| //===- FunctionSpecialization.h - Function Specialization -----------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This specialises functions with constant parameters. Constant parameters |
| // like function pointers and constant globals are propagated to the callee by |
| // specializing the function. The main benefit of this pass at the moment is |
| // that indirect calls are transformed into direct calls, which provides inline |
| // opportunities that the inliner would not have been able to achieve. That's |
| // why function specialisation is run before the inliner in the optimisation |
| // pipeline; that is by design. Otherwise, we would only benefit from constant |
| // passing, which is a valid use-case too, but hasn't been explored much in |
| // terms of performance uplifts, cost-model and compile-time impact. |
| // |
| // Current limitations: |
| // - It does not yet handle integer ranges. We do support "literal constants", |
| // but that's off by default under an option. |
| // - The cost-model could be further looked into (it mainly focuses on inlining |
| // benefits), |
| // |
| // Ideas: |
| // - With a function specialization attribute for arguments, we could have |
| // a direct way to steer function specialization, avoiding the cost-model, |
| // and thus control compile-times / code-size. |
| // |
| // Todos: |
| // - Specializing recursive functions relies on running the transformation a |
| // number of times, which is controlled by option |
| // `func-specialization-max-iters`. Thus, increasing this value and the |
| // number of iterations, will linearly increase the number of times recursive |
| // functions get specialized, see also the discussion in |
| // https://reviews.llvm.org/D106426 for details. Perhaps there is a |
| // compile-time friendlier way to control/limit the number of specialisations |
| // for recursive functions. |
| // - Don't transform the function if function specialization does not trigger; |
| // the SCCPSolver may make IR changes. |
| // |
| // References: |
| // - 2021 LLVM Dev Mtg “Introducing function specialisation, and can we enable |
| // it by default?”, https://www.youtube.com/watch?v=zJiCjeXgV5Q |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_TRANSFORMS_IPO_FUNCTIONSPECIALIZATION_H |
| #define LLVM_TRANSFORMS_IPO_FUNCTIONSPECIALIZATION_H |
| |
| #include "llvm/Analysis/CodeMetrics.h" |
| #include "llvm/Analysis/InlineCost.h" |
| #include "llvm/Analysis/LoopInfo.h" |
| #include "llvm/Analysis/TargetTransformInfo.h" |
| #include "llvm/Transforms/Scalar/SCCP.h" |
| #include "llvm/Transforms/Utils/Cloning.h" |
| #include "llvm/Transforms/Utils/SCCPSolver.h" |
| #include "llvm/Transforms/Utils/SizeOpts.h" |
| |
| using namespace llvm; |
| |
| namespace llvm { |
| // Specialization signature, used to uniquely designate a specialization within |
| // a function. |
| struct SpecSig { |
| // Hashing support, used to distinguish between ordinary, empty, or tombstone |
| // keys. |
| unsigned Key = 0; |
| SmallVector<ArgInfo, 4> Args; |
| |
| bool operator==(const SpecSig &Other) const { |
| if (Key != Other.Key || Args.size() != Other.Args.size()) |
| return false; |
| for (size_t I = 0; I < Args.size(); ++I) |
| if (Args[I] != Other.Args[I]) |
| return false; |
| return true; |
| } |
| |
| friend hash_code hash_value(const SpecSig &S) { |
| return hash_combine(hash_value(S.Key), |
| hash_combine_range(S.Args.begin(), S.Args.end())); |
| } |
| }; |
| |
| // Specialization instance. |
| struct Spec { |
| // Original function. |
| Function *F; |
| |
| // Cloned function, a specialized version of the original one. |
| Function *Clone = nullptr; |
| |
| // Specialization signature. |
| SpecSig Sig; |
| |
| // Profitability of the specialization. |
| InstructionCost Gain; |
| |
| // List of call sites, matching this specialization. |
| SmallVector<CallBase *> CallSites; |
| |
| Spec(Function *F, const SpecSig &S, InstructionCost G) |
| : F(F), Sig(S), Gain(G) {} |
| Spec(Function *F, const SpecSig &&S, InstructionCost G) |
| : F(F), Sig(S), Gain(G) {} |
| }; |
| |
| // Map of potential specializations for each function. The FunctionSpecializer |
| // keeps the discovered specialisation opportunities for the module in a single |
| // vector, where the specialisations of each function form a contiguous range. |
| // This map's value is the beginning and the end of that range. |
| using SpecMap = DenseMap<Function *, std::pair<unsigned, unsigned>>; |
| |
| class FunctionSpecializer { |
| |
| /// The IPSCCP Solver. |
| SCCPSolver &Solver; |
| |
| Module &M; |
| |
| /// Analysis manager, needed to invalidate analyses. |
| FunctionAnalysisManager *FAM; |
| |
| /// Analyses used to help determine if a function should be specialized. |
| std::function<const TargetLibraryInfo &(Function &)> GetTLI; |
| std::function<TargetTransformInfo &(Function &)> GetTTI; |
| std::function<AssumptionCache &(Function &)> GetAC; |
| |
| // The number of functions specialised, used for collecting statistics and |
| // also in the cost model. |
| unsigned NbFunctionsSpecialized = 0; |
| |
| SmallPtrSet<Function *, 32> SpecializedFuncs; |
| SmallPtrSet<Function *, 32> FullySpecialized; |
| DenseMap<Function *, CodeMetrics> FunctionMetrics; |
| |
| public: |
| FunctionSpecializer( |
| SCCPSolver &Solver, Module &M, FunctionAnalysisManager *FAM, |
| std::function<const TargetLibraryInfo &(Function &)> GetTLI, |
| std::function<TargetTransformInfo &(Function &)> GetTTI, |
| std::function<AssumptionCache &(Function &)> GetAC) |
| : Solver(Solver), M(M), FAM(FAM), GetTLI(GetTLI), GetTTI(GetTTI), |
| GetAC(GetAC) {} |
| |
| ~FunctionSpecializer() { |
| // Eliminate dead code. |
| removeDeadFunctions(); |
| cleanUpSSA(); |
| } |
| |
| bool isClonedFunction(Function *F) { return SpecializedFuncs.count(F); } |
| |
| bool run(); |
| |
| private: |
| Constant *getPromotableAlloca(AllocaInst *Alloca, CallInst *Call); |
| |
| /// A constant stack value is an AllocaInst that has a single constant |
| /// value stored to it. Return this constant if such an alloca stack value |
| /// is a function argument. |
| Constant *getConstantStackValue(CallInst *Call, Value *Val); |
| |
| /// Iterate over the argument tracked functions see if there |
| /// are any new constant values for the call instruction via |
| /// stack variables. |
| void promoteConstantStackValues(); |
| |
| /// Clean up fully specialized functions. |
| void removeDeadFunctions(); |
| |
| /// Remove any ssa_copy intrinsics that may have been introduced. |
| void cleanUpSSA(); |
| |
| // Compute the code metrics for function \p F. |
| CodeMetrics &analyzeFunction(Function *F); |
| |
| /// @brief Find potential specialization opportunities. |
| /// @param F Function to specialize |
| /// @param Cost Cost of specializing a function. Final gain is this cost |
| /// minus benefit |
| /// @param AllSpecs A vector to add potential specializations to. |
| /// @param SM A map for a function's specialisation range |
| /// @return True, if any potential specializations were found |
| bool findSpecializations(Function *F, InstructionCost Cost, |
| SmallVectorImpl<Spec> &AllSpecs, SpecMap &SM); |
| |
| bool isCandidateFunction(Function *F); |
| |
| /// @brief Create a specialization of \p F and prime the SCCPSolver |
| /// @param F Function to specialize |
| /// @param S Which specialization to create |
| /// @return The new, cloned function |
| Function *createSpecialization(Function *F, const SpecSig &S); |
| |
| /// Compute and return the cost of specializing function \p F. |
| InstructionCost getSpecializationCost(Function *F); |
| |
| /// Compute a bonus for replacing argument \p A with constant \p C. |
| InstructionCost getSpecializationBonus(Argument *A, Constant *C, |
| const LoopInfo &LI); |
| |
| /// Determine if it is possible to specialise the function for constant values |
| /// of the formal parameter \p A. |
| bool isArgumentInteresting(Argument *A); |
| |
| /// Check if the value \p V (an actual argument) is a constant or can only |
| /// have a constant value. Return that constant. |
| Constant *getCandidateConstant(Value *V); |
| |
| /// @brief Find and update calls to \p F, which match a specialization |
| /// @param F Orginal function |
| /// @param Begin Start of a range of possibly matching specialisations |
| /// @param End End of a range (exclusive) of possibly matching specialisations |
| void updateCallSites(Function *F, const Spec *Begin, const Spec *End); |
| }; |
| } // namespace llvm |
| |
| #endif // LLVM_TRANSFORMS_IPO_FUNCTIONSPECIALIZATION_H |