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 "RegisterCoalescer.h"
39 #include "llvm/CodeGen/CalcSpillWeights.h"
40 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
41 #include "llvm/CodeGen/LiveStackAnalysis.h"
42 #include "llvm/CodeGen/RegAllocPBQP.h"
43 #include "llvm/CodeGen/MachineFunctionPass.h"
44 #include "llvm/CodeGen/MachineLoopInfo.h"
45 #include "llvm/CodeGen/MachineRegisterInfo.h"
46 #include "llvm/CodeGen/PBQP/HeuristicSolver.h"
47 #include "llvm/CodeGen/PBQP/Graph.h"
48 #include "llvm/CodeGen/PBQP/Heuristics/Briggs.h"
49 #include "llvm/CodeGen/RegAllocRegistry.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"
61 static RegisterRegAlloc
62 registerPBQPRepAlloc("pbqp", "PBQP register allocator",
63 createDefaultPBQPRegisterAllocator
);
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-split 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 RegAllocPBQP
: public MachineFunctionPass
{
86 /// Construct a PBQP register allocator.
87 RegAllocPBQP(std::auto_ptr
<PBQPBuilder
> b
, char *cPassID
=0)
88 : MachineFunctionPass(ID
), builder(b
), customPassID(cPassID
) {
89 initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
90 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
91 initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry());
92 initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
93 initializeLiveStacksPass(*PassRegistry::getPassRegistry());
94 initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
95 initializeLoopSplitterPass(*PassRegistry::getPassRegistry());
96 initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
97 initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry());
100 /// Return the pass name.
101 virtual const char* getPassName() const {
102 return "PBQP Register Allocator";
105 /// PBQP analysis usage.
106 virtual void getAnalysisUsage(AnalysisUsage
&au
) const;
108 /// Perform register allocation
109 virtual bool runOnMachineFunction(MachineFunction
&MF
);
113 typedef std::map
<const LiveInterval
*, unsigned> LI2NodeMap
;
114 typedef std::vector
<const LiveInterval
*> Node2LIMap
;
115 typedef std::vector
<unsigned> AllowedSet
;
116 typedef std::vector
<AllowedSet
> AllowedSetMap
;
117 typedef std::pair
<unsigned, unsigned> RegPair
;
118 typedef std::map
<RegPair
, PBQP::PBQPNum
> CoalesceMap
;
119 typedef std::vector
<PBQP::Graph::NodeItr
> NodeVector
;
120 typedef std::set
<unsigned> RegSet
;
123 std::auto_ptr
<PBQPBuilder
> builder
;
128 const TargetMachine
*tm
;
129 const TargetRegisterInfo
*tri
;
130 const TargetInstrInfo
*tii
;
131 const MachineLoopInfo
*loopInfo
;
132 MachineRegisterInfo
*mri
;
133 RenderMachineFunction
*rmf
;
139 RegSet vregsToAlloc
, emptyIntervalVRegs
;
141 /// \brief Finds the initial set of vreg intervals to allocate.
142 void findVRegIntervalsToAlloc();
144 /// \brief Adds a stack interval if the given live interval has been
145 /// spilled. Used to support stack slot coloring.
146 void addStackInterval(const LiveInterval
*spilled
,MachineRegisterInfo
* mri
);
148 /// \brief Given a solved PBQP problem maps this solution back to a register
150 bool mapPBQPToRegAlloc(const PBQPRAProblem
&problem
,
151 const PBQP::Solution
&solution
);
153 /// \brief Postprocessing before final spilling. Sets basic block "live in"
155 void finalizeAlloc() const;
159 char RegAllocPBQP::ID
= 0;
161 } // End anonymous namespace.
163 unsigned PBQPRAProblem::getVRegForNode(PBQP::Graph::ConstNodeItr node
) const {
164 Node2VReg::const_iterator vregItr
= node2VReg
.find(node
);
165 assert(vregItr
!= node2VReg
.end() && "No vreg for node.");
166 return vregItr
->second
;
169 PBQP::Graph::NodeItr
PBQPRAProblem::getNodeForVReg(unsigned vreg
) const {
170 VReg2Node::const_iterator nodeItr
= vreg2Node
.find(vreg
);
171 assert(nodeItr
!= vreg2Node
.end() && "No node for vreg.");
172 return nodeItr
->second
;
176 const PBQPRAProblem::AllowedSet
&
177 PBQPRAProblem::getAllowedSet(unsigned vreg
) const {
178 AllowedSetMap::const_iterator allowedSetItr
= allowedSets
.find(vreg
);
179 assert(allowedSetItr
!= allowedSets
.end() && "No pregs for vreg.");
180 const AllowedSet
&allowedSet
= allowedSetItr
->second
;
184 unsigned PBQPRAProblem::getPRegForOption(unsigned vreg
, unsigned option
) const {
185 assert(isPRegOption(vreg
, option
) && "Not a preg option.");
187 const AllowedSet
& allowedSet
= getAllowedSet(vreg
);
188 assert(option
<= allowedSet
.size() && "Option outside allowed set.");
189 return allowedSet
[option
- 1];
192 std::auto_ptr
<PBQPRAProblem
> PBQPBuilder::build(MachineFunction
*mf
,
193 const LiveIntervals
*lis
,
194 const MachineLoopInfo
*loopInfo
,
195 const RegSet
&vregs
) {
197 typedef std::vector
<const LiveInterval
*> LIVector
;
199 MachineRegisterInfo
*mri
= &mf
->getRegInfo();
200 const TargetRegisterInfo
*tri
= mf
->getTarget().getRegisterInfo();
202 std::auto_ptr
<PBQPRAProblem
> p(new PBQPRAProblem());
203 PBQP::Graph
&g
= p
->getGraph();
206 // Collect the set of preg intervals, record that they're used in the MF.
207 for (LiveIntervals::const_iterator itr
= lis
->begin(), end
= lis
->end();
209 if (TargetRegisterInfo::isPhysicalRegister(itr
->first
)) {
210 pregs
.insert(itr
->first
);
211 mri
->setPhysRegUsed(itr
->first
);
215 BitVector reservedRegs
= tri
->getReservedRegs(*mf
);
217 // Iterate over vregs.
218 for (RegSet::const_iterator vregItr
= vregs
.begin(), vregEnd
= vregs
.end();
219 vregItr
!= vregEnd
; ++vregItr
) {
220 unsigned vreg
= *vregItr
;
221 const TargetRegisterClass
*trc
= mri
->getRegClass(vreg
);
222 const LiveInterval
*vregLI
= &lis
->getInterval(vreg
);
224 // Compute an initial allowed set for the current vreg.
225 typedef std::vector
<unsigned> VRAllowed
;
227 ArrayRef
<unsigned> rawOrder
= trc
->getRawAllocationOrder(*mf
);
228 for (unsigned i
= 0; i
!= rawOrder
.size(); ++i
) {
229 unsigned preg
= rawOrder
[i
];
230 if (!reservedRegs
.test(preg
)) {
231 vrAllowed
.push_back(preg
);
235 // Remove any physical registers which overlap.
236 for (RegSet::const_iterator pregItr
= pregs
.begin(),
237 pregEnd
= pregs
.end();
238 pregItr
!= pregEnd
; ++pregItr
) {
239 unsigned preg
= *pregItr
;
240 const LiveInterval
*pregLI
= &lis
->getInterval(preg
);
242 if (pregLI
->empty()) {
246 if (!vregLI
->overlaps(*pregLI
)) {
250 // Remove the register from the allowed set.
251 VRAllowed::iterator eraseItr
=
252 std::find(vrAllowed
.begin(), vrAllowed
.end(), preg
);
254 if (eraseItr
!= vrAllowed
.end()) {
255 vrAllowed
.erase(eraseItr
);
258 // Also remove any aliases.
259 const unsigned *aliasItr
= tri
->getAliasSet(preg
);
261 for (; *aliasItr
!= 0; ++aliasItr
) {
262 VRAllowed::iterator eraseItr
=
263 std::find(vrAllowed
.begin(), vrAllowed
.end(), *aliasItr
);
265 if (eraseItr
!= vrAllowed
.end()) {
266 vrAllowed
.erase(eraseItr
);
272 // Construct the node.
273 PBQP::Graph::NodeItr node
=
274 g
.addNode(PBQP::Vector(vrAllowed
.size() + 1, 0));
276 // Record the mapping and allowed set in the problem.
277 p
->recordVReg(vreg
, node
, vrAllowed
.begin(), vrAllowed
.end());
279 PBQP::PBQPNum spillCost
= (vregLI
->weight
!= 0.0) ?
280 vregLI
->weight
: std::numeric_limits
<PBQP::PBQPNum
>::min();
282 addSpillCosts(g
.getNodeCosts(node
), spillCost
);
285 for (RegSet::const_iterator vr1Itr
= vregs
.begin(), vrEnd
= vregs
.end();
286 vr1Itr
!= vrEnd
; ++vr1Itr
) {
287 unsigned vr1
= *vr1Itr
;
288 const LiveInterval
&l1
= lis
->getInterval(vr1
);
289 const PBQPRAProblem::AllowedSet
&vr1Allowed
= p
->getAllowedSet(vr1
);
291 for (RegSet::const_iterator vr2Itr
= llvm::next(vr1Itr
);
292 vr2Itr
!= vrEnd
; ++vr2Itr
) {
293 unsigned vr2
= *vr2Itr
;
294 const LiveInterval
&l2
= lis
->getInterval(vr2
);
295 const PBQPRAProblem::AllowedSet
&vr2Allowed
= p
->getAllowedSet(vr2
);
297 assert(!l2
.empty() && "Empty interval in vreg set?");
298 if (l1
.overlaps(l2
)) {
299 PBQP::Graph::EdgeItr edge
=
300 g
.addEdge(p
->getNodeForVReg(vr1
), p
->getNodeForVReg(vr2
),
301 PBQP::Matrix(vr1Allowed
.size()+1, vr2Allowed
.size()+1, 0));
303 addInterferenceCosts(g
.getEdgeCosts(edge
), vr1Allowed
, vr2Allowed
, tri
);
311 void PBQPBuilder::addSpillCosts(PBQP::Vector
&costVec
,
312 PBQP::PBQPNum spillCost
) {
313 costVec
[0] = spillCost
;
316 void PBQPBuilder::addInterferenceCosts(
317 PBQP::Matrix
&costMat
,
318 const PBQPRAProblem::AllowedSet
&vr1Allowed
,
319 const PBQPRAProblem::AllowedSet
&vr2Allowed
,
320 const TargetRegisterInfo
*tri
) {
321 assert(costMat
.getRows() == vr1Allowed
.size() + 1 && "Matrix height mismatch.");
322 assert(costMat
.getCols() == vr2Allowed
.size() + 1 && "Matrix width mismatch.");
324 for (unsigned i
= 0; i
!= vr1Allowed
.size(); ++i
) {
325 unsigned preg1
= vr1Allowed
[i
];
327 for (unsigned j
= 0; j
!= vr2Allowed
.size(); ++j
) {
328 unsigned preg2
= vr2Allowed
[j
];
330 if (tri
->regsOverlap(preg1
, preg2
)) {
331 costMat
[i
+ 1][j
+ 1] = std::numeric_limits
<PBQP::PBQPNum
>::infinity();
337 std::auto_ptr
<PBQPRAProblem
> PBQPBuilderWithCoalescing::build(
339 const LiveIntervals
*lis
,
340 const MachineLoopInfo
*loopInfo
,
341 const RegSet
&vregs
) {
343 std::auto_ptr
<PBQPRAProblem
> p
= PBQPBuilder::build(mf
, lis
, loopInfo
, vregs
);
344 PBQP::Graph
&g
= p
->getGraph();
346 const TargetMachine
&tm
= mf
->getTarget();
347 CoalescerPair
cp(*tm
.getInstrInfo(), *tm
.getRegisterInfo());
349 // Scan the machine function and add a coalescing cost whenever CoalescerPair
351 for (MachineFunction::const_iterator mbbItr
= mf
->begin(),
353 mbbItr
!= mbbEnd
; ++mbbItr
) {
354 const MachineBasicBlock
*mbb
= &*mbbItr
;
356 for (MachineBasicBlock::const_iterator miItr
= mbb
->begin(),
358 miItr
!= miEnd
; ++miItr
) {
359 const MachineInstr
*mi
= &*miItr
;
361 if (!cp
.setRegisters(mi
)) {
362 continue; // Not coalescable.
365 if (cp
.getSrcReg() == cp
.getDstReg()) {
366 continue; // Already coalesced.
369 unsigned dst
= cp
.getDstReg(),
370 src
= cp
.getSrcReg();
372 const float copyFactor
= 0.5; // Cost of copy relative to load. Current
373 // value plucked randomly out of the air.
375 PBQP::PBQPNum cBenefit
=
376 copyFactor
* LiveIntervals::getSpillWeight(false, true,
377 loopInfo
->getLoopDepth(mbb
));
380 if (!lis
->isAllocatable(dst
)) {
384 const PBQPRAProblem::AllowedSet
&allowed
= p
->getAllowedSet(src
);
385 unsigned pregOpt
= 0;
386 while (pregOpt
< allowed
.size() && allowed
[pregOpt
] != dst
) {
389 if (pregOpt
< allowed
.size()) {
390 ++pregOpt
; // +1 to account for spill option.
391 PBQP::Graph::NodeItr node
= p
->getNodeForVReg(src
);
392 addPhysRegCoalesce(g
.getNodeCosts(node
), pregOpt
, cBenefit
);
395 const PBQPRAProblem::AllowedSet
*allowed1
= &p
->getAllowedSet(dst
);
396 const PBQPRAProblem::AllowedSet
*allowed2
= &p
->getAllowedSet(src
);
397 PBQP::Graph::NodeItr node1
= p
->getNodeForVReg(dst
);
398 PBQP::Graph::NodeItr node2
= p
->getNodeForVReg(src
);
399 PBQP::Graph::EdgeItr edge
= g
.findEdge(node1
, node2
);
400 if (edge
== g
.edgesEnd()) {
401 edge
= g
.addEdge(node1
, node2
, PBQP::Matrix(allowed1
->size() + 1,
402 allowed2
->size() + 1,
405 if (g
.getEdgeNode1(edge
) == node2
) {
406 std::swap(node1
, node2
);
407 std::swap(allowed1
, allowed2
);
411 addVirtRegCoalesce(g
.getEdgeCosts(edge
), *allowed1
, *allowed2
,
420 void PBQPBuilderWithCoalescing::addPhysRegCoalesce(PBQP::Vector
&costVec
,
422 PBQP::PBQPNum benefit
) {
423 costVec
[pregOption
] += -benefit
;
426 void PBQPBuilderWithCoalescing::addVirtRegCoalesce(
427 PBQP::Matrix
&costMat
,
428 const PBQPRAProblem::AllowedSet
&vr1Allowed
,
429 const PBQPRAProblem::AllowedSet
&vr2Allowed
,
430 PBQP::PBQPNum benefit
) {
432 assert(costMat
.getRows() == vr1Allowed
.size() + 1 && "Size mismatch.");
433 assert(costMat
.getCols() == vr2Allowed
.size() + 1 && "Size mismatch.");
435 for (unsigned i
= 0; i
!= vr1Allowed
.size(); ++i
) {
436 unsigned preg1
= vr1Allowed
[i
];
437 for (unsigned j
= 0; j
!= vr2Allowed
.size(); ++j
) {
438 unsigned preg2
= vr2Allowed
[j
];
440 if (preg1
== preg2
) {
441 costMat
[i
+ 1][j
+ 1] += -benefit
;
448 void RegAllocPBQP::getAnalysisUsage(AnalysisUsage
&au
) const {
449 au
.addRequired
<SlotIndexes
>();
450 au
.addPreserved
<SlotIndexes
>();
451 au
.addRequired
<LiveIntervals
>();
452 //au.addRequiredID(SplitCriticalEdgesID);
453 au
.addRequired
<RegisterCoalescer
>();
455 au
.addRequiredID(*customPassID
);
456 au
.addRequired
<CalculateSpillWeights
>();
457 au
.addRequired
<LiveStacks
>();
458 au
.addPreserved
<LiveStacks
>();
459 au
.addRequired
<MachineLoopInfo
>();
460 au
.addPreserved
<MachineLoopInfo
>();
461 if (pbqpPreSplitting
)
462 au
.addRequired
<LoopSplitter
>();
463 au
.addRequired
<VirtRegMap
>();
464 au
.addRequired
<RenderMachineFunction
>();
465 MachineFunctionPass::getAnalysisUsage(au
);
468 void RegAllocPBQP::findVRegIntervalsToAlloc() {
470 // Iterate over all live ranges.
471 for (LiveIntervals::iterator itr
= lis
->begin(), end
= lis
->end();
474 // Ignore physical ones.
475 if (TargetRegisterInfo::isPhysicalRegister(itr
->first
))
478 LiveInterval
*li
= itr
->second
;
480 // If this live interval is non-empty we will use pbqp to allocate it.
481 // Empty intervals we allocate in a simple post-processing stage in
484 vregsToAlloc
.insert(li
->reg
);
486 emptyIntervalVRegs
.insert(li
->reg
);
491 void RegAllocPBQP::addStackInterval(const LiveInterval
*spilled
,
492 MachineRegisterInfo
* mri
) {
493 int stackSlot
= vrm
->getStackSlot(spilled
->reg
);
495 if (stackSlot
== VirtRegMap::NO_STACK_SLOT
) {
499 const TargetRegisterClass
*RC
= mri
->getRegClass(spilled
->reg
);
500 LiveInterval
&stackInterval
= lss
->getOrCreateInterval(stackSlot
, RC
);
503 if (stackInterval
.getNumValNums() != 0) {
504 vni
= stackInterval
.getValNumInfo(0);
506 vni
= stackInterval
.getNextValue(
507 SlotIndex(), 0, lss
->getVNInfoAllocator());
510 LiveInterval
&rhsInterval
= lis
->getInterval(spilled
->reg
);
511 stackInterval
.MergeRangesInAsValue(rhsInterval
, vni
);
514 bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAProblem
&problem
,
515 const PBQP::Solution
&solution
) {
516 // Set to true if we have any spills
517 bool anotherRoundNeeded
= false;
519 // Clear the existing allocation.
522 const PBQP::Graph
&g
= problem
.getGraph();
523 // Iterate over the nodes mapping the PBQP solution to a register
525 for (PBQP::Graph::ConstNodeItr node
= g
.nodesBegin(),
526 nodeEnd
= g
.nodesEnd();
527 node
!= nodeEnd
; ++node
) {
528 unsigned vreg
= problem
.getVRegForNode(node
);
529 unsigned alloc
= solution
.getSelection(node
);
531 if (problem
.isPRegOption(vreg
, alloc
)) {
532 unsigned preg
= problem
.getPRegForOption(vreg
, alloc
);
533 DEBUG(dbgs() << "VREG " << vreg
<< " -> " << tri
->getName(preg
) << "\n");
534 assert(preg
!= 0 && "Invalid preg selected.");
535 vrm
->assignVirt2Phys(vreg
, preg
);
536 } else if (problem
.isSpillOption(vreg
, alloc
)) {
537 vregsToAlloc
.erase(vreg
);
538 const LiveInterval
* spillInterval
= &lis
->getInterval(vreg
);
539 double oldWeight
= spillInterval
->weight
;
540 rmf
->rememberUseDefs(spillInterval
);
541 std::vector
<LiveInterval
*> newSpills
=
542 lis
->addIntervalsForSpills(*spillInterval
, 0, loopInfo
, *vrm
);
543 addStackInterval(spillInterval
, mri
);
544 rmf
->rememberSpills(spillInterval
, newSpills
);
547 DEBUG(dbgs() << "VREG " << vreg
<< " -> SPILLED (Cost: "
548 << oldWeight
<< ", New vregs: ");
550 // Copy any newly inserted live intervals into the list of regs to
552 for (std::vector
<LiveInterval
*>::const_iterator
553 itr
= newSpills
.begin(), end
= newSpills
.end();
555 assert(!(*itr
)->empty() && "Empty spill range.");
556 DEBUG(dbgs() << (*itr
)->reg
<< " ");
557 vregsToAlloc
.insert((*itr
)->reg
);
560 DEBUG(dbgs() << ")\n");
562 // We need another round if spill intervals were added.
563 anotherRoundNeeded
|= !newSpills
.empty();
565 assert(false && "Unknown allocation option.");
569 return !anotherRoundNeeded
;
573 void RegAllocPBQP::finalizeAlloc() const {
574 typedef LiveIntervals::iterator LIIterator
;
575 typedef LiveInterval::Ranges::const_iterator LRIterator
;
577 // First allocate registers for the empty intervals.
578 for (RegSet::const_iterator
579 itr
= emptyIntervalVRegs
.begin(), end
= emptyIntervalVRegs
.end();
581 LiveInterval
*li
= &lis
->getInterval(*itr
);
583 unsigned physReg
= vrm
->getRegAllocPref(li
->reg
);
586 const TargetRegisterClass
*liRC
= mri
->getRegClass(li
->reg
);
587 physReg
= liRC
->getRawAllocationOrder(*mf
).front();
590 vrm
->assignVirt2Phys(li
->reg
, physReg
);
593 // Finally iterate over the basic blocks to compute and set the live-in sets.
594 SmallVector
<MachineBasicBlock
*, 8> liveInMBBs
;
595 MachineBasicBlock
*entryMBB
= &*mf
->begin();
597 for (LIIterator liItr
= lis
->begin(), liEnd
= lis
->end();
598 liItr
!= liEnd
; ++liItr
) {
600 const LiveInterval
*li
= liItr
->second
;
603 // Get the physical register for this interval
604 if (TargetRegisterInfo::isPhysicalRegister(li
->reg
)) {
606 } else if (vrm
->isAssignedReg(li
->reg
)) {
607 reg
= vrm
->getPhys(li
->reg
);
609 // Ranges which are assigned a stack slot only are ignored.
614 // Filter out zero regs - they're for intervals that were spilled.
618 // Iterate over the ranges of the current interval...
619 for (LRIterator lrItr
= li
->begin(), lrEnd
= li
->end();
620 lrItr
!= lrEnd
; ++lrItr
) {
622 // Find the set of basic blocks which this range is live into...
623 if (lis
->findLiveInMBBs(lrItr
->start
, lrItr
->end
, liveInMBBs
)) {
624 // And add the physreg for this interval to their live-in sets.
625 for (unsigned i
= 0; i
!= liveInMBBs
.size(); ++i
) {
626 if (liveInMBBs
[i
] != entryMBB
) {
627 if (!liveInMBBs
[i
]->isLiveIn(reg
)) {
628 liveInMBBs
[i
]->addLiveIn(reg
);
639 bool RegAllocPBQP::runOnMachineFunction(MachineFunction
&MF
) {
642 tm
= &mf
->getTarget();
643 tri
= tm
->getRegisterInfo();
644 tii
= tm
->getInstrInfo();
645 mri
= &mf
->getRegInfo();
647 lis
= &getAnalysis
<LiveIntervals
>();
648 lss
= &getAnalysis
<LiveStacks
>();
649 loopInfo
= &getAnalysis
<MachineLoopInfo
>();
650 rmf
= &getAnalysis
<RenderMachineFunction
>();
652 vrm
= &getAnalysis
<VirtRegMap
>();
655 DEBUG(dbgs() << "PBQP Register Allocating for " << mf
->getFunction()->getName() << "\n");
657 // Allocator main loop:
659 // * Map current regalloc problem to a PBQP problem
660 // * Solve the PBQP problem
661 // * Map the solution back to a register allocation
662 // * Spill if necessary
664 // This process is continued till no more spills are generated.
666 // Find the vreg intervals in need of allocation.
667 findVRegIntervalsToAlloc();
669 // If there are non-empty intervals allocate them using pbqp.
670 if (!vregsToAlloc
.empty()) {
672 bool pbqpAllocComplete
= false;
675 while (!pbqpAllocComplete
) {
676 DEBUG(dbgs() << " PBQP Regalloc round " << round
<< ":\n");
678 std::auto_ptr
<PBQPRAProblem
> problem
=
679 builder
->build(mf
, lis
, loopInfo
, vregsToAlloc
);
680 PBQP::Solution solution
=
681 PBQP::HeuristicSolver
<PBQP::Heuristics::Briggs
>::solve(
682 problem
->getGraph());
684 pbqpAllocComplete
= mapPBQPToRegAlloc(*problem
, solution
);
690 // Finalise allocation, allocate empty ranges.
693 rmf
->renderMachineFunction("After PBQP register allocation.", vrm
);
695 vregsToAlloc
.clear();
696 emptyIntervalVRegs
.clear();
698 DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm
<< "\n");
701 std::auto_ptr
<VirtRegRewriter
> rewriter(createVirtRegRewriter());
703 rewriter
->runOnMachineFunction(*mf
, *vrm
, lis
);
708 FunctionPass
* llvm::createPBQPRegisterAllocator(
709 std::auto_ptr
<PBQPBuilder
> builder
,
710 char *customPassID
) {
711 return new RegAllocPBQP(builder
, customPassID
);
714 FunctionPass
* llvm::createDefaultPBQPRegisterAllocator() {
715 if (pbqpCoalescing
) {
716 return createPBQPRegisterAllocator(
717 std::auto_ptr
<PBQPBuilder
>(new PBQPBuilderWithCoalescing()));
719 return createPBQPRegisterAllocator(
720 std::auto_ptr
<PBQPBuilder
>(new PBQPBuilder()));