diff options
Diffstat (limited to 'gcc/tree-ssa-loop-niter.cc')
| -rw-r--r-- | gcc/tree-ssa-loop-niter.cc | 5101 |
1 files changed, 5101 insertions, 0 deletions
diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc new file mode 100644 index 0000000..b767056 --- /dev/null +++ b/gcc/tree-ssa-loop-niter.cc @@ -0,0 +1,5101 @@ +/* Functions to determine/estimate number of iterations of a loop. + Copyright (C) 2004-2022 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by the +Free Software Foundation; either version 3, or (at your option) any +later version. + +GCC is distributed in the hope that it will be useful, but WITHOUT +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "rtl.h" +#include "tree.h" +#include "gimple.h" +#include "tree-pass.h" +#include "ssa.h" +#include "gimple-pretty-print.h" +#include "diagnostic-core.h" +#include "stor-layout.h" +#include "fold-const.h" +#include "calls.h" +#include "intl.h" +#include "gimplify.h" +#include "gimple-iterator.h" +#include "tree-cfg.h" +#include "tree-ssa-loop-ivopts.h" +#include "tree-ssa-loop-niter.h" +#include "tree-ssa-loop.h" +#include "cfgloop.h" +#include "tree-chrec.h" +#include "tree-scalar-evolution.h" +#include "tree-dfa.h" +#include "gimple-range.h" + + +/* 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. */ + +struct bounds +{ + mpz_t below, up; +}; + +static bool number_of_iterations_popcount (loop_p loop, edge exit, + enum tree_code code, + class tree_niter_desc *niter); + + +/* 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; + 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. */ + wi::to_mpz (wi::to_wide (op1), offset, SIGNED); + if (negate) + mpz_neg (offset, offset); + break; + + case INTEGER_CST: + *var = build_int_cst_type (type, 0); + wi::to_mpz (wi::to_wide (expr), offset, TYPE_SIGN (type)); + break; + + default: + break; + } +} + +/* From condition C0 CMP C1 derives information regarding the value range + of VAR, which is of TYPE. Results are stored in to BELOW and UP. */ + +static void +refine_value_range_using_guard (tree type, tree var, + tree c0, enum tree_code cmp, tree c1, + mpz_t below, mpz_t up) +{ + tree varc0, varc1, ctype; + mpz_t offc0, offc1; + mpz_t mint, maxt, minc1, maxc1; + bool no_wrap = nowrap_type_p (type); + bool c0_ok, c1_ok; + signop sgn = TYPE_SIGN (type); + + 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 cases of comparing with bounds. */ + 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 (operand_equal_p (var, c0, 0)) + { + mpz_t valc1; + + /* Case of comparing VAR with its below/up bounds. */ + mpz_init (valc1); + wi::to_mpz (wi::to_wide (c1), valc1, TYPE_SIGN (type)); + if (mpz_cmp (valc1, below) == 0) + cmp = GT_EXPR; + if (mpz_cmp (valc1, up) == 0) + cmp = LT_EXPR; + + mpz_clear (valc1); + } + else + { + /* Case of comparing with the bounds of the type. */ + wide_int min = wi::min_value (type); + wide_int max = wi::max_value (type); + + if (wi::to_wide (c1) == min) + cmp = GT_EXPR; + if (wi::to_wide (c1) == max) + cmp = LT_EXPR; + } + + /* Quick return if no useful information. */ + if (cmp == NE_EXPR) + return; + + break; + + 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 VAR. */ + if (operand_equal_p (var, varc1, 0)) + { + std::swap (varc0, varc1); + mpz_swap (offc0, offc1); + cmp = swap_tree_comparison (cmp); + } + else if (!operand_equal_p (var, varc0, 0)) + { + mpz_clear (offc0); + mpz_clear (offc1); + return; + } + + mpz_init (mint); + mpz_init (maxt); + get_type_static_bounds (type, mint, maxt); + mpz_init (minc1); + mpz_init (maxc1); + value_range r; + /* Setup range information for varc1. */ + if (integer_zerop (varc1)) + { + wi::to_mpz (0, minc1, TYPE_SIGN (type)); + wi::to_mpz (0, maxc1, TYPE_SIGN (type)); + } + else if (TREE_CODE (varc1) == SSA_NAME + && INTEGRAL_TYPE_P (type) + && get_range_query (cfun)->range_of_expr (r, varc1) + && r.kind () == VR_RANGE) + { + gcc_assert (wi::le_p (r.lower_bound (), r.upper_bound (), sgn)); + wi::to_mpz (r.lower_bound (), minc1, sgn); + wi::to_mpz (r.upper_bound (), maxc1, sgn); + } + else + { + mpz_set (minc1, mint); + mpz_set (maxc1, maxt); + } + + /* Compute valid range information for varc1 + offc1. Note nothing + useful can be derived if it overflows or underflows. Overflow or + underflow could happen when: + + offc1 > 0 && varc1 + offc1 > MAX_VAL (type) + offc1 < 0 && varc1 + offc1 < MIN_VAL (type). */ + mpz_add (minc1, minc1, offc1); + mpz_add (maxc1, maxc1, offc1); + c1_ok = (no_wrap + || mpz_sgn (offc1) == 0 + || (mpz_sgn (offc1) < 0 && mpz_cmp (minc1, mint) >= 0) + || (mpz_sgn (offc1) > 0 && mpz_cmp (maxc1, maxt) <= 0)); + if (!c1_ok) + goto end; + + if (mpz_cmp (minc1, mint) < 0) + mpz_set (minc1, mint); + if (mpz_cmp (maxc1, maxt) > 0) + mpz_set (maxc1, maxt); + + if (cmp == LT_EXPR) + { + cmp = LE_EXPR; + mpz_sub_ui (maxc1, maxc1, 1); + } + if (cmp == GT_EXPR) + { + cmp = GE_EXPR; + mpz_add_ui (minc1, minc1, 1); + } + + /* Compute range information for varc0. If there is no overflow, + the condition implied that + + (varc0) cmp (varc1 + offc1 - offc0) + + We can possibly improve the upper bound of varc0 if cmp is LE_EXPR, + or the below bound if cmp is GE_EXPR. + + To prove there is no overflow/underflow, we need to check below + four cases: + 1) cmp == LE_EXPR && offc0 > 0 + + (varc0 + offc0) doesn't overflow + && (varc1 + offc1 - offc0) doesn't underflow + + 2) cmp == LE_EXPR && offc0 < 0 + + (varc0 + offc0) doesn't underflow + && (varc1 + offc1 - offc0) doesn't overfloe + + In this case, (varc0 + offc0) will never underflow if we can + prove (varc1 + offc1 - offc0) doesn't overflow. + + 3) cmp == GE_EXPR && offc0 < 0 + + (varc0 + offc0) doesn't underflow + && (varc1 + offc1 - offc0) doesn't overflow + + 4) cmp == GE_EXPR && offc0 > 0 + + (varc0 + offc0) doesn't overflow + && (varc1 + offc1 - offc0) doesn't underflow + + In this case, (varc0 + offc0) will never overflow if we can + prove (varc1 + offc1 - offc0) doesn't underflow. + + Note we only handle case 2 and 4 in below code. */ + + mpz_sub (minc1, minc1, offc0); + mpz_sub (maxc1, maxc1, offc0); + c0_ok = (no_wrap + || mpz_sgn (offc0) == 0 + || (cmp == LE_EXPR + && mpz_sgn (offc0) < 0 && mpz_cmp (maxc1, maxt) <= 0) + || (cmp == GE_EXPR + && mpz_sgn (offc0) > 0 && mpz_cmp (minc1, mint) >= 0)); + if (!c0_ok) + goto end; + + if (cmp == LE_EXPR) + { + if (mpz_cmp (up, maxc1) > 0) + mpz_set (up, maxc1); + } + else + { + if (mpz_cmp (below, minc1) < 0) + mpz_set (below, minc1); + } + +end: + mpz_clear (mint); + mpz_clear (maxt); + mpz_clear (minc1); + mpz_clear (maxc1); + mpz_clear (offc0); + mpz_clear (offc1); +} + +/* Stores estimate on the minimum/maximum value of the expression VAR + OFF + in TYPE to MIN and MAX. */ + +static void +determine_value_range (class loop *loop, tree type, tree var, mpz_t off, + mpz_t min, mpz_t max) +{ + int cnt = 0; + mpz_t minm, maxm; + basic_block bb; + wide_int minv, maxv; + enum value_range_kind rtype = VR_VARYING; + + /* If the expression is a constant, we know its value exactly. */ + if (integer_zerop (var)) + { + mpz_set (min, off); + mpz_set (max, off); + return; + } + + get_type_static_bounds (type, min, max); + + /* See if we have some range info from VRP. */ + if (TREE_CODE (var) == SSA_NAME && INTEGRAL_TYPE_P (type)) + { + edge e = loop_preheader_edge (loop); + signop sgn = TYPE_SIGN (type); + gphi_iterator gsi; + + /* Either for VAR itself... */ + value_range var_range; + get_range_query (cfun)->range_of_expr (var_range, var); + rtype = var_range.kind (); + if (!var_range.undefined_p ()) + { + minv = var_range.lower_bound (); + maxv = var_range.upper_bound (); + } + + /* Or for PHI results in loop->header where VAR is used as + PHI argument from the loop preheader edge. */ + for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gphi *phi = gsi.phi (); + value_range phi_range; + if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var + && get_range_query (cfun)->range_of_expr (phi_range, + gimple_phi_result (phi)) + && phi_range.kind () == VR_RANGE) + { + if (rtype != VR_RANGE) + { + rtype = VR_RANGE; + minv = phi_range.lower_bound (); + maxv = phi_range.upper_bound (); + } + else + { + minv = wi::max (minv, phi_range.lower_bound (), sgn); + maxv = wi::min (maxv, phi_range.upper_bound (), sgn); + /* If the PHI result range are inconsistent with + the VAR range, give up on looking at the PHI + results. This can happen if VR_UNDEFINED is + involved. */ + if (wi::gt_p (minv, maxv, sgn)) + { + value_range vr; + get_range_query (cfun)->range_of_expr (vr, var); + rtype = vr.kind (); + if (!vr.undefined_p ()) + { + minv = vr.lower_bound (); + maxv = vr.upper_bound (); + } + break; + } + } + } + } + mpz_init (minm); + mpz_init (maxm); + if (rtype != VR_RANGE) + { + mpz_set (minm, min); + mpz_set (maxm, max); + } + else + { + gcc_assert (wi::le_p (minv, maxv, sgn)); + wi::to_mpz (minv, minm, sgn); + wi::to_mpz (maxv, maxm, sgn); + } + /* 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_FOR_FN (cfun) && cnt < MAX_DOMINATORS_TO_WALK; + bb = get_immediate_dominator (CDI_DOMINATORS, bb)) + { + edge e; + tree c0, c1; + gimple *cond; + enum tree_code cmp; + + 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_value_range_using_guard (type, var, c0, cmp, c1, minm, maxm); + ++cnt; + } + + mpz_add (minm, minm, off); + mpz_add (maxm, maxm, off); + /* If the computation may not wrap or off is zero, then this + is always fine. If off is negative and minv + off isn't + smaller than type's minimum, or off is positive and + maxv + off isn't bigger than type's maximum, use the more + precise range too. */ + if (nowrap_type_p (type) + || mpz_sgn (off) == 0 + || (mpz_sgn (off) < 0 && mpz_cmp (minm, min) >= 0) + || (mpz_sgn (off) > 0 && mpz_cmp (maxm, max) <= 0)) + { + mpz_set (min, minm); + mpz_set (max, maxm); + mpz_clear (minm); + mpz_clear (maxm); + return; + } + mpz_clear (minm); + mpz_clear (maxm); + } + + /* If the computation may wrap, we know nothing about the value, except for + the range of the type. */ + 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); + wi::to_mpz (wi::minus_one (TYPE_PRECISION (type)), m, UNSIGNED); + 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, 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)) + { + std::swap (varc0, varc1); + 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) + { + std::swap (varx, vary); + 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 (class 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 (loop, type, varx, offx, minx, maxx); + determine_value_range (loop, 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_FOR_FN (cfun) && 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, const widest_int &delta, tree type) +{ + mpz_t mdelta, max; + + mpz_init (mdelta); + wi::to_mpz (delta, mdelta, SIGNED); + + mpz_init (max); + wi::to_mpz (wi::minus_one (TYPE_PRECISION (type)), max, UNSIGNED); + + 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); + x = int_const_binop (MULT_EXPR, x, x); + } + rslt = int_const_binop (BIT_AND_EXPR, rslt, mask); + } + + 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) +{ + widest_int max; + mpz_t d; + tree type = TREE_TYPE (c); + bool bnds_u_valid = ((no_overflow && exit_must_be_taken) + || mpz_sgn (bnds->below) >= 0); + + if (integer_onep (s) + || (TREE_CODE (c) == INTEGER_CST + && TREE_CODE (s) == INTEGER_CST + && wi::mod_trunc (wi::to_wide (c), wi::to_wide (s), + TYPE_SIGN (type)) == 0) + || (TYPE_OVERFLOW_UNDEFINED (type) + && multiple_of_p (type, 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 = wi::mask <widest_int> (TYPE_PRECISION (type) + - wi::ctz (wi::to_wide (s)), false); + wi::to_mpz (max, bnd, UNSIGNED); + return; + } + + /* Now we know that the induction variable does not overflow, so the loop + iterates at most (range of type / S) times. */ + wi::to_mpz (wi::minus_one (TYPE_PRECISION (type)), bnd, UNSIGNED); + + /* If the induction variable is guaranteed to reach the value of C before + overflow, ... */ + if (exit_must_be_taken) + { + /* ... then we can strengthen this to C / S, and possibly we can use + the upper bound on C given by BNDS. */ + if (TREE_CODE (c) == INTEGER_CST) + wi::to_mpz (wi::to_wide (c), bnd, UNSIGNED); + else if (bnds_u_valid) + mpz_set (bnd, bnds->up); + } + + mpz_init (d); + wi::to_mpz (wi::to_wide (s), d, UNSIGNED); + 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 (class loop *loop, tree type, affine_iv *iv, + tree final, class 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 = widest_int::from (wi::from_mpz (niter_type, max, false), + TYPE_SIGN (niter_type)); + mpz_clear (max); + + /* Compute no-overflow information for the control iv. This can be + proven when below two conditions are satisfied: + + 1) IV evaluates toward FINAL at beginning, i.e: + base <= FINAL ; step > 0 + base >= FINAL ; step < 0 + + 2) |FINAL - base| is an exact multiple of step. + + Unfortunately, it's hard to prove above conditions after pass loop-ch + because loop with exit condition (IV != FINAL) usually will be guarded + by initial-condition (IV.base - IV.step != FINAL). In this case, we + can alternatively try to prove below conditions: + + 1') IV evaluates toward FINAL at beginning, i.e: + new_base = base - step < FINAL ; step > 0 + && base - step doesn't underflow + new_base = base - step > FINAL ; step < 0 + && base - step doesn't overflow + + 2') |FINAL - new_base| is an exact multiple of step. + + Please refer to PR34114 as an example of loop-ch's impact, also refer + to PR72817 as an example why condition 2') is necessary. + + Note, for NE_EXPR, base equals to FINAL is a special case, in + which the loop exits immediately, and the iv does not overflow. */ + if (!niter->control.no_overflow + && (integer_onep (s) || multiple_of_p (type, c, s))) + { + tree t, cond, new_c, relaxed_cond = boolean_false_node; + + if (tree_int_cst_sign_bit (iv->step)) + { + cond = fold_build2 (GE_EXPR, boolean_type_node, iv->base, final); + if (TREE_CODE (type) == INTEGER_TYPE) + { + /* Only when base - step doesn't overflow. */ + t = TYPE_MAX_VALUE (type); + t = fold_build2 (PLUS_EXPR, type, t, iv->step); + t = fold_build2 (GE_EXPR, boolean_type_node, t, iv->base); + if (integer_nonzerop (t)) + { + t = fold_build2 (MINUS_EXPR, type, iv->base, iv->step); + new_c = fold_build2 (MINUS_EXPR, niter_type, + fold_convert (niter_type, t), + fold_convert (niter_type, final)); + if (multiple_of_p (type, new_c, s)) + relaxed_cond = fold_build2 (GT_EXPR, boolean_type_node, + t, final); + } + } + } + else + { + cond = fold_build2 (LE_EXPR, boolean_type_node, iv->base, final); + if (TREE_CODE (type) == INTEGER_TYPE) + { + /* Only when base - step doesn't underflow. */ + t = TYPE_MIN_VALUE (type); + t = fold_build2 (PLUS_EXPR, type, t, iv->step); + t = fold_build2 (LE_EXPR, boolean_type_node, t, iv->base); + if (integer_nonzerop (t)) + { + t = fold_build2 (MINUS_EXPR, type, iv->base, iv->step); + new_c = fold_build2 (MINUS_EXPR, niter_type, + fold_convert (niter_type, final), + fold_convert (niter_type, t)); + if (multiple_of_p (type, new_c, s)) + relaxed_cond = fold_build2 (LT_EXPR, boolean_type_node, + t, final); + } + } + } + + t = simplify_using_initial_conditions (loop, cond); + if (!t || !integer_onep (t)) + t = simplify_using_initial_conditions (loop, relaxed_cond); + + if (t && integer_onep (t)) + niter->control.no_overflow = true; + } + + /* First the trivial cases -- when the step is 1. */ + if (integer_onep (s)) + { + niter->niter = c; + return true; + } + if (niter->control.no_overflow && multiple_of_p (type, c, s)) + { + niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, c, s); + 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_to_uhwi (bits))); + + 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); + if (integer_onep (s)) + { + niter->niter = c; + } + else + { + 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, + class 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); + wi::to_mpz (wi::to_wide (mod), mmod, UNSIGNED); + 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_build_pointer_plus (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_build_pointer_plus (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, wi::to_widest (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, + class 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, + class tree_niter_desc *niter, bounds *bnds) +{ + tree assumption = boolean_true_node, bound, diff; + tree mbz, mbzl, mbzr, type1; + bool rolls_p, no_overflow_p; + widest_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 = wi::to_widest (iv0->step); + else + { + dstep = wi::sext (wi::to_widest (iv1->step), TYPE_PRECISION (type)); + dstep = -dstep; + } + + mpz_init (mstep); + wi::to_mpz (dstep, mstep, UNSIGNED); + mpz_neg (mstep, mstep); + mpz_add_ui (mstep, mstep, 1); + + rolls_p = mpz_cmp (mstep, bnds->below) <= 0; + + mpz_init (max); + wi::to_mpz (wi::minus_one (TYPE_PRECISION (type)), max, UNSIGNED); + 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 which likes: {base, -C} < n, or n < {base, C}. + The number of iterations is stored to NITER. */ + +static bool +number_of_iterations_until_wrap (class loop *loop, tree type, affine_iv *iv0, + affine_iv *iv1, class tree_niter_desc *niter) +{ + tree niter_type = unsigned_type_for (type); + tree step, num, assumptions, may_be_zero, span; + wide_int high, low, max, min; + + may_be_zero = fold_build2 (LE_EXPR, boolean_type_node, iv1->base, iv0->base); + if (integer_onep (may_be_zero)) + return false; + + int prec = TYPE_PRECISION (type); + signop sgn = TYPE_SIGN (type); + min = wi::min_value (prec, sgn); + max = wi::max_value (prec, sgn); + + /* n < {base, C}. */ + if (integer_zerop (iv0->step) && !tree_int_cst_sign_bit (iv1->step)) + { + step = iv1->step; + /* MIN + C - 1 <= n. */ + tree last = wide_int_to_tree (type, min + wi::to_wide (step) - 1); + assumptions = fold_build2 (LE_EXPR, boolean_type_node, last, iv0->base); + if (integer_zerop (assumptions)) + return false; + + num = fold_build2 (MINUS_EXPR, niter_type, wide_int_to_tree (type, max), + iv1->base); + + /* When base has the form iv + 1, if we know iv >= n, then iv + 1 < n + only when iv + 1 overflows, i.e. when iv == TYPE_VALUE_MAX. */ + if (sgn == UNSIGNED + && integer_onep (step) + && TREE_CODE (iv1->base) == PLUS_EXPR + && integer_onep (TREE_OPERAND (iv1->base, 1))) + { + tree cond = fold_build2 (GE_EXPR, boolean_type_node, + TREE_OPERAND (iv1->base, 0), iv0->base); + cond = simplify_using_initial_conditions (loop, cond); + if (integer_onep (cond)) + may_be_zero = fold_build2 (EQ_EXPR, boolean_type_node, + TREE_OPERAND (iv1->base, 0), + TYPE_MAX_VALUE (type)); + } + + high = max; + if (TREE_CODE (iv1->base) == INTEGER_CST) + low = wi::to_wide (iv1->base) - 1; + else if (TREE_CODE (iv0->base) == INTEGER_CST) + low = wi::to_wide (iv0->base); + else + low = min; + } + /* {base, -C} < n. */ + else if (tree_int_cst_sign_bit (iv0->step) && integer_zerop (iv1->step)) + { + step = fold_build1 (NEGATE_EXPR, TREE_TYPE (iv0->step), iv0->step); + /* MAX - C + 1 >= n. */ + tree last = wide_int_to_tree (type, max - wi::to_wide (step) + 1); + assumptions = fold_build2 (GE_EXPR, boolean_type_node, last, iv1->base); + if (integer_zerop (assumptions)) + return false; + + num = fold_build2 (MINUS_EXPR, niter_type, iv0->base, + wide_int_to_tree (type, min)); + low = min; + if (TREE_CODE (iv0->base) == INTEGER_CST) + high = wi::to_wide (iv0->base) + 1; + else if (TREE_CODE (iv1->base) == INTEGER_CST) + high = wi::to_wide (iv1->base); + else + high = max; + } + else + return false; + + /* (delta + step - 1) / step */ + step = fold_convert (niter_type, step); + num = fold_convert (niter_type, num); + num = fold_build2 (PLUS_EXPR, niter_type, num, step); + niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, num, step); + + widest_int delta, s; + delta = widest_int::from (high, sgn) - widest_int::from (low, sgn); + s = wi::to_widest (step); + delta = delta + s - 1; + niter->max = wi::udiv_floor (delta, s); + + niter->may_be_zero = may_be_zero; + + if (!integer_nonzerop (assumptions)) + niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, + niter->assumptions, assumptions); + + niter->control.no_overflow = false; + + /* Update bound and exit condition as: + bound = niter * STEP + (IVbase - STEP). + { IVbase - STEP, +, STEP } != bound + Here, biasing IVbase by 1 step makes 'bound' be the value before wrap. + */ + niter->control.base = fold_build2 (MINUS_EXPR, niter_type, + niter->control.base, niter->control.step); + span = fold_build2 (MULT_EXPR, niter_type, niter->niter, + fold_convert (niter_type, niter->control.step)); + niter->bound = fold_build2 (PLUS_EXPR, niter_type, span, + fold_convert (niter_type, niter->control.base)); + niter->bound = fold_convert (type, niter->bound); + niter->cmp = NE_EXPR; + + 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. 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 (class loop *loop, tree type, affine_iv *iv0, + affine_iv *iv1, class 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; + } + + /* {base, -C} < n, or n < {base, C} */ + if (tree_int_cst_sign_bit (iv0->step) + || (!integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step))) + return number_of_iterations_until_wrap (loop, type, iv0, iv1, niter); + + 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 = widest_int::from (wi::from_mpz (niter_type, bnds->up, false), + TYPE_SIGN (niter_type)); + niter->control.no_overflow = true; + 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 (loop, 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); + wi::to_mpz (wi::to_wide (step), mstep, UNSIGNED); + mpz_add (tmp, bnds->up, mstep); + mpz_sub_ui (tmp, tmp, 1); + mpz_fdiv_q (tmp, tmp, mstep); + niter->max = widest_int::from (wi::from_mpz (niter_type, tmp, false), + TYPE_SIGN (niter_type)); + 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 (class loop *loop, tree type, affine_iv *iv0, + affine_iv *iv1, class 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_build_pointer_plus_hwi (iv1->base, 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_build_pointer_plus_hwi (iv0->base, -1); + else + iv0->base = fold_build2 (MINUS_EXPR, type1, + iv0->base, build_int_cst (type1, 1)); + + bounds_add (bnds, 1, type1); + + return number_of_iterations_lt (loop, 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. + + if EVERY_ITERATION is true, we know the test is executed on every iteration. + + The results (number of iterations and assumptions as described in + comments at class tree_niter_desc in tree-ssa-loop.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 (class loop *loop, + tree type, affine_iv *iv0, enum tree_code code, + affine_iv *iv1, class tree_niter_desc *niter, + bool only_exit, bool every_iteration) +{ + bool exit_must_be_taken = false, ret; + bounds bnds; + + /* If the test is not executed every iteration, wrapping may make the test + to pass again. + TODO: the overflow case can be still used as unreliable estimate of upper + bound. But we have no API to pass it down to number of iterations code + and, at present, it will not use it anyway. */ + if (!every_iteration + && (!iv0->no_overflow || !iv1->no_overflow + || code == NE_EXPR || code == EQ_EXPR)) + return false; + + /* 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 = 0; + 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))) + { + std::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 cases which neither of the sides of the comparison is + invariant: + + {iv0.base, iv0.step} cmp_code {iv1.base, iv1.step} + as if: + {iv0.base, iv0.step - iv1.step} cmp_code {iv1.base, 0} + + provided that either below condition is satisfied: + + a) the test is NE_EXPR; + b) iv0.step - iv1.step is integer and iv0/iv1 don't overflow. + + This rarely occurs in practice, but it is simple enough to manage. */ + if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step)) + { + tree step_type = POINTER_TYPE_P (type) ? sizetype : type; + tree step = fold_binary_to_constant (MINUS_EXPR, step_type, + iv0->step, iv1->step); + + /* No need to check sign of the new step since below code takes care + of this well. */ + if (code != NE_EXPR + && (TREE_CODE (step) != INTEGER_CST + || !iv0->no_overflow || !iv1->no_overflow)) + return false; + + iv0->step = step; + if (!POINTER_TYPE_P (type)) + iv0->no_overflow = false; + + iv1->step = build_int_cst (step_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; + + /* If the loop exits immediately, there is nothing to do. */ + tree tem = fold_binary (code, boolean_type_node, iv0->base, iv1->base); + if (tem && integer_zerop (tem)) + { + if (!every_iteration) + return false; + niter->niter = build_int_cst (unsigned_type_for (type), 0); + niter->max = 0; + 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 (loop, type, iv0, iv1->base, niter, + exit_must_be_taken, &bnds); + break; + + case LT_EXPR: + ret = number_of_iterations_lt (loop, type, iv0, iv1, niter, + exit_must_be_taken, &bnds); + break; + + case LE_EXPR: + ret = number_of_iterations_le (loop, 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 "); + print_decu (niter->max, dump_file); + fprintf (dump_file, "\n"); + } + else + fprintf (dump_file, " failed\n\n"); + } + return ret; +} + +/* Substitute NEW_TREE for OLD in EXPR and fold the result. + If VALUEIZE is non-NULL then OLD and NEW_TREE are ignored and instead + all SSA names are replaced with the result of calling the VALUEIZE + function with the SSA name as argument. */ + +tree +simplify_replace_tree (tree expr, tree old, tree new_tree, + tree (*valueize) (tree, void*), void *context, + bool do_fold) +{ + unsigned i, n; + tree ret = NULL_TREE, e, se; + + if (!expr) + return NULL_TREE; + + /* Do not bother to replace constants. */ + if (CONSTANT_CLASS_P (expr)) + return expr; + + if (valueize) + { + if (TREE_CODE (expr) == SSA_NAME) + { + new_tree = valueize (expr, context); + if (new_tree != expr) + return new_tree; + } + } + else 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, valueize, context, do_fold); + if (e == se) + continue; + + if (!ret) + ret = copy_node (expr); + + TREE_OPERAND (ret, i) = se; + } + + return (ret ? (do_fold ? fold (ret) : ret) : expr); +} + +/* Expand definitions of ssa names in EXPR as long as they are simple + enough, and return the new expression. If STOP is specified, stop + expanding if EXPR equals to it. */ + +static tree +expand_simple_operations (tree expr, tree stop, hash_map<tree, tree> &cache) +{ + 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); + /* SCEV analysis feeds us with a proper expression + graph matching the SSA graph. Avoid turning it + into a tree here, thus handle tree sharing + properly. + ??? The SSA walk below still turns the SSA graph + into a tree but until we find a testcase do not + introduce additional tree sharing here. */ + bool existed_p; + tree &cee = cache.get_or_insert (e, &existed_p); + if (existed_p) + ee = cee; + else + { + cee = e; + ee = expand_simple_operations (e, stop, cache); + if (ee != e) + *cache.get (e) = ee; + } + 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; + } + + /* Stop if it's not ssa name or the one we don't want to expand. */ + if (TREE_CODE (expr) != SSA_NAME || expr == stop) + 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, stop, cache); + } + if (gimple_code (stmt) != GIMPLE_ASSIGN) + return expr; + + /* Avoid expanding to expressions that contain SSA names that need + to take part in abnormal coalescing. */ + ssa_op_iter iter; + FOR_EACH_SSA_TREE_OPERAND (e, stmt, iter, SSA_OP_USE) + if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (e)) + 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, stop, cache); + else if (code == ADDR_EXPR) + { + poly_int64 offset; + tree base = get_addr_base_and_unit_offset (TREE_OPERAND (e, 0), + &offset); + if (base + && TREE_CODE (base) == MEM_REF) + { + ee = expand_simple_operations (TREE_OPERAND (base, 0), stop, + cache); + return fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (expr), ee, + wide_int_to_tree (sizetype, + mem_ref_offset (base) + + offset)); + } + } + + return expr; + } + + switch (code) + { + CASE_CONVERT: + /* Casts are simple. */ + ee = expand_simple_operations (e, stop, cache); + return fold_build1 (code, TREE_TYPE (expr), ee); + + case PLUS_EXPR: + case MINUS_EXPR: + if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (expr)) + && TYPE_OVERFLOW_TRAPS (TREE_TYPE (expr))) + return expr; + /* Fallthru. */ + 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, stop, cache); + return fold_build2 (code, TREE_TYPE (expr), ee, e1); + + default: + return expr; + } +} + +tree +expand_simple_operations (tree expr, tree stop) +{ + hash_map<tree, tree> cache; + return expand_simple_operations (expr, stop, cache); +} + +/* 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, 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; + } + + /* Check whether COND ==> EXPR. */ + notcond = invert_truthvalue (cond); + e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, expr); + if (e && integer_nonzerop (e)) + return e; + + /* Check whether COND ==> not EXPR. */ + e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, expr); + 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). */ + +tree +simplify_using_initial_conditions (class loop *loop, tree expr) +{ + edge e; + basic_block bb; + gimple *stmt; + tree cond, expanded, backup; + int cnt = 0; + + if (TREE_CODE (expr) == INTEGER_CST) + return expr; + + backup = expanded = expand_simple_operations (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_FOR_FN (cfun) && 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); + expanded = tree_simplify_using_condition (cond, expanded); + /* Break if EXPR is simplified to const values. */ + if (expanded + && (integer_zerop (expanded) || integer_nonzerop (expanded))) + return expanded; + + ++cnt; + } + + /* Return the original expression if no simplification is done. */ + return operand_equal_p (backup, expanded, 0) ? expr : expanded; +} + +/* 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 (class 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 class loop *loop, basic_block *body, const_edge exit) +{ + gimple_stmt_iterator bsi; + unsigned i; + + if (exit != single_exit (loop)) + return false; + + for (i = 0; i < loop->num_nodes; i++) + for (bsi = gsi_start_bb (body[i]); !gsi_end_p (bsi); gsi_next (&bsi)) + if (stmt_can_terminate_bb_p (gsi_stmt (bsi))) + return false; + + 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 have meaning described + in comments at class tree_niter_desc declaration), false otherwise. + When EVERY_ITERATION is true, only tests that are known to be executed + every iteration are considered (i.e. only test that alone bounds the loop). + If AT_STMT is not NULL, this function stores LOOP's condition statement in + it when returning true. */ + +bool +number_of_iterations_exit_assumptions (class loop *loop, edge exit, + class tree_niter_desc *niter, + gcond **at_stmt, bool every_iteration, + basic_block *body) +{ + gimple *last; + gcond *stmt; + tree type; + tree op0, op1; + enum tree_code code; + affine_iv iv0, iv1; + bool safe; + + /* The condition at a fake exit (if it exists) does not control its + execution. */ + if (exit->flags & EDGE_FAKE) + return false; + + /* Nothing to analyze if the loop is known to be infinite. */ + if (loop_constraint_set_p (loop, LOOP_C_INFINITE)) + return false; + + safe = dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src); + + if (every_iteration && !safe) + return false; + + niter->assumptions = boolean_false_node; + niter->control.base = NULL_TREE; + niter->control.step = NULL_TREE; + niter->control.no_overflow = false; + last = last_stmt (exit->src); + if (!last) + return false; + stmt = dyn_cast <gcond *> (last); + if (!stmt) + 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 LT_EXPR: + case LE_EXPR: + case NE_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; + + tree iv0_niters = NULL_TREE; + if (!simple_iv_with_niters (loop, loop_containing_stmt (stmt), + op0, &iv0, safe ? &iv0_niters : NULL, false)) + return number_of_iterations_popcount (loop, exit, code, niter); + tree iv1_niters = NULL_TREE; + if (!simple_iv_with_niters (loop, loop_containing_stmt (stmt), + op1, &iv1, safe ? &iv1_niters : NULL, false)) + return false; + /* Give up on complicated case. */ + if (iv0_niters && iv1_niters) + 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); + bool body_from_caller = true; + if (!body) + { + body = get_loop_body (loop); + body_from_caller = false; + } + bool only_exit_p = loop_only_exit_p (loop, body, exit); + if (!body_from_caller) + free (body); + if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter, + only_exit_p, safe)) + { + fold_undefer_and_ignore_overflow_warnings (); + return false; + } + + /* Incorporate additional assumption implied by control iv. */ + tree iv_niters = iv0_niters ? iv0_niters : iv1_niters; + if (iv_niters) + { + tree assumption = fold_build2 (LE_EXPR, boolean_type_node, niter->niter, + fold_convert (TREE_TYPE (niter->niter), + iv_niters)); + + if (!integer_nonzerop (assumption)) + niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, + niter->assumptions, assumption); + + /* Refine upper bound if possible. */ + if (TREE_CODE (iv_niters) == INTEGER_CST + && niter->max > wi::to_widest (iv_niters)) + niter->max = wi::to_widest (iv_niters); + } + + /* There is no assumptions if the loop is known to be finite. */ + if (!integer_zerop (niter->assumptions) + && loop_constraint_set_p (loop, LOOP_C_FINITE)) + niter->assumptions = boolean_true_node; + + 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 NITER has simplified into a constant, update MAX. */ + if (TREE_CODE (niter->niter) == INTEGER_CST) + niter->max = wi::to_widest (niter->niter); + + if (at_stmt) + *at_stmt = stmt; + + return (!integer_zerop (niter->assumptions)); +} + + +/* Utility function to check if OP is defined by a stmt + that is a val - 1. */ + +static bool +ssa_defined_by_minus_one_stmt_p (tree op, tree val) +{ + gimple *stmt; + return (TREE_CODE (op) == SSA_NAME + && (stmt = SSA_NAME_DEF_STMT (op)) + && is_gimple_assign (stmt) + && (gimple_assign_rhs_code (stmt) == PLUS_EXPR) + && val == gimple_assign_rhs1 (stmt) + && integer_minus_onep (gimple_assign_rhs2 (stmt))); +} + + +/* See if LOOP is a popcout implementation, determine NITER for the loop + + We match: + <bb 2> + goto <bb 4> + + <bb 3> + _1 = b_11 + -1 + b_6 = _1 & b_11 + + <bb 4> + b_11 = PHI <b_5(D)(2), b_6(3)> + + exit block + if (b_11 != 0) + goto <bb 3> + else + goto <bb 5> + + OR we match copy-header version: + if (b_5 != 0) + goto <bb 3> + else + goto <bb 4> + + <bb 3> + b_11 = PHI <b_5(2), b_6(3)> + _1 = b_11 + -1 + b_6 = _1 & b_11 + + exit block + if (b_6 != 0) + goto <bb 3> + else + goto <bb 4> + + If popcount pattern, update NITER accordingly. + i.e., set NITER to __builtin_popcount (b) + return true if we did, false otherwise. + + */ + +static bool +number_of_iterations_popcount (loop_p loop, edge exit, + enum tree_code code, + class tree_niter_desc *niter) +{ + bool adjust = true; + tree iter; + HOST_WIDE_INT max; + adjust = true; + tree fn = NULL_TREE; + + /* Check loop terminating branch is like + if (b != 0). */ + gimple *stmt = last_stmt (exit->src); + if (!stmt + || gimple_code (stmt) != GIMPLE_COND + || code != NE_EXPR + || !integer_zerop (gimple_cond_rhs (stmt)) + || TREE_CODE (gimple_cond_lhs (stmt)) != SSA_NAME) + return false; + + gimple *and_stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (stmt)); + + /* Depending on copy-header is performed, feeding PHI stmts might be in + the loop header or loop latch, handle this. */ + if (gimple_code (and_stmt) == GIMPLE_PHI + && gimple_bb (and_stmt) == loop->header + && gimple_phi_num_args (and_stmt) == 2 + && (TREE_CODE (gimple_phi_arg_def (and_stmt, + loop_latch_edge (loop)->dest_idx)) + == SSA_NAME)) + { + /* SSA used in exit condition is defined by PHI stmt + b_11 = PHI <b_5(D)(2), b_6(3)> + from the PHI stmt, get the and_stmt + b_6 = _1 & b_11. */ + tree t = gimple_phi_arg_def (and_stmt, loop_latch_edge (loop)->dest_idx); + and_stmt = SSA_NAME_DEF_STMT (t); + adjust = false; + } + + /* Make sure it is indeed an and stmt (b_6 = _1 & b_11). */ + if (!is_gimple_assign (and_stmt) + || gimple_assign_rhs_code (and_stmt) != BIT_AND_EXPR) + return false; + + tree b_11 = gimple_assign_rhs1 (and_stmt); + tree _1 = gimple_assign_rhs2 (and_stmt); + + /* Check that _1 is defined by _b11 + -1 (_1 = b_11 + -1). + Also make sure that b_11 is the same in and_stmt and _1 defining stmt. + Also canonicalize if _1 and _b11 are revrsed. */ + if (ssa_defined_by_minus_one_stmt_p (b_11, _1)) + std::swap (b_11, _1); + else if (ssa_defined_by_minus_one_stmt_p (_1, b_11)) + ; + else + return false; + /* Check the recurrence: + ... = PHI <b_5(2), b_6(3)>. */ + gimple *phi = SSA_NAME_DEF_STMT (b_11); + if (gimple_code (phi) != GIMPLE_PHI + || (gimple_bb (phi) != loop_latch_edge (loop)->dest) + || (gimple_assign_lhs (and_stmt) + != gimple_phi_arg_def (phi, loop_latch_edge (loop)->dest_idx))) + return false; + + /* We found a match. Get the corresponding popcount builtin. */ + tree src = gimple_phi_arg_def (phi, loop_preheader_edge (loop)->dest_idx); + if (TYPE_PRECISION (TREE_TYPE (src)) <= TYPE_PRECISION (integer_type_node)) + fn = builtin_decl_implicit (BUILT_IN_POPCOUNT); + else if (TYPE_PRECISION (TREE_TYPE (src)) + == TYPE_PRECISION (long_integer_type_node)) + fn = builtin_decl_implicit (BUILT_IN_POPCOUNTL); + else if (TYPE_PRECISION (TREE_TYPE (src)) + == TYPE_PRECISION (long_long_integer_type_node) + || (TYPE_PRECISION (TREE_TYPE (src)) + == 2 * TYPE_PRECISION (long_long_integer_type_node))) + fn = builtin_decl_implicit (BUILT_IN_POPCOUNTLL); + + if (!fn) + return false; + + /* Update NITER params accordingly */ + tree utype = unsigned_type_for (TREE_TYPE (src)); + src = fold_convert (utype, src); + if (TYPE_PRECISION (TREE_TYPE (src)) < TYPE_PRECISION (integer_type_node)) + src = fold_convert (unsigned_type_node, src); + tree call; + if (TYPE_PRECISION (TREE_TYPE (src)) + == 2 * TYPE_PRECISION (long_long_integer_type_node)) + { + int prec = TYPE_PRECISION (long_long_integer_type_node); + tree src1 = fold_convert (long_long_unsigned_type_node, + fold_build2 (RSHIFT_EXPR, TREE_TYPE (src), + unshare_expr (src), + build_int_cst (integer_type_node, + prec))); + tree src2 = fold_convert (long_long_unsigned_type_node, src); + call = build_call_expr (fn, 1, src1); + call = fold_build2 (PLUS_EXPR, TREE_TYPE (call), call, + build_call_expr (fn, 1, src2)); + call = fold_convert (utype, call); + } + else + call = fold_convert (utype, build_call_expr (fn, 1, src)); + if (adjust) + iter = fold_build2 (MINUS_EXPR, utype, call, build_int_cst (utype, 1)); + else + iter = call; + + if (TREE_CODE (call) == INTEGER_CST) + max = tree_to_uhwi (call); + else + max = TYPE_PRECISION (TREE_TYPE (src)); + if (adjust) + max = max - 1; + + niter->niter = iter; + niter->assumptions = boolean_true_node; + + if (adjust) + { + tree may_be_zero = fold_build2 (EQ_EXPR, boolean_type_node, src, + build_zero_cst (TREE_TYPE (src))); + niter->may_be_zero + = simplify_using_initial_conditions (loop, may_be_zero); + } + else + niter->may_be_zero = boolean_false_node; + + niter->max = max; + niter->bound = NULL_TREE; + niter->cmp = ERROR_MARK; + return true; +} + + +/* Like number_of_iterations_exit_assumptions, but return TRUE only if + the niter information holds unconditionally. */ + +bool +number_of_iterations_exit (class loop *loop, edge exit, + class tree_niter_desc *niter, + bool warn, bool every_iteration, + basic_block *body) +{ + gcond *stmt; + if (!number_of_iterations_exit_assumptions (loop, exit, niter, + &stmt, every_iteration, body)) + return false; + + if (integer_nonzerop (niter->assumptions)) + return true; + + if (warn && dump_enabled_p ()) + dump_printf_loc (MSG_MISSED_OPTIMIZATION, stmt, + "missed loop optimization: niters analysis ends up " + "with assumptions.\n"); + + return false; +} + +/* 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 (class loop *loop, edge *exit) +{ + unsigned i; + auto_vec<edge> exits = get_loop_exit_edges (loop); + edge ex; + tree niter = NULL_TREE, aniter; + class tree_niter_desc desc; + + *exit = NULL; + FOR_EACH_VEC_ELT (exits, i, ex) + { + 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; + } + } + + return niter ? niter : chrec_dont_know; +} + +/* Return true if loop is known to have bounded number of iterations. */ + +bool +finite_loop_p (class loop *loop) +{ + widest_int nit; + int flags; + + 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; + } + + if (loop->any_upper_bound + || max_loop_iterations (loop, &nit)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Found loop %i to be finite: upper bound found.\n", + loop->num); + return true; + } + + if (loop->finite_p) + { + unsigned i; + auto_vec<edge> exits = get_loop_exit_edges (loop); + edge ex; + + /* If the loop has a normal exit, we can assume it will terminate. */ + FOR_EACH_VEC_ELT (exits, i, ex) + if (!(ex->flags & (EDGE_EH | EDGE_ABNORMAL | EDGE_FAKE))) + { + if (dump_file) + fprintf (dump_file, "Assume loop %i to be finite: it has an exit " + "and -ffinite-loops is on.\n", loop->num); + return true; + } + } + + return false; +} + +/* + + 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_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 gphi * +chain_of_csts_start (class 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 as_a <gphi *> (stmt); + + return NULL; + } + + if (gimple_code (stmt) != GIMPLE_ASSIGN + || gimple_assign_rhs_class (stmt) == GIMPLE_TERNARY_RHS) + 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, + or is also a constant + + If such phi node exists, it is returned, otherwise NULL is returned. */ + +static gphi * +get_base_for (class loop *loop, tree x) +{ + gphi *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 (!is_gimple_min_invariant (init)) + return NULL; + + if (TREE_CODE (next) == SSA_NAME + && 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. + * if X is a constant, we return the constant X. + * 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_checking_assert (is_gimple_min_invariant (base)); + + if (!x) + return base; + else if (is_gimple_min_invariant (x)) + return x; + + stmt = SSA_NAME_DEF_STMT (x); + if (gimple_code (stmt) == GIMPLE_PHI) + return base; + + gcc_checking_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), + TREE_TYPE (gimple_assign_lhs (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), + TREE_TYPE (gimple_assign_lhs (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 (class loop *loop, edge exit) +{ + tree acnd; + tree op[2], val[2], next[2], aval[2]; + gphi *phi; + gimple *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++) + { + aval[j] = val[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; + } + } + + /* If the next iteration would use the same base values + as the current one, there is no point looping further, + all following iterations will be the same as this one. */ + if (val[0] == aval[0] && val[1] == aval[1]) + break; + } + + 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 (class loop *loop, edge *exit) +{ + unsigned i; + auto_vec<edge> 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 + && exits.length () > 1) + return chrec_dont_know; + + FOR_EACH_VEC_ELT (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; + } + + return niter ? niter : chrec_dont_know; +} + +/* + + Analysis of upper bounds on number of iterations of a loop. + +*/ + +static widest_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 widest_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 widest_int +derive_constant_upper_bound (tree val) +{ + enum tree_code code; + tree op0, op1, op2; + + extract_ops_from_tree (val, &code, &op0, &op1, &op2); + 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 widest_int +derive_constant_upper_bound_ops (tree type, tree op0, + enum tree_code code, tree op1) +{ + tree subtype, maxt; + widest_int bnd, max, cst; + gimple *stmt; + + if (INTEGRAL_TYPE_P (type)) + maxt = TYPE_MAX_VALUE (type); + else + maxt = upper_bound_in_type (type, type); + + max = wi::to_widest (maxt); + + switch (code) + { + case INTEGER_CST: + return wi::to_widest (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 (wi::ltu_p (max, bnd)) + 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 = wi::sext (wi::to_widest (op1), TYPE_PRECISION (type)); + if (code != MINUS_EXPR) + cst = -cst; + + bnd = derive_constant_upper_bound (op0); + + if (wi::neg_p (cst)) + { + cst = -cst; + /* Avoid CST == 0x80000... */ + if (wi::neg_p (cst)) + return max; + + /* OP0 + CST. We need to check that + BND <= MAX (type) - CST. */ + + widest_int mmax = max - cst; + if (wi::leu_p (bnd, mmax)) + return max; + + return 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 (wi::ltu_p (bnd, cst)) + return max; + + if (TYPE_UNSIGNED (type)) + { + tree tem = fold_binary (GE_EXPR, boolean_type_node, op0, + wide_int_to_tree (type, cst)); + if (!tem || integer_nonzerop (tem)) + return max; + } + + 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 wi::udiv_floor (bnd, wi::to_widest (op1)); + + case BIT_AND_EXPR: + if (TREE_CODE (op1) != INTEGER_CST + || tree_int_cst_sign_bit (op1)) + return max; + return wi::to_widest (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; + } +} + +/* Emit a -Waggressive-loop-optimizations warning if needed. */ + +static void +do_warn_aggressive_loop_optimizations (class loop *loop, + widest_int i_bound, gimple *stmt) +{ + /* Don't warn if the loop doesn't have known constant bound. */ + if (!loop->nb_iterations + || TREE_CODE (loop->nb_iterations) != INTEGER_CST + || !warn_aggressive_loop_optimizations + /* To avoid warning multiple times for the same loop, + only start warning when we preserve loops. */ + || (cfun->curr_properties & PROP_loops) == 0 + /* Only warn once per loop. */ + || loop->warned_aggressive_loop_optimizations + /* Only warn if undefined behavior gives us lower estimate than the + known constant bound. */ + || wi::cmpu (i_bound, wi::to_widest (loop->nb_iterations)) >= 0 + /* And undefined behavior happens unconditionally. */ + || !dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (stmt))) + return; + + edge e = single_exit (loop); + if (e == NULL) + return; + + gimple *estmt = last_stmt (e->src); + char buf[WIDE_INT_PRINT_BUFFER_SIZE]; + print_dec (i_bound, buf, TYPE_UNSIGNED (TREE_TYPE (loop->nb_iterations)) + ? UNSIGNED : SIGNED); + auto_diagnostic_group d; + if (warning_at (gimple_location (stmt), OPT_Waggressive_loop_optimizations, + "iteration %s invokes undefined behavior", buf)) + inform (gimple_location (estmt), "within this loop"); + loop->warned_aggressive_loop_optimizations = true; +} + +/* 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 a widest_int upper estimate on BOUND. */ + +static void +record_estimate (class loop *loop, tree bound, const widest_int &i_bound, + gimple *at_stmt, bool is_exit, bool realistic, bool upper) +{ + widest_int delta; + + 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 "); + print_decu (i_bound, dump_file); + 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; + else + gcc_checking_assert (i_bound == wi::to_widest (bound)); + + /* If we have a guaranteed upper bound, record it in the appropriate + list, unless this is an !is_exit bound (i.e. undefined behavior in + at_stmt) in a loop with known constant number of iterations. */ + if (upper + && (is_exit + || loop->nb_iterations == NULL_TREE + || TREE_CODE (loop->nb_iterations) != INTEGER_CST)) + { + class 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; + } + + /* If statement is executed on every path to the loop latch, we can directly + infer the upper bound on the # of iterations of the loop. */ + if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (at_stmt))) + upper = false; + + /* Update the number of iteration estimates according to the bound. + If at_stmt is an exit then the loop latch is executed at most BOUND times, + otherwise it can be executed BOUND + 1 times. We will lower the estimate + later if such statement must be executed on last iteration */ + if (is_exit) + delta = 0; + else + delta = 1; + widest_int new_i_bound = i_bound + delta; + + /* If an overflow occurred, ignore the result. */ + if (wi::ltu_p (new_i_bound, delta)) + return; + + if (upper && !is_exit) + do_warn_aggressive_loop_optimizations (loop, new_i_bound, at_stmt); + record_niter_bound (loop, new_i_bound, realistic, upper); +} + +/* Records the control iv analyzed in NITER for LOOP if the iv is valid + and doesn't overflow. */ + +static void +record_control_iv (class loop *loop, class tree_niter_desc *niter) +{ + struct control_iv *iv; + + if (!niter->control.base || !niter->control.step) + return; + + if (!integer_onep (niter->assumptions) || !niter->control.no_overflow) + return; + + iv = ggc_alloc<control_iv> (); + iv->base = niter->control.base; + iv->step = niter->control.step; + iv->next = loop->control_ivs; + loop->control_ivs = iv; + + return; +} + +/* This function returns TRUE if below conditions are satisfied: + 1) VAR is SSA variable. + 2) VAR is an IV:{base, step} in its defining loop. + 3) IV doesn't overflow. + 4) Both base and step are integer constants. + 5) Base is the MIN/MAX value depends on IS_MIN. + Store value of base to INIT correspondingly. */ + +static bool +get_cst_init_from_scev (tree var, wide_int *init, bool is_min) +{ + if (TREE_CODE (var) != SSA_NAME) + return false; + + gimple *def_stmt = SSA_NAME_DEF_STMT (var); + class loop *loop = loop_containing_stmt (def_stmt); + + if (loop == NULL) + return false; + + affine_iv iv; + if (!simple_iv (loop, loop, var, &iv, false)) + return false; + + if (!iv.no_overflow) + return false; + + if (TREE_CODE (iv.base) != INTEGER_CST || TREE_CODE (iv.step) != INTEGER_CST) + return false; + + if (is_min == tree_int_cst_sign_bit (iv.step)) + return false; + + *init = wi::to_wide (iv.base); + return true; +} + +/* Record the estimate on number of iterations of LOOP based on the fact that + the induction variable BASE + STEP * i evaluated in STMT does not wrap and + its values belong to the range <LOW, HIGH>. REALISTIC is true if the + estimated number of iterations is expected to be close to the real one. + UPPER is true if we are sure the induction variable does not wrap. */ + +static void +record_nonwrapping_iv (class 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; + tree orig_base = base; + + 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)) + { + wide_int max; + value_range base_range; + if (get_range_query (cfun)->range_of_expr (base_range, orig_base) + && !base_range.undefined_p ()) + max = base_range.upper_bound (); + extreme = fold_convert (unsigned_type, low); + if (TREE_CODE (orig_base) == SSA_NAME + && TREE_CODE (high) == INTEGER_CST + && INTEGRAL_TYPE_P (TREE_TYPE (orig_base)) + && (base_range.kind () == VR_RANGE + || get_cst_init_from_scev (orig_base, &max, false)) + && wi::gts_p (wi::to_wide (high), max)) + base = wide_int_to_tree (unsigned_type, max); + else if (TREE_CODE (base) != INTEGER_CST + && dominated_by_p (CDI_DOMINATORS, + loop->latch, gimple_bb (stmt))) + base = fold_convert (unsigned_type, high); + delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme); + step = fold_build1 (NEGATE_EXPR, unsigned_type, step); + } + else + { + wide_int min; + value_range base_range; + if (get_range_query (cfun)->range_of_expr (base_range, orig_base) + && !base_range.undefined_p ()) + min = base_range.lower_bound (); + extreme = fold_convert (unsigned_type, high); + if (TREE_CODE (orig_base) == SSA_NAME + && TREE_CODE (low) == INTEGER_CST + && INTEGRAL_TYPE_P (TREE_TYPE (orig_base)) + && (base_range.kind () == VR_RANGE + || get_cst_init_from_scev (orig_base, &min, true)) + && wi::gts_p (min, wi::to_wide (low))) + base = wide_int_to_tree (unsigned_type, min); + else if (TREE_CODE (base) != INTEGER_CST + && dominated_by_p (CDI_DOMINATORS, + loop->latch, gimple_bb (stmt))) + 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); + widest_int max = derive_constant_upper_bound (niter_bound); + record_estimate (loop, niter_bound, max, stmt, false, realistic, upper); +} + +/* 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 +{ + class loop *loop; + gimple *stmt; +}; + +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 = true, at_end = false; + class 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; + } + + class loop *dloop = loop_containing_stmt (data->stmt); + if (!dloop) + return true; + + ev = analyze_scalar_evolution (dloop, *idx); + ev = instantiate_parameters (loop, ev); + 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; + + /* If access is not executed on every iteration, we must ensure that overlow + may not make the access valid later. */ + if (!dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (data->stmt)) + && scev_probably_wraps_p (NULL_TREE, + initial_condition_in_loop_num (ev, loop->num), + step, data->stmt, loop, true)) + upper = false; + + record_nonwrapping_iv (loop, init, step, data->stmt, low, high, false, 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 (class loop *loop, gimple *stmt, tree ref) +{ + struct ilb_data data; + + data.loop = loop; + data.stmt = stmt; + 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 (class loop *loop, gimple *stmt) +{ + 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); + + if (REFERENCE_CLASS_P (op1)) + infer_loop_bounds_from_ref (loop, stmt, op1); + } + 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); + + 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); + } + } +} + +/* Determine information about number of iterations of a LOOP from the fact + that pointer arithmetics in STMT does not overflow. */ + +static void +infer_loop_bounds_from_pointer_arith (class loop *loop, gimple *stmt) +{ + tree def, base, step, scev, type, low, high; + tree var, ptr; + + if (!is_gimple_assign (stmt) + || gimple_assign_rhs_code (stmt) != POINTER_PLUS_EXPR) + return; + + def = gimple_assign_lhs (stmt); + if (TREE_CODE (def) != SSA_NAME) + return; + + type = TREE_TYPE (def); + if (!nowrap_type_p (type)) + return; + + ptr = gimple_assign_rhs1 (stmt); + if (!expr_invariant_in_loop_p (loop, ptr)) + return; + + var = gimple_assign_rhs2 (stmt); + if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (var))) + return; + + class loop *uloop = loop_containing_stmt (stmt); + scev = instantiate_parameters (loop, analyze_scalar_evolution (uloop, 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); + + /* In C, pointer arithmetic p + 1 cannot use a NULL pointer, and p - 1 cannot + produce a NULL pointer. The contrary would mean NULL points to an object, + while NULL is supposed to compare unequal with the address of all objects. + Furthermore, p + 1 cannot produce a NULL pointer and p - 1 cannot use a + NULL pointer since that would mean wrapping, which we assume here not to + happen. So, we can exclude NULL from the valid range of pointer + arithmetic. */ + if (flag_delete_null_pointer_checks && int_cst_value (low) == 0) + low = build_int_cstu (TREE_TYPE (low), TYPE_ALIGN_UNIT (TREE_TYPE (type))); + + record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true); +} + +/* 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 (class 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); + value_range r; + get_range_query (cfun)->range_of_expr (r, def); + if (r.kind () == VR_RANGE) + { + low = wide_int_to_tree (type, r.lower_bound ()); + high = wide_int_to_tree (type, r.upper_bound ()); + } + + 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 (class loop *loop, basic_block *bbs) +{ + unsigned i; + gimple_stmt_iterator bsi; + basic_block bb; + bool reliable; + + 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 guesses come only from array bounds. */ + 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); + + if (reliable) + { + infer_loop_bounds_from_signedness (loop, stmt); + infer_loop_bounds_from_pointer_arith (loop, stmt); + } + } + + } +} + +/* Compare wide ints, callback for qsort. */ + +static int +wide_int_cmp (const void *p1, const void *p2) +{ + const widest_int *d1 = (const widest_int *) p1; + const widest_int *d2 = (const widest_int *) p2; + return wi::cmpu (*d1, *d2); +} + +/* Return index of BOUND in BOUNDS array sorted in increasing order. + Lookup by binary search. */ + +static int +bound_index (const vec<widest_int> &bounds, const widest_int &bound) +{ + unsigned int end = bounds.length (); + unsigned int begin = 0; + + /* Find a matching index by means of a binary search. */ + while (begin != end) + { + unsigned int middle = (begin + end) / 2; + widest_int index = bounds[middle]; + + if (index == bound) + return middle; + else if (wi::ltu_p (index, bound)) + begin = middle + 1; + else + end = middle; + } + gcc_unreachable (); +} + +/* We recorded loop bounds only for statements dominating loop latch (and thus + executed each loop iteration). If there are any bounds on statements not + dominating the loop latch we can improve the estimate by walking the loop + body and seeing if every path from loop header to loop latch contains + some bounded statement. */ + +static void +discover_iteration_bound_by_body_walk (class loop *loop) +{ + class nb_iter_bound *elt; + auto_vec<widest_int> bounds; + vec<vec<basic_block> > queues = vNULL; + vec<basic_block> queue = vNULL; + ptrdiff_t queue_index; + ptrdiff_t latch_index = 0; + + /* Discover what bounds may interest us. */ + for (elt = loop->bounds; elt; elt = elt->next) + { + widest_int bound = elt->bound; + + /* Exit terminates loop at given iteration, while non-exits produce undefined + effect on the next iteration. */ + if (!elt->is_exit) + { + bound += 1; + /* If an overflow occurred, ignore the result. */ + if (bound == 0) + continue; + } + + if (!loop->any_upper_bound + || wi::ltu_p (bound, loop->nb_iterations_upper_bound)) + bounds.safe_push (bound); + } + + /* Exit early if there is nothing to do. */ + if (!bounds.exists ()) + return; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, " Trying to walk loop body to reduce the bound.\n"); + + /* Sort the bounds in decreasing order. */ + bounds.qsort (wide_int_cmp); + + /* For every basic block record the lowest bound that is guaranteed to + terminate the loop. */ + + hash_map<basic_block, ptrdiff_t> bb_bounds; + for (elt = loop->bounds; elt; elt = elt->next) + { + widest_int bound = elt->bound; + if (!elt->is_exit) + { + bound += 1; + /* If an overflow occurred, ignore the result. */ + if (bound == 0) + continue; + } + + if (!loop->any_upper_bound + || wi::ltu_p (bound, loop->nb_iterations_upper_bound)) + { + ptrdiff_t index = bound_index (bounds, bound); + ptrdiff_t *entry = bb_bounds.get (gimple_bb (elt->stmt)); + if (!entry) + bb_bounds.put (gimple_bb (elt->stmt), index); + else if ((ptrdiff_t)*entry > index) + *entry = index; + } + } + + hash_map<basic_block, ptrdiff_t> block_priority; + + /* Perform shortest path discovery loop->header ... loop->latch. + + The "distance" is given by the smallest loop bound of basic block + present in the path and we look for path with largest smallest bound + on it. + + To avoid the need for fibonacci heap on double ints we simply compress + double ints into indexes to BOUNDS array and then represent the queue + as arrays of queues for every index. + Index of BOUNDS.length() means that the execution of given BB has + no bounds determined. + + VISITED is a pointer map translating basic block into smallest index + it was inserted into the priority queue with. */ + latch_index = -1; + + /* Start walk in loop header with index set to infinite bound. */ + queue_index = bounds.length (); + queues.safe_grow_cleared (queue_index + 1, true); + queue.safe_push (loop->header); + queues[queue_index] = queue; + block_priority.put (loop->header, queue_index); + + for (; queue_index >= 0; queue_index--) + { + if (latch_index < queue_index) + { + while (queues[queue_index].length ()) + { + basic_block bb; + ptrdiff_t bound_index = queue_index; + edge e; + edge_iterator ei; + + queue = queues[queue_index]; + bb = queue.pop (); + + /* OK, we later inserted the BB with lower priority, skip it. */ + if (*block_priority.get (bb) > queue_index) + continue; + + /* See if we can improve the bound. */ + ptrdiff_t *entry = bb_bounds.get (bb); + if (entry && *entry < bound_index) + bound_index = *entry; + + /* Insert succesors into the queue, watch for latch edge + and record greatest index we saw. */ + FOR_EACH_EDGE (e, ei, bb->succs) + { + bool insert = false; + + if (loop_exit_edge_p (loop, e)) + continue; + + if (e == loop_latch_edge (loop) + && latch_index < bound_index) + latch_index = bound_index; + else if (!(entry = block_priority.get (e->dest))) + { + insert = true; + block_priority.put (e->dest, bound_index); + } + else if (*entry < bound_index) + { + insert = true; + *entry = bound_index; + } + + if (insert) + queues[bound_index].safe_push (e->dest); + } + } + } + queues[queue_index].release (); + } + + gcc_assert (latch_index >= 0); + if ((unsigned)latch_index < bounds.length ()) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Found better loop bound "); + print_decu (bounds[latch_index], dump_file); + fprintf (dump_file, "\n"); + } + record_niter_bound (loop, bounds[latch_index], false, true); + } + + queues.release (); +} + +/* See if every path cross the loop goes through a statement that is known + to not execute at the last iteration. In that case we can decrese iteration + count by 1. */ + +static void +maybe_lower_iteration_bound (class loop *loop) +{ + hash_set<gimple *> *not_executed_last_iteration = NULL; + class nb_iter_bound *elt; + bool found_exit = false; + auto_vec<basic_block> queue; + bitmap visited; + + /* Collect all statements with interesting (i.e. lower than + nb_iterations_upper_bound) bound on them. + + TODO: Due to the way record_estimate choose estimates to store, the bounds + will be always nb_iterations_upper_bound-1. We can change this to record + also statements not dominating the loop latch and update the walk bellow + to the shortest path algorithm. */ + for (elt = loop->bounds; elt; elt = elt->next) + { + if (!elt->is_exit + && wi::ltu_p (elt->bound, loop->nb_iterations_upper_bound)) + { + if (!not_executed_last_iteration) + not_executed_last_iteration = new hash_set<gimple *>; + not_executed_last_iteration->add (elt->stmt); + } + } + if (!not_executed_last_iteration) + return; + + /* Start DFS walk in the loop header and see if we can reach the + loop latch or any of the exits (including statements with side + effects that may terminate the loop otherwise) without visiting + any of the statements known to have undefined effect on the last + iteration. */ + queue.safe_push (loop->header); + visited = BITMAP_ALLOC (NULL); + bitmap_set_bit (visited, loop->header->index); + found_exit = false; + + do + { + basic_block bb = queue.pop (); + gimple_stmt_iterator gsi; + bool stmt_found = false; + + /* Loop for possible exits and statements bounding the execution. */ + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple *stmt = gsi_stmt (gsi); + if (not_executed_last_iteration->contains (stmt)) + { + stmt_found = true; + break; + } + if (gimple_has_side_effects (stmt)) + { + found_exit = true; + break; + } + } + if (found_exit) + break; + + /* If no bounding statement is found, continue the walk. */ + if (!stmt_found) + { + edge e; + edge_iterator ei; + + FOR_EACH_EDGE (e, ei, bb->succs) + { + if (loop_exit_edge_p (loop, e) + || e == loop_latch_edge (loop)) + { + found_exit = true; + break; + } + if (bitmap_set_bit (visited, e->dest->index)) + queue.safe_push (e->dest); + } + } + } + while (queue.length () && !found_exit); + + /* If every path through the loop reach bounding statement before exit, + then we know the last iteration of the loop will have undefined effect + and we can decrease number of iterations. */ + + if (!found_exit) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Reducing loop iteration estimate by 1; " + "undefined statement must be executed at the last iteration.\n"); + record_niter_bound (loop, loop->nb_iterations_upper_bound - 1, + false, true); + } + + BITMAP_FREE (visited); + delete not_executed_last_iteration; +} + +/* Get expected upper bound for number of loop iterations for + BUILT_IN_EXPECT_WITH_PROBABILITY for a condition COND. */ + +static tree +get_upper_bound_based_on_builtin_expr_with_prob (gcond *cond) +{ + if (cond == NULL) + return NULL_TREE; + + tree lhs = gimple_cond_lhs (cond); + if (TREE_CODE (lhs) != SSA_NAME) + return NULL_TREE; + + gimple *stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond)); + gcall *def = dyn_cast<gcall *> (stmt); + if (def == NULL) + return NULL_TREE; + + tree decl = gimple_call_fndecl (def); + if (!decl + || !fndecl_built_in_p (decl, BUILT_IN_EXPECT_WITH_PROBABILITY) + || gimple_call_num_args (stmt) != 3) + return NULL_TREE; + + tree c = gimple_call_arg (def, 1); + tree condt = TREE_TYPE (lhs); + tree res = fold_build2 (gimple_cond_code (cond), + condt, c, + gimple_cond_rhs (cond)); + if (TREE_CODE (res) != INTEGER_CST) + return NULL_TREE; + + + tree prob = gimple_call_arg (def, 2); + tree t = TREE_TYPE (prob); + tree one + = build_real_from_int_cst (t, + integer_one_node); + if (integer_zerop (res)) + prob = fold_build2 (MINUS_EXPR, t, one, prob); + tree r = fold_build2 (RDIV_EXPR, t, one, prob); + if (TREE_CODE (r) != REAL_CST) + return NULL_TREE; + + HOST_WIDE_INT probi + = real_to_integer (TREE_REAL_CST_PTR (r)); + return build_int_cst (condt, probi); +} + +/* 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 (class loop *loop) +{ + tree niter, type; + unsigned i; + class tree_niter_desc niter_desc; + edge ex; + widest_int bound; + edge likely_exit; + + /* Give up if we already have tried to compute an estimation. */ + if (loop->estimate_state != EST_NOT_COMPUTED) + return; + + loop->estimate_state = EST_AVAILABLE; + + /* If we have a measured profile, use it to estimate the number of + iterations. Normally this is recorded by branch_prob right after + reading the profile. In case we however found a new loop, record the + information here. + + Explicitly check for profile status so we do not report + wrong prediction hitrates for guessed loop iterations heuristics. + Do not recompute already recorded bounds - we ought to be better on + updating iteration bounds than updating profile in general and thus + recomputing iteration bounds later in the compilation process will just + introduce random roundoff errors. */ + if (!loop->any_estimate + && loop->header->count.reliable_p ()) + { + gcov_type nit = expected_loop_iterations_unbounded (loop); + bound = gcov_type_to_wide_int (nit); + record_niter_bound (loop, bound, true, false); + } + + /* Ensure that loop->nb_iterations is computed if possible. If it turns out + to be constant, we avoid undefined behavior implied bounds and instead + diagnose those loops with -Waggressive-loop-optimizations. */ + number_of_latch_executions (loop); + + basic_block *body = get_loop_body (loop); + auto_vec<edge> exits = get_loop_exit_edges (loop, body); + likely_exit = single_likely_exit (loop, exits); + FOR_EACH_VEC_ELT (exits, i, ex) + { + if (ex == likely_exit) + { + gimple *stmt = last_stmt (ex->src); + if (stmt != NULL) + { + gcond *cond = dyn_cast<gcond *> (stmt); + tree niter_bound + = get_upper_bound_based_on_builtin_expr_with_prob (cond); + if (niter_bound != NULL_TREE) + { + widest_int max = derive_constant_upper_bound (niter_bound); + record_estimate (loop, niter_bound, max, cond, + true, true, false); + } + } + } + + if (!number_of_iterations_exit (loop, ex, &niter_desc, + false, false, body)) + 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, ex == likely_exit, true); + record_control_iv (loop, &niter_desc); + } + + if (flag_aggressive_loop_optimizations) + infer_loop_bounds_from_undefined (loop, body); + free (body); + + discover_iteration_bound_by_body_walk (loop); + + maybe_lower_iteration_bound (loop); + + /* If we know the exact number of iterations of this loop, try to + not break code with undefined behavior by not recording smaller + maximum number of iterations. */ + if (loop->nb_iterations + && TREE_CODE (loop->nb_iterations) == INTEGER_CST) + { + loop->any_upper_bound = true; + loop->nb_iterations_upper_bound = wi::to_widest (loop->nb_iterations); + } +} + +/* Sets NIT to the estimated number of executions of the latch of the + LOOP. If CONSERVATIVE is true, we must be sure that NIT is at least as + large as the number of iterations. If we have no reliable estimate, + the function returns false, otherwise returns true. */ + +bool +estimated_loop_iterations (class loop *loop, widest_int *nit) +{ + /* When SCEV information is available, try to update loop iterations + estimate. Otherwise just return whatever we recorded earlier. */ + if (scev_initialized_p ()) + estimate_numbers_of_iterations (loop); + + return (get_estimated_loop_iterations (loop, nit)); +} + +/* Similar to estimated_loop_iterations, but returns the estimate only + if it fits to HOST_WIDE_INT. If this is not the case, or the estimate + on the number of iterations of LOOP could not be derived, returns -1. */ + +HOST_WIDE_INT +estimated_loop_iterations_int (class loop *loop) +{ + widest_int nit; + HOST_WIDE_INT hwi_nit; + + if (!estimated_loop_iterations (loop, &nit)) + return -1; + + if (!wi::fits_shwi_p (nit)) + return -1; + hwi_nit = nit.to_shwi (); + + return hwi_nit < 0 ? -1 : hwi_nit; +} + + +/* Sets NIT to an upper bound for the maximum number of executions of the + latch of the LOOP. If we have no reliable estimate, the function returns + false, otherwise returns true. */ + +bool +max_loop_iterations (class loop *loop, widest_int *nit) +{ + /* When SCEV information is available, try to update loop iterations + estimate. Otherwise just return whatever we recorded earlier. */ + if (scev_initialized_p ()) + estimate_numbers_of_iterations (loop); + + return get_max_loop_iterations (loop, nit); +} + +/* Similar to max_loop_iterations, but returns the estimate only + if it fits to HOST_WIDE_INT. If this is not the case, or the estimate + on the number of iterations of LOOP could not be derived, returns -1. */ + +HOST_WIDE_INT +max_loop_iterations_int (class loop *loop) +{ + widest_int nit; + HOST_WIDE_INT hwi_nit; + + if (!max_loop_iterations (loop, &nit)) + return -1; + + if (!wi::fits_shwi_p (nit)) + return -1; + hwi_nit = nit.to_shwi (); + + return hwi_nit < 0 ? -1 : hwi_nit; +} + +/* Sets NIT to an likely upper bound for the maximum number of executions of the + latch of the LOOP. If we have no reliable estimate, the function returns + false, otherwise returns true. */ + +bool +likely_max_loop_iterations (class loop *loop, widest_int *nit) +{ + /* When SCEV information is available, try to update loop iterations + estimate. Otherwise just return whatever we recorded earlier. */ + if (scev_initialized_p ()) + estimate_numbers_of_iterations (loop); + + return get_likely_max_loop_iterations (loop, nit); +} + +/* Similar to max_loop_iterations, but returns the estimate only + if it fits to HOST_WIDE_INT. If this is not the case, or the estimate + on the number of iterations of LOOP could not be derived, returns -1. */ + +HOST_WIDE_INT +likely_max_loop_iterations_int (class loop *loop) +{ + widest_int nit; + HOST_WIDE_INT hwi_nit; + + if (!likely_max_loop_iterations (loop, &nit)) + return -1; + + if (!wi::fits_shwi_p (nit)) + return -1; + hwi_nit = nit.to_shwi (); + + return hwi_nit < 0 ? -1 : hwi_nit; +} + +/* Returns an estimate for the number of executions of statements + in the LOOP. For statements before the loop exit, this exceeds + the number of execution of the latch by one. */ + +HOST_WIDE_INT +estimated_stmt_executions_int (class loop *loop) +{ + HOST_WIDE_INT nit = estimated_loop_iterations_int (loop); + HOST_WIDE_INT snit; + + if (nit == -1) + return -1; + + snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1); + + /* If the computation overflows, return -1. */ + return snit < 0 ? -1 : snit; +} + +/* Sets NIT to the maximum number of executions of the latch of the + LOOP, plus one. If we have no reliable estimate, the function returns + false, otherwise returns true. */ + +bool +max_stmt_executions (class loop *loop, widest_int *nit) +{ + widest_int nit_minus_one; + + if (!max_loop_iterations (loop, nit)) + return false; + + nit_minus_one = *nit; + + *nit += 1; + + return wi::gtu_p (*nit, nit_minus_one); +} + +/* Sets NIT to the estimated maximum number of executions of the latch of the + LOOP, plus one. If we have no likely estimate, the function returns + false, otherwise returns true. */ + +bool +likely_max_stmt_executions (class loop *loop, widest_int *nit) +{ + widest_int nit_minus_one; + + if (!likely_max_loop_iterations (loop, nit)) + return false; + + nit_minus_one = *nit; + + *nit += 1; + + return wi::gtu_p (*nit, nit_minus_one); +} + +/* Sets NIT to the estimated number of executions of the latch of the + LOOP, plus one. If we have no reliable estimate, the function returns + false, otherwise returns true. */ + +bool +estimated_stmt_executions (class loop *loop, widest_int *nit) +{ + widest_int nit_minus_one; + + if (!estimated_loop_iterations (loop, nit)) + return false; + + nit_minus_one = *nit; + + *nit += 1; + + return wi::gtu_p (*nit, nit_minus_one); +} + +/* Records estimates on numbers of iterations of loops. */ + +void +estimate_numbers_of_iterations (function *fn) +{ + /* We don't want to issue signed overflow warnings while getting + loop iteration estimates. */ + fold_defer_overflow_warnings (); + + for (auto loop : loops_list (fn, 0)) + estimate_numbers_of_iterations (loop); + + 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 and fact that NITER_BOUND->stmt dominate STMT. + + ??? This code can become quite a CPU hog - we can have many bounds, + and large basic block forcing stmt_dominates_stmt_p to be queried + many times on a large basic blocks, so the whole thing is O(n^2) + for scev_probably_wraps_p invocation (that can be done n times). + + It would make more sense (and give better answers) to remember BB + bounds computed by discover_iteration_bound_by_body_walk. */ + +static bool +n_of_executions_at_most (gimple *stmt, + class nb_iter_bound *niter_bound, + tree niter) +{ + widest_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 (!wi::fits_to_tree_p (bound, nit_type)) + 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 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 then STMT is executed at most NITER_BOUND->bound + 1 times. + + If we can determine that NITER_BOUND->stmt is always executed + after STMT, then STMT is executed at most NITER_BOUND->bound + 2 times. + We conclude that if both statements belong to the same + basic block and STMT is before NITER_BOUND->stmt and there are no + statements with side effects in between. */ + + if (niter_bound->is_exit) + { + if (stmt == niter_bound->stmt + || !stmt_dominates_stmt_p (niter_bound->stmt, stmt)) + return false; + cmp = GE_EXPR; + } + else + { + if (!stmt_dominates_stmt_p (niter_bound->stmt, stmt)) + { + gimple_stmt_iterator bsi; + if (gimple_bb (stmt) != gimple_bb (niter_bound->stmt) + || gimple_code (stmt) == GIMPLE_PHI + || gimple_code (niter_bound->stmt) == GIMPLE_PHI) + return false; + + /* By stmt_dominates_stmt_p we already know that STMT appears + before NITER_BOUND->STMT. Still need to test that the loop + cannot be terinated by a side effect in between. */ + for (bsi = gsi_for_stmt (stmt); gsi_stmt (bsi) != niter_bound->stmt; + gsi_next (&bsi)) + if (gimple_has_side_effects (gsi_stmt (bsi))) + return false; + bound += 1; + if (bound == 0 + || !wi::fits_to_tree_p (bound, nit_type)) + return false; + } + cmp = GT_EXPR; + } + + e = fold_binary (cmp, boolean_type_node, + niter, wide_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 (ANY_INTEGRAL_TYPE_P (type) + && TYPE_OVERFLOW_UNDEFINED (type)) + return true; + + if (POINTER_TYPE_P (type)) + return true; + + return false; +} + +/* Return true if we can prove LOOP is exited before evolution of induction + variable {BASE, STEP} overflows with respect to its type bound. */ + +static bool +loop_exits_before_overflow (tree base, tree step, + gimple *at_stmt, class loop *loop) +{ + widest_int niter; + struct control_iv *civ; + class nb_iter_bound *bound; + tree e, delta, step_abs, unsigned_base; + tree type = TREE_TYPE (step); + tree unsigned_type, valid_niter; + + /* Don't issue signed overflow warnings. */ + fold_defer_overflow_warnings (); + + /* 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); + unsigned_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, unsigned_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, unsigned_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); + + if (max_loop_iterations (loop, &niter) + && wi::fits_to_tree_p (niter, TREE_TYPE (valid_niter)) + && (e = fold_binary (GT_EXPR, boolean_type_node, valid_niter, + wide_int_to_tree (TREE_TYPE (valid_niter), + niter))) != NULL + && integer_nonzerop (e)) + { + fold_undefer_and_ignore_overflow_warnings (); + return true; + } + if (at_stmt) + 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 true; + } + } + fold_undefer_and_ignore_overflow_warnings (); + + /* Try to prove loop is exited before {base, step} overflows with the + help of analyzed loop control IV. This is done only for IVs with + constant step because otherwise we don't have the information. */ + if (TREE_CODE (step) == INTEGER_CST) + { + for (civ = loop->control_ivs; civ; civ = civ->next) + { + enum tree_code code; + tree civ_type = TREE_TYPE (civ->step); + + /* Have to consider type difference because operand_equal_p ignores + that for constants. */ + if (TYPE_UNSIGNED (type) != TYPE_UNSIGNED (civ_type) + || element_precision (type) != element_precision (civ_type)) + continue; + + /* Only consider control IV with same step. */ + if (!operand_equal_p (step, civ->step, 0)) + continue; + + /* Done proving if this is a no-overflow control IV. */ + if (operand_equal_p (base, civ->base, 0)) + return true; + + /* Control IV is recorded after expanding simple operations, + Here we expand base and compare it too. */ + tree expanded_base = expand_simple_operations (base); + if (operand_equal_p (expanded_base, civ->base, 0)) + return true; + + /* If this is a before stepping control IV, in other words, we have + + {civ_base, step} = {base + step, step} + + Because civ {base + step, step} doesn't overflow during loop + iterations, {base, step} will not overflow if we can prove the + operation "base + step" does not overflow. Specifically, we try + to prove below conditions are satisfied: + + base <= UPPER_BOUND (type) - step ;;step > 0 + base >= LOWER_BOUND (type) - step ;;step < 0 + + by proving the reverse conditions are false using loop's initial + condition. */ + if (POINTER_TYPE_P (TREE_TYPE (base))) + code = POINTER_PLUS_EXPR; + else + code = PLUS_EXPR; + + tree stepped = fold_build2 (code, TREE_TYPE (base), base, step); + tree expanded_stepped = fold_build2 (code, TREE_TYPE (base), + expanded_base, step); + if (operand_equal_p (stepped, civ->base, 0) + || operand_equal_p (expanded_stepped, civ->base, 0)) + { + tree extreme; + + if (tree_int_cst_sign_bit (step)) + { + code = LT_EXPR; + extreme = lower_bound_in_type (type, type); + } + else + { + code = GT_EXPR; + extreme = upper_bound_in_type (type, type); + } + extreme = fold_build2 (MINUS_EXPR, type, extreme, step); + e = fold_build2 (code, boolean_type_node, base, extreme); + e = simplify_using_initial_conditions (loop, e); + if (integer_zerop (e)) + return true; + } + } + } + + return false; +} + +/* VAR is scev variable whose evolution part is constant STEP, this function + proves that VAR can't overflow by using value range info. If VAR's value + range is [MIN, MAX], it can be proven by: + MAX + step doesn't overflow ; if step > 0 + or + MIN + step doesn't underflow ; if step < 0. + + We can only do this if var is computed in every loop iteration, i.e, var's + definition has to dominate loop latch. Consider below example: + + { + unsigned int i; + + <bb 3>: + + <bb 4>: + # RANGE [0, 4294967294] NONZERO 65535 + # i_21 = PHI <0(3), i_18(9)> + if (i_21 != 0) + goto <bb 6>; + else + goto <bb 8>; + + <bb 6>: + # RANGE [0, 65533] NONZERO 65535 + _6 = i_21 + 4294967295; + # RANGE [0, 65533] NONZERO 65535 + _7 = (long unsigned int) _6; + # RANGE [0, 524264] NONZERO 524280 + _8 = _7 * 8; + # PT = nonlocal escaped + _9 = a_14 + _8; + *_9 = 0; + + <bb 8>: + # RANGE [1, 65535] NONZERO 65535 + i_18 = i_21 + 1; + if (i_18 >= 65535) + goto <bb 10>; + else + goto <bb 9>; + + <bb 9>: + goto <bb 4>; + + <bb 10>: + return; + } + + VAR _6 doesn't overflow only with pre-condition (i_21 != 0), here we + can't use _6 to prove no-overlfow for _7. In fact, var _7 takes value + sequence (4294967295, 0, 1, ..., 65533) in loop life time, rather than + (4294967295, 4294967296, ...). */ + +static bool +scev_var_range_cant_overflow (tree var, tree step, class loop *loop) +{ + tree type; + wide_int minv, maxv, diff, step_wi; + + if (TREE_CODE (step) != INTEGER_CST || !INTEGRAL_TYPE_P (TREE_TYPE (var))) + return false; + + /* Check if VAR evaluates in every loop iteration. It's not the case + if VAR is default definition or does not dominate loop's latch. */ + basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (var)); + if (!def_bb || !dominated_by_p (CDI_DOMINATORS, loop->latch, def_bb)) + return false; + + value_range r; + get_range_query (cfun)->range_of_expr (r, var); + if (r.kind () != VR_RANGE) + return false; + + /* VAR is a scev whose evolution part is STEP and value range info + is [MIN, MAX], we can prove its no-overflowness by conditions: + + type_MAX - MAX >= step ; if step > 0 + MIN - type_MIN >= |step| ; if step < 0. + + Or VAR must take value outside of value range, which is not true. */ + step_wi = wi::to_wide (step); + type = TREE_TYPE (var); + if (tree_int_cst_sign_bit (step)) + { + diff = r.lower_bound () - wi::to_wide (lower_bound_in_type (type, type)); + step_wi = - step_wi; + } + else + diff = wi::to_wide (upper_bound_in_type (type, type)) - r.upper_bound (); + + return (wi::geu_p (diff, step_wi)); +} + +/* 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). + + If VAR is a ssa variable, this function also returns false if VAR can + be proven not overflow with value range info. */ + +bool +scev_probably_wraps_p (tree var, tree base, tree step, + gimple *at_stmt, class loop *loop, + bool use_overflow_semantics) +{ + /* 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; + + /* Check if var can be proven not overflow with value range info. */ + if (var && TREE_CODE (var) == SSA_NAME + && scev_var_range_cant_overflow (var, step, loop)) + return false; + + if (loop_exits_before_overflow (base, step, at_stmt, loop)) + return false; + + /* 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 (class loop *loop) +{ + struct control_iv *civ; + class nb_iter_bound *bound; + + loop->nb_iterations = NULL; + loop->estimate_state = EST_NOT_COMPUTED; + for (bound = loop->bounds; bound;) + { + class nb_iter_bound *next = bound->next; + ggc_free (bound); + bound = next; + } + loop->bounds = NULL; + + for (civ = loop->control_ivs; civ;) + { + struct control_iv *next = civ->next; + ggc_free (civ); + civ = next; + } + loop->control_ivs = NULL; +} + +/* Frees the information on upper bounds on numbers of iterations of loops. */ + +void +free_numbers_of_iterations_estimates (function *fn) +{ + for (auto loop : loops_list (fn, 0)) + free_numbers_of_iterations_estimates (loop); +} + +/* Substitute value VAL for ssa name NAME inside expressions held + at LOOP. */ + +void +substitute_in_loop_info (class loop *loop, tree name, tree val) +{ + loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val); +} |