RegAllocPBQP.cpp revision 193323
1//===------ RegAllocPBQP.cpp ---- PBQP Register Allocator -------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file contains a Partitioned Boolean Quadratic Programming (PBQP) based 11// register allocator for LLVM. This allocator works by constructing a PBQP 12// problem representing the register allocation problem under consideration, 13// solving this using a PBQP solver, and mapping the solution back to a 14// register assignment. If any variables are selected for spilling then spill 15// code is inserted and the process repeated. 16// 17// The PBQP solver (pbqp.c) provided for this allocator uses a heuristic tuned 18// for register allocation. For more information on PBQP for register 19// allocation, see the following papers: 20// 21// (1) Hames, L. and Scholz, B. 2006. Nearly optimal register allocation with 22// PBQP. In Proceedings of the 7th Joint Modular Languages Conference 23// (JMLC'06). LNCS, vol. 4228. Springer, New York, NY, USA. 346-361. 24// 25// (2) Scholz, B., Eckstein, E. 2002. Register allocation for irregular 26// architectures. In Proceedings of the Joint Conference on Languages, 27// Compilers and Tools for Embedded Systems (LCTES'02), ACM Press, New York, 28// NY, USA, 139-148. 29// 30//===----------------------------------------------------------------------===// 31 32#define DEBUG_TYPE "regalloc" 33 34#include "PBQP.h" 35#include "VirtRegMap.h" 36#include "VirtRegRewriter.h" 37#include "llvm/CodeGen/LiveIntervalAnalysis.h" 38#include "llvm/CodeGen/LiveStackAnalysis.h" 39#include "llvm/CodeGen/MachineFunctionPass.h" 40#include "llvm/CodeGen/MachineLoopInfo.h" 41#include "llvm/CodeGen/MachineRegisterInfo.h" 42#include "llvm/CodeGen/RegAllocRegistry.h" 43#include "llvm/CodeGen/RegisterCoalescer.h" 44#include "llvm/Support/Debug.h" 45#include "llvm/Target/TargetInstrInfo.h" 46#include "llvm/Target/TargetMachine.h" 47#include <limits> 48#include <map> 49#include <memory> 50#include <set> 51#include <vector> 52 53using namespace llvm; 54 55static RegisterRegAlloc 56registerPBQPRepAlloc("pbqp", "PBQP register allocator", 57 createPBQPRegisterAllocator); 58 59namespace { 60 61 //! 62 //! PBQP based allocators solve the register allocation problem by mapping 63 //! register allocation problems to Partitioned Boolean Quadratic 64 //! Programming problems. 65 class VISIBILITY_HIDDEN PBQPRegAlloc : public MachineFunctionPass { 66 public: 67 68 static char ID; 69 70 //! Construct a PBQP register allocator. 71 PBQPRegAlloc() : MachineFunctionPass((intptr_t)&ID) {} 72 73 //! Return the pass name. 74 virtual const char* getPassName() const throw() { 75 return "PBQP Register Allocator"; 76 } 77 78 //! PBQP analysis usage. 79 virtual void getAnalysisUsage(AnalysisUsage &au) const { 80 au.addRequired<LiveIntervals>(); 81 au.addRequiredTransitive<RegisterCoalescer>(); 82 au.addRequired<LiveStacks>(); 83 au.addPreserved<LiveStacks>(); 84 au.addRequired<MachineLoopInfo>(); 85 au.addPreserved<MachineLoopInfo>(); 86 au.addRequired<VirtRegMap>(); 87 MachineFunctionPass::getAnalysisUsage(au); 88 } 89 90 //! Perform register allocation 91 virtual bool runOnMachineFunction(MachineFunction &MF); 92 93 private: 94 typedef std::map<const LiveInterval*, unsigned> LI2NodeMap; 95 typedef std::vector<const LiveInterval*> Node2LIMap; 96 typedef std::vector<unsigned> AllowedSet; 97 typedef std::vector<AllowedSet> AllowedSetMap; 98 typedef std::set<unsigned> RegSet; 99 typedef std::pair<unsigned, unsigned> RegPair; 100 typedef std::map<RegPair, PBQPNum> CoalesceMap; 101 102 typedef std::set<LiveInterval*> LiveIntervalSet; 103 104 MachineFunction *mf; 105 const TargetMachine *tm; 106 const TargetRegisterInfo *tri; 107 const TargetInstrInfo *tii; 108 const MachineLoopInfo *loopInfo; 109 MachineRegisterInfo *mri; 110 111 LiveIntervals *lis; 112 LiveStacks *lss; 113 VirtRegMap *vrm; 114 115 LI2NodeMap li2Node; 116 Node2LIMap node2LI; 117 AllowedSetMap allowedSets; 118 LiveIntervalSet vregIntervalsToAlloc, 119 emptyVRegIntervals; 120 121 122 //! Builds a PBQP cost vector. 123 template <typename RegContainer> 124 PBQPVector* buildCostVector(unsigned vReg, 125 const RegContainer &allowed, 126 const CoalesceMap &cealesces, 127 PBQPNum spillCost) const; 128 129 //! \brief Builds a PBQP interference matrix. 130 //! 131 //! @return Either a pointer to a non-zero PBQP matrix representing the 132 //! allocation option costs, or a null pointer for a zero matrix. 133 //! 134 //! Expects allowed sets for two interfering LiveIntervals. These allowed 135 //! sets should contain only allocable registers from the LiveInterval's 136 //! register class, with any interfering pre-colored registers removed. 137 template <typename RegContainer> 138 PBQPMatrix* buildInterferenceMatrix(const RegContainer &allowed1, 139 const RegContainer &allowed2) const; 140 141 //! 142 //! Expects allowed sets for two potentially coalescable LiveIntervals, 143 //! and an estimated benefit due to coalescing. The allowed sets should 144 //! contain only allocable registers from the LiveInterval's register 145 //! classes, with any interfering pre-colored registers removed. 146 template <typename RegContainer> 147 PBQPMatrix* buildCoalescingMatrix(const RegContainer &allowed1, 148 const RegContainer &allowed2, 149 PBQPNum cBenefit) const; 150 151 //! \brief Finds coalescing opportunities and returns them as a map. 152 //! 153 //! Any entries in the map are guaranteed coalescable, even if their 154 //! corresponding live intervals overlap. 155 CoalesceMap findCoalesces(); 156 157 //! \brief Finds the initial set of vreg intervals to allocate. 158 void findVRegIntervalsToAlloc(); 159 160 //! \brief Constructs a PBQP problem representation of the register 161 //! allocation problem for this function. 162 //! 163 //! @return a PBQP solver object for the register allocation problem. 164 pbqp* constructPBQPProblem(); 165 166 //! \brief Adds a stack interval if the given live interval has been 167 //! spilled. Used to support stack slot coloring. 168 void addStackInterval(const LiveInterval *spilled,MachineRegisterInfo* mri); 169 170 //! \brief Given a solved PBQP problem maps this solution back to a register 171 //! assignment. 172 bool mapPBQPToRegAlloc(pbqp *problem); 173 174 //! \brief Postprocessing before final spilling. Sets basic block "live in" 175 //! variables. 176 void finalizeAlloc() const; 177 178 }; 179 180 char PBQPRegAlloc::ID = 0; 181} 182 183 184template <typename RegContainer> 185PBQPVector* PBQPRegAlloc::buildCostVector(unsigned vReg, 186 const RegContainer &allowed, 187 const CoalesceMap &coalesces, 188 PBQPNum spillCost) const { 189 190 typedef typename RegContainer::const_iterator AllowedItr; 191 192 // Allocate vector. Additional element (0th) used for spill option 193 PBQPVector *v = new PBQPVector(allowed.size() + 1); 194 195 (*v)[0] = spillCost; 196 197 // Iterate over the allowed registers inserting coalesce benefits if there 198 // are any. 199 unsigned ai = 0; 200 for (AllowedItr itr = allowed.begin(), end = allowed.end(); 201 itr != end; ++itr, ++ai) { 202 203 unsigned pReg = *itr; 204 205 CoalesceMap::const_iterator cmItr = 206 coalesces.find(RegPair(vReg, pReg)); 207 208 // No coalesce - on to the next preg. 209 if (cmItr == coalesces.end()) 210 continue; 211 212 // We have a coalesce - insert the benefit. 213 (*v)[ai + 1] = -cmItr->second; 214 } 215 216 return v; 217} 218 219template <typename RegContainer> 220PBQPMatrix* PBQPRegAlloc::buildInterferenceMatrix( 221 const RegContainer &allowed1, const RegContainer &allowed2) const { 222 223 typedef typename RegContainer::const_iterator RegContainerIterator; 224 225 // Construct a PBQP matrix representing the cost of allocation options. The 226 // rows and columns correspond to the allocation options for the two live 227 // intervals. Elements will be infinite where corresponding registers alias, 228 // since we cannot allocate aliasing registers to interfering live intervals. 229 // All other elements (non-aliasing combinations) will have zero cost. Note 230 // that the spill option (element 0,0) has zero cost, since we can allocate 231 // both intervals to memory safely (the cost for each individual allocation 232 // to memory is accounted for by the cost vectors for each live interval). 233 PBQPMatrix *m = new PBQPMatrix(allowed1.size() + 1, allowed2.size() + 1); 234 235 // Assume this is a zero matrix until proven otherwise. Zero matrices occur 236 // between interfering live ranges with non-overlapping register sets (e.g. 237 // non-overlapping reg classes, or disjoint sets of allowed regs within the 238 // same class). The term "overlapping" is used advisedly: sets which do not 239 // intersect, but contain registers which alias, will have non-zero matrices. 240 // We optimize zero matrices away to improve solver speed. 241 bool isZeroMatrix = true; 242 243 244 // Row index. Starts at 1, since the 0th row is for the spill option, which 245 // is always zero. 246 unsigned ri = 1; 247 248 // Iterate over allowed sets, insert infinities where required. 249 for (RegContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end(); 250 a1Itr != a1End; ++a1Itr) { 251 252 // Column index, starts at 1 as for row index. 253 unsigned ci = 1; 254 unsigned reg1 = *a1Itr; 255 256 for (RegContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end(); 257 a2Itr != a2End; ++a2Itr) { 258 259 unsigned reg2 = *a2Itr; 260 261 // If the row/column regs are identical or alias insert an infinity. 262 if ((reg1 == reg2) || tri->areAliases(reg1, reg2)) { 263 (*m)[ri][ci] = std::numeric_limits<PBQPNum>::infinity(); 264 isZeroMatrix = false; 265 } 266 267 ++ci; 268 } 269 270 ++ri; 271 } 272 273 // If this turns out to be a zero matrix... 274 if (isZeroMatrix) { 275 // free it and return null. 276 delete m; 277 return 0; 278 } 279 280 // ...otherwise return the cost matrix. 281 return m; 282} 283 284template <typename RegContainer> 285PBQPMatrix* PBQPRegAlloc::buildCoalescingMatrix( 286 const RegContainer &allowed1, const RegContainer &allowed2, 287 PBQPNum cBenefit) const { 288 289 typedef typename RegContainer::const_iterator RegContainerIterator; 290 291 // Construct a PBQP Matrix representing the benefits of coalescing. As with 292 // interference matrices the rows and columns represent allowed registers 293 // for the LiveIntervals which are (potentially) to be coalesced. The amount 294 // -cBenefit will be placed in any element representing the same register 295 // for both intervals. 296 PBQPMatrix *m = new PBQPMatrix(allowed1.size() + 1, allowed2.size() + 1); 297 298 // Reset costs to zero. 299 m->reset(0); 300 301 // Assume the matrix is zero till proven otherwise. Zero matrices will be 302 // optimized away as in the interference case. 303 bool isZeroMatrix = true; 304 305 // Row index. Starts at 1, since the 0th row is for the spill option, which 306 // is always zero. 307 unsigned ri = 1; 308 309 // Iterate over the allowed sets, insert coalescing benefits where 310 // appropriate. 311 for (RegContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end(); 312 a1Itr != a1End; ++a1Itr) { 313 314 // Column index, starts at 1 as for row index. 315 unsigned ci = 1; 316 unsigned reg1 = *a1Itr; 317 318 for (RegContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end(); 319 a2Itr != a2End; ++a2Itr) { 320 321 // If the row and column represent the same register insert a beneficial 322 // cost to preference this allocation - it would allow us to eliminate a 323 // move instruction. 324 if (reg1 == *a2Itr) { 325 (*m)[ri][ci] = -cBenefit; 326 isZeroMatrix = false; 327 } 328 329 ++ci; 330 } 331 332 ++ri; 333 } 334 335 // If this turns out to be a zero matrix... 336 if (isZeroMatrix) { 337 // ...free it and return null. 338 delete m; 339 return 0; 340 } 341 342 return m; 343} 344 345PBQPRegAlloc::CoalesceMap PBQPRegAlloc::findCoalesces() { 346 347 typedef MachineFunction::const_iterator MFIterator; 348 typedef MachineBasicBlock::const_iterator MBBIterator; 349 typedef LiveInterval::const_vni_iterator VNIIterator; 350 351 CoalesceMap coalescesFound; 352 353 // To find coalesces we need to iterate over the function looking for 354 // copy instructions. 355 for (MFIterator bbItr = mf->begin(), bbEnd = mf->end(); 356 bbItr != bbEnd; ++bbItr) { 357 358 const MachineBasicBlock *mbb = &*bbItr; 359 360 for (MBBIterator iItr = mbb->begin(), iEnd = mbb->end(); 361 iItr != iEnd; ++iItr) { 362 363 const MachineInstr *instr = &*iItr; 364 unsigned srcReg, dstReg, srcSubReg, dstSubReg; 365 366 // If this isn't a copy then continue to the next instruction. 367 if (!tii->isMoveInstr(*instr, srcReg, dstReg, srcSubReg, dstSubReg)) 368 continue; 369 370 // If the registers are already the same our job is nice and easy. 371 if (dstReg == srcReg) 372 continue; 373 374 bool srcRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(srcReg), 375 dstRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(dstReg); 376 377 // If both registers are physical then we can't coalesce. 378 if (srcRegIsPhysical && dstRegIsPhysical) 379 continue; 380 381 // If it's a copy that includes a virtual register but the source and 382 // destination classes differ then we can't coalesce, so continue with 383 // the next instruction. 384 const TargetRegisterClass *srcRegClass = srcRegIsPhysical ? 385 tri->getPhysicalRegisterRegClass(srcReg) : mri->getRegClass(srcReg); 386 387 const TargetRegisterClass *dstRegClass = dstRegIsPhysical ? 388 tri->getPhysicalRegisterRegClass(dstReg) : mri->getRegClass(dstReg); 389 390 if (srcRegClass != dstRegClass) 391 continue; 392 393 // We also need any physical regs to be allocable, coalescing with 394 // a non-allocable register is invalid. 395 if (srcRegIsPhysical) { 396 if (std::find(srcRegClass->allocation_order_begin(*mf), 397 srcRegClass->allocation_order_end(*mf), srcReg) == 398 srcRegClass->allocation_order_end(*mf)) 399 continue; 400 } 401 402 if (dstRegIsPhysical) { 403 if (std::find(dstRegClass->allocation_order_begin(*mf), 404 dstRegClass->allocation_order_end(*mf), dstReg) == 405 dstRegClass->allocation_order_end(*mf)) 406 continue; 407 } 408 409 // If we've made it here we have a copy with compatible register classes. 410 // We can probably coalesce, but we need to consider overlap. 411 const LiveInterval *srcLI = &lis->getInterval(srcReg), 412 *dstLI = &lis->getInterval(dstReg); 413 414 if (srcLI->overlaps(*dstLI)) { 415 // Even in the case of an overlap we might still be able to coalesce, 416 // but we need to make sure that no definition of either range occurs 417 // while the other range is live. 418 419 // Otherwise start by assuming we're ok. 420 bool badDef = false; 421 422 // Test all defs of the source range. 423 for (VNIIterator 424 vniItr = srcLI->vni_begin(), vniEnd = srcLI->vni_end(); 425 vniItr != vniEnd; ++vniItr) { 426 427 // If we find a def that kills the coalescing opportunity then 428 // record it and break from the loop. 429 if (dstLI->liveAt((*vniItr)->def)) { 430 badDef = true; 431 break; 432 } 433 } 434 435 // If we have a bad def give up, continue to the next instruction. 436 if (badDef) 437 continue; 438 439 // Otherwise test definitions of the destination range. 440 for (VNIIterator 441 vniItr = dstLI->vni_begin(), vniEnd = dstLI->vni_end(); 442 vniItr != vniEnd; ++vniItr) { 443 444 // We want to make sure we skip the copy instruction itself. 445 if ((*vniItr)->copy == instr) 446 continue; 447 448 if (srcLI->liveAt((*vniItr)->def)) { 449 badDef = true; 450 break; 451 } 452 } 453 454 // As before a bad def we give up and continue to the next instr. 455 if (badDef) 456 continue; 457 } 458 459 // If we make it to here then either the ranges didn't overlap, or they 460 // did, but none of their definitions would prevent us from coalescing. 461 // We're good to go with the coalesce. 462 463 float cBenefit = powf(10.0f, loopInfo->getLoopDepth(mbb)) / 5.0; 464 465 coalescesFound[RegPair(srcReg, dstReg)] = cBenefit; 466 coalescesFound[RegPair(dstReg, srcReg)] = cBenefit; 467 } 468 469 } 470 471 return coalescesFound; 472} 473 474void PBQPRegAlloc::findVRegIntervalsToAlloc() { 475 476 // Iterate over all live ranges. 477 for (LiveIntervals::iterator itr = lis->begin(), end = lis->end(); 478 itr != end; ++itr) { 479 480 // Ignore physical ones. 481 if (TargetRegisterInfo::isPhysicalRegister(itr->first)) 482 continue; 483 484 LiveInterval *li = itr->second; 485 486 // If this live interval is non-empty we will use pbqp to allocate it. 487 // Empty intervals we allocate in a simple post-processing stage in 488 // finalizeAlloc. 489 if (!li->empty()) { 490 vregIntervalsToAlloc.insert(li); 491 } 492 else { 493 emptyVRegIntervals.insert(li); 494 } 495 } 496} 497 498pbqp* PBQPRegAlloc::constructPBQPProblem() { 499 500 typedef std::vector<const LiveInterval*> LIVector; 501 typedef std::vector<unsigned> RegVector; 502 503 // This will store the physical intervals for easy reference. 504 LIVector physIntervals; 505 506 // Start by clearing the old node <-> live interval mappings & allowed sets 507 li2Node.clear(); 508 node2LI.clear(); 509 allowedSets.clear(); 510 511 // Populate physIntervals, update preg use: 512 for (LiveIntervals::iterator itr = lis->begin(), end = lis->end(); 513 itr != end; ++itr) { 514 515 if (TargetRegisterInfo::isPhysicalRegister(itr->first)) { 516 physIntervals.push_back(itr->second); 517 mri->setPhysRegUsed(itr->second->reg); 518 } 519 } 520 521 // Iterate over vreg intervals, construct live interval <-> node number 522 // mappings. 523 for (LiveIntervalSet::const_iterator 524 itr = vregIntervalsToAlloc.begin(), end = vregIntervalsToAlloc.end(); 525 itr != end; ++itr) { 526 const LiveInterval *li = *itr; 527 528 li2Node[li] = node2LI.size(); 529 node2LI.push_back(li); 530 } 531 532 // Get the set of potential coalesces. 533 CoalesceMap coalesces(findCoalesces()); 534 535 // Construct a PBQP solver for this problem 536 pbqp *solver = alloc_pbqp(vregIntervalsToAlloc.size()); 537 538 // Resize allowedSets container appropriately. 539 allowedSets.resize(vregIntervalsToAlloc.size()); 540 541 // Iterate over virtual register intervals to compute allowed sets... 542 for (unsigned node = 0; node < node2LI.size(); ++node) { 543 544 // Grab pointers to the interval and its register class. 545 const LiveInterval *li = node2LI[node]; 546 const TargetRegisterClass *liRC = mri->getRegClass(li->reg); 547 548 // Start by assuming all allocable registers in the class are allowed... 549 RegVector liAllowed(liRC->allocation_order_begin(*mf), 550 liRC->allocation_order_end(*mf)); 551 552 // Eliminate the physical registers which overlap with this range, along 553 // with all their aliases. 554 for (LIVector::iterator pItr = physIntervals.begin(), 555 pEnd = physIntervals.end(); pItr != pEnd; ++pItr) { 556 557 if (!li->overlaps(**pItr)) 558 continue; 559 560 unsigned pReg = (*pItr)->reg; 561 562 // If we get here then the live intervals overlap, but we're still ok 563 // if they're coalescable. 564 if (coalesces.find(RegPair(li->reg, pReg)) != coalesces.end()) 565 continue; 566 567 // If we get here then we have a genuine exclusion. 568 569 // Remove the overlapping reg... 570 RegVector::iterator eraseItr = 571 std::find(liAllowed.begin(), liAllowed.end(), pReg); 572 573 if (eraseItr != liAllowed.end()) 574 liAllowed.erase(eraseItr); 575 576 const unsigned *aliasItr = tri->getAliasSet(pReg); 577 578 if (aliasItr != 0) { 579 // ...and its aliases. 580 for (; *aliasItr != 0; ++aliasItr) { 581 RegVector::iterator eraseItr = 582 std::find(liAllowed.begin(), liAllowed.end(), *aliasItr); 583 584 if (eraseItr != liAllowed.end()) { 585 liAllowed.erase(eraseItr); 586 } 587 } 588 } 589 } 590 591 // Copy the allowed set into a member vector for use when constructing cost 592 // vectors & matrices, and mapping PBQP solutions back to assignments. 593 allowedSets[node] = AllowedSet(liAllowed.begin(), liAllowed.end()); 594 595 // Set the spill cost to the interval weight, or epsilon if the 596 // interval weight is zero 597 PBQPNum spillCost = (li->weight != 0.0) ? 598 li->weight : std::numeric_limits<PBQPNum>::min(); 599 600 // Build a cost vector for this interval. 601 add_pbqp_nodecosts(solver, node, 602 buildCostVector(li->reg, allowedSets[node], coalesces, 603 spillCost)); 604 605 } 606 607 608 // Now add the cost matrices... 609 for (unsigned node1 = 0; node1 < node2LI.size(); ++node1) { 610 const LiveInterval *li = node2LI[node1]; 611 612 // Test for live range overlaps and insert interference matrices. 613 for (unsigned node2 = node1 + 1; node2 < node2LI.size(); ++node2) { 614 const LiveInterval *li2 = node2LI[node2]; 615 616 CoalesceMap::const_iterator cmItr = 617 coalesces.find(RegPair(li->reg, li2->reg)); 618 619 PBQPMatrix *m = 0; 620 621 if (cmItr != coalesces.end()) { 622 m = buildCoalescingMatrix(allowedSets[node1], allowedSets[node2], 623 cmItr->second); 624 } 625 else if (li->overlaps(*li2)) { 626 m = buildInterferenceMatrix(allowedSets[node1], allowedSets[node2]); 627 } 628 629 if (m != 0) { 630 add_pbqp_edgecosts(solver, node1, node2, m); 631 delete m; 632 } 633 } 634 } 635 636 // We're done, PBQP problem constructed - return it. 637 return solver; 638} 639 640void PBQPRegAlloc::addStackInterval(const LiveInterval *spilled, 641 MachineRegisterInfo* mri) { 642 int stackSlot = vrm->getStackSlot(spilled->reg); 643 644 if (stackSlot == VirtRegMap::NO_STACK_SLOT) 645 return; 646 647 const TargetRegisterClass *RC = mri->getRegClass(spilled->reg); 648 LiveInterval &stackInterval = lss->getOrCreateInterval(stackSlot, RC); 649 650 VNInfo *vni; 651 if (stackInterval.getNumValNums() != 0) 652 vni = stackInterval.getValNumInfo(0); 653 else 654 vni = stackInterval.getNextValue(-0U, 0, lss->getVNInfoAllocator()); 655 656 LiveInterval &rhsInterval = lis->getInterval(spilled->reg); 657 stackInterval.MergeRangesInAsValue(rhsInterval, vni); 658} 659 660bool PBQPRegAlloc::mapPBQPToRegAlloc(pbqp *problem) { 661 662 // Set to true if we have any spills 663 bool anotherRoundNeeded = false; 664 665 // Clear the existing allocation. 666 vrm->clearAllVirt(); 667 668 // Iterate over the nodes mapping the PBQP solution to a register assignment. 669 for (unsigned node = 0; node < node2LI.size(); ++node) { 670 unsigned virtReg = node2LI[node]->reg, 671 allocSelection = get_pbqp_solution(problem, node); 672 673 // If the PBQP solution is non-zero it's a physical register... 674 if (allocSelection != 0) { 675 // Get the physical reg, subtracting 1 to account for the spill option. 676 unsigned physReg = allowedSets[node][allocSelection - 1]; 677 678 DOUT << "VREG " << virtReg << " -> " << tri->getName(physReg) << "\n"; 679 680 assert(physReg != 0); 681 682 // Add to the virt reg map and update the used phys regs. 683 vrm->assignVirt2Phys(virtReg, physReg); 684 } 685 // ...Otherwise it's a spill. 686 else { 687 688 // Make sure we ignore this virtual reg on the next round 689 // of allocation 690 vregIntervalsToAlloc.erase(&lis->getInterval(virtReg)); 691 692 // Insert spill ranges for this live range 693 const LiveInterval *spillInterval = node2LI[node]; 694 double oldSpillWeight = spillInterval->weight; 695 SmallVector<LiveInterval*, 8> spillIs; 696 std::vector<LiveInterval*> newSpills = 697 lis->addIntervalsForSpills(*spillInterval, spillIs, loopInfo, *vrm); 698 addStackInterval(spillInterval, mri); 699 700 DOUT << "VREG " << virtReg << " -> SPILLED (Cost: " 701 << oldSpillWeight << ", New vregs: "; 702 703 // Copy any newly inserted live intervals into the list of regs to 704 // allocate. 705 for (std::vector<LiveInterval*>::const_iterator 706 itr = newSpills.begin(), end = newSpills.end(); 707 itr != end; ++itr) { 708 709 assert(!(*itr)->empty() && "Empty spill range."); 710 711 DOUT << (*itr)->reg << " "; 712 713 vregIntervalsToAlloc.insert(*itr); 714 } 715 716 DOUT << ")\n"; 717 718 // We need another round if spill intervals were added. 719 anotherRoundNeeded |= !newSpills.empty(); 720 } 721 } 722 723 return !anotherRoundNeeded; 724} 725 726void PBQPRegAlloc::finalizeAlloc() const { 727 typedef LiveIntervals::iterator LIIterator; 728 typedef LiveInterval::Ranges::const_iterator LRIterator; 729 730 // First allocate registers for the empty intervals. 731 for (LiveIntervalSet::const_iterator 732 itr = emptyVRegIntervals.begin(), end = emptyVRegIntervals.end(); 733 itr != end; ++itr) { 734 LiveInterval *li = *itr; 735 736 unsigned physReg = li->preference; 737 738 if (physReg == 0) { 739 const TargetRegisterClass *liRC = mri->getRegClass(li->reg); 740 physReg = *liRC->allocation_order_begin(*mf); 741 } 742 743 vrm->assignVirt2Phys(li->reg, physReg); 744 } 745 746 // Finally iterate over the basic blocks to compute and set the live-in sets. 747 SmallVector<MachineBasicBlock*, 8> liveInMBBs; 748 MachineBasicBlock *entryMBB = &*mf->begin(); 749 750 for (LIIterator liItr = lis->begin(), liEnd = lis->end(); 751 liItr != liEnd; ++liItr) { 752 753 const LiveInterval *li = liItr->second; 754 unsigned reg = 0; 755 756 // Get the physical register for this interval 757 if (TargetRegisterInfo::isPhysicalRegister(li->reg)) { 758 reg = li->reg; 759 } 760 else if (vrm->isAssignedReg(li->reg)) { 761 reg = vrm->getPhys(li->reg); 762 } 763 else { 764 // Ranges which are assigned a stack slot only are ignored. 765 continue; 766 } 767 768 // Ignore unallocated vregs: 769 if (reg == 0) { 770 continue; 771 } 772 773 // Iterate over the ranges of the current interval... 774 for (LRIterator lrItr = li->begin(), lrEnd = li->end(); 775 lrItr != lrEnd; ++lrItr) { 776 777 // Find the set of basic blocks which this range is live into... 778 if (lis->findLiveInMBBs(lrItr->start, lrItr->end, liveInMBBs)) { 779 // And add the physreg for this interval to their live-in sets. 780 for (unsigned i = 0; i < liveInMBBs.size(); ++i) { 781 if (liveInMBBs[i] != entryMBB) { 782 if (!liveInMBBs[i]->isLiveIn(reg)) { 783 liveInMBBs[i]->addLiveIn(reg); 784 } 785 } 786 } 787 liveInMBBs.clear(); 788 } 789 } 790 } 791 792} 793 794bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) { 795 796 mf = &MF; 797 tm = &mf->getTarget(); 798 tri = tm->getRegisterInfo(); 799 tii = tm->getInstrInfo(); 800 mri = &mf->getRegInfo(); 801 802 lis = &getAnalysis<LiveIntervals>(); 803 lss = &getAnalysis<LiveStacks>(); 804 loopInfo = &getAnalysis<MachineLoopInfo>(); 805 806 vrm = &getAnalysis<VirtRegMap>(); 807 808 DOUT << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n"; 809 810 // Allocator main loop: 811 // 812 // * Map current regalloc problem to a PBQP problem 813 // * Solve the PBQP problem 814 // * Map the solution back to a register allocation 815 // * Spill if necessary 816 // 817 // This process is continued till no more spills are generated. 818 819 // Find the vreg intervals in need of allocation. 820 findVRegIntervalsToAlloc(); 821 822 // If there aren't any then we're done here. 823 if (vregIntervalsToAlloc.empty() && emptyVRegIntervals.empty()) 824 return true; 825 826 // If there are non-empty intervals allocate them using pbqp. 827 if (!vregIntervalsToAlloc.empty()) { 828 829 bool pbqpAllocComplete = false; 830 unsigned round = 0; 831 832 while (!pbqpAllocComplete) { 833 DOUT << " PBQP Regalloc round " << round << ":\n"; 834 835 pbqp *problem = constructPBQPProblem(); 836 837 solve_pbqp(problem); 838 839 pbqpAllocComplete = mapPBQPToRegAlloc(problem); 840 841 free_pbqp(problem); 842 843 ++round; 844 } 845 } 846 847 // Finalise allocation, allocate empty ranges. 848 finalizeAlloc(); 849 850 vregIntervalsToAlloc.clear(); 851 emptyVRegIntervals.clear(); 852 li2Node.clear(); 853 node2LI.clear(); 854 allowedSets.clear(); 855 856 DOUT << "Post alloc VirtRegMap:\n" << *vrm << "\n"; 857 858 // Run rewriter 859 std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter()); 860 861 rewriter->runOnMachineFunction(*mf, *vrm, lis); 862 863 return true; 864} 865 866FunctionPass* llvm::createPBQPRegisterAllocator() { 867 return new PBQPRegAlloc(); 868} 869 870 871#undef DEBUG_TYPE 872