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
59using namespace llvm;
60
61static RegisterRegAlloc
62registerPBQPRepAlloc("pbqp", "PBQP register allocator",
63                       createDefaultPBQPRegisterAllocator);
64
65static cl::opt<bool>
66pbqpCoalescing("pbqp-coalescing",
67                cl::desc("Attempt coalescing during PBQP register allocation."),
68                cl::init(false), cl::Hidden);
69
70static cl::opt<bool>
71pbqpPreSplitting("pbqp-pre-splitting",
72                 cl::desc("Pre-split before PBQP register allocation."),
73                 cl::init(false), cl::Hidden);
74
75namespace {
76
77///
78/// PBQP based allocators solve the register allocation problem by mapping
79/// register allocation problems to Partitioned Boolean Quadratic
80/// Programming problems.
81class RegAllocPBQP : public MachineFunctionPass {
82public:
83
84  static char ID;
85
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());
98  }
99
100  /// Return the pass name.
101  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
111private:
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
159char RegAllocPBQP::ID = 0;
160
161} // End anonymous namespace.
162
163unsigned 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
169PBQP::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
176const 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;
181  return allowedSet;
182}
183
184unsigned 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
192std::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
311void PBQPBuilder::addSpillCosts(PBQP::Vector &costVec,
312                                PBQP::PBQPNum spillCost) {
313  costVec[0] = spillCost;
314}
315
316void 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
337std::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
420void PBQPBuilderWithCoalescing::addPhysRegCoalesce(PBQP::Vector &costVec,
421                                                   unsigned pregOption,
422                                                   PBQP::PBQPNum benefit) {
423  costVec[pregOption] += -benefit;
424}
425
426void 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
448void 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
468void 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
491void 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
514bool 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
573void 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
639bool 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
708FunctionPass* llvm::createPBQPRegisterAllocator(
709                                           std::auto_ptr<PBQPBuilder> builder,
710                                           char *customPassID) {
711  return new RegAllocPBQP(builder, customPassID);
712}
713
714FunctionPass* 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