Issue 242012
Summary [BasicAA] GEP element sizes are truncated to 32 bits, causing miscompilation and an APInt assertion
Labels new issue
Assignees
Reporter cjsrxzdyzds
    `DecomposeGEPExpression()` scales a variable GEP index by the element size like this
([`llvm/lib/Analysis/BasicAliasAnalysis.cpp`, lines 755-757 at `e65a8642d426`](https://github.com/llvm/llvm-project/blob/e65a8642d426/llvm/lib/Analysis/BasicAliasAnalysis.cpp#L755-L757)):

```cpp
 // Scale by the type size.
      unsigned TypeSize = AllocTypeSize.getFixedValue();
      LE = LE.mul(APInt(IndexSize, TypeSize), NUW, NUSW);
```

`getFixedValue()` returns a `uint64_t`, so an element size of 2^32 bytes or more is truncated to
32 bits. With 64-bit indices, `getelementptr [4294967300 x i8], ptr %p, i64 %x` is decomposed as
`%p + 4 * %x` instead of `%p + 4294967300 * %x`, and BasicAA gives wrong answers. When the
element size does not fit the index type (for example `[300 x i8]` with `e-p:8:8`), the `APInt`
constructor asserts instead.

### Miscompile on x86-64

```c
#include <stdio.h>
#include <stdlib.h>

typedef char big[4294967300ULL]; /* 2^32 + 4 bytes */

__attribute__((noinline)) int f(big *p, long x) {
  p[x][0] = 1;
  ((char *)p)[4 * x] = 2;
  return p[x][0];
}

int main(void) {
  big *p = malloc(2 * sizeof(big)); /* 8 GiB + 8 bytes of address space; two pages are touched */
  if (!p)
    return 3;
  printf("%d\n", f(p, 1));
  return 0;
}
```

For `x == 1` the two stores write the bytes at offsets 2^32 + 4 and 4 of the allocation, so `f`
returns 1. With clang at `e65a8642d426` on x86-64 Linux:

```console
$ clang -O0 repro.c -o repro && ./repro
1
$ clang -O1 repro.c -o repro && ./repro
1
$ clang -O2 repro.c -o repro && ./repro
2
$ clang -O3 repro.c -o repro && ./repro
2
```

At `-O2` the first store is deleted and `f` returns the constant 2. Once InstCombine has turned
`4 * x` into `shl nsw i64 %x, 2`, BasicAA answers `MustAlias` for `p[x]` and `(char *)p + 4 * x`.
Ubuntu's clang 14.0.0 also prints 1 at `-O0` and 2 at `-O2`; GCC 11.4 prints 1 at both.

The same in IR, without clang:

```llvm
declare ptr @malloc(i64)

define i8 @f(ptr %p, i64 %x) noinline {
  %a = getelementptr [4294967300 x i8], ptr %p, i64 %x
  %b = getelementptr i32, ptr %p, i64 %x
  store i8 1, ptr %a
  store i8 2, ptr %b
  %v = load i8, ptr %a
  ret i8 %v
}

define i32 @main() {
  %p = call ptr @malloc(i64 8589934600)
  %null = icmp eq ptr %p, null
  br i1 %null, label %fail, label %ok
fail:
  ret i32 3
ok:
  %r = call i8 @f(ptr %p, i64 1)
  %z = zext i8 %r to i32
  ret i32 %z
}
```

```console
$ lli repro.ll; echo $?
1
$ opt -S -passes=gvn repro.ll -o repro.gvn.ll
$ lli repro.gvn.ll; echo $?
2
$ opt -aa-pipeline=basic-aa -passes=aa-eval -print-all-alias-modref-info -disable-output repro.ll
  MustAlias:	i8* %a, i8* %b
```

(`lli` without `--force-interpreter`, because the interpreter cannot call `malloc`.)

### Assertion when the element size does not fit the index type

```llvm
target datalayout = "e-p:8:8"

define i8 @f(ptr %p, i8 %x) {
  %a = getelementptr [300 x i8], ptr %p, i8 %x
  %b = getelementptr i8, ptr %p, i8 1
  store i8 1, ptr %a
  store i8 2, ptr %b
 %v = load i8, ptr %a
  ret i8 %v
}
```

```console
$ opt -S -passes=gvn repro8.ll        # paths and addresses shortened
opt: llvm/include/llvm/ADT/APInt.h:128: llvm::APInt::APInt(unsigned int, uint64_t, bool, bool): Assertion `llvm::isUIntN(BitWidth, val) && "Value is not an N-bit unsigned value"' failed.
...
 #9 ... llvm::BasicAAResult::DecomposeGEPExpression(llvm::Value const*, llvm::DataLayout const&, llvm::AssumptionCache*, llvm::DominatorTree*)
```

`opt -O2` asserts the same way, and so does `e-p:16:16` with `[70000 x i8]`. In a build of the
same commit without assertions there is no crash, and the three answers checked were right
modulo the index width: `NoAlias` for `%a` and `%b` above and for the 16-bit variant, and
`MustAlias` for `[300 x i8]` indexed by `%x` against `getelementptr i8, ptr %p, i8 (mul %x, 44)`.
Reading `APInt.h`, the constructor then keeps the unmasked value and the following
multiplication masks it. A constant index takes another path (line 733, `uint64_t` times
`APInt`) and is not affected: `getelementptr [4294967300 x i8], ptr %p, i64 1` against
`getelementptr i8, ptr %p, i64 4` is `NoAlias`.

### History

`unsigned TypeSize` came with [cdf45f98ca52](https://github.com/llvm/llvm-project/commit/cdf45f98ca52) ("[BasicAA] Extract linear _expression_ multiplication
(NFC)", October 2021). Before it the scale was built as
`APInt Scale(MaxPointerSize, DL.getTypeAllocSize(...).getFixedSize())`, without the truncation.

### Possible fix

```diff
-      unsigned TypeSize = AllocTypeSize.getFixedValue();
-      LE = LE.mul(APInt(IndexSize, TypeSize), NUW, NUSW);
+      APInt TypeSize(IndexSize, AllocTypeSize.getFixedValue(),
+                    /*isSigned=*/false, /*implicitTrunc=*/true);
+      LE = LE.mul(TypeSize, NUW, NUSW);
```

With this change on `e65a8642d426` (built with assertions): the 4 GiB pair above is `MayAlias`
(right: the two pointers coincide for `%x == 2^32`), the IR program returns 1 after GVN, the C
program prints 1 after clang's unoptimized IR goes through `opt -passes='default<O2>'`, the 8- and
16-bit inputs no longer assert and give the same answers as the build without assertions, and
the tests under `llvm/test/Analysis/BasicAA`, `llvm/test/Transforms/GVN` and
`llvm/test/Transforms/DeadStoreElimination` pass: 469 passed, 5 unsupported, 2 expected failures,
including a new regression file covering both BasicAA answers and GVN. The unmodified build
has 468 passed with the same exclusions; the new checks detect the miscompile and assertion
on unmodified builds. The fix retains the existing no-wrap flag handling, consistent with
`emitGEPOffset()`, which also constructs the scale at the index width and passes the GEP
no-wrap flags to the multiplication.

Related: #138528 fixed the same kind of `APInt` assertion for a location size larger than the
index space. #119365 and #191180 changed nearby code in `DecomposeGEPExpression()` but not this
conversion. I found no existing report of it.

These examples were found while checking a Lean model of BasicAA against LLVM, with Claude
Code assistance. The model exposes assumptions about offsets, objects and flags; the examples
above were then independently reproduced by executing the C and IR programs. The report, fix
and regression tests were prepared with Claude Code and OpenAI Codex assistance.

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

Reply via email to