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