[AMDGPU] Split edge to make si_if dominate end_cf

[alex-t]

Summary

Basic block containing "if" not necessarily dominates block that is the "false" target for the if.

That "false" target block may have another predecessor besides the "if" block. IR value corresponding to the Exec mask is generated by the

si_if intrinsic and then used by the end_cf intrinsic. In this case IR verifier complains that 'Def does not dominate all uses'.

This change split the edge between the "if" block and "false" target block to make it dominated by the "if" block.

[alex-t]

Test added

[arsenm]

Typos "do,imates" and "another predecessors" in message

llvm/lib/Target/AMDGPU/SIAnnotateControlFlow.cpp

319–322

Is this the same as unconditionally calling SplitCriticalEdge?

llvm/test/CodeGen/AMDGPU/virtual-register-defs-dont-dominate-all-uses.ll

4–6

Don't need these

[alex-t]

llvm/lib/Target/AMDGPU/SIAnnotateControlFlow.cpp

319–322

Not really. Any edge from the block with multiple successors to block with multiple predecessors considered critical. So, changing to unconditional call to SplitCriticalEdge involves a lot of trivial CFG patterns that do not require splitting.

For example:

    "entry"     <--  entry has 2 successors
     /        \
"if.then"   |  <-- this edge is considered as critical
    \         /
      "end"    <-- end has 2 predecessors

At least the isCriticalEdge function in CFG.cpp : line 101 works this way

[alex-t]

The odd lines removed from the test

[alex-t]

Ping!

[arsenm]

llvm/lib/Target/AMDGPU/SIAnnotateControlFlow.cpp

317

This should be a cast since it's unchecked

[alex-t]

dyn_cast changed to cast

[alex-t]

llvm/lib/Target/AMDGPU/SIAnnotateControlFlow.cpp

317

Yes. "Exec" producer is always an Instruction. So cast is okay.

[alex-t]

Ping

[alex-t]

ping

[arsenm]

It seems to me there's more logic going on between the decisions SplitEdge makes and the additional dominates call than should be necessary, but this should be fine

[arsenm]

With this applied, I'm still seeing a verifier error in the original testcase

[alex-t]

Could you share the original testcase then? I only have that reduced one attached to the Jira ticket.
And it works for it.

[arsenm]

In D91435#2450202, @alex-t wrote:

Could you share the original testcase then? I only have that reduced one attached to the Jira ticket.
And it works for it.

OK, the original testcase does actually work. However, I ran into another instance which this patch did not fix which I assumed was the same. I've attached that one to the ticket now

[alex-t]

Bug in SIAnnotateControlFlow fixed: simple CF join should not be treated as loop

[alex-t]

There was a bug in SIAnnotateControlFlow. Visited node is not necessarily means loop. It may be CF join instead.
Added check that Term successor visited and dominates Terms's parent.

[arsenm]

Needs a testcase for the second broken case

[alex-t]

In D91435#2461075, @arsenm wrote:

Needs a testcase for the second broken case

I cannot create a relevant testcase. The CFG pattern that triggers the bug only appears in IR compiled with clang.
The reason is that RegionInfo cannot distinguish regions and treat the whole function as one region. As a result CFG structurizer does nothing with it.
When compiling by LLC structurizer does his job and produces good CFG that does not trigger the bug.
MIR test is problematic as well. We need DivergenceAnalysis to make SIAnnotateCF work correctly. DA requires all the Target information to be able to determine if the target is divergent.
Same time we need to avoid all the passes in between including structurizer. So, MIR test is going to be quite tricky.
I still have no idea how to run tti, divergence and si-annotate-control-flow separately and provide the target information to the "-run-pass'"

[arsenm]

In D91435#2463824, @alex-t wrote:

In D91435#2461075, @arsenm wrote:

Needs a testcase for the second broken case

I cannot create a relevant testcase. The CFG pattern that triggers the bug only appears in IR compiled with clang.

It must be possible, and cannot only appear through clang

The reason is that RegionInfo cannot distinguish regions and treat the whole function as one region. As a result CFG structurizer does nothing with it.
When compiling by LLC structurizer does his job and produces good CFG that does not trigger the bug.
MIR test is problematic as well. We need DivergenceAnalysis to make SIAnnotateCF work correctly. DA requires all the Target information to be able to determine if the target is divergent.

This is an IR test, MIR does not come into this.

I still have no idea how to run tti, divergence and si-annotate-control-flow separately and provide the target information to the "-run-pass'"

You shouldn't be trying to use -run-pass/llc, this is an opt test with the relevant passes and then an end to end ISA run line

[alex-t]

New test created to cover both failed cases:

• end_cf in the block that has yet another predecessor besides that one defining the exec mask
• given the pattern above - not any visited node denotes a loop, only when we have a backedge i.e. block's successor dominates the block.

[arsenm]

There should be both tests, not one larger function that hits both

llvm/test/CodeGen/AMDGPU/virtual-register-defs-dont-dominate-all-uses.ll

4

Can you also add an llc run line?

[arsenm]

llvm/test/CodeGen/AMDGPU/virtual-register-defs-dont-dominate-all-uses.ll

4

Test file name should also be more descriptive of the underlying cause

[alex-t]

In D91435#2470128, @arsenm wrote:

There should be both tests, not one larger function that hits both

This second pattern requires the first one to manifest. So even if I split the tests, the second will contain both patterns.
Does it make sense?
I checked the behavior of the united test commenting out the first fix and the second one - both changes were separately controlled.

[alex-t]

llvm/test/CodeGen/AMDGPU/virtual-register-defs-dont-dominate-all-uses.ll

4

What do you need it for? The purpose of the test is to check that we don't hit an assert.
It also checks the output.
Do you want to ensure if it may be compiled down to the ISA?
Both opt and llc in the same file are inconvenient because is tricky to re-generate the checks if changed.
Moreover. the second case with a loop is only reproducible by running the -si-annotate-control-flow explicitly by opt. Running this case by llc will test nothing because the desired CFG pattern only appears compiling by clang. CFG structurizer will produce structured CFG if the test is launched with LLC.
When running clang the CFG pattern remains unchanged because RegionInfo cannot distinguish the regions and report the whole function as one region. Hence the CFG structurizer does nothing. While running LLC with the same IR RegionPass is able to distinguish regions and structurizer does it's job well, so we don't face the pattern causing the bug.

[alex-t]

The testcase is splitted into 2 separate functions. LLC run line added.

llvm/lib/Target/AMDGPU/SIAnnotateControlFlow.cpp

if (L && L->getHeader() == BB) {
     }
 
     BB = SplitBlockPredecessors(BB, Preds, "endcf.split", DT, LI, nullptr,
                                 false);
   }
 
   Value *Exec = popSaved();
   Instruction *FirstInsertionPt = &*BB->getFirstInsertionPt();
-  if (!isa<UndefValue>(Exec) && !isa<UnreachableInst>(FirstInsertionPt))
+  if (!isa<UndefValue>(Exec) && !isa<UnreachableInst>(FirstInsertionPt)) {
+    Instruction *ExecDef = cast<Instruction>(Exec);
+    BasicBlock *DefBB = ExecDef->getParent();
+    if (!DT->dominates(DefBB, BB)) {
+      // Split edge to make Def dominate Use
+      FirstInsertionPt = &*SplitEdge(DefBB, BB, DT, LI)->getFirstInsertionPt();
+    }
     CallInst::Create(EndCf, Exec, "", FirstInsertionPt);
   }
+}
 
 /// Annotate the control flow with intrinsics so the backend can
 /// recognize if/then/else and loops.
 bool SIAnnotateControlFlow::runOnFunction(Function &F) {
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   DA = &getAnalysis<LegacyDivergenceAnalysis>();
   TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
   const TargetMachine &TM = TPC.getTM<TargetMachine>();
 
   initialize(*F.getParent(), TM.getSubtarget<GCNSubtarget>(F));
-
   for (df_iterator<BasicBlock *> I = df_begin(&F.getEntryBlock()),
        E = df_end(&F.getEntryBlock()); I != E; ++I) {
     BasicBlock *BB = *I;
     BranchInst *Term = dyn_cast<BranchInst>(BB->getTerminator());
 
     if (!Term || Term->isUnconditional()) {
       if (isTopOfStack(BB))
         closeControlFlow(BB);

llvm/test/CodeGen/AMDGPU/virtual-register-defs-dont-dominate-all-uses.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -mtriple=amdgcn-amdhsa -verify-machineinstrs < %s | FileCheck -check-prefix=GCN -check-prefix=SI %s
+
+define hidden void @kernel_path_surface_bounce() {
+; GCN-LABEL: kernel_path_surface_bounce:
+; GCN:       ; %bb.0: ; %bb
+; GCN-NEXT:    s_waitcnt vmcnt(0) expcnt(0) lgkmcnt(0)
+; GCN-NEXT:    s_or_saveexec_b64 s[4:5], -1
+; GCN-NEXT:    buffer_store_dword v40, off, s[0:3], s32 ; 4-byte Folded Spill
+; GCN-NEXT:    s_mov_b64 exec, s[4:5]
+; GCN-NEXT:    v_writelane_b32 v40, s33, 2
+; GCN-NEXT:    s_mov_b32 s33, s32
+; GCN-NEXT:    s_add_u32 s32, s32, 0x400
+; GCN-NEXT:    v_mov_b32_e32 v0, 0
+; GCN-NEXT:    v_mov_b32_e32 v1, 0
+; GCN-NEXT:    flat_load_dword v0, v[0:1]
+; GCN-NEXT:    s_waitcnt vmcnt(0)
+; GCN-NEXT:    v_cmp_gt_i32_e32 vcc, 21, v0
+; GCN-NEXT:    s_and_b64 vcc, exec, vcc
+; GCN-NEXT:    v_writelane_b32 v40, s30, 0
+; GCN-NEXT:    v_writelane_b32 v40, s31, 1
+; GCN-NEXT:    s_cbranch_vccz BB0_3
+; GCN-NEXT:  ; %bb.1: ; %bb4
+; GCN-NEXT:    v_cmp_ne_u32_e32 vcc, 9, v0
+; GCN-NEXT:    s_and_b64 vcc, exec, vcc
+; GCN-NEXT:    s_cbranch_vccnz BB0_4
+; GCN-NEXT:  ; %bb.2: ; %bb7
+; GCN-NEXT:    s_getpc_b64 s[4:5]
+; GCN-NEXT:    s_add_u32 s4, s4, _Z3dotDv3_fS_@rel32@lo+4
+; GCN-NEXT:    s_addc_u32 s5, s5, _Z3dotDv3_fS_@rel32@hi+12
+; GCN-NEXT:    s_swappc_b64 s[30:31], s[4:5]
+; GCN-NEXT:    s_branch BB0_7
+; GCN-NEXT:  BB0_3: ; %bb2
+; GCN-NEXT:    v_cmp_eq_u32_e32 vcc, 21, v0
+; GCN-NEXT:    s_and_b64 vcc, exec, vcc
+; GCN-NEXT:    s_cbranch_vccnz BB0_6
+; GCN-NEXT:  BB0_4: ; %bb9
+; GCN-NEXT:    s_getpc_b64 s[4:5]
+; GCN-NEXT:    s_add_u32 s4, s4, _Z3dotDv3_fS_@rel32@lo+4
+; GCN-NEXT:    s_addc_u32 s5, s5, _Z3dotDv3_fS_@rel32@hi+12
+; GCN-NEXT:    s_swappc_b64 s[30:31], s[4:5]
+; GCN-NEXT:    v_cmp_lt_f32_e32 vcc, 0, v0
+; GCN-NEXT:    s_and_saveexec_b64 s[4:5], vcc
+; GCN-NEXT:    s_cbranch_execnz BB0_7
+; GCN-NEXT:  ; %bb.5: ; %bb9.bb12_crit_edge
+; GCN-NEXT:    s_or_b64 exec, exec, s[4:5]
+; GCN-NEXT:  BB0_6: ; %bb12
+; GCN-NEXT:    v_mov_b32_e32 v2, 0
+; GCN-NEXT:    v_mov_b32_e32 v0, 0
+; GCN-NEXT:    v_mov_b32_e32 v1, 0
+; GCN-NEXT:    flat_store_dword v[0:1], v2
+; GCN-NEXT:  BB0_7: ; %UnifiedReturnBlock
+; GCN-NEXT:    v_readlane_b32 s4, v40, 0
+; GCN-NEXT:    v_readlane_b32 s5, v40, 1
+; GCN-NEXT:    s_sub_u32 s32, s32, 0x400
+; GCN-NEXT:    v_readlane_b32 s33, v40, 2
+; GCN-NEXT:    s_or_saveexec_b64 s[6:7], -1
+; GCN-NEXT:    buffer_load_dword v40, off, s[0:3], s32 ; 4-byte Folded Reload
+; GCN-NEXT:    s_mov_b64 exec, s[6:7]
+; GCN-NEXT:    s_waitcnt vmcnt(0)
+; GCN-NEXT:    s_setpc_b64 s[4:5]
+bb:
+  %i = load i32, i32 addrspace(1)* null, align 16
+  %i1 = icmp slt i32 %i, 21
+  br i1 %i1, label %bb4, label %bb2
+
+bb2:                                              ; preds = %bb
+  %i3 = icmp eq i32 %i, 21
+  br i1 %i3, label %bb12, label %bb9
+
+bb4:                                              ; preds = %bb
+  %i5 = icmp eq i32 %i, 9
+  br i1 %i5, label %bb7, label %bb9
+
+bb6:                                              ; preds = %bb9
+  ret void
+
+bb7:                                              ; preds = %bb4
+  %i8 = call float @_Z3dotDv3_fS_()
+  ret void
+
+bb9:                                              ; preds = %bb4, %bb2
+  %i10 = call float @_Z3dotDv3_fS_()
+  %i11 = fcmp nsz ogt float %i10, 0.000000e+00
+  br i1 %i11, label %bb6, label %bb12
+
+bb12:                                             ; preds = %bb9, %bb2
+  store float 0.000000e+00, float addrspace(1)* null, align 8
+  ret void
+}
+
+declare hidden float @_Z3dotDv3_fS_() local_unnamed_addr