1 //===-- RegAllocLinearScan.cpp - Linear Scan register allocator -----------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a linear scan register allocator.
12 //===----------------------------------------------------------------------===//
14 #define DEBUG_TYPE "regalloc"
15 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
16 #include "PhysRegTracker.h"
17 #include "VirtRegMap.h"
18 #include "llvm/Function.h"
19 #include "llvm/CodeGen/MachineFunctionPass.h"
20 #include "llvm/CodeGen/MachineInstr.h"
21 #include "llvm/CodeGen/Passes.h"
22 #include "llvm/CodeGen/RegAllocRegistry.h"
23 #include "llvm/CodeGen/RegisterCoalescer.h"
24 #include "llvm/CodeGen/SSARegMap.h"
25 #include "llvm/Target/MRegisterInfo.h"
26 #include "llvm/Target/TargetMachine.h"
27 #include "llvm/Target/TargetInstrInfo.h"
28 #include "llvm/ADT/EquivalenceClasses.h"
29 #include "llvm/ADT/Statistic.h"
30 #include "llvm/ADT/STLExtras.h"
31 #include "llvm/Support/Debug.h"
32 #include "llvm/Support/Compiler.h"
40 STATISTIC(NumIters , "Number of iterations performed");
41 STATISTIC(NumBacktracks, "Number of times we had to backtrack");
42 STATISTIC(NumCoalesce, "Number of copies coalesced");
44 static RegisterRegAlloc
45 linearscanRegAlloc("linearscan", " linear scan register allocator",
46 createLinearScanRegisterAllocator);
49 struct VISIBILITY_HIDDEN RALinScan : public MachineFunctionPass {
51 RALinScan() : MachineFunctionPass((intptr_t)&ID) {}
53 typedef std::pair<LiveInterval*, LiveInterval::iterator> IntervalPtr;
54 typedef std::vector<IntervalPtr> IntervalPtrs;
56 /// RelatedRegClasses - This structure is built the first time a function is
57 /// compiled, and keeps track of which register classes have registers that
58 /// belong to multiple classes or have aliases that are in other classes.
59 EquivalenceClasses<const TargetRegisterClass*> RelatedRegClasses;
60 std::map<unsigned, const TargetRegisterClass*> OneClassForEachPhysReg;
63 const TargetMachine* tm_;
64 const MRegisterInfo* mri_;
65 const TargetInstrInfo* tii_;
67 BitVector allocatableRegs_;
70 /// handled_ - Intervals are added to the handled_ set in the order of their
71 /// start value. This is uses for backtracking.
72 std::vector<LiveInterval*> handled_;
74 /// fixed_ - Intervals that correspond to machine registers.
78 /// active_ - Intervals that are currently being processed, and which have a
79 /// live range active for the current point.
82 /// inactive_ - Intervals that are currently being processed, but which have
83 /// a hold at the current point.
84 IntervalPtrs inactive_;
86 typedef std::priority_queue<LiveInterval*,
87 std::vector<LiveInterval*>,
88 greater_ptr<LiveInterval> > IntervalHeap;
89 IntervalHeap unhandled_;
90 std::auto_ptr<PhysRegTracker> prt_;
91 std::auto_ptr<VirtRegMap> vrm_;
92 std::auto_ptr<Spiller> spiller_;
95 virtual const char* getPassName() const {
96 return "Linear Scan Register Allocator";
99 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
100 AU.addRequired<LiveIntervals>();
101 // Make sure PassManager knows which analyses to make available
102 // to coalescing and which analyses coalescing invalidates.
103 AU.addRequiredTransitive<RegisterCoalescer>();
104 MachineFunctionPass::getAnalysisUsage(AU);
107 /// runOnMachineFunction - register allocate the whole function
108 bool runOnMachineFunction(MachineFunction&);
111 /// linearScan - the linear scan algorithm
114 /// initIntervalSets - initialize the interval sets.
116 void initIntervalSets();
118 /// processActiveIntervals - expire old intervals and move non-overlapping
119 /// ones to the inactive list.
120 void processActiveIntervals(unsigned CurPoint);
122 /// processInactiveIntervals - expire old intervals and move overlapping
123 /// ones to the active list.
124 void processInactiveIntervals(unsigned CurPoint);
126 /// assignRegOrStackSlotAtInterval - assign a register if one
127 /// is available, or spill.
128 void assignRegOrStackSlotAtInterval(LiveInterval* cur);
130 /// attemptTrivialCoalescing - If a simple interval is defined by a copy,
131 /// try allocate the definition the same register as the source register
132 /// if the register is not defined during live time of the interval. This
133 /// eliminate a copy. This is used to coalesce copies which were not
134 /// coalesced away before allocation either due to dest and src being in
135 /// different register classes or because the coalescer was overly
137 unsigned attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg);
140 /// register handling helpers
143 /// getFreePhysReg - return a free physical register for this virtual
144 /// register interval if we have one, otherwise return 0.
145 unsigned getFreePhysReg(LiveInterval* cur);
147 /// assignVirt2StackSlot - assigns this virtual register to a
148 /// stack slot. returns the stack slot
149 int assignVirt2StackSlot(unsigned virtReg);
151 void ComputeRelatedRegClasses();
153 template <typename ItTy>
154 void printIntervals(const char* const str, ItTy i, ItTy e) const {
155 if (str) DOUT << str << " intervals:\n";
156 for (; i != e; ++i) {
157 DOUT << "\t" << *i->first << " -> ";
158 unsigned reg = i->first->reg;
159 if (MRegisterInfo::isVirtualRegister(reg)) {
160 reg = vrm_->getPhys(reg);
162 DOUT << mri_->getName(reg) << '\n';
166 char RALinScan::ID = 0;
169 void RALinScan::ComputeRelatedRegClasses() {
170 const MRegisterInfo &MRI = *mri_;
172 // First pass, add all reg classes to the union, and determine at least one
173 // reg class that each register is in.
174 bool HasAliases = false;
175 for (MRegisterInfo::regclass_iterator RCI = MRI.regclass_begin(),
176 E = MRI.regclass_end(); RCI != E; ++RCI) {
177 RelatedRegClasses.insert(*RCI);
178 for (TargetRegisterClass::iterator I = (*RCI)->begin(), E = (*RCI)->end();
180 HasAliases = HasAliases || *MRI.getAliasSet(*I) != 0;
182 const TargetRegisterClass *&PRC = OneClassForEachPhysReg[*I];
184 // Already processed this register. Just make sure we know that
185 // multiple register classes share a register.
186 RelatedRegClasses.unionSets(PRC, *RCI);
193 // Second pass, now that we know conservatively what register classes each reg
194 // belongs to, add info about aliases. We don't need to do this for targets
195 // without register aliases.
197 for (std::map<unsigned, const TargetRegisterClass*>::iterator
198 I = OneClassForEachPhysReg.begin(), E = OneClassForEachPhysReg.end();
200 for (const unsigned *AS = MRI.getAliasSet(I->first); *AS; ++AS)
201 RelatedRegClasses.unionSets(I->second, OneClassForEachPhysReg[*AS]);
204 /// attemptTrivialCoalescing - If a simple interval is defined by a copy,
205 /// try allocate the definition the same register as the source register
206 /// if the register is not defined during live time of the interval. This
207 /// eliminate a copy. This is used to coalesce copies which were not
208 /// coalesced away before allocation either due to dest and src being in
209 /// different register classes or because the coalescer was overly
211 unsigned RALinScan::attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg) {
212 if ((cur.preference && cur.preference == Reg) || !cur.containsOneValue())
215 VNInfo *vni = cur.getValNumInfo(0);
216 if (!vni->def || vni->def == ~1U || vni->def == ~0U)
218 MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
219 unsigned SrcReg, DstReg;
220 if (!CopyMI || !tii_->isMoveInstr(*CopyMI, SrcReg, DstReg))
222 if (MRegisterInfo::isVirtualRegister(SrcReg))
223 if (!vrm_->isAssignedReg(SrcReg))
226 SrcReg = vrm_->getPhys(SrcReg);
230 const TargetRegisterClass *RC = regmap_->getRegClass(cur.reg);
231 if (!RC->contains(SrcReg))
235 if (!li_->conflictsWithPhysRegDef(cur, *vrm_, SrcReg)) {
236 DOUT << "Coalescing: " << cur << " -> " << mri_->getName(SrcReg) << '\n';
237 vrm_->clearVirt(cur.reg);
238 vrm_->assignVirt2Phys(cur.reg, SrcReg);
246 bool RALinScan::runOnMachineFunction(MachineFunction &fn) {
248 tm_ = &fn.getTarget();
249 mri_ = tm_->getRegisterInfo();
250 tii_ = tm_->getInstrInfo();
251 regmap_ = mf_->getSSARegMap();
252 allocatableRegs_ = mri_->getAllocatableSet(fn);
253 li_ = &getAnalysis<LiveIntervals>();
255 // We don't run the coalescer here because we have no reason to
256 // interact with it. If the coalescer requires interaction, it
257 // won't do anything. If it doesn't require interaction, we assume
258 // it was run as a separate pass.
260 // If this is the first function compiled, compute the related reg classes.
261 if (RelatedRegClasses.empty())
262 ComputeRelatedRegClasses();
264 if (!prt_.get()) prt_.reset(new PhysRegTracker(*mri_));
265 vrm_.reset(new VirtRegMap(*mf_));
266 if (!spiller_.get()) spiller_.reset(createSpiller());
272 // Rewrite spill code and update the PhysRegsUsed set.
273 spiller_->runOnMachineFunction(*mf_, *vrm_);
274 vrm_.reset(); // Free the VirtRegMap
276 while (!unhandled_.empty()) unhandled_.pop();
285 /// initIntervalSets - initialize the interval sets.
287 void RALinScan::initIntervalSets()
289 assert(unhandled_.empty() && fixed_.empty() &&
290 active_.empty() && inactive_.empty() &&
291 "interval sets should be empty on initialization");
293 for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
294 if (MRegisterInfo::isPhysicalRegister(i->second.reg)) {
295 mf_->setPhysRegUsed(i->second.reg);
296 fixed_.push_back(std::make_pair(&i->second, i->second.begin()));
298 unhandled_.push(&i->second);
302 void RALinScan::linearScan()
304 // linear scan algorithm
305 DOUT << "********** LINEAR SCAN **********\n";
306 DOUT << "********** Function: " << mf_->getFunction()->getName() << '\n';
308 DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end()));
310 while (!unhandled_.empty()) {
311 // pick the interval with the earliest start point
312 LiveInterval* cur = unhandled_.top();
315 DOUT << "\n*** CURRENT ***: " << *cur << '\n';
317 processActiveIntervals(cur->beginNumber());
318 processInactiveIntervals(cur->beginNumber());
320 assert(MRegisterInfo::isVirtualRegister(cur->reg) &&
321 "Can only allocate virtual registers!");
323 // Allocating a virtual register. try to find a free
324 // physical register or spill an interval (possibly this one) in order to
326 assignRegOrStackSlotAtInterval(cur);
328 DEBUG(printIntervals("active", active_.begin(), active_.end()));
329 DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
332 // expire any remaining active intervals
333 while (!active_.empty()) {
334 IntervalPtr &IP = active_.back();
335 unsigned reg = IP.first->reg;
336 DOUT << "\tinterval " << *IP.first << " expired\n";
337 assert(MRegisterInfo::isVirtualRegister(reg) &&
338 "Can only allocate virtual registers!");
339 reg = vrm_->getPhys(reg);
340 prt_->delRegUse(reg);
344 // expire any remaining inactive intervals
345 DEBUG(for (IntervalPtrs::reverse_iterator
346 i = inactive_.rbegin(); i != inactive_.rend(); ++i)
347 DOUT << "\tinterval " << *i->first << " expired\n");
350 // Add live-ins to every BB except for entry.
351 MachineFunction::iterator EntryMBB = mf_->begin();
352 SmallVector<MachineBasicBlock*, 8> LiveInMBBs;
353 for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
354 LiveInterval &cur = i->second;
356 if (MRegisterInfo::isPhysicalRegister(cur.reg))
358 else if (vrm_->isAssignedReg(cur.reg))
359 Reg = attemptTrivialCoalescing(cur, vrm_->getPhys(cur.reg));
362 for (LiveInterval::Ranges::const_iterator I = cur.begin(), E = cur.end();
364 const LiveRange &LR = *I;
365 if (li_->findLiveInMBBs(LR, LiveInMBBs)) {
366 for (unsigned i = 0, e = LiveInMBBs.size(); i != e; ++i)
367 if (LiveInMBBs[i] != EntryMBB)
368 LiveInMBBs[i]->addLiveIn(Reg);
377 /// processActiveIntervals - expire old intervals and move non-overlapping ones
378 /// to the inactive list.
379 void RALinScan::processActiveIntervals(unsigned CurPoint)
381 DOUT << "\tprocessing active intervals:\n";
383 for (unsigned i = 0, e = active_.size(); i != e; ++i) {
384 LiveInterval *Interval = active_[i].first;
385 LiveInterval::iterator IntervalPos = active_[i].second;
386 unsigned reg = Interval->reg;
388 IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
390 if (IntervalPos == Interval->end()) { // Remove expired intervals.
391 DOUT << "\t\tinterval " << *Interval << " expired\n";
392 assert(MRegisterInfo::isVirtualRegister(reg) &&
393 "Can only allocate virtual registers!");
394 reg = vrm_->getPhys(reg);
395 prt_->delRegUse(reg);
397 // Pop off the end of the list.
398 active_[i] = active_.back();
402 } else if (IntervalPos->start > CurPoint) {
403 // Move inactive intervals to inactive list.
404 DOUT << "\t\tinterval " << *Interval << " inactive\n";
405 assert(MRegisterInfo::isVirtualRegister(reg) &&
406 "Can only allocate virtual registers!");
407 reg = vrm_->getPhys(reg);
408 prt_->delRegUse(reg);
410 inactive_.push_back(std::make_pair(Interval, IntervalPos));
412 // Pop off the end of the list.
413 active_[i] = active_.back();
417 // Otherwise, just update the iterator position.
418 active_[i].second = IntervalPos;
423 /// processInactiveIntervals - expire old intervals and move overlapping
424 /// ones to the active list.
425 void RALinScan::processInactiveIntervals(unsigned CurPoint)
427 DOUT << "\tprocessing inactive intervals:\n";
429 for (unsigned i = 0, e = inactive_.size(); i != e; ++i) {
430 LiveInterval *Interval = inactive_[i].first;
431 LiveInterval::iterator IntervalPos = inactive_[i].second;
432 unsigned reg = Interval->reg;
434 IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
436 if (IntervalPos == Interval->end()) { // remove expired intervals.
437 DOUT << "\t\tinterval " << *Interval << " expired\n";
439 // Pop off the end of the list.
440 inactive_[i] = inactive_.back();
441 inactive_.pop_back();
443 } else if (IntervalPos->start <= CurPoint) {
444 // move re-activated intervals in active list
445 DOUT << "\t\tinterval " << *Interval << " active\n";
446 assert(MRegisterInfo::isVirtualRegister(reg) &&
447 "Can only allocate virtual registers!");
448 reg = vrm_->getPhys(reg);
449 prt_->addRegUse(reg);
451 active_.push_back(std::make_pair(Interval, IntervalPos));
453 // Pop off the end of the list.
454 inactive_[i] = inactive_.back();
455 inactive_.pop_back();
458 // Otherwise, just update the iterator position.
459 inactive_[i].second = IntervalPos;
464 /// updateSpillWeights - updates the spill weights of the specifed physical
465 /// register and its weight.
466 static void updateSpillWeights(std::vector<float> &Weights,
467 unsigned reg, float weight,
468 const MRegisterInfo *MRI) {
469 Weights[reg] += weight;
470 for (const unsigned* as = MRI->getAliasSet(reg); *as; ++as)
471 Weights[*as] += weight;
475 RALinScan::IntervalPtrs::iterator
476 FindIntervalInVector(RALinScan::IntervalPtrs &IP, LiveInterval *LI) {
477 for (RALinScan::IntervalPtrs::iterator I = IP.begin(), E = IP.end();
479 if (I->first == LI) return I;
483 static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V, unsigned Point){
484 for (unsigned i = 0, e = V.size(); i != e; ++i) {
485 RALinScan::IntervalPtr &IP = V[i];
486 LiveInterval::iterator I = std::upper_bound(IP.first->begin(),
488 if (I != IP.first->begin()) --I;
493 /// assignRegOrStackSlotAtInterval - assign a register if one is available, or
495 void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
497 DOUT << "\tallocating current interval: ";
499 PhysRegTracker backupPrt = *prt_;
501 std::vector<std::pair<unsigned, float> > SpillWeightsToAdd;
502 unsigned StartPosition = cur->beginNumber();
503 const TargetRegisterClass *RC = regmap_->getRegClass(cur->reg);
504 const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
506 // If this live interval is defined by a move instruction and its source is
507 // assigned a physical register that is compatible with the target register
508 // class, then we should try to assign it the same register.
509 // This can happen when the move is from a larger register class to a smaller
510 // one, e.g. X86::mov32to32_. These move instructions are not coalescable.
511 if (!cur->preference && cur->containsOneValue()) {
512 VNInfo *vni = cur->getValNumInfo(0);
513 if (vni->def && vni->def != ~1U && vni->def != ~0U) {
514 MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
515 unsigned SrcReg, DstReg;
516 if (tii_->isMoveInstr(*CopyMI, SrcReg, DstReg)) {
518 if (MRegisterInfo::isPhysicalRegister(SrcReg))
520 else if (vrm_->isAssignedReg(SrcReg))
521 Reg = vrm_->getPhys(SrcReg);
522 if (Reg && allocatableRegs_[Reg] && RC->contains(Reg))
523 cur->preference = Reg;
528 // for every interval in inactive we overlap with, mark the
529 // register as not free and update spill weights.
530 for (IntervalPtrs::const_iterator i = inactive_.begin(),
531 e = inactive_.end(); i != e; ++i) {
532 unsigned Reg = i->first->reg;
533 assert(MRegisterInfo::isVirtualRegister(Reg) &&
534 "Can only allocate virtual registers!");
535 const TargetRegisterClass *RegRC = regmap_->getRegClass(Reg);
536 // If this is not in a related reg class to the register we're allocating,
538 if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader &&
539 cur->overlapsFrom(*i->first, i->second-1)) {
540 Reg = vrm_->getPhys(Reg);
541 prt_->addRegUse(Reg);
542 SpillWeightsToAdd.push_back(std::make_pair(Reg, i->first->weight));
546 // Speculatively check to see if we can get a register right now. If not,
547 // we know we won't be able to by adding more constraints. If so, we can
548 // check to see if it is valid. Doing an exhaustive search of the fixed_ list
549 // is very bad (it contains all callee clobbered registers for any functions
550 // with a call), so we want to avoid doing that if possible.
551 unsigned physReg = getFreePhysReg(cur);
553 // We got a register. However, if it's in the fixed_ list, we might
554 // conflict with it. Check to see if we conflict with it or any of its
556 SmallSet<unsigned, 8> RegAliases;
557 for (const unsigned *AS = mri_->getAliasSet(physReg); *AS; ++AS)
558 RegAliases.insert(*AS);
560 bool ConflictsWithFixed = false;
561 for (unsigned i = 0, e = fixed_.size(); i != e; ++i) {
562 IntervalPtr &IP = fixed_[i];
563 if (physReg == IP.first->reg || RegAliases.count(IP.first->reg)) {
564 // Okay, this reg is on the fixed list. Check to see if we actually
566 LiveInterval *I = IP.first;
567 if (I->endNumber() > StartPosition) {
568 LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition);
570 if (II != I->begin() && II->start > StartPosition)
572 if (cur->overlapsFrom(*I, II)) {
573 ConflictsWithFixed = true;
580 // Okay, the register picked by our speculative getFreePhysReg call turned
581 // out to be in use. Actually add all of the conflicting fixed registers to
582 // prt so we can do an accurate query.
583 if (ConflictsWithFixed) {
584 // For every interval in fixed we overlap with, mark the register as not
585 // free and update spill weights.
586 for (unsigned i = 0, e = fixed_.size(); i != e; ++i) {
587 IntervalPtr &IP = fixed_[i];
588 LiveInterval *I = IP.first;
590 const TargetRegisterClass *RegRC = OneClassForEachPhysReg[I->reg];
591 if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader &&
592 I->endNumber() > StartPosition) {
593 LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition);
595 if (II != I->begin() && II->start > StartPosition)
597 if (cur->overlapsFrom(*I, II)) {
598 unsigned reg = I->reg;
599 prt_->addRegUse(reg);
600 SpillWeightsToAdd.push_back(std::make_pair(reg, I->weight));
605 // Using the newly updated prt_ object, which includes conflicts in the
606 // future, see if there are any registers available.
607 physReg = getFreePhysReg(cur);
611 // Restore the physical register tracker, removing information about the
615 // if we find a free register, we are done: assign this virtual to
616 // the free physical register and add this interval to the active
619 DOUT << mri_->getName(physReg) << '\n';
620 vrm_->assignVirt2Phys(cur->reg, physReg);
621 prt_->addRegUse(physReg);
622 active_.push_back(std::make_pair(cur, cur->begin()));
623 handled_.push_back(cur);
626 DOUT << "no free registers\n";
628 // Compile the spill weights into an array that is better for scanning.
629 std::vector<float> SpillWeights(mri_->getNumRegs(), 0.0);
630 for (std::vector<std::pair<unsigned, float> >::iterator
631 I = SpillWeightsToAdd.begin(), E = SpillWeightsToAdd.end(); I != E; ++I)
632 updateSpillWeights(SpillWeights, I->first, I->second, mri_);
634 // for each interval in active, update spill weights.
635 for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
637 unsigned reg = i->first->reg;
638 assert(MRegisterInfo::isVirtualRegister(reg) &&
639 "Can only allocate virtual registers!");
640 reg = vrm_->getPhys(reg);
641 updateSpillWeights(SpillWeights, reg, i->first->weight, mri_);
644 DOUT << "\tassigning stack slot at interval "<< *cur << ":\n";
646 // Find a register to spill.
647 float minWeight = HUGE_VALF;
648 unsigned minReg = cur->preference; // Try the preferred register first.
650 if (!minReg || SpillWeights[minReg] == HUGE_VALF)
651 for (TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_),
652 e = RC->allocation_order_end(*mf_); i != e; ++i) {
654 if (minWeight > SpillWeights[reg]) {
655 minWeight = SpillWeights[reg];
660 // If we didn't find a register that is spillable, try aliases?
662 for (TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_),
663 e = RC->allocation_order_end(*mf_); i != e; ++i) {
665 // No need to worry about if the alias register size < regsize of RC.
666 // We are going to spill all registers that alias it anyway.
667 for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as) {
668 if (minWeight > SpillWeights[*as]) {
669 minWeight = SpillWeights[*as];
675 // All registers must have inf weight. Just grab one!
677 minReg = *RC->allocation_order_begin(*mf_);
680 DOUT << "\t\tregister with min weight: "
681 << mri_->getName(minReg) << " (" << minWeight << ")\n";
683 // if the current has the minimum weight, we need to spill it and
684 // add any added intervals back to unhandled, and restart
686 if (cur->weight != HUGE_VALF && cur->weight <= minWeight) {
687 DOUT << "\t\t\tspilling(c): " << *cur << '\n';
688 std::vector<LiveInterval*> added =
689 li_->addIntervalsForSpills(*cur, *vrm_);
691 return; // Early exit if all spills were folded.
693 // Merge added with unhandled. Note that we know that
694 // addIntervalsForSpills returns intervals sorted by their starting
696 for (unsigned i = 0, e = added.size(); i != e; ++i)
697 unhandled_.push(added[i]);
703 // push the current interval back to unhandled since we are going
704 // to re-run at least this iteration. Since we didn't modify it it
705 // should go back right in the front of the list
706 unhandled_.push(cur);
708 // otherwise we spill all intervals aliasing the register with
709 // minimum weight, rollback to the interval with the earliest
710 // start point and let the linear scan algorithm run again
711 std::vector<LiveInterval*> added;
712 assert(MRegisterInfo::isPhysicalRegister(minReg) &&
713 "did not choose a register to spill?");
714 BitVector toSpill(mri_->getNumRegs());
716 // We are going to spill minReg and all its aliases.
717 toSpill[minReg] = true;
718 for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
721 // the earliest start of a spilled interval indicates up to where
722 // in handled we need to roll back
723 unsigned earliestStart = cur->beginNumber();
725 // set of spilled vregs (used later to rollback properly)
726 SmallSet<unsigned, 32> spilled;
728 // spill live intervals of virtual regs mapped to the physical register we
729 // want to clear (and its aliases). We only spill those that overlap with the
730 // current interval as the rest do not affect its allocation. we also keep
731 // track of the earliest start of all spilled live intervals since this will
732 // mark our rollback point.
733 for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
734 unsigned reg = i->first->reg;
735 if (//MRegisterInfo::isVirtualRegister(reg) &&
736 toSpill[vrm_->getPhys(reg)] &&
737 cur->overlapsFrom(*i->first, i->second)) {
738 DOUT << "\t\t\tspilling(a): " << *i->first << '\n';
739 earliestStart = std::min(earliestStart, i->first->beginNumber());
740 std::vector<LiveInterval*> newIs =
741 li_->addIntervalsForSpills(*i->first, *vrm_);
742 std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
746 for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end(); ++i){
747 unsigned reg = i->first->reg;
748 if (//MRegisterInfo::isVirtualRegister(reg) &&
749 toSpill[vrm_->getPhys(reg)] &&
750 cur->overlapsFrom(*i->first, i->second-1)) {
751 DOUT << "\t\t\tspilling(i): " << *i->first << '\n';
752 earliestStart = std::min(earliestStart, i->first->beginNumber());
753 std::vector<LiveInterval*> newIs =
754 li_->addIntervalsForSpills(*i->first, *vrm_);
755 std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
760 DOUT << "\t\trolling back to: " << earliestStart << '\n';
762 // Scan handled in reverse order up to the earliest start of a
763 // spilled live interval and undo each one, restoring the state of
765 while (!handled_.empty()) {
766 LiveInterval* i = handled_.back();
767 // If this interval starts before t we are done.
768 if (i->beginNumber() < earliestStart)
770 DOUT << "\t\t\tundo changes for: " << *i << '\n';
773 // When undoing a live interval allocation we must know if it is active or
774 // inactive to properly update the PhysRegTracker and the VirtRegMap.
775 IntervalPtrs::iterator it;
776 if ((it = FindIntervalInVector(active_, i)) != active_.end()) {
778 assert(!MRegisterInfo::isPhysicalRegister(i->reg));
779 if (!spilled.count(i->reg))
781 prt_->delRegUse(vrm_->getPhys(i->reg));
782 vrm_->clearVirt(i->reg);
783 } else if ((it = FindIntervalInVector(inactive_, i)) != inactive_.end()) {
785 assert(!MRegisterInfo::isPhysicalRegister(i->reg));
786 if (!spilled.count(i->reg))
788 vrm_->clearVirt(i->reg);
790 assert(MRegisterInfo::isVirtualRegister(i->reg) &&
791 "Can only allocate virtual registers!");
792 vrm_->clearVirt(i->reg);
796 // It interval has a preference, it must be defined by a copy. Clear the
797 // preference now since the source interval allocation may have been undone
802 // Rewind the iterators in the active, inactive, and fixed lists back to the
803 // point we reverted to.
804 RevertVectorIteratorsTo(active_, earliestStart);
805 RevertVectorIteratorsTo(inactive_, earliestStart);
806 RevertVectorIteratorsTo(fixed_, earliestStart);
808 // scan the rest and undo each interval that expired after t and
809 // insert it in active (the next iteration of the algorithm will
810 // put it in inactive if required)
811 for (unsigned i = 0, e = handled_.size(); i != e; ++i) {
812 LiveInterval *HI = handled_[i];
813 if (!HI->expiredAt(earliestStart) &&
814 HI->expiredAt(cur->beginNumber())) {
815 DOUT << "\t\t\tundo changes for: " << *HI << '\n';
816 active_.push_back(std::make_pair(HI, HI->begin()));
817 assert(!MRegisterInfo::isPhysicalRegister(HI->reg));
818 prt_->addRegUse(vrm_->getPhys(HI->reg));
822 // merge added with unhandled
823 for (unsigned i = 0, e = added.size(); i != e; ++i)
824 unhandled_.push(added[i]);
827 /// getFreePhysReg - return a free physical register for this virtual register
828 /// interval if we have one, otherwise return 0.
829 unsigned RALinScan::getFreePhysReg(LiveInterval *cur) {
830 std::vector<unsigned> inactiveCounts(mri_->getNumRegs(), 0);
831 unsigned MaxInactiveCount = 0;
833 const TargetRegisterClass *RC = regmap_->getRegClass(cur->reg);
834 const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
836 for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end();
838 unsigned reg = i->first->reg;
839 assert(MRegisterInfo::isVirtualRegister(reg) &&
840 "Can only allocate virtual registers!");
842 // If this is not in a related reg class to the register we're allocating,
844 const TargetRegisterClass *RegRC = regmap_->getRegClass(reg);
845 if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader) {
846 reg = vrm_->getPhys(reg);
847 ++inactiveCounts[reg];
848 MaxInactiveCount = std::max(MaxInactiveCount, inactiveCounts[reg]);
852 unsigned FreeReg = 0;
853 unsigned FreeRegInactiveCount = 0;
855 // If copy coalescer has assigned a "preferred" register, check if it's
858 if (prt_->isRegAvail(cur->preference)) {
859 DOUT << "\t\tassigned the preferred register: "
860 << mri_->getName(cur->preference) << "\n";
861 return cur->preference;
863 DOUT << "\t\tunable to assign the preferred register: "
864 << mri_->getName(cur->preference) << "\n";
866 // Scan for the first available register.
867 TargetRegisterClass::iterator I = RC->allocation_order_begin(*mf_);
868 TargetRegisterClass::iterator E = RC->allocation_order_end(*mf_);
870 if (prt_->isRegAvail(*I)) {
872 FreeRegInactiveCount = inactiveCounts[FreeReg];
876 // If there are no free regs, or if this reg has the max inactive count,
877 // return this register.
878 if (FreeReg == 0 || FreeRegInactiveCount == MaxInactiveCount) return FreeReg;
880 // Continue scanning the registers, looking for the one with the highest
881 // inactive count. Alkis found that this reduced register pressure very
882 // slightly on X86 (in rev 1.94 of this file), though this should probably be
884 for (; I != E; ++I) {
886 if (prt_->isRegAvail(Reg) && FreeRegInactiveCount < inactiveCounts[Reg]) {
888 FreeRegInactiveCount = inactiveCounts[Reg];
889 if (FreeRegInactiveCount == MaxInactiveCount)
890 break; // We found the one with the max inactive count.
897 FunctionPass* llvm::createLinearScanRegisterAllocator() {
898 return new RALinScan();