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