diff options
Diffstat (limited to 'gcc/tree-ssa-loop-niter.c')
| -rw-r--r-- | gcc/tree-ssa-loop-niter.c | 2125 |
1 files changed, 2125 insertions, 0 deletions
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c new file mode 100644 index 0000000..429622b --- /dev/null +++ b/gcc/tree-ssa-loop-niter.c @@ -0,0 +1,2125 @@ +/* Functions to determine/estimate number of iterations of a loop. + Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by the +Free Software Foundation; either version 2, or (at your option) any +later version. + +GCC is distributed in the hope that it will be useful, but WITHOUT +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING. If not, write to the Free +Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301, USA. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "tree.h" +#include "rtl.h" +#include "tm_p.h" +#include "hard-reg-set.h" +#include "basic-block.h" +#include "output.h" +#include "diagnostic.h" +#include "intl.h" +#include "tree-flow.h" +#include "tree-dump.h" +#include "cfgloop.h" +#include "tree-pass.h" +#include "ggc.h" +#include "tree-chrec.h" +#include "tree-scalar-evolution.h" +#include "tree-data-ref.h" +#include "params.h" +#include "flags.h" +#include "toplev.h" +#include "tree-inline.h" + +#define SWAP(X, Y) do { void *tmp = (X); (X) = (Y); (Y) = tmp; } while (0) + + +/* + + Analysis of number of iterations of an affine exit test. + +*/ + +/* 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) +{ + 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. */ + +static tree +inverse (tree x, tree mask) +{ + tree type = TREE_TYPE (x); + tree rslt; + unsigned ctr = tree_floor_log2 (mask); + + if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT) + { + unsigned HOST_WIDE_INT ix; + unsigned HOST_WIDE_INT imask; + unsigned HOST_WIDE_INT irslt = 1; + + gcc_assert (cst_and_fits_in_hwi (x)); + gcc_assert (cst_and_fits_in_hwi (mask)); + + ix = int_cst_value (x); + imask = int_cst_value (mask); + + for (; ctr; ctr--) + { + irslt *= ix; + ix *= ix; + } + irslt &= imask; + + rslt = build_int_cst_type (type, irslt); + } + else + { + rslt = build_int_cst (type, 1); + for (; ctr; ctr--) + { + rslt = int_const_binop (MULT_EXPR, rslt, x, 0); + x = int_const_binop (MULT_EXPR, x, x, 0); + } + rslt = int_const_binop (BIT_AND_EXPR, rslt, mask, 0); + } + + return rslt; +} + +/* 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). */ + +static bool +number_of_iterations_ne (tree type, affine_iv *iv, tree final, + struct tree_niter_desc *niter, bool never_infinite) +{ + tree niter_type = unsigned_type_for (type); + tree s, c, d, bits, assumption, tmp, bound; + + 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. */ + if (tree_int_cst_sign_bit (iv->step)) + { + s = fold_convert (niter_type, + fold_build1 (NEGATE_EXPR, type, iv->step)); + c = fold_build2 (MINUS_EXPR, niter_type, + fold_convert (niter_type, iv->base), + fold_convert (niter_type, final)); + } + else + { + s = fold_convert (niter_type, iv->step); + c = fold_build2 (MINUS_EXPR, niter_type, + fold_convert (niter_type, final), + fold_convert (niter_type, iv->base)); + } + + /* First the trivial cases -- when the step is 1. */ + if (integer_onep (s)) + { + niter->niter = c; + return true; + } + + /* 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 (s); + bound = build_low_bits_mask (niter_type, + (TYPE_PRECISION (niter_type) + - tree_low_cst (bits, 1))); + + d = fold_binary_to_constant (LSHIFT_EXPR, niter_type, + build_int_cst (niter_type, 1), bits); + s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits); + + 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, c, d); + assumption = fold_build2 (EQ_EXPR, boolean_type_node, + assumption, build_int_cst (niter_type, 0)); + if (!nonzero_p (assumption)) + niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, + niter->assumptions, assumption); + } + + c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d); + tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound)); + niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound); + return true; +} + +/* Checks whether we can determine the final value of the control variable + of the loop with ending condition IV0 < IV1 (computed in TYPE). + DELTA is the difference IV1->base - IV0->base, STEP is the absolute value + 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. */ + +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 niter_type = TREE_TYPE (step); + tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step); + tree tmod; + tree assumption = boolean_true_node, bound, noloop; + + if (TREE_CODE (mod) != INTEGER_CST) + return false; + if (nonzero_p (mod)) + mod = fold_build2 (MINUS_EXPR, niter_type, step, mod); + tmod = fold_convert (type, mod); + + if (nonzero_p (iv0->step)) + { + /* The final value of the iv is iv1->base + MOD, assuming that this + computation does not overflow, and that + iv0->base <= iv1->base + MOD. */ + if (!iv1->no_overflow && !zero_p (mod)) + { + bound = fold_build2 (MINUS_EXPR, type, + TYPE_MAX_VALUE (type), tmod); + assumption = fold_build2 (LE_EXPR, boolean_type_node, + iv1->base, bound); + if (zero_p (assumption)) + return false; + } + noloop = fold_build2 (GT_EXPR, boolean_type_node, + iv0->base, + fold_build2 (PLUS_EXPR, type, + iv1->base, tmod)); + } + else + { + /* The final value of the iv is iv0->base - MOD, assuming that this + computation does not overflow, and that + iv0->base - MOD <= iv1->base. */ + if (!iv0->no_overflow && !zero_p (mod)) + { + bound = fold_build2 (PLUS_EXPR, type, + TYPE_MIN_VALUE (type), tmod); + assumption = fold_build2 (GE_EXPR, boolean_type_node, + iv0->base, bound); + if (zero_p (assumption)) + return false; + } + noloop = fold_build2 (GT_EXPR, boolean_type_node, + fold_build2 (MINUS_EXPR, type, + iv0->base, tmod), + iv1->base); + } + + if (!nonzero_p (assumption)) + niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, + niter->assumptions, + assumption); + if (!zero_p (noloop)) + niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, + niter->may_be_zero, + noloop); + *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod); + return true; +} + +/* Add assertions to NITER that ensure that the control variable of the loop + with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1 + are TYPE. Returns false if we can prove that there is an overflow, true + otherwise. STEP is the absolute value of the step. */ + +static bool +assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1, + struct tree_niter_desc *niter, tree step) +{ + tree bound, d, assumption, diff; + tree niter_type = TREE_TYPE (step); + + if (nonzero_p (iv0->step)) + { + /* for (i = iv0->base; i < iv1->base; i += iv0->step) */ + if (iv0->no_overflow) + return true; + + /* If iv0->base is a constant, we can determine the last value before + overflow precisely; otherwise we conservatively assume + MAX - STEP + 1. */ + + if (TREE_CODE (iv0->base) == INTEGER_CST) + { + d = fold_build2 (MINUS_EXPR, niter_type, + fold_convert (niter_type, TYPE_MAX_VALUE (type)), + fold_convert (niter_type, iv0->base)); + diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step); + } + else + diff = fold_build2 (MINUS_EXPR, niter_type, step, + build_int_cst (niter_type, 1)); + bound = fold_build2 (MINUS_EXPR, type, + TYPE_MAX_VALUE (type), fold_convert (type, diff)); + assumption = fold_build2 (LE_EXPR, boolean_type_node, + iv1->base, bound); + } + else + { + /* for (i = iv1->base; i > iv0->base; i += iv1->step) */ + if (iv1->no_overflow) + return true; + + if (TREE_CODE (iv1->base) == INTEGER_CST) + { + d = fold_build2 (MINUS_EXPR, niter_type, + fold_convert (niter_type, iv1->base), + fold_convert (niter_type, TYPE_MIN_VALUE (type))); + diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step); + } + else + diff = fold_build2 (MINUS_EXPR, niter_type, step, + build_int_cst (niter_type, 1)); + bound = fold_build2 (PLUS_EXPR, type, + TYPE_MIN_VALUE (type), fold_convert (type, diff)); + assumption = fold_build2 (GE_EXPR, boolean_type_node, + iv0->base, bound); + } + + if (zero_p (assumption)) + return false; + if (!nonzero_p (assumption)) + niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, + niter->assumptions, assumption); + + iv0->no_overflow = true; + iv1->no_overflow = true; + return true; +} + +/* Add an assumption to NITER that a loop whose ending condition + is IV0 < IV1 rolls. TYPE is the type of the control iv. */ + +static void +assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1, + struct tree_niter_desc *niter) +{ + tree assumption = boolean_true_node, bound, diff; + tree mbz, mbzl, mbzr; + + if (nonzero_p (iv0->step)) + { + diff = fold_build2 (MINUS_EXPR, type, + iv0->step, build_int_cst (type, 1)); + + /* We need to know that iv0->base >= MIN + iv0->step - 1. Since + 0 address never belongs to any object, we can assume this for + pointers. */ + if (!POINTER_TYPE_P (type)) + { + bound = fold_build2 (PLUS_EXPR, type, + TYPE_MIN_VALUE (type), diff); + assumption = fold_build2 (GE_EXPR, boolean_type_node, + iv0->base, bound); + } + + /* And then we can compute iv0->base - diff, and compare it with + iv1->base. */ + mbzl = fold_build2 (MINUS_EXPR, type, iv0->base, diff); + mbzr = iv1->base; + } + else + { + diff = fold_build2 (PLUS_EXPR, type, + iv1->step, build_int_cst (type, 1)); + + if (!POINTER_TYPE_P (type)) + { + bound = fold_build2 (PLUS_EXPR, type, + TYPE_MAX_VALUE (type), diff); + assumption = fold_build2 (LE_EXPR, boolean_type_node, + iv1->base, bound); + } + + mbzl = iv0->base; + mbzr = fold_build2 (MINUS_EXPR, type, iv1->base, diff); + } + + mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr); + + if (!nonzero_p (assumption)) + niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, + niter->assumptions, assumption); + if (!zero_p (mbz)) + 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. */ + +static bool +number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1, + struct tree_niter_desc *niter, + bool never_infinite ATTRIBUTE_UNUSED) +{ + tree niter_type = unsigned_type_for (type); + tree delta, step, s; + + if (nonzero_p (iv0->step)) + { + niter->control = *iv0; + niter->cmp = LT_EXPR; + niter->bound = iv1->base; + } + else + { + niter->control = *iv1; + niter->cmp = GT_EXPR; + niter->bound = iv0->base; + } + + delta = fold_build2 (MINUS_EXPR, niter_type, + fold_convert (niter_type, iv1->base), + fold_convert (niter_type, iv0->base)); + + /* First handle the special case that the step is +-1. */ + if ((iv0->step && integer_onep (iv0->step) + && zero_p (iv1->step)) + || (iv1->step && integer_all_onesp (iv1->step) + && zero_p (iv0->step))) + { + /* for (i = iv0->base; i < iv1->base; i++) + + or + + 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); + niter->niter = delta; + return true; + } + + if (nonzero_p (iv0->step)) + step = fold_convert (niter_type, iv0->step); + else + step = fold_convert (niter_type, + fold_build1 (NEGATE_EXPR, type, iv1->step)); + + /* 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)) + { + affine_iv zps; + + zps.base = build_int_cst (niter_type, 0); + zps.step = step; + /* number_of_iterations_lt_to_ne will add assumptions that ensure that + zps does not overflow. */ + zps.no_overflow = true; + + return number_of_iterations_ne (type, &zps, delta, niter, true); + } + + /* Make sure that the control iv does not overflow. */ + if (!assert_no_overflow_lt (type, iv0, iv1, niter, step)) + return false; + + /* 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); + + 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); + return true; +} + +/* 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. 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). */ + +static bool +number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1, + struct tree_niter_desc *niter, bool never_infinite) +{ + tree assumption; + + /* Say that IV0 is the control variable. Then IV0 <= IV1 iff + IV0 < IV1 + 1, assuming that IV1 is not equal to the greatest + value of the type. This we must know anyway, since if it is + equal to this value, the loop rolls forever. */ + + if (!never_infinite) + { + if (nonzero_p (iv0->step)) + assumption = fold_build2 (NE_EXPR, boolean_type_node, + iv1->base, TYPE_MAX_VALUE (type)); + else + assumption = fold_build2 (NE_EXPR, boolean_type_node, + iv0->base, TYPE_MIN_VALUE (type)); + + if (zero_p (assumption)) + return false; + if (!nonzero_p (assumption)) + niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, + niter->assumptions, assumption); + } + + if (nonzero_p (iv0->step)) + iv1->base = fold_build2 (PLUS_EXPR, type, + iv1->base, build_int_cst (type, 1)); + 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); +} + +/* 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 + 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). + + 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 + variables can overflow or not in a more efficient way. + + The results (number of iterations and assumptions as described in + comments at struct tree_niter_desc in tree-flow.h) are stored to NITER. + Returns false if it fails to determine number of iterations, true if it + was determined (possibly with some assumptions). */ + +static bool +number_of_iterations_cond (tree type, affine_iv *iv0, enum tree_code code, + affine_iv *iv1, struct tree_niter_desc *niter, + bool only_exit) +{ + bool never_infinite; + + /* The meaning of these assumptions is this: + if !assumptions + then the rest of information does not have to be valid + if may_be_zero then the loop does not roll, even if + niter != 0. */ + niter->assumptions = boolean_true_node; + niter->may_be_zero = boolean_false_node; + niter->niter = NULL_TREE; + niter->additional_info = boolean_true_node; + + niter->bound = NULL_TREE; + niter->cmp = ERROR_MARK; + + /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that + the control variable is on lhs. */ + if (code == GE_EXPR || code == GT_EXPR + || (code == NE_EXPR && zero_p (iv0->step))) + { + SWAP (iv0, iv1); + code = swap_tree_comparison (code); + } + + if (!only_exit) + { + /* If this is not the only possible exit from the loop, the information + that the induction variables cannot overflow as derived from + signedness analysis cannot be relied upon. We use them e.g. in the + following way: given loop for (i = 0; i <= n; i++), if i is + signed, it cannot overflow, thus this loop is equivalent to + for (i = 0; i < n + 1; i++); however, if n == MAX, but the loop + is exited in some other way before i overflows, this transformation + is incorrect (the new loop exits immediately). */ + iv0->no_overflow = false; + iv1->no_overflow = false; + } + + if (POINTER_TYPE_P (type)) + { + /* Comparison of pointers is undefined unless both iv0 and iv1 point + to the same object. If they do, the control variable cannot wrap + (as wrap around the bounds of memory will never return a pointer + that would be guaranteed to point to the same object, even if we + avoid undefined behavior by casting to size_t and back). The + restrictions on pointer arithmetics and comparisons of pointers + ensure that using the no-overflow assumptions is correct in this + case even if ONLY_EXIT is false. */ + iv0->no_overflow = true; + iv1->no_overflow = true; + } + + /* 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 (iv0->step) && !zero_p (iv1->step)) + { + if (code != NE_EXPR) + return false; + + 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 of the comparison 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 (iv0->step) && zero_p (iv1->step)) + return false; + + /* Ignore loops of while (i-- < 10) type. */ + if (code != NE_EXPR) + { + if (iv0->step && tree_int_cst_sign_bit (iv0->step)) + return false; + + if (!zero_p (iv1->step) && !tree_int_cst_sign_bit (iv1->step)) + return false; + } + + /* If the loop exits immediately, there is nothing to do. */ + if (zero_p (fold_build2 (code, boolean_type_node, iv0->base, iv1->base))) + { + niter->niter = build_int_cst (unsigned_type_for (type), 0); + return true; + } + + /* OK, now we know we have a senseful loop. Handle several cases, depending + on what comparison operator is used. */ + switch (code) + { + case NE_EXPR: + gcc_assert (zero_p (iv1->step)); + return number_of_iterations_ne (type, iv0, iv1->base, niter, never_infinite); + case LT_EXPR: + return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite); + case LE_EXPR: + return number_of_iterations_le (type, iv0, iv1, niter, never_infinite); + default: + gcc_unreachable (); + } +} + +/* Substitute NEW for OLD in EXPR and fold the result. */ + +static tree +simplify_replace_tree (tree expr, tree old, tree new) +{ + unsigned i, n; + tree ret = NULL_TREE, e, se; + + if (!expr) + return NULL_TREE; + + if (expr == old + || operand_equal_p (expr, old, 0)) + return unshare_expr (new); + + if (!EXPR_P (expr)) + return expr; + + n = TREE_CODE_LENGTH (TREE_CODE (expr)); + for (i = 0; i < n; i++) + { + e = TREE_OPERAND (expr, i); + se = simplify_replace_tree (e, old, new); + if (e == se) + continue; + + if (!ret) + ret = copy_node (expr); + + TREE_OPERAND (ret, i) = se; + } + + return (ret ? fold (ret) : expr); +} + +/* Expand definitions of ssa names in EXPR as long as they are simple + enough, and return the new expression. */ + +tree +expand_simple_operations (tree expr) +{ + unsigned i, n; + tree ret = NULL_TREE, e, ee, stmt; + enum tree_code code; + + if (expr == NULL_TREE) + return expr; + + if (is_gimple_min_invariant (expr)) + return expr; + + code = TREE_CODE (expr); + if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code))) + { + n = TREE_CODE_LENGTH (code); + for (i = 0; i < n; i++) + { + e = TREE_OPERAND (expr, i); + ee = expand_simple_operations (e); + if (e == ee) + continue; + + if (!ret) + ret = copy_node (expr); + + TREE_OPERAND (ret, i) = ee; + } + + if (!ret) + return expr; + + fold_defer_overflow_warnings (); + ret = fold (ret); + fold_undefer_and_ignore_overflow_warnings (); + return ret; + } + + if (TREE_CODE (expr) != SSA_NAME) + return expr; + + stmt = SSA_NAME_DEF_STMT (expr); + if (TREE_CODE (stmt) != MODIFY_EXPR) + return expr; + + e = TREE_OPERAND (stmt, 1); + if (/* Casts are simple. */ + TREE_CODE (e) != NOP_EXPR + && TREE_CODE (e) != CONVERT_EXPR + /* Copies are simple. */ + && TREE_CODE (e) != SSA_NAME + /* Assignments of invariants are simple. */ + && !is_gimple_min_invariant (e) + /* And increments and decrements by a constant are simple. */ + && !((TREE_CODE (e) == PLUS_EXPR + || TREE_CODE (e) == MINUS_EXPR) + && is_gimple_min_invariant (TREE_OPERAND (e, 1)))) + return expr; + + return expand_simple_operations (e); +} + +/* Tries to simplify EXPR using the condition COND. Returns the simplified + expression (or EXPR unchanged, if no simplification was possible). */ + +static tree +tree_simplify_using_condition_1 (tree cond, tree expr) +{ + bool changed; + tree e, te, e0, e1, e2, notcond; + enum tree_code code = TREE_CODE (expr); + + if (code == INTEGER_CST) + return expr; + + if (code == TRUTH_OR_EXPR + || code == TRUTH_AND_EXPR + || code == COND_EXPR) + { + changed = false; + + e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0)); + if (TREE_OPERAND (expr, 0) != e0) + changed = true; + + e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1)); + if (TREE_OPERAND (expr, 1) != e1) + changed = true; + + if (code == COND_EXPR) + { + e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2)); + if (TREE_OPERAND (expr, 2) != e2) + changed = true; + } + else + e2 = NULL_TREE; + + if (changed) + { + if (code == COND_EXPR) + expr = fold_build3 (code, boolean_type_node, e0, e1, e2); + else + expr = fold_build2 (code, boolean_type_node, e0, e1); + } + + return expr; + } + + /* In case COND is equality, we may be able to simplify EXPR by copy/constant + propagation, and vice versa. Fold does not handle this, since it is + considered too expensive. */ + if (TREE_CODE (cond) == EQ_EXPR) + { + e0 = TREE_OPERAND (cond, 0); + e1 = TREE_OPERAND (cond, 1); + + /* We know that e0 == e1. Check whether we cannot simplify expr + using this fact. */ + e = simplify_replace_tree (expr, e0, e1); + if (zero_p (e) || nonzero_p (e)) + return e; + + e = simplify_replace_tree (expr, e1, e0); + if (zero_p (e) || nonzero_p (e)) + return e; + } + if (TREE_CODE (expr) == EQ_EXPR) + { + e0 = TREE_OPERAND (expr, 0); + e1 = TREE_OPERAND (expr, 1); + + /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */ + e = simplify_replace_tree (cond, e0, e1); + if (zero_p (e)) + return e; + e = simplify_replace_tree (cond, e1, e0); + if (zero_p (e)) + return e; + } + if (TREE_CODE (expr) == NE_EXPR) + { + e0 = TREE_OPERAND (expr, 0); + e1 = TREE_OPERAND (expr, 1); + + /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */ + e = simplify_replace_tree (cond, e0, e1); + if (zero_p (e)) + return boolean_true_node; + e = simplify_replace_tree (cond, e1, e0); + if (zero_p (e)) + return boolean_true_node; + } + + te = expand_simple_operations (expr); + + /* Check whether COND ==> EXPR. */ + notcond = invert_truthvalue (cond); + e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te); + if (nonzero_p (e)) + return e; + + /* Check whether COND ==> not EXPR. */ + e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te); + if (e && zero_p (e)) + return e; + + return expr; +} + +/* Tries to simplify EXPR using the condition COND. Returns the simplified + expression (or EXPR unchanged, if no simplification was possible). + Wrapper around tree_simplify_using_condition_1 that ensures that chains + of simple operations in definitions of ssa names in COND are expanded, + so that things like casts or incrementing the value of the bound before + the loop do not cause us to fail. */ + +static tree +tree_simplify_using_condition (tree cond, tree expr) +{ + cond = expand_simple_operations (cond); + + 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) +{ + edge e; + basic_block bb; + tree exp, cond; + int cnt = 0; + + if (TREE_CODE (expr) == INTEGER_CST) + return expr; + + /* Limit walking the dominators to avoid quadraticness in + the number of BBs times the number of loops in degenerate + cases. */ + 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 (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; + ++cnt; + } + + return expr; +} + +/* Tries to simplify EXPR using the evolutions of the loop invariants + in the superloops of LOOP. Returns the simplified expression + (or EXPR unchanged, if no simplification was possible). */ + +static tree +simplify_using_outer_evolutions (struct loop *loop, tree expr) +{ + enum tree_code code = TREE_CODE (expr); + bool changed; + tree e, e0, e1, e2; + + if (is_gimple_min_invariant (expr)) + return expr; + + if (code == TRUTH_OR_EXPR + || code == TRUTH_AND_EXPR + || code == COND_EXPR) + { + changed = false; + + e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0)); + if (TREE_OPERAND (expr, 0) != e0) + changed = true; + + e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1)); + if (TREE_OPERAND (expr, 1) != e1) + changed = true; + + if (code == COND_EXPR) + { + e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2)); + if (TREE_OPERAND (expr, 2) != e2) + changed = true; + } + else + e2 = NULL_TREE; + + if (changed) + { + if (code == COND_EXPR) + expr = fold_build3 (code, boolean_type_node, e0, e1, e2); + else + expr = fold_build2 (code, boolean_type_node, e0, e1); + } + + return expr; + } + + e = instantiate_parameters (loop, expr); + if (is_gimple_min_invariant (e)) + return e; + + return expr; +} + +/* Returns true if EXIT is the only possible exit from LOOP. */ + +static bool +loop_only_exit_p (struct loop *loop, edge exit) +{ + basic_block *body; + block_stmt_iterator bsi; + unsigned i; + tree call; + + if (exit != loop->single_exit) + return false; + + body = get_loop_body (loop); + for (i = 0; i < loop->num_nodes; i++) + { + for (bsi = bsi_start (body[0]); !bsi_end_p (bsi); bsi_next (&bsi)) + { + call = get_call_expr_in (bsi_stmt (bsi)); + if (call && TREE_SIDE_EFFECTS (call)) + { + free (body); + return false; + } + } + } + + free (body); + return true; +} + +/* Stores description of number of iterations of LOOP derived from + EXIT (an exit edge of the LOOP) in NITER. Returns true if some + useful information could be derived (and fields of NITER has + meaning described in comments at struct tree_niter_desc + declaration), false otherwise. If WARN is true and + -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use + potentially unsafe assumptions. */ + +bool +number_of_iterations_exit (struct loop *loop, edge exit, + struct tree_niter_desc *niter, + bool warn) +{ + tree stmt, cond, type; + tree op0, op1; + enum tree_code code; + affine_iv iv0, iv1; + + if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src)) + return false; + + niter->assumptions = boolean_false_node; + stmt = last_stmt (exit->src); + if (!stmt || TREE_CODE (stmt) != COND_EXPR) + return false; + + /* We want the condition for staying inside loop. */ + cond = COND_EXPR_COND (stmt); + if (exit->flags & EDGE_TRUE_VALUE) + cond = invert_truthvalue (cond); + + code = TREE_CODE (cond); + switch (code) + { + case GT_EXPR: + case GE_EXPR: + case NE_EXPR: + case LT_EXPR: + case LE_EXPR: + break; + + default: + return false; + } + + op0 = TREE_OPERAND (cond, 0); + op1 = TREE_OPERAND (cond, 1); + type = TREE_TYPE (op0); + + if (TREE_CODE (type) != INTEGER_TYPE + && !POINTER_TYPE_P (type)) + return false; + + if (!simple_iv (loop, stmt, op0, &iv0, false)) + return false; + if (!simple_iv (loop, stmt, op1, &iv1, false)) + return false; + + /* We don't want to see undefined signed overflow warnings while + computing the nmber of iterations. */ + fold_defer_overflow_warnings (); + + iv0.base = expand_simple_operations (iv0.base); + iv1.base = expand_simple_operations (iv1.base); + if (!number_of_iterations_cond (type, &iv0, code, &iv1, niter, + loop_only_exit_p (loop, exit))) + { + fold_undefer_and_ignore_overflow_warnings (); + return false; + } + + if (optimize >= 3) + { + niter->assumptions = simplify_using_outer_evolutions (loop, + niter->assumptions); + niter->may_be_zero = simplify_using_outer_evolutions (loop, + niter->may_be_zero); + niter->niter = simplify_using_outer_evolutions (loop, niter->niter); + } + + niter->additional_info = boolean_true_node; + niter->assumptions + = simplify_using_initial_conditions (loop, + niter->assumptions, + &niter->additional_info); + niter->may_be_zero + = simplify_using_initial_conditions (loop, + niter->may_be_zero, + &niter->additional_info); + + fold_undefer_and_ignore_overflow_warnings (); + + if (integer_onep (niter->assumptions)) + return true; + + /* With -funsafe-loop-optimizations we assume that nothing bad can happen. + But if we can prove that there is overflow or some other source of weird + behavior, ignore the loop even with -funsafe-loop-optimizations. */ + if (integer_zerop (niter->assumptions)) + return false; + + if (flag_unsafe_loop_optimizations) + niter->assumptions = boolean_true_node; + + if (warn) + { + const char *wording; + location_t loc = EXPR_LOCATION (stmt); + + /* We can provide a more specific warning if one of the operator is + constant and the other advances by +1 or -1. */ + 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") + : N_("cannot optimize possibly infinite loops"); + else + wording = + flag_unsafe_loop_optimizations + ? N_("assuming that the loop counter does not overflow") + : N_("cannot optimize loop, the loop counter may overflow"); + + if (LOCATION_LINE (loc) > 0) + warning (OPT_Wunsafe_loop_optimizations, "%H%s", &loc, gettext (wording)); + else + warning (OPT_Wunsafe_loop_optimizations, "%s", gettext (wording)); + } + + return flag_unsafe_loop_optimizations; +} + +/* Try to determine the number of iterations of LOOP. If we succeed, + expression giving number of iterations is returned and *EXIT is + set to the edge from that the information is obtained. Otherwise + chrec_dont_know is returned. */ + +tree +find_loop_niter (struct loop *loop, edge *exit) +{ + unsigned n_exits, i; + edge *exits = get_loop_exit_edges (loop, &n_exits); + edge ex; + tree niter = NULL_TREE, aniter; + struct tree_niter_desc desc; + + *exit = NULL; + for (i = 0; i < n_exits; i++) + { + ex = exits[i]; + if (!just_once_each_iteration_p (loop, ex->src)) + continue; + + if (!number_of_iterations_exit (loop, ex, &desc, false)) + continue; + + if (nonzero_p (desc.may_be_zero)) + { + /* We exit in the first iteration through this exit. + We won't find anything better. */ + niter = build_int_cst (unsigned_type_node, 0); + *exit = ex; + break; + } + + if (!zero_p (desc.may_be_zero)) + continue; + + aniter = desc.niter; + + if (!niter) + { + /* Nothing recorded yet. */ + niter = aniter; + *exit = ex; + continue; + } + + /* Prefer constants, the lower the better. */ + if (TREE_CODE (aniter) != INTEGER_CST) + continue; + + if (TREE_CODE (niter) != INTEGER_CST) + { + niter = aniter; + *exit = ex; + continue; + } + + if (tree_int_cst_lt (aniter, niter)) + { + niter = aniter; + *exit = ex; + continue; + } + } + free (exits); + + return niter ? niter : chrec_dont_know; +} + +/* + + Analysis of a number of iterations of a loop by a brute-force evaluation. + +*/ + +/* Bound on the number of iterations we try to evaluate. */ + +#define MAX_ITERATIONS_TO_TRACK \ + ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK)) + +/* Returns the loop phi node of LOOP such that ssa name X is derived from its + result by a chain of operations such that all but exactly one of their + operands are constants. */ + +static tree +chain_of_csts_start (struct loop *loop, tree x) +{ + tree stmt = SSA_NAME_DEF_STMT (x); + tree use; + basic_block bb = bb_for_stmt (stmt); + + if (!bb + || !flow_bb_inside_loop_p (loop, bb)) + return NULL_TREE; + + if (TREE_CODE (stmt) == PHI_NODE) + { + if (bb == loop->header) + return stmt; + + return NULL_TREE; + } + + if (TREE_CODE (stmt) != MODIFY_EXPR) + return NULL_TREE; + + if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) + return NULL_TREE; + if (SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF) == NULL_DEF_OPERAND_P) + return NULL_TREE; + + use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE); + if (use == NULL_USE_OPERAND_P) + return NULL_TREE; + + return chain_of_csts_start (loop, use); +} + +/* Determines whether the expression X is derived from a result of a phi node + in header of LOOP such that + + * the derivation of X consists only from operations with constants + * the initial value of the phi node is constant + * the value of the phi node in the next iteration can be derived from the + value in the current iteration by a chain of operations with constants. + + If such phi node exists, it is returned. If X is a constant, X is returned + unchanged. Otherwise NULL_TREE is returned. */ + +static tree +get_base_for (struct loop *loop, tree x) +{ + tree phi, init, next; + + if (is_gimple_min_invariant (x)) + return x; + + phi = chain_of_csts_start (loop, x); + if (!phi) + return NULL_TREE; + + init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop)); + next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop)); + + if (TREE_CODE (next) != SSA_NAME) + return NULL_TREE; + + if (!is_gimple_min_invariant (init)) + return NULL_TREE; + + if (chain_of_csts_start (loop, next) != phi) + return NULL_TREE; + + return phi; +} + +/* Given an expression X, then + + * if X is NULL_TREE, we return the constant BASE. + * otherwise X is a SSA name, whose value in the considered loop is derived + by a chain of operations with constant from a result of a phi node in + the header of the loop. Then we return value of X when the value of the + result of this phi node is given by the constant BASE. */ + +static tree +get_val_for (tree x, tree base) +{ + tree stmt, nx, val; + use_operand_p op; + ssa_op_iter iter; + + gcc_assert (is_gimple_min_invariant (base)); + + if (!x) + return base; + + stmt = SSA_NAME_DEF_STMT (x); + if (TREE_CODE (stmt) == PHI_NODE) + return base; + + FOR_EACH_SSA_USE_OPERAND (op, stmt, iter, SSA_OP_USE) + { + nx = USE_FROM_PTR (op); + val = get_val_for (nx, base); + SET_USE (op, val); + val = fold (TREE_OPERAND (stmt, 1)); + SET_USE (op, nx); + /* only iterate loop once. */ + return val; + } + + /* Should never reach here. */ + gcc_unreachable(); +} + +/* Tries to count the number of iterations of LOOP till it exits by EXIT + by brute force -- i.e. by determining the value of the operands of the + condition at EXIT in first few iterations of the loop (assuming that + these values are constant) and determining the first one in that the + condition is not satisfied. Returns the constant giving the number + of the iterations of LOOP if successful, chrec_dont_know otherwise. */ + +tree +loop_niter_by_eval (struct loop *loop, edge exit) +{ + tree cond, cnd, acnd; + tree op[2], val[2], next[2], aval[2], phi[2]; + unsigned i, j; + enum tree_code cmp; + + cond = last_stmt (exit->src); + if (!cond || TREE_CODE (cond) != COND_EXPR) + return chrec_dont_know; + + cnd = COND_EXPR_COND (cond); + if (exit->flags & EDGE_TRUE_VALUE) + cnd = invert_truthvalue (cnd); + + cmp = TREE_CODE (cnd); + switch (cmp) + { + case EQ_EXPR: + case NE_EXPR: + case GT_EXPR: + case GE_EXPR: + case LT_EXPR: + case LE_EXPR: + for (j = 0; j < 2; j++) + op[j] = TREE_OPERAND (cnd, j); + break; + + default: + return chrec_dont_know; + } + + for (j = 0; j < 2; j++) + { + phi[j] = get_base_for (loop, op[j]); + if (!phi[j]) + return chrec_dont_know; + } + + for (j = 0; j < 2; j++) + { + if (TREE_CODE (phi[j]) == PHI_NODE) + { + val[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_preheader_edge (loop)); + next[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_latch_edge (loop)); + } + else + { + val[j] = phi[j]; + next[j] = NULL_TREE; + op[j] = NULL_TREE; + } + } + + /* Don't issue signed overflow warnings. */ + fold_defer_overflow_warnings (); + + for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++) + { + for (j = 0; j < 2; j++) + aval[j] = get_val_for (op[j], val[j]); + + acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]); + if (acnd && zero_p (acnd)) + { + fold_undefer_and_ignore_overflow_warnings (); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "Proved that loop %d iterates %d times using brute force.\n", + loop->num, i); + return build_int_cst (unsigned_type_node, i); + } + + for (j = 0; j < 2; j++) + { + val[j] = get_val_for (next[j], val[j]); + if (!is_gimple_min_invariant (val[j])) + { + fold_undefer_and_ignore_overflow_warnings (); + return chrec_dont_know; + } + } + } + + fold_undefer_and_ignore_overflow_warnings (); + + return chrec_dont_know; +} + +/* Finds the exit of the LOOP by that the loop exits after a constant + number of iterations and stores the exit edge to *EXIT. The constant + giving the number of iterations of LOOP is returned. The number of + iterations is determined using loop_niter_by_eval (i.e. by brute force + evaluation). If we are unable to find the exit for that loop_niter_by_eval + determines the number of iterations, chrec_dont_know is returned. */ + +tree +find_loop_niter_by_eval (struct loop *loop, edge *exit) +{ + unsigned n_exits, i; + edge *exits = get_loop_exit_edges (loop, &n_exits); + edge ex; + tree niter = NULL_TREE, aniter; + + *exit = NULL; + for (i = 0; i < n_exits; i++) + { + ex = exits[i]; + if (!just_once_each_iteration_p (loop, ex->src)) + continue; + + aniter = loop_niter_by_eval (loop, ex); + if (chrec_contains_undetermined (aniter)) + continue; + + if (niter + && !tree_int_cst_lt (aniter, niter)) + continue; + + niter = aniter; + *exit = ex; + } + free (exits); + + return niter ? niter : chrec_dont_know; +} + +/* + + Analysis of upper bounds on number of iterations of a loop. + +*/ + +/* 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 (nonzero_p (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 nonzero_p (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 (nonzero_p (compare)) + return true; + + if (nonzero_p (cond)) + return false; + + compare = tree_simplify_using_condition_1 (cond, compare); + + return nonzero_p (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). */ + +static double_int +derive_constant_upper_bound (tree val, tree additional) +{ + tree type = TREE_TYPE (val); + tree op0, op1, subtype, maxt; + double_int bnd, max, mmax, cst; + + if (INTEGRAL_TYPE_P (type)) + maxt = TYPE_MAX_VALUE (type); + else + maxt = upper_bound_in_type (type, type); + + max = tree_to_double_int (maxt); + + switch (TREE_CODE (val)) + { + case INTEGER_CST: + return tree_to_double_int (val); + + case NOP_EXPR: + case CONVERT_EXPR: + op0 = TREE_OPERAND (val, 0); + subtype = TREE_TYPE (op0); + if (!TYPE_UNSIGNED (subtype) + /* If TYPE is also signed, the fact that VAL is nonnegative implies + that OP0 is nonnegative. */ + && TYPE_UNSIGNED (type) + && !implies_nonnegative_p (additional, op0)) + { + /* If we cannot prove that the casted expression is nonnegative, + we cannot establish more useful upper bound than the precision + of the type gives us. */ + return max; + } + + /* We now know that op0 is an nonnegative value. Try deriving an upper + bound for it. */ + bnd = derive_constant_upper_bound (op0, additional); + + /* If the bound does not fit in TYPE, max. value of TYPE could be + attained. */ + if (double_int_ucmp (max, bnd) < 0) + return max; + + return bnd; + + case PLUS_EXPR: + case MINUS_EXPR: + op0 = TREE_OPERAND (val, 0); + op1 = TREE_OPERAND (val, 1); + + if (TREE_CODE (op1) != INTEGER_CST + || !implies_nonnegative_p (additional, op0)) + return max; + + /* Canonicalize to OP0 - CST. Consider CST to be signed, in order to + choose the most logical way how to treat this constant regardless + of the signedness of the type. */ + cst = tree_to_double_int (op1); + cst = double_int_sext (cst, TYPE_PRECISION (type)); + if (TREE_CODE (val) == PLUS_EXPR) + cst = double_int_neg (cst); + + bnd = derive_constant_upper_bound (op0, additional); + + if (double_int_negative_p (cst)) + { + cst = double_int_neg (cst); + /* Avoid CST == 0x80000... */ + if (double_int_negative_p (cst)) + return max;; + + /* OP0 + CST. We need to check that + BND <= MAX (type) - CST. */ + + mmax = double_int_add (max, double_int_neg (cst)); + if (double_int_ucmp (bnd, mmax) > 0) + return max; + + return double_int_add (bnd, cst); + } + else + { + /* OP0 - CST, where CST >= 0. + + If TYPE is signed, we have already verified that OP0 >= 0, and we + know that the result is nonnegative. This implies that + VAL <= BND - CST. + + If TYPE is unsigned, we must additionally know that OP0 >= CST, + otherwise the operation underflows. + */ + + /* This should only happen if the type is unsigned; however, for + 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; + + bnd = double_int_add (bnd, double_int_neg (cst)); + } + + return bnd; + + case FLOOR_DIV_EXPR: + case EXACT_DIV_EXPR: + op0 = TREE_OPERAND (val, 0); + op1 = TREE_OPERAND (val, 1); + if (TREE_CODE (op1) != INTEGER_CST + || tree_int_cst_sign_bit (op1)) + return max; + + bnd = derive_constant_upper_bound (op0, additional); + return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR); + + default: + return max; + } +} + +/* Records that AT_STMT is executed at most BOUND times in LOOP. The + additional condition ADDITIONAL is recorded with the bound. */ + +void +record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt) +{ + struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound)); + double_int i_bound = derive_constant_upper_bound (bound, additional); + tree c_bound = double_int_to_tree (unsigned_type_for (TREE_TYPE (bound)), + i_bound); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Statements after "); + print_generic_expr (dump_file, at_stmt, TDF_SLIM); + fprintf (dump_file, " are executed at most "); + print_generic_expr (dump_file, bound, TDF_SLIM); + fprintf (dump_file, " (bounded by "); + print_generic_expr (dump_file, c_bound, TDF_SLIM); + fprintf (dump_file, ") times in loop %d.\n", loop->num); + } + + elt->bound = c_bound; + elt->at_stmt = at_stmt; + elt->next = loop->bounds; + loop->bounds = elt; +} + +/* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe + approximation of the number of iterations for LOOP. */ + +static void +compute_estimated_nb_iterations (struct loop *loop) +{ + struct nb_iter_bound *bound; + + for (bound = loop->bounds; bound; bound = bound->next) + { + if (TREE_CODE (bound->bound) != INTEGER_CST) + continue; + + /* Update only when there is no previous estimation, or when the current + estimation is smaller. */ + if (chrec_contains_undetermined (loop->estimated_nb_iterations) + || tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations)) + loop->estimated_nb_iterations = bound->bound; + } +} + +/* The following analyzers are extracting informations on the bounds + of LOOP from the following undefined behaviors: + + - data references should not access elements over the statically + allocated size, + + - signed variables should not overflow when flag_wrapv is not set. +*/ + +static void +infer_loop_bounds_from_undefined (struct loop *loop) +{ + unsigned i; + basic_block bb, *bbs; + block_stmt_iterator bsi; + + bbs = get_loop_body (loop); + + for (i = 0; i < loop->num_nodes; i++) + { + bb = bbs[i]; + + /* If BB is not executed in each iteration of the loop, we cannot + use the operations in it to infer reliable upper bound on the + # of iterations of the loop. */ + if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb)) + continue; + + for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) + { + tree stmt = bsi_stmt (bsi); + + switch (TREE_CODE (stmt)) + { + case MODIFY_EXPR: + { + tree op0 = TREE_OPERAND (stmt, 0); + tree op1 = TREE_OPERAND (stmt, 1); + + /* For each array access, analyze its access function + and record a bound on the loop iteration domain. */ + if (TREE_CODE (op1) == ARRAY_REF + && !array_ref_contains_indirect_ref (op1)) + estimate_iters_using_array (stmt, op1); + + if (TREE_CODE (op0) == ARRAY_REF + && !array_ref_contains_indirect_ref (op0)) + estimate_iters_using_array (stmt, op0); + + /* For each signed type variable in LOOP, analyze its + scalar evolution and record a bound of the loop + based on the type's ranges. */ + else if (!flag_wrapv && TREE_CODE (op0) == SSA_NAME) + { + tree init, step, diff, estimation; + tree scev = instantiate_parameters + (loop, analyze_scalar_evolution (loop, op0)); + tree type = chrec_type (scev); + + if (chrec_contains_undetermined (scev) + || TYPE_OVERFLOW_WRAPS (type)) + break; + + init = initial_condition_in_loop_num (scev, loop->num); + step = evolution_part_in_loop_num (scev, loop->num); + + if (init == NULL_TREE + || step == NULL_TREE + || TREE_CODE (init) != INTEGER_CST + || TREE_CODE (step) != INTEGER_CST + || TYPE_MIN_VALUE (type) == NULL_TREE + || TYPE_MAX_VALUE (type) == NULL_TREE) + break; + + if (integer_nonzerop (step)) + { + tree utype; + + if (tree_int_cst_lt (step, integer_zero_node)) + diff = fold_build2 (MINUS_EXPR, type, init, + TYPE_MIN_VALUE (type)); + else + diff = fold_build2 (MINUS_EXPR, type, + TYPE_MAX_VALUE (type), init); + + utype = unsigned_type_for (type); + estimation = fold_build2 (CEIL_DIV_EXPR, type, diff, + step); + record_estimate (loop, + fold_convert (utype, estimation), + boolean_true_node, stmt); + } + } + + break; + } + + case CALL_EXPR: + { + tree args; + + for (args = TREE_OPERAND (stmt, 1); args; + args = TREE_CHAIN (args)) + if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF + && !array_ref_contains_indirect_ref (TREE_VALUE (args))) + estimate_iters_using_array (stmt, TREE_VALUE (args)); + + break; + } + + default: + break; + } + } + } + + compute_estimated_nb_iterations (loop); + free (bbs); +} + +/* Records estimates on numbers of iterations of LOOP. */ + +static void +estimate_numbers_of_iterations_loop (struct loop *loop) +{ + edge *exits; + tree niter, type; + unsigned i, n_exits; + struct tree_niter_desc niter_desc; + + /* Give up if we already have tried to compute an estimation. */ + if (loop->estimated_nb_iterations == chrec_dont_know + /* Or when we already have an estimation. */ + || (loop->estimated_nb_iterations != NULL_TREE + && TREE_CODE (loop->estimated_nb_iterations) == INTEGER_CST)) + return; + else + loop->estimated_nb_iterations = chrec_dont_know; + + exits = get_loop_exit_edges (loop, &n_exits); + for (i = 0; i < n_exits; i++) + { + if (!number_of_iterations_exit (loop, exits[i], &niter_desc, false)) + continue; + + 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, 0), + niter); + record_estimate (loop, niter, + niter_desc.additional_info, + last_stmt (exits[i]->src)); + } + free (exits); + + if (chrec_contains_undetermined (loop->estimated_nb_iterations)) + infer_loop_bounds_from_undefined (loop); +} + +/* Records estimates on numbers of iterations of LOOPS. */ + +void +estimate_numbers_of_iterations (struct loops *loops) +{ + unsigned i; + struct loop *loop; + + /* We don't want to issue signed overflow warnings while getting + loop iteration estimates. */ + fold_defer_overflow_warnings (); + + for (i = 1; i < loops->num; i++) + { + loop = loops->parray[i]; + if (loop) + estimate_numbers_of_iterations_loop (loop); + } + + fold_undefer_and_ignore_overflow_warnings (); +} + +/* Returns true if statement S1 dominates statement S2. */ + +static bool +stmt_dominates_stmt_p (tree s1, tree s2) +{ + basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2); + + if (!bb1 + || s1 == s2) + return true; + + if (bb1 == bb2) + { + block_stmt_iterator bsi; + + for (bsi = bsi_start (bb1); bsi_stmt (bsi) != s2; bsi_next (&bsi)) + if (bsi_stmt (bsi) == s1) + return true; + + return false; + } + + return dominated_by_p (CDI_DOMINATORS, bb2, bb1); +} + +/* Returns true when we can prove that the number of executions of + STMT in the loop is at most NITER, according to the fact + that the statement NITER_BOUND->at_stmt is executed at most + NITER_BOUND->bound times. */ + +static bool +n_of_executions_at_most (tree stmt, + struct nb_iter_bound *niter_bound, + tree niter) +{ + tree cond; + tree bound = niter_bound->bound; + tree bound_type = TREE_TYPE (bound); + tree nit_type = TREE_TYPE (niter); + enum tree_code cmp; + + gcc_assert (TYPE_UNSIGNED (bound_type) + && TYPE_UNSIGNED (nit_type) + && is_gimple_min_invariant (bound)); + if (TYPE_PRECISION (nit_type) > TYPE_PRECISION (bound_type)) + bound = fold_convert (nit_type, bound); + else + niter = fold_convert (bound_type, niter); + + /* After the statement niter_bound->at_stmt we know that anything is + executed at most BOUND times. */ + if (stmt && stmt_dominates_stmt_p (niter_bound->at_stmt, stmt)) + cmp = GE_EXPR; + /* Before the statement niter_bound->at_stmt we know that anything + is executed at most BOUND + 1 times. */ + else + cmp = GT_EXPR; + + cond = fold_binary (cmp, boolean_type_node, niter, bound); + return nonzero_p (cond); +} + +/* Returns true if the arithmetics in TYPE can be assumed not to wrap. */ + +bool +nowrap_type_p (tree type) +{ + if (INTEGRAL_TYPE_P (type) + && TYPE_OVERFLOW_UNDEFINED (type)) + return true; + + if (POINTER_TYPE_P (type)) + return true; + + return false; +} + +/* Return false only when the induction variable BASE + STEP * I is + known to not overflow: i.e. when the number of iterations is small + enough with respect to the step and initial condition in order to + keep the evolution confined in TYPEs bounds. Return true when the + iv is known to overflow or when the property is not computable. + + USE_OVERFLOW_SEMANTICS is true if this function should assume that + the rules for overflow of the given language apply (e.g., that signed + arithmetics in C does not overflow). */ + +bool +scev_probably_wraps_p (tree base, tree step, + tree at_stmt, struct loop *loop, + bool use_overflow_semantics) +{ + struct nb_iter_bound *bound; + tree delta, step_abs; + tree unsigned_type, valid_niter; + tree type = TREE_TYPE (step); + + /* FIXME: We really need something like + http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html. + + We used to test for the following situation that frequently appears + during address arithmetics: + + D.1621_13 = (long unsigned intD.4) D.1620_12; + D.1622_14 = D.1621_13 * 8; + D.1623_15 = (doubleD.29 *) D.1622_14; + + And derived that the sequence corresponding to D_14 + can be proved to not wrap because it is used for computing a + memory access; however, this is not really the case -- for example, + if D_12 = (unsigned char) [254,+,1], then D_14 has values + 2032, 2040, 0, 8, ..., but the code is still legal. */ + + if (chrec_contains_undetermined (base) + || chrec_contains_undetermined (step) + || TREE_CODE (step) != INTEGER_CST) + return true; + + if (zero_p (step)) + return false; + + /* If we can use the fact that signed and pointer arithmetics does not + wrap, we are done. */ + if (use_overflow_semantics && nowrap_type_p (type)) + return false; + + /* Don't issue signed overflow warnings. */ + fold_defer_overflow_warnings (); + + /* Otherwise, compute the number of iterations before we reach the + bound of the type, and verify that the loop is exited before this + occurs. */ + unsigned_type = unsigned_type_for (type); + base = fold_convert (unsigned_type, base); + + if (tree_int_cst_sign_bit (step)) + { + tree extreme = fold_convert (unsigned_type, + lower_bound_in_type (type, type)); + delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme); + step_abs = fold_build1 (NEGATE_EXPR, unsigned_type, + fold_convert (unsigned_type, step)); + } + else + { + tree extreme = fold_convert (unsigned_type, + upper_bound_in_type (type, type)); + delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base); + step_abs = fold_convert (unsigned_type, step); + } + + valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs); + + estimate_numbers_of_iterations_loop (loop); + for (bound = loop->bounds; bound; bound = bound->next) + { + if (n_of_executions_at_most (at_stmt, bound, valid_niter)) + { + fold_undefer_and_ignore_overflow_warnings (); + return false; + } + } + + fold_undefer_and_ignore_overflow_warnings (); + + /* At this point we still don't have a proof that the iv does not + overflow: give up. */ + return true; +} + +/* Frees the information on upper bounds on numbers of iterations of LOOP. */ + +void +free_numbers_of_iterations_estimates_loop (struct loop *loop) +{ + struct nb_iter_bound *bound, *next; + + loop->nb_iterations = NULL; + loop->estimated_nb_iterations = NULL; + for (bound = loop->bounds; bound; bound = next) + { + next = bound->next; + free (bound); + } + + loop->bounds = NULL; +} + +/* Frees the information on upper bounds on numbers of iterations of LOOPS. */ + +void +free_numbers_of_iterations_estimates (struct loops *loops) +{ + unsigned i; + struct loop *loop; + + for (i = 1; i < loops->num; i++) + { + loop = loops->parray[i]; + if (loop) + free_numbers_of_iterations_estimates_loop (loop); + } +} + +/* Substitute value VAL for ssa name NAME inside expressions held + at LOOP. */ + +void +substitute_in_loop_info (struct loop *loop, tree name, tree val) +{ + loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val); + loop->estimated_nb_iterations + = simplify_replace_tree (loop->estimated_nb_iterations, name, val); +} |
