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  /// \brief Clear all eviction information.
304  void clear() { Evictees.clear(); }
305 
306  /// \brief 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  /// \brief 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  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  DEBUG(dbgs() << printReg(PhysReg, TRI) << " is available at cost " << Cost
789  << '\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  DEBUG(dbgs() << "can reassign: " << VirtReg << " from "
818  << printReg(PrevReg, TRI) << " to " << printReg(PhysReg, TRI)
819  << '\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  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 /// \brief 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 /// \brief 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  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  DEBUG(dbgs() << TRI->getRegClassName(RC) << " minimum cost = " << MinCost
1111  << ", 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  DEBUG(dbgs() << "Only trying the first " << OrderLimit << " regs.\n");
1120  }
1121  }
1122 
1123  Order.rewind();
1124  while (unsigned PhysReg = Order.next(OrderLimit)) {
1125  if (TRI->getCostPerUse(PhysReg) >= CostPerUseLimit)
1126  continue;
1127  // The first use of a callee-saved register in a function has cost 1.
1128  // Don't start using a CSR when the CostPerUseLimit is low.
1129  if (CostPerUseLimit == 1 && isUnusedCalleeSavedReg(PhysReg)) {
1130  DEBUG(dbgs() << printReg(PhysReg, TRI) << " would clobber CSR "
1131  << printReg(RegClassInfo.getLastCalleeSavedAlias(PhysReg), TRI)
1132  << '\n');
1133  continue;
1134  }
1135 
1136  if (!canEvictInterference(VirtReg, PhysReg, false, BestCost))
1137  continue;
1138 
1139  // Best so far.
1140  BestPhys = PhysReg;
1141 
1142  // Stop if the hint can be used.
1143  if (Order.isHint())
1144  break;
1145  }
1146 
1147  if (!BestPhys)
1148  return 0;
1149 
1150  evictInterference(VirtReg, BestPhys, NewVRegs);
1151  return BestPhys;
1152 }
1153 
1154 //===----------------------------------------------------------------------===//
1155 // Region Splitting
1156 //===----------------------------------------------------------------------===//
1157 
1158 /// addSplitConstraints - Fill out the SplitConstraints vector based on the
1159 /// interference pattern in Physreg and its aliases. Add the constraints to
1160 /// SpillPlacement and return the static cost of this split in Cost, assuming
1161 /// that all preferences in SplitConstraints are met.
1162 /// Return false if there are no bundles with positive bias.
1163 bool RAGreedy::addSplitConstraints(InterferenceCache::Cursor Intf,
1164  BlockFrequency &Cost) {
1165  ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1166 
1167  // Reset interference dependent info.
1168  SplitConstraints.resize(UseBlocks.size());
1169  BlockFrequency StaticCost = 0;
1170  for (unsigned i = 0; i != UseBlocks.size(); ++i) {
1171  const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
1172  SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
1173 
1174  BC.Number = BI.MBB->getNumber();
1175  Intf.moveToBlock(BC.Number);
1178  BC.ChangesValue = BI.FirstDef.isValid();
1179 
1180  if (!Intf.hasInterference())
1181  continue;
1182 
1183  // Number of spill code instructions to insert.
1184  unsigned Ins = 0;
1185 
1186  // Interference for the live-in value.
1187  if (BI.LiveIn) {
1188  if (Intf.first() <= Indexes->getMBBStartIdx(BC.Number)) {
1190  ++Ins;
1191  } else if (Intf.first() < BI.FirstInstr) {
1193  ++Ins;
1194  } else if (Intf.first() < BI.LastInstr) {
1195  ++Ins;
1196  }
1197  }
1198 
1199  // Interference for the live-out value.
1200  if (BI.LiveOut) {
1201  if (Intf.last() >= SA->getLastSplitPoint(BC.Number)) {
1203  ++Ins;
1204  } else if (Intf.last() > BI.LastInstr) {
1206  ++Ins;
1207  } else if (Intf.last() > BI.FirstInstr) {
1208  ++Ins;
1209  }
1210  }
1211 
1212  // Accumulate the total frequency of inserted spill code.
1213  while (Ins--)
1214  StaticCost += SpillPlacer->getBlockFrequency(BC.Number);
1215  }
1216  Cost = StaticCost;
1217 
1218  // Add constraints for use-blocks. Note that these are the only constraints
1219  // that may add a positive bias, it is downhill from here.
1220  SpillPlacer->addConstraints(SplitConstraints);
1221  return SpillPlacer->scanActiveBundles();
1222 }
1223 
1224 /// addThroughConstraints - Add constraints and links to SpillPlacer from the
1225 /// live-through blocks in Blocks.
1226 void RAGreedy::addThroughConstraints(InterferenceCache::Cursor Intf,
1227  ArrayRef<unsigned> Blocks) {
1228  const unsigned GroupSize = 8;
1229  SpillPlacement::BlockConstraint BCS[GroupSize];
1230  unsigned TBS[GroupSize];
1231  unsigned B = 0, T = 0;
1232 
1233  for (unsigned i = 0; i != Blocks.size(); ++i) {
1234  unsigned Number = Blocks[i];
1235  Intf.moveToBlock(Number);
1236 
1237  if (!Intf.hasInterference()) {
1238  assert(T < GroupSize && "Array overflow");
1239  TBS[T] = Number;
1240  if (++T == GroupSize) {
1241  SpillPlacer->addLinks(makeArrayRef(TBS, T));
1242  T = 0;
1243  }
1244  continue;
1245  }
1246 
1247  assert(B < GroupSize && "Array overflow");
1248  BCS[B].Number = Number;
1249 
1250  // Interference for the live-in value.
1251  if (Intf.first() <= Indexes->getMBBStartIdx(Number))
1252  BCS[B].Entry = SpillPlacement::MustSpill;
1253  else
1255 
1256  // Interference for the live-out value.
1257  if (Intf.last() >= SA->getLastSplitPoint(Number))
1258  BCS[B].Exit = SpillPlacement::MustSpill;
1259  else
1261 
1262  if (++B == GroupSize) {
1263  SpillPlacer->addConstraints(makeArrayRef(BCS, B));
1264  B = 0;
1265  }
1266  }
1267 
1268  SpillPlacer->addConstraints(makeArrayRef(BCS, B));
1269  SpillPlacer->addLinks(makeArrayRef(TBS, T));
1270 }
1271 
1272 void RAGreedy::growRegion(GlobalSplitCandidate &Cand) {
1273  // Keep track of through blocks that have not been added to SpillPlacer.
1274  BitVector Todo = SA->getThroughBlocks();
1275  SmallVectorImpl<unsigned> &ActiveBlocks = Cand.ActiveBlocks;
1276  unsigned AddedTo = 0;
1277 #ifndef NDEBUG
1278  unsigned Visited = 0;
1279 #endif
1280 
1281  while (true) {
1282  ArrayRef<unsigned> NewBundles = SpillPlacer->getRecentPositive();
1283  // Find new through blocks in the periphery of PrefRegBundles.
1284  for (int i = 0, e = NewBundles.size(); i != e; ++i) {
1285  unsigned Bundle = NewBundles[i];
1286  // Look at all blocks connected to Bundle in the full graph.
1287  ArrayRef<unsigned> Blocks = Bundles->getBlocks(Bundle);
1288  for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end();
1289  I != E; ++I) {
1290  unsigned Block = *I;
1291  if (!Todo.test(Block))
1292  continue;
1293  Todo.reset(Block);
1294  // This is a new through block. Add it to SpillPlacer later.
1295  ActiveBlocks.push_back(Block);
1296 #ifndef NDEBUG
1297  ++Visited;
1298 #endif
1299  }
1300  }
1301  // Any new blocks to add?
1302  if (ActiveBlocks.size() == AddedTo)
1303  break;
1304 
1305  // Compute through constraints from the interference, or assume that all
1306  // through blocks prefer spilling when forming compact regions.
1307  auto NewBlocks = makeArrayRef(ActiveBlocks).slice(AddedTo);
1308  if (Cand.PhysReg)
1309  addThroughConstraints(Cand.Intf, NewBlocks);
1310  else
1311  // Provide a strong negative bias on through blocks to prevent unwanted
1312  // liveness on loop backedges.
1313  SpillPlacer->addPrefSpill(NewBlocks, /* Strong= */ true);
1314  AddedTo = ActiveBlocks.size();
1315 
1316  // Perhaps iterating can enable more bundles?
1317  SpillPlacer->iterate();
1318  }
1319  DEBUG(dbgs() << ", v=" << Visited);
1320 }
1321 
1322 /// calcCompactRegion - Compute the set of edge bundles that should be live
1323 /// when splitting the current live range into compact regions. Compact
1324 /// regions can be computed without looking at interference. They are the
1325 /// regions formed by removing all the live-through blocks from the live range.
1326 ///
1327 /// Returns false if the current live range is already compact, or if the
1328 /// compact regions would form single block regions anyway.
1329 bool RAGreedy::calcCompactRegion(GlobalSplitCandidate &Cand) {
1330  // Without any through blocks, the live range is already compact.
1331  if (!SA->getNumThroughBlocks())
1332  return false;
1333 
1334  // Compact regions don't correspond to any physreg.
1335  Cand.reset(IntfCache, 0);
1336 
1337  DEBUG(dbgs() << "Compact region bundles");
1338 
1339  // Use the spill placer to determine the live bundles. GrowRegion pretends
1340  // that all the through blocks have interference when PhysReg is unset.
1341  SpillPlacer->prepare(Cand.LiveBundles);
1342 
1343  // The static split cost will be zero since Cand.Intf reports no interference.
1344  BlockFrequency Cost;
1345  if (!addSplitConstraints(Cand.Intf, Cost)) {
1346  DEBUG(dbgs() << ", none.\n");
1347  return false;
1348  }
1349 
1350  growRegion(Cand);
1351  SpillPlacer->finish();
1352 
1353  if (!Cand.LiveBundles.any()) {
1354  DEBUG(dbgs() << ", none.\n");
1355  return false;
1356  }
1357 
1358  DEBUG({
1359  for (int i : Cand.LiveBundles.set_bits())
1360  dbgs() << " EB#" << i;
1361  dbgs() << ".\n";
1362  });
1363  return true;
1364 }
1365 
1366 /// calcSpillCost - Compute how expensive it would be to split the live range in
1367 /// SA around all use blocks instead of forming bundle regions.
1368 BlockFrequency RAGreedy::calcSpillCost() {
1369  BlockFrequency Cost = 0;
1370  ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1371  for (unsigned i = 0; i != UseBlocks.size(); ++i) {
1372  const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
1373  unsigned Number = BI.MBB->getNumber();
1374  // We normally only need one spill instruction - a load or a store.
1375  Cost += SpillPlacer->getBlockFrequency(Number);
1376 
1377  // Unless the value is redefined in the block.
1378  if (BI.LiveIn && BI.LiveOut && BI.FirstDef)
1379  Cost += SpillPlacer->getBlockFrequency(Number);
1380  }
1381  return Cost;
1382 }
1383 
1384 /// \brief Check if splitting Evictee will create a local split interval in
1385 /// basic block number BBNumber that may cause a bad eviction chain. This is
1386 /// intended to prevent bad eviction sequences like:
1387 /// movl %ebp, 8(%esp) # 4-byte Spill
1388 /// movl %ecx, %ebp
1389 /// movl %ebx, %ecx
1390 /// movl %edi, %ebx
1391 /// movl %edx, %edi
1392 /// cltd
1393 /// idivl %esi
1394 /// movl %edi, %edx
1395 /// movl %ebx, %edi
1396 /// movl %ecx, %ebx
1397 /// movl %ebp, %ecx
1398 /// movl 16(%esp), %ebp # 4 - byte Reload
1399 ///
1400 /// Such sequences are created in 2 scenarios:
1401 ///
1402 /// Scenario #1:
1403 /// %0 is evicted from physreg0 by %1.
1404 /// Evictee %0 is intended for region splitting with split candidate
1405 /// physreg0 (the reg %0 was evicted from).
1406 /// Region splitting creates a local interval because of interference with the
1407 /// evictor %1 (normally region spliitting creates 2 interval, the "by reg"
1408 /// and "by stack" intervals and local interval created when interference
1409 /// occurs).
1410 /// One of the split intervals ends up evicting %2 from physreg1.
1411 /// Evictee %2 is intended for region splitting with split candidate
1412 /// physreg1.
1413 /// One of the split intervals ends up evicting %3 from physreg2, etc.
1414 ///
1415 /// Scenario #2
1416 /// %0 is evicted from physreg0 by %1.
1417 /// %2 is evicted from physreg2 by %3 etc.
1418 /// Evictee %0 is intended for region splitting with split candidate
1419 /// physreg1.
1420 /// Region splitting creates a local interval because of interference with the
1421 /// evictor %1.
1422 /// One of the split intervals ends up evicting back original evictor %1
1423 /// from physreg0 (the reg %0 was evicted from).
1424 /// Another evictee %2 is intended for region splitting with split candidate
1425 /// physreg1.
1426 /// One of the split intervals ends up evicting %3 from physreg2, etc.
1427 ///
1428 /// \param Evictee The register considered to be split.
1429 /// \param Cand The split candidate that determines the physical register
1430 /// we are splitting for and the interferences.
1431 /// \param BBNumber The number of a BB for which the region split process will
1432 /// create a local split interval.
1433 /// \param Order The physical registers that may get evicted by a split
1434 /// artifact of Evictee.
1435 /// \return True if splitting Evictee may cause a bad eviction chain, false
1436 /// otherwise.
1437 bool RAGreedy::splitCanCauseEvictionChain(unsigned Evictee,
1438  GlobalSplitCandidate &Cand,
1439  unsigned BBNumber,
1440  const AllocationOrder &Order) {
1441  EvictionTrack::EvictorInfo VregEvictorInfo = LastEvicted.getEvictor(Evictee);
1442  unsigned Evictor = VregEvictorInfo.first;
1443  unsigned PhysReg = VregEvictorInfo.second;
1444 
1445  // No actual evictor.
1446  if (!Evictor || !PhysReg)
1447  return false;
1448 
1449  float MaxWeight = 0;
1450  unsigned FutureEvictedPhysReg =
1451  getCheapestEvicteeWeight(Order, LIS->getInterval(Evictee),
1452  Cand.Intf.first(), Cand.Intf.last(), &MaxWeight);
1453 
1454  // The bad eviction chain occurs when either the split candidate is the
1455  // evicting reg or one of the split artifact will evict the evicting reg.
1456  if ((PhysReg != Cand.PhysReg) && (PhysReg != FutureEvictedPhysReg))
1457  return false;
1458 
1459  Cand.Intf.moveToBlock(BBNumber);
1460 
1461  // Check to see if the Evictor contains interference (with Evictee) in the
1462  // given BB. If so, this interference caused the eviction of Evictee from
1463  // PhysReg. This suggest that we will create a local interval during the
1464  // region split to avoid this interference This local interval may cause a bad
1465  // eviction chain.
1466  if (!LIS->hasInterval(Evictor))
1467  return false;
1468  LiveInterval &EvictorLI = LIS->getInterval(Evictor);
1469  if (EvictorLI.FindSegmentContaining(Cand.Intf.first()) == EvictorLI.end())
1470  return false;
1471 
1472  // Now, check to see if the local interval we will create is going to be
1473  // expensive enough to evict somebody If so, this may cause a bad eviction
1474  // chain.
1475  VirtRegAuxInfo VRAI(*MF, *LIS, VRM, getAnalysis<MachineLoopInfo>(), *MBFI);
1476  float splitArtifactWeight =
1477  VRAI.futureWeight(LIS->getInterval(Evictee),
1478  Cand.Intf.first().getPrevIndex(), Cand.Intf.last());
1479  if (splitArtifactWeight >= 0 && splitArtifactWeight < MaxWeight)
1480  return false;
1481 
1482  return true;
1483 }
1484 
1485 /// \brief Check if splitting VirtRegToSplit will create a local split interval
1486 /// in basic block number BBNumber that may cause a spill.
1487 ///
1488 /// \param VirtRegToSplit The register considered to be split.
1489 /// \param Cand The split candidate that determines the physical
1490 /// register we are splitting for and the interferences.
1491 /// \param BBNumber The number of a BB for which the region split process
1492 /// will create a local split interval.
1493 /// \param Order The physical registers that may get evicted by a
1494 /// split artifact of VirtRegToSplit.
1495 /// \return True if splitting VirtRegToSplit may cause a spill, false
1496 /// otherwise.
1497 bool RAGreedy::splitCanCauseLocalSpill(unsigned VirtRegToSplit,
1498  GlobalSplitCandidate &Cand,
1499  unsigned BBNumber,
1500  const AllocationOrder &Order) {
1501  Cand.Intf.moveToBlock(BBNumber);
1502 
1503  // Check if the local interval will find a non interfereing assignment.
1504  for (auto PhysReg : Order.getOrder()) {
1505  if (!Matrix->checkInterference(Cand.Intf.first().getPrevIndex(),
1506  Cand.Intf.last(), PhysReg))
1507  return false;
1508  }
1509 
1510  // Check if the local interval will evict a cheaper interval.
1511  float CheapestEvictWeight = 0;
1512  unsigned FutureEvictedPhysReg = getCheapestEvicteeWeight(
1513  Order, LIS->getInterval(VirtRegToSplit), Cand.Intf.first(),
1514  Cand.Intf.last(), &CheapestEvictWeight);
1515 
1516  // Have we found an interval that can be evicted?
1517  if (FutureEvictedPhysReg) {
1518  VirtRegAuxInfo VRAI(*MF, *LIS, VRM, getAnalysis<MachineLoopInfo>(), *MBFI);
1519  float splitArtifactWeight =
1520  VRAI.futureWeight(LIS->getInterval(VirtRegToSplit),
1521  Cand.Intf.first().getPrevIndex(), Cand.Intf.last());
1522  // Will the weight of the local interval be higher than the cheapest evictee
1523  // weight? If so it will evict it and will not cause a spill.
1524  if (splitArtifactWeight >= 0 && splitArtifactWeight > CheapestEvictWeight)
1525  return false;
1526  }
1527 
1528  // The local interval is not able to find non interferening assignment and not
1529  // able to evict a less worthy interval, therfore, it can cause a spill.
1530  return true;
1531 }
1532 
1533 /// calcGlobalSplitCost - Return the global split cost of following the split
1534 /// pattern in LiveBundles. This cost should be added to the local cost of the
1535 /// interference pattern in SplitConstraints.
1536 ///
1537 BlockFrequency RAGreedy::calcGlobalSplitCost(GlobalSplitCandidate &Cand,
1538  const AllocationOrder &Order,
1539  bool *CanCauseEvictionChain) {
1540  BlockFrequency GlobalCost = 0;
1541  const BitVector &LiveBundles = Cand.LiveBundles;
1542  unsigned VirtRegToSplit = SA->getParent().reg;
1543  ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1544  for (unsigned i = 0; i != UseBlocks.size(); ++i) {
1545  const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
1546  SpillPlacement::BlockConstraint &BC = SplitConstraints[i];
1547  bool RegIn = LiveBundles[Bundles->getBundle(BC.Number, false)];
1548  bool RegOut = LiveBundles[Bundles->getBundle(BC.Number, true)];
1549  unsigned Ins = 0;
1550 
1551  Cand.Intf.moveToBlock(BC.Number);
1552  // Check wheather a local interval is going to be created during the region
1553  // split. Calculate adavanced spilt cost (cost of local intervals) if option
1554  // is enabled.
1555  if (EnableAdvancedRASplitCost && Cand.Intf.hasInterference() && BI.LiveIn &&
1556  BI.LiveOut && RegIn && RegOut) {
1557 
1558  if (CanCauseEvictionChain &&
1559  splitCanCauseEvictionChain(VirtRegToSplit, Cand, BC.Number, Order)) {
1560  // This interference causes our eviction from this assignment, we might
1561  // evict somebody else and eventually someone will spill, add that cost.
1562  // See splitCanCauseEvictionChain for detailed description of scenarios.
1563  GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);
1564  GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);
1565 
1566  *CanCauseEvictionChain = true;
1567 
1568  } else if (splitCanCauseLocalSpill(VirtRegToSplit, Cand, BC.Number,
1569  Order)) {
1570  // This interference causes local interval to spill, add that cost.
1571  GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);
1572  GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);
1573  }
1574  }
1575 
1576  if (BI.LiveIn)
1577  Ins += RegIn != (BC.Entry == SpillPlacement::PrefReg);
1578  if (BI.LiveOut)
1579  Ins += RegOut != (BC.Exit == SpillPlacement::PrefReg);
1580  while (Ins--)
1581  GlobalCost += SpillPlacer->getBlockFrequency(BC.Number);
1582  }
1583 
1584  for (unsigned i = 0, e = Cand.ActiveBlocks.size(); i != e; ++i) {
1585  unsigned Number = Cand.ActiveBlocks[i];
1586  bool RegIn = LiveBundles[Bundles->getBundle(Number, false)];
1587  bool RegOut = LiveBundles[Bundles->getBundle(Number, true)];
1588  if (!RegIn && !RegOut)
1589  continue;
1590  if (RegIn && RegOut) {
1591  // We need double spill code if this block has interference.
1592  Cand.Intf.moveToBlock(Number);
1593  if (Cand.Intf.hasInterference()) {
1594  GlobalCost += SpillPlacer->getBlockFrequency(Number);
1595  GlobalCost += SpillPlacer->getBlockFrequency(Number);
1596 
1597  // Check wheather a local interval is going to be created during the
1598  // region split.
1599  if (EnableAdvancedRASplitCost && CanCauseEvictionChain &&
1600  splitCanCauseEvictionChain(VirtRegToSplit, Cand, Number, Order)) {
1601  // This interference cause our eviction from this assignment, we might
1602  // evict somebody else, add that cost.
1603  // See splitCanCauseEvictionChain for detailed description of
1604  // scenarios.
1605  GlobalCost += SpillPlacer->getBlockFrequency(Number);
1606  GlobalCost += SpillPlacer->getBlockFrequency(Number);
1607 
1608  *CanCauseEvictionChain = true;
1609  }
1610  }
1611  continue;
1612  }
1613  // live-in / stack-out or stack-in live-out.
1614  GlobalCost += SpillPlacer->getBlockFrequency(Number);
1615  }
1616  return GlobalCost;
1617 }
1618 
1619 /// splitAroundRegion - Split the current live range around the regions
1620 /// determined by BundleCand and GlobalCand.
1621 ///
1622 /// Before calling this function, GlobalCand and BundleCand must be initialized
1623 /// so each bundle is assigned to a valid candidate, or NoCand for the
1624 /// stack-bound bundles. The shared SA/SE SplitAnalysis and SplitEditor
1625 /// objects must be initialized for the current live range, and intervals
1626 /// created for the used candidates.
1627 ///
1628 /// @param LREdit The LiveRangeEdit object handling the current split.
1629 /// @param UsedCands List of used GlobalCand entries. Every BundleCand value
1630 /// must appear in this list.
1631 void RAGreedy::splitAroundRegion(LiveRangeEdit &LREdit,
1632  ArrayRef<unsigned> UsedCands) {
1633  // These are the intervals created for new global ranges. We may create more
1634  // intervals for local ranges.
1635  const unsigned NumGlobalIntvs = LREdit.size();
1636  DEBUG(dbgs() << "splitAroundRegion with " << NumGlobalIntvs << " globals.\n");
1637  assert(NumGlobalIntvs && "No global intervals configured");
1638 
1639  // Isolate even single instructions when dealing with a proper sub-class.
1640  // That guarantees register class inflation for the stack interval because it
1641  // is all copies.
1642  unsigned Reg = SA->getParent().reg;
1643  bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg));
1644 
1645  // First handle all the blocks with uses.
1646  ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1647  for (unsigned i = 0; i != UseBlocks.size(); ++i) {
1648  const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
1649  unsigned Number = BI.MBB->getNumber();
1650  unsigned IntvIn = 0, IntvOut = 0;
1651  SlotIndex IntfIn, IntfOut;
1652  if (BI.LiveIn) {
1653  unsigned CandIn = BundleCand[Bundles->getBundle(Number, false)];
1654  if (CandIn != NoCand) {
1655  GlobalSplitCandidate &Cand = GlobalCand[CandIn];
1656  IntvIn = Cand.IntvIdx;
1657  Cand.Intf.moveToBlock(Number);
1658  IntfIn = Cand.Intf.first();
1659  }
1660  }
1661  if (BI.LiveOut) {
1662  unsigned CandOut = BundleCand[Bundles->getBundle(Number, true)];
1663  if (CandOut != NoCand) {
1664  GlobalSplitCandidate &Cand = GlobalCand[CandOut];
1665  IntvOut = Cand.IntvIdx;
1666  Cand.Intf.moveToBlock(Number);
1667  IntfOut = Cand.Intf.last();
1668  }
1669  }
1670 
1671  // Create separate intervals for isolated blocks with multiple uses.
1672  if (!IntvIn && !IntvOut) {
1673  DEBUG(dbgs() << printMBBReference(*BI.MBB) << " isolated.\n");
1674  if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
1675  SE->splitSingleBlock(BI);
1676  continue;
1677  }
1678 
1679  if (IntvIn && IntvOut)
1680  SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut);
1681  else if (IntvIn)
1682  SE->splitRegInBlock(BI, IntvIn, IntfIn);
1683  else
1684  SE->splitRegOutBlock(BI, IntvOut, IntfOut);
1685  }
1686 
1687  // Handle live-through blocks. The relevant live-through blocks are stored in
1688  // the ActiveBlocks list with each candidate. We need to filter out
1689  // duplicates.
1690  BitVector Todo = SA->getThroughBlocks();
1691  for (unsigned c = 0; c != UsedCands.size(); ++c) {
1692  ArrayRef<unsigned> Blocks = GlobalCand[UsedCands[c]].ActiveBlocks;
1693  for (unsigned i = 0, e = Blocks.size(); i != e; ++i) {
1694  unsigned Number = Blocks[i];
1695  if (!Todo.test(Number))
1696  continue;
1697  Todo.reset(Number);
1698 
1699  unsigned IntvIn = 0, IntvOut = 0;
1700  SlotIndex IntfIn, IntfOut;
1701 
1702  unsigned CandIn = BundleCand[Bundles->getBundle(Number, false)];
1703  if (CandIn != NoCand) {
1704  GlobalSplitCandidate &Cand = GlobalCand[CandIn];
1705  IntvIn = Cand.IntvIdx;
1706  Cand.Intf.moveToBlock(Number);
1707  IntfIn = Cand.Intf.first();
1708  }
1709 
1710  unsigned CandOut = BundleCand[Bundles->getBundle(Number, true)];
1711  if (CandOut != NoCand) {
1712  GlobalSplitCandidate &Cand = GlobalCand[CandOut];
1713  IntvOut = Cand.IntvIdx;
1714  Cand.Intf.moveToBlock(Number);
1715  IntfOut = Cand.Intf.last();
1716  }
1717  if (!IntvIn && !IntvOut)
1718  continue;
1719  SE->splitLiveThroughBlock(Number, IntvIn, IntfIn, IntvOut, IntfOut);
1720  }
1721  }
1722 
1723  ++NumGlobalSplits;
1724 
1725  SmallVector<unsigned, 8> IntvMap;
1726  SE->finish(&IntvMap);
1727  DebugVars->splitRegister(Reg, LREdit.regs(), *LIS);
1728 
1729  ExtraRegInfo.resize(MRI->getNumVirtRegs());
1730  unsigned OrigBlocks = SA->getNumLiveBlocks();
1731 
1732  // Sort out the new intervals created by splitting. We get four kinds:
1733  // - Remainder intervals should not be split again.
1734  // - Candidate intervals can be assigned to Cand.PhysReg.
1735  // - Block-local splits are candidates for local splitting.
1736  // - DCE leftovers should go back on the queue.
1737  for (unsigned i = 0, e = LREdit.size(); i != e; ++i) {
1738  LiveInterval &Reg = LIS->getInterval(LREdit.get(i));
1739 
1740  // Ignore old intervals from DCE.
1741  if (getStage(Reg) != RS_New)
1742  continue;
1743 
1744  // Remainder interval. Don't try splitting again, spill if it doesn't
1745  // allocate.
1746  if (IntvMap[i] == 0) {
1747  setStage(Reg, RS_Spill);
1748  continue;
1749  }
1750 
1751  // Global intervals. Allow repeated splitting as long as the number of live
1752  // blocks is strictly decreasing.
1753  if (IntvMap[i] < NumGlobalIntvs) {
1754  if (SA->countLiveBlocks(&Reg) >= OrigBlocks) {
1755  DEBUG(dbgs() << "Main interval covers the same " << OrigBlocks
1756  << " blocks as original.\n");
1757  // Don't allow repeated splitting as a safe guard against looping.
1758  setStage(Reg, RS_Split2);
1759  }
1760  continue;
1761  }
1762 
1763  // Other intervals are treated as new. This includes local intervals created
1764  // for blocks with multiple uses, and anything created by DCE.
1765  }
1766 
1767  if (VerifyEnabled)
1768  MF->verify(this, "After splitting live range around region");
1769 }
1770 
1771 unsigned RAGreedy::tryRegionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
1772  SmallVectorImpl<unsigned> &NewVRegs) {
1773  unsigned NumCands = 0;
1774  BlockFrequency SpillCost = calcSpillCost();
1775  BlockFrequency BestCost;
1776 
1777  // Check if we can split this live range around a compact region.
1778  bool HasCompact = calcCompactRegion(GlobalCand.front());
1779  if (HasCompact) {
1780  // Yes, keep GlobalCand[0] as the compact region candidate.
1781  NumCands = 1;
1782  BestCost = BlockFrequency::getMaxFrequency();
1783  } else {
1784  // No benefit from the compact region, our fallback will be per-block
1785  // splitting. Make sure we find a solution that is cheaper than spilling.
1786  BestCost = SpillCost;
1787  DEBUG(dbgs() << "Cost of isolating all blocks = ";
1788  MBFI->printBlockFreq(dbgs(), BestCost) << '\n');
1789  }
1790 
1791  bool CanCauseEvictionChain = false;
1792  unsigned BestCand =
1793  calculateRegionSplitCost(VirtReg, Order, BestCost, NumCands,
1794  false /*IgnoreCSR*/, &CanCauseEvictionChain);
1795 
1796  // Split candidates with compact regions can cause a bad eviction sequence.
1797  // See splitCanCauseEvictionChain for detailed description of scenarios.
1798  // To avoid it, we need to comapre the cost with the spill cost and not the
1799  // current max frequency.
1800  if (HasCompact && (BestCost > SpillCost) && (BestCand != NoCand) &&
1801  CanCauseEvictionChain) {
1802  return 0;
1803  }
1804 
1805  // No solutions found, fall back to single block splitting.
1806  if (!HasCompact && BestCand == NoCand)
1807  return 0;
1808 
1809  return doRegionSplit(VirtReg, BestCand, HasCompact, NewVRegs);
1810 }
1811 
1812 unsigned RAGreedy::calculateRegionSplitCost(LiveInterval &VirtReg,
1813  AllocationOrder &Order,
1814  BlockFrequency &BestCost,
1815  unsigned &NumCands, bool IgnoreCSR,
1816  bool *CanCauseEvictionChain) {
1817  unsigned BestCand = NoCand;
1818  Order.rewind();
1819  while (unsigned PhysReg = Order.next()) {
1820  if (IgnoreCSR && isUnusedCalleeSavedReg(PhysReg))
1821  continue;
1822 
1823  // Discard bad candidates before we run out of interference cache cursors.
1824  // This will only affect register classes with a lot of registers (>32).
1825  if (NumCands == IntfCache.getMaxCursors()) {
1826  unsigned WorstCount = ~0u;
1827  unsigned Worst = 0;
1828  for (unsigned i = 0; i != NumCands; ++i) {
1829  if (i == BestCand || !GlobalCand[i].PhysReg)
1830  continue;
1831  unsigned Count = GlobalCand[i].LiveBundles.count();
1832  if (Count < WorstCount) {
1833  Worst = i;
1834  WorstCount = Count;
1835  }
1836  }
1837  --NumCands;
1838  GlobalCand[Worst] = GlobalCand[NumCands];
1839  if (BestCand == NumCands)
1840  BestCand = Worst;
1841  }
1842 
1843  if (GlobalCand.size() <= NumCands)
1844  GlobalCand.resize(NumCands+1);
1845  GlobalSplitCandidate &Cand = GlobalCand[NumCands];
1846  Cand.reset(IntfCache, PhysReg);
1847 
1848  SpillPlacer->prepare(Cand.LiveBundles);
1849  BlockFrequency Cost;
1850  if (!addSplitConstraints(Cand.Intf, Cost)) {
1851  DEBUG(dbgs() << printReg(PhysReg, TRI) << "\tno positive bundles\n");
1852  continue;
1853  }
1854  DEBUG(dbgs() << printReg(PhysReg, TRI) << "\tstatic = ";
1855  MBFI->printBlockFreq(dbgs(), Cost));
1856  if (Cost >= BestCost) {
1857  DEBUG({
1858  if (BestCand == NoCand)
1859  dbgs() << " worse than no bundles\n";
1860  else
1861  dbgs() << " worse than "
1862  << printReg(GlobalCand[BestCand].PhysReg, TRI) << '\n';
1863  });
1864  continue;
1865  }
1866  growRegion(Cand);
1867 
1868  SpillPlacer->finish();
1869 
1870  // No live bundles, defer to splitSingleBlocks().
1871  if (!Cand.LiveBundles.any()) {
1872  DEBUG(dbgs() << " no bundles.\n");
1873  continue;
1874  }
1875 
1876  bool HasEvictionChain = false;
1877  Cost += calcGlobalSplitCost(Cand, Order, &HasEvictionChain);
1878  DEBUG({
1879  dbgs() << ", total = "; MBFI->printBlockFreq(dbgs(), Cost)
1880  << " with bundles";
1881  for (int i : Cand.LiveBundles.set_bits())
1882  dbgs() << " EB#" << i;
1883  dbgs() << ".\n";
1884  });
1885  if (Cost < BestCost) {
1886  BestCand = NumCands;
1887  BestCost = Cost;
1888  // See splitCanCauseEvictionChain for detailed description of bad
1889  // eviction chain scenarios.
1890  if (CanCauseEvictionChain)
1891  *CanCauseEvictionChain = HasEvictionChain;
1892  }
1893  ++NumCands;
1894  }
1895 
1896  if (CanCauseEvictionChain && BestCand != NoCand) {
1897  // See splitCanCauseEvictionChain for detailed description of bad
1898  // eviction chain scenarios.
1899  DEBUG(dbgs() << "Best split candidate of vreg "
1900  << printReg(VirtReg.reg, TRI) << " may ");
1901  if (!(*CanCauseEvictionChain))
1902  DEBUG(dbgs() << "not ");
1903  DEBUG(dbgs() << "cause bad eviction chain\n");
1904  }
1905 
1906  return BestCand;
1907 }
1908 
1909 unsigned RAGreedy::doRegionSplit(LiveInterval &VirtReg, unsigned BestCand,
1910  bool HasCompact,
1911  SmallVectorImpl<unsigned> &NewVRegs) {
1912  SmallVector<unsigned, 8> UsedCands;
1913  // Prepare split editor.
1914  LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
1915  SE->reset(LREdit, SplitSpillMode);
1916 
1917  // Assign all edge bundles to the preferred candidate, or NoCand.
1918  BundleCand.assign(Bundles->getNumBundles(), NoCand);
1919 
1920  // Assign bundles for the best candidate region.
1921  if (BestCand != NoCand) {
1922  GlobalSplitCandidate &Cand = GlobalCand[BestCand];
1923  if (unsigned B = Cand.getBundles(BundleCand, BestCand)) {
1924  UsedCands.push_back(BestCand);
1925  Cand.IntvIdx = SE->openIntv();
1926  DEBUG(dbgs() << "Split for " << printReg(Cand.PhysReg, TRI) << " in "
1927  << B << " bundles, intv " << Cand.IntvIdx << ".\n");
1928  (void)B;
1929  }
1930  }
1931 
1932  // Assign bundles for the compact region.
1933  if (HasCompact) {
1934  GlobalSplitCandidate &Cand = GlobalCand.front();
1935  assert(!Cand.PhysReg && "Compact region has no physreg");
1936  if (unsigned B = Cand.getBundles(BundleCand, 0)) {
1937  UsedCands.push_back(0);
1938  Cand.IntvIdx = SE->openIntv();
1939  DEBUG(dbgs() << "Split for compact region in " << B << " bundles, intv "
1940  << Cand.IntvIdx << ".\n");
1941  (void)B;
1942  }
1943  }
1944 
1945  splitAroundRegion(LREdit, UsedCands);
1946  return 0;
1947 }
1948 
1949 //===----------------------------------------------------------------------===//
1950 // Per-Block Splitting
1951 //===----------------------------------------------------------------------===//
1952 
1953 /// tryBlockSplit - Split a global live range around every block with uses. This
1954 /// creates a lot of local live ranges, that will be split by tryLocalSplit if
1955 /// they don't allocate.
1956 unsigned RAGreedy::tryBlockSplit(LiveInterval &VirtReg, AllocationOrder &Order,
1957  SmallVectorImpl<unsigned> &NewVRegs) {
1958  assert(&SA->getParent() == &VirtReg && "Live range wasn't analyzed");
1959  unsigned Reg = VirtReg.reg;
1960  bool SingleInstrs = RegClassInfo.isProperSubClass(MRI->getRegClass(Reg));
1961  LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
1962  SE->reset(LREdit, SplitSpillMode);
1963  ArrayRef<SplitAnalysis::BlockInfo> UseBlocks = SA->getUseBlocks();
1964  for (unsigned i = 0; i != UseBlocks.size(); ++i) {
1965  const SplitAnalysis::BlockInfo &BI = UseBlocks[i];
1966  if (SA->shouldSplitSingleBlock(BI, SingleInstrs))
1967  SE->splitSingleBlock(BI);
1968  }
1969  // No blocks were split.
1970  if (LREdit.empty())
1971  return 0;
1972 
1973  // We did split for some blocks.
1974  SmallVector<unsigned, 8> IntvMap;
1975  SE->finish(&IntvMap);
1976 
1977  // Tell LiveDebugVariables about the new ranges.
1978  DebugVars->splitRegister(Reg, LREdit.regs(), *LIS);
1979 
1980  ExtraRegInfo.resize(MRI->getNumVirtRegs());
1981 
1982  // Sort out the new intervals created by splitting. The remainder interval
1983  // goes straight to spilling, the new local ranges get to stay RS_New.
1984  for (unsigned i = 0, e = LREdit.size(); i != e; ++i) {
1985  LiveInterval &LI = LIS->getInterval(LREdit.get(i));
1986  if (getStage(LI) == RS_New && IntvMap[i] == 0)
1987  setStage(LI, RS_Spill);
1988  }
1989 
1990  if (VerifyEnabled)
1991  MF->verify(this, "After splitting live range around basic blocks");
1992  return 0;
1993 }
1994 
1995 //===----------------------------------------------------------------------===//
1996 // Per-Instruction Splitting
1997 //===----------------------------------------------------------------------===//
1998 
1999 /// Get the number of allocatable registers that match the constraints of \p Reg
2000 /// on \p MI and that are also in \p SuperRC.
2002  const MachineInstr *MI, unsigned Reg, const TargetRegisterClass *SuperRC,
2003  const TargetInstrInfo *TII, const TargetRegisterInfo *TRI,
2004  const RegisterClassInfo &RCI) {
2005  assert(SuperRC && "Invalid register class");
2006 
2007  const TargetRegisterClass *ConstrainedRC =
2008  MI->getRegClassConstraintEffectForVReg(Reg, SuperRC, TII, TRI,
2009  /* ExploreBundle */ true);
2010  if (!ConstrainedRC)
2011  return 0;
2012  return RCI.getNumAllocatableRegs(ConstrainedRC);
2013 }
2014 
2015 /// tryInstructionSplit - Split a live range around individual instructions.
2016 /// This is normally not worthwhile since the spiller is doing essentially the
2017 /// same thing. However, when the live range is in a constrained register
2018 /// class, it may help to insert copies such that parts of the live range can
2019 /// be moved to a larger register class.
2020 ///
2021 /// This is similar to spilling to a larger register class.
2022 unsigned
2023 RAGreedy::tryInstructionSplit(LiveInterval &VirtReg, AllocationOrder &Order,
2024  SmallVectorImpl<unsigned> &NewVRegs) {
2025  const TargetRegisterClass *CurRC = MRI->getRegClass(VirtReg.reg);
2026  // There is no point to this if there are no larger sub-classes.
2027  if (!RegClassInfo.isProperSubClass(CurRC))
2028  return 0;
2029 
2030  // Always enable split spill mode, since we're effectively spilling to a
2031  // register.
2032  LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
2033  SE->reset(LREdit, SplitEditor::SM_Size);
2034 
2035  ArrayRef<SlotIndex> Uses = SA->getUseSlots();
2036  if (Uses.size() <= 1)
2037  return 0;
2038 
2039  DEBUG(dbgs() << "Split around " << Uses.size() << " individual instrs.\n");
2040 
2041  const TargetRegisterClass *SuperRC =
2042  TRI->getLargestLegalSuperClass(CurRC, *MF);
2043  unsigned SuperRCNumAllocatableRegs = RCI.getNumAllocatableRegs(SuperRC);
2044  // Split around every non-copy instruction if this split will relax
2045  // the constraints on the virtual register.
2046  // Otherwise, splitting just inserts uncoalescable copies that do not help
2047  // the allocation.
2048  for (unsigned i = 0; i != Uses.size(); ++i) {
2049  if (const MachineInstr *MI = Indexes->getInstructionFromIndex(Uses[i]))
2050  if (MI->isFullCopy() ||
2051  SuperRCNumAllocatableRegs ==
2052  getNumAllocatableRegsForConstraints(MI, VirtReg.reg, SuperRC, TII,
2053  TRI, RCI)) {
2054  DEBUG(dbgs() << " skip:\t" << Uses[i] << '\t' << *MI);
2055  continue;
2056  }
2057  SE->openIntv();
2058  SlotIndex SegStart = SE->enterIntvBefore(Uses[i]);
2059  SlotIndex SegStop = SE->leaveIntvAfter(Uses[i]);
2060  SE->useIntv(SegStart, SegStop);
2061  }
2062 
2063  if (LREdit.empty()) {
2064  DEBUG(dbgs() << "All uses were copies.\n");
2065  return 0;
2066  }
2067 
2068  SmallVector<unsigned, 8> IntvMap;
2069  SE->finish(&IntvMap);
2070  DebugVars->splitRegister(VirtReg.reg, LREdit.regs(), *LIS);
2071  ExtraRegInfo.resize(MRI->getNumVirtRegs());
2072 
2073  // Assign all new registers to RS_Spill. This was the last chance.
2074  setStage(LREdit.begin(), LREdit.end(), RS_Spill);
2075  return 0;
2076 }
2077 
2078 //===----------------------------------------------------------------------===//
2079 // Local Splitting
2080 //===----------------------------------------------------------------------===//
2081 
2082 /// calcGapWeights - Compute the maximum spill weight that needs to be evicted
2083 /// in order to use PhysReg between two entries in SA->UseSlots.
2084 ///
2085 /// GapWeight[i] represents the gap between UseSlots[i] and UseSlots[i+1].
2086 ///
2087 void RAGreedy::calcGapWeights(unsigned PhysReg,
2088  SmallVectorImpl<float> &GapWeight) {
2089  assert(SA->getUseBlocks().size() == 1 && "Not a local interval");
2090  const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front();
2091  ArrayRef<SlotIndex> Uses = SA->getUseSlots();
2092  const unsigned NumGaps = Uses.size()-1;
2093 
2094  // Start and end points for the interference check.
2095  SlotIndex StartIdx =
2096  BI.LiveIn ? BI.FirstInstr.getBaseIndex() : BI.FirstInstr;
2097  SlotIndex StopIdx =
2098  BI.LiveOut ? BI.LastInstr.getBoundaryIndex() : BI.LastInstr;
2099 
2100  GapWeight.assign(NumGaps, 0.0f);
2101 
2102  // Add interference from each overlapping register.
2103  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
2104  if (!Matrix->query(const_cast<LiveInterval&>(SA->getParent()), *Units)
2105  .checkInterference())
2106  continue;
2107 
2108  // We know that VirtReg is a continuous interval from FirstInstr to
2109  // LastInstr, so we don't need InterferenceQuery.
2110  //
2111  // Interference that overlaps an instruction is counted in both gaps
2112  // surrounding the instruction. The exception is interference before
2113  // StartIdx and after StopIdx.
2114  //
2116  Matrix->getLiveUnions()[*Units] .find(StartIdx);
2117  for (unsigned Gap = 0; IntI.valid() && IntI.start() < StopIdx; ++IntI) {
2118  // Skip the gaps before IntI.
2119  while (Uses[Gap+1].getBoundaryIndex() < IntI.start())
2120  if (++Gap == NumGaps)
2121  break;
2122  if (Gap == NumGaps)
2123  break;
2124 
2125  // Update the gaps covered by IntI.
2126  const float weight = IntI.value()->weight;
2127  for (; Gap != NumGaps; ++Gap) {
2128  GapWeight[Gap] = std::max(GapWeight[Gap], weight);
2129  if (Uses[Gap+1].getBaseIndex() >= IntI.stop())
2130  break;
2131  }
2132  if (Gap == NumGaps)
2133  break;
2134  }
2135  }
2136 
2137  // Add fixed interference.
2138  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
2139  const LiveRange &LR = LIS->getRegUnit(*Units);
2140  LiveRange::const_iterator I = LR.find(StartIdx);
2142 
2143  // Same loop as above. Mark any overlapped gaps as HUGE_VALF.
2144  for (unsigned Gap = 0; I != E && I->start < StopIdx; ++I) {
2145  while (Uses[Gap+1].getBoundaryIndex() < I->start)
2146  if (++Gap == NumGaps)
2147  break;
2148  if (Gap == NumGaps)
2149  break;
2150 
2151  for (; Gap != NumGaps; ++Gap) {
2152  GapWeight[Gap] = huge_valf;
2153  if (Uses[Gap+1].getBaseIndex() >= I->end)
2154  break;
2155  }
2156  if (Gap == NumGaps)
2157  break;
2158  }
2159  }
2160 }
2161 
2162 /// tryLocalSplit - Try to split VirtReg into smaller intervals inside its only
2163 /// basic block.
2164 ///
2165 unsigned RAGreedy::tryLocalSplit(LiveInterval &VirtReg, AllocationOrder &Order,
2166  SmallVectorImpl<unsigned> &NewVRegs) {
2167  assert(SA->getUseBlocks().size() == 1 && "Not a local interval");
2168  const SplitAnalysis::BlockInfo &BI = SA->getUseBlocks().front();
2169 
2170  // Note that it is possible to have an interval that is live-in or live-out
2171  // while only covering a single block - A phi-def can use undef values from
2172  // predecessors, and the block could be a single-block loop.
2173  // We don't bother doing anything clever about such a case, we simply assume
2174  // that the interval is continuous from FirstInstr to LastInstr. We should
2175  // make sure that we don't do anything illegal to such an interval, though.
2176 
2177  ArrayRef<SlotIndex> Uses = SA->getUseSlots();
2178  if (Uses.size() <= 2)
2179  return 0;
2180  const unsigned NumGaps = Uses.size()-1;
2181 
2182  DEBUG({
2183  dbgs() << "tryLocalSplit: ";
2184  for (unsigned i = 0, e = Uses.size(); i != e; ++i)
2185  dbgs() << ' ' << Uses[i];
2186  dbgs() << '\n';
2187  });
2188 
2189  // If VirtReg is live across any register mask operands, compute a list of
2190  // gaps with register masks.
2191  SmallVector<unsigned, 8> RegMaskGaps;
2192  if (Matrix->checkRegMaskInterference(VirtReg)) {
2193  // Get regmask slots for the whole block.
2194  ArrayRef<SlotIndex> RMS = LIS->getRegMaskSlotsInBlock(BI.MBB->getNumber());
2195  DEBUG(dbgs() << RMS.size() << " regmasks in block:");
2196  // Constrain to VirtReg's live range.
2197  unsigned ri = std::lower_bound(RMS.begin(), RMS.end(),
2198  Uses.front().getRegSlot()) - RMS.begin();
2199  unsigned re = RMS.size();
2200  for (unsigned i = 0; i != NumGaps && ri != re; ++i) {
2201  // Look for Uses[i] <= RMS <= Uses[i+1].
2202  assert(!SlotIndex::isEarlierInstr(RMS[ri], Uses[i]));
2203  if (SlotIndex::isEarlierInstr(Uses[i+1], RMS[ri]))
2204  continue;
2205  // Skip a regmask on the same instruction as the last use. It doesn't
2206  // overlap the live range.
2207  if (SlotIndex::isSameInstr(Uses[i+1], RMS[ri]) && i+1 == NumGaps)
2208  break;
2209  DEBUG(dbgs() << ' ' << RMS[ri] << ':' << Uses[i] << '-' << Uses[i+1]);
2210  RegMaskGaps.push_back(i);
2211  // Advance ri to the next gap. A regmask on one of the uses counts in
2212  // both gaps.
2213  while (ri != re && SlotIndex::isEarlierInstr(RMS[ri], Uses[i+1]))
2214  ++ri;
2215  }
2216  DEBUG(dbgs() << '\n');
2217  }
2218 
2219  // Since we allow local split results to be split again, there is a risk of
2220  // creating infinite loops. It is tempting to require that the new live
2221  // ranges have less instructions than the original. That would guarantee
2222  // convergence, but it is too strict. A live range with 3 instructions can be
2223  // split 2+3 (including the COPY), and we want to allow that.
2224  //
2225  // Instead we use these rules:
2226  //
2227  // 1. Allow any split for ranges with getStage() < RS_Split2. (Except for the
2228  // noop split, of course).
2229  // 2. Require progress be made for ranges with getStage() == RS_Split2. All
2230  // the new ranges must have fewer instructions than before the split.
2231  // 3. New ranges with the same number of instructions are marked RS_Split2,
2232  // smaller ranges are marked RS_New.
2233  //
2234  // These rules allow a 3 -> 2+3 split once, which we need. They also prevent
2235  // excessive splitting and infinite loops.
2236  //
2237  bool ProgressRequired = getStage(VirtReg) >= RS_Split2;
2238 
2239  // Best split candidate.
2240  unsigned BestBefore = NumGaps;
2241  unsigned BestAfter = 0;
2242  float BestDiff = 0;
2243 
2244  const float blockFreq =
2245  SpillPlacer->getBlockFrequency(BI.MBB->getNumber()).getFrequency() *
2246  (1.0f / MBFI->getEntryFreq());
2247  SmallVector<float, 8> GapWeight;
2248 
2249  Order.rewind();
2250  while (unsigned PhysReg = Order.next()) {
2251  // Keep track of the largest spill weight that would need to be evicted in
2252  // order to make use of PhysReg between UseSlots[i] and UseSlots[i+1].
2253  calcGapWeights(PhysReg, GapWeight);
2254 
2255  // Remove any gaps with regmask clobbers.
2256  if (Matrix->checkRegMaskInterference(VirtReg, PhysReg))
2257  for (unsigned i = 0, e = RegMaskGaps.size(); i != e; ++i)
2258  GapWeight[RegMaskGaps[i]] = huge_valf;
2259 
2260  // Try to find the best sequence of gaps to close.
2261  // The new spill weight must be larger than any gap interference.
2262 
2263  // We will split before Uses[SplitBefore] and after Uses[SplitAfter].
2264  unsigned SplitBefore = 0, SplitAfter = 1;
2265 
2266  // MaxGap should always be max(GapWeight[SplitBefore..SplitAfter-1]).
2267  // It is the spill weight that needs to be evicted.
2268  float MaxGap = GapWeight[0];
2269 
2270  while (true) {
2271  // Live before/after split?
2272  const bool LiveBefore = SplitBefore != 0 || BI.LiveIn;
2273  const bool LiveAfter = SplitAfter != NumGaps || BI.LiveOut;
2274 
2275  DEBUG(dbgs() << printReg(PhysReg, TRI) << ' '
2276  << Uses[SplitBefore] << '-' << Uses[SplitAfter]
2277  << " i=" << MaxGap);
2278 
2279  // Stop before the interval gets so big we wouldn't be making progress.
2280  if (!LiveBefore && !LiveAfter) {
2281  DEBUG(dbgs() << " all\n");
2282  break;
2283  }
2284  // Should the interval be extended or shrunk?
2285  bool Shrink = true;
2286 
2287  // How many gaps would the new range have?
2288  unsigned NewGaps = LiveBefore + SplitAfter - SplitBefore + LiveAfter;
2289 
2290  // Legally, without causing looping?
2291  bool Legal = !ProgressRequired || NewGaps < NumGaps;
2292 
2293  if (Legal && MaxGap < huge_valf) {
2294  // Estimate the new spill weight. Each instruction reads or writes the
2295  // register. Conservatively assume there are no read-modify-write
2296  // instructions.
2297  //
2298  // Try to guess the size of the new interval.
2299  const float EstWeight = normalizeSpillWeight(
2300  blockFreq * (NewGaps + 1),
2301  Uses[SplitBefore].distance(Uses[SplitAfter]) +
2302  (LiveBefore + LiveAfter) * SlotIndex::InstrDist,
2303  1);
2304  // Would this split be possible to allocate?
2305  // Never allocate all gaps, we wouldn't be making progress.
2306  DEBUG(dbgs() << " w=" << EstWeight);
2307  if (EstWeight * Hysteresis >= MaxGap) {
2308  Shrink = false;
2309  float Diff = EstWeight - MaxGap;
2310  if (Diff > BestDiff) {
2311  DEBUG(dbgs() << " (best)");
2312  BestDiff = Hysteresis * Diff;
2313  BestBefore = SplitBefore;
2314  BestAfter = SplitAfter;
2315  }
2316  }
2317  }
2318 
2319  // Try to shrink.
2320  if (Shrink) {
2321  if (++SplitBefore < SplitAfter) {
2322  DEBUG(dbgs() << " shrink\n");
2323  // Recompute the max when necessary.
2324  if (GapWeight[SplitBefore - 1] >= MaxGap) {
2325  MaxGap = GapWeight[SplitBefore];
2326  for (unsigned i = SplitBefore + 1; i != SplitAfter; ++i)
2327  MaxGap = std::max(MaxGap, GapWeight[i]);
2328  }
2329  continue;
2330  }
2331  MaxGap = 0;
2332  }
2333 
2334  // Try to extend the interval.
2335  if (SplitAfter >= NumGaps) {
2336  DEBUG(dbgs() << " end\n");
2337  break;
2338  }
2339 
2340  DEBUG(dbgs() << " extend\n");
2341  MaxGap = std::max(MaxGap, GapWeight[SplitAfter++]);
2342  }
2343  }
2344 
2345  // Didn't find any candidates?
2346  if (BestBefore == NumGaps)
2347  return 0;
2348 
2349  DEBUG(dbgs() << "Best local split range: " << Uses[BestBefore]
2350  << '-' << Uses[BestAfter] << ", " << BestDiff
2351  << ", " << (BestAfter - BestBefore + 1) << " instrs\n");
2352 
2353  LiveRangeEdit LREdit(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
2354  SE->reset(LREdit);
2355 
2356  SE->openIntv();
2357  SlotIndex SegStart = SE->enterIntvBefore(Uses[BestBefore]);
2358  SlotIndex SegStop = SE->leaveIntvAfter(Uses[BestAfter]);
2359  SE->useIntv(SegStart, SegStop);
2360  SmallVector<unsigned, 8> IntvMap;
2361  SE->finish(&IntvMap);
2362  DebugVars->splitRegister(VirtReg.reg, LREdit.regs(), *LIS);
2363 
2364  // If the new range has the same number of instructions as before, mark it as
2365  // RS_Split2 so the next split will be forced to make progress. Otherwise,
2366  // leave the new intervals as RS_New so they can compete.
2367  bool LiveBefore = BestBefore != 0 || BI.LiveIn;
2368  bool LiveAfter = BestAfter != NumGaps || BI.LiveOut;
2369  unsigned NewGaps = LiveBefore + BestAfter - BestBefore + LiveAfter;
2370  if (NewGaps >= NumGaps) {
2371  DEBUG(dbgs() << "Tagging non-progress ranges: ");
2372  assert(!ProgressRequired && "Didn't make progress when it was required.");
2373  for (unsigned i = 0, e = IntvMap.size(); i != e; ++i)
2374  if (IntvMap[i] == 1) {
2375  setStage(LIS->getInterval(LREdit.get(i)), RS_Split2);
2376  DEBUG(dbgs() << printReg(LREdit.get(i)));
2377  }
2378  DEBUG(dbgs() << '\n');
2379  }
2380  ++NumLocalSplits;
2381 
2382  return 0;
2383 }
2384 
2385 //===----------------------------------------------------------------------===//
2386 // Live Range Splitting
2387 //===----------------------------------------------------------------------===//
2388 
2389 /// trySplit - Try to split VirtReg or one of its interferences, making it
2390 /// assignable.
2391 /// @return Physreg when VirtReg may be assigned and/or new NewVRegs.
2392 unsigned RAGreedy::trySplit(LiveInterval &VirtReg, AllocationOrder &Order,
2393  SmallVectorImpl<unsigned>&NewVRegs) {
2394  // Ranges must be Split2 or less.
2395  if (getStage(VirtReg) >= RS_Spill)
2396  return 0;
2397 
2398  // Local intervals are handled separately.
2399  if (LIS->intervalIsInOneMBB(VirtReg)) {
2400  NamedRegionTimer T("local_split", "Local Splitting", TimerGroupName,
2401  TimerGroupDescription, TimePassesIsEnabled);
2402  SA->analyze(&VirtReg);
2403  unsigned PhysReg = tryLocalSplit(VirtReg, Order, NewVRegs);
2404  if (PhysReg || !NewVRegs.empty())
2405  return PhysReg;
2406  return tryInstructionSplit(VirtReg, Order, NewVRegs);
2407  }
2408 
2409  NamedRegionTimer T("global_split", "Global Splitting", TimerGroupName,
2410  TimerGroupDescription, TimePassesIsEnabled);
2411 
2412  SA->analyze(&VirtReg);
2413 
2414  // FIXME: SplitAnalysis may repair broken live ranges coming from the
2415  // coalescer. That may cause the range to become allocatable which means that
2416  // tryRegionSplit won't be making progress. This check should be replaced with
2417  // an assertion when the coalescer is fixed.
2418  if (SA->didRepairRange()) {
2419  // VirtReg has changed, so all cached queries are invalid.
2420  Matrix->invalidateVirtRegs();
2421  if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs))
2422  return PhysReg;
2423  }
2424 
2425  // First try to split around a region spanning multiple blocks. RS_Split2
2426  // ranges already made dubious progress with region splitting, so they go
2427  // straight to single block splitting.
2428  if (getStage(VirtReg) < RS_Split2) {
2429  unsigned PhysReg = tryRegionSplit(VirtReg, Order, NewVRegs);
2430  if (PhysReg || !NewVRegs.empty())
2431  return PhysReg;
2432  }
2433 
2434  // Then isolate blocks.
2435  return tryBlockSplit(VirtReg, Order, NewVRegs);
2436 }
2437 
2438 //===----------------------------------------------------------------------===//
2439 // Last Chance Recoloring
2440 //===----------------------------------------------------------------------===//
2441 
2442 /// Return true if \p reg has any tied def operand.
2443 static bool hasTiedDef(MachineRegisterInfo *MRI, unsigned reg) {
2444  for (const MachineOperand &MO : MRI->def_operands(reg))
2445  if (MO.isTied())
2446  return true;
2447 
2448  return false;
2449 }
2450 
2451 /// mayRecolorAllInterferences - Check if the virtual registers that
2452 /// interfere with \p VirtReg on \p PhysReg (or one of its aliases) may be
2453 /// recolored to free \p PhysReg.
2454 /// When true is returned, \p RecoloringCandidates has been augmented with all
2455 /// the live intervals that need to be recolored in order to free \p PhysReg
2456 /// for \p VirtReg.
2457 /// \p FixedRegisters contains all the virtual registers that cannot be
2458 /// recolored.
2459 bool
2460 RAGreedy::mayRecolorAllInterferences(unsigned PhysReg, LiveInterval &VirtReg,
2461  SmallLISet &RecoloringCandidates,
2462  const SmallVirtRegSet &FixedRegisters) {
2463  const TargetRegisterClass *CurRC = MRI->getRegClass(VirtReg.reg);
2464 
2465  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
2466  LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
2467  // If there is LastChanceRecoloringMaxInterference or more interferences,
2468  // chances are one would not be recolorable.
2471  DEBUG(dbgs() << "Early abort: too many interferences.\n");
2472  CutOffInfo |= CO_Interf;
2473  return false;
2474  }
2475  for (unsigned i = Q.interferingVRegs().size(); i; --i) {
2476  LiveInterval *Intf = Q.interferingVRegs()[i - 1];
2477  // If Intf is done and sit on the same register class as VirtReg,
2478  // it would not be recolorable as it is in the same state as VirtReg.
2479  // However, if VirtReg has tied defs and Intf doesn't, then
2480  // there is still a point in examining if it can be recolorable.
2481  if (((getStage(*Intf) == RS_Done &&
2482  MRI->getRegClass(Intf->reg) == CurRC) &&
2483  !(hasTiedDef(MRI, VirtReg.reg) && !hasTiedDef(MRI, Intf->reg))) ||
2484  FixedRegisters.count(Intf->reg)) {
2485  DEBUG(dbgs() << "Early abort: the interference is not recolorable.\n");
2486  return false;
2487  }
2488  RecoloringCandidates.insert(Intf);
2489  }
2490  }
2491  return true;
2492 }
2493 
2494 /// tryLastChanceRecoloring - Try to assign a color to \p VirtReg by recoloring
2495 /// its interferences.
2496 /// Last chance recoloring chooses a color for \p VirtReg and recolors every
2497 /// virtual register that was using it. The recoloring process may recursively
2498 /// use the last chance recoloring. Therefore, when a virtual register has been
2499 /// assigned a color by this mechanism, it is marked as Fixed, i.e., it cannot
2500 /// be last-chance-recolored again during this recoloring "session".
2501 /// E.g.,
2502 /// Let
2503 /// vA can use {R1, R2 }
2504 /// vB can use { R2, R3}
2505 /// vC can use {R1 }
2506 /// Where vA, vB, and vC cannot be split anymore (they are reloads for
2507 /// instance) and they all interfere.
2508 ///
2509 /// vA is assigned R1
2510 /// vB is assigned R2
2511 /// vC tries to evict vA but vA is already done.
2512 /// Regular register allocation fails.
2513 ///
2514 /// Last chance recoloring kicks in:
2515 /// vC does as if vA was evicted => vC uses R1.
2516 /// vC is marked as fixed.
2517 /// vA needs to find a color.
2518 /// None are available.
2519 /// vA cannot evict vC: vC is a fixed virtual register now.
2520 /// vA does as if vB was evicted => vA uses R2.
2521 /// vB needs to find a color.
2522 /// R3 is available.
2523 /// Recoloring => vC = R1, vA = R2, vB = R3
2524 ///
2525 /// \p Order defines the preferred allocation order for \p VirtReg.
2526 /// \p NewRegs will contain any new virtual register that have been created
2527 /// (split, spill) during the process and that must be assigned.
2528 /// \p FixedRegisters contains all the virtual registers that cannot be
2529 /// recolored.
2530 /// \p Depth gives the current depth of the last chance recoloring.
2531 /// \return a physical register that can be used for VirtReg or ~0u if none
2532 /// exists.
2533 unsigned RAGreedy::tryLastChanceRecoloring(LiveInterval &VirtReg,
2534  AllocationOrder &Order,
2535  SmallVectorImpl<unsigned> &NewVRegs,
2536  SmallVirtRegSet &FixedRegisters,
2537  unsigned Depth) {
2538  DEBUG(dbgs() << "Try last chance recoloring for " << VirtReg << '\n');
2539  // Ranges must be Done.
2540  assert((getStage(VirtReg) >= RS_Done || !VirtReg.isSpillable()) &&
2541  "Last chance recoloring should really be last chance");
2542  // Set the max depth to LastChanceRecoloringMaxDepth.
2543  // We may want to reconsider that if we end up with a too large search space
2544  // for target with hundreds of registers.
2545  // Indeed, in that case we may want to cut the search space earlier.
2547  DEBUG(dbgs() << "Abort because max depth has been reached.\n");
2548  CutOffInfo |= CO_Depth;
2549  return ~0u;
2550  }
2551 
2552  // Set of Live intervals that will need to be recolored.
2553  SmallLISet RecoloringCandidates;
2554  // Record the original mapping virtual register to physical register in case
2555  // the recoloring fails.
2556  DenseMap<unsigned, unsigned> VirtRegToPhysReg;
2557  // Mark VirtReg as fixed, i.e., it will not be recolored pass this point in
2558  // this recoloring "session".
2559  FixedRegisters.insert(VirtReg.reg);
2560  SmallVector<unsigned, 4> CurrentNewVRegs;
2561 
2562  Order.rewind();
2563  while (unsigned PhysReg = Order.next()) {
2564  DEBUG(dbgs() << "Try to assign: " << VirtReg << " to "
2565  << printReg(PhysReg, TRI) << '\n');
2566  RecoloringCandidates.clear();
2567  VirtRegToPhysReg.clear();
2568  CurrentNewVRegs.clear();
2569 
2570  // It is only possible to recolor virtual register interference.
2571  if (Matrix->checkInterference(VirtReg, PhysReg) >
2573  DEBUG(dbgs() << "Some interferences are not with virtual registers.\n");
2574 
2575  continue;
2576  }
2577 
2578  // Early give up on this PhysReg if it is obvious we cannot recolor all
2579  // the interferences.
2580  if (!mayRecolorAllInterferences(PhysReg, VirtReg, RecoloringCandidates,
2581  FixedRegisters)) {
2582  DEBUG(dbgs() << "Some interferences cannot be recolored.\n");
2583  continue;
2584  }
2585 
2586  // RecoloringCandidates contains all the virtual registers that interfer
2587  // with VirtReg on PhysReg (or one of its aliases).
2588  // Enqueue them for recoloring and perform the actual recoloring.
2589  PQueue RecoloringQueue;
2590  for (SmallLISet::iterator It = RecoloringCandidates.begin(),
2591  EndIt = RecoloringCandidates.end();
2592  It != EndIt; ++It) {
2593  unsigned ItVirtReg = (*It)->reg;
2594  enqueue(RecoloringQueue, *It);
2595  assert(VRM->hasPhys(ItVirtReg) &&
2596  "Interferences are supposed to be with allocated vairables");
2597 
2598  // Record the current allocation.
2599  VirtRegToPhysReg[ItVirtReg] = VRM->getPhys(ItVirtReg);
2600  // unset the related struct.
2601  Matrix->unassign(**It);
2602  }
2603 
2604  // Do as if VirtReg was assigned to PhysReg so that the underlying
2605  // recoloring has the right information about the interferes and
2606  // available colors.
2607  Matrix->assign(VirtReg, PhysReg);
2608 
2609  // Save the current recoloring state.
2610  // If we cannot recolor all the interferences, we will have to start again
2611  // at this point for the next physical register.
2612  SmallVirtRegSet SaveFixedRegisters(FixedRegisters);
2613  if (tryRecoloringCandidates(RecoloringQueue, CurrentNewVRegs,
2614  FixedRegisters, Depth)) {
2615  // Push the queued vregs into the main queue.
2616  for (unsigned NewVReg : CurrentNewVRegs)
2617  NewVRegs.push_back(NewVReg);
2618  // Do not mess up with the global assignment process.
2619  // I.e., VirtReg must be unassigned.
2620  Matrix->unassign(VirtReg);
2621  return PhysReg;
2622  }
2623 
2624  DEBUG(dbgs() << "Fail to assign: " << VirtReg << " to "
2625  << printReg(PhysReg, TRI) << '\n');
2626 
2627  // The recoloring attempt failed, undo the changes.
2628  FixedRegisters = SaveFixedRegisters;
2629  Matrix->unassign(VirtReg);
2630 
2631  // For a newly created vreg which is also in RecoloringCandidates,
2632  // don't add it to NewVRegs because its physical register will be restored
2633  // below. Other vregs in CurrentNewVRegs are created by calling
2634  // selectOrSplit and should be added into NewVRegs.
2635  for (SmallVectorImpl<unsigned>::iterator Next = CurrentNewVRegs.begin(),
2636  End = CurrentNewVRegs.end();
2637  Next != End; ++Next) {
2638  if (RecoloringCandidates.count(&LIS->getInterval(*Next)))
2639  continue;
2640  NewVRegs.push_back(*Next);
2641  }
2642 
2643  for (SmallLISet::iterator It = RecoloringCandidates.begin(),
2644  EndIt = RecoloringCandidates.end();
2645  It != EndIt; ++It) {
2646  unsigned ItVirtReg = (*It)->reg;
2647  if (VRM->hasPhys(ItVirtReg))
2648  Matrix->unassign(**It);
2649  unsigned ItPhysReg = VirtRegToPhysReg[ItVirtReg];
2650  Matrix->assign(**It, ItPhysReg);
2651  }
2652  }
2653 
2654  // Last chance recoloring did not worked either, give up.
2655  return ~0u;
2656 }
2657 
2658 /// tryRecoloringCandidates - Try to assign a new color to every register
2659 /// in \RecoloringQueue.
2660 /// \p NewRegs will contain any new virtual register created during the
2661 /// recoloring process.
2662 /// \p FixedRegisters[in/out] contains all the registers that have been
2663 /// recolored.
2664 /// \return true if all virtual registers in RecoloringQueue were successfully
2665 /// recolored, false otherwise.
2666 bool RAGreedy::tryRecoloringCandidates(PQueue &RecoloringQueue,
2667  SmallVectorImpl<unsigned> &NewVRegs,
2668  SmallVirtRegSet &FixedRegisters,
2669  unsigned Depth) {
2670  while (!RecoloringQueue.empty()) {
2671  LiveInterval *LI = dequeue(RecoloringQueue);
2672  DEBUG(dbgs() << "Try to recolor: " << *LI << '\n');
2673  unsigned PhysReg;
2674  PhysReg = selectOrSplitImpl(*LI, NewVRegs, FixedRegisters, Depth + 1);
2675  // When splitting happens, the live-range may actually be empty.
2676  // In that case, this is okay to continue the recoloring even
2677  // if we did not find an alternative color for it. Indeed,
2678  // there will not be anything to color for LI in the end.
2679  if (PhysReg == ~0u || (!PhysReg && !LI->empty()))
2680  return false;
2681 
2682  if (!PhysReg) {
2683  assert(LI->empty() && "Only empty live-range do not require a register");
2684  DEBUG(dbgs() << "Recoloring of " << *LI << " succeeded. Empty LI.\n");
2685  continue;
2686  }
2687  DEBUG(dbgs() << "Recoloring of " << *LI
2688  << " succeeded with: " << printReg(PhysReg, TRI) << '\n');
2689 
2690  Matrix->assign(*LI, PhysReg);
2691  FixedRegisters.insert(LI->reg);
2692  }
2693  return true;
2694 }
2695 
2696 //===----------------------------------------------------------------------===//
2697 // Main Entry Point
2698 //===----------------------------------------------------------------------===//
2699 
2700 unsigned RAGreedy::selectOrSplit(LiveInterval &VirtReg,
2701  SmallVectorImpl<unsigned> &NewVRegs) {
2702  CutOffInfo = CO_None;
2703  LLVMContext &Ctx = MF->getFunction().getContext();
2704  SmallVirtRegSet FixedRegisters;
2705  unsigned Reg = selectOrSplitImpl(VirtReg, NewVRegs, FixedRegisters);
2706  if (Reg == ~0U && (CutOffInfo != CO_None)) {
2707  uint8_t CutOffEncountered = CutOffInfo & (CO_Depth | CO_Interf);
2708  if (CutOffEncountered == CO_Depth)
2709  Ctx.emitError("register allocation failed: maximum depth for recoloring "
2710  "reached. Use -fexhaustive-register-search to skip "
2711  "cutoffs");
2712  else if (CutOffEncountered == CO_Interf)
2713  Ctx.emitError("register allocation failed: maximum interference for "
2714  "recoloring reached. Use -fexhaustive-register-search "
2715  "to skip cutoffs");
2716  else if (CutOffEncountered == (CO_Depth | CO_Interf))
2717  Ctx.emitError("register allocation failed: maximum interference and "
2718  "depth for recoloring reached. Use "
2719  "-fexhaustive-register-search to skip cutoffs");
2720  }
2721  return Reg;
2722 }
2723 
2724 /// Using a CSR for the first time has a cost because it causes push|pop
2725 /// to be added to prologue|epilogue. Splitting a cold section of the live
2726 /// range can have lower cost than using the CSR for the first time;
2727 /// Spilling a live range in the cold path can have lower cost than using
2728 /// the CSR for the first time. Returns the physical register if we decide
2729 /// to use the CSR; otherwise return 0.
2730 unsigned RAGreedy::tryAssignCSRFirstTime(LiveInterval &VirtReg,
2731  AllocationOrder &Order,
2732  unsigned PhysReg,
2733  unsigned &CostPerUseLimit,
2734  SmallVectorImpl<unsigned> &NewVRegs) {
2735  if (getStage(VirtReg) == RS_Spill && VirtReg.isSpillable()) {
2736  // We choose spill over using the CSR for the first time if the spill cost
2737  // is lower than CSRCost.
2738  SA->analyze(&VirtReg);
2739  if (calcSpillCost() >= CSRCost)
2740  return PhysReg;
2741 
2742  // We are going to spill, set CostPerUseLimit to 1 to make sure that
2743  // we will not use a callee-saved register in tryEvict.
2744  CostPerUseLimit = 1;
2745  return 0;
2746  }
2747  if (getStage(VirtReg) < RS_Split) {
2748  // We choose pre-splitting over using the CSR for the first time if
2749  // the cost of splitting is lower than CSRCost.
2750  SA->analyze(&VirtReg);
2751  unsigned NumCands = 0;
2752  BlockFrequency BestCost = CSRCost; // Don't modify CSRCost.
2753  unsigned BestCand = calculateRegionSplitCost(VirtReg, Order, BestCost,
2754  NumCands, true /*IgnoreCSR*/);
2755  if (BestCand == NoCand)
2756  // Use the CSR if we can't find a region split below CSRCost.
2757  return PhysReg;
2758 
2759  // Perform the actual pre-splitting.
2760  doRegionSplit(VirtReg, BestCand, false/*HasCompact*/, NewVRegs);
2761  return 0;
2762  }
2763  return PhysReg;
2764 }
2765 
2766 void RAGreedy::aboutToRemoveInterval(LiveInterval &LI) {
2767  // Do not keep invalid information around.
2768  SetOfBrokenHints.remove(&LI);
2769 }
2770 
2771 void RAGreedy::initializeCSRCost() {
2772  // We use the larger one out of the command-line option and the value report
2773  // by TRI.
2774  CSRCost = BlockFrequency(
2775  std::max((unsigned)CSRFirstTimeCost, TRI->getCSRFirstUseCost()));
2776  if (!CSRCost.getFrequency())
2777  return;
2778 
2779  // Raw cost is relative to Entry == 2^14; scale it appropriately.
2780  uint64_t ActualEntry = MBFI->getEntryFreq();
2781  if (!ActualEntry) {
2782  CSRCost = 0;
2783  return;
2784  }
2785  uint64_t FixedEntry = 1 << 14;
2786  if (ActualEntry < FixedEntry)
2787  CSRCost *= BranchProbability(ActualEntry, FixedEntry);
2788  else if (ActualEntry <= UINT32_MAX)
2789  // Invert the fraction and divide.
2790  CSRCost /= BranchProbability(FixedEntry, ActualEntry);
2791  else
2792  // Can't use BranchProbability in general, since it takes 32-bit numbers.
2793  CSRCost = CSRCost.getFrequency() * (ActualEntry / FixedEntry);
2794 }
2795 
2796 /// \brief Collect the hint info for \p Reg.
2797 /// The results are stored into \p Out.
2798 /// \p Out is not cleared before being populated.
2799 void RAGreedy::collectHintInfo(unsigned Reg, HintsInfo &Out) {
2800  for (const MachineInstr &Instr : MRI->reg_nodbg_instructions(Reg)) {
2801  if (!Instr.isFullCopy())
2802  continue;
2803  // Look for the other end of the copy.
2804  unsigned OtherReg = Instr.getOperand(0).getReg();
2805  if (OtherReg == Reg) {
2806  OtherReg = Instr.getOperand(1).getReg();
2807  if (OtherReg == Reg)
2808  continue;
2809  }
2810  // Get the current assignment.
2811  unsigned OtherPhysReg = TargetRegisterInfo::isPhysicalRegister(OtherReg)
2812  ? OtherReg
2813  : VRM->getPhys(OtherReg);
2814  // Push the collected information.
2815  Out.push_back(HintInfo(MBFI->getBlockFreq(Instr.getParent()), OtherReg,
2816  OtherPhysReg));
2817  }
2818 }
2819 
2820 /// \brief Using the given \p List, compute the cost of the broken hints if
2821 /// \p PhysReg was used.
2822 /// \return The cost of \p List for \p PhysReg.
2823 BlockFrequency RAGreedy::getBrokenHintFreq(const HintsInfo &List,
2824  unsigned PhysReg) {
2825  BlockFrequency Cost = 0;
2826  for (const HintInfo &Info : List) {
2827  if (Info.PhysReg != PhysReg)
2828  Cost += Info.Freq;
2829  }
2830  return Cost;
2831 }
2832 
2833 /// \brief Using the register assigned to \p VirtReg, try to recolor
2834 /// all the live ranges that are copy-related with \p VirtReg.
2835 /// The recoloring is then propagated to all the live-ranges that have
2836 /// been recolored and so on, until no more copies can be coalesced or
2837 /// it is not profitable.
2838 /// For a given live range, profitability is determined by the sum of the
2839 /// frequencies of the non-identity copies it would introduce with the old
2840 /// and new register.
2841 void RAGreedy::tryHintRecoloring(LiveInterval &VirtReg) {
2842  // We have a broken hint, check if it is possible to fix it by
2843  // reusing PhysReg for the copy-related live-ranges. Indeed, we evicted
2844  // some register and PhysReg may be available for the other live-ranges.
2845  SmallSet<unsigned, 4> Visited;
2846  SmallVector<unsigned, 2> RecoloringCandidates;
2847  HintsInfo Info;
2848  unsigned Reg = VirtReg.reg;
2849  unsigned PhysReg = VRM->getPhys(Reg);
2850  // Start the recoloring algorithm from the input live-interval, then
2851  // it will propagate to the ones that are copy-related with it.
2852  Visited.insert(Reg);
2853  RecoloringCandidates.push_back(Reg);
2854 
2855  DEBUG(dbgs() << "Trying to reconcile hints for: " << printReg(Reg, TRI) << '('
2856  << printReg(PhysReg, TRI) << ")\n");
2857 
2858  do {
2859  Reg = RecoloringCandidates.pop_back_val();
2860 
2861  // We cannot recolor physical register.
2863  continue;
2864 
2865  assert(VRM->hasPhys(Reg) && "We have unallocated variable!!");
2866 
2867  // Get the live interval mapped with this virtual register to be able
2868  // to check for the interference with the new color.
2869  LiveInterval &LI = LIS->getInterval(Reg);
2870  unsigned CurrPhys = VRM->getPhys(Reg);
2871  // Check that the new color matches the register class constraints and
2872  // that it is free for this live range.
2873  if (CurrPhys != PhysReg && (!MRI->getRegClass(Reg)->contains(PhysReg) ||
2874  Matrix->checkInterference(LI, PhysReg)))
2875  continue;
2876 
2877  DEBUG(dbgs() << printReg(Reg, TRI) << '(' << printReg(CurrPhys, TRI)
2878  << ") is recolorable.\n");
2879 
2880  // Gather the hint info.
2881  Info.clear();
2882  collectHintInfo(Reg, Info);
2883  // Check if recoloring the live-range will increase the cost of the
2884  // non-identity copies.
2885  if (CurrPhys != PhysReg) {
2886  DEBUG(dbgs() << "Checking profitability:\n");
2887  BlockFrequency OldCopiesCost = getBrokenHintFreq(Info, CurrPhys);
2888  BlockFrequency NewCopiesCost = getBrokenHintFreq(Info, PhysReg);
2889  DEBUG(dbgs() << "Old Cost: " << OldCopiesCost.getFrequency()
2890  << "\nNew Cost: " << NewCopiesCost.getFrequency() << '\n');
2891  if (OldCopiesCost < NewCopiesCost) {
2892  DEBUG(dbgs() << "=> Not profitable.\n");
2893  continue;
2894  }
2895  // At this point, the cost is either cheaper or equal. If it is
2896  // equal, we consider this is profitable because it may expose
2897  // more recoloring opportunities.
2898  DEBUG(dbgs() << "=> Profitable.\n");
2899  // Recolor the live-range.
2900  Matrix->unassign(LI);
2901  Matrix->assign(LI, PhysReg);
2902  }
2903  // Push all copy-related live-ranges to keep reconciling the broken
2904  // hints.
2905  for (const HintInfo &HI : Info) {
2906  if (Visited.insert(HI.Reg).second)
2907  RecoloringCandidates.push_back(HI.Reg);
2908  }
2909  } while (!RecoloringCandidates.empty());
2910 }
2911 
2912 /// \brief Try to recolor broken hints.
2913 /// Broken hints may be repaired by recoloring when an evicted variable
2914 /// freed up a register for a larger live-range.
2915 /// Consider the following example:
2916 /// BB1:
2917 /// a =
2918 /// b =
2919 /// BB2:
2920 /// ...
2921 /// = b
2922 /// = a
2923 /// Let us assume b gets split:
2924 /// BB1:
2925 /// a =
2926 /// b =
2927 /// BB2:
2928 /// c = b
2929 /// ...
2930 /// d = c
2931 /// = d
2932 /// = a
2933 /// Because of how the allocation work, b, c, and d may be assigned different
2934 /// colors. Now, if a gets evicted later:
2935 /// BB1:
2936 /// a =
2937 /// st a, SpillSlot
2938 /// b =
2939 /// BB2:
2940 /// c = b
2941 /// ...
2942 /// d = c
2943 /// = d
2944 /// e = ld SpillSlot
2945 /// = e
2946 /// This is likely that we can assign the same register for b, c, and d,
2947 /// getting rid of 2 copies.
2948 void RAGreedy::tryHintsRecoloring() {
2949  for (LiveInterval *LI : SetOfBrokenHints) {
2951  "Recoloring is possible only for virtual registers");
2952  // Some dead defs may be around (e.g., because of debug uses).
2953  // Ignore those.
2954  if (!VRM->hasPhys(LI->reg))
2955  continue;
2956  tryHintRecoloring(*LI);
2957  }
2958 }
2959 
2960 unsigned RAGreedy::selectOrSplitImpl(LiveInterval &VirtReg,
2961  SmallVectorImpl<unsigned> &NewVRegs,
2962  SmallVirtRegSet &FixedRegisters,
2963  unsigned Depth) {
2964  unsigned CostPerUseLimit = ~0u;
2965  // First try assigning a free register.
2966  AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo, Matrix);
2967  if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs)) {
2968  // If VirtReg got an assignment, the eviction info is no longre relevant.
2969  LastEvicted.clearEvicteeInfo(VirtReg.reg);
2970  // When NewVRegs is not empty, we may have made decisions such as evicting
2971  // a virtual register, go with the earlier decisions and use the physical
2972  // register.
2973  if (CSRCost.getFrequency() && isUnusedCalleeSavedReg(PhysReg) &&
2974  NewVRegs.empty()) {
2975  unsigned CSRReg = tryAssignCSRFirstTime(VirtReg, Order, PhysReg,
2976  CostPerUseLimit, NewVRegs);
2977  if (CSRReg || !NewVRegs.empty())
2978  // Return now if we decide to use a CSR or create new vregs due to
2979  // pre-splitting.
2980  return CSRReg;
2981  } else
2982  return PhysReg;
2983  }
2984 
2985  LiveRangeStage Stage = getStage(VirtReg);
2986  DEBUG(dbgs() << StageName[Stage]
2987  << " Cascade " << ExtraRegInfo[VirtReg.reg].Cascade << '\n');
2988 
2989  // Try to evict a less worthy live range, but only for ranges from the primary
2990  // queue. The RS_Split ranges already failed to do this, and they should not
2991  // get a second chance until they have been split.
2992  if (Stage != RS_Split)
2993  if (unsigned PhysReg =
2994  tryEvict(VirtReg, Order, NewVRegs, CostPerUseLimit)) {
2995  unsigned Hint = MRI->getSimpleHint(VirtReg.reg);
2996  // If VirtReg has a hint and that hint is broken record this
2997  // virtual register as a recoloring candidate for broken hint.
2998  // Indeed, since we evicted a variable in its neighborhood it is
2999  // likely we can at least partially recolor some of the
3000  // copy-related live-ranges.
3001  if (Hint && Hint != PhysReg)
3002  SetOfBrokenHints.insert(&VirtReg);
3003  // If VirtReg eviction someone, the eviction info for it as an evictee is
3004  // no longre relevant.
3005  LastEvicted.clearEvicteeInfo(VirtReg.reg);
3006  return PhysReg;
3007  }
3008 
3009  assert((NewVRegs.empty() || Depth) && "Cannot append to existing NewVRegs");
3010 
3011  // The first time we see a live range, don't try to split or spill.
3012  // Wait until the second time, when all smaller ranges have been allocated.
3013  // This gives a better picture of the interference to split around.
3014  if (Stage < RS_Split) {
3015  setStage(VirtReg, RS_Split);
3016  DEBUG(dbgs() << "wait for second round\n");
3017  NewVRegs.push_back(VirtReg.reg);
3018  return 0;
3019  }
3020 
3021  if (Stage < RS_Spill) {
3022  // Try splitting VirtReg or interferences.
3023  unsigned NewVRegSizeBefore = NewVRegs.size();
3024  unsigned PhysReg = trySplit(VirtReg, Order, NewVRegs);
3025  if (PhysReg || (NewVRegs.size() - NewVRegSizeBefore)) {
3026  // If VirtReg got split, the eviction info is no longre relevant.
3027  LastEvicted.clearEvicteeInfo(VirtReg.reg);
3028  return PhysReg;
3029  }
3030  }
3031 
3032  // If we couldn't allocate a register from spilling, there is probably some
3033  // invalid inline assembly. The base class will report it.
3034  if (Stage >= RS_Done || !VirtReg.isSpillable())
3035  return tryLastChanceRecoloring(VirtReg, Order, NewVRegs, FixedRegisters,
3036  Depth);
3037 
3038  // Finally spill VirtReg itself.
3039  if (EnableDeferredSpilling && getStage(VirtReg) < RS_Memory) {
3040  // TODO: This is experimental and in particular, we do not model
3041  // the live range splitting done by spilling correctly.
3042  // We would need a deep integration with the spiller to do the
3043  // right thing here. Anyway, that is still good for early testing.
3044  setStage(VirtReg, RS_Memory);
3045  DEBUG(dbgs() << "Do as if this register is in memory\n");
3046  NewVRegs.push_back(VirtReg.reg);
3047  } else {
3048  NamedRegionTimer T("spill", "Spiller", TimerGroupName,
3049  TimerGroupDescription, TimePassesIsEnabled);
3050  LiveRangeEdit LRE(&VirtReg, NewVRegs, *MF, *LIS, VRM, this, &DeadRemats);
3051  spiller().spill(LRE);
3052  setStage(NewVRegs.begin(), NewVRegs.end(), RS_Done);
3053 
3054  if (VerifyEnabled)
3055  MF->verify(this, "After spilling");
3056  }
3057 
3058  // The live virtual register requesting allocation was spilled, so tell
3059  // the caller not to allocate anything during this round.
3060  return 0;
3061 }
3062 
3063 void RAGreedy::reportNumberOfSplillsReloads(MachineLoop *L, unsigned &Reloads,
3064  unsigned &FoldedReloads,
3065  unsigned &Spills,
3066  unsigned &FoldedSpills) {
3067  Reloads = 0;
3068  FoldedReloads = 0;
3069  Spills = 0;
3070  FoldedSpills = 0;
3071 
3072  // Sum up the spill and reloads in subloops.
3073  for (MachineLoop *SubLoop : *L) {
3074  unsigned SubReloads;
3075  unsigned SubFoldedReloads;
3076  unsigned SubSpills;
3077  unsigned SubFoldedSpills;
3078 
3079  reportNumberOfSplillsReloads(SubLoop, SubReloads, SubFoldedReloads,
3080  SubSpills, SubFoldedSpills);
3081  Reloads += SubReloads;
3082  FoldedReloads += SubFoldedReloads;
3083  Spills += SubSpills;
3084  FoldedSpills += SubFoldedSpills;
3085  }
3086 
3087  const MachineFrameInfo &MFI = MF->getFrameInfo();
3088  const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
3089  int FI;
3090 
3091  for (MachineBasicBlock *MBB : L->getBlocks())
3092  // Handle blocks that were not included in subloops.
3093  if (Loops->getLoopFor(MBB) == L)
3094  for (MachineInstr &MI : *MBB) {
3095  const MachineMemOperand *MMO;
3096 
3097  if (TII->isLoadFromStackSlot(MI, FI) && MFI.isSpillSlotObjectIndex(FI))
3098  ++Reloads;
3099  else if (TII->hasLoadFromStackSlot(MI, MMO, FI) &&
3100  MFI.isSpillSlotObjectIndex(FI))
3101  ++FoldedReloads;
3102  else if (TII->isStoreToStackSlot(MI, FI) &&
3103  MFI.isSpillSlotObjectIndex(FI))
3104  ++Spills;
3105  else if (TII->hasStoreToStackSlot(MI, MMO, FI) &&
3106  MFI.isSpillSlotObjectIndex(FI))
3107  ++FoldedSpills;
3108  }
3109 
3110  if (Reloads || FoldedReloads || Spills || FoldedSpills) {
3111  using namespace ore;
3112 
3113  ORE->emit([&]() {
3114  MachineOptimizationRemarkMissed R(DEBUG_TYPE, "LoopSpillReload",
3115  L->getStartLoc(), L->getHeader());
3116  if (Spills)
3117  R << NV("NumSpills", Spills) << " spills ";
3118  if (FoldedSpills)
3119  R << NV("NumFoldedSpills", FoldedSpills) << " folded spills ";
3120  if (Reloads)
3121  R << NV("NumReloads", Reloads) << " reloads ";
3122  if (FoldedReloads)
3123  R << NV("NumFoldedReloads", FoldedReloads) << " folded reloads ";
3124  R << "generated in loop";
3125  return R;
3126  });
3127  }
3128 }
3129 
3130 bool RAGreedy::runOnMachineFunction(MachineFunction &mf) {
3131  DEBUG(dbgs() << "********** GREEDY REGISTER ALLOCATION **********\n"
3132  << "********** Function: " << mf.getName() << '\n');
3133 
3134  MF = &mf;
3135  TRI = MF->getSubtarget().getRegisterInfo();
3136  TII = MF->getSubtarget().getInstrInfo();
3137  RCI.runOnMachineFunction(mf);
3138 
3139  EnableLocalReassign = EnableLocalReassignment ||
3140  MF->getSubtarget().enableRALocalReassignment(
3141  MF->getTarget().getOptLevel());
3142 
3143  EnableAdvancedRASplitCost = ConsiderLocalIntervalCost ||
3144  MF->getSubtarget().enableAdvancedRASplitCost();
3145 
3146  if (VerifyEnabled)
3147  MF->verify(this, "Before greedy register allocator");
3148 
3149  RegAllocBase::init(getAnalysis<VirtRegMap>(),
3150  getAnalysis<LiveIntervals>(),
3151  getAnalysis<LiveRegMatrix>());
3152  Indexes = &getAnalysis<SlotIndexes>();
3153  MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
3154  DomTree = &getAnalysis<MachineDominatorTree>();
3155  ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
3156  SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
3157  Loops = &getAnalysis<MachineLoopInfo>();
3158  Bundles = &getAnalysis<EdgeBundles>();
3159  SpillPlacer = &getAnalysis<SpillPlacement>();
3160  DebugVars = &getAnalysis<LiveDebugVariables>();
3161  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
3162 
3163  initializeCSRCost();
3164 
3165  calculateSpillWeightsAndHints(*LIS, mf, VRM, *Loops, *MBFI);
3166 
3167  DEBUG(LIS->dump());
3168 
3169  SA.reset(new SplitAnalysis(*VRM, *LIS, *Loops));
3170  SE.reset(new SplitEditor(*SA, *AA, *LIS, *VRM, *DomTree, *MBFI));
3171  ExtraRegInfo.clear();
3172  ExtraRegInfo.resize(MRI->getNumVirtRegs());
3173  NextCascade = 1;
3174  IntfCache.init(MF, Matrix->getLiveUnions(), Indexes, LIS, TRI);
3175  GlobalCand.resize(32); // This will grow as needed.
3176  SetOfBrokenHints.clear();
3177  LastEvicted.clear();
3178 
3179  allocatePhysRegs();
3180  tryHintsRecoloring();
3181  postOptimization();
3182  reportNumberOfSplillsReloads();
3183 
3184  releaseMemory();
3185  return true;
3186 }
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 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
bool valid() const
valid - Return true if the current position is valid, false for end().
Definition: IntervalMap.h:1349
char & RAGreedyID
Greedy register allocator.
The default distance between instructions as returned by distance().
Definition: SlotIndexes.h:138
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:160
ArrayRef< unsigned > getRecentPositive()
getRecentPositive - Return an array of bundles that became positive during the previous call to scanA...
iterator end()
Definition: LiveInterval.h:212
Reg
All possible values of the reg field in the ModR/M byte.
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...
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubRegIdx=0)
Prints virtual and physical registers with or without a TRI instance.
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:910
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:406
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.
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:626
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:194
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:285
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:132
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:210
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:601
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)
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.
#define DEBUG(X)
Definition: Debug.h:118
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
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:42
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.