/* Common subexpression elimination library for GNU compiler.
Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
- 1999, 2000, 2001 Free Software Foundation, Inc.
+ 1999, 2000, 2001, 2003 Free Software Foundation, Inc.
This file is part of GCC.
#include "config.h"
#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
#include "rtl.h"
#include "tm_p.h"
#include "cselib.h"
static int entry_and_rtx_equal_p PARAMS ((const void *, const void *));
-static unsigned int get_value_hash PARAMS ((const void *));
+static hashval_t 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 *,
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 void clear_table PARAMS ((void));
static int discard_useless_locs PARAMS ((void **, void *));
static int discard_useless_values PARAMS ((void **, void *));
static void remove_useless_values PARAMS ((void));
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 *,
/* 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;
/* 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. */
+/* 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. The first element of the list defines the mode in
+ 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. */
static GTY(()) varray_type reg_values;
static GTY((deletable (""))) varray_type reg_values_old;
#define REG_VALUES(I) VARRAY_ELT_LIST (reg_values, (I))
/* Set by discard_useless_locs if it deleted the last location of any
value. */
static int values_became_useless;
+
+/* Used as stop element of the containing_mem list so we can check
+ presence in the list by checking the next pointer. */
+static cselib_val dummy_val;
+
+/* Used to list all values that contain memory reference.
+ May or may not contain the useless values - the list is compacted
+ each time memory is invalidated. */
+static cselib_val *first_containing_mem = &dummy_val;
\f
/* Allocate a struct elt_list and fill in its two elements with the
el->next = next;
el->loc = loc;
el->setting_insn = cselib_current_insn;
+ el->in_libcall = cselib_current_insn_in_libcall;
return el;
}
which are known to have been used. */
static void
-clear_table (clear_all)
- int clear_all;
+clear_table ()
{
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;
+ for (i = 0; i < VARRAY_ACTIVE_SIZE (used_regs); i++)
+ REG_VALUES (VARRAY_UINT (used_regs, i)) = 0;
max_value_regs = 0;
n_useless_values = 0;
next_unknown_value = 0;
+
+ first_containing_mem = &dummy_val;
}
/* The equality test for our hash table. The first argument ENTRY is a table
hash_rtx when adding an element; this function just extracts the hash
value from a cselib_val structure. */
-static unsigned int
+static hashval_t
get_value_hash (entry)
const void *entry;
{
static void
remove_useless_values ()
{
+ cselib_val **p, *v;
/* First pass: eliminate locations that reference the value. That in
turn can make more values useless. */
do
/* Second pass: actually remove the values. */
htab_traverse (hash_table, discard_useless_values, 0);
+ p = &first_containing_mem;
+ for (v = *p; v != &dummy_val; v = v->next_containing_mem)
+ if (v->locs)
+ {
+ *p = v;
+ p = &(*p)->next_containing_mem;
+ }
+ *p = &dummy_val;
+
if (n_useless_values != 0)
abort ();
}
+/* Return the mode in which a register was last set. If X is not a
+ register, return its mode. If the mode in which the register was
+ set is not known, or the value was already clobbered, return
+ VOIDmode. */
+
+enum machine_mode
+cselib_reg_set_mode (x)
+ rtx x;
+{
+ if (GET_CODE (x) != REG)
+ 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 nonzero if we can prove that X and Y contain the same value, taking
our gathered information into account. */
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);
+ hash += real_hash (CONST_DOUBLE_REAL_VALUE (x));
else
hash += ((unsigned) CONST_DOUBLE_LOW (x)
+ (unsigned) CONST_DOUBLE_HIGH (x));
CSELIB_VAL_PTR (e->u.val_rtx) = e;
e->addr_list = 0;
e->locs = 0;
+ e->next_containing_mem = 0;
return e;
}
mem_elt->locs
= new_elt_loc_list (mem_elt->locs,
replace_equiv_address_nv (x, addr_elt->u.val_rtx));
+ if (mem_elt->next_containing_mem == NULL)
+ {
+ mem_elt->next_containing_mem = first_containing_mem;
+ first_containing_mem = mem_elt;
+ }
}
/* Subroutine of cselib_lookup. Return a value for X, which is a MEM rtx.
switch (code)
{
case REG:
- for (l = REG_VALUES (REGNO (x)); l; l = l->next)
+ l = REG_VALUES (REGNO (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;
struct elt_list *l;
unsigned int i = REGNO (x);
- for (l = REG_VALUES (i); l; l = l->next)
+ l = REG_VALUES (i);
+ 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;
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);
+ {
+ /* Maintain the invariant that the first entry of
+ REG_VALUES, if present, must be the value used to set the
+ register, or NULL. */
+ VARRAY_PUSH_UINT (used_regs, i);
+ 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 = e;
return e;
struct elt_loc_list **p;
unsigned int this_last = i;
- if (i < FIRST_PSEUDO_REGISTER)
+ if (i < FIRST_PSEUDO_REGISTER && v != NULL)
this_last += HARD_REGNO_NREGS (i, GET_MODE (v->u.val_rtx)) - 1;
- if (this_last < regno)
+ if (this_last < regno || v == NULL)
{
l = &(*l)->next;
continue;
}
/* We have an overlap. */
- unchain_one_elt_list (l);
+ if (*l == REG_VALUES (i))
+ {
+ /* Maintain the invariant that the first entry of
+ REG_VALUES, if present, must be the value used to set
+ the register, or NULL. This is also nice because
+ then we won't push the same regno onto user_regs
+ multiple times. */
+ (*l)->elt = NULL;
+ l = &(*l)->next;
+ }
+ else
+ 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. */
return 0;
}
-/* For the value found in SLOT, walk its locations to determine if any overlap
- INFO (which is a MEM rtx). */
+/* 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 int
-cselib_invalidate_mem_1 (slot, info)
- void **slot;
- void *info;
+static void
+cselib_invalidate_mem (mem_rtx)
+ rtx mem_rtx;
{
- cselib_val *v = (cselib_val *) *slot;
- rtx mem_rtx = (rtx) info;
- struct elt_loc_list **p = &v->locs;
- int had_locs = v->locs != 0;
+ cselib_val **vp, *v, *next;
- while (*p)
+ vp = &first_containing_mem;
+ for (v = *vp; v != &dummy_val; v = next)
{
- 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;
- }
+ bool has_mem = false;
+ struct elt_loc_list **p = &v->locs;
+ int had_locs = v->locs != 0;
- /* 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 (;;)
+ while (*p)
{
- if ((*mem_chain)->elt == v)
+ 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)
{
- unchain_one_elt_list (mem_chain);
- break;
+ p = &(*p)->next;
+ continue;
+ }
+ if (! cselib_mem_conflict_p (mem_rtx, x))
+ {
+ has_mem = true;
+ p = &(*p)->next;
+ continue;
}
- mem_chain = &(*mem_chain)->next;
- }
-
- unchain_one_elt_loc_list (p);
- }
+ /* 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;
+ }
- if (had_locs && v->locs == 0)
- n_useless_values++;
+ mem_chain = &(*mem_chain)->next;
+ }
- return 1;
-}
+ unchain_one_elt_loc_list (p);
+ }
-/* 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). */
+ if (had_locs && v->locs == 0)
+ n_useless_values++;
-static void
-cselib_invalidate_mem (mem_rtx)
- rtx mem_rtx;
-{
- htab_traverse (hash_table, cselib_invalidate_mem_1, mem_rtx);
+ next = v->next_containing_mem;
+ if (has_mem)
+ {
+ *vp = v;
+ vp = &(*vp)->next_containing_mem;
+ }
+ else
+ v->next_containing_mem = NULL;
+ }
+ *vp = &dummy_val;
}
/* Invalidate DEST, which is being assigned to or clobbered. The second and
if (dreg >= 0)
{
- if (REG_VALUES (dreg) == 0)
- VARRAY_PUSH_UINT (used_regs, dreg);
-
if (dreg < FIRST_PSEUDO_REGISTER)
{
unsigned int n = HARD_REGNO_NREGS (dreg, GET_MODE (dest));
max_value_regs = n;
}
- REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt);
+ if (REG_VALUES (dreg) == 0)
+ {
+ VARRAY_PUSH_UINT (used_regs, dreg);
+ REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt);
+ }
+ else
+ {
+ if (REG_VALUES (dreg)->elt == 0)
+ REG_VALUES (dreg)->elt = src_elt;
+ else
+ /* The register should have been invalidated. */
+ abort ();
+ }
+
if (src_elt->locs == 0)
n_useless_values--;
src_elt->locs = new_elt_loc_list (src_elt->locs, dest);
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. */
&& GET_CODE (PATTERN (insn)) == ASM_OPERANDS
&& MEM_VOLATILE_P (PATTERN (insn))))
{
- clear_table (0);
+ clear_table ();
return;
}
{
reg_values = reg_values_old;
used_regs = used_regs_old;
- VARRAY_CLEAR (reg_values);
- VARRAY_CLEAR (used_regs);
}
else
{
}
hash_table = htab_create_ggc (31, get_value_hash, entry_and_rtx_equal_p,
NULL);
- clear_table (1);
+ cselib_current_insn_in_libcall = false;
}
/* Called when the current user is done with cselib. */
void
cselib_finish ()
{
+ clear_table ();
reg_values_old = reg_values;
reg_values = 0;
used_regs_old = used_regs;
OSDN Git Service
