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 //===----------------------------------------------------------------------===//
13 #define DEBUG_TYPE "regalloc"
14 #include "llvm/Function.h"
15 #include "llvm/CodeGen/LiveIntervals.h"
16 #include "llvm/CodeGen/LiveVariables.h"
17 #include "llvm/CodeGen/MachineFrameInfo.h"
18 #include "llvm/CodeGen/MachineFunctionPass.h"
19 #include "llvm/CodeGen/MachineInstr.h"
20 #include "llvm/CodeGen/Passes.h"
21 #include "llvm/CodeGen/SSARegMap.h"
22 #include "llvm/Target/MRegisterInfo.h"
23 #include "llvm/Target/TargetInstrInfo.h"
24 #include "llvm/Target/TargetMachine.h"
25 #include "llvm/Support/CFG.h"
26 #include "Support/Debug.h"
27 #include "Support/DepthFirstIterator.h"
28 #include "Support/Statistic.h"
29 #include "Support/STLExtras.h"
34 Statistic<> numStores("ra-linearscan", "Number of stores added");
35 Statistic<> numLoads ("ra-linearscan", "Number of loads added");
37 class PhysRegTracker {
39 const MRegisterInfo* mri_;
40 std::vector<unsigned> regUse_;
43 PhysRegTracker(MachineFunction* mf)
44 : mri_(mf ? mf->getTarget().getRegisterInfo() : NULL) {
46 regUse_.assign(mri_->getNumRegs(), 0);
50 PhysRegTracker(const PhysRegTracker& rhs)
52 regUse_(rhs.regUse_) {
55 const PhysRegTracker& operator=(const PhysRegTracker& rhs) {
57 regUse_ = rhs.regUse_;
61 void addPhysRegUse(unsigned physReg) {
63 for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as) {
69 void delPhysRegUse(unsigned physReg) {
70 assert(regUse_[physReg] != 0);
72 for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as) {
74 assert(regUse_[physReg] != 0);
79 bool isPhysRegAvail(unsigned physReg) const {
80 return regUse_[physReg] == 0;
84 class RA : public MachineFunctionPass {
87 const TargetMachine* tm_;
88 const TargetInstrInfo* tii_;
89 const MRegisterInfo* mri_;
91 typedef std::list<LiveIntervals::Interval*> IntervalPtrs;
92 IntervalPtrs unhandled_, fixed_, active_, inactive_, handled_;
96 typedef std::map<unsigned, unsigned> Virt2PhysMap;
99 typedef std::map<unsigned, int> Virt2StackSlotMap;
100 Virt2StackSlotMap v2ssMap_;
104 typedef std::vector<float> SpillWeights;
105 SpillWeights spillWeights_;
113 virtual const char* getPassName() const {
114 return "Linear Scan Register Allocator";
117 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
118 AU.addRequired<LiveVariables>();
119 AU.addRequired<LiveIntervals>();
120 MachineFunctionPass::getAnalysisUsage(AU);
123 /// runOnMachineFunction - register allocate the whole function
124 bool runOnMachineFunction(MachineFunction&);
126 void releaseMemory();
129 /// initIntervalSets - initializa the four interval sets:
130 /// unhandled, fixed, active and inactive
131 void initIntervalSets(LiveIntervals::Intervals& li);
133 /// processActiveIntervals - expire old intervals and move
134 /// non-overlapping ones to the incative list
135 void processActiveIntervals(IntervalPtrs::value_type cur);
137 /// processInactiveIntervals - expire old intervals and move
138 /// overlapping ones to the active list
139 void processInactiveIntervals(IntervalPtrs::value_type cur);
141 /// updateSpillWeights - updates the spill weights of the
142 /// specifed physical register and its weight
143 void updateSpillWeights(unsigned reg, SpillWeights::value_type weight);
145 /// assignRegOrStackSlotAtInterval - assign a register if one
146 /// is available, or spill.
147 void assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur);
149 /// addSpillCode - adds spill code for interval. The interval
150 /// must be modified by LiveIntervals::updateIntervalForSpill.
151 void addSpillCode(IntervalPtrs::value_type li, int slot);
154 /// register handling helpers
157 /// getFreePhysReg - return a free physical register for this
158 /// virtual register interval if we have one, otherwise return
160 unsigned getFreePhysReg(IntervalPtrs::value_type cur);
162 /// assignVirt2PhysReg - assigns the free physical register to
163 /// the virtual register passed as arguments
164 Virt2PhysMap::iterator
165 assignVirt2PhysReg(unsigned virtReg, unsigned physReg);
167 /// clearVirtReg - free the physical register associated with this
168 /// virtual register and disassociate virtual->physical and
169 /// physical->virtual mappings
170 void clearVirtReg(Virt2PhysMap::iterator it);
172 /// assignVirt2StackSlot - assigns this virtual register to a
173 /// stack slot. returns the stack slot
174 int assignVirt2StackSlot(unsigned virtReg);
176 /// getStackSlot - returns the offset of the specified
177 /// register on the stack
178 int getStackSlot(unsigned virtReg);
180 void printVirtRegAssignment() const {
181 std::cerr << "register assignment:\n";
183 for (Virt2PhysMap::const_iterator
184 i = v2pMap_.begin(), e = v2pMap_.end(); i != e; ++i) {
185 assert(i->second != 0);
186 std::cerr << "[reg" << i->first << " -> "
187 << mri_->getName(i->second) << "]\n";
189 for (Virt2StackSlotMap::const_iterator
190 i = v2ssMap_.begin(), e = v2ssMap_.end(); i != e; ++i) {
191 std::cerr << '[' << i->first << " -> ss#" << i->second << "]\n";
196 void printIntervals(const char* const str,
197 RA::IntervalPtrs::const_iterator i,
198 RA::IntervalPtrs::const_iterator e) const {
199 if (str) std::cerr << str << " intervals:\n";
200 for (; i != e; ++i) {
201 std::cerr << "\t" << **i << " -> ";
202 unsigned reg = (*i)->reg;
203 if (MRegisterInfo::isVirtualRegister(reg)) {
204 Virt2PhysMap::const_iterator it = v2pMap_.find(reg);
205 reg = (it == v2pMap_.end() ? 0 : it->second);
207 std::cerr << mri_->getName(reg) << '\n';
211 void verifyAssignment() const {
212 for (Virt2PhysMap::const_iterator i = v2pMap_.begin(),
213 e = v2pMap_.end(); i != e; ++i)
214 for (Virt2PhysMap::const_iterator i2 = next(i); i2 != e; ++i2)
215 if (MRegisterInfo::isVirtualRegister(i->second) &&
216 (i->second == i2->second ||
217 mri_->areAliases(i->second, i2->second))) {
218 const LiveIntervals::Interval
219 &in = li_->getInterval(i->second),
220 &in2 = li_->getInterval(i2->second);
221 if (in.overlaps(in2)) {
222 std::cerr << in << " overlaps " << in2 << '\n';
230 void RA::releaseMemory()
241 bool RA::runOnMachineFunction(MachineFunction &fn) {
243 tm_ = &fn.getTarget();
244 tii_ = &tm_->getInstrInfo();
245 mri_ = tm_->getRegisterInfo();
246 li_ = &getAnalysis<LiveIntervals>();
247 prt_ = PhysRegTracker(mf_);
249 initIntervalSets(li_->getIntervals());
251 // linear scan algorithm
252 DEBUG(std::cerr << "********** LINEAR SCAN **********\n");
253 DEBUG(std::cerr << "********** Function: "
254 << mf_->getFunction()->getName() << '\n');
256 DEBUG(printIntervals("unhandled", unhandled_.begin(), unhandled_.end()));
257 DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end()));
258 DEBUG(printIntervals("active", active_.begin(), active_.end()));
259 DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
261 while (!unhandled_.empty() || !fixed_.empty()) {
262 // pick the interval with the earliest start point
263 IntervalPtrs::value_type cur;
264 if (fixed_.empty()) {
265 cur = unhandled_.front();
266 unhandled_.pop_front();
268 else if (unhandled_.empty()) {
269 cur = fixed_.front();
272 else if (unhandled_.front()->start() < fixed_.front()->start()) {
273 cur = unhandled_.front();
274 unhandled_.pop_front();
277 cur = fixed_.front();
281 DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n');
283 processActiveIntervals(cur);
284 processInactiveIntervals(cur);
286 // if this register is fixed we are done
287 if (MRegisterInfo::isPhysicalRegister(cur->reg)) {
288 prt_.addPhysRegUse(cur->reg);
289 active_.push_back(cur);
290 handled_.push_back(cur);
292 // otherwise we are allocating a virtual register. try to find
293 // a free physical register or spill an interval in order to
294 // assign it one (we could spill the current though).
296 assignRegOrStackSlotAtInterval(cur);
299 DEBUG(printIntervals("active", active_.begin(), active_.end()));
300 DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
301 // DEBUG(verifyAssignment());
304 // expire any remaining active intervals
305 for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
306 unsigned reg = (*i)->reg;
307 DEBUG(std::cerr << "\tinterval " << **i << " expired\n");
308 if (MRegisterInfo::isVirtualRegister(reg)) {
311 prt_.delPhysRegUse(reg);
314 DEBUG(printVirtRegAssignment());
316 DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
317 DEBUG(std::cerr << "********** Function: "
318 << mf_->getFunction()->getName() << '\n');
320 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
321 mbbi != mbbe; ++mbbi) {
324 for (MachineBasicBlock::iterator mii = mbbi->begin(), mie = mbbi->end();
328 unsigned index = li_->getInstructionIndex(mii);
329 if (index == std::numeric_limits<unsigned>::max())
334 mii->print(std::cerr, *tm_));
336 // use our current mapping and actually replace every
337 // virtual register with its allocated physical registers
338 DEBUG(std::cerr << "\t");
339 for (unsigned i = 0, e = mii->getNumOperands();
341 MachineOperand& op = mii->getOperand(i);
342 if (op.isRegister() &&
343 MRegisterInfo::isVirtualRegister(op.getReg())) {
344 unsigned virtReg = op.getReg();
345 Virt2PhysMap::iterator it = v2pMap_.find(virtReg);
346 assert(it != v2pMap_.end() &&
347 "all virtual registers must be allocated");
348 unsigned physReg = it->second;
349 assert(MRegisterInfo::isPhysicalRegister(physReg));
350 DEBUG(std::cerr << "\t[reg" << virtReg
351 << " -> " << mri_->getName(physReg) << ']');
352 mii->SetMachineOperandReg(i, physReg);
355 DEBUG(std::cerr << '\n');
359 DEBUG(std::cerr << "********** MACHINEINSTRS **********\n");
361 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
362 mbbi != mbbe; ++mbbi) {
363 for (MachineBasicBlock::iterator mii = mbbi->begin(),
364 mie = mbbi->end(); mii != mie; ++mii) {
365 unsigned index = li_->getInstructionIndex(mii);
366 if (index == std::numeric_limits<unsigned>::max())
369 std::cerr << index << '\t';
370 mii->print(std::cerr, *tm_);
377 void RA::initIntervalSets(LiveIntervals::Intervals& li)
379 assert(unhandled_.empty() && fixed_.empty() &&
380 active_.empty() && inactive_.empty() &&
381 "interval sets should be empty on initialization");
383 for (LiveIntervals::Intervals::iterator i = li.begin(), e = li.end();
385 if (MRegisterInfo::isPhysicalRegister(i->reg))
386 fixed_.push_back(&*i);
388 unhandled_.push_back(&*i);
392 void RA::processActiveIntervals(IntervalPtrs::value_type cur)
394 DEBUG(std::cerr << "\tprocessing active intervals:\n");
395 for (IntervalPtrs::iterator i = active_.begin(); i != active_.end();) {
396 unsigned reg = (*i)->reg;
397 // remove expired intervals
398 if ((*i)->expiredAt(cur->start())) {
399 DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
400 if (MRegisterInfo::isVirtualRegister(reg)) {
403 prt_.delPhysRegUse(reg);
404 // remove from active
405 i = active_.erase(i);
407 // move inactive intervals to inactive list
408 else if (!(*i)->liveAt(cur->start())) {
409 DEBUG(std::cerr << "\t\tinterval " << **i << " inactive\n");
410 if (MRegisterInfo::isVirtualRegister(reg)) {
413 prt_.delPhysRegUse(reg);
415 inactive_.push_back(*i);
416 // remove from active
417 i = active_.erase(i);
425 void RA::processInactiveIntervals(IntervalPtrs::value_type cur)
427 DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
428 for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end();) {
429 unsigned reg = (*i)->reg;
431 // remove expired intervals
432 if ((*i)->expiredAt(cur->start())) {
433 DEBUG(std::cerr << "\t\tinterval " << **i << " expired\n");
434 // remove from inactive
435 i = inactive_.erase(i);
437 // move re-activated intervals in active list
438 else if ((*i)->liveAt(cur->start())) {
439 DEBUG(std::cerr << "\t\tinterval " << **i << " active\n");
440 if (MRegisterInfo::isVirtualRegister(reg)) {
443 prt_.addPhysRegUse(reg);
445 active_.push_back(*i);
446 // remove from inactive
447 i = inactive_.erase(i);
455 void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight)
457 spillWeights_[reg] += weight;
458 for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
459 spillWeights_[*as] += weight;
462 void RA::assignRegOrStackSlotAtInterval(IntervalPtrs::value_type cur)
464 DEBUG(std::cerr << "\tallocating current interval: ");
466 PhysRegTracker backupPrt = prt_;
468 spillWeights_.assign(mri_->getNumRegs(), 0.0);
470 // for each interval in active update spill weights
471 for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
473 unsigned reg = (*i)->reg;
474 if (MRegisterInfo::isVirtualRegister(reg))
476 updateSpillWeights(reg, (*i)->weight);
479 // for every interval in inactive we overlap with, mark the
480 // register as not free and update spill weights
481 for (IntervalPtrs::const_iterator i = inactive_.begin(),
482 e = inactive_.end(); i != e; ++i) {
483 if (cur->overlaps(**i)) {
484 unsigned reg = (*i)->reg;
485 if (MRegisterInfo::isVirtualRegister(reg))
487 prt_.addPhysRegUse(reg);
488 updateSpillWeights(reg, (*i)->weight);
492 // for every interval in fixed we overlap with,
493 // mark the register as not free and update spill weights
494 for (IntervalPtrs::const_iterator i = fixed_.begin(),
495 e = fixed_.end(); i != e; ++i) {
496 if (cur->overlaps(**i)) {
497 unsigned reg = (*i)->reg;
498 prt_.addPhysRegUse(reg);
499 updateSpillWeights(reg, (*i)->weight);
503 unsigned physReg = getFreePhysReg(cur);
504 // restore the physical register tracker
506 // if we find a free register, we are done: assign this virtual to
507 // the free physical register and add this interval to the active
510 DEBUG(std::cerr << mri_->getName(physReg) << '\n');
511 assignVirt2PhysReg(cur->reg, physReg);
512 active_.push_back(cur);
513 handled_.push_back(cur);
516 DEBUG(std::cerr << "no free registers\n");
518 DEBUG(std::cerr << "\tassigning stack slot at interval "<< *cur << ":\n");
520 float minWeight = std::numeric_limits<float>::infinity();
522 const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
523 for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
524 i != rc->allocation_order_end(*mf_); ++i) {
526 if (minWeight > spillWeights_[reg]) {
527 minWeight = spillWeights_[reg];
531 DEBUG(std::cerr << "\t\tregister with min weight: "
532 << mri_->getName(minReg) << " (" << minWeight << ")\n");
534 // if the current has the minimum weight, we need to modify it,
535 // push it back in unhandled and let the linear scan algorithm run
537 if (cur->weight <= minWeight) {
538 DEBUG(std::cerr << "\t\t\tspilling(c): " << *cur << '\n';);
539 int slot = assignVirt2StackSlot(cur->reg);
540 li_->updateSpilledInterval(*cur, slot);
542 // if we didn't eliminate the interval find where to add it
543 // back to unhandled. We need to scan since unhandled are
544 // sorted on earliest start point and we may have changed our
547 addSpillCode(cur, slot);
548 IntervalPtrs::iterator it = unhandled_.begin();
549 while (it != unhandled_.end() && (*it)->start() < cur->start())
551 unhandled_.insert(it, cur);
556 // push the current interval back to unhandled since we are going
557 // to re-run at least this iteration. Since we didn't modify it it
558 // should go back right in the front of the list
559 unhandled_.push_front(cur);
561 // otherwise we spill all intervals aliasing the register with
562 // minimum weight, rollback to the interval with the earliest
563 // start point and let the linear scan algorithm run again
564 std::vector<bool> toSpill(mri_->getNumRegs(), false);
565 toSpill[minReg] = true;
566 for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
568 unsigned earliestStart = cur->start();
570 for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
571 unsigned reg = (*i)->reg;
572 if (MRegisterInfo::isVirtualRegister(reg) &&
573 toSpill[v2pMap_[reg]] &&
574 cur->overlaps(**i)) {
575 DEBUG(std::cerr << "\t\t\tspilling(a): " << **i << '\n');
576 earliestStart = std::min(earliestStart, (*i)->start());
577 int slot = assignVirt2StackSlot((*i)->reg);
578 li_->updateSpilledInterval(**i, slot);
579 addSpillCode(*i, slot);
582 for (IntervalPtrs::iterator i = inactive_.begin();
583 i != inactive_.end(); ++i) {
584 unsigned reg = (*i)->reg;
585 if (MRegisterInfo::isVirtualRegister(reg) &&
586 toSpill[v2pMap_[reg]] &&
587 cur->overlaps(**i)) {
588 DEBUG(std::cerr << "\t\t\tspilling(i): " << **i << '\n');
589 earliestStart = std::min(earliestStart, (*i)->start());
590 int slot = assignVirt2StackSlot((*i)->reg);
591 li_->updateSpilledInterval(**i, slot);
592 addSpillCode(*i, slot);
596 DEBUG(std::cerr << "\t\trolling back to: " << earliestStart << '\n');
597 // scan handled in reverse order and undo each one, restoring the
598 // state of unhandled and fixed
599 while (!handled_.empty()) {
600 IntervalPtrs::value_type i = handled_.back();
601 // if this interval starts before t we are done
602 if (!i->empty() && i->start() < earliestStart)
604 DEBUG(std::cerr << "\t\t\tundo changes for: " << *i << '\n');
606 IntervalPtrs::iterator it;
607 if ((it = find(active_.begin(), active_.end(), i)) != active_.end()) {
609 if (MRegisterInfo::isPhysicalRegister(i->reg)) {
610 fixed_.push_front(i);
611 prt_.delPhysRegUse(i->reg);
614 Virt2PhysMap::iterator v2pIt = v2pMap_.find(i->reg);
616 prt_.delPhysRegUse(v2pIt->second);
619 IntervalPtrs::iterator it = unhandled_.begin();
620 while (it != unhandled_.end() &&
621 (*it)->start() < i->start())
623 unhandled_.insert(it, i);
627 unhandled_.push_front(i);
631 else if ((it = find(inactive_.begin(), inactive_.end(), i)) != inactive_.end()) {
633 if (MRegisterInfo::isPhysicalRegister(i->reg))
634 fixed_.push_front(i);
636 Virt2PhysMap::iterator v2pIt = v2pMap_.find(i->reg);
640 IntervalPtrs::iterator it = unhandled_.begin();
641 while (it != unhandled_.end() &&
642 (*it)->start() < i->start())
644 unhandled_.insert(it, i);
648 unhandled_.push_front(i);
652 if (MRegisterInfo::isPhysicalRegister(i->reg))
653 fixed_.push_front(i);
655 Virt2PhysMap::iterator v2pIt = v2pMap_.find(i->reg);
657 unhandled_.push_front(i);
662 // scan the rest and undo each interval that expired after t and
663 // insert it in active (the next iteration of the algorithm will
664 // put it in inactive if required)
665 IntervalPtrs::iterator i = handled_.begin(), e = handled_.end();
666 for (; i != e; ++i) {
667 if (!(*i)->expiredAt(earliestStart) && (*i)->expiredAt(cur->start())) {
668 DEBUG(std::cerr << "\t\t\tundo changes for: " << **i << '\n');
669 active_.push_back(*i);
670 if (MRegisterInfo::isPhysicalRegister((*i)->reg))
671 prt_.addPhysRegUse((*i)->reg);
673 assert(v2pMap_.count((*i)->reg));
674 prt_.addPhysRegUse(v2pMap_.find((*i)->reg)->second);
680 void RA::addSpillCode(IntervalPtrs::value_type li, int slot)
682 // We scan the instructions corresponding to each range. We load
683 // when we have a use and spill at end of basic blocks or end of
684 // ranges only if the register was modified.
685 const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(li->reg);
687 for (LiveIntervals::Interval::Ranges::iterator i = li->ranges.begin(),
688 e = li->ranges.end(); i != e; ++i) {
689 unsigned index = i->first;
690 unsigned end = i->second;
694 // skip deleted instructions. getInstructionFromIndex returns
695 // null if the instruction was deleted (because of coalescing
697 while (!li_->getInstructionFromIndex(index))
698 index += LiveIntervals::InstrSlots::NUM;
699 MachineBasicBlock::iterator mi = li_->getInstructionFromIndex(index);
700 MachineBasicBlock* mbb = mi->getParent();
701 assert(mbb && "machine instruction not bound to basic block");
703 for (; index < end; index += LiveIntervals::InstrSlots::NUM) {
704 // ignore deleted instructions
705 while (!li_->getInstructionFromIndex(index)) index += 2;
706 mi = li_->getInstructionFromIndex(index);
707 DEBUG(std::cerr << "\t\t\t\texamining: \t\t\t\t\t"
708 << LiveIntervals::getBaseIndex(index) << '\t';
709 mi->print(std::cerr, *tm_));
711 // if it is used in this instruction load it
712 for (unsigned i = 0; i < mi->getNumOperands(); ++i) {
713 MachineOperand& mop = mi->getOperand(i);
714 if (mop.isRegister() && mop.getReg() == li->reg &&
715 mop.isUse() && !loaded) {
717 mri_->loadRegFromStackSlot(*mbb, mi, li->reg, slot, rc);
719 DEBUG(std::cerr << "\t\t\t\tadded load for reg" << li->reg
720 << " from ss#" << slot << " before: \t"
721 << LiveIntervals::getBaseIndex(index) << '\t';
722 mi->print(std::cerr, *tm_));
726 // if it is defined in this instruction mark as dirty
727 for (unsigned i = 0; i < mi->getNumOperands(); ++i) {
728 MachineOperand& mop = mi->getOperand(i);
729 if (mop.isRegister() && mop.getReg() == li->reg &&
733 mri_->storeRegToStackSlot(*mbb, next(mi), li->reg, slot,rc);
735 DEBUG(std::cerr << "\t\t\t\tadded store for reg" << li->reg
736 << " to ss#" << slot << " after: \t\t"
737 << LiveIntervals::getBaseIndex(index) << " \t";
738 mi->print(std::cerr, *tm_));
745 unsigned RA::getFreePhysReg(IntervalPtrs::value_type cur)
747 const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
749 for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
750 i != rc->allocation_order_end(*mf_); ++i) {
752 if (prt_.isPhysRegAvail(reg))
758 RA::Virt2PhysMap::iterator
759 RA::assignVirt2PhysReg(unsigned virtReg, unsigned physReg)
762 Virt2PhysMap::iterator it;
763 tie(it, inserted) = v2pMap_.insert(std::make_pair(virtReg, physReg));
764 assert(inserted && "attempting to assign a virt->phys mapping to an "
765 "already mapped register");
766 prt_.addPhysRegUse(physReg);
770 void RA::clearVirtReg(Virt2PhysMap::iterator it)
772 assert(it != v2pMap_.end() &&
773 "attempting to clear a not allocated virtual register");
774 unsigned physReg = it->second;
776 DEBUG(std::cerr << "\t\t\tcleared register " << mri_->getName(physReg)
781 int RA::assignVirt2StackSlot(unsigned virtReg)
783 const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(virtReg);
784 int frameIndex = mf_->getFrameInfo()->CreateStackObject(rc);
786 bool inserted = v2ssMap_.insert(std::make_pair(virtReg, frameIndex)).second;
787 assert(inserted && "attempt to assign stack slot to spilled register!");
791 int RA::getStackSlot(unsigned virtReg)
793 assert(v2ssMap_.count(virtReg) &&
794 "attempt to get stack slot for a non spilled register");
795 return v2ssMap_.find(virtReg)->second;
798 FunctionPass* llvm::createLinearScanRegisterAllocator() {