RegAllocPBQP.cpp revision 8dd26253f54247e77e5accfdd70e7b4bf27b39c2
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 "LiveRangeEdit.h" 35#include "RenderMachineFunction.h" 36#include "Spiller.h" 37#include "VirtRegMap.h" 38#include "RegisterCoalescer.h" 39#include "llvm/Analysis/AliasAnalysis.h" 40#include "llvm/CodeGen/CalcSpillWeights.h" 41#include "llvm/CodeGen/LiveIntervalAnalysis.h" 42#include "llvm/CodeGen/LiveStackAnalysis.h" 43#include "llvm/CodeGen/RegAllocPBQP.h" 44#include "llvm/CodeGen/MachineDominators.h" 45#include "llvm/CodeGen/MachineFunctionPass.h" 46#include "llvm/CodeGen/MachineLoopInfo.h" 47#include "llvm/CodeGen/MachineRegisterInfo.h" 48#include "llvm/CodeGen/PBQP/HeuristicSolver.h" 49#include "llvm/CodeGen/PBQP/Graph.h" 50#include "llvm/CodeGen/PBQP/Heuristics/Briggs.h" 51#include "llvm/CodeGen/RegAllocRegistry.h" 52#include "llvm/Support/Debug.h" 53#include "llvm/Support/raw_ostream.h" 54#include "llvm/Target/TargetInstrInfo.h" 55#include "llvm/Target/TargetMachine.h" 56#include <limits> 57#include <memory> 58#include <set> 59#include <vector> 60 61using namespace llvm; 62 63static RegisterRegAlloc 64registerPBQPRepAlloc("pbqp", "PBQP register allocator", 65 createDefaultPBQPRegisterAllocator); 66 67static cl::opt<bool> 68pbqpCoalescing("pbqp-coalescing", 69 cl::desc("Attempt coalescing during PBQP register allocation."), 70 cl::init(false), cl::Hidden); 71 72namespace { 73 74/// 75/// PBQP based allocators solve the register allocation problem by mapping 76/// register allocation problems to Partitioned Boolean Quadratic 77/// Programming problems. 78class RegAllocPBQP : public MachineFunctionPass { 79public: 80 81 static char ID; 82 83 /// Construct a PBQP register allocator. 84 RegAllocPBQP(std::auto_ptr<PBQPBuilder> b, char *cPassID=0) 85 : MachineFunctionPass(ID), builder(b), customPassID(cPassID) { 86 initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 87 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 88 initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); 89 initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 90 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 91 initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 92 initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry()); 93 } 94 95 /// Return the pass name. 96 virtual const char* getPassName() const { 97 return "PBQP Register Allocator"; 98 } 99 100 /// PBQP analysis usage. 101 virtual void getAnalysisUsage(AnalysisUsage &au) const; 102 103 /// Perform register allocation 104 virtual bool runOnMachineFunction(MachineFunction &MF); 105 106private: 107 108 typedef std::map<const LiveInterval*, unsigned> LI2NodeMap; 109 typedef std::vector<const LiveInterval*> Node2LIMap; 110 typedef std::vector<unsigned> AllowedSet; 111 typedef std::vector<AllowedSet> AllowedSetMap; 112 typedef std::pair<unsigned, unsigned> RegPair; 113 typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap; 114 typedef std::vector<PBQP::Graph::NodeItr> NodeVector; 115 typedef std::set<unsigned> RegSet; 116 117 118 std::auto_ptr<PBQPBuilder> builder; 119 120 char *customPassID; 121 122 MachineFunction *mf; 123 const TargetMachine *tm; 124 const TargetRegisterInfo *tri; 125 const TargetInstrInfo *tii; 126 const MachineLoopInfo *loopInfo; 127 MachineRegisterInfo *mri; 128 RenderMachineFunction *rmf; 129 130 std::auto_ptr<Spiller> spiller; 131 LiveIntervals *lis; 132 LiveStacks *lss; 133 VirtRegMap *vrm; 134 135 RegSet vregsToAlloc, emptyIntervalVRegs; 136 137 /// \brief Finds the initial set of vreg intervals to allocate. 138 void findVRegIntervalsToAlloc(); 139 140 /// \brief Given a solved PBQP problem maps this solution back to a register 141 /// assignment. 142 bool mapPBQPToRegAlloc(const PBQPRAProblem &problem, 143 const PBQP::Solution &solution); 144 145 /// \brief Postprocessing before final spilling. Sets basic block "live in" 146 /// variables. 147 void finalizeAlloc() const; 148 149}; 150 151char RegAllocPBQP::ID = 0; 152 153} // End anonymous namespace. 154 155unsigned PBQPRAProblem::getVRegForNode(PBQP::Graph::ConstNodeItr node) const { 156 Node2VReg::const_iterator vregItr = node2VReg.find(node); 157 assert(vregItr != node2VReg.end() && "No vreg for node."); 158 return vregItr->second; 159} 160 161PBQP::Graph::NodeItr PBQPRAProblem::getNodeForVReg(unsigned vreg) const { 162 VReg2Node::const_iterator nodeItr = vreg2Node.find(vreg); 163 assert(nodeItr != vreg2Node.end() && "No node for vreg."); 164 return nodeItr->second; 165 166} 167 168const PBQPRAProblem::AllowedSet& 169 PBQPRAProblem::getAllowedSet(unsigned vreg) const { 170 AllowedSetMap::const_iterator allowedSetItr = allowedSets.find(vreg); 171 assert(allowedSetItr != allowedSets.end() && "No pregs for vreg."); 172 const AllowedSet &allowedSet = allowedSetItr->second; 173 return allowedSet; 174} 175 176unsigned PBQPRAProblem::getPRegForOption(unsigned vreg, unsigned option) const { 177 assert(isPRegOption(vreg, option) && "Not a preg option."); 178 179 const AllowedSet& allowedSet = getAllowedSet(vreg); 180 assert(option <= allowedSet.size() && "Option outside allowed set."); 181 return allowedSet[option - 1]; 182} 183 184std::auto_ptr<PBQPRAProblem> PBQPBuilder::build(MachineFunction *mf, 185 const LiveIntervals *lis, 186 const MachineLoopInfo *loopInfo, 187 const RegSet &vregs) { 188 189 typedef std::vector<const LiveInterval*> LIVector; 190 191 MachineRegisterInfo *mri = &mf->getRegInfo(); 192 const TargetRegisterInfo *tri = mf->getTarget().getRegisterInfo(); 193 194 std::auto_ptr<PBQPRAProblem> p(new PBQPRAProblem()); 195 PBQP::Graph &g = p->getGraph(); 196 RegSet pregs; 197 198 // Collect the set of preg intervals, record that they're used in the MF. 199 for (LiveIntervals::const_iterator itr = lis->begin(), end = lis->end(); 200 itr != end; ++itr) { 201 if (TargetRegisterInfo::isPhysicalRegister(itr->first)) { 202 pregs.insert(itr->first); 203 mri->setPhysRegUsed(itr->first); 204 } 205 } 206 207 BitVector reservedRegs = tri->getReservedRegs(*mf); 208 209 // Iterate over vregs. 210 for (RegSet::const_iterator vregItr = vregs.begin(), vregEnd = vregs.end(); 211 vregItr != vregEnd; ++vregItr) { 212 unsigned vreg = *vregItr; 213 const TargetRegisterClass *trc = mri->getRegClass(vreg); 214 const LiveInterval *vregLI = &lis->getInterval(vreg); 215 216 // Compute an initial allowed set for the current vreg. 217 typedef std::vector<unsigned> VRAllowed; 218 VRAllowed vrAllowed; 219 ArrayRef<unsigned> rawOrder = trc->getRawAllocationOrder(*mf); 220 for (unsigned i = 0; i != rawOrder.size(); ++i) { 221 unsigned preg = rawOrder[i]; 222 if (!reservedRegs.test(preg)) { 223 vrAllowed.push_back(preg); 224 } 225 } 226 227 // Remove any physical registers which overlap. 228 for (RegSet::const_iterator pregItr = pregs.begin(), 229 pregEnd = pregs.end(); 230 pregItr != pregEnd; ++pregItr) { 231 unsigned preg = *pregItr; 232 const LiveInterval *pregLI = &lis->getInterval(preg); 233 234 if (pregLI->empty()) { 235 continue; 236 } 237 238 if (!vregLI->overlaps(*pregLI)) { 239 continue; 240 } 241 242 // Remove the register from the allowed set. 243 VRAllowed::iterator eraseItr = 244 std::find(vrAllowed.begin(), vrAllowed.end(), preg); 245 246 if (eraseItr != vrAllowed.end()) { 247 vrAllowed.erase(eraseItr); 248 } 249 250 // Also remove any aliases. 251 const unsigned *aliasItr = tri->getAliasSet(preg); 252 if (aliasItr != 0) { 253 for (; *aliasItr != 0; ++aliasItr) { 254 VRAllowed::iterator eraseItr = 255 std::find(vrAllowed.begin(), vrAllowed.end(), *aliasItr); 256 257 if (eraseItr != vrAllowed.end()) { 258 vrAllowed.erase(eraseItr); 259 } 260 } 261 } 262 } 263 264 // Construct the node. 265 PBQP::Graph::NodeItr node = 266 g.addNode(PBQP::Vector(vrAllowed.size() + 1, 0)); 267 268 // Record the mapping and allowed set in the problem. 269 p->recordVReg(vreg, node, vrAllowed.begin(), vrAllowed.end()); 270 271 PBQP::PBQPNum spillCost = (vregLI->weight != 0.0) ? 272 vregLI->weight : std::numeric_limits<PBQP::PBQPNum>::min(); 273 274 addSpillCosts(g.getNodeCosts(node), spillCost); 275 } 276 277 for (RegSet::const_iterator vr1Itr = vregs.begin(), vrEnd = vregs.end(); 278 vr1Itr != vrEnd; ++vr1Itr) { 279 unsigned vr1 = *vr1Itr; 280 const LiveInterval &l1 = lis->getInterval(vr1); 281 const PBQPRAProblem::AllowedSet &vr1Allowed = p->getAllowedSet(vr1); 282 283 for (RegSet::const_iterator vr2Itr = llvm::next(vr1Itr); 284 vr2Itr != vrEnd; ++vr2Itr) { 285 unsigned vr2 = *vr2Itr; 286 const LiveInterval &l2 = lis->getInterval(vr2); 287 const PBQPRAProblem::AllowedSet &vr2Allowed = p->getAllowedSet(vr2); 288 289 assert(!l2.empty() && "Empty interval in vreg set?"); 290 if (l1.overlaps(l2)) { 291 PBQP::Graph::EdgeItr edge = 292 g.addEdge(p->getNodeForVReg(vr1), p->getNodeForVReg(vr2), 293 PBQP::Matrix(vr1Allowed.size()+1, vr2Allowed.size()+1, 0)); 294 295 addInterferenceCosts(g.getEdgeCosts(edge), vr1Allowed, vr2Allowed, tri); 296 } 297 } 298 } 299 300 return p; 301} 302 303void PBQPBuilder::addSpillCosts(PBQP::Vector &costVec, 304 PBQP::PBQPNum spillCost) { 305 costVec[0] = spillCost; 306} 307 308void PBQPBuilder::addInterferenceCosts( 309 PBQP::Matrix &costMat, 310 const PBQPRAProblem::AllowedSet &vr1Allowed, 311 const PBQPRAProblem::AllowedSet &vr2Allowed, 312 const TargetRegisterInfo *tri) { 313 assert(costMat.getRows() == vr1Allowed.size() + 1 && "Matrix height mismatch."); 314 assert(costMat.getCols() == vr2Allowed.size() + 1 && "Matrix width mismatch."); 315 316 for (unsigned i = 0; i != vr1Allowed.size(); ++i) { 317 unsigned preg1 = vr1Allowed[i]; 318 319 for (unsigned j = 0; j != vr2Allowed.size(); ++j) { 320 unsigned preg2 = vr2Allowed[j]; 321 322 if (tri->regsOverlap(preg1, preg2)) { 323 costMat[i + 1][j + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity(); 324 } 325 } 326 } 327} 328 329std::auto_ptr<PBQPRAProblem> PBQPBuilderWithCoalescing::build( 330 MachineFunction *mf, 331 const LiveIntervals *lis, 332 const MachineLoopInfo *loopInfo, 333 const RegSet &vregs) { 334 335 std::auto_ptr<PBQPRAProblem> p = PBQPBuilder::build(mf, lis, loopInfo, vregs); 336 PBQP::Graph &g = p->getGraph(); 337 338 const TargetMachine &tm = mf->getTarget(); 339 CoalescerPair cp(*tm.getInstrInfo(), *tm.getRegisterInfo()); 340 341 // Scan the machine function and add a coalescing cost whenever CoalescerPair 342 // gives the Ok. 343 for (MachineFunction::const_iterator mbbItr = mf->begin(), 344 mbbEnd = mf->end(); 345 mbbItr != mbbEnd; ++mbbItr) { 346 const MachineBasicBlock *mbb = &*mbbItr; 347 348 for (MachineBasicBlock::const_iterator miItr = mbb->begin(), 349 miEnd = mbb->end(); 350 miItr != miEnd; ++miItr) { 351 const MachineInstr *mi = &*miItr; 352 353 if (!cp.setRegisters(mi)) { 354 continue; // Not coalescable. 355 } 356 357 if (cp.getSrcReg() == cp.getDstReg()) { 358 continue; // Already coalesced. 359 } 360 361 unsigned dst = cp.getDstReg(), 362 src = cp.getSrcReg(); 363 364 const float copyFactor = 0.5; // Cost of copy relative to load. Current 365 // value plucked randomly out of the air. 366 367 PBQP::PBQPNum cBenefit = 368 copyFactor * LiveIntervals::getSpillWeight(false, true, 369 loopInfo->getLoopDepth(mbb)); 370 371 if (cp.isPhys()) { 372 if (!lis->isAllocatable(dst)) { 373 continue; 374 } 375 376 const PBQPRAProblem::AllowedSet &allowed = p->getAllowedSet(src); 377 unsigned pregOpt = 0; 378 while (pregOpt < allowed.size() && allowed[pregOpt] != dst) { 379 ++pregOpt; 380 } 381 if (pregOpt < allowed.size()) { 382 ++pregOpt; // +1 to account for spill option. 383 PBQP::Graph::NodeItr node = p->getNodeForVReg(src); 384 addPhysRegCoalesce(g.getNodeCosts(node), pregOpt, cBenefit); 385 } 386 } else { 387 const PBQPRAProblem::AllowedSet *allowed1 = &p->getAllowedSet(dst); 388 const PBQPRAProblem::AllowedSet *allowed2 = &p->getAllowedSet(src); 389 PBQP::Graph::NodeItr node1 = p->getNodeForVReg(dst); 390 PBQP::Graph::NodeItr node2 = p->getNodeForVReg(src); 391 PBQP::Graph::EdgeItr edge = g.findEdge(node1, node2); 392 if (edge == g.edgesEnd()) { 393 edge = g.addEdge(node1, node2, PBQP::Matrix(allowed1->size() + 1, 394 allowed2->size() + 1, 395 0)); 396 } else { 397 if (g.getEdgeNode1(edge) == node2) { 398 std::swap(node1, node2); 399 std::swap(allowed1, allowed2); 400 } 401 } 402 403 addVirtRegCoalesce(g.getEdgeCosts(edge), *allowed1, *allowed2, 404 cBenefit); 405 } 406 } 407 } 408 409 return p; 410} 411 412void PBQPBuilderWithCoalescing::addPhysRegCoalesce(PBQP::Vector &costVec, 413 unsigned pregOption, 414 PBQP::PBQPNum benefit) { 415 costVec[pregOption] += -benefit; 416} 417 418void PBQPBuilderWithCoalescing::addVirtRegCoalesce( 419 PBQP::Matrix &costMat, 420 const PBQPRAProblem::AllowedSet &vr1Allowed, 421 const PBQPRAProblem::AllowedSet &vr2Allowed, 422 PBQP::PBQPNum benefit) { 423 424 assert(costMat.getRows() == vr1Allowed.size() + 1 && "Size mismatch."); 425 assert(costMat.getCols() == vr2Allowed.size() + 1 && "Size mismatch."); 426 427 for (unsigned i = 0; i != vr1Allowed.size(); ++i) { 428 unsigned preg1 = vr1Allowed[i]; 429 for (unsigned j = 0; j != vr2Allowed.size(); ++j) { 430 unsigned preg2 = vr2Allowed[j]; 431 432 if (preg1 == preg2) { 433 costMat[i + 1][j + 1] += -benefit; 434 } 435 } 436 } 437} 438 439 440void RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const { 441 au.setPreservesCFG(); 442 au.addRequired<AliasAnalysis>(); 443 au.addPreserved<AliasAnalysis>(); 444 au.addRequired<SlotIndexes>(); 445 au.addPreserved<SlotIndexes>(); 446 au.addRequired<LiveIntervals>(); 447 //au.addRequiredID(SplitCriticalEdgesID); 448 if (customPassID) 449 au.addRequiredID(*customPassID); 450 au.addRequired<CalculateSpillWeights>(); 451 au.addRequired<LiveStacks>(); 452 au.addPreserved<LiveStacks>(); 453 au.addRequired<MachineDominatorTree>(); 454 au.addPreserved<MachineDominatorTree>(); 455 au.addRequired<MachineLoopInfo>(); 456 au.addPreserved<MachineLoopInfo>(); 457 au.addRequired<VirtRegMap>(); 458 au.addRequired<RenderMachineFunction>(); 459 MachineFunctionPass::getAnalysisUsage(au); 460} 461 462void RegAllocPBQP::findVRegIntervalsToAlloc() { 463 464 // Iterate over all live ranges. 465 for (LiveIntervals::iterator itr = lis->begin(), end = lis->end(); 466 itr != end; ++itr) { 467 468 // Ignore physical ones. 469 if (TargetRegisterInfo::isPhysicalRegister(itr->first)) 470 continue; 471 472 LiveInterval *li = itr->second; 473 474 // If this live interval is non-empty we will use pbqp to allocate it. 475 // Empty intervals we allocate in a simple post-processing stage in 476 // finalizeAlloc. 477 if (!li->empty()) { 478 vregsToAlloc.insert(li->reg); 479 } else { 480 emptyIntervalVRegs.insert(li->reg); 481 } 482 } 483} 484 485bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAProblem &problem, 486 const PBQP::Solution &solution) { 487 // Set to true if we have any spills 488 bool anotherRoundNeeded = false; 489 490 // Clear the existing allocation. 491 vrm->clearAllVirt(); 492 493 const PBQP::Graph &g = problem.getGraph(); 494 // Iterate over the nodes mapping the PBQP solution to a register 495 // assignment. 496 for (PBQP::Graph::ConstNodeItr node = g.nodesBegin(), 497 nodeEnd = g.nodesEnd(); 498 node != nodeEnd; ++node) { 499 unsigned vreg = problem.getVRegForNode(node); 500 unsigned alloc = solution.getSelection(node); 501 502 if (problem.isPRegOption(vreg, alloc)) { 503 unsigned preg = problem.getPRegForOption(vreg, alloc); 504 DEBUG(dbgs() << "VREG " << vreg << " -> " << tri->getName(preg) << "\n"); 505 assert(preg != 0 && "Invalid preg selected."); 506 vrm->assignVirt2Phys(vreg, preg); 507 } else if (problem.isSpillOption(vreg, alloc)) { 508 vregsToAlloc.erase(vreg); 509 SmallVector<LiveInterval*, 8> newSpills; 510 LiveRangeEdit LRE(lis->getInterval(vreg), newSpills); 511 spiller->spill(LRE); 512 513 DEBUG(dbgs() << "VREG " << vreg << " -> SPILLED (Cost: " 514 << LRE.getParent().weight << ", New vregs: "); 515 516 // Copy any newly inserted live intervals into the list of regs to 517 // allocate. 518 for (LiveRangeEdit::iterator itr = LRE.begin(), end = LRE.end(); 519 itr != end; ++itr) { 520 assert(!(*itr)->empty() && "Empty spill range."); 521 DEBUG(dbgs() << (*itr)->reg << " "); 522 vregsToAlloc.insert((*itr)->reg); 523 } 524 525 DEBUG(dbgs() << ")\n"); 526 527 // We need another round if spill intervals were added. 528 anotherRoundNeeded |= !LRE.empty(); 529 } else { 530 llvm_unreachable("Unknown allocation option."); 531 } 532 } 533 534 return !anotherRoundNeeded; 535} 536 537 538void RegAllocPBQP::finalizeAlloc() const { 539 typedef LiveIntervals::iterator LIIterator; 540 typedef LiveInterval::Ranges::const_iterator LRIterator; 541 542 // First allocate registers for the empty intervals. 543 for (RegSet::const_iterator 544 itr = emptyIntervalVRegs.begin(), end = emptyIntervalVRegs.end(); 545 itr != end; ++itr) { 546 LiveInterval *li = &lis->getInterval(*itr); 547 548 unsigned physReg = vrm->getRegAllocPref(li->reg); 549 550 if (physReg == 0) { 551 const TargetRegisterClass *liRC = mri->getRegClass(li->reg); 552 physReg = liRC->getRawAllocationOrder(*mf).front(); 553 } 554 555 vrm->assignVirt2Phys(li->reg, physReg); 556 } 557 558 // Finally iterate over the basic blocks to compute and set the live-in sets. 559 SmallVector<MachineBasicBlock*, 8> liveInMBBs; 560 MachineBasicBlock *entryMBB = &*mf->begin(); 561 562 for (LIIterator liItr = lis->begin(), liEnd = lis->end(); 563 liItr != liEnd; ++liItr) { 564 565 const LiveInterval *li = liItr->second; 566 unsigned reg = 0; 567 568 // Get the physical register for this interval 569 if (TargetRegisterInfo::isPhysicalRegister(li->reg)) { 570 reg = li->reg; 571 } else if (vrm->isAssignedReg(li->reg)) { 572 reg = vrm->getPhys(li->reg); 573 } else { 574 // Ranges which are assigned a stack slot only are ignored. 575 continue; 576 } 577 578 if (reg == 0) { 579 // Filter out zero regs - they're for intervals that were spilled. 580 continue; 581 } 582 583 // Iterate over the ranges of the current interval... 584 for (LRIterator lrItr = li->begin(), lrEnd = li->end(); 585 lrItr != lrEnd; ++lrItr) { 586 587 // Find the set of basic blocks which this range is live into... 588 if (lis->findLiveInMBBs(lrItr->start, lrItr->end, liveInMBBs)) { 589 // And add the physreg for this interval to their live-in sets. 590 for (unsigned i = 0; i != liveInMBBs.size(); ++i) { 591 if (liveInMBBs[i] != entryMBB) { 592 if (!liveInMBBs[i]->isLiveIn(reg)) { 593 liveInMBBs[i]->addLiveIn(reg); 594 } 595 } 596 } 597 liveInMBBs.clear(); 598 } 599 } 600 } 601 602} 603 604bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { 605 606 mf = &MF; 607 tm = &mf->getTarget(); 608 tri = tm->getRegisterInfo(); 609 tii = tm->getInstrInfo(); 610 mri = &mf->getRegInfo(); 611 612 lis = &getAnalysis<LiveIntervals>(); 613 lss = &getAnalysis<LiveStacks>(); 614 loopInfo = &getAnalysis<MachineLoopInfo>(); 615 rmf = &getAnalysis<RenderMachineFunction>(); 616 617 vrm = &getAnalysis<VirtRegMap>(); 618 spiller.reset(createInlineSpiller(*this, MF, *vrm)); 619 620 mri->freezeReservedRegs(MF); 621 622 DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n"); 623 624 // Allocator main loop: 625 // 626 // * Map current regalloc problem to a PBQP problem 627 // * Solve the PBQP problem 628 // * Map the solution back to a register allocation 629 // * Spill if necessary 630 // 631 // This process is continued till no more spills are generated. 632 633 // Find the vreg intervals in need of allocation. 634 findVRegIntervalsToAlloc(); 635 636 // If there are non-empty intervals allocate them using pbqp. 637 if (!vregsToAlloc.empty()) { 638 639 bool pbqpAllocComplete = false; 640 unsigned round = 0; 641 642 while (!pbqpAllocComplete) { 643 DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n"); 644 645 std::auto_ptr<PBQPRAProblem> problem = 646 builder->build(mf, lis, loopInfo, vregsToAlloc); 647 PBQP::Solution solution = 648 PBQP::HeuristicSolver<PBQP::Heuristics::Briggs>::solve( 649 problem->getGraph()); 650 651 pbqpAllocComplete = mapPBQPToRegAlloc(*problem, solution); 652 653 ++round; 654 } 655 } 656 657 // Finalise allocation, allocate empty ranges. 658 finalizeAlloc(); 659 660 rmf->renderMachineFunction("After PBQP register allocation.", vrm); 661 662 vregsToAlloc.clear(); 663 emptyIntervalVRegs.clear(); 664 665 DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm << "\n"); 666 667 // Run rewriter 668 vrm->rewrite(lis->getSlotIndexes()); 669 670 return true; 671} 672 673FunctionPass* llvm::createPBQPRegisterAllocator( 674 std::auto_ptr<PBQPBuilder> builder, 675 char *customPassID) { 676 return new RegAllocPBQP(builder, customPassID); 677} 678 679FunctionPass* llvm::createDefaultPBQPRegisterAllocator() { 680 if (pbqpCoalescing) { 681 return createPBQPRegisterAllocator( 682 std::auto_ptr<PBQPBuilder>(new PBQPBuilderWithCoalescing())); 683 } // else 684 return createPBQPRegisterAllocator( 685 std::auto_ptr<PBQPBuilder>(new PBQPBuilder())); 686} 687 688#undef DEBUG_TYPE 689