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