X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fcselib.c;h=66d92a01ad0d304bf2d6986c76470b6d0a2ed4e6;hb=f018d957a72d418d69c6d2d8bc80c9415666a9f6;hp=31a6d70a4bb0355c043a017f499a0f2b9517246e;hpb=ddffd2a9d389bf6a4c2a512c0fdc1412e5c04afb;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/cselib.c b/gcc/cselib.c index 31a6d70a4bb..66d92a01ad0 100644 --- a/gcc/cselib.c +++ b/gcc/cselib.c @@ -1,12 +1,13 @@ /* Common subexpression elimination library for GNU compiler. Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998, - 1999, 2000, 2001, 2003, 2004 Free Software Foundation, Inc. + 1999, 2000, 2001, 2003, 2004, 2005, 2006, 2007, 2008, 2009 + Free Software Foundation, Inc. This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free -Software Foundation; either version 2, or (at your option) any later +Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY @@ -15,9 +16,8 @@ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING. If not, write to the Free -Software Foundation, 59 Temple Place - Suite 330, Boston, MA -02111-1307, USA. */ +along with GCC; see the file COPYING3. If not see +. */ #include "config.h" #include "system.h" @@ -33,15 +33,18 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "insn-config.h" #include "recog.h" #include "function.h" -#include "expr.h" +#include "emit-rtl.h" #include "toplev.h" #include "output.h" #include "ggc.h" #include "hashtab.h" +#include "tree-pass.h" #include "cselib.h" #include "params.h" #include "alloc-pool.h" +#include "target.h" +static bool cselib_record_memory; static int entry_and_rtx_equal_p (const void *, const void *); static hashval_t get_value_hash (const void *); static struct elt_list *new_elt_list (struct elt_list *, cselib_val *); @@ -49,21 +52,27 @@ static struct elt_loc_list *new_elt_loc_list (struct elt_loc_list *, rtx); static void unchain_one_value (cselib_val *); static void unchain_one_elt_list (struct elt_list **); static void unchain_one_elt_loc_list (struct elt_loc_list **); -static void clear_table (void); static int discard_useless_locs (void **, void *); static int discard_useless_values (void **, void *); static void remove_useless_values (void); -static rtx wrap_constant (enum machine_mode, rtx); -static unsigned int hash_rtx (rtx, enum machine_mode, int); -static cselib_val *new_cselib_val (unsigned int, enum machine_mode); +static unsigned int cselib_hash_rtx (rtx, int); +static cselib_val *new_cselib_val (unsigned int, enum machine_mode, rtx); static void add_mem_for_addr (cselib_val *, cselib_val *, rtx); static cselib_val *cselib_lookup_mem (rtx, int); static void cselib_invalidate_regno (unsigned int, enum machine_mode); static void cselib_invalidate_mem (rtx); -static void cselib_invalidate_rtx (rtx, rtx, void *); static void cselib_record_set (rtx, cselib_val *, cselib_val *); static void cselib_record_sets (rtx); +struct expand_value_data +{ + bitmap regs_active; + cselib_expand_callback callback; + void *callback_arg; +}; + +static rtx cselib_expand_value_rtx_1 (rtx, struct expand_value_data *, int); + /* 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 @@ -74,12 +83,11 @@ static void cselib_record_sets (rtx); 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; +static htab_t cselib_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; -static bool cselib_current_insn_in_libcall; /* Every new unknown value gets a unique number. */ static unsigned int next_unknown_value; @@ -101,16 +109,16 @@ static int n_useless_values; which the register was set; if the mode is unknown or the value is no longer valid in that mode, ELT will be NULL for the first element. */ -struct elt_list **reg_values; -unsigned int reg_values_size; +static struct elt_list **reg_values; +static unsigned int reg_values_size; #define REG_VALUES(i) reg_values[i] /* The largest number of hard regs used by any entry added to the - REG_VALUES table. Cleared on each clear_table() invocation. */ + REG_VALUES table. Cleared on each cselib_clear_table() invocation. */ static unsigned int max_value_regs; /* Here the set of indices I with REG_VALUES(I) != 0 is saved. This is used - in clear_table() for fast emptying. */ + in cselib_clear_table() for fast emptying. */ static unsigned int *used_regs; static unsigned int n_used_regs; @@ -131,6 +139,24 @@ static cselib_val dummy_val; each time memory is invalidated. */ static cselib_val *first_containing_mem = &dummy_val; static alloc_pool elt_loc_list_pool, elt_list_pool, cselib_val_pool, value_pool; + +/* If nonnull, cselib will call this function before freeing useless + VALUEs. A VALUE is deemed useless if its "locs" field is null. */ +void (*cselib_discard_hook) (cselib_val *); + +/* If nonnull, cselib will call this function before recording sets or + even clobbering outputs of INSN. All the recorded sets will be + represented in the array sets[n_sets]. new_val_min can be used to + tell whether values present in sets are introduced by this + instruction. */ +void (*cselib_record_sets_hook) (rtx insn, struct cselib_set *sets, + int n_sets); + +#define PRESERVED_VALUE_P(RTX) \ + (RTL_FLAG_CHECK1("PRESERVED_VALUE_P", (RTX), VALUE)->unchanging) +#define LONG_TERM_PRESERVED_VALUE_P(RTX) \ + (RTL_FLAG_CHECK1("LONG_TERM_PRESERVED_VALUE_P", (RTX), VALUE)->in_struct) + /* Allocate a struct elt_list and fill in its two elements with the @@ -140,7 +166,7 @@ static inline struct elt_list * new_elt_list (struct elt_list *next, cselib_val *elt) { struct elt_list *el; - el = pool_alloc (elt_list_pool); + el = (struct elt_list *) pool_alloc (elt_list_pool); el->next = next; el->elt = elt; return el; @@ -153,12 +179,10 @@ static inline struct elt_loc_list * new_elt_loc_list (struct elt_loc_list *next, rtx loc) { struct elt_loc_list *el; - el = pool_alloc (elt_loc_list_pool); + el = (struct elt_loc_list *) pool_alloc (elt_loc_list_pool); el->next = next; el->loc = loc; - el->canon_loc = NULL; el->setting_insn = cselib_current_insn; - el->in_libcall = cselib_current_insn_in_libcall; return el; } @@ -198,11 +222,19 @@ unchain_one_value (cselib_val *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. */ + initialization. */ -static void -clear_table (void) +void +cselib_clear_table (void) +{ + cselib_reset_table_with_next_value (0); +} + +/* Remove all entries from the hash table, arranging for the next + value to be numbered NUM. */ + +void +cselib_reset_table_with_next_value (unsigned int num) { unsigned int i; @@ -213,15 +245,24 @@ clear_table (void) n_used_regs = 0; - htab_empty (hash_table); + /* ??? Preserve constants? */ + htab_empty (cselib_hash_table); n_useless_values = 0; - next_unknown_value = 0; + next_unknown_value = num; first_containing_mem = &dummy_val; } +/* Return the number of the next value that will be generated. */ + +unsigned int +cselib_get_next_unknown_value (void) +{ + return next_unknown_value; +} + /* 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 @@ -231,19 +272,20 @@ static int entry_and_rtx_equal_p (const void *entry, const void *x_arg) { struct elt_loc_list *l; - const cselib_val *v = (const cselib_val *) entry; - rtx x = (rtx) x_arg; + const cselib_val *const v = (const cselib_val *) entry; + rtx x = CONST_CAST_RTX ((const_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)) + gcc_assert (!CONST_INT_P (x) && GET_CODE (x) != CONST_FIXED + && (mode != VOIDmode || GET_CODE (x) != CONST_DOUBLE)); + + if (mode != GET_MODE (v->val_rtx)) return 0; /* Unwrap X if necessary. */ if (GET_CODE (x) == CONST - && (GET_CODE (XEXP (x, 0)) == CONST_INT + && (CONST_INT_P (XEXP (x, 0)) + || GET_CODE (XEXP (x, 0)) == CONST_FIXED || GET_CODE (XEXP (x, 0)) == CONST_DOUBLE)) x = XEXP (x, 0); @@ -257,13 +299,13 @@ entry_and_rtx_equal_p (const void *entry, const void *x_arg) } /* 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. */ + cselib_hash_rtx when adding an element; this function just extracts the + hash value from a cselib_val structure. */ static hashval_t get_value_hash (const void *entry) { - const cselib_val *v = (const cselib_val *) entry; + const cselib_val *const v = (const cselib_val *) entry; return v->value; } @@ -273,9 +315,9 @@ get_value_hash (const void *entry) removed. */ int -references_value_p (rtx x, int only_useless) +references_value_p (const_rtx x, int only_useless) { - enum rtx_code code = GET_CODE (x); + const enum rtx_code code = GET_CODE (x); const char *fmt = GET_RTX_FORMAT (code); int i, j; @@ -315,7 +357,7 @@ discard_useless_locs (void **x, void *info ATTRIBUTE_UNUSED) p = &(*p)->next; } - if (had_locs && v->locs == 0) + if (had_locs && v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx)) { n_useless_values++; values_became_useless = 1; @@ -330,10 +372,13 @@ discard_useless_values (void **x, void *info ATTRIBUTE_UNUSED) { cselib_val *v = (cselib_val *)*x; - if (v->locs == 0) + if (v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx)) { - CSELIB_VAL_PTR (v->u.val_rtx) = NULL; - htab_clear_slot (hash_table, x); + if (cselib_discard_hook) + cselib_discard_hook (v); + + CSELIB_VAL_PTR (v->val_rtx) = NULL; + htab_clear_slot (cselib_hash_table, x); unchain_one_value (v); n_useless_values--; } @@ -353,7 +398,7 @@ remove_useless_values (void) do { values_became_useless = 0; - htab_traverse (hash_table, discard_useless_locs, 0); + htab_traverse (cselib_hash_table, discard_useless_locs, 0); } while (values_became_useless); @@ -368,10 +413,81 @@ remove_useless_values (void) } *p = &dummy_val; - htab_traverse (hash_table, discard_useless_values, 0); + htab_traverse (cselib_hash_table, discard_useless_values, 0); + + gcc_assert (!n_useless_values); +} + +/* Arrange for a value to not be removed from the hash table even if + it becomes useless. */ + +void +cselib_preserve_value (cselib_val *v) +{ + PRESERVED_VALUE_P (v->val_rtx) = 1; +} + +/* Test whether a value is preserved. */ + +bool +cselib_preserved_value_p (cselib_val *v) +{ + return PRESERVED_VALUE_P (v->val_rtx); +} + +/* Mark preserved values as preserved for the long term. */ + +static int +cselib_preserve_definitely (void **slot, void *info ATTRIBUTE_UNUSED) +{ + cselib_val *v = (cselib_val *)*slot; + + if (PRESERVED_VALUE_P (v->val_rtx) + && !LONG_TERM_PRESERVED_VALUE_P (v->val_rtx)) + LONG_TERM_PRESERVED_VALUE_P (v->val_rtx) = true; - if (n_useless_values != 0) - abort (); + return 1; +} + +/* Clear the preserve marks for values not preserved for the long + term. */ + +static int +cselib_clear_preserve (void **slot, void *info ATTRIBUTE_UNUSED) +{ + cselib_val *v = (cselib_val *)*slot; + + if (PRESERVED_VALUE_P (v->val_rtx) + && !LONG_TERM_PRESERVED_VALUE_P (v->val_rtx)) + { + PRESERVED_VALUE_P (v->val_rtx) = false; + if (!v->locs) + n_useless_values++; + } + + return 1; +} + +/* Clean all non-constant expressions in the hash table, but retain + their values. */ + +void +cselib_preserve_only_values (bool retain) +{ + int i; + + htab_traverse (cselib_hash_table, + retain ? cselib_preserve_definitely : cselib_clear_preserve, + NULL); + + for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) + cselib_invalidate_regno (i, reg_raw_mode[i]); + + cselib_invalidate_mem (callmem); + + remove_useless_values (); + + gcc_assert (first_containing_mem == &dummy_val); } /* Return the mode in which a register was last set. If X is not a @@ -380,16 +496,16 @@ remove_useless_values (void) VOIDmode. */ enum machine_mode -cselib_reg_set_mode (rtx x) +cselib_reg_set_mode (const_rtx x) { - if (GET_CODE (x) != REG) + if (!REG_P (x)) return GET_MODE (x); if (REG_VALUES (REGNO (x)) == NULL || REG_VALUES (REGNO (x))->elt == NULL) return VOIDmode; - return GET_MODE (REG_VALUES (REGNO (x))->elt->u.val_rtx); + return GET_MODE (REG_VALUES (REGNO (x))->elt->val_rtx); } /* Return nonzero if we can prove that X and Y contain the same value, taking @@ -402,20 +518,20 @@ rtx_equal_for_cselib_p (rtx x, rtx y) const char *fmt; int i; - if (GET_CODE (x) == REG || GET_CODE (x) == MEM) + if (REG_P (x) || MEM_P (x)) { cselib_val *e = cselib_lookup (x, GET_MODE (x), 0); if (e) - x = e->u.val_rtx; + x = e->val_rtx; } - if (GET_CODE (y) == REG || GET_CODE (y) == MEM) + if (REG_P (y) || MEM_P (y)) { cselib_val *e = cselib_lookup (y, GET_MODE (y), 0); if (e) - y = e->u.val_rtx; + y = e->val_rtx; } if (x == y) @@ -434,7 +550,7 @@ rtx_equal_for_cselib_p (rtx x, rtx y) rtx t = l->loc; /* Avoid infinite recursion. */ - if (GET_CODE (t) == REG || GET_CODE (t) == MEM) + if (REG_P (t) || MEM_P (t)) continue; else if (rtx_equal_for_cselib_p (t, y)) return 1; @@ -452,7 +568,7 @@ rtx_equal_for_cselib_p (rtx x, rtx y) { rtx t = l->loc; - if (GET_CODE (t) == REG || GET_CODE (t) == MEM) + if (REG_P (t) || MEM_P (t)) continue; else if (rtx_equal_for_cselib_p (x, t)) return 1; @@ -464,9 +580,20 @@ rtx_equal_for_cselib_p (rtx x, rtx y) 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); + /* These won't be handled correctly by the code below. */ + switch (GET_CODE (x)) + { + case CONST_DOUBLE: + case CONST_FIXED: + case DEBUG_EXPR: + return 0; + + case LABEL_REF: + return XEXP (x, 0) == XEXP (y, 0); + + default: + break; + } code = GET_CODE (x); fmt = GET_RTX_FORMAT (code); @@ -502,6 +629,11 @@ rtx_equal_for_cselib_p (rtx x, rtx y) break; case 'e': + if (i == 1 + && targetm.commutative_p (x, UNKNOWN) + && rtx_equal_for_cselib_p (XEXP (x, 1), XEXP (y, 0)) + && rtx_equal_for_cselib_p (XEXP (x, 0), XEXP (y, 1))) + return 1; if (! rtx_equal_for_cselib_p (XEXP (x, i), XEXP (y, i))) return 0; break; @@ -524,7 +656,7 @@ rtx_equal_for_cselib_p (rtx x, rtx y) contain anything but integers and other rtx's, except for within LABEL_REFs and SYMBOL_REFs. */ default: - abort (); + gcc_unreachable (); } } return 1; @@ -536,11 +668,10 @@ rtx_equal_for_cselib_p (rtx x, rtx y) static rtx wrap_constant (enum machine_mode mode, rtx x) { - if (GET_CODE (x) != CONST_INT + if (!CONST_INT_P (x) && GET_CODE (x) != CONST_FIXED && (GET_CODE (x) != CONST_DOUBLE || GET_MODE (x) != VOIDmode)) return x; - if (mode == VOIDmode) - abort (); + gcc_assert (mode != VOIDmode); return gen_rtx_CONST (mode, x); } @@ -550,11 +681,22 @@ wrap_constant (enum machine_mode mode, rtx x) 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. */ + N.B. this hash function returns the same hash value for RTXes that + differ only in the order of operands, thus it is suitable for comparisons + that take commutativity into account. + If we wanted to also support associative rules, we'd have to use a different + strategy to avoid returning spurious 0, e.g. return ~(~0U >> 1) . + We used to have a MODE argument for hashing for CONST_INTs, but that + didn't make sense, since it caused spurious hash differences between + (set (reg:SI 1) (const_int)) + (plus:SI (reg:SI 2) (reg:SI 1)) + and + (plus:SI (reg:SI 2) (const_int)) + If the mode is important in any context, it must be checked specifically + in a comparison anyway, since relying on hash differences is unsafe. */ static unsigned int -hash_rtx (rtx x, enum machine_mode mode, int create) +cselib_hash_rtx (rtx x, int create) { cselib_val *e; int i, j; @@ -575,8 +717,13 @@ hash_rtx (rtx x, enum machine_mode mode, int create) return e->value; + case DEBUG_EXPR: + hash += ((unsigned) DEBUG_EXPR << 7) + + DEBUG_TEMP_UID (DEBUG_EXPR_TREE_DECL (x)); + return hash ? hash : (unsigned int) DEBUG_EXPR; + case CONST_INT: - hash += ((unsigned) CONST_INT << 7) + (unsigned) mode + INTVAL (x); + hash += ((unsigned) CONST_INT << 7) + INTVAL (x); return hash ? hash : (unsigned int) CONST_INT; case CONST_DOUBLE: @@ -590,6 +737,11 @@ hash_rtx (rtx x, enum machine_mode mode, int create) + (unsigned) CONST_DOUBLE_HIGH (x)); return hash ? hash : (unsigned int) CONST_DOUBLE; + case CONST_FIXED: + hash += (unsigned int) code + (unsigned int) GET_MODE (x); + hash += fixed_hash (CONST_FIXED_VALUE (x)); + return hash ? hash : (unsigned int) CONST_FIXED; + case CONST_VECTOR: { int units; @@ -600,7 +752,7 @@ hash_rtx (rtx x, enum machine_mode mode, int create) for (i = 0; i < units; ++i) { elt = CONST_VECTOR_ELT (x, i); - hash += hash_rtx (elt, GET_MODE (elt), 0); + hash += cselib_hash_rtx (elt, 0); } return hash; @@ -608,14 +760,28 @@ hash_rtx (rtx x, enum machine_mode mode, int create) /* Assume there is only one rtx object for any given label. */ case LABEL_REF: - hash - += ((unsigned) LABEL_REF << 7) + (unsigned long) XEXP (x, 0); + /* We don't hash on the address of the CODE_LABEL to avoid bootstrap + differences and differences between each stage's debugging dumps. */ + hash += (((unsigned int) LABEL_REF << 7) + + CODE_LABEL_NUMBER (XEXP (x, 0))); return hash ? hash : (unsigned int) LABEL_REF; case SYMBOL_REF: - hash - += ((unsigned) SYMBOL_REF << 7) + (unsigned long) XSTR (x, 0); - return hash ? hash : (unsigned int) SYMBOL_REF; + { + /* Don't hash on the symbol's address to avoid bootstrap differences. + Different hash values may cause expressions to be recorded in + different orders and thus different registers to be used in the + final assembler. This also avoids differences in the dump files + between various stages. */ + unsigned int h = 0; + const unsigned char *p = (const unsigned char *) XSTR (x, 0); + + while (*p) + h += (h << 7) + *p++; /* ??? revisit */ + + hash += ((unsigned int) SYMBOL_REF << 7) + h; + return hash ? hash : (unsigned int) SYMBOL_REF; + } case PRE_DEC: case PRE_INC: @@ -643,40 +809,54 @@ hash_rtx (rtx x, enum machine_mode mode, int create) fmt = GET_RTX_FORMAT (code); for (; i >= 0; i--) { - if (fmt[i] == 'e') + switch (fmt[i]) { - rtx tem = XEXP (x, i); - unsigned int 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++) + case 'e': { - unsigned int tem_hash = hash_rtx (XVECEXP (x, i, j), 0, create); + rtx tem = XEXP (x, i); + unsigned int tem_hash = cselib_hash_rtx (tem, 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); + break; + case 'E': + for (j = 0; j < XVECLEN (x, i); j++) + { + unsigned int tem_hash + = cselib_hash_rtx (XVECEXP (x, i, j), create); + + if (tem_hash == 0) + return 0; + + hash += tem_hash; + } + break; - if (p) - while (*p) - hash += *p++; + case 's': + { + const unsigned char *p = (const unsigned char *) XSTR (x, i); + + if (p) + while (*p) + hash += *p++; + break; + } + + case 'i': + hash += XINT (x, i); + break; + + case '0': + case 't': + /* unused */ + break; + + default: + gcc_unreachable (); } - else if (fmt[i] == 'i') - hash += XINT (x, i); - else if (fmt[i] == '0' || fmt[i] == 't') - /* unused */; - else - abort (); } return hash ? hash : 1 + (unsigned int) GET_CODE (x); @@ -686,26 +866,38 @@ hash_rtx (rtx x, enum machine_mode mode, int create) value is MODE. */ static inline cselib_val * -new_cselib_val (unsigned int value, enum machine_mode mode) +new_cselib_val (unsigned int value, enum machine_mode mode, rtx x) { - cselib_val *e = pool_alloc (cselib_val_pool); + cselib_val *e = (cselib_val *) pool_alloc (cselib_val_pool); -#ifdef ENABLE_CHECKING - if (value == 0) - abort (); -#endif + gcc_assert (value); e->value = value; - /* We use custom method to allocate this RTL construct because it accounts - about 8% of overall memory usage. */ - e->u.val_rtx = pool_alloc (value_pool); - memset (e->u.val_rtx, 0, RTX_HDR_SIZE); - PUT_CODE (e->u.val_rtx, VALUE); - PUT_MODE (e->u.val_rtx, mode); - CSELIB_VAL_PTR (e->u.val_rtx) = e; + /* We use an alloc pool to allocate this RTL construct because it + accounts for about 8% of the overall memory usage. We know + precisely when we can have VALUE RTXen (when cselib is active) + so we don't need to put them in garbage collected memory. + ??? Why should a VALUE be an RTX in the first place? */ + e->val_rtx = (rtx) pool_alloc (value_pool); + memset (e->val_rtx, 0, RTX_HDR_SIZE); + PUT_CODE (e->val_rtx, VALUE); + PUT_MODE (e->val_rtx, mode); + CSELIB_VAL_PTR (e->val_rtx) = e; e->addr_list = 0; e->locs = 0; e->next_containing_mem = 0; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "cselib value %u ", value); + if (flag_dump_noaddr || flag_dump_unnumbered) + fputs ("# ", dump_file); + else + fprintf (dump_file, "%p ", (void*)e); + print_rtl_single (dump_file, x); + fputc ('\n', dump_file); + } + return e; } @@ -720,14 +912,14 @@ add_mem_for_addr (cselib_val *addr_elt, cselib_val *mem_elt, rtx x) /* Avoid duplicates. */ for (l = mem_elt->locs; l; l = l->next) - if (GET_CODE (l->loc) == MEM + if (MEM_P (l->loc) && CSELIB_VAL_PTR (XEXP (l->loc, 0)) == addr_elt) return; addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt); mem_elt->locs = new_elt_loc_list (mem_elt->locs, - replace_equiv_address_nv (x, addr_elt->u.val_rtx)); + replace_equiv_address_nv (x, addr_elt->val_rtx)); if (mem_elt->next_containing_mem == NULL) { mem_elt->next_containing_mem = first_containing_mem; @@ -748,6 +940,7 @@ cselib_lookup_mem (rtx x, int create) struct elt_list *l; if (MEM_VOLATILE_P (x) || mode == BLKmode + || !cselib_record_memory || (FLOAT_MODE_P (mode) && flag_float_store)) return 0; @@ -758,20 +951,414 @@ cselib_lookup_mem (rtx x, int create) /* 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) + if (GET_MODE (l->elt->val_rtx) == mode) return l->elt; if (! create) return 0; - mem_elt = new_cselib_val (++next_unknown_value, mode); + mem_elt = new_cselib_val (++next_unknown_value, mode, x); add_mem_for_addr (addr, mem_elt, x); - slot = htab_find_slot_with_hash (hash_table, wrap_constant (mode, x), + slot = htab_find_slot_with_hash (cselib_hash_table, wrap_constant (mode, x), mem_elt->value, INSERT); *slot = mem_elt; return mem_elt; } +/* Search thru the possible substitutions in P. We prefer a non reg + substitution because this allows us to expand the tree further. If + we find, just a reg, take the lowest regno. There may be several + non-reg results, we just take the first one because they will all + expand to the same place. */ + +static rtx +expand_loc (struct elt_loc_list *p, struct expand_value_data *evd, + int max_depth) +{ + rtx reg_result = NULL; + unsigned int regno = UINT_MAX; + struct elt_loc_list *p_in = p; + + for (; p; p = p -> next) + { + /* Avoid infinite recursion trying to expand a reg into a + the same reg. */ + if ((REG_P (p->loc)) + && (REGNO (p->loc) < regno) + && !bitmap_bit_p (evd->regs_active, REGNO (p->loc))) + { + reg_result = p->loc; + regno = REGNO (p->loc); + } + /* Avoid infinite recursion and do not try to expand the + value. */ + else if (GET_CODE (p->loc) == VALUE + && CSELIB_VAL_PTR (p->loc)->locs == p_in) + continue; + else if (!REG_P (p->loc)) + { + rtx result, note; + if (dump_file && (dump_flags & TDF_DETAILS)) + { + print_inline_rtx (dump_file, p->loc, 0); + fprintf (dump_file, "\n"); + } + if (GET_CODE (p->loc) == LO_SUM + && GET_CODE (XEXP (p->loc, 1)) == SYMBOL_REF + && p->setting_insn + && (note = find_reg_note (p->setting_insn, REG_EQUAL, NULL_RTX)) + && XEXP (note, 0) == XEXP (p->loc, 1)) + return XEXP (p->loc, 1); + result = cselib_expand_value_rtx_1 (p->loc, evd, max_depth - 1); + if (result) + return result; + } + + } + + if (regno != UINT_MAX) + { + rtx result; + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "r%d\n", regno); + + result = cselib_expand_value_rtx_1 (reg_result, evd, max_depth - 1); + if (result) + return result; + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + if (reg_result) + { + print_inline_rtx (dump_file, reg_result, 0); + fprintf (dump_file, "\n"); + } + else + fprintf (dump_file, "NULL\n"); + } + return reg_result; +} + + +/* Forward substitute and expand an expression out to its roots. + This is the opposite of common subexpression. Because local value + numbering is such a weak optimization, the expanded expression is + pretty much unique (not from a pointer equals point of view but + from a tree shape point of view. + + This function returns NULL if the expansion fails. The expansion + will fail if there is no value number for one of the operands or if + one of the operands has been overwritten between the current insn + and the beginning of the basic block. For instance x has no + expansion in: + + r1 <- r1 + 3 + x <- r1 + 8 + + REGS_ACTIVE is a scratch bitmap that should be clear when passing in. + It is clear on return. */ + +rtx +cselib_expand_value_rtx (rtx orig, bitmap regs_active, int max_depth) +{ + struct expand_value_data evd; + + evd.regs_active = regs_active; + evd.callback = NULL; + evd.callback_arg = NULL; + + return cselib_expand_value_rtx_1 (orig, &evd, max_depth); +} + +/* Same as cselib_expand_value_rtx, but using a callback to try to + resolve some expressions. The CB function should return ORIG if it + can't or does not want to deal with a certain RTX. Any other + return value, including NULL, will be used as the expansion for + VALUE, without any further changes. */ + +rtx +cselib_expand_value_rtx_cb (rtx orig, bitmap regs_active, int max_depth, + cselib_expand_callback cb, void *data) +{ + struct expand_value_data evd; + + evd.regs_active = regs_active; + evd.callback = cb; + evd.callback_arg = data; + + return cselib_expand_value_rtx_1 (orig, &evd, max_depth); +} + +/* Internal implementation of cselib_expand_value_rtx and + cselib_expand_value_rtx_cb. */ + +static rtx +cselib_expand_value_rtx_1 (rtx orig, struct expand_value_data *evd, + int max_depth) +{ + rtx copy, scopy; + int i, j; + RTX_CODE code; + const char *format_ptr; + enum machine_mode mode; + + code = GET_CODE (orig); + + /* For the context of dse, if we end up expand into a huge tree, we + will not have a useful address, so we might as well just give up + quickly. */ + if (max_depth <= 0) + return NULL; + + switch (code) + { + case REG: + { + struct elt_list *l = REG_VALUES (REGNO (orig)); + + if (l && l->elt == NULL) + l = l->next; + for (; l; l = l->next) + if (GET_MODE (l->elt->val_rtx) == GET_MODE (orig)) + { + rtx result; + int regno = REGNO (orig); + + /* The only thing that we are not willing to do (this + is requirement of dse and if others potential uses + need this function we should add a parm to control + it) is that we will not substitute the + STACK_POINTER_REGNUM, FRAME_POINTER or the + HARD_FRAME_POINTER. + + These expansions confuses the code that notices that + stores into the frame go dead at the end of the + function and that the frame is not effected by calls + to subroutines. If you allow the + STACK_POINTER_REGNUM substitution, then dse will + think that parameter pushing also goes dead which is + wrong. If you allow the FRAME_POINTER or the + HARD_FRAME_POINTER then you lose the opportunity to + make the frame assumptions. */ + if (regno == STACK_POINTER_REGNUM + || regno == FRAME_POINTER_REGNUM + || regno == HARD_FRAME_POINTER_REGNUM) + return orig; + + bitmap_set_bit (evd->regs_active, regno); + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "expanding: r%d into: ", regno); + + result = expand_loc (l->elt->locs, evd, max_depth); + bitmap_clear_bit (evd->regs_active, regno); + + if (result) + return result; + else + return orig; + } + } + + case CONST_INT: + case CONST_DOUBLE: + case CONST_VECTOR: + case SYMBOL_REF: + case CODE_LABEL: + case PC: + case CC0: + case SCRATCH: + /* SCRATCH must be shared because they represent distinct values. */ + return orig; + case CLOBBER: + if (REG_P (XEXP (orig, 0)) && HARD_REGISTER_NUM_P (REGNO (XEXP (orig, 0)))) + return orig; + break; + + case CONST: + if (shared_const_p (orig)) + return orig; + break; + + case SUBREG: + { + rtx subreg; + + if (evd->callback) + { + subreg = evd->callback (orig, evd->regs_active, max_depth, + evd->callback_arg); + if (subreg != orig) + return subreg; + } + + subreg = cselib_expand_value_rtx_1 (SUBREG_REG (orig), evd, + max_depth - 1); + if (!subreg) + return NULL; + scopy = simplify_gen_subreg (GET_MODE (orig), subreg, + GET_MODE (SUBREG_REG (orig)), + SUBREG_BYTE (orig)); + if (scopy == NULL + || (GET_CODE (scopy) == SUBREG + && !REG_P (SUBREG_REG (scopy)) + && !MEM_P (SUBREG_REG (scopy)))) + return NULL; + + return scopy; + } + + case VALUE: + { + rtx result; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fputs ("\nexpanding ", dump_file); + print_rtl_single (dump_file, orig); + fputs (" into...", dump_file); + } + + if (evd->callback) + { + result = evd->callback (orig, evd->regs_active, max_depth, + evd->callback_arg); + + if (result != orig) + return result; + } + + result = expand_loc (CSELIB_VAL_PTR (orig)->locs, evd, max_depth); + return result; + } + + case DEBUG_EXPR: + if (evd->callback) + return evd->callback (orig, evd->regs_active, max_depth, + evd->callback_arg); + return orig; + + default: + break; + } + + /* Copy the various flags, fields, and other information. We assume + that all fields need copying, and then clear the fields that should + not be copied. That is the sensible default behavior, and forces + us to explicitly document why we are *not* copying a flag. */ + copy = shallow_copy_rtx (orig); + + format_ptr = GET_RTX_FORMAT (code); + + for (i = 0; i < GET_RTX_LENGTH (code); i++) + switch (*format_ptr++) + { + case 'e': + if (XEXP (orig, i) != NULL) + { + rtx result = cselib_expand_value_rtx_1 (XEXP (orig, i), evd, + max_depth - 1); + if (!result) + return NULL; + XEXP (copy, i) = result; + } + break; + + case 'E': + case 'V': + if (XVEC (orig, i) != NULL) + { + XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i)); + for (j = 0; j < XVECLEN (copy, i); j++) + { + rtx result = cselib_expand_value_rtx_1 (XVECEXP (orig, i, j), + evd, max_depth - 1); + if (!result) + return NULL; + XVECEXP (copy, i, j) = result; + } + } + break; + + case 't': + case 'w': + case 'i': + case 's': + case 'S': + case 'T': + case 'u': + case 'B': + case '0': + /* These are left unchanged. */ + break; + + default: + gcc_unreachable (); + } + + mode = GET_MODE (copy); + /* If an operand has been simplified into CONST_INT, which doesn't + have a mode and the mode isn't derivable from whole rtx's mode, + try simplify_*_operation first with mode from original's operand + and as a fallback wrap CONST_INT into gen_rtx_CONST. */ + scopy = copy; + switch (GET_RTX_CLASS (code)) + { + case RTX_UNARY: + if (CONST_INT_P (XEXP (copy, 0)) + && GET_MODE (XEXP (orig, 0)) != VOIDmode) + { + scopy = simplify_unary_operation (code, mode, XEXP (copy, 0), + GET_MODE (XEXP (orig, 0))); + if (scopy) + return scopy; + } + break; + case RTX_COMM_ARITH: + case RTX_BIN_ARITH: + /* These expressions can derive operand modes from the whole rtx's mode. */ + break; + case RTX_TERNARY: + case RTX_BITFIELD_OPS: + if (CONST_INT_P (XEXP (copy, 0)) + && GET_MODE (XEXP (orig, 0)) != VOIDmode) + { + scopy = simplify_ternary_operation (code, mode, + GET_MODE (XEXP (orig, 0)), + XEXP (copy, 0), XEXP (copy, 1), + XEXP (copy, 2)); + if (scopy) + return scopy; + } + break; + case RTX_COMPARE: + case RTX_COMM_COMPARE: + if (CONST_INT_P (XEXP (copy, 0)) + && GET_MODE (XEXP (copy, 1)) == VOIDmode + && (GET_MODE (XEXP (orig, 0)) != VOIDmode + || GET_MODE (XEXP (orig, 1)) != VOIDmode)) + { + scopy = simplify_relational_operation (code, mode, + (GET_MODE (XEXP (orig, 0)) + != VOIDmode) + ? GET_MODE (XEXP (orig, 0)) + : GET_MODE (XEXP (orig, 1)), + XEXP (copy, 0), + XEXP (copy, 1)); + if (scopy) + return scopy; + } + break; + default: + break; + } + scopy = simplify_rtx (copy); + if (scopy) + return scopy; + return copy; +} + /* 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. @@ -795,10 +1382,10 @@ cselib_subst_to_values (rtx x) if (l && l->elt == NULL) l = l->next; for (; l; l = l->next) - if (GET_MODE (l->elt->u.val_rtx) == GET_MODE (x)) - return l->elt->u.val_rtx; + if (GET_MODE (l->elt->val_rtx) == GET_MODE (x)) + return l->elt->val_rtx; - abort (); + gcc_unreachable (); case MEM: e = cselib_lookup_mem (x, 0); @@ -806,13 +1393,14 @@ cselib_subst_to_values (rtx x) { /* This happens for autoincrements. Assign a value that doesn't match any other. */ - e = new_cselib_val (++next_unknown_value, GET_MODE (x)); + e = new_cselib_val (++next_unknown_value, GET_MODE (x), x); } - return e->u.val_rtx; + return e->val_rtx; case CONST_DOUBLE: case CONST_VECTOR: case CONST_INT: + case CONST_FIXED: return x; case POST_INC: @@ -821,8 +1409,8 @@ cselib_subst_to_values (rtx x) case PRE_DEC: case POST_MODIFY: case PRE_MODIFY: - e = new_cselib_val (++next_unknown_value, GET_MODE (x)); - return e->u.val_rtx; + e = new_cselib_val (++next_unknown_value, GET_MODE (x), x); + return e->val_rtx; default: break; @@ -834,30 +1422,31 @@ cselib_subst_to_values (rtx x) { 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; + if (t != XEXP (x, i)) + { + if (x == copy) + copy = shallow_copy_rtx (x); + XEXP (copy, i) = t; + } } else if (fmt[i] == 'E') { - int j, k; + int j; 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 (t != XVECEXP (x, i, j)) { - 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); + if (XVEC (x, i) == XVEC (copy, i)) + { + if (x == copy) + copy = shallow_copy_rtx (x); + XVEC (copy, i) = shallow_copy_rtvec (XVEC (x, i)); + } + XVECEXP (copy, i, j) = t; } - - XVECEXP (copy, i, j) = t; } } } @@ -865,6 +1454,21 @@ cselib_subst_to_values (rtx x) return copy; } +/* Log a lookup of X to the cselib table along with the result RET. */ + +static cselib_val * +cselib_log_lookup (rtx x, cselib_val *ret) +{ + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fputs ("cselib lookup ", dump_file); + print_inline_rtx (dump_file, x, 2); + fprintf (dump_file, " => %u\n", ret ? ret->value : 0); + } + + return ret; +} + /* 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 @@ -883,7 +1487,7 @@ cselib_lookup (rtx x, enum machine_mode mode, int create) if (GET_CODE (x) == VALUE) return CSELIB_VAL_PTR (x); - if (GET_CODE (x) == REG) + if (REG_P (x)) { struct elt_list *l; unsigned int i = REGNO (x); @@ -892,11 +1496,11 @@ cselib_lookup (rtx x, enum machine_mode mode, int create) if (l && l->elt == NULL) l = l->next; for (; l; l = l->next) - if (mode == GET_MODE (l->elt->u.val_rtx)) - return l->elt; + if (mode == GET_MODE (l->elt->val_rtx)) + return cselib_log_lookup (x, l->elt); if (! create) - return 0; + return cselib_log_lookup (x, 0); if (i < FIRST_PSEUDO_REGISTER) { @@ -906,7 +1510,7 @@ cselib_lookup (rtx x, enum machine_mode mode, int create) max_value_regs = n; } - e = new_cselib_val (++next_unknown_value, GET_MODE (x)); + e = new_cselib_val (++next_unknown_value, GET_MODE (x), x); e->locs = new_elt_loc_list (e->locs, x); if (REG_VALUES (i) == 0) { @@ -917,36 +1521,36 @@ cselib_lookup (rtx x, enum machine_mode mode, int create) REG_VALUES (i) = new_elt_list (REG_VALUES (i), NULL); } REG_VALUES (i)->next = new_elt_list (REG_VALUES (i)->next, e); - slot = htab_find_slot_with_hash (hash_table, x, e->value, INSERT); + slot = htab_find_slot_with_hash (cselib_hash_table, x, e->value, INSERT); *slot = e; - return e; + return cselib_log_lookup (x, e); } - if (GET_CODE (x) == MEM) - return cselib_lookup_mem (x, create); + if (MEM_P (x)) + return cselib_log_lookup (x, cselib_lookup_mem (x, create)); - hashval = hash_rtx (x, mode, create); + hashval = cselib_hash_rtx (x, create); /* Can't even create if hashing is not possible. */ if (! hashval) - return 0; + return cselib_log_lookup (x, 0); - slot = htab_find_slot_with_hash (hash_table, wrap_constant (mode, x), + slot = htab_find_slot_with_hash (cselib_hash_table, wrap_constant (mode, x), hashval, create ? INSERT : NO_INSERT); if (slot == 0) - return 0; + return cselib_log_lookup (x, 0); e = (cselib_val *) *slot; if (e) - return e; + return cselib_log_lookup (x, e); - e = new_cselib_val (hashval, mode); + e = new_cselib_val (hashval, mode, x); /* 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; + return cselib_log_lookup (x, e); } /* Invalidate any entries in reg_values that overlap REGNO. This is called @@ -962,9 +1566,8 @@ cselib_invalidate_regno (unsigned int regno, enum machine_mode mode) unsigned int i; /* If we see pseudos after reload, something is _wrong_. */ - if (reload_completed && regno >= FIRST_PSEUDO_REGISTER - && reg_renumber[regno] >= 0) - abort (); + gcc_assert (!reload_completed || regno < FIRST_PSEUDO_REGISTER + || reg_renumber[regno] < 0); /* Determine the range of registers that must be invalidated. For pseudos, only REGNO is affected. For hard regs, we must take MODE @@ -972,15 +1575,14 @@ cselib_invalidate_regno (unsigned int regno, enum machine_mode mode) if they contain values that overlap REGNO. */ if (regno < FIRST_PSEUDO_REGISTER) { - if (mode == VOIDmode) - abort (); + gcc_assert (mode != VOIDmode); if (regno < max_value_regs) i = 0; else i = regno - max_value_regs; - endregno = regno + hard_regno_nregs[regno][mode]; + endregno = end_hard_regno (mode, regno); } else { @@ -1001,7 +1603,7 @@ cselib_invalidate_regno (unsigned int regno, enum machine_mode mode) unsigned int this_last = i; if (i < FIRST_PSEUDO_REGISTER && v != NULL) - this_last += hard_regno_nregs[i][GET_MODE (v->u.val_rtx)] - 1; + this_last = end_hard_regno (GET_MODE (v->val_rtx), i) - 1; if (this_last < regno || v == NULL) { @@ -1029,13 +1631,13 @@ cselib_invalidate_regno (unsigned int regno, enum machine_mode mode) { rtx x = (*p)->loc; - if (GET_CODE (x) == REG && REGNO (x) == i) + if (REG_P (x) && REGNO (x) == i) { unchain_one_elt_loc_list (p); break; } } - if (v->locs == 0) + if (v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx)) n_useless_values++; } } @@ -1045,8 +1647,8 @@ cselib_invalidate_regno (unsigned int regno, enum machine_mode mode) executions of the program. 0 means X can be compared reliably against certain constants or near-constants. */ -static int -cselib_rtx_varies_p (rtx x ATTRIBUTE_UNUSED, int from_alias ATTRIBUTE_UNUSED) +static bool +cselib_rtx_varies_p (const_rtx x ATTRIBUTE_UNUSED, bool from_alias ATTRIBUTE_UNUSED) { /* We actually don't need to verify very hard. This is because if X has actually changed, we invalidate the memory anyway, @@ -1079,22 +1681,19 @@ cselib_invalidate_mem (rtx mem_rtx) while (*p) { rtx x = (*p)->loc; - rtx canon_x = (*p)->canon_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) + if (!MEM_P (x)) { p = &(*p)->next; continue; } - if (!canon_x) - canon_x = (*p)->canon_loc = canon_rtx (x); if (num_mems < PARAM_VALUE (PARAM_MAX_CSELIB_MEMORY_LOCATIONS) && ! canon_true_dependence (mem_rtx, GET_MODE (mem_rtx), mem_addr, - x, cselib_rtx_varies_p)) + x, NULL_RTX, cselib_rtx_varies_p)) { has_mem = true; num_mems++; @@ -1121,7 +1720,7 @@ cselib_invalidate_mem (rtx mem_rtx) unchain_one_elt_loc_list (p); } - if (had_locs && v->locs == 0) + if (had_locs && v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx)) n_useless_values++; next = v->next_containing_mem; @@ -1136,21 +1735,19 @@ cselib_invalidate_mem (rtx mem_rtx) *vp = &dummy_val; } -/* 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. */ +/* Invalidate DEST, which is being assigned to or clobbered. */ -static void -cselib_invalidate_rtx (rtx dest, rtx ignore ATTRIBUTE_UNUSED, - void *data ATTRIBUTE_UNUSED) +void +cselib_invalidate_rtx (rtx dest) { - while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SIGN_EXTRACT - || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG) + while (GET_CODE (dest) == SUBREG + || GET_CODE (dest) == ZERO_EXTRACT + || GET_CODE (dest) == STRICT_LOW_PART) dest = XEXP (dest, 0); - if (GET_CODE (dest) == REG) + if (REG_P (dest)) cselib_invalidate_regno (REGNO (dest), GET_MODE (dest)); - else if (GET_CODE (dest) == MEM) + else if (MEM_P (dest)) cselib_invalidate_mem (dest); /* Some machines don't define AUTO_INC_DEC, but they still use push @@ -1158,7 +1755,16 @@ cselib_invalidate_rtx (rtx dest, rtx ignore ATTRIBUTE_UNUSED, 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); + cselib_invalidate_rtx (stack_pointer_rtx); +} + +/* A wrapper for cselib_invalidate_rtx to be called via note_stores. */ + +static void +cselib_invalidate_rtx_note_stores (rtx dest, const_rtx ignore ATTRIBUTE_UNUSED, + void *data ATTRIBUTE_UNUSED) +{ + cselib_invalidate_rtx (dest); } /* Record the result of a SET instruction. DEST is being set; the source @@ -1168,7 +1774,7 @@ cselib_invalidate_rtx (rtx dest, rtx ignore ATTRIBUTE_UNUSED, static void cselib_record_set (rtx dest, cselib_val *src_elt, cselib_val *dest_addr_elt) { - int dreg = GET_CODE (dest) == REG ? (int) REGNO (dest) : -1; + int dreg = REG_P (dest) ? (int) REGNO (dest) : -1; if (src_elt == 0 || side_effects_p (dest)) return; @@ -1190,34 +1796,24 @@ cselib_record_set (rtx dest, cselib_val *src_elt, cselib_val *dest_addr_elt) } else { - if (REG_VALUES (dreg)->elt == 0) - REG_VALUES (dreg)->elt = src_elt; - else - /* The register should have been invalidated. */ - abort (); + /* The register should have been invalidated. */ + gcc_assert (REG_VALUES (dreg)->elt == 0); + REG_VALUES (dreg)->elt = src_elt; } - if (src_elt->locs == 0) + if (src_elt->locs == 0 && !PRESERVED_VALUE_P (src_elt->val_rtx)) n_useless_values--; src_elt->locs = new_elt_loc_list (src_elt->locs, dest); } - else if (GET_CODE (dest) == MEM && dest_addr_elt != 0) + else if (MEM_P (dest) && dest_addr_elt != 0 + && cselib_record_memory) { - if (src_elt->locs == 0) + if (src_elt->locs == 0 && !PRESERVED_VALUE_P (src_elt->val_rtx)) 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) @@ -1228,7 +1824,7 @@ cselib_record_sets (rtx insn) { int n_sets = 0; int i; - struct set sets[MAX_SETS]; + struct cselib_set sets[MAX_SETS]; rtx body = PATTERN (insn); rtx cond = 0; @@ -1263,6 +1859,17 @@ cselib_record_sets (rtx insn) } } + if (n_sets == 1 + && MEM_P (sets[0].src) + && !cselib_record_memory + && MEM_READONLY_P (sets[0].src)) + { + rtx note = find_reg_equal_equiv_note (insn); + + if (note && CONSTANT_P (XEXP (note, 0))) + sets[0].src = XEXP (note, 0); + } + /* Look up the values that are read. Do this before invalidating the locations that are written. */ for (i = 0; i < n_sets; i++) @@ -1275,23 +1882,33 @@ cselib_record_sets (rtx insn) 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) + if (REG_P (dest) + || (MEM_P (dest) && cselib_record_memory)) { rtx src = sets[i].src; if (cond) - src = gen_rtx_IF_THEN_ELSE (GET_MODE (src), cond, src, dest); + src = gen_rtx_IF_THEN_ELSE (GET_MODE (dest), cond, src, dest); sets[i].src_elt = cselib_lookup (src, GET_MODE (dest), 1); - if (GET_CODE (dest) == MEM) - sets[i].dest_addr_elt = cselib_lookup (XEXP (dest, 0), Pmode, 1); + if (MEM_P (dest)) + { + enum machine_mode address_mode + = targetm.addr_space.address_mode (MEM_ADDR_SPACE (dest)); + + sets[i].dest_addr_elt = cselib_lookup (XEXP (dest, 0), + address_mode, 1); + } else sets[i].dest_addr_elt = 0; } } + if (cselib_record_sets_hook) + cselib_record_sets_hook (insn, sets, n_sets); + /* 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); + note_stores (body, cselib_invalidate_rtx_note_stores, NULL); /* If this is an asm, look for duplicate sets. This can happen when the user uses the same value as an output multiple times. This is valid @@ -1303,7 +1920,7 @@ cselib_record_sets (rtx insn) for (i = 0; i < n_sets; i++) { rtx dest = sets[i].dest; - if (GET_CODE (dest) == REG || GET_CODE (dest) == MEM) + if (REG_P (dest) || MEM_P (dest)) { int j; for (j = i + 1; j < n_sets; j++) @@ -1320,7 +1937,8 @@ cselib_record_sets (rtx insn) for (i = 0; i < n_sets; i++) { rtx dest = sets[i].dest; - if (GET_CODE (dest) == REG || GET_CODE (dest) == MEM) + if (REG_P (dest) + || (MEM_P (dest) && cselib_record_memory)) cselib_record_set (dest, sets[i].src_elt, sets[i].dest_addr_elt); } } @@ -1333,21 +1951,17 @@ cselib_process_insn (rtx insn) int i; rtx x; - if (find_reg_note (insn, REG_LIBCALL, NULL)) - cselib_current_insn_in_libcall = true; - if (find_reg_note (insn, REG_RETVAL, NULL)) - cselib_current_insn_in_libcall = false; 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) == CALL_INSN + if (LABEL_P (insn) + || (CALL_P (insn) && find_reg_note (insn, REG_SETJMP, NULL)) - || (GET_CODE (insn) == INSN + || (NONJUMP_INSN_P (insn) && GET_CODE (PATTERN (insn)) == ASM_OPERANDS && MEM_VOLATILE_P (PATTERN (insn)))) { - clear_table (); + cselib_reset_table_with_next_value (next_unknown_value); return; } @@ -1360,13 +1974,20 @@ cselib_process_insn (rtx insn) /* 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) + if (CALL_P (insn)) { for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) - if (call_used_regs[i]) + if (call_used_regs[i] + || (REG_VALUES (i) && REG_VALUES (i)->elt + && HARD_REGNO_CALL_PART_CLOBBERED (i, + GET_MODE (REG_VALUES (i)->elt->val_rtx)))) cselib_invalidate_regno (i, reg_raw_mode[i]); - if (! CONST_OR_PURE_CALL_P (insn)) + /* Since it is not clear how cselib is going to be used, be + conservative here and treat looping pure or const functions + as if they were regular functions. */ + if (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn) + || !(RTL_CONST_OR_PURE_CALL_P (insn))) cselib_invalidate_mem (callmem); } @@ -1378,19 +1999,23 @@ cselib_process_insn (rtx insn) 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); + cselib_invalidate_rtx (XEXP (x, 0)); #endif /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only after we have processed the insn. */ - if (GET_CODE (insn) == CALL_INSN) + if (CALL_P (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_invalidate_rtx (XEXP (XEXP (x, 0), 0)); cselib_current_insn = 0; - if (n_useless_values > MAX_USELESS_VALUES) + if (n_useless_values > MAX_USELESS_VALUES + /* remove_useless_values is linear in the hash table size. Avoid + quadratic behavior for very large hashtables with very few + useless elements. */ + && (unsigned int)n_useless_values > cselib_hash_table->n_elements / 4) remove_useless_values (); } @@ -1398,19 +2023,21 @@ cselib_process_insn (rtx insn) init_alias_analysis. */ void -cselib_init (void) +cselib_init (bool record_memory) { - elt_list_pool = create_alloc_pool ("elt_list", + elt_list_pool = create_alloc_pool ("elt_list", sizeof (struct elt_list), 10); - elt_loc_list_pool = create_alloc_pool ("elt_loc_list", + elt_loc_list_pool = create_alloc_pool ("elt_loc_list", sizeof (struct elt_loc_list), 10); - cselib_val_pool = create_alloc_pool ("cselib_val_list", + cselib_val_pool = create_alloc_pool ("cselib_val_list", sizeof (cselib_val), 10); - value_pool = create_alloc_pool ("value", - RTX_SIZE (VALUE), 100); - /* This is only created once. */ + value_pool = create_alloc_pool ("value", RTX_CODE_SIZE (VALUE), 100); + cselib_record_memory = record_memory; + + /* (mem:BLK (scratch)) is a special mechanism to conflict with everything, + see canon_true_dependence. This is only created once. */ if (! callmem) - callmem = gen_rtx_MEM (BLKmode, const0_rtx); + callmem = gen_rtx_MEM (BLKmode, gen_rtx_SCRATCH (VOIDmode)); cselib_nregs = max_reg_num (); @@ -1424,12 +2051,12 @@ cselib_init (void) /* Some space for newly emit instructions so we don't end up reallocating in between passes. */ reg_values_size = cselib_nregs + (63 + cselib_nregs) / 16; - reg_values = xcalloc (reg_values_size, sizeof (reg_values)); + reg_values = XCNEWVEC (struct elt_list *, reg_values_size); } - used_regs = xmalloc (sizeof (*used_regs) * cselib_nregs); + used_regs = XNEWVEC (unsigned int, cselib_nregs); n_used_regs = 0; - hash_table = htab_create (31, get_value_hash, entry_and_rtx_equal_p, NULL); - cselib_current_insn_in_libcall = false; + cselib_hash_table = htab_create (31, get_value_hash, + entry_and_rtx_equal_p, NULL); } /* Called when the current user is done with cselib. */ @@ -1437,17 +2064,106 @@ cselib_init (void) void cselib_finish (void) { + cselib_discard_hook = NULL; free_alloc_pool (elt_list_pool); free_alloc_pool (elt_loc_list_pool); free_alloc_pool (cselib_val_pool); free_alloc_pool (value_pool); - clear_table (); - htab_delete (hash_table); + cselib_clear_table (); + htab_delete (cselib_hash_table); free (used_regs); used_regs = 0; - hash_table = 0; + cselib_hash_table = 0; n_useless_values = 0; next_unknown_value = 0; } +/* Dump the cselib_val *X to FILE *info. */ + +static int +dump_cselib_val (void **x, void *info) +{ + cselib_val *v = (cselib_val *)*x; + FILE *out = (FILE *)info; + bool need_lf = true; + + print_inline_rtx (out, v->val_rtx, 0); + + if (v->locs) + { + struct elt_loc_list *l = v->locs; + if (need_lf) + { + fputc ('\n', out); + need_lf = false; + } + fputs (" locs:", out); + do + { + fprintf (out, "\n from insn %i ", + INSN_UID (l->setting_insn)); + print_inline_rtx (out, l->loc, 4); + } + while ((l = l->next)); + fputc ('\n', out); + } + else + { + fputs (" no locs", out); + need_lf = true; + } + + if (v->addr_list) + { + struct elt_list *e = v->addr_list; + if (need_lf) + { + fputc ('\n', out); + need_lf = false; + } + fputs (" addr list:", out); + do + { + fputs ("\n ", out); + print_inline_rtx (out, e->elt->val_rtx, 2); + } + while ((e = e->next)); + fputc ('\n', out); + } + else + { + fputs (" no addrs", out); + need_lf = true; + } + + if (v->next_containing_mem == &dummy_val) + fputs (" last mem\n", out); + else if (v->next_containing_mem) + { + fputs (" next mem ", out); + print_inline_rtx (out, v->next_containing_mem->val_rtx, 2); + fputc ('\n', out); + } + else if (need_lf) + fputc ('\n', out); + + return 1; +} + +/* Dump to OUT everything in the CSELIB table. */ + +void +dump_cselib_table (FILE *out) +{ + fprintf (out, "cselib hash table:\n"); + htab_traverse (cselib_hash_table, dump_cselib_val, out); + if (first_containing_mem != &dummy_val) + { + fputs ("first mem ", out); + print_inline_rtx (out, first_containing_mem->val_rtx, 2); + fputc ('\n', out); + } + fprintf (out, "last unknown value %i\n", next_unknown_value); +} + #include "gt-cselib.h"