RegAllocGreedy.cpp revision 8a61da8a689ee95874c833af4c7aa965fab5c0a9 
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 "VirtRegRewriter.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
46using namespace llvm;
47
48static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator",
49                                       createGreedyRegisterAllocator);
50
51namespace {
52class RAGreedy : public MachineFunctionPass, public RegAllocBase {
53  // context
54  MachineFunction *MF;
55  BitVector ReservedRegs;
56
57  // analyses
58  SlotIndexes *Indexes;
59  LiveStacks *LS;
60  MachineDominatorTree *DomTree;
61  MachineLoopInfo *Loops;
62  MachineLoopRanges *LoopRanges;
63  EdgeBundles *Bundles;
64  SpillPlacement *SpillPlacer;
65
66  // state
67  std::auto_ptr<Spiller> SpillerInstance;
68  std::auto_ptr<SplitAnalysis> SA;
69
70  // splitting state.
71
72  /// All basic blocks where the current register is live.
73  SmallVector<SpillPlacement::BlockConstraint, 8> SpillConstraints;
74
75  /// Additional information about basic blocks where the current variable is
76  /// live. Such a block will look like one of these templates:
77  ///
78  ///  1. |   o---x   | Internal to block. Variable is only live in this block.
79  ///  2. |---x       | Live-in, kill.
80  ///  3. |       o---| Def, live-out.
81  ///  4. |---x   o---| Live-in, kill, def, live-out.
82  ///  5. |---o---o---| Live-through with uses or defs.
83  ///  6. |-----------| Live-through without uses. Transparent.
84  ///
85  struct BlockInfo {
86    MachineBasicBlock *MBB;
87    SlotIndex FirstUse;   ///< First instr using current reg.
88    SlotIndex LastUse;    ///< Last instr using current reg.
89    SlotIndex Kill;       ///< Interval end point inside block.
90    SlotIndex Def;        ///< Interval start point inside block.
91    /// Last possible point for splitting live ranges.
92    SlotIndex LastSplitPoint;
93    bool Uses;            ///< Current reg has uses or defs in block.
94    bool LiveThrough;     ///< Live in whole block (Templ 5. or 6. above).
95    bool LiveIn;          ///< Current reg is live in.
96    bool LiveOut;         ///< Current reg is live out.
97
98    // Per-interference pattern scratch data.
99    bool OverlapEntry;    ///< Interference overlaps entering interval.
100    bool OverlapExit;     ///< Interference overlaps exiting interval.
101  };
102
103  /// Basic blocks where var is live. This array is parallel to
104  /// SpillConstraints.
105  SmallVector<BlockInfo, 8> LiveBlocks;
106
107public:
108  RAGreedy();
109
110  /// Return the pass name.
111  virtual const char* getPassName() const {
112    return "Greedy Register Allocator";
113  }
114
115  /// RAGreedy analysis usage.
116  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
117
118  virtual void releaseMemory();
119
120  virtual Spiller &spiller() { return *SpillerInstance; }
121
122  virtual float getPriority(LiveInterval *LI);
123
124  virtual unsigned selectOrSplit(LiveInterval&,
125                                 SmallVectorImpl<LiveInterval*>&);
126
127  /// Perform register allocation.
128  virtual bool runOnMachineFunction(MachineFunction &mf);
129
130  static char ID;
131
132private:
133  bool checkUncachedInterference(LiveInterval&, unsigned);
134  LiveInterval *getSingleInterference(LiveInterval&, unsigned);
135  bool reassignVReg(LiveInterval &InterferingVReg, unsigned OldPhysReg);
136  bool reassignInterferences(LiveInterval &VirtReg, unsigned PhysReg);
137  float calcInterferenceWeight(LiveInterval&, unsigned);
138  void calcLiveBlockInfo(LiveInterval&);
139  float calcInterferenceInfo(LiveInterval&, unsigned);
140  float calcGlobalSplitCost(const BitVector&);
141  void splitAroundRegion(LiveInterval&, unsigned, const BitVector&,
142                         SmallVectorImpl<LiveInterval*>&);
143
144  unsigned tryReassign(LiveInterval&, AllocationOrder&);
145  unsigned tryRegionSplit(LiveInterval&, AllocationOrder&,
146                          SmallVectorImpl<LiveInterval*>&);
147  unsigned trySplit(LiveInterval&, AllocationOrder&,
148                    SmallVectorImpl<LiveInterval*>&);
149  unsigned trySpillInterferences(LiveInterval&, AllocationOrder&,
150                                 SmallVectorImpl<LiveInterval*>&);
151};
152} // end anonymous namespace
153
154char RAGreedy::ID = 0;
155
156FunctionPass* llvm::createGreedyRegisterAllocator() {
157  return new RAGreedy();
158}
159
160RAGreedy::RAGreedy(): MachineFunctionPass(ID) {
161  initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
162  initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
163  initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
164  initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
165  initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
166  initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
167  initializeLiveStacksPass(*PassRegistry::getPassRegistry());
168  initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
169  initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
170  initializeMachineLoopRangesPass(*PassRegistry::getPassRegistry());
171  initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
172  initializeEdgeBundlesPass(*PassRegistry::getPassRegistry());
173  initializeSpillPlacementPass(*PassRegistry::getPassRegistry());
174}
175
176void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
177  AU.setPreservesCFG();
178  AU.addRequired<AliasAnalysis>();
179  AU.addPreserved<AliasAnalysis>();
180  AU.addRequired<LiveIntervals>();
181  AU.addRequired<SlotIndexes>();
182  AU.addPreserved<SlotIndexes>();
183  if (StrongPHIElim)
184    AU.addRequiredID(StrongPHIEliminationID);
185  AU.addRequiredTransitive<RegisterCoalescer>();
186  AU.addRequired<CalculateSpillWeights>();
187  AU.addRequired<LiveStacks>();
188  AU.addPreserved<LiveStacks>();
189  AU.addRequired<MachineDominatorTree>();
190  AU.addPreserved<MachineDominatorTree>();
191  AU.addRequired<MachineLoopInfo>();
192  AU.addPreserved<MachineLoopInfo>();
193  AU.addRequired<MachineLoopRanges>();
194  AU.addPreserved<MachineLoopRanges>();
195  AU.addRequired<VirtRegMap>();
196  AU.addPreserved<VirtRegMap>();
197  AU.addRequired<EdgeBundles>();
198  AU.addRequired<SpillPlacement>();
199  MachineFunctionPass::getAnalysisUsage(AU);
200}
201
202void RAGreedy::releaseMemory() {
203  SpillerInstance.reset(0);
204  RegAllocBase::releaseMemory();
205}
206
207float RAGreedy::getPriority(LiveInterval *LI) {
208  float Priority = LI->weight;
209
210  // Prioritize hinted registers so they are allocated first.
211  std::pair<unsigned, unsigned> Hint;
212  if (Hint.first || Hint.second) {
213    // The hint can be target specific, a virtual register, or a physreg.
214    Priority *= 2;
215
216    // Prefer physreg hints above anything else.
217    if (Hint.first == 0 && TargetRegisterInfo::isPhysicalRegister(Hint.second))
218      Priority *= 2;
219  }
220  return Priority;
221}
222
223
224//===----------------------------------------------------------------------===//
225//                         Register Reassignment
226//===----------------------------------------------------------------------===//
227
228// Check interference without using the cache.
229bool RAGreedy::checkUncachedInterference(LiveInterval &VirtReg,
230                                         unsigned PhysReg) {
231  for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
232    LiveIntervalUnion::Query subQ(&VirtReg, &PhysReg2LiveUnion[*AliasI]);
233    if (subQ.checkInterference())
234      return true;
235  }
236  return false;
237}
238
239/// getSingleInterference - Return the single interfering virtual register
240/// assigned to PhysReg. Return 0 if more than one virtual register is
241/// interfering.
242LiveInterval *RAGreedy::getSingleInterference(LiveInterval &VirtReg,
243                                              unsigned PhysReg) {
244  // Check physreg and aliases.
245  LiveInterval *Interference = 0;
246  for (const unsigned *AliasI = TRI->getOverlaps(PhysReg); *AliasI; ++AliasI) {
247    LiveIntervalUnion::Query &Q = query(VirtReg, *AliasI);
248    if (Q.checkInterference()) {
249      if (Interference)
250        return 0;
251      Q.collectInterferingVRegs(1);
252      if (!Q.seenAllInterferences())
253        return 0;
254      Interference = Q.interferingVRegs().front();
255    }
256  }
257  return Interference;
258}
259
260// Attempt to reassign this virtual register to a different physical register.
261//
262// FIXME: we are not yet caching these "second-level" interferences discovered
263// in the sub-queries. These interferences can change with each call to
264// selectOrSplit. However, we could implement a "may-interfere" cache that
265// could be conservatively dirtied when we reassign or split.
266//
267// FIXME: This may result in a lot of alias queries. We could summarize alias
268// live intervals in their parent register's live union, but it's messy.
269bool RAGreedy::reassignVReg(LiveInterval &InterferingVReg,
270                            unsigned WantedPhysReg) {
271  assert(TargetRegisterInfo::isVirtualRegister(InterferingVReg.reg) &&
272         "Can only reassign virtual registers");
273  assert(TRI->regsOverlap(WantedPhysReg, VRM->getPhys(InterferingVReg.reg)) &&
274         "inconsistent phys reg assigment");
275
276  AllocationOrder Order(InterferingVReg.reg, *VRM, ReservedRegs);
277  while (unsigned PhysReg = Order.next()) {
278    // Don't reassign to a WantedPhysReg alias.
279    if (TRI->regsOverlap(PhysReg, WantedPhysReg))
280      continue;
281
282    if (checkUncachedInterference(InterferingVReg, PhysReg))
283      continue;
284
285    // Reassign the interfering virtual reg to this physical reg.
286    unsigned OldAssign = VRM->getPhys(InterferingVReg.reg);
287    DEBUG(dbgs() << "reassigning: " << InterferingVReg << " from " <<
288          TRI->getName(OldAssign) << " to " << TRI->getName(PhysReg) << '\n');
289    PhysReg2LiveUnion[OldAssign].extract(InterferingVReg);
290    VRM->clearVirt(InterferingVReg.reg);
291    VRM->assignVirt2Phys(InterferingVReg.reg, PhysReg);
292    PhysReg2LiveUnion[PhysReg].unify(InterferingVReg);
293
294    return true;
295  }
296  return false;
297}
298
299/// reassignInterferences - Reassign all interferences to different physical
300/// registers such that Virtreg can be assigned to PhysReg.
301/// Currently this only works with a single interference.
302/// @param  VirtReg Currently unassigned virtual register.
303/// @param  PhysReg Physical register to be cleared.
304/// @return True on success, false if nothing was changed.
305bool RAGreedy::reassignInterferences(LiveInterval &VirtReg, unsigned PhysReg) {
306  LiveInterval *InterferingVReg = getSingleInterference(VirtReg, PhysReg);
307  if (!InterferingVReg)
308    return false;
309  if (TargetRegisterInfo::isPhysicalRegister(InterferingVReg->reg))
310    return false;
311  return reassignVReg(*InterferingVReg, PhysReg);
312}
313
314/// tryReassign - Try to reassign interferences to different physregs.
315/// @param  VirtReg Currently unassigned virtual register.
316/// @param  Order   Physregs to try.
317/// @return         Physreg to assign VirtReg, or 0.
318unsigned RAGreedy::tryReassign(LiveInterval &VirtReg, AllocationOrder &Order) {
319  NamedRegionTimer T("Reassign", TimerGroupName, TimePassesIsEnabled);
320  Order.rewind();
321  while (unsigned PhysReg = Order.next())
322    if (reassignInterferences(VirtReg, PhysReg))
323      return PhysReg;
324  return 0;
325}
326
327
328//===----------------------------------------------------------------------===//
329//                              Region Splitting
330//===----------------------------------------------------------------------===//
331
332/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
333/// where VirtReg is live.
334/// The SpillConstraints array is minimally initialized with MBB->getNumber().
335void RAGreedy::calcLiveBlockInfo(LiveInterval &VirtReg) {
336  LiveBlocks.clear();
337  SpillConstraints.clear();
338
339  assert(!VirtReg.empty() && "Cannot allocate an empty interval");
340  LiveInterval::const_iterator LVI = VirtReg.begin();
341  LiveInterval::const_iterator LVE = VirtReg.end();
342
343  SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE;
344  UseI = SA->UseSlots.begin();
345  UseE = SA->UseSlots.end();
346
347  // Loop over basic blocks where VirtReg is live.
348  MachineFunction::iterator MFI = Indexes->getMBBFromIndex(LVI->start);
349  for (;;) {
350    // Block constraints depend on the interference pattern.
351    // Just allocate them here, don't compute anything.
352    SpillPlacement::BlockConstraint BC;
353    BC.Number = MFI->getNumber();
354    SpillConstraints.push_back(BC);
355
356    BlockInfo BI;
357    BI.MBB = MFI;
358    SlotIndex Start, Stop;
359    tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
360
361    // The last split point is the latest possible insertion point that dominates
362    // all successor blocks. If interference reaches LastSplitPoint, it is not
363    // possible to insert a split or reload that makes VirtReg live in the
364    // outgoing bundle.
365    MachineBasicBlock::iterator LSP = LIS->getLastSplitPoint(VirtReg, BI.MBB);
366    if (LSP == BI.MBB->end())
367      BI.LastSplitPoint = Stop;
368    else
369      BI.LastSplitPoint = Indexes->getInstructionIndex(LSP);
370
371    // LVI is the first live segment overlapping MBB.
372    BI.LiveIn = LVI->start <= Start;
373    if (!BI.LiveIn)
374      BI.Def = LVI->start;
375
376    // Find the first and last uses in the block.
377    BI.Uses = SA->hasUses(MFI);
378    if (BI.Uses && UseI != UseE) {
379      BI.FirstUse = *UseI;
380      assert(BI.FirstUse >= Start);
381      do ++UseI;
382      while (UseI != UseE && *UseI < Stop);
383      BI.LastUse = UseI[-1];
384      assert(BI.LastUse < Stop);
385    }
386
387    // Look for gaps in the live range.
388    bool hasGap = false;
389    BI.LiveOut = true;
390    while (LVI->end < Stop) {
391      SlotIndex LastStop = LVI->end;
392      if (++LVI == LVE || LVI->start >= Stop) {
393        BI.Kill = LastStop;
394        BI.LiveOut = false;
395        break;
396      }
397      if (LastStop < LVI->start) {
398        hasGap = true;
399        BI.Kill = LastStop;
400        BI.Def = LVI->start;
401      }
402    }
403
404    // Don't set LiveThrough when the block has a gap.
405    BI.LiveThrough = !hasGap && BI.LiveIn && BI.LiveOut;
406    LiveBlocks.push_back(BI);
407
408    // LVI is now at LVE or LVI->end >= Stop.
409    if (LVI == LVE)
410      break;
411
412    // Live segment ends exactly at Stop. Move to the next segment.
413    if (LVI->end == Stop && ++LVI == LVE)
414      break;
415
416    // Pick the next basic block.
417    if (LVI->start < Stop)
418      ++MFI;
419    else
420      MFI = Indexes->getMBBFromIndex(LVI->start);
421  }
422}
423
424/// calcInterferenceInfo - Compute per-block outgoing and ingoing constraints
425/// when considering interference from PhysReg. Also compute an optimistic local
426/// cost of this interference pattern.
427///
428/// The final cost of a split is the local cost + global cost of preferences
429/// broken by SpillPlacement.
430///
431float RAGreedy::calcInterferenceInfo(LiveInterval &VirtReg, unsigned PhysReg) {
432  // Reset interference dependent info.
433  for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
434    BlockInfo &BI = LiveBlocks[i];
435    SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
436    BC.Entry = (BI.Uses && BI.LiveIn) ?
437      SpillPlacement::PrefReg : SpillPlacement::DontCare;
438    BC.Exit = (BI.Uses && BI.LiveOut) ?
439      SpillPlacement::PrefReg : SpillPlacement::DontCare;
440    BI.OverlapEntry = BI.OverlapExit = false;
441  }
442
443  // Add interference info from each PhysReg alias.
444  for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
445    if (!query(VirtReg, *AI).checkInterference())
446      continue;
447    LiveIntervalUnion::SegmentIter IntI =
448      PhysReg2LiveUnion[*AI].find(VirtReg.beginIndex());
449    if (!IntI.valid())
450      continue;
451
452    for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
453      BlockInfo &BI = LiveBlocks[i];
454      SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
455      SlotIndex Start, Stop;
456      tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
457
458      // Skip interference-free blocks.
459      if (IntI.start() >= Stop)
460        continue;
461
462      // Handle transparent blocks with interference separately.
463      // Transparent blocks never incur any fixed cost.
464      if (BI.LiveThrough && !BI.Uses) {
465        // Check if interference is live-in - force spill.
466        if (BC.Entry != SpillPlacement::MustSpill) {
467          BC.Entry = SpillPlacement::PrefSpill;
468          IntI.advanceTo(Start);
469          if (IntI.valid() && IntI.start() <= Start)
470            BC.Entry = SpillPlacement::MustSpill;
471        }
472
473        // Check if interference is live-out - force spill.
474        if (BC.Exit != SpillPlacement::MustSpill) {
475          BC.Exit = SpillPlacement::PrefSpill;
476          // Any interference overlapping [LastSplitPoint;Stop) forces a spill.
477          IntI.advanceTo(BI.LastSplitPoint.getPrevSlot());
478          if (IntI.valid() && IntI.start() < Stop)
479            BC.Exit = SpillPlacement::MustSpill;
480        }
481
482        // Nothing more to do for this transparent block.
483        if (!IntI.valid())
484          break;
485        continue;
486      }
487
488      // Now we only have blocks with uses left.
489      // Check if the interference overlaps the uses.
490      assert(BI.Uses && "Non-transparent block without any uses");
491
492      // Check interference on entry.
493      if (BI.LiveIn && BC.Entry != SpillPlacement::MustSpill) {
494        IntI.advanceTo(Start);
495        if (!IntI.valid())
496          break;
497
498        // Interference is live-in - force spill.
499        if (IntI.start() <= Start)
500          BC.Entry = SpillPlacement::MustSpill;
501        // Not live in, but before the first use.
502        else if (IntI.start() < BI.FirstUse)
503          BC.Entry = SpillPlacement::PrefSpill;
504      }
505
506      // Does interference overlap the uses in the entry segment
507      // [FirstUse;Kill)?
508      if (BI.LiveIn && !BI.OverlapEntry) {
509        IntI.advanceTo(BI.FirstUse);
510        if (!IntI.valid())
511          break;
512        // A live-through interval has no kill.
513        // Check [FirstUse;LastUse) instead.
514        if (IntI.start() < (BI.LiveThrough ? BI.LastUse : BI.Kill))
515          BI.OverlapEntry = true;
516      }
517
518      // Does interference overlap the uses in the exit segment [Def;LastUse)?
519      if (BI.LiveOut && !BI.LiveThrough && !BI.OverlapExit) {
520        IntI.advanceTo(BI.Def);
521        if (!IntI.valid())
522          break;
523        if (IntI.start() < BI.LastUse)
524          BI.OverlapExit = true;
525      }
526
527      // Check interference on exit.
528      if (BI.LiveOut && BC.Exit != SpillPlacement::MustSpill) {
529        // Check interference between LastUse and Stop.
530        if (BC.Exit != SpillPlacement::PrefSpill) {
531          IntI.advanceTo(BI.LastUse);
532          if (!IntI.valid())
533            break;
534          if (IntI.start() < Stop)
535            BC.Exit = SpillPlacement::PrefSpill;
536        }
537        // Is the interference overlapping the last split point?
538        IntI.advanceTo(BI.LastSplitPoint.getPrevSlot());
539        if (!IntI.valid())
540          break;
541        if (IntI.start() < Stop)
542          BC.Exit = SpillPlacement::MustSpill;
543      }
544    }
545  }
546
547  // Accumulate a local cost of this interference pattern.
548  float LocalCost = 0;
549  for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
550    BlockInfo &BI = LiveBlocks[i];
551    if (!BI.Uses)
552      continue;
553    SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
554    unsigned Inserts = 0;
555
556    // Do we need spill code for the entry segment?
557    if (BI.LiveIn)
558      Inserts += BI.OverlapEntry || BC.Entry != SpillPlacement::PrefReg;
559
560    // For the exit segment?
561    if (BI.LiveOut)
562      Inserts += BI.OverlapExit || BC.Exit != SpillPlacement::PrefReg;
563
564    // The local cost of spill code in this block is the block frequency times
565    // the number of spill instructions inserted.
566    if (Inserts)
567      LocalCost += Inserts * SpillPlacer->getBlockFrequency(BI.MBB);
568  }
569  DEBUG(dbgs() << "Local cost of " << PrintReg(PhysReg, TRI) << " = "
570               << LocalCost << '\n');
571  return LocalCost;
572}
573
574/// calcGlobalSplitCost - Return the global split cost of following the split
575/// pattern in LiveBundles. This cost should be added to the local cost of the
576/// interference pattern in SpillConstraints.
577///
578float RAGreedy::calcGlobalSplitCost(const BitVector &LiveBundles) {
579  float GlobalCost = 0;
580  for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
581    SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
582    unsigned Inserts = 0;
583    // Broken entry preference?
584    Inserts += LiveBundles[Bundles->getBundle(BC.Number, 0)] !=
585                 (BC.Entry == SpillPlacement::PrefReg);
586    // Broken exit preference?
587    Inserts += LiveBundles[Bundles->getBundle(BC.Number, 1)] !=
588                 (BC.Exit == SpillPlacement::PrefReg);
589    if (Inserts)
590      GlobalCost += Inserts * SpillPlacer->getBlockFrequency(LiveBlocks[i].MBB);
591  }
592  DEBUG(dbgs() << "Global cost = " << GlobalCost << '\n');
593  return GlobalCost;
594}
595
596/// splitAroundRegion - Split VirtReg around the region determined by
597/// LiveBundles. Make an effort to avoid interference from PhysReg.
598///
599/// The 'register' interval is going to contain as many uses as possible while
600/// avoiding interference. The 'stack' interval is the complement constructed by
601/// SplitEditor. It will contain the rest.
602///
603void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
604                                 const BitVector &LiveBundles,
605                                 SmallVectorImpl<LiveInterval*> &NewVRegs) {
606  DEBUG({
607    dbgs() << "Splitting around region for " << PrintReg(PhysReg, TRI)
608           << " with bundles";
609    for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i))
610      dbgs() << " EB#" << i;
611    dbgs() << ".\n";
612  });
613
614  // First compute interference ranges in the live blocks.
615  typedef std::pair<SlotIndex, SlotIndex> IndexPair;
616  SmallVector<IndexPair, 8> InterferenceRanges;
617  InterferenceRanges.resize(LiveBlocks.size());
618  for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
619    if (!query(VirtReg, *AI).checkInterference())
620      continue;
621    LiveIntervalUnion::SegmentIter IntI =
622      PhysReg2LiveUnion[*AI].find(VirtReg.beginIndex());
623    if (!IntI.valid())
624      continue;
625    for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
626      const BlockInfo &BI = LiveBlocks[i];
627      IndexPair &IP = InterferenceRanges[i];
628      SlotIndex Start, Stop;
629      tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
630      // Skip interference-free blocks.
631      if (IntI.start() >= Stop)
632        continue;
633
634      // First interference in block.
635      if (BI.LiveIn) {
636        IntI.advanceTo(Start);
637        if (!IntI.valid())
638          break;
639        if (IntI.start() >= Stop)
640          continue;
641        if (!IP.first.isValid() || IntI.start() < IP.first)
642          IP.first = IntI.start();
643      }
644
645      // Last interference in block.
646      if (BI.LiveOut) {
647        IntI.advanceTo(Stop);
648        if (!IntI.valid() || IntI.start() >= Stop)
649          --IntI;
650        if (IntI.stop() <= Start)
651          continue;
652        if (!IP.second.isValid() || IntI.stop() > IP.second)
653          IP.second = IntI.stop();
654      }
655    }
656  }
657
658  SmallVector<LiveInterval*, 4> SpillRegs;
659  LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs);
660  SplitEditor SE(*SA, *LIS, *VRM, *DomTree, LREdit);
661
662  // Create the main cross-block interval.
663  SE.openIntv();
664
665  // First add all defs that are live out of a block.
666  for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
667    BlockInfo &BI = LiveBlocks[i];
668    bool RegIn  = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
669    bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
670
671    // Should the register be live out?
672    if (!BI.LiveOut || !RegOut)
673      continue;
674
675    IndexPair &IP = InterferenceRanges[i];
676    SlotIndex Start, Stop;
677    tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
678
679    DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#"
680                 << Bundles->getBundle(BI.MBB->getNumber(), 1)
681                 << " intf [" << IP.first << ';' << IP.second << ')');
682
683    // The interference interval should either be invalid or overlap MBB.
684    assert((!IP.first.isValid() || IP.first < Stop) && "Bad interference");
685    assert((!IP.second.isValid() || IP.second > Start) && "Bad interference");
686
687    // Check interference leaving the block.
688    if (!IP.second.isValid()) {
689      // Block is interference-free.
690      DEBUG(dbgs() << ", no interference");
691      if (!BI.Uses) {
692        assert(BI.LiveThrough && "No uses, but not live through block?");
693        // Block is live-through without interference.
694        DEBUG(dbgs() << ", no uses"
695                     << (RegIn ? ", live-through.\n" : ", stack in.\n"));
696        if (!RegIn)
697          SE.enterIntvAtEnd(*BI.MBB);
698        continue;
699      }
700      if (!BI.LiveThrough) {
701        DEBUG(dbgs() << ", not live-through.\n");
702        SE.useIntv(SE.enterIntvBefore(BI.Def), Stop);
703        continue;
704      }
705      if (!RegIn) {
706        // Block is live-through, but entry bundle is on the stack.
707        // Reload just before the first use.
708        DEBUG(dbgs() << ", not live-in, enter before first use.\n");
709        SE.useIntv(SE.enterIntvBefore(BI.FirstUse), Stop);
710        continue;
711      }
712      DEBUG(dbgs() << ", live-through.\n");
713      continue;
714    }
715
716    // Block has interference.
717    DEBUG(dbgs() << ", interference to " << IP.second);
718
719    if (!BI.LiveThrough && IP.second <= BI.Def) {
720      // The interference doesn't reach the outgoing segment.
721      DEBUG(dbgs() << " doesn't affect def from " << BI.Def << '\n');
722      SE.useIntv(BI.Def, Stop);
723      continue;
724    }
725
726
727    if (!BI.Uses) {
728      // No uses in block, avoid interference by reloading as late as possible.
729      DEBUG(dbgs() << ", no uses.\n");
730      SlotIndex SegStart = SE.enterIntvAtEnd(*BI.MBB);
731      assert(SegStart >= IP.second && "Couldn't avoid interference");
732      continue;
733    }
734
735    if (IP.second.getBoundaryIndex() < BI.LastUse &&
736        IP.second.getBoundaryIndex() <= BI.LastSplitPoint) {
737      // There are interference-free uses at the end of the block.
738      // Find the first use that can get the live-out register.
739      SmallVectorImpl<SlotIndex>::const_iterator UI =
740        std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(),
741                         IP.second.getBoundaryIndex());
742      assert(UI != SA->UseSlots.end() && "Couldn't find last use");
743      SlotIndex Use = *UI;
744      DEBUG(dbgs() << ", free use at " << Use << ".\n");
745      assert(Use <= BI.LastUse && "Couldn't find last use");
746      SlotIndex SegStart = SE.enterIntvBefore(Use);
747      assert(SegStart >= IP.second && "Couldn't avoid interference");
748      assert(SegStart < BI.LastSplitPoint && "Impossible split point");
749      SE.useIntv(SegStart, Stop);
750      continue;
751    }
752
753    // Interference is after the last use.
754    DEBUG(dbgs() << " after last use.\n");
755    SlotIndex SegStart = SE.enterIntvAtEnd(*BI.MBB);
756    assert(SegStart >= IP.second && "Couldn't avoid interference");
757  }
758
759  // Now all defs leading to live bundles are handled, do everything else.
760  for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
761    BlockInfo &BI = LiveBlocks[i];
762    bool RegIn  = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
763    bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
764
765    // Is the register live-in?
766    if (!BI.LiveIn || !RegIn)
767      continue;
768
769    // We have an incoming register. Check for interference.
770    IndexPair &IP = InterferenceRanges[i];
771    SlotIndex Start, Stop;
772    tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
773
774    DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0)
775                 << " -> BB#" << BI.MBB->getNumber());
776
777    // Check interference entering the block.
778    if (!IP.first.isValid()) {
779      // Block is interference-free.
780      DEBUG(dbgs() << ", no interference");
781      if (!BI.Uses) {
782        assert(BI.LiveThrough && "No uses, but not live through block?");
783        // Block is live-through without interference.
784        if (RegOut) {
785          DEBUG(dbgs() << ", no uses, live-through.\n");
786          SE.useIntv(Start, Stop);
787        } else {
788          DEBUG(dbgs() << ", no uses, stack-out.\n");
789          SE.leaveIntvAtTop(*BI.MBB);
790        }
791        continue;
792      }
793      if (!BI.LiveThrough) {
794        DEBUG(dbgs() << ", killed in block.\n");
795        SE.useIntv(Start, SE.leaveIntvAfter(BI.Kill));
796        continue;
797      }
798      if (!RegOut) {
799        // Block is live-through, but exit bundle is on the stack.
800        // Spill immediately after the last use.
801        if (BI.LastUse < BI.LastSplitPoint) {
802          DEBUG(dbgs() << ", uses, stack-out.\n");
803          SE.useIntv(Start, SE.leaveIntvAfter(BI.LastUse));
804          continue;
805        }
806        // The last use is after the last split point, it is probably an
807        // indirect jump.
808        DEBUG(dbgs() << ", uses at " << BI.LastUse << " after split point "
809                     << BI.LastSplitPoint << ", stack-out.\n");
810        SlotIndex SegEnd;
811        if (BI.LastSplitPoint == Start)
812          SegEnd = SE.leaveIntvAtTop(*BI.MBB);
813        else {
814          MachineBasicBlock::iterator I =
815            LIS->getInstructionFromIndex(BI.LastSplitPoint);
816          do assert(I != BI.MBB->begin() && "Expected instruction");
817          while ((--I)->isDebugValue());
818          SegEnd = SE.leaveIntvAfter(LIS->getInstructionIndex(I));
819        }
820        SE.useIntv(Start, SegEnd);
821        // Run a double interval from the split to the last use.
822        // This makes it possible to spill the complement without affecting the
823        // indirect branch.
824        SE.overlapIntv(SegEnd, BI.LastUse);
825        continue;
826      }
827      // Register is live-through.
828      DEBUG(dbgs() << ", uses, live-through.\n");
829      SE.useIntv(Start, Stop);
830      continue;
831    }
832
833    // Block has interference.
834    DEBUG(dbgs() << ", interference from " << IP.first);
835
836    if (!BI.LiveThrough && IP.first >= BI.Kill) {
837      // The interference doesn't reach the outgoing segment.
838      DEBUG(dbgs() << " doesn't affect kill at " << BI.Kill << '\n');
839      SE.useIntv(Start, BI.Kill);
840      continue;
841    }
842
843    if (!BI.Uses) {
844      // No uses in block, avoid interference by spilling as soon as possible.
845      DEBUG(dbgs() << ", no uses.\n");
846      SlotIndex SegEnd = SE.leaveIntvAtTop(*BI.MBB);
847      assert(SegEnd <= IP.first && "Couldn't avoid interference");
848      continue;
849    }
850    if (IP.first.getBaseIndex() > BI.FirstUse) {
851      // There are interference-free uses at the beginning of the block.
852      // Find the last use that can get the register.
853      SmallVectorImpl<SlotIndex>::const_iterator UI =
854        std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(),
855                         IP.first.getBaseIndex());
856      assert(UI != SA->UseSlots.begin() && "Couldn't find first use");
857      SlotIndex Use = (--UI)->getBoundaryIndex();
858      DEBUG(dbgs() << ", free use at " << *UI << ".\n");
859      SlotIndex SegEnd = SE.leaveIntvAfter(Use);
860      assert(SegEnd <= IP.first && "Couldn't avoid interference");
861      SE.useIntv(Start, SegEnd);
862      continue;
863    }
864
865    // Interference is before the first use.
866    DEBUG(dbgs() << " before first use.\n");
867    SlotIndex SegEnd = SE.leaveIntvAtTop(*BI.MBB);
868    assert(SegEnd <= IP.first && "Couldn't avoid interference");
869  }
870
871  SE.closeIntv();
872
873  // FIXME: Should we be more aggressive about splitting the stack region into
874  // per-block segments? The current approach allows the stack region to
875  // separate into connected components. Some components may be allocatable.
876  SE.finish();
877
878  if (VerifyEnabled) {
879    MF->verify(this, "After splitting live range around region");
880
881#ifndef NDEBUG
882    // Make sure that at least one of the new intervals can allocate to PhysReg.
883    // That was the whole point of splitting the live range.
884    bool found = false;
885    for (LiveRangeEdit::iterator I = LREdit.begin(), E = LREdit.end(); I != E;
886         ++I)
887      if (!checkUncachedInterference(**I, PhysReg)) {
888        found = true;
889        break;
890      }
891    assert(found && "No allocatable intervals after pointless splitting");
892#endif
893  }
894}
895
896unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
897                                  SmallVectorImpl<LiveInterval*> &NewVRegs) {
898  calcLiveBlockInfo(VirtReg);
899  BitVector LiveBundles, BestBundles;
900  float BestCost = 0;
901  unsigned BestReg = 0;
902  Order.rewind();
903  while (unsigned PhysReg = Order.next()) {
904    float Cost = calcInterferenceInfo(VirtReg, PhysReg);
905    if (BestReg && Cost >= BestCost)
906      continue;
907
908    SpillPlacer->placeSpills(SpillConstraints, LiveBundles);
909    // No live bundles, defer to splitSingleBlocks().
910    if (!LiveBundles.any())
911      continue;
912
913    Cost += calcGlobalSplitCost(LiveBundles);
914    if (!BestReg || Cost < BestCost) {
915      BestReg = PhysReg;
916      BestCost = Cost;
917      BestBundles.swap(LiveBundles);
918    }
919  }
920
921  if (!BestReg)
922    return 0;
923
924  splitAroundRegion(VirtReg, BestReg, BestBundles, NewVRegs);
925  return 0;
926}
927
928
929//===----------------------------------------------------------------------===//
930//                          Live Range Splitting
931//===----------------------------------------------------------------------===//
932
933/// trySplit - Try to split VirtReg or one of its interferences, making it
934/// assignable.
935/// @return Physreg when VirtReg may be assigned and/or new NewVRegs.
936unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
937                            SmallVectorImpl<LiveInterval*>&NewVRegs) {
938  NamedRegionTimer T("Splitter", TimerGroupName, TimePassesIsEnabled);
939  SA->analyze(&VirtReg);
940
941  // Don't attempt splitting on local intervals for now. TBD.
942  if (LIS->intervalIsInOneMBB(VirtReg))
943    return 0;
944
945  // First try to split around a region spanning multiple blocks.
946  unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
947  if (PhysReg || !NewVRegs.empty())
948    return PhysReg;
949
950  // Then isolate blocks with multiple uses.
951  SplitAnalysis::BlockPtrSet Blocks;
952  if (SA->getMultiUseBlocks(Blocks)) {
953    SmallVector<LiveInterval*, 4> SpillRegs;
954    LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs);
955    SplitEditor(*SA, *LIS, *VRM, *DomTree, LREdit).splitSingleBlocks(Blocks);
956    if (VerifyEnabled)
957      MF->verify(this, "After splitting live range around basic blocks");
958  }
959
960  // Don't assign any physregs.
961  return 0;
962}
963
964
965//===----------------------------------------------------------------------===//
966//                                Spilling
967//===----------------------------------------------------------------------===//
968
969/// calcInterferenceWeight - Calculate the combined spill weight of
970/// interferences when assigning VirtReg to PhysReg.
971float RAGreedy::calcInterferenceWeight(LiveInterval &VirtReg, unsigned PhysReg){
972  float Sum = 0;
973  for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
974    LiveIntervalUnion::Query &Q = query(VirtReg, *AI);
975    Q.collectInterferingVRegs();
976    if (Q.seenUnspillableVReg())
977      return HUGE_VALF;
978    for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i)
979      Sum += Q.interferingVRegs()[i]->weight;
980  }
981  return Sum;
982}
983
984/// trySpillInterferences - Try to spill interfering registers instead of the
985/// current one. Only do it if the accumulated spill weight is smaller than the
986/// current spill weight.
987unsigned RAGreedy::trySpillInterferences(LiveInterval &VirtReg,
988                                         AllocationOrder &Order,
989                                     SmallVectorImpl<LiveInterval*> &NewVRegs) {
990  NamedRegionTimer T("Spill Interference", TimerGroupName, TimePassesIsEnabled);
991  unsigned BestPhys = 0;
992  float BestWeight = 0;
993
994  Order.rewind();
995  while (unsigned PhysReg = Order.next()) {
996    float Weight = calcInterferenceWeight(VirtReg, PhysReg);
997    if (Weight == HUGE_VALF || Weight >= VirtReg.weight)
998      continue;
999    if (!BestPhys || Weight < BestWeight)
1000      BestPhys = PhysReg, BestWeight = Weight;
1001  }
1002
1003  // No candidates found.
1004  if (!BestPhys)
1005    return 0;
1006
1007  // Collect all interfering registers.
1008  SmallVector<LiveInterval*, 8> Spills;
1009  for (const unsigned *AI = TRI->getOverlaps(BestPhys); *AI; ++AI) {
1010    LiveIntervalUnion::Query &Q = query(VirtReg, *AI);
1011    Spills.append(Q.interferingVRegs().begin(), Q.interferingVRegs().end());
1012    for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) {
1013      LiveInterval *VReg = Q.interferingVRegs()[i];
1014      PhysReg2LiveUnion[*AI].extract(*VReg);
1015      VRM->clearVirt(VReg->reg);
1016    }
1017  }
1018
1019  // Spill them all.
1020  DEBUG(dbgs() << "spilling " << Spills.size() << " interferences with weight "
1021               << BestWeight << '\n');
1022  for (unsigned i = 0, e = Spills.size(); i != e; ++i)
1023    spiller().spill(Spills[i], NewVRegs, Spills);
1024  return BestPhys;
1025}
1026
1027
1028//===----------------------------------------------------------------------===//
1029//                            Main Entry Point
1030//===----------------------------------------------------------------------===//
1031
1032unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
1033                                 SmallVectorImpl<LiveInterval*> &NewVRegs) {
1034  // First try assigning a free register.
1035  AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs);
1036  while (unsigned PhysReg = Order.next()) {
1037    if (!checkPhysRegInterference(VirtReg, PhysReg))
1038      return PhysReg;
1039  }
1040
1041  // Try to reassign interferences.
1042  if (unsigned PhysReg = tryReassign(VirtReg, Order))
1043    return PhysReg;
1044
1045  assert(NewVRegs.empty() && "Cannot append to existing NewVRegs");
1046
1047  // Try splitting VirtReg or interferences.
1048  unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs);
1049  if (PhysReg || !NewVRegs.empty())
1050    return PhysReg;
1051
1052  // Try to spill another interfering reg with less spill weight.
1053  PhysReg = trySpillInterferences(VirtReg, Order, NewVRegs);
1054  if (PhysReg)
1055    return PhysReg;
1056
1057  // Finally spill VirtReg itself.
1058  NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled);
1059  SmallVector<LiveInterval*, 1> pendingSpills;
1060  spiller().spill(&VirtReg, NewVRegs, pendingSpills);
1061
1062  // The live virtual register requesting allocation was spilled, so tell
1063  // the caller not to allocate anything during this round.
1064  return 0;
1065}
1066
1067bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
1068  DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
1069               << "********** Function: "
1070               << ((Value*)mf.getFunction())->getName() << '\n');
1071
1072  MF = &mf;
1073  if (VerifyEnabled)
1074    MF->verify(this, "Before greedy register allocator");
1075
1076  RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>());
1077  Indexes = &getAnalysis<SlotIndexes>();
1078  DomTree = &getAnalysis<MachineDominatorTree>();
1079  ReservedRegs = TRI->getReservedRegs(*MF);
1080  SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
1081  Loops = &getAnalysis<MachineLoopInfo>();
1082  LoopRanges = &getAnalysis<MachineLoopRanges>();
1083  Bundles = &getAnalysis<EdgeBundles>();
1084  SpillPlacer = &getAnalysis<SpillPlacement>();
1085
1086  SA.reset(new SplitAnalysis(*MF, *LIS, *Loops));
1087
1088  allocatePhysRegs();
1089  addMBBLiveIns(MF);
1090  LIS->addKillFlags();
1091
1092  // Run rewriter
1093  {
1094    NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled);
1095    std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
1096    rewriter->runOnMachineFunction(*MF, *VRM, LIS);
1097  }
1098
1099  // The pass output is in VirtRegMap. Release all the transient data.
1100  releaseMemory();
1101
1102  return true;
1103}
1104