| Issue |
107996
|
| Summary |
GVN wrong optimization with skipped out-of-bounds accesses
|
| Labels |
miscompilation,
llvm:GVN
|
| Assignees |
|
| Reporter |
hvdijk
|
Please consider this function:
```llvm
define i32 @f(i1 %false, i64 %zero) {
entry:
%a = alloca i32
store i32 1, ptr %a
br i1 %false, label %bb.1, label %bb.2
bb.1:
%x = load i64, ptr %a
store i64 %x, ptr %a
br label %bb.2
bb.2:
br i1 %false, label %bb.4, label %bb.3
bb.3:
%j = getelementptr i32, ptr %a, i64 %zero
store i32 3, ptr %j
br label %bb.4
bb.4:
%z = load i32, ptr %a
ret i32 %z
}
```
This is a valid function to call with two zero arguments, in which case `%bb.1` is skipped, `%bb.3` is entered, `3` is stored to `%a`, and in `%bb.4`, `3` is then returned.
If this function is called with any other argument, the behavior is undefined. If `%false` is non-zero, `%bb.1` is entered and `%a` is accessed past its end. If `%false` is zero but `%zero` is non-zero, `%bb.3` stores past `%a`'s end.
GVN transforms this (`opt -passes=gvn`, LLVM commit 09c00b6f0463f6936be5d2100f9d47c0077700f8) to:
```llvm
define i32 @f(i1 %false, i64 %zero) {
entry:
%a = alloca i32, align 4
store i32 1, ptr %a, align 4
br i1 %false, label %bb.1, label %bb.2
bb.1:
%x = load i64, ptr %a, align 4
store i64 %x, ptr %a, align 4
%0 = trunc i64 %x to i32
br label %bb.2
bb.2:
%z = phi i32 [ %0, %bb.1 ], [ 1, %entry ]
br i1 %false, label %bb.4, label %bb.3
bb.3:
%j = getelementptr i32, ptr %a, i64 %zero
store i32 3, ptr %j, align 4
br label %bb.4
bb.4:
ret i32 %z
}
```
If called with two zero arguments, `%bb.3` is still entered and still stores `3` to `%a`, but the load in `%bb.4` has been mis-optimized to its earlier value.
Alive agrees that this transformation is invalid: https://alive2.llvm.org/ce/z/EhdxXU
I have not fully understood yet what is happening, but at first glance, it appears that this bit in [`MemoryDependenceResults::getNonLocalPointerDepFromBB`](https://github.com/llvm/llvm-project/blob/433ca3ebbef50002bec716ef2c6d6a82db71048d/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp#L1097) is wrong:
```c++
// This query's Size is less than the cached one. Conservatively restart
// the query using the greater size.
return getNonLocalPointerDepFromBB(
QueryInst, Pointer, Loc.getWithNewSize(CacheInfo->Size), isLoad,
StartBB, Result, Visited, SkipFirstBlock, IsIncomplete);
```
This assumes that querying with a greater size can only find additional possible dependencies, but it ignores that a greater size may cause dependencies to be left out if that size is greater than the memory region.
![]()
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
