This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[CFG] handle loop with arbitary strides
- From: Jan Hubicka <jh at suse dot cz>
- To: gcc-pdo at atrey dot karlin dot mff dot cuni dot cz, gcc-patches at gcc dot gnu dot org,Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- Date: Sat, 4 May 2002 21:51:33 +0200
- Subject: [CFG] handle loop with arbitary strides
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;