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