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