1 //===-- RegAllocLinearScan.cpp - Linear Scan register allocator -----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a linear scan register allocator.
12 //===----------------------------------------------------------------------===//
14 #define DEBUG_TYPE "regalloc"
15 #include "PhysRegTracker.h"
16 #include "VirtRegMap.h"
18 #include "llvm/Function.h"
19 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
20 #include "llvm/CodeGen/LiveStackAnalysis.h"
21 #include "llvm/CodeGen/MachineFunctionPass.h"
22 #include "llvm/CodeGen/MachineInstr.h"
23 #include "llvm/CodeGen/MachineLoopInfo.h"
24 #include "llvm/CodeGen/MachineRegisterInfo.h"
25 #include "llvm/CodeGen/Passes.h"
26 #include "llvm/CodeGen/RegAllocRegistry.h"
27 #include "llvm/CodeGen/RegisterCoalescer.h"
28 #include "llvm/Target/TargetRegisterInfo.h"
29 #include "llvm/Target/TargetMachine.h"
30 #include "llvm/Target/TargetOptions.h"
31 #include "llvm/Target/TargetInstrInfo.h"
32 #include "llvm/ADT/EquivalenceClasses.h"
33 #include "llvm/ADT/SmallSet.h"
34 #include "llvm/ADT/Statistic.h"
35 #include "llvm/ADT/STLExtras.h"
36 #include "llvm/Support/Debug.h"
37 #include "llvm/Support/Compiler.h"
45 STATISTIC(NumIters , "Number of iterations performed");
46 STATISTIC(NumBacktracks, "Number of times we had to backtrack");
47 STATISTIC(NumCoalesce, "Number of copies coalesced");
48 STATISTIC(NumDowngrade, "Number of registers downgraded");
51 NewHeuristic("new-spilling-heuristic",
52 cl::desc("Use new spilling heuristic"),
53 cl::init(false), cl::Hidden);
56 PreSplitIntervals("pre-alloc-split",
57 cl::desc("Pre-register allocation live interval splitting"),
58 cl::init(false), cl::Hidden);
60 static RegisterRegAlloc
61 linearscanRegAlloc("linearscan", "linear scan register allocator",
62 createLinearScanRegisterAllocator);
65 struct VISIBILITY_HIDDEN RALinScan : public MachineFunctionPass {
67 RALinScan() : MachineFunctionPass(&ID) {}
69 typedef std::pair<LiveInterval*, LiveInterval::iterator> IntervalPtr;
70 typedef SmallVector<IntervalPtr, 32> IntervalPtrs;
72 /// RelatedRegClasses - This structure is built the first time a function is
73 /// compiled, and keeps track of which register classes have registers that
74 /// belong to multiple classes or have aliases that are in other classes.
75 EquivalenceClasses<const TargetRegisterClass*> RelatedRegClasses;
76 DenseMap<unsigned, const TargetRegisterClass*> OneClassForEachPhysReg;
78 // NextReloadMap - For each register in the map, it maps to the another
79 // register which is defined by a reload from the same stack slot and
80 // both reloads are in the same basic block.
81 DenseMap<unsigned, unsigned> NextReloadMap;
83 // DowngradedRegs - A set of registers which are being "downgraded", i.e.
84 // un-favored for allocation.
85 SmallSet<unsigned, 8> DowngradedRegs;
87 // DowngradeMap - A map from virtual registers to physical registers being
88 // downgraded for the virtual registers.
89 DenseMap<unsigned, unsigned> DowngradeMap;
92 MachineRegisterInfo* mri_;
93 const TargetMachine* tm_;
94 const TargetRegisterInfo* tri_;
95 const TargetInstrInfo* tii_;
96 BitVector allocatableRegs_;
99 const MachineLoopInfo *loopInfo;
101 /// handled_ - Intervals are added to the handled_ set in the order of their
102 /// start value. This is uses for backtracking.
103 std::vector<LiveInterval*> handled_;
105 /// fixed_ - Intervals that correspond to machine registers.
109 /// active_ - Intervals that are currently being processed, and which have a
110 /// live range active for the current point.
111 IntervalPtrs active_;
113 /// inactive_ - Intervals that are currently being processed, but which have
114 /// a hold at the current point.
115 IntervalPtrs inactive_;
117 typedef std::priority_queue<LiveInterval*,
118 SmallVector<LiveInterval*, 64>,
119 greater_ptr<LiveInterval> > IntervalHeap;
120 IntervalHeap unhandled_;
121 std::auto_ptr<PhysRegTracker> prt_;
123 std::auto_ptr<Spiller> spiller_;
126 virtual const char* getPassName() const {
127 return "Linear Scan Register Allocator";
130 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
131 AU.addRequired<LiveIntervals>();
133 AU.addRequiredID(StrongPHIEliminationID);
134 // Make sure PassManager knows which analyses to make available
135 // to coalescing and which analyses coalescing invalidates.
136 AU.addRequiredTransitive<RegisterCoalescer>();
137 if (PreSplitIntervals)
138 AU.addRequiredID(PreAllocSplittingID);
139 AU.addRequired<LiveStacks>();
140 AU.addPreserved<LiveStacks>();
141 AU.addRequired<MachineLoopInfo>();
142 AU.addPreserved<MachineLoopInfo>();
143 AU.addRequired<VirtRegMap>();
144 AU.addPreserved<VirtRegMap>();
145 AU.addPreservedID(MachineDominatorsID);
146 MachineFunctionPass::getAnalysisUsage(AU);
149 /// runOnMachineFunction - register allocate the whole function
150 bool runOnMachineFunction(MachineFunction&);
153 /// linearScan - the linear scan algorithm
156 /// initIntervalSets - initialize the interval sets.
158 void initIntervalSets();
160 /// processActiveIntervals - expire old intervals and move non-overlapping
161 /// ones to the inactive list.
162 void processActiveIntervals(unsigned CurPoint);
164 /// processInactiveIntervals - expire old intervals and move overlapping
165 /// ones to the active list.
166 void processInactiveIntervals(unsigned CurPoint);
168 /// hasNextReloadInterval - Return the next liveinterval that's being
169 /// defined by a reload from the same SS as the specified one.
170 LiveInterval *hasNextReloadInterval(LiveInterval *cur);
172 /// DowngradeRegister - Downgrade a register for allocation.
173 void DowngradeRegister(LiveInterval *li, unsigned Reg);
175 /// UpgradeRegister - Upgrade a register for allocation.
176 void UpgradeRegister(unsigned Reg);
178 /// assignRegOrStackSlotAtInterval - assign a register if one
179 /// is available, or spill.
180 void assignRegOrStackSlotAtInterval(LiveInterval* cur);
182 void updateSpillWeights(std::vector<float> &Weights,
183 unsigned reg, float weight,
184 const TargetRegisterClass *RC);
186 /// findIntervalsToSpill - Determine the intervals to spill for the
187 /// specified interval. It's passed the physical registers whose spill
188 /// weight is the lowest among all the registers whose live intervals
189 /// conflict with the interval.
190 void findIntervalsToSpill(LiveInterval *cur,
191 std::vector<std::pair<unsigned,float> > &Candidates,
193 SmallVector<LiveInterval*, 8> &SpillIntervals);
195 /// attemptTrivialCoalescing - If a simple interval is defined by a copy,
196 /// try allocate the definition the same register as the source register
197 /// if the register is not defined during live time of the interval. This
198 /// eliminate a copy. This is used to coalesce copies which were not
199 /// coalesced away before allocation either due to dest and src being in
200 /// different register classes or because the coalescer was overly
202 unsigned attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg);
205 /// register handling helpers
208 /// getFreePhysReg - return a free physical register for this virtual
209 /// register interval if we have one, otherwise return 0.
210 unsigned getFreePhysReg(LiveInterval* cur);
211 unsigned getFreePhysReg(const TargetRegisterClass *RC,
212 unsigned MaxInactiveCount,
213 SmallVector<unsigned, 256> &inactiveCounts,
216 /// assignVirt2StackSlot - assigns this virtual register to a
217 /// stack slot. returns the stack slot
218 int assignVirt2StackSlot(unsigned virtReg);
220 void ComputeRelatedRegClasses();
222 template <typename ItTy>
223 void printIntervals(const char* const str, ItTy i, ItTy e) const {
224 if (str) DOUT << str << " intervals:\n";
225 for (; i != e; ++i) {
226 DOUT << "\t" << *i->first << " -> ";
227 unsigned reg = i->first->reg;
228 if (TargetRegisterInfo::isVirtualRegister(reg)) {
229 reg = vrm_->getPhys(reg);
231 DOUT << tri_->getName(reg) << '\n';
235 char RALinScan::ID = 0;
238 static RegisterPass<RALinScan>
239 X("linearscan-regalloc", "Linear Scan Register Allocator");
241 void RALinScan::ComputeRelatedRegClasses() {
242 // First pass, add all reg classes to the union, and determine at least one
243 // reg class that each register is in.
244 bool HasAliases = false;
245 for (TargetRegisterInfo::regclass_iterator RCI = tri_->regclass_begin(),
246 E = tri_->regclass_end(); RCI != E; ++RCI) {
247 RelatedRegClasses.insert(*RCI);
248 for (TargetRegisterClass::iterator I = (*RCI)->begin(), E = (*RCI)->end();
250 HasAliases = HasAliases || *tri_->getAliasSet(*I) != 0;
252 const TargetRegisterClass *&PRC = OneClassForEachPhysReg[*I];
254 // Already processed this register. Just make sure we know that
255 // multiple register classes share a register.
256 RelatedRegClasses.unionSets(PRC, *RCI);
263 // Second pass, now that we know conservatively what register classes each reg
264 // belongs to, add info about aliases. We don't need to do this for targets
265 // without register aliases.
267 for (DenseMap<unsigned, const TargetRegisterClass*>::iterator
268 I = OneClassForEachPhysReg.begin(), E = OneClassForEachPhysReg.end();
270 for (const unsigned *AS = tri_->getAliasSet(I->first); *AS; ++AS)
271 RelatedRegClasses.unionSets(I->second, OneClassForEachPhysReg[*AS]);
274 /// attemptTrivialCoalescing - If a simple interval is defined by a copy,
275 /// try allocate the definition the same register as the source register
276 /// if the register is not defined during live time of the interval. This
277 /// eliminate a copy. This is used to coalesce copies which were not
278 /// coalesced away before allocation either due to dest and src being in
279 /// different register classes or because the coalescer was overly
281 unsigned RALinScan::attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg) {
282 if ((cur.preference && cur.preference == Reg) || !cur.containsOneValue())
285 VNInfo *vni = cur.begin()->valno;
286 if (!vni->def || vni->def == ~1U || vni->def == ~0U)
288 MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
289 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
291 !tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubReg, DstSubReg))
293 if (TargetRegisterInfo::isVirtualRegister(SrcReg)) {
294 if (!vrm_->isAssignedReg(SrcReg))
297 SrcReg = vrm_->getPhys(SrcReg);
302 const TargetRegisterClass *RC = mri_->getRegClass(cur.reg);
303 if (!RC->contains(SrcReg))
307 if (!li_->conflictsWithPhysRegDef(cur, *vrm_, SrcReg)) {
308 DOUT << "Coalescing: " << cur << " -> " << tri_->getName(SrcReg)
310 vrm_->clearVirt(cur.reg);
311 vrm_->assignVirt2Phys(cur.reg, SrcReg);
319 bool RALinScan::runOnMachineFunction(MachineFunction &fn) {
321 mri_ = &fn.getRegInfo();
322 tm_ = &fn.getTarget();
323 tri_ = tm_->getRegisterInfo();
324 tii_ = tm_->getInstrInfo();
325 allocatableRegs_ = tri_->getAllocatableSet(fn);
326 li_ = &getAnalysis<LiveIntervals>();
327 ls_ = &getAnalysis<LiveStacks>();
328 loopInfo = &getAnalysis<MachineLoopInfo>();
330 // We don't run the coalescer here because we have no reason to
331 // interact with it. If the coalescer requires interaction, it
332 // won't do anything. If it doesn't require interaction, we assume
333 // it was run as a separate pass.
335 // If this is the first function compiled, compute the related reg classes.
336 if (RelatedRegClasses.empty())
337 ComputeRelatedRegClasses();
339 if (!prt_.get()) prt_.reset(new PhysRegTracker(*tri_));
340 vrm_ = &getAnalysis<VirtRegMap>();
341 if (!spiller_.get()) spiller_.reset(createSpiller());
347 // Rewrite spill code and update the PhysRegsUsed set.
348 spiller_->runOnMachineFunction(*mf_, *vrm_, li_);
350 assert(unhandled_.empty() && "Unhandled live intervals remain!");
355 NextReloadMap.clear();
356 DowngradedRegs.clear();
357 DowngradeMap.clear();
362 /// initIntervalSets - initialize the interval sets.
364 void RALinScan::initIntervalSets()
366 assert(unhandled_.empty() && fixed_.empty() &&
367 active_.empty() && inactive_.empty() &&
368 "interval sets should be empty on initialization");
370 handled_.reserve(li_->getNumIntervals());
372 for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
373 if (TargetRegisterInfo::isPhysicalRegister(i->second->reg)) {
374 mri_->setPhysRegUsed(i->second->reg);
375 fixed_.push_back(std::make_pair(i->second, i->second->begin()));
377 unhandled_.push(i->second);
381 void RALinScan::linearScan()
383 // linear scan algorithm
384 DOUT << "********** LINEAR SCAN **********\n";
385 DOUT << "********** Function: " << mf_->getFunction()->getName() << '\n';
387 DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end()));
389 while (!unhandled_.empty()) {
390 // pick the interval with the earliest start point
391 LiveInterval* cur = unhandled_.top();
394 DOUT << "\n*** CURRENT ***: " << *cur << '\n';
397 processActiveIntervals(cur->beginNumber());
398 processInactiveIntervals(cur->beginNumber());
400 assert(TargetRegisterInfo::isVirtualRegister(cur->reg) &&
401 "Can only allocate virtual registers!");
404 // Allocating a virtual register. try to find a free
405 // physical register or spill an interval (possibly this one) in order to
407 assignRegOrStackSlotAtInterval(cur);
409 DEBUG(printIntervals("active", active_.begin(), active_.end()));
410 DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
413 // expire any remaining active intervals
414 while (!active_.empty()) {
415 IntervalPtr &IP = active_.back();
416 unsigned reg = IP.first->reg;
417 DOUT << "\tinterval " << *IP.first << " expired\n";
418 assert(TargetRegisterInfo::isVirtualRegister(reg) &&
419 "Can only allocate virtual registers!");
420 reg = vrm_->getPhys(reg);
421 prt_->delRegUse(reg);
425 // expire any remaining inactive intervals
426 DEBUG(for (IntervalPtrs::reverse_iterator
427 i = inactive_.rbegin(); i != inactive_.rend(); ++i)
428 DOUT << "\tinterval " << *i->first << " expired\n");
431 // Add live-ins to every BB except for entry. Also perform trivial coalescing.
432 MachineFunction::iterator EntryMBB = mf_->begin();
433 SmallVector<MachineBasicBlock*, 8> LiveInMBBs;
434 for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
435 LiveInterval &cur = *i->second;
437 bool isPhys = TargetRegisterInfo::isPhysicalRegister(cur.reg);
440 else if (vrm_->isAssignedReg(cur.reg))
441 Reg = attemptTrivialCoalescing(cur, vrm_->getPhys(cur.reg));
444 // Ignore splited live intervals.
445 if (!isPhys && vrm_->getPreSplitReg(cur.reg))
447 for (LiveInterval::Ranges::const_iterator I = cur.begin(), E = cur.end();
449 const LiveRange &LR = *I;
450 if (li_->findLiveInMBBs(LR.start, LR.end, LiveInMBBs)) {
451 for (unsigned i = 0, e = LiveInMBBs.size(); i != e; ++i)
452 if (LiveInMBBs[i] != EntryMBB)
453 LiveInMBBs[i]->addLiveIn(Reg);
462 /// processActiveIntervals - expire old intervals and move non-overlapping ones
463 /// to the inactive list.
464 void RALinScan::processActiveIntervals(unsigned CurPoint)
466 DOUT << "\tprocessing active intervals:\n";
468 for (unsigned i = 0, e = active_.size(); i != e; ++i) {
469 LiveInterval *Interval = active_[i].first;
470 LiveInterval::iterator IntervalPos = active_[i].second;
471 unsigned reg = Interval->reg;
473 IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
475 if (IntervalPos == Interval->end()) { // Remove expired intervals.
476 DOUT << "\t\tinterval " << *Interval << " expired\n";
477 assert(TargetRegisterInfo::isVirtualRegister(reg) &&
478 "Can only allocate virtual registers!");
479 reg = vrm_->getPhys(reg);
480 prt_->delRegUse(reg);
482 // Pop off the end of the list.
483 active_[i] = active_.back();
487 } else if (IntervalPos->start > CurPoint) {
488 // Move inactive intervals to inactive list.
489 DOUT << "\t\tinterval " << *Interval << " inactive\n";
490 assert(TargetRegisterInfo::isVirtualRegister(reg) &&
491 "Can only allocate virtual registers!");
492 reg = vrm_->getPhys(reg);
493 prt_->delRegUse(reg);
495 inactive_.push_back(std::make_pair(Interval, IntervalPos));
497 // Pop off the end of the list.
498 active_[i] = active_.back();
502 // Otherwise, just update the iterator position.
503 active_[i].second = IntervalPos;
508 /// processInactiveIntervals - expire old intervals and move overlapping
509 /// ones to the active list.
510 void RALinScan::processInactiveIntervals(unsigned CurPoint)
512 DOUT << "\tprocessing inactive intervals:\n";
514 for (unsigned i = 0, e = inactive_.size(); i != e; ++i) {
515 LiveInterval *Interval = inactive_[i].first;
516 LiveInterval::iterator IntervalPos = inactive_[i].second;
517 unsigned reg = Interval->reg;
519 IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
521 if (IntervalPos == Interval->end()) { // remove expired intervals.
522 DOUT << "\t\tinterval " << *Interval << " expired\n";
524 // Pop off the end of the list.
525 inactive_[i] = inactive_.back();
526 inactive_.pop_back();
528 } else if (IntervalPos->start <= CurPoint) {
529 // move re-activated intervals in active list
530 DOUT << "\t\tinterval " << *Interval << " active\n";
531 assert(TargetRegisterInfo::isVirtualRegister(reg) &&
532 "Can only allocate virtual registers!");
533 reg = vrm_->getPhys(reg);
534 prt_->addRegUse(reg);
536 active_.push_back(std::make_pair(Interval, IntervalPos));
538 // Pop off the end of the list.
539 inactive_[i] = inactive_.back();
540 inactive_.pop_back();
543 // Otherwise, just update the iterator position.
544 inactive_[i].second = IntervalPos;
549 /// updateSpillWeights - updates the spill weights of the specifed physical
550 /// register and its weight.
551 void RALinScan::updateSpillWeights(std::vector<float> &Weights,
552 unsigned reg, float weight,
553 const TargetRegisterClass *RC) {
554 SmallSet<unsigned, 4> Processed;
555 SmallSet<unsigned, 4> SuperAdded;
556 SmallVector<unsigned, 4> Supers;
557 Weights[reg] += weight;
558 Processed.insert(reg);
559 for (const unsigned* as = tri_->getAliasSet(reg); *as; ++as) {
560 Weights[*as] += weight;
561 Processed.insert(*as);
562 if (tri_->isSubRegister(*as, reg) &&
563 SuperAdded.insert(*as) &&
565 Supers.push_back(*as);
569 // If the alias is a super-register, and the super-register is in the
570 // register class we are trying to allocate. Then add the weight to all
571 // sub-registers of the super-register even if they are not aliases.
572 // e.g. allocating for GR32, bh is not used, updating bl spill weight.
573 // bl should get the same spill weight otherwise it will be choosen
574 // as a spill candidate since spilling bh doesn't make ebx available.
575 for (unsigned i = 0, e = Supers.size(); i != e; ++i) {
576 for (const unsigned *sr = tri_->getSubRegisters(Supers[i]); *sr; ++sr)
577 if (!Processed.count(*sr))
578 Weights[*sr] += weight;
583 RALinScan::IntervalPtrs::iterator
584 FindIntervalInVector(RALinScan::IntervalPtrs &IP, LiveInterval *LI) {
585 for (RALinScan::IntervalPtrs::iterator I = IP.begin(), E = IP.end();
587 if (I->first == LI) return I;
591 static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V, unsigned Point){
592 for (unsigned i = 0, e = V.size(); i != e; ++i) {
593 RALinScan::IntervalPtr &IP = V[i];
594 LiveInterval::iterator I = std::upper_bound(IP.first->begin(),
596 if (I != IP.first->begin()) --I;
601 /// addStackInterval - Create a LiveInterval for stack if the specified live
602 /// interval has been spilled.
603 static void addStackInterval(LiveInterval *cur, LiveStacks *ls_,
604 LiveIntervals *li_, float &Weight,
606 int SS = vrm_.getStackSlot(cur->reg);
607 if (SS == VirtRegMap::NO_STACK_SLOT)
609 LiveInterval &SI = ls_->getOrCreateInterval(SS);
613 if (SI.hasAtLeastOneValue())
614 VNI = SI.getValNumInfo(0);
616 VNI = SI.getNextValue(~0U, 0, ls_->getVNInfoAllocator());
618 LiveInterval &RI = li_->getInterval(cur->reg);
619 // FIXME: This may be overly conservative.
620 SI.MergeRangesInAsValue(RI, VNI);
623 /// getConflictWeight - Return the number of conflicts between cur
624 /// live interval and defs and uses of Reg weighted by loop depthes.
625 static float getConflictWeight(LiveInterval *cur, unsigned Reg,
627 MachineRegisterInfo *mri_,
628 const MachineLoopInfo *loopInfo) {
630 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(Reg),
631 E = mri_->reg_end(); I != E; ++I) {
632 MachineInstr *MI = &*I;
633 if (cur->liveAt(li_->getInstructionIndex(MI))) {
634 unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent());
635 Conflicts += powf(10.0f, (float)loopDepth);
641 /// findIntervalsToSpill - Determine the intervals to spill for the
642 /// specified interval. It's passed the physical registers whose spill
643 /// weight is the lowest among all the registers whose live intervals
644 /// conflict with the interval.
645 void RALinScan::findIntervalsToSpill(LiveInterval *cur,
646 std::vector<std::pair<unsigned,float> > &Candidates,
648 SmallVector<LiveInterval*, 8> &SpillIntervals) {
649 // We have figured out the *best* register to spill. But there are other
650 // registers that are pretty good as well (spill weight within 3%). Spill
651 // the one that has fewest defs and uses that conflict with cur.
652 float Conflicts[3] = { 0.0f, 0.0f, 0.0f };
653 SmallVector<LiveInterval*, 8> SLIs[3];
655 DOUT << "\tConsidering " << NumCands << " candidates: ";
656 DEBUG(for (unsigned i = 0; i != NumCands; ++i)
657 DOUT << tri_->getName(Candidates[i].first) << " ";
660 // Calculate the number of conflicts of each candidate.
661 for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
662 unsigned Reg = i->first->reg;
663 unsigned PhysReg = vrm_->getPhys(Reg);
664 if (!cur->overlapsFrom(*i->first, i->second))
666 for (unsigned j = 0; j < NumCands; ++j) {
667 unsigned Candidate = Candidates[j].first;
668 if (tri_->regsOverlap(PhysReg, Candidate)) {
670 Conflicts[j] += getConflictWeight(cur, Reg, li_, mri_, loopInfo);
671 SLIs[j].push_back(i->first);
676 for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end(); ++i){
677 unsigned Reg = i->first->reg;
678 unsigned PhysReg = vrm_->getPhys(Reg);
679 if (!cur->overlapsFrom(*i->first, i->second-1))
681 for (unsigned j = 0; j < NumCands; ++j) {
682 unsigned Candidate = Candidates[j].first;
683 if (tri_->regsOverlap(PhysReg, Candidate)) {
685 Conflicts[j] += getConflictWeight(cur, Reg, li_, mri_, loopInfo);
686 SLIs[j].push_back(i->first);
691 // Which is the best candidate?
692 unsigned BestCandidate = 0;
693 float MinConflicts = Conflicts[0];
694 for (unsigned i = 1; i != NumCands; ++i) {
695 if (Conflicts[i] < MinConflicts) {
697 MinConflicts = Conflicts[i];
701 std::copy(SLIs[BestCandidate].begin(), SLIs[BestCandidate].end(),
702 std::back_inserter(SpillIntervals));
706 struct WeightCompare {
707 typedef std::pair<unsigned, float> RegWeightPair;
708 bool operator()(const RegWeightPair &LHS, const RegWeightPair &RHS) const {
709 return LHS.second < RHS.second;
714 static bool weightsAreClose(float w1, float w2) {
718 float diff = w1 - w2;
719 if (diff <= 0.02f) // Within 0.02f
721 return (diff / w2) <= 0.05f; // Within 5%.
724 LiveInterval *RALinScan::hasNextReloadInterval(LiveInterval *cur) {
725 DenseMap<unsigned, unsigned>::iterator I = NextReloadMap.find(cur->reg);
726 if (I == NextReloadMap.end())
728 return &li_->getInterval(I->second);
731 void RALinScan::DowngradeRegister(LiveInterval *li, unsigned Reg) {
732 bool isNew = DowngradedRegs.insert(Reg);
733 isNew = isNew; // Silence compiler warning.
734 assert(isNew && "Multiple reloads holding the same register?");
735 DowngradeMap.insert(std::make_pair(li->reg, Reg));
736 for (const unsigned *AS = tri_->getAliasSet(Reg); *AS; ++AS) {
737 isNew = DowngradedRegs.insert(*AS);
738 isNew = isNew; // Silence compiler warning.
739 assert(isNew && "Multiple reloads holding the same register?");
740 DowngradeMap.insert(std::make_pair(li->reg, *AS));
745 void RALinScan::UpgradeRegister(unsigned Reg) {
747 DowngradedRegs.erase(Reg);
748 for (const unsigned *AS = tri_->getAliasSet(Reg); *AS; ++AS)
749 DowngradedRegs.erase(*AS);
755 bool operator()(LiveInterval* A, LiveInterval* B) {
756 return A->beginNumber() < B->beginNumber();
761 /// assignRegOrStackSlotAtInterval - assign a register if one is available, or
763 void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
765 DOUT << "\tallocating current interval: ";
767 // This is an implicitly defined live interval, just assign any register.
768 const TargetRegisterClass *RC = mri_->getRegClass(cur->reg);
770 unsigned physReg = cur->preference;
772 physReg = *RC->allocation_order_begin(*mf_);
773 DOUT << tri_->getName(physReg) << '\n';
774 // Note the register is not really in use.
775 vrm_->assignVirt2Phys(cur->reg, physReg);
779 PhysRegTracker backupPrt = *prt_;
781 std::vector<std::pair<unsigned, float> > SpillWeightsToAdd;
782 unsigned StartPosition = cur->beginNumber();
783 const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
785 // If start of this live interval is defined by a move instruction and its
786 // source is assigned a physical register that is compatible with the target
787 // register class, then we should try to assign it the same register.
788 // This can happen when the move is from a larger register class to a smaller
789 // one, e.g. X86::mov32to32_. These move instructions are not coalescable.
790 if (!cur->preference && cur->hasAtLeastOneValue()) {
791 VNInfo *vni = cur->begin()->valno;
792 if (vni->def && vni->def != ~1U && vni->def != ~0U) {
793 MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
794 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
796 tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubReg, DstSubReg)) {
798 if (TargetRegisterInfo::isPhysicalRegister(SrcReg))
800 else if (vrm_->isAssignedReg(SrcReg))
801 Reg = vrm_->getPhys(SrcReg);
804 Reg = tri_->getSubReg(Reg, SrcSubReg);
806 Reg = tri_->getMatchingSuperReg(Reg, DstSubReg, RC);
807 if (Reg && allocatableRegs_[Reg] && RC->contains(Reg))
808 cur->preference = Reg;
814 // for every interval in inactive we overlap with, mark the
815 // register as not free and update spill weights.
816 for (IntervalPtrs::const_iterator i = inactive_.begin(),
817 e = inactive_.end(); i != e; ++i) {
818 unsigned Reg = i->first->reg;
819 assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
820 "Can only allocate virtual registers!");
821 const TargetRegisterClass *RegRC = mri_->getRegClass(Reg);
822 // If this is not in a related reg class to the register we're allocating,
824 if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader &&
825 cur->overlapsFrom(*i->first, i->second-1)) {
826 Reg = vrm_->getPhys(Reg);
827 prt_->addRegUse(Reg);
828 SpillWeightsToAdd.push_back(std::make_pair(Reg, i->first->weight));
832 // Speculatively check to see if we can get a register right now. If not,
833 // we know we won't be able to by adding more constraints. If so, we can
834 // check to see if it is valid. Doing an exhaustive search of the fixed_ list
835 // is very bad (it contains all callee clobbered registers for any functions
836 // with a call), so we want to avoid doing that if possible.
837 unsigned physReg = getFreePhysReg(cur);
838 unsigned BestPhysReg = physReg;
840 // We got a register. However, if it's in the fixed_ list, we might
841 // conflict with it. Check to see if we conflict with it or any of its
843 SmallSet<unsigned, 8> RegAliases;
844 for (const unsigned *AS = tri_->getAliasSet(physReg); *AS; ++AS)
845 RegAliases.insert(*AS);
847 bool ConflictsWithFixed = false;
848 for (unsigned i = 0, e = fixed_.size(); i != e; ++i) {
849 IntervalPtr &IP = fixed_[i];
850 if (physReg == IP.first->reg || RegAliases.count(IP.first->reg)) {
851 // Okay, this reg is on the fixed list. Check to see if we actually
853 LiveInterval *I = IP.first;
854 if (I->endNumber() > StartPosition) {
855 LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition);
857 if (II != I->begin() && II->start > StartPosition)
859 if (cur->overlapsFrom(*I, II)) {
860 ConflictsWithFixed = true;
867 // Okay, the register picked by our speculative getFreePhysReg call turned
868 // out to be in use. Actually add all of the conflicting fixed registers to
869 // prt so we can do an accurate query.
870 if (ConflictsWithFixed) {
871 // For every interval in fixed we overlap with, mark the register as not
872 // free and update spill weights.
873 for (unsigned i = 0, e = fixed_.size(); i != e; ++i) {
874 IntervalPtr &IP = fixed_[i];
875 LiveInterval *I = IP.first;
877 const TargetRegisterClass *RegRC = OneClassForEachPhysReg[I->reg];
878 if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader &&
879 I->endNumber() > StartPosition) {
880 LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition);
882 if (II != I->begin() && II->start > StartPosition)
884 if (cur->overlapsFrom(*I, II)) {
885 unsigned reg = I->reg;
886 prt_->addRegUse(reg);
887 SpillWeightsToAdd.push_back(std::make_pair(reg, I->weight));
892 // Using the newly updated prt_ object, which includes conflicts in the
893 // future, see if there are any registers available.
894 physReg = getFreePhysReg(cur);
898 // Restore the physical register tracker, removing information about the
902 // if we find a free register, we are done: assign this virtual to
903 // the free physical register and add this interval to the active
906 DOUT << tri_->getName(physReg) << '\n';
907 vrm_->assignVirt2Phys(cur->reg, physReg);
908 prt_->addRegUse(physReg);
909 active_.push_back(std::make_pair(cur, cur->begin()));
910 handled_.push_back(cur);
912 // "Upgrade" the physical register since it has been allocated.
913 UpgradeRegister(physReg);
914 if (LiveInterval *NextReloadLI = hasNextReloadInterval(cur)) {
915 // "Downgrade" physReg to try to keep physReg from being allocated until
916 // the next reload from the same SS is allocated.
917 NextReloadLI->preference = physReg;
918 DowngradeRegister(cur, physReg);
922 DOUT << "no free registers\n";
924 // Compile the spill weights into an array that is better for scanning.
925 std::vector<float> SpillWeights(tri_->getNumRegs(), 0.0f);
926 for (std::vector<std::pair<unsigned, float> >::iterator
927 I = SpillWeightsToAdd.begin(), E = SpillWeightsToAdd.end(); I != E; ++I)
928 updateSpillWeights(SpillWeights, I->first, I->second, RC);
930 // for each interval in active, update spill weights.
931 for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
933 unsigned reg = i->first->reg;
934 assert(TargetRegisterInfo::isVirtualRegister(reg) &&
935 "Can only allocate virtual registers!");
936 reg = vrm_->getPhys(reg);
937 updateSpillWeights(SpillWeights, reg, i->first->weight, RC);
940 DOUT << "\tassigning stack slot at interval "<< *cur << ":\n";
942 // Find a register to spill.
943 float minWeight = HUGE_VALF;
944 unsigned minReg = 0; /*cur->preference*/; // Try the pref register first.
947 std::vector<std::pair<unsigned,float> > RegsWeights;
948 if (!minReg || SpillWeights[minReg] == HUGE_VALF)
949 for (TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_),
950 e = RC->allocation_order_end(*mf_); i != e; ++i) {
952 float regWeight = SpillWeights[reg];
953 if (minWeight > regWeight)
955 RegsWeights.push_back(std::make_pair(reg, regWeight));
958 // If we didn't find a register that is spillable, try aliases?
960 for (TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_),
961 e = RC->allocation_order_end(*mf_); i != e; ++i) {
963 // No need to worry about if the alias register size < regsize of RC.
964 // We are going to spill all registers that alias it anyway.
965 for (const unsigned* as = tri_->getAliasSet(reg); *as; ++as)
966 RegsWeights.push_back(std::make_pair(*as, SpillWeights[*as]));
970 // Sort all potential spill candidates by weight.
971 std::sort(RegsWeights.begin(), RegsWeights.end(), WeightCompare());
972 minReg = RegsWeights[0].first;
973 minWeight = RegsWeights[0].second;
974 if (minWeight == HUGE_VALF) {
975 // All registers must have inf weight. Just grab one!
976 minReg = BestPhysReg ? BestPhysReg : *RC->allocation_order_begin(*mf_);
977 if (cur->weight == HUGE_VALF ||
978 li_->getApproximateInstructionCount(*cur) == 0) {
979 // Spill a physical register around defs and uses.
980 if (li_->spillPhysRegAroundRegDefsUses(*cur, minReg, *vrm_)) {
981 DowngradedRegs.clear();
982 assignRegOrStackSlotAtInterval(cur);
984 cerr << "Ran out of registers during register allocation!\n";
991 // Find up to 3 registers to consider as spill candidates.
992 unsigned LastCandidate = RegsWeights.size() >= 3 ? 3 : 1;
993 while (LastCandidate > 1) {
994 if (weightsAreClose(RegsWeights[LastCandidate-1].second, minWeight))
999 DOUT << "\t\tregister(s) with min weight(s): ";
1000 DEBUG(for (unsigned i = 0; i != LastCandidate; ++i)
1001 DOUT << tri_->getName(RegsWeights[i].first)
1002 << " (" << RegsWeights[i].second << ")\n");
1004 // If the current has the minimum weight, we need to spill it and
1005 // add any added intervals back to unhandled, and restart
1007 if (cur->weight != HUGE_VALF && cur->weight <= minWeight) {
1008 DOUT << "\t\t\tspilling(c): " << *cur << '\n';
1010 SmallVector<LiveInterval*, 8> spillIs;
1011 std::vector<LiveInterval*> added =
1012 li_->addIntervalsForSpills(*cur, spillIs, loopInfo, *vrm_, SSWeight);
1013 std::sort(added.begin(), added.end(), LISorter());
1014 addStackInterval(cur, ls_, li_, SSWeight, *vrm_);
1016 return; // Early exit if all spills were folded.
1018 // Merge added with unhandled. Note that we have already sorted
1019 // intervals returned by addIntervalsForSpills by their starting
1021 // This also update the NextReloadMap. That is, it adds mapping from a
1022 // register defined by a reload from SS to the next reload from SS in the
1023 // same basic block.
1024 MachineBasicBlock *LastReloadMBB = 0;
1025 LiveInterval *LastReload = 0;
1026 int LastReloadSS = VirtRegMap::NO_STACK_SLOT;
1027 for (unsigned i = 0, e = added.size(); i != e; ++i) {
1028 LiveInterval *ReloadLi = added[i];
1029 if (ReloadLi->weight == HUGE_VALF &&
1030 li_->getApproximateInstructionCount(*ReloadLi) == 0) {
1031 unsigned ReloadIdx = ReloadLi->beginNumber();
1032 MachineBasicBlock *ReloadMBB = li_->getMBBFromIndex(ReloadIdx);
1033 int ReloadSS = vrm_->getStackSlot(ReloadLi->reg);
1034 if (LastReloadMBB == ReloadMBB && LastReloadSS == ReloadSS) {
1035 // Last reload of same SS is in the same MBB. We want to try to
1036 // allocate both reloads the same register and make sure the reg
1037 // isn't clobbered in between if at all possible.
1038 assert(LastReload->beginNumber() < ReloadIdx);
1039 NextReloadMap.insert(std::make_pair(LastReload->reg, ReloadLi->reg));
1041 LastReloadMBB = ReloadMBB;
1042 LastReload = ReloadLi;
1043 LastReloadSS = ReloadSS;
1045 unhandled_.push(ReloadLi);
1052 // Push the current interval back to unhandled since we are going
1053 // to re-run at least this iteration. Since we didn't modify it it
1054 // should go back right in the front of the list
1055 unhandled_.push(cur);
1057 assert(TargetRegisterInfo::isPhysicalRegister(minReg) &&
1058 "did not choose a register to spill?");
1060 // We spill all intervals aliasing the register with
1061 // minimum weight, rollback to the interval with the earliest
1062 // start point and let the linear scan algorithm run again
1063 SmallVector<LiveInterval*, 8> spillIs;
1065 // Determine which intervals have to be spilled.
1066 findIntervalsToSpill(cur, RegsWeights, LastCandidate, spillIs);
1068 // Set of spilled vregs (used later to rollback properly)
1069 SmallSet<unsigned, 8> spilled;
1071 // The earliest start of a Spilled interval indicates up to where
1072 // in handled we need to roll back
1073 unsigned earliestStart = cur->beginNumber();
1075 // Spill live intervals of virtual regs mapped to the physical register we
1076 // want to clear (and its aliases). We only spill those that overlap with the
1077 // current interval as the rest do not affect its allocation. we also keep
1078 // track of the earliest start of all spilled live intervals since this will
1079 // mark our rollback point.
1080 std::vector<LiveInterval*> added;
1081 while (!spillIs.empty()) {
1082 LiveInterval *sli = spillIs.back();
1084 DOUT << "\t\t\tspilling(a): " << *sli << '\n';
1085 earliestStart = std::min(earliestStart, sli->beginNumber());
1087 std::vector<LiveInterval*> newIs =
1088 li_->addIntervalsForSpills(*sli, spillIs, loopInfo, *vrm_, SSWeight);
1089 addStackInterval(sli, ls_, li_, SSWeight, *vrm_);
1090 std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
1091 spilled.insert(sli->reg);
1094 DOUT << "\t\trolling back to: " << earliestStart << '\n';
1096 // Scan handled in reverse order up to the earliest start of a
1097 // spilled live interval and undo each one, restoring the state of
1099 while (!handled_.empty()) {
1100 LiveInterval* i = handled_.back();
1101 // If this interval starts before t we are done.
1102 if (i->beginNumber() < earliestStart)
1104 DOUT << "\t\t\tundo changes for: " << *i << '\n';
1105 handled_.pop_back();
1107 // When undoing a live interval allocation we must know if it is active or
1108 // inactive to properly update the PhysRegTracker and the VirtRegMap.
1109 IntervalPtrs::iterator it;
1110 if ((it = FindIntervalInVector(active_, i)) != active_.end()) {
1112 assert(!TargetRegisterInfo::isPhysicalRegister(i->reg));
1113 if (!spilled.count(i->reg))
1115 prt_->delRegUse(vrm_->getPhys(i->reg));
1116 vrm_->clearVirt(i->reg);
1117 } else if ((it = FindIntervalInVector(inactive_, i)) != inactive_.end()) {
1118 inactive_.erase(it);
1119 assert(!TargetRegisterInfo::isPhysicalRegister(i->reg));
1120 if (!spilled.count(i->reg))
1122 vrm_->clearVirt(i->reg);
1124 assert(TargetRegisterInfo::isVirtualRegister(i->reg) &&
1125 "Can only allocate virtual registers!");
1126 vrm_->clearVirt(i->reg);
1130 DenseMap<unsigned, unsigned>::iterator ii = DowngradeMap.find(i->reg);
1131 if (ii == DowngradeMap.end())
1132 // It interval has a preference, it must be defined by a copy. Clear the
1133 // preference now since the source interval allocation may have been
1137 UpgradeRegister(ii->second);
1141 // Rewind the iterators in the active, inactive, and fixed lists back to the
1142 // point we reverted to.
1143 RevertVectorIteratorsTo(active_, earliestStart);
1144 RevertVectorIteratorsTo(inactive_, earliestStart);
1145 RevertVectorIteratorsTo(fixed_, earliestStart);
1147 // Scan the rest and undo each interval that expired after t and
1148 // insert it in active (the next iteration of the algorithm will
1149 // put it in inactive if required)
1150 for (unsigned i = 0, e = handled_.size(); i != e; ++i) {
1151 LiveInterval *HI = handled_[i];
1152 if (!HI->expiredAt(earliestStart) &&
1153 HI->expiredAt(cur->beginNumber())) {
1154 DOUT << "\t\t\tundo changes for: " << *HI << '\n';
1155 active_.push_back(std::make_pair(HI, HI->begin()));
1156 assert(!TargetRegisterInfo::isPhysicalRegister(HI->reg));
1157 prt_->addRegUse(vrm_->getPhys(HI->reg));
1161 // Merge added with unhandled.
1162 // This also update the NextReloadMap. That is, it adds mapping from a
1163 // register defined by a reload from SS to the next reload from SS in the
1164 // same basic block.
1165 MachineBasicBlock *LastReloadMBB = 0;
1166 LiveInterval *LastReload = 0;
1167 int LastReloadSS = VirtRegMap::NO_STACK_SLOT;
1168 std::sort(added.begin(), added.end(), LISorter());
1169 for (unsigned i = 0, e = added.size(); i != e; ++i) {
1170 LiveInterval *ReloadLi = added[i];
1171 if (ReloadLi->weight == HUGE_VALF &&
1172 li_->getApproximateInstructionCount(*ReloadLi) == 0) {
1173 unsigned ReloadIdx = ReloadLi->beginNumber();
1174 MachineBasicBlock *ReloadMBB = li_->getMBBFromIndex(ReloadIdx);
1175 int ReloadSS = vrm_->getStackSlot(ReloadLi->reg);
1176 if (LastReloadMBB == ReloadMBB && LastReloadSS == ReloadSS) {
1177 // Last reload of same SS is in the same MBB. We want to try to
1178 // allocate both reloads the same register and make sure the reg
1179 // isn't clobbered in between if at all possible.
1180 assert(LastReload->beginNumber() < ReloadIdx);
1181 NextReloadMap.insert(std::make_pair(LastReload->reg, ReloadLi->reg));
1183 LastReloadMBB = ReloadMBB;
1184 LastReload = ReloadLi;
1185 LastReloadSS = ReloadSS;
1187 unhandled_.push(ReloadLi);
1191 unsigned RALinScan::getFreePhysReg(const TargetRegisterClass *RC,
1192 unsigned MaxInactiveCount,
1193 SmallVector<unsigned, 256> &inactiveCounts,
1195 unsigned FreeReg = 0;
1196 unsigned FreeRegInactiveCount = 0;
1198 TargetRegisterClass::iterator I = RC->allocation_order_begin(*mf_);
1199 TargetRegisterClass::iterator E = RC->allocation_order_end(*mf_);
1200 assert(I != E && "No allocatable register in this register class!");
1202 // Scan for the first available register.
1203 for (; I != E; ++I) {
1205 // Ignore "downgraded" registers.
1206 if (SkipDGRegs && DowngradedRegs.count(Reg))
1208 if (prt_->isRegAvail(Reg)) {
1210 if (FreeReg < inactiveCounts.size())
1211 FreeRegInactiveCount = inactiveCounts[FreeReg];
1213 FreeRegInactiveCount = 0;
1218 // If there are no free regs, or if this reg has the max inactive count,
1219 // return this register.
1220 if (FreeReg == 0 || FreeRegInactiveCount == MaxInactiveCount)
1223 // Continue scanning the registers, looking for the one with the highest
1224 // inactive count. Alkis found that this reduced register pressure very
1225 // slightly on X86 (in rev 1.94 of this file), though this should probably be
1227 for (; I != E; ++I) {
1229 // Ignore "downgraded" registers.
1230 if (SkipDGRegs && DowngradedRegs.count(Reg))
1232 if (prt_->isRegAvail(Reg) && Reg < inactiveCounts.size() &&
1233 FreeRegInactiveCount < inactiveCounts[Reg]) {
1235 FreeRegInactiveCount = inactiveCounts[Reg];
1236 if (FreeRegInactiveCount == MaxInactiveCount)
1237 break; // We found the one with the max inactive count.
1244 /// getFreePhysReg - return a free physical register for this virtual register
1245 /// interval if we have one, otherwise return 0.
1246 unsigned RALinScan::getFreePhysReg(LiveInterval *cur) {
1247 SmallVector<unsigned, 256> inactiveCounts;
1248 unsigned MaxInactiveCount = 0;
1250 const TargetRegisterClass *RC = mri_->getRegClass(cur->reg);
1251 const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
1253 for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end();
1255 unsigned reg = i->first->reg;
1256 assert(TargetRegisterInfo::isVirtualRegister(reg) &&
1257 "Can only allocate virtual registers!");
1259 // If this is not in a related reg class to the register we're allocating,
1261 const TargetRegisterClass *RegRC = mri_->getRegClass(reg);
1262 if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader) {
1263 reg = vrm_->getPhys(reg);
1264 if (inactiveCounts.size() <= reg)
1265 inactiveCounts.resize(reg+1);
1266 ++inactiveCounts[reg];
1267 MaxInactiveCount = std::max(MaxInactiveCount, inactiveCounts[reg]);
1271 // If copy coalescer has assigned a "preferred" register, check if it's
1273 if (cur->preference) {
1274 DOUT << "(preferred: " << tri_->getName(cur->preference) << ") ";
1275 if (prt_->isRegAvail(cur->preference) &&
1276 RC->contains(cur->preference))
1277 return cur->preference;
1280 if (!DowngradedRegs.empty()) {
1281 unsigned FreeReg = getFreePhysReg(RC, MaxInactiveCount, inactiveCounts,
1286 return getFreePhysReg(RC, MaxInactiveCount, inactiveCounts, false);
1289 FunctionPass* llvm::createLinearScanRegisterAllocator() {
1290 return new RALinScan();