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_;
45 typedef std::vector<float> SpillWeights;
46 SpillWeights spillWeights_;
49 virtual const char* getPassName() const {
50 return "Linear Scan Register Allocator";
53 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
54 AU.addRequired<LiveVariables>();
55 AU.addRequired<LiveIntervals>();
56 MachineFunctionPass::getAnalysisUsage(AU);
59 /// runOnMachineFunction - register allocate the whole function
60 bool runOnMachineFunction(MachineFunction&);
65 /// linearScan - the linear scan algorithm
68 /// initIntervalSets - initializa the four interval sets:
69 /// unhandled, fixed, active and inactive
70 void initIntervalSets(LiveIntervals::Intervals& li);
72 /// processActiveIntervals - expire old intervals and move
73 /// non-overlapping ones to the incative list
74 void processActiveIntervals(IntervalPtrs::value_type cur);
76 /// processInactiveIntervals - expire old intervals and move
77 /// overlapping ones to the active list
78 void processInactiveIntervals(IntervalPtrs::value_type cur);
80 /// updateSpillWeights - updates the spill weights of the
81 /// specifed physical register and its weight
82 void updateSpillWeights(unsigned reg, SpillWeights::value_type weight);
84 /// assignRegOrStackSlotAtInterval - assign a register if one
85 /// is available, or spill.
86 void assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur);
89 /// register handling helpers
92 /// getFreePhysReg - return a free physical register for this
93 /// virtual register interval if we have one, otherwise return
95 unsigned getFreePhysReg(IntervalPtrs::value_type cur);
97 /// assignVirt2StackSlot - assigns this virtual register to a
98 /// stack slot. returns the stack slot
99 int assignVirt2StackSlot(unsigned virtReg);
101 void printIntervals(const char* const str,
102 RA::IntervalPtrs::const_iterator i,
103 RA::IntervalPtrs::const_iterator e) const {
104 if (str) std::cerr << str << " intervals:\n";
105 for (; i != e; ++i) {
106 std::cerr << "\t" << **i << " -> ";
107 unsigned reg = (*i)->reg;
108 if (MRegisterInfo::isVirtualRegister(reg)) {
109 reg = vrm_->getPhys(reg);
111 std::cerr << mri_->getName(reg) << '\n';
115 // void verifyAssignment() const {
116 // for (Virt2PhysMap::const_iterator i = v2pMap_.begin(),
117 // e = v2pMap_.end(); i != e; ++i)
118 // for (Virt2PhysMap::const_iterator i2 = next(i); i2 != e; ++i2)
119 // if (MRegisterInfo::isVirtualRegister(i->second) &&
120 // (i->second == i2->second ||
121 // mri_->areAliases(i->second, i2->second))) {
122 // const LiveIntervals::Interval
123 // &in = li_->getInterval(i->second),
124 // &in2 = li_->getInterval(i2->second);
125 // if (in.overlaps(in2)) {
126 // std::cerr << in << " overlaps " << in2 << '\n';
134 void RA::releaseMemory()
143 bool RA::runOnMachineFunction(MachineFunction &fn) {
145 tm_ = &fn.getTarget();
146 mri_ = tm_->getRegisterInfo();
147 li_ = &getAnalysis<LiveIntervals>();
148 if (!prt_.get()) prt_.reset(new PhysRegTracker(*mri_));
149 vrm_.reset(new VirtRegMap(*mf_));
151 initIntervalSets(li_->getIntervals());
155 eliminateVirtRegs(*mf_, *vrm_);
160 void RA::linearScan()
162 // linear scan algorithm
163 DEBUG(std::cerr << "********** LINEAR SCAN **********\n");
164 DEBUG(std::cerr << "********** Function: "
165 << mf_->getFunction()->getName() << '\n');
167 DEBUG(printIntervals("unhandled", unhandled_.begin(), unhandled_.end()));
168 DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end()));
169 DEBUG(printIntervals("active", active_.begin(), active_.end()));
170 DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
172 while (!unhandled_.empty() || !fixed_.empty()) {
173 // pick the interval with the earliest start point
174 IntervalPtrs::value_type cur;
175 if (fixed_.empty()) {
176 cur = unhandled_.front();
177 unhandled_.pop_front();
179 else if (unhandled_.empty()) {
180 cur = fixed_.front();
183 else if (unhandled_.front()->start() < fixed_.front()->start()) {
184 cur = unhandled_.front();
185 unhandled_.pop_front();
188 cur = fixed_.front();
192 DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n');
194 processActiveIntervals(cur);
195 processInactiveIntervals(cur);
197 // if this register is fixed we are done
198 if (MRegisterInfo::isPhysicalRegister(cur->reg)) {
199 prt_->addRegUse(cur->reg);
200 active_.push_back(cur);
201 handled_.push_back(cur);
203 // otherwise we are allocating a virtual register. try to find
204 // a free physical register or spill an interval in order to
205 // assign it one (we could spill the current though).
207 assignRegOrStackSlotAtInterval(cur);
210 DEBUG(printIntervals("active", active_.begin(), active_.end()));
211 DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
212 // DEBUG(verifyAssignment());
215 // expire any remaining active intervals
216 for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
217 unsigned reg = (*i)->reg;
218 DEBUG(std::cerr << "\tinterval " << **i << " expired\n");
219 if (MRegisterInfo::isVirtualRegister(reg))
220 reg = vrm_->getPhys(reg);
221 prt_->delRegUse(reg);
224 DEBUG(std::cerr << *vrm_);
227 void RA::initIntervalSets(LiveIntervals::Intervals& li)
229 assert(unhandled_.empty() && fixed_.empty() &&
230 active_.empty() && inactive_.empty() &&
231 "interval sets should be empty on initialization");
233 for (LiveIntervals::Intervals::iterator i = li.begin(), e = li.end();
235 if (MRegisterInfo::isPhysicalRegister(i->reg))
236 fixed_.push_back(&*i);
238 unhandled_.push_back(&*i);
242 void RA::processActiveIntervals(IntervalPtrs::value_type cur)
244 DEBUG(std::cerr << "\tprocessing active intervals:\n");
245 for (IntervalPtrs::iterator i = active_.begin(); i != active_.end();) {
246 unsigned reg = (*i)->reg;
247 // remove expired intervals
248 if ((*i)->expiredAt(cur->start())) {
249 DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
250 if (MRegisterInfo::isVirtualRegister(reg))
251 reg = vrm_->getPhys(reg);
252 prt_->delRegUse(reg);
253 // remove from active
254 i = active_.erase(i);
256 // move inactive intervals to inactive list
257 else if (!(*i)->liveAt(cur->start())) {
258 DEBUG(std::cerr << "\t\tinterval " << **i << " inactive\n");
259 if (MRegisterInfo::isVirtualRegister(reg))
260 reg = vrm_->getPhys(reg);
261 prt_->delRegUse(reg);
263 inactive_.push_back(*i);
264 // remove from active
265 i = active_.erase(i);
273 void RA::processInactiveIntervals(IntervalPtrs::value_type cur)
275 DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
276 for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end();) {
277 unsigned reg = (*i)->reg;
279 // remove expired intervals
280 if ((*i)->expiredAt(cur->start())) {
281 DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
282 // remove from inactive
283 i = inactive_.erase(i);
285 // move re-activated intervals in active list
286 else if ((*i)->liveAt(cur->start())) {
287 DEBUG(std::cerr << "\t\tinterval " << **i << " active\n");
288 if (MRegisterInfo::isVirtualRegister(reg))
289 reg = vrm_->getPhys(reg);
290 prt_->addRegUse(reg);
292 active_.push_back(*i);
293 // remove from inactive
294 i = inactive_.erase(i);
302 void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight)
304 spillWeights_[reg] += weight;
305 for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
306 spillWeights_[*as] += weight;
309 void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur)
311 DEBUG(std::cerr << "\tallocating current interval: ");
313 PhysRegTracker backupPrt = *prt_;
315 spillWeights_.assign(mri_->getNumRegs(), 0.0);
317 // for each interval in active update spill weights
318 for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
320 unsigned reg = (*i)->reg;
321 if (MRegisterInfo::isVirtualRegister(reg))
322 reg = vrm_->getPhys(reg);
323 updateSpillWeights(reg, (*i)->weight);
326 // for every interval in inactive we overlap with, mark the
327 // register as not free and update spill weights
328 for (IntervalPtrs::const_iterator i = inactive_.begin(),
329 e = inactive_.end(); i != e; ++i) {
330 if (cur->overlaps(**i)) {
331 unsigned reg = (*i)->reg;
332 if (MRegisterInfo::isVirtualRegister(reg))
333 reg = vrm_->getPhys(reg);
334 prt_->addRegUse(reg);
335 updateSpillWeights(reg, (*i)->weight);
339 // for every interval in fixed we overlap with,
340 // mark the register as not free and update spill weights
341 for (IntervalPtrs::const_iterator i = fixed_.begin(),
342 e = fixed_.end(); i != e; ++i) {
343 if (cur->overlaps(**i)) {
344 unsigned reg = (*i)->reg;
345 prt_->addRegUse(reg);
346 updateSpillWeights(reg, (*i)->weight);
350 unsigned physReg = getFreePhysReg(cur);
351 // restore the physical register tracker
353 // if we find a free register, we are done: assign this virtual to
354 // the free physical register and add this interval to the active
357 DEBUG(std::cerr << mri_->getName(physReg) << '\n');
358 vrm_->assignVirt2Phys(cur->reg, physReg);
359 prt_->addRegUse(physReg);
360 active_.push_back(cur);
361 handled_.push_back(cur);
364 DEBUG(std::cerr << "no free registers\n");
366 DEBUG(std::cerr << "\tassigning stack slot at interval "<< *cur << ":\n");
368 float minWeight = std::numeric_limits<float>::infinity();
370 const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
371 for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
372 i != rc->allocation_order_end(*mf_); ++i) {
374 if (minWeight > spillWeights_[reg]) {
375 minWeight = spillWeights_[reg];
379 DEBUG(std::cerr << "\t\tregister with min weight: "
380 << mri_->getName(minReg) << " (" << minWeight << ")\n");
382 // if the current has the minimum weight, we need to modify it,
383 // push it back in unhandled and let the linear scan algorithm run
385 if (cur->weight <= minWeight) {
386 DEBUG(std::cerr << "\t\t\tspilling(c): " << *cur << '\n';);
387 int slot = vrm_->assignVirt2StackSlot(cur->reg);
388 li_->updateSpilledInterval(*cur, slot);
390 // if we didn't eliminate the interval find where to add it
391 // back to unhandled. We need to scan since unhandled are
392 // sorted on earliest start point and we may have changed our
395 IntervalPtrs::iterator it = unhandled_.begin();
396 while (it != unhandled_.end() && (*it)->start() < cur->start())
398 unhandled_.insert(it, cur);
403 // push the current interval back to unhandled since we are going
404 // to re-run at least this iteration. Since we didn't modify it it
405 // should go back right in the front of the list
406 unhandled_.push_front(cur);
408 // otherwise we spill all intervals aliasing the register with
409 // minimum weight, rollback to the interval with the earliest
410 // start point and let the linear scan algorithm run again
411 assert(MRegisterInfo::isPhysicalRegister(minReg) &&
412 "did not choose a register to spill?");
413 std::vector<bool> toSpill(mri_->getNumRegs(), false);
414 toSpill[minReg] = true;
415 for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
417 unsigned earliestStart = cur->start();
419 for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
420 unsigned reg = (*i)->reg;
421 if (MRegisterInfo::isVirtualRegister(reg) &&
422 toSpill[vrm_->getPhys(reg)] &&
423 cur->overlaps(**i)) {
424 DEBUG(std::cerr << "\t\t\tspilling(a): " << **i << '\n');
425 earliestStart = std::min(earliestStart, (*i)->start());
426 int slot = vrm_->assignVirt2StackSlot((*i)->reg);
427 li_->updateSpilledInterval(**i, slot);
430 for (IntervalPtrs::iterator i = inactive_.begin();
431 i != inactive_.end(); ++i) {
432 unsigned reg = (*i)->reg;
433 if (MRegisterInfo::isVirtualRegister(reg) &&
434 toSpill[vrm_->getPhys(reg)] &&
435 cur->overlaps(**i)) {
436 DEBUG(std::cerr << "\t\t\tspilling(i): " << **i << '\n');
437 earliestStart = std::min(earliestStart, (*i)->start());
438 int slot = vrm_->assignVirt2StackSlot((*i)->reg);
439 li_->updateSpilledInterval(**i, slot);
443 DEBUG(std::cerr << "\t\trolling back to: " << earliestStart << '\n');
444 // scan handled in reverse order and undo each one, restoring the
445 // state of unhandled and fixed
446 while (!handled_.empty()) {
447 IntervalPtrs::value_type i = handled_.back();
448 // if this interval starts before t we are done
449 if (!i->empty() && i->start() < earliestStart)
451 DEBUG(std::cerr << "\t\t\tundo changes for: " << *i << '\n');
453 IntervalPtrs::iterator it;
454 if ((it = find(active_.begin(), active_.end(), i)) != active_.end()) {
456 if (MRegisterInfo::isPhysicalRegister(i->reg)) {
457 fixed_.push_front(i);
458 prt_->delRegUse(i->reg);
461 prt_->delRegUse(vrm_->getPhys(i->reg));
462 vrm_->clearVirtReg(i->reg);
465 IntervalPtrs::iterator it = unhandled_.begin();
466 while (it != unhandled_.end() &&
467 (*it)->start() < i->start())
469 unhandled_.insert(it, i);
473 unhandled_.push_front(i);
477 else if ((it = find(inactive_.begin(), inactive_.end(), i)) != inactive_.end()) {
479 if (MRegisterInfo::isPhysicalRegister(i->reg))
480 fixed_.push_front(i);
482 vrm_->clearVirtReg(i->reg);
485 IntervalPtrs::iterator it = unhandled_.begin();
486 while (it != unhandled_.end() &&
487 (*it)->start() < i->start())
489 unhandled_.insert(it, i);
493 unhandled_.push_front(i);
497 if (MRegisterInfo::isPhysicalRegister(i->reg))
498 fixed_.push_front(i);
500 vrm_->clearVirtReg(i->reg);
501 unhandled_.push_front(i);
506 // scan the rest and undo each interval that expired after t and
507 // insert it in active (the next iteration of the algorithm will
508 // put it in inactive if required)
509 IntervalPtrs::iterator i = handled_.begin(), e = handled_.end();
510 for (; i != e; ++i) {
511 if (!(*i)->expiredAt(earliestStart) && (*i)->expiredAt(cur->start())) {
512 DEBUG(std::cerr << "\t\t\tundo changes for: " << **i << '\n');
513 active_.push_back(*i);
514 if (MRegisterInfo::isPhysicalRegister((*i)->reg))
515 prt_->addRegUse((*i)->reg);
517 prt_->addRegUse(vrm_->getPhys((*i)->reg));
522 unsigned RA::getFreePhysReg(IntervalPtrs::value_type cur)
524 const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
526 for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
527 i != rc->allocation_order_end(*mf_); ++i) {
529 if (prt_->isRegAvail(reg))
535 FunctionPass* llvm::createLinearScanRegisterAllocator() {