From 554fd8c5195424bdbcabf5de30fdc183aba391bd Mon Sep 17 00:00:00 2001 From: upstream source tree Date: Sun, 15 Mar 2015 20:14:05 -0400 Subject: obtained gcc-4.6.4.tar.bz2 from upstream website; verified gcc-4.6.4.tar.bz2.sig; imported gcc-4.6.4 source tree from verified upstream tarball. downloading a git-generated archive based on the 'upstream' tag should provide you with a source tree that is binary identical to the one extracted from the above tarball. if you have obtained the source via the command 'git clone', however, do note that line-endings of files in your working directory might differ from line-endings of the respective files in the upstream repository. --- gcc/tree-ssa-loop-niter.c | 3260 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 3260 insertions(+) create mode 100644 gcc/tree-ssa-loop-niter.c (limited to 'gcc/tree-ssa-loop-niter.c') diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c new file mode 100644 index 000000000..c14e13c72 --- /dev/null +++ b/gcc/tree-ssa-loop-niter.c @@ -0,0 +1,3260 @@ +/* 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 +. */ + +#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 . 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); +} -- cgit v1.2.3