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