/* Functions to determine/estimate number of iterations of a loop.
- Copyright (C) 2004 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2005 Free Software Foundation, Inc.
This file is part of GCC.
#include "ggc.h"
#include "tree-chrec.h"
#include "tree-scalar-evolution.h"
+#include "tree-data-ref.h"
#include "params.h"
#include "flags.h"
#include "tree-inline.h"
#define SWAP(X, Y) do { void *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
-/* Just to shorten the ugly names. */
-#define EXEC_BINARY nondestructive_fold_binary_to_constant
-#define EXEC_UNARY nondestructive_fold_unary_to_constant
/*
*/
-/* Returns true if ARG is either NULL_TREE or constant zero. */
+/* Returns true if ARG is either NULL_TREE or constant zero. Unlike
+ integer_zerop, it does not care about overflow flags. */
bool
zero_p (tree arg)
if (!arg)
return true;
- return integer_zerop (arg);
+ if (TREE_CODE (arg) != INTEGER_CST)
+ return false;
+
+ return (TREE_INT_CST_LOW (arg) == 0 && TREE_INT_CST_HIGH (arg) == 0);
+}
+
+/* Returns true if ARG a nonzero constant. Unlike integer_nonzerop, it does
+ not care about overflow flags. */
+
+static bool
+nonzero_p (tree arg)
+{
+ if (!arg)
+ return false;
+
+ if (TREE_CODE (arg) != INTEGER_CST)
+ return false;
+
+ return (TREE_INT_CST_LOW (arg) != 0 || TREE_INT_CST_HIGH (arg) != 0);
}
/* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
inverse (tree x, tree mask)
{
tree type = TREE_TYPE (x);
- tree ctr = EXEC_BINARY (RSHIFT_EXPR, type, mask, integer_one_node);
- tree rslt = convert (type, integer_one_node);
+ tree rslt;
+ unsigned ctr = tree_floor_log2 (mask);
- while (integer_nonzerop (ctr))
+ if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT)
{
- rslt = EXEC_BINARY (MULT_EXPR, type, rslt, x);
- rslt = EXEC_BINARY (BIT_AND_EXPR, type, rslt, mask);
- x = EXEC_BINARY (MULT_EXPR, type, x, x);
- x = EXEC_BINARY (BIT_AND_EXPR, type, x, mask);
- ctr = EXEC_BINARY (RSHIFT_EXPR, type, ctr, integer_one_node);
- }
+ unsigned HOST_WIDE_INT ix;
+ unsigned HOST_WIDE_INT imask;
+ unsigned HOST_WIDE_INT irslt = 1;
- return rslt;
-}
+ gcc_assert (cst_and_fits_in_hwi (x));
+ gcc_assert (cst_and_fits_in_hwi (mask));
-/* Returns unsigned variant of TYPE. */
+ ix = int_cst_value (x);
+ imask = int_cst_value (mask);
-tree
-unsigned_type_for (tree type)
-{
- return make_unsigned_type (TYPE_PRECISION (type));
-}
+ for (; ctr; ctr--)
+ {
+ irslt *= ix;
+ ix *= ix;
+ }
+ irslt &= imask;
-/* Returns signed variant of TYPE. */
+ rslt = build_int_cst_type (type, irslt);
+ }
+ else
+ {
+ 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 = fold_binary_to_constant (BIT_AND_EXPR, type, rslt, mask);
+ }
-static tree
-signed_type_for (tree type)
-{
- return make_signed_type (TYPE_PRECISION (type));
+ return rslt;
}
/* Determine the number of iterations according to condition (for staying
In case we are unable to determine number of iterations, contents of
this structure is unchanged. */
-void
+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)
tree assumptions = boolean_true_node;
tree noloop_assumptions = boolean_false_node;
tree niter_type, signed_niter_type;
+ tree bits;
/* The meaning of these assumptions is this:
if !assumptions
if (code != NE_EXPR)
return;
- step0 = EXEC_BINARY (MINUS_EXPR, type, step0, step1);
+ step0 = fold_binary_to_constant (MINUS_EXPR, type, step0, step1);
step1 = NULL_TREE;
}
if (zero_p (step0))
{
if (mmax)
- assumption = fold (build (EQ_EXPR, boolean_type_node, base0, mmax));
+ assumption = fold_build2 (EQ_EXPR, boolean_type_node, base0, mmax);
else
assumption = boolean_false_node;
- if (integer_nonzerop (assumption))
+ if (nonzero_p (assumption))
goto zero_iter;
- base0 = fold (build (PLUS_EXPR, type, base0,
- convert (type, integer_one_node)));
+ base0 = fold_build2 (PLUS_EXPR, type, base0,
+ build_int_cst_type (type, 1));
}
else
{
if (mmin)
- assumption = fold (build (EQ_EXPR, boolean_type_node, base1, mmin));
+ assumption = fold_build2 (EQ_EXPR, boolean_type_node, base1, mmin);
else
assumption = boolean_false_node;
- if (integer_nonzerop (assumption))
+ if (nonzero_p (assumption))
goto zero_iter;
- base1 = fold (build (MINUS_EXPR, type, base1,
- convert (type, integer_one_node)));
+ base1 = fold_build2 (MINUS_EXPR, type, base1,
+ build_int_cst_type (type, 1));
}
noloop_assumptions = assumption;
code = LE_EXPR;
if (code != NE_EXPR)
{
if (zero_p (step0))
- step = EXEC_UNARY (NEGATE_EXPR, type, step1);
+ step = fold_unary_to_constant (NEGATE_EXPR, type, step1);
else
step = step0;
- delta = build (MINUS_EXPR, type, base1, base0);
- delta = fold (build (FLOOR_MOD_EXPR, type, delta, step));
+ delta = build2 (MINUS_EXPR, type, base1, base0);
+ delta = fold_build2 (FLOOR_MOD_EXPR, type, delta, step);
may_xform = boolean_false_node;
if (TREE_CODE (delta) == INTEGER_CST)
{
- tmp = EXEC_BINARY (MINUS_EXPR, type, step,
- convert (type, integer_one_node));
+ tmp = fold_binary_to_constant (MINUS_EXPR, type, step,
+ build_int_cst_type (type, 1));
if (was_sharp
&& operand_equal_p (delta, tmp, 0))
{
may_xform = boolean_true_node;
else
{
- bound = EXEC_BINARY (PLUS_EXPR, type, mmin, step);
- bound = EXEC_BINARY (MINUS_EXPR, type, bound, delta);
- may_xform = fold (build (LE_EXPR, boolean_type_node,
- bound, base0));
+ 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
may_xform = boolean_true_node;
else
{
- bound = EXEC_BINARY (MINUS_EXPR, type, mmax, step);
- bound = EXEC_BINARY (PLUS_EXPR, type, bound, delta);
- may_xform = fold (build (LE_EXPR, boolean_type_node,
- base1, bound));
+ 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);
}
}
}
- if (!integer_zerop (may_xform))
+ 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 (!integer_nonzerop (may_xform))
+ if (!nonzero_p (may_xform))
assumptions = may_xform;
if (zero_p (step0))
{
- base0 = build (PLUS_EXPR, type, base0, delta);
- base0 = fold (build (MINUS_EXPR, type, base0, step));
+ base0 = fold_build2 (PLUS_EXPR, type, base0, delta);
+ base0 = fold_build2 (MINUS_EXPR, type, base0, step);
}
else
{
- base1 = build (MINUS_EXPR, type, base1, delta);
- base1 = fold (build (PLUS_EXPR, type, base1, step));
+ base1 = fold_build2 (MINUS_EXPR, type, base1, delta);
+ base1 = fold_build2 (PLUS_EXPR, type, base1, step);
}
- assumption = fold (build (GT_EXPR, boolean_type_node, base0, base1));
- noloop_assumptions = fold (build (TRUTH_OR_EXPR, boolean_type_node,
- noloop_assumptions, assumption));
+ 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;
}
}
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 (build (MINUS_EXPR, type, base1, base0));
+ base1 = fold_build2 (MINUS_EXPR, type, base1, base0);
base0 = NULL_TREE;
if (!zero_p (step1))
- step0 = EXEC_UNARY (NEGATE_EXPR, type, step1);
+ step0 = fold_unary_to_constant (NEGATE_EXPR, type, step1);
step1 = NULL_TREE;
- if (!tree_expr_nonnegative_p (convert (signed_niter_type, step0)))
+ if (!tree_expr_nonnegative_p (fold_convert (signed_niter_type, step0)))
{
- step0 = EXEC_UNARY (NEGATE_EXPR, type, step0);
- base1 = fold (build1 (NEGATE_EXPR, type, base1));
+ step0 = fold_unary_to_constant (NEGATE_EXPR, type, step0);
+ base1 = fold_build1 (NEGATE_EXPR, type, base1);
}
- base1 = convert (niter_type, base1);
- step0 = convert (niter_type, step0);
+ base1 = fold_convert (niter_type, base1);
+ step0 = fold_convert (niter_type, step0);
- /* Let nsd (s, size of mode) = d. If d does not divide c, the loop
+ /* 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). */
- s = step0;
- d = integer_one_node;
- bound = convert (niter_type, build_int_cst (NULL_TREE, -1));
- while (1)
- {
- tmp = EXEC_BINARY (BIT_AND_EXPR, niter_type, s,
- convert (niter_type, integer_one_node));
- if (integer_nonzerop (tmp))
- break;
-
- s = EXEC_BINARY (RSHIFT_EXPR, niter_type, s,
- convert (niter_type, integer_one_node));
- d = EXEC_BINARY (LSHIFT_EXPR, niter_type, d,
- convert (niter_type, integer_one_node));
- bound = EXEC_BINARY (RSHIFT_EXPR, niter_type, bound,
- convert (niter_type, integer_one_node));
- }
-
- 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 (build (EXACT_DIV_EXPR, niter_type, base1, d));
- tmp = fold (build (MULT_EXPR, niter_type, tmp, inverse (s, bound)));
- niter->niter = fold (build (BIT_AND_EXPR, niter_type, tmp, bound));
+ 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);
+
+ bound = build_low_bits_mask (niter_type,
+ (TYPE_PRECISION (niter_type)
+ - tree_low_cst (bits, 1)));
+
+ 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);
}
else
{
{
if (mmax)
{
- bound = EXEC_BINARY (MINUS_EXPR, type, mmax, step0);
- assumption = fold (build (LE_EXPR, boolean_type_node,
- base1, bound));
- assumptions = fold (build (TRUTH_AND_EXPR, boolean_type_node,
- assumptions, assumption));
+ 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);
}
step = step0;
- tmp = fold (build (PLUS_EXPR, type, base1, step0));
- assumption = fold (build (GT_EXPR, boolean_type_node, base0, tmp));
- delta = fold (build (PLUS_EXPR, type, base1, step));
- delta = fold (build (MINUS_EXPR, type, delta, base0));
- delta = convert (niter_type, delta);
+ 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
{
we can again compute number of iterations as (b - (a - s)) / s. */
if (mmin)
{
- bound = EXEC_BINARY (MINUS_EXPR, type, mmin, step1);
- assumption = fold (build (LE_EXPR, boolean_type_node,
- bound, base0));
- assumptions = fold (build (TRUTH_AND_EXPR, boolean_type_node,
- assumptions, assumption));
+ 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 (build (PLUS_EXPR, type, base0, step1));
- assumption = fold (build (GT_EXPR, boolean_type_node, tmp, base1));
- delta = fold (build (MINUS_EXPR, type, base0, step));
- delta = fold (build (MINUS_EXPR, type, base1, delta));
- delta = convert (niter_type, delta);
+ 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 (build (TRUTH_OR_EXPR, boolean_type_node,
- noloop_assumptions, assumption));
- delta = fold (build (FLOOR_DIV_EXPR, niter_type, delta,
- convert (niter_type, step)));
+ 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;
}
zero_iter:
niter->assumptions = boolean_true_node;
niter->may_be_zero = boolean_true_node;
- niter->niter = convert (type, integer_zero_node);
+ niter->niter = build_int_cst_type (type, 0);
return;
}
-/* Tries to simplify EXPR using the evolutions of the loop invariants
- in the superloops of LOOP. Returns the simplified expression
- (or EXPR unchanged, if no simplification was possible). */
-static tree
-simplify_using_outer_evolutions (struct loop *loop, tree expr)
+/* 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_special (tree type, tree base0, tree step0,
+ enum tree_code code, tree base1, tree step1,
+ struct tree_niter_desc *niter)
{
- enum tree_code code = TREE_CODE (expr);
- bool changed;
- tree e, e0, e1, e2;
+ tree niter_type = unsigned_type_for (type), mmax, mmin;
- if (is_gimple_min_invariant (expr))
- return expr;
+ /* Make < comparison from > ones. */
+ if (code == GE_EXPR
+ || code == GT_EXPR)
+ {
+ SWAP (base0, base1);
+ SWAP (step0, step1);
+ code = swap_tree_comparison (code);
+ }
- if (code == TRUTH_OR_EXPR
- || code == TRUTH_AND_EXPR
- || code == COND_EXPR)
+ switch (code)
{
- changed = false;
+ 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;
- e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
- if (TREE_OPERAND (expr, 0) != e0)
- changed = 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;
- e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
- if (TREE_OPERAND (expr, 1) != e1)
- changed = true;
+ break;
- if (code == COND_EXPR)
+ case LT_EXPR:
+ if ((step0 && integer_onep (step0) && zero_p (step1))
+ || (step1 && integer_all_onesp (step1) && zero_p (step0)))
{
- e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
- if (TREE_OPERAND (expr, 2) != e2)
- changed = true;
+ /* for (i = base0; i < base1; i++)
+
+ or
+
+ for (i = base1; i > base0; i--).
+
+ In both cases # of iterations is base1 - base0. */
+
+ 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
- e2 = NULL_TREE;
+ return false;
+ break;
- if (changed)
+ case LE_EXPR:
+ if (POINTER_TYPE_P (type))
{
- if (code == COND_EXPR)
- expr = build (code, boolean_type_node, e0, e1, e2);
+ /* 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
- expr = build (code, boolean_type_node, e0, e1);
- expr = fold (expr);
+ niter->assumptions = boolean_true_node;
+ base0 = fold_build2 (MINUS_EXPR, type, base0,
+ build_int_cst_type (type, 1));
}
+ else
+ return false;
- return expr;
+ niter->may_be_zero = fold_build2 (GT_EXPR, boolean_type_node,
+ base0, base1);
+ niter->niter = fold_build2 (MINUS_EXPR, type, base1, base0);
+ break;
+
+ default:
+ gcc_unreachable ();
}
- e = instantiate_parameters (loop, expr);
- if (is_gimple_min_invariant (e))
- return e;
+ niter->niter = fold_convert (niter_type, niter->niter);
+ niter->additional_info = boolean_true_node;
+ return true;
+}
- return expr;
+/* Substitute NEW for OLD in EXPR and fold the result. */
+
+static tree
+simplify_replace_tree (tree expr, tree old, tree new)
+{
+ unsigned i, n;
+ tree ret = NULL_TREE, e, se;
+
+ if (!expr)
+ return NULL_TREE;
+
+ if (expr == old
+ || operand_equal_p (expr, old, 0))
+ return unshare_expr (new);
+
+ if (!EXPR_P (expr))
+ return expr;
+
+ n = TREE_CODE_LENGTH (TREE_CODE (expr));
+ for (i = 0; i < n; i++)
+ {
+ e = TREE_OPERAND (expr, i);
+ se = simplify_replace_tree (e, old, new);
+ if (e == se)
+ continue;
+
+ if (!ret)
+ ret = copy_node (expr);
+
+ TREE_OPERAND (ret, i) = se;
+ }
+
+ return (ret ? fold (ret) : expr);
+}
+
+/* Expand definitions of ssa names in EXPR as long as they are simple
+ enough, and return the new expression. */
+
+static tree
+expand_simple_operations (tree expr)
+{
+ unsigned i, n;
+ tree ret = NULL_TREE, e, ee, stmt;
+ enum tree_code code = TREE_CODE (expr);
+
+ if (is_gimple_min_invariant (expr))
+ return expr;
+
+ if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
+ {
+ n = TREE_CODE_LENGTH (code);
+ for (i = 0; i < n; i++)
+ {
+ e = TREE_OPERAND (expr, i);
+ ee = expand_simple_operations (e);
+ if (e == ee)
+ continue;
+
+ if (!ret)
+ ret = copy_node (expr);
+
+ TREE_OPERAND (ret, i) = ee;
+ }
+
+ return (ret ? fold (ret) : expr);
+ }
+
+ if (TREE_CODE (expr) != SSA_NAME)
+ return expr;
+
+ stmt = SSA_NAME_DEF_STMT (expr);
+ if (TREE_CODE (stmt) != MODIFY_EXPR)
+ return expr;
+
+ e = TREE_OPERAND (stmt, 1);
+ if (/* Casts are simple. */
+ TREE_CODE (e) != NOP_EXPR
+ && TREE_CODE (e) != CONVERT_EXPR
+ /* 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)
+ && is_gimple_min_invariant (TREE_OPERAND (e, 1))))
+ return expr;
+
+ return expand_simple_operations (e);
}
/* Tries to simplify EXPR using the condition COND. Returns the simplified
- expression (or EXPR unchanged, if no simplification was possible).*/
+ expression (or EXPR unchanged, if no simplification was possible). */
static tree
-tree_simplify_using_condition (tree cond, tree expr)
+tree_simplify_using_condition_1 (tree cond, tree expr)
{
bool changed;
- tree e, e0, e1, e2, notcond;
+ tree e, te, e0, e1, e2, notcond;
enum tree_code code = TREE_CODE (expr);
if (code == INTEGER_CST)
{
changed = false;
- e0 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 0));
+ e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
if (TREE_OPERAND (expr, 0) != e0)
changed = true;
- e1 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 1));
+ e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
if (TREE_OPERAND (expr, 1) != e1)
changed = true;
if (code == COND_EXPR)
{
- e2 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 2));
+ e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2));
if (TREE_OPERAND (expr, 2) != e2)
changed = true;
}
if (changed)
{
if (code == COND_EXPR)
- expr = build (code, boolean_type_node, e0, e1, e2);
+ expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
else
- expr = build (code, boolean_type_node, e0, e1);
- expr = fold (expr);
+ expr = fold_build2 (code, boolean_type_node, e0, e1);
}
return expr;
}
+ /* In case COND is equality, we may be able to simplify EXPR by copy/constant
+ propagation, and vice versa. Fold does not handle this, since it is
+ considered too expensive. */
+ if (TREE_CODE (cond) == EQ_EXPR)
+ {
+ e0 = TREE_OPERAND (cond, 0);
+ e1 = TREE_OPERAND (cond, 1);
+
+ /* We know that e0 == e1. Check whether we cannot simplify expr
+ using this fact. */
+ e = simplify_replace_tree (expr, e0, e1);
+ if (zero_p (e) || nonzero_p (e))
+ return e;
+
+ e = simplify_replace_tree (expr, e1, e0);
+ if (zero_p (e) || nonzero_p (e))
+ return e;
+ }
+ if (TREE_CODE (expr) == EQ_EXPR)
+ {
+ e0 = TREE_OPERAND (expr, 0);
+ e1 = TREE_OPERAND (expr, 1);
+
+ /* If e0 == e1 (EXPR) implies !COND, then EXPR cannot be true. */
+ e = simplify_replace_tree (cond, e0, e1);
+ if (zero_p (e))
+ return e;
+ e = simplify_replace_tree (cond, e1, e0);
+ if (zero_p (e))
+ return e;
+ }
+ if (TREE_CODE (expr) == NE_EXPR)
+ {
+ e0 = TREE_OPERAND (expr, 0);
+ e1 = TREE_OPERAND (expr, 1);
+
+ /* If e0 == e1 (!EXPR) implies !COND, then EXPR must be true. */
+ e = simplify_replace_tree (cond, e0, e1);
+ if (zero_p (e))
+ return boolean_true_node;
+ e = simplify_replace_tree (cond, e1, e0);
+ if (zero_p (e))
+ return boolean_true_node;
+ }
+
+ te = expand_simple_operations (expr);
+
/* Check whether COND ==> EXPR. */
notcond = invert_truthvalue (cond);
- e = fold (build (TRUTH_OR_EXPR, boolean_type_node,
- notcond, expr));
- if (integer_nonzerop (e))
+ e = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
+ if (nonzero_p (e))
return e;
/* Check whether COND ==> not EXPR. */
- e = fold (build (TRUTH_AND_EXPR, boolean_type_node,
- cond, expr));
- if (integer_zerop (e))
+ e = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, cond, te);
+ if (zero_p (e))
return e;
return expr;
}
+/* Tries to simplify EXPR using the condition COND. Returns the simplified
+ expression (or EXPR unchanged, if no simplification was possible).
+ Wrapper around tree_simplify_using_condition_1 that ensures that chains
+ of simple operations in definitions of ssa names in COND are expanded,
+ so that things like casts or incrementing the value of the bound before
+ the loop do not cause us to fail. */
+
+static tree
+tree_simplify_using_condition (tree cond, tree expr)
+{
+ cond = expand_simple_operations (cond);
+
+ return tree_simplify_using_condition_1 (cond, expr);
+}
+
/* Tries to simplify EXPR using the conditions on entry to LOOP.
Record the conditions used for simplification to CONDS_USED.
Returns the simplified expression (or EXPR unchanged, if no
bb != ENTRY_BLOCK_PTR;
bb = get_immediate_dominator (CDI_DOMINATORS, bb))
{
- e = bb->pred;
- if (e->pred_next)
+ if (!single_pred_p (bb))
continue;
+ e = single_pred_edge (bb);
if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
continue;
exp = tree_simplify_using_condition (cond, expr);
if (exp != expr)
- *conds_used = fold (build (TRUTH_AND_EXPR,
+ *conds_used = fold_build2 (TRUTH_AND_EXPR,
boolean_type_node,
*conds_used,
- cond));
+ cond);
expr = exp;
}
return expr;
}
+/* Tries to simplify EXPR using the evolutions of the loop invariants
+ in the superloops of LOOP. Returns the simplified expression
+ (or EXPR unchanged, if no simplification was possible). */
+
+static tree
+simplify_using_outer_evolutions (struct loop *loop, tree expr)
+{
+ enum tree_code code = TREE_CODE (expr);
+ bool changed;
+ tree e, e0, e1, e2;
+
+ if (is_gimple_min_invariant (expr))
+ return expr;
+
+ if (code == TRUTH_OR_EXPR
+ || code == TRUTH_AND_EXPR
+ || code == COND_EXPR)
+ {
+ changed = false;
+
+ e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
+ if (TREE_OPERAND (expr, 0) != e0)
+ changed = true;
+
+ e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
+ if (TREE_OPERAND (expr, 1) != e1)
+ changed = true;
+
+ if (code == COND_EXPR)
+ {
+ e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
+ if (TREE_OPERAND (expr, 2) != e2)
+ changed = true;
+ }
+ else
+ e2 = NULL_TREE;
+
+ if (changed)
+ {
+ if (code == COND_EXPR)
+ expr = fold_build3 (code, boolean_type_node, e0, e1, e2);
+ else
+ expr = fold_build2 (code, boolean_type_node, e0, e1);
+ }
+
+ return expr;
+ }
+
+ e = instantiate_parameters (loop, expr);
+ if (is_gimple_min_invariant (e))
+ return e;
+
+ return expr;
+}
+
/* Stores description of number of iterations of LOOP derived from
EXIT (an exit edge of the LOOP) in NITER. Returns true if some
useful information could be derived (and fields of NITER has
return false;
niter->niter = NULL_TREE;
- number_of_iterations_cond (type, base0, step0, code, base1, step1,
- niter);
- if (!niter->niter)
- return false;
- niter->assumptions = simplify_using_outer_evolutions (loop,
- niter->assumptions);
- niter->may_be_zero = simplify_using_outer_evolutions (loop,
- niter->may_be_zero);
- niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
+ /* 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;
+ }
+
+ if (optimize >= 3)
+ {
+ niter->assumptions = simplify_using_outer_evolutions (loop,
+ niter->assumptions);
+ niter->may_be_zero = simplify_using_outer_evolutions (loop,
+ niter->may_be_zero);
+ niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
+ }
niter->additional_info = boolean_true_node;
niter->assumptions
return integer_onep (niter->assumptions);
}
+/* Try to determine the number of iterations of LOOP. If we succeed,
+ expression giving number of iterations is returned and *EXIT is
+ set to the edge from that the information is obtained. Otherwise
+ chrec_dont_know is returned. */
+
+tree
+find_loop_niter (struct loop *loop, edge *exit)
+{
+ unsigned n_exits, i;
+ edge *exits = get_loop_exit_edges (loop, &n_exits);
+ edge ex;
+ tree niter = NULL_TREE, aniter;
+ struct tree_niter_desc desc;
+
+ *exit = NULL;
+ for (i = 0; i < n_exits; i++)
+ {
+ ex = exits[i];
+ if (!just_once_each_iteration_p (loop, ex->src))
+ continue;
+
+ if (!number_of_iterations_exit (loop, ex, &desc))
+ continue;
+
+ if (nonzero_p (desc.may_be_zero))
+ {
+ /* We exit in the first iteration through this exit.
+ We won't find anything better. */
+ niter = build_int_cst_type (unsigned_type_node, 0);
+ *exit = ex;
+ break;
+ }
+
+ if (!zero_p (desc.may_be_zero))
+ continue;
+
+ aniter = desc.niter;
+
+ if (!niter)
+ {
+ /* Nothing recorded yet. */
+ niter = aniter;
+ *exit = ex;
+ continue;
+ }
+
+ /* Prefer constants, the lower the better. */
+ if (TREE_CODE (aniter) != INTEGER_CST)
+ continue;
+
+ if (TREE_CODE (niter) != INTEGER_CST)
+ {
+ niter = aniter;
+ *exit = ex;
+ continue;
+ }
+
+ if (tree_int_cst_lt (aniter, niter))
+ {
+ niter = aniter;
+ *exit = ex;
+ continue;
+ }
+ }
+ free (exits);
+
+ return niter ? niter : chrec_dont_know;
+}
+
/*
Analysis of a number of iterations of a loop by a brute-force evaluation.
if (TREE_CODE (stmt) != MODIFY_EXPR)
return NULL_TREE;
- get_stmt_operands (stmt);
if (NUM_VUSES (STMT_VUSE_OPS (stmt)) > 0)
return NULL_TREE;
if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) > 0)
for (j = 0; j < 2; j++)
aval[j] = get_val_for (op[j], val[j]);
- acnd = fold (build (cmp, boolean_type_node, aval[0], aval[1]));
- if (integer_zerop (acnd))
+ acnd = fold_build2 (cmp, boolean_type_node, aval[0], aval[1]);
+ if (zero_p (acnd))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
continue;
aniter = loop_niter_by_eval (loop, ex);
- if (chrec_contains_undetermined (aniter)
- || TREE_CODE (aniter) != INTEGER_CST)
+ if (chrec_contains_undetermined (aniter))
continue;
if (niter
- && !integer_nonzerop (fold (build (LT_EXPR, boolean_type_node,
- aniter, niter))))
+ && !tree_int_cst_lt (aniter, niter))
continue;
niter = aniter;
*/
-/* The structure describing a bound on number of iterations of a loop. */
-
-struct nb_iter_bound
-{
- tree bound; /* The expression whose value is an upper bound on the
- number of executions of anything after ... */
- tree at_stmt; /* ... this statement during one execution of loop. */
- tree additional; /* A conjunction of conditions the operands of BOUND
- satisfy. The additional information about the value
- of the bound may be derived from it. */
- struct nb_iter_bound *next;
- /* The next bound in a list. */
-};
-
/* Records that AT_STMT is executed at most BOUND times in LOOP. The
additional condition ADDITIONAL is recorded with the bound. */
-static void
+void
record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt)
{
struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound));
niter = niter_desc.niter;
type = TREE_TYPE (niter);
- if (!integer_zerop (niter_desc.may_be_zero)
- && !integer_nonzerop (niter_desc.may_be_zero))
- niter = build (COND_EXPR, type, niter_desc.may_be_zero,
- convert (type, integer_zero_node),
- niter);
+ if (!zero_p (niter_desc.may_be_zero)
+ && !nonzero_p (niter_desc.may_be_zero))
+ niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
+ build_int_cst_type (type, 0),
+ niter);
record_estimate (loop, niter,
niter_desc.additional_info,
last_stmt (exits[i]->src));
}
free (exits);
- /* TODO Here we could use other possibilities, like bounds of arrays accessed
- in the loop. */
+ /* 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);
+ }
}
/* Records estimates on numbers of iterations of LOOPS. */
else
type = typeb;
- a = convert (type, a);
- b = convert (type, b);
+ a = fold_convert (type, a);
+ b = fold_convert (type, b);
- if (integer_nonzerop (fold (build (EQ_EXPR, boolean_type_node, a, b))))
+ if (nonzero_p (fold_build2 (EQ_EXPR, boolean_type_node, a, b)))
return 0;
- if (integer_nonzerop (fold (build (LT_EXPR, boolean_type_node, a, b))))
+ if (nonzero_p (fold_build2 (LT_EXPR, boolean_type_node, a, b)))
return 1;
- if (integer_nonzerop (fold (build (GT_EXPR, boolean_type_node, a, b))))
+ if (nonzero_p (fold_build2 (GT_EXPR, boolean_type_node, a, b)))
return -1;
return 2;
}
-/* Returns the largest value obtainable by casting something in INNER type to
- OUTER type. */
-
-tree
-upper_bound_in_type (tree outer, tree inner)
-{
- unsigned HOST_WIDE_INT lo, hi;
- unsigned bits = TYPE_PRECISION (inner);
-
- if (TYPE_UNSIGNED (outer) || TYPE_UNSIGNED (inner))
- {
- /* Zero extending in these cases. */
- if (bits <= HOST_BITS_PER_WIDE_INT)
- {
- hi = 0;
- lo = (~(unsigned HOST_WIDE_INT) 0)
- >> (HOST_BITS_PER_WIDE_INT - bits);
- }
- else
- {
- hi = (~(unsigned HOST_WIDE_INT) 0)
- >> (2 * HOST_BITS_PER_WIDE_INT - bits);
- lo = ~(unsigned HOST_WIDE_INT) 0;
- }
- }
- else
- {
- /* Sign extending in these cases. */
- if (bits <= HOST_BITS_PER_WIDE_INT)
- {
- hi = 0;
- lo = (~(unsigned HOST_WIDE_INT) 0)
- >> (HOST_BITS_PER_WIDE_INT - bits) >> 1;
- }
- else
- {
- hi = (~(unsigned HOST_WIDE_INT) 0)
- >> (2 * HOST_BITS_PER_WIDE_INT - bits) >> 1;
- lo = ~(unsigned HOST_WIDE_INT) 0;
- }
- }
-
- return convert (outer,
- convert (inner,
- build_int_cst_wide (NULL_TREE, lo, hi)));
-}
-
-/* Returns the smallest value obtainable by casting something in INNER type to
- OUTER type. */
-
-tree
-lower_bound_in_type (tree outer, tree inner)
-{
- unsigned HOST_WIDE_INT lo, hi;
- unsigned bits = TYPE_PRECISION (inner);
-
- if (TYPE_UNSIGNED (outer) || TYPE_UNSIGNED (inner))
- lo = hi = 0;
- else if (bits <= HOST_BITS_PER_WIDE_INT)
- {
- hi = ~(unsigned HOST_WIDE_INT) 0;
- lo = (~(unsigned HOST_WIDE_INT) 0) << (bits - 1);
- }
- else
- {
- hi = (~(unsigned HOST_WIDE_INT) 0) << (bits - HOST_BITS_PER_WIDE_INT - 1);
- lo = 0;
- }
-
- return convert (outer,
- convert (inner,
- build_int_cst_wide (NULL_TREE, lo, hi)));
-}
-
/* Returns true if statement S1 dominates statement S2. */
static bool
tree valid_niter, extreme, unsigned_type, delta, bound_type;
tree cond;
- b = convert (type, base);
- bplusstep = convert (type,
- fold (build (PLUS_EXPR, inner_type, base, step)));
- new_step = fold (build (MINUS_EXPR, type, bplusstep, b));
+ 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 NULL_TREE;
{
case -1:
extreme = upper_bound_in_type (type, inner_type);
- delta = fold (build (MINUS_EXPR, type, extreme, b));
+ delta = fold_build2 (MINUS_EXPR, type, extreme, b);
new_step_abs = new_step;
break;
case 1:
extreme = lower_bound_in_type (type, inner_type);
- new_step_abs = fold (build (NEGATE_EXPR, type, new_step));
- delta = fold (build (MINUS_EXPR, type, b, extreme));
+ new_step_abs = fold_build1 (NEGATE_EXPR, type, new_step);
+ delta = fold_build2 (MINUS_EXPR, type, b, extreme);
break;
case 0:
}
unsigned_type = unsigned_type_for (type);
- delta = convert (unsigned_type, delta);
- new_step_abs = convert (unsigned_type, new_step_abs);
- valid_niter = fold (build (FLOOR_DIV_EXPR, unsigned_type,
- delta, new_step_abs));
+ delta = fold_convert (unsigned_type, delta);
+ new_step_abs = fold_convert (unsigned_type, new_step_abs);
+ valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type,
+ delta, new_step_abs);
bound_type = TREE_TYPE (bound);
if (TYPE_PRECISION (type) > TYPE_PRECISION (bound_type))
- bound = convert (unsigned_type, bound);
+ bound = fold_convert (unsigned_type, bound);
else
- valid_niter = convert (bound_type, valid_niter);
+ valid_niter = fold_convert (bound_type, valid_niter);
if (at_stmt && stmt_dominates_stmt_p (of, at_stmt))
{
/* After the statement OF we know that anything is executed at most
BOUND times. */
- cond = build (GE_EXPR, boolean_type_node, valid_niter, bound);
+ cond = fold_build2 (GE_EXPR, boolean_type_node, valid_niter, bound);
}
else
{
/* Before the statement OF we know that anything is executed at most
BOUND + 1 times. */
- cond = build (GT_EXPR, boolean_type_node, valid_niter, bound);
+ cond = fold_build2 (GT_EXPR, boolean_type_node, valid_niter, bound);
}
- cond = fold (cond);
- if (integer_nonzerop (cond))
+ if (nonzero_p (cond))
return new_step;
/* Try taking additional conditions into account. */
- cond = build (TRUTH_OR_EXPR, boolean_type_node,
- invert_truthvalue (additional),
- cond);
- cond = fold (cond);
- if (integer_nonzerop (cond))
+ cond = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
+ invert_truthvalue (additional),
+ cond);
+ if (nonzero_p (cond))
return new_step;
return NULL_TREE;
OSDN Git Service
