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