Index: lib/CodeGen/SplitKit.h =================================================================== --- lib/CodeGen/SplitKit.h +++ lib/CodeGen/SplitKit.h @@ -38,6 +38,42 @@ 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, 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 { @@ -84,15 +120,12 @@ // Current live interval. const LiveInterval *CurLI; + // Insert Point Analysis. + InsertPointAnalysis IPA; + // Sorted slot indexes of using instructions. SmallVector 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, 8> LastSplitPoint; - /// UseBlocks - Blocks where CurLI has uses. SmallVector UseBlocks; @@ -109,8 +142,6 @@ /// DidRepairRange - analyze was forced to shrinkToUses(). bool DidRepairRange; - SlotIndex computeLastSplitPoint(unsigned Num); - // Sumarize statistics by counting instructions using CurLI. void analyzeUses(); @@ -137,19 +168,6 @@ /// 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. @@ -195,6 +213,14 @@ /// @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); + } }; Index: lib/CodeGen/SplitKit.cpp =================================================================== --- lib/CodeGen/SplitKit.cpp +++ lib/CodeGen/SplitKit.cpp @@ -38,82 +38,91 @@ STATISTIC(NumRepairs, "Number of invalid live ranges repaired"); //===----------------------------------------------------------------------===// -// Split Analysis +// Last Insert Point Analysis //===----------------------------------------------------------------------===// +InsertPointAnalysis::InsertPointAnalysis(const LiveIntervals &lis, + unsigned BBNum) + : LIS(lis), CurLI(nullptr), LastInsertPoint(BBNum) {} -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); +SlotIndex +InsertPointAnalysis::computeLastInsertPoint(const MachineBasicBlock &MBB) { + unsigned Num = MBB.getNumber(); // FIXME: Handle multiple EH pad successors. - const MachineBasicBlock *LPad = MBB->getLandingPadSuccessor(); - std::pair &LSP = LastSplitPoint[Num]; - SlotIndex MBBEnd = LIS.getMBBEndIdx(MBB); + const MachineBasicBlock *LPad = MBB.getLandingPadSuccessor(); + std::pair &LIP = LastInsertPoint[Num]; + SlotIndex MBBEnd = LIS.getMBBEndIdx(&MBB); - // 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 (!LPad) - 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 (!LPad || !LSP.second || !LIS.isLiveInToMBB(*CurLI, LPad)) - return LSP.first; + assert(CurLI && "CurLI not being set"); + if (!LPad || !LIP.second || !LIS.isLiveInToMBB(*CurLI, LPad)) + 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. // - 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 insert 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. @@ -310,6 +319,7 @@ void SplitAnalysis::analyze(const LiveInterval *li) { clear(); CurLI = li; + IPA.setInterval(li); analyzeUses(); }