RegAllocGreedy.cpp revision 90c1d7ddfc65654f7efe72d56cad65d1af9e6b2a 
1//===-- RegAllocGreedy.cpp - greedy 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 RAGreedy function pass for register allocation in
11// optimized builds.
12//
13//===----------------------------------------------------------------------===//
14
15#define DEBUG_TYPE "regalloc"
16#include "LiveIntervalUnion.h"
17#include "RegAllocBase.h"
18#include "Spiller.h"
19#include "VirtRegMap.h"
20#include "VirtRegRewriter.h"
21#include "llvm/Analysis/AliasAnalysis.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/MachineLoopInfo.h"
29#include "llvm/CodeGen/MachineRegisterInfo.h"
30#include "llvm/CodeGen/Passes.h"
31#include "llvm/CodeGen/RegAllocRegistry.h"
32#include "llvm/CodeGen/RegisterCoalescer.h"
33#include "llvm/Target/TargetOptions.h"
34#include "llvm/Support/Debug.h"
35#include "llvm/Support/ErrorHandling.h"
36#include "llvm/Support/raw_ostream.h"
37
38using namespace llvm;
39
40static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator",
41                                       createGreedyRegisterAllocator);
42
43namespace {
44class RAGreedy : public MachineFunctionPass, public RegAllocBase {
45  // context
46  MachineFunction *MF;
47  const TargetMachine *TM;
48  MachineRegisterInfo *MRI;
49
50  BitVector ReservedRegs;
51
52  // analyses
53  LiveStacks *LS;
54
55  // state
56  std::auto_ptr<Spiller> SpillerInstance;
57
58public:
59  RAGreedy();
60
61  /// Return the pass name.
62  virtual const char* getPassName() const {
63    return "Basic Register Allocator";
64  }
65
66  /// RAGreedy analysis usage.
67  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
68
69  virtual void releaseMemory();
70
71  virtual Spiller &spiller() { return *SpillerInstance; }
72
73  virtual float getPriority(LiveInterval *LI);
74
75  virtual unsigned selectOrSplit(LiveInterval &VirtReg,
76                                 SmallVectorImpl<LiveInterval*> &SplitVRegs);
77
78  /// Perform register allocation.
79  virtual bool runOnMachineFunction(MachineFunction &mf);
80
81  static char ID;
82};
83} // end anonymous namespace
84
85char RAGreedy::ID = 0;
86
87FunctionPass* llvm::createGreedyRegisterAllocator() {
88  return new RAGreedy();
89}
90
91RAGreedy::RAGreedy(): MachineFunctionPass(ID) {
92  initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
93  initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
94  initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
95  initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
96  initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
97  initializeLiveStacksPass(*PassRegistry::getPassRegistry());
98  initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
99  initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
100  initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
101}
102
103void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
104  AU.setPreservesCFG();
105  AU.addRequired<AliasAnalysis>();
106  AU.addPreserved<AliasAnalysis>();
107  AU.addRequired<LiveIntervals>();
108  AU.addPreserved<SlotIndexes>();
109  if (StrongPHIElim)
110    AU.addRequiredID(StrongPHIEliminationID);
111  AU.addRequiredTransitive<RegisterCoalescer>();
112  AU.addRequired<CalculateSpillWeights>();
113  AU.addRequired<LiveStacks>();
114  AU.addPreserved<LiveStacks>();
115  AU.addRequiredID(MachineDominatorsID);
116  AU.addPreservedID(MachineDominatorsID);
117  AU.addRequired<MachineLoopInfo>();
118  AU.addPreserved<MachineLoopInfo>();
119  AU.addRequired<VirtRegMap>();
120  AU.addPreserved<VirtRegMap>();
121  MachineFunctionPass::getAnalysisUsage(AU);
122}
123
124void RAGreedy::releaseMemory() {
125  SpillerInstance.reset(0);
126  RegAllocBase::releaseMemory();
127}
128
129float RAGreedy::getPriority(LiveInterval *LI) {
130  float Priority = LI->weight;
131
132  // Prioritize hinted registers so they are allocated first.
133  std::pair<unsigned, unsigned> Hint;
134  if (Hint.first || Hint.second) {
135    // The hint can be target specific, a virtual register, or a physreg.
136    Priority *= 2;
137
138    // Prefer physreg hints above anything else.
139    if (Hint.first == 0 && TargetRegisterInfo::isPhysicalRegister(Hint.second))
140      Priority *= 2;
141  }
142  return Priority;
143}
144
145unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
146                                SmallVectorImpl<LiveInterval*> &SplitVRegs) {
147  // Populate a list of physical register spill candidates.
148  SmallVector<unsigned, 8> PhysRegSpillCands;
149
150  // Check for an available register in this class.
151  const TargetRegisterClass *TRC = MRI->getRegClass(VirtReg.reg);
152  DEBUG(dbgs() << "RegClass: " << TRC->getName() << ' ');
153
154  // Preferred physical register computed from hints.
155  unsigned Hint = VRM->getRegAllocPref(VirtReg.reg);
156
157  // Try a hinted allocation.
158  if (Hint && !ReservedRegs.test(Hint) && TRC->contains(Hint) &&
159      checkPhysRegInterference(VirtReg, Hint) == 0)
160    return Hint;
161
162  for (TargetRegisterClass::iterator I = TRC->allocation_order_begin(*MF),
163         E = TRC->allocation_order_end(*MF);
164       I != E; ++I) {
165
166    unsigned PhysReg = *I;
167    if (ReservedRegs.test(PhysReg)) continue;
168
169    // Check interference and as a side effect, intialize queries for this
170    // VirtReg and its aliases.
171    unsigned interfReg = checkPhysRegInterference(VirtReg, PhysReg);
172    if (interfReg == 0) {
173      // Found an available register.
174      return PhysReg;
175    }
176    LiveInterval *interferingVirtReg =
177      Queries[interfReg].firstInterference().liveUnionPos().value();
178
179    // The current VirtReg must either spillable, or one of its interferences
180    // must have less spill weight.
181    if (interferingVirtReg->weight < VirtReg.weight ) {
182      PhysRegSpillCands.push_back(PhysReg);
183    }
184  }
185  // Try to spill another interfering reg with less spill weight.
186  //
187  // FIXME: RAGreedy will sort this list by spill weight.
188  for (SmallVectorImpl<unsigned>::iterator PhysRegI = PhysRegSpillCands.begin(),
189         PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) {
190
191    if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs)) continue;
192
193    assert(checkPhysRegInterference(VirtReg, *PhysRegI) == 0 &&
194           "Interference after spill.");
195    // Tell the caller to allocate to this newly freed physical register.
196    return *PhysRegI;
197  }
198  // No other spill candidates were found, so spill the current VirtReg.
199  DEBUG(dbgs() << "spilling: " << VirtReg << '\n');
200  SmallVector<LiveInterval*, 1> pendingSpills;
201
202  spiller().spill(&VirtReg, SplitVRegs, pendingSpills);
203
204  // The live virtual register requesting allocation was spilled, so tell
205  // the caller not to allocate anything during this round.
206  return 0;
207}
208
209bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
210  DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
211               << "********** Function: "
212               << ((Value*)mf.getFunction())->getName() << '\n');
213
214  MF = &mf;
215  TM = &mf.getTarget();
216  MRI = &mf.getRegInfo();
217
218  const TargetRegisterInfo *TRI = TM->getRegisterInfo();
219  RegAllocBase::init(*TRI, getAnalysis<VirtRegMap>(),
220                     getAnalysis<LiveIntervals>());
221
222  ReservedRegs = TRI->getReservedRegs(*MF);
223  SpillerInstance.reset(createSpiller(*this, *MF, *VRM));
224  allocatePhysRegs();
225  addMBBLiveIns(MF);
226
227  // Run rewriter
228  std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
229  rewriter->runOnMachineFunction(*MF, *VRM, LIS);
230
231  // The pass output is in VirtRegMap. Release all the transient data.
232  releaseMemory();
233
234  return true;
235}
236
237