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_;
52 /// handled_ - Intervals are added to the handled_ set in the order of their
53 /// start value. This is uses for backtracking.
54 std::vector<LiveInterval*> handled_;
56 /// fixed_ - Intervals that correspond to machine registers.
60 /// active_ - Intervals that are currently being processed, and which have a
61 /// live range active for the current point.
64 /// inactive_ - Intervals that are currently being processed, but which have
65 /// a hold at the current point.
66 IntervalPtrs inactive_;
68 typedef std::priority_queue<LiveInterval*,
69 std::vector<LiveInterval*>,
70 greater_ptr<LiveInterval> > IntervalHeap;
71 IntervalHeap unhandled_;
72 std::auto_ptr<PhysRegTracker> prt_;
73 std::auto_ptr<VirtRegMap> vrm_;
74 std::auto_ptr<Spiller> spiller_;
77 virtual const char* getPassName() const {
78 return "Linear Scan Register Allocator";
81 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
82 AU.addRequired<LiveIntervals>();
83 MachineFunctionPass::getAnalysisUsage(AU);
86 /// runOnMachineFunction - register allocate the whole function
87 bool runOnMachineFunction(MachineFunction&);
90 /// linearScan - the linear scan algorithm
93 /// initIntervalSets - initialize the interval sets.
95 void initIntervalSets();
97 /// processActiveIntervals - expire old intervals and move non-overlapping
98 /// ones to the inactive list.
99 void processActiveIntervals(unsigned CurPoint);
101 /// processInactiveIntervals - expire old intervals and move overlapping
102 /// ones to the active list.
103 void processInactiveIntervals(unsigned CurPoint);
105 /// assignRegOrStackSlotAtInterval - assign a register if one
106 /// is available, or spill.
107 void assignRegOrStackSlotAtInterval(LiveInterval* cur);
110 /// register handling helpers
113 /// getFreePhysReg - return a free physical register for this virtual
114 /// register interval if we have one, otherwise return 0.
115 unsigned getFreePhysReg(LiveInterval* cur);
117 /// assignVirt2StackSlot - assigns this virtual register to a
118 /// stack slot. returns the stack slot
119 int assignVirt2StackSlot(unsigned virtReg);
121 template <typename ItTy>
122 void printIntervals(const char* const str, ItTy i, ItTy e) const {
123 if (str) std::cerr << str << " intervals:\n";
124 for (; i != e; ++i) {
125 std::cerr << "\t" << *i->first << " -> ";
126 unsigned reg = i->first->reg;
127 if (MRegisterInfo::isVirtualRegister(reg)) {
128 reg = vrm_->getPhys(reg);
130 std::cerr << mri_->getName(reg) << '\n';
136 bool RA::runOnMachineFunction(MachineFunction &fn) {
138 tm_ = &fn.getTarget();
139 mri_ = tm_->getRegisterInfo();
140 li_ = &getAnalysis<LiveIntervals>();
142 if (!prt_.get()) prt_.reset(new PhysRegTracker(*mri_));
143 vrm_.reset(new VirtRegMap(*mf_));
144 if (!spiller_.get()) spiller_.reset(createSpiller());
150 spiller_->runOnMachineFunction(*mf_, *vrm_);
152 vrm_.reset(); // Free the VirtRegMap
155 while (!unhandled_.empty()) unhandled_.pop();
164 /// initIntervalSets - initialize the interval sets.
166 void RA::initIntervalSets()
168 assert(unhandled_.empty() && fixed_.empty() &&
169 active_.empty() && inactive_.empty() &&
170 "interval sets should be empty on initialization");
172 for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
173 if (MRegisterInfo::isPhysicalRegister(i->second.reg))
174 fixed_.push_back(std::make_pair(&i->second, i->second.begin()));
176 unhandled_.push(&i->second);
180 void RA::linearScan()
182 // linear scan algorithm
183 DEBUG(std::cerr << "********** LINEAR SCAN **********\n");
184 DEBUG(std::cerr << "********** Function: "
185 << mf_->getFunction()->getName() << '\n');
187 // DEBUG(printIntervals("unhandled", unhandled_.begin(), unhandled_.end()));
188 DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end()));
189 DEBUG(printIntervals("active", active_.begin(), active_.end()));
190 DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
192 while (!unhandled_.empty()) {
193 // pick the interval with the earliest start point
194 LiveInterval* cur = unhandled_.top();
197 DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n');
199 processActiveIntervals(cur->beginNumber());
200 processInactiveIntervals(cur->beginNumber());
202 assert(MRegisterInfo::isVirtualRegister(cur->reg) &&
203 "Can only allocate virtual registers!");
205 // Allocating a virtual register. try to find a free
206 // physical register or spill an interval (possibly this one) in order to
208 assignRegOrStackSlotAtInterval(cur);
210 DEBUG(printIntervals("active", active_.begin(), active_.end()));
211 DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
213 numIntervals += li_->getNumIntervals();
214 efficiency = double(numIterations) / double(numIntervals);
216 // expire any remaining active intervals
217 for (IntervalPtrs::reverse_iterator
218 i = active_.rbegin(); i != active_.rend(); ) {
219 unsigned reg = i->first->reg;
220 DEBUG(std::cerr << "\tinterval " << *i->first << " expired\n");
221 assert(MRegisterInfo::isVirtualRegister(reg) &&
222 "Can only allocate virtual registers!");
223 reg = vrm_->getPhys(reg);
224 prt_->delRegUse(reg);
225 i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1));
228 // expire any remaining inactive intervals
229 for (IntervalPtrs::reverse_iterator
230 i = inactive_.rbegin(); i != inactive_.rend(); ) {
231 DEBUG(std::cerr << "\tinterval " << *i->first << " expired\n");
232 i = IntervalPtrs::reverse_iterator(inactive_.erase(i.base()-1));
235 DEBUG(std::cerr << *vrm_);
238 /// processActiveIntervals - expire old intervals and move non-overlapping ones
239 /// to the inactive list.
240 void RA::processActiveIntervals(unsigned CurPoint)
242 DEBUG(std::cerr << "\tprocessing active intervals:\n");
244 for (unsigned i = 0, e = active_.size(); i != e; ++i) {
245 LiveInterval *Interval = active_[i].first;
246 LiveInterval::iterator IntervalPos = active_[i].second;
247 unsigned reg = Interval->reg;
249 IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
251 if (IntervalPos == Interval->end()) { // Remove expired intervals.
252 DEBUG(std::cerr << "\t\tinterval " << *Interval << " expired\n");
253 assert(MRegisterInfo::isVirtualRegister(reg) &&
254 "Can only allocate virtual registers!");
255 reg = vrm_->getPhys(reg);
256 prt_->delRegUse(reg);
258 // Pop off the end of the list.
259 active_[i] = active_.back();
263 } else if (IntervalPos->start > CurPoint) {
264 // Move inactive intervals to inactive list.
265 DEBUG(std::cerr << "\t\tinterval " << *Interval << " inactive\n");
266 assert(MRegisterInfo::isVirtualRegister(reg) &&
267 "Can only allocate virtual registers!");
268 reg = vrm_->getPhys(reg);
269 prt_->delRegUse(reg);
271 inactive_.push_back(std::make_pair(Interval, IntervalPos));
273 // Pop off the end of the list.
274 active_[i] = active_.back();
278 // Otherwise, just update the iterator position.
279 active_[i].second = IntervalPos;
284 /// processInactiveIntervals - expire old intervals and move overlapping
285 /// ones to the active list.
286 void RA::processInactiveIntervals(unsigned CurPoint)
288 DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
290 for (unsigned i = 0, e = inactive_.size(); i != e; ++i) {
291 LiveInterval *Interval = inactive_[i].first;
292 LiveInterval::iterator IntervalPos = inactive_[i].second;
293 unsigned reg = Interval->reg;
295 IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
297 if (IntervalPos == Interval->end()) { // remove expired intervals.
298 DEBUG(std::cerr << "\t\tinterval " << *Interval << " expired\n");
300 // Pop off the end of the list.
301 inactive_[i] = inactive_.back();
302 inactive_.pop_back();
304 } else if (IntervalPos->start <= CurPoint) {
305 // move re-activated intervals in active list
306 DEBUG(std::cerr << "\t\tinterval " << *Interval << " active\n");
307 assert(MRegisterInfo::isVirtualRegister(reg) &&
308 "Can only allocate virtual registers!");
309 reg = vrm_->getPhys(reg);
310 prt_->addRegUse(reg);
312 active_.push_back(std::make_pair(Interval, IntervalPos));
314 // Pop off the end of the list.
315 inactive_[i] = inactive_.back();
316 inactive_.pop_back();
319 // Otherwise, just update the iterator position.
320 inactive_[i].second = IntervalPos;
325 /// updateSpillWeights - updates the spill weights of the specifed physical
326 /// register and its weight.
327 static void updateSpillWeights(std::vector<float> &Weights,
328 unsigned reg, float weight,
329 const MRegisterInfo *MRI) {
330 Weights[reg] += weight;
331 for (const unsigned* as = MRI->getAliasSet(reg); *as; ++as)
332 Weights[*as] += weight;
335 static RA::IntervalPtrs::iterator FindIntervalInVector(RA::IntervalPtrs &IP,
337 for (RA::IntervalPtrs::iterator I = IP.begin(), E = IP.end(); I != E; ++I)
338 if (I->first == LI) return I;
342 static void RevertVectorIteratorsTo(RA::IntervalPtrs &V, unsigned Point) {
343 for (unsigned i = 0, e = V.size(); i != e; ++i) {
344 RA::IntervalPtr &IP = V[i];
345 LiveInterval::iterator I = std::upper_bound(IP.first->begin(),
347 if (I != IP.first->begin()) --I;
353 /// assignRegOrStackSlotAtInterval - assign a register if one is available, or
355 void RA::assignRegOrStackSlotAtInterval(LiveInterval* cur)
357 DEBUG(std::cerr << "\tallocating current interval: ");
359 PhysRegTracker backupPrt = *prt_;
361 std::vector<float> SpillWeights;
362 SpillWeights.assign(mri_->getNumRegs(), 0.0);
364 unsigned StartPosition = cur->beginNumber();
366 // for each interval in active, update spill weights.
367 for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
369 unsigned reg = i->first->reg;
370 assert(MRegisterInfo::isVirtualRegister(reg) &&
371 "Can only allocate virtual registers!");
372 reg = vrm_->getPhys(reg);
373 updateSpillWeights(SpillWeights, reg, i->first->weight, mri_);
376 // for every interval in inactive we overlap with, mark the
377 // register as not free and update spill weights
378 for (IntervalPtrs::const_iterator i = inactive_.begin(),
379 e = inactive_.end(); i != e; ++i) {
380 if (cur->overlapsFrom(*i->first, i->second-1)) {
381 unsigned reg = i->first->reg;
382 assert(MRegisterInfo::isVirtualRegister(reg) &&
383 "Can only allocate virtual registers!");
384 reg = vrm_->getPhys(reg);
385 prt_->addRegUse(reg);
386 updateSpillWeights(SpillWeights, reg, i->first->weight, mri_);
390 // For every interval in fixed we overlap with, mark the register as not free
391 // and update spill weights.
392 for (unsigned i = 0, e = fixed_.size(); i != e; ++i) {
393 IntervalPtr &IP = fixed_[i];
394 LiveInterval *I = IP.first;
395 if (I->endNumber() > StartPosition) {
396 LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition);
398 if (II != I->begin() && II->start > StartPosition)
400 if (cur->overlapsFrom(*I, II)) {
401 unsigned reg = I->reg;
402 prt_->addRegUse(reg);
403 updateSpillWeights(SpillWeights, reg, I->weight, mri_);
408 unsigned physReg = getFreePhysReg(cur);
409 // restore the physical register tracker
411 // if we find a free register, we are done: assign this virtual to
412 // the free physical register and add this interval to the active
415 DEBUG(std::cerr << mri_->getName(physReg) << '\n');
416 vrm_->assignVirt2Phys(cur->reg, physReg);
417 prt_->addRegUse(physReg);
418 active_.push_back(std::make_pair(cur, cur->begin()));
419 handled_.push_back(cur);
422 DEBUG(std::cerr << "no free registers\n");
424 DEBUG(std::cerr << "\tassigning stack slot at interval "<< *cur << ":\n");
426 float minWeight = float(HUGE_VAL);
428 const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
429 for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_),
430 e = rc->allocation_order_end(*mf_); i != e; ++i) {
432 if (minWeight > SpillWeights[reg]) {
433 minWeight = SpillWeights[reg];
437 DEBUG(std::cerr << "\t\tregister with min weight: "
438 << mri_->getName(minReg) << " (" << minWeight << ")\n");
440 // if the current has the minimum weight, we need to spill it and
441 // add any added intervals back to unhandled, and restart
443 if (cur->weight <= minWeight) {
444 DEBUG(std::cerr << "\t\t\tspilling(c): " << *cur << '\n';);
445 int slot = vrm_->assignVirt2StackSlot(cur->reg);
446 std::vector<LiveInterval*> added =
447 li_->addIntervalsForSpills(*cur, *vrm_, slot);
449 return; // Early exit if all spills were folded.
451 // Merge added with unhandled. Note that we know that
452 // addIntervalsForSpills returns intervals sorted by their starting
454 for (unsigned i = 0, e = added.size(); i != e; ++i)
455 unhandled_.push(added[i]);
461 // push the current interval back to unhandled since we are going
462 // to re-run at least this iteration. Since we didn't modify it it
463 // should go back right in the front of the list
464 unhandled_.push(cur);
466 // otherwise we spill all intervals aliasing the register with
467 // minimum weight, rollback to the interval with the earliest
468 // start point and let the linear scan algorithm run again
469 std::vector<LiveInterval*> added;
470 assert(MRegisterInfo::isPhysicalRegister(minReg) &&
471 "did not choose a register to spill?");
472 std::vector<bool> toSpill(mri_->getNumRegs(), false);
474 // We are going to spill minReg and all its aliases.
475 toSpill[minReg] = true;
476 for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
479 // the earliest start of a spilled interval indicates up to where
480 // in handled we need to roll back
481 unsigned earliestStart = cur->beginNumber();
483 // set of spilled vregs (used later to rollback properly)
484 std::set<unsigned> spilled;
486 // spill live intervals of virtual regs mapped to the physical register we
487 // want to clear (and its aliases). We only spill those that overlap with the
488 // current interval as the rest do not affect its allocation. we also keep
489 // track of the earliest start of all spilled live intervals since this will
490 // mark our rollback point.
491 for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
492 unsigned reg = i->first->reg;
493 if (//MRegisterInfo::isVirtualRegister(reg) &&
494 toSpill[vrm_->getPhys(reg)] &&
495 cur->overlapsFrom(*i->first, i->second)) {
496 DEBUG(std::cerr << "\t\t\tspilling(a): " << *i->first << '\n');
497 earliestStart = std::min(earliestStart, i->first->beginNumber());
498 int slot = vrm_->assignVirt2StackSlot(i->first->reg);
499 std::vector<LiveInterval*> newIs =
500 li_->addIntervalsForSpills(*i->first, *vrm_, slot);
501 std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
505 for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end(); ++i){
506 unsigned reg = i->first->reg;
507 if (//MRegisterInfo::isVirtualRegister(reg) &&
508 toSpill[vrm_->getPhys(reg)] &&
509 cur->overlapsFrom(*i->first, i->second-1)) {
510 DEBUG(std::cerr << "\t\t\tspilling(i): " << *i->first << '\n');
511 earliestStart = std::min(earliestStart, i->first->beginNumber());
512 int slot = vrm_->assignVirt2StackSlot(reg);
513 std::vector<LiveInterval*> newIs =
514 li_->addIntervalsForSpills(*i->first, *vrm_, slot);
515 std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
520 DEBUG(std::cerr << "\t\trolling back to: " << earliestStart << '\n');
522 // Scan handled in reverse order up to the earliest start of a
523 // spilled live interval and undo each one, restoring the state of
525 while (!handled_.empty()) {
526 LiveInterval* i = handled_.back();
527 // If this interval starts before t we are done.
528 if (i->beginNumber() < earliestStart)
530 DEBUG(std::cerr << "\t\t\tundo changes for: " << *i << '\n');
533 // When undoing a live interval allocation we must know if it is active or
534 // inactive to properly update the PhysRegTracker and the VirtRegMap.
535 IntervalPtrs::iterator it;
536 if ((it = FindIntervalInVector(active_, i)) != active_.end()) {
538 if (MRegisterInfo::isPhysicalRegister(i->reg)) {
539 assert(0 && "daksjlfd");
540 prt_->delRegUse(i->reg);
543 if (!spilled.count(i->reg))
545 prt_->delRegUse(vrm_->getPhys(i->reg));
546 vrm_->clearVirt(i->reg);
548 } else if ((it = FindIntervalInVector(inactive_, i)) != inactive_.end()) {
550 if (MRegisterInfo::isPhysicalRegister(i->reg)) {
551 assert(0 && "daksjlfd");
554 if (!spilled.count(i->reg))
556 vrm_->clearVirt(i->reg);
559 assert(MRegisterInfo::isVirtualRegister(i->reg) &&
560 "Can only allocate virtual registers!");
561 vrm_->clearVirt(i->reg);
566 // Rewind the iterators in the active, inactive, and fixed lists back to the
567 // point we reverted to.
568 RevertVectorIteratorsTo(active_, earliestStart);
569 RevertVectorIteratorsTo(inactive_, earliestStart);
570 RevertVectorIteratorsTo(fixed_, earliestStart);
572 // scan the rest and undo each interval that expired after t and
573 // insert it in active (the next iteration of the algorithm will
574 // put it in inactive if required)
575 for (unsigned i = 0, e = handled_.size(); i != e; ++i) {
576 LiveInterval *HI = handled_[i];
577 if (!HI->expiredAt(earliestStart) &&
578 HI->expiredAt(cur->beginNumber())) {
579 DEBUG(std::cerr << "\t\t\tundo changes for: " << *HI << '\n');
580 active_.push_back(std::make_pair(HI, HI->begin()));
581 if (MRegisterInfo::isPhysicalRegister(HI->reg)) {
582 assert(0 &&"sdflkajsdf");
583 prt_->addRegUse(HI->reg);
585 prt_->addRegUse(vrm_->getPhys(HI->reg));
589 // merge added with unhandled
590 for (unsigned i = 0, e = added.size(); i != e; ++i)
591 unhandled_.push(added[i]);
594 /// getFreePhysReg - return a free physical register for this virtual register
595 /// interval if we have one, otherwise return 0.
596 unsigned RA::getFreePhysReg(LiveInterval* cur)
598 std::vector<unsigned> inactiveCounts(mri_->getNumRegs(), 0);
599 for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end();
601 unsigned reg = i->first->reg;
602 assert(MRegisterInfo::isVirtualRegister(reg) &&
603 "Can only allocate virtual registers!");
604 reg = vrm_->getPhys(reg);
605 ++inactiveCounts[reg];
608 const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
610 unsigned freeReg = 0;
611 for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_),
612 e = rc->allocation_order_end(*mf_); i != e; ++i) {
614 if (prt_->isRegAvail(reg) &&
615 (!freeReg || inactiveCounts[freeReg] < inactiveCounts[reg]))
621 FunctionPass* llvm::createLinearScanRegisterAllocator() {