RegAllocGreedy.cpp revision 2dfbb3e9125aa0a66feab7a7638815b57da85968 
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 "SpillPlacement.h"
22#include "SplitKit.h"
23#include "VirtRegMap.h"
24#include "VirtRegRewriter.h"
25#include "llvm/Analysis/AliasAnalysis.h"
26#include "llvm/Function.h"
27#include "llvm/PassAnalysisSupport.h"
28#include "llvm/CodeGen/CalcSpillWeights.h"
29#include "llvm/CodeGen/EdgeBundles.h"
30#include "llvm/CodeGen/LiveIntervalAnalysis.h"
31#include "llvm/CodeGen/LiveStackAnalysis.h"
32#include "llvm/CodeGen/MachineDominators.h"
33#include "llvm/CodeGen/MachineFunctionPass.h"
34#include "llvm/CodeGen/MachineLoopInfo.h"
35#include "llvm/CodeGen/MachineLoopRanges.h"
36#include "llvm/CodeGen/MachineRegisterInfo.h"
37#include "llvm/CodeGen/Passes.h"
38#include "llvm/CodeGen/RegAllocRegistry.h"
39#include "llvm/CodeGen/RegisterCoalescer.h"
40#include "llvm/Target/TargetOptions.h"
41#include "llvm/Support/Debug.h"
42#include "llvm/Support/ErrorHandling.h"
43#include "llvm/Support/raw_ostream.h"
44#include "llvm/Support/Timer.h"
45
46using namespace llvm;
47
48static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator",
49                                       createGreedyRegisterAllocator);
50
51namespace {
52class RAGreedy : public MachineFunctionPass, public RegAllocBase {
53  // context
54  MachineFunction *MF;
55  BitVector ReservedRegs;
56
57  // analyses
58  SlotIndexes *Indexes;
59  LiveStacks *LS;
60  MachineDominatorTree *DomTree;
61  MachineLoopInfo *Loops;
62  MachineLoopRanges *LoopRanges;
63  EdgeBundles *Bundles;
64  SpillPlacement *SpillPlacer;
65
66  // state
67  std::auto_ptr<Spiller> SpillerInstance;
68  std::auto_ptr<SplitAnalysis> SA;
69
70  // splitting state.
71
72  /// All basic blocks where the current register is live.
73  SmallVector<SpillPlacement::BlockConstraint, 8> SpillConstraints;
74
75  /// Additional information about basic blocks where the current variable is
76  /// live. Such a block will look like one of these templates:
77  ///
78  ///  1. |   o---x   | Internal to block. Variable is only live in this block.
79  ///  2. |---x       | Live-in, kill.
80  ///  3. |       o---| Def, live-out.
81  ///  4. |---x   o---| Live-in, kill, def, live-out.
82  ///  5. |---o---o---| Live-through with uses or defs.
83  ///  6. |-----------| Live-through without uses. Transparent.
84  ///
85  struct BlockInfo {
86    MachineBasicBlock *MBB;
87    SlotIndex FirstUse;   ///< First instr using current reg.
88    SlotIndex LastUse;    ///< Last instr using current reg.
89    SlotIndex Kill;       ///< Interval end point inside block.
90    SlotIndex Def;        ///< Interval start point inside block.
91    bool Uses;            ///< Current reg has uses or defs in block.
92    bool LiveThrough;     ///< Live in whole block (Templ 5. or 6. above).
93    bool LiveIn;          ///< Current reg is live in.
94    bool LiveOut;         ///< Current reg is live out.
95
96    // Per-interference pattern scratch data.
97    bool OverlapEntry;    ///< Interference overlaps entering interval.
98    bool OverlapExit;     ///< Interference overlaps exiting interval.
99  };
100
101  /// Basic blocks where var is live. This array is parallel to
102  /// SpillConstraints.
103  SmallVector<BlockInfo, 8> LiveBlocks;
104
105public:
106  RAGreedy();
107
108  /// Return the pass name.
109  virtual const char* getPassName() const {
110    return "Greedy Register Allocator";
111  }
112
113  /// RAGreedy analysis usage.
114  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
115
116  virtual void releaseMemory();
117
118  virtual Spiller &spiller() { return *SpillerInstance; }
119
120  virtual float getPriority(LiveInterval *LI);
121
122  virtual unsigned selectOrSplit(LiveInterval&,
123                                 SmallVectorImpl<LiveInterval*>&);
124
125  /// Perform register allocation.
126  virtual bool runOnMachineFunction(MachineFunction &mf);
127
128  static char ID;
129
130private:
131  bool checkUncachedInterference(LiveInterval&, unsigned);
132  LiveInterval *getSingleInterference(LiveInterval&, unsigned);
133  bool reassignVReg(LiveInterval &InterferingVReg, unsigned OldPhysReg);
134  bool reassignInterferences(LiveInterval &VirtReg, unsigned PhysReg);
135  float calcInterferenceWeight(LiveInterval&, unsigned);
136  void calcLiveBlockInfo(LiveInterval&);
137  float calcInterferenceInfo(LiveInterval&, unsigned);
138  float calcGlobalSplitCost(const BitVector&);
139  void splitAroundRegion(LiveInterval&, unsigned, const BitVector&,
140                         SmallVectorImpl<LiveInterval*>&);
141
142  unsigned tryReassign(LiveInterval&, AllocationOrder&);
143  unsigned tryRegionSplit(LiveInterval&, AllocationOrder&,
144                          SmallVectorImpl<LiveInterval*>&);
145  unsigned trySplit(LiveInterval&, AllocationOrder&,
146                    SmallVectorImpl<LiveInterval*>&);
147  unsigned trySpillInterferences(LiveInterval&, AllocationOrder&,
148                                 SmallVectorImpl<LiveInterval*>&);
149};
150} // end anonymous namespace
151
152char RAGreedy::ID = 0;
153
154FunctionPass* llvm::createGreedyRegisterAllocator() {
155  return new RAGreedy();
156}
157
158RAGreedy::RAGreedy(): MachineFunctionPass(ID) {
159  initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
160  initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
161  initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
162  initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
163  initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
164  initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
165  initializeLiveStacksPass(*PassRegistry::getPassRegistry());
166  initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
167  initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
168  initializeMachineLoopRangesPass(*PassRegistry::getPassRegistry());
169  initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
170  initializeEdgeBundlesPass(*PassRegistry::getPassRegistry());
171  initializeSpillPlacementPass(*PassRegistry::getPassRegistry());
172}
173
174void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
175  AU.setPreservesCFG();
176  AU.addRequired<AliasAnalysis>();
177  AU.addPreserved<AliasAnalysis>();
178  AU.addRequired<LiveIntervals>();
179  AU.addRequired<SlotIndexes>();
180  AU.addPreserved<SlotIndexes>();
181  if (StrongPHIElim)
182    AU.addRequiredID(StrongPHIEliminationID);
183  AU.addRequiredTransitive<RegisterCoalescer>();
184  AU.addRequired<CalculateSpillWeights>();
185  AU.addRequired<LiveStacks>();
186  AU.addPreserved<LiveStacks>();
187  AU.addRequired<MachineDominatorTree>();
188  AU.addPreserved<MachineDominatorTree>();
189  AU.addRequired<MachineLoopInfo>();
190  AU.addPreserved<MachineLoopInfo>();
191  AU.addRequired<MachineLoopRanges>();
192  AU.addPreserved<MachineLoopRanges>();
193  AU.addRequired<VirtRegMap>();
194  AU.addPreserved<VirtRegMap>();
195  AU.addRequired<EdgeBundles>();
196  AU.addRequired<SpillPlacement>();
197  MachineFunctionPass::getAnalysisUsage(AU);
198}
199
200void RAGreedy::releaseMemory() {
201  SpillerInstance.reset(0);
202  RegAllocBase::releaseMemory();
203}
204
205float RAGreedy::getPriority(LiveInterval *LI) {
206  float Priority = LI->weight;
207
208  // Prioritize hinted registers so they are allocated first.
209  std::pair<unsigned, unsigned> Hint;
210  if (Hint.first || Hint.second) {
211    // The hint can be target specific, a virtual register, or a physreg.
212    Priority *= 2;
213
214    // Prefer physreg hints above anything else.
215    if (Hint.first == 0 && TargetRegisterInfo::isPhysicalRegister(Hint.second))
216      Priority *= 2;
217  }
218  return Priority;
219}
220
221
222//===----------------------------------------------------------------------===//
223//                         Register Reassignment
224//===----------------------------------------------------------------------===//
225
226// Check interference without using the cache.
227bool RAGreedy::checkUncachedInterference(LiveInterval &VirtReg,
228                                         unsigned PhysReg) {
229  for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
230    LiveIntervalUnion::Query subQ(&VirtReg, &PhysReg2LiveUnion[*AliasI]);
231    if (subQ.checkInterference())
232      return true;
233  }
234  return false;
235}
236
237/// getSingleInterference - Return the single interfering virtual register
238/// assigned to PhysReg. Return 0 if more than one virtual register is
239/// interfering.
240LiveInterval *RAGreedy::getSingleInterference(LiveInterval &VirtReg,
241                                              unsigned PhysReg) {
242  // Check physreg and aliases.
243  LiveInterval *Interference = 0;
244  for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
245    LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
246    if (Q.checkInterference()) {
247      if (Interference)
248        return 0;
249      Q.collectInterferingVRegs(1);
250      if (!Q.seenAllInterferences())
251        return 0;
252      Interference = Q.interferingVRegs().front();
253    }
254  }
255  return Interference;
256}
257
258// Attempt to reassign this virtual register to a different physical register.
259//
260// FIXME: we are not yet caching these "second-level" interferences discovered
261// in the sub-queries. These interferences can change with each call to
262// selectOrSplit. However, we could implement a "may-interfere" cache that
263// could be conservatively dirtied when we reassign or split.
264//
265// FIXME: This may result in a lot of alias queries. We could summarize alias
266// live intervals in their parent register's live union, but it's messy.
267bool RAGreedy::reassignVReg(LiveInterval &InterferingVReg,
268                            unsigned WantedPhysReg) {
269  assert(TargetRegisterInfo::isVirtualRegister(InterferingVReg.reg) &&
270         "Can only reassign virtual registers");
271  assert(TRI->regsOverlap(WantedPhysReg, VRM->getPhys(InterferingVReg.reg)) &&
272         "inconsistent phys reg assigment");
273
274  AllocationOrder Order(InterferingVReg.reg, *VRM, ReservedRegs);
275  while (unsigned PhysReg = Order.next()) {
276    // Don't reassign to a WantedPhysReg alias.
277    if (TRI->regsOverlap(PhysReg, WantedPhysReg))
278      continue;
279
280    if (checkUncachedInterference(InterferingVReg, PhysReg))
281      continue;
282
283    // Reassign the interfering virtual reg to this physical reg.
284    unsigned OldAssign = VRM->getPhys(InterferingVReg.reg);
285    DEBUG(dbgs() << "reassigning: " << InterferingVReg << " from " <<
286          TRI->getName(OldAssign) << " to " << TRI->getName(PhysReg) << '\n');
287    PhysReg2LiveUnion[OldAssign].extract(InterferingVReg);
288    VRM->clearVirt(InterferingVReg.reg);
289    VRM->assignVirt2Phys(InterferingVReg.reg, PhysReg);
290    PhysReg2LiveUnion[PhysReg].unify(InterferingVReg);
291
292    return true;
293  }
294  return false;
295}
296
297/// reassignInterferences - Reassign all interferences to different physical
298/// registers such that Virtreg can be assigned to PhysReg.
299/// Currently this only works with a single interference.
300/// @param  VirtReg Currently unassigned virtual register.
301/// @param  PhysReg Physical register to be cleared.
302/// @return True on success, false if nothing was changed.
303bool RAGreedy::reassignInterferences(LiveInterval &VirtReg, unsigned PhysReg) {
304  LiveInterval *InterferingVReg = getSingleInterference(VirtReg, PhysReg);
305  if (!InterferingVReg)
306    return false;
307  if (TargetRegisterInfo::isPhysicalRegister(InterferingVReg->reg))
308    return false;
309  return reassignVReg(*InterferingVReg, PhysReg);
310}
311
312/// tryReassign - Try to reassign interferences to different physregs.
313/// @param  VirtReg Currently unassigned virtual register.
314/// @param  Order   Physregs to try.
315/// @return         Physreg to assign VirtReg, or 0.
316unsigned RAGreedy::tryReassign(LiveInterval &VirtReg, AllocationOrder &Order) {
317  NamedRegionTimer T("Reassign", TimerGroupName, TimePassesIsEnabled);
318  Order.rewind();
319  while (unsigned PhysReg = Order.next())
320    if (reassignInterferences(VirtReg, PhysReg))
321      return PhysReg;
322  return 0;
323}
324
325
326//===----------------------------------------------------------------------===//
327//                              Region Splitting
328//===----------------------------------------------------------------------===//
329
330/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
331/// where VirtReg is live.
332/// The SpillConstraints array is minimally initialized with MBB->getNumber().
333void RAGreedy::calcLiveBlockInfo(LiveInterval &VirtReg) {
334  LiveBlocks.clear();
335  SpillConstraints.clear();
336
337  assert(!VirtReg.empty() && "Cannot allocate an empty interval");
338  LiveInterval::const_iterator LVI = VirtReg.begin();
339  LiveInterval::const_iterator LVE = VirtReg.end();
340
341  SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE;
342  UseI = SA->UseSlots.begin();
343  UseE = SA->UseSlots.end();
344
345  // Loop over basic blocks where VirtReg is live.
346  MachineFunction::iterator MFI = Indexes->getMBBFromIndex(LVI->start);
347  for (;;) {
348    // Block constraints depend on the interference pattern.
349    // Just allocate them here, don't compute anything.
350    SpillPlacement::BlockConstraint BC;
351    BC.Number = MFI->getNumber();
352    SpillConstraints.push_back(BC);
353
354    BlockInfo BI;
355    BI.MBB = MFI;
356    SlotIndex Start, Stop;
357    tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
358
359    // LVI is the first live segment overlapping MBB.
360    BI.LiveIn = LVI->start <= Start;
361    if (!BI.LiveIn)
362      BI.Def = LVI->start;
363
364    // Find the first and last uses in the block.
365    BI.Uses = SA->hasUses(MFI);
366    if (BI.Uses && UseI != UseE) {
367      BI.FirstUse = *UseI;
368      assert(BI.FirstUse >= Start);
369      do ++UseI;
370      while (UseI != UseE && *UseI < Stop);
371      BI.LastUse = UseI[-1];
372      assert(BI.LastUse < Stop);
373    }
374
375    // Look for gaps in the live range.
376    bool hasGap = false;
377    BI.LiveOut = true;
378    while (LVI->end < Stop) {
379      SlotIndex LastStop = LVI->end;
380      if (++LVI == LVE || LVI->start >= Stop) {
381        BI.Kill = LastStop;
382        BI.LiveOut = false;
383        break;
384      }
385      if (LastStop < LVI->start) {
386        hasGap = true;
387        BI.Kill = LastStop;
388        BI.Def = LVI->start;
389      }
390    }
391
392    // Don't set LiveThrough when the block has a gap.
393    BI.LiveThrough = !hasGap && BI.LiveIn && BI.LiveOut;
394    LiveBlocks.push_back(BI);
395
396    // LVI is now at LVE or LVI->end >= Stop.
397    if (LVI == LVE)
398      break;
399
400    // Live segment ends exactly at Stop. Move to the next segment.
401    if (LVI->end == Stop && ++LVI == LVE)
402      break;
403
404    // Pick the next basic block.
405    if (LVI->start < Stop)
406      ++MFI;
407    else
408      MFI = Indexes->getMBBFromIndex(LVI->start);
409  }
410}
411
412/// calcInterferenceInfo - Compute per-block outgoing and ingoing constraints
413/// when considering interference from PhysReg. Also compute an optimistic local
414/// cost of this interference pattern.
415///
416/// The final cost of a split is the local cost + global cost of preferences
417/// broken by SpillPlacement.
418///
419float RAGreedy::calcInterferenceInfo(LiveInterval &VirtReg, unsigned PhysReg) {
420  // Reset interference dependent info.
421  for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
422    BlockInfo &BI = LiveBlocks[i];
423    SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
424    BC.Entry = (BI.Uses && BI.LiveIn) ?
425      SpillPlacement::PrefReg : SpillPlacement::DontCare;
426    BC.Exit = (BI.Uses && BI.LiveOut) ?
427      SpillPlacement::PrefReg : SpillPlacement::DontCare;
428    BI.OverlapEntry = BI.OverlapExit = false;
429  }
430
431  // Add interference info from each PhysReg alias.
432  for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
433    if (!query(VirtReg, *AI).checkInterference())
434      continue;
435    DEBUG(PhysReg2LiveUnion[*AI].print(dbgs(), TRI));
436    LiveIntervalUnion::SegmentIter IntI =
437      PhysReg2LiveUnion[*AI].find(VirtReg.beginIndex());
438    if (!IntI.valid())
439      continue;
440
441    for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
442      BlockInfo &BI = LiveBlocks[i];
443      SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
444      SlotIndex Start, Stop;
445      tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
446
447      // Skip interference-free blocks.
448      if (IntI.start() >= Stop)
449        continue;
450
451      // Handle transparent blocks with interference separately.
452      // Transparent blocks never incur any fixed cost.
453      if (BI.LiveThrough && !BI.Uses) {
454        // Check if interference is live-in - force spill.
455        if (BC.Entry != SpillPlacement::MustSpill) {
456          BC.Entry = SpillPlacement::PrefSpill;
457          IntI.advanceTo(Start);
458          if (IntI.valid() && IntI.start() <= Start)
459            BC.Entry = SpillPlacement::MustSpill;
460        }
461
462        // Check if interference is live-out - force spill.
463        if (BC.Exit != SpillPlacement::MustSpill) {
464          BC.Exit = SpillPlacement::PrefSpill;
465          IntI.advanceTo(Stop);
466          if (IntI.valid() && IntI.start() < Stop)
467            BC.Exit = SpillPlacement::MustSpill;
468        }
469
470        // Nothing more to do for this transparent block.
471        if (!IntI.valid())
472          break;
473        continue;
474      }
475
476      // Now we only have blocks with uses left.
477      // Check if the interference overlaps the uses.
478      assert(BI.Uses && "Non-transparent block without any uses");
479
480      // Check interference on entry.
481      if (BI.LiveIn && BC.Entry != SpillPlacement::MustSpill) {
482        IntI.advanceTo(Start);
483        if (!IntI.valid())
484          break;
485
486        // Interference is live-in - force spill.
487        if (IntI.start() <= Start)
488          BC.Entry = SpillPlacement::MustSpill;
489        // Not live in, but before the first use.
490        else if (IntI.start() < BI.FirstUse)
491          BC.Entry = SpillPlacement::PrefSpill;
492      }
493
494      // Does interference overlap the uses in the entry segment
495      // [FirstUse;Kill)?
496      if (BI.LiveIn && !BI.OverlapEntry) {
497        IntI.advanceTo(BI.FirstUse);
498        if (!IntI.valid())
499          break;
500        // A live-through interval has no kill.
501        // Check [FirstUse;LastUse) instead.
502        if (IntI.start() < (BI.LiveThrough ? BI.LastUse : BI.Kill))
503          BI.OverlapEntry = true;
504      }
505
506      // Does interference overlap the uses in the exit segment [Def;LastUse)?
507      if (BI.LiveOut && !BI.LiveThrough && !BI.OverlapExit) {
508        IntI.advanceTo(BI.Def);
509        if (!IntI.valid())
510          break;
511        if (IntI.start() < BI.LastUse)
512          BI.OverlapExit = true;
513      }
514
515      // Check interference on exit.
516      if (BI.LiveOut && BC.Exit != SpillPlacement::MustSpill) {
517        // Check interference between LastUse and Stop.
518        if (BC.Exit != SpillPlacement::PrefSpill) {
519          IntI.advanceTo(BI.LastUse);
520          if (!IntI.valid())
521            break;
522          if (IntI.start() < Stop)
523            BC.Exit = SpillPlacement::PrefSpill;
524        }
525        // Is the interference live-out?
526        IntI.advanceTo(Stop);
527        if (!IntI.valid())
528          break;
529        if (IntI.start() < Stop)
530          BC.Exit = SpillPlacement::MustSpill;
531      }
532    }
533  }
534
535  // Accumulate a local cost of this interference pattern.
536  float LocalCost = 0;
537  for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
538    BlockInfo &BI = LiveBlocks[i];
539    if (!BI.Uses)
540      continue;
541    SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
542    unsigned Inserts = 0;
543
544    // Do we need spill code for the entry segment?
545    if (BI.LiveIn)
546      Inserts += BI.OverlapEntry || BC.Entry != SpillPlacement::PrefReg;
547
548    // For the exit segment?
549    if (BI.LiveOut)
550      Inserts += BI.OverlapExit || BC.Exit != SpillPlacement::PrefReg;
551
552    // The local cost of spill code in this block is the block frequency times
553    // the number of spill instructions inserted.
554    if (Inserts)
555      LocalCost += Inserts * SpillPlacer->getBlockFrequency(BI.MBB);
556  }
557  DEBUG(dbgs() << "Local cost of " << PrintReg(PhysReg, TRI) << " = "
558               << LocalCost << '\n');
559  return LocalCost;
560}
561
562/// calcGlobalSplitCost - Return the global split cost of following the split
563/// pattern in LiveBundles. This cost should be added to the local cost of the
564/// interference pattern in SpillConstraints.
565///
566float RAGreedy::calcGlobalSplitCost(const BitVector &LiveBundles) {
567  float GlobalCost = 0;
568  for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
569    SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
570    unsigned Inserts = 0;
571    // Broken entry preference?
572    Inserts += LiveBundles[Bundles->getBundle(BC.Number, 0)] !=
573                 (BC.Entry == SpillPlacement::PrefReg);
574    // Broken exit preference?
575    Inserts += LiveBundles[Bundles->getBundle(BC.Number, 1)] !=
576                 (BC.Exit == SpillPlacement::PrefReg);
577    if (Inserts)
578      GlobalCost += Inserts * SpillPlacer->getBlockFrequency(LiveBlocks[i].MBB);
579  }
580  DEBUG(dbgs() << "Global cost = " << GlobalCost << '\n');
581  return GlobalCost;
582}
583
584/// splitAroundRegion - Split VirtReg around the region determined by
585/// LiveBundles. Make an effort to avoid interference from PhysReg.
586///
587/// The 'register' interval is going to contain as many uses as possible while
588/// avoiding interference. The 'stack' interval is the complement constructed by
589/// SplitEditor. It will contain the rest.
590///
591void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
592                                 const BitVector &LiveBundles,
593                                 SmallVectorImpl<LiveInterval*> &NewVRegs) {
594  DEBUG({
595    dbgs() << "Splitting around region for " << PrintReg(PhysReg, TRI)
596           << " with bundles";
597    for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i))
598      dbgs() << " EB#" << i;
599    dbgs() << ".\n";
600  });
601
602  // First compute interference ranges in the live blocks.
603  typedef std::pair<SlotIndex, SlotIndex> IndexPair;
604  SmallVector<IndexPair, 8> InterferenceRanges;
605  InterferenceRanges.resize(LiveBlocks.size());
606  for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
607    if (!query(VirtReg, *AI).checkInterference())
608      continue;
609    LiveIntervalUnion::SegmentIter IntI =
610      PhysReg2LiveUnion[*AI].find(VirtReg.beginIndex());
611    if (!IntI.valid())
612      continue;
613    for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
614      BlockInfo &BI = LiveBlocks[i];
615      if (!BI.Uses)
616        continue;
617      IndexPair &IP = InterferenceRanges[i];
618      SlotIndex Start, Stop;
619      tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
620      // Skip interference-free blocks.
621      if (IntI.start() >= Stop)
622        continue;
623
624      // First interference in block.
625      if (BI.LiveIn) {
626        IntI.advanceTo(Start);
627        if (!IntI.valid())
628          break;
629        if (IntI.start() >= Stop)
630          continue;
631        if (!IP.first.isValid() || IntI.start() < IP.first)
632          IP.first = IntI.start();
633      }
634
635      // Last interference in block.
636      if (BI.LiveOut) {
637        IntI.advanceTo(Stop);
638        if (!IntI.valid() || IntI.start() >= Stop)
639          --IntI;
640        if (IntI.stop() <= Start)
641          continue;
642        if (!IP.second.isValid() || IntI.stop() > IP.second)
643          IP.second = IntI.stop();
644      }
645    }
646  }
647
648  SmallVector<LiveInterval*, 4> SpillRegs;
649  LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs);
650  SplitEditor SE(*SA, *LIS, *VRM, *DomTree, LREdit);
651
652  // Create the main cross-block interval.
653  SE.openIntv();
654
655  // First add all defs that are live out of a block.
656  for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
657    BlockInfo &BI = LiveBlocks[i];
658    bool RegIn  = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
659    bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
660
661    // Should the register be live out?
662    if (!BI.LiveOut || !RegOut)
663      continue;
664
665    IndexPair &IP = InterferenceRanges[i];
666    SlotIndex Start, Stop;
667    tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
668
669    DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#"
670                 << Bundles->getBundle(BI.MBB->getNumber(), 1)
671                 << " intf [" << IP.first << ';' << IP.second << ')');
672
673    // The interference interval should either be invalid or overlap MBB.
674    assert((!IP.first.isValid() || IP.first < Stop) && "Bad interference");
675    assert((!IP.second.isValid() || IP.second > Start) && "Bad interference");
676
677    // Check interference leaving the block.
678    if (!IP.second.isValid()) {
679      // Block is interference-free.
680      DEBUG(dbgs() << ", no interference");
681      if (!BI.Uses) {
682        assert(BI.LiveThrough && "No uses, but not live through block?");
683        // Block is live-through without interference.
684        DEBUG(dbgs() << ", no uses"
685                     << (RegIn ? ", live-through.\n" : ", stack in.\n"));
686        if (!RegIn)
687          SE.enterIntvAtEnd(*BI.MBB);
688        continue;
689      }
690      if (!BI.LiveThrough) {
691        DEBUG(dbgs() << ", not live-through.\n");
692        SE.useIntv(SE.enterIntvBefore(BI.Def), Stop);
693        continue;
694      }
695      if (!RegIn) {
696        // Block is live-through, but entry bundle is on the stack.
697        // Reload just before the first use.
698        DEBUG(dbgs() << ", not live-in, enter before first use.\n");
699        SE.useIntv(SE.enterIntvBefore(BI.FirstUse), Stop);
700        continue;
701      }
702      DEBUG(dbgs() << ", live-through.\n");
703      continue;
704    }
705
706    // Block has interference.
707    DEBUG(dbgs() << ", interference to " << IP.second);
708    if (!BI.Uses) {
709      // No uses in block, avoid interference by reloading as late as possible.
710      DEBUG(dbgs() << ", no uses.\n");
711      SE.enterIntvAtEnd(*BI.MBB);
712      continue;
713    }
714    if (IP.second < BI.LastUse) {
715      // There are interference-free uses at the end of the block.
716      // Find the first use that can get the live-out register.
717      SmallVectorImpl<SlotIndex>::const_iterator UI =
718        std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), IP.second);
719      assert(UI != SA->UseSlots.end() && "Couldn't find last use");
720      SlotIndex Use = *UI;
721      DEBUG(dbgs() << ", free use at " << Use << ".\n");
722      assert(Use <= BI.LastUse && "Couldn't find last use");
723      SE.useIntv(SE.enterIntvBefore(Use), Stop);
724      continue;
725    }
726
727    // Interference is after the last use.
728    DEBUG(dbgs() << " after last use.\n");
729    SE.enterIntvAtEnd(*BI.MBB);
730  }
731
732  // Now all defs leading to live bundles are handled, do everything else.
733  for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
734    BlockInfo &BI = LiveBlocks[i];
735    bool RegIn  = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
736    bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
737
738    // Is the register live-in?
739    if (!BI.LiveIn || !RegIn)
740      continue;
741
742    // We have an incoming register. Check for interference.
743    IndexPair &IP = InterferenceRanges[i];
744    SlotIndex Start, Stop;
745    tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
746
747    DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0)
748                 << " -> BB#" << BI.MBB->getNumber());
749
750    // Check interference entering the block.
751    if (!IP.first.isValid()) {
752      // Block is interference-free.
753      DEBUG(dbgs() << ", no interference");
754      if (!BI.Uses) {
755        assert(BI.LiveThrough && "No uses, but not live through block?");
756        // Block is live-through without interference.
757        if (RegOut) {
758          DEBUG(dbgs() << ", no uses, live-through.\n");
759          SE.useIntv(Start, Stop);
760        } else {
761          DEBUG(dbgs() << ", no uses, stack-out.\n");
762          SE.leaveIntvAtTop(*BI.MBB);
763        }
764        continue;
765      }
766      if (!BI.LiveThrough) {
767        DEBUG(dbgs() << ", killed in block.\n");
768        SE.useIntv(Start, SE.leaveIntvAfter(BI.Kill));
769        continue;
770      }
771      if (!RegOut) {
772        // Block is live-through, but exit bundle is on the stack.
773        // Spill immediately after the last use.
774        DEBUG(dbgs() << ", uses, stack-out.\n");
775        SE.useIntv(Start, SE.leaveIntvAfter(BI.LastUse));
776        continue;
777      }
778      // Register is live-through.
779      DEBUG(dbgs() << ", uses, live-through.\n");
780      SE.useIntv(Start, Stop);
781      continue;
782    }
783
784    // Block has interference.
785    DEBUG(dbgs() << ", interference from " << IP.first);
786    if (!BI.Uses) {
787      // No uses in block, avoid interference by spilling as soon as possible.
788      DEBUG(dbgs() << ", no uses.\n");
789      SE.leaveIntvAtTop(*BI.MBB);
790      continue;
791    }
792    if (IP.first > BI.FirstUse) {
793      // There are interference-free uses at the beginning of the block.
794      // Find the last use that can get the register.
795      SmallVectorImpl<SlotIndex>::const_iterator UI =
796        std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(), IP.first);
797      assert(UI != SA->UseSlots.begin() && "Couldn't find first use");
798      SlotIndex Use = (--UI)->getBoundaryIndex();
799      DEBUG(dbgs() << ", free use at " << *UI << ".\n");
800      assert(Use >= BI.FirstUse && Use < IP.first);
801      SE.useIntv(Start, SE.leaveIntvAfter(Use));
802      continue;
803    }
804
805    // Interference is before the first use.
806    DEBUG(dbgs() << " before first use.\n");
807    SE.leaveIntvAtTop(*BI.MBB);
808  }
809
810  SE.closeIntv();
811
812  // FIXME: Should we be more aggressive about splitting the stack region into
813  // per-block segments? The current approach allows the stack region to
814  // separate into connected components. Some components may be allocatable.
815  SE.finish();
816
817  if (VerifyEnabled)
818    MF->verify(this, "After splitting live range around region");
819}
820
821unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
822                                  SmallVectorImpl<LiveInterval*> &NewVRegs) {
823  calcLiveBlockInfo(VirtReg);
824  BitVector LiveBundles, BestBundles;
825  float BestCost = 0;
826  unsigned BestReg = 0;
827  Order.rewind();
828  while (unsigned PhysReg = Order.next()) {
829    float Cost = calcInterferenceInfo(VirtReg, PhysReg);
830    if (BestReg && Cost >= BestCost)
831      continue;
832
833    SpillPlacer->placeSpills(SpillConstraints, LiveBundles);
834    // No live bundles, defer to splitSingleBlocks().
835    if (!LiveBundles.any())
836      continue;
837
838    Cost += calcGlobalSplitCost(LiveBundles);
839    if (!BestReg || Cost < BestCost) {
840      BestReg = PhysReg;
841      BestCost = Cost;
842      BestBundles.swap(LiveBundles);
843    }
844  }
845
846  if (!BestReg)
847    return 0;
848
849  splitAroundRegion(VirtReg, BestReg, BestBundles, NewVRegs);
850  return 0;
851}
852
853
854//===----------------------------------------------------------------------===//
855//                          Live Range Splitting
856//===----------------------------------------------------------------------===//
857
858/// trySplit - Try to split VirtReg or one of its interferences, making it
859/// assignable.
860/// @return Physreg when VirtReg may be assigned and/or new NewVRegs.
861unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
862                            SmallVectorImpl<LiveInterval*>&NewVRegs) {
863  NamedRegionTimer T("Splitter", TimerGroupName, TimePassesIsEnabled);
864  SA->analyze(&VirtReg);
865
866  // Don't attempt splitting on local intervals for now. TBD.
867  if (LIS->intervalIsInOneMBB(VirtReg))
868    return 0;
869
870  // First try to split around a region spanning multiple blocks.
871  unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
872  if (PhysReg || !NewVRegs.empty())
873    return PhysReg;
874
875  // Then isolate blocks with multiple uses.
876  SplitAnalysis::BlockPtrSet Blocks;
877  if (SA->getMultiUseBlocks(Blocks)) {
878    SmallVector<LiveInterval*, 4> SpillRegs;
879    LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs);
880    SplitEditor(*SA, *LIS, *VRM, *DomTree, LREdit).splitSingleBlocks(Blocks);
881    if (VerifyEnabled)
882      MF->verify(this, "After splitting live range around basic blocks");
883  }
884
885  // Don't assign any physregs.
886  return 0;
887}
888
889
890//===----------------------------------------------------------------------===//
891//                                Spilling
892//===----------------------------------------------------------------------===//
893
894/// calcInterferenceWeight - Calculate the combined spill weight of
895/// interferences when assigning VirtReg to PhysReg.
896float RAGreedy::calcInterferenceWeight(LiveInterval &VirtReg, unsigned PhysReg){
897  float Sum = 0;
898  for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
899    LiveIntervalUnion::Query &Q = query(VirtReg, *AI);
900    Q.collectInterferingVRegs();
901    if (Q.seenUnspillableVReg())
902      return HUGE_VALF;
903    for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i)
904      Sum += Q.interferingVRegs()[i]->weight;
905  }
906  return Sum;
907}
908
909/// trySpillInterferences - Try to spill interfering registers instead of the
910/// current one. Only do it if the accumulated spill weight is smaller than the
911/// current spill weight.
912unsigned RAGreedy::trySpillInterferences(LiveInterval &VirtReg,
913                                         AllocationOrder &Order,
914                                     SmallVectorImpl<LiveInterval*> &NewVRegs) {
915  NamedRegionTimer T("Spill Interference", TimerGroupName, TimePassesIsEnabled);
916  unsigned BestPhys = 0;
917  float BestWeight = 0;
918
919  Order.rewind();
920  while (unsigned PhysReg = Order.next()) {
921    float Weight = calcInterferenceWeight(VirtReg, PhysReg);
922    if (Weight == HUGE_VALF || Weight >= VirtReg.weight)
923      continue;
924    if (!BestPhys || Weight < BestWeight)
925      BestPhys = PhysReg, BestWeight = Weight;
926  }
927
928  // No candidates found.
929  if (!BestPhys)
930    return 0;
931
932  // Collect all interfering registers.
933  SmallVector<LiveInterval*, 8> Spills;
934  for (const unsigned *AI = TRI->getOverlaps(BestPhys); *AI; ++AI) {
935    LiveIntervalUnion::Query &Q = query(VirtReg, *AI);
936    Spills.append(Q.interferingVRegs().begin(), Q.interferingVRegs().end());
937    for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) {
938      LiveInterval *VReg = Q.interferingVRegs()[i];
939      PhysReg2LiveUnion[*AI].extract(*VReg);
940      VRM->clearVirt(VReg->reg);
941    }
942  }
943
944  // Spill them all.
945  DEBUG(dbgs() << "spilling " << Spills.size() << " interferences with weight "
946               << BestWeight << '\n');
947  for (unsigned i = 0, e = Spills.size(); i != e; ++i)
948    spiller().spill(Spills[i], NewVRegs, Spills);
949  return BestPhys;
950}
951
952
953//===----------------------------------------------------------------------===//
954//                            Main Entry Point
955//===----------------------------------------------------------------------===//
956
957unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
958                                 SmallVectorImpl<LiveInterval*> &NewVRegs) {
959  // First try assigning a free register.
960  AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs);
961  while (unsigned PhysReg = Order.next()) {
962    if (!checkPhysRegInterference(VirtReg, PhysReg))
963      return PhysReg;
964  }
965
966  // Try to reassign interferences.
967  if (unsigned PhysReg = tryReassign(VirtReg, Order))
968    return PhysReg;
969
970  assert(NewVRegs.empty() && "Cannot append to existing NewVRegs");
971
972  // Try splitting VirtReg or interferences.
973  unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs);
974  if (PhysReg || !NewVRegs.empty())
975    return PhysReg;
976
977  // Try to spill another interfering reg with less spill weight.
978  PhysReg = trySpillInterferences(VirtReg, Order, NewVRegs);
979  if (PhysReg)
980    return PhysReg;
981
982  // Finally spill VirtReg itself.
983  NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled);
984  SmallVector<LiveInterval*, 1> pendingSpills;
985  spiller().spill(&VirtReg, NewVRegs, pendingSpills);
986
987  // The live virtual register requesting allocation was spilled, so tell
988  // the caller not to allocate anything during this round.
989  return 0;
990}
991
992bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
993  DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
994               << "********** Function: "
995               << ((Value*)mf.getFunction())->getName() << '\n');
996
997  MF = &mf;
998  if (VerifyEnabled)
999    MF->verify(this, "Before greedy register allocator");
1000
1001  RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>());
1002  Indexes = &getAnalysis<SlotIndexes>();
1003  DomTree = &getAnalysis<MachineDominatorTree>();
1004  ReservedRegs = TRI->getReservedRegs(*MF);
1005  SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
1006  Loops = &getAnalysis<MachineLoopInfo>();
1007  LoopRanges = &getAnalysis<MachineLoopRanges>();
1008  Bundles = &getAnalysis<EdgeBundles>();
1009  SpillPlacer = &getAnalysis<SpillPlacement>();
1010
1011  SA.reset(new SplitAnalysis(*MF, *LIS, *Loops));
1012
1013  allocatePhysRegs();
1014  addMBBLiveIns(MF);
1015
1016  // Run rewriter
1017  {
1018    NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled);
1019    std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
1020    rewriter->runOnMachineFunction(*MF, *VRM, LIS);
1021  }
1022
1023  // The pass output is in VirtRegMap. Release all the transient data.
1024  releaseMemory();
1025
1026  return true;
1027}
1028