diff options
Diffstat (limited to 'gcc-4.2.1-5666.3/gcc/tree-ssa-loop-niter.c')
| -rw-r--r-- | gcc-4.2.1-5666.3/gcc/tree-ssa-loop-niter.c | 2125 |
1 files changed, 0 insertions, 2125 deletions
diff --git a/gcc-4.2.1-5666.3/gcc/tree-ssa-loop-niter.c b/gcc-4.2.1-5666.3/gcc/tree-ssa-loop-niter.c deleted file mode 100644 index 429622bcf..000000000 --- a/gcc-4.2.1-5666.3/gcc/tree-ssa-loop-niter.c +++ /dev/null @@ -1,2125 +0,0 @@ -/* 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); -} |