This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Proposed patch for loop.c
- To: egcs-patches at cygnus dot com, egcs at cygnus dot com
- Subject: Proposed patch for loop.c
- From: Bernd Schmidt <crux at Pool dot Informatik dot RWTH-Aachen dot DE>
- Date: Thu, 28 May 1998 11:26:21 +0200 (MET DST)
I've been trying to find out why the strength-reduce pass occasionally
generates awful code on the i386. First, an example to demonstrate what
I'm talking about (to the left the "normal" code generated by egcs-980525,
to the right the code that is generated with the patch below).
flush_signal_handlers: flush_signal_handlers:
pushl %ebx | movl 4(%esp),%eax
movl 8(%esp),%eax <
movl 912(%eax),%eax movl 912(%eax),%eax
movl $64,%ebx | movl $64,%edx
leal 4(%eax),%edx | addl $4,%eax
leal 16(%eax),%ecx <
addl $20,%eax <
.align 4 .align 4
.L706: .L706:
cmpl $1,(%edx) | cmpl $1,(%eax)
je .L707 je .L707
movl $0,(%edx) <
.L707: <
movl $0,-12(%eax) <
movl $0,(%eax) movl $0,(%eax)
addl $20,%edx | .L707:
movl $0,(%ecx) | movl $0,4(%eax)
> movl $0,16(%eax)
> movl $0,12(%eax)
addl $20,%eax addl $20,%eax
addl $20,%ecx | decl %edx
decl %ebx <
jnz .L706 jnz .L706
popl %ebx <
ret ret
The compiler prefers two additions and two additional pseudos over more
complicated addressing modes, which is bad since the (base + constant)
addressing modes have practically zero additional cost compared to
simple (base) addressing modes.
This is not an isolated case, this really happens all the time and tends
to produce worse code than the above, since it increases register pressure,
and I don't have to tell anyone what that means on the i386.
I found two problems. First, general_induction_var returns the benefit of
a giv, but it always returns 1 even if it calculated a benefit of zero.
In combine_givs, the benefits of multiple givs can be added up in some cases,
possibly increasing the error quite a bit. Thus I think it's better to
have general_induction_var return zero or nonzero depending on whether X
is a giv or not, and accept a pointer to an int in which it can store the
benefit.
Also, general_induction_var uses rtx_cost to determine the cost of a giv.
This may be inappropriate if the rtx is within a MEM (i.e., when g_i_v is
called from find_mem_givs). In that case, it may be better to use the
ADDRESS_COST macro.
The following patch implements these suggestions. It seems to cure the
problem in the cases I looked at, and I've run a benchmark with the chess
program "crafty" which showed about 1% speed increase with this patch.
Before this is applied it should probably be tested on other architectures
as well.
Bernd
* loop.c: Declare reg_address_cost if ADDRESS_COST defined.
(init_loop): Initialize it.
(general_induction_var): Return 1 if X is a giv, zero if
not. Accept an additional argument to indicate whether X is within
a MEM, and another argument that is a pointer to a location into
which the benefit value should be stored. Use ADDRESS_COST macro
to determine benefit if it is available and X is an address.
All callers changed.
diff -u -r1.1.1.31 loop.c
--- loop.c 1998/05/26 15:24:00 1.1.1.31
+++ loop.c 1998/05/27 17:35:22
@@ -311,7 +311,7 @@
static void update_giv_derive PROTO((rtx));
static int basic_induction_var PROTO((rtx, enum machine_mode, rtx, rtx, rtx *, rtx *));
static rtx simplify_giv_expr PROTO((rtx, int *));
-static int general_induction_var PROTO((rtx, rtx *, rtx *, rtx *));
+static int general_induction_var PROTO((rtx, rtx *, rtx *, rtx *, int, int *));
static int consec_sets_giv PROTO((int, rtx, rtx, rtx, rtx *, rtx *));
static int check_dbra_loop PROTO((rtx, int, rtx));
#ifdef ADDRESS_COST
@@ -360,12 +360,20 @@
copy the value of the strength reduced giv to its original register. */
int copy_cost;
+#ifdef ADDRESS_COST
+static int reg_address_cost;
+#endif
+
void
init_loop ()
{
char *free_point = (char *) oballoc (1);
rtx reg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
+#ifdef ADDRESS_COST
+ reg_address_cost = ADDRESS_COST (reg);
+#endif
+
add_cost = rtx_cost (gen_rtx_PLUS (word_mode, reg, reg), SET);
/* We multiply by 2 to reconcile the difference in scale between
@@ -3319,7 +3327,7 @@
value is a linear function of a biv. */
/* Bivs are recognized by `basic_induction_var';
- Givs by `general_induct_var'. */
+ Givs by `general_induction_var'. */
/* Indexed by register number, indicates whether or not register is an
induction variable, and if so what type. */
@@ -3790,14 +3798,13 @@
continue;
if (/* SET_SRC is a giv. */
- ((benefit = general_induction_var (SET_SRC (set),
- &src_reg, &add_val,
- &mult_val))
+ ((general_induction_var (SET_SRC (set), &src_reg, &add_val,
+ &mult_val, 0, &benefit))
/* Equivalent expression is a giv. */
|| ((regnote = find_reg_note (p, REG_EQUAL, NULL_RTX))
- && (benefit = general_induction_var (XEXP (regnote, 0),
- &src_reg,
- &add_val, &mult_val))))
+ && (general_induction_var (XEXP (regnote, 0), &src_reg,
+ &add_val, &mult_val, 0,
+ &benefit))))
/* Don't try to handle any regs made by loop optimization.
We have nothing on them in regno_first_uid, etc. */
&& REGNO (dest_reg) < max_reg_before_loop
@@ -4541,12 +4548,11 @@
rtx mult_val;
int benefit;
- benefit = general_induction_var (XEXP (x, 0),
- &src_reg, &add_val, &mult_val);
-
- /* Don't make a DEST_ADDR giv with mult_val == 1 && add_val == 0.
- Such a giv isn't useful. */
- if (benefit > 0 && (mult_val != const1_rtx || add_val != const0_rtx))
+ if (general_induction_var (XEXP (x, 0), &src_reg, &add_val,
+ &mult_val, 1, &benefit)
+ /* Don't make a DEST_ADDR giv with mult_val == 1 && add_val == 0.
+ Such a giv isn't useful. */
+ && (mult_val != const1_rtx || add_val != const0_rtx))
{
/* Found one; record it. */
struct induction *v
@@ -5322,16 +5328,19 @@
such that the value of X is biv * mult + add; */
static int
-general_induction_var (x, src_reg, add_val, mult_val)
+general_induction_var (x, src_reg, add_val, mult_val, is_addr, pbenefit)
rtx x;
rtx *src_reg;
rtx *add_val;
rtx *mult_val;
+ int is_addr;
+ int *pbenefit;
{
rtx orig_x = x;
- int benefit = 0;
char *storage;
+ *pbenefit = 0;
+
/* If this is an invariant, forget it, it isn't a giv. */
if (invariant_p (x) == 1)
return 0;
@@ -5339,7 +5348,7 @@
/* See if the expression could be a giv and get its form.
Mark our place on the obstack in case we don't find a giv. */
storage = (char *) oballoc (0);
- x = simplify_giv_expr (x, &benefit);
+ x = simplify_giv_expr (x, pbenefit);
if (x == 0)
{
obfree (storage);
@@ -5398,13 +5407,20 @@
*add_val = XEXP (*add_val, 0);
if (GET_CODE (*mult_val) == USE)
*mult_val = XEXP (*mult_val, 0);
+
+#ifdef ADDRESS_COST
+ if (is_addr)
+ {
+ *pbenefit += ADDRESS_COST (orig_x) - reg_address_cost;
+ }
+ else
+#endif
+ *pbenefit += rtx_cost (orig_x, SET);
- benefit += rtx_cost (orig_x, SET);
-
- /* Always return some benefit if this is a giv so it will be detected
- as such. This allows elimination of bivs that might otherwise
- not be eliminated. */
- return benefit == 0 ? 1 : benefit;
+ /* Always return true if this is a giv so it will be detected as such,
+ even if the benefit is zero or negative. This allows elimination
+ of bivs that might otherwise not be eliminated. */
+ return 1;
}
/* Given an expression, X, try to form it as a linear function of a biv.
@@ -5755,12 +5771,12 @@
&& (set = single_set (p))
&& GET_CODE (SET_DEST (set)) == REG
&& SET_DEST (set) == dest_reg
- && ((benefit = general_induction_var (SET_SRC (set), &src_reg,
- add_val, mult_val))
+ && ((general_induction_var (SET_SRC (set), &src_reg,
+ add_val, mult_val, 0, &benefit))
/* Giv created by equivalent expression. */
|| ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX))
- && (benefit = general_induction_var (XEXP (temp, 0), &src_reg,
- add_val, mult_val))))
+ && (general_induction_var (XEXP (temp, 0), &src_reg,
+ add_val, mult_val, 0, &benefit))))
&& src_reg == v->src_reg)
{
if (find_reg_note (p, REG_RETVAL, NULL_RTX))