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/Function.h" 00016 #include "llvm/CodeGen/MachineFunctionPass.h" 00017 #include "llvm/CodeGen/MachineInstr.h" 00018 #include "llvm/CodeGen/Passes.h" 00019 #include "llvm/CodeGen/SSARegMap.h" 00020 #include "llvm/Target/MRegisterInfo.h" 00021 #include "llvm/Target/TargetMachine.h" 00022 #include "llvm/Support/Debug.h" 00023 #include "llvm/ADT/Statistic.h" 00024 #include "llvm/ADT/STLExtras.h" 00025 #include "LiveIntervalAnalysis.h" 00026 #include "PhysRegTracker.h" 00027 #include "VirtRegMap.h" 00028 #include <algorithm> 00029 #include <cmath> 00030 #include <set> 00031 #include <queue> 00032 using namespace llvm; 00033 00034 namespace { 00035 00036 Statistic<double> efficiency 00037 ("regalloc", "Ratio of intervals processed over total intervals"); 00038 Statistic<> NumBacktracks("regalloc", "Number of times we had to backtrack"); 00039 00040 static unsigned numIterations = 0; 00041 static unsigned numIntervals = 0; 00042 00043 struct RA : public MachineFunctionPass { 00044 typedef std::pair<LiveInterval*, LiveInterval::iterator> IntervalPtr; 00045 typedef std::vector<IntervalPtr> IntervalPtrs; 00046 private: 00047 MachineFunction* mf_; 00048 const TargetMachine* tm_; 00049 const MRegisterInfo* mri_; 00050 LiveIntervals* li_; 00051 00052 /// handled_ - Intervals are added to the handled_ set in the order of their 00053 /// start value. This is uses for backtracking. 00054 std::vector<LiveInterval*> handled_; 00055 00056 /// fixed_ - Intervals that correspond to machine registers. 00057 /// 00058 IntervalPtrs fixed_; 00059 00060 /// active_ - Intervals that are currently being processed, and which have a 00061 /// live range active for the current point. 00062 IntervalPtrs active_; 00063 00064 /// inactive_ - Intervals that are currently being processed, but which have 00065 /// a hold at the current point. 00066 IntervalPtrs inactive_; 00067 00068 typedef std::priority_queue<LiveInterval*, 00069 std::vector<LiveInterval*>, 00070 greater_ptr<LiveInterval> > IntervalHeap; 00071 IntervalHeap unhandled_; 00072 std::auto_ptr<PhysRegTracker> prt_; 00073 std::auto_ptr<VirtRegMap> vrm_; 00074 std::auto_ptr<Spiller> spiller_; 00075 00076 public: 00077 virtual const char* getPassName() const { 00078 return "Linear Scan Register Allocator"; 00079 } 00080 00081 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00082 AU.addRequired<LiveIntervals>(); 00083 MachineFunctionPass::getAnalysisUsage(AU); 00084 } 00085 00086 /// runOnMachineFunction - register allocate the whole function 00087 bool runOnMachineFunction(MachineFunction&); 00088 00089 private: 00090 /// linearScan - the linear scan algorithm 00091 void linearScan(); 00092 00093 /// initIntervalSets - initialize the interval sets. 00094 /// 00095 void initIntervalSets(); 00096 00097 /// processActiveIntervals - expire old intervals and move non-overlapping 00098 /// ones to the inactive list. 00099 void processActiveIntervals(unsigned CurPoint); 00100 00101 /// processInactiveIntervals - expire old intervals and move overlapping 00102 /// ones to the active list. 00103 void processInactiveIntervals(unsigned CurPoint); 00104 00105 /// assignRegOrStackSlotAtInterval - assign a register if one 00106 /// is available, or spill. 00107 void assignRegOrStackSlotAtInterval(LiveInterval* cur); 00108 00109 /// 00110 /// register handling helpers 00111 /// 00112 00113 /// getFreePhysReg - return a free physical register for this virtual 00114 /// register interval if we have one, otherwise return 0. 00115 unsigned getFreePhysReg(LiveInterval* cur); 00116 00117 /// assignVirt2StackSlot - assigns this virtual register to a 00118 /// stack slot. returns the stack slot 00119 int assignVirt2StackSlot(unsigned virtReg); 00120 00121 template <typename ItTy> 00122 void printIntervals(const char* const str, ItTy i, ItTy e) const { 00123 if (str) std::cerr << str << " intervals:\n"; 00124 for (; i != e; ++i) { 00125 std::cerr << "\t" << *i->first << " -> "; 00126 unsigned reg = i->first->reg; 00127 if (MRegisterInfo::isVirtualRegister(reg)) { 00128 reg = vrm_->getPhys(reg); 00129 } 00130 std::cerr << mri_->getName(reg) << '\n'; 00131 } 00132 } 00133 }; 00134 } 00135 00136 bool RA::runOnMachineFunction(MachineFunction &fn) { 00137 mf_ = &fn; 00138 tm_ = &fn.getTarget(); 00139 mri_ = tm_->getRegisterInfo(); 00140 li_ = &getAnalysis<LiveIntervals>(); 00141 00142 if (!prt_.get()) prt_.reset(new PhysRegTracker(*mri_)); 00143 vrm_.reset(new VirtRegMap(*mf_)); 00144 if (!spiller_.get()) spiller_.reset(createSpiller()); 00145 00146 initIntervalSets(); 00147 00148 linearScan(); 00149 00150 spiller_->runOnMachineFunction(*mf_, *vrm_); 00151 00152 vrm_.reset(); // Free the VirtRegMap 00153 00154 00155 while (!unhandled_.empty()) unhandled_.pop(); 00156 fixed_.clear(); 00157 active_.clear(); 00158 inactive_.clear(); 00159 handled_.clear(); 00160 00161 return true; 00162 } 00163 00164 /// initIntervalSets - initialize the interval sets. 00165 /// 00166 void RA::initIntervalSets() 00167 { 00168 assert(unhandled_.empty() && fixed_.empty() && 00169 active_.empty() && inactive_.empty() && 00170 "interval sets should be empty on initialization"); 00171 00172 for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) { 00173 if (MRegisterInfo::isPhysicalRegister(i->second.reg)) 00174 fixed_.push_back(std::make_pair(&i->second, i->second.begin())); 00175 else 00176 unhandled_.push(&i->second); 00177 } 00178 } 00179 00180 void RA::linearScan() 00181 { 00182 // linear scan algorithm 00183 DEBUG(std::cerr << "********** LINEAR SCAN **********\n"); 00184 DEBUG(std::cerr << "********** Function: " 00185 << mf_->getFunction()->getName() << '\n'); 00186 00187 // DEBUG(printIntervals("unhandled", unhandled_.begin(), unhandled_.end())); 00188 DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end())); 00189 DEBUG(printIntervals("active", active_.begin(), active_.end())); 00190 DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end())); 00191 00192 while (!unhandled_.empty()) { 00193 // pick the interval with the earliest start point 00194 LiveInterval* cur = unhandled_.top(); 00195 unhandled_.pop(); 00196 ++numIterations; 00197 DEBUG(std::cerr << "\n*** CURRENT ***: " << *cur << '\n'); 00198 00199 processActiveIntervals(cur->beginNumber()); 00200 processInactiveIntervals(cur->beginNumber()); 00201 00202 assert(MRegisterInfo::isVirtualRegister(cur->reg) && 00203 "Can only allocate virtual registers!"); 00204 00205 // Allocating a virtual register. try to find a free 00206 // physical register or spill an interval (possibly this one) in order to 00207 // assign it one. 00208 assignRegOrStackSlotAtInterval(cur); 00209 00210 DEBUG(printIntervals("active", active_.begin(), active_.end())); 00211 DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end())); 00212 } 00213 numIntervals += li_->getNumIntervals(); 00214 efficiency = double(numIterations) / double(numIntervals); 00215 00216 // expire any remaining active intervals 00217 for (IntervalPtrs::reverse_iterator 00218 i = active_.rbegin(); i != active_.rend(); ) { 00219 unsigned reg = i->first->reg; 00220 DEBUG(std::cerr << "\tinterval " << *i->first << " expired\n"); 00221 assert(MRegisterInfo::isVirtualRegister(reg) && 00222 "Can only allocate virtual registers!"); 00223 reg = vrm_->getPhys(reg); 00224 prt_->delRegUse(reg); 00225 i = IntervalPtrs::reverse_iterator(active_.erase(i.base()-1)); 00226 } 00227 00228 // expire any remaining inactive intervals 00229 for (IntervalPtrs::reverse_iterator 00230 i = inactive_.rbegin(); i != inactive_.rend(); ) { 00231 DEBUG(std::cerr << "\tinterval " << *i->first << " expired\n"); 00232 i = IntervalPtrs::reverse_iterator(inactive_.erase(i.base()-1)); 00233 } 00234 00235 DEBUG(std::cerr << *vrm_); 00236 } 00237 00238 /// processActiveIntervals - expire old intervals and move non-overlapping ones 00239 /// to the inactive list. 00240 void RA::processActiveIntervals(unsigned CurPoint) 00241 { 00242 DEBUG(std::cerr << "\tprocessing active intervals:\n"); 00243 00244 for (unsigned i = 0, e = active_.size(); i != e; ++i) { 00245 LiveInterval *Interval = active_[i].first; 00246 LiveInterval::iterator IntervalPos = active_[i].second; 00247 unsigned reg = Interval->reg; 00248 00249 IntervalPos = Interval->advanceTo(IntervalPos, CurPoint); 00250 00251 if (IntervalPos == Interval->end()) { // Remove expired intervals. 00252 DEBUG(std::cerr << "\t\tinterval " << *Interval << " expired\n"); 00253 assert(MRegisterInfo::isVirtualRegister(reg) && 00254 "Can only allocate virtual registers!"); 00255 reg = vrm_->getPhys(reg); 00256 prt_->delRegUse(reg); 00257 00258 // Pop off the end of the list. 00259 active_[i] = active_.back(); 00260 active_.pop_back(); 00261 --i; --e; 00262 00263 } else if (IntervalPos->start > CurPoint) { 00264 // Move inactive intervals to inactive list. 00265 DEBUG(std::cerr << "\t\tinterval " << *Interval << " inactive\n"); 00266 assert(MRegisterInfo::isVirtualRegister(reg) && 00267 "Can only allocate virtual registers!"); 00268 reg = vrm_->getPhys(reg); 00269 prt_->delRegUse(reg); 00270 // add to inactive. 00271 inactive_.push_back(std::make_pair(Interval, IntervalPos)); 00272 00273 // Pop off the end of the list. 00274 active_[i] = active_.back(); 00275 active_.pop_back(); 00276 --i; --e; 00277 } else { 00278 // Otherwise, just update the iterator position. 00279 active_[i].second = IntervalPos; 00280 } 00281 } 00282 } 00283 00284 /// processInactiveIntervals - expire old intervals and move overlapping 00285 /// ones to the active list. 00286 void RA::processInactiveIntervals(unsigned CurPoint) 00287 { 00288 DEBUG(std::cerr << "\tprocessing inactive intervals:\n"); 00289 00290 for (unsigned i = 0, e = inactive_.size(); i != e; ++i) { 00291 LiveInterval *Interval = inactive_[i].first; 00292 LiveInterval::iterator IntervalPos = inactive_[i].second; 00293 unsigned reg = Interval->reg; 00294 00295 IntervalPos = Interval->advanceTo(IntervalPos, CurPoint); 00296 00297 if (IntervalPos == Interval->end()) { // remove expired intervals. 00298 DEBUG(std::cerr << "\t\tinterval " << *Interval << " expired\n"); 00299 00300 // Pop off the end of the list. 00301 inactive_[i] = inactive_.back(); 00302 inactive_.pop_back(); 00303 --i; --e; 00304 } else if (IntervalPos->start <= CurPoint) { 00305 // move re-activated intervals in active list 00306 DEBUG(std::cerr << "\t\tinterval " << *Interval << " active\n"); 00307 assert(MRegisterInfo::isVirtualRegister(reg) && 00308 "Can only allocate virtual registers!"); 00309 reg = vrm_->getPhys(reg); 00310 prt_->addRegUse(reg); 00311 // add to active 00312 active_.push_back(std::make_pair(Interval, IntervalPos)); 00313 00314 // Pop off the end of the list. 00315 inactive_[i] = inactive_.back(); 00316 inactive_.pop_back(); 00317 --i; --e; 00318 } else { 00319 // Otherwise, just update the iterator position. 00320 inactive_[i].second = IntervalPos; 00321 } 00322 } 00323 } 00324 00325 /// updateSpillWeights - updates the spill weights of the specifed physical 00326 /// register and its weight. 00327 static void updateSpillWeights(std::vector<float> &Weights, 00328 unsigned reg, float weight, 00329 const MRegisterInfo *MRI) { 00330 Weights[reg] += weight; 00331 for (const unsigned* as = MRI->getAliasSet(reg); *as; ++as) 00332 Weights[*as] += weight; 00333 } 00334 00335 static RA::IntervalPtrs::iterator FindIntervalInVector(RA::IntervalPtrs &IP, 00336 LiveInterval *LI) { 00337 for (RA::IntervalPtrs::iterator I = IP.begin(), E = IP.end(); I != E; ++I) 00338 if (I->first == LI) return I; 00339 return IP.end(); 00340 } 00341 00342 static void RevertVectorIteratorsTo(RA::IntervalPtrs &V, unsigned Point) { 00343 for (unsigned i = 0, e = V.size(); i != e; ++i) { 00344 RA::IntervalPtr &IP = V[i]; 00345 LiveInterval::iterator I = std::upper_bound(IP.first->begin(), 00346 IP.second, Point); 00347 if (I != IP.first->begin()) --I; 00348 IP.second = I; 00349 } 00350 } 00351 00352 00353 /// assignRegOrStackSlotAtInterval - assign a register if one is available, or 00354 /// spill. 00355 void RA::assignRegOrStackSlotAtInterval(LiveInterval* cur) 00356 { 00357 DEBUG(std::cerr << "\tallocating current interval: "); 00358 00359 PhysRegTracker backupPrt = *prt_; 00360 00361 std::vector<float> SpillWeights; 00362 SpillWeights.assign(mri_->getNumRegs(), 0.0); 00363 00364 unsigned StartPosition = cur->beginNumber(); 00365 00366 // for each interval in active, update spill weights. 00367 for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end(); 00368 i != e; ++i) { 00369 unsigned reg = i->first->reg; 00370 assert(MRegisterInfo::isVirtualRegister(reg) && 00371 "Can only allocate virtual registers!"); 00372 reg = vrm_->getPhys(reg); 00373 updateSpillWeights(SpillWeights, reg, i->first->weight, mri_); 00374 } 00375 00376 // for every interval in inactive we overlap with, mark the 00377 // register as not free and update spill weights 00378 for (IntervalPtrs::const_iterator i = inactive_.begin(), 00379 e = inactive_.end(); i != e; ++i) { 00380 if (cur->overlapsFrom(*i->first, i->second-1)) { 00381 unsigned reg = i->first->reg; 00382 assert(MRegisterInfo::isVirtualRegister(reg) && 00383 "Can only allocate virtual registers!"); 00384 reg = vrm_->getPhys(reg); 00385 prt_->addRegUse(reg); 00386 updateSpillWeights(SpillWeights, reg, i->first->weight, mri_); 00387 } 00388 } 00389 00390 // For every interval in fixed we overlap with, mark the register as not free 00391 // and update spill weights. 00392 for (unsigned i = 0, e = fixed_.size(); i != e; ++i) { 00393 IntervalPtr &IP = fixed_[i]; 00394 LiveInterval *I = IP.first; 00395 if (I->endNumber() > StartPosition) { 00396 LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition); 00397 IP.second = II; 00398 if (II != I->begin() && II->start > StartPosition) 00399 --II; 00400 if (cur->overlapsFrom(*I, II)) { 00401 unsigned reg = I->reg; 00402 prt_->addRegUse(reg); 00403 updateSpillWeights(SpillWeights, reg, I->weight, mri_); 00404 } 00405 } 00406 } 00407 00408 unsigned physReg = getFreePhysReg(cur); 00409 // restore the physical register tracker 00410 *prt_ = backupPrt; 00411 // if we find a free register, we are done: assign this virtual to 00412 // the free physical register and add this interval to the active 00413 // list. 00414 if (physReg) { 00415 DEBUG(std::cerr << mri_->getName(physReg) << '\n'); 00416 vrm_->assignVirt2Phys(cur->reg, physReg); 00417 prt_->addRegUse(physReg); 00418 active_.push_back(std::make_pair(cur, cur->begin())); 00419 handled_.push_back(cur); 00420 return; 00421 } 00422 DEBUG(std::cerr << "no free registers\n"); 00423 00424 DEBUG(std::cerr << "\tassigning stack slot at interval "<< *cur << ":\n"); 00425 00426 float minWeight = HUGE_VAL; 00427 unsigned minReg = 0; 00428 const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg); 00429 for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_); 00430 i != rc->allocation_order_end(*mf_); ++i) { 00431 unsigned reg = *i; 00432 if (minWeight > SpillWeights[reg]) { 00433 minWeight = SpillWeights[reg]; 00434 minReg = reg; 00435 } 00436 } 00437 DEBUG(std::cerr << "\t\tregister with min weight: " 00438 << mri_->getName(minReg) << " (" << minWeight << ")\n"); 00439 00440 // if the current has the minimum weight, we need to spill it and 00441 // add any added intervals back to unhandled, and restart 00442 // linearscan. 00443 if (cur->weight <= minWeight) { 00444 DEBUG(std::cerr << "\t\t\tspilling(c): " << *cur << '\n';); 00445 int slot = vrm_->assignVirt2StackSlot(cur->reg); 00446 std::vector<LiveInterval*> added = 00447 li_->addIntervalsForSpills(*cur, *vrm_, slot); 00448 if (added.empty()) 00449 return; // Early exit if all spills were folded. 00450 00451 // Merge added with unhandled. Note that we know that 00452 // addIntervalsForSpills returns intervals sorted by their starting 00453 // point. 00454 for (unsigned i = 0, e = added.size(); i != e; ++i) 00455 unhandled_.push(added[i]); 00456 return; 00457 } 00458 00459 ++NumBacktracks; 00460 00461 // push the current interval back to unhandled since we are going 00462 // to re-run at least this iteration. Since we didn't modify it it 00463 // should go back right in the front of the list 00464 unhandled_.push(cur); 00465 00466 // otherwise we spill all intervals aliasing the register with 00467 // minimum weight, rollback to the interval with the earliest 00468 // start point and let the linear scan algorithm run again 00469 std::vector<LiveInterval*> added; 00470 assert(MRegisterInfo::isPhysicalRegister(minReg) && 00471 "did not choose a register to spill?"); 00472 std::vector<bool> toSpill(mri_->getNumRegs(), false); 00473 00474 // We are going to spill minReg and all its aliases. 00475 toSpill[minReg] = true; 00476 for (const unsigned* as = mri_->getAliasSet(minReg); *as; ++as) 00477 toSpill[*as] = true; 00478 00479 // the earliest start of a spilled interval indicates up to where 00480 // in handled we need to roll back 00481 unsigned earliestStart = cur->beginNumber(); 00482 00483 // set of spilled vregs (used later to rollback properly) 00484 std::set<unsigned> spilled; 00485 00486 // spill live intervals of virtual regs mapped to the physical register we 00487 // want to clear (and its aliases). We only spill those that overlap with the 00488 // current interval as the rest do not affect its allocation. we also keep 00489 // track of the earliest start of all spilled live intervals since this will 00490 // mark our rollback point. 00491 for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) { 00492 unsigned reg = i->first->reg; 00493 if (//MRegisterInfo::isVirtualRegister(reg) && 00494 toSpill[vrm_->getPhys(reg)] && 00495 cur->overlapsFrom(*i->first, i->second)) { 00496 DEBUG(std::cerr << "\t\t\tspilling(a): " << *i->first << '\n'); 00497 earliestStart = std::min(earliestStart, i->first->beginNumber()); 00498 int slot = vrm_->assignVirt2StackSlot(i->first->reg); 00499 std::vector<LiveInterval*> newIs = 00500 li_->addIntervalsForSpills(*i->first, *vrm_, slot); 00501 std::copy(newIs.begin(), newIs.end(), std::back_inserter(added)); 00502 spilled.insert(reg); 00503 } 00504 } 00505 for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end(); ++i){ 00506 unsigned reg = i->first->reg; 00507 if (//MRegisterInfo::isVirtualRegister(reg) && 00508 toSpill[vrm_->getPhys(reg)] && 00509 cur->overlapsFrom(*i->first, i->second-1)) { 00510 DEBUG(std::cerr << "\t\t\tspilling(i): " << *i->first << '\n'); 00511 earliestStart = std::min(earliestStart, i->first->beginNumber()); 00512 int slot = vrm_->assignVirt2StackSlot(reg); 00513 std::vector<LiveInterval*> newIs = 00514 li_->addIntervalsForSpills(*i->first, *vrm_, slot); 00515 std::copy(newIs.begin(), newIs.end(), std::back_inserter(added)); 00516 spilled.insert(reg); 00517 } 00518 } 00519 00520 DEBUG(std::cerr << "\t\trolling back to: " << earliestStart << '\n'); 00521 00522 // Scan handled in reverse order up to the earliest start of a 00523 // spilled live interval and undo each one, restoring the state of 00524 // unhandled. 00525 while (!handled_.empty()) { 00526 LiveInterval* i = handled_.back(); 00527 // If this interval starts before t we are done. 00528 if (i->beginNumber() < earliestStart) 00529 break; 00530 DEBUG(std::cerr << "\t\t\tundo changes for: " << *i << '\n'); 00531 handled_.pop_back(); 00532 00533 // When undoing a live interval allocation we must know if it is active or 00534 // inactive to properly update the PhysRegTracker and the VirtRegMap. 00535 IntervalPtrs::iterator it; 00536 if ((it = FindIntervalInVector(active_, i)) != active_.end()) { 00537 active_.erase(it); 00538 if (MRegisterInfo::isPhysicalRegister(i->reg)) { 00539 assert(0 && "daksjlfd"); 00540 prt_->delRegUse(i->reg); 00541 unhandled_.push(i); 00542 } else { 00543 if (!spilled.count(i->reg)) 00544 unhandled_.push(i); 00545 prt_->delRegUse(vrm_->getPhys(i->reg)); 00546 vrm_->clearVirt(i->reg); 00547 } 00548 } else if ((it = FindIntervalInVector(inactive_, i)) != inactive_.end()) { 00549 inactive_.erase(it); 00550 if (MRegisterInfo::isPhysicalRegister(i->reg)) { 00551 assert(0 && "daksjlfd"); 00552 unhandled_.push(i); 00553 } else { 00554 if (!spilled.count(i->reg)) 00555 unhandled_.push(i); 00556 vrm_->clearVirt(i->reg); 00557 } 00558 } else { 00559 assert(MRegisterInfo::isVirtualRegister(i->reg) && 00560 "Can only allocate virtual registers!"); 00561 vrm_->clearVirt(i->reg); 00562 unhandled_.push(i); 00563 } 00564 } 00565 00566 // Rewind the iterators in the active, inactive, and fixed lists back to the 00567 // point we reverted to. 00568 RevertVectorIteratorsTo(active_, earliestStart); 00569 RevertVectorIteratorsTo(inactive_, earliestStart); 00570 RevertVectorIteratorsTo(fixed_, earliestStart); 00571 00572 // scan the rest and undo each interval that expired after t and 00573 // insert it in active (the next iteration of the algorithm will 00574 // put it in inactive if required) 00575 for (unsigned i = 0, e = handled_.size(); i != e; ++i) { 00576 LiveInterval *HI = handled_[i]; 00577 if (!HI->expiredAt(earliestStart) && 00578 HI->expiredAt(cur->beginNumber())) { 00579 DEBUG(std::cerr << "\t\t\tundo changes for: " << *HI << '\n'); 00580 active_.push_back(std::make_pair(HI, HI->begin())); 00581 if (MRegisterInfo::isPhysicalRegister(HI->reg)) { 00582 assert(0 &&"sdflkajsdf"); 00583 prt_->addRegUse(HI->reg); 00584 } else 00585 prt_->addRegUse(vrm_->getPhys(HI->reg)); 00586 } 00587 } 00588 00589 // merge added with unhandled 00590 for (unsigned i = 0, e = added.size(); i != e; ++i) 00591 unhandled_.push(added[i]); 00592 } 00593 00594 /// getFreePhysReg - return a free physical register for this virtual register 00595 /// interval if we have one, otherwise return 0. 00596 unsigned RA::getFreePhysReg(LiveInterval* cur) 00597 { 00598 std::vector<unsigned> inactiveCounts(mri_->getNumRegs(), 0); 00599 for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end(); 00600 i != e; ++i) { 00601 unsigned reg = i->first->reg; 00602 assert(MRegisterInfo::isVirtualRegister(reg) && 00603 "Can only allocate virtual registers!"); 00604 reg = vrm_->getPhys(reg); 00605 ++inactiveCounts[reg]; 00606 } 00607 00608 const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(cur->reg); 00609 00610 unsigned freeReg = 0; 00611 for (TargetRegisterClass::iterator i = rc->allocation_order_begin(*mf_); 00612 i != rc->allocation_order_end(*mf_); ++i) { 00613 unsigned reg = *i; 00614 if (prt_->isRegAvail(reg) && 00615 (!freeReg || inactiveCounts[freeReg] < inactiveCounts[reg])) 00616 freeReg = reg; 00617 } 00618 return freeReg; 00619 } 00620 00621 FunctionPass* llvm::createLinearScanRegisterAllocator() { 00622 return new RA(); 00623 }