comments on loop changes
Richard Henderson
rth@cygnus.com
Sat Feb 13 23:57:00 GMT 1999
On Sun, Feb 14, 1999 at 04:33:43PM +1300, Michael Hayes wrote:
> Unfortunately, it is not the silver bullet :-( For example, a complex
> vector summation still requires twice the number of adress registers
> than it should and REG+REG addressing modes are still being
> unecessarily generated. However, I cannot put my finger on the
> problem at the moment.
Something Toon and I discussed once upon a time is guiding combination
based on register pressure across the entire loop.
This does not attempt anything so bold. But it does fairly effectively
prefer individual combinations that use one register over those that
use more. Which happens to cure the reg+reg losage you are seeing in
that complex vector addition example.
This change should be more effectively benchmarked.
It falls down in that it might, for example, prefer 6 single register
combination givs over one combination giv that uses 4. Full calculation
of register usage among combinations is probably O(C!) where C is the
number of allowable combinations of the N givs. So unless I miss
something, that would seem to be impractical.
Also, register invariants otherwise used within the loop are essentially
free, and so should not be counted. These might be accounted for by
scaning the non-giv-bearing insns of the loop and marking all invariant
registers used therein. Except that flow hasn't been run so dead code
has not been eliminated, so we'd collect a (perhaps large) superset of
what is actually otherwise used.
Oops, I didn't mean to include it in the patch, but note that I had to
disable recombine_givs in order to get good results on your test case.
r~
* loop.c (cmp_combine_givs_stats): Add primary sort on reg_count.
(combine_givs_count_regs): New function.
(combine_givs): Calculate reg_count of all combinations of each giv.
Index: loop.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/loop.c,v
retrieving revision 1.136
diff -c -p -d -r1.136 loop.c
*** loop.c 1999/02/13 23:25:19 1.136
--- loop.c 1999/02/14 07:29:29
*************** Boston, MA 02111-1307, USA. */
*** 49,54 ****
--- 49,55 ----
#include "loop.h"
#include "except.h"
#include "toplev.h"
+ #include "basic-block.h"
/* Vector mapping INSN_UIDs to luids.
The luids are like uids but increase monotonically always.
*************** strength_reduce (scan_start, end, loop_t
*** 4627,4632 ****
--- 4628,4634 ----
VARRAY_GROW (reg_iv_type, nregs);
VARRAY_GROW (reg_iv_info, nregs);
}
+ if (0)
recombine_givs (bl, loop_start, loop_end, unroll_p);
/* Reduce each giv that we decided to reduce. */
*************** combine_givs_p (g1, g2)
*** 6752,6757 ****
--- 6754,6760 ----
struct combine_givs_stats
{
+ int reg_count;
int giv_number;
int total_benefit;
};
*************** cmp_combine_givs_stats (x, y)
*** 6761,6773 ****
struct combine_givs_stats *x, *y;
{
int d;
! d = y->total_benefit - x->total_benefit;
/* Stabilize the sort. */
if (!d)
d = x->giv_number - y->giv_number;
return d;
}
/* Check all pairs of givs for iv_class BL and see if any can be combined with
any other. If so, point SAME to the giv combined with and set NEW_REG to
be an expression (in terms of the other giv's DEST_REG) equivalent to the
--- 6764,6816 ----
struct combine_givs_stats *x, *y;
{
int d;
!
! /* Sort fewest registers used first. */
! d = x->reg_count - y->reg_count;
!
! /* Secondary sort based on benefit. */
! if (!d)
! d = y->total_benefit - x->total_benefit;
!
/* Stabilize the sort. */
if (!d)
d = x->giv_number - y->giv_number;
+
return d;
}
+ static int
+ combine_givs_count_regs (x, used)
+ rtx x;
+ regset used;
+ {
+ register char *fmt;
+ int count;
+ int i, j;
+
+ if (GET_CODE (x) == REG)
+ {
+ if (! REGNO_REG_SET_P (used, REGNO (x)))
+ {
+ SET_REGNO_REG_SET (used, REGNO (x));
+ return 1;
+ }
+ return 0;
+ }
+
+ count = 0;
+ fmt = GET_RTX_FORMAT (GET_CODE (x));
+ for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
+ {
+ if (fmt[i] == 'e')
+ count += combine_givs_count_regs (XEXP (x, i), used);
+ else if (fmt[i] == 'E')
+ for (j = XVECLEN (x, i) - 1; j >= 0; j--)
+ count += combine_givs_count_regs (XVECEXP (x, i, j), used);
+ }
+ return count;
+ }
+
/* Check all pairs of givs for iv_class BL and see if any can be combined with
any other. If so, point SAME to the giv combined with and set NEW_REG to
be an expression (in terms of the other giv's DEST_REG) equivalent to the
*************** combine_givs (bl)
*** 6783,6788 ****
--- 6826,6832 ----
struct induction *g1, *g2, **giv_array;
int i, j, k, giv_count;
struct combine_givs_stats *stats;
+ regset regs_used;
rtx *can_combine;
/* Count givs, because bl->giv_count is incorrect here. */
*************** combine_givs (bl)
*** 6804,6815 ****
can_combine = (rtx *) alloca (giv_count * giv_count * sizeof(rtx));
bzero ((char *) can_combine, giv_count * giv_count * sizeof(rtx));
for (i = 0; i < giv_count; i++)
{
! int this_benefit;
rtx single_use;
g1 = giv_array[i];
stats[i].giv_number = i;
/* If a DEST_REG GIV is used only once, do not allow it to combine
--- 6848,6863 ----
can_combine = (rtx *) alloca (giv_count * giv_count * sizeof(rtx));
bzero ((char *) can_combine, giv_count * giv_count * sizeof(rtx));
+ regs_used = ALLOCA_REG_SET ();
+
for (i = 0; i < giv_count; i++)
{
! int this_benefit, this_reg_count;
rtx single_use;
g1 = giv_array[i];
+ stats[i].reg_count = 0;
+ stats[i].total_benefit = 0;
stats[i].giv_number = i;
/* If a DEST_REG GIV is used only once, do not allow it to combine
*************** combine_givs (bl)
*** 6828,6833 ****
--- 6876,6884 ----
if (g1->no_const_addval)
this_benefit += 1;
+ CLEAR_REG_SET (regs_used);
+ this_reg_count = 0;
+
for (j = 0; j < giv_count; j++)
{
rtx this_combine;
*************** combine_givs (bl)
*** 6838,6845 ****
--- 6889,6899 ----
{
can_combine[i*giv_count + j] = this_combine;
this_benefit += g2->benefit + extra_benefit;
+ this_reg_count += combine_givs_count_regs(this_combine,regs_used);
}
}
+
+ stats[i].reg_count = this_reg_count;
stats[i].total_benefit = this_benefit;
}
*************** restart:
*** 6854,6861 ****
{
g1 = giv_array[stats[k].giv_number];
if (!g1->combined_with && !g1->same)
! fprintf (loop_dump_stream, " {%d, %d}",
INSN_UID (giv_array[stats[k].giv_number]->insn),
stats[k].total_benefit);
}
putc ('\n', loop_dump_stream);
--- 6908,6916 ----
{
g1 = giv_array[stats[k].giv_number];
if (!g1->combined_with && !g1->same)
! fprintf (loop_dump_stream, " {%d,%d,%d}",
INSN_UID (giv_array[stats[k].giv_number]->insn),
+ stats[k].reg_count,
stats[k].total_benefit);
}
putc ('\n', loop_dump_stream);
*************** restart:
*** 6921,6926 ****
--- 6976,6984 ----
stats[j].total_benefit -= g1->benefit + extra_benefit;
}
+ /* ??? Recompute register usage -- too bad we can't do it
+ by subtraction like we did total_benefit. */
+
g1->benefit += g1_add_benefit;
/* We've finished with this giv, and everything it touched.
*************** restart:
*** 6932,6937 ****
--- 6990,6997 ----
goto restart;
}
}
+
+ FREE_REG_SET (regs_used);
}
struct recombine_givs_stats
More information about the Gcc-patches
mailing list