diff options
author | Dan Albert <danalbert@google.com> | 2015-06-17 11:09:54 -0700 |
---|---|---|
committer | Dan Albert <danalbert@google.com> | 2015-06-17 14:15:22 -0700 |
commit | f378ebf14df0952eae870c9865bab8326aa8f137 (patch) | |
tree | 31794503eb2a8c64ea5f313b93100f1163afcffb /gcc-4.6/gcc/tree-ssa-loop-niter.c | |
parent | 2c58169824949d3a597d9fa81931e001ef9b1bd0 (diff) | |
download | toolchain_gcc-f378ebf14df0952eae870c9865bab8326aa8f137.tar.gz toolchain_gcc-f378ebf14df0952eae870c9865bab8326aa8f137.tar.bz2 toolchain_gcc-f378ebf14df0952eae870c9865bab8326aa8f137.zip |
Delete old versions of GCC.
Change-Id: I710f125d905290e1024cbd67f48299861790c66c
Diffstat (limited to 'gcc-4.6/gcc/tree-ssa-loop-niter.c')
-rw-r--r-- | gcc-4.6/gcc/tree-ssa-loop-niter.c | 3260 |
1 files changed, 0 insertions, 3260 deletions
diff --git a/gcc-4.6/gcc/tree-ssa-loop-niter.c b/gcc-4.6/gcc/tree-ssa-loop-niter.c deleted file mode 100644 index c14e13c72..000000000 --- a/gcc-4.6/gcc/tree-ssa-loop-niter.c +++ /dev/null @@ -1,3260 +0,0 @@ -/* Functions to determine/estimate number of iterations of a loop. - Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010 - 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 3, 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 COPYING3. If not see -<http://www.gnu.org/licenses/>. */ - -#include "config.h" -#include "system.h" -#include "coretypes.h" -#include "tm.h" -#include "tree.h" -#include "tm_p.h" -#include "basic-block.h" -#include "output.h" -#include "tree-pretty-print.h" -#include "gimple-pretty-print.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 "diagnostic-core.h" -#include "tree-inline.h" -#include "gmp.h" - -#define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0) - -/* The maximum number of dominator BBs we search for conditions - of loop header copies we use for simplifying a conditional - expression. */ -#define MAX_DOMINATORS_TO_WALK 8 - -/* - - Analysis of number of iterations of an affine exit test. - -*/ - -/* Bounds on some value, BELOW <= X <= UP. */ - -typedef struct -{ - mpz_t below, up; -} bounds; - - -/* Splits expression EXPR to a variable part VAR and constant OFFSET. */ - -static void -split_to_var_and_offset (tree expr, tree *var, mpz_t offset) -{ - tree type = TREE_TYPE (expr); - tree op0, op1; - double_int off; - bool negate = false; - - *var = expr; - mpz_set_ui (offset, 0); - - switch (TREE_CODE (expr)) - { - case MINUS_EXPR: - negate = true; - /* Fallthru. */ - - case PLUS_EXPR: - case POINTER_PLUS_EXPR: - op0 = TREE_OPERAND (expr, 0); - op1 = TREE_OPERAND (expr, 1); - - if (TREE_CODE (op1) != INTEGER_CST) - break; - - *var = op0; - /* Always sign extend the offset. */ - off = tree_to_double_int (op1); - off = double_int_sext (off, TYPE_PRECISION (type)); - mpz_set_double_int (offset, off, false); - if (negate) - mpz_neg (offset, offset); - break; - - case INTEGER_CST: - *var = build_int_cst_type (type, 0); - off = tree_to_double_int (expr); - mpz_set_double_int (offset, off, TYPE_UNSIGNED (type)); - break; - - default: - break; - } -} - -/* Stores estimate on the minimum/maximum value of the expression VAR + OFF - in TYPE to MIN and MAX. */ - -static void -determine_value_range (tree type, tree var, mpz_t off, - mpz_t min, mpz_t max) -{ - /* If the expression is a constant, we know its value exactly. */ - if (integer_zerop (var)) - { - mpz_set (min, off); - mpz_set (max, off); - return; - } - - /* If the computation may wrap, we know nothing about the value, except for - the range of the type. */ - get_type_static_bounds (type, min, max); - if (!nowrap_type_p (type)) - return; - - /* Since the addition of OFF does not wrap, if OFF is positive, then we may - add it to MIN, otherwise to MAX. */ - if (mpz_sgn (off) < 0) - mpz_add (max, max, off); - else - mpz_add (min, min, off); -} - -/* Stores the bounds on the difference of the values of the expressions - (var + X) and (var + Y), computed in TYPE, to BNDS. */ - -static void -bound_difference_of_offsetted_base (tree type, mpz_t x, mpz_t y, - bounds *bnds) -{ - int rel = mpz_cmp (x, y); - bool may_wrap = !nowrap_type_p (type); - mpz_t m; - - /* If X == Y, then the expressions are always equal. - If X > Y, there are the following possibilities: - a) neither of var + X and var + Y overflow or underflow, or both of - them do. Then their difference is X - Y. - b) var + X overflows, and var + Y does not. Then the values of the - expressions are var + X - M and var + Y, where M is the range of - the type, and their difference is X - Y - M. - c) var + Y underflows and var + X does not. Their difference again - is M - X + Y. - Therefore, if the arithmetics in type does not overflow, then the - bounds are (X - Y, X - Y), otherwise they are (X - Y - M, X - Y) - Similarly, if X < Y, the bounds are either (X - Y, X - Y) or - (X - Y, X - Y + M). */ - - if (rel == 0) - { - mpz_set_ui (bnds->below, 0); - mpz_set_ui (bnds->up, 0); - return; - } - - mpz_init (m); - mpz_set_double_int (m, double_int_mask (TYPE_PRECISION (type)), true); - mpz_add_ui (m, m, 1); - mpz_sub (bnds->up, x, y); - mpz_set (bnds->below, bnds->up); - - if (may_wrap) - { - if (rel > 0) - mpz_sub (bnds->below, bnds->below, m); - else - mpz_add (bnds->up, bnds->up, m); - } - - mpz_clear (m); -} - -/* From condition C0 CMP C1 derives information regarding the - difference of values of VARX + OFFX and VARY + OFFY, computed in TYPE, - and stores it to BNDS. */ - -static void -refine_bounds_using_guard (tree type, tree varx, mpz_t offx, - tree vary, mpz_t offy, - tree c0, enum tree_code cmp, tree c1, - bounds *bnds) -{ - tree varc0, varc1, tmp, ctype; - mpz_t offc0, offc1, loffx, loffy, bnd; - bool lbound = false; - bool no_wrap = nowrap_type_p (type); - bool x_ok, y_ok; - - switch (cmp) - { - case LT_EXPR: - case LE_EXPR: - case GT_EXPR: - case GE_EXPR: - STRIP_SIGN_NOPS (c0); - STRIP_SIGN_NOPS (c1); - ctype = TREE_TYPE (c0); - if (!useless_type_conversion_p (ctype, type)) - return; - - break; - - case EQ_EXPR: - /* We could derive quite precise information from EQ_EXPR, however, such - a guard is unlikely to appear, so we do not bother with handling - it. */ - return; - - case NE_EXPR: - /* NE_EXPR comparisons do not contain much of useful information, except for - special case of comparing with the bounds of the type. */ - if (TREE_CODE (c1) != INTEGER_CST - || !INTEGRAL_TYPE_P (type)) - return; - - /* Ensure that the condition speaks about an expression in the same type - as X and Y. */ - ctype = TREE_TYPE (c0); - if (TYPE_PRECISION (ctype) != TYPE_PRECISION (type)) - return; - c0 = fold_convert (type, c0); - c1 = fold_convert (type, c1); - - if (TYPE_MIN_VALUE (type) - && operand_equal_p (c1, TYPE_MIN_VALUE (type), 0)) - { - cmp = GT_EXPR; - break; - } - if (TYPE_MAX_VALUE (type) - && operand_equal_p (c1, TYPE_MAX_VALUE (type), 0)) - { - cmp = LT_EXPR; - break; - } - - return; - default: - return; - } - - mpz_init (offc0); - mpz_init (offc1); - split_to_var_and_offset (expand_simple_operations (c0), &varc0, offc0); - split_to_var_and_offset (expand_simple_operations (c1), &varc1, offc1); - - /* We are only interested in comparisons of expressions based on VARX and - VARY. TODO -- we might also be able to derive some bounds from - expressions containing just one of the variables. */ - - if (operand_equal_p (varx, varc1, 0)) - { - tmp = varc0; varc0 = varc1; varc1 = tmp; - mpz_swap (offc0, offc1); - cmp = swap_tree_comparison (cmp); - } - - if (!operand_equal_p (varx, varc0, 0) - || !operand_equal_p (vary, varc1, 0)) - goto end; - - mpz_init_set (loffx, offx); - mpz_init_set (loffy, offy); - - if (cmp == GT_EXPR || cmp == GE_EXPR) - { - tmp = varx; varx = vary; vary = tmp; - mpz_swap (offc0, offc1); - mpz_swap (loffx, loffy); - cmp = swap_tree_comparison (cmp); - lbound = true; - } - - /* If there is no overflow, the condition implies that - - (VARX + OFFX) cmp (VARY + OFFY) + (OFFX - OFFY + OFFC1 - OFFC0). - - The overflows and underflows may complicate things a bit; each - overflow decreases the appropriate offset by M, and underflow - increases it by M. The above inequality would not necessarily be - true if - - -- VARX + OFFX underflows and VARX + OFFC0 does not, or - VARX + OFFC0 overflows, but VARX + OFFX does not. - This may only happen if OFFX < OFFC0. - -- VARY + OFFY overflows and VARY + OFFC1 does not, or - VARY + OFFC1 underflows and VARY + OFFY does not. - This may only happen if OFFY > OFFC1. */ - - if (no_wrap) - { - x_ok = true; - y_ok = true; - } - else - { - x_ok = (integer_zerop (varx) - || mpz_cmp (loffx, offc0) >= 0); - y_ok = (integer_zerop (vary) - || mpz_cmp (loffy, offc1) <= 0); - } - - if (x_ok && y_ok) - { - mpz_init (bnd); - mpz_sub (bnd, loffx, loffy); - mpz_add (bnd, bnd, offc1); - mpz_sub (bnd, bnd, offc0); - - if (cmp == LT_EXPR) - mpz_sub_ui (bnd, bnd, 1); - - if (lbound) - { - mpz_neg (bnd, bnd); - if (mpz_cmp (bnds->below, bnd) < 0) - mpz_set (bnds->below, bnd); - } - else - { - if (mpz_cmp (bnd, bnds->up) < 0) - mpz_set (bnds->up, bnd); - } - mpz_clear (bnd); - } - - mpz_clear (loffx); - mpz_clear (loffy); -end: - mpz_clear (offc0); - mpz_clear (offc1); -} - -/* Stores the bounds on the value of the expression X - Y in LOOP to BNDS. - The subtraction is considered to be performed in arbitrary precision, - without overflows. - - We do not attempt to be too clever regarding the value ranges of X and - Y; most of the time, they are just integers or ssa names offsetted by - integer. However, we try to use the information contained in the - comparisons before the loop (usually created by loop header copying). */ - -static void -bound_difference (struct loop *loop, tree x, tree y, bounds *bnds) -{ - tree type = TREE_TYPE (x); - tree varx, vary; - mpz_t offx, offy; - mpz_t minx, maxx, miny, maxy; - int cnt = 0; - edge e; - basic_block bb; - tree c0, c1; - gimple cond; - enum tree_code cmp; - - /* Get rid of unnecessary casts, but preserve the value of - the expressions. */ - STRIP_SIGN_NOPS (x); - STRIP_SIGN_NOPS (y); - - mpz_init (bnds->below); - mpz_init (bnds->up); - mpz_init (offx); - mpz_init (offy); - split_to_var_and_offset (x, &varx, offx); - split_to_var_and_offset (y, &vary, offy); - - if (!integer_zerop (varx) - && operand_equal_p (varx, vary, 0)) - { - /* Special case VARX == VARY -- we just need to compare the - offsets. The matters are a bit more complicated in the - case addition of offsets may wrap. */ - bound_difference_of_offsetted_base (type, offx, offy, bnds); - } - else - { - /* Otherwise, use the value ranges to determine the initial - estimates on below and up. */ - mpz_init (minx); - mpz_init (maxx); - mpz_init (miny); - mpz_init (maxy); - determine_value_range (type, varx, offx, minx, maxx); - determine_value_range (type, vary, offy, miny, maxy); - - mpz_sub (bnds->below, minx, maxy); - mpz_sub (bnds->up, maxx, miny); - mpz_clear (minx); - mpz_clear (maxx); - mpz_clear (miny); - mpz_clear (maxy); - } - - /* If both X and Y are constants, we cannot get any more precise. */ - if (integer_zerop (varx) && integer_zerop (vary)) - goto end; - - /* Now walk the dominators of the loop header and use the entry - guards to refine the estimates. */ - for (bb = loop->header; - bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK; - bb = get_immediate_dominator (CDI_DOMINATORS, bb)) - { - if (!single_pred_p (bb)) - continue; - e = single_pred_edge (bb); - - if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))) - continue; - - cond = last_stmt (e->src); - c0 = gimple_cond_lhs (cond); - cmp = gimple_cond_code (cond); - c1 = gimple_cond_rhs (cond); - - if (e->flags & EDGE_FALSE_VALUE) - cmp = invert_tree_comparison (cmp, false); - - refine_bounds_using_guard (type, varx, offx, vary, offy, - c0, cmp, c1, bnds); - ++cnt; - } - -end: - mpz_clear (offx); - mpz_clear (offy); -} - -/* Update the bounds in BNDS that restrict the value of X to the bounds - that restrict the value of X + DELTA. X can be obtained as a - difference of two values in TYPE. */ - -static void -bounds_add (bounds *bnds, double_int delta, tree type) -{ - mpz_t mdelta, max; - - mpz_init (mdelta); - mpz_set_double_int (mdelta, delta, false); - - mpz_init (max); - mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true); - - mpz_add (bnds->up, bnds->up, mdelta); - mpz_add (bnds->below, bnds->below, mdelta); - - if (mpz_cmp (bnds->up, max) > 0) - mpz_set (bnds->up, max); - - mpz_neg (max, max); - if (mpz_cmp (bnds->below, max) < 0) - mpz_set (bnds->below, max); - - mpz_clear (mdelta); - mpz_clear (max); -} - -/* Update the bounds in BNDS that restrict the value of X to the bounds - that restrict the value of -X. */ - -static void -bounds_negate (bounds *bnds) -{ - mpz_t tmp; - - mpz_init_set (tmp, bnds->up); - mpz_neg (bnds->up, bnds->below); - mpz_neg (bnds->below, tmp); - mpz_clear (tmp); -} - -/* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */ - -static tree -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; -} - -/* Derives the upper bound BND on the number of executions of loop with exit - condition S * i <> C. If NO_OVERFLOW is true, then the control variable of - the loop does not overflow. EXIT_MUST_BE_TAKEN is true if we are guaranteed - that the loop ends through this exit, i.e., the induction variable ever - reaches the value of C. - - The value C is equal to final - base, where final and base are the final and - initial value of the actual induction variable in the analysed loop. BNDS - bounds the value of this difference when computed in signed type with - unbounded range, while the computation of C is performed in an unsigned - type with the range matching the range of the type of the induction variable. - In particular, BNDS.up contains an upper bound on C in the following cases: - -- if the iv must reach its final value without overflow, i.e., if - NO_OVERFLOW && EXIT_MUST_BE_TAKEN is true, or - -- if final >= base, which we know to hold when BNDS.below >= 0. */ - -static void -number_of_iterations_ne_max (mpz_t bnd, bool no_overflow, tree c, tree s, - bounds *bnds, bool exit_must_be_taken) -{ - double_int max; - mpz_t d; - bool bnds_u_valid = ((no_overflow && exit_must_be_taken) - || mpz_sgn (bnds->below) >= 0); - - if (multiple_of_p (TREE_TYPE (c), c, s)) - { - /* If C is an exact multiple of S, then its value will be reached before - the induction variable overflows (unless the loop is exited in some - other way before). Note that the actual induction variable in the - loop (which ranges from base to final instead of from 0 to C) may - overflow, in which case BNDS.up will not be giving a correct upper - bound on C; thus, BNDS_U_VALID had to be computed in advance. */ - no_overflow = true; - exit_must_be_taken = true; - } - - /* If the induction variable can overflow, the number of iterations is at - most the period of the control variable (or infinite, but in that case - the whole # of iterations analysis will fail). */ - if (!no_overflow) - { - max = double_int_mask (TYPE_PRECISION (TREE_TYPE (c)) - - tree_low_cst (num_ending_zeros (s), 1)); - mpz_set_double_int (bnd, max, true); - return; - } - - /* Now we know that the induction variable does not overflow, so the loop - iterates at most (range of type / S) times. */ - mpz_set_double_int (bnd, double_int_mask (TYPE_PRECISION (TREE_TYPE (c))), - true); - - /* If the induction variable is guaranteed to reach the value of C before - overflow, ... */ - if (exit_must_be_taken) - { - /* ... then we can strenghten this to C / S, and possibly we can use - the upper bound on C given by BNDS. */ - if (TREE_CODE (c) == INTEGER_CST) - mpz_set_double_int (bnd, tree_to_double_int (c), true); - else if (bnds_u_valid) - mpz_set (bnd, bnds->up); - } - - mpz_init (d); - mpz_set_double_int (d, tree_to_double_int (s), true); - mpz_fdiv_q (bnd, bnd, d); - mpz_clear (d); -} - -/* Determines number of iterations of loop whose ending condition - is IV <> FINAL. TYPE is the type of the iv. The number of - iterations is stored to NITER. EXIT_MUST_BE_TAKEN 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). BNDS contains the - bounds on the difference FINAL - IV->base. */ - -static bool -number_of_iterations_ne (tree type, affine_iv *iv, tree final, - struct tree_niter_desc *niter, bool exit_must_be_taken, - bounds *bnds) -{ - tree niter_type = unsigned_type_for (type); - tree s, c, d, bits, assumption, tmp, bound; - mpz_t max; - - niter->control = *iv; - niter->bound = final; - niter->cmp = NE_EXPR; - - /* Rearrange the terms so that we get inequality S * i <> C, with S - positive. Also cast everything to the unsigned type. If IV does - not overflow, BNDS bounds the value of C. Also, this is the - case if the computation |FINAL - IV->base| does not overflow, i.e., - if BNDS->below in the result is nonnegative. */ - if (tree_int_cst_sign_bit (iv->step)) - { - s = fold_convert (niter_type, - 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)); - bounds_negate (bnds); - } - 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)); - } - - mpz_init (max); - number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds, - exit_must_be_taken); - niter->max = mpz_get_double_int (niter_type, max, false); - mpz_clear (max); - - /* 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 (!exit_must_be_taken) - { - /* If we cannot assume that the exit is taken eventually, 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 (!integer_nonzerop (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. BNDS bounds the value of IV1->base - IV0->base, - and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is - true if we know that the exit must be taken eventually. */ - -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, - bool exit_must_be_taken, bounds *bnds) -{ - tree niter_type = TREE_TYPE (step); - tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step); - tree tmod; - mpz_t mmod; - tree assumption = boolean_true_node, bound, noloop; - bool ret = false, fv_comp_no_overflow; - tree type1 = type; - if (POINTER_TYPE_P (type)) - type1 = sizetype; - - if (TREE_CODE (mod) != INTEGER_CST) - return false; - if (integer_nonzerop (mod)) - mod = fold_build2 (MINUS_EXPR, niter_type, step, mod); - tmod = fold_convert (type1, mod); - - mpz_init (mmod); - mpz_set_double_int (mmod, tree_to_double_int (mod), true); - mpz_neg (mmod, mmod); - - /* If the induction variable does not overflow and the exit is taken, - then the computation of the final value does not overflow. This is - also obviously the case if the new final value is equal to the - current one. Finally, we postulate this for pointer type variables, - as the code cannot rely on the object to that the pointer points being - placed at the end of the address space (and more pragmatically, - TYPE_{MIN,MAX}_VALUE is not defined for pointers). */ - if (integer_zerop (mod) || POINTER_TYPE_P (type)) - fv_comp_no_overflow = true; - else if (!exit_must_be_taken) - fv_comp_no_overflow = false; - else - fv_comp_no_overflow = - (iv0->no_overflow && integer_nonzerop (iv0->step)) - || (iv1->no_overflow && integer_nonzerop (iv1->step)); - - if (integer_nonzerop (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 (!fv_comp_no_overflow) - { - bound = fold_build2 (MINUS_EXPR, type1, - TYPE_MAX_VALUE (type1), tmod); - assumption = fold_build2 (LE_EXPR, boolean_type_node, - iv1->base, bound); - if (integer_zerop (assumption)) - goto end; - } - if (mpz_cmp (mmod, bnds->below) < 0) - noloop = boolean_false_node; - else if (POINTER_TYPE_P (type)) - noloop = fold_build2 (GT_EXPR, boolean_type_node, - iv0->base, - fold_build2 (POINTER_PLUS_EXPR, type, - iv1->base, tmod)); - else - noloop = fold_build2 (GT_EXPR, boolean_type_node, - iv0->base, - fold_build2 (PLUS_EXPR, type1, - 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 (!fv_comp_no_overflow) - { - bound = fold_build2 (PLUS_EXPR, type1, - TYPE_MIN_VALUE (type1), tmod); - assumption = fold_build2 (GE_EXPR, boolean_type_node, - iv0->base, bound); - if (integer_zerop (assumption)) - goto end; - } - if (mpz_cmp (mmod, bnds->below) < 0) - noloop = boolean_false_node; - else if (POINTER_TYPE_P (type)) - noloop = fold_build2 (GT_EXPR, boolean_type_node, - fold_build2 (POINTER_PLUS_EXPR, type, - iv0->base, - fold_build1 (NEGATE_EXPR, - type1, tmod)), - iv1->base); - else - noloop = fold_build2 (GT_EXPR, boolean_type_node, - fold_build2 (MINUS_EXPR, type1, - iv0->base, tmod), - iv1->base); - } - - if (!integer_nonzerop (assumption)) - niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, - niter->assumptions, - assumption); - if (!integer_zerop (noloop)) - niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, - niter->may_be_zero, - noloop); - bounds_add (bnds, tree_to_double_int (mod), type); - *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod); - - ret = true; -end: - mpz_clear (mmod); - return ret; -} - -/* 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 (integer_nonzerop (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 (integer_zerop (assumption)) - return false; - if (!integer_nonzerop (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. BNDS - bounds the value of IV1->base - IV0->base. */ - -static void -assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1, - struct tree_niter_desc *niter, bounds *bnds) -{ - tree assumption = boolean_true_node, bound, diff; - tree mbz, mbzl, mbzr, type1; - bool rolls_p, no_overflow_p; - double_int dstep; - mpz_t mstep, max; - - /* We are going to compute the number of iterations as - (iv1->base - iv0->base + step - 1) / step, computed in the unsigned - variant of TYPE. This formula only works if - - -step + 1 <= (iv1->base - iv0->base) <= MAX - step + 1 - - (where MAX is the maximum value of the unsigned variant of TYPE, and - the computations in this formula are performed in full precision, - i.e., without overflows). - - Usually, for loops with exit condition iv0->base + step * i < iv1->base, - we have a condition of the form iv0->base - step < iv1->base before the loop, - and for loops iv0->base < iv1->base - step * i the condition - iv0->base < iv1->base + step, due to loop header copying, which enable us - to prove the lower bound. - - The upper bound is more complicated. Unless the expressions for initial - and final value themselves contain enough information, we usually cannot - derive it from the context. */ - - /* First check whether the answer does not follow from the bounds we gathered - before. */ - if (integer_nonzerop (iv0->step)) - dstep = tree_to_double_int (iv0->step); - else - { - dstep = double_int_sext (tree_to_double_int (iv1->step), - TYPE_PRECISION (type)); - dstep = double_int_neg (dstep); - } - - mpz_init (mstep); - mpz_set_double_int (mstep, dstep, true); - mpz_neg (mstep, mstep); - mpz_add_ui (mstep, mstep, 1); - - rolls_p = mpz_cmp (mstep, bnds->below) <= 0; - - mpz_init (max); - mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true); - mpz_add (max, max, mstep); - no_overflow_p = (mpz_cmp (bnds->up, max) <= 0 - /* For pointers, only values lying inside a single object - can be compared or manipulated by pointer arithmetics. - Gcc in general does not allow or handle objects larger - than half of the address space, hence the upper bound - is satisfied for pointers. */ - || POINTER_TYPE_P (type)); - mpz_clear (mstep); - mpz_clear (max); - - if (rolls_p && no_overflow_p) - return; - - type1 = type; - if (POINTER_TYPE_P (type)) - type1 = sizetype; - - /* Now the hard part; we must formulate the assumption(s) as expressions, and - we must be careful not to introduce overflow. */ - - if (integer_nonzerop (iv0->step)) - { - diff = fold_build2 (MINUS_EXPR, type1, - iv0->step, build_int_cst (type1, 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, type1, - 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, type1, - fold_convert (type1, iv0->base), diff); - mbzr = fold_convert (type1, iv1->base); - } - else - { - diff = fold_build2 (PLUS_EXPR, type1, - iv1->step, build_int_cst (type1, 1)); - - if (!POINTER_TYPE_P (type)) - { - bound = fold_build2 (PLUS_EXPR, type1, - TYPE_MAX_VALUE (type), diff); - assumption = fold_build2 (LE_EXPR, boolean_type_node, - iv1->base, bound); - } - - mbzl = fold_convert (type1, iv0->base); - mbzr = fold_build2 (MINUS_EXPR, type1, - fold_convert (type1, iv1->base), diff); - } - - if (!integer_nonzerop (assumption)) - niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, - niter->assumptions, assumption); - if (!rolls_p) - { - mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr); - niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, - niter->may_be_zero, mbz); - } -} - -/* Determines number of iterations of loop whose ending condition - is IV0 < IV1. TYPE is the type of the iv. The number of - iterations is stored to NITER. BNDS bounds the difference - IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know - that the exit must be taken eventually. */ - -static bool -number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1, - struct tree_niter_desc *niter, - bool exit_must_be_taken, bounds *bnds) -{ - tree niter_type = unsigned_type_for (type); - tree delta, step, s; - mpz_t mstep, tmp; - - if (integer_nonzerop (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 ((integer_onep (iv0->step) && integer_zerop (iv1->step)) - || (integer_all_onesp (iv1->step) && integer_zerop (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. - - First try to derive a lower bound on the value of - iv1->base - iv0->base, computed in full precision. If the difference - is nonnegative, we are done, otherwise we must record the - condition. */ - - if (mpz_sgn (bnds->below) < 0) - niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node, - iv1->base, iv0->base); - niter->niter = delta; - niter->max = mpz_get_double_int (niter_type, bnds->up, false); - return true; - } - - if (integer_nonzerop (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, - exit_must_be_taken, bnds)) - { - 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, bnds); - } - - /* 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, bnds); - - s = fold_build2 (MINUS_EXPR, niter_type, - step, build_int_cst (niter_type, 1)); - delta = fold_build2 (PLUS_EXPR, niter_type, delta, s); - niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step); - - mpz_init (mstep); - mpz_init (tmp); - mpz_set_double_int (mstep, tree_to_double_int (step), true); - mpz_add (tmp, bnds->up, mstep); - mpz_sub_ui (tmp, tmp, 1); - mpz_fdiv_q (tmp, tmp, mstep); - niter->max = mpz_get_double_int (niter_type, tmp, false); - mpz_clear (mstep); - mpz_clear (tmp); - - 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. EXIT_MUST_BE_TAKEN 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). BNDS bounds the difference IV1->base - IV0->base. */ - -static bool -number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1, - struct tree_niter_desc *niter, bool exit_must_be_taken, - bounds *bnds) -{ - tree assumption; - tree type1 = type; - if (POINTER_TYPE_P (type)) - type1 = sizetype; - - /* 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. We do not check - this condition for pointer type ivs, as the code cannot rely on - the object to that the pointer points being placed at the end of - the address space (and more pragmatically, TYPE_{MIN,MAX}_VALUE is - not defined for pointers). */ - - if (!exit_must_be_taken && !POINTER_TYPE_P (type)) - { - if (integer_nonzerop (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 (integer_zerop (assumption)) - return false; - if (!integer_nonzerop (assumption)) - niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, - niter->assumptions, assumption); - } - - if (integer_nonzerop (iv0->step)) - { - if (POINTER_TYPE_P (type)) - iv1->base = fold_build2 (POINTER_PLUS_EXPR, type, iv1->base, - build_int_cst (type1, 1)); - else - iv1->base = fold_build2 (PLUS_EXPR, type1, iv1->base, - build_int_cst (type1, 1)); - } - else if (POINTER_TYPE_P (type)) - iv0->base = fold_build2 (POINTER_PLUS_EXPR, type, iv0->base, - fold_build1 (NEGATE_EXPR, type1, - build_int_cst (type1, 1))); - else - iv0->base = fold_build2 (MINUS_EXPR, type1, - iv0->base, build_int_cst (type1, 1)); - - bounds_add (bnds, double_int_one, type1); - - return number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken, - bnds); -} - -/* Dumps description of affine induction variable IV to FILE. */ - -static void -dump_affine_iv (FILE *file, affine_iv *iv) -{ - if (!integer_zerop (iv->step)) - fprintf (file, "["); - - print_generic_expr (dump_file, iv->base, TDF_SLIM); - - if (!integer_zerop (iv->step)) - { - fprintf (file, ", + , "); - print_generic_expr (dump_file, iv->step, TDF_SLIM); - fprintf (file, "]%s", iv->no_overflow ? "(no_overflow)" : ""); - } -} - -/* Determine the number of iterations according to condition (for staying - 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). - - LOOP is the loop whose number of iterations we are determining. - - ONLY_EXIT is true if we are sure this is the only way the loop could be - exited (including possibly non-returning function calls, exceptions, etc.) - -- in this case we can use the information whether the control induction - 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 (struct loop *loop, - tree type, affine_iv *iv0, enum tree_code code, - affine_iv *iv1, struct tree_niter_desc *niter, - bool only_exit) -{ - bool exit_must_be_taken = false, ret; - bounds bnds; - - /* 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->max = double_int_zero; - - 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 && integer_zerop (iv0->step))) - { - SWAP (iv0, iv1); - code = swap_tree_comparison (code); - } - - 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). */ - iv0->no_overflow = true; - iv1->no_overflow = true; - } - - /* If the control induction variable does not overflow and the only exit - from the loop is the one that we analyze, we know it must be taken - eventually. */ - if (only_exit) - { - if (!integer_zerop (iv0->step) && iv0->no_overflow) - exit_must_be_taken = true; - else if (!integer_zerop (iv1->step) && iv1->no_overflow) - exit_must_be_taken = true; - } - - /* 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 (!integer_zerop (iv0->step) && !integer_zerop (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 = build_int_cst (type, 0); - 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 (integer_zerop (iv0->step) && integer_zerop (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 (!integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step)) - return false; - } - - /* If the loop exits immediately, there is nothing to do. */ - if (integer_zerop (fold_build2 (code, boolean_type_node, iv0->base, iv1->base))) - { - niter->niter = build_int_cst (unsigned_type_for (type), 0); - niter->max = double_int_zero; - return true; - } - - /* OK, now we know we have a senseful loop. Handle several cases, depending - on what comparison operator is used. */ - bound_difference (loop, iv1->base, iv0->base, &bnds); - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, - "Analyzing # of iterations of loop %d\n", loop->num); - - fprintf (dump_file, " exit condition "); - dump_affine_iv (dump_file, iv0); - fprintf (dump_file, " %s ", - code == NE_EXPR ? "!=" - : code == LT_EXPR ? "<" - : "<="); - dump_affine_iv (dump_file, iv1); - fprintf (dump_file, "\n"); - - fprintf (dump_file, " bounds on difference of bases: "); - mpz_out_str (dump_file, 10, bnds.below); - fprintf (dump_file, " ... "); - mpz_out_str (dump_file, 10, bnds.up); - fprintf (dump_file, "\n"); - } - - switch (code) - { - case NE_EXPR: - gcc_assert (integer_zerop (iv1->step)); - ret = number_of_iterations_ne (type, iv0, iv1->base, niter, - exit_must_be_taken, &bnds); - break; - - case LT_EXPR: - ret = number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken, - &bnds); - break; - - case LE_EXPR: - ret = number_of_iterations_le (type, iv0, iv1, niter, exit_must_be_taken, - &bnds); - break; - - default: - gcc_unreachable (); - } - - mpz_clear (bnds.up); - mpz_clear (bnds.below); - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - if (ret) - { - fprintf (dump_file, " result:\n"); - if (!integer_nonzerop (niter->assumptions)) - { - fprintf (dump_file, " under assumptions "); - print_generic_expr (dump_file, niter->assumptions, TDF_SLIM); - fprintf (dump_file, "\n"); - } - - if (!integer_zerop (niter->may_be_zero)) - { - fprintf (dump_file, " zero if "); - print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM); - fprintf (dump_file, "\n"); - } - - fprintf (dump_file, " # of iterations "); - print_generic_expr (dump_file, niter->niter, TDF_SLIM); - fprintf (dump_file, ", bounded by "); - dump_double_int (dump_file, niter->max, true); - fprintf (dump_file, "\n"); - } - else - fprintf (dump_file, " failed\n\n"); - } - return ret; -} - -/* Substitute NEW for OLD in EXPR and fold the result. */ - -static tree -simplify_replace_tree (tree expr, tree old, tree new_tree) -{ - unsigned i, n; - tree ret = NULL_TREE, e, se; - - if (!expr) - return NULL_TREE; - - /* Do not bother to replace constants. */ - if (CONSTANT_CLASS_P (old)) - return expr; - - if (expr == old - || operand_equal_p (expr, old, 0)) - return unshare_expr (new_tree); - - if (!EXPR_P (expr)) - return expr; - - n = TREE_OPERAND_LENGTH (expr); - for (i = 0; i < n; i++) - { - e = TREE_OPERAND (expr, i); - se = simplify_replace_tree (e, old, new_tree); - 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, e1; - enum tree_code code; - gimple stmt; - - 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_OPERAND_LENGTH (expr); - 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 (gimple_code (stmt) == GIMPLE_PHI) - { - basic_block src, dest; - - if (gimple_phi_num_args (stmt) != 1) - return expr; - e = PHI_ARG_DEF (stmt, 0); - - /* Avoid propagating through loop exit phi nodes, which - could break loop-closed SSA form restrictions. */ - dest = gimple_bb (stmt); - src = single_pred (dest); - if (TREE_CODE (e) == SSA_NAME - && src->loop_father != dest->loop_father) - return expr; - - return expand_simple_operations (e); - } - if (gimple_code (stmt) != GIMPLE_ASSIGN) - return expr; - - e = gimple_assign_rhs1 (stmt); - code = gimple_assign_rhs_code (stmt); - if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS) - { - if (is_gimple_min_invariant (e)) - return e; - - if (code == SSA_NAME) - return expand_simple_operations (e); - - return expr; - } - - switch (code) - { - CASE_CONVERT: - /* Casts are simple. */ - ee = expand_simple_operations (e); - return fold_build1 (code, TREE_TYPE (expr), ee); - - case PLUS_EXPR: - case MINUS_EXPR: - case POINTER_PLUS_EXPR: - /* And increments and decrements by a constant are simple. */ - e1 = gimple_assign_rhs2 (stmt); - if (!is_gimple_min_invariant (e1)) - return expr; - - ee = expand_simple_operations (e); - return fold_build2 (code, TREE_TYPE (expr), ee, e1); - - default: - return expr; - } -} - -/* 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 (integer_zerop (e) || integer_nonzerop (e)) - return e; - - e = simplify_replace_tree (expr, e1, e0); - if (integer_zerop (e) || integer_nonzerop (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 (integer_zerop (e)) - return e; - e = simplify_replace_tree (cond, e1, e0); - if (integer_zerop (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 (integer_zerop (e)) - return boolean_true_node; - e = simplify_replace_tree (cond, e1, e0); - if (integer_zerop (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 (e && integer_nonzerop (e)) - return e; - - /* Check whether COND ==> not EXPR. */ - e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te); - if (e && integer_zerop (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); -} - -/* Tries to simplify EXPR using the conditions on entry to LOOP. - Returns the simplified expression (or EXPR unchanged, if no - simplification was possible).*/ - -static tree -simplify_using_initial_conditions (struct loop *loop, tree expr) -{ - edge e; - basic_block bb; - gimple stmt; - tree 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; - - stmt = last_stmt (e->src); - cond = fold_build2 (gimple_cond_code (stmt), - boolean_type_node, - gimple_cond_lhs (stmt), - gimple_cond_rhs (stmt)); - if (e->flags & EDGE_FALSE_VALUE) - cond = invert_truthvalue (cond); - expr = tree_simplify_using_condition (cond, expr); - ++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. */ - -bool -loop_only_exit_p (const struct loop *loop, const_edge exit) -{ - basic_block *body; - gimple_stmt_iterator bsi; - unsigned i; - gimple call; - - if (exit != single_exit (loop)) - return false; - - body = get_loop_body (loop); - for (i = 0; i < loop->num_nodes; i++) - { - for (bsi = gsi_start_bb (body[i]); !gsi_end_p (bsi); gsi_next (&bsi)) - { - call = gsi_stmt (bsi); - if (gimple_code (call) != GIMPLE_CALL) - continue; - - if (gimple_has_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) -{ - gimple stmt; - tree 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 || gimple_code (stmt) != GIMPLE_COND) - return false; - - /* We want the condition for staying inside loop. */ - code = gimple_cond_code (stmt); - if (exit->flags & EDGE_TRUE_VALUE) - code = invert_tree_comparison (code, false); - - switch (code) - { - case GT_EXPR: - case GE_EXPR: - case NE_EXPR: - case LT_EXPR: - case LE_EXPR: - break; - - default: - return false; - } - - op0 = gimple_cond_lhs (stmt); - op1 = gimple_cond_rhs (stmt); - type = TREE_TYPE (op0); - - if (TREE_CODE (type) != INTEGER_TYPE - && !POINTER_TYPE_P (type)) - return false; - - if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, false)) - return false; - if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, false)) - return false; - - /* We don't want to see undefined signed overflow warnings while - computing the number 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 (loop, 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->assumptions - = simplify_using_initial_conditions (loop, - niter->assumptions); - niter->may_be_zero - = simplify_using_initial_conditions (loop, - niter->may_be_zero); - - 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) || !single_exit (loop)) - return false; - - if (flag_unsafe_loop_optimizations) - niter->assumptions = boolean_true_node; - - if (warn) - { - const char *wording; - location_t loc = gimple_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 (!integer_zerop (iv1.step) - ? (integer_zerop (iv0.step) - && (integer_onep (iv1.step) || integer_all_onesp (iv1.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"); - - warning_at ((LOCATION_LINE (loc) > 0) ? loc : input_location, - 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 i; - VEC (edge, heap) *exits = get_loop_exit_edges (loop); - edge ex; - tree niter = NULL_TREE, aniter; - struct tree_niter_desc desc; - - *exit = NULL; - FOR_EACH_VEC_ELT (edge, exits, i, ex) - { - if (!just_once_each_iteration_p (loop, ex->src)) - continue; - - if (!number_of_iterations_exit (loop, ex, &desc, false)) - continue; - - if (integer_nonzerop (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 (!integer_zerop (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; - } - } - VEC_free (edge, heap, exits); - - return niter ? niter : chrec_dont_know; -} - -/* Return true if loop is known to have bounded number of iterations. */ - -bool -finite_loop_p (struct loop *loop) -{ - unsigned i; - VEC (edge, heap) *exits; - edge ex; - struct tree_niter_desc desc; - bool finite = false; - int flags; - - if (flag_unsafe_loop_optimizations) - return true; - flags = flags_from_decl_or_type (current_function_decl); - if ((flags & (ECF_CONST|ECF_PURE)) && !(flags & ECF_LOOPING_CONST_OR_PURE)) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "Found loop %i to be finite: it is within pure or const function.\n", - loop->num); - return true; - } - - exits = get_loop_exit_edges (loop); - FOR_EACH_VEC_ELT (edge, exits, i, ex) - { - if (!just_once_each_iteration_p (loop, ex->src)) - continue; - - if (number_of_iterations_exit (loop, ex, &desc, false)) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Found loop %i to be finite: iterating ", loop->num); - print_generic_expr (dump_file, desc.niter, TDF_SLIM); - fprintf (dump_file, " times\n"); - } - finite = true; - break; - } - } - VEC_free (edge, heap, exits); - return finite; -} - -/* - - 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 gimple -chain_of_csts_start (struct loop *loop, tree x) -{ - gimple stmt = SSA_NAME_DEF_STMT (x); - tree use; - basic_block bb = gimple_bb (stmt); - enum tree_code code; - - if (!bb - || !flow_bb_inside_loop_p (loop, bb)) - return NULL; - - if (gimple_code (stmt) == GIMPLE_PHI) - { - if (bb == loop->header) - return stmt; - - return NULL; - } - - if (gimple_code (stmt) != GIMPLE_ASSIGN) - return NULL; - - code = gimple_assign_rhs_code (stmt); - if (gimple_references_memory_p (stmt) - || TREE_CODE_CLASS (code) == tcc_reference - || (code == ADDR_EXPR - && !is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))) - return NULL; - - use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE); - if (use == NULL_TREE) - return NULL; - - 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, otherwise NULL is returned. */ - -static gimple -get_base_for (struct loop *loop, tree x) -{ - gimple phi; - tree init, next; - - if (is_gimple_min_invariant (x)) - return NULL; - - phi = chain_of_csts_start (loop, x); - if (!phi) - return NULL; - - 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; - - if (!is_gimple_min_invariant (init)) - return NULL; - - if (chain_of_csts_start (loop, next) != phi) - return NULL; - - 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) -{ - gimple stmt; - - gcc_assert (is_gimple_min_invariant (base)); - - if (!x) - return base; - - stmt = SSA_NAME_DEF_STMT (x); - if (gimple_code (stmt) == GIMPLE_PHI) - return base; - - gcc_assert (is_gimple_assign (stmt)); - - /* STMT must be either an assignment of a single SSA name or an - expression involving an SSA name and a constant. Try to fold that - expression using the value for the SSA name. */ - if (gimple_assign_ssa_name_copy_p (stmt)) - return get_val_for (gimple_assign_rhs1 (stmt), base); - else if (gimple_assign_rhs_class (stmt) == GIMPLE_UNARY_RHS - && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME) - { - return fold_build1 (gimple_assign_rhs_code (stmt), - gimple_expr_type (stmt), - get_val_for (gimple_assign_rhs1 (stmt), base)); - } - else if (gimple_assign_rhs_class (stmt) == GIMPLE_BINARY_RHS) - { - tree rhs1 = gimple_assign_rhs1 (stmt); - tree rhs2 = gimple_assign_rhs2 (stmt); - if (TREE_CODE (rhs1) == SSA_NAME) - rhs1 = get_val_for (rhs1, base); - else if (TREE_CODE (rhs2) == SSA_NAME) - rhs2 = get_val_for (rhs2, base); - else - gcc_unreachable (); - return fold_build2 (gimple_assign_rhs_code (stmt), - gimple_expr_type (stmt), rhs1, rhs2); - } - else - 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 acnd; - tree op[2], val[2], next[2], aval[2]; - gimple phi, cond; - unsigned i, j; - enum tree_code cmp; - - cond = last_stmt (exit->src); - if (!cond || gimple_code (cond) != GIMPLE_COND) - return chrec_dont_know; - - cmp = gimple_cond_code (cond); - if (exit->flags & EDGE_TRUE_VALUE) - cmp = invert_tree_comparison (cmp, false); - - switch (cmp) - { - case EQ_EXPR: - case NE_EXPR: - case GT_EXPR: - case GE_EXPR: - case LT_EXPR: - case LE_EXPR: - op[0] = gimple_cond_lhs (cond); - op[1] = gimple_cond_rhs (cond); - break; - - default: - return chrec_dont_know; - } - - for (j = 0; j < 2; j++) - { - if (is_gimple_min_invariant (op[j])) - { - val[j] = op[j]; - next[j] = NULL_TREE; - op[j] = NULL_TREE; - } - else - { - phi = get_base_for (loop, op[j]); - if (!phi) - return chrec_dont_know; - val[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop)); - next[j] = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop)); - } - } - - /* 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 && integer_zerop (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 i; - VEC (edge, heap) *exits = get_loop_exit_edges (loop); - edge ex; - tree niter = NULL_TREE, aniter; - - *exit = NULL; - - /* Loops with multiple exits are expensive to handle and less important. */ - if (!flag_expensive_optimizations - && VEC_length (edge, exits) > 1) - return chrec_dont_know; - - FOR_EACH_VEC_ELT (edge, exits, i, ex) - { - 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; - } - VEC_free (edge, heap, exits); - - return niter ? niter : chrec_dont_know; -} - -/* - - Analysis of upper bounds on number of iterations of a loop. - -*/ - -static double_int derive_constant_upper_bound_ops (tree, tree, - enum tree_code, tree); - -/* Returns a constant upper bound on the value of the right-hand side of - an assignment statement STMT. */ - -static double_int -derive_constant_upper_bound_assign (gimple stmt) -{ - enum tree_code code = gimple_assign_rhs_code (stmt); - tree op0 = gimple_assign_rhs1 (stmt); - tree op1 = gimple_assign_rhs2 (stmt); - - return derive_constant_upper_bound_ops (TREE_TYPE (gimple_assign_lhs (stmt)), - op0, code, op1); -} - -/* 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. */ - -static double_int -derive_constant_upper_bound (tree val) -{ - enum tree_code code; - tree op0, op1; - - extract_ops_from_tree (val, &code, &op0, &op1); - return derive_constant_upper_bound_ops (TREE_TYPE (val), op0, code, op1); -} - -/* Returns a constant upper bound on the value of expression OP0 CODE OP1, - whose type is TYPE. The expression is considered to be unsigned. If - its type is signed, its value must be nonnegative. */ - -static double_int -derive_constant_upper_bound_ops (tree type, tree op0, - enum tree_code code, tree op1) -{ - tree subtype, maxt; - double_int bnd, max, mmax, cst; - gimple stmt; - - 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 (code) - { - case INTEGER_CST: - return tree_to_double_int (op0); - - CASE_CONVERT: - 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) - && !tree_expr_nonnegative_p (op0)) - { - /* If we cannot prove that the casted expression is nonnegative, - we cannot establish more useful upper bound than the precision - 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); - - /* 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 POINTER_PLUS_EXPR: - case MINUS_EXPR: - if (TREE_CODE (op1) != INTEGER_CST - || !tree_expr_nonnegative_p (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 (code != MINUS_EXPR) - cst = double_int_neg (cst); - - bnd = derive_constant_upper_bound (op0); - - 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_sub (max, 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 - buggy programs that use overflowing signed arithmetics even with - -fno-wrapv, this condition may also be true for signed values. */ - if (double_int_ucmp (bnd, cst) < 0) - return max; - - if (TYPE_UNSIGNED (type)) - { - tree tem = fold_binary (GE_EXPR, boolean_type_node, op0, - double_int_to_tree (type, cst)); - if (!tem || integer_nonzerop (tem)) - return max; - } - - bnd = double_int_sub (bnd, cst); - } - - return bnd; - - case FLOOR_DIV_EXPR: - case EXACT_DIV_EXPR: - if (TREE_CODE (op1) != INTEGER_CST - || tree_int_cst_sign_bit (op1)) - return max; - - bnd = derive_constant_upper_bound (op0); - return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR); - - case BIT_AND_EXPR: - if (TREE_CODE (op1) != INTEGER_CST - || tree_int_cst_sign_bit (op1)) - return max; - return tree_to_double_int (op1); - - case SSA_NAME: - stmt = SSA_NAME_DEF_STMT (op0); - if (gimple_code (stmt) != GIMPLE_ASSIGN - || gimple_assign_lhs (stmt) != op0) - return max; - return derive_constant_upper_bound_assign (stmt); - - default: - return max; - } -} - -/* Records that every statement in LOOP is executed I_BOUND times. - REALISTIC is true if I_BOUND is expected to be close to the real number - of iterations. UPPER is true if we are sure the loop iterates at most - I_BOUND times. */ - -static void -record_niter_bound (struct loop *loop, double_int i_bound, bool realistic, - bool upper) -{ - /* Update the bounds only when there is no previous estimation, or when the current - estimation is smaller. */ - if (upper - && (!loop->any_upper_bound - || double_int_ucmp (i_bound, loop->nb_iterations_upper_bound) < 0)) - { - loop->any_upper_bound = true; - loop->nb_iterations_upper_bound = i_bound; - } - if (realistic - && (!loop->any_estimate - || double_int_ucmp (i_bound, loop->nb_iterations_estimate) < 0)) - { - loop->any_estimate = true; - loop->nb_iterations_estimate = i_bound; - } -} - -/* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT - is true if the loop is exited immediately after STMT, and this exit - is taken at last when the STMT is executed BOUND + 1 times. - REALISTIC is true if BOUND is expected to be close to the real number - of iterations. UPPER is true if we are sure the loop iterates at most - BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */ - -static void -record_estimate (struct loop *loop, tree bound, double_int i_bound, - gimple at_stmt, bool is_exit, bool realistic, bool upper) -{ - double_int delta; - edge exit; - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : ""); - print_gimple_stmt (dump_file, at_stmt, 0, TDF_SLIM); - fprintf (dump_file, " is %sexecuted at most ", - upper ? "" : "probably "); - print_generic_expr (dump_file, bound, TDF_SLIM); - fprintf (dump_file, " (bounded by "); - dump_double_int (dump_file, i_bound, true); - fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num); - } - - /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the - real number of iterations. */ - if (TREE_CODE (bound) != INTEGER_CST) - realistic = false; - if (!upper && !realistic) - return; - - /* If we have a guaranteed upper bound, record it in the appropriate - list. */ - if (upper) - { - struct nb_iter_bound *elt = ggc_alloc_nb_iter_bound (); - - elt->bound = i_bound; - elt->stmt = at_stmt; - elt->is_exit = is_exit; - elt->next = loop->bounds; - loop->bounds = elt; - } - - /* Update the number of iteration estimates according to the bound. - If at_stmt is an exit, then every statement in the loop is - executed at most BOUND + 1 times. If it is not an exit, then - some of the statements before it could be executed BOUND + 2 - times, if an exit of LOOP is before stmt. */ - exit = single_exit (loop); - if (is_exit - || (exit != NULL - && dominated_by_p (CDI_DOMINATORS, - exit->src, gimple_bb (at_stmt)))) - delta = double_int_one; - else - delta = double_int_two; - i_bound = double_int_add (i_bound, delta); - - /* If an overflow occurred, ignore the result. */ - if (double_int_ucmp (i_bound, delta) < 0) - return; - - record_niter_bound (loop, i_bound, realistic, upper); -} - -/* Record the estimate on number of iterations of LOOP based on the fact that - the induction variable BASE + STEP * i evaluated in STMT does not wrap and - its values belong to the range <LOW, HIGH>. REALISTIC is true if the - estimated number of iterations is expected to be close to the real one. - UPPER is true if we are sure the induction variable does not wrap. */ - -static void -record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple stmt, - tree low, tree high, bool realistic, bool upper) -{ - tree niter_bound, extreme, delta; - tree type = TREE_TYPE (base), unsigned_type; - double_int max; - - if (TREE_CODE (step) != INTEGER_CST || integer_zerop (step)) - return; - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Induction variable ("); - print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM); - fprintf (dump_file, ") "); - print_generic_expr (dump_file, base, TDF_SLIM); - fprintf (dump_file, " + "); - print_generic_expr (dump_file, step, TDF_SLIM); - fprintf (dump_file, " * iteration does not wrap in statement "); - print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); - fprintf (dump_file, " in loop %d.\n", loop->num); - } - - unsigned_type = unsigned_type_for (type); - base = fold_convert (unsigned_type, base); - step = fold_convert (unsigned_type, step); - - if (tree_int_cst_sign_bit (step)) - { - extreme = fold_convert (unsigned_type, low); - if (TREE_CODE (base) != INTEGER_CST) - base = fold_convert (unsigned_type, high); - delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme); - step = fold_build1 (NEGATE_EXPR, unsigned_type, step); - } - else - { - extreme = fold_convert (unsigned_type, high); - if (TREE_CODE (base) != INTEGER_CST) - base = fold_convert (unsigned_type, low); - delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base); - } - - /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value - would get out of the range. */ - niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step); - max = derive_constant_upper_bound (niter_bound); - record_estimate (loop, niter_bound, max, stmt, false, realistic, upper); -} - -/* Returns true if REF is a reference to an array at the end of a dynamically - allocated structure. If this is the case, the array may be allocated larger - than its upper bound implies. */ - -bool -array_at_struct_end_p (tree ref) -{ - tree base = get_base_address (ref); - tree parent, field; - - /* Unless the reference is through a pointer, the size of the array matches - its declaration. */ - if (!base || (!INDIRECT_REF_P (base) && TREE_CODE (base) != MEM_REF)) - return false; - - for (;handled_component_p (ref); ref = parent) - { - parent = TREE_OPERAND (ref, 0); - - if (TREE_CODE (ref) == COMPONENT_REF) - { - /* All fields of a union are at its end. */ - if (TREE_CODE (TREE_TYPE (parent)) == UNION_TYPE) - continue; - - /* Unless the field is at the end of the struct, we are done. */ - field = TREE_OPERAND (ref, 1); - if (DECL_CHAIN (field)) - return false; - } - - /* The other options are ARRAY_REF, ARRAY_RANGE_REF, VIEW_CONVERT_EXPR. - In all these cases, we might be accessing the last element, and - although in practice this will probably never happen, it is legal for - the indices of this last element to exceed the bounds of the array. - Therefore, continue checking. */ - } - - return true; -} - -/* Determine information about number of iterations a LOOP from the index - IDX of a data reference accessed in STMT. RELIABLE is true if STMT is - guaranteed to be executed in every iteration of LOOP. Callback for - for_each_index. */ - -struct ilb_data -{ - struct loop *loop; - gimple stmt; - bool reliable; -}; - -static bool -idx_infer_loop_bounds (tree base, tree *idx, void *dta) -{ - struct ilb_data *data = (struct ilb_data *) dta; - tree ev, init, step; - tree low, high, type, next; - bool sign, upper = data->reliable, at_end = false; - struct loop *loop = data->loop; - - if (TREE_CODE (base) != ARRAY_REF) - return true; - - /* For arrays at the end of the structure, we are not guaranteed that they - do not really extend over their declared size. However, for arrays of - size greater than one, this is unlikely to be intended. */ - if (array_at_struct_end_p (base)) - { - at_end = true; - upper = false; - } - - ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx)); - init = initial_condition (ev); - step = evolution_part_in_loop_num (ev, loop->num); - - if (!init - || !step - || TREE_CODE (step) != INTEGER_CST - || integer_zerop (step) - || tree_contains_chrecs (init, NULL) - || chrec_contains_symbols_defined_in_loop (init, loop->num)) - return true; - - low = array_ref_low_bound (base); - high = array_ref_up_bound (base); - - /* The case of nonconstant bounds could be handled, but it would be - complicated. */ - if (TREE_CODE (low) != INTEGER_CST - || !high - || TREE_CODE (high) != INTEGER_CST) - return true; - sign = tree_int_cst_sign_bit (step); - type = TREE_TYPE (step); - - /* The array of length 1 at the end of a structure most likely extends - beyond its bounds. */ - if (at_end - && operand_equal_p (low, high, 0)) - return true; - - /* In case the relevant bound of the array does not fit in type, or - it does, but bound + step (in type) still belongs into the range of the - array, the index may wrap and still stay within the range of the array - (consider e.g. if the array is indexed by the full range of - unsigned char). - - To make things simpler, we require both bounds to fit into type, although - there are cases where this would not be strictly necessary. */ - if (!int_fits_type_p (high, type) - || !int_fits_type_p (low, type)) - return true; - low = fold_convert (type, low); - high = fold_convert (type, high); - - if (sign) - next = fold_binary (PLUS_EXPR, type, low, step); - else - next = fold_binary (PLUS_EXPR, type, high, step); - - if (tree_int_cst_compare (low, next) <= 0 - && tree_int_cst_compare (next, high) <= 0) - return true; - - record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true, upper); - return true; -} - -/* Determine information about number of iterations a LOOP from the bounds - of arrays in the data reference REF accessed in STMT. RELIABLE is true if - STMT is guaranteed to be executed in every iteration of LOOP.*/ - -static void -infer_loop_bounds_from_ref (struct loop *loop, gimple stmt, tree ref, - bool reliable) -{ - struct ilb_data data; - - data.loop = loop; - data.stmt = stmt; - data.reliable = reliable; - for_each_index (&ref, idx_infer_loop_bounds, &data); -} - -/* Determine information about number of iterations of a LOOP from the way - arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be - executed in every iteration of LOOP. */ - -static void -infer_loop_bounds_from_array (struct loop *loop, gimple stmt, bool reliable) -{ - if (is_gimple_assign (stmt)) - { - tree op0 = gimple_assign_lhs (stmt); - tree op1 = gimple_assign_rhs1 (stmt); - - /* For each memory access, analyze its access function - and record a bound on the loop iteration domain. */ - if (REFERENCE_CLASS_P (op0)) - infer_loop_bounds_from_ref (loop, stmt, op0, reliable); - - if (REFERENCE_CLASS_P (op1)) - infer_loop_bounds_from_ref (loop, stmt, op1, reliable); - } - else if (is_gimple_call (stmt)) - { - tree arg, lhs; - unsigned i, n = gimple_call_num_args (stmt); - - lhs = gimple_call_lhs (stmt); - if (lhs && REFERENCE_CLASS_P (lhs)) - infer_loop_bounds_from_ref (loop, stmt, lhs, reliable); - - for (i = 0; i < n; i++) - { - arg = gimple_call_arg (stmt, i); - if (REFERENCE_CLASS_P (arg)) - infer_loop_bounds_from_ref (loop, stmt, arg, reliable); - } - } -} - -/* Determine information about number of iterations of a LOOP from the fact - that signed arithmetics in STMT does not overflow. */ - -static void -infer_loop_bounds_from_signedness (struct loop *loop, gimple stmt) -{ - tree def, base, step, scev, type, low, high; - - if (gimple_code (stmt) != GIMPLE_ASSIGN) - return; - - def = gimple_assign_lhs (stmt); - - if (TREE_CODE (def) != SSA_NAME) - return; - - type = TREE_TYPE (def); - if (!INTEGRAL_TYPE_P (type) - || !TYPE_OVERFLOW_UNDEFINED (type)) - return; - - scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def)); - if (chrec_contains_undetermined (scev)) - return; - - base = initial_condition_in_loop_num (scev, loop->num); - step = evolution_part_in_loop_num (scev, loop->num); - - if (!base || !step - || TREE_CODE (step) != INTEGER_CST - || tree_contains_chrecs (base, NULL) - || chrec_contains_symbols_defined_in_loop (base, loop->num)) - return; - - low = lower_bound_in_type (type, type); - high = upper_bound_in_type (type, type); - - record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true); -} - -/* 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 *bbs; - gimple_stmt_iterator bsi; - basic_block bb; - bool reliable; - - 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. However, we can use it as a guess. */ - reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb); - - for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) - { - gimple stmt = gsi_stmt (bsi); - - infer_loop_bounds_from_array (loop, stmt, reliable); - - if (reliable) - infer_loop_bounds_from_signedness (loop, stmt); - } - - } - - free (bbs); -} - -/* Converts VAL to double_int. */ - -static double_int -gcov_type_to_double_int (gcov_type val) -{ - double_int ret; - - ret.low = (unsigned HOST_WIDE_INT) val; - /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by - the size of type. */ - val >>= HOST_BITS_PER_WIDE_INT - 1; - val >>= 1; - ret.high = (unsigned HOST_WIDE_INT) val; - - return ret; -} - -/* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P - is true also use estimates derived from undefined behavior. */ - -void -estimate_numbers_of_iterations_loop (struct loop *loop, bool use_undefined_p) -{ - VEC (edge, heap) *exits; - tree niter, type; - unsigned i; - struct tree_niter_desc niter_desc; - edge ex; - double_int bound; - - /* Give up if we already have tried to compute an estimation. */ - if (loop->estimate_state != EST_NOT_COMPUTED) - return; - loop->estimate_state = EST_AVAILABLE; - loop->any_upper_bound = false; - loop->any_estimate = false; - - exits = get_loop_exit_edges (loop); - FOR_EACH_VEC_ELT (edge, exits, i, ex) - { - if (!number_of_iterations_exit (loop, ex, &niter_desc, false)) - continue; - - niter = niter_desc.niter; - type = TREE_TYPE (niter); - if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST) - niter = build3 (COND_EXPR, type, niter_desc.may_be_zero, - build_int_cst (type, 0), - niter); - record_estimate (loop, niter, niter_desc.max, - last_stmt (ex->src), - true, true, true); - } - VEC_free (edge, heap, exits); - - if (use_undefined_p) - infer_loop_bounds_from_undefined (loop); - - /* If we have a measured profile, use it to estimate the number of - iterations. */ - if (loop->header->count != 0) - { - gcov_type nit = expected_loop_iterations_unbounded (loop) + 1; - bound = gcov_type_to_double_int (nit); - record_niter_bound (loop, bound, true, false); - } - - /* If an upper bound is smaller than the realistic estimate of the - number of iterations, use the upper bound instead. */ - if (loop->any_upper_bound - && loop->any_estimate - && double_int_ucmp (loop->nb_iterations_upper_bound, - loop->nb_iterations_estimate) < 0) - loop->nb_iterations_estimate = loop->nb_iterations_upper_bound; -} - -/* Records estimates on numbers of iterations of loops. */ - -void -estimate_numbers_of_iterations (bool use_undefined_p) -{ - loop_iterator li; - struct loop *loop; - - /* We don't want to issue signed overflow warnings while getting - loop iteration estimates. */ - fold_defer_overflow_warnings (); - - FOR_EACH_LOOP (li, loop, 0) - { - estimate_numbers_of_iterations_loop (loop, use_undefined_p); - } - - fold_undefer_and_ignore_overflow_warnings (); -} - -/* Returns true if statement S1 dominates statement S2. */ - -bool -stmt_dominates_stmt_p (gimple s1, gimple s2) -{ - basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2); - - if (!bb1 - || s1 == s2) - return true; - - if (bb1 == bb2) - { - gimple_stmt_iterator bsi; - - if (gimple_code (s2) == GIMPLE_PHI) - return false; - - if (gimple_code (s1) == GIMPLE_PHI) - return true; - - for (bsi = gsi_start_bb (bb1); gsi_stmt (bsi) != s2; gsi_next (&bsi)) - if (gsi_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 bound on - the number of executions of the statement NITER_BOUND->stmt recorded in - NITER_BOUND. If STMT is NULL, we must prove this bound for all - statements in the loop. */ - -static bool -n_of_executions_at_most (gimple stmt, - struct nb_iter_bound *niter_bound, - tree niter) -{ - double_int bound = niter_bound->bound; - tree nit_type = TREE_TYPE (niter), e; - enum tree_code cmp; - - gcc_assert (TYPE_UNSIGNED (nit_type)); - - /* If the bound does not even fit into NIT_TYPE, it cannot tell us that - the number of iterations is small. */ - if (!double_int_fits_to_tree_p (nit_type, bound)) - return false; - - /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1 - times. This means that: - - -- if NITER_BOUND->is_exit is true, then everything before - NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1 - times, and everything after it at most NITER_BOUND->bound times. - - -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT - is executed, then NITER_BOUND->stmt is executed as well in the same - iteration (we conclude that if both statements belong to the same - basic block, or if STMT is after NITER_BOUND->stmt), then STMT - is executed at most NITER_BOUND->bound + 1 times. Otherwise STMT is - executed at most NITER_BOUND->bound + 2 times. */ - - if (niter_bound->is_exit) - { - if (stmt - && stmt != niter_bound->stmt - && stmt_dominates_stmt_p (niter_bound->stmt, stmt)) - cmp = GE_EXPR; - else - cmp = GT_EXPR; - } - else - { - if (!stmt - || (gimple_bb (stmt) != gimple_bb (niter_bound->stmt) - && !stmt_dominates_stmt_p (niter_bound->stmt, stmt))) - { - bound = double_int_add (bound, double_int_one); - if (double_int_zero_p (bound) - || !double_int_fits_to_tree_p (nit_type, bound)) - return false; - } - cmp = GT_EXPR; - } - - e = fold_binary (cmp, boolean_type_node, - niter, double_int_to_tree (nit_type, bound)); - return e && integer_nonzerop (e); -} - -/* 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, - gimple 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)) - return true; - - if (integer_zerop (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 (TREE_TYPE (base))) - return false; - - /* To be able to use estimates on number of iterations of the loop, - we must have an upper bound on the absolute value of the step. */ - if (TREE_CODE (step) != INTEGER_CST) - return true; - - /* 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, true); - 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->estimate_state = EST_NOT_COMPUTED; - for (bound = loop->bounds; bound; bound = next) - { - next = bound->next; - ggc_free (bound); - } - - loop->bounds = NULL; -} - -/* Frees the information on upper bounds on numbers of iterations of loops. */ - -void -free_numbers_of_iterations_estimates (void) -{ - loop_iterator li; - struct loop *loop; - - FOR_EACH_LOOP (li, loop, 0) - { - 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); -} |