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