RegAllocBasic.cpp revision c62feda741f9d5811b625967c40f1847fb2040e7 
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
48using namespace llvm;
49
50static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator",
51                                      createBasicRegisterAllocator);
52
53// Temporary verification option until we can put verification inside
54// MachineVerifier.
55static cl::opt<bool>
56VerifyRegAlloc("verify-regalloc",
57               cl::desc("Verify live intervals before renaming"));
58
59namespace {
60
61class PhysicalRegisterDescription : public AbstractRegisterDescription {
62  const TargetRegisterInfo *tri_;
63public:
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.
73class 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
88public:
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
111private:
112  void addMBBLiveIns();
113};
114
115char 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
122INITIALIZE_PASS_BEGIN(RABasic, "basic-regalloc",
123                      "Basic Register Allocator", false, false)
124INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
125INITIALIZE_PASS_DEPENDENCY(StrongPHIElimination)
126INITIALIZE_AG_DEPENDENCY(RegisterCoalescer)
127INITIALIZE_PASS_DEPENDENCY(CalculateSpillWeights)
128INITIALIZE_PASS_DEPENDENCY(LiveStacks)
129INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
130INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
131#ifndef NDEBUG
132INITIALIZE_PASS_DEPENDENCY(RenderMachineFunction)
133#endif
134INITIALIZE_PASS_END(RABasic, "basic-regalloc",
135                    "Basic Register Allocator", false, false)
136#endif // disable INITIALIZE_PASS
137
138RABasic::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
151void 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
173void RABasic::releaseMemory() {
174  spiller_.reset(0);
175  RegAllocBase::releaseMemory();
176}
177
178#ifndef NDEBUG
179// Verify each LiveIntervalUnion.
180void 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.
215void 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
223void 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
233void RegAllocBase::LIUArray::clear() {
234  nRegs_ =  0;
235  array_.reset(0);
236}
237
238void RegAllocBase::releaseMemory() {
239  physReg2liu_.clear();
240}
241
242namespace 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.
249class LiveVirtRegQueue {
250  typedef std::priority_queue
251    <LiveInterval*, std::vector<LiveInterval*>, LessSpillWeightPriority> PQ;
252  PQ pq_;
253
254public:
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.
274void 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.
290void 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.
319unsigned 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.
331struct 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.
339void 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.
368bool
369RegAllocBase::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.
414unsigned 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.
472void 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
496namespace llvm {
497Spiller *createInlineSpiller(MachineFunctionPass &pass,
498                             MachineFunction &mf,
499                             VirtRegMap &vrm);
500}
501
502bool 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
563FunctionPass* llvm::createBasicRegisterAllocator()
564{
565  return new RABasic();
566}
567