RegAllocBasic.cpp revision 43745184cda123d0da6bd37425d94c9ca7dac354 
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  initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
124  initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
125  initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry());
126}
127
128void RABasic::getAnalysisUsage(AnalysisUsage &au) const {
129  au.setPreservesCFG();
130  au.addRequired<LiveIntervals>();
131  au.addPreserved<SlotIndexes>();
132  if (StrongPHIElim)
133    au.addRequiredID(StrongPHIEliminationID);
134  au.addRequiredTransitive<RegisterCoalescer>();
135  au.addRequired<CalculateSpillWeights>();
136  au.addRequired<LiveStacks>();
137  au.addPreserved<LiveStacks>();
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  spiller_.reset(0);
148  RegAllocBase::releaseMemory();
149}
150
151//===----------------------------------------------------------------------===//
152//                         RegAllocBase Implementation
153//===----------------------------------------------------------------------===//
154
155// Instantiate a LiveIntervalUnion for each physical register.
156void RegAllocBase::LIUArray::init(unsigned nRegs) {
157  array_.reset(new LiveIntervalUnion[nRegs]);
158  nRegs_ = nRegs;
159  for (unsigned pr = 0; pr < nRegs; ++pr) {
160    array_[pr].init(pr);
161  }
162}
163
164void RegAllocBase::init(const TargetRegisterInfo &tri, VirtRegMap &vrm,
165                        LiveIntervals &lis) {
166  tri_ = &tri;
167  vrm_ = &vrm;
168  lis_ = &lis;
169  physReg2liu_.init(tri_->getNumRegs());
170}
171
172void RegAllocBase::LIUArray::clear() {
173  nRegs_ =  0;
174  array_.reset(0);
175}
176
177void RegAllocBase::releaseMemory() {
178  physReg2liu_.clear();
179}
180
181namespace llvm {
182/// This class defines a queue of live virtual registers prioritized by spill
183/// weight. The heaviest vreg is popped first.
184///
185/// Currently, this is trivial wrapper that gives us an opaque type in the
186/// header, but we may later give it a virtual interface for register allocators
187/// to override the priority queue comparator.
188class LiveVirtRegQueue {
189  typedef std::priority_queue
190    <LiveInterval*, std::vector<LiveInterval*>, LessSpillWeightPriority> PQ;
191  PQ pq_;
192
193public:
194  // Is the queue empty?
195  bool empty() { return pq_.empty(); }
196
197  // Get the highest priority lvr (top + pop)
198  LiveInterval *get() {
199    LiveInterval *lvr = pq_.top();
200    pq_.pop();
201    return lvr;
202  }
203  // Add this lvr to the queue
204  void push(LiveInterval *lvr) {
205    pq_.push(lvr);
206  }
207};
208} // end namespace llvm
209
210// Visit all the live virtual registers. If they are already assigned to a
211// physical register, unify them with the corresponding LiveIntervalUnion,
212// otherwise push them on the priority queue for later assignment.
213void RegAllocBase::seedLiveVirtRegs(LiveVirtRegQueue &lvrQ) {
214  for (LiveIntervals::iterator liItr = lis_->begin(), liEnd = lis_->end();
215       liItr != liEnd; ++liItr) {
216    unsigned reg = liItr->first;
217    LiveInterval &li = *liItr->second;
218    if (TargetRegisterInfo::isPhysicalRegister(reg)) {
219      physReg2liu_[reg].unify(li);
220    }
221    else {
222      lvrQ.push(&li);
223    }
224  }
225}
226
227// Top-level driver to manage the queue of unassigned LiveVirtRegs and call the
228// selectOrSplit implementation.
229void RegAllocBase::allocatePhysRegs() {
230  LiveVirtRegQueue lvrQ;
231  seedLiveVirtRegs(lvrQ);
232  while (!lvrQ.empty()) {
233    LiveInterval *lvr = lvrQ.get();
234    typedef SmallVector<LiveInterval*, 4> LVRVec;
235    LVRVec splitLVRs;
236    unsigned availablePhysReg = selectOrSplit(*lvr, splitLVRs);
237    if (availablePhysReg) {
238      assert(splitLVRs.empty() && "inconsistent splitting");
239      assert(!vrm_->hasPhys(lvr->reg) && "duplicate vreg in interval unions");
240      vrm_->assignVirt2Phys(lvr->reg, availablePhysReg);
241      physReg2liu_[availablePhysReg].unify(*lvr);
242    }
243    else {
244      for (LVRVec::iterator lvrI = splitLVRs.begin(), lvrEnd = splitLVRs.end();
245           lvrI != lvrEnd; ++lvrI) {
246        assert(TargetRegisterInfo::isVirtualRegister((*lvrI)->reg) &&
247               "expect split value in virtual register");
248        lvrQ.push(*lvrI);
249      }
250    }
251  }
252}
253
254// Check if this live virtual reg interferes with a physical register. If not,
255// then check for interference on each register that aliases with the physical
256// register.
257bool RegAllocBase::checkPhysRegInterference(LiveIntervalUnion::Query &query,
258                                            unsigned preg) {
259  if (query.checkInterference())
260    return true;
261  for (const unsigned *asI = tri_->getAliasSet(preg); *asI; ++asI) {
262    // We assume it's very unlikely for a register in the alias set to also be
263    // in the original register class. So we don't bother caching the
264    // interference.
265    LiveIntervalUnion::Query subQuery(query.lvr(), physReg2liu_[*asI] );
266    if (subQuery.checkInterference())
267      return true;
268  }
269  return false;
270}
271
272//===----------------------------------------------------------------------===//
273//                         RABasic Implementation
274//===----------------------------------------------------------------------===//
275
276// Driver for the register assignment and splitting heuristics.
277// Manages iteration over the LiveIntervalUnions.
278//
279// Minimal implementation of register assignment and splitting--spills whenever
280// we run out of registers.
281//
282// selectOrSplit can only be called once per live virtual register. We then do a
283// single interference test for each register the correct class until we find an
284// available register. So, the number of interference tests in the worst case is
285// |vregs| * |machineregs|. And since the number of interference tests is
286// minimal, there is no value in caching them.
287unsigned RABasic::selectOrSplit(LiveInterval &lvr,
288                                SmallVectorImpl<LiveInterval*> &splitLVRs) {
289  // Check for an available reg in this class.
290  const TargetRegisterClass *trc = mri_->getRegClass(lvr.reg);
291  for (TargetRegisterClass::iterator trcI = trc->allocation_order_begin(*mf_),
292         trcEnd = trc->allocation_order_end(*mf_);
293       trcI != trcEnd; ++trcI) {
294    unsigned preg = *trcI;
295    LiveIntervalUnion::Query query(lvr, physReg2liu_[preg]);
296    if (!checkPhysRegInterference(query, preg)) {
297      DEBUG(dbgs() << "\tallocating: " << tri_->getName(preg) << lvr << '\n');
298      return preg;
299    }
300  }
301  DEBUG(dbgs() << "\tspilling: " << lvr << '\n');
302  SmallVector<LiveInterval*, 1> spillIs; // ignored
303  spiller_->spill(&lvr, splitLVRs, spillIs);
304
305  // FIXME: update LiveStacks
306  return 0;
307}
308
309bool RABasic::runOnMachineFunction(MachineFunction &mf) {
310  DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n"
311               << "********** Function: "
312               << ((Value*)mf.getFunction())->getName() << '\n');
313
314  mf_ = &mf;
315  tm_ = &mf.getTarget();
316  mri_ = &mf.getRegInfo();
317
318  DEBUG(rmf_ = &getAnalysis<RenderMachineFunction>());
319
320  RegAllocBase::init(*tm_->getRegisterInfo(), getAnalysis<VirtRegMap>(),
321                     getAnalysis<LiveIntervals>());
322
323  spiller_.reset(createSpiller(*this, *mf_, *vrm_));
324
325  allocatePhysRegs();
326
327  // Diagnostic output before rewriting
328  DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm_ << "\n");
329
330  // optional HTML output
331  DEBUG(rmf_->renderMachineFunction("After basic register allocation.", vrm_));
332
333  // Run rewriter
334  std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
335  rewriter->runOnMachineFunction(*mf_, *vrm_, lis_);
336
337  // The pass output is in VirtRegMap. Release all the transient data.
338  releaseMemory();
339
340  return true;
341}
342
343FunctionPass* llvm::createBasicRegisterAllocator()
344{
345  return new RABasic();
346}
347