RegAllocBasic.cpp revision fdf16ca44f130afe80c57481d0c08130aa08cc09 
1//===-- RegAllocBasic.cpp - basic register allocator ----------------------===//
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 defines the RABasic function pass, which provides a minimal
11// implementation of the basic register allocator.
12//
13//===----------------------------------------------------------------------===//
14
15#define DEBUG_TYPE "regalloc"
16#include "RegAllocBase.h"
17#include "LiveDebugVariables.h"
18#include "LiveIntervalUnion.h"
19#include "LiveRangeEdit.h"
20#include "RenderMachineFunction.h"
21#include "Spiller.h"
22#include "VirtRegMap.h"
23#include "RegisterCoalescer.h"
24#include "llvm/ADT/OwningPtr.h"
25#include "llvm/ADT/Statistic.h"
26#include "llvm/Analysis/AliasAnalysis.h"
27#include "llvm/Function.h"
28#include "llvm/PassAnalysisSupport.h"
29#include "llvm/CodeGen/CalcSpillWeights.h"
30#include "llvm/CodeGen/LiveIntervalAnalysis.h"
31#include "llvm/CodeGen/LiveStackAnalysis.h"
32#include "llvm/CodeGen/MachineFunctionPass.h"
33#include "llvm/CodeGen/MachineInstr.h"
34#include "llvm/CodeGen/MachineLoopInfo.h"
35#include "llvm/CodeGen/MachineRegisterInfo.h"
36#include "llvm/CodeGen/Passes.h"
37#include "llvm/CodeGen/RegAllocRegistry.h"
38#include "llvm/Target/TargetMachine.h"
39#include "llvm/Target/TargetOptions.h"
40#include "llvm/Target/TargetRegisterInfo.h"
41#ifndef NDEBUG
42#include "llvm/ADT/SparseBitVector.h"
43#endif
44#include "llvm/Support/Debug.h"
45#include "llvm/Support/ErrorHandling.h"
46#include "llvm/Support/raw_ostream.h"
47#include "llvm/Support/Timer.h"
48
49#include <cstdlib>
50#include <queue>
51
52using namespace llvm;
53
54STATISTIC(NumAssigned     , "Number of registers assigned");
55STATISTIC(NumUnassigned   , "Number of registers unassigned");
56STATISTIC(NumNewQueued    , "Number of new live ranges queued");
57
58static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator",
59                                      createBasicRegisterAllocator);
60
61// Temporary verification option until we can put verification inside
62// MachineVerifier.
63static cl::opt<bool, true>
64VerifyRegAlloc("verify-regalloc", cl::location(RegAllocBase::VerifyEnabled),
65               cl::desc("Verify during register allocation"));
66
67const char *RegAllocBase::TimerGroupName = "Register Allocation";
68bool RegAllocBase::VerifyEnabled = false;
69
70namespace {
71  struct CompSpillWeight {
72    bool operator()(LiveInterval *A, LiveInterval *B) const {
73      return A->weight < B->weight;
74    }
75  };
76}
77
78namespace {
79/// RABasic provides a minimal implementation of the basic register allocation
80/// algorithm. It prioritizes live virtual registers by spill weight and spills
81/// whenever a register is unavailable. This is not practical in production but
82/// provides a useful baseline both for measuring other allocators and comparing
83/// the speed of the basic algorithm against other styles of allocators.
84class RABasic : public MachineFunctionPass, public RegAllocBase
85{
86  // context
87  MachineFunction *MF;
88
89  // analyses
90  LiveStacks *LS;
91  RenderMachineFunction *RMF;
92
93  // state
94  std::auto_ptr<Spiller> SpillerInstance;
95  std::priority_queue<LiveInterval*, std::vector<LiveInterval*>,
96                      CompSpillWeight> Queue;
97public:
98  RABasic();
99
100  /// Return the pass name.
101  virtual const char* getPassName() const {
102    return "Basic Register Allocator";
103  }
104
105  /// RABasic analysis usage.
106  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
107
108  virtual void releaseMemory();
109
110  virtual Spiller &spiller() { return *SpillerInstance; }
111
112  virtual float getPriority(LiveInterval *LI) { return LI->weight; }
113
114  virtual void enqueue(LiveInterval *LI) {
115    Queue.push(LI);
116  }
117
118  virtual LiveInterval *dequeue() {
119    if (Queue.empty())
120      return 0;
121    LiveInterval *LI = Queue.top();
122    Queue.pop();
123    return LI;
124  }
125
126  virtual unsigned selectOrSplit(LiveInterval &VirtReg,
127                                 SmallVectorImpl<LiveInterval*> &SplitVRegs);
128
129  /// Perform register allocation.
130  virtual bool runOnMachineFunction(MachineFunction &mf);
131
132  static char ID;
133};
134
135char RABasic::ID = 0;
136
137} // end anonymous namespace
138
139RABasic::RABasic(): MachineFunctionPass(ID) {
140  initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry());
141  initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
142  initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
143  initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
144  initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
145  initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
146  initializeLiveStacksPass(*PassRegistry::getPassRegistry());
147  initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
148  initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
149  initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
150  initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry());
151}
152
153void RABasic::getAnalysisUsage(AnalysisUsage &AU) const {
154  AU.setPreservesCFG();
155  AU.addRequired<AliasAnalysis>();
156  AU.addPreserved<AliasAnalysis>();
157  AU.addRequired<LiveIntervals>();
158  AU.addPreserved<SlotIndexes>();
159  AU.addRequired<LiveDebugVariables>();
160  AU.addPreserved<LiveDebugVariables>();
161  if (StrongPHIElim)
162    AU.addRequiredID(StrongPHIEliminationID);
163  AU.addRequiredTransitive<RegisterCoalescer>();
164  AU.addRequired<CalculateSpillWeights>();
165  AU.addRequired<LiveStacks>();
166  AU.addPreserved<LiveStacks>();
167  AU.addRequiredID(MachineDominatorsID);
168  AU.addPreservedID(MachineDominatorsID);
169  AU.addRequired<MachineLoopInfo>();
170  AU.addPreserved<MachineLoopInfo>();
171  AU.addRequired<VirtRegMap>();
172  AU.addPreserved<VirtRegMap>();
173  DEBUG(AU.addRequired<RenderMachineFunction>());
174  MachineFunctionPass::getAnalysisUsage(AU);
175}
176
177void RABasic::releaseMemory() {
178  SpillerInstance.reset(0);
179  RegAllocBase::releaseMemory();
180}
181
182#ifndef NDEBUG
183// Verify each LiveIntervalUnion.
184void RegAllocBase::verify() {
185  LiveVirtRegBitSet VisitedVRegs;
186  OwningArrayPtr<LiveVirtRegBitSet>
187    unionVRegs(new LiveVirtRegBitSet[PhysReg2LiveUnion.numRegs()]);
188
189  // Verify disjoint unions.
190  for (unsigned PhysReg = 0; PhysReg < PhysReg2LiveUnion.numRegs(); ++PhysReg) {
191    DEBUG(PhysReg2LiveUnion[PhysReg].print(dbgs(), TRI));
192    LiveVirtRegBitSet &VRegs = unionVRegs[PhysReg];
193    PhysReg2LiveUnion[PhysReg].verify(VRegs);
194    // Union + intersection test could be done efficiently in one pass, but
195    // don't add a method to SparseBitVector unless we really need it.
196    assert(!VisitedVRegs.intersects(VRegs) && "vreg in multiple unions");
197    VisitedVRegs |= VRegs;
198  }
199
200  // Verify vreg coverage.
201  for (LiveIntervals::iterator liItr = LIS->begin(), liEnd = LIS->end();
202       liItr != liEnd; ++liItr) {
203    unsigned reg = liItr->first;
204    if (TargetRegisterInfo::isPhysicalRegister(reg)) continue;
205    if (!VRM->hasPhys(reg)) continue; // spilled?
206    unsigned PhysReg = VRM->getPhys(reg);
207    if (!unionVRegs[PhysReg].test(reg)) {
208      dbgs() << "LiveVirtReg " << reg << " not in union " <<
209        TRI->getName(PhysReg) << "\n";
210      llvm_unreachable("unallocated live vreg");
211    }
212  }
213  // FIXME: I'm not sure how to verify spilled intervals.
214}
215#endif //!NDEBUG
216
217//===----------------------------------------------------------------------===//
218//                         RegAllocBase Implementation
219//===----------------------------------------------------------------------===//
220
221// Instantiate a LiveIntervalUnion for each physical register.
222void RegAllocBase::LiveUnionArray::init(LiveIntervalUnion::Allocator &allocator,
223                                        unsigned NRegs) {
224  NumRegs = NRegs;
225  Array =
226    static_cast<LiveIntervalUnion*>(malloc(sizeof(LiveIntervalUnion)*NRegs));
227  for (unsigned r = 0; r != NRegs; ++r)
228    new(Array + r) LiveIntervalUnion(r, allocator);
229}
230
231void RegAllocBase::init(VirtRegMap &vrm, LiveIntervals &lis) {
232  NamedRegionTimer T("Initialize", TimerGroupName, TimePassesIsEnabled);
233  TRI = &vrm.getTargetRegInfo();
234  MRI = &vrm.getRegInfo();
235  VRM = &vrm;
236  LIS = &lis;
237  RegClassInfo.runOnMachineFunction(vrm.getMachineFunction());
238
239  const unsigned NumRegs = TRI->getNumRegs();
240  if (NumRegs != PhysReg2LiveUnion.numRegs()) {
241    PhysReg2LiveUnion.init(UnionAllocator, NumRegs);
242    // Cache an interferece query for each physical reg
243    Queries.reset(new LiveIntervalUnion::Query[PhysReg2LiveUnion.numRegs()]);
244  }
245}
246
247void RegAllocBase::LiveUnionArray::clear() {
248  if (!Array)
249    return;
250  for (unsigned r = 0; r != NumRegs; ++r)
251    Array[r].~LiveIntervalUnion();
252  free(Array);
253  NumRegs =  0;
254  Array = 0;
255}
256
257void RegAllocBase::releaseMemory() {
258  for (unsigned r = 0, e = PhysReg2LiveUnion.numRegs(); r != e; ++r)
259    PhysReg2LiveUnion[r].clear();
260}
261
262// Visit all the live registers. If they are already assigned to a physical
263// register, unify them with the corresponding LiveIntervalUnion, otherwise push
264// them on the priority queue for later assignment.
265void RegAllocBase::seedLiveRegs() {
266  NamedRegionTimer T("Seed Live Regs", TimerGroupName, TimePassesIsEnabled);
267  for (LiveIntervals::iterator I = LIS->begin(), E = LIS->end(); I != E; ++I) {
268    unsigned RegNum = I->first;
269    LiveInterval &VirtReg = *I->second;
270    if (TargetRegisterInfo::isPhysicalRegister(RegNum))
271      PhysReg2LiveUnion[RegNum].unify(VirtReg);
272    else
273      enqueue(&VirtReg);
274  }
275}
276
277void RegAllocBase::assign(LiveInterval &VirtReg, unsigned PhysReg) {
278  DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI)
279               << " to " << PrintReg(PhysReg, TRI) << '\n');
280  assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment");
281  VRM->assignVirt2Phys(VirtReg.reg, PhysReg);
282  MRI->setPhysRegUsed(PhysReg);
283  PhysReg2LiveUnion[PhysReg].unify(VirtReg);
284  ++NumAssigned;
285}
286
287void RegAllocBase::unassign(LiveInterval &VirtReg, unsigned PhysReg) {
288  DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI)
289               << " from " << PrintReg(PhysReg, TRI) << '\n');
290  assert(VRM->getPhys(VirtReg.reg) == PhysReg && "Inconsistent unassign");
291  PhysReg2LiveUnion[PhysReg].extract(VirtReg);
292  VRM->clearVirt(VirtReg.reg);
293  ++NumUnassigned;
294}
295
296// Top-level driver to manage the queue of unassigned VirtRegs and call the
297// selectOrSplit implementation.
298void RegAllocBase::allocatePhysRegs() {
299  seedLiveRegs();
300
301  // Continue assigning vregs one at a time to available physical registers.
302  while (LiveInterval *VirtReg = dequeue()) {
303    assert(!VRM->hasPhys(VirtReg->reg) && "Register already assigned");
304
305    // Unused registers can appear when the spiller coalesces snippets.
306    if (MRI->reg_nodbg_empty(VirtReg->reg)) {
307      DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n');
308      LIS->removeInterval(VirtReg->reg);
309      continue;
310    }
311
312    // Invalidate all interference queries, live ranges could have changed.
313    invalidateVirtRegs();
314
315    // selectOrSplit requests the allocator to return an available physical
316    // register if possible and populate a list of new live intervals that
317    // result from splitting.
318    DEBUG(dbgs() << "\nselectOrSplit "
319                 << MRI->getRegClass(VirtReg->reg)->getName()
320                 << ':' << *VirtReg << '\n');
321    typedef SmallVector<LiveInterval*, 4> VirtRegVec;
322    VirtRegVec SplitVRegs;
323    unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs);
324
325    if (AvailablePhysReg == ~0u) {
326      // selectOrSplit failed to find a register!
327      std::string msg;
328      raw_string_ostream Msg(msg);
329      Msg << "Ran out of registers during register allocation!"
330             "\nCannot allocate: " << *VirtReg;
331      for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(VirtReg->reg);
332      MachineInstr *MI = I.skipInstruction();) {
333        if (!MI->isInlineAsm())
334          continue;
335        Msg << "\nPlease check your inline asm statement for "
336          "invalid constraints:\n";
337        MI->print(Msg, &VRM->getMachineFunction().getTarget());
338      }
339      report_fatal_error(Msg.str());
340    }
341
342    if (AvailablePhysReg)
343      assign(*VirtReg, AvailablePhysReg);
344
345    for (VirtRegVec::iterator I = SplitVRegs.begin(), E = SplitVRegs.end();
346         I != E; ++I) {
347      LiveInterval *SplitVirtReg = *I;
348      assert(!VRM->hasPhys(SplitVirtReg->reg) && "Register already assigned");
349      if (MRI->reg_nodbg_empty(SplitVirtReg->reg)) {
350        DEBUG(dbgs() << "not queueing unused  " << *SplitVirtReg << '\n');
351        LIS->removeInterval(SplitVirtReg->reg);
352        continue;
353      }
354      DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n");
355      assert(TargetRegisterInfo::isVirtualRegister(SplitVirtReg->reg) &&
356             "expect split value in virtual register");
357      enqueue(SplitVirtReg);
358      ++NumNewQueued;
359    }
360  }
361}
362
363// Check if this live virtual register interferes with a physical register. If
364// not, then check for interference on each register that aliases with the
365// physical register. Return the interfering register.
366unsigned RegAllocBase::checkPhysRegInterference(LiveInterval &VirtReg,
367                                                unsigned PhysReg) {
368  for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI)
369    if (query(VirtReg, *AliasI).checkInterference())
370      return *AliasI;
371  return 0;
372}
373
374// Helper for spillInteferences() that spills all interfering vregs currently
375// assigned to this physical register.
376void RegAllocBase::spillReg(LiveInterval& VirtReg, unsigned PhysReg,
377                            SmallVectorImpl<LiveInterval*> &SplitVRegs) {
378  LiveIntervalUnion::Query &Q = query(VirtReg, PhysReg);
379  assert(Q.seenAllInterferences() && "need collectInterferences()");
380  const SmallVectorImpl<LiveInterval*> &PendingSpills = Q.interferingVRegs();
381
382  for (SmallVectorImpl<LiveInterval*>::const_iterator I = PendingSpills.begin(),
383         E = PendingSpills.end(); I != E; ++I) {
384    LiveInterval &SpilledVReg = **I;
385    DEBUG(dbgs() << "extracting from " <<
386          TRI->getName(PhysReg) << " " << SpilledVReg << '\n');
387
388    // Deallocate the interfering vreg by removing it from the union.
389    // A LiveInterval instance may not be in a union during modification!
390    unassign(SpilledVReg, PhysReg);
391
392    // Spill the extracted interval.
393    LiveRangeEdit LRE(SpilledVReg, SplitVRegs, 0, &PendingSpills);
394    spiller().spill(LRE);
395  }
396  // After extracting segments, the query's results are invalid. But keep the
397  // contents valid until we're done accessing pendingSpills.
398  Q.clear();
399}
400
401// Spill or split all live virtual registers currently unified under PhysReg
402// that interfere with VirtReg. The newly spilled or split live intervals are
403// returned by appending them to SplitVRegs.
404bool
405RegAllocBase::spillInterferences(LiveInterval &VirtReg, unsigned PhysReg,
406                                 SmallVectorImpl<LiveInterval*> &SplitVRegs) {
407  // Record each interference and determine if all are spillable before mutating
408  // either the union or live intervals.
409  unsigned NumInterferences = 0;
410  // Collect interferences assigned to any alias of the physical register.
411  for (const unsigned *asI = TRI->getOverlaps(PhysReg); *asI; ++asI) {
412    LiveIntervalUnion::Query &QAlias = query(VirtReg, *asI);
413    NumInterferences += QAlias.collectInterferingVRegs();
414    if (QAlias.seenUnspillableVReg()) {
415      return false;
416    }
417  }
418  DEBUG(dbgs() << "spilling " << TRI->getName(PhysReg) <<
419        " interferences with " << VirtReg << "\n");
420  assert(NumInterferences > 0 && "expect interference");
421
422  // Spill each interfering vreg allocated to PhysReg or an alias.
423  for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI)
424    spillReg(VirtReg, *AliasI, SplitVRegs);
425  return true;
426}
427
428// Add newly allocated physical registers to the MBB live in sets.
429void RegAllocBase::addMBBLiveIns(MachineFunction *MF) {
430  NamedRegionTimer T("MBB Live Ins", TimerGroupName, TimePassesIsEnabled);
431  SlotIndexes *Indexes = LIS->getSlotIndexes();
432  if (MF->size() <= 1)
433    return;
434
435  LiveIntervalUnion::SegmentIter SI;
436  for (unsigned PhysReg = 0; PhysReg < PhysReg2LiveUnion.numRegs(); ++PhysReg) {
437    LiveIntervalUnion &LiveUnion = PhysReg2LiveUnion[PhysReg];
438    if (LiveUnion.empty())
439      continue;
440    MachineFunction::iterator MBB = llvm::next(MF->begin());
441    MachineFunction::iterator MFE = MF->end();
442    SlotIndex Start, Stop;
443    tie(Start, Stop) = Indexes->getMBBRange(MBB);
444    SI.setMap(LiveUnion.getMap());
445    SI.find(Start);
446    while (SI.valid()) {
447      if (SI.start() <= Start) {
448        if (!MBB->isLiveIn(PhysReg))
449          MBB->addLiveIn(PhysReg);
450      } else if (SI.start() > Stop)
451        MBB = Indexes->getMBBFromIndex(SI.start().getPrevIndex());
452      if (++MBB == MFE)
453        break;
454      tie(Start, Stop) = Indexes->getMBBRange(MBB);
455      SI.advanceTo(Start);
456    }
457  }
458}
459
460
461//===----------------------------------------------------------------------===//
462//                         RABasic Implementation
463//===----------------------------------------------------------------------===//
464
465// Driver for the register assignment and splitting heuristics.
466// Manages iteration over the LiveIntervalUnions.
467//
468// This is a minimal implementation of register assignment and splitting that
469// spills whenever we run out of registers.
470//
471// selectOrSplit can only be called once per live virtual register. We then do a
472// single interference test for each register the correct class until we find an
473// available register. So, the number of interference tests in the worst case is
474// |vregs| * |machineregs|. And since the number of interference tests is
475// minimal, there is no value in caching them outside the scope of
476// selectOrSplit().
477unsigned RABasic::selectOrSplit(LiveInterval &VirtReg,
478                                SmallVectorImpl<LiveInterval*> &SplitVRegs) {
479  // Populate a list of physical register spill candidates.
480  SmallVector<unsigned, 8> PhysRegSpillCands;
481
482  // Check for an available register in this class.
483  ArrayRef<unsigned> Order =
484    RegClassInfo.getOrder(MRI->getRegClass(VirtReg.reg));
485  for (ArrayRef<unsigned>::iterator I = Order.begin(), E = Order.end(); I != E;
486       ++I) {
487    unsigned PhysReg = *I;
488
489    // Check interference and as a side effect, intialize queries for this
490    // VirtReg and its aliases.
491    unsigned interfReg = checkPhysRegInterference(VirtReg, PhysReg);
492    if (interfReg == 0) {
493      // Found an available register.
494      return PhysReg;
495    }
496    LiveInterval *interferingVirtReg =
497      Queries[interfReg].firstInterference().liveUnionPos().value();
498
499    // The current VirtReg must either be spillable, or one of its interferences
500    // must have less spill weight.
501    if (interferingVirtReg->weight < VirtReg.weight ) {
502      PhysRegSpillCands.push_back(PhysReg);
503    }
504  }
505  // Try to spill another interfering reg with less spill weight.
506  for (SmallVectorImpl<unsigned>::iterator PhysRegI = PhysRegSpillCands.begin(),
507         PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) {
508
509    if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs)) continue;
510
511    assert(checkPhysRegInterference(VirtReg, *PhysRegI) == 0 &&
512           "Interference after spill.");
513    // Tell the caller to allocate to this newly freed physical register.
514    return *PhysRegI;
515  }
516
517  // No other spill candidates were found, so spill the current VirtReg.
518  DEBUG(dbgs() << "spilling: " << VirtReg << '\n');
519  if (!VirtReg.isSpillable())
520    return ~0u;
521  LiveRangeEdit LRE(VirtReg, SplitVRegs);
522  spiller().spill(LRE);
523
524  // The live virtual register requesting allocation was spilled, so tell
525  // the caller not to allocate anything during this round.
526  return 0;
527}
528
529bool RABasic::runOnMachineFunction(MachineFunction &mf) {
530  DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n"
531               << "********** Function: "
532               << ((Value*)mf.getFunction())->getName() << '\n');
533
534  MF = &mf;
535  DEBUG(RMF = &getAnalysis<RenderMachineFunction>());
536
537  RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>());
538  SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
539
540  allocatePhysRegs();
541
542  addMBBLiveIns(MF);
543
544  // Diagnostic output before rewriting
545  DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n");
546
547  // optional HTML output
548  DEBUG(RMF->renderMachineFunction("After basic register allocation.", VRM));
549
550  // FIXME: Verification currently must run before VirtRegRewriter. We should
551  // make the rewriter a separate pass and override verifyAnalysis instead. When
552  // that happens, verification naturally falls under VerifyMachineCode.
553#ifndef NDEBUG
554  if (VerifyEnabled) {
555    // Verify accuracy of LiveIntervals. The standard machine code verifier
556    // ensures that each LiveIntervals covers all uses of the virtual reg.
557
558    // FIXME: MachineVerifier is badly broken when using the standard
559    // spiller. Always use -spiller=inline with -verify-regalloc. Even with the
560    // inline spiller, some tests fail to verify because the coalescer does not
561    // always generate verifiable code.
562    MF->verify(this, "In RABasic::verify");
563
564    // Verify that LiveIntervals are partitioned into unions and disjoint within
565    // the unions.
566    verify();
567  }
568#endif // !NDEBUG
569
570  // Run rewriter
571  VRM->rewrite(LIS->getSlotIndexes());
572
573  // Write out new DBG_VALUE instructions.
574  getAnalysis<LiveDebugVariables>().emitDebugValues(VRM);
575
576  // The pass output is in VirtRegMap. Release all the transient data.
577  releaseMemory();
578
579  return true;
580}
581
582FunctionPass* llvm::createBasicRegisterAllocator()
583{
584  return new RABasic();
585}
586