X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSplitKit.cpp;h=80c9a83cb691281f6f6a3bd46cfab03cea6387e7;hb=283c82abaaa85d032725cba11fb9ad05c9a9b060;hp=89e85bd38381af1f3b30cee75922cb192fbeb4ea;hpb=e5a2e366322ef5f0d597b1fb8dbf55f2cf36cf15;p=oota-llvm.git diff --git a/lib/CodeGen/SplitKit.cpp b/lib/CodeGen/SplitKit.cpp index 89e85bd3838..80c9a83cb69 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,22 +40,17 @@ 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; } @@ -61,13 +58,14 @@ SlotIndex SplitAnalysis::computeLastSplitPoint(unsigned Num) { const MachineBasicBlock *MBB = MF.getBlockNumbered(Num); 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 +77,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 +86,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. @@ -107,11 +127,9 @@ void SplitAnalysis::analyzeUses() { // 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()); @@ -164,7 +182,7 @@ bool SplitAnalysis::calcLiveBlockInfo() { BlockInfo BI; 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 +208,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 +239,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; } @@ -298,39 +316,41 @@ 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() + .getTarget() + .getSubtargetImpl() + ->getInstrInfo()), + TRI(*vrm.getMachineFunction() + .getTarget() + .getSubtargetImpl() + ->getRegisterInfo()), + MBFI(mbfi), Edit(nullptr), OpenIdx(0), SpillMode(SM_Partition), + RegAssign(Allocator) {} void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) { Edit = &LRE; SpillMode = SM; OpenIdx = 0; - OverlappedComplement.clear(); RegAssign.clear(); Values.clear(); // Reset the LiveRangeCalc instances needed for this spill mode. - LRCalc[0].reset(&VRM.getMachineFunction()); + LRCalc[0].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT, + &LIS.getVNInfoAllocator()); if (SpillMode) - LRCalc[1].reset(&VRM.getMachineFunction()); + 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"; @@ -341,6 +361,7 @@ void SplitEditor::dump() const { dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value(); dbgs() << '\n'; } +#endif VNInfo *SplitEditor::defValue(unsigned RegIdx, const VNInfo *ParentVNI, @@ -348,14 +369,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. @@ -363,43 +385,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; -} - -void SplitEditor::markOverlappedComplement(const VNInfo *ParentVNI) { - if (OverlappedComplement.insert(ParentVNI)) - markComplexMapped(0, ParentVNI); -} - -bool SplitEditor::needsRecompute(unsigned RegIdx, const VNInfo *ParentVNI) { - return (RegIdx == 0 && OverlappedComplement.count(ParentVNI)) || - Edit->didRematerialize(ParentVNI); + 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, @@ -407,9 +425,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. @@ -417,33 +435,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; } @@ -485,7 +501,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; } @@ -501,7 +517,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; @@ -524,18 +540,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; } @@ -579,19 +606,224 @@ 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 LRCalc.extend(). if (ParentVNI) - markOverlappedComplement(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) { + VNInfo *VNI = Copies[i]; + SlotIndex Def = VNI->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); + LI->removeValNo(VNI); + LIS.RemoveMachineInstrFromMaps(MI); + MI->eraseFromParent(); + + // Adjust RegAssign if a register assignment is killed at VNI->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 (LiveInterval::vni_iterator VI = LI->vni_begin(), VE = LI->vni_end(); + VI != VE; ++VI) { + VNInfo *VNI = *VI; + 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 (LiveInterval::vni_iterator VI = LI->vni_begin(), VE = LI->vni_end(); + VI != VE; ++VI) { + VNInfo *VNI = *VI; + 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 LRCalc.extend(). bool SplitEditor::transferValues() { @@ -622,20 +854,20 @@ 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 LRCalc.extend() and - // extendPHIKillRanges() to completely recompute the live ranges. - if (needsRecompute(RegIdx, ParentVNI)) { - DEBUG(dbgs() << "(remat)"); + // Skip values with forced recomputation. + if (VFP.getInt()) { + DEBUG(dbgs() << "(recalc)"); Skipped = true; Start = End; continue; @@ -648,11 +880,11 @@ bool SplitEditor::transferValues() { // LiveInBlocks. MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start); 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)); + 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? @@ -672,7 +904,7 @@ bool SplitEditor::transferValues() { 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)); + VNInfo *VNI = LR.extendInBlock(BlockStart, std::min(BlockEnd, End)); assert(VNI && "Missing def for complex mapped parent PHI"); if (End >= BlockEnd) LRC.setLiveOutValue(MBB, VNI); // Live-out as well. @@ -680,11 +912,11 @@ bool SplitEditor::transferValues() { // This block needs a live-in value. The last block covered may not // be live-out. if (End < BlockEnd) - LRC.addLiveInBlock(LI, MDT[MBB], End); + LRC.addLiveInBlock(LR, MDT[MBB], End); else { // Live-through, and we don't know the value. - LRC.addLiveInBlock(LI, MDT[MBB]); - LRC.setLiveOutValue(MBB, 0); + LRC.addLiveInBlock(LR, MDT[MBB]); + LRC.setLiveOutValue(MBB, nullptr); } } BlockStart = BlockEnd; @@ -695,11 +927,9 @@ bool SplitEditor::transferValues() { DEBUG(dbgs() << '\n'); } - LRCalc[0].calculateValues(LIS.getSlotIndexes(), &MDT, - &LIS.getVNInfoAllocator()); + LRCalc[0].calculateValues(); if (SpillMode) - LRCalc[1].calculateValues(LIS.getSlotIndexes(), &MDT, - &LIS.getVNInfoAllocator()); + LRCalc[1].calculateValues(); return Skipped; } @@ -712,7 +942,7 @@ void SplitEditor::extendPHIKillRanges() { if (PHIVNI->isUnused() || !PHIVNI->isPHIDef()) continue; unsigned RegIdx = RegAssign.lookup(PHIVNI->def); - LiveInterval *LI = Edit->get(RegIdx); + 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(), @@ -724,8 +954,7 @@ void SplitEditor::extendPHIKillRanges() { if (Edit->getParent().liveAt(LastUse)) { assert(RegAssign.lookup(LastUse) == RegIdx && "Different register assignment in phi predecessor"); - LRC.extend(LI, End, - LIS.getSlotIndexes(), &MDT, &LIS.getVNInfoAllocator()); + LRC.extend(LR, End); } } } @@ -735,7 +964,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. @@ -750,11 +979,11 @@ 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); - LiveInterval *LI = Edit->get(RegIdx); + LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx)); MO.setReg(LI->reg); DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t' << Idx << ':' << RegIdx << '\t' << *MI); @@ -773,21 +1002,20 @@ void SplitEditor::rewriteAssigned(bool ExtendRanges) { if (!Edit->getParent().liveAt(Idx)) continue; } else - Idx = Idx.getUseIndex(); + Idx = Idx.getRegSlot(true); - getLRCalc(RegIdx).extend(LI, Idx.getNextSlot(), LIS.getSlotIndexes(), - &MDT, &LIS.getVNInfoAllocator()); + 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; + LiveInterval *LI = &LIS.getInterval(*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()) + // Dead defs end at the dead slot. + if (LII->end != LII->valno->def.getDeadSlot()) continue; MachineInstr *MI = LIS.getInstructionFromIndex(LII->valno->def); assert(MI && "Missing instruction for dead def"); @@ -804,7 +1032,7 @@ void SplitEditor::deleteRematVictims() { if (Dead.empty()) return; - Edit->eliminateDeadDefs(Dead, LIS, VRM, TII); + Edit->eliminateDeadDefs(Dead); } void SplitEditor::finish(SmallVectorImpl *LRMap) { @@ -820,15 +1048,25 @@ void SplitEditor::finish(SmallVectorImpl *LRMap) { 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. @@ -846,8 +1084,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) { @@ -860,7 +1100,7 @@ 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); + LiveInterval *li = &LIS.getInterval(Edit->get(i)); unsigned NumComp = ConEQ.Classify(li); if (NumComp <= 1) continue; @@ -868,7 +1108,7 @@ void SplitEditor::finish(SmallVectorImpl *LRMap) { SmallVector dups; dups.push_back(li); for (unsigned j = 1; j != NumComp; ++j) - dups.push_back(&Edit->create(LIS, VRM)); + dups.push_back(&Edit->createEmptyInterval()); ConEQ.Distribute(&dups[0], MRI); // The new intervals all map back to i. if (LRMap) @@ -876,7 +1116,7 @@ void SplitEditor::finish(SmallVectorImpl *LRMap) { } // 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()); } @@ -935,7 +1175,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 @@ -1038,7 +1278,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 @@ -1130,7 +1370,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