| Issue |
245027
|
| Summary |
[LoopUnroll] Parallel reduction phis keep range attributes of the min/max call, so partial results started from the identity are poison
|
| Labels |
new issue
|
| Assignees |
|
| Reporter |
ubmaxxer
|
### Reproducer
godbolt: https://godbolt.org/z/997qT16Tr
Reproduces with `opt` (trunk) on godbolt and locally at faf262703dfc53f2fc7a877c32a1ba8c462ed343 (`opt` and `llubi` built from that revision). `opt` 23.1.0 gives the same output; `opt` 22.1.0 does not split the `smin` reduction and is not affected.
```llvm
target triple = "x86_64-unknown-linux-gnu"
; %x is always in [-128, 128) and %v starts at 1, so %v stays in [-128, 2).
; The range on the %v argument is true on every iteration.
; For %k == 2, %x takes 0, 2, 4, ..., 14, so @test returns 0.
define i32 @test(i32 %k) {
entry:
br label %loop
loop:
%iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
%v = phi i32 [ 1, %entry ], [ %m, %loop ]
%t = mul i32 %iv, %k
%t8 = trunc i32 %t to i8
%x = sext i8 %t8 to i32
%m = call i32 @llvm.smin.i32(i32 range(i32 -128, 128) %v, i32 %x)
%iv.next = add nuw nsw i32 %iv, 1
%again = icmp ult i32 %iv.next, 8
br i1 %again, label %loop, label %exit, !llvm.loop !0
exit:
ret i32 %m
}
; same loop with the range on the call's return value instead
define i32 @test_ret(i32 %k) {
entry:
br label %loop
loop:
%iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
%v = phi i32 [ 1, %entry ], [ %m, %loop ]
%t = mul i32 %iv, %k
%t8 = trunc i32 %t to i8
%x = sext i8 %t8 to i32
%m = call range(i32 -128, 2) i32 @llvm.smin.i32(i32 %v, i32 %x)
%iv.next = add nuw nsw i32 %iv, 1
%again = icmp ult i32 %iv.next, 8
br i1 %again, label %loop, label %exit, !llvm.loop !2
exit:
ret i32 %m
}
; same loop without attributes: unrolled correctly
define i32 @clean(i32 %k) {
entry:
br label %loop
loop:
%iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
%v = phi i32 [ 1, %entry ], [ %m, %loop ]
%t = mul i32 %iv, %k
%t8 = trunc i32 %t to i8
%x = sext i8 %t8 to i32
%m = call i32 @llvm.smin.i32(i32 %v, i32 %x)
%iv.next = add nuw nsw i32 %iv, 1
%again = icmp ult i32 %iv.next, 8
br i1 %again, label %loop, label %exit, !llvm.loop !3
exit:
ret i32 %m
}
define i32 @main() {
%r = call i32 @test(i32 2)
%ok = icmp eq i32 %r, 0
%ret = select i1 %ok, i32 7, i32 9
ret i32 %ret
}
declare i32 @llvm.smin.i32(i32, i32)
!0 = distinct !{!0, !1}
!1 = !{!"llvm.loop.unroll.count", i32 2}
!2 = distinct !{!2, !1}
!3 = distinct !{!3, !1}
```
```console
$ opt -S -passes=loop-unroll -unroll-add-parallel-reductions repro.ll # abridged
define i32 @test(i32 %k) {
...
loop:
%iv = phi i32 [ 0, %entry ], [ %iv.next.1, %loop ]
%v.1 = phi i32 [ 2147483647, %entry ], [ %m.1, %loop ]
%v = phi i32 [ 1, %entry ], [ %m, %loop ]
...
%m = call i32 @llvm.smin.i32(i32 range(i32 -128, 128) %v, i32 %x)
...
%m.1 = call i32 @llvm.smin.i32(i32 range(i32 -128, 128) %v.1, i32 %x.1)
...
exit:
%m.lcssa = phi i32 [ %m.1, %loop ]
%rdx.minmax = call i32 @llvm.smin.i32(i32 %m, i32 %m.1)
ret i32 %rdx.minmax
}
```
When unrolling by 2 with parallel reduction phis, the unroller adds a second accumulator `%v.1` that starts at the `smin` identity, `INT32_MAX`, and feeds it to the cloned call `%m.1`. The clone keeps the `range(i32 -128, 128)` attribute on that argument. Per LangRef, an argument outside its `range` is poison, so on the first iteration `%m.1` is `smin(poison, %x.1)`, which is poison. `%m.1` is carried around the loop in `%v.1` and into `%rdx.minmax`, so `@test` returns poison. In the source the attribute is true on every iteration (`%v` is 1 or a previous `%x`), and `@test(2)` returns 0. `@test_ret` shows the same problem with the attribute on the return value: `range(i32 -128, 2)` holds for the original chain because `%v` starts at 1, but the second accumulator computes `smin(INT32_MAX, 2) = 2` for `%k == 2`, which is outside the range. `@clean` has no attribute and its output is fine.
llubi: the input returns 7 from `main`; after `-passes=loop-unroll -unroll-add-parallel-reductions` it reports `Execution of function 'main' resulted in poison return value.` The same holds when `main` calls `@test_ret(2)`. With `@clean(2)` it still returns 7.
Alive2 (local `alive-tv --disable-undef-input --src-unroll=8 --tgt-unroll=4 repro.ll out.ll`, where `out.ll` is the output of the `opt` above at faf262703dfc) rejects `@test_ret`. It accepts `@test`, apparently because it does not model `range` on call arguments (it reports adding such an attribute to a call as "syntactically equal"):
```console
define i32 @test_ret(i32 %k) {
Transformation doesn't verify!
ERROR: Target is more poisonous than source
Example:
i32 %k = #x00000009 (9)
...
Target:
i32 %v.1 = #x7fffffff (2147483647)
...
i32 %m.1 = #x00000009 (9)
i32 %#range_1_%m.1 = poison
...
i32 %rdx.minmax = poison
Source value: #x00000000 (0)
Target value: poison
Summary:
3 correct transformations
1 incorrect transformations
```
`UnrollLoop` in `llvm/lib/Transforms/Utils/LoopUnroll.cpp` (parallel reduction phis were added by #149470, 2d9e452ab0f3; min/max support by #201010, 452f59c8dc30) ends with
```cpp
for (Instruction *RdxPart : PartialReductions)
RdxPart->dropPoisonGeneratingFlags();
```
which clears `nsw`/`nuw` and similar flags but not call attributes. A fix could call `dropPoisonGeneratingAnnotations()` there instead, which also removes poison-generating return and parameter attributes (`range`, among others) and metadata.
This is reachable from C at default flags on Apple CPUs, where `AArch64TTIImpl` enables `AddAdditionalAccumulators` (`isAppleMLike()`), so `-unroll-add-parallel-reductions` is not needed (enabled there by 3ea089ba1976). IPSCCP puts `range` on the parameters of the static helper and the inliner copies it to the arguments of the `smin` call:
```c
static inline long min64(long a, long b) { return a < b ? a : b; }
struct node { long val; int next; };
short kernel(struct node *a, unsigned n) {
short v = 1; int p = 0;
for (unsigned i = 0; i < n; i++) {
v = (short)min64((long)v, (long)(short)a[p].val);
p = a[p].next;
}
return v;
}
```
```console
$ clang -O2 --target=arm64-apple-macosx14.0 -S -emit-llvm kernel.c -o - # abridged
for.body:
%v.011.1 = phi i64 [ 9223372036854775807, %for.body.preheader.new ], [ %cond.i.1, %for.body ]
...
%cond.i.1 = tail call range(i64 -32768, 32768) i64 @llvm.smin.i64(i64 range(i64 -32768, 32768) %v.011.1, i64 range(i64 -32768, 32768) %conv2.1)
```
Three of the four accumulators start at `INT64_MAX` and their `smin` calls keep the `[-32768, 32768)` range on that argument. With a `main` that calls `kernel` on 9 nodes, llubi prints the expected result for the `-O0` IR and reports `Immediate UB detected: The value poison violates noundef attribute.` for the `-O2` IR. The IR reproducer above shows the same without the flag under `opt -passes=loop-unroll -mcpu=apple-m1` with an `arm64-apple-macosx` triple. I have not observed a wrong result in generated machine code: as far as I can tell nothing currently uses `range` on a call argument to fold the call, and in the C case the return-value range still holds for the new accumulators.
Note: This test case was generated by a fuzzer, and the report was written with LLM assistance.
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs