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