LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

RegAllocLinearScan.cpp

Go to the documentation of this file.
00001 //===-- RegAllocLinearScan.cpp - Linear Scan register allocator -----------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements a linear scan register allocator.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #define DEBUG_TYPE "regalloc"
00015 #include "llvm/Function.h"
00016 #include "llvm/CodeGen/MachineFunctionPass.h"
00017 #include "llvm/CodeGen/MachineInstr.h"
00018 #include "llvm/CodeGen/Passes.h"
00019 #include "llvm/CodeGen/SSARegMap.h"
00020 #include "llvm/Target/MRegisterInfo.h"
00021 #include "llvm/Target/TargetMachine.h"
00022 #include "llvm/Support/Debug.h"
00023 #include "llvm/ADT/Statistic.h"
00024 #include "llvm/ADT/STLExtras.h"
00025 #include "LiveIntervalAnalysis.h"
00026 #include "PhysRegTracker.h"
00027 #include "VirtRegMap.h"
00028 #include <algorithm>
00029 #include <cmath>
00030 #include <set>
00031 #include <queue>
00032 using namespace llvm;
00033 
00034 namespace {
00035 
00036   Statistic<double> efficiency
00037   ("regalloc", "Ratio of intervals processed over total intervals");
00038   Statistic<> NumBacktracks("regalloc", "Number of times we had to backtrack");
00039 
00040   static unsigned numIterations = 0;
00041   static unsigned numIntervals = 0;
00042 
00043   struct RA : public MachineFunctionPass {
00044     typedef std::pair<LiveInterval*, LiveInterval::iterator> IntervalPtr;
00045     typedef std::vector<IntervalPtr> IntervalPtrs;
00046   private:
00047     MachineFunction* mf_;
00048     const TargetMachine* tm_;
00049     const MRegisterInfo* mri_;
00050     LiveIntervals* li_;
00051 
00052     /// handled_ - Intervals are added to the handled_ set in the order of their
00053     /// start value.  This is uses for backtracking.
00054     std::vector<LiveInterval*> handled_;
00055 
00056     /// fixed_ - Intervals that correspond to machine registers.
00057     ///
00058     IntervalPtrs fixed_;
00059 
00060     /// active_ - Intervals that are currently being processed, and which have a
00061     /// live range active for the current point.
00062     IntervalPtrs active_;
00063 
00064     /// inactive_ - Intervals that are currently being processed, but which have
00065     /// a hold at the current point.
00066     IntervalPtrs inactive_;
00067 
00068     typedef std::priority_queue<LiveInterval*,
00069                                 std::vector<LiveInterval*>,
00070                                 greater_ptr<LiveInterval> > IntervalHeap;
00071     IntervalHeap unhandled_;
00072     std::auto_ptr<PhysRegTracker> prt_;
00073     std::auto_ptr<VirtRegMap> vrm_;
00074     std::auto_ptr<Spiller> spiller_;
00075 
00076   public:
00077     virtual const char* getPassName() const {
00078       return "Linear Scan Register Allocator";
00079     }
00080 
00081     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00082       AU.addRequired<LiveIntervals>();
00083       MachineFunctionPass::getAnalysisUsage(AU);
00084     }
00085 
00086     /// runOnMachineFunction - register allocate the whole function
00087     bool runOnMachineFunction(MachineFunction&);
00088 
00089   private:
00090     /// linearScan - the linear scan algorithm
00091     void linearScan();
00092 
00093     /// initIntervalSets - initialize the interval sets.
00094     ///
00095     void initIntervalSets();
00096 
00097     /// processActiveIntervals - expire old intervals and move non-overlapping
00098     /// ones to the inactive list.
00099     void processActiveIntervals(unsigned CurPoint);
00100 
00101     /// processInactiveIntervals - expire old intervals and move overlapping
00102     /// ones to the active list.
00103     void processInactiveIntervals(unsigned CurPoint);
00104 
00105     /// assignRegOrStackSlotAtInterval - assign a register if one
00106     /// is available, or spill.
00107     void assignRegOrStackSlotAtInterval(LiveInterval* cur);
00108 
00109     ///
00110     /// register handling helpers
00111     ///
00112 
00113     /// getFreePhysReg - return a free physical register for this virtual
00114     /// register interval if we have one, otherwise return 0.
00115     unsigned getFreePhysReg(LiveInterval* cur);
00116 
00117     /// assignVirt2StackSlot - assigns this virtual register to a
00118     /// stack slot. returns the stack slot
00119     int assignVirt2StackSlot(unsigned virtReg);
00120 
00121     template <typename ItTy>
00122     void printIntervals(const char* const str, ItTy i, ItTy e) const {
00123       if (str) std::cerr << str << " intervals:\n";
00124       for (; i != e; ++i) {
00125         std::cerr << "\t" << *i->first << " -> ";
00126         unsigned reg = i->first->reg;
00127         if (MRegisterInfo::isVirtualRegister(reg)) {
00128           reg = vrm_->getPhys(reg);
00129         }
00130         std::cerr << mri_->getName(reg) << '\n';
00131       }
00132     }
00133   };
00134 }
00135 
00136 bool RA::runOnMachineFunction(MachineFunction &fn) {
00137   mf_ = &fn;
00138   tm_ = &fn.getTarget();
00139   mri_ = tm_->getRegisterInfo();
00140   li_ = &getAnalysis<LiveIntervals>();
00141 
00142   if (!prt_.get()) prt_.reset(new PhysRegTracker(*mri_));
00143   vrm_.reset(new VirtRegMap(*mf_));
00144   if (!spiller_.get()) spiller_.reset(createSpiller());
00145 
00146   initIntervalSets();
00147 
00148   linearScan();
00149 
00150   spiller_->runOnMachineFunction(*mf_, *vrm_);
00151 
00152   vrm_.reset();  // Free the VirtRegMap
00153 
00154 
00155   while (!unhandled_.empty()) unhandled_.pop();
00156   fixed_.clear();
00157   active_.clear();
00158   inactive_.clear();
00159   handled_.clear();
00160 
00161   return true;
00162 }
00163 
00164 /// initIntervalSets - initialize the interval sets.
00165 ///
00166 void RA::initIntervalSets()
00167 {
00168   assert(unhandled_.empty() && fixed_.empty() &&
00169          active_.empty() && inactive_.empty() &&
00170          "interval sets should be empty on initialization");
00171 
00172   for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
00173     if (MRegisterInfo::isPhysicalRegister(i->second.reg))
00174       fixed_.push_back(std::make_pair(&i->second, i->second.begin()));
00175     else
00176       unhandled_.push(&i->second);
00177   }
00178 }
00179 
00180 void RA::linearScan()
00181 {
00182   // linear scan algorithm
00183   DEBUG(std::cerr << "********** LINEAR SCAN **********\n");
00184   DEBUG(std::cerr << "********** Function: "
00185         << mf_->getFunction()->getName() << '\n');
00186 
00187   // DEBUG(printIntervals("unhandled", unhandled_.begin(), unhandled_.end()));
00188   DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end()));
00189   DEBUG(printIntervals("active", active_.begin(), active_.end()));
00190   DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
00191 
00192   while (!unhandled_.empty()) {
00193     // pick the interval with the earliest start point
00194     LiveInterval* cur = unhandled_.top();
00195     unhandled_.pop();
00196     ++numIterations;
00197     DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n');
00198 
00199     processActiveIntervals(cur->beginNumber());
00200     processInactiveIntervals(cur->beginNumber());
00201 
00202     assert(MRegisterInfo::isVirtualRegister(cur->reg) &&
00203            "Can only allocate virtual registers!");
00204     
00205     // Allocating a virtual register. try to find a free
00206     // physical register or spill an interval (possibly this one) in order to
00207     // assign it one.
00208     assignRegOrStackSlotAtInterval(cur);
00209 
00210     DEBUG(printIntervals("active", active_.begin(), active_.end()));
00211     DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
00212   }
00213   numIntervals += li_->getNumIntervals();
00214   efficiency = double(numIterations) / double(numIntervals);
00215 
00216   // expire any remaining active intervals
00217   for (IntervalPtrs::reverse_iterator
00218          i = active_.rbegin(); i != active_.rend(); ) {
00219     unsigned reg = i->first->reg;
00220     DEBUG(std::cerr << "\tinterval " << *i->first << " expired\n");
00221     assert(MRegisterInfo::isVirtualRegister(reg) &&
00222            "Can only allocate virtual registers!");
00223     reg = vrm_->getPhys(reg);
00224     prt_->delRegUse(reg);
00225     i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1));
00226   }
00227 
00228   // expire any remaining inactive intervals
00229   for (IntervalPtrs::reverse_iterator
00230          i = inactive_.rbegin(); i != inactive_.rend(); ) {
00231     DEBUG(std::cerr << "\tinterval " << *i->first << " expired\n");
00232     i = IntervalPtrs::reverse_iterator(inactive_.erase(i.base()-1));
00233   }
00234 
00235   DEBUG(std::cerr << *vrm_);
00236 }
00237 
00238 /// processActiveIntervals - expire old intervals and move non-overlapping ones
00239 /// to the inactive list.
00240 void RA::processActiveIntervals(unsigned CurPoint)
00241 {
00242   DEBUG(std::cerr << "\tprocessing active intervals:\n");
00243 
00244   for (unsigned i = 0, e = active_.size(); i != e; ++i) {
00245     LiveInterval *Interval = active_[i].first;
00246     LiveInterval::iterator IntervalPos = active_[i].second;
00247     unsigned reg = Interval->reg;
00248 
00249     IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
00250 
00251     if (IntervalPos == Interval->end()) {     // Remove expired intervals.
00252       DEBUG(std::cerr << "\t\tinterval " << *Interval << " expired\n");
00253       assert(MRegisterInfo::isVirtualRegister(reg) &&
00254              "Can only allocate virtual registers!");
00255       reg = vrm_->getPhys(reg);
00256       prt_->delRegUse(reg);
00257 
00258       // Pop off the end of the list.
00259       active_[i] = active_.back();
00260       active_.pop_back();
00261       --i; --e;
00262       
00263     } else if (IntervalPos->start > CurPoint) {
00264       // Move inactive intervals to inactive list.
00265       DEBUG(std::cerr << "\t\tinterval " << *Interval << " inactive\n");
00266       assert(MRegisterInfo::isVirtualRegister(reg) &&
00267              "Can only allocate virtual registers!");
00268       reg = vrm_->getPhys(reg);
00269       prt_->delRegUse(reg);
00270       // add to inactive.
00271       inactive_.push_back(std::make_pair(Interval, IntervalPos));
00272 
00273       // Pop off the end of the list.
00274       active_[i] = active_.back();
00275       active_.pop_back();
00276       --i; --e;
00277     } else {
00278       // Otherwise, just update the iterator position.
00279       active_[i].second = IntervalPos;
00280     }
00281   }
00282 }
00283 
00284 /// processInactiveIntervals - expire old intervals and move overlapping
00285 /// ones to the active list.
00286 void RA::processInactiveIntervals(unsigned CurPoint)
00287 {
00288   DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
00289 
00290   for (unsigned i = 0, e = inactive_.size(); i != e; ++i) {
00291     LiveInterval *Interval = inactive_[i].first;
00292     LiveInterval::iterator IntervalPos = inactive_[i].second;
00293     unsigned reg = Interval->reg;
00294 
00295     IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
00296     
00297     if (IntervalPos == Interval->end()) {       // remove expired intervals.
00298       DEBUG(std::cerr << "\t\tinterval " << *Interval << " expired\n");
00299 
00300       // Pop off the end of the list.
00301       inactive_[i] = inactive_.back();
00302       inactive_.pop_back();
00303       --i; --e;
00304     } else if (IntervalPos->start <= CurPoint) {
00305       // move re-activated intervals in active list
00306       DEBUG(std::cerr << "\t\tinterval " << *Interval << " active\n");
00307       assert(MRegisterInfo::isVirtualRegister(reg) &&
00308              "Can only allocate virtual registers!");
00309       reg = vrm_->getPhys(reg);
00310       prt_->addRegUse(reg);
00311       // add to active
00312       active_.push_back(std::make_pair(Interval, IntervalPos));
00313 
00314       // Pop off the end of the list.
00315       inactive_[i] = inactive_.back();
00316       inactive_.pop_back();
00317       --i; --e;
00318     } else {
00319       // Otherwise, just update the iterator position.
00320       inactive_[i].second = IntervalPos;
00321     }
00322   }
00323 }
00324 
00325 /// updateSpillWeights - updates the spill weights of the specifed physical
00326 /// register and its weight.
00327 static void updateSpillWeights(std::vector<float> &Weights, 
00328                                unsigned reg, float weight,
00329                                const MRegisterInfo *MRI) {
00330   Weights[reg] += weight;
00331   for (const unsigned* as = MRI->getAliasSet(reg); *as; ++as)
00332     Weights[*as] += weight;
00333 }
00334 
00335 static RA::IntervalPtrs::iterator FindIntervalInVector(RA::IntervalPtrs &IP,
00336                                                        LiveInterval *LI) {
00337   for (RA::IntervalPtrs::iterator I = IP.begin(), E = IP.end(); I != E; ++I)
00338     if (I->first == LI) return I;
00339   return IP.end();
00340 }
00341 
00342 static void RevertVectorIteratorsTo(RA::IntervalPtrs &V, unsigned Point) {
00343   for (unsigned i = 0, e = V.size(); i != e; ++i) {
00344     RA::IntervalPtr &IP = V[i];
00345     LiveInterval::iterator I = std::upper_bound(IP.first->begin(),
00346                                                 IP.second, Point);
00347     if (I != IP.first->begin()) --I;
00348     IP.second = I;
00349   }
00350 }
00351 
00352 
00353 /// assignRegOrStackSlotAtInterval - assign a register if one is available, or
00354 /// spill.
00355 void RA::assignRegOrStackSlotAtInterval(LiveInterval* cur)
00356 {
00357   DEBUG(std::cerr << "\tallocating current interval: ");
00358 
00359   PhysRegTracker backupPrt = *prt_;
00360 
00361   std::vector<float> SpillWeights;
00362   SpillWeights.assign(mri_->getNumRegs(), 0.0);
00363 
00364   unsigned StartPosition = cur->beginNumber();
00365 
00366   // for each interval in active, update spill weights.
00367   for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
00368        i != e; ++i) {
00369     unsigned reg = i->first->reg;
00370     assert(MRegisterInfo::isVirtualRegister(reg) &&
00371            "Can only allocate virtual registers!");
00372     reg = vrm_->getPhys(reg);
00373     updateSpillWeights(SpillWeights, reg, i->first->weight, mri_);
00374   }
00375 
00376   // for every interval in inactive we overlap with, mark the
00377   // register as not free and update spill weights
00378   for (IntervalPtrs::const_iterator i = inactive_.begin(),
00379          e = inactive_.end(); i != e; ++i) {
00380     if (cur->overlapsFrom(*i->first, i->second-1)) {
00381       unsigned reg = i->first->reg;
00382       assert(MRegisterInfo::isVirtualRegister(reg) &&
00383              "Can only allocate virtual registers!");
00384       reg = vrm_->getPhys(reg);
00385       prt_->addRegUse(reg);
00386       updateSpillWeights(SpillWeights, reg, i->first->weight, mri_);
00387     }
00388   }
00389 
00390   // For every interval in fixed we overlap with, mark the register as not free
00391   // and update spill weights.
00392   for (unsigned i = 0, e = fixed_.size(); i != e; ++i) {
00393     IntervalPtr &IP = fixed_[i];
00394     LiveInterval *I = IP.first;
00395     if (I->endNumber() > StartPosition) {
00396       LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition);
00397       IP.second = II;
00398       if (II != I->begin() && II->start > StartPosition)
00399         --II;
00400       if (cur->overlapsFrom(*I, II)) {
00401         unsigned reg = I->reg;
00402         prt_->addRegUse(reg);
00403         updateSpillWeights(SpillWeights, reg, I->weight, mri_);
00404       }
00405     }
00406   }
00407 
00408   unsigned physReg = getFreePhysReg(cur);
00409   // restore the physical register tracker
00410   *prt_ = backupPrt;
00411   // if we find a free register, we are done: assign this virtual to
00412   // the free physical register and add this interval to the active
00413   // list.
00414   if (physReg) {
00415     DEBUG(std::cerr <<  mri_->getName(physReg) << '\n');
00416     vrm_->assignVirt2Phys(cur->reg, physReg);
00417     prt_->addRegUse(physReg);
00418     active_.push_back(std::make_pair(cur, cur->begin()));
00419     handled_.push_back(cur);
00420     return;
00421   }
00422   DEBUG(std::cerr << "no free registers\n");
00423 
00424   DEBUG(std::cerr << "\tassigning stack slot at interval "<< *cur << ":\n");
00425 
00426   float minWeight = HUGE_VAL;
00427   unsigned minReg = 0;
00428   const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
00429   for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
00430        i != rc->allocation_order_end(*mf_); ++i) {
00431     unsigned reg = *i;
00432     if (minWeight > SpillWeights[reg]) {
00433       minWeight = SpillWeights[reg];
00434       minReg = reg;
00435     }
00436   }
00437   DEBUG(std::cerr << "\t\tregister with min weight: "
00438         << mri_->getName(minReg) << " (" << minWeight << ")\n");
00439 
00440   // if the current has the minimum weight, we need to spill it and
00441   // add any added intervals back to unhandled, and restart
00442   // linearscan.
00443   if (cur->weight <= minWeight) {
00444     DEBUG(std::cerr << "\t\t\tspilling(c): " << *cur << '\n';);
00445     int slot = vrm_->assignVirt2StackSlot(cur->reg);
00446     std::vector<LiveInterval*> added =
00447       li_->addIntervalsForSpills(*cur, *vrm_, slot);
00448     if (added.empty())
00449       return;  // Early exit if all spills were folded.
00450 
00451     // Merge added with unhandled.  Note that we know that
00452     // addIntervalsForSpills returns intervals sorted by their starting
00453     // point.
00454     for (unsigned i = 0, e = added.size(); i != e; ++i)
00455       unhandled_.push(added[i]);
00456     return;
00457   }
00458 
00459   ++NumBacktracks;
00460 
00461   // push the current interval back to unhandled since we are going
00462   // to re-run at least this iteration. Since we didn't modify it it
00463   // should go back right in the front of the list
00464   unhandled_.push(cur);
00465 
00466   // otherwise we spill all intervals aliasing the register with
00467   // minimum weight, rollback to the interval with the earliest
00468   // start point and let the linear scan algorithm run again
00469   std::vector<LiveInterval*> added;
00470   assert(MRegisterInfo::isPhysicalRegister(minReg) &&
00471          "did not choose a register to spill?");
00472   std::vector<bool> toSpill(mri_->getNumRegs(), false);
00473 
00474   // We are going to spill minReg and all its aliases.
00475   toSpill[minReg] = true;
00476   for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
00477     toSpill[*as] = true;
00478 
00479   // the earliest start of a spilled interval indicates up to where
00480   // in handled we need to roll back
00481   unsigned earliestStart = cur->beginNumber();
00482 
00483   // set of spilled vregs (used later to rollback properly)
00484   std::set<unsigned> spilled;
00485 
00486   // spill live intervals of virtual regs mapped to the physical register we
00487   // want to clear (and its aliases).  We only spill those that overlap with the
00488   // current interval as the rest do not affect its allocation. we also keep
00489   // track of the earliest start of all spilled live intervals since this will
00490   // mark our rollback point.
00491   for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
00492     unsigned reg = i->first->reg;
00493     if (//MRegisterInfo::isVirtualRegister(reg) &&
00494         toSpill[vrm_->getPhys(reg)] &&
00495         cur->overlapsFrom(*i->first, i->second)) {
00496       DEBUG(std::cerr << "\t\t\tspilling(a): " << *i->first << '\n');
00497       earliestStart = std::min(earliestStart, i->first->beginNumber());
00498       int slot = vrm_->assignVirt2StackSlot(i->first->reg);
00499       std::vector<LiveInterval*> newIs =
00500         li_->addIntervalsForSpills(*i->first, *vrm_, slot);
00501       std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
00502       spilled.insert(reg);
00503     }
00504   }
00505   for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end(); ++i){
00506     unsigned reg = i->first->reg;
00507     if (//MRegisterInfo::isVirtualRegister(reg) &&
00508         toSpill[vrm_->getPhys(reg)] &&
00509         cur->overlapsFrom(*i->first, i->second-1)) {
00510       DEBUG(std::cerr << "\t\t\tspilling(i): " << *i->first << '\n');
00511       earliestStart = std::min(earliestStart, i->first->beginNumber());
00512       int slot = vrm_->assignVirt2StackSlot(reg);
00513       std::vector<LiveInterval*> newIs =
00514         li_->addIntervalsForSpills(*i->first, *vrm_, slot);
00515       std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
00516       spilled.insert(reg);
00517     }
00518   }
00519 
00520   DEBUG(std::cerr << "\t\trolling back to: " << earliestStart << '\n');
00521 
00522   // Scan handled in reverse order up to the earliest start of a
00523   // spilled live interval and undo each one, restoring the state of
00524   // unhandled.
00525   while (!handled_.empty()) {
00526     LiveInterval* i = handled_.back();
00527     // If this interval starts before t we are done.
00528     if (i->beginNumber() < earliestStart)
00529       break;
00530     DEBUG(std::cerr << "\t\t\tundo changes for: " << *i << '\n');
00531     handled_.pop_back();
00532 
00533     // When undoing a live interval allocation we must know if it is active or
00534     // inactive to properly update the PhysRegTracker and the VirtRegMap.
00535     IntervalPtrs::iterator it;
00536     if ((it = FindIntervalInVector(active_, i)) != active_.end()) {
00537       active_.erase(it);
00538       if (MRegisterInfo::isPhysicalRegister(i->reg)) {
00539         assert(0 && "daksjlfd");
00540         prt_->delRegUse(i->reg);
00541         unhandled_.push(i);
00542       } else {
00543         if (!spilled.count(i->reg))
00544           unhandled_.push(i);
00545         prt_->delRegUse(vrm_->getPhys(i->reg));
00546         vrm_->clearVirt(i->reg);
00547       }
00548     } else if ((it = FindIntervalInVector(inactive_, i)) != inactive_.end()) {
00549       inactive_.erase(it);
00550       if (MRegisterInfo::isPhysicalRegister(i->reg)) {
00551         assert(0 && "daksjlfd");
00552         unhandled_.push(i);
00553       } else {
00554         if (!spilled.count(i->reg))
00555           unhandled_.push(i);
00556         vrm_->clearVirt(i->reg);
00557       }
00558     } else {
00559       assert(MRegisterInfo::isVirtualRegister(i->reg) &&
00560              "Can only allocate virtual registers!");
00561       vrm_->clearVirt(i->reg);
00562       unhandled_.push(i);
00563     }
00564   }
00565 
00566   // Rewind the iterators in the active, inactive, and fixed lists back to the
00567   // point we reverted to.
00568   RevertVectorIteratorsTo(active_, earliestStart);
00569   RevertVectorIteratorsTo(inactive_, earliestStart);
00570   RevertVectorIteratorsTo(fixed_, earliestStart);
00571 
00572   // scan the rest and undo each interval that expired after t and
00573   // insert it in active (the next iteration of the algorithm will
00574   // put it in inactive if required)
00575   for (unsigned i = 0, e = handled_.size(); i != e; ++i) {
00576     LiveInterval *HI = handled_[i];
00577     if (!HI->expiredAt(earliestStart) &&
00578         HI->expiredAt(cur->beginNumber())) {
00579       DEBUG(std::cerr << "\t\t\tundo changes for: " << *HI << '\n');
00580       active_.push_back(std::make_pair(HI, HI->begin()));
00581       if (MRegisterInfo::isPhysicalRegister(HI->reg)) {
00582         assert(0 &&"sdflkajsdf");
00583         prt_->addRegUse(HI->reg);
00584       } else
00585         prt_->addRegUse(vrm_->getPhys(HI->reg));
00586     }
00587   }
00588 
00589   // merge added with unhandled
00590   for (unsigned i = 0, e = added.size(); i != e; ++i)
00591     unhandled_.push(added[i]);
00592 }
00593 
00594 /// getFreePhysReg - return a free physical register for this virtual register
00595 /// interval if we have one, otherwise return 0.
00596 unsigned RA::getFreePhysReg(LiveInterval* cur)
00597 {
00598   std::vector<unsigned> inactiveCounts(mri_->getNumRegs(), 0);
00599   for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end();
00600        i != e; ++i) {
00601     unsigned reg = i->first->reg;
00602     assert(MRegisterInfo::isVirtualRegister(reg) &&
00603            "Can only allocate virtual registers!");
00604     reg = vrm_->getPhys(reg);
00605     ++inactiveCounts[reg];
00606   }
00607 
00608   const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
00609 
00610   unsigned freeReg = 0;
00611   for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
00612        i != rc->allocation_order_end(*mf_); ++i) {
00613     unsigned reg = *i;
00614     if (prt_->isRegAvail(reg) &&
00615         (!freeReg || inactiveCounts[freeReg] < inactiveCounts[reg]))
00616         freeReg = reg;
00617   }
00618   return freeReg;
00619 }
00620 
00621 FunctionPass* llvm::createLinearScanRegisterAllocator() {
00622   return new RA();
00623 }