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