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 "PBQP/HeuristicSolver.h"
35 #include "PBQP/Graph.h"
36 #include "PBQP/Heuristics/Briggs.h"
37 #include "VirtRegMap.h"
38 #include "VirtRegRewriter.h"
39 #include "llvm/CodeGen/CalcSpillWeights.h"
40 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
41 #include "llvm/CodeGen/LiveStackAnalysis.h"
42 #include "llvm/CodeGen/MachineFunctionPass.h"
43 #include "llvm/CodeGen/MachineLoopInfo.h"
44 #include "llvm/CodeGen/MachineRegisterInfo.h"
45 #include "llvm/CodeGen/RegAllocRegistry.h"
46 #include "llvm/CodeGen/RegisterCoalescer.h"
47 #include "llvm/Support/Debug.h"
48 #include "llvm/Support/raw_ostream.h"
49 #include "llvm/Target/TargetInstrInfo.h"
50 #include "llvm/Target/TargetMachine.h"
59 static RegisterRegAlloc
60 registerPBQPRepAlloc("pbqp", "PBQP register allocator",
61 llvm::createPBQPRegisterAllocator
);
64 pbqpCoalescing("pbqp-coalescing",
65 cl::desc("Attempt coalescing during PBQP register allocation."),
66 cl::init(false), cl::Hidden
);
71 /// PBQP based allocators solve the register allocation problem by mapping
72 /// register allocation problems to Partitioned Boolean Quadratic
73 /// Programming problems.
74 class PBQPRegAlloc
: public MachineFunctionPass
{
79 /// Construct a PBQP register allocator.
80 PBQPRegAlloc() : MachineFunctionPass(&ID
) {}
82 /// Return the pass name.
83 virtual const char* getPassName() const {
84 return "PBQP Register Allocator";
87 /// PBQP analysis usage.
88 virtual void getAnalysisUsage(AnalysisUsage
&au
) const {
89 au
.addRequired
<SlotIndexes
>();
90 au
.addPreserved
<SlotIndexes
>();
91 au
.addRequired
<LiveIntervals
>();
92 //au.addRequiredID(SplitCriticalEdgesID);
93 au
.addRequired
<RegisterCoalescer
>();
94 au
.addRequired
<CalculateSpillWeights
>();
95 au
.addRequired
<LiveStacks
>();
96 au
.addPreserved
<LiveStacks
>();
97 au
.addRequired
<MachineLoopInfo
>();
98 au
.addPreserved
<MachineLoopInfo
>();
99 au
.addRequired
<VirtRegMap
>();
100 MachineFunctionPass::getAnalysisUsage(au
);
103 /// Perform register allocation
104 virtual bool runOnMachineFunction(MachineFunction
&MF
);
107 typedef std::map
<const LiveInterval
*, unsigned> LI2NodeMap
;
108 typedef std::vector
<const LiveInterval
*> Node2LIMap
;
109 typedef std::vector
<unsigned> AllowedSet
;
110 typedef std::vector
<AllowedSet
> AllowedSetMap
;
111 typedef std::set
<unsigned> RegSet
;
112 typedef std::pair
<unsigned, unsigned> RegPair
;
113 typedef std::map
<RegPair
, PBQP::PBQPNum
> CoalesceMap
;
115 typedef std::set
<LiveInterval
*> LiveIntervalSet
;
117 typedef std::vector
<PBQP::Graph::NodeItr
> NodeVector
;
120 const TargetMachine
*tm
;
121 const TargetRegisterInfo
*tri
;
122 const TargetInstrInfo
*tii
;
123 const MachineLoopInfo
*loopInfo
;
124 MachineRegisterInfo
*mri
;
132 AllowedSetMap allowedSets
;
133 LiveIntervalSet vregIntervalsToAlloc
,
135 NodeVector problemNodes
;
138 /// Builds a PBQP cost vector.
139 template <typename RegContainer
>
140 PBQP::Vector
buildCostVector(unsigned vReg
,
141 const RegContainer
&allowed
,
142 const CoalesceMap
&cealesces
,
143 PBQP::PBQPNum spillCost
) const;
145 /// \brief Builds a PBQP interference matrix.
147 /// @return Either a pointer to a non-zero PBQP matrix representing the
148 /// allocation option costs, or a null pointer for a zero matrix.
150 /// Expects allowed sets for two interfering LiveIntervals. These allowed
151 /// sets should contain only allocable registers from the LiveInterval's
152 /// register class, with any interfering pre-colored registers removed.
153 template <typename RegContainer
>
154 PBQP::Matrix
* buildInterferenceMatrix(const RegContainer
&allowed1
,
155 const RegContainer
&allowed2
) const;
158 /// Expects allowed sets for two potentially coalescable LiveIntervals,
159 /// and an estimated benefit due to coalescing. The allowed sets should
160 /// contain only allocable registers from the LiveInterval's register
161 /// classes, with any interfering pre-colored registers removed.
162 template <typename RegContainer
>
163 PBQP::Matrix
* buildCoalescingMatrix(const RegContainer
&allowed1
,
164 const RegContainer
&allowed2
,
165 PBQP::PBQPNum cBenefit
) const;
167 /// \brief Finds coalescing opportunities and returns them as a map.
169 /// Any entries in the map are guaranteed coalescable, even if their
170 /// corresponding live intervals overlap.
171 CoalesceMap
findCoalesces();
173 /// \brief Finds the initial set of vreg intervals to allocate.
174 void findVRegIntervalsToAlloc();
176 /// \brief Constructs a PBQP problem representation of the register
177 /// allocation problem for this function.
179 /// @return a PBQP solver object for the register allocation problem.
180 PBQP::Graph
constructPBQPProblem();
182 /// \brief Adds a stack interval if the given live interval has been
183 /// spilled. Used to support stack slot coloring.
184 void addStackInterval(const LiveInterval
*spilled
,MachineRegisterInfo
* mri
);
186 /// \brief Given a solved PBQP problem maps this solution back to a register
188 bool mapPBQPToRegAlloc(const PBQP::Solution
&solution
);
190 /// \brief Postprocessing before final spilling. Sets basic block "live in"
192 void finalizeAlloc() const;
196 char PBQPRegAlloc::ID
= 0;
200 template <typename RegContainer
>
201 PBQP::Vector
PBQPRegAlloc::buildCostVector(unsigned vReg
,
202 const RegContainer
&allowed
,
203 const CoalesceMap
&coalesces
,
204 PBQP::PBQPNum spillCost
) const {
206 typedef typename
RegContainer::const_iterator AllowedItr
;
208 // Allocate vector. Additional element (0th) used for spill option
209 PBQP::Vector
v(allowed
.size() + 1, 0);
213 // Iterate over the allowed registers inserting coalesce benefits if there
216 for (AllowedItr itr
= allowed
.begin(), end
= allowed
.end();
217 itr
!= end
; ++itr
, ++ai
) {
219 unsigned pReg
= *itr
;
221 CoalesceMap::const_iterator cmItr
=
222 coalesces
.find(RegPair(vReg
, pReg
));
224 // No coalesce - on to the next preg.
225 if (cmItr
== coalesces
.end())
228 // We have a coalesce - insert the benefit.
229 v
[ai
+ 1] = -cmItr
->second
;
235 template <typename RegContainer
>
236 PBQP::Matrix
* PBQPRegAlloc::buildInterferenceMatrix(
237 const RegContainer
&allowed1
, const RegContainer
&allowed2
) const {
239 typedef typename
RegContainer::const_iterator RegContainerIterator
;
241 // Construct a PBQP matrix representing the cost of allocation options. The
242 // rows and columns correspond to the allocation options for the two live
243 // intervals. Elements will be infinite where corresponding registers alias,
244 // since we cannot allocate aliasing registers to interfering live intervals.
245 // All other elements (non-aliasing combinations) will have zero cost. Note
246 // that the spill option (element 0,0) has zero cost, since we can allocate
247 // both intervals to memory safely (the cost for each individual allocation
248 // to memory is accounted for by the cost vectors for each live interval).
250 new PBQP::Matrix(allowed1
.size() + 1, allowed2
.size() + 1, 0);
252 // Assume this is a zero matrix until proven otherwise. Zero matrices occur
253 // between interfering live ranges with non-overlapping register sets (e.g.
254 // non-overlapping reg classes, or disjoint sets of allowed regs within the
255 // same class). The term "overlapping" is used advisedly: sets which do not
256 // intersect, but contain registers which alias, will have non-zero matrices.
257 // We optimize zero matrices away to improve solver speed.
258 bool isZeroMatrix
= true;
261 // Row index. Starts at 1, since the 0th row is for the spill option, which
265 // Iterate over allowed sets, insert infinities where required.
266 for (RegContainerIterator a1Itr
= allowed1
.begin(), a1End
= allowed1
.end();
267 a1Itr
!= a1End
; ++a1Itr
) {
269 // Column index, starts at 1 as for row index.
271 unsigned reg1
= *a1Itr
;
273 for (RegContainerIterator a2Itr
= allowed2
.begin(), a2End
= allowed2
.end();
274 a2Itr
!= a2End
; ++a2Itr
) {
276 unsigned reg2
= *a2Itr
;
278 // If the row/column regs are identical or alias insert an infinity.
279 if (tri
->regsOverlap(reg1
, reg2
)) {
280 (*m
)[ri
][ci
] = std::numeric_limits
<PBQP::PBQPNum
>::infinity();
281 isZeroMatrix
= false;
290 // If this turns out to be a zero matrix...
292 // free it and return null.
297 // ...otherwise return the cost matrix.
301 template <typename RegContainer
>
302 PBQP::Matrix
* PBQPRegAlloc::buildCoalescingMatrix(
303 const RegContainer
&allowed1
, const RegContainer
&allowed2
,
304 PBQP::PBQPNum cBenefit
) const {
306 typedef typename
RegContainer::const_iterator RegContainerIterator
;
308 // Construct a PBQP Matrix representing the benefits of coalescing. As with
309 // interference matrices the rows and columns represent allowed registers
310 // for the LiveIntervals which are (potentially) to be coalesced. The amount
311 // -cBenefit will be placed in any element representing the same register
312 // for both intervals.
314 new PBQP::Matrix(allowed1
.size() + 1, allowed2
.size() + 1, 0);
316 // Reset costs to zero.
319 // Assume the matrix is zero till proven otherwise. Zero matrices will be
320 // optimized away as in the interference case.
321 bool isZeroMatrix
= true;
323 // Row index. Starts at 1, since the 0th row is for the spill option, which
327 // Iterate over the allowed sets, insert coalescing benefits where
329 for (RegContainerIterator a1Itr
= allowed1
.begin(), a1End
= allowed1
.end();
330 a1Itr
!= a1End
; ++a1Itr
) {
332 // Column index, starts at 1 as for row index.
334 unsigned reg1
= *a1Itr
;
336 for (RegContainerIterator a2Itr
= allowed2
.begin(), a2End
= allowed2
.end();
337 a2Itr
!= a2End
; ++a2Itr
) {
339 // If the row and column represent the same register insert a beneficial
340 // cost to preference this allocation - it would allow us to eliminate a
342 if (reg1
== *a2Itr
) {
343 (*m
)[ri
][ci
] = -cBenefit
;
344 isZeroMatrix
= false;
353 // If this turns out to be a zero matrix...
355 // ...free it and return null.
363 PBQPRegAlloc::CoalesceMap
PBQPRegAlloc::findCoalesces() {
365 typedef MachineFunction::const_iterator MFIterator
;
366 typedef MachineBasicBlock::const_iterator MBBIterator
;
367 typedef LiveInterval::const_vni_iterator VNIIterator
;
369 CoalesceMap coalescesFound
;
371 // To find coalesces we need to iterate over the function looking for
372 // copy instructions.
373 for (MFIterator bbItr
= mf
->begin(), bbEnd
= mf
->end();
374 bbItr
!= bbEnd
; ++bbItr
) {
376 const MachineBasicBlock
*mbb
= &*bbItr
;
378 for (MBBIterator iItr
= mbb
->begin(), iEnd
= mbb
->end();
379 iItr
!= iEnd
; ++iItr
) {
381 const MachineInstr
*instr
= &*iItr
;
382 unsigned srcReg
, dstReg
, srcSubReg
, dstSubReg
;
384 // If this isn't a copy then continue to the next instruction.
385 if (!tii
->isMoveInstr(*instr
, srcReg
, dstReg
, srcSubReg
, dstSubReg
))
388 // If the registers are already the same our job is nice and easy.
389 if (dstReg
== srcReg
)
392 bool srcRegIsPhysical
= TargetRegisterInfo::isPhysicalRegister(srcReg
),
393 dstRegIsPhysical
= TargetRegisterInfo::isPhysicalRegister(dstReg
);
395 // If both registers are physical then we can't coalesce.
396 if (srcRegIsPhysical
&& dstRegIsPhysical
)
399 // If it's a copy that includes a virtual register but the source and
400 // destination classes differ then we can't coalesce, so continue with
401 // the next instruction.
402 const TargetRegisterClass
*srcRegClass
= srcRegIsPhysical
?
403 tri
->getPhysicalRegisterRegClass(srcReg
) : mri
->getRegClass(srcReg
);
405 const TargetRegisterClass
*dstRegClass
= dstRegIsPhysical
?
406 tri
->getPhysicalRegisterRegClass(dstReg
) : mri
->getRegClass(dstReg
);
408 if (srcRegClass
!= dstRegClass
)
411 // We also need any physical regs to be allocable, coalescing with
412 // a non-allocable register is invalid.
413 if (srcRegIsPhysical
) {
414 if (std::find(dstRegClass
->allocation_order_begin(*mf
),
415 dstRegClass
->allocation_order_end(*mf
), srcReg
) ==
416 dstRegClass
->allocation_order_end(*mf
))
420 if (dstRegIsPhysical
) {
421 if (std::find(srcRegClass
->allocation_order_begin(*mf
),
422 srcRegClass
->allocation_order_end(*mf
), dstReg
) ==
423 srcRegClass
->allocation_order_end(*mf
))
427 // If we've made it here we have a copy with compatible register classes.
428 // We can probably coalesce, but we need to consider overlap.
429 const LiveInterval
*srcLI
= &lis
->getInterval(srcReg
),
430 *dstLI
= &lis
->getInterval(dstReg
);
432 if (srcLI
->overlaps(*dstLI
)) {
433 // Even in the case of an overlap we might still be able to coalesce,
434 // but we need to make sure that no definition of either range occurs
435 // while the other range is live.
437 // Otherwise start by assuming we're ok.
440 // Test all defs of the source range.
442 vniItr
= srcLI
->vni_begin(), vniEnd
= srcLI
->vni_end();
443 vniItr
!= vniEnd
; ++vniItr
) {
445 // If we find a poorly defined def we err on the side of caution.
446 if (!(*vniItr
)->def
.isValid()) {
451 // If we find a def that kills the coalescing opportunity then
452 // record it and break from the loop.
453 if (dstLI
->liveAt((*vniItr
)->def
)) {
459 // If we have a bad def give up, continue to the next instruction.
463 // Otherwise test definitions of the destination range.
465 vniItr
= dstLI
->vni_begin(), vniEnd
= dstLI
->vni_end();
466 vniItr
!= vniEnd
; ++vniItr
) {
468 // We want to make sure we skip the copy instruction itself.
469 if ((*vniItr
)->getCopy() == instr
)
472 if (!(*vniItr
)->def
.isValid()) {
477 if (srcLI
->liveAt((*vniItr
)->def
)) {
483 // As before a bad def we give up and continue to the next instr.
488 // If we make it to here then either the ranges didn't overlap, or they
489 // did, but none of their definitions would prevent us from coalescing.
490 // We're good to go with the coalesce.
492 float cBenefit
= std::pow(10.0f
, (float)loopInfo
->getLoopDepth(mbb
)) / 5.0;
494 coalescesFound
[RegPair(srcReg
, dstReg
)] = cBenefit
;
495 coalescesFound
[RegPair(dstReg
, srcReg
)] = cBenefit
;
500 return coalescesFound
;
503 void PBQPRegAlloc::findVRegIntervalsToAlloc() {
505 // Iterate over all live ranges.
506 for (LiveIntervals::iterator itr
= lis
->begin(), end
= lis
->end();
509 // Ignore physical ones.
510 if (TargetRegisterInfo::isPhysicalRegister(itr
->first
))
513 LiveInterval
*li
= itr
->second
;
515 // If this live interval is non-empty we will use pbqp to allocate it.
516 // Empty intervals we allocate in a simple post-processing stage in
519 vregIntervalsToAlloc
.insert(li
);
522 emptyVRegIntervals
.insert(li
);
527 PBQP::Graph
PBQPRegAlloc::constructPBQPProblem() {
529 typedef std::vector
<const LiveInterval
*> LIVector
;
530 typedef std::vector
<unsigned> RegVector
;
532 // This will store the physical intervals for easy reference.
533 LIVector physIntervals
;
535 // Start by clearing the old node <-> live interval mappings & allowed sets
540 // Populate physIntervals, update preg use:
541 for (LiveIntervals::iterator itr
= lis
->begin(), end
= lis
->end();
544 if (TargetRegisterInfo::isPhysicalRegister(itr
->first
)) {
545 physIntervals
.push_back(itr
->second
);
546 mri
->setPhysRegUsed(itr
->second
->reg
);
550 // Iterate over vreg intervals, construct live interval <-> node number
552 for (LiveIntervalSet::const_iterator
553 itr
= vregIntervalsToAlloc
.begin(), end
= vregIntervalsToAlloc
.end();
555 const LiveInterval
*li
= *itr
;
557 li2Node
[li
] = node2LI
.size();
558 node2LI
.push_back(li
);
561 // Get the set of potential coalesces.
562 CoalesceMap coalesces
;
564 if (pbqpCoalescing
) {
565 coalesces
= findCoalesces();
568 // Construct a PBQP solver for this problem
570 problemNodes
.resize(vregIntervalsToAlloc
.size());
572 // Resize allowedSets container appropriately.
573 allowedSets
.resize(vregIntervalsToAlloc
.size());
575 // Iterate over virtual register intervals to compute allowed sets...
576 for (unsigned node
= 0; node
< node2LI
.size(); ++node
) {
578 // Grab pointers to the interval and its register class.
579 const LiveInterval
*li
= node2LI
[node
];
580 const TargetRegisterClass
*liRC
= mri
->getRegClass(li
->reg
);
582 // Start by assuming all allocable registers in the class are allowed...
583 RegVector
liAllowed(liRC
->allocation_order_begin(*mf
),
584 liRC
->allocation_order_end(*mf
));
586 // Eliminate the physical registers which overlap with this range, along
587 // with all their aliases.
588 for (LIVector::iterator pItr
= physIntervals
.begin(),
589 pEnd
= physIntervals
.end(); pItr
!= pEnd
; ++pItr
) {
591 if (!li
->overlaps(**pItr
))
594 unsigned pReg
= (*pItr
)->reg
;
596 // If we get here then the live intervals overlap, but we're still ok
597 // if they're coalescable.
598 if (coalesces
.find(RegPair(li
->reg
, pReg
)) != coalesces
.end())
601 // If we get here then we have a genuine exclusion.
603 // Remove the overlapping reg...
604 RegVector::iterator eraseItr
=
605 std::find(liAllowed
.begin(), liAllowed
.end(), pReg
);
607 if (eraseItr
!= liAllowed
.end())
608 liAllowed
.erase(eraseItr
);
610 const unsigned *aliasItr
= tri
->getAliasSet(pReg
);
613 // ...and its aliases.
614 for (; *aliasItr
!= 0; ++aliasItr
) {
615 RegVector::iterator eraseItr
=
616 std::find(liAllowed
.begin(), liAllowed
.end(), *aliasItr
);
618 if (eraseItr
!= liAllowed
.end()) {
619 liAllowed
.erase(eraseItr
);
625 // Copy the allowed set into a member vector for use when constructing cost
626 // vectors & matrices, and mapping PBQP solutions back to assignments.
627 allowedSets
[node
] = AllowedSet(liAllowed
.begin(), liAllowed
.end());
629 // Set the spill cost to the interval weight, or epsilon if the
630 // interval weight is zero
631 PBQP::PBQPNum spillCost
= (li
->weight
!= 0.0) ?
632 li
->weight
: std::numeric_limits
<PBQP::PBQPNum
>::min();
634 // Build a cost vector for this interval.
637 buildCostVector(li
->reg
, allowedSets
[node
], coalesces
, spillCost
));
642 // Now add the cost matrices...
643 for (unsigned node1
= 0; node1
< node2LI
.size(); ++node1
) {
644 const LiveInterval
*li
= node2LI
[node1
];
646 // Test for live range overlaps and insert interference matrices.
647 for (unsigned node2
= node1
+ 1; node2
< node2LI
.size(); ++node2
) {
648 const LiveInterval
*li2
= node2LI
[node2
];
650 CoalesceMap::const_iterator cmItr
=
651 coalesces
.find(RegPair(li
->reg
, li2
->reg
));
655 if (cmItr
!= coalesces
.end()) {
656 m
= buildCoalescingMatrix(allowedSets
[node1
], allowedSets
[node2
],
659 else if (li
->overlaps(*li2
)) {
660 m
= buildInterferenceMatrix(allowedSets
[node1
], allowedSets
[node2
]);
664 problem
.addEdge(problemNodes
[node1
],
673 assert(problem
.getNumNodes() == allowedSets
.size());
675 std::cerr << "Allocating for " << problem.getNumNodes() << " nodes, "
676 << problem.getNumEdges() << " edges.\n";
678 problem.printDot(std::cerr);
680 // We're done, PBQP problem constructed - return it.
684 void PBQPRegAlloc::addStackInterval(const LiveInterval
*spilled
,
685 MachineRegisterInfo
* mri
) {
686 int stackSlot
= vrm
->getStackSlot(spilled
->reg
);
688 if (stackSlot
== VirtRegMap::NO_STACK_SLOT
)
691 const TargetRegisterClass
*RC
= mri
->getRegClass(spilled
->reg
);
692 LiveInterval
&stackInterval
= lss
->getOrCreateInterval(stackSlot
, RC
);
695 if (stackInterval
.getNumValNums() != 0)
696 vni
= stackInterval
.getValNumInfo(0);
698 vni
= stackInterval
.getNextValue(
699 SlotIndex(), 0, false, lss
->getVNInfoAllocator());
701 LiveInterval
&rhsInterval
= lis
->getInterval(spilled
->reg
);
702 stackInterval
.MergeRangesInAsValue(rhsInterval
, vni
);
705 bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution
&solution
) {
707 // Set to true if we have any spills
708 bool anotherRoundNeeded
= false;
710 // Clear the existing allocation.
713 // Iterate over the nodes mapping the PBQP solution to a register assignment.
714 for (unsigned node
= 0; node
< node2LI
.size(); ++node
) {
715 unsigned virtReg
= node2LI
[node
]->reg
,
716 allocSelection
= solution
.getSelection(problemNodes
[node
]);
719 // If the PBQP solution is non-zero it's a physical register...
720 if (allocSelection
!= 0) {
721 // Get the physical reg, subtracting 1 to account for the spill option.
722 unsigned physReg
= allowedSets
[node
][allocSelection
- 1];
724 DEBUG(dbgs() << "VREG " << virtReg
<< " -> "
725 << tri
->getName(physReg
) << "\n");
727 assert(physReg
!= 0);
729 // Add to the virt reg map and update the used phys regs.
730 vrm
->assignVirt2Phys(virtReg
, physReg
);
732 // ...Otherwise it's a spill.
735 // Make sure we ignore this virtual reg on the next round
737 vregIntervalsToAlloc
.erase(&lis
->getInterval(virtReg
));
739 // Insert spill ranges for this live range
740 const LiveInterval
*spillInterval
= node2LI
[node
];
741 double oldSpillWeight
= spillInterval
->weight
;
742 SmallVector
<LiveInterval
*, 8> spillIs
;
743 std::vector
<LiveInterval
*> newSpills
=
744 lis
->addIntervalsForSpills(*spillInterval
, spillIs
, loopInfo
, *vrm
);
745 addStackInterval(spillInterval
, mri
);
747 (void) oldSpillWeight
;
748 DEBUG(dbgs() << "VREG " << virtReg
<< " -> SPILLED (Cost: "
749 << oldSpillWeight
<< ", New vregs: ");
751 // Copy any newly inserted live intervals into the list of regs to
753 for (std::vector
<LiveInterval
*>::const_iterator
754 itr
= newSpills
.begin(), end
= newSpills
.end();
757 assert(!(*itr
)->empty() && "Empty spill range.");
759 DEBUG(dbgs() << (*itr
)->reg
<< " ");
761 vregIntervalsToAlloc
.insert(*itr
);
764 DEBUG(dbgs() << ")\n");
766 // We need another round if spill intervals were added.
767 anotherRoundNeeded
|= !newSpills
.empty();
771 return !anotherRoundNeeded
;
774 void PBQPRegAlloc::finalizeAlloc() const {
775 typedef LiveIntervals::iterator LIIterator
;
776 typedef LiveInterval::Ranges::const_iterator LRIterator
;
778 // First allocate registers for the empty intervals.
779 for (LiveIntervalSet::const_iterator
780 itr
= emptyVRegIntervals
.begin(), end
= emptyVRegIntervals
.end();
782 LiveInterval
*li
= *itr
;
784 unsigned physReg
= vrm
->getRegAllocPref(li
->reg
);
787 const TargetRegisterClass
*liRC
= mri
->getRegClass(li
->reg
);
788 physReg
= *liRC
->allocation_order_begin(*mf
);
791 vrm
->assignVirt2Phys(li
->reg
, physReg
);
794 // Finally iterate over the basic blocks to compute and set the live-in sets.
795 SmallVector
<MachineBasicBlock
*, 8> liveInMBBs
;
796 MachineBasicBlock
*entryMBB
= &*mf
->begin();
798 for (LIIterator liItr
= lis
->begin(), liEnd
= lis
->end();
799 liItr
!= liEnd
; ++liItr
) {
801 const LiveInterval
*li
= liItr
->second
;
804 // Get the physical register for this interval
805 if (TargetRegisterInfo::isPhysicalRegister(li
->reg
)) {
808 else if (vrm
->isAssignedReg(li
->reg
)) {
809 reg
= vrm
->getPhys(li
->reg
);
812 // Ranges which are assigned a stack slot only are ignored.
817 // Filter out zero regs - they're for intervals that were spilled.
821 // Iterate over the ranges of the current interval...
822 for (LRIterator lrItr
= li
->begin(), lrEnd
= li
->end();
823 lrItr
!= lrEnd
; ++lrItr
) {
825 // Find the set of basic blocks which this range is live into...
826 if (lis
->findLiveInMBBs(lrItr
->start
, lrItr
->end
, liveInMBBs
)) {
827 // And add the physreg for this interval to their live-in sets.
828 for (unsigned i
= 0; i
< liveInMBBs
.size(); ++i
) {
829 if (liveInMBBs
[i
] != entryMBB
) {
830 if (!liveInMBBs
[i
]->isLiveIn(reg
)) {
831 liveInMBBs
[i
]->addLiveIn(reg
);
842 bool PBQPRegAlloc::runOnMachineFunction(MachineFunction
&MF
) {
845 tm
= &mf
->getTarget();
846 tri
= tm
->getRegisterInfo();
847 tii
= tm
->getInstrInfo();
848 mri
= &mf
->getRegInfo();
850 lis
= &getAnalysis
<LiveIntervals
>();
851 lss
= &getAnalysis
<LiveStacks
>();
852 loopInfo
= &getAnalysis
<MachineLoopInfo
>();
854 vrm
= &getAnalysis
<VirtRegMap
>();
856 DEBUG(dbgs() << "PBQP Register Allocating for " << mf
->getFunction()->getName() << "\n");
858 // Allocator main loop:
860 // * Map current regalloc problem to a PBQP problem
861 // * Solve the PBQP problem
862 // * Map the solution back to a register allocation
863 // * Spill if necessary
865 // This process is continued till no more spills are generated.
867 // Find the vreg intervals in need of allocation.
868 findVRegIntervalsToAlloc();
870 // If there are non-empty intervals allocate them using pbqp.
871 if (!vregIntervalsToAlloc
.empty()) {
873 bool pbqpAllocComplete
= false;
876 while (!pbqpAllocComplete
) {
877 DEBUG(dbgs() << " PBQP Regalloc round " << round
<< ":\n");
879 PBQP::Graph problem
= constructPBQPProblem();
880 PBQP::Solution solution
=
881 PBQP::HeuristicSolver
<PBQP::Heuristics::Briggs
>::solve(problem
);
883 pbqpAllocComplete
= mapPBQPToRegAlloc(solution
);
889 // Finalise allocation, allocate empty ranges.
892 vregIntervalsToAlloc
.clear();
893 emptyVRegIntervals
.clear();
897 problemNodes
.clear();
899 DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm
<< "\n");
902 std::auto_ptr
<VirtRegRewriter
> rewriter(createVirtRegRewriter());
904 rewriter
->runOnMachineFunction(*mf
, *vrm
, lis
);
909 FunctionPass
* llvm::createPBQPRegisterAllocator() {
910 return new PBQPRegAlloc();