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 <noreply@anthropic.com>
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.
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
new file mode 100644
@@ -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;
+}
new file mode 100644
@@ -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;
+}
@@ -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*-*-* } } */
@@ -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
@@ -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;
}