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/Function.h"
16 #include "llvm/CodeGen/MachineFunctionPass.h"
17 #include "llvm/CodeGen/MachineInstr.h"
18 #include "llvm/CodeGen/Passes.h"
19 #include "llvm/CodeGen/SSARegMap.h"
20 #include "llvm/Target/MRegisterInfo.h"
21 #include "llvm/Target/TargetMachine.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/ADT/STLExtras.h"
25 #include "LiveIntervalAnalysis.h"
26 #include "PhysRegTracker.h"
27 #include "VirtRegMap.h"
36 Statistic<double> efficiency
37 ("regalloc", "Ratio of intervals processed over total intervals");
38 Statistic<> NumBacktracks("regalloc", "Number of times we had to backtrack");
40 static unsigned numIterations = 0;
41 static unsigned numIntervals = 0;
43 struct RA : public MachineFunctionPass {
44 typedef std::pair<LiveInterval*, LiveInterval::iterator> IntervalPtr;
45 typedef std::vector<IntervalPtr> IntervalPtrs;
48 const TargetMachine* tm_;
49 const MRegisterInfo* mri_;
53 /// handled_ - Intervals are added to the handled_ set in the order of their
54 /// start value. This is uses for backtracking.
55 std::vector<LiveInterval*> handled_;
57 /// fixed_ - Intervals that correspond to machine registers.
61 /// active_ - Intervals that are currently being processed, and which have a
62 /// live range active for the current point.
65 /// inactive_ - Intervals that are currently being processed, but which have
66 /// a hold at the current point.
67 IntervalPtrs inactive_;
69 typedef std::priority_queue<LiveInterval*,
70 std::vector<LiveInterval*>,
71 greater_ptr<LiveInterval> > IntervalHeap;
72 IntervalHeap unhandled_;
73 std::auto_ptr<PhysRegTracker> prt_;
74 std::auto_ptr<VirtRegMap> vrm_;
75 std::auto_ptr<Spiller> spiller_;
78 virtual const char* getPassName() const {
79 return "Linear Scan Register Allocator";
82 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
83 AU.addRequired<LiveIntervals>();
84 MachineFunctionPass::getAnalysisUsage(AU);
87 /// runOnMachineFunction - register allocate the whole function
88 bool runOnMachineFunction(MachineFunction&);
91 /// linearScan - the linear scan algorithm
94 /// initIntervalSets - initialize the interval sets.
96 void initIntervalSets();
98 /// processActiveIntervals - expire old intervals and move non-overlapping
99 /// ones to the inactive list.
100 void processActiveIntervals(unsigned CurPoint);
102 /// processInactiveIntervals - expire old intervals and move overlapping
103 /// ones to the active list.
104 void processInactiveIntervals(unsigned CurPoint);
106 /// assignRegOrStackSlotAtInterval - assign a register if one
107 /// is available, or spill.
108 void assignRegOrStackSlotAtInterval(LiveInterval* cur);
111 /// register handling helpers
114 /// getFreePhysReg - return a free physical register for this virtual
115 /// register interval if we have one, otherwise return 0.
116 unsigned getFreePhysReg(LiveInterval* cur);
118 /// assignVirt2StackSlot - assigns this virtual register to a
119 /// stack slot. returns the stack slot
120 int assignVirt2StackSlot(unsigned virtReg);
122 template <typename ItTy>
123 void printIntervals(const char* const str, ItTy i, ItTy e) const {
124 if (str) std::cerr << str << " intervals:\n";
125 for (; i != e; ++i) {
126 std::cerr << "\t" << *i->first << " -> ";
127 unsigned reg = i->first->reg;
128 if (MRegisterInfo::isVirtualRegister(reg)) {
129 reg = vrm_->getPhys(reg);
131 std::cerr << mri_->getName(reg) << '\n';
137 bool RA::runOnMachineFunction(MachineFunction &fn) {
139 tm_ = &fn.getTarget();
140 mri_ = tm_->getRegisterInfo();
141 li_ = &getAnalysis<LiveIntervals>();
143 PhysRegsUsed = new bool[mri_->getNumRegs()];
144 std::fill(PhysRegsUsed, PhysRegsUsed+mri_->getNumRegs(), false);
145 fn.setUsedPhysRegs(PhysRegsUsed);
147 if (!prt_.get()) prt_.reset(new PhysRegTracker(*mri_));
148 vrm_.reset(new VirtRegMap(*mf_));
149 if (!spiller_.get()) spiller_.reset(createSpiller());
155 // Rewrite spill code and update the PhysRegsUsed set.
156 spiller_->runOnMachineFunction(*mf_, *vrm_);
158 vrm_.reset(); // Free the VirtRegMap
161 while (!unhandled_.empty()) unhandled_.pop();
170 /// initIntervalSets - initialize the interval sets.
172 void RA::initIntervalSets()
174 assert(unhandled_.empty() && fixed_.empty() &&
175 active_.empty() && inactive_.empty() &&
176 "interval sets should be empty on initialization");
178 for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
179 if (MRegisterInfo::isPhysicalRegister(i->second.reg)) {
180 PhysRegsUsed[i->second.reg] = true;
181 fixed_.push_back(std::make_pair(&i->second, i->second.begin()));
183 unhandled_.push(&i->second);
187 void RA::linearScan()
189 // linear scan algorithm
190 DEBUG(std::cerr << "********** LINEAR SCAN **********\n");
191 DEBUG(std::cerr << "********** Function: "
192 << mf_->getFunction()->getName() << '\n');
194 // DEBUG(printIntervals("unhandled", unhandled_.begin(), unhandled_.end()));
195 DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end()));
196 DEBUG(printIntervals("active", active_.begin(), active_.end()));
197 DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
199 while (!unhandled_.empty()) {
200 // pick the interval with the earliest start point
201 LiveInterval* cur = unhandled_.top();
204 DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n');
206 processActiveIntervals(cur->beginNumber());
207 processInactiveIntervals(cur->beginNumber());
209 assert(MRegisterInfo::isVirtualRegister(cur->reg) &&
210 "Can only allocate virtual registers!");
212 // Allocating a virtual register. try to find a free
213 // physical register or spill an interval (possibly this one) in order to
215 assignRegOrStackSlotAtInterval(cur);
217 DEBUG(printIntervals("active", active_.begin(), active_.end()));
218 DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
220 numIntervals += li_->getNumIntervals();
221 efficiency = double(numIterations) / double(numIntervals);
223 // expire any remaining active intervals
224 for (IntervalPtrs::reverse_iterator
225 i = active_.rbegin(); i != active_.rend(); ) {
226 unsigned reg = i->first->reg;
227 DEBUG(std::cerr << "\tinterval " << *i->first << " expired\n");
228 assert(MRegisterInfo::isVirtualRegister(reg) &&
229 "Can only allocate virtual registers!");
230 reg = vrm_->getPhys(reg);
231 prt_->delRegUse(reg);
232 i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1));
235 // expire any remaining inactive intervals
236 for (IntervalPtrs::reverse_iterator
237 i = inactive_.rbegin(); i != inactive_.rend(); ) {
238 DEBUG(std::cerr << "\tinterval " << *i->first << " expired\n");
239 i = IntervalPtrs::reverse_iterator(inactive_.erase(i.base()-1));
242 DEBUG(std::cerr << *vrm_);
245 /// processActiveIntervals - expire old intervals and move non-overlapping ones
246 /// to the inactive list.
247 void RA::processActiveIntervals(unsigned CurPoint)
249 DEBUG(std::cerr << "\tprocessing active intervals:\n");
251 for (unsigned i = 0, e = active_.size(); i != e; ++i) {
252 LiveInterval *Interval = active_[i].first;
253 LiveInterval::iterator IntervalPos = active_[i].second;
254 unsigned reg = Interval->reg;
256 IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
258 if (IntervalPos == Interval->end()) { // Remove expired intervals.
259 DEBUG(std::cerr << "\t\tinterval " << *Interval << " expired\n");
260 assert(MRegisterInfo::isVirtualRegister(reg) &&
261 "Can only allocate virtual registers!");
262 reg = vrm_->getPhys(reg);
263 prt_->delRegUse(reg);
265 // Pop off the end of the list.
266 active_[i] = active_.back();
270 } else if (IntervalPos->start > CurPoint) {
271 // Move inactive intervals to inactive list.
272 DEBUG(std::cerr << "\t\tinterval " << *Interval << " inactive\n");
273 assert(MRegisterInfo::isVirtualRegister(reg) &&
274 "Can only allocate virtual registers!");
275 reg = vrm_->getPhys(reg);
276 prt_->delRegUse(reg);
278 inactive_.push_back(std::make_pair(Interval, IntervalPos));
280 // Pop off the end of the list.
281 active_[i] = active_.back();
285 // Otherwise, just update the iterator position.
286 active_[i].second = IntervalPos;
291 /// processInactiveIntervals - expire old intervals and move overlapping
292 /// ones to the active list.
293 void RA::processInactiveIntervals(unsigned CurPoint)
295 DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
297 for (unsigned i = 0, e = inactive_.size(); i != e; ++i) {
298 LiveInterval *Interval = inactive_[i].first;
299 LiveInterval::iterator IntervalPos = inactive_[i].second;
300 unsigned reg = Interval->reg;
302 IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
304 if (IntervalPos == Interval->end()) { // remove expired intervals.
305 DEBUG(std::cerr << "\t\tinterval " << *Interval << " expired\n");
307 // Pop off the end of the list.
308 inactive_[i] = inactive_.back();
309 inactive_.pop_back();
311 } else if (IntervalPos->start <= CurPoint) {
312 // move re-activated intervals in active list
313 DEBUG(std::cerr << "\t\tinterval " << *Interval << " active\n");
314 assert(MRegisterInfo::isVirtualRegister(reg) &&
315 "Can only allocate virtual registers!");
316 reg = vrm_->getPhys(reg);
317 prt_->addRegUse(reg);
319 active_.push_back(std::make_pair(Interval, IntervalPos));
321 // Pop off the end of the list.
322 inactive_[i] = inactive_.back();
323 inactive_.pop_back();
326 // Otherwise, just update the iterator position.
327 inactive_[i].second = IntervalPos;
332 /// updateSpillWeights - updates the spill weights of the specifed physical
333 /// register and its weight.
334 static void updateSpillWeights(std::vector<float> &Weights,
335 unsigned reg, float weight,
336 const MRegisterInfo *MRI) {
337 Weights[reg] += weight;
338 for (const unsigned* as = MRI->getAliasSet(reg); *as; ++as)
339 Weights[*as] += weight;
342 static RA::IntervalPtrs::iterator FindIntervalInVector(RA::IntervalPtrs &IP,
344 for (RA::IntervalPtrs::iterator I = IP.begin(), E = IP.end(); I != E; ++I)
345 if (I->first == LI) return I;
349 static void RevertVectorIteratorsTo(RA::IntervalPtrs &V, unsigned Point) {
350 for (unsigned i = 0, e = V.size(); i != e; ++i) {
351 RA::IntervalPtr &IP = V[i];
352 LiveInterval::iterator I = std::upper_bound(IP.first->begin(),
354 if (I != IP.first->begin()) --I;
360 /// assignRegOrStackSlotAtInterval - assign a register if one is available, or
362 void RA::assignRegOrStackSlotAtInterval(LiveInterval* cur)
364 DEBUG(std::cerr << "\tallocating current interval: ");
366 PhysRegTracker backupPrt = *prt_;
368 std::vector<float> SpillWeights;
369 SpillWeights.assign(mri_->getNumRegs(), 0.0);
371 unsigned StartPosition = cur->beginNumber();
373 // for each interval in active, update spill weights.
374 for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
376 unsigned reg = i->first->reg;
377 assert(MRegisterInfo::isVirtualRegister(reg) &&
378 "Can only allocate virtual registers!");
379 reg = vrm_->getPhys(reg);
380 updateSpillWeights(SpillWeights, reg, i->first->weight, mri_);
383 // for every interval in inactive we overlap with, mark the
384 // register as not free and update spill weights
385 for (IntervalPtrs::const_iterator i = inactive_.begin(),
386 e = inactive_.end(); i != e; ++i) {
387 if (cur->overlapsFrom(*i->first, i->second-1)) {
388 unsigned reg = i->first->reg;
389 assert(MRegisterInfo::isVirtualRegister(reg) &&
390 "Can only allocate virtual registers!");
391 reg = vrm_->getPhys(reg);
392 prt_->addRegUse(reg);
393 updateSpillWeights(SpillWeights, reg, i->first->weight, mri_);
397 // For every interval in fixed we overlap with, mark the register as not free
398 // and update spill weights.
399 for (unsigned i = 0, e = fixed_.size(); i != e; ++i) {
400 IntervalPtr &IP = fixed_[i];
401 LiveInterval *I = IP.first;
402 if (I->endNumber() > StartPosition) {
403 LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition);
405 if (II != I->begin() && II->start > StartPosition)
407 if (cur->overlapsFrom(*I, II)) {
408 unsigned reg = I->reg;
409 prt_->addRegUse(reg);
410 updateSpillWeights(SpillWeights, reg, I->weight, mri_);
415 unsigned physReg = getFreePhysReg(cur);
416 // restore the physical register tracker
418 // if we find a free register, we are done: assign this virtual to
419 // the free physical register and add this interval to the active
422 DEBUG(std::cerr << mri_->getName(physReg) << '\n');
423 vrm_->assignVirt2Phys(cur->reg, physReg);
424 prt_->addRegUse(physReg);
425 active_.push_back(std::make_pair(cur, cur->begin()));
426 handled_.push_back(cur);
429 DEBUG(std::cerr << "no free registers\n");
431 DEBUG(std::cerr << "\tassigning stack slot at interval "<< *cur << ":\n");
433 float minWeight = float(HUGE_VAL);
435 const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
436 for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_),
437 e = rc->allocation_order_end(*mf_); i != e; ++i) {
439 if (minWeight > SpillWeights[reg]) {
440 minWeight = SpillWeights[reg];
444 DEBUG(std::cerr << "\t\tregister with min weight: "
445 << mri_->getName(minReg) << " (" << minWeight << ")\n");
447 // if the current has the minimum weight, we need to spill it and
448 // add any added intervals back to unhandled, and restart
450 if (cur->weight <= minWeight) {
451 DEBUG(std::cerr << "\t\t\tspilling(c): " << *cur << '\n';);
452 int slot = vrm_->assignVirt2StackSlot(cur->reg);
453 std::vector<LiveInterval*> added =
454 li_->addIntervalsForSpills(*cur, *vrm_, slot);
456 return; // Early exit if all spills were folded.
458 // Merge added with unhandled. Note that we know that
459 // addIntervalsForSpills returns intervals sorted by their starting
461 for (unsigned i = 0, e = added.size(); i != e; ++i)
462 unhandled_.push(added[i]);
468 // push the current interval back to unhandled since we are going
469 // to re-run at least this iteration. Since we didn't modify it it
470 // should go back right in the front of the list
471 unhandled_.push(cur);
473 // otherwise we spill all intervals aliasing the register with
474 // minimum weight, rollback to the interval with the earliest
475 // start point and let the linear scan algorithm run again
476 std::vector<LiveInterval*> added;
477 assert(MRegisterInfo::isPhysicalRegister(minReg) &&
478 "did not choose a register to spill?");
479 std::vector<bool> toSpill(mri_->getNumRegs(), false);
481 // We are going to spill minReg and all its aliases.
482 toSpill[minReg] = true;
483 for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
486 // the earliest start of a spilled interval indicates up to where
487 // in handled we need to roll back
488 unsigned earliestStart = cur->beginNumber();
490 // set of spilled vregs (used later to rollback properly)
491 std::set<unsigned> spilled;
493 // spill live intervals of virtual regs mapped to the physical register we
494 // want to clear (and its aliases). We only spill those that overlap with the
495 // current interval as the rest do not affect its allocation. we also keep
496 // track of the earliest start of all spilled live intervals since this will
497 // mark our rollback point.
498 for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
499 unsigned reg = i->first->reg;
500 if (//MRegisterInfo::isVirtualRegister(reg) &&
501 toSpill[vrm_->getPhys(reg)] &&
502 cur->overlapsFrom(*i->first, i->second)) {
503 DEBUG(std::cerr << "\t\t\tspilling(a): " << *i->first << '\n');
504 earliestStart = std::min(earliestStart, i->first->beginNumber());
505 int slot = vrm_->assignVirt2StackSlot(i->first->reg);
506 std::vector<LiveInterval*> newIs =
507 li_->addIntervalsForSpills(*i->first, *vrm_, slot);
508 std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
512 for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end(); ++i){
513 unsigned reg = i->first->reg;
514 if (//MRegisterInfo::isVirtualRegister(reg) &&
515 toSpill[vrm_->getPhys(reg)] &&
516 cur->overlapsFrom(*i->first, i->second-1)) {
517 DEBUG(std::cerr << "\t\t\tspilling(i): " << *i->first << '\n');
518 earliestStart = std::min(earliestStart, i->first->beginNumber());
519 int slot = vrm_->assignVirt2StackSlot(reg);
520 std::vector<LiveInterval*> newIs =
521 li_->addIntervalsForSpills(*i->first, *vrm_, slot);
522 std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
527 DEBUG(std::cerr << "\t\trolling back to: " << earliestStart << '\n');
529 // Scan handled in reverse order up to the earliest start of a
530 // spilled live interval and undo each one, restoring the state of
532 while (!handled_.empty()) {
533 LiveInterval* i = handled_.back();
534 // If this interval starts before t we are done.
535 if (i->beginNumber() < earliestStart)
537 DEBUG(std::cerr << "\t\t\tundo changes for: " << *i << '\n');
540 // When undoing a live interval allocation we must know if it is active or
541 // inactive to properly update the PhysRegTracker and the VirtRegMap.
542 IntervalPtrs::iterator it;
543 if ((it = FindIntervalInVector(active_, i)) != active_.end()) {
545 if (MRegisterInfo::isPhysicalRegister(i->reg)) {
546 assert(0 && "daksjlfd");
547 prt_->delRegUse(i->reg);
550 if (!spilled.count(i->reg))
552 prt_->delRegUse(vrm_->getPhys(i->reg));
553 vrm_->clearVirt(i->reg);
555 } else if ((it = FindIntervalInVector(inactive_, i)) != inactive_.end()) {
557 if (MRegisterInfo::isPhysicalRegister(i->reg)) {
558 assert(0 && "daksjlfd");
561 if (!spilled.count(i->reg))
563 vrm_->clearVirt(i->reg);
566 assert(MRegisterInfo::isVirtualRegister(i->reg) &&
567 "Can only allocate virtual registers!");
568 vrm_->clearVirt(i->reg);
573 // Rewind the iterators in the active, inactive, and fixed lists back to the
574 // point we reverted to.
575 RevertVectorIteratorsTo(active_, earliestStart);
576 RevertVectorIteratorsTo(inactive_, earliestStart);
577 RevertVectorIteratorsTo(fixed_, earliestStart);
579 // scan the rest and undo each interval that expired after t and
580 // insert it in active (the next iteration of the algorithm will
581 // put it in inactive if required)
582 for (unsigned i = 0, e = handled_.size(); i != e; ++i) {
583 LiveInterval *HI = handled_[i];
584 if (!HI->expiredAt(earliestStart) &&
585 HI->expiredAt(cur->beginNumber())) {
586 DEBUG(std::cerr << "\t\t\tundo changes for: " << *HI << '\n');
587 active_.push_back(std::make_pair(HI, HI->begin()));
588 if (MRegisterInfo::isPhysicalRegister(HI->reg)) {
589 assert(0 &&"sdflkajsdf");
590 prt_->addRegUse(HI->reg);
592 prt_->addRegUse(vrm_->getPhys(HI->reg));
596 // merge added with unhandled
597 for (unsigned i = 0, e = added.size(); i != e; ++i)
598 unhandled_.push(added[i]);
601 /// getFreePhysReg - return a free physical register for this virtual register
602 /// interval if we have one, otherwise return 0.
603 unsigned RA::getFreePhysReg(LiveInterval* cur)
605 std::vector<unsigned> inactiveCounts(mri_->getNumRegs(), 0);
606 for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end();
608 unsigned reg = i->first->reg;
609 assert(MRegisterInfo::isVirtualRegister(reg) &&
610 "Can only allocate virtual registers!");
611 reg = vrm_->getPhys(reg);
612 ++inactiveCounts[reg];
615 const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
617 unsigned freeReg = 0;
618 for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_),
619 e = rc->allocation_order_end(*mf_); i != e; ++i) {
621 if (prt_->isRegAvail(reg) &&
622 (!freeReg || inactiveCounts[freeReg] < inactiveCounts[reg]))
628 FunctionPass* llvm::createLinearScanRegisterAllocator() {