LLVM  7.0.0svn
RegAllocGreedy.cpp
Go to the documentation of this file.
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 "AllocationOrder.h"
16 #include "InterferenceCache.h"
17 #include "LiveDebugVariables.h"
18 #include "RegAllocBase.h"
19 #include "SpillPlacement.h"
20 #include "Spiller.h"
21 #include "SplitKit.h"
22 #include "llvm/ADT/ArrayRef.h"
23 #include "llvm/ADT/BitVector.h"
24 #include "llvm/ADT/DenseMap.h"
25 #include "llvm/ADT/IndexedMap.h"
26 #include "llvm/ADT/MapVector.h"
27 #include "llvm/ADT/SetVector.h"
28 #include "llvm/ADT/SmallPtrSet.h"
29 #include "llvm/ADT/SmallSet.h"
30 #include "llvm/ADT/SmallVector.h"
31 #include "llvm/ADT/Statistic.h"
32 #include "llvm/ADT/StringRef.h"
61 #include "llvm/IR/Function.h"
62 #include "llvm/IR/LLVMContext.h"
63 #include "llvm/MC/MCRegisterInfo.h"
64 #include "llvm/Pass.h"
68 #include "llvm/Support/Debug.h"
70 #include "llvm/Support/Timer.h"
73 #include <algorithm>
74 #include <cassert>
75 #include <cstdint>
76 #include <memory>
77 #include <queue>
78 #include <tuple>
79 #include <utility>
80 
81 using namespace llvm;
82 
83 #define DEBUG_TYPE "regalloc"
84 
85 STATISTIC(NumGlobalSplits, "Number of split global live ranges");
86 STATISTIC(NumLocalSplits, "Number of split local live ranges");
87 STATISTIC(NumEvicted, "Number of interferences evicted");
88 
90  "split-spill-mode", cl::Hidden,
91  cl::desc("Spill mode for splitting live ranges"),
92  cl::values(clEnumValN(SplitEditor::SM_Partition, "default", "Default"),
93  clEnumValN(SplitEditor::SM_Size, "size", "Optimize for size"),
94  clEnumValN(SplitEditor::SM_Speed, "speed", "Optimize for speed")),
96 
97 static cl::opt<unsigned>
99  cl::desc("Last chance recoloring max depth"),
100  cl::init(5));
101 
103  "lcr-max-interf", cl::Hidden,
104  cl::desc("Last chance recoloring maximum number of considered"
105  " interference at a time"),
106  cl::init(8));
107 
109  "exhaustive-register-search", cl::NotHidden,
110  cl::desc("Exhaustive Search for registers bypassing the depth "
111  "and interference cutoffs of last chance recoloring"),
112  cl::Hidden);
113 
115  "enable-local-reassign", cl::Hidden,
116  cl::desc("Local reassignment can yield better allocation decisions, but "
117  "may be compile time intensive"),
118  cl::init(false));
119 
121  "enable-deferred-spilling", cl::Hidden,
122  cl::desc("Instead of spilling a variable right away, defer the actual "
123  "code insertion to the end of the allocation. That way the "
124  "allocator might still find a suitable coloring for this "
125  "variable because of other evicted variables."),
126  cl::init(false));
127 
128 // FIXME: Find a good default for this flag and remove the flag.
129 static cl::opt<unsigned>
130 CSRFirstTimeCost("regalloc-csr-first-time-cost",
131  cl::desc("Cost for first time use of callee-saved register."),
132  cl::init(0), cl::Hidden);
133 
135  "condsider-local-interval-cost", cl::Hidden,
136  cl::desc("Consider the cost of local intervals created by a split "
137  "candidate when choosing the best split candidate."),
138  cl::init(false));
139 
140 static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator",
142 
143 namespace {
144 
145 class RAGreedy : public MachineFunctionPass,
146  public RegAllocBase,
147  private LiveRangeEdit::Delegate {
148  // Convenient shortcuts.
149  using PQueue = std::priority_queue<std::pair<unsigned, unsigned>>;
150  using SmallLISet = SmallPtrSet<LiveInterval *, 4>;
151  using SmallVirtRegSet = SmallSet<unsigned, 16>;
152 
153  // context
154  MachineFunction *MF;
155 
156  // Shortcuts to some useful interface.
157  const TargetInstrInfo *TII;
158  const TargetRegisterInfo *TRI;
159  RegisterClassInfo RCI;
160 
161  // analyses
162  SlotIndexes *Indexes;
164  MachineDominatorTree *DomTree;
167  EdgeBundles *Bundles;
168  SpillPlacement *SpillPlacer;
169  LiveDebugVariables *DebugVars;
170  AliasAnalysis *AA;
171 
172  // state
173  std::unique_ptr<Spiller> SpillerInstance;
174  PQueue Queue;
175  unsigned NextCascade;
176 
177  // Live ranges pass through a number of stages as we try to allocate them.
178  // Some of the stages may also create new live ranges:
179  //
180  // - Region splitting.
181  // - Per-block splitting.
182  // - Local splitting.
183  // - Spilling.
184  //
185  // Ranges produced by one of the stages skip the previous stages when they are
186  // dequeued. This improves performance because we can skip interference checks
187  // that are unlikely to give any results. It also guarantees that the live
188  // range splitting algorithm terminates, something that is otherwise hard to
189  // ensure.
190  enum LiveRangeStage {
191  /// Newly created live range that has never been queued.
192  RS_New,
193 
194  /// Only attempt assignment and eviction. Then requeue as RS_Split.
195  RS_Assign,
196 
197  /// Attempt live range splitting if assignment is impossible.
198  RS_Split,
199 
200  /// Attempt more aggressive live range splitting that is guaranteed to make
201  /// progress. This is used for split products that may not be making
202  /// progress.
203  RS_Split2,
204 
205  /// Live range will be spilled. No more splitting will be attempted.
206  RS_Spill,
207 
208 
209  /// Live range is in memory. Because of other evictions, it might get moved
210  /// in a register in the end.
211  RS_Memory,
212 
213  /// There is nothing more we can do to this live range. Abort compilation
214  /// if it can't be assigned.
215  RS_Done
216  };
217 
218  // Enum CutOffStage to keep a track whether the register allocation failed
219  // because of the cutoffs encountered in last chance recoloring.
220  // Note: This is used as bitmask. New value should be next power of 2.
221  enum CutOffStage {
222  // No cutoffs encountered
223  CO_None = 0,
224 
225  // lcr-max-depth cutoff encountered
226  CO_Depth = 1,
227 
228  // lcr-max-interf cutoff encountered
229  CO_Interf = 2
230  };
231 
232  uint8_t CutOffInfo;
233 
234 #ifndef NDEBUG
235  static const char *const StageName[];
236 #endif
237 
238  // RegInfo - Keep additional information about each live range.
239  struct RegInfo {
240  LiveRangeStage Stage = RS_New;
241 
242  // Cascade - Eviction loop prevention. See canEvictInterference().
243  unsigned Cascade = 0;
244 
245  RegInfo() = default;
246  };
247 
249 
250  LiveRangeStage getStage(const LiveInterval &VirtReg) const {
251  return ExtraRegInfo[VirtReg.reg].Stage;
252  }
253 
254  void setStage(const LiveInterval &VirtReg, LiveRangeStage Stage) {
255  ExtraRegInfo.resize(MRI->getNumVirtRegs());
256  ExtraRegInfo[VirtReg.reg].Stage = Stage;
257  }
258 
259  template<typename Iterator>
260  void setStage(Iterator Begin, Iterator End, LiveRangeStage NewStage) {
261  ExtraRegInfo.resize(MRI->getNumVirtRegs());
262  for (;Begin != End; ++Begin) {
263  unsigned Reg = *Begin;
264  if (ExtraRegInfo[Reg].Stage == RS_New)
265  ExtraRegInfo[Reg].Stage = NewStage;
266  }
267  }
268 
269  /// Cost of evicting interference.
270  struct EvictionCost {
271  unsigned BrokenHints = 0; ///< Total number of broken hints.
272  float MaxWeight = 0; ///< Maximum spill weight evicted.
273 
274  EvictionCost() = default;
275 
276  bool isMax() const { return BrokenHints == ~0u; }
277 
278  void setMax() { BrokenHints = ~0u; }
279 
280  void setBrokenHints(unsigned NHints) { BrokenHints = NHints; }
281 
282  bool operator<(const EvictionCost &O) const {
283  return std::tie(BrokenHints, MaxWeight) <
284  std::tie(O.BrokenHints, O.MaxWeight);
285  }
286  };
287 
288  /// EvictionTrack - Keeps track of past evictions in order to optimize region
289  /// split decision.
290  class EvictionTrack {
291 
292  public:
293  using EvictorInfo =
294  std::pair<unsigned /* evictor */, unsigned /* physreg */>;
295  using EvicteeInfo = llvm::MapVector<unsigned /* evictee */, EvictorInfo>;
296 
297  private:
298  /// Each Vreg that has been evicted in the last stage of selectOrSplit will
299  /// be mapped to the evictor Vreg and the PhysReg it was evicted from.
300  EvicteeInfo Evictees;
301 
302  public:
303  /// Clear all eviction information.
304  void clear() { Evictees.clear(); }
305 
306  /// Clear eviction information for the given evictee Vreg.
307  /// E.g. when Vreg get's a new allocation, the old eviction info is no
308  /// longer relevant.
309  /// \param Evictee The evictee Vreg for whom we want to clear collected
310  /// eviction info.
311  void clearEvicteeInfo(unsigned Evictee) { Evictees.erase(Evictee); }
312 
313  /// Track new eviction.
314  /// The Evictor vreg has evicted the Evictee vreg from Physreg.
315  /// \praram PhysReg The phisical register Evictee was evicted from.
316  /// \praram Evictor The evictor Vreg that evicted Evictee.
317  /// \praram Evictee The evictee Vreg.
318  void addEviction(unsigned PhysReg, unsigned Evictor, unsigned Evictee) {
319  Evictees[Evictee].first = Evictor;
320  Evictees[Evictee].second = PhysReg;
321  }
322 
323  /// Return the Evictor Vreg which evicted Evictee Vreg from PhysReg.
324  /// \praram Evictee The evictee vreg.
325  /// \return The Evictor vreg which evicted Evictee vreg from PhysReg. 0 if
326  /// nobody has evicted Evictee from PhysReg.
327  EvictorInfo getEvictor(unsigned Evictee) {
328  if (Evictees.count(Evictee)) {
329  return Evictees[Evictee];
330  }
331 
332  return EvictorInfo(0, 0);
333  }
334  };
335 
336  // Keeps track of past evictions in order to optimize region split decision.
337  EvictionTrack LastEvicted;
338 
339  // splitting state.
340  std::unique_ptr<SplitAnalysis> SA;
341  std::unique_ptr<SplitEditor> SE;
342 
343  /// Cached per-block interference maps
344  InterferenceCache IntfCache;
345 
346  /// All basic blocks where the current register has uses.
348 
349  /// Global live range splitting candidate info.
350  struct GlobalSplitCandidate {
351  // Register intended for assignment, or 0.
352  unsigned PhysReg;
353 
354  // SplitKit interval index for this candidate.
355  unsigned IntvIdx;
356 
357  // Interference for PhysReg.
359 
360  // Bundles where this candidate should be live.
361  BitVector LiveBundles;
362  SmallVector<unsigned, 8> ActiveBlocks;
363 
364  void reset(InterferenceCache &Cache, unsigned Reg) {
365  PhysReg = Reg;
366  IntvIdx = 0;
367  Intf.setPhysReg(Cache, Reg);
368  LiveBundles.clear();
369  ActiveBlocks.clear();
370  }
371 
372  // Set B[i] = C for every live bundle where B[i] was NoCand.
373  unsigned getBundles(SmallVectorImpl<unsigned> &B, unsigned C) {
374  unsigned Count = 0;
375  for (unsigned i : LiveBundles.set_bits())
376  if (B[i] == NoCand) {
377  B[i] = C;
378  Count++;
379  }
380  return Count;
381  }
382  };
383 
384  /// Candidate info for each PhysReg in AllocationOrder.
385  /// This vector never shrinks, but grows to the size of the largest register
386  /// class.
388 
389  enum : unsigned { NoCand = ~0u };
390 
391  /// Candidate map. Each edge bundle is assigned to a GlobalCand entry, or to
392  /// NoCand which indicates the stack interval.
393  SmallVector<unsigned, 32> BundleCand;
394 
395  /// Callee-save register cost, calculated once per machine function.
396  BlockFrequency CSRCost;
397 
398  /// Run or not the local reassignment heuristic. This information is
399  /// obtained from the TargetSubtargetInfo.
400  bool EnableLocalReassign;
401 
402  /// Enable or not the consideration of the cost of local intervals created
403  /// by a split candidate when choosing the best split candidate.
404  bool EnableAdvancedRASplitCost;
405 
406  /// Set of broken hints that may be reconciled later because of eviction.
407  SmallSetVector<LiveInterval *, 8> SetOfBrokenHints;
408 
409 public:
410  RAGreedy();
411 
412  /// Return the pass name.
413  StringRef getPassName() const override { return "Greedy Register Allocator"; }
414 
415  /// RAGreedy analysis usage.
416  void getAnalysisUsage(AnalysisUsage &AU) const override;
417  void releaseMemory() override;
418  Spiller &spiller() override { return *SpillerInstance; }
419  void enqueue(LiveInterval *LI) override;
420  LiveInterval *dequeue() override;
421  unsigned selectOrSplit(LiveInterval&, SmallVectorImpl<unsigned>&) override;
422  void aboutToRemoveInterval(LiveInterval &) override;
423 
424  /// Perform register allocation.
425  bool runOnMachineFunction(MachineFunction &mf) override;
426 
427  MachineFunctionProperties getRequiredProperties() const override {
430  }
431 
432  static char ID;
433 
434 private:
435  unsigned selectOrSplitImpl(LiveInterval &, SmallVectorImpl<unsigned> &,
436  SmallVirtRegSet &, unsigned = 0);
437 
438  bool LRE_CanEraseVirtReg(unsigned) override;
439  void LRE_WillShrinkVirtReg(unsigned) override;
440  void LRE_DidCloneVirtReg(unsigned, unsigned) override;
441  void enqueue(PQueue &CurQueue, LiveInterval *LI);
442  LiveInterval *dequeue(PQueue &CurQueue);
443 
444  BlockFrequency calcSpillCost();
445  bool addSplitConstraints(InterferenceCache::Cursor, BlockFrequency&);
446  void addThroughConstraints(InterferenceCache::Cursor, ArrayRef<unsigned>);
447  void growRegion(GlobalSplitCandidate &Cand);
448  bool splitCanCauseEvictionChain(unsigned Evictee, GlobalSplitCandidate &Cand,
449  unsigned BBNumber,
450  const AllocationOrder &Order);
451  bool splitCanCauseLocalSpill(unsigned VirtRegToSplit,
452  GlobalSplitCandidate &Cand, unsigned BBNumber,
453  const AllocationOrder &Order);
454  BlockFrequency calcGlobalSplitCost(GlobalSplitCandidate &,
455  const AllocationOrder &Order,
456  bool *CanCauseEvictionChain);
457  bool calcCompactRegion(GlobalSplitCandidate&);
458  void splitAroundRegion(LiveRangeEdit&, ArrayRef<unsigned>);
459  void calcGapWeights(unsigned, SmallVectorImpl<float>&);
460  unsigned canReassign(LiveInterval &VirtReg, unsigned PhysReg);
461  bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool);
462  bool canEvictInterference(LiveInterval&, unsigned, bool, EvictionCost&);
463  bool canEvictInterferenceInRange(LiveInterval &VirtReg, unsigned PhysReg,
464  SlotIndex Start, SlotIndex End,
465  EvictionCost &MaxCost);
466  unsigned getCheapestEvicteeWeight(const AllocationOrder &Order,
467  LiveInterval &VirtReg, SlotIndex Start,
468  SlotIndex End, float *BestEvictWeight);
469  void evictInterference(LiveInterval&, unsigned,
471  bool mayRecolorAllInterferences(unsigned PhysReg, LiveInterval &VirtReg,
472  SmallLISet &RecoloringCandidates,
473  const SmallVirtRegSet &FixedRegisters);
474 
475  unsigned tryAssign(LiveInterval&, AllocationOrder&,
477  unsigned tryEvict(LiveInterval&, AllocationOrder&,
478  SmallVectorImpl<unsigned>&, unsigned = ~0u);
479  unsigned tryRegionSplit(LiveInterval&, AllocationOrder&,
481  /// Calculate cost of region splitting.
482  unsigned calculateRegionSplitCost(LiveInterval &VirtReg,
483  AllocationOrder &Order,
484  BlockFrequency &BestCost,
485  unsigned &NumCands, bool IgnoreCSR,
486  bool *CanCauseEvictionChain = nullptr);
487  /// Perform region splitting.
488  unsigned doRegionSplit(LiveInterval &VirtReg, unsigned BestCand,
489  bool HasCompact,
490  SmallVectorImpl<unsigned> &NewVRegs);
491  /// Check other options before using a callee-saved register for the first
492  /// time.
493  unsigned tryAssignCSRFirstTime(LiveInterval &VirtReg, AllocationOrder &Order,
494  unsigned PhysReg, unsigned &CostPerUseLimit,
495  SmallVectorImpl<unsigned> &NewVRegs);
496  void initializeCSRCost();
497  unsigned tryBlockSplit(LiveInterval&, AllocationOrder&,
499  unsigned tryInstructionSplit(LiveInterval&, AllocationOrder&,
501  unsigned tryLocalSplit(LiveInterval&, AllocationOrder&,
503  unsigned trySplit(LiveInterval&, AllocationOrder&,
505  unsigned tryLastChanceRecoloring(LiveInterval &, AllocationOrder &,
507  SmallVirtRegSet &, unsigned);
508  bool tryRecoloringCandidates(PQueue &, SmallVectorImpl<unsigned> &,
509  SmallVirtRegSet &, unsigned);
510  void tryHintRecoloring(LiveInterval &);
511  void tryHintsRecoloring();
512 
513  /// Model the information carried by one end of a copy.
514  struct HintInfo {
515  /// The frequency of the copy.
516  BlockFrequency Freq;
517  /// The virtual register or physical register.
518  unsigned Reg;
519  /// Its currently assigned register.
520  /// In case of a physical register Reg == PhysReg.
521  unsigned PhysReg;
522 
523  HintInfo(BlockFrequency Freq, unsigned Reg, unsigned PhysReg)
524  : Freq(Freq), Reg(Reg), PhysReg(PhysReg) {}
525  };
526  using HintsInfo = SmallVector<HintInfo, 4>;
527 
528  BlockFrequency getBrokenHintFreq(const HintsInfo &, unsigned);
529  void collectHintInfo(unsigned, HintsInfo &);
530 
531  bool isUnusedCalleeSavedReg(unsigned PhysReg) const;
532 
533  /// Compute and report the number of spills and reloads for a loop.
534  void reportNumberOfSplillsReloads(MachineLoop *L, unsigned &Reloads,
535  unsigned &FoldedReloads, unsigned &Spills,
536  unsigned &FoldedSpills);
537 
538  /// Report the number of spills and reloads for each loop.
539  void reportNumberOfSplillsReloads() {
540  for (MachineLoop *L : *Loops) {
541  unsigned Reloads, FoldedReloads, Spills, FoldedSpills;
542  reportNumberOfSplillsReloads(L, Reloads, FoldedReloads, Spills,
543  FoldedSpills);
544  }
545  }
546 };
547 
548 } // end anonymous namespace
549 
550 char RAGreedy::ID = 0;
552 
553 INITIALIZE_PASS_BEGIN(RAGreedy, "greedy",
554  "Greedy Register Allocator", false, false)
558 INITIALIZE_PASS_DEPENDENCY(RegisterCoalescer)
559 INITIALIZE_PASS_DEPENDENCY(MachineScheduler)
569  "Greedy Register Allocator", false, false)
570 
571 #ifndef NDEBUG
572 const char *const RAGreedy::StageName[] = {
573  "RS_New",
574  "RS_Assign",
575  "RS_Split",
576  "RS_Split2",
577  "RS_Spill",
578  "RS_Memory",
579  "RS_Done"
580 };
581 #endif
582 
583 // Hysteresis to use when comparing floats.
584 // This helps stabilize decisions based on float comparisons.
585 const float Hysteresis = (2007 / 2048.0f); // 0.97998046875
586 
588  return new RAGreedy();
589 }
590 
591 RAGreedy::RAGreedy(): MachineFunctionPass(ID) {
592 }
593 
594 void RAGreedy::getAnalysisUsage(AnalysisUsage &AU) const {
595  AU.setPreservesCFG();
602  AU.addRequired<SlotIndexes>();
606  AU.addRequired<LiveStacks>();
607  AU.addPreserved<LiveStacks>();
612  AU.addRequired<VirtRegMap>();
613  AU.addPreserved<VirtRegMap>();
616  AU.addRequired<EdgeBundles>();
620 }
621 
622 //===----------------------------------------------------------------------===//
623 // LiveRangeEdit delegate methods
624 //===----------------------------------------------------------------------===//
625 
626 bool RAGreedy::LRE_CanEraseVirtReg(unsigned VirtReg) {
627  LiveInterval &LI = LIS->getInterval(VirtReg);
628  if (VRM->hasPhys(VirtReg)) {
629  Matrix->unassign(LI);
630  aboutToRemoveInterval(LI);
631  return true;
632  }
633  // Unassigned virtreg is probably in the priority queue.
634  // RegAllocBase will erase it after dequeueing.
635  // Nonetheless, clear the live-range so that the debug
636  // dump will show the right state for that VirtReg.
637  LI.clear();
638  return false;
639 }
640 
641 void RAGreedy::LRE_WillShrinkVirtReg(unsigned VirtReg) {
642  if (!VRM->hasPhys(VirtReg))
643  return;
644 
645  // Register is assigned, put it back on the queue for reassignment.
646  LiveInterval &LI = LIS->getInterval(VirtReg);
647  Matrix->unassign(LI);
648  enqueue(&LI);
649 }
650 
651 void RAGreedy::LRE_DidCloneVirtReg(unsigned New, unsigned Old) {
652  // Cloning a register we haven't even heard about yet? Just ignore it.
653  if (!ExtraRegInfo.inBounds(Old))
654  return;
655 
656  // LRE may clone a virtual register because dead code elimination causes it to
657  // be split into connected components. The new components are much smaller
658  // than the original, so they should get a new chance at being assigned.
659  // same stage as the parent.
660  ExtraRegInfo[Old].Stage = RS_Assign;
661  ExtraRegInfo.grow(New);
662  ExtraRegInfo[New] = ExtraRegInfo[Old];
663 }
664 
665 void RAGreedy::releaseMemory() {
666  SpillerInstance.reset();
667  ExtraRegInfo.clear();
668  GlobalCand.clear();
669 }
670 
671 void RAGreedy::enqueue(LiveInterval *LI) { enqueue(Queue, LI); }
672 
673 void RAGreedy::enqueue(PQueue &CurQueue, LiveInterval *LI) {
674  // Prioritize live ranges by size, assigning larger ranges first.
675  // The queue holds (size, reg) pairs.
676  const unsigned Size = LI->getSize();
677  const unsigned Reg = LI->reg;
679  "Can only enqueue virtual registers");
680  unsigned Prio;
681 
682  ExtraRegInfo.grow(Reg);
683  if (ExtraRegInfo[Reg].Stage == RS_New)
684  ExtraRegInfo[Reg].Stage = RS_Assign;
685 
686  if (ExtraRegInfo[Reg].Stage == RS_Split) {
687  // Unsplit ranges that couldn't be allocated immediately are deferred until
688  // everything else has been allocated.
689  Prio = Size;
690  } else if (ExtraRegInfo[Reg].Stage == RS_Memory) {
691  // Memory operand should be considered last.
692  // Change the priority such that Memory operand are assigned in
693  // the reverse order that they came in.
694  // TODO: Make this a member variable and probably do something about hints.
695  static unsigned MemOp = 0;
696  Prio = MemOp++;
697  } else {
698  // Giant live ranges fall back to the global assignment heuristic, which
699  // prevents excessive spilling in pathological cases.
700  bool ReverseLocal = TRI->reverseLocalAssignment();
701  const TargetRegisterClass &RC = *MRI->getRegClass(Reg);
702  bool ForceGlobal = !ReverseLocal &&
703  (Size / SlotIndex::InstrDist) > (2 * RC.getNumRegs());
704 
705  if (ExtraRegInfo[Reg].Stage == RS_Assign && !ForceGlobal && !LI->empty() &&
706  LIS->intervalIsInOneMBB(*LI)) {
707  // Allocate original local ranges in linear instruction order. Since they
708  // are singly defined, this produces optimal coloring in the absence of
709  // global interference and other constraints.
710  if (!ReverseLocal)
711  Prio = LI->beginIndex().getInstrDistance(Indexes->getLastIndex());
712  else {
713  // Allocating bottom up may allow many short LRGs to be assigned first
714  // to one of the cheap registers. This could be much faster for very
715  // large blocks on targets with many physical registers.
716  Prio = Indexes->getZeroIndex().getInstrDistance(LI->endIndex());
717  }
718  Prio |= RC.AllocationPriority << 24;
719  } else {
720  // Allocate global and split ranges in long->short order. Long ranges that
721  // don't fit should be spilled (or split) ASAP so they don't create
722  // interference. Mark a bit to prioritize global above local ranges.
723  Prio = (1u << 29) + Size;
724  }
725  // Mark a higher bit to prioritize global and local above RS_Split.
726  Prio |= (1u << 31);
727 
728  // Boost ranges that have a physical register hint.
729  if (VRM->hasKnownPreference(Reg))
730  Prio |= (1u << 30);
731  }
732  // The virtual register number is a tie breaker for same-sized ranges.
733  // Give lower vreg numbers higher priority to assign them first.
734  CurQueue.push(std::make_pair(Prio, ~Reg));
735 }
736 
737 LiveInterval *RAGreedy::dequeue() { return dequeue(Queue); }
738 
739 LiveInterval *RAGreedy::dequeue(PQueue &CurQueue) {
740  if (CurQueue.empty())
741  return nullptr;
742  LiveInterval *LI = &LIS->getInterval(~CurQueue.top().second);
743  CurQueue.pop();
744  return LI;
745 }
746 
747 //===----------------------------------------------------------------------===//
748 // Direct Assignment
749 //===----------------------------------------------------------------------===//
750 
751 /// tryAssign - Try to assign VirtReg to an available register.
752 unsigned RAGreedy::tryAssign(LiveInterval &VirtReg,
753  AllocationOrder &Order,
754  SmallVectorImpl<unsigned> &NewVRegs) {
755  Order.rewind();
756  unsigned PhysReg;
757  while ((PhysReg = Order.next()))
758  if (!Matrix->checkInterference(VirtReg, PhysReg))
759  break;
760  if (!PhysReg || Order.isHint())
761  return PhysReg;
762 
763  // PhysReg is available, but there may be a better choice.
764 
765  // If we missed a simple hint, try to cheaply evict interference from the
766  // preferred register.
767  if (unsigned Hint = MRI->getSimpleHint(VirtReg.reg))
768  if (Order.isHint(Hint)) {
769  LLVM_DEBUG(dbgs() << "missed hint " << printReg(Hint, TRI) << '\n');
770  EvictionCost MaxCost;
771  MaxCost.setBrokenHints(1);
772  if (canEvictInterference(VirtReg, Hint, true, MaxCost)) {
773  evictInterference(VirtReg, Hint, NewVRegs);
774  return Hint;
775  }
776  // Record the missed hint, we may be able to recover
777  // at the end if the surrounding allocation changed.
778  SetOfBrokenHints.insert(&VirtReg);
779  }
780 
781  // Try to evict interference from a cheaper alternative.
782  unsigned Cost = TRI->getCostPerUse(PhysReg);
783 
784  // Most registers have 0 additional cost.
785  if (!Cost)
786  return PhysReg;
787 
788  LLVM_DEBUG(dbgs() << printReg(PhysReg, TRI) << " is available at cost "
789  << Cost << '\n');
790  unsigned CheapReg = tryEvict(VirtReg, Order, NewVRegs, Cost);
791  return CheapReg ? CheapReg : PhysReg;
792 }
793 
794 //===----------------------------------------------------------------------===//
795 // Interference eviction
796 //===----------------------------------------------------------------------===//
797 
798 unsigned RAGreedy::canReassign(LiveInterval &VirtReg, unsigned PrevReg) {
799  AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo, Matrix);
800  unsigned PhysReg;
801  while ((PhysReg = Order.next())) {
802  if (PhysReg == PrevReg)
803  continue;
804 
805  MCRegUnitIterator Units(PhysReg, TRI);
806  for (; Units.isValid(); ++Units) {
807  // Instantiate a "subquery", not to be confused with the Queries array.
808  LiveIntervalUnion::Query subQ(VirtReg, Matrix->getLiveUnions()[*Units]);
809  if (subQ.checkInterference())
810  break;
811  }
812  // If no units have interference, break out with the current PhysReg.
813  if (!Units.isValid())
814  break;
815  }
816  if (PhysReg)
817  LLVM_DEBUG(dbgs() << "can reassign: " << VirtReg << " from "
818  << printReg(PrevReg, TRI) << " to "
819  << printReg(PhysReg, TRI) << '\n');
820  return PhysReg;
821 }
822 
823 /// shouldEvict - determine if A should evict the assigned live range B. The
824 /// eviction policy defined by this function together with the allocation order
825 /// defined by enqueue() decides which registers ultimately end up being split
826 /// and spilled.
827 ///
828 /// Cascade numbers are used to prevent infinite loops if this function is a
829 /// cyclic relation.
830 ///
831 /// @param A The live range to be assigned.
832 /// @param IsHint True when A is about to be assigned to its preferred
833 /// register.
834 /// @param B The live range to be evicted.
835 /// @param BreaksHint True when B is already assigned to its preferred register.
836 bool RAGreedy::shouldEvict(LiveInterval &A, bool IsHint,
837  LiveInterval &B, bool BreaksHint) {
838  bool CanSplit = getStage(B) < RS_Spill;
839 
840  // Be fairly aggressive about following hints as long as the evictee can be
841  // split.
842  if (CanSplit && IsHint && !BreaksHint)
843  return true;
844 
845  if (A.weight > B.weight) {
846  LLVM_DEBUG(dbgs() << "should evict: " << B << " w= " << B.weight << '\n');
847  return true;
848  }
849  return false;
850 }
851 
852 /// canEvictInterference - Return true if all interferences between VirtReg and
853 /// PhysReg can be evicted.
854 ///
855 /// @param VirtReg Live range that is about to be assigned.
856 /// @param PhysReg Desired register for assignment.
857 /// @param IsHint True when PhysReg is VirtReg's preferred register.
858 /// @param MaxCost Only look for cheaper candidates and update with new cost
859 /// when returning true.
860 /// @returns True when interference can be evicted cheaper than MaxCost.
861 bool RAGreedy::canEvictInterference(LiveInterval &VirtReg, unsigned PhysReg,
862  bool IsHint, EvictionCost &MaxCost) {
863  // It is only possible to evict virtual register interference.
864  if (Matrix->checkInterference(VirtReg, PhysReg) > LiveRegMatrix::IK_VirtReg)
865  return false;
866 
867  bool IsLocal = LIS->intervalIsInOneMBB(VirtReg);
868 
869  // Find VirtReg's cascade number. This will be unassigned if VirtReg was never
870  // involved in an eviction before. If a cascade number was assigned, deny
871  // evicting anything with the same or a newer cascade number. This prevents
872  // infinite eviction loops.
873  //
874  // This works out so a register without a cascade number is allowed to evict
875  // anything, and it can be evicted by anything.
876  unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade;
877  if (!Cascade)
878  Cascade = NextCascade;
879 
880  EvictionCost Cost;
881  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
882  LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
883  // If there is 10 or more interferences, chances are one is heavier.
884  if (Q.collectInterferingVRegs(10) >= 10)
885  return false;
886 
887  // Check if any interfering live range is heavier than MaxWeight.
888  for (unsigned i = Q.interferingVRegs().size(); i; --i) {
889  LiveInterval *Intf = Q.interferingVRegs()[i - 1];
891  "Only expecting virtual register interference from query");
892  // Never evict spill products. They cannot split or spill.
893  if (getStage(*Intf) == RS_Done)
894  return false;
895  // Once a live range becomes small enough, it is urgent that we find a
896  // register for it. This is indicated by an infinite spill weight. These
897  // urgent live ranges get to evict almost anything.
898  //
899  // Also allow urgent evictions of unspillable ranges from a strictly
900  // larger allocation order.
901  bool Urgent = !VirtReg.isSpillable() &&
902  (Intf->isSpillable() ||
903  RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(VirtReg.reg)) <
904  RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(Intf->reg)));
905  // Only evict older cascades or live ranges without a cascade.
906  unsigned IntfCascade = ExtraRegInfo[Intf->reg].Cascade;
907  if (Cascade <= IntfCascade) {
908  if (!Urgent)
909  return false;
910  // We permit breaking cascades for urgent evictions. It should be the
911  // last resort, though, so make it really expensive.
912  Cost.BrokenHints += 10;
913  }
914  // Would this break a satisfied hint?
915  bool BreaksHint = VRM->hasPreferredPhys(Intf->reg);
916  // Update eviction cost.
917  Cost.BrokenHints += BreaksHint;
918  Cost.MaxWeight = std::max(Cost.MaxWeight, Intf->weight);
919  // Abort if this would be too expensive.
920  if (!(Cost < MaxCost))
921  return false;
922  if (Urgent)
923  continue;
924  // Apply the eviction policy for non-urgent evictions.
925  if (!shouldEvict(VirtReg, IsHint, *Intf, BreaksHint))
926  return false;
927  // If !MaxCost.isMax(), then we're just looking for a cheap register.
928  // Evicting another local live range in this case could lead to suboptimal
929  // coloring.
930  if (!MaxCost.isMax() && IsLocal && LIS->intervalIsInOneMBB(*Intf) &&
931  (!EnableLocalReassign || !canReassign(*Intf, PhysReg))) {
932  return false;
933  }
934  }
935  }
936  MaxCost = Cost;
937  return true;
938 }
939 
940 /// Return true if all interferences between VirtReg and PhysReg between
941 /// Start and End can be evicted.
942 ///
943 /// \param VirtReg Live range that is about to be assigned.
944 /// \param PhysReg Desired register for assignment.
945 /// \param Start Start of range to look for interferences.
946 /// \param End End of range to look for interferences.
947 /// \param MaxCost Only look for cheaper candidates and update with new cost
948 /// when returning true.
949 /// \return True when interference can be evicted cheaper than MaxCost.
950 bool RAGreedy::canEvictInterferenceInRange(LiveInterval &VirtReg,
951  unsigned PhysReg, SlotIndex Start,
952  SlotIndex End,
953  EvictionCost &MaxCost) {
954  EvictionCost Cost;
955 
956  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
957  LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
958 
959  // Check if any interfering live range is heavier than MaxWeight.
960  for (unsigned i = Q.interferingVRegs().size(); i; --i) {
961  LiveInterval *Intf = Q.interferingVRegs()[i - 1];
962 
963  // Check if interference overlast the segment in interest.
964  if (!Intf->overlaps(Start, End))
965  continue;
966 
967  // Cannot evict non virtual reg interference.
969  return false;
970  // Never evict spill products. They cannot split or spill.
971  if (getStage(*Intf) == RS_Done)
972  return false;
973 
974  // Would this break a satisfied hint?
975  bool BreaksHint = VRM->hasPreferredPhys(Intf->reg);
976  // Update eviction cost.
977  Cost.BrokenHints += BreaksHint;
978  Cost.MaxWeight = std::max(Cost.MaxWeight, Intf->weight);
979  // Abort if this would be too expensive.
980  if (!(Cost < MaxCost))
981  return false;
982  }
983  }
984 
985  if (Cost.MaxWeight == 0)
986  return false;
987 
988  MaxCost = Cost;
989  return true;
990 }
991 
992 /// Return tthe physical register that will be best
993 /// candidate for eviction by a local split interval that will be created
994 /// between Start and End.
995 ///
996 /// \param Order The allocation order
997 /// \param VirtReg Live range that is about to be assigned.
998 /// \param Start Start of range to look for interferences
999 /// \param End End of range to look for interferences
1000 /// \param BestEvictweight The eviction cost of that eviction
1001 /// \return The PhysReg which is the best candidate for eviction and the
1002 /// eviction cost in BestEvictweight
1003 unsigned RAGreedy::getCheapestEvicteeWeight(const AllocationOrder &Order,
1004  LiveInterval &VirtReg,
1005  SlotIndex Start, SlotIndex End,
1006  float *BestEvictweight) {
1007  EvictionCost BestEvictCost;
1008  BestEvictCost.setMax();
1009  BestEvictCost.MaxWeight = VirtReg.weight;
1010  unsigned BestEvicteePhys = 0;
1011 
1012  // Go over all physical registers and find the best candidate for eviction
1013  for (auto PhysReg : Order.getOrder()) {
1014 
1015  if (!canEvictInterferenceInRange(VirtReg, PhysReg, Start, End,
1016  BestEvictCost))
1017  continue;
1018 
1019  // Best so far.
1020  BestEvicteePhys = PhysReg;
1021  }
1022  *BestEvictweight = BestEvictCost.MaxWeight;
1023  return BestEvicteePhys;
1024 }
1025 
1026 /// evictInterference - Evict any interferring registers that prevent VirtReg
1027 /// from being assigned to Physreg. This assumes that canEvictInterference
1028 /// returned true.
1029 void RAGreedy::evictInterference(LiveInterval &VirtReg, unsigned PhysReg,
1030  SmallVectorImpl<unsigned> &NewVRegs) {
1031  // Make sure that VirtReg has a cascade number, and assign that cascade
1032  // number to every evicted register. These live ranges than then only be
1033  // evicted by a newer cascade, preventing infinite loops.
1034  unsigned Cascade = ExtraRegInfo[VirtReg.reg].Cascade;
1035  if (!Cascade)
1036  Cascade = ExtraRegInfo[VirtReg.reg].Cascade = NextCascade++;
1037 
1038  LLVM_DEBUG(dbgs() << "evicting " << printReg(PhysReg, TRI)
1039  << " interference: Cascade " << Cascade << '\n');
1040 
1041  // Collect all interfering virtregs first.
1043  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
1044  LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
1045  // We usually have the interfering VRegs cached so collectInterferingVRegs()
1046  // should be fast, we may need to recalculate if when different physregs
1047  // overlap the same register unit so we had different SubRanges queried
1048  // against it.
1051  Intfs.append(IVR.begin(), IVR.end());
1052  }
1053 
1054  // Evict them second. This will invalidate the queries.
1055  for (unsigned i = 0, e = Intfs.size(); i != e; ++i) {
1056  LiveInterval *Intf = Intfs[i];
1057  // The same VirtReg may be present in multiple RegUnits. Skip duplicates.
1058  if (!VRM->hasPhys(Intf->reg))
1059  continue;
1060 
1061  LastEvicted.addEviction(PhysReg, VirtReg.reg, Intf->reg);
1062 
1063  Matrix->unassign(*Intf);
1064  assert((ExtraRegInfo[Intf->reg].Cascade < Cascade ||
1065  VirtReg.isSpillable() < Intf->isSpillable()) &&
1066  "Cannot decrease cascade number, illegal eviction");
1067  ExtraRegInfo[Intf->reg].Cascade = Cascade;
1068  ++NumEvicted;
1069  NewVRegs.push_back(Intf->reg);
1070  }
1071 }
1072 
1073 /// Returns true if the given \p PhysReg is a callee saved register and has not
1074 /// been used for allocation yet.
1075 bool RAGreedy::isUnusedCalleeSavedReg(unsigned PhysReg) const {
1076  unsigned CSR = RegClassInfo.getLastCalleeSavedAlias(PhysReg);
1077  if (CSR == 0)
1078  return false;
1079 
1080  return !Matrix->isPhysRegUsed(PhysReg);
1081 }
1082 
1083 /// tryEvict - Try to evict all interferences for a physreg.
1084 /// @param VirtReg Currently unassigned virtual register.
1085 /// @param Order Physregs to try.
1086 /// @return Physreg to assign VirtReg, or 0.
1087 unsigned RAGreedy::tryEvict(LiveInterval &VirtReg,
1088  AllocationOrder &Order,
1089  SmallVectorImpl<unsigned> &NewVRegs,
1090  unsigned CostPerUseLimit) {
1091  NamedRegionTimer T("evict", "Evict", TimerGroupName, TimerGroupDescription,
1093 
1094  // Keep track of the cheapest interference seen so far.
1095  EvictionCost BestCost;
1096  BestCost.setMax();
1097  unsigned BestPhys = 0;
1098  unsigned OrderLimit = Order.getOrder().size();
1099 
1100  // When we are just looking for a reduced cost per use, don't break any
1101  // hints, and only evict smaller spill weights.
1102  if (CostPerUseLimit < ~0u) {
1103  BestCost.BrokenHints = 0;
1104  BestCost.MaxWeight = VirtReg.weight;
1105 
1106  // Check of any registers in RC are below CostPerUseLimit.
1107  const TargetRegisterClass *RC = MRI->getRegClass(VirtReg.reg);
1108  unsigned MinCost = RegClassInfo.getMinCost(RC);
1109  if (MinCost >= CostPerUseLimit) {
1110  LLVM_DEBUG(dbgs() << TRI->getRegClassName(RC) << " minimum cost = "
1111  << MinCost << ", no cheaper registers to be found.\n");
1112  return 0;
1113  }
1114 
1115  // It is normal for register classes to have a long tail of registers with
1116  // the same cost. We don't need to look at them if they're too expensive.
1117  if (TRI->getCostPerUse(Order.getOrder().back()) >= CostPerUseLimit) {
1118  OrderLimit = RegClassInfo.getLastCostChange(RC);
1119  LLVM_DEBUG(dbgs() << "Only trying the first " << OrderLimit
1120  << " regs.\n");
1121  }
1122  }
1123 
1124  Order.rewind();
1125  while (unsigned PhysReg = Order.next(OrderLimit)) {
1126  if (TRI->getCostPerUse(PhysReg) >= CostPerUseLimit)
1127  continue;
1128  // The first use of a callee-saved register in a function has cost 1.
1129  // Don't start using a CSR when the CostPerUseLimit is low.
1130  if (CostPerUseLimit == 1 && isUnusedCalleeSavedReg(PhysReg)) {
1131  LLVM_DEBUG(
1132  dbgs() << printReg(PhysReg, TRI) << " would clobber CSR "
1133  << printReg(RegClassInfo.getLastCalleeSavedAlias(PhysReg), TRI)
1134  << '\n');
1135  continue;
1136  }
1137 
1138  if (!canEvictInterference(VirtReg, PhysReg, false, BestCost))
1139  continue;
1140 
1141  // Best so far.
1142  BestPhys = PhysReg;
1143 
1144  // Stop if the hint can be used.
1145  if (Order.isHint())
1146  break;
1147  }
1148 
1149  if (!BestPhys)
1150  return 0;
1151 
1152  evictInterference(VirtReg, BestPhys, NewVRegs);
1153  return BestPhys;
1154 }
1155 
1156 //===----------------------------------------------------------------------===//
1157 // Region Splitting
1158 //===----------------------------------------------------------------------===//
1159 
1160 /// addSplitConstraints - Fill out the SplitConstraints vector based on the
1161 /// interference pattern in Physreg and its aliases. Add the constraints to
1162 /// SpillPlacement and return the static cost of this split in Cost, assuming
1163 /// that all preferences in SplitConstraints are met.
1164 /// Return false if there are no bundles with positive bias.
1165 bool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf,
1166  BlockFrequency &Cost) {
1167  ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1168 
1169  // Reset interference dependent info.
1170  SplitConstraints.resize(UseBlocks.size());
1171  BlockFrequency StaticCost = 0;
1172  for (unsigned i = 0; i != UseBlocks.size(); ++i) {
1173  const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
1174  SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
1175 
1176  BC.Number = BI.MBB->getNumber();
1177  Intf.moveToBlock(BC.Number);
1180  BC.ChangesValue = BI.FirstDef.isValid();
1181 
1182  if (!Intf.hasInterference())
1183  continue;
1184 
1185  // Number of spill code instructions to insert.
1186  unsigned Ins = 0;
1187 
1188  // Interference for the live-in value.
1189  if (BI.LiveIn) {
1190  if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number)) {
1192  ++Ins;
1193  } else if (Intf.first() < BI.FirstInstr) {
1195  ++Ins;
1196  } else if (Intf.first() < BI.LastInstr) {
1197  ++Ins;
1198  }
1199  }
1200 
1201  // Interference for the live-out value.
1202  if (BI.LiveOut) {
1203  if (Intf.last() >= SA->getLastSplitPoint(BC.Number)) {
1205  ++Ins;
1206  } else if (Intf.last() > BI.LastInstr) {
1208  ++Ins;
1209  } else if (Intf.last() > BI.FirstInstr) {
1210  ++Ins;
1211  }
1212  }
1213 
1214  // Accumulate the total frequency of inserted spill code.
1215  while (Ins--)
1216  StaticCost += SpillPlacer->getBlockFrequency(BC.Number);
1217  }
1218  Cost = StaticCost;
1219 
1220  // Add constraints for use-blocks. Note that these are the only constraints
1221  // that may add a positive bias, it is downhill from here.
1222  SpillPlacer->addConstraints(SplitConstraints);
1223  return SpillPlacer->scanActiveBundles();
1224 }
1225 
1226 /// addThroughConstraints - Add constraints and links to SpillPlacer from the
1227 /// live-through blocks in Blocks.
1228 void RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf,
1229  ArrayRef<unsigned> Blocks) {
1230  const unsigned GroupSize = 8;
1231  SpillPlacement::BlockConstraint BCS[GroupSize];
1232  unsigned TBS[GroupSize];
1233  unsigned B = 0, T = 0;
1234 
1235  for (unsigned i = 0; i != Blocks.size(); ++i) {
1236  unsigned Number = Blocks[i];
1237  Intf.moveToBlock(Number);
1238 
1239  if (!Intf.hasInterference()) {
1240  assert(T < GroupSize && "Array overflow");
1241  TBS[T] = Number;
1242  if (++T == GroupSize) {
1243  SpillPlacer->addLinks(makeArrayRef(TBS, T));
1244  T = 0;
1245  }
1246  continue;
1247  }
1248 
1249  assert(B < GroupSize && "Array overflow");
1250  BCS[B].Number = Number;
1251 
1252  // Interference for the live-in value.
1253  if (Intf.first() <= Indexes->getMBBStartIdx(Number))
1254  BCS[B].Entry = SpillPlacement::MustSpill;
1255  else
1257 
1258  // Interference for the live-out value.
1259  if (Intf.last() >= SA->getLastSplitPoint(Number))
1260  BCS[B].Exit = SpillPlacement::MustSpill;
1261  else
1263 
1264  if (++B == GroupSize) {
1265  SpillPlacer->addConstraints(makeArrayRef(BCS, B));
1266  B = 0;
1267  }
1268  }
1269 
1270  SpillPlacer->addConstraints(makeArrayRef(BCS, B));
1271  SpillPlacer->addLinks(makeArrayRef(TBS, T));
1272 }
1273 
1274 void RAGreedy::growRegion(GlobalSplitCandidate &Cand) {
1275  // Keep track of through blocks that have not been added to SpillPlacer.
1276  BitVector Todo = SA->getThroughBlocks();
1277  SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks;
1278  unsigned AddedTo = 0;
1279 #ifndef NDEBUG
1280  unsigned Visited = 0;
1281 #endif
1282 
1283  while (true) {
1284  ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive();
1285  // Find new through blocks in the periphery of PrefRegBundles.
1286  for (int i = 0, e = NewBundles.size(); i != e; ++i) {
1287  unsigned Bundle = NewBundles[i];
1288  // Look at all blocks connected to Bundle in the full graph.
1289  ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle);
1290  for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end();
1291  I != E; ++I) {
1292  unsigned Block = *I;
1293  if (!Todo.test(Block))
1294  continue;
1295  Todo.reset(Block);
1296  // This is a new through block. Add it to SpillPlacer later.
1297  ActiveBlocks.push_back(Block);
1298 #ifndef NDEBUG
1299  ++Visited;
1300 #endif
1301  }
1302  }
1303  // Any new blocks to add?
1304  if (ActiveBlocks.size() == AddedTo)
1305  break;
1306 
1307  // Compute through constraints from the interference, or assume that all
1308  // through blocks prefer spilling when forming compact regions.
1309  auto NewBlocks = makeArrayRef(ActiveBlocks).slice(AddedTo);
1310  if (Cand.PhysReg)
1311  addThroughConstraints(Cand.Intf, NewBlocks);
1312  else
1313  // Provide a strong negative bias on through blocks to prevent unwanted
1314  // liveness on loop backedges.
1315  SpillPlacer->addPrefSpill(NewBlocks, /* Strong= */ true);
1316  AddedTo = ActiveBlocks.size();
1317 
1318  // Perhaps iterating can enable more bundles?
1319  SpillPlacer->iterate();
1320  }
1321  LLVM_DEBUG(dbgs() << ", v=" << Visited);
1322 }
1323 
1324 /// calcCompactRegion - Compute the set of edge bundles that should be live
1325 /// when splitting the current live range into compact regions. Compact
1326 /// regions can be computed without looking at interference. They are the
1327 /// regions formed by removing all the live-through blocks from the live range.
1328 ///
1329 /// Returns false if the current live range is already compact, or if the
1330 /// compact regions would form single block regions anyway.
1331 bool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) {
1332  // Without any through blocks, the live range is already compact.
1333  if (!SA->getNumThroughBlocks())
1334  return false;
1335 
1336  // Compact regions don't correspond to any physreg.
1337  Cand.reset(IntfCache, 0);
1338 
1339  LLVM_DEBUG(dbgs() << "Compact region bundles");
1340 
1341  // Use the spill placer to determine the live bundles. GrowRegion pretends
1342  // that all the through blocks have interference when PhysReg is unset.
1343  SpillPlacer->prepare(Cand.LiveBundles);
1344 
1345  // The static split cost will be zero since Cand.Intf reports no interference.
1346  BlockFrequency Cost;
1347  if (!addSplitConstraints(Cand.Intf, Cost)) {
1348  LLVM_DEBUG(dbgs() << ", none.\n");
1349  return false;
1350  }
1351 
1352  growRegion(Cand);
1353  SpillPlacer->finish();
1354 
1355  if (!Cand.LiveBundles.any()) {
1356  LLVM_DEBUG(dbgs() << ", none.\n");
1357  return false;
1358  }
1359 
1360  LLVM_DEBUG({
1361  for (int i : Cand.LiveBundles.set_bits())
1362  dbgs() << " EB#" << i;
1363  dbgs() << ".\n";
1364  });
1365  return true;
1366 }
1367 
1368 /// calcSpillCost - Compute how expensive it would be to split the live range in
1369 /// SA around all use blocks instead of forming bundle regions.
1370 BlockFrequency RAGreedy::calcSpillCost() {
1371  BlockFrequency Cost = 0;
1372  ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1373  for (unsigned i = 0; i != UseBlocks.size(); ++i) {
1374  const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
1375  unsigned Number = BI.MBB->getNumber();
1376  // We normally only need one spill instruction - a load or a store.
1377  Cost += SpillPlacer->getBlockFrequency(Number);
1378 
1379  // Unless the value is redefined in the block.
1380  if (BI.LiveIn && BI.LiveOut && BI.FirstDef)
1381  Cost += SpillPlacer->getBlockFrequency(Number);
1382  }
1383  return Cost;
1384 }
1385 
1386 /// Check if splitting Evictee will create a local split interval in
1387 /// basic block number BBNumber that may cause a bad eviction chain. This is
1388 /// intended to prevent bad eviction sequences like:
1389 /// movl %ebp, 8(%esp) # 4-byte Spill
1390 /// movl %ecx, %ebp
1391 /// movl %ebx, %ecx
1392 /// movl %edi, %ebx
1393 /// movl %edx, %edi
1394 /// cltd
1395 /// idivl %esi
1396 /// movl %edi, %edx
1397 /// movl %ebx, %edi
1398 /// movl %ecx, %ebx
1399 /// movl %ebp, %ecx
1400 /// movl 16(%esp), %ebp # 4 - byte Reload
1401 ///
1402 /// Such sequences are created in 2 scenarios:
1403 ///
1404 /// Scenario #1:
1405 /// %0 is evicted from physreg0 by %1.
1406 /// Evictee %0 is intended for region splitting with split candidate
1407 /// physreg0 (the reg %0 was evicted from).
1408 /// Region splitting creates a local interval because of interference with the
1409 /// evictor %1 (normally region spliitting creates 2 interval, the "by reg"
1410 /// and "by stack" intervals and local interval created when interference
1411 /// occurs).
1412 /// One of the split intervals ends up evicting %2 from physreg1.
1413 /// Evictee %2 is intended for region splitting with split candidate
1414 /// physreg1.
1415 /// One of the split intervals ends up evicting %3 from physreg2, etc.
1416 ///
1417 /// Scenario #2
1418 /// %0 is evicted from physreg0 by %1.
1419 /// %2 is evicted from physreg2 by %3 etc.
1420 /// Evictee %0 is intended for region splitting with split candidate
1421 /// physreg1.
1422 /// Region splitting creates a local interval because of interference with the
1423 /// evictor %1.
1424 /// One of the split intervals ends up evicting back original evictor %1
1425 /// from physreg0 (the reg %0 was evicted from).
1426 /// Another evictee %2 is intended for region splitting with split candidate
1427 /// physreg1.
1428 /// One of the split intervals ends up evicting %3 from physreg2, etc.
1429 ///
1430 /// \param Evictee The register considered to be split.
1431 /// \param Cand The split candidate that determines the physical register
1432 /// we are splitting for and the interferences.
1433 /// \param BBNumber The number of a BB for which the region split process will
1434 /// create a local split interval.
1435 /// \param Order The physical registers that may get evicted by a split
1436 /// artifact of Evictee.
1437 /// \return True if splitting Evictee may cause a bad eviction chain, false
1438 /// otherwise.
1439 bool RAGreedy::splitCanCauseEvictionChain(unsigned Evictee,
1440  GlobalSplitCandidate &Cand,
1441  unsigned BBNumber,
1442  const AllocationOrder &Order) {
1443  EvictionTrack::EvictorInfo VregEvictorInfo = LastEvicted.getEvictor(Evictee);
1444  unsigned Evictor = VregEvictorInfo.first;
1445  unsigned PhysReg = VregEvictorInfo.second;
1446 
1447  // No actual evictor.
1448  if (!Evictor || !PhysReg)
1449  return false;
1450 
1451  float MaxWeight = 0;
1452  unsigned FutureEvictedPhysReg =
1453  getCheapestEvicteeWeight(Order, LIS->getInterval(Evictee),
1454  Cand.Intf.first(), Cand.Intf.last(), &MaxWeight);
1455 
1456  // The bad eviction chain occurs when either the split candidate is the
1457  // evicting reg or one of the split artifact will evict the evicting reg.
1458  if ((PhysReg != Cand.PhysReg) && (PhysReg != FutureEvictedPhysReg))
1459  return false;
1460 
1461  Cand.Intf.moveToBlock(BBNumber);
1462 
1463  // Check to see if the Evictor contains interference (with Evictee) in the
1464  // given BB. If so, this interference caused the eviction of Evictee from
1465  // PhysReg. This suggest that we will create a local interval during the
1466  // region split to avoid this interference This local interval may cause a bad
1467  // eviction chain.
1468  if (!LIS->hasInterval(Evictor))
1469  return false;
1470  LiveInterval &EvictorLI = LIS->getInterval(Evictor);
1471  if (EvictorLI.FindSegmentContaining(Cand.Intf.first()) == EvictorLI.end())
1472  return false;
1473 
1474  // Now, check to see if the local interval we will create is going to be
1475  // expensive enough to evict somebody If so, this may cause a bad eviction
1476  // chain.
1477  VirtRegAuxInfo VRAI(*MF, *LIS, VRM, getAnalysis<MachineLoopInfo>(), *MBFI);
1478  float splitArtifactWeight =
1479  VRAI.futureWeight(LIS->getInterval(Evictee),
1480  Cand.Intf.first().getPrevIndex(), Cand.Intf.last());
1481  if (splitArtifactWeight >= 0 && splitArtifactWeight < MaxWeight)
1482  return false;
1483 
1484  return true;
1485 }
1486 
1487 /// Check if splitting VirtRegToSplit will create a local split interval
1488 /// in basic block number BBNumber that may cause a spill.
1489 ///
1490 /// \param VirtRegToSplit The register considered to be split.
1491 /// \param Cand The split candidate that determines the physical
1492 /// register we are splitting for and the interferences.
1493 /// \param BBNumber The number of a BB for which the region split process
1494 /// will create a local split interval.
1495 /// \param Order The physical registers that may get evicted by a
1496 /// split artifact of VirtRegToSplit.
1497 /// \return True if splitting VirtRegToSplit may cause a spill, false
1498 /// otherwise.
1499 bool RAGreedy::splitCanCauseLocalSpill(unsigned VirtRegToSplit,
1500  GlobalSplitCandidate &Cand,
1501  unsigned BBNumber,
1502  const AllocationOrder &Order) {
1503  Cand.Intf.moveToBlock(BBNumber);
1504 
1505  // Check if the local interval will find a non interfereing assignment.
1506  for (auto PhysReg : Order.getOrder()) {
1507  if (!Matrix->checkInterference(Cand.Intf.first().getPrevIndex(),
1508  Cand.Intf.last(), PhysReg))
1509  return false;
1510  }
1511 
1512  // Check if the local interval will evict a cheaper interval.
1513  float CheapestEvictWeight = 0;
1514  unsigned FutureEvictedPhysReg = getCheapestEvicteeWeight(
1515  Order, LIS->getInterval(VirtRegToSplit), Cand.Intf.first(),
1516  Cand.Intf.last(), &CheapestEvictWeight);
1517 
1518  // Have we found an interval that can be evicted?
1519  if (FutureEvictedPhysReg) {
1520  VirtRegAuxInfo VRAI(*MF, *LIS, VRM, getAnalysis<MachineLoopInfo>(), *MBFI);
1521  float splitArtifactWeight =
1522  VRAI.futureWeight(LIS->getInterval(VirtRegToSplit),
1523  Cand.Intf.first().getPrevIndex(), Cand.Intf.last());
1524  // Will the weight of the local interval be higher than the cheapest evictee
1525  // weight? If so it will evict it and will not cause a spill.
1526  if (splitArtifactWeight >= 0 && splitArtifactWeight > CheapestEvictWeight)
1527  return false;
1528  }
1529 
1530  // The local interval is not able to find non interferening assignment and not
1531  // able to evict a less worthy interval, therfore, it can cause a spill.
1532  return true;
1533 }
1534 
1535 /// calcGlobalSplitCost - Return the global split cost of following the split
1536 /// pattern in LiveBundles. This cost should be added to the local cost of the
1537 /// interference pattern in SplitConstraints.
1538 ///
1539 BlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand,
1540  const AllocationOrder &Order,
1541  bool *CanCauseEvictionChain) {
1542  BlockFrequency GlobalCost = 0;
1543  const BitVector &LiveBundles = Cand.LiveBundles;
1544  unsigned VirtRegToSplit = SA->getParent().reg;
1545  ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1546  for (unsigned i = 0; i != UseBlocks.size(); ++i) {
1547  const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
1548  SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
1549  bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, false)];
1550  bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, true)];
1551  unsigned Ins = 0;
1552 
1553  Cand.Intf.moveToBlock(BC.Number);
1554  // Check wheather a local interval is going to be created during the region
1555  // split. Calculate adavanced spilt cost (cost of local intervals) if option
1556  // is enabled.
1557  if (EnableAdvancedRASplitCost && Cand.Intf.hasInterference() && BI.LiveIn &&
1558  BI.LiveOut && RegIn && RegOut) {
1559 
1560  if (CanCauseEvictionChain &&
1561  splitCanCauseEvictionChain(VirtRegToSplit, Cand, BC.Number, Order)) {
1562  // This interference causes our eviction from this assignment, we might
1563  // evict somebody else and eventually someone will spill, add that cost.
1564  // See splitCanCauseEvictionChain for detailed description of scenarios.
1565  GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);
1566  GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);
1567 
1568  *CanCauseEvictionChain = true;
1569 
1570  } else if (splitCanCauseLocalSpill(VirtRegToSplit, Cand, BC.Number,
1571  Order)) {
1572  // This interference causes local interval to spill, add that cost.
1573  GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);
1574  GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);
1575  }
1576  }
1577 
1578  if (BI.LiveIn)
1579  Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg);
1580  if (BI.LiveOut)
1581  Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg);
1582  while (Ins--)
1583  GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);
1584  }
1585 
1586  for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) {
1587  unsigned Number = Cand.ActiveBlocks[i];
1588  bool RegIn = LiveBundles[Bundles->getBundle(Number, false)];
1589  bool RegOut = LiveBundles[Bundles->getBundle(Number, true)];
1590  if (!RegIn && !RegOut)
1591  continue;
1592  if (RegIn && RegOut) {
1593  // We need double spill code if this block has interference.
1594  Cand.Intf.moveToBlock(Number);
1595  if (Cand.Intf.hasInterference()) {
1596  GlobalCost += SpillPlacer->getBlockFrequency(Number);
1597  GlobalCost += SpillPlacer->getBlockFrequency(Number);
1598 
1599  // Check wheather a local interval is going to be created during the
1600  // region split.
1601  if (EnableAdvancedRASplitCost && CanCauseEvictionChain &&
1602  splitCanCauseEvictionChain(VirtRegToSplit, Cand, Number, Order)) {
1603  // This interference cause our eviction from this assignment, we might
1604  // evict somebody else, add that cost.
1605  // See splitCanCauseEvictionChain for detailed description of
1606  // scenarios.
1607  GlobalCost += SpillPlacer->getBlockFrequency(Number);
1608  GlobalCost += SpillPlacer->getBlockFrequency(Number);
1609 
1610  *CanCauseEvictionChain = true;
1611  }
1612  }
1613  continue;
1614  }
1615  // live-in / stack-out or stack-in live-out.
1616  GlobalCost += SpillPlacer->getBlockFrequency(Number);
1617  }
1618  return GlobalCost;
1619 }
1620 
1621 /// splitAroundRegion - Split the current live range around the regions
1622 /// determined by BundleCand and GlobalCand.
1623 ///
1624 /// Before calling this function, GlobalCand and BundleCand must be initialized
1625 /// so each bundle is assigned to a valid candidate, or NoCand for the
1626 /// stack-bound bundles. The shared SA/SE SplitAnalysis and SplitEditor
1627 /// objects must be initialized for the current live range, and intervals
1628 /// created for the used candidates.
1629 ///
1630 /// @param LREdit The LiveRangeEdit object handling the current split.
1631 /// @param UsedCands List of used GlobalCand entries. Every BundleCand value
1632 /// must appear in this list.
1633 void RAGreedy::splitAroundRegion(LiveRangeEdit &LREdit,
1634  ArrayRef<unsigned> UsedCands) {
1635  // These are the intervals created for new global ranges. We may create more
1636  // intervals for local ranges.
1637  const unsigned NumGlobalIntvs = LREdit.size();
1638  LLVM_DEBUG(dbgs() << "splitAroundRegion with " << NumGlobalIntvs
1639  << " globals.\n");
1640  assert(NumGlobalIntvs && "No global intervals configured");
1641 
1642  // Isolate even single instructions when dealing with a proper sub-class.
1643  // That guarantees register class inflation for the stack interval because it
1644  // is all copies.
1645  unsigned Reg = SA->getParent().reg;
1646  bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg));
1647 
1648  // First handle all the blocks with uses.
1649  ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1650  for (unsigned i = 0; i != UseBlocks.size(); ++i) {
1651  const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
1652  unsigned Number = BI.MBB->getNumber();
1653  unsigned IntvIn = 0, IntvOut = 0;
1654  SlotIndex IntfIn, IntfOut;
1655  if (BI.LiveIn) {
1656  unsigned CandIn = BundleCand[Bundles->getBundle(Number, false)];
1657  if (CandIn != NoCand) {
1658  GlobalSplitCandidate &Cand = GlobalCand[CandIn];
1659  IntvIn = Cand.IntvIdx;
1660  Cand.Intf.moveToBlock(Number);
1661  IntfIn = Cand.Intf.first();
1662  }
1663  }
1664  if (BI.LiveOut) {
1665  unsigned CandOut = BundleCand[Bundles->getBundle(Number, true)];
1666  if (CandOut != NoCand) {
1667  GlobalSplitCandidate &Cand = GlobalCand[CandOut];
1668  IntvOut = Cand.IntvIdx;
1669  Cand.Intf.moveToBlock(Number);
1670  IntfOut = Cand.Intf.last();
1671  }
1672  }
1673 
1674  // Create separate intervals for isolated blocks with multiple uses.
1675  if (!IntvIn && !IntvOut) {
1676  LLVM_DEBUG(dbgs() << printMBBReference(*BI.MBB) << " isolated.\n");
1677  if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
1678  SE->splitSingleBlock(BI);
1679  continue;
1680  }
1681 
1682  if (IntvIn && IntvOut)
1683  SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut);
1684  else if (IntvIn)
1685  SE->splitRegInBlock(BI, IntvIn, IntfIn);
1686  else
1687  SE->splitRegOutBlock(BI, IntvOut, IntfOut);
1688  }
1689 
1690  // Handle live-through blocks. The relevant live-through blocks are stored in
1691  // the ActiveBlocks list with each candidate. We need to filter out
1692  // duplicates.
1693  BitVector Todo = SA->getThroughBlocks();
1694  for (unsigned c = 0; c != UsedCands.size(); ++c) {
1695  ArrayRef<unsigned> Blocks = GlobalCand[UsedCands[c]].ActiveBlocks;
1696  for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
1697  unsigned Number = Blocks[i];
1698  if (!Todo.test(Number))
1699  continue;
1700  Todo.reset(Number);
1701 
1702  unsigned IntvIn = 0, IntvOut = 0;
1703  SlotIndex IntfIn, IntfOut;
1704 
1705  unsigned CandIn = BundleCand[Bundles->getBundle(Number, false)];
1706  if (CandIn != NoCand) {
1707  GlobalSplitCandidate &Cand = GlobalCand[CandIn];
1708  IntvIn = Cand.IntvIdx;
1709  Cand.Intf.moveToBlock(Number);
1710  IntfIn = Cand.Intf.first();
1711  }
1712 
1713  unsigned CandOut = BundleCand[Bundles->getBundle(Number, true)];
1714  if (CandOut != NoCand) {
1715  GlobalSplitCandidate &Cand = GlobalCand[CandOut];
1716  IntvOut = Cand.IntvIdx;
1717  Cand.Intf.moveToBlock(Number);
1718  IntfOut = Cand.Intf.last();
1719  }
1720  if (!IntvIn && !IntvOut)
1721  continue;
1722  SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut);
1723  }
1724  }
1725 
1726  ++NumGlobalSplits;
1727 
1728  SmallVector<unsigned, 8> IntvMap;
1729  SE->finish(&IntvMap);
1730  DebugVars->splitRegister(Reg, LREdit.regs(), *LIS);
1731 
1732  ExtraRegInfo.resize(MRI->getNumVirtRegs());
1733  unsigned OrigBlocks = SA->getNumLiveBlocks();
1734 
1735  // Sort out the new intervals created by splitting. We get four kinds:
1736  // - Remainder intervals should not be split again.
1737  // - Candidate intervals can be assigned to Cand.PhysReg.
1738  // - Block-local splits are candidates for local splitting.
1739  // - DCE leftovers should go back on the queue.
1740  for (unsigned i = 0, e = LREdit.size(); i != e; ++i) {
1741  LiveInterval &Reg = LIS->getInterval(LREdit.get(i));
1742 
1743  // Ignore old intervals from DCE.
1744  if (getStage(Reg) != RS_New)
1745  continue;
1746 
1747  // Remainder interval. Don't try splitting again, spill if it doesn't
1748  // allocate.
1749  if (IntvMap[i] == 0) {
1750  setStage(Reg, RS_Spill);
1751  continue;
1752  }
1753 
1754  // Global intervals. Allow repeated splitting as long as the number of live
1755  // blocks is strictly decreasing.
1756  if (IntvMap[i] < NumGlobalIntvs) {
1757  if (SA->countLiveBlocks(&Reg) >= OrigBlocks) {
1758  LLVM_DEBUG(dbgs() << "Main interval covers the same " << OrigBlocks
1759  << " blocks as original.\n");
1760  // Don't allow repeated splitting as a safe guard against looping.
1761  setStage(Reg, RS_Split2);
1762  }
1763  continue;
1764  }
1765 
1766  // Other intervals are treated as new. This includes local intervals created
1767  // for blocks with multiple uses, and anything created by DCE.
1768  }
1769 
1770  if (VerifyEnabled)
1771  MF->verify(this, "After splitting live range around region");
1772 }
1773 
1774 unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
1775  SmallVectorImpl<unsigned> &NewVRegs) {
1776  unsigned NumCands = 0;
1777  BlockFrequency SpillCost = calcSpillCost();
1778  BlockFrequency BestCost;
1779 
1780  // Check if we can split this live range around a compact region.
1781  bool HasCompact = calcCompactRegion(GlobalCand.front());
1782  if (HasCompact) {
1783  // Yes, keep GlobalCand[0] as the compact region candidate.
1784  NumCands = 1;
1785  BestCost = BlockFrequency::getMaxFrequency();
1786  } else {
1787  // No benefit from the compact region, our fallback will be per-block
1788  // splitting. Make sure we find a solution that is cheaper than spilling.
1789  BestCost = SpillCost;
1790  LLVM_DEBUG(dbgs() << "Cost of isolating all blocks = ";
1791  MBFI->printBlockFreq(dbgs(), BestCost) << '\n');
1792  }
1793 
1794  bool CanCauseEvictionChain = false;
1795  unsigned BestCand =
1796  calculateRegionSplitCost(VirtReg, Order, BestCost, NumCands,
1797  false /*IgnoreCSR*/, &CanCauseEvictionChain);
1798 
1799  // Split candidates with compact regions can cause a bad eviction sequence.
1800  // See splitCanCauseEvictionChain for detailed description of scenarios.
1801  // To avoid it, we need to comapre the cost with the spill cost and not the
1802  // current max frequency.
1803  if (HasCompact && (BestCost > SpillCost) && (BestCand != NoCand) &&
1804  CanCauseEvictionChain) {
1805  return 0;
1806  }
1807 
1808  // No solutions found, fall back to single block splitting.
1809  if (!HasCompact && BestCand == NoCand)
1810  return 0;
1811 
1812  return doRegionSplit(VirtReg, BestCand, HasCompact, NewVRegs);
1813 }
1814 
1815 unsigned RAGreedy::calculateRegionSplitCost(LiveInterval &VirtReg,
1816  AllocationOrder &Order,
1817  BlockFrequency &BestCost,
1818  unsigned &NumCands, bool IgnoreCSR,
1819  bool *CanCauseEvictionChain) {
1820  unsigned BestCand = NoCand;
1821  Order.rewind();
1822  while (unsigned PhysReg = Order.next()) {
1823  if (IgnoreCSR && isUnusedCalleeSavedReg(PhysReg))
1824  continue;
1825 
1826  // Discard bad candidates before we run out of interference cache cursors.
1827  // This will only affect register classes with a lot of registers (>32).
1828  if (NumCands == IntfCache.getMaxCursors()) {
1829  unsigned WorstCount = ~0u;
1830  unsigned Worst = 0;
1831  for (unsigned i = 0; i != NumCands; ++i) {
1832  if (i == BestCand || !GlobalCand[i].PhysReg)
1833  continue;
1834  unsigned Count = GlobalCand[i].LiveBundles.count();
1835  if (Count < WorstCount) {
1836  Worst = i;
1837  WorstCount = Count;
1838  }
1839  }
1840  --NumCands;
1841  GlobalCand[Worst] = GlobalCand[NumCands];
1842  if (BestCand == NumCands)
1843  BestCand = Worst;
1844  }
1845 
1846  if (GlobalCand.size() <= NumCands)
1847  GlobalCand.resize(NumCands+1);
1848  GlobalSplitCandidate &Cand = GlobalCand[NumCands];
1849  Cand.reset(IntfCache, PhysReg);
1850 
1851  SpillPlacer->prepare(Cand.LiveBundles);
1852  BlockFrequency Cost;
1853  if (!addSplitConstraints(Cand.Intf, Cost)) {
1854  LLVM_DEBUG(dbgs() << printReg(PhysReg, TRI) << "\tno positive bundles\n");
1855  continue;
1856  }
1857  LLVM_DEBUG(dbgs() << printReg(PhysReg, TRI) << "\tstatic = ";
1858  MBFI->printBlockFreq(dbgs(), Cost));
1859  if (Cost >= BestCost) {
1860  LLVM_DEBUG({
1861  if (BestCand == NoCand)
1862  dbgs() << " worse than no bundles\n";
1863  else
1864  dbgs() << " worse than "
1865  << printReg(GlobalCand[BestCand].PhysReg, TRI) << '\n';
1866  });
1867  continue;
1868  }
1869  growRegion(Cand);
1870 
1871  SpillPlacer->finish();
1872 
1873  // No live bundles, defer to splitSingleBlocks().
1874  if (!Cand.LiveBundles.any()) {
1875  LLVM_DEBUG(dbgs() << " no bundles.\n");
1876  continue;
1877  }
1878 
1879  bool HasEvictionChain = false;
1880  Cost += calcGlobalSplitCost(Cand, Order, &HasEvictionChain);
1881  LLVM_DEBUG({
1882  dbgs() << ", total = ";
1883  MBFI->printBlockFreq(dbgs(), Cost) << " with bundles";
1884  for (int i : Cand.LiveBundles.set_bits())
1885  dbgs() << " EB#" << i;
1886  dbgs() << ".\n";
1887  });
1888  if (Cost < BestCost) {
1889  BestCand = NumCands;
1890  BestCost = Cost;
1891  // See splitCanCauseEvictionChain for detailed description of bad
1892  // eviction chain scenarios.
1893  if (CanCauseEvictionChain)
1894  *CanCauseEvictionChain = HasEvictionChain;
1895  }
1896  ++NumCands;
1897  }
1898 
1899  if (CanCauseEvictionChain && BestCand != NoCand) {
1900  // See splitCanCauseEvictionChain for detailed description of bad
1901  // eviction chain scenarios.
1902  LLVM_DEBUG(dbgs() << "Best split candidate of vreg "
1903  << printReg(VirtReg.reg, TRI) << " may ");
1904  if (!(*CanCauseEvictionChain))
1905  LLVM_DEBUG(dbgs() << "not ");
1906  LLVM_DEBUG(dbgs() << "cause bad eviction chain\n");
1907  }
1908 
1909  return BestCand;
1910 }
1911 
1912 unsigned RAGreedy::doRegionSplit(LiveInterval &VirtReg, unsigned BestCand,
1913  bool HasCompact,
1914  SmallVectorImpl<unsigned> &NewVRegs) {
1915  SmallVector<unsigned, 8> UsedCands;
1916  // Prepare split editor.
1917  LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
1918  SE->reset(LREdit, SplitSpillMode);
1919 
1920  // Assign all edge bundles to the preferred candidate, or NoCand.
1921  BundleCand.assign(Bundles->getNumBundles(), NoCand);
1922 
1923  // Assign bundles for the best candidate region.
1924  if (BestCand != NoCand) {
1925  GlobalSplitCandidate &Cand = GlobalCand[BestCand];
1926  if (unsigned B = Cand.getBundles(BundleCand, BestCand)) {
1927  UsedCands.push_back(BestCand);
1928  Cand.IntvIdx = SE->openIntv();
1929  LLVM_DEBUG(dbgs() << "Split for " << printReg(Cand.PhysReg, TRI) << " in "
1930  << B << " bundles, intv " << Cand.IntvIdx << ".\n");
1931  (void)B;
1932  }
1933  }
1934 
1935  // Assign bundles for the compact region.
1936  if (HasCompact) {
1937  GlobalSplitCandidate &Cand = GlobalCand.front();
1938  assert(!Cand.PhysReg && "Compact region has no physreg");
1939  if (unsigned B = Cand.getBundles(BundleCand, 0)) {
1940  UsedCands.push_back(0);
1941  Cand.IntvIdx = SE->openIntv();
1942  LLVM_DEBUG(dbgs() << "Split for compact region in " << B
1943  << " bundles, intv " << Cand.IntvIdx << ".\n");
1944  (void)B;
1945  }
1946  }
1947 
1948  splitAroundRegion(LREdit, UsedCands);
1949  return 0;
1950 }
1951 
1952 //===----------------------------------------------------------------------===//
1953 // Per-Block Splitting
1954 //===----------------------------------------------------------------------===//
1955 
1956 /// tryBlockSplit - Split a global live range around every block with uses. This
1957 /// creates a lot of local live ranges, that will be split by tryLocalSplit if
1958 /// they don't allocate.
1959 unsigned RAGreedy::tryBlockSplit(LiveInterval &VirtReg, AllocationOrder &Order,
1960  SmallVectorImpl<unsigned> &NewVRegs) {
1961  assert(&SA->getParent() == &VirtReg && "Live range wasn't analyzed");
1962  unsigned Reg = VirtReg.reg;
1963  bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg));
1964  LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
1965  SE->reset(LREdit, SplitSpillMode);
1966  ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1967  for (unsigned i = 0; i != UseBlocks.size(); ++i) {
1968  const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
1969  if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
1970  SE->splitSingleBlock(BI);
1971  }
1972  // No blocks were split.
1973  if (LREdit.empty())
1974  return 0;
1975 
1976  // We did split for some blocks.
1977  SmallVector<unsigned, 8> IntvMap;
1978  SE->finish(&IntvMap);
1979 
1980  // Tell LiveDebugVariables about the new ranges.
1981  DebugVars->splitRegister(Reg, LREdit.regs(), *LIS);
1982 
1983  ExtraRegInfo.resize(MRI->getNumVirtRegs());
1984 
1985  // Sort out the new intervals created by splitting. The remainder interval
1986  // goes straight to spilling, the new local ranges get to stay RS_New.
1987  for (unsigned i = 0, e = LREdit.size(); i != e; ++i) {
1988  LiveInterval &LI = LIS->getInterval(LREdit.get(i));
1989  if (getStage(LI) == RS_New && IntvMap[i] == 0)
1990  setStage(LI, RS_Spill);
1991  }
1992 
1993  if (VerifyEnabled)
1994  MF->verify(this, "After splitting live range around basic blocks");
1995  return 0;
1996 }
1997 
1998 //===----------------------------------------------------------------------===//
1999 // Per-Instruction Splitting
2000 //===----------------------------------------------------------------------===//
2001 
2002 /// Get the number of allocatable registers that match the constraints of \p Reg
2003 /// on \p MI and that are also in \p SuperRC.
2005  const MachineInstr *MI, unsigned Reg, const TargetRegisterClass *SuperRC,
2006  const TargetInstrInfo *TII, const TargetRegisterInfo *TRI,
2007  const RegisterClassInfo &RCI) {
2008  assert(SuperRC && "Invalid register class");
2009 
2010  const TargetRegisterClass *ConstrainedRC =
2011  MI->getRegClassConstraintEffectForVReg(Reg, SuperRC, TII, TRI,
2012  /* ExploreBundle */ true);
2013  if (!ConstrainedRC)
2014  return 0;
2015  return RCI.getNumAllocatableRegs(ConstrainedRC);
2016 }
2017 
2018 /// tryInstructionSplit - Split a live range around individual instructions.
2019 /// This is normally not worthwhile since the spiller is doing essentially the
2020 /// same thing. However, when the live range is in a constrained register
2021 /// class, it may help to insert copies such that parts of the live range can
2022 /// be moved to a larger register class.
2023 ///
2024 /// This is similar to spilling to a larger register class.
2025 unsigned
2026 RAGreedy::tryInstructionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
2027  SmallVectorImpl<unsigned> &NewVRegs) {
2028  const TargetRegisterClass *CurRC = MRI->getRegClass(VirtReg.reg);
2029  // There is no point to this if there are no larger sub-classes.
2030  if (!RegClassInfo.isProperSubClass(CurRC))
2031  return 0;
2032 
2033  // Always enable split spill mode, since we're effectively spilling to a
2034  // register.
2035  LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
2036  SE->reset(LREdit, SplitEditor::SM_Size);
2037 
2038  ArrayRef<SlotIndex> Uses = SA->getUseSlots();
2039  if (Uses.size() <= 1)
2040  return 0;
2041 
2042  LLVM_DEBUG(dbgs() << "Split around " << Uses.size()
2043  << " individual instrs.\n");
2044 
2045  const TargetRegisterClass *SuperRC =
2046  TRI->getLargestLegalSuperClass(CurRC, *MF);
2047  unsigned SuperRCNumAllocatableRegs = RCI.getNumAllocatableRegs(SuperRC);
2048  // Split around every non-copy instruction if this split will relax
2049  // the constraints on the virtual register.
2050  // Otherwise, splitting just inserts uncoalescable copies that do not help
2051  // the allocation.
2052  for (unsigned i = 0; i != Uses.size(); ++i) {
2053  if (const MachineInstr *MI = Indexes->getInstructionFromIndex(Uses[i]))
2054  if (MI->isFullCopy() ||
2055  SuperRCNumAllocatableRegs ==
2056  getNumAllocatableRegsForConstraints(MI, VirtReg.reg, SuperRC, TII,
2057  TRI, RCI)) {
2058  LLVM_DEBUG(dbgs() << " skip:\t" << Uses[i] << '\t' << *MI);
2059  continue;
2060  }
2061  SE->openIntv();
2062  SlotIndex SegStart = SE->enterIntvBefore(Uses[i]);
2063  SlotIndex SegStop = SE->leaveIntvAfter(Uses[i]);
2064  SE->useIntv(SegStart, SegStop);
2065  }
2066 
2067  if (LREdit.empty()) {
2068  LLVM_DEBUG(dbgs() << "All uses were copies.\n");
2069  return 0;
2070  }
2071 
2072  SmallVector<unsigned, 8> IntvMap;
2073  SE->finish(&IntvMap);
2074  DebugVars->splitRegister(VirtReg.reg, LREdit.regs(), *LIS);
2075  ExtraRegInfo.resize(MRI->getNumVirtRegs());
2076 
2077  // Assign all new registers to RS_Spill. This was the last chance.
2078  setStage(LREdit.begin(), LREdit.end(), RS_Spill);
2079  return 0;
2080 }
2081 
2082 //===----------------------------------------------------------------------===//
2083 // Local Splitting
2084 //===----------------------------------------------------------------------===//
2085 
2086 /// calcGapWeights - Compute the maximum spill weight that needs to be evicted
2087 /// in order to use PhysReg between two entries in SA->UseSlots.
2088 ///
2089 /// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1].
2090 ///
2091 void RAGreedy::calcGapWeights(unsigned PhysReg,
2092  SmallVectorImpl<float> &GapWeight) {
2093  assert(SA->getUseBlocks().size() == 1 && "Not a local interval");
2094  const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front();
2095  ArrayRef<SlotIndex> Uses = SA->getUseSlots();
2096  const unsigned NumGaps = Uses.size()-1;
2097 
2098  // Start and end points for the interference check.
2099  SlotIndex StartIdx =
2100  BI.LiveIn ? BI.FirstInstr.getBaseIndex() : BI.FirstInstr;
2101  SlotIndex StopIdx =
2102  BI.LiveOut ? BI.LastInstr.getBoundaryIndex() : BI.LastInstr;
2103 
2104  GapWeight.assign(NumGaps, 0.0f);
2105 
2106  // Add interference from each overlapping register.
2107  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
2108  if (!Matrix->query(const_cast<LiveInterval&>(SA->getParent()), *Units)
2109  .checkInterference())
2110  continue;
2111 
2112  // We know that VirtReg is a continuous interval from FirstInstr to
2113  // LastInstr, so we don't need InterferenceQuery.
2114  //
2115  // Interference that overlaps an instruction is counted in both gaps
2116  // surrounding the instruction. The exception is interference before
2117  // StartIdx and after StopIdx.
2118  //
2120  Matrix->getLiveUnions()[*Units] .find(StartIdx);
2121  for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) {
2122  // Skip the gaps before IntI.
2123  while (Uses[Gap+1].getBoundaryIndex() < IntI.start())
2124  if (++Gap == NumGaps)
2125  break;
2126  if (Gap == NumGaps)
2127  break;
2128 
2129  // Update the gaps covered by IntI.
2130  const float weight = IntI.value()->weight;
2131  for (; Gap != NumGaps; ++Gap) {
2132  GapWeight[Gap] = std::max(GapWeight[Gap], weight);
2133  if (Uses[Gap+1].getBaseIndex() >= IntI.stop())
2134  break;
2135  }
2136  if (Gap == NumGaps)
2137  break;
2138  }
2139  }
2140 
2141  // Add fixed interference.
2142  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
2143  const LiveRange &LR = LIS->getRegUnit(*Units);
2144  LiveRange::const_iterator I = LR.find(StartIdx);
2146 
2147  // Same loop as above. Mark any overlapped gaps as HUGE_VALF.
2148  for (unsigned Gap = 0; I != E && I->start < StopIdx; ++I) {
2149  while (Uses[Gap+1].getBoundaryIndex() < I->start)
2150  if (++Gap == NumGaps)
2151  break;
2152  if (Gap == NumGaps)
2153  break;
2154 
2155  for (; Gap != NumGaps; ++Gap) {
2156  GapWeight[Gap] = huge_valf;
2157  if (Uses[Gap+1].getBaseIndex() >= I->end)
2158  break;
2159  }
2160  if (Gap == NumGaps)
2161  break;
2162  }
2163  }
2164 }
2165 
2166 /// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only
2167 /// basic block.
2168 ///
2169 unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order,
2170  SmallVectorImpl<unsigned> &NewVRegs) {
2171  assert(SA->getUseBlocks().size() == 1 && "Not a local interval");
2172  const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front();
2173 
2174  // Note that it is possible to have an interval that is live-in or live-out
2175  // while only covering a single block - A phi-def can use undef values from
2176  // predecessors, and the block could be a single-block loop.
2177  // We don't bother doing anything clever about such a case, we simply assume
2178  // that the interval is continuous from FirstInstr to LastInstr. We should
2179  // make sure that we don't do anything illegal to such an interval, though.
2180 
2181  ArrayRef<SlotIndex> Uses = SA->getUseSlots();
2182  if (Uses.size() <= 2)
2183  return 0;
2184  const unsigned NumGaps = Uses.size()-1;
2185 
2186  LLVM_DEBUG({
2187  dbgs() << "tryLocalSplit: ";
2188  for (unsigned i = 0, e = Uses.size(); i != e; ++i)
2189  dbgs() << ' ' << Uses[i];
2190  dbgs() << '\n';
2191  });
2192 
2193  // If VirtReg is live across any register mask operands, compute a list of
2194  // gaps with register masks.
2195  SmallVector<unsigned, 8> RegMaskGaps;
2196  if (Matrix->checkRegMaskInterference(VirtReg)) {
2197  // Get regmask slots for the whole block.
2198  ArrayRef<SlotIndex> RMS = LIS->getRegMaskSlotsInBlock(BI.MBB->getNumber());
2199  LLVM_DEBUG(dbgs() << RMS.size() << " regmasks in block:");
2200  // Constrain to VirtReg's live range.
2201  unsigned ri = std::lower_bound(RMS.begin(), RMS.end(),
2202  Uses.front().getRegSlot()) - RMS.begin();
2203  unsigned re = RMS.size();
2204  for (unsigned i = 0; i != NumGaps && ri != re; ++i) {
2205  // Look for Uses[i] <= RMS <= Uses[i+1].
2206  assert(!SlotIndex::isEarlierInstr(RMS[ri], Uses[i]));
2207  if (SlotIndex::isEarlierInstr(Uses[i+1], RMS[ri]))
2208  continue;
2209  // Skip a regmask on the same instruction as the last use. It doesn't
2210  // overlap the live range.
2211  if (SlotIndex::isSameInstr(Uses[i+1], RMS[ri]) && i+1 == NumGaps)
2212  break;
2213  LLVM_DEBUG(dbgs() << ' ' << RMS[ri] << ':' << Uses[i] << '-'
2214  << Uses[i + 1]);
2215  RegMaskGaps.push_back(i);
2216  // Advance ri to the next gap. A regmask on one of the uses counts in
2217  // both gaps.
2218  while (ri != re && SlotIndex::isEarlierInstr(RMS[ri], Uses[i+1]))
2219  ++ri;
2220  }
2221  LLVM_DEBUG(dbgs() << '\n');
2222  }
2223 
2224  // Since we allow local split results to be split again, there is a risk of
2225  // creating infinite loops. It is tempting to require that the new live
2226  // ranges have less instructions than the original. That would guarantee
2227  // convergence, but it is too strict. A live range with 3 instructions can be
2228  // split 2+3 (including the COPY), and we want to allow that.
2229  //
2230  // Instead we use these rules:
2231  //
2232  // 1. Allow any split for ranges with getStage() < RS_Split2. (Except for the
2233  // noop split, of course).
2234  // 2. Require progress be made for ranges with getStage() == RS_Split2. All
2235  // the new ranges must have fewer instructions than before the split.
2236  // 3. New ranges with the same number of instructions are marked RS_Split2,
2237  // smaller ranges are marked RS_New.
2238  //
2239  // These rules allow a 3 -> 2+3 split once, which we need. They also prevent
2240  // excessive splitting and infinite loops.
2241  //
2242  bool ProgressRequired = getStage(VirtReg) >= RS_Split2;
2243 
2244  // Best split candidate.
2245  unsigned BestBefore = NumGaps;
2246  unsigned BestAfter = 0;
2247  float BestDiff = 0;
2248 
2249  const float blockFreq =
2250  SpillPlacer->getBlockFrequency(BI.MBB->getNumber()).getFrequency() *
2251  (1.0f / MBFI->getEntryFreq());
2252  SmallVector<float, 8> GapWeight;
2253 
2254  Order.rewind();
2255  while (unsigned PhysReg = Order.next()) {
2256  // Keep track of the largest spill weight that would need to be evicted in
2257  // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1].
2258  calcGapWeights(PhysReg, GapWeight);
2259 
2260  // Remove any gaps with regmask clobbers.
2261  if (Matrix->checkRegMaskInterference(VirtReg, PhysReg))
2262  for (unsigned i = 0, e = RegMaskGaps.size(); i != e; ++i)
2263  GapWeight[RegMaskGaps[i]] = huge_valf;
2264 
2265  // Try to find the best sequence of gaps to close.
2266  // The new spill weight must be larger than any gap interference.
2267 
2268  // We will split before Uses[SplitBefore] and after Uses[SplitAfter].
2269  unsigned SplitBefore = 0, SplitAfter = 1;
2270 
2271  // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]).
2272  // It is the spill weight that needs to be evicted.
2273  float MaxGap = GapWeight[0];
2274 
2275  while (true) {
2276  // Live before/after split?
2277  const bool LiveBefore = SplitBefore != 0 || BI.LiveIn;
2278  const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut;
2279 
2280  LLVM_DEBUG(dbgs() << printReg(PhysReg, TRI) << ' ' << Uses[SplitBefore]
2281  << '-' << Uses[SplitAfter] << " i=" << MaxGap);
2282 
2283  // Stop before the interval gets so big we wouldn't be making progress.
2284  if (!LiveBefore && !LiveAfter) {
2285  LLVM_DEBUG(dbgs() << " all\n");
2286  break;
2287  }
2288  // Should the interval be extended or shrunk?
2289  bool Shrink = true;
2290 
2291  // How many gaps would the new range have?
2292  unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter;
2293 
2294  // Legally, without causing looping?
2295  bool Legal = !ProgressRequired || NewGaps < NumGaps;
2296 
2297  if (Legal && MaxGap < huge_valf) {
2298  // Estimate the new spill weight. Each instruction reads or writes the
2299  // register. Conservatively assume there are no read-modify-write
2300  // instructions.
2301  //
2302  // Try to guess the size of the new interval.
2303  const float EstWeight = normalizeSpillWeight(
2304  blockFreq * (NewGaps + 1),
2305  Uses[SplitBefore].distance(Uses[SplitAfter]) +
2306  (LiveBefore + LiveAfter) * SlotIndex::InstrDist,
2307  1);
2308  // Would this split be possible to allocate?
2309  // Never allocate all gaps, we wouldn't be making progress.
2310  LLVM_DEBUG(dbgs() << " w=" << EstWeight);
2311  if (EstWeight * Hysteresis >= MaxGap) {
2312  Shrink = false;
2313  float Diff = EstWeight - MaxGap;
2314  if (Diff > BestDiff) {
2315  LLVM_DEBUG(dbgs() << " (best)");
2316  BestDiff = Hysteresis * Diff;
2317  BestBefore = SplitBefore;
2318  BestAfter = SplitAfter;
2319  }
2320  }
2321  }
2322 
2323  // Try to shrink.
2324  if (Shrink) {
2325  if (++SplitBefore < SplitAfter) {
2326  LLVM_DEBUG(dbgs() << " shrink\n");
2327  // Recompute the max when necessary.
2328  if (GapWeight[SplitBefore - 1] >= MaxGap) {
2329  MaxGap = GapWeight[SplitBefore];
2330  for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i)
2331  MaxGap = std::max(MaxGap, GapWeight[i]);
2332  }
2333  continue;
2334  }
2335  MaxGap = 0;
2336  }
2337 
2338  // Try to extend the interval.
2339  if (SplitAfter >= NumGaps) {
2340  LLVM_DEBUG(dbgs() << " end\n");
2341  break;
2342  }
2343 
2344  LLVM_DEBUG(dbgs() << " extend\n");
2345  MaxGap = std::max(MaxGap, GapWeight[SplitAfter++]);
2346  }
2347  }
2348 
2349  // Didn't find any candidates?
2350  if (BestBefore == NumGaps)
2351  return 0;
2352 
2353  LLVM_DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore] << '-'
2354  << Uses[BestAfter] << ", " << BestDiff << ", "
2355  << (BestAfter - BestBefore + 1) << " instrs\n");
2356 
2357  LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
2358  SE->reset(LREdit);
2359 
2360  SE->openIntv();
2361  SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]);
2362  SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]);
2363  SE->useIntv(SegStart, SegStop);
2364  SmallVector<unsigned, 8> IntvMap;
2365  SE->finish(&IntvMap);
2366  DebugVars->splitRegister(VirtReg.reg, LREdit.regs(), *LIS);
2367 
2368  // If the new range has the same number of instructions as before, mark it as
2369  // RS_Split2 so the next split will be forced to make progress. Otherwise,
2370  // leave the new intervals as RS_New so they can compete.
2371  bool LiveBefore = BestBefore != 0 || BI.LiveIn;
2372  bool LiveAfter = BestAfter != NumGaps || BI.LiveOut;
2373  unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter;
2374  if (NewGaps >= NumGaps) {
2375  LLVM_DEBUG(dbgs() << "Tagging non-progress ranges: ");
2376  assert(!ProgressRequired && "Didn't make progress when it was required.");
2377  for (unsigned i = 0, e = IntvMap.size(); i != e; ++i)
2378  if (IntvMap[i] == 1) {
2379  setStage(LIS->getInterval(LREdit.get(i)), RS_Split2);
2380  LLVM_DEBUG(dbgs() << printReg(LREdit.get(i)));
2381  }
2382  LLVM_DEBUG(dbgs() << '\n');
2383  }
2384  ++NumLocalSplits;
2385 
2386  return 0;
2387 }
2388 
2389 //===----------------------------------------------------------------------===//
2390 // Live Range Splitting
2391 //===----------------------------------------------------------------------===//
2392 
2393 /// trySplit - Try to split VirtReg or one of its interferences, making it
2394 /// assignable.
2395 /// @return Physreg when VirtReg may be assigned and/or new NewVRegs.
2396 unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
2397  SmallVectorImpl<unsigned>&NewVRegs) {
2398  // Ranges must be Split2 or less.
2399  if (getStage(VirtReg) >= RS_Spill)
2400  return 0;
2401 
2402  // Local intervals are handled separately.
2403  if (LIS->intervalIsInOneMBB(VirtReg)) {
2404  NamedRegionTimer T("local_split", "Local Splitting", TimerGroupName,
2405  TimerGroupDescription, TimePassesIsEnabled);
2406  SA->analyze(&VirtReg);
2407  unsigned PhysReg = tryLocalSplit(VirtReg, Order, NewVRegs);
2408  if (PhysReg || !NewVRegs.empty())
2409  return PhysReg;
2410  return tryInstructionSplit(VirtReg, Order, NewVRegs);
2411  }
2412 
2413  NamedRegionTimer T("global_split", "Global Splitting", TimerGroupName,
2414  TimerGroupDescription, TimePassesIsEnabled);
2415 
2416  SA->analyze(&VirtReg);
2417 
2418  // FIXME: SplitAnalysis may repair broken live ranges coming from the
2419  // coalescer. That may cause the range to become allocatable which means that
2420  // tryRegionSplit won't be making progress. This check should be replaced with
2421  // an assertion when the coalescer is fixed.
2422  if (SA->didRepairRange()) {
2423  // VirtReg has changed, so all cached queries are invalid.
2424  Matrix->invalidateVirtRegs();
2425  if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs))
2426  return PhysReg;
2427  }
2428 
2429  // First try to split around a region spanning multiple blocks. RS_Split2
2430  // ranges already made dubious progress with region splitting, so they go
2431  // straight to single block splitting.
2432  if (getStage(VirtReg) < RS_Split2) {
2433  unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
2434  if (PhysReg || !NewVRegs.empty())
2435  return PhysReg;
2436  }
2437 
2438  // Then isolate blocks.
2439  return tryBlockSplit(VirtReg, Order, NewVRegs);
2440 }
2441 
2442 //===----------------------------------------------------------------------===//
2443 // Last Chance Recoloring
2444 //===----------------------------------------------------------------------===//
2445 
2446 /// Return true if \p reg has any tied def operand.
2447 static bool hasTiedDef(MachineRegisterInfo *MRI, unsigned reg) {
2448  for (const MachineOperand &MO : MRI->def_operands(reg))
2449  if (MO.isTied())
2450  return true;
2451 
2452  return false;
2453 }
2454 
2455 /// mayRecolorAllInterferences - Check if the virtual registers that
2456 /// interfere with \p VirtReg on \p PhysReg (or one of its aliases) may be
2457 /// recolored to free \p PhysReg.
2458 /// When true is returned, \p RecoloringCandidates has been augmented with all
2459 /// the live intervals that need to be recolored in order to free \p PhysReg
2460 /// for \p VirtReg.
2461 /// \p FixedRegisters contains all the virtual registers that cannot be
2462 /// recolored.
2463 bool
2464 RAGreedy::mayRecolorAllInterferences(unsigned PhysReg, LiveInterval &VirtReg,
2465  SmallLISet &RecoloringCandidates,
2466  const SmallVirtRegSet &FixedRegisters) {
2467  const TargetRegisterClass *CurRC = MRI->getRegClass(VirtReg.reg);
2468 
2469  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
2470  LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
2471  // If there is LastChanceRecoloringMaxInterference or more interferences,
2472  // chances are one would not be recolorable.
2475  LLVM_DEBUG(dbgs() << "Early abort: too many interferences.\n");
2476  CutOffInfo |= CO_Interf;
2477  return false;
2478  }
2479  for (unsigned i = Q.interferingVRegs().size(); i; --i) {
2480  LiveInterval *Intf = Q.interferingVRegs()[i - 1];
2481  // If Intf is done and sit on the same register class as VirtReg,
2482  // it would not be recolorable as it is in the same state as VirtReg.
2483  // However, if VirtReg has tied defs and Intf doesn't, then
2484  // there is still a point in examining if it can be recolorable.
2485  if (((getStage(*Intf) == RS_Done &&
2486  MRI->getRegClass(Intf->reg) == CurRC) &&
2487  !(hasTiedDef(MRI, VirtReg.reg) && !hasTiedDef(MRI, Intf->reg))) ||
2488  FixedRegisters.count(Intf->reg)) {
2489  LLVM_DEBUG(
2490  dbgs() << "Early abort: the interference is not recolorable.\n");
2491  return false;
2492  }
2493  RecoloringCandidates.insert(Intf);
2494  }
2495  }
2496  return true;
2497 }
2498 
2499 /// tryLastChanceRecoloring - Try to assign a color to \p VirtReg by recoloring
2500 /// its interferences.
2501 /// Last chance recoloring chooses a color for \p VirtReg and recolors every
2502 /// virtual register that was using it. The recoloring process may recursively
2503 /// use the last chance recoloring. Therefore, when a virtual register has been
2504 /// assigned a color by this mechanism, it is marked as Fixed, i.e., it cannot
2505 /// be last-chance-recolored again during this recoloring "session".
2506 /// E.g.,
2507 /// Let
2508 /// vA can use {R1, R2 }
2509 /// vB can use { R2, R3}
2510 /// vC can use {R1 }
2511 /// Where vA, vB, and vC cannot be split anymore (they are reloads for
2512 /// instance) and they all interfere.
2513 ///
2514 /// vA is assigned R1
2515 /// vB is assigned R2
2516 /// vC tries to evict vA but vA is already done.
2517 /// Regular register allocation fails.
2518 ///
2519 /// Last chance recoloring kicks in:
2520 /// vC does as if vA was evicted => vC uses R1.
2521 /// vC is marked as fixed.
2522 /// vA needs to find a color.
2523 /// None are available.
2524 /// vA cannot evict vC: vC is a fixed virtual register now.
2525 /// vA does as if vB was evicted => vA uses R2.
2526 /// vB needs to find a color.
2527 /// R3 is available.
2528 /// Recoloring => vC = R1, vA = R2, vB = R3
2529 ///
2530 /// \p Order defines the preferred allocation order for \p VirtReg.
2531 /// \p NewRegs will contain any new virtual register that have been created
2532 /// (split, spill) during the process and that must be assigned.
2533 /// \p FixedRegisters contains all the virtual registers that cannot be
2534 /// recolored.
2535 /// \p Depth gives the current depth of the last chance recoloring.
2536 /// \return a physical register that can be used for VirtReg or ~0u if none
2537 /// exists.
2538 unsigned RAGreedy::tryLastChanceRecoloring(LiveInterval &VirtReg,
2539  AllocationOrder &Order,
2540  SmallVectorImpl<unsigned> &NewVRegs,
2541  SmallVirtRegSet &FixedRegisters,
2542  unsigned Depth) {
2543  LLVM_DEBUG(dbgs() << "Try last chance recoloring for " << VirtReg << '\n');
2544  // Ranges must be Done.
2545  assert((getStage(VirtReg) >= RS_Done || !VirtReg.isSpillable()) &&
2546  "Last chance recoloring should really be last chance");
2547  // Set the max depth to LastChanceRecoloringMaxDepth.
2548  // We may want to reconsider that if we end up with a too large search space
2549  // for target with hundreds of registers.
2550  // Indeed, in that case we may want to cut the search space earlier.
2552  LLVM_DEBUG(dbgs() << "Abort because max depth has been reached.\n");
2553  CutOffInfo |= CO_Depth;
2554  return ~0u;
2555  }
2556 
2557  // Set of Live intervals that will need to be recolored.
2558  SmallLISet RecoloringCandidates;
2559  // Record the original mapping virtual register to physical register in case
2560  // the recoloring fails.
2561  DenseMap<unsigned, unsigned> VirtRegToPhysReg;
2562  // Mark VirtReg as fixed, i.e., it will not be recolored pass this point in
2563  // this recoloring "session".
2564  FixedRegisters.insert(VirtReg.reg);
2565  SmallVector<unsigned, 4> CurrentNewVRegs;
2566 
2567  Order.rewind();
2568  while (unsigned PhysReg = Order.next()) {
2569  LLVM_DEBUG(dbgs() << "Try to assign: " << VirtReg << " to "
2570  << printReg(PhysReg, TRI) << '\n');
2571  RecoloringCandidates.clear();
2572  VirtRegToPhysReg.clear();
2573  CurrentNewVRegs.clear();
2574 
2575  // It is only possible to recolor virtual register interference.
2576  if (Matrix->checkInterference(VirtReg, PhysReg) >
2578  LLVM_DEBUG(
2579  dbgs() << "Some interferences are not with virtual registers.\n");
2580 
2581  continue;
2582  }
2583 
2584  // Early give up on this PhysReg if it is obvious we cannot recolor all
2585  // the interferences.
2586  if (!mayRecolorAllInterferences(PhysReg, VirtReg, RecoloringCandidates,
2587  FixedRegisters)) {
2588  LLVM_DEBUG(dbgs() << "Some interferences cannot be recolored.\n");
2589  continue;
2590  }
2591 
2592  // RecoloringCandidates contains all the virtual registers that interfer
2593  // with VirtReg on PhysReg (or one of its aliases).
2594  // Enqueue them for recoloring and perform the actual recoloring.
2595  PQueue RecoloringQueue;
2596  for (SmallLISet::iterator It = RecoloringCandidates.begin(),
2597  EndIt = RecoloringCandidates.end();
2598  It != EndIt; ++It) {
2599  unsigned ItVirtReg = (*It)->reg;
2600  enqueue(RecoloringQueue, *It);
2601  assert(VRM->hasPhys(ItVirtReg) &&
2602  "Interferences are supposed to be with allocated vairables");
2603 
2604  // Record the current allocation.
2605  VirtRegToPhysReg[ItVirtReg] = VRM->getPhys(ItVirtReg);
2606  // unset the related struct.
2607  Matrix->unassign(**It);
2608  }
2609 
2610  // Do as if VirtReg was assigned to PhysReg so that the underlying
2611  // recoloring has the right information about the interferes and
2612  // available colors.
2613  Matrix->assign(VirtReg, PhysReg);
2614 
2615  // Save the current recoloring state.
2616  // If we cannot recolor all the interferences, we will have to start again
2617  // at this point for the next physical register.
2618  SmallVirtRegSet SaveFixedRegisters(FixedRegisters);
2619  if (tryRecoloringCandidates(RecoloringQueue, CurrentNewVRegs,
2620  FixedRegisters, Depth)) {
2621  // Push the queued vregs into the main queue.
2622  for (unsigned NewVReg : CurrentNewVRegs)
2623  NewVRegs.push_back(NewVReg);
2624  // Do not mess up with the global assignment process.
2625  // I.e., VirtReg must be unassigned.
2626  Matrix->unassign(VirtReg);
2627  return PhysReg;
2628  }
2629 
2630  LLVM_DEBUG(dbgs() << "Fail to assign: " << VirtReg << " to "
2631  << printReg(PhysReg, TRI) << '\n');
2632 
2633  // The recoloring attempt failed, undo the changes.
2634  FixedRegisters = SaveFixedRegisters;
2635  Matrix->unassign(VirtReg);
2636 
2637  // For a newly created vreg which is also in RecoloringCandidates,
2638  // don't add it to NewVRegs because its physical register will be restored
2639  // below. Other vregs in CurrentNewVRegs are created by calling
2640  // selectOrSplit and should be added into NewVRegs.
2641  for (SmallVectorImpl<unsigned>::iterator Next = CurrentNewVRegs.begin(),
2642  End = CurrentNewVRegs.end();
2643  Next != End; ++Next) {
2644  if (RecoloringCandidates.count(&LIS->getInterval(*Next)))
2645  continue;
2646  NewVRegs.push_back(*Next);
2647  }
2648 
2649  for (SmallLISet::iterator It = RecoloringCandidates.begin(),
2650  EndIt = RecoloringCandidates.end();
2651  It != EndIt; ++It) {
2652  unsigned ItVirtReg = (*It)->reg;
2653  if (VRM->hasPhys(ItVirtReg))
2654  Matrix->unassign(**It);
2655  unsigned ItPhysReg = VirtRegToPhysReg[ItVirtReg];
2656  Matrix->assign(**It, ItPhysReg);
2657  }
2658  }
2659 
2660  // Last chance recoloring did not worked either, give up.
2661  return ~0u;
2662 }
2663 
2664 /// tryRecoloringCandidates - Try to assign a new color to every register
2665 /// in \RecoloringQueue.
2666 /// \p NewRegs will contain any new virtual register created during the
2667 /// recoloring process.
2668 /// \p FixedRegisters[in/out] contains all the registers that have been
2669 /// recolored.
2670 /// \return true if all virtual registers in RecoloringQueue were successfully
2671 /// recolored, false otherwise.
2672 bool RAGreedy::tryRecoloringCandidates(PQueue &RecoloringQueue,
2673  SmallVectorImpl<unsigned> &NewVRegs,
2674  SmallVirtRegSet &FixedRegisters,
2675  unsigned Depth) {
2676  while (!RecoloringQueue.empty()) {
2677  LiveInterval *LI = dequeue(RecoloringQueue);
2678  LLVM_DEBUG(dbgs() << "Try to recolor: " << *LI << '\n');
2679  unsigned PhysReg;
2680  PhysReg = selectOrSplitImpl(*LI, NewVRegs, FixedRegisters, Depth + 1);
2681  // When splitting happens, the live-range may actually be empty.
2682  // In that case, this is okay to continue the recoloring even
2683  // if we did not find an alternative color for it. Indeed,
2684  // there will not be anything to color for LI in the end.
2685  if (PhysReg == ~0u || (!PhysReg && !LI->empty()))
2686  return false;
2687 
2688  if (!PhysReg) {
2689  assert(LI->empty() && "Only empty live-range do not require a register");
2690  LLVM_DEBUG(dbgs() << "Recoloring of " << *LI
2691  << " succeeded. Empty LI.\n");
2692  continue;
2693  }
2694  LLVM_DEBUG(dbgs() << "Recoloring of " << *LI
2695  << " succeeded with: " << printReg(PhysReg, TRI) << '\n');
2696 
2697  Matrix->assign(*LI, PhysReg);
2698  FixedRegisters.insert(LI->reg);
2699  }
2700  return true;
2701 }
2702 
2703 //===----------------------------------------------------------------------===//
2704 // Main Entry Point
2705 //===----------------------------------------------------------------------===//
2706 
2707 unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
2708  SmallVectorImpl<unsigned> &NewVRegs) {
2709  CutOffInfo = CO_None;
2710  LLVMContext &Ctx = MF->getFunction().getContext();
2711  SmallVirtRegSet FixedRegisters;
2712  unsigned Reg = selectOrSplitImpl(VirtReg, NewVRegs, FixedRegisters);
2713  if (Reg == ~0U && (CutOffInfo != CO_None)) {
2714  uint8_t CutOffEncountered = CutOffInfo & (CO_Depth | CO_Interf);
2715  if (CutOffEncountered == CO_Depth)
2716  Ctx.emitError("register allocation failed: maximum depth for recoloring "
2717  "reached. Use -fexhaustive-register-search to skip "
2718  "cutoffs");
2719  else if (CutOffEncountered == CO_Interf)
2720  Ctx.emitError("register allocation failed: maximum interference for "
2721  "recoloring reached. Use -fexhaustive-register-search "
2722  "to skip cutoffs");
2723  else if (CutOffEncountered == (CO_Depth | CO_Interf))
2724  Ctx.emitError("register allocation failed: maximum interference and "
2725  "depth for recoloring reached. Use "
2726  "-fexhaustive-register-search to skip cutoffs");
2727  }
2728  return Reg;
2729 }
2730 
2731 /// Using a CSR for the first time has a cost because it causes push|pop
2732 /// to be added to prologue|epilogue. Splitting a cold section of the live
2733 /// range can have lower cost than using the CSR for the first time;
2734 /// Spilling a live range in the cold path can have lower cost than using
2735 /// the CSR for the first time. Returns the physical register if we decide
2736 /// to use the CSR; otherwise return 0.
2737 unsigned RAGreedy::tryAssignCSRFirstTime(LiveInterval &VirtReg,
2738  AllocationOrder &Order,
2739  unsigned PhysReg,
2740  unsigned &CostPerUseLimit,
2741  SmallVectorImpl<unsigned> &NewVRegs) {
2742  if (getStage(VirtReg) == RS_Spill && VirtReg.isSpillable()) {
2743  // We choose spill over using the CSR for the first time if the spill cost
2744  // is lower than CSRCost.
2745  SA->analyze(&VirtReg);
2746  if (calcSpillCost() >= CSRCost)
2747  return PhysReg;
2748 
2749  // We are going to spill, set CostPerUseLimit to 1 to make sure that
2750  // we will not use a callee-saved register in tryEvict.
2751  CostPerUseLimit = 1;
2752  return 0;
2753  }
2754  if (getStage(VirtReg) < RS_Split) {
2755  // We choose pre-splitting over using the CSR for the first time if
2756  // the cost of splitting is lower than CSRCost.
2757  SA->analyze(&VirtReg);
2758  unsigned NumCands = 0;
2759  BlockFrequency BestCost = CSRCost; // Don't modify CSRCost.
2760  unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, BestCost,
2761  NumCands, true /*IgnoreCSR*/);
2762  if (BestCand == NoCand)
2763  // Use the CSR if we can't find a region split below CSRCost.
2764  return PhysReg;
2765 
2766  // Perform the actual pre-splitting.
2767  doRegionSplit(VirtReg, BestCand, false/*HasCompact*/, NewVRegs);
2768  return 0;
2769  }
2770  return PhysReg;
2771 }
2772 
2773 void RAGreedy::aboutToRemoveInterval(LiveInterval &LI) {
2774  // Do not keep invalid information around.
2775  SetOfBrokenHints.remove(&LI);
2776 }
2777 
2778 void RAGreedy::initializeCSRCost() {
2779  // We use the larger one out of the command-line option and the value report
2780  // by TRI.
2781  CSRCost = BlockFrequency(
2782  std::max((unsigned)CSRFirstTimeCost, TRI->getCSRFirstUseCost()));
2783  if (!CSRCost.getFrequency())
2784  return;
2785 
2786  // Raw cost is relative to Entry == 2^14; scale it appropriately.
2787  uint64_t ActualEntry = MBFI->getEntryFreq();
2788  if (!ActualEntry) {
2789  CSRCost = 0;
2790  return;
2791  }
2792  uint64_t FixedEntry = 1 << 14;
2793  if (ActualEntry < FixedEntry)
2794  CSRCost *= BranchProbability(ActualEntry, FixedEntry);
2795  else if (ActualEntry <= UINT32_MAX)
2796  // Invert the fraction and divide.
2797  CSRCost /= BranchProbability(FixedEntry, ActualEntry);
2798  else
2799  // Can't use BranchProbability in general, since it takes 32-bit numbers.
2800  CSRCost = CSRCost.getFrequency() * (ActualEntry / FixedEntry);
2801 }
2802 
2803 /// Collect the hint info for \p Reg.
2804 /// The results are stored into \p Out.
2805 /// \p Out is not cleared before being populated.
2806 void RAGreedy::collectHintInfo(unsigned Reg, HintsInfo &Out) {
2807  for (const MachineInstr &Instr : MRI->reg_nodbg_instructions(Reg)) {
2808  if (!Instr.isFullCopy())
2809  continue;
2810  // Look for the other end of the copy.
2811  unsigned OtherReg = Instr.getOperand(0).getReg();
2812  if (OtherReg == Reg) {
2813  OtherReg = Instr.getOperand(1).getReg();
2814  if (OtherReg == Reg)
2815  continue;
2816  }
2817  // Get the current assignment.
2818  unsigned OtherPhysReg = TargetRegisterInfo::isPhysicalRegister(OtherReg)
2819  ? OtherReg
2820  : VRM->getPhys(OtherReg);
2821  // Push the collected information.
2822  Out.push_back(HintInfo(MBFI->getBlockFreq(Instr.getParent()), OtherReg,
2823  OtherPhysReg));
2824  }
2825 }
2826 
2827 /// Using the given \p List, compute the cost of the broken hints if
2828 /// \p PhysReg was used.
2829 /// \return The cost of \p List for \p PhysReg.
2830 BlockFrequency RAGreedy::getBrokenHintFreq(const HintsInfo &List,
2831  unsigned PhysReg) {
2832  BlockFrequency Cost = 0;
2833  for (const HintInfo &Info : List) {
2834  if (Info.PhysReg != PhysReg)
2835  Cost += Info.Freq;
2836  }
2837  return Cost;
2838 }
2839 
2840 /// Using the register assigned to \p VirtReg, try to recolor
2841 /// all the live ranges that are copy-related with \p VirtReg.
2842 /// The recoloring is then propagated to all the live-ranges that have
2843 /// been recolored and so on, until no more copies can be coalesced or
2844 /// it is not profitable.
2845 /// For a given live range, profitability is determined by the sum of the
2846 /// frequencies of the non-identity copies it would introduce with the old
2847 /// and new register.
2848 void RAGreedy::tryHintRecoloring(LiveInterval &VirtReg) {
2849  // We have a broken hint, check if it is possible to fix it by
2850  // reusing PhysReg for the copy-related live-ranges. Indeed, we evicted
2851  // some register and PhysReg may be available for the other live-ranges.
2852  SmallSet<unsigned, 4> Visited;
2853  SmallVector<unsigned, 2> RecoloringCandidates;
2854  HintsInfo Info;
2855  unsigned Reg = VirtReg.reg;
2856  unsigned PhysReg = VRM->getPhys(Reg);
2857  // Start the recoloring algorithm from the input live-interval, then
2858  // it will propagate to the ones that are copy-related with it.
2859  Visited.insert(Reg);
2860  RecoloringCandidates.push_back(Reg);
2861 
2862  LLVM_DEBUG(dbgs() << "Trying to reconcile hints for: " << printReg(Reg, TRI)
2863  << '(' << printReg(PhysReg, TRI) << ")\n");
2864 
2865  do {
2866  Reg = RecoloringCandidates.pop_back_val();
2867 
2868  // We cannot recolor physical register.
2870  continue;
2871 
2872  assert(VRM->hasPhys(Reg) && "We have unallocated variable!!");
2873 
2874  // Get the live interval mapped with this virtual register to be able
2875  // to check for the interference with the new color.
2876  LiveInterval &LI = LIS->getInterval(Reg);
2877  unsigned CurrPhys = VRM->getPhys(Reg);
2878  // Check that the new color matches the register class constraints and
2879  // that it is free for this live range.
2880  if (CurrPhys != PhysReg && (!MRI->getRegClass(Reg)->contains(PhysReg) ||
2881  Matrix->checkInterference(LI, PhysReg)))
2882  continue;
2883 
2884  LLVM_DEBUG(dbgs() << printReg(Reg, TRI) << '(' << printReg(CurrPhys, TRI)
2885  << ") is recolorable.\n");
2886 
2887  // Gather the hint info.
2888  Info.clear();
2889  collectHintInfo(Reg, Info);
2890  // Check if recoloring the live-range will increase the cost of the
2891  // non-identity copies.
2892  if (CurrPhys != PhysReg) {
2893  LLVM_DEBUG(dbgs() << "Checking profitability:\n");
2894  BlockFrequency OldCopiesCost = getBrokenHintFreq(Info, CurrPhys);
2895  BlockFrequency NewCopiesCost = getBrokenHintFreq(Info, PhysReg);
2896  LLVM_DEBUG(dbgs() << "Old Cost: " << OldCopiesCost.getFrequency()
2897  << "\nNew Cost: " << NewCopiesCost.getFrequency()
2898  << '\n');
2899  if (OldCopiesCost < NewCopiesCost) {
2900  LLVM_DEBUG(dbgs() << "=> Not profitable.\n");
2901  continue;
2902  }
2903  // At this point, the cost is either cheaper or equal. If it is
2904  // equal, we consider this is profitable because it may expose
2905  // more recoloring opportunities.
2906  LLVM_DEBUG(dbgs() << "=> Profitable.\n");
2907  // Recolor the live-range.
2908  Matrix->unassign(LI);
2909  Matrix->assign(LI, PhysReg);
2910  }
2911  // Push all copy-related live-ranges to keep reconciling the broken
2912  // hints.
2913  for (const HintInfo &HI : Info) {
2914  if (Visited.insert(HI.Reg).second)
2915  RecoloringCandidates.push_back(HI.Reg);
2916  }
2917  } while (!RecoloringCandidates.empty());
2918 }
2919 
2920 /// Try to recolor broken hints.
2921 /// Broken hints may be repaired by recoloring when an evicted variable
2922 /// freed up a register for a larger live-range.
2923 /// Consider the following example:
2924 /// BB1:
2925 /// a =
2926 /// b =
2927 /// BB2:
2928 /// ...
2929 /// = b
2930 /// = a
2931 /// Let us assume b gets split:
2932 /// BB1:
2933 /// a =
2934 /// b =
2935 /// BB2:
2936 /// c = b
2937 /// ...
2938 /// d = c
2939 /// = d
2940 /// = a
2941 /// Because of how the allocation work, b, c, and d may be assigned different
2942 /// colors. Now, if a gets evicted later:
2943 /// BB1:
2944 /// a =
2945 /// st a, SpillSlot
2946 /// b =
2947 /// BB2:
2948 /// c = b
2949 /// ...
2950 /// d = c
2951 /// = d
2952 /// e = ld SpillSlot
2953 /// = e
2954 /// This is likely that we can assign the same register for b, c, and d,
2955 /// getting rid of 2 copies.
2956 void RAGreedy::tryHintsRecoloring() {
2957  for (LiveInterval *LI : SetOfBrokenHints) {
2959  "Recoloring is possible only for virtual registers");
2960  // Some dead defs may be around (e.g., because of debug uses).
2961  // Ignore those.
2962  if (!VRM->hasPhys(LI->reg))
2963  continue;
2964  tryHintRecoloring(*LI);
2965  }
2966 }
2967 
2968 unsigned RAGreedy::selectOrSplitImpl(LiveInterval &VirtReg,
2969  SmallVectorImpl<unsigned> &NewVRegs,
2970  SmallVirtRegSet &FixedRegisters,
2971  unsigned Depth) {
2972  unsigned CostPerUseLimit = ~0u;
2973  // First try assigning a free register.
2974  AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo, Matrix);
2975  if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) {
2976  // If VirtReg got an assignment, the eviction info is no longre relevant.
2977  LastEvicted.clearEvicteeInfo(VirtReg.reg);
2978  // When NewVRegs is not empty, we may have made decisions such as evicting
2979  // a virtual register, go with the earlier decisions and use the physical
2980  // register.
2981  if (CSRCost.getFrequency() && isUnusedCalleeSavedReg(PhysReg) &&
2982  NewVRegs.empty()) {
2983  unsigned CSRReg = tryAssignCSRFirstTime(VirtReg, Order, PhysReg,
2984  CostPerUseLimit, NewVRegs);
2985  if (CSRReg || !NewVRegs.empty())
2986  // Return now if we decide to use a CSR or create new vregs due to
2987  // pre-splitting.
2988  return CSRReg;
2989  } else
2990  return PhysReg;
2991  }
2992 
2993  LiveRangeStage Stage = getStage(VirtReg);
2994  LLVM_DEBUG(dbgs() << StageName[Stage] << " Cascade "
2995  << ExtraRegInfo[VirtReg.reg].Cascade << '\n');
2996 
2997  // Try to evict a less worthy live range, but only for ranges from the primary
2998  // queue. The RS_Split ranges already failed to do this, and they should not
2999  // get a second chance until they have been split.
3000  if (Stage != RS_Split)
3001  if (unsigned PhysReg =
3002  tryEvict(VirtReg, Order, NewVRegs, CostPerUseLimit)) {
3003  unsigned Hint = MRI->getSimpleHint(VirtReg.reg);
3004  // If VirtReg has a hint and that hint is broken record this
3005  // virtual register as a recoloring candidate for broken hint.
3006  // Indeed, since we evicted a variable in its neighborhood it is
3007  // likely we can at least partially recolor some of the
3008  // copy-related live-ranges.
3009  if (Hint && Hint != PhysReg)
3010  SetOfBrokenHints.insert(&VirtReg);
3011  // If VirtReg eviction someone, the eviction info for it as an evictee is
3012  // no longre relevant.
3013  LastEvicted.clearEvicteeInfo(VirtReg.reg);
3014  return PhysReg;
3015  }
3016 
3017  assert((NewVRegs.empty() || Depth) && "Cannot append to existing NewVRegs");
3018 
3019  // The first time we see a live range, don't try to split or spill.
3020  // Wait until the second time, when all smaller ranges have been allocated.
3021  // This gives a better picture of the interference to split around.
3022  if (Stage < RS_Split) {
3023  setStage(VirtReg, RS_Split);
3024  LLVM_DEBUG(dbgs() << "wait for second round\n");
3025  NewVRegs.push_back(VirtReg.reg);
3026  return 0;
3027  }
3028 
3029  if (Stage < RS_Spill) {
3030  // Try splitting VirtReg or interferences.
3031  unsigned NewVRegSizeBefore = NewVRegs.size();
3032  unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs);
3033  if (PhysReg || (NewVRegs.size() - NewVRegSizeBefore)) {
3034  // If VirtReg got split, the eviction info is no longre relevant.
3035  LastEvicted.clearEvicteeInfo(VirtReg.reg);
3036  return PhysReg;
3037  }
3038  }
3039 
3040  // If we couldn't allocate a register from spilling, there is probably some
3041  // invalid inline assembly. The base class will report it.
3042  if (Stage >= RS_Done || !VirtReg.isSpillable())
3043  return tryLastChanceRecoloring(VirtReg, Order, NewVRegs, FixedRegisters,
3044  Depth);
3045 
3046  // Finally spill VirtReg itself.
3047  if (EnableDeferredSpilling && getStage(VirtReg) < RS_Memory) {
3048  // TODO: This is experimental and in particular, we do not model
3049  // the live range splitting done by spilling correctly.
3050  // We would need a deep integration with the spiller to do the
3051  // right thing here. Anyway, that is still good for early testing.
3052  setStage(VirtReg, RS_Memory);
3053  LLVM_DEBUG(dbgs() << "Do as if this register is in memory\n");
3054  NewVRegs.push_back(VirtReg.reg);
3055  } else {
3056  NamedRegionTimer T("spill", "Spiller", TimerGroupName,
3057  TimerGroupDescription, TimePassesIsEnabled);
3058  LiveRangeEdit LRE(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
3059  spiller().spill(LRE);
3060  setStage(NewVRegs.begin(), NewVRegs.end(), RS_Done);
3061 
3062  if (VerifyEnabled)
3063  MF->verify(this, "After spilling");
3064  }
3065 
3066  // The live virtual register requesting allocation was spilled, so tell
3067  // the caller not to allocate anything during this round.
3068  return 0;
3069 }
3070 
3071 void RAGreedy::reportNumberOfSplillsReloads(MachineLoop *L, unsigned &Reloads,
3072  unsigned &FoldedReloads,
3073  unsigned &Spills,
3074  unsigned &FoldedSpills) {
3075  Reloads = 0;
3076  FoldedReloads = 0;
3077  Spills = 0;
3078  FoldedSpills = 0;
3079 
3080  // Sum up the spill and reloads in subloops.
3081  for (MachineLoop *SubLoop : *L) {
3082  unsigned SubReloads;
3083  unsigned SubFoldedReloads;
3084  unsigned SubSpills;
3085  unsigned SubFoldedSpills;
3086 
3087  reportNumberOfSplillsReloads(SubLoop, SubReloads, SubFoldedReloads,
3088  SubSpills, SubFoldedSpills);
3089  Reloads += SubReloads;
3090  FoldedReloads += SubFoldedReloads;
3091  Spills += SubSpills;
3092  FoldedSpills += SubFoldedSpills;
3093  }
3094 
3095  const MachineFrameInfo &MFI = MF->getFrameInfo();
3096  const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
3097  int FI;
3098 
3099  for (MachineBasicBlock *MBB : L->getBlocks())
3100  // Handle blocks that were not included in subloops.
3101  if (Loops->getLoopFor(MBB) == L)
3102  for (MachineInstr &MI : *MBB) {
3103  const MachineMemOperand *MMO;
3104 
3105  if (TII->isLoadFromStackSlot(MI, FI) && MFI.isSpillSlotObjectIndex(FI))
3106  ++Reloads;
3107  else if (TII->hasLoadFromStackSlot(MI, MMO, FI) &&
3108  MFI.isSpillSlotObjectIndex(FI))
3109  ++FoldedReloads;
3110  else if (TII->isStoreToStackSlot(MI, FI) &&
3111  MFI.isSpillSlotObjectIndex(FI))
3112  ++Spills;
3113  else if (TII->hasStoreToStackSlot(MI, MMO, FI) &&
3114  MFI.isSpillSlotObjectIndex(FI))
3115  ++FoldedSpills;
3116  }
3117 
3118  if (Reloads || FoldedReloads || Spills || FoldedSpills) {
3119  using namespace ore;
3120 
3121  ORE->emit([&]() {
3122  MachineOptimizationRemarkMissed R(DEBUG_TYPE, "LoopSpillReload",
3123  L->getStartLoc(), L->getHeader());
3124  if (Spills)
3125  R << NV("NumSpills", Spills) << " spills ";
3126  if (FoldedSpills)
3127  R << NV("NumFoldedSpills", FoldedSpills) << " folded spills ";
3128  if (Reloads)
3129  R << NV("NumReloads", Reloads) << " reloads ";
3130  if (FoldedReloads)
3131  R << NV("NumFoldedReloads", FoldedReloads) << " folded reloads ";
3132  R << "generated in loop";
3133  return R;
3134  });
3135  }
3136 }
3137 
3138 bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
3139  LLVM_DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
3140  << "********** Function: " << mf.getName() << '\n');
3141 
3142  MF = &mf;
3143  TRI = MF->getSubtarget().getRegisterInfo();
3144  TII = MF->getSubtarget().getInstrInfo();
3145  RCI.runOnMachineFunction(mf);
3146 
3147  EnableLocalReassign = EnableLocalReassignment ||
3148  MF->getSubtarget().enableRALocalReassignment(
3149  MF->getTarget().getOptLevel());
3150 
3151  EnableAdvancedRASplitCost = ConsiderLocalIntervalCost ||
3152  MF->getSubtarget().enableAdvancedRASplitCost();
3153 
3154  if (VerifyEnabled)
3155  MF->verify(this, "Before greedy register allocator");
3156 
3157  RegAllocBase::init(getAnalysis<VirtRegMap>(),
3158  getAnalysis<LiveIntervals>(),
3159  getAnalysis<LiveRegMatrix>());
3160  Indexes = &getAnalysis<SlotIndexes>();
3161  MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
3162  DomTree = &getAnalysis<MachineDominatorTree>();
3163  ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
3164  SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
3165  Loops = &getAnalysis<MachineLoopInfo>();
3166  Bundles = &getAnalysis<EdgeBundles>();
3167  SpillPlacer = &getAnalysis<SpillPlacement>();
3168  DebugVars = &getAnalysis<LiveDebugVariables>();
3169  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
3170 
3171  initializeCSRCost();
3172 
3173  calculateSpillWeightsAndHints(*LIS, mf, VRM, *Loops, *MBFI);
3174 
3175  LLVM_DEBUG(LIS->dump());
3176 
3177  SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops));
3178  SE.reset(new SplitEditor(*SA, *AA, *LIS, *VRM, *DomTree, *MBFI));
3179  ExtraRegInfo.clear();
3180  ExtraRegInfo.resize(MRI->getNumVirtRegs());
3181  NextCascade = 1;
3182  IntfCache.init(MF, Matrix->getLiveUnions(), Indexes, LIS, TRI);
3183  GlobalCand.resize(32); // This will grow as needed.
3184  SetOfBrokenHints.clear();
3185  LastEvicted.clear();
3186 
3187  allocatePhysRegs();
3188  tryHintsRecoloring();
3189  postOptimization();
3190  reportNumberOfSplillsReloads();
3191 
3192  releaseMemory();
3193  return true;
3194 }
bool isHint() const
Return true if the last register returned from next() was a preferred register.
const T & front() const
front - Get the first element.
Definition: ArrayRef.h:152
uint64_t CallInst * C
bool empty() const
Definition: LiveInterval.h:370
void push_back(const T &Elt)
Definition: SmallVector.h:212
void setPhysReg(InterferenceCache &Cache, unsigned PhysReg)
setPhysReg - Point this cursor to PhysReg&#39;s interference.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Calculate auxiliary information for a virtual register such as its spill weight and allocation hint...
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
const unsigned reg
Definition: LiveInterval.h:667
const T & back() const
back - Get the last element.
Definition: ArrayRef.h:158
DiagnosticInfoOptimizationBase::Argument NV
unsigned getBundle(unsigned N, bool Out) const
getBundle - Return the ingoing (Out = false) or outgoing (Out = true) bundle number for basic block N...
Definition: EdgeBundles.h:43
SlotIndex getBaseIndex() const
Returns the base index for associated with this index.
Definition: SlotIndexes.h:242
void rewind()
Start over from the beginning.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
unsigned getNumRegs() const
Return the number of registers in this class.
iterator begin() const
Definition: ArrayRef.h:137
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
A register is impossible, variable must be spilled.
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:638
SM_Speed - Overlap intervals to minimize the expected execution frequency of the inserted copies...
Definition: SplitKit.h:276
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
unsigned Reg
unsigned getCostPerUse(unsigned RegNo) const
Return the additional cost of using this register instead of other registers in its class...
bool test(unsigned Idx) const
Definition: BitVector.h:502
Spiller interface.
Definition: Spiller.h:24
uint64_t getFrequency() const
Returns the frequency as a fixpoint number scaled by the entry frequency.
SlotIndex FirstDef
First non-phi valno->def, or SlotIndex().
Definition: SplitKit.h:112
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
virtual bool reverseLocalAssignment() const
Allow the target to reverse allocation order of local live ranges.
unsigned next(unsigned Limit=0)
Return the next physical register in the allocation order, or 0.
This class implements a map that also provides access to all stored values in a deterministic order...
Definition: MapVector.h:38
bool isValid() const
Returns true if this is a valid index.
Definition: SlotIndexes.h:152
STATISTIC(NumFunctions, "Total number of functions")
ArrayRef< unsigned > regs() const
unsigned const TargetRegisterInfo * TRI
bool valid() const
valid - Return true if the current position is valid, false for end().
Definition: IntervalMap.h:1349
char & RAGreedyID
Greedy register allocator.
Callback methods for LiveRangeEdit owners.
Definition: LiveRangeEdit.h:49
static cl::opt< bool > EnableDeferredSpilling("enable-deferred-spilling", cl::Hidden, cl::desc("Instead of spilling a variable right away, defer the actual " "code insertion to the end of the allocation. That way the " "allocator might still find a suitable coloring for this " "variable because of other evicted variables."), cl::init(false))
Live Register Matrix
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
#define DEBUG_TYPE
ArrayRef< unsigned > getBlocks(unsigned Bundle) const
getBlocks - Return an array of blocks that are connected to Bundle.
Definition: EdgeBundles.h:49
static bool isEarlierInstr(SlotIndex A, SlotIndex B)
isEarlierInstr - Return true if A refers to an instruction earlier than B.
Definition: SlotIndexes.h:204
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:191
const char * getRegClassName(const TargetRegisterClass *Class) const
Returns the name of the register class.
SlotIndex getLastIndex()
Returns the base index of the last slot in this analysis.
Definition: SlotIndexes.h:403
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Emit an optimization remark.
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
Hexagon Hardware Loops
A description of a memory reference used in the backend.
const float Hysteresis
void clear()
clear - Removes all bits from the bitvector. Does not change capacity.
Definition: BitVector.h:367
Query interferences between a single live virtual register and a live interval union.
void addPrefSpill(ArrayRef< unsigned > Blocks, bool Strong)
addPrefSpill - Add PrefSpill constraints to all blocks listed.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
static cl::opt< unsigned > LastChanceRecoloringMaxDepth("lcr-max-depth", cl::Hidden, cl::desc("Last chance recoloring max depth"), cl::init(5))
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:451
bool scanActiveBundles()
scanActiveBundles - Perform an initial scan of all bundles activated by addConstraints and addLinks...
void init(MachineFunction *mf, LiveIntervalUnion *liuarray, SlotIndexes *indexes, LiveIntervals *lis, const TargetRegisterInfo *tri)
init - Prepare cache for a new function.
This class is basically a combination of TimeRegion and Timer.
Definition: Timer.h:161
ArrayRef< unsigned > getRecentPositive()
getRecentPositive - Return an array of bundles that became positive during the previous call to scanA...
iterator end()
Definition: LiveInterval.h:212
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted...
static cl::opt< bool > EnableLocalReassignment("enable-local-reassign", cl::Hidden, cl::desc("Local reassignment can yield better allocation decisions, but " "may be compile time intensive"), cl::init(false))
void iterate()
iterate - Update the network iteratively until convergence, or new bundles are found.
bool remove(const value_type &X)
Remove an item from the set vector.
Definition: SetVector.h:158
RegAllocBase provides the register allocation driver and interface that can be extended to add intere...
Definition: RegAllocBase.h:61
BorderConstraint Exit
Constraint on block exit.
void assign(size_type NumElts, const T &Elt)
Definition: SmallVector.h:425
MachineBasicBlock * MBB
Definition: SplitKit.h:109
void emitError(unsigned LocCookie, const Twine &ErrorStr)
emitError - Emit an error message to the currently installed error handler with optional location inf...
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:142
SlotIndexes pass.
Definition: SlotIndexes.h:331
SlotIndex getRegSlot(bool EC=false) const
Returns the register use/def slot in the current instruction for a normal or early-clobber def...
Definition: SlotIndexes.h:255
const SmallVectorImpl< LiveInterval * > & interferingVRegs() const
#define T
SplitEditor - Edit machine code and LiveIntervals for live range splitting.
Definition: SplitKit.h:241
iterator_range< def_iterator > def_operands(unsigned Reg) const
INITIALIZE_PASS_BEGIN(RAGreedy, "greedy", "Greedy Register Allocator", false, false) INITIALIZE_PASS_END(RAGreedy
virtual unsigned isStoreToStackSlot(const MachineInstr &MI, int &FrameIndex) const
If the specified machine instruction is a direct store to a stack slot, return the virtual or physica...
auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range))
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1004
const float huge_valf
Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
Definition: MathExtras.cpp:29
virtual const TargetRegisterClass * getLargestLegalSuperClass(const TargetRegisterClass *RC, const MachineFunction &) const
Returns the largest super class of RC that is legal to use in the current sub-target and has the same...
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
RegisterRegAlloc class - Track the registration of register allocators.
virtual const TargetInstrInfo * getInstrInfo() const
BlockConstraint - Entry and exit constraints for a basic block.
bool inBounds(IndexT n) const
Definition: IndexedMap.h:74
SlotIndex LastInstr
Last instr accessing current reg.
Definition: SplitKit.h:111
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
float futureWeight(LiveInterval &li, SlotIndex start, SlotIndex end)
Compute future expected spill weight of a split artifact of li that will span between start and end s...
TargetInstrInfo - Interface to description of machine instruction set.
static cl::opt< unsigned > CSRFirstTimeCost("regalloc-csr-first-time-cost", cl::desc("Cost for first time use of callee-saved register."), cl::init(0), cl::Hidden)
void addLinks(ArrayRef< unsigned > Links)
addLinks - Add transparent blocks with the given numbers.
===- MachineOptimizationRemarkEmitter.h - Opt Diagnostics -*- C++ -*-—===//
unsigned collectInterferingVRegs(unsigned MaxInterferingRegs=std::numeric_limits< unsigned >::max())
SlotIndex last()
last - Return the ending index of the last interfering range in the current block.
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction for the given index, or null if the given index has no instruction associated...
Definition: SlotIndexes.h:424
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:410
SlotIndex endIndex() const
endNumber - return the maximum point of the range of the whole, exclusive.
Definition: LiveInterval.h:380
const uint8_t AllocationPriority
Classes with a higher priority value are assigned first by register allocators using a greedy heurist...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
unsigned const MachineRegisterInfo * MRI
Block doesn&#39;t care / variable not live.
BlockFrequency getBlockFrequency(unsigned Number) const
getBlockFrequency - Return the estimated block execution frequency per function invocation.
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubRegIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
Cursor - The primary query interface for the block interference cache.
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:630
SM_Partition(Default) - Try to create the complement interval so it doesn&#39;t overlap any other interva...
Definition: SplitKit.h:264
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
ArrayRef< MCPhysReg > getOrder() const
Get the allocation order without reordered hints.
const KeyT & start() const
start - Return the beginning of the current interval.
Definition: IntervalMap.h:1355
SM_Size - Overlap intervals to minimize the number of inserted COPY instructions. ...
Definition: SplitKit.h:271
BlockFrequency getBlockFreq(const MachineBasicBlock *MBB) const
getblockFreq - Return block frequency.
unsigned size() const
raw_ostream & printBlockFreq(raw_ostream &OS, const BlockFrequency Freq) const
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Definition: SlotIndexes.h:487
Represent the analysis usage information of a pass.
Greedy Register Allocator
static unsigned getNumAllocatableRegsForConstraints(const MachineInstr *MI, unsigned Reg, const TargetRegisterClass *SuperRC, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, const RegisterClassInfo &RCI)
Get the number of allocatable registers that match the constraints of Reg on MI and that are also in ...
int getInstrDistance(SlotIndex other) const
Return the scaled distance from this index to the given one, where all slots on the same instruction ...
Definition: SlotIndexes.h:221
unsigned Number
Basic block number (from MBB::getNumber()).
BitVector & reset()
Definition: BitVector.h:439
SlotIndex getZeroIndex()
Returns the zero index for this analysis.
Definition: SlotIndexes.h:397
void resize(typename StorageT::size_type s)
Definition: IndexedMap.h:60
static const unsigned End
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
unsigned getNumAllocatableRegs(const TargetRegisterClass *RC) const
getNumAllocatableRegs - Returns the number of actually allocatable registers in RC in the current fun...
static cl::opt< SplitEditor::ComplementSpillMode > SplitSpillMode("split-spill-mode", cl::Hidden, cl::desc("Spill mode for splitting live ranges"), cl::values(clEnumValN(SplitEditor::SM_Partition, "default", "Default"), clEnumValN(SplitEditor::SM_Size, "size", "Optimize for size"), clEnumValN(SplitEditor::SM_Speed, "speed", "Optimize for speed")), cl::init(SplitEditor::SM_Speed))
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:81
void runOnMachineFunction(const MachineFunction &MF)
runOnFunction - Prepare to answer questions about MF.
void init(VirtRegMap &vrm, LiveIntervals &lis, LiveRegMatrix &mat)
virtual unsigned getCSRFirstUseCost() const
Allow the target to override the cost of using a callee-saved register for the first time...
static cl::opt< bool > ConsiderLocalIntervalCost("condsider-local-interval-cost", cl::Hidden, cl::desc("Consider the cost of local intervals created by a split " "candidate when choosing the best split candidate."), cl::init(false))
bool empty() const
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:193
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
BorderConstraint Entry
Constraint on block entry.
bool finish()
finish - Compute the optimal spill code placement given the constraints.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Block entry/exit prefers a register.
void addConstraints(ArrayRef< BlockConstraint > LiveBlocks)
addConstraints - Add constraints and biases.
iterator find(SlotIndex Pos)
find - Return an iterator pointing to the first segment that ends after Pos, or end().
static bool hasTiedDef(MachineRegisterInfo *MRI, unsigned reg)
Return true if reg has any tied def operand.
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:298
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
virtual bool hasLoadFromStackSlot(const MachineInstr &MI, const MachineMemOperand *&MMO, int &FrameIndex) const
If the specified machine instruction has a load from a stack slot, return true along with the FrameIn...
void calculateSpillWeightsAndHints(LiveIntervals &LIS, MachineFunction &MF, VirtRegMap *VRM, const MachineLoopInfo &MLI, const MachineBlockFrequencyInfo &MBFI, VirtRegAuxInfo::NormalizingFn norm=normalizeSpillWeight)
Compute spill weights and allocation hints for all virtual register live intervals.
static bool isSameInstr(SlotIndex A, SlotIndex B)
isSameInstr - Return true if A and B refer to the same instruction.
Definition: SlotIndexes.h:198
void splitRegister(unsigned OldReg, ArrayRef< unsigned > NewRegs, LiveIntervals &LIS)
splitRegister - Move any user variables in OldReg to the live ranges in NewRegs where they are live...
Segments::const_iterator const_iterator
Definition: LiveInterval.h:209
Block entry/exit prefers a stack slot.
The optimization diagnostic interface.
SlotIndex FirstInstr
First instr accessing current reg.
Definition: SplitKit.h:110
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:862
iterator end() const
Definition: ArrayRef.h:138
Additional information about basic blocks where the current variable is live.
Definition: SplitKit.h:108
Promote Memory to Register
Definition: Mem2Reg.cpp:110
SplitAnalysis - Analyze a LiveInterval, looking for live range splitting opportunities.
Definition: SplitKit.h:83
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:383
void prepare(BitVector &RegBundles)
prepare - Reset state and prepare for a new spill placement computation.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:286
bool hasInterference()
hasInterference - Return true if the current block has any interference.
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
unsigned getSize() const
getSize - Returns the sum of sizes of all the LiveRange&#39;s.
const ValT & value() const
value - Return the mapped value at the current interval.
Definition: IntervalMap.h:1361
virtual bool hasStoreToStackSlot(const MachineInstr &MI, const MachineMemOperand *&MMO, int &FrameIndex) const
If the specified machine instruction has a store to a stack slot, return true along with the FrameInd...
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
bool LiveOut
Current reg is live out.
Definition: SplitKit.h:114
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:211
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:396
unsigned getNumBundles() const
getNumBundles - Return the total number of bundles in the CFG.
Definition: EdgeBundles.h:46
void moveToBlock(unsigned MBBNum)
moveTo - Move cursor to basic block MBBNum.
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:605
const KeyT & stop() const
stop - Return the end of the current interval.
Definition: IntervalMap.h:1358
static cl::opt< unsigned > LastChanceRecoloringMaxInterference("lcr-max-interf", cl::Hidden, cl::desc("Last chance recoloring maximum number of considered" " interference at a time"), cl::init(8))
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
MachineFunctionProperties & set(Property P)
Spiller * createInlineSpiller(MachineFunctionPass &pass, MachineFunction &mf, VirtRegMap &vrm)
Create and return a spiller that will insert spill code directly instead of deferring though VirtRegM...
Representation of each machine instruction.
Definition: MachineInstr.h:60
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
static uint64_t getMaxFrequency()
Returns the maximum possible frequency, the saturation value.
bool overlaps(const LiveRange &other) const
overlaps - Return true if the intersection of the two live ranges is not empty.
Definition: LiveInterval.h:436
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
bool verify(Pass *p=nullptr, const char *Banner=nullptr, bool AbortOnError=true) const
Run the current MachineFunction through the machine code verifier, useful for debugger use...
iterator begin() const
virtual unsigned isLoadFromStackSlot(const MachineInstr &MI, int &FrameIndex) const
If the specified machine instruction is a direct load from a stack slot, return the virtual or physic...
FunctionPass * createGreedyRegisterAllocator()
Greedy register allocation pass - This pass implements a global register allocator for optimized buil...
const NodeList & List
Definition: RDFGraph.cpp:210
static cl::opt< bool > ExhaustiveSearch("exhaustive-register-search", cl::NotHidden, cl::desc("Exhaustive Search for registers bypassing the depth " "and interference cutoffs of last chance recoloring"), cl::Hidden)
const TargetRegisterClass * getRegClassConstraintEffectForVReg(unsigned Reg, const TargetRegisterClass *CurRC, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, bool ExploreBundle=false) const
Applies the constraints (def/use) implied by this MI on Reg to the given CurRC.
#define I(x, y, z)
Definition: MD5.cpp:58
static RegisterRegAlloc greedyRegAlloc("greedy", "greedy register allocator", createGreedyRegisterAllocator)
The default distance between instructions as returned by distance().
Definition: SlotIndexes.h:138
Diagnostic information for missed-optimization remarks.
iterator end() const
void grow(IndexT n)
Definition: IndexedMap.h:68
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static float normalizeSpillWeight(float UseDefFreq, unsigned Size, unsigned NumInstr)
Normalize the spill weight of a live interval.
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:326
bool isSpillable() const
isSpillable - Can this interval be spilled?
Definition: LiveInterval.h:767
SlotIndex beginIndex() const
beginIndex - Return the lowest numbered slot covered.
Definition: LiveInterval.h:373
iterator_range< const_set_bits_iterator > set_bits() const
Definition: BitVector.h:130
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
iterator FindSegmentContaining(SlotIndex Idx)
Return an iterator to the segment that contains the specified index, or end() if there is none...
Definition: LiveInterval.h:424
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
bool TimePassesIsEnabled
If the user specifies the -time-passes argument on an LLVM tool command line then the value of this b...
Definition: IRReader.cpp:25
#define LLVM_DEBUG(X)
Definition: Debug.h:119
bool LiveIn
Current reg is live in.
Definition: SplitKit.h:113
unsigned getMaxCursors() const
getMaxCursors - Return the maximum number of concurrent cursors that can be supported.
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:84
Virtual register interference.
Definition: LiveRegMatrix.h:91
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
The operation is expected to be selectable directly by the target, and no transformation is necessary...
Definition: LegalizerInfo.h:45
SlotIndex first()
first - Return the starting index of the first interfering range in the current block.
unsigned get(unsigned idx) const
SlotIndex getBoundaryIndex() const
Returns the boundary index for associated with this index.
Definition: SlotIndexes.h:249
bool isSpillSlotObjectIndex(int ObjectIdx) const
Returns true if the specified index corresponds to a spill slot.
Properties which a MachineFunction may have at a given point in time.
void resize(size_type N)
Definition: SmallVector.h:353
bool ChangesValue
True when this block changes the value of the live range.