LCOV - code coverage report
Current view: top level - lib/CodeGen - RegAllocGreedy.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 951 985 96.5 %
Date: 2018-02-22 04:41:24 Functions: 71 72 98.6 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13