/* 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. */
-static bool
+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);
-static 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
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;
}
/* 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 simmilar to it, but the problem is that here
+ 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))
{
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))
{
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
- cathegory, so handling this case specially is definitely
+ category, so handling this case specially is definitely
worth the troubles. */
may_xform = boolean_true_node;
}
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 = 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);
- may_xform = fold (build (LE_EXPR, boolean_type_node,
+ 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,
+ 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);
+ 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));
- }
+ 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,
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));
+ 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 = fold_binary_to_constant (MINUS_EXPR, type, mmin, step1);
+ assumption = fold (build2 (LE_EXPR, boolean_type_node,
bound, base0));
- assumptions = fold (build (TRUTH_AND_EXPR, boolean_type_node,
+ 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);
+ 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 = fold (build2 (TRUTH_OR_EXPR, boolean_type_node,
noloop_assumptions, assumption));
- delta = fold (build (FLOOR_DIV_EXPR, niter_type, delta,
- convert (niter_type, step)));
+ 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;
}
if (changed)
{
if (code == COND_EXPR)
- expr = build (code, boolean_type_node, e0, e1, e2);
+ expr = build3 (code, boolean_type_node, e0, e1, e2);
else
- expr = build (code, boolean_type_node, e0, e1);
+ expr = build2 (code, boolean_type_node, e0, e1);
expr = fold (expr);
}
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).*/
if (changed)
{
if (code == COND_EXPR)
- expr = build (code, boolean_type_node, e0, e1, e2);
+ expr = build3 (code, boolean_type_node, e0, e1, e2);
else
- expr = build (code, boolean_type_node, e0, e1);
+ expr = build2 (code, boolean_type_node, e0, e1);
expr = fold (expr);
}
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 (build (TRUTH_OR_EXPR, boolean_type_node,
+ e = fold (build2 (TRUTH_OR_EXPR, boolean_type_node,
notcond, expr));
- if (integer_nonzerop (e))
+ if (nonzero_p (e))
return e;
/* Check whether COND ==> not EXPR. */
- e = fold (build (TRUTH_AND_EXPR, boolean_type_node,
+ e = fold (build2 (TRUTH_AND_EXPR, boolean_type_node,
cond, expr));
- if (integer_zerop (e))
+ if (zero_p (e))
return e;
return expr;
bb != ENTRY_BLOCK_PTR;
bb = get_immediate_dominator (CDI_DOMINATORS, bb))
{
- e = bb->pred;
- if (e->pred_next)
+ e = EDGE_PRED (bb, 0);
+ if (EDGE_COUNT (bb->preds) > 1)
continue;
if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
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));
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.
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 = 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 = 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 = 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,
+ cond = build2 (TRUTH_OR_EXPR, boolean_type_node,
invert_truthvalue (additional),
cond);
cond = fold (cond);
- if (integer_nonzerop (cond))
+ if (nonzero_p (cond))
return new_step;
return NULL_TREE;
OSDN Git Service
