gnu1987/gnu1988/gcc-1.21/combine.c

/* 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 distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY.  No author or distributor
accepts responsibility to anyone for the consequences of using it
or for whether it serves any particular purpose or works at all,
unless he says so in writing.  Refer to the GNU CC General Public
License for full details.

Everyone is granted permission to copy, modify and redistribute
GNU CC, but only under the conditions described in the
GNU CC General Public License.   A copy of this license is
supposed to have been given to you along with GNU CC so you
can know your rights and responsibilities.  It should be in a
file named COPYING.  Among other things, the copyright notice
and this notice must be preserved on all copies.  */


/* 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 "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;

/* Number of attempts that got as far as substitution in this function.  */

static int combine_merges;

/* 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;

/* Totals over entire compilation.  */

static int total_attempts, total_merges, total_extras, total_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 short *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.  */

struct undo
{
  rtx *where;
  rtx old_contents;
};

/* 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 10

struct 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 remove_death ();
static void record_dead_and_set_regs ();
int regno_dead_p ();
static int use_crosses_set_p ();
static rtx subst ();
static void undo_all ();
static void copy_substitutions ();
static void add_links ();
static void add_incs ();
static int insn_has_inc_p ();
static int adjacent_insns_p ();
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.  */

void
combine_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;

  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 = (short *) alloca ((i + 1) * sizeof (short));

  /* 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;
	    }
#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
	  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 int
try_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;
  int recog_flags = 0;
  rtx i2dest, i2src;
  rtx i1dest, i1src;
  int maxreg;

  combine_attempts++;

  /* Don't combine with something already used up by combination.  */

  if (GET_CODE (i2) == NOTE
      || (i1 && GET_CODE (i1) == NOTE))
    return 0;

  /* Don't combine across a CALL_INSN, because that would possibly
     change whether the life span of some REGs crosses calls or not,
     and it is a pain to update that information.  */

  if (INSN_CUID (i2) < last_call_cuid
      || (i1 && INSN_CUID (i1) < last_call_cuid))
    return 0;

  /* Can combine only if previous insn is a SET of a REG, a SUBREG or CC0.
     That REG must be either set or dead by the final instruction
     (so that we can safely forget about setting it).
     Also test use_crosses_set_p to make sure that the value
     that is to be substituted for the register
     does not use any registers whose values alter in between.
     Do not try combining with moves from one register to another
     since it is better to let them be tied by register allocation.
     (There is a switch to permit such combination; except the insns
     that copy a function value into another register are never combined
     because moving that too far away from the function call could cause
     something else to be stored in that register in the interim.)

     A set of a SUBREG is considered as if it were a set from
     SUBREG.  Thus, (SET (SUBREG:X (REG:Y...)) (something:X...))
     is handled by substituting (SUBREG:Y (something:X...)) for (REG:Y...).  */

  if (GET_CODE (PATTERN (i2)) != SET)
    return 0;
  i2dest = SET_DEST (PATTERN (i2));
  i2src = SET_SRC (PATTERN (i2));
  if (GET_CODE (i2dest) == SUBREG)
    {
      i2dest = SUBREG_REG (i2dest);
      i2src = gen_rtx (SUBREG, GET_MODE (i2dest), i2src, 0);
    }
  if (GET_CODE (i2dest) != CC0
      && (GET_CODE (i2dest) != REG
	  || (GET_CODE (i2src) == REG
	      && (!flag_combine_regs
		  || FUNCTION_VALUE_REGNO_P (REGNO (i2src))))
	  || GET_CODE (i2src) == CALL
	  || use_crosses_set_p (i2src, INSN_CUID (i2))))
    return 0;

  if (i1 != 0)
    {
      if (GET_CODE (PATTERN (i1)) != SET)
	return 0;
      i1dest = SET_DEST (PATTERN (i1));
      i1src = SET_SRC (PATTERN (i1));
      if (GET_CODE (i1dest) == SUBREG)
	{
	  i1dest = SUBREG_REG (i1dest);
	  i1src = gen_rtx (SUBREG, GET_MODE (i1dest), i1src, 0);
	}
      if (GET_CODE (i1dest) != CC0
	  && (GET_CODE (i1dest) != REG
	      || (GET_CODE (i1src) == REG
		  && (!flag_combine_regs
		      || FUNCTION_VALUE_REGNO_P (REGNO (i1src))))
	      || GET_CODE (i1src) == CALL
	      || use_crosses_set_p (i1src, INSN_CUID (i1))))
	return 0;
    }

  /* If I1 or I2 contains an autoincrement or autodecrement,
     make sure that register is not used between there and I3.
     Also insist that I3 not be a jump; if it were one
     and the incremented register were spilled, we would lose.  */
  if ((link = find_reg_note (i2, REG_INC, 0)) != 0
      && (GET_CODE (i3) == JUMP_INSN
	  || reg_used_between_p (XEXP (link, 0), i2, i3)))
    return 0;

  if (i1 && (link = find_reg_note (i1, REG_INC, 0)) != 0
      && (GET_CODE (i3) == JUMP_INSN
	  || reg_used_between_p (XEXP (link, 0), i1, i3)))
    return 0;

  /* See if the SETs in i1 or i2 need to be kept around in the merged
     instruction: whenever the value set there is still needed past i3.  */
  added_sets_2 = (GET_CODE (i2dest) != CC0
		  && ! dead_or_set_p (i3, i2dest));
  if (i1)
    added_sets_1 = ! (dead_or_set_p (i3, i1dest)
		      || dead_or_set_p (i2, i1dest));

  combine_merges++;

  undobuf.num_undo = 0;
  undobuf.storage = 0;

  /* Substitute in the latest insn for the regs set by the earlier ones.  */

  maxreg = max_reg_num ();

  subst_insn = i3;
  n_occurrences = 0;		/* `subst' counts here */

  newpat = subst (PATTERN (i3), i2dest, i2src);
  /* Record whether i2's body now appears within i3's body.  */
  i2_is_used = n_occurrences;

  if (i1)
    {
      n_occurrences = 0;
      newpat = subst (newpat, i1dest, i1src);
    }

  if (GET_CODE (PATTERN (i3)) == SET
      && SET_DEST (PATTERN (i3)) == cc0_rtx
      && (GET_CODE (SET_SRC (PATTERN (i3))) == AND
	  || GET_CODE (SET_SRC (PATTERN (i3))) == LSHIFTRT)
      && next_insn_tests_no_inequality (i3))
    simplify_set_cc0_and (i3);

  if (max_reg_num () != maxreg)
    abort ();

  /* If the actions of the earler insns must be kept
     in addition to substituting them into the latest one,
     we must make a new PARALLEL for the latest insn
     to hold additional the SETs.  */

  if (added_sets_1 || added_sets_2)
    {
      combine_extras++;

      /* Arrange to free later what we allocate now
	 if we don't accept this combination.  */
      if (!undobuf.storage)
	undobuf.storage = (char *) oballoc (0);

      if (GET_CODE (newpat) == PARALLEL)
	{
	  rtvec old = XVEC (newpat, 0);
	  total_sets = XVECLEN (newpat, 0) + added_sets_1 + added_sets_2;
	  newpat = gen_rtx (PARALLEL, VOIDmode, rtvec_alloc (total_sets));
	  bcopy (&old->elem[0], &XVECEXP (newpat, 0, 0),
		 sizeof (old->elem[0]) * old->num_elem);
	}
      else
	{
	  rtx old = newpat;
	  total_sets = 1 + added_sets_1 + added_sets_2;
	  newpat = gen_rtx (PARALLEL, VOIDmode, rtvec_alloc (total_sets));
	  XVECEXP (newpat, 0, 0) = old;
	}
     if (added_sets_1)
	{
	  XVECEXP (newpat, 0, --total_sets) = PATTERN (i1);
	}
     if (added_sets_2)
	{
	  /* If there is no I1, use I2's body as is.  */
	  if (i1 == 0
	  /* If I2 was stuck into I3, then anything within it has
	     already had I1 substituted into it when that was done to I3.  */
	      || i2_is_used)
	    {
	      XVECEXP (newpat, 0, --total_sets) = PATTERN (i2);
	    }
	  else
	    XVECEXP (newpat, 0, --total_sets)
	      = subst (PATTERN (i2), i1dest, i1src);
	}
    }

  /* Fail if an autoincrement side-effect has been duplicated.  */
  if ((i2_is_used > 1 && find_reg_note (i2, REG_INC, 0) != 0)
      || (i1 != 0 && n_occurrences > 1 && find_reg_note (i1, REG_INC, 0) != 0))
    {
      undo_all ();
      return 0;
    }

  /* Is the result of combination a valid instruction?  */
  insn_code_number = recog (newpat, i3);

  if (insn_code_number >= 0)
    {
      /* Yes.  Install it.  */
      register int regno;
      INSN_CODE (i3) = insn_code_number;
      PATTERN (i3) = newpat;
      /* If anything was substituted more than once,
	 copy it to avoid invalid shared rtl structure.  */
      copy_substitutions ();
      /* The data flowing into I2 now flows into I3.
	 But we cannot always move all of I2's LOG_LINKS into I3,
	 since they must go to a setting of a REG from the
	 first use following.  If I2 was the first use following a set,
	 I3 is now a use, but it is not the first use
	 if some instruction between I2 and I3 is also a use.
	 Here, for simplicity, we move all the links only if
	 there are no real insns between I2 and I3.
	 Otherwise, we move only links that correspond to regs
	 that used to die in I2.  They are always safe to move.  */
      add_links (i3, i2, adjacent_insns_p (i2, i3));
      /* Most REGs that previously died in I2 now die in I3.  */ 
      move_deaths (i2src, INSN_CUID (i2), i3);
      if (GET_CODE (i2dest) == REG)
	{
	  /* If the reg formerly set in I2 died only once and that was in I3,
	     zero its use count so it won't make `reload' do any work.  */
	  regno = REGNO (i2dest);
	  if (! added_sets_2)
	    {
	      reg_n_sets[regno]--;
	      /* Used to check  && regno_dead_p (regno, i3)  also here.  */
	      if (reg_n_sets[regno] == 0
		  && ! (basic_block_live_at_start[0][regno / HOST_BITS_PER_INT]
			& (1 << (regno % HOST_BITS_PER_INT))))
		reg_n_refs[regno] = 0;
	    }
	  /* If a ref to REGNO was substituted into I3 from I2,
	     then it still dies there if it previously did.
	     Otherwise either REGNO never did die in I3 so remove_death is safe
	     or this entire life of REGNO is gone so remove its death.  */
	  if (!added_sets_2
	      && ! reg_mentioned_p (i2dest, PATTERN (i3)))
	    remove_death (regno, i3);
	}
      /* Any registers previously autoincremented in I2
	 are now incremented in I3.  */
      add_incs (i3, REG_NOTES (i2));
      if (i1)
	{
	  /* Likewise, merge the info from I1 and get rid of it.  */
	  add_links (i3, i1,
		     adjacent_insns_p (i1, i2) && adjacent_insns_p (i2, i3));
	  move_deaths (i1src, INSN_CUID (i1), i3);
	  if (GET_CODE (i1dest) == REG)
	    {
	      regno = REGNO (i1dest);
	      if (! added_sets_1)
		{
		  reg_n_sets[regno]--;
		  /* Used to also check  && regno_dead_p (regno, i3) here.  */

		  if (reg_n_sets[regno] == 0
		      && ! (basic_block_live_at_start[0][regno / HOST_BITS_PER_INT]
			    & (1 << (regno % HOST_BITS_PER_INT))))

		    reg_n_refs[regno] = 0;
		}
	      /* If a ref to REGNO was substituted into I3 from I1,
		 then it still dies there if it previously did.
		 Else either REGNO never did die in I3 so remove_death is safe
		 or this entire life of REGNO is gone so remove its death.  */
	      if (! added_sets_1
		  && ! reg_mentioned_p (i1dest, PATTERN (i3)))
		remove_death (regno, i3);
	    }
	  add_incs (i3, REG_NOTES (i1));
	  LOG_LINKS (i1) = 0;
	  PUT_CODE (i1, NOTE);
	  NOTE_LINE_NUMBER (i1) = NOTE_INSN_DELETED;
	  NOTE_SOURCE_FILE (i1) = 0;
	}
      /* Get rid of I2.  */
      LOG_LINKS (i2) = 0;
      PUT_CODE (i2, NOTE);
      NOTE_LINE_NUMBER (i2) = NOTE_INSN_DELETED;
      NOTE_SOURCE_FILE (i2) = 0;

      combine_successes++;
      return 1;
    }

  /* Failure: change I3 back the way it was.  */
  undo_all ();

  return 0;
}

/* Undo all the modifications recorded in undobuf.  */

static void
undo_all ()
{
  register int i;
  if (undobuf.num_undo > MAX_UNDO)
    undobuf.num_undo = MAX_UNDO;
  for (i = undobuf.num_undo - 1; i >= 0; i--)
    *undobuf.undo[i].where = undobuf.undo[i].old_contents;
  if (undobuf.storage)
    obfree (undobuf.storage);
  undobuf.num_undo = 0;
  undobuf.storage = 0;
}

/* If this insn had more than one substitution,
   copy all but one, so that no invalid shared substructure is introduced.  */

static void
copy_substitutions ()
{
  register int i;
  if (undobuf.num_undo > 1)
    {
      for (i = undobuf.num_undo - 1; i >= 1; i--)
	*undobuf.undo[i].where = copy_rtx (*undobuf.undo[i].where);
    }
}

/* Throughout X, replace FROM with TO, and return the result.
   The result is TO if X is FROM;
   otherwise the result is X, but its contents may have been modified.
   If they were modified, a record was made in undobuf so that
   undo_all will (among other things) return X to its original state.

   If the number of changes necessary is too much to record to undo,
   the excess changes are not made, so the result is invalid.
   The changes already made can still be undone.
   undobuf.num_undo is incremented for such changes, so by testing that
   the caller can tell whether the result is valid.

   `n_occurrences' is incremented each time FROM is replaced.  */

static rtx
subst (x, from, to)
     register rtx x, from, to;
{
  register char *fmt;
  register int len, i;
  register enum rtx_code code;
  char was_replaced[2];

#define SUBST(INTO, NEWVAL)  \
 do { if (undobuf.num_undo < MAX_UNDO)					\
	{								\
	  undobuf.undo[undobuf.num_undo].where = &INTO;			\
	  undobuf.undo[undobuf.num_undo].old_contents = INTO;		\
	  INTO = NEWVAL;						\
	}								\
      undobuf.num_undo++; } while (0)

/* FAKE_EXTEND_SAFE_P (MODE, FROM) is 1 if (subreg:MODE FROM 0) is a safe
   replacement for (zero_extend:MODE FROM) or (sign_extend:MODE FROM).
   If it is 0, that cannot be done because it might cause a badly aligned
   memory reference.  */

#ifndef STRICT_ALIGNMENT
#define FAKE_EXTEND_SAFE_P(MODE, FROM)  \
   (GET_CODE (FROM) == REG ||				\
    (GET_CODE (FROM) == MEM				\
     && offsetable_address_p ((MODE), XEXP ((FROM), 0))	\
     && ! mode_dependent_address_p ((XEXP ((FROM), 0)))))
#else
#define FAKE_EXTEND_SAFE_P(MODE, FROM) (GET_CODE (FROM) == REG)
#endif

  if (x == from)
    return to;

  /* It is possible to have a subexpression appear twice in the insn.
     Suppose that FROM is a register that appears within TO.
     Then, after that subexpression has been scanned once by `subst',
     the second time it is scanned, TO may be found.  If we were
     to scan TO here, we would find FROM within it and create a
     self-referent rtl structure which is completely wrong.  */
  if (x == to)
    return to;

  code = GET_CODE (x);

  /* A little bit of algebraic simplification here.  */
  switch (code)
    {
      /* This case has no effect except to speed things up.  */
    case REG:
    case CONST_INT:
    case CONST:
    case SYMBOL_REF:
    case LABEL_REF:
    case PC:
    case CC0:
      return x;
    }

  was_replaced[0] = 0;
  was_replaced[1] = 0;

  len = GET_RTX_LENGTH (code);
  fmt = GET_RTX_FORMAT (code);

  /* Don't replace FROM where it is being stored in rather than used.  */
  if (code == SET && SET_DEST (x) == from)
    fmt = "ie";
  if (code == SET && GET_CODE (SET_DEST (x)) == SUBREG
      && SUBREG_REG (SET_DEST (x)) == from)
    fmt = "ie";

  for (i = 0; i < len; i++)
    {
      if (fmt[i] == 'E')
	{
	  register int j;
	  for (j = XVECLEN (x, i) - 1; j >= 0; j--)
	    {
	      register rtx new;
	      if (XVECEXP (x, i, j) == from)
		new = to, n_occurrences++;
	      else
		new = subst (XVECEXP (x, i, j), from, to);
	      if (new != XVECEXP (x, i, j))
		SUBST (XVECEXP (x, i, j), new);
	    }
	}
      else if (fmt[i] == 'e')
	{
	  register rtx new;

	  if (XEXP (x, i) == from)
	    {
	      new = to;
	      n_occurrences++;
	      if (i < 2)
		was_replaced[i] = 1;
	    }
	  else
	    new = subst (XEXP (x, i), from, to);

	  if (new != XEXP (x, i))
	    SUBST (XEXP (x, i), new);
	}
    }

  /* A little bit of algebraic simplification here.  */
  switch (code)
    {
    case SUBREG:
      /* Changing mode twice with SUBREG => just change it once,
	 or not at all if changing back to starting mode.  */
      if (SUBREG_REG (x) == to
	  && GET_CODE (to) == SUBREG
	  && SUBREG_WORD (x) == 0
	  && SUBREG_WORD (to) == 0)
	{
	  if (GET_MODE (x) == GET_MODE (SUBREG_REG (to)))
	    return SUBREG_REG (to);
	  SUBST (SUBREG_REG (x), SUBREG_REG (to));
	}
      break;

    case NOT:
    case NEG:
      /* Don't let substitution introduce double-negatives.  */
      if (was_replaced[0]
	  && GET_CODE (to) == code)
	return XEXP (to, 0);
      break;

    case FLOAT_TRUNCATE:
      /* (float_truncate:SF (float_extend:DF foo:SF)) = foo:SF.  */
      if (was_replaced[0]
	  && GET_CODE (to) == FLOAT_EXTEND
	  && GET_MODE (XEXP (to, 0)) == GET_MODE (x))
	return XEXP (to, 0);
      break;

    case PLUS:
      /* In (plus <foo> (ashift <bar> <n>))
	 change the shift to a multiply so we can recognize
	 scaled indexed addresses.  */
      if ((was_replaced[0]
	   || was_replaced[1])
	  && GET_CODE (to) == ASHIFT
	  && GET_CODE (XEXP (to, 1)) == CONST_INT
	  && INTVAL (XEXP (to, 1)) < HOST_BITS_PER_INT)
	{
	  rtx temp;
	  if (!undobuf.storage)
	    undobuf.storage = (char *) oballoc (0);
	  temp = gen_rtx (MULT, GET_MODE (to),
			  XEXP (to, 0),
			  gen_rtx (CONST_INT, VOIDmode,
				   1 << INTVAL (XEXP (to, 1))));
	  if (was_replaced[0])
	    SUBST (XEXP (x, 0), temp);
	  else
	    SUBST (XEXP (x, 1), temp);
	}
      /* (plus X (neg Y)) becomes (minus X Y).  */
      if (GET_CODE (XEXP (x, 1)) == NEG)
	{
	  if (!undobuf.storage)
	    undobuf.storage = (char *) oballoc (0);
	  return gen_rtx (MINUS, GET_MODE (x),
			  XEXP (x, 0), XEXP (XEXP (x, 1), 0));
	}
      /* (plus (neg X) Y) becomes (minus Y X).  */
      if (GET_CODE (XEXP (x, 0)) == NEG)
	{
	  if (!undobuf.storage)
	    undobuf.storage = (char *) oballoc (0);
	  return gen_rtx (MINUS, GET_MODE (x),
			  XEXP (x, 1), XEXP (XEXP (x, 0), 0));
	}
      /* (plus (plus x c1) c2) => (plus x c1+c2) */
      if (GET_CODE (XEXP (x, 1)) == CONST_INT
	  && GET_CODE (XEXP (x, 0)) == PLUS
	  && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT)
	{
	  int sum = (INTVAL (XEXP (x, 1))
		     + INTVAL (XEXP (XEXP (x, 0), 1)));
	  if (sum == 0)
	    return XEXP (XEXP (x, 0), 0);
	  if (!undobuf.storage)
	    undobuf.storage = (char *) oballoc (0);
	  SUBST (XEXP (x, 1), gen_rtx (CONST_INT, VOIDmode, sum));
	  SUBST (XEXP (x, 0), XEXP (XEXP (x, 0), 0));
	  break;
	}
      /* If we have something (putative index) being added to a sum,
	 associate it so that any constant term is outermost.
	 That's because that's the way indexed addresses are
	 now supposed to appear.  */
      if (((was_replaced[0] && GET_CODE (XEXP (x, 1)) == PLUS)
	   || (was_replaced[1] && GET_CODE (XEXP (x, 0)) == PLUS))
	  ||
	  ((was_replaced[0] || was_replaced[1])
	   && GET_CODE (to) == PLUS))
	{
	  rtx offset = 0, base, index;
	  if (GET_CODE (to) != PLUS)
	    {
	      index = to;
	      base = was_replaced[0] ? XEXP (x, 1) : XEXP (x, 0);
	    }
	  else
	    {
	      index = was_replaced[0] ? XEXP (x, 1) : XEXP (x, 0);
	      base = to;
	    }
	  if (CONSTANT_ADDRESS_P (XEXP (base, 0)))
	    {
	      offset = XEXP (base, 0);
	      base = XEXP (base, 1);
	    }
	  else if (CONSTANT_ADDRESS_P (XEXP (base, 1)))
	    {
	      offset = XEXP (base, 1);
	      base = XEXP (base, 0);
	    }
	  if (offset != 0)
	    {
	      if (!undobuf.storage)
		undobuf.storage = (char *) oballoc (0);
	      if (GET_CODE (offset) == CONST_INT)
		return plus_constant (gen_rtx (PLUS, GET_MODE (index),
					       base, index),
				      INTVAL (offset));
	      if (GET_CODE (index) == CONST_INT)
		return plus_constant (gen_rtx (PLUS, GET_MODE (offset),
					       base, offset),
				      INTVAL (index));
	      return gen_rtx (PLUS, GET_MODE (index),
			      gen_rtx (PLUS, GET_MODE (index),
				       base, index),
			      offset);
	    }
	}
      break;

    case MINUS:
      /* Can simplify (minus:VOIDmode (zero/sign_extend FOO) CONST)
	 (which is a compare instruction, not a subtract instruction)
	 to (minus FOO CONST) if CONST fits in FOO's mode
	 and we are only testing equality.
	 In fact, this is valid for zero_extend if what follows is an
	 unsigned comparison, and for sign_extend with a signed comparison.  */
      if (GET_MODE (x) == VOIDmode
	  && was_replaced[0]
	  && (GET_CODE (to) == ZERO_EXTEND || GET_CODE (to) == SIGN_EXTEND)
	  && next_insn_tests_no_inequality (subst_insn)
	  && GET_CODE (XEXP (x, 1)) == CONST_INT
	  /* This is overly cautious by one bit, but saves worrying about
	     whether it is zero-extension or sign extension.  */
	  && ((unsigned) INTVAL (XEXP (x, 1))
	      < (1 << (GET_MODE_BITSIZE (GET_MODE (XEXP (to, 0))) - 1))))
	SUBST (XEXP (x, 0), XEXP (to, 0));
      break;

    case EQ:
    case NE:
      /* If comparing a subreg against zero, discard the subreg.  */
      if (was_replaced[0]
	  && GET_CODE (to) == SUBREG
	  && SUBREG_WORD (to) == 0
	  && XEXP (x, 1) == const0_rtx)
	SUBST (XEXP (x, 0), SUBREG_REG (to));

      /* If comparing a ZERO_EXTRACT against zero,
	 canonicalize to a SIGN_EXTRACT,
	 since the two are equivalent here.  */
      if (was_replaced[0]
	  && GET_CODE (to) == ZERO_EXTRACT
	  && XEXP (x, 1) == const0_rtx)
	{
	  if (!undobuf.storage)
	    undobuf.storage = (char *) oballoc (0);
	  SUBST (XEXP (x, 0),
		 gen_rtx (SIGN_EXTRACT, GET_MODE (to),
			  XEXP (to, 0), XEXP (to, 1),
			  XEXP (to, 2)));
	}
      /* If we are putting (ASHIFT 1 x) into (EQ (AND ... y) 0),
	 arrange to return (EQ (SIGN_EXTRACT y 1 x) 0),
	 which is what jump-on-bit instructions are written with.  */
      else if (XEXP (x, 1) == const0_rtx
	       && GET_CODE (XEXP (x, 0)) == AND
	       && (XEXP (XEXP (x, 0), 0) == to
		   || XEXP (XEXP (x, 0), 1) == to)
	       && GET_CODE (to) == ASHIFT
	       && XEXP (to, 0) == const1_rtx)
	{
	  register rtx y = XEXP (XEXP (x, 0),
				 XEXP (XEXP (x, 0), 0) == to);
	  if (!undobuf.storage)
	    undobuf.storage = (char *) oballoc (0);
	  SUBST (XEXP (x, 0),
		 gen_rtx (SIGN_EXTRACT, GET_MODE (to),
			  y,
			  const1_rtx, XEXP (to, 1)));
	}

      break;

    case ZERO_EXTEND:
      if (was_replaced[0]
	  && GET_CODE (to) == ZERO_EXTEND)
	SUBST (XEXP (x, 0), XEXP (to, 0));
      /* Zero-extending the result of an and with a constant can be done
	 with a wider and.  */
      if (was_replaced[0]
	  && GET_CODE (to) == AND
	  && GET_CODE (XEXP (to, 1)) == CONST_INT
	  && FAKE_EXTEND_SAFE_P (GET_MODE (x), XEXP (to, 0))
	  /* Avoid getting wrong result if the constant has high bits set
	     that are irrelevant in the narrow mode where it is being used.  */
	  && 0 == (INTVAL (XEXP (to, 1))
		   & ~ GET_MODE_MASK (GET_MODE (to))))
	{
	  if (!undobuf.storage)
	    undobuf.storage = (char *) oballoc (0);
	  return gen_rtx (AND, GET_MODE (x),
			  gen_lowpart_for_combine (GET_MODE (x), XEXP (to, 0)),
			  XEXP (to, 1));
	} 
      /* Change (zero_extend:M (subreg:N (zero_extract:M ...) 0))
	 to (zero_extract:M ...) if the field extracted fits in mode N.  */
      if (GET_CODE (XEXP (x, 0)) == SUBREG
	  && GET_CODE (XEXP (XEXP (x, 0), 0)) == ZERO_EXTRACT
	  && GET_CODE (XEXP (XEXP (XEXP (x, 0), 0), 1)) == CONST_INT
	  && (INTVAL (XEXP (XEXP (XEXP (x, 0), 0), 1))
	      <= GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0)))))
	{
	  return XEXP (XEXP (x, 0), 0);
	}
      break;

    case SIGN_EXTEND:
      if (was_replaced[0]
	  && GET_CODE (to) == SIGN_EXTEND)
	SUBST (XEXP (x, 0), XEXP (to, 0));
      /* Sign-extending the result of an and with a constant can be done
	 with a wider and, provided the high bit of the constant is 0.  */
      if (was_replaced[0]
	  && GET_CODE (to) == AND
	  && GET_CODE (XEXP (to, 1)) == CONST_INT
	  && FAKE_EXTEND_SAFE_P (GET_MODE (x), XEXP (to, 0))
	  && ((INTVAL (XEXP (to, 1))
	       & (-1 << (GET_MODE_BITSIZE (GET_MODE (to)) - 1)))
	      == 0))
	{
	  if (!undobuf.storage)
	    undobuf.storage = (char *) oballoc (0);
	  return gen_rtx (AND, GET_MODE (x),
			  gen_lowpart_for_combine (GET_MODE (x), XEXP (to, 0)),
			  XEXP (to, 1));
	 } 
      break;

    case SET:
      /* In (set (zero-extract <x> <n> <y>) (and <foo> <(2**n-1) | anything>))
	 the `and' can be deleted.  This can happen when storing a bit
	 that came from a set-flag insn followed by masking to one bit.  */
      if (GET_CODE (XEXP (x, 0)) == ZERO_EXTRACT
	  && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
	  && was_replaced[1]
	  && GET_CODE (to) == AND
	  && GET_CODE (XEXP (to, 1)) == CONST_INT
	  && 0 == (((1 << INTVAL (XEXP (XEXP (x, 0), 1))) - 1)
		   & ~ INTVAL (XEXP (to, 1))))
	{
	  SUBST (XEXP (x, 1), XEXP (to, 0));
	} 
      /* In (set (zero-extract <x> <n> <y>)
	         (subreg (and <foo> <(2**n-1) | anything>)))
	 the `and' can be deleted.  */
      if (GET_CODE (XEXP (x, 0)) == ZERO_EXTRACT
	  && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
	  && GET_CODE (XEXP (x, 1)) == SUBREG
	  && SUBREG_WORD (XEXP (x, 1)) == 0
	  && GET_CODE (SUBREG_REG (XEXP (x, 1))) == AND
	  && GET_CODE (XEXP (SUBREG_REG (XEXP (x, 1)), 1)) == CONST_INT
	  && 0 == (((1 << INTVAL (XEXP (XEXP (x, 0), 1))) - 1)
		   & ~ INTVAL (XEXP (SUBREG_REG (XEXP (x, 1)), 1))))
	{
	  SUBST (SUBREG_REG (XEXP (x, 1)), XEXP (SUBREG_REG (XEXP (x, 1)), 0));
	} 
      /* (set (zero_extract ...) (and/or/xor (zero_extract ...) const)),
	 if both zero_extracts have the byte size and position,
	 can be changed to avoid the byte extracts.  */
      if ((GET_CODE (XEXP (x, 0)) == ZERO_EXTRACT
	   || GET_CODE (XEXP (x, 0)) == SIGN_EXTRACT)
	  && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
	  && (GET_CODE (XEXP (x, 1)) == AND
	      || GET_CODE (XEXP (x, 1)) == IOR
	      || GET_CODE (XEXP (x, 1)) == XOR)
	  && (GET_CODE (XEXP (XEXP (x, 1), 0)) == ZERO_EXTRACT
	      || GET_CODE (XEXP (XEXP (x, 1), 0)) == SIGN_EXTRACT)
	  && rtx_equal_p (XEXP (XEXP (XEXP (x, 1), 0), 1),
			  XEXP (XEXP (x, 0), 1))
	  && rtx_equal_p (XEXP (XEXP (XEXP (x, 1), 0), 2),
			  XEXP (XEXP (x, 0), 2))
	  && GET_CODE (XEXP (XEXP (x, 1), 0)) == GET_CODE (XEXP (x, 0))
	  && GET_CODE (XEXP (XEXP (x, 1), 1)) == CONST_INT)
	{
#ifdef BITS_BIG_ENDIAN
	  int shiftcount
	    = GET_MODE_BITSIZE (GET_MODE (XEXP (XEXP (x, 0), 0)))
	      - INTVAL (XEXP (XEXP (x, 0), 1)) - INTVAL (XEXP (XEXP (x, 0), 2));
#else
	  int shiftcount
	    = INTVAL (XEXP (XEXP (x, 0), 2));
#endif
	  if (!undobuf.storage)
	    undobuf.storage = (char *) oballoc (0);
	  return
	    gen_rtx (SET, VOIDmode,
		     XEXP (XEXP (x, 0), 0),
		     gen_rtx (GET_CODE (XEXP (x, 1)),
			      GET_MODE (XEXP (XEXP (x, 0), 0)),
			      XEXP (XEXP (XEXP (x, 1), 0), 0),
			      gen_rtx (CONST_INT, VOIDmode,
				       (INTVAL (XEXP (XEXP (x, 1), 1))
					<< shiftcount)
				       + (GET_CODE (XEXP (x, 1)) == AND
					  ? (1 << shiftcount) - 1
					  : 0))));
	}
      break;

    case AND:
      if (GET_CODE (XEXP (x, 1)) == CONST_INT)
	{
	  rtx tem = simplify_and_const_int (x, to);
	  if (tem)
	    return tem;
	}
      break;

    case FLOAT:
      /* (float (sign_extend <X>)) = (float <X>).  */
      if (was_replaced[0]
	  && GET_CODE (to) == SIGN_EXTEND)
	SUBST (XEXP (x, 0), XEXP (to, 0));
      break;

    case ZERO_EXTRACT:
      /* (ZERO_EXTRACT (TRUNCATE x)...)
	 can become (ZERO_EXTRACT x ...).  */
      if (was_replaced[0]
	  && GET_CODE (to) == TRUNCATE)
	{
#ifdef BITS_BIG_ENDIAN
	  if (GET_CODE (XEXP (x, 2)) == CONST_INT)
	    {
	      if (!undobuf.storage)
		undobuf.storage = (char *) oballoc (0);
	      /* On a big-endian machine, must increment the bit-number
		 since sign bit is farther away in the pre-truncated value.  */
	      return gen_rtx (ZERO_EXTRACT, GET_MODE (x),
			      XEXP (to, 0),
			      XEXP (x, 1),
			      gen_rtx (CONST_INT, VOIDmode,
				       (INTVAL (XEXP (x, 2))
					+ GET_MODE_BITSIZE (GET_MODE (XEXP (to, 0)))
					- GET_MODE_BITSIZE (GET_MODE (to)))));
	    }
#else
	  SUBST (XEXP (x, 0), XEXP (to, 0));
#endif
	}
      /* Extracting a single bit from the result of a shift:
	 see which bit it was before the shift and extract that directly.  */
      if (was_replaced[0]
	  && (GET_CODE (to) == ASHIFTRT || GET_CODE (to) == LSHIFTRT
	      || GET_CODE (to) == ASHIFT || GET_CODE (to) == LSHIFT)
	  && GET_CODE (XEXP (to, 1)) == CONST_INT
	  && XEXP (x, 1) == const1_rtx
	  && GET_CODE (XEXP (x, 2)) == CONST_INT)
	{
	  int shift = INTVAL (XEXP (to, 1));
	  int newpos;
	  if (GET_CODE (to) == ASHIFT || GET_CODE (to) == LSHIFT)
	    shift = - shift;
#ifdef BITS_BIG_ENDIAN
	  shift = - shift;
#endif
	  newpos = INTVAL (XEXP (x, 2)) + shift;
	  if (newpos >= 0 &&
	      newpos < GET_MODE_BITSIZE (GET_MODE (to)))
	    {
	      if (!undobuf.storage)
		undobuf.storage = (char *) oballoc (0);
	      return gen_rtx (ZERO_EXTRACT, GET_MODE (x),
			      XEXP (to, 0), const1_rtx,
			      gen_rtx (CONST_INT, VOIDmode, newpos));
	    }
	}
      break;

    case LSHIFTRT:
    case ASHIFTRT:
    case ROTATE:
    case ROTATERT:
#ifdef SHIFT_COUNT_TRUNCATED
      /* (lshift <X> (sign_extend <Y>)) = (lshift <X> <Y>) (most machines).
	 True for all kinds of shifts and also for zero_extend.  */
      if (was_replaced[1]
	  && (GET_CODE (to) == SIGN_EXTEND
	      || GET_CODE (to) == ZERO_EXTEND)
	  && FAKE_EXTEND_SAFE_P (GET_MODE (to), XEXP (to, 0)))
	{
	  if (!undobuf.storage)
	    undobuf.storage = (char *) oballoc (0);
	  SUBST (XEXP (x, 1),
		 /* This is a perverse SUBREG, wider than its base.  */
		 gen_lowpart_for_combine (GET_MODE (to), XEXP (to, 0)));
	}
#endif
      /* Two shifts in a row of same kind
	 in same direction with constant counts
	 may be combined.  */
      if (was_replaced[0]
	  && GET_CODE (to) == GET_CODE (x)
	  && GET_CODE (XEXP (x, 1)) == CONST_INT
	  && GET_CODE (XEXP (to, 1)) == CONST_INT
	  && INTVAL (XEXP (to, 1)) > 0
	  && INTVAL (XEXP (x, 1)) > 0
	  && (INTVAL (XEXP (x, 1)) + INTVAL (XEXP (to, 1))
	      < GET_MODE_BITSIZE (GET_MODE (x))))
	{
	  if (!undobuf.storage)
	    undobuf.storage = (char *) oballoc (0);
	  return gen_rtx (GET_CODE (x), GET_MODE (x),
			  XEXP (to, 0),
			  gen_rtx (CONST_INT, VOIDmode,
				   INTVAL (XEXP (x, 1))
				   + INTVAL (XEXP (to, 1))));
	}
      break;

    case LSHIFT:
    case ASHIFT:
#ifdef SHIFT_COUNT_TRUNCATED
      /* (lshift <X> (sign_extend <Y>)) = (lshift <X> <Y>) (most machines).
	 True for all kinds of shifts and also for zero_extend.  */
      if (was_replaced[1]
	  && (GET_CODE (to) == SIGN_EXTEND
	      || GET_CODE (to) == ZERO_EXTEND))
	{
	  if (!undobuf.storage)
	    undobuf.storage = (char *) oballoc (0);
	  SUBST (XEXP (x, 1), gen_rtx (SUBREG, GET_MODE (to), XEXP (to, 0), 0));
	}
#endif
      /* (lshift (and (lshiftrt <foo> <X>) <Y>) <X>)
	 happens copying between bit fields in similar structures.
	 It can be replaced by one and instruction.
	 It does not matter whether the shifts are logical or arithmetic.  */
      if (GET_CODE (XEXP (x, 0)) == AND
	  && GET_CODE (XEXP (x, 1)) == CONST_INT
	  && INTVAL (XEXP (x, 1)) > 0
	  && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
	  && XEXP (XEXP (x, 0), 0) == to
	  && (GET_CODE (to) == LSHIFTRT
	      || GET_CODE (to) == ASHIFTRT)
#if 0
/* I now believe this restriction is unnecessary.
   The outer shift will discard those bits in any case, right?  */

	      /* If inner shift is arithmetic, either it shifts left or
		 the bits it shifts the sign into are zeroed by the and.  */
		  && (INTVAL (XEXP (x, 1)) < 0
		      || ((unsigned) INTVAL (XEXP (XEXP (x, 0), 1))
			  < 1 << (GET_MODE_BITSIZE (GET_MODE (x))
				  - INTVAL (XEXP (x, 0)))))
#endif
	  && GET_CODE (XEXP (to, 1)) == CONST_INT
	  && INTVAL (XEXP (x, 1)) == INTVAL (XEXP (to, 1)))
	{
	  if (!undobuf.storage)
	    undobuf.storage = (char *) oballoc (0);
	  /* The constant in the new `and' is <Y> << <X>
	     but clear out all bits that don't belong in our mode.  */
	  return gen_rtx (AND, GET_MODE (x), XEXP (to, 0),
			  gen_rtx (CONST_INT, VOIDmode,
				   (GET_MODE_MASK (GET_MODE (x))
				    & ((GET_MODE_MASK (GET_MODE (x))
					& INTVAL (XEXP (XEXP (x, 0), 1)))
				       << INTVAL (XEXP (x, 1))))));
	} 
      /* Two shifts in a row in same direction with constant counts
	 may be combined.  */
      if (was_replaced[0]
	  && (GET_CODE (to) == ASHIFT || GET_CODE (to) == LSHIFT)
	  && GET_CODE (XEXP (x, 1)) == CONST_INT
	  && GET_CODE (XEXP (to, 1)) == CONST_INT
	  && INTVAL (XEXP (to, 1)) > 0
	  && INTVAL (XEXP (x, 1)) > 0
	  && (INTVAL (XEXP (x, 1)) + INTVAL (XEXP (to, 1))
	      < GET_MODE_BITSIZE (GET_MODE (x))))
	{
	  if (!undobuf.storage)
	    undobuf.storage = (char *) oballoc (0);
	  return gen_rtx (GET_CODE (x), GET_MODE (x),
			  XEXP (to, 0),
			  gen_rtx (CONST_INT, VOIDmode,
				   INTVAL (XEXP (x, 1))
				   + INTVAL (XEXP (to, 1))));
	}
      /* (ashift (ashiftrt <foo> <X>) <X>)
	 (or, on some machines, (ashift (ashift <foo> <-X>) <X>) instead)
	 happens if you divide by 2**N and then multiply by 2**N.
	 It can be replaced by one `and' instruction.
	 It does not matter whether the shifts are logical or arithmetic.  */
      if (GET_CODE (XEXP (x, 1)) == CONST_INT
	  && INTVAL (XEXP (x, 1)) > 0
	  && was_replaced[0]
	  && (((GET_CODE (to) == LSHIFTRT || GET_CODE (to) == ASHIFTRT)
	       && GET_CODE (XEXP (to, 1)) == CONST_INT
	       && INTVAL (XEXP (x, 1)) == INTVAL (XEXP (to, 1)))
	      ||
	      ((GET_CODE (to) == LSHIFT || GET_CODE (to) == ASHIFT)
	       && GET_CODE (XEXP (to, 1)) == CONST_INT
	       && INTVAL (XEXP (x, 1)) == - INTVAL (XEXP (to, 1)))))
	{
	  if (!undobuf.storage)
	    undobuf.storage = (char *) oballoc (0);
	  /* The constant in the new `and' is -1 << <X>
	     but clear out all bits that don't belong in our mode.  */
	  return gen_rtx (AND, GET_MODE (x), XEXP (to, 0),
			  gen_rtx (CONST_INT, VOIDmode,
				   (GET_MODE_MASK (GET_MODE (x))
				    & (GET_MODE_MASK (GET_MODE (x))
				       << INTVAL (XEXP (x, 1))))));
	} 

    }

  return x;
}

/* This is the AND case of the function subst.  */

static rtx
simplify_and_const_int (x, to)
     rtx x, to;
{
  register rtx varop = XEXP (x, 0);
  register int constop = INTVAL (XEXP (x, 1));

  /* (and (subreg (and <foo> <constant>) 0) <constant>)
     results from an andsi followed by an andqi,
     which happens frequently when storing bit-fields
     on something whose result comes from an andsi.  */
  if (GET_CODE (varop) == SUBREG
      && XEXP (varop, 0) == to
      && subreg_lowpart_p (varop)
      && GET_CODE (to) == AND
      && GET_CODE (XEXP (to, 1)) == CONST_INT
      /* Verify that the result of the outer `and'
	 is not affected by any bits not defined in the inner `and'.
	 True if the outer mode is narrower, or if the outer constant
	 masks to zero all the bits that the inner mode doesn't have.  */
      && (GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (GET_MODE (to))
	  || (constop & ~ GET_MODE_MASK (GET_MODE (to))) == 0))
    {
      if (!undobuf.storage)
	undobuf.storage = (char *) oballoc (0);
      return gen_rtx (AND, GET_MODE (x),
		      gen_lowpart_for_combine (GET_MODE (x), XEXP (to, 0)),
		      gen_rtx (CONST_INT, VOIDmode,
			       constop
			       /* Remember that the bits outside that mode
				  are not being changed, so the effect
				  is as if they were all 1.  */
			       & INTVAL (XEXP (to, 1))));
    } 
  /* (and:SI (zero_extract:SI ...) <constant>)
     results from an andsi following a byte-fetch on risc machines.
     When the constant includes all bits extracted, eliminate the `and'.  */
  if (GET_CODE (varop) == ZERO_EXTRACT
      && GET_CODE (XEXP (varop, 1)) == CONST_INT
      /* The `and' must not clear any bits that the extract can give.  */
      && (~ constop & ((1 << INTVAL (XEXP (varop, 1))) - 1)) == 0)
    return varop;
  /* (and (zero_extend <foo>) <constant>)
     often results from storing in a bit-field something
     that was calculated as a short.  Replace with a single `and'
     in whose constant all bits not in <foo>'s mode are zero.  */
  if (varop == to
      && GET_CODE (to) == ZERO_EXTEND
      && FAKE_EXTEND_SAFE_P (GET_MODE (x), XEXP (to, 0)))
    {
      if (!undobuf.storage)
	undobuf.storage = (char *) oballoc (0);
      return gen_rtx (AND, GET_MODE (x),
		      /* This is a perverse SUBREG, wider than its base.  */
		      gen_lowpart_for_combine (GET_MODE (x), XEXP (to, 0)),
		      gen_rtx (CONST_INT, VOIDmode,
			       constop & GET_MODE_MASK (GET_MODE (XEXP (to, 0)))));
    }
  /* (and (sign_extend <foo>) <constant>)
     can be replaced with (and (subreg <foo>) <constant>)
     if <constant> is narrower than <foo>'s mode,
     or with (zero_extend <foo>) if <constant> is a mask for that mode.  */
  if (varop == to
      && GET_CODE (to) == SIGN_EXTEND
      && ((unsigned) constop <= GET_MODE_MASK (GET_MODE (XEXP (to, 0))))
      && FAKE_EXTEND_SAFE_P (GET_MODE (x), XEXP (to, 0)))
    {
      if (!undobuf.storage)
	undobuf.storage = (char *) oballoc (0);
      if (constop == GET_MODE_MASK (GET_MODE (XEXP (to, 0))))
	return gen_rtx (ZERO_EXTEND, GET_MODE (x), XEXP (to, 0));
      return gen_rtx (AND, GET_MODE (x),
		      /* This is a perverse SUBREG, wider than its base.  */
		      gen_lowpart_for_combine (GET_MODE (x), XEXP (to, 0)),
		      XEXP (x, 1));
    }
  /* (and (and <foo> <constant>) <constant>)
     comes from two and instructions in a row.  */
  if (varop == to
      && GET_CODE (to) == AND
      && GET_CODE (XEXP (to, 1)) == CONST_INT)
    {
      if (!undobuf.storage)
	undobuf.storage = (char *) oballoc (0);
      return gen_rtx (AND, GET_MODE (x),
		      XEXP (to, 0),
		      gen_rtx (CONST_INT, VOIDmode,
			       constop
			       & INTVAL (XEXP (to, 1))));
    }
  /* (and (ashiftrt (ashift FOO N) N) CONST)
     may be simplified to (and FOO CONST) if CONST masks off the bits
     changed by the two shifts.  */
  if (GET_CODE (varop) == ASHIFTRT
      && GET_CODE (XEXP (varop, 1)) == CONST_INT
      && XEXP (varop, 0) == to
      && GET_CODE (to) == ASHIFT
      && GET_CODE (XEXP (to, 1)) == CONST_INT
      && INTVAL (XEXP (varop, 1)) == INTVAL (XEXP (to, 1))
      && ((unsigned) constop >> INTVAL (XEXP (varop, 1))) == 0)
    {
      if (!undobuf.storage)
	undobuf.storage = (char *) oballoc (0);
      /* If CONST is a mask for the low byte,
	 change this into a zero-extend instruction
	 from just the low byte of FOO.  */
      if (constop == GET_MODE_MASK (QImode))
	{
	  rtx temp = gen_lowpart_for_combine (QImode, XEXP (to, 0));
	  if (GET_CODE (temp) != CLOBBER)
	    return gen_rtx (ZERO_EXTEND, GET_MODE (x), temp);
	}
      return gen_rtx (AND, GET_MODE (x),
		      XEXP (to, 0), XEXP (x, 1));
    }
  /* (and x const) may be converted to (zero_extend (subreg x 0)).  */
  if (constop == GET_MODE_MASK (QImode))
    {
      if (!undobuf.storage)
	undobuf.storage = (char *) oballoc (0);
      return gen_rtx (ZERO_EXTEND, GET_MODE (x),
		      gen_rtx (SUBREG, QImode, varop, 0));
    }
  if (constop == GET_MODE_MASK (HImode))
    {
      if (!undobuf.storage)
	undobuf.storage = (char *) oballoc (0);
      return gen_rtx (ZERO_EXTEND, GET_MODE (x),
		      gen_rtx (SUBREG, HImode, varop, 0));
    }
  /* No simplification applies.  */
  return 0;
}

/* Like gen_lowpart but for use by combine.  In combine it is not possible
   to create any new pseudoregs.  However, it is safe to create
   invalid memory addresses, because combine will try to recognize
   them and all they will do is make the combine attempt fail.

   If for some reason this cannot do its job, an rtx
   (clobber (const_int 0)) is returned.
   An insn containing that will not be recognized.  */

#undef gen_lowpart

static rtx
gen_lowpart_for_combine (mode, x)
     enum machine_mode mode;
     register rtx x;
{
  if (GET_CODE (x) == SUBREG || GET_CODE (x) == REG)
    return gen_lowpart (mode, x);
  if (GET_MODE (x) == mode || x->volatil)
    return gen_rtx (CLOBBER, VOIDmode, const0_rtx);
  if (GET_CODE (x) == MEM)
    {
      register int offset = 0;
#ifdef WORDS_BIG_ENDIAN
      offset = (max (GET_MODE_SIZE (GET_MODE (x)), UNITS_PER_WORD)
		- max (GET_MODE_SIZE (mode), UNITS_PER_WORD));
#endif
#ifdef BYTES_BIG_ENDIAN
      /* Adjust the address so that the address-after-the-data
	 is unchanged.  */
      offset -= (min (UNITS_PER_WORD, GET_MODE_SIZE (mode))
		 - min (UNITS_PER_WORD, GET_MODE_SIZE (GET_MODE (x))));
#endif
      return gen_rtx (MEM, mode, plus_constant (XEXP (x, 0),
						offset));
    }
  else
    return gen_rtx (CLOBBER, VOIDmode, const0_rtx);
}

/* After substitution, if the resulting pattern looks like
   (set (cc0) (and ...)) or (set (cc0) (lshiftrt ...)),
   this function is called to simplify the
   pattern into a bit-field operation if possible.  */

static void
simplify_set_cc0_and (insn)
     rtx insn;
{
  register rtx value = XEXP (PATTERN (insn), 1);
  register rtx op0 = XEXP (value, 0);
  register rtx op1 = XEXP (value, 1);
  int offset = 0;
  rtx var = 0;
  rtx bitnum = 0;
  int temp;
  int unit;
  rtx newpat;

  if (GET_CODE (value) == AND)
    {
      op0 = XEXP (value, 0);
      op1 = XEXP (value, 1);
    }
  else if (GET_CODE (value) == LSHIFTRT)
    {
      /* If there is no AND, but there is a shift that discards
	 all but the sign bit, we can pretend that the shift result
	 is ANDed with 1.  Otherwise we cannot handle just a shift.  */
      if (GET_CODE (XEXP (value, 1)) == CONST_INT
	  && (INTVAL (XEXP (value, 1))
	      == GET_MODE_BITSIZE (GET_MODE (value)) - 1))
	{
	  op0 = value;
	  op1 = const1_rtx;
	}
      else
	return;
    }
  else
    abort ();

  /* Look for a constant power of 2 or a shifted 1
     on either side of the AND.  Set VAR to the other side.
     Set BITNUM to the shift count of the 1 (as an rtx).
     Or, if bit number is constant, set OFFSET to the bit number.  */

  switch (GET_CODE (op0))
    {
    case CONST_INT:
      temp = exact_log2 (INTVAL (op0));
      if (temp < 0)
	return;
      offset = temp;
      var = op1;
      break;

    case ASHIFT:
    case LSHIFT:
      if (XEXP (op0, 0) == const1_rtx)
	{
	  bitnum = XEXP (op0, 1);
	  var = op1;
	}
    }
  if (var == 0)
    switch (GET_CODE (op1))
      {
      case CONST_INT:
	temp = exact_log2 (INTVAL (op1));
	if (temp < 0)
	  return;
	offset = temp;
	var = op0;
	break;

      case ASHIFT:
      case LSHIFT:
	if (XEXP (op1, 0) == const1_rtx)
	  {
	    bitnum = XEXP (op1, 1);
	    var = op0;
	  }
      }

  /* If VAR is 0, we didn't find something recognizable.  */
  if (var == 0)
    return;

  if (!undobuf.storage)
    undobuf.storage = (char *) oballoc (0);

  /* If the bit position is currently exactly 0,
     extract a right-shift from the variable portion.  */
  if (offset == 0
      && (GET_CODE (var) == ASHIFTRT || GET_CODE (var) == LSHIFTRT))
    {
      bitnum = XEXP (var, 1);
      var = XEXP (var, 0);
    }

  if (GET_CODE (var) == SUBREG && SUBREG_WORD (var) == 0)
    var = SUBREG_REG (var);

  /* Note that BITNUM and OFFSET are always little-endian thru here
     even on a big-endian machine.  */

#ifdef BITS_BIG_ENDIAN
  unit = GET_MODE_BITSIZE (GET_MODE (var)) - 1;

  if (bitnum != 0)
    bitnum = gen_rtx (MINUS, SImode,
		      gen_rtx (CONST_INT, VOIDmode, unit), bitnum);
  else
    offset = unit - offset;
#endif

  if (bitnum == 0)
    bitnum = gen_rtx (CONST_INT, VOIDmode, offset);

  newpat = gen_rtx (SET, VOIDmode, cc0_rtx,
		    gen_rtx (ZERO_EXTRACT, VOIDmode, var, const1_rtx, bitnum));
  if (recog (newpat, insn) >= 0)
    {
      if (undobuf.num_undo < MAX_UNDO)
	{
	  undobuf.undo[undobuf.num_undo].where = &XEXP (PATTERN (insn), 1);
	  undobuf.undo[undobuf.num_undo].old_contents = value;
	  XEXP (PATTERN (insn), 1) = XEXP (newpat, 1);
	}
      undobuf.num_undo++;
    }
}

/* Update the records of when each REG was most recently set or killed
   for the things done by INSN.  This is the last thing done in processing
   INSN in the combiner loop.

   We update reg_last_set, reg_last_death, and also the similar information
   mem_last_set (which insn most recently modified memory)
   and last_call_cuid (which insn was the most recent subroutine call).  */

static void
record_dead_and_set_regs (insn)
     rtx insn;
{
  register rtx link;
  for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
    {
      if (REG_NOTE_KIND (link) == REG_DEAD)
	reg_last_death[REGNO (XEXP (link, 0))] = insn;
      else if (REG_NOTE_KIND (link) == REG_INC)
	reg_last_set[REGNO (XEXP (link, 0))] = insn;
    }

  if (GET_CODE (insn) == CALL_INSN)
    last_call_cuid = mem_last_set = INSN_CUID (insn);

  if (GET_CODE (PATTERN (insn)) == PARALLEL)
    {
      register int i;
      for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
	{
	  register rtx elt = XVECEXP (PATTERN (insn), 0, i);
	  register enum rtx_code code = GET_CODE (elt);
	  if (code == SET || code == CLOBBER)
	    {
	      if (GET_CODE (XEXP (elt, 0)) == REG)
		reg_last_set[REGNO (XEXP (elt, 0))] = insn;
	      if (GET_CODE (XEXP (elt, 0)) == SUBREG
		  && GET_CODE (SUBREG_REG (XEXP (elt, 0))) == REG)
		reg_last_set[REGNO (SUBREG_REG (XEXP (elt, 0)))] = insn;
	      else if (GET_CODE (XEXP (elt, 0)) == MEM)
		mem_last_set = INSN_CUID (insn);
	    }
	}
    }
  else if (GET_CODE (PATTERN (insn)) == SET
	   || GET_CODE (PATTERN (insn)) == CLOBBER)
    {
      register rtx x = XEXP (PATTERN (insn), 0);
      if (GET_CODE (x) == REG)
	reg_last_set[REGNO (x)] = insn;
      if (GET_CODE (x) == SUBREG
	  && GET_CODE (SUBREG_REG (x)) == REG)
	reg_last_set[REGNO (SUBREG_REG (x))] = insn;
      else if (GET_CODE (x) == MEM)
	mem_last_set = INSN_CUID (insn);
    }
}

/* Return nonzero if expression X refers to a REG or to memory
   that is set in an instruction more recent than FROM_CUID.  */

static int
use_crosses_set_p (x, from_cuid)
     register rtx x;
     int from_cuid;
{
  register char *fmt;
  register int i;
  register enum rtx_code code = GET_CODE (x);

  if (code == REG)
    {
      register int regno = REGNO (x);
      return (reg_last_set[regno]
	      && INSN_CUID (reg_last_set[regno]) > from_cuid);
    }

  if (code == MEM && mem_last_set > from_cuid)
    return 1;

  fmt = GET_RTX_FORMAT (code);

  for (i = GET_RTX_LENGTH (code); i >= 0; i--)
    {
      if (fmt[i] == 'E')
	{
	  register int j;
	  for (j = XVECLEN (x, i) - 1; j >= 0; j--)
	    if (use_crosses_set_p (XVECEXP (x, i, j), from_cuid))
	      return 1;
	}
      else if (fmt[i] == 'e'
	       && use_crosses_set_p (XEXP (x, i), from_cuid))
	return 1;
    }
  return 0;
}

/* Return nonzero if reg REGNO is marked as dying in INSN.  */

int
regno_dead_p (regno, insn)
     int regno;
     rtx insn;
{
  register rtx link;

  for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
    if ((REG_NOTE_KIND (link) == REG_DEAD
	 || REG_NOTE_KIND (link) == REG_INC)
	&& REGNO (XEXP (link, 0)) == regno)
      return 1;

  return 0;
}

/* Remove register number REGNO from the dead registers list of INSN.  */

static void
remove_death (regno, insn)
     int regno;
     rtx insn;
{
  register rtx link, next;
  while ((link = REG_NOTES (insn))
	 && REG_NOTE_KIND (link) == REG_DEAD
	 && REGNO (XEXP (link, 0)) == regno)
    REG_NOTES (insn) = XEXP (link, 1);

  if (link)
    while (next = XEXP (link, 1))
      {
	if (REG_NOTE_KIND (next) == REG_DEAD
	    && REGNO (XEXP (next, 0)) == regno)
	  XEXP (link, 1) = XEXP (next, 1);
	else
	  link = next;
      }
}

/* Return nonzero if J is the first insn following I,
   not counting labels, line numbers, etc.
   We assume that J follows I.  */

static int
adjacent_insns_p (i, j)
     rtx i, j;
{
  register rtx insn;
  for (insn = NEXT_INSN (i); insn != j; insn = NEXT_INSN (insn))
    if (GET_CODE (insn) == INSN
	|| GET_CODE (insn) == CALL_INSN
	|| GET_CODE (insn) == JUMP_INSN)
      return 0;
  return 1;
}

/* Concatenate the list of logical links of OINSN
   into INSN's list of logical links.
   Modifies OINSN destructively.

   If ALL_LINKS is nonzero, move all the links that OINSN has.
   Otherwise, move only those that point to insns that set regs
   that die in the insn OINSN.
   Other links are clobbered so that they are no longer effective.  */

static void
add_links (insn, oinsn, all_links)
     rtx insn, oinsn;
     int all_links;
{
  register rtx links = LOG_LINKS (oinsn);
  if (! all_links)
    {
      rtx tail;
      for (tail = links; tail; tail = XEXP (tail, 1))
	{
	  rtx target = XEXP (tail, 0);
	  if (GET_CODE (target) != INSN
	      || GET_CODE (PATTERN (target)) != SET
	      || GET_CODE (SET_DEST (PATTERN (target))) != REG
	      || ! dead_or_set_p (oinsn, SET_DEST (PATTERN (target))))
	    /* OINSN is going to become a NOTE 
	       so a link pointing there will have no effect.  */
	    XEXP (tail, 0) = oinsn;
	}
    }
  if (LOG_LINKS (insn) == 0)
    LOG_LINKS (insn) = links;
  else
    {
      register rtx next, prev = LOG_LINKS (insn);
      while (next = XEXP (prev, 1))
	prev = next;
      XEXP (prev, 1) = links;
    }
}

/* Concatenate the any elements of the list of reg-notes INCS
   which are of type REG_INC
   into INSN's list of reg-notes.  */

static void
add_incs (insn, incs)
     rtx insn, incs;
{
  register rtx tail;

  for (tail = incs; tail; tail = XEXP (tail, 1))
    if (REG_NOTE_KIND (tail) == REG_INC)
      REG_NOTES (insn)
	= gen_rtx (EXPR_LIST, REG_INC, XEXP (tail, 0), REG_NOTES (insn));
}

/* For each register (hardware or pseudo) used within expression X,
   if its death is in an instruction with cuid
   between FROM_CUID (inclusive) and TO_INSN (exclusive),
   mark it as dead in TO_INSN instead.

   This is done when X is being merged by combination into TO_INSN.  */

static void
move_deaths (x, from_cuid, to_insn)
     rtx x;
     int from_cuid;
     rtx to_insn;
{
  register char *fmt;
  register int len, i;
  register enum rtx_code code = GET_CODE (x);

  if (code == REG)
    {
      register rtx where_dead = reg_last_death[REGNO (x)];

      if (where_dead && INSN_CUID (where_dead) >= from_cuid
	  && INSN_CUID (where_dead) < INSN_CUID (to_insn))
	{
	  remove_death (REGNO (x), reg_last_death[REGNO (x)]);
	  if (! dead_or_set_p (to_insn, x))
	    REG_NOTES (to_insn)
	      = gen_rtx (EXPR_LIST, REG_DEAD, x, REG_NOTES (to_insn));
	}
      return;
    }

  len = GET_RTX_LENGTH (code);
  fmt = GET_RTX_FORMAT (code);

  for (i = 0; i < len; i++)
    {
      if (fmt[i] == 'E')
	{
	  register int j;
	  for (j = XVECLEN (x, i) - 1; j >= 0; j--)
	    move_deaths (XVECEXP (x, i, j), from_cuid, to_insn);
	}
      else if (fmt[i] == 'e')
	move_deaths (XEXP (x, i), from_cuid, to_insn);
    }
}

void
dump_combine_stats (file)
     char *file;
{
  fprintf
    (file,
     ";; Combiner statistics: %d attempts, %d substitutions (%d requiring new space),\n;; %d successes.\n\n"
     , combine_attempts, combine_merges, combine_extras, combine_successes);
}

void
dump_combine_total_stats (file)
     char *file;
{
  fprintf
    (file,
     "\n;; Combiner totals: %d attempts, %d substitutions (%d requiring new space),\n;; %d successes.\n",
     total_attempts, total_merges, total_extras, total_successes);
}