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,
31 // Email: lhames@gmail.com
33 //===----------------------------------------------------------------------===//
35 #define DEBUG_TYPE "regalloc"
38 #include "VirtRegMap.h"
39 #include "llvm/CodeGen/MachineFunctionPass.h"
40 #include "llvm/CodeGen/RegAllocRegistry.h"
41 #include "llvm/CodeGen/RegisterCoalescer.h"
42 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
43 #include "llvm/CodeGen/LiveStackAnalysis.h"
44 #include "llvm/CodeGen/MachineRegisterInfo.h"
45 #include "llvm/CodeGen/MachineLoopInfo.h"
46 #include "llvm/Target/TargetMachine.h"
47 #include "llvm/Target/TargetInstrInfo.h"
48 #include "llvm/Support/Debug.h"
57 static RegisterRegAlloc
58 registerPBQPRepAlloc("pbqp", "PBQP register allocator",
59 createPBQPRegisterAllocator);
64 //! PBQP based allocators solve the register allocation problem by mapping
65 //! register allocation problems to Partitioned Boolean Quadratic
66 //! Programming problems.
67 class VISIBILITY_HIDDEN PBQPRegAlloc : public MachineFunctionPass {
72 //! Construct a PBQP register allocator.
73 PBQPRegAlloc() : MachineFunctionPass((intptr_t)&ID) {}
75 //! Return the pass name.
76 virtual const char* getPassName() const throw() {
77 return "PBQP Register Allocator";
80 //! PBQP analysis usage.
81 virtual void getAnalysisUsage(AnalysisUsage &au) const {
82 au.addRequired<LiveIntervals>();
83 au.addRequiredTransitive<RegisterCoalescer>();
84 au.addRequired<LiveStacks>();
85 au.addPreserved<LiveStacks>();
86 au.addRequired<MachineLoopInfo>();
87 au.addPreserved<MachineLoopInfo>();
88 MachineFunctionPass::getAnalysisUsage(au);
91 //! Perform register allocation
92 virtual bool runOnMachineFunction(MachineFunction &MF);
95 typedef std::map<const LiveInterval*, unsigned> LI2NodeMap;
96 typedef std::vector<const LiveInterval*> Node2LIMap;
97 typedef std::vector<unsigned> AllowedSet;
98 typedef std::vector<AllowedSet> AllowedSetMap;
99 typedef std::set<unsigned> RegSet;
100 typedef std::pair<unsigned, unsigned> RegPair;
101 typedef std::map<RegPair, PBQPNum> CoalesceMap;
103 typedef std::set<LiveInterval*> LiveIntervalSet;
106 const TargetMachine *tm;
107 const TargetRegisterInfo *tri;
108 const TargetInstrInfo *tii;
109 const MachineLoopInfo *loopInfo;
110 MachineRegisterInfo *mri;
118 AllowedSetMap allowedSets;
119 LiveIntervalSet vregIntervalsToAlloc,
123 //! Builds a PBQP cost vector.
124 template <typename RegContainer>
125 PBQPVector* buildCostVector(unsigned vReg,
126 const RegContainer &allowed,
127 const CoalesceMap &cealesces,
128 PBQPNum spillCost) const;
130 //! \brief Builds a PBQP interference matrix.
132 //! @return Either a pointer to a non-zero PBQP matrix representing the
133 //! allocation option costs, or a null pointer for a zero matrix.
135 //! Expects allowed sets for two interfering LiveIntervals. These allowed
136 //! sets should contain only allocable registers from the LiveInterval's
137 //! register class, with any interfering pre-colored registers removed.
138 template <typename RegContainer>
139 PBQPMatrix* buildInterferenceMatrix(const RegContainer &allowed1,
140 const RegContainer &allowed2) const;
143 //! Expects allowed sets for two potentially coalescable LiveIntervals,
144 //! and an estimated benefit due to coalescing. The allowed sets should
145 //! contain only allocable registers from the LiveInterval's register
146 //! classes, with any interfering pre-colored registers removed.
147 template <typename RegContainer>
148 PBQPMatrix* buildCoalescingMatrix(const RegContainer &allowed1,
149 const RegContainer &allowed2,
150 PBQPNum cBenefit) const;
152 //! \brief Finds coalescing opportunities and returns them as a map.
154 //! Any entries in the map are guaranteed coalescable, even if their
155 //! corresponding live intervals overlap.
156 CoalesceMap findCoalesces();
158 //! \brief Finds the initial set of vreg intervals to allocate.
159 void findVRegIntervalsToAlloc();
161 //! \brief Constructs a PBQP problem representation of the register
162 //! allocation problem for this function.
164 //! @return a PBQP solver object for the register allocation problem.
165 pbqp* constructPBQPProblem();
167 //! \brief Adds a stack interval if the given live interval has been
168 //! spilled. Used to support stack slot coloring.
169 void addStackInterval(const LiveInterval *spilled, float &weight);
171 //! \brief Given a solved PBQP problem maps this solution back to a register
173 bool mapPBQPToRegAlloc(pbqp *problem);
175 //! \brief Postprocessing before final spilling. Sets basic block "live in"
177 void finalizeAlloc() const;
181 char PBQPRegAlloc::ID = 0;
185 template <typename RegContainer>
186 PBQPVector* PBQPRegAlloc::buildCostVector(unsigned vReg,
187 const RegContainer &allowed,
188 const CoalesceMap &coalesces,
189 PBQPNum spillCost) const {
191 typedef typename RegContainer::const_iterator AllowedItr;
193 // Allocate vector. Additional element (0th) used for spill option
194 PBQPVector *v = new PBQPVector(allowed.size() + 1);
198 // Iterate over the allowed registers inserting coalesce benefits if there
201 for (AllowedItr itr = allowed.begin(), end = allowed.end();
202 itr != end; ++itr, ++ai) {
204 unsigned pReg = *itr;
206 CoalesceMap::const_iterator cmItr =
207 coalesces.find(RegPair(vReg, pReg));
209 // No coalesce - on to the next preg.
210 if (cmItr == coalesces.end())
213 // We have a coalesce - insert the benefit.
214 (*v)[ai + 1] = -cmItr->second;
220 template <typename RegContainer>
221 PBQPMatrix* PBQPRegAlloc::buildInterferenceMatrix(
222 const RegContainer &allowed1, const RegContainer &allowed2) const {
224 typedef typename RegContainer::const_iterator RegContainerIterator;
226 // Construct a PBQP matrix representing the cost of allocation options. The
227 // rows and columns correspond to the allocation options for the two live
228 // intervals. Elements will be infinite where corresponding registers alias,
229 // since we cannot allocate aliasing registers to interfering live intervals.
230 // All other elements (non-aliasing combinations) will have zero cost. Note
231 // that the spill option (element 0,0) has zero cost, since we can allocate
232 // both intervals to memory safely (the cost for each individual allocation
233 // to memory is accounted for by the cost vectors for each live interval).
234 PBQPMatrix *m = new PBQPMatrix(allowed1.size() + 1, allowed2.size() + 1);
236 // Assume this is a zero matrix until proven otherwise. Zero matrices occur
237 // between interfering live ranges with non-overlapping register sets (e.g.
238 // non-overlapping reg classes, or disjoint sets of allowed regs within the
239 // same class). The term "overlapping" is used advisedly: sets which do not
240 // intersect, but contain registers which alias, will have non-zero matrices.
241 // We optimize zero matrices away to improve solver speed.
242 bool isZeroMatrix = true;
245 // Row index. Starts at 1, since the 0th row is for the spill option, which
249 // Iterate over allowed sets, insert infinities where required.
250 for (RegContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end();
251 a1Itr != a1End; ++a1Itr) {
253 // Column index, starts at 1 as for row index.
255 unsigned reg1 = *a1Itr;
257 for (RegContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end();
258 a2Itr != a2End; ++a2Itr) {
260 unsigned reg2 = *a2Itr;
262 // If the row/column regs are identical or alias insert an infinity.
263 if ((reg1 == reg2) || tri->areAliases(reg1, reg2)) {
264 (*m)[ri][ci] = std::numeric_limits<PBQPNum>::infinity();
265 isZeroMatrix = false;
274 // If this turns out to be a zero matrix...
276 // free it and return null.
281 // ...otherwise return the cost matrix.
285 template <typename RegContainer>
286 PBQPMatrix* PBQPRegAlloc::buildCoalescingMatrix(
287 const RegContainer &allowed1, const RegContainer &allowed2,
288 PBQPNum cBenefit) const {
290 typedef typename RegContainer::const_iterator RegContainerIterator;
292 // Construct a PBQP Matrix representing the benefits of coalescing. As with
293 // interference matrices the rows and columns represent allowed registers
294 // for the LiveIntervals which are (potentially) to be coalesced. The amount
295 // -cBenefit will be placed in any element representing the same register
296 // for both intervals.
297 PBQPMatrix *m = new PBQPMatrix(allowed1.size() + 1, allowed2.size() + 1);
299 // Reset costs to zero.
302 // Assume the matrix is zero till proven otherwise. Zero matrices will be
303 // optimized away as in the interference case.
304 bool isZeroMatrix = true;
306 // Row index. Starts at 1, since the 0th row is for the spill option, which
310 // Iterate over the allowed sets, insert coalescing benefits where
312 for (RegContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end();
313 a1Itr != a1End; ++a1Itr) {
315 // Column index, starts at 1 as for row index.
317 unsigned reg1 = *a1Itr;
319 for (RegContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end();
320 a2Itr != a2End; ++a2Itr) {
322 // If the row and column represent the same register insert a beneficial
323 // cost to preference this allocation - it would allow us to eliminate a
325 if (reg1 == *a2Itr) {
326 (*m)[ri][ci] = -cBenefit;
327 isZeroMatrix = false;
336 // If this turns out to be a zero matrix...
338 // ...free it and return null.
346 PBQPRegAlloc::CoalesceMap PBQPRegAlloc::findCoalesces() {
348 typedef MachineFunction::const_iterator MFIterator;
349 typedef MachineBasicBlock::const_iterator MBBIterator;
350 typedef LiveInterval::const_vni_iterator VNIIterator;
352 CoalesceMap coalescesFound;
354 // To find coalesces we need to iterate over the function looking for
355 // copy instructions.
356 for (MFIterator bbItr = mf->begin(), bbEnd = mf->end();
357 bbItr != bbEnd; ++bbItr) {
359 const MachineBasicBlock *mbb = &*bbItr;
361 for (MBBIterator iItr = mbb->begin(), iEnd = mbb->end();
362 iItr != iEnd; ++iItr) {
364 const MachineInstr *instr = &*iItr;
365 unsigned srcReg, dstReg;
367 // If this isn't a copy then continue to the next instruction.
368 if (!tii->isMoveInstr(*instr, srcReg, dstReg))
371 // If the registers are already the same our job is nice and easy.
372 if (dstReg == srcReg)
375 bool srcRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(srcReg),
376 dstRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(dstReg);
378 // If both registers are physical then we can't coalesce.
379 if (srcRegIsPhysical && dstRegIsPhysical)
382 // If it's a copy that includes a virtual register but the source and
383 // destination classes differ then we can't coalesce, so continue with
384 // the next instruction.
385 const TargetRegisterClass *srcRegClass = srcRegIsPhysical ?
386 tri->getPhysicalRegisterRegClass(srcReg) : mri->getRegClass(srcReg);
388 const TargetRegisterClass *dstRegClass = dstRegIsPhysical ?
389 tri->getPhysicalRegisterRegClass(dstReg) : mri->getRegClass(dstReg);
391 if (srcRegClass != dstRegClass)
394 // We also need any physical regs to be allocable, coalescing with
395 // a non-allocable register is invalid.
396 if (srcRegIsPhysical) {
397 if (std::find(srcRegClass->allocation_order_begin(*mf),
398 srcRegClass->allocation_order_end(*mf), srcReg) ==
399 srcRegClass->allocation_order_end(*mf))
403 if (dstRegIsPhysical) {
404 if (std::find(dstRegClass->allocation_order_begin(*mf),
405 dstRegClass->allocation_order_end(*mf), dstReg) ==
406 dstRegClass->allocation_order_end(*mf))
410 // If we've made it here we have a copy with compatible register classes.
411 // We can probably coalesce, but we need to consider overlap.
412 const LiveInterval *srcLI = &lis->getInterval(srcReg),
413 *dstLI = &lis->getInterval(dstReg);
415 if (srcLI->overlaps(*dstLI)) {
416 // Even in the case of an overlap we might still be able to coalesce,
417 // but we need to make sure that no definition of either range occurs
418 // while the other range is live.
420 // Otherwise start by assuming we're ok.
423 // Test all defs of the source range.
425 vniItr = srcLI->vni_begin(), vniEnd = srcLI->vni_end();
426 vniItr != vniEnd; ++vniItr) {
428 // If we find a def that kills the coalescing opportunity then
429 // record it and break from the loop.
430 if (dstLI->liveAt((*vniItr)->def)) {
436 // If we have a bad def give up, continue to the next instruction.
440 // Otherwise test definitions of the destination range.
442 vniItr = dstLI->vni_begin(), vniEnd = dstLI->vni_end();
443 vniItr != vniEnd; ++vniItr) {
445 // We want to make sure we skip the copy instruction itself.
446 if ((*vniItr)->copy == instr)
449 if (srcLI->liveAt((*vniItr)->def)) {
455 // As before a bad def we give up and continue to the next instr.
460 // If we make it to here then either the ranges didn't overlap, or they
461 // did, but none of their definitions would prevent us from coalescing.
462 // We're good to go with the coalesce.
464 float cBenefit = powf(10.0f, loopInfo->getLoopDepth(mbb)) / 5.0;
466 coalescesFound[RegPair(srcReg, dstReg)] = cBenefit;
467 coalescesFound[RegPair(dstReg, srcReg)] = cBenefit;
472 return coalescesFound;
475 void PBQPRegAlloc::findVRegIntervalsToAlloc() {
477 // Iterate over all live ranges.
478 for (LiveIntervals::iterator itr = lis->begin(), end = lis->end();
481 // Ignore physical ones.
482 if (TargetRegisterInfo::isPhysicalRegister(itr->first))
485 LiveInterval *li = itr->second;
487 // If this live interval is non-empty we will use pbqp to allocate it.
488 // Empty intervals we allocate in a simple post-processing stage in
491 vregIntervalsToAlloc.insert(li);
494 emptyVRegIntervals.insert(li);
499 pbqp* PBQPRegAlloc::constructPBQPProblem() {
501 typedef std::vector<const LiveInterval*> LIVector;
502 typedef std::vector<unsigned> RegVector;
504 // This will store the physical intervals for easy reference.
505 LIVector physIntervals;
507 // Start by clearing the old node <-> live interval mappings & allowed sets
512 // Populate physIntervals, update preg use:
513 for (LiveIntervals::iterator itr = lis->begin(), end = lis->end();
516 if (TargetRegisterInfo::isPhysicalRegister(itr->first)) {
517 physIntervals.push_back(itr->second);
518 mri->setPhysRegUsed(itr->second->reg);
522 // Iterate over vreg intervals, construct live interval <-> node number
524 for (LiveIntervalSet::const_iterator
525 itr = vregIntervalsToAlloc.begin(), end = vregIntervalsToAlloc.end();
527 const LiveInterval *li = *itr;
529 li2Node[li] = node2LI.size();
530 node2LI.push_back(li);
533 // Get the set of potential coalesces.
534 CoalesceMap coalesces(findCoalesces());
536 // Construct a PBQP solver for this problem
537 pbqp *solver = alloc_pbqp(vregIntervalsToAlloc.size());
539 // Resize allowedSets container appropriately.
540 allowedSets.resize(vregIntervalsToAlloc.size());
542 // Iterate over virtual register intervals to compute allowed sets...
543 for (unsigned node = 0; node < node2LI.size(); ++node) {
545 // Grab pointers to the interval and its register class.
546 const LiveInterval *li = node2LI[node];
547 const TargetRegisterClass *liRC = mri->getRegClass(li->reg);
549 // Start by assuming all allocable registers in the class are allowed...
550 RegVector liAllowed(liRC->allocation_order_begin(*mf),
551 liRC->allocation_order_end(*mf));
553 // Eliminate the physical registers which overlap with this range, along
554 // with all their aliases.
555 for (LIVector::iterator pItr = physIntervals.begin(),
556 pEnd = physIntervals.end(); pItr != pEnd; ++pItr) {
558 if (!li->overlaps(**pItr))
561 unsigned pReg = (*pItr)->reg;
563 // If we get here then the live intervals overlap, but we're still ok
564 // if they're coalescable.
565 if (coalesces.find(RegPair(li->reg, pReg)) != coalesces.end())
568 // If we get here then we have a genuine exclusion.
570 // Remove the overlapping reg...
571 RegVector::iterator eraseItr =
572 std::find(liAllowed.begin(), liAllowed.end(), pReg);
574 if (eraseItr != liAllowed.end())
575 liAllowed.erase(eraseItr);
577 const unsigned *aliasItr = tri->getAliasSet(pReg);
580 // ...and its aliases.
581 for (; *aliasItr != 0; ++aliasItr) {
582 RegVector::iterator eraseItr =
583 std::find(liAllowed.begin(), liAllowed.end(), *aliasItr);
585 if (eraseItr != liAllowed.end()) {
586 liAllowed.erase(eraseItr);
592 // Copy the allowed set into a member vector for use when constructing cost
593 // vectors & matrices, and mapping PBQP solutions back to assignments.
594 allowedSets[node] = AllowedSet(liAllowed.begin(), liAllowed.end());
596 // Set the spill cost to the interval weight, or epsilon if the
597 // interval weight is zero
598 PBQPNum spillCost = (li->weight != 0.0) ?
599 li->weight : std::numeric_limits<PBQPNum>::min();
601 // Build a cost vector for this interval.
602 add_pbqp_nodecosts(solver, node,
603 buildCostVector(li->reg, allowedSets[node], coalesces,
609 // Now add the cost matrices...
610 for (unsigned node1 = 0; node1 < node2LI.size(); ++node1) {
611 const LiveInterval *li = node2LI[node1];
613 // Test for live range overlaps and insert interference matrices.
614 for (unsigned node2 = node1 + 1; node2 < node2LI.size(); ++node2) {
615 const LiveInterval *li2 = node2LI[node2];
617 CoalesceMap::const_iterator cmItr =
618 coalesces.find(RegPair(li->reg, li2->reg));
622 if (cmItr != coalesces.end()) {
623 m = buildCoalescingMatrix(allowedSets[node1], allowedSets[node2],
626 else if (li->overlaps(*li2)) {
627 m = buildInterferenceMatrix(allowedSets[node1], allowedSets[node2]);
631 add_pbqp_edgecosts(solver, node1, node2, m);
637 // We're done, PBQP problem constructed - return it.
641 void PBQPRegAlloc::addStackInterval(const LiveInterval *spilled, float &weight) {
642 int stackSlot = vrm->getStackSlot(spilled->reg);
644 if (stackSlot == VirtRegMap::NO_STACK_SLOT)
647 LiveInterval &stackInterval = lss->getOrCreateInterval(stackSlot);
648 stackInterval.weight += weight;
651 if (stackInterval.getNumValNums() != 0)
652 vni = stackInterval.getValNumInfo(0);
654 vni = stackInterval.getNextValue(-0U, 0, lss->getVNInfoAllocator());
656 LiveInterval &rhsInterval = lis->getInterval(spilled->reg);
657 stackInterval.MergeRangesInAsValue(rhsInterval, vni);
660 bool PBQPRegAlloc::mapPBQPToRegAlloc(pbqp *problem) {
662 // Set to true if we have any spills
663 bool anotherRoundNeeded = false;
665 // Clear the existing allocation.
668 // Iterate over the nodes mapping the PBQP solution to a register assignment.
669 for (unsigned node = 0; node < node2LI.size(); ++node) {
670 unsigned virtReg = node2LI[node]->reg,
671 allocSelection = get_pbqp_solution(problem, node);
673 // If the PBQP solution is non-zero it's a physical register...
674 if (allocSelection != 0) {
675 // Get the physical reg, subtracting 1 to account for the spill option.
676 unsigned physReg = allowedSets[node][allocSelection - 1];
678 DOUT << "VREG " << virtReg << " -> " << tri->getName(physReg) << "\n";
680 assert(physReg != 0);
682 // Add to the virt reg map and update the used phys regs.
683 vrm->assignVirt2Phys(virtReg, physReg);
685 // ...Otherwise it's a spill.
688 // Make sure we ignore this virtual reg on the next round
690 vregIntervalsToAlloc.erase(&lis->getInterval(virtReg));
694 // Insert spill ranges for this live range
695 const LiveInterval *spillInterval = node2LI[node];
696 double oldSpillWeight = spillInterval->weight;
697 SmallVector<LiveInterval*, 8> spillIs;
698 std::vector<LiveInterval*> newSpills =
699 lis->addIntervalsForSpills(*spillInterval, spillIs, loopInfo, *vrm,
701 addStackInterval(spillInterval, ssWeight);
703 DOUT << "VREG " << virtReg << " -> SPILLED (Cost: "
704 << oldSpillWeight << ", New vregs: ";
706 // Copy any newly inserted live intervals into the list of regs to
708 for (std::vector<LiveInterval*>::const_iterator
709 itr = newSpills.begin(), end = newSpills.end();
712 assert(!(*itr)->empty() && "Empty spill range.");
714 DOUT << (*itr)->reg << " ";
716 vregIntervalsToAlloc.insert(*itr);
721 // We need another round if spill intervals were added.
722 anotherRoundNeeded |= !newSpills.empty();
726 return !anotherRoundNeeded;
729 void PBQPRegAlloc::finalizeAlloc() const {
730 typedef LiveIntervals::iterator LIIterator;
731 typedef LiveInterval::Ranges::const_iterator LRIterator;
733 // First allocate registers for the empty intervals.
734 for (LiveIntervalSet::iterator
735 itr = emptyVRegIntervals.begin(), end = emptyVRegIntervals.end();
737 LiveInterval *li = *itr;
739 unsigned physReg = li->preference;
742 const TargetRegisterClass *liRC = mri->getRegClass(li->reg);
743 physReg = *liRC->allocation_order_begin(*mf);
746 vrm->assignVirt2Phys(li->reg, physReg);
749 // Finally iterate over the basic blocks to compute and set the live-in sets.
750 SmallVector<MachineBasicBlock*, 8> liveInMBBs;
751 MachineBasicBlock *entryMBB = &*mf->begin();
753 for (LIIterator liItr = lis->begin(), liEnd = lis->end();
754 liItr != liEnd; ++liItr) {
756 const LiveInterval *li = liItr->second;
759 // Get the physical register for this interval
760 if (TargetRegisterInfo::isPhysicalRegister(li->reg)) {
763 else if (vrm->isAssignedReg(li->reg)) {
764 reg = vrm->getPhys(li->reg);
767 // Ranges which are assigned a stack slot only are ignored.
771 // Iterate over the ranges of the current interval...
772 for (LRIterator lrItr = li->begin(), lrEnd = li->end();
773 lrItr != lrEnd; ++lrItr) {
775 // Find the set of basic blocks which this range is live into...
776 if (lis->findLiveInMBBs(lrItr->start, lrItr->end, liveInMBBs)) {
777 // And add the physreg for this interval to their live-in sets.
778 for (unsigned i = 0; i < liveInMBBs.size(); ++i) {
779 if (liveInMBBs[i] != entryMBB) {
780 if (!liveInMBBs[i]->isLiveIn(reg)) {
781 liveInMBBs[i]->addLiveIn(reg);
792 bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) {
795 tm = &mf->getTarget();
796 tri = tm->getRegisterInfo();
797 tii = tm->getInstrInfo();
798 mri = &mf->getRegInfo();
800 lis = &getAnalysis<LiveIntervals>();
801 lss = &getAnalysis<LiveStacks>();
802 loopInfo = &getAnalysis<MachineLoopInfo>();
804 std::auto_ptr<VirtRegMap> vrmAutoPtr(new VirtRegMap(*mf));
805 vrm = vrmAutoPtr.get();
807 DOUT << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n";
809 // Allocator main loop:
811 // * Map current regalloc problem to a PBQP problem
812 // * Solve the PBQP problem
813 // * Map the solution back to a register allocation
814 // * Spill if necessary
816 // This process is continued till no more spills are generated.
818 // Find the vreg intervals in need of allocation.
819 findVRegIntervalsToAlloc();
821 // If there aren't any then we're done here.
822 if (vregIntervalsToAlloc.empty() && emptyVRegIntervals.empty())
825 // If there are non-empty intervals allocate them using pbqp.
826 if (!vregIntervalsToAlloc.empty()) {
828 bool pbqpAllocComplete = false;
831 while (!pbqpAllocComplete) {
832 DOUT << " PBQP Regalloc round " << round << ":\n";
834 pbqp *problem = constructPBQPProblem();
838 pbqpAllocComplete = mapPBQPToRegAlloc(problem);
846 // Finalise allocation, allocate empty ranges.
849 vregIntervalsToAlloc.clear();
850 emptyVRegIntervals.clear();
855 DOUT << "Post alloc VirtRegMap:\n" << *vrm << "\n";
858 std::auto_ptr<Spiller> spiller(createSpiller());
859 spiller->runOnMachineFunction(*mf, *vrm);
864 FunctionPass* llvm::createPBQPRegisterAllocator() {
865 return new PBQPRegAlloc();