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.
Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed.
Richard.
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.
---
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(-)
create mode 100644 gcc/testsuite/gcc.dg/torture/pr113703-5.c
create mode 100644 gcc/testsuite/gcc.dg/torture/pr113703-6.c
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 00000000000..bb63c0f69e9
--- /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 00000000000..de6f228eda3
--- /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 fa3c2c136fc..ab2c797b386 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);
--
2.51.0
