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