X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegAllocLinearScan.cpp;h=41a42fd22d3bb92f3366eefcfd5a5d736f231cee;hb=1c7a848e5488c5b29cc80ccc07df006c5b524955;hp=c7383154841502fe9f4a7adff6662d4ea12b5442;hpb=c4f718a3a7990a13888836902ecac034a9d6a235;p=oota-llvm.git diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp index c7383154841..41a42fd22d3 100644 --- a/lib/CodeGen/RegAllocLinearScan.cpp +++ b/lib/CodeGen/RegAllocLinearScan.cpp @@ -12,8 +12,8 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "regalloc" -#include "PhysRegTracker.h" #include "VirtRegMap.h" +#include "VirtRegRewriter.h" #include "Spiller.h" #include "llvm/Function.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" @@ -40,6 +40,7 @@ #include #include #include + using namespace llvm; STATISTIC(NumIters , "Number of iterations performed"); @@ -57,6 +58,11 @@ PreSplitIntervals("pre-alloc-split", cl::desc("Pre-register allocation live interval splitting"), cl::init(false), cl::Hidden); +static cl::opt +NewSpillFramework("new-spill-framework", + cl::desc("New spilling framework"), + cl::init(false), cl::Hidden); + static RegisterRegAlloc linearscanRegAlloc("linearscan", "linear scan register allocator", createLinearScanRegisterAllocator); @@ -118,8 +124,16 @@ namespace { SmallVector, greater_ptr > IntervalHeap; IntervalHeap unhandled_; - std::auto_ptr prt_; + + /// regUse_ - Tracks register usage. + SmallVector regUse_; + SmallVector regUseBackUp_; + + /// vrm_ - Tracks register assignments. VirtRegMap* vrm_; + + std::auto_ptr rewriter_; + std::auto_ptr spiller_; public: @@ -202,13 +216,73 @@ namespace { unsigned attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg); /// - /// register handling helpers + /// Register usage / availability tracking helpers. + /// + + void initRegUses() { + regUse_.resize(tri_->getNumRegs(), 0); + regUseBackUp_.resize(tri_->getNumRegs(), 0); + } + + void finalizeRegUses() { +#ifndef NDEBUG + // Verify all the registers are "freed". + 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"; + Error = true; + } + } + if (Error) + abort(); +#endif + regUse_.clear(); + regUseBackUp_.clear(); + } + + void addRegUse(unsigned physReg) { + assert(TargetRegisterInfo::isPhysicalRegister(physReg) && + "should be physical register!"); + ++regUse_[physReg]; + for (const unsigned* as = tri_->getAliasSet(physReg); *as; ++as) + ++regUse_[*as]; + } + + void delRegUse(unsigned physReg) { + assert(TargetRegisterInfo::isPhysicalRegister(physReg) && + "should be physical register!"); + assert(regUse_[physReg] != 0); + --regUse_[physReg]; + for (const unsigned* as = tri_->getAliasSet(physReg); *as; ++as) { + assert(regUse_[*as] != 0); + --regUse_[*as]; + } + } + + bool isRegAvail(unsigned physReg) const { + assert(TargetRegisterInfo::isPhysicalRegister(physReg) && + "should be physical register!"); + return regUse_[physReg] == 0; + } + + void backUpRegUses() { + regUseBackUp_ = regUse_; + } + + void restoreRegUses() { + regUse_ = regUseBackUp_; + } + + /// + /// Register handling helpers. /// /// 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); @@ -279,38 +353,54 @@ void RALinScan::ComputeRelatedRegClasses() { /// 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) + if (!vni->def || vni->isUnused() || !vni->isDefAccurate()) return Reg; MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def); - unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; + unsigned SrcReg, DstReg, SrcSubReg, DstSubReg, PhysReg; if (!CopyMI || !tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubReg, DstSubReg)) return Reg; + PhysReg = SrcReg; if (TargetRegisterInfo::isVirtualRegister(SrcReg)) { if (!vrm_->isAssignedReg(SrcReg)) return Reg; - else - SrcReg = vrm_->getPhys(SrcReg); + PhysReg = vrm_->getPhys(SrcReg); } - if (Reg == SrcReg) + if (Reg == PhysReg) return Reg; const TargetRegisterClass *RC = mri_->getRegClass(cur.reg); - if (!RC->contains(SrcReg)) + if (!RC->contains(PhysReg)) return Reg; // Try to coalesce. - if (!li_->conflictsWithPhysRegDef(cur, *vrm_, SrcReg)) { - DOUT << "Coalescing: " << cur << " -> " << tri_->getName(SrcReg) + if (!li_->conflictsWithPhysRegDef(cur, *vrm_, PhysReg)) { + DOUT << "Coalescing: " << cur << " -> " << tri_->getName(PhysReg) << '\n'; vrm_->clearVirt(cur.reg); - vrm_->assignVirt2Phys(cur.reg, SrcReg); + 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); + } + } + ++NumCoalesce; - return SrcReg; + return PhysReg; } return Reg; @@ -335,19 +425,28 @@ bool RALinScan::runOnMachineFunction(MachineFunction &fn) { // If this is the first function compiled, compute the related reg classes. if (RelatedRegClasses.empty()) ComputeRelatedRegClasses(); - - if (!prt_.get()) prt_.reset(new PhysRegTracker(*tri_)); - vrm_ = &getAnalysis(); - if (!spiller_.get()) spiller_.reset(createSpiller()); + // Also resize register usage trackers. + initRegUses(); + + vrm_ = &getAnalysis(); + if (!rewriter_.get()) rewriter_.reset(createVirtRegRewriter()); + + if (NewSpillFramework) { + spiller_.reset(createSpiller(mf_, li_, ls_, vrm_)); + } + initIntervalSets(); linearScan(); // Rewrite spill code and update the PhysRegsUsed set. - spiller_->runOnMachineFunction(*mf_, *vrm_); + rewriter_->runOnMachineFunction(*mf_, *vrm_, li_); assert(unhandled_.empty() && "Unhandled live intervals remain!"); + + finalizeRegUses(); + fixed_.clear(); active_.clear(); inactive_.clear(); @@ -355,6 +454,7 @@ bool RALinScan::runOnMachineFunction(MachineFunction &fn) { NextReloadMap.clear(); DowngradedRegs.clear(); DowngradeMap.clear(); + spiller_.reset(0); return true; } @@ -410,7 +510,7 @@ void RALinScan::linearScan() DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end())); } - // expire any remaining active intervals + // Expire any remaining active intervals while (!active_.empty()) { IntervalPtr &IP = active_.back(); unsigned reg = IP.first->reg; @@ -418,11 +518,11 @@ void RALinScan::linearScan() assert(TargetRegisterInfo::isVirtualRegister(reg) && "Can only allocate virtual registers!"); reg = vrm_->getPhys(reg); - prt_->delRegUse(reg); + delRegUse(reg); active_.pop_back(); } - // expire any remaining inactive intervals + // Expire any remaining inactive intervals DEBUG(for (IntervalPtrs::reverse_iterator i = inactive_.rbegin(); i != inactive_.rend(); ++i) DOUT << "\tinterval " << *i->first << " expired\n"); @@ -444,19 +544,50 @@ void RALinScan::linearScan() // Ignore splited live intervals. 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)) { + assert(TargetRegisterInfo::isPhysicalRegister(Reg) && + "Adding a virtual register to livein set?"); + 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_; + + // 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(li_)) + return; } /// processActiveIntervals - expire old intervals and move non-overlapping ones @@ -477,7 +608,7 @@ void RALinScan::processActiveIntervals(unsigned CurPoint) assert(TargetRegisterInfo::isVirtualRegister(reg) && "Can only allocate virtual registers!"); reg = vrm_->getPhys(reg); - prt_->delRegUse(reg); + delRegUse(reg); // Pop off the end of the list. active_[i] = active_.back(); @@ -490,7 +621,7 @@ void RALinScan::processActiveIntervals(unsigned CurPoint) assert(TargetRegisterInfo::isVirtualRegister(reg) && "Can only allocate virtual registers!"); reg = vrm_->getPhys(reg); - prt_->delRegUse(reg); + delRegUse(reg); // add to inactive. inactive_.push_back(std::make_pair(Interval, IntervalPos)); @@ -531,7 +662,7 @@ void RALinScan::processInactiveIntervals(unsigned CurPoint) assert(TargetRegisterInfo::isVirtualRegister(reg) && "Can only allocate virtual registers!"); reg = vrm_->getPhys(reg); - prt_->addRegUse(reg); + addRegUse(reg); // add to active active_.push_back(std::make_pair(Interval, IntervalPos)); @@ -573,9 +704,9 @@ void RALinScan::updateSpillWeights(std::vector &Weights, // bl should get the same spill weight otherwise it will be choosen // 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) - if (!Processed.count(*sr)) - Weights[*sr] += weight; + for (const unsigned *sr = tri_->getSubRegisters(Supers[i]); *sr; ++sr) + if (!Processed.count(*sr)) + Weights[*sr] += weight; } } @@ -601,19 +732,20 @@ 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_, float &Weight, - VirtRegMap &vrm_) { + LiveIntervals *li_, + MachineRegisterInfo* mri_, VirtRegMap &vrm_) { int SS = vrm_.getStackSlot(cur->reg); if (SS == VirtRegMap::NO_STACK_SLOT) return; - LiveInterval &SI = ls_->getOrCreateInterval(SS); - SI.weight += Weight; + + 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()); + VNI = SI.getNextValue(0, 0, false, ls_->getVNInfoAllocator()); LiveInterval &RI = li_->getInterval(cur->reg); // FIXME: This may be overly conservative. @@ -622,10 +754,10 @@ static void addStackInterval(LiveInterval *cur, LiveStacks *ls_, /// 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) { +static +float getConflictWeight(LiveInterval *cur, unsigned Reg, LiveIntervals *li_, + MachineRegisterInfo *mri_, + const MachineLoopInfo *loopInfo) { float Conflicts = 0; for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(Reg), E = mri_->reg_end(); I != E; ++I) { @@ -767,7 +899,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) // 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'; @@ -776,7 +908,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) return; } - PhysRegTracker backupPrt = *prt_; + backUpRegUses(); std::vector > SpillWeightsToAdd; unsigned StartPosition = cur->beginNumber(); @@ -787,9 +919,9 @@ 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->def && !vni->isUnused() && vni->isDefAccurate()) { MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def); unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; if (CopyMI && @@ -799,13 +931,19 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) Reg = SrcReg; else if (vrm_->isAssignedReg(SrcReg)) Reg = vrm_->getPhys(SrcReg); - if (Reg && allocatableRegs_[Reg] && RC->contains(Reg)) - cur->preference = Reg; + if (Reg) { + if (SrcSubReg) + Reg = tri_->getSubReg(Reg, SrcSubReg); + if (DstSubReg) + Reg = tri_->getMatchingSuperReg(Reg, DstSubReg, RC); + if (Reg && allocatableRegs_[Reg] && RC->contains(Reg)) + mri_->setRegAllocationHint(cur->reg, 0, Reg); + } } } } - // for every interval in inactive we overlap with, mark the + // For every interval in inactive we overlap with, mark the // register as not free and update spill weights. for (IntervalPtrs::const_iterator i = inactive_.begin(), e = inactive_.end(); i != e; ++i) { @@ -818,7 +956,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader && cur->overlapsFrom(*i->first, i->second-1)) { Reg = vrm_->getPhys(Reg); - prt_->addRegUse(Reg); + addRegUse(Reg); SpillWeightsToAdd.push_back(std::make_pair(Reg, i->first->weight)); } } @@ -860,7 +998,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 - // prt so we can do an accurate query. + // regUse_ so we can do an accurate query. if (ConflictsWithFixed) { // For every interval in fixed we overlap with, mark the register as not // free and update spill weights. @@ -877,13 +1015,13 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) --II; if (cur->overlapsFrom(*I, II)) { unsigned reg = I->reg; - prt_->addRegUse(reg); + addRegUse(reg); SpillWeightsToAdd.push_back(std::make_pair(reg, I->weight)); } } } - // Using the newly updated prt_ object, which includes conflicts in the + // Using the newly updated regUse_ object, which includes conflicts in the // future, see if there are any registers available. physReg = getFreePhysReg(cur); } @@ -891,15 +1029,15 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) // Restore the physical register tracker, removing information about the // future. - *prt_ = backupPrt; + restoreRegUses(); - // if we find a free register, we are done: assign this virtual to + // 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'; vrm_->assignVirt2Phys(cur->reg, physReg); - prt_->addRegUse(physReg); + addRegUse(physReg); active_.push_back(std::make_pair(cur, cur->begin())); handled_.push_back(cur); @@ -908,7 +1046,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) 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; + mri_->setRegAllocationHint(NextReloadLI->reg, 0, physReg); DowngradeRegister(cur, physReg); } return; @@ -935,7 +1073,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) // 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; @@ -972,6 +1110,15 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) li_->getApproximateInstructionCount(*cur) == 0) { // Spill a physical register around defs and uses. if (li_->spillPhysRegAroundRegDefsUses(*cur, minReg, *vrm_)) { + // spillPhysRegAroundRegDefsUses may have invalidated iterator stored + // in fixed_. Reset them. + for (unsigned i = 0, e = fixed_.size(); i != e; ++i) { + IntervalPtr &IP = fixed_[i]; + LiveInterval *I = IP.first; + if (I->reg == minReg || tri_->isSubRegister(minReg, I->reg)) + IP.second = I->advanceTo(I->begin(), StartPosition); + } + DowngradedRegs.clear(); assignRegOrStackSlotAtInterval(cur); } else { @@ -1000,12 +1147,17 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) // linearscan. if (cur->weight != HUGE_VALF && cur->weight <= minWeight) { DOUT << "\t\t\tspilling(c): " << *cur << '\n'; - float SSWeight; SmallVector spillIs; - std::vector added = - li_->addIntervalsForSpills(*cur, spillIs, loopInfo, *vrm_, SSWeight); + std::vector added; + + if (!NewSpillFramework) { + added = li_->addIntervalsForSpills(*cur, spillIs, loopInfo, *vrm_); + } else { + added = spiller_->spill(cur); + } + std::sort(added.begin(), added.end(), LISorter()); - addStackInterval(cur, ls_, li_, SSWeight, *vrm_); + addStackInterval(cur, ls_, li_, mri_, *vrm_); if (added.empty()) return; // Early exit if all spills were folded. @@ -1064,7 +1216,8 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) // The earliest start of a Spilled interval indicates up to where // in handled we need to roll back - unsigned earliestStart = cur->beginNumber(); + + LiveInterval *earliestStartInterval = cur; // 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 @@ -1073,18 +1226,31 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) // mark our rollback point. std::vector added; while (!spillIs.empty()) { + bool epicFail = false; LiveInterval *sli = spillIs.back(); spillIs.pop_back(); DOUT << "\t\t\tspilling(a): " << *sli << '\n'; - earliestStart = std::min(earliestStart, sli->beginNumber()); - float SSWeight; - std::vector newIs = - li_->addIntervalsForSpills(*sli, spillIs, loopInfo, *vrm_, SSWeight); - addStackInterval(sli, ls_, li_, SSWeight, *vrm_); + 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)); spilled.insert(sli->reg); + + if (epicFail) { + //abort(); + } } + unsigned earliestStart = earliestStartInterval->beginNumber(); + DOUT << "\t\trolling back to: " << earliestStart << '\n'; // Scan handled in reverse order up to the earliest start of a @@ -1099,14 +1265,14 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) handled_.pop_back(); // When undoing a live interval allocation we must know if it is active or - // inactive to properly update the PhysRegTracker and the VirtRegMap. + // inactive to properly update regUse_ and the VirtRegMap. IntervalPtrs::iterator it; if ((it = FindIntervalInVector(active_, i)) != active_.end()) { active_.erase(it); assert(!TargetRegisterInfo::isPhysicalRegister(i->reg)); if (!spilled.count(i->reg)) unhandled_.push(i); - prt_->delRegUse(vrm_->getPhys(i->reg)); + delRegUse(vrm_->getPhys(i->reg)); vrm_->clearVirt(i->reg); } else if ((it = FindIntervalInVector(inactive_, i)) != inactive_.end()) { inactive_.erase(it); @@ -1126,7 +1292,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); } @@ -1148,7 +1314,7 @@ void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) DOUT << "\t\t\tundo changes for: " << *HI << '\n'; active_.push_back(std::make_pair(HI, HI->begin())); assert(!TargetRegisterInfo::isPhysicalRegister(HI->reg)); - prt_->addRegUse(vrm_->getPhys(HI->reg)); + addRegUse(vrm_->getPhys(HI->reg)); } } @@ -1182,15 +1348,23 @@ 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_); + std::pair Hint = mri_->getRegAllocationHint(cur->reg); + // Resolve second part of the hint (if possible) given the current allocation. + unsigned physReg = Hint.second; + if (physReg && + TargetRegisterInfo::isVirtualRegister(physReg) && vrm_->hasPhys(physReg)) + physReg = vrm_->getPhys(physReg); + + TargetRegisterClass::iterator I, E; + tie(I, E) = tri_->getAllocationOrder(RC, Hint.first, physReg, *mf_); assert(I != E && "No allocatable register in this register class!"); // Scan for the first available register. @@ -1199,7 +1373,7 @@ unsigned RALinScan::getFreePhysReg(const TargetRegisterClass *RC, // Ignore "downgraded" registers. if (SkipDGRegs && DowngradedRegs.count(Reg)) continue; - if (prt_->isRegAvail(Reg)) { + if (isRegAvail(Reg)) { FreeReg = Reg; if (FreeReg < inactiveCounts.size()) FreeRegInactiveCount = inactiveCounts[FreeReg]; @@ -1213,7 +1387,7 @@ unsigned RALinScan::getFreePhysReg(const TargetRegisterClass *RC, // return this register. if (FreeReg == 0 || FreeRegInactiveCount == MaxInactiveCount) 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 @@ -1223,7 +1397,7 @@ unsigned RALinScan::getFreePhysReg(const TargetRegisterClass *RC, // Ignore "downgraded" registers. if (SkipDGRegs && DowngradedRegs.count(Reg)) continue; - if (prt_->isRegAvail(Reg) && Reg < inactiveCounts.size() && + if (isRegAvail(Reg) && Reg < inactiveCounts.size() && FreeRegInactiveCount < inactiveCounts[Reg]) { FreeReg = Reg; FreeRegInactiveCount = inactiveCounts[Reg]; @@ -1264,24 +1438,21 @@ unsigned RALinScan::getFreePhysReg(LiveInterval *cur) { // If copy coalescer has assigned a "preferred" register, check if it's // available first. - if (cur->preference) { - if (prt_->isRegAvail(cur->preference) && - RC->contains(cur->preference)) { - DOUT << "\t\tassigned the preferred register: " - << tri_->getName(cur->preference) << "\n"; - return cur->preference; - } else - DOUT << "\t\tunable to assign the preferred register: " - << tri_->getName(cur->preference) << "\n"; + unsigned Preference = vrm_->getRegAllocPref(cur->reg); + if (Preference) { + DOUT << "(preferred: " << tri_->getName(Preference) << ") "; + if (isRegAvail(Preference) && + RC->contains(Preference)) + return Preference; } if (!DowngradedRegs.empty()) { - unsigned FreeReg = getFreePhysReg(RC, MaxInactiveCount, inactiveCounts, + unsigned FreeReg = getFreePhysReg(cur, RC, MaxInactiveCount, inactiveCounts, true); if (FreeReg) return FreeReg; } - return getFreePhysReg(RC, MaxInactiveCount, inactiveCounts, false); + return getFreePhysReg(cur, RC, MaxInactiveCount, inactiveCounts, false); } FunctionPass* llvm::createLinearScanRegisterAllocator() {