RegAllocBasic.cpp revision 6c7228faf7b8bc03ee4fdad3ab462f96978ceaed 
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/Function.h"
23#include "llvm/PassAnalysisSupport.h"
24#include "llvm/CodeGen/CalcSpillWeights.h"
25#include "llvm/CodeGen/LiveIntervalAnalysis.h"
26#include "llvm/CodeGen/LiveStackAnalysis.h"
27#include "llvm/CodeGen/MachineFunctionPass.h"
28#include "llvm/CodeGen/MachineInstr.h"
29#include "llvm/CodeGen/MachineLoopInfo.h"
30#include "llvm/CodeGen/MachineRegisterInfo.h"
31#include "llvm/CodeGen/Passes.h"
32#include "llvm/CodeGen/RegAllocRegistry.h"
33#include "llvm/CodeGen/RegisterCoalescer.h"
34#include "llvm/Target/TargetMachine.h"
35#include "llvm/Target/TargetOptions.h"
36#include "llvm/Target/TargetRegisterInfo.h"
37#include "llvm/Support/Debug.h"
38#include "llvm/Support/ErrorHandling.h"
39#include "llvm/Support/raw_ostream.h"
40
41#include <vector>
42#include <queue>
43
44using namespace llvm;
45
46static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator",
47                                      createBasicRegisterAllocator);
48
49namespace {
50
51/// RABasic provides a minimal implementation of the basic register allocation
52/// algorithm. It prioritizes live virtual registers by spill weight and spills
53/// whenever a register is unavailable. This is not practical in production but
54/// provides a useful baseline both for measuring other allocators and comparing
55/// the speed of the basic algorithm against other styles of allocators.
56class RABasic : public MachineFunctionPass, public RegAllocBase
57{
58  // context
59  MachineFunction *mf_;
60  const TargetMachine *tm_;
61  MachineRegisterInfo *mri_;
62
63  // analyses
64  LiveStacks *ls_;
65  RenderMachineFunction *rmf_;
66
67  // state
68  std::auto_ptr<Spiller> spiller_;
69
70public:
71  RABasic();
72
73  /// Return the pass name.
74  virtual const char* getPassName() const {
75    return "Basic Register Allocator";
76  }
77
78  /// RABasic analysis usage.
79  virtual void getAnalysisUsage(AnalysisUsage &au) const;
80
81  virtual void releaseMemory();
82
83  virtual unsigned selectOrSplit(LiveInterval &lvr,
84                                 SmallVectorImpl<LiveInterval*> &splitLVRs);
85
86  void spillInterferences(unsigned preg,
87                          SmallVectorImpl<LiveInterval*> &splitLVRs);
88
89  /// Perform register allocation.
90  virtual bool runOnMachineFunction(MachineFunction &mf);
91
92  static char ID;
93};
94
95char RABasic::ID = 0;
96
97} // end anonymous namespace
98
99// We should not need to publish the initializer as long as no other passes
100// require RABasic.
101#if 0 // disable INITIALIZE_PASS
102INITIALIZE_PASS_BEGIN(RABasic, "basic-regalloc",
103                      "Basic Register Allocator", false, false)
104INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
105INITIALIZE_PASS_DEPENDENCY(StrongPHIElimination)
106INITIALIZE_AG_DEPENDENCY(RegisterCoalescer)
107INITIALIZE_PASS_DEPENDENCY(CalculateSpillWeights)
108INITIALIZE_PASS_DEPENDENCY(LiveStacks)
109INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
110INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
111#ifndef NDEBUG
112INITIALIZE_PASS_DEPENDENCY(RenderMachineFunction)
113#endif
114INITIALIZE_PASS_END(RABasic, "basic-regalloc",
115                    "Basic Register Allocator", false, false)
116#endif // disable INITIALIZE_PASS
117
118RABasic::RABasic(): MachineFunctionPass(ID) {
119  initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
120  initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
121  initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
122  initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
123  initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
124  initializeLiveStacksPass(*PassRegistry::getPassRegistry());
125  initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
126  initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
127  initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
128  initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry());
129}
130
131void RABasic::getAnalysisUsage(AnalysisUsage &au) const {
132  au.setPreservesCFG();
133  au.addRequired<LiveIntervals>();
134  au.addPreserved<SlotIndexes>();
135  if (StrongPHIElim)
136    au.addRequiredID(StrongPHIEliminationID);
137  au.addRequiredTransitive<RegisterCoalescer>();
138  au.addRequired<CalculateSpillWeights>();
139  au.addRequired<LiveStacks>();
140  au.addPreserved<LiveStacks>();
141  au.addRequiredID(MachineDominatorsID);
142  au.addPreservedID(MachineDominatorsID);
143  au.addRequired<MachineLoopInfo>();
144  au.addPreserved<MachineLoopInfo>();
145  au.addRequired<VirtRegMap>();
146  au.addPreserved<VirtRegMap>();
147  DEBUG(au.addRequired<RenderMachineFunction>());
148  MachineFunctionPass::getAnalysisUsage(au);
149}
150
151void RABasic::releaseMemory() {
152  spiller_.reset(0);
153  RegAllocBase::releaseMemory();
154}
155
156//===----------------------------------------------------------------------===//
157//                         RegAllocBase Implementation
158//===----------------------------------------------------------------------===//
159
160// Instantiate a LiveIntervalUnion for each physical register.
161void RegAllocBase::LIUArray::init(unsigned nRegs) {
162  array_.reset(new LiveIntervalUnion[nRegs]);
163  nRegs_ = nRegs;
164  for (unsigned pr = 0; pr < nRegs; ++pr) {
165    array_[pr].init(pr);
166  }
167}
168
169void RegAllocBase::init(const TargetRegisterInfo &tri, VirtRegMap &vrm,
170                        LiveIntervals &lis) {
171  tri_ = &tri;
172  vrm_ = &vrm;
173  lis_ = &lis;
174  physReg2liu_.init(tri_->getNumRegs());
175  // Cache an interferece query for each physical reg
176  queries_.reset(new LiveIntervalUnion::Query[physReg2liu_.numRegs()]);
177}
178
179void RegAllocBase::LIUArray::clear() {
180  nRegs_ =  0;
181  array_.reset(0);
182}
183
184void RegAllocBase::releaseMemory() {
185  physReg2liu_.clear();
186}
187
188namespace llvm {
189/// This class defines a queue of live virtual registers prioritized by spill
190/// weight. The heaviest vreg is popped first.
191///
192/// Currently, this is trivial wrapper that gives us an opaque type in the
193/// header, but we may later give it a virtual interface for register allocators
194/// to override the priority queue comparator.
195class LiveVirtRegQueue {
196  typedef std::priority_queue
197    <LiveInterval*, std::vector<LiveInterval*>, LessSpillWeightPriority> PQ;
198  PQ pq_;
199
200public:
201  // Is the queue empty?
202  bool empty() { return pq_.empty(); }
203
204  // Get the highest priority lvr (top + pop)
205  LiveInterval *get() {
206    LiveInterval *lvr = pq_.top();
207    pq_.pop();
208    return lvr;
209  }
210  // Add this lvr to the queue
211  void push(LiveInterval *lvr) {
212    pq_.push(lvr);
213  }
214};
215} // end namespace llvm
216
217// Visit all the live virtual registers. If they are already assigned to a
218// physical register, unify them with the corresponding LiveIntervalUnion,
219// otherwise push them on the priority queue for later assignment.
220void RegAllocBase::seedLiveVirtRegs(LiveVirtRegQueue &lvrQ) {
221  for (LiveIntervals::iterator liItr = lis_->begin(), liEnd = lis_->end();
222       liItr != liEnd; ++liItr) {
223    unsigned reg = liItr->first;
224    LiveInterval &li = *liItr->second;
225    if (TargetRegisterInfo::isPhysicalRegister(reg)) {
226      physReg2liu_[reg].unify(li);
227    }
228    else {
229      lvrQ.push(&li);
230    }
231  }
232}
233
234// Top-level driver to manage the queue of unassigned LiveVirtRegs and call the
235// selectOrSplit implementation.
236void RegAllocBase::allocatePhysRegs() {
237  LiveVirtRegQueue lvrQ;
238  seedLiveVirtRegs(lvrQ);
239  while (!lvrQ.empty()) {
240    LiveInterval *lvr = lvrQ.get();
241    typedef SmallVector<LiveInterval*, 4> LVRVec;
242    LVRVec splitLVRs;
243    unsigned availablePhysReg = selectOrSplit(*lvr, splitLVRs);
244    if (availablePhysReg) {
245      DEBUG(dbgs() << "allocating: " << tri_->getName(availablePhysReg) <<
246            " " << lvr << '\n');
247      assert(!vrm_->hasPhys(lvr->reg) && "duplicate vreg in interval unions");
248      vrm_->assignVirt2Phys(lvr->reg, availablePhysReg);
249      physReg2liu_[availablePhysReg].unify(*lvr);
250    }
251    for (LVRVec::iterator lvrI = splitLVRs.begin(), lvrEnd = splitLVRs.end();
252         lvrI != lvrEnd; ++lvrI) {
253      DEBUG(dbgs() << "queuing new interval: " << **lvrI << "\n");
254      assert(TargetRegisterInfo::isVirtualRegister((*lvrI)->reg) &&
255             "expect split value in virtual register");
256      lvrQ.push(*lvrI);
257    }
258  }
259}
260
261// Check if this live virtual reg interferes with a physical register. If not,
262// then check for interference on each register that aliases with the physical
263// register. Return the interfering register.
264unsigned RegAllocBase::checkPhysRegInterference(LiveInterval &lvr,
265                                                unsigned preg) {
266  queries_[preg].init(&lvr, &physReg2liu_[preg]);
267  if (queries_[preg].checkInterference())
268    return preg;
269  for (const unsigned *asI = tri_->getAliasSet(preg); *asI; ++asI) {
270    queries_[*asI].init(&lvr, &physReg2liu_[*asI]);
271    if (queries_[*asI].checkInterference())
272      return *asI;
273  }
274  return 0;
275}
276
277// Spill all live virtual registers currently unified under preg that interfere
278// with lvr.
279void RABasic::spillInterferences(unsigned preg,
280                                 SmallVectorImpl<LiveInterval*> &splitLVRs) {
281  SmallPtrSet<LiveInterval*, 8> spilledLVRs;
282  LiveIntervalUnion::Query &query = queries_[preg];
283  LiveIntervalUnion::InterferenceResult ir = query.firstInterference();
284  assert(query.isInterference(ir) && "expect interference");
285  do {
286    LiveInterval *lvr = ir.liuSegPos()->liveVirtReg;
287    if (!spilledLVRs.insert(lvr)) continue;
288    // Spill the previously allocated lvr.
289    SmallVector<LiveInterval*, 1> spillIs; // ignored
290    spiller_->spill(lvr, splitLVRs, spillIs);
291  } while (query.nextInterference(ir));
292  for (SmallPtrSetIterator<LiveInterval*> lvrI = spilledLVRs.begin(),
293         lvrEnd = spilledLVRs.end();
294       lvrI != lvrEnd; ++lvrI ) {
295    // Deallocate the interfering lvr by removing it from the preg union.
296    physReg2liu_[preg].extract(**lvrI);
297  }
298  // After extracting segments, the query's results are invalid.
299  query.clear();
300}
301
302//===----------------------------------------------------------------------===//
303//                         RABasic Implementation
304//===----------------------------------------------------------------------===//
305
306// Driver for the register assignment and splitting heuristics.
307// Manages iteration over the LiveIntervalUnions.
308//
309// Minimal implementation of register assignment and splitting--spills whenever
310// we run out of registers.
311//
312// selectOrSplit can only be called once per live virtual register. We then do a
313// single interference test for each register the correct class until we find an
314// available register. So, the number of interference tests in the worst case is
315// |vregs| * |machineregs|. And since the number of interference tests is
316// minimal, there is no value in caching them.
317unsigned RABasic::selectOrSplit(LiveInterval &lvr,
318                                SmallVectorImpl<LiveInterval*> &splitLVRs) {
319  // Accumulate the min spill cost among the interferences, in case we spill.
320  unsigned minSpillReg = 0;
321  unsigned minSpillAlias = 0;
322  float minSpillWeight = lvr.weight;
323
324  // Check for an available reg in this class.
325  const TargetRegisterClass *trc = mri_->getRegClass(lvr.reg);
326  for (TargetRegisterClass::iterator trcI = trc->allocation_order_begin(*mf_),
327         trcEnd = trc->allocation_order_end(*mf_);
328       trcI != trcEnd; ++trcI) {
329    unsigned preg = *trcI;
330    unsigned interfReg = checkPhysRegInterference(lvr, preg);
331    if (interfReg == 0) {
332      return preg;
333    }
334    LiveIntervalUnion::InterferenceResult interf =
335      queries_[interfReg].firstInterference();
336    float interfWeight = interf.liuSegPos()->liveVirtReg->weight;
337    if (interfWeight < minSpillWeight ) {
338      minSpillReg = interfReg;
339      minSpillAlias = preg;
340      minSpillWeight = interfWeight;
341    }
342  }
343  if (minSpillReg == 0) {
344    DEBUG(dbgs() << "spilling: " << lvr << '\n');
345    SmallVector<LiveInterval*, 1> spillIs; // ignored
346    spiller_->spill(&lvr, splitLVRs, spillIs);
347    // The live virtual register requesting to be allocated was spilled. So tell
348    // the caller not to allocate anything for this round.
349    return 0;
350  }
351  // Free the cheapest physical register.
352  spillInterferences(minSpillReg, splitLVRs);
353  // Tell the caller to allocate to this newly freed physical register.
354  assert(minSpillAlias != 0 && "need a free register after spilling");
355  // We just spilled the first register that interferes with minSpillAlias. We
356  // now assume minSpillAlias is free because only one register alias may
357  // interfere at a time. e.g. we ignore predication.
358  unsigned interfReg = checkPhysRegInterference(lvr, minSpillAlias);
359  if (interfReg != 0) {
360    dbgs() << "spilling cannot free " << tri_->getName(minSpillAlias) <<
361      " for " << lvr.reg << " with interference " <<
362      *queries_[interfReg].firstInterference().liuSegPos()->liveVirtReg << "\n";
363    llvm_unreachable("Interference after spill.");
364  }
365  return minSpillAlias;
366}
367
368namespace llvm {
369Spiller *createInlineSpiller(MachineFunctionPass &pass,
370                             MachineFunction &mf,
371                             VirtRegMap &vrm);
372}
373
374bool RABasic::runOnMachineFunction(MachineFunction &mf) {
375  DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n"
376               << "********** Function: "
377               << ((Value*)mf.getFunction())->getName() << '\n');
378
379  mf_ = &mf;
380  tm_ = &mf.getTarget();
381  mri_ = &mf.getRegInfo();
382
383  DEBUG(rmf_ = &getAnalysis<RenderMachineFunction>());
384
385  RegAllocBase::init(*tm_->getRegisterInfo(), getAnalysis<VirtRegMap>(),
386                     getAnalysis<LiveIntervals>());
387
388  // We may want to force InlineSpiller for this register allocator. For
389  // now we're also experimenting with the standard spiller.
390  //
391  //spiller_.reset(createInlineSpiller(*this, *mf_, *vrm_));
392  spiller_.reset(createSpiller(*this, *mf_, *vrm_));
393
394  allocatePhysRegs();
395
396  // Diagnostic output before rewriting
397  DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm_ << "\n");
398
399  // optional HTML output
400  DEBUG(rmf_->renderMachineFunction("After basic register allocation.", vrm_));
401
402  // Run rewriter
403  std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
404  rewriter->runOnMachineFunction(*mf_, *vrm_, lis_);
405
406  // The pass output is in VirtRegMap. Release all the transient data.
407  releaseMemory();
408
409  return true;
410}
411
412FunctionPass* llvm::createBasicRegisterAllocator()
413{
414  return new RABasic();
415}
416