This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] Find more cases for AUTO_INC_DEC
- From: Adam Nemet <anemet at lnxw dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Sat, 16 Jul 2005 13:40:53 -0700
- Subject: [PATCH] Find more cases for AUTO_INC_DEC
Hi,
Mainline has stopped optimizing the following function into stuw
(pre-increment) on PowerPC:
int *stwu4 (int *p, int i)
{
*++p = i;
return p;
}
AUTO_INC_DEC in flow.c is supposed to take care of optmizing this. It
does it by searching for situations where a pseudo is
incremented/decremented and the next use is an address expression:
p = p + 1; *p => *++p
The reason is why GCC in many cases does not arrive to the left side
of this is two-fold. First, outof-ssa live-range splitting produces
the following code:
p.9 = p + 4B;
*p.9 = i;
return p.9;
And p.9 and p are expanded into different pseudos (r = p + 1; *r).
Second, CSE notices that address_cost on PowerPC allows propagation of
the addition into the address expression.
Because of these two reasons, AUTO_INC_DEC in flow might be presented
with something like: r = p + 4; *(p + 4).
In my assessment both live-range splitting and CSE do the right thing.
The transformation in CSE makes sense assuming that R has no uses
later so the addition can get eliminated. It seems to me that flow is
where there is enough information about uses to decided whether we
want the CSE'd address or inc/dec'd address.
The patch below attempts to extend the cases where this optimization
triggers. This results in not only fixing the above regression but an
additional 472 cases to the current 900 cases (+52%) of AUTO_INC_DEC
substitutions during a darwin bootstrap.
There is at least one limitation to my approach. It doesn't do full
"unpropagation", i.e. it only looks at P's next use hoping that it can
be considered R's next use. (But next use info is basically free as
this information is already available in flow.) So a case like
r = p + 4; use (p); *(p+4); use (r)
will not be transformed. I will measure how typical a case this is
and perhaps further generalize the approach. Anyway, given the
positive effect of the patch I hope it can be accepted even in its
current form.
Bootstrapped and tested on powerpc-apple-darwin7.5.1 (also on
i686-pc-linux-gnu but there is no AUTO_INC_DEC on x86). I am also
planning to do further testing on arm-elf which has POST_INC/DEC as
well.
OK to apply if ARM testing is successful?
Adam
2005-07-16 Adam Nemet <anemet@lnxw.com>
* flow.c: (struct reg_next_use_info): New struct.
(struct propagate_block_info, reg_next_use): Change type to
reg_next_use_info.
(init_propagate_block_info, mark_set_1, attempt_auto_inc,
find_auto_inc, mark_used_reg): Adjust use of reg_next_use.
(try_pre_increment): Add new argument. Adjust declaration.
(try_pre_increment_1): Return rtx. Adjust declaration. Work with
more cases. Add comment before function.
(propagate_one_insn): Adjust logic of calling try_pre_increment_1.
Index: flow.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flow.c,v
retrieving revision 1.632
diff -c -p -r1.632 flow.c
*** flow.c 5 Jul 2005 16:19:55 -0000 1.632
--- flow.c 16 Jul 2005 18:59:23 -0000
*************** struct reg_cond_life_info
*** 214,219 ****
--- 214,230 ----
track lifetimes of multi-word registers accessed via subregs. */
};
+ /* Holds information about the next use of a register. INSN is the
+ next insn using the register; or zero, if there is no such insn.
+ INSN_NUM is the index of INSN. Its value is only valid if INSN is
+ non-zero. */
+
+ struct reg_next_use_info
+ {
+ rtx insn;
+ int insn_num;
+ };
+
/* For use in communicating between propagate_block and its subroutines.
Holds all information needed to compute life and def-use information. */
*************** struct propagate_block_info
*** 228,236 ****
/* Bit N is set if register N is set this insn. */
regset new_set;
! /* Element N is the next insn that uses (hard or pseudo) register N
! within the current basic block; or zero, if there is no such insn. */
! rtx *reg_next_use;
/* Contains a list of all the MEMs we are tracking for dead store
elimination. */
--- 239,247 ----
/* Bit N is set if register N is set this insn. */
regset new_set;
! /* Element N is information about the next insn that uses (hard or
! pseudo) register N within the current basic block. */
! struct reg_next_use_info *reg_next_use;
/* Contains a list of all the MEMs we are tracking for dead store
elimination. */
*************** static rtx and_reg_cond (rtx, rtx, int);
*** 319,326 ****
static void attempt_auto_inc (struct propagate_block_info *, rtx, rtx, rtx,
rtx, rtx);
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);
#endif
static void mark_used_reg (struct propagate_block_info *, rtx, rtx, rtx);
static void mark_used_regs (struct propagate_block_info *, rtx, rtx, rtx);
--- 330,337 ----
static void attempt_auto_inc (struct propagate_block_info *, rtx, rtx, rtx,
rtx, rtx);
static void find_auto_inc (struct propagate_block_info *, rtx, rtx);
! static rtx try_pre_increment_1 (struct propagate_block_info *, rtx);
! static int try_pre_increment (rtx, rtx, HOST_WIDE_INT, rtx);
#endif
static void mark_used_reg (struct propagate_block_info *, rtx, rtx, rtx);
static void mark_used_regs (struct propagate_block_info *, rtx, rtx, rtx);
*************** propagate_one_insn (struct propagate_blo
*** 1768,1781 ****
&& 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)
! && 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
! or PRE_DEC, cancel this insn, and return 1.
Return 0 if nothing has been done. */
! && try_pre_increment_1 (pbi, insn))
! return prev;
}
#endif /* AUTO_INC_DEC */
--- 1779,1796 ----
&& REG_P (SET_DEST (x))
&& (GET_CODE (SET_SRC (x)) == PLUS
|| GET_CODE (SET_SRC (x)) == MINUS)
! && 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
! or PRE_DEC, and continue with the new previous insn.
Return 0 if nothing has been done. */
! rtx newprev = try_pre_increment_1 (pbi, insn);
!
! if (newprev)
! return newprev;
! }
}
#endif /* AUTO_INC_DEC */
*************** init_propagate_block_info (basic_block b
*** 1950,1956 ****
pbi->insn_num = 0;
if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
! pbi->reg_next_use = xcalloc (max_reg_num (), sizeof (rtx));
else
pbi->reg_next_use = NULL;
--- 1965,1972 ----
pbi->insn_num = 0;
if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
! pbi->reg_next_use
! = xcalloc (max_reg_num (), sizeof (struct reg_next_use_info));
else
pbi->reg_next_use = NULL;
*************** mark_set_1 (struct propagate_block_info
*** 2848,2858 ****
y = NULL_RTX;
if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
{
! y = pbi->reg_next_use[regno_first];
/* The next use is no longer next, since a store intervenes. */
for (i = regno_first; i <= regno_last; ++i)
! pbi->reg_next_use[i] = 0;
}
if (flags & PROP_REG_INFO)
--- 2864,2874 ----
y = NULL_RTX;
if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
{
! y = pbi->reg_next_use[regno_first].insn;
/* The next use is no longer next, since a store intervenes. */
for (i = regno_first; i <= regno_last; ++i)
! pbi->reg_next_use[i].insn = 0;
}
if (flags & PROP_REG_INFO)
*************** mark_set_1 (struct propagate_block_info
*** 2982,2988 ****
else if (REG_P (reg))
{
if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
! pbi->reg_next_use[regno_first] = 0;
if ((flags & PROP_REG_INFO) != 0
&& (flags & PROP_ASM_SCAN) != 0
--- 2998,3004 ----
else if (REG_P (reg))
{
if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
! pbi->reg_next_use[regno_first].insn = 0;
if ((flags & PROP_REG_INFO) != 0
&& (flags & PROP_ASM_SCAN) != 0
*************** attempt_auto_inc (struct propagate_block
*** 3491,3499 ****
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;
incr_reg = q;
regno = REGNO (q);
--- 3507,3518 ----
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].insn = PREV_INSN (insn);
! pbi->reg_next_use[regno].insn_num = pbi->insn_num + 1;
! }
else
! pbi->reg_next_use[regno].insn = 0;
incr_reg = q;
regno = REGNO (q);
*************** find_auto_inc (struct propagate_block_in
*** 3599,3605 ****
regno = REGNO (addr);
/* 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);
--- 3618,3624 ----
regno = REGNO (addr);
/* Is the next use an increment that might make auto-increment? */
! incr = pbi->reg_next_use[regno].insn;
if (incr == 0 || BLOCK_NUM (incr) != BLOCK_NUM (insn))
return;
set = single_set (incr);
*************** mark_used_reg (struct propagate_block_in
*** 3693,3699 ****
{
/* Record where each reg is used, so when the reg is set we know
the next insn that uses it. */
! pbi->reg_next_use[regno_first] = insn;
}
if (pbi->flags & PROP_REG_INFO)
--- 3712,3719 ----
{
/* Record where each reg is used, so when the reg is set we know
the next insn that uses it. */
! pbi->reg_next_use[regno_first].insn = insn;
! pbi->reg_next_use[regno_first].insn_num = pbi->insn_num;
}
if (pbi->flags & PROP_REG_INFO)
*************** mark_used_regs (struct propagate_block_i
*** 4119,4125 ****
#ifdef AUTO_INC_DEC
! static int
try_pre_increment_1 (struct propagate_block_info *pbi, rtx insn)
{
/* Find the next use of this reg. If in same basic block,
--- 4139,4155 ----
#ifdef AUTO_INC_DEC
! /* INSN is an addition/substraction instruction. See if the next use
! provided by PBI can be changed into an auto-increment or
! auto-decrement. Return the previous insn.
!
! We handle three cases:
!
! (1) r = r + C; *r => *(r+=C)
! (2) r = p + C; *r => r = p; *(r+=C)
! (3) r = p + C; *(p + C) => r = p; *(r+=C) */
!
! static rtx
try_pre_increment_1 (struct propagate_block_info *pbi, rtx insn)
{
/* Find the next use of this reg. If in same basic block,
*************** try_pre_increment_1 (struct propagate_bl
*** 4127,4172 ****
rtx x = single_set (insn);
HOST_WIDE_INT amount = ((GET_CODE (SET_SRC (x)) == PLUS ? 1 : -1)
* INTVAL (XEXP (SET_SRC (x), 1)));
! int regno = REGNO (SET_DEST (x));
! rtx y = pbi->reg_next_use[regno];
! if (y != 0
! && SET_DEST (x) != stack_pointer_rtx
! && BLOCK_NUM (y) == BLOCK_NUM (insn)
! /* Don't do this if the reg dies, or gets set in y; a standard addressing
! mode would be better. */
! && ! 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. */
! if (regno >= FIRST_PSEUDO_REGISTER)
! {
! REG_FREQ (regno) += REG_FREQ_FROM_BB (pbi->bb);
! REG_N_SETS (regno)++;
! }
!
! /* Flush any remembered memories depending on the value of
! the incremented register. */
! invalidate_mems_from_set (pbi, SET_DEST (x));
! return 1;
}
! return 0;
}
/* Try to change INSN so that it does pre-increment or pre-decrement
addressing on register REG in order to add AMOUNT to REG.
AMOUNT is negative for pre-decrement.
Returns 1 if the change could be made.
! This checks all about the validity of the result of modifying INSN. */
static int
! try_pre_increment (rtx insn, rtx reg, HOST_WIDE_INT amount)
{
rtx use;
--- 4157,4260 ----
rtx x = single_set (insn);
HOST_WIDE_INT amount = ((GET_CODE (SET_SRC (x)) == PLUS ? 1 : -1)
* INTVAL (XEXP (SET_SRC (x), 1)));
! rtx p = XEXP (SET_SRC (x), 0);
! rtx r = SET_DEST (x);
! int pno = REGNO (p), rno = REGNO (r);
! rtx next_use;
! struct reg_next_use_info *next_use_info;
! rtx prev;
! if (r == stack_pointer_rtx)
! return NULL_RTX;
!
! /* Case 3. */
! if (p != r
! && (next_use_info = &pbi->reg_next_use[pno])->insn
! && BLOCK_NUM (next_use_info->insn) == BLOCK_NUM (insn)
! /* Make sure R is used later. Don't do this if R is used
! between INSN and NEXT_USE. */
! && (pbi->reg_next_use[rno].insn
! ? pbi->reg_next_use[rno].insn_num < next_use_info->insn_num
! : REGNO_REG_SET_P (pbi->reg_live, rno))
! /* The incremented value of R is not used later if it is set
! here. */
! && !reg_set_p (r, next_use_info->insn)
! && try_pre_increment (next_use_info->insn, r, amount, p))
! {
! rtx next_use = next_use_info->insn;
! rtx dead_note = find_reg_note (next_use, REG_DEAD, p);
!
! /* Notice that between INSN and NEXT_USE there can be no def or
! use of P and R. So we can just assume that their use
! situation is the same at INSN as it was at NEXT_USE. Update
! meta-data with removed use for P. */
! if (dead_note)
! {
! remove_note (next_use, dead_note);
! pbi->reg_next_use[pno].insn = 0;
! reg_deaths[pno] = 0;
! CLEAR_REGNO_REG_SET (pbi->reg_live, pno);
! }
!
! /* Add the new use for R. */
! pbi->reg_next_use[rno].insn = next_use;
! pbi->reg_next_use[rno].insn_num = next_use_info->insn_num;
! }
! /* Case 1 and 2. */
! else if ((next_use = pbi->reg_next_use[rno].insn)
! && BLOCK_NUM (next_use) == BLOCK_NUM (insn)
! /* Don't do this if the reg dies, or gets set in y; a
! standard addressing mode would be better. */
! && !dead_or_set_p (next_use, r)
! && try_pre_increment (next_use, r, amount, NULL_RTX))
! ;
! else
! return 0;
!
! /* Emit r = p. */
! if (p != r)
! {
! rtx insns;
!
! start_sequence ();
! emit_move_insn (r, p);
! insns = get_insns ();
! end_sequence ();
! prev = emit_insn_before (insns, insn);
}
! else
! prev = PREV_INSN (insn);
!
! /* We have found a suitable auto-increment and already changed insn
! NEXT_USE 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. */
! if (rno >= FIRST_PSEUDO_REGISTER)
! {
! REG_FREQ (rno) += REG_FREQ_FROM_BB (pbi->bb);
! REG_N_SETS (rno)++;
! }
!
! /* Flush any remembered memories depending on the value of
! the incremented register. */
! invalidate_mems_from_set (pbi, r);
!
! return prev;
}
/* Try to change INSN so that it does pre-increment or pre-decrement
addressing on register REG in order to add AMOUNT to REG.
AMOUNT is negative for pre-decrement.
Returns 1 if the change could be made.
! This checks all about the validity of the result of modifying INSN.
! If BASE is set, cse has replaced REG with its defining expression
! (BASE + AMOUNT). Look for this form instead. */
static int
! try_pre_increment (rtx insn, rtx reg, HOST_WIDE_INT amount, rtx base)
{
rtx use;
*************** try_pre_increment (rtx insn, rtx reg, HO
*** 4206,4215 ****
use = 0;
if (pre_ok)
! use = find_use_as_address (PATTERN (insn), reg, 0);
if (post_ok && (use == 0 || use == (rtx) (size_t) 1))
{
! use = find_use_as_address (PATTERN (insn), reg, -amount);
do_post = 1;
}
--- 4294,4311 ----
use = 0;
if (pre_ok)
! {
! if (base)
! use = find_use_as_address (PATTERN (insn), base, amount);
! else
! use = find_use_as_address (PATTERN (insn), reg, 0);
! }
if (post_ok && (use == 0 || use == (rtx) (size_t) 1))
{
! if (base)
! use = find_use_as_address (PATTERN (insn), base, 0);
! else
! use = find_use_as_address (PATTERN (insn), reg, -amount);
do_post = 1;
}