/* Functions to determine/estimate number of iterations of a loop.
- Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
+ Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
Free Software Foundation, Inc.
This file is part of GCC.
#include "params.h"
#include "flags.h"
#include "diagnostic-core.h"
-#include "toplev.h"
#include "tree-inline.h"
#include "gmp.h"
*var = op0;
/* Always sign extend the offset. */
off = tree_to_double_int (op1);
- if (negate)
- off = double_int_neg (off);
off = double_int_sext (off, TYPE_PRECISION (type));
mpz_set_double_int (offset, off, false);
+ if (negate)
+ mpz_neg (offset, offset);
break;
case INTEGER_CST:
rslt = build_int_cst (type, 1);
for (; ctr; ctr--)
{
- rslt = int_const_binop (MULT_EXPR, rslt, x, 0);
- x = int_const_binop (MULT_EXPR, x, x, 0);
+ rslt = int_const_binop (MULT_EXPR, rslt, x);
+ x = int_const_binop (MULT_EXPR, x, x);
}
- rslt = int_const_binop (BIT_AND_EXPR, rslt, mask, 0);
+ 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, assuming that this exit is taken. If
- NO_OVERFLOW is true, then the control variable of the loop does not
- overflow. If NO_OVERFLOW is true or BNDS.below >= 0, then BNDS.up
- contains the upper bound on the value of C. */
+ 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)
+ bounds *bnds, bool exit_must_be_taken)
{
double_int max;
mpz_t d;
+ bool bnds_u_valid = ((no_overflow && exit_must_be_taken)
+ || mpz_sgn (bnds->below) >= 0);
+
+ if (multiple_of_p (TREE_TYPE (c), c, s))
+ {
+ /* If C is an exact multiple of S, then its value will be reached before
+ the induction variable overflows (unless the loop is exited in some
+ other way before). Note that the actual induction variable in the
+ loop (which ranges from base to final instead of from 0 to C) may
+ overflow, in which case BNDS.up will not be giving a correct upper
+ bound on C; thus, BNDS_U_VALID had to be computed in advance. */
+ no_overflow = true;
+ exit_must_be_taken = true;
+ }
- /* If the control variable does not overflow, the number of iterations is
- at most c / s. Otherwise it is at most the period of the control
- variable. */
- if (!no_overflow && !multiple_of_p (TREE_TYPE (c), c, s))
+ /* If the induction variable can overflow, the number of iterations is at
+ most the period of the control variable (or infinite, but in that case
+ the whole # of iterations analysis will fail). */
+ if (!no_overflow)
{
max = double_int_mask (TYPE_PRECISION (TREE_TYPE (c))
- tree_low_cst (num_ending_zeros (s), 1));
return;
}
- /* Determine the upper bound on C. */
- if (no_overflow || mpz_sgn (bnds->below) >= 0)
- mpz_set (bnd, bnds->up);
- else if (TREE_CODE (c) == INTEGER_CST)
- mpz_set_double_int (bnd, tree_to_double_int (c), true);
- else
- mpz_set_double_int (bnd, double_int_mask (TYPE_PRECISION (TREE_TYPE (c))),
- true);
+ /* Now we know that the induction variable does not overflow, so the loop
+ iterates at most (range of type / S) times. */
+ mpz_set_double_int (bnd, double_int_mask (TYPE_PRECISION (TREE_TYPE (c))),
+ true);
+
+ /* If the induction variable is guaranteed to reach the value of C before
+ overflow, ... */
+ if (exit_must_be_taken)
+ {
+ /* ... then we can strenghten this to C / S, and possibly we can use
+ the upper bound on C given by BNDS. */
+ if (TREE_CODE (c) == INTEGER_CST)
+ mpz_set_double_int (bnd, tree_to_double_int (c), true);
+ else if (bnds_u_valid)
+ mpz_set (bnd, bnds->up);
+ }
mpz_init (d);
mpz_set_double_int (d, tree_to_double_int (s), true);
}
mpz_init (max);
- number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds);
+ number_of_iterations_ne_max (max, iv->no_overflow, c, s, bnds,
+ exit_must_be_taken);
niter->max = mpz_get_double_int (niter_type, max, false);
mpz_clear (max);
else if (POINTER_TYPE_P (type))
noloop = fold_build2 (GT_EXPR, boolean_type_node,
iv0->base,
- fold_build2 (POINTER_PLUS_EXPR, type,
- iv1->base, tmod));
+ fold_build_pointer_plus (iv1->base, tmod));
else
noloop = fold_build2 (GT_EXPR, boolean_type_node,
iv0->base,
noloop = boolean_false_node;
else if (POINTER_TYPE_P (type))
noloop = fold_build2 (GT_EXPR, boolean_type_node,
- fold_build2 (POINTER_PLUS_EXPR, type,
- iv0->base,
- fold_build1 (NEGATE_EXPR,
- type1, tmod)),
+ fold_build_pointer_plus (iv0->base,
+ fold_build1 (NEGATE_EXPR,
+ type1, tmod)),
iv1->base);
else
noloop = fold_build2 (GT_EXPR, boolean_type_node,
if (integer_nonzerop (iv0->step))
{
if (POINTER_TYPE_P (type))
- iv1->base = fold_build2 (POINTER_PLUS_EXPR, type, iv1->base,
- build_int_cst (type1, 1));
+ 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_build2 (POINTER_PLUS_EXPR, type, iv0->base,
- fold_build1 (NEGATE_EXPR, type1,
- build_int_cst (type1, 1)));
+ 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));
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;
if (code != NE_EXPR)
return false;
- iv0->step = fold_binary_to_constant (MINUS_EXPR, type,
+ iv0->step = fold_binary_to_constant (MINUS_EXPR, step_type,
iv0->step, iv1->step);
iv0->no_overflow = false;
- iv1->step = build_int_cst (type, 0);
+ iv1->step = build_int_cst (step_type, 0);
iv1->no_overflow = true;
}
/* With -funsafe-loop-optimizations we assume that nothing bad can happen.
But if we can prove that there is overflow or some other source of weird
behavior, ignore the loop even with -funsafe-loop-optimizations. */
- if (integer_zerop (niter->assumptions))
+ if (integer_zerop (niter->assumptions) || !single_exit (loop))
return false;
if (flag_unsafe_loop_optimizations)
struct tree_niter_desc desc;
*exit = NULL;
- for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
+ FOR_EACH_VEC_ELT (edge, exits, i, ex)
{
if (!just_once_each_iteration_p (loop, ex->src))
continue;
edge ex;
struct tree_niter_desc desc;
bool finite = false;
+ int flags;
if (flag_unsafe_loop_optimizations)
return true;
- if ((TREE_READONLY (current_function_decl)
- || DECL_PURE_P (current_function_decl))
- && !DECL_LOOPING_CONST_OR_PURE_P (current_function_decl))
+ 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",
}
exits = get_loop_exit_edges (loop);
- for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
+ FOR_EACH_VEC_ELT (edge, exits, i, ex)
{
if (!just_once_each_iteration_p (loop, ex->src))
continue;
&& VEC_length (edge, exits) > 1)
return chrec_dont_know;
- for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
+ FOR_EACH_VEC_ELT (edge, exits, i, ex)
{
if (!just_once_each_iteration_p (loop, ex->src))
continue;
}
/* 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. */
+ If at_stmt is an exit or dominates the single exit from the loop,
+ then the loop latch is executed at most BOUND times, otherwise
+ it can be executed BOUND + 1 times. */
exit = single_exit (loop);
if (is_exit
|| (exit != NULL
&& dominated_by_p (CDI_DOMINATORS,
exit->src, gimple_bb (at_stmt))))
- delta = double_int_one;
+ delta = double_int_zero;
else
- delta = double_int_two;
+ delta = double_int_one;
i_bound = double_int_add (i_bound, delta);
/* If an overflow occurred, ignore the result. */
/* Unless the field is at the end of the struct, we are done. */
field = TREE_OPERAND (ref, 1);
- if (TREE_CHAIN (field))
+ if (DECL_CHAIN (field))
return false;
}
}
/* 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 (struct 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;
+
+ 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);
+
+ /* 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_array (loop, stmt, reliable);
if (reliable)
- infer_loop_bounds_from_signedness (loop, stmt);
+ {
+ infer_loop_bounds_from_signedness (loop, stmt);
+ infer_loop_bounds_from_pointer_arith (loop, stmt);
+ }
}
}
return ret;
}
-/* Records estimates on numbers of iterations of LOOP. */
+/* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
+ is true also use estimates derived from undefined behavior. */
void
-estimate_numbers_of_iterations_loop (struct loop *loop)
+estimate_numbers_of_iterations_loop (struct loop *loop, bool use_undefined_p)
{
VEC (edge, heap) *exits;
tree niter, type;
loop->any_estimate = false;
exits = get_loop_exit_edges (loop);
- for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
+ FOR_EACH_VEC_ELT (edge, exits, i, ex)
{
if (!number_of_iterations_exit (loop, ex, &niter_desc, false))
continue;
}
VEC_free (edge, heap, exits);
- infer_loop_bounds_from_undefined (loop);
+ if (use_undefined_p)
+ infer_loop_bounds_from_undefined (loop);
/* If we have a measured profile, use it to estimate the number of
iterations. */
loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
}
+/* 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 (struct loop *loop, bool conservative,
+ double_int *nit)
+{
+ estimate_numbers_of_iterations_loop (loop, true);
+ if (conservative)
+ {
+ if (!loop->any_upper_bound)
+ return false;
+
+ *nit = loop->nb_iterations_upper_bound;
+ }
+ else
+ {
+ if (!loop->any_estimate)
+ return false;
+
+ *nit = loop->nb_iterations_estimate;
+ }
+
+ return true;
+}
+
+/* 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 (struct loop *loop, bool conservative)
+{
+ double_int nit;
+ HOST_WIDE_INT hwi_nit;
+
+ if (!estimated_loop_iterations (loop, conservative, &nit))
+ return -1;
+
+ if (!double_int_fits_in_shwi_p (nit))
+ return -1;
+ hwi_nit = double_int_to_shwi (nit);
+
+ return hwi_nit < 0 ? -1 : hwi_nit;
+}
+
+/* Returns an upper bound on 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
+max_stmt_executions_int (struct loop *loop, bool conservative)
+{
+ HOST_WIDE_INT nit = estimated_loop_iterations_int (loop, conservative);
+ 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 estimated number of executions of the latch of the
+ LOOP, plus one. 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
+max_stmt_executions (struct loop *loop, bool conservative, double_int *nit)
+{
+ double_int nit_minus_one;
+
+ if (!estimated_loop_iterations (loop, conservative, nit))
+ return false;
+
+ nit_minus_one = *nit;
+
+ *nit = double_int_add (*nit, double_int_one);
+
+ return double_int_ucmp (*nit, nit_minus_one) > 0;
+}
+
/* Records estimates on numbers of iterations of loops. */
void
-estimate_numbers_of_iterations (void)
+estimate_numbers_of_iterations (bool use_undefined_p)
{
loop_iterator li;
struct loop *loop;
FOR_EACH_LOOP (li, loop, 0)
{
- estimate_numbers_of_iterations_loop (loop);
+ estimate_numbers_of_iterations_loop (loop, use_undefined_p);
}
fold_undefer_and_ignore_overflow_warnings ();
valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
- estimate_numbers_of_iterations_loop (loop);
+ estimate_numbers_of_iterations_loop (loop, true);
for (bound = loop->bounds; bound; bound = bound->next)
{
if (n_of_executions_at_most (at_stmt, bound, valid_niter))
OSDN Git Service
