This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
extension dependant givs
- To: gcc-patches at gcc dot gnu dot org
- Subject: extension dependant givs
- From: Richard Henderson <rth at cygnus dot com>
- Date: Thu, 7 Sep 2000 15:52:08 -0700
This is a variant of a patch I did once upon a time for the new ia32
backend. The object is to recognize cases in which a sign or zero-extend
of a BIV does not affect the outcome, and thus could be folded in to
the initialization of a GIV.
At the time it was put aside, since the conditions that give rise to the
problem didn't happen often enough to be worth the effort. However, it
does happen often on IA-64. Almost all the time, in fact. In fact,
without this patch we'll recognize *no* pointer arithmetic GIVs if the
BIV was an "int" instead of a "long".
Some statistics:
IA-64 IA-32
success 2194 13
fail/inc1 12783 96
fail 7326 18
Looking through the .loop dumps of the entire gcc/ source tree,
"success" marks how often the optimization was successfully
applied; "fail/inc1" counts how many times we might be able to
apply an extended version of this optimization (see below);
"fail" counts how many times we saw a giv that we had to discard
due to unfriendly loop increment.
The next thing to do is to recognize that in
int i, start, end;
for (i = start; i < end; ++i)
...
"i" cannot overflow if "end" is loop invariant since we're protected
by the initial comparison, and the +1 ensures we will not pass "end".
This appears to be very common, particularly when start == 0.
This optimization unfortunately does not trigger on Alpha at all,
because there we are more apt to see
(zero_extend:DI (subreg:SI (reg:DI) 0))
and this code does not handle nested extensions. Another thing
to fix, perhaps.
Tested on Alpha, i686, and ia64. Benchmarked on i686 with no
speed regressions for Spec95.
r~
2000-09-07 Richard Henderson <rth@cygnus.com>
* loop.c (strength_reduce): Call check_ext_dependant_givs.
Properly extend the biv initial value for the giv.
(record_biv): Zero ext_dependant.
(record_giv): New argument ext_val. Update all callers.
(general_induction_var): Likewise.
(consec_sets_giv): Likewise.
(simplify_giv_expr): Likewise. Fill in ext_val if we find
a sign-extend, zero-extend, or truncate.
(combine_givs_p): Make sure modes are compatible.
(check_ext_dependant_givs): New.
(extend_value_for_giv): New.
* loop.h (struct induction): Add ext_dependant.
* unroll.c (iteration_info): Extend the biv initial value for the giv.
(find_splittable_givs): Likewise.
(final_giv_value): Likewise.
Index: loop.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/loop.c,v
retrieving revision 1.279
diff -c -p -d -r1.279 loop.c
*** loop.c 2000/09/06 09:20:37 1.279
--- loop.c 2000/09/07 22:19:23
*************** static void record_biv PARAMS ((struct i
*** 270,286 ****
static void check_final_value PARAMS ((const struct loop *,
struct induction *));
static void record_giv PARAMS ((const struct loop *, struct induction *,
! rtx, rtx, rtx, rtx, rtx, int, enum g_types,
! int, int, rtx *));
static void update_giv_derive PARAMS ((const struct loop *, rtx));
static int basic_induction_var PARAMS ((const struct loop *, rtx,
enum machine_mode, rtx, rtx,
rtx *, rtx *, rtx **));
! static rtx simplify_giv_expr PARAMS ((const struct loop *, rtx, int *));
static int general_induction_var PARAMS ((const struct loop *loop, rtx, rtx *,
! rtx *, rtx *, int, int *, enum machine_mode));
static int consec_sets_giv PARAMS ((const struct loop *, int, rtx,
! rtx, rtx, rtx *, rtx *, rtx *));
static int check_dbra_loop PARAMS ((struct loop *, int));
static rtx express_from_1 PARAMS ((rtx, rtx, rtx));
static rtx combine_givs_p PARAMS ((struct induction *, struct induction *));
--- 270,289 ----
static void check_final_value PARAMS ((const struct loop *,
struct induction *));
static void record_giv PARAMS ((const struct loop *, struct induction *,
! rtx, rtx, rtx, rtx, rtx, rtx, int,
! enum g_types, int, int, rtx *));
static void update_giv_derive PARAMS ((const struct loop *, rtx));
+ static void check_ext_dependant_givs PARAMS ((struct iv_class *,
+ struct loop_info *));
static int basic_induction_var PARAMS ((const struct loop *, rtx,
enum machine_mode, rtx, rtx,
rtx *, rtx *, rtx **));
! static rtx simplify_giv_expr PARAMS ((const struct loop *, rtx, rtx *, int *));
static int general_induction_var PARAMS ((const struct loop *loop, rtx, rtx *,
! rtx *, rtx *, rtx *, int, int *,
! enum machine_mode));
static int consec_sets_giv PARAMS ((const struct loop *, int, rtx,
! rtx, rtx, rtx *, rtx *, rtx *, rtx *));
static int check_dbra_loop PARAMS ((struct loop *, int));
static rtx express_from_1 PARAMS ((rtx, rtx, rtx));
static rtx combine_givs_p PARAMS ((struct induction *, struct induction *));
*************** strength_reduce (loop, insn_count, flags
*** 4412,4417 ****
--- 4415,4424 ----
}
}
+ /* Check each extension dependant giv in this class to see if its
+ root biv is safe from wrapping in the interior mode. */
+ check_ext_dependant_givs (bl, loop_info);
+
/* Combine all giv's for this iv_class. */
combine_givs (bl);
*************** strength_reduce (loop, insn_count, flags
*** 4733,4740 ****
/* Add code at loop start to initialize giv's reduced reg. */
! emit_iv_add_mult (bl->initial_value, v->mult_val,
! v->add_val, v->new_reg, loop_start);
}
}
--- 4740,4748 ----
/* Add code at loop start to initialize giv's reduced reg. */
! emit_iv_add_mult (extend_value_for_giv (v, bl->initial_value),
! v->mult_val, v->add_val, v->new_reg,
! loop_start);
}
}
*************** strength_reduce (loop, insn_count, flags
*** 4799,4806 ****
not replaceable. The correct final value is the same as the
value that the giv starts the reversed loop with. */
if (bl->reversed && ! v->replaceable)
! emit_iv_add_mult (bl->initial_value, v->mult_val,
! v->add_val, v->dest_reg, end_insert_before);
else if (v->final_value)
{
rtx insert_before;
--- 4807,4815 ----
not replaceable. The correct final value is the same as the
value that the giv starts the reversed loop with. */
if (bl->reversed && ! v->replaceable)
! emit_iv_add_mult (extend_value_for_giv (v, bl->initial_value),
! v->mult_val, v->add_val, v->dest_reg,
! end_insert_before);
else if (v->final_value)
{
rtx insert_before;
*************** check_insn_for_givs (loop, p, not_every_
*** 5057,5062 ****
--- 5066,5072 ----
rtx dest_reg;
rtx add_val;
rtx mult_val;
+ rtx ext_val;
int benefit;
rtx regnote = 0;
rtx last_consec_insn;
*************** check_insn_for_givs (loop, p, not_every_
*** 5067,5077 ****
if (/* SET_SRC is a giv. */
(general_induction_var (loop, SET_SRC (set), &src_reg, &add_val,
! &mult_val, 0, &benefit, VOIDmode)
/* Equivalent expression is a giv. */
|| ((regnote = find_reg_note (p, REG_EQUAL, NULL_RTX))
&& general_induction_var (loop, XEXP (regnote, 0), &src_reg,
! &add_val, &mult_val, 0,
&benefit, VOIDmode)))
/* Don't try to handle any regs made by loop optimization.
We have nothing on them in regno_first_uid, etc. */
--- 5077,5087 ----
if (/* SET_SRC is a giv. */
(general_induction_var (loop, SET_SRC (set), &src_reg, &add_val,
! &mult_val, &ext_val, 0, &benefit, VOIDmode)
/* Equivalent expression is a giv. */
|| ((regnote = find_reg_note (p, REG_EQUAL, NULL_RTX))
&& general_induction_var (loop, XEXP (regnote, 0), &src_reg,
! &add_val, &mult_val, &ext_val, 0,
&benefit, VOIDmode)))
/* Don't try to handle any regs made by loop optimization.
We have nothing on them in regno_first_uid, etc. */
*************** check_insn_for_givs (loop, p, not_every_
*** 5083,5089 ****
/* or all sets must be consecutive and make a giv. */
|| (benefit = consec_sets_giv (loop, benefit, p,
src_reg, dest_reg,
! &add_val, &mult_val,
&last_consec_insn))))
{
struct induction *v
--- 5093,5099 ----
/* or all sets must be consecutive and make a giv. */
|| (benefit = consec_sets_giv (loop, benefit, p,
src_reg, dest_reg,
! &add_val, &mult_val, &ext_val,
&last_consec_insn))))
{
struct induction *v
*************** check_insn_for_givs (loop, p, not_every_
*** 5098,5104 ****
p = last_consec_insn;
record_giv (loop, v, p, src_reg, dest_reg, mult_val, add_val,
! benefit, DEST_REG, not_every_iteration,
maybe_multiple, NULL_PTR);
}
--- 5108,5114 ----
p = last_consec_insn;
record_giv (loop, v, p, src_reg, dest_reg, mult_val, add_val,
! ext_val, benefit, DEST_REG, not_every_iteration,
maybe_multiple, NULL_PTR);
}
*************** find_mem_givs (loop, x, insn, not_every_
*** 5202,5207 ****
--- 5212,5218 ----
rtx src_reg;
rtx add_val;
rtx mult_val;
+ rtx ext_val;
int benefit;
/* This code used to disable creating GIVs with mult_val == 1 and
*************** find_mem_givs (loop, x, insn, not_every_
*** 5210,5224 ****
this one would not be seen. */
if (general_induction_var (loop, XEXP (x, 0), &src_reg, &add_val,
! &mult_val, 1, &benefit, GET_MODE (x)))
{
/* Found one; record it. */
struct induction *v
= (struct induction *) oballoc (sizeof (struct induction));
record_giv (loop, v, insn, src_reg, addr_placeholder, mult_val,
! add_val, benefit, DEST_ADDR, not_every_iteration,
! maybe_multiple, &XEXP (x, 0));
v->mem_mode = GET_MODE (x);
}
--- 5221,5236 ----
this one would not be seen. */
if (general_induction_var (loop, XEXP (x, 0), &src_reg, &add_val,
! &mult_val, &ext_val, 1, &benefit,
! GET_MODE (x)))
{
/* Found one; record it. */
struct induction *v
= (struct induction *) oballoc (sizeof (struct induction));
record_giv (loop, v, insn, src_reg, addr_placeholder, mult_val,
! add_val, ext_val, benefit, DEST_ADDR,
! not_every_iteration, maybe_multiple, &XEXP (x, 0));
v->mem_mode = GET_MODE (x);
}
*************** record_biv (v, insn, dest_reg, inc_val,
*** 5277,5282 ****
--- 5289,5295 ----
v->dest_reg = dest_reg;
v->mult_val = mult_val;
v->add_val = inc_val;
+ v->ext_dependant = NULL_RTX;
v->location = location;
v->mode = GET_MODE (dest_reg);
v->always_computable = ! not_every_iteration;
*************** record_biv (v, insn, dest_reg, inc_val,
*** 5360,5373 ****
LOCATION points to the place where this giv's value appears in INSN. */
static void
! record_giv (loop, v, insn, src_reg, dest_reg, mult_val, add_val, benefit,
! type, not_every_iteration, maybe_multiple, location)
const struct loop *loop;
struct induction *v;
rtx insn;
rtx src_reg;
rtx dest_reg;
! rtx mult_val, add_val;
int benefit;
enum g_types type;
int not_every_iteration, maybe_multiple;
--- 5373,5386 ----
LOCATION points to the place where this giv's value appears in INSN. */
static void
! record_giv (loop, v, insn, src_reg, dest_reg, mult_val, add_val, ext_val,
! benefit, type, not_every_iteration, maybe_multiple, location)
const struct loop *loop;
struct induction *v;
rtx insn;
rtx src_reg;
rtx dest_reg;
! rtx mult_val, add_val, ext_val;
int benefit;
enum g_types type;
int not_every_iteration, maybe_multiple;
*************** record_giv (loop, v, insn, src_reg, dest
*** 5389,5394 ****
--- 5402,5408 ----
v->dest_reg = dest_reg;
v->mult_val = mult_val;
v->add_val = add_val;
+ v->ext_dependant = ext_val;
v->benefit = benefit;
v->location = location;
v->cant_derive = 0;
*************** record_giv (loop, v, insn, src_reg, dest
*** 5577,5582 ****
--- 5591,5614 ----
if (v->no_const_addval)
fprintf (loop_dump_stream, " ncav");
+ if (v->ext_dependant)
+ {
+ switch (GET_CODE (v->ext_dependant))
+ {
+ case SIGN_EXTEND:
+ fprintf (loop_dump_stream, " ext se");
+ break;
+ case ZERO_EXTEND:
+ fprintf (loop_dump_stream, " ext ze");
+ break;
+ case TRUNCATE:
+ fprintf (loop_dump_stream, " ext tr");
+ break;
+ default:
+ abort ();
+ }
+ }
+
if (GET_CODE (mult_val) == CONST_INT)
{
fprintf (loop_dump_stream, " mult ");
*************** update_giv_derive (loop, p)
*** 5825,5844 ****
be able to compute a compensation. */
else if (biv->insn == p)
{
! tem = 0;
if (biv->mult_val == const1_rtx)
tem = simplify_giv_expr (loop,
gen_rtx_MULT (giv->mode,
biv->add_val,
giv->mult_val),
! &dummy);
if (tem && giv->derive_adjustment)
tem = simplify_giv_expr
(loop,
gen_rtx_PLUS (giv->mode, tem, giv->derive_adjustment),
! &dummy);
if (tem)
giv->derive_adjustment = tem;
--- 5857,5877 ----
be able to compute a compensation. */
else if (biv->insn == p)
{
! rtx ext_val_dummy;
+ tem = 0;
if (biv->mult_val == const1_rtx)
tem = simplify_giv_expr (loop,
gen_rtx_MULT (giv->mode,
biv->add_val,
giv->mult_val),
! &ext_val_dummy, &dummy);
if (tem && giv->derive_adjustment)
tem = simplify_giv_expr
(loop,
gen_rtx_PLUS (giv->mode, tem, giv->derive_adjustment),
! &ext_val_dummy, &dummy);
if (tem)
giv->derive_adjustment = tem;
*************** basic_induction_var (loop, x, mode, dest
*** 6058,6070 ****
such that the value of X is biv * mult + add; */
static int
! general_induction_var (loop, x, src_reg, add_val, mult_val, is_addr,
! pbenefit, addr_mode)
const struct loop *loop;
rtx x;
rtx *src_reg;
rtx *add_val;
rtx *mult_val;
int is_addr;
int *pbenefit;
enum machine_mode addr_mode;
--- 6091,6104 ----
such that the value of X is biv * mult + add; */
static int
! general_induction_var (loop, x, src_reg, add_val, mult_val, ext_val,
! is_addr, pbenefit, addr_mode)
const struct loop *loop;
rtx x;
rtx *src_reg;
rtx *add_val;
rtx *mult_val;
+ rtx *ext_val;
int is_addr;
int *pbenefit;
enum machine_mode addr_mode;
*************** general_induction_var (loop, x, src_reg,
*** 6080,6086 ****
Mark our place on the obstack in case we don't find a giv. */
storage = (char *) oballoc (0);
*pbenefit = 0;
! x = simplify_giv_expr (loop, x, pbenefit);
if (x == 0)
{
obfree (storage);
--- 6114,6121 ----
Mark our place on the obstack in case we don't find a giv. */
storage = (char *) oballoc (0);
*pbenefit = 0;
! *ext_val = NULL_RTX;
! x = simplify_giv_expr (loop, x, ext_val, pbenefit);
if (x == 0)
{
obfree (storage);
*************** static int cmp_combine_givs_stats PARAMS
*** 6177,6185 ****
static int cmp_recombine_givs_stats PARAMS ((const PTR, const PTR));
static rtx
! simplify_giv_expr (loop, x, benefit)
const struct loop *loop;
rtx x;
int *benefit;
{
enum machine_mode mode = GET_MODE (x);
--- 6212,6221 ----
static int cmp_recombine_givs_stats PARAMS ((const PTR, const PTR));
static rtx
! simplify_giv_expr (loop, x, ext_val, benefit)
const struct loop *loop;
rtx x;
+ rtx *ext_val;
int *benefit;
{
enum machine_mode mode = GET_MODE (x);
*************** simplify_giv_expr (loop, x, benefit)
*** 6196,6203 ****
switch (GET_CODE (x))
{
case PLUS:
! arg0 = simplify_giv_expr (loop, XEXP (x, 0), benefit);
! arg1 = simplify_giv_expr (loop, XEXP (x, 1), benefit);
if (arg0 == 0 || arg1 == 0)
return NULL_RTX;
--- 6232,6239 ----
switch (GET_CODE (x))
{
case PLUS:
! arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
! arg1 = simplify_giv_expr (loop, XEXP (x, 1), ext_val, benefit);
if (arg0 == 0 || arg1 == 0)
return NULL_RTX;
*************** simplify_giv_expr (loop, x, benefit)
*** 6249,6255 ****
gen_rtx_PLUS (mode,
XEXP (arg0, 1),
arg1)),
! benefit);
default:
abort ();
--- 6285,6291 ----
gen_rtx_PLUS (mode,
XEXP (arg0, 1),
arg1)),
! ext_val, benefit);
default:
abort ();
*************** simplify_giv_expr (loop, x, benefit)
*** 6275,6281 ****
gen_rtx_PLUS (mode, arg0,
XEXP (arg1, 0)),
XEXP (arg1, 1)),
! benefit);
/* Now must have MULT + MULT. Distribute if same biv, else not giv. */
if (GET_CODE (arg0) != MULT || GET_CODE (arg1) != MULT)
--- 6311,6317 ----
gen_rtx_PLUS (mode, arg0,
XEXP (arg1, 0)),
XEXP (arg1, 1)),
! ext_val, benefit);
/* Now must have MULT + MULT. Distribute if same biv, else not giv. */
if (GET_CODE (arg0) != MULT || GET_CODE (arg1) != MULT)
*************** simplify_giv_expr (loop, x, benefit)
*** 6290,6296 ****
gen_rtx_PLUS (mode,
XEXP (arg0, 1),
XEXP (arg1, 1))),
! benefit);
case MINUS:
/* Handle "a - b" as "a + b * (-1)". */
--- 6326,6332 ----
gen_rtx_PLUS (mode,
XEXP (arg0, 1),
XEXP (arg1, 1))),
! ext_val, benefit);
case MINUS:
/* Handle "a - b" as "a + b * (-1)". */
*************** simplify_giv_expr (loop, x, benefit)
*** 6300,6310 ****
gen_rtx_MULT (mode,
XEXP (x, 1),
constm1_rtx)),
! benefit);
case MULT:
! arg0 = simplify_giv_expr (loop, XEXP (x, 0), benefit);
! arg1 = simplify_giv_expr (loop, XEXP (x, 1), benefit);
if (arg0 == 0 || arg1 == 0)
return NULL_RTX;
--- 6336,6346 ----
gen_rtx_MULT (mode,
XEXP (x, 1),
constm1_rtx)),
! ext_val, benefit);
case MULT:
! arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
! arg1 = simplify_giv_expr (loop, XEXP (x, 1), ext_val, benefit);
if (arg0 == 0 || arg1 == 0)
return NULL_RTX;
*************** simplify_giv_expr (loop, x, benefit)
*** 6350,6356 ****
XEXP (arg0,
1),
arg1)),
! benefit);
}
/* Porpagate the MULT expressions to the intermost nodes. */
else if (GET_CODE (arg0) == PLUS)
--- 6386,6392 ----
XEXP (arg0,
1),
arg1)),
! ext_val, benefit);
}
/* Porpagate the MULT expressions to the intermost nodes. */
else if (GET_CODE (arg0) == PLUS)
*************** simplify_giv_expr (loop, x, benefit)
*** 6366,6372 ****
XEXP (arg0,
1),
arg1)),
! benefit);
}
return gen_rtx_USE (mode, gen_rtx_MULT (mode, arg0, arg1));
--- 6402,6408 ----
XEXP (arg0,
1),
arg1)),
! ext_val, benefit);
}
return gen_rtx_USE (mode, gen_rtx_MULT (mode, arg0, arg1));
*************** simplify_giv_expr (loop, x, benefit)
*** 6378,6384 ****
gen_rtx_MULT (mode,
XEXP (arg0, 1),
arg1)),
! benefit);
case PLUS:
/* (a + invar_1) * invar_2. Distribute. */
--- 6414,6420 ----
gen_rtx_MULT (mode,
XEXP (arg0, 1),
arg1)),
! ext_val, benefit);
case PLUS:
/* (a + invar_1) * invar_2. Distribute. */
*************** simplify_giv_expr (loop, x, benefit)
*** 6390,6396 ****
gen_rtx_MULT (mode,
XEXP (arg0, 1),
arg1)),
! benefit);
default:
abort ();
--- 6426,6432 ----
gen_rtx_MULT (mode,
XEXP (arg0, 1),
arg1)),
! ext_val, benefit);
default:
abort ();
*************** simplify_giv_expr (loop, x, benefit)
*** 6407,6419 ****
XEXP (x, 0),
GEN_INT ((HOST_WIDE_INT) 1
<< INTVAL (XEXP (x, 1)))),
! benefit);
case NEG:
/* "-a" is "a * (-1)" */
return simplify_giv_expr (loop,
gen_rtx_MULT (mode, XEXP (x, 0), constm1_rtx),
! benefit);
case NOT:
/* "~a" is "-a - 1". Silly, but easy. */
--- 6443,6455 ----
XEXP (x, 0),
GEN_INT ((HOST_WIDE_INT) 1
<< INTVAL (XEXP (x, 1)))),
! ext_val, benefit);
case NEG:
/* "-a" is "a * (-1)" */
return simplify_giv_expr (loop,
gen_rtx_MULT (mode, XEXP (x, 0), constm1_rtx),
! ext_val, benefit);
case NOT:
/* "~a" is "-a - 1". Silly, but easy. */
*************** simplify_giv_expr (loop, x, benefit)
*** 6421,6433 ****
gen_rtx_MINUS (mode,
gen_rtx_NEG (mode, XEXP (x, 0)),
const1_rtx),
! benefit);
case USE:
/* Already in proper form for invariant. */
return x;
! case REG:
/* If this is a new register, we can't deal with it. */
if (REGNO (x) >= max_reg_before_loop)
return 0;
--- 6457,6486 ----
gen_rtx_MINUS (mode,
gen_rtx_NEG (mode, XEXP (x, 0)),
const1_rtx),
! ext_val, benefit);
case USE:
/* Already in proper form for invariant. */
return x;
! case SIGN_EXTEND:
! case ZERO_EXTEND:
! case TRUNCATE:
! /* Conditionally recognize extensions of simple IVs. After we've
! computed loop traversal counts and verified the range of the
! source IV, we'll reevaluate this as a GIV. */
! if (*ext_val == NULL_RTX)
! {
! arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
! if (arg0 && *ext_val == NULL_RTX && GET_CODE (arg0) == REG)
! {
! *ext_val = gen_rtx_fmt_e (GET_CODE (x), mode, arg0);
! return arg0;
! }
! }
! goto do_default;
!
! case REG:
/* If this is a new register, we can't deal with it. */
if (REGNO (x) >= max_reg_before_loop)
return 0;
*************** simplify_giv_expr (loop, x, benefit)
*** 6466,6475 ****
if (v->derive_adjustment)
tem = gen_rtx_MINUS (mode, tem, v->derive_adjustment);
! return simplify_giv_expr (loop, tem, benefit);
}
default:
/* If it isn't an induction variable, and it is invariant, we
may be able to simplify things further by looking through
the bits we just moved outside the loop. */
--- 6519,6540 ----
if (v->derive_adjustment)
tem = gen_rtx_MINUS (mode, tem, v->derive_adjustment);
! arg0 = simplify_giv_expr (loop, tem, ext_val, benefit);
! if (*ext_val)
! {
! if (!v->ext_dependant)
! return arg0;
! }
! else
! {
! *ext_val = v->ext_dependant;
! return arg0;
! }
! return 0;
}
default:
+ do_default:
/* If it isn't an induction variable, and it is invariant, we
may be able to simplify things further by looking through
the bits we just moved outside the loop. */
*************** simplify_giv_expr (loop, x, benefit)
*** 6486,6492 ****
this one is going away. */
if (m->match)
return simplify_giv_expr (loop, m->match->set_dest,
! benefit);
/* If consec is non-zero, this is a member of a group of
instructions that were moved together. We handle this
--- 6551,6557 ----
this one is going away. */
if (m->match)
return simplify_giv_expr (loop, m->match->set_dest,
! ext_val, benefit);
/* If consec is non-zero, this is a member of a group of
instructions that were moved together. We handle this
*************** simplify_giv_expr (loop, x, benefit)
*** 6520,6526 ****
|| GET_CODE (tem) == CONST_INT
|| GET_CODE (tem) == SYMBOL_REF)
{
! tem = simplify_giv_expr (loop, tem, benefit);
if (tem)
return tem;
}
--- 6585,6592 ----
|| GET_CODE (tem) == CONST_INT
|| GET_CODE (tem) == SYMBOL_REF)
{
! tem = simplify_giv_expr (loop, tem, ext_val,
! benefit);
if (tem)
return tem;
}
*************** simplify_giv_expr (loop, x, benefit)
*** 6530,6536 ****
&& GET_CODE (XEXP (XEXP (tem, 0), 1)) == CONST_INT)
{
tem = simplify_giv_expr (loop, XEXP (tem, 0),
! benefit);
if (tem)
return tem;
}
--- 6596,6602 ----
&& GET_CODE (XEXP (XEXP (tem, 0), 1)) == CONST_INT)
{
tem = simplify_giv_expr (loop, XEXP (tem, 0),
! ext_val, benefit);
if (tem)
return tem;
}
*************** sge_plus (mode, x, y)
*** 6635,6641 ****
static int
consec_sets_giv (loop, first_benefit, p, src_reg, dest_reg,
! add_val, mult_val, last_consec_insn)
const struct loop *loop;
int first_benefit;
rtx p;
--- 6701,6707 ----
static int
consec_sets_giv (loop, first_benefit, p, src_reg, dest_reg,
! add_val, mult_val, ext_val, last_consec_insn)
const struct loop *loop;
int first_benefit;
rtx p;
*************** consec_sets_giv (loop, first_benefit, p,
*** 6643,6648 ****
--- 6709,6715 ----
rtx dest_reg;
rtx *add_val;
rtx *mult_val;
+ rtx *ext_val;
rtx *last_consec_insn;
{
int count;
*************** consec_sets_giv (loop, first_benefit, p,
*** 6666,6671 ****
--- 6733,6739 ----
v->benefit = first_benefit;
v->cant_derive = 0;
v->derive_adjustment = 0;
+ v->ext_dependant = NULL_RTX;
REG_IV_TYPE (REGNO (dest_reg)) = GENERAL_INDUCT;
REG_IV_INFO (REGNO (dest_reg)) = v;
*************** consec_sets_giv (loop, first_benefit, p,
*** 6686,6697 ****
&& GET_CODE (SET_DEST (set)) == REG
&& SET_DEST (set) == dest_reg
&& (general_induction_var (loop, SET_SRC (set), &src_reg,
! add_val, mult_val, 0, &benefit, VOIDmode)
/* Giv created by equivalent expression. */
|| ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX))
&& general_induction_var (loop, XEXP (temp, 0), &src_reg,
! add_val, mult_val, 0, &benefit,
! VOIDmode)))
&& src_reg == v->src_reg)
{
if (find_reg_note (p, REG_RETVAL, NULL_RTX))
--- 6754,6766 ----
&& GET_CODE (SET_DEST (set)) == REG
&& SET_DEST (set) == dest_reg
&& (general_induction_var (loop, SET_SRC (set), &src_reg,
! add_val, mult_val, ext_val, 0,
! &benefit, VOIDmode)
/* Giv created by equivalent expression. */
|| ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX))
&& general_induction_var (loop, XEXP (temp, 0), &src_reg,
! add_val, mult_val, ext_val, 0,
! &benefit, VOIDmode)))
&& src_reg == v->src_reg)
{
if (find_reg_note (p, REG_RETVAL, NULL_RTX))
*************** static rtx
*** 6921,6945 ****
combine_givs_p (g1, g2)
struct induction *g1, *g2;
{
! rtx tem = express_from (g1, g2);
/* If these givs are identical, they can be combined. We use the results
of express_from because the addends are not in a canonical form, so
rtx_equal_p is a weaker test. */
/* But don't combine a DEST_REG giv with a DEST_ADDR giv; we want the
combination to be the other way round. */
! if (tem == g1->dest_reg
&& (g1->giv_type == DEST_REG || g2->giv_type == DEST_ADDR))
{
! return g1->dest_reg;
}
/* 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 (tem != NULL_RTX
&& g2->giv_type == DEST_ADDR
! && memory_address_p (g2->mem_mode, tem)
/* ??? Looses, especially with -fforce-addr, where *g2->location
will always be a register, and so anything more complicated
gets discarded. */
--- 6990,7025 ----
combine_givs_p (g1, g2)
struct induction *g1, *g2;
{
! rtx comb, ret;
!
! /* With the introduction of ext dependant givs, we must care for modes.
! G2 must not use a wider mode than G1. */
! if (GET_MODE_SIZE (g1->mode) < GET_MODE_SIZE (g2->mode))
! return NULL_RTX;
+ ret = comb = express_from (g1, g2);
+ if (comb == NULL_RTX)
+ return NULL_RTX;
+ if (g1->mode != g2->mode)
+ ret = gen_lowpart (g2->mode, comb);
+
/* If these givs are identical, they can be combined. We use the results
of express_from because the addends are not in a canonical form, so
rtx_equal_p is a weaker test. */
/* But don't combine a DEST_REG giv with a DEST_ADDR giv; we want the
combination to be the other way round. */
! if (comb == g1->dest_reg
&& (g1->giv_type == DEST_REG || g2->giv_type == DEST_ADDR))
{
! return ret;
}
/* 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 (ret != NULL_RTX
&& g2->giv_type == DEST_ADDR
! && memory_address_p (g2->mem_mode, ret)
/* ??? Looses, especially with -fforce-addr, where *g2->location
will always be a register, and so anything more complicated
gets discarded. */
*************** combine_givs_p (g1, g2)
*** 6952,6961 ****
#endif
)
{
! return tem;
}
return NULL_RTX;
}
struct combine_givs_stats
--- 7032,7226 ----
#endif
)
{
! return ret;
}
return NULL_RTX;
+ }
+
+ /* Check each extension dependant giv in this class to see if its
+ root biv is safe from wrapping in the interior mode, which would
+ make the giv illegal. */
+
+ static void
+ check_ext_dependant_givs (bl, loop_info)
+ struct iv_class *bl;
+ struct loop_info *loop_info;
+ {
+ int ze_ok = 0, se_ok = 0, info_ok = 0;
+ enum machine_mode biv_mode = GET_MODE (bl->biv->src_reg);
+ HOST_WIDE_INT start_val;
+ unsigned HOST_WIDE_INT u_end_val, u_start_val;
+ rtx incr = pc_rtx;
+ struct induction *v;
+
+ /* Make sure the iteration data is available. We must have
+ constants in order to be certain of no overflow. */
+ /* ??? An unknown iteration count with an increment of +-1
+ combined with friendly exit tests of against an invariant
+ value is also ameanable to optimization. Not implemented. */
+ if (loop_info->n_iterations > 0
+ && bl->initial_value
+ && GET_CODE (bl->initial_value) == CONST_INT
+ && (incr = biv_total_increment (bl))
+ && GET_CODE (incr) == CONST_INT
+ /* Make sure the host can represent the arithmetic. */
+ && HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (biv_mode))
+ {
+ unsigned HOST_WIDE_INT abs_incr, total_incr;
+ HOST_WIDE_INT s_end_val;
+ int neg_incr;
+
+ info_ok = 1;
+ start_val = INTVAL (bl->initial_value);
+ u_start_val = start_val;
+
+ neg_incr = 0, abs_incr = INTVAL (incr);
+ if (INTVAL (incr) < 0)
+ neg_incr = 1, abs_incr = -abs_incr;
+ total_incr = abs_incr * loop_info->n_iterations;
+
+ /* Check for host arithmatic overflow. */
+ if (total_incr / loop_info->n_iterations == abs_incr)
+ {
+ unsigned HOST_WIDE_INT u_max;
+ HOST_WIDE_INT s_max;
+
+ u_end_val = start_val + (neg_incr ? -total_incr : total_incr);
+ s_end_val = u_end_val;
+ u_max = GET_MODE_MASK (biv_mode);
+ s_max = u_max >> 1;
+
+ /* Check zero extension of biv ok. */
+ if (start_val >= 0
+ /* Check for host arithmatic overflow. */
+ && (neg_incr
+ ? u_end_val < u_start_val
+ : u_end_val > u_start_val)
+ /* Check for target arithmetic overflow. */
+ && (neg_incr
+ ? 1 /* taken care of with host overflow */
+ : u_end_val <= u_max))
+ {
+ ze_ok = 1;
+ }
+
+ /* Check sign extension of biv ok. */
+ /* ??? While it is true that overflow with signed and pointer
+ arithmetic is undefined, I fear too many programmers don't
+ keep this fact in mind -- myself included on occasion.
+ So leave alone with the signed overflow optimizations. */
+ if (start_val >= -s_max - 1
+ /* Check for host arithmatic overflow. */
+ && (neg_incr
+ ? s_end_val < start_val
+ : s_end_val > start_val)
+ /* Check for target arithmetic overflow. */
+ && (neg_incr
+ ? s_end_val >= -s_max - 1
+ : s_end_val <= s_max))
+ {
+ se_ok = 1;
+ }
+ }
+ }
+
+ /* Invalidate givs that fail the tests. */
+ for (v = bl->giv; v; v = v->next_iv)
+ if (v->ext_dependant)
+ {
+ enum rtx_code code = GET_CODE (v->ext_dependant);
+ int ok = 0;
+
+ switch (code)
+ {
+ case SIGN_EXTEND:
+ ok = se_ok;
+ break;
+ case ZERO_EXTEND:
+ ok = ze_ok;
+ break;
+
+ case TRUNCATE:
+ /* We don't know whether this value is being used as either
+ signed or unsigned, so to safely truncate we must satisfy
+ both. The initial check here verifies the BIV itself;
+ once that is successful we may check its range wrt the
+ derived GIV. */
+ if (se_ok && ze_ok)
+ {
+ enum machine_mode outer_mode = GET_MODE (v->ext_dependant);
+ unsigned HOST_WIDE_INT max = GET_MODE_MASK (outer_mode) >> 1;
+
+ /* We know from the above that both endpoints are nonnegative,
+ and that there is no wrapping. Verify that both endpoints
+ are within the (signed) range of the outer mode. */
+ if (u_start_val <= max && u_end_val <= max)
+ ok = 1;
+ }
+ break;
+
+ default:
+ abort ();
+ }
+
+ if (ok)
+ {
+ if (loop_dump_stream)
+ {
+ fprintf(loop_dump_stream,
+ "Verified ext dependant giv at %d of reg %d\n",
+ INSN_UID (v->insn), bl->regno);
+ }
+ }
+ else
+ {
+ if (loop_dump_stream)
+ {
+ const char *why;
+
+ if (info_ok)
+ why = "biv iteration values overflowed";
+ else
+ {
+ if (incr == pc_rtx)
+ incr = biv_total_increment (bl);
+ if (incr == const1_rtx)
+ why = "biv iteration info incomplete; incr by 1";
+ else
+ why = "biv iteration info incomplete";
+ }
+
+ fprintf(loop_dump_stream,
+ "Failed ext dependant giv at %d, %s\n",
+ INSN_UID (v->insn), why);
+ }
+ v->ignore = 1;
+ }
+ }
+ }
+
+ /* Generate a version of VALUE in a mode appropriate for initializing V. */
+
+ rtx
+ extend_value_for_giv (v, value)
+ struct induction *v;
+ rtx value;
+ {
+ rtx ext_dep = v->ext_dependant;
+
+ if (! ext_dep)
+ return value;
+
+ /* Recall that check_ext_dependant_givs verified that the known bounds
+ of a biv did not overflow or wrap with respect to the extension for
+ the giv. Therefore, constants need no additional adjustment. */
+ if (CONSTANT_P (value) && GET_MODE (value) == VOIDmode)
+ return value;
+
+ /* Otherwise, we must adjust the value to compensate for the
+ differing modes of the biv and the giv. */
+ return gen_rtx_fmt_e (GET_CODE (ext_dep), GET_MODE (ext_dep), value);
}
struct combine_givs_stats
Index: loop.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/loop.h,v
retrieving revision 1.33
diff -c -p -d -r1.33 loop.h
*** loop.h 2000/07/30 23:57:56 1.33
--- loop.h 2000/09/07 22:19:23
*************** struct induction
*** 115,120 ****
--- 115,122 ----
subtracted from add_val when this giv
derives another. This occurs when the
giv spans a biv update by incrementation. */
+ rtx ext_dependant; /* If nonzero, is a sign or zero extension
+ if a biv on which this giv is dependant. */
struct induction *next_iv; /* For givs, links together all givs that are
based on the same biv. For bivs, links
together all biv entries that refer to the
*************** int loop_invariant_p PARAMS ((const stru
*** 238,243 ****
--- 240,246 ----
rtx get_condition_for_loop PARAMS ((const struct loop *, rtx));
void emit_iv_add_mult PARAMS ((rtx, rtx, rtx, rtx, rtx));
rtx express_from PARAMS ((struct induction *, struct induction *));
+ rtx extend_value_for_giv PARAMS ((struct induction *, rtx));
void unroll_loop PARAMS ((struct loop *, int, rtx, int));
rtx biv_total_increment PARAMS ((struct iv_class *));
*************** void emit_unrolled_add PARAMS ((rtx, rtx
*** 251,257 ****
int back_branch_in_range_p PARAMS ((const struct loop *, rtx));
int loop_insn_first_p PARAMS ((rtx, rtx));
! typedef rtx (*loop_insn_callback ) PARAMS ((struct loop *, rtx, int, int));
void for_each_insn_in_loop PARAMS ((struct loop *, loop_insn_callback));
/* Forward declarations for non-static functions declared in doloop.c. */
--- 254,260 ----
int back_branch_in_range_p PARAMS ((const struct loop *, rtx));
int loop_insn_first_p PARAMS ((rtx, rtx));
! typedef rtx (*loop_insn_callback) PARAMS ((struct loop *, rtx, int, int));
void for_each_insn_in_loop PARAMS ((struct loop *, loop_insn_callback));
/* Forward declarations for non-static functions declared in doloop.c. */
Index: unroll.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/unroll.c,v
retrieving revision 1.104
diff -c -p -d -r1.104 unroll.c
*** unroll.c 2000/09/07 13:10:51 1.104
--- unroll.c 2000/09/07 22:19:23
*************** iteration_info (loop, iteration_var, ini
*** 2495,2500 ****
--- 2495,2501 ----
{
HOST_WIDE_INT offset = 0;
struct induction *v = REG_IV_INFO (REGNO (iteration_var));
+ rtx biv_initial_value;
if (REGNO (v->src_reg) >= max_reg_before_loop)
abort ();
*************** iteration_info (loop, iteration_var, ini
*** 2527,2537 ****
fprintf (loop_dump_stream,
"Loop unrolling: Giv iterator, initial value bias %ld.\n",
(long) offset);
/* Initial value is mult_val times the biv's initial value plus
add_val. Only useful if it is a constant. */
*initial_value
= fold_rtx_mult_add (v->mult_val,
! plus_constant (bl->initial_value, offset),
v->add_val, v->mode);
}
else
--- 2528,2540 ----
fprintf (loop_dump_stream,
"Loop unrolling: Giv iterator, initial value bias %ld.\n",
(long) offset);
+
/* Initial value is mult_val times the biv's initial value plus
add_val. Only useful if it is a constant. */
+ biv_initial_value = extend_value_for_giv (v, bl->initial_value);
*initial_value
= fold_rtx_mult_add (v->mult_val,
! plus_constant (biv_initial_value, offset),
v->add_val, v->mode);
}
else
*************** find_splittable_givs (loop, bl, unroll_t
*** 2895,2900 ****
--- 2898,2904 ----
loop->start);
biv_initial_value = tem;
}
+ biv_initial_value = extend_value_for_giv (v, biv_initial_value);
value = fold_rtx_mult_add (v->mult_val, biv_initial_value,
v->add_val, v->mode);
}
*************** final_giv_value (loop, v)
*** 3456,3465 ****
insert_before = NEXT_INSN (loop_end);
/* Put the final biv value in tem. */
! tem = gen_reg_rtx (bl->biv->mode);
record_base_value (REGNO (tem), bl->biv->add_val, 0);
emit_iv_add_mult (increment, GEN_INT (n_iterations),
! bl->initial_value, tem, insert_before);
/* Subtract off extra increments as we find them. */
for (insn = NEXT_INSN (v->insn); insn != loop_end;
--- 3460,3470 ----
insert_before = NEXT_INSN (loop_end);
/* Put the final biv value in tem. */
! tem = gen_reg_rtx (v->mode);
record_base_value (REGNO (tem), bl->biv->add_val, 0);
emit_iv_add_mult (increment, GEN_INT (n_iterations),
! extend_value_for_giv (v, bl->initial_value),
! tem, insert_before);
/* Subtract off extra increments as we find them. */
for (insn = NEXT_INSN (v->insn); insn != loop_end;