LLVM 17.0.0git
FunctionSpecialization.h
Go to the documentation of this file.
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
59
60using namespace llvm;
61
62namespace llvm {
63// Specialization signature, used to uniquely designate a specialization within
64// a function.
65struct SpecSig {
66 // Hashing support, used to distinguish between ordinary, empty, or tombstone
67 // keys.
68 unsigned Key = 0;
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.
87struct Spec {
88 // Original function.
90
91 // Cloned function, a specialized version of the original one.
92 Function *Clone = nullptr;
93
94 // Specialization signature.
96
97 // Profitability of the specialization.
99
100 // List of call sites, matching this specialization.
102
104 : F(F), Sig(S), Gain(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.
114
116
117 /// The IPSCCP Solver.
118 SCCPSolver &Solver;
119
120 Module &M;
121
122 /// Analysis manager, needed to invalidate analyses.
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 SmallPtrSet<Function *, 32> Specializations;
131 SmallPtrSet<Function *, 32> FullySpecialized;
132 DenseMap<Function *, CodeMetrics> FunctionMetrics;
133
134public:
136 SCCPSolver &Solver, Module &M, FunctionAnalysisManager *FAM,
137 std::function<const TargetLibraryInfo &(Function &)> GetTLI,
138 std::function<TargetTransformInfo &(Function &)> GetTTI,
139 std::function<AssumptionCache &(Function &)> GetAC)
140 : Solver(Solver), M(M), FAM(FAM), GetTLI(GetTLI), GetTTI(GetTTI),
141 GetAC(GetAC) {}
142
144
145 bool isClonedFunction(Function *F) { return Specializations.count(F); }
146
147 bool run();
148
149private:
150 Constant *getPromotableAlloca(AllocaInst *Alloca, CallInst *Call);
151
152 /// A constant stack value is an AllocaInst that has a single constant
153 /// value stored to it. Return this constant if such an alloca stack value
154 /// is a function argument.
155 Constant *getConstantStackValue(CallInst *Call, Value *Val);
156
157 /// Iterate over the argument tracked functions see if there
158 /// are any new constant values for the call instruction via
159 /// stack variables.
160 void promoteConstantStackValues();
161
162 /// Clean up fully specialized functions.
163 void removeDeadFunctions();
164
165 /// Remove any ssa_copy intrinsics that may have been introduced.
166 void cleanUpSSA();
167
168 // Compute the code metrics for function \p F.
169 CodeMetrics &analyzeFunction(Function *F);
170
171 /// @brief Find potential specialization opportunities.
172 /// @param F Function to specialize
173 /// @param Cost Cost of specializing a function. Final gain is this cost
174 /// minus benefit
175 /// @param AllSpecs A vector to add potential specializations to.
176 /// @param SM A map for a function's specialisation range
177 /// @return True, if any potential specializations were found
178 bool findSpecializations(Function *F, InstructionCost Cost,
179 SmallVectorImpl<Spec> &AllSpecs, SpecMap &SM);
180
181 bool isCandidateFunction(Function *F);
182
183 /// @brief Create a specialization of \p F and prime the SCCPSolver
184 /// @param F Function to specialize
185 /// @param S Which specialization to create
186 /// @return The new, cloned function
187 Function *createSpecialization(Function *F, const SpecSig &S);
188
189 /// Compute and return the cost of specializing function \p F.
190 InstructionCost getSpecializationCost(Function *F);
191
192 /// Compute a bonus for replacing argument \p A with constant \p C.
193 InstructionCost getSpecializationBonus(Argument *A, Constant *C,
194 const LoopInfo &LI);
195
196 /// Determine if it is possible to specialise the function for constant values
197 /// of the formal parameter \p A.
198 bool isArgumentInteresting(Argument *A);
199
200 /// Check if the value \p V (an actual argument) is a constant or can only
201 /// have a constant value. Return that constant.
202 Constant *getCandidateConstant(Value *V);
203
204 /// @brief Find and update calls to \p F, which match a specialization
205 /// @param F Orginal function
206 /// @param Begin Start of a range of possibly matching specialisations
207 /// @param End End of a range (exclusive) of possibly matching specialisations
208 void updateCallSites(Function *F, const Spec *Begin, const Spec *End);
209};
210} // namespace llvm
211
212#endif // LLVM_TRANSFORMS_IPO_FUNCTIONSPECIALIZATION_H
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define G(x, y, z)
Definition: MD5.cpp:56
FunctionAnalysisManager FAM
This pass exposes codegen information to IR-level passes.
an instruction to allocate memory on the stack
Definition: Instructions.h:58
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
A cache of @llvm.assume calls within a function.
This class represents a function call, abstracting a target machine's calling convention.
This is an important base class in LLVM.
Definition: Constant.h:41
bool run()
Attempt to specialize functions in the module to enable constant propagation across function boundari...
FunctionSpecializer(SCCPSolver &Solver, Module &M, FunctionAnalysisManager *FAM, std::function< const TargetLibraryInfo &(Function &)> GetTLI, std::function< TargetTransformInfo &(Function &)> GetTTI, std::function< AssumptionCache &(Function &)> GetAC)
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
SCCPSolver - This interface class is a general purpose solver for Sparse Conditional Constant Propaga...
Definition: SCCPSolver.h:75
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
Provides information about what library functions are available for the current target.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
LLVM Value Representation.
Definition: Value.h:74
An opaque object representing a hash code.
Definition: Hashing.h:74
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:613
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:491
Utility to calculate the size and a few similar metrics for a set of basic blocks.
Definition: CodeMetrics.h:31
SmallVector< ArgInfo, 4 > Args
bool operator==(const SpecSig &Other) const
friend hash_code hash_value(const SpecSig &S)
Spec(Function *F, const SpecSig &S, InstructionCost G)
SmallVector< CallBase * > CallSites
InstructionCost Gain
Spec(Function *F, const SpecSig &&S, InstructionCost G)