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