RegAllocGreedy.cpp revision 3ef9f3da397d27e2340742274a7f6e8b8f1149cf 
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 "AllocationOrder.h"
17#include "LiveIntervalUnion.h"
18#include "RegAllocBase.h"
19#include "Spiller.h"
20#include "VirtRegMap.h"
21#include "VirtRegRewriter.h"
22#include "llvm/Analysis/AliasAnalysis.h"
23#include "llvm/Function.h"
24#include "llvm/PassAnalysisSupport.h"
25#include "llvm/CodeGen/CalcSpillWeights.h"
26#include "llvm/CodeGen/LiveIntervalAnalysis.h"
27#include "llvm/CodeGen/LiveStackAnalysis.h"
28#include "llvm/CodeGen/MachineFunctionPass.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/TargetOptions.h"
35#include "llvm/Support/Debug.h"
36#include "llvm/Support/ErrorHandling.h"
37#include "llvm/Support/raw_ostream.h"
38#include "llvm/Support/Timer.h"
39
40using namespace llvm;
41
42static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator",
43                                       createGreedyRegisterAllocator);
44
45namespace {
46class RAGreedy : public MachineFunctionPass, public RegAllocBase {
47  // context
48  MachineFunction *MF;
49  BitVector ReservedRegs;
50
51  // analyses
52  LiveStacks *LS;
53
54  // state
55  std::auto_ptr<Spiller> SpillerInstance;
56
57public:
58  RAGreedy();
59
60  /// Return the pass name.
61  virtual const char* getPassName() const {
62    return "Greedy Register Allocator";
63  }
64
65  /// RAGreedy analysis usage.
66  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
67
68  virtual void releaseMemory();
69
70  virtual Spiller &spiller() { return *SpillerInstance; }
71
72  virtual float getPriority(LiveInterval *LI);
73
74  virtual unsigned selectOrSplit(LiveInterval &VirtReg,
75                                 SmallVectorImpl<LiveInterval*> &SplitVRegs);
76
77  /// Perform register allocation.
78  virtual bool runOnMachineFunction(MachineFunction &mf);
79
80  static char ID;
81
82private:
83  bool checkUncachedInterference(LiveInterval&, unsigned);
84  LiveInterval *getSingleInterference(LiveInterval&, unsigned);
85  bool reassignVReg(LiveInterval &InterferingVReg, unsigned OldPhysReg);
86  bool reassignInterferences(LiveInterval &VirtReg, unsigned PhysReg);
87
88  unsigned tryReassign(LiveInterval&, AllocationOrder&);
89  unsigned trySplit(LiveInterval&, AllocationOrder&,
90                    SmallVectorImpl<LiveInterval*>&);
91};
92} // end anonymous namespace
93
94char RAGreedy::ID = 0;
95
96FunctionPass* llvm::createGreedyRegisterAllocator() {
97  return new RAGreedy();
98}
99
100RAGreedy::RAGreedy(): MachineFunctionPass(ID) {
101  initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
102  initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
103  initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
104  initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
105  initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
106  initializeLiveStacksPass(*PassRegistry::getPassRegistry());
107  initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
108  initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
109  initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
110}
111
112void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
113  AU.setPreservesCFG();
114  AU.addRequired<AliasAnalysis>();
115  AU.addPreserved<AliasAnalysis>();
116  AU.addRequired<LiveIntervals>();
117  AU.addPreserved<SlotIndexes>();
118  if (StrongPHIElim)
119    AU.addRequiredID(StrongPHIEliminationID);
120  AU.addRequiredTransitive<RegisterCoalescer>();
121  AU.addRequired<CalculateSpillWeights>();
122  AU.addRequired<LiveStacks>();
123  AU.addPreserved<LiveStacks>();
124  AU.addRequiredID(MachineDominatorsID);
125  AU.addPreservedID(MachineDominatorsID);
126  AU.addRequired<MachineLoopInfo>();
127  AU.addPreserved<MachineLoopInfo>();
128  AU.addRequired<VirtRegMap>();
129  AU.addPreserved<VirtRegMap>();
130  MachineFunctionPass::getAnalysisUsage(AU);
131}
132
133void RAGreedy::releaseMemory() {
134  SpillerInstance.reset(0);
135  RegAllocBase::releaseMemory();
136}
137
138float RAGreedy::getPriority(LiveInterval *LI) {
139  float Priority = LI->weight;
140
141  // Prioritize hinted registers so they are allocated first.
142  std::pair<unsigned, unsigned> Hint;
143  if (Hint.first || Hint.second) {
144    // The hint can be target specific, a virtual register, or a physreg.
145    Priority *= 2;
146
147    // Prefer physreg hints above anything else.
148    if (Hint.first == 0 && TargetRegisterInfo::isPhysicalRegister(Hint.second))
149      Priority *= 2;
150  }
151  return Priority;
152}
153
154// Check interference without using the cache.
155bool RAGreedy::checkUncachedInterference(LiveInterval &VirtReg,
156                                         unsigned PhysReg) {
157  LiveIntervalUnion::Query subQ(&VirtReg, &PhysReg2LiveUnion[PhysReg]);
158  if (subQ.checkInterference())
159      return true;
160  for (const unsigned *AliasI = TRI->getAliasSet(PhysReg); *AliasI; ++AliasI) {
161    subQ.init(&VirtReg, &PhysReg2LiveUnion[*AliasI]);
162    if (subQ.checkInterference())
163      return true;
164  }
165  return false;
166}
167
168/// getSingleInterference - Return the single interfering virtual register
169/// assigned to PhysReg. Return 0 if more than one virtual register is
170/// interfering.
171LiveInterval *RAGreedy::getSingleInterference(LiveInterval &VirtReg,
172                                              unsigned PhysReg) {
173  LiveInterval *Interference = 0;
174
175  // Check direct interferences.
176  LiveIntervalUnion::Query &Q = query(VirtReg, PhysReg);
177  if (Q.checkInterference()) {
178    Q.collectInterferingVRegs(1);
179    if (!Q.seenAllInterferences())
180      return 0;
181    Interference = Q.interferingVRegs().front();
182  }
183
184  // Check aliases.
185  for (const unsigned *AliasI = TRI->getAliasSet(PhysReg); *AliasI; ++AliasI) {
186    LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
187    if (Q.checkInterference()) {
188      if (Interference)
189        return 0;
190      Q.collectInterferingVRegs(1);
191      if (!Q.seenAllInterferences())
192        return 0;
193      Interference = Q.interferingVRegs().front();
194    }
195  }
196  return Interference;
197}
198
199// Attempt to reassign this virtual register to a different physical register.
200//
201// FIXME: we are not yet caching these "second-level" interferences discovered
202// in the sub-queries. These interferences can change with each call to
203// selectOrSplit. However, we could implement a "may-interfere" cache that
204// could be conservatively dirtied when we reassign or split.
205//
206// FIXME: This may result in a lot of alias queries. We could summarize alias
207// live intervals in their parent register's live union, but it's messy.
208bool RAGreedy::reassignVReg(LiveInterval &InterferingVReg,
209                            unsigned WantedPhysReg) {
210  assert(TargetRegisterInfo::isVirtualRegister(InterferingVReg.reg) &&
211         "Can only reassign virtual registers");
212  assert(TRI->regsOverlap(WantedPhysReg, VRM->getPhys(InterferingVReg.reg)) &&
213         "inconsistent phys reg assigment");
214
215  AllocationOrder Order(InterferingVReg.reg, *VRM, ReservedRegs);
216  while (unsigned PhysReg = Order.next()) {
217    // Don't reassign to a WantedPhysReg alias.
218    if (TRI->regsOverlap(PhysReg, WantedPhysReg))
219      continue;
220
221    if (checkUncachedInterference(InterferingVReg, PhysReg))
222      continue;
223
224    // Reassign the interfering virtual reg to this physical reg.
225    unsigned OldAssign = VRM->getPhys(InterferingVReg.reg);
226    DEBUG(dbgs() << "reassigning: " << InterferingVReg << " from " <<
227          TRI->getName(OldAssign) << " to " << TRI->getName(PhysReg) << '\n');
228    PhysReg2LiveUnion[OldAssign].extract(InterferingVReg);
229    VRM->clearVirt(InterferingVReg.reg);
230    VRM->assignVirt2Phys(InterferingVReg.reg, PhysReg);
231    PhysReg2LiveUnion[PhysReg].unify(InterferingVReg);
232
233    return true;
234  }
235  return false;
236}
237
238/// reassignInterferences - Reassign all interferences to different physical
239/// registers such that Virtreg can be assigned to PhysReg.
240/// Currently this only works with a single interference.
241/// @param  VirtReg Currently unassigned virtual register.
242/// @param  PhysReg Physical register to be cleared.
243/// @return True on success, false if nothing was changed.
244bool RAGreedy::reassignInterferences(LiveInterval &VirtReg, unsigned PhysReg) {
245  LiveInterval *InterferingVReg = getSingleInterference(VirtReg, PhysReg);
246  if (!InterferingVReg)
247    return false;
248  if (TargetRegisterInfo::isPhysicalRegister(InterferingVReg->reg))
249    return false;
250  return reassignVReg(*InterferingVReg, PhysReg);
251}
252
253/// tryReassign - Try to reassign interferences to different physregs.
254/// @param  VirtReg Currently unassigned virtual register.
255/// @param  Order   Physregs to try.
256/// @return         Physreg to assign VirtReg, or 0.
257unsigned RAGreedy::tryReassign(LiveInterval &VirtReg, AllocationOrder &Order) {
258  NamedRegionTimer T("Reassign", TimerGroupName, TimePassesIsEnabled);
259  Order.rewind();
260  while (unsigned PhysReg = Order.next())
261    if (reassignInterferences(VirtReg, PhysReg))
262      return PhysReg;
263  return 0;
264}
265
266/// trySplit - Try to split VirtReg or one of its interferences, making it
267/// assignable.
268/// @return Physreg when VirtReg may be assigned and/or new SplitVRegs.
269unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
270                            SmallVectorImpl<LiveInterval*>&SplitVRegs) {
271  NamedRegionTimer T("Splitter", TimerGroupName, TimePassesIsEnabled);
272  DEBUG({
273    Order.rewind();
274    while (unsigned PhysReg = Order.next()) {
275        query(VirtReg, PhysReg).print(dbgs(), TRI);
276        for (const unsigned *AI = TRI->getAliasSet(PhysReg); *AI; ++AI)
277          query(VirtReg, *AI).print(dbgs(), TRI);
278    }
279  });
280  return 0;
281}
282
283unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
284                                SmallVectorImpl<LiveInterval*> &SplitVRegs) {
285  // Populate a list of physical register spill candidates.
286  SmallVector<unsigned, 8> PhysRegSpillCands;
287
288  // Check for an available register in this class.
289  AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs);
290  while (unsigned PhysReg = Order.next()) {
291    // Check interference and as a side effect, intialize queries for this
292    // VirtReg and its aliases.
293    unsigned InterfReg = checkPhysRegInterference(VirtReg, PhysReg);
294    if (InterfReg == 0) {
295      // Found an available register.
296      return PhysReg;
297    }
298    assert(!VirtReg.empty() && "Empty VirtReg has interference");
299    LiveInterval *InterferingVirtReg =
300      Queries[InterfReg].firstInterference().liveUnionPos().value();
301
302    // The current VirtReg must either be spillable, or one of its interferences
303    // must have less spill weight.
304    if (InterferingVirtReg->weight < VirtReg.weight )
305      PhysRegSpillCands.push_back(PhysReg);
306  }
307
308  // Try to reassign interferences.
309  if (unsigned PhysReg = tryReassign(VirtReg, Order))
310    return PhysReg;
311
312  // Try splitting VirtReg or interferences.
313  unsigned PhysReg = trySplit(VirtReg, Order, SplitVRegs);
314  if (PhysReg || !SplitVRegs.empty())
315    return PhysReg;
316
317  // Try to spill another interfering reg with less spill weight.
318  NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled);
319  //
320  // FIXME: do this in two steps: (1) check for unspillable interferences while
321  // accumulating spill weight; (2) spill the interferences with lowest
322  // aggregate spill weight.
323  for (SmallVectorImpl<unsigned>::iterator PhysRegI = PhysRegSpillCands.begin(),
324         PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) {
325
326    if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs)) continue;
327
328    assert(checkPhysRegInterference(VirtReg, *PhysRegI) == 0 &&
329           "Interference after spill.");
330    // Tell the caller to allocate to this newly freed physical register.
331    return *PhysRegI;
332  }
333
334  // No other spill candidates were found, so spill the current VirtReg.
335  DEBUG(dbgs() << "spilling: " << VirtReg << '\n');
336  SmallVector<LiveInterval*, 1> pendingSpills;
337
338  spiller().spill(&VirtReg, SplitVRegs, pendingSpills);
339
340  // The live virtual register requesting allocation was spilled, so tell
341  // the caller not to allocate anything during this round.
342  return 0;
343}
344
345bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
346  DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
347               << "********** Function: "
348               << ((Value*)mf.getFunction())->getName() << '\n');
349
350  MF = &mf;
351  RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>());
352
353  ReservedRegs = TRI->getReservedRegs(*MF);
354  SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
355  allocatePhysRegs();
356  addMBBLiveIns(MF);
357
358  // Run rewriter
359  {
360    NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled);
361    std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
362    rewriter->runOnMachineFunction(*MF, *VRM, LIS);
363  }
364
365  // The pass output is in VirtRegMap. Release all the transient data.
366  releaseMemory();
367
368  return true;
369}
370