LLVM API Documentation
00001 //===------ RegAllocPBQP.cpp ---- PBQP Register Allocator -------*- C++ -*-===// 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 contains a Partitioned Boolean Quadratic Programming (PBQP) based 00011 // register allocator for LLVM. This allocator works by constructing a PBQP 00012 // problem representing the register allocation problem under consideration, 00013 // solving this using a PBQP solver, and mapping the solution back to a 00014 // register assignment. If any variables are selected for spilling then spill 00015 // code is inserted and the process repeated. 00016 // 00017 // The PBQP solver (pbqp.c) provided for this allocator uses a heuristic tuned 00018 // for register allocation. For more information on PBQP for register 00019 // allocation, see the following papers: 00020 // 00021 // (1) Hames, L. and Scholz, B. 2006. Nearly optimal register allocation with 00022 // PBQP. In Proceedings of the 7th Joint Modular Languages Conference 00023 // (JMLC'06). LNCS, vol. 4228. Springer, New York, NY, USA. 346-361. 00024 // 00025 // (2) Scholz, B., Eckstein, E. 2002. Register allocation for irregular 00026 // architectures. In Proceedings of the Joint Conference on Languages, 00027 // Compilers and Tools for Embedded Systems (LCTES'02), ACM Press, New York, 00028 // NY, USA, 139-148. 00029 // 00030 //===----------------------------------------------------------------------===// 00031 00032 #define DEBUG_TYPE "regalloc" 00033 00034 #include "PBQP/HeuristicSolver.h" 00035 #include "PBQP/SimpleGraph.h" 00036 #include "PBQP/Heuristics/Briggs.h" 00037 #include "VirtRegMap.h" 00038 #include "VirtRegRewriter.h" 00039 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 00040 #include "llvm/CodeGen/LiveStackAnalysis.h" 00041 #include "llvm/CodeGen/MachineFunctionPass.h" 00042 #include "llvm/CodeGen/MachineLoopInfo.h" 00043 #include "llvm/CodeGen/MachineRegisterInfo.h" 00044 #include "llvm/CodeGen/RegAllocRegistry.h" 00045 #include "llvm/CodeGen/RegisterCoalescer.h" 00046 #include "llvm/Support/Debug.h" 00047 #include "llvm/Support/raw_ostream.h" 00048 #include "llvm/Target/TargetInstrInfo.h" 00049 #include "llvm/Target/TargetMachine.h" 00050 #include <limits> 00051 #include <map> 00052 #include <memory> 00053 #include <set> 00054 #include <vector> 00055 00056 using namespace llvm; 00057 00058 static RegisterRegAlloc 00059 registerPBQPRepAlloc("pbqp", "PBQP register allocator.", 00060 llvm::createPBQPRegisterAllocator); 00061 00062 static cl::opt<bool> 00063 pbqpCoalescing("pbqp-coalescing", 00064 cl::desc("Attempt coalescing during PBQP register allocation."), 00065 cl::init(false), cl::Hidden); 00066 00067 namespace { 00068 00069 /// 00070 /// PBQP based allocators solve the register allocation problem by mapping 00071 /// register allocation problems to Partitioned Boolean Quadratic 00072 /// Programming problems. 00073 class VISIBILITY_HIDDEN PBQPRegAlloc : public MachineFunctionPass { 00074 public: 00075 00076 static char ID; 00077 00078 /// Construct a PBQP register allocator. 00079 PBQPRegAlloc() : MachineFunctionPass(&ID) {} 00080 00081 /// Return the pass name. 00082 virtual const char* getPassName() const { 00083 return "PBQP Register Allocator"; 00084 } 00085 00086 /// PBQP analysis usage. 00087 virtual void getAnalysisUsage(AnalysisUsage &au) const { 00088 au.addRequired<LiveIntervals>(); 00089 //au.addRequiredID(SplitCriticalEdgesID); 00090 au.addRequired<RegisterCoalescer>(); 00091 au.addRequired<LiveStacks>(); 00092 au.addPreserved<LiveStacks>(); 00093 au.addRequired<MachineLoopInfo>(); 00094 au.addPreserved<MachineLoopInfo>(); 00095 au.addRequired<VirtRegMap>(); 00096 MachineFunctionPass::getAnalysisUsage(au); 00097 } 00098 00099 /// Perform register allocation 00100 virtual bool runOnMachineFunction(MachineFunction &MF); 00101 00102 private: 00103 typedef std::map<const LiveInterval*, unsigned> LI2NodeMap; 00104 typedef std::vector<const LiveInterval*> Node2LIMap; 00105 typedef std::vector<unsigned> AllowedSet; 00106 typedef std::vector<AllowedSet> AllowedSetMap; 00107 typedef std::set<unsigned> RegSet; 00108 typedef std::pair<unsigned, unsigned> RegPair; 00109 typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap; 00110 00111 typedef std::set<LiveInterval*> LiveIntervalSet; 00112 00113 MachineFunction *mf; 00114 const TargetMachine *tm; 00115 const TargetRegisterInfo *tri; 00116 const TargetInstrInfo *tii; 00117 const MachineLoopInfo *loopInfo; 00118 MachineRegisterInfo *mri; 00119 00120 LiveIntervals *lis; 00121 LiveStacks *lss; 00122 VirtRegMap *vrm; 00123 00124 LI2NodeMap li2Node; 00125 Node2LIMap node2LI; 00126 AllowedSetMap allowedSets; 00127 LiveIntervalSet vregIntervalsToAlloc, 00128 emptyVRegIntervals; 00129 00130 00131 /// Builds a PBQP cost vector. 00132 template <typename RegContainer> 00133 PBQP::Vector buildCostVector(unsigned vReg, 00134 const RegContainer &allowed, 00135 const CoalesceMap &cealesces, 00136 PBQP::PBQPNum spillCost) const; 00137 00138 /// \brief Builds a PBQP interference matrix. 00139 /// 00140 /// @return Either a pointer to a non-zero PBQP matrix representing the 00141 /// allocation option costs, or a null pointer for a zero matrix. 00142 /// 00143 /// Expects allowed sets for two interfering LiveIntervals. These allowed 00144 /// sets should contain only allocable registers from the LiveInterval's 00145 /// register class, with any interfering pre-colored registers removed. 00146 template <typename RegContainer> 00147 PBQP::Matrix* buildInterferenceMatrix(const RegContainer &allowed1, 00148 const RegContainer &allowed2) const; 00149 00150 /// 00151 /// Expects allowed sets for two potentially coalescable LiveIntervals, 00152 /// and an estimated benefit due to coalescing. The allowed sets should 00153 /// contain only allocable registers from the LiveInterval's register 00154 /// classes, with any interfering pre-colored registers removed. 00155 template <typename RegContainer> 00156 PBQP::Matrix* buildCoalescingMatrix(const RegContainer &allowed1, 00157 const RegContainer &allowed2, 00158 PBQP::PBQPNum cBenefit) const; 00159 00160 /// \brief Finds coalescing opportunities and returns them as a map. 00161 /// 00162 /// Any entries in the map are guaranteed coalescable, even if their 00163 /// corresponding live intervals overlap. 00164 CoalesceMap findCoalesces(); 00165 00166 /// \brief Finds the initial set of vreg intervals to allocate. 00167 void findVRegIntervalsToAlloc(); 00168 00169 /// \brief Constructs a PBQP problem representation of the register 00170 /// allocation problem for this function. 00171 /// 00172 /// @return a PBQP solver object for the register allocation problem. 00173 PBQP::SimpleGraph constructPBQPProblem(); 00174 00175 /// \brief Adds a stack interval if the given live interval has been 00176 /// spilled. Used to support stack slot coloring. 00177 void addStackInterval(const LiveInterval *spilled,MachineRegisterInfo* mri); 00178 00179 /// \brief Given a solved PBQP problem maps this solution back to a register 00180 /// assignment. 00181 bool mapPBQPToRegAlloc(const PBQP::Solution &solution); 00182 00183 /// \brief Postprocessing before final spilling. Sets basic block "live in" 00184 /// variables. 00185 void finalizeAlloc() const; 00186 00187 }; 00188 00189 char PBQPRegAlloc::ID = 0; 00190 } 00191 00192 00193 template <typename RegContainer> 00194 PBQP::Vector PBQPRegAlloc::buildCostVector(unsigned vReg, 00195 const RegContainer &allowed, 00196 const CoalesceMap &coalesces, 00197 PBQP::PBQPNum spillCost) const { 00198 00199 typedef typename RegContainer::const_iterator AllowedItr; 00200 00201 // Allocate vector. Additional element (0th) used for spill option 00202 PBQP::Vector v(allowed.size() + 1, 0); 00203 00204 v[0] = spillCost; 00205 00206 // Iterate over the allowed registers inserting coalesce benefits if there 00207 // are any. 00208 unsigned ai = 0; 00209 for (AllowedItr itr = allowed.begin(), end = allowed.end(); 00210 itr != end; ++itr, ++ai) { 00211 00212 unsigned pReg = *itr; 00213 00214 CoalesceMap::const_iterator cmItr = 00215 coalesces.find(RegPair(vReg, pReg)); 00216 00217 // No coalesce - on to the next preg. 00218 if (cmItr == coalesces.end()) 00219 continue; 00220 00221 // We have a coalesce - insert the benefit. 00222 v[ai + 1] = -cmItr->second; 00223 } 00224 00225 return v; 00226 } 00227 00228 template <typename RegContainer> 00229 PBQP::Matrix* PBQPRegAlloc::buildInterferenceMatrix( 00230 const RegContainer &allowed1, const RegContainer &allowed2) const { 00231 00232 typedef typename RegContainer::const_iterator RegContainerIterator; 00233 00234 // Construct a PBQP matrix representing the cost of allocation options. The 00235 // rows and columns correspond to the allocation options for the two live 00236 // intervals. Elements will be infinite where corresponding registers alias, 00237 // since we cannot allocate aliasing registers to interfering live intervals. 00238 // All other elements (non-aliasing combinations) will have zero cost. Note 00239 // that the spill option (element 0,0) has zero cost, since we can allocate 00240 // both intervals to memory safely (the cost for each individual allocation 00241 // to memory is accounted for by the cost vectors for each live interval). 00242 PBQP::Matrix *m = 00243 new PBQP::Matrix(allowed1.size() + 1, allowed2.size() + 1, 0); 00244 00245 // Assume this is a zero matrix until proven otherwise. Zero matrices occur 00246 // between interfering live ranges with non-overlapping register sets (e.g. 00247 // non-overlapping reg classes, or disjoint sets of allowed regs within the 00248 // same class). The term "overlapping" is used advisedly: sets which do not 00249 // intersect, but contain registers which alias, will have non-zero matrices. 00250 // We optimize zero matrices away to improve solver speed. 00251 bool isZeroMatrix = true; 00252 00253 00254 // Row index. Starts at 1, since the 0th row is for the spill option, which 00255 // is always zero. 00256 unsigned ri = 1; 00257 00258 // Iterate over allowed sets, insert infinities where required. 00259 for (RegContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end(); 00260 a1Itr != a1End; ++a1Itr) { 00261 00262 // Column index, starts at 1 as for row index. 00263 unsigned ci = 1; 00264 unsigned reg1 = *a1Itr; 00265 00266 for (RegContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end(); 00267 a2Itr != a2End; ++a2Itr) { 00268 00269 unsigned reg2 = *a2Itr; 00270 00271 // If the row/column regs are identical or alias insert an infinity. 00272 if (tri->regsOverlap(reg1, reg2)) { 00273 (*m)[ri][ci] = std::numeric_limits<PBQP::PBQPNum>::infinity(); 00274 isZeroMatrix = false; 00275 } 00276 00277 ++ci; 00278 } 00279 00280 ++ri; 00281 } 00282 00283 // If this turns out to be a zero matrix... 00284 if (isZeroMatrix) { 00285 // free it and return null. 00286 delete m; 00287 return 0; 00288 } 00289 00290 // ...otherwise return the cost matrix. 00291 return m; 00292 } 00293 00294 template <typename RegContainer> 00295 PBQP::Matrix* PBQPRegAlloc::buildCoalescingMatrix( 00296 const RegContainer &allowed1, const RegContainer &allowed2, 00297 PBQP::PBQPNum cBenefit) const { 00298 00299 typedef typename RegContainer::const_iterator RegContainerIterator; 00300 00301 // Construct a PBQP Matrix representing the benefits of coalescing. As with 00302 // interference matrices the rows and columns represent allowed registers 00303 // for the LiveIntervals which are (potentially) to be coalesced. The amount 00304 // -cBenefit will be placed in any element representing the same register 00305 // for both intervals. 00306 PBQP::Matrix *m = 00307 new PBQP::Matrix(allowed1.size() + 1, allowed2.size() + 1, 0); 00308 00309 // Reset costs to zero. 00310 m->reset(0); 00311 00312 // Assume the matrix is zero till proven otherwise. Zero matrices will be 00313 // optimized away as in the interference case. 00314 bool isZeroMatrix = true; 00315 00316 // Row index. Starts at 1, since the 0th row is for the spill option, which 00317 // is always zero. 00318 unsigned ri = 1; 00319 00320 // Iterate over the allowed sets, insert coalescing benefits where 00321 // appropriate. 00322 for (RegContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end(); 00323 a1Itr != a1End; ++a1Itr) { 00324 00325 // Column index, starts at 1 as for row index. 00326 unsigned ci = 1; 00327 unsigned reg1 = *a1Itr; 00328 00329 for (RegContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end(); 00330 a2Itr != a2End; ++a2Itr) { 00331 00332 // If the row and column represent the same register insert a beneficial 00333 // cost to preference this allocation - it would allow us to eliminate a 00334 // move instruction. 00335 if (reg1 == *a2Itr) { 00336 (*m)[ri][ci] = -cBenefit; 00337 isZeroMatrix = false; 00338 } 00339 00340 ++ci; 00341 } 00342 00343 ++ri; 00344 } 00345 00346 // If this turns out to be a zero matrix... 00347 if (isZeroMatrix) { 00348 // ...free it and return null. 00349 delete m; 00350 return 0; 00351 } 00352 00353 return m; 00354 } 00355 00356 PBQPRegAlloc::CoalesceMap PBQPRegAlloc::findCoalesces() { 00357 00358 typedef MachineFunction::const_iterator MFIterator; 00359 typedef MachineBasicBlock::const_iterator MBBIterator; 00360 typedef LiveInterval::const_vni_iterator VNIIterator; 00361 00362 CoalesceMap coalescesFound; 00363 00364 // To find coalesces we need to iterate over the function looking for 00365 // copy instructions. 00366 for (MFIterator bbItr = mf->begin(), bbEnd = mf->end(); 00367 bbItr != bbEnd; ++bbItr) { 00368 00369 const MachineBasicBlock *mbb = &*bbItr; 00370 00371 for (MBBIterator iItr = mbb->begin(), iEnd = mbb->end(); 00372 iItr != iEnd; ++iItr) { 00373 00374 const MachineInstr *instr = &*iItr; 00375 unsigned srcReg, dstReg, srcSubReg, dstSubReg; 00376 00377 // If this isn't a copy then continue to the next instruction. 00378 if (!tii->isMoveInstr(*instr, srcReg, dstReg, srcSubReg, dstSubReg)) 00379 continue; 00380 00381 // If the registers are already the same our job is nice and easy. 00382 if (dstReg == srcReg) 00383 continue; 00384 00385 bool srcRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(srcReg), 00386 dstRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(dstReg); 00387 00388 // If both registers are physical then we can't coalesce. 00389 if (srcRegIsPhysical && dstRegIsPhysical) 00390 continue; 00391 00392 // If it's a copy that includes a virtual register but the source and 00393 // destination classes differ then we can't coalesce, so continue with 00394 // the next instruction. 00395 const TargetRegisterClass *srcRegClass = srcRegIsPhysical ? 00396 tri->getPhysicalRegisterRegClass(srcReg) : mri->getRegClass(srcReg); 00397 00398 const TargetRegisterClass *dstRegClass = dstRegIsPhysical ? 00399 tri->getPhysicalRegisterRegClass(dstReg) : mri->getRegClass(dstReg); 00400 00401 if (srcRegClass != dstRegClass) 00402 continue; 00403 00404 // We also need any physical regs to be allocable, coalescing with 00405 // a non-allocable register is invalid. 00406 if (srcRegIsPhysical) { 00407 if (std::find(srcRegClass->allocation_order_begin(*mf), 00408 srcRegClass->allocation_order_end(*mf), srcReg) == 00409 srcRegClass->allocation_order_end(*mf)) 00410 continue; 00411 } 00412 00413 if (dstRegIsPhysical) { 00414 if (std::find(dstRegClass->allocation_order_begin(*mf), 00415 dstRegClass->allocation_order_end(*mf), dstReg) == 00416 dstRegClass->allocation_order_end(*mf)) 00417 continue; 00418 } 00419 00420 // If we've made it here we have a copy with compatible register classes. 00421 // We can probably coalesce, but we need to consider overlap. 00422 const LiveInterval *srcLI = &lis->getInterval(srcReg), 00423 *dstLI = &lis->getInterval(dstReg); 00424 00425 if (srcLI->overlaps(*dstLI)) { 00426 // Even in the case of an overlap we might still be able to coalesce, 00427 // but we need to make sure that no definition of either range occurs 00428 // while the other range is live. 00429 00430 // Otherwise start by assuming we're ok. 00431 bool badDef = false; 00432 00433 // Test all defs of the source range. 00434 for (VNIIterator 00435 vniItr = srcLI->vni_begin(), vniEnd = srcLI->vni_end(); 00436 vniItr != vniEnd; ++vniItr) { 00437 00438 // If we find a def that kills the coalescing opportunity then 00439 // record it and break from the loop. 00440 if (dstLI->liveAt((*vniItr)->def)) { 00441 badDef = true; 00442 break; 00443 } 00444 } 00445 00446 // If we have a bad def give up, continue to the next instruction. 00447 if (badDef) 00448 continue; 00449 00450 // Otherwise test definitions of the destination range. 00451 for (VNIIterator 00452 vniItr = dstLI->vni_begin(), vniEnd = dstLI->vni_end(); 00453 vniItr != vniEnd; ++vniItr) { 00454 00455 // We want to make sure we skip the copy instruction itself. 00456 if ((*vniItr)->getCopy() == instr) 00457 continue; 00458 00459 if (srcLI->liveAt((*vniItr)->def)) { 00460 badDef = true; 00461 break; 00462 } 00463 } 00464 00465 // As before a bad def we give up and continue to the next instr. 00466 if (badDef) 00467 continue; 00468 } 00469 00470 // If we make it to here then either the ranges didn't overlap, or they 00471 // did, but none of their definitions would prevent us from coalescing. 00472 // We're good to go with the coalesce. 00473 00474 float cBenefit = powf(10.0f, loopInfo->getLoopDepth(mbb)) / 5.0; 00475 00476 coalescesFound[RegPair(srcReg, dstReg)] = cBenefit; 00477 coalescesFound[RegPair(dstReg, srcReg)] = cBenefit; 00478 } 00479 00480 } 00481 00482 return coalescesFound; 00483 } 00484 00485 void PBQPRegAlloc::findVRegIntervalsToAlloc() { 00486 00487 // Iterate over all live ranges. 00488 for (LiveIntervals::iterator itr = lis->begin(), end = lis->end(); 00489 itr != end; ++itr) { 00490 00491 // Ignore physical ones. 00492 if (TargetRegisterInfo::isPhysicalRegister(itr->first)) 00493 continue; 00494 00495 LiveInterval *li = itr->second; 00496 00497 // If this live interval is non-empty we will use pbqp to allocate it. 00498 // Empty intervals we allocate in a simple post-processing stage in 00499 // finalizeAlloc. 00500 if (!li->empty()) { 00501 vregIntervalsToAlloc.insert(li); 00502 } 00503 else { 00504 emptyVRegIntervals.insert(li); 00505 } 00506 } 00507 } 00508 00509 PBQP::SimpleGraph PBQPRegAlloc::constructPBQPProblem() { 00510 00511 typedef std::vector<const LiveInterval*> LIVector; 00512 typedef std::vector<unsigned> RegVector; 00513 typedef std::vector<PBQP::SimpleGraph::NodeIterator> NodeVector; 00514 00515 // This will store the physical intervals for easy reference. 00516 LIVector physIntervals; 00517 00518 // Start by clearing the old node <-> live interval mappings & allowed sets 00519 li2Node.clear(); 00520 node2LI.clear(); 00521 allowedSets.clear(); 00522 00523 // Populate physIntervals, update preg use: 00524 for (LiveIntervals::iterator itr = lis->begin(), end = lis->end(); 00525 itr != end; ++itr) { 00526 00527 if (TargetRegisterInfo::isPhysicalRegister(itr->first)) { 00528 physIntervals.push_back(itr->second); 00529 mri->setPhysRegUsed(itr->second->reg); 00530 } 00531 } 00532 00533 // Iterate over vreg intervals, construct live interval <-> node number 00534 // mappings. 00535 for (LiveIntervalSet::const_iterator 00536 itr = vregIntervalsToAlloc.begin(), end = vregIntervalsToAlloc.end(); 00537 itr != end; ++itr) { 00538 const LiveInterval *li = *itr; 00539 00540 li2Node[li] = node2LI.size(); 00541 node2LI.push_back(li); 00542 } 00543 00544 // Get the set of potential coalesces. 00545 CoalesceMap coalesces; 00546 00547 if (pbqpCoalescing) { 00548 coalesces = findCoalesces(); 00549 } 00550 00551 // Construct a PBQP solver for this problem 00552 PBQP::SimpleGraph problem; 00553 NodeVector problemNodes(vregIntervalsToAlloc.size()); 00554 00555 // Resize allowedSets container appropriately. 00556 allowedSets.resize(vregIntervalsToAlloc.size()); 00557 00558 // Iterate over virtual register intervals to compute allowed sets... 00559 for (unsigned node = 0; node < node2LI.size(); ++node) { 00560 00561 // Grab pointers to the interval and its register class. 00562 const LiveInterval *li = node2LI[node]; 00563 const TargetRegisterClass *liRC = mri->getRegClass(li->reg); 00564 00565 // Start by assuming all allocable registers in the class are allowed... 00566 RegVector liAllowed(liRC->allocation_order_begin(*mf), 00567 liRC->allocation_order_end(*mf)); 00568 00569 // Eliminate the physical registers which overlap with this range, along 00570 // with all their aliases. 00571 for (LIVector::iterator pItr = physIntervals.begin(), 00572 pEnd = physIntervals.end(); pItr != pEnd; ++pItr) { 00573 00574 if (!li->overlaps(**pItr)) 00575 continue; 00576 00577 unsigned pReg = (*pItr)->reg; 00578 00579 // If we get here then the live intervals overlap, but we're still ok 00580 // if they're coalescable. 00581 if (coalesces.find(RegPair(li->reg, pReg)) != coalesces.end()) 00582 continue; 00583 00584 // If we get here then we have a genuine exclusion. 00585 00586 // Remove the overlapping reg... 00587 RegVector::iterator eraseItr = 00588 std::find(liAllowed.begin(), liAllowed.end(), pReg); 00589 00590 if (eraseItr != liAllowed.end()) 00591 liAllowed.erase(eraseItr); 00592 00593 const unsigned *aliasItr = tri->getAliasSet(pReg); 00594 00595 if (aliasItr != 0) { 00596 // ...and its aliases. 00597 for (; *aliasItr != 0; ++aliasItr) { 00598 RegVector::iterator eraseItr = 00599 std::find(liAllowed.begin(), liAllowed.end(), *aliasItr); 00600 00601 if (eraseItr != liAllowed.end()) { 00602 liAllowed.erase(eraseItr); 00603 } 00604 } 00605 } 00606 } 00607 00608 // Copy the allowed set into a member vector for use when constructing cost 00609 // vectors & matrices, and mapping PBQP solutions back to assignments. 00610 allowedSets[node] = AllowedSet(liAllowed.begin(), liAllowed.end()); 00611 00612 // Set the spill cost to the interval weight, or epsilon if the 00613 // interval weight is zero 00614 PBQP::PBQPNum spillCost = (li->weight != 0.0) ? 00615 li->weight : std::numeric_limits<PBQP::PBQPNum>::min(); 00616 00617 // Build a cost vector for this interval. 00618 problemNodes[node] = 00619 problem.addNode( 00620 buildCostVector(li->reg, allowedSets[node], coalesces, spillCost)); 00621 00622 } 00623 00624 00625 // Now add the cost matrices... 00626 for (unsigned node1 = 0; node1 < node2LI.size(); ++node1) { 00627 const LiveInterval *li = node2LI[node1]; 00628 00629 // Test for live range overlaps and insert interference matrices. 00630 for (unsigned node2 = node1 + 1; node2 < node2LI.size(); ++node2) { 00631 const LiveInterval *li2 = node2LI[node2]; 00632 00633 CoalesceMap::const_iterator cmItr = 00634 coalesces.find(RegPair(li->reg, li2->reg)); 00635 00636 PBQP::Matrix *m = 0; 00637 00638 if (cmItr != coalesces.end()) { 00639 m = buildCoalescingMatrix(allowedSets[node1], allowedSets[node2], 00640 cmItr->second); 00641 } 00642 else if (li->overlaps(*li2)) { 00643 m = buildInterferenceMatrix(allowedSets[node1], allowedSets[node2]); 00644 } 00645 00646 if (m != 0) { 00647 problem.addEdge(problemNodes[node1], 00648 problemNodes[node2], 00649 *m); 00650 00651 delete m; 00652 } 00653 } 00654 } 00655 00656 problem.assignNodeIDs(); 00657 00658 assert(problem.getNumNodes() == allowedSets.size()); 00659 for (unsigned i = 0; i < allowedSets.size(); ++i) { 00660 assert(problem.getNodeItr(i) == problemNodes[i]); 00661 } 00662 /* 00663 std::cerr << "Allocating for " << problem.getNumNodes() << " nodes, " 00664 << problem.getNumEdges() << " edges.\n"; 00665 00666 problem.printDot(std::cerr); 00667 */ 00668 // We're done, PBQP problem constructed - return it. 00669 return problem; 00670 } 00671 00672 void PBQPRegAlloc::addStackInterval(const LiveInterval *spilled, 00673 MachineRegisterInfo* mri) { 00674 int stackSlot = vrm->getStackSlot(spilled->reg); 00675 00676 if (stackSlot == VirtRegMap::NO_STACK_SLOT) 00677 return; 00678 00679 const TargetRegisterClass *RC = mri->getRegClass(spilled->reg); 00680 LiveInterval &stackInterval = lss->getOrCreateInterval(stackSlot, RC); 00681 00682 VNInfo *vni; 00683 if (stackInterval.getNumValNums() != 0) 00684 vni = stackInterval.getValNumInfo(0); 00685 else 00686 vni = stackInterval.getNextValue(0, 0, false, lss->getVNInfoAllocator()); 00687 00688 LiveInterval &rhsInterval = lis->getInterval(spilled->reg); 00689 stackInterval.MergeRangesInAsValue(rhsInterval, vni); 00690 } 00691 00692 bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) { 00693 00694 static unsigned round = 0; 00695 (void) round; 00696 00697 // Set to true if we have any spills 00698 bool anotherRoundNeeded = false; 00699 00700 // Clear the existing allocation. 00701 vrm->clearAllVirt(); 00702 00703 // Iterate over the nodes mapping the PBQP solution to a register assignment. 00704 for (unsigned node = 0; node < node2LI.size(); ++node) { 00705 unsigned virtReg = node2LI[node]->reg, 00706 allocSelection = solution.getSelection(node); 00707 00708 00709 // If the PBQP solution is non-zero it's a physical register... 00710 if (allocSelection != 0) { 00711 // Get the physical reg, subtracting 1 to account for the spill option. 00712 unsigned physReg = allowedSets[node][allocSelection - 1]; 00713 00714 DEBUG(errs() << "VREG " << virtReg << " -> " 00715 << tri->getName(physReg) << "\n"); 00716 00717 assert(physReg != 0); 00718 00719 // Add to the virt reg map and update the used phys regs. 00720 vrm->assignVirt2Phys(virtReg, physReg); 00721 } 00722 // ...Otherwise it's a spill. 00723 else { 00724 00725 // Make sure we ignore this virtual reg on the next round 00726 // of allocation 00727 vregIntervalsToAlloc.erase(&lis->getInterval(virtReg)); 00728 00729 // Insert spill ranges for this live range 00730 const LiveInterval *spillInterval = node2LI[node]; 00731 double oldSpillWeight = spillInterval->weight; 00732 SmallVector<LiveInterval*, 8> spillIs; 00733 std::vector<LiveInterval*> newSpills = 00734 lis->addIntervalsForSpills(*spillInterval, spillIs, loopInfo, *vrm); 00735 addStackInterval(spillInterval, mri); 00736 00737 (void) oldSpillWeight; 00738 DEBUG(errs() << "VREG " << virtReg << " -> SPILLED (Cost: " 00739 << oldSpillWeight << ", New vregs: "); 00740 00741 // Copy any newly inserted live intervals into the list of regs to 00742 // allocate. 00743 for (std::vector<LiveInterval*>::const_iterator 00744 itr = newSpills.begin(), end = newSpills.end(); 00745 itr != end; ++itr) { 00746 00747 assert(!(*itr)->empty() && "Empty spill range."); 00748 00749 DEBUG(errs() << (*itr)->reg << " "); 00750 00751 vregIntervalsToAlloc.insert(*itr); 00752 } 00753 00754 DEBUG(errs() << ")\n"); 00755 00756 // We need another round if spill intervals were added. 00757 anotherRoundNeeded |= !newSpills.empty(); 00758 } 00759 } 00760 00761 return !anotherRoundNeeded; 00762 } 00763 00764 void PBQPRegAlloc::finalizeAlloc() const { 00765 typedef LiveIntervals::iterator LIIterator; 00766 typedef LiveInterval::Ranges::const_iterator LRIterator; 00767 00768 // First allocate registers for the empty intervals. 00769 for (LiveIntervalSet::const_iterator 00770 itr = emptyVRegIntervals.begin(), end = emptyVRegIntervals.end(); 00771 itr != end; ++itr) { 00772 LiveInterval *li = *itr; 00773 00774 unsigned physReg = vrm->getRegAllocPref(li->reg); 00775 00776 if (physReg == 0) { 00777 const TargetRegisterClass *liRC = mri->getRegClass(li->reg); 00778 physReg = *liRC->allocation_order_begin(*mf); 00779 } 00780 00781 vrm->assignVirt2Phys(li->reg, physReg); 00782 } 00783 00784 // Finally iterate over the basic blocks to compute and set the live-in sets. 00785 SmallVector<MachineBasicBlock*, 8> liveInMBBs; 00786 MachineBasicBlock *entryMBB = &*mf->begin(); 00787 00788 for (LIIterator liItr = lis->begin(), liEnd = lis->end(); 00789 liItr != liEnd; ++liItr) { 00790 00791 const LiveInterval *li = liItr->second; 00792 unsigned reg = 0; 00793 00794 // Get the physical register for this interval 00795 if (TargetRegisterInfo::isPhysicalRegister(li->reg)) { 00796 reg = li->reg; 00797 } 00798 else if (vrm->isAssignedReg(li->reg)) { 00799 reg = vrm->getPhys(li->reg); 00800 } 00801 else { 00802 // Ranges which are assigned a stack slot only are ignored. 00803 continue; 00804 } 00805 00806 if (reg == 0) { 00807 // Filter out zero regs - they're for intervals that were spilled. 00808 continue; 00809 } 00810 00811 // Iterate over the ranges of the current interval... 00812 for (LRIterator lrItr = li->begin(), lrEnd = li->end(); 00813 lrItr != lrEnd; ++lrItr) { 00814 00815 // Find the set of basic blocks which this range is live into... 00816 if (lis->findLiveInMBBs(lrItr->start, lrItr->end, liveInMBBs)) { 00817 // And add the physreg for this interval to their live-in sets. 00818 for (unsigned i = 0; i < liveInMBBs.size(); ++i) { 00819 if (liveInMBBs[i] != entryMBB) { 00820 if (!liveInMBBs[i]->isLiveIn(reg)) { 00821 liveInMBBs[i]->addLiveIn(reg); 00822 } 00823 } 00824 } 00825 liveInMBBs.clear(); 00826 } 00827 } 00828 } 00829 00830 } 00831 00832 bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) { 00833 00834 mf = &MF; 00835 tm = &mf->getTarget(); 00836 tri = tm->getRegisterInfo(); 00837 tii = tm->getInstrInfo(); 00838 mri = &mf->getRegInfo(); 00839 00840 lis = &getAnalysis<LiveIntervals>(); 00841 lss = &getAnalysis<LiveStacks>(); 00842 loopInfo = &getAnalysis<MachineLoopInfo>(); 00843 00844 vrm = &getAnalysis<VirtRegMap>(); 00845 00846 DEBUG(errs() << "PBQP2 Register Allocating for " << mf->getFunction()->getName() << "\n"); 00847 00848 // Allocator main loop: 00849 // 00850 // * Map current regalloc problem to a PBQP problem 00851 // * Solve the PBQP problem 00852 // * Map the solution back to a register allocation 00853 // * Spill if necessary 00854 // 00855 // This process is continued till no more spills are generated. 00856 00857 // Find the vreg intervals in need of allocation. 00858 findVRegIntervalsToAlloc(); 00859 00860 // If there aren't any then we're done here. 00861 if (vregIntervalsToAlloc.empty() && emptyVRegIntervals.empty()) 00862 return true; 00863 00864 // If there are non-empty intervals allocate them using pbqp. 00865 if (!vregIntervalsToAlloc.empty()) { 00866 00867 bool pbqpAllocComplete = false; 00868 unsigned round = 0; 00869 00870 while (!pbqpAllocComplete) { 00871 DEBUG(errs() << " PBQP Regalloc round " << round << ":\n"); 00872 00873 PBQP::SimpleGraph problem = constructPBQPProblem(); 00874 PBQP::HeuristicSolver<PBQP::Heuristics::Briggs> solver; 00875 problem.assignNodeIDs(); 00876 PBQP::Solution solution = solver.solve(problem); 00877 00878 pbqpAllocComplete = mapPBQPToRegAlloc(solution); 00879 00880 ++round; 00881 } 00882 } 00883 00884 // Finalise allocation, allocate empty ranges. 00885 finalizeAlloc(); 00886 00887 vregIntervalsToAlloc.clear(); 00888 emptyVRegIntervals.clear(); 00889 li2Node.clear(); 00890 node2LI.clear(); 00891 allowedSets.clear(); 00892 00893 DEBUG(errs() << "Post alloc VirtRegMap:\n" << *vrm << "\n"); 00894 00895 // Run rewriter 00896 std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter()); 00897 00898 rewriter->runOnMachineFunction(*mf, *vrm, lis); 00899 00900 return true; 00901 } 00902 00903 FunctionPass* llvm::createPBQPRegisterAllocator() { 00904 return new PBQPRegAlloc(); 00905 } 00906 00907 00908 #undef DEBUG_TYPE