1 //===- SpillPlacement.h - Optimal Spill Code Placement ---------*- C++ -*--===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This analysis computes the optimal spill code placement between basic blocks. 10 // 11 // The runOnMachineFunction() method only precomputes some profiling information 12 // about the CFG. The real work is done by prepare(), addConstraints(), and 13 // finish() which are called by the register allocator. 14 // 15 // Given a variable that is live across multiple basic blocks, and given 16 // constraints on the basic blocks where the variable is live, determine which 17 // edge bundles should have the variable in a register and which edge bundles 18 // should have the variable in a stack slot. 19 // 20 // The returned bit vector can be used to place optimal spill code at basic 21 // block entries and exits. Spill code placement inside a basic block is not 22 // considered. 23 // 24 //===----------------------------------------------------------------------===// 25 26 #ifndef LLVM_LIB_CODEGEN_SPILLPLACEMENT_H 27 #define LLVM_LIB_CODEGEN_SPILLPLACEMENT_H 28 29 #include "llvm/ADT/ArrayRef.h" 30 #include "llvm/ADT/SmallVector.h" 31 #include "llvm/ADT/SparseSet.h" 32 #include "llvm/CodeGen/MachineFunctionAnalysis.h" 33 #include "llvm/CodeGen/MachineFunctionPass.h" 34 #include "llvm/Support/BlockFrequency.h" 35 36 namespace llvm { 37 38 class BitVector; 39 class EdgeBundles; 40 class MachineBlockFrequencyInfo; 41 class MachineFunction; 42 class SpillPlacementWrapperLegacy; 43 class SpillPlacementAnalysis; 44 45 class SpillPlacement { 46 friend class SpillPlacementWrapperLegacy; 47 friend class SpillPlacementAnalysis; 48 49 struct Node; 50 51 const MachineFunction *MF = nullptr; 52 const EdgeBundles *bundles = nullptr; 53 const MachineBlockFrequencyInfo *MBFI = nullptr; 54 55 std::unique_ptr<Node[]> nodes; 56 57 // Nodes that are active in the current computation. Owned by the prepare() 58 // caller. 59 BitVector *ActiveNodes = nullptr; 60 61 // Nodes with active links. Populated by scanActiveBundles. 62 SmallVector<unsigned, 8> Linked; 63 64 // Nodes that went positive during the last call to scanActiveBundles or 65 // iterate. 66 SmallVector<unsigned, 8> RecentPositive; 67 68 // Block frequencies are computed once. Indexed by block number. 69 SmallVector<BlockFrequency, 8> BlockFrequencies; 70 71 /// Decision threshold. A node gets the output value 0 if the weighted sum of 72 /// its inputs falls in the open interval (-Threshold;Threshold). 73 BlockFrequency Threshold; 74 75 /// List of nodes that need to be updated in ::iterate. 76 SparseSet<unsigned> TodoList; 77 78 public: 79 /// BorderConstraint - A basic block has separate constraints for entry and 80 /// exit. 81 enum BorderConstraint { 82 DontCare, ///< Block doesn't care / variable not live. 83 PrefReg, ///< Block entry/exit prefers a register. 84 PrefSpill, ///< Block entry/exit prefers a stack slot. 85 PrefBoth, ///< Block entry prefers both register and stack. 86 MustSpill ///< A register is impossible, variable must be spilled. 87 }; 88 89 /// BlockConstraint - Entry and exit constraints for a basic block. 90 struct BlockConstraint { 91 unsigned Number; ///< Basic block number (from MBB::getNumber()). 92 BorderConstraint Entry : 8; ///< Constraint on block entry. 93 BorderConstraint Exit : 8; ///< Constraint on block exit. 94 95 /// True when this block changes the value of the live range. This means 96 /// the block has a non-PHI def. When this is false, a live-in value on 97 /// the stack can be live-out on the stack without inserting a spill. 98 bool ChangesValue; 99 100 void print(raw_ostream &OS) const; 101 void dump() const; 102 }; 103 104 /// prepare - Reset state and prepare for a new spill placement computation. 105 /// @param RegBundles Bit vector to receive the edge bundles where the 106 /// variable should be kept in a register. Each bit 107 /// corresponds to an edge bundle, a set bit means the 108 /// variable should be kept in a register through the 109 /// bundle. A clear bit means the variable should be 110 /// spilled. This vector is retained. 111 void prepare(BitVector &RegBundles); 112 113 /// addConstraints - Add constraints and biases. This method may be called 114 /// more than once to accumulate constraints. 115 /// @param LiveBlocks Constraints for blocks that have the variable live in or 116 /// live out. 117 void addConstraints(ArrayRef<BlockConstraint> LiveBlocks); 118 119 /// addPrefSpill - Add PrefSpill constraints to all blocks listed. This is 120 /// equivalent to calling addConstraint with identical BlockConstraints with 121 /// Entry = Exit = PrefSpill, and ChangesValue = false. 122 /// 123 /// @param Blocks Array of block numbers that prefer to spill in and out. 124 /// @param Strong When true, double the negative bias for these blocks. 125 void addPrefSpill(ArrayRef<unsigned> Blocks, bool Strong); 126 127 /// addLinks - Add transparent blocks with the given numbers. 128 void addLinks(ArrayRef<unsigned> Links); 129 130 /// scanActiveBundles - Perform an initial scan of all bundles activated by 131 /// addConstraints and addLinks, updating their state. Add all the bundles 132 /// that now prefer a register to RecentPositive. 133 /// Prepare internal data structures for iterate. 134 /// Return true is there are any positive nodes. 135 bool scanActiveBundles(); 136 137 /// iterate - Update the network iteratively until convergence, or new bundles 138 /// are found. 139 void iterate(); 140 141 /// getRecentPositive - Return an array of bundles that became positive during 142 /// the previous call to scanActiveBundles or iterate. getRecentPositive()143 ArrayRef<unsigned> getRecentPositive() { return RecentPositive; } 144 145 /// finish - Compute the optimal spill code placement given the 146 /// constraints. No MustSpill constraints will be violated, and the smallest 147 /// possible number of PrefX constraints will be violated, weighted by 148 /// expected execution frequencies. 149 /// The selected bundles are returned in the bitvector passed to prepare(). 150 /// @return True if a perfect solution was found, allowing the variable to be 151 /// in a register through all relevant bundles. 152 bool finish(); 153 154 /// getBlockFrequency - Return the estimated block execution frequency per 155 /// function invocation. getBlockFrequency(unsigned Number)156 BlockFrequency getBlockFrequency(unsigned Number) const { 157 return BlockFrequencies[Number]; 158 } 159 160 bool invalidate(MachineFunction &MF, const PreservedAnalyses &PA, 161 MachineFunctionAnalysisManager::Invalidator &Inv); 162 163 SpillPlacement(SpillPlacement &&); 164 ~SpillPlacement(); 165 166 private: 167 SpillPlacement(); 168 169 void releaseMemory(); 170 171 void run(MachineFunction &MF, EdgeBundles *Bundles, 172 MachineBlockFrequencyInfo *MBFI); 173 void activate(unsigned n); 174 void setThreshold(BlockFrequency Entry); 175 176 bool update(unsigned n); 177 }; 178 179 class SpillPlacementWrapperLegacy : public MachineFunctionPass { 180 public: 181 static char ID; SpillPlacementWrapperLegacy()182 SpillPlacementWrapperLegacy() : MachineFunctionPass(ID) {} 183 getResult()184 SpillPlacement &getResult() { return Impl; } getResult()185 const SpillPlacement &getResult() const { return Impl; } 186 187 private: 188 SpillPlacement Impl; 189 bool runOnMachineFunction(MachineFunction &MF) override; 190 void getAnalysisUsage(AnalysisUsage &AU) const override; releaseMemory()191 void releaseMemory() override { Impl.releaseMemory(); } 192 }; 193 194 class SpillPlacementAnalysis 195 : public AnalysisInfoMixin<SpillPlacementAnalysis> { 196 friend AnalysisInfoMixin<SpillPlacementAnalysis>; 197 static AnalysisKey Key; 198 199 public: 200 using Result = SpillPlacement; 201 SpillPlacement run(MachineFunction &, MachineFunctionAnalysisManager &); 202 }; 203 204 } // end namespace llvm 205 206 #endif // LLVM_LIB_CODEGEN_SPILLPLACEMENT_H 207