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 #include "llvm/CodeGen/Passes.h"
16 #include "AllocationOrder.h"
17 #include "InterferenceCache.h"
18 #include "LiveDebugVariables.h"
19 #include "RegAllocBase.h"
20 #include "SpillPlacement.h"
21 #include "Spiller.h"
22 #include "SplitKit.h"
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/Analysis/AliasAnalysis.h"
25 #include "llvm/CodeGen/CalcSpillWeights.h"
26 #include "llvm/CodeGen/EdgeBundles.h"
27 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
28 #include "llvm/CodeGen/LiveRangeEdit.h"
29 #include "llvm/CodeGen/LiveRegMatrix.h"
30 #include "llvm/CodeGen/LiveStackAnalysis.h"
31 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
32 #include "llvm/CodeGen/MachineDominators.h"
33 #include "llvm/CodeGen/MachineFunctionPass.h"
34 #include "llvm/CodeGen/MachineLoopInfo.h"
35 #include "llvm/CodeGen/MachineRegisterInfo.h"
36 #include "llvm/CodeGen/RegAllocRegistry.h"
37 #include "llvm/CodeGen/RegisterClassInfo.h"
38 #include "llvm/CodeGen/VirtRegMap.h"
39 #include "llvm/IR/LLVMContext.h"
40 #include "llvm/PassAnalysisSupport.h"
41 #include "llvm/Support/BranchProbability.h"
42 #include "llvm/Support/CommandLine.h"
43 #include "llvm/Support/Debug.h"
44 #include "llvm/Support/ErrorHandling.h"
45 #include "llvm/Support/Timer.h"
46 #include "llvm/Support/raw_ostream.h"
47 #include "llvm/Target/TargetSubtargetInfo.h"
48 #include <queue>
49 
50 using namespace llvm;
51 
52 #define DEBUG_TYPE "regalloc"
53 
54 STATISTIC(NumGlobalSplits, "Number of split global live ranges");
55 STATISTIC(NumLocalSplits,  "Number of split local live ranges");
56 STATISTIC(NumEvicted,      "Number of interferences evicted");
57 
58 static cl::opt<SplitEditor::ComplementSpillMode>
59 SplitSpillMode("split-spill-mode", cl::Hidden,
60   cl::desc("Spill mode for splitting live ranges"),
61   cl::values(clEnumValN(SplitEditor::SM_Partition, "default", "Default"),
62              clEnumValN(SplitEditor::SM_Size,  "size",  "Optimize for size"),
63              clEnumValN(SplitEditor::SM_Speed, "speed", "Optimize for speed"),
64              clEnumValEnd),
65   cl::init(SplitEditor::SM_Partition));
66 
67 static cl::opt<unsigned>
68 LastChanceRecoloringMaxDepth("lcr-max-depth", cl::Hidden,
69                              cl::desc("Last chance recoloring max depth"),
70                              cl::init(5));
71 
72 static cl::opt<unsigned> LastChanceRecoloringMaxInterference(
73     "lcr-max-interf", cl::Hidden,
74     cl::desc("Last chance recoloring maximum number of considered"
75              " interference at a time"),
76     cl::init(8));
77 
78 static cl::opt<bool>
79 ExhaustiveSearch("exhaustive-register-search", cl::NotHidden,
80                  cl::desc("Exhaustive Search for registers bypassing the depth "
81                           "and interference cutoffs of last chance recoloring"));
82 
83 static cl::opt<bool> EnableLocalReassignment(
84     "enable-local-reassign", cl::Hidden,
85     cl::desc("Local reassignment can yield better allocation decisions, but "
86              "may be compile time intensive"),
87     cl::init(false));
88 
89 static cl::opt<bool> EnableDeferredSpilling(
90     "enable-deferred-spilling", cl::Hidden,
91     cl::desc("Instead of spilling a variable right away, defer the actual "
92              "code insertion to the end of the allocation. That way the "
93              "allocator might still find a suitable coloring for this "
94              "variable because of other evicted variables."),
95     cl::init(false));
96 
97 // FIXME: Find a good default for this flag and remove the flag.
98 static cl::opt<unsigned>
99 CSRFirstTimeCost("regalloc-csr-first-time-cost",
100               cl::desc("Cost for first time use of callee-saved register."),
101               cl::init(0), cl::Hidden);
102 
103 static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator",
104                                        createGreedyRegisterAllocator);
105 
106 namespace {
107 class RAGreedy : public MachineFunctionPass,
108                  public RegAllocBase,
109                  private LiveRangeEdit::Delegate {
110   // Convenient shortcuts.
111   typedef std::priority_queue<std::pair<unsigned, unsigned> > PQueue;
112   typedef SmallPtrSet<LiveInterval *, 4> SmallLISet;
113   typedef SmallSet<unsigned, 16> SmallVirtRegSet;
114 
115   // context
116   MachineFunction *MF;
117 
118   // Shortcuts to some useful interface.
119   const TargetInstrInfo *TII;
120   const TargetRegisterInfo *TRI;
121   RegisterClassInfo RCI;
122 
123   // analyses
124   SlotIndexes *Indexes;
125   MachineBlockFrequencyInfo *MBFI;
126   MachineDominatorTree *DomTree;
127   MachineLoopInfo *Loops;
128   EdgeBundles *Bundles;
129   SpillPlacement *SpillPlacer;
130   LiveDebugVariables *DebugVars;
131 
132   // state
133   std::unique_ptr<Spiller> SpillerInstance;
134   PQueue Queue;
135   unsigned NextCascade;
136 
137   // Live ranges pass through a number of stages as we try to allocate them.
138   // Some of the stages may also create new live ranges:
139   //
140   // - Region splitting.
141   // - Per-block splitting.
142   // - Local splitting.
143   // - Spilling.
144   //
145   // Ranges produced by one of the stages skip the previous stages when they are
146   // dequeued. This improves performance because we can skip interference checks
147   // that are unlikely to give any results. It also guarantees that the live
148   // range splitting algorithm terminates, something that is otherwise hard to
149   // ensure.
150   enum LiveRangeStage {
151     /// Newly created live range that has never been queued.
152     RS_New,
153 
154     /// Only attempt assignment and eviction. Then requeue as RS_Split.
155     RS_Assign,
156 
157     /// Attempt live range splitting if assignment is impossible.
158     RS_Split,
159 
160     /// Attempt more aggressive live range splitting that is guaranteed to make
161     /// progress.  This is used for split products that may not be making
162     /// progress.
163     RS_Split2,
164 
165     /// Live range will be spilled.  No more splitting will be attempted.
166     RS_Spill,
167 
168 
169     /// Live range is in memory. Because of other evictions, it might get moved
170     /// in a register in the end.
171     RS_Memory,
172 
173     /// There is nothing more we can do to this live range.  Abort compilation
174     /// if it can't be assigned.
175     RS_Done
176   };
177 
178   // Enum CutOffStage to keep a track whether the register allocation failed
179   // because of the cutoffs encountered in last chance recoloring.
180   // Note: This is used as bitmask. New value should be next power of 2.
181   enum CutOffStage {
182     // No cutoffs encountered
183     CO_None = 0,
184 
185     // lcr-max-depth cutoff encountered
186     CO_Depth = 1,
187 
188     // lcr-max-interf cutoff encountered
189     CO_Interf = 2
190   };
191 
192   uint8_t CutOffInfo;
193 
194 #ifndef NDEBUG
195   static const char *const StageName[];
196 #endif
197 
198   // RegInfo - Keep additional information about each live range.
199   struct RegInfo {
200     LiveRangeStage Stage;
201 
202     // Cascade - Eviction loop prevention. See canEvictInterference().
203     unsigned Cascade;
204 
RegInfo__anon4e4d313f0111::RAGreedy::RegInfo205     RegInfo() : Stage(RS_New), Cascade(0) {}
206   };
207 
208   IndexedMap<RegInfo, VirtReg2IndexFunctor> ExtraRegInfo;
209 
getStage(const LiveInterval & VirtReg) const210   LiveRangeStage getStage(const LiveInterval &VirtReg) const {
211     return ExtraRegInfo[VirtReg.reg].Stage;
212   }
213 
setStage(const LiveInterval & VirtReg,LiveRangeStage Stage)214   void setStage(const LiveInterval &VirtReg, LiveRangeStage Stage) {
215     ExtraRegInfo.resize(MRI->getNumVirtRegs());
216     ExtraRegInfo[VirtReg.reg].Stage = Stage;
217   }
218 
219   template<typename Iterator>
setStage(Iterator Begin,Iterator End,LiveRangeStage NewStage)220   void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) {
221     ExtraRegInfo.resize(MRI->getNumVirtRegs());
222     for (;Begin != End; ++Begin) {
223       unsigned Reg = *Begin;
224       if (ExtraRegInfo[Reg].Stage == RS_New)
225         ExtraRegInfo[Reg].Stage = NewStage;
226     }
227   }
228 
229   /// Cost of evicting interference.
230   struct EvictionCost {
231     unsigned BrokenHints; ///< Total number of broken hints.
232     float MaxWeight;      ///< Maximum spill weight evicted.
233 
EvictionCost__anon4e4d313f0111::RAGreedy::EvictionCost234     EvictionCost(): BrokenHints(0), MaxWeight(0) {}
235 
isMax__anon4e4d313f0111::RAGreedy::EvictionCost236     bool isMax() const { return BrokenHints == ~0u; }
237 
setMax__anon4e4d313f0111::RAGreedy::EvictionCost238     void setMax() { BrokenHints = ~0u; }
239 
setBrokenHints__anon4e4d313f0111::RAGreedy::EvictionCost240     void setBrokenHints(unsigned NHints) { BrokenHints = NHints; }
241 
operator <__anon4e4d313f0111::RAGreedy::EvictionCost242     bool operator<(const EvictionCost &O) const {
243       return std::tie(BrokenHints, MaxWeight) <
244              std::tie(O.BrokenHints, O.MaxWeight);
245     }
246   };
247 
248   // splitting state.
249   std::unique_ptr<SplitAnalysis> SA;
250   std::unique_ptr<SplitEditor> SE;
251 
252   /// Cached per-block interference maps
253   InterferenceCache IntfCache;
254 
255   /// All basic blocks where the current register has uses.
256   SmallVector<SpillPlacement::BlockConstraint, 8> SplitConstraints;
257 
258   /// Global live range splitting candidate info.
259   struct GlobalSplitCandidate {
260     // Register intended for assignment, or 0.
261     unsigned PhysReg;
262 
263     // SplitKit interval index for this candidate.
264     unsigned IntvIdx;
265 
266     // Interference for PhysReg.
267     InterferenceCache::Cursor Intf;
268 
269     // Bundles where this candidate should be live.
270     BitVector LiveBundles;
271     SmallVector<unsigned, 8> ActiveBlocks;
272 
reset__anon4e4d313f0111::RAGreedy::GlobalSplitCandidate273     void reset(InterferenceCache &Cache, unsigned Reg) {
274       PhysReg = Reg;
275       IntvIdx = 0;
276       Intf.setPhysReg(Cache, Reg);
277       LiveBundles.clear();
278       ActiveBlocks.clear();
279     }
280 
281     // Set B[i] = C for every live bundle where B[i] was NoCand.
getBundles__anon4e4d313f0111::RAGreedy::GlobalSplitCandidate282     unsigned getBundles(SmallVectorImpl<unsigned> &B, unsigned C) {
283       unsigned Count = 0;
284       for (int i = LiveBundles.find_first(); i >= 0;
285            i = LiveBundles.find_next(i))
286         if (B[i] == NoCand) {
287           B[i] = C;
288           Count++;
289         }
290       return Count;
291     }
292   };
293 
294   /// Candidate info for each PhysReg in AllocationOrder.
295   /// This vector never shrinks, but grows to the size of the largest register
296   /// class.
297   SmallVector<GlobalSplitCandidate, 32> GlobalCand;
298 
299   enum : unsigned { NoCand = ~0u };
300 
301   /// Candidate map. Each edge bundle is assigned to a GlobalCand entry, or to
302   /// NoCand which indicates the stack interval.
303   SmallVector<unsigned, 32> BundleCand;
304 
305   /// Callee-save register cost, calculated once per machine function.
306   BlockFrequency CSRCost;
307 
308   /// Run or not the local reassignment heuristic. This information is
309   /// obtained from the TargetSubtargetInfo.
310   bool EnableLocalReassign;
311 
312   /// Set of broken hints that may be reconciled later because of eviction.
313   SmallSetVector<LiveInterval *, 8> SetOfBrokenHints;
314 
315 public:
316   RAGreedy();
317 
318   /// Return the pass name.
getPassName() const319   const char* getPassName() const override {
320     return "Greedy Register Allocator";
321   }
322 
323   /// RAGreedy analysis usage.
324   void getAnalysisUsage(AnalysisUsage &AU) const override;
325   void releaseMemory() override;
spiller()326   Spiller &spiller() override { return *SpillerInstance; }
327   void enqueue(LiveInterval *LI) override;
328   LiveInterval *dequeue() override;
329   unsigned selectOrSplit(LiveInterval&, SmallVectorImpl<unsigned>&) override;
330   void aboutToRemoveInterval(LiveInterval &) override;
331 
332   /// Perform register allocation.
333   bool runOnMachineFunction(MachineFunction &mf) override;
334 
335   static char ID;
336 
337 private:
338   unsigned selectOrSplitImpl(LiveInterval &, SmallVectorImpl<unsigned> &,
339                              SmallVirtRegSet &, unsigned = 0);
340 
341   bool LRE_CanEraseVirtReg(unsigned) override;
342   void LRE_WillShrinkVirtReg(unsigned) override;
343   void LRE_DidCloneVirtReg(unsigned, unsigned) override;
344   void enqueue(PQueue &CurQueue, LiveInterval *LI);
345   LiveInterval *dequeue(PQueue &CurQueue);
346 
347   BlockFrequency calcSpillCost();
348   bool addSplitConstraints(InterferenceCache::Cursor, BlockFrequency&);
349   void addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>);
350   void growRegion(GlobalSplitCandidate &Cand);
351   BlockFrequency calcGlobalSplitCost(GlobalSplitCandidate&);
352   bool calcCompactRegion(GlobalSplitCandidate&);
353   void splitAroundRegion(LiveRangeEdit&, ArrayRef<unsigned>);
354   void calcGapWeights(unsigned, SmallVectorImpl<float>&);
355   unsigned canReassign(LiveInterval &VirtReg, unsigned PhysReg);
356   bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool);
357   bool canEvictInterference(LiveInterval&, unsigned, bool, EvictionCost&);
358   void evictInterference(LiveInterval&, unsigned,
359                          SmallVectorImpl<unsigned>&);
360   bool mayRecolorAllInterferences(unsigned PhysReg, LiveInterval &VirtReg,
361                                   SmallLISet &RecoloringCandidates,
362                                   const SmallVirtRegSet &FixedRegisters);
363 
364   unsigned tryAssign(LiveInterval&, AllocationOrder&,
365                      SmallVectorImpl<unsigned>&);
366   unsigned tryEvict(LiveInterval&, AllocationOrder&,
367                     SmallVectorImpl<unsigned>&, unsigned = ~0u);
368   unsigned tryRegionSplit(LiveInterval&, AllocationOrder&,
369                           SmallVectorImpl<unsigned>&);
370   /// Calculate cost of region splitting.
371   unsigned calculateRegionSplitCost(LiveInterval &VirtReg,
372                                     AllocationOrder &Order,
373                                     BlockFrequency &BestCost,
374                                     unsigned &NumCands, bool IgnoreCSR);
375   /// Perform region splitting.
376   unsigned doRegionSplit(LiveInterval &VirtReg, unsigned BestCand,
377                          bool HasCompact,
378                          SmallVectorImpl<unsigned> &NewVRegs);
379   /// Check other options before using a callee-saved register for the first
380   /// time.
381   unsigned tryAssignCSRFirstTime(LiveInterval &VirtReg, AllocationOrder &Order,
382                                  unsigned PhysReg, unsigned &CostPerUseLimit,
383                                  SmallVectorImpl<unsigned> &NewVRegs);
384   void initializeCSRCost();
385   unsigned tryBlockSplit(LiveInterval&, AllocationOrder&,
386                          SmallVectorImpl<unsigned>&);
387   unsigned tryInstructionSplit(LiveInterval&, AllocationOrder&,
388                                SmallVectorImpl<unsigned>&);
389   unsigned tryLocalSplit(LiveInterval&, AllocationOrder&,
390     SmallVectorImpl<unsigned>&);
391   unsigned trySplit(LiveInterval&, AllocationOrder&,
392                     SmallVectorImpl<unsigned>&);
393   unsigned tryLastChanceRecoloring(LiveInterval &, AllocationOrder &,
394                                    SmallVectorImpl<unsigned> &,
395                                    SmallVirtRegSet &, unsigned);
396   bool tryRecoloringCandidates(PQueue &, SmallVectorImpl<unsigned> &,
397                                SmallVirtRegSet &, unsigned);
398   void tryHintRecoloring(LiveInterval &);
399   void tryHintsRecoloring();
400 
401   /// Model the information carried by one end of a copy.
402   struct HintInfo {
403     /// The frequency of the copy.
404     BlockFrequency Freq;
405     /// The virtual register or physical register.
406     unsigned Reg;
407     /// Its currently assigned register.
408     /// In case of a physical register Reg == PhysReg.
409     unsigned PhysReg;
HintInfo__anon4e4d313f0111::RAGreedy::HintInfo410     HintInfo(BlockFrequency Freq, unsigned Reg, unsigned PhysReg)
411         : Freq(Freq), Reg(Reg), PhysReg(PhysReg) {}
412   };
413   typedef SmallVector<HintInfo, 4> HintsInfo;
414   BlockFrequency getBrokenHintFreq(const HintsInfo &, unsigned);
415   void collectHintInfo(unsigned, HintsInfo &);
416 
417   bool isUnusedCalleeSavedReg(unsigned PhysReg) const;
418 };
419 } // end anonymous namespace
420 
421 char RAGreedy::ID = 0;
422 
423 #ifndef NDEBUG
424 const char *const RAGreedy::StageName[] = {
425     "RS_New",
426     "RS_Assign",
427     "RS_Split",
428     "RS_Split2",
429     "RS_Spill",
430     "RS_Memory",
431     "RS_Done"
432 };
433 #endif
434 
435 // Hysteresis to use when comparing floats.
436 // This helps stabilize decisions based on float comparisons.
437 const float Hysteresis = (2007 / 2048.0f); // 0.97998046875
438 
439 
createGreedyRegisterAllocator()440 FunctionPass* llvm::createGreedyRegisterAllocator() {
441   return new RAGreedy();
442 }
443 
RAGreedy()444 RAGreedy::RAGreedy(): MachineFunctionPass(ID) {
445   initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry());
446   initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
447   initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
448   initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
449   initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry());
450   initializeMachineSchedulerPass(*PassRegistry::getPassRegistry());
451   initializeLiveStacksPass(*PassRegistry::getPassRegistry());
452   initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
453   initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
454   initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
455   initializeLiveRegMatrixPass(*PassRegistry::getPassRegistry());
456   initializeEdgeBundlesPass(*PassRegistry::getPassRegistry());
457   initializeSpillPlacementPass(*PassRegistry::getPassRegistry());
458 }
459 
getAnalysisUsage(AnalysisUsage & AU) const460 void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
461   AU.setPreservesCFG();
462   AU.addRequired<MachineBlockFrequencyInfo>();
463   AU.addPreserved<MachineBlockFrequencyInfo>();
464   AU.addRequired<AAResultsWrapperPass>();
465   AU.addPreserved<AAResultsWrapperPass>();
466   AU.addRequired<LiveIntervals>();
467   AU.addPreserved<LiveIntervals>();
468   AU.addRequired<SlotIndexes>();
469   AU.addPreserved<SlotIndexes>();
470   AU.addRequired<LiveDebugVariables>();
471   AU.addPreserved<LiveDebugVariables>();
472   AU.addRequired<LiveStacks>();
473   AU.addPreserved<LiveStacks>();
474   AU.addRequired<MachineDominatorTree>();
475   AU.addPreserved<MachineDominatorTree>();
476   AU.addRequired<MachineLoopInfo>();
477   AU.addPreserved<MachineLoopInfo>();
478   AU.addRequired<VirtRegMap>();
479   AU.addPreserved<VirtRegMap>();
480   AU.addRequired<LiveRegMatrix>();
481   AU.addPreserved<LiveRegMatrix>();
482   AU.addRequired<EdgeBundles>();
483   AU.addRequired<SpillPlacement>();
484   MachineFunctionPass::getAnalysisUsage(AU);
485 }
486 
487 
488 //===----------------------------------------------------------------------===//
489 //                     LiveRangeEdit delegate methods
490 //===----------------------------------------------------------------------===//
491 
LRE_CanEraseVirtReg(unsigned VirtReg)492 bool RAGreedy::LRE_CanEraseVirtReg(unsigned VirtReg) {
493   if (VRM->hasPhys(VirtReg)) {
494     LiveInterval &LI = LIS->getInterval(VirtReg);
495     Matrix->unassign(LI);
496     aboutToRemoveInterval(LI);
497     return true;
498   }
499   // Unassigned virtreg is probably in the priority queue.
500   // RegAllocBase will erase it after dequeueing.
501   return false;
502 }
503 
LRE_WillShrinkVirtReg(unsigned VirtReg)504 void RAGreedy::LRE_WillShrinkVirtReg(unsigned VirtReg) {
505   if (!VRM->hasPhys(VirtReg))
506     return;
507 
508   // Register is assigned, put it back on the queue for reassignment.
509   LiveInterval &LI = LIS->getInterval(VirtReg);
510   Matrix->unassign(LI);
511   enqueue(&LI);
512 }
513 
LRE_DidCloneVirtReg(unsigned New,unsigned Old)514 void RAGreedy::LRE_DidCloneVirtReg(unsigned New, unsigned Old) {
515   // Cloning a register we haven't even heard about yet?  Just ignore it.
516   if (!ExtraRegInfo.inBounds(Old))
517     return;
518 
519   // LRE may clone a virtual register because dead code elimination causes it to
520   // be split into connected components. The new components are much smaller
521   // than the original, so they should get a new chance at being assigned.
522   // same stage as the parent.
523   ExtraRegInfo[Old].Stage = RS_Assign;
524   ExtraRegInfo.grow(New);
525   ExtraRegInfo[New] = ExtraRegInfo[Old];
526 }
527 
releaseMemory()528 void RAGreedy::releaseMemory() {
529   SpillerInstance.reset();
530   ExtraRegInfo.clear();
531   GlobalCand.clear();
532 }
533 
enqueue(LiveInterval * LI)534 void RAGreedy::enqueue(LiveInterval *LI) { enqueue(Queue, LI); }
535 
enqueue(PQueue & CurQueue,LiveInterval * LI)536 void RAGreedy::enqueue(PQueue &CurQueue, LiveInterval *LI) {
537   // Prioritize live ranges by size, assigning larger ranges first.
538   // The queue holds (size, reg) pairs.
539   const unsigned Size = LI->getSize();
540   const unsigned Reg = LI->reg;
541   assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
542          "Can only enqueue virtual registers");
543   unsigned Prio;
544 
545   ExtraRegInfo.grow(Reg);
546   if (ExtraRegInfo[Reg].Stage == RS_New)
547     ExtraRegInfo[Reg].Stage = RS_Assign;
548 
549   if (ExtraRegInfo[Reg].Stage == RS_Split) {
550     // Unsplit ranges that couldn't be allocated immediately are deferred until
551     // everything else has been allocated.
552     Prio = Size;
553   } else if (ExtraRegInfo[Reg].Stage == RS_Memory) {
554     // Memory operand should be considered last.
555     // Change the priority such that Memory operand are assigned in
556     // the reverse order that they came in.
557     // TODO: Make this a member variable and probably do something about hints.
558     static unsigned MemOp = 0;
559     Prio = MemOp++;
560   } else {
561     // Giant live ranges fall back to the global assignment heuristic, which
562     // prevents excessive spilling in pathological cases.
563     bool ReverseLocal = TRI->reverseLocalAssignment();
564     const TargetRegisterClass &RC = *MRI->getRegClass(Reg);
565     bool ForceGlobal = !ReverseLocal &&
566       (Size / SlotIndex::InstrDist) > (2 * RC.getNumRegs());
567 
568     if (ExtraRegInfo[Reg].Stage == RS_Assign && !ForceGlobal && !LI->empty() &&
569         LIS->intervalIsInOneMBB(*LI)) {
570       // Allocate original local ranges in linear instruction order. Since they
571       // are singly defined, this produces optimal coloring in the absence of
572       // global interference and other constraints.
573       if (!ReverseLocal)
574         Prio = LI->beginIndex().getInstrDistance(Indexes->getLastIndex());
575       else {
576         // Allocating bottom up may allow many short LRGs to be assigned first
577         // to one of the cheap registers. This could be much faster for very
578         // large blocks on targets with many physical registers.
579         Prio = Indexes->getZeroIndex().getInstrDistance(LI->endIndex());
580       }
581       Prio |= RC.AllocationPriority << 24;
582     } else {
583       // Allocate global and split ranges in long->short order. Long ranges that
584       // don't fit should be spilled (or split) ASAP so they don't create
585       // interference.  Mark a bit to prioritize global above local ranges.
586       Prio = (1u << 29) + Size;
587     }
588     // Mark a higher bit to prioritize global and local above RS_Split.
589     Prio |= (1u << 31);
590 
591     // Boost ranges that have a physical register hint.
592     if (VRM->hasKnownPreference(Reg))
593       Prio |= (1u << 30);
594   }
595   // The virtual register number is a tie breaker for same-sized ranges.
596   // Give lower vreg numbers higher priority to assign them first.
597   CurQueue.push(std::make_pair(Prio, ~Reg));
598 }
599 
dequeue()600 LiveInterval *RAGreedy::dequeue() { return dequeue(Queue); }
601 
dequeue(PQueue & CurQueue)602 LiveInterval *RAGreedy::dequeue(PQueue &CurQueue) {
603   if (CurQueue.empty())
604     return nullptr;
605   LiveInterval *LI = &LIS->getInterval(~CurQueue.top().second);
606   CurQueue.pop();
607   return LI;
608 }
609 
610 
611 //===----------------------------------------------------------------------===//
612 //                            Direct Assignment
613 //===----------------------------------------------------------------------===//
614 
615 /// tryAssign - Try to assign VirtReg to an available register.
tryAssign(LiveInterval & VirtReg,AllocationOrder & Order,SmallVectorImpl<unsigned> & NewVRegs)616 unsigned RAGreedy::tryAssign(LiveInterval &VirtReg,
617                              AllocationOrder &Order,
618                              SmallVectorImpl<unsigned> &NewVRegs) {
619   Order.rewind();
620   unsigned PhysReg;
621   while ((PhysReg = Order.next()))
622     if (!Matrix->checkInterference(VirtReg, PhysReg))
623       break;
624   if (!PhysReg || Order.isHint())
625     return PhysReg;
626 
627   // PhysReg is available, but there may be a better choice.
628 
629   // If we missed a simple hint, try to cheaply evict interference from the
630   // preferred register.
631   if (unsigned Hint = MRI->getSimpleHint(VirtReg.reg))
632     if (Order.isHint(Hint)) {
633       DEBUG(dbgs() << "missed hint " << PrintReg(Hint, TRI) << '\n');
634       EvictionCost MaxCost;
635       MaxCost.setBrokenHints(1);
636       if (canEvictInterference(VirtReg, Hint, true, MaxCost)) {
637         evictInterference(VirtReg, Hint, NewVRegs);
638         return Hint;
639       }
640     }
641 
642   // Try to evict interference from a cheaper alternative.
643   unsigned Cost = TRI->getCostPerUse(PhysReg);
644 
645   // Most registers have 0 additional cost.
646   if (!Cost)
647     return PhysReg;
648 
649   DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " is available at cost " << Cost
650                << '\n');
651   unsigned CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost);
652   return CheapReg ? CheapReg : PhysReg;
653 }
654 
655 
656 //===----------------------------------------------------------------------===//
657 //                         Interference eviction
658 //===----------------------------------------------------------------------===//
659 
canReassign(LiveInterval & VirtReg,unsigned PrevReg)660 unsigned RAGreedy::canReassign(LiveInterval &VirtReg, unsigned PrevReg) {
661   AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo, Matrix);
662   unsigned PhysReg;
663   while ((PhysReg = Order.next())) {
664     if (PhysReg == PrevReg)
665       continue;
666 
667     MCRegUnitIterator Units(PhysReg, TRI);
668     for (; Units.isValid(); ++Units) {
669       // Instantiate a "subquery", not to be confused with the Queries array.
670       LiveIntervalUnion::Query subQ(&VirtReg, &Matrix->getLiveUnions()[*Units]);
671       if (subQ.checkInterference())
672         break;
673     }
674     // If no units have interference, break out with the current PhysReg.
675     if (!Units.isValid())
676       break;
677   }
678   if (PhysReg)
679     DEBUG(dbgs() << "can reassign: " << VirtReg << " from "
680           << PrintReg(PrevReg, TRI) << " to " << PrintReg(PhysReg, TRI)
681           << '\n');
682   return PhysReg;
683 }
684 
685 /// shouldEvict - determine if A should evict the assigned live range B. The
686 /// eviction policy defined by this function together with the allocation order
687 /// defined by enqueue() decides which registers ultimately end up being split
688 /// and spilled.
689 ///
690 /// Cascade numbers are used to prevent infinite loops if this function is a
691 /// cyclic relation.
692 ///
693 /// @param A          The live range to be assigned.
694 /// @param IsHint     True when A is about to be assigned to its preferred
695 ///                   register.
696 /// @param B          The live range to be evicted.
697 /// @param BreaksHint True when B is already assigned to its preferred register.
shouldEvict(LiveInterval & A,bool IsHint,LiveInterval & B,bool BreaksHint)698 bool RAGreedy::shouldEvict(LiveInterval &A, bool IsHint,
699                            LiveInterval &B, bool BreaksHint) {
700   bool CanSplit = getStage(B) < RS_Spill;
701 
702   // Be fairly aggressive about following hints as long as the evictee can be
703   // split.
704   if (CanSplit && IsHint && !BreaksHint)
705     return true;
706 
707   if (A.weight > B.weight) {
708     DEBUG(dbgs() << "should evict: " << B << " w= " << B.weight << '\n');
709     return true;
710   }
711   return false;
712 }
713 
714 /// canEvictInterference - Return true if all interferences between VirtReg and
715 /// PhysReg can be evicted.
716 ///
717 /// @param VirtReg Live range that is about to be assigned.
718 /// @param PhysReg Desired register for assignment.
719 /// @param IsHint  True when PhysReg is VirtReg's preferred register.
720 /// @param MaxCost Only look for cheaper candidates and update with new cost
721 ///                when returning true.
722 /// @returns True when interference can be evicted cheaper than MaxCost.
canEvictInterference(LiveInterval & VirtReg,unsigned PhysReg,bool IsHint,EvictionCost & MaxCost)723 bool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg,
724                                     bool IsHint, EvictionCost &MaxCost) {
725   // It is only possible to evict virtual register interference.
726   if (Matrix->checkInterference(VirtReg, PhysReg) > LiveRegMatrix::IK_VirtReg)
727     return false;
728 
729   bool IsLocal = LIS->intervalIsInOneMBB(VirtReg);
730 
731   // Find VirtReg's cascade number. This will be unassigned if VirtReg was never
732   // involved in an eviction before. If a cascade number was assigned, deny
733   // evicting anything with the same or a newer cascade number. This prevents
734   // infinite eviction loops.
735   //
736   // This works out so a register without a cascade number is allowed to evict
737   // anything, and it can be evicted by anything.
738   unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade;
739   if (!Cascade)
740     Cascade = NextCascade;
741 
742   EvictionCost Cost;
743   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
744     LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
745     // If there is 10 or more interferences, chances are one is heavier.
746     if (Q.collectInterferingVRegs(10) >= 10)
747       return false;
748 
749     // Check if any interfering live range is heavier than MaxWeight.
750     for (unsigned i = Q.interferingVRegs().size(); i; --i) {
751       LiveInterval *Intf = Q.interferingVRegs()[i - 1];
752       assert(TargetRegisterInfo::isVirtualRegister(Intf->reg) &&
753              "Only expecting virtual register interference from query");
754       // Never evict spill products. They cannot split or spill.
755       if (getStage(*Intf) == RS_Done)
756         return false;
757       // Once a live range becomes small enough, it is urgent that we find a
758       // register for it. This is indicated by an infinite spill weight. These
759       // urgent live ranges get to evict almost anything.
760       //
761       // Also allow urgent evictions of unspillable ranges from a strictly
762       // larger allocation order.
763       bool Urgent = !VirtReg.isSpillable() &&
764         (Intf->isSpillable() ||
765          RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(VirtReg.reg)) <
766          RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(Intf->reg)));
767       // Only evict older cascades or live ranges without a cascade.
768       unsigned IntfCascade = ExtraRegInfo[Intf->reg].Cascade;
769       if (Cascade <= IntfCascade) {
770         if (!Urgent)
771           return false;
772         // We permit breaking cascades for urgent evictions. It should be the
773         // last resort, though, so make it really expensive.
774         Cost.BrokenHints += 10;
775       }
776       // Would this break a satisfied hint?
777       bool BreaksHint = VRM->hasPreferredPhys(Intf->reg);
778       // Update eviction cost.
779       Cost.BrokenHints += BreaksHint;
780       Cost.MaxWeight = std::max(Cost.MaxWeight, Intf->weight);
781       // Abort if this would be too expensive.
782       if (!(Cost < MaxCost))
783         return false;
784       if (Urgent)
785         continue;
786       // Apply the eviction policy for non-urgent evictions.
787       if (!shouldEvict(VirtReg, IsHint, *Intf, BreaksHint))
788         return false;
789       // If !MaxCost.isMax(), then we're just looking for a cheap register.
790       // Evicting another local live range in this case could lead to suboptimal
791       // coloring.
792       if (!MaxCost.isMax() && IsLocal && LIS->intervalIsInOneMBB(*Intf) &&
793           (!EnableLocalReassign || !canReassign(*Intf, PhysReg))) {
794         return false;
795       }
796     }
797   }
798   MaxCost = Cost;
799   return true;
800 }
801 
802 /// evictInterference - Evict any interferring registers that prevent VirtReg
803 /// from being assigned to Physreg. This assumes that canEvictInterference
804 /// returned true.
evictInterference(LiveInterval & VirtReg,unsigned PhysReg,SmallVectorImpl<unsigned> & NewVRegs)805 void RAGreedy::evictInterference(LiveInterval &VirtReg, unsigned PhysReg,
806                                  SmallVectorImpl<unsigned> &NewVRegs) {
807   // Make sure that VirtReg has a cascade number, and assign that cascade
808   // number to every evicted register. These live ranges than then only be
809   // evicted by a newer cascade, preventing infinite loops.
810   unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade;
811   if (!Cascade)
812     Cascade = ExtraRegInfo[VirtReg.reg].Cascade = NextCascade++;
813 
814   DEBUG(dbgs() << "evicting " << PrintReg(PhysReg, TRI)
815                << " interference: Cascade " << Cascade << '\n');
816 
817   // Collect all interfering virtregs first.
818   SmallVector<LiveInterval*, 8> Intfs;
819   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
820     LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
821     assert(Q.seenAllInterferences() && "Didn't check all interfererences.");
822     ArrayRef<LiveInterval*> IVR = Q.interferingVRegs();
823     Intfs.append(IVR.begin(), IVR.end());
824   }
825 
826   // Evict them second. This will invalidate the queries.
827   for (unsigned i = 0, e = Intfs.size(); i != e; ++i) {
828     LiveInterval *Intf = Intfs[i];
829     // The same VirtReg may be present in multiple RegUnits. Skip duplicates.
830     if (!VRM->hasPhys(Intf->reg))
831       continue;
832     Matrix->unassign(*Intf);
833     assert((ExtraRegInfo[Intf->reg].Cascade < Cascade ||
834             VirtReg.isSpillable() < Intf->isSpillable()) &&
835            "Cannot decrease cascade number, illegal eviction");
836     ExtraRegInfo[Intf->reg].Cascade = Cascade;
837     ++NumEvicted;
838     NewVRegs.push_back(Intf->reg);
839   }
840 }
841 
842 /// Returns true if the given \p PhysReg is a callee saved register and has not
843 /// been used for allocation yet.
isUnusedCalleeSavedReg(unsigned PhysReg) const844 bool RAGreedy::isUnusedCalleeSavedReg(unsigned PhysReg) const {
845   unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg);
846   if (CSR == 0)
847     return false;
848 
849   return !Matrix->isPhysRegUsed(PhysReg);
850 }
851 
852 /// tryEvict - Try to evict all interferences for a physreg.
853 /// @param  VirtReg Currently unassigned virtual register.
854 /// @param  Order   Physregs to try.
855 /// @return         Physreg to assign VirtReg, or 0.
tryEvict(LiveInterval & VirtReg,AllocationOrder & Order,SmallVectorImpl<unsigned> & NewVRegs,unsigned CostPerUseLimit)856 unsigned RAGreedy::tryEvict(LiveInterval &VirtReg,
857                             AllocationOrder &Order,
858                             SmallVectorImpl<unsigned> &NewVRegs,
859                             unsigned CostPerUseLimit) {
860   NamedRegionTimer T("Evict", TimerGroupName, TimePassesIsEnabled);
861 
862   // Keep track of the cheapest interference seen so far.
863   EvictionCost BestCost;
864   BestCost.setMax();
865   unsigned BestPhys = 0;
866   unsigned OrderLimit = Order.getOrder().size();
867 
868   // When we are just looking for a reduced cost per use, don't break any
869   // hints, and only evict smaller spill weights.
870   if (CostPerUseLimit < ~0u) {
871     BestCost.BrokenHints = 0;
872     BestCost.MaxWeight = VirtReg.weight;
873 
874     // Check of any registers in RC are below CostPerUseLimit.
875     const TargetRegisterClass *RC = MRI->getRegClass(VirtReg.reg);
876     unsigned MinCost = RegClassInfo.getMinCost(RC);
877     if (MinCost >= CostPerUseLimit) {
878       DEBUG(dbgs() << TRI->getRegClassName(RC) << " minimum cost = " << MinCost
879                    << ", no cheaper registers to be found.\n");
880       return 0;
881     }
882 
883     // It is normal for register classes to have a long tail of registers with
884     // the same cost. We don't need to look at them if they're too expensive.
885     if (TRI->getCostPerUse(Order.getOrder().back()) >= CostPerUseLimit) {
886       OrderLimit = RegClassInfo.getLastCostChange(RC);
887       DEBUG(dbgs() << "Only trying the first " << OrderLimit << " regs.\n");
888     }
889   }
890 
891   Order.rewind();
892   while (unsigned PhysReg = Order.next(OrderLimit)) {
893     if (TRI->getCostPerUse(PhysReg) >= CostPerUseLimit)
894       continue;
895     // The first use of a callee-saved register in a function has cost 1.
896     // Don't start using a CSR when the CostPerUseLimit is low.
897     if (CostPerUseLimit == 1 && isUnusedCalleeSavedReg(PhysReg)) {
898       DEBUG(dbgs() << PrintReg(PhysReg, TRI) << " would clobber CSR "
899             << PrintReg(RegClassInfo.getLastCalleeSavedAlias(PhysReg), TRI)
900             << '\n');
901       continue;
902     }
903 
904     if (!canEvictInterference(VirtReg, PhysReg, false, BestCost))
905       continue;
906 
907     // Best so far.
908     BestPhys = PhysReg;
909 
910     // Stop if the hint can be used.
911     if (Order.isHint())
912       break;
913   }
914 
915   if (!BestPhys)
916     return 0;
917 
918   evictInterference(VirtReg, BestPhys, NewVRegs);
919   return BestPhys;
920 }
921 
922 
923 //===----------------------------------------------------------------------===//
924 //                              Region Splitting
925 //===----------------------------------------------------------------------===//
926 
927 /// addSplitConstraints - Fill out the SplitConstraints vector based on the
928 /// interference pattern in Physreg and its aliases. Add the constraints to
929 /// SpillPlacement and return the static cost of this split in Cost, assuming
930 /// that all preferences in SplitConstraints are met.
931 /// Return false if there are no bundles with positive bias.
addSplitConstraints(InterferenceCache::Cursor Intf,BlockFrequency & Cost)932 bool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf,
933                                    BlockFrequency &Cost) {
934   ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
935 
936   // Reset interference dependent info.
937   SplitConstraints.resize(UseBlocks.size());
938   BlockFrequency StaticCost = 0;
939   for (unsigned i = 0; i != UseBlocks.size(); ++i) {
940     const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
941     SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
942 
943     BC.Number = BI.MBB->getNumber();
944     Intf.moveToBlock(BC.Number);
945     BC.Entry = BI.LiveIn ? SpillPlacement::PrefReg : SpillPlacement::DontCare;
946     BC.Exit = BI.LiveOut ? SpillPlacement::PrefReg : SpillPlacement::DontCare;
947     BC.ChangesValue = BI.FirstDef.isValid();
948 
949     if (!Intf.hasInterference())
950       continue;
951 
952     // Number of spill code instructions to insert.
953     unsigned Ins = 0;
954 
955     // Interference for the live-in value.
956     if (BI.LiveIn) {
957       if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number))
958         BC.Entry = SpillPlacement::MustSpill, ++Ins;
959       else if (Intf.first() < BI.FirstInstr)
960         BC.Entry = SpillPlacement::PrefSpill, ++Ins;
961       else if (Intf.first() < BI.LastInstr)
962         ++Ins;
963     }
964 
965     // Interference for the live-out value.
966     if (BI.LiveOut) {
967       if (Intf.last() >= SA->getLastSplitPoint(BC.Number))
968         BC.Exit = SpillPlacement::MustSpill, ++Ins;
969       else if (Intf.last() > BI.LastInstr)
970         BC.Exit = SpillPlacement::PrefSpill, ++Ins;
971       else if (Intf.last() > BI.FirstInstr)
972         ++Ins;
973     }
974 
975     // Accumulate the total frequency of inserted spill code.
976     while (Ins--)
977       StaticCost += SpillPlacer->getBlockFrequency(BC.Number);
978   }
979   Cost = StaticCost;
980 
981   // Add constraints for use-blocks. Note that these are the only constraints
982   // that may add a positive bias, it is downhill from here.
983   SpillPlacer->addConstraints(SplitConstraints);
984   return SpillPlacer->scanActiveBundles();
985 }
986 
987 
988 /// addThroughConstraints - Add constraints and links to SpillPlacer from the
989 /// live-through blocks in Blocks.
addThroughConstraints(InterferenceCache::Cursor Intf,ArrayRef<unsigned> Blocks)990 void RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf,
991                                      ArrayRef<unsigned> Blocks) {
992   const unsigned GroupSize = 8;
993   SpillPlacement::BlockConstraint BCS[GroupSize];
994   unsigned TBS[GroupSize];
995   unsigned B = 0, T = 0;
996 
997   for (unsigned i = 0; i != Blocks.size(); ++i) {
998     unsigned Number = Blocks[i];
999     Intf.moveToBlock(Number);
1000 
1001     if (!Intf.hasInterference()) {
1002       assert(T < GroupSize && "Array overflow");
1003       TBS[T] = Number;
1004       if (++T == GroupSize) {
1005         SpillPlacer->addLinks(makeArrayRef(TBS, T));
1006         T = 0;
1007       }
1008       continue;
1009     }
1010 
1011     assert(B < GroupSize && "Array overflow");
1012     BCS[B].Number = Number;
1013 
1014     // Interference for the live-in value.
1015     if (Intf.first() <= Indexes->getMBBStartIdx(Number))
1016       BCS[B].Entry = SpillPlacement::MustSpill;
1017     else
1018       BCS[B].Entry = SpillPlacement::PrefSpill;
1019 
1020     // Interference for the live-out value.
1021     if (Intf.last() >= SA->getLastSplitPoint(Number))
1022       BCS[B].Exit = SpillPlacement::MustSpill;
1023     else
1024       BCS[B].Exit = SpillPlacement::PrefSpill;
1025 
1026     if (++B == GroupSize) {
1027       SpillPlacer->addConstraints(makeArrayRef(BCS, B));
1028       B = 0;
1029     }
1030   }
1031 
1032   SpillPlacer->addConstraints(makeArrayRef(BCS, B));
1033   SpillPlacer->addLinks(makeArrayRef(TBS, T));
1034 }
1035 
growRegion(GlobalSplitCandidate & Cand)1036 void RAGreedy::growRegion(GlobalSplitCandidate &Cand) {
1037   // Keep track of through blocks that have not been added to SpillPlacer.
1038   BitVector Todo = SA->getThroughBlocks();
1039   SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks;
1040   unsigned AddedTo = 0;
1041 #ifndef NDEBUG
1042   unsigned Visited = 0;
1043 #endif
1044 
1045   for (;;) {
1046     ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive();
1047     // Find new through blocks in the periphery of PrefRegBundles.
1048     for (int i = 0, e = NewBundles.size(); i != e; ++i) {
1049       unsigned Bundle = NewBundles[i];
1050       // Look at all blocks connected to Bundle in the full graph.
1051       ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle);
1052       for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end();
1053            I != E; ++I) {
1054         unsigned Block = *I;
1055         if (!Todo.test(Block))
1056           continue;
1057         Todo.reset(Block);
1058         // This is a new through block. Add it to SpillPlacer later.
1059         ActiveBlocks.push_back(Block);
1060 #ifndef NDEBUG
1061         ++Visited;
1062 #endif
1063       }
1064     }
1065     // Any new blocks to add?
1066     if (ActiveBlocks.size() == AddedTo)
1067       break;
1068 
1069     // Compute through constraints from the interference, or assume that all
1070     // through blocks prefer spilling when forming compact regions.
1071     auto NewBlocks = makeArrayRef(ActiveBlocks).slice(AddedTo);
1072     if (Cand.PhysReg)
1073       addThroughConstraints(Cand.Intf, NewBlocks);
1074     else
1075       // Provide a strong negative bias on through blocks to prevent unwanted
1076       // liveness on loop backedges.
1077       SpillPlacer->addPrefSpill(NewBlocks, /* Strong= */ true);
1078     AddedTo = ActiveBlocks.size();
1079 
1080     // Perhaps iterating can enable more bundles?
1081     SpillPlacer->iterate();
1082   }
1083   DEBUG(dbgs() << ", v=" << Visited);
1084 }
1085 
1086 /// calcCompactRegion - Compute the set of edge bundles that should be live
1087 /// when splitting the current live range into compact regions.  Compact
1088 /// regions can be computed without looking at interference.  They are the
1089 /// regions formed by removing all the live-through blocks from the live range.
1090 ///
1091 /// Returns false if the current live range is already compact, or if the
1092 /// compact regions would form single block regions anyway.
calcCompactRegion(GlobalSplitCandidate & Cand)1093 bool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) {
1094   // Without any through blocks, the live range is already compact.
1095   if (!SA->getNumThroughBlocks())
1096     return false;
1097 
1098   // Compact regions don't correspond to any physreg.
1099   Cand.reset(IntfCache, 0);
1100 
1101   DEBUG(dbgs() << "Compact region bundles");
1102 
1103   // Use the spill placer to determine the live bundles. GrowRegion pretends
1104   // that all the through blocks have interference when PhysReg is unset.
1105   SpillPlacer->prepare(Cand.LiveBundles);
1106 
1107   // The static split cost will be zero since Cand.Intf reports no interference.
1108   BlockFrequency Cost;
1109   if (!addSplitConstraints(Cand.Intf, Cost)) {
1110     DEBUG(dbgs() << ", none.\n");
1111     return false;
1112   }
1113 
1114   growRegion(Cand);
1115   SpillPlacer->finish();
1116 
1117   if (!Cand.LiveBundles.any()) {
1118     DEBUG(dbgs() << ", none.\n");
1119     return false;
1120   }
1121 
1122   DEBUG({
1123     for (int i = Cand.LiveBundles.find_first(); i>=0;
1124          i = Cand.LiveBundles.find_next(i))
1125     dbgs() << " EB#" << i;
1126     dbgs() << ".\n";
1127   });
1128   return true;
1129 }
1130 
1131 /// calcSpillCost - Compute how expensive it would be to split the live range in
1132 /// SA around all use blocks instead of forming bundle regions.
calcSpillCost()1133 BlockFrequency RAGreedy::calcSpillCost() {
1134   BlockFrequency Cost = 0;
1135   ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1136   for (unsigned i = 0; i != UseBlocks.size(); ++i) {
1137     const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
1138     unsigned Number = BI.MBB->getNumber();
1139     // We normally only need one spill instruction - a load or a store.
1140     Cost += SpillPlacer->getBlockFrequency(Number);
1141 
1142     // Unless the value is redefined in the block.
1143     if (BI.LiveIn && BI.LiveOut && BI.FirstDef)
1144       Cost += SpillPlacer->getBlockFrequency(Number);
1145   }
1146   return Cost;
1147 }
1148 
1149 /// calcGlobalSplitCost - Return the global split cost of following the split
1150 /// pattern in LiveBundles. This cost should be added to the local cost of the
1151 /// interference pattern in SplitConstraints.
1152 ///
calcGlobalSplitCost(GlobalSplitCandidate & Cand)1153 BlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand) {
1154   BlockFrequency GlobalCost = 0;
1155   const BitVector &LiveBundles = Cand.LiveBundles;
1156   ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1157   for (unsigned i = 0; i != UseBlocks.size(); ++i) {
1158     const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
1159     SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
1160     bool RegIn  = LiveBundles[Bundles->getBundle(BC.Number, 0)];
1161     bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, 1)];
1162     unsigned Ins = 0;
1163 
1164     if (BI.LiveIn)
1165       Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg);
1166     if (BI.LiveOut)
1167       Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg);
1168     while (Ins--)
1169       GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);
1170   }
1171 
1172   for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) {
1173     unsigned Number = Cand.ActiveBlocks[i];
1174     bool RegIn  = LiveBundles[Bundles->getBundle(Number, 0)];
1175     bool RegOut = LiveBundles[Bundles->getBundle(Number, 1)];
1176     if (!RegIn && !RegOut)
1177       continue;
1178     if (RegIn && RegOut) {
1179       // We need double spill code if this block has interference.
1180       Cand.Intf.moveToBlock(Number);
1181       if (Cand.Intf.hasInterference()) {
1182         GlobalCost += SpillPlacer->getBlockFrequency(Number);
1183         GlobalCost += SpillPlacer->getBlockFrequency(Number);
1184       }
1185       continue;
1186     }
1187     // live-in / stack-out or stack-in live-out.
1188     GlobalCost += SpillPlacer->getBlockFrequency(Number);
1189   }
1190   return GlobalCost;
1191 }
1192 
1193 /// splitAroundRegion - Split the current live range around the regions
1194 /// determined by BundleCand and GlobalCand.
1195 ///
1196 /// Before calling this function, GlobalCand and BundleCand must be initialized
1197 /// so each bundle is assigned to a valid candidate, or NoCand for the
1198 /// stack-bound bundles.  The shared SA/SE SplitAnalysis and SplitEditor
1199 /// objects must be initialized for the current live range, and intervals
1200 /// created for the used candidates.
1201 ///
1202 /// @param LREdit    The LiveRangeEdit object handling the current split.
1203 /// @param UsedCands List of used GlobalCand entries. Every BundleCand value
1204 ///                  must appear in this list.
splitAroundRegion(LiveRangeEdit & LREdit,ArrayRef<unsigned> UsedCands)1205 void RAGreedy::splitAroundRegion(LiveRangeEdit &LREdit,
1206                                  ArrayRef<unsigned> UsedCands) {
1207   // These are the intervals created for new global ranges. We may create more
1208   // intervals for local ranges.
1209   const unsigned NumGlobalIntvs = LREdit.size();
1210   DEBUG(dbgs() << "splitAroundRegion with " << NumGlobalIntvs << " globals.\n");
1211   assert(NumGlobalIntvs && "No global intervals configured");
1212 
1213   // Isolate even single instructions when dealing with a proper sub-class.
1214   // That guarantees register class inflation for the stack interval because it
1215   // is all copies.
1216   unsigned Reg = SA->getParent().reg;
1217   bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg));
1218 
1219   // First handle all the blocks with uses.
1220   ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1221   for (unsigned i = 0; i != UseBlocks.size(); ++i) {
1222     const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
1223     unsigned Number = BI.MBB->getNumber();
1224     unsigned IntvIn = 0, IntvOut = 0;
1225     SlotIndex IntfIn, IntfOut;
1226     if (BI.LiveIn) {
1227       unsigned CandIn = BundleCand[Bundles->getBundle(Number, 0)];
1228       if (CandIn != NoCand) {
1229         GlobalSplitCandidate &Cand = GlobalCand[CandIn];
1230         IntvIn = Cand.IntvIdx;
1231         Cand.Intf.moveToBlock(Number);
1232         IntfIn = Cand.Intf.first();
1233       }
1234     }
1235     if (BI.LiveOut) {
1236       unsigned CandOut = BundleCand[Bundles->getBundle(Number, 1)];
1237       if (CandOut != NoCand) {
1238         GlobalSplitCandidate &Cand = GlobalCand[CandOut];
1239         IntvOut = Cand.IntvIdx;
1240         Cand.Intf.moveToBlock(Number);
1241         IntfOut = Cand.Intf.last();
1242       }
1243     }
1244 
1245     // Create separate intervals for isolated blocks with multiple uses.
1246     if (!IntvIn && !IntvOut) {
1247       DEBUG(dbgs() << "BB#" << BI.MBB->getNumber() << " isolated.\n");
1248       if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
1249         SE->splitSingleBlock(BI);
1250       continue;
1251     }
1252 
1253     if (IntvIn && IntvOut)
1254       SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut);
1255     else if (IntvIn)
1256       SE->splitRegInBlock(BI, IntvIn, IntfIn);
1257     else
1258       SE->splitRegOutBlock(BI, IntvOut, IntfOut);
1259   }
1260 
1261   // Handle live-through blocks. The relevant live-through blocks are stored in
1262   // the ActiveBlocks list with each candidate. We need to filter out
1263   // duplicates.
1264   BitVector Todo = SA->getThroughBlocks();
1265   for (unsigned c = 0; c != UsedCands.size(); ++c) {
1266     ArrayRef<unsigned> Blocks = GlobalCand[UsedCands[c]].ActiveBlocks;
1267     for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
1268       unsigned Number = Blocks[i];
1269       if (!Todo.test(Number))
1270         continue;
1271       Todo.reset(Number);
1272 
1273       unsigned IntvIn = 0, IntvOut = 0;
1274       SlotIndex IntfIn, IntfOut;
1275 
1276       unsigned CandIn = BundleCand[Bundles->getBundle(Number, 0)];
1277       if (CandIn != NoCand) {
1278         GlobalSplitCandidate &Cand = GlobalCand[CandIn];
1279         IntvIn = Cand.IntvIdx;
1280         Cand.Intf.moveToBlock(Number);
1281         IntfIn = Cand.Intf.first();
1282       }
1283 
1284       unsigned CandOut = BundleCand[Bundles->getBundle(Number, 1)];
1285       if (CandOut != NoCand) {
1286         GlobalSplitCandidate &Cand = GlobalCand[CandOut];
1287         IntvOut = Cand.IntvIdx;
1288         Cand.Intf.moveToBlock(Number);
1289         IntfOut = Cand.Intf.last();
1290       }
1291       if (!IntvIn && !IntvOut)
1292         continue;
1293       SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut);
1294     }
1295   }
1296 
1297   ++NumGlobalSplits;
1298 
1299   SmallVector<unsigned, 8> IntvMap;
1300   SE->finish(&IntvMap);
1301   DebugVars->splitRegister(Reg, LREdit.regs(), *LIS);
1302 
1303   ExtraRegInfo.resize(MRI->getNumVirtRegs());
1304   unsigned OrigBlocks = SA->getNumLiveBlocks();
1305 
1306   // Sort out the new intervals created by splitting. We get four kinds:
1307   // - Remainder intervals should not be split again.
1308   // - Candidate intervals can be assigned to Cand.PhysReg.
1309   // - Block-local splits are candidates for local splitting.
1310   // - DCE leftovers should go back on the queue.
1311   for (unsigned i = 0, e = LREdit.size(); i != e; ++i) {
1312     LiveInterval &Reg = LIS->getInterval(LREdit.get(i));
1313 
1314     // Ignore old intervals from DCE.
1315     if (getStage(Reg) != RS_New)
1316       continue;
1317 
1318     // Remainder interval. Don't try splitting again, spill if it doesn't
1319     // allocate.
1320     if (IntvMap[i] == 0) {
1321       setStage(Reg, RS_Spill);
1322       continue;
1323     }
1324 
1325     // Global intervals. Allow repeated splitting as long as the number of live
1326     // blocks is strictly decreasing.
1327     if (IntvMap[i] < NumGlobalIntvs) {
1328       if (SA->countLiveBlocks(&Reg) >= OrigBlocks) {
1329         DEBUG(dbgs() << "Main interval covers the same " << OrigBlocks
1330                      << " blocks as original.\n");
1331         // Don't allow repeated splitting as a safe guard against looping.
1332         setStage(Reg, RS_Split2);
1333       }
1334       continue;
1335     }
1336 
1337     // Other intervals are treated as new. This includes local intervals created
1338     // for blocks with multiple uses, and anything created by DCE.
1339   }
1340 
1341   if (VerifyEnabled)
1342     MF->verify(this, "After splitting live range around region");
1343 }
1344 
tryRegionSplit(LiveInterval & VirtReg,AllocationOrder & Order,SmallVectorImpl<unsigned> & NewVRegs)1345 unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
1346                                   SmallVectorImpl<unsigned> &NewVRegs) {
1347   unsigned NumCands = 0;
1348   BlockFrequency BestCost;
1349 
1350   // Check if we can split this live range around a compact region.
1351   bool HasCompact = calcCompactRegion(GlobalCand.front());
1352   if (HasCompact) {
1353     // Yes, keep GlobalCand[0] as the compact region candidate.
1354     NumCands = 1;
1355     BestCost = BlockFrequency::getMaxFrequency();
1356   } else {
1357     // No benefit from the compact region, our fallback will be per-block
1358     // splitting. Make sure we find a solution that is cheaper than spilling.
1359     BestCost = calcSpillCost();
1360     DEBUG(dbgs() << "Cost of isolating all blocks = ";
1361                  MBFI->printBlockFreq(dbgs(), BestCost) << '\n');
1362   }
1363 
1364   unsigned BestCand =
1365       calculateRegionSplitCost(VirtReg, Order, BestCost, NumCands,
1366                                false/*IgnoreCSR*/);
1367 
1368   // No solutions found, fall back to single block splitting.
1369   if (!HasCompact && BestCand == NoCand)
1370     return 0;
1371 
1372   return doRegionSplit(VirtReg, BestCand, HasCompact, NewVRegs);
1373 }
1374 
calculateRegionSplitCost(LiveInterval & VirtReg,AllocationOrder & Order,BlockFrequency & BestCost,unsigned & NumCands,bool IgnoreCSR)1375 unsigned RAGreedy::calculateRegionSplitCost(LiveInterval &VirtReg,
1376                                             AllocationOrder &Order,
1377                                             BlockFrequency &BestCost,
1378                                             unsigned &NumCands,
1379                                             bool IgnoreCSR) {
1380   unsigned BestCand = NoCand;
1381   Order.rewind();
1382   while (unsigned PhysReg = Order.next()) {
1383     if (IgnoreCSR && isUnusedCalleeSavedReg(PhysReg))
1384       continue;
1385 
1386     // Discard bad candidates before we run out of interference cache cursors.
1387     // This will only affect register classes with a lot of registers (>32).
1388     if (NumCands == IntfCache.getMaxCursors()) {
1389       unsigned WorstCount = ~0u;
1390       unsigned Worst = 0;
1391       for (unsigned i = 0; i != NumCands; ++i) {
1392         if (i == BestCand || !GlobalCand[i].PhysReg)
1393           continue;
1394         unsigned Count = GlobalCand[i].LiveBundles.count();
1395         if (Count < WorstCount)
1396           Worst = i, WorstCount = Count;
1397       }
1398       --NumCands;
1399       GlobalCand[Worst] = GlobalCand[NumCands];
1400       if (BestCand == NumCands)
1401         BestCand = Worst;
1402     }
1403 
1404     if (GlobalCand.size() <= NumCands)
1405       GlobalCand.resize(NumCands+1);
1406     GlobalSplitCandidate &Cand = GlobalCand[NumCands];
1407     Cand.reset(IntfCache, PhysReg);
1408 
1409     SpillPlacer->prepare(Cand.LiveBundles);
1410     BlockFrequency Cost;
1411     if (!addSplitConstraints(Cand.Intf, Cost)) {
1412       DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tno positive bundles\n");
1413       continue;
1414     }
1415     DEBUG(dbgs() << PrintReg(PhysReg, TRI) << "\tstatic = ";
1416                  MBFI->printBlockFreq(dbgs(), Cost));
1417     if (Cost >= BestCost) {
1418       DEBUG({
1419         if (BestCand == NoCand)
1420           dbgs() << " worse than no bundles\n";
1421         else
1422           dbgs() << " worse than "
1423                  << PrintReg(GlobalCand[BestCand].PhysReg, TRI) << '\n';
1424       });
1425       continue;
1426     }
1427     growRegion(Cand);
1428 
1429     SpillPlacer->finish();
1430 
1431     // No live bundles, defer to splitSingleBlocks().
1432     if (!Cand.LiveBundles.any()) {
1433       DEBUG(dbgs() << " no bundles.\n");
1434       continue;
1435     }
1436 
1437     Cost += calcGlobalSplitCost(Cand);
1438     DEBUG({
1439       dbgs() << ", total = "; MBFI->printBlockFreq(dbgs(), Cost)
1440                                 << " with bundles";
1441       for (int i = Cand.LiveBundles.find_first(); i>=0;
1442            i = Cand.LiveBundles.find_next(i))
1443         dbgs() << " EB#" << i;
1444       dbgs() << ".\n";
1445     });
1446     if (Cost < BestCost) {
1447       BestCand = NumCands;
1448       BestCost = Cost;
1449     }
1450     ++NumCands;
1451   }
1452   return BestCand;
1453 }
1454 
doRegionSplit(LiveInterval & VirtReg,unsigned BestCand,bool HasCompact,SmallVectorImpl<unsigned> & NewVRegs)1455 unsigned RAGreedy::doRegionSplit(LiveInterval &VirtReg, unsigned BestCand,
1456                                  bool HasCompact,
1457                                  SmallVectorImpl<unsigned> &NewVRegs) {
1458   SmallVector<unsigned, 8> UsedCands;
1459   // Prepare split editor.
1460   LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this);
1461   SE->reset(LREdit, SplitSpillMode);
1462 
1463   // Assign all edge bundles to the preferred candidate, or NoCand.
1464   BundleCand.assign(Bundles->getNumBundles(), NoCand);
1465 
1466   // Assign bundles for the best candidate region.
1467   if (BestCand != NoCand) {
1468     GlobalSplitCandidate &Cand = GlobalCand[BestCand];
1469     if (unsigned B = Cand.getBundles(BundleCand, BestCand)) {
1470       UsedCands.push_back(BestCand);
1471       Cand.IntvIdx = SE->openIntv();
1472       DEBUG(dbgs() << "Split for " << PrintReg(Cand.PhysReg, TRI) << " in "
1473                    << B << " bundles, intv " << Cand.IntvIdx << ".\n");
1474       (void)B;
1475     }
1476   }
1477 
1478   // Assign bundles for the compact region.
1479   if (HasCompact) {
1480     GlobalSplitCandidate &Cand = GlobalCand.front();
1481     assert(!Cand.PhysReg && "Compact region has no physreg");
1482     if (unsigned B = Cand.getBundles(BundleCand, 0)) {
1483       UsedCands.push_back(0);
1484       Cand.IntvIdx = SE->openIntv();
1485       DEBUG(dbgs() << "Split for compact region in " << B << " bundles, intv "
1486                    << Cand.IntvIdx << ".\n");
1487       (void)B;
1488     }
1489   }
1490 
1491   splitAroundRegion(LREdit, UsedCands);
1492   return 0;
1493 }
1494 
1495 
1496 //===----------------------------------------------------------------------===//
1497 //                            Per-Block Splitting
1498 //===----------------------------------------------------------------------===//
1499 
1500 /// tryBlockSplit - Split a global live range around every block with uses. This
1501 /// creates a lot of local live ranges, that will be split by tryLocalSplit if
1502 /// they don't allocate.
tryBlockSplit(LiveInterval & VirtReg,AllocationOrder & Order,SmallVectorImpl<unsigned> & NewVRegs)1503 unsigned RAGreedy::tryBlockSplit(LiveInterval &VirtReg, AllocationOrder &Order,
1504                                  SmallVectorImpl<unsigned> &NewVRegs) {
1505   assert(&SA->getParent() == &VirtReg && "Live range wasn't analyzed");
1506   unsigned Reg = VirtReg.reg;
1507   bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg));
1508   LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this);
1509   SE->reset(LREdit, SplitSpillMode);
1510   ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1511   for (unsigned i = 0; i != UseBlocks.size(); ++i) {
1512     const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
1513     if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
1514       SE->splitSingleBlock(BI);
1515   }
1516   // No blocks were split.
1517   if (LREdit.empty())
1518     return 0;
1519 
1520   // We did split for some blocks.
1521   SmallVector<unsigned, 8> IntvMap;
1522   SE->finish(&IntvMap);
1523 
1524   // Tell LiveDebugVariables about the new ranges.
1525   DebugVars->splitRegister(Reg, LREdit.regs(), *LIS);
1526 
1527   ExtraRegInfo.resize(MRI->getNumVirtRegs());
1528 
1529   // Sort out the new intervals created by splitting. The remainder interval
1530   // goes straight to spilling, the new local ranges get to stay RS_New.
1531   for (unsigned i = 0, e = LREdit.size(); i != e; ++i) {
1532     LiveInterval &LI = LIS->getInterval(LREdit.get(i));
1533     if (getStage(LI) == RS_New && IntvMap[i] == 0)
1534       setStage(LI, RS_Spill);
1535   }
1536 
1537   if (VerifyEnabled)
1538     MF->verify(this, "After splitting live range around basic blocks");
1539   return 0;
1540 }
1541 
1542 
1543 //===----------------------------------------------------------------------===//
1544 //                         Per-Instruction Splitting
1545 //===----------------------------------------------------------------------===//
1546 
1547 /// Get the number of allocatable registers that match the constraints of \p Reg
1548 /// on \p MI and that are also in \p SuperRC.
getNumAllocatableRegsForConstraints(const MachineInstr * MI,unsigned Reg,const TargetRegisterClass * SuperRC,const TargetInstrInfo * TII,const TargetRegisterInfo * TRI,const RegisterClassInfo & RCI)1549 static unsigned getNumAllocatableRegsForConstraints(
1550     const MachineInstr *MI, unsigned Reg, const TargetRegisterClass *SuperRC,
1551     const TargetInstrInfo *TII, const TargetRegisterInfo *TRI,
1552     const RegisterClassInfo &RCI) {
1553   assert(SuperRC && "Invalid register class");
1554 
1555   const TargetRegisterClass *ConstrainedRC =
1556       MI->getRegClassConstraintEffectForVReg(Reg, SuperRC, TII, TRI,
1557                                              /* ExploreBundle */ true);
1558   if (!ConstrainedRC)
1559     return 0;
1560   return RCI.getNumAllocatableRegs(ConstrainedRC);
1561 }
1562 
1563 /// tryInstructionSplit - Split a live range around individual instructions.
1564 /// This is normally not worthwhile since the spiller is doing essentially the
1565 /// same thing. However, when the live range is in a constrained register
1566 /// class, it may help to insert copies such that parts of the live range can
1567 /// be moved to a larger register class.
1568 ///
1569 /// This is similar to spilling to a larger register class.
1570 unsigned
tryInstructionSplit(LiveInterval & VirtReg,AllocationOrder & Order,SmallVectorImpl<unsigned> & NewVRegs)1571 RAGreedy::tryInstructionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
1572                               SmallVectorImpl<unsigned> &NewVRegs) {
1573   const TargetRegisterClass *CurRC = MRI->getRegClass(VirtReg.reg);
1574   // There is no point to this if there are no larger sub-classes.
1575   if (!RegClassInfo.isProperSubClass(CurRC))
1576     return 0;
1577 
1578   // Always enable split spill mode, since we're effectively spilling to a
1579   // register.
1580   LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this);
1581   SE->reset(LREdit, SplitEditor::SM_Size);
1582 
1583   ArrayRef<SlotIndex> Uses = SA->getUseSlots();
1584   if (Uses.size() <= 1)
1585     return 0;
1586 
1587   DEBUG(dbgs() << "Split around " << Uses.size() << " individual instrs.\n");
1588 
1589   const TargetRegisterClass *SuperRC =
1590       TRI->getLargestLegalSuperClass(CurRC, *MF);
1591   unsigned SuperRCNumAllocatableRegs = RCI.getNumAllocatableRegs(SuperRC);
1592   // Split around every non-copy instruction if this split will relax
1593   // the constraints on the virtual register.
1594   // Otherwise, splitting just inserts uncoalescable copies that do not help
1595   // the allocation.
1596   for (unsigned i = 0; i != Uses.size(); ++i) {
1597     if (const MachineInstr *MI = Indexes->getInstructionFromIndex(Uses[i]))
1598       if (MI->isFullCopy() ||
1599           SuperRCNumAllocatableRegs ==
1600               getNumAllocatableRegsForConstraints(MI, VirtReg.reg, SuperRC, TII,
1601                                                   TRI, RCI)) {
1602         DEBUG(dbgs() << "    skip:\t" << Uses[i] << '\t' << *MI);
1603         continue;
1604       }
1605     SE->openIntv();
1606     SlotIndex SegStart = SE->enterIntvBefore(Uses[i]);
1607     SlotIndex SegStop  = SE->leaveIntvAfter(Uses[i]);
1608     SE->useIntv(SegStart, SegStop);
1609   }
1610 
1611   if (LREdit.empty()) {
1612     DEBUG(dbgs() << "All uses were copies.\n");
1613     return 0;
1614   }
1615 
1616   SmallVector<unsigned, 8> IntvMap;
1617   SE->finish(&IntvMap);
1618   DebugVars->splitRegister(VirtReg.reg, LREdit.regs(), *LIS);
1619   ExtraRegInfo.resize(MRI->getNumVirtRegs());
1620 
1621   // Assign all new registers to RS_Spill. This was the last chance.
1622   setStage(LREdit.begin(), LREdit.end(), RS_Spill);
1623   return 0;
1624 }
1625 
1626 
1627 //===----------------------------------------------------------------------===//
1628 //                             Local Splitting
1629 //===----------------------------------------------------------------------===//
1630 
1631 
1632 /// calcGapWeights - Compute the maximum spill weight that needs to be evicted
1633 /// in order to use PhysReg between two entries in SA->UseSlots.
1634 ///
1635 /// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1].
1636 ///
calcGapWeights(unsigned PhysReg,SmallVectorImpl<float> & GapWeight)1637 void RAGreedy::calcGapWeights(unsigned PhysReg,
1638                               SmallVectorImpl<float> &GapWeight) {
1639   assert(SA->getUseBlocks().size() == 1 && "Not a local interval");
1640   const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front();
1641   ArrayRef<SlotIndex> Uses = SA->getUseSlots();
1642   const unsigned NumGaps = Uses.size()-1;
1643 
1644   // Start and end points for the interference check.
1645   SlotIndex StartIdx =
1646     BI.LiveIn ? BI.FirstInstr.getBaseIndex() : BI.FirstInstr;
1647   SlotIndex StopIdx =
1648     BI.LiveOut ? BI.LastInstr.getBoundaryIndex() : BI.LastInstr;
1649 
1650   GapWeight.assign(NumGaps, 0.0f);
1651 
1652   // Add interference from each overlapping register.
1653   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
1654     if (!Matrix->query(const_cast<LiveInterval&>(SA->getParent()), *Units)
1655           .checkInterference())
1656       continue;
1657 
1658     // We know that VirtReg is a continuous interval from FirstInstr to
1659     // LastInstr, so we don't need InterferenceQuery.
1660     //
1661     // Interference that overlaps an instruction is counted in both gaps
1662     // surrounding the instruction. The exception is interference before
1663     // StartIdx and after StopIdx.
1664     //
1665     LiveIntervalUnion::SegmentIter IntI =
1666       Matrix->getLiveUnions()[*Units] .find(StartIdx);
1667     for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) {
1668       // Skip the gaps before IntI.
1669       while (Uses[Gap+1].getBoundaryIndex() < IntI.start())
1670         if (++Gap == NumGaps)
1671           break;
1672       if (Gap == NumGaps)
1673         break;
1674 
1675       // Update the gaps covered by IntI.
1676       const float weight = IntI.value()->weight;
1677       for (; Gap != NumGaps; ++Gap) {
1678         GapWeight[Gap] = std::max(GapWeight[Gap], weight);
1679         if (Uses[Gap+1].getBaseIndex() >= IntI.stop())
1680           break;
1681       }
1682       if (Gap == NumGaps)
1683         break;
1684     }
1685   }
1686 
1687   // Add fixed interference.
1688   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
1689     const LiveRange &LR = LIS->getRegUnit(*Units);
1690     LiveRange::const_iterator I = LR.find(StartIdx);
1691     LiveRange::const_iterator E = LR.end();
1692 
1693     // Same loop as above. Mark any overlapped gaps as HUGE_VALF.
1694     for (unsigned Gap = 0; I != E && I->start < StopIdx; ++I) {
1695       while (Uses[Gap+1].getBoundaryIndex() < I->start)
1696         if (++Gap == NumGaps)
1697           break;
1698       if (Gap == NumGaps)
1699         break;
1700 
1701       for (; Gap != NumGaps; ++Gap) {
1702         GapWeight[Gap] = llvm::huge_valf;
1703         if (Uses[Gap+1].getBaseIndex() >= I->end)
1704           break;
1705       }
1706       if (Gap == NumGaps)
1707         break;
1708     }
1709   }
1710 }
1711 
1712 /// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only
1713 /// basic block.
1714 ///
tryLocalSplit(LiveInterval & VirtReg,AllocationOrder & Order,SmallVectorImpl<unsigned> & NewVRegs)1715 unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order,
1716                                  SmallVectorImpl<unsigned> &NewVRegs) {
1717   assert(SA->getUseBlocks().size() == 1 && "Not a local interval");
1718   const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front();
1719 
1720   // Note that it is possible to have an interval that is live-in or live-out
1721   // while only covering a single block - A phi-def can use undef values from
1722   // predecessors, and the block could be a single-block loop.
1723   // We don't bother doing anything clever about such a case, we simply assume
1724   // that the interval is continuous from FirstInstr to LastInstr. We should
1725   // make sure that we don't do anything illegal to such an interval, though.
1726 
1727   ArrayRef<SlotIndex> Uses = SA->getUseSlots();
1728   if (Uses.size() <= 2)
1729     return 0;
1730   const unsigned NumGaps = Uses.size()-1;
1731 
1732   DEBUG({
1733     dbgs() << "tryLocalSplit: ";
1734     for (unsigned i = 0, e = Uses.size(); i != e; ++i)
1735       dbgs() << ' ' << Uses[i];
1736     dbgs() << '\n';
1737   });
1738 
1739   // If VirtReg is live across any register mask operands, compute a list of
1740   // gaps with register masks.
1741   SmallVector<unsigned, 8> RegMaskGaps;
1742   if (Matrix->checkRegMaskInterference(VirtReg)) {
1743     // Get regmask slots for the whole block.
1744     ArrayRef<SlotIndex> RMS = LIS->getRegMaskSlotsInBlock(BI.MBB->getNumber());
1745     DEBUG(dbgs() << RMS.size() << " regmasks in block:");
1746     // Constrain to VirtReg's live range.
1747     unsigned ri = std::lower_bound(RMS.begin(), RMS.end(),
1748                                    Uses.front().getRegSlot()) - RMS.begin();
1749     unsigned re = RMS.size();
1750     for (unsigned i = 0; i != NumGaps && ri != re; ++i) {
1751       // Look for Uses[i] <= RMS <= Uses[i+1].
1752       assert(!SlotIndex::isEarlierInstr(RMS[ri], Uses[i]));
1753       if (SlotIndex::isEarlierInstr(Uses[i+1], RMS[ri]))
1754         continue;
1755       // Skip a regmask on the same instruction as the last use. It doesn't
1756       // overlap the live range.
1757       if (SlotIndex::isSameInstr(Uses[i+1], RMS[ri]) && i+1 == NumGaps)
1758         break;
1759       DEBUG(dbgs() << ' ' << RMS[ri] << ':' << Uses[i] << '-' << Uses[i+1]);
1760       RegMaskGaps.push_back(i);
1761       // Advance ri to the next gap. A regmask on one of the uses counts in
1762       // both gaps.
1763       while (ri != re && SlotIndex::isEarlierInstr(RMS[ri], Uses[i+1]))
1764         ++ri;
1765     }
1766     DEBUG(dbgs() << '\n');
1767   }
1768 
1769   // Since we allow local split results to be split again, there is a risk of
1770   // creating infinite loops. It is tempting to require that the new live
1771   // ranges have less instructions than the original. That would guarantee
1772   // convergence, but it is too strict. A live range with 3 instructions can be
1773   // split 2+3 (including the COPY), and we want to allow that.
1774   //
1775   // Instead we use these rules:
1776   //
1777   // 1. Allow any split for ranges with getStage() < RS_Split2. (Except for the
1778   //    noop split, of course).
1779   // 2. Require progress be made for ranges with getStage() == RS_Split2. All
1780   //    the new ranges must have fewer instructions than before the split.
1781   // 3. New ranges with the same number of instructions are marked RS_Split2,
1782   //    smaller ranges are marked RS_New.
1783   //
1784   // These rules allow a 3 -> 2+3 split once, which we need. They also prevent
1785   // excessive splitting and infinite loops.
1786   //
1787   bool ProgressRequired = getStage(VirtReg) >= RS_Split2;
1788 
1789   // Best split candidate.
1790   unsigned BestBefore = NumGaps;
1791   unsigned BestAfter = 0;
1792   float BestDiff = 0;
1793 
1794   const float blockFreq =
1795     SpillPlacer->getBlockFrequency(BI.MBB->getNumber()).getFrequency() *
1796     (1.0f / MBFI->getEntryFreq());
1797   SmallVector<float, 8> GapWeight;
1798 
1799   Order.rewind();
1800   while (unsigned PhysReg = Order.next()) {
1801     // Keep track of the largest spill weight that would need to be evicted in
1802     // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1].
1803     calcGapWeights(PhysReg, GapWeight);
1804 
1805     // Remove any gaps with regmask clobbers.
1806     if (Matrix->checkRegMaskInterference(VirtReg, PhysReg))
1807       for (unsigned i = 0, e = RegMaskGaps.size(); i != e; ++i)
1808         GapWeight[RegMaskGaps[i]] = llvm::huge_valf;
1809 
1810     // Try to find the best sequence of gaps to close.
1811     // The new spill weight must be larger than any gap interference.
1812 
1813     // We will split before Uses[SplitBefore] and after Uses[SplitAfter].
1814     unsigned SplitBefore = 0, SplitAfter = 1;
1815 
1816     // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]).
1817     // It is the spill weight that needs to be evicted.
1818     float MaxGap = GapWeight[0];
1819 
1820     for (;;) {
1821       // Live before/after split?
1822       const bool LiveBefore = SplitBefore != 0 || BI.LiveIn;
1823       const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut;
1824 
1825       DEBUG(dbgs() << PrintReg(PhysReg, TRI) << ' '
1826                    << Uses[SplitBefore] << '-' << Uses[SplitAfter]
1827                    << " i=" << MaxGap);
1828 
1829       // Stop before the interval gets so big we wouldn't be making progress.
1830       if (!LiveBefore && !LiveAfter) {
1831         DEBUG(dbgs() << " all\n");
1832         break;
1833       }
1834       // Should the interval be extended or shrunk?
1835       bool Shrink = true;
1836 
1837       // How many gaps would the new range have?
1838       unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter;
1839 
1840       // Legally, without causing looping?
1841       bool Legal = !ProgressRequired || NewGaps < NumGaps;
1842 
1843       if (Legal && MaxGap < llvm::huge_valf) {
1844         // Estimate the new spill weight. Each instruction reads or writes the
1845         // register. Conservatively assume there are no read-modify-write
1846         // instructions.
1847         //
1848         // Try to guess the size of the new interval.
1849         const float EstWeight = normalizeSpillWeight(
1850             blockFreq * (NewGaps + 1),
1851             Uses[SplitBefore].distance(Uses[SplitAfter]) +
1852                 (LiveBefore + LiveAfter) * SlotIndex::InstrDist,
1853             1);
1854         // Would this split be possible to allocate?
1855         // Never allocate all gaps, we wouldn't be making progress.
1856         DEBUG(dbgs() << " w=" << EstWeight);
1857         if (EstWeight * Hysteresis >= MaxGap) {
1858           Shrink = false;
1859           float Diff = EstWeight - MaxGap;
1860           if (Diff > BestDiff) {
1861             DEBUG(dbgs() << " (best)");
1862             BestDiff = Hysteresis * Diff;
1863             BestBefore = SplitBefore;
1864             BestAfter = SplitAfter;
1865           }
1866         }
1867       }
1868 
1869       // Try to shrink.
1870       if (Shrink) {
1871         if (++SplitBefore < SplitAfter) {
1872           DEBUG(dbgs() << " shrink\n");
1873           // Recompute the max when necessary.
1874           if (GapWeight[SplitBefore - 1] >= MaxGap) {
1875             MaxGap = GapWeight[SplitBefore];
1876             for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i)
1877               MaxGap = std::max(MaxGap, GapWeight[i]);
1878           }
1879           continue;
1880         }
1881         MaxGap = 0;
1882       }
1883 
1884       // Try to extend the interval.
1885       if (SplitAfter >= NumGaps) {
1886         DEBUG(dbgs() << " end\n");
1887         break;
1888       }
1889 
1890       DEBUG(dbgs() << " extend\n");
1891       MaxGap = std::max(MaxGap, GapWeight[SplitAfter++]);
1892     }
1893   }
1894 
1895   // Didn't find any candidates?
1896   if (BestBefore == NumGaps)
1897     return 0;
1898 
1899   DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore]
1900                << '-' << Uses[BestAfter] << ", " << BestDiff
1901                << ", " << (BestAfter - BestBefore + 1) << " instrs\n");
1902 
1903   LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this);
1904   SE->reset(LREdit);
1905 
1906   SE->openIntv();
1907   SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]);
1908   SlotIndex SegStop  = SE->leaveIntvAfter(Uses[BestAfter]);
1909   SE->useIntv(SegStart, SegStop);
1910   SmallVector<unsigned, 8> IntvMap;
1911   SE->finish(&IntvMap);
1912   DebugVars->splitRegister(VirtReg.reg, LREdit.regs(), *LIS);
1913 
1914   // If the new range has the same number of instructions as before, mark it as
1915   // RS_Split2 so the next split will be forced to make progress. Otherwise,
1916   // leave the new intervals as RS_New so they can compete.
1917   bool LiveBefore = BestBefore != 0 || BI.LiveIn;
1918   bool LiveAfter = BestAfter != NumGaps || BI.LiveOut;
1919   unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter;
1920   if (NewGaps >= NumGaps) {
1921     DEBUG(dbgs() << "Tagging non-progress ranges: ");
1922     assert(!ProgressRequired && "Didn't make progress when it was required.");
1923     for (unsigned i = 0, e = IntvMap.size(); i != e; ++i)
1924       if (IntvMap[i] == 1) {
1925         setStage(LIS->getInterval(LREdit.get(i)), RS_Split2);
1926         DEBUG(dbgs() << PrintReg(LREdit.get(i)));
1927       }
1928     DEBUG(dbgs() << '\n');
1929   }
1930   ++NumLocalSplits;
1931 
1932   return 0;
1933 }
1934 
1935 //===----------------------------------------------------------------------===//
1936 //                          Live Range Splitting
1937 //===----------------------------------------------------------------------===//
1938 
1939 /// trySplit - Try to split VirtReg or one of its interferences, making it
1940 /// assignable.
1941 /// @return Physreg when VirtReg may be assigned and/or new NewVRegs.
trySplit(LiveInterval & VirtReg,AllocationOrder & Order,SmallVectorImpl<unsigned> & NewVRegs)1942 unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
1943                             SmallVectorImpl<unsigned>&NewVRegs) {
1944   // Ranges must be Split2 or less.
1945   if (getStage(VirtReg) >= RS_Spill)
1946     return 0;
1947 
1948   // Local intervals are handled separately.
1949   if (LIS->intervalIsInOneMBB(VirtReg)) {
1950     NamedRegionTimer T("Local Splitting", TimerGroupName, TimePassesIsEnabled);
1951     SA->analyze(&VirtReg);
1952     unsigned PhysReg = tryLocalSplit(VirtReg, Order, NewVRegs);
1953     if (PhysReg || !NewVRegs.empty())
1954       return PhysReg;
1955     return tryInstructionSplit(VirtReg, Order, NewVRegs);
1956   }
1957 
1958   NamedRegionTimer T("Global Splitting", TimerGroupName, TimePassesIsEnabled);
1959 
1960   SA->analyze(&VirtReg);
1961 
1962   // FIXME: SplitAnalysis may repair broken live ranges coming from the
1963   // coalescer. That may cause the range to become allocatable which means that
1964   // tryRegionSplit won't be making progress. This check should be replaced with
1965   // an assertion when the coalescer is fixed.
1966   if (SA->didRepairRange()) {
1967     // VirtReg has changed, so all cached queries are invalid.
1968     Matrix->invalidateVirtRegs();
1969     if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs))
1970       return PhysReg;
1971   }
1972 
1973   // First try to split around a region spanning multiple blocks. RS_Split2
1974   // ranges already made dubious progress with region splitting, so they go
1975   // straight to single block splitting.
1976   if (getStage(VirtReg) < RS_Split2) {
1977     unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
1978     if (PhysReg || !NewVRegs.empty())
1979       return PhysReg;
1980   }
1981 
1982   // Then isolate blocks.
1983   return tryBlockSplit(VirtReg, Order, NewVRegs);
1984 }
1985 
1986 //===----------------------------------------------------------------------===//
1987 //                          Last Chance Recoloring
1988 //===----------------------------------------------------------------------===//
1989 
1990 /// mayRecolorAllInterferences - Check if the virtual registers that
1991 /// interfere with \p VirtReg on \p PhysReg (or one of its aliases) may be
1992 /// recolored to free \p PhysReg.
1993 /// When true is returned, \p RecoloringCandidates has been augmented with all
1994 /// the live intervals that need to be recolored in order to free \p PhysReg
1995 /// for \p VirtReg.
1996 /// \p FixedRegisters contains all the virtual registers that cannot be
1997 /// recolored.
1998 bool
mayRecolorAllInterferences(unsigned PhysReg,LiveInterval & VirtReg,SmallLISet & RecoloringCandidates,const SmallVirtRegSet & FixedRegisters)1999 RAGreedy::mayRecolorAllInterferences(unsigned PhysReg, LiveInterval &VirtReg,
2000                                      SmallLISet &RecoloringCandidates,
2001                                      const SmallVirtRegSet &FixedRegisters) {
2002   const TargetRegisterClass *CurRC = MRI->getRegClass(VirtReg.reg);
2003 
2004   for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
2005     LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
2006     // If there is LastChanceRecoloringMaxInterference or more interferences,
2007     // chances are one would not be recolorable.
2008     if (Q.collectInterferingVRegs(LastChanceRecoloringMaxInterference) >=
2009         LastChanceRecoloringMaxInterference && !ExhaustiveSearch) {
2010       DEBUG(dbgs() << "Early abort: too many interferences.\n");
2011       CutOffInfo |= CO_Interf;
2012       return false;
2013     }
2014     for (unsigned i = Q.interferingVRegs().size(); i; --i) {
2015       LiveInterval *Intf = Q.interferingVRegs()[i - 1];
2016       // If Intf is done and sit on the same register class as VirtReg,
2017       // it would not be recolorable as it is in the same state as VirtReg.
2018       if ((getStage(*Intf) == RS_Done &&
2019            MRI->getRegClass(Intf->reg) == CurRC) ||
2020           FixedRegisters.count(Intf->reg)) {
2021         DEBUG(dbgs() << "Early abort: the inteference is not recolorable.\n");
2022         return false;
2023       }
2024       RecoloringCandidates.insert(Intf);
2025     }
2026   }
2027   return true;
2028 }
2029 
2030 /// tryLastChanceRecoloring - Try to assign a color to \p VirtReg by recoloring
2031 /// its interferences.
2032 /// Last chance recoloring chooses a color for \p VirtReg and recolors every
2033 /// virtual register that was using it. The recoloring process may recursively
2034 /// use the last chance recoloring. Therefore, when a virtual register has been
2035 /// assigned a color by this mechanism, it is marked as Fixed, i.e., it cannot
2036 /// be last-chance-recolored again during this recoloring "session".
2037 /// E.g.,
2038 /// Let
2039 /// vA can use {R1, R2    }
2040 /// vB can use {    R2, R3}
2041 /// vC can use {R1        }
2042 /// Where vA, vB, and vC cannot be split anymore (they are reloads for
2043 /// instance) and they all interfere.
2044 ///
2045 /// vA is assigned R1
2046 /// vB is assigned R2
2047 /// vC tries to evict vA but vA is already done.
2048 /// Regular register allocation fails.
2049 ///
2050 /// Last chance recoloring kicks in:
2051 /// vC does as if vA was evicted => vC uses R1.
2052 /// vC is marked as fixed.
2053 /// vA needs to find a color.
2054 /// None are available.
2055 /// vA cannot evict vC: vC is a fixed virtual register now.
2056 /// vA does as if vB was evicted => vA uses R2.
2057 /// vB needs to find a color.
2058 /// R3 is available.
2059 /// Recoloring => vC = R1, vA = R2, vB = R3
2060 ///
2061 /// \p Order defines the preferred allocation order for \p VirtReg.
2062 /// \p NewRegs will contain any new virtual register that have been created
2063 /// (split, spill) during the process and that must be assigned.
2064 /// \p FixedRegisters contains all the virtual registers that cannot be
2065 /// recolored.
2066 /// \p Depth gives the current depth of the last chance recoloring.
2067 /// \return a physical register that can be used for VirtReg or ~0u if none
2068 /// exists.
tryLastChanceRecoloring(LiveInterval & VirtReg,AllocationOrder & Order,SmallVectorImpl<unsigned> & NewVRegs,SmallVirtRegSet & FixedRegisters,unsigned Depth)2069 unsigned RAGreedy::tryLastChanceRecoloring(LiveInterval &VirtReg,
2070                                            AllocationOrder &Order,
2071                                            SmallVectorImpl<unsigned> &NewVRegs,
2072                                            SmallVirtRegSet &FixedRegisters,
2073                                            unsigned Depth) {
2074   DEBUG(dbgs() << "Try last chance recoloring for " << VirtReg << '\n');
2075   // Ranges must be Done.
2076   assert((getStage(VirtReg) >= RS_Done || !VirtReg.isSpillable()) &&
2077          "Last chance recoloring should really be last chance");
2078   // Set the max depth to LastChanceRecoloringMaxDepth.
2079   // We may want to reconsider that if we end up with a too large search space
2080   // for target with hundreds of registers.
2081   // Indeed, in that case we may want to cut the search space earlier.
2082   if (Depth >= LastChanceRecoloringMaxDepth && !ExhaustiveSearch) {
2083     DEBUG(dbgs() << "Abort because max depth has been reached.\n");
2084     CutOffInfo |= CO_Depth;
2085     return ~0u;
2086   }
2087 
2088   // Set of Live intervals that will need to be recolored.
2089   SmallLISet RecoloringCandidates;
2090   // Record the original mapping virtual register to physical register in case
2091   // the recoloring fails.
2092   DenseMap<unsigned, unsigned> VirtRegToPhysReg;
2093   // Mark VirtReg as fixed, i.e., it will not be recolored pass this point in
2094   // this recoloring "session".
2095   FixedRegisters.insert(VirtReg.reg);
2096 
2097   Order.rewind();
2098   while (unsigned PhysReg = Order.next()) {
2099     DEBUG(dbgs() << "Try to assign: " << VirtReg << " to "
2100                  << PrintReg(PhysReg, TRI) << '\n');
2101     RecoloringCandidates.clear();
2102     VirtRegToPhysReg.clear();
2103 
2104     // It is only possible to recolor virtual register interference.
2105     if (Matrix->checkInterference(VirtReg, PhysReg) >
2106         LiveRegMatrix::IK_VirtReg) {
2107       DEBUG(dbgs() << "Some inteferences are not with virtual registers.\n");
2108 
2109       continue;
2110     }
2111 
2112     // Early give up on this PhysReg if it is obvious we cannot recolor all
2113     // the interferences.
2114     if (!mayRecolorAllInterferences(PhysReg, VirtReg, RecoloringCandidates,
2115                                     FixedRegisters)) {
2116       DEBUG(dbgs() << "Some inteferences cannot be recolored.\n");
2117       continue;
2118     }
2119 
2120     // RecoloringCandidates contains all the virtual registers that interfer
2121     // with VirtReg on PhysReg (or one of its aliases).
2122     // Enqueue them for recoloring and perform the actual recoloring.
2123     PQueue RecoloringQueue;
2124     for (SmallLISet::iterator It = RecoloringCandidates.begin(),
2125                               EndIt = RecoloringCandidates.end();
2126          It != EndIt; ++It) {
2127       unsigned ItVirtReg = (*It)->reg;
2128       enqueue(RecoloringQueue, *It);
2129       assert(VRM->hasPhys(ItVirtReg) &&
2130              "Interferences are supposed to be with allocated vairables");
2131 
2132       // Record the current allocation.
2133       VirtRegToPhysReg[ItVirtReg] = VRM->getPhys(ItVirtReg);
2134       // unset the related struct.
2135       Matrix->unassign(**It);
2136     }
2137 
2138     // Do as if VirtReg was assigned to PhysReg so that the underlying
2139     // recoloring has the right information about the interferes and
2140     // available colors.
2141     Matrix->assign(VirtReg, PhysReg);
2142 
2143     // Save the current recoloring state.
2144     // If we cannot recolor all the interferences, we will have to start again
2145     // at this point for the next physical register.
2146     SmallVirtRegSet SaveFixedRegisters(FixedRegisters);
2147     if (tryRecoloringCandidates(RecoloringQueue, NewVRegs, FixedRegisters,
2148                                 Depth)) {
2149       // Do not mess up with the global assignment process.
2150       // I.e., VirtReg must be unassigned.
2151       Matrix->unassign(VirtReg);
2152       return PhysReg;
2153     }
2154 
2155     DEBUG(dbgs() << "Fail to assign: " << VirtReg << " to "
2156                  << PrintReg(PhysReg, TRI) << '\n');
2157 
2158     // The recoloring attempt failed, undo the changes.
2159     FixedRegisters = SaveFixedRegisters;
2160     Matrix->unassign(VirtReg);
2161 
2162     for (SmallLISet::iterator It = RecoloringCandidates.begin(),
2163                               EndIt = RecoloringCandidates.end();
2164          It != EndIt; ++It) {
2165       unsigned ItVirtReg = (*It)->reg;
2166       if (VRM->hasPhys(ItVirtReg))
2167         Matrix->unassign(**It);
2168       unsigned ItPhysReg = VirtRegToPhysReg[ItVirtReg];
2169       Matrix->assign(**It, ItPhysReg);
2170     }
2171   }
2172 
2173   // Last chance recoloring did not worked either, give up.
2174   return ~0u;
2175 }
2176 
2177 /// tryRecoloringCandidates - Try to assign a new color to every register
2178 /// in \RecoloringQueue.
2179 /// \p NewRegs will contain any new virtual register created during the
2180 /// recoloring process.
2181 /// \p FixedRegisters[in/out] contains all the registers that have been
2182 /// recolored.
2183 /// \return true if all virtual registers in RecoloringQueue were successfully
2184 /// recolored, false otherwise.
tryRecoloringCandidates(PQueue & RecoloringQueue,SmallVectorImpl<unsigned> & NewVRegs,SmallVirtRegSet & FixedRegisters,unsigned Depth)2185 bool RAGreedy::tryRecoloringCandidates(PQueue &RecoloringQueue,
2186                                        SmallVectorImpl<unsigned> &NewVRegs,
2187                                        SmallVirtRegSet &FixedRegisters,
2188                                        unsigned Depth) {
2189   while (!RecoloringQueue.empty()) {
2190     LiveInterval *LI = dequeue(RecoloringQueue);
2191     DEBUG(dbgs() << "Try to recolor: " << *LI << '\n');
2192     unsigned PhysReg;
2193     PhysReg = selectOrSplitImpl(*LI, NewVRegs, FixedRegisters, Depth + 1);
2194     if (PhysReg == ~0u || !PhysReg)
2195       return false;
2196     DEBUG(dbgs() << "Recoloring of " << *LI
2197                  << " succeeded with: " << PrintReg(PhysReg, TRI) << '\n');
2198     Matrix->assign(*LI, PhysReg);
2199     FixedRegisters.insert(LI->reg);
2200   }
2201   return true;
2202 }
2203 
2204 //===----------------------------------------------------------------------===//
2205 //                            Main Entry Point
2206 //===----------------------------------------------------------------------===//
2207 
selectOrSplit(LiveInterval & VirtReg,SmallVectorImpl<unsigned> & NewVRegs)2208 unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
2209                                  SmallVectorImpl<unsigned> &NewVRegs) {
2210   CutOffInfo = CO_None;
2211   LLVMContext &Ctx = MF->getFunction()->getContext();
2212   SmallVirtRegSet FixedRegisters;
2213   unsigned Reg = selectOrSplitImpl(VirtReg, NewVRegs, FixedRegisters);
2214   if (Reg == ~0U && (CutOffInfo != CO_None)) {
2215     uint8_t CutOffEncountered = CutOffInfo & (CO_Depth | CO_Interf);
2216     if (CutOffEncountered == CO_Depth)
2217       Ctx.emitError("register allocation failed: maximum depth for recoloring "
2218                     "reached. Use -fexhaustive-register-search to skip "
2219                     "cutoffs");
2220     else if (CutOffEncountered == CO_Interf)
2221       Ctx.emitError("register allocation failed: maximum interference for "
2222                     "recoloring reached. Use -fexhaustive-register-search "
2223                     "to skip cutoffs");
2224     else if (CutOffEncountered == (CO_Depth | CO_Interf))
2225       Ctx.emitError("register allocation failed: maximum interference and "
2226                     "depth for recoloring reached. Use "
2227                     "-fexhaustive-register-search to skip cutoffs");
2228   }
2229   return Reg;
2230 }
2231 
2232 /// Using a CSR for the first time has a cost because it causes push|pop
2233 /// to be added to prologue|epilogue. Splitting a cold section of the live
2234 /// range can have lower cost than using the CSR for the first time;
2235 /// Spilling a live range in the cold path can have lower cost than using
2236 /// the CSR for the first time. Returns the physical register if we decide
2237 /// to use the CSR; otherwise return 0.
tryAssignCSRFirstTime(LiveInterval & VirtReg,AllocationOrder & Order,unsigned PhysReg,unsigned & CostPerUseLimit,SmallVectorImpl<unsigned> & NewVRegs)2238 unsigned RAGreedy::tryAssignCSRFirstTime(LiveInterval &VirtReg,
2239                                          AllocationOrder &Order,
2240                                          unsigned PhysReg,
2241                                          unsigned &CostPerUseLimit,
2242                                          SmallVectorImpl<unsigned> &NewVRegs) {
2243   if (getStage(VirtReg) == RS_Spill && VirtReg.isSpillable()) {
2244     // We choose spill over using the CSR for the first time if the spill cost
2245     // is lower than CSRCost.
2246     SA->analyze(&VirtReg);
2247     if (calcSpillCost() >= CSRCost)
2248       return PhysReg;
2249 
2250     // We are going to spill, set CostPerUseLimit to 1 to make sure that
2251     // we will not use a callee-saved register in tryEvict.
2252     CostPerUseLimit = 1;
2253     return 0;
2254   }
2255   if (getStage(VirtReg) < RS_Split) {
2256     // We choose pre-splitting over using the CSR for the first time if
2257     // the cost of splitting is lower than CSRCost.
2258     SA->analyze(&VirtReg);
2259     unsigned NumCands = 0;
2260     BlockFrequency BestCost = CSRCost; // Don't modify CSRCost.
2261     unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, BestCost,
2262                                                  NumCands, true /*IgnoreCSR*/);
2263     if (BestCand == NoCand)
2264       // Use the CSR if we can't find a region split below CSRCost.
2265       return PhysReg;
2266 
2267     // Perform the actual pre-splitting.
2268     doRegionSplit(VirtReg, BestCand, false/*HasCompact*/, NewVRegs);
2269     return 0;
2270   }
2271   return PhysReg;
2272 }
2273 
aboutToRemoveInterval(LiveInterval & LI)2274 void RAGreedy::aboutToRemoveInterval(LiveInterval &LI) {
2275   // Do not keep invalid information around.
2276   SetOfBrokenHints.remove(&LI);
2277 }
2278 
initializeCSRCost()2279 void RAGreedy::initializeCSRCost() {
2280   // We use the larger one out of the command-line option and the value report
2281   // by TRI.
2282   CSRCost = BlockFrequency(
2283       std::max((unsigned)CSRFirstTimeCost, TRI->getCSRFirstUseCost()));
2284   if (!CSRCost.getFrequency())
2285     return;
2286 
2287   // Raw cost is relative to Entry == 2^14; scale it appropriately.
2288   uint64_t ActualEntry = MBFI->getEntryFreq();
2289   if (!ActualEntry) {
2290     CSRCost = 0;
2291     return;
2292   }
2293   uint64_t FixedEntry = 1 << 14;
2294   if (ActualEntry < FixedEntry)
2295     CSRCost *= BranchProbability(ActualEntry, FixedEntry);
2296   else if (ActualEntry <= UINT32_MAX)
2297     // Invert the fraction and divide.
2298     CSRCost /= BranchProbability(FixedEntry, ActualEntry);
2299   else
2300     // Can't use BranchProbability in general, since it takes 32-bit numbers.
2301     CSRCost = CSRCost.getFrequency() * (ActualEntry / FixedEntry);
2302 }
2303 
2304 /// \brief Collect the hint info for \p Reg.
2305 /// The results are stored into \p Out.
2306 /// \p Out is not cleared before being populated.
collectHintInfo(unsigned Reg,HintsInfo & Out)2307 void RAGreedy::collectHintInfo(unsigned Reg, HintsInfo &Out) {
2308   for (const MachineInstr &Instr : MRI->reg_nodbg_instructions(Reg)) {
2309     if (!Instr.isFullCopy())
2310       continue;
2311     // Look for the other end of the copy.
2312     unsigned OtherReg = Instr.getOperand(0).getReg();
2313     if (OtherReg == Reg) {
2314       OtherReg = Instr.getOperand(1).getReg();
2315       if (OtherReg == Reg)
2316         continue;
2317     }
2318     // Get the current assignment.
2319     unsigned OtherPhysReg = TargetRegisterInfo::isPhysicalRegister(OtherReg)
2320                                 ? OtherReg
2321                                 : VRM->getPhys(OtherReg);
2322     // Push the collected information.
2323     Out.push_back(HintInfo(MBFI->getBlockFreq(Instr.getParent()), OtherReg,
2324                            OtherPhysReg));
2325   }
2326 }
2327 
2328 /// \brief Using the given \p List, compute the cost of the broken hints if
2329 /// \p PhysReg was used.
2330 /// \return The cost of \p List for \p PhysReg.
getBrokenHintFreq(const HintsInfo & List,unsigned PhysReg)2331 BlockFrequency RAGreedy::getBrokenHintFreq(const HintsInfo &List,
2332                                            unsigned PhysReg) {
2333   BlockFrequency Cost = 0;
2334   for (const HintInfo &Info : List) {
2335     if (Info.PhysReg != PhysReg)
2336       Cost += Info.Freq;
2337   }
2338   return Cost;
2339 }
2340 
2341 /// \brief Using the register assigned to \p VirtReg, try to recolor
2342 /// all the live ranges that are copy-related with \p VirtReg.
2343 /// The recoloring is then propagated to all the live-ranges that have
2344 /// been recolored and so on, until no more copies can be coalesced or
2345 /// it is not profitable.
2346 /// For a given live range, profitability is determined by the sum of the
2347 /// frequencies of the non-identity copies it would introduce with the old
2348 /// and new register.
tryHintRecoloring(LiveInterval & VirtReg)2349 void RAGreedy::tryHintRecoloring(LiveInterval &VirtReg) {
2350   // We have a broken hint, check if it is possible to fix it by
2351   // reusing PhysReg for the copy-related live-ranges. Indeed, we evicted
2352   // some register and PhysReg may be available for the other live-ranges.
2353   SmallSet<unsigned, 4> Visited;
2354   SmallVector<unsigned, 2> RecoloringCandidates;
2355   HintsInfo Info;
2356   unsigned Reg = VirtReg.reg;
2357   unsigned PhysReg = VRM->getPhys(Reg);
2358   // Start the recoloring algorithm from the input live-interval, then
2359   // it will propagate to the ones that are copy-related with it.
2360   Visited.insert(Reg);
2361   RecoloringCandidates.push_back(Reg);
2362 
2363   DEBUG(dbgs() << "Trying to reconcile hints for: " << PrintReg(Reg, TRI) << '('
2364                << PrintReg(PhysReg, TRI) << ")\n");
2365 
2366   do {
2367     Reg = RecoloringCandidates.pop_back_val();
2368 
2369     // We cannot recolor physcal register.
2370     if (TargetRegisterInfo::isPhysicalRegister(Reg))
2371       continue;
2372 
2373     assert(VRM->hasPhys(Reg) && "We have unallocated variable!!");
2374 
2375     // Get the live interval mapped with this virtual register to be able
2376     // to check for the interference with the new color.
2377     LiveInterval &LI = LIS->getInterval(Reg);
2378     unsigned CurrPhys = VRM->getPhys(Reg);
2379     // Check that the new color matches the register class constraints and
2380     // that it is free for this live range.
2381     if (CurrPhys != PhysReg && (!MRI->getRegClass(Reg)->contains(PhysReg) ||
2382                                 Matrix->checkInterference(LI, PhysReg)))
2383       continue;
2384 
2385     DEBUG(dbgs() << PrintReg(Reg, TRI) << '(' << PrintReg(CurrPhys, TRI)
2386                  << ") is recolorable.\n");
2387 
2388     // Gather the hint info.
2389     Info.clear();
2390     collectHintInfo(Reg, Info);
2391     // Check if recoloring the live-range will increase the cost of the
2392     // non-identity copies.
2393     if (CurrPhys != PhysReg) {
2394       DEBUG(dbgs() << "Checking profitability:\n");
2395       BlockFrequency OldCopiesCost = getBrokenHintFreq(Info, CurrPhys);
2396       BlockFrequency NewCopiesCost = getBrokenHintFreq(Info, PhysReg);
2397       DEBUG(dbgs() << "Old Cost: " << OldCopiesCost.getFrequency()
2398                    << "\nNew Cost: " << NewCopiesCost.getFrequency() << '\n');
2399       if (OldCopiesCost < NewCopiesCost) {
2400         DEBUG(dbgs() << "=> Not profitable.\n");
2401         continue;
2402       }
2403       // At this point, the cost is either cheaper or equal. If it is
2404       // equal, we consider this is profitable because it may expose
2405       // more recoloring opportunities.
2406       DEBUG(dbgs() << "=> Profitable.\n");
2407       // Recolor the live-range.
2408       Matrix->unassign(LI);
2409       Matrix->assign(LI, PhysReg);
2410     }
2411     // Push all copy-related live-ranges to keep reconciling the broken
2412     // hints.
2413     for (const HintInfo &HI : Info) {
2414       if (Visited.insert(HI.Reg).second)
2415         RecoloringCandidates.push_back(HI.Reg);
2416     }
2417   } while (!RecoloringCandidates.empty());
2418 }
2419 
2420 /// \brief Try to recolor broken hints.
2421 /// Broken hints may be repaired by recoloring when an evicted variable
2422 /// freed up a register for a larger live-range.
2423 /// Consider the following example:
2424 /// BB1:
2425 ///   a =
2426 ///   b =
2427 /// BB2:
2428 ///   ...
2429 ///   = b
2430 ///   = a
2431 /// Let us assume b gets split:
2432 /// BB1:
2433 ///   a =
2434 ///   b =
2435 /// BB2:
2436 ///   c = b
2437 ///   ...
2438 ///   d = c
2439 ///   = d
2440 ///   = a
2441 /// Because of how the allocation work, b, c, and d may be assigned different
2442 /// colors. Now, if a gets evicted later:
2443 /// BB1:
2444 ///   a =
2445 ///   st a, SpillSlot
2446 ///   b =
2447 /// BB2:
2448 ///   c = b
2449 ///   ...
2450 ///   d = c
2451 ///   = d
2452 ///   e = ld SpillSlot
2453 ///   = e
2454 /// This is likely that we can assign the same register for b, c, and d,
2455 /// getting rid of 2 copies.
tryHintsRecoloring()2456 void RAGreedy::tryHintsRecoloring() {
2457   for (LiveInterval *LI : SetOfBrokenHints) {
2458     assert(TargetRegisterInfo::isVirtualRegister(LI->reg) &&
2459            "Recoloring is possible only for virtual registers");
2460     // Some dead defs may be around (e.g., because of debug uses).
2461     // Ignore those.
2462     if (!VRM->hasPhys(LI->reg))
2463       continue;
2464     tryHintRecoloring(*LI);
2465   }
2466 }
2467 
selectOrSplitImpl(LiveInterval & VirtReg,SmallVectorImpl<unsigned> & NewVRegs,SmallVirtRegSet & FixedRegisters,unsigned Depth)2468 unsigned RAGreedy::selectOrSplitImpl(LiveInterval &VirtReg,
2469                                      SmallVectorImpl<unsigned> &NewVRegs,
2470                                      SmallVirtRegSet &FixedRegisters,
2471                                      unsigned Depth) {
2472   unsigned CostPerUseLimit = ~0u;
2473   // First try assigning a free register.
2474   AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo, Matrix);
2475   if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) {
2476     // When NewVRegs is not empty, we may have made decisions such as evicting
2477     // a virtual register, go with the earlier decisions and use the physical
2478     // register.
2479     if (CSRCost.getFrequency() && isUnusedCalleeSavedReg(PhysReg) &&
2480         NewVRegs.empty()) {
2481       unsigned CSRReg = tryAssignCSRFirstTime(VirtReg, Order, PhysReg,
2482                                               CostPerUseLimit, NewVRegs);
2483       if (CSRReg || !NewVRegs.empty())
2484         // Return now if we decide to use a CSR or create new vregs due to
2485         // pre-splitting.
2486         return CSRReg;
2487     } else
2488       return PhysReg;
2489   }
2490 
2491   LiveRangeStage Stage = getStage(VirtReg);
2492   DEBUG(dbgs() << StageName[Stage]
2493                << " Cascade " << ExtraRegInfo[VirtReg.reg].Cascade << '\n');
2494 
2495   // Try to evict a less worthy live range, but only for ranges from the primary
2496   // queue. The RS_Split ranges already failed to do this, and they should not
2497   // get a second chance until they have been split.
2498   if (Stage != RS_Split)
2499     if (unsigned PhysReg =
2500             tryEvict(VirtReg, Order, NewVRegs, CostPerUseLimit)) {
2501       unsigned Hint = MRI->getSimpleHint(VirtReg.reg);
2502       // If VirtReg has a hint and that hint is broken record this
2503       // virtual register as a recoloring candidate for broken hint.
2504       // Indeed, since we evicted a variable in its neighborhood it is
2505       // likely we can at least partially recolor some of the
2506       // copy-related live-ranges.
2507       if (Hint && Hint != PhysReg)
2508         SetOfBrokenHints.insert(&VirtReg);
2509       return PhysReg;
2510     }
2511 
2512   assert(NewVRegs.empty() && "Cannot append to existing NewVRegs");
2513 
2514   // The first time we see a live range, don't try to split or spill.
2515   // Wait until the second time, when all smaller ranges have been allocated.
2516   // This gives a better picture of the interference to split around.
2517   if (Stage < RS_Split) {
2518     setStage(VirtReg, RS_Split);
2519     DEBUG(dbgs() << "wait for second round\n");
2520     NewVRegs.push_back(VirtReg.reg);
2521     return 0;
2522   }
2523 
2524   // If we couldn't allocate a register from spilling, there is probably some
2525   // invalid inline assembly. The base class wil report it.
2526   if (Stage >= RS_Done || !VirtReg.isSpillable())
2527     return tryLastChanceRecoloring(VirtReg, Order, NewVRegs, FixedRegisters,
2528                                    Depth);
2529 
2530   // Try splitting VirtReg or interferences.
2531   unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs);
2532   if (PhysReg || !NewVRegs.empty())
2533     return PhysReg;
2534 
2535   // Finally spill VirtReg itself.
2536   if (EnableDeferredSpilling && getStage(VirtReg) < RS_Memory) {
2537     // TODO: This is experimental and in particular, we do not model
2538     // the live range splitting done by spilling correctly.
2539     // We would need a deep integration with the spiller to do the
2540     // right thing here. Anyway, that is still good for early testing.
2541     setStage(VirtReg, RS_Memory);
2542     DEBUG(dbgs() << "Do as if this register is in memory\n");
2543     NewVRegs.push_back(VirtReg.reg);
2544   } else {
2545     NamedRegionTimer T("Spiller", TimerGroupName, TimePassesIsEnabled);
2546     LiveRangeEdit LRE(&VirtReg, NewVRegs, *MF, *LIS, VRM, this);
2547     spiller().spill(LRE);
2548     setStage(NewVRegs.begin(), NewVRegs.end(), RS_Done);
2549 
2550     if (VerifyEnabled)
2551       MF->verify(this, "After spilling");
2552   }
2553 
2554   // The live virtual register requesting allocation was spilled, so tell
2555   // the caller not to allocate anything during this round.
2556   return 0;
2557 }
2558 
runOnMachineFunction(MachineFunction & mf)2559 bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
2560   DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
2561                << "********** Function: " << mf.getName() << '\n');
2562 
2563   MF = &mf;
2564   TRI = MF->getSubtarget().getRegisterInfo();
2565   TII = MF->getSubtarget().getInstrInfo();
2566   RCI.runOnMachineFunction(mf);
2567 
2568   EnableLocalReassign = EnableLocalReassignment ||
2569                         MF->getSubtarget().enableRALocalReassignment(
2570                             MF->getTarget().getOptLevel());
2571 
2572   if (VerifyEnabled)
2573     MF->verify(this, "Before greedy register allocator");
2574 
2575   RegAllocBase::init(getAnalysis<VirtRegMap>(),
2576                      getAnalysis<LiveIntervals>(),
2577                      getAnalysis<LiveRegMatrix>());
2578   Indexes = &getAnalysis<SlotIndexes>();
2579   MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
2580   DomTree = &getAnalysis<MachineDominatorTree>();
2581   SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
2582   Loops = &getAnalysis<MachineLoopInfo>();
2583   Bundles = &getAnalysis<EdgeBundles>();
2584   SpillPlacer = &getAnalysis<SpillPlacement>();
2585   DebugVars = &getAnalysis<LiveDebugVariables>();
2586 
2587   initializeCSRCost();
2588 
2589   calculateSpillWeightsAndHints(*LIS, mf, VRM, *Loops, *MBFI);
2590 
2591   DEBUG(LIS->dump());
2592 
2593   SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops));
2594   SE.reset(new SplitEditor(*SA, *LIS, *VRM, *DomTree, *MBFI));
2595   ExtraRegInfo.clear();
2596   ExtraRegInfo.resize(MRI->getNumVirtRegs());
2597   NextCascade = 1;
2598   IntfCache.init(MF, Matrix->getLiveUnions(), Indexes, LIS, TRI);
2599   GlobalCand.resize(32);  // This will grow as needed.
2600   SetOfBrokenHints.clear();
2601 
2602   allocatePhysRegs();
2603   tryHintsRecoloring();
2604   releaseMemory();
2605   return true;
2606 }
2607