/* Functions to determine/estimate number of iterations of a loop.
- Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation,
+ Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
-Free Software Foundation; either version 2, or (at your option) any
+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
for more details.
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
#include "tree-inline.h"
#include "gmp.h"
-#define SWAP(X, Y) do { void *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
+#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
mpz_t below, up;
} bounds;
-/* Sets RESULT to VAL, taken unsigned if UNS is true and as signed
- otherwise. */
-
-static void
-mpz_set_double_int (mpz_t result, double_int val, bool uns)
-{
- bool negate = false;
- unsigned HOST_WIDE_INT vp[2];
-
- if (!uns && double_int_negative_p (val))
- {
- negate = true;
- val = double_int_neg (val);
- }
-
- vp[0] = val.low;
- vp[1] = (unsigned HOST_WIDE_INT) val.high;
- mpz_import (result, 2, -1, sizeof (HOST_WIDE_INT), 0, 0, vp);
-
- if (negate)
- mpz_neg (result, result);
-}
-
-/* Stores bounds of TYPE to MIN and MAX. */
-
-static void
-get_type_bounds (tree type, mpz_t min, mpz_t max)
-{
- if (TYPE_UNSIGNED (type))
- {
- mpz_set_ui (min, 0);
- mpz_set_double_int (max, double_int_mask (TYPE_PRECISION (type)), true);
- }
- else
- {
- double_int mx, mn;
-
- mx = double_int_mask (TYPE_PRECISION (type) - 1);
- mn = double_int_sext (double_int_add (mx, double_int_one),
- TYPE_PRECISION (type));
- mpz_set_double_int (max, mx, true);
- mpz_set_double_int (min, mn, false);
- }
-}
-
-/* Returns VAL converted to TYPE. If VAL does not fit in TYPE,
- the minimum or maximum value of the type is returned instead. */
-
-static double_int
-mpz_to_double_int (tree type, mpz_t val)
-{
- mpz_t min, max;
- unsigned HOST_WIDE_INT vp[2];
- bool negate = false;
- size_t count;
- double_int res;
-
- mpz_init (min);
- mpz_init (max);
- get_type_bounds (type, min, max);
-
- if (mpz_cmp (val, min) < 0)
- mpz_set (val, min);
- else if (mpz_cmp (val, max) > 0)
- mpz_set (val, max);
-
- if (mpz_sgn (val) < 0)
- negate = true;
-
- vp[0] = 0;
- vp[1] = 0;
- mpz_export (vp, &count, -1, sizeof (HOST_WIDE_INT), 0, 0, val);
- gcc_assert (count <= 2);
-
- mpz_clear (min);
- mpz_clear (max);
-
- res.low = vp[0];
- res.high = (HOST_WIDE_INT) vp[1];
-
- res = double_int_ext (res, TYPE_PRECISION (type), TYPE_UNSIGNED (type));
- if (negate)
- res = double_int_neg (res);
-
- return res;
-}
/* Splits expression EXPR to a variable part VAR and constant OFFSET. */
/* Fallthru. */
case PLUS_EXPR:
+ case POINTER_PLUS_EXPR:
op0 = TREE_OPERAND (expr, 0);
op1 = TREE_OPERAND (expr, 1);
/* If the computation may wrap, we know nothing about the value, except for
the range of the type. */
- get_type_bounds (type, min, max);
+ get_type_static_bounds (type, min, max);
if (!nowrap_type_p (type))
return;
tree c0, enum tree_code cmp, tree c1,
bounds *bnds)
{
- tree varc0, varc1, tmp;
+ tree varc0, varc1, tmp, ctype;
mpz_t offc0, offc1, loffx, loffy, bnd;
bool lbound = false;
bool no_wrap = nowrap_type_p (type);
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.
- TODO. */
+ 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 cases like comparing with the bounds of the type, TODO). */
+ /* 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;
int cnt = 0;
edge e;
basic_block bb;
- tree cond, c0, c1, ctype;
+ tree cond, c0, c1;
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);
c0 = TREE_OPERAND (cond, 0);
cmp = TREE_CODE (cond);
c1 = TREE_OPERAND (cond, 1);
- ctype = TREE_TYPE (c0);
-
- if (!tree_ssa_useless_type_conversion_1 (ctype, type))
- continue;
if (e->flags & EDGE_FALSE_VALUE)
cmp = invert_tree_comparison (cmp, false);
mpz_init (max);
number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds);
- niter->max = mpz_to_double_int (niter_type, max);
+ niter->max = mpz_get_double_int (niter_type, max, false);
mpz_clear (max);
/* First the trivial cases -- when the step is 1. */
mpz_t mmod;
tree assumption = boolean_true_node, bound, noloop;
bool ret = false;
+ 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 (type, mod);
+ tmod = fold_convert (type1, mod);
mpz_init (mmod);
mpz_set_double_int (mmod, tree_to_double_int (mod), true);
if (!iv1->no_overflow && !integer_zerop (mod))
{
bound = fold_build2 (MINUS_EXPR, type,
- TYPE_MAX_VALUE (type), tmod);
+ TYPE_MAX_VALUE (type1), tmod);
assumption = fold_build2 (LE_EXPR, boolean_type_node,
iv1->base, bound);
if (integer_zerop (assumption))
else
noloop = fold_build2 (GT_EXPR, boolean_type_node,
iv0->base,
- fold_build2 (PLUS_EXPR, type,
+ fold_build2 (PLUS_EXPR, type1,
iv1->base, tmod));
}
else
iv0->base - MOD <= iv1->base. */
if (!iv0->no_overflow && !integer_zerop (mod))
{
- bound = fold_build2 (PLUS_EXPR, type,
- TYPE_MIN_VALUE (type), tmod);
+ 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))
noloop = boolean_false_node;
else
noloop = fold_build2 (GT_EXPR, boolean_type_node,
- fold_build2 (MINUS_EXPR, type,
+ fold_build2 (MINUS_EXPR, type1,
iv0->base, tmod),
iv1->base);
}
struct tree_niter_desc *niter, bounds *bnds)
{
tree assumption = boolean_true_node, bound, diff;
- tree mbz, mbzl, mbzr;
+ tree mbz, mbzl, mbzr, type1;
bool rolls_p, no_overflow_p;
double_int dstep;
mpz_t mstep, 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, type,
- iv0->step, build_int_cst (type, 1));
+ 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, 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, type, iv0->base, diff);
- mbzr = 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, type,
- iv1->step, build_int_cst (type, 1));
+ diff = fold_build2 (PLUS_EXPR, type1,
+ iv1->step, build_int_cst (type1, 1));
if (!POINTER_TYPE_P (type))
{
- bound = fold_build2 (PLUS_EXPR, type,
+ bound = fold_build2 (PLUS_EXPR, type1,
TYPE_MAX_VALUE (type), diff);
assumption = fold_build2 (LE_EXPR, boolean_type_node,
iv1->base, bound);
}
- mbzl = iv0->base;
- mbzr = fold_build2 (MINUS_EXPR, type, iv1->base, diff);
+ mbzl = fold_convert (type1, iv0->base);
+ mbzr = fold_build2 (MINUS_EXPR, type1,
+ fold_convert (type1, iv1->base), diff);
}
if (!integer_nonzerop (assumption))
niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
iv1->base, iv0->base);
niter->niter = delta;
- niter->max = mpz_to_double_int (niter_type, bnds->up);
+ niter->max = mpz_get_double_int (niter_type, bnds->up, false);
return true;
}
mpz_add (tmp, bnds->up, mstep);
mpz_sub_ui (tmp, tmp, 1);
mpz_fdiv_q (tmp, tmp, mstep);
- niter->max = mpz_to_double_int (niter_type, tmp);
+ niter->max = mpz_get_double_int (niter_type, tmp, false);
mpz_clear (mstep);
mpz_clear (tmp);
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
{
if (integer_nonzerop (iv0->step))
assumption = fold_build2 (NE_EXPR, boolean_type_node,
- iv1->base, TYPE_MAX_VALUE (type));
+ iv1->base, TYPE_MAX_VALUE (type1));
else
assumption = fold_build2 (NE_EXPR, boolean_type_node,
- iv0->base, TYPE_MIN_VALUE (type));
+ iv0->base, TYPE_MIN_VALUE (type1));
if (integer_zerop (assumption))
return false;
}
if (integer_nonzerop (iv0->step))
- iv1->base = fold_build2 (PLUS_EXPR, type,
- iv1->base, build_int_cst (type, 1));
+ iv1->base = fold_build2 (PLUS_EXPR, type1,
+ iv1->base, build_int_cst (type1, 1));
else
- iv0->base = fold_build2 (MINUS_EXPR, type,
- iv0->base, build_int_cst (type, 1));
+ iv0->base = fold_build2 (MINUS_EXPR, type1,
+ iv0->base, build_int_cst (type1, 1));
- bounds_add (bnds, double_int_one, type);
+ bounds_add (bnds, double_int_one, type1);
return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite, bnds);
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file,
- "Analysing # of iterations of loop %d\n", loop->num);
+ "Analyzing # of iterations of loop %d\n", loop->num);
fprintf (dump_file, " exit condition ");
dump_affine_iv (dump_file, iv0);
/* Substitute NEW for OLD in EXPR and fold the result. */
static tree
-simplify_replace_tree (tree expr, tree old, tree new)
+simplify_replace_tree (tree expr, tree old, tree new_tree)
{
unsigned i, n;
tree ret = NULL_TREE, e, se;
if (expr == old
|| operand_equal_p (expr, old, 0))
- return unshare_expr (new);
+ return unshare_expr (new_tree);
if (!EXPR_P (expr) && !GIMPLE_STMT_P (expr))
return expr;
for (i = 0; i < n; i++)
{
e = TREE_OPERAND (expr, i);
- se = simplify_replace_tree (e, old, new);
+ se = simplify_replace_tree (e, old, new_tree);
if (e == se)
continue;
e = GIMPLE_STMT_OPERAND (stmt, 1);
if (/* Casts are simple. */
- TREE_CODE (e) != NOP_EXPR
- && TREE_CODE (e) != CONVERT_EXPR
+ !CONVERT_EXPR_P (e)
/* Copies are simple. */
&& TREE_CODE (e) != SSA_NAME
/* Assignments of invariants are simple. */
&& !is_gimple_min_invariant (e)
/* And increments and decrements by a constant are simple. */
&& !((TREE_CODE (e) == PLUS_EXPR
- || TREE_CODE (e) == MINUS_EXPR)
+ || TREE_CODE (e) == MINUS_EXPR
+ || TREE_CODE (e) == POINTER_PLUS_EXPR)
&& is_gimple_min_invariant (TREE_OPERAND (e, 1))))
return expr;
/* Returns true if EXIT is the only possible exit from LOOP. */
static bool
-loop_only_exit_p (struct loop *loop, edge exit)
+loop_only_exit_p (const struct loop *loop, const_edge exit)
{
basic_block *body;
block_stmt_iterator bsi;
be nonnegative. */
static double_int
-derive_constant_upper_bound (tree val)
+derive_constant_upper_bound (const_tree val)
{
tree type = TREE_TYPE (val);
tree op0, op1, subtype, maxt;
case INTEGER_CST:
return tree_to_double_int (val);
- case NOP_EXPR:
- case CONVERT_EXPR:
+ CASE_CONVERT:
op0 = TREE_OPERAND (val, 0);
subtype = TREE_TYPE (op0);
if (!TYPE_UNSIGNED (subtype)
return bnd;
case PLUS_EXPR:
+ case POINTER_PLUS_EXPR:
case MINUS_EXPR:
op0 = TREE_OPERAND (val, 0);
op1 = TREE_OPERAND (val, 1);
}
}
+/* Records that every statement in LOOP is executed I_BOUND times.
+ REALISTIC is true if I_BOUND is expected to be close to the real number
+ of iterations. UPPER is true if we are sure the loop iterates at most
+ I_BOUND times. */
+
+static void
+record_niter_bound (struct loop *loop, double_int i_bound, bool realistic,
+ bool upper)
+{
+ /* Update the bounds only when there is no previous estimation, or when the current
+ estimation is smaller. */
+ if (upper
+ && (!loop->any_upper_bound
+ || double_int_ucmp (i_bound, loop->nb_iterations_upper_bound) < 0))
+ {
+ loop->any_upper_bound = true;
+ loop->nb_iterations_upper_bound = i_bound;
+ }
+ if (realistic
+ && (!loop->any_estimate
+ || double_int_ucmp (i_bound, loop->nb_iterations_estimate) < 0))
+ {
+ loop->any_estimate = true;
+ loop->nb_iterations_estimate = i_bound;
+ }
+}
+
/* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT
is true if the loop is exited immediately after STMT, and this exit
is taken at last when the STMT is executed BOUND + 1 times.
- REALISTIC is true if the estimate comes from a reliable source
- (number of iterations analysis, or size of data accessed in the loop).
- I_BOUND is an unsigned double_int upper estimate on BOUND. */
+ REALISTIC is true if BOUND is expected to be close to the real number
+ of iterations. UPPER is true if we are sure the loop iterates at most
+ BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
static void
record_estimate (struct loop *loop, tree bound, double_int i_bound,
- tree at_stmt, bool is_exit, bool realistic)
+ tree at_stmt, bool is_exit, bool realistic, bool upper)
{
- struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound));
+ double_int delta;
+ edge exit;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : "");
print_generic_expr (dump_file, at_stmt, TDF_SLIM);
- fprintf (dump_file, " is executed at most ");
+ fprintf (dump_file, " is %sexecuted at most ",
+ upper ? "" : "probably ");
print_generic_expr (dump_file, bound, TDF_SLIM);
fprintf (dump_file, " (bounded by ");
dump_double_int (dump_file, i_bound, true);
fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num);
}
- elt->bound = i_bound;
- elt->stmt = at_stmt;
- elt->is_exit = is_exit;
- elt->realistic = realistic && TREE_CODE (bound) == INTEGER_CST;
- elt->next = loop->bounds;
- loop->bounds = elt;
+ /* If the I_BOUND is just an estimate of BOUND, it rarely is close to the
+ real number of iterations. */
+ if (TREE_CODE (bound) != INTEGER_CST)
+ realistic = false;
+ if (!upper && !realistic)
+ return;
+
+ /* If we have a guaranteed upper bound, record it in the appropriate
+ list. */
+ if (upper)
+ {
+ struct nb_iter_bound *elt = GGC_NEW (struct nb_iter_bound);
+
+ elt->bound = i_bound;
+ elt->stmt = at_stmt;
+ elt->is_exit = is_exit;
+ elt->next = loop->bounds;
+ loop->bounds = elt;
+ }
+
+ /* Update the number of iteration estimates according to the bound.
+ If at_stmt is an exit, then every statement in the loop is
+ executed at most BOUND + 1 times. If it is not an exit, then
+ some of the statements before it could be executed BOUND + 2
+ times, if an exit of LOOP is before stmt. */
+ exit = single_exit (loop);
+ if (is_exit
+ || (exit != NULL
+ && dominated_by_p (CDI_DOMINATORS,
+ exit->src, bb_for_stmt (at_stmt))))
+ delta = double_int_one;
+ else
+ delta = double_int_two;
+ i_bound = double_int_add (i_bound, delta);
+
+ /* If an overflow occurred, ignore the result. */
+ if (double_int_ucmp (i_bound, delta) < 0)
+ return;
+
+ record_niter_bound (loop, i_bound, realistic, upper);
}
/* Record the estimate on number of iterations of LOOP based on the fact that
the induction variable BASE + STEP * i evaluated in STMT does not wrap and
- its values belong to the range <LOW, HIGH>. DATA_SIZE_BOUNDS_P is true if
- LOW and HIGH are derived from the size of data. */
+ its values belong to the range <LOW, HIGH>. REALISTIC is true if the
+ estimated number of iterations is expected to be close to the real one.
+ UPPER is true if we are sure the induction variable does not wrap. */
static void
record_nonwrapping_iv (struct loop *loop, tree base, tree step, tree stmt,
- tree low, tree high, bool data_size_bounds_p)
+ tree low, tree high, bool realistic, bool upper)
{
tree niter_bound, extreme, delta;
tree type = TREE_TYPE (base), unsigned_type;
would get out of the range. */
niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step);
max = derive_constant_upper_bound (niter_bound);
- record_estimate (loop, niter_bound, max, stmt, false, data_size_bounds_p);
-}
-
-/* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe
- approximation of the number of iterations for LOOP. */
-
-static void
-compute_estimated_nb_iterations (struct loop *loop)
-{
- struct nb_iter_bound *bound;
- double_int bnd_val, delta;
- edge exit;
-
- gcc_assert (loop->estimate_state == EST_NOT_AVAILABLE);
-
- for (bound = loop->bounds; bound; bound = bound->next)
- {
- if (!bound->realistic)
- continue;
-
- bnd_val = bound->bound;
- /* If bound->stmt is an exit, then every statement in the loop is
- executed at most BND_VAL + 1 times. If it is not an exit, then
- some of the statements before it could be executed BND_VAL + 2
- times, if an exit of LOOP is before stmt. */
- exit = single_exit (loop);
-
- if (bound->is_exit
- || (exit != NULL
- && dominated_by_p (CDI_DOMINATORS,
- exit->src, bb_for_stmt (bound->stmt))))
- delta = double_int_one;
- else
- delta = double_int_two;
- bnd_val = double_int_add (bnd_val, delta);
-
- /* If an overflow occured, ignore the result. */
- if (double_int_ucmp (bnd_val, delta) < 0)
- continue;
-
- /* Update only when there is no previous estimation, or when the current
- estimation is smaller. */
- if (loop->estimate_state == EST_NOT_AVAILABLE
- || double_int_ucmp (bnd_val, loop->estimated_nb_iterations) < 0)
- {
- loop->estimate_state = EST_AVAILABLE;
- loop->estimated_nb_iterations = bnd_val;
- }
- }
+ record_estimate (loop, niter_bound, max, stmt, false, realistic, upper);
}
/* Returns true if REF is a reference to an array at the end of a dynamically
}
/* Determine information about number of iterations a LOOP from the index
- IDX of a data reference accessed in STMT. Callback for for_each_index. */
+ IDX of a data reference accessed in STMT. RELIABLE is true if STMT is
+ guaranteed to be executed in every iteration of LOOP. Callback for
+ for_each_index. */
struct ilb_data
{
struct loop *loop;
tree stmt;
+ bool reliable;
};
static bool
idx_infer_loop_bounds (tree base, tree *idx, void *dta)
{
- struct ilb_data *data = dta;
+ struct ilb_data *data = (struct ilb_data *) dta;
tree ev, init, step;
tree low, high, type, next;
- bool sign;
+ bool sign, upper = data->reliable, at_end = false;
struct loop *loop = data->loop;
- if (TREE_CODE (base) != ARRAY_REF
- || array_at_struct_end_p (base))
+ if (TREE_CODE (base) != ARRAY_REF)
return true;
+ /* For arrays at the end of the structure, we are not guaranteed that they
+ do not really extend over their declared size. However, for arrays of
+ size greater than one, this is unlikely to be intended. */
+ if (array_at_struct_end_p (base))
+ {
+ at_end = true;
+ upper = false;
+ }
+
ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx));
init = initial_condition (ev);
step = evolution_part_in_loop_num (ev, loop->num);
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
&& tree_int_cst_compare (next, high) <= 0)
return true;
- record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true);
+ record_nonwrapping_iv (loop, init, step, data->stmt, low, high, true, upper);
return true;
}
/* Determine information about number of iterations a LOOP from the bounds
- of arrays in the data reference REF accessed in STMT. */
+ of arrays in the data reference REF accessed in STMT. RELIABLE is true if
+ STMT is guaranteed to be executed in every iteration of LOOP.*/
static void
-infer_loop_bounds_from_ref (struct loop *loop, tree stmt, tree ref)
+infer_loop_bounds_from_ref (struct loop *loop, tree stmt, tree ref,
+ bool reliable)
{
struct ilb_data data;
data.loop = loop;
data.stmt = stmt;
+ data.reliable = reliable;
for_each_index (&ref, idx_infer_loop_bounds, &data);
}
/* Determine information about number of iterations of a LOOP from the way
- arrays are used in STMT. */
+ arrays are used in STMT. RELIABLE is true if STMT is guaranteed to be
+ executed in every iteration of LOOP. */
static void
-infer_loop_bounds_from_array (struct loop *loop, tree stmt)
+infer_loop_bounds_from_array (struct loop *loop, tree stmt, bool reliable)
{
tree call;
/* 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);
+ infer_loop_bounds_from_ref (loop, stmt, op0, reliable);
if (REFERENCE_CLASS_P (op1))
- infer_loop_bounds_from_ref (loop, stmt, op1);
+ infer_loop_bounds_from_ref (loop, stmt, op1, reliable);
}
FOR_EACH_CALL_EXPR_ARG (arg, iter, call)
if (REFERENCE_CLASS_P (arg))
- infer_loop_bounds_from_ref (loop, stmt, arg);
+ infer_loop_bounds_from_ref (loop, stmt, arg, reliable);
}
}
low = lower_bound_in_type (type, type);
high = upper_bound_in_type (type, type);
- record_nonwrapping_iv (loop, base, step, stmt, low, high, false);
+ record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
}
/* The following analyzers are extracting informations on the bounds
basic_block *bbs;
block_stmt_iterator bsi;
basic_block bb;
+ bool reliable;
bbs = get_loop_body (loop);
bb = bbs[i];
/* If BB is not executed in each iteration of the loop, we cannot
- use it to infer any information about # of iterations of the loop. */
- if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
- continue;
+ use the operations in it to infer reliable upper bound on the
+ # of iterations of the loop. However, we can use it as a guess. */
+ reliable = dominated_by_p (CDI_DOMINATORS, loop->latch, bb);
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
- infer_loop_bounds_from_array (loop, stmt);
- infer_loop_bounds_from_signedness (loop, stmt);
+ infer_loop_bounds_from_array (loop, stmt, reliable);
+
+ if (reliable)
+ infer_loop_bounds_from_signedness (loop, stmt);
}
}
free (bbs);
}
+/* Converts VAL to double_int. */
+
+static double_int
+gcov_type_to_double_int (gcov_type val)
+{
+ double_int ret;
+
+ ret.low = (unsigned HOST_WIDE_INT) val;
+ /* If HOST_BITS_PER_WIDE_INT == HOST_BITS_PER_WIDEST_INT, avoid shifting by
+ the size of type. */
+ val >>= HOST_BITS_PER_WIDE_INT - 1;
+ val >>= 1;
+ ret.high = (unsigned HOST_WIDE_INT) val;
+
+ return ret;
+}
+
/* Records estimates on numbers of iterations of LOOP. */
void
unsigned i;
struct tree_niter_desc niter_desc;
edge ex;
+ double_int bound;
/* Give up if we already have tried to compute an estimation. */
if (loop->estimate_state != EST_NOT_COMPUTED)
return;
- loop->estimate_state = EST_NOT_AVAILABLE;
+ loop->estimate_state = EST_AVAILABLE;
+ loop->any_upper_bound = false;
+ loop->any_estimate = false;
exits = get_loop_exit_edges (loop);
for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
niter);
record_estimate (loop, niter, niter_desc.max,
last_stmt (ex->src),
- true, true);
+ true, true, true);
}
VEC_free (edge, heap, exits);
infer_loop_bounds_from_undefined (loop);
- compute_estimated_nb_iterations (loop);
+
+ /* If we have a measured profile, use it to estimate the number of
+ iterations. */
+ if (loop->header->count != 0)
+ {
+ gcov_type nit = expected_loop_iterations_unbounded (loop) + 1;
+ bound = gcov_type_to_double_int (nit);
+ record_niter_bound (loop, bound, true, false);
+ }
+
+ /* If an upper bound is smaller than the realistic estimate of the
+ number of iterations, use the upper bound instead. */
+ if (loop->any_upper_bound
+ && loop->any_estimate
+ && double_int_ucmp (loop->nb_iterations_upper_bound,
+ loop->nb_iterations_estimate) < 0)
+ loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
}
/* Records estimates on numbers of iterations of loops. */
/* Returns true if statement S1 dominates statement S2. */
-static bool
+bool
stmt_dominates_stmt_p (tree s1, tree s2)
{
basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2);
2032, 2040, 0, 8, ..., but the code is still legal. */
if (chrec_contains_undetermined (base)
- || chrec_contains_undetermined (step)
- || TREE_CODE (step) != INTEGER_CST)
+ || chrec_contains_undetermined (step))
return true;
if (integer_zerop (step))
if (use_overflow_semantics && nowrap_type_p (type))
return false;
+ /* To be able to use estimates on number of iterations of the loop,
+ we must have an upper bound on the absolute value of the step. */
+ if (TREE_CODE (step) != INTEGER_CST)
+ return true;
+
/* Don't issue signed overflow warnings. */
fold_defer_overflow_warnings ();
for (bound = loop->bounds; bound; bound = next)
{
next = bound->next;
- free (bound);
+ ggc_free (bound);
}
loop->bounds = NULL;
OSDN Git Service
