/* 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 to not alias each other. There is one
- exception, however. Consider something like:
+ different alias sets cannot alias each other, with one important
+ exception. Consider something like:
struct S {int i; double d; };
|/_ _\|
int double
- (The arrows are directed and point downwards.) If, when comparing
- two alias sets, we can hold one set fixed, trace the other set
- downwards, and at some point find the first set, the two MEMs can
- alias one another. In this situation we say the alias set for
- `struct S' is the `superset' and that those for `int' and `double'
- are `subsets'.
+ (The arrows are directed and point downwards.)
+ In this situation we say the alias set for `struct S' is the
+ `superset' and that those for `int' and `double' are `subsets'.
+
+ To see whether two alias sets can point to the same memory, we must
+ see if either alias set is a subset of the other. We need not trace
+ past immediate decendents, however, since we propagate all
+ grandchildren up one level.
Alias set zero is implicitly a superset of all other alias sets.
However, this is no actual entry for alias set zero. It is an
typedef struct alias_set_entry
{
/* The alias set number, as stored in MEM_ALIAS_SET. */
- int alias_set;
+ HOST_WIDE_INT alias_set;
/* The children of the alias set. These are not just the immediate
- children, but, in fact, all children. So, if we have:
+ children, but, in fact, all decendents. So, if we have:
struct T { struct S s; float f; }
continuing our example above, the children here will be all of
`int', `double', `float', and `struct S'. */
splay_tree 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;
-static rtx canon_rtx PARAMS ((rtx));
static int rtx_equal_for_memref_p PARAMS ((rtx, rtx));
static rtx find_symbolic_term PARAMS ((rtx));
static rtx get_addr PARAMS ((rtx));
static rtx find_base_value PARAMS ((rtx));
static int mems_in_disjoint_alias_sets_p PARAMS ((rtx, rtx));
static int insert_subset_children PARAMS ((splay_tree_node, void*));
-static alias_set_entry get_alias_set_entry PARAMS ((int));
+static tree find_base_decl PARAMS ((tree));
+static alias_set_entry get_alias_set_entry PARAMS ((HOST_WIDE_INT));
static rtx fixed_scalar_and_varying_struct_p PARAMS ((rtx, rtx, rtx, rtx,
- int (*)(rtx)));
+ int (*) (rtx)));
static int aliases_everything_p PARAMS ((rtx));
static int write_dependence_p PARAMS ((rtx, rtx, int));
static int nonlocal_reference_p PARAMS ((rtx));
mems_in_disjoint_alias_sets_p (MEM1, MEM2)
/* Cap the number of passes we make over the insns propagating alias
- information through set chains.
-
- 10 is a completely arbitrary choice. */
+ information through set chains. 10 is a completely arbitrary choice. */
#define MAX_ALIAS_LOOP_PASSES 10
/* reg_base_value[N] gives an address to which register N is related.
static unsigned int reg_base_value_size; /* size of reg_base_value array */
#define REG_BASE_VALUE(X) \
- ((unsigned) REGNO (X) < reg_base_value_size ? reg_base_value[REGNO (X)] : 0)
+ (REGNO (X) < reg_base_value_size ? 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
after reload. */
static rtx *alias_invariant;
-/* Vector indexed by N giving the initial (unchanging) value known
- for pseudo-register N. */
+/* Vector indexed by N giving the initial (unchanging) value known for
+ pseudo-register N. This array is initialized in
+ init_alias_analysis, and does not change until end_alias_analysis
+ is called. */
rtx *reg_known_value;
/* Indicates number of valid entries in reg_known_value. */
/* Vector recording for each reg_known_value whether it is due to a
REG_EQUIV note. Future passes (viz., reload) may replace the
pseudo with the equivalent expression and so we account for the
- dependences that would be introduced if that happens. */
-/* ??? This is a problem only on the Convex. The REG_EQUIV notes created in
- assign_parms mention the arg pointer, and there are explicit insns in the
- RTL that modify the arg pointer. Thus we must ensure that such insns don't
- get scheduled across each other because that would invalidate the REG_EQUIV
- notes. One could argue that the REG_EQUIV notes are wrong, but solving
- the problem in the scheduler will likely give better code, so we do it
- here. */
+ dependences that would be introduced if that happens.
+
+ The REG_EQUIV notes created in assign_parms may mention the arg
+ pointer, and there are explicit insns in the RTL that modify the
+ arg pointer. Thus we must ensure that such insns don't get
+ scheduled across each other because that would invalidate the
+ REG_EQUIV notes. One could argue that the REG_EQUIV notes are
+ wrong, but solving the problem in the scheduler will likely give
+ better code, so we do it here. */
char *reg_known_equiv_p;
/* True when scanning insns from the start of the rtl to the
NOTE_INSN_FUNCTION_BEG note. */
-
static int copying_arguments;
/* The splay-tree used to store the various alias set entries. */
-
static splay_tree 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
get_alias_set_entry (alias_set)
- int alias_set;
+ 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;
}
-/* Returns nonzero value if the alias sets for MEM1 and MEM2 are such
- that the two MEMs cannot alias each other. */
+/* Returns nonzero if the alias sets for MEM1 and MEM2 are such that
+ the two MEMs cannot alias each other. */
static int
mems_in_disjoint_alias_sets_p (mem1, mem2)
if (MEM_ALIAS_SET (mem1) == MEM_ALIAS_SET (mem2))
return 0;
- /* Iterate through each of the children of the first alias set,
- comparing it with the second alias set. */
+ /* See if the first alias set is a subset of the second. */
ase = get_alias_set_entry (MEM_ALIAS_SET (mem1));
- if (ase != 0 && splay_tree_lookup (ase->children,
- (splay_tree_key) MEM_ALIAS_SET (mem2)))
+ if (ase != 0
+ && (ase->has_zero_child
+ || splay_tree_lookup (ase->children,
+ (splay_tree_key) MEM_ALIAS_SET (mem2))))
return 0;
/* Now do the same, but with the alias sets reversed. */
ase = get_alias_set_entry (MEM_ALIAS_SET (mem2));
- if (ase != 0 && splay_tree_lookup (ase->children,
- (splay_tree_key) MEM_ALIAS_SET (mem1)))
+ if (ase != 0
+ && (ase->has_zero_child
+ || splay_tree_lookup (ase->children,
+ (splay_tree_key) MEM_ALIAS_SET (mem1))))
return 0;
/* The two MEMs are in distinct alias sets, and neither one is the
return 0;
}
+\f
+/* T is an expression with pointer type. Find the DECL on which this
+ expression is based. (For example, in `a[i]' this would be `a'.)
+ If there is no such DECL, or a unique decl cannot be determined,
+ NULL_TREE is retured. */
+
+static tree
+find_base_decl (t)
+ tree t;
+{
+ tree d0, d1, d2;
+
+ if (t == 0 || t == error_mark_node || ! POINTER_TYPE_P (TREE_TYPE (t)))
+ return 0;
+
+ /* If this is a declaration, return it. */
+ if (TREE_CODE_CLASS (TREE_CODE (t)) == 'd')
+ return t;
+
+ /* Handle general expressions. It would be nice to deal with
+ COMPONENT_REFs here. If we could tell that `a' and `b' were the
+ same, then `a->f' and `b->f' are also the same. */
+ switch (TREE_CODE_CLASS (TREE_CODE (t)))
+ {
+ case '1':
+ return find_base_decl (TREE_OPERAND (t, 0));
+
+ case '2':
+ /* Return 0 if found in neither or both are the same. */
+ d0 = find_base_decl (TREE_OPERAND (t, 0));
+ d1 = find_base_decl (TREE_OPERAND (t, 1));
+ if (d0 == d1)
+ return d0;
+ else if (d0 == 0)
+ return d1;
+ else if (d1 == 0)
+ return d0;
+ else
+ return 0;
+
+ case '3':
+ d0 = find_base_decl (TREE_OPERAND (t, 0));
+ d1 = find_base_decl (TREE_OPERAND (t, 1));
+ d0 = find_base_decl (TREE_OPERAND (t, 0));
+ d2 = find_base_decl (TREE_OPERAND (t, 2));
+
+ /* Set any nonzero values from the last, then from the first. */
+ if (d1 == 0) d1 = d2;
+ if (d0 == 0) d0 = d1;
+ if (d1 == 0) d1 = d0;
+ if (d2 == 0) d2 = d1;
+
+ /* At this point all are nonzero or all are zero. If all three are the
+ same, return it. Otherwise, return zero. */
+ return (d0 == d1 && d1 == d2) ? d0 : 0;
+
+ default:
+ return 0;
+ }
+}
+
+/* Return the alias set for T, which may be either a type or an
+ expression. Call language-specific routine for help, if needed. */
+
+HOST_WIDE_INT
+get_alias_set (t)
+ tree t;
+{
+ tree orig_t;
+ HOST_WIDE_INT set;
+ HOST_WIDE_INT bitsize, bitpos;
+ tree offset;
+ enum machine_mode mode;
+ int volatilep, unsignedp;
+ unsigned int alignment;
+
+ /* If we're not doing any alias analysis, just assume everything
+ aliases everything else. Also return 0 if this or its type is
+ an error. */
+ if (! flag_strict_aliasing || t == error_mark_node
+ || (! TYPE_P (t)
+ && (TREE_TYPE (t) == 0 || TREE_TYPE (t) == error_mark_node)))
+ return 0;
+
+ /* We can be passed either an expression or a type. This and the
+ language-specific routine may make mutually-recursive calls to
+ each other to figure out what to do. At each juncture, we see if
+ this is a tree that the language may need to handle specially.
+ First handle things that aren't types and start by removing nops
+ since we care only about the actual object. */
+ if (! TYPE_P (t))
+ {
+ while (TREE_CODE (t) == NOP_EXPR || TREE_CODE (t) == CONVERT_EXPR
+ || TREE_CODE (t) == NON_LVALUE_EXPR)
+ t = TREE_OPERAND (t, 0);
+
+ /* Now give the language a chance to do something but record what we
+ gave it this time. */
+ orig_t = t;
+ if ((set = lang_get_alias_set (t)) != -1)
+ return set;
+
+ /* If this is a reference, go inside it and use the underlying
+ object. */
+ if (TREE_CODE_CLASS (TREE_CODE (t)) == 'r')
+ t = get_inner_reference (t, &bitsize, &bitpos, &offset, &mode,
+ &unsignedp, &volatilep, &alignment);
+
+ if (TREE_CODE (t) == INDIRECT_REF)
+ {
+ /* Check for accesses through restrict-qualified pointers. */
+ tree decl = find_base_decl (TREE_OPERAND (t, 0));
+
+ if (decl && DECL_POINTER_ALIAS_SET_KNOWN_P (decl))
+ /* We use the alias set indicated in the declaration. */
+ return DECL_POINTER_ALIAS_SET (decl);
+
+ /* If we have an INDIRECT_REF via a void pointer, we don't
+ know anything about what that might alias. */
+ if (TREE_CODE (TREE_TYPE (t)) == VOID_TYPE)
+ return 0;
+ }
+
+ /* Give the language another chance to do something special. */
+ if (orig_t != t
+ && (set = lang_get_alias_set (t)) != -1)
+ return set;
+
+ /* Now all we care about is the type. */
+ t = TREE_TYPE (t);
+ }
+
+ /* Variant qualifiers don't affect the alias set, so get the main
+ variant. If this is a type with a known alias set, return it. */
+ t = TYPE_MAIN_VARIANT (t);
+ if (TYPE_P (t) && TYPE_ALIAS_SET_KNOWN_P (t))
+ return TYPE_ALIAS_SET (t);
+
+ /* See if the language has special handling for this type. */
+ if ((set = lang_get_alias_set (t)) != -1)
+ {
+ /* If the alias set is now known, we are done. */
+ if (TYPE_ALIAS_SET_KNOWN_P (t))
+ return TYPE_ALIAS_SET (t);
+ }
+
+ /* There are no objects of FUNCTION_TYPE, so there's no point in
+ using up an alias set for them. (There are, of course, pointers
+ and references to functions, but that's different.) */
+ else if (TREE_CODE (t) == FUNCTION_TYPE)
+ set = 0;
+ else
+ /* Otherwise make a new alias set for this type. */
+ set = new_alias_set ();
+
+ TYPE_ALIAS_SET (t) = set;
+
+ /* If this is an aggregate type, we must record any component aliasing
+ information. */
+ if (AGGREGATE_TYPE_P (t))
+ record_component_aliases (t);
+
+ return set;
+}
+
+/* Return a brand-new alias set. */
+
+HOST_WIDE_INT
+new_alias_set ()
+{
+ static HOST_WIDE_INT last_alias_set;
+
+ if (flag_strict_aliasing)
+ 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. At
- present any given alias set may only be a subset of one superset.
+ 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. */
void
record_alias_subset (superset, subset)
- int superset;
- int subset;
+ HOST_WIDE_INT superset;
+ HOST_WIDE_INT subset;
{
alias_set_entry superset_entry;
alias_set_entry subset_entry;
superset_entry->alias_set = superset;
superset_entry->children
= splay_tree_new (splay_tree_compare_ints, 0, 0);
+ superset_entry->has_zero_child = 0;
splay_tree_insert (alias_sets, (splay_tree_key) superset,
(splay_tree_value) superset_entry);
+ }
+
+ if (subset == 0)
+ superset_entry->has_zero_child = 1;
+ else
+ {
+ subset_entry = get_alias_set_entry (subset);
+ /* If there is an entry for the subset, enter all of its children
+ (if they are not already present) as children of the SUPERSET. */
+ if (subset_entry)
+ {
+ if (subset_entry->has_zero_child)
+ superset_entry->has_zero_child = 1;
+
+ splay_tree_foreach (subset_entry->children, insert_subset_children,
+ superset_entry->children);
+ }
+ /* Enter the SUBSET itself as a child of the SUPERSET. */
+ splay_tree_insert (superset_entry->children,
+ (splay_tree_key) subset, 0);
}
+}
+
+/* Record that component types of TYPE, if any, are part of that type for
+ aliasing purposes. For record types, we only record component types
+ for fields that are marked addressable. For array types, we always
+ record the component types, so the front end should not call this
+ function if the individual component aren't addressable. */
+
+void
+record_component_aliases (type)
+ tree type;
+{
+ HOST_WIDE_INT superset = get_alias_set (type);
+ tree field;
+
+ if (superset == 0)
+ return;
+
+ switch (TREE_CODE (type))
+ {
+ case ARRAY_TYPE:
+ if (! TYPE_NONALIASED_COMPONENT (type))
+ record_alias_subset (superset, get_alias_set (TREE_TYPE (type)));
+ break;
+
+ case RECORD_TYPE:
+ case UNION_TYPE:
+ case QUAL_UNION_TYPE:
+ for (field = TYPE_FIELDS (type); field != 0; field = TREE_CHAIN (field))
+ if (TREE_CODE (field) == FIELD_DECL && ! DECL_NONADDRESSABLE_P (field))
+ record_alias_subset (superset, get_alias_set (TREE_TYPE (field)));
+ break;
+
+ default:
+ break;
+ }
+}
+
+/* Allocate an alias set for use in storing and reading from the varargs
+ spill area. */
- subset_entry = get_alias_set_entry (subset);
+HOST_WIDE_INT
+get_varargs_alias_set ()
+{
+ static HOST_WIDE_INT set = -1;
- /* If there is an entry for the subset, enter all of its children
- (if they are not already present) as children of the SUPERSET. */
- if (subset_entry)
- splay_tree_foreach (subset_entry->children,
- insert_subset_children,
- superset_entry->children);
+ if (set == -1)
+ set = new_alias_set ();
- /* Enter the SUBSET itself as a child of the SUPERSET. */
- splay_tree_insert (superset_entry->children,
- (splay_tree_key) subset, 0);
+ return set;
+}
+
+/* Likewise, but used for the fixed portions of the frame, e.g., register
+ save areas. */
+
+HOST_WIDE_INT
+get_frame_alias_set ()
+{
+ static HOST_WIDE_INT set = -1;
+
+ if (set == -1)
+ set = new_alias_set ();
+
+ return set;
}
/* Inside SRC, the source of a SET, find a base address. */
reg_seen[regno] = 1;
}
-/* Called from loop optimization when a new pseudo-register is created. */
+/* Called from loop optimization when a new pseudo-register is
+ created. It indicates that REGNO is being set to VAL. f INVARIANT
+ is true then this value also describes an invariant relationship
+ which can be used to deduce that two registers with unknown values
+ are different. */
void
record_base_value (regno, val, invariant)
- int regno;
+ unsigned int regno;
rtx val;
int invariant;
{
- if ((unsigned) regno >= reg_base_value_size)
+ if (regno >= reg_base_value_size)
return;
- /* If INVARIANT is true then this value also describes an invariant
- relationship which can be used to deduce that two registers with
- unknown values are different. */
if (invariant && alias_invariant)
alias_invariant[regno] = val;
if (GET_CODE (val) == REG)
{
- if ((unsigned) REGNO (val) < reg_base_value_size)
+ if (REGNO (val) < reg_base_value_size)
reg_base_value[regno] = reg_base_value[REGNO (val)];
return;
reg_base_value[regno] = find_base_value (val);
}
-static rtx
+/* Returns a canonical version of X, from the point of view alias
+ analysis. (For example, if X is a MEM whose address is a register,
+ and the register has a known value (say a SYMBOL_REF), then a MEM
+ whose address is the SYMBOL_REF is returned.) */
+
+rtx
canon_rtx (x)
rtx x;
{
{
rtx new = gen_rtx_MEM (GET_MODE (x), addr);
- RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x);
MEM_COPY_ATTRIBUTES (new, x);
- MEM_ALIAS_SET (new) = MEM_ALIAS_SET (x);
x = new;
}
}
if (GET_MODE (x) != GET_MODE (y))
return 0;
- /* REG, LABEL_REF, and SYMBOL_REF can be compared nonrecursively. */
-
- if (code == REG)
- return REGNO (x) == REGNO (y);
- if (code == LABEL_REF)
- return XEXP (x, 0) == XEXP (y, 0);
- if (code == SYMBOL_REF)
- return XSTR (x, 0) == XSTR (y, 0);
- if (code == CONST_INT)
- return INTVAL (x) == INTVAL (y);
- /* There's no need to compare the contents of CONST_DOUBLEs because
- they're unique. */
- if (code == CONST_DOUBLE)
- return 0;
- if (code == ADDRESSOF)
- return (REGNO (XEXP (x, 0)) == REGNO (XEXP (y, 0))
- && XINT (x, 1) == XINT (y, 1));
+ /* Some RTL can be compared without a recursive examination. */
+ switch (code)
+ {
+ case REG:
+ return REGNO (x) == REGNO (y);
+
+ case LABEL_REF:
+ return XEXP (x, 0) == XEXP (y, 0);
+
+ case SYMBOL_REF:
+ return XSTR (x, 0) == XSTR (y, 0);
+
+ case CONST_INT:
+ case CONST_DOUBLE:
+ /* There's no need to compare the contents of CONST_DOUBLEs or
+ CONST_INTs because pointer equality is a good enough
+ comparison for these nodes. */
+ return 0;
+
+ case ADDRESSOF:
+ return (REGNO (XEXP (x, 0)) == REGNO (XEXP (y, 0))
+ && XINT (x, 1) == XINT (y, 1));
+
+ default:
+ break;
+ }
/* For commutative operations, the RTX match if the operand match in any
order. Also handle the simple binary and unary cases without a loop. */
/* Convert the address X into something we can use. This is done by returning
it unchanged unless it is a value; in the latter case we call cselib to get
a more useful rtx. */
+
static rtx
get_addr (x)
rtx x;
changed. A volatile and non-volatile reference can be interchanged
though.
- A MEM_IN_STRUCT reference at a non-QImode non-AND varying address can never
- conflict with a non-MEM_IN_STRUCT reference at a fixed address. We must
- allow QImode aliasing because the ANSI C standard allows character
- pointers to alias anything. We are assuming that characters are
- always QImode here. We also must allow AND addresses, because they may
- generate accesses outside the object being referenced. This is used to
- generate aligned addresses from unaligned addresses, for instance, the
- alpha storeqi_unaligned pattern. */
+ A MEM_IN_STRUCT reference at a non-AND varying address can never
+ conflict with a non-MEM_IN_STRUCT reference at a fixed address. We
+ also must allow AND addresses, because they may generate accesses
+ outside the object being referenced. This is used to generate
+ aligned addresses from unaligned addresses, for instance, the alpha
+ storeqi_unaligned pattern. */
/* Read dependence: X is read after read in MEM takes place. There can
only be a dependence here if both reads are volatile. */
aliases_everything_p (mem)
rtx mem;
{
- if (GET_MODE (mem) == QImode)
- /* ANSI C says that a `char*' can point to anything. */
- return 1;
-
if (GET_CODE (XEXP (mem, 0)) == AND)
/* If the address is an AND, its very hard to know at what it is
actually pointing. */
if (GET_RTX_CLASS (code) == 'i')
{
- /* Constant functions are constant. */
+ /* Constant functions can be constant if they don't use
+ scratch memory used to mark function w/o side effects. */
if (code == CALL_INSN && CONST_CALL_P (x))
- return 0;
- x = PATTERN (x);
+ {
+ x = CALL_INSN_FUNCTION_USAGE (x);
+ if (x == 0)
+ return 0;
+ }
+ else
+ x = PATTERN (x);
code = GET_CODE (x);
}
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
- if (fmt[i] == 'e')
+ if (fmt[i] == 'e' && XEXP (x, i))
{
if (nonlocal_reference_p (XEXP (x, i)))
return 1;
alias_sets = splay_tree_new (splay_tree_compare_ints, 0, 0);
}
+/* Initialize the aliasing machinery. Initialize the REG_KNOWN_VALUE
+ array. */
+
void
init_alias_analysis ()
{
/* Walk the insns adding values to the new_reg_base_value array. */
for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
{
-#if defined (HAVE_prologue) || defined (HAVE_epilogue)
- if (prologue_epilogue_contains (insn))
- continue;
-#endif
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
{
rtx note, set;
+
+#if defined (HAVE_prologue) || defined (HAVE_epilogue)
+ if (prologue_epilogue_contains (insn))
+ continue;
+#endif
+
/* If this insn has a noalias note, process it, Otherwise,
scan for sets. A simple set will have no side effects
which could change the base value of any other register. */
if (GET_CODE (PATTERN (insn)) == SET
- && (find_reg_note (insn, REG_NOALIAS, NULL_RTX)))
+ && REG_NOTES (insn) != 0
+ && find_reg_note (insn, REG_NOALIAS, NULL_RTX))
record_set (SET_DEST (PATTERN (insn)), NULL_RTX, NULL);
else
note_stores (PATTERN (insn), record_set, NULL);
if (set != 0
&& GET_CODE (SET_DEST (set)) == REG
&& REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
+ && REG_NOTES (insn) != 0
&& (((note = find_reg_note (insn, REG_EQUAL, 0)) != 0
&& REG_N_SETS (REGNO (SET_DEST (set))) == 1)
|| (note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0)
OSDN Git Service
