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, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
#include "config.h"
#include "system.h"
#include "basic-block.h"
#include "output.h"
#include "diagnostic.h"
+#include "intl.h"
#include "tree-flow.h"
#include "tree-dump.h"
#include "cfgloop.h"
#include "tree-data-ref.h"
#include "params.h"
#include "flags.h"
+#include "toplev.h"
#include "tree-inline.h"
#define SWAP(X, Y) do { void *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
rslt = build_int_cst_type (type, 1);
for (; ctr; ctr--)
{
- rslt = fold_binary_to_constant (MULT_EXPR, type, rslt, x);
- x = fold_binary_to_constant (MULT_EXPR, type, x, x);
+ rslt = int_const_binop (MULT_EXPR, rslt, x, 0);
+ x = int_const_binop (MULT_EXPR, x, x, 0);
}
- rslt = fold_binary_to_constant (BIT_AND_EXPR, type, rslt, mask);
+ rslt = int_const_binop (BIT_AND_EXPR, rslt, mask, 0);
}
return rslt;
}
-/* Determine the number of iterations according to condition (for staying
- inside loop) which compares two induction variables using comparison
- operator CODE. The induction variable on left side of the comparison
- has base BASE0 and step STEP0. the right-hand side one has base
- BASE1 and step STEP1. Both induction variables must have type TYPE,
- which must be an integer or pointer type. STEP0 and STEP1 must be
- constants (or NULL_TREE, which is interpreted as constant zero).
-
- The results (number of iterations and assumptions as described in
- comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
- In case we are unable to determine number of iterations, contents of
- this structure is unchanged. */
+/* 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
+ we know that the loop cannot be infinite (we derived this
+ earlier, and possibly set NITER->assumptions to make sure this
+ is the case. */
-static void
-number_of_iterations_cond (tree type, tree base0, tree step0,
- enum tree_code code, tree base1, tree step1,
- struct tree_niter_desc *niter)
+static bool
+number_of_iterations_ne (tree type, affine_iv *iv, tree final,
+ struct tree_niter_desc *niter, bool never_infinite)
{
- tree step, delta, mmin, mmax;
- tree may_xform, bound, s, d, tmp;
- bool was_sharp = false;
- tree assumption;
- tree assumptions = boolean_true_node;
- tree noloop_assumptions = boolean_false_node;
- tree niter_type, signed_niter_type;
- tree bits;
+ tree niter_type = unsigned_type_for (type);
+ tree s, c, d, bits, assumption, tmp, bound;
- /* The meaning of these assumptions is this:
- if !assumptions
- then the rest of information does not have to be valid
- if noloop_assumptions then the loop does not have to roll
- (but it is only conservative approximation, i.e. it only says that
- if !noloop_assumptions, then the loop does not end before the computed
- number of iterations) */
-
- /* Make < comparison from > ones. */
- if (code == GE_EXPR
- || code == GT_EXPR)
+ niter->control = *iv;
+ niter->bound = final;
+ niter->cmp = NE_EXPR;
+
+ /* Rearrange the terms so that we get inequality s * i <> c, with s
+ positive. Also cast everything to the unsigned type. */
+ if (tree_int_cst_sign_bit (iv->step))
{
- SWAP (base0, base1);
- SWAP (step0, step1);
- code = swap_tree_comparison (code);
+ s = fold_convert (niter_type,
+ fold_build1 (NEGATE_EXPR, type, iv->step));
+ c = fold_build2 (MINUS_EXPR, niter_type,
+ fold_convert (niter_type, iv->base),
+ fold_convert (niter_type, final));
}
-
- /* 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
- practice, but it is simple enough to manage. */
- if (!zero_p (step0) && !zero_p (step1))
+ else
{
- if (code != NE_EXPR)
- return;
+ s = fold_convert (niter_type, iv->step);
+ c = fold_build2 (MINUS_EXPR, niter_type,
+ fold_convert (niter_type, final),
+ fold_convert (niter_type, iv->base));
+ }
- step0 = fold_binary_to_constant (MINUS_EXPR, type, step0, step1);
- step1 = NULL_TREE;
+ /* First the trivial cases -- when the step is 1. */
+ if (integer_onep (s))
+ {
+ niter->niter = c;
+ return true;
}
- /* If the result is a constant, the loop is weird. More precise handling
- would be possible, but the situation is not common enough to waste time
- on it. */
- if (zero_p (step0) && zero_p (step1))
- return;
+ /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
+ is infinite. Otherwise, the number of iterations is
+ (inverse(s/d) * (c/d)) mod (size of mode/d). */
+ bits = num_ending_zeros (s);
+ bound = build_low_bits_mask (niter_type,
+ (TYPE_PRECISION (niter_type)
+ - tree_low_cst (bits, 1)));
- /* Ignore loops of while (i-- < 10) type. */
- if (code != NE_EXPR)
- {
- if (step0 && !tree_expr_nonnegative_p (step0))
- return;
+ d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
+ build_int_cst_type (niter_type, 1), bits);
+ s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
- if (!zero_p (step1) && tree_expr_nonnegative_p (step1))
- return;
+ if (!never_infinite)
+ {
+ /* If we cannot assume that the loop is not infinite, record the
+ assumptions for divisibility of c. */
+ assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
+ assumption = fold_build2 (EQ_EXPR, boolean_type_node,
+ assumption, build_int_cst (niter_type, 0));
+ if (!nonzero_p (assumption))
+ niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
+ niter->assumptions, assumption);
}
+
+ c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d);
+ tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound));
+ niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
+ return true;
+}
- if (POINTER_TYPE_P (type))
+/* Checks whether we can determine the final value of the control variable
+ of the loop with ending condition IV0 < IV1 (computed in TYPE).
+ DELTA is the difference IV1->base - IV0->base, STEP is the absolute value
+ of the step. The assumptions necessary to ensure that the computation
+ of the final value does not overflow are recorded in NITER. If we
+ find the final value, we adjust DELTA and return TRUE. Otherwise
+ we return false. */
+
+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)
+{
+ tree niter_type = TREE_TYPE (step);
+ tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
+ tree tmod;
+ tree assumption = boolean_true_node, bound, noloop;
+
+ if (TREE_CODE (mod) != INTEGER_CST)
+ return false;
+ if (nonzero_p (mod))
+ mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
+ tmod = fold_convert (type, mod);
+
+ if (nonzero_p (iv0->step))
{
- /* We assume pointer arithmetic never overflows. */
- mmin = mmax = NULL_TREE;
+ /* 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 (!iv1->no_overflow && !zero_p (mod))
+ {
+ bound = fold_build2 (MINUS_EXPR, type,
+ TYPE_MAX_VALUE (type), tmod);
+ assumption = fold_build2 (LE_EXPR, boolean_type_node,
+ iv1->base, bound);
+ if (zero_p (assumption))
+ return false;
+ }
+ noloop = fold_build2 (GT_EXPR, boolean_type_node,
+ iv0->base,
+ fold_build2 (PLUS_EXPR, type,
+ iv1->base, tmod));
}
else
{
- mmin = TYPE_MIN_VALUE (type);
- mmax = TYPE_MAX_VALUE (type);
+ /* 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 (!iv0->no_overflow && !zero_p (mod))
+ {
+ bound = fold_build2 (PLUS_EXPR, type,
+ TYPE_MIN_VALUE (type), tmod);
+ assumption = fold_build2 (GE_EXPR, boolean_type_node,
+ iv0->base, bound);
+ if (zero_p (assumption))
+ return false;
+ }
+ noloop = fold_build2 (GT_EXPR, boolean_type_node,
+ fold_build2 (MINUS_EXPR, type,
+ iv0->base, tmod),
+ iv1->base);
}
- /* Some more condition normalization. We must record some assumptions
- due to overflows. */
+ if (!nonzero_p (assumption))
+ niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
+ niter->assumptions,
+ assumption);
+ if (!zero_p (noloop))
+ niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
+ niter->may_be_zero,
+ noloop);
+ *delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
+ return true;
+}
+
+/* Add assertions to NITER that ensure that the control variable of the loop
+ with ending condition IV0 < IV1 does not overflow. Types of IV0 and IV1
+ are TYPE. Returns false if we can prove that there is an overflow, true
+ otherwise. STEP is the absolute value of the step. */
+
+static bool
+assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
+ struct tree_niter_desc *niter, tree step)
+{
+ tree bound, d, assumption, diff;
+ tree niter_type = TREE_TYPE (step);
- if (code == LT_EXPR)
+ if (nonzero_p (iv0->step))
{
- /* We want to take care only of <=; this is easy,
- as in cases the overflow would make the transformation unsafe the loop
- does not roll. Seemingly it would make more sense to want to take
- care of <, as NE is more similar to it, but the problem is that here
- the transformation would be more difficult due to possibly infinite
- loops. */
- if (zero_p (step0))
+ /* for (i = iv0->base; i < iv1->base; i += iv0->step) */
+ if (iv0->no_overflow)
+ return true;
+
+ /* If iv0->base is a constant, we can determine the last value before
+ overflow precisely; otherwise we conservatively assume
+ MAX - STEP + 1. */
+
+ if (TREE_CODE (iv0->base) == INTEGER_CST)
{
- if (mmax)
- assumption = fold_build2 (EQ_EXPR, boolean_type_node, base0, mmax);
- else
- assumption = boolean_false_node;
- if (nonzero_p (assumption))
- goto zero_iter;
- base0 = fold_build2 (PLUS_EXPR, type, base0,
- build_int_cst_type (type, 1));
+ d = fold_build2 (MINUS_EXPR, niter_type,
+ fold_convert (niter_type, TYPE_MAX_VALUE (type)),
+ fold_convert (niter_type, iv0->base));
+ diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
}
else
+ diff = fold_build2 (MINUS_EXPR, niter_type, step,
+ build_int_cst_type (niter_type, 1));
+ bound = fold_build2 (MINUS_EXPR, type,
+ TYPE_MAX_VALUE (type), fold_convert (type, diff));
+ assumption = fold_build2 (LE_EXPR, boolean_type_node,
+ iv1->base, bound);
+ }
+ else
+ {
+ /* for (i = iv1->base; i > iv0->base; i += iv1->step) */
+ if (iv1->no_overflow)
+ return true;
+
+ if (TREE_CODE (iv1->base) == INTEGER_CST)
{
- if (mmin)
- assumption = fold_build2 (EQ_EXPR, boolean_type_node, base1, mmin);
- else
- assumption = boolean_false_node;
- if (nonzero_p (assumption))
- goto zero_iter;
- base1 = fold_build2 (MINUS_EXPR, type, base1,
- build_int_cst_type (type, 1));
+ d = fold_build2 (MINUS_EXPR, niter_type,
+ fold_convert (niter_type, iv1->base),
+ fold_convert (niter_type, TYPE_MIN_VALUE (type)));
+ diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
}
- noloop_assumptions = assumption;
- code = LE_EXPR;
-
- /* It will be useful to be able to tell the difference once more in
- <= -> != reduction. */
- was_sharp = true;
+ else
+ diff = fold_build2 (MINUS_EXPR, niter_type, step,
+ build_int_cst_type (niter_type, 1));
+ bound = fold_build2 (PLUS_EXPR, type,
+ TYPE_MIN_VALUE (type), fold_convert (type, diff));
+ assumption = fold_build2 (GE_EXPR, boolean_type_node,
+ iv0->base, bound);
}
- /* Take care of trivially infinite loops. */
- if (code != NE_EXPR)
- {
- if (zero_p (step0)
- && mmin
- && operand_equal_p (base0, mmin, 0))
- return;
- if (zero_p (step1)
- && mmax
- && operand_equal_p (base1, mmax, 0))
- return;
- }
+ if (zero_p (assumption))
+ return false;
+ if (!nonzero_p (assumption))
+ niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
+ niter->assumptions, assumption);
+
+ iv0->no_overflow = true;
+ iv1->no_overflow = true;
+ return true;
+}
- /* If we can we want to take care of NE conditions instead of size
- comparisons, as they are much more friendly (most importantly
- this takes care of special handling of loops with step 1). We can
- do it if we first check that upper bound is greater or equal to
- lower bound, their difference is constant c modulo step and that
- there is not an overflow. */
- if (code != NE_EXPR)
+/* Add an assumption to NITER that a loop whose ending condition
+ is IV0 < IV1 rolls. TYPE is the type of the control iv. */
+
+static void
+assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
+ struct tree_niter_desc *niter)
+{
+ tree assumption = boolean_true_node, bound, diff;
+ tree mbz, mbzl, mbzr;
+
+ if (nonzero_p (iv0->step))
{
- if (zero_p (step0))
- step = fold_unary_to_constant (NEGATE_EXPR, type, step1);
- else
- step = step0;
- delta = build2 (MINUS_EXPR, type, base1, base0);
- delta = fold_build2 (FLOOR_MOD_EXPR, type, delta, step);
- may_xform = boolean_false_node;
+ diff = fold_build2 (MINUS_EXPR, type,
+ iv0->step, build_int_cst_type (type, 1));
- if (TREE_CODE (delta) == INTEGER_CST)
+ /* 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))
{
- tmp = fold_binary_to_constant (MINUS_EXPR, type, step,
- build_int_cst_type (type, 1));
- if (was_sharp
- && operand_equal_p (delta, tmp, 0))
- {
- /* A special case. We have transformed condition of type
- for (i = 0; i < 4; i += 4)
- into
- for (i = 0; i <= 3; i += 4)
- obviously if the test for overflow during that transformation
- passed, we cannot overflow here. Most importantly any
- loop with sharp end condition and step 1 falls into this
- category, so handling this case specially is definitely
- worth the troubles. */
- may_xform = boolean_true_node;
- }
- else if (zero_p (step0))
- {
- if (!mmin)
- may_xform = boolean_true_node;
- else
- {
- bound = fold_binary_to_constant (PLUS_EXPR, type,
- mmin, step);
- bound = fold_binary_to_constant (MINUS_EXPR, type,
- bound, delta);
- may_xform = fold_build2 (LE_EXPR, boolean_type_node,
- bound, base0);
- }
- }
- else
- {
- if (!mmax)
- may_xform = boolean_true_node;
- else
- {
- bound = fold_binary_to_constant (MINUS_EXPR, type,
- mmax, step);
- bound = fold_binary_to_constant (PLUS_EXPR, type,
- bound, delta);
- may_xform = fold_build2 (LE_EXPR, boolean_type_node,
- base1, bound);
- }
- }
+ bound = fold_build2 (PLUS_EXPR, type,
+ TYPE_MIN_VALUE (type), diff);
+ assumption = fold_build2 (GE_EXPR, boolean_type_node,
+ iv0->base, bound);
}
- if (!zero_p (may_xform))
- {
- /* We perform the transformation always provided that it is not
- completely senseless. This is OK, as we would need this assumption
- to determine the number of iterations anyway. */
- if (!nonzero_p (may_xform))
- assumptions = may_xform;
-
- if (zero_p (step0))
- {
- base0 = fold_build2 (PLUS_EXPR, type, base0, delta);
- base0 = fold_build2 (MINUS_EXPR, type, base0, step);
- }
- else
- {
- base1 = fold_build2 (MINUS_EXPR, type, base1, delta);
- base1 = fold_build2 (PLUS_EXPR, type, base1, step);
- }
+ /* 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;
+ }
+ else
+ {
+ diff = fold_build2 (PLUS_EXPR, type,
+ iv1->step, build_int_cst_type (type, 1));
- assumption = fold_build2 (GT_EXPR, boolean_type_node, base0, base1);
- noloop_assumptions = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
- noloop_assumptions, assumption);
- code = NE_EXPR;
+ if (!POINTER_TYPE_P (type))
+ {
+ bound = fold_build2 (PLUS_EXPR, type,
+ 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);
}
- /* Count the number of iterations. */
- niter_type = unsigned_type_for (type);
- signed_niter_type = signed_type_for (type);
+ mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
+
+ if (!nonzero_p (assumption))
+ niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
+ niter->assumptions, assumption);
+ if (!zero_p (mbz))
+ niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
+ niter->may_be_zero, mbz);
+}
+
+/* Determines number of iterations of loop whose ending condition
+ is IV0 < IV1. TYPE is the type of the iv. The number of
+ iterations is stored to NITER. */
+
+static bool
+number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
+ struct tree_niter_desc *niter,
+ bool never_infinite ATTRIBUTE_UNUSED)
+{
+ tree niter_type = unsigned_type_for (type);
+ tree delta, step, s;
- if (code == NE_EXPR)
+ if (nonzero_p (iv0->step))
{
- /* Everything we do here is just arithmetics modulo size of mode. This
- makes us able to do more involved computations of number of iterations
- than in other cases. First transform the condition into shape
- s * i <> c, with s positive. */
- base1 = fold_build2 (MINUS_EXPR, type, base1, base0);
- base0 = NULL_TREE;
- if (!zero_p (step1))
- step0 = fold_unary_to_constant (NEGATE_EXPR, type, step1);
- step1 = NULL_TREE;
- if (!tree_expr_nonnegative_p (fold_convert (signed_niter_type, step0)))
- {
- step0 = fold_unary_to_constant (NEGATE_EXPR, type, step0);
- base1 = fold_build1 (NEGATE_EXPR, type, base1);
- }
+ niter->control = *iv0;
+ niter->cmp = LT_EXPR;
+ niter->bound = iv1->base;
+ }
+ else
+ {
+ niter->control = *iv1;
+ niter->cmp = GT_EXPR;
+ niter->bound = iv0->base;
+ }
- base1 = fold_convert (niter_type, base1);
- step0 = fold_convert (niter_type, step0);
+ delta = fold_build2 (MINUS_EXPR, niter_type,
+ fold_convert (niter_type, iv1->base),
+ fold_convert (niter_type, iv0->base));
- /* Let nsd (step, size of mode) = d. If d does not divide c, the loop
- is infinite. Otherwise, the number of iterations is
- (inverse(s/d) * (c/d)) mod (size of mode/d). */
- bits = num_ending_zeros (step0);
- d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
- build_int_cst_type (niter_type, 1), bits);
- s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, step0, bits);
+ /* First handle the special case that the step is +-1. */
+ if ((iv0->step && integer_onep (iv0->step)
+ && zero_p (iv1->step))
+ || (iv1->step && integer_all_onesp (iv1->step)
+ && zero_p (iv0->step)))
+ {
+ /* for (i = iv0->base; i < iv1->base; i++)
- bound = build_low_bits_mask (niter_type,
- (TYPE_PRECISION (niter_type)
- - tree_low_cst (bits, 1)));
+ or
- assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, base1, d);
- assumption = fold_build2 (EQ_EXPR, boolean_type_node,
- assumption,
- build_int_cst (niter_type, 0));
- assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
- assumptions, assumption);
-
- tmp = fold_build2 (EXACT_DIV_EXPR, niter_type, base1, d);
- tmp = fold_build2 (MULT_EXPR, niter_type, tmp, inverse (s, bound));
- niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
+ for (i = iv1->base; i > iv0->base; i--).
+
+ In both cases # of iterations is iv1->base - iv0->base, assuming that
+ iv1->base >= iv0->base. */
+ niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
+ iv1->base, iv0->base);
+ niter->niter = delta;
+ return true;
}
+
+ if (nonzero_p (iv0->step))
+ step = fold_convert (niter_type, iv0->step);
else
+ step = fold_convert (niter_type,
+ fold_build1 (NEGATE_EXPR, type, iv1->step));
+
+ /* If we can determine the final value of the control iv exactly, we can
+ transform the condition to != comparison. In particular, this will be
+ the case if DELTA is constant. */
+ if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step))
{
- if (zero_p (step1))
- /* Condition in shape a + s * i <= b
- We must know that b + s does not overflow and a <= b + s and then we
- can compute number of iterations as (b + s - a) / s. (It might
- seem that we in fact could be more clever about testing the b + s
- overflow condition using some information about b - a mod s,
- but it was already taken into account during LE -> NE transform). */
- {
- if (mmax)
- {
- bound = fold_binary_to_constant (MINUS_EXPR, type, mmax, step0);
- assumption = fold_build2 (LE_EXPR, boolean_type_node,
- base1, bound);
- assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
- assumptions, assumption);
- }
+ affine_iv zps;
- step = step0;
- tmp = fold_build2 (PLUS_EXPR, type, base1, step0);
- assumption = fold_build2 (GT_EXPR, boolean_type_node, base0, tmp);
- delta = fold_build2 (PLUS_EXPR, type, base1, step);
- delta = fold_build2 (MINUS_EXPR, type, delta, base0);
- delta = fold_convert (niter_type, delta);
- }
- else
- {
- /* Condition in shape a <= b - s * i
- We must know that a - s does not overflow and a - s <= b and then
- we can again compute number of iterations as (b - (a - s)) / s. */
- if (mmin)
- {
- bound = fold_binary_to_constant (MINUS_EXPR, type, mmin, step1);
- assumption = fold_build2 (LE_EXPR, boolean_type_node,
- bound, base0);
- assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
- assumptions, assumption);
- }
- step = fold_build1 (NEGATE_EXPR, type, step1);
- tmp = fold_build2 (PLUS_EXPR, type, base0, step1);
- assumption = fold_build2 (GT_EXPR, boolean_type_node, tmp, base1);
- delta = fold_build2 (MINUS_EXPR, type, base0, step);
- delta = fold_build2 (MINUS_EXPR, type, base1, delta);
- delta = fold_convert (niter_type, delta);
- }
- noloop_assumptions = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
- noloop_assumptions, assumption);
- delta = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta,
- fold_convert (niter_type, step));
- niter->niter = delta;
+ zps.base = build_int_cst_type (niter_type, 0);
+ zps.step = step;
+ /* number_of_iterations_lt_to_ne will add assumptions that ensure that
+ zps does not overflow. */
+ zps.no_overflow = true;
+
+ return number_of_iterations_ne (type, &zps, delta, niter, true);
}
- niter->assumptions = assumptions;
- niter->may_be_zero = noloop_assumptions;
- return;
+ /* Make sure that the control iv does not overflow. */
+ if (!assert_no_overflow_lt (type, iv0, iv1, niter, step))
+ return false;
+
+ /* We determine the number of iterations as (delta + step - 1) / step. For
+ this to work, we must know that iv1->base >= iv0->base - step + 1,
+ otherwise the loop does not roll. */
+ assert_loop_rolls_lt (type, iv0, iv1, niter);
-zero_iter:
- niter->assumptions = boolean_true_node;
- niter->may_be_zero = boolean_true_node;
- niter->niter = build_int_cst_type (type, 0);
- return;
+ s = fold_build2 (MINUS_EXPR, niter_type,
+ step, build_int_cst_type (niter_type, 1));
+ delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
+ niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
+ return true;
}
+/* Determines number of iterations of loop whose ending condition
+ is IV0 <= IV1. TYPE is the type of the iv. The number of
+ iterations is stored to NITER. NEVER_INFINITE is true if
+ we know that the loop cannot be infinite (we derived this
+ earlier, and possibly set NITER->assumptions to make sure this
+ is the case. */
-/* Similar to number_of_iterations_cond, but only handles the special
- case of loops with step 1 or -1. The meaning of the arguments
- is the same as in number_of_iterations_cond. The function
- returns true if the special case was recognized, false otherwise. */
+static bool
+number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
+ struct tree_niter_desc *niter, bool never_infinite)
+{
+ 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. */
+
+ if (!never_infinite)
+ {
+ if (nonzero_p (iv0->step))
+ assumption = fold_build2 (NE_EXPR, boolean_type_node,
+ iv1->base, TYPE_MAX_VALUE (type));
+ else
+ assumption = fold_build2 (NE_EXPR, boolean_type_node,
+ iv0->base, TYPE_MIN_VALUE (type));
+
+ if (zero_p (assumption))
+ return false;
+ if (!nonzero_p (assumption))
+ niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
+ niter->assumptions, assumption);
+ }
+
+ if (nonzero_p (iv0->step))
+ iv1->base = fold_build2 (PLUS_EXPR, type,
+ iv1->base, build_int_cst_type (type, 1));
+ else
+ iv0->base = fold_build2 (MINUS_EXPR, type,
+ iv0->base, build_int_cst_type (type, 1));
+ return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite);
+}
+
+/* Determine the number of iterations according to condition (for staying
+ inside loop) which compares two induction variables using comparison
+ operator CODE. The induction variable on left side of the comparison
+ is IV0, the right-hand side is IV1. Both induction variables must have
+ type TYPE, which must be an integer or pointer type. The steps of the
+ ivs must be constants (or NULL_TREE, which is interpreted as constant zero).
+
+ The results (number of iterations and assumptions as described in
+ comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
+ Returns false if it fails to determine number of iterations, true if it
+ was determined (possibly with some assumptions). */
static bool
-number_of_iterations_special (tree type, tree base0, tree step0,
- enum tree_code code, tree base1, tree step1,
- struct tree_niter_desc *niter)
+number_of_iterations_cond (tree type, affine_iv *iv0, enum tree_code code,
+ affine_iv *iv1, struct tree_niter_desc *niter)
{
- tree niter_type = unsigned_type_for (type), mmax, mmin;
+ bool never_infinite;
- /* Make < comparison from > ones. */
- if (code == GE_EXPR
- || code == GT_EXPR)
+ /* The meaning of these assumptions is this:
+ if !assumptions
+ then the rest of information does not have to be valid
+ if may_be_zero then the loop does not roll, even if
+ niter != 0. */
+ niter->assumptions = boolean_true_node;
+ niter->may_be_zero = boolean_false_node;
+ niter->niter = NULL_TREE;
+ niter->additional_info = boolean_true_node;
+
+ niter->bound = NULL_TREE;
+ niter->cmp = ERROR_MARK;
+
+ /* Make < comparison from > ones, and for NE_EXPR comparisons, ensure that
+ the control variable is on lhs. */
+ if (code == GE_EXPR || code == GT_EXPR
+ || (code == NE_EXPR && zero_p (iv0->step)))
{
- SWAP (base0, base1);
- SWAP (step0, step1);
+ SWAP (iv0, iv1);
code = swap_tree_comparison (code);
}
- switch (code)
+ if (POINTER_TYPE_P (type))
{
- case NE_EXPR:
- if (zero_p (step0))
- {
- if (zero_p (step1))
- return false;
- SWAP (base0, base1);
- SWAP (step0, step1);
- }
- else if (!zero_p (step1))
- return false;
+ /* Comparison of pointers is undefined unless both iv0 and iv1 point
+ to the same object. If they do, the control variable cannot wrap
+ (as wrap around the bounds of memory will never return a pointer
+ that would be guaranteed to point to the same object, even if we
+ avoid undefined behavior by casting to size_t and back). */
+ iv0->no_overflow = true;
+ iv1->no_overflow = true;
+ }
- if (integer_onep (step0))
- {
- /* for (i = base0; i != base1; i++) */
- niter->assumptions = boolean_true_node;
- niter->may_be_zero = boolean_false_node;
- niter->niter = fold_build2 (MINUS_EXPR, type, base1, base0);
- niter->additional_info = boolean_true_node;
- }
- else if (integer_all_onesp (step0))
- {
- /* for (i = base0; i != base1; i--) */
- niter->assumptions = boolean_true_node;
- niter->may_be_zero = boolean_false_node;
- niter->niter = fold_build2 (MINUS_EXPR, type, base0, base1);
- }
- else
- return false;
+ /* If the control induction variable does not overflow, the loop obviously
+ cannot be infinite. */
+ if (!zero_p (iv0->step) && iv0->no_overflow)
+ never_infinite = true;
+ else if (!zero_p (iv1->step) && iv1->no_overflow)
+ never_infinite = true;
+ else
+ never_infinite = false;
- break;
+ /* 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
+ practice, but it is simple enough to manage. */
+ if (!zero_p (iv0->step) && !zero_p (iv1->step))
+ {
+ if (code != NE_EXPR)
+ return false;
- case LT_EXPR:
- if ((step0 && integer_onep (step0) && zero_p (step1))
- || (step1 && integer_all_onesp (step1) && zero_p (step0)))
- {
- /* for (i = base0; i < base1; i++)
-
- or
+ iv0->step = fold_binary_to_constant (MINUS_EXPR, type,
+ iv0->step, iv1->step);
+ iv0->no_overflow = false;
+ iv1->step = NULL_TREE;
+ iv1->no_overflow = true;
+ }
- for (i = base1; i > base0; i--).
-
- In both cases # of iterations is base1 - base0. */
+ /* If the result of the comparison is a constant, the loop is weird. More
+ precise handling would be possible, but the situation is not common enough
+ to waste time on it. */
+ if (zero_p (iv0->step) && zero_p (iv1->step))
+ return false;
- niter->assumptions = boolean_true_node;
- niter->may_be_zero = fold_build2 (GT_EXPR, boolean_type_node,
- base0, base1);
- niter->niter = fold_build2 (MINUS_EXPR, type, base1, base0);
- }
- else
+ /* Ignore loops of while (i-- < 10) type. */
+ if (code != NE_EXPR)
+ {
+ if (iv0->step && tree_int_cst_sign_bit (iv0->step))
return false;
- break;
- case LE_EXPR:
- if (POINTER_TYPE_P (type))
- {
- /* We assume pointer arithmetic never overflows. */
- mmin = mmax = NULL_TREE;
- }
- else
- {
- mmin = TYPE_MIN_VALUE (type);
- mmax = TYPE_MAX_VALUE (type);
- }
-
- if (step0 && integer_onep (step0) && zero_p (step1))
- {
- /* for (i = base0; i <= base1; i++) */
- if (mmax)
- niter->assumptions = fold_build2 (NE_EXPR, boolean_type_node,
- base1, mmax);
- else
- niter->assumptions = boolean_true_node;
- base1 = fold_build2 (PLUS_EXPR, type, base1,
- build_int_cst_type (type, 1));
- }
- else if (step1 && integer_all_onesp (step1) && zero_p (step0))
- {
- /* for (i = base1; i >= base0; i--) */
- if (mmin)
- niter->assumptions = fold_build2 (NE_EXPR, boolean_type_node,
- base0, mmin);
- else
- niter->assumptions = boolean_true_node;
- base0 = fold_build2 (MINUS_EXPR, type, base0,
- build_int_cst_type (type, 1));
- }
- else
+ if (!zero_p (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
return false;
+ }
- niter->may_be_zero = fold_build2 (GT_EXPR, boolean_type_node,
- base0, base1);
- niter->niter = fold_build2 (MINUS_EXPR, type, base1, base0);
- break;
+ /* If the loop exits immediately, there is nothing to do. */
+ if (zero_p (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
+ {
+ niter->niter = build_int_cst_type (unsigned_type_for (type), 0);
+ return true;
+ }
+ /* OK, now we know we have a senseful loop. Handle several cases, depending
+ on what comparison operator is used. */
+ switch (code)
+ {
+ case NE_EXPR:
+ gcc_assert (zero_p (iv1->step));
+ return number_of_iterations_ne (type, iv0, iv1->base, niter, never_infinite);
+ case LT_EXPR:
+ return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite);
+ case LE_EXPR:
+ return number_of_iterations_le (type, iv0, iv1, niter, never_infinite);
default:
gcc_unreachable ();
}
-
- niter->niter = fold_convert (niter_type, niter->niter);
- niter->additional_info = boolean_true_node;
- return true;
}
/* Substitute NEW for OLD in EXPR and fold the result. */
/* Expand definitions of ssa names in EXPR as long as they are simple
enough, and return the new expression. */
-static tree
+tree
expand_simple_operations (tree expr)
{
unsigned i, n;
tree ret = NULL_TREE, e, ee, stmt;
- enum tree_code code = TREE_CODE (expr);
+ enum tree_code code;
+
+ if (expr == NULL_TREE)
+ return expr;
if (is_gimple_min_invariant (expr))
return expr;
+ code = TREE_CODE (expr);
if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
{
n = TREE_CODE_LENGTH (code);
/* Check whether COND ==> EXPR. */
notcond = invert_truthvalue (cond);
- e = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
+ e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
if (nonzero_p (e))
return e;
/* Check whether COND ==> not EXPR. */
- e = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, cond, te);
- if (zero_p (e))
+ e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te);
+ if (e && zero_p (e))
return e;
return expr;
EXIT (an exit edge of the LOOP) in NITER. Returns true if some
useful information could be derived (and fields of NITER has
meaning described in comments at struct tree_niter_desc
- declaration), false otherwise. */
+ declaration), false otherwise. If WARN is true and
+ -Wunsafe-loop-optimizations was given, warn if the optimizer is going to use
+ potentially unsafe assumptions. */
bool
number_of_iterations_exit (struct loop *loop, edge exit,
- struct tree_niter_desc *niter)
+ struct tree_niter_desc *niter,
+ bool warn)
{
tree stmt, cond, type;
- tree op0, base0, step0;
- tree op1, base1, step1;
+ tree op0, op1;
enum tree_code code;
+ affine_iv iv0, iv1;
if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
return false;
&& !POINTER_TYPE_P (type))
return false;
- if (!simple_iv (loop, stmt, op0, &base0, &step0))
+ if (!simple_iv (loop, stmt, op0, &iv0, false))
return false;
- if (!simple_iv (loop, stmt, op1, &base1, &step1))
+ if (!simple_iv (loop, stmt, op1, &iv1, false))
return false;
- niter->niter = NULL_TREE;
-
- /* Handle common special cases first, so that we do not need to use
- generic (and slow) analysis very often. */
- if (!number_of_iterations_special (type, base0, step0, code, base1, step1,
- niter))
- {
-
- number_of_iterations_cond (type, base0, step0, code, base1, step1,
- niter);
-
- if (!niter->niter)
- return false;
- }
+ iv0.base = expand_simple_operations (iv0.base);
+ iv1.base = expand_simple_operations (iv1.base);
+ if (!number_of_iterations_cond (type, &iv0, code, &iv1, niter))
+ return false;
if (optimize >= 3)
{
= simplify_using_initial_conditions (loop,
niter->may_be_zero,
&niter->additional_info);
- return integer_onep (niter->assumptions);
+
+ if (integer_onep (niter->assumptions))
+ return 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))
+ return false;
+
+ if (flag_unsafe_loop_optimizations)
+ niter->assumptions = boolean_true_node;
+
+ if (warn)
+ {
+ const char *wording;
+ location_t loc = EXPR_LOCATION (stmt);
+
+ /* We can provide a more specific warning if one of the operator is
+ constant and the other advances by +1 or -1. */
+ if (!zero_p (iv1.step)
+ ? (zero_p (iv0.step)
+ && (integer_onep (iv1.step) || integer_all_onesp (iv1.step)))
+ : (iv0.step
+ && (integer_onep (iv0.step) || integer_all_onesp (iv0.step))))
+ wording =
+ flag_unsafe_loop_optimizations
+ ? N_("assuming that the loop is not infinite")
+ : N_("cannot optimize possibly infinite loops");
+ else
+ wording =
+ flag_unsafe_loop_optimizations
+ ? 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));
+ }
+
+ return flag_unsafe_loop_optimizations;
}
/* Try to determine the number of iterations of LOOP. If we succeed,
if (!just_once_each_iteration_p (loop, ex->src))
continue;
- if (!number_of_iterations_exit (loop, ex, &desc))
+ if (!number_of_iterations_exit (loop, ex, &desc, false))
continue;
if (nonzero_p (desc.may_be_zero))
chain_of_csts_start (struct loop *loop, tree x)
{
tree stmt = SSA_NAME_DEF_STMT (x);
+ tree use;
basic_block bb = bb_for_stmt (stmt);
- use_optype uses;
if (!bb
|| !flow_bb_inside_loop_p (loop, bb))
if (TREE_CODE (stmt) != MODIFY_EXPR)
return NULL_TREE;
- if (NUM_VUSES (STMT_VUSE_OPS (stmt)) > 0)
+ if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
return NULL_TREE;
- if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) > 0)
+ if (SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF) == NULL_DEF_OPERAND_P)
return NULL_TREE;
- if (NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt)) > 0)
- return NULL_TREE;
- if (NUM_DEFS (STMT_DEF_OPS (stmt)) > 1)
- return NULL_TREE;
- uses = STMT_USE_OPS (stmt);
- if (NUM_USES (uses) != 1)
+
+ use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
+ if (use == NULL_USE_OPERAND_P)
return NULL_TREE;
- return chain_of_csts_start (loop, USE_OP (uses, 0));
+ return chain_of_csts_start (loop, use);
}
/* Determines whether the expression X is derived from a result of a phi node
get_val_for (tree x, tree base)
{
tree stmt, nx, val;
- use_optype uses;
use_operand_p op;
+ ssa_op_iter iter;
if (!x)
return base;
if (TREE_CODE (stmt) == PHI_NODE)
return base;
- uses = STMT_USE_OPS (stmt);
- op = USE_OP_PTR (uses, 0);
-
- nx = USE_FROM_PTR (op);
- val = get_val_for (nx, base);
- SET_USE (op, val);
- val = fold (TREE_OPERAND (stmt, 1));
- SET_USE (op, nx);
+ FOR_EACH_SSA_USE_OPERAND (op, stmt, iter, SSA_OP_USE)
+ {
+ nx = USE_FROM_PTR (op);
+ val = get_val_for (nx, base);
+ SET_USE (op, val);
+ val = fold (TREE_OPERAND (stmt, 1));
+ SET_USE (op, nx);
+ /* only iterate loop once. */
+ return val;
+ }
- return val;
+ /* Should never reach here. */
+ gcc_unreachable();
}
/* Tries to count the number of iterations of LOOP till it exits by EXIT
for (j = 0; j < 2; j++)
aval[j] = get_val_for (op[j], val[j]);
- acnd = fold_build2 (cmp, boolean_type_node, aval[0], aval[1]);
- if (zero_p (acnd))
+ acnd = fold_binary (cmp, boolean_type_node, aval[0], aval[1]);
+ if (acnd && zero_p (acnd))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
loop->bounds = elt;
}
+/* 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;
+
+ for (bound = loop->bounds; bound; bound = bound->next)
+ if (TREE_CODE (bound->bound) == INTEGER_CST
+ /* Update only when there is no previous estimation. */
+ && (chrec_contains_undetermined (loop->estimated_nb_iterations)
+ /* Or when the current estimation is smaller. */
+ || tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations)))
+ loop->estimated_nb_iterations = bound->bound;
+}
+
+/* The following analyzers are extracting informations on the bounds
+ of LOOP from the following undefined behaviors:
+
+ - data references should not access elements over the statically
+ allocated size,
+
+ - signed variables should not overflow when flag_wrapv is not set.
+*/
+
+static void
+infer_loop_bounds_from_undefined (struct loop *loop)
+{
+ unsigned i;
+ basic_block bb, *bbs;
+ block_stmt_iterator bsi;
+
+ bbs = get_loop_body (loop);
+
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+ bb = bbs[i];
+
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ tree stmt = bsi_stmt (bsi);
+
+ switch (TREE_CODE (stmt))
+ {
+ case MODIFY_EXPR:
+ {
+ tree op0 = TREE_OPERAND (stmt, 0);
+ tree op1 = TREE_OPERAND (stmt, 1);
+
+ /* For each array access, analyze its access function
+ and record a bound on the loop iteration domain. */
+ if (TREE_CODE (op1) == ARRAY_REF
+ && !array_ref_contains_indirect_ref (op1))
+ estimate_iters_using_array (stmt, op1);
+
+ if (TREE_CODE (op0) == ARRAY_REF
+ && !array_ref_contains_indirect_ref (op0))
+ estimate_iters_using_array (stmt, op0);
+
+ /* For each signed type variable in LOOP, analyze its
+ scalar evolution and record a bound of the loop
+ based on the type's ranges. */
+ else if (!flag_wrapv && TREE_CODE (op0) == SSA_NAME)
+ {
+ tree init, step, diff, estimation;
+ tree scev = instantiate_parameters
+ (loop, analyze_scalar_evolution (loop, op0));
+ tree type = chrec_type (scev);
+ tree utype;
+
+ if (chrec_contains_undetermined (scev)
+ || TYPE_UNSIGNED (type))
+ break;
+
+ init = initial_condition_in_loop_num (scev, loop->num);
+ step = evolution_part_in_loop_num (scev, loop->num);
+
+ if (init == NULL_TREE
+ || step == NULL_TREE
+ || TREE_CODE (init) != INTEGER_CST
+ || TREE_CODE (step) != INTEGER_CST
+ || TYPE_MIN_VALUE (type) == NULL_TREE
+ || TYPE_MAX_VALUE (type) == NULL_TREE)
+ break;
+
+ utype = unsigned_type_for (type);
+ if (tree_int_cst_lt (step, integer_zero_node))
+ diff = fold_build2 (MINUS_EXPR, utype, init,
+ TYPE_MIN_VALUE (type));
+ else
+ diff = fold_build2 (MINUS_EXPR, utype,
+ TYPE_MAX_VALUE (type), init);
+
+ estimation = fold_build2 (CEIL_DIV_EXPR, utype, diff,
+ step);
+ record_estimate (loop, estimation, boolean_true_node, stmt);
+ }
+
+ break;
+ }
+
+ case CALL_EXPR:
+ {
+ tree args;
+
+ for (args = TREE_OPERAND (stmt, 1); args;
+ args = TREE_CHAIN (args))
+ if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF
+ && !array_ref_contains_indirect_ref (TREE_VALUE (args)))
+ estimate_iters_using_array (stmt, TREE_VALUE (args));
+
+ break;
+ }
+
+ default:
+ break;
+ }
+ }
+
+ if (chrec_contains_undetermined (loop->estimated_nb_iterations))
+ compute_estimated_nb_iterations (loop);
+ }
+
+ free (bbs);
+}
+
/* Records estimates on numbers of iterations of LOOP. */
static void
unsigned i, n_exits;
struct tree_niter_desc niter_desc;
+ /* Give up if we already have tried to compute an estimation. */
+ if (loop->estimated_nb_iterations == chrec_dont_know
+ /* Or when we already have an estimation. */
+ || (loop->estimated_nb_iterations != NULL_TREE
+ && TREE_CODE (loop->estimated_nb_iterations) == INTEGER_CST))
+ return;
+ else
+ loop->estimated_nb_iterations = chrec_dont_know;
+
exits = get_loop_exit_edges (loop, &n_exits);
for (i = 0; i < n_exits; i++)
{
- if (!number_of_iterations_exit (loop, exits[i], &niter_desc))
+ if (!number_of_iterations_exit (loop, exits[i], &niter_desc, false))
continue;
niter = niter_desc.niter;
}
free (exits);
- /* Analyzes the bounds of arrays accessed in the loop. */
- if (loop->estimated_nb_iterations == NULL_TREE)
- {
- varray_type datarefs;
- VARRAY_GENERIC_PTR_INIT (datarefs, 3, "datarefs");
- find_data_references_in_loop (loop, &datarefs);
- free_data_refs (datarefs);
- }
+ if (chrec_contains_undetermined (loop->estimated_nb_iterations))
+ infer_loop_bounds_from_undefined (loop);
}
/* Records estimates on numbers of iterations of LOOPS. */
a = fold_convert (type, a);
b = fold_convert (type, b);
- if (nonzero_p (fold_build2 (EQ_EXPR, boolean_type_node, a, b)))
+ if (nonzero_p (fold_binary (EQ_EXPR, boolean_type_node, a, b)))
return 0;
- if (nonzero_p (fold_build2 (LT_EXPR, boolean_type_node, a, b)))
+ if (nonzero_p (fold_binary (LT_EXPR, boolean_type_node, a, b)))
return 1;
- if (nonzero_p (fold_build2 (GT_EXPR, boolean_type_node, a, b)))
+ if (nonzero_p (fold_binary (GT_EXPR, boolean_type_node, a, b)))
return -1;
return 2;
return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
}
-/* Checks whether it is correct to count the induction variable BASE + STEP * I
- at AT_STMT in wider TYPE, using the fact that statement OF is executed at
- most BOUND times in the loop. If it is possible, return the value of step
- of the induction variable in the TYPE, otherwise return NULL_TREE.
+/* Return true when it is possible to prove that the induction
+ variable does not wrap: vary outside the type specified bounds.
+ Checks whether BOUND < VALID_NITER that means in the context of iv
+ conversion that all the iterations in the loop are safe: not
+ producing wraps.
+
+ The statement NITER_BOUND->AT_STMT is executed at most
+ NITER_BOUND->BOUND times in the loop.
- ADDITIONAL is the additional condition recorded for operands of the bound.
- This is useful in the following case, created by loop header copying:
+ NITER_BOUND->ADDITIONAL is the additional condition recorded for
+ operands of the bound. This is useful in the following case,
+ created by loop header copying:
i = 0;
if (n > 0)
assumption "n > 0" says us that the value of the number of iterations is at
most MAX_TYPE - 1 (without this assumption, it might overflow). */
-static tree
-can_count_iv_in_wider_type_bound (tree type, tree base, tree step,
- tree at_stmt,
- tree bound,
- tree additional,
- tree of)
+static bool
+proved_non_wrapping_p (tree at_stmt,
+ struct nb_iter_bound *niter_bound,
+ tree new_type,
+ tree valid_niter)
{
- tree inner_type = TREE_TYPE (base), b, bplusstep, new_step, new_step_abs;
- tree valid_niter, extreme, unsigned_type, delta, bound_type;
tree cond;
+ tree bound = niter_bound->bound;
+ enum tree_code cmp;
+
+ if (TYPE_PRECISION (new_type) > TYPE_PRECISION (TREE_TYPE (bound)))
+ bound = fold_convert (unsigned_type_for (new_type), bound);
+ else
+ valid_niter = fold_convert (TREE_TYPE (bound), valid_niter);
+
+ /* Give up if BOUND was not folded to an INTEGER_CST, as in PR23434. */
+ if (TREE_CODE (bound) != INTEGER_CST)
+ return false;
+
+ /* After the statement niter_bound->at_stmt we know that anything is
+ executed at most BOUND times. */
+ if (at_stmt && stmt_dominates_stmt_p (niter_bound->at_stmt, at_stmt))
+ cmp = GE_EXPR;
+ /* Before the statement niter_bound->at_stmt we know that anything
+ is executed at most BOUND + 1 times. */
+ else
+ cmp = GT_EXPR;
+
+ cond = fold_binary (cmp, boolean_type_node, valid_niter, bound);
+ if (nonzero_p (cond))
+ return true;
+
+ cond = build2 (cmp, boolean_type_node, valid_niter, bound);
+ /* Try taking additional conditions into account. */
+ cond = fold_binary (TRUTH_OR_EXPR, boolean_type_node,
+ invert_truthvalue (niter_bound->additional),
+ cond);
+
+ if (nonzero_p (cond))
+ return true;
- b = fold_convert (type, base);
- bplusstep = fold_convert (type,
- fold_build2 (PLUS_EXPR, inner_type, base, step));
- new_step = fold_build2 (MINUS_EXPR, type, bplusstep, b);
- if (TREE_CODE (new_step) != INTEGER_CST)
+ return false;
+}
+
+/* Checks whether it is correct to count the induction variable BASE +
+ STEP * I at AT_STMT in a wider type NEW_TYPE, using the bounds on
+ numbers of iterations of a LOOP. If it is possible, return the
+ value of step of the induction variable in the NEW_TYPE, otherwise
+ return NULL_TREE. */
+
+static tree
+convert_step_widening (struct loop *loop, tree new_type, tree base, tree step,
+ tree at_stmt)
+{
+ struct nb_iter_bound *bound;
+ tree base_in_new_type, base_plus_step_in_new_type, step_in_new_type;
+ tree delta, step_abs;
+ tree unsigned_type, valid_niter;
+
+ /* Compute the new step. For example, {(uchar) 100, +, (uchar) 240}
+ is converted to {(uint) 100, +, (uint) 0xfffffff0} in order to
+ keep the values of the induction variable unchanged: 100, 84, 68,
+ ...
+
+ Another example is: (uint) {(uchar)100, +, (uchar)3} is converted
+ to {(uint)100, +, (uint)3}.
+
+ Before returning the new step, verify that the number of
+ iterations is less than DELTA / STEP_ABS (i.e. in the previous
+ example (256 - 100) / 3) such that the iv does not wrap (in which
+ case the operations are too difficult to be represented and
+ handled: the values of the iv should be taken modulo 256 in the
+ wider type; this is not implemented). */
+ base_in_new_type = fold_convert (new_type, base);
+ base_plus_step_in_new_type =
+ fold_convert (new_type,
+ fold_build2 (PLUS_EXPR, TREE_TYPE (base), base, step));
+ step_in_new_type = fold_build2 (MINUS_EXPR, new_type,
+ base_plus_step_in_new_type,
+ base_in_new_type);
+
+ if (TREE_CODE (step_in_new_type) != INTEGER_CST)
return NULL_TREE;
- switch (compare_trees (bplusstep, b))
+ switch (compare_trees (base_plus_step_in_new_type, base_in_new_type))
{
case -1:
- extreme = upper_bound_in_type (type, inner_type);
- delta = fold_build2 (MINUS_EXPR, type, extreme, b);
- new_step_abs = new_step;
- break;
+ {
+ tree extreme = upper_bound_in_type (new_type, TREE_TYPE (base));
+ delta = fold_build2 (MINUS_EXPR, new_type, extreme,
+ base_in_new_type);
+ step_abs = step_in_new_type;
+ break;
+ }
case 1:
- extreme = lower_bound_in_type (type, inner_type);
- new_step_abs = fold_build1 (NEGATE_EXPR, type, new_step);
- delta = fold_build2 (MINUS_EXPR, type, b, extreme);
- break;
+ {
+ tree extreme = lower_bound_in_type (new_type, TREE_TYPE (base));
+ delta = fold_build2 (MINUS_EXPR, new_type, base_in_new_type,
+ extreme);
+ step_abs = fold_build1 (NEGATE_EXPR, new_type, step_in_new_type);
+ break;
+ }
case 0:
- return new_step;
+ return step_in_new_type;
default:
return NULL_TREE;
}
- unsigned_type = unsigned_type_for (type);
+ unsigned_type = unsigned_type_for (new_type);
delta = fold_convert (unsigned_type, delta);
- new_step_abs = fold_convert (unsigned_type, new_step_abs);
+ step_abs = fold_convert (unsigned_type, step_abs);
valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type,
- delta, new_step_abs);
+ delta, step_abs);
- bound_type = TREE_TYPE (bound);
- if (TYPE_PRECISION (type) > TYPE_PRECISION (bound_type))
- bound = fold_convert (unsigned_type, bound);
- else
- valid_niter = fold_convert (bound_type, valid_niter);
-
- if (at_stmt && stmt_dominates_stmt_p (of, at_stmt))
+ estimate_numbers_of_iterations_loop (loop);
+ for (bound = loop->bounds; bound; bound = bound->next)
+ if (proved_non_wrapping_p (at_stmt, bound, new_type, valid_niter))
+ return step_in_new_type;
+
+ /* Fail when the loop has no bound estimations, or when no bound can
+ be used for verifying the conversion. */
+ return NULL_TREE;
+}
+
+/* Returns true when VAR is used in pointer arithmetics. DEPTH is
+ used for limiting the search. */
+
+static bool
+used_in_pointer_arithmetic_p (tree var, int depth)
+{
+ use_operand_p use_p;
+ imm_use_iterator iter;
+
+ if (depth == 0
+ || TREE_CODE (var) != SSA_NAME
+ || !has_single_use (var))
+ return false;
+
+ FOR_EACH_IMM_USE_FAST (use_p, iter, var)
+ {
+ tree stmt = USE_STMT (use_p);
+
+ if (stmt && TREE_CODE (stmt) == MODIFY_EXPR)
+ {
+ tree rhs = TREE_OPERAND (stmt, 1);
+
+ if (TREE_CODE (rhs) == NOP_EXPR
+ || TREE_CODE (rhs) == CONVERT_EXPR)
+ {
+ if (POINTER_TYPE_P (TREE_TYPE (rhs)))
+ return true;
+ return false;
+ }
+ else
+ return used_in_pointer_arithmetic_p (TREE_OPERAND (stmt, 0),
+ depth - 1);
+ }
+ }
+ 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
+ keep the evolution confined in TYPEs bounds. Return true when the
+ iv is known to overflow or when the property is not computable.
+
+ Initialize INIT_IS_MAX to true when the evolution goes from
+ INIT_IS_MAX to LOWER_BOUND_IN_TYPE, false in the contrary case.
+ When this property cannot be determined, UNKNOWN_MAX is set to
+ true. */
+
+bool
+scev_probably_wraps_p (tree type, tree base, tree step,
+ tree at_stmt, struct loop *loop,
+ bool *init_is_max, bool *unknown_max)
+{
+ struct nb_iter_bound *bound;
+ tree delta, step_abs;
+ tree unsigned_type, valid_niter;
+ tree base_plus_step, bpsps;
+ int cps, cpsps;
+
+ /* FIXME: The following code will not be used anymore once
+ http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html is
+ committed.
+
+ If AT_STMT is a cast to unsigned that is later used for
+ referencing a memory location, it is followed by a pointer
+ conversion just after. Because pointers do not wrap, the
+ sequences that reference the memory do not wrap either. In the
+ following example, sequences corresponding to D_13 and to D_14
+ can be proved to not wrap because they are used for computing a
+ memory access:
+
+ D.1621_13 = (long unsigned intD.4) D.1620_12;
+ D.1622_14 = D.1621_13 * 8;
+ D.1623_15 = (doubleD.29 *) D.1622_14;
+ */
+ if (at_stmt && TREE_CODE (at_stmt) == MODIFY_EXPR)
{
- /* After the statement OF we know that anything is executed at most
- BOUND times. */
- cond = fold_build2 (GE_EXPR, boolean_type_node, valid_niter, bound);
+ tree op0 = TREE_OPERAND (at_stmt, 0);
+ tree op1 = TREE_OPERAND (at_stmt, 1);
+ tree type_op1 = TREE_TYPE (op1);
+
+ if ((TYPE_UNSIGNED (type_op1)
+ && used_in_pointer_arithmetic_p (op0, 2))
+ || POINTER_TYPE_P (type_op1))
+ {
+ *unknown_max = true;
+ return false;
+ }
}
- else
+
+ if (chrec_contains_undetermined (base)
+ || chrec_contains_undetermined (step)
+ || TREE_CODE (base) == REAL_CST
+ || TREE_CODE (step) == REAL_CST)
{
- /* Before the statement OF we know that anything is executed at most
- BOUND + 1 times. */
- cond = fold_build2 (GT_EXPR, boolean_type_node, valid_niter, bound);
+ *unknown_max = true;
+ return true;
}
- if (nonzero_p (cond))
- return new_step;
+ *unknown_max = false;
+ base_plus_step = fold_build2 (PLUS_EXPR, type, base, step);
+ bpsps = fold_build2 (PLUS_EXPR, type, base_plus_step, step);
+ cps = compare_trees (base_plus_step, base);
+ cpsps = compare_trees (bpsps, base_plus_step);
- /* Try taking additional conditions into account. */
- cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
- invert_truthvalue (additional),
- cond);
- if (nonzero_p (cond))
- return new_step;
+ /* Check that the sequence is not wrapping in the first step: it
+ should have the same monotonicity for the first two steps. See
+ PR23410. */
+ if (cps != cpsps)
+ return true;
- return NULL_TREE;
+ switch (cps)
+ {
+ case -1:
+ {
+ tree extreme = upper_bound_in_type (type, TREE_TYPE (base));
+ delta = fold_build2 (MINUS_EXPR, type, extreme, base);
+ step_abs = step;
+ *init_is_max = false;
+ break;
+ }
+
+ case 1:
+ {
+ tree extreme = lower_bound_in_type (type, TREE_TYPE (base));
+ delta = fold_build2 (MINUS_EXPR, type, base, extreme);
+ step_abs = fold_build1 (NEGATE_EXPR, type, step);
+ *init_is_max = true;
+ break;
+ }
+
+ case 0:
+ /* This means step is equal to 0. This should not happen. It
+ could happen in convert step, but not here. Safely answer
+ don't know as in the default case. */
+
+ default:
+ *unknown_max = true;
+ return true;
+ }
+
+ /* If AT_STMT represents a cast operation, we may not be able to
+ take advantage of the undefinedness of signed type evolutions.
+
+ implement-c.texi states: "For conversion to a type of width
+ N, the value is reduced modulo 2^N to be within range of the
+ type;"
+
+ See PR 21959 for a test case. Essentially, given a cast
+ operation
+ unsigned char uc;
+ signed char sc;
+ ...
+ sc = (signed char) uc;
+ if (sc < 0)
+ ...
+
+ where uc and sc have the scev {0, +, 1}, we would consider uc to
+ wrap around, but not sc, because it is of a signed type. This
+ causes VRP to erroneously fold the predicate above because it
+ thinks that sc cannot be negative. */
+ if (at_stmt && TREE_CODE (at_stmt) == MODIFY_EXPR)
+ {
+ tree rhs = TREE_OPERAND (at_stmt, 1);
+ tree outer_t = TREE_TYPE (rhs);
+
+ if (!TYPE_UNSIGNED (outer_t)
+ && (TREE_CODE (rhs) == NOP_EXPR || TREE_CODE (rhs) == CONVERT_EXPR))
+ {
+ tree inner_t = TREE_TYPE (TREE_OPERAND (rhs, 0));
+
+ /* If the inner type is unsigned and its size and/or
+ precision are smaller to that of the outer type, then the
+ expression may wrap around. */
+ if (TYPE_UNSIGNED (inner_t)
+ && (TYPE_SIZE (inner_t) <= TYPE_SIZE (outer_t)
+ || TYPE_PRECISION (inner_t) <= TYPE_PRECISION (outer_t)))
+ {
+ *unknown_max = true;
+ return true;
+ }
+ }
+ }
+
+ /* After having set INIT_IS_MAX, we can return false: when not using
+ wrapping arithmetic, signed types don't wrap. */
+ if (!flag_wrapv && !TYPE_UNSIGNED (type))
+ return false;
+
+ unsigned_type = unsigned_type_for (type);
+ delta = fold_convert (unsigned_type, delta);
+ step_abs = fold_convert (unsigned_type, step_abs);
+ valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
+
+ estimate_numbers_of_iterations_loop (loop);
+ for (bound = loop->bounds; bound; bound = bound->next)
+ if (proved_non_wrapping_p (at_stmt, bound, type, valid_niter))
+ return false;
+
+ /* At this point we still don't have a proof that the iv does not
+ overflow: give up. */
+ *unknown_max = true;
+ return true;
}
-/* Checks whether it is correct to count the induction variable BASE + STEP * I
- at AT_STMT in wider TYPE, using the bounds on numbers of iterations of a
- LOOP. If it is possible, return the value of step of the induction variable
- in the TYPE, otherwise return NULL_TREE. */
+/* Return the conversion to NEW_TYPE of the STEP of an induction
+ variable BASE + STEP * I at AT_STMT. When it fails, return
+ NULL_TREE. */
tree
-can_count_iv_in_wider_type (struct loop *loop, tree type, tree base, tree step,
- tree at_stmt)
+convert_step (struct loop *loop, tree new_type, tree base, tree step,
+ tree at_stmt)
{
- struct nb_iter_bound *bound;
- tree new_step;
+ tree base_type;
- for (bound = loop->bounds; bound; bound = bound->next)
- {
- new_step = can_count_iv_in_wider_type_bound (type, base, step,
- at_stmt,
- bound->bound,
- bound->additional,
- bound->at_stmt);
-
- if (new_step)
- return new_step;
- }
+ if (chrec_contains_undetermined (base)
+ || chrec_contains_undetermined (step))
+ return NULL_TREE;
- return NULL_TREE;
+ base_type = TREE_TYPE (base);
+
+ /* When not using wrapping arithmetic, signed types don't wrap. */
+ if (!flag_wrapv && !TYPE_UNSIGNED (base_type))
+ return fold_convert (new_type, step);
+
+ if (TYPE_PRECISION (new_type) > TYPE_PRECISION (base_type))
+ return convert_step_widening (loop, new_type, base, step, at_stmt);
+
+ return fold_convert (new_type, step);
}
/* Frees the information on upper bounds on numbers of iterations of LOOP. */
-static void
+void
free_numbers_of_iterations_estimates_loop (struct loop *loop)
{
struct nb_iter_bound *bound, *next;
-
+
+ loop->nb_iterations = NULL;
+ loop->estimated_nb_iterations = NULL;
for (bound = loop->bounds; bound; bound = next)
{
next = bound->next;
free_numbers_of_iterations_estimates_loop (loop);
}
}
+
+/* Substitute value VAL for ssa name NAME inside expressions held
+ at LOOP. */
+
+void
+substitute_in_loop_info (struct loop *loop, tree name, tree val)
+{
+ struct nb_iter_bound *bound;
+
+ loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);
+ loop->estimated_nb_iterations
+ = simplify_replace_tree (loop->estimated_nb_iterations, name, val);
+ for (bound = loop->bounds; bound; bound = bound->next)
+ {
+ bound->bound = simplify_replace_tree (bound->bound, name, val);
+ bound->additional = simplify_replace_tree (bound->additional, name, val);
+ }
+}
OSDN Git Service
