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 <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 }