/* Optimize by combining instructions for GNU compiler.   Copyright (C) 1987, 1988 Free Software Foundation, Inc.This file is part of GNU CC.GNU CC is free software; you can redistribute it and/or modifyit under the terms of the GNU General Public License as published bythe Free Software Foundation; either version 1, or (at your option)any later version.GNU CC is distributed in the hope that it will be useful,but WITHOUT ANY WARRANTY; without even the implied warranty ofMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See theGNU General Public License for more details.You should have received a copy of the GNU General Public Licensealong with GNU CC; see the file COPYING.  If not, write tothe Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  *//* This module is essentially the "combiner" phase of the U. of Arizona   Portable Optimizer, but redone to work on our list-structured   representation for RTL instead of their string representation.   The LOG_LINKS of each insn identify the most recent assignment   to each REG used in the insn.  It is a list of previous insns,   each of which contains a SET for a REG that is used in this insn   and not used or set in between.  LOG_LINKs never cross basic blocks.   They were set up by the preceding pass (lifetime analysis).   We try to combine each pair of insns joined by a logical link.   We also try to combine triples of insns A, B and C when   C has a link back to B and B has a link back to A.   LOG_LINKS does not have links for use of the CC0.  They don't   need to, because the insn that sets the CC0 is always immediately   before the insn that tests it.  So we always regard a branch   insn as having a logical link to the preceding insn.   We check (with use_crosses_set_p) to avoid combining in such a way   as to move a computation to a place where its value would be different.   Combination is done by mathematically substituting the previous   insn(s) values for the regs they set into the expressions in   the later insns that refer to these regs.  If the result is a valid insn   for our target machine, according to the machine description,   we install it, delete the earlier insns, and update the data flow   information (LOG_LINKS and REG_NOTES) for what we did.   To simplify substitution, we combine only when the earlier insn(s)   consist of only a single assignment.  To simplify updating afterward,   we never combine when a subroutine call appears in the middle.   Since we do not represent assignments to CC0 explicitly except when that   is all an insn does, there is no LOG_LINKS entry in an insn that uses   the condition code for the insn that set the condition code.   Fortunately, these two insns must be consecutive.   Therefore, every JUMP_INSN is taken to have an implicit logical link   to the preceding insn.  This is not quite right, since non-jumps can   also use the condition code; but in practice such insns would not   combine anyway.  */#include <stdio.h>#include "config.h"#include "rtl.h"#include "flags.h"#include "regs.h"#include "basic-block.h"#include "insn-config.h"#include "recog.h"#define max(A,B) ((A) > (B) ? (A) : (B))#define min(A,B) ((A) < (B) ? (A) : (B))/* It is not safe to use ordinary gen_lowpart in combine.   Use gen_lowpart_for_combine instead.  See comments there.  */#define gen_lowpart dont_use_gen_lowpart_you_dummy/* Number of attempts to combine instructions in this function.  */static int combine_attempts;static int distrib_attempts;/* Number of attempts that got as far as substitution in this function.  */static int combine_merges;static int distrib_merges_1, distrib_merges_2;/* Number of instructions combined with added SETs in this function.  */static int combine_extras;/* Number of instructions combined in this function.  */static int combine_successes;static int distrib_successes;/* Totals over entire compilation.  */static int total_attempts, total_merges, total_extras, total_successes;static int total_distrib_attempts, total_distrib_merges_1, total_distrib_merges_2, total_distrib_successes;/* Vector mapping INSN_UIDs to cuids.   The cuids are like uids but increase monononically always.   Combine always uses cuids so that it can compare them.   But actually renumbering the uids, which we used to do,   proves to be a bad idea because it makes it hard to compare   the dumps produced by earlier passes with those from later passes.  */static int *uid_cuid;/* Get the cuid of an insn.  */#define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])/* Record last point of death of (hard or pseudo) register n.  */static rtx *reg_last_death;/* Record last point of modification of (hard or pseudo) register n.  */static rtx *reg_last_set;/* Record the cuid of the last insn that invalidated memory   (anything that writes memory, and subroutine calls).  */static int mem_last_set;/* Record the cuid of the last CALL_INSN   so we can tell whether a potential combination crosses any calls.  */static int last_call_cuid;/* When `subst' is called, this is the insn that is being modified   (by combining in a previous insn).  The PATTERN of this insn   is still the old pattern partially modified and it should not be   looked at, but this may be used to examine the successors of the insn   to judge whether a simplification is valid.  */static rtx subst_insn;/* Record one modification to rtl structure   to be undone by storing old_contents into *where.   is_int is 1 if the contents are an int.  */struct undo{  rtx *where;  rtx old_contents;  int is_int;};struct undo_int{  int *where;  int old_contents;  int is_int;};/* Record a bunch of changes to be undone, up to MAX_UNDO of them.   num_undo says how many are currently recorded.   storage is nonzero if we must undo the allocation of new storage.   The value of storage is what to pass to obfree.  */#define MAX_UNDO 10struct undobuf{  int num_undo;  char *storage;  struct undo undo[MAX_UNDO];};static struct undobuf undobuf;/* Number of times the pseudo being substituted for   was found and replaced.  */static int n_occurrences;static void move_deaths ();static void move_deaths_2 ();void remove_death ();static void record_dead_and_set_regs ();int regno_dead_p ();static int use_crosses_set_p ();static int try_combine ();static rtx try_distrib ();static rtx subst ();static void undo_all ();static void copy_substitutions ();static void add_links ();static void remove_links ();static void add_incs ();static int adjacent_insns_p ();static int check_asm_operands ();static rtx simplify_and_const_int ();static rtx gen_lowpart_for_combine ();static void simplify_set_cc0_and ();/* Main entry point for combiner.  F is the first insn of the function.   NREGS is the first unused pseudo-reg number.  */voidcombine_instructions (f, nregs)     rtx f;     int nregs;{  register rtx insn;  register int i;  register rtx links, nextlinks;  rtx prev;  combine_attempts = 0;  combine_merges = 0;  combine_extras = 0;  combine_successes = 0;  distrib_attempts = 0;  distrib_merges_1 = 0;  distrib_merges_2 = 0;  distrib_successes = 0;  reg_last_death = (rtx *) alloca (nregs * sizeof (rtx));  reg_last_set = (rtx *) alloca (nregs * sizeof (rtx));  bzero (reg_last_death, nregs * sizeof (rtx));  bzero (reg_last_set, nregs * sizeof (rtx));  init_recog ();  /* Compute maximum uid value so uid_cuid can be allocated.  */  for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))    if (INSN_UID (insn) > i)      i = INSN_UID (insn);  uid_cuid = (int *) alloca ((i + 1) * sizeof (int));  /* Compute the mapping from uids to cuids.     Cuids are numbers assigned to insns, like uids,     except that cuids increase monotonically through the code.  */  for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))    INSN_CUID (insn) = ++i;  /* Now scan all the insns in forward order.  */  last_call_cuid = 0;  mem_last_set = 0;  prev = 0;  for (insn = f; insn; insn = NEXT_INSN (insn))    {      if (GET_CODE (insn) == INSN	  || GET_CODE (insn) == CALL_INSN	  || GET_CODE (insn) == JUMP_INSN)	{	retry:	  /* Try this insn with each insn it links back to.  */	  for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))	    if (try_combine (insn, XEXP (links, 0), 0))	      goto retry;	  /* Try each sequence of three linked insns ending with this one.  */	  for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))	    if (GET_CODE (XEXP (links, 0)) != NOTE)	      for (nextlinks = LOG_LINKS (XEXP (links, 0)); nextlinks;		   nextlinks = XEXP (nextlinks, 1))		if (try_combine (insn, XEXP (links, 0), XEXP (nextlinks, 0)))		  goto retry;	  /* Try to combine a jump insn that uses CC0	     with a preceding insn that sets CC0, and maybe with its	     logical predecessor as well.	     This is how we make decrement-and-branch insns.	     We need this special code because data flow connections	     via CC0 do not get entered in LOG_LINKS.  */	  if (GET_CODE (insn) == JUMP_INSN	      && prev != 0	      && GET_CODE (prev) == INSN	      && GET_CODE (PATTERN (prev)) == SET	      && GET_CODE (SET_DEST (PATTERN (prev))) == CC0)	    {	      if (try_combine (insn, prev, 0))		goto retry;	      if (GET_CODE (prev) != NOTE)		for (nextlinks = LOG_LINKS (prev); nextlinks;		     nextlinks = XEXP (nextlinks, 1))		  if (try_combine (insn, prev, XEXP (nextlinks, 0)))		    goto retry;	    }	  /* Try to apply the distributive law to this insn	     and two insns that compute the operands of this one.  */	  for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))	    if (GET_CODE (XEXP (links, 0)) != NOTE)	      for (nextlinks = XEXP (links, 1); nextlinks; nextlinks = XEXP (nextlinks, 1))		if (GET_CODE (XEXP (nextlinks, 0)) != NOTE)		  {		    rtx try_from = 0;		    if (GET_CODE (PATTERN (XEXP (links, 0))) == SET			&& find_reg_note (insn, REG_DEAD, SET_DEST (PATTERN (XEXP (links, 0))))			&& GET_CODE (PATTERN (XEXP (nextlinks, 0))) == SET			&& find_reg_note (insn, REG_DEAD, SET_DEST (PATTERN (XEXP (nextlinks, 0)))))		      try_from = try_distrib (insn, XEXP (links, 0), XEXP (nextlinks, 0));		    if (try_from != 0)		      {			insn = try_from;			goto retry;		      }		  }#if 0/* Turned off because on 68020 it takes four insns to make   something like (a[b / 32] & (1 << (31 - (b % 32)))) != 0   that could actually be optimized, and that's an unlikely piece of code.  */	  /* If an insn gets or sets a bit field, try combining it	     with two different insns whose results it uses.  */	  if (GET_CODE (insn) == INSN	      && GET_CODE (PATTERN (insn)) == SET	      && (GET_CODE (SET_DEST (PATTERN (insn))) == ZERO_EXTRACT		  || GET_CODE (SET_DEST (PATTERN (insn))) == SIGN_EXTRACT		  || GET_CODE (SET_SRC (PATTERN (insn))) == ZERO_EXTRACT		  || GET_CODE (SET_SRC (PATTERN (insn))) == SIGN_EXTRACT))	    {	      for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))		if (GET_CODE (XEXP (links, 0)) != NOTE)		  for (nextlinks = XEXP (links, 1); nextlinks;		       nextlinks = XEXP (nextlinks, 1))		    if (try_combine (insn, XEXP (links, 0), XEXP (nextlinks, 0)))		      goto retry;	    }#endif	  if (GET_CODE (insn) != NOTE)	    record_dead_and_set_regs (insn);	  prev = insn;	}      else if (GET_CODE (insn) != NOTE)	prev = 0;    }  total_attempts += combine_attempts;  total_merges += combine_merges;  total_extras += combine_extras;  total_successes += combine_successes;}/* Try to combine the insns I1 and I2 into I3.   Here I1 appears earlier than I2, which is earlier than I3.   I1 can be zero; then we combine just I2 into I3.    Return 1 if successful; if that happens, I1 and I2 are pseudo-deleted   by turning them into NOTEs, and I3 is modified.   Return 0 if the combination does not work.  Then nothing is changed.  */static inttry_combine (i3, i2, i1)     register rtx i3, i2, i1;{  register rtx newpat;  int added_sets_1 = 0;  int added_sets_2 = 0;  int total_sets;  int i2_is_used;  register rtx link;  int insn_code_number;  rtx i2dest, i2src;  rtx i1dest, i1src;  int maxreg;  rtx temp;  int i;  combine_attempts++;  /* Don't combine with something already used up by combination.  */  if (GET_CODE (i2) == NOTE