RegAllocGreedy.cpp revision bece06f0c6936527e2b1c72d09f7d3a949af9a47 
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 "llvm/ADT/Statistic.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
46#include <queue>
47
48using namespace llvm;
49
50STATISTIC(NumGlobalSplits, "Number of split global live ranges");
51STATISTIC(NumLocalSplits,  "Number of split local live ranges");
52STATISTIC(NumReassigned,   "Number of interferences reassigned");
53STATISTIC(NumEvicted,      "Number of interferences evicted");
54
55static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator",
56                                       createGreedyRegisterAllocator);
57
58namespace {
59class RAGreedy : public MachineFunctionPass, public RegAllocBase {
60  // context
61  MachineFunction *MF;
62  BitVector ReservedRegs;
63
64  // analyses
65  SlotIndexes *Indexes;
66  LiveStacks *LS;
67  MachineDominatorTree *DomTree;
68  MachineLoopInfo *Loops;
69  MachineLoopRanges *LoopRanges;
70  EdgeBundles *Bundles;
71  SpillPlacement *SpillPlacer;
72
73  // state
74  std::auto_ptr<Spiller> SpillerInstance;
75  std::priority_queue<std::pair<unsigned, unsigned> > Queue;
76
77  // Live ranges pass through a number of stages as we try to allocate them.
78  // Some of the stages may also create new live ranges:
79  //
80  // - Region splitting.
81  // - Per-block splitting.
82  // - Local splitting.
83  // - Spilling.
84  //
85  // Ranges produced by one of the stages skip the previous stages when they are
86  // dequeued. This improves performance because we can skip interference checks
87  // that are unlikely to give any results. It also guarantees that the live
88  // range splitting algorithm terminates, something that is otherwise hard to
89  // ensure.
90  enum LiveRangeStage {
91    RS_Original, ///< Never seen before, never split.
92    RS_Second,   ///< Second time in the queue.
93    RS_Region,   ///< Produced by region splitting.
94    RS_Block,    ///< Produced by per-block splitting.
95    RS_Local,    ///< Produced by local splitting.
96    RS_Spill     ///< Produced by spilling.
97  };
98
99  IndexedMap<unsigned char, VirtReg2IndexFunctor> LRStage;
100
101  LiveRangeStage getStage(const LiveInterval &VirtReg) const {
102    return LiveRangeStage(LRStage[VirtReg.reg]);
103  }
104
105  template<typename Iterator>
106  void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) {
107    LRStage.resize(MRI->getNumVirtRegs());
108    for (;Begin != End; ++Begin)
109      LRStage[(*Begin)->reg] = NewStage;
110  }
111
112  // splitting state.
113  std::auto_ptr<SplitAnalysis> SA;
114  std::auto_ptr<SplitEditor> SE;
115
116  /// All basic blocks where the current register is live.
117  SmallVector<SpillPlacement::BlockConstraint, 8> SpillConstraints;
118
119  /// For every instruction in SA->UseSlots, store the previous non-copy
120  /// instruction.
121  SmallVector<SlotIndex, 8> PrevSlot;
122
123public:
124  RAGreedy();
125
126  /// Return the pass name.
127  virtual const char* getPassName() const {
128    return "Greedy Register Allocator";
129  }
130
131  /// RAGreedy analysis usage.
132  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
133  virtual void releaseMemory();
134  virtual Spiller &spiller() { return *SpillerInstance; }
135  virtual void enqueue(LiveInterval *LI);
136  virtual LiveInterval *dequeue();
137  virtual unsigned selectOrSplit(LiveInterval&,
138                                 SmallVectorImpl<LiveInterval*>&);
139
140  /// Perform register allocation.
141  virtual bool runOnMachineFunction(MachineFunction &mf);
142
143  static char ID;
144
145private:
146  bool checkUncachedInterference(LiveInterval&, unsigned);
147  LiveInterval *getSingleInterference(LiveInterval&, unsigned);
148  bool reassignVReg(LiveInterval &InterferingVReg, unsigned OldPhysReg);
149  float calcInterferenceInfo(LiveInterval&, unsigned);
150  float calcGlobalSplitCost(const BitVector&);
151  void splitAroundRegion(LiveInterval&, unsigned, const BitVector&,
152                         SmallVectorImpl<LiveInterval*>&);
153  void calcGapWeights(unsigned, SmallVectorImpl<float>&);
154  SlotIndex getPrevMappedIndex(const MachineInstr*);
155  void calcPrevSlots();
156  unsigned nextSplitPoint(unsigned);
157  bool canEvictInterference(LiveInterval&, unsigned, unsigned, float&);
158
159  unsigned tryReassign(LiveInterval&, AllocationOrder&,
160                              SmallVectorImpl<LiveInterval*>&);
161  unsigned tryEvict(LiveInterval&, AllocationOrder&,
162                    SmallVectorImpl<LiveInterval*>&);
163  unsigned tryRegionSplit(LiveInterval&, AllocationOrder&,
164                          SmallVectorImpl<LiveInterval*>&);
165  unsigned tryLocalSplit(LiveInterval&, AllocationOrder&,
166    SmallVectorImpl<LiveInterval*>&);
167  unsigned trySplit(LiveInterval&, AllocationOrder&,
168                    SmallVectorImpl<LiveInterval*>&);
169};
170} // end anonymous namespace
171
172char RAGreedy::ID = 0;
173
174FunctionPass* llvm::createGreedyRegisterAllocator() {
175  return new RAGreedy();
176}
177
178RAGreedy::RAGreedy(): MachineFunctionPass(ID), LRStage(RS_Original) {
179  initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
180  initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
181  initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
182  initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
183  initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
184  initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
185  initializeLiveStacksPass(*PassRegistry::getPassRegistry());
186  initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
187  initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
188  initializeMachineLoopRangesPass(*PassRegistry::getPassRegistry());
189  initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
190  initializeEdgeBundlesPass(*PassRegistry::getPassRegistry());
191  initializeSpillPlacementPass(*PassRegistry::getPassRegistry());
192}
193
194void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
195  AU.setPreservesCFG();
196  AU.addRequired<AliasAnalysis>();
197  AU.addPreserved<AliasAnalysis>();
198  AU.addRequired<LiveIntervals>();
199  AU.addRequired<SlotIndexes>();
200  AU.addPreserved<SlotIndexes>();
201  if (StrongPHIElim)
202    AU.addRequiredID(StrongPHIEliminationID);
203  AU.addRequiredTransitive<RegisterCoalescer>();
204  AU.addRequired<CalculateSpillWeights>();
205  AU.addRequired<LiveStacks>();
206  AU.addPreserved<LiveStacks>();
207  AU.addRequired<MachineDominatorTree>();
208  AU.addPreserved<MachineDominatorTree>();
209  AU.addRequired<MachineLoopInfo>();
210  AU.addPreserved<MachineLoopInfo>();
211  AU.addRequired<MachineLoopRanges>();
212  AU.addPreserved<MachineLoopRanges>();
213  AU.addRequired<VirtRegMap>();
214  AU.addPreserved<VirtRegMap>();
215  AU.addRequired<EdgeBundles>();
216  AU.addRequired<SpillPlacement>();
217  MachineFunctionPass::getAnalysisUsage(AU);
218}
219
220void RAGreedy::releaseMemory() {
221  SpillerInstance.reset(0);
222  LRStage.clear();
223  RegAllocBase::releaseMemory();
224}
225
226void RAGreedy::enqueue(LiveInterval *LI) {
227  // Prioritize live ranges by size, assigning larger ranges first.
228  // The queue holds (size, reg) pairs.
229  const unsigned Size = LI->getSize();
230  const unsigned Reg = LI->reg;
231  assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
232         "Can only enqueue virtual registers");
233  unsigned Prio;
234
235  LRStage.grow(Reg);
236  if (LRStage[Reg] == RS_Original)
237    // 1st generation ranges are handled first, long -> short.
238    Prio = (1u << 31) + Size;
239  else
240    // Repeat offenders are handled second, short -> long
241    Prio = (1u << 30) - Size;
242
243  // Boost ranges that have a physical register hint.
244  const unsigned Hint = VRM->getRegAllocPref(Reg);
245  if (TargetRegisterInfo::isPhysicalRegister(Hint))
246    Prio |= (1u << 30);
247
248  Queue.push(std::make_pair(Prio, Reg));
249}
250
251LiveInterval *RAGreedy::dequeue() {
252  if (Queue.empty())
253    return 0;
254  LiveInterval *LI = &LIS->getInterval(Queue.top().second);
255  Queue.pop();
256  return LI;
257}
258
259//===----------------------------------------------------------------------===//
260//                         Register Reassignment
261//===----------------------------------------------------------------------===//
262
263// Check interference without using the cache.
264bool RAGreedy::checkUncachedInterference(LiveInterval &VirtReg,
265                                         unsigned PhysReg) {
266  for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
267    LiveIntervalUnion::Query subQ(&VirtReg, &PhysReg2LiveUnion[*AliasI]);
268    if (subQ.checkInterference())
269      return true;
270  }
271  return false;
272}
273
274/// getSingleInterference - Return the single interfering virtual register
275/// assigned to PhysReg. Return 0 if more than one virtual register is
276/// interfering.
277LiveInterval *RAGreedy::getSingleInterference(LiveInterval &VirtReg,
278                                              unsigned PhysReg) {
279  // Check physreg and aliases.
280  LiveInterval *Interference = 0;
281  for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
282    LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
283    if (Q.checkInterference()) {
284      if (Interference)
285        return 0;
286      if (Q.collectInterferingVRegs(2) > 1)
287        return 0;
288      Interference = Q.interferingVRegs().front();
289    }
290  }
291  return Interference;
292}
293
294// Attempt to reassign this virtual register to a different physical register.
295//
296// FIXME: we are not yet caching these "second-level" interferences discovered
297// in the sub-queries. These interferences can change with each call to
298// selectOrSplit. However, we could implement a "may-interfere" cache that
299// could be conservatively dirtied when we reassign or split.
300//
301// FIXME: This may result in a lot of alias queries. We could summarize alias
302// live intervals in their parent register's live union, but it's messy.
303bool RAGreedy::reassignVReg(LiveInterval &InterferingVReg,
304                            unsigned WantedPhysReg) {
305  assert(TargetRegisterInfo::isVirtualRegister(InterferingVReg.reg) &&
306         "Can only reassign virtual registers");
307  assert(TRI->regsOverlap(WantedPhysReg, VRM->getPhys(InterferingVReg.reg)) &&
308         "inconsistent phys reg assigment");
309
310  AllocationOrder Order(InterferingVReg.reg, *VRM, ReservedRegs);
311  while (unsigned PhysReg = Order.next()) {
312    // Don't reassign to a WantedPhysReg alias.
313    if (TRI->regsOverlap(PhysReg, WantedPhysReg))
314      continue;
315
316    if (checkUncachedInterference(InterferingVReg, PhysReg))
317      continue;
318
319    // Reassign the interfering virtual reg to this physical reg.
320    unsigned OldAssign = VRM->getPhys(InterferingVReg.reg);
321    DEBUG(dbgs() << "reassigning: " << InterferingVReg << " from " <<
322          TRI->getName(OldAssign) << " to " << TRI->getName(PhysReg) << '\n');
323    unassign(InterferingVReg, OldAssign);
324    assign(InterferingVReg, PhysReg);
325    ++NumReassigned;
326    return true;
327  }
328  return false;
329}
330
331/// tryReassign - Try to reassign a single interference to a different physreg.
332/// @param  VirtReg Currently unassigned virtual register.
333/// @param  Order   Physregs to try.
334/// @return         Physreg to assign VirtReg, or 0.
335unsigned RAGreedy::tryReassign(LiveInterval &VirtReg, AllocationOrder &Order,
336                               SmallVectorImpl<LiveInterval*> &NewVRegs){
337  NamedRegionTimer T("Reassign", TimerGroupName, TimePassesIsEnabled);
338
339  Order.rewind();
340  while (unsigned PhysReg = Order.next()) {
341    LiveInterval *InterferingVReg = getSingleInterference(VirtReg, PhysReg);
342    if (!InterferingVReg)
343      continue;
344    if (TargetRegisterInfo::isPhysicalRegister(InterferingVReg->reg))
345      continue;
346    if (reassignVReg(*InterferingVReg, PhysReg))
347      return PhysReg;
348  }
349  return 0;
350}
351
352
353//===----------------------------------------------------------------------===//
354//                         Interference eviction
355//===----------------------------------------------------------------------===//
356
357/// canEvict - Return true if all interferences between VirtReg and PhysReg can
358/// be evicted. Set maxWeight to the maximal spill weight of an interference.
359bool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg,
360                                    unsigned Size, float &MaxWeight) {
361  float Weight = 0;
362  for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
363    LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
364    // If there is 10 or more interferences, chances are one is smaller.
365    if (Q.collectInterferingVRegs(10) >= 10)
366      return false;
367
368    // CHeck if any interfering live range is shorter than VirtReg.
369    for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) {
370      LiveInterval *Intf = Q.interferingVRegs()[i];
371      if (TargetRegisterInfo::isPhysicalRegister(Intf->reg))
372        return false;
373      if (Intf->getSize() <= Size)
374        return false;
375      Weight = std::max(Weight, Intf->weight);
376    }
377  }
378  MaxWeight = Weight;
379  return true;
380}
381
382/// tryEvict - Try to evict all interferences for a physreg.
383/// @param  VirtReg Currently unassigned virtual register.
384/// @param  Order   Physregs to try.
385/// @return         Physreg to assign VirtReg, or 0.
386unsigned RAGreedy::tryEvict(LiveInterval &VirtReg,
387                            AllocationOrder &Order,
388                            SmallVectorImpl<LiveInterval*> &NewVRegs){
389  NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled);
390
391  // We can only evict interference if all interfering registers are virtual and
392  // longer than VirtReg.
393  const unsigned Size = VirtReg.getSize();
394
395  // Keep track of the lightest single interference seen so far.
396  float BestWeight = 0;
397  unsigned BestPhys = 0;
398
399  Order.rewind();
400  while (unsigned PhysReg = Order.next()) {
401    float Weight = 0;
402    if (!canEvictInterference(VirtReg, PhysReg, Size, Weight))
403      continue;
404
405    // This is an eviction candidate.
406    DEBUG(dbgs() << "max " << PrintReg(PhysReg, TRI) << " interference = "
407                 << Weight << '\n');
408    if (BestPhys && Weight >= BestWeight)
409      continue;
410
411    // Best so far.
412    BestPhys = PhysReg;
413    BestWeight = Weight;
414    // Stop if the hint can be used.
415    if (Order.isHint(PhysReg))
416      break;
417  }
418
419  if (!BestPhys)
420    return 0;
421
422  DEBUG(dbgs() << "evicting " << PrintReg(BestPhys, TRI) << " interference\n");
423  for (const unsigned *AliasI = TRI->getOverlaps(BestPhys); *AliasI; ++AliasI) {
424    LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
425    assert(Q.seenAllInterferences() && "Didn't check all interfererences.");
426    for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) {
427      LiveInterval *Intf = Q.interferingVRegs()[i];
428      unassign(*Intf, VRM->getPhys(Intf->reg));
429      ++NumEvicted;
430      NewVRegs.push_back(Intf);
431    }
432  }
433  return BestPhys;
434}
435
436
437//===----------------------------------------------------------------------===//
438//                              Region Splitting
439//===----------------------------------------------------------------------===//
440
441/// calcInterferenceInfo - Compute per-block outgoing and ingoing constraints
442/// when considering interference from PhysReg. Also compute an optimistic local
443/// cost of this interference pattern.
444///
445/// The final cost of a split is the local cost + global cost of preferences
446/// broken by SpillPlacement.
447///
448float RAGreedy::calcInterferenceInfo(LiveInterval &VirtReg, unsigned PhysReg) {
449  // Reset interference dependent info.
450  SpillConstraints.resize(SA->LiveBlocks.size());
451  for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) {
452    SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i];
453    SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
454    BC.Number = BI.MBB->getNumber();
455    BC.Entry = (BI.Uses && BI.LiveIn) ?
456      SpillPlacement::PrefReg : SpillPlacement::DontCare;
457    BC.Exit = (BI.Uses && BI.LiveOut) ?
458      SpillPlacement::PrefReg : SpillPlacement::DontCare;
459    BI.OverlapEntry = BI.OverlapExit = false;
460  }
461
462  // Add interference info from each PhysReg alias.
463  for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
464    if (!query(VirtReg, *AI).checkInterference())
465      continue;
466    LiveIntervalUnion::SegmentIter IntI =
467      PhysReg2LiveUnion[*AI].find(VirtReg.beginIndex());
468    if (!IntI.valid())
469      continue;
470
471    // Determine which blocks have interference live in or after the last split
472    // point.
473    for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) {
474      SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i];
475      SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
476      SlotIndex Start, Stop;
477      tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
478
479      // Skip interference-free blocks.
480      if (IntI.start() >= Stop)
481        continue;
482
483      // Is the interference live-in?
484      if (BI.LiveIn) {
485        IntI.advanceTo(Start);
486        if (!IntI.valid())
487          break;
488        if (IntI.start() <= Start)
489          BC.Entry = SpillPlacement::MustSpill;
490      }
491
492      // Is the interference overlapping the last split point?
493      if (BI.LiveOut) {
494        if (IntI.stop() < BI.LastSplitPoint)
495          IntI.advanceTo(BI.LastSplitPoint.getPrevSlot());
496        if (!IntI.valid())
497          break;
498        if (IntI.start() < Stop)
499          BC.Exit = SpillPlacement::MustSpill;
500      }
501    }
502
503    // Rewind iterator and check other interferences.
504    IntI.find(VirtReg.beginIndex());
505    for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) {
506      SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i];
507      SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
508      SlotIndex Start, Stop;
509      tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
510
511      // Skip interference-free blocks.
512      if (IntI.start() >= Stop)
513        continue;
514
515      // Handle transparent blocks with interference separately.
516      // Transparent blocks never incur any fixed cost.
517      if (BI.LiveThrough && !BI.Uses) {
518        IntI.advanceTo(Start);
519        if (!IntI.valid())
520          break;
521        if (IntI.start() >= Stop)
522          continue;
523
524        if (BC.Entry != SpillPlacement::MustSpill)
525          BC.Entry = SpillPlacement::PrefSpill;
526        if (BC.Exit != SpillPlacement::MustSpill)
527          BC.Exit = SpillPlacement::PrefSpill;
528        continue;
529      }
530
531      // Now we only have blocks with uses left.
532      // Check if the interference overlaps the uses.
533      assert(BI.Uses && "Non-transparent block without any uses");
534
535      // Check interference on entry.
536      if (BI.LiveIn && BC.Entry != SpillPlacement::MustSpill) {
537        IntI.advanceTo(Start);
538        if (!IntI.valid())
539          break;
540        // Not live in, but before the first use.
541        if (IntI.start() < BI.FirstUse) {
542          BC.Entry = SpillPlacement::PrefSpill;
543          // If the block contains a kill from an earlier split, never split
544          // again in the same block.
545          if (!BI.LiveThrough && !SA->isOriginalEndpoint(BI.Kill))
546            BC.Entry = SpillPlacement::MustSpill;
547        }
548      }
549
550      // Does interference overlap the uses in the entry segment
551      // [FirstUse;Kill)?
552      if (BI.LiveIn && !BI.OverlapEntry) {
553        IntI.advanceTo(BI.FirstUse);
554        if (!IntI.valid())
555          break;
556        // A live-through interval has no kill.
557        // Check [FirstUse;LastUse) instead.
558        if (IntI.start() < (BI.LiveThrough ? BI.LastUse : BI.Kill))
559          BI.OverlapEntry = true;
560      }
561
562      // Does interference overlap the uses in the exit segment [Def;LastUse)?
563      if (BI.LiveOut && !BI.LiveThrough && !BI.OverlapExit) {
564        IntI.advanceTo(BI.Def);
565        if (!IntI.valid())
566          break;
567        if (IntI.start() < BI.LastUse)
568          BI.OverlapExit = true;
569      }
570
571      // Check interference on exit.
572      if (BI.LiveOut && BC.Exit != SpillPlacement::MustSpill) {
573        // Check interference between LastUse and Stop.
574        if (BC.Exit != SpillPlacement::PrefSpill) {
575          IntI.advanceTo(BI.LastUse);
576          if (!IntI.valid())
577            break;
578          if (IntI.start() < Stop) {
579            BC.Exit = SpillPlacement::PrefSpill;
580            // Avoid splitting twice in the same block.
581            if (!BI.LiveThrough && !SA->isOriginalEndpoint(BI.Def))
582              BC.Exit = SpillPlacement::MustSpill;
583          }
584        }
585      }
586    }
587  }
588
589  // Accumulate a local cost of this interference pattern.
590  float LocalCost = 0;
591  for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) {
592    SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i];
593    if (!BI.Uses)
594      continue;
595    SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
596    unsigned Inserts = 0;
597
598    // Do we need spill code for the entry segment?
599    if (BI.LiveIn)
600      Inserts += BI.OverlapEntry || BC.Entry != SpillPlacement::PrefReg;
601
602    // For the exit segment?
603    if (BI.LiveOut)
604      Inserts += BI.OverlapExit || BC.Exit != SpillPlacement::PrefReg;
605
606    // The local cost of spill code in this block is the block frequency times
607    // the number of spill instructions inserted.
608    if (Inserts)
609      LocalCost += Inserts * SpillPlacer->getBlockFrequency(BI.MBB);
610  }
611  DEBUG(dbgs() << "Local cost of " << PrintReg(PhysReg, TRI) << " = "
612               << LocalCost << '\n');
613  return LocalCost;
614}
615
616/// calcGlobalSplitCost - Return the global split cost of following the split
617/// pattern in LiveBundles. This cost should be added to the local cost of the
618/// interference pattern in SpillConstraints.
619///
620float RAGreedy::calcGlobalSplitCost(const BitVector &LiveBundles) {
621  float GlobalCost = 0;
622  for (unsigned i = 0, e = SpillConstraints.size(); i != e; ++i) {
623    SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
624    unsigned Inserts = 0;
625    // Broken entry preference?
626    Inserts += LiveBundles[Bundles->getBundle(BC.Number, 0)] !=
627                 (BC.Entry == SpillPlacement::PrefReg);
628    // Broken exit preference?
629    Inserts += LiveBundles[Bundles->getBundle(BC.Number, 1)] !=
630                 (BC.Exit == SpillPlacement::PrefReg);
631    if (Inserts)
632      GlobalCost +=
633        Inserts * SpillPlacer->getBlockFrequency(SA->LiveBlocks[i].MBB);
634  }
635  DEBUG(dbgs() << "Global cost = " << GlobalCost << '\n');
636  return GlobalCost;
637}
638
639/// splitAroundRegion - Split VirtReg around the region determined by
640/// LiveBundles. Make an effort to avoid interference from PhysReg.
641///
642/// The 'register' interval is going to contain as many uses as possible while
643/// avoiding interference. The 'stack' interval is the complement constructed by
644/// SplitEditor. It will contain the rest.
645///
646void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
647                                 const BitVector &LiveBundles,
648                                 SmallVectorImpl<LiveInterval*> &NewVRegs) {
649  DEBUG({
650    dbgs() << "Splitting around region for " << PrintReg(PhysReg, TRI)
651           << " with bundles";
652    for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i))
653      dbgs() << " EB#" << i;
654    dbgs() << ".\n";
655  });
656
657  // First compute interference ranges in the live blocks.
658  typedef std::pair<SlotIndex, SlotIndex> IndexPair;
659  SmallVector<IndexPair, 8> InterferenceRanges;
660  InterferenceRanges.resize(SA->LiveBlocks.size());
661  for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
662    if (!query(VirtReg, *AI).checkInterference())
663      continue;
664    LiveIntervalUnion::SegmentIter IntI =
665      PhysReg2LiveUnion[*AI].find(VirtReg.beginIndex());
666    if (!IntI.valid())
667      continue;
668    for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) {
669      const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i];
670      IndexPair &IP = InterferenceRanges[i];
671      SlotIndex Start, Stop;
672      tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
673      // Skip interference-free blocks.
674      if (IntI.start() >= Stop)
675        continue;
676
677      // First interference in block.
678      if (BI.LiveIn) {
679        IntI.advanceTo(Start);
680        if (!IntI.valid())
681          break;
682        if (IntI.start() >= Stop)
683          continue;
684        if (!IP.first.isValid() || IntI.start() < IP.first)
685          IP.first = IntI.start();
686      }
687
688      // Last interference in block.
689      if (BI.LiveOut) {
690        IntI.advanceTo(Stop);
691        if (!IntI.valid() || IntI.start() >= Stop)
692          --IntI;
693        if (IntI.stop() <= Start)
694          continue;
695        if (!IP.second.isValid() || IntI.stop() > IP.second)
696          IP.second = IntI.stop();
697      }
698    }
699  }
700
701  SmallVector<LiveInterval*, 4> SpillRegs;
702  LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs);
703  SE->reset(LREdit);
704
705  // Create the main cross-block interval.
706  SE->openIntv();
707
708  // First add all defs that are live out of a block.
709  for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) {
710    SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i];
711    bool RegIn  = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
712    bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
713
714    // Should the register be live out?
715    if (!BI.LiveOut || !RegOut)
716      continue;
717
718    IndexPair &IP = InterferenceRanges[i];
719    SlotIndex Start, Stop;
720    tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
721
722    DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#"
723                 << Bundles->getBundle(BI.MBB->getNumber(), 1)
724                 << " intf [" << IP.first << ';' << IP.second << ')');
725
726    // The interference interval should either be invalid or overlap MBB.
727    assert((!IP.first.isValid() || IP.first < Stop) && "Bad interference");
728    assert((!IP.second.isValid() || IP.second > Start) && "Bad interference");
729
730    // Check interference leaving the block.
731    if (!IP.second.isValid()) {
732      // Block is interference-free.
733      DEBUG(dbgs() << ", no interference");
734      if (!BI.Uses) {
735        assert(BI.LiveThrough && "No uses, but not live through block?");
736        // Block is live-through without interference.
737        DEBUG(dbgs() << ", no uses"
738                     << (RegIn ? ", live-through.\n" : ", stack in.\n"));
739        if (!RegIn)
740          SE->enterIntvAtEnd(*BI.MBB);
741        continue;
742      }
743      if (!BI.LiveThrough) {
744        DEBUG(dbgs() << ", not live-through.\n");
745        SE->useIntv(SE->enterIntvBefore(BI.Def), Stop);
746        continue;
747      }
748      if (!RegIn) {
749        // Block is live-through, but entry bundle is on the stack.
750        // Reload just before the first use.
751        DEBUG(dbgs() << ", not live-in, enter before first use.\n");
752        SE->useIntv(SE->enterIntvBefore(BI.FirstUse), Stop);
753        continue;
754      }
755      DEBUG(dbgs() << ", live-through.\n");
756      continue;
757    }
758
759    // Block has interference.
760    DEBUG(dbgs() << ", interference to " << IP.second);
761
762    if (!BI.LiveThrough && IP.second <= BI.Def) {
763      // The interference doesn't reach the outgoing segment.
764      DEBUG(dbgs() << " doesn't affect def from " << BI.Def << '\n');
765      SE->useIntv(BI.Def, Stop);
766      continue;
767    }
768
769
770    if (!BI.Uses) {
771      // No uses in block, avoid interference by reloading as late as possible.
772      DEBUG(dbgs() << ", no uses.\n");
773      SlotIndex SegStart = SE->enterIntvAtEnd(*BI.MBB);
774      assert(SegStart >= IP.second && "Couldn't avoid interference");
775      continue;
776    }
777
778    if (IP.second.getBoundaryIndex() < BI.LastUse) {
779      // There are interference-free uses at the end of the block.
780      // Find the first use that can get the live-out register.
781      SmallVectorImpl<SlotIndex>::const_iterator UI =
782        std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(),
783                         IP.second.getBoundaryIndex());
784      assert(UI != SA->UseSlots.end() && "Couldn't find last use");
785      SlotIndex Use = *UI;
786      assert(Use <= BI.LastUse && "Couldn't find last use");
787      // Only attempt a split befroe the last split point.
788      if (Use.getBaseIndex() <= BI.LastSplitPoint) {
789        DEBUG(dbgs() << ", free use at " << Use << ".\n");
790        SlotIndex SegStart = SE->enterIntvBefore(Use);
791        assert(SegStart >= IP.second && "Couldn't avoid interference");
792        assert(SegStart < BI.LastSplitPoint && "Impossible split point");
793        SE->useIntv(SegStart, Stop);
794        continue;
795      }
796    }
797
798    // Interference is after the last use.
799    DEBUG(dbgs() << " after last use.\n");
800    SlotIndex SegStart = SE->enterIntvAtEnd(*BI.MBB);
801    assert(SegStart >= IP.second && "Couldn't avoid interference");
802  }
803
804  // Now all defs leading to live bundles are handled, do everything else.
805  for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) {
806    SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i];
807    bool RegIn  = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
808    bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
809
810    // Is the register live-in?
811    if (!BI.LiveIn || !RegIn)
812      continue;
813
814    // We have an incoming register. Check for interference.
815    IndexPair &IP = InterferenceRanges[i];
816    SlotIndex Start, Stop;
817    tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
818
819    DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0)
820                 << " -> BB#" << BI.MBB->getNumber());
821
822    // Check interference entering the block.
823    if (!IP.first.isValid()) {
824      // Block is interference-free.
825      DEBUG(dbgs() << ", no interference");
826      if (!BI.Uses) {
827        assert(BI.LiveThrough && "No uses, but not live through block?");
828        // Block is live-through without interference.
829        if (RegOut) {
830          DEBUG(dbgs() << ", no uses, live-through.\n");
831          SE->useIntv(Start, Stop);
832        } else {
833          DEBUG(dbgs() << ", no uses, stack-out.\n");
834          SE->leaveIntvAtTop(*BI.MBB);
835        }
836        continue;
837      }
838      if (!BI.LiveThrough) {
839        DEBUG(dbgs() << ", killed in block.\n");
840        SE->useIntv(Start, SE->leaveIntvAfter(BI.Kill));
841        continue;
842      }
843      if (!RegOut) {
844        // Block is live-through, but exit bundle is on the stack.
845        // Spill immediately after the last use.
846        if (BI.LastUse < BI.LastSplitPoint) {
847          DEBUG(dbgs() << ", uses, stack-out.\n");
848          SE->useIntv(Start, SE->leaveIntvAfter(BI.LastUse));
849          continue;
850        }
851        // The last use is after the last split point, it is probably an
852        // indirect jump.
853        DEBUG(dbgs() << ", uses at " << BI.LastUse << " after split point "
854                     << BI.LastSplitPoint << ", stack-out.\n");
855        SlotIndex SegEnd = SE->leaveIntvBefore(BI.LastSplitPoint);
856        SE->useIntv(Start, SegEnd);
857        // Run a double interval from the split to the last use.
858        // This makes it possible to spill the complement without affecting the
859        // indirect branch.
860        SE->overlapIntv(SegEnd, BI.LastUse);
861        continue;
862      }
863      // Register is live-through.
864      DEBUG(dbgs() << ", uses, live-through.\n");
865      SE->useIntv(Start, Stop);
866      continue;
867    }
868
869    // Block has interference.
870    DEBUG(dbgs() << ", interference from " << IP.first);
871
872    if (!BI.LiveThrough && IP.first >= BI.Kill) {
873      // The interference doesn't reach the outgoing segment.
874      DEBUG(dbgs() << " doesn't affect kill at " << BI.Kill << '\n');
875      SE->useIntv(Start, BI.Kill);
876      continue;
877    }
878
879    if (!BI.Uses) {
880      // No uses in block, avoid interference by spilling as soon as possible.
881      DEBUG(dbgs() << ", no uses.\n");
882      SlotIndex SegEnd = SE->leaveIntvAtTop(*BI.MBB);
883      assert(SegEnd <= IP.first && "Couldn't avoid interference");
884      continue;
885    }
886    if (IP.first.getBaseIndex() > BI.FirstUse) {
887      // There are interference-free uses at the beginning of the block.
888      // Find the last use that can get the register.
889      SmallVectorImpl<SlotIndex>::const_iterator UI =
890        std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(),
891                         IP.first.getBaseIndex());
892      assert(UI != SA->UseSlots.begin() && "Couldn't find first use");
893      SlotIndex Use = (--UI)->getBoundaryIndex();
894      DEBUG(dbgs() << ", free use at " << *UI << ".\n");
895      SlotIndex SegEnd = SE->leaveIntvAfter(Use);
896      assert(SegEnd <= IP.first && "Couldn't avoid interference");
897      SE->useIntv(Start, SegEnd);
898      continue;
899    }
900
901    // Interference is before the first use.
902    DEBUG(dbgs() << " before first use.\n");
903    SlotIndex SegEnd = SE->leaveIntvAtTop(*BI.MBB);
904    assert(SegEnd <= IP.first && "Couldn't avoid interference");
905  }
906
907  SE->closeIntv();
908
909  // FIXME: Should we be more aggressive about splitting the stack region into
910  // per-block segments? The current approach allows the stack region to
911  // separate into connected components. Some components may be allocatable.
912  SE->finish();
913  ++NumGlobalSplits;
914
915  if (VerifyEnabled) {
916    MF->verify(this, "After splitting live range around region");
917
918#ifndef NDEBUG
919    // Make sure that at least one of the new intervals can allocate to PhysReg.
920    // That was the whole point of splitting the live range.
921    bool found = false;
922    for (LiveRangeEdit::iterator I = LREdit.begin(), E = LREdit.end(); I != E;
923         ++I)
924      if (!checkUncachedInterference(**I, PhysReg)) {
925        found = true;
926        break;
927      }
928    assert(found && "No allocatable intervals after pointless splitting");
929#endif
930  }
931}
932
933unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
934                                  SmallVectorImpl<LiveInterval*> &NewVRegs) {
935  BitVector LiveBundles, BestBundles;
936  float BestCost = 0;
937  unsigned BestReg = 0;
938  Order.rewind();
939  while (unsigned PhysReg = Order.next()) {
940    float Cost = calcInterferenceInfo(VirtReg, PhysReg);
941    if (BestReg && Cost >= BestCost)
942      continue;
943
944    SpillPlacer->placeSpills(SpillConstraints, LiveBundles);
945    // No live bundles, defer to splitSingleBlocks().
946    if (!LiveBundles.any())
947      continue;
948
949    Cost += calcGlobalSplitCost(LiveBundles);
950    if (!BestReg || Cost < BestCost) {
951      BestReg = PhysReg;
952      BestCost = Cost;
953      BestBundles.swap(LiveBundles);
954    }
955  }
956
957  if (!BestReg)
958    return 0;
959
960  splitAroundRegion(VirtReg, BestReg, BestBundles, NewVRegs);
961  setStage(NewVRegs.begin(), NewVRegs.end(), RS_Region);
962  return 0;
963}
964
965
966//===----------------------------------------------------------------------===//
967//                             Local Splitting
968//===----------------------------------------------------------------------===//
969
970
971/// calcGapWeights - Compute the maximum spill weight that needs to be evicted
972/// in order to use PhysReg between two entries in SA->UseSlots.
973///
974/// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1].
975///
976void RAGreedy::calcGapWeights(unsigned PhysReg,
977                              SmallVectorImpl<float> &GapWeight) {
978  assert(SA->LiveBlocks.size() == 1 && "Not a local interval");
979  const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks.front();
980  const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots;
981  const unsigned NumGaps = Uses.size()-1;
982
983  // Start and end points for the interference check.
984  SlotIndex StartIdx = BI.LiveIn ? BI.FirstUse.getBaseIndex() : BI.FirstUse;
985  SlotIndex StopIdx = BI.LiveOut ? BI.LastUse.getBoundaryIndex() : BI.LastUse;
986
987  GapWeight.assign(NumGaps, 0.0f);
988
989  // Add interference from each overlapping register.
990  for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
991    if (!query(const_cast<LiveInterval&>(SA->getParent()), *AI)
992           .checkInterference())
993      continue;
994
995    // We know that VirtReg is a continuous interval from FirstUse to LastUse,
996    // so we don't need InterferenceQuery.
997    //
998    // Interference that overlaps an instruction is counted in both gaps
999    // surrounding the instruction. The exception is interference before
1000    // StartIdx and after StopIdx.
1001    //
1002    LiveIntervalUnion::SegmentIter IntI = PhysReg2LiveUnion[*AI].find(StartIdx);
1003    for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) {
1004      // Skip the gaps before IntI.
1005      while (Uses[Gap+1].getBoundaryIndex() < IntI.start())
1006        if (++Gap == NumGaps)
1007          break;
1008      if (Gap == NumGaps)
1009        break;
1010
1011      // Update the gaps covered by IntI.
1012      const float weight = IntI.value()->weight;
1013      for (; Gap != NumGaps; ++Gap) {
1014        GapWeight[Gap] = std::max(GapWeight[Gap], weight);
1015        if (Uses[Gap+1].getBaseIndex() >= IntI.stop())
1016          break;
1017      }
1018      if (Gap == NumGaps)
1019        break;
1020    }
1021  }
1022}
1023
1024/// getPrevMappedIndex - Return the slot index of the last non-copy instruction
1025/// before MI that has a slot index. If MI is the first mapped instruction in
1026/// its block, return the block start index instead.
1027///
1028SlotIndex RAGreedy::getPrevMappedIndex(const MachineInstr *MI) {
1029  assert(MI && "Missing MachineInstr");
1030  const MachineBasicBlock *MBB = MI->getParent();
1031  MachineBasicBlock::const_iterator B = MBB->begin(), I = MI;
1032  while (I != B)
1033    if (!(--I)->isDebugValue() && !I->isCopy())
1034      return Indexes->getInstructionIndex(I);
1035  return Indexes->getMBBStartIdx(MBB);
1036}
1037
1038/// calcPrevSlots - Fill in the PrevSlot array with the index of the previous
1039/// real non-copy instruction for each instruction in SA->UseSlots.
1040///
1041void RAGreedy::calcPrevSlots() {
1042  const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots;
1043  PrevSlot.clear();
1044  PrevSlot.reserve(Uses.size());
1045  for (unsigned i = 0, e = Uses.size(); i != e; ++i) {
1046    const MachineInstr *MI = Indexes->getInstructionFromIndex(Uses[i]);
1047    PrevSlot.push_back(getPrevMappedIndex(MI).getDefIndex());
1048  }
1049}
1050
1051/// nextSplitPoint - Find the next index into SA->UseSlots > i such that it may
1052/// be beneficial to split before UseSlots[i].
1053///
1054/// 0 is always a valid split point
1055unsigned RAGreedy::nextSplitPoint(unsigned i) {
1056  const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots;
1057  const unsigned Size = Uses.size();
1058  assert(i != Size && "No split points after the end");
1059  // Allow split before i when Uses[i] is not adjacent to the previous use.
1060  while (++i != Size && PrevSlot[i].getBaseIndex() <= Uses[i-1].getBaseIndex())
1061    ;
1062  return i;
1063}
1064
1065/// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only
1066/// basic block.
1067///
1068unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order,
1069                                 SmallVectorImpl<LiveInterval*> &NewVRegs) {
1070  assert(SA->LiveBlocks.size() == 1 && "Not a local interval");
1071  const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks.front();
1072
1073  // Note that it is possible to have an interval that is live-in or live-out
1074  // while only covering a single block - A phi-def can use undef values from
1075  // predecessors, and the block could be a single-block loop.
1076  // We don't bother doing anything clever about such a case, we simply assume
1077  // that the interval is continuous from FirstUse to LastUse. We should make
1078  // sure that we don't do anything illegal to such an interval, though.
1079
1080  const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots;
1081  if (Uses.size() <= 2)
1082    return 0;
1083  const unsigned NumGaps = Uses.size()-1;
1084
1085  DEBUG({
1086    dbgs() << "tryLocalSplit: ";
1087    for (unsigned i = 0, e = Uses.size(); i != e; ++i)
1088      dbgs() << ' ' << SA->UseSlots[i];
1089    dbgs() << '\n';
1090  });
1091
1092  // For every use, find the previous mapped non-copy instruction.
1093  // We use this to detect valid split points, and to estimate new interval
1094  // sizes.
1095  calcPrevSlots();
1096
1097  unsigned BestBefore = NumGaps;
1098  unsigned BestAfter = 0;
1099  float BestDiff = 0;
1100
1101  const float blockFreq = SpillPlacer->getBlockFrequency(BI.MBB);
1102  SmallVector<float, 8> GapWeight;
1103
1104  Order.rewind();
1105  while (unsigned PhysReg = Order.next()) {
1106    // Keep track of the largest spill weight that would need to be evicted in
1107    // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1].
1108    calcGapWeights(PhysReg, GapWeight);
1109
1110    // Try to find the best sequence of gaps to close.
1111    // The new spill weight must be larger than any gap interference.
1112
1113    // We will split before Uses[SplitBefore] and after Uses[SplitAfter].
1114    unsigned SplitBefore = 0, SplitAfter = nextSplitPoint(1) - 1;
1115
1116    // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]).
1117    // It is the spill weight that needs to be evicted.
1118    float MaxGap = GapWeight[0];
1119    for (unsigned i = 1; i != SplitAfter; ++i)
1120      MaxGap = std::max(MaxGap, GapWeight[i]);
1121
1122    for (;;) {
1123      // Live before/after split?
1124      const bool LiveBefore = SplitBefore != 0 || BI.LiveIn;
1125      const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut;
1126
1127      DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' '
1128                   << Uses[SplitBefore] << '-' << Uses[SplitAfter]
1129                   << " i=" << MaxGap);
1130
1131      // Stop before the interval gets so big we wouldn't be making progress.
1132      if (!LiveBefore && !LiveAfter) {
1133        DEBUG(dbgs() << " all\n");
1134        break;
1135      }
1136      // Should the interval be extended or shrunk?
1137      bool Shrink = true;
1138      if (MaxGap < HUGE_VALF) {
1139        // Estimate the new spill weight.
1140        //
1141        // Each instruction reads and writes the register, except the first
1142        // instr doesn't read when !FirstLive, and the last instr doesn't write
1143        // when !LastLive.
1144        //
1145        // We will be inserting copies before and after, so the total number of
1146        // reads and writes is 2 * EstUses.
1147        //
1148        const unsigned EstUses = 2*(SplitAfter - SplitBefore) +
1149                                 2*(LiveBefore + LiveAfter);
1150
1151        // Try to guess the size of the new interval. This should be trivial,
1152        // but the slot index of an inserted copy can be a lot smaller than the
1153        // instruction it is inserted before if there are many dead indexes
1154        // between them.
1155        //
1156        // We measure the distance from the instruction before SplitBefore to
1157        // get a conservative estimate.
1158        //
1159        // The final distance can still be different if inserting copies
1160        // triggers a slot index renumbering.
1161        //
1162        const float EstWeight = normalizeSpillWeight(blockFreq * EstUses,
1163                              PrevSlot[SplitBefore].distance(Uses[SplitAfter]));
1164        // Would this split be possible to allocate?
1165        // Never allocate all gaps, we wouldn't be making progress.
1166        float Diff = EstWeight - MaxGap;
1167        DEBUG(dbgs() << " w=" << EstWeight << " d=" << Diff);
1168        if (Diff > 0) {
1169          Shrink = false;
1170          if (Diff > BestDiff) {
1171            DEBUG(dbgs() << " (best)");
1172            BestDiff = Diff;
1173            BestBefore = SplitBefore;
1174            BestAfter = SplitAfter;
1175          }
1176        }
1177      }
1178
1179      // Try to shrink.
1180      if (Shrink) {
1181        SplitBefore = nextSplitPoint(SplitBefore);
1182        if (SplitBefore < SplitAfter) {
1183          DEBUG(dbgs() << " shrink\n");
1184          // Recompute the max when necessary.
1185          if (GapWeight[SplitBefore - 1] >= MaxGap) {
1186            MaxGap = GapWeight[SplitBefore];
1187            for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i)
1188              MaxGap = std::max(MaxGap, GapWeight[i]);
1189          }
1190          continue;
1191        }
1192        MaxGap = 0;
1193      }
1194
1195      // Try to extend the interval.
1196      if (SplitAfter >= NumGaps) {
1197        DEBUG(dbgs() << " end\n");
1198        break;
1199      }
1200
1201      DEBUG(dbgs() << " extend\n");
1202      for (unsigned e = nextSplitPoint(SplitAfter + 1) - 1;
1203           SplitAfter != e; ++SplitAfter)
1204        MaxGap = std::max(MaxGap, GapWeight[SplitAfter]);
1205          continue;
1206    }
1207  }
1208
1209  // Didn't find any candidates?
1210  if (BestBefore == NumGaps)
1211    return 0;
1212
1213  DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore]
1214               << '-' << Uses[BestAfter] << ", " << BestDiff
1215               << ", " << (BestAfter - BestBefore + 1) << " instrs\n");
1216
1217  SmallVector<LiveInterval*, 4> SpillRegs;
1218  LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs);
1219  SE->reset(LREdit);
1220
1221  SE->openIntv();
1222  SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]);
1223  SlotIndex SegStop  = SE->leaveIntvAfter(Uses[BestAfter]);
1224  SE->useIntv(SegStart, SegStop);
1225  SE->closeIntv();
1226  SE->finish();
1227  setStage(NewVRegs.begin(), NewVRegs.end(), RS_Local);
1228  ++NumLocalSplits;
1229
1230  return 0;
1231}
1232
1233//===----------------------------------------------------------------------===//
1234//                          Live Range Splitting
1235//===----------------------------------------------------------------------===//
1236
1237/// trySplit - Try to split VirtReg or one of its interferences, making it
1238/// assignable.
1239/// @return Physreg when VirtReg may be assigned and/or new NewVRegs.
1240unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
1241                            SmallVectorImpl<LiveInterval*>&NewVRegs) {
1242  // Local intervals are handled separately.
1243  if (LIS->intervalIsInOneMBB(VirtReg)) {
1244    NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled);
1245    SA->analyze(&VirtReg);
1246    return tryLocalSplit(VirtReg, Order, NewVRegs);
1247  }
1248
1249  NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled);
1250
1251  // Don't iterate global splitting.
1252  // Move straight to spilling if this range was produced by a global split.
1253  LiveRangeStage Stage = getStage(VirtReg);
1254  if (Stage >= RS_Block)
1255    return 0;
1256
1257  SA->analyze(&VirtReg);
1258
1259  // First try to split around a region spanning multiple blocks.
1260  if (Stage < RS_Region) {
1261    unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
1262    if (PhysReg || !NewVRegs.empty())
1263      return PhysReg;
1264  }
1265
1266  // Then isolate blocks with multiple uses.
1267  if (Stage < RS_Block) {
1268    SplitAnalysis::BlockPtrSet Blocks;
1269    if (SA->getMultiUseBlocks(Blocks)) {
1270      SmallVector<LiveInterval*, 4> SpillRegs;
1271      LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs);
1272      SE->reset(LREdit);
1273      SE->splitSingleBlocks(Blocks);
1274      setStage(NewVRegs.begin(), NewVRegs.end(), RS_Block);
1275      if (VerifyEnabled)
1276        MF->verify(this, "After splitting live range around basic blocks");
1277    }
1278  }
1279
1280  // Don't assign any physregs.
1281  return 0;
1282}
1283
1284
1285//===----------------------------------------------------------------------===//
1286//                            Main Entry Point
1287//===----------------------------------------------------------------------===//
1288
1289unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
1290                                 SmallVectorImpl<LiveInterval*> &NewVRegs) {
1291  LiveRangeStage Stage = getStage(VirtReg);
1292  if (Stage == RS_Original)
1293    LRStage[VirtReg.reg] = RS_Second;
1294
1295  // First try assigning a free register.
1296  AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs);
1297  while (unsigned PhysReg = Order.next()) {
1298    if (!checkPhysRegInterference(VirtReg, PhysReg))
1299      return PhysReg;
1300  }
1301
1302  if (unsigned PhysReg = tryReassign(VirtReg, Order, NewVRegs))
1303    return PhysReg;
1304
1305  if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs))
1306    return PhysReg;
1307
1308  assert(NewVRegs.empty() && "Cannot append to existing NewVRegs");
1309
1310  // The first time we see a live range, don't try to split or spill.
1311  // Wait until the second time, when all smaller ranges have been allocated.
1312  // This gives a better picture of the interference to split around.
1313  if (Stage == RS_Original) {
1314    NewVRegs.push_back(&VirtReg);
1315    return 0;
1316  }
1317
1318  assert(Stage < RS_Spill && "Cannot allocate after spilling");
1319
1320  // Try splitting VirtReg or interferences.
1321  unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs);
1322  if (PhysReg || !NewVRegs.empty())
1323    return PhysReg;
1324
1325  // Finally spill VirtReg itself.
1326  NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled);
1327  SmallVector<LiveInterval*, 1> pendingSpills;
1328  spiller().spill(&VirtReg, NewVRegs, pendingSpills);
1329
1330  // The live virtual register requesting allocation was spilled, so tell
1331  // the caller not to allocate anything during this round.
1332  return 0;
1333}
1334
1335bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
1336  DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
1337               << "********** Function: "
1338               << ((Value*)mf.getFunction())->getName() << '\n');
1339
1340  MF = &mf;
1341  if (VerifyEnabled)
1342    MF->verify(this, "Before greedy register allocator");
1343
1344  RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>());
1345  Indexes = &getAnalysis<SlotIndexes>();
1346  DomTree = &getAnalysis<MachineDominatorTree>();
1347  ReservedRegs = TRI->getReservedRegs(*MF);
1348  SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
1349  Loops = &getAnalysis<MachineLoopInfo>();
1350  LoopRanges = &getAnalysis<MachineLoopRanges>();
1351  Bundles = &getAnalysis<EdgeBundles>();
1352  SpillPlacer = &getAnalysis<SpillPlacement>();
1353
1354  SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops));
1355  SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree));
1356  LRStage.clear();
1357  LRStage.resize(MRI->getNumVirtRegs());
1358
1359  allocatePhysRegs();
1360  addMBBLiveIns(MF);
1361  LIS->addKillFlags();
1362
1363  // Run rewriter
1364  {
1365    NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled);
1366    VRM->rewrite(Indexes);
1367  }
1368
1369  // The pass output is in VirtRegMap. Release all the transient data.
1370  releaseMemory();
1371
1372  return true;
1373}
1374