Hi,
I'mm currently looking at the dataflow branch for m68k mainly because of
the new auto-inc-dec pass, I worked a bit on the old code in flow.c, but
considering the new pass, I think it doesn't make much sense to continue
it.
I'm attaching my current patch and some test cases, but before delving
deeper into the code, I have a few questions and I'd like to hear some
opinions. Currently I only looked at the output and it misses some
opportunities (not that my patch can do everything either :) ).
One case is about multiple increments, the tree optimizer merges them and
increments the register only once, so if one only looks at the size of the
pointer value one misses them, e.g. something like this:
(set (mem (reg)) (x))
(set (mem (plus (reg) (const_int 4))) (x))
(set (reg) (plus (reg) (const_int 8))
Another case are multiple uses of the register within an instruction, the
old code didn't do this at all, the new code seems to do a bit better, but
there as a rather tricky case I looked into, e.g.
(set (mem) (plus (mem) (reg)))
could be turned into:
(set (post_inc (mem)) (plus (mem) (reg)))
or
(set (mem) (plus (pre_dec (mem)) (reg)))
This is at least what operands_match_p() accepts, but hasn't been
generated in a long time and has the potential to trigger bugs in the
back end (e.g. m68k only looks only at one of the operands).
A question would be now if there is a general interest in reactivating
this, so gcc could generate a instruction like "add.l %d0,(%a0)+" for
m68k.
The more general question is whether someone is already working on further
improvements, so I won't duplicate anything (which wouldn't be before I
looked into the remaining m68k dataflow problems anyway. :) ).
The dataflow porting document mentions other possible, but doesn't mention
any examples. Anything I might have to look out for regardings the m68k
post_inc/pre_dec addressing modes?
bye, Romanvoid f1(int *p, int i)
{
*--p = i;
}
int f1b(int *p, int i)
{
return *--p;
}
void f2(int *p, int i)
{
*--p = i++;
*--p = i;
}
int *f3(int *p, int i)
{
*p++ = i;
return p;
}
int *f4(int *p, int i)
{
*p++ = 1;
*p++ = 2;
return p;
}
int *f5(int *p, int i)
{
*p++ = i++;
*p++ = i;
return p;
}
void f6(int *p, int i)
{
while (--i) {
*p++ = 1;
*p++ = 2;
}
}
void f7(int *p, int i)
{
while (--i) {
*--p = 1;
*--p = 2;
}
}
void f8(int *p, int i)
{
*p++ = 1;
*p = 2;
}
void f9(int *p, int i)
{
*p++ += 1;
*p = 2;
}
void f10(int *p, int i)
{
*p++ = 1;
*p += 2;
}
---
gcc/flow.c | 350 ++++++++++++++++++++++++++++++++++++++-----------------------
1 file changed, 219 insertions(+), 131 deletions(-)
Index: gcc/gcc/flow.c
===================================================================
--- gcc.orig/gcc/flow.c
+++ gcc/gcc/flow.c
@@ -314,8 +314,9 @@ static rtx not_reg_cond (rtx);
static rtx and_reg_cond (rtx, rtx, int);
#endif
#ifdef AUTO_INC_DEC
-static void attempt_auto_inc (struct propagate_block_info *, rtx, rtx, rtx,
- rtx, rtx);
+struct inc_data;
+static void attempt_auto_inc (struct propagate_block_info *pbi, rtx insn,
+ rtx mem, struct inc_data *inc);
static void find_auto_inc (struct propagate_block_info *, rtx, rtx);
static int try_pre_increment_1 (struct propagate_block_info *, rtx);
static int try_pre_increment (rtx, rtx, HOST_WIDE_INT);
@@ -1802,7 +1803,7 @@ propagate_one_insn (struct propagate_blo
&& REG_P (SET_DEST (x))
&& (GET_CODE (SET_SRC (x)) == PLUS
|| GET_CODE (SET_SRC (x)) == MINUS)
- && XEXP (SET_SRC (x), 0) == SET_DEST (x)
+ && REG_P (XEXP (SET_SRC (x), 0))
&& GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
/* Ok, look for a following memory ref we can combine with.
If one is found, change the memory ref to a PRE_INC
@@ -3488,6 +3489,53 @@ elim_reg_cond (rtx x, unsigned int regno
#ifdef AUTO_INC_DEC
+struct inc_data
+{
+ rtx incr;
+ rtx reg;
+ unsigned int regno;
+ HOST_WIDE_INT offset;
+ rtx inc;
+
+ rtx *inc_loc;
+ rtx inc_val;
+ rtx inc_dest;
+ rtx *reg_dest;
+};
+
+static int
+find_inc_1 (rtx *x, void *data)
+{
+ struct inc_data *inc = data;
+
+ if (!*x)
+ return 0;
+ if (GET_CODE (*x) == PLUS)
+ {
+ if (inc->inc_loc)
+ return 0;
+ if (REG_P (XEXP (*x, 0)) && REGNO (XEXP (*x, 0)) == inc->regno)
+ inc->inc_val = XEXP (*x, 1);
+ else if (REG_P (XEXP (*x, 1)) && REGNO (XEXP (*x, 1)) == inc->regno)
+ inc->inc_val = XEXP (*x, 0);
+ else
+ return 0;
+ inc->inc_loc = x;
+ return -1;
+ }
+ if (GET_CODE (*x) == EXPR_LIST)
+ return -1;
+ if (REG_P (*x) && REGNO (*x) == inc->regno && x != inc->reg_dest)
+ return 1;
+ if (GET_CODE (*x) == SET)
+ {
+ rtx *y = &SET_DEST (*x);
+ if (REG_P (*y) && REGNO (*y) == inc->regno)
+ inc->reg_dest = y;
+ }
+ return 0;
+}
+
/* Try to substitute the auto-inc expression INC as the address inside
MEM which occurs in INSN. Currently, the address of MEM is an expression
involving INCR_REG, and INCR is the next use of INCR_REG; it is an insn
@@ -3495,49 +3543,55 @@ elim_reg_cond (rtx x, unsigned int regno
else. */
static void
-attempt_auto_inc (struct propagate_block_info *pbi, rtx inc, rtx insn,
- rtx mem, rtx incr, rtx incr_reg)
+attempt_auto_inc (struct propagate_block_info *pbi, rtx insn,
+ rtx mem, struct inc_data *inc)
{
- int regno = REGNO (incr_reg);
- rtx set = single_set (incr);
- rtx q = SET_DEST (set);
- rtx y = SET_SRC (set);
- int opnum = XEXP (y, 0) == incr_reg ? 0 : 1;
+ rtx insns = NULL_RTX;
int changed;
/* Make sure this reg appears only once in this insn. */
- if (count_occurrences (PATTERN (insn), incr_reg, 1) != 1)
+ if (count_occurrences (PATTERN (insn), inc->reg, 1) != 1)
return;
- if (dead_or_set_p (incr, incr_reg)
+ if (dead_or_set_p (inc->incr, inc->reg)
/* Mustn't autoinc an eliminable register. */
- && (regno >= FIRST_PSEUDO_REGISTER
- || ! TEST_HARD_REG_BIT (elim_reg_set, regno)))
+ && (inc->regno >= FIRST_PSEUDO_REGISTER
+ || !TEST_HARD_REG_BIT (elim_reg_set, inc->regno)))
{
/* This is the simple case. Try to make the auto-inc. If
we can't, we are done. Otherwise, we will do any
needed updates below. */
- if (! validate_change (insn, &XEXP (mem, 0), inc, 0))
+ if (! validate_change (insn, &XEXP (mem, 0), inc->inc, 0))
return;
+
+ if (inc->offset)
+ {
+ start_sequence ();
+ emit_move_insn (inc->reg, plus_constant (inc->reg, inc->offset));
+ insns = get_insns ();
+ end_sequence ();
+ }
}
- else if (REG_P (q)
+ else if (inc->inc_dest
/* PREV_INSN used here to check the semi-open interval
[insn,incr). */
- && ! reg_used_between_p (q, PREV_INSN (insn), incr)
- /* We must also check for sets of q as q may be
+ && ! reg_used_between_p (inc->inc_dest, PREV_INSN (insn), inc->incr)
+ /* We must also check for sets of inc_dest as inc_dest may be
a call clobbered hard register and there may
be a call between PREV_INSN (insn) and incr. */
- && ! reg_set_between_p (q, PREV_INSN (insn), incr))
+ && ! reg_set_between_p (inc->inc_dest, PREV_INSN (insn), inc->incr))
{
- /* We have *p followed sometime later by q = p+size.
- Both p and q must be live afterward,
- and q is not used between INSN and its assignment.
- Change it to q = p, ...*q..., q = q+size.
+ /* We have *p followed sometime later by inc_dest = p+size.
+ Both p and inc_dest must be live afterward,
+ and inc_dest is not used between INSN and its assignment.
+ Change it to inc_dest = p, ...*inc_dest..., inc_dest = inc_dest+size.
Then fall into the usual case. */
- rtx insns, temp;
+ rtx temp;
+ rtx y = *inc->inc_loc;
+ int opnum = XEXP (y, 0) == inc->reg ? 0 : 1;
start_sequence ();
- emit_move_insn (q, incr_reg);
+ emit_move_insn (inc->inc_dest, plus_constant (inc->reg, inc->offset));
insns = get_insns ();
end_sequence ();
@@ -3546,55 +3600,41 @@ attempt_auto_inc (struct propagate_block
the change below if we can't do the auto-inc and doing
so is not correct in the pre-inc case. */
- XEXP (inc, 0) = q;
- validate_change (insn, &XEXP (mem, 0), inc, 1);
- validate_change (incr, &XEXP (y, opnum), q, 1);
+ XEXP (inc->inc, 0) = inc->inc_dest;
+ validate_change (insn, &XEXP (mem, 0), inc->inc, 1);
+ validate_change (inc->incr, &XEXP (y, opnum), inc->inc_dest, 1);
if (! apply_change_group ())
return;
- /* We now know we'll be doing this change, so emit the
- new insn(s) and do the updates. */
- emit_insn_before (insns, insn);
-
- if (BB_HEAD (pbi->bb) == insn)
- BB_HEAD (pbi->bb) = insns;
-
/* INCR will become a NOTE and INSN won't contain a
- use of INCR_REG. If a use of INCR_REG was just placed in
- the insn before INSN, make that the next use.
- Otherwise, invalidate it. */
- if (NONJUMP_INSN_P (PREV_INSN (insn))
- && GET_CODE (PATTERN (PREV_INSN (insn))) == SET
- && SET_SRC (PATTERN (PREV_INSN (insn))) == incr_reg)
- pbi->reg_next_use[regno] = PREV_INSN (insn);
- else
- pbi->reg_next_use[regno] = 0;
+ use of INCR_REG, so invalidate it. */
+ pbi->reg_next_use[inc->regno] = 0;
- incr_reg = q;
- regno = REGNO (q);
+ inc->reg = inc->inc_dest;
+ inc->regno = REGNO (inc->inc_dest);
if ((pbi->flags & PROP_REG_INFO)
- && !REGNO_REG_SET_P (pbi->reg_live, regno))
- reg_deaths[regno] = pbi->insn_num;
+ && !REGNO_REG_SET_P (pbi->reg_live, inc->regno))
+ reg_deaths[inc->regno] = pbi->insn_num;
/* REGNO is now used in INCR which is below INSN, but
it previously wasn't live here. If we don't mark
it as live, we'll put a REG_DEAD note for it
on this insn, which is incorrect. */
- SET_REGNO_REG_SET (pbi->reg_live, regno);
+ SET_REGNO_REG_SET (pbi->reg_live, inc->regno);
/* If there are any calls between INSN and INCR, show
that REGNO now crosses them. */
- for (temp = insn; temp != incr; temp = NEXT_INSN (temp))
+ for (temp = insn; temp != inc->incr; temp = NEXT_INSN (temp))
if (CALL_P (temp))
{
- REG_N_CALLS_CROSSED (regno)++;
+ REG_N_CALLS_CROSSED (inc->regno)++;
if (can_throw_internal (temp))
- REG_N_THROWING_CALLS_CROSSED (regno)++;
+ REG_N_THROWING_CALLS_CROSSED (inc->regno)++;
}
/* Invalidate alias info for Q since we just changed its value. */
- clear_reg_alias_info (q);
+ clear_reg_alias_info (inc->inc_dest);
}
else
return;
@@ -3603,25 +3643,34 @@ attempt_auto_inc (struct propagate_block
auto-inc, so update the status. First, record that this insn
has an implicit side effect. */
- REG_NOTES (insn) = alloc_EXPR_LIST (REG_INC, incr_reg, REG_NOTES (insn));
+ REG_NOTES (insn) = alloc_EXPR_LIST (REG_INC, inc->reg, REG_NOTES (insn));
+
+ /* Emit the new insn(s) and do the updates. */
+ if (insns)
+ {
+ emit_insn_before (insns, insn);
+
+ if (BB_HEAD (pbi->bb) == insn)
+ BB_HEAD (pbi->bb) = insns;
+ }
/* Modify the old increment-insn to simply copy
the already-incremented value of our register. */
- changed = validate_change (incr, &SET_SRC (set), incr_reg, 0);
+ changed = validate_change (inc->incr, inc->inc_loc, inc->reg, 0);
gcc_assert (changed);
/* If that makes it a no-op (copying the register into itself) delete
it so it won't appear to be a "use" and a "set" of this
register. */
- if (REGNO (SET_DEST (set)) == REGNO (incr_reg))
+ if (inc->inc_dest && REGNO (inc->inc_dest) == inc->regno)
{
/* If the original source was dead, it's dead now. */
rtx note;
- while ((note = find_reg_note (incr, REG_DEAD, NULL_RTX)) != NULL_RTX)
+ while ((note = find_reg_note (inc->incr, REG_DEAD, NULL_RTX)) !=
NULL_RTX)
{
- remove_note (incr, note);
- if (XEXP (note, 0) != incr_reg)
+ remove_note (inc->incr, note);
+ if (XEXP (note, 0) != inc->reg)
{
unsigned int regno = REGNO (XEXP (note, 0));
@@ -3635,19 +3684,19 @@ attempt_auto_inc (struct propagate_block
}
}
- SET_INSN_DELETED (incr);
+ SET_INSN_DELETED (inc->incr);
}
- if (regno >= FIRST_PSEUDO_REGISTER)
+ if (inc->regno >= FIRST_PSEUDO_REGISTER)
{
/* Count an extra reference to the reg. When a reg is
incremented, spilling it is worse, so we want to make
that less likely. */
- REG_FREQ (regno) += REG_FREQ_FROM_BB (pbi->bb);
+ REG_FREQ (inc->regno) += REG_FREQ_FROM_BB (pbi->bb);
/* Count the increment as a setting of the register,
even though it isn't a SET in rtl. */
- REG_N_SETS (regno)++;
+ REG_N_SETS (inc->regno)++;
}
}
@@ -3655,89 +3704,120 @@ attempt_auto_inc (struct propagate_block
reference. */
static void
-find_auto_inc (struct propagate_block_info *pbi, rtx x, rtx insn)
+find_auto_inc (struct propagate_block_info *pbi, rtx mem, rtx insn)
{
- rtx addr = XEXP (x, 0);
- HOST_WIDE_INT offset = 0;
- rtx set, y, incr, inc_val;
- int regno;
- int size = GET_MODE_SIZE (GET_MODE (x));
+ rtx set;
+ HOST_WIDE_INT val, offset = 0;
+ struct inc_data inc;
+ int size = GET_MODE_SIZE (GET_MODE (mem));
if (JUMP_P (insn))
return;
+ memset (&inc, 0, sizeof(inc));
+ inc.reg = XEXP (mem, 0);
+ inc.offset = 0;
+
/* Here we detect use of an index register which might be good for
postincrement, postdecrement, preincrement, or predecrement. */
+ if (GET_CODE (inc.reg) == PLUS
+ && GET_CODE (XEXP (inc.reg, 1)) == CONST_INT)
+ {
+ offset = INTVAL (XEXP (inc.reg, 1));
+ inc.reg = XEXP (inc.reg, 0);
+ }
- if (GET_CODE (addr) == PLUS && GET_CODE (XEXP (addr, 1)) == CONST_INT)
- offset = INTVAL (XEXP (addr, 1)), addr = XEXP (addr, 0);
-
- if (!REG_P (addr))
+ if (!REG_P (inc.reg))
return;
- regno = REGNO (addr);
+ inc.regno = REGNO (inc.reg);
/* Is the next use an increment that might make auto-increment? */
- incr = pbi->reg_next_use[regno];
- if (incr == 0 || BLOCK_NUM (incr) != BLOCK_NUM (insn))
- return;
- set = single_set (incr);
- if (set == 0 || GET_CODE (set) != SET)
- return;
- y = SET_SRC (set);
-
- if (GET_CODE (y) != PLUS)
- return;
-
- if (REG_P (XEXP (y, 0)) && REGNO (XEXP (y, 0)) == REGNO (addr))
- inc_val = XEXP (y, 1);
- else if (REG_P (XEXP (y, 1)) && REGNO (XEXP (y, 1)) == REGNO (addr))
- inc_val = XEXP (y, 0);
- else
+ inc.incr = pbi->reg_next_use[inc.regno];
+ if (!inc.incr || BLOCK_NUM (inc.incr) != BLOCK_NUM (insn))
+ {
+ if (HAVE_PRE_DECREMENT && offset == -size
+ && dead_or_set_p (insn, inc.reg)
+ && (inc.regno >= FIRST_PSEUDO_REGISTER
+ || !TEST_HARD_REG_BIT (elim_reg_set, inc.regno))
+ && count_occurrences (PATTERN (insn), inc.reg, 1) == 1)
+ {
+ inc.inc = gen_rtx_PRE_DEC (Pmode, inc.reg);
+ if (!validate_change (insn, &XEXP (mem, 0), inc.inc, 0))
+ return;
+ if (inc.regno >= FIRST_PSEUDO_REGISTER)
+ {
+ REG_FREQ (inc.regno) += REG_FREQ_FROM_BB (pbi->bb);
+ REG_N_SETS (inc.regno)++;
+ }
+ }
+ return;
+ }
+ if (for_each_rtx (&inc.incr, find_inc_1, &inc) || !inc.inc_loc)
return;
+ set = single_set (inc.incr);
+ if (set && inc.inc_loc == &SET_SRC (set) && REG_P (SET_DEST (set)))
+ inc.inc_dest = SET_DEST (set);
- if (GET_CODE (inc_val) == CONST_INT)
+ if (GET_CODE (inc.inc_val) == CONST_INT)
{
- if (HAVE_POST_INCREMENT
- && (INTVAL (inc_val) == size && offset == 0))
- attempt_auto_inc (pbi, gen_rtx_POST_INC (Pmode, addr), insn, x,
- incr, addr);
- else if (HAVE_POST_DECREMENT
- && (INTVAL (inc_val) == -size && offset == 0))
- attempt_auto_inc (pbi, gen_rtx_POST_DEC (Pmode, addr), insn, x,
- incr, addr);
- else if (HAVE_PRE_INCREMENT
- && (INTVAL (inc_val) == size && offset == size))
- attempt_auto_inc (pbi, gen_rtx_PRE_INC (Pmode, addr), insn, x,
- incr, addr);
- else if (HAVE_PRE_DECREMENT
- && (INTVAL (inc_val) == -size && offset == -size))
- attempt_auto_inc (pbi, gen_rtx_PRE_DEC (Pmode, addr), insn, x,
- incr, addr);
+ inc.offset = INTVAL (inc.inc_val);
+ val = INTVAL (inc.inc_val) - offset;
+
+ if (HAVE_POST_INCREMENT && val == size
+ && (inc.inc_dest || offset == 0))
+ {
+ inc.inc = gen_rtx_POST_INC (Pmode, inc.reg);
+ inc.offset -= size;
+ }
+ else if (HAVE_POST_DECREMENT && val == -size
+ && (inc.inc_dest || offset == 0))
+ {
+ inc.inc = gen_rtx_POST_DEC (Pmode, inc.reg);
+ inc.offset += size;
+ }
+ else if (HAVE_PRE_INCREMENT && val == 0
+ && (inc.inc_dest || offset == size))
+ {
+ inc.inc = gen_rtx_PRE_INC (Pmode, inc.reg);
+ inc.offset -= size;
+ }
+ else if (HAVE_PRE_DECREMENT && val == 0
+ && (inc.inc_dest || offset == -size))
+ {
+ inc.inc = gen_rtx_PRE_DEC (Pmode, inc.reg);
+ inc.offset += size;
+ }
else if (HAVE_POST_MODIFY_DISP && offset == 0)
- attempt_auto_inc (pbi, gen_rtx_POST_MODIFY (Pmode, addr,
- gen_rtx_PLUS (Pmode,
- addr,
- inc_val)),
- insn, x, incr, addr);
- else if (HAVE_PRE_MODIFY_DISP && offset == INTVAL (inc_val))
- attempt_auto_inc (pbi, gen_rtx_PRE_MODIFY (Pmode, addr,
- gen_rtx_PLUS (Pmode,
- addr,
- inc_val)),
- insn, x, incr, addr);
- }
- else if (REG_P (inc_val)
- && ! reg_set_between_p (inc_val, PREV_INSN (insn),
- NEXT_INSN (incr)))
+ {
+ inc.inc = gen_rtx_POST_MODIFY (Pmode, inc.reg,
+ gen_rtx_PLUS (Pmode, inc.reg,
+ inc.inc_val));
+ inc.offset = 0;
+ }
+ else if (HAVE_PRE_MODIFY_DISP && offset == INTVAL (inc.inc_val))
+ {
+ inc.inc = gen_rtx_PRE_MODIFY (Pmode, inc.reg,
+ gen_rtx_PLUS (Pmode, inc.reg,
+ inc.inc_val));
+ inc.offset = 0;
+ }
+ else
+ return;
+ attempt_auto_inc (pbi, insn, mem, &inc);
+ }
+ else if (REG_P (inc.inc_val)
+ && ! reg_set_between_p (inc.inc_val, PREV_INSN (insn),
+ NEXT_INSN (inc.incr)))
{
if (HAVE_POST_MODIFY_REG && offset == 0)
- attempt_auto_inc (pbi, gen_rtx_POST_MODIFY (Pmode, addr,
- gen_rtx_PLUS (Pmode,
- addr,
- inc_val)),
- insn, x, incr, addr);
+ inc.inc = gen_rtx_POST_MODIFY (Pmode, inc.reg,
+ gen_rtx_PLUS (Pmode, inc.reg,
+ inc.inc_val));
+ else
+ return;
+ attempt_auto_inc (pbi, insn, mem, &inc);
}
}
@@ -4250,10 +4330,6 @@ try_pre_increment_1 (struct propagate_bl
&& ! dead_or_set_p (y, SET_DEST (x))
&& try_pre_increment (y, SET_DEST (x), amount))
{
- /* We have found a suitable auto-increment and already changed
- insn Y to do it. So flush this increment instruction. */
- propagate_block_delete_insn (insn);
-
/* Count a reference to this reg for the increment insn we are
deleting. When a reg is incremented, spilling it is worse,
so we want to make that less likely. */
@@ -4263,6 +4339,18 @@ try_pre_increment_1 (struct propagate_bl
REG_N_SETS (regno)++;
}
+ if (XEXP (SET_SRC (x), 0) != SET_DEST (x))
+ {
+ int change;
+ change = validate_change (insn, &SET_SRC (x), XEXP (SET_SRC (x), 0),
0);
+ gcc_assert(change);
+ return 0;
+ }
+
+ /* We have found a suitable auto-increment and already changed
+ insn Y to do it. So flush this increment instruction. */
+ propagate_block_delete_insn (insn);
+
/* Flush any remembered memories depending on the value of
the incremented register. */
invalidate_mems_from_set (pbi, SET_DEST (x));
