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