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 "RenderMachineFunction.h"
39 #include "VirtRegMap.h"
40 #include "VirtRegRewriter.h"
41 #include "llvm/CodeGen/CalcSpillWeights.h"
42 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
43 #include "llvm/CodeGen/LiveStackAnalysis.h"
44 #include "llvm/CodeGen/MachineFunctionPass.h"
45 #include "llvm/CodeGen/MachineLoopInfo.h"
46 #include "llvm/CodeGen/MachineRegisterInfo.h"
47 #include "llvm/CodeGen/RegAllocRegistry.h"
48 #include "llvm/CodeGen/RegisterCoalescer.h"
49 #include "llvm/Support/Debug.h"
50 #include "llvm/Support/raw_ostream.h"
51 #include "llvm/Target/TargetInstrInfo.h"
52 #include "llvm/Target/TargetMachine.h"
61 static RegisterRegAlloc
62 registerPBQPRepAlloc("pbqp", "PBQP register allocator",
63 llvm::createPBQPRegisterAllocator
);
66 pbqpCoalescing("pbqp-coalescing",
67 cl::desc("Attempt coalescing during PBQP register allocation."),
68 cl::init(false), cl::Hidden
);
71 pbqpPreSplitting("pbqp-pre-splitting",
72 cl::desc("Pre-splite before PBQP register allocation."),
73 cl::init(false), cl::Hidden
);
78 /// PBQP based allocators solve the register allocation problem by mapping
79 /// register allocation problems to Partitioned Boolean Quadratic
80 /// Programming problems.
81 class PBQPRegAlloc
: public MachineFunctionPass
{
86 /// Construct a PBQP register allocator.
87 PBQPRegAlloc() : MachineFunctionPass(&ID
) {}
89 /// Return the pass name.
90 virtual const char* getPassName() const {
91 return "PBQP Register Allocator";
94 /// PBQP analysis usage.
95 virtual void getAnalysisUsage(AnalysisUsage
&au
) const {
96 au
.addRequired
<SlotIndexes
>();
97 au
.addPreserved
<SlotIndexes
>();
98 au
.addRequired
<LiveIntervals
>();
99 //au.addRequiredID(SplitCriticalEdgesID);
100 au
.addRequired
<RegisterCoalescer
>();
101 au
.addRequired
<CalculateSpillWeights
>();
102 au
.addRequired
<LiveStacks
>();
103 au
.addPreserved
<LiveStacks
>();
104 au
.addRequired
<MachineLoopInfo
>();
105 au
.addPreserved
<MachineLoopInfo
>();
106 if (pbqpPreSplitting
)
107 au
.addRequired
<LoopSplitter
>();
108 au
.addRequired
<VirtRegMap
>();
109 au
.addRequired
<RenderMachineFunction
>();
110 MachineFunctionPass::getAnalysisUsage(au
);
113 /// Perform register allocation
114 virtual bool runOnMachineFunction(MachineFunction
&MF
);
120 bool operator()(const LiveInterval
*li1
, const LiveInterval
*li2
) const {
121 return li1
->reg
< li2
->reg
;
125 typedef std::map
<const LiveInterval
*, unsigned, LIOrdering
> LI2NodeMap
;
126 typedef std::vector
<const LiveInterval
*> Node2LIMap
;
127 typedef std::vector
<unsigned> AllowedSet
;
128 typedef std::vector
<AllowedSet
> AllowedSetMap
;
129 typedef std::set
<unsigned> RegSet
;
130 typedef std::pair
<unsigned, unsigned> RegPair
;
131 typedef std::map
<RegPair
, PBQP::PBQPNum
> CoalesceMap
;
133 typedef std::set
<LiveInterval
*, LIOrdering
> LiveIntervalSet
;
135 typedef std::vector
<PBQP::Graph::NodeItr
> NodeVector
;
138 const TargetMachine
*tm
;
139 const TargetRegisterInfo
*tri
;
140 const TargetInstrInfo
*tii
;
141 const MachineLoopInfo
*loopInfo
;
142 MachineRegisterInfo
*mri
;
150 AllowedSetMap allowedSets
;
151 LiveIntervalSet vregIntervalsToAlloc
,
153 NodeVector problemNodes
;
156 /// Builds a PBQP cost vector.
157 template <typename RegContainer
>
158 PBQP::Vector
buildCostVector(unsigned vReg
,
159 const RegContainer
&allowed
,
160 const CoalesceMap
&cealesces
,
161 PBQP::PBQPNum spillCost
) const;
163 /// \brief Builds a PBQP interference matrix.
165 /// @return Either a pointer to a non-zero PBQP matrix representing the
166 /// allocation option costs, or a null pointer for a zero matrix.
168 /// Expects allowed sets for two interfering LiveIntervals. These allowed
169 /// sets should contain only allocable registers from the LiveInterval's
170 /// register class, with any interfering pre-colored registers removed.
171 template <typename RegContainer
>
172 PBQP::Matrix
* buildInterferenceMatrix(const RegContainer
&allowed1
,
173 const RegContainer
&allowed2
) const;
176 /// Expects allowed sets for two potentially coalescable LiveIntervals,
177 /// and an estimated benefit due to coalescing. The allowed sets should
178 /// contain only allocable registers from the LiveInterval's register
179 /// classes, with any interfering pre-colored registers removed.
180 template <typename RegContainer
>
181 PBQP::Matrix
* buildCoalescingMatrix(const RegContainer
&allowed1
,
182 const RegContainer
&allowed2
,
183 PBQP::PBQPNum cBenefit
) const;
185 /// \brief Finds coalescing opportunities and returns them as a map.
187 /// Any entries in the map are guaranteed coalescable, even if their
188 /// corresponding live intervals overlap.
189 CoalesceMap
findCoalesces();
191 /// \brief Finds the initial set of vreg intervals to allocate.
192 void findVRegIntervalsToAlloc();
194 /// \brief Constructs a PBQP problem representation of the register
195 /// allocation problem for this function.
197 /// @return a PBQP solver object for the register allocation problem.
198 PBQP::Graph
constructPBQPProblem();
200 /// \brief Adds a stack interval if the given live interval has been
201 /// spilled. Used to support stack slot coloring.
202 void addStackInterval(const LiveInterval
*spilled
,MachineRegisterInfo
* mri
);
204 /// \brief Given a solved PBQP problem maps this solution back to a register
206 bool mapPBQPToRegAlloc(const PBQP::Solution
&solution
);
208 /// \brief Postprocessing before final spilling. Sets basic block "live in"
210 void finalizeAlloc() const;
214 char PBQPRegAlloc::ID
= 0;
218 template <typename RegContainer
>
219 PBQP::Vector
PBQPRegAlloc::buildCostVector(unsigned vReg
,
220 const RegContainer
&allowed
,
221 const CoalesceMap
&coalesces
,
222 PBQP::PBQPNum spillCost
) const {
224 typedef typename
RegContainer::const_iterator AllowedItr
;
226 // Allocate vector. Additional element (0th) used for spill option
227 PBQP::Vector
v(allowed
.size() + 1, 0);
231 // Iterate over the allowed registers inserting coalesce benefits if there
234 for (AllowedItr itr
= allowed
.begin(), end
= allowed
.end();
235 itr
!= end
; ++itr
, ++ai
) {
237 unsigned pReg
= *itr
;
239 CoalesceMap::const_iterator cmItr
=
240 coalesces
.find(RegPair(vReg
, pReg
));
242 // No coalesce - on to the next preg.
243 if (cmItr
== coalesces
.end())
246 // We have a coalesce - insert the benefit.
247 v
[ai
+ 1] = -cmItr
->second
;
253 template <typename RegContainer
>
254 PBQP::Matrix
* PBQPRegAlloc::buildInterferenceMatrix(
255 const RegContainer
&allowed1
, const RegContainer
&allowed2
) const {
257 typedef typename
RegContainer::const_iterator RegContainerIterator
;
259 // Construct a PBQP matrix representing the cost of allocation options. The
260 // rows and columns correspond to the allocation options for the two live
261 // intervals. Elements will be infinite where corresponding registers alias,
262 // since we cannot allocate aliasing registers to interfering live intervals.
263 // All other elements (non-aliasing combinations) will have zero cost. Note
264 // that the spill option (element 0,0) has zero cost, since we can allocate
265 // both intervals to memory safely (the cost for each individual allocation
266 // to memory is accounted for by the cost vectors for each live interval).
268 new PBQP::Matrix(allowed1
.size() + 1, allowed2
.size() + 1, 0);
270 // Assume this is a zero matrix until proven otherwise. Zero matrices occur
271 // between interfering live ranges with non-overlapping register sets (e.g.
272 // non-overlapping reg classes, or disjoint sets of allowed regs within the
273 // same class). The term "overlapping" is used advisedly: sets which do not
274 // intersect, but contain registers which alias, will have non-zero matrices.
275 // We optimize zero matrices away to improve solver speed.
276 bool isZeroMatrix
= true;
279 // Row index. Starts at 1, since the 0th row is for the spill option, which
283 // Iterate over allowed sets, insert infinities where required.
284 for (RegContainerIterator a1Itr
= allowed1
.begin(), a1End
= allowed1
.end();
285 a1Itr
!= a1End
; ++a1Itr
) {
287 // Column index, starts at 1 as for row index.
289 unsigned reg1
= *a1Itr
;
291 for (RegContainerIterator a2Itr
= allowed2
.begin(), a2End
= allowed2
.end();
292 a2Itr
!= a2End
; ++a2Itr
) {
294 unsigned reg2
= *a2Itr
;
296 // If the row/column regs are identical or alias insert an infinity.
297 if (tri
->regsOverlap(reg1
, reg2
)) {
298 (*m
)[ri
][ci
] = std::numeric_limits
<PBQP::PBQPNum
>::infinity();
299 isZeroMatrix
= false;
308 // If this turns out to be a zero matrix...
310 // free it and return null.
315 // ...otherwise return the cost matrix.
319 template <typename RegContainer
>
320 PBQP::Matrix
* PBQPRegAlloc::buildCoalescingMatrix(
321 const RegContainer
&allowed1
, const RegContainer
&allowed2
,
322 PBQP::PBQPNum cBenefit
) const {
324 typedef typename
RegContainer::const_iterator RegContainerIterator
;
326 // Construct a PBQP Matrix representing the benefits of coalescing. As with
327 // interference matrices the rows and columns represent allowed registers
328 // for the LiveIntervals which are (potentially) to be coalesced. The amount
329 // -cBenefit will be placed in any element representing the same register
330 // for both intervals.
332 new PBQP::Matrix(allowed1
.size() + 1, allowed2
.size() + 1, 0);
334 // Reset costs to zero.
337 // Assume the matrix is zero till proven otherwise. Zero matrices will be
338 // optimized away as in the interference case.
339 bool isZeroMatrix
= true;
341 // Row index. Starts at 1, since the 0th row is for the spill option, which
345 // Iterate over the allowed sets, insert coalescing benefits where
347 for (RegContainerIterator a1Itr
= allowed1
.begin(), a1End
= allowed1
.end();
348 a1Itr
!= a1End
; ++a1Itr
) {
350 // Column index, starts at 1 as for row index.
352 unsigned reg1
= *a1Itr
;
354 for (RegContainerIterator a2Itr
= allowed2
.begin(), a2End
= allowed2
.end();
355 a2Itr
!= a2End
; ++a2Itr
) {
357 // If the row and column represent the same register insert a beneficial
358 // cost to preference this allocation - it would allow us to eliminate a
360 if (reg1
== *a2Itr
) {
361 (*m
)[ri
][ci
] = -cBenefit
;
362 isZeroMatrix
= false;
371 // If this turns out to be a zero matrix...
373 // ...free it and return null.
381 PBQPRegAlloc::CoalesceMap
PBQPRegAlloc::findCoalesces() {
383 typedef MachineFunction::const_iterator MFIterator
;
384 typedef MachineBasicBlock::const_iterator MBBIterator
;
385 typedef LiveInterval::const_vni_iterator VNIIterator
;
387 CoalesceMap coalescesFound
;
389 // To find coalesces we need to iterate over the function looking for
390 // copy instructions.
391 for (MFIterator bbItr
= mf
->begin(), bbEnd
= mf
->end();
392 bbItr
!= bbEnd
; ++bbItr
) {
394 const MachineBasicBlock
*mbb
= &*bbItr
;
396 for (MBBIterator iItr
= mbb
->begin(), iEnd
= mbb
->end();
397 iItr
!= iEnd
; ++iItr
) {
399 const MachineInstr
*instr
= &*iItr
;
401 // If this isn't a copy then continue to the next instruction.
402 if (!instr
->isCopy())
405 unsigned srcReg
= instr
->getOperand(1).getReg();
406 unsigned dstReg
= instr
->getOperand(0).getReg();
408 // If the registers are already the same our job is nice and easy.
409 if (dstReg
== srcReg
)
412 bool srcRegIsPhysical
= TargetRegisterInfo::isPhysicalRegister(srcReg
),
413 dstRegIsPhysical
= TargetRegisterInfo::isPhysicalRegister(dstReg
);
415 // If both registers are physical then we can't coalesce.
416 if (srcRegIsPhysical
&& dstRegIsPhysical
)
419 // If it's a copy that includes two virtual register but the source and
420 // destination classes differ then we can't coalesce.
421 if (!srcRegIsPhysical
&& !dstRegIsPhysical
&&
422 mri
->getRegClass(srcReg
) != mri
->getRegClass(dstReg
))
425 // If one is physical and one is virtual, check that the physical is
426 // allocatable in the class of the virtual.
427 if (srcRegIsPhysical
&& !dstRegIsPhysical
) {
428 const TargetRegisterClass
*dstRegClass
= mri
->getRegClass(dstReg
);
429 if (std::find(dstRegClass
->allocation_order_begin(*mf
),
430 dstRegClass
->allocation_order_end(*mf
), srcReg
) ==
431 dstRegClass
->allocation_order_end(*mf
))
434 if (!srcRegIsPhysical
&& dstRegIsPhysical
) {
435 const TargetRegisterClass
*srcRegClass
= mri
->getRegClass(srcReg
);
436 if (std::find(srcRegClass
->allocation_order_begin(*mf
),
437 srcRegClass
->allocation_order_end(*mf
), dstReg
) ==
438 srcRegClass
->allocation_order_end(*mf
))
442 // If we've made it here we have a copy with compatible register classes.
443 // We can probably coalesce, but we need to consider overlap.
444 const LiveInterval
*srcLI
= &lis
->getInterval(srcReg
),
445 *dstLI
= &lis
->getInterval(dstReg
);
447 if (srcLI
->overlaps(*dstLI
)) {
448 // Even in the case of an overlap we might still be able to coalesce,
449 // but we need to make sure that no definition of either range occurs
450 // while the other range is live.
452 // Otherwise start by assuming we're ok.
455 // Test all defs of the source range.
457 vniItr
= srcLI
->vni_begin(), vniEnd
= srcLI
->vni_end();
458 vniItr
!= vniEnd
; ++vniItr
) {
460 // If we find a poorly defined def we err on the side of caution.
461 if (!(*vniItr
)->def
.isValid()) {
466 // If we find a def that kills the coalescing opportunity then
467 // record it and break from the loop.
468 if (dstLI
->liveAt((*vniItr
)->def
)) {
474 // If we have a bad def give up, continue to the next instruction.
478 // Otherwise test definitions of the destination range.
480 vniItr
= dstLI
->vni_begin(), vniEnd
= dstLI
->vni_end();
481 vniItr
!= vniEnd
; ++vniItr
) {
483 // We want to make sure we skip the copy instruction itself.
484 if ((*vniItr
)->getCopy() == instr
)
487 if (!(*vniItr
)->def
.isValid()) {
492 if (srcLI
->liveAt((*vniItr
)->def
)) {
498 // As before a bad def we give up and continue to the next instr.
503 // If we make it to here then either the ranges didn't overlap, or they
504 // did, but none of their definitions would prevent us from coalescing.
505 // We're good to go with the coalesce.
507 float cBenefit
= std::pow(10.0f
, (float)loopInfo
->getLoopDepth(mbb
)) / 5.0;
509 coalescesFound
[RegPair(srcReg
, dstReg
)] = cBenefit
;
510 coalescesFound
[RegPair(dstReg
, srcReg
)] = cBenefit
;
515 return coalescesFound
;
518 void PBQPRegAlloc::findVRegIntervalsToAlloc() {
520 // Iterate over all live ranges.
521 for (LiveIntervals::iterator itr
= lis
->begin(), end
= lis
->end();
524 // Ignore physical ones.
525 if (TargetRegisterInfo::isPhysicalRegister(itr
->first
))
528 LiveInterval
*li
= itr
->second
;
530 // If this live interval is non-empty we will use pbqp to allocate it.
531 // Empty intervals we allocate in a simple post-processing stage in
534 vregIntervalsToAlloc
.insert(li
);
537 emptyVRegIntervals
.insert(li
);
542 PBQP::Graph
PBQPRegAlloc::constructPBQPProblem() {
544 typedef std::vector
<const LiveInterval
*> LIVector
;
545 typedef std::vector
<unsigned> RegVector
;
547 // This will store the physical intervals for easy reference.
548 LIVector physIntervals
;
550 // Start by clearing the old node <-> live interval mappings & allowed sets
555 // Populate physIntervals, update preg use:
556 for (LiveIntervals::iterator itr
= lis
->begin(), end
= lis
->end();
559 if (TargetRegisterInfo::isPhysicalRegister(itr
->first
)) {
560 physIntervals
.push_back(itr
->second
);
561 mri
->setPhysRegUsed(itr
->second
->reg
);
565 // Iterate over vreg intervals, construct live interval <-> node number
567 for (LiveIntervalSet::const_iterator
568 itr
= vregIntervalsToAlloc
.begin(), end
= vregIntervalsToAlloc
.end();
570 const LiveInterval
*li
= *itr
;
572 li2Node
[li
] = node2LI
.size();
573 node2LI
.push_back(li
);
576 // Get the set of potential coalesces.
577 CoalesceMap coalesces
;
579 if (pbqpCoalescing
) {
580 coalesces
= findCoalesces();
583 // Construct a PBQP solver for this problem
585 problemNodes
.resize(vregIntervalsToAlloc
.size());
587 // Resize allowedSets container appropriately.
588 allowedSets
.resize(vregIntervalsToAlloc
.size());
590 // Iterate over virtual register intervals to compute allowed sets...
591 for (unsigned node
= 0; node
< node2LI
.size(); ++node
) {
593 // Grab pointers to the interval and its register class.
594 const LiveInterval
*li
= node2LI
[node
];
595 const TargetRegisterClass
*liRC
= mri
->getRegClass(li
->reg
);
597 // Start by assuming all allocable registers in the class are allowed...
598 RegVector
liAllowed(liRC
->allocation_order_begin(*mf
),
599 liRC
->allocation_order_end(*mf
));
601 // Eliminate the physical registers which overlap with this range, along
602 // with all their aliases.
603 for (LIVector::iterator pItr
= physIntervals
.begin(),
604 pEnd
= physIntervals
.end(); pItr
!= pEnd
; ++pItr
) {
606 if (!li
->overlaps(**pItr
))
609 unsigned pReg
= (*pItr
)->reg
;
611 // If we get here then the live intervals overlap, but we're still ok
612 // if they're coalescable.
613 if (coalesces
.find(RegPair(li
->reg
, pReg
)) != coalesces
.end())
616 // If we get here then we have a genuine exclusion.
618 // Remove the overlapping reg...
619 RegVector::iterator eraseItr
=
620 std::find(liAllowed
.begin(), liAllowed
.end(), pReg
);
622 if (eraseItr
!= liAllowed
.end())
623 liAllowed
.erase(eraseItr
);
625 const unsigned *aliasItr
= tri
->getAliasSet(pReg
);
628 // ...and its aliases.
629 for (; *aliasItr
!= 0; ++aliasItr
) {
630 RegVector::iterator eraseItr
=
631 std::find(liAllowed
.begin(), liAllowed
.end(), *aliasItr
);
633 if (eraseItr
!= liAllowed
.end()) {
634 liAllowed
.erase(eraseItr
);
640 // Copy the allowed set into a member vector for use when constructing cost
641 // vectors & matrices, and mapping PBQP solutions back to assignments.
642 allowedSets
[node
] = AllowedSet(liAllowed
.begin(), liAllowed
.end());
644 // Set the spill cost to the interval weight, or epsilon if the
645 // interval weight is zero
646 PBQP::PBQPNum spillCost
= (li
->weight
!= 0.0) ?
647 li
->weight
: std::numeric_limits
<PBQP::PBQPNum
>::min();
649 // Build a cost vector for this interval.
652 buildCostVector(li
->reg
, allowedSets
[node
], coalesces
, spillCost
));
657 // Now add the cost matrices...
658 for (unsigned node1
= 0; node1
< node2LI
.size(); ++node1
) {
659 const LiveInterval
*li
= node2LI
[node1
];
661 // Test for live range overlaps and insert interference matrices.
662 for (unsigned node2
= node1
+ 1; node2
< node2LI
.size(); ++node2
) {
663 const LiveInterval
*li2
= node2LI
[node2
];
665 CoalesceMap::const_iterator cmItr
=
666 coalesces
.find(RegPair(li
->reg
, li2
->reg
));
670 if (cmItr
!= coalesces
.end()) {
671 m
= buildCoalescingMatrix(allowedSets
[node1
], allowedSets
[node2
],
674 else if (li
->overlaps(*li2
)) {
675 m
= buildInterferenceMatrix(allowedSets
[node1
], allowedSets
[node2
]);
679 problem
.addEdge(problemNodes
[node1
],
688 assert(problem
.getNumNodes() == allowedSets
.size());
690 std::cerr << "Allocating for " << problem.getNumNodes() << " nodes, "
691 << problem.getNumEdges() << " edges.\n";
693 problem.printDot(std::cerr);
695 // We're done, PBQP problem constructed - return it.
699 void PBQPRegAlloc::addStackInterval(const LiveInterval
*spilled
,
700 MachineRegisterInfo
* mri
) {
701 int stackSlot
= vrm
->getStackSlot(spilled
->reg
);
703 if (stackSlot
== VirtRegMap::NO_STACK_SLOT
)
706 const TargetRegisterClass
*RC
= mri
->getRegClass(spilled
->reg
);
707 LiveInterval
&stackInterval
= lss
->getOrCreateInterval(stackSlot
, RC
);
710 if (stackInterval
.getNumValNums() != 0)
711 vni
= stackInterval
.getValNumInfo(0);
713 vni
= stackInterval
.getNextValue(
714 SlotIndex(), 0, false, lss
->getVNInfoAllocator());
716 LiveInterval
&rhsInterval
= lis
->getInterval(spilled
->reg
);
717 stackInterval
.MergeRangesInAsValue(rhsInterval
, vni
);
720 bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution
&solution
) {
722 // Set to true if we have any spills
723 bool anotherRoundNeeded
= false;
725 // Clear the existing allocation.
728 // Iterate over the nodes mapping the PBQP solution to a register assignment.
729 for (unsigned node
= 0; node
< node2LI
.size(); ++node
) {
730 unsigned virtReg
= node2LI
[node
]->reg
,
731 allocSelection
= solution
.getSelection(problemNodes
[node
]);
734 // If the PBQP solution is non-zero it's a physical register...
735 if (allocSelection
!= 0) {
736 // Get the physical reg, subtracting 1 to account for the spill option.
737 unsigned physReg
= allowedSets
[node
][allocSelection
- 1];
739 DEBUG(dbgs() << "VREG " << virtReg
<< " -> "
740 << tri
->getName(physReg
) << "\n");
742 assert(physReg
!= 0);
744 // Add to the virt reg map and update the used phys regs.
745 vrm
->assignVirt2Phys(virtReg
, physReg
);
747 // ...Otherwise it's a spill.
750 // Make sure we ignore this virtual reg on the next round
752 vregIntervalsToAlloc
.erase(&lis
->getInterval(virtReg
));
754 // Insert spill ranges for this live range
755 const LiveInterval
*spillInterval
= node2LI
[node
];
756 double oldSpillWeight
= spillInterval
->weight
;
757 SmallVector
<LiveInterval
*, 8> spillIs
;
758 std::vector
<LiveInterval
*> newSpills
=
759 lis
->addIntervalsForSpills(*spillInterval
, spillIs
, loopInfo
, *vrm
);
760 addStackInterval(spillInterval
, mri
);
762 (void) oldSpillWeight
;
763 DEBUG(dbgs() << "VREG " << virtReg
<< " -> SPILLED (Cost: "
764 << oldSpillWeight
<< ", New vregs: ");
766 // Copy any newly inserted live intervals into the list of regs to
768 for (std::vector
<LiveInterval
*>::const_iterator
769 itr
= newSpills
.begin(), end
= newSpills
.end();
772 assert(!(*itr
)->empty() && "Empty spill range.");
774 DEBUG(dbgs() << (*itr
)->reg
<< " ");
776 vregIntervalsToAlloc
.insert(*itr
);
779 DEBUG(dbgs() << ")\n");
781 // We need another round if spill intervals were added.
782 anotherRoundNeeded
|= !newSpills
.empty();
786 return !anotherRoundNeeded
;
789 void PBQPRegAlloc::finalizeAlloc() const {
790 typedef LiveIntervals::iterator LIIterator
;
791 typedef LiveInterval::Ranges::const_iterator LRIterator
;
793 // First allocate registers for the empty intervals.
794 for (LiveIntervalSet::const_iterator
795 itr
= emptyVRegIntervals
.begin(), end
= emptyVRegIntervals
.end();
797 LiveInterval
*li
= *itr
;
799 unsigned physReg
= vrm
->getRegAllocPref(li
->reg
);
802 const TargetRegisterClass
*liRC
= mri
->getRegClass(li
->reg
);
803 physReg
= *liRC
->allocation_order_begin(*mf
);
806 vrm
->assignVirt2Phys(li
->reg
, physReg
);
809 // Finally iterate over the basic blocks to compute and set the live-in sets.
810 SmallVector
<MachineBasicBlock
*, 8> liveInMBBs
;
811 MachineBasicBlock
*entryMBB
= &*mf
->begin();
813 for (LIIterator liItr
= lis
->begin(), liEnd
= lis
->end();
814 liItr
!= liEnd
; ++liItr
) {
816 const LiveInterval
*li
= liItr
->second
;
819 // Get the physical register for this interval
820 if (TargetRegisterInfo::isPhysicalRegister(li
->reg
)) {
823 else if (vrm
->isAssignedReg(li
->reg
)) {
824 reg
= vrm
->getPhys(li
->reg
);
827 // Ranges which are assigned a stack slot only are ignored.
832 // Filter out zero regs - they're for intervals that were spilled.
836 // Iterate over the ranges of the current interval...
837 for (LRIterator lrItr
= li
->begin(), lrEnd
= li
->end();
838 lrItr
!= lrEnd
; ++lrItr
) {
840 // Find the set of basic blocks which this range is live into...
841 if (lis
->findLiveInMBBs(lrItr
->start
, lrItr
->end
, liveInMBBs
)) {
842 // And add the physreg for this interval to their live-in sets.
843 for (unsigned i
= 0; i
< liveInMBBs
.size(); ++i
) {
844 if (liveInMBBs
[i
] != entryMBB
) {
845 if (!liveInMBBs
[i
]->isLiveIn(reg
)) {
846 liveInMBBs
[i
]->addLiveIn(reg
);
857 bool PBQPRegAlloc::runOnMachineFunction(MachineFunction
&MF
) {
860 tm
= &mf
->getTarget();
861 tri
= tm
->getRegisterInfo();
862 tii
= tm
->getInstrInfo();
863 mri
= &mf
->getRegInfo();
865 lis
= &getAnalysis
<LiveIntervals
>();
866 lss
= &getAnalysis
<LiveStacks
>();
867 loopInfo
= &getAnalysis
<MachineLoopInfo
>();
868 RenderMachineFunction
*rmf
= &getAnalysis
<RenderMachineFunction
>();
870 vrm
= &getAnalysis
<VirtRegMap
>();
873 DEBUG(dbgs() << "PBQP Register Allocating for " << mf
->getFunction()->getName() << "\n");
875 // Allocator main loop:
877 // * Map current regalloc problem to a PBQP problem
878 // * Solve the PBQP problem
879 // * Map the solution back to a register allocation
880 // * Spill if necessary
882 // This process is continued till no more spills are generated.
884 // Find the vreg intervals in need of allocation.
885 findVRegIntervalsToAlloc();
887 // If there are non-empty intervals allocate them using pbqp.
888 if (!vregIntervalsToAlloc
.empty()) {
890 bool pbqpAllocComplete
= false;
893 while (!pbqpAllocComplete
) {
894 DEBUG(dbgs() << " PBQP Regalloc round " << round
<< ":\n");
896 PBQP::Graph problem
= constructPBQPProblem();
897 PBQP::Solution solution
=
898 PBQP::HeuristicSolver
<PBQP::Heuristics::Briggs
>::solve(problem
);
900 pbqpAllocComplete
= mapPBQPToRegAlloc(solution
);
906 // Finalise allocation, allocate empty ranges.
909 rmf
->renderMachineFunction("After PBQP register allocation.", vrm
);
911 vregIntervalsToAlloc
.clear();
912 emptyVRegIntervals
.clear();
916 problemNodes
.clear();
918 DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm
<< "\n");
921 std::auto_ptr
<VirtRegRewriter
> rewriter(createVirtRegRewriter());
923 rewriter
->runOnMachineFunction(*mf
, *vrm
, lis
);
928 FunctionPass
* llvm::createPBQPRegisterAllocator() {
929 return new PBQPRegAlloc();