From: Robin Dapp <[email protected]>
This patch adds a path for scev to continue when encountering wrapping
behavior instead of giving up. If scev_probably_wraps_p is passed a
nonzero nowrap_bound tree it will use the type bound of the current step
as upper bound for wrapping and store it.
In order for the nowrap_bound parameter to reach scev_probably_wraps_p,
the patch adds parameters to many of the internal scev functions. Most
of them just forward the parameter.
Initially, I attempted a global variable that was supposed to store the
bound. None of my tries resulted in comprehensible code or correct
results, however, and I found myself running into corner case
after corner case. Thus, I arrived at the mostly mechanical "brute-force"
solution.
The patch also introduces a new helper scev_add_nowrap_bound that
combines two bounds by building a MIN of each so that we'd get a
condition like IV <= MIN (dr1.bound, dr2.bound, ...).
Cache invalidation is handled by an additional bit (assumption or no
assumption) for the respective entry.
affine_iv gets a new field nowrap_bound. This allows passing the nowrap
bounds to dataref analysis.
gcc/ChangeLog:
* tree-chrec.cc (convert_affine_scev): Add nowrap_bound param.
(chrec_convert_rhs): Ditto.
(chrec_convert_1): Ditto.
(chrec_convert): Ditto.
* tree-chrec.h (chrec_convert): Ditto.
(chrec_convert_rhs): Ditto.
(convert_affine_scev): Ditto.
* tree-scalar-evolution.cc (analyze_scalar_evolution_1): Ditto.
(analyze_scalar_evolution_for_address_of): Ditto.
(struct scev_info_str): Add nowrap_assumed.
(new_scev_info_str): Ditto.
(scev_info_hasher::hash): Ditto.
(scev_info_hasher::equal): Ditto.
(find_var_scev_info): Ditto.
(scev_add_nowrap_bound): New function to accumulate bounds.
(set_scalar_evolution): Add nowrap_bound param.
(get_scalar_evolution): Ditto.
(simplify_peeled_chrec): Ditto.
(analyze_evolution_in_loop): Ditto.
(interpret_loop_phi): Ditto.
(interpret_condition_phi): Ditto.
(interpret_rhs_expr): Ditto.
(interpret_expr): Ditto.
(interpret_gimple_assign): Ditto.
(analyze_scalar_evolution): Ditto.
(analyze_scalar_evolution_in_loop): Ditto.
(simple_iv_with_niters): Add allow_wrapping.
(simple_iv): Ditto.
* tree-scalar-evolution.h (analyze_scalar_evolution): Add new
param.
(simple_iv_with_niters): Ditto.
(scev_add_nowrap_bound): Declare.
* tree-ssa-loop-niter.cc (scev_probably_wraps_p): Build no-wrap
bound.
* tree-ssa-loop-niter.h (scev_probably_wraps_p): Add param.
* tree-ssa-loop.h (struct affine_iv): Add nowrap_bound.
---
gcc/tree-chrec.cc | 51 ++++--
gcc/tree-chrec.h | 7 +-
gcc/tree-scalar-evolution.cc | 314 +++++++++++++++++++++++------------
gcc/tree-scalar-evolution.h | 9 +-
gcc/tree-ssa-loop-niter.cc | 16 +-
gcc/tree-ssa-loop-niter.h | 2 +-
gcc/tree-ssa-loop.h | 4 +
7 files changed, 270 insertions(+), 133 deletions(-)
diff --git a/gcc/tree-chrec.cc b/gcc/tree-chrec.cc
index 9869389a7b9..2b1659eab76 100644
--- a/gcc/tree-chrec.cc
+++ b/gcc/tree-chrec.cc
@@ -1421,13 +1421,18 @@ nb_vars_in_chrec (tree chrec)
that the rules for overflow of the given language apply (e.g., that signed
arithmetics in C does not overflow) -- i.e., to use them to avoid
unnecessary tests, but also to enforce that the result follows them.
- FROM is the source variable converted if it's not NULL. Returns true if
- the conversion succeeded, false otherwise. */
+ FROM is the source variable converted if it's not NULL.
+ If NOWRAP_BOUND is nonzero, pass it on to scev_probably_wraps_p etc.
+ to have them determine the bound below which no wrapping occurs.
+ Most other functions just forward NOWRAP_BOUND, therefore it is not
+ documented everywhere.
+ The function returns true if the conversion succeeded, false otherwise. */
bool
convert_affine_scev (class loop *loop, tree type,
tree *base, tree *step, gimple *at_stmt,
- bool use_overflow_semantics, tree from)
+ bool use_overflow_semantics, tree from,
+ tree *nowrap_bound)
{
tree ct = TREE_TYPE (*step);
bool enforce_overflow_semantics;
@@ -1452,6 +1457,11 @@ convert_affine_scev (class loop *loop, tree type,
happen. */
must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
+ /* MUST_CHECK_SRC_OVERFLOW implies chrec_convert_aggressive later
+ which can prove "no wrap" without assumptions. */
+ if (!must_check_src_overflow)
+ nowrap_bound = NULL;
+
enforce_overflow_semantics = (use_overflow_semantics
&& nowrap_type_p (type));
if (enforce_overflow_semantics)
@@ -1487,10 +1497,11 @@ convert_affine_scev (class loop *loop, tree type,
if (must_check_src_overflow
&& scev_probably_wraps_p (from, *base, *step, at_stmt, loop,
- use_overflow_semantics))
+ use_overflow_semantics, nowrap_bound))
return false;
- new_base = chrec_convert (type, *base, at_stmt, use_overflow_semantics);
+ new_base = chrec_convert (type, *base, at_stmt, nowrap_bound,
+ use_overflow_semantics);
/* The step must be sign extended, regardless of the signedness
of CT and TYPE. This only needs to be handled specially when
CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
@@ -1501,10 +1512,10 @@ convert_affine_scev (class loop *loop, tree type,
if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
{
tree signed_ct = signed_type_for (ct);
- new_step = chrec_convert (signed_ct, new_step, at_stmt,
+ new_step = chrec_convert (signed_ct, new_step, at_stmt, nowrap_bound,
use_overflow_semantics);
}
- new_step = chrec_convert (step_type, new_step, at_stmt,
+ new_step = chrec_convert (step_type, new_step, at_stmt, nowrap_bound,
use_overflow_semantics);
if (automatically_generated_chrec_p (new_base)
@@ -1515,7 +1526,7 @@ convert_affine_scev (class loop *loop, tree type,
/* Note that in this case we cannot use the fact that signed variables
do not overflow, as this is what we are verifying for the new iv. */
&& scev_probably_wraps_p (NULL_TREE, new_base, new_step,
- at_stmt, loop, false))
+ at_stmt, loop, false, nowrap_bound))
return false;
*base = new_base;
@@ -1528,12 +1539,12 @@ convert_affine_scev (class loop *loop, tree type,
The increment for a pointer type is always sizetype. */
tree
-chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt)
+chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt, tree *nowrap_bound)
{
if (POINTER_TYPE_P (type))
type = sizetype;
- return chrec_convert (type, chrec, at_stmt);
+ return chrec_convert (type, chrec, at_stmt, nowrap_bound);
}
/* Convert CHREC to TYPE. When the analyzer knows the context in
@@ -1552,7 +1563,7 @@ chrec_convert_rhs (tree type, tree chrec, gimple *at_stmt)
static tree
chrec_convert_1 (tree type, tree chrec, gimple *at_stmt,
- bool use_overflow_semantics, tree from)
+ tree *nowrap_bound, bool use_overflow_semantics, tree from)
{
tree ct, res;
tree base, step;
@@ -1573,7 +1584,7 @@ chrec_convert_1 (tree type, tree chrec, gimple *at_stmt,
step = CHREC_RIGHT (chrec);
if (convert_affine_scev (loop, type, &base, &step, at_stmt,
- use_overflow_semantics, from))
+ use_overflow_semantics, from, nowrap_bound))
return build_polynomial_chrec (loop->num, base, step);
/* If we cannot propagate the cast inside the chrec, just keep the cast. */
@@ -1606,7 +1617,8 @@ keep_cast:
CHREC_LEFT (chrec)),
fold_convert (utype,
CHREC_RIGHT (chrec)));
- res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics, from);
+ res = chrec_convert_1 (type, res, at_stmt, nowrap_bound,
+ use_overflow_semantics, from);
}
/* Similar perform the trick that (unsigned T)(base + step) can be
folded to ((unsigned T)x + (unsigned T)step). */
@@ -1631,7 +1643,8 @@ keep_cast:
CHREC_LEFT (chrec)),
fold_convert (type,
CHREC_RIGHT (chrec)));
- res = chrec_convert_1 (type, res, at_stmt, use_overflow_semantics, from);
+ res = chrec_convert_1 (type, res, at_stmt, nowrap_bound,
+ use_overflow_semantics, from);
}
else
res = fold_convert (type, chrec);
@@ -1677,6 +1690,11 @@ keep_cast:
{(uint) 0, +, (uint) 260}
+ If NOWRAP_BOUND is nonzero it is used to store the bound below which
+ no wrapping occurs. Here as well as in many other similar functions,
+ it is just passed through to other functions and thus not documented
+ everywhere.
+
USE_OVERFLOW_SEMANTICS is true if this function should assume that
the rules for overflow of the given language apply (e.g., that signed
arithmetics in C does not overflow) -- i.e., to use them to avoid
@@ -1686,9 +1704,10 @@ keep_cast:
tree
chrec_convert (tree type, tree chrec, gimple *at_stmt,
- bool use_overflow_semantics, tree from)
+ tree *nowrap_bound, bool use_overflow_semantics, tree from)
{
- return chrec_convert_1 (type, chrec, at_stmt, use_overflow_semantics, from);
+ return chrec_convert_1 (type, chrec, at_stmt, nowrap_bound,
+ use_overflow_semantics, from);
}
/* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
diff --git a/gcc/tree-chrec.h b/gcc/tree-chrec.h
index 7777ff50942..9fdfaac0e15 100644
--- a/gcc/tree-chrec.h
+++ b/gcc/tree-chrec.h
@@ -62,8 +62,9 @@ enum ev_direction scev_direction (const_tree);
extern tree chrec_fold_plus (tree, tree, tree);
extern tree chrec_fold_minus (tree, tree, tree);
extern tree chrec_fold_multiply (tree, tree, tree);
-extern tree chrec_convert (tree, tree, gimple *, bool = true, tree = NULL);
-extern tree chrec_convert_rhs (tree, tree, gimple * = NULL);
+extern tree chrec_convert (tree, tree, gimple *, tree * = nullptr,
+ bool = true, tree = NULL);
+extern tree chrec_convert_rhs (tree, tree, gimple * = NULL, tree * = nullptr);
extern tree chrec_convert_aggressive (tree, tree, bool *);
/* Operations. */
@@ -78,7 +79,7 @@ extern tree reset_evolution_in_loop (unsigned, tree, tree);
extern tree chrec_merge (tree, tree);
extern void for_each_scev_op (tree *, bool (*) (tree *, void *), void *);
extern bool convert_affine_scev (class loop *, tree, tree *, tree *, gimple *,
- bool, tree = NULL);
+ bool, tree = NULL, tree * = nullptr);
/* Observers. */
extern bool eq_evolutions_p (const_tree, const_tree);
diff --git a/gcc/tree-scalar-evolution.cc b/gcc/tree-scalar-evolution.cc
index b9acdbe9135..0d1500fec65 100644
--- a/gcc/tree-scalar-evolution.cc
+++ b/gcc/tree-scalar-evolution.cc
@@ -286,18 +286,24 @@ along with GCC; see the file COPYING3. If not see
#include "case-cfn-macros.h"
#include "tree-eh.h"
-static tree analyze_scalar_evolution_1 (class loop *, tree);
+static tree analyze_scalar_evolution_1 (class loop *, tree, tree * = nullptr);
static tree analyze_scalar_evolution_for_address_of (class loop *loop,
- tree var);
+ tree var,
+ tree * = nullptr);
/* The cached information about an SSA name with version NAME_VERSION,
claiming that below basic block with index INSTANTIATED_BELOW, the
- value of the SSA name can be expressed as CHREC. */
+ value of the SSA name can be expressed as CHREC.
+ NOWRAP_ASSUMPTION_P indicates whether or not the SSA name requires
+ an assumption to guarantee that it doesn't wrap. The assumption
+ itself is stored in NOWRAP_BOUND if necessary. */
struct GTY((for_user)) scev_info_str {
unsigned int name_version;
int instantiated_below;
+ bool nowrap_assumption_p;
tree chrec;
+ tree nowrap_bound;
};
/* Counters for the scev database. */
@@ -316,14 +322,17 @@ static GTY (()) hash_table<scev_info_hasher>
*scalar_evolution_info;
/* Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. */
static inline struct scev_info_str *
-new_scev_info_str (basic_block instantiated_below, tree var)
+new_scev_info_str (basic_block instantiated_below, tree var,
+ bool nowrap_assumption_p)
{
struct scev_info_str *res;
res = ggc_alloc<scev_info_str> ();
res->name_version = SSA_NAME_VERSION (var);
- res->chrec = chrec_not_analyzed_yet;
res->instantiated_below = instantiated_below->index;
+ res->nowrap_assumption_p = nowrap_assumption_p;
+ res->chrec = chrec_not_analyzed_yet;
+ res->nowrap_bound = NULL_TREE;
return res;
}
@@ -333,7 +342,8 @@ new_scev_info_str (basic_block instantiated_below, tree var)
hashval_t
scev_info_hasher::hash (scev_info_str *elt)
{
- return elt->name_version ^ elt->instantiated_below;
+ return (elt->name_version ^ elt->instantiated_below)
+ + elt->nowrap_assumption_p;
}
/* Compares database elements E1 and E2. */
@@ -342,27 +352,29 @@ bool
scev_info_hasher::equal (const scev_info_str *elt1, const scev_info_str *elt2)
{
return (elt1->name_version == elt2->name_version
- && elt1->instantiated_below == elt2->instantiated_below);
+ && elt1->instantiated_below == elt2->instantiated_below
+ && elt1->nowrap_assumption_p == elt2->nowrap_assumption_p);
}
/* Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.
A first query on VAR returns chrec_not_analyzed_yet. */
-static tree *
-find_var_scev_info (basic_block instantiated_below, tree var)
+static scev_info_str *
+find_var_scev_info (basic_block instantiated_below, tree var,
+ bool nowrap_assumption_p)
{
- struct scev_info_str *res;
struct scev_info_str tmp;
tmp.name_version = SSA_NAME_VERSION (var);
tmp.instantiated_below = instantiated_below->index;
+ tmp.nowrap_assumption_p = nowrap_assumption_p;
scev_info_str **slot = scalar_evolution_info->find_slot (&tmp, INSERT);
if (!*slot)
- *slot = new_scev_info_str (instantiated_below, var);
- res = *slot;
+ *slot = new_scev_info_str (instantiated_below, var,
+ tmp.nowrap_assumption_p);
- return &res->chrec;
+ return *slot;
}
@@ -396,6 +408,27 @@ instantiate_cache_type::~instantiate_cache_type ()
or resolve_mixers call. */
static instantiate_cache_type *global_cache;
+/* Build a combined bound from BASE and BOUND by taking the minimum
+ of both. The result is stored in BASE. */
+
+void
+scev_add_nowrap_bound (tree *base, tree bound)
+{
+ if (!base || !bound)
+ return;
+ if (!*base)
+ {
+ *base = bound;
+ return;
+ }
+
+ tree t1 = TREE_TYPE (*base);
+ tree t2 = TREE_TYPE (bound);
+ tree wide_type = TYPE_PRECISION (t1) >= TYPE_PRECISION (t2) ? t1 : t2;
+ *base = fold_build2 (MIN_EXPR, wide_type,
+ fold_convert (wide_type, *base),
+ fold_convert (wide_type, bound));
+}
/* Return true when PHI is a loop-phi-node. */
@@ -493,14 +526,16 @@ compute_overall_effect_of_inner_loop (class loop *loop,
tree evolution_fn)
/* Associate CHREC to SCALAR. */
static void
-set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec)
+set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec,
+ tree *nowrap_bound)
{
- tree *scalar_info;
+ scev_info_str *scalar_info;
if (TREE_CODE (scalar) != SSA_NAME)
return;
- scalar_info = find_var_scev_info (instantiated_below, scalar);
+ scalar_info = find_var_scev_info (instantiated_below, scalar,
+ nowrap_bound != nullptr);
if (dump_file)
{
@@ -519,14 +554,17 @@ set_scalar_evolution (basic_block instantiated_below,
tree scalar, tree chrec)
nb_set_scev++;
}
- *scalar_info = chrec;
+ scalar_info->chrec = chrec;
+ if (scalar_info->nowrap_assumption_p && nowrap_bound)
+ scalar_info->nowrap_bound = *nowrap_bound;
}
/* Retrieve the chrec associated to SCALAR instantiated below
INSTANTIATED_BELOW block. */
static tree
-get_scalar_evolution (basic_block instantiated_below, tree scalar)
+get_scalar_evolution (basic_block instantiated_below, tree scalar,
+ tree *nowrap_bound)
{
tree res;
@@ -551,10 +589,19 @@ get_scalar_evolution (basic_block instantiated_below,
tree scalar)
switch (TREE_CODE (scalar))
{
case SSA_NAME:
- if (SSA_NAME_IS_DEFAULT_DEF (scalar))
+ if (SSA_NAME_IS_DEFAULT_DEF (scalar))
res = scalar;
else
- res = *find_var_scev_info (instantiated_below, scalar);
+ {
+ scev_info_str *info
+ = find_var_scev_info (instantiated_below, scalar,
+ nowrap_bound != nullptr);
+ res = info->chrec;
+ if (info->nowrap_assumption_p
+ && res != chrec_not_analyzed_yet
+ && info->nowrap_bound)
+ scev_add_nowrap_bound (nowrap_bound, info->nowrap_bound);
+ }
break;
case REAL_CST:
@@ -1361,12 +1408,18 @@ get_loop_exit_condition (const_edge exit_edge)
See PR41488. */
static tree
-simplify_peeled_chrec (class loop *loop, tree arg, tree init_cond)
+simplify_peeled_chrec (class loop *loop, tree arg, tree init_cond,
+ tree *nowrap_bound = nullptr)
{
aff_tree aff1, aff2;
tree ev, left, right, type, step_val;
hash_map<tree, name_expansion *> *peeled_chrec_map = NULL;
+ tree local_nowrap_bound = NULL_TREE;
+ tree *bound = nullptr;
+ if (nowrap_bound)
+ bound = &local_nowrap_bound;
+
ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, arg));
if (ev == NULL_TREE)
return chrec_dont_know;
@@ -1390,7 +1443,7 @@ simplify_peeled_chrec (class loop *loop, tree arg, tree
init_cond)
if (TREE_CODE (left_before) == INTEGER_CST
&& wi::to_widest (init_cond) == wi::to_widest (left_before)
&& !scev_probably_wraps_p (NULL_TREE, left_before, right, NULL,
- loop, false))
+ loop, false, bound))
{
tree tp = TREE_TYPE (right);
@@ -1399,10 +1452,11 @@ simplify_peeled_chrec (class loop *loop, tree arg, tree
init_cond)
if (TYPE_UNSIGNED (tp))
right = fold_convert (signed_type_for (tp), right);
- return build_polynomial_chrec (loop->num, init_cond,
- chrec_convert (TREE_TYPE (ev),
- right, NULL,
- false, NULL_TREE));
+ scev_add_nowrap_bound (nowrap_bound, local_nowrap_bound);
+ return build_polynomial_chrec
+ (loop->num, init_cond, chrec_convert (TREE_TYPE (ev), right, NULL,
+ nullptr, false,
+ NULL_TREE));
}
return chrec_dont_know;
}
@@ -1422,6 +1476,7 @@ simplify_peeled_chrec (class loop *loop, tree arg, tree
init_cond)
if (dump_file && (dump_flags & TDF_SCEV))
fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
+ scev_add_nowrap_bound (nowrap_bound, local_nowrap_bound);
return build_polynomial_chrec (loop->num, init_cond, right);
}
@@ -1444,6 +1499,7 @@ simplify_peeled_chrec (class loop *loop, tree arg, tree
init_cond)
if (dump_file && (dump_flags & TDF_SCEV))
fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
+ scev_add_nowrap_bound (nowrap_bound, local_nowrap_bound);
return build_polynomial_chrec (loop->num, init_cond, right);
}
return chrec_dont_know;
@@ -1454,7 +1510,8 @@ simplify_peeled_chrec (class loop *loop, tree arg, tree
init_cond)
static tree
analyze_evolution_in_loop (gphi *loop_phi_node,
- tree init_cond)
+ tree init_cond,
+ tree *nowrap_bound = nullptr)
{
int i, n = gimple_phi_num_args (loop_phi_node);
tree evolution_function = chrec_not_analyzed_yet;
@@ -1517,7 +1574,8 @@ analyze_evolution_in_loop (gphi *loop_phi_node,
if (simplify_peeled_chrec_p && TREE_CODE (arg) == SSA_NAME)
{
simplify_peeled_chrec_p = false;
- ev_fn = simplify_peeled_chrec (loop, arg, init_cond);
+ ev_fn = simplify_peeled_chrec
+ (loop, arg, init_cond, nowrap_bound);
simplify_peeled_chrec_p = true;
}
}
@@ -1640,7 +1698,8 @@ analyze_initial_condition (gphi *loop_phi_node)
/* Analyze the scalar evolution for LOOP_PHI_NODE. */
static tree
-interpret_loop_phi (class loop *loop, gphi *loop_phi_node)
+interpret_loop_phi (class loop *loop, gphi *loop_phi_node,
+ tree *nowrap_bound = nullptr)
{
class loop *phi_loop = loop_containing_stmt (loop_phi_node);
tree init_cond;
@@ -1649,7 +1708,7 @@ interpret_loop_phi (class loop *loop, gphi *loop_phi_node)
/* Otherwise really interpret the loop phi. */
init_cond = analyze_initial_condition (loop_phi_node);
- return analyze_evolution_in_loop (loop_phi_node, init_cond);
+ return analyze_evolution_in_loop (loop_phi_node, init_cond, nowrap_bound);
}
/* This function merges the branches of a condition-phi-node,
@@ -1657,7 +1716,8 @@ interpret_loop_phi (class loop *loop, gphi *loop_phi_node)
analyzed. */
static tree
-interpret_condition_phi (class loop *loop, gphi *condition_phi)
+interpret_condition_phi (class loop *loop, gphi *condition_phi,
+ tree *nowrap_bound)
{
int i, n = gimple_phi_num_args (condition_phi);
tree res = chrec_not_analyzed_yet;
@@ -1673,7 +1733,7 @@ interpret_condition_phi (class loop *loop, gphi
*condition_phi)
}
branch_chrec = analyze_scalar_evolution
- (loop, PHI_ARG_DEF (condition_phi, i));
+ (loop, PHI_ARG_DEF (condition_phi, i), nowrap_bound);
res = chrec_merge (res, branch_chrec);
if (res == chrec_dont_know)
@@ -1692,7 +1752,8 @@ interpret_condition_phi (class loop *loop, gphi
*condition_phi)
static tree
interpret_rhs_expr (class loop *loop, gimple *at_stmt,
- tree type, tree rhs1, enum tree_code code, tree rhs2)
+ tree type, tree rhs1, enum tree_code code, tree rhs2,
+ tree *nowrap_bound = nullptr)
{
tree res, chrec1, chrec2, ctype;
gimple *def;
@@ -1703,8 +1764,10 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt,
return chrec_convert (type, rhs1, at_stmt);
if (code == SSA_NAME)
- return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
- at_stmt);
+ return chrec_convert (type,
+ analyze_scalar_evolution (loop, rhs1,
+ nowrap_bound),
+ at_stmt, nowrap_bound);
}
switch (code)
@@ -1730,25 +1793,28 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt,
rhs2 = TREE_OPERAND (base, 1);
rhs1 = TREE_OPERAND (base, 0);
- chrec1 = analyze_scalar_evolution (loop, rhs1);
- chrec2 = analyze_scalar_evolution (loop, rhs2);
- chrec1 = chrec_convert (type, chrec1, at_stmt);
- chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
+ chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound);
+ chrec2 = analyze_scalar_evolution (loop, rhs2, nowrap_bound);
+ chrec1 = chrec_convert (type, chrec1, at_stmt, nowrap_bound);
+ chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt,
+ nowrap_bound);
chrec1 = instantiate_parameters (loop, chrec1);
chrec2 = instantiate_parameters (loop, chrec2);
res = chrec_fold_plus (type, chrec1, chrec2);
}
else
{
- chrec1 = analyze_scalar_evolution_for_address_of (loop, base);
- chrec1 = chrec_convert (type, chrec1, at_stmt);
+ chrec1 = analyze_scalar_evolution_for_address_of (loop, base,
+ nowrap_bound);
+ chrec1 = chrec_convert (type, chrec1, at_stmt, nowrap_bound);
res = chrec1;
}
if (offset != NULL_TREE)
{
- chrec2 = analyze_scalar_evolution (loop, offset);
- chrec2 = chrec_convert (TREE_TYPE (offset), chrec2, at_stmt);
+ chrec2 = analyze_scalar_evolution (loop, offset, nowrap_bound);
+ chrec2 = chrec_convert (TREE_TYPE (offset), chrec2, at_stmt,
+ nowrap_bound);
chrec2 = instantiate_parameters (loop, chrec2);
res = chrec_fold_plus (type, res, chrec2);
}
@@ -1756,8 +1822,9 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt,
if (maybe_ne (bitpos, 0))
{
unitpos = size_int (exact_div (bitpos, BITS_PER_UNIT));
- chrec3 = analyze_scalar_evolution (loop, unitpos);
- chrec3 = chrec_convert (TREE_TYPE (unitpos), chrec3, at_stmt);
+ chrec3 = analyze_scalar_evolution (loop, unitpos, nowrap_bound);
+ chrec3 = chrec_convert (TREE_TYPE (unitpos), chrec3, at_stmt,
+ nowrap_bound);
chrec3 = instantiate_parameters (loop, chrec3);
res = chrec_fold_plus (type, res, chrec3);
}
@@ -1767,10 +1834,11 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt,
break;
case POINTER_PLUS_EXPR:
- chrec1 = analyze_scalar_evolution (loop, rhs1);
- chrec2 = analyze_scalar_evolution (loop, rhs2);
- chrec1 = chrec_convert (type, chrec1, at_stmt);
- chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
+ chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound);
+ chrec2 = analyze_scalar_evolution (loop, rhs2, nowrap_bound);
+ chrec1 = chrec_convert (type, chrec1, at_stmt, nowrap_bound);
+ chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt,
+ nowrap_bound);
chrec1 = instantiate_parameters (loop, chrec1);
chrec2 = instantiate_parameters (loop, chrec2);
res = chrec_fold_plus (type, chrec1, chrec2);
@@ -1779,20 +1847,20 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt,
case POINTER_DIFF_EXPR:
{
tree utype = unsigned_type_for (type);
- chrec1 = analyze_scalar_evolution (loop, rhs1);
- chrec2 = analyze_scalar_evolution (loop, rhs2);
- chrec1 = chrec_convert (utype, chrec1, at_stmt);
- chrec2 = chrec_convert (utype, chrec2, at_stmt);
+ chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound);
+ chrec2 = analyze_scalar_evolution (loop, rhs2, nowrap_bound);
+ chrec1 = chrec_convert (utype, chrec1, at_stmt, nowrap_bound);
+ chrec2 = chrec_convert (utype, chrec2, at_stmt, nowrap_bound);
chrec1 = instantiate_parameters (loop, chrec1);
chrec2 = instantiate_parameters (loop, chrec2);
res = chrec_fold_minus (utype, chrec1, chrec2);
- res = chrec_convert (type, res, at_stmt);
+ res = chrec_convert (type, res, at_stmt, nowrap_bound);
break;
}
case PLUS_EXPR:
- chrec1 = analyze_scalar_evolution (loop, rhs1);
- chrec2 = analyze_scalar_evolution (loop, rhs2);
+ chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound);
+ chrec2 = analyze_scalar_evolution (loop, rhs2, nowrap_bound);
ctype = type;
/* When the stmt is conditionally executed re-write the CHREC
into a form that has well-defined behavior on overflow. */
@@ -1802,18 +1870,18 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt,
&& ! dominated_by_p (CDI_DOMINATORS, loop->latch,
gimple_bb (at_stmt)))
ctype = unsigned_type_for (type);
- chrec1 = chrec_convert (ctype, chrec1, at_stmt);
- chrec2 = chrec_convert (ctype, chrec2, at_stmt);
+ chrec1 = chrec_convert (ctype, chrec1, at_stmt, nowrap_bound);
+ chrec2 = chrec_convert (ctype, chrec2, at_stmt, nowrap_bound);
chrec1 = instantiate_parameters (loop, chrec1);
chrec2 = instantiate_parameters (loop, chrec2);
res = chrec_fold_plus (ctype, chrec1, chrec2);
if (type != ctype)
- res = chrec_convert (type, res, at_stmt);
+ res = chrec_convert (type, res, at_stmt, nowrap_bound);
break;
case MINUS_EXPR:
- chrec1 = analyze_scalar_evolution (loop, rhs1);
- chrec2 = analyze_scalar_evolution (loop, rhs2);
+ chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound);
+ chrec2 = analyze_scalar_evolution (loop, rhs2, nowrap_bound);
ctype = type;
/* When the stmt is conditionally executed re-write the CHREC
into a form that has well-defined behavior on overflow. */
@@ -1823,17 +1891,17 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt,
&& ! dominated_by_p (CDI_DOMINATORS,
loop->latch, gimple_bb (at_stmt)))
ctype = unsigned_type_for (type);
- chrec1 = chrec_convert (ctype, chrec1, at_stmt);
- chrec2 = chrec_convert (ctype, chrec2, at_stmt);
+ chrec1 = chrec_convert (ctype, chrec1, at_stmt, nowrap_bound);
+ chrec2 = chrec_convert (ctype, chrec2, at_stmt, nowrap_bound);
chrec1 = instantiate_parameters (loop, chrec1);
chrec2 = instantiate_parameters (loop, chrec2);
res = chrec_fold_minus (ctype, chrec1, chrec2);
if (type != ctype)
- res = chrec_convert (type, res, at_stmt);
+ res = chrec_convert (type, res, at_stmt, nowrap_bound);
break;
case NEGATE_EXPR:
- chrec1 = analyze_scalar_evolution (loop, rhs1);
+ chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound);
ctype = type;
/* When the stmt is conditionally executed re-write the CHREC
into a form that has well-defined behavior on overflow. */
@@ -1843,19 +1911,19 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt,
&& ! dominated_by_p (CDI_DOMINATORS,
loop->latch, gimple_bb (at_stmt)))
ctype = unsigned_type_for (type);
- chrec1 = chrec_convert (ctype, chrec1, at_stmt);
+ chrec1 = chrec_convert (ctype, chrec1, at_stmt, nowrap_bound);
/* TYPE may be integer, real or complex, so use fold_convert. */
chrec1 = instantiate_parameters (loop, chrec1);
res = chrec_fold_multiply (ctype, chrec1,
fold_convert (ctype, integer_minus_one_node));
if (type != ctype)
- res = chrec_convert (type, res, at_stmt);
+ res = chrec_convert (type, res, at_stmt, nowrap_bound);
break;
case BIT_NOT_EXPR:
/* Handle ~X as -1 - X. */
- chrec1 = analyze_scalar_evolution (loop, rhs1);
- chrec1 = chrec_convert (type, chrec1, at_stmt);
+ chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound);
+ chrec1 = chrec_convert (type, chrec1, at_stmt, nowrap_bound);
chrec1 = instantiate_parameters (loop, chrec1);
res = chrec_fold_minus (type,
fold_convert (type, integer_minus_one_node),
@@ -1863,8 +1931,8 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt,
break;
case MULT_EXPR:
- chrec1 = analyze_scalar_evolution (loop, rhs1);
- chrec2 = analyze_scalar_evolution (loop, rhs2);
+ chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound);
+ chrec2 = analyze_scalar_evolution (loop, rhs2, nowrap_bound);
ctype = type;
/* When the stmt is conditionally executed re-write the CHREC
into a form that has well-defined behavior on overflow. */
@@ -1874,29 +1942,29 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt,
&& ! dominated_by_p (CDI_DOMINATORS,
loop->latch, gimple_bb (at_stmt)))
ctype = unsigned_type_for (type);
- chrec1 = chrec_convert (ctype, chrec1, at_stmt);
- chrec2 = chrec_convert (ctype, chrec2, at_stmt);
+ chrec1 = chrec_convert (ctype, chrec1, at_stmt, nowrap_bound);
+ chrec2 = chrec_convert (ctype, chrec2, at_stmt, nowrap_bound);
chrec1 = instantiate_parameters (loop, chrec1);
chrec2 = instantiate_parameters (loop, chrec2);
res = chrec_fold_multiply (ctype, chrec1, chrec2);
if (type != ctype)
- res = chrec_convert (type, res, at_stmt);
+ res = chrec_convert (type, res, at_stmt, nowrap_bound);
break;
case LSHIFT_EXPR:
{
/* Handle A<<B as A * (1<<B). */
tree uns = unsigned_type_for (type);
- chrec1 = analyze_scalar_evolution (loop, rhs1);
- chrec2 = analyze_scalar_evolution (loop, rhs2);
- chrec1 = chrec_convert (uns, chrec1, at_stmt);
+ chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound);
+ chrec2 = analyze_scalar_evolution (loop, rhs2, nowrap_bound);
+ chrec1 = chrec_convert (uns, chrec1, at_stmt, nowrap_bound);
chrec1 = instantiate_parameters (loop, chrec1);
chrec2 = instantiate_parameters (loop, chrec2);
tree one = build_int_cst (uns, 1);
chrec2 = fold_build2 (LSHIFT_EXPR, uns, one, chrec2);
res = chrec_fold_multiply (uns, chrec1, chrec2);
- res = chrec_convert (type, res, at_stmt);
+ res = chrec_convert (type, res, at_stmt, nowrap_bound);
}
break;
@@ -1920,11 +1988,12 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt,
chrec1 = interpret_rhs_expr (loop, at_stmt, utype,
gimple_assign_rhs1 (def),
gimple_assign_rhs_code (def),
- gimple_assign_rhs2 (def));
+ gimple_assign_rhs2 (def),
+ nowrap_bound);
}
else
- chrec1 = analyze_scalar_evolution (loop, rhs1);
- res = chrec_convert (type, chrec1, at_stmt, true, rhs1);
+ chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound);
+ res = chrec_convert (type, chrec1, at_stmt, nowrap_bound, true, rhs1);
break;
case BIT_AND_EXPR:
@@ -1949,9 +2018,11 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt,
if (TYPE_PRECISION (utype) < TYPE_PRECISION (TREE_TYPE (rhs1)))
{
- chrec1 = analyze_scalar_evolution (loop, rhs1);
- chrec1 = chrec_convert (utype, chrec1, at_stmt);
- res = chrec_convert (TREE_TYPE (rhs1), chrec1, at_stmt);
+ chrec1 = analyze_scalar_evolution (loop, rhs1, nowrap_bound);
+ chrec1 = chrec_convert (utype, chrec1, at_stmt,
+ nowrap_bound);
+ res = chrec_convert (TREE_TYPE (rhs1), chrec1, at_stmt,
+ nowrap_bound);
}
}
}
@@ -1968,7 +2039,8 @@ interpret_rhs_expr (class loop *loop, gimple *at_stmt,
/* Interpret the expression EXPR. */
static tree
-interpret_expr (class loop *loop, gimple *at_stmt, tree expr)
+interpret_expr (class loop *loop, gimple *at_stmt, tree expr,
+ tree *nowrap_bound)
{
enum tree_code code;
tree type = TREE_TYPE (expr), op0, op1;
@@ -1984,20 +2056,20 @@ interpret_expr (class loop *loop, gimple *at_stmt, tree
expr)
extract_ops_from_tree (expr, &code, &op0, &op1);
return interpret_rhs_expr (loop, at_stmt, type,
- op0, code, op1);
+ op0, code, op1, nowrap_bound);
}
/* Interpret the rhs of the assignment STMT. */
static tree
-interpret_gimple_assign (class loop *loop, gimple *stmt)
+interpret_gimple_assign (class loop *loop, gimple *stmt, tree *nowrap_bound)
{
tree type = TREE_TYPE (gimple_assign_lhs (stmt));
enum tree_code code = gimple_assign_rhs_code (stmt);
return interpret_rhs_expr (loop, stmt, type,
gimple_assign_rhs1 (stmt), code,
- gimple_assign_rhs2 (stmt));
+ gimple_assign_rhs2 (stmt), nowrap_bound);
}
@@ -2011,7 +2083,7 @@ interpret_gimple_assign (class loop *loop, gimple *stmt)
/* Helper recursive function. */
static tree
-analyze_scalar_evolution_1 (class loop *loop, tree var)
+analyze_scalar_evolution_1 (class loop *loop, tree var, tree *nowrap_bound)
{
gimple *def;
basic_block bb;
@@ -2019,7 +2091,12 @@ analyze_scalar_evolution_1 (class loop *loop, tree var)
tree res;
if (TREE_CODE (var) != SSA_NAME)
- return interpret_expr (loop, NULL, var);
+ return interpret_expr (loop, NULL, var, nowrap_bound);
+
+ tree local_nowrap_bound = NULL_TREE;
+ tree *bound = nullptr;
+ if (nowrap_bound)
+ bound = &local_nowrap_bound;
def = SSA_NAME_DEF_STMT (var);
bb = gimple_bb (def);
@@ -2034,26 +2111,26 @@ analyze_scalar_evolution_1 (class loop *loop, tree var)
if (loop != def_loop)
{
- res = analyze_scalar_evolution_1 (def_loop, var);
+ res = analyze_scalar_evolution_1 (def_loop, var, bound);
class loop *loop_to_skip = superloop_at_depth (def_loop,
loop_depth (loop) + 1);
res = compute_overall_effect_of_inner_loop (loop_to_skip, res);
if (chrec_contains_symbols_defined_in_loop (res, loop->num))
- res = analyze_scalar_evolution_1 (loop, res);
+ res = analyze_scalar_evolution_1 (loop, res, bound);
goto set_and_end;
}
switch (gimple_code (def))
{
case GIMPLE_ASSIGN:
- res = interpret_gimple_assign (loop, def);
+ res = interpret_gimple_assign (loop, def, bound);
break;
case GIMPLE_PHI:
if (loop_phi_node_p (def))
- res = interpret_loop_phi (loop, as_a <gphi *> (def));
+ res = interpret_loop_phi (loop, as_a <gphi *> (def), bound);
else
- res = interpret_condition_phi (loop, as_a <gphi *> (def));
+ res = interpret_condition_phi (loop, as_a <gphi *> (def), bound);
break;
default:
@@ -2068,7 +2145,9 @@ analyze_scalar_evolution_1 (class loop *loop, tree var)
res = var;
if (loop == def_loop)
- set_scalar_evolution (block_before_loop (loop), var, res);
+ set_scalar_evolution (block_before_loop (loop), var, res, bound);
+
+ scev_add_nowrap_bound (nowrap_bound, local_nowrap_bound);
return res;
}
@@ -2087,7 +2166,7 @@ analyze_scalar_evolution_1 (class loop *loop, tree var)
*/
tree
-analyze_scalar_evolution (class loop *loop, tree var)
+analyze_scalar_evolution (class loop *loop, tree var, tree *nowrap_bound)
{
tree res;
@@ -2104,7 +2183,7 @@ analyze_scalar_evolution (class loop *loop, tree var)
fprintf (dump_file, ")\n");
}
- res = get_scalar_evolution (block_before_loop (loop), var);
+ res = get_scalar_evolution (block_before_loop (loop), var, nowrap_bound);
if (res == chrec_not_analyzed_yet)
{
/* We'll recurse into instantiate_scev, avoid tearing down the
@@ -2115,7 +2194,7 @@ analyze_scalar_evolution (class loop *loop, tree var)
global_cache = new instantiate_cache_type;
destr = true;
}
- res = analyze_scalar_evolution_1 (loop, var);
+ res = analyze_scalar_evolution_1 (loop, var, nowrap_bound);
if (destr)
{
delete global_cache;
@@ -2156,9 +2235,11 @@ bool nonwrapping_chrec_p (tree chrec)
/* Analyzes and returns the scalar evolution of VAR address in LOOP. */
static tree
-analyze_scalar_evolution_for_address_of (class loop *loop, tree var)
+analyze_scalar_evolution_for_address_of (class loop *loop, tree var,
+ tree *nowrap_bound)
{
- return analyze_scalar_evolution (loop, build_fold_addr_expr (var));
+ return analyze_scalar_evolution (loop, build_fold_addr_expr (var),
+ nowrap_bound);
}
/* Analyze scalar evolution of use of VERSION in USE_LOOP with respect to
@@ -2213,7 +2294,8 @@ analyze_scalar_evolution_for_address_of (class loop
*loop, tree var)
static tree
analyze_scalar_evolution_in_loop (class loop *wrto_loop, class loop *use_loop,
- tree version, bool *folded_casts)
+ tree version, bool *folded_casts,
+ tree *nowrap_bound = nullptr)
{
bool val = false;
tree ev = version, tmp;
@@ -2241,7 +2323,7 @@ analyze_scalar_evolution_in_loop (class loop *wrto_loop,
class loop *use_loop,
*folded_casts = false;
while (1)
{
- tmp = analyze_scalar_evolution (use_loop, ev);
+ tmp = analyze_scalar_evolution (use_loop, ev, nowrap_bound);
ev = resolve_mixers (use_loop, tmp, folded_casts);
if (use_loop == wrto_loop)
@@ -3280,12 +3362,17 @@ derive_simple_iv_with_niters (tree ev, tree *niters)
The derived condition normally is the maximum number the inner iv can
iterate, and will be stored in IV_NITERS. This is useful in loop niter
analysis, to derive break conditions when a loop must terminate, when is
- infinite. */
+ infinite.
+
+ If ALLOW_WRAPPING is true, let scev analysis continue rather than stop if
+ an IV might wrap. Store the bound under which no wrapping occurs in IV's
+ nowrap_bound. */
bool
simple_iv_with_niters (class loop *wrto_loop, class loop *use_loop,
tree op, affine_iv *iv, tree *iv_niters,
- bool allow_nonconstant_step)
+ bool allow_nonconstant_step,
+ bool allow_wrapping)
{
enum tree_code code;
tree type, ev, base, e;
@@ -3295,14 +3382,23 @@ simple_iv_with_niters (class loop *wrto_loop, class
loop *use_loop,
iv->base = NULL_TREE;
iv->step = NULL_TREE;
iv->no_overflow = false;
+ iv->nowrap_bound = NULL_TREE;
type = TREE_TYPE (op);
if (!POINTER_TYPE_P (type)
&& !INTEGRAL_TYPE_P (type))
return false;
+ tree nowrap_bound = NULL_TREE;
ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
- &folded_casts);
+ &folded_casts,
+ allow_wrapping ? &nowrap_bound
+ : nullptr);
+
+ /* If there was a nontrivial nowrap bound, add it to the IV. */
+ if (allow_wrapping && nowrap_bound)
+ iv->nowrap_bound = nowrap_bound;
+
if (chrec_contains_undetermined (ev)
|| chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
return false;
@@ -3429,10 +3525,12 @@ simple_iv_with_niters (class loop *wrto_loop, class
loop *use_loop,
bool
simple_iv (class loop *wrto_loop, class loop *use_loop, tree op,
- affine_iv *iv, bool allow_nonconstant_step)
+ affine_iv *iv, bool allow_nonconstant_step,
+ bool allow_wrapping)
{
return simple_iv_with_niters (wrto_loop, use_loop, op, iv,
- NULL, allow_nonconstant_step);
+ NULL, allow_nonconstant_step,
+ allow_wrapping);
}
/* Finalize the scalar evolution analysis. */
diff --git a/gcc/tree-scalar-evolution.h b/gcc/tree-scalar-evolution.h
index 0c15956de3f..4f94cf7baa0 100644
--- a/gcc/tree-scalar-evolution.h
+++ b/gcc/tree-scalar-evolution.h
@@ -30,7 +30,7 @@ extern bool scev_initialized_p (void);
extern void scev_reset (void);
extern void scev_reset_htab (void);
extern void scev_finalize (void);
-extern tree analyze_scalar_evolution (class loop *, tree);
+extern tree analyze_scalar_evolution (class loop *, tree, tree * = nullptr);
extern tree instantiate_scev (edge, class loop *, tree);
extern tree resolve_mixers (class loop *, tree, bool *);
extern void gather_stats_on_scev_database (void);
@@ -38,14 +38,17 @@ extern bool final_value_replacement_loop (class loop *);
extern unsigned int scev_const_prop (void);
extern bool expression_expensive_p (tree, bool *);
extern bool simple_iv_with_niters (class loop *, class loop *, tree,
- struct affine_iv *, tree *, bool);
+ struct affine_iv *, tree *, bool,
+ bool = false);
extern bool simple_iv (class loop *, class loop *, tree, struct affine_iv *,
- bool);
+ bool, bool = false);
extern bool iv_can_overflow_p (class loop *, tree, tree, tree);
extern tree compute_overall_effect_of_inner_loop (class loop *, tree);
extern void record_nonwrapping_chrec (tree);
extern bool nonwrapping_chrec_p (tree);
+extern void scev_add_nowrap_bound (tree *, tree);
+
/* Returns the basic block preceding LOOP, or the CFG entry block when
the loop is function's body. */
diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc
index fe179b69b05..a4630c8a0a1 100644
--- a/gcc/tree-ssa-loop-niter.cc
+++ b/gcc/tree-ssa-loop-niter.cc
@@ -5604,12 +5604,16 @@ scev_var_range_cant_overflow (tree var, tree step,
class loop *loop)
arithmetics in C does not overflow).
If VAR is a ssa variable, this function also returns false if VAR can
- be proven not overflow with value range info. */
+ be proven not overflow with value range info.
+
+ If NOWRAP_BOUND is nonzero and we can't prove it differently, get
+ STEP's type bound, build a bound MIN (NOWRAP_BOUND, STEP_TYPE_BOUND)
+ and store it in NOWRAP_BOUND. */
bool
scev_probably_wraps_p (tree var, tree base, tree step,
gimple *at_stmt, class loop *loop,
- bool use_overflow_semantics)
+ bool use_overflow_semantics, tree *nowrap_bound)
{
/* FIXME: We really need something like
http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html.
@@ -5657,6 +5661,14 @@ scev_probably_wraps_p (tree var, tree base, tree step,
if (var && nonwrapping_chrec_p (analyze_scalar_evolution (loop, var)))
return false;
+ /* If we can use a bound to guarantee no wrapping, save it. */
+ if (nowrap_bound)
+ {
+ tree b = get_niter_type_bound (TREE_TYPE (step), base, step);
+ scev_add_nowrap_bound (nowrap_bound, b);
+ return false;
+ }
+
/* At this point we still don't have a proof that the iv does not
overflow: give up. */
return true;
diff --git a/gcc/tree-ssa-loop-niter.h b/gcc/tree-ssa-loop-niter.h
index 24e458f08db..c789ec524f9 100644
--- a/gcc/tree-ssa-loop-niter.h
+++ b/gcc/tree-ssa-loop-niter.h
@@ -54,7 +54,7 @@ extern bool stmt_dominates_stmt_p (gimple *, gimple *);
extern bool nowrap_type_p (tree);
extern tree get_niter_type_bound (tree, tree, tree);
extern bool scev_probably_wraps_p (tree, tree, tree, gimple *,
- class loop *, bool);
+ class loop *, bool, tree * = nullptr);
extern void free_numbers_of_iterations_estimates (class loop *);
extern void free_numbers_of_iterations_estimates (function *);
extern tree simplify_replace_tree (tree, tree,
diff --git a/gcc/tree-ssa-loop.h b/gcc/tree-ssa-loop.h
index 73796a2732b..de8f9c69dac 100644
--- a/gcc/tree-ssa-loop.h
+++ b/gcc/tree-ssa-loop.h
@@ -30,6 +30,10 @@ struct affine_iv
/* True if this iv does not overflow. */
bool no_overflow;
+
+ /* Upper bound for the number of loop iterations for which this IV
+ does not wrap. */
+ tree nowrap_bound;
};
/* Description of number of iterations of a loop. All the expressions inside
--
2.54.0
