diff options
| -rw-r--r-- | gcc/ChangeLog | 20 | ||||
| -rw-r--r-- | gcc/testsuite/ChangeLog | 4 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/loop-15.c | 27 | ||||
| -rw-r--r-- | gcc/tree-chrec.c | 18 | ||||
| -rw-r--r-- | gcc/tree-scalar-evolution.c | 76 | ||||
| -rw-r--r-- | gcc/tree-scalar-evolution.h | 14 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-ivopts.c | 33 | ||||
| -rw-r--r-- | gcc/tree-ssa-loop-niter.c | 272 |
8 files changed, 279 insertions, 185 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index c8b616af0c2..f7834cb640a 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,23 @@ +2005-01-06 Zdenek Dvorak <dvorakz@suse.cz> + + PR tree-optimization/18527 + * tree-ssa-loop-niter.c (number_of_iterations_cond, + number_of_iterations_special, number_of_iterations_exit): + Move base and step of an iv to a single structure. Add + no_overflow flag, and use it in # of iterations analysis. + * tree-scalar-evolution.c (analyze_scalar_evolution_in_loop): Add + folded_casts argument. + (simple_iv): Pass base and step in a structure. Set no_overflow + flag. + (scev_const_prop): Add argument to analyze_scalar_evolution_in_loop. + Evaluate expensiveness of computing # of iterations instead of + the final expression. + * tree-scalar-evolution.h (affine_iv): New structure. + (simple_iv): Declaration changed. + * tree-chrec.c (chrec_apply): Handle chrecs containing symbols. + * tree-ssa-loop-ivopts.c (determine_biv_step, find_givs_in_stmt_scev, + find_givs_in_stmt): Changed due to simple_iv change. + 2005-01-06 Jeff Law <law@redhat.com> PR ada/24994 diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index a1aa997e2c0..ca893730e66 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2005-01-06 Zdenek Dvorak <dvorakz@suse.cz> + + * gcc.dg/tree-ssa/loop-15.c: New test. + 2005-01-05 Jerry DeLisle <jvdelisle@gcc.gnu.org> PR fortran/25598 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-15.c b/gcc/testsuite/gcc.dg/tree-ssa/loop-15.c new file mode 100644 index 00000000000..44cd10103fa --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-15.c @@ -0,0 +1,27 @@ +/* A test for # of iterations analysis (signed counter cannot wrap) and final + value replacement. */ + +/* { dg-options "-O2 -fdump-tree-vars" } */ + +int foo(void); + +int bla(void) +{ + int i, n = foo (), j; + + j = 0; + /* The loop should be removed completely. */ + for (i = 1; i <= n; i++) + j += n; + + /* Should be replaced with return n * n; */ + return j; +} + +/* Since the loop is removed, there should be no addition. */ +/* { dg-final { scan-tree-dump-times "\\+" 0 "vars" } } */ +/* { dg-final { scan-tree-dump-times "n \\* n" 1 "vars" } } */ + +/* The if from the loop header copying remains in the code. */ +/* { dg-final { scan-tree-dump-times "if " 1 "vars" } } */ +/* { dg-final { cleanup-tree-dump "vars" } } */ diff --git a/gcc/tree-chrec.c b/gcc/tree-chrec.c index 0bf1d384592..30915d280ec 100644 --- a/gcc/tree-chrec.c +++ b/gcc/tree-chrec.c @@ -533,10 +533,9 @@ chrec_apply (unsigned var, /* When the symbols are defined in an outer loop, it is possible to symbolically compute the apply, since the symbols are constants with respect to the varying loop. */ - || chrec_contains_symbols_defined_in_loop (chrec, var) - || chrec_contains_symbols (x)) + || chrec_contains_symbols_defined_in_loop (chrec, var)) return chrec_dont_know; - + if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "(chrec_apply \n"); @@ -546,14 +545,10 @@ chrec_apply (unsigned var, if (evolution_function_is_affine_p (chrec)) { /* "{a, +, b} (x)" -> "a + b*x". */ - if (TREE_CODE (CHREC_LEFT (chrec)) == INTEGER_CST - && integer_zerop (CHREC_LEFT (chrec))) - res = chrec_fold_multiply (type, CHREC_RIGHT (chrec), x); - - else - res = chrec_fold_plus (type, CHREC_LEFT (chrec), - chrec_fold_multiply (type, - CHREC_RIGHT (chrec), x)); + x = chrec_convert (type, x, NULL_TREE); + res = chrec_fold_multiply (type, CHREC_RIGHT (chrec), x); + if (!integer_zerop (CHREC_LEFT (chrec))) + res = chrec_fold_plus (type, CHREC_LEFT (chrec), res); } else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) @@ -563,7 +558,6 @@ chrec_apply (unsigned var, && tree_int_cst_sgn (x) == 1) /* testsuite/.../ssa-chrec-38.c. */ res = chrec_evaluate (var, chrec, x, 0); - else res = chrec_dont_know; diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index 2b0d817d8a7..3075839f3e7 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -1831,19 +1831,28 @@ analyze_scalar_evolution (struct loop *loop, tree var) /* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to WRTO_LOOP (which should be a superloop of both USE_LOOP and definition - of VERSION). */ + of VERSION). + + FOLDED_CASTS is set to true if resolve_mixers used + chrec_convert_aggressive (TODO -- not really, we are way too conservative + at the moment in order to keep things simple). */ static tree analyze_scalar_evolution_in_loop (struct loop *wrto_loop, struct loop *use_loop, - tree version) + tree version, bool *folded_casts) { bool val = false; - tree ev = version; + tree ev = version, tmp; + if (folded_casts) + *folded_casts = false; while (1) { - ev = analyze_scalar_evolution (use_loop, ev); - ev = resolve_mixers (use_loop, ev); + tmp = analyze_scalar_evolution (use_loop, ev); + ev = resolve_mixers (use_loop, tmp); + + if (folded_casts && tmp != ev) + *folded_casts = true; if (use_loop == wrto_loop) return ev; @@ -2561,33 +2570,38 @@ scev_reset (void) } /* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns - its BASE and STEP if possible. If ALLOW_NONCONSTANT_STEP is true, we - want STEP to be invariant in LOOP. Otherwise we require it to be an - integer constant. */ + its base and step in IV if possible. If ALLOW_NONCONSTANT_STEP is true, we + want step to be invariant in LOOP. Otherwise we require it to be an + integer constant. IV->no_overflow is set to true if we are sure the iv cannot + overflow (e.g. because it is computed in signed arithmetics). */ bool -simple_iv (struct loop *loop, tree stmt, tree op, tree *base, tree *step, +simple_iv (struct loop *loop, tree stmt, tree op, affine_iv *iv, bool allow_nonconstant_step) { basic_block bb = bb_for_stmt (stmt); tree type, ev; + bool folded_casts; - *base = NULL_TREE; - *step = NULL_TREE; + iv->base = NULL_TREE; + iv->step = NULL_TREE; + iv->no_overflow = false; type = TREE_TYPE (op); if (TREE_CODE (type) != INTEGER_TYPE && TREE_CODE (type) != POINTER_TYPE) return false; - ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op); + ev = analyze_scalar_evolution_in_loop (loop, bb->loop_father, op, + &folded_casts); if (chrec_contains_undetermined (ev)) return false; if (tree_does_not_contain_chrecs (ev) && !chrec_contains_symbols_defined_in_loop (ev, loop->num)) { - *base = ev; + iv->base = ev; + iv->no_overflow = true; return true; } @@ -2595,21 +2609,24 @@ simple_iv (struct loop *loop, tree stmt, tree op, tree *base, tree *step, || CHREC_VARIABLE (ev) != (unsigned) loop->num) return false; - *step = CHREC_RIGHT (ev); + iv->step = CHREC_RIGHT (ev); if (allow_nonconstant_step) { - if (tree_contains_chrecs (*step, NULL) - || chrec_contains_symbols_defined_in_loop (*step, loop->num)) + if (tree_contains_chrecs (iv->step, NULL) + || chrec_contains_symbols_defined_in_loop (iv->step, loop->num)) return false; } - else if (TREE_CODE (*step) != INTEGER_CST) + else if (TREE_CODE (iv->step) != INTEGER_CST) return false; - *base = CHREC_LEFT (ev); - if (tree_contains_chrecs (*base, NULL) - || chrec_contains_symbols_defined_in_loop (*base, loop->num)) + iv->base = CHREC_LEFT (ev); + if (tree_contains_chrecs (iv->base, NULL) + || chrec_contains_symbols_defined_in_loop (iv->base, loop->num)) return false; + iv->no_overflow = (!folded_casts + && !flag_wrapv + && !TYPE_UNSIGNED (type)); return true; } @@ -2722,7 +2739,7 @@ scev_const_prop (void) for (i = current_loops->num - 1; i > 0; i--) { edge exit; - tree def, rslt, ass; + tree def, rslt, ass, niter; block_stmt_iterator bsi; loop = current_loops->parray[i]; @@ -2732,8 +2749,14 @@ scev_const_prop (void) /* If we do not know exact number of iterations of the loop, we cannot replace the final value. */ exit = loop->single_exit; - if (!exit - || number_of_iterations_in_loop (loop) == chrec_dont_know) + if (!exit) + continue; + + niter = number_of_iterations_in_loop (loop); + if (niter == chrec_dont_know + /* If computing the number of iterations is expensive, it may be + better not to introduce computations involving it. */ + || expression_expensive_p (niter)) continue; /* Ensure that it is possible to insert new statements somewhere. */ @@ -2756,17 +2779,12 @@ scev_const_prop (void) && !INTEGRAL_TYPE_P (TREE_TYPE (def))) continue; - def = analyze_scalar_evolution_in_loop (ex_loop, loop, def); + def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL); def = compute_overall_effect_of_inner_loop (ex_loop, def); if (!tree_does_not_contain_chrecs (def) || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)) continue; - /* If computing the expression is expensive, let it remain in the - loop. */ - if (expression_expensive_p (def)) - continue; - /* Eliminate the phi node and replace it by a computation outside the loop. */ def = unshare_expr (def); diff --git a/gcc/tree-scalar-evolution.h b/gcc/tree-scalar-evolution.h index 60878b1d97e..0fecaee2390 100644 --- a/gcc/tree-scalar-evolution.h +++ b/gcc/tree-scalar-evolution.h @@ -32,7 +32,19 @@ extern tree analyze_scalar_evolution (struct loop *, tree); extern tree instantiate_parameters (struct loop *, tree); extern void gather_stats_on_scev_database (void); extern void scev_analysis (void); -extern bool simple_iv (struct loop *, tree, tree, tree *, tree *, bool); void scev_const_prop (void); +/* Affine iv. */ + +typedef struct +{ + /* Iv = BASE + STEP * i. */ + tree base, step; + + /* True if this iv does not overflow. */ + bool no_overflow; +} affine_iv; + +extern bool simple_iv (struct loop *, tree, tree, affine_iv *, bool); + #endif /* GCC_TREE_SCALAR_EVOLUTION_H */ diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c index 1e6d17ed6a0..8e1c53ad174 100644 --- a/gcc/tree-ssa-loop-ivopts.c +++ b/gcc/tree-ssa-loop-ivopts.c @@ -881,18 +881,16 @@ static tree determine_biv_step (tree phi) { struct loop *loop = bb_for_stmt (phi)->loop_father; - tree name = PHI_RESULT (phi), base, step; + tree name = PHI_RESULT (phi); + affine_iv iv; if (!is_gimple_reg (name)) return NULL_TREE; - if (!simple_iv (loop, phi, name, &base, &step, true)) + if (!simple_iv (loop, phi, name, &iv, true)) return NULL_TREE; - if (zero_p (step)) - return NULL_TREE; - - return step; + return (zero_p (iv.step) ? NULL_TREE : iv.step); } /* Returns true if EXP is a ssa name that occurs in an abnormal phi node. */ @@ -1044,17 +1042,16 @@ mark_bivs (struct ivopts_data *data) } /* Checks whether STMT defines a linear induction variable and stores its - parameters to BASE and STEP. */ + parameters to IV. */ static bool -find_givs_in_stmt_scev (struct ivopts_data *data, tree stmt, - tree *base, tree *step) +find_givs_in_stmt_scev (struct ivopts_data *data, tree stmt, affine_iv *iv) { tree lhs; struct loop *loop = data->current_loop; - *base = NULL_TREE; - *step = NULL_TREE; + iv->base = NULL_TREE; + iv->step = NULL_TREE; if (TREE_CODE (stmt) != MODIFY_EXPR) return false; @@ -1063,12 +1060,12 @@ find_givs_in_stmt_scev (struct ivopts_data *data, tree stmt, if (TREE_CODE (lhs) != SSA_NAME) return false; - if (!simple_iv (loop, stmt, TREE_OPERAND (stmt, 1), base, step, true)) + if (!simple_iv (loop, stmt, TREE_OPERAND (stmt, 1), iv, true)) return false; - *base = expand_simple_operations (*base); + iv->base = expand_simple_operations (iv->base); - if (contains_abnormal_ssa_name_p (*base) - || contains_abnormal_ssa_name_p (*step)) + if (contains_abnormal_ssa_name_p (iv->base) + || contains_abnormal_ssa_name_p (iv->step)) return false; return true; @@ -1079,12 +1076,12 @@ find_givs_in_stmt_scev (struct ivopts_data *data, tree stmt, static void find_givs_in_stmt (struct ivopts_data *data, tree stmt) { - tree base, step; + affine_iv iv; - if (!find_givs_in_stmt_scev (data, stmt, &base, &step)) + if (!find_givs_in_stmt_scev (data, stmt, &iv)) return; - set_iv (data, TREE_OPERAND (stmt, 0), base, step); + set_iv (data, TREE_OPERAND (stmt, 0), iv.base, iv.step); } /* Finds general ivs in basic block BB. */ diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index 796991bcf50..bd3667b302e 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -129,10 +129,9 @@ inverse (tree x, tree mask) /* Determine the number of iterations according to condition (for staying inside loop) which compares two induction variables using comparison operator CODE. The induction variable on left side of the comparison - has base BASE0 and step STEP0. the right-hand side one has base - BASE1 and step STEP1. Both induction variables must have type TYPE, - which must be an integer or pointer type. STEP0 and STEP1 must be - constants (or NULL_TREE, which is interpreted as constant zero). + is IV0, the right-hand side is IV1. Both induction variables must have + type TYPE, which must be an integer or pointer type. The steps of the + ivs must be constants (or NULL_TREE, which is interpreted as constant zero). The results (number of iterations and assumptions as described in comments at struct tree_niter_desc in tree-flow.h) are stored to NITER. @@ -140,13 +139,12 @@ inverse (tree x, tree mask) this structure is unchanged. */ static void -number_of_iterations_cond (tree type, tree base0, tree step0, - enum tree_code code, tree base1, tree step1, - struct tree_niter_desc *niter) +number_of_iterations_cond (tree type, affine_iv *iv0, enum tree_code code, + affine_iv *iv1, struct tree_niter_desc *niter) { tree step, delta, mmin, mmax; tree may_xform, bound, s, d, tmp; - bool was_sharp = false; + bool was_sharp = false, never_infinite; tree assumption; tree assumptions = boolean_true_node; tree noloop_assumptions = boolean_false_node; @@ -165,36 +163,47 @@ number_of_iterations_cond (tree type, tree base0, tree step0, if (code == GE_EXPR || code == GT_EXPR) { - SWAP (base0, base1); - SWAP (step0, step1); + SWAP (iv0, iv1); code = swap_tree_comparison (code); } + /* If the control induction variable does not overflow, the loop obviously + cannot be infinite. */ + if (!zero_p (iv0->step) && iv0->no_overflow) + never_infinite = true; + else if (!zero_p (iv1->step) && iv1->no_overflow) + never_infinite = true; + else + never_infinite = false; + /* We can handle the case when neither of the sides of the comparison is invariant, provided that the test is NE_EXPR. This rarely occurs in practice, but it is simple enough to manage. */ - if (!zero_p (step0) && !zero_p (step1)) + if (!zero_p (iv0->step) && !zero_p (iv1->step)) { if (code != NE_EXPR) return; - step0 = fold_binary_to_constant (MINUS_EXPR, type, step0, step1); - step1 = NULL_TREE; + iv0->step = fold_binary_to_constant (MINUS_EXPR, type, + iv0->step, iv1->step); + iv0->no_overflow = false; + iv1->step = NULL_TREE; + iv1->no_overflow = true; } /* If the result is a constant, the loop is weird. More precise handling would be possible, but the situation is not common enough to waste time on it. */ - if (zero_p (step0) && zero_p (step1)) + if (zero_p (iv0->step) && zero_p (iv1->step)) return; /* Ignore loops of while (i-- < 10) type. */ if (code != NE_EXPR) { - if (step0 && tree_int_cst_sign_bit (step0)) + if (iv0->step && tree_int_cst_sign_bit (iv0->step)) return; - if (!zero_p (step1) && !tree_int_cst_sign_bit (step1)) + if (!zero_p (iv1->step) && !tree_int_cst_sign_bit (iv1->step)) return; } @@ -220,27 +229,29 @@ number_of_iterations_cond (tree type, tree base0, tree step0, care of <, as NE is more similar to it, but the problem is that here the transformation would be more difficult due to possibly infinite loops. */ - if (zero_p (step0)) + if (zero_p (iv0->step)) { if (mmax) - assumption = fold_build2 (EQ_EXPR, boolean_type_node, base0, mmax); + assumption = fold_build2 (EQ_EXPR, boolean_type_node, + iv0->base, 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)); + iv0->base = fold_build2 (PLUS_EXPR, type, iv0->base, + build_int_cst_type (type, 1)); } else { if (mmin) - assumption = fold_build2 (EQ_EXPR, boolean_type_node, base1, mmin); + assumption = fold_build2 (EQ_EXPR, boolean_type_node, + iv1->base, 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)); + iv1->base = fold_build2 (MINUS_EXPR, type, iv1->base, + build_int_cst_type (type, 1)); } noloop_assumptions = assumption; code = LE_EXPR; @@ -253,13 +264,13 @@ number_of_iterations_cond (tree type, tree base0, tree step0, /* Take care of trivially infinite loops. */ if (code != NE_EXPR) { - if (zero_p (step0) + if (zero_p (iv0->step) && mmin - && operand_equal_p (base0, mmin, 0)) + && operand_equal_p (iv0->base, mmin, 0)) return; - if (zero_p (step1) + if (zero_p (iv1->step) && mmax - && operand_equal_p (base1, mmax, 0)) + && operand_equal_p (iv1->base, mmax, 0)) return; } @@ -271,11 +282,11 @@ number_of_iterations_cond (tree type, tree base0, tree step0, there is not an overflow. */ if (code != NE_EXPR) { - if (zero_p (step0)) - step = fold_unary_to_constant (NEGATE_EXPR, type, step1); + if (zero_p (iv0->step)) + step = fold_unary_to_constant (NEGATE_EXPR, type, iv1->step); else - step = step0; - delta = fold_build2 (MINUS_EXPR, type, base1, base0); + step = iv0->step; + delta = fold_build2 (MINUS_EXPR, type, iv1->base, iv0->base); delta = fold_build2 (FLOOR_MOD_EXPR, type, delta, step); may_xform = boolean_false_node; @@ -297,9 +308,9 @@ number_of_iterations_cond (tree type, tree base0, tree step0, worth the troubles. */ may_xform = boolean_true_node; } - else if (zero_p (step0)) + else if (zero_p (iv0->step)) { - if (!mmin) + if (!mmin || iv1->no_overflow) may_xform = boolean_true_node; else { @@ -308,12 +319,12 @@ number_of_iterations_cond (tree type, tree base0, tree step0, bound = fold_binary_to_constant (MINUS_EXPR, type, bound, delta); may_xform = fold_build2 (LE_EXPR, boolean_type_node, - bound, base0); + bound, iv0->base); } } else { - if (!mmax) + if (!mmax || iv0->no_overflow) may_xform = boolean_true_node; else { @@ -322,7 +333,7 @@ number_of_iterations_cond (tree type, tree base0, tree step0, bound = fold_binary_to_constant (PLUS_EXPR, type, bound, delta); may_xform = fold_build2 (LE_EXPR, boolean_type_node, - base1, bound); + iv1->base, bound); } } } @@ -335,18 +346,19 @@ number_of_iterations_cond (tree type, tree base0, tree step0, if (!nonzero_p (may_xform)) assumptions = may_xform; - if (zero_p (step0)) + if (zero_p (iv0->step)) { - base0 = fold_build2 (PLUS_EXPR, type, base0, delta); - base0 = fold_build2 (MINUS_EXPR, type, base0, step); + iv0->base = fold_build2 (PLUS_EXPR, type, iv0->base, delta); + iv0->base = fold_build2 (MINUS_EXPR, type, iv0->base, step); } else { - base1 = fold_build2 (MINUS_EXPR, type, base1, delta); - base1 = fold_build2 (PLUS_EXPR, type, base1, step); + iv1->base = fold_build2 (MINUS_EXPR, type, iv1->base, delta); + iv1->base = fold_build2 (PLUS_EXPR, type, iv1->base, step); } - assumption = fold_build2 (GT_EXPR, boolean_type_node, base0, base1); + assumption = fold_build2 (GT_EXPR, boolean_type_node, + iv0->base, iv1->base); noloop_assumptions = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, noloop_assumptions, assumption); code = NE_EXPR; @@ -363,46 +375,51 @@ number_of_iterations_cond (tree type, tree base0, tree step0, 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 = fold_unary_to_constant (NEGATE_EXPR, type, step1); - step1 = NULL_TREE; - if (tree_int_cst_sign_bit (fold_convert (signed_niter_type, step0))) + iv1->base = fold_build2 (MINUS_EXPR, type, iv1->base, iv0->base); + iv0->base = NULL_TREE; + if (!zero_p (iv1->step)) + iv0->step = fold_unary_to_constant (NEGATE_EXPR, type, iv1->step); + iv1->step = NULL_TREE; + if (tree_int_cst_sign_bit (fold_convert (signed_niter_type, iv0->step))) { - step0 = fold_unary_to_constant (NEGATE_EXPR, type, step0); - base1 = fold_build1 (NEGATE_EXPR, type, base1); + iv0->step = fold_unary_to_constant (NEGATE_EXPR, type, iv0->step); + iv1->base = fold_build1 (NEGATE_EXPR, type, iv1->base); } - base1 = fold_convert (niter_type, base1); - step0 = fold_convert (niter_type, step0); + iv1->base = fold_convert (niter_type, iv1->base); + iv0->step = fold_convert (niter_type, iv0->step); /* Let nsd (step, 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). */ - bits = num_ending_zeros (step0); + bits = num_ending_zeros (iv0->step); d = fold_binary_to_constant (LSHIFT_EXPR, niter_type, build_int_cst_type (niter_type, 1), bits); - s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, step0, bits); + s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, iv0->step, bits); bound = build_low_bits_mask (niter_type, (TYPE_PRECISION (niter_type) - tree_low_cst (bits, 1))); - assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, base1, d); - assumption = fold_build2 (EQ_EXPR, boolean_type_node, - assumption, - build_int_cst (niter_type, 0)); - assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, - assumptions, assumption); + if (!never_infinite) + { + /* If we cannot assume that the loop is not infinite, record the + assumptions for divisibility of c. */ + assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, iv1->base, d); + assumption = fold_build2 (EQ_EXPR, boolean_type_node, + assumption, + build_int_cst (niter_type, 0)); + assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, + assumptions, assumption); + } - tmp = fold_build2 (EXACT_DIV_EXPR, niter_type, base1, d); + tmp = fold_build2 (EXACT_DIV_EXPR, niter_type, iv1->base, d); tmp = fold_build2 (MULT_EXPR, niter_type, tmp, inverse (s, bound)); niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound); } else { - if (zero_p (step1)) + if (zero_p (iv1->step)) /* Condition in shape a + s * i <= b We must know that b + s does not overflow and a <= b + s and then we can compute number of iterations as (b + s - a) / s. (It might @@ -410,20 +427,22 @@ number_of_iterations_cond (tree type, tree base0, tree step0, overflow condition using some information about b - a mod s, but it was already taken into account during LE -> NE transform). */ { - if (mmax) + if (mmax && !iv0->no_overflow) { - bound = fold_binary_to_constant (MINUS_EXPR, type, mmax, step0); + bound = fold_binary_to_constant (MINUS_EXPR, type, + mmax, iv0->step); assumption = fold_build2 (LE_EXPR, boolean_type_node, - base1, bound); + iv1->base, 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); + step = iv0->step; + tmp = fold_build2 (PLUS_EXPR, type, iv1->base, iv0->step); + assumption = fold_build2 (GT_EXPR, boolean_type_node, + iv0->base, tmp); + delta = fold_build2 (PLUS_EXPR, type, iv1->base, step); + delta = fold_build2 (MINUS_EXPR, type, delta, iv0->base); delta = fold_convert (niter_type, delta); } else @@ -431,19 +450,20 @@ number_of_iterations_cond (tree type, tree base0, tree step0, /* Condition in shape a <= b - s * i We must know that a - s does not overflow and a - s <= b and then we can again compute number of iterations as (b - (a - s)) / s. */ - if (mmin) + if (mmin && !iv1->no_overflow) { - bound = fold_binary_to_constant (MINUS_EXPR, type, mmin, step1); + bound = fold_binary_to_constant (MINUS_EXPR, type, + mmin, iv1->step); assumption = fold_build2 (LE_EXPR, boolean_type_node, - bound, base0); + bound, iv0->base); 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); + step = fold_build1 (NEGATE_EXPR, type, iv1->step); + tmp = fold_build2 (PLUS_EXPR, type, iv0->base, iv1->step); + assumption = fold_build2 (GT_EXPR, boolean_type_node, tmp, iv1->base); + delta = fold_build2 (MINUS_EXPR, type, iv0->base, step); + delta = fold_build2 (MINUS_EXPR, type, iv1->base, delta); delta = fold_convert (niter_type, delta); } noloop_assumptions = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, @@ -471,9 +491,8 @@ zero_iter: returns true if the special case was recognized, false otherwise. */ static bool -number_of_iterations_special (tree type, tree base0, tree step0, - enum tree_code code, tree base1, tree step1, - struct tree_niter_desc *niter) +number_of_iterations_special (tree type, affine_iv *iv0, enum tree_code code, + affine_iv *iv1, struct tree_niter_desc *niter) { tree niter_type = unsigned_type_for (type), mmax, mmin; @@ -481,38 +500,36 @@ number_of_iterations_special (tree type, tree base0, tree step0, if (code == GE_EXPR || code == GT_EXPR) { - SWAP (base0, base1); - SWAP (step0, step1); + SWAP (iv0, iv1); code = swap_tree_comparison (code); } switch (code) { case NE_EXPR: - if (zero_p (step0)) + if (zero_p (iv0->step)) { - if (zero_p (step1)) + if (zero_p (iv1->step)) return false; - SWAP (base0, base1); - SWAP (step0, step1); + SWAP (iv0, iv1); } - else if (!zero_p (step1)) + else if (!zero_p (iv1->step)) return false; - if (integer_onep (step0)) + if (integer_onep (iv0->step)) { - /* for (i = base0; i != base1; i++) */ + /* for (i = iv0->base; i != iv1->base; i++) */ niter->assumptions = boolean_true_node; niter->may_be_zero = boolean_false_node; - niter->niter = fold_build2 (MINUS_EXPR, type, base1, base0); + niter->niter = fold_build2 (MINUS_EXPR, type, iv1->base, iv0->base); niter->additional_info = boolean_true_node; } - else if (integer_all_onesp (step0)) + else if (integer_all_onesp (iv0->step)) { - /* for (i = base0; i != base1; i--) */ + /* for (i = iv0->base; i != iv1->base; i--) */ niter->assumptions = boolean_true_node; niter->may_be_zero = boolean_false_node; - niter->niter = fold_build2 (MINUS_EXPR, type, base0, base1); + niter->niter = fold_build2 (MINUS_EXPR, type, iv0->base, iv1->base); } else return false; @@ -520,21 +537,23 @@ number_of_iterations_special (tree type, tree base0, tree step0, break; case LT_EXPR: - if ((step0 && integer_onep (step0) && zero_p (step1)) - || (step1 && integer_all_onesp (step1) && zero_p (step0))) + if ((iv0->step && integer_onep (iv0->step) + && zero_p (iv1->step)) + || (iv1->step && integer_all_onesp (iv1->step) + && zero_p (iv0->step))) { - /* for (i = base0; i < base1; i++) + /* for (i = iv0->base; i < iv1->base; i++) or - for (i = base1; i > base0; i--). + for (i = iv1->base; i > iv0->base; i--). - In both cases # of iterations is base1 - base0. */ + In both cases # of iterations is iv1->base - iv0->base. */ niter->assumptions = boolean_true_node; niter->may_be_zero = fold_build2 (GT_EXPR, boolean_type_node, - base0, base1); - niter->niter = fold_build2 (MINUS_EXPR, type, base1, base0); + iv0->base, iv1->base); + niter->niter = fold_build2 (MINUS_EXPR, type, iv1->base, iv0->base); } else return false; @@ -552,34 +571,36 @@ number_of_iterations_special (tree type, tree base0, tree step0, mmax = TYPE_MAX_VALUE (type); } - if (step0 && integer_onep (step0) && zero_p (step1)) + if (iv0->step && integer_onep (iv0->step) + && zero_p (iv1->step)) { - /* for (i = base0; i <= base1; i++) */ - if (mmax) + /* for (i = iv0->base; i <= iv1->base; i++) */ + if (mmax && !iv0->no_overflow) niter->assumptions = fold_build2 (NE_EXPR, boolean_type_node, - base1, mmax); + iv1->base, mmax); else niter->assumptions = boolean_true_node; - base1 = fold_build2 (PLUS_EXPR, type, base1, - build_int_cst_type (type, 1)); + iv1->base = fold_build2 (PLUS_EXPR, type, iv1->base, + build_int_cst_type (type, 1)); } - else if (step1 && integer_all_onesp (step1) && zero_p (step0)) + else if (iv1->step && integer_all_onesp (iv1->step) + && zero_p (iv0->step)) { - /* for (i = base1; i >= base0; i--) */ - if (mmin) + /* for (i = iv1->base; i >= iv0->base; i--) */ + if (mmin && !iv1->no_overflow) niter->assumptions = fold_build2 (NE_EXPR, boolean_type_node, - base0, mmin); + iv0->base, mmin); else niter->assumptions = boolean_true_node; - base0 = fold_build2 (MINUS_EXPR, type, base0, - build_int_cst_type (type, 1)); + iv0->base = fold_build2 (MINUS_EXPR, type, iv0->base, + build_int_cst_type (type, 1)); } else return false; niter->may_be_zero = fold_build2 (GT_EXPR, boolean_type_node, - base0, base1); - niter->niter = fold_build2 (MINUS_EXPR, type, base1, base0); + iv0->base, iv1->base); + niter->niter = fold_build2 (MINUS_EXPR, type, iv1->base, iv0->base); break; default: @@ -922,9 +943,9 @@ number_of_iterations_exit (struct loop *loop, edge exit, bool warn) { tree stmt, cond, type; - tree op0, base0, step0; - tree op1, base1, step1; + tree op0, op1; enum tree_code code; + affine_iv iv0, iv1; if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src)) return false; @@ -961,21 +982,19 @@ number_of_iterations_exit (struct loop *loop, edge exit, && !POINTER_TYPE_P (type)) return false; - if (!simple_iv (loop, stmt, op0, &base0, &step0, false)) + if (!simple_iv (loop, stmt, op0, &iv0, false)) return false; - if (!simple_iv (loop, stmt, op1, &base1, &step1, false)) + if (!simple_iv (loop, stmt, op1, &iv1, false)) return false; niter->niter = NULL_TREE; /* Handle common special cases first, so that we do not need to use generic (and slow) analysis very often. */ - if (!number_of_iterations_special (type, base0, step0, code, base1, step1, - niter)) + if (!number_of_iterations_special (type, &iv0, code, &iv1, niter)) { - number_of_iterations_cond (type, base0, step0, code, base1, step1, - niter); + number_of_iterations_cond (type, &iv0, code, &iv1, niter); if (!niter->niter) return false; @@ -1019,8 +1038,11 @@ number_of_iterations_exit (struct loop *loop, edge exit, /* We can provide a more specific warning if one of the operator is constant and the other advances by +1 or -1. */ - if (step1 ? !step0 && (integer_onep (step1) || integer_all_onesp (step1)) - : step0 && (integer_onep (step0) || integer_all_onesp (step0))) + if (!zero_p (iv1.step) + ? (zero_p (iv0.step) + && (integer_onep (iv1.step) || integer_all_onesp (iv1.step))) + : (iv0.step + && (integer_onep (iv0.step) || integer_all_onesp (iv0.step)))) wording = flag_unsafe_loop_optimizations ? N_("assuming that the loop is not infinite") |