/* Common subexpression elimination for GNU compiler.
- Copyright (C) 1987, 88, 89, 92-7, 1998, 1999 Free Software Foundation, Inc.
+ Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
+ 1999, 2000 Free Software Foundation, Inc.
This file is part of GNU CC.
#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. */
|| GET_CODE (X) == ADDRESSOF)
-static rtx simplify_plus_minus PROTO((enum rtx_code, enum machine_mode,
+static rtx simplify_plus_minus PARAMS ((enum rtx_code, enum machine_mode,
rtx, rtx));
-static void check_fold_consts PROTO((PTR));
+static void check_fold_consts PARAMS ((PTR));
/* Make a binary operation by properly ordering the operands and
seeing if the expression folds. */
rtx op;
enum machine_mode op_mode;
{
- register int width = GET_MODE_BITSIZE (mode);
+ unsigned 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,
{
register HOST_WIDE_INT arg0, arg1, arg0s, arg1s;
HOST_WIDE_INT val;
- int width = GET_MODE_BITSIZE (mode);
+ unsigned int width = GET_MODE_BITSIZE (mode);
rtx tem;
/* Relational operations don't work here. We must know the mode
)
return 0;
+ /* Make sure the constant is second. */
+ if ((CONSTANT_P (op0) && ! CONSTANT_P (op1))
+ || (GET_CODE (op0) == CONST_INT && GET_CODE (op1) != CONST_INT))
+ {
+ tem = op0, op0 = op1, op1 = tem;
+ code = swap_condition (code);
+ }
+
/* For integer comparisons of A and B maybe we can simplify A - B and can
then simplify a comparison of that with zero. If A and B are both either
a register or a CONST_INT, this can't help; testing for these cases will
return NULL;
}
}
+\f
+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 ((unsigned 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;
+ const cselib_val *v = (const 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;
+{
+ const cselib_val *v = (const 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;
+ enum rtx_code code;
+ const char *fmt;
+ unsigned int hash = 0;
+
+ /* repeat is used to turn tail-recursion into iteration. */
+ repeat:
+ code = GET_CODE (x);
+ hash += (unsigned) code + (unsigned) GET_MODE (x);
+
+ switch (code)
+ {
+ case MEM:
+ case REG:
+ e = cselib_lookup (x, GET_MODE (x), create);
+ if (! e)
+ return 0;
+ hash += e->value;
+ return hash;
+
+ 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;
+ 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')
+ {
+ const unsigned char *p = (const 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);
+ /* We have to fill the slot before calling cselib_subst_to_values:
+ the hash table is inconsistent until we do so, and
+ cselib_subst_to_values will need to do lookups. */
+ *slot = (void *) e;
+ e->locs = new_elt_loc_list (e->locs, cselib_subst_to_values (x));
+ 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)
+ unsigned int regno;
+ enum machine_mode mode;
+{
+ unsigned int endregno;
+ unsigned 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 = ®_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;
+ unsigned 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 ? (int) 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);
+}
OSDN Git Service
