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