AMDGPU: Skip other terminators before inserting s_cbranch_exec[n]z

[arsenm]

Summary

PHIElimination/createPHISourceCopy inserts non-branch terminators
after the control flow pseudo if a successor phi reads a register
defined by the control flow pseudo. If this happens, we need to split
the expansion of the control flow pseudo to ensure all the branches
are after all of the other mask management instructions.

GlobalISel hit this in testscases that happened to be tail
duplicated. The original testcase still does not work, since the same
problem appears to be present in a later pass.

[arsenm]

Missed test update

[arsenm]

Merge tests. This is apparently not my first attempt to fix this

[nhaehnle]

It's hard to say whether this is really correct given how underdefined the control flow pseudos are, but it seems like a pretty reasonable change to me. Assuming you've properly tested this change, LGTM

[arsenm]

In D84464#2172405, @nhaehnle wrote:

It's hard to say whether this is really correct given how underdefined the control flow pseudos are, but it seems like a pretty reasonable change to me. Assuming you've properly tested this change, LGTM

This isn't the only insert point trick we need to play, it was just only really bad for SI_END_CF before. It needs to be moved to insert itself before lowered phi destination copies. This is the complementary problem on the phi source block side

[arsenm]

2bd72abef0f24d9f7da13af3a43a25409159a87e

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

private:
 
   // Skip to the next instruction, ignoring debug instructions, and trivial
   // block boundaries (blocks that have one (typically fallthrough) successor,
   // and the successor has one predecessor.
   MachineBasicBlock::iterator
   skipIgnoreExecInstsTrivialSucc(MachineBasicBlock &MBB,
                                  MachineBasicBlock::iterator It) const;
 
+  /// Find the insertion point for a new conditional branch.
+  MachineBasicBlock::iterator
+  skipToUncondBrOrEnd(MachineBasicBlock &MBB,
+                      MachineBasicBlock::iterator I) const {
+    assert(I->isTerminator());
+
+    // FIXME: What if we had multiple pre-existing conditional branches?
+    MachineBasicBlock::iterator End = MBB.end();
+    while (I != End && !I->isUnconditionalBranch())
+      ++I;
+    return I;
+  }
+
   // Remove redundant SI_END_CF instructions.
   void optimizeEndCf();
 
 public:
   static char ID;
 
   SILowerControlFlow() : MachineFunctionPass(ID) {}
 
void SILowerControlFlow::emitIf(MachineInstr &MI) {
   }
 
   // Use a copy that is a terminator to get correct spill code placement it with
   // fast regalloc.
   MachineInstr *SetExec =
     BuildMI(MBB, I, DL, TII->get(MovTermOpc), Exec)
     .addReg(Tmp, RegState::Kill);
 
+  // Skip ahead to the unconditional branch in case there are other terminators
+  // present.
+  I = skipToUncondBrOrEnd(MBB, I);
+
   // Insert the S_CBRANCH_EXECZ instruction which will be optimized later
   // during SIRemoveShortExecBranches.
   MachineInstr *NewBr = BuildMI(MBB, I, DL, TII->get(AMDGPU::S_CBRANCH_EXECZ))
                             .add(MI.getOperand(2));
 
   if (!LIS) {
     MI.eraseFromParent();
     return;
if (LIS)
       LIS->InsertMachineInstrInMaps(*And);
   }
 
   MachineInstr *Xor =
     BuildMI(MBB, ElsePt, DL, TII->get(XorTermrOpc), Exec)
     .addReg(Exec)
     .addReg(DstReg);
 
+  // Skip ahead to the unconditional branch in case there are other terminators
+  // present.
+  ElsePt = skipToUncondBrOrEnd(MBB, ElsePt);
+
   MachineInstr *Branch =
       BuildMI(MBB, ElsePt, DL, TII->get(AMDGPU::S_CBRANCH_EXECZ))
           .addMBB(DestBB);
 
   if (!LIS) {
     MI.eraseFromParent();
     return;
   }
void SILowerControlFlow::emitLoop(MachineInstr &MI) {
   MachineBasicBlock &MBB = *MI.getParent();
   const DebugLoc &DL = MI.getDebugLoc();
 
   MachineInstr *AndN2 =
       BuildMI(MBB, &MI, DL, TII->get(Andn2TermOpc), Exec)
           .addReg(Exec)
           .add(MI.getOperand(0));
 
+  auto BranchPt = skipToUncondBrOrEnd(MBB, MI.getIterator());
   MachineInstr *Branch =
-      BuildMI(MBB, &MI, DL, TII->get(AMDGPU::S_CBRANCH_EXECNZ))
+      BuildMI(MBB, BranchPt, DL, TII->get(AMDGPU::S_CBRANCH_EXECNZ))
           .add(MI.getOperand(1));
 
   if (LIS) {
     LIS->ReplaceMachineInstrInMaps(MI, *AndN2);
     LIS->InsertMachineInstrInMaps(*Branch);
   }
 
   MI.eraseFromParent();

llvm/test/CodeGen/AMDGPU/lower-control-flow-other-terminators.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -march=amdgcn -mcpu=fiji -verify-machineinstrs -run-pass=si-lower-control-flow -o - %s | FileCheck %s
+
+# Test si-lower-control-flow insertion points when other terminator
+# instructions are present besides the control flow pseudo and a
+# branch.
+
+
+# There's another terminator instruction between SI_IF and
+# S_BRANCH. The S_CBRANCH_EXECZ should be inserted immediately before
+# S_BRANCH.
+---
+name: other_terminator_sbranch_after_si_if
+tracksRegLiveness: true
+body:             |
+  ; CHECK-LABEL: name: other_terminator_sbranch_after_si_if
+  ; CHECK: bb.0:
+  ; CHECK:   successors: %bb.2(0x40000000), %bb.1(0x40000000)
+  ; CHECK:   liveins: $vgpr0, $vgpr1, $sgpr4_sgpr5
+  ; CHECK:   [[COPY:%[0-9]+]]:vgpr_32 = COPY killed $vgpr0
+  ; CHECK:   [[COPY1:%[0-9]+]]:sreg_64_xexec = COPY $sgpr4_sgpr5
+  ; CHECK:   [[V_CMP_EQ_U32_e64_:%[0-9]+]]:sreg_64_xexec = V_CMP_EQ_U32_e64 0, [[COPY]], implicit $exec
+  ; CHECK:   [[COPY2:%[0-9]+]]:sreg_64 = COPY $exec, implicit-def $exec
+  ; CHECK:   [[S_AND_B64_:%[0-9]+]]:sreg_64 = S_AND_B64 [[COPY2]], [[V_CMP_EQ_U32_e64_]], implicit-def dead $scc
+  ; CHECK:   [[S_XOR_B64_:%[0-9]+]]:sreg_64_xexec = S_XOR_B64 [[S_AND_B64_]], [[COPY2]], implicit-def dead $scc
+  ; CHECK:   $exec = S_MOV_B64_term killed [[S_AND_B64_]]
+  ; CHECK:   [[S_MOV_B64_term:%[0-9]+]]:sreg_64_xexec = S_MOV_B64_term killed [[COPY1]], implicit $exec
+  ; CHECK:   S_CBRANCH_EXECZ %bb.1, implicit $exec
+  ; CHECK:   S_BRANCH %bb.2
+  ; CHECK: bb.1:
+  ; CHECK:   successors: %bb.2(0x80000000)
+  ; CHECK:   S_BRANCH %bb.2
+  ; CHECK: bb.2:
+  ; CHECK:   S_ENDPGM 0, implicit [[S_MOV_B64_term]]
+  bb.0:
+    successors: %bb.2, %bb.1
+    liveins: $vgpr0, $vgpr1, $sgpr4_sgpr5
+
+    %0:vgpr_32 = COPY killed $vgpr0
+    %1:sreg_64_xexec = COPY $sgpr4_sgpr5
+    %2:sreg_64_xexec = V_CMP_EQ_U32_e64 0, %0, implicit $exec
+    %3:sreg_64_xexec = SI_IF %2, %bb.1, implicit-def $exec, implicit-def dead $scc, implicit $exec
+    %4:sreg_64_xexec = S_MOV_B64_term killed %1, implicit $exec
+    S_BRANCH %bb.2
+
+  bb.1:
+    S_BRANCH %bb.2
+
+  bb.2:
+    S_ENDPGM 0, implicit %4
+
+...
+
+# S_CBRANCH_EXECZ should be inserted after the other terminator
+---
+name: other_terminator_fallthrough_after_si_if
+tracksRegLiveness: true
+body:             |
+  ; CHECK-LABEL: name: other_terminator_fallthrough_after_si_if
+  ; CHECK: bb.0:
+  ; CHECK:   successors: %bb.2(0x40000000), %bb.1(0x40000000)
+  ; CHECK:   liveins: $vgpr0, $vgpr1, $sgpr4_sgpr5
+  ; CHECK:   [[COPY:%[0-9]+]]:vgpr_32 = COPY killed $vgpr0
+  ; CHECK:   [[COPY1:%[0-9]+]]:sreg_64_xexec = COPY $sgpr4_sgpr5
+  ; CHECK:   [[V_CMP_EQ_U32_e64_:%[0-9]+]]:sreg_64_xexec = V_CMP_EQ_U32_e64 0, [[COPY]], implicit $exec
+  ; CHECK:   [[COPY2:%[0-9]+]]:sreg_64 = COPY $exec, implicit-def $exec
+  ; CHECK:   [[S_AND_B64_:%[0-9]+]]:sreg_64 = S_AND_B64 [[COPY2]], [[V_CMP_EQ_U32_e64_]], implicit-def dead $scc
+  ; CHECK:   [[S_XOR_B64_:%[0-9]+]]:sreg_64_xexec = S_XOR_B64 [[S_AND_B64_]], [[COPY2]], implicit-def dead $scc
+  ; CHECK:   $exec = S_MOV_B64_term killed [[S_AND_B64_]]
+  ; CHECK:   [[S_MOV_B64_term:%[0-9]+]]:sreg_64_xexec = S_MOV_B64_term killed [[COPY1]], implicit $exec
+  ; CHECK:   S_CBRANCH_EXECZ %bb.2, implicit $exec
+  ; CHECK: bb.1:
+  ; CHECK:   successors: %bb.2(0x80000000)
+  ; CHECK:   S_BRANCH %bb.2
+  ; CHECK: bb.2:
+  ; CHECK:   S_ENDPGM 0, implicit [[S_MOV_B64_term]]
+  bb.0:
+    successors: %bb.2, %bb.1
+    liveins: $vgpr0, $vgpr1, $sgpr4_sgpr5
+
+    %0:vgpr_32 = COPY killed $vgpr0
+    %1:sreg_64_xexec = COPY $sgpr4_sgpr5
+    %2:sreg_64_xexec = V_CMP_EQ_U32_e64 0, %0, implicit $exec
+    %3:sreg_64_xexec = SI_IF %2, %bb.2, implicit-def $exec, implicit-def dead $scc, implicit $exec
+    %4:sreg_64_xexec = S_MOV_B64_term killed %1, implicit $exec
+
+  bb.1:
+    S_BRANCH %bb.2
+
+  bb.2:
+    S_ENDPGM 0, implicit %4
+
+...
+
+---
+name: other_terminator_sbranch_after_si_else
+tracksRegLiveness: true
+body:             |
+  ; CHECK-LABEL: name: other_terminator_sbranch_after_si_else
+  ; CHECK: bb.0:
+  ; CHECK:   successors: %bb.2(0x40000000), %bb.1(0x40000000)
+  ; CHECK:   liveins: $vgpr0, $vgpr1, $sgpr4_sgpr5
+  ; CHECK:   [[COPY:%[0-9]+]]:sreg_64 = COPY %2
+  ; CHECK:   [[S_OR_SAVEEXEC_B64_:%[0-9]+]]:sreg_64_xexec = S_OR_SAVEEXEC_B64 [[COPY]], implicit-def $exec, implicit-def $scc, implicit $exec
+  ; CHECK:   [[COPY1:%[0-9]+]]:vgpr_32 = COPY killed $vgpr0
+  ; CHECK:   [[COPY2:%[0-9]+]]:sreg_64_xexec = COPY $sgpr4_sgpr5
+  ; CHECK:   [[V_CMP_EQ_U32_e64_:%[0-9]+]]:sreg_64_xexec = V_CMP_EQ_U32_e64 0, [[COPY1]], implicit $exec
+  ; CHECK:   $exec = S_XOR_B64_term $exec, [[S_OR_SAVEEXEC_B64_]], implicit-def $scc
+  ; CHECK:   [[S_MOV_B64_term:%[0-9]+]]:sreg_64_xexec = S_MOV_B64_term killed [[COPY2]], implicit $exec
+  ; CHECK:   S_CBRANCH_EXECZ %bb.1, implicit $exec
+  ; CHECK:   S_BRANCH %bb.2
+  ; CHECK: bb.1:
+  ; CHECK:   successors: %bb.2(0x80000000)
+  ; CHECK:   S_BRANCH %bb.2
+  ; CHECK: bb.2:
+  ; CHECK:   S_ENDPGM 0, implicit [[S_MOV_B64_term]]
+  bb.0:
+    successors: %bb.2, %bb.1
+    liveins: $vgpr0, $vgpr1, $sgpr4_sgpr5
+
+    %0:vgpr_32 = COPY killed $vgpr0
+    %1:sreg_64_xexec = COPY $sgpr4_sgpr5
+    %2:sreg_64_xexec = V_CMP_EQ_U32_e64 0, %0, implicit $exec
+    %3:sreg_64_xexec = SI_ELSE %2, %bb.1, 0, implicit-def $exec, implicit-def dead $scc, implicit $exec
+    %4:sreg_64_xexec = S_MOV_B64_term killed %1, implicit $exec
+    S_BRANCH %bb.2
+
+  bb.1:
+    S_BRANCH %bb.2
+
+  bb.2:
+    S_ENDPGM 0, implicit %4
+
+...
+
+---
+name: other_terminator_sbranch_after_si_loop
+tracksRegLiveness: true
+body:             |
+  ; CHECK-LABEL: name: other_terminator_sbranch_after_si_loop
+  ; CHECK: bb.0:
+  ; CHECK:   successors: %bb.2(0x40000000), %bb.1(0x40000000)
+  ; CHECK:   liveins: $vgpr0, $vgpr1, $sgpr4_sgpr5
+  ; CHECK:   [[COPY:%[0-9]+]]:vgpr_32 = COPY killed $vgpr0
+  ; CHECK:   [[COPY1:%[0-9]+]]:sreg_64_xexec = COPY $sgpr4_sgpr5
+  ; CHECK:   [[V_CMP_EQ_U32_e64_:%[0-9]+]]:sreg_64_xexec = V_CMP_EQ_U32_e64 0, [[COPY]], implicit $exec
+  ; CHECK:   $exec = S_ANDN2_B64_term $exec, [[V_CMP_EQ_U32_e64_]], implicit-def $scc
+  ; CHECK:   [[S_MOV_B64_term:%[0-9]+]]:sreg_64_xexec = S_MOV_B64_term killed [[COPY1]], implicit $exec
+  ; CHECK:   S_CBRANCH_EXECNZ %bb.1, implicit $exec
+  ; CHECK:   S_BRANCH %bb.2
+  ; CHECK: bb.1:
+  ; CHECK:   successors: %bb.2(0x80000000)
+  ; CHECK:   S_BRANCH %bb.2
+  ; CHECK: bb.2:
+  ; CHECK:   S_ENDPGM 0, implicit [[S_MOV_B64_term]]
+  bb.0:
+    successors: %bb.2, %bb.1
+    liveins: $vgpr0, $vgpr1, $sgpr4_sgpr5
+
+    %0:vgpr_32 = COPY killed $vgpr0
+    %1:sreg_64_xexec = COPY $sgpr4_sgpr5
+    %2:sreg_64_xexec = V_CMP_EQ_U32_e64 0, %0, implicit $exec
+    SI_LOOP %2, %bb.1, implicit-def $exec, implicit-def dead $scc, implicit $exec
+    %4:sreg_64_xexec = S_MOV_B64_term killed %1, implicit $exec
+    S_BRANCH %bb.2
+
+  bb.1:
+    S_BRANCH %bb.2
+
+  bb.2:
+    S_ENDPGM 0, implicit %4
+
+...

llvm/test/CodeGen/AMDGPU/si-if-lower-user-terminators.mir

body:             |
   ; CHECK:   liveins: $vgpr0, $vgpr1, $sgpr30_sgpr31
   ; CHECK:   [[COPY:%[0-9]+]]:vgpr_32 = COPY killed $vgpr0
   ; CHECK:   [[COPY1:%[0-9]+]]:vgpr_32 = COPY killed $vgpr1
   ; CHECK:   [[V_CMP_EQ_U32_e64_:%[0-9]+]]:sreg_64_xexec = V_CMP_EQ_U32_e64 killed [[COPY]], killed [[COPY1]], implicit $exec
   ; CHECK:   [[COPY2:%[0-9]+]]:sreg_64 = COPY $exec, implicit-def $exec
   ; CHECK:   [[S_AND_B64_:%[0-9]+]]:sreg_64 = S_AND_B64 [[COPY2]], [[V_CMP_EQ_U32_e64_]], implicit-def dead $scc
   ; CHECK:   [[S_XOR_B64_:%[0-9]+]]:sreg_64_xexec = S_XOR_B64 [[S_AND_B64_]], [[COPY2]], implicit-def dead $scc
   ; CHECK:   $exec = S_MOV_B64_term killed [[S_AND_B64_]]
-  ; CHECK:   S_CBRANCH_EXECZ %bb.1, implicit $exec
   ; CHECK:   [[S_MOV_B64_term:%[0-9]+]]:sreg_64_xexec = S_MOV_B64_term [[S_XOR_B64_]], implicit $exec
   ; CHECK:   [[S_MOV_B64_term1:%[0-9]+]]:sreg_64_xexec = S_MOV_B64_term [[S_XOR_B64_]], implicit $exec
+  ; CHECK:   S_CBRANCH_EXECZ %bb.1, implicit $exec
   ; CHECK:   S_BRANCH %bb.2
   ; CHECK: bb.1:
   ; CHECK:   successors: %bb.2(0x80000000)
   ; CHECK:   [[COPY3:%[0-9]+]]:sreg_64_xexec = COPY [[S_MOV_B64_term1]]
   ; CHECK:   dead %7:vgpr_32 = GLOBAL_LOAD_DWORD undef %8:vreg_64, 0, 0, 0, 0, implicit $exec :: (volatile load 4, addrspace 1)
   ; CHECK:   [[COPY4:%[0-9]+]]:sreg_64_xexec = COPY [[COPY3]]
   ; CHECK: bb.2:
   ; CHECK:   successors: %bb.1(0x40000000), %bb.2(0x40000000)
   ; CHECK:   [[COPY5:%[0-9]+]]:sreg_64_xexec = COPY [[COPY4]]
   ; CHECK:   $exec = S_OR_B64 $exec, killed [[COPY5]], implicit-def $scc
   ; CHECK:   S_SLEEP 1
   ; CHECK:   [[COPY6:%[0-9]+]]:sreg_64 = COPY $exec, implicit-def $exec
   ; CHECK:   [[S_AND_B64_1:%[0-9]+]]:sreg_64 = S_AND_B64 [[COPY6]], [[V_CMP_EQ_U32_e64_]], implicit-def dead $scc
   ; CHECK:   [[S_XOR_B64_1:%[0-9]+]]:sreg_64_xexec = S_XOR_B64 [[S_AND_B64_1]], [[COPY6]], implicit-def dead $scc
   ; CHECK:   $exec = S_MOV_B64_term killed [[S_AND_B64_1]]
-  ; CHECK:   S_CBRANCH_EXECZ %bb.1, implicit $exec
   ; CHECK:   [[S_MOV_B64_term1:%[0-9]+]]:sreg_64_xexec = S_MOV_B64_term [[S_XOR_B64_1]], implicit $exec
   ; CHECK:   [[S_MOV_B64_term2:%[0-9]+]]:sreg_64_xexec = S_MOV_B64_term [[S_XOR_B64_1]], implicit $exec
+  ; CHECK:   S_CBRANCH_EXECZ %bb.1, implicit $exec
   ; CHECK:   S_BRANCH %bb.2
   bb.0:
     liveins: $vgpr0, $vgpr1, $sgpr30_sgpr31
 
     %0:vgpr_32 = COPY killed $vgpr0
     %1:vgpr_32 = COPY killed $vgpr1
     %3:sreg_64_xexec = V_CMP_EQ_U32_e64 killed %0, killed %1, implicit $exec
     %10:sreg_64_xexec = SI_IF %3, %bb.1, implicit-def $exec, implicit-def dead $scc, implicit $exec