Stephen Hines | c6ca60f | 2023-05-09 02:19:22 -0700 | [diff] [blame^] | 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 |