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