This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
giv combination patch mark 2
> I've got some improvements I want to make this evening; perhaps
> I'll find the bug by inspection ...
I did find a bit in which I was using an uninitialized variable,
so maybe I got it.
One current shortcoming in the code is that if it finds eg on m68k
Biv 39 initialized at insn 48: initial value 2
Insn 62: giv reg 52 src reg 39 benefit 6 used 1 replaceable mult 4 add -4
Insn 81: dest address src reg 39 benefit 10 used 1 replaceable mult 4
add (plus:SI (reg/v/u:SI 29)
(const_int -4))
the search in combine_givs will not search the raw bivs, and so we get
fmove.s %fp0,(%a2,%d1.l)
addq.l #4,%d1
instead of a potential fmove.s %fp0,(%a2,%d0.l,4). Hmm, well actually
fmove has a restricted set of modes doesn't it so that was a bad example.
Anyway, the case holds as well for some x86 examples where the modes
are availible.
Anyone know if anything bad would happen if a giv with mult 1 add 0
was added for every biv? Or, more to the point, why they are kept
separately?
Unchanged from the previous patch is the lack of ability to recognize
indexes through rank 2 dynamic arrays.
r~
Sun Dec 14 03:27:16 1997 Richard Henderson <rth@cygnus.com>
* loop.c (basic_induction_var) [REG]: Don't just search the previous
insn, but continue back to the beginning of the loop or to a label.
(express_from_1): New function.
(express_from): Allow more complex add_val than just CONST_INT.
(combine_givs_p): Use rtx_cost if ADDRESS_COST is not available.
(giv_sort): Handle more complex add_val genericly.
(combine_givs): Always sort givs.
Index: loop.c
===================================================================
RCS file: /cvs/cvsfiles/egcs/gcc/loop.c,v
retrieving revision 1.22
diff -u -p -d -r1.22 loop.c
--- loop.c 1997/12/07 00:28:53 1.22
+++ loop.c 1997/12/14 11:27:58
@@ -5146,30 +5146,36 @@ basic_induction_var (x, mode, dest_reg,
return 0;
case REG:
- /* If this register is assigned in the previous insn, look at its
+ /* If this register is assigned in a previous insn, look at its
source, but don't go outside the loop or past a label. */
- for (insn = PREV_INSN (p);
- (insn && GET_CODE (insn) == NOTE
- && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
- insn = PREV_INSN (insn))
- ;
+ insn = p;
+ while (1)
+ {
+ do {
+ insn = PREV_INSN (insn);
+ } while (insn && GET_CODE (insn) == NOTE
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
- if (insn)
- set = single_set (insn);
+ if (!insn)
+ break;
+ set = single_set (insn);
+ if (set == 0)
+ break;
- if (set != 0
- && (SET_DEST (set) == x
- || (GET_CODE (SET_DEST (set)) == SUBREG
- && (GET_MODE_SIZE (GET_MODE (SET_DEST (set)))
- <= UNITS_PER_WORD)
- && SUBREG_REG (SET_DEST (set)) == x)))
- return basic_induction_var (SET_SRC (set),
- (GET_MODE (SET_SRC (set)) == VOIDmode
- ? GET_MODE (x)
- : GET_MODE (SET_SRC (set))),
- dest_reg, insn,
- inc_val, mult_val);
+ if ((SET_DEST (set) == x
+ || (GET_CODE (SET_DEST (set)) == SUBREG
+ && (GET_MODE_SIZE (GET_MODE (SET_DEST (set)))
+ <= UNITS_PER_WORD)
+ && SUBREG_REG (SET_DEST (set)) == x))
+ && basic_induction_var (SET_SRC (set),
+ (GET_MODE (SET_SRC (set)) == VOIDmode
+ ? GET_MODE (x)
+ : GET_MODE (SET_SRC (set))),
+ dest_reg, insn,
+ inc_val, mult_val))
+ return 1;
+ }
/* ... fall through ... */
/* Can accept constant setting of biv only when inside inner most loop.
@@ -5711,9 +5717,115 @@ consec_sets_giv (first_benefit, p, src_r
G2 = c * v + d
where `v' is the biv.
- So G2 = (c/a) * G1 + (d - b*c/a) */
+ So G2 = (c/a) * G1 + (d - b*c/a)
+
+ Update: B and D are now allowed to be additive expressions such that
+ D contains all variables in B. That is, computing D-B will not require
+ subtracting variables. */
+
+static rtx
+express_from_1 (a, b, mult)
+ rtx a, b;
+ HOST_WIDE_INT mult;
+{
+ /* In general these structures are sorted top to bottom (down the PLUS
+ chain), but not left to right across the PLUS. If B is a higher
+ order giv than A, we can strip one level and recurse. If A is higher
+ order, we'll eventually abort, but won't know that until the end.
+ If they are the same, we'll strip one level around this loop. */
+
+ while (GET_CODE (a) == PLUS && GET_CODE (b) == PLUS)
+ {
+ rtx ra, rb, oa, ob;
+
+ if (GET_CODE (XEXP (a, 0)) == REG)
+ ra = XEXP (a, 0), oa = XEXP (a, 1);
+ else if (GET_CODE (XEXP (a, 1)) == REG)
+ ra = XEXP (a, 1), oa = XEXP (a, 0);
+ else
+ return NULL_RTX;
+
+ if (GET_CODE (XEXP (b, 0)) == REG)
+ rb = XEXP (b, 0), ob = XEXP (b, 1);
+ else if (GET_CODE (XEXP (b, 1)) == REG)
+ rb = XEXP (b, 1), ob = XEXP (b, 0);
+ else
+ return NULL_RTX;
+
+ if (REGNO (ra) == REGNO (rb))
+ {
+ /* We matched: remove one reg completely. */
+ a = oa;
+ b = ob;
+ }
+ else if (GET_CODE (ob) == REG && REGNO (ra) == REGNO (ob))
+ {
+ /* An alternate match. */
+ a = oa;
+ b = rb;
+ }
+ else
+ {
+ /* Indicates an extra register in B. Strip one level from B and
+ recurse, hoping B was the higher order expression. */
+ ob = express_from_1 (a, ob, mult);
+ if (ob == NULL_RTX)
+ return NULL_RTX;
+ return gen_rtx (PLUS, GET_MODE (b), rb, ob);
+ }
+ }
+
+ /* Here we are at the last level of A, go through the cases hoping to
+ get rid of everything but a constant. */
+
+ if (GET_CODE (a) == PLUS)
+ {
+ rtx ra, oa;
+
+ if (GET_CODE (XEXP (a, 0)) == REG)
+ ra = XEXP (a, 0), oa = XEXP (a, 1);
+ else if (GET_CODE (XEXP (a, 1)) == REG)
+ ra = XEXP (a, 1), oa = XEXP (a, 0);
+ else
+ return NULL_RTX;
+
+ if (GET_CODE (b) != REG
+ || REGNO (ra) != REGNO (b)
+ || GET_CODE (oa) != CONST_INT)
+ return NULL_RTX;
+
+ return GEN_INT (- INTVAL (oa) * mult);
+ }
+ else if (GET_CODE (a) == REG)
+ {
+ if (GET_CODE (b) == PLUS)
+ {
+ rtx rb, ob;
+
+ if (GET_CODE (XEXP (b, 0)) == REG)
+ rb = XEXP (b, 0), ob = XEXP (b, 1);
+ else if (GET_CODE (XEXP (b, 1)) == REG)
+ rb = XEXP (b, 1), ob = XEXP (b, 0);
+ else
+ return NULL_RTX;
+
+ return (REGNO (a) == REGNO (rb) ? ob : NULL_RTX);
+ }
+ if (GET_CODE (b) != REG
+ || REGNO (a) != REGNO (b))
+ return NULL_RTX;
+
+ return const0_rtx;
+ }
+ else if (GET_CODE (a) == CONST_INT)
+ {
+ return plus_constant (b, -INTVAL (a) * mult);
+ }
+
+ return NULL_RTX;
+}
+
-#ifdef ADDRESS_COST
static rtx
express_from (g1, g2)
struct induction *g1, *g2;
@@ -5725,13 +5837,15 @@ express_from (g1, g2)
for notation) is also an integer. */
if (GET_CODE (g1->mult_val) != CONST_INT
|| GET_CODE (g2->mult_val) != CONST_INT
- || GET_CODE (g1->add_val) != CONST_INT
|| g1->mult_val == const0_rtx
|| INTVAL (g2->mult_val) % INTVAL (g1->mult_val) != 0)
- return 0;
+ return NULL_RTX;
mult = GEN_INT (INTVAL (g2->mult_val) / INTVAL (g1->mult_val));
- add = plus_constant (g2->add_val, - INTVAL (g1->add_val) * INTVAL (mult));
+
+ add = express_from_1 (g1->add_val, g2->add_val);
+ if (add == NULL_RTX)
+ return NULL_RTX;
/* Form simplified final result. */
if (mult == const0_rtx)
@@ -5746,7 +5860,6 @@ express_from (g1, g2)
else
return gen_rtx (PLUS, g2->mode, mult, add);
}
-#endif
/* Return 1 if giv G2 can be combined with G1. This means that G2 can use
(either directly or via an address expression) a register used to represent
@@ -5767,37 +5880,89 @@ combine_givs_p (g1, g2)
return 1;
}
-#ifdef ADDRESS_COST
/* If G2 can be expressed as a function of G1 and that function is valid
as an address and no more expensive than using a register for G2,
the expression of G2 in terms of G1 can be used. */
if (g2->giv_type == DEST_ADDR
&& (tem = express_from (g1, g2)) != 0
&& memory_address_p (g2->mem_mode, tem)
- && ADDRESS_COST (tem) <= ADDRESS_COST (*g2->location))
+#ifdef ADDRESS_COST
+ && ADDRESS_COST (tem) <= ADDRESS_COST (*g2->location)
+#else
+ && rtx_cost (tem, MEM) <= rtx_cost (*g2->location, MEM)
+#endif
+ )
{
g2->new_reg = tem;
return 1;
}
-#endif
return 0;
}
-#ifdef GIV_SORT_CRITERION
-/* Compare two givs and sort the most desirable one for combinations first.
- This is used only in one qsort call below. */
+/* Compare two givs and sort sorting for lower PLUS nesting depth first,
+ then lower constants. This is used only in one qsort call below. */
static int
giv_sort (x, y)
struct induction **x, **y;
{
- GIV_SORT_CRITERION (*x, *y);
+ rtx a, b, a_const, b_const;
+ int a_depth, b_depth;
+
+ a = (*x)->add_val;
+ a_const = NULL_RTX;
+ a_depth = 0;
+ if (GET_CODE (a) == PLUS)
+ {
+ while (1)
+ {
+ a_depth++;
+ if (GET_CODE (XEXP (a, 0)) == PLUS)
+ a = XEXP (a, 0);
+ else if (GET_CODE (XEXP (a, 1)) == PLUS)
+ a = XEXP (a, 1);
+ else
+ break;
+ }
+ if (GET_CODE (XEXP (a, 1)) == CONST_INT)
+ a_const = XEXP (a, 1);
+ }
+ else if (GET_CODE (a) == CONST_INT)
+ a_const = a, a_depth = 10000;
+ b = (*y)->add_val;
+ b_const = NULL_RTX;
+ b_depth = 0;
+ if (GET_CODE (b) == PLUS)
+ {
+ while (1)
+ {
+ b_depth++;
+ if (GET_CODE (XEXP (b, 0)) == PLUS)
+ b = XEXP (b, 0);
+ else if (GET_CODE (XEXP (b, 1)) == PLUS)
+ b = XEXP (b, 1);
+ else
+ break;
+ }
+ if (GET_CODE (XEXP (b, 1)) == CONST_INT)
+ b_const = XEXP (b, 1);
+ }
+ else if (GET_CODE (b) == CONST_INT)
+ b_const = b, b_depth = 10000;
+
+ if (a_depth != b_depth)
+ return a_depth - b_depth;
+ if (GET_CODE ((*x)->mult_val) == CONST_INT
+ && GET_CODE ((*y)->mult_val) == CONST_INT
+ && INTVAL ((*x)->mult_val) != INTVAL ((*y)->mult_val))
+ return INTVAL ((*y)->mult_val) - INTVAL ((*x)->mult_val);
+ if (a_const && b_const)
+ return INTVAL (a_const) - INTVAL (b_const);
return 0;
}
-#endif
-
+
/* 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
@@ -5821,16 +5986,21 @@ combine_givs (bl)
for (g1 = bl->giv; g1; g1 = g1->next_iv)
giv_array[i++] = g1;
-#ifdef GIV_SORT_CRITERION
- /* Sort the givs if GIV_SORT_CRITERION is defined.
- This is usually defined for processors which lack
- negative register offsets so more givs may be combined. */
+ /* Sort the givs. This not only helps out processors which lack negative
+ register offsets, but also often eliminates a pointless addition at the
+ start of the loop. */
if (loop_dump_stream)
- fprintf (loop_dump_stream, "%d givs counted, sorting...\n", giv_count);
+ fprintf (loop_dump_stream, "%d givs counted, sorting:\n", giv_count);
qsort (giv_array, giv_count, sizeof (struct induction *), giv_sort);
-#endif
+
+ if (loop_dump_stream)
+ {
+ for (i = 0; i < giv_count; ++i)
+ fprintf (loop_dump_stream, " %d", INSN_UID (giv_array[i]->insn));
+ fprintf (loop_dump_stream, "\n");
+ }
for (i = 0; i < giv_count; i++)
{
Index: toplev.c
===================================================================
RCS file: /cvs/cvsfiles/egcs/gcc/toplev.c,v
retrieving revision 1.24
diff -u -p -d -r1.24 toplev.c
--- toplev.c 1997/12/12 08:50:19 1.24
+++ toplev.c 1997/12/14 11:27:59
@@ -3894,7 +3894,6 @@ main (argc, argv, envp)
flag_expensive_optimizations = 1;
flag_strength_reduce = 1;
flag_rerun_cse_after_loop = 1;
- flag_rerun_loop_opt = 1;
flag_caller_saves = 1;
flag_force_mem = 1;
#ifdef INSN_SCHEDULING