https://gcc.gnu.org/g:471022256e4705314aedf21c53bc351ece88ff43
commit r17-4520-g471022256e4705314aedf21c53bc351ece88ff43 Author: Richard Biener <[email protected]> Date: Mon Sep 21 12:15:02 2026 +0200 tree-optimization/127515 - ivopts: fix bound when counter wraps on first increment 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. The number of iterations of the loop is (a + 1 > b) ? 0 : b - a - 1 and the fix for PR tree-optimization/113703 made sure that the bound is not derived from it, since converting b - a to the type of the offsets is not value preserving when the loop rolls zero times and b - a is negative. But the reasoning also assumes that a + 1 does not wrap around in the type of a, which need not be the case: if a is the maximum value of its type, then a + 1 is zero, a + 1 > b is false whatever b is, so the loop rolls and its number of iterations is b, whereas b - a computed on the offsets is b - a and not b + 1. 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, -1, 1), the loop iterates twice but the bound is computed as p_0 + ((sizetype) 0xffffffff - (sizetype) 1), i.e. p_0 + 0xfffffffe instead of p_0 - 2, so the loop exits at the first test. So build the bound out of a + 1 and b + 1 instead of a and b, converting a + 1 to the type of the offsets as a whole instead of rewriting it into a and 1, and computing b + 1 in the type of the offsets, where it cannot wrap around. The difference of the two offsets is then the number of iterations of the loop in the wrapping case too, since a + 1 is zero there. Require the new pair of offsets to be non-negative and to not overflow as well. Co-Authored-By: Claude Opus 5 <[email protected]> PR tree-optimization/113703 PR tree-optimization/127515 * tree-ssa-loop-ivopts.cc (iv_elimination_compare_lt): Also record A + 1 when matching the number of iterations. Convert it to OFF_TYPE as a whole, compute B + 1 in OFF_TYPE and require both to be non-negative scaled offsets that do not overflow. Build the bound out of them instead of A and B. * gcc.dg/torture/pr113703-5.c: New test. * gcc.dg/torture/pr113703-6.c: New test. Diff: --- gcc/testsuite/gcc.dg/torture/pr113703-5.c | 34 ++++++++++++++++ gcc/testsuite/gcc.dg/torture/pr113703-6.c | 33 ++++++++++++++++ gcc/tree-ssa-loop-ivopts.cc | 64 +++++++++++++++++++++---------- 3 files changed, 110 insertions(+), 21 deletions(-) diff --git a/gcc/testsuite/gcc.dg/torture/pr113703-5.c b/gcc/testsuite/gcc.dg/torture/pr113703-5.c new file mode 100644 index 000000000000..bb63c0f69e94 --- /dev/null +++ b/gcc/testsuite/gcc.dg/torture/pr113703-5.c @@ -0,0 +1,34 @@ +/* { dg-do run { target lp64 } } */ +/* { dg-additional-options "-fno-tree-vectorize -fno-tree-loop-distribute-patterns" } */ + +#include <stdint.h> + +uintptr_t sum = 0; + +__attribute__((noipa)) void +f (char *p, unsigned int i, unsigned int n) +{ + p -= i; + do + { + sum += (uintptr_t)p; + p -= 1; + i++; + } + while (i < n); +} + +int +main () +{ + /* The number of iterations of the loop is (i + 1 > n) ? 0 : n - i - 1. + I is -1, so i + 1 wraps around to 0 and is not greater than N, and the + loop iterates twice. IVOPTs used to replace the exit test by one on P + with the bound P_0 + ((sizetype) i - (sizetype) n), i.e. P_0 + 0xfffffffe + instead of P_0 - 2, and the loop ran away. */ + f ((char *)0x10000ffffffff, -1, 1); + /* SUM is 0x10000000000 + 0xfffffffffff. */ + if (sum != (uintptr_t)0x1ffffffffffff) + __builtin_abort (); + return 0; +} diff --git a/gcc/testsuite/gcc.dg/torture/pr113703-6.c b/gcc/testsuite/gcc.dg/torture/pr113703-6.c new file mode 100644 index 000000000000..de6f228eda3a --- /dev/null +++ b/gcc/testsuite/gcc.dg/torture/pr113703-6.c @@ -0,0 +1,33 @@ +/* { dg-do run { target lp64 } } */ +/* { dg-additional-options "-fno-tree-vectorize -fno-tree-loop-distribute-patterns" } */ + +#include <stdint.h> + +uintptr_t sum = 0; + +__attribute__((noipa)) void +f (char *p, unsigned int i, unsigned int n) +{ + p += i; + do + { + sum += (uintptr_t)p; + p += 1; + i++; + } + while (i < n); +} + +int +main () +{ + /* Mirror image of gcc.dg/torture/pr113703-5.c with an increasing pointer: + the loop iterates twice and IVOPTs used to compute the bound as + P_0 - 0xfffffffe instead of P_0 + 2, making the loop exit at the first + test. */ + f ((char *)0xff00000001, -1, 1); + /* SUM is 0x10000000000 + 0x10000000001. */ + if (sum != (uintptr_t)0x20000000001) + __builtin_abort (); + return 0; +} diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc index fa3c2c136fc0..ab2c797b3865 100644 --- a/gcc/tree-ssa-loop-ivopts.cc +++ b/gcc/tree-ssa-loop-ivopts.cc @@ -5290,33 +5290,44 @@ nonneg_scaled_offset_p (tree val, HOST_WIDE_INT step, tree off_type) bla (*p); p++; } - while (p < p_0 - a + b); + while (p < p_0 - (a + 1) + (b + 1)); - 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. + Note that the bound has to be computed as p_0 - (a + 1) + (b + 1) 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. + + Note also that a + 1 must be used as the offset it is, i.e. converted to + the type of the offsets as a whole, and not rewritten into a and 1, since + it may wrap around in the type of a: this is precisely the case where the + loop rolls but b - a is not the number of iterations either. Conversely + b + 1 must be computed in the type of the offsets, where it cannot wrap + around, since nothing constrains b 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: + a, b, a + 1 and b + 1 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 + 1) if a + 1 <= b, then the loop rolls b - (a + 1) times, so that (b + 1) + - (a + 1) computed on the offsets is its number of iterations, and + p_0 - (a + 1) + (b + 1) is the final value of p, hence there is no 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. */ + 2) if a + 1 > b, then the loop exits at the first test and a + 1 does not + wrap around, so b <= a implies that p_0 - (a + 1) + (b + 1) = 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, struct iv_use *use, struct iv_cand *cand, enum tree_code *comp_p, class tree_niter_desc *niter, tree *bound_p) { - tree cand_type, a, b, mbz, nit_type = TREE_TYPE (niter->niter); + tree cand_type, a, a1, b, b1, mbz, nit_type = TREE_TYPE (niter->niter); tree off_type, offset, bound; class aff_tree nit, tmpa, tmpb; enum tree_code comp; @@ -5356,6 +5367,7 @@ iv_elimination_compare_lt (struct ivopts_data *data, struct iv_use *use, tree op0 = TREE_OPERAND (mbz, 0); if (TREE_CODE (op0) == PLUS_EXPR && integer_onep (TREE_OPERAND (op0, 1))) { + a1 = op0; a = TREE_OPERAND (op0, 0); b = TREE_OPERAND (mbz, 1); } @@ -5369,6 +5381,7 @@ iv_elimination_compare_lt (struct ivopts_data *data, struct iv_use *use, /* Handle b < a + 1. */ if (TREE_CODE (op1) == PLUS_EXPR && integer_onep (TREE_OPERAND (op1, 1))) { + a1 = op1; a = TREE_OPERAND (op1, 0); b = TREE_OPERAND (mbz, 0); } @@ -5402,11 +5415,21 @@ iv_elimination_compare_lt (struct ivopts_data *data, struct iv_use *use, if (!difference_cannot_overflow_p (data, cand->iv->base, offset)) return false; + /* Convert A + 1 as a whole, since it may wrap around in the type of A, but + compute B + 1 in OFF_TYPE, where it cannot wrap around. */ + a1 = fold_convert (off_type, a1); + b1 = fold_build2 (PLUS_EXPR, off_type, fold_convert (off_type, b), + build_one_cst (off_type)); + /* 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. */ + which A + 1 and B + 1 move it away from CAND->IV->BASE - CAND->IV->STEP + * (A + 1) have to be ordered the same way as A + 1 and B + 1 themselves. + The same is required of A and B, in terms of which the bound is + expressed when the loop rolls zero times. */ if (!nonneg_scaled_offset_p (a, step, off_type) - || !nonneg_scaled_offset_p (b, step, off_type)) + || !nonneg_scaled_offset_p (b, step, off_type) + || !nonneg_scaled_offset_p (a1, step, off_type) + || !nonneg_scaled_offset_p (b1, step, off_type)) return false; /* Determine the new comparison operator. */ @@ -5418,15 +5441,14 @@ iv_elimination_compare_lt (struct ivopts_data *data, struct iv_use *use, 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 + /* Recompute the bound as CAND->IV->BASE - CAND->IV->STEP * (A + 1) + + CAND->IV->STEP * (B + 1). 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); + fold_build2 (MULT_EXPR, off_type, cand->iv->step, b1), + fold_build2 (MULT_EXPR, off_type, cand->iv->step, a1)); cand_type = TREE_TYPE (cand->iv->base); if (POINTER_TYPE_P (cand_type)) *bound_p = fold_build_pointer_plus (cand->iv->base, bound);
