On Fri, Jul 10, 2026 at 6:13 PM Robin Dapp <[email protected]> wrote:
>
> 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.
Thanks for working on this.
I wonder how to deal with the situation
where CHREC_RIGHT changes? Whenever we call chrec_fold_plus
with CHRECs of the same loop we get { a + b, step_a + step_b }_loop
which will invalidate nowrap bounds?
Likewise if you start with
{ init, +, 1 }_0 and a bound of N, adding 5 requires to adjust N?
So even changing CHREC_LEFT is problematic.
Should nowrap_bound be part of a CHREC itself? I see no particular
way to perform the nowrap_bound adjustment in chrec_fold_plus,
but I have to admit I haven't thought about this for too long. At least
it would give us the chance to drop to chrec_dont_know.
But maybe I'm missing something?
Thanks,
Richard.
> 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
>
