/* Functions to determine/estimate number of iterations of a loop.
- Copyright (C) 2004-2018 Free Software Foundation, Inc.
+ Copyright (C) 2004-2021 Free Software Foundation, Inc.
This file is part of GCC.
#include "cfgloop.h"
#include "tree-chrec.h"
#include "tree-scalar-evolution.h"
-#include "params.h"
#include "tree-dfa.h"
+#include "gimple-range.h"
/* The maximum number of dominator BBs we search for conditions
static bool number_of_iterations_popcount (loop_p loop, edge exit,
enum tree_code code,
- struct tree_niter_desc *niter);
+ class tree_niter_desc *niter);
/* Splits expression EXPR to a variable part VAR and constant OFFSET. */
tree varc0, varc1, ctype;
mpz_t offc0, offc1;
mpz_t mint, maxt, minc1, maxc1;
- wide_int minv, maxv;
bool no_wrap = nowrap_type_p (type);
bool c0_ok, c1_ok;
signop sgn = TYPE_SIGN (type);
get_type_static_bounds (type, mint, maxt);
mpz_init (minc1);
mpz_init (maxc1);
+ value_range r;
/* Setup range information for varc1. */
if (integer_zerop (varc1))
{
}
else if (TREE_CODE (varc1) == SSA_NAME
&& INTEGRAL_TYPE_P (type)
- && get_range_info (varc1, &minv, &maxv) == VR_RANGE)
+ && get_range_query (cfun)->range_of_expr (r, varc1)
+ && r.kind () == VR_RANGE)
{
- gcc_assert (wi::le_p (minv, maxv, sgn));
- wi::to_mpz (minv, minc1, sgn);
- wi::to_mpz (maxv, maxc1, sgn);
+ gcc_assert (wi::le_p (r.lower_bound (), r.upper_bound (), sgn));
+ wi::to_mpz (r.lower_bound (), minc1, sgn);
+ wi::to_mpz (r.upper_bound (), maxc1, sgn);
}
else
{
in TYPE to MIN and MAX. */
static void
-determine_value_range (struct loop *loop, tree type, tree var, mpz_t off,
+determine_value_range (class loop *loop, tree type, tree var, mpz_t off,
mpz_t min, mpz_t max)
{
int cnt = 0;
mpz_t minm, maxm;
basic_block bb;
wide_int minv, maxv;
- enum value_range_type rtype = VR_VARYING;
+ enum value_range_kind rtype = VR_VARYING;
/* If the expression is a constant, we know its value exactly. */
if (integer_zerop (var))
gphi_iterator gsi;
/* Either for VAR itself... */
- rtype = get_range_info (var, &minv, &maxv);
+ value_range var_range;
+ get_range_query (cfun)->range_of_expr (var_range, var);
+ rtype = var_range.kind ();
+ if (!var_range.undefined_p ())
+ {
+ minv = var_range.lower_bound ();
+ maxv = var_range.upper_bound ();
+ }
+
/* Or for PHI results in loop->header where VAR is used as
PHI argument from the loop preheader edge. */
for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
{
gphi *phi = gsi.phi ();
- wide_int minc, maxc;
+ value_range phi_range;
if (PHI_ARG_DEF_FROM_EDGE (phi, e) == var
- && (get_range_info (gimple_phi_result (phi), &minc, &maxc)
- == VR_RANGE))
+ && get_range_query (cfun)->range_of_expr (phi_range,
+ gimple_phi_result (phi))
+ && phi_range.kind () == VR_RANGE)
{
if (rtype != VR_RANGE)
{
rtype = VR_RANGE;
- minv = minc;
- maxv = maxc;
+ minv = phi_range.lower_bound ();
+ maxv = phi_range.upper_bound ();
}
else
{
- minv = wi::max (minv, minc, sgn);
- maxv = wi::min (maxv, maxc, sgn);
+ minv = wi::max (minv, phi_range.lower_bound (), sgn);
+ maxv = wi::min (maxv, phi_range.upper_bound (), sgn);
/* If the PHI result range are inconsistent with
the VAR range, give up on looking at the PHI
results. This can happen if VR_UNDEFINED is
involved. */
if (wi::gt_p (minv, maxv, sgn))
{
- rtype = get_range_info (var, &minv, &maxv);
+ value_range vr;
+ get_range_query (cfun)->range_of_expr (vr, var);
+ rtype = vr.kind ();
+ if (!vr.undefined_p ())
+ {
+ minv = vr.lower_bound ();
+ maxv = vr.upper_bound ();
+ }
break;
}
}
comparisons before the loop (usually created by loop header copying). */
static void
-bound_difference (struct loop *loop, tree x, tree y, bounds *bnds)
+bound_difference (class loop *loop, tree x, tree y, bounds *bnds)
{
tree type = TREE_TYPE (x);
tree varx, vary;
bounds on the difference FINAL - IV->base. */
static bool
-number_of_iterations_ne (struct loop *loop, tree type, affine_iv *iv,
- tree final, struct tree_niter_desc *niter,
+number_of_iterations_ne (class loop *loop, tree type, affine_iv *iv,
+ tree final, class tree_niter_desc *niter,
bool exit_must_be_taken, bounds *bnds)
{
tree niter_type = unsigned_type_for (type);
}
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);
+ if (integer_onep (s))
+ {
+ niter->niter = c;
+ }
+ else
+ {
+ 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,
+ class tree_niter_desc *niter,
tree *delta, tree step,
bool exit_must_be_taken, bounds *bnds)
{
static bool
assert_no_overflow_lt (tree type, affine_iv *iv0, affine_iv *iv1,
- struct tree_niter_desc *niter, tree step)
+ class tree_niter_desc *niter, tree step)
{
tree bound, d, assumption, diff;
tree niter_type = TREE_TYPE (step);
static void
assert_loop_rolls_lt (tree type, affine_iv *iv0, affine_iv *iv1,
- struct tree_niter_desc *niter, bounds *bnds)
+ class tree_niter_desc *niter, bounds *bnds)
{
tree assumption = boolean_true_node, bound, diff;
tree mbz, mbzl, mbzr, type1;
that the exit must be taken eventually. */
static bool
-number_of_iterations_lt (struct loop *loop, tree type, affine_iv *iv0,
- affine_iv *iv1, struct tree_niter_desc *niter,
+number_of_iterations_lt (class loop *loop, tree type, affine_iv *iv0,
+ affine_iv *iv1, class tree_niter_desc *niter,
bool exit_must_be_taken, bounds *bnds)
{
tree niter_type = unsigned_type_for (type);
is the case). BNDS bounds the difference IV1->base - IV0->base. */
static bool
-number_of_iterations_le (struct loop *loop, tree type, affine_iv *iv0,
- affine_iv *iv1, struct tree_niter_desc *niter,
+number_of_iterations_le (class loop *loop, tree type, affine_iv *iv0,
+ affine_iv *iv1, class tree_niter_desc *niter,
bool exit_must_be_taken, bounds *bnds)
{
tree assumption;
}
}
+/* Given exit condition IV0 CODE IV1 in TYPE, this function adjusts
+ the condition for loop-until-wrap cases. For example:
+ (unsigned){8, -1}_loop < 10 => {0, 1} != 9
+ 10 < (unsigned){0, max - 7}_loop => {0, 1} != 8
+ Return true if condition is successfully adjusted. */
+
+static bool
+adjust_cond_for_loop_until_wrap (tree type, affine_iv *iv0, tree_code *code,
+ affine_iv *iv1)
+{
+ /* Only support simple cases for the moment. */
+ if (TREE_CODE (iv0->base) != INTEGER_CST
+ || TREE_CODE (iv1->base) != INTEGER_CST)
+ return false;
+
+ tree niter_type = unsigned_type_for (type), high, low;
+ /* Case: i-- < 10. */
+ if (integer_zerop (iv1->step))
+ {
+ /* TODO: Should handle case in which abs(step) != 1. */
+ if (!integer_minus_onep (iv0->step))
+ return false;
+ /* Give up on infinite loop. */
+ if (*code == LE_EXPR
+ && tree_int_cst_equal (iv1->base, TYPE_MAX_VALUE (type)))
+ return false;
+ high = fold_build2 (PLUS_EXPR, niter_type,
+ fold_convert (niter_type, iv0->base),
+ build_int_cst (niter_type, 1));
+ low = fold_convert (niter_type, TYPE_MIN_VALUE (type));
+ }
+ else if (integer_zerop (iv0->step))
+ {
+ /* TODO: Should handle case in which abs(step) != 1. */
+ if (!integer_onep (iv1->step))
+ return false;
+ /* Give up on infinite loop. */
+ if (*code == LE_EXPR
+ && tree_int_cst_equal (iv0->base, TYPE_MIN_VALUE (type)))
+ return false;
+ high = fold_convert (niter_type, TYPE_MAX_VALUE (type));
+ low = fold_build2 (MINUS_EXPR, niter_type,
+ fold_convert (niter_type, iv1->base),
+ build_int_cst (niter_type, 1));
+ }
+ else
+ gcc_unreachable ();
+
+ iv0->base = low;
+ iv0->step = fold_convert (niter_type, integer_one_node);
+ iv1->base = high;
+ iv1->step = build_int_cst (niter_type, 0);
+ *code = NE_EXPR;
+ return true;
+}
+
/* Determine the number of iterations according to condition (for staying
inside loop) which compares two induction variables using comparison
operator CODE. The induction variable on left side of the comparison
if EVERY_ITERATION is true, we know the test is executed on every iteration.
The results (number of iterations and assumptions as described in
- comments at struct tree_niter_desc in tree-ssa-loop.h) are stored to NITER.
+ comments at class tree_niter_desc in tree-ssa-loop.h) are stored to NITER.
Returns false if it fails to determine number of iterations, true if it
was determined (possibly with some assumptions). */
static bool
-number_of_iterations_cond (struct loop *loop,
+number_of_iterations_cond (class loop *loop,
tree type, affine_iv *iv0, enum tree_code code,
- affine_iv *iv1, struct tree_niter_desc *niter,
+ affine_iv *iv1, class tree_niter_desc *niter,
bool only_exit, bool every_iteration)
{
bool exit_must_be_taken = false, ret;
if (integer_zerop (iv0->step) && integer_zerop (iv1->step))
return false;
- /* Ignore loops of while (i-- < 10) type. */
- if (code != NE_EXPR)
- {
- if (iv0->step && tree_int_cst_sign_bit (iv0->step))
- return false;
-
- if (!integer_zerop (iv1->step) && !tree_int_cst_sign_bit (iv1->step))
- return false;
- }
-
/* If the loop exits immediately, there is nothing to do. */
tree tem = fold_binary (code, boolean_type_node, iv0->base, iv1->base);
if (tem && integer_zerop (tem))
{
+ if (!every_iteration)
+ return false;
niter->niter = build_int_cst (unsigned_type_for (type), 0);
niter->max = 0;
return true;
}
+ /* Handle special case loops: while (i-- < 10) and while (10 < i++) by
+ adjusting iv0, iv1 and code. */
+ if (code != NE_EXPR
+ && (tree_int_cst_sign_bit (iv0->step)
+ || (!integer_zerop (iv1->step)
+ && !tree_int_cst_sign_bit (iv1->step)))
+ && !adjust_cond_for_loop_until_wrap (type, iv0, &code, iv1))
+ return false;
+
/* OK, now we know we have a senseful loop. Handle several cases, depending
on what comparison operator is used. */
bound_difference (loop, iv1->base, iv0->base, &bnds);
return ret;
}
-/* Substitute NEW for OLD in EXPR and fold the result. */
+/* Substitute NEW_TREE for OLD in EXPR and fold the result.
+ If VALUEIZE is non-NULL then OLD and NEW_TREE are ignored and instead
+ all SSA names are replaced with the result of calling the VALUEIZE
+ function with the SSA name as argument. */
-static tree
-simplify_replace_tree (tree expr, tree old, tree new_tree)
+tree
+simplify_replace_tree (tree expr, tree old, tree new_tree,
+ tree (*valueize) (tree, void*), void *context,
+ bool do_fold)
{
unsigned i, n;
tree ret = NULL_TREE, e, se;
return NULL_TREE;
/* Do not bother to replace constants. */
- if (CONSTANT_CLASS_P (old))
+ if (CONSTANT_CLASS_P (expr))
return expr;
- if (expr == old
- || operand_equal_p (expr, old, 0))
+ if (valueize)
+ {
+ if (TREE_CODE (expr) == SSA_NAME)
+ {
+ new_tree = valueize (expr, context);
+ if (new_tree != expr)
+ return new_tree;
+ }
+ }
+ else if (expr == old
+ || operand_equal_p (expr, old, 0))
return unshare_expr (new_tree);
if (!EXPR_P (expr))
for (i = 0; i < n; i++)
{
e = TREE_OPERAND (expr, i);
- se = simplify_replace_tree (e, old, new_tree);
+ se = simplify_replace_tree (e, old, new_tree, valueize, context, do_fold);
if (e == se)
continue;
TREE_OPERAND (ret, i) = se;
}
- return (ret ? fold (ret) : expr);
+ return (ret ? (do_fold ? fold (ret) : ret) : expr);
}
/* Expand definitions of ssa names in EXPR as long as they are simple
enough, and return the new expression. If STOP is specified, stop
expanding if EXPR equals to it. */
-tree
-expand_simple_operations (tree expr, tree stop)
+static tree
+expand_simple_operations (tree expr, tree stop, hash_map<tree, tree> &cache)
{
unsigned i, n;
tree ret = NULL_TREE, e, ee, e1;
for (i = 0; i < n; i++)
{
e = TREE_OPERAND (expr, i);
- ee = expand_simple_operations (e, stop);
+ /* SCEV analysis feeds us with a proper expression
+ graph matching the SSA graph. Avoid turning it
+ into a tree here, thus handle tree sharing
+ properly.
+ ??? The SSA walk below still turns the SSA graph
+ into a tree but until we find a testcase do not
+ introduce additional tree sharing here. */
+ bool existed_p;
+ tree &cee = cache.get_or_insert (e, &existed_p);
+ if (existed_p)
+ ee = cee;
+ else
+ {
+ cee = e;
+ ee = expand_simple_operations (e, stop, cache);
+ if (ee != e)
+ *cache.get (e) = ee;
+ }
if (e == ee)
continue;
&& src->loop_father != dest->loop_father)
return expr;
- return expand_simple_operations (e, stop);
+ return expand_simple_operations (e, stop, cache);
}
if (gimple_code (stmt) != GIMPLE_ASSIGN)
return expr;
return e;
if (code == SSA_NAME)
- return expand_simple_operations (e, stop);
+ return expand_simple_operations (e, stop, cache);
else if (code == ADDR_EXPR)
{
poly_int64 offset;
if (base
&& TREE_CODE (base) == MEM_REF)
{
- ee = expand_simple_operations (TREE_OPERAND (base, 0), stop);
+ ee = expand_simple_operations (TREE_OPERAND (base, 0), stop,
+ cache);
return fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (expr), ee,
wide_int_to_tree (sizetype,
mem_ref_offset (base)
{
CASE_CONVERT:
/* Casts are simple. */
- ee = expand_simple_operations (e, stop);
+ ee = expand_simple_operations (e, stop, cache);
return fold_build1 (code, TREE_TYPE (expr), ee);
case PLUS_EXPR:
if (!is_gimple_min_invariant (e1))
return expr;
- ee = expand_simple_operations (e, stop);
+ ee = expand_simple_operations (e, stop, cache);
return fold_build2 (code, TREE_TYPE (expr), ee, e1);
default:
}
}
+tree
+expand_simple_operations (tree expr, tree stop)
+{
+ hash_map<tree, tree> cache;
+ return expand_simple_operations (expr, stop, cache);
+}
+
/* Tries to simplify EXPR using the condition COND. Returns the simplified
expression (or EXPR unchanged, if no simplification was possible). */
simplification was possible). */
tree
-simplify_using_initial_conditions (struct loop *loop, tree expr)
+simplify_using_initial_conditions (class loop *loop, tree expr)
{
edge e;
basic_block bb;
(or EXPR unchanged, if no simplification was possible). */
static tree
-simplify_using_outer_evolutions (struct loop *loop, tree expr)
+simplify_using_outer_evolutions (class loop *loop, tree expr)
{
enum tree_code code = TREE_CODE (expr);
bool changed;
/* Returns true if EXIT is the only possible exit from LOOP. */
bool
-loop_only_exit_p (const struct loop *loop, const_edge exit)
+loop_only_exit_p (const class loop *loop, basic_block *body, const_edge exit)
{
- basic_block *body;
gimple_stmt_iterator bsi;
unsigned i;
if (exit != single_exit (loop))
return false;
- body = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
- {
- for (bsi = gsi_start_bb (body[i]); !gsi_end_p (bsi); gsi_next (&bsi))
- if (stmt_can_terminate_bb_p (gsi_stmt (bsi)))
- {
- free (body);
- return true;
- }
- }
+ for (bsi = gsi_start_bb (body[i]); !gsi_end_p (bsi); gsi_next (&bsi))
+ if (stmt_can_terminate_bb_p (gsi_stmt (bsi)))
+ return false;
- free (body);
return true;
}
/* Stores description of number of iterations of LOOP derived from
EXIT (an exit edge of the LOOP) in NITER. Returns true if some useful
information could be derived (and fields of NITER have meaning described
- in comments at struct tree_niter_desc declaration), false otherwise.
+ in comments at class tree_niter_desc declaration), false otherwise.
When EVERY_ITERATION is true, only tests that are known to be executed
every iteration are considered (i.e. only test that alone bounds the loop).
If AT_STMT is not NULL, this function stores LOOP's condition statement in
it when returning true. */
bool
-number_of_iterations_exit_assumptions (struct loop *loop, edge exit,
- struct tree_niter_desc *niter,
- gcond **at_stmt, bool every_iteration)
+number_of_iterations_exit_assumptions (class loop *loop, edge exit,
+ class tree_niter_desc *niter,
+ gcond **at_stmt, bool every_iteration,
+ basic_block *body)
{
gimple *last;
gcond *stmt;
affine_iv iv0, iv1;
bool safe;
+ /* The condition at a fake exit (if it exists) does not control its
+ execution. */
+ if (exit->flags & EDGE_FAKE)
+ return false;
+
/* Nothing to analyze if the loop is known to be infinite. */
if (loop_constraint_set_p (loop, LOOP_C_INFINITE))
return false;
iv0.base = expand_simple_operations (iv0.base);
iv1.base = expand_simple_operations (iv1.base);
+ bool body_from_caller = true;
+ if (!body)
+ {
+ body = get_loop_body (loop);
+ body_from_caller = false;
+ }
+ bool only_exit_p = loop_only_exit_p (loop, body, exit);
+ if (!body_from_caller)
+ free (body);
if (!number_of_iterations_cond (loop, type, &iv0, code, &iv1, niter,
- loop_only_exit_p (loop, exit), safe))
+ only_exit_p, safe))
{
fold_undefer_and_ignore_overflow_warnings ();
return false;
static bool
number_of_iterations_popcount (loop_p loop, edge exit,
enum tree_code code,
- struct tree_niter_desc *niter)
+ class tree_niter_desc *niter)
{
bool adjust = true;
tree iter;
... = PHI <b_5(2), b_6(3)>. */
gimple *phi = SSA_NAME_DEF_STMT (b_11);
if (gimple_code (phi) != GIMPLE_PHI
+ || (gimple_bb (phi) != loop_latch_edge (loop)->dest)
|| (gimple_assign_lhs (and_stmt)
!= gimple_phi_arg_def (phi, loop_latch_edge (loop)->dest_idx)))
return false;
/* We found a match. Get the corresponding popcount builtin. */
tree src = gimple_phi_arg_def (phi, loop_preheader_edge (loop)->dest_idx);
- if (TYPE_PRECISION (TREE_TYPE (src)) == TYPE_PRECISION (integer_type_node))
+ if (TYPE_PRECISION (TREE_TYPE (src)) <= TYPE_PRECISION (integer_type_node))
fn = builtin_decl_implicit (BUILT_IN_POPCOUNT);
- else if (TYPE_PRECISION (TREE_TYPE (src)) == TYPE_PRECISION
- (long_integer_type_node))
+ else if (TYPE_PRECISION (TREE_TYPE (src))
+ == TYPE_PRECISION (long_integer_type_node))
fn = builtin_decl_implicit (BUILT_IN_POPCOUNTL);
- else if (TYPE_PRECISION (TREE_TYPE (src)) == TYPE_PRECISION
- (long_long_integer_type_node))
+ else if (TYPE_PRECISION (TREE_TYPE (src))
+ == TYPE_PRECISION (long_long_integer_type_node)
+ || (TYPE_PRECISION (TREE_TYPE (src))
+ == 2 * TYPE_PRECISION (long_long_integer_type_node)))
fn = builtin_decl_implicit (BUILT_IN_POPCOUNTLL);
- /* ??? Support promoting char/short to int. */
if (!fn)
return false;
/* Update NITER params accordingly */
tree utype = unsigned_type_for (TREE_TYPE (src));
src = fold_convert (utype, src);
- tree call = fold_convert (utype, build_call_expr (fn, 1, src));
+ if (TYPE_PRECISION (TREE_TYPE (src)) < TYPE_PRECISION (integer_type_node))
+ src = fold_convert (unsigned_type_node, src);
+ tree call;
+ if (TYPE_PRECISION (TREE_TYPE (src))
+ == 2 * TYPE_PRECISION (long_long_integer_type_node))
+ {
+ int prec = TYPE_PRECISION (long_long_integer_type_node);
+ tree src1 = fold_convert (long_long_unsigned_type_node,
+ fold_build2 (RSHIFT_EXPR, TREE_TYPE (src),
+ unshare_expr (src),
+ build_int_cst (integer_type_node,
+ prec)));
+ tree src2 = fold_convert (long_long_unsigned_type_node, src);
+ call = build_call_expr (fn, 1, src1);
+ call = fold_build2 (PLUS_EXPR, TREE_TYPE (call), call,
+ build_call_expr (fn, 1, src2));
+ call = fold_convert (utype, call);
+ }
+ else
+ call = fold_convert (utype, build_call_expr (fn, 1, src));
if (adjust)
- iter = fold_build2 (MINUS_EXPR, utype,
- call,
- build_int_cst (utype, 1));
+ iter = fold_build2 (MINUS_EXPR, utype, call, build_int_cst (utype, 1));
else
iter = call;
if (TREE_CODE (call) == INTEGER_CST)
max = tree_to_uhwi (call);
else
- {
- max = TYPE_PRECISION (TREE_TYPE (src));
- if (adjust)
- max = max - 1;
- }
+ max = TYPE_PRECISION (TREE_TYPE (src));
+ if (adjust)
+ max = max - 1;
niter->niter = iter;
niter->assumptions = boolean_true_node;
+
if (adjust)
- niter->may_be_zero = fold_build2 (EQ_EXPR, boolean_type_node, src,
- build_zero_cst
- (TREE_TYPE (src)));
+ {
+ tree may_be_zero = fold_build2 (EQ_EXPR, boolean_type_node, src,
+ build_zero_cst (TREE_TYPE (src)));
+ niter->may_be_zero
+ = simplify_using_initial_conditions (loop, may_be_zero);
+ }
else
niter->may_be_zero = boolean_false_node;
the niter information holds unconditionally. */
bool
-number_of_iterations_exit (struct loop *loop, edge exit,
- struct tree_niter_desc *niter,
- bool warn, bool every_iteration)
+number_of_iterations_exit (class loop *loop, edge exit,
+ class tree_niter_desc *niter,
+ bool warn, bool every_iteration,
+ basic_block *body)
{
gcond *stmt;
if (!number_of_iterations_exit_assumptions (loop, exit, niter,
- &stmt, every_iteration))
+ &stmt, every_iteration, body))
return false;
if (integer_nonzerop (niter->assumptions))
return true;
- if (warn)
- dump_printf_loc (MSG_MISSED_OPTIMIZATION, gimple_location_safe (stmt),
+ if (warn && dump_enabled_p ())
+ dump_printf_loc (MSG_MISSED_OPTIMIZATION, stmt,
"missed loop optimization: niters analysis ends up "
"with assumptions.\n");
chrec_dont_know is returned. */
tree
-find_loop_niter (struct loop *loop, edge *exit)
+find_loop_niter (class loop *loop, edge *exit)
{
unsigned i;
- vec<edge> exits = get_loop_exit_edges (loop);
+ auto_vec<edge> exits = get_loop_exit_edges (loop);
edge ex;
tree niter = NULL_TREE, aniter;
- struct tree_niter_desc desc;
+ class tree_niter_desc desc;
*exit = NULL;
FOR_EACH_VEC_ELT (exits, i, ex)
continue;
}
}
- exits.release ();
return niter ? niter : chrec_dont_know;
}
/* Return true if loop is known to have bounded number of iterations. */
bool
-finite_loop_p (struct loop *loop)
+finite_loop_p (class loop *loop)
{
widest_int nit;
int flags;
loop->num);
return true;
}
+
+ if (loop->finite_p)
+ {
+ unsigned i;
+ auto_vec<edge> exits = get_loop_exit_edges (loop);
+ edge ex;
+
+ /* If the loop has a normal exit, we can assume it will terminate. */
+ FOR_EACH_VEC_ELT (exits, i, ex)
+ if (!(ex->flags & (EDGE_EH | EDGE_ABNORMAL | EDGE_FAKE)))
+ {
+ if (dump_file)
+ fprintf (dump_file, "Assume loop %i to be finite: it has an exit "
+ "and -ffinite-loops is on.\n", loop->num);
+ return true;
+ }
+ }
+
return false;
}
/* Bound on the number of iterations we try to evaluate. */
#define MAX_ITERATIONS_TO_TRACK \
- ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
+ ((unsigned) param_max_iterations_to_track)
/* Returns the loop phi node of LOOP such that ssa name X is derived from its
result by a chain of operations such that all but exactly one of their
operands are constants. */
static gphi *
-chain_of_csts_start (struct loop *loop, tree x)
+chain_of_csts_start (class loop *loop, tree x)
{
gimple *stmt = SSA_NAME_DEF_STMT (x);
tree use;
If such phi node exists, it is returned, otherwise NULL is returned. */
static gphi *
-get_base_for (struct loop *loop, tree x)
+get_base_for (class loop *loop, tree x)
{
gphi *phi;
tree init, next;
else if (gimple_assign_rhs_class (stmt) == GIMPLE_UNARY_RHS
&& TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
return fold_build1 (gimple_assign_rhs_code (stmt),
- gimple_expr_type (stmt),
+ TREE_TYPE (gimple_assign_lhs (stmt)),
get_val_for (gimple_assign_rhs1 (stmt), base));
else if (gimple_assign_rhs_class (stmt) == GIMPLE_BINARY_RHS)
{
else
gcc_unreachable ();
return fold_build2 (gimple_assign_rhs_code (stmt),
- gimple_expr_type (stmt), rhs1, rhs2);
+ TREE_TYPE (gimple_assign_lhs (stmt)), rhs1, rhs2);
}
else
gcc_unreachable ();
of the iterations of LOOP if successful, chrec_dont_know otherwise. */
tree
-loop_niter_by_eval (struct loop *loop, edge exit)
+loop_niter_by_eval (class loop *loop, edge exit)
{
tree acnd;
tree op[2], val[2], next[2], aval[2];
determines the number of iterations, chrec_dont_know is returned. */
tree
-find_loop_niter_by_eval (struct loop *loop, edge *exit)
+find_loop_niter_by_eval (class loop *loop, edge *exit)
{
unsigned i;
- vec<edge> exits = get_loop_exit_edges (loop);
+ auto_vec<edge> exits = get_loop_exit_edges (loop);
edge ex;
tree niter = NULL_TREE, aniter;
/* Loops with multiple exits are expensive to handle and less important. */
if (!flag_expensive_optimizations
&& exits.length () > 1)
- {
- exits.release ();
- return chrec_dont_know;
- }
+ return chrec_dont_know;
FOR_EACH_VEC_ELT (exits, i, ex)
{
niter = aniter;
*exit = ex;
}
- exits.release ();
return niter ? niter : chrec_dont_know;
}
/* Emit a -Waggressive-loop-optimizations warning if needed. */
static void
-do_warn_aggressive_loop_optimizations (struct loop *loop,
+do_warn_aggressive_loop_optimizations (class loop *loop,
widest_int i_bound, gimple *stmt)
{
/* Don't warn if the loop doesn't have known constant bound. */
char buf[WIDE_INT_PRINT_BUFFER_SIZE];
print_dec (i_bound, buf, TYPE_UNSIGNED (TREE_TYPE (loop->nb_iterations))
? UNSIGNED : SIGNED);
+ auto_diagnostic_group d;
if (warning_at (gimple_location (stmt), OPT_Waggressive_loop_optimizations,
"iteration %s invokes undefined behavior", buf))
inform (gimple_location (estmt), "within this loop");
BOUND times. I_BOUND is a widest_int upper estimate on BOUND. */
static void
-record_estimate (struct loop *loop, tree bound, const widest_int &i_bound,
+record_estimate (class loop *loop, tree bound, const widest_int &i_bound,
gimple *at_stmt, bool is_exit, bool realistic, bool upper)
{
widest_int delta;
|| loop->nb_iterations == NULL_TREE
|| TREE_CODE (loop->nb_iterations) != INTEGER_CST))
{
- struct nb_iter_bound *elt = ggc_alloc<nb_iter_bound> ();
+ class nb_iter_bound *elt = ggc_alloc<nb_iter_bound> ();
elt->bound = i_bound;
elt->stmt = at_stmt;
and doesn't overflow. */
static void
-record_control_iv (struct loop *loop, struct tree_niter_desc *niter)
+record_control_iv (class loop *loop, class tree_niter_desc *niter)
{
struct control_iv *iv;
return false;
gimple *def_stmt = SSA_NAME_DEF_STMT (var);
- struct loop *loop = loop_containing_stmt (def_stmt);
+ class loop *loop = loop_containing_stmt (def_stmt);
if (loop == NULL)
return false;
UPPER is true if we are sure the induction variable does not wrap. */
static void
-record_nonwrapping_iv (struct loop *loop, tree base, tree step, gimple *stmt,
+record_nonwrapping_iv (class loop *loop, tree base, tree step, gimple *stmt,
tree low, tree high, bool realistic, bool upper)
{
tree niter_bound, extreme, delta;
if (tree_int_cst_sign_bit (step))
{
- wide_int min, max;
+ wide_int max;
+ value_range base_range;
+ if (get_range_query (cfun)->range_of_expr (base_range, orig_base)
+ && !base_range.undefined_p ())
+ max = base_range.upper_bound ();
extreme = fold_convert (unsigned_type, low);
if (TREE_CODE (orig_base) == SSA_NAME
&& TREE_CODE (high) == INTEGER_CST
&& INTEGRAL_TYPE_P (TREE_TYPE (orig_base))
- && (get_range_info (orig_base, &min, &max) == VR_RANGE
+ && (base_range.kind () == VR_RANGE
|| get_cst_init_from_scev (orig_base, &max, false))
&& wi::gts_p (wi::to_wide (high), max))
base = wide_int_to_tree (unsigned_type, max);
}
else
{
- wide_int min, max;
+ wide_int min;
+ value_range base_range;
+ if (get_range_query (cfun)->range_of_expr (base_range, orig_base)
+ && !base_range.undefined_p ())
+ min = base_range.lower_bound ();
extreme = fold_convert (unsigned_type, high);
if (TREE_CODE (orig_base) == SSA_NAME
&& TREE_CODE (low) == INTEGER_CST
&& INTEGRAL_TYPE_P (TREE_TYPE (orig_base))
- && (get_range_info (orig_base, &min, &max) == VR_RANGE
+ && (base_range.kind () == VR_RANGE
|| get_cst_init_from_scev (orig_base, &min, true))
&& wi::gts_p (min, wi::to_wide (low)))
base = wide_int_to_tree (unsigned_type, min);
struct ilb_data
{
- struct loop *loop;
+ class loop *loop;
gimple *stmt;
};
tree ev, init, step;
tree low, high, type, next;
bool sign, upper = true, at_end = false;
- struct loop *loop = data->loop;
+ class loop *loop = data->loop;
if (TREE_CODE (base) != ARRAY_REF)
return true;
upper = false;
}
- struct loop *dloop = loop_containing_stmt (data->stmt);
+ class loop *dloop = loop_containing_stmt (data->stmt);
if (!dloop)
return true;
STMT is guaranteed to be executed in every iteration of LOOP.*/
static void
-infer_loop_bounds_from_ref (struct loop *loop, gimple *stmt, tree ref)
+infer_loop_bounds_from_ref (class loop *loop, gimple *stmt, tree ref)
{
struct ilb_data data;
executed in every iteration of LOOP. */
static void
-infer_loop_bounds_from_array (struct loop *loop, gimple *stmt)
+infer_loop_bounds_from_array (class loop *loop, gimple *stmt)
{
if (is_gimple_assign (stmt))
{
that pointer arithmetics in STMT does not overflow. */
static void
-infer_loop_bounds_from_pointer_arith (struct loop *loop, gimple *stmt)
+infer_loop_bounds_from_pointer_arith (class loop *loop, gimple *stmt)
{
tree def, base, step, scev, type, low, high;
tree var, ptr;
if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (var)))
return;
- struct loop *uloop = loop_containing_stmt (stmt);
+ class loop *uloop = loop_containing_stmt (stmt);
scev = instantiate_parameters (loop, analyze_scalar_evolution (uloop, def));
if (chrec_contains_undetermined (scev))
return;
that signed arithmetics in STMT does not overflow. */
static void
-infer_loop_bounds_from_signedness (struct loop *loop, gimple *stmt)
+infer_loop_bounds_from_signedness (class loop *loop, gimple *stmt)
{
tree def, base, step, scev, type, low, high;
low = lower_bound_in_type (type, type);
high = upper_bound_in_type (type, type);
- wide_int minv, maxv;
- if (get_range_info (def, &minv, &maxv) == VR_RANGE)
+ value_range r;
+ get_range_query (cfun)->range_of_expr (r, def);
+ if (r.kind () == VR_RANGE)
{
- low = wide_int_to_tree (type, minv);
- high = wide_int_to_tree (type, maxv);
+ low = wide_int_to_tree (type, r.lower_bound ());
+ high = wide_int_to_tree (type, r.upper_bound ());
}
record_nonwrapping_iv (loop, base, step, stmt, low, high, false, true);
*/
static void
-infer_loop_bounds_from_undefined (struct loop *loop)
+infer_loop_bounds_from_undefined (class loop *loop, basic_block *bbs)
{
unsigned i;
- basic_block *bbs;
gimple_stmt_iterator bsi;
basic_block bb;
bool reliable;
- bbs = get_loop_body (loop);
-
for (i = 0; i < loop->num_nodes; i++)
{
bb = bbs[i];
}
}
-
- free (bbs);
}
/* Compare wide ints, callback for qsort. */
Lookup by binary search. */
static int
-bound_index (vec<widest_int> bounds, const widest_int &bound)
+bound_index (const vec<widest_int> &bounds, const widest_int &bound)
{
unsigned int end = bounds.length ();
unsigned int begin = 0;
some bounded statement. */
static void
-discover_iteration_bound_by_body_walk (struct loop *loop)
+discover_iteration_bound_by_body_walk (class loop *loop)
{
- struct nb_iter_bound *elt;
+ class nb_iter_bound *elt;
auto_vec<widest_int> bounds;
vec<vec<basic_block> > queues = vNULL;
vec<basic_block> queue = vNULL;
/* Start walk in loop header with index set to infinite bound. */
queue_index = bounds.length ();
- queues.safe_grow_cleared (queue_index + 1);
+ queues.safe_grow_cleared (queue_index + 1, true);
queue.safe_push (loop->header);
queues[queue_index] = queue;
block_priority.put (loop->header, queue_index);
count by 1. */
static void
-maybe_lower_iteration_bound (struct loop *loop)
+maybe_lower_iteration_bound (class loop *loop)
{
hash_set<gimple *> *not_executed_last_iteration = NULL;
- struct nb_iter_bound *elt;
+ class nb_iter_bound *elt;
bool found_exit = false;
auto_vec<basic_block> queue;
bitmap visited;
delete not_executed_last_iteration;
}
+/* Get expected upper bound for number of loop iterations for
+ BUILT_IN_EXPECT_WITH_PROBABILITY for a condition COND. */
+
+static tree
+get_upper_bound_based_on_builtin_expr_with_prob (gcond *cond)
+{
+ if (cond == NULL)
+ return NULL_TREE;
+
+ tree lhs = gimple_cond_lhs (cond);
+ if (TREE_CODE (lhs) != SSA_NAME)
+ return NULL_TREE;
+
+ gimple *stmt = SSA_NAME_DEF_STMT (gimple_cond_lhs (cond));
+ gcall *def = dyn_cast<gcall *> (stmt);
+ if (def == NULL)
+ return NULL_TREE;
+
+ tree decl = gimple_call_fndecl (def);
+ if (!decl
+ || !fndecl_built_in_p (decl, BUILT_IN_EXPECT_WITH_PROBABILITY)
+ || gimple_call_num_args (stmt) != 3)
+ return NULL_TREE;
+
+ tree c = gimple_call_arg (def, 1);
+ tree condt = TREE_TYPE (lhs);
+ tree res = fold_build2 (gimple_cond_code (cond),
+ condt, c,
+ gimple_cond_rhs (cond));
+ if (TREE_CODE (res) != INTEGER_CST)
+ return NULL_TREE;
+
+
+ tree prob = gimple_call_arg (def, 2);
+ tree t = TREE_TYPE (prob);
+ tree one
+ = build_real_from_int_cst (t,
+ integer_one_node);
+ if (integer_zerop (res))
+ prob = fold_build2 (MINUS_EXPR, t, one, prob);
+ tree r = fold_build2 (RDIV_EXPR, t, one, prob);
+ if (TREE_CODE (r) != REAL_CST)
+ return NULL_TREE;
+
+ HOST_WIDE_INT probi
+ = real_to_integer (TREE_REAL_CST_PTR (r));
+ return build_int_cst (condt, probi);
+}
+
/* Records estimates on numbers of iterations of LOOP. If USE_UNDEFINED_P
is true also use estimates derived from undefined behavior. */
void
-estimate_numbers_of_iterations (struct loop *loop)
+estimate_numbers_of_iterations (class loop *loop)
{
- vec<edge> exits;
tree niter, type;
unsigned i;
- struct tree_niter_desc niter_desc;
+ class tree_niter_desc niter_desc;
edge ex;
widest_int bound;
edge likely_exit;
diagnose those loops with -Waggressive-loop-optimizations. */
number_of_latch_executions (loop);
- exits = get_loop_exit_edges (loop);
- likely_exit = single_likely_exit (loop);
+ basic_block *body = get_loop_body (loop);
+ auto_vec<edge> exits = get_loop_exit_edges (loop, body);
+ likely_exit = single_likely_exit (loop, exits);
FOR_EACH_VEC_ELT (exits, i, ex)
{
- if (!number_of_iterations_exit (loop, ex, &niter_desc, false, false))
+ if (ex == likely_exit)
+ {
+ gimple *stmt = last_stmt (ex->src);
+ if (stmt != NULL)
+ {
+ gcond *cond = dyn_cast<gcond *> (stmt);
+ tree niter_bound
+ = get_upper_bound_based_on_builtin_expr_with_prob (cond);
+ if (niter_bound != NULL_TREE)
+ {
+ widest_int max = derive_constant_upper_bound (niter_bound);
+ record_estimate (loop, niter_bound, max, cond,
+ true, true, false);
+ }
+ }
+ }
+
+ if (!number_of_iterations_exit (loop, ex, &niter_desc,
+ false, false, body))
continue;
niter = niter_desc.niter;
true, ex == likely_exit, true);
record_control_iv (loop, &niter_desc);
}
- exits.release ();
if (flag_aggressive_loop_optimizations)
- infer_loop_bounds_from_undefined (loop);
+ infer_loop_bounds_from_undefined (loop, body);
+ free (body);
discover_iteration_bound_by_body_walk (loop);
the function returns false, otherwise returns true. */
bool
-estimated_loop_iterations (struct loop *loop, widest_int *nit)
+estimated_loop_iterations (class loop *loop, widest_int *nit)
{
/* When SCEV information is available, try to update loop iterations
estimate. Otherwise just return whatever we recorded earlier. */
on the number of iterations of LOOP could not be derived, returns -1. */
HOST_WIDE_INT
-estimated_loop_iterations_int (struct loop *loop)
+estimated_loop_iterations_int (class loop *loop)
{
widest_int nit;
HOST_WIDE_INT hwi_nit;
false, otherwise returns true. */
bool
-max_loop_iterations (struct loop *loop, widest_int *nit)
+max_loop_iterations (class loop *loop, widest_int *nit)
{
/* When SCEV information is available, try to update loop iterations
estimate. Otherwise just return whatever we recorded earlier. */
on the number of iterations of LOOP could not be derived, returns -1. */
HOST_WIDE_INT
-max_loop_iterations_int (struct loop *loop)
+max_loop_iterations_int (class loop *loop)
{
widest_int nit;
HOST_WIDE_INT hwi_nit;
false, otherwise returns true. */
bool
-likely_max_loop_iterations (struct loop *loop, widest_int *nit)
+likely_max_loop_iterations (class loop *loop, widest_int *nit)
{
/* When SCEV information is available, try to update loop iterations
estimate. Otherwise just return whatever we recorded earlier. */
on the number of iterations of LOOP could not be derived, returns -1. */
HOST_WIDE_INT
-likely_max_loop_iterations_int (struct loop *loop)
+likely_max_loop_iterations_int (class loop *loop)
{
widest_int nit;
HOST_WIDE_INT hwi_nit;
the number of execution of the latch by one. */
HOST_WIDE_INT
-estimated_stmt_executions_int (struct loop *loop)
+estimated_stmt_executions_int (class loop *loop)
{
HOST_WIDE_INT nit = estimated_loop_iterations_int (loop);
HOST_WIDE_INT snit;
false, otherwise returns true. */
bool
-max_stmt_executions (struct loop *loop, widest_int *nit)
+max_stmt_executions (class loop *loop, widest_int *nit)
{
widest_int nit_minus_one;
false, otherwise returns true. */
bool
-likely_max_stmt_executions (struct loop *loop, widest_int *nit)
+likely_max_stmt_executions (class loop *loop, widest_int *nit)
{
widest_int nit_minus_one;
false, otherwise returns true. */
bool
-estimated_stmt_executions (struct loop *loop, widest_int *nit)
+estimated_stmt_executions (class loop *loop, widest_int *nit)
{
widest_int nit_minus_one;
void
estimate_numbers_of_iterations (function *fn)
{
- struct loop *loop;
+ class loop *loop;
/* We don't want to issue signed overflow warnings while getting
loop iteration estimates. */
static bool
n_of_executions_at_most (gimple *stmt,
- struct nb_iter_bound *niter_bound,
+ class nb_iter_bound *niter_bound,
tree niter)
{
widest_int bound = niter_bound->bound;
/* By stmt_dominates_stmt_p we already know that STMT appears
before NITER_BOUND->STMT. Still need to test that the loop
- can not be terinated by a side effect in between. */
+ cannot be terinated by a side effect in between. */
for (bsi = gsi_for_stmt (stmt); gsi_stmt (bsi) != niter_bound->stmt;
gsi_next (&bsi))
if (gimple_has_side_effects (gsi_stmt (bsi)))
static bool
loop_exits_before_overflow (tree base, tree step,
- gimple *at_stmt, struct loop *loop)
+ gimple *at_stmt, class loop *loop)
{
widest_int niter;
struct control_iv *civ;
- struct nb_iter_bound *bound;
+ class nb_iter_bound *bound;
tree e, delta, step_abs, unsigned_base;
tree type = TREE_TYPE (step);
tree unsigned_type, valid_niter;
(4294967295, 4294967296, ...). */
static bool
-scev_var_range_cant_overflow (tree var, tree step, struct loop *loop)
+scev_var_range_cant_overflow (tree var, tree step, class loop *loop)
{
tree type;
wide_int minv, maxv, diff, step_wi;
- enum value_range_type rtype;
if (TREE_CODE (step) != INTEGER_CST || !INTEGRAL_TYPE_P (TREE_TYPE (var)))
return false;
if (!def_bb || !dominated_by_p (CDI_DOMINATORS, loop->latch, def_bb))
return false;
- rtype = get_range_info (var, &minv, &maxv);
- if (rtype != VR_RANGE)
+ value_range r;
+ get_range_query (cfun)->range_of_expr (r, var);
+ if (r.kind () != VR_RANGE)
return false;
/* VAR is a scev whose evolution part is STEP and value range info
type = TREE_TYPE (var);
if (tree_int_cst_sign_bit (step))
{
- diff = minv - wi::to_wide (lower_bound_in_type (type, type));
+ diff = r.lower_bound () - wi::to_wide (lower_bound_in_type (type, type));
step_wi = - step_wi;
}
else
- diff = wi::to_wide (upper_bound_in_type (type, type)) - maxv;
+ diff = wi::to_wide (upper_bound_in_type (type, type)) - r.upper_bound ();
return (wi::geu_p (diff, step_wi));
}
bool
scev_probably_wraps_p (tree var, tree base, tree step,
- gimple *at_stmt, struct loop *loop,
+ gimple *at_stmt, class loop *loop,
bool use_overflow_semantics)
{
/* FIXME: We really need something like
/* Frees the information on upper bounds on numbers of iterations of LOOP. */
void
-free_numbers_of_iterations_estimates (struct loop *loop)
+free_numbers_of_iterations_estimates (class loop *loop)
{
struct control_iv *civ;
- struct nb_iter_bound *bound;
+ class nb_iter_bound *bound;
loop->nb_iterations = NULL;
loop->estimate_state = EST_NOT_COMPUTED;
for (bound = loop->bounds; bound;)
{
- struct nb_iter_bound *next = bound->next;
+ class nb_iter_bound *next = bound->next;
ggc_free (bound);
bound = next;
}
void
free_numbers_of_iterations_estimates (function *fn)
{
- struct loop *loop;
+ class loop *loop;
FOR_EACH_LOOP_FN (fn, loop, 0)
free_numbers_of_iterations_estimates (loop);
at LOOP. */
void
-substitute_in_loop_info (struct loop *loop, tree name, tree val)
+substitute_in_loop_info (class loop *loop, tree name, tree val)
{
loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);
}
projects / thirdparty / gcc.git / blobdiff