Initial revision

From-SVN: r360

2 files changed, 7470 insertions, 0 deletions

diff --git a/gcc/config/i386/sun386.h b/gcc/config/i386/sun386.h
new file mode 100644
index 0000000..1240081
--- /dev/null
+++ b/gcc/config/i386/sun386.h
@@ -0,0 +1,138 @@
+/* Definitions for Sun assembler syntax for the Intel 80386.
+   Copyright (C) 1988 Free Software Foundation, Inc.
+
+This file is part of GNU CC.
+
+GNU CC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, 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 of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU CC; see the file COPYING.  If not, write to
+the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
+
+
+/* Include common aspects of all 386 Unix assemblers.  */
+#include "unx386.h"
+
+#define TARGET_VERSION fprintf (stderr, " (80386, Sun syntax)");
+
+/* Define the syntax of instructions and addresses.  */
+
+/* Prefix for internally generated assembler labels.  */
+#define LPREFIX ".L"
+
+/* Define the syntax of pseudo-ops, labels and comments.  */
+
+/* Assembler pseudos to introduce constants of various size.  */
+
+#define ASM_BYTE_OP "\t.byte"
+#define ASM_SHORT "\t.value"
+#define ASM_LONG "\t.long"
+#define ASM_DOUBLE "\t.double"
+
+/* How to output an ASCII string constant.  */
+
+#define ASM_OUTPUT_ASCII(FILE, p, size) \
+{ int i = 0; 							\
+  while (i < (size))						\
+    { if (i%10 == 0) { if (i!=0) fprintf ((FILE), "\n");		\
+		       fprintf ((FILE), "%s ", ASM_BYTE_OP); }	\
+      else fprintf ((FILE), ",");					\
+      fprintf ((FILE), "0x%x", ((p)[i++] & 0377)) ;}		\
+      fprintf ((FILE), "\n"); }
+
+/* Output at beginning of assembler file.  */
+/* The .file command should always begin the output.  */
+
+#undef ASM_FILE_START
+#define ASM_FILE_START(FILE) \
+  do {							\
+    extern char *version_string, *language_string;	\
+    {							\
+      int len = strlen (dump_base_name);		\
+      char *na = dump_base_name + len;			\
+      char shorter[15];					\
+      /* NA gets DUMP_BASE_NAME sans directory names.  */\
+      while (na > dump_base_name)			\
+	{						\
+	  if (na[-1] == '/')				\
+	    break;					\
+	  na--;						\
+	}						\
+      strncpy (shorter, na, 14);			\
+      shorter[14] = 0;					\
+      fprintf (FILE, "\t.file\t\"%s\"\n", shorter);	\
+    }							\
+    fprintf (FILE, "\t.version\t\"%s %s\"\n",		\
+	     language_string, version_string);		\
+    if (optimize) ASM_FILE_START_1 (FILE);		\
+  } while (0)
+
+#define ASM_FILE_START_1(FILE) fprintf (FILE, "\t.optim\n")
+
+/* This is how to output an assembler line
+   that says to advance the location counter
+   to a multiple of 2**LOG bytes.  */
+
+#define ASM_OUTPUT_ALIGN(FILE,LOG)	\
+    if ((LOG)!=0) fprintf ((FILE), "\t.align %d\n", 1<<(LOG))
+
+/* This is how to output an assembler line
+   that says to advance the location counter by SIZE bytes.  */
+
+#define ASM_OUTPUT_SKIP(FILE,SIZE)  \
+  fprintf ((FILE), "\t.set\t.,.+%u\n", (SIZE))
+
+/* Output before read-only data.  */
+
+#undef TEXT_SECTION_ASM_OP
+#define TEXT_SECTION_ASM_OP "\t.text"
+
+/* Output before writable data.  */
+
+#undef DATA_SECTION_ASSM_OP
+#define DATA_SECTION_ASM_OP "\t.data"
+
+/* Define the syntax of labels and symbol definitions/declarations.  */
+
+/* This says how to output an assembler line
+   to define a global common symbol.  */
+
+#define ASM_OUTPUT_COMMON(FILE, NAME, SIZE, ROUNDED)  \
+( fputs (".comm ", (FILE)),			\
+  assemble_name ((FILE), (NAME)),		\
+  fprintf ((FILE), ",%u\n", (ROUNDED)))
+
+/* This says how to output an assembler line
+   to define a local common symbol.  */
+
+#define ASM_OUTPUT_LOCAL(FILE, NAME, SIZE, ROUNDED)  \
+( fputs (".lcomm ", (FILE)),			\
+  assemble_name ((FILE), (NAME)),		\
+  fprintf ((FILE), ",%u\n", (ROUNDED)))
+
+/* This is how to store into the string BUF
+   the symbol_ref name of an internal numbered label where
+   PREFIX is the class of label and NUM is the number within the class.
+   This is suitable for output with `assemble_name'.  */
+
+#define ASM_GENERATE_INTERNAL_LABEL(BUF,PREFIX,NUMBER)	\
+  sprintf ((BUF), ".%s%d", (PREFIX), (NUMBER))
+
+/* This is how to output a reference to a user-level label named NAME.  */
+
+#define ASM_OUTPUT_LABELREF(FILE,NAME)	\
+  fprintf (FILE, "%s", NAME)
+
+/* This is how to output an internal numbered label where
+   PREFIX is the class of label and NUM is the number within the class.  */
+
+#define ASM_OUTPUT_INTERNAL_LABEL(FILE,PREFIX,NUM)	\
+  fprintf (FILE, ".%s%d:\n", PREFIX, NUM)
diff --git a/gcc/cse.c b/gcc/cse.c
new file mode 100644
index 0000000..91ff217
--- /dev/null
+++ b/gcc/cse.c
@@ -0,0 +1,7332 @@
+/* Common subexpression elimination for GNU compiler.
+   Copyright (C) 1987, 1988, 1989, 1992 Free Software Foundation, Inc.
+
+This file is part of GNU CC.
+
+GNU CC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, 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 of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU CC; see the file COPYING.  If not, write to
+the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
+
+
+#include "config.h"
+#include "rtl.h"
+#include "regs.h"
+#include "hard-reg-set.h"
+#include "flags.h"
+#include "real.h"
+#include "insn-config.h"
+#include "recog.h"
+
+#include <stdio.h>
+#include <setjmp.h>
+
+/* The basic idea of common subexpression elimination is to go
+   through the code, keeping a record of expressions that would
+   have the same value at the current scan point, and replacing
+   expressions encountered with the cheapest equivalent expression.
+
+   It is too complicated to keep track of the different possibilities
+   when control paths merge; so, at each label, we forget all that is
+   known and start fresh.  This can be described as processing each
+   basic block separately.  Note, however, that these are not quite
+   the same as the basic blocks found by a later pass and used for
+   data flow analysis and register packing.  We do not need to start fresh
+   after a conditional jump instruction if there is no label there.
+
+   We use two data structures to record the equivalent expressions:
+   a hash table for most expressions, and several vectors together
+   with "quantity numbers" to record equivalent (pseudo) registers.
+
+   The use of the special data structure for registers is desirable
+   because it is faster.  It is possible because registers references
+   contain a fairly small number, the register number, taken from
+   a contiguously allocated series, and two register references are
+   identical if they have the same number.  General expressions
+   do not have any such thing, so the only way to retrieve the
+   information recorded on an expression other than a register
+   is to keep it in a hash table.
+
+Registers and "quantity numbers":
+   
+   At the start of each basic block, all of the (hardware and pseudo)
+   registers used in the function are given distinct quantity
+   numbers to indicate their contents.  During scan, when the code
+   copies one register into another, we copy the quantity number.
+   When a register is loaded in any other way, we allocate a new
+   quantity number to describe the value generated by this operation.
+   `reg_qty' records what quantity a register is currently thought
+   of as containing.
+
+   All real quantity numbers are greater than or equal to `max_reg'.
+   If register N has not been assigned a quantity, reg_qty[N] will equal N.
+
+   Quantity numbers below `max_reg' do not exist and none of the `qty_...'
+   variables should be referenced with an index below `max_reg'.
+
+   We also maintain a bidirectional chain of registers for each
+   quantity number.  `qty_first_reg', `qty_last_reg',
+   `reg_next_eqv' and `reg_prev_eqv' hold these chains.
+
+   The first register in a chain is the one whose lifespan is least local.
+   Among equals, it is the one that was seen first.
+   We replace any equivalent register with that one.
+
+   If two registers have the same quantity number, it must be true that
+   REG expressions with `qty_mode' must be in the hash table for both
+   registers and must be in the same class.
+
+   The converse is not true.  Since hard registers may be referenced in
+   any mode, two REG expressions might be equivalent in the hash table
+   but not have the same quantity number if the quantity number of one
+   of the registers is not the same mode as those expressions.
+   
+Constants and quantity numbers
+
+   When a quantity has a known constant value, that value is stored
+   in the appropriate element of qty_const.  This is in addition to
+   putting the constant in the hash table as is usual for non-regs.
+
+   Whether a reg or a constant is prefered is determined by the configuration
+   macro CONST_COSTS and will often depend on the constant value.  In any
+   event, expressions containing constants can be simplified, by fold_rtx.
+
+   When a quantity has a known nearly constant value (such as an address
+   of a stack slot), that value is stored in the appropriate element
+   of qty_const.
+
+   Integer constants don't have a machine mode.  However, cse
+   determines the intended machine mode from the destination
+   of the instruction that moves the constant.  The machine mode
+   is recorded in the hash table along with the actual RTL
+   constant expression so that different modes are kept separate.
+
+Other expressions:
+
+   To record known equivalences among expressions in general
+   we use a hash table called `table'.  It has a fixed number of buckets
+   that contain chains of `struct table_elt' elements for expressions.
+   These chains connect the elements whose expressions have the same
+   hash codes.
+
+   Other chains through the same elements connect the elements which
+   currently have equivalent values.
+
+   Register references in an expression are canonicalized before hashing
+   the expression.  This is done using `reg_qty' and `qty_first_reg'.
+   The hash code of a register reference is computed using the quantity
+   number, not the register number.
+
+   When the value of an expression changes, it is necessary to remove from the
+   hash table not just that expression but all expressions whose values
+   could be different as a result.
+
+     1. If the value changing is in memory, except in special cases
+     ANYTHING referring to memory could be changed.  That is because
+     nobody knows where a pointer does not point.
+     The function `invalidate_memory' removes what is necessary.
+
+     The special cases are when the address is constant or is
+     a constant plus a fixed register such as the frame pointer
+     or a static chain pointer.  When such addresses are stored in,
+     we can tell exactly which other such addresses must be invalidated
+     due to overlap.  `invalidate' does this.
+     All expressions that refer to non-constant
+     memory addresses are also invalidated.  `invalidate_memory' does this.
+
+     2. If the value changing is a register, all expressions
+     containing references to that register, and only those,
+     must be removed.
+
+   Because searching the entire hash table for expressions that contain
+   a register is very slow, we try to figure out when it isn't necessary.
+   Precisely, this is necessary only when expressions have been
+   entered in the hash table using this register, and then the value has
+   changed, and then another expression wants to be added to refer to
+   the register's new value.  This sequence of circumstances is rare
+   within any one basic block.
+
+   The vectors `reg_tick' and `reg_in_table' are used to detect this case.
+   reg_tick[i] is incremented whenever a value is stored in register i.
+   reg_in_table[i] holds -1 if no references to register i have been
+   entered in the table; otherwise, it contains the value reg_tick[i] had
+   when the references were entered.  If we want to enter a reference
+   and reg_in_table[i] != reg_tick[i], we must scan and remove old references.
+   Until we want to enter a new entry, the mere fact that the two vectors
+   don't match makes the entries be ignored if anyone tries to match them.
+
+   Registers themselves are entered in the hash table as well as in
+   the equivalent-register chains.  However, the vectors `reg_tick'
+   and `reg_in_table' do not apply to expressions which are simple
+   register references.  These expressions are removed from the table
+   immediately when they become invalid, and this can be done even if
+   we do not immediately search for all the expressions that refer to
+   the register.
+
+   A CLOBBER rtx in an instruction invalidates its operand for further
+   reuse.  A CLOBBER or SET rtx whose operand is a MEM:BLK
+   invalidates everything that resides in memory.
+
+Related expressions:
+
+   Constant expressions that differ only by an additive integer
+   are called related.  When a constant expression is put in
+   the table, the related expression with no constant term
+   is also entered.  These are made to point at each other
+   so that it is possible to find out if there exists any
+   register equivalent to an expression related to a given expression.  */
+   
+/* One plus largest register number used in this function.  */
+
+static int max_reg;
+
+/* Length of vectors indexed by quantity number.
+   We know in advance we will not need a quantity number this big.  */
+
+static int max_qty;
+
+/* Next quantity number to be allocated.
+   This is 1 + the largest number needed so far.  */
+
+static int next_qty;
+
+/* Indexed by quantity number, gives the first (or last) (pseudo) register 
+   in the chain of registers that currently contain this quantity.  */
+
+static int *qty_first_reg;
+static int *qty_last_reg;
+
+/* Index by quantity number, gives the mode of the quantity.  */
+
+static enum machine_mode *qty_mode;
+
+/* Indexed by quantity number, gives the rtx of the constant value of the
+   quantity, or zero if it does not have a known value.
+   A sum of the frame pointer (or arg pointer) plus a constant
+   can also be entered here.  */
+
+static rtx *qty_const;
+
+/* Indexed by qty number, gives the insn that stored the constant value
+   recorded in `qty_const'.  */
+
+static rtx *qty_const_insn;
+
+/* The next three variables are used to track when a comparison between a
+   quantity and some constant or register has been passed.  In that case, we
+   know the results of the comparison in case we see it again.  These variables
+   record a comparison that is known to be true.  */
+
+/* Indexed by qty number, gives the rtx code of a comparison with a known
+   result involving this quantity.  If none, it is UNKNOWN.  */
+static enum rtx_code *qty_comparison_code;
+
+/* Indexed by qty number, gives the constant being compared against in a
+   comparison of known result.  If no such comparison, it is undefined.
+   If the comparison is not with a constant, it is zero.  */
+
+static rtx *qty_comparison_const;
+
+/* Indexed by qty number, gives the quantity being compared against in a
+   comparison of known result.  If no such comparison, if it undefined.
+   If the comparison is not with a register, it is -1.  */
+
+static int *qty_comparison_qty;
+
+#ifdef HAVE_cc0
+/* For machines that have a CC0, we do not record its value in the hash
+   table since its use is guaranteed to be the insn immediately following
+   its definition and any other insn is presumed to invalidate it.
+
+   Instead, we store below the value last assigned to CC0.  If it should
+   happen to be a constant, it is stored in preference to the actual
+   assigned value.  In case it is a constant, we store the mode in which
+   the constant should be interpreted.  */
+
+static rtx prev_insn_cc0;
+static enum machine_mode prev_insn_cc0_mode;
+#endif
+
+/* Previous actual insn.  0 if at first insn of basic block.  */
+
+static rtx prev_insn;
+
+/* Insn being scanned.  */
+
+static rtx this_insn;
+
+/* Index by (pseudo) register number, gives the quantity number
+   of the register's current contents.  */
+
+static int *reg_qty;
+
+/* Index by (pseudo) register number, gives the number of the next (or
+   previous) (pseudo) register in the chain of registers sharing the same
+   value.
+
+   Or -1 if this register is at the end of the chain.
+
+   If reg_qty[N] == N, reg_next_eqv[N] is undefined.  */
+
+static int *reg_next_eqv;
+static int *reg_prev_eqv;
+
+/* Index by (pseudo) register number, gives the number of times
+   that register has been altered in the current basic block.  */
+
+static int *reg_tick;
+
+/* Index by (pseudo) register number, gives the reg_tick value at which
+   rtx's containing this register are valid in the hash table.
+   If this does not equal the current reg_tick value, such expressions
+   existing in the hash table are invalid.
+   If this is -1, no expressions containing this register have been
+   entered in the table.  */
+
+static int *reg_in_table;
+
+/* A HARD_REG_SET containing all the hard registers for which there is 
+   currently a REG expression in the hash table.  Note the difference
+   from the above variables, which indicate if the REG is mentioned in some
+   expression in the table.  */
+
+static HARD_REG_SET hard_regs_in_table;
+
+/* A HARD_REG_SET containing all the hard registers that are invalidated
+   by a CALL_INSN.  */
+
+static HARD_REG_SET regs_invalidated_by_call;
+
+/* Two vectors of ints:
+   one containing max_reg -1's; the other max_reg + 500 (an approximation
+   for max_qty) elements where element i contains i.
+   These are used to initialize various other vectors fast.  */
+
+static int *all_minus_one;
+static int *consec_ints;
+
+/* CUID of insn that starts the basic block currently being cse-processed.  */
+
+static int cse_basic_block_start;
+
+/* CUID of insn that ends the basic block currently being cse-processed.  */
+
+static int cse_basic_block_end;
+
+/* Vector mapping INSN_UIDs to cuids.
+   The cuids are like uids but increase monononically always.
+   We use them to see whether a reg is used outside a given basic block.  */
+
+static short *uid_cuid;
+
+/* Get the cuid of an insn.  */
+
+#define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
+
+/* Nonzero if cse has altered conditional jump insns
+   in such a way that jump optimization should be redone.  */
+
+static int cse_jumps_altered;
+
+/* canon_hash stores 1 in do_not_record
+   if it notices a reference to CC0, PC, or some other volatile
+   subexpression.  */
+
+static int do_not_record;
+
+/* canon_hash stores 1 in hash_arg_in_memory
+   if it notices a reference to memory within the expression being hashed.  */
+
+static int hash_arg_in_memory;
+
+/* canon_hash stores 1 in hash_arg_in_struct
+   if it notices a reference to memory that's part of a structure.  */
+
+static int hash_arg_in_struct;
+
+/* The hash table contains buckets which are chains of `struct table_elt's,
+   each recording one expression's information.
+   That expression is in the `exp' field.
+
+   Those elements with the same hash code are chained in both directions
+   through the `next_same_hash' and `prev_same_hash' fields.
+
+   Each set of expressions with equivalent values
+   are on a two-way chain through the `next_same_value'
+   and `prev_same_value' fields, and all point with
+   the `first_same_value' field at the first element in
+   that chain.  The chain is in order of increasing cost.
+   Each element's cost value is in its `cost' field.
+
+   The `in_memory' field is nonzero for elements that
+   involve any reference to memory.  These elements are removed
+   whenever a write is done to an unidentified location in memory.
+   To be safe, we assume that a memory address is unidentified unless
+   the address is either a symbol constant or a constant plus
+   the frame pointer or argument pointer.
+
+   The `in_struct' field is nonzero for elements that
+   involve any reference to memory inside a structure or array.
+
+   The `related_value' field is used to connect related expressions
+   (that differ by adding an integer).
+   The related expressions are chained in a circular fashion.
+   `related_value' is zero for expressions for which this
+   chain is not useful.
+
+   The `cost' field stores the cost of this element's expression.
+
+   The `is_const' flag is set if the element is a constant (including
+   a fixed address).
+
+   The `flag' field is used as a temporary during some search routines.
+
+   The `mode' field is usually the same as GET_MODE (`exp'), but
+   if `exp' is a CONST_INT and has no machine mode then the `mode'
+   field is the mode it was being used as.  Each constant is
+   recorded separately for each mode it is used with.  */
+
+
+struct table_elt
+{
+  rtx exp;
+  struct table_elt *next_same_hash;
+  struct table_elt *prev_same_hash;
+  struct table_elt *next_same_value;
+  struct table_elt *prev_same_value;
+  struct table_elt *first_same_value;
+  struct table_elt *related_value;
+  int cost;
+  enum machine_mode mode;
+  char in_memory;
+  char in_struct;
+  char is_const;
+  char flag;
+};
+
+#define HASHBITS 16
+
+/* We don't want a lot of buckets, because we rarely have very many
+   things stored in the hash table, and a lot of buckets slows
+   down a lot of loops that happen frequently.  */
+#define NBUCKETS 31
+
+/* Compute hash code of X in mode M.  Special-case case where X is a pseudo
+   register (hard registers may require `do_not_record' to be set).  */
+
+#define HASH(X, M)	\
+ (GET_CODE (X) == REG && REGNO (X) >= FIRST_PSEUDO_REGISTER	\
+  ? ((((int) REG << 7) + reg_qty[REGNO (X)]) % NBUCKETS)	\
+  : canon_hash (X, M) % NBUCKETS)
+
+/* Determine whether register number N is considered a fixed register for CSE.
+   It is desirable to replace other regs with fixed regs, to reduce need for
+   non-fixed hard regs.
+   A reg wins if it is either the frame pointer or designated as fixed,
+   but not if it is an overlapping register.  */
+#ifdef OVERLAPPING_REGNO_P
+#define FIXED_REGNO_P(N)  \
+  (((N) == FRAME_POINTER_REGNUM || fixed_regs[N])	\
+   && ! OVERLAPPING_REGNO_P ((N)))
+#else
+#define FIXED_REGNO_P(N)  \
+  ((N) == FRAME_POINTER_REGNUM || fixed_regs[N])
+#endif
+
+/* Compute cost of X, as stored in the `cost' field of a table_elt.  Fixed
+   hard registers are the cheapest with a cost of 0.  Next come pseudos
+   with a cost of one and other hard registers with a cost of 2.  Aside
+   from these special cases, call `rtx_cost'.  */
+
+#define COST(X)						\
+  (GET_CODE (X) == REG					\
+   ? (REGNO (X) >= FIRST_PSEUDO_REGISTER ? 1		\
+      : (FIXED_REGNO_P (REGNO (X))			\
+	 && REGNO_REG_CLASS (REGNO (X)) != NO_REGS) ? 0	\
+      : 2)						\
+   : rtx_cost (X) * 2)					\
+
+/* Determine if the quantity number for register X represents a valid index
+   into the `qty_...' variables.  */
+
+#define REGNO_QTY_VALID_P(N) (reg_qty[N] != (N))
+
+static struct table_elt *table[NBUCKETS];
+
+/* Chain of `struct table_elt's made so far for this function
+   but currently removed from the table.  */
+
+static struct table_elt *free_element_chain;
+
+/* Number of `struct table_elt' structures made so far for this function.  */
+
+static int n_elements_made;
+
+/* Maximum value `n_elements_made' has had so far in this compilation
+   for functions previously processed.  */
+
+static int max_elements_made;
+
+/* Surviving equivalence class when two equivalence classes are merged 
+   by recording the effects of a jump in the last insn.  Zero if the
+   last insn was not a conditional jump.  */
+
+static struct table_elt *last_jump_equiv_class;
+
+/* Set to the cost of a constant pool reference if one was found for a
+   symbolic constant.  If this was found, it means we should try to
+   convert constants into constant pool entries if they don't fit in
+   the insn.  */
+
+static int constant_pool_entries_cost;
+
+/* Bits describing what kind of values in memory must be invalidated
+   for a particular instruction.  If all three bits are zero,
+   no memory refs need to be invalidated.  Each bit is more powerful
+   than the preceding ones, and if a bit is set then the preceding
+   bits are also set.
+
+   Here is how the bits are set:
+   Pushing onto the stack invalidates only the stack pointer,
+   writing at a fixed address invalidates only variable addresses,
+   writing in a structure element at variable address
+     invalidates all but scalar variables,
+   and writing in anything else at variable address invalidates everything.  */
+
+struct write_data
+{
+  int sp : 1;			/* Invalidate stack pointer. */
+  int var : 1;			/* Invalidate variable addresses.  */
+  int nonscalar : 1;		/* Invalidate all but scalar variables.  */
+  int all : 1;			/* Invalidate all memory refs.  */
+};
+
+/* Nonzero if X has the form (PLUS frame-pointer integer).  We check for
+   virtual regs here because the simplify_*_operation routines are called
+   by integrate.c, which is called before virtual register instantiation.  */
+
+#define FIXED_BASE_PLUS_P(X)					\
+  ((X) == frame_pointer_rtx || (X) == arg_pointer_rtx		\
+   || (X) == virtual_stack_vars_rtx				\
+   || (X) == virtual_incoming_args_rtx				\
+   || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
+       && (XEXP (X, 0) == frame_pointer_rtx			\
+	   || XEXP (X, 0) == arg_pointer_rtx			\
+	   || XEXP (X, 0) == virtual_stack_vars_rtx		\
+	   || XEXP (X, 0) == virtual_incoming_args_rtx)))
+
+/* Similar, but also allows reference to the stack pointer.  */
+
+#define NONZERO_BASE_PLUS_P(X)					\
+  (FIXED_BASE_PLUS_P (X)					\
+   || (X) == stack_pointer_rtx					\
+   || (X) == virtual_stack_dynamic_rtx				\
+   || (X) == virtual_outgoing_args_rtx				\
+   || (GET_CODE (X) == PLUS && GET_CODE (XEXP (X, 1)) == CONST_INT \
+       && (XEXP (X, 0) == stack_pointer_rtx			\
+	   || XEXP (X, 0) == virtual_stack_dynamic_rtx		\
+	   || XEXP (X, 0) == virtual_outgoing_args_rtx)))
+
+static struct table_elt *lookup ();
+static void free_element ();
+
+static int insert_regs ();
+static void rehash_using_reg ();
+static void remove_invalid_refs ();
+static int exp_equiv_p ();
+int refers_to_p ();
+int refers_to_mem_p ();
+static void invalidate_from_clobbers ();
+static int safe_hash ();
+static int canon_hash ();
+static rtx fold_rtx ();
+static rtx equiv_constant ();
+static void record_jump_cond ();
+static void note_mem_written ();
+static int cse_rtx_addr_varies_p ();
+static enum rtx_code find_comparison_args ();
+static void cse_insn ();
+static void cse_set_around_loop ();
+
+/* Return an estimate of the cost of computing rtx X.
+   One use is in cse, to decide which expression to keep in the hash table.
+   Another is in rtl generation, to pick the cheapest way to multiply.
+   Other uses like the latter are expected in the future.  */
+
+/* Return the right cost to give to an operation
+   to make the cost of the corresponding register-to-register instruction
+   N times that of a fast register-to-register instruction.  */
+
+#define COSTS_N_INSNS(N) ((N) * 4 - 2)
+
+int
+rtx_cost (x)
+     rtx x;
+{
+  register int i, j;
+  register enum rtx_code code;
+  register char *fmt;
+  register int total;
+
+  if (x == 0)
+    return 0;
+
+  /* Compute the default costs of certain things.
+     Note that RTX_COSTS can override the defaults.  */
+
+  code = GET_CODE (x);
+  switch (code)
+    {
+    case MULT:
+      /* Count multiplication by 2**n as a shift,
+	 because if we are considering it, we would output it as a shift.  */
+      if (GET_CODE (XEXP (x, 1)) == CONST_INT
+	  && exact_log2 (INTVAL (XEXP (x, 1))) >= 0)
+	total = 2;
+      else
+	total = COSTS_N_INSNS (5);
+      break;
+    case DIV:
+    case UDIV:
+    case MOD:
+    case UMOD:
+      total = COSTS_N_INSNS (7);
+      break;
+    case USE:
+      /* Used in loop.c and combine.c as a marker.  */
+      total = 0;
+      break;
+    default:
+      total = 2;
+    }
+
+  switch (code)
+    {
+    case REG:
+      return 1;
+    case SUBREG:
+      return 2;
+#ifdef RTX_COSTS
+      RTX_COSTS (x, code);
+#endif 
+      CONST_COSTS (x, code);
+    }
+
+  /* Sum the costs of the sub-rtx's, plus cost of this operation,
+     which is already in total.  */
+
+  fmt = GET_RTX_FORMAT (code);
+  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+    if (fmt[i] == 'e')
+      total += rtx_cost (XEXP (x, i));
+    else if (fmt[i] == 'E')
+      for (j = 0; j < XVECLEN (x, i); j++)
+	total += rtx_cost (XVECEXP (x, i, j));
+
+  return total;
+}
+
+/* Clear the hash table and initialize each register with its own quantity,
+   for a new basic block.  */
+
+static void
+new_basic_block ()
+{
+  register int i;
+
+  next_qty = max_reg;
+
+  bzero (reg_tick, max_reg * sizeof (int));
+
+  bcopy (all_minus_one, reg_in_table, max_reg * sizeof (int));
+  bcopy (consec_ints, reg_qty, max_reg * sizeof (int));
+  CLEAR_HARD_REG_SET (hard_regs_in_table);
+
+  /* The per-quantity values used to be initialized here, but it is
+     much faster to initialize each as it is made in `make_new_qty'.  */
+
+  for (i = 0; i < NBUCKETS; i++)
+    {
+      register struct table_elt *this, *next;
+      for (this = table[i]; this; this = next)
+	{
+	  next = this->next_same_hash;
+	  free_element (this);
+	}
+    }
+
+  bzero (table, sizeof table);
+
+  prev_insn = 0;
+
+#ifdef HAVE_cc0
+  prev_insn_cc0 = 0;
+#endif
+}
+
+/* Say that register REG contains a quantity not in any register before
+   and initialize that quantity.  */
+
+static void
+make_new_qty (reg)
+     register int reg;
+{
+  register int q;
+
+  if (next_qty >= max_qty)
+    abort ();
+
+  q = reg_qty[reg] = next_qty++;
+  qty_first_reg[q] = reg;
+  qty_last_reg[q] = reg;
+  qty_const[q] = qty_const_insn[q] = 0;
+  qty_comparison_code[q] = UNKNOWN;
+
+  reg_next_eqv[reg] = reg_prev_eqv[reg] = -1;
+}
+
+/* Make reg NEW equivalent to reg OLD.
+   OLD is not changing; NEW is.  */
+
+static void
+make_regs_eqv (new, old)
+     register int new, old;
+{
+  register int lastr, firstr;
+  register int q = reg_qty[old];
+
+  /* Nothing should become eqv until it has a "non-invalid" qty number.  */
+  if (! REGNO_QTY_VALID_P (old))
+    abort ();
+
+  reg_qty[new] = q;
+  firstr = qty_first_reg[q];
+  lastr = qty_last_reg[q];
+
+  /* Prefer fixed hard registers to anything.  Prefer pseudo regs to other
+     hard regs.  Among pseudos, if NEW will live longer than any other reg
+     of the same qty, and that is beyond the current basic block,
+     make it the new canonical replacement for this qty.  */
+  if (! (firstr < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (firstr))
+      /* Certain fixed registers might be of the class NO_REGS.  This means
+	 that not only can they not be allocated by the compiler, but
+	 they cannot be used in substitutions or cannonicallizations
+	 either.  */
+      && (new >= FIRST_PSEUDO_REGISTER || REGNO_REG_CLASS (new) != NO_REGS)
+      && ((new < FIRST_PSEUDO_REGISTER && FIXED_REGNO_P (new))
+	  || (new >= FIRST_PSEUDO_REGISTER
+	      && (firstr < FIRST_PSEUDO_REGISTER
+		  || ((uid_cuid[regno_last_uid[new]] > cse_basic_block_end
+		       || (uid_cuid[regno_first_uid[new]]
+			   < cse_basic_block_start))
+		      && (uid_cuid[regno_last_uid[new]]
+			  > uid_cuid[regno_last_uid[firstr]]))))))
+    {
+      reg_prev_eqv[firstr] = new;
+      reg_next_eqv[new] = firstr;
+      reg_prev_eqv[new] = -1;
+      qty_first_reg[q] = new;
+    }
+  else
+    {
+      /* If NEW is a hard reg (known to be non-fixed), insert at end.
+	 Otherwise, insert before any non-fixed hard regs that are at the
+	 end.  Registers of class NO_REGS cannot be used as an
+	 equivalent for anything.  */
+      while (lastr < FIRST_PSEUDO_REGISTER && reg_prev_eqv[lastr] >= 0
+	     && (REGNO_REG_CLASS (lastr) == NO_REGS || ! FIXED_REGNO_P (lastr))
+	     && new >= FIRST_PSEUDO_REGISTER)
+	lastr = reg_prev_eqv[lastr];
+      reg_next_eqv[new] = reg_next_eqv[lastr];
+      if (reg_next_eqv[lastr] >= 0)
+	reg_prev_eqv[reg_next_eqv[lastr]] = new;
+      else
+	qty_last_reg[q] = new;
+      reg_next_eqv[lastr] = new;
+      reg_prev_eqv[new] = lastr;
+    }
+}
+
+/* Remove REG from its equivalence class.  */
+
+static void
+delete_reg_equiv (reg)
+     register int reg;
+{
+  register int n = reg_next_eqv[reg];
+  register int p = reg_prev_eqv[reg];
+  register int q = reg_qty[reg];
+
+  /* If invalid, do nothing.  N and P above are undefined in that case.  */
+  if (q == reg)
+    return;
+
+  if (n != -1)
+    reg_prev_eqv[n] = p;
+  else
+    qty_last_reg[q] = p;
+  if (p != -1)
+    reg_next_eqv[p] = n;
+  else
+    qty_first_reg[q] = n;
+
+  reg_qty[reg] = reg;
+}
+
+/* Remove any invalid expressions from the hash table
+   that refer to any of the registers contained in expression X.
+
+   Make sure that newly inserted references to those registers
+   as subexpressions will be considered valid.
+
+   mention_regs is not called when a register itself
+   is being stored in the table.
+
+   Return 1 if we have done something that may have changed the hash code
+   of X.  */
+
+static int
+mention_regs (x)
+     rtx x;
+{
+  register enum rtx_code code;
+  register int i, j;
+  register char *fmt;
+  register int changed = 0;
+
+  if (x == 0)
+    return;
+
+  code = GET_CODE (x);
+  if (code == REG)
+    {
+      register int regno = REGNO (x);
+      register int endregno
+	= regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
+		   : HARD_REGNO_NREGS (regno, GET_MODE (x)));
+      int i;
+
+      for (i = regno; i < endregno; i++)
+	{
+	  if (reg_in_table[i] >= 0 && reg_in_table[i] != reg_tick[i])
+	    remove_invalid_refs (i);
+
+	  reg_in_table[i] = reg_tick[i];
+	}
+
+      return 0;
+    }
+
+  /* If X is a comparison or a COMPARE and either operand is a register
+     that does not have a quantity, give it one.  This is so that a later
+     call to record_jump_equiv won't cause X to be assigned a different
+     hash code and not found in the table after that call.
+
+     It is not necessary to do this here, since rehash_using_reg can
+     fix up the table later, but doing this here eliminates the need to
+     call that expensive function in the most common case where the only
+     use of the register is in the comparison.  */
+
+  if (code == COMPARE || GET_RTX_CLASS (code) == '<')
+    {
+      if (GET_CODE (XEXP (x, 0)) == REG
+	  && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 0))))
+	if (insert_regs (XEXP (x, 0), 0, 0))
+	  {
+	    rehash_using_reg (XEXP (x, 0));
+	    changed = 1;
+	  }
+
+      if (GET_CODE (XEXP (x, 1)) == REG
+	  && ! REGNO_QTY_VALID_P (REGNO (XEXP (x, 1))))
+	if (insert_regs (XEXP (x, 1), 0, 0))
+	  {
+	    rehash_using_reg (XEXP (x, 1));
+	    changed = 1;
+	  }
+    }
+
+  fmt = GET_RTX_FORMAT (code);
+  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+    if (fmt[i] == 'e')
+      changed |= mention_regs (XEXP (x, i));
+    else if (fmt[i] == 'E')
+      for (j = 0; j < XVECLEN (x, i); j++)
+	changed |= mention_regs (XVECEXP (x, i, j));
+
+  return changed;
+}
+
+/* Update the register quantities for inserting X into the hash table
+   with a value equivalent to CLASSP.
+   (If the class does not contain a REG, it is irrelevant.)
+   If MODIFIED is nonzero, X is a destination; it is being modified.
+   Note that delete_reg_equiv should be called on a register
+   before insert_regs is done on that register with MODIFIED != 0.
+
+   Nonzero value means that elements of reg_qty have changed
+   so X's hash code may be different.  */
+
+static int
+insert_regs (x, classp, modified)
+     rtx x;
+     struct table_elt *classp;
+     int modified;
+{
+  if (GET_CODE (x) == REG)
+    {
+      register int regno = REGNO (x);
+
+      if (modified
+	  || ! (REGNO_QTY_VALID_P (regno)
+		&& qty_mode[reg_qty[regno]] == GET_MODE (x)))
+	{
+	  if (classp)
+	    for (classp = classp->first_same_value;
+		 classp != 0;
+		 classp = classp->next_same_value)
+	      if (GET_CODE (classp->exp) == REG
+		  && GET_MODE (classp->exp) == GET_MODE (x))
+		{
+		  make_regs_eqv (regno, REGNO (classp->exp));
+		  return 1;
+		}
+
+	  make_new_qty (regno);
+	  qty_mode[reg_qty[regno]] = GET_MODE (x);
+	  return 1;
+	}
+    }
+  else
+    return mention_regs (x);
+}
+
+/* Look in or update the hash table.  */
+
+/* Put the element ELT on the list of free elements.  */
+
+static void
+free_element (elt)
+     struct table_elt *elt;
+{
+  elt->next_same_hash = free_element_chain;
+  free_element_chain = elt;
+}
+
+/* Return an element that is free for use.  */
+
+static struct table_elt *
+get_element ()
+{
+  struct table_elt *elt = free_element_chain;
+  if (elt)
+    {
+      free_element_chain = elt->next_same_hash;
+      return elt;
+    }
+  n_elements_made++;
+  return (struct table_elt *) oballoc (sizeof (struct table_elt));
+}
+
+/* Remove table element ELT from use in the table.
+   HASH is its hash code, made using the HASH macro.
+   It's an argument because often that is known in advance
+   and we save much time not recomputing it.  */
+
+static void
+remove_from_table (elt, hash)
+     register struct table_elt *elt;
+     int hash;
+{
+  if (elt == 0)
+    return;
+
+  /* Mark this element as removed.  See cse_insn.  */
+  elt->first_same_value = 0;
+
+  /* Remove the table element from its equivalence class.  */
+     
+  {
+    register struct table_elt *prev = elt->prev_same_value;
+    register struct table_elt *next = elt->next_same_value;
+
+    if (next) next->prev_same_value = prev;
+
+    if (prev)
+      prev->next_same_value = next;
+    else
+      {
+	register struct table_elt *newfirst = next;
+	while (next)
+	  {
+	    next->first_same_value = newfirst;
+	    next = next->next_same_value;
+	  }
+      }
+  }
+
+  /* Remove the table element from its hash bucket.  */
+
+  {
+    register struct table_elt *prev = elt->prev_same_hash;
+    register struct table_elt *next = elt->next_same_hash;
+
+    if (next) next->prev_same_hash = prev;
+
+    if (prev)
+      prev->next_same_hash = next;
+    else if (table[hash] == elt)
+      table[hash] = next;
+    else
+      {
+	/* This entry is not in the proper hash bucket.  This can happen
+	   when two classes were merged by `merge_equiv_classes'.  Search
+	   for the hash bucket that it heads.  This happens only very
+	   rarely, so the cost is acceptable.  */
+	for (hash = 0; hash < NBUCKETS; hash++)
+	  if (table[hash] == elt)
+	    table[hash] = next;
+      }
+  }
+
+  /* Remove the table element from its related-value circular chain.  */
+
+  if (elt->related_value != 0 && elt->related_value != elt)
+    {
+      register struct table_elt *p = elt->related_value;
+      while (p->related_value != elt)
+	p = p->related_value;
+      p->related_value = elt->related_value;
+      if (p->related_value == p)
+	p->related_value = 0;
+    }
+
+  free_element (elt);
+}
+
+/* Look up X in the hash table and return its table element,
+   or 0 if X is not in the table.
+
+   MODE is the machine-mode of X, or if X is an integer constant
+   with VOIDmode then MODE is the mode with which X will be used.
+
+   Here we are satisfied to find an expression whose tree structure
+   looks like X.  */
+
+static struct table_elt *
+lookup (x, hash, mode)
+     rtx x;
+     int hash;
+     enum machine_mode mode;
+{
+  register struct table_elt *p;
+
+  for (p = table[hash]; p; p = p->next_same_hash)
+    if (mode == p->mode && ((x == p->exp && GET_CODE (x) == REG)
+			    || exp_equiv_p (x, p->exp, GET_CODE (x) != REG, 0)))
+      return p;
+
+  return 0;
+}
+
+/* Like `lookup' but don't care whether the table element uses invalid regs.
+   Also ignore discrepancies in the machine mode of a register.  */
+
+static struct table_elt *
+lookup_for_remove (x, hash, mode)
+     rtx x;
+     int hash;
+     enum machine_mode mode;
+{
+  register struct table_elt *p;
+
+  if (GET_CODE (x) == REG)
+    {
+      int regno = REGNO (x);
+      /* Don't check the machine mode when comparing registers;
+	 invalidating (REG:SI 0) also invalidates (REG:DF 0).  */
+      for (p = table[hash]; p; p = p->next_same_hash)
+	if (GET_CODE (p->exp) == REG
+	    && REGNO (p->exp) == regno)
+	  return p;
+    }
+  else
+    {
+      for (p = table[hash]; p; p = p->next_same_hash)
+	if (mode == p->mode && (x == p->exp || exp_equiv_p (x, p->exp, 0, 0)))
+	  return p;
+    }
+
+  return 0;
+}
+
+/* Look for an expression equivalent to X and with code CODE.
+   If one is found, return that expression.  */
+
+static rtx
+lookup_as_function (x, code)
+     rtx x;
+     enum rtx_code code;
+{
+  register struct table_elt *p = lookup (x, safe_hash (x, VOIDmode) % NBUCKETS,
+					 GET_MODE (x));
+  if (p == 0)
+    return 0;
+
+  for (p = p->first_same_value; p; p = p->next_same_value)
+    {
+      if (GET_CODE (p->exp) == code
+	  /* Make sure this is a valid entry in the table.  */
+	  && exp_equiv_p (p->exp, p->exp, 1, 0))
+	return p->exp;
+    }
+  
+  return 0;
+}
+
+/* Insert X in the hash table, assuming HASH is its hash code
+   and CLASSP is an element of the class it should go in
+   (or 0 if a new class should be made).
+   It is inserted at the proper position to keep the class in
+   the order cheapest first.
+
+   MODE is the machine-mode of X, or if X is an integer constant
+   with VOIDmode then MODE is the mode with which X will be used.
+
+   For elements of equal cheapness, the most recent one
+   goes in front, except that the first element in the list
+   remains first unless a cheaper element is added.  The order of
+   pseudo-registers does not matter, as canon_reg will be called to
+   find the cheapest when a register is retreived from the table.
+
+   The in_memory field in the hash table element is set to 0.
+   The caller must set it nonzero if appropriate.
+
+   You should call insert_regs (X, CLASSP, MODIFY) before calling here,
+   and if insert_regs returns a nonzero value
+   you must then recompute its hash code before calling here.
+
+   If necessary, update table showing constant values of quantities.  */
+
+#define CHEAPER(X,Y)   ((X)->cost < (Y)->cost)
+
+static struct table_elt *
+insert (x, classp, hash, mode)
+     register rtx x;
+     register struct table_elt *classp;
+     int hash;
+     enum machine_mode mode;
+{
+  register struct table_elt *elt;
+
+  /* If X is a register and we haven't made a quantity for it,
+     something is wrong.  */
+  if (GET_CODE (x) == REG && ! REGNO_QTY_VALID_P (REGNO (x)))
+    abort ();
+
+  /* If X is a hard register, show it is being put in the table.  */
+  if (GET_CODE (x) == REG && REGNO (x) < FIRST_PSEUDO_REGISTER)
+    {
+      int regno = REGNO (x);
+      int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
+      int i;
+
+      for (i = regno; i < endregno; i++)
+	    SET_HARD_REG_BIT (hard_regs_in_table, i);
+    }
+
+
+  /* Put an element for X into the right hash bucket.  */
+
+  elt = get_element ();
+  elt->exp = x;
+  elt->cost = COST (x);
+  elt->next_same_value = 0;
+  elt->prev_same_value = 0;
+  elt->next_same_hash = table[hash];
+  elt->prev_same_hash = 0;
+  elt->related_value = 0;
+  elt->in_memory = 0;
+  elt->mode = mode;
+  elt->is_const = (CONSTANT_P (x)
+		   /* GNU C++ takes advantage of this for `this'
+		      (and other const values).  */
+		   || (RTX_UNCHANGING_P (x)
+		       && GET_CODE (x) == REG
+		       && REGNO (x) >= FIRST_PSEUDO_REGISTER)
+		   || FIXED_BASE_PLUS_P (x));
+
+  if (table[hash])
+    table[hash]->prev_same_hash = elt;
+  table[hash] = elt;
+
+  /* Put it into the proper value-class.  */
+  if (classp)
+    {
+      classp = classp->first_same_value;
+      if (CHEAPER (elt, classp))
+	/* Insert at the head of the class */
+	{
+	  register struct table_elt *p;
+	  elt->next_same_value = classp;
+	  classp->prev_same_value = elt;
+	  elt->first_same_value = elt;
+
+	  for (p = classp; p; p = p->next_same_value)
+	    p->first_same_value = elt;
+	}
+      else
+	{
+	  /* Insert not at head of the class.  */
+	  /* Put it after the last element cheaper than X.  */
+	  register struct table_elt *p, *next;
+	  for (p = classp; (next = p->next_same_value) && CHEAPER (next, elt);
+	       p = next);
+	  /* Put it after P and before NEXT.  */
+	  elt->next_same_value = next;
+	  if (next)
+	    next->prev_same_value = elt;
+	  elt->prev_same_value = p;
+	  p->next_same_value = elt;
+	  elt->first_same_value = classp;
+	}
+    }
+  else
+    elt->first_same_value = elt;
+
+  /* If this is a constant being set equivalent to a register or a register
+     being set equivalent to a constant, note the constant equivalence.
+
+     If this is a constant, it cannot be equivalent to a different constant,
+     and a constant is the only thing that can be cheaper than a register.  So
+     we know the register is the head of the class (before the constant was
+     inserted).
+
+     If this is a register that is not already known equivalent to a
+     constant, we must check the entire class.
+
+     If this is a register that is already known equivalent to an insn,
+     update `qty_const_insn' to show that `this_insn' is the latest
+     insn making that quantity equivalent to the constant.  */
+
+  if (elt->is_const && classp && GET_CODE (classp->exp) == REG)
+    {
+      qty_const[reg_qty[REGNO (classp->exp)]]
+	= gen_lowpart_if_possible (qty_mode[reg_qty[REGNO (classp->exp)]], x);
+      qty_const_insn[reg_qty[REGNO (classp->exp)]] = this_insn;
+    }
+
+  else if (GET_CODE (x) == REG && classp && ! qty_const[reg_qty[REGNO (x)]])
+    {
+      register struct table_elt *p;
+
+      for (p = classp; p != 0; p = p->next_same_value)
+	{
+	  if (p->is_const)
+	    {
+	      qty_const[reg_qty[REGNO (x)]]
+		= gen_lowpart_if_possible (GET_MODE (x), p->exp);
+	      qty_const_insn[reg_qty[REGNO (x)]] = this_insn;
+	      break;
+	    }
+	}
+    }
+
+  else if (GET_CODE (x) == REG && qty_const[reg_qty[REGNO (x)]]
+	   && GET_MODE (x) == qty_mode[reg_qty[REGNO (x)]])
+    qty_const_insn[reg_qty[REGNO (x)]] = this_insn;
+
+  /* If this is a constant with symbolic value,
+     and it has a term with an explicit integer value,
+     link it up with related expressions.  */
+  if (GET_CODE (x) == CONST)
+    {
+      rtx subexp = get_related_value (x);
+      int subhash;
+      struct table_elt *subelt, *subelt_prev;
+
+      if (subexp != 0)
+	{
+	  /* Get the integer-free subexpression in the hash table.  */
+	  subhash = safe_hash (subexp, mode) % NBUCKETS;
+	  subelt = lookup (subexp, subhash, mode);
+	  if (subelt == 0)
+	    subelt = insert (subexp, 0, subhash, mode);
+	  /* Initialize SUBELT's circular chain if it has none.  */
+	  if (subelt->related_value == 0)
+	    subelt->related_value = subelt;
+	  /* Find the element in the circular chain that precedes SUBELT.  */
+	  subelt_prev = subelt;
+	  while (subelt_prev->related_value != subelt)
+	    subelt_prev = subelt_prev->related_value;
+	  /* Put new ELT into SUBELT's circular chain just before SUBELT.
+	     This way the element that follows SUBELT is the oldest one.  */
+	  elt->related_value = subelt_prev->related_value;
+	  subelt_prev->related_value = elt;
+	}
+    }
+
+  return elt;
+}
+
+/* Given two equivalence classes, CLASS1 and CLASS2, put all the entries from
+   CLASS2 into CLASS1.  This is done when we have reached an insn which makes
+   the two classes equivalent.
+
+   CLASS1 will be the surviving class; CLASS2 should not be used after this
+   call.
+
+   Any invalid entries in CLASS2 will not be copied.  */
+
+static void
+merge_equiv_classes (class1, class2)
+     struct table_elt *class1, *class2;
+{
+  struct table_elt *elt, *next, *new;
+
+  /* Ensure we start with the head of the classes.  */
+  class1 = class1->first_same_value;
+  class2 = class2->first_same_value;
+
+  /* If they were already equal, forget it.  */
+  if (class1 == class2)
+    return;
+
+  for (elt = class2; elt; elt = next)
+    {
+      int hash;
+      rtx exp = elt->exp;
+      enum machine_mode mode = elt->mode;
+
+      next = elt->next_same_value;
+
+      /* Remove old entry, make a new one in CLASS1's class.
+	 Don't do this for invalid entries as we cannot find their
+	 hash code (it also isn't necessary). */
+      if (GET_CODE (exp) == REG || exp_equiv_p (exp, exp, 1, 0))
+	{
+	  hash_arg_in_memory = 0;
+	  hash_arg_in_struct = 0;
+	  hash = HASH (exp, mode);
+	      
+	  if (GET_CODE (exp) == REG)
+	    delete_reg_equiv (REGNO (exp));
+	      
+	  remove_from_table (elt, hash);
+
+	  if (insert_regs (exp, class1, 0))
+	    hash = HASH (exp, mode);
+	  new = insert (exp, class1, hash, mode);
+	  new->in_memory = hash_arg_in_memory;
+	  new->in_struct = hash_arg_in_struct;
+	}
+    }
+}
+
+/* Remove from the hash table, or mark as invalid,
+   all expressions whose values could be altered by storing in X.
+   X is a register, a subreg, or a memory reference with nonvarying address
+   (because, when a memory reference with a varying address is stored in,
+   all memory references are removed by invalidate_memory
+   so specific invalidation is superfluous).
+
+   A nonvarying address may be just a register or just
+   a symbol reference, or it may be either of those plus
+   a numeric offset.  */
+
+static void
+invalidate (x)
+     rtx x;
+{
+  register int i;
+  register struct table_elt *p;
+  register rtx base;
+  register int start, end;
+
+  /* If X is a register, dependencies on its contents
+     are recorded through the qty number mechanism.
+     Just change the qty number of the register,
+     mark it as invalid for expressions that refer to it,
+     and remove it itself.  */
+
+  if (GET_CODE (x) == REG)
+    {
+      register int regno = REGNO (x);
+      register int hash = HASH (x, GET_MODE (x));
+
+      /* Remove REGNO from any quantity list it might be on and indicate
+	 that it's value might have changed.  If it is a pseudo, remove its
+	 entry from the hash table.
+
+	 For a hard register, we do the first two actions above for any
+	 additional hard registers corresponding to X.  Then, if any of these
+	 registers are in the table, we must remove any REG entries that
+	 overlap these registers.  */
+
+      delete_reg_equiv (regno);
+      reg_tick[regno]++;
+
+      if (regno >= FIRST_PSEUDO_REGISTER)
+	remove_from_table (lookup_for_remove (x, hash, GET_MODE (x)), hash);
+      else
+	{
+	  int in_table = TEST_HARD_REG_BIT (hard_regs_in_table, regno);
+	  int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
+	  int tregno, tendregno;
+	  register struct table_elt *p, *next;
+
+	  CLEAR_HARD_REG_BIT (hard_regs_in_table, regno);
+
+	  for (i = regno + 1; i < endregno; i++)
+	    {
+	      in_table |= TEST_HARD_REG_BIT (hard_regs_in_table, i);
+	      CLEAR_HARD_REG_BIT (hard_regs_in_table, i);
+	      delete_reg_equiv (i);
+	      reg_tick[i]++;
+	    }
+
+	  if (in_table)
+	    for (hash = 0; hash < NBUCKETS; hash++)
+	      for (p = table[hash]; p; p = next)
+		{
+		  next = p->next_same_hash;
+
+		  if (GET_CODE (p->exp) != REG
+		      || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER)
+		    continue;
+
+		  tregno = REGNO (p->exp);
+		  tendregno
+		    = tregno + HARD_REGNO_NREGS (tregno, GET_MODE (p->exp));
+		  if (tendregno > regno && tregno < endregno)
+		  remove_from_table (p, hash);
+		}
+	}
+
+      return;
+    }
+
+  if (GET_CODE (x) == SUBREG)
+    {
+      if (GET_CODE (SUBREG_REG (x)) != REG)
+	abort ();
+      invalidate (SUBREG_REG (x));
+      return;
+    }
+
+  /* X is not a register; it must be a memory reference with
+     a nonvarying address.  Remove all hash table elements
+     that refer to overlapping pieces of memory.  */
+
+  if (GET_CODE (x) != MEM)
+    abort ();
+  base = XEXP (x, 0);
+  start = 0;
+
+  /* Registers with nonvarying addresses usually have constant equivalents;
+     but the frame pointer register is also possible.  */
+  if (GET_CODE (base) == REG
+      && REGNO_QTY_VALID_P (REGNO (base))
+      && qty_mode[reg_qty[REGNO (base)]] == GET_MODE (base)
+      && qty_const[reg_qty[REGNO (base)]] != 0)
+    base = qty_const[reg_qty[REGNO (base)]];
+  else if (GET_CODE (base) == PLUS
+	   && GET_CODE (XEXP (base, 1)) == CONST_INT
+	   && GET_CODE (XEXP (base, 0)) == REG
+	   && REGNO_QTY_VALID_P (REGNO (XEXP (base, 0)))
+	   && (qty_mode[reg_qty[REGNO (XEXP (base, 0))]]
+	       == GET_MODE (XEXP (base, 0)))
+	   && qty_const[reg_qty[REGNO (XEXP (base, 0))]])
+    {
+      start = INTVAL (XEXP (base, 1));
+      base = qty_const[reg_qty[REGNO (XEXP (base, 0))]];
+    }
+
+  if (GET_CODE (base) == CONST)
+    base = XEXP (base, 0);
+  if (GET_CODE (base) == PLUS
+      && GET_CODE (XEXP (base, 1)) == CONST_INT)
+    {
+      start += INTVAL (XEXP (base, 1));
+      base = XEXP (base, 0);
+    }
+
+  end = start + GET_MODE_SIZE (GET_MODE (x));
+  for (i = 0; i < NBUCKETS; i++)
+    {
+      register struct table_elt *next;
+      for (p = table[i]; p; p = next)
+	{
+	  next = p->next_same_hash;
+	  if (refers_to_mem_p (p->exp, base, start, end))
+	    remove_from_table (p, i);
+	}
+    }
+}
+
+/* Remove all expressions that refer to register REGNO,
+   since they are already invalid, and we are about to
+   mark that register valid again and don't want the old
+   expressions to reappear as valid.  */
+
+static void
+remove_invalid_refs (regno)
+     int regno;
+{
+  register int i;
+  register struct table_elt *p, *next;
+
+  for (i = 0; i < NBUCKETS; i++)
+    for (p = table[i]; p; p = next)
+      {
+	next = p->next_same_hash;
+	if (GET_CODE (p->exp) != REG
+	    && refers_to_regno_p (regno, regno + 1, p->exp, 0))
+	  remove_from_table (p, i);
+      }
+}
+
+/* Recompute the hash codes of any valid entries in the hash table that
+   reference X, if X is a register, or SUBREG_REG (X) if X is a SUBREG.
+
+   This is called when we make a jump equivalence.  */
+
+static void
+rehash_using_reg (x)
+     rtx x;
+{
+  int i;
+  struct table_elt *p, *next;
+  int hash;
+
+  if (GET_CODE (x) == SUBREG)
+    x = SUBREG_REG (x);
+
+  /* If X is not a register or if the register is known not to be in any
+     valid entries in the table, we have no work to do.  */
+
+  if (GET_CODE (x) != REG
+      || reg_in_table[REGNO (x)] < 0
+      || reg_in_table[REGNO (x)] != reg_tick[REGNO (x)])
+    return;
+
+  /* Scan all hash chains looking for valid entries that mention X.
+     If we find one and it is in the wrong hash chain, move it.  We can skip
+     objects that are registers, since they are handled specially.  */
+
+  for (i = 0; i < NBUCKETS; i++)
+    for (p = table[i]; p; p = next)
+      {
+	next = p->next_same_hash;
+	if (GET_CODE (p->exp) != REG && reg_mentioned_p (x, p->exp)
+	    && exp_equiv_p (p->exp, p->exp, 1)
+	    && i != (hash = safe_hash (p->exp, p->mode) % NBUCKETS))
+	  {
+	    if (p->next_same_hash)
+	      p->next_same_hash->prev_same_hash = p->prev_same_hash;
+
+	    if (p->prev_same_hash)
+	      p->prev_same_hash->next_same_hash = p->next_same_hash;
+	    else
+	      table[i] = p->next_same_hash;
+
+	    p->next_same_hash = table[hash];
+	    p->prev_same_hash = 0;
+	    if (table[hash])
+	      table[hash]->prev_same_hash = p;
+	    table[hash] = p;
+	  }
+      }
+}
+
+/* Remove from the hash table all expressions that reference memory,
+   or some of them as specified by *WRITES.  */
+
+static void
+invalidate_memory (writes)
+     struct write_data *writes;
+{
+  register int i;
+  register struct table_elt *p, *next;
+  int all = writes->all;
+  int nonscalar = writes->nonscalar;
+
+  for (i = 0; i < NBUCKETS; i++)
+    for (p = table[i]; p; p = next)
+      {
+	next = p->next_same_hash;
+	if (p->in_memory
+	    && (all
+		|| (nonscalar && p->in_struct)
+		|| cse_rtx_addr_varies_p (p->exp)))
+	  remove_from_table (p, i);
+      }
+}
+
+/* Remove from the hash table any expression that is a call-clobbered
+   register.  Also update their TICK values.  */
+
+static void
+invalidate_for_call ()
+{
+  int regno, endregno;
+  int i;
+  int hash;
+  struct table_elt *p, *next;
+  int in_table = 0;
+
+  /* Go through all the hard registers.  For each that is clobbered in
+     a CALL_INSN, remove the register from quantity chains and update
+     reg_tick if defined.  Also see if any of these registers is currently
+     in the table.  */
+
+  for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
+    if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
+      {
+	delete_reg_equiv (regno);
+	if (reg_tick[regno] >= 0)
+	  reg_tick[regno]++;
+
+	in_table |= TEST_HARD_REG_BIT (hard_regs_in_table, regno);
+      }
+
+  /* In the case where we have no call-clobbered hard registers in the
+     table, we are done.  Otherwise, scan the table and remove any
+     entry that overlaps a call-clobbered register.  */
+
+  if (in_table)
+    for (hash = 0; hash < NBUCKETS; hash++)
+      for (p = table[hash]; p; p = next)
+	{
+	  next = p->next_same_hash;
+
+	  if (GET_CODE (p->exp) != REG
+	      || REGNO (p->exp) >= FIRST_PSEUDO_REGISTER)
+	    continue;
+
+	  regno = REGNO (p->exp);
+	  endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (p->exp));
+
+	  for (i = regno; i < endregno; i++)
+	    if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
+	      {
+		remove_from_table (p, hash);
+		break;
+	      }
+	}
+}
+
+/* Given an expression X of type CONST,
+   and ELT which is its table entry (or 0 if it
+   is not in the hash table),
+   return an alternate expression for X as a register plus integer.
+   If none can be found, return 0.  */
+
+static rtx
+use_related_value (x, elt)
+     rtx x;
+     struct table_elt *elt;
+{
+  register struct table_elt *relt = 0;
+  register struct table_elt *p, *q;
+  int offset;
+
+  /* First, is there anything related known?
+     If we have a table element, we can tell from that.
+     Otherwise, must look it up.  */
+
+  if (elt != 0 && elt->related_value != 0)
+    relt = elt;
+  else if (elt == 0 && GET_CODE (x) == CONST)
+    {
+      rtx subexp = get_related_value (x);
+      if (subexp != 0)
+	relt = lookup (subexp,
+		       safe_hash (subexp, GET_MODE (subexp)) % NBUCKETS,
+		       GET_MODE (subexp));
+    }
+
+  if (relt == 0)
+    return 0;
+
+  /* Search all related table entries for one that has an
+     equivalent register.  */
+
+  p = relt;
+  while (1)
+    {
+      /* This loop is strange in that it is executed in two different cases.
+	 The first is when X is already in the table.  Then it is searching
+	 the RELATED_VALUE list of X's class (RELT).  The second case is when
+	 X is not in the table.  Then RELT points to a class for the related
+	 value.
+
+	 Ensure that, whatever case we are in, that we ignore classes that have
+	 the same value as X.  */
+
+      if (rtx_equal_p (x, p->exp))
+	q = 0;
+      else
+	for (q = p->first_same_value; q; q = q->next_same_value)
+	  if (GET_CODE (q->exp) == REG)
+	    break;
+
+      if (q)
+	break;
+
+      p = p->related_value;
+
+      /* We went all the way around, so there is nothing to be found.
+	 Alternatively, perhaps RELT was in the table for some other reason
+	 and it has no related values recorded.  */
+      if (p == relt || p == 0)
+	break;
+    }
+
+  if (q == 0)
+    return 0;
+
+  offset = (get_integer_term (x) - get_integer_term (p->exp));
+  /* Note: OFFSET may be 0 if P->xexp and X are related by commutativity.  */
+  return plus_constant (q->exp, offset);
+}
+
+/* Hash an rtx.  We are careful to make sure the value is never negative.
+   Equivalent registers hash identically.
+   MODE is used in hashing for CONST_INTs only;
+   otherwise the mode of X is used.
+
+   Store 1 in do_not_record if any subexpression is volatile.
+
+   Store 1 in hash_arg_in_memory if X contains a MEM rtx
+   which does not have the RTX_UNCHANGING_P bit set.
+   In this case, also store 1 in hash_arg_in_struct
+   if there is a MEM rtx which has the MEM_IN_STRUCT_P bit set.
+
+   Note that cse_insn knows that the hash code of a MEM expression
+   is just (int) MEM plus the hash code of the address.  */
+
+static int
+canon_hash (x, mode)
+     rtx x;
+     enum machine_mode mode;
+{
+  register int i, j;
+  register int hash = 0;
+  register enum rtx_code code;
+  register char *fmt;
+
+  /* repeat is used to turn tail-recursion into iteration.  */
+ repeat:
+  if (x == 0)
+    return hash;
+
+  code = GET_CODE (x);
+  switch (code)
+    {
+    case REG:
+      {
+	register int regno = REGNO (x);
+
+	/* On some machines, we can't record any non-fixed hard register,
+	   because extending its life will cause reload problems.  We
+	   consider ap, fp, and sp to be fixed for this purpose.
+	   On all machines, we can't record any global registers. */
+
+	if (regno < FIRST_PSEUDO_REGISTER
+	    && (global_regs[regno]
+#ifdef SMALL_REGISTER_CLASSES
+		|| (! fixed_regs[regno]
+		    && regno != FRAME_POINTER_REGNUM
+		    && regno != ARG_POINTER_REGNUM
+		    && regno != STACK_POINTER_REGNUM)
+#endif
+		))
+	  {
+	    do_not_record = 1;
+	    return 0;
+	  }
+	return hash + ((int) REG << 7) + reg_qty[regno];
+      }
+
+    case CONST_INT:
+      hash += ((int) mode + ((int) CONST_INT << 7)
+	       + INTVAL (x) + (INTVAL (x) >> HASHBITS));
+      return ((1 << HASHBITS) - 1) & hash;
+
+    case CONST_DOUBLE:
+      /* This is like the general case, except that it only counts
+	 the integers representing the constant.  */
+      hash += (int) code + (int) GET_MODE (x);
+      {
+	int i;
+	for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++)
+	  {
+	    int tem = XINT (x, i);
+	    hash += ((1 << HASHBITS) - 1) & (tem + (tem >> HASHBITS));
+	  }
+      }
+      return hash;
+
+      /* Assume there is only one rtx object for any given label.  */
+    case LABEL_REF:
+      /* Use `and' to ensure a positive number.  */
+      return (hash + ((int) LABEL_REF << 7)
+	      + ((int) XEXP (x, 0) & ((1 << HASHBITS) - 1)));
+
+    case SYMBOL_REF:
+      return (hash + ((int) SYMBOL_REF << 7)
+	      + ((int) XEXP (x, 0) & ((1 << HASHBITS) - 1)));
+
+    case MEM:
+      if (MEM_VOLATILE_P (x))
+	{
+	  do_not_record = 1;
+	  return 0;
+	}
+      if (! RTX_UNCHANGING_P (x))
+	{
+	  hash_arg_in_memory = 1;
+	  if (MEM_IN_STRUCT_P (x)) hash_arg_in_struct = 1;
+	}
+      /* Now that we have already found this special case,
+	 might as well speed it up as much as possible.  */
+      hash += (int) MEM;
+      x = XEXP (x, 0);
+      goto repeat;
+
+    case PRE_DEC:
+    case PRE_INC:
+    case POST_DEC:
+    case POST_INC:
+    case PC:
+    case CC0:
+    case CALL:
+    case UNSPEC_VOLATILE:
+      do_not_record = 1;
+      return 0;
+
+    case ASM_OPERANDS:
+      if (MEM_VOLATILE_P (x))
+	{
+	  do_not_record = 1;
+	  return 0;
+	}
+    }
+
+  i = GET_RTX_LENGTH (code) - 1;
+  hash += (int) code + (int) GET_MODE (x);
+  fmt = GET_RTX_FORMAT (code);
+  for (; i >= 0; i--)
+    {
+      if (fmt[i] == 'e')
+	{
+	  rtx tem = XEXP (x, i);
+	  rtx tem1;
+
+	  /* If the operand is a REG that is equivalent to a constant, hash
+	     as if we were hashing the constant, since we will be comparing
+	     that way.  */
+	  if (tem != 0 && GET_CODE (tem) == REG
+	      && REGNO_QTY_VALID_P (REGNO (tem))
+	      && qty_mode[reg_qty[REGNO (tem)]] == GET_MODE (tem)
+	      && (tem1 = qty_const[reg_qty[REGNO (tem)]]) != 0
+	      && CONSTANT_P (tem1))
+	    tem = tem1;
+
+	  /* If we are about to do the last recursive call
+	     needed at this level, change it into iteration.
+	     This function  is called enough to be worth it.  */
+	  if (i == 0)
+	    {
+	      x = tem;
+	      goto repeat;
+	    }
+	  hash += canon_hash (tem, 0);
+	}
+      else if (fmt[i] == 'E')
+	for (j = 0; j < XVECLEN (x, i); j++)
+	  hash += canon_hash (XVECEXP (x, i, j), 0);
+      else if (fmt[i] == 's')
+	{
+	  register char *p = XSTR (x, i);
+	  if (p)
+	    while (*p)
+	      {
+		register int tem = *p++;
+		hash += ((1 << HASHBITS) - 1) & (tem + (tem >> HASHBITS));
+	      }
+	}
+      else if (fmt[i] == 'i')
+	{
+	  register int tem = XINT (x, i);
+	  hash += ((1 << HASHBITS) - 1) & (tem + (tem >> HASHBITS));
+	}
+      else
+	abort ();
+    }
+  return hash;
+}
+
+/* Like canon_hash but with no side effects.  */
+
+static int
+safe_hash (x, mode)
+     rtx x;
+     enum machine_mode mode;
+{
+  int save_do_not_record = do_not_record;
+  int save_hash_arg_in_memory = hash_arg_in_memory;
+  int save_hash_arg_in_struct = hash_arg_in_struct;
+  int hash = canon_hash (x, mode);
+  hash_arg_in_memory = save_hash_arg_in_memory;
+  hash_arg_in_struct = save_hash_arg_in_struct;
+  do_not_record = save_do_not_record;
+  return hash;
+}
+
+/* Return 1 iff X and Y would canonicalize into the same thing,
+   without actually constructing the canonicalization of either one.
+   If VALIDATE is nonzero,
+   we assume X is an expression being processed from the rtl
+   and Y was found in the hash table.  We check register refs
+   in Y for being marked as valid.
+
+   If EQUAL_VALUES is nonzero, we allow a register to match a constant value
+   that is known to be in the register.  Ordinarily, we don't allow them
+   to match, because letting them match would cause unpredictable results
+   in all the places that search a hash table chain for an equivalent
+   for a given value.  A possible equivalent that has different structure
+   has its hash code computed from different data.  Whether the hash code
+   is the same as that of the the given value is pure luck.  */
+
+static int
+exp_equiv_p (x, y, validate, equal_values)
+     rtx x, y;
+     int validate;
+     int equal_values;
+{
+  register int i;
+  register enum rtx_code code;
+  register char *fmt;
+
+  /* Note: it is incorrect to assume an expression is equivalent to itself
+     if VALIDATE is nonzero.  */
+  if (x == y && !validate)
+    return 1;
+  if (x == 0 || y == 0)
+    return x == y;
+
+  code = GET_CODE (x);
+  if (code != GET_CODE (y))
+    {
+      if (!equal_values)
+	return 0;
+
+      /* If X is a constant and Y is a register or vice versa, they may be
+	 equivalent.  We only have to validate if Y is a register.  */
+      if (CONSTANT_P (x) && GET_CODE (y) == REG
+	  && REGNO_QTY_VALID_P (REGNO (y))
+	  && GET_MODE (y) == qty_mode[reg_qty[REGNO (y)]]
+	  && rtx_equal_p (x, qty_const[reg_qty[REGNO (y)]])
+	  && (! validate || reg_in_table[REGNO (y)] == reg_tick[REGNO (y)]))
+	return 1;
+
+      if (CONSTANT_P (y) && code == REG
+	  && REGNO_QTY_VALID_P (REGNO (x))
+	  && GET_MODE (x) == qty_mode[reg_qty[REGNO (x)]]
+	  && rtx_equal_p (y, qty_const[reg_qty[REGNO (x)]]))
+	return 1;
+
+      return 0;
+    }
+
+  /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.  */
+  if (GET_MODE (x) != GET_MODE (y))
+    return 0;
+
+  switch (code)
+    {
+    case PC:
+    case CC0:
+      return x == y;
+
+    case CONST_INT:
+      return XINT (x, 0) == XINT (y, 0);
+
+    case LABEL_REF:
+    case SYMBOL_REF:
+      return XEXP (x, 0) == XEXP (y, 0);
+
+    case REG:
+      {
+	int regno = REGNO (y);
+	int endregno
+	  = regno + (regno >= FIRST_PSEUDO_REGISTER ? 1
+		     : HARD_REGNO_NREGS (regno, GET_MODE (y)));
+	int i;
+
+	/* If the quantities are not the same, the expressions are not
+	   equivalent.  If there are and we are not to validate, they
+	   are equivalent.  Otherwise, ensure all regs are up-to-date.  */
+
+	if (reg_qty[REGNO (x)] != reg_qty[regno])
+	  return 0;
+
+	if (! validate)
+	  return 1;
+
+	for (i = regno; i < endregno; i++)
+	  if (reg_in_table[i] != reg_tick[i])
+	    return 0;
+
+	return 1;
+      }
+
+    /*  For commutative operations, check both orders.  */
+    case PLUS:
+    case MULT:
+    case AND:
+    case IOR:
+    case XOR:
+    case NE:
+    case EQ:
+      return ((exp_equiv_p (XEXP (x, 0), XEXP (y, 0), validate, equal_values)
+	       && exp_equiv_p (XEXP (x, 1), XEXP (y, 1),
+			       validate, equal_values))
+	      || (exp_equiv_p (XEXP (x, 0), XEXP (y, 1),
+			       validate, equal_values)
+		  && exp_equiv_p (XEXP (x, 1), XEXP (y, 0),
+				  validate, equal_values)));
+    }
+
+  /* Compare the elements.  If any pair of corresponding elements
+     fail to match, return 0 for the whole things.  */
+
+  fmt = GET_RTX_FORMAT (code);
+  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+    {
+      if (fmt[i] == 'e')
+	{
+	  if (! exp_equiv_p (XEXP (x, i), XEXP (y, i), validate, equal_values))
+	    return 0;
+	}
+      else if (fmt[i] == 'E')
+	{
+	  int j;
+	  if (XVECLEN (x, i) != XVECLEN (y, i))
+	    return 0;
+	  for (j = 0; j < XVECLEN (x, i); j++)
+	    if (! exp_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j),
+			       validate, equal_values))
+	      return 0;
+	}
+      else if (fmt[i] == 's')
+	{
+	  if (strcmp (XSTR (x, i), XSTR (y, i)))
+	    return 0;
+	}
+      else if (fmt[i] == 'i')
+	{
+	  if (XINT (x, i) != XINT (y, i))
+	    return 0;
+	}
+      else if (fmt[i] != '0')
+ 	abort ();
+    }
+  return 1;
+}
+
+/* Return 1 iff any subexpression of X matches Y.
+   Here we do not require that X or Y be valid (for registers referred to)
+   for being in the hash table.  */
+
+int
+refers_to_p (x, y)
+     rtx x, y;
+{
+  register int i;
+  register enum rtx_code code;
+  register char *fmt;
+
+ repeat:
+  if (x == y)
+    return 1;
+  if (x == 0 || y == 0)
+    return 0;
+
+  code = GET_CODE (x);
+  /* If X as a whole has the same code as Y, they may match.
+     If so, return 1.  */
+  if (code == GET_CODE (y))
+    {
+      if (exp_equiv_p (x, y, 0, 1))
+	return 1;
+    }
+
+  /* X does not match, so try its subexpressions.  */
+
+  fmt = GET_RTX_FORMAT (code);
+  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+    if (fmt[i] == 'e')
+      {
+	if (i == 0)
+	  {
+	    x = XEXP (x, 0);
+	    goto repeat;
+	  }
+	else
+	  if (refers_to_p (XEXP (x, i), y))
+	    return 1;
+      }
+    else if (fmt[i] == 'E')
+      {
+	int j;
+	for (j = 0; j < XVECLEN (x, i); j++)
+	  if (refers_to_p (XVECEXP (x, i, j), y))
+	    return 1;
+      }
+
+  return 0;
+}
+
+/* Return 1 iff any subexpression of X refers to memory
+   at an address of BASE plus some offset
+   such that any of the bytes' offsets fall between START (inclusive)
+   and END (exclusive).
+
+   The value is undefined if X is a varying address.
+   This function is not used in such cases.
+
+   When used in the cse pass, `qty_const' is nonzero, and it is used
+   to treat an address that is a register with a known constant value
+   as if it were that constant value.
+   In the loop pass, `qty_const' is zero, so this is not done.  */
+
+int
+refers_to_mem_p (x, base, start, end)
+     rtx x, base;
+     int start, end;
+{
+  register int i;
+  register enum rtx_code code;
+  register char *fmt;
+
+  if (GET_CODE (base) == CONST_INT)
+    {
+      start += INTVAL (base);
+      end += INTVAL (base);
+      base = const0_rtx;
+    }
+
+ repeat:
+  if (x == 0)
+    return 0;
+
+  code = GET_CODE (x);
+  if (code == MEM)
+    {
+      register rtx addr = XEXP (x, 0);	/* Get the address.  */
+      int myend;
+
+      i = 0;
+      if (GET_CODE (addr) == REG
+	  /* qty_const is 0 when outside the cse pass;
+	     at such times, this info is not available.  */
+	  && qty_const != 0
+	  && REGNO_QTY_VALID_P (REGNO (addr))
+	  && GET_MODE (addr) == qty_mode[reg_qty[REGNO (addr)]]
+	  && qty_const[reg_qty[REGNO (addr)]] != 0)
+	addr = qty_const[reg_qty[REGNO (addr)]];
+      else if (GET_CODE (addr) == PLUS
+	       && GET_CODE (XEXP (addr, 1)) == CONST_INT
+	       && GET_CODE (XEXP (addr, 0)) == REG
+	       && qty_const != 0
+	       && REGNO_QTY_VALID_P (REGNO (XEXP (addr, 0)))
+	       && (GET_MODE (XEXP (addr, 0))
+		   == qty_mode[reg_qty[REGNO (XEXP (addr, 0))]])
+	       && qty_const[reg_qty[REGNO (XEXP (addr, 0))]])
+	{
+	  i = INTVAL (XEXP (addr, 1));
+	  addr = qty_const[reg_qty[REGNO (XEXP (addr, 0))]];
+	}
+
+    check_addr:
+      if (GET_CODE (addr) == CONST)
+	addr = XEXP (addr, 0);
+
+      /* If ADDR is BASE, or BASE plus an integer, put
+	 the integer in I.  */
+      if (GET_CODE (addr) == PLUS
+	  && XEXP (addr, 0) == base
+	  && GET_CODE (XEXP (addr, 1)) == CONST_INT)
+	i += INTVAL (XEXP (addr, 1));
+      else if (GET_CODE (addr) == LO_SUM)
+	{
+	  if (GET_CODE (base) != LO_SUM)
+	    return 1;
+	  /* The REG component of the LO_SUM is known by the
+	     const value in the XEXP part.  */
+	  addr = XEXP (addr, 1);
+	  base = XEXP (base, 1);
+	  i = 0;
+	  if (GET_CODE (base) == CONST)
+	    base = XEXP (base, 0);
+	  if (GET_CODE (base) == PLUS
+	      && GET_CODE (XEXP (base, 1)) == CONST_INT)
+	    {
+	      int tem = INTVAL (XEXP (base, 1));
+	      start += tem;
+	      end += tem;
+	      base = XEXP (base, 0);
+	    }
+	  goto check_addr;
+	}
+      else if (GET_CODE (base) == LO_SUM)
+	{
+	  base = XEXP (base, 1);
+	  if (GET_CODE (base) == CONST)
+	    base = XEXP (base, 0);
+	  if (GET_CODE (base) == PLUS
+	      && GET_CODE (XEXP (base, 1)) == CONST_INT)
+	    {
+	      int tem = INTVAL (XEXP (base, 1));
+	      start += tem;
+	      end += tem;
+	      base = XEXP (base, 0);
+	    }
+	  goto check_addr;	  
+	}
+      else if (GET_CODE (addr) == CONST_INT && base == const0_rtx)
+	i = INTVAL (addr);
+      else if (addr != base)
+	return 0;
+
+      myend = i + GET_MODE_SIZE (GET_MODE (x));
+      return myend > start && i < end;
+    }
+
+  /* X does not match, so try its subexpressions.  */
+
+  fmt = GET_RTX_FORMAT (code);
+  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+    if (fmt[i] == 'e')
+      {
+	if (i == 0)
+	  {
+	    x = XEXP (x, 0);
+	    goto repeat;
+	  }
+	else
+	  if (refers_to_mem_p (XEXP (x, i), base, start, end))
+	    return 1;
+      }
+    else if (fmt[i] == 'E')
+      {
+	int j;
+	for (j = 0; j < XVECLEN (x, i); j++)
+	  if (refers_to_mem_p (XVECEXP (x, i, j), base, start, end))
+	    return 1;
+      }
+
+  return 0;
+}
+
+/* Nonzero if X refers to memory at a varying address;
+   except that a register which has at the moment a known constant value
+   isn't considered variable.  */
+
+static int
+cse_rtx_addr_varies_p (x)
+     rtx x;
+{
+  /* We need not check for X and the equivalence class being of the same
+     mode because if X is equivalent to a constant in some mode, it
+     doesn't vary in any mode.  */
+
+  if (GET_CODE (x) == MEM
+      && GET_CODE (XEXP (x, 0)) == REG
+      && REGNO_QTY_VALID_P (REGNO (XEXP (x, 0)))
+      && GET_MODE (XEXP (x, 0)) == qty_mode[reg_qty[REGNO (XEXP (x, 0))]]
+      && qty_const[reg_qty[REGNO (XEXP (x, 0))]] != 0)
+    return 0;
+
+  if (GET_CODE (x) == MEM
+      && GET_CODE (XEXP (x, 0)) == PLUS
+      && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
+      && GET_CODE (XEXP (XEXP (x, 0), 0)) == REG
+      && REGNO_QTY_VALID_P (REGNO (XEXP (XEXP (x, 0), 0)))
+      && (GET_MODE (XEXP (XEXP (x, 0), 0))
+	  == qty_mode[reg_qty[REGNO (XEXP (XEXP (x, 0), 0))]])
+      && qty_const[reg_qty[REGNO (XEXP (XEXP (x, 0), 0))]])
+    return 0;
+
+  return rtx_addr_varies_p (x);
+}
+
+/* Canonicalize an expression:
+   replace each register reference inside it
+   with the "oldest" equivalent register.
+
+   If INSN is non-zero and we are replacing a pseudo with a hard register
+   or vice versa, verify that INSN remains valid after we make our
+   substitution.  */
+
+static rtx
+canon_reg (x, insn)
+     rtx x;
+     rtx insn;
+{
+  register int i;
+  register enum rtx_code code;
+  register char *fmt;
+
+  if (x == 0)
+    return x;
+
+  code = GET_CODE (x);
+  switch (code)
+    {
+    case PC:
+    case CC0:
+    case CONST:
+    case CONST_INT:
+    case CONST_DOUBLE:
+    case SYMBOL_REF:
+    case LABEL_REF:
+    case ADDR_VEC:
+    case ADDR_DIFF_VEC:
+      return x;
+
+    case REG:
+      {
+	register int first;
+
+	/* Never replace a hard reg, because hard regs can appear
+	   in more than one machine mode, and we must preserve the mode
+	   of each occurrence.  Also, some hard regs appear in
+	   MEMs that are shared and mustn't be altered.  Don't try to
+	   replace any reg that maps to a reg of class NO_REGS.  */
+	if (REGNO (x) < FIRST_PSEUDO_REGISTER
+	    || ! REGNO_QTY_VALID_P (REGNO (x)))
+	  return x;
+
+	first = qty_first_reg[reg_qty[REGNO (x)]];
+	return (first >= FIRST_PSEUDO_REGISTER ? regno_reg_rtx[first]
+		: REGNO_REG_CLASS (first) == NO_REGS ? x
+		: gen_rtx (REG, qty_mode[reg_qty[REGNO (x)]], first));
+      }
+    }
+
+  fmt = GET_RTX_FORMAT (code);
+  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+    {
+      register int j;
+
+      if (fmt[i] == 'e')
+	{
+	  rtx new = canon_reg (XEXP (x, i), insn);
+
+	  /* If replacing pseudo with hard reg or vice versa, ensure the
+	     insn remains valid.  */
+	  if (new && GET_CODE (new) == REG && GET_CODE (XEXP (x, i)) == REG
+	      && ((REGNO (new) < FIRST_PSEUDO_REGISTER)
+		  != (REGNO (XEXP (x, i)) < FIRST_PSEUDO_REGISTER)))
+	    validate_change (insn, &XEXP (x, i), new, 0);
+	  else
+	    XEXP (x, i) = new;
+	}
+      else if (fmt[i] == 'E')
+	for (j = 0; j < XVECLEN (x, i); j++)
+	  XVECEXP (x, i, j) = canon_reg (XVECEXP (x, i, j), insn);
+    }
+
+  return x;
+}
+
+/* LOC is a location with INSN that is an operand address (the contents of
+   a MEM).  Find the best equivalent address to use that is valid for this
+   insn.
+
+   On most CISC machines, complicated address modes are costly, and rtx_cost
+   is a good approximation for that cost.  However, most RISC machines have
+   only a few (usually only one) memory reference formats.  If an address is
+   valid at all, it is often just as cheap as any other address.  Hence, for
+   RISC machines, we use the configuration macro `ADDRESS_COST' to compare the
+   costs of various addresses.  For two addresses of equal cost, choose the one
+   with the highest `rtx_cost' value as that has the potential of eliminating
+   the most insns.  For equal costs, we choose the first in the equivalence
+   class.  Note that we ignore the fact that pseudo registers are cheaper
+   than hard registers here because we would also prefer the pseudo registers.
+  */
+
+void
+find_best_addr (insn, loc)
+     rtx insn;
+     rtx *loc;
+{
+  struct table_elt *elt, *p;
+  rtx addr = *loc;
+  int our_cost;
+  int found_better = 1;
+  int save_do_not_record = do_not_record;
+  int save_hash_arg_in_memory = hash_arg_in_memory;
+  int save_hash_arg_in_struct = hash_arg_in_struct;
+  int hash_code;
+  int addr_volatile;
+  int regno;
+
+  /* Do not try to replace constant addresses or addresses of local and
+     argument slots.  These MEM expressions are made only once and inserted
+     in many instructions, as well as being used to control symbol table
+     output.  It is not safe to clobber them.
+
+     There are some uncommon cases where the address is already in a register
+     for some reason, but we cannot take advantage of that because we have
+     no easy way to unshare the MEM.  In addition, looking up all stack
+     addresses is costly.  */
+  if ((GET_CODE (addr) == PLUS
+       && GET_CODE (XEXP (addr, 0)) == REG
+       && GET_CODE (XEXP (addr, 1)) == CONST_INT
+       && (regno = REGNO (XEXP (addr, 0)),
+	   regno == FRAME_POINTER_REGNUM || regno == ARG_POINTER_REGNUM))
+      || (GET_CODE (addr) == REG
+	  && (regno = REGNO (addr),
+	      regno == FRAME_POINTER_REGNUM || regno == ARG_POINTER_REGNUM))
+      || CONSTANT_ADDRESS_P (addr))
+    return;
+
+  /* If this address is not simply a register, try to fold it.  This will
+     sometimes simplify the expression.  Many simplifications
+     will not be valid, but some, usually applying the associative rule, will
+     be valid and produce better code.  */
+  if (GET_CODE (addr) != REG
+      && validate_change (insn, loc, fold_rtx (addr, insn), 0))
+    addr = *loc;
+	
+  /* If this address is not in the hash table, we can't do any better.
+     Also, ignore if volatile.  */
+  do_not_record = 0;
+  hash_code = HASH (addr, Pmode);
+  addr_volatile = do_not_record;
+  do_not_record = save_do_not_record;
+  hash_arg_in_memory = save_hash_arg_in_memory;
+  hash_arg_in_struct = save_hash_arg_in_struct;
+
+  if (addr_volatile)
+    return;
+
+  elt = lookup (addr, hash_code, Pmode);
+
+  if (elt == 0)
+    return;
+
+#ifndef ADDRESS_COST
+  our_cost = elt->cost;
+
+  /* Find the lowest cost below ours that works.  */
+  for (elt = elt->first_same_value; elt; elt = elt->next_same_value)
+    if (elt->cost < our_cost
+	&& (GET_CODE (elt->exp) == REG || exp_equiv_p (elt->exp, elt->exp, 1, 0))
+	&& validate_change (insn, loc, canon_reg (copy_rtx (elt->exp), 0), 0))
+      return;
+
+#else
+
+  /* We need to find the best (under the criteria documented above) entry in
+     the class that is valid.  We use the `flag' field to indicate choices
+     that were invalid and iterate until we can't find a better one that
+     hasn't already been tried.  */
+
+  for (p = elt->first_same_value; p; p = p->next_same_value)
+    p->flag = 0;
+
+  while (found_better)
+    {
+      int best_addr_cost = ADDRESS_COST (*loc);
+      int best_rtx_cost = (elt->cost + 1) >> 1;
+      struct table_elt *best_elt = elt; 
+
+      found_better = 0;
+      for (p = elt->first_same_value; p; p = p->next_same_value)
+	if (! p->flag
+	    && (GET_CODE (p->exp) == REG || exp_equiv_p (p->exp, p->exp, 1, 0))
+	    && (ADDRESS_COST (p->exp) < best_addr_cost
+		|| (ADDRESS_COST (p->exp) == best_addr_cost
+		    && (p->cost + 1) >> 1 > best_rtx_cost)))
+	  {
+	    found_better = 1;
+	    best_addr_cost = ADDRESS_COST (p->exp);
+	    best_rtx_cost = (p->cost + 1) >> 1;
+	    best_elt = p;
+	  }
+
+      if (found_better)
+	{
+	  if (validate_change (insn, loc,
+			       canon_reg (copy_rtx (best_elt->exp), 0), 0))
+	    return;
+	  else
+	    best_elt->flag = 1;
+	}
+    }
+#endif
+}
+
+/* Given an operation (CODE, *PARG1, *PARG2), where code is a comparison
+   operation (EQ, NE, GT, etc.), follow it back through the hash table and
+   what values are being compared.
+
+   *PARG1 and *PARG2 are updated to contain the rtx representing the values
+   actually being compared.  For example, if *PARG1 was (cc0) and *PARG2
+   was (const_int 0), *PARG1 and *PARG2 will be set to the objects that were
+   compared to produce cc0.
+
+   The return value is the comparison operator and is either the code of
+   A or the code corresponding to the inverse of the comparison.  */
+
+static enum rtx_code
+find_comparison_args (code, parg1, parg2)
+     enum rtx_code code;
+     rtx *parg1, *parg2;
+{
+  rtx arg1, arg2;
+
+  arg1 = *parg1, arg2 = *parg2;
+
+  /* If ARG2 is const0_rtx, see what ARG1 is equivalent to.  */
+
+  while (arg2 == const0_rtx)
+    {
+      /* Set non-zero when we find something of interest.  */
+      rtx x = 0;
+      int reverse_code = 0;
+      struct table_elt *p = 0;
+
+      /* If arg1 is a COMPARE, extract the comparison arguments from it.
+	 On machines with CC0, this is the only case that can occur, since
+	 fold_rtx will return the COMPARE or item being compared with zero
+	 when given CC0.  */
+
+      if (GET_CODE (arg1) == COMPARE && arg2 == const0_rtx)
+	x = arg1;
+
+      /* If ARG1 is a comparison operator and CODE is testing for
+	 STORE_FLAG_VALUE, get the inner arguments.  */
+
+      else if (GET_RTX_CLASS (GET_CODE (arg1)) == '<')
+	{
+	  if (code == NE || (code == LT && STORE_FLAG_VALUE == -1))
+	    x = arg1;
+	  else if (code == EQ || (code == GE && STORE_FLAG_VALUE == -1))
+	    x = arg1, reverse_code = 1;
+	}
+
+      /* ??? We could also check for
+
+	 (ne (and (eq (...) (const_int 1))) (const_int 0))
+
+	 and related forms, but let's wait until we see them occurring.  */
+
+      if (x == 0)
+	/* Look up ARG1 in the hash table and see if it has an equivalence
+	   that lets us see what is being compared.  */
+	p = lookup (arg1, safe_hash (arg1, GET_MODE (arg1)) % NBUCKETS,
+		    GET_MODE (arg1));
+      if (p) p = p->first_same_value;
+
+      for (; p; p = p->next_same_value)
+	{
+	  enum machine_mode inner_mode = GET_MODE (p->exp);
+
+	  /* If the entry isn't valid, skip it.  */
+	  if (! exp_equiv_p (p->exp, p->exp, 1, 0))
+	    continue;
+
+	  if (GET_CODE (p->exp) == COMPARE
+	      /* Another possibility is that this machine has a compare insn
+		 that includes the comparison code.  In that case, ARG1 would
+		 be equivalent to a comparison operation that would set ARG1 to
+		 either STORE_FLAG_VALUE or zero.  If this is an NE operation,
+		 ORIG_CODE is the actual comparison being done; if it is an EQ,
+		 we must reverse ORIG_CODE.  On machine with a negative value
+		 for STORE_FLAG_VALUE, also look at LT and GE operations.  */
+	      || ((code == NE
+		   || (code == LT
+		       && inner_mode != VOIDmode
+		       && GET_MODE_BITSIZE (inner_mode) <= HOST_BITS_PER_INT
+		       && (STORE_FLAG_VALUE
+			   & (1 << (GET_MODE_BITSIZE (inner_mode) - 1)))))
+		  && GET_RTX_CLASS (GET_CODE (p->exp)) == '<'))
+	    {
+	      x = p->exp;
+	      break;
+	    }
+	  else if ((code == EQ
+		    || (code == GE
+			&& inner_mode != VOIDmode
+			&& GET_MODE_BITSIZE (inner_mode) <= HOST_BITS_PER_INT
+			&& (STORE_FLAG_VALUE
+			    & (1 << (GET_MODE_BITSIZE (inner_mode) - 1)))))
+		   && GET_RTX_CLASS (GET_CODE (p->exp)) == '<')
+	    {
+	      reverse_code = 1;
+	      x = p->exp;
+	      break;
+	    }
+
+	  /* If this is fp + constant, the equivalent is a better operand since
+	     it may let us predict the value of the comparison.  */
+	  else if (NONZERO_BASE_PLUS_P (p->exp))
+	    {
+	      arg1 = p->exp;
+	      continue;
+	    }
+	}
+
+      /* If we didn't find a useful equivalence for ARG1, we are done.
+	 Otherwise, set up for the next iteration.  */
+      if (x == 0)
+	break;
+
+      arg1 = XEXP (x, 0),  arg2 = XEXP (x, 1);
+      if (GET_RTX_CLASS (GET_CODE (x)) == '<')
+	code = GET_CODE (x);
+
+      if (reverse_code)
+	code = reverse_condition (code);
+    }
+
+  /* Return our results.  */
+  *parg1 = fold_rtx (arg1, 0), *parg2 = fold_rtx (arg2, 0);
+
+  return code;
+}
+
+/* Try to simplify a unary operation CODE whose output mode is to be
+   MODE with input operand OP whose mode was originally OP_MODE.
+   Return zero if no simplification can be made.  */
+
+rtx
+simplify_unary_operation (code, mode, op, op_mode)
+     enum rtx_code code;
+     enum machine_mode mode;
+     rtx op;
+     enum machine_mode op_mode;
+{
+  register int width = GET_MODE_BITSIZE (mode);
+
+  /* The order of these tests is critical so that, for example, we don't
+     check the wrong mode (input vs. output) for a conversion operation,
+     such as FIX.  At some point, this should be simplified.  */
+
+#if !defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
+  if (code == FLOAT && GET_CODE (op) == CONST_INT)
+    {
+      REAL_VALUE_TYPE d;
+
+#ifdef REAL_ARITHMETIC
+      REAL_VALUE_FROM_INT (d, INTVAL (op), INTVAL (op) < 0 ? ~0 : 0);
+#else
+      d = (double) INTVAL (op);
+#endif
+      return CONST_DOUBLE_FROM_REAL_VALUE (d, mode);
+    }
+  else if (code == UNSIGNED_FLOAT && GET_CODE (op) == CONST_INT)
+    {
+      REAL_VALUE_TYPE d;
+
+#ifdef REAL_ARITHMETIC
+      REAL_VALUE_FROM_INT (d, INTVAL (op), 0);
+#else
+      d = (double) (unsigned int) INTVAL (op);
+#endif
+      return CONST_DOUBLE_FROM_REAL_VALUE (d, mode);
+    }
+
+  else if (code == FLOAT && GET_CODE (op) == CONST_DOUBLE
+	   && GET_MODE (op) == VOIDmode)
+    {
+      REAL_VALUE_TYPE d;
+
+#ifdef REAL_ARITHMETIC
+      REAL_VALUE_FROM_INT (d, CONST_DOUBLE_LOW (op), CONST_DOUBLE_HIGH (op));
+#else
+      if (CONST_DOUBLE_HIGH (op) < 0)
+	{
+	  d = (double) (~ CONST_DOUBLE_HIGH (op));
+	  d *= ((double) (1 << (HOST_BITS_PER_INT / 2))
+		* (double) (1 << (HOST_BITS_PER_INT / 2)));
+	  d += (double) (unsigned) (~ CONST_DOUBLE_LOW (op));
+	  d = (- d - 1.0);
+	}
+      else
+	{
+	  d = (double) CONST_DOUBLE_HIGH (op);
+	  d *= ((double) (1 << (HOST_BITS_PER_INT / 2))
+		* (double) (1 << (HOST_BITS_PER_INT / 2)));
+	  d += (double) (unsigned) CONST_DOUBLE_LOW (op);
+	}
+#endif  /* REAL_ARITHMETIC */
+      return CONST_DOUBLE_FROM_REAL_VALUE (d, mode);
+    }
+  else if (code == UNSIGNED_FLOAT && GET_CODE (op) == CONST_DOUBLE
+	   && GET_MODE (op) == VOIDmode)
+    {
+      REAL_VALUE_TYPE d;
+
+#ifdef REAL_ARITHMETIC
+      REAL_VALUE_FROM_UNSIGNED_INT (d, CONST_DOUBLE_LOW (op),
+				    CONST_DOUBLE_HIGH (op));
+#else
+      d = (double) CONST_DOUBLE_HIGH (op);
+      d *= ((double) (1 << (HOST_BITS_PER_INT / 2))
+	    * (double) (1 << (HOST_BITS_PER_INT / 2)));
+      d += (double) (unsigned) CONST_DOUBLE_LOW (op);
+#endif  /* REAL_ARITHMETIC */
+      return CONST_DOUBLE_FROM_REAL_VALUE (d, mode);
+    }
+#endif
+
+  else if (GET_CODE (op) == CONST_INT
+	   && width <= HOST_BITS_PER_INT && width > 0)
+    {
+      register int arg0 = INTVAL (op);
+      register int val;
+
+      switch (code)
+	{
+	case NOT:
+	  val = ~ arg0;
+	  break;
+
+	case NEG:
+	  val = - arg0;
+	  break;
+
+	case ABS:
+	  val = (arg0 >= 0 ? arg0 : - arg0);
+	  break;
+
+	case FFS:
+	  /* Don't use ffs here.  Instead, get low order bit and then its
+	     number.  If arg0 is zero, this will return 0, as desired.  */
+	  arg0 &= GET_MODE_MASK (mode);
+	  val = exact_log2 (arg0 & (- arg0)) + 1;
+	  break;
+
+	case TRUNCATE:
+	  val = arg0;
+	  break;
+
+	case ZERO_EXTEND:
+	  if (op_mode == VOIDmode)
+	    op_mode = mode;
+	  if (GET_MODE_BITSIZE (op_mode) == HOST_BITS_PER_INT)
+	    val = arg0;
+	  else if (GET_MODE_BITSIZE (op_mode) < HOST_BITS_PER_INT)
+	    val = arg0 & ~((-1) << GET_MODE_BITSIZE (op_mode));
+	  else
+	    return 0;
+	  break;
+
+	case SIGN_EXTEND:
+	  if (op_mode == VOIDmode)
+	    op_mode = mode;
+	  if (GET_MODE_BITSIZE (op_mode) == HOST_BITS_PER_INT)
+	    val = arg0;
+	  else if (GET_MODE_BITSIZE (op_mode) < HOST_BITS_PER_INT)
+	    {
+	      val = arg0 & ~((-1) << GET_MODE_BITSIZE (op_mode));
+	      if (val & (1 << (GET_MODE_BITSIZE (op_mode) - 1)))
+		val -= 1 << GET_MODE_BITSIZE (op_mode);
+	    }
+	  else
+	    return 0;
+	  break;
+
+	default:
+	  abort ();
+	}
+
+      /* Clear the bits that don't belong in our mode,
+	 unless they and our sign bit are all one.
+	 So we get either a reasonable negative value or a reasonable
+	 unsigned value for this mode.  */
+      if (width < HOST_BITS_PER_INT
+	  && ((val & ((-1) << (width - 1))) != ((-1) << (width - 1))))
+	val &= (1 << width) - 1;
+
+      return gen_rtx (CONST_INT, VOIDmode, val);
+    }
+
+  /* We can do some operations on integer CONST_DOUBLEs.  Also allow
+     for a DImode operation on a CONST_INT. */
+  else if (GET_MODE (op) == VOIDmode
+	   && (GET_CODE (op) == CONST_DOUBLE || GET_CODE (op) == CONST_INT))
+    {
+      int l1, h1, lv, hv;
+
+      if (GET_CODE (op) == CONST_DOUBLE)
+	l1 = CONST_DOUBLE_LOW (op), h1 = CONST_DOUBLE_HIGH (op);
+      else
+	l1 = INTVAL (op), h1 = l1 < 0 ? -1 : 0;
+
+      switch (code)
+	{
+	case NOT:
+	  lv = ~ l1;
+	  hv = ~ h1;
+	  break;
+
+	case NEG:
+	  neg_double (l1, h1, &lv, &hv);
+	  break;
+
+	case ABS:
+	  if (h1 < 0)
+	    neg_double (l1, h1, &lv, &hv);
+	  else
+	    lv = l1, hv = h1;
+	  break;
+
+	case FFS:
+	  hv = 0;
+	  if (l1 == 0)
+	    lv = HOST_BITS_PER_INT + exact_log2 (h1 & (-h1)) + 1;
+	  else
+	    lv = exact_log2 (l1 & (-l1)) + 1;
+	  break;
+
+	case TRUNCATE:
+	  if (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_INT)
+	    return gen_rtx (CONST_INT, VOIDmode, l1 & GET_MODE_MASK (mode));
+	  else
+	    return 0;
+	  break;
+
+	default:
+	  return 0;
+	}
+
+      return immed_double_const (lv, hv, mode);
+    }
+
+#if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
+  else if (GET_CODE (op) == CONST_DOUBLE
+	   && GET_MODE_CLASS (mode) == MODE_FLOAT)
+    {
+      REAL_VALUE_TYPE d;
+      jmp_buf handler;
+      rtx x;
+
+      if (setjmp (handler))
+	/* There used to be a warning here, but that is inadvisable.
+	   People may want to cause traps, and the natural way
+	   to do it should not get a warning.  */
+	return 0;
+
+      set_float_handler (handler);
+
+      REAL_VALUE_FROM_CONST_DOUBLE (d, op);
+
+      switch (code)
+	{
+	case NEG:
+	  d = REAL_VALUE_NEGATE (d);
+	  break;
+
+	case ABS:
+	  if (REAL_VALUES_LESS (d, 0.0))
+	    d = REAL_VALUE_NEGATE (d);
+	  break;
+
+	case FLOAT_TRUNCATE:
+	  d = (double) REAL_VALUE_TRUNCATE (mode, d);
+	  break;
+
+	case FLOAT_EXTEND:
+	  /* All this does is change the mode.  */
+	  break;
+
+	case FIX:
+	  d = (double) REAL_VALUE_FIX_TRUNCATE (d);
+	  break;
+
+	case UNSIGNED_FIX:
+	  d = (double) REAL_VALUE_UNSIGNED_FIX_TRUNCATE (d);
+	  break;
+
+	default:
+	  abort ();
+	}
+
+      x = immed_real_const_1 (d, mode);
+      set_float_handler (0);
+      return x;
+    }
+  else if (GET_CODE (op) == CONST_DOUBLE && GET_MODE_CLASS (mode) == MODE_INT
+	   && width <= HOST_BITS_PER_INT && width > 0)
+    {
+      REAL_VALUE_TYPE d;
+      jmp_buf handler;
+      rtx x;
+      int val;
+
+      if (setjmp (handler))
+	return 0;
+
+      set_float_handler (handler);
+
+      REAL_VALUE_FROM_CONST_DOUBLE (d, op);
+
+      switch (code)
+	{
+	case FIX:
+	  val = REAL_VALUE_FIX (d);
+	  break;
+
+	case UNSIGNED_FIX:
+	  val = REAL_VALUE_UNSIGNED_FIX (d);
+	  break;
+
+	default:
+	  abort ();
+	}
+
+      set_float_handler (0);
+
+      /* Clear the bits that don't belong in our mode,
+	 unless they and our sign bit are all one.
+	 So we get either a reasonable negative value or a reasonable
+	 unsigned value for this mode.  */
+      if (width < HOST_BITS_PER_INT
+	  && ((val & ((-1) << (width - 1))) != ((-1) << (width - 1))))
+	val &= (1 << width) - 1;
+
+      return gen_rtx (CONST_INT, VOIDmode, val);
+    }
+#endif
+  else if (GET_MODE_CLASS (mode) == MODE_INT
+	   || TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT)
+    {
+      /* There are some simplifications we can do even if the operands
+	 aren't constant, but they don't apply to floating-point
+	 unless not IEEE.  */
+      switch (code)
+	{
+	case NEG:
+	case NOT:
+	  /* (not (not X)) == X, similarly for NEG.  */
+	  if (GET_CODE (op) == code)
+	    return XEXP (op, 0);
+	  break;
+
+	case SIGN_EXTEND:
+	  /* (sign_extend (truncate (minus (label_ref L1) (label_ref L2))))
+	     becomes just the MINUS if its mode is MODE.  This allows
+	     folding switch statements on machines using casesi (such as
+	     the Vax).  */
+	  if (GET_CODE (op) == TRUNCATE
+	      && GET_MODE (XEXP (op, 0)) == mode
+	      && GET_CODE (XEXP (op, 0)) == MINUS
+	      && GET_CODE (XEXP (XEXP (op, 0), 0)) == LABEL_REF
+	      && GET_CODE (XEXP (XEXP (op, 0), 1)) == LABEL_REF)
+	    return XEXP (op, 0);
+	  break;
+	}
+
+      return 0;
+    }
+  else
+    return 0;
+}
+
+/* Simplify a binary operation CODE with result mode MODE, operating on OP0
+   and OP1.  Return 0 if no simplification is possible.
+
+   Don't use this for relational operations such as EQ or LT.
+   Use simplify_relational_operation instead.  */
+
+rtx
+simplify_binary_operation (code, mode, op0, op1)
+     enum rtx_code code;
+     enum machine_mode mode;
+     rtx op0, op1;
+{
+  register int arg0, arg1, arg0s, arg1s;
+  int val;
+  int width = GET_MODE_BITSIZE (mode);
+
+  /* Relational operations don't work here.  We must know the mode
+     of the operands in order to do the comparison correctly.
+     Assuming a full word can give incorrect results.
+     Consider comparing 128 with -128 in QImode.  */
+
+  if (GET_RTX_CLASS (code) == '<')
+    abort ();
+
+#if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
+  if (GET_MODE_CLASS (mode) == MODE_FLOAT
+      && GET_CODE (op0) == CONST_DOUBLE && GET_CODE (op1) == CONST_DOUBLE
+      && mode == GET_MODE (op0) && mode == GET_MODE (op1))
+    {
+      REAL_VALUE_TYPE f0, f1, value;
+      jmp_buf handler;
+
+      if (setjmp (handler))
+	return 0;
+
+      set_float_handler (handler);
+
+      REAL_VALUE_FROM_CONST_DOUBLE (f0, op0);
+      REAL_VALUE_FROM_CONST_DOUBLE (f1, op1);
+      f0 = REAL_VALUE_TRUNCATE (mode, f0);
+      f1 = REAL_VALUE_TRUNCATE (mode, f1);
+
+#ifdef REAL_ARITHMETIC
+      REAL_ARITHMETIC (value, code, f0, f1);
+#else
+      switch (code)
+	{
+	case PLUS:
+	  value = f0 + f1;
+	  break;
+	case MINUS:
+	  value = f0 - f1;
+	  break;
+	case MULT:
+	  value = f0 * f1;
+	  break;
+	case DIV:
+#ifndef REAL_INFINITY
+	  if (f1 == 0)
+	    abort ();
+#endif
+	  value = f0 / f1;
+	  break;
+	case SMIN:
+	  value = MIN (f0, f1);
+	  break;
+	case SMAX:
+	  value = MAX (f0, f1);
+	  break;
+	default:
+	  abort ();
+	}
+#endif
+
+      set_float_handler (0);
+      value = REAL_VALUE_TRUNCATE (mode, value);
+      return immed_real_const_1 (value, mode);
+    }
+
+  /* We can fold some multi-word operations.  */
+  else if (GET_MODE_CLASS (mode) == MODE_INT
+	   && GET_CODE (op0) == CONST_DOUBLE
+	   && (GET_CODE (op1) == CONST_DOUBLE || GET_CODE (op1) == CONST_INT))
+    {
+      int l1, l2, h1, h2, lv, hv;
+
+      l1 = CONST_DOUBLE_LOW (op0), h1 = CONST_DOUBLE_HIGH (op0);
+
+      if (GET_CODE (op1) == CONST_DOUBLE)
+	l2 = CONST_DOUBLE_LOW (op1), h2 = CONST_DOUBLE_HIGH (op1);
+      else
+	l2 = INTVAL (op1), h2 = l2 < 0 ? -1 : 0;
+
+      switch (code)
+	{
+	case MINUS:
+	  /* A - B == A + (-B).  */
+	  neg_double (l2, h2, &lv, &hv);
+	  l2 = lv, h2 = hv;
+
+	  /* .. fall through ... */
+
+	case PLUS:
+	  add_double (l1, h1, l2, h2, &lv, &hv);
+	  break;
+
+	case MULT:
+	  mul_double (l1, h1, l2, h2, &lv, &hv);
+	  break;
+
+	case DIV:  case MOD:   case UDIV:  case UMOD:
+	  /* We'd need to include tree.h to do this and it doesn't seem worth
+	     it.  */
+	  return 0;
+
+	case AND:
+	  lv = l1 & l2, hv = h1 & h2;
+	  break;
+
+	case IOR:
+	  lv = l1 | l2, hv = h1 | h2;
+	  break;
+
+	case XOR:
+	  lv = l1 ^ l2, hv = h1 ^ h2;
+	  break;
+
+	case SMIN:
+	  if (h1 < h2 || (h1 == h2 && (unsigned) l1 < (unsigned) l2))
+	    lv = l1, hv = h1;
+	  else
+	    lv = l2, hv = h2;
+	  break;
+
+	case SMAX:
+	  if (h1 > h2 || (h1 == h2 && (unsigned) l1 > (unsigned) l2))
+	    lv = l1, hv = h1;
+	  else
+	    lv = l2, hv = h2;
+	  break;
+
+	case UMIN:
+	  if ((unsigned) h1 < (unsigned) h2
+	      || (h1 == h2 && (unsigned) l1 < (unsigned) l2))
+	    lv = l1, hv = h1;
+	  else
+	    lv = l2, hv = h2;
+	  break;
+
+	case UMAX:
+	  if ((unsigned) h1 > (unsigned) h2
+	      || (h1 == h2 && (unsigned) l1 > (unsigned) l2))
+	    lv = l1, hv = h1;
+	  else
+	    lv = l2, hv = h2;
+	  break;
+
+	case LSHIFTRT:   case ASHIFTRT:
+	case ASHIFT:     case LSHIFT:
+	case ROTATE:     case ROTATERT:
+#ifdef SHIFT_COUNT_TRUNCATED
+	  l2 &= (GET_MODE_BITSIZE (mode) - 1), h2 = 0;
+#endif
+
+	  if (h2 != 0 || l2 < 0 || l2 >= GET_MODE_BITSIZE (mode))
+	    return 0;
+
+	  if (code == LSHIFTRT || code == ASHIFTRT)
+	    rshift_double (l1, h1, l2, GET_MODE_BITSIZE (mode), &lv, &hv,
+			   code == ASHIFTRT);
+	  else if (code == ASHIFT || code == LSHIFT)
+	    lshift_double (l1, h1, l2, GET_MODE_BITSIZE (mode), &lv, &hv,
+			   code == ASHIFT);
+	  else if (code == ROTATE)
+	    lrotate_double (l1, h1, l2, GET_MODE_BITSIZE (mode), &lv, &hv);
+	  else /* code == ROTATERT */
+	    rrotate_double (l1, h1, l2, GET_MODE_BITSIZE (mode), &lv, &hv);
+	  break;
+
+	default:
+	  return 0;
+	}
+
+      return immed_double_const (lv, hv, mode);
+    }
+#endif  /* not REAL_IS_NOT_DOUBLE, or REAL_ARITHMETIC */
+
+  if (GET_CODE (op0) != CONST_INT || GET_CODE (op1) != CONST_INT
+      || width > HOST_BITS_PER_INT || width == 0)
+    {
+      /* Even if we can't compute a constant result,
+	 there are some cases worth simplifying.  */
+
+      switch (code)
+	{
+	case PLUS:
+	  /* In IEEE floating point, x+0 is not the same as x.  Similarly
+	     for the other optimizations below.  */
+	  if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
+	      && GET_MODE_CLASS (mode) != MODE_INT)
+	    break;
+
+	  if (op1 == CONST0_RTX (mode))
+	    return op0;
+
+	  /* Strip off any surrounding CONSTs.  They don't matter in any of 
+	     the cases below.  */
+	  if (GET_CODE (op0) == CONST)
+	    op0 = XEXP (op0, 0);
+	  if (GET_CODE (op1) == CONST)
+	    op1 = XEXP (op1, 0);
+
+	  /* ((-a) + b) -> (b - a) and similarly for (a + (-b)) */
+	  if (GET_CODE (op0) == NEG)
+	    {
+	      rtx tem = simplify_binary_operation (MINUS, mode,
+						   op1, XEXP (op0, 0));
+	      return tem ? tem : gen_rtx (MINUS, mode, op1, XEXP (op0, 0));
+	    }
+	  else if (GET_CODE (op1) == NEG)
+	    {
+	      rtx tem = simplify_binary_operation (MINUS, mode,
+						   op0, XEXP (op1, 0));
+	      return tem ? tem : gen_rtx (MINUS, mode, op0, XEXP (op1, 0));
+	    }
+
+	  /* Don't use the associative law for floating point.
+	     The inaccuracy makes it nonassociative,
+	     and subtle programs can break if operations are associated.  */
+	  if (GET_MODE_CLASS (mode) != MODE_INT)
+	    break;
+
+	  /* (a - b) + b -> a, similarly a + (b - a) -> a */
+	  if (GET_CODE (op0) == MINUS
+	      && rtx_equal_p (XEXP (op0, 1), op1) && ! side_effects_p (op1))
+	    return XEXP (op0, 0);
+
+	  if (GET_CODE (op1) == MINUS
+	      && rtx_equal_p (XEXP (op1, 1), op0) && ! side_effects_p (op0))
+	    return XEXP (op1, 0);
+
+	  /* (c1 - a) + c2 becomes (c1 + c2) - a.  */
+	  if (GET_CODE (op1) == CONST_INT && GET_CODE (op0) == MINUS
+	      && GET_CODE (XEXP (op0, 0)) == CONST_INT)
+	    {
+	      rtx tem = simplify_binary_operation (PLUS, mode, op1,
+						   XEXP (op0, 0));
+
+	      return tem ? gen_rtx (MINUS, mode, tem, XEXP (op0, 1)) : 0;
+	    }
+
+	  /* Handle both-operands-constant cases.  */
+	  if (CONSTANT_P (op0) && CONSTANT_P (op1)
+	      && GET_CODE (op0) != CONST_DOUBLE
+	      && GET_CODE (op1) != CONST_DOUBLE
+	      && GET_MODE_CLASS (mode) == MODE_INT)
+	    {
+	      if (GET_CODE (op1) == CONST_INT)
+		return plus_constant (op0, INTVAL (op1));
+	      else if (GET_CODE (op0) == CONST_INT)
+		return plus_constant (op1, INTVAL (op0));
+	      else
+		return gen_rtx (CONST, mode,
+				gen_rtx (PLUS, mode,
+					 GET_CODE (op0) == CONST
+					 ? XEXP (op0, 0) : op0,
+					 GET_CODE (op1) == CONST
+					 ? XEXP (op1, 0) : op1));
+	    }
+	  else if (GET_CODE (op1) == CONST_INT
+		   && GET_CODE (op0) == PLUS
+		   && (CONSTANT_P (XEXP (op0, 0))
+		       || CONSTANT_P (XEXP (op0, 1))))
+	    /* constant + (variable + constant)
+	       can result if an index register is made constant.
+	       We simplify this by adding the constants.
+	       If we did not, it would become an invalid address.  */
+	    return plus_constant (op0, INTVAL (op1));
+	  break;
+
+	case COMPARE:
+#ifdef HAVE_cc0
+	  /* Convert (compare FOO (const_int 0)) to FOO unless we aren't
+	     using cc0, in which case we want to leave it as a COMPARE
+	     so we can distinguish it from a register-register-copy.
+
+	     In IEEE floating point, x-0 is not the same as x.  */
+
+	  if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
+	       || GET_MODE_CLASS (mode) == MODE_INT)
+	      && op1 == CONST0_RTX (mode))
+	    return op0;
+#else
+	  /* Do nothing here.  */
+#endif
+	  break;
+	      
+	case MINUS:
+	  /* In IEEE floating point, x-0 is not the same as x.  */
+	  if (rtx_equal_p (op0, op1)
+	      && ! side_effects_p (op0)
+	      /* We can't assume x-x is 0
+		 even with non-IEEE floating point.  */
+	      && GET_MODE_CLASS (mode) != MODE_FLOAT)
+	    return const0_rtx;
+
+	  /* Change subtraction from zero into negation.  */
+	  if (op0 == CONST0_RTX (mode))
+	    return gen_rtx (NEG, mode, op1);
+
+	  /* The remainer of these cases cannot be done for IEEE
+	     floating-point.  */
+	  if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
+	      && GET_MODE_CLASS (mode) != MODE_INT)
+	    break;
+
+	  /* Subtracting 0 has no effect.  */
+	  if (op1 == CONST0_RTX (mode))
+	    return op0;
+
+	  /* Strip off any surrounding CONSTs.  They don't matter in any of 
+	     the cases below.  */
+	  if (GET_CODE (op0) == CONST)
+	    op0 = XEXP (op0, 0);
+	  if (GET_CODE (op1) == CONST)
+	    op1 = XEXP (op1, 0);
+
+	  /* (a - (-b)) -> (a + b).  */
+	  if (GET_CODE (op1) == NEG)
+	    {
+	      rtx tem = simplify_binary_operation (PLUS, mode,
+						   op0, XEXP (op1, 0));
+	      return tem ? tem : gen_rtx (PLUS, mode, op0, XEXP (op1, 0));
+	    }
+
+	  /* Don't use the associative law for floating point.
+	     The inaccuracy makes it nonassociative,
+	     and subtle programs can break if operations are associated.  */
+	  if (GET_MODE_CLASS (mode) != MODE_INT)
+	    break;
+
+	  /* (a + b) - a -> b, and (b - (a + b))  -> -a  */
+	  if (GET_CODE (op0) == PLUS
+	      && rtx_equal_p (XEXP (op0, 0), op1)
+	      && ! side_effects_p (op1))
+	    return XEXP (op0, 1);
+	  else if (GET_CODE (op0) == PLUS
+		   && rtx_equal_p (XEXP (op0, 1), op1)
+		   && ! side_effects_p (op1))
+	    return XEXP (op0, 0);
+
+	  if (GET_CODE (op1) == PLUS
+	      && rtx_equal_p (XEXP (op1, 0), op0)
+	      && ! side_effects_p (op0))
+	    {
+	      rtx tem = simplify_unary_operation (NEG, mode, XEXP (op1, 1),
+						  mode);
+
+	      return tem ? tem : gen_rtx (NEG, mode, XEXP (op1, 1));
+	    }
+	  else if (GET_CODE (op1) == PLUS
+		   && rtx_equal_p (XEXP (op1, 1), op0)
+		   && ! side_effects_p (op0))
+	    {
+	      rtx tem = simplify_unary_operation (NEG, mode, XEXP (op1, 0),
+						  mode);
+
+	      return tem ? tem : gen_rtx (NEG, mode, XEXP (op1, 0));
+	    }
+
+	  /* a - (a - b) -> b */
+	  if (GET_CODE (op1) == MINUS && rtx_equal_p (op0, XEXP (op1, 0))
+	      && ! side_effects_p (op0))
+	    return XEXP (op1, 1);
+
+	  /* (a +/- b) - (a +/- c) can be simplified.  Do variants of
+	     this involving commutativity.  The most common case is
+	     (a + C1) - (a + C2), but it's not hard to do all the cases.  */
+	  if ((GET_CODE (op0) == PLUS || GET_CODE (op0) == MINUS)
+	      && (GET_CODE (op1) == PLUS || GET_CODE (op1) == MINUS))
+	    {
+	      rtx lhs0 = XEXP (op0, 0), lhs1 = XEXP (op0, 1);
+	      rtx rhs0 = XEXP (op1, 0), rhs1 = XEXP (op1, 1);
+	      int lhs_neg = GET_CODE (op0) == MINUS;
+	      int rhs_neg = GET_CODE (op1) == MINUS;
+	      rtx lhs = 0, rhs = 0;
+
+	      /* Set LHS and RHS to the two different terms.  */
+	      if (rtx_equal_p (lhs0, rhs0) && ! side_effects_p (lhs0))
+		lhs = lhs1, rhs = rhs1;
+	      else if (! rhs_neg && rtx_equal_p (lhs0, rhs1)
+		       && ! side_effects_p (lhs0))
+		lhs = lhs1, rhs = rhs0;
+	      else if (! lhs_neg && rtx_equal_p (lhs1, rhs0)
+		       && ! side_effects_p (lhs1))
+		lhs = lhs0, rhs = rhs1;
+	      else if (! lhs_neg && ! rhs_neg && rtx_equal_p (lhs1, rhs1)
+		       && ! side_effects_p (lhs1))
+		lhs = lhs0, rhs = rhs0;
+
+	      /* The RHS is the operand of a MINUS, so its negation
+		 status should be complemented.  */
+	      rhs_neg = ! rhs_neg;
+
+	      /* If we found two values equal, form the sum or difference
+		 of the remaining two terms.   */
+	      if (lhs)
+		{
+		  rtx tem = simplify_binary_operation (lhs_neg == rhs_neg
+						       ? PLUS : MINUS,
+						       mode,
+						       lhs_neg ? rhs : lhs,
+						       lhs_neg ? lhs : rhs);
+		  if (tem == 0)
+		    tem = gen_rtx (lhs_neg == rhs_neg
+				   ? PLUS : MINUS,
+				   mode, lhs_neg ? rhs : lhs,
+				   lhs_neg ? lhs : rhs);
+
+		  /* If both sides negated, negate result.  */
+		  if (lhs_neg && rhs_neg)
+		    {
+		      rtx tem1
+			= simplify_unary_operation (NEG, mode, tem, mode);
+		      if (tem1 == 0)
+			tem1 = gen_rtx (NEG, mode, tem);
+		      tem = tem1;
+		    }
+
+		  return tem;
+		}
+
+	      return 0;
+	    }
+
+	  /* c1 - (a + c2) becomes (c1 - c2) - a.  */
+	  if (GET_CODE (op0) == CONST_INT && GET_CODE (op1) == PLUS
+	      && GET_CODE (XEXP (op1, 1)) == CONST_INT)
+	    {
+	      rtx tem = simplify_binary_operation (MINUS, mode, op0,
+						   XEXP (op1, 1));
+
+	      return tem ? gen_rtx (MINUS, mode, tem, XEXP (op1, 0)) : 0;
+	    }
+
+	  /* c1 - (c2 - a) becomes (c1 - c2) + a.  */
+	  if (GET_CODE (op0) == CONST_INT && GET_CODE (op1) == MINUS
+	      && GET_CODE (XEXP (op1, 0)) == CONST_INT)
+	    {
+	      rtx tem = simplify_binary_operation (MINUS, mode, op0,
+						   XEXP (op1, 0));
+
+	      return (tem && GET_CODE (tem) == CONST_INT
+		      ? plus_constant (XEXP (op1, 1), INTVAL (tem))
+		      : 0);
+	    }
+
+	  /* Don't let a relocatable value get a negative coeff.  */
+	  if (GET_CODE (op1) == CONST_INT)
+	    return plus_constant (op0, - INTVAL (op1));
+	  break;
+
+	case MULT:
+	  if (op1 == constm1_rtx)
+	    {
+	      rtx tem = simplify_unary_operation (NEG, mode, op0, mode);
+
+	      return tem ? tem : gen_rtx (NEG, mode, op0);
+	    }
+
+	  /* In IEEE floating point, x*0 is not always 0.  */
+	  if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
+	       || GET_MODE_CLASS (mode) == MODE_INT)
+	      && op1 == CONST0_RTX (mode)
+	      && ! side_effects_p (op0))
+	    return op1;
+
+	  /* In IEEE floating point, x*1 is not equivalent to x for nans.
+	     However, ANSI says we can drop signals,
+	     so we can do this anyway.  */
+	  if (op1 == CONST1_RTX (mode))
+	    return op0;
+
+	  /* Convert multiply by constant power of two into shift.  */
+	  if (GET_CODE (op1) == CONST_INT
+	      && (val = exact_log2 (INTVAL (op1))) >= 0)
+	    return gen_rtx (ASHIFT, mode, op0,
+			    gen_rtx (CONST_INT, VOIDmode, val));
+
+	  if (GET_CODE (op1) == CONST_DOUBLE
+	      && GET_MODE_CLASS (GET_MODE (op1)) == MODE_FLOAT)
+	    {
+	      REAL_VALUE_TYPE d;
+	      REAL_VALUE_FROM_CONST_DOUBLE (d, op1);
+
+	      /* x*2 is x+x and x*(-1) is -x */
+	      if (REAL_VALUES_EQUAL (d, dconst2)
+		  && GET_MODE (op0) == mode)
+		return gen_rtx (PLUS, mode, op0, copy_rtx (op0));
+
+	      else if (REAL_VALUES_EQUAL (d, dconstm1)
+		       && GET_MODE (op0) == mode)
+		return gen_rtx (NEG, mode, op0);
+	    }
+	  break;
+
+	case IOR:
+	  if (op1 == const0_rtx)
+	    return op0;
+	  if (GET_CODE (op1) == CONST_INT
+	      && (INTVAL (op1) & GET_MODE_MASK (mode)) == GET_MODE_MASK (mode))
+	    return op1;
+	  if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
+	    return op0;
+	  /* A | (~A) -> -1 */
+	  if (((GET_CODE (op0) == NOT && rtx_equal_p (XEXP (op0, 0), op1))
+	       || (GET_CODE (op1) == NOT && rtx_equal_p (XEXP (op1, 0), op0)))
+	      && ! side_effects_p (op0))
+	    return constm1_rtx;
+	  break;
+
+	case XOR:
+	  if (op1 == const0_rtx)
+	    return op0;
+	  if (GET_CODE (op1) == CONST_INT
+	      && (INTVAL (op1) & GET_MODE_MASK (mode)) == GET_MODE_MASK (mode))
+	    return gen_rtx (NOT, mode, op0);
+	  if (op0 == op1 && ! side_effects_p (op0))
+	    return const0_rtx;
+	  break;
+
+	case AND:
+	  if (op1 == const0_rtx && ! side_effects_p (op0))
+	    return const0_rtx;
+	  if (GET_CODE (op1) == CONST_INT
+	      && (INTVAL (op1) & GET_MODE_MASK (mode)) == GET_MODE_MASK (mode))
+	    return op0;
+	  if (op0 == op1 && ! side_effects_p (op0))
+	    return op0;
+	  /* A & (~A) -> 0 */
+	  if (((GET_CODE (op0) == NOT && rtx_equal_p (XEXP (op0, 0), op1))
+	       || (GET_CODE (op1) == NOT && rtx_equal_p (XEXP (op1, 0), op0)))
+	      && ! side_effects_p (op0))
+	    return const0_rtx;
+	  break;
+
+	case UDIV:
+	  /* Convert divide by power of two into shift (divide by 1 handled
+	     below).  */
+	  if (GET_CODE (op1) == CONST_INT
+	      && (arg1 = exact_log2 (INTVAL (op1))) > 0)
+	    return gen_rtx (LSHIFTRT, mode, op0,
+			    gen_rtx (CONST_INT, VOIDmode, arg1));
+
+	  /* ... fall through ... */
+
+	case DIV:
+	  if (op1 == CONST1_RTX (mode))
+	    return op0;
+	  else if (op0 == CONST0_RTX (mode)
+		   && ! side_effects_p (op1))
+	    return op0;
+#if 0 /* Turned off till an expert says this is a safe thing to do.  */
+#if ! defined (REAL_IS_NOT_DOUBLE) || defined (REAL_ARITHMETIC)
+	  /* Change division by a constant into multiplication.  */
+	  else if (GET_CODE (op1) == CONST_DOUBLE
+		   && GET_MODE_CLASS (GET_MODE (op1)) == MODE_FLOAT
+		   && op1 != CONST0_RTX (mode))
+	    {
+	      REAL_VALUE_TYPE d;
+	      REAL_VALUE_FROM_CONST_DOUBLE (d, op1);
+	      if (REAL_VALUES_EQUAL (d, dconst0))
+		abort();
+#if defined (REAL_ARITHMETIC)
+	      REAL_ARITHMETIC (d, RDIV_EXPR, dconst1, d);
+	      return gen_rtx (MULT, mode, op0, 
+			      CONST_DOUBLE_FROM_REAL_VALUE (d, mode));
+#else
+	      return gen_rtx (MULT, mode, op0, 
+			      CONST_DOUBLE_FROM_REAL_VALUE (1./d, mode));
+	    }
+#endif
+#endif
+#endif
+	  break;
+
+	case UMOD:
+	  /* Handle modulus by power of two (mod with 1 handled below).  */
+	  if (GET_CODE (op1) == CONST_INT
+	      && exact_log2 (INTVAL (op1)) > 0)
+	    return gen_rtx (AND, mode, op0, 
+			    gen_rtx (CONST_INT, VOIDmode, INTVAL (op1) - 1));
+
+	  /* ... fall through ... */
+
+	case MOD:
+	  if ((op0 == const0_rtx || op1 == const1_rtx)
+	      && ! side_effects_p (op0) && ! side_effects_p (op1))
+	    return const0_rtx;
+	  break;
+
+	case ROTATERT:
+	case ROTATE:
+	  /* Rotating ~0 always results in ~0.  */
+	  if (GET_CODE (op0) == CONST_INT && width <= HOST_BITS_PER_INT
+	      && INTVAL (op0) == GET_MODE_MASK (mode)
+	      && ! side_effects_p (op1))
+	    return op0;
+
+	  /* ... fall through ... */
+
+	case LSHIFT:
+	case ASHIFT:
+	case ASHIFTRT:
+	case LSHIFTRT:
+	  if (op1 == const0_rtx)
+	    return op0;
+	  if (op0 == const0_rtx && ! side_effects_p (op1))
+	    return op0;
+	  break;
+
+	case SMIN:
+	  if (width <= HOST_BITS_PER_INT && GET_CODE (op1) == CONST_INT 
+	      && INTVAL (op1) == 1 << (width -1)
+	      && ! side_effects_p (op0))
+	    return op1;
+	  else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
+	    return op0;
+	  break;
+	   
+	case SMAX:
+	  if (width <= HOST_BITS_PER_INT && GET_CODE (op1) == CONST_INT
+	      && INTVAL (op1) == GET_MODE_MASK (mode) >> 1
+	      && ! side_effects_p (op0))
+	    return op1;
+	  else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
+	    return op0;
+	  break;
+
+	case UMIN:
+	  if (op1 == const0_rtx && ! side_effects_p (op0))
+	    return op1;
+	  else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
+	    return op0;
+	  break;
+	    
+	case UMAX:
+	  if (op1 == constm1_rtx && ! side_effects_p (op0))
+	    return op1;
+	  else if (rtx_equal_p (op0, op1) && ! side_effects_p (op0))
+	    return op0;
+	  break;
+
+	default:
+	  abort ();
+	}
+      
+      return 0;
+    }
+
+  /* Get the integer argument values in two forms:
+     zero-extended in ARG0, ARG1 and sign-extended in ARG0S, ARG1S.  */
+
+  arg0 = INTVAL (op0);
+  arg1 = INTVAL (op1);
+
+  if (width < HOST_BITS_PER_INT)
+    {
+      arg0 &= (1 << width) - 1;
+      arg1 &= (1 << width) - 1;
+
+      arg0s = arg0;
+      if (arg0s & (1 << (width - 1)))
+	arg0s |= ((-1) << width);
+
+      arg1s = arg1;
+      if (arg1s & (1 << (width - 1)))
+	arg1s |= ((-1) << width);
+    }
+  else
+    {
+      arg0s = arg0;
+      arg1s = arg1;
+    }
+
+  /* Compute the value of the arithmetic.  */
+
+  switch (code)
+    {
+    case PLUS:
+      val = arg0 + arg1;
+      break;
+
+    case MINUS:
+      val = arg0 - arg1;
+      break;
+
+    case MULT:
+      val = arg0s * arg1s;
+      break;
+
+    case DIV:
+      if (arg1s == 0)
+	return 0;
+      val = arg0s / arg1s;
+      break;
+
+    case MOD:
+      if (arg1s == 0)
+	return 0;
+      val = arg0s % arg1s;
+      break;
+
+    case UDIV:
+      if (arg1 == 0)
+	return 0;
+      val = (unsigned) arg0 / arg1;
+      break;
+
+    case UMOD:
+      if (arg1 == 0)
+	return 0;
+      val = (unsigned) arg0 % arg1;
+      break;
+
+    case AND:
+      val = arg0 & arg1;
+      break;
+
+    case IOR:
+      val = arg0 | arg1;
+      break;
+
+    case XOR:
+      val = arg0 ^ arg1;
+      break;
+
+    case LSHIFTRT:
+      /* If shift count is undefined, don't fold it; let the machine do
+	 what it wants.  But truncate it if the machine will do that.  */
+      if (arg1 < 0)
+	return 0;
+
+#ifdef SHIFT_COUNT_TRUNCATED
+      arg1 &= (BITS_PER_WORD - 1);
+#endif
+
+      if (arg1 >= width)
+	return 0;
+
+      val = ((unsigned) arg0) >> arg1;
+      break;
+
+    case ASHIFT:
+    case LSHIFT:
+      if (arg1 < 0)
+	return 0;
+
+#ifdef SHIFT_COUNT_TRUNCATED
+      arg1 &= (BITS_PER_WORD - 1);
+#endif
+
+      if (arg1 >= width)
+	return 0;
+
+      val = ((unsigned) arg0) << arg1;
+      break;
+
+    case ASHIFTRT:
+      if (arg1 < 0)
+	return 0;
+
+#ifdef SHIFT_COUNT_TRUNCATED
+      arg1 &= (BITS_PER_WORD - 1);
+#endif
+
+      if (arg1 >= width)
+	return 0;
+
+      val = arg0s >> arg1;
+      break;
+
+    case ROTATERT:
+      if (arg1 < 0)
+	return 0;
+
+      arg1 %= width;
+      val = ((((unsigned) arg0) << (width - arg1))
+	     | (((unsigned) arg0) >> arg1));
+      break;
+
+    case ROTATE:
+      if (arg1 < 0)
+	return 0;
+
+      arg1 %= width;
+      val = ((((unsigned) arg0) << arg1)
+	     | (((unsigned) arg0) >> (width - arg1)));
+      break;
+
+    case COMPARE:
+      /* Do nothing here.  */
+      return 0;
+
+    default:
+      abort ();
+    }
+
+  /* Clear the bits that don't belong in our mode, unless they and our sign
+     bit are all one.  So we get either a reasonable negative value or a
+     reasonable unsigned value for this mode.  */
+  if (width < HOST_BITS_PER_INT
+      && ((val & ((-1) << (width - 1))) != ((-1) << (width - 1))))
+    val &= (1 << width) - 1;
+  
+  return gen_rtx (CONST_INT, VOIDmode, val);
+}
+
+/* Like simplify_binary_operation except used for relational operators.
+   MODE is the mode of the operands, not that of the result.  */
+
+rtx
+simplify_relational_operation (code, mode, op0, op1)
+     enum rtx_code code;
+     enum machine_mode mode;
+     rtx op0, op1;
+{
+  register int arg0, arg1, arg0s, arg1s;
+  int val;
+  int width = GET_MODE_BITSIZE (mode);
+
+  /* If op0 is a compare, extract the comparison arguments from it.  */
+  if (GET_CODE (op0) == COMPARE && op1 == const0_rtx)
+    op1 = XEXP (op0, 1), op0 = XEXP (op0, 0);
+
+  if (GET_CODE (op0) != CONST_INT || GET_CODE (op1) != CONST_INT
+      || width > HOST_BITS_PER_INT || width == 0)
+    {
+      /* Even if we can't compute a constant result,
+	 there are some cases worth simplifying.  */
+
+      /* For non-IEEE floating-point, if the two operands are equal, we know
+	 the result.  */
+      if (rtx_equal_p (op0, op1)
+	  && (TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
+	      || GET_MODE_CLASS (GET_MODE (op0)) != MODE_FLOAT))
+	return (code == EQ || code == GE || code == LE || code == LEU
+		|| code == GEU) ? const_true_rtx : const0_rtx;
+      else if (GET_CODE (op0) == CONST_DOUBLE
+	       && GET_CODE (op1) == CONST_DOUBLE
+	       && GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
+	{
+	  REAL_VALUE_TYPE d0, d1;
+	  int value;
+	  jmp_buf handler;
+	  int op0lt, op1lt, equal;
+
+	  if (setjmp (handler))
+	    return 0;
+
+	  set_float_handler (handler);
+	  REAL_VALUE_FROM_CONST_DOUBLE (d0, op0);
+	  REAL_VALUE_FROM_CONST_DOUBLE (d1, op1);
+	  equal = REAL_VALUES_EQUAL (d0, d1);
+	  op0lt = REAL_VALUES_LESS (d0, d1);
+	  op1lt = REAL_VALUES_LESS (d1, d0);
+	  set_float_handler (0);
+
+	  switch (code)
+	    {
+	    case EQ:
+	      return equal ? const_true_rtx : const0_rtx;
+	    case NE:
+	      return !equal ? const_true_rtx : const0_rtx;
+	    case LE:
+	      return equal || op0lt ? const_true_rtx : const0_rtx;
+	    case LT:
+	      return op0lt ? const_true_rtx : const0_rtx;
+	    case GE:
+	      return equal || op1lt ? const_true_rtx : const0_rtx;
+	    case GT:
+	      return op1lt ? const_true_rtx : const0_rtx;
+	    }
+	}
+      
+      switch (code)
+	{
+	case EQ:
+	  {
+#if 0
+	    /* We can't make this assumption due to #pragma weak */
+	    if (CONSTANT_P (op0) && op1 == const0_rtx)
+	      return const0_rtx;
+#endif
+	    if (NONZERO_BASE_PLUS_P (op0) && op1 == const0_rtx)
+	      return const0_rtx;
+	    break;
+	  }
+
+	case NE:
+#if 0
+	  /* We can't make this assumption due to #pragma weak */
+	  if (CONSTANT_P (op0) && op1 == const0_rtx)
+	    return const_true_rtx;
+#endif
+	  if (NONZERO_BASE_PLUS_P (op0) && op1 == const0_rtx)
+	    return const_true_rtx;
+	  break;
+
+	case GEU:
+	  /* Unsigned values are never negative, but we must be sure we are
+	     actually comparing a value, not a CC operand.  */
+	  if (op1 == const0_rtx
+	      && GET_MODE_CLASS (mode) == MODE_INT)
+	    return const_true_rtx;
+	  break;
+
+	case LTU:
+	  if (op1 == const0_rtx
+	      && GET_MODE_CLASS (mode) == MODE_INT)
+	    return const0_rtx;
+	  break;
+
+	case LEU:
+	  /* Unsigned values are never greater than the largest
+	     unsigned value.  */
+	  if (GET_CODE (op1) == CONST_INT
+	      && INTVAL (op1) == GET_MODE_MASK (mode)
+	      && GET_MODE_CLASS (mode) == MODE_INT)
+	    return const_true_rtx;
+	  break;
+
+	case GTU:
+	  if (GET_CODE (op1) == CONST_INT
+	      && INTVAL (op1) == GET_MODE_MASK (mode)
+	      && GET_MODE_CLASS (mode) == MODE_INT)
+	    return const0_rtx;
+	  break;
+	}
+
+      return 0;
+    }
+
+  /* Get the integer argument values in two forms:
+     zero-extended in ARG0, ARG1 and sign-extended in ARG0S, ARG1S.  */
+
+  arg0 = INTVAL (op0);
+  arg1 = INTVAL (op1);
+
+  if (width < HOST_BITS_PER_INT)
+    {
+      arg0 &= (1 << width) - 1;
+      arg1 &= (1 << width) - 1;
+
+      arg0s = arg0;
+      if (arg0s & (1 << (width - 1)))
+	arg0s |= ((-1) << width);
+
+      arg1s = arg1;
+      if (arg1s & (1 << (width - 1)))
+	arg1s |= ((-1) << width);
+    }
+  else
+    {
+      arg0s = arg0;
+      arg1s = arg1;
+    }
+
+  /* Compute the value of the arithmetic.  */
+
+  switch (code)
+    {
+    case NE:
+      val = arg0 != arg1 ? STORE_FLAG_VALUE : 0;
+      break;
+
+    case EQ:
+      val = arg0 == arg1 ? STORE_FLAG_VALUE : 0;
+      break;
+
+    case LE:
+      val = arg0s <= arg1s ? STORE_FLAG_VALUE : 0;
+      break;
+
+    case LT:
+      val = arg0s < arg1s ? STORE_FLAG_VALUE : 0;
+      break;
+
+    case GE:
+      val = arg0s >= arg1s ? STORE_FLAG_VALUE : 0;
+      break;
+
+    case GT:
+      val = arg0s > arg1s ? STORE_FLAG_VALUE : 0;
+      break;
+
+    case LEU:
+      val = ((unsigned) arg0) <= ((unsigned) arg1) ? STORE_FLAG_VALUE : 0;
+      break;
+
+    case LTU:
+      val = ((unsigned) arg0) < ((unsigned) arg1) ? STORE_FLAG_VALUE : 0;
+      break;
+
+    case GEU:
+      val = ((unsigned) arg0) >= ((unsigned) arg1) ? STORE_FLAG_VALUE : 0;
+      break;
+
+    case GTU:
+      val = ((unsigned) arg0) > ((unsigned) arg1) ? STORE_FLAG_VALUE : 0;
+      break;
+
+    default:
+      abort ();
+    }
+
+  /* Clear the bits that don't belong in our mode, unless they and our sign
+     bit are all one.  So we get either a reasonable negative value or a
+     reasonable unsigned value for this mode.  */
+  if (width < HOST_BITS_PER_INT
+      && ((val & ((-1) << (width - 1))) != ((-1) << (width - 1))))
+    val &= (1 << width) - 1;
+  
+  return gen_rtx (CONST_INT, VOIDmode, val);
+}
+
+/* Simplify CODE, an operation with result mode MODE and three operands,
+   OP0, OP1, and OP2.  OP0_MODE was the mode of OP0 before it became
+   a constant.  Return 0 if no simplifications is possible.  */
+
+rtx
+simplify_ternary_operation (code, mode, op0_mode, op0, op1, op2)
+     enum rtx_code code;
+     enum machine_mode mode, op0_mode;
+     rtx op0, op1, op2;
+{
+  int width = GET_MODE_BITSIZE (mode);
+
+  /* VOIDmode means "infinite" precision.  */
+  if (width == 0)
+    width = HOST_BITS_PER_INT;
+
+  switch (code)
+    {
+    case SIGN_EXTRACT:
+    case ZERO_EXTRACT:
+      if (GET_CODE (op0) == CONST_INT
+	  && GET_CODE (op1) == CONST_INT
+	  && GET_CODE (op2) == CONST_INT
+	  && INTVAL (op1) + INTVAL (op2) <= GET_MODE_BITSIZE (op0_mode)
+	  && width <= HOST_BITS_PER_INT)
+	{
+	  /* Extracting a bit-field from a constant */
+	  int val = INTVAL (op0);
+
+#if BITS_BIG_ENDIAN
+	  val >>= (GET_MODE_BITSIZE (op0_mode) - INTVAL (op2) - INTVAL (op1));
+#else
+	  val >>= INTVAL (op2);
+#endif
+	  if (HOST_BITS_PER_INT != INTVAL (op1))
+	    {
+	      /* First zero-extend.  */
+	      val &= (1 << INTVAL (op1)) - 1;
+	      /* If desired, propagate sign bit.  */
+	      if (code == SIGN_EXTRACT && (val & (1 << (INTVAL (op1) - 1))))
+		val |= ~ (1 << INTVAL (op1));
+	    }
+
+	  /* Clear the bits that don't belong in our mode,
+	     unless they and our sign bit are all one.
+	     So we get either a reasonable negative value or a reasonable
+	     unsigned value for this mode.  */
+	  if (width < HOST_BITS_PER_INT
+	      && ((val & ((-1) << (width - 1))) != ((-1) << (width - 1))))
+	    val &= (1 << width) - 1;
+
+	  return gen_rtx (CONST_INT, VOIDmode, val);
+	}
+      break;
+
+    case IF_THEN_ELSE:
+      if (GET_CODE (op0) == CONST_INT)
+	return op0 != const0_rtx ? op1 : op2;
+      break;
+
+    default:
+      abort ();
+    }
+
+  return 0;
+}
+
+/* If X is a nontrivial arithmetic operation on an argument
+   for which a constant value can be determined, return
+   the result of operating on that value, as a constant.
+   Otherwise, return X, possibly with one or more operands
+   modified by recursive calls to this function.
+
+   If X is a register whose contents are known, we do NOT
+   return those contents.  This is because an instruction that
+   uses a register is usually faster than one that uses a constant.
+
+   INSN is the insn that we may be modifying.  If it is 0, make a copy
+   of X before modifying it.  */
+
+static rtx
+fold_rtx (x, insn)
+     rtx x;
+     rtx insn;    
+{
+  register enum rtx_code code;
+  register enum machine_mode mode;
+  register char *fmt;
+  register int i, val;
+  rtx new = 0;
+  int copied = 0;
+  int must_swap = 0;
+
+  /* Folded equivalents of first two operands of X.  */
+  rtx folded_arg0;
+  rtx folded_arg1;
+
+  /* Constant equivalents of first three operands of X;
+     0 when no such equivalent is known.  */
+  rtx const_arg0;
+  rtx const_arg1;
+  rtx const_arg2;
+
+  /* The mode of the first operand of X.  We need this for sign and zero
+     extends.  */
+  enum machine_mode mode_arg0;
+
+  if (x == 0)
+    return x;
+
+  mode = GET_MODE (x);
+  code = GET_CODE (x);
+  switch (code)
+    {
+    case CONST:
+    case CONST_INT:
+    case CONST_DOUBLE:
+    case SYMBOL_REF:
+    case LABEL_REF:
+    case REG:
+      /* No use simplifying an EXPR_LIST
+	 since they are used only for lists of args
+	 in a function call's REG_EQUAL note.  */
+    case EXPR_LIST:
+      return x;
+
+#ifdef HAVE_cc0
+    case CC0:
+      return prev_insn_cc0;
+#endif
+
+    case PC:
+      /* If the next insn is a CODE_LABEL followed by a jump table,
+	 PC's value is a LABEL_REF pointing to that label.  That
+	 lets us fold switch statements on the Vax.  */
+      if (insn && GET_CODE (insn) == JUMP_INSN)
+	{
+	  rtx next = next_nonnote_insn (insn);
+
+	  if (next && GET_CODE (next) == CODE_LABEL
+	      && NEXT_INSN (next) != 0
+	      && GET_CODE (NEXT_INSN (next)) == JUMP_INSN
+	      && (GET_CODE (PATTERN (NEXT_INSN (next))) == ADDR_VEC
+		  || GET_CODE (PATTERN (NEXT_INSN (next))) == ADDR_DIFF_VEC))
+	    return gen_rtx (LABEL_REF, Pmode, next);
+	}
+      break;
+
+    case SUBREG:
+      /* If this is a single word of a multi-word value, see if we previously
+	 assigned a value to that word.  */
+      if (GET_MODE_SIZE (mode) <= UNITS_PER_WORD
+	  && GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))) > UNITS_PER_WORD
+	  && (new = lookup_as_function (x, CONST_INT)) != 0)
+	return new;
+
+      /* Fold SUBREG_REG.  If it changed, see if we can simplify the SUBREG.
+	 We might be able to if the SUBREG is extracting a single word in an
+	 integral mode or extracting the low part.  */
+
+      folded_arg0 = fold_rtx (SUBREG_REG (x), insn);
+      const_arg0 = equiv_constant (folded_arg0);
+      if (const_arg0)
+	folded_arg0 = const_arg0;
+
+      if (folded_arg0 != SUBREG_REG (x))
+	{
+	  new = 0;
+
+	  if (GET_MODE_CLASS (mode) == MODE_INT
+	      && GET_MODE_SIZE (mode) == UNITS_PER_WORD
+	      && GET_MODE (SUBREG_REG (x)) != VOIDmode)
+	    new = operand_subword (folded_arg0, SUBREG_WORD (x), 0,
+				   GET_MODE (SUBREG_REG (x)));
+	  if (new == 0 && subreg_lowpart_p (x))
+	    new = gen_lowpart_if_possible (mode, folded_arg0);
+	  if (new)
+	    return new;
+	}
+      return x;
+
+    case NOT:
+    case NEG:
+      /* If we have (NOT Y), see if Y is known to be (NOT Z).
+	 If so, (NOT Y) simplifies to Z.  Similarly for NEG.  */
+      new = lookup_as_function (XEXP (x, 0), code);
+      if (new)
+	return fold_rtx (copy_rtx (XEXP (new, 0)), insn);
+      break;
+      
+    case MEM:
+      /* If we are not actually processing an insn, don't try to find the
+	 best address.  Not only don't we care, but we could modify the
+	 MEM in an invalid way since we have no insn to validate against.  */
+      if (insn != 0)
+	find_best_addr (insn, &XEXP (x, 0));
+
+      {
+	/* Even if we don't fold in the insn itself,
+	   we can safely do so here, in hopes of getting a constant.  */
+	rtx addr = fold_rtx (XEXP (x, 0), 0);
+	rtx base = 0;
+	int offset = 0;
+
+	if (GET_CODE (addr) == REG
+	    && REGNO_QTY_VALID_P (REGNO (addr))
+	    && GET_MODE (addr) == qty_mode[reg_qty[REGNO (addr)]]
+	    && qty_const[reg_qty[REGNO (addr)]] != 0)
+	  addr = qty_const[reg_qty[REGNO (addr)]];
+
+	/* If address is constant, split it into a base and integer offset.  */
+	if (GET_CODE (addr) == SYMBOL_REF || GET_CODE (addr) == LABEL_REF)
+	  base = addr;
+	else if (GET_CODE (addr) == CONST && GET_CODE (XEXP (addr, 0)) == PLUS
+		 && GET_CODE (XEXP (XEXP (addr, 0), 1)) == CONST_INT)
+	  {
+	    base = XEXP (XEXP (addr, 0), 0);
+	    offset = INTVAL (XEXP (XEXP (addr, 0), 1));
+	  }
+	else if (GET_CODE (addr) == LO_SUM
+		 && GET_CODE (XEXP (addr, 1)) == SYMBOL_REF)
+	  base = XEXP (addr, 1);
+
+	/* If this is a constant pool reference, we can fold it into its
+	   constant to allow better value tracking.  */
+	if (base && GET_CODE (base) == SYMBOL_REF
+	    && CONSTANT_POOL_ADDRESS_P (base))
+	  {
+	    rtx constant = get_pool_constant (base);
+	    enum machine_mode const_mode = get_pool_mode (base);
+	    rtx new;
+
+	    if (CONSTANT_P (constant) && GET_CODE (constant) != CONST_INT)
+	      constant_pool_entries_cost = COST (constant);
+
+	    /* If we are loading the full constant, we have an equivalence.  */
+	    if (offset == 0 && mode == const_mode)
+	      return constant;
+
+	    /* If this actually isn't a constant (wierd!), we can't do
+	       anything.  Otherwise, handle the two most common cases:
+	       extracting a word from a multi-word constant, and extracting
+	       the low-order bits.  Other cases don't seem common enough to
+	       worry about.  */
+	    if (! CONSTANT_P (constant))
+	      return x;
+
+	    if (GET_MODE_CLASS (mode) == MODE_INT
+		&& GET_MODE_SIZE (mode) == UNITS_PER_WORD
+		&& offset % UNITS_PER_WORD == 0
+		&& (new = operand_subword (constant,
+					   offset / UNITS_PER_WORD,
+					   0, const_mode)) != 0)
+	      return new;
+
+	    if (((BYTES_BIG_ENDIAN
+		  && offset == GET_MODE_SIZE (GET_MODE (constant)) - 1)
+		 || (! BYTES_BIG_ENDIAN && offset == 0))
+		&& (new = gen_lowpart_if_possible (mode, constant)) != 0)
+	      return new;
+	  }
+
+	/* If this is a reference to a label at a known position in a jump
+	   table, we also know its value.  */
+	if (base && GET_CODE (base) == LABEL_REF)
+	  {
+	    rtx label = XEXP (base, 0);
+	    rtx table_insn = NEXT_INSN (label);
+	    
+	    if (table_insn && GET_CODE (table_insn) == JUMP_INSN
+		&& GET_CODE (PATTERN (table_insn)) == ADDR_VEC)
+	      {
+		rtx table = PATTERN (table_insn);
+
+		if (offset >= 0
+		    && (offset / GET_MODE_SIZE (GET_MODE (table))
+			< XVECLEN (table, 0)))
+		  return XVECEXP (table, 0,
+				  offset / GET_MODE_SIZE (GET_MODE (table)));
+	      }
+	    if (table_insn && GET_CODE (table_insn) == JUMP_INSN
+		&& GET_CODE (PATTERN (table_insn)) == ADDR_DIFF_VEC)
+	      {
+		rtx table = PATTERN (table_insn);
+
+		if (offset >= 0
+		    && (offset / GET_MODE_SIZE (GET_MODE (table))
+			< XVECLEN (table, 1)))
+		  {
+		    offset /= GET_MODE_SIZE (GET_MODE (table));
+		    new = gen_rtx (MINUS, Pmode, XVECEXP (table, 1, offset),
+				   XEXP (table, 0));
+
+		    if (GET_MODE (table) != Pmode)
+		      new = gen_rtx (TRUNCATE, GET_MODE (table), new);
+
+		    return new;
+		  }
+	      }
+	  }
+
+	return x;
+      }
+    }
+
+  const_arg0 = 0;
+  const_arg1 = 0;
+  const_arg2 = 0;
+  mode_arg0 = VOIDmode;
+
+  /* Try folding our operands.
+     Then see which ones have constant values known.  */
+
+  fmt = GET_RTX_FORMAT (code);
+  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+    if (fmt[i] == 'e')
+      {
+	rtx arg = XEXP (x, i);
+	rtx folded_arg = arg, const_arg = 0;
+	enum machine_mode mode_arg = GET_MODE (arg);
+	rtx cheap_arg, expensive_arg;
+	rtx replacements[2];
+	int j;
+
+	/* Most arguments are cheap, so handle them specially.  */
+	switch (GET_CODE (arg))
+	  {
+	  case REG:
+	    /* This is the same as calling equiv_constant; it is duplicated
+	       here for speed.  */
+	    if (REGNO_QTY_VALID_P (REGNO (arg))
+		&& qty_const[reg_qty[REGNO (arg)]] != 0
+		&& GET_CODE (qty_const[reg_qty[REGNO (arg)]]) != REG
+		&& GET_CODE (qty_const[reg_qty[REGNO (arg)]]) != PLUS)
+	      const_arg
+		= gen_lowpart_if_possible (GET_MODE (arg),
+					   qty_const[reg_qty[REGNO (arg)]]);
+	    break;
+
+	  case CONST:
+	  case CONST_INT:
+	  case SYMBOL_REF:
+	  case LABEL_REF:
+	  case CONST_DOUBLE:
+	    const_arg = arg;
+	    break;
+
+#ifdef HAVE_cc0
+	  case CC0:
+	    folded_arg = prev_insn_cc0;
+	    mode_arg = prev_insn_cc0_mode;
+	    const_arg = equiv_constant (folded_arg);
+	    break;
+#endif
+
+	  default:
+	    folded_arg = fold_rtx (arg, insn);
+	    const_arg = equiv_constant (folded_arg);
+	  }
+
+	/* For the first three operands, see if the operand
+	   is constant or equivalent to a constant.  */
+	switch (i)
+	  {
+	  case 0:
+	    folded_arg0 = folded_arg;
+	    const_arg0 = const_arg;
+	    mode_arg0 = mode_arg;
+	    break;
+	  case 1:
+	    folded_arg1 = folded_arg;
+	    const_arg1 = const_arg;
+	    break;
+	  case 2:
+	    const_arg2 = const_arg;
+	    break;
+	  }
+
+	/* Pick the least expensive of the folded argument and an
+	   equivalent constant argument.  */
+	if (const_arg == 0 || const_arg == folded_arg
+	    || COST (const_arg) > COST (folded_arg))
+	  cheap_arg = folded_arg, expensive_arg = const_arg;
+	else
+	  cheap_arg = const_arg, expensive_arg = folded_arg;
+
+	/* Try to replace the operand with the cheapest of the two
+	   possibilities.  If it doesn't work and this is either of the first
+	   two operands of a commutative operation, try swapping them.
+	   If THAT fails, try the more expensive, provided it is cheaper
+	   than what is already there.  */
+
+	if (cheap_arg == XEXP (x, i))
+	  continue;
+
+	if (insn == 0 && ! copied)
+	  {
+	    x = copy_rtx (x);
+	    copied = 1;
+	  }
+
+	replacements[0] = cheap_arg, replacements[1] = expensive_arg;
+	for (j = 0;
+	     j < 2 && replacements[j]
+	     && COST (replacements[j]) < COST (XEXP (x, i));
+	     j++)
+	  {
+	    if (validate_change (insn, &XEXP (x, i), replacements[j], 0))
+	      break;
+
+	    if (code == NE || code == EQ || GET_RTX_CLASS (code) == 'c')
+	      {
+		validate_change (insn, &XEXP (x, i), XEXP (x, 1 - i), 1);
+		validate_change (insn, &XEXP (x, 1 - i), replacements[j], 1);
+
+		if (apply_change_group ())
+		  {
+		    /* Swap them back to be invalid so that this loop can
+		       continue and flag them to be swapped back later.  */
+		    rtx tem;
+
+		    tem = XEXP (x, 0); XEXP (x, 0) = XEXP (x, 1);
+				       XEXP (x, 1) = tem;
+		    must_swap = 1;
+		    break;
+		  }
+	      }
+	  }
+      }
+
+    else if (fmt[i] == 'E')
+      /* Don't try to fold inside of a vector of expressions.
+	 Doing nothing is harmless.  */
+      ;
+
+  /* If a commutative operation, place a constant integer as the second
+     operand unless the first operand is also a constant integer.  Otherwise,
+     place any constant second unless the first operand is also a constant.  */
+
+  if (code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
+    {
+      if (must_swap || (const_arg0
+	  		&& (const_arg1 == 0
+	      		    || (GET_CODE (const_arg0) == CONST_INT
+			        && GET_CODE (const_arg1) != CONST_INT))))
+	{
+	  register rtx tem = XEXP (x, 0);
+
+	  if (insn == 0 && ! copied)
+	    {
+	      x = copy_rtx (x);
+	      copied = 1;
+	    }
+
+	  validate_change (insn, &XEXP (x, 0), XEXP (x, 1), 1);
+	  validate_change (insn, &XEXP (x, 1), tem, 1);
+	  if (apply_change_group ())
+	    {
+	      tem = const_arg0, const_arg0 = const_arg1, const_arg1 = tem;
+	      tem = folded_arg0, folded_arg0 = folded_arg1, folded_arg1 = tem;
+	    }
+	}
+    }
+
+  /* If X is an arithmetic operation, see if we can simplify it.  */
+
+  switch (GET_RTX_CLASS (code))
+    {
+    case '1':
+      new = simplify_unary_operation (code, mode,
+				      const_arg0 ? const_arg0 : folded_arg0,
+				      mode_arg0);
+      break;
+      
+    case '<':
+      /* See what items are actually being compared and set FOLDED_ARG[01]
+	 to those values and CODE to the actual comparison code.  If any are
+	 constant, set CONST_ARG0 and CONST_ARG1 appropriately.  We needn't
+	 do anything if both operands are already known to be constant.  */
+
+      if (const_arg0 == 0 || const_arg1 == 0)
+	{
+	  struct table_elt *p0, *p1;
+
+	  code = find_comparison_args (code, &folded_arg0, &folded_arg1);
+	  const_arg0 = equiv_constant (folded_arg0);
+	  const_arg1 = equiv_constant (folded_arg1);
+
+	  /* Get a mode from the values actually being compared, or from the
+	     old value of MODE_ARG0 if both are constants.  If the resulting
+	     mode is VOIDmode or a MODE_CC mode, we don't know what kinds
+	     of things are being compared, so we can't do anything with this
+	     comparison.  */
+
+	  if (GET_MODE (folded_arg0) != VOIDmode
+	      && GET_MODE_CLASS (GET_MODE (folded_arg0)) != MODE_CC)
+	    mode_arg0 = GET_MODE (folded_arg0);
+
+	  else if (GET_MODE (folded_arg1) != VOIDmode
+		   && GET_MODE_CLASS (GET_MODE (folded_arg1)) != MODE_CC)
+	    mode_arg0 = GET_MODE (folded_arg1);
+
+	  if (mode_arg0 == VOIDmode || GET_MODE_CLASS (mode_arg0) == MODE_CC)
+	    break;
+
+	  /* If we do not now have two constants being compared, see if we
+	     can nevertheless deduce some things about the comparison.  */
+	  if (const_arg0 == 0 || const_arg1 == 0)
+	    {
+	      /* Is FOLDED_ARG0 frame-pointer plus a constant?  Or non-explicit
+		 constant?  These aren't zero, but we don't know their sign. */
+	      if (const_arg1 == const0_rtx
+		  && (NONZERO_BASE_PLUS_P (folded_arg0)
+#if 0  /* Sad to say, on sysvr4, #pragma weak can make a symbol address
+	  come out as 0.  */
+		      || GET_CODE (folded_arg0) == SYMBOL_REF
+#endif
+		      || GET_CODE (folded_arg0) == LABEL_REF
+		      || GET_CODE (folded_arg0) == CONST))
+		{
+		  if (code == EQ)
+		    return const0_rtx;
+		  else if (code == NE)
+		    return const_true_rtx;
+		}
+
+	      /* See if the two operands are the same.  We don't do this
+		 for IEEE floating-point since we can't assume x == x
+		 since x might be a NaN.  */
+
+	      if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
+		   || GET_MODE_CLASS (mode_arg0) != MODE_FLOAT)
+		  && (folded_arg0 == folded_arg1
+		      || (GET_CODE (folded_arg0) == REG
+			  && GET_CODE (folded_arg1) == REG
+			  && (reg_qty[REGNO (folded_arg0)]
+			      == reg_qty[REGNO (folded_arg1)]))
+		      || ((p0 = lookup (folded_arg0,
+					(safe_hash (folded_arg0, mode_arg0)
+					 % NBUCKETS), mode_arg0))
+			  && (p1 = lookup (folded_arg1,
+					   (safe_hash (folded_arg1, mode_arg0)
+					    % NBUCKETS), mode_arg0))
+			  && p0->first_same_value == p1->first_same_value)))
+		return ((code == EQ || code == LE || code == GE
+			 || code == LEU || code == GEU)
+			? const_true_rtx : const0_rtx);
+
+	      /* If FOLDED_ARG0 is a register, see if the comparison we are
+		 doing now is either the same as we did before or the reverse
+		 (we only check the reverse if not floating-point).  */
+	      else if (GET_CODE (folded_arg0) == REG)
+		{
+		  int qty = reg_qty[REGNO (folded_arg0)];
+
+		  if (REGNO_QTY_VALID_P (REGNO (folded_arg0))
+		      && (comparison_dominates_p (qty_comparison_code[qty], code)
+			  || (comparison_dominates_p (qty_comparison_code[qty],
+						      reverse_condition (code))
+			      && GET_MODE_CLASS (mode_arg0) == MODE_INT))
+		      && (rtx_equal_p (qty_comparison_const[qty], folded_arg1)
+			  || (const_arg1
+			      && rtx_equal_p (qty_comparison_const[qty],
+					      const_arg1))
+			  || (GET_CODE (folded_arg1) == REG
+			      && (reg_qty[REGNO (folded_arg1)]
+				  == qty_comparison_qty[qty]))))
+		    return (comparison_dominates_p (qty_comparison_code[qty],
+						    code)
+			    ? const_true_rtx : const0_rtx);
+		}
+	    }
+	}
+
+      /* If we are comparing against zero, see if the first operand is
+	 equivalent to an IOR with a constant.  If so, we may be able to
+	 determine the result of this comparison.  */
+
+      if (const_arg1 == const0_rtx)
+	{
+	  rtx y = lookup_as_function (folded_arg0, IOR);
+	  rtx inner_const;
+
+	  if (y != 0
+	      && (inner_const = equiv_constant (XEXP (y, 1))) != 0
+	      && GET_CODE (inner_const) == CONST_INT
+	      && INTVAL (inner_const) != 0)
+	    {
+	      int sign_bitnum = GET_MODE_BITSIZE (mode_arg0) - 1;
+	      int has_sign = (HOST_BITS_PER_INT >= sign_bitnum
+			      && (INTVAL (inner_const) & (1 << sign_bitnum)));
+
+	      switch (code)
+		{
+		case EQ:
+		  return const0_rtx;
+		case NE:
+		  return const_true_rtx;
+		case LT:  case LE:
+		  if (has_sign)
+		    return const_true_rtx;
+		  break;
+		case GT:  case GE:
+		  if (has_sign)
+		    return const0_rtx;
+		  break;
+		}
+	    }
+	}
+
+      new = simplify_relational_operation (code, mode_arg0,
+					   const_arg0 ? const_arg0 : folded_arg0,
+					   const_arg1 ? const_arg1 : folded_arg1);
+      break;
+
+    case '2':
+    case 'c':
+      switch (code)
+	{
+	case PLUS:
+	  /* If the second operand is a LABEL_REF, see if the first is a MINUS
+	     with that LABEL_REF as its second operand.  If so, the result is
+	     the first operand of that MINUS.  This handles switches with an
+	     ADDR_DIFF_VEC table.  */
+	  if (const_arg1 && GET_CODE (const_arg1) == LABEL_REF)
+	    {
+	      rtx y = lookup_as_function (folded_arg0, MINUS);
+
+	      if (y != 0 && GET_CODE (XEXP (y, 1)) == LABEL_REF
+		  && XEXP (XEXP (y, 1), 0) == XEXP (const_arg1, 0))
+		return XEXP (y, 0);
+	    }
+
+	  /* ... fall through ... */
+
+	case MINUS:
+	case SMIN:    case SMAX:      case UMIN:    case UMAX:
+	case IOR:     case AND:       case XOR:
+	case MULT:    case DIV:       case UDIV:
+	case ASHIFT:  case LSHIFTRT:  case ASHIFTRT:
+	  /* If we have (<op> <reg> <const_int>) for an associative OP and REG
+	     is known to be of similar form, we may be able to replace the
+	     operation with a combined operation.  This may eliminate the
+	     intermediate operation if every use is simplified in this way.
+	     Note that the similar optimization done by combine.c only works
+	     if the intermediate operation's result has only one reference.  */
+
+	  if (GET_CODE (folded_arg0) == REG
+	      && const_arg1 && GET_CODE (const_arg1) == CONST_INT)
+	    {
+	      int is_shift
+		= (code == ASHIFT || code == ASHIFTRT || code == LSHIFTRT);
+	      rtx y = lookup_as_function (folded_arg0, code);
+	      rtx inner_const;
+	      enum rtx_code associate_code;
+	      rtx new_const;
+
+	      if (y == 0
+		  || 0 == (inner_const
+			   = equiv_constant (fold_rtx (XEXP (y, 1), 0)))
+		  || GET_CODE (inner_const) != CONST_INT
+		  /* If we have compiled a statement like
+		     "if (x == (x & mask1))", and now are looking at
+		     "x & mask2", we will have a case where the first operand
+		     of Y is the same as our first operand.  Unless we detect
+		     this case, an infinite loop will result.  */
+		  || XEXP (y, 0) == folded_arg0)
+		break;
+
+	      /* Don't associate these operations if they are a PLUS with the
+		 same constant and it is a power of two.  These might be doable
+		 with a pre- or post-increment.  Similarly for two subtracts of
+		 identical powers of two with post decrement.  */
+
+	      if (code == PLUS && INTVAL (const_arg1) == INTVAL (inner_const)
+		  && (0
+#if defined(HAVE_PRE_INCREMENT) || defined(HAVE_POST_INCREMENT)
+		      || exact_log2 (INTVAL (const_arg1)) >= 0
+#endif
+#if defined(HAVE_PRE_DECREMENT) || defined(HAVE_POST_DECREMENT)
+		      || exact_log2 (- INTVAL (const_arg1)) >= 0
+#endif
+		  ))
+		break;
+
+	      /* Compute the code used to compose the constants.  For example,
+		 A/C1/C2 is A/(C1 * C2), so if CODE == DIV, we want MULT.  */
+
+	      associate_code
+		= (code == MULT || code == DIV || code == UDIV ? MULT
+		   : is_shift || code == PLUS || code == MINUS ? PLUS : code);
+
+	      new_const = simplify_binary_operation (associate_code, mode,
+						     const_arg1, inner_const);
+
+	      if (new_const == 0)
+		break;
+
+	      /* If we are associating shift operations, don't let this
+		 produce a shift of larger than the object.  This could
+		 occur when we following a sign-extend by a right shift on
+		 a machine that does a sign-extend as a pair of shifts.  */
+
+	      if (is_shift && GET_CODE (new_const) == CONST_INT
+		  && INTVAL (new_const) > GET_MODE_BITSIZE (mode))
+		break;
+
+	      y = copy_rtx (XEXP (y, 0));
+
+	      /* If Y contains our first operand (the most common way this
+		 can happen is if Y is a MEM), we would do into an infinite
+		 loop if we tried to fold it.  So don't in that case.  */
+
+	      if (! reg_mentioned_p (folded_arg0, y))
+		y = fold_rtx (y, insn);
+
+	      new = simplify_binary_operation (code, mode, y, new_const);
+	      if (new)
+		return new;
+
+	      return gen_rtx (code, mode, y, new_const);
+	    }
+	}
+
+      new = simplify_binary_operation (code, mode,
+				       const_arg0 ? const_arg0 : folded_arg0,
+				       const_arg1 ? const_arg1 : folded_arg1);
+      break;
+
+    case 'o':
+      /* (lo_sum (high X) X) is simply X.  */
+      if (code == LO_SUM && const_arg0 != 0
+	  && GET_CODE (const_arg0) == HIGH
+	  && rtx_equal_p (XEXP (const_arg0, 0), const_arg1))
+	return const_arg1;
+      break;
+
+    case '3':
+    case 'b':
+      new = simplify_ternary_operation (code, mode, mode_arg0,
+					const_arg0 ? const_arg0 : folded_arg0,
+					const_arg1 ? const_arg1 : folded_arg1,
+					const_arg2 ? const_arg2 : XEXP (x, 2));
+      break;
+    }
+
+  return new ? new : x;
+}
+
+/* Return a constant value currently equivalent to X.
+   Return 0 if we don't know one.  */
+
+static rtx
+equiv_constant (x)
+     rtx x;
+{
+  if (GET_CODE (x) == REG
+      && REGNO_QTY_VALID_P (REGNO (x))
+      && qty_const[reg_qty[REGNO (x)]])
+    x = gen_lowpart_if_possible (GET_MODE (x), qty_const[reg_qty[REGNO (x)]]);
+
+  if (x != 0 && CONSTANT_P (x))
+    return x;
+
+  return 0;
+}
+
+/* Assuming that X is an rtx (e.g., MEM, REG or SUBREG) for a fixed-point
+   number, return an rtx (MEM, SUBREG, or CONST_INT) that refers to the
+   least-significant part of X.
+   MODE specifies how big a part of X to return.  
+
+   If the requested operation cannot be done, 0 is returned.
+
+   This is similar to gen_lowpart in emit-rtl.c.  */
+
+rtx
+gen_lowpart_if_possible (mode, x)
+     enum machine_mode mode;
+     register rtx x;
+{
+  rtx result = gen_lowpart_common (mode, x);
+
+  if (result)
+    return result;
+  else if (GET_CODE (x) == MEM)
+    {
+      /* This is the only other case we handle.  */
+      register int offset = 0;
+      rtx new;
+
+#if WORDS_BIG_ENDIAN
+      offset = (MAX (GET_MODE_SIZE (GET_MODE (x)), UNITS_PER_WORD)
+		- MAX (GET_MODE_SIZE (mode), UNITS_PER_WORD));
+#endif
+#if 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
+      new = gen_rtx (MEM, mode, plus_constant (XEXP (x, 0), offset));
+      if (! memory_address_p (mode, XEXP (new, 0)))
+	return 0;
+      MEM_VOLATILE_P (new) = MEM_VOLATILE_P (x);
+      RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x);
+      MEM_IN_STRUCT_P (new) = MEM_IN_STRUCT_P (x);
+      return new;
+    }
+  else
+    return 0;
+}
+
+/* Given INSN, a jump insn, TAKEN indicates if we are following the "taken"
+   branch.  It will be zero if not.
+
+   In certain cases, this can cause us to add an equivalence.  For example,
+   if we are following the taken case of 
+   	if (i == 2)
+   we can add the fact that `i' and '2' are now equivalent.
+
+   In any case, we can record that this comparison was passed.  If the same
+   comparison is seen later, we will know its value.  */
+
+static void
+record_jump_equiv (insn, taken)
+     rtx insn;
+     int taken;
+{
+  int cond_known_true;
+  rtx op0, op1;
+  enum machine_mode mode;
+  int reversed_nonequality = 0;
+  enum rtx_code code;
+
+  /* Ensure this is the right kind of insn.  */
+  if (! condjump_p (insn) || simplejump_p (insn))
+    return;
+
+  /* See if this jump condition is known true or false.  */
+  if (taken)
+    cond_known_true = (XEXP (SET_SRC (PATTERN (insn)), 2) == pc_rtx);
+  else
+    cond_known_true = (XEXP (SET_SRC (PATTERN (insn)), 1) == pc_rtx);
+
+  /* Get the type of comparison being done and the operands being compared.
+     If we had to reverse a non-equality condition, record that fact so we
+     know that it isn't valid for floating-point.  */
+  code = GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 0));
+  op0 = fold_rtx (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 0), insn);
+  op1 = fold_rtx (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 1), insn);
+
+  code = find_comparison_args (code, &op0, &op1);
+  if (! cond_known_true)
+    {
+      reversed_nonequality = (code != EQ && code != NE);
+      code = reverse_condition (code);
+    }
+
+  /* The mode is the mode of the non-constant.  */
+  mode = GET_MODE (op0);
+  if (mode == VOIDmode) mode = GET_MODE (op1);
+
+  record_jump_cond (code, mode, op0, op1, reversed_nonequality);
+}
+
+/* We know that comparison CODE applied to OP0 and OP1 in MODE is true.
+   REVERSED_NONEQUALITY is nonzero if CODE had to be swapped.
+   Make any useful entries we can with that information.  Called from
+   above function and called recursively.  */
+
+static void
+record_jump_cond (code, mode, op0, op1, reversed_nonequality)
+     enum rtx_code code;
+     enum machine_mode mode;
+     rtx op0, op1;
+     int reversed_nonequality;
+{
+  int op0_hash_code, op1_hash_code;
+  int op0_in_memory, op0_in_struct, op1_in_memory, op1_in_struct;
+  struct table_elt *op0_elt, *op1_elt;
+
+  /* If OP0 and OP1 are known equal, and either is a paradoxical SUBREG,
+     we know that they are also equal in the smaller mode (this is also
+     true for all smaller modes whether or not there is a SUBREG, but
+     is not worth testing for with no SUBREG.  */
+
+  if (code == EQ && GET_CODE (op0) == SUBREG
+      && GET_MODE_SIZE (mode) > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0))))
+    {
+      enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op0));
+      rtx tem = gen_lowpart_if_possible (inner_mode, op1);
+
+      record_jump_cond (code, mode, SUBREG_REG (op0),
+			tem ? tem : gen_rtx (SUBREG, inner_mode, op1, 0),
+			reversed_nonequality);
+    }
+
+  if (code == EQ && GET_CODE (op1) == SUBREG
+      && GET_MODE_SIZE (mode) > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1))))
+    {
+      enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op1));
+      rtx tem = gen_lowpart_if_possible (inner_mode, op0);
+
+      record_jump_cond (code, mode, SUBREG_REG (op1),
+			tem ? tem : gen_rtx (SUBREG, inner_mode, op0, 0),
+			reversed_nonequality);
+    }
+
+  /* Similarly, if this is an NE comparison, and either is a SUBREG 
+     making a smaller mode, we know the whole thing is also NE.  */
+
+  if (code == NE && GET_CODE (op0) == SUBREG
+      && subreg_lowpart_p (op0)
+      && GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0))))
+    {
+      enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op0));
+      rtx tem = gen_lowpart_if_possible (inner_mode, op1);
+
+      record_jump_cond (code, mode, SUBREG_REG (op0),
+			tem ? tem : gen_rtx (SUBREG, inner_mode, op1, 0),
+			reversed_nonequality);
+    }
+
+  if (code == NE && GET_CODE (op1) == SUBREG
+      && subreg_lowpart_p (op1)
+      && GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (SUBREG_REG (op1))))
+    {
+      enum machine_mode inner_mode = GET_MODE (SUBREG_REG (op1));
+      rtx tem = gen_lowpart_if_possible (inner_mode, op0);
+
+      record_jump_cond (code, mode, SUBREG_REG (op1),
+			tem ? tem : gen_rtx (SUBREG, inner_mode, op0, 0),
+			reversed_nonequality);
+    }
+
+  /* Hash both operands.  */
+
+  do_not_record = 0;
+  hash_arg_in_memory = 0;
+  hash_arg_in_struct = 0;
+  op0_hash_code = HASH (op0, mode);
+  op0_in_memory = hash_arg_in_memory;
+  op0_in_struct = hash_arg_in_struct;
+
+  if (do_not_record)
+    return;
+
+  do_not_record = 0;
+  hash_arg_in_memory = 0;
+  hash_arg_in_struct = 0;
+  op1_hash_code = HASH (op1, mode);
+  op1_in_memory = hash_arg_in_memory;
+  op1_in_struct = hash_arg_in_struct;
+  
+  if (do_not_record)
+    return;
+
+  /* Look up both operands.  */
+  op0_elt = lookup (op0, op0_hash_code, mode);
+  op1_elt = lookup (op1, op1_hash_code, mode);
+
+  /* If we aren't setting two things equal all we can do is save this
+     comparison.  */
+  if (code != EQ)
+    {
+      /* If we reversed a floating-point comparison, if OP0 is not a
+	 register, or if OP1 is neither a register or constant, we can't
+	 do anything.  */
+
+      if (GET_CODE (op1) != REG)
+	op1 = equiv_constant (op1);
+
+      if ((reversed_nonequality && GET_MODE_CLASS (mode) != MODE_INT)
+	  || GET_CODE (op0) != REG || op1 == 0)
+	return;
+
+      /* Put OP0 in the hash table if it isn't already.  This gives it a
+	 new quantity number.  */
+      if (op0_elt == 0)
+	{
+	  if (insert_regs (op0, 0, 0))
+	    {
+	      rehash_using_reg (op0);
+	      op0_hash_code = HASH (op0, mode);
+	    }
+
+	  op0_elt = insert (op0, 0, op0_hash_code, mode);
+	  op0_elt->in_memory = op0_in_memory;
+	  op0_elt->in_struct = op0_in_struct;
+	}
+
+      qty_comparison_code[reg_qty[REGNO (op0)]] = code;
+      if (GET_CODE (op1) == REG)
+	{
+	  /* Put OP1 in the hash table so it gets a new quantity number.  */
+	  if (op1_elt == 0)
+	    {
+	      if (insert_regs (op1, 0, 0))
+		{
+		  rehash_using_reg (op1);
+		  op1_hash_code = HASH (op1, mode);
+		}
+
+	      op1_elt = insert (op1, 0, op1_hash_code, mode);
+	      op1_elt->in_memory = op1_in_memory;
+	      op1_elt->in_struct = op1_in_struct;
+	    }
+
+	  qty_comparison_qty[reg_qty[REGNO (op0)]] = reg_qty[REGNO (op1)];
+	  qty_comparison_const[reg_qty[REGNO (op0)]] = 0;
+	}
+      else
+	{
+	  qty_comparison_qty[reg_qty[REGNO (op0)]] = -1;
+	  qty_comparison_const[reg_qty[REGNO (op0)]] = op1;
+	}
+
+      return;
+    }
+
+  /* If both are equivalent, merge the two classes.  Save this class for
+     `cse_set_around_loop'.  */
+  if (op0_elt && op1_elt)
+    {
+      merge_equiv_classes (op0_elt, op1_elt);
+      last_jump_equiv_class = op0_elt;
+    }
+
+  /* For whichever side doesn't have an equivalence, make one.  */
+  if (op0_elt == 0)
+    {
+      if (insert_regs (op0, op1_elt, 0))
+	{
+	  rehash_using_reg (op0);
+	  op0_hash_code = HASH (op0, mode);
+	}
+
+      op0_elt = insert (op0, op1_elt, op0_hash_code, mode);
+      op0_elt->in_memory = op0_in_memory;
+      op0_elt->in_struct = op0_in_struct;
+      last_jump_equiv_class = op0_elt;
+    }
+
+  if (op1_elt == 0)
+    {
+      if (insert_regs (op1, op0_elt, 0))
+	{
+	  rehash_using_reg (op1);
+	  op1_hash_code = HASH (op1, mode);
+	}
+
+      op1_elt = insert (op1, op0_elt, op1_hash_code, mode);
+      op1_elt->in_memory = op1_in_memory;
+      op1_elt->in_struct = op1_in_struct;
+      last_jump_equiv_class = op1_elt;
+    }
+}
+
+/* CSE processing for one instruction.
+   First simplify sources and addresses of all assignments
+   in the instruction, using previously-computed equivalents values.
+   Then install the new sources and destinations in the table
+   of available values. 
+
+   If IN_LIBCALL_BLOCK is nonzero, don't record any equivalence made in
+   the insn.  */
+
+/* Data on one SET contained in the instruction.  */
+
+struct set
+{
+  /* The SET rtx itself.  */
+  rtx rtl;
+  /* The SET_SRC of the rtx (the original value, if it is changing).  */
+  rtx src;
+  /* The hash-table element for the SET_SRC of the SET.  */
+  struct table_elt *src_elt;
+  /* Hash code for the SET_SRC.  */
+  int src_hash_code;
+  /* Hash code for the SET_DEST.  */
+  int dest_hash_code;
+  /* The SET_DEST, with SUBREG, etc., stripped.  */
+  rtx inner_dest;
+  /* Place where the pointer to the INNER_DEST was found.  */
+  rtx *inner_dest_loc;
+  /* Nonzero if the SET_SRC is in memory.  */ 
+  char src_in_memory;
+  /* Nonzero if the SET_SRC is in a structure.  */ 
+  char src_in_struct;
+  /* Nonzero if the SET_SRC contains something
+     whose value cannot be predicted and understood.  */
+  char src_volatile;
+  /* Original machine mode, in case it becomes a CONST_INT.  */
+  enum machine_mode mode;
+  /* A constant equivalent for SET_SRC, if any.  */
+  rtx src_const;
+  /* Hash code of constant equivalent for SET_SRC.  */
+  int src_const_hash_code;
+  /* Table entry for constant equivalent for SET_SRC, if any.  */
+  struct table_elt *src_const_elt;
+};
+
+static void
+cse_insn (insn, in_libcall_block)
+     rtx insn;
+     int in_libcall_block;
+{
+  register rtx x = PATTERN (insn);
+  rtx tem;
+  register int i;
+  register int n_sets = 0;
+
+  /* Records what this insn does to set CC0.  */
+  rtx this_insn_cc0 = 0;
+  enum machine_mode this_insn_cc0_mode;
+  struct write_data writes_memory;
+  static struct write_data init = {0, 0, 0, 0};
+
+  rtx src_eqv = 0;
+  struct table_elt *src_eqv_elt = 0;
+  int src_eqv_volatile;
+  int src_eqv_in_memory;
+  int src_eqv_in_struct;
+  int src_eqv_hash_code;
+
+  struct set *sets;
+
+  this_insn = insn;
+  writes_memory = init;
+
+  /* Find all the SETs and CLOBBERs in this instruction.
+     Record all the SETs in the array `set' and count them.
+     Also determine whether there is a CLOBBER that invalidates
+     all memory references, or all references at varying addresses.  */
+
+  if (GET_CODE (x) == SET)
+    {
+      sets = (struct set *) alloca (sizeof (struct set));
+      sets[0].rtl = x;
+
+      /* Ignore SETs that are unconditional jumps.
+	 They never need cse processing, so this does not hurt.
+	 The reason is not efficiency but rather
+	 so that we can test at the end for instructions
+	 that have been simplified to unconditional jumps
+	 and not be misled by unchanged instructions
+	 that were unconditional jumps to begin with.  */
+      if (SET_DEST (x) == pc_rtx
+	  && GET_CODE (SET_SRC (x)) == LABEL_REF)
+	;
+
+      /* Don't count call-insns, (set (reg 0) (call ...)), as a set.
+	 The hard function value register is used only once, to copy to
+	 someplace else, so it isn't worth cse'ing (and on 80386 is unsafe)!
+	 Ensure we invalidate the destination register.  On the 80386 no
+	 other code would invalidate it since it is a fixed_reg.  */
+
+      else if (GET_CODE (SET_SRC (x)) == CALL)
+	{
+	  canon_reg (SET_SRC (x), insn);
+	  fold_rtx (SET_SRC (x), insn);
+	  invalidate (SET_DEST (x));
+	}
+      else
+	n_sets = 1;
+    }
+  else if (GET_CODE (x) == PARALLEL)
+    {
+      register int lim = XVECLEN (x, 0);
+
+      sets = (struct set *) alloca (lim * sizeof (struct set));
+
+      /* Find all regs explicitly clobbered in this insn,
+	 and ensure they are not replaced with any other regs
+	 elsewhere in this insn.
+	 When a reg that is clobbered is also used for input,
+	 we should presume that that is for a reason,
+	 and we should not substitute some other register
+	 which is not supposed to be clobbered.
+	 Therefore, this loop cannot be merged into the one below
+	 because a CALL may preceed a CLOBBER and refer to the
+	 value clobbered.  We must not let a canonicalization do
+	 anything in that case.  */
+      for (i = 0; i < lim; i++)
+	{
+	  register rtx y = XVECEXP (x, 0, i);
+	  if (GET_CODE (y) == CLOBBER && GET_CODE (XEXP (y, 0)) == REG)
+	    invalidate (XEXP (y, 0));
+	}
+	    
+      for (i = 0; i < lim; i++)
+	{
+	  register rtx y = XVECEXP (x, 0, i);
+	  if (GET_CODE (y) == SET)
+	    {
+	      /* As above, we ignore unconditional jumps and call-insns. */
+	      if (GET_CODE (SET_SRC (y)) == CALL)
+		{
+		  canon_reg (SET_SRC (y), insn);
+		  fold_rtx (SET_SRC (y), insn);
+		  invalidate (SET_DEST (y));
+		}
+	      else if (SET_DEST (y) == pc_rtx
+		       && GET_CODE (SET_SRC (y)) == LABEL_REF)
+		;
+	      else
+		sets[n_sets++].rtl = y;
+	    }
+	  else if (GET_CODE (y) == CLOBBER)
+	    {
+	      /* If we clobber memory, take note of that,
+		 and canon the address.
+		 This does nothing when a register is clobbered
+		 because we have already invalidated the reg.  */
+	      if (GET_CODE (XEXP (y, 0)) == MEM)
+		{
+		  canon_reg (XEXP (y, 0), 0);
+		  note_mem_written (XEXP (y, 0), &writes_memory);
+		}
+	    }
+	  else if (GET_CODE (y) == USE
+		   && ! (GET_CODE (XEXP (y, 0)) == REG
+			 && REGNO (XEXP (y, 0)) < FIRST_PSEUDO_REGISTER))
+	    canon_reg (y, 0);
+	  else if (GET_CODE (y) == CALL)
+	    {
+	      canon_reg (y, insn);
+	      fold_rtx (y, insn);
+	    }
+	}
+    }
+  else if (GET_CODE (x) == CLOBBER)
+    {
+      if (GET_CODE (XEXP (x, 0)) == MEM)
+	{
+	  canon_reg (XEXP (x, 0), 0);
+	  note_mem_written (XEXP (x, 0), &writes_memory);
+	}
+    }
+
+  /* Canonicalize a USE of a pseudo register or memory location.  */
+  else if (GET_CODE (x) == USE
+	   && ! (GET_CODE (XEXP (x, 0)) == REG
+		 && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER))
+    canon_reg (XEXP (x, 0), 0);
+  else if (GET_CODE (x) == CALL)
+    {
+      canon_reg (x, insn);
+      fold_rtx (x, insn);
+    }
+
+  if (n_sets == 1 && REG_NOTES (insn) != 0)
+    {
+      /* Store the equivalent value in SRC_EQV, if different.  */
+      rtx tem = find_reg_note (insn, REG_EQUAL, 0);
+
+      if (tem && ! rtx_equal_p (XEXP (tem, 0), SET_SRC (sets[0].rtl)))
+        src_eqv = canon_reg (XEXP (tem, 0), 0);
+    }
+
+  /* Canonicalize sources and addresses of destinations.
+     We do this in a separate pass to avoid problems when a MATCH_DUP is
+     present in the insn pattern.  In that case, we want to ensure that
+     we don't break the duplicate nature of the pattern.  So we will replace
+     both operands at the same time.  Otherwise, we would fail to find an
+     equivalent substitution in the loop calling validate_change below.
+     (We also speed up that loop when a canonicalization was done since
+     recog_memoized need not be called for just a canonicalization unless
+     a pseudo register is being replaced by a hard reg of vice versa.)
+
+     We used to suppress canonicalization of DEST if it appears in SRC,
+     but we don't do this any more.
+
+     ??? The way this code is written now, if we have a MATCH_DUP between
+     two operands that are pseudos and we would want to canonicalize them
+     to a hard register, we won't do that.  The only time this would happen
+     is if the hard reg was a fixed register, and this should be rare.
+
+     ??? This won't work if there is a MATCH_DUP between an input and an
+     output, but these never worked and must be declared invalid.  */
+
+  for (i = 0; i < n_sets; i++)
+    {
+      rtx dest = SET_DEST (sets[i].rtl);
+      rtx src = SET_SRC (sets[i].rtl);
+      rtx new = canon_reg (src, insn);
+
+      if (GET_CODE (new) == REG && GET_CODE (src) == REG
+	  && ((REGNO (new) < FIRST_PSEUDO_REGISTER)
+	      != (REGNO (src) < FIRST_PSEUDO_REGISTER)))
+	validate_change (insn, &SET_SRC (sets[i].rtl), new, 0);
+      else
+	SET_SRC (sets[i].rtl) = new;
+
+      if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT)
+	{
+	  validate_change (insn, &XEXP (dest, 1),
+			   canon_reg (XEXP (dest, 1), insn), 0);
+	  validate_change (insn, &XEXP (dest, 2),
+			   canon_reg (XEXP (dest, 2), insn), 0);
+	}
+
+      while (GET_CODE (dest) == SUBREG || GET_CODE (dest) == STRICT_LOW_PART
+	     || GET_CODE (dest) == ZERO_EXTRACT
+	     || GET_CODE (dest) == SIGN_EXTRACT)
+	dest = XEXP (dest, 0);
+
+      if (GET_CODE (dest) == MEM)
+	canon_reg (dest, insn);
+    }
+
+  /* Set sets[i].src_elt to the class each source belongs to.
+     Detect assignments from or to volatile things
+     and set set[i] to zero so they will be ignored
+     in the rest of this function.
+
+     Nothing in this loop changes the hash table or the register chains.  */
+
+  for (i = 0; i < n_sets; i++)
+    {
+      register rtx src, dest;
+      register rtx src_folded;
+      register struct table_elt *elt = 0, *p;
+      enum machine_mode mode;
+      rtx src_eqv_here;
+      rtx src_const = 0;
+      rtx src_related = 0;
+      struct table_elt *src_const_elt = 0;
+      int src_cost = 10000, src_eqv_cost = 10000, src_folded_cost = 10000;
+      int src_related_cost = 10000, src_elt_cost = 10000;
+      /* Set non-zero if we need to call force_const_mem on with the
+	 contents of src_folded before using it.  */
+      int src_folded_force_flag = 0;
+
+      dest = SET_DEST (sets[i].rtl);
+      src = SET_SRC (sets[i].rtl);
+
+      /* If SRC is a constant that has no machine mode,
+	 hash it with the destination's machine mode.
+	 This way we can keep different modes separate.  */
+
+      mode = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src);
+      sets[i].mode = mode;
+
+      if (src_eqv)
+	{
+	  enum machine_mode eqvmode = mode;
+	  if (GET_CODE (dest) == STRICT_LOW_PART)
+	    eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0)));
+	  do_not_record = 0;
+	  hash_arg_in_memory = 0;
+	  hash_arg_in_struct = 0;
+	  src_eqv = fold_rtx (src_eqv, insn);
+	  src_eqv_hash_code = HASH (src_eqv, eqvmode);
+
+	  /* Find the equivalence class for the equivalent expression.  */
+
+	  if (!do_not_record)
+	    src_eqv_elt = lookup (src_eqv, src_eqv_hash_code, eqvmode);
+
+	  src_eqv_volatile = do_not_record;
+	  src_eqv_in_memory = hash_arg_in_memory;
+	  src_eqv_in_struct = hash_arg_in_struct;
+	}
+
+      /* If this is a STRICT_LOW_PART assignment, src_eqv corresponds to the
+	 value of the INNER register, not the destination.  So it is not
+	 a legal substitution for the source.  But save it for later.  */
+      if (GET_CODE (dest) == STRICT_LOW_PART)
+	src_eqv_here = 0;
+      else
+	src_eqv_here = src_eqv;
+
+      /* Simplify and foldable subexpressions in SRC.  Then get the fully-
+	 simplified result, which may not necessarily be valid.  */
+      src_folded = fold_rtx (src, insn);
+
+      /* If storing a constant in a bitfield, pre-truncate the constant
+	 so we will be able to record it later.  */
+      if (GET_CODE (SET_DEST (sets[i].rtl)) == ZERO_EXTRACT
+	  || GET_CODE (SET_DEST (sets[i].rtl)) == SIGN_EXTRACT)
+	{
+	  rtx width = XEXP (SET_DEST (sets[i].rtl), 1);
+
+	  if (GET_CODE (src) == CONST_INT
+	      && GET_CODE (width) == CONST_INT
+	      && INTVAL (width) < HOST_BITS_PER_INT
+	      && (INTVAL (src) & ((-1) << INTVAL (width))))
+	    src_folded = gen_rtx (CONST_INT, VOIDmode,
+				  INTVAL (src) & ((1 << INTVAL (width)) - 1));
+	}
+
+      /* Compute SRC's hash code, and also notice if it
+	 should not be recorded at all.  In that case,
+	 prevent any further processing of this assignment.  */
+      do_not_record = 0;
+      hash_arg_in_memory = 0;
+      hash_arg_in_struct = 0;
+
+      sets[i].src = src;
+      sets[i].src_hash_code = HASH (src, mode);
+      sets[i].src_volatile = do_not_record;
+      sets[i].src_in_memory = hash_arg_in_memory;
+      sets[i].src_in_struct = hash_arg_in_struct;
+
+      /* If source is a perverse subreg (such as QI treated as an SI),
+	 treat it as volatile.  It may do the work of an SI in one context
+	 where the extra bits are not being used, but cannot replace an SI
+	 in general.  */
+      if (GET_CODE (src) == SUBREG
+	  && (GET_MODE_SIZE (GET_MODE (src))
+	      > GET_MODE_SIZE (GET_MODE (SUBREG_REG (src)))))
+	sets[i].src_volatile = 1;
+
+      /* Locate all possible equivalent forms for SRC.  Try to replace
+         SRC in the insn with each cheaper equivalent.
+
+         We have the following types of equivalents: SRC itself, a folded
+         version, a value given in a REG_EQUAL note, or a value related
+	 to a constant.
+
+         Each of these equivalents may be part of an additional class
+         of equivalents (if more than one is in the table, they must be in
+         the same class; we check for this).
+
+	 If the source is volatile, we don't do any table lookups.
+
+         We note any constant equivalent for possible later use in a
+         REG_NOTE.  */
+
+      if (!sets[i].src_volatile)
+	elt = lookup (src, sets[i].src_hash_code, mode);
+
+      sets[i].src_elt = elt;
+
+      if (elt && src_eqv_here && src_eqv_elt)
+        {
+          if (elt->first_same_value != src_eqv_elt->first_same_value)
+	    {
+	      /* The REG_EQUAL is indicating that two formerly distinct
+		 classes are now equivalent.  So merge them.  */
+	      merge_equiv_classes (elt, src_eqv_elt);
+	      src_eqv_hash_code = HASH (src_eqv, elt->mode);
+	      src_eqv_elt = lookup (src_eqv, src_eqv_hash_code, elt->mode);
+	    }
+
+          src_eqv_here = 0;
+        }
+
+      else if (src_eqv_elt)
+        elt = src_eqv_elt;
+
+      /* Try to find a constant somewhere and record it in `src_const'.
+	 Record its table element, if any, in `src_const_elt'.  Look in
+	 any known equivalences first.  (If the constant is not in the
+	 table, also set `sets[i].src_const_hash_code').  */
+      if (elt)
+        for (p = elt->first_same_value; p; p = p->next_same_value)
+	  if (p->is_const)
+	    {
+	      src_const = p->exp;
+	      src_const_elt = elt;
+	      break;
+	    }
+
+      if (src_const == 0
+	  && (CONSTANT_P (src_folded)
+	      /* Consider (minus (label_ref L1) (label_ref L2)) as 
+		 "constant" here so we will record it. This allows us
+		 to fold switch statements when an ADDR_DIFF_VEC is used.  */
+	      || (GET_CODE (src_folded) == MINUS
+		  && GET_CODE (XEXP (src_folded, 0)) == LABEL_REF
+		  && GET_CODE (XEXP (src_folded, 1)) == LABEL_REF)))
+	src_const = src_folded, src_const_elt = elt;
+      else if (src_const == 0 && src_eqv_here && CONSTANT_P (src_eqv_here))
+	src_const = src_eqv_here, src_const_elt = src_eqv_elt;
+
+      /* If we don't know if the constant is in the table, get its
+	 hash code and look it up.  */
+      if (src_const && src_const_elt == 0)
+	{
+	  sets[i].src_const_hash_code = HASH (src_const, mode);
+	  src_const_elt = lookup (src_const, sets[i].src_const_hash_code,
+				  mode);
+	}
+
+      sets[i].src_const = src_const;
+      sets[i].src_const_elt = src_const_elt;
+
+      /* If the constant and our source are both in the table, mark them as
+	 equivalent.  Otherwise, if a constant is in the table but the source
+	 isn't, set ELT to it.  */
+      if (src_const_elt && elt
+	  && src_const_elt->first_same_value != elt->first_same_value)
+	merge_equiv_classes (elt, src_const_elt);
+      else if (src_const_elt && elt == 0)
+	elt = src_const_elt;
+
+      /* See if there is a register linearly related to a constant
+         equivalent of SRC.  */
+      if (src_const
+	  && (GET_CODE (src_const) == CONST
+	      || (src_const_elt && src_const_elt->related_value != 0)))
+        {
+          src_related = use_related_value (src_const, src_const_elt);
+          if (src_related)
+            {
+	      struct table_elt *src_related_elt
+		    = lookup (src_related, HASH (src_related, mode), mode);
+	      if (src_related_elt && elt)
+	        {
+		  if (elt->first_same_value
+		      != src_related_elt->first_same_value)
+		    /* This can occur when we previously saw a CONST 
+		       involving a SYMBOL_REF and then see the SYMBOL_REF
+		       twice.  Merge the involved classes.  */
+		    merge_equiv_classes (elt, src_related_elt);
+
+	          src_related = 0;
+		  src_related_elt = 0;
+	        }
+              else if (src_related_elt && elt == 0)
+	        elt = src_related_elt;
+	    }
+        }
+
+      if (src == src_folded)
+        src_folded = 0;
+
+      /* At this point, ELT, if non-zero, points to a class of expressions
+         equivalent to the source of this SET and SRC, SRC_EQV, SRC_FOLDED,
+	 and SRC_RELATED, if non-zero, each contain additional equivalent
+	 expressions.  Prune these latter expressions by deleting expressions
+	 already in the equivalence class.
+
+	 Check for an equivalent identical to the destination.  If found,
+	 this is the preferred equivalent since it will likely lead to
+	 elimination of the insn.  Indicate this by placing it in
+	 `src_related'.  */
+
+      if (elt) elt = elt->first_same_value;
+      for (p = elt; p; p = p->next_same_value)
+        {
+	  enum rtx_code code = GET_CODE (p->exp);
+
+	  /* If the expression is not valid, ignore it.  Then we do not
+	     have to check for validity below.  In most cases, we can use
+	     `rtx_equal_p', since canonicalization has already been done.  */
+	  if (code != REG && ! exp_equiv_p (p->exp, p->exp, 1, 0))
+	    continue;
+
+          if (src && GET_CODE (src) == code && rtx_equal_p (src, p->exp))
+	    src = 0;
+          else if (src_folded && GET_CODE (src_folded) == code
+		   && rtx_equal_p (src_folded, p->exp))
+	    src_folded = 0;
+          else if (src_eqv_here && GET_CODE (src_eqv_here) == code
+		   && rtx_equal_p (src_eqv_here, p->exp))
+	    src_eqv_here = 0;
+          else if (src_related && GET_CODE (src_related) == code
+		   && rtx_equal_p (src_related, p->exp))
+	    src_related = 0;
+
+	  /* This is the same as the destination of the insns, we want
+	     to prefer it.  Copy it to src_related.  The code below will
+	     then give it a negative cost.  */
+	  if (GET_CODE (dest) == code && rtx_equal_p (p->exp, dest))
+	    src_related = dest;
+
+        }
+
+      /* Find the cheapest valid equivalent, trying all the available
+         possibilities.  Prefer items not in the hash table to ones
+         that are when they are equal cost.  Note that we can never
+         worsen an insn as the current contents will also succeed.
+	 If we find an equivalent identical to the source, use it as best,
+	 since this insn will probably be eliminated in that case. */
+      if (src)
+	{
+	  if (rtx_equal_p (src, dest))
+	    src_cost = -1;
+	  else
+	    src_cost = COST (src);
+	}
+
+      if (src_eqv_here)
+	{
+	  if (rtx_equal_p (src_eqv_here, dest))
+	    src_eqv_cost = -1;
+	  else
+	    src_eqv_cost = COST (src_eqv_here);
+	}
+
+      if (src_folded)
+	{
+	  if (rtx_equal_p (src_folded, dest))
+	    src_folded_cost = -1;
+	  else
+	    src_folded_cost = COST (src_folded);
+	}
+
+      if (src_related)
+	{
+	  if (rtx_equal_p (src_related, dest))
+	    src_related_cost = -1;
+	  else
+	    src_related_cost = COST (src_related);
+	}
+
+      /* If this was an indirect jump insn, a known label will really be
+	 cheaper even though it looks more expensive.  */
+      if (dest == pc_rtx && src_const && GET_CODE (src_const) == LABEL_REF)
+	src_folded = src_const, src_folded_cost = -1;
+	  
+      /* Terminate loop when replacement made.  This must terminate since
+         the current contents will be tested and will always be valid.  */
+      while (1)
+        {
+          rtx trial;
+
+          /* Skip invalid entries.  */
+          while (elt && GET_CODE (elt->exp) != REG
+	         && ! exp_equiv_p (elt->exp, elt->exp, 1, 0))
+	    elt = elt->next_same_value;	     
+	      
+          if (elt) src_elt_cost = elt->cost;
+
+          /* Find cheapest and skip it for the next time.   For items
+	     of equal cost, use this order:
+	     src_folded, src, src_eqv, src_related and hash table entry.  */
+          if (src_folded_cost <= src_cost
+	      && src_folded_cost <= src_eqv_cost
+	      && src_folded_cost <= src_related_cost
+	      && src_folded_cost <= src_elt_cost)
+	    {
+	      trial = src_folded, src_folded_cost = 10000;
+	      if (src_folded_force_flag)
+		trial = force_const_mem (mode, trial);
+	    }
+          else if (src_cost <= src_eqv_cost
+	           && src_cost <= src_related_cost
+	           && src_cost <= src_elt_cost)
+	    trial = src, src_cost = 10000;
+          else if (src_eqv_cost <= src_related_cost
+	           && src_eqv_cost <= src_elt_cost)
+	    trial = src_eqv_here, src_eqv_cost = 10000;
+          else if (src_related_cost <= src_elt_cost)
+	    trial = src_related, src_related_cost = 10000;
+          else
+	    {
+	      trial = canon_reg (copy_rtx (elt->exp), 0);
+	      elt = elt->next_same_value;
+	      src_elt_cost = 10000;
+	    }
+
+	  /* We don't normally have an insn matching (set (pc) (pc)), so
+	     check for this separately here.  We will delete such an
+	     insn below.
+
+	     Tablejump insns contain a USE of the table, so simply replacing
+	     the operand with the constant won't match.  This is simply an
+	     unconditional branch, however, and is therefore valid.  Just
+	     insert the substitution here and we will delete and re-emit
+	     the insn later.  */
+
+	  if (n_sets == 1 && dest == pc_rtx
+	      && (trial == pc_rtx
+		  || (GET_CODE (trial) == LABEL_REF
+		      && ! condjump_p (insn))))
+	    {
+	      /* If TRIAL is a label in front of a jump table, we are
+		 really falling through the switch (this is how casesi
+		 insns work), so we must branch around the table.  */
+	      if (GET_CODE (trial) == CODE_LABEL
+		  && NEXT_INSN (trial) != 0
+		  && GET_CODE (NEXT_INSN (trial)) == JUMP_INSN
+		  && (GET_CODE (PATTERN (NEXT_INSN (trial))) == ADDR_DIFF_VEC
+		      || GET_CODE (PATTERN (NEXT_INSN (trial))) == ADDR_VEC))
+
+		trial = gen_rtx (LABEL_REF, Pmode, get_label_after (trial));
+
+	      SET_SRC (sets[i].rtl) = trial;
+	      break;
+	    }
+	   
+	  /* Look for a substitution that makes a valid insn.  */
+          else if (validate_change (insn, &SET_SRC (sets[i].rtl), trial, 0))
+	    break;
+
+	  /* If we previously found constant pool entries for 
+	     constants and this is a constant, try making a
+	     pool entry.  Put it in src_folded unless we already have done
+	     this since that is where it likely came from.  */
+
+	  else if (constant_pool_entries_cost
+		   && CONSTANT_P (trial)
+		   && (src_folded == 0 || GET_CODE (src_folded) != MEM)
+		   && GET_MODE_CLASS (mode) != MODE_CC)
+	    {
+	      src_folded_force_flag = 1;
+	      src_folded = trial;
+	      src_folded_cost = constant_pool_entries_cost;
+	    }
+        }
+
+      src = SET_SRC (sets[i].rtl);
+
+      /* In general, it is good to have a SET with SET_SRC == SET_DEST.
+	 However, there is an important exception:  If both are registers
+	 that are not the head of their equivalence class, replace SET_SRC
+	 with the head of the class.  If we do not do this, we will have
+	 both registers live over a portion of the basic block.  This way,
+	 their lifetimes will likely abut instead of overlapping.  */
+      if (GET_CODE (dest) == REG
+	  && REGNO_QTY_VALID_P (REGNO (dest))
+	  && qty_mode[reg_qty[REGNO (dest)]] == GET_MODE (dest)
+	  && qty_first_reg[reg_qty[REGNO (dest)]] != REGNO (dest)
+	  && GET_CODE (src) == REG && REGNO (src) == REGNO (dest)
+	  /* Don't do this if the original insn had a hard reg as
+	     SET_SRC.  */
+	  && (GET_CODE (sets[i].src) != REG
+	      || REGNO (sets[i].src) >= FIRST_PSEUDO_REGISTER))
+	/* We can't call canon_reg here because it won't do anything if
+	   SRC is a hard register.  */
+	{
+	  int first = qty_first_reg[reg_qty[REGNO (src)]];
+
+	  src = SET_SRC (sets[i].rtl)
+	    = first >= FIRST_PSEUDO_REGISTER ? regno_reg_rtx[first]
+	      : gen_rtx (REG, GET_MODE (src), first);
+
+	  /* If we had a constant that is cheaper than what we are now
+	     setting SRC to, use that constant.  We ignored it when we
+	     thought we could make this into a no-op.  */
+	  if (src_const && COST (src_const) < COST (src)
+	      && validate_change (insn, &SET_SRC (sets[i].rtl), src_const, 0))
+	    src = src_const;
+	}
+
+      /* If we made a change, recompute SRC values.  */
+      if (src != sets[i].src)
+        {
+          do_not_record = 0;
+          hash_arg_in_memory = 0;
+          hash_arg_in_struct = 0;
+	  sets[i].src = src;
+          sets[i].src_hash_code = HASH (src, mode);
+          sets[i].src_volatile = do_not_record;
+          sets[i].src_in_memory = hash_arg_in_memory;
+          sets[i].src_in_struct = hash_arg_in_struct;
+          sets[i].src_elt = lookup (src, sets[i].src_hash_code, mode);
+        }
+
+      /* If this is a single SET, we are setting a register, and we have an
+	 equivalent constant, we want to add a REG_NOTE.   We don't want
+	 to write a REG_EQUAL note for a constant pseudo since verifying that
+	 that psuedo hasn't been eliminated is a pain.  Such a note also
+	 won't help anything.  */
+      if (n_sets == 1 && src_const && GET_CODE (dest) == REG
+	  && GET_CODE (src_const) != REG)
+	{
+	  rtx tem = find_reg_note (insn, REG_EQUAL, 0);
+	  
+	  /* Record the actual constant value in a REG_EQUAL note, making
+	     a new one if one does not already exist.  */
+	  if (tem)
+	    XEXP (tem, 0) = src_const;
+	  else
+	    REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_EQUAL,
+				        src_const, REG_NOTES (insn));
+
+          /* If storing a constant value in a register that
+	     previously held the constant value 0,
+	     record this fact with a REG_WAS_0 note on this insn.
+
+	     Note that the *register* is required to have previously held 0,
+	     not just any register in the quantity and we must point to the
+	     insn that set that register to zero.
+
+	     Rather than track each register individually, we just see if
+	     the last set for this quantity was for this register.  */
+
+	  if (REGNO_QTY_VALID_P (REGNO (dest))
+	      && qty_const[reg_qty[REGNO (dest)]] == const0_rtx)
+	    {
+	      /* See if we previously had a REG_WAS_0 note.  */
+	      rtx note = find_reg_note (insn, REG_WAS_0, 0);
+	      rtx const_insn = qty_const_insn[reg_qty[REGNO (dest)]];
+
+	      if ((tem = single_set (const_insn)) != 0
+		  && rtx_equal_p (SET_DEST (tem), dest))
+		{
+		  if (note)
+		    XEXP (note, 0) = const_insn;
+		  else
+		    REG_NOTES (insn) = gen_rtx (INSN_LIST, REG_WAS_0,
+						const_insn, REG_NOTES (insn));
+		}
+	    }
+	}
+
+      /* Now deal with the destination.  */
+      do_not_record = 0;
+      sets[i].inner_dest_loc = &SET_DEST (sets[0].rtl);
+
+      /* Look within any SIGN_EXTRACT or ZERO_EXTRACT
+	 to the MEM or REG within it.  */
+      while (GET_CODE (dest) == SIGN_EXTRACT
+	     || GET_CODE (dest) == ZERO_EXTRACT
+	     || GET_CODE (dest) == SUBREG
+	     || GET_CODE (dest) == STRICT_LOW_PART)
+	{
+	  sets[i].inner_dest_loc = &XEXP (dest, 0);
+	  dest = XEXP (dest, 0);
+	}
+
+      sets[i].inner_dest = dest;
+
+      if (GET_CODE (dest) == MEM)
+	{
+	  dest = fold_rtx (dest, insn);
+
+	  /* Decide whether we invalidate everything in memory,
+	     or just things at non-fixed places.
+	     Writing a large aggregate must invalidate everything
+	     because we don't know how long it is.  */
+	  note_mem_written (dest, &writes_memory);
+	}
+
+      /* Compute the hash code of the destination now,
+	 before the effects of this instruction are recorded,
+	 since the register values used in the address computation
+	 are those before this instruction.  */
+      sets[i].dest_hash_code = HASH (dest, mode);
+
+      /* Don't enter a bit-field in the hash table
+	 because the value in it after the store
+	 may not equal what was stored, due to truncation.  */
+
+      if (GET_CODE (SET_DEST (sets[i].rtl)) == ZERO_EXTRACT
+	  || GET_CODE (SET_DEST (sets[i].rtl)) == SIGN_EXTRACT)
+	{
+	  rtx width = XEXP (SET_DEST (sets[i].rtl), 1);
+
+	  if (src_const != 0 && GET_CODE (src_const) == CONST_INT
+	      && GET_CODE (width) == CONST_INT
+	      && INTVAL (width) < HOST_BITS_PER_INT
+	      && ! (INTVAL (src_const) & ((-1) << INTVAL (width))))
+	    /* Exception: if the value is constant,
+	       and it won't be truncated, record it.  */
+	    ;
+	  else
+	    {
+	      /* This is chosen so that the destination will be invalidated
+		 but no new value will be recorded.
+		 We must invalidate because sometimes constant
+		 values can be recorded for bitfields.  */
+	      sets[i].src_elt = 0;
+	      sets[i].src_volatile = 1;
+	      src_eqv = 0;
+	      src_eqv_elt = 0;
+	    }
+	}
+
+      /* If only one set in a JUMP_INSN and it is now a no-op, we can delete
+	 the insn.  */
+      else if (n_sets == 1 && dest == pc_rtx && src == pc_rtx)
+	{
+	  PUT_CODE (insn, NOTE);
+	  NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
+	  NOTE_SOURCE_FILE (insn) = 0;
+	  cse_jumps_altered = 1;
+	  /* One less use of the label this insn used to jump to.  */
+	  --LABEL_NUSES (JUMP_LABEL (insn));
+	  /* No more processing for this set.  */
+	  sets[i].rtl = 0;
+	}
+
+      /* If this SET is now setting PC to a label, we know it used to
+	 be a conditional or computed branch.  So we see if we can follow
+	 it.  If it was a computed branch, delete it and re-emit.  */
+      else if (dest == pc_rtx && GET_CODE (src) == LABEL_REF)
+	{
+	  rtx p;
+
+	  /* If this is not in the format for a simple branch and
+	     we are the only SET in it, re-emit it.  */
+	  if (! simplejump_p (insn) && n_sets == 1)
+	    {
+	      rtx new = emit_jump_insn_before (gen_jump (XEXP (src, 0)), insn);
+	      JUMP_LABEL (new) = XEXP (src, 0);
+	      LABEL_NUSES (XEXP (src, 0))++;
+	      delete_insn (insn);
+	      insn = new;
+	    }
+
+	  /* Now that we've converted this jump to an unconditional jump,
+	     there is dead code after it.  Delete the dead code until we
+	     reach a BARRIER, the end of the function, or a label.  Do
+	     not delete NOTEs except for NOTE_INSN_DELETED since later
+	     phases assume these notes are retained.  */
+
+	  p = insn;
+
+	  while (NEXT_INSN (p) != 0
+		 && GET_CODE (NEXT_INSN (p)) != BARRIER
+		 && GET_CODE (NEXT_INSN (p)) != CODE_LABEL)
+	    {
+	      if (GET_CODE (NEXT_INSN (p)) != NOTE
+		  || NOTE_LINE_NUMBER (NEXT_INSN (p)) == NOTE_INSN_DELETED)
+		delete_insn (NEXT_INSN (p));
+	      else
+		p = NEXT_INSN (p);
+	    }
+
+	  /* If we don't have a BARRIER immediately after INSN, put one there.
+	     Much code assumes that there are no NOTEs between a JUMP_INSN and
+	     BARRIER.  */
+
+	  if (NEXT_INSN (insn) == 0
+	      || GET_CODE (NEXT_INSN (insn)) != BARRIER)
+	    emit_barrier_after (insn);
+
+	  /* We might have two BARRIERs separated by notes.  Delete the second
+	     one if so.  */
+
+	  if (p != insn && GET_CODE (NEXT_INSN (p)) == BARRIER)
+	    delete_insn (NEXT_INSN (p));
+
+	  cse_jumps_altered = 1;
+	  sets[i].rtl = 0;
+	}
+
+      /* No further processing for this assignment if destination
+	 is volatile.  */
+
+      else if (do_not_record)
+	sets[i].rtl = 0;
+
+      if (sets[i].rtl != 0 && dest != SET_DEST (sets[i].rtl))
+	sets[i].dest_hash_code = HASH (SET_DEST (sets[i].rtl), mode);
+
+#ifdef HAVE_cc0
+      /* If setting CC0, record what it was set to, or a constant, if it
+	 is equivalent to a constant.  If it is being set to a floating-point
+	 value, make a COMPARE with the appropriate constant of 0.  If we
+	 don't do this, later code can interpret this as a test against
+	 const0_rtx, which can cause problems if we try to put it into an
+	 insn as a floating-point operand.  */
+      if (dest == cc0_rtx)
+	{
+	  this_insn_cc0 = src_const && mode != VOIDmode ? src_const : src;
+	  this_insn_cc0_mode = mode;
+	  if (GET_MODE_CLASS (mode) == MODE_FLOAT)
+	    this_insn_cc0 = gen_rtx (COMPARE, VOIDmode, this_insn_cc0,
+				     CONST0_RTX (mode));
+	}
+#endif
+    }
+
+  /* Now enter all non-volatile source expressions in the hash table
+     if they are not already present.
+     Record their equivalence classes in src_elt.
+     This way we can insert the corresponding destinations into
+     the same classes even if the actual sources are no longer in them
+     (having been invalidated).  */
+
+  if (src_eqv && src_eqv_elt == 0 && sets[0].rtl != 0 && ! src_eqv_volatile
+      && ! rtx_equal_p (src_eqv, SET_DEST (sets[0].rtl)))
+    {
+      register struct table_elt *elt;
+      register struct table_elt *classp = sets[0].src_elt;
+      rtx dest = SET_DEST (sets[0].rtl);
+      enum machine_mode eqvmode = GET_MODE (dest);
+
+      if (GET_CODE (dest) == STRICT_LOW_PART)
+	{
+	  eqvmode = GET_MODE (SUBREG_REG (XEXP (dest, 0)));
+	  classp = 0;
+	}
+      if (insert_regs (src_eqv, classp, 0))
+	src_eqv_hash_code = HASH (src_eqv, eqvmode);
+      elt = insert (src_eqv, classp, src_eqv_hash_code, eqvmode);
+      elt->in_memory = src_eqv_in_memory;
+      elt->in_struct = src_eqv_in_struct;
+      src_eqv_elt = elt;
+    }
+
+  for (i = 0; i < n_sets; i++)
+    if (sets[i].rtl && ! sets[i].src_volatile
+	&& ! rtx_equal_p (SET_SRC (sets[i].rtl), SET_DEST (sets[i].rtl)))
+      {
+	if (GET_CODE (SET_DEST (sets[i].rtl)) == STRICT_LOW_PART)
+	  {
+	    /* REG_EQUAL in setting a STRICT_LOW_PART
+	       gives an equivalent for the entire destination register,
+	       not just for the subreg being stored in now.
+	       This is a more interesting equivalence, so we arrange later
+	       to treat the entire reg as the destination.  */
+	    sets[i].src_elt = src_eqv_elt;
+	    sets[i].src_hash_code = src_eqv_hash_code;
+	  }
+	else
+	  {
+	    /* Insert source and constant equivalent into hash table, if not
+	       already present.  */
+	    register struct table_elt *classp = src_eqv_elt;
+	    register rtx src = sets[i].src;
+	    register rtx dest = SET_DEST (sets[i].rtl);
+	    enum machine_mode mode
+	      = GET_MODE (src) == VOIDmode ? GET_MODE (dest) : GET_MODE (src);
+
+	    if (sets[i].src_elt == 0)
+	      {
+		register struct table_elt *elt;
+
+		/* Note that these insert_regs calls cannot remove
+		   any of the src_elt's, because they would have failed to
+		   match if not still valid.  */
+		if (insert_regs (src, classp, 0))
+		  sets[i].src_hash_code = HASH (src, mode);
+		elt = insert (src, classp, sets[i].src_hash_code, mode);
+		elt->in_memory = sets[i].src_in_memory;
+		elt->in_struct = sets[i].src_in_struct;
+		sets[i].src_elt = classp = elt;
+	      }
+
+	    if (sets[i].src_const && sets[i].src_const_elt == 0
+		&& src != sets[i].src_const
+		&& ! rtx_equal_p (sets[i].src_const, src))
+	      sets[i].src_elt = insert (sets[i].src_const, classp,
+					sets[i].src_const_hash_code, mode);
+	  }
+      }
+    else if (sets[i].src_elt == 0)
+      /* If we did not insert the source into the hash table (e.g., it was
+	 volatile), note the equivalence class for the REG_EQUAL value, if any,
+	 so that the destination goes into that class.  */
+      sets[i].src_elt = src_eqv_elt;
+
+  invalidate_from_clobbers (&writes_memory, x);
+  /* Memory, and some registers, are invalidate by subroutine calls.  */
+  if (GET_CODE (insn) == CALL_INSN)
+    {
+      static struct write_data everything = {0, 1, 1, 1};
+      invalidate_memory (&everything);
+      invalidate_for_call ();
+    }
+
+  /* Now invalidate everything set by this instruction.
+     If a SUBREG or other funny destination is being set,
+     sets[i].rtl is still nonzero, so here we invalidate the reg
+     a part of which is being set.  */
+
+  for (i = 0; i < n_sets; i++)
+    if (sets[i].rtl)
+      {
+	register rtx dest = sets[i].inner_dest;
+
+	/* Needed for registers to remove the register from its
+	   previous quantity's chain.
+	   Needed for memory if this is a nonvarying address, unless
+	   we have just done an invalidate_memory that covers even those.  */
+	if (GET_CODE (dest) == REG || GET_CODE (dest) == SUBREG
+	    || (! writes_memory.all && ! cse_rtx_addr_varies_p (dest)))
+	  invalidate (dest);
+      }
+
+  /* Make sure registers mentioned in destinations
+     are safe for use in an expression to be inserted.
+     This removes from the hash table
+     any invalid entry that refers to one of these registers.
+
+     We don't care about the return value from mention_regs because
+     we are going to hash the SET_DEST values unconditionally.  */
+
+  for (i = 0; i < n_sets; i++)
+    if (sets[i].rtl && GET_CODE (SET_DEST (sets[i].rtl)) != REG)
+      mention_regs (SET_DEST (sets[i].rtl));
+
+  /* We may have just removed some of the src_elt's from the hash table.
+     So replace each one with the current head of the same class.  */
+
+  for (i = 0; i < n_sets; i++)
+    if (sets[i].rtl)
+      {
+	if (sets[i].src_elt && sets[i].src_elt->first_same_value == 0)
+	  /* If elt was removed, find current head of same class,
+	     or 0 if nothing remains of that class.  */
+	  {
+	    register struct table_elt *elt = sets[i].src_elt;
+
+	    while (elt && elt->prev_same_value)
+	      elt = elt->prev_same_value;
+
+	    while (elt && elt->first_same_value == 0)
+	      elt = elt->next_same_value;
+	    sets[i].src_elt = elt ? elt->first_same_value : 0;
+	  }
+      }
+
+  /* Now insert the destinations into their equivalence classes.  */
+
+  for (i = 0; i < n_sets; i++)
+    if (sets[i].rtl)
+      {
+	register rtx dest = SET_DEST (sets[i].rtl);
+	register struct table_elt *elt;
+
+	/* Don't record value if we are not supposed to risk allocating
+	   floating-point values in registers that might be wider than
+	   memory.  */
+	if ((flag_float_store
+	     && GET_CODE (dest) == MEM
+	     && GET_MODE_CLASS (GET_MODE (dest)) == MODE_FLOAT)
+	    /* Don't record values of destinations set inside a libcall block
+	       since we might delete the libcall.  Things should have been set
+	       up so we won't want to reuse such a value, but we play it safe
+	       here.  */
+	    || in_libcall_block
+	    /* If we didn't put a REG_EQUAL value or a source into the hash
+	       table, there is no point is recording DEST.  */
+	     || sets[i].src_elt == 0)
+	  continue;
+
+	/* STRICT_LOW_PART isn't part of the value BEING set,
+	   and neither is the SUBREG inside it.
+	   Note that in this case SETS[I].SRC_ELT is really SRC_EQV_ELT.  */
+	if (GET_CODE (dest) == STRICT_LOW_PART)
+	  dest = SUBREG_REG (XEXP (dest, 0));
+
+	if (GET_CODE (dest) == REG)
+	  /* Registers must also be inserted into chains for quantities.  */
+	  if (insert_regs (dest, sets[i].src_elt, 1))
+	    /* If `insert_regs' changes something, the hash code must be
+	       recalculated.  */
+	    sets[i].dest_hash_code = HASH (dest, GET_MODE (dest));
+
+	elt = insert (dest, sets[i].src_elt,
+		      sets[i].dest_hash_code, GET_MODE (dest));
+	elt->in_memory = GET_CODE (sets[i].inner_dest) == MEM;
+	if (elt->in_memory)
+	  {
+	    /* This implicitly assumes a whole struct
+	       need not have MEM_IN_STRUCT_P.
+	       But a whole struct is *supposed* to have MEM_IN_STRUCT_P.  */
+	    elt->in_struct = (MEM_IN_STRUCT_P (sets[i].inner_dest)
+			      || sets[i].inner_dest != SET_DEST (sets[i].rtl));
+	  }
+
+	/* If we have (set (subreg:m1 (reg:m2 foo) 0) (bar:m1)), M1 is wider
+	   than M2, and both M1 and M2 are a single word, we are also doing
+	   (set (reg:m2 foo) (subreg:m2 (bar:m1 0))) so make that equivalence
+	   as well.
+
+	   However, BAR may have equivalences for which gen_lowpart_if_possible
+	   will produce a simpler value than gen_lowpart_if_possible applied to
+	   BAR (e.g., if BAR was ZERO_EXTENDed from M2), so we will scan all
+	   BAR's equivalences.  If we don't get a simplified form, make 
+	   the SUBREG.  It will not be used in an equivalence, but will
+	   cause two similar assignments to be detected.
+
+	   Note the loop below will find SUBREG_REG (DEST) since we have
+	   already entered SRC and DEST of the SET in the table.  */
+
+	if (GET_CODE (dest) == SUBREG
+	    && GET_MODE_SIZE (GET_MODE (dest)) <= UNITS_PER_WORD
+	    && GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))) <= UNITS_PER_WORD
+	    && (GET_MODE_SIZE (GET_MODE (dest))
+		>= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))))
+	    && sets[i].src_elt != 0)
+	  {
+	    enum machine_mode new_mode = GET_MODE (SUBREG_REG (dest));
+	    struct table_elt *elt, *classp = 0;
+
+	    for (elt = sets[i].src_elt->first_same_value; elt;
+		 elt = elt->next_same_value)
+	      {
+		rtx new_src = 0;
+		int src_hash;
+		struct table_elt *src_elt;
+
+		/* Ignore invalid entries.  */
+		if (GET_CODE (elt->exp) != REG
+		    && ! exp_equiv_p (elt->exp, elt->exp, 1, 0))
+		  continue;
+
+		new_src = gen_lowpart_if_possible (new_mode, elt->exp);
+		if (new_src == 0)
+		  new_src = gen_rtx (SUBREG, new_mode, elt->exp, 0);
+
+		src_hash = HASH (new_src, new_mode);
+		src_elt = lookup (new_src, src_hash, new_mode);
+
+		/* Put the new source in the hash table is if isn't
+		   already.  */
+		if (src_elt == 0)
+		  {
+		    if (insert_regs (new_src, classp, 0))
+		      src_hash = HASH (new_src, new_mode);
+		    src_elt = insert (new_src, classp, src_hash, new_mode);
+		    src_elt->in_memory = elt->in_memory;
+		    src_elt->in_struct = elt->in_struct;
+		  }
+		else if (classp && classp != src_elt->first_same_value)
+		  /* Show that two things that we've seen before are 
+		     actually the same.  */
+		  merge_equiv_classes (src_elt, classp);
+
+		classp = src_elt->first_same_value;
+	      }
+	  }
+      }
+
+  /* Special handling for (set REG0 REG1)
+     where REG0 is the "cheapest", cheaper than REG1.
+     After cse, REG1 will probably not be used in the sequel, 
+     so (if easily done) change this insn to (set REG1 REG0) and
+     replace REG1 with REG0 in the previous insn that computed their value.
+     Then REG1 will become a dead store and won't cloud the situation
+     for later optimizations.
+
+     Do not make this change if REG1 is a hard register, because it will
+     then be used in the sequel and we may be changing a two-operand insn
+     into a three-operand insn.
+
+     Also do not do this if we are operating on a copy of INSN.  */
+
+  if (n_sets == 1 && sets[0].rtl && GET_CODE (SET_DEST (sets[0].rtl)) == REG
+      && NEXT_INSN (PREV_INSN (insn)) == insn
+      && GET_CODE (SET_SRC (sets[0].rtl)) == REG
+      && REGNO (SET_SRC (sets[0].rtl)) >= FIRST_PSEUDO_REGISTER
+      && REGNO_QTY_VALID_P (REGNO (SET_SRC (sets[0].rtl)))
+      && (qty_first_reg[reg_qty[REGNO (SET_SRC (sets[0].rtl))]]
+	  == REGNO (SET_DEST (sets[0].rtl))))
+    {
+      rtx prev = PREV_INSN (insn);
+      while (prev && GET_CODE (prev) == NOTE)
+	prev = PREV_INSN (prev);
+
+      if (prev && GET_CODE (prev) == INSN && GET_CODE (PATTERN (prev)) == SET
+	  && SET_DEST (PATTERN (prev)) == SET_SRC (sets[0].rtl))
+	{
+	  rtx dest = SET_DEST (sets[0].rtl);
+	  rtx note = find_reg_note (prev, REG_EQUIV, 0);
+
+	  validate_change (prev, & SET_DEST (PATTERN (prev)), dest, 1);
+	  validate_change (insn, & SET_DEST (sets[0].rtl),
+			   SET_SRC (sets[0].rtl), 1);
+	  validate_change (insn, & SET_SRC (sets[0].rtl), dest, 1);
+	  apply_change_group ();
+
+	  /* If REG1 was equivalent to a constant, REG0 is not.  */
+	  if (note)
+	    PUT_REG_NOTE_KIND (note, REG_EQUAL);
+
+	  /* If there was a REG_WAS_0 note on PREV, remove it.  Move
+	     any REG_WAS_0 note on INSN to PREV.  */
+	  note = find_reg_note (prev, REG_WAS_0, 0);
+	  if (note)
+	    remove_note (prev, note);
+
+	  note = find_reg_note (insn, REG_WAS_0, 0);
+	  if (note)
+	    {
+	      remove_note (insn, note);
+	      XEXP (note, 1) = REG_NOTES (prev);
+	      REG_NOTES (prev) = note;
+	    }
+	}
+    }
+
+  /* If this is a conditional jump insn, record any known equivalences due to
+     the condition being tested.  */
+
+  last_jump_equiv_class = 0;
+  if (GET_CODE (insn) == JUMP_INSN
+      && n_sets == 1 && GET_CODE (x) == SET
+      && GET_CODE (SET_SRC (x)) == IF_THEN_ELSE)
+    record_jump_equiv (insn, 0);
+
+#ifdef HAVE_cc0
+  /* If the previous insn set CC0 and this insn no longer references CC0,
+     delete the previous insn.  Here we use the fact that nothing expects CC0
+     to be valid over an insn, which is true until the final pass.  */
+  if (prev_insn && GET_CODE (prev_insn) == INSN
+      && (tem = single_set (prev_insn)) != 0
+      && SET_DEST (tem) == cc0_rtx
+      && ! reg_mentioned_p (cc0_rtx, x))
+    {
+      PUT_CODE (prev_insn, NOTE);
+      NOTE_LINE_NUMBER (prev_insn) = NOTE_INSN_DELETED;
+      NOTE_SOURCE_FILE (prev_insn) = 0;
+    }
+
+  prev_insn_cc0 = this_insn_cc0;
+  prev_insn_cc0_mode = this_insn_cc0_mode;
+#endif
+
+  prev_insn = insn;
+}
+
+/* Store 1 in *WRITES_PTR for those categories of memory ref
+   that must be invalidated when the expression WRITTEN is stored in.
+   If WRITTEN is null, say everything must be invalidated.  */
+
+static void
+note_mem_written (written, writes_ptr)
+     rtx written;
+     struct write_data *writes_ptr;
+{
+  static struct write_data everything = {0, 1, 1, 1};
+
+  if (written == 0)
+    *writes_ptr = everything;
+  else if (GET_CODE (written) == MEM)
+    {
+      /* Pushing or popping the stack invalidates just the stack pointer. */
+      rtx addr = XEXP (written, 0);
+      if ((GET_CODE (addr) == PRE_DEC || GET_CODE (addr) == PRE_INC
+	   || GET_CODE (addr) == POST_DEC || GET_CODE (addr) == POST_INC)
+	  && GET_CODE (XEXP (addr, 0)) == REG
+	  && REGNO (XEXP (addr, 0)) == STACK_POINTER_REGNUM)
+	{
+	  writes_ptr->sp = 1;
+	  return;
+	}
+      else if (GET_MODE (written) == BLKmode)
+	*writes_ptr = everything;
+      else if (cse_rtx_addr_varies_p (written))
+	{
+	  /* A varying address that is a sum indicates an array element,
+	     and that's just as good as a structure element
+	     in implying that we need not invalidate scalar variables.  */
+	  if (!(MEM_IN_STRUCT_P (written)
+		|| GET_CODE (XEXP (written, 0)) == PLUS))
+	    writes_ptr->all = 1;
+	  writes_ptr->nonscalar = 1;
+	}
+      writes_ptr->var = 1;
+    }
+}
+
+/* Perform invalidation on the basis of everything about an insn
+   except for invalidating the actual places that are SET in it.
+   This includes the places CLOBBERed, and anything that might
+   alias with something that is SET or CLOBBERed.
+
+   W points to the writes_memory for this insn, a struct write_data
+   saying which kinds of memory references must be invalidated.
+   X is the pattern of the insn.  */
+
+static void
+invalidate_from_clobbers (w, x)
+     struct write_data *w;
+     rtx x;
+{
+  /* If W->var is not set, W specifies no action.
+     If W->all is set, this step gets all memory refs
+     so they can be ignored in the rest of this function.  */
+  if (w->var)
+    invalidate_memory (w);
+
+  if (w->sp)
+    {
+      if (reg_tick[STACK_POINTER_REGNUM] >= 0)
+	reg_tick[STACK_POINTER_REGNUM]++;
+
+      /* This should be *very* rare.  */
+      if (TEST_HARD_REG_BIT (hard_regs_in_table, STACK_POINTER_REGNUM))
+	invalidate (stack_pointer_rtx);
+    }
+
+  if (GET_CODE (x) == CLOBBER)
+    {
+      rtx ref = XEXP (x, 0);
+      if (ref
+	  && (GET_CODE (ref) == REG || GET_CODE (ref) == SUBREG
+	      || (GET_CODE (ref) == MEM && ! w->all)))
+	invalidate (ref);
+    }
+  else if (GET_CODE (x) == PARALLEL)
+    {
+      register int i;
+      for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
+	{
+	  register rtx y = XVECEXP (x, 0, i);
+	  if (GET_CODE (y) == CLOBBER)
+	    {
+	      rtx ref = XEXP (y, 0);
+	      if (ref
+		  &&(GET_CODE (ref) == REG || GET_CODE (ref) == SUBREG
+		     || (GET_CODE (ref) == MEM && !w->all)))
+		invalidate (ref);
+	    }
+	}
+    }
+}
+
+/* Process X, part of the REG_NOTES of an insn.  Look at any REG_EQUAL notes
+   and replace any registers in them with either an equivalent constant
+   or the canonical form of the register.  If we are inside an address,
+   only do this if the address remains valid.
+
+   OBJECT is 0 except when within a MEM in which case it is the MEM.
+
+   Return the replacement for X.  */
+
+static rtx
+cse_process_notes (x, object)
+     rtx x;
+     rtx object;
+{
+  enum rtx_code code = GET_CODE (x);
+  char *fmt = GET_RTX_FORMAT (code);
+  int qty;
+  int i;
+
+  switch (code)
+    {
+    case CONST_INT:
+    case CONST:
+    case SYMBOL_REF:
+    case LABEL_REF:
+    case CONST_DOUBLE:
+    case PC:
+    case CC0:
+    case LO_SUM:
+      return x;
+
+    case MEM:
+      XEXP (x, 0) = cse_process_notes (XEXP (x, 0), x);
+      return x;
+
+    case EXPR_LIST:
+    case INSN_LIST:
+      if (REG_NOTE_KIND (x) == REG_EQUAL)
+	XEXP (x, 0) = cse_process_notes (XEXP (x, 0), 0);
+      if (XEXP (x, 1))
+	XEXP (x, 1) = cse_process_notes (XEXP (x, 1), 0);
+      return x;
+
+    case REG:
+      i = reg_qty[REGNO (x)];
+
+      /* Return a constant or a constant register.  */
+      if (REGNO_QTY_VALID_P (REGNO (x))
+	  && qty_const[i] != 0
+	  && (CONSTANT_P (qty_const[i])
+	      || GET_CODE (qty_const[i]) == REG))
+	{
+	  rtx new = gen_lowpart_if_possible (GET_MODE (x), qty_const[i]);
+	  if (new)
+	    return new;
+	}
+
+      /* Otherwise, canonicalize this register.  */
+      return canon_reg (x, 0);
+    }
+
+  for (i = 0; i < GET_RTX_LENGTH (code); i++)
+    if (fmt[i] == 'e')
+      validate_change (object, &XEXP (x, i),
+		       cse_process_notes (XEXP (x, i), object), 0);
+
+  return x;
+}
+
+/* Find common subexpressions between the end test of a loop and the beginning
+   of the loop.  LOOP_START is the CODE_LABEL at the start of a loop.
+
+   Often we have a loop where an expression in the exit test is used
+   in the body of the loop.  For example "while (*p) *q++ = *p++;".
+   Because of the way we duplicate the loop exit test in front of the loop,
+   however, we don't detect that common subexpression.  This will be caught
+   when global cse is implemented, but this is a quite common case.
+
+   This function handles the most common cases of these common expressions.
+   It is called after we have processed the basic block ending with the
+   NOTE_INSN_LOOP_END note that ends a loop and the previous JUMP_INSN
+   jumps to a label used only once.  */
+
+static void
+cse_around_loop (loop_start)
+     rtx loop_start;
+{
+  rtx insn;
+  int i;
+  struct table_elt *p;
+
+  /* If the jump at the end of the loop doesn't go to the start, we don't
+     do anything.  */
+  for (insn = PREV_INSN (loop_start);
+       insn && (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) >= 0);
+       insn = PREV_INSN (insn))
+    ;
+
+  if (insn == 0
+      || GET_CODE (insn) != NOTE
+      || NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG)
+    return;
+
+  /* If the last insn of the loop (the end test) was an NE comparison,
+     we will interpret it as an EQ comparison, since we fell through
+     the loop.  Any equivalances resulting from that comparison are
+     therefore not valid and must be invalidated.  */
+  if (last_jump_equiv_class)
+    for (p = last_jump_equiv_class->first_same_value; p;
+	 p = p->next_same_value)
+      if (GET_CODE (p->exp) == MEM || GET_CODE (p->exp) == REG
+	  || GET_CODE (p->exp) == SUBREG)
+	invalidate (p->exp);
+
+  /* Process insns starting after LOOP_START until we hit a CALL_INSN or
+     a CODE_LABEL (we could handle a CALL_INSN, but it isn't worth it).
+
+     The only thing we do with SET_DEST is invalidate entries, so we
+     can safely process each SET in order.  It is slightly less efficient
+     to do so, but we only want to handle the most common cases.  */
+
+  for (insn = NEXT_INSN (loop_start);
+       GET_CODE (insn) != CALL_INSN && GET_CODE (insn) != CODE_LABEL
+       && ! (GET_CODE (insn) == NOTE
+	     && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END);
+       insn = NEXT_INSN (insn))
+    {
+      if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
+	  && (GET_CODE (PATTERN (insn)) == SET
+	      || GET_CODE (PATTERN (insn)) == CLOBBER))
+	cse_set_around_loop (PATTERN (insn), insn, loop_start);
+      else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
+	       && GET_CODE (PATTERN (insn)) == PARALLEL)
+	for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
+	  if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == SET
+	      || GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == CLOBBER)
+	    cse_set_around_loop (XVECEXP (PATTERN (insn), 0, i), insn,
+				 loop_start);
+    }
+}
+
+/* Used for communication between the following two routines; contains a
+   value to be checked for modification.  */
+
+static rtx cse_check_loop_start_value;
+
+/* If modifying X will modify the value in CSE_CHECK_LOOP_START_VALUE,
+   indicate that fact by setting CSE_CHECK_LOOP_START_VALUE to 0.  */
+
+static void
+cse_check_loop_start (x, set)
+     rtx x;
+     rtx set;
+{
+  if (cse_check_loop_start_value == 0
+      || GET_CODE (x) == CC0 || GET_CODE (x) == PC)
+    return;
+
+  if ((GET_CODE (x) == MEM && GET_CODE (cse_check_loop_start_value) == MEM)
+      || reg_overlap_mentioned_p (x, cse_check_loop_start_value))
+    cse_check_loop_start_value = 0;
+}
+
+/* X is a SET or CLOBBER contained in INSN that was found near the start of
+   a loop that starts with the label at LOOP_START.
+
+   If X is a SET, we see if its SET_SRC is currently in our hash table.
+   If so, we see if it has a value equal to some register used only in the
+   loop exit code (as marked by jump.c).
+
+   If those two conditions are true, we search backwards from the start of
+   the loop to see if that same value was loaded into a register that still
+   retains its value at the start of the loop.
+
+   If so, we insert an insn after the load to copy the destination of that
+   load into the equivalent register and (try to) replace our SET_SRC with that
+   register.
+
+   In any event, we invalidate whatever this SET or CLOBBER modifies.  */
+
+static void
+cse_set_around_loop (x, insn, loop_start)
+     rtx x;
+     rtx insn;
+     rtx loop_start;
+{
+  rtx p;
+  struct table_elt *src_elt;
+  static struct write_data init = {0, 0, 0, 0};
+  struct write_data writes_memory;
+
+  writes_memory = init;
+
+  /* If this is a SET, see if we can replace SET_SRC, but ignore SETs that
+     are setting PC or CC0 or whose SET_SRC is already a register.  */
+  if (GET_CODE (x) == SET
+      && GET_CODE (SET_DEST (x)) != PC && GET_CODE (SET_DEST (x)) != CC0
+      && GET_CODE (SET_SRC (x)) != REG)
+    {
+      src_elt = lookup (SET_SRC (x),
+			HASH (SET_SRC (x), GET_MODE (SET_DEST (x))),
+			GET_MODE (SET_DEST (x)));
+
+      if (src_elt)
+	for (src_elt = src_elt->first_same_value; src_elt;
+	     src_elt = src_elt->next_same_value)
+	  if (GET_CODE (src_elt->exp) == REG && REG_LOOP_TEST_P (src_elt->exp)
+	      && COST (src_elt->exp) < COST (SET_SRC (x)))
+	    {
+	      rtx p, set;
+
+	      /* Look for an insn in front of LOOP_START that sets
+		 something in the desired mode to SET_SRC (x) before we hit
+		 a label or CALL_INSN.  */
+
+	      for (p = prev_nonnote_insn (loop_start);
+		   p && GET_CODE (p) != CALL_INSN
+		   && GET_CODE (p) != CODE_LABEL;
+		   p = prev_nonnote_insn  (p))
+		if ((set = single_set (p)) != 0
+		    && GET_CODE (SET_DEST (set)) == REG
+		    && GET_MODE (SET_DEST (set)) == src_elt->mode
+		    && rtx_equal_p (SET_SRC (set), SET_SRC (x)))
+		  {
+		    /* We now have to ensure that nothing between P
+		       and LOOP_START modified anything referenced in
+		       SET_SRC (x).  We know that nothing within the loop
+		       can modify it, or we would have invalidated it in
+		       the hash table.  */
+		    rtx q;
+
+		    cse_check_loop_start_value = SET_SRC (x);
+		    for (q = p; q != loop_start; q = NEXT_INSN (q))
+		      if (GET_RTX_CLASS (GET_CODE (q)) == 'i')
+			note_stores (PATTERN (q), cse_check_loop_start);
+
+		    /* If nothing was changed and we can replace our
+		       SET_SRC, add an insn after P to copy its destination
+		       to what we will be replacing SET_SRC with.  */
+		    if (cse_check_loop_start_value
+			&& validate_change (insn, &SET_SRC (x),
+					    src_elt->exp, 0))
+		      emit_insn_after (gen_move_insn (src_elt->exp,
+						      SET_DEST (set)),
+				       p);
+		    break;
+		  }
+	    }
+    }
+
+  /* Now invalidate anything modified by X.  */
+  note_mem_written (SET_DEST (x), &writes_memory);
+
+  if (writes_memory.var)
+    invalidate_memory (&writes_memory);
+
+  /* See comment on similar code in cse_insn for explanation of these tests. */
+  if (GET_CODE (SET_DEST (x)) == REG || GET_CODE (SET_DEST (x)) == SUBREG
+      || (GET_CODE (SET_DEST (x)) == MEM && ! writes_memory.all
+	  && ! cse_rtx_addr_varies_p (SET_DEST (x))))
+    invalidate (SET_DEST (x));
+}
+
+/* Find the end of INSN's basic block and return its range,
+   the total number of SETs in all the insns of the block, the last insn of the
+   block, and the branch path.
+
+   The branch path indicates which branches should be followed.  If a non-zero
+   path size is specified, the block should be rescanned and a different set
+   of branches will be taken.  The branch path is only used if
+   FLAG_CSE_FOLLOW_JUMPS is non-zero.
+
+   DATA is a pointer to a struct cse_basic_block_data, defined below, that is
+   used to describe the block.  It is filled in with the information about
+   the current block.  The incoming structure's branch path, if any, is used
+   to construct the output branch path.  */
+
+/* Define maximum length of a branch path.  */
+
+#define PATHLENGTH	20
+
+struct cse_basic_block_data {
+  /* Lowest CUID value of insns in block.  */
+  int low_cuid;
+  /* Highest CUID value of insns in block.  */
+  int high_cuid;
+  /* Total number of SETs in block.  */
+  int nsets;
+  /* Last insn in the block.  */
+  rtx last;
+  /* Size of current branch path, if any.  */
+  int path_size;
+  /* Current branch path, indicating which branches will be taken.  */
+  struct branch_path {
+    /* The branch insn. */
+    rtx branch;
+    /* Whether it should be taken or not.  */
+    enum taken {TAKEN, NOT_TAKEN} status;
+  } path[PATHLENGTH];
+};
+
+void
+cse_end_of_basic_block (insn, data, follow_jumps, after_loop)
+     rtx insn;
+     struct cse_basic_block_data *data;
+     int follow_jumps;
+     int after_loop;
+{
+  rtx p = insn, q;
+  int nsets = 0;
+  int low_cuid = INSN_CUID (insn), high_cuid = INSN_CUID (insn);
+  int path_size = data->path_size;
+  int path_entry = 0;
+  int i;
+
+  /* Update the previous branch path, if any.  If the last branch was
+     previously TAKEN, mark it NOT_TAKEN.  If it was previously NOT_TAKEN,
+     shorten the path by one and look at the previous branch.  We know that
+     at least one branch must have been taken if PATH_SIZE is non-zero.  */
+  while (path_size > 0)
+    {
+      if (data->path[path_size - 1].status == TAKEN)
+	{
+	  data->path[path_size - 1].status = NOT_TAKEN;
+	  break;
+	}
+      else
+	path_size--;
+    }
+
+  /* Scan to end of this basic block.  */
+  while (p && GET_CODE (p) != CODE_LABEL)
+    {
+      /* Don't cse out the end of a loop.  This makes a difference
+	 only for the unusual loops that always execute at least once;
+	 all other loops have labels there so we will stop in any case.
+	 Cse'ing out the end of the loop is dangerous because it
+	 might cause an invariant expression inside the loop
+	 to be reused after the end of the loop.  This would make it
+	 hard to move the expression out of the loop in loop.c,
+	 especially if it is one of several equivalent expressions
+	 and loop.c would like to eliminate it.
+
+	 If we are running after loop.c has finished, we can ignore
+	 the NOTE_INSN_LOOP_END.  */
+
+      if (! after_loop && GET_CODE (p) == NOTE
+	  && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
+	break;
+
+      /* Don't cse over a call to setjmp; on some machines (eg vax)
+	 the regs restored by the longjmp come from
+	 a later time than the setjmp.  */
+      if (GET_CODE (p) == NOTE
+	  && NOTE_LINE_NUMBER (p) == NOTE_INSN_SETJMP)
+	break;
+
+      /* A PARALLEL can have lots of SETs in it,
+	 especially if it is really an ASM_OPERANDS.  */
+      if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
+	  && GET_CODE (PATTERN (p)) == PARALLEL)
+	nsets += XVECLEN (PATTERN (p), 0);
+      else if (GET_CODE (p) != NOTE)
+	nsets += 1;
+	
+      if (INSN_CUID (p) > high_cuid)
+        high_cuid = INSN_CUID (p);
+      if (INSN_CUID (p) < low_cuid)
+        low_cuid = INSN_CUID(p);
+
+      /* See if this insn is in our branch path.  If it is and we are to
+	 take it, do so.  */
+      if (path_entry < path_size && data->path[path_entry].branch == p)
+	{
+	  if (data->path[path_entry].status == TAKEN)
+	    p = JUMP_LABEL (p);
+	  
+	  /* Point to next entry in path, if any.  */
+	  path_entry++;
+	}
+
+      /* If this is a conditional jump, we can follow it if -fcse-follow-jumps
+	 was specified, we haven't reached our maximum path length, there are
+	 insns following the target of the jump, this is the only use of the
+	 jump label, and the target label is preceeded by a BARRIER.  */
+      else if (follow_jumps && path_size < PATHLENGTH - 1
+	       && GET_CODE (p) == JUMP_INSN
+      	       && GET_CODE (PATTERN (p)) == SET
+	       && GET_CODE (SET_SRC (PATTERN (p))) == IF_THEN_ELSE
+	       && LABEL_NUSES (JUMP_LABEL (p)) == 1
+	       && NEXT_INSN (JUMP_LABEL (p)) != 0)
+	{
+	  for (q = PREV_INSN (JUMP_LABEL (p)); q; q = PREV_INSN (q))
+	    if ((GET_CODE (q) != NOTE
+	         || NOTE_LINE_NUMBER (q) == NOTE_INSN_LOOP_END
+	         || NOTE_LINE_NUMBER (q) == NOTE_INSN_SETJMP)
+	        && (GET_CODE (q) != CODE_LABEL || LABEL_NUSES (q) != 0))
+	      break;
+
+	  /* If we ran into a BARRIER, this code is an extension of the
+	     basic block when the branch is taken.  */
+	  if (q != 0 && GET_CODE (q) == BARRIER)
+	    {
+	      /* Don't allow ourself to keep walking around an
+		 always-executed loop.  */
+	      if (next_real_insn (q) == next_real_insn (insn))
+		break;
+
+	      /* Similarly, don't put a branch in our path more than once.  */
+	      for (i = 0; i < path_entry; i++)
+		if (data->path[i].branch == p)
+		  break;
+
+	      if (i != path_entry)
+		break;
+
+	      data->path[path_entry].branch = p;
+	      data->path[path_entry++].status = TAKEN;
+
+	      /* This branch now ends our path.  It was possible that we
+		 didn't see this branch the last time around (when the
+		 insn in front of the target was a JUMP_INSN that was
+		 turned into a no-op).  */
+	      path_size = path_entry;
+
+	      p = JUMP_LABEL (p);
+	      /* Mark block so we won't scan it again later.  */
+	      PUT_MODE (NEXT_INSN (p), QImode);
+	    }
+	}
+	
+      p = NEXT_INSN (p);
+    }
+
+  data->low_cuid = low_cuid;
+  data->high_cuid = high_cuid;
+  data->nsets = nsets;
+  data->last = p;
+
+  /* If all jumps in the path are not taken, set our path length to zero
+     so a rescan won't be done.  */
+  for (i = path_size - 1; i >= 0; i--)
+    if (data->path[i].status == TAKEN)
+      break;
+
+  if (i == -1)
+    data->path_size = 0;
+  else
+    data->path_size = path_size;
+
+  /* End the current branch path.  */
+  data->path[path_size].branch = 0;
+}
+
+static rtx cse_basic_block ();
+
+/* Perform cse on the instructions of a function.
+   F is the first instruction.
+   NREGS is one plus the highest pseudo-reg number used in the instruction.
+
+   AFTER_LOOP is 1 if this is the cse call done after loop optimization
+   (only if -frerun-cse-after-loop).
+
+   Returns 1 if jump_optimize should be redone due to simplifications
+   in conditional jump instructions.  */
+
+int
+cse_main (f, nregs, after_loop, file)
+     rtx f;
+     int nregs;
+     int after_loop;
+     FILE *file;
+{
+  struct cse_basic_block_data val;
+  register rtx insn = f;
+  register int i;
+
+  cse_jumps_altered = 0;
+  constant_pool_entries_cost = 0;
+  val.path_size = 0;
+
+  init_recog ();
+
+  max_reg = nregs;
+
+  all_minus_one = (int *) alloca (nregs * sizeof (int));
+  consec_ints = (int *) alloca (nregs * sizeof (int));
+
+  for (i = 0; i < nregs; i++)
+    {
+      all_minus_one[i] = -1;
+      consec_ints[i] = i;
+    }
+
+  reg_next_eqv = (int *) alloca (nregs * sizeof (int));
+  reg_prev_eqv = (int *) alloca (nregs * sizeof (int));
+  reg_qty = (int *) alloca (nregs * sizeof (int));
+  reg_in_table = (int *) alloca (nregs * sizeof (int));
+  reg_tick = (int *) alloca (nregs * sizeof (int));
+
+  /* Discard all the free elements of the previous function
+     since they are allocated in the temporarily obstack.  */
+  bzero (table, sizeof table);
+  free_element_chain = 0;
+  n_elements_made = 0;
+
+  /* Find the largest uid.  */
+
+  i = get_max_uid ();
+  uid_cuid = (short *) alloca ((i + 1) * sizeof (short));
+  bzero (uid_cuid, (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.
+     Don't assign cuids to line-number NOTEs, so that the distance in cuids
+     between two insns is not affected by -g.  */
+
+  for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
+    {
+      if (GET_CODE (insn) != NOTE
+	  || NOTE_LINE_NUMBER (insn) < 0)
+	INSN_CUID (insn) = ++i;
+      else
+	/* Give a line number note the same cuid as preceding insn.  */
+	INSN_CUID (insn) = i;
+    }
+
+  /* Initialize which registers are clobbered by calls.  */
+
+  CLEAR_HARD_REG_SET (regs_invalidated_by_call);
+
+  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+    if ((call_used_regs[i]
+	 /* Used to check !fixed_regs[i] here, but that isn't safe;
+	    fixed regs are still call-clobbered, and sched can get
+	    confused if they can "live across calls".
+
+	    The frame pointer is always preserved across calls.  The arg
+	    pointer is if it is fixed.  The stack pointer usually is, unless
+	    RETURN_POPS_ARGS, in which case an explicit CLOBBER
+	    will be present.  If we are generating PIC code, the PIC offset
+	    table register is preserved across calls.  */
+
+	 && i != STACK_POINTER_REGNUM
+	 && i != FRAME_POINTER_REGNUM
+#if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
+	 && ! (i == ARG_POINTER_REGNUM && fixed_regs[i])
+#endif
+#ifdef PIC_OFFSET_TABLE_REGNUM
+	 && ! (i == PIC_OFFSET_TABLE_REGNUM && flag_pic)
+#endif
+	 )
+	|| global_regs[i])
+      SET_HARD_REG_BIT (regs_invalidated_by_call, i);
+
+  /* Loop over basic blocks.
+     Compute the maximum number of qty's needed for each basic block
+     (which is 2 for each SET).  */
+  insn = f;
+  while (insn)
+    {
+      int tem;
+
+      cse_end_of_basic_block (insn, &val, flag_cse_follow_jumps, after_loop);
+
+      /* If this basic block was already processed or has no sets, skip it.  */
+      if (val.nsets == 0 || GET_MODE (insn) == QImode)
+	{
+	  PUT_MODE (insn, VOIDmode);
+	  insn = (val.last ? NEXT_INSN (val.last) : 0);
+	  val.path_size = 0;
+	  continue;
+	}
+
+      cse_basic_block_start = val.low_cuid;
+      cse_basic_block_end = val.high_cuid;
+      max_qty = val.nsets * 2;
+      
+      if (file)
+	fprintf (file, ";; Processing block from %d to %d, %d sets.\n",
+		 INSN_UID (insn), val.last ? INSN_UID (val.last) : 0,
+		 val.nsets);
+
+      /* Make MAX_QTY bigger to give us room to optimize
+	 past the end of this basic block, if that should prove useful.  */
+      if (max_qty < 500)
+	max_qty = 500;
+
+      max_qty += max_reg;
+
+      /* If this basic block is being extended by following certain jumps,
+         (see `cse_end_of_basic_block'), we reprocess the code from the start.
+         Otherwise, we start after this basic block.  */
+      if (val.path_size > 0)
+        cse_basic_block (insn, val.last, val.path, 0);
+      else
+	{
+	  int old_cse_jumps_altered = cse_jumps_altered;
+	  rtx temp;
+
+	  /* When cse changes a conditional jump to an unconditional
+	     jump, we want to reprocess the block, since it will give
+	     us a new branch path to investigate.  */
+	  cse_jumps_altered = 0;
+	  temp = cse_basic_block (insn, val.last, val.path, ! after_loop);
+	  if (cse_jumps_altered == 0 || flag_cse_follow_jumps == 0)
+	    insn = temp;
+
+	  cse_jumps_altered |= old_cse_jumps_altered;
+	}
+
+#ifdef USE_C_ALLOCA
+      alloca (0);
+#endif
+    }
+
+  /* Tell refers_to_mem_p that qty_const info is not available.  */
+  qty_const = 0;
+
+  if (max_elements_made < n_elements_made)
+    max_elements_made = n_elements_made;
+
+  return cse_jumps_altered;
+}
+
+/* Process a single basic block.  FROM and TO and the limits of the basic
+   block.  NEXT_BRANCH points to the branch path when following jumps or
+   a null path when not following jumps.
+
+   AROUND_LOOP is non-zero if we are to try to cse around to the start of a
+   loop.  This is true when we are being called for the last time on a
+   block and this CSE pass is before loop.c.  */
+
+static rtx
+cse_basic_block (from, to, next_branch, around_loop)
+     register rtx from, to;
+     struct branch_path *next_branch;
+     int around_loop;
+{
+  register rtx insn;
+  int to_usage = 0;
+  int in_libcall_block = 0;
+
+  /* Each of these arrays is undefined before max_reg, so only allocate
+     the space actually needed and adjust the start below.  */
+
+  qty_first_reg = (int *) alloca ((max_qty - max_reg) * sizeof (int));
+  qty_last_reg = (int *) alloca ((max_qty - max_reg) * sizeof (int));
+  qty_mode= (enum machine_mode *) alloca ((max_qty - max_reg) * sizeof (enum machine_mode));
+  qty_const = (rtx *) alloca ((max_qty - max_reg) * sizeof (rtx));
+  qty_const_insn = (rtx *) alloca ((max_qty - max_reg) * sizeof (rtx));
+  qty_comparison_code
+    = (enum rtx_code *) alloca ((max_qty - max_reg) * sizeof (enum rtx_code));
+  qty_comparison_qty = (int *) alloca ((max_qty - max_reg) * sizeof (int));
+  qty_comparison_const = (rtx *) alloca ((max_qty - max_reg) * sizeof (rtx));
+
+  qty_first_reg -= max_reg;
+  qty_last_reg -= max_reg;
+  qty_mode -= max_reg;
+  qty_const -= max_reg;
+  qty_const_insn -= max_reg;
+  qty_comparison_code -= max_reg;
+  qty_comparison_qty -= max_reg;
+  qty_comparison_const -= max_reg;
+
+  new_basic_block ();
+
+  /* TO might be a label.  If so, protect it from being deleted.  */
+  if (to != 0 && GET_CODE (to) == CODE_LABEL)
+    ++LABEL_NUSES (to);
+
+  for (insn = from; insn != to; insn = NEXT_INSN (insn))
+    {
+      register enum rtx_code code;
+
+      /* See if this is a branch that is part of the path.  If so, and it is
+	 to be taken, do so.  */
+      if (next_branch->branch == insn)
+	{
+	  if (next_branch++->status == TAKEN)
+	    {
+	      record_jump_equiv (insn, 1);
+	      /* Set the last insn as the jump insn; it doesn't affect cc0.
+		 Then follow this branch.  */
+#ifdef HAVE_cc0
+	      prev_insn_cc0 = 0;
+#endif
+	      prev_insn = insn;
+	      insn = JUMP_LABEL (insn);
+	      continue;
+	    }
+	}
+        
+      code = GET_CODE (insn);
+      if (GET_MODE (insn) == QImode)
+	PUT_MODE (insn, VOIDmode);
+
+      if (GET_RTX_CLASS (code) == 'i')
+	{
+	  /* Process notes first so we have all notes in canonical forms when
+	     looking for duplicate operations.  */
+
+	  if (REG_NOTES (insn))
+	    REG_NOTES (insn) = cse_process_notes (REG_NOTES (insn), 0);
+
+	  /* Track when we are inside in LIBCALL block.  Inside such a block,
+	     we do not want to record destinations.  The last insn of a
+	     LIBCALL block is not considered to be part of the block, since
+	     its desitination is the result of the block and hence should be
+	     recorded.  */
+
+	  if (find_reg_note (insn, REG_LIBCALL, 0))
+	    in_libcall_block = 1;
+	  else if (find_reg_note (insn, REG_RETVAL, 0))
+	    in_libcall_block = 0;
+
+	  cse_insn (insn, in_libcall_block);
+	}
+
+      /* If INSN is now an unconditional jump, skip to the end of our
+	 basic block by pretending that we just did the last insn in the
+	 basic block.  If we are jumping to the end of our block, show
+	 that we can have one usage of TO.  */
+
+      if (simplejump_p (insn))
+	{
+	  if (to == 0)
+	    return 0;
+
+	  if (JUMP_LABEL (insn) == to)
+	    to_usage = 1;
+
+	  insn = PREV_INSN (to);
+	}
+
+      /* See if it is ok to keep on going past the label
+	 which used to end our basic block.  Remember that we incremented
+	 the count of that label, so we decremement it here.  If we made
+	 a jump unconditional, TO_USAGE will be one; in that case, we don't
+	 want to count the use in that jump.  */
+
+      if (to != 0 && NEXT_INSN (insn) == to
+	  && GET_CODE (to) == CODE_LABEL && --LABEL_NUSES (to) == to_usage)
+	{
+	  struct cse_basic_block_data val;
+
+	  insn = NEXT_INSN (to);
+
+	  if (LABEL_NUSES (to) == 0)
+	    delete_insn (to);
+
+	  /* Find the end of the following block.  Note that we won't be
+	     following branches in this case.  If TO was the last insn
+	     in the function, we are done.  Similarly, if we deleted the
+	     insn after TO, it must have been because it was preceeded by
+	     a BARRIER.  In that case, we are done with this block because it
+	     has no continuation.  */
+
+	  if (insn == 0 || INSN_DELETED_P (insn))
+	    return 0;
+
+	  to_usage = 0;
+	  val.path_size = 0;
+	  cse_end_of_basic_block (insn, &val, 0, 0);
+
+	  /* If the tables we allocated have enough space left
+	     to handle all the SETs in the next basic block,
+	     continue through it.  Otherwise, return,
+	     and that block will be scanned individually.  */
+	  if (val.nsets * 2 + next_qty > max_qty)
+	    break;
+
+	  cse_basic_block_start = val.low_cuid;
+	  cse_basic_block_end = val.high_cuid;
+	  to = val.last;
+
+	  /* Prevent TO from being deleted if it is a label.  */
+	  if (to != 0 && GET_CODE (to) == CODE_LABEL)
+	    ++LABEL_NUSES (to);
+
+	  /* Back up so we process the first insn in the extension.  */
+	  insn = PREV_INSN (insn);
+	}
+    }
+
+  if (next_qty > max_qty)
+    abort ();
+
+  /* If we are running before loop.c, we stopped on a NOTE_INSN_LOOP_END, and
+     the previous insn is the only insn that branches to the head of a loop,
+     we can cse into the loop.  Don't do this if we changed the jump
+     structure of a loop unless we aren't going to be following jumps.  */
+
+  if ((cse_jumps_altered == 0 || flag_cse_follow_jumps == 0)
+      && around_loop && to != 0
+      && GET_CODE (to) == NOTE && NOTE_LINE_NUMBER (to) == NOTE_INSN_LOOP_END
+      && GET_CODE (PREV_INSN (to)) == JUMP_INSN
+      && JUMP_LABEL (PREV_INSN (to)) != 0
+      && LABEL_NUSES (JUMP_LABEL (PREV_INSN (to))) == 1)
+    cse_around_loop (JUMP_LABEL (PREV_INSN (to)));
+
+  return to ? NEXT_INSN (to) : 0;
+}
+
+/* Count the number of times registers are used (not set) in X.
+   COUNTS is an array in which we accumulate the count, INCR is how much
+   we count each register usage.  */
+
+static void
+count_reg_usage (x, counts, incr)
+     rtx x;
+     int *counts;
+     int incr;
+{
+  enum rtx_code code = GET_CODE (x);
+  char *fmt;
+  int i, j;
+
+  switch (code)
+    {
+    case REG:
+      counts[REGNO (x)] += incr;
+      return;
+
+    case PC:
+    case CC0:
+    case CONST:
+    case CONST_INT:
+    case CONST_DOUBLE:
+    case SYMBOL_REF:
+    case LABEL_REF:
+    case CLOBBER:
+      return;
+
+    case SET:
+      /* Unless we are setting a REG, count everything in SET_DEST.  */
+      if (GET_CODE (SET_DEST (x)) != REG)
+	count_reg_usage (SET_DEST (x), counts, incr);
+      count_reg_usage (SET_SRC (x), counts, incr);
+      return;
+
+    case INSN:
+    case JUMP_INSN:
+    case CALL_INSN:
+      count_reg_usage (PATTERN (x), counts, incr);
+
+      /* Things used in a REG_EQUAL note aren't dead since loop may try to
+	 use them.  */
+
+      if (REG_NOTES (x))
+	count_reg_usage (REG_NOTES (x), counts, incr);
+      return;
+
+    case EXPR_LIST:
+    case INSN_LIST:
+      if (REG_NOTE_KIND (x) == REG_EQUAL)
+	count_reg_usage (XEXP (x, 0), counts, incr);
+      if (XEXP (x, 1))
+	count_reg_usage (XEXP (x, 1), counts, incr);
+      return;
+    }
+
+  fmt = GET_RTX_FORMAT (code);
+  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+    {
+      if (fmt[i] == 'e')
+	count_reg_usage (XEXP (x, i), counts, incr);
+      else if (fmt[i] == 'E')
+	for (j = XVECLEN (x, i) - 1; j >= 0; j--)
+	  count_reg_usage (XVECEXP (x, i, j), counts, incr);
+    }
+}
+
+/* Scan all the insns and delete any that are dead; i.e., they store a register
+   that is never used or they copy a register to itself.
+
+   This is used to remove insns made obviously dead by cse.  It improves the
+   heuristics in loop since it won't try to move dead invariants out of loops
+   or make givs for dead quantities.  The remaining passes of the compilation
+   are also sped up.  */
+
+void
+delete_dead_from_cse (insns, nreg)
+     rtx insns;
+     int nreg;
+{
+  int *counts = (int *) alloca (nreg * sizeof (int));
+  rtx insn;
+  int i;
+
+  /* First count the number of times each register is used.  */
+  bzero (counts, sizeof (int) * nreg);
+  for (insn = next_real_insn (insns); insn; insn = next_real_insn (insn))
+    count_reg_usage (insn, counts, 1);
+
+  /* Go from the last insn to the first and delete insns that only set unused
+     registers or copy a register to itself.  As we delete an insn, remove
+     usage counts for registers it uses.  */
+  for (insn = prev_real_insn (get_last_insn ());
+       insn; insn = prev_real_insn (insn))
+    {
+      int live_insn = 0;
+
+      if (GET_CODE (PATTERN (insn)) == SET)
+	{
+	  if (GET_CODE (SET_DEST (PATTERN (insn))) == REG
+	      && SET_DEST (PATTERN (insn)) == SET_SRC (PATTERN (insn)))
+	    ;
+
+	  else if (GET_CODE (SET_DEST (PATTERN (insn))) != REG
+		   || REGNO (SET_DEST (PATTERN (insn))) < FIRST_PSEUDO_REGISTER
+		   || counts[REGNO (SET_DEST (PATTERN (insn)))] != 0
+		   || side_effects_p (SET_SRC (PATTERN (insn))))
+	    live_insn = 1;
+	}
+      else if (GET_CODE (PATTERN (insn)) == PARALLEL)
+	for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
+	  {
+	    rtx elt = XVECEXP (PATTERN (insn), 0, i);
+
+	    if (GET_CODE (elt) == SET)
+	      {
+		if (GET_CODE (SET_DEST (elt)) == REG
+		    && SET_DEST (elt) == SET_SRC (elt))
+		  ;
+
+		else if (GET_CODE (SET_DEST (elt)) != REG
+			 || REGNO (SET_DEST (elt)) < FIRST_PSEUDO_REGISTER
+			 || counts[REGNO (SET_DEST (elt))] != 0
+			 || side_effects_p (SET_SRC (elt)))
+		  live_insn = 1;
+	      }
+	    else if (GET_CODE (elt) != CLOBBER && GET_CODE (elt) != USE)
+	      live_insn = 1;
+	  }
+      else
+	live_insn = 1;
+
+      /* If this is a dead insn, delete it and show registers in it aren't
+	 being used.  If this is the last insn of a libcall sequence, don't
+	 delete it even if it is dead because we don't know how to do so
+	 here.  */
+
+      if (! live_insn && ! find_reg_note (insn, REG_RETVAL, 0))
+	{
+	  count_reg_usage (insn, counts, -1);
+	  PUT_CODE (insn, NOTE);
+	  NOTE_SOURCE_FILE (insn) = 0;
+	  NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
+	}
+    }
+}