RegAllocGreedy.cpp revision 2710638db2eb84cd7eefb8bb9a1b7e5c49413d45 
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  float calcInterferenceWeight(LiveInterval&, unsigned);
137  void calcLiveBlockInfo(LiveInterval&);
138  float calcInterferenceInfo(LiveInterval&, unsigned);
139  float calcGlobalSplitCost(const BitVector&);
140  void splitAroundRegion(LiveInterval&, unsigned, const BitVector&,
141                         SmallVectorImpl<LiveInterval*>&);
142
143  unsigned tryReassignOrEvict(LiveInterval&, AllocationOrder&,
144                              SmallVectorImpl<LiveInterval*>&);
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    unassign(InterferingVReg, OldAssign);
290    assign(InterferingVReg, PhysReg);
291    return true;
292  }
293  return false;
294}
295
296/// tryReassignOrEvict - Try to reassign a single interferences to a different
297/// physreg, or evict a single interference with a lower spill weight.
298/// @param  VirtReg Currently unassigned virtual register.
299/// @param  Order   Physregs to try.
300/// @return         Physreg to assign VirtReg, or 0.
301unsigned RAGreedy::tryReassignOrEvict(LiveInterval &VirtReg,
302                                      AllocationOrder &Order,
303                                      SmallVectorImpl<LiveInterval*> &NewVRegs){
304  NamedRegionTimer T("Reassign", TimerGroupName, TimePassesIsEnabled);
305
306  // Keep track of the lightest single interference seen so far.
307  float BestWeight = VirtReg.weight;
308  LiveInterval *BestVirt = 0;
309  unsigned BestPhys = 0;
310
311  Order.rewind();
312  while (unsigned PhysReg = Order.next()) {
313    LiveInterval *InterferingVReg = getSingleInterference(VirtReg, PhysReg);
314    if (!InterferingVReg)
315      continue;
316    if (TargetRegisterInfo::isPhysicalRegister(InterferingVReg->reg))
317      continue;
318    if (reassignVReg(*InterferingVReg, PhysReg))
319      return PhysReg;
320
321    // Cannot reassign, is this an eviction candidate?
322    if (InterferingVReg->weight < BestWeight) {
323      BestVirt = InterferingVReg;
324      BestPhys = PhysReg;
325      BestWeight = InterferingVReg->weight;
326    }
327  }
328
329  // Nothing reassigned, can we evict a lighter single interference?
330  if (BestVirt) {
331    DEBUG(dbgs() << "evicting lighter " << *BestVirt << '\n');
332    unassign(*BestVirt, VRM->getPhys(BestVirt->reg));
333    NewVRegs.push_back(BestVirt);
334    return BestPhys;
335  }
336
337  return 0;
338}
339
340
341//===----------------------------------------------------------------------===//
342//                              Region Splitting
343//===----------------------------------------------------------------------===//
344
345/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
346/// where VirtReg is live.
347/// The SpillConstraints array is minimally initialized with MBB->getNumber().
348void RAGreedy::calcLiveBlockInfo(LiveInterval &VirtReg) {
349  LiveBlocks.clear();
350  SpillConstraints.clear();
351
352  assert(!VirtReg.empty() && "Cannot allocate an empty interval");
353  LiveInterval::const_iterator LVI = VirtReg.begin();
354  LiveInterval::const_iterator LVE = VirtReg.end();
355
356  SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE;
357  UseI = SA->UseSlots.begin();
358  UseE = SA->UseSlots.end();
359
360  // Loop over basic blocks where VirtReg is live.
361  MachineFunction::iterator MFI = Indexes->getMBBFromIndex(LVI->start);
362  for (;;) {
363    // Block constraints depend on the interference pattern.
364    // Just allocate them here, don't compute anything.
365    SpillPlacement::BlockConstraint BC;
366    BC.Number = MFI->getNumber();
367    SpillConstraints.push_back(BC);
368
369    BlockInfo BI;
370    BI.MBB = MFI;
371    SlotIndex Start, Stop;
372    tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
373
374    // The last split point is the latest possible insertion point that dominates
375    // all successor blocks. If interference reaches LastSplitPoint, it is not
376    // possible to insert a split or reload that makes VirtReg live in the
377    // outgoing bundle.
378    MachineBasicBlock::iterator LSP = LIS->getLastSplitPoint(VirtReg, BI.MBB);
379    if (LSP == BI.MBB->end())
380      BI.LastSplitPoint = Stop;
381    else
382      BI.LastSplitPoint = Indexes->getInstructionIndex(LSP);
383
384    // LVI is the first live segment overlapping MBB.
385    BI.LiveIn = LVI->start <= Start;
386    if (!BI.LiveIn)
387      BI.Def = LVI->start;
388
389    // Find the first and last uses in the block.
390    BI.Uses = SA->hasUses(MFI);
391    if (BI.Uses && UseI != UseE) {
392      BI.FirstUse = *UseI;
393      assert(BI.FirstUse >= Start);
394      do ++UseI;
395      while (UseI != UseE && *UseI < Stop);
396      BI.LastUse = UseI[-1];
397      assert(BI.LastUse < Stop);
398    }
399
400    // Look for gaps in the live range.
401    bool hasGap = false;
402    BI.LiveOut = true;
403    while (LVI->end < Stop) {
404      SlotIndex LastStop = LVI->end;
405      if (++LVI == LVE || LVI->start >= Stop) {
406        BI.Kill = LastStop;
407        BI.LiveOut = false;
408        break;
409      }
410      if (LastStop < LVI->start) {
411        hasGap = true;
412        BI.Kill = LastStop;
413        BI.Def = LVI->start;
414      }
415    }
416
417    // Don't set LiveThrough when the block has a gap.
418    BI.LiveThrough = !hasGap && BI.LiveIn && BI.LiveOut;
419    LiveBlocks.push_back(BI);
420
421    // LVI is now at LVE or LVI->end >= Stop.
422    if (LVI == LVE)
423      break;
424
425    // Live segment ends exactly at Stop. Move to the next segment.
426    if (LVI->end == Stop && ++LVI == LVE)
427      break;
428
429    // Pick the next basic block.
430    if (LVI->start < Stop)
431      ++MFI;
432    else
433      MFI = Indexes->getMBBFromIndex(LVI->start);
434  }
435}
436
437/// calcInterferenceInfo - Compute per-block outgoing and ingoing constraints
438/// when considering interference from PhysReg. Also compute an optimistic local
439/// cost of this interference pattern.
440///
441/// The final cost of a split is the local cost + global cost of preferences
442/// broken by SpillPlacement.
443///
444float RAGreedy::calcInterferenceInfo(LiveInterval &VirtReg, unsigned PhysReg) {
445  // Reset interference dependent info.
446  for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
447    BlockInfo &BI = LiveBlocks[i];
448    SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
449    BC.Entry = (BI.Uses && BI.LiveIn) ?
450      SpillPlacement::PrefReg : SpillPlacement::DontCare;
451    BC.Exit = (BI.Uses && BI.LiveOut) ?
452      SpillPlacement::PrefReg : SpillPlacement::DontCare;
453    BI.OverlapEntry = BI.OverlapExit = false;
454  }
455
456  // Add interference info from each PhysReg alias.
457  for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
458    if (!query(VirtReg, *AI).checkInterference())
459      continue;
460    LiveIntervalUnion::SegmentIter IntI =
461      PhysReg2LiveUnion[*AI].find(VirtReg.beginIndex());
462    if (!IntI.valid())
463      continue;
464
465    // Determine which blocks have interference live in or after the last split
466    // point.
467    for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
468      BlockInfo &BI = LiveBlocks[i];
469      SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
470      SlotIndex Start, Stop;
471      tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
472
473      // Skip interference-free blocks.
474      if (IntI.start() >= Stop)
475        continue;
476
477      // Is the interference live-in?
478      if (BI.LiveIn) {
479        IntI.advanceTo(Start);
480        if (!IntI.valid())
481          break;
482        if (IntI.start() <= Start)
483          BC.Entry = SpillPlacement::MustSpill;
484      }
485
486      // Is the interference overlapping the last split point?
487      if (BI.LiveOut) {
488        if (IntI.stop() < BI.LastSplitPoint)
489          IntI.advanceTo(BI.LastSplitPoint.getPrevSlot());
490        if (!IntI.valid())
491          break;
492        if (IntI.start() < Stop)
493          BC.Exit = SpillPlacement::MustSpill;
494      }
495    }
496
497    // Rewind iterator and check other interferences.
498    IntI.find(VirtReg.beginIndex());
499    for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
500      BlockInfo &BI = LiveBlocks[i];
501      SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
502      SlotIndex Start, Stop;
503      tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
504
505      // Skip interference-free blocks.
506      if (IntI.start() >= Stop)
507        continue;
508
509      // Handle transparent blocks with interference separately.
510      // Transparent blocks never incur any fixed cost.
511      if (BI.LiveThrough && !BI.Uses) {
512        IntI.advanceTo(Start);
513        if (!IntI.valid())
514          break;
515        if (IntI.start() >= Stop)
516          continue;
517
518        if (BC.Entry != SpillPlacement::MustSpill)
519          BC.Entry = SpillPlacement::PrefSpill;
520        if (BC.Exit != SpillPlacement::MustSpill)
521          BC.Exit = SpillPlacement::PrefSpill;
522        continue;
523      }
524
525      // Now we only have blocks with uses left.
526      // Check if the interference overlaps the uses.
527      assert(BI.Uses && "Non-transparent block without any uses");
528
529      // Check interference on entry.
530      if (BI.LiveIn && BC.Entry != SpillPlacement::MustSpill) {
531        IntI.advanceTo(Start);
532        if (!IntI.valid())
533          break;
534        // Not live in, but before the first use.
535        if (IntI.start() < BI.FirstUse)
536          BC.Entry = SpillPlacement::PrefSpill;
537      }
538
539      // Does interference overlap the uses in the entry segment
540      // [FirstUse;Kill)?
541      if (BI.LiveIn && !BI.OverlapEntry) {
542        IntI.advanceTo(BI.FirstUse);
543        if (!IntI.valid())
544          break;
545        // A live-through interval has no kill.
546        // Check [FirstUse;LastUse) instead.
547        if (IntI.start() < (BI.LiveThrough ? BI.LastUse : BI.Kill))
548          BI.OverlapEntry = true;
549      }
550
551      // Does interference overlap the uses in the exit segment [Def;LastUse)?
552      if (BI.LiveOut && !BI.LiveThrough && !BI.OverlapExit) {
553        IntI.advanceTo(BI.Def);
554        if (!IntI.valid())
555          break;
556        if (IntI.start() < BI.LastUse)
557          BI.OverlapExit = true;
558      }
559
560      // Check interference on exit.
561      if (BI.LiveOut && BC.Exit != SpillPlacement::MustSpill) {
562        // Check interference between LastUse and Stop.
563        if (BC.Exit != SpillPlacement::PrefSpill) {
564          IntI.advanceTo(BI.LastUse);
565          if (!IntI.valid())
566            break;
567          if (IntI.start() < Stop)
568            BC.Exit = SpillPlacement::PrefSpill;
569        }
570      }
571    }
572  }
573
574  // Accumulate a local cost of this interference pattern.
575  float LocalCost = 0;
576  for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
577    BlockInfo &BI = LiveBlocks[i];
578    if (!BI.Uses)
579      continue;
580    SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
581    unsigned Inserts = 0;
582
583    // Do we need spill code for the entry segment?
584    if (BI.LiveIn)
585      Inserts += BI.OverlapEntry || BC.Entry != SpillPlacement::PrefReg;
586
587    // For the exit segment?
588    if (BI.LiveOut)
589      Inserts += BI.OverlapExit || BC.Exit != SpillPlacement::PrefReg;
590
591    // The local cost of spill code in this block is the block frequency times
592    // the number of spill instructions inserted.
593    if (Inserts)
594      LocalCost += Inserts * SpillPlacer->getBlockFrequency(BI.MBB);
595  }
596  DEBUG(dbgs() << "Local cost of " << PrintReg(PhysReg, TRI) << " = "
597               << LocalCost << '\n');
598  return LocalCost;
599}
600
601/// calcGlobalSplitCost - Return the global split cost of following the split
602/// pattern in LiveBundles. This cost should be added to the local cost of the
603/// interference pattern in SpillConstraints.
604///
605float RAGreedy::calcGlobalSplitCost(const BitVector &LiveBundles) {
606  float GlobalCost = 0;
607  for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
608    SpillPlacement::BlockConstraint &BC = SpillConstraints[i];
609    unsigned Inserts = 0;
610    // Broken entry preference?
611    Inserts += LiveBundles[Bundles->getBundle(BC.Number, 0)] !=
612                 (BC.Entry == SpillPlacement::PrefReg);
613    // Broken exit preference?
614    Inserts += LiveBundles[Bundles->getBundle(BC.Number, 1)] !=
615                 (BC.Exit == SpillPlacement::PrefReg);
616    if (Inserts)
617      GlobalCost += Inserts * SpillPlacer->getBlockFrequency(LiveBlocks[i].MBB);
618  }
619  DEBUG(dbgs() << "Global cost = " << GlobalCost << '\n');
620  return GlobalCost;
621}
622
623/// splitAroundRegion - Split VirtReg around the region determined by
624/// LiveBundles. Make an effort to avoid interference from PhysReg.
625///
626/// The 'register' interval is going to contain as many uses as possible while
627/// avoiding interference. The 'stack' interval is the complement constructed by
628/// SplitEditor. It will contain the rest.
629///
630void RAGreedy::splitAroundRegion(LiveInterval &VirtReg, unsigned PhysReg,
631                                 const BitVector &LiveBundles,
632                                 SmallVectorImpl<LiveInterval*> &NewVRegs) {
633  DEBUG({
634    dbgs() << "Splitting around region for " << PrintReg(PhysReg, TRI)
635           << " with bundles";
636    for (int i = LiveBundles.find_first(); i>=0; i = LiveBundles.find_next(i))
637      dbgs() << " EB#" << i;
638    dbgs() << ".\n";
639  });
640
641  // First compute interference ranges in the live blocks.
642  typedef std::pair<SlotIndex, SlotIndex> IndexPair;
643  SmallVector<IndexPair, 8> InterferenceRanges;
644  InterferenceRanges.resize(LiveBlocks.size());
645  for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
646    if (!query(VirtReg, *AI).checkInterference())
647      continue;
648    LiveIntervalUnion::SegmentIter IntI =
649      PhysReg2LiveUnion[*AI].find(VirtReg.beginIndex());
650    if (!IntI.valid())
651      continue;
652    for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
653      const BlockInfo &BI = LiveBlocks[i];
654      IndexPair &IP = InterferenceRanges[i];
655      SlotIndex Start, Stop;
656      tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
657      // Skip interference-free blocks.
658      if (IntI.start() >= Stop)
659        continue;
660
661      // First interference in block.
662      if (BI.LiveIn) {
663        IntI.advanceTo(Start);
664        if (!IntI.valid())
665          break;
666        if (IntI.start() >= Stop)
667          continue;
668        if (!IP.first.isValid() || IntI.start() < IP.first)
669          IP.first = IntI.start();
670      }
671
672      // Last interference in block.
673      if (BI.LiveOut) {
674        IntI.advanceTo(Stop);
675        if (!IntI.valid() || IntI.start() >= Stop)
676          --IntI;
677        if (IntI.stop() <= Start)
678          continue;
679        if (!IP.second.isValid() || IntI.stop() > IP.second)
680          IP.second = IntI.stop();
681      }
682    }
683  }
684
685  SmallVector<LiveInterval*, 4> SpillRegs;
686  LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs);
687  SplitEditor SE(*SA, *LIS, *VRM, *DomTree, LREdit);
688
689  // Create the main cross-block interval.
690  SE.openIntv();
691
692  // First add all defs that are live out of a block.
693  for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
694    BlockInfo &BI = LiveBlocks[i];
695    bool RegIn  = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
696    bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
697
698    // Should the register be live out?
699    if (!BI.LiveOut || !RegOut)
700      continue;
701
702    IndexPair &IP = InterferenceRanges[i];
703    SlotIndex Start, Stop;
704    tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
705
706    DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " -> EB#"
707                 << Bundles->getBundle(BI.MBB->getNumber(), 1)
708                 << " intf [" << IP.first << ';' << IP.second << ')');
709
710    // The interference interval should either be invalid or overlap MBB.
711    assert((!IP.first.isValid() || IP.first < Stop) && "Bad interference");
712    assert((!IP.second.isValid() || IP.second > Start) && "Bad interference");
713
714    // Check interference leaving the block.
715    if (!IP.second.isValid()) {
716      // Block is interference-free.
717      DEBUG(dbgs() << ", no interference");
718      if (!BI.Uses) {
719        assert(BI.LiveThrough && "No uses, but not live through block?");
720        // Block is live-through without interference.
721        DEBUG(dbgs() << ", no uses"
722                     << (RegIn ? ", live-through.\n" : ", stack in.\n"));
723        if (!RegIn)
724          SE.enterIntvAtEnd(*BI.MBB);
725        continue;
726      }
727      if (!BI.LiveThrough) {
728        DEBUG(dbgs() << ", not live-through.\n");
729        SE.useIntv(SE.enterIntvBefore(BI.Def), Stop);
730        continue;
731      }
732      if (!RegIn) {
733        // Block is live-through, but entry bundle is on the stack.
734        // Reload just before the first use.
735        DEBUG(dbgs() << ", not live-in, enter before first use.\n");
736        SE.useIntv(SE.enterIntvBefore(BI.FirstUse), Stop);
737        continue;
738      }
739      DEBUG(dbgs() << ", live-through.\n");
740      continue;
741    }
742
743    // Block has interference.
744    DEBUG(dbgs() << ", interference to " << IP.second);
745
746    if (!BI.LiveThrough && IP.second <= BI.Def) {
747      // The interference doesn't reach the outgoing segment.
748      DEBUG(dbgs() << " doesn't affect def from " << BI.Def << '\n');
749      SE.useIntv(BI.Def, Stop);
750      continue;
751    }
752
753
754    if (!BI.Uses) {
755      // No uses in block, avoid interference by reloading as late as possible.
756      DEBUG(dbgs() << ", no uses.\n");
757      SlotIndex SegStart = SE.enterIntvAtEnd(*BI.MBB);
758      assert(SegStart >= IP.second && "Couldn't avoid interference");
759      continue;
760    }
761
762    if (IP.second.getBoundaryIndex() < BI.LastUse) {
763      // There are interference-free uses at the end of the block.
764      // Find the first use that can get the live-out register.
765      SmallVectorImpl<SlotIndex>::const_iterator UI =
766        std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(),
767                         IP.second.getBoundaryIndex());
768      assert(UI != SA->UseSlots.end() && "Couldn't find last use");
769      SlotIndex Use = *UI;
770      assert(Use <= BI.LastUse && "Couldn't find last use");
771      // Only attempt a split befroe the last split point.
772      if (Use.getBaseIndex() <= BI.LastSplitPoint) {
773        DEBUG(dbgs() << ", free use at " << Use << ".\n");
774        SlotIndex SegStart = SE.enterIntvBefore(Use);
775        assert(SegStart >= IP.second && "Couldn't avoid interference");
776        assert(SegStart < BI.LastSplitPoint && "Impossible split point");
777        SE.useIntv(SegStart, Stop);
778        continue;
779      }
780    }
781
782    // Interference is after the last use.
783    DEBUG(dbgs() << " after last use.\n");
784    SlotIndex SegStart = SE.enterIntvAtEnd(*BI.MBB);
785    assert(SegStart >= IP.second && "Couldn't avoid interference");
786  }
787
788  // Now all defs leading to live bundles are handled, do everything else.
789  for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
790    BlockInfo &BI = LiveBlocks[i];
791    bool RegIn  = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 0)];
792    bool RegOut = LiveBundles[Bundles->getBundle(BI.MBB->getNumber(), 1)];
793
794    // Is the register live-in?
795    if (!BI.LiveIn || !RegIn)
796      continue;
797
798    // We have an incoming register. Check for interference.
799    IndexPair &IP = InterferenceRanges[i];
800    SlotIndex Start, Stop;
801    tie(Start, Stop) = Indexes->getMBBRange(BI.MBB);
802
803    DEBUG(dbgs() << "EB#" << Bundles->getBundle(BI.MBB->getNumber(), 0)
804                 << " -> BB#" << BI.MBB->getNumber());
805
806    // Check interference entering the block.
807    if (!IP.first.isValid()) {
808      // Block is interference-free.
809      DEBUG(dbgs() << ", no interference");
810      if (!BI.Uses) {
811        assert(BI.LiveThrough && "No uses, but not live through block?");
812        // Block is live-through without interference.
813        if (RegOut) {
814          DEBUG(dbgs() << ", no uses, live-through.\n");
815          SE.useIntv(Start, Stop);
816        } else {
817          DEBUG(dbgs() << ", no uses, stack-out.\n");
818          SE.leaveIntvAtTop(*BI.MBB);
819        }
820        continue;
821      }
822      if (!BI.LiveThrough) {
823        DEBUG(dbgs() << ", killed in block.\n");
824        SE.useIntv(Start, SE.leaveIntvAfter(BI.Kill));
825        continue;
826      }
827      if (!RegOut) {
828        // Block is live-through, but exit bundle is on the stack.
829        // Spill immediately after the last use.
830        if (BI.LastUse < BI.LastSplitPoint) {
831          DEBUG(dbgs() << ", uses, stack-out.\n");
832          SE.useIntv(Start, SE.leaveIntvAfter(BI.LastUse));
833          continue;
834        }
835        // The last use is after the last split point, it is probably an
836        // indirect jump.
837        DEBUG(dbgs() << ", uses at " << BI.LastUse << " after split point "
838                     << BI.LastSplitPoint << ", stack-out.\n");
839        SlotIndex SegEnd;
840        // Find the last real instruction before the split point.
841        MachineBasicBlock::iterator SplitI =
842          LIS->getInstructionFromIndex(BI.LastSplitPoint);
843        MachineBasicBlock::iterator I = SplitI, B = BI.MBB->begin();
844        while (I != B && (--I)->isDebugValue())
845          ;
846        if (I == SplitI)
847          SegEnd = SE.leaveIntvAtTop(*BI.MBB);
848        else {
849          SegEnd = SE.leaveIntvAfter(LIS->getInstructionIndex(I));
850          SE.useIntv(Start, SegEnd);
851        }
852        // Run a double interval from the split to the last use.
853        // This makes it possible to spill the complement without affecting the
854        // indirect branch.
855        SE.overlapIntv(SegEnd, BI.LastUse);
856        continue;
857      }
858      // Register is live-through.
859      DEBUG(dbgs() << ", uses, live-through.\n");
860      SE.useIntv(Start, Stop);
861      continue;
862    }
863
864    // Block has interference.
865    DEBUG(dbgs() << ", interference from " << IP.first);
866
867    if (!BI.LiveThrough && IP.first >= BI.Kill) {
868      // The interference doesn't reach the outgoing segment.
869      DEBUG(dbgs() << " doesn't affect kill at " << BI.Kill << '\n');
870      SE.useIntv(Start, BI.Kill);
871      continue;
872    }
873
874    if (!BI.Uses) {
875      // No uses in block, avoid interference by spilling as soon as possible.
876      DEBUG(dbgs() << ", no uses.\n");
877      SlotIndex SegEnd = SE.leaveIntvAtTop(*BI.MBB);
878      assert(SegEnd <= IP.first && "Couldn't avoid interference");
879      continue;
880    }
881    if (IP.first.getBaseIndex() > BI.FirstUse) {
882      // There are interference-free uses at the beginning of the block.
883      // Find the last use that can get the register.
884      SmallVectorImpl<SlotIndex>::const_iterator UI =
885        std::lower_bound(SA->UseSlots.begin(), SA->UseSlots.end(),
886                         IP.first.getBaseIndex());
887      assert(UI != SA->UseSlots.begin() && "Couldn't find first use");
888      SlotIndex Use = (--UI)->getBoundaryIndex();
889      DEBUG(dbgs() << ", free use at " << *UI << ".\n");
890      SlotIndex SegEnd = SE.leaveIntvAfter(Use);
891      assert(SegEnd <= IP.first && "Couldn't avoid interference");
892      SE.useIntv(Start, SegEnd);
893      continue;
894    }
895
896    // Interference is before the first use.
897    DEBUG(dbgs() << " before first use.\n");
898    SlotIndex SegEnd = SE.leaveIntvAtTop(*BI.MBB);
899    assert(SegEnd <= IP.first && "Couldn't avoid interference");
900  }
901
902  SE.closeIntv();
903
904  // FIXME: Should we be more aggressive about splitting the stack region into
905  // per-block segments? The current approach allows the stack region to
906  // separate into connected components. Some components may be allocatable.
907  SE.finish();
908
909  if (VerifyEnabled) {
910    MF->verify(this, "After splitting live range around region");
911
912#ifndef NDEBUG
913    // Make sure that at least one of the new intervals can allocate to PhysReg.
914    // That was the whole point of splitting the live range.
915    bool found = false;
916    for (LiveRangeEdit::iterator I = LREdit.begin(), E = LREdit.end(); I != E;
917         ++I)
918      if (!checkUncachedInterference(**I, PhysReg)) {
919        found = true;
920        break;
921      }
922    assert(found && "No allocatable intervals after pointless splitting");
923#endif
924  }
925}
926
927unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
928                                  SmallVectorImpl<LiveInterval*> &NewVRegs) {
929  calcLiveBlockInfo(VirtReg);
930  BitVector LiveBundles, BestBundles;
931  float BestCost = 0;
932  unsigned BestReg = 0;
933  Order.rewind();
934  while (unsigned PhysReg = Order.next()) {
935    float Cost = calcInterferenceInfo(VirtReg, PhysReg);
936    if (BestReg && Cost >= BestCost)
937      continue;
938
939    SpillPlacer->placeSpills(SpillConstraints, LiveBundles);
940    // No live bundles, defer to splitSingleBlocks().
941    if (!LiveBundles.any())
942      continue;
943
944    Cost += calcGlobalSplitCost(LiveBundles);
945    if (!BestReg || Cost < BestCost) {
946      BestReg = PhysReg;
947      BestCost = Cost;
948      BestBundles.swap(LiveBundles);
949    }
950  }
951
952  if (!BestReg)
953    return 0;
954
955  splitAroundRegion(VirtReg, BestReg, BestBundles, NewVRegs);
956  return 0;
957}
958
959
960//===----------------------------------------------------------------------===//
961//                          Live Range Splitting
962//===----------------------------------------------------------------------===//
963
964/// trySplit - Try to split VirtReg or one of its interferences, making it
965/// assignable.
966/// @return Physreg when VirtReg may be assigned and/or new NewVRegs.
967unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
968                            SmallVectorImpl<LiveInterval*>&NewVRegs) {
969  NamedRegionTimer T("Splitter", TimerGroupName, TimePassesIsEnabled);
970  SA->analyze(&VirtReg);
971
972  // Don't attempt splitting on local intervals for now. TBD.
973  if (LIS->intervalIsInOneMBB(VirtReg))
974    return 0;
975
976  // First try to split around a region spanning multiple blocks.
977  unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
978  if (PhysReg || !NewVRegs.empty())
979    return PhysReg;
980
981  // Then isolate blocks with multiple uses.
982  SplitAnalysis::BlockPtrSet Blocks;
983  if (SA->getMultiUseBlocks(Blocks)) {
984    SmallVector<LiveInterval*, 4> SpillRegs;
985    LiveRangeEdit LREdit(VirtReg, NewVRegs, SpillRegs);
986    SplitEditor(*SA, *LIS, *VRM, *DomTree, LREdit).splitSingleBlocks(Blocks);
987    if (VerifyEnabled)
988      MF->verify(this, "After splitting live range around basic blocks");
989  }
990
991  // Don't assign any physregs.
992  return 0;
993}
994
995
996//===----------------------------------------------------------------------===//
997//                                Spilling
998//===----------------------------------------------------------------------===//
999
1000/// calcInterferenceWeight - Calculate the combined spill weight of
1001/// interferences when assigning VirtReg to PhysReg.
1002float RAGreedy::calcInterferenceWeight(LiveInterval &VirtReg, unsigned PhysReg){
1003  float Sum = 0;
1004  for (const unsigned *AI = TRI->getOverlaps(PhysReg); *AI; ++AI) {
1005    LiveIntervalUnion::Query &Q = query(VirtReg, *AI);
1006    Q.collectInterferingVRegs();
1007    if (Q.seenUnspillableVReg())
1008      return HUGE_VALF;
1009    for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i)
1010      Sum += Q.interferingVRegs()[i]->weight;
1011  }
1012  return Sum;
1013}
1014
1015/// trySpillInterferences - Try to spill interfering registers instead of the
1016/// current one. Only do it if the accumulated spill weight is smaller than the
1017/// current spill weight.
1018unsigned RAGreedy::trySpillInterferences(LiveInterval &VirtReg,
1019                                         AllocationOrder &Order,
1020                                     SmallVectorImpl<LiveInterval*> &NewVRegs) {
1021  NamedRegionTimer T("Spill Interference", TimerGroupName, TimePassesIsEnabled);
1022  unsigned BestPhys = 0;
1023  float BestWeight = 0;
1024
1025  Order.rewind();
1026  while (unsigned PhysReg = Order.next()) {
1027    float Weight = calcInterferenceWeight(VirtReg, PhysReg);
1028    if (Weight == HUGE_VALF || Weight >= VirtReg.weight)
1029      continue;
1030    if (!BestPhys || Weight < BestWeight)
1031      BestPhys = PhysReg, BestWeight = Weight;
1032  }
1033
1034  // No candidates found.
1035  if (!BestPhys)
1036    return 0;
1037
1038  // Collect all interfering registers.
1039  SmallVector<LiveInterval*, 8> Spills;
1040  for (const unsigned *AI = TRI->getOverlaps(BestPhys); *AI; ++AI) {
1041    LiveIntervalUnion::Query &Q = query(VirtReg, *AI);
1042    Spills.append(Q.interferingVRegs().begin(), Q.interferingVRegs().end());
1043    for (unsigned i = 0, e = Q.interferingVRegs().size(); i != e; ++i) {
1044      LiveInterval *VReg = Q.interferingVRegs()[i];
1045      unassign(*VReg, *AI);
1046    }
1047  }
1048
1049  // Spill them all.
1050  DEBUG(dbgs() << "spilling " << Spills.size() << " interferences with weight "
1051               << BestWeight << '\n');
1052  for (unsigned i = 0, e = Spills.size(); i != e; ++i)
1053    spiller().spill(Spills[i], NewVRegs, Spills);
1054  return BestPhys;
1055}
1056
1057
1058//===----------------------------------------------------------------------===//
1059//                            Main Entry Point
1060//===----------------------------------------------------------------------===//
1061
1062unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
1063                                 SmallVectorImpl<LiveInterval*> &NewVRegs) {
1064  // First try assigning a free register.
1065  AllocationOrder Order(VirtReg.reg, *VRM, ReservedRegs);
1066  while (unsigned PhysReg = Order.next()) {
1067    if (!checkPhysRegInterference(VirtReg, PhysReg))
1068      return PhysReg;
1069  }
1070
1071  // Try to reassign interferences.
1072  if (unsigned PhysReg = tryReassignOrEvict(VirtReg, Order, NewVRegs))
1073    return PhysReg;
1074
1075  assert(NewVRegs.empty() && "Cannot append to existing NewVRegs");
1076
1077  // Try splitting VirtReg or interferences.
1078  unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs);
1079  if (PhysReg || !NewVRegs.empty())
1080    return PhysReg;
1081
1082  // Try to spill another interfering reg with less spill weight.
1083  PhysReg = trySpillInterferences(VirtReg, Order, NewVRegs);
1084  if (PhysReg)
1085    return PhysReg;
1086
1087  // Finally spill VirtReg itself.
1088  NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled);
1089  SmallVector<LiveInterval*, 1> pendingSpills;
1090  spiller().spill(&VirtReg, NewVRegs, pendingSpills);
1091
1092  // The live virtual register requesting allocation was spilled, so tell
1093  // the caller not to allocate anything during this round.
1094  return 0;
1095}
1096
1097bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
1098  DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
1099               << "********** Function: "
1100               << ((Value*)mf.getFunction())->getName() << '\n');
1101
1102  MF = &mf;
1103  if (VerifyEnabled)
1104    MF->verify(this, "Before greedy register allocator");
1105
1106  RegAllocBase::init(getAnalysis<VirtRegMap>(), getAnalysis<LiveIntervals>());
1107  Indexes = &getAnalysis<SlotIndexes>();
1108  DomTree = &getAnalysis<MachineDominatorTree>();
1109  ReservedRegs = TRI->getReservedRegs(*MF);
1110  SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
1111  Loops = &getAnalysis<MachineLoopInfo>();
1112  LoopRanges = &getAnalysis<MachineLoopRanges>();
1113  Bundles = &getAnalysis<EdgeBundles>();
1114  SpillPlacer = &getAnalysis<SpillPlacement>();
1115
1116  SA.reset(new SplitAnalysis(*MF, *LIS, *Loops));
1117
1118  allocatePhysRegs();
1119  addMBBLiveIns(MF);
1120  LIS->addKillFlags();
1121
1122  // Run rewriter
1123  {
1124    NamedRegionTimer T("Rewriter", TimerGroupName, TimePassesIsEnabled);
1125    std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
1126    rewriter->runOnMachineFunction(*MF, *VRM, LIS);
1127  }
1128
1129  // The pass output is in VirtRegMap. Release all the transient data.
1130  releaseMemory();
1131
1132  return true;
1133}
1134