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/LiveVariables.h"
17 #include "llvm/CodeGen/MachineFunctionPass.h"
18 #include "llvm/CodeGen/MachineInstr.h"
19 #include "llvm/CodeGen/Passes.h"
20 #include "llvm/CodeGen/SSARegMap.h"
21 #include "llvm/Target/MRegisterInfo.h"
22 #include "llvm/Target/TargetMachine.h"
23 #include "Support/Debug.h"
24 #include "LiveIntervals.h"
25 #include "PhysRegTracker.h"
26 #include "VirtRegMap.h"
33 class RA : public MachineFunctionPass {
36 const TargetMachine* tm_;
37 const MRegisterInfo* mri_;
39 typedef std::list<LiveIntervals::Interval*> IntervalPtrs;
40 IntervalPtrs unhandled_, fixed_, active_, inactive_, handled_;
42 std::auto_ptr<PhysRegTracker> prt_;
43 std::auto_ptr<VirtRegMap> vrm_;
44 std::auto_ptr<Spiller> spiller_;
46 typedef std::vector<float> SpillWeights;
47 SpillWeights spillWeights_;
50 virtual const char* getPassName() const {
51 return "Linear Scan Register Allocator";
54 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
55 AU.addRequired<LiveVariables>();
56 AU.addRequired<LiveIntervals>();
57 MachineFunctionPass::getAnalysisUsage(AU);
60 /// runOnMachineFunction - register allocate the whole function
61 bool runOnMachineFunction(MachineFunction&);
66 /// linearScan - the linear scan algorithm
69 /// initIntervalSets - initializa the four interval sets:
70 /// unhandled, fixed, active and inactive
71 void initIntervalSets(LiveIntervals::Intervals& li);
73 /// processActiveIntervals - expire old intervals and move
74 /// non-overlapping ones to the incative list
75 void processActiveIntervals(IntervalPtrs::value_type cur);
77 /// processInactiveIntervals - expire old intervals and move
78 /// overlapping ones to the active list
79 void processInactiveIntervals(IntervalPtrs::value_type cur);
81 /// updateSpillWeights - updates the spill weights of the
82 /// specifed physical register and its weight
83 void updateSpillWeights(unsigned reg, SpillWeights::value_type weight);
85 /// assignRegOrStackSlotAtInterval - assign a register if one
86 /// is available, or spill.
87 void assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur);
90 /// register handling helpers
93 /// getFreePhysReg - return a free physical register for this
94 /// virtual register interval if we have one, otherwise return
96 unsigned getFreePhysReg(IntervalPtrs::value_type cur);
98 /// assignVirt2StackSlot - assigns this virtual register to a
99 /// stack slot. returns the stack slot
100 int assignVirt2StackSlot(unsigned virtReg);
102 void printIntervals(const char* const str,
103 RA::IntervalPtrs::const_iterator i,
104 RA::IntervalPtrs::const_iterator e) const {
105 if (str) std::cerr << str << " intervals:\n";
106 for (; i != e; ++i) {
107 std::cerr << "\t" << **i << " -> ";
108 unsigned reg = (*i)->reg;
109 if (MRegisterInfo::isVirtualRegister(reg)) {
110 reg = vrm_->getPhys(reg);
112 std::cerr << mri_->getName(reg) << '\n';
116 // void verifyAssignment() const {
117 // for (Virt2PhysMap::const_iterator i = v2pMap_.begin(),
118 // e = v2pMap_.end(); i != e; ++i)
119 // for (Virt2PhysMap::const_iterator i2 = next(i); i2 != e; ++i2)
120 // if (MRegisterInfo::isVirtualRegister(i->second) &&
121 // (i->second == i2->second ||
122 // mri_->areAliases(i->second, i2->second))) {
123 // const LiveIntervals::Interval
124 // &in = li_->getInterval(i->second),
125 // &in2 = li_->getInterval(i2->second);
126 // if (in.overlaps(in2)) {
127 // std::cerr << in << " overlaps " << in2 << '\n';
135 void RA::releaseMemory()
144 bool RA::runOnMachineFunction(MachineFunction &fn) {
146 tm_ = &fn.getTarget();
147 mri_ = tm_->getRegisterInfo();
148 li_ = &getAnalysis<LiveIntervals>();
149 if (!prt_.get()) prt_.reset(new PhysRegTracker(*mri_));
150 vrm_.reset(new VirtRegMap(*mf_));
151 if (!spiller_.get()) spiller_.reset(createSpiller());
153 initIntervalSets(li_->getIntervals());
157 spiller_->runOnMachineFunction(*mf_, *vrm_);
162 void RA::linearScan()
164 // linear scan algorithm
165 DEBUG(std::cerr << "********** LINEAR SCAN **********\n");
166 DEBUG(std::cerr << "********** Function: "
167 << mf_->getFunction()->getName() << '\n');
169 DEBUG(printIntervals("unhandled", unhandled_.begin(), unhandled_.end()));
170 DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end()));
171 DEBUG(printIntervals("active", active_.begin(), active_.end()));
172 DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
174 while (!unhandled_.empty() || !fixed_.empty()) {
175 // pick the interval with the earliest start point
176 IntervalPtrs::value_type cur;
177 if (fixed_.empty()) {
178 cur = unhandled_.front();
179 unhandled_.pop_front();
181 else if (unhandled_.empty()) {
182 cur = fixed_.front();
185 else if (unhandled_.front()->start() < fixed_.front()->start()) {
186 cur = unhandled_.front();
187 unhandled_.pop_front();
190 cur = fixed_.front();
194 DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n');
196 processActiveIntervals(cur);
197 processInactiveIntervals(cur);
199 // if this register is fixed we are done
200 if (MRegisterInfo::isPhysicalRegister(cur->reg)) {
201 prt_->addRegUse(cur->reg);
202 active_.push_back(cur);
203 handled_.push_back(cur);
205 // otherwise we are allocating a virtual register. try to find
206 // a free physical register or spill an interval in order to
207 // assign it one (we could spill the current though).
209 assignRegOrStackSlotAtInterval(cur);
212 DEBUG(printIntervals("active", active_.begin(), active_.end()));
213 DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
214 // DEBUG(verifyAssignment());
217 // expire any remaining active intervals
218 for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
219 unsigned reg = (*i)->reg;
220 DEBUG(std::cerr << "\tinterval " << **i << " expired\n");
221 if (MRegisterInfo::isVirtualRegister(reg))
222 reg = vrm_->getPhys(reg);
223 prt_->delRegUse(reg);
226 DEBUG(std::cerr << *vrm_);
229 void RA::initIntervalSets(LiveIntervals::Intervals& li)
231 assert(unhandled_.empty() && fixed_.empty() &&
232 active_.empty() && inactive_.empty() &&
233 "interval sets should be empty on initialization");
235 for (LiveIntervals::Intervals::iterator i = li.begin(), e = li.end();
237 if (MRegisterInfo::isPhysicalRegister(i->reg))
238 fixed_.push_back(&*i);
240 unhandled_.push_back(&*i);
244 void RA::processActiveIntervals(IntervalPtrs::value_type cur)
246 DEBUG(std::cerr << "\tprocessing active intervals:\n");
247 for (IntervalPtrs::iterator i = active_.begin(); i != active_.end();) {
248 unsigned reg = (*i)->reg;
249 // remove expired intervals
250 if ((*i)->expiredAt(cur->start())) {
251 DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
252 if (MRegisterInfo::isVirtualRegister(reg))
253 reg = vrm_->getPhys(reg);
254 prt_->delRegUse(reg);
255 // remove from active
256 i = active_.erase(i);
258 // move inactive intervals to inactive list
259 else if (!(*i)->liveAt(cur->start())) {
260 DEBUG(std::cerr << "\t\tinterval " << **i << " inactive\n");
261 if (MRegisterInfo::isVirtualRegister(reg))
262 reg = vrm_->getPhys(reg);
263 prt_->delRegUse(reg);
265 inactive_.push_back(*i);
266 // remove from active
267 i = active_.erase(i);
275 void RA::processInactiveIntervals(IntervalPtrs::value_type cur)
277 DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
278 for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end();) {
279 unsigned reg = (*i)->reg;
281 // remove expired intervals
282 if ((*i)->expiredAt(cur->start())) {
283 DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
284 // remove from inactive
285 i = inactive_.erase(i);
287 // move re-activated intervals in active list
288 else if ((*i)->liveAt(cur->start())) {
289 DEBUG(std::cerr << "\t\tinterval " << **i << " active\n");
290 if (MRegisterInfo::isVirtualRegister(reg))
291 reg = vrm_->getPhys(reg);
292 prt_->addRegUse(reg);
294 active_.push_back(*i);
295 // remove from inactive
296 i = inactive_.erase(i);
304 void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight)
306 spillWeights_[reg] += weight;
307 for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
308 spillWeights_[*as] += weight;
311 void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur)
313 DEBUG(std::cerr << "\tallocating current interval: ");
315 PhysRegTracker backupPrt = *prt_;
317 spillWeights_.assign(mri_->getNumRegs(), 0.0);
319 // for each interval in active update spill weights
320 for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
322 unsigned reg = (*i)->reg;
323 if (MRegisterInfo::isVirtualRegister(reg))
324 reg = vrm_->getPhys(reg);
325 updateSpillWeights(reg, (*i)->weight);
328 // for every interval in inactive we overlap with, mark the
329 // register as not free and update spill weights
330 for (IntervalPtrs::const_iterator i = inactive_.begin(),
331 e = inactive_.end(); i != e; ++i) {
332 if (cur->overlaps(**i)) {
333 unsigned reg = (*i)->reg;
334 if (MRegisterInfo::isVirtualRegister(reg))
335 reg = vrm_->getPhys(reg);
336 prt_->addRegUse(reg);
337 updateSpillWeights(reg, (*i)->weight);
341 // for every interval in fixed we overlap with,
342 // mark the register as not free and update spill weights
343 for (IntervalPtrs::const_iterator i = fixed_.begin(),
344 e = fixed_.end(); i != e; ++i) {
345 if (cur->overlaps(**i)) {
346 unsigned reg = (*i)->reg;
347 prt_->addRegUse(reg);
348 updateSpillWeights(reg, (*i)->weight);
352 unsigned physReg = getFreePhysReg(cur);
353 // restore the physical register tracker
355 // if we find a free register, we are done: assign this virtual to
356 // the free physical register and add this interval to the active
359 DEBUG(std::cerr << mri_->getName(physReg) << '\n');
360 vrm_->assignVirt2Phys(cur->reg, physReg);
361 prt_->addRegUse(physReg);
362 active_.push_back(cur);
363 handled_.push_back(cur);
366 DEBUG(std::cerr << "no free registers\n");
368 DEBUG(std::cerr << "\tassigning stack slot at interval "<< *cur << ":\n");
370 float minWeight = std::numeric_limits<float>::infinity();
372 const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
373 for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
374 i != rc->allocation_order_end(*mf_); ++i) {
376 if (minWeight > spillWeights_[reg]) {
377 minWeight = spillWeights_[reg];
381 DEBUG(std::cerr << "\t\tregister with min weight: "
382 << mri_->getName(minReg) << " (" << minWeight << ")\n");
384 // if the current has the minimum weight, we need to modify it,
385 // push it back in unhandled and let the linear scan algorithm run
387 if (cur->weight <= minWeight) {
388 DEBUG(std::cerr << "\t\t\tspilling(c): " << *cur << '\n';);
389 int slot = vrm_->assignVirt2StackSlot(cur->reg);
390 li_->updateSpilledInterval(*cur, *vrm_, slot);
392 // if we didn't eliminate the interval find where to add it
393 // back to unhandled. We need to scan since unhandled are
394 // sorted on earliest start point and we may have changed our
397 IntervalPtrs::iterator it = unhandled_.begin();
398 while (it != unhandled_.end() && (*it)->start() < cur->start())
400 unhandled_.insert(it, cur);
405 // push the current interval back to unhandled since we are going
406 // to re-run at least this iteration. Since we didn't modify it it
407 // should go back right in the front of the list
408 unhandled_.push_front(cur);
410 // otherwise we spill all intervals aliasing the register with
411 // minimum weight, rollback to the interval with the earliest
412 // start point and let the linear scan algorithm run again
413 assert(MRegisterInfo::isPhysicalRegister(minReg) &&
414 "did not choose a register to spill?");
415 std::vector<bool> toSpill(mri_->getNumRegs(), false);
416 toSpill[minReg] = true;
417 for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
419 unsigned earliestStart = cur->start();
421 for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
422 unsigned reg = (*i)->reg;
423 if (MRegisterInfo::isVirtualRegister(reg) &&
424 toSpill[vrm_->getPhys(reg)] &&
425 cur->overlaps(**i)) {
426 DEBUG(std::cerr << "\t\t\tspilling(a): " << **i << '\n');
427 earliestStart = std::min(earliestStart, (*i)->start());
428 int slot = vrm_->assignVirt2StackSlot((*i)->reg);
429 li_->updateSpilledInterval(**i, *vrm_, slot);
432 for (IntervalPtrs::iterator i = inactive_.begin();
433 i != inactive_.end(); ++i) {
434 unsigned reg = (*i)->reg;
435 if (MRegisterInfo::isVirtualRegister(reg) &&
436 toSpill[vrm_->getPhys(reg)] &&
437 cur->overlaps(**i)) {
438 DEBUG(std::cerr << "\t\t\tspilling(i): " << **i << '\n');
439 earliestStart = std::min(earliestStart, (*i)->start());
440 int slot = vrm_->assignVirt2StackSlot((*i)->reg);
441 li_->updateSpilledInterval(**i, *vrm_, slot);
445 DEBUG(std::cerr << "\t\trolling back to: " << earliestStart << '\n');
446 // scan handled in reverse order and undo each one, restoring the
447 // state of unhandled and fixed
448 while (!handled_.empty()) {
449 IntervalPtrs::value_type i = handled_.back();
450 // if this interval starts before t we are done
451 if (!i->empty() && i->start() < earliestStart)
453 DEBUG(std::cerr << "\t\t\tundo changes for: " << *i << '\n');
455 IntervalPtrs::iterator it;
456 if ((it = find(active_.begin(), active_.end(), i)) != active_.end()) {
458 if (MRegisterInfo::isPhysicalRegister(i->reg)) {
459 fixed_.push_front(i);
460 prt_->delRegUse(i->reg);
463 prt_->delRegUse(vrm_->getPhys(i->reg));
464 vrm_->clearVirt(i->reg);
467 IntervalPtrs::iterator it = unhandled_.begin();
468 while (it != unhandled_.end() &&
469 (*it)->start() < i->start())
471 unhandled_.insert(it, i);
475 unhandled_.push_front(i);
479 else if ((it = find(inactive_.begin(), inactive_.end(), i)) != inactive_.end()) {
481 if (MRegisterInfo::isPhysicalRegister(i->reg))
482 fixed_.push_front(i);
484 vrm_->clearVirt(i->reg);
487 IntervalPtrs::iterator it = unhandled_.begin();
488 while (it != unhandled_.end() &&
489 (*it)->start() < i->start())
491 unhandled_.insert(it, i);
495 unhandled_.push_front(i);
499 if (MRegisterInfo::isPhysicalRegister(i->reg))
500 fixed_.push_front(i);
502 vrm_->clearVirt(i->reg);
503 unhandled_.push_front(i);
508 // scan the rest and undo each interval that expired after t and
509 // insert it in active (the next iteration of the algorithm will
510 // put it in inactive if required)
511 IntervalPtrs::iterator i = handled_.begin(), e = handled_.end();
512 for (; i != e; ++i) {
513 if (!(*i)->expiredAt(earliestStart) && (*i)->expiredAt(cur->start())) {
514 DEBUG(std::cerr << "\t\t\tundo changes for: " << **i << '\n');
515 active_.push_back(*i);
516 if (MRegisterInfo::isPhysicalRegister((*i)->reg))
517 prt_->addRegUse((*i)->reg);
519 prt_->addRegUse(vrm_->getPhys((*i)->reg));
524 unsigned RA::getFreePhysReg(IntervalPtrs::value_type cur)
526 const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
528 for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
529 i != rc->allocation_order_end(*mf_); ++i) {
531 if (prt_->isRegAvail(reg))
537 FunctionPass* llvm::createLinearScanRegisterAllocator() {