Patch to improve shadowing of loop variables
Michael Hayes
mhayes@cygnus.com
Sun Jul 30 04:01:00 GMT 2000
I would like to submit the following patch for review that improves
loop reversal, GIV replacement, and BIV elimination for global
induction variables that get shadowed by a register.
This patch improves the generated code for loops using a global
variable as an induction variable so that it is comparable with code
generated when an automatic variable is used as the induction
variable. (Personally I abhor using global variables, especially for
induction variables, but it's amazing what some folks do....)
I've bootstrapped gcc with it on i686-pc-linux-gnu.
Synopsis:
Currently, when load_mems hoists/sinks memory references from a loop
and shadows the memory with a pseudo register, we get code of the
form:
(set (pseudo_foo) (plus ((pseudo_shadow) (const_int 1)))
(set (pseudo_shadow) (pseudo_foo))
(set (flags) (compare (pseudo_foo) (bar)))
This patch does a little renaming to give:
(set (pseudo_shadow) (plus ((pseudo_shadow) (const_int 1)))
(set (pseudo_foo) (pseudo_shadow))
(set (flags) (compare (pseudo_foo) (bar)))
and then performs some copy propagation to give:
(set (pseudo_shadow) (plus ((pseudo_shadow) (const_int 1)))
(set (flags) (compare (pseudo_shadow) (bar)))
The GIV elimination code finds this much more digestible.
Michael.
2000-07-10 Michael Hayes <mhayes@cygnus.com>
* loop.c (try_swap_copy_prop): New function.
(load_mems): Rename copies to load_copies and add new regset
store_copies. Check for sets of shadow registers and mark
in store_copies. Call try_swap_copy_prop for registers
marked in store_copies.
Index: loop.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/loop.c,v
retrieving revision 1.261
diff -c -3 -p -r1.261 loop.c
*** loop.c 2000/07/22 23:29:14 1.261
--- loop.c 2000/07/30 10:38:00
*************** static int replace_loop_mem PARAMS ((rtx
*** 307,312 ****
--- 307,314 ----
static int replace_loop_reg PARAMS ((rtx *, void *));
static void note_reg_stored PARAMS ((rtx, rtx, void *));
static void try_copy_prop PARAMS ((const struct loop *, rtx, unsigned int));
+ static void try_swap_copy_prop PARAMS ((const struct loop *, rtx,
+ unsigned int));
static int replace_label PARAMS ((rtx *, void *));
static rtx check_insn_for_givs PARAMS((struct loop *, rtx, int, int));
static rtx check_insn_for_bivs PARAMS((struct loop *, rtx, int, int));
*************** load_mems (loop)
*** 9749,9755 ****
/* Actually move the MEMs. */
for (i = 0; i < loop_mems_idx; ++i)
{
! regset_head copies;
int written = 0;
rtx reg;
rtx mem = loop_mems[i].mem;
--- 9751,9758 ----
/* Actually move the MEMs. */
for (i = 0; i < loop_mems_idx; ++i)
{
! regset_head load_copies;
! regset_head store_copies;
int written = 0;
rtx reg;
rtx mem = loop_mems[i].mem;
*************** load_mems (loop)
*** 9815,9821 ****
loop, but later discovered that we could not. */
continue;
! INIT_REG_SET (&copies);
/* Allocate a pseudo for this MEM. We set REG_USERVAR_P in
order to keep scan_loop from moving stores to this MEM
--- 9818,9825 ----
loop, but later discovered that we could not. */
continue;
! INIT_REG_SET (&load_copies);
! INIT_REG_SET (&store_copies);
/* Allocate a pseudo for this MEM. We set REG_USERVAR_P in
order to keep scan_loop from moving stores to this MEM
*************** load_mems (loop)
*** 9833,9855 ****
p = next_insn_in_loop (loop, p))
{
rtx_and_int ri;
- rtx set;
if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
{
/* See if this copies the mem into a register that isn't
modified afterwards. We'll try to do copy propagation
a little further on. */
- set = single_set (p);
if (set
/* @@@ This test is _way_ too conservative. */
&& ! maybe_never
&& GET_CODE (SET_DEST (set)) == REG
&& REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
&& REGNO (SET_DEST (set)) < last_max_reg
! && VARRAY_INT (n_times_set, REGNO (SET_DEST (set))) == 1
! && rtx_equal_p (SET_SRC (set), loop_mems[i].mem))
! SET_REGNO_REG_SET (&copies, REGNO (SET_DEST (set)));
ri.r = p;
ri.i = i;
for_each_rtx (&p, replace_loop_mem, &ri);
--- 9837,9877 ----
p = next_insn_in_loop (loop, p))
{
rtx_and_int ri;
if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
{
+ rtx set;
+
+ set = single_set (p);
+
/* See if this copies the mem into a register that isn't
modified afterwards. We'll try to do copy propagation
a little further on. */
if (set
/* @@@ This test is _way_ too conservative. */
&& ! maybe_never
&& GET_CODE (SET_DEST (set)) == REG
&& REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
&& REGNO (SET_DEST (set)) < last_max_reg
! && VARRAY_INT (n_times_set, REGNO (SET_DEST (set))) == 1U
! && rtx_equal_p (SET_SRC (set), mem))
! SET_REGNO_REG_SET (&load_copies, REGNO (SET_DEST (set)));
!
! /* See if this copies the mem from a register that isn't
! modified afterwards. We'll try to remove the
! redundant copy later on by doing a little register
! renaming and copy propagation. This will help
! to untangle things for the BIV detection code. */
! if (set
! && ! maybe_never
! && GET_CODE (SET_SRC (set)) == REG
! && REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER
! && REGNO (SET_SRC (set)) < last_max_reg
! && VARRAY_INT (n_times_set, REGNO (SET_SRC (set))) == 1U
! && rtx_equal_p (SET_DEST (set), mem))
! SET_REGNO_REG_SET (&store_copies, REGNO (SET_SRC (set)));
!
! /* Replace the memory reference with the shadow register. */
ri.r = p;
ri.i = i;
for_each_rtx (&p, replace_loop_mem, &ri);
*************** load_mems (loop)
*** 9945,9955 ****
data flow, and enables {basic,general}_induction_var to find
more bivs/givs. */
EXECUTE_IF_SET_IN_REG_SET
! (&copies, FIRST_PSEUDO_REGISTER, j,
{
! try_copy_prop (loop, loop_mems[i].reg, j);
});
! CLEAR_REG_SET (&copies);
}
}
--- 9967,9984 ----
data flow, and enables {basic,general}_induction_var to find
more bivs/givs. */
EXECUTE_IF_SET_IN_REG_SET
! (&load_copies, FIRST_PSEUDO_REGISTER, j,
{
! try_copy_prop (loop, reg, j);
});
! CLEAR_REG_SET (&load_copies);
!
! EXECUTE_IF_SET_IN_REG_SET
! (&store_copies, FIRST_PSEUDO_REGISTER, j,
! {
! try_swap_copy_prop (loop, reg, j);
! });
! CLEAR_REG_SET (&store_copies);
}
}
*************** try_copy_prop (loop, replacement, regno)
*** 10084,10089 ****
--- 10113,10207 ----
fprintf (loop_dump_stream, ".\n");
}
}
+
+
+ /* Try to replace occurrences of pseudo REGNO with REPLACEMENT within
+ loop LOOP if the order of the sets of these registers can be
+ swapped. There must be exactly one insn within the loop that sets
+ this pseudo followed immediately by a move insn that sets
+ REPLACEMENT with REGNO. */
+ static void
+ try_swap_copy_prop (loop, replacement, regno)
+ const struct loop *loop;
+ rtx replacement;
+ unsigned int regno;
+ {
+ rtx insn;
+ rtx set;
+ int new_regno;
+
+ new_regno = REGNO (replacement);
+
+ for (insn = next_insn_in_loop (loop, loop->scan_start);
+ insn != NULL_RTX;
+ insn = next_insn_in_loop (loop, insn))
+ {
+ /* Search for the insn that copies REGNO to NEW_REGNO? */
+ if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
+ && (set = single_set (insn))
+ && GET_CODE (SET_DEST (set)) == REG
+ && REGNO (SET_DEST (set)) == new_regno
+ && GET_CODE (SET_SRC (set)) == REG
+ && REGNO (SET_SRC (set)) == regno)
+ break;
+ }
+
+ if (insn != NULL_RTX)
+ {
+ rtx prev_insn;
+ rtx prev_set;
+
+ /* Some DEF-USE info would come in handy here to make this
+ function more general. For now, just check the previous insn
+ which is the most likely candidate for setting REGNO. */
+
+ prev_insn = PREV_INSN (insn);
+
+ if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
+ && (prev_set = single_set (prev_insn))
+ && GET_CODE (SET_DEST (prev_set)) == REG
+ && REGNO (SET_DEST (prev_set)) == regno)
+ {
+ /* We have:
+ (set (reg regno) (expr))
+ (set (reg new_regno) (reg regno))
+
+ so try converting this to:
+ (set (reg new_regno) (expr))
+ (set (reg regno) (reg new_regno))
+
+ The former construct is often generated when a global
+ variable used for an induction variable is shadowed by a
+ register (NEW_REGNO). The latter construct improves the
+ chances of GIV replacement and BIV elimination. */
+
+ validate_change (prev_insn, &SET_DEST (prev_set),
+ replacement, 1);
+ validate_change (insn, &SET_DEST (set),
+ SET_SRC (set), 1);
+ validate_change (insn, &SET_SRC (set),
+ replacement, 1);
+
+ if (apply_change_group ())
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ " Swapped set of reg %d at %d with reg %d at %d.\n",
+ regno, INSN_UID (insn),
+ new_regno, INSN_UID (prev_insn));
+
+ /* Update first use of REGNO. */
+ if (REGNO_FIRST_UID (regno) == INSN_UID (prev_insn))
+ REGNO_FIRST_UID (regno) = INSN_UID (insn);
+
+ /* Now perform copy propagation to hopefully
+ remove all uses of REGNO within the loop. */
+ try_copy_prop (loop, replacement, regno);
+ }
+ }
+ }
+ }
+
/* Replace MEM with its associated pseudo register. This function is
called from load_mems via for_each_rtx. DATA is actually an
More information about the Gcc-patches
mailing list