self@BAYES.ARC.NASA.GOV (Matthew Self) (03/17/89)
Here are some patches which improve strength-reduction in GCC.
These changes permit the complete elimination of basic induction
variables if all of their general induction variables have been
reduced. I have tested these changes a fair amount, but I would
appreciate it if others would test it too. In any case, it will make
your loops run faster!
After these changes, the following two functions generate exactly
the same inner loop. (Well, one drops straight in, and the other
jumps in, but...)
int sum (int *a, int n)
{
int s = 0;
int i;
for (i = 0; i < n; i++)
s += a[i];
return s;
}
int sum2 (int *a, int n)
{
int s = 0;
int *a_ptr;
for (a_ptr = a; a_ptr < a + n; a_ptr++)
s += *a_ptr;
return s;
}
On the m68k this results in the following assembler: (If you installed
the patches to the m68k.md to speed up compare instructions....)
L5:
addl a0@+,d1
cmpl a0,d0
jgt L5
It's hard to do much better than that!
Cheers,
--Matthew
*** loop.c.orig Tue Mar 14 23:51:59 1989
--- loop.c Wed Mar 15 00:33:08 1989
***************
*** 1904,1907 ****
--- 1904,1911 ----
/* A `struct iv_class' is created for each biv. */
+ /* init_val_set replaced by init_insn. Initially zero for each biv,
+ Set to the insn which intializes the biv, or if zero if we can't
+ find one. March 14, 1989 -- self@bayes.arc.nasa.gov */
+
struct iv_class {
int regno; /* Pseudo reg which is the biv. */
***************
*** 1914,1919 ****
rtx initial_value; /* Value of reg at loop start */
struct iv_class *next; /* Links all class structures together */
! char init_val_set; /* Used during scan for initial value,
! 1 if assignment seen, 0 otherwise. */
char eliminable; /* 1 if plausible candidate for elimination. */
char nonneg; /* 1 if we added a REG_NONNEG note for this. */
--- 1918,1922 ----
rtx initial_value; /* Value of reg at loop start */
struct iv_class *next; /* Links all class structures together */
! rtx init_insn; /* insn which intializes biv, 0 if none seen. */
char eliminable; /* 1 if plausible candidate for elimination. */
char nonneg; /* 1 if we added a REG_NONNEG note for this. */
***************
*** 2095,2099 ****
/* Set initial value to the reg itself. */
bl->initial_value = SET_DEST (PATTERN (p));
! bl->init_val_set = 0;
bl->eliminable = 0;
bl->nonneg = 0;
--- 2098,2103 ----
/* Set initial value to the reg itself. */
bl->initial_value = SET_DEST (PATTERN (p));
! /* We haven't seen the intializing insn yet */
! bl->init_insn = 0;
bl->eliminable = 0;
bl->nonneg = 0;
***************
*** 2117,2120 ****
--- 2121,2127 ----
fprintf (loop_dump_stream, " const = %d\n",
INTVAL (inc_val));
+ else if (GET_CODE (inc_val) == REG)
+ fprintf (loop_dump_stream, "const = reg %d\n",
+ REGNO (inc_val));
else
{
***************
*** 2201,2208 ****
if (induct_var[dest_regno] == BASIC_INDUCT
! && class_struct[dest_regno]->init_val_set == 0)
{
/* This is the first modification found for this reg. */
/* Save value if it is a constant or register. */
if (GET_CODE (SET_SRC (PATTERN (p))) == CONST_INT
--- 2208,2223 ----
if (induct_var[dest_regno] == BASIC_INDUCT
! && class_struct[dest_regno]->init_insn == 0)
{
/* This is the first modification found for this reg. */
+ /* Record the intializing INSN */
+
+ class_struct[dest_regno]->init_insn = p;
+
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream, "biv %d initialized at insn %d.\n",
+ dest_regno, INSN_UID (p));
+
/* Save value if it is a constant or register. */
if (GET_CODE (SET_SRC (PATTERN (p))) == CONST_INT
***************
*** 2220,2226 ****
fprintf (loop_dump_stream, "%d\n",
INTVAL (SET_SRC (PATTERN (p))));
! else
fprintf (loop_dump_stream, "reg %d\n",
REGNO (SET_SRC (PATTERN (p))));
}
}
--- 2235,2246 ----
fprintf (loop_dump_stream, "%d\n",
INTVAL (SET_SRC (PATTERN (p))));
! else if (GET_CODE (SET_SRC (PATTERN (p))) == REG)
fprintf (loop_dump_stream, "reg %d\n",
REGNO (SET_SRC (PATTERN (p))));
+ else
+ {
+ print_rtl (loop_dump_stream, SET_SRC (PATTERN (p)));
+ fprintf (loop_dump_stream, "\n");
+ }
}
}
***************
*** 2235,2239 ****
}
- class_struct[dest_regno]->init_val_set = 1;
biv_found--;
}
--- 2255,2258 ----
***************
*** 2375,2381 ****
??? That should be only on machines that have dbra insns. */
if ((uid_luid[regno_last_uid[bl->regno]] < INSN_LUID (loop_end)
! && uid_luid[regno_first_uid[bl->regno]] > INSN_LUID (loop_start)
! && bl->init_val_set && ! bl->nonneg)
|| (final_value = final_biv_value (bl, loop_end)))
{
--- 2394,2413 ----
??? That should be only on machines that have dbra insns. */
+ /* Compare against bl->init_insn rather than loop_start.
+ We aren't concerned with any uses of the biv between
+ init_insn and loop_start since these won't be affected
+ by the value of the biv elsewhere in the function, so
+ long as init_insn doesn't use the biv itself.
+ March 14, 1989 -- self@bayes.arc.nasa.gov
+
+ ?? Why do we care if init_insn has been set? Can't we
+ just use loop_start instead of init_insn in this case? */
+
if ((uid_luid[regno_last_uid[bl->regno]] < INSN_LUID (loop_end)
! && bl->init_insn
! && uid_luid[regno_first_uid[bl->regno]] >= INSN_LUID (bl->init_insn)
! && ! reg_mentioned_p (SET_DEST (PATTERN (bl->biv->insn)),
! SET_SRC (PATTERN (bl->init_insn)))
! && ! bl->nonneg)
|| (final_value = final_biv_value (bl, loop_end)))
{
***************
*** 2392,2396 ****
then we can't eliminate the biv. */
if (GET_CODE (PATTERN (p)) != SET)
! break;
/* The insns that increment the biv are no problem. */
--- 2424,2434 ----
then we can't eliminate the biv. */
if (GET_CODE (PATTERN (p)) != SET)
! {
! if (loop_dump_stream)
! fprintf (loop_dump_stream,
! "Cannot eliminate biv %d: cannot understand insn %d.\n",
! bl->regno, INSN_UID (p));
! break;
! }
/* The insns that increment the biv are no problem. */
***************
*** 2402,2410 ****
continue;
! /* If this is an insn which computes a giv, no problem,
! because it will go away if the giv is reduced. */
for (v = bl->giv; v; v = v->family)
! if (!v->ignore && v->insn == p && v->giv_type == DEST_REG)
! break;
if (v)
continue;
--- 2440,2456 ----
continue;
! /* If this is an insn which uses the biv ONLY in the
! calculation of a giv which is in the family of this
! biv, it's ok becuase it will go away when the giv is
! reduced. March 14, 1989 -- self@bayes.arc.nasa.gov */
for (v = bl->giv; v; v = v->family)
! if (v->insn == p)
! {
! if (v->giv_type == DEST_REG
! || (v->giv_type == DEST_ADDR
! && only_reg_use_p (reg, *(v->location),
! PATTERN (p))))
! break;
! }
if (v)
continue;
***************
*** 2411,2414 ****
--- 2457,2464 ----
/* Biv is used in a way we cannot eliminate. */
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Cannot eliminate biv %d: biv used in insn %d.\n",
+ bl->regno, INSN_UID (p));
break;
}
***************
*** 2422,2429 ****
bl->regno);
}
- else if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Cannot eliminate biv %d due to insn %d.\n",
- bl->regno, INSN_UID (p));
}
else
--- 2472,2475 ----
***************
*** 2430,2436 ****
{
if (loop_dump_stream)
! fprintf (loop_dump_stream,
! "Cannot eliminate biv %d: used outside the loop\n",
! bl->regno);
}
--- 2476,2488 ----
{
if (loop_dump_stream)
! {
! fprintf (loop_dump_stream,
! "Cannot eliminate biv %d: used outside the loop.\n",
! bl->regno);
! fprintf (loop_dump_stream,
! "First use: insn %d, last use: insn %d.\n",
! uid_luid[regno_first_uid[bl->regno]],
! uid_luid[regno_last_uid[bl->regno]]);
! }
}
***************
*** 2671,2674 ****
--- 2723,2732 ----
delete_insn (v->insn);
+ /* ?? If we created a new test to bypass the loop entirely,
+ or otherwise drop straight in, based on this test, then
+ we might want to rewrite it also. This way some later
+ pass has more hope of removing the intialization of this
+ biv entirely. */
+
/* If final_value != 0, then biv may be used after loop end
and we must emit an insn to set it just in case. */
***************
*** 2692,2695 ****
--- 2750,2814 ----
}
+ /* Nonzero if register REG appears nowhere within IN, except
+ in subexpressions EQ to EXPR. This is a modification of
+ reg_mentioned_p in rtl.c
+ March 14, 1989 -- self@bayes.arc.nasa.gov */
+
+ int
+ only_reg_use_p (reg, expr, in)
+ register rtx reg, expr, in;
+ {
+ register char *fmt;
+ register int i;
+ register enum rtx_code code;
+
+ if (in == 0)
+ return 0;
+
+ if (reg == expr) /* this is the only line different */
+ return 0; /* from reg_mentioned_p. */
+
+ if (reg == in)
+ return 1;
+
+ code = GET_CODE (in);
+
+ switch (code)
+ {
+ /* Compare registers by number. */
+ case REG:
+ return GET_CODE (reg) == REG && REGNO (in) == REGNO (reg);
+
+ /* These codes have no constituent expressions
+ and are unique. */
+ case CC0:
+ case PC:
+ return 0;
+
+ case CONST_INT:
+ return GET_CODE (reg) == CONST_INT && INTVAL (in) == INTVAL (reg);
+ }
+
+ if (GET_CODE (reg) == code && rtx_equal_p (reg, in))
+ return 1;
+
+ fmt = GET_RTX_FORMAT (code);
+
+ for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ {
+ if (fmt[i] == 'E')
+ {
+ register int j;
+ for (j = XVECLEN (in, i) - 1; j >= 0; j--)
+ if (reg_mentioned_p (reg, XVECEXP (in, i, j)))
+ return 1;
+ }
+ else if (fmt[i] == 'e'
+ && reg_mentioned_p (reg, XEXP (in, i)))
+ return 1;
+ }
+ return 0;
+ }
+
/* Scan X for memory refs and check each memory address
as a possible giv. INSN is the insn whose pattern X comes from.
***************
*** 2950,2953 ****
--- 3069,3075 ----
fprintf (loop_dump_stream, " add %d",
INTVAL (add_val));
+ else if (GET_CODE (add_val) == REG)
+ fprintf (loop_dump_stream, " add reg %d",
+ REGNO (add_val));
else
{
*** loop.c Wed Mar 15 00:33:08 1989
--- loop.c-2 Wed Mar 15 15:32:57 1989
***************
*** 1863,1866 ****
--- 1863,1869 ----
an induction variable (either a biv or a giv). */
+ /* Added mode field to record mode of iv. This doesn't always get
+ set, so don't use it yet! March 15, 1989 -- self@bayes.arc.nasa.gov */
+
struct induction
{
***************
*** 1877,1880 ****
--- 1880,1884 ----
rtx *location; /* Place in the insn where this giv occurs.
If GIV_TYPE is DEST_REG, this is 0. */
+ enum machine_mode mode; /* The mode of this biv or giv */
rtx mult_val; /* Multiplicative factor for src_reg. */
rtx add_val; /* Additive constant for that product. */
***************
*** 2436,2443 ****
continue;
- /* If can rewrite this insn not to use the biv, it's ok. */
- if (can_eliminate_biv_p (p, bl))
- continue;
-
/* If this is an insn which uses the biv ONLY in the
calculation of a giv which is in the family of this
--- 2440,2443 ----
***************
*** 2456,2459 ****
--- 2456,2463 ----
continue;
+ /* If can rewrite this insn not to use the biv, it's ok. */
+ if (can_eliminate_biv_p (p, bl))
+ continue;
+
/* Biv is used in a way we cannot eliminate. */
if (loop_dump_stream)
***************
*** 2923,2926 ****
--- 2927,2931 ----
if (type == DEST_ADDR)
{
+ v->mode = GET_MODE (*location);
v->consec = 0;
v->lifetime = 1;
***************
*** 2927,2932 ****
v->times_used = 1;
}
! else
{
v->consec = n_times_set[dest_regno] - 1;
v->lifetime = (uid_luid[regno_last_uid[dest_regno]]
--- 2932,2938 ----
v->times_used = 1;
}
! else /* type == DEST_REG */
{
+ v->mode = GET_MODE (SET_DEST (PATTERN (insn)));
v->consec = n_times_set[dest_regno] - 1;
v->lifetime = (uid_luid[regno_last_uid[dest_regno]]
***************
*** 4445,4448 ****
--- 4451,4458 ----
The following function is very parallel to this one. */
+ /* Modified mode checking to take into account DEST_ADDR giv's.
+ Replace this mess with (v->mode == mode) once it is working.
+ March 15, 1989 -- self@bayes.arc.nasa.gov */
+
static int
can_eliminate_biv_p (insn, bl)
***************
*** 4473,4477 ****
for (v = bl->giv; v; v = v->family)
if (v->mult_val != const0_rtx && v->add_val == const0_rtx
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
return 1;
--- 4483,4490 ----
for (v = bl->giv; v; v = v->family)
if (v->mult_val != const0_rtx && v->add_val == const0_rtx
! && ((v->giv_type == DEST_REG
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
! || (v->giv_type == DEST_ADDR
! && (GET_MODE (*(v->location)) == mode))))
return 1;
***************
*** 4481,4486 ****
for (v = bl->giv; v; v = v->family)
if (v->mult_val != const0_rtx
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
return 1;
return 0;
--- 4494,4505 ----
for (v = bl->giv; v; v = v->family)
if (v->mult_val != const0_rtx
! && ((v->giv_type == DEST_REG
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
! || (v->giv_type == DEST_ADDR
! && (GET_MODE (*(v->location)) == mode))))
return 1;
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream, "Cannot eliminate biv %d in test insn %d: no appropriate giv.\n",
+ bl->regno, INSN_UID (insn));
return 0;
***************
*** 4507,4511 ****
if (GET_CODE (v->mult_val) == CONST_INT
&& GET_CODE (v->add_val) == CONST_INT
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
return 1;
--- 4526,4533 ----
if (GET_CODE (v->mult_val) == CONST_INT
&& GET_CODE (v->add_val) == CONST_INT
! && ((v->giv_type == DEST_REG
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
! || (v->giv_type == DEST_ADDR
! && (GET_MODE (*(v->location)) == mode))))
return 1;
***************
*** 4516,4520 ****
for (v = bl->giv; v; v = v->family)
if (GET_CODE (v->mult_val) == CONST_INT
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
return 1;
}
--- 4538,4545 ----
for (v = bl->giv; v; v = v->family)
if (GET_CODE (v->mult_val) == CONST_INT
! && ((v->giv_type == DEST_REG
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
! || (v->giv_type == DEST_ADDR
! && (GET_MODE (*(v->location)) == mode))))
return 1;
}
***************
*** 4530,4534 ****
for (v = bl->giv; v; v = v->family)
if ((GET_CODE (v->mult_val) == CONST_INT)
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
return 1;
}
--- 4555,4562 ----
for (v = bl->giv; v; v = v->family)
if ((GET_CODE (v->mult_val) == CONST_INT)
! && ((v->giv_type == DEST_REG
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
! || (v->giv_type == DEST_ADDR
! && (GET_MODE (*(v->location)) == mode))))
return 1;
}
***************
*** 4542,4546 ****
values for mult_val and add_val. */
for (v = bl->giv; v; v = v->family)
! if (GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
{
for (tv = class_struct[REGNO (arg)]->giv; tv; tv = tv->family)
--- 4570,4577 ----
values for mult_val and add_val. */
for (v = bl->giv; v; v = v->family)
! if ((v->giv_type == DEST_REG
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
! || (v->giv_type == DEST_ADDR
! && (GET_MODE (*(v->location)) == mode)))
{
for (tv = class_struct[REGNO (arg)]->giv; tv; tv = tv->family)
***************
*** 4548,4552 ****
&& rtx_equal_p (tv->mult_val, v->mult_val)
&& rtx_equal_p (tv->mult_val, v->mult_val)
! && GET_MODE (SET_DEST (PATTERN (tv->insn))) == mode)
return 1;
}
--- 4579,4586 ----
&& rtx_equal_p (tv->mult_val, v->mult_val)
&& rtx_equal_p (tv->mult_val, v->mult_val)
! && ((v->giv_type == DEST_REG
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
! || (v->giv_type == DEST_ADDR
! && (GET_MODE (*(v->location)) == mode))))
return 1;
}
***************
*** 4589,4593 ****
if (v->mult_val != const0_rtx && v->add_val == const0_rtx
&& v->new_reg != 0
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
break;
if (v)
--- 4623,4630 ----
if (v->mult_val != const0_rtx && v->add_val == const0_rtx
&& v->new_reg != 0
! && ((v->giv_type == DEST_REG
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
! || (v->giv_type == DEST_ADDR
! && (GET_MODE (*(v->location)) == mode))))
break;
if (v)
***************
*** 4603,4607 ****
for (v = bl->giv; v; v = v->family)
if (v->mult_val != const0_rtx && v->new_reg != 0
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
break;
if (v)
--- 4640,4647 ----
for (v = bl->giv; v; v = v->family)
if (v->mult_val != const0_rtx && v->new_reg != 0
! && ((v->giv_type == DEST_REG
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
! || (v->giv_type == DEST_ADDR
! && (GET_MODE (*(v->location)) == mode))))
break;
if (v)
***************
*** 4647,4651 ****
&& GET_CODE (v->add_val) == CONST_INT
&& v->new_reg
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
break;
if (v)
--- 4687,4694 ----
&& GET_CODE (v->add_val) == CONST_INT
&& v->new_reg
! && ((v->giv_type == DEST_REG
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
! || (v->giv_type == DEST_ADDR
! && (GET_MODE (*(v->location)) == mode))))
break;
if (v)
***************
*** 4666,4670 ****
if (GET_CODE (v->mult_val) == CONST_INT
&& v->new_reg
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
break;
if (v)
--- 4709,4716 ----
if (GET_CODE (v->mult_val) == CONST_INT
&& v->new_reg
! && ((v->giv_type == DEST_REG
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
! || (v->giv_type == DEST_ADDR
! && (GET_MODE (*(v->location)) == mode))))
break;
if (v)
***************
*** 4696,4700 ****
if (GET_CODE (v->mult_val) == CONST_INT
&& v->new_reg
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
break;
if (v)
--- 4742,4749 ----
if (GET_CODE (v->mult_val) == CONST_INT
&& v->new_reg
! && ((v->giv_type == DEST_REG
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
! || (v->giv_type == DEST_ADDR
! && (GET_MODE (*(v->location)) == mode))))
break;
if (v)
***************
*** 4728,4732 ****
{
if (!v->new_reg
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
continue;
for (tv = class_struct[REGNO (arg)]->giv; tv; tv = tv->family)
--- 4777,4784 ----
{
if (!v->new_reg
! && ((v->giv_type == DEST_REG
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
! || (v->giv_type == DEST_ADDR
! && (GET_MODE (*(v->location)) == mode))))
continue;
for (tv = class_struct[REGNO (arg)]->giv; tv; tv = tv->family)
***************
*** 4734,4738 ****
&& rtx_equal_p (tv->mult_val, v->mult_val)
&& rtx_equal_p (tv->mult_val, v->mult_val)
! && GET_MODE (SET_DEST (PATTERN (tv->insn))) == mode)
break;
if (tv)
--- 4786,4793 ----
&& rtx_equal_p (tv->mult_val, v->mult_val)
&& rtx_equal_p (tv->mult_val, v->mult_val)
! && ((v->giv_type == DEST_REG
! && GET_MODE (SET_DEST (PATTERN (v->insn))) == mode)
! || (v->giv_type == DEST_ADDR
! && (GET_MODE (*(v->location)) == mode))))
break;
if (tv)meissner@bert.dg.com (Michael Meissner) (03/28/89)
I just tried this out with GCC 1.34, and found that it exposes a latent bug in loop optimization caused by 1.34. I tried to recompile the 88k compiler with it, and when I got to global-alloc.c, it aborted with an insn not found. The insn involved looked like: (set cc0 (minus (match_operand:SI 0 "register_operand" "r") (const_int 0))) This was how you set the condition code under 1.33 and before. However, under 1.34 a new RTL operator was added 'compare', so the RTX should look like: (set cc0 (compare (match_operand:SI 0 "register_operand" "r") (const_int 0))) I will look at this on my own, but this quick description might set off bells for somebody more familar with that section of code. Michael Meissner, Data General. Uucp: ...!mcnc!rti!xyzzy!meissner If compiles were much Internet: meissner@dg-rtp.DG.COM faster, when would we Old Internet: meissner%dg-rtp.DG.COM@relay.cs.net have time for netnews?