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

Generated by: LCOV version 1.13