X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSplitKit.cpp;h=51dddabed2d9ea7bb1892d44283563ffda3bb27f;hb=810bd4f2193675f5b4ac2601a1671e6526c43489;hp=b1416cc17e595594c5ccabe19cdecf8083d5a547;hpb=b5a457c4cbc71db6ae313ef1bf8eadac65767ab0;p=oota-llvm.git diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp index b1416cc17e5..51dddabed2d 100644 --- a/lib/CodeGen/SplitKit.cpp +++ b/lib/CodeGen/SplitKit.cpp @@ -12,15 +12,15 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "regalloc" #include "SplitKit.h" -#include "LiveRangeEdit.h" -#include "VirtRegMap.h" #include "llvm/ADT/Statistic.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" +#include "llvm/CodeGen/LiveRangeEdit.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineInstrBuilder.h" +#include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/VirtRegMap.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" @@ -28,6 +28,8 @@ using namespace llvm; +#define DEBUG_TYPE "regalloc" + STATISTIC(NumFinished, "Number of splits finished"); STATISTIC(NumSimple, "Number of splits that were simple"); STATISTIC(NumCopies, "Number of copies inserted for splitting"); @@ -38,36 +40,33 @@ STATISTIC(NumRepairs, "Number of invalid live ranges repaired"); // Split Analysis //===----------------------------------------------------------------------===// -SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, - const LiveIntervals &lis, +SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis, const MachineLoopInfo &mli) - : MF(vrm.getMachineFunction()), - VRM(vrm), - LIS(lis), - Loops(mli), - TII(*MF.getTarget().getInstrInfo()), - CurLI(0), - LastSplitPoint(MF.getNumBlockIDs()) {} + : 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 = 0; + CurLI = nullptr; DidRepairRange = false; } SlotIndex SplitAnalysis::computeLastSplitPoint(unsigned Num) { const MachineBasicBlock *MBB = MF.getBlockNumbered(Num); + // FIXME: Handle multiple EH pad successors. const MachineBasicBlock *LPad = MBB->getLandingPadSuccessor(); std::pair &LSP = LastSplitPoint[Num]; + SlotIndex MBBEnd = LIS.getMBBEndIdx(MBB); // Compute split 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 = LIS.getMBBEndIdx(MBB); + LSP.first = MBBEnd; else LSP.first = LIS.getInstructionIndex(FirstTerm); @@ -79,7 +78,7 @@ SlotIndex SplitAnalysis::computeLastSplitPoint(unsigned Num) { for (MachineBasicBlock::const_iterator I = MBB->end(), E = MBB->begin(); I != E;) { --I; - if (I->getDesc().isCall()) { + if (I->isCall()) { LSP.second = LIS.getInstructionIndex(I); break; } @@ -88,10 +87,32 @@ SlotIndex SplitAnalysis::computeLastSplitPoint(unsigned Num) { // If CurLI is live into a landing pad successor, move the last split point // back to the call that may throw. - if (LPad && LSP.second.isValid() && LIS.isLiveInToMBB(*CurLI, LPad)) - return LSP.second; - else + if (!LPad || !LSP.second || !LIS.isLiveInToMBB(*CurLI, LPad)) return LSP.first; + + // Find the value leaving MBB. + const VNInfo *VNI = CurLI->getVNInfoBefore(MBBEnd); + if (!VNI) + return LSP.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; + + // Value is properly live-in to the landing pad. + // Only allow splits before the call. + return LSP.second; +} + +MachineBasicBlock::iterator +SplitAnalysis::getLastSplitPointIter(MachineBasicBlock *MBB) { + SlotIndex LSP = getLastSplitPoint(MBB->getNumber()); + if (LSP == LIS.getMBBEndIdx(MBB)) + return MBB->end(); + return LIS.getInstructionFromIndex(LSP); } /// analyzeUses - Count instructions, basic blocks, and loops using CurLI. @@ -100,18 +121,15 @@ void SplitAnalysis::analyzeUses() { // First get all the defs from the interval values. This provides the correct // slots for early clobbers. - for (LiveInterval::const_vni_iterator I = CurLI->vni_begin(), - E = CurLI->vni_end(); I != E; ++I) - if (!(*I)->isPHIDef() && !(*I)->isUnused()) - UseSlots.push_back((*I)->def); + for (const VNInfo *VNI : CurLI->valnos) + if (!VNI->isPHIDef() && !VNI->isUnused()) + UseSlots.push_back(VNI->def); // Get use slots form the use-def chain. const MachineRegisterInfo &MRI = MF.getRegInfo(); - for (MachineRegisterInfo::use_nodbg_iterator - I = MRI.use_nodbg_begin(CurLI->reg), E = MRI.use_nodbg_end(); I != E; - ++I) - if (!I.getOperand().isUndef()) - UseSlots.push_back(LIS.getInstructionIndex(&*I).getDefIndex()); + for (MachineOperand &MO : MRI.use_nodbg_operands(CurLI->reg)) + if (!MO.isUndef()) + UseSlots.push_back(LIS.getInstructionIndex(MO.getParent()).getRegSlot()); array_pod_sort(UseSlots.begin(), UseSlots.end()); @@ -159,12 +177,13 @@ bool SplitAnalysis::calcLiveBlockInfo() { UseE = UseSlots.end(); // Loop over basic blocks where CurLI is live. - MachineFunction::iterator MFI = LIS.getMBBFromIndex(LVI->start); + MachineFunction::iterator MFI = + LIS.getMBBFromIndex(LVI->start)->getIterator(); for (;;) { BlockInfo BI; - BI.MBB = MFI; + BI.MBB = &*MFI; SlotIndex Start, Stop; - tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); + std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); // If the block contains no uses, the range must be live through. At one // point, RegisterCoalescer could create dangling ranges that ended @@ -190,7 +209,7 @@ bool SplitAnalysis::calcLiveBlockInfo() { // When not live in, the first use should be a def. if (!BI.LiveIn) { - assert(LVI->start == LVI->valno->def && "Dangling LiveRange start"); + assert(LVI->start == LVI->valno->def && "Dangling Segment start"); assert(LVI->start == BI.FirstInstr && "First instr should be a def"); BI.FirstDef = BI.FirstInstr; } @@ -221,8 +240,8 @@ bool SplitAnalysis::calcLiveBlockInfo() { BI.FirstInstr = BI.FirstDef = LVI->start; } - // A LiveRange that starts in the middle of the block must be a def. - assert(LVI->start == LVI->valno->def && "Dangling LiveRange start"); + // A Segment that starts in the middle of the block must be a def. + assert(LVI->start == LVI->valno->def && "Dangling Segment start"); if (!BI.FirstDef) BI.FirstDef = LVI->start; } @@ -242,7 +261,7 @@ bool SplitAnalysis::calcLiveBlockInfo() { if (LVI->start < Stop) ++MFI; else - MFI = LIS.getMBBFromIndex(LVI->start); + MFI = LIS.getMBBFromIndex(LVI->start)->getIterator(); } assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count"); @@ -258,8 +277,9 @@ unsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const { unsigned Count = 0; // Loop over basic blocks where li is live. - MachineFunction::const_iterator MFI = LIS.getMBBFromIndex(LVI->start); - SlotIndex Stop = LIS.getMBBEndIdx(MFI); + MachineFunction::const_iterator MFI = + LIS.getMBBFromIndex(LVI->start)->getIterator(); + SlotIndex Stop = LIS.getMBBEndIdx(&*MFI); for (;;) { ++Count; LVI = li->advanceTo(LVI, Stop); @@ -267,7 +287,7 @@ unsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const { return Count; do { ++MFI; - Stop = LIS.getMBBEndIdx(MFI); + Stop = LIS.getMBBEndIdx(&*MFI); } while (Stop <= LVI->start); } } @@ -298,20 +318,14 @@ void SplitAnalysis::analyze(const LiveInterval *li) { //===----------------------------------------------------------------------===// /// Create a new SplitEditor for editing the LiveInterval analyzed by SA. -SplitEditor::SplitEditor(SplitAnalysis &sa, - LiveIntervals &lis, - VirtRegMap &vrm, - MachineDominatorTree &mdt) - : SA(sa), LIS(lis), VRM(vrm), - MRI(vrm.getMachineFunction().getRegInfo()), - MDT(mdt), - TII(*vrm.getMachineFunction().getTarget().getInstrInfo()), - TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()), - Edit(0), - OpenIdx(0), - SpillMode(SM_Partition), - RegAssign(Allocator) -{} +SplitEditor::SplitEditor(SplitAnalysis &sa, LiveIntervals &lis, VirtRegMap &vrm, + MachineDominatorTree &mdt, + MachineBlockFrequencyInfo &mbfi) + : SA(sa), LIS(lis), VRM(vrm), MRI(vrm.getMachineFunction().getRegInfo()), + MDT(mdt), TII(*vrm.getMachineFunction().getSubtarget().getInstrInfo()), + TRI(*vrm.getMachineFunction().getSubtarget().getRegisterInfo()), + MBFI(mbfi), Edit(nullptr), OpenIdx(0), SpillMode(SM_Partition), + RegAssign(Allocator) {} void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) { Edit = &LRE; @@ -319,13 +333,20 @@ void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) { OpenIdx = 0; RegAssign.clear(); Values.clear(); - LRCalc.reset(&VRM.getMachineFunction()); + + // Reset the LiveRangeCalc instances needed for this spill mode. + LRCalc[0].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, + &LIS.getVNInfoAllocator()); + if (SpillMode) + LRCalc[1].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, + &LIS.getVNInfoAllocator()); // We don't need an AliasAnalysis since we will only be performing // cheap-as-a-copy remats anyway. - Edit->anyRematerializable(LIS, TII, 0); + Edit->anyRematerializable(nullptr); } +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) void SplitEditor::dump() const { if (RegAssign.empty()) { dbgs() << " empty\n"; @@ -336,6 +357,7 @@ void SplitEditor::dump() const { dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); dbgs() << '\n'; } +#endif VNInfo *SplitEditor::defValue(unsigned RegIdx, const VNInfo *ParentVNI, @@ -343,14 +365,15 @@ VNInfo *SplitEditor::defValue(unsigned RegIdx, assert(ParentVNI && "Mapping NULL value"); assert(Idx.isValid() && "Invalid SlotIndex"); assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI"); - LiveInterval *LI = Edit->get(RegIdx); + LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); // Create a new value. - VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator()); + VNInfo *VNI = LI->getNextValue(Idx, LIS.getVNInfoAllocator()); // Use insert for lookup, so we can add missing values with a second lookup. std::pair InsP = - Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), VNI)); + Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), + ValueForcePair(VNI, false))); // This was the first time (RegIdx, ParentVNI) was mapped. // Keep it as a simple def without any liveness. @@ -358,40 +381,39 @@ VNInfo *SplitEditor::defValue(unsigned RegIdx, return VNI; // If the previous value was a simple mapping, add liveness for it now. - if (VNInfo *OldVNI = InsP.first->second) { + if (VNInfo *OldVNI = InsP.first->second.getPointer()) { SlotIndex Def = OldVNI->def; - LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI)); - // No longer a simple mapping. - InsP.first->second = 0; + LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), OldVNI)); + // No longer a simple mapping. Switch to a complex, non-forced mapping. + InsP.first->second = ValueForcePair(); } // This is a complex mapping, add liveness for VNI SlotIndex Def = VNI->def; - LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); + LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), VNI)); return VNI; } -void SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) { +void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo *ParentVNI) { assert(ParentVNI && "Mapping NULL value"); - VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)]; + ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI->id)]; + VNInfo *VNI = VFP.getPointer(); - // ParentVNI was either unmapped or already complex mapped. Either way. - if (!VNI) + // ParentVNI was either unmapped or already complex mapped. Either way, just + // set the force bit. + if (!VNI) { + VFP.setInt(true); return; + } // This was previously a single mapping. Make sure the old def is represented // by a trivial live range. SlotIndex Def = VNI->def; - Edit->get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI)); - VNI = 0; -} - -// extendRange - Extend the live range to reach Idx. -// Potentially create phi-def values. -void SplitEditor::extendRange(unsigned RegIdx, SlotIndex Idx) { - LRCalc.extend(Edit->get(RegIdx), Idx.getNextSlot(), - LIS.getSlotIndexes(), &MDT, &LIS.getVNInfoAllocator()); + LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); + LI->addSegment(LiveInterval::Segment(Def, Def.getDeadSlot(), VNI)); + // Mark as complex mapped, forced. + VFP = ValueForcePair(nullptr, true); } VNInfo *SplitEditor::defFromParent(unsigned RegIdx, @@ -399,9 +421,9 @@ VNInfo *SplitEditor::defFromParent(unsigned RegIdx, SlotIndex UseIdx, MachineBasicBlock &MBB, MachineBasicBlock::iterator I) { - MachineInstr *CopyMI = 0; + MachineInstr *CopyMI = nullptr; SlotIndex Def; - LiveInterval *LI = Edit->get(RegIdx); + LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); // We may be trying to avoid interference that ends at a deleted instruction, // so always begin RegIdx 0 early and all others late. @@ -409,33 +431,31 @@ VNInfo *SplitEditor::defFromParent(unsigned RegIdx, // Attempt cheap-as-a-copy rematerialization. LiveRangeEdit::Remat RM(ParentVNI); - if (Edit->canRematerializeAt(RM, UseIdx, true, LIS)) { - Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI, Late); + if (Edit->canRematerializeAt(RM, UseIdx, true)) { + Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, TRI, Late); ++NumRemats; } else { // Can't remat, just insert a copy from parent. CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg) .addReg(Edit->getReg()); Def = LIS.getSlotIndexes()->insertMachineInstrInMaps(CopyMI, Late) - .getDefIndex(); + .getRegSlot(); ++NumCopies; } // Define the value in Reg. - VNInfo *VNI = defValue(RegIdx, ParentVNI, Def); - VNI->setCopy(CopyMI); - return VNI; + return defValue(RegIdx, ParentVNI, Def); } /// Create a new virtual register and live interval. unsigned SplitEditor::openIntv() { // Create the complement as index 0. if (Edit->empty()) - Edit->create(LIS, VRM); + Edit->createEmptyInterval(); // Create the open interval. OpenIdx = Edit->size(); - Edit->create(LIS, VRM); + Edit->createEmptyInterval(); return OpenIdx; } @@ -477,7 +497,7 @@ SlotIndex SplitEditor::enterIntvAfter(SlotIndex Idx) { assert(MI && "enterIntvAfter called with invalid index"); VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), - llvm::next(MachineBasicBlock::iterator(MI))); + std::next(MachineBasicBlock::iterator(MI))); return VNI->def; } @@ -493,7 +513,7 @@ SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) { } DEBUG(dbgs() << ": valno " << ParentVNI->id); VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB, - LIS.getLastSplitPoint(Edit->getParent(), &MBB)); + SA.getLastSplitPointIter(&MBB)); RegAssign.insert(VNI->def, End, OpenIdx); DEBUG(dump()); return VNI->def; @@ -516,18 +536,29 @@ SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) { DEBUG(dbgs() << " leaveIntvAfter " << Idx); // The interval must be live beyond the instruction at Idx. - Idx = Idx.getBoundaryIndex(); - VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Idx); + SlotIndex Boundary = Idx.getBoundaryIndex(); + VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Boundary); if (!ParentVNI) { DEBUG(dbgs() << ": not live\n"); - return Idx.getNextSlot(); + return Boundary.getNextSlot(); } DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n'); - - MachineInstr *MI = LIS.getInstructionFromIndex(Idx); + MachineInstr *MI = LIS.getInstructionFromIndex(Boundary); assert(MI && "No instruction at index"); - VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), - llvm::next(MachineBasicBlock::iterator(MI))); + + // In spill mode, make live ranges as short as possible by inserting the copy + // before MI. This is only possible if that instruction doesn't redefine the + // value. The inserted COPY is not a kill, and we don't need to recompute + // the source live range. The spiller also won't try to hoist this copy. + if (SpillMode && !SlotIndex::isSameInstr(ParentVNI->def, Idx) && + MI->readsVirtualRegister(Edit->getReg())) { + forceRecompute(0, ParentVNI); + defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI); + return Idx; + } + + VNInfo *VNI = defFromParent(0, ParentVNI, Boundary, *MI->getParent(), + std::next(MachineBasicBlock::iterator(MI))); return VNI->def; } @@ -571,34 +602,232 @@ SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) { void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) { assert(OpenIdx && "openIntv not called before overlapIntv"); const VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(Start); - assert(ParentVNI == Edit->getParent().getVNInfoAt(End.getPrevSlot()) && + assert(ParentVNI == Edit->getParent().getVNInfoBefore(End) && "Parent changes value in extended range"); assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) && "Range cannot span basic blocks"); - // The complement interval will be extended as needed by extendRange(). + // The complement interval will be extended as needed by LRCalc.extend(). if (ParentVNI) - markComplexMapped(0, ParentVNI); + forceRecompute(0, ParentVNI); DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):"); RegAssign.insert(Start, End, OpenIdx); DEBUG(dump()); } +//===----------------------------------------------------------------------===// +// Spill modes +//===----------------------------------------------------------------------===// + +void SplitEditor::removeBackCopies(SmallVectorImpl &Copies) { + LiveInterval *LI = &LIS.getInterval(Edit->get(0)); + DEBUG(dbgs() << "Removing " << Copies.size() << " back-copies.\n"); + RegAssignMap::iterator AssignI; + AssignI.setMap(RegAssign); + + for (unsigned i = 0, e = Copies.size(); i != e; ++i) { + SlotIndex Def = Copies[i]->def; + MachineInstr *MI = LIS.getInstructionFromIndex(Def); + assert(MI && "No instruction for back-copy"); + + MachineBasicBlock *MBB = MI->getParent(); + MachineBasicBlock::iterator MBBI(MI); + bool AtBegin; + do AtBegin = MBBI == MBB->begin(); + while (!AtBegin && (--MBBI)->isDebugValue()); + + DEBUG(dbgs() << "Removing " << Def << '\t' << *MI); + LIS.removeVRegDefAt(*LI, Def); + LIS.RemoveMachineInstrFromMaps(MI); + MI->eraseFromParent(); + + // Adjust RegAssign if a register assignment is killed at Def. We want to + // avoid calculating the live range of the source register if possible. + AssignI.find(Def.getPrevSlot()); + if (!AssignI.valid() || AssignI.start() >= Def) + continue; + // If MI doesn't kill the assigned register, just leave it. + if (AssignI.stop() != Def) + continue; + unsigned RegIdx = AssignI.value(); + if (AtBegin || !MBBI->readsVirtualRegister(Edit->getReg())) { + DEBUG(dbgs() << " cannot find simple kill of RegIdx " << RegIdx << '\n'); + forceRecompute(RegIdx, Edit->getParent().getVNInfoAt(Def)); + } else { + SlotIndex Kill = LIS.getInstructionIndex(MBBI).getRegSlot(); + DEBUG(dbgs() << " move kill to " << Kill << '\t' << *MBBI); + AssignI.setStop(Kill); + } + } +} + +MachineBasicBlock* +SplitEditor::findShallowDominator(MachineBasicBlock *MBB, + MachineBasicBlock *DefMBB) { + if (MBB == DefMBB) + return MBB; + assert(MDT.dominates(DefMBB, MBB) && "MBB must be dominated by the def."); + + const MachineLoopInfo &Loops = SA.Loops; + const MachineLoop *DefLoop = Loops.getLoopFor(DefMBB); + MachineDomTreeNode *DefDomNode = MDT[DefMBB]; + + // Best candidate so far. + MachineBasicBlock *BestMBB = MBB; + unsigned BestDepth = UINT_MAX; + + for (;;) { + const MachineLoop *Loop = Loops.getLoopFor(MBB); + + // MBB isn't in a loop, it doesn't get any better. All dominators have a + // higher frequency by definition. + if (!Loop) { + DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#" + << MBB->getNumber() << " at depth 0\n"); + return MBB; + } + + // We'll never be able to exit the DefLoop. + if (Loop == DefLoop) { + DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#" + << MBB->getNumber() << " in the same loop\n"); + return MBB; + } + + // Least busy dominator seen so far. + unsigned Depth = Loop->getLoopDepth(); + if (Depth < BestDepth) { + BestMBB = MBB; + BestDepth = Depth; + DEBUG(dbgs() << "Def in BB#" << DefMBB->getNumber() << " dominates BB#" + << MBB->getNumber() << " at depth " << Depth << '\n'); + } + + // Leave loop by going to the immediate dominator of the loop header. + // This is a bigger stride than simply walking up the dominator tree. + MachineDomTreeNode *IDom = MDT[Loop->getHeader()]->getIDom(); + + // Too far up the dominator tree? + if (!IDom || !MDT.dominates(DefDomNode, IDom)) + return BestMBB; + + MBB = IDom->getBlock(); + } +} + +void SplitEditor::hoistCopiesForSize() { + // Get the complement interval, always RegIdx 0. + LiveInterval *LI = &LIS.getInterval(Edit->get(0)); + LiveInterval *Parent = &Edit->getParent(); + + // Track the nearest common dominator for all back-copies for each ParentVNI, + // indexed by ParentVNI->id. + typedef std::pair DomPair; + SmallVector NearestDom(Parent->getNumValNums()); + + // Find the nearest common dominator for parent values with multiple + // back-copies. If a single back-copy dominates, put it in DomPair.second. + for (VNInfo *VNI : LI->valnos) { + if (VNI->isUnused()) + continue; + VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def); + assert(ParentVNI && "Parent not live at complement def"); + + // Don't hoist remats. The complement is probably going to disappear + // completely anyway. + if (Edit->didRematerialize(ParentVNI)) + continue; + + MachineBasicBlock *ValMBB = LIS.getMBBFromIndex(VNI->def); + DomPair &Dom = NearestDom[ParentVNI->id]; + + // Keep directly defined parent values. This is either a PHI or an + // instruction in the complement range. All other copies of ParentVNI + // should be eliminated. + if (VNI->def == ParentVNI->def) { + DEBUG(dbgs() << "Direct complement def at " << VNI->def << '\n'); + Dom = DomPair(ValMBB, VNI->def); + continue; + } + // Skip the singly mapped values. There is nothing to gain from hoisting a + // single back-copy. + if (Values.lookup(std::make_pair(0, ParentVNI->id)).getPointer()) { + DEBUG(dbgs() << "Single complement def at " << VNI->def << '\n'); + continue; + } + + if (!Dom.first) { + // First time we see ParentVNI. VNI dominates itself. + Dom = DomPair(ValMBB, VNI->def); + } else if (Dom.first == ValMBB) { + // Two defs in the same block. Pick the earlier def. + if (!Dom.second.isValid() || VNI->def < Dom.second) + Dom.second = VNI->def; + } else { + // Different basic blocks. Check if one dominates. + MachineBasicBlock *Near = + MDT.findNearestCommonDominator(Dom.first, ValMBB); + if (Near == ValMBB) + // Def ValMBB dominates. + Dom = DomPair(ValMBB, VNI->def); + else if (Near != Dom.first) + // None dominate. Hoist to common dominator, need new def. + Dom = DomPair(Near, SlotIndex()); + } + + DEBUG(dbgs() << "Multi-mapped complement " << VNI->id << '@' << VNI->def + << " for parent " << ParentVNI->id << '@' << ParentVNI->def + << " hoist to BB#" << Dom.first->getNumber() << ' ' + << Dom.second << '\n'); + } + + // Insert the hoisted copies. + for (unsigned i = 0, e = Parent->getNumValNums(); i != e; ++i) { + DomPair &Dom = NearestDom[i]; + if (!Dom.first || Dom.second.isValid()) + continue; + // This value needs a hoisted copy inserted at the end of Dom.first. + VNInfo *ParentVNI = Parent->getValNumInfo(i); + MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(ParentVNI->def); + // Get a less loopy dominator than Dom.first. + Dom.first = findShallowDominator(Dom.first, DefMBB); + SlotIndex Last = LIS.getMBBEndIdx(Dom.first).getPrevSlot(); + Dom.second = + defFromParent(0, ParentVNI, Last, *Dom.first, + SA.getLastSplitPointIter(Dom.first))->def; + } + + // Remove redundant back-copies that are now known to be dominated by another + // def with the same value. + SmallVector BackCopies; + for (VNInfo *VNI : LI->valnos) { + if (VNI->isUnused()) + continue; + VNInfo *ParentVNI = Edit->getParent().getVNInfoAt(VNI->def); + const DomPair &Dom = NearestDom[ParentVNI->id]; + if (!Dom.first || Dom.second == VNI->def) + continue; + BackCopies.push_back(VNI); + forceRecompute(0, ParentVNI); + } + removeBackCopies(BackCopies); +} + + /// transferValues - Transfer all possible values to the new live ranges. -/// Values that were rematerialized are left alone, they need extendRange(). +/// Values that were rematerialized are left alone, they need LRCalc.extend(). bool SplitEditor::transferValues() { bool Skipped = false; RegAssignMap::const_iterator AssignI = RegAssign.begin(); - for (LiveInterval::const_iterator ParentI = Edit->getParent().begin(), - ParentE = Edit->getParent().end(); ParentI != ParentE; ++ParentI) { - DEBUG(dbgs() << " blit " << *ParentI << ':'); - VNInfo *ParentVNI = ParentI->valno; + for (const LiveRange::Segment &S : Edit->getParent()) { + DEBUG(dbgs() << " blit " << S << ':'); + VNInfo *ParentVNI = S.valno; // RegAssign has holes where RegIdx 0 should be used. - SlotIndex Start = ParentI->start; + SlotIndex Start = S.start; AssignI.advanceTo(Start); do { unsigned RegIdx; - SlotIndex End = ParentI->end; + SlotIndex End = S.end; if (!AssignI.valid()) { RegIdx = 0; } else if (AssignI.start() <= Start) { @@ -614,41 +843,42 @@ bool SplitEditor::transferValues() { // The interval [Start;End) is continuously mapped to RegIdx, ParentVNI. DEBUG(dbgs() << " [" << Start << ';' << End << ")=" << RegIdx); - LiveInterval *LI = Edit->get(RegIdx); + LiveRange &LR = LIS.getInterval(Edit->get(RegIdx)); // Check for a simply defined value that can be blitted directly. - if (VNInfo *VNI = Values.lookup(std::make_pair(RegIdx, ParentVNI->id))) { + ValueForcePair VFP = Values.lookup(std::make_pair(RegIdx, ParentVNI->id)); + if (VNInfo *VNI = VFP.getPointer()) { DEBUG(dbgs() << ':' << VNI->id); - LI->addRange(LiveRange(Start, End, VNI)); + LR.addSegment(LiveInterval::Segment(Start, End, VNI)); Start = End; continue; } - // Skip rematerialized values, we need to use extendRange() and - // extendPHIKillRanges() to completely recompute the live ranges. - if (Edit->didRematerialize(ParentVNI)) { - DEBUG(dbgs() << "(remat)"); + // Skip values with forced recomputation. + if (VFP.getInt()) { + DEBUG(dbgs() << "(recalc)"); Skipped = true; Start = End; continue; } + LiveRangeCalc &LRC = getLRCalc(RegIdx); + // This value has multiple defs in RegIdx, but it wasn't rematerialized, // so the live range is accurate. Add live-in blocks in [Start;End) to the // LiveInBlocks. - MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start); + MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator(); SlotIndex BlockStart, BlockEnd; - tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(MBB); + std::tie(BlockStart, BlockEnd) = LIS.getSlotIndexes()->getMBBRange(&*MBB); // The first block may be live-in, or it may have its own def. if (Start != BlockStart) { - VNInfo *VNI = LI->extendInBlock(BlockStart, - std::min(BlockEnd, End).getPrevSlot()); + VNInfo *VNI = LR.extendInBlock(BlockStart, std::min(BlockEnd, End)); assert(VNI && "Missing def for complex mapped value"); DEBUG(dbgs() << ':' << VNI->id << "*BB#" << MBB->getNumber()); // MBB has its own def. Is it also live-out? if (BlockEnd <= End) - LRCalc.setLiveOutValue(MBB, VNI); + LRC.setLiveOutValue(&*MBB, VNI); // Skip to the next block for live-in. ++MBB; @@ -659,57 +889,59 @@ bool SplitEditor::transferValues() { assert(Start <= BlockStart && "Expected live-in block"); while (BlockStart < End) { DEBUG(dbgs() << ">BB#" << MBB->getNumber()); - BlockEnd = LIS.getMBBEndIdx(MBB); + BlockEnd = LIS.getMBBEndIdx(&*MBB); if (BlockStart == ParentVNI->def) { // This block has the def of a parent PHI, so it isn't live-in. assert(ParentVNI->isPHIDef() && "Non-phi defined at block start?"); - VNInfo *VNI = LI->extendInBlock(BlockStart, - std::min(BlockEnd, End).getPrevSlot()); + VNInfo *VNI = LR.extendInBlock(BlockStart, std::min(BlockEnd, End)); assert(VNI && "Missing def for complex mapped parent PHI"); if (End >= BlockEnd) - LRCalc.setLiveOutValue(MBB, VNI); // Live-out as well. + LRC.setLiveOutValue(&*MBB, VNI); // Live-out as well. } else { // This block needs a live-in value. The last block covered may not // be live-out. if (End < BlockEnd) - LRCalc.addLiveInBlock(LI, MDT[MBB], End); + LRC.addLiveInBlock(LR, MDT[&*MBB], End); else { // Live-through, and we don't know the value. - LRCalc.addLiveInBlock(LI, MDT[MBB]); - LRCalc.setLiveOutValue(MBB, 0); + LRC.addLiveInBlock(LR, MDT[&*MBB]); + LRC.setLiveOutValue(&*MBB, nullptr); } } BlockStart = BlockEnd; ++MBB; } Start = End; - } while (Start != ParentI->end); + } while (Start != S.end); DEBUG(dbgs() << '\n'); } - LRCalc.calculateValues(LIS.getSlotIndexes(), &MDT, &LIS.getVNInfoAllocator()); + LRCalc[0].calculateValues(); + if (SpillMode) + LRCalc[1].calculateValues(); return Skipped; } void SplitEditor::extendPHIKillRanges() { // Extend live ranges to be live-out for successor PHI values. - for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), - E = Edit->getParent().vni_end(); I != E; ++I) { - const VNInfo *PHIVNI = *I; + for (const VNInfo *PHIVNI : Edit->getParent().valnos) { if (PHIVNI->isUnused() || !PHIVNI->isPHIDef()) continue; unsigned RegIdx = RegAssign.lookup(PHIVNI->def); + LiveRange &LR = LIS.getInterval(Edit->get(RegIdx)); + LiveRangeCalc &LRC = getLRCalc(RegIdx); MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def); for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), PE = MBB->pred_end(); PI != PE; ++PI) { - SlotIndex End = LIS.getMBBEndIdx(*PI).getPrevSlot(); + SlotIndex End = LIS.getMBBEndIdx(*PI); + SlotIndex LastUse = End.getPrevSlot(); // The predecessor may not have a live-out value. That is OK, like an // undef PHI operand. - if (Edit->getParent().liveAt(End)) { - assert(RegAssign.lookup(End) == RegIdx && + if (Edit->getParent().liveAt(LastUse)) { + assert(RegAssign.lookup(LastUse) == RegIdx && "Different register assignment in phi predecessor"); - extendRange(RegIdx, End); + LRC.extend(LR, End); } } } @@ -719,7 +951,7 @@ void SplitEditor::extendPHIKillRanges() { void SplitEditor::rewriteAssigned(bool ExtendRanges) { for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit->getReg()), RE = MRI.reg_end(); RI != RE;) { - MachineOperand &MO = RI.getOperand(); + MachineOperand &MO = *RI; MachineInstr *MI = MO.getParent(); ++RI; // LiveDebugVariables should have handled all DBG_VALUE instructions. @@ -734,11 +966,12 @@ void SplitEditor::rewriteAssigned(bool ExtendRanges) { // use the same register as the def, so just do that always. SlotIndex Idx = LIS.getInstructionIndex(MI); if (MO.isDef() || MO.isUndef()) - Idx = MO.isEarlyClobber() ? Idx.getUseIndex() : Idx.getDefIndex(); + Idx = Idx.getRegSlot(MO.isEarlyClobber()); // Rewrite to the mapped register at Idx. unsigned RegIdx = RegAssign.lookup(Idx); - MO.setReg(Edit->get(RegIdx)->reg); + LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); + MO.setReg(LI->reg); DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' << Idx << ':' << RegIdx << '\t' << *MI); @@ -756,22 +989,21 @@ void SplitEditor::rewriteAssigned(bool ExtendRanges) { if (!Edit->getParent().liveAt(Idx)) continue; } else - Idx = Idx.getUseIndex(); + Idx = Idx.getRegSlot(true); - extendRange(RegIdx, Idx); + getLRCalc(RegIdx).extend(*LI, Idx.getNextSlot()); } } void SplitEditor::deleteRematVictims() { SmallVector Dead; for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I){ - LiveInterval *LI = *I; - for (LiveInterval::const_iterator LII = LI->begin(), LIE = LI->end(); - LII != LIE; ++LII) { - // Dead defs end at the store slot. - if (LII->end != LII->valno->def.getNextSlot()) + LiveInterval *LI = &LIS.getInterval(*I); + for (const LiveRange::Segment &S : LI->segments) { + // Dead defs end at the dead slot. + if (S.end != S.valno->def.getDeadSlot()) continue; - MachineInstr *MI = LIS.getInstructionFromIndex(LII->valno->def); + MachineInstr *MI = LIS.getInstructionFromIndex(S.valno->def); assert(MI && "Missing instruction for dead def"); MI->addRegisterDead(LI->reg, &TRI); @@ -786,7 +1018,7 @@ void SplitEditor::deleteRematVictims() { if (Dead.empty()) return; - Edit->eliminateDeadDefs(Dead, LIS, VRM, TII); + Edit->eliminateDeadDefs(Dead); } void SplitEditor::finish(SmallVectorImpl *LRMap) { @@ -796,21 +1028,29 @@ void SplitEditor::finish(SmallVectorImpl *LRMap) { // the inserted copies. // Add the original defs from the parent interval. - for (LiveInterval::const_vni_iterator I = Edit->getParent().vni_begin(), - E = Edit->getParent().vni_end(); I != E; ++I) { - const VNInfo *ParentVNI = *I; + for (const VNInfo *ParentVNI : Edit->getParent().valnos) { if (ParentVNI->isUnused()) continue; unsigned RegIdx = RegAssign.lookup(ParentVNI->def); - VNInfo *VNI = defValue(RegIdx, ParentVNI, ParentVNI->def); - VNI->setIsPHIDef(ParentVNI->isPHIDef()); - VNI->setCopy(ParentVNI->getCopy()); + defValue(RegIdx, ParentVNI, ParentVNI->def); - // Mark rematted values as complex everywhere to force liveness computation. + // Force rematted values to be recomputed everywhere. // The new live ranges may be truncated. if (Edit->didRematerialize(ParentVNI)) for (unsigned i = 0, e = Edit->size(); i != e; ++i) - markComplexMapped(i, ParentVNI); + forceRecompute(i, ParentVNI); + } + + // Hoist back-copies to the complement interval when in spill mode. + switch (SpillMode) { + case SM_Partition: + // Leave all back-copies as is. + break; + case SM_Size: + hoistCopiesForSize(); + break; + case SM_Speed: + llvm_unreachable("Spill mode 'speed' not implemented yet"); } // Transfer the simply mapped values, check if any are skipped. @@ -828,8 +1068,10 @@ void SplitEditor::finish(SmallVectorImpl *LRMap) { deleteRematVictims(); // Get rid of unused values and set phi-kill flags. - for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) - (*I)->RenumberValues(LIS); + for (LiveRangeEdit::iterator I = Edit->begin(), E = Edit->end(); I != E; ++I) { + LiveInterval &LI = LIS.getInterval(*I); + LI.RenumberValues(); + } // Provide a reverse mapping from original indices to Edit ranges. if (LRMap) { @@ -842,23 +1084,21 @@ void SplitEditor::finish(SmallVectorImpl *LRMap) { ConnectedVNInfoEqClasses ConEQ(LIS); for (unsigned i = 0, e = Edit->size(); i != e; ++i) { // Don't use iterators, they are invalidated by create() below. - LiveInterval *li = Edit->get(i); - unsigned NumComp = ConEQ.Classify(li); - if (NumComp <= 1) - continue; - DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n'); - SmallVector dups; - dups.push_back(li); - for (unsigned j = 1; j != NumComp; ++j) - dups.push_back(&Edit->create(LIS, VRM)); - ConEQ.Distribute(&dups[0], MRI); + unsigned VReg = Edit->get(i); + LiveInterval &LI = LIS.getInterval(VReg); + SmallVector SplitLIs; + LIS.splitSeparateComponents(LI, SplitLIs); + unsigned Original = VRM.getOriginal(VReg); + for (LiveInterval *SplitLI : SplitLIs) + VRM.setIsSplitFromReg(SplitLI->reg, Original); + // The new intervals all map back to i. if (LRMap) LRMap->resize(Edit->size(), i); } // Calculate spill weight and allocation hints for new intervals. - Edit->calculateRegClassAndHint(VRM.getMachineFunction(), LIS, SA.Loops); + Edit->calculateRegClassAndHint(VRM.getMachineFunction(), SA.Loops, MBFI); assert(!LRMap || LRMap->size() == Edit->size()); } @@ -917,7 +1157,7 @@ void SplitEditor::splitLiveThroughBlock(unsigned MBBNum, unsigned IntvIn, SlotIndex LeaveBefore, unsigned IntvOut, SlotIndex EnterAfter){ SlotIndex Start, Stop; - tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum); + std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(MBBNum); DEBUG(dbgs() << "BB#" << MBBNum << " [" << Start << ';' << Stop << ") intf " << LeaveBefore << '-' << EnterAfter @@ -1020,7 +1260,7 @@ void SplitEditor::splitLiveThroughBlock(unsigned MBBNum, void SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI, unsigned IntvIn, SlotIndex LeaveBefore) { SlotIndex Start, Stop; - tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); + std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop << "), uses " << BI.FirstInstr << '-' << BI.LastInstr @@ -1112,7 +1352,7 @@ void SplitEditor::splitRegInBlock(const SplitAnalysis::BlockInfo &BI, void SplitEditor::splitRegOutBlock(const SplitAnalysis::BlockInfo &BI, unsigned IntvOut, SlotIndex EnterAfter) { SlotIndex Start, Stop; - tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); + std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB); DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " [" << Start << ';' << Stop << "), uses " << BI.FirstInstr << '-' << BI.LastInstr