}
/* Derives the upper bound BND on the number of executions of loop with exit
- condition S * i <> C, assuming that the loop is not infinite. If
+ 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. */
/* 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. NEVER_INFINITE is true if
+ 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
static bool
number_of_iterations_ne (tree type, affine_iv *iv, tree final,
- struct tree_niter_desc *niter, bool never_infinite,
+ struct tree_niter_desc *niter, bool exit_must_be_taken,
bounds *bnds)
{
tree niter_type = unsigned_type_for (type);
build_int_cst (niter_type, 1), bits);
s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
- if (!never_infinite)
+ if (!exit_must_be_taken)
{
- /* If we cannot assume that the loop is not infinite, record the
+ /* 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,
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. */
+ and will be updated by the same amount as DELTA. EXIT_MUST_BE_TAKEN is
+ true if we know that the exit must be taken eventually. */
static bool
number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1,
struct tree_niter_desc *niter,
tree *delta, tree step,
- bounds *bnds)
+ 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;
+ bool ret = false, fv_comp_no_overflow;
tree type1 = type;
if (POINTER_TYPE_P (type))
type1 = sizetype;
mpz_set_double_int (mmod, tree_to_double_int (mod), true);
mpz_neg (mmod, mmod);
+ /* If the induction variable does not overflow and the exit is taken,
+ then the computation of the final value does not overflow. This is
+ also obviously the case if the new final value is equal to the
+ current one. Finally, we postulate this for pointer type variables,
+ as the code cannot rely on the object to that the pointer points being
+ placed at the end of the address space (and more pragmatically,
+ TYPE_{MIN,MAX}_VALUE is not defined for pointers). */
+ if (integer_zerop (mod) || POINTER_TYPE_P (type))
+ fv_comp_no_overflow = true;
+ else if (!exit_must_be_taken)
+ fv_comp_no_overflow = false;
+ else
+ fv_comp_no_overflow =
+ (iv0->no_overflow && integer_nonzerop (iv0->step))
+ || (iv1->no_overflow && integer_nonzerop (iv1->step));
+
if (integer_nonzerop (iv0->step))
{
/* The final value of the iv is iv1->base + MOD, assuming that this
computation does not overflow, and that
iv0->base <= iv1->base + MOD. */
- if (!iv0->no_overflow && !integer_zerop (mod))
+ if (!fv_comp_no_overflow)
{
- bound = fold_build2 (MINUS_EXPR, type,
+ bound = fold_build2 (MINUS_EXPR, type1,
TYPE_MAX_VALUE (type1), tmod);
assumption = fold_build2 (LE_EXPR, boolean_type_node,
iv1->base, bound);
}
if (mpz_cmp (mmod, bnds->below) < 0)
noloop = boolean_false_node;
+ else if (POINTER_TYPE_P (type))
+ noloop = fold_build2 (GT_EXPR, boolean_type_node,
+ iv0->base,
+ fold_build2 (POINTER_PLUS_EXPR, type,
+ iv1->base, tmod));
else
noloop = fold_build2 (GT_EXPR, boolean_type_node,
iv0->base,
/* 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 (!iv1->no_overflow && !integer_zerop (mod))
+ if (!fv_comp_no_overflow)
{
bound = fold_build2 (PLUS_EXPR, type1,
TYPE_MIN_VALUE (type1), tmod);
}
if (mpz_cmp (mmod, bnds->below) < 0)
noloop = boolean_false_node;
+ else if (POINTER_TYPE_P (type))
+ noloop = fold_build2 (GT_EXPR, boolean_type_node,
+ fold_build2 (POINTER_PLUS_EXPR, type,
+ iv0->base,
+ fold_build1 (NEGATE_EXPR,
+ type1, tmod)),
+ iv1->base);
else
noloop = fold_build2 (GT_EXPR, boolean_type_node,
fold_build2 (MINUS_EXPR, type1,
/* 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. */
+ IV1->base - IV0->base. EXIT_MUST_BE_TAKEN is true if we know
+ that the exit must be taken eventually. */
static bool
number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
struct tree_niter_desc *niter,
- bool never_infinite ATTRIBUTE_UNUSED,
- bounds *bnds)
+ bool exit_must_be_taken, bounds *bnds)
{
tree niter_type = unsigned_type_for (type);
tree delta, step, s;
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,
- bnds))
+ exit_must_be_taken, bnds))
{
affine_iv zps;
/* 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. NEVER_INFINITE is true if
+ iterations is stored to NITER. EXIT_MUST_BE_TAKEN is true if
we know that this condition must eventually become false (we derived this
earlier, and possibly set NITER->assumptions to make sure this
is the case). BNDS bounds the difference IV1->base - IV0->base. */
static bool
number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
- struct tree_niter_desc *niter, bool never_infinite,
+ struct tree_niter_desc *niter, bool exit_must_be_taken,
bounds *bnds)
{
tree assumption;
/* 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. */
+ 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 (!never_infinite)
+ 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 (type1));
+ iv1->base, TYPE_MAX_VALUE (type));
else
assumption = fold_build2 (NE_EXPR, boolean_type_node,
- iv0->base, TYPE_MIN_VALUE (type1));
+ iv0->base, TYPE_MIN_VALUE (type));
if (integer_zerop (assumption))
return false;
}
if (integer_nonzerop (iv0->step))
- iv1->base = fold_build2 (PLUS_EXPR, type1,
- iv1->base, build_int_cst (type1, 1));
+ {
+ if (POINTER_TYPE_P (type))
+ iv1->base = fold_build2 (POINTER_PLUS_EXPR, type, iv1->base,
+ build_int_cst (type1, 1));
+ else
+ iv1->base = fold_build2 (PLUS_EXPR, type1, iv1->base,
+ build_int_cst (type1, 1));
+ }
+ else if (POINTER_TYPE_P (type))
+ iv0->base = fold_build2 (POINTER_PLUS_EXPR, type, iv0->base,
+ fold_build1 (NEGATE_EXPR, type1,
+ build_int_cst (type1, 1)));
else
iv0->base = fold_build2 (MINUS_EXPR, type1,
iv0->base, build_int_cst (type1, 1));
bounds_add (bnds, double_int_one, type1);
- return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite, bnds);
+ return number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken,
+ bnds);
}
/* Dumps description of affine induction variable IV to FILE. */
affine_iv *iv1, struct tree_niter_desc *niter,
bool only_exit)
{
- bool never_infinite, ret;
+ bool exit_must_be_taken = false, ret;
bounds bnds;
/* The meaning of these assumptions is this:
code = swap_tree_comparison (code);
}
- if (!only_exit)
- {
- /* If this is not the only possible exit from the loop, the information
- that the induction variables cannot overflow as derived from
- signedness analysis cannot be relied upon. We use them e.g. in the
- following way: given loop for (i = 0; i <= n; i++), if i is
- signed, it cannot overflow, thus this loop is equivalent to
- for (i = 0; i < n + 1; i++); however, if n == MAX, but the loop
- is exited in some other way before i overflows, this transformation
- is incorrect (the new loop exits immediately). */
- iv0->no_overflow = false;
- iv1->no_overflow = false;
- }
-
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). The
- restrictions on pointer arithmetics and comparisons of pointers
- ensure that using the no-overflow assumptions is correct in this
- case even if ONLY_EXIT is false. */
+ 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, the loop obviously
- cannot be infinite. */
- if (!integer_zerop (iv0->step) && iv0->no_overflow)
- never_infinite = true;
- else if (!integer_zerop (iv1->step) && iv1->no_overflow)
- never_infinite = true;
- else
- never_infinite = false;
+ /* If the control induction variable does not overflow and the only exit
+ from the loop is the one that we analyze, we know it must be taken
+ eventually. */
+ if (only_exit)
+ {
+ if (!integer_zerop (iv0->step) && iv0->no_overflow)
+ exit_must_be_taken = true;
+ else if (!integer_zerop (iv1->step) && iv1->no_overflow)
+ exit_must_be_taken = true;
+ }
/* We can handle the case when neither of the sides of the comparison is
invariant, provided that the test is NE_EXPR. This rarely occurs in
case NE_EXPR:
gcc_assert (integer_zerop (iv1->step));
ret = number_of_iterations_ne (type, iv0, iv1->base, niter,
- never_infinite, &bnds);
+ exit_must_be_taken, &bnds);
break;
case LT_EXPR:
- ret = number_of_iterations_lt (type, iv0, iv1, niter, never_infinite,
+ ret = number_of_iterations_lt (type, iv0, iv1, niter, exit_must_be_taken,
&bnds);
break;
case LE_EXPR:
- ret = number_of_iterations_le (type, iv0, iv1, niter, never_infinite,
+ ret = number_of_iterations_le (type, iv0, iv1, niter, exit_must_be_taken,
&bnds);
break;
switch (code)
{
- case NOP_EXPR:
- case CONVERT_EXPR:
+ CASE_CONVERT:
/* Casts are simple. */
ee = expand_simple_operations (e);
return fold_build1 (code, TREE_TYPE (expr), ee);
&& !POINTER_TYPE_P (type))
return false;
- if (!simple_iv (loop, stmt, op0, &iv0, false))
+ if (!simple_iv (loop, loop_containing_stmt (stmt), op0, &iv0, false))
return false;
- if (!simple_iv (loop, stmt, op1, &iv1, false))
+ if (!simple_iv (loop, loop_containing_stmt (stmt), op1, &iv1, false))
return false;
/* We don't want to see undefined signed overflow warnings while
? N_("assuming that the loop counter does not overflow")
: N_("cannot optimize loop, the loop counter may overflow");
- if (LOCATION_LINE (loc) > 0)
- warning (OPT_Wunsafe_loop_optimizations, "%H%s", &loc, gettext (wording));
- else
- warning (OPT_Wunsafe_loop_optimizations, "%s", gettext (wording));
+ warning_at ((LOCATION_LINE (loc) > 0) ? loc : input_location,
+ OPT_Wunsafe_loop_optimizations, "%s", gettext (wording));
}
return flag_unsafe_loop_optimizations;
return niter ? niter : chrec_dont_know;
}
+/* Return true if loop is known to have bounded number of iterations. */
+
+bool
+finite_loop_p (struct loop *loop)
+{
+ unsigned i;
+ VEC (edge, heap) *exits = get_loop_exit_edges (loop);
+ edge ex;
+ struct tree_niter_desc desc;
+ bool finite = false;
+
+ 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))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Found loop %i to be finite: it is within pure or const function.\n",
+ loop->num);
+ return true;
+ }
+
+ exits = get_loop_exit_edges (loop);
+ for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
+ {
+ if (!just_once_each_iteration_p (loop, ex->src))
+ continue;
+
+ if (number_of_iterations_exit (loop, ex, &desc, false))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Found loop %i to be finite: iterating ", loop->num);
+ print_generic_expr (dump_file, desc.niter, TDF_SLIM);
+ fprintf (dump_file, " times\n");
+ }
+ finite = true;
+ break;
+ }
+ }
+ VEC_free (edge, heap, exits);
+ return finite;
+}
+
/*
Analysis of a number of iterations of a loop by a brute-force evaluation.
code = gimple_assign_rhs_code (stmt);
if (gimple_references_memory_p (stmt)
- /* Before alias information is computed, operand scanning marks
- statements that write memory volatile. However, the statements
- that only read memory are not marked, thus gimple_references_memory_p
- returns false for them. */
|| TREE_CODE_CLASS (code) == tcc_reference
- || TREE_CODE_CLASS (code) == tcc_declaration
- || SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF) == NULL_DEF_OPERAND_P)
+ || (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_USE_OPERAND_P)
+ if (use == NULL_TREE)
return NULL;
return chain_of_csts_start (loop, use);
tree niter = NULL_TREE, aniter;
*exit = NULL;
+
+ /* Loops with multiple exits are expensive to handle and less important. */
+ if (!flag_expensive_optimizations
+ && VEC_length (edge, exits) > 1)
+ return chrec_dont_know;
+
for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
{
if (!just_once_each_iteration_p (loop, ex->src))
{
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;
/* If we can use the fact that signed and pointer arithmetics does not
wrap, we are done. */
- if (use_overflow_semantics && nowrap_type_p (type))
+ 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,
OSDN Git Service
