1//===- FunctionSpecialization.h - Function Specialization -----------------===//
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
7//===----------------------------------------------------------------------===//
11// Function Specialization is a transformation which propagates the constant
12// parameters of a function call from the caller to the callee. It is part of
13// the Inter-Procedural Sparse Conditional Constant Propagation (IPSCCP) pass.
14// The transformation runs iteratively a number of times which is controlled
15// by the option `funcspec-max-iters`. Running it multiple times is needed
16// for specializing recursive functions, but also exposes new opportunities
17// arising from specializations which return constant values or contain calls
18// which can be specialized.
20// Function Specialization supports propagating constant parameters like
21// function pointers, literal constants and addresses of global variables.
22// By propagating function pointers, indirect calls become direct calls. This
23// exposes inlining opportunities which we would have otherwise missed. That's
24// why function specialization is run before the inliner in the optimization
25// pipeline; that is by design.
29// The cost model facilitates a utility for estimating the specialization bonus
30// from propagating a constant argument. This is the InstCostVisitor, a class
31// that inherits from the InstVisitor. The bonus itself is expressed as codesize
32// and latency savings. Codesize savings means the amount of code that becomes
33// dead in the specialization from propagating the constant, whereas latency
34// savings represents the cycles we are saving from replacing instructions with
35// constant values. The InstCostVisitor overrides a set of `visit*` methods to
36// be able to handle different types of instructions. These attempt to constant-
37// fold the instruction in which case a constant is returned and propagated
40// Function pointers are not handled by the InstCostVisitor. They are treated
41// separately as they could expose inlining opportunities via indirect call
42// promotion. The inlining bonus contributes to the total specialization score.
44// For a specialization to be profitable its bonus needs to exceed a minimum
45// threshold. There are three options for controlling the threshold which are
46// expressed as percentages of the original function size:
47// * funcspec-min-codesize-savings
48// * funcspec-min-latency-savings
49// * funcspec-min-inlining-bonus
50// There's also an option for controlling the codesize growth from recursive
51// specializations. That is `funcspec-max-codesize-growth`.
53// Once we have all the potential specializations with their score we need to
54// choose the best ones, which fit in the module specialization budget. That
55// is controlled by the option `funcspec-max-clones`. To find the best `NSpec`
56// specializations we use a max-heap. For more details refer to D139346.
60// - With a function specialization attribute for arguments, we could have
61// a direct way to steer function specialization, avoiding the cost-model,
62// and thus control compile-times / code-size.
64// - Perhaps a post-inlining function specialization pass could be more
65// aggressive on literal constants.
69// - We are unable to consider specializations of functions called from indirect
70// callsites whose pointer operand has a lattice value that is known to be
71// constant, either from IPSCCP or previous iterations of FuncSpec. This is
72// because SCCP has not yet replaced the uses of the known constant.
76// 2021 LLVM Dev Mtg "Introducing function specialisation, and can we enable
77// it by default?", https://www.youtube.com/watch?v=zJiCjeXgV5Q
79//===----------------------------------------------------------------------===//
81#ifndef LLVM_TRANSFORMS_IPO_FUNCTIONSPECIALIZATION_H
82#define LLVM_TRANSFORMS_IPO_FUNCTIONSPECIALIZATION_H
96// Map of potential specializations for each function. The FunctionSpecializer
97// keeps the discovered specialisation opportunities for the module in a single
98// vector, where the specialisations of each function form a contiguous range.
99// This map's value is the beginning and the end of that range.
102// Just a shorter abbreviation to improve indentation.
105// Map of known constants found during the specialization bonus estimation.
108// Specialization signature, used to uniquely designate a specialization within
111 // Hashing support, used to distinguish between ordinary, empty, or tombstone
127// Specialization instance.
129 // Original function.
132 // Cloned function, a specialized version of the original one.
135 // Specialization signature.
138 // Profitability of the specialization.
141 // Number of instructions in the specialization.
144 // List of call sites, matching this specialization.
161 // Basic blocks known to be unreachable after constant propagation.
163 // PHI nodes we have visited before.
165 // PHI nodes we have visited once without successfully constant folding them.
166 // Once the InstCostVisitor has processed all the specialization arguments,
167 // it should be possible to determine whether those PHIs can be folded
168 // (some of their incoming values may have become constant or dead).
177 : GetBFI(GetBFI), F(F), DL(DL), TTI(TTI), Solver(Solver) {}
180 return Solver.isBlockExecutable(BB) && !DeadBlocks.contains(BB);
203 // Transitively Incoming Values (TIV) is a set of Values that can "feed" a
204 // value to the initial PHI-node. It is defined like this:
206 // * the initial PHI-node belongs to TIV.
208 // * for every PHI-node in TIV, its operands belong to TIV
210 // If TIV for the initial PHI-node (P) contains more than one constant or a
211 // value that is not a PHI-node, then P cannot be folded to a constant.
213 // As soon as we detect these cases, we bail, without constructing the
215 // Otherwise P can be folded to the one constant in TIV.
216 bool discoverTransitivelyIncomingValues(
Constant *Const,
PHINode *Root,
234 /// The IPSCCP Solver.
239 /// Analysis manager, needed to invalidate analyses.
242 /// Analyses used to help determine if a function should be specialized.
252 unsigned NGlobals = 0;
261 : Solver(Solver), M(M), FAM(FAM), GetBFI(GetBFI), GetTLI(GetTLI),
262 GetTTI(GetTTI), GetAC(GetAC) {}
269 auto &
TTI = GetTTI(*
F);
278 /// A constant stack value is an AllocaInst that has a single constant
279 /// value stored to it. Return this constant if such an alloca stack value
280 /// is a function argument.
283 /// See if there are any new constant values for the callers of \p F via
284 /// stack variables and promote them to global variables.
285 void promoteConstantStackValues(
Function *
F);
287 /// Clean up fully specialized functions.
288 void removeDeadFunctions();
290 /// Remove any ssa_copy intrinsics that may have been introduced.
293 /// @brief Find potential specialization opportunities.
294 /// @param F Function to specialize
295 /// @param FuncSize Cost of specializing a function.
296 /// @param AllSpecs A vector to add potential specializations to.
297 /// @param SM A map for a function's specialisation range
298 /// @return True, if any potential specializations were found
299 bool findSpecializations(
Function *
F,
unsigned FuncSize,
302 /// Compute the inlining bonus for replacing argument \p A with constant \p C.
307 /// @brief Create a specialization of \p F and prime the SCCPSolver
308 /// @param F Function to specialize
309 /// @param S Which specialization to create
310 /// @return The new, cloned function
313 /// Determine if it is possible to specialise the function for constant values
314 /// of the formal parameter \p A.
317 /// Check if the value \p V (an actual argument) is a constant or can only
318 /// have a constant value. Return that constant.
321 /// @brief Find and update calls to \p F, which match a specialization
322 /// @param F Orginal function
323 /// @param Begin Start of a range of possibly matching specialisations
324 /// @param End End of a range (exclusive) of possibly matching specialisations
329#endif // LLVM_TRANSFORMS_IPO_FUNCTIONSPECIALIZATION_H
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
an instruction to allocate memory on the stack
This class represents an incoming formal argument to a Function.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Conditional or Unconditional Branch instruction.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
This class represents a function call, abstracting a target machine's calling convention.
This is the base class for all instructions that perform data casts.
This class is the base class for the comparison instructions.
This is an important base class in LLVM.
A parsed version of the target data layout string in and methods for querying it.
DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator
Implements a dense probed hash-table based set.
This class represents a freeze function that returns random concrete value if an operand is either a ...
LLVM_ABI ~FunctionSpecializer()
LLVM_ABI 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< BlockFrequencyInfo &(Function &)> GetBFI, std::function< const TargetLibraryInfo &(Function &)> GetTLI, std::function< TargetTransformInfo &(Function &)> GetTTI, std::function< AssumptionCache &(Function &)> GetAC)
InstCostVisitor getInstCostVisitorFor(Function *F)
bool isDeadFunction(Function *F)
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
LLVM_ABI Cost getLatencySavingsForKnownConstants()
Compute the latency savings from replacing all arguments with constants for a specialization candidat...
LLVM_ABI Cost getCodeSizeSavingsForArg(Argument *A, Constant *C)
Compute the codesize savings for replacing argument A with constant C.
LLVM_ABI Cost getCodeSizeSavingsFromPendingPHIs()
InstCostVisitor(std::function< BlockFrequencyInfo &(Function &)> GetBFI, Function *F, const DataLayout &DL, TargetTransformInfo &TTI, SCCPSolver &Solver)
bool isBlockExecutable(BasicBlock *BB) const
Base class for instruction visitors.
An instruction for reading from memory.
A Module instance is used to store all the information related to an LLVM module.
SCCPSolver - This interface class is a general purpose solver for Sparse Conditional Constant Propaga...
This class represents the LLVM 'select' instruction.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Provides information about what library functions are available for the current target.
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
An opaque object representing a hash code.
@ C
The default llvm calling convention, compatible with C.
This is an optimization pass for GlobalISel generic memory operations.
DenseMap< Value *, Constant * > ConstMap
DenseMap< Function *, std::pair< unsigned, unsigned > > SpecMap
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
SmallVector< ArgInfo, 4 > Args
bool operator==(const SpecSig &Other) const
friend hash_code hash_value(const SpecSig &S)
Spec(Function *F, const SpecSig &&S, unsigned Score, unsigned CodeSize)
SmallVector< CallBase * > CallSites
Spec(Function *F, const SpecSig &S, unsigned Score, unsigned CodeSize)