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