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