/* Alias analysis for GNU C
- Copyright (C) 1997, 1998, 1999 Free Software Foundation, Inc.
+ Copyright (C) 1997, 1998, 1999, 2000 Free Software Foundation, Inc.
Contributed by John Carr (jfc@mit.edu).
This file is part of GNU CC.
#include "flags.h"
#include "output.h"
#include "toplev.h"
+#include "cselib.h"
#include "splay-tree.h"
#include "ggc.h"
splay_tree children;
} *alias_set_entry;
-static rtx canon_rtx PROTO((rtx));
-static int rtx_equal_for_memref_p PROTO((rtx, rtx));
-static rtx find_symbolic_term PROTO((rtx));
-static int memrefs_conflict_p PROTO((int, rtx, int, rtx,
- HOST_WIDE_INT));
-static void record_set PROTO((rtx, rtx, void *));
-static rtx find_base_term PROTO((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 insert_subset_children PROTO((splay_tree_node,
- void*));
-static alias_set_entry get_alias_set_entry PROTO((int));
-static rtx fixed_scalar_and_varying_struct_p PROTO((rtx, rtx, int (*)(rtx)));
-static int aliases_everything_p PROTO((rtx));
-static int write_dependence_p PROTO((rtx, rtx, int));
-static int nonlocal_reference_p PROTO((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 int memrefs_conflict_p PARAMS ((int, rtx, int, rtx,
+ HOST_WIDE_INT));
+static void record_set PARAMS ((rtx, rtx, void *));
+static rtx find_base_term PARAMS ((rtx));
+static int base_alias_check PARAMS ((rtx, rtx, enum machine_mode,
+ enum machine_mode));
+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 rtx fixed_scalar_and_varying_struct_p PARAMS ((rtx, rtx, rtx, 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));
/* Set up all info needed to perform alias analysis on memory references. */
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. */
-static int reg_known_value_size;
+static unsigned int reg_known_value_size;
/* Vector recording for each reg_known_value whether it is due to a
REG_EQUIV note. Future passes (viz., reload) may replace the
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;
{
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. */
find_base_term (x)
register rtx x;
{
+ cselib_val *val;
+ struct elt_loc_list *l;
+
switch (GET_CODE (x))
{
case REG:
case POST_DEC:
return find_base_term (XEXP (x, 0));
+ case VALUE:
+ val = CSELIB_VAL_PTR (x);
+ for (l = val->locs; l; l = l->next)
+ if ((x = find_base_term (l->loc)) != 0)
+ return x;
+ return 0;
+
case CONST:
x = XEXP (x, 0);
if (GET_CODE (x) != PLUS && GET_CODE (x) != MINUS)
return ! (GET_MODE (x_base) == VOIDmode && GET_MODE (y_base) == VOIDmode);
}
+/* 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;
+{
+ cselib_val *v;
+ struct elt_loc_list *l;
+
+ 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;
+ return x;
+}
+
/* Return the address of the (N_REFS + 1)th memory reference to ADDR
where SIZE is the size in bytes of the memory reference. If ADDR
is not modified by the memory reference then ADDR is returned. */
Nice to notice that varying addresses cannot conflict with fp if no
local variables had their addresses taken, but that's too hard now. */
-
static int
memrefs_conflict_p (xsize, x, ysize, y, c)
register rtx x, y;
int xsize, ysize;
HOST_WIDE_INT c;
{
+ if (GET_CODE (x) == VALUE)
+ x = get_addr (x);
+ if (GET_CODE (y) == VALUE)
+ y = get_addr (y);
if (GET_CODE (x) == HIGH)
x = XEXP (x, 0);
else if (GET_CODE (x) == LO_SUM)
MEM2 if vice versa. Otherwise, returns NULL_RTX. If a non-NULL
value is returned MEM1 and MEM2 can never alias. VARIES_P is used
to decide whether or not an address may vary; it should return
- nozero whenever variation is possible. */
-
-static rtx
-fixed_scalar_and_varying_struct_p (mem1, mem2, varies_p)
- rtx mem1;
- rtx mem2;
- int (*varies_p) PROTO((rtx));
-{
- rtx mem1_addr = XEXP (mem1, 0);
- rtx mem2_addr = XEXP (mem2, 0);
+ nonzero whenever variation is possible.
+ MEM1_ADDR and MEM2_ADDR are the addresses of MEM1 and MEM2. */
+static rtx
+fixed_scalar_and_varying_struct_p (mem1, mem2, mem1_addr, mem2_addr, varies_p)
+ rtx mem1, mem2;
+ rtx mem1_addr, mem2_addr;
+ int (*varies_p) PARAMS ((rtx));
+{
if (MEM_SCALAR_P (mem1) && MEM_IN_STRUCT_P (mem2)
&& !varies_p (mem1_addr) && varies_p (mem2_addr))
/* MEM1 is a scalar at a fixed address; MEM2 is a struct at a
rtx mem;
enum machine_mode mem_mode;
rtx x;
- int (*varies) PROTO((rtx));
+ int (*varies) PARAMS ((rtx));
{
register rtx x_addr, mem_addr;
if (mem_mode == VOIDmode)
mem_mode = GET_MODE (mem);
- if (! base_alias_check (XEXP (x, 0), XEXP (mem, 0), GET_MODE (x), mem_mode))
+ x_addr = get_addr (XEXP (x, 0));
+ mem_addr = get_addr (XEXP (mem, 0));
+
+ if (! base_alias_check (x_addr, mem_addr, GET_MODE (x), mem_mode))
return 0;
- x_addr = canon_rtx (XEXP (x, 0));
- mem_addr = canon_rtx (XEXP (mem, 0));
+ x_addr = canon_rtx (x_addr);
+ mem_addr = canon_rtx (mem_addr);
if (! memrefs_conflict_p (GET_MODE_SIZE (mem_mode), mem_addr,
SIZE_FOR_MODE (x), x_addr, 0))
if (mem_mode == BLKmode || GET_MODE (x) == BLKmode)
return 1;
- return !fixed_scalar_and_varying_struct_p (mem, x, varies);
+ return ! fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
+ varies);
}
/* Returns non-zero if a write to X might alias a previous read from
if (MEM_VOLATILE_P (x) && MEM_VOLATILE_P (mem))
return 1;
+ if (DIFFERENT_ALIAS_SETS_P (x, mem))
+ return 0;
+
/* If MEM is an unchanging read, then it can't possibly conflict with
the store to X, because there is at most one store to MEM, and it must
have occurred somewhere before MEM. */
if (!writep && RTX_UNCHANGING_P (mem))
return 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);
+ x_addr = get_addr (XEXP (x, 0));
+ mem_addr = get_addr (XEXP (mem, 0));
- if (DIFFERENT_ALIAS_SETS_P (x, mem))
+ if (! base_alias_check (x_addr, mem_addr, GET_MODE (x),
+ GET_MODE (mem)))
return 0;
- x_addr = XEXP (x, 0);
- mem_addr = XEXP (mem, 0);
+ x_addr = canon_rtx (x_addr);
+ mem_addr = canon_rtx (mem_addr);
if (!memrefs_conflict_p (SIZE_FOR_MODE (mem), mem_addr,
SIZE_FOR_MODE (x), x_addr, 0))
return 0;
fixed_scalar
- = fixed_scalar_and_varying_struct_p (mem, x, rtx_addr_varies_p);
-
+ = fixed_scalar_and_varying_struct_p (mem, x, mem_addr, x_addr,
+ rtx_addr_varies_p);
+
return (!(fixed_scalar == mem && !aliases_everything_p (x))
&& !(fixed_scalar == x && !aliases_everything_p (mem)));
}
if (nonlocal_reference_p (XEXP (x, i)))
return 1;
}
- if (fmt[i] == 'E')
+ else if (fmt[i] == 'E')
{
register int j;
for (j = 0; j < XVECLEN (x, i); j++)
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 ()
{