[CFG] More aggresive constant_iterations
Zdenek Dvorak
rakdver@atrey.karlin.mff.cuni.cz
Tue May 28 15:32:00 GMT 2002
Hello.
This makes constant_iterations a bit more aggresive -- when there is
more than one possible definition of initial/final value of loop, check
all combinations.
Zdenek Dvorak
Changelog:
* loop.h (struct loop_desc): Field init replaced by var_alts,
new field lim_alts.
* unroll-new.c (variable_initial_values): New static function.
(count_loop_iterations): Add arguments for explicit values of
initial and final value.
(simple_condition_p): Use variable_initial_values.
(constant_iterations): More aggressive now.
(simple_loop_exit_p): Use variable_initial_values, dump lim_alts and
var_alts.
(test_for_iteration, unroll_loop_runtime_iterations): Modified.
Index: loop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.h,v
retrieving revision 1.56.2.16
diff -c -3 -p -r1.56.2.16 loop.h
*** loop.h 23 May 2002 15:00:06 -0000 1.56.2.16
--- loop.h 28 May 2002 21:23:04 -0000
*************** void unswitch_loops PARAMS ((struct loop
*** 439,448 ****
struct loop_desc
{
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. */
bool const_iter; /* True if it iterates constant number of times. */
unsigned HOST_WIDE_INT niter;
/* Number of iterations if it is constant. */
--- 439,449 ----
struct loop_desc
{
int postincr; /* 1 if increment/decrement is done after loop exit condition. */
rtx stride; /* Value added to VAR in each iteration. */
+ rtx var; /* Loop control variable. */
+ rtx var_alts; /* List of definitions of its initial value. */
rtx lim; /* Expression var is compared with. */
! rtx lim_alts; /* List of definitions of its initial value. */
bool const_iter; /* True if it iterates constant number of times. */
unsigned HOST_WIDE_INT niter;
/* Number of iterations if it is constant. */
Index: unroll-new.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/unroll-new.c,v
retrieving revision 1.1.2.28
diff -c -3 -p -r1.1.2.28 unroll-new.c
*** unroll-new.c 24 May 2002 20:54:53 -0000 1.1.2.28
--- unroll-new.c 28 May 2002 21:23:04 -0000
*************** static basic_block simple_increment PARA
*** 48,53 ****
--- 48,54 ----
basic_block *,
struct loop_desc *));
static rtx variable_initial_value PARAMS ((rtx, basic_block, rtx, rtx *));
+ static rtx variable_initial_values PARAMS ((edge, rtx));
static bool simple_loop_p PARAMS ((struct loops *, struct loop *,
struct loop_desc *));
static bool simple_loop_exit_p PARAMS ((struct loops *, struct loop *,
*************** static bool simple_loop_exit_p PARAMS ((
*** 56,62 ****
static bool constant_iterations PARAMS ((struct loop_desc *,
unsigned HOST_WIDE_INT *,
bool *));
! static rtx count_loop_iterations PARAMS ((struct loop_desc *, int));
static void unroll_or_peel_loop PARAMS ((struct loops *, struct loop *, int));
static bool peel_loop_simple PARAMS ((struct loops *, struct loop *, int));
static bool peel_loop_completely PARAMS ((struct loops *, struct loop *,
--- 57,63 ----
static bool constant_iterations PARAMS ((struct loop_desc *,
unsigned HOST_WIDE_INT *,
bool *));
! static rtx count_loop_iterations PARAMS ((struct loop_desc *, rtx, rtx));
static void unroll_or_peel_loop PARAMS ((struct loops *, struct loop *, int));
static bool peel_loop_simple PARAMS ((struct loops *, struct loop *, int));
static bool peel_loop_completely PARAMS ((struct loops *, struct loop *,
*************** simple_condition_p (loop, body, conditio
*** 130,136 ****
rtx condition;
struct loop_desc *desc;
{
! rtx op0, op1, set_insn;
edge e = loop_preheader_edge (loop);
/* Check condition. */
--- 131,137 ----
rtx condition;
struct loop_desc *desc;
{
! rtx op0, op1;
edge e = loop_preheader_edge (loop);
/* Check condition. */
*************** simple_condition_p (loop, body, conditio
*** 169,178 ****
desc->var = op1;
desc->lim = op0;
! set_insn = e->src->end;
! while (REG_P (op0)
! && (op0 = variable_initial_value (set_insn, e->src, op0, &set_insn)))
! desc->lim = op0;
desc->cond = swap_condition (GET_CODE (condition));
if (desc->cond == UNKNOWN)
--- 170,176 ----
desc->var = op1;
desc->lim = op0;
! desc->lim_alts = variable_initial_values (e, op0);
desc->cond = swap_condition (GET_CODE (condition));
if (desc->cond == UNKNOWN)
*************** simple_condition_p (loop, body, conditio
*** 189,198 ****
desc->var = op0;
desc->lim = op1;
! set_insn = e->src->end;
! while (REG_P (op1)
! && (op1 = variable_initial_value (set_insn, e->src, op1, &set_insn)))
! desc->lim = op1;
desc->cond = GET_CODE (condition);
--- 187,193 ----
desc->var = op0;
desc->lim = op1;
! desc->lim_alts = variable_initial_values (e, op1);
desc->cond = GET_CODE (condition);
*************** variable_initial_value (insn, end_bb, va
*** 322,327 ****
--- 317,343 ----
return NULL;
}
+ /* Returns list of definitions of initial value of VAR at Edge. */
+ static rtx
+ variable_initial_values (e, var)
+ edge e;
+ rtx var;
+ {
+ rtx set_insn, list;
+
+ list = alloc_EXPR_LIST (0, copy_rtx (var), NULL);
+
+ if (e->src == ENTRY_BLOCK_PTR)
+ return list;
+
+ set_insn = e->src->end;
+ while (REG_P (var)
+ && (var = variable_initial_value (set_insn, e->src, var, &set_insn)))
+ list = alloc_EXPR_LIST (0, copy_rtx (var), list);
+
+ return list;
+ }
+
/* Tests whether LOOP is simple for loop. Returns simple loop description
in DESC. */
static bool
*************** constant_iterations (desc, niter, may_be
*** 367,372 ****
--- 383,389 ----
bool *may_be_zero;
{
rtx test, expr;
+ rtx ainit, alim;
test = test_for_iteration (desc, 0);
if (test == const0_rtx)
*************** constant_iterations (desc, niter, may_be
*** 378,400 ****
*may_be_zero = (test != const_true_rtx);
! if (!(expr = count_loop_iterations (desc, true)))
! abort ();
!
! if (GET_CODE (expr) == CONST_INT)
! {
! *niter = INTVAL (expr);
! return true;
! }
!
! if (!(expr = count_loop_iterations (desc, false)))
! abort ();
!
! if (GET_CODE (expr) == CONST_INT)
! {
! *niter = INTVAL (expr);
! return true;
! }
return false;
}
--- 395,411 ----
*may_be_zero = (test != const_true_rtx);
! for (ainit = desc->var_alts; ainit; ainit = XEXP (ainit, 1))
! for (alim = desc->lim_alts; alim; alim = XEXP (alim, 1))
! {
! if (!(expr = count_loop_iterations (desc, XEXP (ainit, 0), XEXP (alim, 0))))
! abort ();
! if (GET_CODE (expr) == CONST_INT)
! {
! *niter = INTVAL (expr);
! return true;
! }
! }
return false;
}
*************** simple_loop_exit_p (loops, loop, exit_ed
*** 455,464 ****
/* Find initial value of var. */
e = loop_preheader_edge (loop);
! desc->init = variable_initial_value (e->src->end, e->src, desc->var, NULL);
/* Number of iterations. */
! if (!count_loop_iterations (desc, false))
return false;
desc->const_iter = constant_iterations (desc, &desc->niter, &desc->may_be_zero);
--- 466,475 ----
/* Find initial value of var. */
e = loop_preheader_edge (loop);
! desc->var_alts = variable_initial_values (e, desc->var);
/* Number of iterations. */
! if (!count_loop_iterations (desc, NULL, NULL))
return false;
desc->const_iter = constant_iterations (desc, &desc->niter, &desc->may_be_zero);
*************** simple_loop_exit_p (loops, loop, exit_ed
*** 468,502 ****
if (desc->postincr)
fprintf (rtl_dump_file,
"; does postincrement after loop exit condition\n");
! if (desc->var)
! {
! fprintf (rtl_dump_file, "; Induction variable:");
! 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:");
! print_simple_rtl (rtl_dump_file, desc->init);
! fputc ('\n', rtl_dump_file);
! }
! if (desc->lim)
! {
! fprintf (rtl_dump_file, "; Compared with:");
! print_simple_rtl (rtl_dump_file, desc->lim);
! fputc ('\n', rtl_dump_file);
! }
! if (desc->cond)
! {
! fprintf (rtl_dump_file, "; Exit condtion:");
! if (desc->neg)
! fprintf (rtl_dump_file, "(negated)");
! fprintf (rtl_dump_file, "%s\n", GET_RTX_NAME (desc->cond));
! fputc ('\n', rtl_dump_file);
! }
}
return true;
}
--- 479,510 ----
if (desc->postincr)
fprintf (rtl_dump_file,
"; does postincrement after loop exit condition\n");
!
! fprintf (rtl_dump_file, "; Induction variable:");
! print_simple_rtl (rtl_dump_file, desc->var);
! fputc ('\n', rtl_dump_file);
!
! fprintf (rtl_dump_file, "; Initial values:");
! print_simple_rtl (rtl_dump_file, desc->var_alts);
! fputc ('\n', rtl_dump_file);
!
fprintf (rtl_dump_file, "; Stride:");
print_simple_rtl (rtl_dump_file, desc->stride);
fputc ('\n', rtl_dump_file);
!
! fprintf (rtl_dump_file, "; Compared with:");
! print_simple_rtl (rtl_dump_file, desc->lim);
! fputc ('\n', rtl_dump_file);
!
! fprintf (rtl_dump_file, "; Alternative values:");
! print_simple_rtl (rtl_dump_file, desc->lim_alts);
! fputc ('\n', rtl_dump_file);
!
! fprintf (rtl_dump_file, "; Exit condition:");
! if (desc->neg)
! fprintf (rtl_dump_file, "(negated)");
! fprintf (rtl_dump_file, "%s\n", GET_RTX_NAME (desc->cond));
! fputc ('\n', rtl_dump_file);
}
return true;
}
*************** simple_loop_exit_p (loops, loop, exit_ed
*** 512,529 ****
These cases needs to be eighter cared by copying the loop test in the front
of loop or keeping the test in first iteration of loop.
! When INITIAL is set, the initial values of reigsters are used instead
! of registers themselves, that may lead to expression to be simplified
! and computed at compile time. */
static rtx
! count_loop_iterations (desc, initial)
struct loop_desc *desc;
! int initial;
{
enum rtx_code cond = desc->cond;
- rtx exp = initial && 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. */
--- 520,538 ----
These cases needs to be eighter cared by copying the loop test in the front
of loop or keeping the test in first iteration of loop.
! When INIT/LIM are set, they are used instead of var/lim of DESC. */
static rtx
! count_loop_iterations (desc, init, lim)
struct loop_desc *desc;
! rtx init;
! rtx lim;
{
enum rtx_code cond = desc->cond;
rtx stride = desc->stride;
! rtx mod, exp;
!
! init = init ? copy_rtx (init) : copy_rtx (desc->var);
! lim = lim ? copy_rtx (lim) : copy_rtx (desc->lim);
/* 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. */
*************** count_loop_iterations (desc, initial)
*** 542,548 ****
|| cond == GTU)
return NULL;
exp = simplify_gen_binary (MINUS, GET_MODE (desc->var),
! copy_rtx (desc->lim), exp);
}
else
{
--- 551,557 ----
|| cond == GTU)
return NULL;
exp = simplify_gen_binary (MINUS, GET_MODE (desc->var),
! lim, init);
}
else
{
*************** count_loop_iterations (desc, initial)
*** 551,557 ****
|| 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));
}
--- 560,566 ----
|| cond == LTU)
return NULL;
exp = simplify_gen_binary (MINUS, GET_MODE (desc->var),
! init, lim);
stride = simplify_gen_unary (NEG, GET_MODE (desc->var),
stride, GET_MODE (desc->var));
}
*************** test_for_iteration (desc, iter)
*** 640,646 ****
unsigned HOST_WIDE_INT iter;
{
enum rtx_code cond = desc->cond;
! rtx exp = desc->init ? copy_rtx (desc->init) : desc->var;
rtx addval;
/* Give up on floating point modes and friends. It can be possible to do
--- 649,655 ----
unsigned HOST_WIDE_INT iter;
{
enum rtx_code cond = desc->cond;
! rtx exp = XEXP (desc->var_alts, 0);
rtx addval;
/* Give up on floating point modes and friends. It can be possible to do
*************** unroll_loop_runtime_iterations (loops, l
*** 899,905 ****
/* Normalization. */
start_sequence ();
! niter = count_loop_iterations (desc, false);
if (!niter)
abort ();
niter = force_operand (niter, NULL);
--- 908,914 ----
/* Normalization. */
start_sequence ();
! niter = count_loop_iterations (desc, NULL, NULL);
if (!niter)
abort ();
niter = force_operand (niter, NULL);
More information about the Gcc-patches
mailing list