diff options
Diffstat (limited to 'gcc/simplify-rtx.c')
| -rw-r--r-- | gcc/simplify-rtx.c | 1336 |
1 files changed, 1 insertions, 1335 deletions
diff --git a/gcc/simplify-rtx.c b/gcc/simplify-rtx.c index afd8d264b62..fa3dfe17f0f 100644 --- a/gcc/simplify-rtx.c +++ b/gcc/simplify-rtx.c @@ -37,9 +37,6 @@ Boston, MA 02111-1307, USA. */ #include "toplev.h" #include "output.h" #include "ggc.h" -#include "obstack.h" -#include "hashtab.h" -#include "cselib.h" /* Simplification and canonicalization of RTL. */ @@ -102,94 +99,6 @@ Boston, MA 02111-1307, USA. */ static rtx simplify_plus_minus PARAMS ((enum rtx_code, enum machine_mode, rtx, rtx)); static void check_fold_consts PARAMS ((PTR)); -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 ((int)); -static int discard_useless_locs PARAMS ((void **, void *)); -static int discard_useless_values PARAMS ((void **, void *)); -static void remove_useless_values PARAMS ((void)); -static rtx wrap_constant PARAMS ((enum machine_mode, rtx)); -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 unsigned 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)) - -/* Here the set of indices I with REG_VALUES(I) != 0 is saved. This is used - in clear_table() for fast emptying. */ -static varray_type used_regs; - -/* 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; - -/* Set by discard_useless_locs if it deleted the last location of any - value. */ -static int values_became_useless; /* Make a binary operation by properly ordering the operands and seeing if the expression folds. */ @@ -1798,7 +1707,7 @@ simplify_relational_operation (code, mode, op0, op1) args.op1 = op1; - if (!do_float_handler(check_fold_consts, (PTR) &args)) + if (!do_float_handler (check_fold_consts, (PTR) &args)) args.unordered = 1; if (args.unordered) @@ -2184,1246 +2093,3 @@ simplify_rtx (x) return NULL; } } - - -/* 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. If CLEAR_ALL isn't set, then only clear the entries - which are known to have been used. */ - -static void -clear_table (clear_all) - int clear_all; -{ - unsigned int i; - - if (clear_all) - for (i = 0; i < cselib_nregs; i++) - REG_VALUES (i) = 0; - else - for (i = 0; i < VARRAY_ACTIVE_SIZE (used_regs); i++) - REG_VALUES (VARRAY_UINT (used_regs, i)) = 0; - - VARRAY_POP_ALL (used_regs); - - 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. We know - that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a - CONST of an appropriate mode. */ - -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; - enum machine_mode mode = GET_MODE (x); - - if (GET_CODE (x) == CONST_INT - || (mode == VOIDmode && GET_CODE (x) == CONST_DOUBLE)) - abort (); - if (mode != GET_MODE (v->u.val_rtx)) - return 0; - - /* Unwrap X if necessary. */ - if (GET_CODE (x) == CONST - && (GET_CODE (XEXP (x, 0)) == CONST_INT - || GET_CODE (XEXP (x, 0)) == CONST_DOUBLE)) - x = XEXP (x, 0); - - /* 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; -} - -/* 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, j; - - if (GET_CODE (x) == VALUE - && (! only_useless || CSELIB_VAL_PTR (x)->locs == 0)) - return 1; - - for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) - { - if (fmt[i] == 'e' && references_value_p (XEXP (x, i), only_useless)) - return 1; - else if (fmt[i] == 'E') - for (j = 0; j < XVECLEN (x, i); j++) - if (references_value_p (XVECEXP (x, i, j), only_useless)) - return 1; - } - - return 0; -} - -/* 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; - int had_locs = v->locs != 0; - - while (*p) - { - if (references_value_p ((*p)->loc, 1)) - unchain_one_elt_loc_list (p); - else - p = &(*p)->next; - } - - if (had_locs && v->locs == 0) - { - n_useless_values++; - 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->locs == 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, GET_MODE (x), 0); - - if (e) - x = e->u.val_rtx; - } - - if (GET_CODE (y) == REG || GET_CODE (y) == MEM) - { - cselib_val *e = cselib_lookup (y, GET_MODE (y), 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; - else 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; - else 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; -} - -/* We need to pass down the mode of constants through the hash table - functions. For that purpose, wrap them in a CONST of the appropriate - mode. */ -static rtx -wrap_constant (mode, x) - enum machine_mode mode; - rtx x; -{ - if (GET_CODE (x) != CONST_INT - && (GET_CODE (x) != CONST_DOUBLE || GET_MODE (x) != VOIDmode)) - return x; - if (mode == VOIDmode) - abort (); - return gen_rtx_CONST (mode, x); -} - -/* 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: - hash += ((unsigned) CONST_INT << 7) + (unsigned) mode + INTVAL (x); - 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++) - hash += XWINT (x, i); - 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 POST_MODIFY: - case PRE_MODIFY: - 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') - { - rtx tem = XEXP (x, i); - unsigned int tem_hash; - - /* 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') - hash += XINT (x, i); - 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); - MEM_COPY_ATTRIBUTES (new, x); - - addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt); - 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; -{ - enum machine_mode mode = GET_MODE (x); - void **slot; - cselib_val *addr; - cselib_val *mem_elt; - struct elt_list *l; - - if (MEM_VOLATILE_P (x) || mode == BLKmode - || (FLOAT_MODE_P (mode) && flag_float_store)) - return 0; - - /* Look up the value for the address. */ - addr = cselib_lookup (XEXP (x, 0), mode, 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) == mode) - return l->elt; - - if (! create) - return 0; - - mem_elt = new_cselib_val (++next_unknown_value, mode); - add_mem_for_addr (addr, mem_elt, x); - slot = htab_find_slot_with_hash (hash_table, wrap_constant (mode, x), - mem_elt->value, INSERT); - *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: - for (l = REG_VALUES (REGNO (x)); 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; - unsigned 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); - if (REG_VALUES (i) == 0) - VARRAY_PUSH_UINT (used_regs, i); - REG_VALUES (i) = new_elt_list (REG_VALUES (i), e); - slot = htab_find_slot_with_hash (hash_table, x, e->value, INSERT); - *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, wrap_constant (mode, x), - hashval, create ? INSERT : NO_INSERT); - 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; - } - } - if (v->locs == 0) - n_useless_values++; - } - } -} - -/* 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, j; - - 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 - || 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') - 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; - int had_locs = v->locs != 0; - - while (*p) - { - rtx x = (*p)->loc; - cselib_val *addr; - struct elt_list **mem_chain; - - /* 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); - } - - if (had_locs && v->locs == 0) - n_useless_values++; - - 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) - { - if (REG_VALUES (dreg) == 0) - VARRAY_PUSH_UINT (used_regs, dreg); - - REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt); - if (src_elt->locs == 0) - n_useless_values--; - src_elt->locs = new_elt_loc_list (src_elt->locs, dest); - } - else if (GET_CODE (dest) == MEM && dest_addr_elt != 0) - { - if (src_elt->locs == 0) - n_useless_values--; - 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++) - { - rtx dest = sets[i].dest; - - /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for - the low part after invalidating any knowledge about larger modes. */ - if (GET_CODE (sets[i].dest) == STRICT_LOW_PART) - sets[i].dest = dest = XEXP (dest, 0); - - /* We don't know how to record anything but REG or MEM. */ - if (GET_CODE (dest) == REG || GET_CODE (dest) == MEM) - { - sets[i].src_elt = cselib_lookup (sets[i].src, GET_MODE (dest), 1); - if (GET_CODE (dest) == MEM) - sets[i].dest_addr_elt = cselib_lookup (XEXP (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++) - { - rtx dest = sets[i].dest; - if (GET_CODE (dest) == REG || GET_CODE (dest) == MEM) - cselib_record_set (dest, sets[i].src_elt, sets[i].dest_addr_elt); - } -} - -/* Record the effects of INSN. */ - -void -cselib_process_insn (insn) - rtx insn; -{ - int i; - rtx x; - - 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 (0); - return; - } - - if (! INSN_P (insn)) - { - 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. */ - 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) - 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 () -{ - unsigned int nregs = max_reg_num (); - - if (nregs == cselib_nregs) - return; - - cselib_nregs = nregs; - VARRAY_GROW (reg_values, nregs); - VARRAY_GROW (used_regs, nregs); -} - -/* Initialize cselib for one pass. The caller must also call - init_alias_analysis. */ - -void -cselib_init () -{ - /* These are only created once. */ - if (! callmem) - { - gcc_obstack_init (&cselib_obstack); - cselib_startobj = obstack_alloc (&cselib_obstack, 0); - - callmem = gen_rtx_MEM (BLKmode, const0_rtx); - ggc_add_rtx_root (&callmem, 1); - } - - cselib_nregs = max_reg_num (); - VARRAY_ELT_LIST_INIT (reg_values, cselib_nregs, "reg_values"); - VARRAY_UINT_INIT (used_regs, cselib_nregs, "used_regs"); - hash_table = htab_create (31, get_value_hash, entry_and_rtx_equal_p, NULL); - clear_table (1); -} - -/* Called when the current user is done with cselib. */ - -void -cselib_finish () -{ - clear_table (0); - VARRAY_FREE (reg_values); - VARRAY_FREE (used_regs); - htab_delete (hash_table); -} |