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

Generated by: LCOV version 1.13