| 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