[patch] Some ivopts improvements
Zdenek Dvorak
rakdver@atrey.karlin.mff.cuni.cz
Thu Sep 30 19:11:00 GMT 2004
Hello,
this patch addresses several issues with ivopts and induction variable
analysis I noticed during investigation of PR 17679:
-- ivopts may use difference of addresses of two different memory
objects; this is one of causes the PR, is not really useful
except in very rare situations, and may spoil the code
significantly in not so rare situations. So this patch makes
ivopts avoid this possibility.
-- we performed induction variable elimination only for loops with just
single exit. It is trivial to extend this for all exits of the loop
that dominate the latch (it is of course possible to perform
induction variable elimination with all conditions in loop body,
but this would require us to be much more careful).
-- on numerous places in scev and # of iterations analysis, convert
was used instead of fold_convert and build instead of buildN.
-- some utilities in # of iterations analysis used integer_zerop/
integer_nonzerop. These functions do not behave sanely for
overflowed constants, which may cause (and does with the improvement
to iv elimination) endless loops during compilation. So we use
functions that do not care about overflows instead.
Bootstrapped & regtested on i686 and x86_64.
Zdenek
* tree-chrec.c (chrec_fold_plus_poly_poly, chrec_fold_plus_1,
chrec_fold_multiply): Use fold_convert or build_int_cst_type instead
od fonvert.
* tree-scalar-evolution.c (compute_overall_effect_of_inner_loop,
add_to_evolution, set_nb_iterations_in_loop, follow_ssa_edge_in_rhs,
follow_ssa_edge_in_rhs): Ditto.
* tree-ssa-loop-ivopts.c (struct iv): Add base_object field.
(dump_iv): Dump base_object.
(dump_use, dump_cand): Use dump_iv.
(determine_base_object): New function.
(alloc_iv): Initialize base_object field.
(record_use): Clear the ssa_name field of iv.
(get_computation_cost_at): Do not use difference of addresses of
two different objects.
(may_eliminate_iv): Do not require the loop to have just single exit.
* tree-ssa-loop-niter.c (zero_p): Do not check for overflows.
(nonzero_p): New function.
(inverse, number_of_iterations_cond, simplify_using_outer_evolutions,
tree_simplify_using_condition, simplify_using_initial_conditions,
loop_niter_by_eval, find_loop_niter_by_eval,
estimate_numbers_of_iterations_loop, compare_trees,
upper_bound_in_type, lower_bound_in_type,
can_count_iv_in_wider_type_bound): Use buildN instead of build. Use
fold_convert or build_int_cst_type instead of convert. Use (non)zero_p
instead of integer_(non)zerop.
Index: tree-chrec.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-chrec.c,v
retrieving revision 2.9
diff -c -3 -p -r2.9 tree-chrec.c
*** tree-chrec.c 19 Sep 2004 18:01:47 -0000 2.9
--- tree-chrec.c 30 Sep 2004 10:28:40 -0000
*************** chrec_fold_plus_poly_poly (enum tree_cod
*** 117,123 ****
(CHREC_VARIABLE (poly1),
chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
chrec_fold_multiply (type, CHREC_RIGHT (poly1),
! convert (type, integer_minus_one_node)));
}
if (CHREC_VARIABLE (poly0) > CHREC_VARIABLE (poly1))
--- 117,123 ----
(CHREC_VARIABLE (poly1),
chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
chrec_fold_multiply (type, CHREC_RIGHT (poly1),
! build_int_cst_type (type, -1)));
}
if (CHREC_VARIABLE (poly0) > CHREC_VARIABLE (poly1))
*************** chrec_fold_plus_1 (enum tree_code code,
*** 282,290 ****
return build_polynomial_chrec
(CHREC_VARIABLE (op1),
chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
! chrec_fold_multiply (type, CHREC_RIGHT (op1),
! convert (type,
! integer_minus_one_node)));
default:
if (tree_contains_chrecs (op0)
--- 282,289 ----
return build_polynomial_chrec
(CHREC_VARIABLE (op1),
chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
! chrec_fold_multiply (type, CHREC_RIGHT (op1),
! build_int_cst_type (type, -1)));
default:
if (tree_contains_chrecs (op0)
*************** chrec_fold_multiply (tree type,
*** 347,353 ****
if (integer_onep (op1))
return op0;
if (integer_zerop (op1))
! return convert (type, integer_zero_node);
return build_polynomial_chrec
(CHREC_VARIABLE (op0),
--- 346,352 ----
if (integer_onep (op1))
return op0;
if (integer_zerop (op1))
! return build_int_cst_type (type, 0);
return build_polynomial_chrec
(CHREC_VARIABLE (op0),
*************** chrec_fold_multiply (tree type,
*** 360,366 ****
return op1;
if (integer_zerop (op0))
! return convert (type, integer_zero_node);
switch (TREE_CODE (op1))
{
--- 359,365 ----
return op1;
if (integer_zerop (op0))
! return build_int_cst_type (type, 0);
switch (TREE_CODE (op1))
{
*************** chrec_fold_multiply (tree type,
*** 374,380 ****
if (integer_onep (op1))
return op0;
if (integer_zerop (op1))
! return convert (type, integer_zero_node);
return fold (build (MULT_EXPR, type, op0, op1));
}
}
--- 373,379 ----
if (integer_onep (op1))
return op0;
if (integer_zerop (op1))
! return build_int_cst_type (type, 0);
return fold (build (MULT_EXPR, type, op0, op1));
}
}
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-scalar-evolution.c,v
retrieving revision 2.7
diff -c -3 -p -r2.7 tree-scalar-evolution.c
*** tree-scalar-evolution.c 17 Sep 2004 09:14:09 -0000 2.7
--- tree-scalar-evolution.c 30 Sep 2004 10:28:40 -0000
*************** compute_overall_effect_of_inner_loop (st
*** 506,514 ****
/* Number of iterations is off by one (the ssa name we
analyze must be defined before the exit). */
nb_iter = chrec_fold_minus (chrec_type (nb_iter),
! nb_iter,
! fold_convert (chrec_type (nb_iter),
! integer_one_node));
/* evolution_fn is the evolution function in LOOP. Get
its value in the nb_iter-th iteration. */
--- 506,513 ----
/* Number of iterations is off by one (the ssa name we
analyze must be defined before the exit). */
nb_iter = chrec_fold_minus (chrec_type (nb_iter),
! nb_iter,
! build_int_cst_type (chrec_type (nb_iter), 1));
/* evolution_fn is the evolution function in LOOP. Get
its value in the nb_iter-th iteration. */
*************** add_to_evolution (unsigned loop_nb,
*** 896,902 ****
if (code == MINUS_EXPR)
to_add = chrec_fold_multiply (type, to_add,
! fold_convert (type, integer_minus_one_node));
res = add_to_evolution_1 (loop_nb, chrec_before, to_add);
--- 895,901 ----
if (code == MINUS_EXPR)
to_add = chrec_fold_multiply (type, to_add,
! build_int_cst_type (type, -1));
res = add_to_evolution_1 (loop_nb, chrec_before, to_add);
*************** static inline tree
*** 916,922 ****
set_nb_iterations_in_loop (struct loop *loop,
tree res)
{
! res = chrec_fold_plus (chrec_type (res), res, integer_one_node);
/* FIXME HWI: However we want to store one iteration less than the
count of the loop in order to be compatible with the other
nb_iter computations in loop-iv. This also allows the
--- 915,923 ----
set_nb_iterations_in_loop (struct loop *loop,
tree res)
{
! res = chrec_fold_plus (chrec_type (res), res,
! build_int_cst_type (chrec_type (res), 1));
!
/* FIXME HWI: However we want to store one iteration less than the
count of the loop in order to be compatible with the other
nb_iter computations in loop-iv. This also allows the
*************** follow_ssa_edge_in_rhs (struct loop *loo
*** 1209,1216 ****
(loop->num,
chrec_fold_multiply (type_rhs,
*evolution_of_loop,
! fold_convert (type_rhs,
! integer_minus_one_node)),
PLUS_EXPR, rhs0);
}
}
--- 1210,1216 ----
(loop->num,
chrec_fold_multiply (type_rhs,
*evolution_of_loop,
! build_int_cst_type (type_rhs, -1)),
PLUS_EXPR, rhs0);
}
}
*************** follow_ssa_edge_in_rhs (struct loop *loo
*** 1241,1247 ****
(loop->num,
chrec_fold_multiply (type_rhs,
*evolution_of_loop,
! fold_convert (type_rhs, integer_minus_one_node)),
PLUS_EXPR, rhs0);
}
--- 1241,1247 ----
(loop->num,
chrec_fold_multiply (type_rhs,
*evolution_of_loop,
! build_int_cst_type (type_rhs, -1)),
PLUS_EXPR, rhs0);
}
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivopts.c,v
retrieving revision 2.15
diff -c -3 -p -r2.15 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c 28 Sep 2004 07:59:52 -0000 2.15
--- tree-ssa-loop-ivopts.c 30 Sep 2004 10:28:40 -0000
*************** Software Foundation, 59 Temple Place - S
*** 104,109 ****
--- 104,110 ----
struct iv
{
tree base; /* Initial value of the iv. */
+ tree base_object; /* A memory object to that the induction variable points. */
tree step; /* Step of the iv (constant only). */
tree ssa_name; /* The ssa name with the value. */
bool biv_p; /* Is it a biv? */
*************** extern void dump_iv (FILE *, struct iv *
*** 301,309 ****
void
dump_iv (FILE *file, struct iv *iv)
{
! fprintf (file, "ssa name ");
! print_generic_expr (file, iv->ssa_name, TDF_SLIM);
! fprintf (file, "\n");
fprintf (file, " type ");
print_generic_expr (file, TREE_TYPE (iv->base), TDF_SLIM);
--- 302,313 ----
void
dump_iv (FILE *file, struct iv *iv)
{
! if (iv->ssa_name)
! {
! fprintf (file, "ssa name ");
! print_generic_expr (file, iv->ssa_name, TDF_SLIM);
! fprintf (file, "\n");
! }
fprintf (file, " type ");
print_generic_expr (file, TREE_TYPE (iv->base), TDF_SLIM);
*************** dump_iv (FILE *file, struct iv *iv)
*** 326,331 ****
--- 330,342 ----
fprintf (file, "\n");
}
+ if (iv->base_object)
+ {
+ fprintf (file, " base object ");
+ print_generic_expr (file, iv->base_object, TDF_SLIM);
+ fprintf (file, "\n");
+ }
+
if (iv->biv_p)
fprintf (file, " is a biv\n");
}
*************** extern void dump_use (FILE *, struct iv_
*** 336,343 ****
void
dump_use (FILE *file, struct iv_use *use)
{
- struct iv *iv = use->iv;
-
fprintf (file, "use %d\n", use->id);
switch (use->type)
--- 347,352 ----
*************** dump_use (FILE *file, struct iv_use *use
*** 371,396 ****
print_generic_expr (file, *use->op_p, TDF_SLIM);
fprintf (file, "\n");
! fprintf (file, " type ");
! print_generic_expr (file, TREE_TYPE (iv->base), TDF_SLIM);
! fprintf (file, "\n");
!
! if (iv->step)
! {
! fprintf (file, " base ");
! print_generic_expr (file, iv->base, TDF_SLIM);
! fprintf (file, "\n");
!
! fprintf (file, " step ");
! print_generic_expr (file, iv->step, TDF_SLIM);
! fprintf (file, "\n");
! }
! else
! {
! fprintf (file, " invariant ");
! print_generic_expr (file, iv->base, TDF_SLIM);
! fprintf (file, "\n");
! }
fprintf (file, " related candidates ");
dump_bitmap (file, use->related_cands);
--- 380,386 ----
print_generic_expr (file, *use->op_p, TDF_SLIM);
fprintf (file, "\n");
! dump_iv (file, use->iv);
fprintf (file, " related candidates ");
dump_bitmap (file, use->related_cands);
*************** dump_cand (FILE *file, struct iv_cand *c
*** 446,471 ****
break;
}
! fprintf (file, " type ");
! print_generic_expr (file, TREE_TYPE (iv->base), TDF_SLIM);
! fprintf (file, "\n");
!
! if (iv->step)
! {
! fprintf (file, " base ");
! print_generic_expr (file, iv->base, TDF_SLIM);
! fprintf (file, "\n");
!
! fprintf (file, " step ");
! print_generic_expr (file, iv->step, TDF_SLIM);
! fprintf (file, "\n");
! }
! else
! {
! fprintf (file, " invariant ");
! print_generic_expr (file, iv->base, TDF_SLIM);
! fprintf (file, "\n");
! }
}
/* Returns the info for ssa version VER. */
--- 436,442 ----
break;
}
! dump_iv (file, iv);
}
/* Returns the info for ssa version VER. */
*************** tree_ssa_iv_optimize_init (struct loops
*** 626,631 ****
--- 597,648 ----
VARRAY_GENERIC_PTR_NOGC_INIT (decl_rtl_to_reset, 20, "decl_rtl_to_reset");
}
+ /* Returns a memory object to that EXPR points. In case we are able to
+ determine that it does not point to any such object, NULL is returned. */
+
+ static tree
+ determine_base_object (tree expr)
+ {
+ enum tree_code code = TREE_CODE (expr);
+ tree base, obj, op0, op1;
+
+ if (!POINTER_TYPE_P (TREE_TYPE (expr)))
+ return NULL_TREE;
+
+ switch (code)
+ {
+ case INTEGER_CST:
+ return NULL_TREE;
+
+ case ADDR_EXPR:
+ obj = TREE_OPERAND (expr, 0);
+ base = get_base_address (obj);
+
+ if (!base)
+ return fold_convert (ptr_type_node, expr);
+
+ return fold (build1 (ADDR_EXPR, ptr_type_node, base));
+
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ op0 = determine_base_object (TREE_OPERAND (expr, 0));
+ op1 = determine_base_object (TREE_OPERAND (expr, 1));
+
+ if (!op1)
+ return op0;
+
+ if (!op0)
+ return (code == PLUS_EXPR
+ ? op1
+ : fold (build1 (NEGATE_EXPR, ptr_type_node, op1)));
+
+ return fold (build (code, ptr_type_node, op0, op1));
+
+ default:
+ return fold_convert (ptr_type_node, expr);
+ }
+ }
+
/* Allocates an induction variable with given initial value BASE and step STEP
for loop LOOP. */
*************** alloc_iv (tree base, tree step)
*** 638,643 ****
--- 655,661 ----
step = NULL_TREE;
iv->base = base;
+ iv->base_object = determine_base_object (base);
iv->step = step;
iv->biv_p = false;
iv->have_use_for = false;
*************** record_use (struct ivopts_data *data, tr
*** 1001,1006 ****
--- 1019,1028 ----
use->op_p = use_p;
use->related_cands = BITMAP_XMALLOC ();
+ /* To avoid showing ssa name in the dumps, if it was not reset by the
+ caller. */
+ iv->ssa_name = NULL_TREE;
+
if (dump_file && (dump_flags & TDF_DETAILS))
dump_use (dump_file, use);
*************** get_computation_cost_at (struct ivopts_d
*** 2794,2799 ****
--- 2816,2834 ----
return INFTY;
}
+ if (address_p)
+ {
+ /* Do not try to express address of an object with computation based
+ on address of a different object. This may cause problems in rtl
+ level alias analysis (that does not expect this to be happening,
+ as this is illegal in C), and would be unlikely to be useful
+ anyway. */
+ if (use->iv->base_object
+ && cand->iv->base_object
+ && !operand_equal_p (use->iv->base_object, cand->iv->base_object, 0))
+ return INFTY;
+ }
+
if (!cst_and_fits_in_hwi (ustep)
|| !cst_and_fits_in_hwi (cstep))
return INFTY;
*************** may_eliminate_iv (struct loop *loop,
*** 2974,2996 ****
struct iv_use *use, struct iv_cand *cand,
enum tree_code *compare, tree *bound)
{
edge exit;
! struct tree_niter_desc *niter, new_niter;
tree wider_type, type, base;
!
! /* For now just very primitive -- we work just for the single exit condition,
! and are quite conservative about the possible overflows. TODO -- both of
! these can be improved. */
! exit = single_dom_exit (loop);
! if (!exit)
return false;
! if (use->stmt != last_stmt (exit->src))
return false;
! niter = &loop_data (loop)->niter;
! if (!niter->niter
! || !integer_nonzerop (niter->assumptions)
! || !integer_zerop (niter->may_be_zero))
return false;
if (exit->flags & EDGE_TRUE_VALUE)
--- 3009,3039 ----
struct iv_use *use, struct iv_cand *cand,
enum tree_code *compare, tree *bound)
{
+ basic_block ex_bb;
edge exit;
! struct tree_niter_desc niter, new_niter;
tree wider_type, type, base;
!
! /* For now works only for exits that dominate the loop latch. TODO -- extend
! for other conditions inside loop body. */
! ex_bb = bb_for_stmt (use->stmt);
! if (use->stmt != last_stmt (ex_bb)
! || TREE_CODE (use->stmt) != COND_EXPR)
return false;
! if (!dominated_by_p (CDI_DOMINATORS, loop->latch, ex_bb))
return false;
! exit = EDGE_SUCC (ex_bb, 0);
! if (flow_bb_inside_loop_p (loop, exit->dest))
! exit = EDGE_SUCC (ex_bb, 1);
! if (flow_bb_inside_loop_p (loop, exit->dest))
! return false;
!
! niter.niter = NULL_TREE;
! number_of_iterations_exit (loop, exit, &niter);
! if (!niter.niter
! || !integer_nonzerop (niter.assumptions)
! || !integer_zerop (niter.may_be_zero))
return false;
if (exit->flags & EDGE_TRUE_VALUE)
*************** may_eliminate_iv (struct loop *loop,
*** 2998,3004 ****
else
*compare = NE_EXPR;
! *bound = cand_value_at (loop, cand, use->stmt, niter->niter);
/* Let us check there is not some problem with overflows, by checking that
the number of iterations is unchanged. */
--- 3041,3047 ----
else
*compare = NE_EXPR;
! *bound = cand_value_at (loop, cand, use->stmt, niter.niter);
/* Let us check there is not some problem with overflows, by checking that
the number of iterations is unchanged. */
*************** may_eliminate_iv (struct loop *loop,
*** 3017,3025 ****
return false;
wider_type = TREE_TYPE (new_niter.niter);
! if (TYPE_PRECISION (wider_type) < TYPE_PRECISION (TREE_TYPE (niter->niter)))
! wider_type = TREE_TYPE (niter->niter);
! if (!operand_equal_p (fold_convert (wider_type, niter->niter),
fold_convert (wider_type, new_niter.niter), 0))
return false;
--- 3060,3068 ----
return false;
wider_type = TREE_TYPE (new_niter.niter);
! if (TYPE_PRECISION (wider_type) < TYPE_PRECISION (TREE_TYPE (niter.niter)))
! wider_type = TREE_TYPE (niter.niter);
! if (!operand_equal_p (fold_convert (wider_type, niter.niter),
fold_convert (wider_type, new_niter.niter), 0))
return false;
Index: tree-ssa-loop-niter.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-niter.c,v
retrieving revision 2.9
diff -c -3 -p -r2.9 tree-ssa-loop-niter.c
*** tree-ssa-loop-niter.c 28 Sep 2004 07:59:52 -0000 2.9
--- tree-ssa-loop-niter.c 30 Sep 2004 10:28:40 -0000
*************** Software Foundation, 59 Temple Place - S
*** 52,58 ****
*/
! /* Returns true if ARG is either NULL_TREE or constant zero. */
bool
zero_p (tree arg)
--- 52,59 ----
*/
! /* Returns true if ARG is either NULL_TREE or constant zero. Unlike
! integer_zerop, it does not care about overflow flags. */
bool
zero_p (tree arg)
*************** zero_p (tree arg)
*** 60,66 ****
if (!arg)
return true;
! return integer_zerop (arg);
}
/* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
--- 61,85 ----
if (!arg)
return true;
! if (TREE_CODE (arg) != INTEGER_CST)
! return false;
!
! return (TREE_INT_CST_LOW (arg) == 0 && TREE_INT_CST_HIGH (arg) == 0);
! }
!
! /* Returns true if ARG a nonzero constant. Unlike integer_nonzerop, it does
! not care about overflow flags. */
!
! static bool
! nonzero_p (tree arg)
! {
! if (!arg)
! return false;
!
! if (TREE_CODE (arg) != INTEGER_CST)
! return false;
!
! return (TREE_INT_CST_LOW (arg) != 0 || TREE_INT_CST_HIGH (arg) != 0);
}
/* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
*************** inverse (tree x, tree mask)
*** 70,78 ****
{
tree type = TREE_TYPE (x);
tree ctr = EXEC_BINARY (RSHIFT_EXPR, type, mask, integer_one_node);
! tree rslt = convert (type, integer_one_node);
! while (integer_nonzerop (ctr))
{
rslt = EXEC_BINARY (MULT_EXPR, type, rslt, x);
rslt = EXEC_BINARY (BIT_AND_EXPR, type, rslt, mask);
--- 89,97 ----
{
tree type = TREE_TYPE (x);
tree ctr = EXEC_BINARY (RSHIFT_EXPR, type, mask, integer_one_node);
! tree rslt = build_int_cst_type (type, 1);
! while (nonzero_p (ctr))
{
rslt = EXEC_BINARY (MULT_EXPR, type, rslt, x);
rslt = EXEC_BINARY (BIT_AND_EXPR, type, rslt, mask);
*************** number_of_iterations_cond (tree type, tr
*** 180,203 ****
if (zero_p (step0))
{
if (mmax)
! assumption = fold (build (EQ_EXPR, boolean_type_node, base0, mmax));
else
assumption = boolean_false_node;
! if (integer_nonzerop (assumption))
goto zero_iter;
! base0 = fold (build (PLUS_EXPR, type, base0,
! convert (type, integer_one_node)));
}
else
{
if (mmin)
! assumption = fold (build (EQ_EXPR, boolean_type_node, base1, mmin));
else
assumption = boolean_false_node;
! if (integer_nonzerop (assumption))
goto zero_iter;
! base1 = fold (build (MINUS_EXPR, type, base1,
! convert (type, integer_one_node)));
}
noloop_assumptions = assumption;
code = LE_EXPR;
--- 199,222 ----
if (zero_p (step0))
{
if (mmax)
! assumption = fold (build2 (EQ_EXPR, boolean_type_node, base0, mmax));
else
assumption = boolean_false_node;
! if (nonzero_p (assumption))
goto zero_iter;
! base0 = fold (build2 (PLUS_EXPR, type, base0,
! build_int_cst_type (type, 1)));
}
else
{
if (mmin)
! assumption = fold (build2 (EQ_EXPR, boolean_type_node, base1, mmin));
else
assumption = boolean_false_node;
! if (nonzero_p (assumption))
goto zero_iter;
! base1 = fold (build2 (MINUS_EXPR, type, base1,
! build_int_cst_type (type, 1)));
}
noloop_assumptions = assumption;
code = LE_EXPR;
*************** number_of_iterations_cond (tree type, tr
*** 232,245 ****
step = EXEC_UNARY (NEGATE_EXPR, type, step1);
else
step = step0;
! delta = build (MINUS_EXPR, type, base1, base0);
! delta = fold (build (FLOOR_MOD_EXPR, type, delta, step));
may_xform = boolean_false_node;
if (TREE_CODE (delta) == INTEGER_CST)
{
tmp = EXEC_BINARY (MINUS_EXPR, type, step,
! convert (type, integer_one_node));
if (was_sharp
&& operand_equal_p (delta, tmp, 0))
{
--- 251,264 ----
step = EXEC_UNARY (NEGATE_EXPR, type, step1);
else
step = step0;
! delta = build2 (MINUS_EXPR, type, base1, base0);
! delta = fold (build2 (FLOOR_MOD_EXPR, type, delta, step));
may_xform = boolean_false_node;
if (TREE_CODE (delta) == INTEGER_CST)
{
tmp = EXEC_BINARY (MINUS_EXPR, type, step,
! build_int_cst_type (type, 1));
if (was_sharp
&& operand_equal_p (delta, tmp, 0))
{
*************** number_of_iterations_cond (tree type, tr
*** 262,268 ****
{
bound = EXEC_BINARY (PLUS_EXPR, type, mmin, step);
bound = EXEC_BINARY (MINUS_EXPR, type, bound, delta);
! may_xform = fold (build (LE_EXPR, boolean_type_node,
bound, base0));
}
}
--- 281,287 ----
{
bound = EXEC_BINARY (PLUS_EXPR, type, mmin, step);
bound = EXEC_BINARY (MINUS_EXPR, type, bound, delta);
! may_xform = fold (build2 (LE_EXPR, boolean_type_node,
bound, base0));
}
}
*************** number_of_iterations_cond (tree type, tr
*** 274,306 ****
{
bound = EXEC_BINARY (MINUS_EXPR, type, mmax, step);
bound = EXEC_BINARY (PLUS_EXPR, type, bound, delta);
! may_xform = fold (build (LE_EXPR, boolean_type_node,
base1, bound));
}
}
}
! if (!integer_zerop (may_xform))
{
/* We perform the transformation always provided that it is not
completely senseless. This is OK, as we would need this assumption
to determine the number of iterations anyway. */
! if (!integer_nonzerop (may_xform))
assumptions = may_xform;
if (zero_p (step0))
{
! base0 = build (PLUS_EXPR, type, base0, delta);
! base0 = fold (build (MINUS_EXPR, type, base0, step));
}
else
{
! base1 = build (MINUS_EXPR, type, base1, delta);
! base1 = fold (build (PLUS_EXPR, type, base1, step));
}
! assumption = fold (build (GT_EXPR, boolean_type_node, base0, base1));
! noloop_assumptions = fold (build (TRUTH_OR_EXPR, boolean_type_node,
noloop_assumptions, assumption));
code = NE_EXPR;
}
--- 293,325 ----
{
bound = EXEC_BINARY (MINUS_EXPR, type, mmax, step);
bound = EXEC_BINARY (PLUS_EXPR, type, bound, delta);
! may_xform = fold (build2 (LE_EXPR, boolean_type_node,
base1, bound));
}
}
}
! if (!zero_p (may_xform))
{
/* We perform the transformation always provided that it is not
completely senseless. This is OK, as we would need this assumption
to determine the number of iterations anyway. */
! if (!nonzero_p (may_xform))
assumptions = may_xform;
if (zero_p (step0))
{
! base0 = build2 (PLUS_EXPR, type, base0, delta);
! base0 = fold (build2 (MINUS_EXPR, type, base0, step));
}
else
{
! base1 = build2 (MINUS_EXPR, type, base1, delta);
! base1 = fold (build2 (PLUS_EXPR, type, base1, step));
}
! assumption = fold (build2 (GT_EXPR, boolean_type_node, base0, base1));
! noloop_assumptions = fold (build2 (TRUTH_OR_EXPR, boolean_type_node,
noloop_assumptions, assumption));
code = NE_EXPR;
}
*************** number_of_iterations_cond (tree type, tr
*** 316,354 ****
makes us able to do more involved computations of number of iterations
than in other cases. First transform the condition into shape
s * i <> c, with s positive. */
! base1 = fold (build (MINUS_EXPR, type, base1, base0));
base0 = NULL_TREE;
if (!zero_p (step1))
step0 = EXEC_UNARY (NEGATE_EXPR, type, step1);
step1 = NULL_TREE;
! if (!tree_expr_nonnegative_p (convert (signed_niter_type, step0)))
{
step0 = EXEC_UNARY (NEGATE_EXPR, type, step0);
base1 = fold (build1 (NEGATE_EXPR, type, base1));
}
! base1 = convert (niter_type, base1);
! step0 = convert (niter_type, step0);
/* Let nsd (s, size of mode) = d. If d does not divide c, the loop
is infinite. Otherwise, the number of iterations is
(inverse(s/d) * (c/d)) mod (size of mode/d). */
s = step0;
d = integer_one_node;
! bound = convert (niter_type, build_int_cst (NULL_TREE, -1));
while (1)
{
tmp = EXEC_BINARY (BIT_AND_EXPR, niter_type, s,
! convert (niter_type, integer_one_node));
! if (integer_nonzerop (tmp))
break;
s = EXEC_BINARY (RSHIFT_EXPR, niter_type, s,
! convert (niter_type, integer_one_node));
d = EXEC_BINARY (LSHIFT_EXPR, niter_type, d,
! convert (niter_type, integer_one_node));
bound = EXEC_BINARY (RSHIFT_EXPR, niter_type, bound,
! convert (niter_type, integer_one_node));
}
assumption = fold (build2 (FLOOR_MOD_EXPR, niter_type, base1, d));
--- 335,373 ----
makes us able to do more involved computations of number of iterations
than in other cases. First transform the condition into shape
s * i <> c, with s positive. */
! base1 = fold (build2 (MINUS_EXPR, type, base1, base0));
base0 = NULL_TREE;
if (!zero_p (step1))
step0 = EXEC_UNARY (NEGATE_EXPR, type, step1);
step1 = NULL_TREE;
! if (!tree_expr_nonnegative_p (fold_convert (signed_niter_type, step0)))
{
step0 = EXEC_UNARY (NEGATE_EXPR, type, step0);
base1 = fold (build1 (NEGATE_EXPR, type, base1));
}
! base1 = fold_convert (niter_type, base1);
! step0 = fold_convert (niter_type, step0);
/* Let nsd (s, size of mode) = d. If d does not divide c, the loop
is infinite. Otherwise, the number of iterations is
(inverse(s/d) * (c/d)) mod (size of mode/d). */
s = step0;
d = integer_one_node;
! bound = build_int_cst (niter_type, -1);
while (1)
{
tmp = EXEC_BINARY (BIT_AND_EXPR, niter_type, s,
! build_int_cst (niter_type, 1));
! if (nonzero_p (tmp))
break;
s = EXEC_BINARY (RSHIFT_EXPR, niter_type, s,
! build_int_cst (niter_type, 1));
d = EXEC_BINARY (LSHIFT_EXPR, niter_type, d,
! build_int_cst (niter_type, 1));
bound = EXEC_BINARY (RSHIFT_EXPR, niter_type, bound,
! build_int_cst (niter_type, 1));
}
assumption = fold (build2 (FLOOR_MOD_EXPR, niter_type, base1, d));
*************** number_of_iterations_cond (tree type, tr
*** 358,366 ****
assumptions = fold (build2 (TRUTH_AND_EXPR, boolean_type_node,
assumptions, assumption));
! tmp = fold (build (EXACT_DIV_EXPR, niter_type, base1, d));
! tmp = fold (build (MULT_EXPR, niter_type, tmp, inverse (s, bound)));
! niter->niter = fold (build (BIT_AND_EXPR, niter_type, tmp, bound));
}
else
{
--- 377,385 ----
assumptions = fold (build2 (TRUTH_AND_EXPR, boolean_type_node,
assumptions, assumption));
! tmp = fold (build2 (EXACT_DIV_EXPR, niter_type, base1, d));
! tmp = fold (build2 (MULT_EXPR, niter_type, tmp, inverse (s, bound)));
! niter->niter = fold (build2 (BIT_AND_EXPR, niter_type, tmp, bound));
}
else
{
*************** number_of_iterations_cond (tree type, tr
*** 375,392 ****
if (mmax)
{
bound = EXEC_BINARY (MINUS_EXPR, type, mmax, step0);
! assumption = fold (build (LE_EXPR, boolean_type_node,
! base1, bound));
! assumptions = fold (build (TRUTH_AND_EXPR, boolean_type_node,
! assumptions, assumption));
}
step = step0;
! tmp = fold (build (PLUS_EXPR, type, base1, step0));
! assumption = fold (build (GT_EXPR, boolean_type_node, base0, tmp));
! delta = fold (build (PLUS_EXPR, type, base1, step));
! delta = fold (build (MINUS_EXPR, type, delta, base0));
! delta = convert (niter_type, delta);
}
else
{
--- 394,411 ----
if (mmax)
{
bound = EXEC_BINARY (MINUS_EXPR, type, mmax, step0);
! assumption = fold (build2 (LE_EXPR, boolean_type_node,
! base1, bound));
! assumptions = fold (build2 (TRUTH_AND_EXPR, boolean_type_node,
! assumptions, assumption));
}
step = step0;
! tmp = fold (build2 (PLUS_EXPR, type, base1, step0));
! assumption = fold (build2 (GT_EXPR, boolean_type_node, base0, tmp));
! delta = fold (build2 (PLUS_EXPR, type, base1, step));
! delta = fold (build2 (MINUS_EXPR, type, delta, base0));
! delta = fold_convert (niter_type, delta);
}
else
{
*************** number_of_iterations_cond (tree type, tr
*** 396,417 ****
if (mmin)
{
bound = EXEC_BINARY (MINUS_EXPR, type, mmin, step1);
! assumption = fold (build (LE_EXPR, boolean_type_node,
bound, base0));
! assumptions = fold (build (TRUTH_AND_EXPR, boolean_type_node,
assumptions, assumption));
}
step = fold (build1 (NEGATE_EXPR, type, step1));
! tmp = fold (build (PLUS_EXPR, type, base0, step1));
! assumption = fold (build (GT_EXPR, boolean_type_node, tmp, base1));
! delta = fold (build (MINUS_EXPR, type, base0, step));
! delta = fold (build (MINUS_EXPR, type, base1, delta));
! delta = convert (niter_type, delta);
}
! noloop_assumptions = fold (build (TRUTH_OR_EXPR, boolean_type_node,
noloop_assumptions, assumption));
! delta = fold (build (FLOOR_DIV_EXPR, niter_type, delta,
! convert (niter_type, step)));
niter->niter = delta;
}
--- 415,436 ----
if (mmin)
{
bound = EXEC_BINARY (MINUS_EXPR, type, mmin, step1);
! assumption = fold (build2 (LE_EXPR, boolean_type_node,
bound, base0));
! assumptions = fold (build2 (TRUTH_AND_EXPR, boolean_type_node,
assumptions, assumption));
}
step = fold (build1 (NEGATE_EXPR, type, step1));
! tmp = fold (build2 (PLUS_EXPR, type, base0, step1));
! assumption = fold (build2 (GT_EXPR, boolean_type_node, tmp, base1));
! delta = fold (build2 (MINUS_EXPR, type, base0, step));
! delta = fold (build2 (MINUS_EXPR, type, base1, delta));
! delta = fold_convert (niter_type, delta);
}
! noloop_assumptions = fold (build2 (TRUTH_OR_EXPR, boolean_type_node,
noloop_assumptions, assumption));
! delta = fold (build2 (FLOOR_DIV_EXPR, niter_type, delta,
! fold_convert (niter_type, step)));
niter->niter = delta;
}
*************** number_of_iterations_cond (tree type, tr
*** 422,428 ****
zero_iter:
niter->assumptions = boolean_true_node;
niter->may_be_zero = boolean_true_node;
! niter->niter = convert (type, integer_zero_node);
return;
}
--- 441,447 ----
zero_iter:
niter->assumptions = boolean_true_node;
niter->may_be_zero = boolean_true_node;
! niter->niter = build_int_cst_type (type, 0);
return;
}
*************** simplify_using_outer_evolutions (struct
*** 466,474 ****
if (changed)
{
if (code == COND_EXPR)
! expr = build (code, boolean_type_node, e0, e1, e2);
else
! expr = build (code, boolean_type_node, e0, e1);
expr = fold (expr);
}
--- 485,493 ----
if (changed)
{
if (code == COND_EXPR)
! expr = build3 (code, boolean_type_node, e0, e1, e2);
else
! expr = build2 (code, boolean_type_node, e0, e1);
expr = fold (expr);
}
*************** tree_simplify_using_condition (tree cond
*** 521,529 ****
if (changed)
{
if (code == COND_EXPR)
! expr = build (code, boolean_type_node, e0, e1, e2);
else
! expr = build (code, boolean_type_node, e0, e1);
expr = fold (expr);
}
--- 540,548 ----
if (changed)
{
if (code == COND_EXPR)
! expr = build3 (code, boolean_type_node, e0, e1, e2);
else
! expr = build2 (code, boolean_type_node, e0, e1);
expr = fold (expr);
}
*************** tree_simplify_using_condition (tree cond
*** 532,546 ****
/* Check whether COND ==> EXPR. */
notcond = invert_truthvalue (cond);
! e = fold (build (TRUTH_OR_EXPR, boolean_type_node,
notcond, expr));
! if (integer_nonzerop (e))
return e;
/* Check whether COND ==> not EXPR. */
! e = fold (build (TRUTH_AND_EXPR, boolean_type_node,
cond, expr));
! if (integer_zerop (e))
return e;
return expr;
--- 551,565 ----
/* Check whether COND ==> EXPR. */
notcond = invert_truthvalue (cond);
! e = fold (build2 (TRUTH_OR_EXPR, boolean_type_node,
notcond, expr));
! if (nonzero_p (e))
return e;
/* Check whether COND ==> not EXPR. */
! e = fold (build2 (TRUTH_AND_EXPR, boolean_type_node,
cond, expr));
! if (zero_p (e))
return e;
return expr;
*************** simplify_using_initial_conditions (struc
*** 579,585 ****
exp = tree_simplify_using_condition (cond, expr);
if (exp != expr)
! *conds_used = fold (build (TRUTH_AND_EXPR,
boolean_type_node,
*conds_used,
cond));
--- 598,604 ----
exp = tree_simplify_using_condition (cond, expr);
if (exp != expr)
! *conds_used = fold (build2 (TRUTH_AND_EXPR,
boolean_type_node,
*conds_used,
cond));
*************** loop_niter_by_eval (struct loop *loop, e
*** 861,868 ****
for (j = 0; j < 2; j++)
aval[j] = get_val_for (op[j], val[j]);
! acnd = fold (build (cmp, boolean_type_node, aval[0], aval[1]));
! if (integer_zerop (acnd))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
--- 880,887 ----
for (j = 0; j < 2; j++)
aval[j] = get_val_for (op[j], val[j]);
! acnd = fold (build2 (cmp, boolean_type_node, aval[0], aval[1]));
! if (zero_p (acnd))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
*************** find_loop_niter_by_eval (struct loop *lo
*** 906,912 ****
continue;
if (niter
! && !integer_nonzerop (fold (build (LT_EXPR, boolean_type_node,
aniter, niter))))
continue;
--- 925,931 ----
continue;
if (niter
! && !nonzero_p (fold (build2 (LT_EXPR, boolean_type_node,
aniter, niter))))
continue;
*************** estimate_numbers_of_iterations_loop (str
*** 980,990 ****
niter = niter_desc.niter;
type = TREE_TYPE (niter);
! if (!integer_zerop (niter_desc.may_be_zero)
! && !integer_nonzerop (niter_desc.may_be_zero))
! niter = build (COND_EXPR, type, niter_desc.may_be_zero,
! convert (type, integer_zero_node),
! niter);
record_estimate (loop, niter,
niter_desc.additional_info,
last_stmt (exits[i]->src));
--- 999,1009 ----
niter = niter_desc.niter;
type = TREE_TYPE (niter);
! if (!zero_p (niter_desc.may_be_zero)
! && !nonzero_p (niter_desc.may_be_zero))
! niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
! build_int_cst_type (type, 0),
! niter);
record_estimate (loop, niter,
niter_desc.additional_info,
last_stmt (exits[i]->src));
*************** compare_trees (tree a, tree b)
*** 1025,1038 ****
else
type = typeb;
! a = convert (type, a);
! b = convert (type, b);
! if (integer_nonzerop (fold (build (EQ_EXPR, boolean_type_node, a, b))))
return 0;
! if (integer_nonzerop (fold (build (LT_EXPR, boolean_type_node, a, b))))
return 1;
! if (integer_nonzerop (fold (build (GT_EXPR, boolean_type_node, a, b))))
return -1;
return 2;
--- 1044,1057 ----
else
type = typeb;
! a = fold_convert (type, a);
! b = fold_convert (type, b);
! if (nonzero_p (fold (build2 (EQ_EXPR, boolean_type_node, a, b))))
return 0;
! if (nonzero_p (fold (build2 (LT_EXPR, boolean_type_node, a, b))))
return 1;
! if (nonzero_p (fold (build2 (GT_EXPR, boolean_type_node, a, b))))
return -1;
return 2;
*************** upper_bound_in_type (tree outer, tree in
*** 1080,1088 ****
}
}
! return convert (outer,
! convert (inner,
! build_int_cst_wide (NULL_TREE, lo, hi)));
}
/* Returns the smallest value obtainable by casting something in INNER type to
--- 1099,1106 ----
}
}
! return fold_convert (outer,
! build_int_cst_wide (inner, lo, hi));
}
/* Returns the smallest value obtainable by casting something in INNER type to
*************** lower_bound_in_type (tree outer, tree in
*** 1107,1115 ****
lo = 0;
}
! return convert (outer,
! convert (inner,
! build_int_cst_wide (NULL_TREE, lo, hi)));
}
/* Returns true if statement S1 dominates statement S2. */
--- 1125,1132 ----
lo = 0;
}
! return fold_convert (outer,
! build_int_cst_wide (inner, lo, hi));
}
/* Returns true if statement S1 dominates statement S2. */
*************** can_count_iv_in_wider_type_bound (tree t
*** 1168,1177 ****
tree valid_niter, extreme, unsigned_type, delta, bound_type;
tree cond;
! b = convert (type, base);
! bplusstep = convert (type,
! fold (build (PLUS_EXPR, inner_type, base, step)));
! new_step = fold (build (MINUS_EXPR, type, bplusstep, b));
if (TREE_CODE (new_step) != INTEGER_CST)
return NULL_TREE;
--- 1185,1194 ----
tree valid_niter, extreme, unsigned_type, delta, bound_type;
tree cond;
! b = fold_convert (type, base);
! bplusstep = fold_convert (type,
! fold (build2 (PLUS_EXPR, inner_type, base, step)));
! new_step = fold (build2 (MINUS_EXPR, type, bplusstep, b));
if (TREE_CODE (new_step) != INTEGER_CST)
return NULL_TREE;
*************** can_count_iv_in_wider_type_bound (tree t
*** 1179,1192 ****
{
case -1:
extreme = upper_bound_in_type (type, inner_type);
! delta = fold (build (MINUS_EXPR, type, extreme, b));
new_step_abs = new_step;
break;
case 1:
extreme = lower_bound_in_type (type, inner_type);
! new_step_abs = fold (build (NEGATE_EXPR, type, new_step));
! delta = fold (build (MINUS_EXPR, type, b, extreme));
break;
case 0:
--- 1196,1209 ----
{
case -1:
extreme = upper_bound_in_type (type, inner_type);
! delta = fold (build2 (MINUS_EXPR, type, extreme, b));
new_step_abs = new_step;
break;
case 1:
extreme = lower_bound_in_type (type, inner_type);
! new_step_abs = fold (build1 (NEGATE_EXPR, type, new_step));
! delta = fold (build2 (MINUS_EXPR, type, b, extreme));
break;
case 0:
*************** can_count_iv_in_wider_type_bound (tree t
*** 1197,1236 ****
}
unsigned_type = unsigned_type_for (type);
! delta = convert (unsigned_type, delta);
! new_step_abs = convert (unsigned_type, new_step_abs);
! valid_niter = fold (build (FLOOR_DIV_EXPR, unsigned_type,
delta, new_step_abs));
bound_type = TREE_TYPE (bound);
if (TYPE_PRECISION (type) > TYPE_PRECISION (bound_type))
! bound = convert (unsigned_type, bound);
else
! valid_niter = convert (bound_type, valid_niter);
if (at_stmt && stmt_dominates_stmt_p (of, at_stmt))
{
/* After the statement OF we know that anything is executed at most
BOUND times. */
! cond = build (GE_EXPR, boolean_type_node, valid_niter, bound);
}
else
{
/* Before the statement OF we know that anything is executed at most
BOUND + 1 times. */
! cond = build (GT_EXPR, boolean_type_node, valid_niter, bound);
}
cond = fold (cond);
! if (integer_nonzerop (cond))
return new_step;
/* Try taking additional conditions into account. */
! cond = build (TRUTH_OR_EXPR, boolean_type_node,
invert_truthvalue (additional),
cond);
cond = fold (cond);
! if (integer_nonzerop (cond))
return new_step;
return NULL_TREE;
--- 1214,1253 ----
}
unsigned_type = unsigned_type_for (type);
! delta = fold_convert (unsigned_type, delta);
! new_step_abs = fold_convert (unsigned_type, new_step_abs);
! valid_niter = fold (build2 (FLOOR_DIV_EXPR, unsigned_type,
delta, new_step_abs));
bound_type = TREE_TYPE (bound);
if (TYPE_PRECISION (type) > TYPE_PRECISION (bound_type))
! bound = fold_convert (unsigned_type, bound);
else
! valid_niter = fold_convert (bound_type, valid_niter);
if (at_stmt && stmt_dominates_stmt_p (of, at_stmt))
{
/* After the statement OF we know that anything is executed at most
BOUND times. */
! cond = build2 (GE_EXPR, boolean_type_node, valid_niter, bound);
}
else
{
/* Before the statement OF we know that anything is executed at most
BOUND + 1 times. */
! cond = build2 (GT_EXPR, boolean_type_node, valid_niter, bound);
}
cond = fold (cond);
! if (nonzero_p (cond))
return new_step;
/* Try taking additional conditions into account. */
! cond = build2 (TRUTH_OR_EXPR, boolean_type_node,
invert_truthvalue (additional),
cond);
cond = fold (cond);
! if (nonzero_p (cond))
return new_step;
return NULL_TREE;
More information about the Gcc-patches
mailing list