LCOV - code coverage report
Current view: top level - lib/CodeGen - RegAllocGreedy.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 954 987 96.7 %
Date: 2018-07-13 00:08:38 Functions: 71 72 98.6 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13