[CFG] handle loop with arbitary strides
Jan Hubicka
jh@suse.cz
Sat May 4 12:51:00 GMT 2002
Zdenek,
the attached patch implements handling of loop with arbitary strides
(increments) of induction variable. Does it looks OK to you?
Testing still in progress...
Honza
Sat May 4 22:55:55 CEST 2002 Jan Hubicka <jh@suse.cz>
* unroll-new.c (simple_increment, simple_loop_p, test_for_iteration):
Use stride.
(count_loop_iterations): Update to handle arbitary strides.
* loop.h (loop_desc): Use stride, instead of grow.
*** unroll-new.c.old Sat May 4 21:37:24 2002
--- unroll-new.c Sat May 4 22:50:21 2002
*************** simple_condition_p (loop, body, conditio
*** 214,220 ****
}
/* Checks whether DESC->var is incremented/decremented exactly once each
! iteration. Fills in DESC->grow and returns block in that DESC->var is
modified. */
static basic_block
simple_increment (loops, loop, body, desc)
--- 214,220 ----
}
/* Checks whether DESC->var is incremented/decremented exactly once each
! iteration. Fills in DESC->stride and returns block in that DESC->var is
modified. */
static basic_block
simple_increment (loops, loop, body, desc)
*************** simple_increment (loops, loop, body, des
*** 264,275 ****
if (!rtx_equal_p (XEXP (set_src, 0), desc->var))
return NULL;
! /* Set desc->grow. */
set_add = XEXP (set_src, 1);
! if (set_add == const1_rtx)
! desc->grow = 1;
! else if (set_add == constm1_rtx)
! desc->grow = 0;
else
return NULL;
--- 264,273 ----
if (!rtx_equal_p (XEXP (set_src, 0), desc->var))
return NULL;
! /* Set desc->stride. */
set_add = XEXP (set_src, 1);
! if (CONSTANT_P (set_add))
! desc->stride = set_add;
else
return NULL;
*************** simple_loop_p (loops, loop, desc)
*** 404,411 ****
print_simple_rtl (rtl_dump_file, desc->var);
fputc ('\n', rtl_dump_file);
}
! fprintf (rtl_dump_file,
! desc->grow ? "; Counter grows\n": "; Counter decreases\n");
if (desc->init)
{
fprintf (rtl_dump_file, "; Initial value:");
--- 402,410 ----
print_simple_rtl (rtl_dump_file, desc->var);
fputc ('\n', rtl_dump_file);
}
! fprintf (rtl_dump_file, "; Stride:");
! print_simple_rtl (rtl_dump_file, desc->stride);
! fputc ('\n', rtl_dump_file);
if (desc->init)
{
fprintf (rtl_dump_file, "; Initial value:");
*************** static rtx
*** 448,475 ****
count_loop_iterations (desc)
struct loop_desc *desc;
{
- int delta;
enum rtx_code cond = desc->cond;
rtx exp = desc->init ? copy_rtx (desc->init) : desc->var;
/* Give up on floating point modes and friends. It can be possible to do
the job for constant loop bounds, but it is probably not worthwhile. */
if (!INTEGRAL_MODE_P (GET_MODE (desc->var)))
return NULL;
/* Ensure that we always handle the condition to stay inside loop. */
if (desc->neg)
cond = reverse_condition (cond);
/* Compute absolute value of the difference of initial and final value. */
! if (desc->grow)
{
/* Bypass nonsential tests. */
if (cond == EQ || cond == GE || cond == GT || cond == GEU
|| cond == GTU)
return NULL;
exp = simplify_gen_binary (MINUS, GET_MODE (desc->var),
! copy_rtx (desc->lim), exp);
}
else
{
--- 447,477 ----
count_loop_iterations (desc)
struct loop_desc *desc;
{
enum rtx_code cond = desc->cond;
rtx exp = desc->init ? copy_rtx (desc->init) : desc->var;
+ rtx stride = desc->stride;
+ rtx mod;
/* Give up on floating point modes and friends. It can be possible to do
the job for constant loop bounds, but it is probably not worthwhile. */
if (!INTEGRAL_MODE_P (GET_MODE (desc->var)))
return NULL;
+ if (GET_CODE (desc->stride) != CONST_INT)
+ return NULL;
/* Ensure that we always handle the condition to stay inside loop. */
if (desc->neg)
cond = reverse_condition (cond);
/* Compute absolute value of the difference of initial and final value. */
! if (INTVAL (stride) > 0)
{
/* Bypass nonsential tests. */
if (cond == EQ || cond == GE || cond == GT || cond == GEU
|| cond == GTU)
return NULL;
exp = simplify_gen_binary (MINUS, GET_MODE (desc->var),
! copy_rtx (desc->lim), exp);
}
else
{
*************** count_loop_iterations (desc)
*** 478,494 ****
|| cond == LTU)
return NULL;
exp = simplify_gen_binary (MINUS, GET_MODE (desc->var),
! exp, copy_rtx (desc->lim));
}
! delta = 0;
if (!desc->postincr)
! delta--;
/* Determine delta caused by exit condition. */
switch (cond)
{
case NE:
case LT:
case GT:
case LTU:
--- 480,510 ----
|| cond == LTU)
return NULL;
exp = simplify_gen_binary (MINUS, GET_MODE (desc->var),
! exp, copy_rtx (desc->lim));
! stride = simplify_gen_unary (NEG, GET_MODE (desc->var),
! stride, GET_MODE (desc->var));
}
! /* Normalize difference so the value is always first examined
! and later incremented. */
!
if (!desc->postincr)
! exp = simplify_gen_binary (MINUS, GET_MODE (desc->var),
! exp, stride);
/* Determine delta caused by exit condition. */
switch (cond)
{
case NE:
+ /* For NE tests, make sure that the iteration variable won't miss
+ the final value. If EXP mod STRIDE is not zero, then the
+ iteration variable will overflow before the loop exits, and we
+ can not calculate the number of iterations easilly. */
+ if (stride != const1_rtx
+ && (simplify_gen_binary (UMOD, GET_MODE (desc->var), exp, stride)
+ != const0_rtx))
+ return NULL;
+ break;
case LT:
case GT:
case LTU:
*************** count_loop_iterations (desc)
*** 498,512 ****
case GE:
case LEU:
case GEU:
! delta++;
break;
default:
abort ();
}
! if (delta)
! exp = simplify_gen_binary (PLUS, GET_MODE (desc->var),
! exp, GEN_INT (delta));
if (rtl_dump_file)
{
--- 514,554 ----
case GE:
case LEU:
case GEU:
! exp = simplify_gen_binary (PLUS, GET_MODE (desc->var),
! exp, const1_rtx);
break;
default:
abort ();
}
! if (stride != const1_rtx)
! {
! /* Number of iterations is now (EXP + STRIDE - 1 / STRIDE),
! but we need to take care for overflows. */
!
! mod = simplify_gen_binary (UMOD, GET_MODE (desc->var), exp, stride);
!
! /* This is dirty trick. When we can't compute number of iterations
! to be constant, we simply ignore the possible overflow, as
! runtime unroller always use power of 2 amounts and does not
! care about possible lost bits. */
!
! if (GET_CODE (mod) != CONST_INT)
! {
! rtx stridem1 = simplify_gen_binary (PLUS, GET_MODE (desc->var),
! stride, constm1_rtx);
! exp = simplify_gen_binary (PLUS, GET_MODE (desc->var),
! exp, stridem1);
! exp = simplify_gen_binary (UDIV, GET_MODE (desc->var), exp, stride);
! }
! else
! {
! exp = simplify_gen_binary (UDIV, GET_MODE (desc->var), exp, stride);
! if (mod != const0_rtx)
! exp = simplify_gen_binary (PLUS, GET_MODE (desc->var),
! exp, const1_rtx);
! }
! }
if (rtl_dump_file)
{
*************** test_for_iteration (desc, iter)
*** 541,547 ****
/* Compute the value of induction variable. */
addval = simplify_gen_binary (MULT, GET_MODE (desc->var),
! desc->grow ? const1_rtx : constm1_rtx,
gen_int_mode (desc->postincr
? iter : iter + 1,
GET_MODE (desc->var)));
--- 583,589 ----
/* Compute the value of induction variable. */
addval = simplify_gen_binary (MULT, GET_MODE (desc->var),
! desc->stride,
gen_int_mode (desc->postincr
? iter : iter + 1,
GET_MODE (desc->var)));
*** loop.h.old Sat May 4 21:37:07 2002
--- loop.h Sat May 4 21:38:27 2002
*************** struct loop_desc
*** 438,444 ****
{
int postincr; /* 1 if increment/decrement is done after loop exit condition. */
rtx var; /* Loop control variable. */
! int grow; /* 1 if it grows, 0 if it decreases. */
rtx lim; /* Expression var is compared with. */
rtx init; /* Initial value of var. */
HOST_WIDE_INT lim_n;
--- 438,444 ----
{
int postincr; /* 1 if increment/decrement is done after loop exit condition. */
rtx var; /* Loop control variable. */
! rtx stride; /* Value added to VAR in each iteration. */
rtx lim; /* Expression var is compared with. */
rtx init; /* Initial value of var. */
HOST_WIDE_INT lim_n;
More information about the Gcc-patches
mailing list