/* 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 Free Software Foundation, Inc.
This file is part of GCC.
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. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
#include "config.h"
#include "system.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 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 cselib_hash_rtx (rtx, enum machine_mode, int);
+static unsigned int cselib_hash_rtx (rtx, int);
static cselib_val *new_cselib_val (unsigned int, enum machine_mode);
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);
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. */
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;
initialization. If CLEAR_ALL isn't set, then only clear the entries
which are known to have been used. */
-static void
-clear_table (void)
+void
+cselib_clear_table (void)
{
unsigned int i;
n_used_regs = 0;
- htab_empty (hash_table);
+ htab_empty (cselib_hash_table);
n_useless_values = 0;
if (v->locs == 0)
{
CSELIB_VAL_PTR (v->u.val_rtx) = NULL;
- htab_clear_slot (hash_table, x);
+ htab_clear_slot (cselib_hash_table, x);
unchain_one_value (v);
n_useless_values--;
}
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);
}
*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);
}
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:
+ return 0;
+
+ case LABEL_REF:
+ return XEXP (x, 0) == XEXP (y, 0);
+
+ default:
+ break;
+ }
code = GET_CODE (x);
fmt = GET_RTX_FORMAT (code);
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;
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
-cselib_hash_rtx (rtx x, enum machine_mode mode, int create)
+cselib_hash_rtx (rtx x, int create)
{
cselib_val *e;
int i, j;
return e->value;
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:
for (i = 0; i < units; ++i)
{
elt = CONST_VECTOR_ELT (x, i);
- hash += cselib_hash_rtx (elt, GET_MODE (elt), 0);
+ hash += cselib_hash_rtx (elt, 0);
}
return hash;
case 'e':
{
rtx tem = XEXP (x, i);
- unsigned int tem_hash = cselib_hash_rtx (tem, 0, create);
+ unsigned int tem_hash = cselib_hash_rtx (tem, create);
if (tem_hash == 0)
return 0;
for (j = 0; j < XVECLEN (x, i); j++)
{
unsigned int tem_hash
- = cselib_hash_rtx (XVECEXP (x, i, j), 0, create);
+ = cselib_hash_rtx (XVECEXP (x, i, j), create);
if (tem_hash == 0)
return 0;
gcc_assert (value);
e->value = value;
- /* We use custom method to allocate this RTL construct because it accounts
- about 8% of overall memory usage. */
+ /* 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->u.val_rtx = pool_alloc (value_pool);
memset (e->u.val_rtx, 0, RTX_HDR_SIZE);
PUT_CODE (e->u.val_rtx, VALUE);
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),
+ slot = htab_find_slot_with_hash (cselib_hash_table, wrap_constant (mode, x),
mem_elt->value, INSERT);
*slot = mem_elt;
return mem_elt;
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;
}
if (MEM_P (x))
return cselib_lookup_mem (x, create);
- hashval = cselib_hash_rtx (x, mode, create);
+ hashval = cselib_hash_rtx (x, 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),
+ slot = htab_find_slot_with_hash (cselib_hash_table, wrap_constant (mode, x),
hashval, create ? INSERT : NO_INSERT);
if (slot == 0)
return 0;
*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 (REG_P (dest))
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, 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
/* 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
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. */
&& GET_CODE (PATTERN (insn)) == ASM_OPERANDS
&& MEM_VOLATILE_P (PATTERN (insn))))
{
- clear_table ();
+ if (find_reg_note (insn, REG_RETVAL, NULL))
+ cselib_current_insn_in_libcall = false;
+ cselib_clear_table ();
return;
}
if (! INSN_P (insn))
{
+ if (find_reg_note (insn, REG_RETVAL, NULL))
+ cselib_current_insn_in_libcall = false;
cselib_current_insn = 0;
return;
}
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->u.val_rtx))))
cselib_invalidate_regno (i, reg_raw_mode[i]);
if (! CONST_OR_PURE_CALL_P (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
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));
+ if (find_reg_note (insn, REG_RETVAL, NULL))
+ cselib_current_insn_in_libcall = false;
cselib_current_insn = 0;
if (n_useless_values > MAX_USELESS_VALUES)
sizeof (struct elt_loc_list), 10);
cselib_val_pool = create_alloc_pool ("cselib_val_list",
sizeof (cselib_val), 10);
- value_pool = create_alloc_pool ("value",
- RTX_SIZE (VALUE), 100);
+ value_pool = create_alloc_pool ("value", RTX_CODE_SIZE (VALUE), 100);
cselib_record_memory = record_memory;
/* This is only created once. */
if (! callmem)
/* 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_hash_table = htab_create (31, get_value_hash,
+ entry_and_rtx_equal_p, NULL);
cselib_current_insn_in_libcall = false;
}
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;
}