LiveIntervals: Allow constructing standalone without a PassManager

[arsenm]

Summary

The verifier is semi-reliant on LiveIntervals in a weird way. The
verifier has its own liveness analysis, which misses some things
caught with LiveIntervals. As a consequence, llvm-reduce's use of the
verifier fails to filter out some invalid MIR. Allow constructing
LiveIntervals independently of a PassManager, so that llvm-reduce can
use this directly in its passless verify calls. Additionally, some
reductions should directly inspect the LiveIntervals.

[arsenm]

Fix bad patch split

[MatzeB]

I think it's fair to have a version of the algorithm that is not an analysis pass. It feels a bit odd, that the classes are subclasses of MachineFunctionPass but can now (also) be created independently without actually being added to a pass manager, but I guess it avoids a log of refactoring, so okay...

llvm/include/llvm/CodeGen/LiveIntervals.h

101–102

This constructor doesn't have a definition. Is it from an early version and you meant to remove it?

105–106

This probably deserves a comment, mentioning that it should be used when constructor LiveIntervals independently without being an actual AnalysisPass.

I'd prefer compute as a name, but no strong opinion.

llvm/include/llvm/CodeGen/SlotIndexes.h

360

Maybe call it compute to fit the pattern of the LiveIntervals code. Again no strong opinion.

llvm/lib/CodeGen/LiveIntervals.cpp

120–121

Make Indexes_ and DT_ parameters references to indicate that they must not be nullptr.

llvm/include/llvm/CodeGen/LiveIntervals.h

class LiveIntervals : public MachineFunctionPass {
     /// we can't just keep track of the first register mask in each basic
     /// block.
     SmallVector<std::pair<unsigned, unsigned>, 8> RegMaskBlocks;
 
     /// Keeps a live range set for each register unit to track fixed physreg
     /// interference.
     SmallVector<LiveRange*, 0> RegUnitRanges;
 
+
   public:
     static char ID;
 
     LiveIntervals();
+    LiveIntervals(MachineFunction &MF, SlotIndexes *Indexes,
+                  MachineDominatorTree *DT);
     ~LiveIntervals() override;
 
+    void init(MachineFunction &MF, SlotIndexes *Indexes,
+              MachineDominatorTree *DT);
+
+
+    MachineDominatorTree *getDomTree() {
+      return DomTree;
+    }
+
+    const MachineDominatorTree *getDomTree() const {
+      return DomTree;
+    }
+
     /// Calculate the spill weight to assign to a single instruction.
     static float getSpillWeight(bool isDef, bool isUse,
                                 const MachineBlockFrequencyInfo *MBFI,
                                 const MachineInstr &MI);
 
     /// Calculate the spill weight to assign to a single instruction.
     static float getSpillWeight(bool isDef, bool isUse,
                                 const MachineBlockFrequencyInfo *MBFI,

llvm/include/llvm/CodeGen/SlotIndexes.h

public:
 
     SlotIndexes();
 
     ~SlotIndexes() override;
 
     void getAnalysisUsage(AnalysisUsage &au) const override;
     void releaseMemory() override;
 
+    void calculate(MachineFunction &fn);
     bool runOnMachineFunction(MachineFunction &fn) override;
 
     /// Dump the indexes.
     void dump() const;
 
     /// Repair indexes after adding and removing instructions.
     void repairIndexesInRange(MachineBasicBlock *MBB,
                               MachineBasicBlock::iterator Begin,

llvm/lib/CodeGen/LiveIntervals.cpp

void LiveIntervals::releaseMemory() {
   for (LiveRange *LR : RegUnitRanges)
     delete LR;
   RegUnitRanges.clear();
 
   // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.
   VNInfoAllocator.Reset();
 }
 
-bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
-  MF = &fn;
+void LiveIntervals::init(MachineFunction &MF_, SlotIndexes *Indexes_,
+                         MachineDominatorTree *DT_) {
+  MF = &MF_;
+  Indexes = Indexes_;
+  DomTree = DT_;
   MRI = &MF->getRegInfo();
   TRI = MF->getSubtarget().getRegisterInfo();
   TII = MF->getSubtarget().getInstrInfo();
-  Indexes = &getAnalysis<SlotIndexes>();
-  DomTree = &getAnalysis<MachineDominatorTree>();
 
   if (!LICalc)
     LICalc = new LiveIntervalCalc();
 
   // Allocate space for all virtual registers.
   VirtRegIntervals.resize(MRI->getNumVirtRegs());
 
   computeVirtRegs();
   computeRegMasks();
   computeLiveInRegUnits();
 
   if (EnablePrecomputePhysRegs) {
     // For stress testing, precompute live ranges of all physical register
     // units, including reserved registers.
     for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i)
       getRegUnit(i);
   }
+}
+
+bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
+  init(fn, &getAnalysis<SlotIndexes>(), &getAnalysis<MachineDominatorTree>());
   LLVM_DEBUG(dump());
   return false;
 }
 
 void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
   OS << "********** INTERVALS **********\n";
 
   // Dump the regunits.

llvm/lib/CodeGen/SlotIndexes.cpp

 void SlotIndexes::releaseMemory() {
   mi2iMap.clear();
   MBBRanges.clear();
   idx2MBBMap.clear();
   indexList.clear();
   ileAllocator.Reset();
 }
 
-bool SlotIndexes::runOnMachineFunction(MachineFunction &fn) {
-
+void SlotIndexes::calculate(MachineFunction &fn) {
   // Compute numbering as follows:
   // Grab an iterator to the start of the index list.
   // Iterate over all MBBs, and within each MBB all MIs, keeping the MI
   // iterator in lock-step (though skipping it over indexes which have
   // null pointers in the instruction field).
   // At each iteration assert that the instruction pointed to in the index
   // is the same one pointed to by the MI iterator. This
 
for (MachineBasicBlock &MBB : *mf) {
     MBBRanges[MBB.getNumber()].first = blockStartIndex;
     MBBRanges[MBB.getNumber()].second = SlotIndex(&indexList.back(),
                                                    SlotIndex::Slot_Block);
     idx2MBBMap.push_back(IdxMBBPair(blockStartIndex, &MBB));
   }
 
   // Sort the Idx2MBBMap
   llvm::sort(idx2MBBMap, less_first());
+}
 
+bool SlotIndexes::runOnMachineFunction(MachineFunction &fn) {
+  calculate(fn);
   LLVM_DEBUG(mf->print(dbgs(), this));
 
   // And we're done!
   return false;
 }
 
 void SlotIndexes::removeMachineInstrFromMaps(MachineInstr &MI,
                                              bool AllowBundled) {