1 //===- FunctionSpecialization.h - Function Specialization -----------------===// 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 specialises functions with constant parameters. Constant parameters 10 // like function pointers and constant globals are propagated to the callee by 11 // specializing the function. The main benefit of this pass at the moment is 12 // that indirect calls are transformed into direct calls, which provides inline 13 // opportunities that the inliner would not have been able to achieve. That's 14 // why function specialisation is run before the inliner in the optimisation 15 // pipeline; that is by design. Otherwise, we would only benefit from constant 16 // passing, which is a valid use-case too, but hasn't been explored much in 17 // terms of performance uplifts, cost-model and compile-time impact. 18 // 19 // Current limitations: 20 // - It does not yet handle integer ranges. We do support "literal constants", 21 // but that's off by default under an option. 22 // - The cost-model could be further looked into (it mainly focuses on inlining 23 // benefits), 24 // 25 // Ideas: 26 // - With a function specialization attribute for arguments, we could have 27 // a direct way to steer function specialization, avoiding the cost-model, 28 // and thus control compile-times / code-size. 29 // 30 // Todos: 31 // - Specializing recursive functions relies on running the transformation a 32 // number of times, which is controlled by option 33 // `func-specialization-max-iters`. Thus, increasing this value and the 34 // number of iterations, will linearly increase the number of times recursive 35 // functions get specialized, see also the discussion in 36 // https://reviews.llvm.org/D106426 for details. Perhaps there is a 37 // compile-time friendlier way to control/limit the number of specialisations 38 // for recursive functions. 39 // - Don't transform the function if function specialization does not trigger; 40 // the SCCPSolver may make IR changes. 41 // 42 // References: 43 // - 2021 LLVM Dev Mtg “Introducing function specialisation, and can we enable 44 // it by default?”, https://www.youtube.com/watch?v=zJiCjeXgV5Q 45 // 46 //===----------------------------------------------------------------------===// 47 48 #ifndef LLVM_TRANSFORMS_IPO_FUNCTIONSPECIALIZATION_H 49 #define LLVM_TRANSFORMS_IPO_FUNCTIONSPECIALIZATION_H 50 51 #include "llvm/Analysis/CodeMetrics.h" 52 #include "llvm/Analysis/InlineCost.h" 53 #include "llvm/Analysis/LoopInfo.h" 54 #include "llvm/Analysis/TargetTransformInfo.h" 55 #include "llvm/Transforms/Scalar/SCCP.h" 56 #include "llvm/Transforms/Utils/Cloning.h" 57 #include "llvm/Transforms/Utils/SCCPSolver.h" 58 #include "llvm/Transforms/Utils/SizeOpts.h" 59 60 using namespace llvm; 61 62 namespace llvm { 63 // Specialization signature, used to uniquely designate a specialization within 64 // a function. 65 struct SpecSig { 66 // Hashing support, used to distinguish between ordinary, empty, or tombstone 67 // keys. 68 unsigned Key = 0; 69 SmallVector<ArgInfo, 4> Args; 70 71 bool operator==(const SpecSig &Other) const { 72 if (Key != Other.Key || Args.size() != Other.Args.size()) 73 return false; 74 for (size_t I = 0; I < Args.size(); ++I) 75 if (Args[I] != Other.Args[I]) 76 return false; 77 return true; 78 } 79 80 friend hash_code hash_value(const SpecSig &S) { 81 return hash_combine(hash_value(S.Key), 82 hash_combine_range(S.Args.begin(), S.Args.end())); 83 } 84 }; 85 86 // Specialization instance. 87 struct Spec { 88 // Original function. 89 Function *F; 90 91 // Cloned function, a specialized version of the original one. 92 Function *Clone = nullptr; 93 94 // Specialization signature. 95 SpecSig Sig; 96 97 // Profitability of the specialization. 98 InstructionCost Gain; 99 100 // List of call sites, matching this specialization. 101 SmallVector<CallBase *> CallSites; 102 103 Spec(Function *F, const SpecSig &S, InstructionCost G) 104 : F(F), Sig(S), Gain(G) {} 105 Spec(Function *F, const SpecSig &&S, InstructionCost G) 106 : F(F), Sig(S), Gain(G) {} 107 }; 108 109 // Map of potential specializations for each function. The FunctionSpecializer 110 // keeps the discovered specialisation opportunities for the module in a single 111 // vector, where the specialisations of each function form a contiguous range. 112 // This map's value is the beginning and the end of that range. 113 using SpecMap = DenseMap<Function *, std::pair<unsigned, unsigned>>; 114 115 class FunctionSpecializer { 116 117 /// The IPSCCP Solver. 118 SCCPSolver &Solver; 119 120 Module &M; 121 122 /// Analysis manager, needed to invalidate analyses. 123 FunctionAnalysisManager *FAM; 124 125 /// Analyses used to help determine if a function should be specialized. 126 std::function<const TargetLibraryInfo &(Function &)> GetTLI; 127 std::function<TargetTransformInfo &(Function &)> GetTTI; 128 std::function<AssumptionCache &(Function &)> GetAC; 129 130 // The number of functions specialised, used for collecting statistics and 131 // also in the cost model. 132 unsigned NbFunctionsSpecialized = 0; 133 134 SmallPtrSet<Function *, 32> SpecializedFuncs; 135 SmallPtrSet<Function *, 32> FullySpecialized; 136 DenseMap<Function *, CodeMetrics> FunctionMetrics; 137 138 public: 139 FunctionSpecializer( 140 SCCPSolver &Solver, Module &M, FunctionAnalysisManager *FAM, 141 std::function<const TargetLibraryInfo &(Function &)> GetTLI, 142 std::function<TargetTransformInfo &(Function &)> GetTTI, 143 std::function<AssumptionCache &(Function &)> GetAC) 144 : Solver(Solver), M(M), FAM(FAM), GetTLI(GetTLI), GetTTI(GetTTI), 145 GetAC(GetAC) {} 146 147 ~FunctionSpecializer() { 148 // Eliminate dead code. 149 removeDeadFunctions(); 150 cleanUpSSA(); 151 } 152 153 bool isClonedFunction(Function *F) { return SpecializedFuncs.count(F); } 154 155 bool run(); 156 157 private: 158 Constant *getPromotableAlloca(AllocaInst *Alloca, CallInst *Call); 159 160 /// A constant stack value is an AllocaInst that has a single constant 161 /// value stored to it. Return this constant if such an alloca stack value 162 /// is a function argument. 163 Constant *getConstantStackValue(CallInst *Call, Value *Val); 164 165 /// Iterate over the argument tracked functions see if there 166 /// are any new constant values for the call instruction via 167 /// stack variables. 168 void promoteConstantStackValues(); 169 170 /// Clean up fully specialized functions. 171 void removeDeadFunctions(); 172 173 /// Remove any ssa_copy intrinsics that may have been introduced. 174 void cleanUpSSA(); 175 176 // Compute the code metrics for function \p F. 177 CodeMetrics &analyzeFunction(Function *F); 178 179 /// @brief Find potential specialization opportunities. 180 /// @param F Function to specialize 181 /// @param Cost Cost of specializing a function. Final gain is this cost 182 /// minus benefit 183 /// @param AllSpecs A vector to add potential specializations to. 184 /// @param SM A map for a function's specialisation range 185 /// @return True, if any potential specializations were found 186 bool findSpecializations(Function *F, InstructionCost Cost, 187 SmallVectorImpl<Spec> &AllSpecs, SpecMap &SM); 188 189 bool isCandidateFunction(Function *F); 190 191 /// @brief Create a specialization of \p F and prime the SCCPSolver 192 /// @param F Function to specialize 193 /// @param S Which specialization to create 194 /// @return The new, cloned function 195 Function *createSpecialization(Function *F, const SpecSig &S); 196 197 /// Compute and return the cost of specializing function \p F. 198 InstructionCost getSpecializationCost(Function *F); 199 200 /// Compute a bonus for replacing argument \p A with constant \p C. 201 InstructionCost getSpecializationBonus(Argument *A, Constant *C, 202 const LoopInfo &LI); 203 204 /// Determine if it is possible to specialise the function for constant values 205 /// of the formal parameter \p A. 206 bool isArgumentInteresting(Argument *A); 207 208 /// Check if the value \p V (an actual argument) is a constant or can only 209 /// have a constant value. Return that constant. 210 Constant *getCandidateConstant(Value *V); 211 212 /// @brief Find and update calls to \p F, which match a specialization 213 /// @param F Orginal function 214 /// @param Begin Start of a range of possibly matching specialisations 215 /// @param End End of a range (exclusive) of possibly matching specialisations 216 void updateCallSites(Function *F, const Spec *Begin, const Spec *End); 217 }; 218 } // namespace llvm 219 220 #endif // LLVM_TRANSFORMS_IPO_FUNCTIONSPECIALIZATION_H 221