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