1 //===------ RegAllocPBQP.cpp ---- PBQP Register Allocator -------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
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:
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.
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,
30 //===----------------------------------------------------------------------===//
32 #define DEBUG_TYPE "regalloc"
34 #include "RenderMachineFunction.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"
62 using namespace PBQP::Heuristics;
64 static RegisterRegAlloc
65 registerPBQPRepAlloc("pbqp", "PBQP register allocator",
66 llvm::createPBQPRegisterAllocator);
69 pbqpCoalescing("pbqp-coalescing",
70 cl::desc("Attempt coalescing during PBQP register allocation."),
71 cl::init(false), cl::Hidden);
74 pbqpBuilder("pbqp-builder",
75 cl::desc("Use new builder system."),
76 cl::init(false), cl::Hidden);
80 pbqpPreSplitting("pbqp-pre-splitting",
81 cl::desc("Pre-splite before PBQP register allocation."),
82 cl::init(false), cl::Hidden);
84 char RegAllocPBQP::ID = 0;
86 unsigned 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;
92 PBQP::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;
99 const 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;
107 unsigned PBQPRAProblem::getPRegForOption(unsigned vreg, unsigned option) const {
108 assert(isPRegOption(vreg, option) && "Not a preg option.");
110 const AllowedSet& allowedSet = getAllowedSet(vreg);
111 assert(option <= allowedSet.size() && "Option outside allowed set.");
112 return allowedSet[option - 1];
115 std::auto_ptr<PBQPRAProblem> PBQPBuilder::build(
117 const LiveIntervals *lis,
118 const RegSet &vregs) {
120 typedef std::vector<const LiveInterval*> LIVector;
122 MachineRegisterInfo *mri = &mf->getRegInfo();
123 const TargetRegisterInfo *tri = mf->getTarget().getRegisterInfo();
125 std::auto_ptr<PBQPRAProblem> p(new PBQPRAProblem());
126 PBQP::Graph &g = p->getGraph();
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();
132 if (TargetRegisterInfo::isPhysicalRegister(itr->first)) {
133 pregs.insert(itr->first);
134 mri->setPhysRegUsed(itr->first);
138 BitVector reservedRegs = tri->getReservedRegs(*mf);
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);
147 // Compute an initial allowed set for the current vreg.
148 typedef std::vector<unsigned> 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);
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);
169 if (!vregLI->overlaps(*pregLI))
172 // Remove the register from the allowed set.
173 VRAllowed::iterator eraseItr =
174 std::find(vrAllowed.begin(), vrAllowed.end(), preg);
176 if (eraseItr != vrAllowed.end()) {
177 vrAllowed.erase(eraseItr);
180 // Also remove any aliases.
181 const unsigned *aliasItr = tri->getAliasSet(preg);
183 for (; *aliasItr != 0; ++aliasItr) {
184 VRAllowed::iterator eraseItr =
185 std::find(vrAllowed.begin(), vrAllowed.end(), *aliasItr);
187 if (eraseItr != vrAllowed.end()) {
188 vrAllowed.erase(eraseItr);
194 // Construct the node.
195 PBQP::Graph::NodeItr node =
196 g.addNode(PBQP::Vector(vrAllowed.size() + 1, 0));
198 // Record the mapping and allowed set in the problem.
199 p->recordVReg(vreg, node, vrAllowed.begin(), vrAllowed.end());
201 PBQP::PBQPNum spillCost = (vregLI->weight != 0.0) ?
202 vregLI->weight : std::numeric_limits<PBQP::PBQPNum>::min();
204 addSpillCosts(g.getNodeCosts(node), spillCost);
207 for (RegSet::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);
213 for (RegSet::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);
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));
225 addInterferenceCosts(g.getEdgeCosts(edge), vr1Allowed, vr2Allowed, tri);
233 void PBQPBuilder::addSpillCosts(PBQP::Vector &costVec,
234 PBQP::PBQPNum spillCost) {
235 costVec[0] = spillCost;
238 void 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.");
245 for (unsigned i = 0; i < vr1Allowed.size(); ++i) {
246 unsigned preg1 = vr1Allowed[i];
248 for (unsigned j = 0; j < vr2Allowed.size(); ++j) {
249 unsigned preg2 = vr2Allowed[j];
251 if (tri->regsOverlap(preg1, preg2)) {
252 costMat[i + 1][j + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity();
260 void 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);
278 template <typename RegContainer>
279 PBQP::Vector RegAllocPBQP::buildCostVector(unsigned vReg,
280 const RegContainer &allowed,
281 const CoalesceMap &coalesces,
282 PBQP::PBQPNum spillCost) const {
284 typedef typename RegContainer::const_iterator AllowedItr;
286 // Allocate vector. Additional element (0th) used for spill option
287 PBQP::Vector v(allowed.size() + 1, 0);
291 // Iterate over the allowed registers inserting coalesce benefits if there
294 for (AllowedItr itr = allowed.begin(), end = allowed.end();
295 itr != end; ++itr, ++ai) {
297 unsigned pReg = *itr;
299 CoalesceMap::const_iterator cmItr =
300 coalesces.find(RegPair(vReg, pReg));
302 // No coalesce - on to the next preg.
303 if (cmItr == coalesces.end())
306 // We have a coalesce - insert the benefit.
307 v[ai + 1] = -cmItr->second;
313 template <typename RegContainer>
314 PBQP::Matrix* RegAllocPBQP::buildInterferenceMatrix(
315 const RegContainer &allowed1, const RegContainer &allowed2) const {
317 typedef typename RegContainer::const_iterator RegContainerIterator;
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).
328 new PBQP::Matrix(allowed1.size() + 1, allowed2.size() + 1, 0);
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;
339 // Row index. Starts at 1, since the 0th row is for the spill option, which
343 // Iterate over allowed sets, insert infinities where required.
344 for (RegContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end();
345 a1Itr != a1End; ++a1Itr) {
347 // Column index, starts at 1 as for row index.
349 unsigned reg1 = *a1Itr;
351 for (RegContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end();
352 a2Itr != a2End; ++a2Itr) {
354 unsigned reg2 = *a2Itr;
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;
368 // If this turns out to be a zero matrix...
370 // free it and return null.
375 // ...otherwise return the cost matrix.
379 template <typename RegContainer>
380 PBQP::Matrix* RegAllocPBQP::buildCoalescingMatrix(
381 const RegContainer &allowed1, const RegContainer &allowed2,
382 PBQP::PBQPNum cBenefit) const {
384 typedef typename RegContainer::const_iterator RegContainerIterator;
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.
392 new PBQP::Matrix(allowed1.size() + 1, allowed2.size() + 1, 0);
394 // Reset costs to zero.
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;
401 // Row index. Starts at 1, since the 0th row is for the spill option, which
405 // Iterate over the allowed sets, insert coalescing benefits where
407 for (RegContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end();
408 a1Itr != a1End; ++a1Itr) {
410 // Column index, starts at 1 as for row index.
412 unsigned reg1 = *a1Itr;
414 for (RegContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end();
415 a2Itr != a2End; ++a2Itr) {
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
420 if (reg1 == *a2Itr) {
421 (*m)[ri][ci] = -cBenefit;
422 isZeroMatrix = false;
431 // If this turns out to be a zero matrix...
433 // ...free it and return null.
441 RegAllocPBQP::CoalesceMap RegAllocPBQP::findCoalesces() {
443 typedef MachineFunction::const_iterator MFIterator;
444 typedef MachineBasicBlock::const_iterator MBBIterator;
445 typedef LiveInterval::const_vni_iterator VNIIterator;
447 CoalesceMap coalescesFound;
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) {
454 const MachineBasicBlock *mbb = &*bbItr;
456 for (MBBIterator iItr = mbb->begin(), iEnd = mbb->end();
457 iItr != iEnd; ++iItr) {
459 const MachineInstr *instr = &*iItr;
461 // If this isn't a copy then continue to the next instruction.
462 if (!instr->isCopy())
465 unsigned srcReg = instr->getOperand(1).getReg();
466 unsigned dstReg = instr->getOperand(0).getReg();
468 // If the registers are already the same our job is nice and easy.
469 if (dstReg == srcReg)
472 bool srcRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(srcReg),
473 dstRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(dstReg);
475 // If both registers are physical then we can't coalesce.
476 if (srcRegIsPhysical && dstRegIsPhysical)
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))
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))
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))
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);
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.
512 // Otherwise start by assuming we're ok.
515 // Test all defs of the source range.
517 vniItr = srcLI->vni_begin(), vniEnd = srcLI->vni_end();
518 vniItr != vniEnd; ++vniItr) {
520 // If we find a poorly defined def we err on the side of caution.
521 if (!(*vniItr)->def.isValid()) {
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)) {
534 // If we have a bad def give up, continue to the next instruction.
538 // Otherwise test definitions of the destination range.
540 vniItr = dstLI->vni_begin(), vniEnd = dstLI->vni_end();
541 vniItr != vniEnd; ++vniItr) {
543 // We want to make sure we skip the copy instruction itself.
544 if ((*vniItr)->getCopy() == instr)
547 if (!(*vniItr)->def.isValid()) {
552 if (srcLI->liveAt((*vniItr)->def)) {
558 // As before a bad def we give up and continue to the next instr.
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.
567 float cBenefit = std::pow(10.0f, (float)loopInfo->getLoopDepth(mbb)) / 5.0;
569 coalescesFound[RegPair(srcReg, dstReg)] = cBenefit;
570 coalescesFound[RegPair(dstReg, srcReg)] = cBenefit;
575 return coalescesFound;
578 void RegAllocPBQP::findVRegIntervalsToAlloc() {
580 // Iterate over all live ranges.
581 for (LiveIntervals::iterator itr = lis->begin(), end = lis->end();
584 // Ignore physical ones.
585 if (TargetRegisterInfo::isPhysicalRegister(itr->first))
588 LiveInterval *li = itr->second;
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
594 vregsToAlloc.insert(li->reg);
597 emptyIntervalVRegs.insert(li->reg);
602 PBQP::Graph RegAllocPBQP::constructPBQPProblem() {
604 typedef std::vector<const LiveInterval*> LIVector;
605 typedef std::vector<unsigned> RegVector;
607 // This will store the physical intervals for easy reference.
608 LIVector physIntervals;
610 // Start by clearing the old node <-> live interval mappings & allowed sets
615 // Populate physIntervals, update preg use:
616 for (LiveIntervals::iterator itr = lis->begin(), end = lis->end();
619 if (TargetRegisterInfo::isPhysicalRegister(itr->first)) {
620 physIntervals.push_back(itr->second);
621 mri->setPhysRegUsed(itr->second->reg);
625 // Iterate over vreg intervals, construct live interval <-> node number
627 for (RegSet::const_iterator itr = vregsToAlloc.begin(),
628 end = vregsToAlloc.end();
630 const LiveInterval *li = &lis->getInterval(*itr);
632 li2Node[li] = node2LI.size();
633 node2LI.push_back(li);
636 // Get the set of potential coalesces.
637 CoalesceMap coalesces;
639 if (pbqpCoalescing) {
640 coalesces = findCoalesces();
643 // Construct a PBQP solver for this problem
645 problemNodes.resize(vregsToAlloc.size());
647 // Resize allowedSets container appropriately.
648 allowedSets.resize(vregsToAlloc.size());
650 BitVector ReservedRegs = tri->getReservedRegs(*mf);
652 // Iterate over virtual register intervals to compute allowed sets...
653 for (unsigned node = 0; node < node2LI.size(); ++node) {
655 // Grab pointers to the interval and its register class.
656 const LiveInterval *li = node2LI[node];
657 const TargetRegisterClass *liRC = mri->getRegClass(li->reg);
659 // Start by assuming all allocable registers in the class are allowed...
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);
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) {
672 if (!li->overlaps(**pItr))
675 unsigned pReg = (*pItr)->reg;
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");
684 // If we get here then we have a genuine exclusion.
686 // Remove the overlapping reg...
687 RegVector::iterator eraseItr =
688 std::find(liAllowed.begin(), liAllowed.end(), pReg);
690 if (eraseItr != liAllowed.end())
691 liAllowed.erase(eraseItr);
693 const unsigned *aliasItr = tri->getAliasSet(pReg);
696 // ...and its aliases.
697 for (; *aliasItr != 0; ++aliasItr) {
698 RegVector::iterator eraseItr =
699 std::find(liAllowed.begin(), liAllowed.end(), *aliasItr);
701 if (eraseItr != liAllowed.end()) {
702 liAllowed.erase(eraseItr);
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());
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();
717 // Build a cost vector for this interval.
720 buildCostVector(li->reg, allowedSets[node], coalesces, spillCost));
725 // Now add the cost matrices...
726 for (unsigned node1 = 0; node1 < node2LI.size(); ++node1) {
727 const LiveInterval *li = node2LI[node1];
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];
733 CoalesceMap::const_iterator cmItr =
734 coalesces.find(RegPair(li->reg, li2->reg));
738 if (cmItr != coalesces.end()) {
739 m = buildCoalescingMatrix(allowedSets[node1], allowedSets[node2],
742 else if (li->overlaps(*li2)) {
743 m = buildInterferenceMatrix(allowedSets[node1], allowedSets[node2]);
747 problem.addEdge(problemNodes[node1],
756 assert(problem.getNumNodes() == allowedSets.size());
758 std::cerr << "Allocating for " << problem.getNumNodes() << " nodes, "
759 << problem.getNumEdges() << " edges.\n";
761 problem.printDot(std::cerr);
763 // We're done, PBQP problem constructed - return it.
767 void RegAllocPBQP::addStackInterval(const LiveInterval *spilled,
768 MachineRegisterInfo* mri) {
769 int stackSlot = vrm->getStackSlot(spilled->reg);
771 if (stackSlot == VirtRegMap::NO_STACK_SLOT)
774 const TargetRegisterClass *RC = mri->getRegClass(spilled->reg);
775 LiveInterval &stackInterval = lss->getOrCreateInterval(stackSlot, RC);
778 if (stackInterval.getNumValNums() != 0)
779 vni = stackInterval.getValNumInfo(0);
781 vni = stackInterval.getNextValue(
782 SlotIndex(), 0, false, lss->getVNInfoAllocator());
784 LiveInterval &rhsInterval = lis->getInterval(spilled->reg);
785 stackInterval.MergeRangesInAsValue(rhsInterval, vni);
788 bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQP::Solution &solution) {
790 // Set to true if we have any spills
791 bool anotherRoundNeeded = false;
793 // Clear the existing allocation.
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]);
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];
807 DEBUG(dbgs() << "VREG " << virtReg << " -> "
808 << tri->getName(physReg) << " (Option: " << allocSelection << ")\n");
810 assert(physReg != 0);
812 // Add to the virt reg map and update the used phys regs.
813 vrm->assignVirt2Phys(virtReg, physReg);
815 // ...Otherwise it's a spill.
818 // Make sure we ignore this virtual reg on the next round
820 vregsToAlloc.erase(virtReg);
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);
832 (void) oldSpillWeight;
833 DEBUG(dbgs() << "VREG " << virtReg << " -> SPILLED (Option: 0, Cost: "
834 << oldSpillWeight << ", New vregs: ");
836 // Copy any newly inserted live intervals into the list of regs to
838 for (std::vector<LiveInterval*>::const_iterator
839 itr = newSpills.begin(), end = newSpills.end();
842 assert(!(*itr)->empty() && "Empty spill range.");
844 DEBUG(dbgs() << (*itr)->reg << " ");
846 vregsToAlloc.insert((*itr)->reg);
849 DEBUG(dbgs() << ")\n");
851 // We need another round if spill intervals were added.
852 anotherRoundNeeded |= !newSpills.empty();
856 return !anotherRoundNeeded;
859 bool RegAllocPBQP::mapPBQPToRegAlloc2(const PBQPRAProblem &problem,
860 const PBQP::Solution &solution) {
861 // Set to true if we have any spills
862 bool anotherRoundNeeded = false;
864 // Clear the existing allocation.
867 const PBQP::Graph &g = problem.getGraph();
868 // Iterate over the nodes mapping the PBQP solution to a register
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);
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);
893 DEBUG(dbgs() << "VREG " << vreg << " -> SPILLED (Cost: "
894 << oldWeight << ", New vregs: ");
896 // Copy any newly inserted live intervals into the list of regs to
898 for (std::vector<LiveInterval*>::const_iterator
899 itr = newSpills.begin(), end = newSpills.end();
901 assert(!(*itr)->empty() && "Empty spill range.");
902 DEBUG(dbgs() << (*itr)->reg << " ");
903 vregsToAlloc.insert((*itr)->reg);
906 DEBUG(dbgs() << ")\n");
908 // We need another round if spill intervals were added.
909 anotherRoundNeeded |= !newSpills.empty();
911 assert(false && "Unknown allocation option.");
915 return !anotherRoundNeeded;
919 void RegAllocPBQP::finalizeAlloc() const {
920 typedef LiveIntervals::iterator LIIterator;
921 typedef LiveInterval::Ranges::const_iterator LRIterator;
923 // First allocate registers for the empty intervals.
924 for (RegSet::const_iterator
925 itr = emptyIntervalVRegs.begin(), end = emptyIntervalVRegs.end();
927 LiveInterval *li = &lis->getInterval(*itr);
929 unsigned physReg = vrm->getRegAllocPref(li->reg);
932 const TargetRegisterClass *liRC = mri->getRegClass(li->reg);
933 physReg = *liRC->allocation_order_begin(*mf);
936 vrm->assignVirt2Phys(li->reg, physReg);
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();
943 for (LIIterator liItr = lis->begin(), liEnd = lis->end();
944 liItr != liEnd; ++liItr) {
946 const LiveInterval *li = liItr->second;
949 // Get the physical register for this interval
950 if (TargetRegisterInfo::isPhysicalRegister(li->reg)) {
953 else if (vrm->isAssignedReg(li->reg)) {
954 reg = vrm->getPhys(li->reg);
957 // Ranges which are assigned a stack slot only are ignored.
962 // Filter out zero regs - they're for intervals that were spilled.
966 // Iterate over the ranges of the current interval...
967 for (LRIterator lrItr = li->begin(), lrEnd = li->end();
968 lrItr != lrEnd; ++lrItr) {
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);
987 bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) {
990 tm = &mf->getTarget();
991 tri = tm->getRegisterInfo();
992 tii = tm->getInstrInfo();
993 mri = &mf->getRegInfo();
995 lis = &getAnalysis<LiveIntervals>();
996 lss = &getAnalysis<LiveStacks>();
997 loopInfo = &getAnalysis<MachineLoopInfo>();
998 rmf = &getAnalysis<RenderMachineFunction>();
1000 vrm = &getAnalysis<VirtRegMap>();
1003 DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n");
1005 // Allocator main loop:
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
1012 // This process is continued till no more spills are generated.
1014 // Find the vreg intervals in need of allocation.
1015 findVRegIntervalsToAlloc();
1017 // If there are non-empty intervals allocate them using pbqp.
1018 if (!vregsToAlloc.empty()) {
1020 bool pbqpAllocComplete = false;
1024 while (!pbqpAllocComplete) {
1025 DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n");
1027 PBQP::Graph problem = constructPBQPProblem();
1028 PBQP::Solution solution =
1029 PBQP::HeuristicSolver<PBQP::Heuristics::Briggs>::solve(problem);
1031 pbqpAllocComplete = mapPBQPToRegAlloc(solution);
1036 while (!pbqpAllocComplete) {
1037 DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n");
1039 std::auto_ptr<PBQPRAProblem> problem =
1040 builder->build(mf, lis, vregsToAlloc);
1041 PBQP::Solution solution =
1042 HeuristicSolver<Briggs>::solve(problem->getGraph());
1044 pbqpAllocComplete = mapPBQPToRegAlloc2(*problem, solution);
1051 // Finalise allocation, allocate empty ranges.
1054 rmf->renderMachineFunction("After PBQP register allocation.", vrm);
1056 vregsToAlloc.clear();
1057 emptyIntervalVRegs.clear();
1060 allowedSets.clear();
1061 problemNodes.clear();
1063 DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm << "\n");
1066 std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
1068 rewriter->runOnMachineFunction(*mf, *vrm, lis);
1073 FunctionPass* createPBQPRegisterAllocator() {
1074 return new RegAllocPBQP(std::auto_ptr<PBQPBuilder>(new PBQPBuilder()));