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