[AMDGPU] Do not only rely on BB number when finding bottom loop

[msearles]

Summary

We should also check that the "bottom" basic block of a loop
is a successor of the "header" basic block, otherwise we don't
propagate the information correctly when the CFG is complex.

This fixes an important rendering problem with Wolfsentein 2,
because of one vector-memory wait was missing.

Please review,
Thanks!

[kzhuravl]

is it possible to include the test as well?

[hakzsam]

This new revision attaches a LLVM IR testcase that reproduces the issue, not sure if the test can still be reduced compared to the original monster shader.

I have noticed one weird thing after running shader-db, it looks like there is a side effect that produces some unnecessary expcnt(0) instructions in some compute shaders. Maybe this patch triggers a new issue? Otherwise, I don't see any regressions with RADV.

I will investigate about the extra expcnt(0).

Please review, thanks!

[hakzsam]

Here's a test case where a expcnt(0) is generated https://hastebin.com/uyuhabeqov.pl

If you look at the CFG, there is two loops (BB1 and BB5). The previous algorithm returns BB12 for both loop headers which looks quite wrong. The real bottom basic blocks are BB2 for BB1 and BB6 for BB5 (which is what this patch does return).

I think something isn't correctly re-initialized. Anyway, generating expcnt(0) instructions in compute shaders is just useless.

[hakzsam]

Oh, I thought expcnt() was for parameters export only, but it can be used for GDS instructions as well.

[hakzsam]

So, the expcnt(0) is generated because there is a buffer_atomic_add in that test case, which actually makes sense to me. Looks like this patch also fixes that case.

[nhaehnle]

Could you please reduce the testcase?

[hakzsam]

In D43831#1027001, @nhaehnle wrote:

Could you please reduce the testcase?

Okay, I will try to.

[hakzsam]

v3: reduced testcase

[msearles]

For the testcase, would you also run -instnamer to rename instances of %<number>? You may want to combine it with other clean-up options, something like this: opt -S -deadarghaX0r -strip -strip-debug -strip-dead-prototypes -instnamer

[hakzsam]

In D43831#1027405, @msearles wrote:

For the testcase, would you also run -instnamer to rename instances of %<number>? You may want to combine it with other clean-up options, something like this: opt -S -deadarghaX0r -strip -strip-debug -strip-dead-prototypes -instnamer

Ah yeah, thanks for the hints. I will try to clean up the testcase a bit more.

[hakzsam]

v4: - run 'opt -S -deadarghaX0r -strip -strip-debug -strip-dead-prototypes -instnamer'

• remove RFC on the subject

[nhaehnle]

I haven't yet had the time to fully grok what's going on here, but I suspect this code is fundamentally broken because the whole assumption of having a single loopBottom is wrong. It happens to be true for structured loops with non-uniform control flow, but when there's uniform control flow, there may well be multiple back-edges. What happens in those cases?

test/CodeGen/AMDGPU/waitcnt-looptest.ll

145–265

These attributes clash with the attributes defined later on in the added part of the tests. I'm surprised there is no warning about that.

Please put all attributes at the end of the file and make their numbers unique.

[nhaehnle]

test/CodeGen/AMDGPU/waitcnt-looptest.ll

170

This and possibly others are redundant. Have you tried running -dce?

[hakzsam]

In D43831#1028129, @nhaehnle wrote:

I haven't yet had the time to fully grok what's going on here, but I suspect this code is fundamentally broken because the whole assumption of having a single loopBottom is wrong. It happens to be true for structured loops with non-uniform control flow, but when there's uniform control flow, there may well be multiple back-edges. What happens in those cases?

I'm not sure either if the current code correctly supports multiple back-edges. I think if there is more than one, loopBottom() will select the basic block with the highest number if it's a successor of the header loop.

[nhaehnle]

In D43831#1028150, @hakzsam wrote:

In D43831#1028129, @nhaehnle wrote:

I haven't yet had the time to fully grok what's going on here, but I suspect this code is fundamentally broken because the whole assumption of having a single loopBottom is wrong. It happens to be true for structured loops with non-uniform control flow, but when there's uniform control flow, there may well be multiple back-edges. What happens in those cases?

I'm not sure either if the current code correctly supports multiple back-edges. I think if there is more than one, loopBottom() will select the basic block with the highest number if it's a successor of the header loop.

The other way around: it will select the basic block with the highest number which has the loop header as its successor.

The question is whether that ends up doing the right thing in all cases.

[hakzsam]

In D43831#1028165, @nhaehnle wrote:

In D43831#1028150, @hakzsam wrote:

In D43831#1028129, @nhaehnle wrote:

I haven't yet had the time to fully grok what's going on here, but I suspect this code is fundamentally broken because the whole assumption of having a single loopBottom is wrong. It happens to be true for structured loops with non-uniform control flow, but when there's uniform control flow, there may well be multiple back-edges. What happens in those cases?

I'm not sure either if the current code correctly supports multiple back-edges. I think if there is more than one, loopBottom() will select the basic block with the highest number if it's a successor of the header loop.

The other way around: it will select the basic block with the highest number which has the loop header as its successor.

The question is whether that ends up doing the right thing in all cases.

Exactly, I can try to write a test with multi back-edges and we will see what happens in this situation.

test/CodeGen/AMDGPU/waitcnt-looptest.ll

170

No, I didn't, I will try and update the patch again if needed, Thanks!

[hakzsam]

v5: run -dce to remove redundant phis

[hakzsam]

In D43831#1028165, @nhaehnle wrote:

In D43831#1028150, @hakzsam wrote:

In D43831#1028129, @nhaehnle wrote:

I haven't yet had the time to fully grok what's going on here, but I suspect this code is fundamentally broken because the whole assumption of having a single loopBottom is wrong. It happens to be true for structured loops with non-uniform control flow, but when there's uniform control flow, there may well be multiple back-edges. What happens in those cases?

I'm not sure either if the current code correctly supports multiple back-edges. I think if there is more than one, loopBottom() will select the basic block with the highest number if it's a successor of the header loop.

The other way around: it will select the basic block with the highest number which has the loop header as its successor.

The question is whether that ends up doing the right thing in all cases.

https://hastebin.com/joqihayohe One case that doesn't work (ie. a vmcnt(0) is missing).

[hakzsam]

In D43831#1028208, @hakzsam wrote:

In D43831#1028165, @nhaehnle wrote:

In D43831#1028150, @hakzsam wrote:

In D43831#1028129, @nhaehnle wrote:

I haven't yet had the time to fully grok what's going on here, but I suspect this code is fundamentally broken because the whole assumption of having a single loopBottom is wrong. It happens to be true for structured loops with non-uniform control flow, but when there's uniform control flow, there may well be multiple back-edges. What happens in those cases?

I'm not sure either if the current code correctly supports multiple back-edges. I think if there is more than one, loopBottom() will select the basic block with the highest number if it's a successor of the header loop.

The other way around: it will select the basic block with the highest number which has the loop header as its successor.

The question is whether that ends up doing the right thing in all cases.

https://hastebin.com/joqihayohe One case that doesn't work (ie. a vmcnt(0) is missing).

I should have a fix for the multiple back-edges case, I'm going to run CTS to be sure it doesn't break anything before updating.

[hakzsam]

v6: fix the multiple back-edges case and update the testcase

[arsenm]

I think this really calls for a MIR testcase

[hakzsam]

v7:

• replace the LLVM IR testcase with a MIR one
• remove one unused variable in isLoopBottom()
• do not rely on block numbfer in isLoopBottom()

[arsenm]

lib/Target/AMDGPU/SIInsertWaitcnts.cpp

1556

lowercase true

1562

Braces

1563

Swap order of checks

1572

Braces

[hakzsam]

v8:

• add a sanity check when a block is looping over itself
• cosmetic changes

[msearles]

lib/Target/AMDGPU/SIInsertWaitcnts.cpp

1564

Can you explain why you avoid re-visiting a loop when a block loops over itself? I suppose this makes sense considering the current waitcnt pass sources. I.e., it admits that it does not handle single block loops correctly. See an "IMPORTANT NOTE" to this effect in SIInsertWaitcnts::mergeInputScoreBrackets() at SIInsertWaitcnts.cpp:1315-1317 . However, in order for it to correctly handle single block loops, it will need to revisit them and then the sanitify check won't make sense. I have a patch that fixes SIInsertWaitcnts::mergeInputScoreBrackets() in the case of a single block loop, but it's only useful if the block is revisited.

See the reduced testcase. Note:

• the first GLOBAL_STORE_DWORD has its write-data in $vgpr11
• the last GLOBAL_LOAD_DWORD loads into $vgpr11
• so, a waitcnt is needed before the store to wait for the load
• if the pass does not revisit bb.0, it has no way of knowing this

$ llc -mcpu=gfx900 -mtriple=amdgcn -verify-machineinstrs -run-pass si-insert-waitcnts testcase.mir
$ cat testcase.mir
--- |
define amdgpu_kernel void @benchmark_func() {
ret void
}
...
---
name: benchmark_func
body: |
bb.0:
GLOBAL_STORE_DWORD $vgpr7_vgpr8, $vgpr11, 0, 0, 0, implicit $exec
$vgpr21 = GLOBAL_LOAD_DWORD $vgpr4_vgpr5, 0, 0, 0, implicit $exec
$vgpr10 = GLOBAL_LOAD_DWORD $vgpr10_vgpr11, 0, 0, 0, implicit $exec
GLOBAL_STORE_DWORD $vgpr14_vgpr15, $vgpr21, 0, 0, 0, implicit $exec
$vgpr11 = GLOBAL_LOAD_DWORD $vgpr11_vgpr12, 0, 0, 0, implicit $exec
S_CBRANCH_SCC1 %bb.0, implicit $scc

bb.1:
S_ENDPGM
...

[msearles]

lib/Target/AMDGPU/SIInsertWaitcnts.cpp

1564

Hi @hakzsam, I'd like to see this patch move forward, so any comment on my comment? Thanks.

[hakzsam]

lib/Target/AMDGPU/SIInsertWaitcnts.cpp

1564

Hi,

Sorry, I was working on something more important.

Yes, I would like this patch to move forward too, I have to handle your testcase. I will update in the next few days.

Thanks for your feedbacks!

[msearles]

lib/Target/AMDGPU/SIInsertWaitcnts.cpp

1564

Sounds good; note that the testcase is llvm/trunk/test/CodeGen/AMDGPU/waitcnt-loop-single-basic-block.mir , which was pushed as part of https://reviews.llvm.org/rL327583 . I think if you remove that sanitify check, then the testcase will continue to pass; however, it will fail with the santify check as the single bb is not revisited.

Mark

[msearles]

lib/Target/AMDGPU/SIInsertWaitcnts.cpp

1564

Hi @hakzsam - ping; let me know if you don't have time to work on this; I can pick-up where you left off.

Mark

[hakzsam]

Hi Mark,

Yes, feel free to update this patch if you have time because I'm not sure when I will be able to.

Thanks.

[msearles]

Picking up where @hakzsam left off

[msearles]

• Change isLoopBottom() to return true in the case of a single basic block loop
• Clear LoopWaitcntDataMap in between functions

[hakzsam]

In D43831#1063216, @msearles wrote:

• Change isLoopBottom() to return true in the case of a single basic block loop
• Clear LoopWaitcntDataMap in between functions

Thanks for taking care of this!

The patch seems good to me, but as my LLVM skills are not that great, I'm not able to say "LGTM". :)

I will let AMDGPU LLVM people reply.

[msearles]

Ping; the patch looks good to the original author and to me, the follow-on author. However, it would be nice if someone other than one of us accepts the revision.

[kzhuravl]

LGTM.

lib/Target/AMDGPU/SIInsertWaitcnts.cpp

 MachineBasicBlock *SIInsertWaitcnts::loopBottom(const MachineLoop *Loop) {
   MachineBasicBlock *Bottom = Loop->getHeader();
   for (MachineBasicBlock *MBB : Loop->blocks())
-    if (MBB->getNumber() > Bottom->getNumber())
+    if (MBB->getNumber() > Bottom->getNumber() &&
+        MBB->isSuccessor(Loop->getHeader()))
       Bottom = MBB;
   return Bottom;
 }

test/CodeGen/AMDGPU/waitcnt-looptest.ll

 
 attributes #0 = { "target-cpu"="fiji" "target-features"="-flat-for-global" }
 attributes #1 = { nounwind readnone speculatable }
+
+; Check that the waitcnt insertion algorithm correctly propagates wait counts
+; from bottom loop to the loop header.
+
+; GCN-LABEL: {{^}}testLoopBottom
+; GCN: BB1_2:
+; GCN: s_waitcnt vmcnt(0)
+
+define amdgpu_kernel void @testLoopBottom([0 x i8] addrspace(4)* inreg noalias dereferenceable(18446744073709551615), [0 x i8] addrspace(4)* inreg noalias dereferenceable(18446744073709551615), i32 inreg, i32 inreg, i32, i32, i32, i32) {
+main_body:
+  %8 = add i32 %4, %2
+  %9 = and i32 %8, 3
+  %10 = lshr i32 %8, 2
+  %11 = getelementptr [0 x i8], [0 x i8] addrspace(4)* %1, i64 0, i64 48
+  %12 = bitcast i8 addrspace(4)* %11 to <4 x i32> addrspace(4)*, !amdgpu.uniform !0
+  %13 = shl i32 %10, 5
+  %14 = load <4 x i32>, <4 x i32> addrspace(4)* %12, align 16, !invariant.load !0
+  %15 = call float @llvm.amdgcn.buffer.load.f32(<4 x i32> %14, i32 0, i32 %13, i1 false, i1 false)
+  %16 = bitcast [0 x i8] addrspace(4)* %0 to <4 x i32> addrspace(4)*, !amdgpu.uniform !0
+  %17 = load <4 x i32>, <4 x i32> addrspace(4)* %16, align 16, !invariant.load !0
+  %18 = call float @llvm.SI.load.const.v4i32(<4 x i32> %17, i32 64)
+  %19 = call float @llvm.SI.load.const.v4i32(<4 x i32> %17, i32 80)
+  %20 = icmp ult i32 %9, 2
+  %21 = icmp eq i32 %9, 0
+  %22 = select i1 %21, i32 1065353216, i32 -1082130432
+  %23 = icmp eq i32 %9, 3
+  %24 = select i1 %23, i32 1065353216, i32 -1082130432
+  %25 = select i1 %20, i32 %22, i32 %24
+  %26 = select i1 %20, i32 1065353216, i32 -1082130432
+  %27 = bitcast i32 %25 to float
+  %28 = fmul float %27, 5.000000e-01
+  %29 = bitcast i32 %26 to float
+  %30 = fmul float %29, -5.000000e-01
+  %31 = fadd float %28, 5.000000e-01
+  %32 = fadd float %30, 5.000000e-01
+  %33 = getelementptr [0 x i8], [0 x i8] addrspace(4)* %1, i64 0, i64 16
+  %34 = bitcast i8 addrspace(4)* %33 to <4 x i32> addrspace(4)*, !amdgpu.uniform !0
+  %35 = load <4 x i32>, <4 x i32> addrspace(4)* %34, align 16, !invariant.load !0
+  %36 = call float @llvm.SI.load.const.v4i32(<4 x i32> %35, i32 0)
+  br label %37
+
+; <label>:37:                                     ; preds = %57, %main_body
+  %.in = phi float [ %36, %main_body ], [ %66, %57 ]
+  %38 = phi i32 [ 0, %main_body ], [ %63, %57 ]
+  %39 = phi float [ %15, %main_body ], [ %58, %57 ]
+  %40 = phi float [ %15, %main_body ], [ %59, %57 ]
+  %41 = fptosi float %.in to i32
+  %42 = icmp eq i32 %41, 0
+  br i1 %42, label %43, label %50
+
+; <label>:43:                                     ; preds = %37, %50
+  %44 = bitcast i32 %25 to float
+  %45 = fmul float %18, %44
+  %46 = bitcast i32 %26 to float
+  %47 = fmul float %19, %46
+  %48 = fadd float %45, %47
+  %49 = fadd float %39, %48
+  call void @llvm.amdgcn.exp.f32(i32 12, i32 15, float %49, float undef, float undef, float undef, i1 true, i1 false) #3
+  call void @llvm.amdgcn.exp.f32(i32 32, i32 15, float %31, float %32, float undef, float 0.000000e+00, i1 false, i1 false) #3
+  ret void
+
+; <label>:50:                                     ; preds = %37
+  %51 = icmp sgt i32 %38, 895
+  br i1 %51, label %43, label %52
+
+; <label>:52:                                     ; preds = %50
+  %53 = icmp eq i32 %41, 9
+  %54 = icmp eq i32 %41, 8
+  %55 = or i32 %41, 1
+  %56 = icmp ne i32 %55, 9
+  br i1 %53, label %67, label %57
+
+; <label>:57:                                     ; preds = %52, %67
+  %58 = phi float [ %77, %67 ], [ %39, %52 ]
+  %59 = phi float [ %77, %67 ], [ %40, %52 ]
+  %60 = zext i1 %54 to i32
+  %61 = add i32 %38, %60
+  %62 = zext i1 %56 to i32
+  %63 = add i32 %61, %62
+  %64 = shl i32 %63, 4
+  %65 = load <4 x i32>, <4 x i32> addrspace(4)* %34, align 16, !invariant.load !0
+  %66 = call float @llvm.SI.load.const.v4i32(<4 x i32> %65, i32 %64)
+  br label %37
+
+; <label>:67:                                     ; preds = %52
+  %68 = shl i32 %38, 4
+  %69 = load <4 x i32>, <4 x i32> addrspace(4)* %34, align 16, !invariant.load !0
+  %70 = or i32 %68, 4
+  %71 = call float @llvm.SI.load.const.v4i32(<4 x i32> %69, i32 %70)
+  %72 = add nsw i32 %70, 4
+  %73 = call float @llvm.SI.load.const.v4i32(<4 x i32> %69, i32 %72)
+  %74 = fmul float %18, %71
+  %75 = fmul float %19, %73
+  %76 = fadd float %74, %75
+  %77 = fadd float %40, %76
+  br label %57
+}
+
+; Function Attrs: nounwind readnone speculatable
+declare i8 addrspace(4)* @llvm.amdgcn.implicit.buffer.ptr() #0
+
+; Function Attrs: nounwind readonly
+declare <4 x float> @llvm.amdgcn.buffer.load.v4f32(<4 x i32>, i32, i32, i1, i1) #1
+
+; Function Attrs: nounwind readnone
+declare float @llvm.SI.load.const.v4i32(<4 x i32>, i32) #2
+
+; Function Attrs: nounwind
+declare void @llvm.amdgcn.exp.f32(i32, i32, float, float, float, float, i1, i1) #3
+
+; Function Attrs: nounwind readonly
+declare float @llvm.amdgcn.buffer.load.f32(<4 x i32>, i32, i32, i1, i1) #1
+
+attributes #0 = { nounwind readnone speculatable }
+attributes #1 = { nounwind readonly }
+attributes #2 = { nounwind readnone }
+attributes #3 = { nounwind }
+
+!0 = !{}