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