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