This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[lno] Some tree-ssa-loop-niter.c improvements
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Tue, 25 May 2004 16:17:55 +0200
- Subject: [lno] Some tree-ssa-loop-niter.c improvements
Hello,
this patch makes several improvements to tree-ssa-loop-niter.c and
related iv analysis stuff:
-- Induction variables like while (...) { ... i = i + a; }
where scev can prove that a is a constant are handled.
-- Evolutions of variables in the outer loops are taken into account
for simplifying the number of iterations and assumptions.
-- number_of_iterations_in_loop is based purely on
number_of_iterations_exit for now, until the misscompilations it
cause are fixed (Sebastian, IIRC you already posted some patch for
the problem; so if you verify that it indeed works, of course
reenable the old code).
Zdenek
Index: ChangeLog.lno
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ChangeLog.lno,v
retrieving revision 1.1.2.163
diff -c -3 -p -r1.1.2.163 ChangeLog.lno
*** ChangeLog.lno 24 May 2004 21:58:01 -0000 1.1.2.163
--- ChangeLog.lno 25 May 2004 14:00:23 -0000
***************
*** 1,3 ****
--- 1,16 ----
+ 2004-05-25 Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.cz>
+
+ * tree-scalar-evolution.c (resolve_mixers): New function.
+ (already_instantiated): Type changed to bitmap.
+ (scev_initialize, scev_finalize): Reflect the change.
+ (analyze_scalar_evolution_in_loop): Use resolve_mixers.
+ (instantiate_parameters_1): Add possibility to just resolve mixers.
+ Fold the results.
+ (number_of_iterations_in_loop): Use number_of_iterations_exit.
+ * tree-ssa-loop-niter.c (simplify_using_outer_evolutions): New
+ function.
+ (number_of_iterations_exit): Use it.
+
2004-05-24 Dale Johannesen <dalej@apple.com>
* loop-invariant.c (find_defs): Add DF_EQUIV_NOTES.
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-scalar-evolution.c,v
retrieving revision 1.1.2.48
diff -c -3 -p -r1.1.2.48 tree-scalar-evolution.c
*** tree-scalar-evolution.c 19 May 2004 22:05:04 -0000 1.1.2.48
--- tree-scalar-evolution.c 25 May 2004 14:00:24 -0000
*************** Software Foundation, 59 Temple Place - S
*** 265,270 ****
--- 265,271 ----
#include "flags.h"
static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
+ static tree resolve_mixers (struct loop *, tree);
/* The cached information about a ssa name VAR, claiming that inside LOOP,
the value of VAR can be expressed as CHREC. */
*************** tree chrec_top;
*** 295,301 ****
tree chrec_bot;
static struct loops *current_loops;
! static varray_type already_instantiated;
static htab_t scalar_evolution_info;
--- 296,302 ----
tree chrec_bot;
static struct loops *current_loops;
! static bitmap already_instantiated;
static htab_t scalar_evolution_info;
*************** analyze_scalar_evolution_in_loop (struct
*** 2409,2414 ****
--- 2410,2416 ----
while (1)
{
ev = analyze_scalar_evolution (use_loop, ev);
+ ev = resolve_mixers (use_loop, ev);
if (use_loop == wrto_loop)
return ev;
*************** analyze_scalar_evolution_in_loop (struct
*** 2425,2434 ****
}
/* Analyze all the parameters of the chrec that were left under a symbolic form,
! with respect to LOOP. CHREC is the chrec to instantiate. */
static tree
! instantiate_parameters_1 (struct loop *loop, tree chrec)
{
tree res, op0, op1, op2;
basic_block def_bb;
--- 2427,2439 ----
}
/* Analyze all the parameters of the chrec that were left under a symbolic form,
! with respect to LOOP. CHREC is the chrec to instantiate. If
! ALLOW_SUPERLOOP_CHRECS is true, replacing loop invariants with
! outer loop chrecs is done. */
static tree
! instantiate_parameters_1 (struct loop *loop, tree chrec,
! bool allow_superloop_chrecs)
{
tree res, op0, op1, op2;
basic_block def_bb;
*************** instantiate_parameters_1 (struct loop *l
*** 2446,2471 ****
case SSA_NAME:
def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (chrec));
! /* A parameter, nothing to do. */
! if (!def_bb)
return chrec;
/* Don't instantiate the SSA_NAME if it is in a mixer
structure. This is used for avoiding the instantiation of
recursively defined functions, such as:
! | a_2 -> {0, +, 1, +, a_2}_1
! Note: the size of already_instantiated is proportional to
! the degree of the evolution function. This is the number
! of parameters that have to be instantiated, and is almost
! all the time less than 2. */
! if (tree_is_in_varray_tree_p (chrec, already_instantiated))
{
if (!flow_bb_inside_loop_p (loop, def_bb))
{
! /* It is an invariant in LOOP, so we may keep the symbolic
! form. */
return chrec;
}
else
--- 2451,2474 ----
case SSA_NAME:
def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (chrec));
! /* A parameter (or loop invariant and we do not want to include
! evolutions in outer loops), nothing to do. */
! if (!def_bb
! || (!allow_superloop_chrecs
! && !flow_bb_inside_loop_p (loop, def_bb)))
return chrec;
/* Don't instantiate the SSA_NAME if it is in a mixer
structure. This is used for avoiding the instantiation of
recursively defined functions, such as:
! | a_2 -> {0, +, 1, +, a_2}_1 */
! if (bitmap_bit_p (already_instantiated, SSA_NAME_VERSION (chrec)))
{
if (!flow_bb_inside_loop_p (loop, def_bb))
{
! /* We may keep the loop invariant in symbolic form. */
return chrec;
}
else
*************** instantiate_parameters_1 (struct loop *l
*** 2481,2529 ****
the result again. Enqueue the SSA_NAME such that it will
never be instantiated twice, avoiding the cyclic
instantiation in mixers. */
! VARRAY_PUSH_TREE (already_instantiated, chrec);
res = analyze_scalar_evolution (def_loop, chrec);
! res = instantiate_parameters (loop, res);
! VARRAY_POP (already_instantiated);
return res;
case POLYNOMIAL_CHREC:
! op0 = instantiate_parameters (loop, CHREC_LEFT (chrec));
! op1 = instantiate_parameters (loop, CHREC_RIGHT (chrec));
return build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
case EXPONENTIAL_CHREC:
! op0 = instantiate_parameters (loop, CHREC_LEFT (chrec));
! op1 = instantiate_parameters (loop, CHREC_RIGHT (chrec));
return build_exponential_chrec (CHREC_VARIABLE (chrec), op0, op1);
case PEELED_CHREC:
! op0 = instantiate_parameters (loop, CHREC_LEFT (chrec));
! op1 = instantiate_parameters (loop, CHREC_RIGHT (chrec));
return build_peeled_chrec (CHREC_VARIABLE (chrec), op0, op1);
case INTERVAL_CHREC:
! op0 = instantiate_parameters (loop, CHREC_LOW (chrec));
! op1 = instantiate_parameters (loop, CHREC_UP (chrec));
return build_interval_chrec (op0, op1);
case PLUS_EXPR:
! op0 = instantiate_parameters (loop, TREE_OPERAND (chrec, 0));
! op1 = instantiate_parameters (loop, TREE_OPERAND (chrec, 1));
return chrec_fold_plus (TREE_TYPE (chrec), op0, op1);
case MINUS_EXPR:
! op0 = instantiate_parameters (loop, TREE_OPERAND (chrec, 0));
! op1 = instantiate_parameters (loop, TREE_OPERAND (chrec, 1));
return chrec_fold_minus (TREE_TYPE (chrec), op0, op1);
case MULT_EXPR:
! op0 = instantiate_parameters (loop, TREE_OPERAND (chrec, 0));
! op1 = instantiate_parameters (loop, TREE_OPERAND (chrec, 1));
return chrec_fold_multiply (TREE_TYPE (chrec), op0, op1);
case NOP_EXPR:
! op0 = instantiate_parameters (loop, TREE_OPERAND (chrec, 0));
return chrec_convert (TREE_TYPE (chrec), op0);
default:
--- 2484,2549 ----
the result again. Enqueue the SSA_NAME such that it will
never be instantiated twice, avoiding the cyclic
instantiation in mixers. */
! bitmap_set_bit (already_instantiated, SSA_NAME_VERSION (chrec));
res = analyze_scalar_evolution (def_loop, chrec);
! res = instantiate_parameters_1 (loop, res, allow_superloop_chrecs);
! bitmap_clear_bit (already_instantiated, SSA_NAME_VERSION (chrec));
return res;
case POLYNOMIAL_CHREC:
! op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
! allow_superloop_chrecs);
! op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
! allow_superloop_chrecs);
return build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
case EXPONENTIAL_CHREC:
! op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
! allow_superloop_chrecs);
! op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
! allow_superloop_chrecs);
return build_exponential_chrec (CHREC_VARIABLE (chrec), op0, op1);
case PEELED_CHREC:
! op0 = instantiate_parameters_1 (loop, CHREC_LEFT (chrec),
! allow_superloop_chrecs);
! op1 = instantiate_parameters_1 (loop, CHREC_RIGHT (chrec),
! allow_superloop_chrecs);
return build_peeled_chrec (CHREC_VARIABLE (chrec), op0, op1);
case INTERVAL_CHREC:
! op0 = instantiate_parameters_1 (loop, CHREC_LOW (chrec),
! allow_superloop_chrecs);
! op1 = instantiate_parameters_1 (loop, CHREC_UP (chrec),
! allow_superloop_chrecs);
return build_interval_chrec (op0, op1);
case PLUS_EXPR:
! op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
! allow_superloop_chrecs);
! op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
! allow_superloop_chrecs);
return chrec_fold_plus (TREE_TYPE (chrec), op0, op1);
case MINUS_EXPR:
! op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
! allow_superloop_chrecs);
! op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
! allow_superloop_chrecs);
return chrec_fold_minus (TREE_TYPE (chrec), op0, op1);
case MULT_EXPR:
! op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
! allow_superloop_chrecs);
! op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
! allow_superloop_chrecs);
return chrec_fold_multiply (TREE_TYPE (chrec), op0, op1);
case NOP_EXPR:
! case CONVERT_EXPR:
! case NON_LVALUE_EXPR:
! op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
! allow_superloop_chrecs);
return chrec_convert (TREE_TYPE (chrec), op0);
default:
*************** instantiate_parameters_1 (struct loop *l
*** 2533,2551 ****
switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
{
case 3:
! op0 = instantiate_parameters (loop, TREE_OPERAND (chrec, 0));
! op1 = instantiate_parameters (loop, TREE_OPERAND (chrec, 1));
! op2 = instantiate_parameters (loop, TREE_OPERAND (chrec, 2));
! return build (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1, op2);
case 2:
! op0 = instantiate_parameters (loop, TREE_OPERAND (chrec, 0));
! op1 = instantiate_parameters (loop, TREE_OPERAND (chrec, 1));
! return build (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1);
case 1:
! op0 = instantiate_parameters (loop, TREE_OPERAND (chrec, 0));
! return build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0);
case 0:
return chrec;
--- 2553,2578 ----
switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
{
case 3:
! op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
! allow_superloop_chrecs);
! op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
! allow_superloop_chrecs);
! op2 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 2),
! allow_superloop_chrecs);
! return fold (build (TREE_CODE (chrec),
! TREE_TYPE (chrec), op0, op1, op2));
case 2:
! op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
! allow_superloop_chrecs);
! op1 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 1),
! allow_superloop_chrecs);
! return fold (build (TREE_CODE (chrec), TREE_TYPE (chrec), op0, op1));
case 1:
! op0 = instantiate_parameters_1 (loop, TREE_OPERAND (chrec, 0),
! allow_superloop_chrecs);
! return fold (build1 (TREE_CODE (chrec), TREE_TYPE (chrec), op0));
case 0:
return chrec;
*************** instantiate_parameters (struct loop *loo
*** 2577,2583 ****
fprintf (dump_file, ")\n");
}
! res = instantiate_parameters_1 (loop, chrec);
if (dump_file && (dump_flags & TDF_DETAILS))
{
--- 2604,2610 ----
fprintf (dump_file, ")\n");
}
! res = instantiate_parameters_1 (loop, chrec, true);
if (dump_file && (dump_flags & TDF_DETAILS))
{
*************** instantiate_parameters (struct loop *loo
*** 2589,2594 ****
--- 2616,2630 ----
return res;
}
+ /* Similar to instantiate_parameters, but does not introduce the
+ evolutions in outer loops for LOOP invariants in CHREC. */
+
+ static tree
+ resolve_mixers (struct loop *loop, tree chrec)
+ {
+ return instantiate_parameters_1 (loop, chrec, false);
+ }
+
/* Entry point for the analysis of the number of iterations pass.
This function tries to safely approximate the number of iterations
the loop will run. When this property is not decidable at compile
*************** instantiate_parameters (struct loop *loo
*** 2612,2629 ****
tree
number_of_iterations_in_loop (struct loop *loop)
{
! enum tree_code code;
! tree res;
! tree cond, test, opnd0, opnd1;
! tree chrec0, chrec1;
edge exit;
/* Determine whether the number_of_iterations_in_loop has already
been computed. */
res = loop_nb_iterations (loop);
if (res)
return res;
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(number_of_iterations_in_loop \n");
--- 2648,2688 ----
tree
number_of_iterations_in_loop (struct loop *loop)
{
! tree res, type;
edge exit;
+ struct tree_niter_desc niter_desc;
/* Determine whether the number_of_iterations_in_loop has already
been computed. */
res = loop_nb_iterations (loop);
if (res)
return res;
+ res = chrec_top;
+ /* The code in first_iteration_non_satisfying is buggy, so for
+ now play it safe. */
+ if (!loop_exit_edges (loop))
+ goto end;
+ exit = loop_exit_edge (loop, 0);
+
+ if (!number_of_iterations_exit (loop, exit, &niter_desc))
+ goto end;
+
+ type = TREE_TYPE (niter_desc.niter);
+ if (integer_nonzerop (niter_desc.may_be_zero))
+ res = convert (type, integer_zero_node);
+ else if (integer_zerop (niter_desc.may_be_zero))
+ res = niter_desc.niter;
+ else
+ res = build (COND_EXPR, type, niter_desc.may_be_zero,
+ convert (type, integer_zero_node),
+ niter_desc.niter);
+
+ #if 0
+ enum tree_code code;
+ tree cond, test, opnd0, opnd1;
+ tree chrec0, chrec1;
+
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(number_of_iterations_in_loop \n");
*************** number_of_iterations_in_loop (struct loo
*** 2706,2712 ****
--- 2765,2773 ----
}
res = first_iteration_non_satisfying (code, loop->num, chrec0, chrec1);
+ #endif
+ end:
return set_nb_iterations_in_loop (loop, res);
}
*************** scev_initialize (struct loops *loops)
*** 3005,3012 ****
scalar_evolution_info = htab_create (100, hash_scev_info,
eq_scev_info, del_scev_info);
! VARRAY_TREE_INIT (already_instantiated, 3,
! "already_instantiated");
initialize_scalar_evolutions_analyzer ();
--- 3066,3072 ----
scalar_evolution_info = htab_create (100, hash_scev_info,
eq_scev_info, del_scev_info);
! already_instantiated = BITMAP_XMALLOC ();
initialize_scalar_evolutions_analyzer ();
*************** void
*** 3152,3158 ****
scev_finalize (void)
{
htab_delete (scalar_evolution_info);
! already_instantiated = NULL;
current_loops = NULL;
}
--- 3212,3218 ----
scev_finalize (void)
{
htab_delete (scalar_evolution_info);
! BITMAP_XFREE (already_instantiated);
current_loops = NULL;
}
Index: tree-ssa-loop-niter.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-niter.c,v
retrieving revision 1.1.2.1
diff -c -3 -p -r1.1.2.1 tree-ssa-loop-niter.c
*** tree-ssa-loop-niter.c 30 Apr 2004 23:38:49 -0000 1.1.2.1
--- tree-ssa-loop-niter.c 25 May 2004 14:00:24 -0000
*************** zero_iter:
*** 427,432 ****
--- 427,482 ----
return;
}
+ /* Tries to simplify EXPR using the evolutions of the loop invariants
+ in the outer loops. */
+
+ static tree
+ simplify_using_outer_evolutions (struct loop *loop, tree expr)
+ {
+ enum tree_code code = TREE_CODE (expr);
+ bool changed;
+ tree e;
+
+ if (is_gimple_min_invariant (expr))
+ return expr;
+
+ if (code == TRUTH_OR_EXPR
+ || code == TRUTH_AND_EXPR
+ || code == COND_EXPR)
+ {
+ changed = false;
+
+ e = TREE_OPERAND (expr, 0);
+ TREE_OPERAND (expr, 0) = simplify_using_outer_evolutions (loop, e);
+ if (TREE_OPERAND (expr, 0) != e)
+ changed = true;
+
+ e = TREE_OPERAND (expr, 1);
+ TREE_OPERAND (expr, 1) = simplify_using_outer_evolutions (loop, e);
+ if (TREE_OPERAND (expr, 1) != e)
+ changed = true;
+
+ if (code == COND_EXPR)
+ {
+ e = TREE_OPERAND (expr, 2);
+ TREE_OPERAND (expr, 2) = simplify_using_outer_evolutions (loop, e);
+ if (TREE_OPERAND (expr, 2) != e)
+ changed = true;
+ }
+
+ if (changed)
+ expr = fold (expr);
+
+ return expr;
+ }
+
+ e = instantiate_parameters (loop, expr);
+ if (is_gimple_min_invariant (e))
+ return e;
+
+ return expr;
+ }
+
/* Stores description of number of iterations of LOOP derived from EXIT
in NITER. */
*************** number_of_iterations_exit (struct loop *
*** 479,486 ****
--- 529,545 ----
if (!simple_iv (loop, stmt, op1, &base1, &step1))
return false;
+ niter->niter = NULL_TREE;
number_of_iterations_cond (type, base0, step0, code, base1, step1,
niter);
+ if (!niter->niter)
+ return false;
+
+ niter->assumptions = simplify_using_outer_evolutions (loop,
+ niter->assumptions);
+ niter->may_be_zero = simplify_using_outer_evolutions (loop,
+ niter->may_be_zero);
+ niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
return integer_onep (niter->assumptions);
}