From: rakdver Date: Wed, 14 Mar 2007 00:38:34 +0000 (+0000) Subject: PR tree-optimization/30730 X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=commitdiff_plain;h=a463eaead43052f98075eb210b931bd0e90b9249 PR tree-optimization/30730 PR tree-optimization/26900 * tree-ssa-loop-niter.c: Include gmp.h. (bounds): New type. (mpz_set_double_int, get_type_bounds, mpz_to_double_int, split_to_var_and_offset, determine_value_range, bound_difference_of_offsetted_base, refine_bounds_using_guard, bound_difference, bounds_add, bounds_negate, number_of_iterations_ne_max, dump_affine_iv): New functions. (number_of_iterations_ne, number_of_iterations_lt_to_ne, assert_loop_rolls_lt, assert_loop_rolls_le): Use bounds on the difference of initial and final value of control iv to validate results. (number_of_iterations_cond): Add loop parameter. Determine bounds on the difference of the extremes of the control iv. Add dumps. (expand_simple_operations): Handle phi nodes. (simplify_using_initial_conditions): Do not record used conditions. (number_of_iterations_exit): Pass loop to number_of_iterations_cond. Do not set additional_info. (implies_nonnegative_p, implies_ge_p): Removed. (derive_constant_upper_bound): Do not use parameter `additional'. (record_estimate): Parameter `additional' removed. Parameter `i_bound' added. Do not call derive_constant_upper_bound. (record_nonwrapping_iv): Use derive_constant_upper_bound to bound the number of iterations estimate. (estimate_numbers_of_iterations_loop): Pass the estimate from the number of iterations analysis to record_estimate. * tree.h (multiple_of_p): Declare. * tree-scalar-evolution.c (expression_expensive_p): Removed. (scev_const_prop): Do not check expression_expensive_p. * fold-const.c (multiple_of_p): Exported. * double-int.c (double_int_mask): Exported. * double-int.h (double_int_mask): Declare. * tree-flow.h (struct tree_niter_desc): Removed additional_info field. Added max field. * gcc.dg/tree-ssa/loop-26.c: New test. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@122896 138bc75d-0d04-0410-961f-82ee72b054a4 --- diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 4644b96cff1..1a40c6f846e 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,41 @@ +2007-03-13 Zdenek Dvorak + + PR tree-optimization/30730 + PR tree-optimization/26900 + * tree-ssa-loop-niter.c: Include gmp.h. + (bounds): New type. + (mpz_set_double_int, get_type_bounds, mpz_to_double_int, + split_to_var_and_offset, determine_value_range, + bound_difference_of_offsetted_base, refine_bounds_using_guard, + bound_difference, bounds_add, bounds_negate, + number_of_iterations_ne_max, dump_affine_iv): New functions. + (number_of_iterations_ne, number_of_iterations_lt_to_ne, + assert_loop_rolls_lt, assert_loop_rolls_le): Use bounds on the + difference of initial and final value of control iv to validate + results. + (number_of_iterations_cond): Add loop parameter. Determine bounds + on the difference of the extremes of the control iv. Add dumps. + (expand_simple_operations): Handle phi nodes. + (simplify_using_initial_conditions): Do not record used conditions. + (number_of_iterations_exit): Pass loop to number_of_iterations_cond. + Do not set additional_info. + (implies_nonnegative_p, implies_ge_p): Removed. + (derive_constant_upper_bound): Do not use parameter `additional'. + (record_estimate): Parameter `additional' removed. Parameter + `i_bound' added. Do not call derive_constant_upper_bound. + (record_nonwrapping_iv): Use derive_constant_upper_bound to + bound the number of iterations estimate. + (estimate_numbers_of_iterations_loop): Pass the estimate from + the number of iterations analysis to record_estimate. + * tree.h (multiple_of_p): Declare. + * tree-scalar-evolution.c (expression_expensive_p): Removed. + (scev_const_prop): Do not check expression_expensive_p. + * fold-const.c (multiple_of_p): Exported. + * double-int.c (double_int_mask): Exported. + * double-int.h (double_int_mask): Declare. + * tree-flow.h (struct tree_niter_desc): Removed additional_info + field. Added max field. + 2007-03-13 David Taylor PR driver/12448: diff --git a/gcc/double-int.c b/gcc/double-int.c index f1824da8ff4..45a833a0654 100644 --- a/gcc/double-int.c +++ b/gcc/double-int.c @@ -26,7 +26,7 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA /* Returns mask for PREC bits. */ -static inline double_int +double_int double_int_mask (unsigned prec) { unsigned HOST_WIDE_INT m; diff --git a/gcc/double-int.h b/gcc/double-int.h index 6ecfa48f787..807166b8957 100644 --- a/gcc/double-int.h +++ b/gcc/double-int.h @@ -134,6 +134,7 @@ void dump_double_int (FILE *, double_int, bool); double_int double_int_ext (double_int, unsigned, bool); double_int double_int_sext (double_int, unsigned); double_int double_int_zext (double_int, unsigned); +double_int double_int_mask (unsigned); #define ALL_ONES (~((unsigned HOST_WIDE_INT) 0)) diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 3c03cb8742b..c0358cfc826 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2007-03-13 Zdenek Dvorak + + * gcc.dg/tree-ssa/loop-26.c: New test. + 2007-03-13 Uros Bizjak * testsuite/gcc.target/i386/cmpxchg16b-1.c: New test. @@ -10,13 +14,13 @@ 2007-03-12 Seongbae Park - * gcc.dg/wvla-1.c: New test - * gcc.dg/wvla-2.c: New test - * gcc.dg/wvla-3.c: New test - * gcc.dg/wvla-4.c: New test - * gcc.dg/wvla-5.c: New test - * gcc.dg/wvla-6.c: New test - * gcc.dg/wvla-7.c: New test + * gcc.dg/wvla-1.c: New test + * gcc.dg/wvla-2.c: New test + * gcc.dg/wvla-3.c: New test + * gcc.dg/wvla-4.c: New test + * gcc.dg/wvla-5.c: New test + * gcc.dg/wvla-6.c: New test + * gcc.dg/wvla-7.c: New test * g++.dg/warn/Wvla-1.C: New test * g++.dg/warn/Wvla-2.C: New test * g++.dg/warn/Wvla-3.C: New test diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-26.c b/gcc/testsuite/gcc.dg/tree-ssa/loop-26.c new file mode 100644 index 00000000000..5ebb3b1e1f7 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-26.c @@ -0,0 +1,29 @@ +/* PR 30730, PR 26900, number of iterations analysis should be able to + determine number of iterations of the following loops unconditionally. */ + +/* { dg-do compile } */ +/* { dg-options "-O -fstrict-overflow -fdump-tree-empty" } */ + +unsigned foo(unsigned int n) +{ + unsigned x = 0;; + + while (n > 10) + { + n -= 2; + x++; + } + + return x; +} + +int foo0(int i0, int i1) +{ + int i, j = 0; + for (i=i0; i<=i1+1; ++i) + ++j; + return j; +} + +/* { dg-final { scan-tree-dump-times "Removing empty loop" 2 "empty" } } */ +/* { dg-final { cleanup-tree-dump "empty" } } */ diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h index 99db89da32e..ea2d677be43 100644 --- a/gcc/tree-flow.h +++ b/gcc/tree-flow.h @@ -822,18 +822,8 @@ struct tree_niter_desc a loop (provided that assumptions == true and may_be_zero == false), more precisely the number of executions of the latch of the loop. */ - tree additional_info; /* The boolean expression. Sometimes we use additional - knowledge to simplify the other expressions - contained in this structure (for example the - knowledge about value ranges of operands on entry to - the loop). If this is a case, conjunction of such - condition is stored in this field, so that we do not - lose the information: for example if may_be_zero - is (n <= 0) and niter is (unsigned) n, we know - that the number of iterations is at most - MAX_SIGNED_INT. However if the (n <= 0) assumption - is eliminated (by looking at the guard on entry of - the loop), then the information would be lost. */ + double_int max; /* The upper bound on the number of iterations of + the loop. */ /* The simplified shape of the exit condition. The loop exits if CONTROL CMP BOUND is false, where CMP is one of NE_EXPR, diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c index f1914c3d51e..846d27414d5 100644 --- a/gcc/tree-scalar-evolution.c +++ b/gcc/tree-scalar-evolution.c @@ -2864,14 +2864,6 @@ scev_finalize (void) BITMAP_FREE (already_instantiated); } -/* Returns true if EXPR looks expensive. */ - -static bool -expression_expensive_p (tree expr) -{ - return force_expr_to_var_cost (expr) >= target_spill_cost; -} - /* Replace ssa names for that scev can prove they are constant by the appropriate constants. Also perform final value replacement in loops, in case the replacement expressions are cheap. @@ -2958,10 +2950,13 @@ scev_const_prop (void) continue; niter = number_of_latch_executions (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)) + /* We used to check here whether the computation of NITER is expensive, + and avoided final value elimination if that is the case. The problem + is that it is hard to evaluate whether the expression is too + expensive, as we do not know what optimization opportunities the + the elimination of the final value may reveal. Therefore, we now + eliminate the final values of induction variables unconditionally. */ + if (niter == chrec_dont_know) continue; /* Ensure that it is possible to insert new statements somewhere. */ diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index 018e9a80529..f105d2b636e 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -42,9 +42,14 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA #include "flags.h" #include "toplev.h" #include "tree-inline.h" +#include "gmp.h" #define SWAP(X, Y) do { void *tmp = (X); (X) = (Y); (Y) = tmp; } while (0) +/* The maximum number of dominator BBs we search for conditions + of loop header copies we use for simplifying a conditional + expression. */ +#define MAX_DOMINATORS_TO_WALK 8 /* @@ -52,6 +57,492 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA */ +/* Bounds on some value, BELOW <= X <= UP. */ + +typedef struct +{ + mpz_t below, up; +} bounds; + +/* Sets RESULT to VAL, taken unsigned if UNS is true and as signed + otherwise. */ + +static void +mpz_set_double_int (mpz_t result, double_int val, bool uns) +{ + bool negate = false; + unsigned HOST_WIDE_INT vp[2]; + + if (!uns && double_int_negative_p (val)) + { + negate = true; + val = double_int_neg (val); + } + + vp[0] = val.low; + vp[1] = (unsigned HOST_WIDE_INT) val.high; + mpz_import (result, 2, -1, sizeof (HOST_WIDE_INT), 0, 0, vp); + + if (negate) + mpz_neg (result, result); +} + +/* Stores bounds of TYPE to MIN and MAX. */ + +static void +get_type_bounds (tree type, mpz_t min, mpz_t max) +{ + if (TYPE_UNSIGNED (type)) + { + mpz_set_ui (min, 0); + mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true); + } + else + { + double_int mx, mn; + + mx = double_int_mask (TYPE_PRECISION (type) - 1); + mn = double_int_sext (double_int_add (mx, double_int_one), + TYPE_PRECISION (type)); + mpz_set_double_int (max, mx, true); + mpz_set_double_int (min, mn, false); + } +} + +/* Returns VAL converted to TYPE. If VAL does not fit in TYPE, + the minimum or maximum value of the type is returned instead. */ + +static double_int +mpz_to_double_int (tree type, mpz_t val) +{ + mpz_t min, max; + unsigned HOST_WIDE_INT vp[2]; + bool negate = false; + size_t count; + double_int res; + + mpz_init (min); + mpz_init (max); + get_type_bounds (type, min, max); + + if (mpz_cmp (val, min) < 0) + mpz_set (val, min); + else if (mpz_cmp (val, max) > 0) + mpz_set (val, max); + + if (mpz_sgn (val) < 0) + negate = true; + + vp[0] = 0; + vp[1] = 0; + mpz_export (vp, &count, -1, sizeof (HOST_WIDE_INT), 0, 0, val); + gcc_assert (count <= 2); + + mpz_clear (min); + mpz_clear (max); + + res.low = vp[0]; + res.high = (HOST_WIDE_INT) vp[1]; + + res = double_int_ext (res, TYPE_PRECISION (type), TYPE_UNSIGNED (type)); + if (negate) + res = double_int_neg (res); + + return res; +} + +/* Splits expression EXPR to a variable part VAR and constant OFFSET. */ + +static void +split_to_var_and_offset (tree expr, tree *var, mpz_t offset) +{ + tree type = TREE_TYPE (expr); + tree op0, op1; + double_int off; + bool negate = false; + + *var = expr; + mpz_set_ui (offset, 0); + + switch (TREE_CODE (expr)) + { + case MINUS_EXPR: + negate = true; + /* Fallthru. */ + + case PLUS_EXPR: + op0 = TREE_OPERAND (expr, 0); + op1 = TREE_OPERAND (expr, 1); + + if (TREE_CODE (op1) != INTEGER_CST) + break; + + *var = op0; + /* Always sign extend the offset. */ + off = double_int_sext (tree_to_double_int (op1), + TYPE_PRECISION (type)); + mpz_set_double_int (offset, off, false); + break; + + case INTEGER_CST: + *var = build_int_cst_type (type, 0); + off = tree_to_double_int (expr); + mpz_set_double_int (offset, off, TYPE_UNSIGNED (type)); + break; + + default: + break; + } +} + +/* Stores estimate on the minimum/maximum value of the expression VAR + OFF + in TYPE to MIN and MAX. */ + +static void +determine_value_range (tree type, tree var, mpz_t off, + mpz_t min, mpz_t max) +{ + /* If the expression is a constant, we know its value exactly. */ + if (integer_zerop (var)) + { + mpz_set (min, off); + mpz_set (max, off); + return; + } + + /* If the computation may wrap, we know nothing about the value, except for + the range of the type. */ + get_type_bounds (type, min, max); + if (!nowrap_type_p (type)) + return; + + /* Since the addition of OFF does not wrap, if OFF is positive, then we may + add it to MIN, otherwise to MAX. */ + if (mpz_sgn (off) < 0) + mpz_add (max, max, off); + else + mpz_add (min, min, off); +} + +/* Stores the bounds on the difference of the values of the expressions + (var + X) and (var + Y), computed in TYPE, to BNDS. */ + +static void +bound_difference_of_offsetted_base (tree type, mpz_t x, mpz_t y, + bounds *bnds) +{ + int rel = mpz_cmp (x, y); + bool may_wrap = !nowrap_type_p (type); + mpz_t m; + + /* If X == Y, then the expressions are always equal. + If X > Y, there are the following possibilities: + a) neither of var + X and var + Y overflow or underflow, or both of + them do. Then their difference is X - Y. + b) var + X overflows, and var + Y does not. Then the values of the + expressions are var + X - M and var + Y, where M is the range of + the type, and their difference is X - Y - M. + c) var + Y underflows and var + X does not. Their difference again + is M - X + Y. + Therefore, if the arithmetics in type does not overflow, then the + bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y) + Similarly, if X < Y, the bounds are either (X - Y, X - Y) or + (X - Y, X - Y + M). */ + + if (rel == 0) + { + mpz_set_ui (bnds->below, 0); + mpz_set_ui (bnds->up, 0); + return; + } + + mpz_init (m); + mpz_set_double_int (m, double_int_mask (TYPE_PRECISION (type)), true); + mpz_add_ui (m, m, 1); + mpz_sub (bnds->up, x, y); + mpz_set (bnds->below, bnds->up); + + if (may_wrap) + { + if (rel > 0) + mpz_sub (bnds->below, bnds->below, m); + else + mpz_add (bnds->up, bnds->up, m); + } + + mpz_clear (m); +} + +/* From condition C0 CMP C1 derives information regarding the + difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE, + and stores it to BNDS. */ + +static void +refine_bounds_using_guard (tree type, tree varx, mpz_t offx, + tree vary, mpz_t offy, + tree c0, enum tree_code cmp, tree c1, + bounds *bnds) +{ + tree varc0, varc1, tmp; + mpz_t offc0, offc1, loffx, loffy, bnd; + bool lbound = false; + bool no_wrap = nowrap_type_p (type); + bool x_ok, y_ok; + + switch (cmp) + { + case LT_EXPR: + case LE_EXPR: + case GT_EXPR: + case GE_EXPR: + break; + + case EQ_EXPR: + /* We could derive quite precise information from EQ_EXPR, however, such + a guard is unlikely to appear, so we do not bother with handling it. + TODO. */ + return; + + case NE_EXPR: + /* NE_EXPR comparisons do not contain much of useful information (except for + special cases like comparing with the bounds of the type, TODO). */ + return; + default: + return; + } + + mpz_init (offc0); + mpz_init (offc1); + split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0); + split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1); + + /* We are only interested in comparisons of expressions based on VARX and + VARY. TODO -- we might also be able to derive some bounds from + expressions containing just one of the variables. */ + + if (operand_equal_p (varx, varc1, 0)) + { + tmp = varc0; varc0 = varc1; varc1 = tmp; + mpz_swap (offc0, offc1); + cmp = swap_tree_comparison (cmp); + } + + if (!operand_equal_p (varx, varc0, 0) + || !operand_equal_p (vary, varc1, 0)) + goto end; + + mpz_init_set (loffx, offx); + mpz_init_set (loffy, offy); + + if (cmp == GT_EXPR || cmp == GE_EXPR) + { + tmp = varx; varx = vary; vary = tmp; + mpz_swap (offc0, offc1); + mpz_swap (loffx, loffy); + cmp = swap_tree_comparison (cmp); + lbound = true; + } + + /* If there is no overflow, the condition implies that + + (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0). + + The overflows and underflows may complicate things a bit; each + overflow decreases the appropriate offset by M, and underflow + increases it by M. The above inequality would not necessarily be + true if + + -- VARX + OFFX underflows and VARX + OFFC0 does not, or + VARX + OFFC0 overflows, but VARX + OFFX does not. + This may only happen if OFFX < OFFC0. + -- VARY + OFFY overflows and VARY + OFFC1 does not, or + VARY + OFFC1 underflows and VARY + OFFY does not. + This may only happen if OFFY > OFFC1. */ + + if (no_wrap) + { + x_ok = true; + y_ok = true; + } + else + { + x_ok = (integer_zerop (varx) + || mpz_cmp (loffx, offc0) >= 0); + y_ok = (integer_zerop (vary) + || mpz_cmp (loffy, offc1) <= 0); + } + + if (x_ok && y_ok) + { + mpz_init (bnd); + mpz_sub (bnd, loffx, loffy); + mpz_add (bnd, bnd, offc1); + mpz_sub (bnd, bnd, offc0); + + if (cmp == LT_EXPR) + mpz_sub_ui (bnd, bnd, 1); + + if (lbound) + { + mpz_neg (bnd, bnd); + if (mpz_cmp (bnds->below, bnd) < 0) + mpz_set (bnds->below, bnd); + } + else + { + if (mpz_cmp (bnd, bnds->up) < 0) + mpz_set (bnds->up, bnd); + } + mpz_clear (bnd); + } + + mpz_clear (loffx); + mpz_clear (loffy); +end: + mpz_clear (offc0); + mpz_clear (offc1); +} + +/* Stores the bounds on the value of the expression X - Y in LOOP to BNDS. + The subtraction is considered to be performed in arbitrary precision, + without overflows. + + We do not attempt to be too clever regarding the value ranges of X and + Y; most of the time, they are just integers or ssa names offsetted by + integer. However, we try to use the information contained in the + comparisons before the loop (usually created by loop header copying). */ + +static void +bound_difference (struct loop *loop, tree x, tree y, bounds *bnds) +{ + tree type = TREE_TYPE (x); + tree varx, vary; + mpz_t offx, offy; + mpz_t minx, maxx, miny, maxy; + int cnt = 0; + edge e; + basic_block bb; + tree cond, c0, c1, ctype; + enum tree_code cmp; + + mpz_init (bnds->below); + mpz_init (bnds->up); + mpz_init (offx); + mpz_init (offy); + split_to_var_and_offset (x, &varx, offx); + split_to_var_and_offset (y, &vary, offy); + + if (!integer_zerop (varx) + && operand_equal_p (varx, vary, 0)) + { + /* Special case VARX == VARY -- we just need to compare the + offsets. The matters are a bit more complicated in the + case addition of offsets may wrap. */ + bound_difference_of_offsetted_base (type, offx, offy, bnds); + } + else + { + /* Otherwise, use the value ranges to determine the initial + estimates on below and up. */ + mpz_init (minx); + mpz_init (maxx); + mpz_init (miny); + mpz_init (maxy); + determine_value_range (type, varx, offx, minx, maxx); + determine_value_range (type, vary, offy, miny, maxy); + + mpz_sub (bnds->below, minx, maxy); + mpz_sub (bnds->up, maxx, miny); + mpz_clear (minx); + mpz_clear (maxx); + mpz_clear (miny); + mpz_clear (maxy); + } + + /* If both X and Y are constants, we cannot get any more precise. */ + if (integer_zerop (varx) && integer_zerop (vary)) + goto end; + + /* Now walk the dominators of the loop header and use the entry + guards to refine the estimates. */ + for (bb = loop->header; + bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK; + bb = get_immediate_dominator (CDI_DOMINATORS, bb)) + { + if (!single_pred_p (bb)) + continue; + e = single_pred_edge (bb); + + if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))) + continue; + + cond = COND_EXPR_COND (last_stmt (e->src)); + if (!COMPARISON_CLASS_P (cond)) + continue; + c0 = TREE_OPERAND (cond, 0); + cmp = TREE_CODE (cond); + c1 = TREE_OPERAND (cond, 1); + ctype = TREE_TYPE (c0); + + if (!tree_ssa_useless_type_conversion_1 (ctype, type)) + continue; + + if (e->flags & EDGE_FALSE_VALUE) + cmp = invert_tree_comparison (cmp, false); + + refine_bounds_using_guard (type, varx, offx, vary, offy, + c0, cmp, c1, bnds); + ++cnt; + } + +end: + mpz_clear (offx); + mpz_clear (offy); +} + +/* Update the bounds in BNDS that restrict the value of X to the bounds + that restrict the value of X + DELTA. X can be obtained as a + difference of two values in TYPE. */ + +static void +bounds_add (bounds *bnds, double_int delta, tree type) +{ + mpz_t mdelta, max; + + mpz_init (mdelta); + mpz_set_double_int (mdelta, delta, false); + + mpz_init (max); + mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true); + + mpz_add (bnds->up, bnds->up, mdelta); + mpz_add (bnds->below, bnds->below, mdelta); + + if (mpz_cmp (bnds->up, max) > 0) + mpz_set (bnds->up, max); + + mpz_neg (max, max); + if (mpz_cmp (bnds->below, max) < 0) + mpz_set (bnds->below, max); + + mpz_clear (mdelta); + mpz_clear (max); +} + +/* Update the bounds in BNDS that restrict the value of X to the bounds + that restrict the value of -X. */ + +static void +bounds_negate (bounds *bnds) +{ + mpz_t tmp; + + mpz_init_set (tmp, bnds->up); + mpz_neg (bnds->up, bnds->below); + mpz_neg (bnds->below, tmp); + mpz_clear (tmp); +} + /* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */ static tree @@ -96,26 +587,71 @@ inverse (tree x, tree mask) return rslt; } +/* Derives the upper bound BND on the number of executions of loop with exit + condition S * i <> C, assuming that the loop is not infinite. If + NO_OVERFLOW is true, then the control variable of the loop does not + overflow. If NO_OVERFLOW is true or BNDS.below >= 0, then BNDS.up + contains the upper bound on the value of C. */ + +static void +number_of_iterations_ne_max (mpz_t bnd, bool no_overflow, tree c, tree s, + bounds *bnds) +{ + double_int max; + mpz_t d; + + /* If the control variable does not overflow, the number of iterations is + at most c / s. Otherwise it is at most the period of the control + variable. */ + if (!no_overflow && !multiple_of_p (TREE_TYPE (c), c, s)) + { + max = double_int_mask (TYPE_PRECISION (TREE_TYPE (c)) + - tree_low_cst (num_ending_zeros (s), 1)); + mpz_set_double_int (bnd, max, true); + return; + } + + /* Determine the upper bound on C. */ + if (no_overflow || mpz_sgn (bnds->below) >= 0) + mpz_set (bnd, bnds->up); + else if (TREE_CODE (c) == INTEGER_CST) + mpz_set_double_int (bnd, tree_to_double_int (c), true); + else + mpz_set_double_int (bnd, double_int_mask (TYPE_PRECISION (TREE_TYPE (c))), + true); + + mpz_init (d); + mpz_set_double_int (d, tree_to_double_int (s), true); + mpz_fdiv_q (bnd, bnd, d); + mpz_clear (d); +} + /* Determines number of iterations of loop whose ending condition is IV <> FINAL. TYPE is the type of the iv. The number of iterations is stored to NITER. NEVER_INFINITE is true if we know that the exit must be taken eventually, i.e., that the IV ever reaches the value FINAL (we derived this earlier, and possibly set - NITER->assumptions to make sure this is the case). */ + NITER->assumptions to make sure this is the case). BNDS contains the + bounds on the difference FINAL - IV->base. */ static bool number_of_iterations_ne (tree type, affine_iv *iv, tree final, - struct tree_niter_desc *niter, bool never_infinite) + struct tree_niter_desc *niter, bool never_infinite, + bounds *bnds) { tree niter_type = unsigned_type_for (type); tree s, c, d, bits, assumption, tmp, bound; + mpz_t max; niter->control = *iv; niter->bound = final; niter->cmp = NE_EXPR; - /* Rearrange the terms so that we get inequality s * i <> c, with s - positive. Also cast everything to the unsigned type. */ + /* Rearrange the terms so that we get inequality S * i <> C, with S + positive. Also cast everything to the unsigned type. If IV does + not overflow, BNDS bounds the value of C. Also, this is the + case if the computation |FINAL - IV->base| does not overflow, i.e., + if BNDS->below in the result is nonnegative. */ if (tree_int_cst_sign_bit (iv->step)) { s = fold_convert (niter_type, @@ -123,6 +659,7 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final, c = fold_build2 (MINUS_EXPR, niter_type, fold_convert (niter_type, iv->base), fold_convert (niter_type, final)); + bounds_negate (bnds); } else { @@ -132,6 +669,11 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final, fold_convert (niter_type, iv->base)); } + mpz_init (max); + number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds); + niter->max = mpz_to_double_int (niter_type, max); + mpz_clear (max); + /* First the trivial cases -- when the step is 1. */ if (integer_onep (s)) { @@ -175,17 +717,21 @@ number_of_iterations_ne (tree type, affine_iv *iv, tree final, of the step. The assumptions necessary to ensure that the computation of the final value does not overflow are recorded in NITER. If we find the final value, we adjust DELTA and return TRUE. Otherwise - we return false. */ + we return false. BNDS bounds the value of IV1->base - IV0->base, + and will be updated by the same amount as DELTA. */ static bool number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1, struct tree_niter_desc *niter, - tree *delta, tree step) + tree *delta, tree step, + bounds *bnds) { tree niter_type = TREE_TYPE (step); tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step); tree tmod; + mpz_t mmod; tree assumption = boolean_true_node, bound, noloop; + bool ret = false; if (TREE_CODE (mod) != INTEGER_CST) return false; @@ -193,6 +739,10 @@ number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1, mod = fold_build2 (MINUS_EXPR, niter_type, step, mod); tmod = fold_convert (type, mod); + mpz_init (mmod); + mpz_set_double_int (mmod, tree_to_double_int (mod), true); + mpz_neg (mmod, mmod); + if (integer_nonzerop (iv0->step)) { /* The final value of the iv is iv1->base + MOD, assuming that this @@ -205,12 +755,15 @@ number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1, assumption = fold_build2 (LE_EXPR, boolean_type_node, iv1->base, bound); if (integer_zerop (assumption)) - return false; + goto end; } - noloop = fold_build2 (GT_EXPR, boolean_type_node, - iv0->base, - fold_build2 (PLUS_EXPR, type, - iv1->base, tmod)); + if (mpz_cmp (mmod, bnds->below) < 0) + noloop = boolean_false_node; + else + noloop = fold_build2 (GT_EXPR, boolean_type_node, + iv0->base, + fold_build2 (PLUS_EXPR, type, + iv1->base, tmod)); } else { @@ -224,12 +777,15 @@ number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1, assumption = fold_build2 (GE_EXPR, boolean_type_node, iv0->base, bound); if (integer_zerop (assumption)) - return false; + goto end; } - noloop = fold_build2 (GT_EXPR, boolean_type_node, - fold_build2 (MINUS_EXPR, type, - iv0->base, tmod), - iv1->base); + if (mpz_cmp (mmod, bnds->below) < 0) + noloop = boolean_false_node; + else + noloop = fold_build2 (GT_EXPR, boolean_type_node, + fold_build2 (MINUS_EXPR, type, + iv0->base, tmod), + iv1->base); } if (!integer_nonzerop (assumption)) @@ -240,8 +796,13 @@ number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1, niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, niter->may_be_zero, noloop); + bounds_add (bnds, tree_to_double_int (mod), type); *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod); - return true; + + ret = true; +end: + mpz_clear (mmod); + return ret; } /* Add assertions to NITER that ensure that the control variable of the loop @@ -315,14 +876,75 @@ assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1, } /* Add an assumption to NITER that a loop whose ending condition - is IV0 < IV1 rolls. TYPE is the type of the control iv. */ + is IV0 < IV1 rolls. TYPE is the type of the control iv. BNDS + bounds the value of IV1->base - IV0->base. */ static void assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1, - struct tree_niter_desc *niter) + struct tree_niter_desc *niter, bounds *bnds) { tree assumption = boolean_true_node, bound, diff; tree mbz, mbzl, mbzr; + bool rolls_p, no_overflow_p; + double_int dstep; + mpz_t mstep, max; + + /* We are going to compute the number of iterations as + (iv1->base - iv0->base + step - 1) / step, computed in the unsigned + variant of TYPE. This formula only works if + + -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1 + + (where MAX is the maximum value of the unsigned variant of TYPE, and + the computations in this formula are performed in full precision + (without overflows). + + Usually, for loops with exit condition iv0->base + step * i < iv1->base, + we have a condition of form iv0->base - step < iv1->base before the loop, + and for loops iv0->base < iv1->base - step * i the condition + iv0->base < iv1->base + step, due to loop header copying, which enable us + to prove the lower bound. + + The upper bound is more complicated. Unless the expressions for initial + and final value themselves contain enough information, we usually cannot + derive it from the context. */ + + /* First check whether the answer does not follow from the bounds we gathered + before. */ + if (integer_nonzerop (iv0->step)) + dstep = tree_to_double_int (iv0->step); + else + { + dstep = double_int_sext (tree_to_double_int (iv1->step), + TYPE_PRECISION (type)); + dstep = double_int_neg (dstep); + } + + mpz_init (mstep); + mpz_set_double_int (mstep, dstep, true); + mpz_neg (mstep, mstep); + mpz_add_ui (mstep, mstep, 1); + + rolls_p = mpz_cmp (mstep, bnds->below) <= 0; + + mpz_init (max); + mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true); + mpz_add (max, max, mstep); + no_overflow_p = (mpz_cmp (bnds->up, max) <= 0 + /* For pointers, only values lying inside a single object + can be compared or manipulated by pointer arithmetics. + Gcc in general does not allow or handle objects larger + than half of the address space, hence the upper bound + is satisfied for pointers. */ + || POINTER_TYPE_P (type)); + mpz_clear (mstep); + mpz_clear (max); + + if (rolls_p && no_overflow_p) + return; + + /* Now the hard part; we must formulate the assumption(s) as expressions, and + we must be careful not to introduce overflow. */ if (integer_nonzerop (iv0->step)) { @@ -362,27 +984,31 @@ assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1, mbzr = fold_build2 (MINUS_EXPR, type, iv1->base, diff); } - mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr); - if (!integer_nonzerop (assumption)) niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, niter->assumptions, assumption); - if (!integer_zerop (mbz)) - niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, - niter->may_be_zero, mbz); + if (!rolls_p) + { + mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr); + niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, + niter->may_be_zero, mbz); + } } /* Determines number of iterations of loop whose ending condition is IV0 < IV1. TYPE is the type of the iv. The number of - iterations is stored to NITER. */ + iterations is stored to NITER. BNDS bounds the difference + IV1->base - IV0->base. */ static bool number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1, struct tree_niter_desc *niter, - bool never_infinite ATTRIBUTE_UNUSED) + bool never_infinite ATTRIBUTE_UNUSED, + bounds *bnds) { tree niter_type = unsigned_type_for (type); tree delta, step, s; + mpz_t mstep, tmp; if (integer_nonzerop (iv0->step)) { @@ -412,10 +1038,18 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1, for (i = iv1->base; i > iv0->base; i--). In both cases # of iterations is iv1->base - iv0->base, assuming that - iv1->base >= iv0->base. */ - niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node, - iv1->base, iv0->base); + iv1->base >= iv0->base. + + First try to derive a lower bound on the value of + iv1->base - iv0->base, computed in full precision. If the difference + is nonnegative, we are done, otherwise we must record the + condition. */ + + if (mpz_sgn (bnds->below) < 0) + niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node, + iv1->base, iv0->base); niter->niter = delta; + niter->max = mpz_to_double_int (niter_type, bnds->up); return true; } @@ -428,7 +1062,8 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1, /* If we can determine the final value of the control iv exactly, we can transform the condition to != comparison. In particular, this will be the case if DELTA is constant. */ - if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step)) + if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step, + bnds)) { affine_iv zps; @@ -438,7 +1073,7 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1, zps does not overflow. */ zps.no_overflow = true; - return number_of_iterations_ne (type, &zps, delta, niter, true); + return number_of_iterations_ne (type, &zps, delta, niter, true, bnds); } /* Make sure that the control iv does not overflow. */ @@ -448,12 +1083,23 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1, /* We determine the number of iterations as (delta + step - 1) / step. For this to work, we must know that iv1->base >= iv0->base - step + 1, otherwise the loop does not roll. */ - assert_loop_rolls_lt (type, iv0, iv1, niter); + assert_loop_rolls_lt (type, iv0, iv1, niter, bnds); s = fold_build2 (MINUS_EXPR, niter_type, step, build_int_cst (niter_type, 1)); delta = fold_build2 (PLUS_EXPR, niter_type, delta, s); niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step); + + mpz_init (mstep); + mpz_init (tmp); + mpz_set_double_int (mstep, tree_to_double_int (step), true); + mpz_add (tmp, bnds->up, mstep); + mpz_sub_ui (tmp, tmp, 1); + mpz_fdiv_q (tmp, tmp, mstep); + niter->max = mpz_to_double_int (niter_type, tmp); + mpz_clear (mstep); + mpz_clear (tmp); + return true; } @@ -462,11 +1108,12 @@ number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1, iterations is stored to NITER. NEVER_INFINITE is true if we know that this condition must eventually become false (we derived this earlier, and possibly set NITER->assumptions to make sure this - is the case). */ + is the case). BNDS bounds the difference IV1->base - IV0->base. */ static bool number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1, - struct tree_niter_desc *niter, bool never_infinite) + struct tree_niter_desc *niter, bool never_infinite, + bounds *bnds) { tree assumption; @@ -497,7 +1144,28 @@ number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1, else iv0->base = fold_build2 (MINUS_EXPR, type, iv0->base, build_int_cst (type, 1)); - return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite); + + bounds_add (bnds, double_int_one, type); + + return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite, bnds); +} + +/* Dumps description of affine induction variable IV to FILE. */ + +static void +dump_affine_iv (FILE *file, affine_iv *iv) +{ + if (!integer_zerop (iv->step)) + fprintf (file, "["); + + print_generic_expr (dump_file, iv->base, TDF_SLIM); + + if (!integer_zerop (iv->step)) + { + fprintf (file, ", + , "); + print_generic_expr (dump_file, iv->step, TDF_SLIM); + fprintf (file, "]%s", iv->no_overflow ? "(no_overflow)" : ""); + } } /* Determine the number of iterations according to condition (for staying @@ -507,6 +1175,8 @@ number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1, 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). + LOOP is the loop whose number of iterations we are determining. + ONLY_EXIT is true if we are sure this is the only way the loop could be exited (including possibly non-returning function calls, exceptions, etc.) -- in this case we can use the information whether the control induction @@ -518,11 +1188,13 @@ number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1, was determined (possibly with some assumptions). */ static bool -number_of_iterations_cond (tree type, affine_iv *iv0, enum tree_code code, +number_of_iterations_cond (struct loop *loop, + tree type, affine_iv *iv0, enum tree_code code, affine_iv *iv1, struct tree_niter_desc *niter, bool only_exit) { - bool never_infinite; + bool never_infinite, ret; + bounds bnds; /* The meaning of these assumptions is this: if !assumptions @@ -532,7 +1204,7 @@ number_of_iterations_cond (tree type, affine_iv *iv0, enum tree_code code, niter->assumptions = boolean_true_node; niter->may_be_zero = boolean_false_node; niter->niter = NULL_TREE; - niter->additional_info = boolean_true_node; + niter->max = double_int_zero; niter->bound = NULL_TREE; niter->cmp = ERROR_MARK; @@ -618,23 +1290,89 @@ number_of_iterations_cond (tree type, affine_iv *iv0, enum tree_code code, if (integer_zerop (fold_build2 (code, boolean_type_node, iv0->base, iv1->base))) { niter->niter = build_int_cst (unsigned_type_for (type), 0); + niter->max = double_int_zero; return true; } - + /* OK, now we know we have a senseful loop. Handle several cases, depending on what comparison operator is used. */ + bound_difference (loop, iv1->base, iv0->base, &bnds); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, + "Analysing # of iterations of loop %d\n", loop->num); + + fprintf (dump_file, " exit condition "); + dump_affine_iv (dump_file, iv0); + fprintf (dump_file, " %s ", + code == NE_EXPR ? "!=" + : code == LT_EXPR ? "<" + : "<="); + dump_affine_iv (dump_file, iv1); + fprintf (dump_file, "\n"); + + fprintf (dump_file, " bounds on difference of bases: "); + mpz_out_str (dump_file, 10, bnds.below); + fprintf (dump_file, " ... "); + mpz_out_str (dump_file, 10, bnds.up); + fprintf (dump_file, "\n"); + } + switch (code) { case NE_EXPR: gcc_assert (integer_zerop (iv1->step)); - return number_of_iterations_ne (type, iv0, iv1->base, niter, never_infinite); + ret = number_of_iterations_ne (type, iv0, iv1->base, niter, + never_infinite, &bnds); + break; + case LT_EXPR: - return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite); + ret = number_of_iterations_lt (type, iv0, iv1, niter, never_infinite, + &bnds); + break; + case LE_EXPR: - return number_of_iterations_le (type, iv0, iv1, niter, never_infinite); + ret = number_of_iterations_le (type, iv0, iv1, niter, never_infinite, + &bnds); + break; + default: gcc_unreachable (); } + + mpz_clear (bnds.up); + mpz_clear (bnds.below); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + if (ret) + { + fprintf (dump_file, " result:\n"); + if (!integer_nonzerop (niter->assumptions)) + { + fprintf (dump_file, " under assumptions "); + print_generic_expr (dump_file, niter->assumptions, TDF_SLIM); + fprintf (dump_file, "\n"); + } + + if (!integer_zerop (niter->may_be_zero)) + { + fprintf (dump_file, " zero if "); + print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM); + fprintf (dump_file, "\n"); + } + + fprintf (dump_file, " # of iterations "); + print_generic_expr (dump_file, niter->niter, TDF_SLIM); + fprintf (dump_file, ", bounded by "); + dump_double_int (dump_file, niter->max, true); + fprintf (dump_file, "\n"); + } + else + fprintf (dump_file, " failed\n\n"); + } + return ret; } /* Substitute NEW for OLD in EXPR and fold the result. */ @@ -718,6 +1456,24 @@ expand_simple_operations (tree expr) return expr; stmt = SSA_NAME_DEF_STMT (expr); + if (TREE_CODE (stmt) == PHI_NODE) + { + basic_block src, dest; + + if (PHI_NUM_ARGS (stmt) != 1) + return expr; + e = PHI_ARG_DEF (stmt, 0); + + /* Avoid propagating through loop exit phi nodes, which + could break loop-closed SSA form restrictions. */ + dest = bb_for_stmt (stmt); + src = single_pred (dest); + if (TREE_CODE (e) == SSA_NAME + && src->loop_father != dest->loop_father) + return expr; + + return expand_simple_operations (e); + } if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT) return expr; @@ -861,23 +1617,16 @@ tree_simplify_using_condition (tree cond, tree expr) return tree_simplify_using_condition_1 (cond, expr); } -/* The maximum number of dominator BBs we search for conditions - of loop header copies we use for simplifying a conditional - expression. */ -#define MAX_DOMINATORS_TO_WALK 8 - /* Tries to simplify EXPR using the conditions on entry to LOOP. - Record the conditions used for simplification to CONDS_USED. Returns the simplified expression (or EXPR unchanged, if no simplification was possible).*/ static tree -simplify_using_initial_conditions (struct loop *loop, tree expr, - tree *conds_used) +simplify_using_initial_conditions (struct loop *loop, tree expr) { edge e; basic_block bb; - tree exp, cond; + tree cond; int cnt = 0; if (TREE_CODE (expr) == INTEGER_CST) @@ -900,15 +1649,7 @@ simplify_using_initial_conditions (struct loop *loop, tree expr, cond = COND_EXPR_COND (last_stmt (e->src)); if (e->flags & EDGE_FALSE_VALUE) cond = invert_truthvalue (cond); - exp = tree_simplify_using_condition (cond, expr); - - if (exp != expr) - *conds_used = fold_build2 (TRUTH_AND_EXPR, - boolean_type_node, - *conds_used, - cond); - - expr = exp; + expr = tree_simplify_using_condition (cond, expr); ++cnt; } @@ -1065,7 +1806,7 @@ number_of_iterations_exit (struct loop *loop, edge exit, iv0.base = expand_simple_operations (iv0.base); iv1.base = expand_simple_operations (iv1.base); - if (!number_of_iterations_cond (type, &iv0, code, &iv1, niter, + if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter, loop_only_exit_p (loop, exit))) { fold_undefer_and_ignore_overflow_warnings (); @@ -1081,15 +1822,12 @@ number_of_iterations_exit (struct loop *loop, edge exit, niter->niter = simplify_using_outer_evolutions (loop, niter->niter); } - niter->additional_info = boolean_true_node; niter->assumptions = simplify_using_initial_conditions (loop, - niter->assumptions, - &niter->additional_info); + niter->assumptions); niter->may_be_zero = simplify_using_initial_conditions (loop, - niter->may_be_zero, - &niter->additional_info); + niter->may_be_zero); fold_undefer_and_ignore_overflow_warnings (); @@ -1469,55 +2207,12 @@ find_loop_niter_by_eval (struct loop *loop, edge *exit) */ -/* Returns true if we can prove that COND ==> VAL >= 0. */ - -static bool -implies_nonnegative_p (tree cond, tree val) -{ - tree type = TREE_TYPE (val); - tree compare; - - if (tree_expr_nonnegative_p (val)) - return true; - - if (integer_nonzerop (cond)) - return false; - - compare = fold_build2 (GE_EXPR, - boolean_type_node, val, build_int_cst (type, 0)); - compare = tree_simplify_using_condition_1 (cond, compare); - - return integer_nonzerop (compare); -} - -/* Returns true if we can prove that COND ==> A >= B. */ - -static bool -implies_ge_p (tree cond, tree a, tree b) -{ - tree compare = fold_build2 (GE_EXPR, boolean_type_node, a, b); - - if (integer_nonzerop (compare)) - return true; - - if (integer_nonzerop (cond)) - return false; - - compare = tree_simplify_using_condition_1 (cond, compare); - - return integer_nonzerop (compare); -} - /* Returns a constant upper bound on the value of expression VAL. VAL is considered to be unsigned. If its type is signed, its value must - be nonnegative. - - The condition ADDITIONAL must be satisfied (for example, if VAL is - "(unsigned) n" and ADDITIONAL is "n > 0", then we can derive that - VAL is at most (unsigned) MAX_INT). */ + be nonnegative. */ static double_int -derive_constant_upper_bound (tree val, tree additional) +derive_constant_upper_bound (tree val) { tree type = TREE_TYPE (val); tree op0, op1, subtype, maxt; @@ -1544,7 +2239,7 @@ derive_constant_upper_bound (tree val, tree additional) /* If TYPE is also signed, the fact that VAL is nonnegative implies that OP0 is nonnegative. */ && TYPE_UNSIGNED (type) - && !implies_nonnegative_p (additional, op0)) + && !tree_expr_nonnegative_p (op0)) { /* If we cannot prove that the casted expression is nonnegative, we cannot establish more useful upper bound than the precision @@ -1554,7 +2249,7 @@ derive_constant_upper_bound (tree val, tree additional) /* We now know that op0 is an nonnegative value. Try deriving an upper bound for it. */ - bnd = derive_constant_upper_bound (op0, additional); + bnd = derive_constant_upper_bound (op0); /* If the bound does not fit in TYPE, max. value of TYPE could be attained. */ @@ -1569,7 +2264,7 @@ derive_constant_upper_bound (tree val, tree additional) op1 = TREE_OPERAND (val, 1); if (TREE_CODE (op1) != INTEGER_CST - || !implies_nonnegative_p (additional, op0)) + || !tree_expr_nonnegative_p (op0)) return max; /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to @@ -1580,7 +2275,7 @@ derive_constant_upper_bound (tree val, tree additional) if (TREE_CODE (val) == PLUS_EXPR) cst = double_int_neg (cst); - bnd = derive_constant_upper_bound (op0, additional); + bnd = derive_constant_upper_bound (op0); if (double_int_negative_p (cst)) { @@ -1611,15 +2306,18 @@ derive_constant_upper_bound (tree val, tree additional) */ /* This should only happen if the type is unsigned; however, for - programs that use overflowing signed arithmetics even with + buggy programs that use overflowing signed arithmetics even with -fno-wrapv, this condition may also be true for signed values. */ if (double_int_ucmp (bnd, cst) < 0) return max; - if (TYPE_UNSIGNED (type) - && !implies_ge_p (additional, - op0, double_int_to_tree (type, cst))) - return max; + if (TYPE_UNSIGNED (type)) + { + tree tem = fold_binary (GE_EXPR, boolean_type_node, op0, + double_int_to_tree (type, cst)); + if (!tem || integer_nonzerop (tem)) + return max; + } bnd = double_int_add (bnd, double_int_neg (cst)); } @@ -1634,7 +2332,7 @@ derive_constant_upper_bound (tree val, tree additional) || tree_int_cst_sign_bit (op1)) return max; - bnd = derive_constant_upper_bound (op0, additional); + bnd = derive_constant_upper_bound (op0); return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR); case BIT_AND_EXPR: @@ -1649,27 +2347,25 @@ derive_constant_upper_bound (tree val, tree additional) if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT || GIMPLE_STMT_OPERAND (stmt, 0) != val) return max; - return derive_constant_upper_bound (GIMPLE_STMT_OPERAND (stmt, 1), - additional); + return derive_constant_upper_bound (GIMPLE_STMT_OPERAND (stmt, 1)); default: return max; } } -/* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. The - additional condition ADDITIONAL is recorded with the bound. IS_EXIT +/* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT is true if the loop is exited immediately after STMT, and this exit is taken at last when the STMT is executed BOUND + 1 times. REALISTIC is true if the estimate comes from a reliable source - (number of iterations analysis, or size of data accessed in the loop). */ + (number of iterations analysis, or size of data accessed in the loop). + I_BOUND is an unsigned double_int upper estimate on BOUND. */ static void -record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt, - bool is_exit, bool realistic) +record_estimate (struct loop *loop, tree bound, double_int i_bound, + tree at_stmt, bool is_exit, bool realistic) { struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound)); - double_int i_bound = derive_constant_upper_bound (bound, additional); if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -1701,6 +2397,7 @@ record_nonwrapping_iv (struct loop *loop, tree base, tree step, tree stmt, { tree niter_bound, extreme, delta; tree type = TREE_TYPE (base), unsigned_type; + double_int max; if (TREE_CODE (step) != INTEGER_CST || integer_zerop (step)) return; @@ -1741,8 +2438,8 @@ record_nonwrapping_iv (struct loop *loop, tree base, tree step, tree stmt, /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value would get out of the range. */ niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step); - record_estimate (loop, niter_bound, boolean_true_node, stmt, - false, data_size_bounds_p); + max = derive_constant_upper_bound (niter_bound); + record_estimate (loop, niter_bound, max, stmt, false, data_size_bounds_p); } /* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe @@ -2065,8 +2762,7 @@ estimate_numbers_of_iterations_loop (struct loop *loop) niter = build3 (COND_EXPR, type, niter_desc.may_be_zero, build_int_cst (type, 0), niter); - record_estimate (loop, niter, - niter_desc.additional_info, + record_estimate (loop, niter, niter_desc.max, last_stmt (ex->src), true, true); } diff --git a/gcc/tree.h b/gcc/tree.h index b090770b61f..6cd846d7cc0 100644 --- a/gcc/tree.h +++ b/gcc/tree.h @@ -4481,6 +4481,7 @@ extern enum tree_code invert_tree_comparison (enum tree_code, bool); extern bool tree_expr_nonzero_p (tree); extern bool tree_expr_nonzero_warnv_p (tree, bool *); +extern int multiple_of_p (tree, tree, tree); /* In builtins.c */ extern tree fold_call_expr (tree, bool);