From 6111cd8660c5fca74db6f3ee68d2581037bd60b3 Mon Sep 17 00:00:00 2001 From: Matthias Braun Date: Wed, 9 Sep 2015 18:07:54 +0000 Subject: [PATCH] VirtRegMap: Improve addMBBLiveIns() using SlotIndex::MBBIndexIterator; NFC Now that we have an explicit iterator over the idx2MBBMap in SlotIndices we can use the fact that segments and the idx2MBBMap is sorted by SlotIndex position so can advance both simultaneously instead of starting from the beginning for each segment. This complicates the code for the subregister case somewhat but should be more efficient and has the advantage that we get the final lanemask for each block immediately which will be important for a subsequent change. Removes the now unused SlotIndexes::findMBBLiveIns function. Differential Revision: http://reviews.llvm.org/D12443 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@247170 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/LiveIntervalAnalysis.h | 5 -- include/llvm/CodeGen/SlotIndexes.h | 11 --- lib/CodeGen/VirtRegMap.cpp | 87 +++++++++++++++------ 3 files changed, 62 insertions(+), 41 deletions(-) diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h index 343bd3bc00f..5996f8dd334 100644 --- a/include/llvm/CodeGen/LiveIntervalAnalysis.h +++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -258,11 +258,6 @@ extern cl::opt UseSegmentSetForPhysRegs; Indexes->replaceMachineInstrInMaps(MI, NewMI); } - bool findLiveInMBBs(SlotIndex Start, SlotIndex End, - SmallVectorImpl &MBBs) const { - return Indexes->findLiveInMBBs(Start, End, MBBs); - } - VNInfo::Allocator& getVNInfoAllocator() { return VNInfoAllocator; } void getAnalysisUsage(AnalysisUsage &AU) const override; diff --git a/include/llvm/CodeGen/SlotIndexes.h b/include/llvm/CodeGen/SlotIndexes.h index b689f0d7445..be0f87ed9c4 100644 --- a/include/llvm/CodeGen/SlotIndexes.h +++ b/include/llvm/CodeGen/SlotIndexes.h @@ -541,17 +541,6 @@ namespace llvm { return J->second; } - bool findLiveInMBBs(SlotIndex start, SlotIndex end, - SmallVectorImpl &mbbs) const { - bool resVal = false; - for (MBBIndexIterator itr = findMBBIndex(start); - itr != MBBIndexEnd() && itr->first < end; ++itr) { - mbbs.push_back(itr->second); - resVal = true; - } - return resVal; - } - /// Returns the MBB covering the given range, or null if the range covers /// more than one basic block. MachineBasicBlock* getMBBCoveringRange(SlotIndex start, SlotIndex end) const { diff --git a/lib/CodeGen/VirtRegMap.cpp b/lib/CodeGen/VirtRegMap.cpp index 02341b4d66b..fdc135fc240 100644 --- a/lib/CodeGen/VirtRegMap.cpp +++ b/lib/CodeGen/VirtRegMap.cpp @@ -167,6 +167,8 @@ class VirtRegRewriter : public MachineFunctionPass { void rewrite(); void addMBBLiveIns(); bool readsUndefSubreg(const MachineOperand &MO) const; + void addLiveInsForSubRanges(const LiveInterval &LI, unsigned PhysReg) const; + public: static char ID; VirtRegRewriter() : MachineFunctionPass(ID) {} @@ -236,10 +238,58 @@ bool VirtRegRewriter::runOnMachineFunction(MachineFunction &fn) { return true; } +void VirtRegRewriter::addLiveInsForSubRanges(const LiveInterval &LI, + unsigned PhysReg) const { + assert(!LI.empty()); + assert(LI.hasSubRanges()); + + typedef std::pair SubRangeIteratorPair; + SmallVector SubRanges; + SlotIndex First; + SlotIndex Last; + for (const LiveInterval::SubRange &SR : LI.subranges()) { + SubRanges.push_back(std::make_pair(&SR, SR.begin())); + if (!First.isValid() || SR.segments.front().start < First) + First = SR.segments.front().start; + if (!Last.isValid() || SR.segments.back().end > Last) + Last = SR.segments.back().end; + } + + // Check all mbb start positions between First and Last while + // simulatenously advancing an iterator for each subrange. + for (SlotIndexes::MBBIndexIterator MBBI = Indexes->findMBBIndex(First); + MBBI != Indexes->MBBIndexEnd() && MBBI->first <= Last; ++MBBI) { + SlotIndex MBBBegin = MBBI->first; + // Advance all subrange iterators so that their end position is just + // behind MBBBegin (or the iterator is at the end). + unsigned LaneMask = 0; + for (auto &RangeIterPair : SubRanges) { + const LiveInterval::SubRange *SR = RangeIterPair.first; + LiveInterval::const_iterator &SRI = RangeIterPair.second; + while (SRI != SR->end() && SRI->end <= MBBBegin) + ++SRI; + if (SRI == SR->end()) + continue; + if (SRI->start <= MBBBegin) + LaneMask |= SR->LaneMask; + } + if (LaneMask == 0) + continue; + MachineBasicBlock *MBB = MBBI->second; + for (MCSubRegIndexIterator SR(PhysReg, TRI); SR.isValid(); ++SR) { + unsigned SubReg = SR.getSubReg(); + unsigned SubRegIndex = SR.getSubRegIndex(); + unsigned SubRegLaneMask = TRI->getSubRegIndexLaneMask(SubRegIndex); + if ((SubRegLaneMask & LaneMask) != 0) + MBB->addLiveIn(SubReg); + } + } +} + // Compute MBB live-in lists from virtual register live ranges and their // assignments. void VirtRegRewriter::addMBBLiveIns() { - SmallVector LiveIn; for (unsigned Idx = 0, IdxE = MRI->getNumVirtRegs(); Idx != IdxE; ++Idx) { unsigned VirtReg = TargetRegisterInfo::index2VirtReg(Idx); if (MRI->reg_nodbg_empty(VirtReg)) @@ -253,31 +303,18 @@ void VirtRegRewriter::addMBBLiveIns() { assert(PhysReg != VirtRegMap::NO_PHYS_REG && "Unmapped virtual register."); if (LI.hasSubRanges()) { - for (LiveInterval::SubRange &S : LI.subranges()) { - for (const auto &Seg : S.segments) { - if (!Indexes->findLiveInMBBs(Seg.start, Seg.end, LiveIn)) - continue; - for (MCSubRegIndexIterator SR(PhysReg, TRI); SR.isValid(); ++SR) { - unsigned SubReg = SR.getSubReg(); - unsigned SubRegIndex = SR.getSubRegIndex(); - unsigned SubRegLaneMask = TRI->getSubRegIndexLaneMask(SubRegIndex); - if ((SubRegLaneMask & S.LaneMask) == 0) - continue; - for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) { - LiveIn[i]->addLiveIn(SubReg); - } - } - LiveIn.clear(); - } - } + addLiveInsForSubRanges(LI, PhysReg); } else { - // Scan the segments of LI. - for (const auto &Seg : LI.segments) { - if (!Indexes->findLiveInMBBs(Seg.start, Seg.end, LiveIn)) - continue; - for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) - LiveIn[i]->addLiveIn(PhysReg); - LiveIn.clear(); + // Go over MBB begin positions and see if we have segments covering them. + // The following works because segments and the MBBIndex list are both + // sorted by slot indexes. + SlotIndexes::MBBIndexIterator I = Indexes->MBBIndexBegin(); + for (const auto &Seg : LI) { + I = Indexes->advanceMBBIndex(I, Seg.start); + for (; I != Indexes->MBBIndexEnd() && I->first < Seg.end; ++I) { + MachineBasicBlock *MBB = I->second; + MBB->addLiveIn(PhysReg); + } } } } -- 2.34.1