Issue 241377
Summary [BasicAA] Decomposed GEP offset sums can wrap even when each scaled index is nsw
Labels new issue
Assignees
Reporter cjsrxzdyzds
    The decomposition of two GEPs gives the distance between the pointers as
`Offset + sum(Scale * V)`, but only modulo 2^BW. Three rules of `aliasGEP()` treat that sum as an
integer:

- the modular rule, when the GCD of the scales does not divide 2^BW;
- the minimum-offset rule for two indices, which uses `abs(Scale*V0 - Scale*V1) >= abs(Scale)` for
  `V0 != V1`;
- the constant offset heuristic, which is the same for a known difference.

They required each `Scale * V` not to wrap. That does not keep the sum from wrapping:

```llvm
define i8 @f(ptr %p, i64 %x, i64 %y) noinline {
  %mx = mul nsw i64 %x, 3
  %my = mul nsw i64 %y, 3
  %g0 = getelementptr i8, ptr %p, i64 4
  %g1 = getelementptr i8, ptr %g0, i64 %mx
  %g2 = getelementptr i8, ptr %g1, i64 %my
  store i8 1, ptr %p
  store i8 2, ptr %g2
  %v = load i8, ptr %p
  ret i8 %v
}

define i32 @main() {
  %a = alloca i8
  %r = call i8 @f(ptr %a, i64 3074457345618258602, i64 3074457345618258602)
  %z = zext i8 %r to i32
 ret i32 %z
}
```

`4 + 3*x + 3*y` is 2^64 for these arguments and neither multiplication overflows, so `%g2` is
`%p`. `lli --force-interpreter` exits with 2. After `opt -passes=gvn` on LLVM main at `45403d3979a5` it exits
with 1: BasicAA answers `NoAlias` for `%g2` and `%p` because 4 is not a multiple of 3, GVN forwards
the first store to the load.

The two rules for a pair of indices fail the same way when one product is close to `INT64_MAX`
and the other to `INT64_MIN`. The check added to the heuristic in #236719 accepts nsw products and
does not exclude this. The constants can
wrap as well, even if every GEP is nusw.


Related: #236396 was fixed by #236719, which rejects individually wrapping scaled indices. This report concerns the remaining case where each product is non-wrapping but their sum or difference wraps. The two-index minimum-offset guard added in #137755 has the same remaining limitation.

Save the IR above as `repro.ll` and run on x86-64:

```sh
lli --force-interpreter repro.ll; echo $?
opt -S -passes=gvn repro.ll -o repro.gvn.ll
lli --force-interpreter repro.gvn.ll; echo $?
```

Expected exit status: 2 in both executions. Actual: 2 before GVN, 1 after GVN.

These examples were developed while checking a model of BasicAA against LLVM, with Claude Code assistance. The report was prepared with Claude Code and OpenAI Codex.

_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs

Reply via email to