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 "intl.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 "tree-data-ref.h"
#include "params.h"
#include "flags.h"
#include "toplev.h"
#include "tree-inline.h"
#define SWAP(X, Y) do { void *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
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 rslt;
unsigned ctr = tree_floor_log2 (mask);
if (TYPE_PRECISION (type) <= HOST_BITS_PER_WIDE_INT)
{
unsigned HOST_WIDE_INT ix;
unsigned HOST_WIDE_INT imask;
unsigned HOST_WIDE_INT irslt = 1;
gcc_assert (cst_and_fits_in_hwi (x));
gcc_assert (cst_and_fits_in_hwi (mask));
ix = int_cst_value (x);
imask = int_cst_value (mask);
for (; ctr; ctr--)
{
irslt *= ix;
ix *= ix;
}
irslt &= imask;
rslt = build_int_cst_type (type, irslt);
}
else
{
rslt = build_int_cst (type, 1);
for (; ctr; ctr--)
{
rslt = int_const_binop (MULT_EXPR, rslt, x, 0);
x = int_const_binop (MULT_EXPR, x, x, 0);
}
rslt = int_const_binop (BIT_AND_EXPR, rslt, mask, 0);
}
return rslt;
}
static bool
number_of_iterations_ne (tree type, affine_iv *iv, tree final,
struct tree_niter_desc *niter, bool never_infinite)
{
tree niter_type = unsigned_type_for (type);
tree s, c, d, bits, assumption, tmp, bound;
niter->control = *iv;
niter->bound = final;
niter->cmp = NE_EXPR;
if (tree_int_cst_sign_bit (iv->step))
{
s = fold_convert (niter_type,
fold_build1 (NEGATE_EXPR, type, iv->step));
c = fold_build2 (MINUS_EXPR, niter_type,
fold_convert (niter_type, iv->base),
fold_convert (niter_type, final));
}
else
{
s = fold_convert (niter_type, iv->step);
c = fold_build2 (MINUS_EXPR, niter_type,
fold_convert (niter_type, final),
fold_convert (niter_type, iv->base));
}
if (integer_onep (s))
{
niter->niter = c;
return true;
}
bits = num_ending_zeros (s);
bound = build_low_bits_mask (niter_type,
(TYPE_PRECISION (niter_type)
- tree_low_cst (bits, 1)));
d = fold_binary_to_constant (LSHIFT_EXPR, niter_type,
build_int_cst (niter_type, 1), bits);
s = fold_binary_to_constant (RSHIFT_EXPR, niter_type, s, bits);
if (!never_infinite)
{
assumption = fold_build2 (FLOOR_MOD_EXPR, niter_type, c, d);
assumption = fold_build2 (EQ_EXPR, boolean_type_node,
assumption, build_int_cst (niter_type, 0));
if (!nonzero_p (assumption))
niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
niter->assumptions, assumption);
}
c = fold_build2 (EXACT_DIV_EXPR, niter_type, c, d);
tmp = fold_build2 (MULT_EXPR, niter_type, c, inverse (s, bound));
niter->niter = fold_build2 (BIT_AND_EXPR, niter_type, tmp, bound);
return true;
}
static bool
number_of_iterations_lt_to_ne (tree type, affine_iv *iv0, affine_iv *iv1,
struct tree_niter_desc *niter,
tree *delta, tree step)
{
tree niter_type = TREE_TYPE (step);
tree mod = fold_build2 (FLOOR_MOD_EXPR, niter_type, *delta, step);
tree tmod;
tree assumption = boolean_true_node, bound, noloop;
if (TREE_CODE (mod) != INTEGER_CST)
return false;
if (nonzero_p (mod))
mod = fold_build2 (MINUS_EXPR, niter_type, step, mod);
tmod = fold_convert (type, mod);
if (nonzero_p (iv0->step))
{
if (!iv1->no_overflow && !zero_p (mod))
{
bound = fold_build2 (MINUS_EXPR, type,
TYPE_MAX_VALUE (type), tmod);
assumption = fold_build2 (LE_EXPR, boolean_type_node,
iv1->base, bound);
if (zero_p (assumption))
return false;
}
noloop = fold_build2 (GT_EXPR, boolean_type_node,
iv0->base,
fold_build2 (PLUS_EXPR, type,
iv1->base, tmod));
}
else
{
if (!iv0->no_overflow && !zero_p (mod))
{
bound = fold_build2 (PLUS_EXPR, type,
TYPE_MIN_VALUE (type), tmod);
assumption = fold_build2 (GE_EXPR, boolean_type_node,
iv0->base, bound);
if (zero_p (assumption))
return false;
}
noloop = fold_build2 (GT_EXPR, boolean_type_node,
fold_build2 (MINUS_EXPR, type,
iv0->base, tmod),
iv1->base);
}
if (!nonzero_p (assumption))
niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
niter->assumptions,
assumption);
if (!zero_p (noloop))
niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
niter->may_be_zero,
noloop);
*delta = fold_build2 (PLUS_EXPR, niter_type, *delta, mod);
return true;
}
static bool
assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
struct tree_niter_desc *niter, tree step)
{
tree bound, d, assumption, diff;
tree niter_type = TREE_TYPE (step);
if (nonzero_p (iv0->step))
{
if (iv0->no_overflow)
return true;
if (TREE_CODE (iv0->base) == INTEGER_CST)
{
d = fold_build2 (MINUS_EXPR, niter_type,
fold_convert (niter_type, TYPE_MAX_VALUE (type)),
fold_convert (niter_type, iv0->base));
diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
}
else
diff = fold_build2 (MINUS_EXPR, niter_type, step,
build_int_cst (niter_type, 1));
bound = fold_build2 (MINUS_EXPR, type,
TYPE_MAX_VALUE (type), fold_convert (type, diff));
assumption = fold_build2 (LE_EXPR, boolean_type_node,
iv1->base, bound);
}
else
{
if (iv1->no_overflow)
return true;
if (TREE_CODE (iv1->base) == INTEGER_CST)
{
d = fold_build2 (MINUS_EXPR, niter_type,
fold_convert (niter_type, iv1->base),
fold_convert (niter_type, TYPE_MIN_VALUE (type)));
diff = fold_build2 (FLOOR_MOD_EXPR, niter_type, d, step);
}
else
diff = fold_build2 (MINUS_EXPR, niter_type, step,
build_int_cst (niter_type, 1));
bound = fold_build2 (PLUS_EXPR, type,
TYPE_MIN_VALUE (type), fold_convert (type, diff));
assumption = fold_build2 (GE_EXPR, boolean_type_node,
iv0->base, bound);
}
if (zero_p (assumption))
return false;
if (!nonzero_p (assumption))
niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
niter->assumptions, assumption);
iv0->no_overflow = true;
iv1->no_overflow = true;
return true;
}
static void
assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
struct tree_niter_desc *niter)
{
tree assumption = boolean_true_node, bound, diff;
tree mbz, mbzl, mbzr;
if (nonzero_p (iv0->step))
{
diff = fold_build2 (MINUS_EXPR, type,
iv0->step, build_int_cst (type, 1));
if (!POINTER_TYPE_P (type))
{
bound = fold_build2 (PLUS_EXPR, type,
TYPE_MIN_VALUE (type), diff);
assumption = fold_build2 (GE_EXPR, boolean_type_node,
iv0->base, bound);
}
mbzl = fold_build2 (MINUS_EXPR, type, iv0->base, diff);
mbzr = iv1->base;
}
else
{
diff = fold_build2 (PLUS_EXPR, type,
iv1->step, build_int_cst (type, 1));
if (!POINTER_TYPE_P (type))
{
bound = fold_build2 (PLUS_EXPR, type,
TYPE_MAX_VALUE (type), diff);
assumption = fold_build2 (LE_EXPR, boolean_type_node,
iv1->base, bound);
}
mbzl = iv0->base;
mbzr = fold_build2 (MINUS_EXPR, type, iv1->base, diff);
}
mbz = fold_build2 (GT_EXPR, boolean_type_node, mbzl, mbzr);
if (!nonzero_p (assumption))
niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
niter->assumptions, assumption);
if (!zero_p (mbz))
niter->may_be_zero = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
niter->may_be_zero, mbz);
}
static bool
number_of_iterations_lt (tree type, affine_iv *iv0, affine_iv *iv1,
struct tree_niter_desc *niter,
bool never_infinite ATTRIBUTE_UNUSED)
{
tree niter_type = unsigned_type_for (type);
tree delta, step, s;
if (nonzero_p (iv0->step))
{
niter->control = *iv0;
niter->cmp = LT_EXPR;
niter->bound = iv1->base;
}
else
{
niter->control = *iv1;
niter->cmp = GT_EXPR;
niter->bound = iv0->base;
}
delta = fold_build2 (MINUS_EXPR, niter_type,
fold_convert (niter_type, iv1->base),
fold_convert (niter_type, iv0->base));
if ((iv0->step && integer_onep (iv0->step)
&& zero_p (iv1->step))
|| (iv1->step && integer_all_onesp (iv1->step)
&& zero_p (iv0->step)))
{
niter->may_be_zero = fold_build2 (LT_EXPR, boolean_type_node,
iv1->base, iv0->base);
niter->niter = delta;
return true;
}
if (nonzero_p (iv0->step))
step = fold_convert (niter_type, iv0->step);
else
step = fold_convert (niter_type,
fold_build1 (NEGATE_EXPR, type, iv1->step));
if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step))
{
affine_iv zps;
zps.base = build_int_cst (niter_type, 0);
zps.step = step;
zps.no_overflow = true;
return number_of_iterations_ne (type, &zps, delta, niter, true);
}
if (!assert_no_overflow_lt (type, iv0, iv1, niter, step))
return false;
assert_loop_rolls_lt (type, iv0, iv1, niter);
s = fold_build2 (MINUS_EXPR, niter_type,
step, build_int_cst (niter_type, 1));
delta = fold_build2 (PLUS_EXPR, niter_type, delta, s);
niter->niter = fold_build2 (FLOOR_DIV_EXPR, niter_type, delta, step);
return true;
}
static bool
number_of_iterations_le (tree type, affine_iv *iv0, affine_iv *iv1,
struct tree_niter_desc *niter, bool never_infinite)
{
tree assumption;
if (!never_infinite)
{
if (nonzero_p (iv0->step))
assumption = fold_build2 (NE_EXPR, boolean_type_node,
iv1->base, TYPE_MAX_VALUE (type));
else
assumption = fold_build2 (NE_EXPR, boolean_type_node,
iv0->base, TYPE_MIN_VALUE (type));
if (zero_p (assumption))
return false;
if (!nonzero_p (assumption))
niter->assumptions = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
niter->assumptions, assumption);
}
if (nonzero_p (iv0->step))
iv1->base = fold_build2 (PLUS_EXPR, type,
iv1->base, build_int_cst (type, 1));
else
iv0->base = fold_build2 (MINUS_EXPR, type,
iv0->base, build_int_cst (type, 1));
return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite);
}
static bool
number_of_iterations_cond (tree type, affine_iv *iv0, enum tree_code code,
affine_iv *iv1, struct tree_niter_desc *niter,
bool only_exit)
{
bool never_infinite;
niter->assumptions = boolean_true_node;
niter->may_be_zero = boolean_false_node;
niter->niter = NULL_TREE;
niter->additional_info = boolean_true_node;
niter->bound = NULL_TREE;
niter->cmp = ERROR_MARK;
if (code == GE_EXPR || code == GT_EXPR
|| (code == NE_EXPR && zero_p (iv0->step)))
{
SWAP (iv0, iv1);
code = swap_tree_comparison (code);
}
if (!only_exit)
{
iv0->no_overflow = false;
iv1->no_overflow = false;
}
if (POINTER_TYPE_P (type))
{
iv0->no_overflow = true;
iv1->no_overflow = true;
}
if (!zero_p (iv0->step) && iv0->no_overflow)
never_infinite = true;
else if (!zero_p (iv1->step) && iv1->no_overflow)
never_infinite = true;
else
never_infinite = false;
if (!zero_p (iv0->step) && !zero_p (iv1->step))
{
if (code != NE_EXPR)
return false;
iv0->step = fold_binary_to_constant (MINUS_EXPR, type,
iv0->step, iv1->step);
iv0->no_overflow = false;
iv1->step = NULL_TREE;
iv1->no_overflow = true;
}
if (zero_p (iv0->step) && zero_p (iv1->step))
return false;
if (code != NE_EXPR)
{
if (iv0->step && tree_int_cst_sign_bit (iv0->step))
return false;
if (!zero_p (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
return false;
}
if (zero_p (fold_build2 (code, boolean_type_node, iv0->base, iv1->base)))
{
niter->niter = build_int_cst (unsigned_type_for (type), 0);
return true;
}
switch (code)
{
case NE_EXPR:
gcc_assert (zero_p (iv1->step));
return number_of_iterations_ne (type, iv0, iv1->base, niter, never_infinite);
case LT_EXPR:
return number_of_iterations_lt (type, iv0, iv1, niter, never_infinite);
case LE_EXPR:
return number_of_iterations_le (type, iv0, iv1, niter, never_infinite);
default:
gcc_unreachable ();
}
}
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);
}
tree
expand_simple_operations (tree expr)
{
unsigned i, n;
tree ret = NULL_TREE, e, ee, stmt;
enum tree_code code;
if (expr == NULL_TREE)
return expr;
if (is_gimple_min_invariant (expr))
return expr;
code = TREE_CODE (expr);
if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
{
n = TREE_CODE_LENGTH (code);
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;
}
if (!ret)
return expr;
fold_defer_overflow_warnings ();
ret = fold (ret);
fold_undefer_and_ignore_overflow_warnings ();
return ret;
}
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 (
TREE_CODE (e) != NOP_EXPR
&& TREE_CODE (e) != CONVERT_EXPR
&& TREE_CODE (e) != SSA_NAME
&& !is_gimple_min_invariant (e)
&& !((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);
}
static tree
tree_simplify_using_condition_1 (tree cond, tree expr)
{
bool changed;
tree e, te, 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_1 (cond, TREE_OPERAND (expr, 0));
if (TREE_OPERAND (expr, 0) != e0)
changed = true;
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_1 (cond, 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;
}
if (TREE_CODE (cond) == EQ_EXPR)
{
e0 = TREE_OPERAND (cond, 0);
e1 = TREE_OPERAND (cond, 1);
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);
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);
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);
notcond = invert_truthvalue (cond);
e = fold_binary (TRUTH_OR_EXPR, boolean_type_node, notcond, te);
if (nonzero_p (e))
return e;
e = fold_binary (TRUTH_AND_EXPR, boolean_type_node, cond, te);
if (e && zero_p (e))
return e;
return expr;
}
static tree
tree_simplify_using_condition (tree cond, tree expr)
{
cond = expand_simple_operations (cond);
return tree_simplify_using_condition_1 (cond, expr);
}
#define MAX_DOMINATORS_TO_WALK 8
static tree
simplify_using_initial_conditions (struct loop *loop, tree expr,
tree *conds_used)
{
edge e;
basic_block bb;
tree exp, cond;
int cnt = 0;
if (TREE_CODE (expr) == INTEGER_CST)
return expr;
for (bb = loop->header;
bb != ENTRY_BLOCK_PTR && cnt < MAX_DOMINATORS_TO_WALK;
bb = get_immediate_dominator (CDI_DOMINATORS, bb))
{
if (!single_pred_p (bb))
continue;
e = single_pred_edge (bb);
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;
++cnt;
}
return expr;
}
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;
}
static bool
loop_only_exit_p (struct loop *loop, edge exit)
{
basic_block *body;
block_stmt_iterator bsi;
unsigned i;
tree call;
if (exit != loop->single_exit)
return false;
body = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
{
for (bsi = bsi_start (body[0]); !bsi_end_p (bsi); bsi_next (&bsi))
{
call = get_call_expr_in (bsi_stmt (bsi));
if (call && TREE_SIDE_EFFECTS (call))
{
free (body);
return false;
}
}
}
free (body);
return true;
}
bool
number_of_iterations_exit (struct loop *loop, edge exit,
struct tree_niter_desc *niter,
bool warn)
{
tree stmt, cond, type;
tree op0, op1;
enum tree_code code;
affine_iv iv0, iv1;
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, &iv0, false))
return false;
if (!simple_iv (loop, stmt, op1, &iv1, false))
return false;
fold_defer_overflow_warnings ();
iv0.base = expand_simple_operations (iv0.base);
iv1.base = expand_simple_operations (iv1.base);
if (!number_of_iterations_cond (type, &iv0, code, &iv1, niter,
loop_only_exit_p (loop, exit)))
{
fold_undefer_and_ignore_overflow_warnings ();
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
= 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);
fold_undefer_and_ignore_overflow_warnings ();
if (integer_onep (niter->assumptions))
return true;
if (integer_zerop (niter->assumptions))
return false;
if (flag_unsafe_loop_optimizations)
niter->assumptions = boolean_true_node;
if (warn)
{
const char *wording;
location_t loc = EXPR_LOCATION (stmt);
if (!zero_p (iv1.step)
? (zero_p (iv0.step)
&& (integer_onep (iv1.step) || integer_all_onesp (iv1.step)))
: (iv0.step
&& (integer_onep (iv0.step) || integer_all_onesp (iv0.step))))
wording =
flag_unsafe_loop_optimizations
? N_("assuming that the loop is not infinite")
: N_("cannot optimize possibly infinite loops");
else
wording =
flag_unsafe_loop_optimizations
? N_("assuming that the loop counter does not overflow")
: N_("cannot optimize loop, the loop counter may overflow");
if (LOCATION_LINE (loc) > 0)
warning (OPT_Wunsafe_loop_optimizations, "%H%s", &loc, gettext (wording));
else
warning (OPT_Wunsafe_loop_optimizations, "%s", gettext (wording));
}
return flag_unsafe_loop_optimizations;
}
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, false))
continue;
if (nonzero_p (desc.may_be_zero))
{
niter = build_int_cst (unsigned_type_node, 0);
*exit = ex;
break;
}
if (!zero_p (desc.may_be_zero))
continue;
aniter = desc.niter;
if (!niter)
{
niter = aniter;
*exit = ex;
continue;
}
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;
}
#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);
tree use;
basic_block bb = bb_for_stmt (stmt);
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;
if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
return NULL_TREE;
if (SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF) == NULL_DEF_OPERAND_P)
return NULL_TREE;
use = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_USE);
if (use == NULL_USE_OPERAND_P)
return NULL_TREE;
return chain_of_csts_start (loop, use);
}
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_operand_p op;
ssa_op_iter iter;
gcc_assert (is_gimple_min_invariant (base));
if (!x)
return base;
stmt = SSA_NAME_DEF_STMT (x);
if (TREE_CODE (stmt) == PHI_NODE)
return base;
FOR_EACH_SSA_USE_OPERAND (op, stmt, iter, SSA_OP_USE)
{
nx = USE_FROM_PTR (op);
val = get_val_for (nx, base);
SET_USE (op, val);
val = fold (TREE_OPERAND (stmt, 1));
SET_USE (op, nx);
return val;
}
gcc_unreachable();
}
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;
}
}
fold_defer_overflow_warnings ();
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_binary (cmp, boolean_type_node, aval[0], aval[1]);
if (acnd && zero_p (acnd))
{
fold_undefer_and_ignore_overflow_warnings ();
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]);
if (!is_gimple_min_invariant (val[j]))
{
fold_undefer_and_ignore_overflow_warnings ();
return chrec_dont_know;
}
}
}
fold_undefer_and_ignore_overflow_warnings ();
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))
continue;
if (niter
&& !tree_int_cst_lt (aniter, niter))
continue;
niter = aniter;
*exit = ex;
}
free (exits);
return niter ? niter : chrec_dont_know;
}
static bool
implies_nonnegative_p (tree cond, tree val)
{
tree type = TREE_TYPE (val);
tree compare;
if (tree_expr_nonnegative_p (val))
return true;
if (nonzero_p (cond))
return false;
compare = fold_build2 (GE_EXPR,
boolean_type_node, val, build_int_cst (type, 0));
compare = tree_simplify_using_condition_1 (cond, compare);
return nonzero_p (compare);
}
static bool
implies_ge_p (tree cond, tree a, tree b)
{
tree compare = fold_build2 (GE_EXPR, boolean_type_node, a, b);
if (nonzero_p (compare))
return true;
if (nonzero_p (cond))
return false;
compare = tree_simplify_using_condition_1 (cond, compare);
return nonzero_p (compare);
}
static double_int
derive_constant_upper_bound (tree val, tree additional)
{
tree type = TREE_TYPE (val);
tree op0, op1, subtype, maxt;
double_int bnd, max, mmax, cst;
if (INTEGRAL_TYPE_P (type))
maxt = TYPE_MAX_VALUE (type);
else
maxt = upper_bound_in_type (type, type);
max = tree_to_double_int (maxt);
switch (TREE_CODE (val))
{
case INTEGER_CST:
return tree_to_double_int (val);
case NOP_EXPR:
case CONVERT_EXPR:
op0 = TREE_OPERAND (val, 0);
subtype = TREE_TYPE (op0);
if (!TYPE_UNSIGNED (subtype)
&& TYPE_UNSIGNED (type)
&& !implies_nonnegative_p (additional, op0))
{
return max;
}
bnd = derive_constant_upper_bound (op0, additional);
if (double_int_ucmp (max, bnd) < 0)
return max;
return bnd;
case PLUS_EXPR:
case MINUS_EXPR:
op0 = TREE_OPERAND (val, 0);
op1 = TREE_OPERAND (val, 1);
if (TREE_CODE (op1) != INTEGER_CST
|| !implies_nonnegative_p (additional, op0))
return max;
cst = tree_to_double_int (op1);
cst = double_int_sext (cst, TYPE_PRECISION (type));
if (TREE_CODE (val) == PLUS_EXPR)
cst = double_int_neg (cst);
bnd = derive_constant_upper_bound (op0, additional);
if (double_int_negative_p (cst))
{
cst = double_int_neg (cst);
if (double_int_negative_p (cst))
return max;;
mmax = double_int_add (max, double_int_neg (cst));
if (double_int_ucmp (bnd, mmax) > 0)
return max;
return double_int_add (bnd, cst);
}
else
{
if (double_int_ucmp (bnd, cst) < 0)
return max;
if (TYPE_UNSIGNED (type)
&& !implies_ge_p (additional,
op0, double_int_to_tree (type, cst)))
return max;
bnd = double_int_add (bnd, double_int_neg (cst));
}
return bnd;
case FLOOR_DIV_EXPR:
case EXACT_DIV_EXPR:
op0 = TREE_OPERAND (val, 0);
op1 = TREE_OPERAND (val, 1);
if (TREE_CODE (op1) != INTEGER_CST
|| tree_int_cst_sign_bit (op1))
return max;
bnd = derive_constant_upper_bound (op0, additional);
return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR);
default:
return max;
}
}
void
record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt)
{
struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound));
double_int i_bound = derive_constant_upper_bound (bound, additional);
tree c_bound = double_int_to_tree (unsigned_type_for (TREE_TYPE (bound)),
i_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, " (bounded by ");
print_generic_expr (dump_file, c_bound, TDF_SLIM);
fprintf (dump_file, ") times in loop %d.\n", loop->num);
}
elt->bound = c_bound;
elt->at_stmt = at_stmt;
elt->next = loop->bounds;
loop->bounds = elt;
}
static void
compute_estimated_nb_iterations (struct loop *loop)
{
struct nb_iter_bound *bound;
for (bound = loop->bounds; bound; bound = bound->next)
{
if (TREE_CODE (bound->bound) != INTEGER_CST)
continue;
if (chrec_contains_undetermined (loop->estimated_nb_iterations)
|| tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations))
loop->estimated_nb_iterations = bound->bound;
}
}
static void
infer_loop_bounds_from_undefined (struct loop *loop)
{
unsigned i;
basic_block bb, *bbs;
block_stmt_iterator bsi;
bbs = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
{
bb = bbs[i];
if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
continue;
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
switch (TREE_CODE (stmt))
{
case MODIFY_EXPR:
{
tree op0 = TREE_OPERAND (stmt, 0);
tree op1 = TREE_OPERAND (stmt, 1);
if (TREE_CODE (op1) == ARRAY_REF
&& !array_ref_contains_indirect_ref (op1))
estimate_iters_using_array (stmt, op1);
if (TREE_CODE (op0) == ARRAY_REF
&& !array_ref_contains_indirect_ref (op0))
estimate_iters_using_array (stmt, op0);
else if (!flag_wrapv && TREE_CODE (op0) == SSA_NAME)
{
tree init, step, diff, estimation;
tree scev = instantiate_parameters
(loop, analyze_scalar_evolution (loop, op0));
tree type = chrec_type (scev);
if (chrec_contains_undetermined (scev)
|| TYPE_OVERFLOW_WRAPS (type))
break;
init = initial_condition_in_loop_num (scev, loop->num);
step = evolution_part_in_loop_num (scev, loop->num);
if (init == NULL_TREE
|| step == NULL_TREE
|| TREE_CODE (init) != INTEGER_CST
|| TREE_CODE (step) != INTEGER_CST
|| TYPE_MIN_VALUE (type) == NULL_TREE
|| TYPE_MAX_VALUE (type) == NULL_TREE)
break;
if (integer_nonzerop (step))
{
tree utype;
if (tree_int_cst_lt (step, integer_zero_node))
diff = fold_build2 (MINUS_EXPR, type, init,
TYPE_MIN_VALUE (type));
else
diff = fold_build2 (MINUS_EXPR, type,
TYPE_MAX_VALUE (type), init);
utype = unsigned_type_for (type);
estimation = fold_build2 (CEIL_DIV_EXPR, type, diff,
step);
record_estimate (loop,
fold_convert (utype, estimation),
boolean_true_node, stmt);
}
}
break;
}
case CALL_EXPR:
{
tree args;
for (args = TREE_OPERAND (stmt, 1); args;
args = TREE_CHAIN (args))
if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF
&& !array_ref_contains_indirect_ref (TREE_VALUE (args)))
estimate_iters_using_array (stmt, TREE_VALUE (args));
break;
}
default:
break;
}
}
}
compute_estimated_nb_iterations (loop);
free (bbs);
}
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;
if (loop->estimated_nb_iterations == chrec_dont_know
|| (loop->estimated_nb_iterations != NULL_TREE
&& TREE_CODE (loop->estimated_nb_iterations) == INTEGER_CST))
return;
else
loop->estimated_nb_iterations = chrec_dont_know;
exits = get_loop_exit_edges (loop, &n_exits);
for (i = 0; i < n_exits; i++)
{
if (!number_of_iterations_exit (loop, exits[i], &niter_desc, false))
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, 0),
niter);
record_estimate (loop, niter,
niter_desc.additional_info,
last_stmt (exits[i]->src));
}
free (exits);
if (chrec_contains_undetermined (loop->estimated_nb_iterations))
infer_loop_bounds_from_undefined (loop);
}
void
estimate_numbers_of_iterations (struct loops *loops)
{
unsigned i;
struct loop *loop;
fold_defer_overflow_warnings ();
for (i = 1; i < loops->num; i++)
{
loop = loops->parray[i];
if (loop)
estimate_numbers_of_iterations_loop (loop);
}
fold_undefer_and_ignore_overflow_warnings ();
}
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 bool
n_of_executions_at_most (tree stmt,
struct nb_iter_bound *niter_bound,
tree niter)
{
tree cond;
tree bound = niter_bound->bound;
tree bound_type = TREE_TYPE (bound);
tree nit_type = TREE_TYPE (niter);
enum tree_code cmp;
gcc_assert (TYPE_UNSIGNED (bound_type)
&& TYPE_UNSIGNED (nit_type)
&& is_gimple_min_invariant (bound));
if (TYPE_PRECISION (nit_type) > TYPE_PRECISION (bound_type))
bound = fold_convert (nit_type, bound);
else
niter = fold_convert (bound_type, niter);
if (stmt && stmt_dominates_stmt_p (niter_bound->at_stmt, stmt))
cmp = GE_EXPR;
else
cmp = GT_EXPR;
cond = fold_binary (cmp, boolean_type_node, niter, bound);
return nonzero_p (cond);
}
bool
nowrap_type_p (tree type)
{
if (INTEGRAL_TYPE_P (type)
&& TYPE_OVERFLOW_UNDEFINED (type))
return true;
if (POINTER_TYPE_P (type))
return true;
return false;
}
bool
scev_probably_wraps_p (tree base, tree step,
tree at_stmt, struct loop *loop,
bool use_overflow_semantics)
{
struct nb_iter_bound *bound;
tree delta, step_abs;
tree unsigned_type, valid_niter;
tree type = TREE_TYPE (step);
if (chrec_contains_undetermined (base)
|| chrec_contains_undetermined (step)
|| TREE_CODE (step) != INTEGER_CST)
return true;
if (zero_p (step))
return false;
if (use_overflow_semantics && nowrap_type_p (type))
return false;
fold_defer_overflow_warnings ();
unsigned_type = unsigned_type_for (type);
base = fold_convert (unsigned_type, base);
if (tree_int_cst_sign_bit (step))
{
tree extreme = fold_convert (unsigned_type,
lower_bound_in_type (type, type));
delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
step_abs = fold_build1 (NEGATE_EXPR, unsigned_type,
fold_convert (unsigned_type, step));
}
else
{
tree extreme = fold_convert (unsigned_type,
upper_bound_in_type (type, type));
delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
step_abs = fold_convert (unsigned_type, step);
}
valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
estimate_numbers_of_iterations_loop (loop);
for (bound = loop->bounds; bound; bound = bound->next)
{
if (n_of_executions_at_most (at_stmt, bound, valid_niter))
{
fold_undefer_and_ignore_overflow_warnings ();
return false;
}
}
fold_undefer_and_ignore_overflow_warnings ();
return true;
}
void
free_numbers_of_iterations_estimates_loop (struct loop *loop)
{
struct nb_iter_bound *bound, *next;
loop->nb_iterations = NULL;
loop->estimated_nb_iterations = NULL;
for (bound = loop->bounds; bound; bound = next)
{
next = bound->next;
free (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);
}
}
void
substitute_in_loop_info (struct loop *loop, tree name, tree val)
{
loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);
loop->estimated_nb_iterations
= simplify_replace_tree (loop->estimated_nb_iterations, name, val);
}