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 using namespace llvm;
  33
  34 namespace {
  35
  36   Statistic<double> efficiency
  37   ("regalloc", "Ratio of intervals processed over total intervals");
  38   Statistic<> NumBacktracks("regalloc", "Number of times we had to backtrack");
  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
 149   if (!prt_.get()) prt_.reset(new PhysRegTracker(*mri_));
 150   vrm_.reset(new VirtRegMap(*mf_));
 151   if (!spiller_.get()) spiller_.reset(createSpiller());
 152
 153   initIntervalSets();
 154
 155   linearScan();
 156
 157   spiller_->runOnMachineFunction(*mf_, *vrm_);
 158
 159   vrm_.reset();  // Free the VirtRegMap
 160
 161
 162   while (!unhandled_.empty()) unhandled_.pop();
 163   fixed_.clear();
 164   active_.clear();
 165   inactive_.clear();
 166   handled_.clear();
 167
 168   return true;
 169 }
 170
 171 void RA::linearScan()
 172 {
 173   // linear scan algorithm
 174   DEBUG(std::cerr << "********** LINEAR SCAN **********\n");
 175   DEBUG(std::cerr << "********** Function: "
 176         << mf_->getFunction()->getName() << '\n');
 177
 178   // DEBUG(printIntervals("unhandled", unhandled_.begin(), unhandled_.end()));
 179   DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end()));
 180   DEBUG(printIntervals("active", active_.begin(), active_.end()));
 181   DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
 182
 183   while (!unhandled_.empty()) {
 184     // pick the interval with the earliest start point
 185     LiveInterval* cur = unhandled_.top();
 186     unhandled_.pop();
 187     ++numIterations;
 188     DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n');
 189
 190     processActiveIntervals(cur->beginNumber());
 191     processInactiveIntervals(cur->beginNumber());
 192
 193     // if this register is fixed we are done
 194     if (MRegisterInfo::isPhysicalRegister(cur->reg)) {
 195       prt_->addRegUse(cur->reg);
 196       active_.push_back(std::make_pair(cur, cur->begin()));
 197       handled_.push_back(cur);
 198     } else {
 199       // otherwise we are allocating a virtual register. try to find a free
 200       // physical register or spill an interval (possibly this one) in order to
 201       // assign it one.
 202       assignRegOrStackSlotAtInterval(cur);
 203     }
 204
 205     DEBUG(printIntervals("active", active_.begin(), active_.end()));
 206     DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
 207   }
 208   numIntervals += li_->getNumIntervals();
 209   efficiency = double(numIterations) / double(numIntervals);
 210
 211   // expire any remaining active intervals
 212   for (IntervalPtrs::reverse_iterator
 213          i = active_.rbegin(); i != active_.rend(); ) {
 214     unsigned reg = i->first->reg;
 215     DEBUG(std::cerr << "\tinterval " << *i->first << " expired\n");
 216     if (MRegisterInfo::isVirtualRegister(reg))
 217       reg = vrm_->getPhys(reg);
 218     prt_->delRegUse(reg);
 219     i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1));
 220   }
 221
 222   // expire any remaining inactive intervals
 223   for (IntervalPtrs::reverse_iterator
 224          i = inactive_.rbegin(); i != inactive_.rend(); ) {
 225     DEBUG(std::cerr << "\tinterval " << *i->first << " expired\n");
 226     i = IntervalPtrs::reverse_iterator(inactive_.erase(i.base()-1));
 227   }
 228
 229   DEBUG(std::cerr << *vrm_);
 230 }
 231
 232 /// initIntervalSets - initialize the interval sets.
 233 ///
 234 void RA::initIntervalSets()
 235 {
 236   assert(unhandled_.empty() && fixed_.empty() &&
 237          active_.empty() && inactive_.empty() &&
 238          "interval sets should be empty on initialization");
 239
 240   for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i){
 241     unhandled_.push(&i->second);
 242     if (MRegisterInfo::isPhysicalRegister(i->second.reg))
 243       fixed_.push_back(std::make_pair(&i->second, i->second.begin()));
 244   }
 245 }
 246
 247 /// processActiveIntervals - expire old intervals and move non-overlapping ones
 248 /// to the inactive list.
 249 void RA::processActiveIntervals(unsigned CurPoint)
 250 {
 251   DEBUG(std::cerr << "\tprocessing active intervals:\n");
 252
 253   for (unsigned i = 0, e = active_.size(); i != e; ++i) {
 254     LiveInterval *Interval = active_[i].first;
 255     LiveInterval::iterator IntervalPos = active_[i].second;
 256     unsigned reg = Interval->reg;
 257
 258     IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
 259
 260     if (IntervalPos == Interval->end()) {     // Remove expired intervals.
 261       DEBUG(std::cerr << "\t\tinterval " << *Interval << " expired\n");
 262       if (MRegisterInfo::isVirtualRegister(reg))
 263         reg = vrm_->getPhys(reg);
 264       prt_->delRegUse(reg);
 265
 266       // Pop off the end of the list.
 267       active_[i] = active_.back();
 268       active_.pop_back();
 269       --i; --e;
 270
 271     } else if (IntervalPos->start > CurPoint) {
 272       // Move inactive intervals to inactive list.
 273       DEBUG(std::cerr << "\t\tinterval " << *Interval << " inactive\n");
 274       if (MRegisterInfo::isVirtualRegister(reg))
 275         reg = vrm_->getPhys(reg);
 276       prt_->delRegUse(reg);
 277       // add to inactive.
 278       inactive_.push_back(std::make_pair(Interval, IntervalPos));
 279
 280       // Pop off the end of the list.
 281       active_[i] = active_.back();
 282       active_.pop_back();
 283       --i; --e;
 284     } else {
 285       // Otherwise, just update the iterator position.
 286       active_[i].second = IntervalPos;
 287     }
 288   }
 289 }
 290
 291 /// processInactiveIntervals - expire old intervals and move overlapping
 292 /// ones to the active list.
 293 void RA::processInactiveIntervals(unsigned CurPoint)
 294 {
 295   DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
 296
 297   for (unsigned i = 0, e = inactive_.size(); i != e; ++i) {
 298     LiveInterval *Interval = inactive_[i].first;
 299     LiveInterval::iterator IntervalPos = inactive_[i].second;
 300     unsigned reg = Interval->reg;
 301
 302     IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
 303
 304     if (IntervalPos == Interval->end()) {       // remove expired intervals.
 305       DEBUG(std::cerr << "\t\tinterval " << *Interval << " expired\n");
 306
 307       // Pop off the end of the list.
 308       inactive_[i] = inactive_.back();
 309       inactive_.pop_back();
 310       --i; --e;
 311     } else if (IntervalPos->start <= CurPoint) {
 312       // move re-activated intervals in active list
 313       DEBUG(std::cerr << "\t\tinterval " << *Interval << " active\n");
 314       if (MRegisterInfo::isVirtualRegister(reg))
 315         reg = vrm_->getPhys(reg);
 316       prt_->addRegUse(reg);
 317       // add to active
 318       active_.push_back(std::make_pair(Interval, IntervalPos));
 319
 320       // Pop off the end of the list.
 321       inactive_[i] = inactive_.back();
 322       inactive_.pop_back();
 323       --i; --e;
 324     } else {
 325       // Otherwise, just update the iterator position.
 326       inactive_[i].second = IntervalPos;
 327     }
 328   }
 329 }
 330
 331 /// updateSpillWeights - updates the spill weights of the specifed physical
 332 /// register and its weight.
 333 void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight)
 334 {
 335   spillWeights_[reg] += weight;
 336   for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
 337     spillWeights_[*as] += weight;
 338 }
 339
 340 static RA::IntervalPtrs::iterator FindIntervalInVector(RA::IntervalPtrs &IP,
 341                                                        LiveInterval *LI) {
 342   for (RA::IntervalPtrs::iterator I = IP.begin(), E = IP.end(); I != E; ++I)
 343     if (I->first == LI) return I;
 344   return IP.end();
 345 }
 346
 347 static void RevertVectorIteratorsTo(RA::IntervalPtrs &V, unsigned Point) {
 348   for (unsigned i = 0, e = V.size(); i != e; ++i) {
 349     RA::IntervalPtr &IP = V[i];
 350     LiveInterval::iterator I = std::upper_bound(IP.first->begin(),
 351                                                 IP.second, Point);
 352     if (I != IP.first->begin()) --I;
 353     IP.second = I;
 354   }
 355 }
 356
 357
 358 /// assignRegOrStackSlotAtInterval - assign a register if one is available, or
 359 /// spill.
 360 void RA::assignRegOrStackSlotAtInterval(LiveInterval* cur)
 361 {
 362   DEBUG(std::cerr << "\tallocating current interval: ");
 363
 364   PhysRegTracker backupPrt = *prt_;
 365
 366   spillWeights_.assign(mri_->getNumRegs(), 0.0);
 367
 368   unsigned StartPosition = cur->beginNumber();
 369
 370   // for each interval in active update spill weights
 371   for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
 372        i != e; ++i) {
 373     unsigned reg = i->first->reg;
 374     if (MRegisterInfo::isVirtualRegister(reg))
 375       reg = vrm_->getPhys(reg);
 376     updateSpillWeights(reg, i->first->weight);
 377   }
 378
 379   // for every interval in inactive we overlap with, mark the
 380   // register as not free and update spill weights
 381   for (IntervalPtrs::const_iterator i = inactive_.begin(),
 382          e = inactive_.end(); i != e; ++i) {
 383     if (cur->overlapsFrom(*i->first, i->second-1)) {
 384       unsigned reg = i->first->reg;
 385       if (MRegisterInfo::isVirtualRegister(reg))
 386         reg = vrm_->getPhys(reg);
 387       prt_->addRegUse(reg);
 388       updateSpillWeights(reg, i->first->weight);
 389     }
 390   }
 391
 392   // For every interval in fixed we overlap with, mark the register as not free
 393   // and update spill weights.
 394   for (unsigned i = 0, e = fixed_.size(); i != e; ++i) {
 395     IntervalPtr &IP = fixed_[i];
 396     LiveInterval *I = IP.first;
 397     if (I->endNumber() > StartPosition) {
 398       LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition);
 399       IP.second = II;
 400       if (II != I->begin() && II->start > StartPosition)
 401         --II;
 402       if (cur->overlapsFrom(*I, II)) {
 403         unsigned reg = I->reg;
 404         prt_->addRegUse(reg);
 405         updateSpillWeights(reg, I->weight);
 406       }
 407     }
 408   }
 409
 410   unsigned physReg = getFreePhysReg(cur);
 411   // restore the physical register tracker
 412   *prt_ = backupPrt;
 413   // if we find a free register, we are done: assign this virtual to
 414   // the free physical register and add this interval to the active
 415   // list.
 416   if (physReg) {
 417     DEBUG(std::cerr <<  mri_->getName(physReg) << '\n');
 418     vrm_->assignVirt2Phys(cur->reg, physReg);
 419     prt_->addRegUse(physReg);
 420     active_.push_back(std::make_pair(cur, cur->begin()));
 421     handled_.push_back(cur);
 422     return;
 423   }
 424   DEBUG(std::cerr << "no free registers\n");
 425
 426   DEBUG(std::cerr << "\tassigning stack slot at interval "<< *cur << ":\n");
 427
 428   float minWeight = HUGE_VAL;
 429   unsigned minReg = 0;
 430   const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 431   for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 432        i != rc->allocation_order_end(*mf_); ++i) {
 433     unsigned reg = *i;
 434     if (minWeight > spillWeights_[reg]) {
 435       minWeight = spillWeights_[reg];
 436       minReg = reg;
 437     }
 438   }
 439   DEBUG(std::cerr << "\t\tregister with min weight: "
 440         << mri_->getName(minReg) << " (" << minWeight << ")\n");
 441
 442   // if the current has the minimum weight, we need to spill it and
 443   // add any added intervals back to unhandled, and restart
 444   // linearscan.
 445   if (cur->weight <= minWeight) {
 446     DEBUG(std::cerr << "\t\t\tspilling(c): " << *cur << '\n';);
 447     int slot = vrm_->assignVirt2StackSlot(cur->reg);
 448     std::vector<LiveInterval*> added =
 449       li_->addIntervalsForSpills(*cur, *vrm_, slot);
 450     if (added.empty())
 451       return;  // Early exit if all spills were folded.
 452
 453     // Merge added with unhandled.  Note that we know that
 454     // addIntervalsForSpills returns intervals sorted by their starting
 455     // point.
 456     for (unsigned i = 0, e = added.size(); i != e; ++i)
 457       unhandled_.push(added[i]);
 458     return;
 459   }
 460
 461   ++NumBacktracks;
 462
 463   // push the current interval back to unhandled since we are going
 464   // to re-run at least this iteration. Since we didn't modify it it
 465   // should go back right in the front of the list
 466   unhandled_.push(cur);
 467
 468   // otherwise we spill all intervals aliasing the register with
 469   // minimum weight, rollback to the interval with the earliest
 470   // start point and let the linear scan algorithm run again
 471   std::vector<LiveInterval*> added;
 472   assert(MRegisterInfo::isPhysicalRegister(minReg) &&
 473          "did not choose a register to spill?");
 474   std::vector<bool> toSpill(mri_->getNumRegs(), false);
 475
 476   // We are going to spill minReg and all its aliases.
 477   toSpill[minReg] = true;
 478   for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
 479     toSpill[*as] = true;
 480
 481   // the earliest start of a spilled interval indicates up to where
 482   // in handled we need to roll back
 483   unsigned earliestStart = cur->beginNumber();
 484
 485   // set of spilled vregs (used later to rollback properly)
 486   std::set<unsigned> spilled;
 487
 488   // spill live intervals of virtual regs mapped to the physical register we
 489   // want to clear (and its aliases).  We only spill those that overlap with the
 490   // current interval as the rest do not affect its allocation. we also keep
 491   // track of the earliest start of all spilled live intervals since this will
 492   // mark our rollback point.
 493   for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
 494     unsigned reg = i->first->reg;
 495     if (MRegisterInfo::isVirtualRegister(reg) &&
 496         toSpill[vrm_->getPhys(reg)] &&
 497         cur->overlapsFrom(*i->first, i->second)) {
 498       DEBUG(std::cerr << "\t\t\tspilling(a): " << *i->first << '\n');
 499       earliestStart = std::min(earliestStart, i->first->beginNumber());
 500       int slot = vrm_->assignVirt2StackSlot(i->first->reg);
 501       std::vector<LiveInterval*> newIs =
 502         li_->addIntervalsForSpills(*i->first, *vrm_, slot);
 503       std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
 504       spilled.insert(reg);
 505     }
 506   }
 507   for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end(); ++i){
 508     unsigned reg = i->first->reg;
 509     if (MRegisterInfo::isVirtualRegister(reg) &&
 510         toSpill[vrm_->getPhys(reg)] &&
 511         cur->overlapsFrom(*i->first, i->second-1)) {
 512       DEBUG(std::cerr << "\t\t\tspilling(i): " << *i->first << '\n');
 513       earliestStart = std::min(earliestStart, i->first->beginNumber());
 514       int slot = vrm_->assignVirt2StackSlot(reg);
 515       std::vector<LiveInterval*> newIs =
 516         li_->addIntervalsForSpills(*i->first, *vrm_, slot);
 517       std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
 518       spilled.insert(reg);
 519     }
 520   }
 521
 522   DEBUG(std::cerr << "\t\trolling back to: " << earliestStart << '\n');
 523
 524   // Scan handled in reverse order up to the earliest start of a
 525   // spilled live interval and undo each one, restoring the state of
 526   // unhandled.
 527   while (!handled_.empty()) {
 528     LiveInterval* i = handled_.back();
 529     // If this interval starts before t we are done.
 530     if (i->beginNumber() < earliestStart)
 531       break;
 532     DEBUG(std::cerr << "\t\t\tundo changes for: " << *i << '\n');
 533     handled_.pop_back();
 534
 535     // When undoing a live interval allocation we must know if it is active or
 536     // inactive to properly update the PhysRegTracker and the VirtRegMap.
 537     IntervalPtrs::iterator it;
 538     if ((it = FindIntervalInVector(active_, i)) != active_.end()) {
 539       active_.erase(it);
 540       if (MRegisterInfo::isPhysicalRegister(i->reg)) {
 541         prt_->delRegUse(i->reg);
 542         unhandled_.push(i);
 543       } else {
 544         if (!spilled.count(i->reg))
 545           unhandled_.push(i);
 546         prt_->delRegUse(vrm_->getPhys(i->reg));
 547         vrm_->clearVirt(i->reg);
 548       }
 549     } else if ((it = FindIntervalInVector(inactive_, i)) != inactive_.end()) {
 550       inactive_.erase(it);
 551       if (MRegisterInfo::isPhysicalRegister(i->reg))
 552         unhandled_.push(i);
 553       else {
 554         if (!spilled.count(i->reg))
 555           unhandled_.push(i);
 556         vrm_->clearVirt(i->reg);
 557       }
 558     }
 559     else {
 560       if (MRegisterInfo::isVirtualRegister(i->reg))
 561         vrm_->clearVirt(i->reg);
 562       unhandled_.push(i);
 563     }
 564   }
 565
 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);
 571
 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         prt_->addRegUse(HI->reg);
 583       else
 584         prt_->addRegUse(vrm_->getPhys(HI->reg));
 585     }
 586   }
 587
 588   // merge added with unhandled
 589   for (unsigned i = 0, e = added.size(); i != e; ++i)
 590     unhandled_.push(added[i]);
 591 }
 592
 593 /// getFreePhysReg - return a free physical register for this virtual register
 594 /// interval if we have one, otherwise return 0.
 595 unsigned RA::getFreePhysReg(LiveInterval* cur)
 596 {
 597   std::vector<unsigned> inactiveCounts(mri_->getNumRegs(), 0);
 598   for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end();
 599        i != e; ++i) {
 600     unsigned reg = i->first->reg;
 601     if (MRegisterInfo::isVirtualRegister(reg))
 602       reg = vrm_->getPhys(reg);
 603     ++inactiveCounts[reg];
 604   }
 605
 606   const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
 607
 608   unsigned freeReg = 0;
 609   for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
 610        i != rc->allocation_order_end(*mf_); ++i) {
 611     unsigned reg = *i;
 612     if (prt_->isRegAvail(reg) &&
 613         (!freeReg || inactiveCounts[freeReg] < inactiveCounts[reg]))
 614         freeReg = reg;
 615   }
 616   return freeReg;
 617 }
 618
 619 FunctionPass* llvm::createLinearScanRegisterAllocator() {
 620   return new RA();
 621 }