X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocLinearScan.cpp;h=ce3fb90b1126ad00d0b6bf810c0a1c18ecf8b56a;hb=f4b841d4e2754861adade83ece637f84aed031da;hp=ab4068e6e4c30ef44c2bd1a68f60b0236fa8e44e;hpb=550aacb978a8391f605c6ec1feca7d797415d38b;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp index ab4068e6e4c..ce3fb90b112 100644 --- a/lib/CodeGen/RegAllocLinearScan.cpp +++ b/lib/CodeGen/RegAllocLinearScan.cpp @@ -12,19 +12,22 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "regalloc" +#include "LiveDebugVariables.h" +#include "LiveRangeEdit.h" #include "VirtRegMap.h" #include "VirtRegRewriter.h" +#include "RegisterClassInfo.h" #include "Spiller.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Function.h" +#include "llvm/CodeGen/CalcSpillWeights.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" -#include "llvm/CodeGen/LiveStackAnalysis.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" #include "llvm/CodeGen/RegAllocRegistry.h" -#include "llvm/CodeGen/RegisterCoalescer.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetOptions.h" @@ -34,9 +37,9 @@ #include "llvm/ADT/Statistic.h" #include "llvm/ADT/STLExtras.h" #include "llvm/Support/Debug.h" -#include "llvm/Support/Compiler.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" #include -#include #include #include #include @@ -54,23 +57,59 @@ NewHeuristic("new-spilling-heuristic", cl::init(false), cl::Hidden); static cl::opt -PreSplitIntervals("pre-alloc-split", - cl::desc("Pre-register allocation live interval splitting"), +TrivCoalesceEnds("trivial-coalesce-ends", + cl::desc("Attempt trivial coalescing of interval ends"), cl::init(false), cl::Hidden); static cl::opt -NewSpillFramework("new-spill-framework", - cl::desc("New spilling framework"), - cl::init(false), cl::Hidden); +AvoidWAWHazard("avoid-waw-hazard", + cl::desc("Avoid write-write hazards for some register classes"), + cl::init(false), cl::Hidden); static RegisterRegAlloc linearscanRegAlloc("linearscan", "linear scan register allocator", createLinearScanRegisterAllocator); namespace { - struct VISIBILITY_HIDDEN RALinScan : public MachineFunctionPass { + // When we allocate a register, add it to a fixed-size queue of + // registers to skip in subsequent allocations. This trades a small + // amount of register pressure and increased spills for flexibility in + // the post-pass scheduler. + // + // Note that in a the number of registers used for reloading spills + // will be one greater than the value of this option. + // + // One big limitation of this is that it doesn't differentiate between + // different register classes. So on x86-64, if there is xmm register + // pressure, it can caused fewer GPRs to be held in the queue. + static cl::opt + NumRecentlyUsedRegs("linearscan-skip-count", + cl::desc("Number of registers for linearscan to remember" + "to skip."), + cl::init(0), + cl::Hidden); + + struct RALinScan : public MachineFunctionPass { static char ID; - RALinScan() : MachineFunctionPass(&ID) {} + RALinScan() : MachineFunctionPass(ID) { + initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry()); + initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); + initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry()); + initializeRegisterCoalescerPass( + *PassRegistry::getPassRegistry()); + initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); + initializeLiveStacksPass(*PassRegistry::getPassRegistry()); + initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); + initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); + initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); + initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry()); + + // Initialize the queue to record recently-used registers. + if (NumRecentlyUsedRegs > 0) + RecentRegs.resize(NumRecentlyUsedRegs, 0); + RecentNext = RecentRegs.begin(); + avoidWAW_ = 0; + } typedef std::pair IntervalPtr; typedef SmallVector IntervalPtrs; @@ -100,9 +139,10 @@ namespace { const TargetRegisterInfo* tri_; const TargetInstrInfo* tii_; BitVector allocatableRegs_; + BitVector reservedRegs_; LiveIntervals* li_; - LiveStacks* ls_; - const MachineLoopInfo *loopInfo; + MachineLoopInfo *loopInfo; + RegisterClassInfo RegClassInfo; /// handled_ - Intervals are added to the handled_ set in the order of their /// start value. This is uses for backtracking. @@ -136,26 +176,49 @@ namespace { std::auto_ptr spiller_; + // The queue of recently-used registers. + SmallVector RecentRegs; + SmallVector::iterator RecentNext; + + // Last write-after-write register written. + unsigned avoidWAW_; + + // Record that we just picked this register. + void recordRecentlyUsed(unsigned reg) { + assert(reg != 0 && "Recently used register is NOREG!"); + if (!RecentRegs.empty()) { + *RecentNext++ = reg; + if (RecentNext == RecentRegs.end()) + RecentNext = RecentRegs.begin(); + } + } + public: virtual const char* getPassName() const { return "Linear Scan Register Allocator"; } virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesCFG(); + AU.addRequired(); + AU.addPreserved(); AU.addRequired(); + AU.addPreserved(); if (StrongPHIElim) AU.addRequiredID(StrongPHIEliminationID); // Make sure PassManager knows which analyses to make available // to coalescing and which analyses coalescing invalidates. - AU.addRequiredTransitive(); - if (PreSplitIntervals) - AU.addRequiredID(PreAllocSplittingID); - AU.addRequired(); - AU.addPreserved(); + AU.addRequiredTransitiveID(RegisterCoalescerPassID); + AU.addRequired(); + AU.addRequiredID(LiveStacksID); + AU.addPreservedID(LiveStacksID); AU.addRequired(); AU.addPreserved(); AU.addRequired(); AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); + AU.addRequiredID(MachineDominatorsID); AU.addPreservedID(MachineDominatorsID); MachineFunctionPass::getAnalysisUsage(AU); } @@ -163,6 +226,12 @@ namespace { /// runOnMachineFunction - register allocate the whole function bool runOnMachineFunction(MachineFunction&); + // Determine if we skip this register due to its being recently used. + bool isRecentlyUsed(unsigned reg) const { + return reg == avoidWAW_ || + std::find(RecentRegs.begin(), RecentRegs.end(), reg) != RecentRegs.end(); + } + private: /// linearScan - the linear scan algorithm void linearScan(); @@ -173,11 +242,11 @@ namespace { /// processActiveIntervals - expire old intervals and move non-overlapping /// ones to the inactive list. - void processActiveIntervals(unsigned CurPoint); + void processActiveIntervals(SlotIndex CurPoint); /// processInactiveIntervals - expire old intervals and move overlapping /// ones to the active list. - void processInactiveIntervals(unsigned CurPoint); + void processInactiveIntervals(SlotIndex CurPoint); /// hasNextReloadInterval - Return the next liveinterval that's being /// defined by a reload from the same SS as the specified one. @@ -207,9 +276,9 @@ namespace { SmallVector &SpillIntervals); /// attemptTrivialCoalescing - If a simple interval is defined by a copy, - /// try allocate the definition the same register as the source register - /// if the register is not defined during live time of the interval. This - /// eliminate a copy. This is used to coalesce copies which were not + /// try to allocate the definition to the same register as the source, + /// if the register is not defined during the life time of the interval. + /// This eliminates a copy, and is used to coalesce copies which were not /// coalesced away before allocation either due to dest and src being in /// different register classes or because the coalescer was overly /// conservative. @@ -230,12 +299,12 @@ namespace { bool Error = false; for (unsigned i = 0, e = tri_->getNumRegs(); i != e; ++i) { if (regUse_[i] != 0) { - cerr << tri_->getName(i) << " is still in use!\n"; + dbgs() << tri_->getName(i) << " is still in use!\n"; Error = true; } } if (Error) - abort(); + llvm_unreachable(0); #endif regUse_.clear(); regUseBackUp_.clear(); @@ -281,35 +350,55 @@ namespace { /// getFreePhysReg - return a free physical register for this virtual /// register interval if we have one, otherwise return 0. unsigned getFreePhysReg(LiveInterval* cur); - unsigned getFreePhysReg(const TargetRegisterClass *RC, + unsigned getFreePhysReg(LiveInterval* cur, + const TargetRegisterClass *RC, unsigned MaxInactiveCount, SmallVector &inactiveCounts, bool SkipDGRegs); - /// assignVirt2StackSlot - assigns this virtual register to a - /// stack slot. returns the stack slot - int assignVirt2StackSlot(unsigned virtReg); + /// getFirstNonReservedPhysReg - return the first non-reserved physical + /// register in the register class. + unsigned getFirstNonReservedPhysReg(const TargetRegisterClass *RC) { + ArrayRef O = RegClassInfo.getOrder(RC); + assert(!O.empty() && "All registers reserved?!"); + return O.front(); + } void ComputeRelatedRegClasses(); template void printIntervals(const char* const str, ItTy i, ItTy e) const { - if (str) DOUT << str << " intervals:\n"; - for (; i != e; ++i) { - DOUT << "\t" << *i->first << " -> "; - unsigned reg = i->first->reg; - if (TargetRegisterInfo::isVirtualRegister(reg)) { - reg = vrm_->getPhys(reg); - } - DOUT << tri_->getName(reg) << '\n'; - } + DEBUG({ + if (str) + dbgs() << str << " intervals:\n"; + + for (; i != e; ++i) { + dbgs() << '\t' << *i->first << " -> "; + + unsigned reg = i->first->reg; + if (TargetRegisterInfo::isVirtualRegister(reg)) + reg = vrm_->getPhys(reg); + + dbgs() << tri_->getName(reg) << '\n'; + } + }); } }; char RALinScan::ID = 0; } -static RegisterPass -X("linearscan-regalloc", "Linear Scan Register Allocator"); +INITIALIZE_PASS_BEGIN(RALinScan, "linearscan-regalloc", + "Linear Scan Register Allocator", false, false) +INITIALIZE_PASS_DEPENDENCY(LiveIntervals) +INITIALIZE_PASS_DEPENDENCY(StrongPHIElimination) +INITIALIZE_PASS_DEPENDENCY(CalculateSpillWeights) +INITIALIZE_PASS_DEPENDENCY(LiveStacks) +INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) +INITIALIZE_PASS_DEPENDENCY(VirtRegMap) +INITIALIZE_PASS_DEPENDENCY(RegisterCoalescer) +INITIALIZE_AG_DEPENDENCY(AliasAnalysis) +INITIALIZE_PASS_END(RALinScan, "linearscan-regalloc", + "Linear Scan Register Allocator", false, false) void RALinScan::ComputeRelatedRegClasses() { // First pass, add all reg classes to the union, and determine at least one @@ -321,7 +410,7 @@ void RALinScan::ComputeRelatedRegClasses() { for (TargetRegisterClass::iterator I = (*RCI)->begin(), E = (*RCI)->end(); I != E; ++I) { HasAliases = HasAliases || *tri_->getAliasSet(*I) != 0; - + const TargetRegisterClass *&PRC = OneClassForEachPhysReg[*I]; if (PRC) { // Already processed this register. Just make sure we know that @@ -332,7 +421,7 @@ void RALinScan::ComputeRelatedRegClasses() { } } } - + // Second pass, now that we know conservatively what register classes each reg // belongs to, add info about aliases. We don't need to do this for targets // without register aliases. @@ -340,68 +429,78 @@ void RALinScan::ComputeRelatedRegClasses() { for (DenseMap::iterator I = OneClassForEachPhysReg.begin(), E = OneClassForEachPhysReg.end(); I != E; ++I) - for (const unsigned *AS = tri_->getAliasSet(I->first); *AS; ++AS) - RelatedRegClasses.unionSets(I->second, OneClassForEachPhysReg[*AS]); + for (const unsigned *AS = tri_->getAliasSet(I->first); *AS; ++AS) { + const TargetRegisterClass *AliasClass = + OneClassForEachPhysReg.lookup(*AS); + if (AliasClass) + RelatedRegClasses.unionSets(I->second, AliasClass); + } } -/// attemptTrivialCoalescing - If a simple interval is defined by a copy, -/// try allocate the definition the same register as the source register -/// if the register is not defined during live time of the interval. This -/// eliminate a copy. This is used to coalesce copies which were not -/// coalesced away before allocation either due to dest and src being in -/// different register classes or because the coalescer was overly -/// conservative. +/// attemptTrivialCoalescing - If a simple interval is defined by a copy, try +/// allocate the definition the same register as the source register if the +/// register is not defined during live time of the interval. If the interval is +/// killed by a copy, try to use the destination register. This eliminates a +/// copy. This is used to coalesce copies which were not coalesced away before +/// allocation either due to dest and src being in different register classes or +/// because the coalescer was overly conservative. unsigned RALinScan::attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg) { - if ((cur.preference && cur.preference == Reg) || !cur.containsOneValue()) + unsigned Preference = vrm_->getRegAllocPref(cur.reg); + if ((Preference && Preference == Reg) || !cur.containsOneValue()) return Reg; - VNInfo *vni = cur.begin()->valno; - if (!vni->def || vni->def == ~1U || vni->def == ~0U) + // We cannot handle complicated live ranges. Simple linear stuff only. + if (cur.ranges.size() != 1) return Reg; - MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def); - unsigned SrcReg, DstReg, SrcSubReg, DstSubReg, PhysReg; - if (!CopyMI || - !tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubReg, DstSubReg)) + + const LiveRange &range = cur.ranges.front(); + + VNInfo *vni = range.valno; + if (vni->isUnused() || !vni->def.isValid()) return Reg; - PhysReg = SrcReg; - if (TargetRegisterInfo::isVirtualRegister(SrcReg)) { - if (!vrm_->isAssignedReg(SrcReg)) + + unsigned CandReg; + { + MachineInstr *CopyMI; + if ((CopyMI = li_->getInstructionFromIndex(vni->def)) && CopyMI->isCopy()) + // Defined by a copy, try to extend SrcReg forward + CandReg = CopyMI->getOperand(1).getReg(); + else if (TrivCoalesceEnds && + (CopyMI = li_->getInstructionFromIndex(range.end.getBaseIndex())) && + CopyMI->isCopy() && cur.reg == CopyMI->getOperand(1).getReg()) + // Only used by a copy, try to extend DstReg backwards + CandReg = CopyMI->getOperand(0).getReg(); + else + return Reg; + + // If the target of the copy is a sub-register then don't coalesce. + if(CopyMI->getOperand(0).getSubReg()) return Reg; - PhysReg = vrm_->getPhys(SrcReg); } - if (Reg == PhysReg) + + if (TargetRegisterInfo::isVirtualRegister(CandReg)) { + if (!vrm_->isAssignedReg(CandReg)) + return Reg; + CandReg = vrm_->getPhys(CandReg); + } + if (Reg == CandReg) return Reg; const TargetRegisterClass *RC = mri_->getRegClass(cur.reg); - if (!RC->contains(PhysReg)) + if (!RC->contains(CandReg)) return Reg; - // Try to coalesce. - if (!li_->conflictsWithPhysRegDef(cur, *vrm_, PhysReg)) { - DOUT << "Coalescing: " << cur << " -> " << tri_->getName(PhysReg) - << '\n'; - vrm_->clearVirt(cur.reg); - vrm_->assignVirt2Phys(cur.reg, PhysReg); - - // Remove unnecessary kills since a copy does not clobber the register. - if (li_->hasInterval(SrcReg)) { - LiveInterval &SrcLI = li_->getInterval(SrcReg); - for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(cur.reg), - E = mri_->reg_end(); I != E; ++I) { - MachineOperand &O = I.getOperand(); - if (!O.isUse() || !O.isKill()) - continue; - MachineInstr *MI = &*I; - if (SrcLI.liveAt(li_->getDefIndex(li_->getInstructionIndex(MI)))) - O.setIsKill(false); - } - } + if (li_->conflictsWithPhysReg(cur, *vrm_, CandReg)) + return Reg; - ++NumCoalesce; - return SrcReg; - } + // Try to coalesce. + DEBUG(dbgs() << "Coalescing: " << cur << " -> " << tri_->getName(CandReg) + << '\n'); + vrm_->clearVirt(cur.reg); + vrm_->assignVirt2Phys(cur.reg, CandReg); - return Reg; + ++NumCoalesce; + return CandReg; } bool RALinScan::runOnMachineFunction(MachineFunction &fn) { @@ -411,9 +510,10 @@ bool RALinScan::runOnMachineFunction(MachineFunction &fn) { tri_ = tm_->getRegisterInfo(); tii_ = tm_->getInstrInfo(); allocatableRegs_ = tri_->getAllocatableSet(fn); + reservedRegs_ = tri_->getReservedRegs(fn); li_ = &getAnalysis(); - ls_ = &getAnalysis(); loopInfo = &getAnalysis(); + RegClassInfo.runOnMachineFunction(fn); // We don't run the coalescer here because we have no reason to // interact with it. If the coalescer requires interaction, it @@ -429,11 +529,9 @@ bool RALinScan::runOnMachineFunction(MachineFunction &fn) { vrm_ = &getAnalysis(); if (!rewriter_.get()) rewriter_.reset(createVirtRegRewriter()); - - if (NewSpillFramework) { - spiller_.reset(createSpiller(mf_, li_, ls_, vrm_)); - } - + + spiller_.reset(createSpiller(*this, *mf_, *vrm_)); + initIntervalSets(); linearScan(); @@ -441,6 +539,9 @@ bool RALinScan::runOnMachineFunction(MachineFunction &fn) { // Rewrite spill code and update the PhysRegsUsed set. rewriter_->runOnMachineFunction(*mf_, *vrm_, li_); + // Write out new DBG_VALUE instructions. + getAnalysis().emitDebugValues(vrm_); + assert(unhandled_.empty() && "Unhandled live intervals remain!"); finalizeRegUses(); @@ -469,50 +570,60 @@ void RALinScan::initIntervalSets() for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) { if (TargetRegisterInfo::isPhysicalRegister(i->second->reg)) { - mri_->setPhysRegUsed(i->second->reg); - fixed_.push_back(std::make_pair(i->second, i->second->begin())); - } else - unhandled_.push(i->second); + if (!i->second->empty() && allocatableRegs_.test(i->second->reg)) { + mri_->setPhysRegUsed(i->second->reg); + fixed_.push_back(std::make_pair(i->second, i->second->begin())); + } + } else { + if (i->second->empty()) { + assignRegOrStackSlotAtInterval(i->second); + } + else + unhandled_.push(i->second); + } } } -void RALinScan::linearScan() -{ +void RALinScan::linearScan() { // linear scan algorithm - DOUT << "********** LINEAR SCAN **********\n"; - DOUT << "********** Function: " << mf_->getFunction()->getName() << '\n'; - - DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end())); + DEBUG({ + dbgs() << "********** LINEAR SCAN **********\n" + << "********** Function: " + << mf_->getFunction()->getName() << '\n'; + printIntervals("fixed", fixed_.begin(), fixed_.end()); + }); while (!unhandled_.empty()) { // pick the interval with the earliest start point LiveInterval* cur = unhandled_.top(); unhandled_.pop(); ++NumIters; - DOUT << "\n*** CURRENT ***: " << *cur << '\n'; + DEBUG(dbgs() << "\n*** CURRENT ***: " << *cur << '\n'); - if (!cur->empty()) { - processActiveIntervals(cur->beginNumber()); - processInactiveIntervals(cur->beginNumber()); + assert(!cur->empty() && "Empty interval in unhandled set."); - assert(TargetRegisterInfo::isVirtualRegister(cur->reg) && - "Can only allocate virtual registers!"); - } + processActiveIntervals(cur->beginIndex()); + processInactiveIntervals(cur->beginIndex()); + + assert(TargetRegisterInfo::isVirtualRegister(cur->reg) && + "Can only allocate virtual registers!"); // Allocating a virtual register. try to find a free // physical register or spill an interval (possibly this one) in order to // assign it one. assignRegOrStackSlotAtInterval(cur); - DEBUG(printIntervals("active", active_.begin(), active_.end())); - DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end())); + DEBUG({ + printIntervals("active", active_.begin(), active_.end()); + printIntervals("inactive", inactive_.begin(), inactive_.end()); + }); } // Expire any remaining active intervals while (!active_.empty()) { IntervalPtr &IP = active_.back(); unsigned reg = IP.first->reg; - DOUT << "\tinterval " << *IP.first << " expired\n"; + DEBUG(dbgs() << "\tinterval " << *IP.first << " expired\n"); assert(TargetRegisterInfo::isVirtualRegister(reg) && "Can only allocate virtual registers!"); reg = vrm_->getPhys(reg); @@ -521,9 +632,11 @@ void RALinScan::linearScan() } // Expire any remaining inactive intervals - DEBUG(for (IntervalPtrs::reverse_iterator - i = inactive_.rbegin(); i != inactive_.rend(); ++i) - DOUT << "\tinterval " << *i->first << " expired\n"); + DEBUG({ + for (IntervalPtrs::reverse_iterator + i = inactive_.rbegin(); i != inactive_.rend(); ++i) + dbgs() << "\tinterval " << *i->first << " expired\n"; + }); inactive_.clear(); // Add live-ins to every BB except for entry. Also perform trivial coalescing. @@ -543,50 +656,34 @@ void RALinScan::linearScan() if (!isPhys && vrm_->getPreSplitReg(cur.reg)) continue; - // A register defined by an implicit_def can be liveout the def BB and livein - // to a use BB. Add it to the livein set of the use BB's. - if (!isPhys && cur.empty()) { - if (MachineInstr *DefMI = mri_->getVRegDef(cur.reg)) { - assert(DefMI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF); - MachineBasicBlock *DefMBB = DefMI->getParent(); - SmallPtrSet Seen; - Seen.insert(DefMBB); - for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(cur.reg), - re = mri_->reg_end(); ri != re; ++ri) { - MachineInstr *UseMI = &*ri; - MachineBasicBlock *UseMBB = UseMI->getParent(); - if (Seen.insert(UseMBB)) - UseMBB->addLiveIn(Reg); - } - } - } for (LiveInterval::Ranges::const_iterator I = cur.begin(), E = cur.end(); I != E; ++I) { const LiveRange &LR = *I; if (li_->findLiveInMBBs(LR.start, LR.end, LiveInMBBs)) { for (unsigned i = 0, e = LiveInMBBs.size(); i != e; ++i) - if (LiveInMBBs[i] != EntryMBB) + if (LiveInMBBs[i] != EntryMBB) { + assert(TargetRegisterInfo::isPhysicalRegister(Reg) && + "Adding a virtual register to livein set?"); LiveInMBBs[i]->addLiveIn(Reg); + } LiveInMBBs.clear(); } } } - DOUT << *vrm_; + DEBUG(dbgs() << *vrm_); // Look for physical registers that end up not being allocated even though // register allocator had to spill other registers in its register class. - if (ls_->getNumIntervals() == 0) - return; - if (!vrm_->FindUnusedRegisters(tri_, li_)) + if (!vrm_->FindUnusedRegisters(li_)) return; } /// processActiveIntervals - expire old intervals and move non-overlapping ones /// to the inactive list. -void RALinScan::processActiveIntervals(unsigned CurPoint) +void RALinScan::processActiveIntervals(SlotIndex CurPoint) { - DOUT << "\tprocessing active intervals:\n"; + DEBUG(dbgs() << "\tprocessing active intervals:\n"); for (unsigned i = 0, e = active_.size(); i != e; ++i) { LiveInterval *Interval = active_[i].first; @@ -596,7 +693,7 @@ void RALinScan::processActiveIntervals(unsigned CurPoint) IntervalPos = Interval->advanceTo(IntervalPos, CurPoint); if (IntervalPos == Interval->end()) { // Remove expired intervals. - DOUT << "\t\tinterval " << *Interval << " expired\n"; + DEBUG(dbgs() << "\t\tinterval " << *Interval << " expired\n"); assert(TargetRegisterInfo::isVirtualRegister(reg) && "Can only allocate virtual registers!"); reg = vrm_->getPhys(reg); @@ -609,7 +706,7 @@ void RALinScan::processActiveIntervals(unsigned CurPoint) } else if (IntervalPos->start > CurPoint) { // Move inactive intervals to inactive list. - DOUT << "\t\tinterval " << *Interval << " inactive\n"; + DEBUG(dbgs() << "\t\tinterval " << *Interval << " inactive\n"); assert(TargetRegisterInfo::isVirtualRegister(reg) && "Can only allocate virtual registers!"); reg = vrm_->getPhys(reg); @@ -630,9 +727,9 @@ void RALinScan::processActiveIntervals(unsigned CurPoint) /// processInactiveIntervals - expire old intervals and move overlapping /// ones to the active list. -void RALinScan::processInactiveIntervals(unsigned CurPoint) +void RALinScan::processInactiveIntervals(SlotIndex CurPoint) { - DOUT << "\tprocessing inactive intervals:\n"; + DEBUG(dbgs() << "\tprocessing inactive intervals:\n"); for (unsigned i = 0, e = inactive_.size(); i != e; ++i) { LiveInterval *Interval = inactive_[i].first; @@ -642,7 +739,7 @@ void RALinScan::processInactiveIntervals(unsigned CurPoint) IntervalPos = Interval->advanceTo(IntervalPos, CurPoint); if (IntervalPos == Interval->end()) { // remove expired intervals. - DOUT << "\t\tinterval " << *Interval << " expired\n"; + DEBUG(dbgs() << "\t\tinterval " << *Interval << " expired\n"); // Pop off the end of the list. inactive_[i] = inactive_.back(); @@ -650,7 +747,7 @@ void RALinScan::processInactiveIntervals(unsigned CurPoint) --i; --e; } else if (IntervalPos->start <= CurPoint) { // move re-activated intervals in active list - DOUT << "\t\tinterval " << *Interval << " active\n"; + DEBUG(dbgs() << "\t\tinterval " << *Interval << " active\n"); assert(TargetRegisterInfo::isVirtualRegister(reg) && "Can only allocate virtual registers!"); reg = vrm_->getPhys(reg); @@ -693,7 +790,7 @@ void RALinScan::updateSpillWeights(std::vector &Weights, // register class we are trying to allocate. Then add the weight to all // sub-registers of the super-register even if they are not aliases. // e.g. allocating for GR32, bh is not used, updating bl spill weight. - // bl should get the same spill weight otherwise it will be choosen + // bl should get the same spill weight otherwise it will be chosen // as a spill candidate since spilling bh doesn't make ebx available. for (unsigned i = 0, e = Supers.size(); i != e; ++i) { for (const unsigned *sr = tri_->getSubRegisters(Supers[i]); *sr; ++sr) @@ -711,7 +808,8 @@ FindIntervalInVector(RALinScan::IntervalPtrs &IP, LiveInterval *LI) { return IP.end(); } -static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V, unsigned Point){ +static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V, + SlotIndex Point){ for (unsigned i = 0, e = V.size(); i != e; ++i) { RALinScan::IntervalPtr &IP = V[i]; LiveInterval::iterator I = std::upper_bound(IP.first->begin(), @@ -721,42 +819,19 @@ static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V, unsigned Point){ } } -/// addStackInterval - Create a LiveInterval for stack if the specified live -/// interval has been spilled. -static void addStackInterval(LiveInterval *cur, LiveStacks *ls_, - LiveIntervals *li_, - MachineRegisterInfo* mri_, VirtRegMap &vrm_) { - int SS = vrm_.getStackSlot(cur->reg); - if (SS == VirtRegMap::NO_STACK_SLOT) - return; - - const TargetRegisterClass *RC = mri_->getRegClass(cur->reg); - LiveInterval &SI = ls_->getOrCreateInterval(SS, RC); - - VNInfo *VNI; - if (SI.hasAtLeastOneValue()) - VNI = SI.getValNumInfo(0); - else - VNI = SI.getNextValue(~0U, 0, ls_->getVNInfoAllocator()); - - LiveInterval &RI = li_->getInterval(cur->reg); - // FIXME: This may be overly conservative. - SI.MergeRangesInAsValue(RI, VNI); -} - /// getConflictWeight - Return the number of conflicts between cur /// live interval and defs and uses of Reg weighted by loop depthes. static float getConflictWeight(LiveInterval *cur, unsigned Reg, LiveIntervals *li_, MachineRegisterInfo *mri_, - const MachineLoopInfo *loopInfo) { + MachineLoopInfo *loopInfo) { float Conflicts = 0; for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(Reg), E = mri_->reg_end(); I != E; ++I) { MachineInstr *MI = &*I; if (cur->liveAt(li_->getInstructionIndex(MI))) { unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent()); - Conflicts += powf(10.0f, (float)loopDepth); + Conflicts += std::pow(10.0f, (float)loopDepth); } } return Conflicts; @@ -776,11 +851,13 @@ void RALinScan::findIntervalsToSpill(LiveInterval *cur, float Conflicts[3] = { 0.0f, 0.0f, 0.0f }; SmallVector SLIs[3]; - DOUT << "\tConsidering " << NumCands << " candidates: "; - DEBUG(for (unsigned i = 0; i != NumCands; ++i) - DOUT << tri_->getName(Candidates[i].first) << " "; - DOUT << "\n";); - + DEBUG({ + dbgs() << "\tConsidering " << NumCands << " candidates: "; + for (unsigned i = 0; i != NumCands; ++i) + dbgs() << tri_->getName(Candidates[i].first) << " "; + dbgs() << "\n"; + }); + // Calculate the number of conflicts of each candidate. for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) { unsigned Reg = i->first->reg; @@ -828,9 +905,15 @@ void RALinScan::findIntervalsToSpill(LiveInterval *cur, namespace { struct WeightCompare { + private: + const RALinScan &Allocator; + + public: + WeightCompare(const RALinScan &Alloc) : Allocator(Alloc) {} + typedef std::pair RegWeightPair; bool operator()(const RegWeightPair &LHS, const RegWeightPair &RHS) const { - return LHS.second < RHS.second; + return LHS.second < RHS.second && !Allocator.isRecentlyUsed(LHS.first); } }; } @@ -853,13 +936,9 @@ LiveInterval *RALinScan::hasNextReloadInterval(LiveInterval *cur) { } void RALinScan::DowngradeRegister(LiveInterval *li, unsigned Reg) { - bool isNew = DowngradedRegs.insert(Reg); - isNew = isNew; // Silence compiler warning. - assert(isNew && "Multiple reloads holding the same register?"); - DowngradeMap.insert(std::make_pair(li->reg, Reg)); - for (const unsigned *AS = tri_->getAliasSet(Reg); *AS; ++AS) { - isNew = DowngradedRegs.insert(*AS); - isNew = isNew; // Silence compiler warning. + for (const unsigned *AS = tri_->getOverlaps(Reg); *AS; ++AS) { + bool isNew = DowngradedRegs.insert(*AS); + (void)isNew; // Silence compiler warning. assert(isNew && "Multiple reloads holding the same register?"); DowngradeMap.insert(std::make_pair(li->reg, *AS)); } @@ -877,24 +956,24 @@ void RALinScan::UpgradeRegister(unsigned Reg) { namespace { struct LISorter { bool operator()(LiveInterval* A, LiveInterval* B) { - return A->beginNumber() < B->beginNumber(); + return A->beginIndex() < B->beginIndex(); } }; } /// assignRegOrStackSlotAtInterval - assign a register if one is available, or /// spill. -void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) -{ - DOUT << "\tallocating current interval: "; +void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) { + const TargetRegisterClass *RC = mri_->getRegClass(cur->reg); + DEBUG(dbgs() << "\tallocating current interval from " + << RC->getName() << ": "); // This is an implicitly defined live interval, just assign any register. - const TargetRegisterClass *RC = mri_->getRegClass(cur->reg); if (cur->empty()) { - unsigned physReg = cur->preference; + unsigned physReg = vrm_->getRegAllocPref(cur->reg); if (!physReg) - physReg = *RC->allocation_order_begin(*mf_); - DOUT << tri_->getName(physReg) << '\n'; + physReg = getFirstNonReservedPhysReg(RC); + DEBUG(dbgs() << tri_->getName(physReg) << '\n'); // Note the register is not really in use. vrm_->assignVirt2Phys(cur->reg, physReg); return; @@ -903,7 +982,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) backUpRegUses(); std::vector > SpillWeightsToAdd; - unsigned StartPosition = cur->beginNumber(); + SlotIndex StartPosition = cur->beginIndex(); const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC); // If start of this live interval is defined by a move instruction and its @@ -911,13 +990,14 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) // register class, then we should try to assign it the same register. // This can happen when the move is from a larger register class to a smaller // one, e.g. X86::mov32to32_. These move instructions are not coalescable. - if (!cur->preference && cur->hasAtLeastOneValue()) { + if (!vrm_->getRegAllocPref(cur->reg) && cur->hasAtLeastOneValue()) { VNInfo *vni = cur->begin()->valno; - if (vni->def && vni->def != ~1U && vni->def != ~0U) { + if (!vni->isUnused() && vni->def.isValid()) { MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def); - unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; - if (CopyMI && - tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubReg, DstSubReg)) { + if (CopyMI && CopyMI->isCopy()) { + unsigned DstSubReg = CopyMI->getOperand(0).getSubReg(); + unsigned SrcReg = CopyMI->getOperand(1).getReg(); + unsigned SrcSubReg = CopyMI->getOperand(1).getSubReg(); unsigned Reg = 0; if (TargetRegisterInfo::isPhysicalRegister(SrcReg)) Reg = SrcReg; @@ -929,7 +1009,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) if (DstSubReg) Reg = tri_->getMatchingSuperReg(Reg, DstSubReg, RC); if (Reg && allocatableRegs_[Reg] && RC->contains(Reg)) - cur->preference = Reg; + mri_->setRegAllocationHint(cur->reg, 0, Reg); } } } @@ -943,7 +1023,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Can only allocate virtual registers!"); const TargetRegisterClass *RegRC = mri_->getRegClass(Reg); - // If this is not in a related reg class to the register we're allocating, + // If this is not in a related reg class to the register we're allocating, // don't check it. if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader && cur->overlapsFrom(*i->first, i->second-1)) { @@ -952,7 +1032,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) SpillWeightsToAdd.push_back(std::make_pair(Reg, i->first->weight)); } } - + // Speculatively check to see if we can get a register right now. If not, // we know we won't be able to by adding more constraints. If so, we can // check to see if it is valid. Doing an exhaustive search of the fixed_ list @@ -967,7 +1047,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) SmallSet RegAliases; for (const unsigned *AS = tri_->getAliasSet(physReg); *AS; ++AS) RegAliases.insert(*AS); - + bool ConflictsWithFixed = false; for (unsigned i = 0, e = fixed_.size(); i != e; ++i) { IntervalPtr &IP = fixed_[i]; @@ -975,7 +1055,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) // Okay, this reg is on the fixed list. Check to see if we actually // conflict. LiveInterval *I = IP.first; - if (I->endNumber() > StartPosition) { + if (I->endIndex() > StartPosition) { LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition); IP.second = II; if (II != I->begin() && II->start > StartPosition) @@ -987,7 +1067,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) } } } - + // Okay, the register picked by our speculative getFreePhysReg call turned // out to be in use. Actually add all of the conflicting fixed registers to // regUse_ so we can do an accurate query. @@ -999,8 +1079,8 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) LiveInterval *I = IP.first; const TargetRegisterClass *RegRC = OneClassForEachPhysReg[I->reg]; - if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader && - I->endNumber() > StartPosition) { + if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader && + I->endIndex() > StartPosition) { LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition); IP.second = II; if (II != I->begin() && II->start > StartPosition) @@ -1018,39 +1098,46 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) physReg = getFreePhysReg(cur); } } - + // Restore the physical register tracker, removing information about the // future. restoreRegUses(); - + // If we find a free register, we are done: assign this virtual to // the free physical register and add this interval to the active // list. if (physReg) { - DOUT << tri_->getName(physReg) << '\n'; + DEBUG(dbgs() << tri_->getName(physReg) << '\n'); + assert(RC->contains(physReg) && "Invalid candidate"); vrm_->assignVirt2Phys(cur->reg, physReg); addRegUse(physReg); active_.push_back(std::make_pair(cur, cur->begin())); handled_.push_back(cur); + // Remember physReg for avoiding a write-after-write hazard in the next + // instruction. + if (AvoidWAWHazard && + tri_->avoidWriteAfterWrite(mri_->getRegClass(cur->reg))) + avoidWAW_ = physReg; + // "Upgrade" the physical register since it has been allocated. UpgradeRegister(physReg); if (LiveInterval *NextReloadLI = hasNextReloadInterval(cur)) { // "Downgrade" physReg to try to keep physReg from being allocated until - // the next reload from the same SS is allocated. - NextReloadLI->preference = physReg; + // the next reload from the same SS is allocated. + mri_->setRegAllocationHint(NextReloadLI->reg, 0, physReg); DowngradeRegister(cur, physReg); } return; } - DOUT << "no free registers\n"; + DEBUG(dbgs() << "no free registers\n"); // Compile the spill weights into an array that is better for scanning. std::vector SpillWeights(tri_->getNumRegs(), 0.0f); for (std::vector >::iterator I = SpillWeightsToAdd.begin(), E = SpillWeightsToAdd.end(); I != E; ++I) updateSpillWeights(SpillWeights, I->first, I->second, RC); - + // for each interval in active, update spill weights. for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end(); i != e; ++i) { @@ -1060,30 +1147,30 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) reg = vrm_->getPhys(reg); updateSpillWeights(SpillWeights, reg, i->first->weight, RC); } - - DOUT << "\tassigning stack slot at interval "<< *cur << ":\n"; + + DEBUG(dbgs() << "\tassigning stack slot at interval "<< *cur << ":\n"); // Find a register to spill. float minWeight = HUGE_VALF; - unsigned minReg = 0; /*cur->preference*/; // Try the pref register first. + unsigned minReg = 0; bool Found = false; std::vector > RegsWeights; + ArrayRef Order = RegClassInfo.getOrder(RC); if (!minReg || SpillWeights[minReg] == HUGE_VALF) - for (TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_), - e = RC->allocation_order_end(*mf_); i != e; ++i) { - unsigned reg = *i; + for (unsigned i = 0; i != Order.size(); ++i) { + unsigned reg = Order[i]; float regWeight = SpillWeights[reg]; - if (minWeight > regWeight) + // Skip recently allocated registers and reserved registers. + if (minWeight > regWeight && !isRecentlyUsed(reg)) Found = true; RegsWeights.push_back(std::make_pair(reg, regWeight)); } - + // If we didn't find a register that is spillable, try aliases? if (!Found) { - for (TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_), - e = RC->allocation_order_end(*mf_); i != e; ++i) { - unsigned reg = *i; + for (unsigned i = 0; i != Order.size(); ++i) { + unsigned reg = Order[i]; // No need to worry about if the alias register size < regsize of RC. // We are going to spill all registers that alias it anyway. for (const unsigned* as = tri_->getAliasSet(reg); *as; ++as) @@ -1092,12 +1179,12 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) } // Sort all potential spill candidates by weight. - std::sort(RegsWeights.begin(), RegsWeights.end(), WeightCompare()); + std::sort(RegsWeights.begin(), RegsWeights.end(), WeightCompare(*this)); minReg = RegsWeights[0].first; minWeight = RegsWeights[0].second; if (minWeight == HUGE_VALF) { // All registers must have inf weight. Just grab one! - minReg = BestPhysReg ? BestPhysReg : *RC->allocation_order_begin(*mf_); + minReg = BestPhysReg ? BestPhysReg : getFirstNonReservedPhysReg(RC); if (cur->weight == HUGE_VALF || li_->getApproximateInstructionCount(*cur) == 0) { // Spill a physical register around defs and uses. @@ -1114,8 +1201,8 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) DowngradedRegs.clear(); assignRegOrStackSlotAtInterval(cur); } else { - cerr << "Ran out of registers during register allocation!\n"; - exit(1); + assert(false && "Ran out of registers during register allocation!"); + report_fatal_error("Ran out of registers during register allocation!"); } return; } @@ -1129,27 +1216,24 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) --LastCandidate; } - DOUT << "\t\tregister(s) with min weight(s): "; - DEBUG(for (unsigned i = 0; i != LastCandidate; ++i) - DOUT << tri_->getName(RegsWeights[i].first) - << " (" << RegsWeights[i].second << ")\n"); + DEBUG({ + dbgs() << "\t\tregister(s) with min weight(s): "; + + for (unsigned i = 0; i != LastCandidate; ++i) + dbgs() << tri_->getName(RegsWeights[i].first) + << " (" << RegsWeights[i].second << ")\n"; + }); // If the current has the minimum weight, we need to spill it and // add any added intervals back to unhandled, and restart // linearscan. if (cur->weight != HUGE_VALF && cur->weight <= minWeight) { - DOUT << "\t\t\tspilling(c): " << *cur << '\n'; - SmallVector spillIs; - std::vector added; - - if (!NewSpillFramework) { - added = li_->addIntervalsForSpills(*cur, spillIs, loopInfo, *vrm_); - } else { - added = spiller_->spill(cur); - } + DEBUG(dbgs() << "\t\t\tspilling(c): " << *cur << '\n'); + SmallVector added; + LiveRangeEdit LRE(*cur, added); + spiller_->spill(LRE); std::sort(added.begin(), added.end(), LISorter()); - addStackInterval(cur, ls_, li_, mri_, *vrm_); if (added.empty()) return; // Early exit if all spills were folded. @@ -1166,14 +1250,14 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) LiveInterval *ReloadLi = added[i]; if (ReloadLi->weight == HUGE_VALF && li_->getApproximateInstructionCount(*ReloadLi) == 0) { - unsigned ReloadIdx = ReloadLi->beginNumber(); + SlotIndex ReloadIdx = ReloadLi->beginIndex(); MachineBasicBlock *ReloadMBB = li_->getMBBFromIndex(ReloadIdx); int ReloadSS = vrm_->getStackSlot(ReloadLi->reg); if (LastReloadMBB == ReloadMBB && LastReloadSS == ReloadSS) { // Last reload of same SS is in the same MBB. We want to try to // allocate both reloads the same register and make sure the reg // isn't clobbered in between if at all possible. - assert(LastReload->beginNumber() < ReloadIdx); + assert(LastReload->beginIndex() < ReloadIdx); NextReloadMap.insert(std::make_pair(LastReload->reg, ReloadLi->reg)); } LastReloadMBB = ReloadMBB; @@ -1208,42 +1292,34 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) // The earliest start of a Spilled interval indicates up to where // in handled we need to roll back - - LiveInterval *earliestStartInterval = cur; + assert(!spillIs.empty() && "No spill intervals?"); + SlotIndex earliestStart = spillIs[0]->beginIndex(); // Spill live intervals of virtual regs mapped to the physical register we // want to clear (and its aliases). We only spill those that overlap with the // current interval as the rest do not affect its allocation. we also keep // track of the earliest start of all spilled live intervals since this will // mark our rollback point. - std::vector added; + SmallVector added; while (!spillIs.empty()) { - bool epicFail = false; LiveInterval *sli = spillIs.back(); spillIs.pop_back(); - DOUT << "\t\t\tspilling(a): " << *sli << '\n'; - earliestStartInterval = - (earliestStartInterval->beginNumber() < sli->beginNumber()) ? - earliestStartInterval : sli; - - std::vector newIs; - if (!NewSpillFramework) { - newIs = li_->addIntervalsForSpills(*sli, spillIs, loopInfo, *vrm_); - } else { - newIs = spiller_->spill(sli); - } - addStackInterval(sli, ls_, li_, mri_, *vrm_); - std::copy(newIs.begin(), newIs.end(), std::back_inserter(added)); + DEBUG(dbgs() << "\t\t\tspilling(a): " << *sli << '\n'); + if (sli->beginIndex() < earliestStart) + earliestStart = sli->beginIndex(); + LiveRangeEdit LRE(*sli, added, 0, &spillIs); + spiller_->spill(LRE); spilled.insert(sli->reg); - - if (epicFail) { - //abort(); - } } - unsigned earliestStart = earliestStartInterval->beginNumber(); + // Include any added intervals in earliestStart. + for (unsigned i = 0, e = added.size(); i != e; ++i) { + SlotIndex SI = added[i]->beginIndex(); + if (SI < earliestStart) + earliestStart = SI; + } - DOUT << "\t\trolling back to: " << earliestStart << '\n'; + DEBUG(dbgs() << "\t\trolling back to: " << earliestStart << '\n'); // Scan handled in reverse order up to the earliest start of a // spilled live interval and undo each one, restoring the state of @@ -1251,9 +1327,9 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) while (!handled_.empty()) { LiveInterval* i = handled_.back(); // If this interval starts before t we are done. - if (i->beginNumber() < earliestStart) + if (!i->empty() && i->beginIndex() < earliestStart) break; - DOUT << "\t\t\tundo changes for: " << *i << '\n'; + DEBUG(dbgs() << "\t\t\tundo changes for: " << *i << '\n'); handled_.pop_back(); // When undoing a live interval allocation we must know if it is active or @@ -1284,7 +1360,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) // It interval has a preference, it must be defined by a copy. Clear the // preference now since the source interval allocation may have been // undone as well. - i->preference = 0; + mri_->setRegAllocationHint(i->reg, 0, 0); else { UpgradeRegister(ii->second); } @@ -1302,8 +1378,8 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) for (unsigned i = 0, e = handled_.size(); i != e; ++i) { LiveInterval *HI = handled_[i]; if (!HI->expiredAt(earliestStart) && - HI->expiredAt(cur->beginNumber())) { - DOUT << "\t\t\tundo changes for: " << *HI << '\n'; + HI->expiredAt(cur->beginIndex())) { + DEBUG(dbgs() << "\t\t\tundo changes for: " << *HI << '\n'); active_.push_back(std::make_pair(HI, HI->begin())); assert(!TargetRegisterInfo::isPhysicalRegister(HI->reg)); addRegUse(vrm_->getPhys(HI->reg)); @@ -1322,14 +1398,14 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) LiveInterval *ReloadLi = added[i]; if (ReloadLi->weight == HUGE_VALF && li_->getApproximateInstructionCount(*ReloadLi) == 0) { - unsigned ReloadIdx = ReloadLi->beginNumber(); + SlotIndex ReloadIdx = ReloadLi->beginIndex(); MachineBasicBlock *ReloadMBB = li_->getMBBFromIndex(ReloadIdx); int ReloadSS = vrm_->getStackSlot(ReloadLi->reg); if (LastReloadMBB == ReloadMBB && LastReloadSS == ReloadSS) { // Last reload of same SS is in the same MBB. We want to try to // allocate both reloads the same register and make sure the reg // isn't clobbered in between if at all possible. - assert(LastReload->beginNumber() < ReloadIdx); + assert(LastReload->beginIndex() < ReloadIdx); NextReloadMap.insert(std::make_pair(LastReload->reg, ReloadLi->reg)); } LastReloadMBB = ReloadMBB; @@ -1340,24 +1416,39 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) } } -unsigned RALinScan::getFreePhysReg(const TargetRegisterClass *RC, +unsigned RALinScan::getFreePhysReg(LiveInterval* cur, + const TargetRegisterClass *RC, unsigned MaxInactiveCount, SmallVector &inactiveCounts, bool SkipDGRegs) { unsigned FreeReg = 0; unsigned FreeRegInactiveCount = 0; - TargetRegisterClass::iterator I = RC->allocation_order_begin(*mf_); - TargetRegisterClass::iterator E = RC->allocation_order_end(*mf_); - assert(I != E && "No allocatable register in this register class!"); + std::pair Hint = mri_->getRegAllocationHint(cur->reg); + // Resolve second part of the hint (if possible) given the current allocation. + unsigned physReg = Hint.second; + if (TargetRegisterInfo::isVirtualRegister(physReg) && vrm_->hasPhys(physReg)) + physReg = vrm_->getPhys(physReg); + + ArrayRef Order; + if (Hint.first) + Order = tri_->getRawAllocationOrder(RC, Hint.first, physReg, *mf_); + else + Order = RegClassInfo.getOrder(RC); + + assert(!Order.empty() && "No allocatable register in this register class!"); // Scan for the first available register. - for (; I != E; ++I) { - unsigned Reg = *I; + for (unsigned i = 0; i != Order.size(); ++i) { + unsigned Reg = Order[i]; // Ignore "downgraded" registers. if (SkipDGRegs && DowngradedRegs.count(Reg)) continue; - if (isRegAvail(Reg)) { + // Skip reserved registers. + if (reservedRegs_.test(Reg)) + continue; + // Skip recently allocated registers. + if (isRegAvail(Reg) && (!SkipDGRegs || !isRecentlyUsed(Reg))) { FreeReg = Reg; if (FreeReg < inactiveCounts.size()) FreeRegInactiveCount = inactiveCounts[FreeReg]; @@ -1369,20 +1460,27 @@ unsigned RALinScan::getFreePhysReg(const TargetRegisterClass *RC, // If there are no free regs, or if this reg has the max inactive count, // return this register. - if (FreeReg == 0 || FreeRegInactiveCount == MaxInactiveCount) + if (FreeReg == 0 || FreeRegInactiveCount == MaxInactiveCount) { + // Remember what register we picked so we can skip it next time. + if (FreeReg != 0) recordRecentlyUsed(FreeReg); return FreeReg; - + } + // Continue scanning the registers, looking for the one with the highest // inactive count. Alkis found that this reduced register pressure very // slightly on X86 (in rev 1.94 of this file), though this should probably be // reevaluated now. - for (; I != E; ++I) { - unsigned Reg = *I; + for (unsigned i = 0; i != Order.size(); ++i) { + unsigned Reg = Order[i]; // Ignore "downgraded" registers. if (SkipDGRegs && DowngradedRegs.count(Reg)) continue; + // Skip reserved registers. + if (reservedRegs_.test(Reg)) + continue; if (isRegAvail(Reg) && Reg < inactiveCounts.size() && - FreeRegInactiveCount < inactiveCounts[Reg]) { + FreeRegInactiveCount < inactiveCounts[Reg] && + (!SkipDGRegs || !isRecentlyUsed(Reg))) { FreeReg = Reg; FreeRegInactiveCount = inactiveCounts[Reg]; if (FreeRegInactiveCount == MaxInactiveCount) @@ -1390,6 +1488,9 @@ unsigned RALinScan::getFreePhysReg(const TargetRegisterClass *RC, } } + // Remember what register we picked so we can skip it next time. + recordRecentlyUsed(FreeReg); + return FreeReg; } @@ -1398,17 +1499,17 @@ unsigned RALinScan::getFreePhysReg(const TargetRegisterClass *RC, unsigned RALinScan::getFreePhysReg(LiveInterval *cur) { SmallVector inactiveCounts; unsigned MaxInactiveCount = 0; - + const TargetRegisterClass *RC = mri_->getRegClass(cur->reg); const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC); - + for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end(); i != e; ++i) { unsigned reg = i->first->reg; assert(TargetRegisterInfo::isVirtualRegister(reg) && "Can only allocate virtual registers!"); - // If this is not in a related reg class to the register we're allocating, + // If this is not in a related reg class to the register we're allocating, // don't check it. const TargetRegisterClass *RegRC = mri_->getRegClass(reg); if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader) { @@ -1422,20 +1523,19 @@ unsigned RALinScan::getFreePhysReg(LiveInterval *cur) { // If copy coalescer has assigned a "preferred" register, check if it's // available first. - if (cur->preference) { - DOUT << "(preferred: " << tri_->getName(cur->preference) << ") "; - if (isRegAvail(cur->preference) && - RC->contains(cur->preference)) - return cur->preference; + unsigned Preference = vrm_->getRegAllocPref(cur->reg); + if (Preference) { + DEBUG(dbgs() << "(preferred: " << tri_->getName(Preference) << ") "); + if (isRegAvail(Preference) && + RC->contains(Preference)) + return Preference; } - if (!DowngradedRegs.empty()) { - unsigned FreeReg = getFreePhysReg(RC, MaxInactiveCount, inactiveCounts, - true); - if (FreeReg) - return FreeReg; - } - return getFreePhysReg(RC, MaxInactiveCount, inactiveCounts, false); + unsigned FreeReg = getFreePhysReg(cur, RC, MaxInactiveCount, inactiveCounts, + true); + if (FreeReg) + return FreeReg; + return getFreePhysReg(cur, RC, MaxInactiveCount, inactiveCounts, false); } FunctionPass* llvm::createLinearScanRegisterAllocator() {