RegAllocGreedy.cpp revision f428eb6c1b09a2322b7a577b0bf2e49dd107bcea 
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 "LiveRangeEdit.h"
19#include "RegAllocBase.h"
20#include "Spiller.h"
21#include "SplitKit.h"
22#include "VirtRegMap.h"
23#include "VirtRegRewriter.h"
24#include "llvm/Analysis/AliasAnalysis.h"
25#include "llvm/Function.h"
26#include "llvm/PassAnalysisSupport.h"
27#include "llvm/CodeGen/CalcSpillWeights.h"
28#include "llvm/CodeGen/LiveIntervalAnalysis.h"
29#include "llvm/CodeGen/LiveStackAnalysis.h"
30#include "llvm/CodeGen/MachineDominators.h"
31#include "llvm/CodeGen/MachineFunctionPass.h"
32#include "llvm/CodeGen/MachineLoopInfo.h"
33#include "llvm/CodeGen/MachineLoopRanges.h"
34#include "llvm/CodeGen/MachineRegisterInfo.h"
35#include "llvm/CodeGen/Passes.h"
36#include "llvm/CodeGen/RegAllocRegistry.h"
37#include "llvm/CodeGen/RegisterCoalescer.h"
38#include "llvm/Target/TargetOptions.h"
39#include "llvm/Support/Debug.h"
40#include "llvm/Support/ErrorHandling.h"
41#include "llvm/Support/raw_ostream.h"
42#include "llvm/Support/Timer.h"
43
44using namespace llvm;
45
46static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator",
47                                       createGreedyRegisterAllocator);
48
49namespace {
50class RAGreedy : public MachineFunctionPass, public RegAllocBase {
51  // context
52  MachineFunction *MF;
53  BitVector ReservedRegs;
54
55  // analyses
56  LiveStacks *LS;
57  MachineDominatorTree *DomTree;
58  MachineLoopInfo *Loops;
59  MachineLoopRanges *LoopRanges;
60
61  // state
62  std::auto_ptr<Spiller> SpillerInstance;
63  std::auto_ptr<SplitAnalysis> SA;
64
65public:
66  RAGreedy();
67
68  /// Return the pass name.
69  virtual const char* getPassName() const {
70    return "Greedy Register Allocator";
71  }
72
73  /// RAGreedy analysis usage.
74  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
75
76  virtual void releaseMemory();
77
78  virtual Spiller &spiller() { return *SpillerInstance; }
79
80  virtual float getPriority(LiveInterval *LI);
81
82  virtual unsigned selectOrSplit(LiveInterval &VirtReg,
83                                 SmallVectorImpl<LiveInterval*> &SplitVRegs);
84
85  /// Perform register allocation.
86  virtual bool runOnMachineFunction(MachineFunction &mf);
87
88  static char ID;
89
90private:
91  bool checkUncachedInterference(LiveInterval&, unsigned);
92  LiveInterval *getSingleInterference(LiveInterval&, unsigned);
93  bool reassignVReg(LiveInterval &InterferingVReg, unsigned OldPhysReg);
94  bool reassignInterferences(LiveInterval &VirtReg, unsigned PhysReg);
95  unsigned findInterferenceFreeReg(MachineLoopRange*,
96                                   LiveInterval&, AllocationOrder&);
97
98  unsigned tryReassign(LiveInterval&, AllocationOrder&);
99  unsigned trySplit(LiveInterval&, AllocationOrder&,
100                    SmallVectorImpl<LiveInterval*>&);
101};
102} // end anonymous namespace
103
104char RAGreedy::ID = 0;
105
106FunctionPass* llvm::createGreedyRegisterAllocator() {
107  return new RAGreedy();
108}
109
110RAGreedy::RAGreedy(): MachineFunctionPass(ID) {
111  initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
112  initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
113  initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
114  initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
115  initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
116  initializeLiveStacksPass(*PassRegistry::getPassRegistry());
117  initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
118  initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
119  initializeMachineLoopRangesPass(*PassRegistry::getPassRegistry());
120  initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
121}
122
123void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
124  AU.setPreservesCFG();
125  AU.addRequired<AliasAnalysis>();
126  AU.addPreserved<AliasAnalysis>();
127  AU.addRequired<LiveIntervals>();
128  AU.addPreserved<SlotIndexes>();
129  if (StrongPHIElim)
130    AU.addRequiredID(StrongPHIEliminationID);
131  AU.addRequiredTransitive<RegisterCoalescer>();
132  AU.addRequired<CalculateSpillWeights>();
133  AU.addRequired<LiveStacks>();
134  AU.addPreserved<LiveStacks>();
135  AU.addRequired<MachineDominatorTree>();
136  AU.addPreserved<MachineDominatorTree>();
137  AU.addRequired<MachineLoopInfo>();
138  AU.addPreserved<MachineLoopInfo>();
139  AU.addRequired<MachineLoopRanges>();
140  AU.addPreserved<MachineLoopRanges>();
141  AU.addRequired<VirtRegMap>();
142  AU.addPreserved<VirtRegMap>();
143  MachineFunctionPass::getAnalysisUsage(AU);
144}
145
146void RAGreedy::releaseMemory() {
147  SpillerInstance.reset(0);
148  RegAllocBase::releaseMemory();
149}
150
151float RAGreedy::getPriority(LiveInterval *LI) {
152  float Priority = LI->weight;
153
154  // Prioritize hinted registers so they are allocated first.
155  std::pair<unsigned, unsigned> Hint;
156  if (Hint.first || Hint.second) {
157    // The hint can be target specific, a virtual register, or a physreg.
158    Priority *= 2;
159
160    // Prefer physreg hints above anything else.
161    if (Hint.first == 0 && TargetRegisterInfo::isPhysicalRegister(Hint.second))
162      Priority *= 2;
163  }
164  return Priority;
165}
166
167// Check interference without using the cache.
168bool RAGreedy::checkUncachedInterference(LiveInterval &VirtReg,
169                                         unsigned PhysReg) {
170  for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
171    LiveIntervalUnion::Query subQ(&VirtReg, &PhysReg2LiveUnion[*AliasI]);
172    if (subQ.checkInterference())
173      return true;
174  }
175  return false;
176}
177
178/// getSingleInterference - Return the single interfering virtual register
179/// assigned to PhysReg. Return 0 if more than one virtual register is
180/// interfering.
181LiveInterval *RAGreedy::getSingleInterference(LiveInterval &VirtReg,
182                                              unsigned PhysReg) {
183  // Check physreg and aliases.
184  LiveInterval *Interference = 0;
185  for (const unsigned *AliasI = TRI->getOverlaps(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/// findInterferenceFreeReg - Find a physical register in Order where Loop has
267/// no interferences with VirtReg.
268unsigned RAGreedy::findInterferenceFreeReg(MachineLoopRange *Loop,
269                                           LiveInterval &VirtReg,
270                                           AllocationOrder &Order) {
271  Order.rewind();
272  while (unsigned PhysReg = Order.next()) {
273    bool interference = false;
274    for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
275      if (query(VirtReg, *AI).checkLoopInterference(Loop)) {
276        interference = true;
277        break;
278      }
279    }
280    if (!interference)
281      return PhysReg;
282  }
283  // No physreg found.
284  return 0;
285}
286
287/// trySplit - Try to split VirtReg or one of its interferences, making it
288/// assignable.
289/// @return Physreg when VirtReg may be assigned and/or new SplitVRegs.
290unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
291                            SmallVectorImpl<LiveInterval*>&SplitVRegs) {
292  NamedRegionTimer T("Splitter", TimerGroupName, TimePassesIsEnabled);
293  SA->analyze(&VirtReg);
294
295  // Get the set of loops that have VirtReg uses and are splittable.
296  SplitAnalysis::LoopPtrSet SplitLoopSet;
297  SA->getSplitLoops(SplitLoopSet);
298
299  // Order loops by descending area.
300  SmallVector<MachineLoopRange*, 8> SplitLoops;
301  for (SplitAnalysis::LoopPtrSet::const_iterator I = SplitLoopSet.begin(),
302         E = SplitLoopSet.end(); I != E; ++I)
303    SplitLoops.push_back(LoopRanges->getLoopRange(*I));
304  array_pod_sort(SplitLoops.begin(), SplitLoops.end(),
305                 MachineLoopRange::byAreaDesc);
306
307  // Find the first loop that is interference-free for some register in the
308  // allocation order.
309  MachineLoopRange *Loop = 0;
310  for (unsigned i = 0, e = SplitLoops.size(); i != e; ++i) {
311    if (unsigned PhysReg = findInterferenceFreeReg(SplitLoops[i],
312                                                   VirtReg, Order)) {
313      Loop = SplitLoops[i];
314      DEBUG(dbgs() << "  " << TRI->getName(PhysReg)
315                   << " has no interferences in " << *Loop << '\n');
316      break;
317    }
318  }
319
320  if (!Loop) {
321    DEBUG(dbgs() << "  All candidate loops have interference.\n");
322    return 0;
323  }
324
325  // Execute the split around Loop.
326  SmallVector<LiveInterval*, 4> SpillRegs;
327  LiveRangeEdit LREdit(VirtReg, SplitVRegs, SpillRegs);
328  SplitEditor(*SA, *LIS, *VRM, *DomTree, LREdit)
329    .splitAroundLoop(Loop->getLoop());
330
331  // We have new split regs, don't assign anything.
332  return 0;
333}
334
335unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
336                                SmallVectorImpl<LiveInterval*> &SplitVRegs) {
337  // Populate a list of physical register spill candidates.
338  SmallVector<unsigned, 8> PhysRegSpillCands;
339
340  // Check for an available register in this class.
341  AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs);
342  while (unsigned PhysReg = Order.next()) {
343    // Check interference and as a side effect, intialize queries for this
344    // VirtReg and its aliases.
345    unsigned InterfReg = checkPhysRegInterference(VirtReg, PhysReg);
346    if (InterfReg == 0) {
347      // Found an available register.
348      return PhysReg;
349    }
350    assert(!VirtReg.empty() && "Empty VirtReg has interference");
351    LiveInterval *InterferingVirtReg =
352      Queries[InterfReg].firstInterference().liveUnionPos().value();
353
354    // The current VirtReg must either be spillable, or one of its interferences
355    // must have less spill weight.
356    if (InterferingVirtReg->weight < VirtReg.weight )
357      PhysRegSpillCands.push_back(PhysReg);
358  }
359
360  // Try to reassign interferences.
361  if (unsigned PhysReg = tryReassign(VirtReg, Order))
362    return PhysReg;
363
364  // Try splitting VirtReg or interferences.
365  unsigned PhysReg = trySplit(VirtReg, Order, SplitVRegs);
366  if (PhysReg || !SplitVRegs.empty())
367    return PhysReg;
368
369  // Try to spill another interfering reg with less spill weight.
370  NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled);
371  //
372  // FIXME: do this in two steps: (1) check for unspillable interferences while
373  // accumulating spill weight; (2) spill the interferences with lowest
374  // aggregate spill weight.
375  for (SmallVectorImpl<unsigned>::iterator PhysRegI = PhysRegSpillCands.begin(),
376         PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) {
377
378    if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs)) continue;
379
380    assert(checkPhysRegInterference(VirtReg, *PhysRegI) == 0 &&
381           "Interference after spill.");
382    // Tell the caller to allocate to this newly freed physical register.
383    return *PhysRegI;
384  }
385
386  // No other spill candidates were found, so spill the current VirtReg.
387  DEBUG(dbgs() << "spilling: " << VirtReg << '\n');
388  SmallVector<LiveInterval*, 1> pendingSpills;
389
390  spiller().spill(&VirtReg, SplitVRegs, pendingSpills);
391
392  // The live virtual register requesting allocation was spilled, so tell
393  // the caller not to allocate anything during this round.
394  return 0;
395}
396
397bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
398  DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
399               << "********** Function: "
400               << ((Value*)mf.getFunction())->getName() << '\n');
401
402  MF = &mf;
403  RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>());
404  DomTree = &getAnalysis<MachineDominatorTree>();
405  ReservedRegs = TRI->getReservedRegs(*MF);
406  SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
407  Loops = &getAnalysis<MachineLoopInfo>();
408  LoopRanges = &getAnalysis<MachineLoopRanges>();
409  SA.reset(new SplitAnalysis(*MF, *LIS, *Loops));
410
411  allocatePhysRegs();
412  addMBBLiveIns(MF);
413
414  // Run rewriter
415  {
416    NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled);
417    std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
418    rewriter->runOnMachineFunction(*MF, *VRM, LIS);
419  }
420
421  // The pass output is in VirtRegMap. Release all the transient data.
422  releaseMemory();
423
424  return true;
425}
426