tree-ssa-loop-niter.c [plain text]
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "output.h"
#include "diagnostic.h"
#include "tree-flow.h"
#include "tree-dump.h"
#include "cfgloop.h"
#include "tree-pass.h"
#include "ggc.h"
#include "tree-chrec.h"
#include "tree-scalar-evolution.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)
#define EXEC_BINARY nondestructive_fold_binary_to_constant
#define EXEC_UNARY nondestructive_fold_unary_to_constant
bool
zero_p (tree arg)
{
if (!arg)
return true;
if (TREE_CODE (arg) != INTEGER_CST)
return false;
return (TREE_INT_CST_LOW (arg) == 0 && TREE_INT_CST_HIGH (arg) == 0);
}
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);
}
static tree
inverse (tree x, tree mask)
{
tree type = TREE_TYPE (x);
tree ctr = EXEC_BINARY (RSHIFT_EXPR, type, mask, integer_one_node);
tree rslt = build_int_cst_type (type, 1);
while (nonzero_p (ctr))
{
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);
}
return rslt;
}
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 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;
if (code == GE_EXPR
|| code == GT_EXPR)
{
SWAP (base0, base1);
SWAP (step0, step1);
code = swap_tree_comparison (code);
}
if (!zero_p (step0) && !zero_p (step1))
{
if (code != NE_EXPR)
return;
step0 = EXEC_BINARY (MINUS_EXPR, type, step0, step1);
step1 = NULL_TREE;
}
if (zero_p (step0) && zero_p (step1))
return;
if (code != NE_EXPR)
{
if (step0 && !tree_expr_nonnegative_p (step0))
return;
if (!zero_p (step1) && tree_expr_nonnegative_p (step1))
return;
}
if (POINTER_TYPE_P (type))
{
mmin = mmax = NULL_TREE;
}
else
{
mmin = TYPE_MIN_VALUE (type);
mmax = TYPE_MAX_VALUE (type);
}
if (code == LT_EXPR)
{
if (zero_p (step0))
{
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)));
}
else
{
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)));
}
noloop_assumptions = assumption;
code = LE_EXPR;
was_sharp = true;
}
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 (code != NE_EXPR)
{
if (zero_p (step0))
step = EXEC_UNARY (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;
if (TREE_CODE (delta) == INTEGER_CST)
{
tmp = EXEC_BINARY (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 if (zero_p (step0))
{
if (!mmin)
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 (build2 (LE_EXPR, boolean_type_node,
bound, base0));
}
}
else
{
if (!mmax)
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 (build2 (LE_EXPR, boolean_type_node,
base1, bound));
}
}
}
if (!zero_p (may_xform))
{
if (!nonzero_p (may_xform))
assumptions = may_xform;
if (zero_p (step0))
{
base0 = 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 (PLUS_EXPR, type, base1, step));
}
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;
}
}
niter_type = unsigned_type_for (type);
signed_niter_type = signed_type_for (type);
if (code == NE_EXPR)
{
base1 = fold (build2 (MINUS_EXPR, type, base1, base0));
base0 = NULL_TREE;
if (!zero_p (step1))
step0 = EXEC_UNARY (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);
base1 = fold (build1 (NEGATE_EXPR, type, base1));
}
base1 = fold_convert (niter_type, base1);
step0 = fold_convert (niter_type, step0);
s = step0;
d = integer_one_node;
bound = build_int_cst (niter_type, -1);
while (1)
{
tmp = EXEC_BINARY (BIT_AND_EXPR, niter_type, s,
build_int_cst (niter_type, 1));
if (nonzero_p (tmp))
break;
s = EXEC_BINARY (RSHIFT_EXPR, niter_type, s,
build_int_cst (niter_type, 1));
d = EXEC_BINARY (LSHIFT_EXPR, niter_type, d,
build_int_cst (niter_type, 1));
bound = EXEC_BINARY (RSHIFT_EXPR, niter_type, bound,
build_int_cst (niter_type, 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 (zero_p (step1))
{
if (mmax)
{
bound = EXEC_BINARY (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 (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
{
if (mmin)
{
bound = EXEC_BINARY (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;
}
niter->assumptions = assumptions;
niter->may_be_zero = noloop_assumptions;
return;
zero_iter:
niter->assumptions = boolean_true_node;
niter->may_be_zero = boolean_true_node;
niter->niter = build_int_cst_type (type, 0);
return;
}
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 = build3 (code, boolean_type_node, e0, e1, e2);
else
expr = build2 (code, boolean_type_node, e0, e1);
expr = fold (expr);
}
return expr;
}
e = instantiate_parameters (loop, expr);
if (is_gimple_min_invariant (e))
return e;
return expr;
}
static tree
tree_simplify_using_condition (tree cond, tree expr)
{
bool changed;
tree e, e0, e1, e2, notcond;
enum tree_code code = TREE_CODE (expr);
if (code == INTEGER_CST)
return expr;
if (code == TRUTH_OR_EXPR
|| code == TRUTH_AND_EXPR
|| code == COND_EXPR)
{
changed = false;
e0 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 0));
if (TREE_OPERAND (expr, 0) != e0)
changed = true;
e1 = tree_simplify_using_condition (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));
if (TREE_OPERAND (expr, 2) != e2)
changed = true;
}
else
e2 = NULL_TREE;
if (changed)
{
if (code == COND_EXPR)
expr = build3 (code, boolean_type_node, e0, e1, e2);
else
expr = build2 (code, boolean_type_node, e0, e1);
expr = fold (expr);
}
return expr;
}
notcond = invert_truthvalue (cond);
e = fold (build2 (TRUTH_OR_EXPR, boolean_type_node,
notcond, expr));
if (nonzero_p (e))
return e;
e = fold (build2 (TRUTH_AND_EXPR, boolean_type_node,
cond, expr));
if (zero_p (e))
return e;
return expr;
}
static tree
simplify_using_initial_conditions (struct loop *loop, tree expr,
tree *conds_used)
{
edge e;
basic_block bb;
tree exp, cond;
if (TREE_CODE (expr) == INTEGER_CST)
return expr;
for (bb = loop->header;
bb != ENTRY_BLOCK_PTR;
bb = get_immediate_dominator (CDI_DOMINATORS, bb))
{
e = EDGE_PRED (bb, 0);
if (EDGE_COUNT (bb->preds) > 1)
continue;
if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
continue;
cond = COND_EXPR_COND (last_stmt (e->src));
if (e->flags & EDGE_FALSE_VALUE)
cond = invert_truthvalue (cond);
exp = tree_simplify_using_condition (cond, expr);
if (exp != expr)
*conds_used = fold (build2 (TRUTH_AND_EXPR,
boolean_type_node,
*conds_used,
cond));
expr = exp;
}
return expr;
}
bool
number_of_iterations_exit (struct loop *loop, edge exit,
struct tree_niter_desc *niter)
{
tree stmt, cond, type;
tree op0, base0, step0;
tree op1, base1, step1;
enum tree_code code;
if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
return false;
niter->assumptions = boolean_false_node;
stmt = last_stmt (exit->src);
if (!stmt || TREE_CODE (stmt) != COND_EXPR)
return false;
cond = COND_EXPR_COND (stmt);
if (exit->flags & EDGE_TRUE_VALUE)
cond = invert_truthvalue (cond);
code = TREE_CODE (cond);
switch (code)
{
case GT_EXPR:
case GE_EXPR:
case NE_EXPR:
case LT_EXPR:
case LE_EXPR:
break;
default:
return false;
}
op0 = TREE_OPERAND (cond, 0);
op1 = TREE_OPERAND (cond, 1);
type = TREE_TYPE (op0);
if (TREE_CODE (type) != INTEGER_TYPE
&& !POINTER_TYPE_P (type))
return false;
if (!simple_iv (loop, stmt, op0, &base0, &step0))
return false;
if (!simple_iv (loop, stmt, op1, &base1, &step1))
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);
niter->additional_info = boolean_true_node;
niter->assumptions
= simplify_using_initial_conditions (loop,
niter->assumptions,
&niter->additional_info);
niter->may_be_zero
= simplify_using_initial_conditions (loop,
niter->may_be_zero,
&niter->additional_info);
return integer_onep (niter->assumptions);
}
#define MAX_ITERATIONS_TO_TRACK \
((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
static tree
chain_of_csts_start (struct loop *loop, tree x)
{
tree stmt = SSA_NAME_DEF_STMT (x);
basic_block bb = bb_for_stmt (stmt);
use_optype uses;
if (!bb
|| !flow_bb_inside_loop_p (loop, bb))
return NULL_TREE;
if (TREE_CODE (stmt) == PHI_NODE)
{
if (bb == loop->header)
return stmt;
return NULL_TREE;
}
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)
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)
return NULL_TREE;
return chain_of_csts_start (loop, USE_OP (uses, 0));
}
static tree
get_base_for (struct loop *loop, tree x)
{
tree phi, init, next;
if (is_gimple_min_invariant (x))
return x;
phi = chain_of_csts_start (loop, x);
if (!phi)
return NULL_TREE;
init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
if (TREE_CODE (next) != SSA_NAME)
return NULL_TREE;
if (!is_gimple_min_invariant (init))
return NULL_TREE;
if (chain_of_csts_start (loop, next) != phi)
return NULL_TREE;
return phi;
}
static tree
get_val_for (tree x, tree base)
{
tree stmt, nx, val;
use_optype uses;
use_operand_p op;
if (!x)
return base;
stmt = SSA_NAME_DEF_STMT (x);
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);
return val;
}
tree
loop_niter_by_eval (struct loop *loop, edge exit)
{
tree cond, cnd, acnd;
tree op[2], val[2], next[2], aval[2], phi[2];
unsigned i, j;
enum tree_code cmp;
cond = last_stmt (exit->src);
if (!cond || TREE_CODE (cond) != COND_EXPR)
return chrec_dont_know;
cnd = COND_EXPR_COND (cond);
if (exit->flags & EDGE_TRUE_VALUE)
cnd = invert_truthvalue (cnd);
cmp = TREE_CODE (cnd);
switch (cmp)
{
case EQ_EXPR:
case NE_EXPR:
case GT_EXPR:
case GE_EXPR:
case LT_EXPR:
case LE_EXPR:
for (j = 0; j < 2; j++)
op[j] = TREE_OPERAND (cnd, j);
break;
default:
return chrec_dont_know;
}
for (j = 0; j < 2; j++)
{
phi[j] = get_base_for (loop, op[j]);
if (!phi[j])
return chrec_dont_know;
}
for (j = 0; j < 2; j++)
{
if (TREE_CODE (phi[j]) == PHI_NODE)
{
val[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_preheader_edge (loop));
next[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_latch_edge (loop));
}
else
{
val[j] = phi[j];
next[j] = NULL_TREE;
op[j] = NULL_TREE;
}
}
for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
{
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))
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
"Proved that loop %d iterates %d times using brute force.\n",
loop->num, i);
return build_int_cst (unsigned_type_node, i);
}
for (j = 0; j < 2; j++)
val[j] = get_val_for (next[j], val[j]);
}
return chrec_dont_know;
}
tree
find_loop_niter_by_eval (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;
*exit = NULL;
for (i = 0; i < n_exits; i++)
{
ex = exits[i];
if (!just_once_each_iteration_p (loop, ex->src))
continue;
aniter = loop_niter_by_eval (loop, ex);
if (chrec_contains_undetermined (aniter)
|| TREE_CODE (aniter) != INTEGER_CST)
continue;
if (niter
&& !nonzero_p (fold (build2 (LT_EXPR, boolean_type_node,
aniter, niter))))
continue;
niter = aniter;
*exit = ex;
}
free (exits);
return niter ? niter : chrec_dont_know;
}
struct nb_iter_bound
{
tree bound;
tree at_stmt;
tree additional;
struct nb_iter_bound *next;
};
static void
record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt)
{
struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound));
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Statements after ");
print_generic_expr (dump_file, at_stmt, TDF_SLIM);
fprintf (dump_file, " are executed at most ");
print_generic_expr (dump_file, bound, TDF_SLIM);
fprintf (dump_file, " times in loop %d.\n", loop->num);
}
elt->bound = bound;
elt->at_stmt = at_stmt;
elt->additional = additional;
elt->next = loop->bounds;
loop->bounds = elt;
}
static void
estimate_numbers_of_iterations_loop (struct loop *loop)
{
edge *exits;
tree niter, type;
unsigned i, n_exits;
struct tree_niter_desc niter_desc;
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))
continue;
niter = niter_desc.niter;
type = TREE_TYPE (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);
}
void
estimate_numbers_of_iterations (struct loops *loops)
{
unsigned i;
struct loop *loop;
for (i = 1; i < loops->num; i++)
{
loop = loops->parray[i];
if (loop)
estimate_numbers_of_iterations_loop (loop);
}
}
static int
compare_trees (tree a, tree b)
{
tree typea = TREE_TYPE (a), typeb = TREE_TYPE (b);
tree type;
if (TYPE_PRECISION (typea) > TYPE_PRECISION (typeb))
type = typea;
else
type = typeb;
a = fold_convert (type, a);
b = fold_convert (type, b);
if (nonzero_p (fold (build2 (EQ_EXPR, boolean_type_node, a, b))))
return 0;
if (nonzero_p (fold (build2 (LT_EXPR, boolean_type_node, a, b))))
return 1;
if (nonzero_p (fold (build2 (GT_EXPR, boolean_type_node, a, b))))
return -1;
return 2;
}
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))
{
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
{
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));
}
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));
}
static bool
stmt_dominates_stmt_p (tree s1, tree s2)
{
basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2);
if (!bb1
|| s1 == s2)
return true;
if (bb1 == bb2)
{
block_stmt_iterator bsi;
for (bsi = bsi_start (bb1); bsi_stmt (bsi) != s2; bsi_next (&bsi))
if (bsi_stmt (bsi) == s1)
return true;
return false;
}
return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
}
static tree
can_count_iv_in_wider_type_bound (tree type, tree base, tree step,
tree at_stmt,
tree bound,
tree additional,
tree of)
{
tree inner_type = TREE_TYPE (base), b, bplusstep, new_step, new_step_abs;
tree valid_niter, extreme, unsigned_type, delta, bound_type;
tree cond;
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;
switch (compare_trees (bplusstep, b))
{
case -1:
extreme = upper_bound_in_type (type, inner_type);
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 (build1 (NEGATE_EXPR, type, new_step));
delta = fold (build2 (MINUS_EXPR, type, b, extreme));
break;
case 0:
return new_step;
default:
return NULL_TREE;
}
unsigned_type = unsigned_type_for (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 = fold_convert (unsigned_type, bound);
else
valid_niter = fold_convert (bound_type, valid_niter);
if (at_stmt && stmt_dominates_stmt_p (of, at_stmt))
{
cond = build2 (GE_EXPR, boolean_type_node, valid_niter, bound);
}
else
{
cond = build2 (GT_EXPR, boolean_type_node, valid_niter, bound);
}
cond = fold (cond);
if (nonzero_p (cond))
return new_step;
cond = build2 (TRUTH_OR_EXPR, boolean_type_node,
invert_truthvalue (additional),
cond);
cond = fold (cond);
if (nonzero_p (cond))
return new_step;
return NULL_TREE;
}
tree
can_count_iv_in_wider_type (struct loop *loop, tree type, tree base, tree step,
tree at_stmt)
{
struct nb_iter_bound *bound;
tree new_step;
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;
}
return NULL_TREE;
}
static void
free_numbers_of_iterations_estimates_loop (struct loop *loop)
{
struct nb_iter_bound *bound, *next;
for (bound = loop->bounds; bound; bound = next)
{
next = bound->next;
free (bound);
}
loop->bounds = NULL;
}
void
free_numbers_of_iterations_estimates (struct loops *loops)
{
unsigned i;
struct loop *loop;
for (i = 1; i < loops->num; i++)
{
loop = loops->parray[i];
if (loop)
free_numbers_of_iterations_estimates_loop (loop);
}
}
static void
unmark_surely_finite_loop (struct loop *loop)
{
edge *exits;
unsigned i, n_exits;
struct tree_niter_desc niter_desc;
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))
{
loop_latch_edge (loop)->flags &= ~EDGE_DFS_BACK;
return;
}
}
void
mark_maybe_infinite_loops (struct loops *loops)
{
unsigned i;
struct loop *loop;
basic_block bb;
edge e;
tree stmt;
bool inserted = false;
block_stmt_iterator bsi;
mark_dfs_back_edges ();
for (i = 1; i < loops->num; i++)
{
loop = loops->parray[i];
if (loop)
unmark_surely_finite_loop (loop);
}
FOR_EACH_BB (bb)
{
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
if (e->flags & EDGE_DFS_BACK)
{
stmt = build_function_call_expr (built_in_decls[BUILT_IN_MAYBE_INFINITE_LOOP],
NULL);
if (!(e->flags & EDGE_ABNORMAL))
{
bsi_insert_on_edge (e, stmt);
inserted = true;
continue;
}
bsi = bsi_last (e->src);
if (!bsi_end_p (bsi)
&& stmt_ends_bb_p (bsi_stmt (bsi)))
bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
else
bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
}
}
if (inserted)
loop_commit_inserts ();
}