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

Reply via email to