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