RegAllocPBQP.cpp revision d76938788b4b682043a74befbb6320ce0077ddc9 
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 "Spiller.h"
36#include "VirtRegMap.h"
37#include "RegisterCoalescer.h"
38#include "llvm/Module.h"
39#include "llvm/Analysis/AliasAnalysis.h"
40#include "llvm/CodeGen/CalcSpillWeights.h"
41#include "llvm/CodeGen/LiveIntervalAnalysis.h"
42#include "llvm/CodeGen/LiveRangeEdit.h"
43#include "llvm/CodeGen/LiveStackAnalysis.h"
44#include "llvm/CodeGen/RegAllocPBQP.h"
45#include "llvm/CodeGen/MachineDominators.h"
46#include "llvm/CodeGen/MachineFunctionPass.h"
47#include "llvm/CodeGen/MachineLoopInfo.h"
48#include "llvm/CodeGen/MachineRegisterInfo.h"
49#include "llvm/CodeGen/PBQP/HeuristicSolver.h"
50#include "llvm/CodeGen/PBQP/Graph.h"
51#include "llvm/CodeGen/PBQP/Heuristics/Briggs.h"
52#include "llvm/CodeGen/RegAllocRegistry.h"
53#include "llvm/Support/Debug.h"
54#include "llvm/Support/raw_ostream.h"
55#include "llvm/Target/TargetInstrInfo.h"
56#include "llvm/Target/TargetMachine.h"
57#include <limits>
58#include <memory>
59#include <set>
60#include <sstream>
61#include <vector>
62
63using namespace llvm;
64
65static RegisterRegAlloc
66registerPBQPRepAlloc("pbqp", "PBQP register allocator",
67                       createDefaultPBQPRegisterAllocator);
68
69static cl::opt<bool>
70pbqpCoalescing("pbqp-coalescing",
71                cl::desc("Attempt coalescing during PBQP register allocation."),
72                cl::init(false), cl::Hidden);
73
74#ifndef NDEBUG
75static cl::opt<bool>
76pbqpDumpGraphs("pbqp-dump-graphs",
77               cl::desc("Dump graphs for each function/round in the compilation unit."),
78               cl::init(false), cl::Hidden);
79#endif
80
81namespace {
82
83///
84/// PBQP based allocators solve the register allocation problem by mapping
85/// register allocation problems to Partitioned Boolean Quadratic
86/// Programming problems.
87class RegAllocPBQP : public MachineFunctionPass {
88public:
89
90  static char ID;
91
92  /// Construct a PBQP register allocator.
93  RegAllocPBQP(std::auto_ptr<PBQPBuilder> b, char *cPassID=0)
94      : MachineFunctionPass(ID), builder(b), customPassID(cPassID) {
95    initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
96    initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
97    initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
98    initializeLiveStacksPass(*PassRegistry::getPassRegistry());
99    initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
100    initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
101    initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry());
102  }
103
104  /// Return the pass name.
105  virtual const char* getPassName() const {
106    return "PBQP Register Allocator";
107  }
108
109  /// PBQP analysis usage.
110  virtual void getAnalysisUsage(AnalysisUsage &au) const;
111
112  /// Perform register allocation
113  virtual bool runOnMachineFunction(MachineFunction &MF);
114
115private:
116
117  typedef std::map<const LiveInterval*, unsigned> LI2NodeMap;
118  typedef std::vector<const LiveInterval*> Node2LIMap;
119  typedef std::vector<unsigned> AllowedSet;
120  typedef std::vector<AllowedSet> AllowedSetMap;
121  typedef std::pair<unsigned, unsigned> RegPair;
122  typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap;
123  typedef std::vector<PBQP::Graph::NodeItr> NodeVector;
124  typedef std::set<unsigned> RegSet;
125
126
127  std::auto_ptr<PBQPBuilder> builder;
128
129  char *customPassID;
130
131  MachineFunction *mf;
132  const TargetMachine *tm;
133  const TargetRegisterInfo *tri;
134  const TargetInstrInfo *tii;
135  const MachineLoopInfo *loopInfo;
136  MachineRegisterInfo *mri;
137  RenderMachineFunction *rmf;
138
139  std::auto_ptr<Spiller> spiller;
140  LiveIntervals *lis;
141  LiveStacks *lss;
142  VirtRegMap *vrm;
143
144  RegSet vregsToAlloc, emptyIntervalVRegs;
145
146  /// \brief Finds the initial set of vreg intervals to allocate.
147  void findVRegIntervalsToAlloc();
148
149  /// \brief Given a solved PBQP problem maps this solution back to a register
150  /// assignment.
151  bool mapPBQPToRegAlloc(const PBQPRAProblem &problem,
152                         const PBQP::Solution &solution);
153
154  /// \brief Postprocessing before final spilling. Sets basic block "live in"
155  /// variables.
156  void finalizeAlloc() const;
157
158};
159
160char RegAllocPBQP::ID = 0;
161
162} // End anonymous namespace.
163
164unsigned PBQPRAProblem::getVRegForNode(PBQP::Graph::ConstNodeItr node) const {
165  Node2VReg::const_iterator vregItr = node2VReg.find(node);
166  assert(vregItr != node2VReg.end() && "No vreg for node.");
167  return vregItr->second;
168}
169
170PBQP::Graph::NodeItr PBQPRAProblem::getNodeForVReg(unsigned vreg) const {
171  VReg2Node::const_iterator nodeItr = vreg2Node.find(vreg);
172  assert(nodeItr != vreg2Node.end() && "No node for vreg.");
173  return nodeItr->second;
174
175}
176
177const PBQPRAProblem::AllowedSet&
178  PBQPRAProblem::getAllowedSet(unsigned vreg) const {
179  AllowedSetMap::const_iterator allowedSetItr = allowedSets.find(vreg);
180  assert(allowedSetItr != allowedSets.end() && "No pregs for vreg.");
181  const AllowedSet &allowedSet = allowedSetItr->second;
182  return allowedSet;
183}
184
185unsigned PBQPRAProblem::getPRegForOption(unsigned vreg, unsigned option) const {
186  assert(isPRegOption(vreg, option) && "Not a preg option.");
187
188  const AllowedSet& allowedSet = getAllowedSet(vreg);
189  assert(option <= allowedSet.size() && "Option outside allowed set.");
190  return allowedSet[option - 1];
191}
192
193std::auto_ptr<PBQPRAProblem> PBQPBuilder::build(MachineFunction *mf,
194                                                const LiveIntervals *lis,
195                                                const MachineLoopInfo *loopInfo,
196                                                const RegSet &vregs) {
197
198  typedef std::vector<const LiveInterval*> LIVector;
199  ArrayRef<SlotIndex> regMaskSlots = lis->getRegMaskSlots();
200  MachineRegisterInfo *mri = &mf->getRegInfo();
201  const TargetRegisterInfo *tri = mf->getTarget().getRegisterInfo();
202
203  std::auto_ptr<PBQPRAProblem> p(new PBQPRAProblem());
204  PBQP::Graph &g = p->getGraph();
205  RegSet pregs;
206
207  // Collect the set of preg intervals, record that they're used in the MF.
208  for (LiveIntervals::const_iterator itr = lis->begin(), end = lis->end();
209       itr != end; ++itr) {
210    if (TargetRegisterInfo::isPhysicalRegister(itr->first)) {
211      pregs.insert(itr->first);
212      mri->setPhysRegUsed(itr->first);
213    }
214  }
215
216  BitVector reservedRegs = tri->getReservedRegs(*mf);
217
218  // Iterate over vregs.
219  for (RegSet::const_iterator vregItr = vregs.begin(), vregEnd = vregs.end();
220       vregItr != vregEnd; ++vregItr) {
221    unsigned vreg = *vregItr;
222    const TargetRegisterClass *trc = mri->getRegClass(vreg);
223    const LiveInterval *vregLI = &lis->getInterval(vreg);
224
225    // Compute an initial allowed set for the current vreg.
226    typedef std::vector<unsigned> VRAllowed;
227    VRAllowed vrAllowed;
228    ArrayRef<uint16_t> rawOrder = trc->getRawAllocationOrder(*mf);
229    for (unsigned i = 0; i != rawOrder.size(); ++i) {
230      unsigned preg = rawOrder[i];
231      if (!reservedRegs.test(preg)) {
232        vrAllowed.push_back(preg);
233      }
234    }
235
236    RegSet overlappingPRegs;
237
238    // Record physical registers whose ranges overlap.
239    for (RegSet::const_iterator pregItr = pregs.begin(),
240                                pregEnd = pregs.end();
241         pregItr != pregEnd; ++pregItr) {
242      unsigned preg = *pregItr;
243      const LiveInterval *pregLI = &lis->getInterval(preg);
244
245      if (pregLI->empty()) {
246        continue;
247      }
248
249      if (vregLI->overlaps(*pregLI))
250        overlappingPRegs.insert(preg);
251    }
252
253    // Record any overlaps with regmask operands.
254    BitVector regMaskOverlaps(tri->getNumRegs());
255    for (ArrayRef<SlotIndex>::iterator rmItr = regMaskSlots.begin(),
256                                       rmEnd = regMaskSlots.end();
257         rmItr != rmEnd; ++rmItr) {
258      SlotIndex rmIdx = *rmItr;
259      if (vregLI->liveAt(rmIdx)) {
260        MachineInstr *rmMI = lis->getInstructionFromIndex(rmIdx);
261        const uint32_t* regMask = 0;
262        for (MachineInstr::mop_iterator mopItr = rmMI->operands_begin(),
263                                        mopEnd = rmMI->operands_end();
264             mopItr != mopEnd; ++mopItr) {
265          if (mopItr->isRegMask()) {
266            regMask = mopItr->getRegMask();
267            break;
268          }
269        }
270        assert(regMask != 0 && "Couldn't find register mask.");
271        regMaskOverlaps.setBitsNotInMask(regMask);
272      }
273    }
274
275    for (unsigned preg = 0; preg < tri->getNumRegs(); ++preg) {
276      if (regMaskOverlaps.test(preg))
277        overlappingPRegs.insert(preg);
278    }
279
280    for (RegSet::const_iterator pregItr = overlappingPRegs.begin(),
281                                pregEnd = overlappingPRegs.end();
282         pregItr != pregEnd; ++pregItr) {
283      unsigned preg = *pregItr;
284
285      // Remove the register from the allowed set.
286      VRAllowed::iterator eraseItr =
287        std::find(vrAllowed.begin(), vrAllowed.end(), preg);
288
289      if (eraseItr != vrAllowed.end()) {
290        vrAllowed.erase(eraseItr);
291      }
292
293      // Also remove any aliases.
294      const uint16_t *aliasItr = tri->getAliasSet(preg);
295      if (aliasItr != 0) {
296        for (; *aliasItr != 0; ++aliasItr) {
297          VRAllowed::iterator eraseItr =
298            std::find(vrAllowed.begin(), vrAllowed.end(), *aliasItr);
299
300          if (eraseItr != vrAllowed.end()) {
301            vrAllowed.erase(eraseItr);
302          }
303        }
304      }
305    }
306
307    // Construct the node.
308    PBQP::Graph::NodeItr node =
309      g.addNode(PBQP::Vector(vrAllowed.size() + 1, 0));
310
311    // Record the mapping and allowed set in the problem.
312    p->recordVReg(vreg, node, vrAllowed.begin(), vrAllowed.end());
313
314    PBQP::PBQPNum spillCost = (vregLI->weight != 0.0) ?
315        vregLI->weight : std::numeric_limits<PBQP::PBQPNum>::min();
316
317    addSpillCosts(g.getNodeCosts(node), spillCost);
318  }
319
320  for (RegSet::const_iterator vr1Itr = vregs.begin(), vrEnd = vregs.end();
321         vr1Itr != vrEnd; ++vr1Itr) {
322    unsigned vr1 = *vr1Itr;
323    const LiveInterval &l1 = lis->getInterval(vr1);
324    const PBQPRAProblem::AllowedSet &vr1Allowed = p->getAllowedSet(vr1);
325
326    for (RegSet::const_iterator vr2Itr = llvm::next(vr1Itr);
327         vr2Itr != vrEnd; ++vr2Itr) {
328      unsigned vr2 = *vr2Itr;
329      const LiveInterval &l2 = lis->getInterval(vr2);
330      const PBQPRAProblem::AllowedSet &vr2Allowed = p->getAllowedSet(vr2);
331
332      assert(!l2.empty() && "Empty interval in vreg set?");
333      if (l1.overlaps(l2)) {
334        PBQP::Graph::EdgeItr edge =
335          g.addEdge(p->getNodeForVReg(vr1), p->getNodeForVReg(vr2),
336                    PBQP::Matrix(vr1Allowed.size()+1, vr2Allowed.size()+1, 0));
337
338        addInterferenceCosts(g.getEdgeCosts(edge), vr1Allowed, vr2Allowed, tri);
339      }
340    }
341  }
342
343  return p;
344}
345
346void PBQPBuilder::addSpillCosts(PBQP::Vector &costVec,
347                                PBQP::PBQPNum spillCost) {
348  costVec[0] = spillCost;
349}
350
351void PBQPBuilder::addInterferenceCosts(
352                                    PBQP::Matrix &costMat,
353                                    const PBQPRAProblem::AllowedSet &vr1Allowed,
354                                    const PBQPRAProblem::AllowedSet &vr2Allowed,
355                                    const TargetRegisterInfo *tri) {
356  assert(costMat.getRows() == vr1Allowed.size() + 1 && "Matrix height mismatch.");
357  assert(costMat.getCols() == vr2Allowed.size() + 1 && "Matrix width mismatch.");
358
359  for (unsigned i = 0; i != vr1Allowed.size(); ++i) {
360    unsigned preg1 = vr1Allowed[i];
361
362    for (unsigned j = 0; j != vr2Allowed.size(); ++j) {
363      unsigned preg2 = vr2Allowed[j];
364
365      if (tri->regsOverlap(preg1, preg2)) {
366        costMat[i + 1][j + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity();
367      }
368    }
369  }
370}
371
372std::auto_ptr<PBQPRAProblem> PBQPBuilderWithCoalescing::build(
373                                                MachineFunction *mf,
374                                                const LiveIntervals *lis,
375                                                const MachineLoopInfo *loopInfo,
376                                                const RegSet &vregs) {
377
378  std::auto_ptr<PBQPRAProblem> p = PBQPBuilder::build(mf, lis, loopInfo, vregs);
379  PBQP::Graph &g = p->getGraph();
380
381  const TargetMachine &tm = mf->getTarget();
382  CoalescerPair cp(*tm.getInstrInfo(), *tm.getRegisterInfo());
383
384  // Scan the machine function and add a coalescing cost whenever CoalescerPair
385  // gives the Ok.
386  for (MachineFunction::const_iterator mbbItr = mf->begin(),
387                                       mbbEnd = mf->end();
388       mbbItr != mbbEnd; ++mbbItr) {
389    const MachineBasicBlock *mbb = &*mbbItr;
390
391    for (MachineBasicBlock::const_iterator miItr = mbb->begin(),
392                                           miEnd = mbb->end();
393         miItr != miEnd; ++miItr) {
394      const MachineInstr *mi = &*miItr;
395
396      if (!cp.setRegisters(mi)) {
397        continue; // Not coalescable.
398      }
399
400      if (cp.getSrcReg() == cp.getDstReg()) {
401        continue; // Already coalesced.
402      }
403
404      unsigned dst = cp.getDstReg(),
405               src = cp.getSrcReg();
406
407      const float copyFactor = 0.5; // Cost of copy relative to load. Current
408      // value plucked randomly out of the air.
409
410      PBQP::PBQPNum cBenefit =
411        copyFactor * LiveIntervals::getSpillWeight(false, true,
412                                                   loopInfo->getLoopDepth(mbb));
413
414      if (cp.isPhys()) {
415        if (!lis->isAllocatable(dst)) {
416          continue;
417        }
418
419        const PBQPRAProblem::AllowedSet &allowed = p->getAllowedSet(src);
420        unsigned pregOpt = 0;
421        while (pregOpt < allowed.size() && allowed[pregOpt] != dst) {
422          ++pregOpt;
423        }
424        if (pregOpt < allowed.size()) {
425          ++pregOpt; // +1 to account for spill option.
426          PBQP::Graph::NodeItr node = p->getNodeForVReg(src);
427          addPhysRegCoalesce(g.getNodeCosts(node), pregOpt, cBenefit);
428        }
429      } else {
430        const PBQPRAProblem::AllowedSet *allowed1 = &p->getAllowedSet(dst);
431        const PBQPRAProblem::AllowedSet *allowed2 = &p->getAllowedSet(src);
432        PBQP::Graph::NodeItr node1 = p->getNodeForVReg(dst);
433        PBQP::Graph::NodeItr node2 = p->getNodeForVReg(src);
434        PBQP::Graph::EdgeItr edge = g.findEdge(node1, node2);
435        if (edge == g.edgesEnd()) {
436          edge = g.addEdge(node1, node2, PBQP::Matrix(allowed1->size() + 1,
437                                                      allowed2->size() + 1,
438                                                      0));
439        } else {
440          if (g.getEdgeNode1(edge) == node2) {
441            std::swap(node1, node2);
442            std::swap(allowed1, allowed2);
443          }
444        }
445
446        addVirtRegCoalesce(g.getEdgeCosts(edge), *allowed1, *allowed2,
447                           cBenefit);
448      }
449    }
450  }
451
452  return p;
453}
454
455void PBQPBuilderWithCoalescing::addPhysRegCoalesce(PBQP::Vector &costVec,
456                                                   unsigned pregOption,
457                                                   PBQP::PBQPNum benefit) {
458  costVec[pregOption] += -benefit;
459}
460
461void PBQPBuilderWithCoalescing::addVirtRegCoalesce(
462                                    PBQP::Matrix &costMat,
463                                    const PBQPRAProblem::AllowedSet &vr1Allowed,
464                                    const PBQPRAProblem::AllowedSet &vr2Allowed,
465                                    PBQP::PBQPNum benefit) {
466
467  assert(costMat.getRows() == vr1Allowed.size() + 1 && "Size mismatch.");
468  assert(costMat.getCols() == vr2Allowed.size() + 1 && "Size mismatch.");
469
470  for (unsigned i = 0; i != vr1Allowed.size(); ++i) {
471    unsigned preg1 = vr1Allowed[i];
472    for (unsigned j = 0; j != vr2Allowed.size(); ++j) {
473      unsigned preg2 = vr2Allowed[j];
474
475      if (preg1 == preg2) {
476        costMat[i + 1][j + 1] += -benefit;
477      }
478    }
479  }
480}
481
482
483void RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const {
484  au.setPreservesCFG();
485  au.addRequired<AliasAnalysis>();
486  au.addPreserved<AliasAnalysis>();
487  au.addRequired<SlotIndexes>();
488  au.addPreserved<SlotIndexes>();
489  au.addRequired<LiveIntervals>();
490  //au.addRequiredID(SplitCriticalEdgesID);
491  if (customPassID)
492    au.addRequiredID(*customPassID);
493  au.addRequired<CalculateSpillWeights>();
494  au.addRequired<LiveStacks>();
495  au.addPreserved<LiveStacks>();
496  au.addRequired<MachineDominatorTree>();
497  au.addPreserved<MachineDominatorTree>();
498  au.addRequired<MachineLoopInfo>();
499  au.addPreserved<MachineLoopInfo>();
500  au.addRequired<VirtRegMap>();
501  au.addRequired<RenderMachineFunction>();
502  MachineFunctionPass::getAnalysisUsage(au);
503}
504
505void RegAllocPBQP::findVRegIntervalsToAlloc() {
506
507  // Iterate over all live ranges.
508  for (LiveIntervals::iterator itr = lis->begin(), end = lis->end();
509       itr != end; ++itr) {
510
511    // Ignore physical ones.
512    if (TargetRegisterInfo::isPhysicalRegister(itr->first))
513      continue;
514
515    LiveInterval *li = itr->second;
516
517    // If this live interval is non-empty we will use pbqp to allocate it.
518    // Empty intervals we allocate in a simple post-processing stage in
519    // finalizeAlloc.
520    if (!li->empty()) {
521      vregsToAlloc.insert(li->reg);
522    } else {
523      emptyIntervalVRegs.insert(li->reg);
524    }
525  }
526}
527
528bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAProblem &problem,
529                                     const PBQP::Solution &solution) {
530  // Set to true if we have any spills
531  bool anotherRoundNeeded = false;
532
533  // Clear the existing allocation.
534  vrm->clearAllVirt();
535
536  const PBQP::Graph &g = problem.getGraph();
537  // Iterate over the nodes mapping the PBQP solution to a register
538  // assignment.
539  for (PBQP::Graph::ConstNodeItr node = g.nodesBegin(),
540                                 nodeEnd = g.nodesEnd();
541       node != nodeEnd; ++node) {
542    unsigned vreg = problem.getVRegForNode(node);
543    unsigned alloc = solution.getSelection(node);
544
545    if (problem.isPRegOption(vreg, alloc)) {
546      unsigned preg = problem.getPRegForOption(vreg, alloc);
547      DEBUG(dbgs() << "VREG " << PrintReg(vreg, tri) << " -> "
548            << tri->getName(preg) << "\n");
549      assert(preg != 0 && "Invalid preg selected.");
550      vrm->assignVirt2Phys(vreg, preg);
551    } else if (problem.isSpillOption(vreg, alloc)) {
552      vregsToAlloc.erase(vreg);
553      SmallVector<LiveInterval*, 8> newSpills;
554      LiveRangeEdit LRE(&lis->getInterval(vreg), newSpills, *mf, *lis, vrm);
555      spiller->spill(LRE);
556
557      DEBUG(dbgs() << "VREG " << PrintReg(vreg, tri) << " -> SPILLED (Cost: "
558                   << LRE.getParent().weight << ", New vregs: ");
559
560      // Copy any newly inserted live intervals into the list of regs to
561      // allocate.
562      for (LiveRangeEdit::iterator itr = LRE.begin(), end = LRE.end();
563           itr != end; ++itr) {
564        assert(!(*itr)->empty() && "Empty spill range.");
565        DEBUG(dbgs() << PrintReg((*itr)->reg, tri) << " ");
566        vregsToAlloc.insert((*itr)->reg);
567      }
568
569      DEBUG(dbgs() << ")\n");
570
571      // We need another round if spill intervals were added.
572      anotherRoundNeeded |= !LRE.empty();
573    } else {
574      llvm_unreachable("Unknown allocation option.");
575    }
576  }
577
578  return !anotherRoundNeeded;
579}
580
581
582void RegAllocPBQP::finalizeAlloc() const {
583  typedef LiveIntervals::iterator LIIterator;
584  typedef LiveInterval::Ranges::const_iterator LRIterator;
585
586  // First allocate registers for the empty intervals.
587  for (RegSet::const_iterator
588         itr = emptyIntervalVRegs.begin(), end = emptyIntervalVRegs.end();
589         itr != end; ++itr) {
590    LiveInterval *li = &lis->getInterval(*itr);
591
592    unsigned physReg = vrm->getRegAllocPref(li->reg);
593
594    if (physReg == 0) {
595      const TargetRegisterClass *liRC = mri->getRegClass(li->reg);
596      physReg = liRC->getRawAllocationOrder(*mf).front();
597    }
598
599    vrm->assignVirt2Phys(li->reg, physReg);
600  }
601
602  // Finally iterate over the basic blocks to compute and set the live-in sets.
603  SmallVector<MachineBasicBlock*, 8> liveInMBBs;
604  MachineBasicBlock *entryMBB = &*mf->begin();
605
606  for (LIIterator liItr = lis->begin(), liEnd = lis->end();
607       liItr != liEnd; ++liItr) {
608
609    const LiveInterval *li = liItr->second;
610    unsigned reg = 0;
611
612    // Get the physical register for this interval
613    if (TargetRegisterInfo::isPhysicalRegister(li->reg)) {
614      reg = li->reg;
615    } else if (vrm->isAssignedReg(li->reg)) {
616      reg = vrm->getPhys(li->reg);
617    } else {
618      // Ranges which are assigned a stack slot only are ignored.
619      continue;
620    }
621
622    if (reg == 0) {
623      // Filter out zero regs - they're for intervals that were spilled.
624      continue;
625    }
626
627    // Iterate over the ranges of the current interval...
628    for (LRIterator lrItr = li->begin(), lrEnd = li->end();
629         lrItr != lrEnd; ++lrItr) {
630
631      // Find the set of basic blocks which this range is live into...
632      if (lis->findLiveInMBBs(lrItr->start, lrItr->end,  liveInMBBs)) {
633        // And add the physreg for this interval to their live-in sets.
634        for (unsigned i = 0; i != liveInMBBs.size(); ++i) {
635          if (liveInMBBs[i] != entryMBB) {
636            if (!liveInMBBs[i]->isLiveIn(reg)) {
637              liveInMBBs[i]->addLiveIn(reg);
638            }
639          }
640        }
641        liveInMBBs.clear();
642      }
643    }
644  }
645
646}
647
648bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) {
649
650  mf = &MF;
651  tm = &mf->getTarget();
652  tri = tm->getRegisterInfo();
653  tii = tm->getInstrInfo();
654  mri = &mf->getRegInfo();
655
656  lis = &getAnalysis<LiveIntervals>();
657  lss = &getAnalysis<LiveStacks>();
658  loopInfo = &getAnalysis<MachineLoopInfo>();
659  rmf = &getAnalysis<RenderMachineFunction>();
660
661  vrm = &getAnalysis<VirtRegMap>();
662  spiller.reset(createInlineSpiller(*this, MF, *vrm));
663
664  mri->freezeReservedRegs(MF);
665
666  DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n");
667
668  // Allocator main loop:
669  //
670  // * Map current regalloc problem to a PBQP problem
671  // * Solve the PBQP problem
672  // * Map the solution back to a register allocation
673  // * Spill if necessary
674  //
675  // This process is continued till no more spills are generated.
676
677  // Find the vreg intervals in need of allocation.
678  findVRegIntervalsToAlloc();
679
680  const Function* func = mf->getFunction();
681  std::string fqn =
682    func->getParent()->getModuleIdentifier() + "." +
683    func->getName().str();
684  (void)fqn;
685
686  // If there are non-empty intervals allocate them using pbqp.
687  if (!vregsToAlloc.empty()) {
688
689    bool pbqpAllocComplete = false;
690    unsigned round = 0;
691
692    while (!pbqpAllocComplete) {
693      DEBUG(dbgs() << "  PBQP Regalloc round " << round << ":\n");
694
695      std::auto_ptr<PBQPRAProblem> problem =
696        builder->build(mf, lis, loopInfo, vregsToAlloc);
697
698#ifndef NDEBUG
699      if (pbqpDumpGraphs) {
700        std::ostringstream rs;
701        rs << round;
702        std::string graphFileName(fqn + "." + rs.str() + ".pbqpgraph");
703        std::string tmp;
704        raw_fd_ostream os(graphFileName.c_str(), tmp);
705        DEBUG(dbgs() << "Dumping graph for round " << round << " to \""
706              << graphFileName << "\"\n");
707        problem->getGraph().dump(os);
708      }
709#endif
710
711      PBQP::Solution solution =
712        PBQP::HeuristicSolver<PBQP::Heuristics::Briggs>::solve(
713          problem->getGraph());
714
715      pbqpAllocComplete = mapPBQPToRegAlloc(*problem, solution);
716
717      ++round;
718    }
719  }
720
721  // Finalise allocation, allocate empty ranges.
722  finalizeAlloc();
723
724  rmf->renderMachineFunction("After PBQP register allocation.", vrm);
725
726  vregsToAlloc.clear();
727  emptyIntervalVRegs.clear();
728
729  DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm << "\n");
730
731  // Run rewriter
732  vrm->rewrite(lis->getSlotIndexes());
733
734  // All machine operands and other references to virtual registers have been
735  // replaced. Remove the virtual registers.
736  vrm->clearAllVirt();
737  mri->clearVirtRegs();
738
739  return true;
740}
741
742FunctionPass* llvm::createPBQPRegisterAllocator(
743                                           std::auto_ptr<PBQPBuilder> builder,
744                                           char *customPassID) {
745  return new RegAllocPBQP(builder, customPassID);
746}
747
748FunctionPass* llvm::createDefaultPBQPRegisterAllocator() {
749  if (pbqpCoalescing) {
750    return createPBQPRegisterAllocator(
751             std::auto_ptr<PBQPBuilder>(new PBQPBuilderWithCoalescing()));
752  } // else
753  return createPBQPRegisterAllocator(
754           std::auto_ptr<PBQPBuilder>(new PBQPBuilder()));
755}
756
757#undef DEBUG_TYPE
758