LLVM API Documentation
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 }