#include "regs.h"
#include "hard-reg-set.h"
#include "flags.h"
+#include "output.h"
#include "toplev.h"
+#include "splay-tree.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 to not alias each other. There is one
+ exception, however. Consider something like:
+
+ 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'
+ and vice versa.) We indicate this via a tree structure that looks
+ like:
+ struct S
+ / \
+ / \
+ |/_ _\|
+ int double
+
+ (The arrows are directed and point downwards.) If, when comparing
+ two alias sets, we can hold one set fixed, and 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'.
+
+ 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
+ error to attempt to explicitly construct a subset of zero. */
+
+typedef struct alias_set_entry {
+ /* The alias set number, as stored in MEM_ALIAS_SET. */
+ 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:
+
+ 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;
+}* alias_set_entry;
static rtx canon_rtx PROTO((rtx));
static int rtx_equal_for_memref_p PROTO((rtx, rtx));
HOST_WIDE_INT));
static void record_set PROTO((rtx, rtx));
static rtx find_base_term PROTO((rtx));
-static int base_alias_check PROTO((rtx, rtx));
+static int base_alias_check PROTO((rtx, rtx, enum machine_mode,
+ enum machine_mode));
static rtx find_base_value PROTO((rtx));
+static int mems_in_disjoint_alias_sets_p PROTO((rtx, rtx));
+static int alias_set_compare PROTO((splay_tree_key,
+ splay_tree_key));
+static int insert_subset_children PROTO((splay_tree_node,
+ void*));
+static alias_set_entry get_alias_set_entry PROTO((int));
/* Set up all info needed to perform alias analysis on memory references. */
#define SIZE_FOR_MODE(X) (GET_MODE_SIZE (GET_MODE (X)))
+/* Returns nonzero if MEM1 and MEM2 do not alias because they are in
+ different alias sets. We ignore alias sets in functions making use
+ of variable arguments because the va_arg macros on some systems are
+ not legal ANSI C. */
+#define DIFFERENT_ALIAS_SETS_P(MEM1, MEM2) \
+ mems_in_disjoint_alias_sets_p (MEM1, MEM2)
+
/* Cap the number of passes we make over the insns propagating alias
information through set chains.
rtx *new_reg_base_value;
unsigned int reg_base_value_size; /* size of reg_base_value array */
#define REG_BASE_VALUE(X) \
- (REGNO (X) < reg_base_value_size ? reg_base_value[REGNO (X)] : 0)
+ ((unsigned) 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
static int copying_arguments;
+/* The splay-tree used to store the various alias set entries. */
+
+static splay_tree alias_sets;
+
+/* Returns -1, 0, 1 according to whether SET1 is less than, equal to,
+ or greater than SET2. */
+
+static int
+alias_set_compare (set1, set2)
+ splay_tree_key set1;
+ splay_tree_key set2;
+{
+ int s1 = (int) set1;
+ int s2 = (int) set2;
+
+ if (s1 < s2)
+ return -1;
+ else if (s1 > s2)
+ return 1;
+ else
+ return 0;
+}
+
+/* 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;
+{
+ splay_tree_node sn =
+ splay_tree_lookup (alias_sets, (splay_tree_key) alias_set);
+
+ return sn ? ((alias_set_entry) sn->value) : ((alias_set_entry) 0);
+}
+
+/* Returns nonzero value 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)
+ rtx mem1;
+ rtx mem2;
+{
+ alias_set_entry ase;
+
+#ifdef ENABLE_CHECKING
+/* Perform a basic sanity check. Namely, that there are no alias sets
+ if we're not using strict aliasing. This helps to catch bugs
+ whereby someone uses PUT_CODE, but doesn't clear MEM_ALIAS_SET, or
+ where a MEM is allocated in some way other than by the use of
+ gen_rtx_MEM, and the MEM_ALIAS_SET is not cleared. If we begin to
+ use alias sets to indicate that spilled registers cannot alias each
+ other, we might need to remove this check. */
+ if (!flag_strict_aliasing &&
+ (MEM_ALIAS_SET (mem1) || MEM_ALIAS_SET (mem2)))
+ abort ();
+#endif
+
+ /* The code used in varargs macros are often not conforming ANSI C,
+ which can trick the compiler into making incorrect aliasing
+ assumptions in these functions. So, we don't use alias sets in
+ such a function. FIXME: This should be moved into the front-end;
+ it is a language-dependent notion, and there's no reason not to
+ still use these checks to handle globals. */
+ if (current_function_stdarg || current_function_varargs)
+ return 0;
+
+ if (!MEM_ALIAS_SET (mem1) || !MEM_ALIAS_SET (mem2))
+ /* We have no alias set information for one of the MEMs, so we
+ have to assume it can alias anything. */
+ return 0;
+
+ if (MEM_ALIAS_SET (mem1) == MEM_ALIAS_SET (mem2))
+ /* The two alias sets are the same, so they may alias. */
+ return 0;
+
+ /* Iterate through each of the children of the first alias set,
+ comparing it with the second alias set. */
+ ase = get_alias_set_entry (MEM_ALIAS_SET (mem1));
+ if (ase && 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 && 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
+ child of the other. Therefore, they cannot alias. */
+ return 1;
+}
+
+/* Insert the NODE into the splay tree given by DATA. Used by
+ record_alias_subset via splay_tree_foreach. */
+
+static int
+insert_subset_children (node, data)
+ splay_tree_node node;
+ void *data;
+{
+ splay_tree_insert ((splay_tree) data,
+ node->key,
+ node->value);
+
+ 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.
+
+ 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;
+{
+ alias_set_entry superset_entry;
+ alias_set_entry subset_entry;
+
+ if (superset == 0)
+ abort ();
+
+ superset_entry = get_alias_set_entry (superset);
+ if (!superset_entry)
+ {
+ /* Create an entry for the SUPERSET, so that we have a place to
+ attach the SUBSET. */
+ superset_entry =
+ (alias_set_entry) xmalloc (sizeof (struct alias_set_entry));
+ superset_entry->alias_set = superset;
+ superset_entry->children
+ = splay_tree_new (&alias_set_compare, 0, 0);
+ splay_tree_insert (alias_sets,
+ (splay_tree_key) superset,
+ (splay_tree_value) superset_entry);
+
+ }
+
+ subset_entry = get_alias_set_entry (subset);
+ if (subset_entry)
+ /* There is an entry for the subset. Enter all of its children
+ (if they are not already present) as children of the SUPERSET. */
+ 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,
+ /*value=*/0);
+}
+
/* Inside SRC, the source of a SET, find a base address. */
static rtx
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 (src) >= FIRST_PSEUDO_REGISTER
- && REGNO (src) < reg_base_value_size
+ && (unsigned) REGNO (src) < reg_base_value_size
&& reg_base_value[REGNO (src)])
return reg_base_value[REGNO (src)];
rtx val;
int invariant;
{
- if (regno >= reg_base_value_size)
+ if ((unsigned) regno >= reg_base_value_size)
return;
/* If INVARIANT is true then this value also describes an invariant
if (GET_CODE (val) == REG)
{
- if (REGNO (val) < reg_base_value_size)
+ if ((unsigned) REGNO (val) < reg_base_value_size)
{
reg_base_value[regno] = reg_base_value[REGNO (val)];
}
MEM_VOLATILE_P (new) = MEM_VOLATILE_P (x);
RTX_UNCHANGING_P (new) = RTX_UNCHANGING_P (x);
MEM_IN_STRUCT_P (new) = MEM_IN_STRUCT_P (x);
+ MEM_ALIAS_SET (new) = MEM_ALIAS_SET (x);
x = new;
}
}
objects, 1 if they might be pointers to the same object. */
static int
-base_alias_check (x, y)
+base_alias_check (x, y, x_mode, y_mode)
rtx x, y;
+ enum machine_mode x_mode, y_mode;
{
rtx x_base = find_base_term (x);
rtx y_base = find_base_term (y);
if (rtx_equal_p (x_base, y_base))
return 1;
- /* The base addresses of the read and write are different
- expressions. If they are both symbols and they are not accessed
- via AND, there is no conflict. */
- /* XXX: We can bring knowledge of object alignment and offset into
- play here. For example, on alpha, "char a, b;" can alias one
- another, though "char a; long b;" cannot. Similarly, offsets
- into strutures may be brought into play. Given "char a, b[40];",
- a and b[1] may overlap, but a and b[20] do not. */
+ /* The base addresses of the read and write are different expressions.
+ If they are both symbols and they are not accessed via AND, there is
+ no conflict. We can bring knowledge of object alignment into play
+ here. For example, on alpha, "char a, b;" can alias one another,
+ though "char a; long b;" cannot. */
if (GET_CODE (x_base) != ADDRESS && GET_CODE (y_base) != ADDRESS)
{
- return GET_CODE (x) == AND || GET_CODE (y) == AND;
+ if (GET_CODE (x) == AND && GET_CODE (y) == AND)
+ return 1;
+ if (GET_CODE (x) == AND
+ && (GET_CODE (XEXP (x, 1)) != CONST_INT
+ || GET_MODE_UNIT_SIZE (y_mode) < -INTVAL (XEXP (x, 1))))
+ return 1;
+ if (GET_CODE (y) == AND
+ && (GET_CODE (XEXP (y, 1)) != CONST_INT
+ || GET_MODE_UNIT_SIZE (x_mode) < -INTVAL (XEXP (y, 1))))
+ return 1;
}
/* If one address is a stack reference there can be no alias:
if (rtx_equal_for_memref_p (x0, y0))
return memrefs_conflict_p (xsize, x1, ysize, y1, c);
if (GET_CODE (x1) == CONST_INT)
- if (GET_CODE (y1) == CONST_INT)
- return memrefs_conflict_p (xsize, x0, ysize, y0,
- c - INTVAL (x1) + INTVAL (y1));
- else
- return memrefs_conflict_p (xsize, x0, ysize, y, c - INTVAL (x1));
+ {
+ if (GET_CODE (y1) == CONST_INT)
+ return memrefs_conflict_p (xsize, x0, ysize, y0,
+ c - INTVAL (x1) + INTVAL (y1));
+ else
+ return memrefs_conflict_p (xsize, x0, ysize, y,
+ c - INTVAL (x1));
+ }
else if (GET_CODE (y1) == CONST_INT)
return memrefs_conflict_p (xsize, x, ysize, y0, c + INTVAL (y1));
/* Are these registers known not to be equal? */
if (alias_invariant)
{
- int r_x = REGNO (x), r_y = REGNO (y);
+ 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];
}
/* Treat an access through an AND (e.g. a subword access on an Alpha)
- as an access with indeterminate size.
- ??? Could instead convert an n byte reference at (and x y) to an
- n-y byte reference at (plus x y). */
+ as an access with indeterminate size. Assume that references
+ besides AND are aligned, so if the size of the other reference is
+ at least as large as the alignment, assume no other overlap. */
if (GET_CODE (x) == AND && GET_CODE (XEXP (x, 1)) == CONST_INT)
- return memrefs_conflict_p (-1, XEXP (x, 0), ysize, y, c);
+ {
+ if (ysize < -INTVAL (XEXP (x, 1)))
+ xsize = -1;
+ return memrefs_conflict_p (xsize, XEXP (x, 0), ysize, y, c);
+ }
if (GET_CODE (y) == AND && GET_CODE (XEXP (y, 1)) == CONST_INT)
{
- /* XXX: If we are indexing far enough into the array/structure, we
+ /* ??? If we are indexing far enough into the array/structure, we
may yet be able to determine that we can not overlap. But we
also need to that we are far enough from the end not to overlap
- a following reference, so we do nothing for now. */
- return memrefs_conflict_p (xsize, x, -1, XEXP (y, 0), c);
+ a following reference, so we do nothing with that for now. */
+ if (xsize < -INTVAL (XEXP (y, 1)))
+ ysize = -1;
+ return memrefs_conflict_p (xsize, x, ysize, XEXP (y, 0), c);
}
if (CONSTANT_P (x))
if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
return 1;
+ if (DIFFERENT_ALIAS_SETS_P (x, mem))
+ return 0;
+
/* If X is an unchanging read, then it can't possibly conflict with any
non-unchanging store. It may conflict with an unchanging write though,
because there may be a single store to this address to initialize it.
if (RTX_UNCHANGING_P (x) && ! RTX_UNCHANGING_P (mem))
return 0;
- if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0)))
+ if (mem_mode == VOIDmode)
+ mem_mode = GET_MODE (mem);
+
+ if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0), GET_MODE (x), mem_mode))
return 0;
x_addr = canon_rtx (XEXP (x, 0));
mem_addr = canon_rtx (XEXP (mem, 0));
- if (mem_mode == VOIDmode)
- mem_mode = GET_MODE (mem);
-
if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
SIZE_FOR_MODE (x), x_addr, 0))
return 0;
if (RTX_UNCHANGING_P (mem))
return 0;
- if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0)))
+ if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0), GET_MODE (x),
+ GET_MODE (mem)))
return 0;
x = canon_rtx (x);
mem = canon_rtx (mem);
+ if (DIFFERENT_ALIAS_SETS_P (x, mem))
+ return 0;
+
x_addr = XEXP (x, 0);
mem_addr = XEXP (mem, 0);
if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
return 1;
- if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0)))
+ if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0), GET_MODE (x),
+ GET_MODE (mem)))
return 0;
x = canon_rtx (x);
mem = canon_rtx (mem);
+ if (DIFFERENT_ALIAS_SETS_P (x, mem))
+ return 0;
+
return (memrefs_conflict_p (SIZE_FOR_MODE (mem), XEXP (mem, 0),
SIZE_FOR_MODE (x), XEXP (x, 0), 0)
&& ! (MEM_IN_STRUCT_P (mem) && rtx_addr_varies_p (mem)
if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i))
&& HARD_REGNO_MODE_OK (i, Pmode))
SET_HARD_REG_BIT (argument_registers, i);
+
+ alias_sets = splay_tree_new (&alias_set_compare, 0, 0);
}
void
int maxreg = max_reg_num ();
int changed, pass;
register int i;
+ register unsigned int ui;
register rtx insn;
reg_known_value_size = maxreg;
}
/* Now propagate values from new_reg_base_value to reg_base_value. */
- for (i = 0; i < reg_base_value_size; i++)
+ for (ui = 0; ui < reg_base_value_size; ui++)
{
- if (new_reg_base_value[i]
- && new_reg_base_value[i] != reg_base_value[i]
- && ! rtx_equal_p (new_reg_base_value[i], reg_base_value[i]))
+ 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]))
{
- reg_base_value[i] = new_reg_base_value[i];
+ reg_base_value[ui] = new_reg_base_value[ui];
changed = 1;
}
}
{
changed = 0;
pass++;
- for (i = 0; i < reg_base_value_size; i++)
+ for (ui = 0; ui < reg_base_value_size; ui++)
{
- rtx base = reg_base_value[i];
+ rtx base = reg_base_value[ui];
if (base && GET_CODE (base) == REG)
{
- int base_regno = REGNO (base);
- if (base_regno == i) /* register set from itself */
- reg_base_value[i] = 0;
+ unsigned int base_regno = REGNO (base);
+ if (base_regno == ui) /* register set from itself */
+ reg_base_value[ui] = 0;
else
- reg_base_value[i] = reg_base_value[base_regno];
+ reg_base_value[ui] = reg_base_value[base_regno];
changed = 1;
}
}
OSDN Git Service
