[AMDGPU] SILowerControlFlow::optimizeEndCF should remove empty basic block

[alex-t]

Summary

optimizeEndCF removes EXEC restoring instruction case this instruction is the only one except the branch to the single successor and that successor contains EXEC mask restoring instruction that was lowered from END_CF belonging to IF_ELSE.
As a result of such optimization we get the basic block with the only one instruction that is a branch to the single successor.
In case the control flow can reach such an empty block from S_CBRANCH_EXEZ/EXECNZ it might happen that spill/reload instructions that were inserted later by register allocator are placed under exec == 0 condition and never execute.
Removing empty block solves the problem.

This change require further work to re-implement LIS updates. Recently, LIS is always nullptr in this pass. To enable it we need another patch to fix many places across the codegen.

[rampitec]

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

158

Does it preserve MDT and MLI now?

606

It will work differently with and without debug info. Imagine that you have a DBG_VALUE in that block, its size will not be 1 anymore. You also need a mir test axactly the same as you are using but with the DBG_VALUE in that block.

Besides in most cases there is no S_BRANCH at the end, just a fall through to successor.

607

Isn't it the same as MBB.succ_begin()?

609

You can simply initialize Preds vector with MBB.predecessors(), loop is not needed.

627

Need a test for this case.

633

What happens to MBB instructions? Will they be erased or become dangling?

635

MBB is already deleted at this point, it will assert or crash. It also needs to remove all instructions, not just first as there can be DBG_VALUEs.

[arsenm]

Should also add a few cases with other empty block situations, including with debug info.

Also should add an example where the original problem occurred

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

606

what if the block is truly empty?

Should also move all of this to a separate function

613–614

replaceSuccessor

[alex-t]

Changes as requested by reviewer.

[alex-t]

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

158

yes. your initial assumption was a chain of single successors. So, if we remove block, we remove it from that chain.

[alex-t]

In D86634#2240606, @arsenm wrote:

Should also add a few cases with other empty block situations, including with debug info.

Also should add an example where the original problem occurred

All the above in fact are covered in collapse-encf.mir
As for the original problem, it is mostly about placing the spills in the redundant block under exec == 0.
CFG in this example is trivial if-break loop exit and also covered by the existing test.

[rampitec]

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

158

I assume when you remove a block you also need to call at least MLI::removeBlock() and MDT::eraseNode() to call them preserved.

684

You do not need this branch if target is a fall thru block.
You also do not seem a testcase when it is not and this branch is needed.

[alex-t]

Added MachineDominatorTree and MachineLoopInfo update after redundant block removal.

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

158

Oops. Yes. This is correct.
So, given that neither MDT no LI is not used in SILowerControlFlow I'd perfer to remove setPreserved. Otherwise I'd call getAnalysisIfAvailable just to get a pointer and update them. I'm not sure if it worth doing.

684

Removing block we channge MBBs order.
Verifier complains if the new successor is not a branch target and is not "next node" (MBB.getNextNode()).
It consider legal fall thru to the next node only.

The branch is only necessary in case of fall thru to make verifier happy

[rampitec]

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

684

This defeats optimization purpose to reduce control flow. This branch will survive till the end, right?

712

Will this also erase all instructions?

713

I would do it before actually erasing MBB itself.

715

Looks like both MLI and MDT are already destroyed at this point anyway. Do you see any of the analysis available? If not I would just remove it from preserved.

[arsenm]

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

684

You're just missing a call to updateTerminator? You shouldn't need to leave a branch to a fallthrough just to satisfy the verifier

[alex-t]

changed as requested by reviewer

[rampitec]

llvm/test/CodeGen/AMDGPU/collapse-endcf.mir

25–26

I still see redundant branches.

[alex-t]

llvm/test/CodeGen/AMDGPU/collapse-endcf.mir

25–26

It is impossible to remove block without inserting branch. Otherwise I have to rebuild MBBs layout.
Machine Verifier explicitly requires fallthru to be the next item in MBBs list.

 if (Fallthrough && SuccMBB == MBB->getNextNode())
   continue;
report("MBB has unexpected successors which are not branch targets, "
        "fallthrough, EHPads, or inlineasm_br targets.",
        MBB);

[alex-t]

The only difference is that now these redundant branch is inserted by MachineBasicBlock::updateTerminator() as Matt suggested.

[rampitec]

In D86634#2245537, @alex-t wrote:

The only difference is that now these redundant branch is inserted by MachineBasicBlock::updateTerminator() as Matt suggested.

Use MachineFunction::splice() to reinsert block into a proper place?

[alex-t]

No redundant branches anymore

[rampitec]

LGTM, but please run PSDB before submission. This stuff is quite nontrivial.

[alex-t]

diff rebased to latest trunk

[alex-t]

Enhanced PSDB passed

llvm/lib/Target/AMDGPU/SILowerControlFlow.cpp

private:
   void emitLoop(MachineInstr &MI);
   void emitEndCf(MachineInstr &MI);
 
   void findMaskOperands(MachineInstr &MI, unsigned OpNo,
                         SmallVectorImpl<MachineOperand> &Src) const;
 
   void combineMasks(MachineInstr &MI);
 
+  bool removeMBBifRedundant(MachineBasicBlock &MBB);
+
   void process(MachineInstr &MI);
 
   // 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;
StringRef getPassName() const override {
     return "SI Lower control flow pseudo instructions";
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     // Should preserve the same set that TwoAddressInstructions does.
     AU.addPreserved<SlotIndexes>();
     AU.addPreserved<LiveIntervals>();
     AU.addPreservedID(LiveVariablesID);
-    AU.addPreservedID(MachineLoopInfoID);
-    AU.addPreservedID(MachineDominatorsID);
-    AU.setPreservesCFG();
     MachineFunctionPass::getAnalysisUsage(AU);
   }
 };
 
 } // end anonymous namespace
 
 char SILowerControlFlow::ID = 0;
 
for (MachineInstr *MI : LoweredEndCf) {
     assert(SavedExec.isVirtual() && "Expected saved exec to be src1!");
 
     const MachineInstr *Def = MRI->getUniqueVRegDef(SavedExec);
     if (Def && LoweredIf.count(SavedExec)) {
       LLVM_DEBUG(dbgs() << "Skip redundant "; MI->dump());
       if (LIS)
         LIS->RemoveMachineInstrFromMaps(*MI);
       MI->eraseFromParent();
+      removeMBBifRedundant(MBB);
     }
   }
 }
 
 void SILowerControlFlow::process(MachineInstr &MI) {
   MachineBasicBlock &MBB = *MI.getParent();
   MachineBasicBlock::iterator I(MI);
   MachineInstr *Prev = (I != MBB.begin()) ? &*(std::prev(I)) : nullptr;
 
   switch (MI.getOpcode()) {
   case AMDGPU::SI_IF:
     emitIf(MI);
     break;
 
   case AMDGPU::SI_ELSE:
     emitElse(MI);
     break;
 
   case AMDGPU::SI_IF_BREAK:
     emitIfBreak(MI);
     break;
 
   case AMDGPU::SI_LOOP:
     emitLoop(MI);
     break;
 
   case AMDGPU::SI_END_CF:
     emitEndCf(MI);
     break;
 
   default:
     assert(false && "Attempt to process unsupported instruction");
     break;
   }
 
   MachineBasicBlock::iterator Next;
   for (I = Prev ? Prev->getIterator() : MBB.begin(); I != MBB.end(); I = Next) {
case AMDGPU::S_OR_B32:
       break;
     default:
       I = MBB.end();
       break;
     }
   }
 }
 
+bool SILowerControlFlow::removeMBBifRedundant(MachineBasicBlock &MBB) {
+  bool Redundant = true;
+  for (auto &I : MBB.instrs()) {
+    if (!I.isDebugInstr() && !I.isUnconditionalBranch())
+      Redundant = false;
+  }
+  if (Redundant) {
+    MachineBasicBlock *Succ = *MBB.succ_begin();
+    SmallVector<MachineBasicBlock *, 2> Preds(MBB.predecessors());
+    for (auto P : Preds) {
+      P->replaceSuccessor(&MBB, Succ);
+      MachineBasicBlock::iterator I(P->getFirstInstrTerminator());
+      while (I != P->end()) {
+        if (I->isBranch()) {
+          if (TII->getBranchDestBlock(*I) == &MBB) {
+            I->getOperand(0).setMBB(Succ);
+            break;
+          }
+        }
+        I++;
+      }
+      if (I == P->end()) {
+        MachineFunction *MF = P->getParent();
+        MachineFunction::iterator InsertPt =
+            P->getNextNode() ? MachineFunction::iterator(P->getNextNode())
+                             : MF->end();
+        MF->splice(InsertPt, Succ);
+      }
+    }
+    MBB.removeSuccessor(Succ);
+    if (LIS) {
+      for (auto &I : MBB.instrs())
+        LIS->RemoveMachineInstrFromMaps(I);
+    }
+    MBB.clear();
+    MBB.eraseFromParent();
+    return true;
+  }
+  return false;
+}
+
 bool SILowerControlFlow::runOnMachineFunction(MachineFunction &MF) {
   const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
   TII = ST.getInstrInfo();
   TRI = &TII->getRegisterInfo();
 
   // This doesn't actually need LiveIntervals, but we can preserve them.
   LIS = getAnalysisIfAvailable<LiveIntervals>();
   MRI = &MF.getRegInfo();
   BoolRC = TRI->getBoolRC();
   InsertKillCleanups =
       MF.getFunction().getCallingConv() == CallingConv::AMDGPU_PS;
 
   if (ST.isWave32()) {
     AndOpc = AMDGPU::S_AND_B32;
     OrOpc = AMDGPU::S_OR_B32;
     XorOpc = AMDGPU::S_XOR_B32;
     MovTermOpc = AMDGPU::S_MOV_B32_term;
     Andn2TermOpc = AMDGPU::S_ANDN2_B32_term;
     XorTermrOpc = AMDGPU::S_XOR_B32_term;
     OrSaveExecOpc = AMDGPU::S_OR_SAVEEXEC_B32;
     Exec = AMDGPU::EXEC_LO;
   } else {

llvm/test/CodeGen/AMDGPU/collapse-endcf.mir

body:             |
   ; GCN-LABEL: name: simple_nested_if_dbg_value
   ; GCN: bb.0:
   ; GCN:   successors: %bb.1(0x40000000), %bb.4(0x40000000)
   ; GCN:   [[COPY:%[0-9]+]]:sreg_64 = COPY $exec, implicit-def $exec
   ; GCN:   [[S_AND_B64_:%[0-9]+]]:sreg_64 = S_AND_B64 [[COPY]], undef %1:sreg_64, implicit-def dead $scc
   ; GCN:   $exec = S_MOV_B64_term killed [[S_AND_B64_]]
   ; GCN:   S_CBRANCH_EXECZ %bb.4, implicit $exec
   ; GCN: bb.1:
-  ; GCN:   successors: %bb.2(0x40000000), %bb.3(0x40000000)
+  ; GCN:   successors: %bb.2(0x40000000), %bb.4(0x40000000)
   ; GCN:   [[COPY1:%[0-9]+]]:sreg_64 = COPY $exec, implicit-def $exec
   ; GCN:   [[S_AND_B64_1:%[0-9]+]]:sreg_64 = S_AND_B64 [[COPY1]], undef %3:sreg_64, implicit-def dead $scc
   ; GCN:   $exec = S_MOV_B64_term killed [[S_AND_B64_1]]
-  ; GCN:   S_CBRANCH_EXECZ %bb.3, implicit $exec
+  ; GCN:   S_CBRANCH_EXECZ %bb.4, implicit $exec
   ; GCN: bb.2:
-  ; GCN:   successors: %bb.3(0x80000000)
-  ; GCN: bb.3:
   ; GCN:   successors: %bb.4(0x80000000)
-  ; GCN:   DBG_VALUE
   ; GCN: bb.4:
   ; GCN:   $exec = S_OR_B64 $exec, [[COPY]], implicit-def $scc
   ; GCN:   DBG_VALUE
   ; GCN:   S_ENDPGM 0
   bb.0:
     successors: %bb.1, %bb.4
 
     %0:sreg_64 = SI_IF undef %1:sreg_64, %bb.4, implicit-def dead $exec, implicit-def dead $scc, implicit $exec
 
body:             |
   ; GCN-LABEL: name: simple_nested_if_empty_block_between
   ; GCN: bb.0:
   ; GCN:   successors: %bb.5(0x40000000), %bb.1(0x40000000)
   ; GCN:   [[COPY:%[0-9]+]]:sreg_64 = COPY $exec, implicit-def $exec
   ; GCN:   [[S_AND_B64_:%[0-9]+]]:sreg_64 = S_AND_B64 [[COPY]], undef %1:sreg_64, implicit-def dead $scc
   ; GCN:   $exec = S_MOV_B64_term killed [[S_AND_B64_]]
   ; GCN:   S_CBRANCH_EXECZ %bb.5, implicit $exec
   ; GCN: bb.1:
-  ; GCN:   successors: %bb.2(0x40000000), %bb.3(0x40000000)
+  ; GCN:   successors: %bb.2(0x40000000), %bb.4(0x40000000)
   ; GCN:   [[COPY1:%[0-9]+]]:sreg_64 = COPY $exec, implicit-def $exec
   ; GCN:   [[S_AND_B64_1:%[0-9]+]]:sreg_64 = S_AND_B64 [[COPY1]], undef %3:sreg_64, implicit-def dead $scc
   ; GCN:   $exec = S_MOV_B64_term killed [[S_AND_B64_1]]
-  ; GCN:   S_CBRANCH_EXECZ %bb.3, implicit $exec
+  ; GCN:   S_CBRANCH_EXECZ %bb.4, implicit $exec
   ; GCN: bb.2:
-  ; GCN:   successors: %bb.3(0x80000000)
-  ; GCN: bb.3:
   ; GCN:   successors: %bb.4(0x80000000)
   ; GCN: bb.4:
   ; GCN:   successors: %bb.5(0x80000000)
   ; GCN: bb.5:
   ; GCN:   $exec = S_OR_B64 $exec, [[COPY]], implicit-def $scc
   ; GCN:   S_ENDPGM 0
   bb.0:
     %0:sreg_64 = SI_IF undef %1:sreg_64, %bb.4, implicit-def dead $exec, implicit-def dead $scc, implicit $exec
body:             |
   ; GCN-LABEL: name: simple_nested_if_empty_block_dbg_between
   ; GCN: bb.0:
   ; GCN:   successors: %bb.1(0x40000000), %bb.5(0x40000000)
   ; GCN:   [[COPY:%[0-9]+]]:sreg_64 = COPY $exec, implicit-def $exec
   ; GCN:   [[S_AND_B64_:%[0-9]+]]:sreg_64 = S_AND_B64 [[COPY]], undef %1:sreg_64, implicit-def dead $scc
   ; GCN:   $exec = S_MOV_B64_term killed [[S_AND_B64_]]
   ; GCN:   S_CBRANCH_EXECZ %bb.5, implicit $exec
   ; GCN: bb.1:
-  ; GCN:   successors: %bb.2(0x40000000), %bb.3(0x40000000)
+  ; GCN:   successors: %bb.2(0x40000000), %bb.4(0x40000000)
   ; GCN:   [[COPY1:%[0-9]+]]:sreg_64 = COPY $exec, implicit-def $exec
   ; GCN:   [[S_AND_B64_1:%[0-9]+]]:sreg_64 = S_AND_B64 [[COPY1]], undef %3:sreg_64, implicit-def dead $scc
   ; GCN:   $exec = S_MOV_B64_term killed [[S_AND_B64_1]]
-  ; GCN:   S_CBRANCH_EXECZ %bb.3, implicit $exec
+  ; GCN:   S_CBRANCH_EXECZ %bb.4, implicit $exec
   ; GCN: bb.2:
-  ; GCN:   successors: %bb.3(0x80000000)
-  ; GCN: bb.3:
   ; GCN:   successors: %bb.4(0x80000000)
   ; GCN: bb.4:
   ; GCN:   successors: %bb.5(0x80000000)
   ; GCN:   DBG_VALUE
   ; GCN: bb.5:
   ; GCN:   $exec = S_OR_B64 $exec, [[COPY]], implicit-def $scc
   ; GCN:   S_ENDPGM 0
   bb.0:
body:             |
   ; GCN-LABEL: name: simple_nested_if_not_layout_successor
   ; GCN: bb.0:
   ; GCN:   successors: %bb.1(0x40000000), %bb.4(0x40000000)
   ; GCN:   [[COPY:%[0-9]+]]:sreg_64 = COPY $exec, implicit-def $exec
   ; GCN:   [[S_AND_B64_:%[0-9]+]]:sreg_64 = S_AND_B64 [[COPY]], undef %1:sreg_64, implicit-def dead $scc
   ; GCN:   $exec = S_MOV_B64_term killed [[S_AND_B64_]]
   ; GCN:   S_CBRANCH_EXECZ %bb.4, implicit $exec
   ; GCN: bb.1:
-  ; GCN:   successors: %bb.2(0x40000000), %bb.3(0x40000000)
+  ; GCN:   successors: %bb.2(0x40000000), %bb.5(0x40000000)
   ; GCN:   [[COPY1:%[0-9]+]]:sreg_64 = COPY $exec, implicit-def $exec
   ; GCN:   [[S_AND_B64_1:%[0-9]+]]:sreg_64 = S_AND_B64 [[COPY1]], undef %3:sreg_64, implicit-def dead $scc
   ; GCN:   $exec = S_MOV_B64_term killed [[S_AND_B64_1]]
-  ; GCN:   S_CBRANCH_EXECZ %bb.3, implicit $exec
+  ; GCN:   S_CBRANCH_EXECZ %bb.5, implicit $exec
   ; GCN: bb.2:
-  ; GCN:   successors: %bb.3(0x80000000)
-  ; GCN: bb.3:
   ; GCN:   successors: %bb.5(0x80000000)
-  ; GCN:   S_BRANCH %bb.5
-  ; GCN: bb.4:
-  ; GCN:   $exec = S_OR_B64 $exec, [[COPY]], implicit-def $scc
-  ; GCN:   S_ENDPGM 0
   ; GCN: bb.5:
   ; GCN:   successors: %bb.4(0x80000000)
   ; GCN:   S_BRANCH %bb.4
+  ; GCN: bb.4:
+  ; GCN:   $exec = S_OR_B64 $exec, [[COPY]], implicit-def $scc
+  ; GCN:   S_ENDPGM 0
   bb.0:
     successors: %bb.1, %bb.4
 
     %0:sreg_64 = SI_IF undef %1:sreg_64, %bb.4, implicit-def dead $exec, implicit-def dead $scc, implicit $exec
 
   bb.1:
     successors: %bb.2, %bb.3