LLVM API Documentation

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

RegAllocIterativeScan.cpp

Go to the documentation of this file.
00001 //===-- RegAllocIterativeScan.cpp - Iterative 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 an iterative scan register
00011 // allocator. Iterative scan is a linear scan variant with the
00012 // following difference:
00013 //
00014 // It performs linear scan and keeps a list of the registers it cannot
00015 // allocate. It then spills all those registers and repeats the
00016 // process until allocation succeeds.
00017 //
00018 //===----------------------------------------------------------------------===//
00019 
00020 #define DEBUG_TYPE "regalloc"
00021 #include "llvm/Function.h"
00022 #include "llvm/CodeGen/MachineFunctionPass.h"
00023 #include "llvm/CodeGen/MachineInstr.h"
00024 #include "llvm/CodeGen/Passes.h"
00025 #include "llvm/CodeGen/SSARegMap.h"
00026 #include "llvm/Target/MRegisterInfo.h"
00027 #include "llvm/Target/TargetMachine.h"
00028 #include "llvm/Support/Debug.h"
00029 #include "llvm/ADT/Statistic.h"
00030 #include "llvm/ADT/STLExtras.h"
00031 #include "LiveIntervalAnalysis.h"
00032 #include "PhysRegTracker.h"
00033 #include "VirtRegMap.h"
00034 #include <algorithm>
00035 #include <cmath>
00036 #include <set>
00037 
00038 using namespace llvm;
00039 
00040 namespace {
00041 
00042   Statistic<double> efficiency
00043   ("regalloc", "Ratio of intervals processed over total intervals");
00044 
00045   static unsigned numIterations = 0;
00046   static unsigned numIntervals = 0;
00047 
00048   class RA : public MachineFunctionPass {
00049   private:
00050     MachineFunction* mf_;
00051     const TargetMachine* tm_;
00052     const MRegisterInfo* mri_;
00053     LiveIntervals* li_;
00054     typedef std::vector<LiveInterval*> IntervalPtrs;
00055     IntervalPtrs unhandled_, fixed_, active_, inactive_, handled_, spilled_;
00056 
00057     std::auto_ptr<PhysRegTracker> prt_;
00058     std::auto_ptr<VirtRegMap> vrm_;
00059     std::auto_ptr<Spiller> spiller_;
00060 
00061     typedef std::vector<float> SpillWeights;
00062     SpillWeights spillWeights_;
00063 
00064   public:
00065     virtual const char* getPassName() const {
00066       return "Iterative Scan Register Allocator";
00067     }
00068 
00069     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00070       AU.addRequired<LiveIntervals>();
00071       MachineFunctionPass::getAnalysisUsage(AU);
00072     }
00073 
00074     /// runOnMachineFunction - register allocate the whole function
00075     bool runOnMachineFunction(MachineFunction&);
00076 
00077     void releaseMemory();
00078 
00079   private:
00080     /// linearScan - the linear scan algorithm. Returns a boolean
00081     /// indicating if there were any spills
00082     bool linearScan();
00083 
00084     /// initIntervalSets - initializes the four interval sets:
00085     /// unhandled, fixed, active and inactive
00086     void initIntervalSets();
00087 
00088     /// processActiveIntervals - expire old intervals and move
00089     /// non-overlapping ones to the incative list
00090     void processActiveIntervals(IntervalPtrs::value_type cur);
00091 
00092     /// processInactiveIntervals - expire old intervals and move
00093     /// overlapping ones to the active list
00094     void processInactiveIntervals(IntervalPtrs::value_type cur);
00095 
00096     /// updateSpillWeights - updates the spill weights of the
00097     /// specifed physical register and its weight
00098     void updateSpillWeights(unsigned reg, SpillWeights::value_type weight);
00099 
00100     /// assignRegOrStackSlotAtInterval - assign a register if one
00101     /// is available, or spill.
00102     void assignRegOrSpillAtInterval(IntervalPtrs::value_type cur);
00103 
00104     ///
00105     /// register handling helpers
00106     ///
00107 
00108     /// getFreePhysReg - return a free physical register for this
00109     /// virtual register interval if we have one, otherwise return
00110     /// 0
00111     unsigned getFreePhysReg(IntervalPtrs::value_type cur);
00112 
00113     /// assignVirt2StackSlot - assigns this virtual register to a
00114     /// stack slot. returns the stack slot
00115     int assignVirt2StackSlot(unsigned virtReg);
00116 
00117     void printIntervals(const char* const str,
00118                         RA::IntervalPtrs::const_iterator i,
00119                         RA::IntervalPtrs::const_iterator e) const {
00120       if (str) std::cerr << str << " intervals:\n";
00121       for (; i != e; ++i) {
00122         std::cerr << "\t" << **i << " -> ";
00123         unsigned reg = (*i)->reg;
00124         if (MRegisterInfo::isVirtualRegister(reg)) {
00125           reg = vrm_->getPhys(reg);
00126         }
00127         std::cerr << mri_->getName(reg) << '\n';
00128       }
00129     }
00130   };
00131 }
00132 
00133 void RA::releaseMemory()
00134 {
00135   unhandled_.clear();
00136   fixed_.clear();
00137   active_.clear();
00138   inactive_.clear();
00139   handled_.clear();
00140   spilled_.clear();
00141 }
00142 
00143 bool RA::runOnMachineFunction(MachineFunction &fn) {
00144   mf_ = &fn;
00145   tm_ = &fn.getTarget();
00146   mri_ = tm_->getRegisterInfo();
00147   li_ = &getAnalysis<LiveIntervals>();
00148   if (!prt_.get()) prt_.reset(new PhysRegTracker(*mri_));
00149   vrm_.reset(new VirtRegMap(*mf_));
00150   if (!spiller_.get()) spiller_.reset(createSpiller());
00151 
00152   initIntervalSets();
00153 
00154   numIntervals += li_->getNumIntervals();
00155 
00156   while (linearScan()) {
00157     // we spilled some registers, so we need to add intervals for
00158     // the spill code and restart the algorithm
00159     std::set<unsigned> spilledRegs;
00160     for (IntervalPtrs::iterator
00161            i = spilled_.begin(); i != spilled_.end(); ++i) {
00162       int slot = vrm_->assignVirt2StackSlot((*i)->reg);
00163       std::vector<LiveInterval*> added =
00164         li_->addIntervalsForSpills(**i, *vrm_, slot);
00165       std::copy(added.begin(), added.end(), std::back_inserter(handled_));
00166       spilledRegs.insert((*i)->reg);
00167     }
00168     spilled_.clear();
00169     for (IntervalPtrs::iterator
00170            i = handled_.begin(); i != handled_.end(); )
00171       if (spilledRegs.count((*i)->reg))
00172         i = handled_.erase(i);
00173       else
00174         ++i;
00175     handled_.swap(unhandled_);
00176     vrm_->clearAllVirt();
00177   }
00178 
00179   efficiency = double(numIterations) / double(numIntervals);
00180 
00181   DEBUG(std::cerr << *vrm_);
00182 
00183   spiller_->runOnMachineFunction(*mf_, *vrm_);
00184 
00185   return true;
00186 }
00187 
00188 bool RA::linearScan()
00189 {
00190   // linear scan algorithm
00191   DEBUG(std::cerr << "********** LINEAR SCAN **********\n");
00192   DEBUG(std::cerr << "********** Function: "
00193         << mf_->getFunction()->getName() << '\n');
00194 
00195 
00196   std::sort(unhandled_.begin(), unhandled_.end(),
00197             greater_ptr<LiveInterval>());
00198   DEBUG(printIntervals("unhandled", unhandled_.begin(), unhandled_.end()));
00199   DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end()));
00200   DEBUG(printIntervals("active", active_.begin(), active_.end()));
00201   DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
00202 
00203   while (!unhandled_.empty()) {
00204     // pick the interval with the earliest start point
00205     IntervalPtrs::value_type cur = unhandled_.back();
00206     unhandled_.pop_back();
00207     ++numIterations;
00208     DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n');
00209 
00210     processActiveIntervals(cur);
00211     processInactiveIntervals(cur);
00212 
00213     // if this register is fixed we are done
00214     if (MRegisterInfo::isPhysicalRegister(cur->reg)) {
00215       prt_->addRegUse(cur->reg);
00216       active_.push_back(cur);
00217       handled_.push_back(cur);
00218     }
00219     // otherwise we are allocating a virtual register. try to find
00220     // a free physical register or spill an interval in order to
00221     // assign it one (we could spill the current though).
00222     else {
00223       assignRegOrSpillAtInterval(cur);
00224     }
00225 
00226     DEBUG(printIntervals("active", active_.begin(), active_.end()));
00227     DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
00228   }
00229 
00230   // expire any remaining active intervals
00231   for (IntervalPtrs::reverse_iterator
00232          i = active_.rbegin(); i != active_.rend(); ) {
00233     unsigned reg = (*i)->reg;
00234     DEBUG(std::cerr << "\tinterval " << **i << " expired\n");
00235     if (MRegisterInfo::isVirtualRegister(reg))
00236       reg = vrm_->getPhys(reg);
00237     prt_->delRegUse(reg);
00238     i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1));
00239   }
00240 
00241   // expire any remaining inactive intervals
00242   for (IntervalPtrs::reverse_iterator
00243          i = inactive_.rbegin(); i != inactive_.rend(); ) {
00244     DEBUG(std::cerr << "\tinterval " << **i << " expired\n");
00245     i = IntervalPtrs::reverse_iterator(inactive_.erase(i.base()-1));
00246   }
00247 
00248   // return true if we spilled anything
00249   return !spilled_.empty();
00250 }
00251 
00252 void RA::initIntervalSets() {
00253   assert(unhandled_.empty() && fixed_.empty() &&
00254          active_.empty() && inactive_.empty() &&
00255          "interval sets should be empty on initialization");
00256 
00257   for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i){
00258     unhandled_.push_back(&i->second);
00259     if (MRegisterInfo::isPhysicalRegister(i->second.reg))
00260       fixed_.push_back(&i->second);
00261   }
00262 }
00263 
00264 void RA::processActiveIntervals(IntervalPtrs::value_type cur)
00265 {
00266   DEBUG(std::cerr << "\tprocessing active intervals:\n");
00267   IntervalPtrs::iterator ii = active_.begin(), ie = active_.end();
00268   while (ii != ie) {
00269     LiveInterval* i = *ii;
00270     unsigned reg = i->reg;
00271 
00272     // remove expired intervals
00273     if (i->expiredAt(cur->beginNumber())) {
00274       DEBUG(std::cerr << "\t\tinterval " << *i << " expired\n");
00275       if (MRegisterInfo::isVirtualRegister(reg))
00276         reg = vrm_->getPhys(reg);
00277       prt_->delRegUse(reg);
00278       // swap with last element and move end iterator back one position
00279       std::iter_swap(ii, --ie);
00280     }
00281     // move inactive intervals to inactive list
00282     else if (!i->liveAt(cur->beginNumber())) {
00283       DEBUG(std::cerr << "\t\tinterval " << *i << " inactive\n");
00284       if (MRegisterInfo::isVirtualRegister(reg))
00285         reg = vrm_->getPhys(reg);
00286       prt_->delRegUse(reg);
00287       // add to inactive
00288       inactive_.push_back(i);
00289       // swap with last element and move end iterator back one postion
00290       std::iter_swap(ii, --ie);
00291     }
00292     else {
00293       ++ii;
00294     }
00295   }
00296   active_.erase(ie, active_.end());
00297 }
00298 
00299 void RA::processInactiveIntervals(IntervalPtrs::value_type cur)
00300 {
00301   DEBUG(std::cerr << "\tprocessing inactive intervals:\n");
00302   IntervalPtrs::iterator ii = inactive_.begin(), ie = inactive_.end();
00303   while (ii != ie) {
00304     LiveInterval* i = *ii;
00305     unsigned reg = i->reg;
00306 
00307     // remove expired intervals
00308     if (i->expiredAt(cur->beginNumber())) {
00309       DEBUG(std::cerr << "\t\tinterval " << *i << " expired\n");
00310       // swap with last element and move end iterator back one position
00311       std::iter_swap(ii, --ie);
00312     }
00313     // move re-activated intervals in active list
00314     else if (i->liveAt(cur->beginNumber())) {
00315       DEBUG(std::cerr << "\t\tinterval " << *i << " active\n");
00316       if (MRegisterInfo::isVirtualRegister(reg))
00317         reg = vrm_->getPhys(reg);
00318       prt_->addRegUse(reg);
00319       // add to active
00320       active_.push_back(i);
00321       // swap with last element and move end iterator back one position
00322       std::iter_swap(ii, --ie);
00323     }
00324     else {
00325       ++ii;
00326     }
00327   }
00328   inactive_.erase(ie, inactive_.end());
00329 }
00330 
00331 void RA::updateSpillWeights(unsigned reg, SpillWeights::value_type weight)
00332 {
00333   spillWeights_[reg] += weight;
00334   for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
00335     spillWeights_[*as] += weight;
00336 }
00337 
00338 void RA::assignRegOrSpillAtInterval(IntervalPtrs::value_type cur)
00339 {
00340   DEBUG(std::cerr << "\tallocating current interval: ");
00341 
00342   PhysRegTracker backupPrt = *prt_;
00343 
00344   spillWeights_.assign(mri_->getNumRegs(), 0.0);
00345 
00346   // for each interval in active update spill weights
00347   for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
00348        i != e; ++i) {
00349     unsigned reg = (*i)->reg;
00350     if (MRegisterInfo::isVirtualRegister(reg))
00351       reg = vrm_->getPhys(reg);
00352     updateSpillWeights(reg, (*i)->weight);
00353   }
00354 
00355   // for every interval in inactive we overlap with, mark the
00356   // register as not free and update spill weights
00357   for (IntervalPtrs::const_iterator i = inactive_.begin(),
00358          e = inactive_.end(); i != e; ++i) {
00359     if (cur->overlaps(**i)) {
00360       unsigned reg = (*i)->reg;
00361       if (MRegisterInfo::isVirtualRegister(reg))
00362         reg = vrm_->getPhys(reg);
00363       prt_->addRegUse(reg);
00364       updateSpillWeights(reg, (*i)->weight);
00365     }
00366   }
00367 
00368   // for every interval in fixed we overlap with,
00369   // mark the register as not free and update spill weights
00370   for (IntervalPtrs::const_iterator i = fixed_.begin(),
00371          e = fixed_.end(); i != e; ++i) {
00372     if (cur->overlaps(**i)) {
00373       unsigned reg = (*i)->reg;
00374       prt_->addRegUse(reg);
00375       updateSpillWeights(reg, (*i)->weight);
00376     }
00377   }
00378 
00379   unsigned physReg = getFreePhysReg(cur);
00380   // restore the physical register tracker
00381   *prt_ = backupPrt;
00382   // if we find a free register, we are done: assign this virtual to
00383   // the free physical register and add this interval to the active
00384   // list.
00385   if (physReg) {
00386     DEBUG(std::cerr <<  mri_->getName(physReg) << '\n');
00387     vrm_->assignVirt2Phys(cur->reg, physReg);
00388     prt_->addRegUse(physReg);
00389     active_.push_back(cur);
00390     handled_.push_back(cur);
00391     return;
00392   }
00393   DEBUG(std::cerr << "no free registers\n");
00394 
00395   DEBUG(std::cerr << "\tassigning stack slot at interval "<< *cur << ":\n");
00396 
00397   float minWeight = HUGE_VAL;
00398   unsigned minReg = 0;
00399   const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
00400   for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
00401        i != rc->allocation_order_end(*mf_); ++i) {
00402     unsigned reg = *i;
00403     if (minWeight > spillWeights_[reg]) {
00404       minWeight = spillWeights_[reg];
00405       minReg = reg;
00406     }
00407   }
00408   DEBUG(std::cerr << "\t\tregister with min weight: "
00409         << mri_->getName(minReg) << " (" << minWeight << ")\n");
00410 
00411   // if the current has the minimum weight, we spill it and move on
00412   if (cur->weight <= minWeight) {
00413     DEBUG(std::cerr << "\t\t\tspilling(c): " << *cur << '\n');
00414     spilled_.push_back(cur);
00415     return;
00416   }
00417 
00418   // otherwise we spill all intervals aliasing the register with
00419   // minimum weight, assigned the newly cleared register to the
00420   // current interval and continue
00421   assert(MRegisterInfo::isPhysicalRegister(minReg) &&
00422          "did not choose a register to spill?");
00423   std::vector<bool> toSpill(mri_->getNumRegs(), false);
00424   toSpill[minReg] = true;
00425   for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as)
00426     toSpill[*as] = true;
00427   unsigned earliestStart = cur->beginNumber();
00428 
00429   std::set<unsigned> spilled;
00430 
00431   for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ) {
00432     unsigned reg = (*i)->reg;
00433     if (MRegisterInfo::isVirtualRegister(reg) &&
00434         toSpill[vrm_->getPhys(reg)] &&
00435         cur->overlaps(**i)) {
00436       DEBUG(std::cerr << "\t\t\tspilling(a): " << **i << '\n');
00437       spilled_.push_back(*i);
00438       prt_->delRegUse(vrm_->getPhys(reg));
00439       vrm_->clearVirt(reg);
00440       i = active_.erase(i);
00441     }
00442     else
00443       ++i;
00444   }
00445   for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end(); ) {
00446     unsigned reg = (*i)->reg;
00447     if (MRegisterInfo::isVirtualRegister(reg) &&
00448         toSpill[vrm_->getPhys(reg)] &&
00449         cur->overlaps(**i)) {
00450       DEBUG(std::cerr << "\t\t\tspilling(i): " << **i << '\n');
00451       spilled_.push_back(*i);
00452       vrm_->clearVirt(reg);
00453       i = inactive_.erase(i);
00454     }
00455     else
00456       ++i;
00457   }
00458 
00459   vrm_->assignVirt2Phys(cur->reg, minReg);
00460   prt_->addRegUse(minReg);
00461   active_.push_back(cur);
00462   handled_.push_back(cur);
00463 
00464 }
00465 
00466 unsigned RA::getFreePhysReg(LiveInterval* cur)
00467 {
00468   std::vector<unsigned> inactiveCounts(mri_->getNumRegs(), 0);
00469   for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end();
00470        i != e; ++i) {
00471     unsigned reg = (*i)->reg;
00472     if (MRegisterInfo::isVirtualRegister(reg))
00473       reg = vrm_->getPhys(reg);
00474     ++inactiveCounts[reg];
00475   }
00476 
00477   const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg);
00478 
00479   unsigned freeReg = 0;
00480   for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_);
00481        i != rc->allocation_order_end(*mf_); ++i) {
00482     unsigned reg = *i;
00483     if (prt_->isRegAvail(reg) &&
00484         (!freeReg || inactiveCounts[freeReg] < inactiveCounts[reg]))
00485         freeReg = reg;
00486   }
00487   return freeReg;
00488 }
00489 
00490 FunctionPass* llvm::createIterativeScanRegisterAllocator() {
00491   return new RA();
00492 }