/* 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.
#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
/*
return (TREE_INT_CST_LOW (arg) != 0 || TREE_INT_CST_HIGH (arg) != 0);
}
-/* Returns number of zeros at the end of binary representation of X.
-
- ??? Use ffs if available? */
-
-static tree
-num_ending_zeros (tree x)
-{
- unsigned HOST_WIDE_INT fr, nfr;
- unsigned num, abits;
- tree type = TREE_TYPE (x);
-
- if (TREE_INT_CST_LOW (x) == 0)
- {
- num = HOST_BITS_PER_WIDE_INT;
- fr = TREE_INT_CST_HIGH (x);
- }
- else
- {
- num = 0;
- fr = TREE_INT_CST_LOW (x);
- }
-
- for (abits = HOST_BITS_PER_WIDE_INT / 2; abits; abits /= 2)
- {
- nfr = fr >> abits;
- if (nfr << abits == fr)
- {
- num += abits;
- fr = nfr;
- }
- }
-
- if (num > TYPE_PRECISION (type))
- num = TYPE_PRECISION (type);
-
- return build_int_cst_type (type, num);
-}
-
/* Returns inverse of X modulo 2^s, where MASK = 2^s-1. */
static tree
rslt = build_int_cst_type (type, 1);
for (; ctr; ctr--)
{
- rslt = EXEC_BINARY (MULT_EXPR, type, rslt, x);
- x = EXEC_BINARY (MULT_EXPR, type, x, x);
+ rslt = fold_binary_to_constant (MULT_EXPR, type, rslt, x);
+ x = fold_binary_to_constant (MULT_EXPR, type, x, x);
}
- rslt = EXEC_BINARY (BIT_AND_EXPR, type, rslt, mask);
+ rslt = fold_binary_to_constant (BIT_AND_EXPR, type, rslt, mask);
}
return rslt;
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 (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 = build2 (MINUS_EXPR, type, base1, base0);
if (TREE_CODE (delta) == INTEGER_CST)
{
- tmp = EXEC_BINARY (MINUS_EXPR, type, step,
- build_int_cst_type (type, 1));
+ 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);
+ 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));
}
may_xform = boolean_true_node;
else
{
- bound = EXEC_BINARY (MINUS_EXPR, type, mmax, step);
- bound = EXEC_BINARY (PLUS_EXPR, type, bound, delta);
+ 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 (zero_p (step0))
{
- base0 = build2 (PLUS_EXPR, type, base0, delta);
+ base0 = fold (build2 (PLUS_EXPR, type, base0, delta));
base0 = fold (build2 (MINUS_EXPR, type, base0, step));
}
else
{
- base1 = build2 (MINUS_EXPR, type, base1, delta);
+ base1 = fold (build2 (MINUS_EXPR, type, base1, delta));
base1 = fold (build2 (PLUS_EXPR, type, base1, step));
}
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 (fold_convert (signed_niter_type, step0)))
{
- step0 = EXEC_UNARY (NEGATE_EXPR, type, step0);
+ step0 = fold_unary_to_constant (NEGATE_EXPR, type, step0);
base1 = fold (build1 (NEGATE_EXPR, type, base1));
}
is infinite. Otherwise, the number of iterations is
(inverse(s/d) * (c/d)) mod (size of mode/d). */
bits = num_ending_zeros (step0);
- d = EXEC_BINARY (LSHIFT_EXPR, niter_type,
- build_int_cst_type (niter_type, 1), bits);
- s = EXEC_BINARY (RSHIFT_EXPR, niter_type, step0, bits);
+ 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)
{
if (mmax)
{
- bound = EXEC_BINARY (MINUS_EXPR, type, mmax, step0);
+ 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,
we can again compute number of iterations as (b - (a - s)) / s. */
if (mmin)
{
- bound = EXEC_BINARY (MINUS_EXPR, type, mmin, step1);
+ 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,
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);
+}
+
/* Tries to simplify EXPR using the condition COND. Returns the simplified
expression (or EXPR unchanged, if no simplification was possible).*/
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;
+ }
+
/* Check whether COND ==> EXPR. */
notcond = invert_truthvalue (cond);
e = fold (build2 (TRUTH_OR_EXPR, boolean_type_node,
bb != ENTRY_BLOCK_PTR;
bb = get_immediate_dominator (CDI_DOMINATORS, bb))
{
- e = EDGE_PRED (bb, 0);
- if (EDGE_COUNT (bb->preds) > 1)
+ if (!single_pred_p (bb))
continue;
+ e = single_pred_edge (bb);
if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
continue;
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.
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
- && !nonzero_p (fold (build2 (LT_EXPR, boolean_type_node,
- aniter, niter))))
+ && !tree_int_cst_lt (aniter, niter))
continue;
niter = aniter;
return 2;
}
-/* Returns the largest value obtainable by casting something in INNER type to
- OUTER type. */
-
-static 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 fold_convert (outer,
- build_int_cst_wide (inner, lo, hi));
-}
-
-/* Returns the smallest value obtainable by casting something in INNER type to
- OUTER type. */
-
-static 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 fold_convert (outer,
- build_int_cst_wide (inner, lo, hi));
-}
-
/* Returns true if statement S1 dominates statement S2. */
static bool
OSDN Git Service
