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