RegAllocBasic.cpp revision 4a84cce3ed0008baf72ccc6831a046215addd2d7 
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  if (query(VirtReg, PhysReg).checkInterference())
289    return PhysReg;
290  for (const unsigned *AliasI = TRI->getAliasSet(PhysReg); *AliasI; ++AliasI) {
291    if (query(VirtReg, *AliasI).checkInterference())
292      return *AliasI;
293  }
294  return 0;
295}
296
297// Helper for spillInteferences() that spills all interfering vregs currently
298// assigned to this physical register.
299void RegAllocBase::spillReg(LiveInterval& VirtReg, unsigned PhysReg,
300                            SmallVectorImpl<LiveInterval*> &SplitVRegs) {
301  LiveIntervalUnion::Query &Q = query(VirtReg, PhysReg);
302  assert(Q.seenAllInterferences() && "need collectInterferences()");
303  const SmallVectorImpl<LiveInterval*> &PendingSpills = Q.interferingVRegs();
304
305  for (SmallVectorImpl<LiveInterval*>::const_iterator I = PendingSpills.begin(),
306         E = PendingSpills.end(); I != E; ++I) {
307    LiveInterval &SpilledVReg = **I;
308    DEBUG(dbgs() << "extracting from " <<
309          TRI->getName(PhysReg) << " " << SpilledVReg << '\n');
310
311    // Deallocate the interfering vreg by removing it from the union.
312    // A LiveInterval instance may not be in a union during modification!
313    PhysReg2LiveUnion[PhysReg].extract(SpilledVReg);
314
315    // Clear the vreg assignment.
316    VRM->clearVirt(SpilledVReg.reg);
317
318    // Spill the extracted interval.
319    spiller().spill(&SpilledVReg, SplitVRegs, PendingSpills);
320  }
321  // After extracting segments, the query's results are invalid. But keep the
322  // contents valid until we're done accessing pendingSpills.
323  Q.clear();
324}
325
326// Spill or split all live virtual registers currently unified under PhysReg
327// that interfere with VirtReg. The newly spilled or split live intervals are
328// returned by appending them to SplitVRegs.
329bool
330RegAllocBase::spillInterferences(LiveInterval &VirtReg, unsigned PhysReg,
331                                 SmallVectorImpl<LiveInterval*> &SplitVRegs) {
332  // Record each interference and determine if all are spillable before mutating
333  // either the union or live intervals.
334
335  // Collect interferences assigned to the requested physical register.
336  LiveIntervalUnion::Query &QPreg = query(VirtReg, PhysReg);
337  unsigned NumInterferences = QPreg.collectInterferingVRegs();
338  if (QPreg.seenUnspillableVReg()) {
339    return false;
340  }
341  // Collect interferences assigned to any alias of the physical register.
342  for (const unsigned *asI = TRI->getAliasSet(PhysReg); *asI; ++asI) {
343    LiveIntervalUnion::Query &QAlias = query(VirtReg, *asI);
344    NumInterferences += QAlias.collectInterferingVRegs();
345    if (QAlias.seenUnspillableVReg()) {
346      return false;
347    }
348  }
349  DEBUG(dbgs() << "spilling " << TRI->getName(PhysReg) <<
350        " interferences with " << VirtReg << "\n");
351  assert(NumInterferences > 0 && "expect interference");
352
353  // Spill each interfering vreg allocated to PhysReg or an alias.
354  spillReg(VirtReg, PhysReg, SplitVRegs);
355  for (const unsigned *AliasI = TRI->getAliasSet(PhysReg); *AliasI; ++AliasI)
356    spillReg(VirtReg, *AliasI, SplitVRegs);
357  return true;
358}
359
360// Add newly allocated physical registers to the MBB live in sets.
361void RegAllocBase::addMBBLiveIns(MachineFunction *MF) {
362  NamedRegionTimer T("MBB Live Ins", TimerGroupName, TimePassesIsEnabled);
363  typedef SmallVector<MachineBasicBlock*, 8> MBBVec;
364  MBBVec liveInMBBs;
365  MachineBasicBlock &entryMBB = *MF->begin();
366
367  for (unsigned PhysReg = 0; PhysReg < PhysReg2LiveUnion.numRegs(); ++PhysReg) {
368    LiveIntervalUnion &LiveUnion = PhysReg2LiveUnion[PhysReg];
369    if (LiveUnion.empty())
370      continue;
371    for (LiveIntervalUnion::SegmentIter SI = LiveUnion.begin(); SI.valid();
372         ++SI) {
373
374      // Find the set of basic blocks which this range is live into...
375      liveInMBBs.clear();
376      if (!LIS->findLiveInMBBs(SI.start(), SI.stop(), liveInMBBs)) continue;
377
378      // And add the physreg for this interval to their live-in sets.
379      for (MBBVec::iterator I = liveInMBBs.begin(), E = liveInMBBs.end();
380           I != E; ++I) {
381        MachineBasicBlock *MBB = *I;
382        if (MBB == &entryMBB) continue;
383        if (MBB->isLiveIn(PhysReg)) continue;
384        MBB->addLiveIn(PhysReg);
385      }
386    }
387  }
388}
389
390
391//===----------------------------------------------------------------------===//
392//                         RABasic Implementation
393//===----------------------------------------------------------------------===//
394
395// Driver for the register assignment and splitting heuristics.
396// Manages iteration over the LiveIntervalUnions.
397//
398// This is a minimal implementation of register assignment and splitting that
399// spills whenever we run out of registers.
400//
401// selectOrSplit can only be called once per live virtual register. We then do a
402// single interference test for each register the correct class until we find an
403// available register. So, the number of interference tests in the worst case is
404// |vregs| * |machineregs|. And since the number of interference tests is
405// minimal, there is no value in caching them outside the scope of
406// selectOrSplit().
407unsigned RABasic::selectOrSplit(LiveInterval &VirtReg,
408                                SmallVectorImpl<LiveInterval*> &SplitVRegs) {
409  // Populate a list of physical register spill candidates.
410  SmallVector<unsigned, 8> PhysRegSpillCands;
411
412  // Check for an available register in this class.
413  const TargetRegisterClass *TRC = MRI->getRegClass(VirtReg.reg);
414
415  for (TargetRegisterClass::iterator I = TRC->allocation_order_begin(*MF),
416         E = TRC->allocation_order_end(*MF);
417       I != E; ++I) {
418
419    unsigned PhysReg = *I;
420    if (ReservedRegs.test(PhysReg)) continue;
421
422    // Check interference and as a side effect, intialize queries for this
423    // VirtReg and its aliases.
424    unsigned interfReg = checkPhysRegInterference(VirtReg, PhysReg);
425    if (interfReg == 0) {
426      // Found an available register.
427      return PhysReg;
428    }
429    LiveInterval *interferingVirtReg =
430      Queries[interfReg].firstInterference().liveUnionPos().value();
431
432    // The current VirtReg must either be spillable, or one of its interferences
433    // must have less spill weight.
434    if (interferingVirtReg->weight < VirtReg.weight ) {
435      PhysRegSpillCands.push_back(PhysReg);
436    }
437  }
438  // Try to spill another interfering reg with less spill weight.
439  for (SmallVectorImpl<unsigned>::iterator PhysRegI = PhysRegSpillCands.begin(),
440         PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) {
441
442    if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs)) continue;
443
444    assert(checkPhysRegInterference(VirtReg, *PhysRegI) == 0 &&
445           "Interference after spill.");
446    // Tell the caller to allocate to this newly freed physical register.
447    return *PhysRegI;
448  }
449  // No other spill candidates were found, so spill the current VirtReg.
450  DEBUG(dbgs() << "spilling: " << VirtReg << '\n');
451  SmallVector<LiveInterval*, 1> pendingSpills;
452
453  spiller().spill(&VirtReg, SplitVRegs, pendingSpills);
454
455  // The live virtual register requesting allocation was spilled, so tell
456  // the caller not to allocate anything during this round.
457  return 0;
458}
459
460bool RABasic::runOnMachineFunction(MachineFunction &mf) {
461  DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n"
462               << "********** Function: "
463               << ((Value*)mf.getFunction())->getName() << '\n');
464
465  MF = &mf;
466  DEBUG(RMF = &getAnalysis<RenderMachineFunction>());
467
468  RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>());
469
470  ReservedRegs = TRI->getReservedRegs(*MF);
471
472  SpillerInstance.reset(createSpiller(*this, *MF, *VRM));
473
474  allocatePhysRegs();
475
476  addMBBLiveIns(MF);
477
478  // Diagnostic output before rewriting
479  DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n");
480
481  // optional HTML output
482  DEBUG(RMF->renderMachineFunction("After basic register allocation.", VRM));
483
484  // FIXME: Verification currently must run before VirtRegRewriter. We should
485  // make the rewriter a separate pass and override verifyAnalysis instead. When
486  // that happens, verification naturally falls under VerifyMachineCode.
487#ifndef NDEBUG
488  if (VerifyRegAlloc) {
489    // Verify accuracy of LiveIntervals. The standard machine code verifier
490    // ensures that each LiveIntervals covers all uses of the virtual reg.
491
492    // FIXME: MachineVerifier is badly broken when using the standard
493    // spiller. Always use -spiller=inline with -verify-regalloc. Even with the
494    // inline spiller, some tests fail to verify because the coalescer does not
495    // always generate verifiable code.
496    MF->verify(this);
497
498    // Verify that LiveIntervals are partitioned into unions and disjoint within
499    // the unions.
500    verify();
501  }
502#endif // !NDEBUG
503
504  // Run rewriter
505  std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
506  rewriter->runOnMachineFunction(*MF, *VRM, LIS);
507
508  // The pass output is in VirtRegMap. Release all the transient data.
509  releaseMemory();
510
511  return true;
512}
513
514FunctionPass* llvm::createBasicRegisterAllocator()
515{
516  return new RABasic();
517}
518