1 //===------ RegAllocPBQP.cpp ---- PBQP Register Allocator -------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
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.
16 //
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:
20 //
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.
24 //
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,
28 // NY, USA, 139-148.
29 //
30 //===----------------------------------------------------------------------===//
31
32 #define DEBUG_TYPE "regalloc"
33
34 #include "RenderMachineFunction.h"
35 #include "Splitter.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"
54 #include <limits>
55 #include <memory>
56 #include <set>
57 #include <vector>
58
59 using namespace llvm;
60
61 static RegisterRegAlloc
62 registerPBQPRepAlloc("pbqp", "PBQP register allocator",
63 createDefaultPBQPRegisterAllocator);
64
65 static cl::opt<bool>
66 pbqpCoalescing("pbqp-coalescing",
67 cl::desc("Attempt coalescing during PBQP register allocation."),
68 cl::init(false), cl::Hidden);
69
70 static cl::opt<bool>
71 pbqpPreSplitting("pbqp-pre-splitting",
72 cl::desc("Pre-split before PBQP register allocation."),
73 cl::init(false), cl::Hidden);
74
75 namespace {
76
77 ///
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 {
82 public:
83
84 static char ID;
85
86 /// Construct a PBQP register allocator.
RegAllocPBQP(std::auto_ptr<PBQPBuilder> b,char * cPassID=0)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());
98 }
99
100 /// Return the pass name.
getPassName() const101 virtual const char* getPassName() const {
102 return "PBQP Register Allocator";
103 }
104
105 /// PBQP analysis usage.
106 virtual void getAnalysisUsage(AnalysisUsage &au) const;
107
108 /// Perform register allocation
109 virtual bool runOnMachineFunction(MachineFunction &MF);
110
111 private:
112
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;
121
122
123 std::auto_ptr<PBQPBuilder> builder;
124
125 char *customPassID;
126
127 MachineFunction *mf;
128 const TargetMachine *tm;
129 const TargetRegisterInfo *tri;
130 const TargetInstrInfo *tii;
131 const MachineLoopInfo *loopInfo;
132 MachineRegisterInfo *mri;
133 RenderMachineFunction *rmf;
134
135 LiveIntervals *lis;
136 LiveStacks *lss;
137 VirtRegMap *vrm;
138
139 RegSet vregsToAlloc, emptyIntervalVRegs;
140
141 /// \brief Finds the initial set of vreg intervals to allocate.
142 void findVRegIntervalsToAlloc();
143
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);
147
148 /// \brief Given a solved PBQP problem maps this solution back to a register
149 /// assignment.
150 bool mapPBQPToRegAlloc(const PBQPRAProblem &problem,
151 const PBQP::Solution &solution);
152
153 /// \brief Postprocessing before final spilling. Sets basic block "live in"
154 /// variables.
155 void finalizeAlloc() const;
156
157 };
158
159 char RegAllocPBQP::ID = 0;
160
161 } // End anonymous namespace.
162
getVRegForNode(PBQP::Graph::ConstNodeItr node) const163 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;
167 }
168
getNodeForVReg(unsigned vreg) const169 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;
173
174 }
175
176 const PBQPRAProblem::AllowedSet&
getAllowedSet(unsigned vreg) const177 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;
181 return allowedSet;
182 }
183
getPRegForOption(unsigned vreg,unsigned option) const184 unsigned PBQPRAProblem::getPRegForOption(unsigned vreg, unsigned option) const {
185 assert(isPRegOption(vreg, option) && "Not a preg option.");
186
187 const AllowedSet& allowedSet = getAllowedSet(vreg);
188 assert(option <= allowedSet.size() && "Option outside allowed set.");
189 return allowedSet[option - 1];
190 }
191
build(MachineFunction * mf,const LiveIntervals * lis,const MachineLoopInfo * loopInfo,const RegSet & vregs)192 std::auto_ptr<PBQPRAProblem> PBQPBuilder::build(MachineFunction *mf,
193 const LiveIntervals *lis,
194 const MachineLoopInfo *loopInfo,
195 const RegSet &vregs) {
196
197 typedef std::vector<const LiveInterval*> LIVector;
198
199 MachineRegisterInfo *mri = &mf->getRegInfo();
200 const TargetRegisterInfo *tri = mf->getTarget().getRegisterInfo();
201
202 std::auto_ptr<PBQPRAProblem> p(new PBQPRAProblem());
203 PBQP::Graph &g = p->getGraph();
204 RegSet pregs;
205
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();
208 itr != end; ++itr) {
209 if (TargetRegisterInfo::isPhysicalRegister(itr->first)) {
210 pregs.insert(itr->first);
211 mri->setPhysRegUsed(itr->first);
212 }
213 }
214
215 BitVector reservedRegs = tri->getReservedRegs(*mf);
216
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);
223
224 // Compute an initial allowed set for the current vreg.
225 typedef std::vector<unsigned> VRAllowed;
226 VRAllowed 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);
232 }
233 }
234
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);
241
242 if (pregLI->empty()) {
243 continue;
244 }
245
246 if (!vregLI->overlaps(*pregLI)) {
247 continue;
248 }
249
250 // Remove the register from the allowed set.
251 VRAllowed::iterator eraseItr =
252 std::find(vrAllowed.begin(), vrAllowed.end(), preg);
253
254 if (eraseItr != vrAllowed.end()) {
255 vrAllowed.erase(eraseItr);
256 }
257
258 // Also remove any aliases.
259 const unsigned *aliasItr = tri->getAliasSet(preg);
260 if (aliasItr != 0) {
261 for (; *aliasItr != 0; ++aliasItr) {
262 VRAllowed::iterator eraseItr =
263 std::find(vrAllowed.begin(), vrAllowed.end(), *aliasItr);
264
265 if (eraseItr != vrAllowed.end()) {
266 vrAllowed.erase(eraseItr);
267 }
268 }
269 }
270 }
271
272 // Construct the node.
273 PBQP::Graph::NodeItr node =
274 g.addNode(PBQP::Vector(vrAllowed.size() + 1, 0));
275
276 // Record the mapping and allowed set in the problem.
277 p->recordVReg(vreg, node, vrAllowed.begin(), vrAllowed.end());
278
279 PBQP::PBQPNum spillCost = (vregLI->weight != 0.0) ?
280 vregLI->weight : std::numeric_limits<PBQP::PBQPNum>::min();
281
282 addSpillCosts(g.getNodeCosts(node), spillCost);
283 }
284
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);
290
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);
296
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));
302
303 addInterferenceCosts(g.getEdgeCosts(edge), vr1Allowed, vr2Allowed, tri);
304 }
305 }
306 }
307
308 return p;
309 }
310
addSpillCosts(PBQP::Vector & costVec,PBQP::PBQPNum spillCost)311 void PBQPBuilder::addSpillCosts(PBQP::Vector &costVec,
312 PBQP::PBQPNum spillCost) {
313 costVec[0] = spillCost;
314 }
315
addInterferenceCosts(PBQP::Matrix & costMat,const PBQPRAProblem::AllowedSet & vr1Allowed,const PBQPRAProblem::AllowedSet & vr2Allowed,const TargetRegisterInfo * tri)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.");
323
324 for (unsigned i = 0; i != vr1Allowed.size(); ++i) {
325 unsigned preg1 = vr1Allowed[i];
326
327 for (unsigned j = 0; j != vr2Allowed.size(); ++j) {
328 unsigned preg2 = vr2Allowed[j];
329
330 if (tri->regsOverlap(preg1, preg2)) {
331 costMat[i + 1][j + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity();
332 }
333 }
334 }
335 }
336
build(MachineFunction * mf,const LiveIntervals * lis,const MachineLoopInfo * loopInfo,const RegSet & vregs)337 std::auto_ptr<PBQPRAProblem> PBQPBuilderWithCoalescing::build(
338 MachineFunction *mf,
339 const LiveIntervals *lis,
340 const MachineLoopInfo *loopInfo,
341 const RegSet &vregs) {
342
343 std::auto_ptr<PBQPRAProblem> p = PBQPBuilder::build(mf, lis, loopInfo, vregs);
344 PBQP::Graph &g = p->getGraph();
345
346 const TargetMachine &tm = mf->getTarget();
347 CoalescerPair cp(*tm.getInstrInfo(), *tm.getRegisterInfo());
348
349 // Scan the machine function and add a coalescing cost whenever CoalescerPair
350 // gives the Ok.
351 for (MachineFunction::const_iterator mbbItr = mf->begin(),
352 mbbEnd = mf->end();
353 mbbItr != mbbEnd; ++mbbItr) {
354 const MachineBasicBlock *mbb = &*mbbItr;
355
356 for (MachineBasicBlock::const_iterator miItr = mbb->begin(),
357 miEnd = mbb->end();
358 miItr != miEnd; ++miItr) {
359 const MachineInstr *mi = &*miItr;
360
361 if (!cp.setRegisters(mi)) {
362 continue; // Not coalescable.
363 }
364
365 if (cp.getSrcReg() == cp.getDstReg()) {
366 continue; // Already coalesced.
367 }
368
369 unsigned dst = cp.getDstReg(),
370 src = cp.getSrcReg();
371
372 const float copyFactor = 0.5; // Cost of copy relative to load. Current
373 // value plucked randomly out of the air.
374
375 PBQP::PBQPNum cBenefit =
376 copyFactor * LiveIntervals::getSpillWeight(false, true,
377 loopInfo->getLoopDepth(mbb));
378
379 if (cp.isPhys()) {
380 if (!lis->isAllocatable(dst)) {
381 continue;
382 }
383
384 const PBQPRAProblem::AllowedSet &allowed = p->getAllowedSet(src);
385 unsigned pregOpt = 0;
386 while (pregOpt < allowed.size() && allowed[pregOpt] != dst) {
387 ++pregOpt;
388 }
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);
393 }
394 } else {
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,
403 0));
404 } else {
405 if (g.getEdgeNode1(edge) == node2) {
406 std::swap(node1, node2);
407 std::swap(allowed1, allowed2);
408 }
409 }
410
411 addVirtRegCoalesce(g.getEdgeCosts(edge), *allowed1, *allowed2,
412 cBenefit);
413 }
414 }
415 }
416
417 return p;
418 }
419
addPhysRegCoalesce(PBQP::Vector & costVec,unsigned pregOption,PBQP::PBQPNum benefit)420 void PBQPBuilderWithCoalescing::addPhysRegCoalesce(PBQP::Vector &costVec,
421 unsigned pregOption,
422 PBQP::PBQPNum benefit) {
423 costVec[pregOption] += -benefit;
424 }
425
addVirtRegCoalesce(PBQP::Matrix & costMat,const PBQPRAProblem::AllowedSet & vr1Allowed,const PBQPRAProblem::AllowedSet & vr2Allowed,PBQP::PBQPNum benefit)426 void PBQPBuilderWithCoalescing::addVirtRegCoalesce(
427 PBQP::Matrix &costMat,
428 const PBQPRAProblem::AllowedSet &vr1Allowed,
429 const PBQPRAProblem::AllowedSet &vr2Allowed,
430 PBQP::PBQPNum benefit) {
431
432 assert(costMat.getRows() == vr1Allowed.size() + 1 && "Size mismatch.");
433 assert(costMat.getCols() == vr2Allowed.size() + 1 && "Size mismatch.");
434
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];
439
440 if (preg1 == preg2) {
441 costMat[i + 1][j + 1] += -benefit;
442 }
443 }
444 }
445 }
446
447
getAnalysisUsage(AnalysisUsage & au) const448 void RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const {
449 au.addRequired<SlotIndexes>();
450 au.addPreserved<SlotIndexes>();
451 au.addRequired<LiveIntervals>();
452 //au.addRequiredID(SplitCriticalEdgesID);
453 au.addRequiredID(RegisterCoalescerPassID);
454 if (customPassID)
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);
466 }
467
findVRegIntervalsToAlloc()468 void RegAllocPBQP::findVRegIntervalsToAlloc() {
469
470 // Iterate over all live ranges.
471 for (LiveIntervals::iterator itr = lis->begin(), end = lis->end();
472 itr != end; ++itr) {
473
474 // Ignore physical ones.
475 if (TargetRegisterInfo::isPhysicalRegister(itr->first))
476 continue;
477
478 LiveInterval *li = itr->second;
479
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
482 // finalizeAlloc.
483 if (!li->empty()) {
484 vregsToAlloc.insert(li->reg);
485 } else {
486 emptyIntervalVRegs.insert(li->reg);
487 }
488 }
489 }
490
addStackInterval(const LiveInterval * spilled,MachineRegisterInfo * mri)491 void RegAllocPBQP::addStackInterval(const LiveInterval *spilled,
492 MachineRegisterInfo* mri) {
493 int stackSlot = vrm->getStackSlot(spilled->reg);
494
495 if (stackSlot == VirtRegMap::NO_STACK_SLOT) {
496 return;
497 }
498
499 const TargetRegisterClass *RC = mri->getRegClass(spilled->reg);
500 LiveInterval &stackInterval = lss->getOrCreateInterval(stackSlot, RC);
501
502 VNInfo *vni;
503 if (stackInterval.getNumValNums() != 0) {
504 vni = stackInterval.getValNumInfo(0);
505 } else {
506 vni = stackInterval.getNextValue(
507 SlotIndex(), 0, lss->getVNInfoAllocator());
508 }
509
510 LiveInterval &rhsInterval = lis->getInterval(spilled->reg);
511 stackInterval.MergeRangesInAsValue(rhsInterval, vni);
512 }
513
mapPBQPToRegAlloc(const PBQPRAProblem & problem,const PBQP::Solution & solution)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;
518
519 // Clear the existing allocation.
520 vrm->clearAllVirt();
521
522 const PBQP::Graph &g = problem.getGraph();
523 // Iterate over the nodes mapping the PBQP solution to a register
524 // assignment.
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);
530
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);
545
546 (void) oldWeight;
547 DEBUG(dbgs() << "VREG " << vreg << " -> SPILLED (Cost: "
548 << oldWeight << ", New vregs: ");
549
550 // Copy any newly inserted live intervals into the list of regs to
551 // allocate.
552 for (std::vector<LiveInterval*>::const_iterator
553 itr = newSpills.begin(), end = newSpills.end();
554 itr != end; ++itr) {
555 assert(!(*itr)->empty() && "Empty spill range.");
556 DEBUG(dbgs() << (*itr)->reg << " ");
557 vregsToAlloc.insert((*itr)->reg);
558 }
559
560 DEBUG(dbgs() << ")\n");
561
562 // We need another round if spill intervals were added.
563 anotherRoundNeeded |= !newSpills.empty();
564 } else {
565 assert(false && "Unknown allocation option.");
566 }
567 }
568
569 return !anotherRoundNeeded;
570 }
571
572
finalizeAlloc() const573 void RegAllocPBQP::finalizeAlloc() const {
574 typedef LiveIntervals::iterator LIIterator;
575 typedef LiveInterval::Ranges::const_iterator LRIterator;
576
577 // First allocate registers for the empty intervals.
578 for (RegSet::const_iterator
579 itr = emptyIntervalVRegs.begin(), end = emptyIntervalVRegs.end();
580 itr != end; ++itr) {
581 LiveInterval *li = &lis->getInterval(*itr);
582
583 unsigned physReg = vrm->getRegAllocPref(li->reg);
584
585 if (physReg == 0) {
586 const TargetRegisterClass *liRC = mri->getRegClass(li->reg);
587 physReg = liRC->getRawAllocationOrder(*mf).front();
588 }
589
590 vrm->assignVirt2Phys(li->reg, physReg);
591 }
592
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();
596
597 for (LIIterator liItr = lis->begin(), liEnd = lis->end();
598 liItr != liEnd; ++liItr) {
599
600 const LiveInterval *li = liItr->second;
601 unsigned reg = 0;
602
603 // Get the physical register for this interval
604 if (TargetRegisterInfo::isPhysicalRegister(li->reg)) {
605 reg = li->reg;
606 } else if (vrm->isAssignedReg(li->reg)) {
607 reg = vrm->getPhys(li->reg);
608 } else {
609 // Ranges which are assigned a stack slot only are ignored.
610 continue;
611 }
612
613 if (reg == 0) {
614 // Filter out zero regs - they're for intervals that were spilled.
615 continue;
616 }
617
618 // Iterate over the ranges of the current interval...
619 for (LRIterator lrItr = li->begin(), lrEnd = li->end();
620 lrItr != lrEnd; ++lrItr) {
621
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);
629 }
630 }
631 }
632 liveInMBBs.clear();
633 }
634 }
635 }
636
637 }
638
runOnMachineFunction(MachineFunction & MF)639 bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) {
640
641 mf = &MF;
642 tm = &mf->getTarget();
643 tri = tm->getRegisterInfo();
644 tii = tm->getInstrInfo();
645 mri = &mf->getRegInfo();
646
647 lis = &getAnalysis<LiveIntervals>();
648 lss = &getAnalysis<LiveStacks>();
649 loopInfo = &getAnalysis<MachineLoopInfo>();
650 rmf = &getAnalysis<RenderMachineFunction>();
651
652 vrm = &getAnalysis<VirtRegMap>();
653
654
655 DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n");
656
657 // Allocator main loop:
658 //
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
663 //
664 // This process is continued till no more spills are generated.
665
666 // Find the vreg intervals in need of allocation.
667 findVRegIntervalsToAlloc();
668
669 // If there are non-empty intervals allocate them using pbqp.
670 if (!vregsToAlloc.empty()) {
671
672 bool pbqpAllocComplete = false;
673 unsigned round = 0;
674
675 while (!pbqpAllocComplete) {
676 DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n");
677
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());
683
684 pbqpAllocComplete = mapPBQPToRegAlloc(*problem, solution);
685
686 ++round;
687 }
688 }
689
690 // Finalise allocation, allocate empty ranges.
691 finalizeAlloc();
692
693 rmf->renderMachineFunction("After PBQP register allocation.", vrm);
694
695 vregsToAlloc.clear();
696 emptyIntervalVRegs.clear();
697
698 DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm << "\n");
699
700 // Run rewriter
701 std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
702
703 rewriter->runOnMachineFunction(*mf, *vrm, lis);
704
705 return true;
706 }
707
createPBQPRegisterAllocator(std::auto_ptr<PBQPBuilder> builder,char * customPassID)708 FunctionPass* llvm::createPBQPRegisterAllocator(
709 std::auto_ptr<PBQPBuilder> builder,
710 char *customPassID) {
711 return new RegAllocPBQP(builder, customPassID);
712 }
713
createDefaultPBQPRegisterAllocator()714 FunctionPass* llvm::createDefaultPBQPRegisterAllocator() {
715 if (pbqpCoalescing) {
716 return createPBQPRegisterAllocator(
717 std::auto_ptr<PBQPBuilder>(new PBQPBuilderWithCoalescing()));
718 } // else
719 return createPBQPRegisterAllocator(
720 std::auto_ptr<PBQPBuilder>(new PBQPBuilder()));
721 }
722
723 #undef DEBUG_TYPE
724