LLVM API Documentation
00001 //===-- RegAllocLinearScan.cpp - Linear Scan register allocator -----------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // 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 "VirtRegMap.h" 00016 #include "VirtRegRewriter.h" 00017 #include "Spiller.h" 00018 #include "llvm/Function.h" 00019 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 00020 #include "llvm/CodeGen/LiveStackAnalysis.h" 00021 #include "llvm/CodeGen/MachineFunctionPass.h" 00022 #include "llvm/CodeGen/MachineInstr.h" 00023 #include "llvm/CodeGen/MachineLoopInfo.h" 00024 #include "llvm/CodeGen/MachineRegisterInfo.h" 00025 #include "llvm/CodeGen/Passes.h" 00026 #include "llvm/CodeGen/RegAllocRegistry.h" 00027 #include "llvm/CodeGen/RegisterCoalescer.h" 00028 #include "llvm/Target/TargetRegisterInfo.h" 00029 #include "llvm/Target/TargetMachine.h" 00030 #include "llvm/Target/TargetOptions.h" 00031 #include "llvm/Target/TargetInstrInfo.h" 00032 #include "llvm/ADT/EquivalenceClasses.h" 00033 #include "llvm/ADT/SmallSet.h" 00034 #include "llvm/ADT/Statistic.h" 00035 #include "llvm/ADT/STLExtras.h" 00036 #include "llvm/Support/Debug.h" 00037 #include "llvm/Support/ErrorHandling.h" 00038 #include "llvm/Support/Compiler.h" 00039 #include "llvm/Support/ErrorHandling.h" 00040 #include "llvm/Support/raw_ostream.h" 00041 #include <algorithm> 00042 #include <set> 00043 #include <queue> 00044 #include <memory> 00045 #include <cmath> 00046 00047 using namespace llvm; 00048 00049 STATISTIC(NumIters , "Number of iterations performed"); 00050 STATISTIC(NumBacktracks, "Number of times we had to backtrack"); 00051 STATISTIC(NumCoalesce, "Number of copies coalesced"); 00052 STATISTIC(NumDowngrade, "Number of registers downgraded"); 00053 00054 static cl::opt<bool> 00055 NewHeuristic("new-spilling-heuristic", 00056 cl::desc("Use new spilling heuristic"), 00057 cl::init(false), cl::Hidden); 00058 00059 static cl::opt<bool> 00060 PreSplitIntervals("pre-alloc-split", 00061 cl::desc("Pre-register allocation live interval splitting"), 00062 cl::init(false), cl::Hidden); 00063 00064 static cl::opt<bool> 00065 NewSpillFramework("new-spill-framework", 00066 cl::desc("New spilling framework"), 00067 cl::init(false), cl::Hidden); 00068 00069 static RegisterRegAlloc 00070 linearscanRegAlloc("linearscan", "linear scan register allocator", 00071 createLinearScanRegisterAllocator); 00072 00073 namespace { 00074 struct VISIBILITY_HIDDEN RALinScan : public MachineFunctionPass { 00075 static char ID; 00076 RALinScan() : MachineFunctionPass(&ID) {} 00077 00078 typedef std::pair<LiveInterval*, LiveInterval::iterator> IntervalPtr; 00079 typedef SmallVector<IntervalPtr, 32> IntervalPtrs; 00080 private: 00081 /// RelatedRegClasses - This structure is built the first time a function is 00082 /// compiled, and keeps track of which register classes have registers that 00083 /// belong to multiple classes or have aliases that are in other classes. 00084 EquivalenceClasses<const TargetRegisterClass*> RelatedRegClasses; 00085 DenseMap<unsigned, const TargetRegisterClass*> OneClassForEachPhysReg; 00086 00087 // NextReloadMap - For each register in the map, it maps to the another 00088 // register which is defined by a reload from the same stack slot and 00089 // both reloads are in the same basic block. 00090 DenseMap<unsigned, unsigned> NextReloadMap; 00091 00092 // DowngradedRegs - A set of registers which are being "downgraded", i.e. 00093 // un-favored for allocation. 00094 SmallSet<unsigned, 8> DowngradedRegs; 00095 00096 // DowngradeMap - A map from virtual registers to physical registers being 00097 // downgraded for the virtual registers. 00098 DenseMap<unsigned, unsigned> DowngradeMap; 00099 00100 MachineFunction* mf_; 00101 MachineRegisterInfo* mri_; 00102 const TargetMachine* tm_; 00103 const TargetRegisterInfo* tri_; 00104 const TargetInstrInfo* tii_; 00105 BitVector allocatableRegs_; 00106 LiveIntervals* li_; 00107 LiveStacks* ls_; 00108 const MachineLoopInfo *loopInfo; 00109 00110 /// handled_ - Intervals are added to the handled_ set in the order of their 00111 /// start value. This is uses for backtracking. 00112 std::vector<LiveInterval*> handled_; 00113 00114 /// fixed_ - Intervals that correspond to machine registers. 00115 /// 00116 IntervalPtrs fixed_; 00117 00118 /// active_ - Intervals that are currently being processed, and which have a 00119 /// live range active for the current point. 00120 IntervalPtrs active_; 00121 00122 /// inactive_ - Intervals that are currently being processed, but which have 00123 /// a hold at the current point. 00124 IntervalPtrs inactive_; 00125 00126 typedef std::priority_queue<LiveInterval*, 00127 SmallVector<LiveInterval*, 64>, 00128 greater_ptr<LiveInterval> > IntervalHeap; 00129 IntervalHeap unhandled_; 00130 00131 /// regUse_ - Tracks register usage. 00132 SmallVector<unsigned, 32> regUse_; 00133 SmallVector<unsigned, 32> regUseBackUp_; 00134 00135 /// vrm_ - Tracks register assignments. 00136 VirtRegMap* vrm_; 00137 00138 std::auto_ptr<VirtRegRewriter> rewriter_; 00139 00140 std::auto_ptr<Spiller> spiller_; 00141 00142 public: 00143 virtual const char* getPassName() const { 00144 return "Linear Scan Register Allocator"; 00145 } 00146 00147 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00148 AU.setPreservesCFG(); 00149 AU.addRequired<LiveIntervals>(); 00150 if (StrongPHIElim) 00151 AU.addRequiredID(StrongPHIEliminationID); 00152 // Make sure PassManager knows which analyses to make available 00153 // to coalescing and which analyses coalescing invalidates. 00154 AU.addRequiredTransitive<RegisterCoalescer>(); 00155 if (PreSplitIntervals) 00156 AU.addRequiredID(PreAllocSplittingID); 00157 AU.addRequired<LiveStacks>(); 00158 AU.addPreserved<LiveStacks>(); 00159 AU.addRequired<MachineLoopInfo>(); 00160 AU.addPreserved<MachineLoopInfo>(); 00161 AU.addRequired<VirtRegMap>(); 00162 AU.addPreserved<VirtRegMap>(); 00163 AU.addPreservedID(MachineDominatorsID); 00164 MachineFunctionPass::getAnalysisUsage(AU); 00165 } 00166 00167 /// runOnMachineFunction - register allocate the whole function 00168 bool runOnMachineFunction(MachineFunction&); 00169 00170 private: 00171 /// linearScan - the linear scan algorithm 00172 void linearScan(); 00173 00174 /// initIntervalSets - initialize the interval sets. 00175 /// 00176 void initIntervalSets(); 00177 00178 /// processActiveIntervals - expire old intervals and move non-overlapping 00179 /// ones to the inactive list. 00180 void processActiveIntervals(unsigned CurPoint); 00181 00182 /// processInactiveIntervals - expire old intervals and move overlapping 00183 /// ones to the active list. 00184 void processInactiveIntervals(unsigned CurPoint); 00185 00186 /// hasNextReloadInterval - Return the next liveinterval that's being 00187 /// defined by a reload from the same SS as the specified one. 00188 LiveInterval *hasNextReloadInterval(LiveInterval *cur); 00189 00190 /// DowngradeRegister - Downgrade a register for allocation. 00191 void DowngradeRegister(LiveInterval *li, unsigned Reg); 00192 00193 /// UpgradeRegister - Upgrade a register for allocation. 00194 void UpgradeRegister(unsigned Reg); 00195 00196 /// assignRegOrStackSlotAtInterval - assign a register if one 00197 /// is available, or spill. 00198 void assignRegOrStackSlotAtInterval(LiveInterval* cur); 00199 00200 void updateSpillWeights(std::vector<float> &Weights, 00201 unsigned reg, float weight, 00202 const TargetRegisterClass *RC); 00203 00204 /// findIntervalsToSpill - Determine the intervals to spill for the 00205 /// specified interval. It's passed the physical registers whose spill 00206 /// weight is the lowest among all the registers whose live intervals 00207 /// conflict with the interval. 00208 void findIntervalsToSpill(LiveInterval *cur, 00209 std::vector<std::pair<unsigned,float> > &Candidates, 00210 unsigned NumCands, 00211 SmallVector<LiveInterval*, 8> &SpillIntervals); 00212 00213 /// attemptTrivialCoalescing - If a simple interval is defined by a copy, 00214 /// try allocate the definition the same register as the source register 00215 /// if the register is not defined during live time of the interval. This 00216 /// eliminate a copy. This is used to coalesce copies which were not 00217 /// coalesced away before allocation either due to dest and src being in 00218 /// different register classes or because the coalescer was overly 00219 /// conservative. 00220 unsigned attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg); 00221 00222 /// 00223 /// Register usage / availability tracking helpers. 00224 /// 00225 00226 void initRegUses() { 00227 regUse_.resize(tri_->getNumRegs(), 0); 00228 regUseBackUp_.resize(tri_->getNumRegs(), 0); 00229 } 00230 00231 void finalizeRegUses() { 00232 #ifndef NDEBUG 00233 // Verify all the registers are "freed". 00234 bool Error = false; 00235 for (unsigned i = 0, e = tri_->getNumRegs(); i != e; ++i) { 00236 if (regUse_[i] != 0) { 00237 cerr << tri_->getName(i) << " is still in use!\n"; 00238 Error = true; 00239 } 00240 } 00241 if (Error) 00242 llvm_unreachable(0); 00243 #endif 00244 regUse_.clear(); 00245 regUseBackUp_.clear(); 00246 } 00247 00248 void addRegUse(unsigned physReg) { 00249 assert(TargetRegisterInfo::isPhysicalRegister(physReg) && 00250 "should be physical register!"); 00251 ++regUse_[physReg]; 00252 for (const unsigned* as = tri_->getAliasSet(physReg); *as; ++as) 00253 ++regUse_[*as]; 00254 } 00255 00256 void delRegUse(unsigned physReg) { 00257 assert(TargetRegisterInfo::isPhysicalRegister(physReg) && 00258 "should be physical register!"); 00259 assert(regUse_[physReg] != 0); 00260 --regUse_[physReg]; 00261 for (const unsigned* as = tri_->getAliasSet(physReg); *as; ++as) { 00262 assert(regUse_[*as] != 0); 00263 --regUse_[*as]; 00264 } 00265 } 00266 00267 bool isRegAvail(unsigned physReg) const { 00268 assert(TargetRegisterInfo::isPhysicalRegister(physReg) && 00269 "should be physical register!"); 00270 return regUse_[physReg] == 0; 00271 } 00272 00273 void backUpRegUses() { 00274 regUseBackUp_ = regUse_; 00275 } 00276 00277 void restoreRegUses() { 00278 regUse_ = regUseBackUp_; 00279 } 00280 00281 /// 00282 /// Register handling helpers. 00283 /// 00284 00285 /// getFreePhysReg - return a free physical register for this virtual 00286 /// register interval if we have one, otherwise return 0. 00287 unsigned getFreePhysReg(LiveInterval* cur); 00288 unsigned getFreePhysReg(LiveInterval* cur, 00289 const TargetRegisterClass *RC, 00290 unsigned MaxInactiveCount, 00291 SmallVector<unsigned, 256> &inactiveCounts, 00292 bool SkipDGRegs); 00293 00294 /// assignVirt2StackSlot - assigns this virtual register to a 00295 /// stack slot. returns the stack slot 00296 int assignVirt2StackSlot(unsigned virtReg); 00297 00298 void ComputeRelatedRegClasses(); 00299 00300 template <typename ItTy> 00301 void printIntervals(const char* const str, ItTy i, ItTy e) const { 00302 if (str) DOUT << str << " intervals:\n"; 00303 for (; i != e; ++i) { 00304 DOUT << "\t" << *i->first << " -> "; 00305 unsigned reg = i->first->reg; 00306 if (TargetRegisterInfo::isVirtualRegister(reg)) { 00307 reg = vrm_->getPhys(reg); 00308 } 00309 DOUT << tri_->getName(reg) << '\n'; 00310 } 00311 } 00312 }; 00313 char RALinScan::ID = 0; 00314 } 00315 00316 static RegisterPass<RALinScan> 00317 X("linearscan-regalloc", "Linear Scan Register Allocator"); 00318 00319 void RALinScan::ComputeRelatedRegClasses() { 00320 // First pass, add all reg classes to the union, and determine at least one 00321 // reg class that each register is in. 00322 bool HasAliases = false; 00323 for (TargetRegisterInfo::regclass_iterator RCI = tri_->regclass_begin(), 00324 E = tri_->regclass_end(); RCI != E; ++RCI) { 00325 RelatedRegClasses.insert(*RCI); 00326 for (TargetRegisterClass::iterator I = (*RCI)->begin(), E = (*RCI)->end(); 00327 I != E; ++I) { 00328 HasAliases = HasAliases || *tri_->getAliasSet(*I) != 0; 00329 00330 const TargetRegisterClass *&PRC = OneClassForEachPhysReg[*I]; 00331 if (PRC) { 00332 // Already processed this register. Just make sure we know that 00333 // multiple register classes share a register. 00334 RelatedRegClasses.unionSets(PRC, *RCI); 00335 } else { 00336 PRC = *RCI; 00337 } 00338 } 00339 } 00340 00341 // Second pass, now that we know conservatively what register classes each reg 00342 // belongs to, add info about aliases. We don't need to do this for targets 00343 // without register aliases. 00344 if (HasAliases) 00345 for (DenseMap<unsigned, const TargetRegisterClass*>::iterator 00346 I = OneClassForEachPhysReg.begin(), E = OneClassForEachPhysReg.end(); 00347 I != E; ++I) 00348 for (const unsigned *AS = tri_->getAliasSet(I->first); *AS; ++AS) 00349 RelatedRegClasses.unionSets(I->second, OneClassForEachPhysReg[*AS]); 00350 } 00351 00352 /// attemptTrivialCoalescing - If a simple interval is defined by a copy, 00353 /// try allocate the definition the same register as the source register 00354 /// if the register is not defined during live time of the interval. This 00355 /// eliminate a copy. This is used to coalesce copies which were not 00356 /// coalesced away before allocation either due to dest and src being in 00357 /// different register classes or because the coalescer was overly 00358 /// conservative. 00359 unsigned RALinScan::attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg) { 00360 unsigned Preference = vrm_->getRegAllocPref(cur.reg); 00361 if ((Preference && Preference == Reg) || !cur.containsOneValue()) 00362 return Reg; 00363 00364 VNInfo *vni = cur.begin()->valno; 00365 if (!vni->def || vni->isUnused() || !vni->isDefAccurate()) 00366 return Reg; 00367 MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def); 00368 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg, PhysReg; 00369 if (!CopyMI || 00370 !tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubReg, DstSubReg)) 00371 return Reg; 00372 PhysReg = SrcReg; 00373 if (TargetRegisterInfo::isVirtualRegister(SrcReg)) { 00374 if (!vrm_->isAssignedReg(SrcReg)) 00375 return Reg; 00376 PhysReg = vrm_->getPhys(SrcReg); 00377 } 00378 if (Reg == PhysReg) 00379 return Reg; 00380 00381 const TargetRegisterClass *RC = mri_->getRegClass(cur.reg); 00382 if (!RC->contains(PhysReg)) 00383 return Reg; 00384 00385 // Try to coalesce. 00386 if (!li_->conflictsWithPhysRegDef(cur, *vrm_, PhysReg)) { 00387 DOUT << "Coalescing: " << cur << " -> " << tri_->getName(PhysReg) 00388 << '\n'; 00389 vrm_->clearVirt(cur.reg); 00390 vrm_->assignVirt2Phys(cur.reg, PhysReg); 00391 00392 // Remove unnecessary kills since a copy does not clobber the register. 00393 if (li_->hasInterval(SrcReg)) { 00394 LiveInterval &SrcLI = li_->getInterval(SrcReg); 00395 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(cur.reg), 00396 E = mri_->reg_end(); I != E; ++I) { 00397 MachineOperand &O = I.getOperand(); 00398 if (!O.isUse() || !O.isKill()) 00399 continue; 00400 MachineInstr *MI = &*I; 00401 if (SrcLI.liveAt(li_->getDefIndex(li_->getInstructionIndex(MI)))) 00402 O.setIsKill(false); 00403 } 00404 } 00405 00406 ++NumCoalesce; 00407 return PhysReg; 00408 } 00409 00410 return Reg; 00411 } 00412 00413 bool RALinScan::runOnMachineFunction(MachineFunction &fn) { 00414 mf_ = &fn; 00415 mri_ = &fn.getRegInfo(); 00416 tm_ = &fn.getTarget(); 00417 tri_ = tm_->getRegisterInfo(); 00418 tii_ = tm_->getInstrInfo(); 00419 allocatableRegs_ = tri_->getAllocatableSet(fn); 00420 li_ = &getAnalysis<LiveIntervals>(); 00421 ls_ = &getAnalysis<LiveStacks>(); 00422 loopInfo = &getAnalysis<MachineLoopInfo>(); 00423 00424 // We don't run the coalescer here because we have no reason to 00425 // interact with it. If the coalescer requires interaction, it 00426 // won't do anything. If it doesn't require interaction, we assume 00427 // it was run as a separate pass. 00428 00429 // If this is the first function compiled, compute the related reg classes. 00430 if (RelatedRegClasses.empty()) 00431 ComputeRelatedRegClasses(); 00432 00433 // Also resize register usage trackers. 00434 initRegUses(); 00435 00436 vrm_ = &getAnalysis<VirtRegMap>(); 00437 if (!rewriter_.get()) rewriter_.reset(createVirtRegRewriter()); 00438 00439 if (NewSpillFramework) { 00440 spiller_.reset(createSpiller(mf_, li_, ls_, vrm_)); 00441 } 00442 00443 initIntervalSets(); 00444 00445 linearScan(); 00446 00447 // Rewrite spill code and update the PhysRegsUsed set. 00448 rewriter_->runOnMachineFunction(*mf_, *vrm_, li_); 00449 00450 assert(unhandled_.empty() && "Unhandled live intervals remain!"); 00451 00452 finalizeRegUses(); 00453 00454 fixed_.clear(); 00455 active_.clear(); 00456 inactive_.clear(); 00457 handled_.clear(); 00458 NextReloadMap.clear(); 00459 DowngradedRegs.clear(); 00460 DowngradeMap.clear(); 00461 spiller_.reset(0); 00462 00463 return true; 00464 } 00465 00466 /// initIntervalSets - initialize the interval sets. 00467 /// 00468 void RALinScan::initIntervalSets() 00469 { 00470 assert(unhandled_.empty() && fixed_.empty() && 00471 active_.empty() && inactive_.empty() && 00472 "interval sets should be empty on initialization"); 00473 00474 handled_.reserve(li_->getNumIntervals()); 00475 00476 for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) { 00477 if (TargetRegisterInfo::isPhysicalRegister(i->second->reg)) { 00478 mri_->setPhysRegUsed(i->second->reg); 00479 fixed_.push_back(std::make_pair(i->second, i->second->begin())); 00480 } else 00481 unhandled_.push(i->second); 00482 } 00483 } 00484 00485 void RALinScan::linearScan() 00486 { 00487 // linear scan algorithm 00488 DOUT << "********** LINEAR SCAN **********\n"; 00489 DEBUG(errs() << "********** Function: " 00490 << mf_->getFunction()->getName() << '\n'); 00491 00492 DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end())); 00493 00494 while (!unhandled_.empty()) { 00495 // pick the interval with the earliest start point 00496 LiveInterval* cur = unhandled_.top(); 00497 unhandled_.pop(); 00498 ++NumIters; 00499 DOUT << "\n*** CURRENT ***: " << *cur << '\n'; 00500 00501 if (!cur->empty()) { 00502 processActiveIntervals(cur->beginNumber()); 00503 processInactiveIntervals(cur->beginNumber()); 00504 00505 assert(TargetRegisterInfo::isVirtualRegister(cur->reg) && 00506 "Can only allocate virtual registers!"); 00507 } 00508 00509 // Allocating a virtual register. try to find a free 00510 // physical register or spill an interval (possibly this one) in order to 00511 // assign it one. 00512 assignRegOrStackSlotAtInterval(cur); 00513 00514 DEBUG(printIntervals("active", active_.begin(), active_.end())); 00515 DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end())); 00516 } 00517 00518 // Expire any remaining active intervals 00519 while (!active_.empty()) { 00520 IntervalPtr &IP = active_.back(); 00521 unsigned reg = IP.first->reg; 00522 DOUT << "\tinterval " << *IP.first << " expired\n"; 00523 assert(TargetRegisterInfo::isVirtualRegister(reg) && 00524 "Can only allocate virtual registers!"); 00525 reg = vrm_->getPhys(reg); 00526 delRegUse(reg); 00527 active_.pop_back(); 00528 } 00529 00530 // Expire any remaining inactive intervals 00531 DEBUG(for (IntervalPtrs::reverse_iterator 00532 i = inactive_.rbegin(); i != inactive_.rend(); ++i) 00533 DOUT << "\tinterval " << *i->first << " expired\n"); 00534 inactive_.clear(); 00535 00536 // Add live-ins to every BB except for entry. Also perform trivial coalescing. 00537 MachineFunction::iterator EntryMBB = mf_->begin(); 00538 SmallVector<MachineBasicBlock*, 8> LiveInMBBs; 00539 for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) { 00540 LiveInterval &cur = *i->second; 00541 unsigned Reg = 0; 00542 bool isPhys = TargetRegisterInfo::isPhysicalRegister(cur.reg); 00543 if (isPhys) 00544 Reg = cur.reg; 00545 else if (vrm_->isAssignedReg(cur.reg)) 00546 Reg = attemptTrivialCoalescing(cur, vrm_->getPhys(cur.reg)); 00547 if (!Reg) 00548 continue; 00549 // Ignore splited live intervals. 00550 if (!isPhys && vrm_->getPreSplitReg(cur.reg)) 00551 continue; 00552 00553 for (LiveInterval::Ranges::const_iterator I = cur.begin(), E = cur.end(); 00554 I != E; ++I) { 00555 const LiveRange &LR = *I; 00556 if (li_->findLiveInMBBs(LR.start, LR.end, LiveInMBBs)) { 00557 for (unsigned i = 0, e = LiveInMBBs.size(); i != e; ++i) 00558 if (LiveInMBBs[i] != EntryMBB) { 00559 assert(TargetRegisterInfo::isPhysicalRegister(Reg) && 00560 "Adding a virtual register to livein set?"); 00561 LiveInMBBs[i]->addLiveIn(Reg); 00562 } 00563 LiveInMBBs.clear(); 00564 } 00565 } 00566 } 00567 00568 DOUT << *vrm_; 00569 00570 // Look for physical registers that end up not being allocated even though 00571 // register allocator had to spill other registers in its register class. 00572 if (ls_->getNumIntervals() == 0) 00573 return; 00574 if (!vrm_->FindUnusedRegisters(li_)) 00575 return; 00576 } 00577 00578 /// processActiveIntervals - expire old intervals and move non-overlapping ones 00579 /// to the inactive list. 00580 void RALinScan::processActiveIntervals(unsigned CurPoint) 00581 { 00582 DOUT << "\tprocessing active intervals:\n"; 00583 00584 for (unsigned i = 0, e = active_.size(); i != e; ++i) { 00585 LiveInterval *Interval = active_[i].first; 00586 LiveInterval::iterator IntervalPos = active_[i].second; 00587 unsigned reg = Interval->reg; 00588 00589 IntervalPos = Interval->advanceTo(IntervalPos, CurPoint); 00590 00591 if (IntervalPos == Interval->end()) { // Remove expired intervals. 00592 DOUT << "\t\tinterval " << *Interval << " expired\n"; 00593 assert(TargetRegisterInfo::isVirtualRegister(reg) && 00594 "Can only allocate virtual registers!"); 00595 reg = vrm_->getPhys(reg); 00596 delRegUse(reg); 00597 00598 // Pop off the end of the list. 00599 active_[i] = active_.back(); 00600 active_.pop_back(); 00601 --i; --e; 00602 00603 } else if (IntervalPos->start > CurPoint) { 00604 // Move inactive intervals to inactive list. 00605 DOUT << "\t\tinterval " << *Interval << " inactive\n"; 00606 assert(TargetRegisterInfo::isVirtualRegister(reg) && 00607 "Can only allocate virtual registers!"); 00608 reg = vrm_->getPhys(reg); 00609 delRegUse(reg); 00610 // add to inactive. 00611 inactive_.push_back(std::make_pair(Interval, IntervalPos)); 00612 00613 // Pop off the end of the list. 00614 active_[i] = active_.back(); 00615 active_.pop_back(); 00616 --i; --e; 00617 } else { 00618 // Otherwise, just update the iterator position. 00619 active_[i].second = IntervalPos; 00620 } 00621 } 00622 } 00623 00624 /// processInactiveIntervals - expire old intervals and move overlapping 00625 /// ones to the active list. 00626 void RALinScan::processInactiveIntervals(unsigned CurPoint) 00627 { 00628 DOUT << "\tprocessing inactive intervals:\n"; 00629 00630 for (unsigned i = 0, e = inactive_.size(); i != e; ++i) { 00631 LiveInterval *Interval = inactive_[i].first; 00632 LiveInterval::iterator IntervalPos = inactive_[i].second; 00633 unsigned reg = Interval->reg; 00634 00635 IntervalPos = Interval->advanceTo(IntervalPos, CurPoint); 00636 00637 if (IntervalPos == Interval->end()) { // remove expired intervals. 00638 DOUT << "\t\tinterval " << *Interval << " expired\n"; 00639 00640 // Pop off the end of the list. 00641 inactive_[i] = inactive_.back(); 00642 inactive_.pop_back(); 00643 --i; --e; 00644 } else if (IntervalPos->start <= CurPoint) { 00645 // move re-activated intervals in active list 00646 DOUT << "\t\tinterval " << *Interval << " active\n"; 00647 assert(TargetRegisterInfo::isVirtualRegister(reg) && 00648 "Can only allocate virtual registers!"); 00649 reg = vrm_->getPhys(reg); 00650 addRegUse(reg); 00651 // add to active 00652 active_.push_back(std::make_pair(Interval, IntervalPos)); 00653 00654 // Pop off the end of the list. 00655 inactive_[i] = inactive_.back(); 00656 inactive_.pop_back(); 00657 --i; --e; 00658 } else { 00659 // Otherwise, just update the iterator position. 00660 inactive_[i].second = IntervalPos; 00661 } 00662 } 00663 } 00664 00665 /// updateSpillWeights - updates the spill weights of the specifed physical 00666 /// register and its weight. 00667 void RALinScan::updateSpillWeights(std::vector<float> &Weights, 00668 unsigned reg, float weight, 00669 const TargetRegisterClass *RC) { 00670 SmallSet<unsigned, 4> Processed; 00671 SmallSet<unsigned, 4> SuperAdded; 00672 SmallVector<unsigned, 4> Supers; 00673 Weights[reg] += weight; 00674 Processed.insert(reg); 00675 for (const unsigned* as = tri_->getAliasSet(reg); *as; ++as) { 00676 Weights[*as] += weight; 00677 Processed.insert(*as); 00678 if (tri_->isSubRegister(*as, reg) && 00679 SuperAdded.insert(*as) && 00680 RC->contains(*as)) { 00681 Supers.push_back(*as); 00682 } 00683 } 00684 00685 // If the alias is a super-register, and the super-register is in the 00686 // register class we are trying to allocate. Then add the weight to all 00687 // sub-registers of the super-register even if they are not aliases. 00688 // e.g. allocating for GR32, bh is not used, updating bl spill weight. 00689 // bl should get the same spill weight otherwise it will be choosen 00690 // as a spill candidate since spilling bh doesn't make ebx available. 00691 for (unsigned i = 0, e = Supers.size(); i != e; ++i) { 00692 for (const unsigned *sr = tri_->getSubRegisters(Supers[i]); *sr; ++sr) 00693 if (!Processed.count(*sr)) 00694 Weights[*sr] += weight; 00695 } 00696 } 00697 00698 static 00699 RALinScan::IntervalPtrs::iterator 00700 FindIntervalInVector(RALinScan::IntervalPtrs &IP, LiveInterval *LI) { 00701 for (RALinScan::IntervalPtrs::iterator I = IP.begin(), E = IP.end(); 00702 I != E; ++I) 00703 if (I->first == LI) return I; 00704 return IP.end(); 00705 } 00706 00707 static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V, unsigned Point){ 00708 for (unsigned i = 0, e = V.size(); i != e; ++i) { 00709 RALinScan::IntervalPtr &IP = V[i]; 00710 LiveInterval::iterator I = std::upper_bound(IP.first->begin(), 00711 IP.second, Point); 00712 if (I != IP.first->begin()) --I; 00713 IP.second = I; 00714 } 00715 } 00716 00717 /// addStackInterval - Create a LiveInterval for stack if the specified live 00718 /// interval has been spilled. 00719 static void addStackInterval(LiveInterval *cur, LiveStacks *ls_, 00720 LiveIntervals *li_, 00721 MachineRegisterInfo* mri_, VirtRegMap &vrm_) { 00722 int SS = vrm_.getStackSlot(cur->reg); 00723 if (SS == VirtRegMap::NO_STACK_SLOT) 00724 return; 00725 00726 const TargetRegisterClass *RC = mri_->getRegClass(cur->reg); 00727 LiveInterval &SI = ls_->getOrCreateInterval(SS, RC); 00728 00729 VNInfo *VNI; 00730 if (SI.hasAtLeastOneValue()) 00731 VNI = SI.getValNumInfo(0); 00732 else 00733 VNI = SI.getNextValue(0, 0, false, ls_->getVNInfoAllocator()); 00734 00735 LiveInterval &RI = li_->getInterval(cur->reg); 00736 // FIXME: This may be overly conservative. 00737 SI.MergeRangesInAsValue(RI, VNI); 00738 } 00739 00740 /// getConflictWeight - Return the number of conflicts between cur 00741 /// live interval and defs and uses of Reg weighted by loop depthes. 00742 static 00743 float getConflictWeight(LiveInterval *cur, unsigned Reg, LiveIntervals *li_, 00744 MachineRegisterInfo *mri_, 00745 const MachineLoopInfo *loopInfo) { 00746 float Conflicts = 0; 00747 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(Reg), 00748 E = mri_->reg_end(); I != E; ++I) { 00749 MachineInstr *MI = &*I; 00750 if (cur->liveAt(li_->getInstructionIndex(MI))) { 00751 unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent()); 00752 Conflicts += powf(10.0f, (float)loopDepth); 00753 } 00754 } 00755 return Conflicts; 00756 } 00757 00758 /// findIntervalsToSpill - Determine the intervals to spill for the 00759 /// specified interval. It's passed the physical registers whose spill 00760 /// weight is the lowest among all the registers whose live intervals 00761 /// conflict with the interval. 00762 void RALinScan::findIntervalsToSpill(LiveInterval *cur, 00763 std::vector<std::pair<unsigned,float> > &Candidates, 00764 unsigned NumCands, 00765 SmallVector<LiveInterval*, 8> &SpillIntervals) { 00766 // We have figured out the *best* register to spill. But there are other 00767 // registers that are pretty good as well (spill weight within 3%). Spill 00768 // the one that has fewest defs and uses that conflict with cur. 00769 float Conflicts[3] = { 0.0f, 0.0f, 0.0f }; 00770 SmallVector<LiveInterval*, 8> SLIs[3]; 00771 00772 DOUT << "\tConsidering " << NumCands << " candidates: "; 00773 DEBUG(for (unsigned i = 0; i != NumCands; ++i) 00774 DOUT << tri_->getName(Candidates[i].first) << " "; 00775 DOUT << "\n";); 00776 00777 // Calculate the number of conflicts of each candidate. 00778 for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) { 00779 unsigned Reg = i->first->reg; 00780 unsigned PhysReg = vrm_->getPhys(Reg); 00781 if (!cur->overlapsFrom(*i->first, i->second)) 00782 continue; 00783 for (unsigned j = 0; j < NumCands; ++j) { 00784 unsigned Candidate = Candidates[j].first; 00785 if (tri_->regsOverlap(PhysReg, Candidate)) { 00786 if (NumCands > 1) 00787 Conflicts[j] += getConflictWeight(cur, Reg, li_, mri_, loopInfo); 00788 SLIs[j].push_back(i->first); 00789 } 00790 } 00791 } 00792 00793 for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end(); ++i){ 00794 unsigned Reg = i->first->reg; 00795 unsigned PhysReg = vrm_->getPhys(Reg); 00796 if (!cur->overlapsFrom(*i->first, i->second-1)) 00797 continue; 00798 for (unsigned j = 0; j < NumCands; ++j) { 00799 unsigned Candidate = Candidates[j].first; 00800 if (tri_->regsOverlap(PhysReg, Candidate)) { 00801 if (NumCands > 1) 00802 Conflicts[j] += getConflictWeight(cur, Reg, li_, mri_, loopInfo); 00803 SLIs[j].push_back(i->first); 00804 } 00805 } 00806 } 00807 00808 // Which is the best candidate? 00809 unsigned BestCandidate = 0; 00810 float MinConflicts = Conflicts[0]; 00811 for (unsigned i = 1; i != NumCands; ++i) { 00812 if (Conflicts[i] < MinConflicts) { 00813 BestCandidate = i; 00814 MinConflicts = Conflicts[i]; 00815 } 00816 } 00817 00818 std::copy(SLIs[BestCandidate].begin(), SLIs[BestCandidate].end(), 00819 std::back_inserter(SpillIntervals)); 00820 } 00821 00822 namespace { 00823 struct WeightCompare { 00824 typedef std::pair<unsigned, float> RegWeightPair; 00825 bool operator()(const RegWeightPair &LHS, const RegWeightPair &RHS) const { 00826 return LHS.second < RHS.second; 00827 } 00828 }; 00829 } 00830 00831 static bool weightsAreClose(float w1, float w2) { 00832 if (!NewHeuristic) 00833 return false; 00834 00835 float diff = w1 - w2; 00836 if (diff <= 0.02f) // Within 0.02f 00837 return true; 00838 return (diff / w2) <= 0.05f; // Within 5%. 00839 } 00840 00841 LiveInterval *RALinScan::hasNextReloadInterval(LiveInterval *cur) { 00842 DenseMap<unsigned, unsigned>::iterator I = NextReloadMap.find(cur->reg); 00843 if (I == NextReloadMap.end()) 00844 return 0; 00845 return &li_->getInterval(I->second); 00846 } 00847 00848 void RALinScan::DowngradeRegister(LiveInterval *li, unsigned Reg) { 00849 bool isNew = DowngradedRegs.insert(Reg); 00850 isNew = isNew; // Silence compiler warning. 00851 assert(isNew && "Multiple reloads holding the same register?"); 00852 DowngradeMap.insert(std::make_pair(li->reg, Reg)); 00853 for (const unsigned *AS = tri_->getAliasSet(Reg); *AS; ++AS) { 00854 isNew = DowngradedRegs.insert(*AS); 00855 isNew = isNew; // Silence compiler warning. 00856 assert(isNew && "Multiple reloads holding the same register?"); 00857 DowngradeMap.insert(std::make_pair(li->reg, *AS)); 00858 } 00859 ++NumDowngrade; 00860 } 00861 00862 void RALinScan::UpgradeRegister(unsigned Reg) { 00863 if (Reg) { 00864 DowngradedRegs.erase(Reg); 00865 for (const unsigned *AS = tri_->getAliasSet(Reg); *AS; ++AS) 00866 DowngradedRegs.erase(*AS); 00867 } 00868 } 00869 00870 namespace { 00871 struct LISorter { 00872 bool operator()(LiveInterval* A, LiveInterval* B) { 00873 return A->beginNumber() < B->beginNumber(); 00874 } 00875 }; 00876 } 00877 00878 /// assignRegOrStackSlotAtInterval - assign a register if one is available, or 00879 /// spill. 00880 void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur) 00881 { 00882 DOUT << "\tallocating current interval: "; 00883 00884 // This is an implicitly defined live interval, just assign any register. 00885 const TargetRegisterClass *RC = mri_->getRegClass(cur->reg); 00886 if (cur->empty()) { 00887 unsigned physReg = vrm_->getRegAllocPref(cur->reg); 00888 if (!physReg) 00889 physReg = *RC->allocation_order_begin(*mf_); 00890 DOUT << tri_->getName(physReg) << '\n'; 00891 // Note the register is not really in use. 00892 vrm_->assignVirt2Phys(cur->reg, physReg); 00893 return; 00894 } 00895 00896 backUpRegUses(); 00897 00898 std::vector<std::pair<unsigned, float> > SpillWeightsToAdd; 00899 unsigned StartPosition = cur->beginNumber(); 00900 const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC); 00901 00902 // If start of this live interval is defined by a move instruction and its 00903 // source is assigned a physical register that is compatible with the target 00904 // register class, then we should try to assign it the same register. 00905 // This can happen when the move is from a larger register class to a smaller 00906 // one, e.g. X86::mov32to32_. These move instructions are not coalescable. 00907 if (!vrm_->getRegAllocPref(cur->reg) && cur->hasAtLeastOneValue()) { 00908 VNInfo *vni = cur->begin()->valno; 00909 if (vni->def && !vni->isUnused() && vni->isDefAccurate()) { 00910 MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def); 00911 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 00912 if (CopyMI && 00913 tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubReg, DstSubReg)) { 00914 unsigned Reg = 0; 00915 if (TargetRegisterInfo::isPhysicalRegister(SrcReg)) 00916 Reg = SrcReg; 00917 else if (vrm_->isAssignedReg(SrcReg)) 00918 Reg = vrm_->getPhys(SrcReg); 00919 if (Reg) { 00920 if (SrcSubReg) 00921 Reg = tri_->getSubReg(Reg, SrcSubReg); 00922 if (DstSubReg) 00923 Reg = tri_->getMatchingSuperReg(Reg, DstSubReg, RC); 00924 if (Reg && allocatableRegs_[Reg] && RC->contains(Reg)) 00925 mri_->setRegAllocationHint(cur->reg, 0, Reg); 00926 } 00927 } 00928 } 00929 } 00930 00931 // For every interval in inactive we overlap with, mark the 00932 // register as not free and update spill weights. 00933 for (IntervalPtrs::const_iterator i = inactive_.begin(), 00934 e = inactive_.end(); i != e; ++i) { 00935 unsigned Reg = i->first->reg; 00936 assert(TargetRegisterInfo::isVirtualRegister(Reg) && 00937 "Can only allocate virtual registers!"); 00938 const TargetRegisterClass *RegRC = mri_->getRegClass(Reg); 00939 // If this is not in a related reg class to the register we're allocating, 00940 // don't check it. 00941 if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader && 00942 cur->overlapsFrom(*i->first, i->second-1)) { 00943 Reg = vrm_->getPhys(Reg); 00944 addRegUse(Reg); 00945 SpillWeightsToAdd.push_back(std::make_pair(Reg, i->first->weight)); 00946 } 00947 } 00948 00949 // Speculatively check to see if we can get a register right now. If not, 00950 // we know we won't be able to by adding more constraints. If so, we can 00951 // check to see if it is valid. Doing an exhaustive search of the fixed_ list 00952 // is very bad (it contains all callee clobbered registers for any functions 00953 // with a call), so we want to avoid doing that if possible. 00954 unsigned physReg = getFreePhysReg(cur); 00955 unsigned BestPhysReg = physReg; 00956 if (physReg) { 00957 // We got a register. However, if it's in the fixed_ list, we might 00958 // conflict with it. Check to see if we conflict with it or any of its 00959 // aliases. 00960 SmallSet<unsigned, 8> RegAliases; 00961 for (const unsigned *AS = tri_->getAliasSet(physReg); *AS; ++AS) 00962 RegAliases.insert(*AS); 00963 00964 bool ConflictsWithFixed = false; 00965 for (unsigned i = 0, e = fixed_.size(); i != e; ++i) { 00966 IntervalPtr &IP = fixed_[i]; 00967 if (physReg == IP.first->reg || RegAliases.count(IP.first->reg)) { 00968 // Okay, this reg is on the fixed list. Check to see if we actually 00969 // conflict. 00970 LiveInterval *I = IP.first; 00971 if (I->endNumber() > StartPosition) { 00972 LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition); 00973 IP.second = II; 00974 if (II != I->begin() && II->start > StartPosition) 00975 --II; 00976 if (cur->overlapsFrom(*I, II)) { 00977 ConflictsWithFixed = true; 00978 break; 00979 } 00980 } 00981 } 00982 } 00983 00984 // Okay, the register picked by our speculative getFreePhysReg call turned 00985 // out to be in use. Actually add all of the conflicting fixed registers to 00986 // regUse_ so we can do an accurate query. 00987 if (ConflictsWithFixed) { 00988 // For every interval in fixed we overlap with, mark the register as not 00989 // free and update spill weights. 00990 for (unsigned i = 0, e = fixed_.size(); i != e; ++i) { 00991 IntervalPtr &IP = fixed_[i]; 00992 LiveInterval *I = IP.first; 00993 00994 const TargetRegisterClass *RegRC = OneClassForEachPhysReg[I->reg]; 00995 if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader && 00996 I->endNumber() > StartPosition) { 00997 LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition); 00998 IP.second = II; 00999 if (II != I->begin() && II->start > StartPosition) 01000 --II; 01001 if (cur->overlapsFrom(*I, II)) { 01002 unsigned reg = I->reg; 01003 addRegUse(reg); 01004 SpillWeightsToAdd.push_back(std::make_pair(reg, I->weight)); 01005 } 01006 } 01007 } 01008 01009 // Using the newly updated regUse_ object, which includes conflicts in the 01010 // future, see if there are any registers available. 01011 physReg = getFreePhysReg(cur); 01012 } 01013 } 01014 01015 // Restore the physical register tracker, removing information about the 01016 // future. 01017 restoreRegUses(); 01018 01019 // If we find a free register, we are done: assign this virtual to 01020 // the free physical register and add this interval to the active 01021 // list. 01022 if (physReg) { 01023 DOUT << tri_->getName(physReg) << '\n'; 01024 vrm_->assignVirt2Phys(cur->reg, physReg); 01025 addRegUse(physReg); 01026 active_.push_back(std::make_pair(cur, cur->begin())); 01027 handled_.push_back(cur); 01028 01029 // "Upgrade" the physical register since it has been allocated. 01030 UpgradeRegister(physReg); 01031 if (LiveInterval *NextReloadLI = hasNextReloadInterval(cur)) { 01032 // "Downgrade" physReg to try to keep physReg from being allocated until 01033 // the next reload from the same SS is allocated. 01034 mri_->setRegAllocationHint(NextReloadLI->reg, 0, physReg); 01035 DowngradeRegister(cur, physReg); 01036 } 01037 return; 01038 } 01039 DOUT << "no free registers\n"; 01040 01041 // Compile the spill weights into an array that is better for scanning. 01042 std::vector<float> SpillWeights(tri_->getNumRegs(), 0.0f); 01043 for (std::vector<std::pair<unsigned, float> >::iterator 01044 I = SpillWeightsToAdd.begin(), E = SpillWeightsToAdd.end(); I != E; ++I) 01045 updateSpillWeights(SpillWeights, I->first, I->second, RC); 01046 01047 // for each interval in active, update spill weights. 01048 for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end(); 01049 i != e; ++i) { 01050 unsigned reg = i->first->reg; 01051 assert(TargetRegisterInfo::isVirtualRegister(reg) && 01052 "Can only allocate virtual registers!"); 01053 reg = vrm_->getPhys(reg); 01054 updateSpillWeights(SpillWeights, reg, i->first->weight, RC); 01055 } 01056 01057 DOUT << "\tassigning stack slot at interval "<< *cur << ":\n"; 01058 01059 // Find a register to spill. 01060 float minWeight = HUGE_VALF; 01061 unsigned minReg = 0; 01062 01063 bool Found = false; 01064 std::vector<std::pair<unsigned,float> > RegsWeights; 01065 if (!minReg || SpillWeights[minReg] == HUGE_VALF) 01066 for (TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_), 01067 e = RC->allocation_order_end(*mf_); i != e; ++i) { 01068 unsigned reg = *i; 01069 float regWeight = SpillWeights[reg]; 01070 if (minWeight > regWeight) 01071 Found = true; 01072 RegsWeights.push_back(std::make_pair(reg, regWeight)); 01073 } 01074 01075 // If we didn't find a register that is spillable, try aliases? 01076 if (!Found) { 01077 for (TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_), 01078 e = RC->allocation_order_end(*mf_); i != e; ++i) { 01079 unsigned reg = *i; 01080 // No need to worry about if the alias register size < regsize of RC. 01081 // We are going to spill all registers that alias it anyway. 01082 for (const unsigned* as = tri_->getAliasSet(reg); *as; ++as) 01083 RegsWeights.push_back(std::make_pair(*as, SpillWeights[*as])); 01084 } 01085 } 01086 01087 // Sort all potential spill candidates by weight. 01088 std::sort(RegsWeights.begin(), RegsWeights.end(), WeightCompare()); 01089 minReg = RegsWeights[0].first; 01090 minWeight = RegsWeights[0].second; 01091 if (minWeight == HUGE_VALF) { 01092 // All registers must have inf weight. Just grab one! 01093 minReg = BestPhysReg ? BestPhysReg : *RC->allocation_order_begin(*mf_); 01094 if (cur->weight == HUGE_VALF || 01095 li_->getApproximateInstructionCount(*cur) == 0) { 01096 // Spill a physical register around defs and uses. 01097 if (li_->spillPhysRegAroundRegDefsUses(*cur, minReg, *vrm_)) { 01098 // spillPhysRegAroundRegDefsUses may have invalidated iterator stored 01099 // in fixed_. Reset them. 01100 for (unsigned i = 0, e = fixed_.size(); i != e; ++i) { 01101 IntervalPtr &IP = fixed_[i]; 01102 LiveInterval *I = IP.first; 01103 if (I->reg == minReg || tri_->isSubRegister(minReg, I->reg)) 01104 IP.second = I->advanceTo(I->begin(), StartPosition); 01105 } 01106 01107 DowngradedRegs.clear(); 01108 assignRegOrStackSlotAtInterval(cur); 01109 } else { 01110 llvm_report_error("Ran out of registers during register allocation!"); 01111 } 01112 return; 01113 } 01114 } 01115 01116 // Find up to 3 registers to consider as spill candidates. 01117 unsigned LastCandidate = RegsWeights.size() >= 3 ? 3 : 1; 01118 while (LastCandidate > 1) { 01119 if (weightsAreClose(RegsWeights[LastCandidate-1].second, minWeight)) 01120 break; 01121 --LastCandidate; 01122 } 01123 01124 DOUT << "\t\tregister(s) with min weight(s): "; 01125 DEBUG(for (unsigned i = 0; i != LastCandidate; ++i) 01126 DOUT << tri_->getName(RegsWeights[i].first) 01127 << " (" << RegsWeights[i].second << ")\n"); 01128 01129 // If the current has the minimum weight, we need to spill it and 01130 // add any added intervals back to unhandled, and restart 01131 // linearscan. 01132 if (cur->weight != HUGE_VALF && cur->weight <= minWeight) { 01133 DOUT << "\t\t\tspilling(c): " << *cur << '\n'; 01134 SmallVector<LiveInterval*, 8> spillIs; 01135 std::vector<LiveInterval*> added; 01136 01137 if (!NewSpillFramework) { 01138 added = li_->addIntervalsForSpills(*cur, spillIs, loopInfo, *vrm_); 01139 } else { 01140 added = spiller_->spill(cur); 01141 } 01142 01143 std::sort(added.begin(), added.end(), LISorter()); 01144 addStackInterval(cur, ls_, li_, mri_, *vrm_); 01145 if (added.empty()) 01146 return; // Early exit if all spills were folded. 01147 01148 // Merge added with unhandled. Note that we have already sorted 01149 // intervals returned by addIntervalsForSpills by their starting 01150 // point. 01151 // This also update the NextReloadMap. That is, it adds mapping from a 01152 // register defined by a reload from SS to the next reload from SS in the 01153 // same basic block. 01154 MachineBasicBlock *LastReloadMBB = 0; 01155 LiveInterval *LastReload = 0; 01156 int LastReloadSS = VirtRegMap::NO_STACK_SLOT; 01157 for (unsigned i = 0, e = added.size(); i != e; ++i) { 01158 LiveInterval *ReloadLi = added[i]; 01159 if (ReloadLi->weight == HUGE_VALF && 01160 li_->getApproximateInstructionCount(*ReloadLi) == 0) { 01161 unsigned ReloadIdx = ReloadLi->beginNumber(); 01162 MachineBasicBlock *ReloadMBB = li_->getMBBFromIndex(ReloadIdx); 01163 int ReloadSS = vrm_->getStackSlot(ReloadLi->reg); 01164 if (LastReloadMBB == ReloadMBB && LastReloadSS == ReloadSS) { 01165 // Last reload of same SS is in the same MBB. We want to try to 01166 // allocate both reloads the same register and make sure the reg 01167 // isn't clobbered in between if at all possible. 01168 assert(LastReload->beginNumber() < ReloadIdx); 01169 NextReloadMap.insert(std::make_pair(LastReload->reg, ReloadLi->reg)); 01170 } 01171 LastReloadMBB = ReloadMBB; 01172 LastReload = ReloadLi; 01173 LastReloadSS = ReloadSS; 01174 } 01175 unhandled_.push(ReloadLi); 01176 } 01177 return; 01178 } 01179 01180 ++NumBacktracks; 01181 01182 // Push the current interval back to unhandled since we are going 01183 // to re-run at least this iteration. Since we didn't modify it it 01184 // should go back right in the front of the list 01185 unhandled_.push(cur); 01186 01187 assert(TargetRegisterInfo::isPhysicalRegister(minReg) && 01188 "did not choose a register to spill?"); 01189 01190 // We spill all intervals aliasing the register with 01191 // minimum weight, rollback to the interval with the earliest 01192 // start point and let the linear scan algorithm run again 01193 SmallVector<LiveInterval*, 8> spillIs; 01194 01195 // Determine which intervals have to be spilled. 01196 findIntervalsToSpill(cur, RegsWeights, LastCandidate, spillIs); 01197 01198 // Set of spilled vregs (used later to rollback properly) 01199 SmallSet<unsigned, 8> spilled; 01200 01201 // The earliest start of a Spilled interval indicates up to where 01202 // in handled we need to roll back 01203 01204 LiveInterval *earliestStartInterval = cur; 01205 01206 // Spill live intervals of virtual regs mapped to the physical register we 01207 // want to clear (and its aliases). We only spill those that overlap with the 01208 // current interval as the rest do not affect its allocation. we also keep 01209 // track of the earliest start of all spilled live intervals since this will 01210 // mark our rollback point. 01211 std::vector<LiveInterval*> added; 01212 while (!spillIs.empty()) { 01213 LiveInterval *sli = spillIs.back(); 01214 spillIs.pop_back(); 01215 DOUT << "\t\t\tspilling(a): " << *sli << '\n'; 01216 earliestStartInterval = 01217 (earliestStartInterval->beginNumber() < sli->beginNumber()) ? 01218 earliestStartInterval : sli; 01219 01220 std::vector<LiveInterval*> newIs; 01221 if (!NewSpillFramework) { 01222 newIs = li_->addIntervalsForSpills(*sli, spillIs, loopInfo, *vrm_); 01223 } else { 01224 newIs = spiller_->spill(sli); 01225 } 01226 addStackInterval(sli, ls_, li_, mri_, *vrm_); 01227 std::copy(newIs.begin(), newIs.end(), std::back_inserter(added)); 01228 spilled.insert(sli->reg); 01229 } 01230 01231 unsigned earliestStart = earliestStartInterval->beginNumber(); 01232 01233 DOUT << "\t\trolling back to: " << earliestStart << '\n'; 01234 01235 // Scan handled in reverse order up to the earliest start of a 01236 // spilled live interval and undo each one, restoring the state of 01237 // unhandled. 01238 while (!handled_.empty()) { 01239 LiveInterval* i = handled_.back(); 01240 // If this interval starts before t we are done. 01241 if (i->beginNumber() < earliestStart) 01242 break; 01243 DOUT << "\t\t\tundo changes for: " << *i << '\n'; 01244 handled_.pop_back(); 01245 01246 // When undoing a live interval allocation we must know if it is active or 01247 // inactive to properly update regUse_ and the VirtRegMap. 01248 IntervalPtrs::iterator it; 01249 if ((it = FindIntervalInVector(active_, i)) != active_.end()) { 01250 active_.erase(it); 01251 assert(!TargetRegisterInfo::isPhysicalRegister(i->reg)); 01252 if (!spilled.count(i->reg)) 01253 unhandled_.push(i); 01254 delRegUse(vrm_->getPhys(i->reg)); 01255 vrm_->clearVirt(i->reg); 01256 } else if ((it = FindIntervalInVector(inactive_, i)) != inactive_.end()) { 01257 inactive_.erase(it); 01258 assert(!TargetRegisterInfo::isPhysicalRegister(i->reg)); 01259 if (!spilled.count(i->reg)) 01260 unhandled_.push(i); 01261 vrm_->clearVirt(i->reg); 01262 } else { 01263 assert(TargetRegisterInfo::isVirtualRegister(i->reg) && 01264 "Can only allocate virtual registers!"); 01265 vrm_->clearVirt(i->reg); 01266 unhandled_.push(i); 01267 } 01268 01269 DenseMap<unsigned, unsigned>::iterator ii = DowngradeMap.find(i->reg); 01270 if (ii == DowngradeMap.end()) 01271 // It interval has a preference, it must be defined by a copy. Clear the 01272 // preference now since the source interval allocation may have been 01273 // undone as well. 01274 mri_->setRegAllocationHint(i->reg, 0, 0); 01275 else { 01276 UpgradeRegister(ii->second); 01277 } 01278 } 01279 01280 // Rewind the iterators in the active, inactive, and fixed lists back to the 01281 // point we reverted to. 01282 RevertVectorIteratorsTo(active_, earliestStart); 01283 RevertVectorIteratorsTo(inactive_, earliestStart); 01284 RevertVectorIteratorsTo(fixed_, earliestStart); 01285 01286 // Scan the rest and undo each interval that expired after t and 01287 // insert it in active (the next iteration of the algorithm will 01288 // put it in inactive if required) 01289 for (unsigned i = 0, e = handled_.size(); i != e; ++i) { 01290 LiveInterval *HI = handled_[i]; 01291 if (!HI->expiredAt(earliestStart) && 01292 HI->expiredAt(cur->beginNumber())) { 01293 DOUT << "\t\t\tundo changes for: " << *HI << '\n'; 01294 active_.push_back(std::make_pair(HI, HI->begin())); 01295 assert(!TargetRegisterInfo::isPhysicalRegister(HI->reg)); 01296 addRegUse(vrm_->getPhys(HI->reg)); 01297 } 01298 } 01299 01300 // Merge added with unhandled. 01301 // This also update the NextReloadMap. That is, it adds mapping from a 01302 // register defined by a reload from SS to the next reload from SS in the 01303 // same basic block. 01304 MachineBasicBlock *LastReloadMBB = 0; 01305 LiveInterval *LastReload = 0; 01306 int LastReloadSS = VirtRegMap::NO_STACK_SLOT; 01307 std::sort(added.begin(), added.end(), LISorter()); 01308 for (unsigned i = 0, e = added.size(); i != e; ++i) { 01309 LiveInterval *ReloadLi = added[i]; 01310 if (ReloadLi->weight == HUGE_VALF && 01311 li_->getApproximateInstructionCount(*ReloadLi) == 0) { 01312 unsigned ReloadIdx = ReloadLi->beginNumber(); 01313 MachineBasicBlock *ReloadMBB = li_->getMBBFromIndex(ReloadIdx); 01314 int ReloadSS = vrm_->getStackSlot(ReloadLi->reg); 01315 if (LastReloadMBB == ReloadMBB && LastReloadSS == ReloadSS) { 01316 // Last reload of same SS is in the same MBB. We want to try to 01317 // allocate both reloads the same register and make sure the reg 01318 // isn't clobbered in between if at all possible. 01319 assert(LastReload->beginNumber() < ReloadIdx); 01320 NextReloadMap.insert(std::make_pair(LastReload->reg, ReloadLi->reg)); 01321 } 01322 LastReloadMBB = ReloadMBB; 01323 LastReload = ReloadLi; 01324 LastReloadSS = ReloadSS; 01325 } 01326 unhandled_.push(ReloadLi); 01327 } 01328 } 01329 01330 unsigned RALinScan::getFreePhysReg(LiveInterval* cur, 01331 const TargetRegisterClass *RC, 01332 unsigned MaxInactiveCount, 01333 SmallVector<unsigned, 256> &inactiveCounts, 01334 bool SkipDGRegs) { 01335 unsigned FreeReg = 0; 01336 unsigned FreeRegInactiveCount = 0; 01337 01338 std::pair<unsigned, unsigned> Hint = mri_->getRegAllocationHint(cur->reg); 01339 // Resolve second part of the hint (if possible) given the current allocation. 01340 unsigned physReg = Hint.second; 01341 if (physReg && 01342 TargetRegisterInfo::isVirtualRegister(physReg) && vrm_->hasPhys(physReg)) 01343 physReg = vrm_->getPhys(physReg); 01344 01345 TargetRegisterClass::iterator I, E; 01346 tie(I, E) = tri_->getAllocationOrder(RC, Hint.first, physReg, *mf_); 01347 assert(I != E && "No allocatable register in this register class!"); 01348 01349 // Scan for the first available register. 01350 for (; I != E; ++I) { 01351 unsigned Reg = *I; 01352 // Ignore "downgraded" registers. 01353 if (SkipDGRegs && DowngradedRegs.count(Reg)) 01354 continue; 01355 if (isRegAvail(Reg)) { 01356 FreeReg = Reg; 01357 if (FreeReg < inactiveCounts.size()) 01358 FreeRegInactiveCount = inactiveCounts[FreeReg]; 01359 else 01360 FreeRegInactiveCount = 0; 01361 break; 01362 } 01363 } 01364 01365 // If there are no free regs, or if this reg has the max inactive count, 01366 // return this register. 01367 if (FreeReg == 0 || FreeRegInactiveCount == MaxInactiveCount) 01368 return FreeReg; 01369 01370 // Continue scanning the registers, looking for the one with the highest 01371 // inactive count. Alkis found that this reduced register pressure very 01372 // slightly on X86 (in rev 1.94 of this file), though this should probably be 01373 // reevaluated now. 01374 for (; I != E; ++I) { 01375 unsigned Reg = *I; 01376 // Ignore "downgraded" registers. 01377 if (SkipDGRegs && DowngradedRegs.count(Reg)) 01378 continue; 01379 if (isRegAvail(Reg) && Reg < inactiveCounts.size() && 01380 FreeRegInactiveCount < inactiveCounts[Reg]) { 01381 FreeReg = Reg; 01382 FreeRegInactiveCount = inactiveCounts[Reg]; 01383 if (FreeRegInactiveCount == MaxInactiveCount) 01384 break; // We found the one with the max inactive count. 01385 } 01386 } 01387 01388 return FreeReg; 01389 } 01390 01391 /// getFreePhysReg - return a free physical register for this virtual register 01392 /// interval if we have one, otherwise return 0. 01393 unsigned RALinScan::getFreePhysReg(LiveInterval *cur) { 01394 SmallVector<unsigned, 256> inactiveCounts; 01395 unsigned MaxInactiveCount = 0; 01396 01397 const TargetRegisterClass *RC = mri_->getRegClass(cur->reg); 01398 const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC); 01399 01400 for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end(); 01401 i != e; ++i) { 01402 unsigned reg = i->first->reg; 01403 assert(TargetRegisterInfo::isVirtualRegister(reg) && 01404 "Can only allocate virtual registers!"); 01405 01406 // If this is not in a related reg class to the register we're allocating, 01407 // don't check it. 01408 const TargetRegisterClass *RegRC = mri_->getRegClass(reg); 01409 if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader) { 01410 reg = vrm_->getPhys(reg); 01411 if (inactiveCounts.size() <= reg) 01412 inactiveCounts.resize(reg+1); 01413 ++inactiveCounts[reg]; 01414 MaxInactiveCount = std::max(MaxInactiveCount, inactiveCounts[reg]); 01415 } 01416 } 01417 01418 // If copy coalescer has assigned a "preferred" register, check if it's 01419 // available first. 01420 unsigned Preference = vrm_->getRegAllocPref(cur->reg); 01421 if (Preference) { 01422 DOUT << "(preferred: " << tri_->getName(Preference) << ") "; 01423 if (isRegAvail(Preference) && 01424 RC->contains(Preference)) 01425 return Preference; 01426 } 01427 01428 if (!DowngradedRegs.empty()) { 01429 unsigned FreeReg = getFreePhysReg(cur, RC, MaxInactiveCount, inactiveCounts, 01430 true); 01431 if (FreeReg) 01432 return FreeReg; 01433 } 01434 return getFreePhysReg(cur, RC, MaxInactiveCount, inactiveCounts, false); 01435 } 01436 01437 FunctionPass* llvm::createLinearScanRegisterAllocator() { 01438 return new RALinScan(); 01439 }