Add cselib; use it in loop and reload_cse_regs

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@32538 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 1230 insertions, 0 deletions

diff --git a/gcc/simplify-rtx.c b/gcc/simplify-rtx.c
index 8f1aa9628d8..f9ed9318080 100644
--- a/gcc/simplify-rtx.c
+++ b/gcc/simplify-rtx.c
@@ -37,6 +37,10 @@ Boston, MA 02111-1307, USA.  */
 #include "expr.h"
 #include "toplev.h"
 #include "output.h"
+#include "ggc.h"
+#include "obstack.h"
+#include "hashtab.h"
+#include "cselib.h"
 
 /* Simplification and canonicalization of RTL.  */
 
@@ -1957,3 +1961,1229 @@ simplify_rtx (x)
       return NULL;
     }
 }
+
+static int entry_and_rtx_equal_p	PARAMS ((const void *, const void *));
+static unsigned int get_value_hash	PARAMS ((const void *));
+static struct elt_list *new_elt_list	PARAMS ((struct elt_list *, cselib_val *));
+static struct elt_loc_list *new_elt_loc_list	PARAMS ((struct elt_loc_list *, rtx));
+static void unchain_one_value		PARAMS ((cselib_val *));
+static void unchain_one_elt_list	PARAMS ((struct elt_list **));
+static void unchain_one_elt_loc_list	PARAMS ((struct elt_loc_list **));
+static void clear_table			PARAMS ((void));
+static int check_value_useless		PARAMS ((cselib_val *));
+static int discard_useless_locs		PARAMS ((void **, void *));
+static int discard_useless_values	PARAMS ((void **, void *));
+static void remove_useless_values	PARAMS ((void));
+static unsigned int hash_rtx		PARAMS ((rtx, enum machine_mode, int));
+static cselib_val *new_cselib_val	PARAMS ((unsigned int, enum machine_mode));
+static void add_mem_for_addr		PARAMS ((cselib_val *, cselib_val *, rtx));
+static cselib_val *cselib_lookup_mem	PARAMS ((rtx, int));
+static rtx cselib_subst_to_values	PARAMS ((rtx));
+static void cselib_invalidate_regno	PARAMS ((int, enum machine_mode));
+static int cselib_mem_conflict_p	PARAMS ((rtx, rtx));
+static int cselib_invalidate_mem_1	PARAMS ((void **, void *));
+static void cselib_invalidate_mem	PARAMS ((rtx));
+static void cselib_invalidate_rtx	PARAMS ((rtx, rtx, void *));
+static void cselib_record_set		PARAMS ((rtx, cselib_val *, cselib_val *));
+static void cselib_record_sets		PARAMS ((rtx));
+
+/* There are three ways in which cselib can look up an rtx:
+   - for a REG, the reg_values table (which is indexed by regno) is used
+   - for a MEM, we recursively look up its address and then follow the
+     addr_list of that value
+   - for everything else, we compute a hash value and go through the hash
+     table.  Since different rtx's can still have the same hash value,
+     this involves walking the table entries for a given value and comparing
+     the locations of the entries with the rtx we are looking up.  */
+
+/* A table that enables us to look up elts by their value.  */
+static htab_t hash_table;
+
+/* This is a global so we don't have to pass this through every function.
+   It is used in new_elt_loc_list to set SETTING_INSN.  */
+static rtx cselib_current_insn;
+
+/* Every new unknown value gets a unique number.  */
+static unsigned int next_unknown_value;
+
+/* The number of registers we had when the varrays were last resized.  */
+static int cselib_nregs;
+
+/* Count values without known locations.  Whenever this grows too big, we
+   remove these useless values from the table.  */
+static int n_useless_values;
+
+/* Number of useless values before we remove them from the hash table.  */
+#define MAX_USELESS_VALUES 32
+
+/* This table maps from register number to values.  It does not contain
+   pointers to cselib_val structures, but rather elt_lists.  The purpose is
+   to be able to refer to the same register in different modes.  */
+static varray_type reg_values;
+#define REG_VALUES(I) VARRAY_ELT_LIST (reg_values, (I))
+
+/* We pass this to cselib_invalidate_mem to invalidate all of
+   memory for a non-const call instruction.  */
+static rtx callmem;
+
+/* Memory for our structures is allocated from this obstack.  */
+static struct obstack cselib_obstack;
+
+/* Used to quickly free all memory.  */
+static char *cselib_startobj;
+
+/* Caches for unused structures.  */
+static cselib_val *empty_vals;
+static struct elt_list *empty_elt_lists;
+static struct elt_loc_list *empty_elt_loc_lists;
+
+/* Allocate a struct elt_list and fill in its two elements with the
+   arguments.  */
+static struct elt_list *
+new_elt_list (next, elt)
+     struct elt_list *next;
+     cselib_val *elt;
+{
+  struct elt_list *el = empty_elt_lists;
+  if (el)
+    empty_elt_lists = el->next;
+  else
+    el = (struct elt_list *) obstack_alloc (&cselib_obstack,
+					    sizeof (struct elt_list));
+  el->next = next;
+  el->elt = elt;
+  return el;
+}
+
+/* Allocate a struct elt_loc_list and fill in its two elements with the
+   arguments.  */
+static struct elt_loc_list *
+new_elt_loc_list (next, loc)
+     struct elt_loc_list *next;
+     rtx loc;
+{
+  struct elt_loc_list *el = empty_elt_loc_lists;
+  if (el)
+    empty_elt_loc_lists = el->next;
+  else
+    el = (struct elt_loc_list *) obstack_alloc (&cselib_obstack,
+						sizeof (struct elt_loc_list));
+  el->next = next;
+  el->loc = loc;
+  el->setting_insn = cselib_current_insn;
+  return el;
+}
+
+/* The elt_list at *PL is no longer needed.  Unchain it and free its
+   storage.  */
+static void
+unchain_one_elt_list (pl)
+     struct elt_list **pl;
+{
+  struct elt_list *l = *pl;
+  *pl = l->next;
+  l->next = empty_elt_lists;
+  empty_elt_lists = l;
+}
+
+/* Likewise for elt_loc_lists.  */
+static void
+unchain_one_elt_loc_list (pl)
+     struct elt_loc_list **pl;
+{
+  struct elt_loc_list *l = *pl;
+  *pl = l->next;
+  l->next = empty_elt_loc_lists;
+  empty_elt_loc_lists = l;
+}
+
+/* Likewise for cselib_vals.  This also frees the addr_list associated with
+   V.  */
+static void
+unchain_one_value (v)
+     cselib_val *v;
+{
+  while (v->addr_list)
+    unchain_one_elt_list (&v->addr_list);
+
+  v->u.next_free = empty_vals;
+  empty_vals = v;
+}
+
+/* Remove all entries from the hash table.  Also used during
+   initialization.  */
+static void
+clear_table ()
+{
+  int i;
+  for (i = 0; i < cselib_nregs; i++)
+    REG_VALUES (i) = 0;
+
+  htab_empty (hash_table);
+  obstack_free (&cselib_obstack, cselib_startobj);
+
+  empty_vals = 0;
+  empty_elt_lists = 0;
+  empty_elt_loc_lists = 0;
+  n_useless_values = 0;
+
+  next_unknown_value = 0;
+}
+
+/* The equality test for our hash table.  The first argument ENTRY is a table
+   element (i.e. a cselib_val), while the second arg X is an rtx.  */
+static int
+entry_and_rtx_equal_p (entry, x_arg)
+     const void *entry, *x_arg;
+{
+  struct elt_loc_list *l;
+  cselib_val *v = (cselib_val *)entry;
+  rtx x = (rtx)x_arg;
+
+  /* We don't guarantee that distinct rtx's have different hash values,
+     so we need to do a comparison.  */
+  for (l = v->locs; l; l = l->next)
+    if (rtx_equal_for_cselib_p (l->loc, x))
+      return 1;
+  return 0;
+}
+
+/* The hash function for our hash table.  The value is always computed with
+   hash_rtx when adding an element; this function just extracts the hash
+   value from a cselib_val structure.  */
+static unsigned int
+get_value_hash (entry)
+     const void *entry;
+{
+  cselib_val *v = (cselib_val *) entry;
+  return v->value;
+}
+
+/* If there are no more locations that hold a value, the value has become
+   useless.  See whether that is the case for V.  Return 1 if this has
+   just become useless.  */
+static int
+check_value_useless (v)
+     cselib_val *v;
+{
+  if (v->locs != 0)
+    return 0;
+
+  if (v->value == 0)
+    return 0;
+
+  /* This is a marker to indicate that the value will be reclaimed.  */
+  v->value = 0;
+  n_useless_values++;
+  return 1;
+}
+
+/* Return true if X contains a VALUE rtx.  If ONLY_USELESS is set, we
+   only return true for values which point to a cselib_val whose value
+   element has been set to zero, which implies the cselib_val will be
+   removed.  */
+int
+references_value_p (x, only_useless)
+     rtx x;
+     int only_useless;
+{
+  enum rtx_code code = GET_CODE (x);
+  const char *fmt = GET_RTX_FORMAT (code);
+  int i;
+
+  if (GET_CODE (x) == VALUE
+      && (! only_useless || CSELIB_VAL_PTR (x)->value == 0))
+    return 1;
+
+  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+    {
+      if (fmt[i] == 'e')
+	{
+	  if (references_value_p (XEXP (x, i), only_useless))
+	    return 1;
+	}
+      else if (fmt[i] == 'E')
+	{
+	  int j;
+
+	  for (j = 0; j < XVECLEN (x, i); j++)
+	    if (references_value_p (XVECEXP (x, i, j), only_useless))
+	      return 1;
+	}
+    }
+
+  return 0;
+}
+
+/* Set by discard_useless_locs if it deleted the last location of any
+   value.  */
+static int values_became_useless;
+
+/* For all locations found in X, delete locations that reference useless
+   values (i.e. values without any location).  Called through
+   htab_traverse.  */
+static int
+discard_useless_locs (x, info)
+     void **x;
+     void *info ATTRIBUTE_UNUSED;
+{
+  cselib_val *v = (cselib_val *)*x;
+  struct elt_loc_list **p = &v->locs;
+
+  while (*p)
+    {
+      if (references_value_p ((*p)->loc, 1))
+	unchain_one_elt_loc_list (p);
+      else
+	p = &(*p)->next;
+    }
+  if (check_value_useless (v))
+    values_became_useless = 1;
+
+  return 1;
+}
+
+/* If X is a value with no locations, remove it from the hashtable.  */
+
+static int
+discard_useless_values (x, info)
+     void **x;
+     void *info ATTRIBUTE_UNUSED;
+{
+  cselib_val *v = (cselib_val *)*x;
+
+  if (v->value == 0)
+    {
+      htab_clear_slot (hash_table, x);
+      unchain_one_value (v);
+      n_useless_values--;
+    }
+  return 1;
+}
+
+/* Clean out useless values (i.e. those which no longer have locations
+   associated with them) from the hash table.  */
+static void
+remove_useless_values ()
+{
+  /* First pass: eliminate locations that reference the value.  That in
+     turn can make more values useless.  */
+  do
+    {
+      values_became_useless = 0;
+      htab_traverse (hash_table, discard_useless_locs, 0);
+    }
+  while (values_became_useless);
+
+  /* Second pass: actually remove the values.  */
+  htab_traverse (hash_table, discard_useless_values, 0);
+
+  if (n_useless_values != 0)
+    abort ();
+}
+
+/* Return nonzero if we can prove that X and Y contain the same value, taking
+   our gathered information into account.  */
+int
+rtx_equal_for_cselib_p (x, y)
+     rtx x, y;
+{
+  enum rtx_code code;
+  const char *fmt;
+  int i;
+  
+  if (GET_CODE (x) == REG || GET_CODE (x) == MEM)
+    {
+      cselib_val *e = cselib_lookup (x, VOIDmode, 0);
+      if (e)
+	x = e->u.val_rtx;
+    }
+  if (GET_CODE (y) == REG || GET_CODE (y) == MEM)
+    {
+      cselib_val *e = cselib_lookup (y, VOIDmode, 0);
+      if (e)
+	y = e->u.val_rtx;
+    }
+
+  if (x == y)
+    return 1;
+
+  if (GET_CODE (x) == VALUE && GET_CODE (y) == VALUE)
+    return CSELIB_VAL_PTR (x) == CSELIB_VAL_PTR (y);
+
+  if (GET_CODE (x) == VALUE)
+    {
+      cselib_val *e = CSELIB_VAL_PTR (x);
+      struct elt_loc_list *l;
+
+      for (l = e->locs; l; l = l->next)
+	{
+	  rtx t = l->loc;
+
+	  /* Avoid infinite recursion.  */
+	  if (GET_CODE (t) == REG || GET_CODE (t) == MEM)
+	    continue;
+
+	  if (rtx_equal_for_cselib_p (t, y))
+	    return 1;
+	}
+      
+      return 0;
+    }
+
+  if (GET_CODE (y) == VALUE)
+    {
+      cselib_val *e = CSELIB_VAL_PTR (y);
+      struct elt_loc_list *l;
+
+      for (l = e->locs; l; l = l->next)
+	{
+	  rtx t = l->loc;
+
+	  if (GET_CODE (t) == REG || GET_CODE (t) == MEM)
+	    continue;
+
+	  if (rtx_equal_for_cselib_p (x, t))
+	    return 1;
+	}
+      
+      return 0;
+    }
+
+  if (GET_CODE (x) != GET_CODE (y)
+      || GET_MODE (x) != GET_MODE (y))
+    return 0;
+
+  /* This won't be handled correctly by the code below.  */
+  if (GET_CODE (x) == LABEL_REF)
+    return XEXP (x, 0) == XEXP (y, 0);
+  
+  code = GET_CODE (x);
+  fmt = GET_RTX_FORMAT (code);
+
+  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+    {
+      int j;
+      switch (fmt[i])
+	{
+	case 'w':
+	  if (XWINT (x, i) != XWINT (y, i))
+	    return 0;
+	  break;
+
+	case 'n':
+	case 'i':
+	  if (XINT (x, i) != XINT (y, i))
+	    return 0;
+	  break;
+
+	case 'V':
+	case 'E':
+	  /* Two vectors must have the same length.  */
+	  if (XVECLEN (x, i) != XVECLEN (y, i))
+	    return 0;
+
+	  /* And the corresponding elements must match.  */
+	  for (j = 0; j < XVECLEN (x, i); j++)
+	    if (! rtx_equal_for_cselib_p (XVECEXP (x, i, j),
+					  XVECEXP (y, i, j)))
+	      return 0;
+	  break;
+
+	case 'e':
+	  if (! rtx_equal_for_cselib_p (XEXP (x, i), XEXP (y, i)))
+	    return 0;
+	  break;
+
+	case 'S':
+	case 's':
+	  if (strcmp (XSTR (x, i), XSTR (y, i)))
+	    return 0;
+	  break;
+
+	case 'u':
+	  /* These are just backpointers, so they don't matter.  */
+	  break;
+
+	case '0':
+	case 't':
+	  break;
+
+	  /* It is believed that rtx's at this level will never
+	     contain anything but integers and other rtx's,
+	     except for within LABEL_REFs and SYMBOL_REFs.  */
+	default:
+	  abort ();
+	}
+    }
+  return 1;
+}
+
+/* Hash an rtx.  Return 0 if we couldn't hash the rtx.
+   For registers and memory locations, we look up their cselib_val structure
+   and return its VALUE element.
+   Possible reasons for return 0 are: the object is volatile, or we couldn't
+   find a register or memory location in the table and CREATE is zero.  If
+   CREATE is nonzero, table elts are created for regs and mem.
+   MODE is used in hashing for CONST_INTs only;
+   otherwise the mode of X is used.  */
+static unsigned int
+hash_rtx (x, mode, create)
+     rtx x;
+     enum machine_mode mode;
+     int create;
+{
+  cselib_val *e;
+  int i, j;
+  unsigned int hash = 0;
+  enum rtx_code code = GET_CODE (x);
+  const char *fmt = GET_RTX_FORMAT (code);
+
+  /* repeat is used to turn tail-recursion into iteration.  */
+ repeat:
+
+  code = GET_CODE (x);
+  switch (code)
+    {
+    case MEM:
+    case REG:
+      e = cselib_lookup (x, GET_MODE (x), create);
+      if (! e)
+	return 0;
+      return e->value;
+
+    case CONST_INT:
+      {
+	unsigned HOST_WIDE_INT tem = INTVAL (x);
+	hash += ((unsigned) CONST_INT << 7) + (unsigned) mode + tem;
+	return hash ? hash : CONST_INT;
+      }
+
+    case CONST_DOUBLE:
+      /* This is like the general case, except that it only counts
+	 the integers representing the constant.  */
+      hash += (unsigned) code + (unsigned) GET_MODE (x);
+      if (GET_MODE (x) != VOIDmode)
+	for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++)
+	  {
+	    unsigned HOST_WIDE_INT tem = XWINT (x, i);
+	    hash += tem;
+	  }
+      else
+	hash += ((unsigned) CONST_DOUBLE_LOW (x)
+		 + (unsigned) CONST_DOUBLE_HIGH (x));
+      return hash ? hash : CONST_DOUBLE;
+
+      /* Assume there is only one rtx object for any given label.  */
+    case LABEL_REF:
+      hash
+	+= ((unsigned) LABEL_REF << 7) + (unsigned long) XEXP (x, 0);
+      return hash ? hash : LABEL_REF;
+
+    case SYMBOL_REF:
+      hash
+	+= ((unsigned) SYMBOL_REF << 7) + (unsigned long) XSTR (x, 0);
+      return hash ? hash : SYMBOL_REF;
+
+    case PRE_DEC:
+    case PRE_INC:
+    case POST_DEC:
+    case POST_INC:
+    case PC:
+    case CC0:
+    case CALL:
+    case UNSPEC_VOLATILE:
+      return 0;
+
+    case ASM_OPERANDS:
+      if (MEM_VOLATILE_P (x))
+	return 0;
+
+      break;
+      
+    default:
+      break;
+    }
+
+  i = GET_RTX_LENGTH (code) - 1;
+  hash += (unsigned) code + (unsigned) GET_MODE (x);
+  fmt = GET_RTX_FORMAT (code);
+  for (; i >= 0; i--)
+    {
+      if (fmt[i] == 'e')
+	{
+	  unsigned int tem_hash;
+	  rtx tem = XEXP (x, i);
+
+	  /* 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;
+	    }
+	  tem_hash = hash_rtx (tem, 0, create);
+	  if (tem_hash == 0)
+	    return 0;
+	  hash += tem_hash;
+	}
+      else if (fmt[i] == 'E')
+	for (j = 0; j < XVECLEN (x, i); j++)
+	  {
+	    unsigned int tem_hash = hash_rtx (XVECEXP (x, i, j), 0, create);
+	    if (tem_hash == 0)
+	      return 0;
+	    hash += tem_hash;
+	  }
+      else if (fmt[i] == 's')
+	{
+	  unsigned char *p = (unsigned char *) XSTR (x, i);
+	  if (p)
+	    while (*p)
+	      hash += *p++;
+	}
+      else if (fmt[i] == 'i')
+	{
+	  unsigned int tem = XINT (x, i);
+	  hash += tem;
+	}
+      else if (fmt[i] == '0' || fmt[i] == 't')
+	/* unused */;
+      else
+	abort ();
+    }
+  return hash ? hash : 1 + GET_CODE (x);
+}
+
+/* Create a new value structure for VALUE and initialize it.  The mode of the
+   value is MODE.  */
+static cselib_val *
+new_cselib_val (value, mode)
+     unsigned int value;
+     enum machine_mode mode;
+{
+  cselib_val *e = empty_vals;
+  if (e)
+    empty_vals = e->u.next_free;
+  else
+    e = (cselib_val *) obstack_alloc (&cselib_obstack, sizeof (cselib_val));
+  if (value == 0)
+    abort ();
+  e->value = value;
+  e->u.val_rtx = gen_rtx_VALUE (mode);
+  CSELIB_VAL_PTR (e->u.val_rtx) = e;
+
+  e->addr_list = 0;
+  e->locs = 0;
+  return e;
+}
+
+/* ADDR_ELT is a value that is used as address.  MEM_ELT is the value that
+   contains the data at this address.  X is a MEM that represents the
+   value.  Update the two value structures to represent this situation.  */
+static void
+add_mem_for_addr (addr_elt, mem_elt, x)
+     cselib_val *addr_elt, *mem_elt;
+     rtx x;
+{
+  rtx new;
+  struct elt_loc_list *l;
+
+  /* Avoid duplicates.  */
+  for (l = mem_elt->locs; l; l = l->next)
+    if (GET_CODE (l->loc) == MEM
+	&& CSELIB_VAL_PTR (XEXP (l->loc, 0)) == addr_elt)
+      return;
+
+  new = gen_rtx_MEM (GET_MODE (x), addr_elt->u.val_rtx);
+  addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt);
+
+  RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x);
+  MEM_COPY_ATTRIBUTES (new, x);
+
+  mem_elt->locs = new_elt_loc_list (mem_elt->locs, new);
+}
+
+/* Subroutine of cselib_lookup.  Return a value for X, which is a MEM rtx.
+   If CREATE, make a new one if we haven't seen it before.  */
+static cselib_val *
+cselib_lookup_mem (x, create)
+     rtx x;
+     int create;
+{
+  void **slot;
+  cselib_val *addr;
+  cselib_val *mem_elt;
+  struct elt_list *l;
+
+  if (MEM_VOLATILE_P (x) || GET_MODE (x) == BLKmode)
+    return 0;
+  if (FLOAT_MODE_P (GET_MODE (x)) && flag_float_store)
+    return 0;
+
+  /* Look up the value for the address.  */
+  addr = cselib_lookup (XEXP (x, 0), GET_MODE (x), create);
+  if (! addr)
+    return 0;
+
+  /* Find a value that describes a value of our mode at that address.  */
+  for (l = addr->addr_list; l; l = l->next)
+    if (GET_MODE (l->elt->u.val_rtx) == GET_MODE (x))
+      return l->elt;
+  if (! create)
+    return 0;
+  mem_elt = new_cselib_val (++next_unknown_value, GET_MODE (x));
+  add_mem_for_addr (addr, mem_elt, x);
+  slot = htab_find_slot_with_hash (hash_table, x, mem_elt->value, 1);
+  *slot = mem_elt;
+  return mem_elt;
+}
+
+/* Walk rtx X and replace all occurrences of REG and MEM subexpressions
+   with VALUE expressions.  This way, it becomes independent of changes
+   to registers and memory.
+   X isn't actually modified; if modifications are needed, new rtl is
+   allocated.  However, the return value can share rtl with X.  */
+static rtx
+cselib_subst_to_values (x)
+     rtx x;
+{
+  enum rtx_code code = GET_CODE (x);
+  const char *fmt = GET_RTX_FORMAT (code);
+  cselib_val *e;
+  struct elt_list *l;
+  rtx copy = x;
+  int i;
+
+  switch (code)
+    {
+    case REG:
+      i = REGNO (x);
+      for (l = REG_VALUES (i); l; l = l->next)
+	if (GET_MODE (l->elt->u.val_rtx) == GET_MODE (x))
+	  return l->elt->u.val_rtx;
+      abort ();
+
+    case MEM:
+      e = cselib_lookup_mem (x, 0);
+      if (! e)
+	abort ();
+      return e->u.val_rtx;
+
+      /* CONST_DOUBLEs must be special-cased here so that we won't try to
+	 look up the CONST_DOUBLE_MEM inside.  */
+    case CONST_DOUBLE:
+    case CONST_INT:
+      return x;
+
+    default:
+      break;
+    }
+
+  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+    {
+      if (fmt[i] == 'e')
+	{
+	  rtx t = cselib_subst_to_values (XEXP (x, i));
+	  if (t != XEXP (x, i) && x == copy)
+	    copy = shallow_copy_rtx (x);
+	  XEXP (copy, i) = t;
+	}
+      else if (fmt[i] == 'E')
+	{
+	  int j, k;
+
+	  for (j = 0; j < XVECLEN (x, i); j++)
+	    {
+	      rtx t = cselib_subst_to_values (XVECEXP (x, i, j));
+	      if (t != XVECEXP (x, i, j) && XVEC (x, i) == XVEC (copy, i))
+		{
+		  if (x == copy)
+		    copy = shallow_copy_rtx (x);
+		  XVEC (copy, i) = rtvec_alloc (XVECLEN (x, i));
+		  for (k = 0; k < j; k++)
+		    XVECEXP (copy, i, k) = XVECEXP (x, i, k);
+		}
+	      XVECEXP (copy, i, j) = t;
+	    }
+	}
+    }
+  return copy;
+}
+
+/* Look up the rtl expression X in our tables and return the value it has.
+   If CREATE is zero, we return NULL if we don't know the value.  Otherwise,
+   we create a new one if possible, using mode MODE if X doesn't have a mode
+   (i.e. because it's a constant).  */
+cselib_val *
+cselib_lookup (x, mode, create)
+     rtx x;
+     enum machine_mode mode;
+     int create;
+{
+  void **slot;
+  cselib_val *e;
+  unsigned int hashval;
+
+  if (GET_MODE (x) != VOIDmode)
+    mode = GET_MODE (x);
+
+  if (GET_CODE (x) == VALUE)
+    return CSELIB_VAL_PTR (x);
+
+  if (GET_CODE (x) == REG)
+    {
+      struct elt_list *l;
+      int i = REGNO (x);
+      for (l = REG_VALUES (i); l; l = l->next)
+	if (mode == GET_MODE (l->elt->u.val_rtx))
+	  return l->elt;
+      if (! create)
+	return 0;
+      e = new_cselib_val (++next_unknown_value, GET_MODE (x));
+      e->locs = new_elt_loc_list (e->locs, x);
+      REG_VALUES (i) = new_elt_list (REG_VALUES (i), e);
+      slot = htab_find_slot_with_hash (hash_table, x, e->value, 1);
+      *slot = e;
+      return e;
+    }
+
+  if (GET_CODE (x) == MEM)
+    return cselib_lookup_mem (x, create);
+
+  hashval = hash_rtx (x, mode, create);
+  /* Can't even create if hashing is not possible.  */
+  if (! hashval)
+    return 0;
+
+  slot = htab_find_slot_with_hash (hash_table, x, hashval, create);
+  if (slot == 0)
+    return 0;
+  e = (cselib_val *) *slot;
+  if (e)
+    return e;
+
+  e = new_cselib_val (hashval, mode);
+  e->locs = new_elt_loc_list (e->locs, cselib_subst_to_values (x));
+  *slot = (void *) e;
+  return e;
+}
+
+/* Invalidate any entries in reg_values that overlap REGNO.  This is called
+   if REGNO is changing.  MODE is the mode of the assignment to REGNO, which
+   is used to determine how many hard registers are being changed.  If MODE
+   is VOIDmode, then only REGNO is being changed; this is used when
+   invalidating call clobbered registers across a call.  */
+static void
+cselib_invalidate_regno (regno, mode)
+     int regno;
+     enum machine_mode mode;
+{
+  int endregno;
+  int i;
+
+  /* If we see pseudos after reload, something is _wrong_.  */
+  if (reload_completed && regno >= FIRST_PSEUDO_REGISTER
+      && reg_renumber[regno] >= 0)
+    abort ();
+
+  /* Determine the range of registers that must be invalidated.  For
+     pseudos, only REGNO is affected.  For hard regs, we must take MODE
+     into account, and we must also invalidate lower register numbers
+     if they contain values that overlap REGNO.  */
+  endregno = regno + 1;
+  if (regno < FIRST_PSEUDO_REGISTER && mode != VOIDmode) 
+    endregno = regno + HARD_REGNO_NREGS (regno, mode);
+
+  for (i = 0; i < endregno; i++)
+    {
+      struct elt_list **l = &REG_VALUES (i);
+
+      /* Go through all known values for this reg; if it overlaps the range
+	 we're invalidating, remove the value.  */
+      while (*l)
+	{
+	  cselib_val *v = (*l)->elt;
+	  struct elt_loc_list **p;
+	  int this_last = i;
+
+	  if (i < FIRST_PSEUDO_REGISTER)
+	    this_last += HARD_REGNO_NREGS (i, GET_MODE (v->u.val_rtx)) - 1;
+	  if (this_last < regno)
+	    {
+	      l = &(*l)->next;
+	      continue;
+	    }
+	  /* We have an overlap.  */
+	  unchain_one_elt_list (l);
+
+	  /* Now, we clear the mapping from value to reg.  It must exist, so
+	     this code will crash intentionally if it doesn't.  */
+	  for (p = &v->locs; ; p = &(*p)->next)
+	    {
+	      rtx x = (*p)->loc;
+	      if (GET_CODE (x) == REG && REGNO (x) == i)
+		{
+		  unchain_one_elt_loc_list (p);
+		  break;
+		}
+	    }
+	  check_value_useless (v);
+	}
+    }
+}
+
+/* The memory at address MEM_BASE is being changed.
+   Return whether this change will invalidate VAL.  */
+static int
+cselib_mem_conflict_p (mem_base, val)
+     rtx mem_base;
+     rtx val;
+{
+  enum rtx_code code;
+  const char *fmt;
+  int i;
+
+  code = GET_CODE (val);
+  switch (code)
+    {
+      /* Get rid of a few simple cases quickly. */
+    case REG:
+    case PC:
+    case CC0:
+    case SCRATCH:
+    case CONST:
+    case CONST_INT:
+    case CONST_DOUBLE:
+    case SYMBOL_REF:
+    case LABEL_REF:
+      return 0;
+
+    case MEM:
+      if (GET_MODE (mem_base) == BLKmode
+	  || GET_MODE (val) == BLKmode)
+	return 1;
+      if (anti_dependence (val, mem_base))
+	return 1;
+      /* The address may contain nested MEMs.  */
+      break;
+
+    default:
+      break;
+    }
+
+  fmt = GET_RTX_FORMAT (code);
+
+  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+    {
+      if (fmt[i] == 'e')
+	{
+	  if (cselib_mem_conflict_p (mem_base, XEXP (val, i)))
+	    return 1;
+	}
+      else if (fmt[i] == 'E')
+	{
+	  int j;
+
+	  for (j = 0; j < XVECLEN (val, i); j++)
+	    if (cselib_mem_conflict_p (mem_base, XVECEXP (val, i, j)))
+	      return 1;
+	}
+    }
+
+  return 0;
+}
+
+/* For the value found in SLOT, walk its locations to determine if any overlap
+   INFO (which is a MEM rtx).  */
+static int
+cselib_invalidate_mem_1 (slot, info)
+     void **slot;
+     void *info;
+{
+  cselib_val *v = (cselib_val *) *slot;
+  rtx mem_rtx = (rtx) info;
+  struct elt_loc_list **p = &v->locs;
+
+  while (*p)
+    {
+      cselib_val *addr;
+      struct elt_list **mem_chain;
+      rtx x = (*p)->loc;
+
+      /* MEMs may occur in locations only at the top level; below
+	 that every MEM or REG is substituted by its VALUE.  */
+      if (GET_CODE (x) != MEM
+	  || ! cselib_mem_conflict_p (mem_rtx, x))
+	{
+	  p = &(*p)->next;
+	  continue;
+	}
+
+      /* This one overlaps.  */
+      /* We must have a mapping from this MEM's address to the
+	 value (E).  Remove that, too.  */
+      addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0);
+      mem_chain = &addr->addr_list;
+      for (;;)
+	{
+	  if ((*mem_chain)->elt == v)
+	    {
+	      unchain_one_elt_list (mem_chain);
+	      break;
+	    }
+	  mem_chain = &(*mem_chain)->next;
+	}
+      unchain_one_elt_loc_list (p);
+    }
+  check_value_useless (v);
+  return 1;
+}
+
+/* Invalidate any locations in the table which are changed because of a
+   store to MEM_RTX.  If this is called because of a non-const call
+   instruction, MEM_RTX is (mem:BLK const0_rtx).  */
+static void
+cselib_invalidate_mem (mem_rtx)
+     rtx mem_rtx;
+{
+  htab_traverse (hash_table, cselib_invalidate_mem_1, mem_rtx);
+}
+
+/* Invalidate DEST, which is being assigned to or clobbered.  The second and
+   the third parameter exist so that this function can be passed to
+   note_stores; they are ignored.  */
+static void
+cselib_invalidate_rtx (dest, ignore, data)
+     rtx dest;
+     rtx ignore ATTRIBUTE_UNUSED;
+     void *data ATTRIBUTE_UNUSED;
+{
+  while (GET_CODE (dest) == STRICT_LOW_PART
+	 || GET_CODE (dest) == SIGN_EXTRACT
+	 || GET_CODE (dest) == ZERO_EXTRACT
+	 || GET_CODE (dest) == SUBREG)
+    dest = XEXP (dest, 0);
+
+  if (GET_CODE (dest) == REG)
+    cselib_invalidate_regno (REGNO (dest), GET_MODE (dest));
+  else if (GET_CODE (dest) == MEM)
+    cselib_invalidate_mem (dest);
+
+  /* Some machines don't define AUTO_INC_DEC, but they still use push
+     instructions.  We need to catch that case here in order to
+     invalidate the stack pointer correctly.  Note that invalidating
+     the stack pointer is different from invalidating DEST.  */
+  if (push_operand (dest, GET_MODE (dest)))
+    cselib_invalidate_rtx (stack_pointer_rtx, NULL_RTX, NULL);
+}
+
+/* Record the result of a SET instruction.  DEST is being set; the source
+   contains the value described by SRC_ELT.  If DEST is a MEM, DEST_ADDR_ELT
+   describes its address.  */
+static void
+cselib_record_set (dest, src_elt, dest_addr_elt)
+     rtx dest;
+     cselib_val *src_elt, *dest_addr_elt;
+{
+  int dreg = GET_CODE (dest) == REG ? REGNO (dest) : -1;
+
+  if (src_elt == 0 || side_effects_p (dest))
+    return;
+
+  if (dreg >= 0)
+    {
+      REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt);
+      src_elt->locs = new_elt_loc_list (src_elt->locs, dest);
+    }
+  else if (GET_CODE (dest) == MEM && dest_addr_elt != 0)
+    add_mem_for_addr (dest_addr_elt, src_elt, dest);
+}
+
+/* Describe a single set that is part of an insn.  */
+struct set
+{
+  rtx src;
+  rtx dest;
+  cselib_val *src_elt;
+  cselib_val *dest_addr_elt;
+};
+
+/* There is no good way to determine how many elements there can be
+   in a PARALLEL.  Since it's fairly cheap, use a really large number.  */
+#define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
+
+/* Record the effects of any sets in INSN.  */
+static void
+cselib_record_sets (insn)
+     rtx insn;
+{
+  int n_sets = 0;
+  int i;
+  struct set sets[MAX_SETS];
+  rtx body = PATTERN (insn);
+
+  body = PATTERN (insn);
+  /* Find all sets.  */
+  if (GET_CODE (body) == SET)
+    {
+      sets[0].src = SET_SRC (body);
+      sets[0].dest = SET_DEST (body);
+      n_sets = 1;
+    }
+  else if (GET_CODE (body) == PARALLEL)
+    {
+      /* Look through the PARALLEL and record the values being
+	 set, if possible.  Also handle any CLOBBERs.  */
+      for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
+	{
+	  rtx x = XVECEXP (body, 0, i);
+
+	  if (GET_CODE (x) == SET)
+	    {
+	      sets[n_sets].src = SET_SRC (x);
+	      sets[n_sets].dest = SET_DEST (x);
+	      n_sets++;
+	    }
+	}
+    }
+
+  /* Look up the values that are read.  Do this before invalidating the
+     locations that are written.  */
+  for (i = 0; i < n_sets; i++)
+    {
+      sets[i].src_elt = cselib_lookup (sets[i].src, GET_MODE (sets[i].dest),
+				       1);
+      if (GET_CODE (sets[i].dest) == MEM)
+	sets[i].dest_addr_elt = cselib_lookup (XEXP (sets[i].dest, 0), Pmode,
+					       1);
+      else
+	sets[i].dest_addr_elt = 0;
+    }
+
+  /* Invalidate all locations written by this insn.  Note that the elts we
+     looked up in the previous loop aren't affected, just some of their
+     locations may go away.  */
+  note_stores (body, cselib_invalidate_rtx, NULL);
+
+  /* Now enter the equivalences in our tables.  */
+  for (i = 0; i < n_sets; i++)
+    cselib_record_set (sets[i].dest, sets[i].src_elt, sets[i].dest_addr_elt);
+}
+
+/* Record the effects of INSN.  */
+void
+cselib_process_insn (insn)
+     rtx insn;
+{
+  int i;
+
+  cselib_current_insn = insn;
+
+  /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp.  */
+  if (GET_CODE (insn) == CODE_LABEL
+      || (GET_CODE (insn) == NOTE
+	  && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
+      || (GET_CODE (insn) == INSN
+	  && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
+	  && MEM_VOLATILE_P (PATTERN (insn))))
+    {
+      clear_table ();
+      return;
+    }
+
+  if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
+    {
+      cselib_current_insn = 0;
+      return;
+    }
+  /* If this is a call instruction, forget anything stored in a
+     call clobbered register, or, if this is not a const call, in
+     memory.  */
+  if (GET_CODE (insn) == CALL_INSN)
+    {
+      for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+	if (call_used_regs[i])
+	  cselib_invalidate_regno (i, VOIDmode);
+
+      if (! CONST_CALL_P (insn))
+	cselib_invalidate_mem (callmem);
+    }
+
+  cselib_record_sets (insn);
+
+#ifdef AUTO_INC_DEC
+  /* Clobber any registers which appear in REG_INC notes.  We
+     could keep track of the changes to their values, but it is
+     unlikely to help.  */
+  {
+    rtx x;
+
+    for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
+      if (REG_NOTE_KIND (x) == REG_INC)
+	cselib_invalidate_rtx (XEXP (x, 0), NULL_RTX, NULL);
+  }
+#endif
+
+  /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
+     after we have processed the insn.  */
+  if (GET_CODE (insn) == CALL_INSN)
+    {
+      rtx x;
+
+      for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1))
+	if (GET_CODE (XEXP (x, 0)) == CLOBBER)
+	  cselib_invalidate_rtx (XEXP (XEXP (x, 0), 0), NULL_RTX,
+				     NULL);
+    }
+
+  cselib_current_insn = 0;
+
+  if (n_useless_values > MAX_USELESS_VALUES)
+    remove_useless_values ();
+}
+
+/* Make sure our varrays are big enough.  Not called from any cselib routines;
+   it must be called by the user if it allocated new registers.  */
+void
+cselib_update_varray_sizes ()
+{
+  int nregs = max_reg_num ();
+  if (nregs == cselib_nregs)
+    return;
+  cselib_nregs = nregs;
+  VARRAY_GROW (reg_values, nregs);
+}
+
+/* Initialize cselib for one pass.  The caller must also call
+   init_alias_analysis.  */
+void
+cselib_init ()
+{
+  /* These are only created once.  */
+  if (! callmem)
+    {
+      extern struct obstack permanent_obstack;
+      gcc_obstack_init (&cselib_obstack);
+      cselib_startobj = obstack_alloc (&cselib_obstack, 0);
+
+      push_obstacks (&permanent_obstack, &permanent_obstack);
+      callmem = gen_rtx_MEM (BLKmode, const0_rtx);
+      pop_obstacks ();
+      ggc_add_rtx_root (&callmem, 1);
+    }
+
+  cselib_nregs = max_reg_num ();
+  VARRAY_ELT_LIST_INIT (reg_values, cselib_nregs, "reg_values");
+  hash_table = htab_create (31, get_value_hash, entry_and_rtx_equal_p, NULL);
+  clear_table ();
+}
+
+/* Called when the current user is done with cselib.  */
+void
+cselib_finish ()
+{
+  clear_table ();
+  htab_delete (hash_table);
+}