lib/CodeGen/RegAllocLinearScan.cpp

   1 //===-- RegAllocLinearScan.cpp - Linear Scan register allocator -----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   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.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements a linear scan register allocator.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  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"
  28 #include <algorithm>
  29 #include <cmath>
  30 #include <set>
  31 #include <queue>
  32
  33 using namespace llvm;
  34
  35 namespace {
  36
  37   Statistic<double> efficiency
  38   ("regalloc", "Ratio of intervals processed over total intervals");
  39
  40   static unsigned numIterations = 0;
  41   static unsigned numIntervals = 0;
  42
  43   struct RA : public MachineFunctionPass {
  44     typedef std::pair<LiveInterval*, LiveInterval::iterator> IntervalPtr;
  45     typedef std::vector<IntervalPtr> IntervalPtrs;
  46   private:
  47     MachineFunction* mf_;
  48     const TargetMachine* tm_;
  49     const MRegisterInfo* mri_;
  50     LiveIntervals* li_;
  51
  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_;
  55
  56     /// fixed_ - Intervals that correspond to machine registers.
  57     ///
  58     IntervalPtrs fixed_;
  59
  60     /// active_ - Intervals that are currently being processed, and which have a
  61     /// live range active for the current point.
  62     IntervalPtrs active_;
  63
  64     /// inactive_ - Intervals that are currently being processed, but which have
  65     /// a hold at the current point.
  66     IntervalPtrs inactive_;
  67
  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_;
  75
  76     typedef std::vector<float> SpillWeights;
  77     SpillWeights spillWeights_;
  78
  79   public:
  80     virtual const char* getPassName() const {
  81       return "Linear Scan Register Allocator";
  82     }
  83
  84     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  85       AU.addRequired<LiveIntervals>();
  86       MachineFunctionPass::getAnalysisUsage(AU);
  87     }
  88
  89     /// runOnMachineFunction - register allocate the whole function
  90     bool runOnMachineFunction(MachineFunction&);
  91
  92   private:
  93     /// linearScan - the linear scan algorithm
  94     void linearScan();
  95
  96     /// initIntervalSets - initialize the interval sets.
  97     ///
  98     void initIntervalSets();
  99
 100     /// processActiveIntervals - expire old intervals and move non-overlapping
 101     /// ones to the inactive list.
 102     void processActiveIntervals(unsigned CurPoint);
 103
 104     /// processInactiveIntervals - expire old intervals and move overlapping
 105     /// ones to the active list.
 106     void processInactiveIntervals(unsigned CurPoint);
 107
 108     /// updateSpillWeights - updates the spill weights of the
 109     /// specifed physical register and its weight.
 110     void updateSpillWeights(unsigned reg, SpillWeights::value_type weight);
 111
 112     /// assignRegOrStackSlotAtInterval - assign a register if one
 113     /// is available, or spill.
 114     void assignRegOrStackSlotAtInterval(LiveInterval* cur);
 115
 116     ///
 117     /// register handling helpers
 118     ///
 119
 120     /// getFreePhysReg - return a free physical register for this virtual
 121     /// register interval if we have one, otherwise return 0.
 122     unsigned getFreePhysReg(LiveInterval* cur);
 123
 124     /// assignVirt2StackSlot - assigns this virtual register to a
 125     /// stack slot. returns the stack slot
 126     int assignVirt2StackSlot(unsigned virtReg);
 127
 128     template <typename ItTy>
 129     void printIntervals(const char* const str, ItTy i, ItTy e) const {
 130       if (str) std::cerr << str << " intervals:\n";
 131       for (; i != e; ++i) {
 132         std::cerr << "\t" << *i->first << " -> ";
 133         unsigned reg = i->first->reg;
 134         if (MRegisterInfo::isVirtualRegister(reg)) {
 135           reg = vrm_->getPhys(reg);
 136         }
 137         std::cerr << mri_->getName(reg) << '\n';
 138       }
 139     }
 140   };
 141 }
 142
 143 bool RA::runOnMachineFunction(MachineFunction &fn) {
 144   mf_ = &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_));
 150   if (!spiller_.get()) spiller_.reset(createSpiller());
 151
 152   initIntervalSets();
 153
 154   linearScan();
 155
 156   spiller_->runOnMachineFunction(*mf_, *vrm_);
 157
 158   vrm_.reset();  // Free the VirtRegMap
 159
 160
 161   while (!unhandled_.empty()) unhandled_.pop();
 162   fixed_.clear();
 163   active_.clear();
 164   inactive_.clear();
 165   handled_.clear();
 166
 167   return true;
 168 }
 169
 170 void RA::linearScan()
 171 {
 172   // linear scan algorithm
 173   DEBUG(std::cerr << "********** LINEAR SCAN **********\n");
 174   DEBUG(std::cerr << "********** Function: "
 175         << mf_->getFunction()->getName() << '\n');
 176
 177   // DEBUG(printIntervals("unhandled", unhandled_.begin(), unhandled_.end()));
 178   DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end()));
 179   DEBUG(printIntervals("active", active_.begin(), active_.end()));
 180   DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
 181
 182   while (!unhandled_.empty()) {
 183     // pick the interval with the earliest start point
 184     LiveInterval* cur = unhandled_.top();
 185     unhandled_.pop();
 186     ++numIterations;
 187     DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n');
 188
 189     processActiveIntervals(cur->beginNumber());
 190     processInactiveIntervals(cur->beginNumber());
 191
 192     // if this register is fixed we are done
 193     if (MRegisterInfo::isPhysicalRegister(cur->reg)) {
 194       prt_->addRegUse(cur->reg);
 195       active_.push_back(std::make_pair(cur, cur->begin()));
 196       handled_.push_back(cur);
 197     } else {
 198       // otherwise we are allocating a virtual register. try to find a free
 199       // physical register or spill an interval in order to assign it one (we
 200       // could spill the current though).
 201       assignRegOrStackSlotAtInterval(cur);
 202     }
 203
 204     DEBUG(printIntervals("active", active_.begin(), active_.end()));
 205     DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
 206   }
 207   numIntervals += li_->getNumIntervals();
 208   efficiency = double(numIterations) / double(numIntervals);
 209
 210   // expire any remaining active intervals
 211   for (IntervalPtrs::reverse_iterator
 212          i = active_.rbegin(); i != active_.rend(); ) {
 213     unsigned reg = i->first->reg;
 214     DEBUG(std::cerr << "\tinterval " << *i->first << " expired\n");
 215     if (MRegisterInfo::isVirtualRegister(reg))
 216       reg = vrm_->getPhys(reg);
 217     prt_->delRegUse(reg);
 218     i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1));
 219   }
 220
 221   // expire any remaining inactive intervals
 222   for (IntervalPtrs::reverse_iterator
 223          i = inactive_.rbegin(); i != inactive_.rend(); ) {
 224     DEBUG(std::cerr << "\tinterval " << *i->first << " expired\n");
 225     i = IntervalPtrs::reverse_iterator(inactive_.erase(i.base()-1));
 226   }
 227
 228   DEBUG(std::cerr << *vrm_);
 229 }
 230
 231 /// initIntervalSets - initialize the interval sets.
 232 ///
 233 void RA::initIntervalSets()
 234 {
 235   assert(unhandled_.empty() && fixed_.empty() &&
 236          active_.empty() && inactive_.empty() &&
 237          "interval sets should be empty on initialization");
 238
 239   for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i){
 240     unhandled_.push(&i->second);
 241     if (MRegisterInfo::isPhysicalRegister(i->second.reg))
 242       fixed_.push_back(std::make_pair(&i->second, i->second.begin()));
 243   }
 244 }
 245
 246 /// processActiveIntervals - expire old intervals and move non-overlapping ones
 247 /// to the inactive list.
 248 void RA::processActiveIntervals(unsigned CurPoint)
 249 {
 250   DEBUG(std::cerr << "\tprocessing active intervals:\n");
 251
 252   for (unsigned i = 0, e = active_.size(); i != e; ++i) {
 253     LiveInterval *Interval = active_[i].first;
 254     LiveInterval::iterator IntervalPos = active_[i].second;
 255     unsigned reg = Interval->reg;
 256
 257     IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
 258
 259     if (IntervalPos == Interval->end()) {     // Remove expired intervals.
 260       DEBUG(std::cerr << "\t\tinterval " << *Interval << " expired\n");
 261       if (MRegisterInfo::isVirtualRegister(reg))
 262         reg = vrm_->getPhys(reg);
 263       prt_->delRegUse(reg);
 264
 265       // Pop off the end of the list.
 266       active_[i] = active_.back();
 267       active_.pop_back();
 268       --i; --e;
 269
 270     } else if (IntervalPos->start > CurPoint) {
 271       // Move inactive intervals to inactive list.
 272       DEBUG(std::cerr << "\t\tinterval " << *Interval << " inactive\n");
 273       if (MRegisterInfo::isVirtualRegister(reg))
 274         reg = vrm_->getPhys(reg);
 275       prt_->delRegUse(reg);
 276       // add to inactive.
 277       inactive_.push_back(std::make_pair(Interval, IntervalPos));
 278
 279       // Pop off the end of the list.
 280       active_[i] = active_.back();
 281       active_.pop_back();
 282       --i; --e;
 283     } else {
 284       // Otherwise, just update the iterator position.
 285       active_[i].second = IntervalPos;
 286     }
 287   }
 288 }
 289
 290 /// processInactiveIntervals - expire old intervals and move overlapping
 291 /// ones to the active list.
 292 void RA::processInactiveIntervals(unsigned CurPoint)
 293 {
 294   DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
 295   for (unsigned i = 0, e = inactive_.size(); i != e; ++i) {
 296     LiveInterval *Interval = inactive_[i].first;
 297     LiveInterval::iterator IntervalPos = inactive_[i].second;
 298     unsigned reg = Interval->reg;
 299
 300     IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
 301
 302     if (IntervalPos == Interval->end()) {       // remove expired intervals.
 303       DEBUG(std::cerr << "\t\tinterval " << *Interval << " expired\n");
 304
 305       // Pop off the end of the list.
 306       inactive_[i] = inactive_.back();
 307       inactive_.pop_back();
 308       --i; --e;
 309     } else if (IntervalPos->start <= CurPoint) {
 310       // move re-activated intervals in active list
 311       DEBUG(std::cerr << "\t\tinterval " << *Interval << " active\n");
 312       if (MRegisterInfo::isVirtualRegister(reg))
 313         reg = vrm_->getPhys(reg);
 314       prt_->addRegUse(reg);
 315       // add to active
 316       active_.push_back(std::make_pair(Interval, IntervalPos));
 317
 318       // Pop off the end of the list.
 319       inactive_[i] = inactive_.back();
 320       inactive_.pop_back();
 321       --i; --e;
 322     } else {
 323       // Otherwise, just update the iterator position.
 324       inactive_[i].second = IntervalPos;
 325     }
 326   }
 327 }
 328
 329 /// updateSpillWeights - updates the spill weights of the specifed physical
 330 /// register and its weight.
 331 void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight)
 332 {
 333   spillWeights_[reg] += weight;
 334   for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
 335     spillWeights_[*as] += weight;
 336 }
 337
 338 static RA::IntervalPtrs::iterator FindIntervalInVector(RA::IntervalPtrs &IP,
 339                                                        LiveInterval *LI) {
 340   for (RA::IntervalPtrs::iterator I = IP.begin(), E = IP.end(); I != E; ++I)
 341     if (I->first == LI) return I;
 342   return IP.end();
 343 }
 344
 345
 346
 347 /// assignRegOrStackSlotAtInterval - assign a register if one is available, or
 348 /// spill.
 349 void RA::assignRegOrStackSlotAtInterval(LiveInterval* cur)
 350 {
 351   DEBUG(std::cerr << "\tallocating current interval: ");
 352
 353   PhysRegTracker backupPrt = *prt_;
 354
 355   spillWeights_.assign(mri_->getNumRegs(), 0.0);
 356
 357   // for each interval in active update spill weights
 358   for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
 359        i != e; ++i) {
 360     unsigned reg = i->first->reg;
 361     if (MRegisterInfo::isVirtualRegister(reg))
 362       reg = vrm_->getPhys(reg);
 363     updateSpillWeights(reg, i->first->weight);
 364   }
 365
 366   // for every interval in inactive we overlap with, mark the
 367   // register as not free and update spill weights
 368   for (IntervalPtrs::const_iterator i = inactive_.begin(),
 369          e = inactive_.end(); i != e; ++i) {
 370     if (cur->overlaps(*i->first)) {
 371       unsigned reg = i->first->reg;
 372       if (MRegisterInfo::isVirtualRegister(reg))
 373         reg = vrm_->getPhys(reg);
 374       prt_->addRegUse(reg);
 375       updateSpillWeights(reg, i->first->weight);
 376     }
 377   }
 378
 379   // for every interval in fixed we overlap with,
 380   // mark the register as not free and update spill weights
 381   for (IntervalPtrs::const_iterator i = fixed_.begin(),
 382          e = fixed_.end(); i != e; ++i) {
 383     if (cur->overlaps(*i->first)) {
 384       unsigned reg = i->first->reg;
 385       prt_->addRegUse(reg);
 386       updateSpillWeights(reg, i->first->weight);
 387     }
 388   }
 389
 390   unsigned physReg = getFreePhysReg(cur);
 391   // restore the physical register tracker
 392   *prt_ = backupPrt;
 393   // if we find a free register, we are done: assign this virtual to
 394   // the free physical register and add this interval to the active
 395   // list.
 396   if (physReg) {
 397     DEBUG(std::cerr <<  mri_->getName(physReg) << '\n');
 398     vrm_->assignVirt2Phys(cur->reg, physReg);
 399     prt_->addRegUse(physReg);
 400     active_.push_back(std::make_pair(cur, cur->begin()));
 401     handled_.push_back(cur);
 402     return;
 403   }
 404   DEBUG(std::cerr << "no free registers\n");
 405
 406   DEBUG(std::cerr << "\tassigning stack slot at interval "<< *cur << ":\n");
 407
 408   float minWeight = HUGE_VAL;
 409   unsigned minReg = 0;
 410   const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 411   for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 412        i != rc->allocation_order_end(*mf_); ++i) {
 413     unsigned reg = *i;
 414     if (minWeight > spillWeights_[reg]) {
 415       minWeight = spillWeights_[reg];
 416       minReg = reg;
 417     }
 418   }
 419   DEBUG(std::cerr << "\t\tregister with min weight: "
 420         << mri_->getName(minReg) << " (" << minWeight << ")\n");
 421
 422   // if the current has the minimum weight, we need to spill it and
 423   // add any added intervals back to unhandled, and restart
 424   // linearscan.
 425   if (cur->weight <= minWeight) {
 426     DEBUG(std::cerr << "\t\t\tspilling(c): " << *cur << '\n';);
 427     int slot = vrm_->assignVirt2StackSlot(cur->reg);
 428     std::vector<LiveInterval*> added =
 429       li_->addIntervalsForSpills(*cur, *vrm_, slot);
 430     if (added.empty())
 431       return;  // Early exit if all spills were folded.
 432
 433     // Merge added with unhandled.  Note that we know that
 434     // addIntervalsForSpills returns intervals sorted by their starting
 435     // point.
 436     for (unsigned i = 0, e = added.size(); i != e; ++i)
 437       unhandled_.push(added[i]);
 438     return;
 439   }
 440
 441   // push the current interval back to unhandled since we are going
 442   // to re-run at least this iteration. Since we didn't modify it it
 443   // should go back right in the front of the list
 444   unhandled_.push(cur);
 445
 446   // otherwise we spill all intervals aliasing the register with
 447   // minimum weight, rollback to the interval with the earliest
 448   // start point and let the linear scan algorithm run again
 449   std::vector<LiveInterval*> added;
 450   assert(MRegisterInfo::isPhysicalRegister(minReg) &&
 451          "did not choose a register to spill?");
 452   std::vector<bool> toSpill(mri_->getNumRegs(), false);
 453   // we are going to spill minReg and all its aliases
 454   toSpill[minReg] = true;
 455   for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
 456     toSpill[*as] = true;
 457
 458   // the earliest start of a spilled interval indicates up to where
 459   // in handled we need to roll back
 460   unsigned earliestStart = cur->beginNumber();
 461
 462   // set of spilled vregs (used later to rollback properly)
 463   std::set<unsigned> spilled;
 464
 465   // spill live intervals of virtual regs mapped to the physical
 466   // register we want to clear (and its aliases). we only spill
 467   // those that overlap with the current interval as the rest do not
 468   // affect its allocation. we also keep track of the earliest start
 469   // of all spilled live intervals since this will mark our rollback
 470   // point
 471   for (IntervalPtrs::iterator
 472          i = active_.begin(); i != active_.end(); ++i) {
 473     unsigned reg = i->first->reg;
 474     if (MRegisterInfo::isVirtualRegister(reg) &&
 475         toSpill[vrm_->getPhys(reg)] &&
 476         cur->overlaps(*i->first)) {
 477       DEBUG(std::cerr << "\t\t\tspilling(a): " << *i->first << '\n');
 478       earliestStart = std::min(earliestStart, i->first->beginNumber());
 479       int slot = vrm_->assignVirt2StackSlot(i->first->reg);
 480       std::vector<LiveInterval*> newIs =
 481         li_->addIntervalsForSpills(*i->first, *vrm_, slot);
 482       std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
 483       spilled.insert(reg);
 484     }
 485   }
 486   for (IntervalPtrs::iterator
 487          i = inactive_.begin(); i != inactive_.end(); ++i) {
 488     unsigned reg = i->first->reg;
 489     if (MRegisterInfo::isVirtualRegister(reg) &&
 490         toSpill[vrm_->getPhys(reg)] &&
 491         cur->overlaps(*i->first)) {
 492       DEBUG(std::cerr << "\t\t\tspilling(i): " << *i->first << '\n');
 493       earliestStart = std::min(earliestStart, i->first->beginNumber());
 494       int slot = vrm_->assignVirt2StackSlot(reg);
 495       std::vector<LiveInterval*> newIs =
 496         li_->addIntervalsForSpills(*i->first, *vrm_, slot);
 497       std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
 498       spilled.insert(reg);
 499     }
 500   }
 501
 502   DEBUG(std::cerr << "\t\trolling back to: " << earliestStart << '\n');
 503
 504   // Scan handled in reverse order up to the earliest start of a
 505   // spilled live interval and undo each one, restoring the state of
 506   // unhandled.
 507   while (!handled_.empty()) {
 508     LiveInterval* i = handled_.back();
 509     // If this interval starts before t we are done.
 510     if (i->beginNumber() < earliestStart)
 511       break;
 512     DEBUG(std::cerr << "\t\t\tundo changes for: " << *i << '\n');
 513     handled_.pop_back();
 514
 515     // When undoing a live interval allocation we must know if it is active or
 516     // inactive to properly update the PhysRegTracker and the VirtRegMap.
 517     IntervalPtrs::iterator it;
 518     if ((it = FindIntervalInVector(active_, i)) != active_.end()) {
 519       active_.erase(it);
 520       if (MRegisterInfo::isPhysicalRegister(i->reg)) {
 521         prt_->delRegUse(i->reg);
 522         unhandled_.push(i);
 523       } else {
 524         if (!spilled.count(i->reg))
 525           unhandled_.push(i);
 526         prt_->delRegUse(vrm_->getPhys(i->reg));
 527         vrm_->clearVirt(i->reg);
 528       }
 529     } else if ((it = FindIntervalInVector(inactive_, i)) != inactive_.end()) {
 530       inactive_.erase(it);
 531       if (MRegisterInfo::isPhysicalRegister(i->reg))
 532         unhandled_.push(i);
 533       else {
 534         if (!spilled.count(i->reg))
 535           unhandled_.push(i);
 536         vrm_->clearVirt(i->reg);
 537       }
 538     }
 539     else {
 540       if (MRegisterInfo::isVirtualRegister(i->reg))
 541         vrm_->clearVirt(i->reg);
 542       unhandled_.push(i);
 543     }
 544   }
 545
 546   // scan the rest and undo each interval that expired after t and
 547   // insert it in active (the next iteration of the algorithm will
 548   // put it in inactive if required)
 549   for (unsigned i = 0, e = handled_.size(); i != e; ++i) {
 550     LiveInterval *HI = handled_[i];
 551     if (!HI->expiredAt(earliestStart) &&
 552         HI->expiredAt(cur->beginNumber())) {
 553       DEBUG(std::cerr << "\t\t\tundo changes for: " << *HI << '\n');
 554       active_.push_back(std::make_pair(HI, HI->begin()));
 555       if (MRegisterInfo::isPhysicalRegister(HI->reg))
 556         prt_->addRegUse(HI->reg);
 557       else
 558         prt_->addRegUse(vrm_->getPhys(HI->reg));
 559     }
 560   }
 561
 562   // merge added with unhandled
 563   for (unsigned i = 0, e = added.size(); i != e; ++i)
 564     unhandled_.push(added[i]);
 565 }
 566
 567 /// getFreePhysReg - return a free physical register for this virtual register
 568 /// interval if we have one, otherwise return 0.
 569 unsigned RA::getFreePhysReg(LiveInterval* cur)
 570 {
 571   std::vector<unsigned> inactiveCounts(mri_->getNumRegs(), 0);
 572   for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end();
 573        i != e; ++i) {
 574     unsigned reg = i->first->reg;
 575     if (MRegisterInfo::isVirtualRegister(reg))
 576       reg = vrm_->getPhys(reg);
 577     ++inactiveCounts[reg];
 578   }
 579
 580   const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 581
 582   unsigned freeReg = 0;
 583   for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 584        i != rc->allocation_order_end(*mf_); ++i) {
 585     unsigned reg = *i;
 586     if (prt_->isRegAvail(reg) &&
 587         (!freeReg || inactiveCounts[freeReg] < inactiveCounts[reg]))
 588         freeReg = reg;
 589   }
 590   return freeReg;
 591 }
 592
 593 FunctionPass* llvm::createLinearScanRegisterAllocator() {
 594   return new RA();
 595 }