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_);
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 // Unfavor downgraded registers for spilling.
558 if (DowngradedRegs.count(reg))
560 Weights[reg] += weight;
561 Processed.insert(reg);
562 for (const unsigned* as = tri_->getAliasSet(reg); *as; ++as) {
563 Weights[*as] += weight;
564 Processed.insert(*as);
565 if (tri_->isSubRegister(*as, reg) &&
566 SuperAdded.insert(*as) &&
568 Supers.push_back(*as);
572 // If the alias is a super-register, and the super-register is in the
573 // register class we are trying to allocate. Then add the weight to all
574 // sub-registers of the super-register even if they are not aliases.
575 // e.g. allocating for GR32, bh is not used, updating bl spill weight.
576 // bl should get the same spill weight otherwise it will be choosen
577 // as a spill candidate since spilling bh doesn't make ebx available.
578 for (unsigned i = 0, e = Supers.size(); i != e; ++i) {
579 for (const unsigned *sr = tri_->getSubRegisters(Supers[i]); *sr; ++sr)
580 if (!Processed.count(*sr))
581 Weights[*sr] += weight;
586 RALinScan::IntervalPtrs::iterator
587 FindIntervalInVector(RALinScan::IntervalPtrs &IP, LiveInterval *LI) {
588 for (RALinScan::IntervalPtrs::iterator I = IP.begin(), E = IP.end();
590 if (I->first == LI) return I;
594 static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V, unsigned Point){
595 for (unsigned i = 0, e = V.size(); i != e; ++i) {
596 RALinScan::IntervalPtr &IP = V[i];
597 LiveInterval::iterator I = std::upper_bound(IP.first->begin(),
599 if (I != IP.first->begin()) --I;
604 /// addStackInterval - Create a LiveInterval for stack if the specified live
605 /// interval has been spilled.
606 static void addStackInterval(LiveInterval *cur, LiveStacks *ls_,
607 LiveIntervals *li_, float &Weight,
609 int SS = vrm_.getStackSlot(cur->reg);
610 if (SS == VirtRegMap::NO_STACK_SLOT)
612 LiveInterval &SI = ls_->getOrCreateInterval(SS);
616 if (SI.hasAtLeastOneValue())
617 VNI = SI.getValNumInfo(0);
619 VNI = SI.getNextValue(~0U, 0, ls_->getVNInfoAllocator());
621 LiveInterval &RI = li_->getInterval(cur->reg);
622 // FIXME: This may be overly conservative.
623 SI.MergeRangesInAsValue(RI, VNI);
626 /// getConflictWeight - Return the number of conflicts between cur
627 /// live interval and defs and uses of Reg weighted by loop depthes.
628 static float getConflictWeight(LiveInterval *cur, unsigned Reg,
630 MachineRegisterInfo *mri_,
631 const MachineLoopInfo *loopInfo) {
633 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(Reg),
634 E = mri_->reg_end(); I != E; ++I) {
635 MachineInstr *MI = &*I;
636 if (cur->liveAt(li_->getInstructionIndex(MI))) {
637 unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent());
638 Conflicts += powf(10.0f, (float)loopDepth);
644 /// findIntervalsToSpill - Determine the intervals to spill for the
645 /// specified interval. It's passed the physical registers whose spill
646 /// weight is the lowest among all the registers whose live intervals
647 /// conflict with the interval.
648 void RALinScan::findIntervalsToSpill(LiveInterval *cur,
649 std::vector<std::pair<unsigned,float> > &Candidates,
651 SmallVector<LiveInterval*, 8> &SpillIntervals) {
652 // We have figured out the *best* register to spill. But there are other
653 // registers that are pretty good as well (spill weight within 3%). Spill
654 // the one that has fewest defs and uses that conflict with cur.
655 float Conflicts[3] = { 0.0f, 0.0f, 0.0f };
656 SmallVector<LiveInterval*, 8> SLIs[3];
658 DOUT << "\tConsidering " << NumCands << " candidates: ";
659 DEBUG(for (unsigned i = 0; i != NumCands; ++i)
660 DOUT << tri_->getName(Candidates[i].first) << " ";
663 // Calculate the number of conflicts of each candidate.
664 for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
665 unsigned Reg = i->first->reg;
666 unsigned PhysReg = vrm_->getPhys(Reg);
667 if (!cur->overlapsFrom(*i->first, i->second))
669 for (unsigned j = 0; j < NumCands; ++j) {
670 unsigned Candidate = Candidates[j].first;
671 if (tri_->regsOverlap(PhysReg, Candidate)) {
673 Conflicts[j] += getConflictWeight(cur, Reg, li_, mri_, loopInfo);
674 SLIs[j].push_back(i->first);
679 for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end(); ++i){
680 unsigned Reg = i->first->reg;
681 unsigned PhysReg = vrm_->getPhys(Reg);
682 if (!cur->overlapsFrom(*i->first, i->second-1))
684 for (unsigned j = 0; j < NumCands; ++j) {
685 unsigned Candidate = Candidates[j].first;
686 if (tri_->regsOverlap(PhysReg, Candidate)) {
688 Conflicts[j] += getConflictWeight(cur, Reg, li_, mri_, loopInfo);
689 SLIs[j].push_back(i->first);
694 // Which is the best candidate?
695 unsigned BestCandidate = 0;
696 float MinConflicts = Conflicts[0];
697 for (unsigned i = 1; i != NumCands; ++i) {
698 if (Conflicts[i] < MinConflicts) {
700 MinConflicts = Conflicts[i];
704 std::copy(SLIs[BestCandidate].begin(), SLIs[BestCandidate].end(),
705 std::back_inserter(SpillIntervals));
709 struct WeightCompare {
710 typedef std::pair<unsigned, float> RegWeightPair;
711 bool operator()(const RegWeightPair &LHS, const RegWeightPair &RHS) const {
712 return LHS.second < RHS.second;
717 static bool weightsAreClose(float w1, float w2) {
721 float diff = w1 - w2;
722 if (diff <= 0.02f) // Within 0.02f
724 return (diff / w2) <= 0.05f; // Within 5%.
727 LiveInterval *RALinScan::hasNextReloadInterval(LiveInterval *cur) {
728 DenseMap<unsigned, unsigned>::iterator I = NextReloadMap.find(cur->reg);
729 if (I == NextReloadMap.end())
731 return &li_->getInterval(I->second);
734 void RALinScan::DowngradeRegister(LiveInterval *li, unsigned Reg) {
735 bool isNew = DowngradedRegs.insert(Reg);
736 isNew = isNew; // Silence compiler warning.
737 assert(isNew && "Multiple reloads holding the same register?");
738 DowngradeMap.insert(std::make_pair(li->reg, Reg));
739 for (const unsigned *AS = tri_->getAliasSet(Reg); *AS; ++AS) {
740 isNew = DowngradedRegs.insert(*AS);
741 isNew = isNew; // Silence compiler warning.
742 assert(isNew && "Multiple reloads holding the same register?");
743 DowngradeMap.insert(std::make_pair(li->reg, *AS));
748 void RALinScan::UpgradeRegister(unsigned Reg) {
750 DowngradedRegs.erase(Reg);
751 for (const unsigned *AS = tri_->getAliasSet(Reg); *AS; ++AS)
752 DowngradedRegs.erase(*AS);
758 bool operator()(LiveInterval* A, LiveInterval* B) {
759 return A->beginNumber() < B->beginNumber();
764 /// assignRegOrStackSlotAtInterval - assign a register if one is available, or
766 void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
768 DOUT << "\tallocating current interval: ";
770 // This is an implicitly defined live interval, just assign any register.
771 const TargetRegisterClass *RC = mri_->getRegClass(cur->reg);
773 unsigned physReg = cur->preference;
775 physReg = *RC->allocation_order_begin(*mf_);
776 DOUT << tri_->getName(physReg) << '\n';
777 // Note the register is not really in use.
778 vrm_->assignVirt2Phys(cur->reg, physReg);
782 PhysRegTracker backupPrt = *prt_;
784 std::vector<std::pair<unsigned, float> > SpillWeightsToAdd;
785 unsigned StartPosition = cur->beginNumber();
786 const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
788 // If start of this live interval is defined by a move instruction and its
789 // source is assigned a physical register that is compatible with the target
790 // register class, then we should try to assign it the same register.
791 // This can happen when the move is from a larger register class to a smaller
792 // one, e.g. X86::mov32to32_. These move instructions are not coalescable.
793 if (!cur->preference && cur->hasAtLeastOneValue()) {
794 VNInfo *vni = cur->begin()->valno;
795 if (vni->def && vni->def != ~1U && vni->def != ~0U) {
796 MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
797 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
799 tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubReg, DstSubReg)) {
801 if (TargetRegisterInfo::isPhysicalRegister(SrcReg))
803 else if (vrm_->isAssignedReg(SrcReg))
804 Reg = vrm_->getPhys(SrcReg);
805 if (Reg && allocatableRegs_[Reg] && RC->contains(Reg))
806 cur->preference = Reg;
811 // for every interval in inactive we overlap with, mark the
812 // register as not free and update spill weights.
813 for (IntervalPtrs::const_iterator i = inactive_.begin(),
814 e = inactive_.end(); i != e; ++i) {
815 unsigned Reg = i->first->reg;
816 assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
817 "Can only allocate virtual registers!");
818 const TargetRegisterClass *RegRC = mri_->getRegClass(Reg);
819 // If this is not in a related reg class to the register we're allocating,
821 if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader &&
822 cur->overlapsFrom(*i->first, i->second-1)) {
823 Reg = vrm_->getPhys(Reg);
824 prt_->addRegUse(Reg);
825 SpillWeightsToAdd.push_back(std::make_pair(Reg, i->first->weight));
829 // Speculatively check to see if we can get a register right now. If not,
830 // we know we won't be able to by adding more constraints. If so, we can
831 // check to see if it is valid. Doing an exhaustive search of the fixed_ list
832 // is very bad (it contains all callee clobbered registers for any functions
833 // with a call), so we want to avoid doing that if possible.
834 unsigned physReg = getFreePhysReg(cur);
835 unsigned BestPhysReg = physReg;
837 // We got a register. However, if it's in the fixed_ list, we might
838 // conflict with it. Check to see if we conflict with it or any of its
840 SmallSet<unsigned, 8> RegAliases;
841 for (const unsigned *AS = tri_->getAliasSet(physReg); *AS; ++AS)
842 RegAliases.insert(*AS);
844 bool ConflictsWithFixed = false;
845 for (unsigned i = 0, e = fixed_.size(); i != e; ++i) {
846 IntervalPtr &IP = fixed_[i];
847 if (physReg == IP.first->reg || RegAliases.count(IP.first->reg)) {
848 // Okay, this reg is on the fixed list. Check to see if we actually
850 LiveInterval *I = IP.first;
851 if (I->endNumber() > StartPosition) {
852 LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition);
854 if (II != I->begin() && II->start > StartPosition)
856 if (cur->overlapsFrom(*I, II)) {
857 ConflictsWithFixed = true;
864 // Okay, the register picked by our speculative getFreePhysReg call turned
865 // out to be in use. Actually add all of the conflicting fixed registers to
866 // prt so we can do an accurate query.
867 if (ConflictsWithFixed) {
868 // For every interval in fixed we overlap with, mark the register as not
869 // free and update spill weights.
870 for (unsigned i = 0, e = fixed_.size(); i != e; ++i) {
871 IntervalPtr &IP = fixed_[i];
872 LiveInterval *I = IP.first;
874 const TargetRegisterClass *RegRC = OneClassForEachPhysReg[I->reg];
875 if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader &&
876 I->endNumber() > StartPosition) {
877 LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition);
879 if (II != I->begin() && II->start > StartPosition)
881 if (cur->overlapsFrom(*I, II)) {
882 unsigned reg = I->reg;
883 prt_->addRegUse(reg);
884 SpillWeightsToAdd.push_back(std::make_pair(reg, I->weight));
889 // Using the newly updated prt_ object, which includes conflicts in the
890 // future, see if there are any registers available.
891 physReg = getFreePhysReg(cur);
895 // Restore the physical register tracker, removing information about the
899 // if we find a free register, we are done: assign this virtual to
900 // the free physical register and add this interval to the active
903 DOUT << tri_->getName(physReg) << '\n';
904 vrm_->assignVirt2Phys(cur->reg, physReg);
905 prt_->addRegUse(physReg);
906 active_.push_back(std::make_pair(cur, cur->begin()));
907 handled_.push_back(cur);
909 // "Upgrade" the physical register since it has been allocated.
910 UpgradeRegister(physReg);
911 if (LiveInterval *NextReloadLI = hasNextReloadInterval(cur)) {
912 // "Downgrade" physReg to try to keep physReg from being allocated until
913 // the next reload from the same SS is allocated.
914 NextReloadLI->preference = physReg;
915 DowngradeRegister(cur, physReg);
919 DOUT << "no free registers\n";
921 // Compile the spill weights into an array that is better for scanning.
922 std::vector<float> SpillWeights(tri_->getNumRegs(), 0.0f);
923 for (std::vector<std::pair<unsigned, float> >::iterator
924 I = SpillWeightsToAdd.begin(), E = SpillWeightsToAdd.end(); I != E; ++I)
925 updateSpillWeights(SpillWeights, I->first, I->second, RC);
927 // for each interval in active, update spill weights.
928 for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
930 unsigned reg = i->first->reg;
931 assert(TargetRegisterInfo::isVirtualRegister(reg) &&
932 "Can only allocate virtual registers!");
933 reg = vrm_->getPhys(reg);
934 updateSpillWeights(SpillWeights, reg, i->first->weight, RC);
937 DOUT << "\tassigning stack slot at interval "<< *cur << ":\n";
939 // Find a register to spill.
940 float minWeight = HUGE_VALF;
941 unsigned minReg = 0; /*cur->preference*/; // Try the pref register first.
944 std::vector<std::pair<unsigned,float> > RegsWeights;
945 if (!minReg || SpillWeights[minReg] == HUGE_VALF)
946 for (TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_),
947 e = RC->allocation_order_end(*mf_); i != e; ++i) {
949 float regWeight = SpillWeights[reg];
950 if (minWeight > regWeight)
952 RegsWeights.push_back(std::make_pair(reg, regWeight));
955 // If we didn't find a register that is spillable, try aliases?
957 for (TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_),
958 e = RC->allocation_order_end(*mf_); i != e; ++i) {
960 // No need to worry about if the alias register size < regsize of RC.
961 // We are going to spill all registers that alias it anyway.
962 for (const unsigned* as = tri_->getAliasSet(reg); *as; ++as)
963 RegsWeights.push_back(std::make_pair(*as, SpillWeights[*as]));
967 // Sort all potential spill candidates by weight.
968 std::sort(RegsWeights.begin(), RegsWeights.end(), WeightCompare());
969 minReg = RegsWeights[0].first;
970 minWeight = RegsWeights[0].second;
971 if (minWeight == HUGE_VALF) {
972 // All registers must have inf weight. Just grab one!
973 minReg = BestPhysReg ? BestPhysReg : *RC->allocation_order_begin(*mf_);
974 if (cur->weight == HUGE_VALF ||
975 li_->getApproximateInstructionCount(*cur) == 0) {
976 // Spill a physical register around defs and uses.
977 if (li_->spillPhysRegAroundRegDefsUses(*cur, minReg, *vrm_)) {
978 DowngradedRegs.clear();
979 assignRegOrStackSlotAtInterval(cur);
981 cerr << "Ran out of registers during register allocation!\n";
988 // Find up to 3 registers to consider as spill candidates.
989 unsigned LastCandidate = RegsWeights.size() >= 3 ? 3 : 1;
990 while (LastCandidate > 1) {
991 if (weightsAreClose(RegsWeights[LastCandidate-1].second, minWeight))
996 DOUT << "\t\tregister(s) with min weight(s): ";
997 DEBUG(for (unsigned i = 0; i != LastCandidate; ++i)
998 DOUT << tri_->getName(RegsWeights[i].first)
999 << " (" << RegsWeights[i].second << ")\n");
1001 // If the current has the minimum weight, we need to spill it and
1002 // add any added intervals back to unhandled, and restart
1004 if (cur->weight != HUGE_VALF && cur->weight <= minWeight) {
1005 DOUT << "\t\t\tspilling(c): " << *cur << '\n';
1007 SmallVector<LiveInterval*, 8> spillIs;
1008 std::vector<LiveInterval*> added =
1009 li_->addIntervalsForSpills(*cur, spillIs, loopInfo, *vrm_, SSWeight);
1010 std::sort(added.begin(), added.end(), LISorter());
1011 addStackInterval(cur, ls_, li_, SSWeight, *vrm_);
1013 return; // Early exit if all spills were folded.
1015 // Merge added with unhandled. Note that we have already sorted
1016 // intervals returned by addIntervalsForSpills by their starting
1018 for (unsigned i = 0, e = added.size(); i != e; ++i)
1019 unhandled_.push(added[i]);
1025 // Push the current interval back to unhandled since we are going
1026 // to re-run at least this iteration. Since we didn't modify it it
1027 // should go back right in the front of the list
1028 unhandled_.push(cur);
1030 assert(TargetRegisterInfo::isPhysicalRegister(minReg) &&
1031 "did not choose a register to spill?");
1033 // We spill all intervals aliasing the register with
1034 // minimum weight, rollback to the interval with the earliest
1035 // start point and let the linear scan algorithm run again
1036 SmallVector<LiveInterval*, 8> spillIs;
1038 // Determine which intervals have to be spilled.
1039 findIntervalsToSpill(cur, RegsWeights, LastCandidate, spillIs);
1041 // Set of spilled vregs (used later to rollback properly)
1042 SmallSet<unsigned, 8> spilled;
1044 // The earliest start of a Spilled interval indicates up to where
1045 // in handled we need to roll back
1046 unsigned earliestStart = cur->beginNumber();
1048 // Spill live intervals of virtual regs mapped to the physical register we
1049 // want to clear (and its aliases). We only spill those that overlap with the
1050 // current interval as the rest do not affect its allocation. we also keep
1051 // track of the earliest start of all spilled live intervals since this will
1052 // mark our rollback point.
1053 std::vector<LiveInterval*> added;
1054 while (!spillIs.empty()) {
1055 LiveInterval *sli = spillIs.back();
1057 DOUT << "\t\t\tspilling(a): " << *sli << '\n';
1058 earliestStart = std::min(earliestStart, sli->beginNumber());
1060 std::vector<LiveInterval*> newIs =
1061 li_->addIntervalsForSpills(*sli, spillIs, loopInfo, *vrm_, SSWeight);
1062 addStackInterval(sli, ls_, li_, SSWeight, *vrm_);
1063 std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
1064 spilled.insert(sli->reg);
1067 DOUT << "\t\trolling back to: " << earliestStart << '\n';
1069 // Scan handled in reverse order up to the earliest start of a
1070 // spilled live interval and undo each one, restoring the state of
1072 while (!handled_.empty()) {
1073 LiveInterval* i = handled_.back();
1074 // If this interval starts before t we are done.
1075 if (i->beginNumber() < earliestStart)
1077 DOUT << "\t\t\tundo changes for: " << *i << '\n';
1078 handled_.pop_back();
1080 // When undoing a live interval allocation we must know if it is active or
1081 // inactive to properly update the PhysRegTracker and the VirtRegMap.
1082 IntervalPtrs::iterator it;
1083 if ((it = FindIntervalInVector(active_, i)) != active_.end()) {
1085 assert(!TargetRegisterInfo::isPhysicalRegister(i->reg));
1086 if (!spilled.count(i->reg))
1088 prt_->delRegUse(vrm_->getPhys(i->reg));
1089 vrm_->clearVirt(i->reg);
1090 } else if ((it = FindIntervalInVector(inactive_, i)) != inactive_.end()) {
1091 inactive_.erase(it);
1092 assert(!TargetRegisterInfo::isPhysicalRegister(i->reg));
1093 if (!spilled.count(i->reg))
1095 vrm_->clearVirt(i->reg);
1097 assert(TargetRegisterInfo::isVirtualRegister(i->reg) &&
1098 "Can only allocate virtual registers!");
1099 vrm_->clearVirt(i->reg);
1103 DenseMap<unsigned, unsigned>::iterator ii = DowngradeMap.find(i->reg);
1104 if (ii == DowngradeMap.end())
1105 // It interval has a preference, it must be defined by a copy. Clear the
1106 // preference now since the source interval allocation may have been
1110 UpgradeRegister(ii->second);
1114 // Rewind the iterators in the active, inactive, and fixed lists back to the
1115 // point we reverted to.
1116 RevertVectorIteratorsTo(active_, earliestStart);
1117 RevertVectorIteratorsTo(inactive_, earliestStart);
1118 RevertVectorIteratorsTo(fixed_, earliestStart);
1120 // Scan the rest and undo each interval that expired after t and
1121 // insert it in active (the next iteration of the algorithm will
1122 // put it in inactive if required)
1123 for (unsigned i = 0, e = handled_.size(); i != e; ++i) {
1124 LiveInterval *HI = handled_[i];
1125 if (!HI->expiredAt(earliestStart) &&
1126 HI->expiredAt(cur->beginNumber())) {
1127 DOUT << "\t\t\tundo changes for: " << *HI << '\n';
1128 active_.push_back(std::make_pair(HI, HI->begin()));
1129 assert(!TargetRegisterInfo::isPhysicalRegister(HI->reg));
1130 prt_->addRegUse(vrm_->getPhys(HI->reg));
1134 // Merge added with unhandled.
1135 // This also update the NextReloadMap. That is, it adds mapping from a
1136 // register defined by a reload from SS to the next reload from SS in the
1137 // same basic block.
1138 MachineBasicBlock *LastReloadMBB = 0;
1139 LiveInterval *LastReload = 0;
1140 int LastReloadSS = VirtRegMap::NO_STACK_SLOT;
1141 std::sort(added.begin(), added.end(), LISorter());
1142 for (unsigned i = 0, e = added.size(); i != e; ++i) {
1143 LiveInterval *ReloadLi = added[i];
1144 if (ReloadLi->weight == HUGE_VALF &&
1145 li_->getApproximateInstructionCount(*ReloadLi) == 0) {
1146 unsigned ReloadIdx = ReloadLi->beginNumber();
1147 MachineBasicBlock *ReloadMBB = li_->getMBBFromIndex(ReloadIdx);
1148 int ReloadSS = vrm_->getStackSlot(ReloadLi->reg);
1149 if (LastReloadMBB == ReloadMBB && LastReloadSS == ReloadSS) {
1150 // Last reload of same SS is in the same MBB. We want to try to
1151 // allocate both reloads the same register and make sure the reg
1152 // isn't clobbered in between if at all possible.
1153 assert(LastReload->beginNumber() < ReloadIdx);
1154 NextReloadMap.insert(std::make_pair(LastReload->reg, ReloadLi->reg));
1156 LastReloadMBB = ReloadMBB;
1157 LastReload = ReloadLi;
1158 LastReloadSS = ReloadSS;
1160 unhandled_.push(ReloadLi);
1164 unsigned RALinScan::getFreePhysReg(const TargetRegisterClass *RC,
1165 unsigned MaxInactiveCount,
1166 SmallVector<unsigned, 256> &inactiveCounts,
1168 unsigned FreeReg = 0;
1169 unsigned FreeRegInactiveCount = 0;
1171 TargetRegisterClass::iterator I = RC->allocation_order_begin(*mf_);
1172 TargetRegisterClass::iterator E = RC->allocation_order_end(*mf_);
1173 assert(I != E && "No allocatable register in this register class!");
1175 // Scan for the first available register.
1176 for (; I != E; ++I) {
1178 // Ignore "downgraded" registers.
1179 if (SkipDGRegs && DowngradedRegs.count(Reg))
1181 if (prt_->isRegAvail(Reg)) {
1183 if (FreeReg < inactiveCounts.size())
1184 FreeRegInactiveCount = inactiveCounts[FreeReg];
1186 FreeRegInactiveCount = 0;
1191 // If there are no free regs, or if this reg has the max inactive count,
1192 // return this register.
1193 if (FreeReg == 0 || FreeRegInactiveCount == MaxInactiveCount)
1196 // Continue scanning the registers, looking for the one with the highest
1197 // inactive count. Alkis found that this reduced register pressure very
1198 // slightly on X86 (in rev 1.94 of this file), though this should probably be
1200 for (; I != E; ++I) {
1202 // Ignore "downgraded" registers.
1203 if (SkipDGRegs && DowngradedRegs.count(Reg))
1205 if (prt_->isRegAvail(Reg) && Reg < inactiveCounts.size() &&
1206 FreeRegInactiveCount < inactiveCounts[Reg]) {
1208 FreeRegInactiveCount = inactiveCounts[Reg];
1209 if (FreeRegInactiveCount == MaxInactiveCount)
1210 break; // We found the one with the max inactive count.
1217 /// getFreePhysReg - return a free physical register for this virtual register
1218 /// interval if we have one, otherwise return 0.
1219 unsigned RALinScan::getFreePhysReg(LiveInterval *cur) {
1220 SmallVector<unsigned, 256> inactiveCounts;
1221 unsigned MaxInactiveCount = 0;
1223 const TargetRegisterClass *RC = mri_->getRegClass(cur->reg);
1224 const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
1226 for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end();
1228 unsigned reg = i->first->reg;
1229 assert(TargetRegisterInfo::isVirtualRegister(reg) &&
1230 "Can only allocate virtual registers!");
1232 // If this is not in a related reg class to the register we're allocating,
1234 const TargetRegisterClass *RegRC = mri_->getRegClass(reg);
1235 if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader) {
1236 reg = vrm_->getPhys(reg);
1237 if (inactiveCounts.size() <= reg)
1238 inactiveCounts.resize(reg+1);
1239 ++inactiveCounts[reg];
1240 MaxInactiveCount = std::max(MaxInactiveCount, inactiveCounts[reg]);
1244 // If copy coalescer has assigned a "preferred" register, check if it's
1246 if (cur->preference) {
1247 if (prt_->isRegAvail(cur->preference) &&
1248 RC->contains(cur->preference)) {
1249 DOUT << "\t\tassigned the preferred register: "
1250 << tri_->getName(cur->preference) << "\n";
1251 return cur->preference;
1253 DOUT << "\t\tunable to assign the preferred register: "
1254 << tri_->getName(cur->preference) << "\n";
1257 if (!DowngradedRegs.empty()) {
1258 unsigned FreeReg = getFreePhysReg(RC, MaxInactiveCount, inactiveCounts,
1263 return getFreePhysReg(RC, MaxInactiveCount, inactiveCounts, false);
1266 FunctionPass* llvm::createLinearScanRegisterAllocator() {
1267 return new RALinScan();