AMDGPU: Move SIFixSGPRLiveRanges to be a regalloc pass

[arsenm]

Summary

Replace LiveInterval usage with LiveVariables. LiveIntervals
computes far more information than is needed for this pass
which just needs to find if an SGPR is live out of the
defining block.

LiveIntervals are not usually available that early, requiring
computing them twice which is very expensive. The extra run of
LiveIntervals/LiveVariables/SlotIndexes was costing in total
about 5% of compile time.

Continuing to use LiveIntervals is problematic. It seems
there is an option (early-live-intervals) to run the analysis
about where it should go to avoid recomputing LiveVariables,
but it seems to be completely broken with subreg liveness
enabled. There are also problems from trying to recompute
LiveIntervals since this seems to undo LiveVariables
and clearing kill flags, causing TwoAddressInstructions
to make bad decisions.

Insert the pass right after live variables and preserve it.
The tricky case to worry about might be phis since
LiveVariables doesn't count a register as live out if
in the successor block it is only used in a phi,
but I don't think this is a concern right now
because SIFixSGPRCopies replaces SGPR phis.

[MatzeB]

Note that long-term we plan to remove the LiveVariables analysis and just keep LiveIntervals around; though I don't see this happening soon as I don't see an incentive to actually do the work of fixing TwoAddressInstructions and PhiElimination to use LiveIntervals...

[arsenm]

In D13197#254947, @MatzeB wrote:

Note that long-term we plan to remove the LiveVariables analysis and just keep LiveIntervals around; though I don't see this happening soon as I don't see an incentive to actually do the work of fixing TwoAddressInstructions and PhiElimination to use LiveIntervals...

I'm kind of confused what the relationship between LiveVariables and LiveIntervals is, but I've seen the comments about removing LiveVariables. LiveIntervals seems to require LiveVariables, but then the calculation of LiveIntervals seems to clear kill flags?

[MatzeB]

The fact that LiveIntervals requires LiveVariables appears to be hack. From LiveIntervalAnalaysis.cpp:

// LiveVariables isn't really required by this analysis, it is only required
// here to make sure it is live during TwoAddressInstructionPass and
// PHIElimination. This is temporary.

This is probably not the right place for an in-depth discussion but kill flags is another feature that we hope to remove long term... Yes the current state of TwoAddressInstruction and PhiElimination prohibits those changes and I don't see this getting fixed in the near future.

[• tstellarAMD]

LGTM.

[arsenm]

r249087 with the asserts removed about physical register defs because it is not actually useful and should be a verifier error

lib/Target/AMDGPU/AMDGPUTargetMachine.cpp

 #include <llvm/CodeGen/Passes.h>
 
 using namespace llvm;
 
 extern "C" void LLVMInitializeAMDGPUTarget() {
   // Register the target
   RegisterTargetMachine<R600TargetMachine> X(TheAMDGPUTarget);
   RegisterTargetMachine<GCNTargetMachine> Y(TheGCNTarget);
+
+  PassRegistry *PR = PassRegistry::getPassRegistry();
+  initializeSIFixSGPRLiveRangesPass(*PR);
 }
 
 static std::unique_ptr<TargetLoweringObjectFile> createTLOF(const Triple &TT) {
   if (TT.getOS() == Triple::AMDHSA)
     return make_unique<AMDGPUHSATargetObjectFile>();
 
   return make_unique<TargetLoweringObjectFileELF>();
 }

 };
 
 class GCNPassConfig : public AMDGPUPassConfig {
 public:
   GCNPassConfig(TargetMachine *TM, PassManagerBase &PM)
     : AMDGPUPassConfig(TM, PM) { }
   bool addPreISel() override;
   bool addInstSelector() override;
+  void addFastRegAlloc(FunctionPass *RegAllocPass) override;
+  void addOptimizedRegAlloc(FunctionPass *RegAllocPass) override;
   void addPreRegAlloc() override;
   void addPostRegAlloc() override;
   void addPreSched2() override;
   void addPreEmitPass() override;
 };
 
 } // End of anonymous namespace
 
if (getOptLevel() > CodeGenOpt::None && ST.loadStoreOptEnabled()) {
 
     // This should be run after scheduling, but before register allocation. It
     // also need extra copies to the address operand to be eliminated.
     initializeSILoadStoreOptimizerPass(*PassRegistry::getPassRegistry());
     insertPass(&MachineSchedulerID, &SILoadStoreOptimizerID);
     insertPass(&MachineSchedulerID, &RegisterCoalescerID);
   }
   addPass(createSIShrinkInstructionsPass(), false);
-  addPass(createSIFixSGPRLiveRangesPass());
+}
+
+void GCNPassConfig::addFastRegAlloc(FunctionPass *RegAllocPass) {
+  addPass(&SIFixSGPRLiveRangesID);
+  TargetPassConfig::addFastRegAlloc(RegAllocPass);
+}
+
+void GCNPassConfig::addOptimizedRegAlloc(FunctionPass *RegAllocPass) {
+  // We want to run this after LiveVariables is computed to avoid computing them
+  // twice.
+  insertPass(&LiveVariablesID, &SIFixSGPRLiveRangesID);
+  TargetPassConfig::addOptimizedRegAlloc(RegAllocPass);
 }
 
 void GCNPassConfig::addPostRegAlloc() {
   addPass(createSIPrepareScratchRegs(), false);
   addPass(createSIShrinkInstructionsPass(), false);
 }
 
 void GCNPassConfig::addPreSched2() {

lib/Target/AMDGPU/SIFixSGPRLiveRanges.cpp

public:
 
   bool runOnMachineFunction(MachineFunction &MF) override;
 
   const char *getPassName() const override {
     return "SI Fix SGPR live ranges";
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
-    AU.addRequired<LiveIntervals>();
+    AU.addRequired<LiveVariables>();
+    AU.addPreserved<LiveVariables>();
+
     AU.addRequired<MachinePostDominatorTree>();
+    AU.addPreserved<MachinePostDominatorTree>();
     AU.setPreservesCFG();
 
-    //AU.addPreserved<SlotIndexes>(); // XXX - This might be OK
-    AU.addPreserved<LiveIntervals>();
-
     MachineFunctionPass::getAnalysisUsage(AU);
   }
 };
 
 } // End anonymous namespace.
 
 INITIALIZE_PASS_BEGIN(SIFixSGPRLiveRanges, DEBUG_TYPE,
                       "SI Fix SGPR Live Ranges", false, false)
-INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
 INITIALIZE_PASS_DEPENDENCY(LiveVariables)
 INITIALIZE_PASS_DEPENDENCY(MachinePostDominatorTree)
 INITIALIZE_PASS_END(SIFixSGPRLiveRanges, DEBUG_TYPE,
                     "SI Fix SGPR Live Ranges", false, false)
 
 char SIFixSGPRLiveRanges::ID = 0;
 
 char &llvm::SIFixSGPRLiveRangesID = SIFixSGPRLiveRanges::ID;
 
 FunctionPass *llvm::createSIFixSGPRLiveRangesPass() {
   return new SIFixSGPRLiveRanges();
 }
 
+static bool isPhysRegLiveOut(unsigned Reg, const MachineBasicBlock &MBB) {
+  for (const MachineBasicBlock *Succ : MBB.successors()) {
+    if (Succ->isLiveIn(Reg))
+      return true;
+  }
+
+  return false;
+}
+
 bool SIFixSGPRLiveRanges::runOnMachineFunction(MachineFunction &MF) {
   MachineRegisterInfo &MRI = MF.getRegInfo();
   const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
   const SIRegisterInfo *TRI = static_cast<const SIRegisterInfo *>(
       MF.getSubtarget().getRegisterInfo());
   bool MadeChange = false;
 
   MachinePostDominatorTree *PDT = &getAnalysis<MachinePostDominatorTree>();
-  std::vector<std::pair<unsigned, LiveRange *>> SGPRLiveRanges;
+  SmallVector<unsigned, 16> SGPRLiveRanges;
 
-  LiveIntervals *LIS = &getAnalysis<LiveIntervals>();
-  LiveVariables *LV = getAnalysisIfAvailable<LiveVariables>();
+  LiveVariables *LV = &getAnalysis<LiveVariables>();
   MachineBasicBlock *Entry = MF.begin();
 
   // Use a depth first order so that in SSA, we encounter all defs before
   // uses. Once the defs of the block have been found, attempt to insert
   // SGPR_USE instructions in successor blocks if required.
   for (MachineBasicBlock *MBB : depth_first(Entry)) {
     for (const MachineInstr &MI : *MBB) {
       for (const MachineOperand &MO : MI.defs()) {
         if (MO.isImplicit())
           continue;
         unsigned Def = MO.getReg();
         if (TargetRegisterInfo::isVirtualRegister(Def)) {
           if (TRI->isSGPRClass(MRI.getRegClass(Def))) {
             // Only consider defs that are live outs. We don't care about def /
             // use within the same block.
-            LiveRange &LR = LIS->getInterval(Def);
-            if (LIS->isLiveOutOfMBB(LR, MBB))
-              SGPRLiveRanges.push_back(std::make_pair(Def, &LR));
+
+            // LiveVariables does not consider registers that are only used in a
+            // phi in a sucessor block as live out, unlike LiveIntervals.
+            //
+            // This is OK because SIFixSGPRCopies replaced any SGPR phis with
+            // VGPRs.
+            if (LV->isLiveOut(Def, *MBB))
+              SGPRLiveRanges.push_back(Def);
           }
-        } else if (TRI->isSGPRClass(TRI->getPhysRegClass(Def))) {
-          SGPRLiveRanges.push_back(std::make_pair(Def, &LIS->getRegUnit(Def)));
+        } else {
+          assert(!isPhysRegLiveOut(Def, *MBB) && "Should never see physical reg live outs");
         }
       }
     }
 
     if (MBB->succ_size() < 2)
       continue;
 
     // We have structured control flow, so the number of successors should be
for (MachineBasicBlock *MBB : depth_first(Entry)) {
     if (NCDTerm != NCD->end() && NCDTerm->getOpcode() == AMDGPU::SI_ELSE) {
       assert(NCD->succ_size() == 2);
       // We want to make sure we insert the Use after the ENDIF, not after
       // the ELSE.
       NCD = PDT->findNearestCommonDominator(*NCD->succ_begin(),
                                             *(++NCD->succ_begin()));
     }
 
-    for (std::pair<unsigned, LiveRange*> RegLR : SGPRLiveRanges) {
-      unsigned Reg = RegLR.first;
-      LiveRange *LR = RegLR.second;
-
+    for (unsigned Reg : SGPRLiveRanges) {
       // FIXME: We could be smarter here. If the register is Live-In to one
       // block, but the other doesn't have any SGPR defs, then there won't be a
       // conflict. Also, if the branch condition is uniform then there will be
       // no conflict.
-      bool LiveInToA = LIS->isLiveInToMBB(*LR, SuccA);
-      bool LiveInToB = LIS->isLiveInToMBB(*LR, SuccB);
+      bool LiveInToA = LV->isLiveIn(Reg, *SuccA);
+      bool LiveInToB = LV->isLiveIn(Reg, *SuccB);
 
       if (!LiveInToA && !LiveInToB) {
         DEBUG(dbgs() << PrintReg(Reg, TRI, 0)
               << " is live into neither successor\n");
         continue;
       }
 
       if (LiveInToA && LiveInToB) {
         DEBUG(dbgs() << PrintReg(Reg, TRI, 0)
               << " is live into both successors\n");
         continue;
       }
 
       // This interval is live in to one successor, but not the other, so
       // we need to update its range so it is live in to both.
       DEBUG(dbgs() << "Possible SGPR conflict detected for "
-            << PrintReg(Reg, TRI, 0) <<  " in " << *LR
-            << " BB#" << SuccA->getNumber() << ", BB#"
-            << SuccB->getNumber()
+            << PrintReg(Reg, TRI, 0)
+            << " BB#" << SuccA->getNumber()
+            << ", BB#" << SuccB->getNumber()
             << " with NCD = BB#" << NCD->getNumber() << '\n');
 
       assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
              "Not expecting to extend live range of physreg");
 
       // FIXME: Need to figure out how to update LiveRange here so this pass
       // will be able to preserve LiveInterval analysis.
       MachineInstr *NCDSGPRUse =
         BuildMI(*NCD, NCD->getFirstNonPHI(), DebugLoc(),
                 TII->get(AMDGPU::SGPR_USE))
         .addReg(Reg, RegState::Implicit);
 
       MadeChange = true;
-
-      SlotIndex SI = LIS->InsertMachineInstrInMaps(NCDSGPRUse);
-      LIS->extendToIndices(*LR, SI.getRegSlot());
-
-      if (LV) {
-        // TODO: This won't work post-SSA
-        LV->HandleVirtRegUse(Reg, NCD, NCDSGPRUse);
-      }
 
       DEBUG(NCDSGPRUse->dump());
     }
   }
 
   return MadeChange;
 }