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