lib/CodeGen/RegAllocBasic.cpp

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