RegAllocGreedy.cpp revision fb69810a2b617d888b6ea7c6a69fee7364fe233b 
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
477      // Skip interference-free blocks.
478      if (IntI.start() >= BI.Stop)
479        continue;
480
481      // Is the interference live-in?
482      if (BI.LiveIn) {
483        IntI.advanceTo(BI.Start);
484        if (!IntI.valid())
485          break;
486        if (IntI.start() <= BI.Start)
487          BC.Entry = SpillPlacement::MustSpill;
488      }
489
490      // Is the interference overlapping the last split point?
491      if (BI.LiveOut) {
492        if (IntI.stop() < BI.LastSplitPoint)
493          IntI.advanceTo(BI.LastSplitPoint.getPrevSlot());
494        if (!IntI.valid())
495          break;
496        if (IntI.start() < BI.Stop)
497          BC.Exit = SpillPlacement::MustSpill;
498      }
499    }
500
501    // Rewind iterator and check other interferences.
502    IntI.find(VirtReg.beginIndex());
503    for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) {
504      SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i];
505      SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
506
507      // Skip interference-free blocks.
508      if (IntI.start() >= BI.Stop)
509        continue;
510
511      // Handle transparent blocks with interference separately.
512      // Transparent blocks never incur any fixed cost.
513      if (BI.LiveThrough && !BI.Uses) {
514        IntI.advanceTo(BI.Start);
515        if (!IntI.valid())
516          break;
517        if (IntI.start() >= BI.Stop)
518          continue;
519
520        if (BC.Entry != SpillPlacement::MustSpill)
521          BC.Entry = SpillPlacement::PrefSpill;
522        if (BC.Exit != SpillPlacement::MustSpill)
523          BC.Exit = SpillPlacement::PrefSpill;
524        continue;
525      }
526
527      // Now we only have blocks with uses left.
528      // Check if the interference overlaps the uses.
529      assert(BI.Uses && "Non-transparent block without any uses");
530
531      // Check interference on entry.
532      if (BI.LiveIn && BC.Entry != SpillPlacement::MustSpill) {
533        IntI.advanceTo(BI.Start);
534        if (!IntI.valid())
535          break;
536        // Not live in, but before the first use.
537        if (IntI.start() < BI.FirstUse) {
538          BC.Entry = SpillPlacement::PrefSpill;
539          // If the block contains a kill from an earlier split, never split
540          // again in the same block.
541          if (!BI.LiveThrough && !SA->isOriginalEndpoint(BI.Kill))
542            BC.Entry = SpillPlacement::MustSpill;
543        }
544      }
545
546      // Does interference overlap the uses in the entry segment
547      // [FirstUse;Kill)?
548      if (BI.LiveIn && !BI.OverlapEntry) {
549        IntI.advanceTo(BI.FirstUse);
550        if (!IntI.valid())
551          break;
552        // A live-through interval has no kill.
553        // Check [FirstUse;LastUse) instead.
554        if (IntI.start() < (BI.LiveThrough ? BI.LastUse : BI.Kill))
555          BI.OverlapEntry = true;
556      }
557
558      // Does interference overlap the uses in the exit segment [Def;LastUse)?
559      if (BI.LiveOut && !BI.LiveThrough && !BI.OverlapExit) {
560        IntI.advanceTo(BI.Def);
561        if (!IntI.valid())
562          break;
563        if (IntI.start() < BI.LastUse)
564          BI.OverlapExit = true;
565      }
566
567      // Check interference on exit.
568      if (BI.LiveOut && BC.Exit != SpillPlacement::MustSpill) {
569        // Check interference between LastUse and Stop.
570        if (BC.Exit != SpillPlacement::PrefSpill) {
571          IntI.advanceTo(BI.LastUse);
572          if (!IntI.valid())
573            break;
574          if (IntI.start() < BI.Stop) {
575            BC.Exit = SpillPlacement::PrefSpill;
576            // Avoid splitting twice in the same block.
577            if (!BI.LiveThrough && !SA->isOriginalEndpoint(BI.Def))
578              BC.Exit = SpillPlacement::MustSpill;
579          }
580        }
581      }
582    }
583  }
584
585  // Accumulate a local cost of this interference pattern.
586  float LocalCost = 0;
587  for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) {
588    SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i];
589    if (!BI.Uses)
590      continue;
591    SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
592    unsigned Inserts = 0;
593
594    // Do we need spill code for the entry segment?
595    if (BI.LiveIn)
596      Inserts += BI.OverlapEntry || BC.Entry != SpillPlacement::PrefReg;
597
598    // For the exit segment?
599    if (BI.LiveOut)
600      Inserts += BI.OverlapExit || BC.Exit != SpillPlacement::PrefReg;
601
602    // The local cost of spill code in this block is the block frequency times
603    // the number of spill instructions inserted.
604    if (Inserts)
605      LocalCost += Inserts * SpillPlacer->getBlockFrequency(BC.Number);
606  }
607  DEBUG(dbgs() << "Local cost of " << PrintReg(PhysReg, TRI) << " = "
608               << LocalCost << '\n');
609  return LocalCost;
610}
611
612/// calcGlobalSplitCost - Return the global split cost of following the split
613/// pattern in LiveBundles. This cost should be added to the local cost of the
614/// interference pattern in SpillConstraints.
615///
616float RAGreedy::calcGlobalSplitCost(const BitVector &LiveBundles) {
617  float GlobalCost = 0;
618  for (unsigned i = 0, e = SpillConstraints.size(); i != e; ++i) {
619    SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
620    unsigned Inserts = 0;
621    // Broken entry preference?
622    Inserts += LiveBundles[Bundles->getBundle(BC.Number, 0)] !=
623                 (BC.Entry == SpillPlacement::PrefReg);
624    // Broken exit preference?
625    Inserts += LiveBundles[Bundles->getBundle(BC.Number, 1)] !=
626                 (BC.Exit == SpillPlacement::PrefReg);
627    if (Inserts)
628      GlobalCost += Inserts * SpillPlacer->getBlockFrequency(BC.Number);
629  }
630  DEBUG({
631    dbgs() << "Global cost = " << GlobalCost << " with bundles";
632    for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i))
633      dbgs() << " EB#" << i;
634    dbgs() << ".\n";
635  });
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
672      // Skip interference-free blocks.
673      if (IntI.start() >= BI.Stop)
674        continue;
675
676      // First interference in block.
677      if (BI.LiveIn) {
678        IntI.advanceTo(BI.Start);
679        if (!IntI.valid())
680          break;
681        if (IntI.start() >= BI.Stop)
682          continue;
683        if (!IP.first.isValid() || IntI.start() < IP.first)
684          IP.first = IntI.start();
685      }
686
687      // Last interference in block.
688      if (BI.LiveOut) {
689        IntI.advanceTo(BI.Stop);
690        if (!IntI.valid() || IntI.start() >= BI.Stop)
691          --IntI;
692        if (IntI.stop() <= BI.Start)
693          continue;
694        if (!IP.second.isValid() || IntI.stop() > IP.second)
695          IP.second = IntI.stop();
696      }
697    }
698  }
699
700  SmallVector<LiveInterval*, 4> SpillRegs;
701  LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs);
702  SE->reset(LREdit);
703
704  // Create the main cross-block interval.
705  SE->openIntv();
706
707  // First add all defs that are live out of a block.
708  for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) {
709    SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i];
710    bool RegIn  = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
711    bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
712
713    // Should the register be live out?
714    if (!BI.LiveOut || !RegOut)
715      continue;
716
717    IndexPair &IP = InterferenceRanges[i];
718    DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#"
719                 << Bundles->getBundle(BI.MBB->getNumber(), 1)
720                 << " intf [" << IP.first << ';' << IP.second << ')');
721
722    // The interference interval should either be invalid or overlap MBB.
723    assert((!IP.first.isValid() || IP.first < BI.Stop) && "Bad interference");
724    assert((!IP.second.isValid() || IP.second > BI.Start)
725           && "Bad interference");
726
727    // Check interference leaving the block.
728    if (!IP.second.isValid()) {
729      // Block is interference-free.
730      DEBUG(dbgs() << ", no interference");
731      if (!BI.Uses) {
732        assert(BI.LiveThrough && "No uses, but not live through block?");
733        // Block is live-through without interference.
734        DEBUG(dbgs() << ", no uses"
735                     << (RegIn ? ", live-through.\n" : ", stack in.\n"));
736        if (!RegIn)
737          SE->enterIntvAtEnd(*BI.MBB);
738        continue;
739      }
740      if (!BI.LiveThrough) {
741        DEBUG(dbgs() << ", not live-through.\n");
742        SE->useIntv(SE->enterIntvBefore(BI.Def), BI.Stop);
743        continue;
744      }
745      if (!RegIn) {
746        // Block is live-through, but entry bundle is on the stack.
747        // Reload just before the first use.
748        DEBUG(dbgs() << ", not live-in, enter before first use.\n");
749        SE->useIntv(SE->enterIntvBefore(BI.FirstUse), BI.Stop);
750        continue;
751      }
752      DEBUG(dbgs() << ", live-through.\n");
753      continue;
754    }
755
756    // Block has interference.
757    DEBUG(dbgs() << ", interference to " << IP.second);
758
759    if (!BI.LiveThrough && IP.second <= BI.Def) {
760      // The interference doesn't reach the outgoing segment.
761      DEBUG(dbgs() << " doesn't affect def from " << BI.Def << '\n');
762      SE->useIntv(BI.Def, BI.Stop);
763      continue;
764    }
765
766
767    if (!BI.Uses) {
768      // No uses in block, avoid interference by reloading as late as possible.
769      DEBUG(dbgs() << ", no uses.\n");
770      SlotIndex SegStart = SE->enterIntvAtEnd(*BI.MBB);
771      assert(SegStart >= IP.second && "Couldn't avoid interference");
772      continue;
773    }
774
775    if (IP.second.getBoundaryIndex() < BI.LastUse) {
776      // There are interference-free uses at the end of the block.
777      // Find the first use that can get the live-out register.
778      SmallVectorImpl<SlotIndex>::const_iterator UI =
779        std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(),
780                         IP.second.getBoundaryIndex());
781      assert(UI != SA->UseSlots.end() && "Couldn't find last use");
782      SlotIndex Use = *UI;
783      assert(Use <= BI.LastUse && "Couldn't find last use");
784      // Only attempt a split befroe the last split point.
785      if (Use.getBaseIndex() <= BI.LastSplitPoint) {
786        DEBUG(dbgs() << ", free use at " << Use << ".\n");
787        SlotIndex SegStart = SE->enterIntvBefore(Use);
788        assert(SegStart >= IP.second && "Couldn't avoid interference");
789        assert(SegStart < BI.LastSplitPoint && "Impossible split point");
790        SE->useIntv(SegStart, BI.Stop);
791        continue;
792      }
793    }
794
795    // Interference is after the last use.
796    DEBUG(dbgs() << " after last use.\n");
797    SlotIndex SegStart = SE->enterIntvAtEnd(*BI.MBB);
798    assert(SegStart >= IP.second && "Couldn't avoid interference");
799  }
800
801  // Now all defs leading to live bundles are handled, do everything else.
802  for (unsigned i = 0, e = SA->LiveBlocks.size(); i != e; ++i) {
803    SplitAnalysis::BlockInfo &BI = SA->LiveBlocks[i];
804    bool RegIn  = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
805    bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
806
807    // Is the register live-in?
808    if (!BI.LiveIn || !RegIn)
809      continue;
810
811    // We have an incoming register. Check for interference.
812    IndexPair &IP = InterferenceRanges[i];
813
814    DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0)
815                 << " -> BB#" << BI.MBB->getNumber());
816
817    // Check interference entering the block.
818    if (!IP.first.isValid()) {
819      // Block is interference-free.
820      DEBUG(dbgs() << ", no interference");
821      if (!BI.Uses) {
822        assert(BI.LiveThrough && "No uses, but not live through block?");
823        // Block is live-through without interference.
824        if (RegOut) {
825          DEBUG(dbgs() << ", no uses, live-through.\n");
826          SE->useIntv(BI.Start, BI.Stop);
827        } else {
828          DEBUG(dbgs() << ", no uses, stack-out.\n");
829          SE->leaveIntvAtTop(*BI.MBB);
830        }
831        continue;
832      }
833      if (!BI.LiveThrough) {
834        DEBUG(dbgs() << ", killed in block.\n");
835        SE->useIntv(BI.Start, SE->leaveIntvAfter(BI.Kill));
836        continue;
837      }
838      if (!RegOut) {
839        // Block is live-through, but exit bundle is on the stack.
840        // Spill immediately after the last use.
841        if (BI.LastUse < BI.LastSplitPoint) {
842          DEBUG(dbgs() << ", uses, stack-out.\n");
843          SE->useIntv(BI.Start, SE->leaveIntvAfter(BI.LastUse));
844          continue;
845        }
846        // The last use is after the last split point, it is probably an
847        // indirect jump.
848        DEBUG(dbgs() << ", uses at " << BI.LastUse << " after split point "
849                     << BI.LastSplitPoint << ", stack-out.\n");
850        SlotIndex SegEnd = SE->leaveIntvBefore(BI.LastSplitPoint);
851        SE->useIntv(BI.Start, SegEnd);
852        // Run a double interval from the split to the last use.
853        // This makes it possible to spill the complement without affecting the
854        // indirect branch.
855        SE->overlapIntv(SegEnd, BI.LastUse);
856        continue;
857      }
858      // Register is live-through.
859      DEBUG(dbgs() << ", uses, live-through.\n");
860      SE->useIntv(BI.Start, BI.Stop);
861      continue;
862    }
863
864    // Block has interference.
865    DEBUG(dbgs() << ", interference from " << IP.first);
866
867    if (!BI.LiveThrough && IP.first >= BI.Kill) {
868      // The interference doesn't reach the outgoing segment.
869      DEBUG(dbgs() << " doesn't affect kill at " << BI.Kill << '\n');
870      SE->useIntv(BI.Start, BI.Kill);
871      continue;
872    }
873
874    if (!BI.Uses) {
875      // No uses in block, avoid interference by spilling as soon as possible.
876      DEBUG(dbgs() << ", no uses.\n");
877      SlotIndex SegEnd = SE->leaveIntvAtTop(*BI.MBB);
878      assert(SegEnd <= IP.first && "Couldn't avoid interference");
879      continue;
880    }
881    if (IP.first.getBaseIndex() > BI.FirstUse) {
882      // There are interference-free uses at the beginning of the block.
883      // Find the last use that can get the register.
884      SmallVectorImpl<SlotIndex>::const_iterator UI =
885        std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(),
886                         IP.first.getBaseIndex());
887      assert(UI != SA->UseSlots.begin() && "Couldn't find first use");
888      SlotIndex Use = (--UI)->getBoundaryIndex();
889      DEBUG(dbgs() << ", free use at " << *UI << ".\n");
890      SlotIndex SegEnd = SE->leaveIntvAfter(Use);
891      assert(SegEnd <= IP.first && "Couldn't avoid interference");
892      SE->useIntv(BI.Start, SegEnd);
893      continue;
894    }
895
896    // Interference is before the first use.
897    DEBUG(dbgs() << " before first use.\n");
898    SlotIndex SegEnd = SE->leaveIntvAtTop(*BI.MBB);
899    assert(SegEnd <= IP.first && "Couldn't avoid interference");
900  }
901
902  SE->closeIntv();
903
904  // FIXME: Should we be more aggressive about splitting the stack region into
905  // per-block segments? The current approach allows the stack region to
906  // separate into connected components. Some components may be allocatable.
907  SE->finish();
908  ++NumGlobalSplits;
909
910  if (VerifyEnabled) {
911    MF->verify(this, "After splitting live range around region");
912
913#ifndef NDEBUG
914    // Make sure that at least one of the new intervals can allocate to PhysReg.
915    // That was the whole point of splitting the live range.
916    bool found = false;
917    for (LiveRangeEdit::iterator I = LREdit.begin(), E = LREdit.end(); I != E;
918         ++I)
919      if (!checkUncachedInterference(**I, PhysReg)) {
920        found = true;
921        break;
922      }
923    assert(found && "No allocatable intervals after pointless splitting");
924#endif
925  }
926}
927
928unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
929                                  SmallVectorImpl<LiveInterval*> &NewVRegs) {
930  BitVector LiveBundles, BestBundles;
931  float BestCost = 0;
932  unsigned BestReg = 0;
933  Order.rewind();
934  while (unsigned PhysReg = Order.next()) {
935    float Cost = calcInterferenceInfo(VirtReg, PhysReg);
936    if (BestReg && Cost >= BestCost)
937      continue;
938
939    SpillPlacer->placeSpills(SpillConstraints, LiveBundles);
940    // No live bundles, defer to splitSingleBlocks().
941    if (!LiveBundles.any())
942      continue;
943
944    Cost += calcGlobalSplitCost(LiveBundles);
945    if (!BestReg || Cost < BestCost) {
946      BestReg = PhysReg;
947      BestCost = Cost;
948      BestBundles.swap(LiveBundles);
949    }
950  }
951
952  if (!BestReg)
953    return 0;
954
955  splitAroundRegion(VirtReg, BestReg, BestBundles, NewVRegs);
956  setStage(NewVRegs.begin(), NewVRegs.end(), RS_Region);
957  return 0;
958}
959
960
961//===----------------------------------------------------------------------===//
962//                             Local Splitting
963//===----------------------------------------------------------------------===//
964
965
966/// calcGapWeights - Compute the maximum spill weight that needs to be evicted
967/// in order to use PhysReg between two entries in SA->UseSlots.
968///
969/// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1].
970///
971void RAGreedy::calcGapWeights(unsigned PhysReg,
972                              SmallVectorImpl<float> &GapWeight) {
973  assert(SA->LiveBlocks.size() == 1 && "Not a local interval");
974  const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks.front();
975  const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots;
976  const unsigned NumGaps = Uses.size()-1;
977
978  // Start and end points for the interference check.
979  SlotIndex StartIdx = BI.LiveIn ? BI.FirstUse.getBaseIndex() : BI.FirstUse;
980  SlotIndex StopIdx = BI.LiveOut ? BI.LastUse.getBoundaryIndex() : BI.LastUse;
981
982  GapWeight.assign(NumGaps, 0.0f);
983
984  // Add interference from each overlapping register.
985  for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
986    if (!query(const_cast<LiveInterval&>(SA->getParent()), *AI)
987           .checkInterference())
988      continue;
989
990    // We know that VirtReg is a continuous interval from FirstUse to LastUse,
991    // so we don't need InterferenceQuery.
992    //
993    // Interference that overlaps an instruction is counted in both gaps
994    // surrounding the instruction. The exception is interference before
995    // StartIdx and after StopIdx.
996    //
997    LiveIntervalUnion::SegmentIter IntI = PhysReg2LiveUnion[*AI].find(StartIdx);
998    for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) {
999      // Skip the gaps before IntI.
1000      while (Uses[Gap+1].getBoundaryIndex() < IntI.start())
1001        if (++Gap == NumGaps)
1002          break;
1003      if (Gap == NumGaps)
1004        break;
1005
1006      // Update the gaps covered by IntI.
1007      const float weight = IntI.value()->weight;
1008      for (; Gap != NumGaps; ++Gap) {
1009        GapWeight[Gap] = std::max(GapWeight[Gap], weight);
1010        if (Uses[Gap+1].getBaseIndex() >= IntI.stop())
1011          break;
1012      }
1013      if (Gap == NumGaps)
1014        break;
1015    }
1016  }
1017}
1018
1019/// getPrevMappedIndex - Return the slot index of the last non-copy instruction
1020/// before MI that has a slot index. If MI is the first mapped instruction in
1021/// its block, return the block start index instead.
1022///
1023SlotIndex RAGreedy::getPrevMappedIndex(const MachineInstr *MI) {
1024  assert(MI && "Missing MachineInstr");
1025  const MachineBasicBlock *MBB = MI->getParent();
1026  MachineBasicBlock::const_iterator B = MBB->begin(), I = MI;
1027  while (I != B)
1028    if (!(--I)->isDebugValue() && !I->isCopy())
1029      return Indexes->getInstructionIndex(I);
1030  return Indexes->getMBBStartIdx(MBB);
1031}
1032
1033/// calcPrevSlots - Fill in the PrevSlot array with the index of the previous
1034/// real non-copy instruction for each instruction in SA->UseSlots.
1035///
1036void RAGreedy::calcPrevSlots() {
1037  const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots;
1038  PrevSlot.clear();
1039  PrevSlot.reserve(Uses.size());
1040  for (unsigned i = 0, e = Uses.size(); i != e; ++i) {
1041    const MachineInstr *MI = Indexes->getInstructionFromIndex(Uses[i]);
1042    PrevSlot.push_back(getPrevMappedIndex(MI).getDefIndex());
1043  }
1044}
1045
1046/// nextSplitPoint - Find the next index into SA->UseSlots > i such that it may
1047/// be beneficial to split before UseSlots[i].
1048///
1049/// 0 is always a valid split point
1050unsigned RAGreedy::nextSplitPoint(unsigned i) {
1051  const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots;
1052  const unsigned Size = Uses.size();
1053  assert(i != Size && "No split points after the end");
1054  // Allow split before i when Uses[i] is not adjacent to the previous use.
1055  while (++i != Size && PrevSlot[i].getBaseIndex() <= Uses[i-1].getBaseIndex())
1056    ;
1057  return i;
1058}
1059
1060/// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only
1061/// basic block.
1062///
1063unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order,
1064                                 SmallVectorImpl<LiveInterval*> &NewVRegs) {
1065  assert(SA->LiveBlocks.size() == 1 && "Not a local interval");
1066  const SplitAnalysis::BlockInfo &BI = SA->LiveBlocks.front();
1067
1068  // Note that it is possible to have an interval that is live-in or live-out
1069  // while only covering a single block - A phi-def can use undef values from
1070  // predecessors, and the block could be a single-block loop.
1071  // We don't bother doing anything clever about such a case, we simply assume
1072  // that the interval is continuous from FirstUse to LastUse. We should make
1073  // sure that we don't do anything illegal to such an interval, though.
1074
1075  const SmallVectorImpl<SlotIndex> &Uses = SA->UseSlots;
1076  if (Uses.size() <= 2)
1077    return 0;
1078  const unsigned NumGaps = Uses.size()-1;
1079
1080  DEBUG({
1081    dbgs() << "tryLocalSplit: ";
1082    for (unsigned i = 0, e = Uses.size(); i != e; ++i)
1083      dbgs() << ' ' << SA->UseSlots[i];
1084    dbgs() << '\n';
1085  });
1086
1087  // For every use, find the previous mapped non-copy instruction.
1088  // We use this to detect valid split points, and to estimate new interval
1089  // sizes.
1090  calcPrevSlots();
1091
1092  unsigned BestBefore = NumGaps;
1093  unsigned BestAfter = 0;
1094  float BestDiff = 0;
1095
1096  const float blockFreq = SpillPlacer->getBlockFrequency(BI.MBB->getNumber());
1097  SmallVector<float, 8> GapWeight;
1098
1099  Order.rewind();
1100  while (unsigned PhysReg = Order.next()) {
1101    // Keep track of the largest spill weight that would need to be evicted in
1102    // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1].
1103    calcGapWeights(PhysReg, GapWeight);
1104
1105    // Try to find the best sequence of gaps to close.
1106    // The new spill weight must be larger than any gap interference.
1107
1108    // We will split before Uses[SplitBefore] and after Uses[SplitAfter].
1109    unsigned SplitBefore = 0, SplitAfter = nextSplitPoint(1) - 1;
1110
1111    // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]).
1112    // It is the spill weight that needs to be evicted.
1113    float MaxGap = GapWeight[0];
1114    for (unsigned i = 1; i != SplitAfter; ++i)
1115      MaxGap = std::max(MaxGap, GapWeight[i]);
1116
1117    for (;;) {
1118      // Live before/after split?
1119      const bool LiveBefore = SplitBefore != 0 || BI.LiveIn;
1120      const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut;
1121
1122      DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' '
1123                   << Uses[SplitBefore] << '-' << Uses[SplitAfter]
1124                   << " i=" << MaxGap);
1125
1126      // Stop before the interval gets so big we wouldn't be making progress.
1127      if (!LiveBefore && !LiveAfter) {
1128        DEBUG(dbgs() << " all\n");
1129        break;
1130      }
1131      // Should the interval be extended or shrunk?
1132      bool Shrink = true;
1133      if (MaxGap < HUGE_VALF) {
1134        // Estimate the new spill weight.
1135        //
1136        // Each instruction reads and writes the register, except the first
1137        // instr doesn't read when !FirstLive, and the last instr doesn't write
1138        // when !LastLive.
1139        //
1140        // We will be inserting copies before and after, so the total number of
1141        // reads and writes is 2 * EstUses.
1142        //
1143        const unsigned EstUses = 2*(SplitAfter - SplitBefore) +
1144                                 2*(LiveBefore + LiveAfter);
1145
1146        // Try to guess the size of the new interval. This should be trivial,
1147        // but the slot index of an inserted copy can be a lot smaller than the
1148        // instruction it is inserted before if there are many dead indexes
1149        // between them.
1150        //
1151        // We measure the distance from the instruction before SplitBefore to
1152        // get a conservative estimate.
1153        //
1154        // The final distance can still be different if inserting copies
1155        // triggers a slot index renumbering.
1156        //
1157        const float EstWeight = normalizeSpillWeight(blockFreq * EstUses,
1158                              PrevSlot[SplitBefore].distance(Uses[SplitAfter]));
1159        // Would this split be possible to allocate?
1160        // Never allocate all gaps, we wouldn't be making progress.
1161        float Diff = EstWeight - MaxGap;
1162        DEBUG(dbgs() << " w=" << EstWeight << " d=" << Diff);
1163        if (Diff > 0) {
1164          Shrink = false;
1165          if (Diff > BestDiff) {
1166            DEBUG(dbgs() << " (best)");
1167            BestDiff = Diff;
1168            BestBefore = SplitBefore;
1169            BestAfter = SplitAfter;
1170          }
1171        }
1172      }
1173
1174      // Try to shrink.
1175      if (Shrink) {
1176        SplitBefore = nextSplitPoint(SplitBefore);
1177        if (SplitBefore < SplitAfter) {
1178          DEBUG(dbgs() << " shrink\n");
1179          // Recompute the max when necessary.
1180          if (GapWeight[SplitBefore - 1] >= MaxGap) {
1181            MaxGap = GapWeight[SplitBefore];
1182            for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i)
1183              MaxGap = std::max(MaxGap, GapWeight[i]);
1184          }
1185          continue;
1186        }
1187        MaxGap = 0;
1188      }
1189
1190      // Try to extend the interval.
1191      if (SplitAfter >= NumGaps) {
1192        DEBUG(dbgs() << " end\n");
1193        break;
1194      }
1195
1196      DEBUG(dbgs() << " extend\n");
1197      for (unsigned e = nextSplitPoint(SplitAfter + 1) - 1;
1198           SplitAfter != e; ++SplitAfter)
1199        MaxGap = std::max(MaxGap, GapWeight[SplitAfter]);
1200          continue;
1201    }
1202  }
1203
1204  // Didn't find any candidates?
1205  if (BestBefore == NumGaps)
1206    return 0;
1207
1208  DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore]
1209               << '-' << Uses[BestAfter] << ", " << BestDiff
1210               << ", " << (BestAfter - BestBefore + 1) << " instrs\n");
1211
1212  SmallVector<LiveInterval*, 4> SpillRegs;
1213  LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs);
1214  SE->reset(LREdit);
1215
1216  SE->openIntv();
1217  SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]);
1218  SlotIndex SegStop  = SE->leaveIntvAfter(Uses[BestAfter]);
1219  SE->useIntv(SegStart, SegStop);
1220  SE->closeIntv();
1221  SE->finish();
1222  setStage(NewVRegs.begin(), NewVRegs.end(), RS_Local);
1223  ++NumLocalSplits;
1224
1225  return 0;
1226}
1227
1228//===----------------------------------------------------------------------===//
1229//                          Live Range Splitting
1230//===----------------------------------------------------------------------===//
1231
1232/// trySplit - Try to split VirtReg or one of its interferences, making it
1233/// assignable.
1234/// @return Physreg when VirtReg may be assigned and/or new NewVRegs.
1235unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
1236                            SmallVectorImpl<LiveInterval*>&NewVRegs) {
1237  // Local intervals are handled separately.
1238  if (LIS->intervalIsInOneMBB(VirtReg)) {
1239    NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled);
1240    SA->analyze(&VirtReg);
1241    return tryLocalSplit(VirtReg, Order, NewVRegs);
1242  }
1243
1244  NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled);
1245
1246  // Don't iterate global splitting.
1247  // Move straight to spilling if this range was produced by a global split.
1248  LiveRangeStage Stage = getStage(VirtReg);
1249  if (Stage >= RS_Block)
1250    return 0;
1251
1252  SA->analyze(&VirtReg);
1253
1254  // First try to split around a region spanning multiple blocks.
1255  if (Stage < RS_Region) {
1256    unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
1257    if (PhysReg || !NewVRegs.empty())
1258      return PhysReg;
1259  }
1260
1261  // Then isolate blocks with multiple uses.
1262  if (Stage < RS_Block) {
1263    SplitAnalysis::BlockPtrSet Blocks;
1264    if (SA->getMultiUseBlocks(Blocks)) {
1265      SmallVector<LiveInterval*, 4> SpillRegs;
1266      LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs);
1267      SE->reset(LREdit);
1268      SE->splitSingleBlocks(Blocks);
1269      setStage(NewVRegs.begin(), NewVRegs.end(), RS_Block);
1270      if (VerifyEnabled)
1271        MF->verify(this, "After splitting live range around basic blocks");
1272    }
1273  }
1274
1275  // Don't assign any physregs.
1276  return 0;
1277}
1278
1279
1280//===----------------------------------------------------------------------===//
1281//                            Main Entry Point
1282//===----------------------------------------------------------------------===//
1283
1284unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
1285                                 SmallVectorImpl<LiveInterval*> &NewVRegs) {
1286  LiveRangeStage Stage = getStage(VirtReg);
1287  if (Stage == RS_Original)
1288    LRStage[VirtReg.reg] = RS_Second;
1289
1290  // First try assigning a free register.
1291  AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs);
1292  while (unsigned PhysReg = Order.next()) {
1293    if (!checkPhysRegInterference(VirtReg, PhysReg))
1294      return PhysReg;
1295  }
1296
1297  if (unsigned PhysReg = tryReassign(VirtReg, Order, NewVRegs))
1298    return PhysReg;
1299
1300  if (unsigned PhysReg = tryEvict(VirtReg, Order, NewVRegs))
1301    return PhysReg;
1302
1303  assert(NewVRegs.empty() && "Cannot append to existing NewVRegs");
1304
1305  // The first time we see a live range, don't try to split or spill.
1306  // Wait until the second time, when all smaller ranges have been allocated.
1307  // This gives a better picture of the interference to split around.
1308  if (Stage == RS_Original) {
1309    NewVRegs.push_back(&VirtReg);
1310    return 0;
1311  }
1312
1313  assert(Stage < RS_Spill && "Cannot allocate after spilling");
1314
1315  // Try splitting VirtReg or interferences.
1316  unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs);
1317  if (PhysReg || !NewVRegs.empty())
1318    return PhysReg;
1319
1320  // Finally spill VirtReg itself.
1321  NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled);
1322  SmallVector<LiveInterval*, 1> pendingSpills;
1323  spiller().spill(&VirtReg, NewVRegs, pendingSpills);
1324
1325  // The live virtual register requesting allocation was spilled, so tell
1326  // the caller not to allocate anything during this round.
1327  return 0;
1328}
1329
1330bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
1331  DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
1332               << "********** Function: "
1333               << ((Value*)mf.getFunction())->getName() << '\n');
1334
1335  MF = &mf;
1336  if (VerifyEnabled)
1337    MF->verify(this, "Before greedy register allocator");
1338
1339  RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>());
1340  Indexes = &getAnalysis<SlotIndexes>();
1341  DomTree = &getAnalysis<MachineDominatorTree>();
1342  ReservedRegs = TRI->getReservedRegs(*MF);
1343  SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
1344  Loops = &getAnalysis<MachineLoopInfo>();
1345  LoopRanges = &getAnalysis<MachineLoopRanges>();
1346  Bundles = &getAnalysis<EdgeBundles>();
1347  SpillPlacer = &getAnalysis<SpillPlacement>();
1348
1349  SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops));
1350  SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree));
1351  LRStage.clear();
1352  LRStage.resize(MRI->getNumVirtRegs());
1353
1354  allocatePhysRegs();
1355  addMBBLiveIns(MF);
1356  LIS->addKillFlags();
1357
1358  // Run rewriter
1359  {
1360    NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled);
1361    VRM->rewrite(Indexes);
1362  }
1363
1364  // The pass output is in VirtRegMap. Release all the transient data.
1365  releaseMemory();
1366
1367  return true;
1368}
1369