This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
alias stuff
- To: jfc at mit dot edu
- Subject: alias stuff
- From: Jeffrey A Law <law at cygnus dot com>
- Date: Sun, 26 Oct 1997 22:45:21 -0700
- Cc: egcs at cygnus dot com
- Reply-To: law at cygnus dot com
I went ahead and finished the improved propagation scheme I
mentioned in an earlier message.
It eliminates the need to peek at REG_N_SETS, but does not
remove the need to improve how find_base_value handles PLUS.
As I mentioned in the earlier, the basic theory is to keep two
arrays of base values and propage info from one array into the other.
One array contains the known constant base values, the other contains
potential base values. After each pass over the insns, any new
potential base values move into the constant base values array
and the process repeats until no new information propages into
the known constant base value array.
When passed a REG, find_base_value will return the known constant
base value if one exists. This results in base values propaging
through chains of sets better than the old code.
When passed a PLUS, find_base_value will recursively call itself
for either operand of the PLUS if it is a REG. This allows us to
propagate base value information through PLUS expressions when
one of the operands is a register that is not strictly a pointer.
The basic loop to walk over the insns didn't change -- it just got moved
inside the outer loop and had to be reindented.
I have not checked in this code -- I'd really appreciate any feedback
you could provide.
* alias.c (new_reg_base_value): New array of potential base values.
(unique_id): Now file scoped static.
(find_base_value, case REG): Return the value in reg_base_value
array for the REG if it exists. Else, return the value from
new_reg_base_value if copying args and REG is a hard register.
(find_base_value, case PLUS): If either operand of the PLUS is
a REG, try to get its base value. Handle base + index and
index + base.
(record_set): Use new_reg_base_value instead of reg_base_value.
(init_alias_analysis): Allocate space for new_reg_base_value too.
Rework code to iterate over the insns propagating base value
information until nothing changes.
Index: alias.c
===================================================================
RCS file: /cvs/cvsfiles/egcs/gcc/alias.c,v
retrieving revision 1.13
diff -c -3 -p -r1.13 alias.c
*** alias.c 1997/10/26 20:25:38 1.13
--- alias.c 1997/10/27 05:38:29
*************** static int memrefs_conflict_p PROTO((in
*** 52,57 ****
--- 52,58 ----
other special value. */
rtx *reg_base_value;
+ 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)
*************** find_base_value (src)
*** 94,105 ****
return src;
case REG:
/* At the start of a function argument registers have known base
values which may be lost later. Returning an ADDRESS
expression here allows optimization based on argument values
even when the argument registers are used for other purposes. */
if (REGNO (src) < FIRST_PSEUDO_REGISTER && copying_arguments)
! return reg_base_value[REGNO (src)];
return src;
case MEM:
--- 95,110 ----
return src;
case REG:
+ /* If this REG is related to a known base value, return it. */
+ if (reg_base_value[REGNO (src)])
+ return reg_base_value[REGNO (src)];
+
/* At the start of a function argument registers have known base
values which may be lost later. Returning an ADDRESS
expression here allows optimization based on argument values
even when the argument registers are used for other purposes. */
if (REGNO (src) < FIRST_PSEUDO_REGISTER && copying_arguments)
! return new_reg_base_value[REGNO (src)];
return src;
case MEM:
*************** find_base_value (src)
*** 122,135 ****
case PLUS:
case MINUS:
{
! rtx src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
/* Guess which operand is the base address.
! If the first operand is a symbol or the second operand is
! an integer, the first operand is the base address. Else if
! either operand is a register marked as a pointer, it is the
! base address. */
if (GET_CODE (src_1) == CONST_INT
|| GET_CODE (src_0) == SYMBOL_REF
--- 127,154 ----
case PLUS:
case MINUS:
{
! rtx temp, src_0 = XEXP (src, 0), src_1 = XEXP (src, 1);
!
! /* If either operand is a REG, then see if we already have
! a known value for it. */
! if (GET_CODE (src_0) == REG)
! {
! temp = find_base_value (src_0);
! if (temp)
! src_0 = temp;
! }
!
! if (GET_CODE (src_1) == REG)
! {
! temp = find_base_value (src_1);
! if (temp)
! src_1 = temp;
! }
/* Guess which operand is the base address.
! If either operand is a symbol, then it is the base. If
! either operand is a CONST_INT, then the other is the base. */
if (GET_CODE (src_1) == CONST_INT
|| GET_CODE (src_0) == SYMBOL_REF
*************** find_base_value (src)
*** 137,142 ****
--- 156,171 ----
|| GET_CODE (src_0) == CONST)
return find_base_value (src_0);
+ if (GET_CODE (src_0) == CONST_INT
+ || GET_CODE (src_1) == SYMBOL_REF
+ || GET_CODE (src_1) == LABEL_REF
+ || GET_CODE (src_1) == CONST)
+ return find_base_value (src_1);
+
+ /* This might not be necessary anymore.
+
+ If either operand is a REG that is a known pointer, then it
+ is the base. */
if (GET_CODE (src_0) == REG && REGNO_POINTER_FLAG (REGNO (src_0)))
return find_base_value (src_0);
*************** find_base_value (src)
*** 171,176 ****
--- 200,208 ----
register N has been set in this function. */
static char *reg_seen;
+ /* */
+ static int unique_id;
+
static void
record_set (dest, set)
rtx dest, set;
*************** record_set (dest, set)
*** 190,210 ****
set). */
if (GET_CODE (set) == CLOBBER)
{
! reg_base_value[regno] = 0;
return;
}
src = SET_SRC (set);
}
else
{
- static int unique_id;
if (reg_seen[regno])
{
! reg_base_value[regno] = 0;
return;
}
reg_seen[regno] = 1;
! reg_base_value[regno] = gen_rtx (ADDRESS, Pmode,
GEN_INT (unique_id++));
return;
}
--- 222,241 ----
set). */
if (GET_CODE (set) == CLOBBER)
{
! new_reg_base_value[regno] = 0;
return;
}
src = SET_SRC (set);
}
else
{
if (reg_seen[regno])
{
! new_reg_base_value[regno] = 0;
return;
}
reg_seen[regno] = 1;
! new_reg_base_value[regno] = gen_rtx (ADDRESS, Pmode,
GEN_INT (unique_id++));
return;
}
*************** record_set (dest, set)
*** 215,241 ****
extern int x, y; int *p = &x; p += (&y-&x);
ANSI C does not allow computing the difference of addresses
of distinct top level objects. */
! if (reg_base_value[regno])
switch (GET_CODE (src))
{
case LO_SUM:
case PLUS:
case MINUS:
if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
! reg_base_value[regno] = 0;
break;
case AND:
if (XEXP (src, 0) != dest || GET_CODE (XEXP (src, 1)) != CONST_INT)
! reg_base_value[regno] = 0;
break;
default:
! reg_base_value[regno] = 0;
break;
}
/* If this is the first set of a register, record the value. */
else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
! && ! reg_seen[regno] && reg_base_value[regno] == 0)
! reg_base_value[regno] = find_base_value (src);
reg_seen[regno] = 1;
}
--- 246,272 ----
extern int x, y; int *p = &x; p += (&y-&x);
ANSI C does not allow computing the difference of addresses
of distinct top level objects. */
! if (new_reg_base_value[regno])
switch (GET_CODE (src))
{
case LO_SUM:
case PLUS:
case MINUS:
if (XEXP (src, 0) != dest && XEXP (src, 1) != dest)
! new_reg_base_value[regno] = 0;
break;
case AND:
if (XEXP (src, 0) != dest || GET_CODE (XEXP (src, 1)) != CONST_INT)
! new_reg_base_value[regno] = 0;
break;
default:
! new_reg_base_value[regno] = 0;
break;
}
/* If this is the first set of a register, record the value. */
else if ((regno >= FIRST_PSEUDO_REGISTER || ! fixed_regs[regno])
! && ! reg_seen[regno] && new_reg_base_value[regno] == 0)
! new_reg_base_value[regno] = find_base_value (src);
reg_seen[regno] = 1;
}
*************** init_alias_analysis ()
*** 949,957 ****
registers. */
reg_base_value_size = maxreg * 2;
reg_base_value = (rtx *)oballoc (reg_base_value_size * sizeof (rtx));
reg_seen = (char *)alloca (reg_base_value_size);
bzero ((char *) reg_base_value, reg_base_value_size * sizeof (rtx));
! bzero (reg_seen, reg_base_value_size);
/* Mark all hard registers which may contain an address.
The stack, frame and argument pointers may contain an address.
--- 980,1020 ----
registers. */
reg_base_value_size = maxreg * 2;
reg_base_value = (rtx *)oballoc (reg_base_value_size * sizeof (rtx));
+ new_reg_base_value = (rtx *)alloca (reg_base_value_size * sizeof (rtx));
reg_seen = (char *)alloca (reg_base_value_size);
bzero ((char *) reg_base_value, reg_base_value_size * sizeof (rtx));
! }
!
! /* The basic idea is that each pass through this loop will use the
! "constant" information from the previous pass to propagate alias
! information through another level of assignments.
!
! This could get expensive if the assignment chains are long. Maybe
! we should throttle the number of iterations, possibly based on
! the optimization level.
!
! We could propagate more information in the first pass by making use
! of REG_N_SETS to determine immediately that the alias information
! for a pseudo is "constant". */
! changed = 1;
! while (changed)
! {
! /* Assume nothing will change this iteration of the loop. */
! changed = 0;
!
! /* Wipe the potential alias information clean for this pass. */
! bzero ((char *) new_reg_base_value, reg_base_value_size * sizeof (rtx));
!
! /* Wipe the reg_seen array clean. */
! bzero ((char *) reg_seen, reg_base_value_size);
!
! /* We want to assign the same IDs each iteration of this loop, so
! start counting from zero each iteration of the loop. */
! unique_id = 0;
!
! /* We're at the start of the funtion each iteration through the
! loop, so we're copying arguments. */
! copying_arguments = 1;
/* Mark all hard registers which may contain an address.
The stack, frame and argument pointers may contain an address.
*************** init_alias_analysis ()
*** 968,1019 ****
argument. FUNCTION_ARG_REGNO_P tests outgoing register
numbers, so translate if necessary due to register windows. */
if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i)) && HARD_REGNO_MODE_OK (i, Pmode))
! reg_base_value[i] = gen_rtx (ADDRESS, VOIDmode,
! gen_rtx (REG, Pmode, i));
! reg_base_value[STACK_POINTER_REGNUM]
= gen_rtx (ADDRESS, Pmode, stack_pointer_rtx);
! reg_base_value[ARG_POINTER_REGNUM]
= gen_rtx (ADDRESS, Pmode, arg_pointer_rtx);
! reg_base_value[FRAME_POINTER_REGNUM]
= gen_rtx (ADDRESS, Pmode, frame_pointer_rtx);
#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
! reg_base_value[HARD_FRAME_POINTER_REGNUM]
= gen_rtx (ADDRESS, Pmode, hard_frame_pointer_rtx);
#endif
- }
! copying_arguments = 1;
! /* Fill in the entries with known constant values. */
! for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
! {
! if (flag_alias_check && GET_RTX_CLASS (GET_CODE (insn)) == 'i')
! {
! /* 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. */
! rtx noalias_note;
! if (GET_CODE (PATTERN (insn)) == SET
! && (noalias_note = find_reg_note (insn, REG_NOALIAS, NULL_RTX)))
! record_set (SET_DEST (PATTERN (insn)), 0);
! else
! note_stores (PATTERN (insn), record_set);
}
! else if (GET_CODE (insn) == NOTE
! && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
! copying_arguments = 0;
!
! if ((set = single_set (insn)) != 0
! && GET_CODE (SET_DEST (set)) == REG
! && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
! && (((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)
! && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
! {
! int regno = REGNO (SET_DEST (set));
! reg_known_value[regno] = XEXP (note, 0);
! reg_known_equiv_p[regno] = REG_NOTE_KIND (note) == REG_EQUIV;
}
}
--- 1031,1094 ----
argument. FUNCTION_ARG_REGNO_P tests outgoing register
numbers, so translate if necessary due to register windows. */
if (FUNCTION_ARG_REGNO_P (OUTGOING_REGNO (i)) && HARD_REGNO_MODE_OK (i, Pmode))
! new_reg_base_value[i] = gen_rtx (ADDRESS, VOIDmode,
! gen_rtx (REG, Pmode, i));
! new_reg_base_value[STACK_POINTER_REGNUM]
= gen_rtx (ADDRESS, Pmode, stack_pointer_rtx);
! new_reg_base_value[ARG_POINTER_REGNUM]
= gen_rtx (ADDRESS, Pmode, arg_pointer_rtx);
! new_reg_base_value[FRAME_POINTER_REGNUM]
= gen_rtx (ADDRESS, Pmode, frame_pointer_rtx);
#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
! new_reg_base_value[HARD_FRAME_POINTER_REGNUM]
= gen_rtx (ADDRESS, Pmode, hard_frame_pointer_rtx);
#endif
! /* Walk the insns adding values to the new_reg_base_value array. */
! for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
! {
! if (flag_alias_check && GET_RTX_CLASS (GET_CODE (insn)) == 'i')
! {
! /* 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. */
! rtx noalias_note;
! if (GET_CODE (PATTERN (insn)) == SET
! && (noalias_note = find_reg_note (insn,
! REG_NOALIAS, NULL_RTX)))
! record_set (SET_DEST (PATTERN (insn)), 0);
! else
! note_stores (PATTERN (insn), record_set);
! }
! else if (GET_CODE (insn) == NOTE
! && NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
! copying_arguments = 0;
!
! if ((set = single_set (insn)) != 0
! && GET_CODE (SET_DEST (set)) == REG
! && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
! && (((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)
! && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
! {
! int regno = REGNO (SET_DEST (set));
! reg_known_value[regno] = XEXP (note, 0);
! reg_known_equiv_p[regno] = REG_NOTE_KIND (note) == REG_EQUIV;
! }
}
!
! /* Now propagate values from new_reg_base_value to reg_base_value. */
! for (i = 0; i < reg_base_value_size; i++)
! {
! 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]))
! {
! reg_base_value[i] = new_reg_base_value[i];
! changed = 1;
! }
}
}
*************** init_alias_analysis ()
*** 1051,1056 ****
--- 1126,1132 ----
}
while (changed);
+ new_reg_base_value = 0;
reg_seen = 0;
}