RegAllocGreedy.cpp revision 770d42de3b7643b2b4f835f32e3a16275b9fbdba 
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  float calcInterferenceWeight(LiveInterval&, unsigned);
98
99  unsigned tryReassign(LiveInterval&, AllocationOrder&);
100  unsigned trySplit(LiveInterval&, AllocationOrder&,
101                    SmallVectorImpl<LiveInterval*>&);
102  unsigned trySpillInterferences(LiveInterval&, AllocationOrder&,
103                                 SmallVectorImpl<LiveInterval*>&);
104};
105} // end anonymous namespace
106
107char RAGreedy::ID = 0;
108
109FunctionPass* llvm::createGreedyRegisterAllocator() {
110  return new RAGreedy();
111}
112
113RAGreedy::RAGreedy(): MachineFunctionPass(ID) {
114  initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
115  initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
116  initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
117  initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
118  initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
119  initializeLiveStacksPass(*PassRegistry::getPassRegistry());
120  initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
121  initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
122  initializeMachineLoopRangesPass(*PassRegistry::getPassRegistry());
123  initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
124}
125
126void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
127  AU.setPreservesCFG();
128  AU.addRequired<AliasAnalysis>();
129  AU.addPreserved<AliasAnalysis>();
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<MachineDominatorTree>();
139  AU.addPreserved<MachineDominatorTree>();
140  AU.addRequired<MachineLoopInfo>();
141  AU.addPreserved<MachineLoopInfo>();
142  AU.addRequired<MachineLoopRanges>();
143  AU.addPreserved<MachineLoopRanges>();
144  AU.addRequired<VirtRegMap>();
145  AU.addPreserved<VirtRegMap>();
146  MachineFunctionPass::getAnalysisUsage(AU);
147}
148
149void RAGreedy::releaseMemory() {
150  SpillerInstance.reset(0);
151  RegAllocBase::releaseMemory();
152}
153
154float RAGreedy::getPriority(LiveInterval *LI) {
155  float Priority = LI->weight;
156
157  // Prioritize hinted registers so they are allocated first.
158  std::pair<unsigned, unsigned> Hint;
159  if (Hint.first || Hint.second) {
160    // The hint can be target specific, a virtual register, or a physreg.
161    Priority *= 2;
162
163    // Prefer physreg hints above anything else.
164    if (Hint.first == 0 && TargetRegisterInfo::isPhysicalRegister(Hint.second))
165      Priority *= 2;
166  }
167  return Priority;
168}
169
170
171//===----------------------------------------------------------------------===//
172//                         Register Reassignment
173//===----------------------------------------------------------------------===//
174
175// Check interference without using the cache.
176bool RAGreedy::checkUncachedInterference(LiveInterval &VirtReg,
177                                         unsigned PhysReg) {
178  for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
179    LiveIntervalUnion::Query subQ(&VirtReg, &PhysReg2LiveUnion[*AliasI]);
180    if (subQ.checkInterference())
181      return true;
182  }
183  return false;
184}
185
186/// getSingleInterference - Return the single interfering virtual register
187/// assigned to PhysReg. Return 0 if more than one virtual register is
188/// interfering.
189LiveInterval *RAGreedy::getSingleInterference(LiveInterval &VirtReg,
190                                              unsigned PhysReg) {
191  // Check physreg and aliases.
192  LiveInterval *Interference = 0;
193  for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
194    LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
195    if (Q.checkInterference()) {
196      if (Interference)
197        return 0;
198      Q.collectInterferingVRegs(1);
199      if (!Q.seenAllInterferences())
200        return 0;
201      Interference = Q.interferingVRegs().front();
202    }
203  }
204  return Interference;
205}
206
207// Attempt to reassign this virtual register to a different physical register.
208//
209// FIXME: we are not yet caching these "second-level" interferences discovered
210// in the sub-queries. These interferences can change with each call to
211// selectOrSplit. However, we could implement a "may-interfere" cache that
212// could be conservatively dirtied when we reassign or split.
213//
214// FIXME: This may result in a lot of alias queries. We could summarize alias
215// live intervals in their parent register's live union, but it's messy.
216bool RAGreedy::reassignVReg(LiveInterval &InterferingVReg,
217                            unsigned WantedPhysReg) {
218  assert(TargetRegisterInfo::isVirtualRegister(InterferingVReg.reg) &&
219         "Can only reassign virtual registers");
220  assert(TRI->regsOverlap(WantedPhysReg, VRM->getPhys(InterferingVReg.reg)) &&
221         "inconsistent phys reg assigment");
222
223  AllocationOrder Order(InterferingVReg.reg, *VRM, ReservedRegs);
224  while (unsigned PhysReg = Order.next()) {
225    // Don't reassign to a WantedPhysReg alias.
226    if (TRI->regsOverlap(PhysReg, WantedPhysReg))
227      continue;
228
229    if (checkUncachedInterference(InterferingVReg, PhysReg))
230      continue;
231
232    // Reassign the interfering virtual reg to this physical reg.
233    unsigned OldAssign = VRM->getPhys(InterferingVReg.reg);
234    DEBUG(dbgs() << "reassigning: " << InterferingVReg << " from " <<
235          TRI->getName(OldAssign) << " to " << TRI->getName(PhysReg) << '\n');
236    PhysReg2LiveUnion[OldAssign].extract(InterferingVReg);
237    VRM->clearVirt(InterferingVReg.reg);
238    VRM->assignVirt2Phys(InterferingVReg.reg, PhysReg);
239    PhysReg2LiveUnion[PhysReg].unify(InterferingVReg);
240
241    return true;
242  }
243  return false;
244}
245
246/// reassignInterferences - Reassign all interferences to different physical
247/// registers such that Virtreg can be assigned to PhysReg.
248/// Currently this only works with a single interference.
249/// @param  VirtReg Currently unassigned virtual register.
250/// @param  PhysReg Physical register to be cleared.
251/// @return True on success, false if nothing was changed.
252bool RAGreedy::reassignInterferences(LiveInterval &VirtReg, unsigned PhysReg) {
253  LiveInterval *InterferingVReg = getSingleInterference(VirtReg, PhysReg);
254  if (!InterferingVReg)
255    return false;
256  if (TargetRegisterInfo::isPhysicalRegister(InterferingVReg->reg))
257    return false;
258  return reassignVReg(*InterferingVReg, PhysReg);
259}
260
261/// tryReassign - Try to reassign interferences to different physregs.
262/// @param  VirtReg Currently unassigned virtual register.
263/// @param  Order   Physregs to try.
264/// @return         Physreg to assign VirtReg, or 0.
265unsigned RAGreedy::tryReassign(LiveInterval &VirtReg, AllocationOrder &Order) {
266  NamedRegionTimer T("Reassign", TimerGroupName, TimePassesIsEnabled);
267  Order.rewind();
268  while (unsigned PhysReg = Order.next())
269    if (reassignInterferences(VirtReg, PhysReg))
270      return PhysReg;
271  return 0;
272}
273
274
275//===----------------------------------------------------------------------===//
276//                              Loop Splitting
277//===----------------------------------------------------------------------===//
278
279/// findInterferenceFreeReg - Find a physical register in Order where Loop has
280/// no interferences with VirtReg.
281unsigned RAGreedy::findInterferenceFreeReg(MachineLoopRange *Loop,
282                                           LiveInterval &VirtReg,
283                                           AllocationOrder &Order) {
284  Order.rewind();
285  while (unsigned PhysReg = Order.next()) {
286    bool interference = false;
287    for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
288      if (query(VirtReg, *AI).checkLoopInterference(Loop)) {
289        interference = true;
290        break;
291      }
292    }
293    if (!interference)
294      return PhysReg;
295  }
296  // No physreg found.
297  return 0;
298}
299
300/// trySplit - Try to split VirtReg or one of its interferences, making it
301/// assignable.
302/// @return Physreg when VirtReg may be assigned and/or new SplitVRegs.
303unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
304                            SmallVectorImpl<LiveInterval*>&SplitVRegs) {
305  NamedRegionTimer T("Splitter", TimerGroupName, TimePassesIsEnabled);
306  SA->analyze(&VirtReg);
307
308  // Get the set of loops that have VirtReg uses and are splittable.
309  SplitAnalysis::LoopPtrSet SplitLoopSet;
310  SA->getSplitLoops(SplitLoopSet);
311
312  // Order loops by descending area.
313  SmallVector<MachineLoopRange*, 8> SplitLoops;
314  for (SplitAnalysis::LoopPtrSet::const_iterator I = SplitLoopSet.begin(),
315         E = SplitLoopSet.end(); I != E; ++I)
316    SplitLoops.push_back(LoopRanges->getLoopRange(*I));
317  array_pod_sort(SplitLoops.begin(), SplitLoops.end(),
318                 MachineLoopRange::byAreaDesc);
319
320  // Find the first loop that is interference-free for some register in the
321  // allocation order.
322  MachineLoopRange *Loop = 0;
323  for (unsigned i = 0, e = SplitLoops.size(); i != e; ++i) {
324    DEBUG(dbgs() << "  Checking " << *SplitLoops[i]);
325    if (unsigned PhysReg = findInterferenceFreeReg(SplitLoops[i],
326                                                   VirtReg, Order)) {
327      (void)PhysReg;
328      Loop = SplitLoops[i];
329      DEBUG(dbgs() << ": Use %" << TRI->getName(PhysReg) << '\n');
330      break;
331    } else {
332      DEBUG(dbgs() << ": Interference.\n");
333    }
334  }
335
336  if (!Loop) {
337    DEBUG(dbgs() << "  All candidate loops have interference.\n");
338    return 0;
339  }
340
341  // Execute the split around Loop.
342  SmallVector<LiveInterval*, 4> SpillRegs;
343  LiveRangeEdit LREdit(VirtReg, SplitVRegs, SpillRegs);
344  SplitEditor(*SA, *LIS, *VRM, *DomTree, LREdit)
345    .splitAroundLoop(Loop->getLoop());
346
347  if (VerifyEnabled)
348    MF->verify(this, "After splitting live range around loop");
349
350  // We have new split regs, don't assign anything.
351  return 0;
352}
353
354
355//===----------------------------------------------------------------------===//
356//                                Spilling
357//===----------------------------------------------------------------------===//
358
359/// calcInterferenceWeight - Calculate the combined spill weight of
360/// interferences when assigning VirtReg to PhysReg.
361float RAGreedy::calcInterferenceWeight(LiveInterval &VirtReg, unsigned PhysReg){
362  float Sum = 0;
363  for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
364    LiveIntervalUnion::Query &Q = query(VirtReg, *AI);
365    Q.collectInterferingVRegs();
366    if (Q.seenUnspillableVReg())
367      return HUGE_VALF;
368    for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i)
369      Sum += Q.interferingVRegs()[i]->weight;
370  }
371  return Sum;
372}
373
374/// trySpillInterferences - Try to spill interfering registers instead of the
375/// current one. Only do it if the accumulated spill weight is smaller than the
376/// current spill weight.
377unsigned RAGreedy::trySpillInterferences(LiveInterval &VirtReg,
378                                         AllocationOrder &Order,
379                                     SmallVectorImpl<LiveInterval*> &NewVRegs) {
380  NamedRegionTimer T("Spill Interference", TimerGroupName, TimePassesIsEnabled);
381  unsigned BestPhys = 0;
382  float BestWeight;
383
384  Order.rewind();
385  while (unsigned PhysReg = Order.next()) {
386    float Weight = calcInterferenceWeight(VirtReg, PhysReg);
387    if (Weight == HUGE_VALF || Weight >= VirtReg.weight)
388      continue;
389    if (!BestPhys || Weight < BestWeight)
390      BestPhys = PhysReg, BestWeight = Weight;
391  }
392
393  // No candidates found.
394  if (!BestPhys)
395    return 0;
396
397  // Collect all interfering registers.
398  SmallVector<LiveInterval*, 8> Spills;
399  for (const unsigned *AI = TRI->getOverlaps(BestPhys); *AI; ++AI) {
400    LiveIntervalUnion::Query &Q = query(VirtReg, *AI);
401    Spills.append(Q.interferingVRegs().begin(), Q.interferingVRegs().end());
402    for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) {
403      LiveInterval *VReg = Q.interferingVRegs()[i];
404      PhysReg2LiveUnion[*AI].extract(*VReg);
405      VRM->clearVirt(VReg->reg);
406    }
407  }
408
409  // Spill them all.
410  DEBUG(dbgs() << "spilling " << Spills.size() << " interferences with weight "
411               << BestWeight << '\n');
412  for (unsigned i = 0, e = Spills.size(); i != e; ++i)
413    spiller().spill(Spills[i], NewVRegs, Spills);
414  return BestPhys;
415}
416
417
418//===----------------------------------------------------------------------===//
419//                            Main Entry Point
420//===----------------------------------------------------------------------===//
421
422unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
423                                 SmallVectorImpl<LiveInterval*> &SplitVRegs) {
424  // First try assigning a free register.
425  AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs);
426  while (unsigned PhysReg = Order.next()) {
427    if (!checkPhysRegInterference(VirtReg, PhysReg))
428      return PhysReg;
429  }
430
431  // Try to reassign interferences.
432  if (unsigned PhysReg = tryReassign(VirtReg, Order))
433    return PhysReg;
434
435  // Try splitting VirtReg or interferences.
436  unsigned PhysReg = trySplit(VirtReg, Order, SplitVRegs);
437  if (PhysReg || !SplitVRegs.empty())
438    return PhysReg;
439
440  // Try to spill another interfering reg with less spill weight.
441  PhysReg = trySpillInterferences(VirtReg, Order, SplitVRegs);
442  if (PhysReg)
443    return PhysReg;
444
445  // Finally spill VirtReg itself.
446  NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled);
447  SmallVector<LiveInterval*, 1> pendingSpills;
448  spiller().spill(&VirtReg, SplitVRegs, pendingSpills);
449
450  // The live virtual register requesting allocation was spilled, so tell
451  // the caller not to allocate anything during this round.
452  return 0;
453}
454
455bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
456  DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
457               << "********** Function: "
458               << ((Value*)mf.getFunction())->getName() << '\n');
459
460  MF = &mf;
461  if (VerifyEnabled)
462    MF->verify(this, "Before greedy register allocator");
463
464  RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>());
465  DomTree = &getAnalysis<MachineDominatorTree>();
466  ReservedRegs = TRI->getReservedRegs(*MF);
467  SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
468  Loops = &getAnalysis<MachineLoopInfo>();
469  LoopRanges = &getAnalysis<MachineLoopRanges>();
470  SA.reset(new SplitAnalysis(*MF, *LIS, *Loops));
471
472  allocatePhysRegs();
473  addMBBLiveIns(MF);
474
475  // Run rewriter
476  {
477    NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled);
478    std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
479    rewriter->runOnMachineFunction(*MF, *VRM, LIS);
480  }
481
482  // The pass output is in VirtRegMap. Release all the transient data.
483  releaseMemory();
484
485  return true;
486}
487