[RegAlloc, NFC] Extract LastSplitPoint computation to a new class

[wmi]

Summary

This is a preparing patch for http://reviews.llvm.org/D19884

Because both split and spill hoisting want to use LastSplitPoint computation result, extract the LastSplitPoint computation from SplitAnalysis class which also contains a bunch of other analysises only related to split.

[wmi]

change computeLastSplitPoint to private.

[MatzeB]

lib/CodeGen/SplitKit.h

41–44

This explanation of the purpose of this class is confusing. This is not about liverange splitting (liverange splitting just happens to be one of the users later). The analysis simply determines the latest point in a block in which we can insert an instruction (that reads CurLI).

47

VirtRegMap is not used here.

50

Three slashes for doxygen comments.

61

Use const LiveInterval& in the API, as nullptr is not allowed here.

63

I'd suggest using const MachineBasicBlock& instead of block numbers in the API here. That is simpler to use and you can get away without storing a reference to the MachineFunction in the LSplitPointAnalysis class.

76

Use const MachineBasicBlock& in the API as nullptr is not allowed here.

216

no need for two empty lines.

[wmi]

Address Matthias's comments.

lib/CodeGen/SplitKit.h

41–44

I renamed LSplitPointAnalysis to InsertPointAnalysis and changed related fields and comments.

47

Removed.

50

Fixed.

61

CurLI is usually not initialized when constructor is called. It is setup in the process of split/spill and reset from time to time. So I feel const LiveInterval *CurLI is easier here.

63

Done.

76

Done.

216

Fixed.

[MatzeB]

LGTM with 1 nitpick.

Please do not push this patch until http://reviews.llvm.org/D19884 is accepted.

lib/CodeGen/SplitKit.h

123

Use three slash doxygen comment.

[MatzeB]

Looking at the use in D19884 this may need a reset(const LiveIntervalAnalysis&) method that clears the cache and re-initializes the LiveIntervalAnalysis field, so users do not need to create new instances of the object less often.

[wmi]

Rebase the patch.

[MatzeB]

This was committed a while ago in r269248

lib/CodeGen/SplitKit.h

 class MachineLoopInfo;
 class MachineRegisterInfo;
 class TargetInstrInfo;
 class TargetRegisterInfo;
 class VirtRegMap;
 class VNInfo;
 class raw_ostream;
 
+/// Determines the latest safe point in a block in which we can insert a split,
+/// spill or other instruction related with CurLI.
+class LLVM_LIBRARY_VISIBILITY InsertPointAnalysis {
+private:
+  const LiveIntervals &LIS;
+
+  /// Current LiveInterval for which to insert split or spill.
+  const LiveInterval *CurLI;
+
+  /// Last legal insert point in each basic block in the current function.
+  /// The first entry is the first terminator, the second entry is the
+  /// last valid point to insert a split or spill for a variable that is
+  /// live into a landing pad successor.
+  SmallVector<std::pair<SlotIndex, SlotIndex>, 8> LastInsertPoint;
+
+  SlotIndex computeLastInsertPoint(const MachineBasicBlock &MBB);
+
+public:
+  InsertPointAnalysis(const LiveIntervals &lis, unsigned BBNum);
+
+  void setInterval(const LiveInterval *LI) { CurLI = LI; }
+
+  /// Return the base index of the last valid insert point in \pMBB.
+  SlotIndex getLastInsertPoint(const MachineBasicBlock &MBB) {
+    unsigned Num = MBB.getNumber();
+    // Inline the common simple case.
+    if (LastInsertPoint[Num].first.isValid() &&
+        !LastInsertPoint[Num].second.isValid())
+      return LastInsertPoint[Num].first;
+    return computeLastInsertPoint(MBB);
+  }
+
+  /// Returns the last insert point as an iterator.
+  MachineBasicBlock::iterator getLastInsertPointIter(MachineBasicBlock &);
+};
+
 /// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting
 /// opportunities.
 class LLVM_LIBRARY_VISIBILITY SplitAnalysis {
 public:
   const MachineFunction &MF;
   const VirtRegMap &VRM;
   const LiveIntervals &LIS;
   const MachineLoopInfo &Loops;
bool isOneInstr() const {
       return SlotIndex::isSameInstr(FirstInstr, LastInstr);
     }
   };
 
 private:
   // Current live interval.
   const LiveInterval *CurLI;
 
+  /// Insert Point Analysis.
+  InsertPointAnalysis IPA;
+
   // Sorted slot indexes of using instructions.
   SmallVector<SlotIndex, 8> UseSlots;
 
-  /// LastSplitPoint - Last legal split point in each basic block in the current
-  /// function. The first entry is the first terminator, the second entry is the
-  /// last valid split point for a variable that is live in to a landing pad
-  /// successor.
-  SmallVector<std::pair<SlotIndex, SlotIndex>, 8> LastSplitPoint;
-
   /// UseBlocks - Blocks where CurLI has uses.
   SmallVector<BlockInfo, 8> UseBlocks;
 
   /// NumGapBlocks - Number of duplicate entries in UseBlocks for blocks where
   /// the live range has a gap.
   unsigned NumGapBlocks;
 
   /// ThroughBlocks - Block numbers where CurLI is live through without uses.
   BitVector ThroughBlocks;
 
   /// NumThroughBlocks - Number of live-through blocks.
   unsigned NumThroughBlocks;
 
   /// DidRepairRange - analyze was forced to shrinkToUses().
   bool DidRepairRange;
 
-  SlotIndex computeLastSplitPoint(unsigned Num);
-
   // Sumarize statistics by counting instructions using CurLI.
   void analyzeUses();
 
   /// calcLiveBlockInfo - Compute per-block information about CurLI.
   bool calcLiveBlockInfo();
 
 public:
   SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis,
public:
 
   /// clear - clear all data structures so SplitAnalysis is ready to analyze a
   /// new interval.
   void clear();
 
   /// getParent - Return the last analyzed interval.
   const LiveInterval &getParent() const { return *CurLI; }
 
-  /// getLastSplitPoint - Return the base index of the last valid split point
-  /// in the basic block numbered Num.
-  SlotIndex getLastSplitPoint(unsigned Num) {
-    // Inline the common simple case.
-    if (LastSplitPoint[Num].first.isValid() &&
-        !LastSplitPoint[Num].second.isValid())
-      return LastSplitPoint[Num].first;
-    return computeLastSplitPoint(Num);
-  }
-
-  /// getLastSplitPointIter - Returns the last split point as an iterator.
-  MachineBasicBlock::iterator getLastSplitPointIter(MachineBasicBlock*);
-
   /// isOriginalEndpoint - Return true if the original live range was killed or
   /// (re-)defined at Idx. Idx should be the 'def' slot for a normal kill/def,
   /// and 'use' for an early-clobber def.
   /// This can be used to recognize code inserted by earlier live range
   /// splitting.
   bool isOriginalEndpoint(SlotIndex Idx) const;
 
   /// getUseSlots - Return an array of SlotIndexes of instructions using CurLI.
public:
   /// live range for the instructions in BI. There is normally no benefit to
   /// creating a live range for a single instruction, but it does enable
   /// register class inflation if the instruction has a restricted register
   /// class.
   ///
   /// @param BI           The block to be isolated.
   /// @param SingleInstrs True when single instructions should be isolated.
   bool shouldSplitSingleBlock(const BlockInfo &BI, bool SingleInstrs) const;
+
+  SlotIndex getLastSplitPoint(unsigned Num) {
+    return IPA.getLastInsertPoint(*MF.getBlockNumbered(Num));
+  }
+
+  MachineBasicBlock::iterator getLastSplitPointIter(MachineBasicBlock *BB) {
+    return IPA.getLastInsertPointIter(*BB);
+  }
 };
 
 
 /// SplitEditor - Edit machine code and LiveIntervals for live range
 /// splitting.
 ///
 /// - Create a SplitEditor from a SplitAnalysis.
 /// - Start a new live interval with openIntv.

lib/CodeGen/SplitKit.cpp

 
 STATISTIC(NumFinished, "Number of splits finished");
 STATISTIC(NumSimple,   "Number of splits that were simple");
 STATISTIC(NumCopies,   "Number of copies inserted for splitting");
 STATISTIC(NumRemats,   "Number of rematerialized defs for splitting");
 STATISTIC(NumRepairs,  "Number of invalid live ranges repaired");
 
 //===----------------------------------------------------------------------===//
-//                                 Split Analysis
+//                     Last Insert Point Analysis
 //===----------------------------------------------------------------------===//
 
-SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis,
-                             const MachineLoopInfo &mli)
-    : MF(vrm.getMachineFunction()), VRM(vrm), LIS(lis), Loops(mli),
-      TII(*MF.getSubtarget().getInstrInfo()), CurLI(nullptr),
-      LastSplitPoint(MF.getNumBlockIDs()) {}
-
-void SplitAnalysis::clear() {
-  UseSlots.clear();
-  UseBlocks.clear();
-  ThroughBlocks.clear();
-  CurLI = nullptr;
-  DidRepairRange = false;
-}
-
-SlotIndex SplitAnalysis::computeLastSplitPoint(unsigned Num) {
-  const MachineBasicBlock *MBB = MF.getBlockNumbered(Num);
-  std::pair<SlotIndex, SlotIndex> &LSP = LastSplitPoint[Num];
-  SlotIndex MBBEnd = LIS.getMBBEndIdx(MBB);
+InsertPointAnalysis::InsertPointAnalysis(const LiveIntervals &lis,
+                                         unsigned BBNum)
+    : LIS(lis), CurLI(nullptr), LastInsertPoint(BBNum) {}
+
+SlotIndex
+InsertPointAnalysis::computeLastInsertPoint(const MachineBasicBlock &MBB) {
+  unsigned Num = MBB.getNumber();
+  std::pair<SlotIndex, SlotIndex> &LIP = LastInsertPoint[Num];
+  SlotIndex MBBEnd = LIS.getMBBEndIdx(&MBB);
 
   SmallVector<const MachineBasicBlock *, 1> EHPadSucessors;
-  for (const MachineBasicBlock *SMBB : MBB->successors())
+  for (const MachineBasicBlock *SMBB : MBB.successors())
     if (SMBB->isEHPad())
       EHPadSucessors.push_back(SMBB);
 
-  // Compute split points on the first call. The pair is independent of the
+  // Compute insert points on the first call. The pair is independent of the
   // current live interval.
-  if (!LSP.first.isValid()) {
-    MachineBasicBlock::const_iterator FirstTerm = MBB->getFirstTerminator();
-    if (FirstTerm == MBB->end())
-      LSP.first = MBBEnd;
+  if (!LIP.first.isValid()) {
+    MachineBasicBlock::const_iterator FirstTerm = MBB.getFirstTerminator();
+    if (FirstTerm == MBB.end())
+      LIP.first = MBBEnd;
     else
-      LSP.first = LIS.getInstructionIndex(*FirstTerm);
+      LIP.first = LIS.getInstructionIndex(*FirstTerm);
 
     // If there is a landing pad successor, also find the call instruction.
     if (EHPadSucessors.empty())
-      return LSP.first;
+      return LIP.first;
     // There may not be a call instruction (?) in which case we ignore LPad.
-    LSP.second = LSP.first;
-    for (MachineBasicBlock::const_iterator I = MBB->end(), E = MBB->begin();
+    LIP.second = LIP.first;
+    for (MachineBasicBlock::const_iterator I = MBB.end(), E = MBB.begin();
          I != E;) {
       --I;
       if (I->isCall()) {
-        LSP.second = LIS.getInstructionIndex(*I);
+        LIP.second = LIS.getInstructionIndex(*I);
         break;
       }
     }
   }
 
-  // If CurLI is live into a landing pad successor, move the last split point
+  // If CurLI is live into a landing pad successor, move the last insert point
   // back to the call that may throw.
-  if (!LSP.second)
-    return LSP.first;
+  if (!LIP.second)
+    return LIP.first;
 
+  assert(CurLI && "CurLI not being set");
   if (none_of(EHPadSucessors, [&](const MachineBasicBlock *EHPad) {
         return LIS.isLiveInToMBB(*CurLI, EHPad);
       }))
-    return LSP.first;
+    return LIP.first;
 
   // Find the value leaving MBB.
   const VNInfo *VNI = CurLI->getVNInfoBefore(MBBEnd);
   if (!VNI)
-    return LSP.first;
+    return LIP.first;
 
   // If the value leaving MBB was defined after the call in MBB, it can't
   // really be live-in to the landing pad.  This can happen if the landing pad
   // has a PHI, and this register is undef on the exceptional edge.
   // <rdar://problem/10664933>
-  if (!SlotIndex::isEarlierInstr(VNI->def, LSP.second) && VNI->def < MBBEnd)
-    return LSP.first;
+  if (!SlotIndex::isEarlierInstr(VNI->def, LIP.second) && VNI->def < MBBEnd)
+    return LIP.first;
 
   // Value is properly live-in to the landing pad.
-  // Only allow splits before the call.
-  return LSP.second;
+  // Only allow inserts before the call.
+  return LIP.second;
 }
 
 MachineBasicBlock::iterator
-SplitAnalysis::getLastSplitPointIter(MachineBasicBlock *MBB) {
-  SlotIndex LSP = getLastSplitPoint(MBB->getNumber());
-  if (LSP == LIS.getMBBEndIdx(MBB))
-    return MBB->end();
-  return LIS.getInstructionFromIndex(LSP);
+InsertPointAnalysis::getLastInsertPointIter(MachineBasicBlock &MBB) {
+  SlotIndex LIP = getLastInsertPoint(MBB);
+  if (LIP == LIS.getMBBEndIdx(&MBB))
+    return MBB.end();
+  return LIS.getInstructionFromIndex(LIP);
+}
+
+//===----------------------------------------------------------------------===//
+//                                 Split Analysis
+//===----------------------------------------------------------------------===//
+
+SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis,
+                             const MachineLoopInfo &mli)
+    : MF(vrm.getMachineFunction()), VRM(vrm), LIS(lis), Loops(mli),
+      TII(*MF.getSubtarget().getInstrInfo()), CurLI(nullptr),
+      IPA(lis, MF.getNumBlockIDs()) {}
+
+void SplitAnalysis::clear() {
+  UseSlots.clear();
+  UseBlocks.clear();
+  ThroughBlocks.clear();
+  CurLI = nullptr;
+  DidRepairRange = false;
 }
 
 /// analyzeUses - Count instructions, basic blocks, and loops using CurLI.
 void SplitAnalysis::analyzeUses() {
   assert(UseSlots.empty() && "Call clear first");
 
   // First get all the defs from the interval values. This provides the correct
   // slots for early clobbers.
bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const {
 
   // Range does not contain Idx, previous must end at Idx.
   return I != Orig.begin() && (--I)->end == Idx;
 }
 
 void SplitAnalysis::analyze(const LiveInterval *li) {
   clear();
   CurLI = li;
+  IPA.setInterval(li);
   analyzeUses();
 }
 
 
 //===----------------------------------------------------------------------===//
 //                               Split Editor
 //===----------------------------------------------------------------------===//