/* Functions to determine/estimate number of iterations of a loop.
- Copyright (C) 2004-2013 Free Software Foundation, Inc.
+ Copyright (C) 2004-2015 Free Software Foundation, Inc.
This file is part of GCC.
#include "system.h"
#include "coretypes.h"
#include "tm.h"
+#include "alias.h"
+#include "symtab.h"
#include "tree.h"
+#include "stor-layout.h"
+#include "fold-const.h"
#include "calls.h"
+#include "hard-reg-set.h"
+#include "function.h"
+#include "rtl.h"
+#include "flags.h"
+#include "insn-config.h"
+#include "expmed.h"
+#include "dojump.h"
+#include "explow.h"
+#include "emit-rtl.h"
+#include "varasm.h"
+#include "stmt.h"
#include "expr.h"
#include "tm_p.h"
+#include "predict.h"
+#include "dominance.h"
+#include "cfg.h"
#include "basic-block.h"
#include "gimple-pretty-print.h"
#include "intl.h"
+#include "tree-ssa-alias.h"
+#include "internal-fn.h"
+#include "gimple-expr.h"
#include "gimple.h"
#include "gimplify.h"
#include "gimple-iterator.h"
#include "tree-ssa-loop.h"
#include "dumpfile.h"
#include "cfgloop.h"
-#include "ggc.h"
#include "tree-chrec.h"
#include "tree-scalar-evolution.h"
#include "tree-data-ref.h"
#include "params.h"
-#include "flags.h"
#include "diagnostic-core.h"
#include "tree-inline.h"
#include "tree-pass.h"
#include "stringpool.h"
#include "tree-ssanames.h"
+#include "wide-int-print.h"
-#define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
-
/* The maximum number of dominator BBs we search for conditions
of loop header copies we use for simplifying a conditional
expression. */
{
tree type = TREE_TYPE (expr);
tree op0, op1;
- double_int off;
bool negate = false;
*var = expr;
*var = op0;
/* Always sign extend the offset. */
- off = tree_to_double_int (op1);
- off = off.sext (TYPE_PRECISION (type));
- mpz_set_double_int (offset, off, false);
+ wi::to_mpz (op1, offset, SIGNED);
if (negate)
mpz_neg (offset, offset);
break;
case INTEGER_CST:
*var = build_int_cst_type (type, 0);
- off = tree_to_double_int (expr);
- mpz_set_double_int (offset, off, TYPE_UNSIGNED (type));
+ wi::to_mpz (expr, offset, TYPE_SIGN (type));
break;
default:
determine_value_range (struct loop *loop, tree type, tree var, mpz_t off,
mpz_t min, mpz_t max)
{
- double_int minv, maxv;
+ wide_int minv, maxv;
enum value_range_type rtype = VR_VARYING;
/* If the expression is a constant, we know its value exactly. */
if (TREE_CODE (var) == SSA_NAME && INTEGRAL_TYPE_P (type))
{
edge e = loop_preheader_edge (loop);
- gimple_stmt_iterator gsi;
+ signop sgn = TYPE_SIGN (type);
+ gphi_iterator gsi;
/* Either for VAR itself... */
rtype = get_range_info (var, &minv, &maxv);
PHI argument from the loop preheader edge. */
for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
{
- gimple phi = gsi_stmt (gsi);
- double_int minc, maxc;
+ gphi *phi = gsi.phi ();
+ wide_int minc, maxc;
if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var
&& (get_range_info (gimple_phi_result (phi), &minc, &maxc)
== VR_RANGE))
}
else
{
- minv = minv.max (minc, TYPE_UNSIGNED (type));
- maxv = maxv.min (maxc, TYPE_UNSIGNED (type));
- gcc_assert (minv.cmp (maxv, TYPE_UNSIGNED (type)) <= 0);
+ minv = wi::max (minv, minc, sgn);
+ maxv = wi::min (maxv, maxc, 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))
+ {
+ rtype = get_range_info (var, &minv, &maxv);
+ break;
+ }
}
}
}
if (rtype == VR_RANGE)
{
mpz_t minm, maxm;
- gcc_assert (minv.cmp (maxv, TYPE_UNSIGNED (type)) <= 0);
+ gcc_assert (wi::le_p (minv, maxv, sgn));
mpz_init (minm);
mpz_init (maxm);
- mpz_set_double_int (minm, minv, TYPE_UNSIGNED (type));
- mpz_set_double_int (maxm, maxv, TYPE_UNSIGNED (type));
+ wi::to_mpz (minv, minm, sgn);
+ wi::to_mpz (maxv, maxm, sgn);
mpz_add (minm, minm, off);
mpz_add (maxm, maxm, off);
/* If the computation may not wrap or off is zero, then this
}
mpz_init (m);
- mpz_set_double_int (m, double_int::mask (TYPE_PRECISION (type)), true);
+ 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);
tree c0, enum tree_code cmp, tree c1,
bounds *bnds)
{
- tree varc0, varc1, tmp, ctype;
+ tree varc0, varc1, ctype;
mpz_t offc0, offc1, loffx, loffy, bnd;
bool lbound = false;
bool no_wrap = nowrap_type_p (type);
if (operand_equal_p (varx, varc1, 0))
{
- tmp = varc0; varc0 = varc1; varc1 = tmp;
+ std::swap (varc0, varc1);
mpz_swap (offc0, offc1);
cmp = swap_tree_comparison (cmp);
}
if (cmp == GT_EXPR || cmp == GE_EXPR)
{
- tmp = varx; varx = vary; vary = tmp;
+ std::swap (varx, vary);
mpz_swap (offc0, offc1);
mpz_swap (loffx, loffy);
cmp = swap_tree_comparison (cmp);
difference of two values in TYPE. */
static void
-bounds_add (bounds *bnds, double_int delta, tree type)
+bounds_add (bounds *bnds, const widest_int &delta, tree type)
{
mpz_t mdelta, max;
mpz_init (mdelta);
- mpz_set_double_int (mdelta, delta, false);
+ wi::to_mpz (delta, mdelta, SIGNED);
mpz_init (max);
- mpz_set_double_int (max, double_int::mask (TYPE_PRECISION (type)), true);
+ 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);
number_of_iterations_ne_max (mpz_t bnd, bool no_overflow, tree c, tree s,
bounds *bnds, bool exit_must_be_taken)
{
- double_int max;
+ widest_int max;
mpz_t d;
tree type = TREE_TYPE (c);
bool bnds_u_valid = ((no_overflow && exit_must_be_taken)
if (integer_onep (s)
|| (TREE_CODE (c) == INTEGER_CST
&& TREE_CODE (s) == INTEGER_CST
- && tree_to_double_int (c).mod (tree_to_double_int (s),
- TYPE_UNSIGNED (type),
- EXACT_DIV_EXPR).is_zero ())
- || (TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (c))
+ && wi::mod_trunc (c, 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 whole # of iterations analysis will fail). */
if (!no_overflow)
{
- max = double_int::mask (TYPE_PRECISION (type)
- - tree_to_uhwi (num_ending_zeros (s)));
- mpz_set_double_int (bnd, max, true);
+ max = wi::mask <widest_int> (TYPE_PRECISION (type) - wi::ctz (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. */
- mpz_set_double_int (bnd, double_int::mask (TYPE_PRECISION (type)), true);
+ 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, ... */
/* ... 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)
- mpz_set_double_int (bnd, tree_to_double_int (c), true);
+ wi::to_mpz (c, bnd, UNSIGNED);
else if (bnds_u_valid)
mpz_set (bnd, bnds->up);
}
mpz_init (d);
- mpz_set_double_int (d, tree_to_double_int (s), true);
+ wi::to_mpz (s, d, UNSIGNED);
mpz_fdiv_q (bnd, bnd, d);
mpz_clear (d);
}
mpz_init (max);
number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds,
exit_must_be_taken);
- niter->max = mpz_get_double_int (niter_type, max, false);
+ niter->max = widest_int::from (wi::from_mpz (niter_type, max, false),
+ TYPE_SIGN (niter_type));
mpz_clear (max);
/* First the trivial cases -- when the step is 1. */
tmod = fold_convert (type1, mod);
mpz_init (mmod);
- mpz_set_double_int (mmod, tree_to_double_int (mod), true);
+ wi::to_mpz (mod, mmod, UNSIGNED);
mpz_neg (mmod, mmod);
/* If the induction variable does not overflow and the exit is taken,
niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
niter->may_be_zero,
noloop);
- bounds_add (bnds, tree_to_double_int (mod), type);
+ bounds_add (bnds, wi::to_widest (mod), type);
*delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
ret = true;
tree assumption = boolean_true_node, bound, diff;
tree mbz, mbzl, mbzr, type1;
bool rolls_p, no_overflow_p;
- double_int dstep;
+ widest_int dstep;
mpz_t mstep, max;
/* We are going to compute the number of iterations as
/* First check whether the answer does not follow from the bounds we gathered
before. */
if (integer_nonzerop (iv0->step))
- dstep = tree_to_double_int (iv0->step);
+ dstep = wi::to_widest (iv0->step);
else
{
- dstep = tree_to_double_int (iv1->step).sext (TYPE_PRECISION (type));
+ dstep = wi::sext (wi::to_widest (iv1->step), TYPE_PRECISION (type));
dstep = -dstep;
}
mpz_init (mstep);
- mpz_set_double_int (mstep, dstep, true);
+ 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);
- mpz_set_double_int (max, double_int::mask (TYPE_PRECISION (type)), true);
+ 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
niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
iv1->base, iv0->base);
niter->niter = delta;
- niter->max = mpz_get_double_int (niter_type, bnds->up, false);
+ niter->max = widest_int::from (wi::from_mpz (niter_type, bnds->up, false),
+ TYPE_SIGN (niter_type));
+ niter->control.no_overflow = true;
return true;
}
mpz_init (mstep);
mpz_init (tmp);
- mpz_set_double_int (mstep, tree_to_double_int (step), true);
+ wi::to_mpz (step, mstep, UNSIGNED);
mpz_add (tmp, bnds->up, mstep);
mpz_sub_ui (tmp, tmp, 1);
mpz_fdiv_q (tmp, tmp, mstep);
- niter->max = mpz_get_double_int (niter_type, tmp, false);
+ niter->max = widest_int::from (wi::from_mpz (niter_type, tmp, false),
+ TYPE_SIGN (niter_type));
mpz_clear (mstep);
mpz_clear (tmp);
iv0->base = fold_build2 (MINUS_EXPR, type1,
iv0->base, build_int_cst (type1, 1));
- bounds_add (bnds, double_int_one, type1);
+ bounds_add (bnds, 1, type1);
return number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken,
bnds);
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 struct tree_niter_desc in tree-flow.h) are stored to NITER.
+ comments at struct 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). */
niter->assumptions = boolean_true_node;
niter->may_be_zero = boolean_false_node;
niter->niter = NULL_TREE;
- niter->max = double_int_zero;
-
+ niter->max = 0;
niter->bound = NULL_TREE;
niter->cmp = ERROR_MARK;
if (code == GE_EXPR || code == GT_EXPR
|| (code == NE_EXPR && integer_zerop (iv0->step)))
{
- SWAP (iv0, iv1);
+ std::swap (iv0, iv1);
code = swap_tree_comparison (code);
}
if (tem && integer_zerop (tem))
{
niter->niter = build_int_cst (unsigned_type_for (type), 0);
- niter->max = double_int_zero;
+ niter->max = 0;
return true;
}
fprintf (dump_file, " # of iterations ");
print_generic_expr (dump_file, niter->niter, TDF_SLIM);
fprintf (dump_file, ", bounded by ");
- dump_double_int (dump_file, niter->max, true);
+ print_decu (niter->max, dump_file);
fprintf (dump_file, "\n");
}
else
}
/* Expand definitions of ssa names in EXPR as long as they are simple
- enough, and return the new expression. */
+ enough, and return the new expression. If STOP is specified, stop
+ expanding if EXPR equals to it. */
tree
-expand_simple_operations (tree expr)
+expand_simple_operations (tree expr, tree stop)
{
unsigned i, n;
tree ret = NULL_TREE, e, ee, e1;
for (i = 0; i < n; i++)
{
e = TREE_OPERAND (expr, i);
- ee = expand_simple_operations (e);
+ ee = expand_simple_operations (e, stop);
if (e == ee)
continue;
return ret;
}
- if (TREE_CODE (expr) != SSA_NAME)
+ /* 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);
&& src->loop_father != dest->loop_father)
return expr;
- return expand_simple_operations (e);
+ return expand_simple_operations (e, stop);
}
if (gimple_code (stmt) != GIMPLE_ASSIGN)
return expr;
return e;
if (code == SSA_NAME)
- return expand_simple_operations (e);
+ return expand_simple_operations (e, stop);
return expr;
}
{
CASE_CONVERT:
/* Casts are simple. */
- ee = expand_simple_operations (e);
+ ee = expand_simple_operations (e, stop);
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);
+ ee = expand_simple_operations (e, stop);
return fold_build2 (code, TREE_TYPE (expr), ee, e1);
default:
struct tree_niter_desc *niter,
bool warn, bool every_iteration)
{
- gimple stmt;
+ gimple last;
+ gcond *stmt;
tree type;
tree op0, op1;
enum tree_code code;
return false;
niter->assumptions = boolean_false_node;
- stmt = last_stmt (exit->src);
- if (!stmt || gimple_code (stmt) != GIMPLE_COND)
+ 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. */
/* If NITER has simplified into a constant, update MAX. */
if (TREE_CODE (niter->niter) == INTEGER_CST)
- niter->max = tree_to_double_int (niter->niter);
+ niter->max = wi::to_widest (niter->niter);
if (integer_onep (niter->assumptions))
return true;
bool
finite_loop_p (struct loop *loop)
{
- double_int nit;
+ widest_int nit;
int flags;
if (flag_unsafe_loop_optimizations)
result by a chain of operations such that all but exactly one of their
operands are constants. */
-static gimple
+static gphi *
chain_of_csts_start (struct loop *loop, tree x)
{
gimple stmt = SSA_NAME_DEF_STMT (x);
if (gimple_code (stmt) == GIMPLE_PHI)
{
if (bb == loop->header)
- return stmt;
+ return as_a <gphi *> (stmt);
return NULL;
}
- if (gimple_code (stmt) != GIMPLE_ASSIGN)
+ if (gimple_code (stmt) != GIMPLE_ASSIGN
+ || gimple_assign_rhs_class (stmt) == GIMPLE_TERNARY_RHS)
return NULL;
code = gimple_assign_rhs_code (stmt);
If such phi node exists, it is returned, otherwise NULL is returned. */
-static gimple
+static gphi *
get_base_for (struct loop *loop, tree x)
{
- gimple phi;
+ gphi *phi;
tree init, next;
if (is_gimple_min_invariant (x))
{
gimple stmt;
- gcc_assert (is_gimple_min_invariant (base));
+ gcc_checking_assert (is_gimple_min_invariant (base));
if (!x)
return base;
if (gimple_code (stmt) == GIMPLE_PHI)
return base;
- gcc_assert (is_gimple_assign (stmt));
+ 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
{
tree acnd;
tree op[2], val[2], next[2], aval[2];
- gimple phi, cond;
+ gphi *phi;
+ gimple cond;
unsigned i, j;
enum tree_code cmp;
*/
-static double_int derive_constant_upper_bound_ops (tree, tree,
+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 double_int
+static widest_int
derive_constant_upper_bound_assign (gimple stmt)
{
enum tree_code code = gimple_assign_rhs_code (stmt);
is considered to be unsigned. If its type is signed, its value must
be nonnegative. */
-static double_int
+static widest_int
derive_constant_upper_bound (tree val)
{
enum tree_code code;
whose type is TYPE. The expression is considered to be unsigned. If
its type is signed, its value must be nonnegative. */
-static double_int
+static widest_int
derive_constant_upper_bound_ops (tree type, tree op0,
enum tree_code code, tree op1)
{
tree subtype, maxt;
- double_int bnd, max, mmax, cst;
+ widest_int bnd, max, mmax, cst;
gimple stmt;
if (INTEGRAL_TYPE_P (type))
else
maxt = upper_bound_in_type (type, type);
- max = tree_to_double_int (maxt);
+ max = wi::to_widest (maxt);
switch (code)
{
case INTEGER_CST:
- return tree_to_double_int (op0);
+ return wi::to_widest (op0);
CASE_CONVERT:
subtype = TREE_TYPE (op0);
/* If the bound does not fit in TYPE, max. value of TYPE could be
attained. */
- if (max.ult (bnd))
+ if (wi::ltu_p (max, bnd))
return max;
return bnd;
/* Canonicalize to OP0 - CST. Consider CST to be signed, in order to
choose the most logical way how to treat this constant regardless
of the signedness of the type. */
- cst = tree_to_double_int (op1);
- cst = cst.sext (TYPE_PRECISION (type));
+ cst = wi::sext (wi::to_widest (op1), TYPE_PRECISION (type));
if (code != MINUS_EXPR)
cst = -cst;
bnd = derive_constant_upper_bound (op0);
- if (cst.is_negative ())
+ if (wi::neg_p (cst))
{
cst = -cst;
/* Avoid CST == 0x80000... */
- if (cst.is_negative ())
- return max;;
+ if (wi::neg_p (cst))
+ return max;
/* OP0 + CST. We need to check that
BND <= MAX (type) - CST. */
mmax -= cst;
- if (bnd.ugt (mmax))
+ if (wi::ltu_p (bnd, max))
return max;
return bnd + cst;
/* 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 (bnd.ult (cst))
+ if (wi::ltu_p (bnd, cst))
return max;
if (TYPE_UNSIGNED (type))
{
tree tem = fold_binary (GE_EXPR, boolean_type_node, op0,
- double_int_to_tree (type, cst));
+ wide_int_to_tree (type, cst));
if (!tem || integer_nonzerop (tem))
return max;
}
return max;
bnd = derive_constant_upper_bound (op0);
- return bnd.udiv (tree_to_double_int (op1), FLOOR_DIV_EXPR);
+ 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 tree_to_double_int (op1);
+ return wi::to_widest (op1);
case SSA_NAME:
stmt = SSA_NAME_DEF_STMT (op0);
static void
do_warn_aggressive_loop_optimizations (struct loop *loop,
- double_int i_bound, gimple stmt)
+ widest_int i_bound, gimple stmt)
{
/* Don't warn if the loop doesn't have known constant bound. */
if (!loop->nb_iterations
|| loop->warned_aggressive_loop_optimizations
/* Only warn if undefined behavior gives us lower estimate than the
known constant bound. */
- || i_bound.ucmp (tree_to_double_int (loop->nb_iterations)) >= 0
+ || 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;
gimple estmt = last_stmt (e->src);
if (warning_at (gimple_location (stmt), OPT_Waggressive_loop_optimizations,
"iteration %E invokes undefined behavior",
- double_int_to_tree (TREE_TYPE (loop->nb_iterations),
- i_bound)))
+ wide_int_to_tree (TREE_TYPE (loop->nb_iterations),
+ i_bound)))
inform (gimple_location (estmt), "containing loop");
loop->warned_aggressive_loop_optimizations = true;
}
is taken at last when the STMT is executed BOUND + 1 times.
REALISTIC is true if BOUND is expected to be close to the real number
of iterations. UPPER is true if we are sure the loop iterates at most
- BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
+ BOUND times. I_BOUND is a widest_int upper estimate on BOUND. */
static void
-record_estimate (struct loop *loop, tree bound, double_int i_bound,
+record_estimate (struct loop *loop, tree bound, const widest_int &i_bound,
gimple at_stmt, bool is_exit, bool realistic, bool upper)
{
- double_int delta;
+ widest_int delta;
if (dump_file && (dump_flags & TDF_DETAILS))
{
upper ? "" : "probably ");
print_generic_expr (dump_file, bound, TDF_SLIM);
fprintf (dump_file, " (bounded by ");
- dump_double_int (dump_file, i_bound, true);
+ print_decu (i_bound, dump_file);
fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num);
}
if (TREE_CODE (bound) != INTEGER_CST)
realistic = false;
else
- gcc_checking_assert (i_bound == tree_to_double_int (bound));
+ gcc_checking_assert (i_bound == wi::to_widest (bound));
if (!upper && !realistic)
return;
|| loop->nb_iterations == NULL_TREE
|| TREE_CODE (loop->nb_iterations) != INTEGER_CST))
{
- struct nb_iter_bound *elt = ggc_alloc_nb_iter_bound ();
+ struct nb_iter_bound *elt = ggc_alloc<nb_iter_bound> ();
elt->bound = i_bound;
elt->stmt = at_stmt;
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 = double_int_zero;
+ delta = 0;
else
- delta = double_int_one;
- i_bound += delta;
+ delta = 1;
+ widest_int new_i_bound = i_bound + delta;
/* If an overflow occurred, ignore the result. */
- if (i_bound.ult (delta))
+ if (wi::ltu_p (new_i_bound, delta))
return;
if (upper && !is_exit)
- do_warn_aggressive_loop_optimizations (loop, i_bound, at_stmt);
- record_niter_bound (loop, i_bound, realistic, upper);
+ 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 (struct loop *loop, struct 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;
}
/* Record the estimate on number of iterations of LOOP based on the fact that
{
tree niter_bound, extreme, delta;
tree type = TREE_TYPE (base), unsigned_type;
- double_int max;
+ tree orig_base = base;
if (TREE_CODE (step) != INTEGER_CST || integer_zerop (step))
return;
if (tree_int_cst_sign_bit (step))
{
+ wide_int min, max;
extreme = fold_convert (unsigned_type, low);
- if (TREE_CODE (base) != INTEGER_CST)
+ if (TREE_CODE (orig_base) == SSA_NAME
+ && TREE_CODE (high) == INTEGER_CST
+ && INTEGRAL_TYPE_P (TREE_TYPE (orig_base))
+ && get_range_info (orig_base, &min, &max) == VR_RANGE
+ && wi::gts_p (high, max))
+ base = wide_int_to_tree (unsigned_type, max);
+ else if (TREE_CODE (base) != INTEGER_CST)
base = fold_convert (unsigned_type, high);
delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
}
else
{
+ wide_int min, max;
extreme = fold_convert (unsigned_type, high);
- if (TREE_CODE (base) != INTEGER_CST)
+ if (TREE_CODE (orig_base) == SSA_NAME
+ && TREE_CODE (low) == INTEGER_CST
+ && INTEGRAL_TYPE_P (TREE_TYPE (orig_base))
+ && get_range_info (orig_base, &min, &max) == VR_RANGE
+ && wi::gts_p (min, low))
+ base = wide_int_to_tree (unsigned_type, min);
+ else if (TREE_CODE (base) != INTEGER_CST)
base = fold_convert (unsigned_type, low);
delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
}
/* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
would get out of the range. */
niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step);
- max = derive_constant_upper_bound (niter_bound);
+ widest_int max = derive_constant_upper_bound (niter_bound);
record_estimate (loop, niter_bound, max, stmt, false, realistic, upper);
}
free (bbs);
}
-
-
-/* Compare double ints, callback for qsort. */
+/* Compare wide ints, callback for qsort. */
static int
-double_int_cmp (const void *p1, const void *p2)
+wide_int_cmp (const void *p1, const void *p2)
{
- const double_int *d1 = (const double_int *)p1;
- const double_int *d2 = (const double_int *)p2;
- if (*d1 == *d2)
- return 0;
- if (d1->ult (*d2))
- return -1;
- return 1;
+ 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 (vec<double_int> bounds, double_int bound)
+bound_index (vec<widest_int> bounds, const widest_int &bound)
{
unsigned int end = bounds.length ();
unsigned int begin = 0;
while (begin != end)
{
unsigned int middle = (begin + end) / 2;
- double_int index = bounds[middle];
+ widest_int index = bounds[middle];
if (index == bound)
return middle;
- else if (index.ult (bound))
+ else if (wi::ltu_p (index, bound))
begin = middle + 1;
else
end = middle;
static void
discover_iteration_bound_by_body_walk (struct loop *loop)
{
- pointer_map_t *bb_bounds;
struct nb_iter_bound *elt;
- vec<double_int> bounds = vNULL;
+ vec<widest_int> bounds = vNULL;
vec<vec<basic_block> > queues = vNULL;
vec<basic_block> queue = vNULL;
ptrdiff_t queue_index;
ptrdiff_t latch_index = 0;
- pointer_map_t *block_priority;
/* Discover what bounds may interest us. */
for (elt = loop->bounds; elt; elt = elt->next)
{
- double_int bound = elt->bound;
+ 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 += double_int_one;
+ bound += 1;
/* If an overflow occurred, ignore the result. */
- if (bound.is_zero ())
+ if (bound == 0)
continue;
}
if (!loop->any_upper_bound
- || bound.ult (loop->nb_iterations_upper_bound))
+ || wi::ltu_p (bound, loop->nb_iterations_upper_bound))
bounds.safe_push (bound);
}
fprintf (dump_file, " Trying to walk loop body to reduce the bound.\n");
/* Sort the bounds in decreasing order. */
- qsort (bounds.address (), bounds.length (),
- sizeof (double_int), double_int_cmp);
+ bounds.qsort (wide_int_cmp);
/* For every basic block record the lowest bound that is guaranteed to
terminate the loop. */
- bb_bounds = pointer_map_create ();
+ hash_map<basic_block, ptrdiff_t> bb_bounds;
for (elt = loop->bounds; elt; elt = elt->next)
{
- double_int bound = elt->bound;
+ widest_int bound = elt->bound;
if (!elt->is_exit)
{
- bound += double_int_one;
+ bound += 1;
/* If an overflow occurred, ignore the result. */
- if (bound.is_zero ())
+ if (bound == 0)
continue;
}
if (!loop->any_upper_bound
- || bound.ult (loop->nb_iterations_upper_bound))
+ || wi::ltu_p (bound, loop->nb_iterations_upper_bound))
{
ptrdiff_t index = bound_index (bounds, bound);
- void **entry = pointer_map_contains (bb_bounds,
- gimple_bb (elt->stmt));
+ ptrdiff_t *entry = bb_bounds.get (gimple_bb (elt->stmt));
if (!entry)
- *pointer_map_insert (bb_bounds,
- gimple_bb (elt->stmt)) = (void *)index;
+ bb_bounds.put (gimple_bb (elt->stmt), index);
else if ((ptrdiff_t)*entry > index)
- *entry = (void *)index;
+ *entry = index;
}
}
- block_priority = pointer_map_create ();
+ hash_map<basic_block, ptrdiff_t> block_priority;
/* Perform shortest path discovery loop->header ... loop->latch.
queues.safe_grow_cleared (queue_index + 1);
queue.safe_push (loop->header);
queues[queue_index] = queue;
- *pointer_map_insert (block_priority, loop->header) = (void *)queue_index;
+ block_priority.put (loop->header, queue_index);
for (; queue_index >= 0; queue_index--)
{
{
basic_block bb;
ptrdiff_t bound_index = queue_index;
- void **entry;
edge e;
edge_iterator ei;
bb = queue.pop ();
/* OK, we later inserted the BB with lower priority, skip it. */
- if ((ptrdiff_t)*pointer_map_contains (block_priority, bb) > queue_index)
+ if (*block_priority.get (bb) > queue_index)
continue;
/* See if we can improve the bound. */
- entry = pointer_map_contains (bb_bounds, bb);
- if (entry && (ptrdiff_t)*entry < bound_index)
- bound_index = (ptrdiff_t)*entry;
+ 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;
- void **entry;
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 = pointer_map_contains (block_priority, e->dest)))
+ else if (!(entry = block_priority.get (e->dest)))
{
insert = true;
- *pointer_map_insert (block_priority, e->dest) = (void *)bound_index;
+ block_priority.put (e->dest, bound_index);
}
- else if ((ptrdiff_t)*entry < bound_index)
+ else if (*entry < bound_index)
{
insert = true;
- *entry = (void *)bound_index;
+ *entry = bound_index;
}
if (insert)
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Found better loop bound ");
- dump_double_int (dump_file, bounds[latch_index], true);
+ print_decu (bounds[latch_index], dump_file);
fprintf (dump_file, "\n");
}
record_niter_bound (loop, bounds[latch_index], false, true);
queues.release ();
bounds.release ();
- pointer_map_destroy (bb_bounds);
- pointer_map_destroy (block_priority);
}
/* See if every path cross the loop goes through a statement that is known
static void
maybe_lower_iteration_bound (struct loop *loop)
{
- pointer_set_t *not_executed_last_iteration = NULL;
+ hash_set<gimple> *not_executed_last_iteration = NULL;
struct nb_iter_bound *elt;
bool found_exit = false;
vec<basic_block> queue = vNULL;
for (elt = loop->bounds; elt; elt = elt->next)
{
if (!elt->is_exit
- && elt->bound.ult (loop->nb_iterations_upper_bound))
+ && wi::ltu_p (elt->bound, loop->nb_iterations_upper_bound))
{
if (!not_executed_last_iteration)
- not_executed_last_iteration = pointer_set_create ();
- pointer_set_insert (not_executed_last_iteration, elt->stmt);
+ not_executed_last_iteration = new hash_set<gimple>;
+ not_executed_last_iteration->add (elt->stmt);
}
}
if (!not_executed_last_iteration)
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
gimple stmt = gsi_stmt (gsi);
- if (pointer_set_contains (not_executed_last_iteration, stmt))
+ if (not_executed_last_iteration->contains (stmt))
{
stmt_found = true;
break;
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 - double_int_one,
+ record_niter_bound (loop, loop->nb_iterations_upper_bound - 1,
false, true);
}
+
BITMAP_FREE (visited);
queue.release ();
- pointer_set_destroy (not_executed_last_iteration);
+ delete not_executed_last_iteration;
}
/* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
unsigned i;
struct tree_niter_desc niter_desc;
edge ex;
- double_int bound;
+ widest_int bound;
edge likely_exit;
/* Give up if we already have tried to compute an estimation. */
record_estimate (loop, niter, niter_desc.max,
last_stmt (ex->src),
true, ex == likely_exit, true);
+ record_control_iv (loop, &niter_desc);
}
exits.release ();
if (loop->header->count != 0)
{
gcov_type nit = expected_loop_iterations_unbounded (loop) + 1;
- bound = gcov_type_to_double_int (nit);
+ bound = gcov_type_to_wide_int (nit);
record_niter_bound (loop, bound, true, false);
}
&& TREE_CODE (loop->nb_iterations) == INTEGER_CST)
{
loop->any_upper_bound = true;
- loop->nb_iterations_upper_bound
- = tree_to_double_int (loop->nb_iterations);
+ loop->nb_iterations_upper_bound = wi::to_widest (loop->nb_iterations);
}
}
the function returns false, otherwise returns true. */
bool
-estimated_loop_iterations (struct loop *loop, double_int *nit)
+estimated_loop_iterations (struct loop *loop, widest_int *nit)
{
/* When SCEV information is available, try to update loop iterations
estimate. Otherwise just return whatever we recorded earlier. */
HOST_WIDE_INT
estimated_loop_iterations_int (struct loop *loop)
{
- double_int nit;
+ widest_int nit;
HOST_WIDE_INT hwi_nit;
if (!estimated_loop_iterations (loop, &nit))
return -1;
- if (!nit.fits_shwi ())
+ if (!wi::fits_shwi_p (nit))
return -1;
hwi_nit = nit.to_shwi ();
false, otherwise returns true. */
bool
-max_loop_iterations (struct loop *loop, double_int *nit)
+max_loop_iterations (struct loop *loop, widest_int *nit)
{
/* When SCEV information is available, try to update loop iterations
estimate. Otherwise just return whatever we recorded earlier. */
HOST_WIDE_INT
max_loop_iterations_int (struct loop *loop)
{
- double_int nit;
+ widest_int nit;
HOST_WIDE_INT hwi_nit;
if (!max_loop_iterations (loop, &nit))
return -1;
- if (!nit.fits_shwi ())
+ if (!wi::fits_shwi_p (nit))
return -1;
hwi_nit = nit.to_shwi ();
false, otherwise returns true. */
bool
-max_stmt_executions (struct loop *loop, double_int *nit)
+max_stmt_executions (struct loop *loop, widest_int *nit)
{
- double_int nit_minus_one;
+ widest_int nit_minus_one;
if (!max_loop_iterations (loop, nit))
return false;
nit_minus_one = *nit;
- *nit += double_int_one;
+ *nit += 1;
- return (*nit).ugt (nit_minus_one);
+ return wi::gtu_p (*nit, nit_minus_one);
}
/* Sets NIT to the estimated number of executions of the latch of the
false, otherwise returns true. */
bool
-estimated_stmt_executions (struct loop *loop, double_int *nit)
+estimated_stmt_executions (struct loop *loop, widest_int *nit)
{
- double_int nit_minus_one;
+ widest_int nit_minus_one;
if (!estimated_loop_iterations (loop, nit))
return false;
nit_minus_one = *nit;
- *nit += double_int_one;
+ *nit += 1;
- return (*nit).ugt (nit_minus_one);
+ return wi::gtu_p (*nit, nit_minus_one);
}
/* Records estimates on numbers of iterations of loops. */
struct nb_iter_bound *niter_bound,
tree niter)
{
- double_int bound = niter_bound->bound;
+ widest_int bound = niter_bound->bound;
tree nit_type = TREE_TYPE (niter), e;
enum tree_code cmp;
/* If the bound does not even fit into NIT_TYPE, it cannot tell us that
the number of iterations is small. */
- if (!double_int_fits_to_tree_p (nit_type, bound))
+ 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
gsi_next (&bsi))
if (gimple_has_side_effects (gsi_stmt (bsi)))
return false;
- bound += double_int_one;
- if (bound.is_zero ()
- || !double_int_fits_to_tree_p (nit_type, bound))
+ 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, double_int_to_tree (nit_type, bound));
+ niter, wide_int_to_tree (nit_type, bound));
return e && integer_nonzerop (e);
}
return false;
}
+/* Return true if we can prove LOOP is exited before evolution of induction
+ variabled {BASE, STEP} overflows with respect to its type bound. */
+
+static bool
+loop_exits_before_overflow (tree base, tree step,
+ gimple at_stmt, struct loop *loop)
+{
+ widest_int niter;
+ struct control_iv *civ;
+ struct 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 (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 stepped, extreme, 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;
+
+ /* 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;
+
+ stepped = fold_build2 (code, TREE_TYPE (base), base, step);
+ if (operand_equal_p (stepped, civ->base, 0))
+ {
+ 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;
+
+ continue;
+ }
+
+ /* Similar to above, only in this case we have:
+
+ {civ_base, step} = {(signed T)((unsigned T)base + step), step}
+ && TREE_TYPE (civ_base) = signed T.
+
+ We prove that below condition is satisfied:
+
+ (signed T)((unsigned T)base + step)
+ == (signed T)(unsigned T)base + step
+ == base + step
+
+ because of exact the same reason as above. This also proves
+ there is no overflow in the operation "base + step", thus the
+ induction variable {base, step} during loop iterations.
+
+ This is necessary to handle cases as below:
+
+ int foo (int *a, signed char s, signed char l)
+ {
+ signed char i;
+ for (i = s; i < l; i++)
+ a[i] = 0;
+ return 0;
+ }
+
+ The variable I is firstly converted to type unsigned char,
+ incremented, then converted back to type signed char. */
+ if (!CONVERT_EXPR_P (civ->base) || TREE_TYPE (civ->base) != type)
+ continue;
+ e = TREE_OPERAND (civ->base, 0);
+ if (TREE_CODE (e) != PLUS_EXPR
+ || TREE_CODE (TREE_OPERAND (e, 1)) != INTEGER_CST
+ || !operand_equal_p (step,
+ fold_convert (type,
+ TREE_OPERAND (e, 1)), 0))
+ continue;
+ e = TREE_OPERAND (e, 0);
+ if (!CONVERT_EXPR_P (e) || !operand_equal_p (e, unsigned_base, 0))
+ continue;
+ e = TREE_OPERAND (e, 0);
+ /* It may still be possible to prove no overflow even if condition
+ "operand_equal_p (e, base, 0)" isn't satisfied here, like below
+ example:
+
+ e : ssa_var ; unsigned long type
+ base : (int) ssa_var
+ unsigned_base : (unsigned int) ssa_var
+
+ Unfortunately this is a rare case observed during GCC profiled
+ bootstrap. See PR66638 for more information.
+
+ For now, we just skip the possibility. */
+ if (!operand_equal_p (e, base, 0))
+ continue;
+
+ 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;
+}
+
/* 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
gimple at_stmt, struct loop *loop,
bool use_overflow_semantics)
{
- tree delta, step_abs;
- tree unsigned_type, valid_niter;
- tree type = TREE_TYPE (step);
- tree e;
- double_int niter;
- struct nb_iter_bound *bound;
-
/* FIXME: We really need something like
http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
if (TREE_CODE (step) != INTEGER_CST)
return true;
- /* Don't issue signed overflow warnings. */
- fold_defer_overflow_warnings ();
-
- /* Otherwise, compute the number of iterations before we reach the
- bound of the type, and verify that the loop is exited before this
- occurs. */
- unsigned_type = unsigned_type_for (type);
- base = fold_convert (unsigned_type, base);
-
- if (tree_int_cst_sign_bit (step))
- {
- tree extreme = fold_convert (unsigned_type,
- lower_bound_in_type (type, type));
- delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
- step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
- fold_convert (unsigned_type, step));
- }
- else
- {
- tree extreme = fold_convert (unsigned_type,
- upper_bound_in_type (type, type));
- delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
- step_abs = fold_convert (unsigned_type, step);
- }
-
- valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
-
- estimate_numbers_of_iterations_loop (loop);
-
- if (max_loop_iterations (loop, &niter)
- && double_int_fits_to_tree_p (TREE_TYPE (valid_niter), niter)
- && (e = fold_binary (GT_EXPR, boolean_type_node, valid_niter,
- double_int_to_tree (TREE_TYPE (valid_niter),
- niter))) != NULL
- && integer_nonzerop (e))
- {
- fold_undefer_and_ignore_overflow_warnings ();
- return false;
- }
- 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 false;
- }
- }
-
- fold_undefer_and_ignore_overflow_warnings ();
+ 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. */
void
free_numbers_of_iterations_estimates_loop (struct loop *loop)
{
- struct nb_iter_bound *bound, *next;
+ struct control_iv *civ;
+ struct nb_iter_bound *bound;
loop->nb_iterations = NULL;
loop->estimate_state = EST_NOT_COMPUTED;
- for (bound = loop->bounds; bound; bound = next)
+ for (bound = loop->bounds; bound;)
{
- next = bound->next;
+ struct 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. */
projects / gcc.git / blobdiff