| Issue |
243391
|
| Summary |
[LoopUnroll] Convergent loop runtime-unrolled when its trip count comes from a loop with a divergent exit
|
| Labels |
new issue
|
| Assignees |
|
| Reporter |
PankajDwivedi-25
|
Since #192819, LoopUnroll can add a remainder loop to a loop that contains convergent operations if `isSCEVUniform()` says the backedge-taken count is uniform. That check misses temporal divergence: a value computed in a loop that threads leave at different iterations is uniform inside that loop, but differs between threads after it.
Reproducer (reproduces on `main`, tested at b8e25fc2bbc3):
```
opt -mtriple=amdgcn-amd-amdhsa -mcpu=gfx90a -passes=loop-unroll -S repro.ll
```
```llvm
define amdgpu_kernel void @count_then_shuffle(ptr addrspace(1) %out, ptr addrspace(1) %data) {
entry:
%tid = call i32 @llvm.amdgcn.workitem.id.x()
br label %count
count:
%n = phi i32 [ 0, %entry ], [ %n.next, %count ]
%p = getelementptr inbounds i32, ptr addrspace(1) %data, i32 %n
%d = load i32, ptr addrspace(1) %p
%n.next = add nuw nsw i32 %n, 1
%stop = icmp sgt i32 %d, %tid
br i1 %stop, label %loop.ph, label %count
loop.ph:
%n.lcssa = phi i32 [ %n.next, %count ]
br label %loop
loop:
%i = phi i32 [ 0, %loop.ph ], [ %i.next, %loop ]
%v = call i32 @llvm.amdgcn.ds.bpermute(i32 %i, i32 %i)
%gep = getelementptr inbounds i32, ptr addrspace(1) %out, i32 %i
store i32 %v, ptr addrspace(1) %gep
%i.next = add nuw nsw i32 %i, 1
%c = icmp eq i32 %i.next, %n.lcssa
br i1 %c, label %exit, label %loop
exit:
ret void
}
declare i32 @llvm.amdgcn.workitem.id.x()
declare i32 @llvm.amdgcn.ds.bpermute(i32, i32)
```
Each thread leaves `%count` at a different iteration, so `%n.lcssa`, the trip count of `%loop`, differs between threads, and `print<uniformity>` marks it divergent. But SCEV looks through the LCSSA phi: the backedge-taken count of `%loop` is `{0,+,1}<nuw><nsw><%count>`, an AddRec of the earlier loop with constant operands, which `isSCEVUniform()` accepts. `%loop` is unrolled by 8 with an epilog:
```llvm
loop.ph:
%n.lcssa = phi i32 [ %n.next, %count ]
%0 = add i32 %n.lcssa, -1
%xtraiter = and i32 %n.lcssa, 7
%1 = icmp ult i32 %0, 7
br i1 %1, label %loop.epil.preheader, label %loop.ph.new
```
This branch is divergent, so threads with different trip counts run the same original iteration in different copies of `ds.bpermute`. Expected: the loop is not runtime-unrolled, as before #192819.
The same happens when the trip count is a `SCEVUnknown` defined inside the earlier loop, and when it comes out of an irreducible cycle with a divergent exit.
<details>
<summary>Wrong results on an MI250X (gfx90a)</summary>
```c++
__device__ static inline int laneId() {
return __builtin_amdgcn_mbcnt_hi(-1, __builtin_amdgcn_mbcnt_lo(-1, 0));
}
__device__ static inline int shfl(int Var, int SrcLane) {
int Index = (SrcLane & 63) + (laneId() & ~63);
return __builtin_amdgcn_ds_bpermute(Index << 2, Var);
}
extern "C" __global__ void count_then_shuffle(int *Out, const int *Thresholds) {
int Tid = __builtin_amdgcn_workitem_id_x();
int N = 0;
do
N++;
while (Thresholds[N] <= Tid);
for (int I = 0; I < N; I++)
Out[Tid * 32 + I] = shfl(I * 1000 + Tid, 63);
}
```
Built with `clang -x hip --offload-arch=gfx90a --cuda-device-only -nogpuinc -nogpulib -O3` and run with one wave of 64 lanes and `Thresholds[k] = 4 * k`. Lane 63 runs the second loop the most times, so every lane should read `I * 1000 + 63`. 196 of the 2048 values are wrong; for example, lane 8 reads 63 instead of 2063 on iteration 2. With `-mllvm -unroll-runtime=false`, all values are correct.
</details>
This report was prepared with help from an AI assistant. I reviewed it and verified the reproducer and the hardware results.
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs