Issue 241376
Summary [BasicAA] Incorrect NoAlias from nsw linear expressions with overflowing scales or shl
Labels new issue
Assignees
Reporter cjsrxzdyzds
    `GetLinearExpression()` represents an index as `V * Scale + Offset` and keeps an `IsNSW` flag. The
rules of `aliasGEP()` read the flag as "`V * Scale` does not overflow": the range rule multiplies
with `smul_sat`, and the minimum-offset rule assumes `abs(V * Scale) >= abs(Scale)`. The flag was
kept in three cases where that does not hold.

1. `(V *nsw A) *nsw B` was recorded as `V *nsw (A * B)` even if `A * B` overflows. `V * 2^32 * 2^31`
   is `V * 2^63`, which is defined for `V == -1`. The recorded scale is `INT64_MIN`, and
   `-1 * INT64_MIN` overflows.
2. `shl nsw V, 63` was recorded as `V *nsw INT64_MIN`. It is defined for `V == -1` as well.
3. `shl nsw (V +nsw C), N` kept the flag. That `(V + C) << N` does not overflow does not imply
   that `V << N` does not. `mul` already drops the flag when the offset is not zero.

In each case BasicAA answers `NoAlias` for two pointers that are equal. For the second one:

```llvm
define i8 @f(ptr %p, i1 %c) noinline {
  %x = sext i1 %c to i64
  %s = shl nsw i64 %x, 63
  %g0 = getelementptr i8, ptr %p, i64 %s
  %g1 = getelementptr i8, ptr %g0, i64 -9223372036854775808
  store i8 1, ptr %p
  store i8 2, ptr %g1
  %v = load i8, ptr %p
  ret i8 %v
}

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

With `%c` true, `%s` is `INT64_MIN` and `%g1` is `%p - 2^64`, which is `%p`. `lli
--force-interpreter` exits with 2. After `opt -passes=gvn` on LLVM main at `45403d3979a5` it exits with 1: GVN
forwards the first store to the load.

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.
The other two cases have the same incorrect `NoAlias` consequence.

Related: #69122 fixed loss of `nsw` when merging two occurrences of an index.
This report concerns constant-scale multiplication and shifts inside
`GetLinearExpression()`.

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