On Wed, 2 Sep 2026, Richard Biener wrote:
> iv_elimination_compare_lt turns a loop with the exit test i < b, entered
> with i = a and a pointer p = base + a stepping in lockstep with i, into a
> loop with the exit test p < p_0 - a + b, so as to eliminate the counter.
>
> This is unsound in two ways when the loop may roll zero times, i.e. when
> the number of iterations is a + 1 > b ? 0 : b - a - 1.
>
> The first one is that the bound is not recomputed by the function, but
> taken from cand_value_at, which evaluates the candidate at the number of
> iterations, i.e. computes p_0 + (b - a - 1 + 1) with b - a computed in the
> type of the number of iterations. If that type is narrower than the type
> of the offsets, converting the difference is not value preserving when the
> loop rolls zero times, since b - a is negative there. For example, with
>
> void f (char *p, unsigned int i, unsigned int n)
> { p += i; do { *p = 1; p += 1; i++; } while (i < n); }
>
> called as f (p, 2, 0), the bound is computed as p_0 + (sizetype) 0xfffffffd
> and the loop walks 4G bytes forward instead of exiting at the first test.
>
> The second one is that the comparison of the pointers is performed modulo
> the size of the address space, so replacing i < b by p_0 - a + i < p_0 - a
> + b requires the addition of p_0 - a to be order preserving on the values
> of i and b. That does not hold when the offsets are as wide as a pointer
> and either of them is large, e.g. for
>
> void f (char *p, uintptr_t i, uintptr_t n)
> { p += i; do { *p = 1; p += 1; i++; } while (i < n); }
>
> called as f (a + 2, -2, 8): the bound p_0 - a + b wraps around to the very
> end of the address space, the test holds and the loop again runs away.
>
> So recompute the bound as base + step * b - step * a, converting a and b to
> the offset type separately, and require the may_be_zero comparison to be an
> unsigned one and both scaled offsets to be provably non-negative and free of
> overflow. Since the recomputed bound is the value of the candidate after
> the last iteration, also require the exit test to come after the increment
> of the candidate. Finally, move the expression_expensive_p check on the
> bound after the call so that it applies to the recomputed bound.
>
> Assisted-by: Claude Opus 5 <[email protected]>
>
> Bootstrapped and tested on x86_64-unknown-linux-gnu.
>
> Instead of removing iv_elimination_compare_lt alltogether as suggested
> after my 2nd attempt of deciphering it a few months ago this is what
> I arrived at with some LLM help and back-and-forth.
>
> OK? Otherwise I'll proceed with purging the whole thing, the
> restriction on integer-width < pointer-width makes it less useful,
> esp. on 32bit archs.
I have re-tested this on x86_64-unknwon-linux-gnu and plan to push
this tomorrow.
Thanks,
Richard.
> Thanks,
> Richard.
>
> PR tree-optimization/113703
> * tree-ssa-loop-ivopts.cc: Include gimple-range.h.
> (nonneg_scaled_offset_p): New function.
> (iv_elimination_compare_lt): Add USE and BOUND_P parameters. Bail
> out if the exit test does not come after the increment of the
> candidate, if the comparison in the number of iterations is signed
> or if the offsets are not known to be non-negative and to not
> overflow. Recompute the bound and store it in BOUND_P.
> (may_eliminate_iv): Adjust the call to iv_elimination_compare_lt
> and move the expensiveness check on the bound after it.
>
> * gcc.dg/tree-ssa/ivopts-lt.c: Use unsigned int counters,
> restrict to lp64.
> * gcc.dg/tree-ssa/ivopts-lt-2.c: Restrict to lp64.
> * gcc.dg/torture/pr113703-1.c: New test.
> * gcc.dg/torture/pr113703-2.c: New test.
> ---
> gcc/testsuite/gcc.dg/torture/pr113703-1.c | 34 ++++++
> gcc/testsuite/gcc.dg/torture/pr113703-2.c | 37 ++++++
> gcc/testsuite/gcc.dg/tree-ssa/ivopts-lt-2.c | 2 +-
> gcc/testsuite/gcc.dg/tree-ssa/ivopts-lt.c | 10 +-
> gcc/tree-ssa-loop-ivopts.cc | 118 ++++++++++++++++----
> 5 files changed, 173 insertions(+), 28 deletions(-)
> create mode 100644 gcc/testsuite/gcc.dg/torture/pr113703-1.c
> create mode 100644 gcc/testsuite/gcc.dg/torture/pr113703-2.c
>
> diff --git a/gcc/testsuite/gcc.dg/torture/pr113703-1.c
> b/gcc/testsuite/gcc.dg/torture/pr113703-1.c
> new file mode 100644
> index 00000000000..6446d32c039
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/torture/pr113703-1.c
> @@ -0,0 +1,34 @@
> +/* { dg-do run } */
> +/* { dg-additional-options "-fno-tree-vectorize
> -fno-tree-loop-distribute-patterns" } */
> +
> +#include <stdint.h>
> +
> +char a[16];
> +
> +__attribute__((noipa)) void
> +f (char *p, uintptr_t i, uintptr_t n)
> +{
> + p += i;
> + do
> + {
> + *p = 1;
> + p += 1;
> + i++;
> + }
> + while (i < n);
> +}
> +
> +int
> +main ()
> +{
> + /* I is -2 and thus not less than N, so the loop stores to A[0] only.
> + IVOPTs used to replace the exit test by P < (A + 2) + N, which does
> + not hold at the first test and makes the loop iterate on. */
> + f (a + 2, -2, 8);
> + if (a[0] != 1)
> + __builtin_abort ();
> + for (int j = 1; j < 16; j++)
> + if (a[j] != 0)
> + __builtin_abort ();
> + return 0;
> +}
> diff --git a/gcc/testsuite/gcc.dg/torture/pr113703-2.c
> b/gcc/testsuite/gcc.dg/torture/pr113703-2.c
> new file mode 100644
> index 00000000000..0d93be206d7
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/torture/pr113703-2.c
> @@ -0,0 +1,37 @@
> +/* { dg-do run { target *-*-linux* *-*-gnu* *-*-uclinux* } } */
> +/* { dg-additional-options "-fno-tree-vectorize
> -fno-tree-loop-distribute-patterns" } */
> +
> +#include <sys/mman.h>
> +#include <unistd.h>
> +
> +__attribute__((noipa)) void
> +f (char *p, unsigned int i, unsigned int n)
> +{
> + p += i;
> + do
> + {
> + *p = 1;
> + p += 1;
> + i++;
> + }
> + while (i < n);
> +}
> +
> +int
> +main ()
> +{
> + long pgsz = sysconf (_SC_PAGESIZE);
> + char *p = mmap (NULL, pgsz * 2, PROT_READ | PROT_WRITE,
> + MAP_ANONYMOUS | MAP_PRIVATE, 0, 0);
> + if (p == MAP_FAILED)
> + return 0;
> + mprotect (p + pgsz, pgsz, PROT_NONE);
> + /* I + 1 is not less than N, so the loop stores to P[4] only. IVOPTs
> + used to compute the bound of the transformed loop from the number of
> + iterations N - I - 1, which is (unsigned int) -3 here and gets zero
> + extended, so that the loop ran into the protected page. */
> + f (p + 2, 2, 0);
> + if (p[4] != 1 || p[5] != 0)
> + __builtin_abort ();
> + return 0;
> +}
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ivopts-lt-2.c
> b/gcc/testsuite/gcc.dg/tree-ssa/ivopts-lt-2.c
> index be325775fbb..4d244ddadea 100644
> --- a/gcc/testsuite/gcc.dg/tree-ssa/ivopts-lt-2.c
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ivopts-lt-2.c
> @@ -1,4 +1,4 @@
> -/* { dg-do compile } */
> +/* { dg-do compile { target lp64 } } */
> /* { dg-options "-O2 -fno-tree-vectorize -fno-tree-loop-distribute-patterns
> -fdump-tree-ivopts" } */
> /* { dg-skip-if "PR68644" { hppa*-*-* powerpc*-*-* } } */
>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ivopts-lt.c
> b/gcc/testsuite/gcc.dg/tree-ssa/ivopts-lt.c
> index 8d2b9d39355..2ee43d12567 100644
> --- a/gcc/testsuite/gcc.dg/tree-ssa/ivopts-lt.c
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ivopts-lt.c
> @@ -1,11 +1,13 @@
> -/* { dg-do compile } */
> +/* { dg-do compile { target lp64 } } */
> /* { dg-options "-O2 -fno-tree-vectorize -fno-tree-loop-distribute-patterns
> -fdump-tree-ivopts" } */
> -/* { dg-require-effective-target stdint_types } */
>
> -#include "stdint.h"
> +/* The counter can be eliminated in favour of P, since the offsets I and N
> + are known to be non-negative and small enough not to overflow. Note that
> + this is not the case for offsets of the width of a pointer, see
> + gcc.dg/torture/ivopts-lt-1.c. */
>
> void
> -f1 (char *p, uintptr_t i, uintptr_t n)
> +f1 (char *p, unsigned int i, unsigned int n)
> {
> p += i;
> do
> diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc
> index 5a4254290d8..fa3c2c136fc 100644
> --- a/gcc/tree-ssa-loop-ivopts.cc
> +++ b/gcc/tree-ssa-loop-ivopts.cc
> @@ -133,6 +133,7 @@ along with GCC; see the file COPYING3. If not see
> #include "dbgcnt.h"
> #include "cfganal.h"
> #include "gimple-fold.h"
> +#include "gimple-range.h"
>
> /* For lang_hooks.types.type_for_mode. */
> #include "langhooks.h"
> @@ -5234,14 +5235,40 @@ difference_cannot_overflow_p (struct ivopts_data
> *data, tree base, tree offset)
> }
> }
>
> +/* Return true if STEP * VAL, computed in OFF_TYPE, is known to be a
> + non-negative offset which does not overflow, i.e. if the value of VAL is
> + non-negative and multiplying it by STEP fits in the signed range of
> + OFF_TYPE. */
> +
> +static bool
> +nonneg_scaled_offset_p (tree val, HOST_WIDE_INT step, tree off_type)
> +{
> + if (!INTEGRAL_TYPE_P (TREE_TYPE (val)) || step == 0)
> + return false;
> +
> + signop sgn = TYPE_SIGN (TREE_TYPE (val));
> + int_range_max r;
> + if (!get_range_query (cfun)->range_of_expr (r, val)
> + || r.undefined_p ()
> + || wi::neg_p (r.lower_bound (), sgn))
> + return false;
> +
> + widest_int max = widest_int::from (r.upper_bound (), sgn);
> + widest_int limit
> + = widest_int::from (wi::max_value (TYPE_PRECISION (off_type), SIGNED),
> + SIGNED);
> + return wi::leu_p (max, wi::udiv_trunc (limit, absu_hwi (step)));
> +}
> +
> /* Tries to replace loop exit by one formulated in terms of a LT_EXPR
> comparison with CAND. NITER describes the number of iterations of
> - the loops. If successful, the comparison in COMP_P is altered
> accordingly.
> + the loops. If successful, the comparison in COMP_P is altered accordingly
> + and the bound in BOUND_P is recomputed.
>
> We aim to handle the following situation:
>
> sometype *base, *p;
> - int a, b, i;
> + unsigned a, b, i;
>
> i = a;
> p = p_0 = base + a;
> @@ -5265,20 +5292,32 @@ difference_cannot_overflow_p (struct ivopts_data
> *data, tree base, tree offset)
> }
> while (p < p_0 - a + b);
>
> - This preserves the correctness, since the pointer arithmetics does not
> - overflow. More precisely:
> + Note that the bound has to be computed as p_0 - a + b and not from the
> + number of iterations as p_0 + (b - a): the latter is only equivalent if
> + b - a does not wrap, which is not the case when the loop rolls zero times.
> +
> + For this to preserve correctness, we need to know that the values compared
> + in the transformed loop are ordered the same way as i and b are. Since
> the
> + comparison of the pointers is performed modulo the size of the address
> + space, this needs a + 1 > b to be an unsigned comparison, and the offsets
> + a and b scaled by the step of the candidate to be non-negative and to not
> + overflow. Then:
>
> 1) if a + 1 <= b, then p_0 - a + b is the final value of p, hence there
> is no
> - overflow in computing it or the values of p.
> - 2) if a + 1 > b, then we need to verify that the expression p_0 - a does
> not
> - overflow. To prove this, we use the fact that p_0 = base + a. */
> + overflow in computing it or the values of p, and the pointers increase
> + monotonically together with i.
> + 2) if a + 1 > b, then the loop exits at the first test, and b <= a implies
> + that p_0 - a + b lies between the valid addresses p_0 - a and p_0, so
> + the test indeed fails. Here we also need to verify that the expression
> + p_0 - a does not overflow, which we prove using p_0 = base + a. */
>
> static bool
> -iv_elimination_compare_lt (struct ivopts_data *data,
> +iv_elimination_compare_lt (struct ivopts_data *data, struct iv_use *use,
> struct iv_cand *cand, enum tree_code *comp_p,
> - class tree_niter_desc *niter)
> + class tree_niter_desc *niter, tree *bound_p)
> {
> - tree cand_type, a, b, mbz, nit_type = TREE_TYPE (niter->niter), offset;
> + tree cand_type, a, b, mbz, nit_type = TREE_TYPE (niter->niter);
> + tree off_type, offset, bound;
> class aff_tree nit, tmpa, tmpb;
> enum tree_code comp;
> HOST_WIDE_INT step;
> @@ -5303,6 +5342,11 @@ iv_elimination_compare_lt (struct ivopts_data *data,
> return false;
> step = int_cst_value (cand->iv->step);
>
> + /* The bound we compute below is the value the candidate has after the last
> + iteration, so the exit test has to see the incremented candidate. */
> + if (!stmt_after_increment (data->current_loop, cand, use->stmt))
> + return false;
> +
> /* Check that the number of iterations matches the expected pattern:
> a + 1 > b ? 0 : b - a - 1. */
> mbz = niter->may_be_zero;
> @@ -5346,14 +5390,25 @@ iv_elimination_compare_lt (struct ivopts_data *data,
> if (tmpb.n != 0 || maybe_ne (tmpb.offset, 1))
> return false;
>
> - /* Finally, check that CAND->IV->BASE - CAND->IV->STEP * A does not
> - overflow. */
> - offset = fold_build2 (MULT_EXPR, TREE_TYPE (cand->iv->step),
> - cand->iv->step,
> - fold_convert (TREE_TYPE (cand->iv->step), a));
> + /* The comparison A + 1 > B only tells us that B is at most A if it is
> + an unsigned one; otherwise B may well be negative. */
> + if (!TYPE_UNSIGNED (TREE_TYPE (a)))
> + return false;
> +
> + /* Check that CAND->IV->BASE - CAND->IV->STEP * A does not overflow. */
> + off_type = TREE_TYPE (cand->iv->step);
> + offset = fold_build2 (MULT_EXPR, off_type, cand->iv->step,
> + fold_convert (off_type, a));
> if (!difference_cannot_overflow_p (data, cand->iv->base, offset))
> return false;
>
> + /* The candidate is compared as an unsigned quantity, so the offsets by
> + which A and B move it away from CAND->IV->BASE - CAND->IV->STEP * A have
> + to be ordered the same way as A and B themselves. */
> + if (!nonneg_scaled_offset_p (a, step, off_type)
> + || !nonneg_scaled_offset_p (b, step, off_type))
> + return false;
> +
> /* Determine the new comparison operator. */
> comp = step < 0 ? GT_EXPR : LT_EXPR;
> if (*comp_p == NE_EXPR)
> @@ -5363,6 +5418,22 @@ iv_elimination_compare_lt (struct ivopts_data *data,
> else
> gcc_unreachable ();
>
> + /* Recompute the bound as CAND->IV->BASE - CAND->IV->STEP * A
> + + CAND->IV->STEP * B. Deriving it from the number of iterations, as
> + cand_value_at does, is not correct here: B - A is computed in NIT_TYPE
> + and converting it to OFF_TYPE is not value preserving when the loop
> + rolls zero times and B - A is thus negative. */
> + bound = fold_build2 (MINUS_EXPR, off_type,
> + fold_build2 (MULT_EXPR, off_type, cand->iv->step,
> + fold_convert (off_type, b)),
> + offset);
> + cand_type = TREE_TYPE (cand->iv->base);
> + if (POINTER_TYPE_P (cand_type))
> + *bound_p = fold_build_pointer_plus (cand->iv->base, bound);
> + else
> + *bound_p = fold_build2 (PLUS_EXPR, cand_type, cand->iv->base,
> + fold_convert (cand_type, bound));
> +
> return true;
> }
>
> @@ -5472,12 +5543,6 @@ may_eliminate_iv (struct ivopts_data *data,
> aff_combination_to_tree (&bnd));
> *comp = iv_elimination_compare (data, use);
>
> - /* It is unlikely that computing the number of iterations using division
> - would be more profitable than keeping the original induction variable.
> */
> - bool cond_overflow_p;
> - if (expression_expensive_p (*bound, &cond_overflow_p))
> - return false;
> -
> /* Sometimes, it is possible to handle the situation that the number of
> iterations may be zero unless additional assumptions by using <
> instead of != in the exit condition.
> @@ -5485,8 +5550,15 @@ may_eliminate_iv (struct ivopts_data *data,
> TODO: we could also calculate the value MAY_BE_ZERO ? 0 : NITER and
> base the exit condition on it. However, that is often too
> expensive. */
> - if (!integer_zerop (desc->may_be_zero))
> - return iv_elimination_compare_lt (data, cand, comp, desc);
> + if (!integer_zerop (desc->may_be_zero)
> + && !iv_elimination_compare_lt (data, use, cand, comp, desc, bound))
> + return false;
> +
> + /* It is unlikely that computing the number of iterations using division
> + would be more profitable than keeping the original induction variable.
> */
> + bool cond_overflow_p;
> + if (expression_expensive_p (*bound, &cond_overflow_p))
> + return false;
>
> return true;
> }
>
--
Richard Biener <[email protected]>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Stefan Gaiser, Jochen Jaser, Abhinav Puri; (HRB 36809, AG Nuernberg)
