https://gcc.gnu.org/g:afa2c7515d19b01a63bf0bca9a77ea9d55e556a1
commit r17-4249-gafa2c7515d19b01a63bf0bca9a77ea9d55e556a1 Author: Richard Biener <[email protected]> Date: Wed Sep 2 13:48:33 2026 +0200 ivopts: fix the bound when eliminating an IV with a LT comparison 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]> 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. Diff: --- 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(-) 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 000000000000..6446d32c039c --- /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 000000000000..0d93be206d78 --- /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 be325775fbb7..4d244ddadea3 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 8d2b9d39355c..2ee43d125675 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 5a4254290d8e..fa3c2c136fc0 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; }
