[AMDGPU] Rename SIInsertSkips Pass

[critson]

Summary

Pass no longer handles skips. Pass now removes unnecessary
unconditional branches and lowers early termination branches.
Hence rename to SILateBranchLowering.

Move code to handle returns to epilog from SIPreEmitPeephole
into SILateBranchLowering. This means SIPreEmitPeephole only
contains optional optimisations, and all required transforms
are in SILateBranchLowering.

[foad]

Seems fine to me but I'll leave it for someone who knows this code better to accept it.

[arsenm]

I still think something is off where we need yet another control flow lowering pass, but that's a battle for another day. This at least makes the name less misleading

llvm/lib/Target/AMDGPU/AMDGPU.h

 extern char &SIWholeQuadModeID;
 
 void initializeSILowerControlFlowPass(PassRegistry &);
 extern char &SILowerControlFlowID;
 
 void initializeSIPreEmitPeepholePass(PassRegistry &);
 extern char &SIPreEmitPeepholeID;
 
-void initializeSIInsertSkipsPass(PassRegistry &);
-extern char &SIInsertSkipsPassID;
+void initializeSILateBranchLoweringPass(PassRegistry &);
+extern char &SILateBranchLoweringPassID;
 
 void initializeSIOptimizeExecMaskingPass(PassRegistry &);
 extern char &SIOptimizeExecMaskingID;
 
 void initializeSIPreAllocateWWMRegsPass(PassRegistry &);
 extern char &SIPreAllocateWWMRegsID;
 
 void initializeAMDGPUSimplifyLibCallsPass(PassRegistry &);

llvm/lib/Target/AMDGPU/AMDGPUTargetMachine.cpp

extern "C" LLVM_EXTERNAL_VISIBILITY void LLVMInitializeAMDGPUTarget() {
   initializeAMDGPUUnifyMetadataPass(*PR);
   initializeSIAnnotateControlFlowPass(*PR);
   initializeSIInsertHardClausesPass(*PR);
   initializeSIInsertWaitcntsPass(*PR);
   initializeSIModeRegisterPass(*PR);
   initializeSIWholeQuadModePass(*PR);
   initializeSILowerControlFlowPass(*PR);
   initializeSIPreEmitPeepholePass(*PR);
-  initializeSIInsertSkipsPass(*PR);
+  initializeSILateBranchLoweringPass(*PR);
   initializeSIMemoryLegalizerPass(*PR);
   initializeSIOptimizeExecMaskingPass(*PR);
   initializeSIPreAllocateWWMRegsPass(*PR);
   initializeSIFormMemoryClausesPass(*PR);
   initializeSIPostRABundlerPass(*PR);
   initializeAMDGPUUnifyDivergentExitNodesPass(*PR);
   initializeAMDGPUAAWrapperPassPass(*PR);
   initializeAMDGPUExternalAAWrapperPass(*PR);
void GCNPassConfig::addPreEmitPass() {
   addPass(createSIMemoryLegalizerPass());
   addPass(createSIInsertWaitcntsPass());
   addPass(createSIShrinkInstructionsPass());
   addPass(createSIModeRegisterPass());
 
   if (getOptLevel() > CodeGenOpt::None)
     addPass(&SIInsertHardClausesID);
 
-  addPass(&SIInsertSkipsPassID);
+  addPass(&SILateBranchLoweringPassID);
+  if (getOptLevel() > CodeGenOpt::None)
     addPass(&SIPreEmitPeepholeID);
   // The hazard recognizer that runs as part of the post-ra scheduler does not
   // guarantee to be able handle all hazards correctly. This is because if there
   // are multiple scheduling regions in a basic block, the regions are scheduled
   // bottom up, so when we begin to schedule a region we don't know what
   // instructions were emitted directly before it.
   //
   // Here we add a stand-alone hazard recognizer pass which can handle all
   // cases.

llvm/lib/Target/AMDGPU/CMakeLists.txt

add_llvm_target(AMDGPUCodeGen
   SIAnnotateControlFlow.cpp
   SIFixSGPRCopies.cpp
   SIFixVGPRCopies.cpp
   SIPreAllocateWWMRegs.cpp
   SIFoldOperands.cpp
   SIFormMemoryClauses.cpp
   SIFrameLowering.cpp
   SIInsertHardClauses.cpp
-  SIInsertSkips.cpp
+  SILateBranchLowering.cpp
   SIInsertWaitcnts.cpp
   SIInstrInfo.cpp
   SIISelLowering.cpp
   SILoadStoreOptimizer.cpp
   SILowerControlFlow.cpp
   SILowerI1Copies.cpp
   SILowerSGPRSpills.cpp
   SIMachineFunctionInfo.cpp

llvm/lib/Target/AMDGPU/SILateBranchLowering.cpp

-//===-- SIInsertSkips.cpp - Use predicates for control flow ---------------===//
+//===-- SILateBranchLowering.cpp - Final preparation of branches ----------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 /// \file
 /// This pass mainly lowers early terminate pseudo instructions.
 //
 //===----------------------------------------------------------------------===//
 
 #include "AMDGPU.h"
 #include "GCNSubtarget.h"
 #include "MCTargetDesc/AMDGPUMCTargetDesc.h"
-#include "llvm/ADT/DepthFirstIterator.h"
+#include "SIMachineFunctionInfo.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/InitializePasses.h"
 
 using namespace llvm;
 
-#define DEBUG_TYPE "si-insert-skips"
+#define DEBUG_TYPE "si-late-branch-lowering"
 
 namespace {
 
-class SIInsertSkips : public MachineFunctionPass {
+class SILateBranchLowering : public MachineFunctionPass {
 private:
   const SIRegisterInfo *TRI = nullptr;
   const SIInstrInfo *TII = nullptr;
   MachineDominatorTree *MDT = nullptr;
 
-  MachineBasicBlock *EarlyExitBlock = nullptr;
-  bool EarlyExitClearsExec = false;
-
-  void ensureEarlyExitBlock(MachineBasicBlock &MBB, bool ClearExec);
-
-  void earlyTerm(MachineInstr &MI);
+  void earlyTerm(MachineInstr &MI, MachineBasicBlock *EarlyExitBlock);
 
 public:
   static char ID;
 
   unsigned MovOpc;
   Register ExecReg;
 
-  SIInsertSkips() : MachineFunctionPass(ID) {}
+  SILateBranchLowering() : MachineFunctionPass(ID) {}
 
   bool runOnMachineFunction(MachineFunction &MF) override;
 
   StringRef getPassName() const override {
-    return "SI insert s_cbranch_execz instructions";
+    return "SI Final Branch Preparation";
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<MachineDominatorTree>();
     AU.addPreserved<MachineDominatorTree>();
     MachineFunctionPass::getAnalysisUsage(AU);
   }
 };
 
 } // end anonymous namespace
 
-char SIInsertSkips::ID = 0;
+char SILateBranchLowering::ID = 0;
 
-INITIALIZE_PASS_BEGIN(SIInsertSkips, DEBUG_TYPE,
+INITIALIZE_PASS_BEGIN(SILateBranchLowering, DEBUG_TYPE,
                       "SI insert s_cbranch_execz instructions", false, false)
 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
-INITIALIZE_PASS_END(SIInsertSkips, DEBUG_TYPE,
+INITIALIZE_PASS_END(SILateBranchLowering, DEBUG_TYPE,
                     "SI insert s_cbranch_execz instructions", false, false)
 
-char &llvm::SIInsertSkipsPassID = SIInsertSkips::ID;
+char &llvm::SILateBranchLoweringPassID = SILateBranchLowering::ID;
 
 static void generateEndPgm(MachineBasicBlock &MBB,
                            MachineBasicBlock::iterator I, DebugLoc DL,
                            const SIInstrInfo *TII, bool IsPS) {
   // "null export"
   if (IsPS) {
     BuildMI(MBB, I, DL, TII->get(AMDGPU::EXP_DONE))
         .addImm(AMDGPU::Exp::ET_NULL)
         .addReg(AMDGPU::VGPR0, RegState::Undef)
         .addReg(AMDGPU::VGPR0, RegState::Undef)
         .addReg(AMDGPU::VGPR0, RegState::Undef)
         .addReg(AMDGPU::VGPR0, RegState::Undef)
         .addImm(1)  // vm
         .addImm(0)  // compr
         .addImm(0); // en
   }
   // s_endpgm
   BuildMI(MBB, I, DL, TII->get(AMDGPU::S_ENDPGM)).addImm(0);
 }
 
-void SIInsertSkips::ensureEarlyExitBlock(MachineBasicBlock &MBB,
-                                         bool ClearExec) {
-  MachineFunction *MF = MBB.getParent();
-  DebugLoc DL;
-
-  if (!EarlyExitBlock) {
-    EarlyExitBlock = MF->CreateMachineBasicBlock();
-    MF->insert(MF->end(), EarlyExitBlock);
-    generateEndPgm(*EarlyExitBlock, EarlyExitBlock->end(), DL, TII,
-                   MF->getFunction().getCallingConv() ==
-                       CallingConv::AMDGPU_PS);
-    EarlyExitClearsExec = false;
-  }
-
-  if (ClearExec && !EarlyExitClearsExec) {
-    auto ExitI = EarlyExitBlock->getFirstNonPHI();
-    BuildMI(*EarlyExitBlock, ExitI, DL, TII->get(MovOpc), ExecReg).addImm(0);
-    EarlyExitClearsExec = true;
-  }
-}
-
 static void splitBlock(MachineBasicBlock &MBB, MachineInstr &MI,
                        MachineDominatorTree *MDT) {
   MachineBasicBlock *SplitBB = MBB.splitAt(MI, /*UpdateLiveIns*/ true);
 
   // Update dominator tree
   using DomTreeT = DomTreeBase<MachineBasicBlock>;
   SmallVector<DomTreeT::UpdateType, 16> DTUpdates;
   for (MachineBasicBlock *Succ : SplitBB->successors()) {
     DTUpdates.push_back({DomTreeT::Insert, SplitBB, Succ});
     DTUpdates.push_back({DomTreeT::Delete, &MBB, Succ});
   }
   DTUpdates.push_back({DomTreeT::Insert, &MBB, SplitBB});
   MDT->getBase().applyUpdates(DTUpdates);
 }
 
-void SIInsertSkips::earlyTerm(MachineInstr &MI) {
+void SILateBranchLowering::earlyTerm(MachineInstr &MI,
+                                     MachineBasicBlock *EarlyExitBlock) {
   MachineBasicBlock &MBB = *MI.getParent();
   const DebugLoc DL = MI.getDebugLoc();
 
-  ensureEarlyExitBlock(MBB, true);
-
   auto BranchMI = BuildMI(MBB, MI, DL, TII->get(AMDGPU::S_CBRANCH_SCC0))
                       .addMBB(EarlyExitBlock);
   auto Next = std::next(MI.getIterator());
 
   if (Next != MBB.end() && !Next->isTerminator())
     splitBlock(MBB, *BranchMI, MDT);
 
   MBB.addSuccessor(EarlyExitBlock);
   MDT->getBase().insertEdge(&MBB, EarlyExitBlock);
 }
 
-bool SIInsertSkips::runOnMachineFunction(MachineFunction &MF) {
+bool SILateBranchLowering::runOnMachineFunction(MachineFunction &MF) {
   const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
   TII = ST.getInstrInfo();
   TRI = &TII->getRegisterInfo();
   MDT = &getAnalysis<MachineDominatorTree>();
 
   MovOpc = ST.isWave32() ? AMDGPU::S_MOV_B32 : AMDGPU::S_MOV_B64;
   ExecReg = ST.isWave32() ? AMDGPU::EXEC_LO : AMDGPU::EXEC;
 
   SmallVector<MachineInstr *, 4> EarlyTermInstrs;
+  SmallVector<MachineInstr *, 1> EpilogInstrs;
   bool MadeChange = false;
 
   for (MachineBasicBlock &MBB : MF) {
     MachineBasicBlock::iterator I, Next;
     for (I = MBB.begin(); I != MBB.end(); I = Next) {
       Next = std::next(I);
       MachineInstr &MI = *I;
 
       switch (MI.getOpcode()) {
       case AMDGPU::S_BRANCH:
         // Optimize out branches to the next block.
-        // FIXME: Shouldn't this be handled by BranchFolding?
+        // This only occurs in -O0 when BranchFolding is not executed.
         if (MBB.isLayoutSuccessor(MI.getOperand(0).getMBB())) {
           assert(&MI == &MBB.back());
           MI.eraseFromParent();
           MadeChange = true;
         }
         break;
 
       case AMDGPU::SI_EARLY_TERMINATE_SCC0:
         EarlyTermInstrs.push_back(&MI);
         break;
 
+      case AMDGPU::SI_RETURN_TO_EPILOG:
+        EpilogInstrs.push_back(&MI);
+        break;
+
       default:
         break;
       }
     }
   }
 
+  // Lower any early exit branches first
+  if (!EarlyTermInstrs.empty()) {
+    MachineBasicBlock *EarlyExitBlock = MF.CreateMachineBasicBlock();
+    DebugLoc DL;
+
+    MF.insert(MF.end(), EarlyExitBlock);
+    BuildMI(*EarlyExitBlock, EarlyExitBlock->end(), DL, TII->get(MovOpc),
+            ExecReg)
+        .addImm(0);
+    generateEndPgm(*EarlyExitBlock, EarlyExitBlock->end(), DL, TII,
+                   MF.getFunction().getCallingConv() == CallingConv::AMDGPU_PS);
+
     for (MachineInstr *Instr : EarlyTermInstrs) {
       // Early termination in GS does nothing
       if (MF.getFunction().getCallingConv() != CallingConv::AMDGPU_GS)
-      earlyTerm(*Instr);
+        earlyTerm(*Instr, EarlyExitBlock);
       Instr->eraseFromParent();
     }
+
     EarlyTermInstrs.clear();
-  EarlyExitBlock = nullptr;
+    MadeChange = true;
+  }
+
+  // Now check return to epilog instructions occur at function end
+  if (!EpilogInstrs.empty()) {
+    MachineBasicBlock *EmptyMBBAtEnd = nullptr;
+    assert(!MF.getInfo<SIMachineFunctionInfo>()->returnsVoid());
+
+    // If there are multiple returns to epilog then all will
+    // become jumps to new empty end block.
+    if (EpilogInstrs.size() > 1) {
+      EmptyMBBAtEnd = MF.CreateMachineBasicBlock();
+      MF.insert(MF.end(), EmptyMBBAtEnd);
+    }
+
+    for (auto MI : EpilogInstrs) {
+      auto MBB = MI->getParent();
+      if (MBB == &MF.back() && MI == &MBB->back())
+        continue;
+
+      // SI_RETURN_TO_EPILOG is not the last instruction.
+      // Jump to empty block at function end.
+      if (!EmptyMBBAtEnd) {
+        EmptyMBBAtEnd = MF.CreateMachineBasicBlock();
+        MF.insert(MF.end(), EmptyMBBAtEnd);
+      }
+
+      MBB->addSuccessor(EmptyMBBAtEnd);
+      BuildMI(*MBB, MI, MI->getDebugLoc(), TII->get(AMDGPU::S_BRANCH))
+          .addMBB(EmptyMBBAtEnd);
+      MI->eraseFromParent();
+      MadeChange = true;
+    }
+
+    EpilogInstrs.clear();
+  }
 
   return MadeChange;
 }

llvm/lib/Target/AMDGPU/SIPreEmitPeephole.cpp

 //===-- SIPreEmitPeephole.cpp ------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 /// \file
 /// This pass performs the peephole optimizations before code emission.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "AMDGPU.h"
 #include "GCNSubtarget.h"
 #include "MCTargetDesc/AMDGPUMCTargetDesc.h"
-#include "SIMachineFunctionInfo.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "si-pre-emit-peephole"
 
 static unsigned SkipThreshold;
 
bool SIPreEmitPeephole::removeExeczBranch(MachineInstr &MI,
 
   return true;
 }
 
 bool SIPreEmitPeephole::runOnMachineFunction(MachineFunction &MF) {
   const GCNSubtarget &ST = MF.getSubtarget<GCNSubtarget>();
   TII = ST.getInstrInfo();
   TRI = &TII->getRegisterInfo();
-  MachineBasicBlock *EmptyMBBAtEnd = nullptr;
   bool Changed = false;
 
   MF.RenumberBlocks();
 
   for (MachineBasicBlock &MBB : MF) {
     MachineBasicBlock::iterator MBBE = MBB.getFirstTerminator();
     MachineBasicBlock::iterator TermI = MBBE;
     // Check first terminator for branches to optimize
     if (TermI != MBB.end()) {
       MachineInstr &MI = *TermI;
       switch (MI.getOpcode()) {
       case AMDGPU::S_CBRANCH_VCCZ:
       case AMDGPU::S_CBRANCH_VCCNZ:
         Changed |= optimizeVccBranch(MI);
         continue;
       case AMDGPU::S_CBRANCH_EXECZ:
         Changed |= removeExeczBranch(MI, MBB);
         continue;
       default:
         break;
       }
     }
-    // Check all terminators for SI_RETURN_TO_EPILOG
-    // FIXME: This is not an optimization and should be moved somewhere else.
-    while (TermI != MBB.end()) {
-      MachineInstr &MI = *TermI;
-      if (MI.getOpcode() == AMDGPU::SI_RETURN_TO_EPILOG) {
-        assert(!MF.getInfo<SIMachineFunctionInfo>()->returnsVoid());
-
-        // Graphics shaders returning non-void shouldn't contain S_ENDPGM,
-        // because external bytecode will be appended at the end.
-        if (&MBB != &MF.back() || &MI != &MBB.back()) {
-          // SI_RETURN_TO_EPILOG is not the last instruction. Add an empty block
-          // at the end and jump there.
-          if (!EmptyMBBAtEnd) {
-            EmptyMBBAtEnd = MF.CreateMachineBasicBlock();
-            MF.insert(MF.end(), EmptyMBBAtEnd);
-          }
-
-          MBB.addSuccessor(EmptyMBBAtEnd);
-          BuildMI(MBB, &MI, MI.getDebugLoc(), TII->get(AMDGPU::S_BRANCH))
-              .addMBB(EmptyMBBAtEnd);
-          MI.eraseFromParent();
-          MBBE = MBB.getFirstTerminator();
-          TermI = MBBE;
-          continue;
-        }
-      }
-      TermI++;
-    }
 
     if (!ST.hasVGPRIndexMode())
       continue;
 
     MachineInstr *SetGPRMI = nullptr;
     const unsigned Threshold = 20;
     unsigned Count = 0;
     // Scan the block for two S_SET_GPR_IDX_ON instructions to see if a

llvm/test/CodeGen/AMDGPU/early-term.mir

 # NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
-# RUN: llc -march=amdgcn -mcpu=gfx1010 -run-pass=si-insert-skips -verify-machineinstrs  %s -o - | FileCheck %s
+# RUN: llc -march=amdgcn -mcpu=gfx1010 -run-pass=si-late-branch-lowering -verify-machineinstrs  %s -o - | FileCheck %s
 
 --- |
   define amdgpu_ps void @early_term_scc0_end_block() {
     ret void
   }
 
   define amdgpu_ps void @early_term_scc0_next_terminator() {
     ret void

llvm/test/CodeGen/AMDGPU/kill-infinite-loop.ll

end:
   call void @llvm.amdgcn.exp.compr.v2i16(i32 0, i32 5, <2 x i16> < i16 0, i16 0 >, <2 x i16> < i16 0, i16 0 >, i1 true, i1 true) #3
   ret void
 }
 
 ; test the case where there's only a kill in an infinite loop
 ; CHECK-LABEL: only_kill
 ; CHECK: exp null off, off, off, off done vm
 ; CHECK-NEXT: s_endpgm
-; SIInsertSkips inserts an extra null export here, but it should be harmless.
+; SILateBranchLowering inserts an extra null export here, but it should be harmless.
 ; CHECK: exp null off, off, off, off done vm
 ; CHECK-NEXT: s_endpgm
 define amdgpu_ps void @only_kill() #0 {
 main_body:
   br label %loop
 
 loop:
   call void @llvm.amdgcn.kill(i1 false) #3

llvm/test/CodeGen/AMDGPU/readlane_exec0.mir

-# RUN: llc -o - %s -march=amdgcn -mcpu=fiji  -run-pass=si-insert-skips -verify-machineinstrs | FileCheck -check-prefix=GCN %s
+# RUN: llc -o - %s -march=amdgcn -mcpu=fiji -run-pass=si-late-branch-lowering -verify-machineinstrs | FileCheck -check-prefix=GCN %s
 
 # GCN-LABEL: readlane_exec0
 # GCN: bb.0
 # GCN: S_CBRANCH_EXECZ %bb.2
 
 ---
 name: readlane_exec0
 

llvm/test/CodeGen/AMDGPU/shrink-carry.mir

-# RUN: llc -march=amdgcn -mcpu=gfx900 -verify-machineinstrs -start-before si-shrink-instructions -stop-before si-insert-skips -o - %s | FileCheck -check-prefix=GCN %s
+# RUN: llc -march=amdgcn -mcpu=gfx900 -verify-machineinstrs -start-before si-shrink-instructions -stop-before si-late-branch-lowering -o - %s | FileCheck -check-prefix=GCN %s
 
 # GCN-LABEL: name: subbrev{{$}}
 # GCN:       V_SUBBREV_U32_e32 0, undef $vgpr0, implicit-def $vcc, implicit killed $vcc, implicit $exec
 
 ---
 name:            subbrev
 tracksRegLiveness: true
 registers:

llvm/test/CodeGen/AMDGPU/syncscopes.ll

-; RUN: llc -mtriple=amdgcn-amd-amdhsa -mcpu=gfx803 -stop-after=si-insert-skips < %s | FileCheck --check-prefix=GCN %s
+; RUN: llc -mtriple=amdgcn-amd-amdhsa -mcpu=gfx803 -stop-after=si-late-branch-lowering < %s | FileCheck --check-prefix=GCN %s
 
 ; GCN-LABEL: name: syncscopes
 ; GCN: FLAT_STORE_DWORD killed renamable $vgpr1_vgpr2, killed renamable $vgpr0, 0, 0, implicit $exec, implicit $flat_scr :: (store syncscope("agent") seq_cst 4 into %ir.agent_out)
 ; GCN: FLAT_STORE_DWORD killed renamable $vgpr4_vgpr5, killed renamable $vgpr3, 0, 0, implicit $exec, implicit $flat_scr :: (store syncscope("workgroup") seq_cst 4 into %ir.workgroup_out)
 ; GCN: FLAT_STORE_DWORD killed renamable $vgpr7_vgpr8, killed renamable $vgpr6, 0, 0, implicit $exec, implicit $flat_scr :: (store syncscope("wavefront") seq_cst 4 into %ir.wavefront_out)
 define void @syncscopes(
     i32 %agent,
     i32* %agent_out,

llvm/utils/gn/secondary/llvm/lib/Target/AMDGPU/BUILD.gn

sources = [
     "SIAnnotateControlFlow.cpp",
     "SIFixSGPRCopies.cpp",
     "SIFixVGPRCopies.cpp",
     "SIFoldOperands.cpp",
     "SIFormMemoryClauses.cpp",
     "SIFrameLowering.cpp",
     "SIISelLowering.cpp",
     "SIInsertHardClauses.cpp",
-    "SIInsertSkips.cpp",
+    "SILateBranchLowering.cpp",
     "SIInsertWaitcnts.cpp",
     "SIInstrInfo.cpp",
     "SILoadStoreOptimizer.cpp",
     "SILowerControlFlow.cpp",
     "SILowerI1Copies.cpp",
     "SILowerSGPRSpills.cpp",
     "SIMachineFunctionInfo.cpp",
     "SIMachineScheduler.cpp",