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