/* Alias analysis for GNU C
- Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003
+ Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004
Free Software Foundation, Inc.
Contributed by John Carr (jfc@mit.edu).
#include "timevar.h"
#include "target.h"
#include "cgraph.h"
+#include "varray.h"
/* The alias sets assigned to MEMs assist the back-end in determining
which MEMs can alias which other MEMs. In general, two MEMs in
different alias sets cannot alias each other, with one important
exception. Consider something like:
- struct S {int i; double d; };
+ struct S { int i; double d; };
a store to an `S' can alias something of either type `int' or type
`double'. (However, a store to an `int' cannot alias a `double'
However, this is no actual entry for alias set zero. It is an
error to attempt to explicitly construct a subset of zero. */
-typedef struct alias_set_entry
+struct alias_set_entry GTY(())
{
/* The alias set number, as stored in MEM_ALIAS_SET. */
HOST_WIDE_INT alias_set;
continuing our example above, the children here will be all of
`int', `double', `float', and `struct S'. */
- splay_tree children;
+ splay_tree GTY((param1_is (int), param2_is (int))) children;
/* Nonzero if would have a child of zero: this effectively makes this
alias set the same as alias set zero. */
int has_zero_child;
-} *alias_set_entry;
+};
+typedef struct alias_set_entry *alias_set_entry;
static int rtx_equal_for_memref_p (rtx, rtx);
static rtx find_symbolic_term (rtx);
current function performs nonlocal memory memory references for the
purposes of marking the function as a constant function. */
-static GTY((length ("reg_base_value_size"))) rtx *reg_base_value;
+static GTY(()) varray_type reg_base_value;
static rtx *new_reg_base_value;
-static unsigned int reg_base_value_size; /* size of reg_base_value array */
+
+/* We preserve the copy of old array around to avoid amount of garbage
+ produced. About 8% of garbage produced were attributed to this
+ array. */
+static GTY((deletable (""))) varray_type old_reg_base_value;
/* Static hunks of RTL used by the aliasing code; these are initialized
once per function to avoid unnecessary RTL allocations. */
static GTY (()) rtx static_reg_base_value[FIRST_PSEUDO_REGISTER];
#define REG_BASE_VALUE(X) \
- (REGNO (X) < reg_base_value_size \
- ? reg_base_value[REGNO (X)] : 0)
+ (reg_base_value && REGNO (X) < VARRAY_SIZE (reg_base_value) \
+ ? VARRAY_RTX (reg_base_value, REGNO (X)) : 0)
/* Vector of known invariant relationships between registers. Set in
loop unrolling. Indexed by register number, if nonzero the value
Because this array contains only pseudo registers it has no effect
after reload. */
static rtx *alias_invariant;
+unsigned int alias_invariant_size;
/* Vector indexed by N giving the initial (unchanging) value known for
pseudo-register N. This array is initialized in
static bool copying_arguments;
/* The splay-tree used to store the various alias set entries. */
-static splay_tree alias_sets;
+static GTY ((param_is (struct alias_set_entry))) varray_type alias_sets;
\f
/* Returns a pointer to the alias set entry for ALIAS_SET, if there is
such an entry, or NULL otherwise. */
-static alias_set_entry
+static inline alias_set_entry
get_alias_set_entry (HOST_WIDE_INT alias_set)
{
- splay_tree_node sn
- = splay_tree_lookup (alias_sets, (splay_tree_key) alias_set);
-
- return sn != 0 ? ((alias_set_entry) sn->value) : 0;
+ return (alias_set_entry)VARRAY_GENERIC_PTR (alias_sets, alias_set);
}
/* Returns nonzero if the alias sets for MEM1 and MEM2 are such that
the two MEMs cannot alias each other. */
-static int
+static inline int
mems_in_disjoint_alias_sets_p (rtx mem1, rtx mem2)
{
#ifdef ENABLE_CHECKING
if (pointed_to_alias_set == 0)
/* It's not legal to make a subset of alias set zero. */
- ;
+ DECL_POINTER_ALIAS_SET (decl) = 0;
else
{
DECL_POINTER_ALIAS_SET (decl) = new_alias_set ();
/* Return a brand-new alias set. */
+static GTY(()) HOST_WIDE_INT last_alias_set;
+
HOST_WIDE_INT
new_alias_set (void)
{
- static HOST_WIDE_INT last_alias_set;
-
if (flag_strict_aliasing)
- return ++last_alias_set;
+ {
+ if (!alias_sets)
+ VARRAY_GENERIC_PTR_INIT (alias_sets, 10, "alias sets");
+ else
+ VARRAY_GROW (alias_sets, last_alias_set + 2);
+ return ++last_alias_set;
+ }
else
return 0;
}
-/* Indicate that things in SUBSET can alias things in SUPERSET, but
- not vice versa. For example, in C, a store to an `int' can alias a
- structure containing an `int', but not vice versa. Here, the
- structure would be the SUPERSET and `int' the SUBSET. This
- function should be called only once per SUPERSET/SUBSET pair.
+/* Indicate that things in SUBSET can alias things in SUPERSET, but that
+ not everything that aliases SUPERSET also aliases SUBSET. For example,
+ in C, a store to an `int' can alias a load of a structure containing an
+ `int', and vice versa. But it can't alias a load of a 'double' member
+ of the same structure. Here, the structure would be the SUPERSET and
+ `int' the SUBSET. This relationship is also described in the comment at
+ the beginning of this file.
+
+ This function should be called only once per SUPERSET/SUBSET pair.
It is illegal for SUPERSET to be zero; everything is implicitly a
subset of alias set zero. */
{
/* Create an entry for the SUPERSET, so that we have a place to
attach the SUBSET. */
- superset_entry = xmalloc (sizeof (struct alias_set_entry));
+ superset_entry = ggc_alloc (sizeof (struct alias_set_entry));
superset_entry->alias_set = superset;
superset_entry->children
- = splay_tree_new (splay_tree_compare_ints, 0, 0);
+ = splay_tree_new_ggc (splay_tree_compare_ints);
superset_entry->has_zero_child = 0;
- splay_tree_insert (alias_sets, (splay_tree_key) superset,
- (splay_tree_value) superset_entry);
+ VARRAY_GENERIC_PTR (alias_sets, superset) = superset_entry;
}
if (subset == 0)
case RECORD_TYPE:
case UNION_TYPE:
case QUAL_UNION_TYPE:
- /* Recursively record aliases for the base classes, if there are any */
+ /* Recursively record aliases for the base classes, if there are any. */
if (TYPE_BINFO (type) != NULL && TYPE_BINFO_BASETYPES (type) != NULL)
{
int i;
/* Allocate an alias set for use in storing and reading from the varargs
spill area. */
+static GTY(()) HOST_WIDE_INT varargs_set = -1;
+
HOST_WIDE_INT
get_varargs_alias_set (void)
{
- static HOST_WIDE_INT set = -1;
-
- if (set == -1)
- set = new_alias_set ();
+ if (varargs_set == -1)
+ varargs_set = new_alias_set ();
- return set;
+ return varargs_set;
}
/* Likewise, but used for the fixed portions of the frame, e.g., register
save areas. */
+static GTY(()) HOST_WIDE_INT frame_set = -1;
+
HOST_WIDE_INT
get_frame_alias_set (void)
{
- static HOST_WIDE_INT set = -1;
+ if (frame_set == -1)
+ frame_set = new_alias_set ();
- if (set == -1)
- set = new_alias_set ();
-
- return set;
+ return frame_set;
}
/* Inside SRC, the source of a SET, find a base address. */
The test above is not sufficient because the scheduler may move
a copy out of an arg reg past the NOTE_INSN_FUNCTION_BEGIN. */
if ((regno >= FIRST_PSEUDO_REGISTER || fixed_regs[regno])
- && regno < reg_base_value_size)
+ && regno < VARRAY_SIZE (reg_base_value))
{
/* If we're inside init_alias_analysis, use new_reg_base_value
to reduce the number of relaxation iterations. */
&& REG_N_SETS (regno) == 1)
return new_reg_base_value[regno];
- if (reg_base_value[regno])
- return reg_base_value[regno];
+ if (VARRAY_RTX (reg_base_value, regno))
+ return VARRAY_RTX (reg_base_value, regno);
}
return 0;
{
rtx temp = find_base_value (XEXP (src, 0));
-#ifdef POINTERS_EXTEND_UNSIGNED
- if (temp != 0 && CONSTANT_P (temp) && GET_MODE (temp) != Pmode)
+ if (temp != 0 && CONSTANT_P (temp))
temp = convert_memory_address (Pmode, temp);
-#endif
return temp;
}
regno = REGNO (dest);
- if (regno >= reg_base_value_size)
+ if (regno >= VARRAY_SIZE (reg_base_value))
abort ();
/* If this spans multiple hard registers, then we must indicate that every
register has an unusable value. */
if (regno < FIRST_PSEUDO_REGISTER)
- n = HARD_REGNO_NREGS (regno, GET_MODE (dest));
+ n = hard_regno_nregs[regno][GET_MODE (dest)];
else
n = 1;
if (n != 1)
void
record_base_value (unsigned int regno, rtx val, int invariant)
{
- if (regno >= reg_base_value_size)
- return;
-
- if (invariant && alias_invariant)
+ if (invariant && alias_invariant && regno < alias_invariant_size)
alias_invariant[regno] = val;
+ if (regno >= VARRAY_SIZE (reg_base_value))
+ VARRAY_GROW (reg_base_value, max_reg_num ());
+
if (GET_CODE (val) == REG)
{
- if (REGNO (val) < reg_base_value_size)
- reg_base_value[regno] = reg_base_value[REGNO (val)];
-
+ VARRAY_RTX (reg_base_value, regno)
+ = REG_BASE_VALUE (val);
return;
}
-
- reg_base_value[regno] = find_base_value (val);
+ VARRAY_RTX (reg_base_value, regno)
+ = find_base_value (val);
}
/* Clear alias info for a register. This is used if an RTL transformation
/* Some RTL can be compared without a recursive examination. */
switch (code)
{
- case VALUE:
- return CSELIB_VAL_PTR (x) == CSELIB_VAL_PTR (y);
-
case REG:
return REGNO (x) == REGNO (y);
case SYMBOL_REF:
return XSTR (x, 0) == XSTR (y, 0);
+ case VALUE:
case CONST_INT:
case CONST_DOUBLE:
/* There's no need to compare the contents of CONST_DOUBLEs or
{
rtx temp = find_base_term (XEXP (x, 0));
-#ifdef POINTERS_EXTEND_UNSIGNED
- if (temp != 0 && CONSTANT_P (temp) && GET_MODE (temp) != Pmode)
+ if (temp != 0 && CONSTANT_P (temp))
temp = convert_memory_address (Pmode, temp);
-#endif
return temp;
}
case VALUE:
val = CSELIB_VAL_PTR (x);
+ if (!val)
+ return 0;
for (l = val->locs; l; l = l->next)
if ((x = find_base_term (l->loc)) != 0)
return x;
if (GET_CODE (x) != VALUE)
return x;
v = CSELIB_VAL_PTR (x);
- for (l = v->locs; l; l = l->next)
- if (CONSTANT_P (l->loc))
- return l->loc;
- for (l = v->locs; l; l = l->next)
- if (GET_CODE (l->loc) != REG && GET_CODE (l->loc) != MEM)
- return l->loc;
- if (v->locs)
- return v->locs->loc;
+ if (v)
+ {
+ for (l = v->locs; l; l = l->next)
+ if (CONSTANT_P (l->loc))
+ return l->loc;
+ for (l = v->locs; l; l = l->next)
+ if (GET_CODE (l->loc) != REG && GET_CODE (l->loc) != MEM)
+ return l->loc;
+ if (v->locs)
+ return v->locs->loc;
+ }
return x;
}
unsigned int r_x = REGNO (x), r_y = REGNO (y);
rtx i_x, i_y; /* invariant relationships of X and Y */
- i_x = r_x >= reg_base_value_size ? 0 : alias_invariant[r_x];
- i_y = r_y >= reg_base_value_size ? 0 : alias_invariant[r_y];
+ i_x = r_x >= alias_invariant_size ? 0 : alias_invariant[r_x];
+ i_y = r_y >= alias_invariant_size ? 0 : alias_invariant[r_y];
if (i_x == 0 && i_y == 0)
break;
if (MEM_VOLATILE_P (x))
return 1;
- /* FALLTHROUGH */
+ /* Fall through. */
default:
break;
if (MEM_VOLATILE_P (x))
return 1;
- /* FALLTHROUGH */
+ /* Fall through. */
default:
break;
if (MEM_VOLATILE_P (x))
return 1;
- /* FALLTHROUGH */
+ /* Fall through. */
default:
break;
static_reg_base_value[HARD_FRAME_POINTER_REGNUM]
= gen_rtx_ADDRESS (Pmode, hard_frame_pointer_rtx);
#endif
-
- alias_sets = splay_tree_new (splay_tree_compare_ints, 0, 0);
}
/* Set MEMORY_MODIFIED when X modifies DATA (that is assumed
void
init_alias_analysis (void)
{
- int maxreg = max_reg_num ();
+ unsigned int maxreg = max_reg_num ();
int changed, pass;
int i;
unsigned int ui;
/* Overallocate reg_base_value to allow some growth during loop
optimization. Loop unrolling can create a large number of
registers. */
- reg_base_value_size = maxreg * 2;
- reg_base_value = ggc_alloc_cleared (reg_base_value_size * sizeof (rtx));
+ if (old_reg_base_value)
+ {
+ reg_base_value = old_reg_base_value;
+ /* If varray gets large zeroing cost may get important. */
+ if (VARRAY_SIZE (reg_base_value) > 256
+ && VARRAY_SIZE (reg_base_value) > 4 * maxreg)
+ VARRAY_GROW (reg_base_value, maxreg);
+ VARRAY_CLEAR (reg_base_value);
+ if (VARRAY_SIZE (reg_base_value) < maxreg)
+ VARRAY_GROW (reg_base_value, maxreg);
+ }
+ else
+ {
+ VARRAY_RTX_INIT (reg_base_value, maxreg, "reg_base_value");
+ }
- new_reg_base_value = xmalloc (reg_base_value_size * sizeof (rtx));
- reg_seen = xmalloc (reg_base_value_size);
+ new_reg_base_value = xmalloc (maxreg * sizeof (rtx));
+ reg_seen = xmalloc (maxreg);
if (! reload_completed && flag_old_unroll_loops)
{
/* ??? Why are we realloc'ing if we're just going to zero it? */
alias_invariant = xrealloc (alias_invariant,
- reg_base_value_size * sizeof (rtx));
- memset (alias_invariant, 0, reg_base_value_size * sizeof (rtx));
+ maxreg * sizeof (rtx));
+ memset (alias_invariant, 0, maxreg * sizeof (rtx));
+ alias_invariant_size = maxreg;
}
/* The basic idea is that each pass through this loop will use the
copying_arguments = true;
/* Wipe the potential alias information clean for this pass. */
- memset (new_reg_base_value, 0, reg_base_value_size * sizeof (rtx));
+ memset (new_reg_base_value, 0, maxreg * sizeof (rtx));
/* Wipe the reg_seen array clean. */
- memset (reg_seen, 0, reg_base_value_size);
+ memset (reg_seen, 0, maxreg);
/* Mark all hard registers which may contain an address.
The stack, frame and argument pointers may contain an address.
}
/* Now propagate values from new_reg_base_value to reg_base_value. */
- for (ui = 0; ui < reg_base_value_size; ui++)
+ if (maxreg != (unsigned int) max_reg_num())
+ abort ();
+ for (ui = 0; ui < maxreg; ui++)
{
if (new_reg_base_value[ui]
- && new_reg_base_value[ui] != reg_base_value[ui]
- && ! rtx_equal_p (new_reg_base_value[ui], reg_base_value[ui]))
+ && new_reg_base_value[ui] != VARRAY_RTX (reg_base_value, ui)
+ && ! rtx_equal_p (new_reg_base_value[ui],
+ VARRAY_RTX (reg_base_value, ui)))
{
- reg_base_value[ui] = new_reg_base_value[ui];
+ VARRAY_RTX (reg_base_value, ui) = new_reg_base_value[ui];
changed = 1;
}
}
while (changed && ++pass < MAX_ALIAS_LOOP_PASSES);
/* Fill in the remaining entries. */
- for (i = FIRST_PSEUDO_REGISTER; i < maxreg; i++)
+ for (i = FIRST_PSEUDO_REGISTER; i < (int)maxreg; i++)
if (reg_known_value[i] == 0)
reg_known_value[i] = regno_reg_rtx[i];
{
changed = 0;
pass++;
- for (ui = 0; ui < reg_base_value_size; ui++)
+ for (ui = 0; ui < maxreg; ui++)
{
- rtx base = reg_base_value[ui];
+ rtx base = VARRAY_RTX (reg_base_value, ui);
if (base && GET_CODE (base) == REG)
{
unsigned int base_regno = REGNO (base);
if (base_regno == ui) /* register set from itself */
- reg_base_value[ui] = 0;
+ VARRAY_RTX (reg_base_value, ui) = 0;
else
- reg_base_value[ui] = reg_base_value[base_regno];
+ VARRAY_RTX (reg_base_value, ui)
+ = VARRAY_RTX (reg_base_value, base_regno);
changed = 1;
}
}
void
end_alias_analysis (void)
{
+ old_reg_base_value = reg_base_value;
free (reg_known_value + FIRST_PSEUDO_REGISTER);
reg_known_value = 0;
reg_known_value_size = 0;
free (reg_known_equiv_p + FIRST_PSEUDO_REGISTER);
reg_known_equiv_p = 0;
- reg_base_value = 0;
- reg_base_value_size = 0;
if (alias_invariant)
{
free (alias_invariant);
alias_invariant = 0;
+ alias_invariant_size = 0;
}
}