LLVM API Documentation

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/CodeGen/LiveIntervalAnalysis.h"
00016 #include "PhysRegTracker.h"
00017 #include "VirtRegMap.h"
00018 #include "llvm/Function.h"
00019 #include "llvm/CodeGen/MachineFunctionPass.h"
00020 #include "llvm/CodeGen/MachineInstr.h"
00021 #include "llvm/CodeGen/Passes.h"
00022 #include "llvm/CodeGen/SSARegMap.h"
00023 #include "llvm/Target/MRegisterInfo.h"
00024 #include "llvm/Target/TargetMachine.h"
00025 #include "llvm/ADT/EquivalenceClasses.h"
00026 #include "llvm/ADT/Statistic.h"
00027 #include "llvm/ADT/STLExtras.h"
00028 #include "llvm/Support/Debug.h"
00029 #include <algorithm>
00030 #include <cmath>
00031 #include <iostream>
00032 #include <set>
00033 #include <queue>
00034 #include <memory>
00035 using namespace llvm;
00036 
00037 namespace {
00038 
00039   Statistic<double> efficiency
00040   ("regalloc", "Ratio of intervals processed over total intervals");
00041   Statistic<> NumBacktracks("regalloc", "Number of times we had to backtrack");
00042 
00043   static unsigned numIterations = 0;
00044   static unsigned numIntervals = 0;
00045 
00046   struct RA : public MachineFunctionPass {
00047     typedef std::pair<LiveInterval*, LiveInterval::iterator> IntervalPtr;
00048     typedef std::vector<IntervalPtr> IntervalPtrs;
00049   private:
00050     /// RelatedRegClasses - This structure is built the first time a function is
00051     /// compiled, and keeps track of which register classes have registers that
00052     /// belong to multiple classes or have aliases that are in other classes.
00053     EquivalenceClasses<const TargetRegisterClass*> RelatedRegClasses;
00054     std::map<unsigned, const TargetRegisterClass*> OneClassForEachPhysReg;
00055 
00056     MachineFunction* mf_;
00057     const TargetMachine* tm_;
00058     const MRegisterInfo* mri_;
00059     LiveIntervals* li_;
00060     bool *PhysRegsUsed;
00061 
00062     /// handled_ - Intervals are added to the handled_ set in the order of their
00063     /// start value.  This is uses for backtracking.
00064     std::vector<LiveInterval*> handled_;
00065 
00066     /// fixed_ - Intervals that correspond to machine registers.
00067     ///
00068     IntervalPtrs fixed_;
00069 
00070     /// active_ - Intervals that are currently being processed, and which have a
00071     /// live range active for the current point.
00072     IntervalPtrs active_;
00073 
00074     /// inactive_ - Intervals that are currently being processed, but which have
00075     /// a hold at the current point.
00076     IntervalPtrs inactive_;
00077 
00078     typedef std::priority_queue<LiveInterval*,
00079                                 std::vector<LiveInterval*>,
00080                                 greater_ptr<LiveInterval> > IntervalHeap;
00081     IntervalHeap unhandled_;
00082     std::auto_ptr<PhysRegTracker> prt_;
00083     std::auto_ptr<VirtRegMap> vrm_;
00084     std::auto_ptr<Spiller> spiller_;
00085 
00086   public:
00087     virtual const char* getPassName() const {
00088       return "Linear Scan Register Allocator";
00089     }
00090 
00091     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00092       AU.addRequired<LiveIntervals>();
00093       MachineFunctionPass::getAnalysisUsage(AU);
00094     }
00095 
00096     /// runOnMachineFunction - register allocate the whole function
00097     bool runOnMachineFunction(MachineFunction&);
00098 
00099   private:
00100     /// linearScan - the linear scan algorithm
00101     void linearScan();
00102 
00103     /// initIntervalSets - initialize the interval sets.
00104     ///
00105     void initIntervalSets();
00106 
00107     /// processActiveIntervals - expire old intervals and move non-overlapping
00108     /// ones to the inactive list.
00109     void processActiveIntervals(unsigned CurPoint);
00110 
00111     /// processInactiveIntervals - expire old intervals and move overlapping
00112     /// ones to the active list.
00113     void processInactiveIntervals(unsigned CurPoint);
00114 
00115     /// assignRegOrStackSlotAtInterval - assign a register if one
00116     /// is available, or spill.
00117     void assignRegOrStackSlotAtInterval(LiveInterval* cur);
00118 
00119     ///
00120     /// register handling helpers
00121     ///
00122 
00123     /// getFreePhysReg - return a free physical register for this virtual
00124     /// register interval if we have one, otherwise return 0.
00125     unsigned getFreePhysReg(LiveInterval* cur);
00126 
00127     /// assignVirt2StackSlot - assigns this virtual register to a
00128     /// stack slot. returns the stack slot
00129     int assignVirt2StackSlot(unsigned virtReg);
00130 
00131     void ComputeRelatedRegClasses();
00132 
00133     template <typename ItTy>
00134     void printIntervals(const char* const str, ItTy i, ItTy e) const {
00135       if (str) std::cerr << str << " intervals:\n";
00136       for (; i != e; ++i) {
00137         std::cerr << "\t" << *i->first << " -> ";
00138         unsigned reg = i->first->reg;
00139         if (MRegisterInfo::isVirtualRegister(reg)) {
00140           reg = vrm_->getPhys(reg);
00141         }
00142         std::cerr << mri_->getName(reg) << '\n';
00143       }
00144     }
00145   };
00146 }
00147 
00148 void RA::ComputeRelatedRegClasses() {
00149   const MRegisterInfo &MRI = *mri_;
00150   
00151   // First pass, add all reg classes to the union, and determine at least one
00152   // reg class that each register is in.
00153   bool HasAliases = false;
00154   for (MRegisterInfo::regclass_iterator RCI = MRI.regclass_begin(),
00155        E = MRI.regclass_end(); RCI != E; ++RCI) {
00156     RelatedRegClasses.insert(*RCI);
00157     for (TargetRegisterClass::iterator I = (*RCI)->begin(), E = (*RCI)->end();
00158          I != E; ++I) {
00159       HasAliases = HasAliases || *MRI.getAliasSet(*I) != 0;
00160       
00161       const TargetRegisterClass *&PRC = OneClassForEachPhysReg[*I];
00162       if (PRC) {
00163         // Already processed this register.  Just make sure we know that
00164         // multiple register classes share a register.
00165         RelatedRegClasses.unionSets(PRC, *RCI);
00166       } else {
00167         PRC = *RCI;
00168       }
00169     }
00170   }
00171   
00172   // Second pass, now that we know conservatively what register classes each reg
00173   // belongs to, add info about aliases.  We don't need to do this for targets
00174   // without register aliases.
00175   if (HasAliases)
00176     for (std::map<unsigned, const TargetRegisterClass*>::iterator
00177          I = OneClassForEachPhysReg.begin(), E = OneClassForEachPhysReg.end();
00178          I != E; ++I)
00179       for (const unsigned *AS = MRI.getAliasSet(I->first); *AS; ++AS)
00180         RelatedRegClasses.unionSets(I->second, OneClassForEachPhysReg[*AS]);
00181 }
00182 
00183 bool RA::runOnMachineFunction(MachineFunction &fn) {
00184   mf_ = &fn;
00185   tm_ = &fn.getTarget();
00186   mri_ = tm_->getRegisterInfo();
00187   li_ = &getAnalysis<LiveIntervals>();
00188 
00189   // If this is the first function compiled, compute the related reg classes.
00190   if (RelatedRegClasses.empty())
00191     ComputeRelatedRegClasses();
00192   
00193   PhysRegsUsed = new bool[mri_->getNumRegs()];
00194   std::fill(PhysRegsUsed, PhysRegsUsed+mri_->getNumRegs(), false);
00195   fn.setUsedPhysRegs(PhysRegsUsed);
00196 
00197   if (!prt_.get()) prt_.reset(new PhysRegTracker(*mri_));
00198   vrm_.reset(new VirtRegMap(*mf_));
00199   if (!spiller_.get()) spiller_.reset(createSpiller());
00200 
00201   initIntervalSets();
00202 
00203   linearScan();
00204 
00205   // Rewrite spill code and update the PhysRegsUsed set.
00206   spiller_->runOnMachineFunction(*mf_, *vrm_);
00207 
00208   vrm_.reset();  // Free the VirtRegMap
00209 
00210 
00211   while (!unhandled_.empty()) unhandled_.pop();
00212   fixed_.clear();
00213   active_.clear();
00214   inactive_.clear();
00215   handled_.clear();
00216 
00217   return true;
00218 }
00219 
00220 /// initIntervalSets - initialize the interval sets.
00221 ///
00222 void RA::initIntervalSets()
00223 {
00224   assert(unhandled_.empty() && fixed_.empty() &&
00225          active_.empty() && inactive_.empty() &&
00226          "interval sets should be empty on initialization");
00227 
00228   for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
00229     if (MRegisterInfo::isPhysicalRegister(i->second.reg)) {
00230       PhysRegsUsed[i->second.reg] = true;
00231       fixed_.push_back(std::make_pair(&i->second, i->second.begin()));
00232     } else
00233       unhandled_.push(&i->second);
00234   }
00235 }
00236 
00237 void RA::linearScan()
00238 {
00239   // linear scan algorithm
00240   DEBUG(std::cerr << "********** LINEAR SCAN **********\n");
00241   DEBUG(std::cerr << "********** Function: "
00242         << mf_->getFunction()->getName() << '\n');
00243 
00244   // DEBUG(printIntervals("unhandled", unhandled_.begin(), unhandled_.end()));
00245   DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end()));
00246   DEBUG(printIntervals("active", active_.begin(), active_.end()));
00247   DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
00248 
00249   while (!unhandled_.empty()) {
00250     // pick the interval with the earliest start point
00251     LiveInterval* cur = unhandled_.top();
00252     unhandled_.pop();
00253     ++numIterations;
00254     DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n');
00255 
00256     processActiveIntervals(cur->beginNumber());
00257     processInactiveIntervals(cur->beginNumber());
00258 
00259     assert(MRegisterInfo::isVirtualRegister(cur->reg) &&
00260            "Can only allocate virtual registers!");
00261 
00262     // Allocating a virtual register. try to find a free
00263     // physical register or spill an interval (possibly this one) in order to
00264     // assign it one.
00265     assignRegOrStackSlotAtInterval(cur);
00266 
00267     DEBUG(printIntervals("active", active_.begin(), active_.end()));
00268     DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
00269   }
00270   numIntervals += li_->getNumIntervals();
00271   efficiency = double(numIterations) / double(numIntervals);
00272 
00273   // expire any remaining active intervals
00274   for (IntervalPtrs::reverse_iterator
00275          i = active_.rbegin(); i != active_.rend(); ) {
00276     unsigned reg = i->first->reg;
00277     DEBUG(std::cerr << "\tinterval " << *i->first << " expired\n");
00278     assert(MRegisterInfo::isVirtualRegister(reg) &&
00279            "Can only allocate virtual registers!");
00280     reg = vrm_->getPhys(reg);
00281     prt_->delRegUse(reg);
00282     i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1));
00283   }
00284 
00285   // expire any remaining inactive intervals
00286   for (IntervalPtrs::reverse_iterator
00287          i = inactive_.rbegin(); i != inactive_.rend(); ) {
00288     DEBUG(std::cerr << "\tinterval " << *i->first << " expired\n");
00289     i = IntervalPtrs::reverse_iterator(inactive_.erase(i.base()-1));
00290   }
00291 
00292   DEBUG(std::cerr << *vrm_);
00293 }
00294 
00295 /// processActiveIntervals - expire old intervals and move non-overlapping ones
00296 /// to the inactive list.
00297 void RA::processActiveIntervals(unsigned CurPoint)
00298 {
00299   DEBUG(std::cerr << "\tprocessing active intervals:\n");
00300 
00301   for (unsigned i = 0, e = active_.size(); i != e; ++i) {
00302     LiveInterval *Interval = active_[i].first;
00303     LiveInterval::iterator IntervalPos = active_[i].second;
00304     unsigned reg = Interval->reg;
00305 
00306     IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
00307 
00308     if (IntervalPos == Interval->end()) {     // Remove expired intervals.
00309       DEBUG(std::cerr << "\t\tinterval " << *Interval << " expired\n");
00310       assert(MRegisterInfo::isVirtualRegister(reg) &&
00311              "Can only allocate virtual registers!");
00312       reg = vrm_->getPhys(reg);
00313       prt_->delRegUse(reg);
00314 
00315       // Pop off the end of the list.
00316       active_[i] = active_.back();
00317       active_.pop_back();
00318       --i; --e;
00319 
00320     } else if (IntervalPos->start > CurPoint) {
00321       // Move inactive intervals to inactive list.
00322       DEBUG(std::cerr << "\t\tinterval " << *Interval << " inactive\n");
00323       assert(MRegisterInfo::isVirtualRegister(reg) &&
00324              "Can only allocate virtual registers!");
00325       reg = vrm_->getPhys(reg);
00326       prt_->delRegUse(reg);
00327       // add to inactive.
00328       inactive_.push_back(std::make_pair(Interval, IntervalPos));
00329 
00330       // Pop off the end of the list.
00331       active_[i] = active_.back();
00332       active_.pop_back();
00333       --i; --e;
00334     } else {
00335       // Otherwise, just update the iterator position.
00336       active_[i].second = IntervalPos;
00337     }
00338   }
00339 }
00340 
00341 /// processInactiveIntervals - expire old intervals and move overlapping
00342 /// ones to the active list.
00343 void RA::processInactiveIntervals(unsigned CurPoint)
00344 {
00345   DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
00346 
00347   for (unsigned i = 0, e = inactive_.size(); i != e; ++i) {
00348     LiveInterval *Interval = inactive_[i].first;
00349     LiveInterval::iterator IntervalPos = inactive_[i].second;
00350     unsigned reg = Interval->reg;
00351 
00352     IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
00353 
00354     if (IntervalPos == Interval->end()) {       // remove expired intervals.
00355       DEBUG(std::cerr << "\t\tinterval " << *Interval << " expired\n");
00356 
00357       // Pop off the end of the list.
00358       inactive_[i] = inactive_.back();
00359       inactive_.pop_back();
00360       --i; --e;
00361     } else if (IntervalPos->start <= CurPoint) {
00362       // move re-activated intervals in active list
00363       DEBUG(std::cerr << "\t\tinterval " << *Interval << " active\n");
00364       assert(MRegisterInfo::isVirtualRegister(reg) &&
00365              "Can only allocate virtual registers!");
00366       reg = vrm_->getPhys(reg);
00367       prt_->addRegUse(reg);
00368       // add to active
00369       active_.push_back(std::make_pair(Interval, IntervalPos));
00370 
00371       // Pop off the end of the list.
00372       inactive_[i] = inactive_.back();
00373       inactive_.pop_back();
00374       --i; --e;
00375     } else {
00376       // Otherwise, just update the iterator position.
00377       inactive_[i].second = IntervalPos;
00378     }
00379   }
00380 }
00381 
00382 /// updateSpillWeights - updates the spill weights of the specifed physical
00383 /// register and its weight.
00384 static void updateSpillWeights(std::vector<float> &Weights,
00385                                unsigned reg, float weight,
00386                                const MRegisterInfo *MRI) {
00387   Weights[reg] += weight;
00388   for (const unsigned* as = MRI->getAliasSet(reg); *as; ++as)
00389     Weights[*as] += weight;
00390 }
00391 
00392 static RA::IntervalPtrs::iterator FindIntervalInVector(RA::IntervalPtrs &IP,
00393                                                        LiveInterval *LI) {
00394   for (RA::IntervalPtrs::iterator I = IP.begin(), E = IP.end(); I != E; ++I)
00395     if (I->first == LI) return I;
00396   return IP.end();
00397 }
00398 
00399 static void RevertVectorIteratorsTo(RA::IntervalPtrs &V, unsigned Point) {
00400   for (unsigned i = 0, e = V.size(); i != e; ++i) {
00401     RA::IntervalPtr &IP = V[i];
00402     LiveInterval::iterator I = std::upper_bound(IP.first->begin(),
00403                                                 IP.second, Point);
00404     if (I != IP.first->begin()) --I;
00405     IP.second = I;
00406   }
00407 }
00408 
00409 
00410 /// assignRegOrStackSlotAtInterval - assign a register if one is available, or
00411 /// spill.
00412 void RA::assignRegOrStackSlotAtInterval(LiveInterval* cur)
00413 {
00414   DEBUG(std::cerr << "\tallocating current interval: ");
00415 
00416   PhysRegTracker backupPrt = *prt_;
00417 
00418   std::vector<std::pair<unsigned, float> > SpillWeightsToAdd;
00419   unsigned StartPosition = cur->beginNumber();
00420   const TargetRegisterClass *RC = mf_->getSSARegMap()->getRegClass(cur->reg);
00421   const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
00422       
00423   // for every interval in inactive we overlap with, mark the
00424   // register as not free and update spill weights.
00425   for (IntervalPtrs::const_iterator i = inactive_.begin(),
00426          e = inactive_.end(); i != e; ++i) {
00427     unsigned Reg = i->first->reg;
00428     assert(MRegisterInfo::isVirtualRegister(Reg) &&
00429            "Can only allocate virtual registers!");
00430     const TargetRegisterClass *RegRC = mf_->getSSARegMap()->getRegClass(Reg);
00431     // If this is not in a related reg class to the register we're allocating, 
00432     // don't check it.
00433     if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader &&
00434         cur->overlapsFrom(*i->first, i->second-1)) {
00435       Reg = vrm_->getPhys(Reg);
00436       prt_->addRegUse(Reg);
00437       SpillWeightsToAdd.push_back(std::make_pair(Reg, i->first->weight));
00438     }
00439   }
00440   
00441   // Speculatively check to see if we can get a register right now.  If not,
00442   // we know we won't be able to by adding more constraints.  If so, we can
00443   // check to see if it is valid.  Doing an exhaustive search of the fixed_ list
00444   // is very bad (it contains all callee clobbered registers for any functions
00445   // with a call), so we want to avoid doing that if possible.
00446   unsigned physReg = getFreePhysReg(cur);
00447   if (physReg) {
00448     // We got a register.  However, if it's in the fixed_ list, we might
00449     // conflict with it.  Check to see if we conflict with it or any of its
00450     // aliases.
00451     std::set<unsigned> RegAliases;
00452     for (const unsigned *AS = mri_->getAliasSet(physReg); *AS; ++AS)
00453       RegAliases.insert(*AS);
00454     
00455     bool ConflictsWithFixed = false;
00456     for (unsigned i = 0, e = fixed_.size(); i != e; ++i) {
00457       if (physReg == fixed_[i].first->reg ||
00458           RegAliases.count(fixed_[i].first->reg)) {
00459         // Okay, this reg is on the fixed list.  Check to see if we actually
00460         // conflict.
00461         IntervalPtr &IP = fixed_[i];
00462         LiveInterval *I = IP.first;
00463         if (I->endNumber() > StartPosition) {
00464           LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition);
00465           IP.second = II;
00466           if (II != I->begin() && II->start > StartPosition)
00467             --II;
00468           if (cur->overlapsFrom(*I, II)) {
00469             ConflictsWithFixed = true;
00470             break;
00471           }
00472         }
00473       }
00474     }
00475     
00476     // Okay, the register picked by our speculative getFreePhysReg call turned
00477     // out to be in use.  Actually add all of the conflicting fixed registers to
00478     // prt so we can do an accurate query.
00479     if (ConflictsWithFixed) {
00480       // For every interval in fixed we overlap with, mark the register as not
00481       // free and update spill weights.
00482       for (unsigned i = 0, e = fixed_.size(); i != e; ++i) {
00483         IntervalPtr &IP = fixed_[i];
00484         LiveInterval *I = IP.first;
00485 
00486         const TargetRegisterClass *RegRC = OneClassForEachPhysReg[I->reg];
00487         if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader &&       
00488             I->endNumber() > StartPosition) {
00489           LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition);
00490           IP.second = II;
00491           if (II != I->begin() && II->start > StartPosition)
00492             --II;
00493           if (cur->overlapsFrom(*I, II)) {
00494             unsigned reg = I->reg;
00495             prt_->addRegUse(reg);
00496             SpillWeightsToAdd.push_back(std::make_pair(reg, I->weight));
00497           }
00498         }
00499       }
00500 
00501       // Using the newly updated prt_ object, which includes conflicts in the
00502       // future, see if there are any registers available.
00503       physReg = getFreePhysReg(cur);
00504     }
00505   }
00506     
00507   // Restore the physical register tracker, removing information about the
00508   // future.
00509   *prt_ = backupPrt;
00510   
00511   // if we find a free register, we are done: assign this virtual to
00512   // the free physical register and add this interval to the active
00513   // list.
00514   if (physReg) {
00515     DEBUG(std::cerr <<  mri_->getName(physReg) << '\n');
00516     vrm_->assignVirt2Phys(cur->reg, physReg);
00517     prt_->addRegUse(physReg);
00518     active_.push_back(std::make_pair(cur, cur->begin()));
00519     handled_.push_back(cur);
00520     return;
00521   }
00522   DEBUG(std::cerr << "no free registers\n");
00523 
00524   // Compile the spill weights into an array that is better for scanning.
00525   std::vector<float> SpillWeights(mri_->getNumRegs(), 0.0);
00526   for (std::vector<std::pair<unsigned, float> >::iterator
00527        I = SpillWeightsToAdd.begin(), E = SpillWeightsToAdd.end(); I != E; ++I)
00528     updateSpillWeights(SpillWeights, I->first, I->second, mri_);
00529   
00530   // for each interval in active, update spill weights.
00531   for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
00532        i != e; ++i) {
00533     unsigned reg = i->first->reg;
00534     assert(MRegisterInfo::isVirtualRegister(reg) &&
00535            "Can only allocate virtual registers!");
00536     reg = vrm_->getPhys(reg);
00537     updateSpillWeights(SpillWeights, reg, i->first->weight, mri_);
00538   }
00539  
00540   DEBUG(std::cerr << "\tassigning stack slot at interval "<< *cur << ":\n");
00541 
00542   // Find a register to spill.
00543   float minWeight = float(HUGE_VAL);
00544   unsigned minReg = 0;
00545   for (TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_),
00546        e = RC->allocation_order_end(*mf_); i != e; ++i) {
00547     unsigned reg = *i;
00548     if (minWeight > SpillWeights[reg]) {
00549       minWeight = SpillWeights[reg];
00550       minReg = reg;
00551     }
00552   }
00553   
00554   // If we didn't find a register that is spillable, try aliases?
00555   
00556 // FIXME:  assert(minReg && "Didn't find any reg!");
00557   DEBUG(std::cerr << "\t\tregister with min weight: "
00558         << mri_->getName(minReg) << " (" << minWeight << ")\n");
00559 
00560   // if the current has the minimum weight, we need to spill it and
00561   // add any added intervals back to unhandled, and restart
00562   // linearscan.
00563   if (cur->weight <= minWeight) {
00564     DEBUG(std::cerr << "\t\t\tspilling(c): " << *cur << '\n';);
00565     int slot = vrm_->assignVirt2StackSlot(cur->reg);
00566     std::vector<LiveInterval*> added =
00567       li_->addIntervalsForSpills(*cur, *vrm_, slot);
00568     if (added.empty())
00569       return;  // Early exit if all spills were folded.
00570 
00571     // Merge added with unhandled.  Note that we know that
00572     // addIntervalsForSpills returns intervals sorted by their starting
00573     // point.
00574     for (unsigned i = 0, e = added.size(); i != e; ++i)
00575       unhandled_.push(added[i]);
00576     return;
00577   }
00578 
00579   ++NumBacktracks;
00580 
00581   // push the current interval back to unhandled since we are going
00582   // to re-run at least this iteration. Since we didn't modify it it
00583   // should go back right in the front of the list
00584   unhandled_.push(cur);
00585 
00586   // otherwise we spill all intervals aliasing the register with
00587   // minimum weight, rollback to the interval with the earliest
00588   // start point and let the linear scan algorithm run again
00589   std::vector<LiveInterval*> added;
00590   assert(MRegisterInfo::isPhysicalRegister(minReg) &&
00591          "did not choose a register to spill?");
00592   std::vector<bool> toSpill(mri_->getNumRegs(), false);
00593 
00594   // We are going to spill minReg and all its aliases.
00595   toSpill[minReg] = true;
00596   for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
00597     toSpill[*as] = true;
00598 
00599   // the earliest start of a spilled interval indicates up to where
00600   // in handled we need to roll back
00601   unsigned earliestStart = cur->beginNumber();
00602 
00603   // set of spilled vregs (used later to rollback properly)
00604   std::set<unsigned> spilled;
00605 
00606   // spill live intervals of virtual regs mapped to the physical register we
00607   // want to clear (and its aliases).  We only spill those that overlap with the
00608   // current interval as the rest do not affect its allocation. we also keep
00609   // track of the earliest start of all spilled live intervals since this will
00610   // mark our rollback point.
00611   for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
00612     unsigned reg = i->first->reg;
00613     if (//MRegisterInfo::isVirtualRegister(reg) &&
00614         toSpill[vrm_->getPhys(reg)] &&
00615         cur->overlapsFrom(*i->first, i->second)) {
00616       DEBUG(std::cerr << "\t\t\tspilling(a): " << *i->first << '\n');
00617       earliestStart = std::min(earliestStart, i->first->beginNumber());
00618       int slot = vrm_->assignVirt2StackSlot(i->first->reg);
00619       std::vector<LiveInterval*> newIs =
00620         li_->addIntervalsForSpills(*i->first, *vrm_, slot);
00621       std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
00622       spilled.insert(reg);
00623     }
00624   }
00625   for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end(); ++i){
00626     unsigned reg = i->first->reg;
00627     if (//MRegisterInfo::isVirtualRegister(reg) &&
00628         toSpill[vrm_->getPhys(reg)] &&
00629         cur->overlapsFrom(*i->first, i->second-1)) {
00630       DEBUG(std::cerr << "\t\t\tspilling(i): " << *i->first << '\n');
00631       earliestStart = std::min(earliestStart, i->first->beginNumber());
00632       int slot = vrm_->assignVirt2StackSlot(reg);
00633       std::vector<LiveInterval*> newIs =
00634         li_->addIntervalsForSpills(*i->first, *vrm_, slot);
00635       std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
00636       spilled.insert(reg);
00637     }
00638   }
00639 
00640   DEBUG(std::cerr << "\t\trolling back to: " << earliestStart << '\n');
00641 
00642   // Scan handled in reverse order up to the earliest start of a
00643   // spilled live interval and undo each one, restoring the state of
00644   // unhandled.
00645   while (!handled_.empty()) {
00646     LiveInterval* i = handled_.back();
00647     // If this interval starts before t we are done.
00648     if (i->beginNumber() < earliestStart)
00649       break;
00650     DEBUG(std::cerr << "\t\t\tundo changes for: " << *i << '\n');
00651     handled_.pop_back();
00652 
00653     // When undoing a live interval allocation we must know if it is active or
00654     // inactive to properly update the PhysRegTracker and the VirtRegMap.
00655     IntervalPtrs::iterator it;
00656     if ((it = FindIntervalInVector(active_, i)) != active_.end()) {
00657       active_.erase(it);
00658       assert(!MRegisterInfo::isPhysicalRegister(i->reg));
00659       if (!spilled.count(i->reg))
00660         unhandled_.push(i);
00661       prt_->delRegUse(vrm_->getPhys(i->reg));
00662       vrm_->clearVirt(i->reg);
00663     } else if ((it = FindIntervalInVector(inactive_, i)) != inactive_.end()) {
00664       inactive_.erase(it);
00665       assert(!MRegisterInfo::isPhysicalRegister(i->reg));
00666       if (!spilled.count(i->reg))
00667         unhandled_.push(i);
00668       vrm_->clearVirt(i->reg);
00669     } else {
00670       assert(MRegisterInfo::isVirtualRegister(i->reg) &&
00671              "Can only allocate virtual registers!");
00672       vrm_->clearVirt(i->reg);
00673       unhandled_.push(i);
00674     }
00675   }
00676 
00677   // Rewind the iterators in the active, inactive, and fixed lists back to the
00678   // point we reverted to.
00679   RevertVectorIteratorsTo(active_, earliestStart);
00680   RevertVectorIteratorsTo(inactive_, earliestStart);
00681   RevertVectorIteratorsTo(fixed_, earliestStart);
00682 
00683   // scan the rest and undo each interval that expired after t and
00684   // insert it in active (the next iteration of the algorithm will
00685   // put it in inactive if required)
00686   for (unsigned i = 0, e = handled_.size(); i != e; ++i) {
00687     LiveInterval *HI = handled_[i];
00688     if (!HI->expiredAt(earliestStart) &&
00689         HI->expiredAt(cur->beginNumber())) {
00690       DEBUG(std::cerr << "\t\t\tundo changes for: " << *HI << '\n');
00691       active_.push_back(std::make_pair(HI, HI->begin()));
00692       assert(!MRegisterInfo::isPhysicalRegister(HI->reg));
00693       prt_->addRegUse(vrm_->getPhys(HI->reg));
00694     }
00695   }
00696 
00697   // merge added with unhandled
00698   for (unsigned i = 0, e = added.size(); i != e; ++i)
00699     unhandled_.push(added[i]);
00700 }
00701 
00702 /// getFreePhysReg - return a free physical register for this virtual register
00703 /// interval if we have one, otherwise return 0.
00704 unsigned RA::getFreePhysReg(LiveInterval *cur) {
00705   std::vector<unsigned> inactiveCounts(mri_->getNumRegs(), 0);
00706   unsigned MaxInactiveCount = 0;
00707   
00708   const TargetRegisterClass *RC = mf_->getSSARegMap()->getRegClass(cur->reg);
00709   const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
00710  
00711   for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end();
00712        i != e; ++i) {
00713     unsigned reg = i->first->reg;
00714     assert(MRegisterInfo::isVirtualRegister(reg) &&
00715            "Can only allocate virtual registers!");
00716 
00717     // If this is not in a related reg class to the register we're allocating, 
00718     // don't check it.
00719     const TargetRegisterClass *RegRC = mf_->getSSARegMap()->getRegClass(reg);
00720     if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader) {
00721       reg = vrm_->getPhys(reg);
00722       ++inactiveCounts[reg];
00723       MaxInactiveCount = std::max(MaxInactiveCount, inactiveCounts[reg]);
00724     }
00725   }
00726 
00727   const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
00728 
00729   unsigned FreeReg = 0;
00730   unsigned FreeRegInactiveCount = 0;
00731   
00732   // Scan for the first available register.
00733   TargetRegisterClass::iterator I = rc->allocation_order_begin(*mf_);
00734   TargetRegisterClass::iterator E = rc->allocation_order_end(*mf_);
00735   for (; I != E; ++I)
00736     if (prt_->isRegAvail(*I)) {
00737       FreeReg = *I;
00738       FreeRegInactiveCount = inactiveCounts[FreeReg];
00739       break;
00740     }
00741   
00742   // If there are no free regs, or if this reg has the max inactive count,
00743   // return this register.
00744   if (FreeReg == 0 || FreeRegInactiveCount == MaxInactiveCount) return FreeReg;
00745   
00746   // Continue scanning the registers, looking for the one with the highest
00747   // inactive count.  Alkis found that this reduced register pressure very
00748   // slightly on X86 (in rev 1.94 of this file), though this should probably be
00749   // reevaluated now.
00750   for (; I != E; ++I) {
00751     unsigned Reg = *I;
00752     if (prt_->isRegAvail(Reg) && FreeRegInactiveCount < inactiveCounts[Reg]) {
00753       FreeReg = Reg;
00754       FreeRegInactiveCount = inactiveCounts[Reg];
00755       if (FreeRegInactiveCount == MaxInactiveCount)
00756         break;    // We found the one with the max inactive count.
00757     }
00758   }
00759   
00760   return FreeReg;
00761 }
00762 
00763 FunctionPass* llvm::createLinearScanRegisterAllocator() {
00764   return new RA();
00765 }