LLVM 17.0.0git
ModuleInliner.cpp
Go to the documentation of this file.
1//===- ModuleInliner.cpp - Code related to module inliner -----------------===//
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 file implements the mechanics required to implement inlining without
10// missing any calls in the module level. It doesn't need any infromation about
11// SCC or call graph, which is different from the SCC inliner. The decisions of
12// which calls are profitable to inline are implemented elsewhere.
13//
14//===----------------------------------------------------------------------===//
15
17#include "llvm/ADT/ScopeExit.h"
19#include "llvm/ADT/Statistic.h"
31#include "llvm/IR/Function.h"
33#include "llvm/IR/Instruction.h"
35#include "llvm/IR/Module.h"
36#include "llvm/IR/PassManager.h"
38#include "llvm/Support/Debug.h"
42#include <cassert>
43
44using namespace llvm;
45
46#define DEBUG_TYPE "module-inline"
47
48STATISTIC(NumInlined, "Number of functions inlined");
49STATISTIC(NumDeleted, "Number of functions deleted because all callers found");
50
51/// Return true if the specified inline history ID
52/// indicates an inline history that includes the specified function.
54 Function *F, int InlineHistoryID,
55 const SmallVectorImpl<std::pair<Function *, int>> &InlineHistory) {
56 while (InlineHistoryID != -1) {
57 assert(unsigned(InlineHistoryID) < InlineHistory.size() &&
58 "Invalid inline history ID");
59 if (InlineHistory[InlineHistoryID].first == F)
60 return true;
61 InlineHistoryID = InlineHistory[InlineHistoryID].second;
62 }
63 return false;
64}
65
66InlineAdvisor &ModuleInlinerPass::getAdvisor(const ModuleAnalysisManager &MAM,
68 Module &M) {
69 if (OwnedAdvisor)
70 return *OwnedAdvisor;
71
73 if (!IAA) {
74 // It should still be possible to run the inliner as a stand-alone module
75 // pass, for test scenarios. In that case, we default to the
76 // DefaultInlineAdvisor, which doesn't need to keep state between module
77 // pass runs. It also uses just the default InlineParams. In this case, we
78 // need to use the provided FAM, which is valid for the duration of the
79 // inliner pass, and thus the lifetime of the owned advisor. The one we
80 // would get from the MAM can be invalidated as a result of the inliner's
81 // activity.
82 OwnedAdvisor = std::make_unique<DefaultInlineAdvisor>(
83 M, FAM, Params, InlineContext{LTOPhase, InlinePass::ModuleInliner});
84
85 return *OwnedAdvisor;
86 }
87 assert(IAA->getAdvisor() &&
88 "Expected a present InlineAdvisorAnalysis also have an "
89 "InlineAdvisor initialized");
90 return *IAA->getAdvisor();
91}
92
94 LibFunc LF;
95
96 // Either this is a normal library function or a "vectorizable"
97 // function. Not using the VFDatabase here because this query
98 // is related only to libraries handled via the TLI.
99 return TLI.getLibFunc(F, LF) ||
100 TLI.isKnownVectorFunctionInLibrary(F.getName());
101}
102
105 LLVM_DEBUG(dbgs() << "---- Module Inliner is Running ---- \n");
106
107 auto &IAA = MAM.getResult<InlineAdvisorAnalysis>(M);
108 if (!IAA.tryCreate(Params, Mode, {},
109 InlineContext{LTOPhase, InlinePass::ModuleInliner})) {
110 M.getContext().emitError(
111 "Could not setup Inlining Advisor for the requested "
112 "mode and/or options");
113 return PreservedAnalyses::all();
114 }
115
116 bool Changed = false;
117
119
122
123 auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & {
125 };
126
127 InlineAdvisor &Advisor = getAdvisor(MAM, FAM, M);
128 Advisor.onPassEntry();
129
130 auto AdvisorOnExit = make_scope_exit([&] { Advisor.onPassExit(); });
131
132 // In the module inliner, a priority-based worklist is used for calls across
133 // the entire Module. With this module inliner, the inline order is not
134 // limited to bottom-up order. More globally scope inline order is enabled.
135 // Also, the inline deferral logic become unnecessary in this module inliner.
136 // It is possible to use other priority heuristics, e.g. profile-based
137 // heuristic.
138 //
139 // TODO: Here is a huge amount duplicate code between the module inliner and
140 // the SCC inliner, which need some refactoring.
141 auto Calls = getInlineOrder(FAM, Params, MAM, M);
142 assert(Calls != nullptr && "Expected an initialized InlineOrder");
143
144 // Populate the initial list of calls in this module.
145 for (Function &F : M) {
147 // We want to generally process call sites top-down in order for
148 // simplifications stemming from replacing the call with the returned value
149 // after inlining to be visible to subsequent inlining decisions.
150 // FIXME: Using instructions sequence is a really bad way to do this.
151 // Instead we should do an actual RPO walk of the function body.
152 for (Instruction &I : instructions(F))
153 if (auto *CB = dyn_cast<CallBase>(&I))
154 if (Function *Callee = CB->getCalledFunction()) {
155 if (!Callee->isDeclaration())
156 Calls->push({CB, -1});
157 else if (!isa<IntrinsicInst>(I)) {
158 using namespace ore;
159 setInlineRemark(*CB, "unavailable definition");
160 ORE.emit([&]() {
161 return OptimizationRemarkMissed(DEBUG_TYPE, "NoDefinition", &I)
162 << NV("Callee", Callee) << " will not be inlined into "
163 << NV("Caller", CB->getCaller())
164 << " because its definition is unavailable"
165 << setIsVerbose();
166 });
167 }
168 }
169 }
170 if (Calls->empty())
171 return PreservedAnalyses::all();
172
173 // When inlining a callee produces new call sites, we want to keep track of
174 // the fact that they were inlined from the callee. This allows us to avoid
175 // infinite inlining in some obscure cases. To represent this, we use an
176 // index into the InlineHistory vector.
178
179 // Track the dead functions to delete once finished with inlining calls. We
180 // defer deleting these to make it easier to handle the call graph updates.
181 SmallVector<Function *, 4> DeadFunctions;
182
183 // Loop forward over all of the calls.
184 while (!Calls->empty()) {
185 auto P = Calls->pop();
186 CallBase *CB = P.first;
187 const int InlineHistoryID = P.second;
188 Function &F = *CB->getCaller();
190
191 LLVM_DEBUG(dbgs() << "Inlining calls in: " << F.getName() << "\n"
192 << " Function size: " << F.getInstructionCount()
193 << "\n");
194 (void)F;
195
196 auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
198 };
199
200 if (InlineHistoryID != -1 &&
201 inlineHistoryIncludes(&Callee, InlineHistoryID, InlineHistory)) {
202 setInlineRemark(*CB, "recursive");
203 continue;
204 }
205
206 auto Advice = Advisor.getAdvice(*CB, /*OnlyMandatory*/ false);
207 // Check whether we want to inline this callsite.
208 if (!Advice->isInliningRecommended()) {
209 Advice->recordUnattemptedInlining();
210 continue;
211 }
212
213 // Setup the data structure used to plumb customization into the
214 // `InlineFunction` routine.
216 GetAssumptionCache, PSI,
219
221 InlineFunction(*CB, IFI, /*MergeAttributes=*/true,
222 &FAM.getResult<AAManager>(*CB->getCaller()));
223 if (!IR.isSuccess()) {
224 Advice->recordUnsuccessfulInlining(IR);
225 continue;
226 }
227
228 Changed = true;
229 ++NumInlined;
230
231 LLVM_DEBUG(dbgs() << " Size after inlining: " << F.getInstructionCount()
232 << "\n");
233
234 // Add any new callsites to defined functions to the worklist.
235 if (!IFI.InlinedCallSites.empty()) {
236 int NewHistoryID = InlineHistory.size();
237 InlineHistory.push_back({&Callee, InlineHistoryID});
238
239 for (CallBase *ICB : reverse(IFI.InlinedCallSites)) {
240 Function *NewCallee = ICB->getCalledFunction();
241 if (!NewCallee) {
242 // Try to promote an indirect (virtual) call without waiting for
243 // the post-inline cleanup and the next DevirtSCCRepeatedPass
244 // iteration because the next iteration may not happen and we may
245 // miss inlining it.
246 if (tryPromoteCall(*ICB))
247 NewCallee = ICB->getCalledFunction();
248 }
249 if (NewCallee)
250 if (!NewCallee->isDeclaration())
251 Calls->push({ICB, NewHistoryID});
252 }
253 }
254
255 // For local functions, check whether this makes the callee trivially
256 // dead. In that case, we can drop the body of the function eagerly
257 // which may reduce the number of callers of other functions to one,
258 // changing inline cost thresholds.
259 bool CalleeWasDeleted = false;
260 if (Callee.hasLocalLinkage()) {
261 // To check this we also need to nuke any dead constant uses (perhaps
262 // made dead by this operation on other functions).
263 Callee.removeDeadConstantUsers();
264 // if (Callee.use_empty() && !CG.isLibFunction(Callee)) {
265 if (Callee.use_empty() && !isKnownLibFunction(Callee, GetTLI(Callee))) {
266 Calls->erase_if([&](const std::pair<CallBase *, int> &Call) {
267 return Call.first->getCaller() == &Callee;
268 });
269 // Clear the body and queue the function itself for deletion when we
270 // finish inlining.
271 // Note that after this point, it is an error to do anything other
272 // than use the callee's address or delete it.
273 Callee.dropAllReferences();
274 assert(!is_contained(DeadFunctions, &Callee) &&
275 "Cannot put cause a function to become dead twice!");
276 DeadFunctions.push_back(&Callee);
277 CalleeWasDeleted = true;
278 }
279 }
280 if (CalleeWasDeleted)
281 Advice->recordInliningWithCalleeDeleted();
282 else
283 Advice->recordInlining();
284 }
285
286 // Now that we've finished inlining all of the calls across this module,
287 // delete all of the trivially dead functions.
288 //
289 // Note that this walks a pointer set which has non-deterministic order but
290 // that is OK as all we do is delete things and add pointers to unordered
291 // sets.
292 for (Function *DeadF : DeadFunctions) {
293 // Clear out any cached analyses.
294 FAM.clear(*DeadF, DeadF->getName());
295
296 // And delete the actual function from the module.
297 M.getFunctionList().erase(DeadF);
298
299 ++NumDeleted;
300 }
301
302 if (!Changed)
303 return PreservedAnalyses::all();
304
306}
amdgpu Simplify well known AMD library false FunctionCallee Callee
#define LLVM_DEBUG(X)
Definition: Debug.h:101
#define DEBUG_TYPE
static bool inlineHistoryIncludes(Function *F, int InlineHistoryID, const SmallVectorImpl< std::pair< Function *, int > > &InlineHistory)
Return true if the specified inline history ID indicates an inline history that includes the specifie...
Definition: Inliner.cpp:151
static bool isKnownLibFunction(Function &F, TargetLibraryInfo &TLI)
Statically lint checks LLVM IR
Definition: Lint.cpp:746
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
static bool inlineHistoryIncludes(Function *F, int InlineHistoryID, const SmallVectorImpl< std::pair< Function *, int > > &InlineHistory)
Return true if the specified inline history ID indicates an inline history that includes the specifie...
Module.h This file contains the declarations for the Module class.
print must be executed print the must be executed context for all instructions
#define P(N)
FunctionAnalysisManager FAM
ModuleAnalysisManager MAM
This header defines various interfaces for pass management in LLVM.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
A manager for alias analyses.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
void clear(IRUnitT &IR, llvm::StringRef Name)
Clear any cached analysis results for a single unit of IR.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:793
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
Analysis pass which computes BlockFrequencyInfo.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1186
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1408
Function * getCaller()
Helper to get the caller (the parent function).
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:275
The InlineAdvisorAnalysis is a module pass because the InlineAdvisor needs to capture state right bef...
Interface for deciding whether to inline a call site or not.
virtual void onPassEntry(LazyCallGraph::SCC *SCC=nullptr)
This must be called when the Inliner pass is entered, to allow the InlineAdvisor update internal stat...
virtual void onPassExit(LazyCallGraph::SCC *SCC=nullptr)
This must be called when the Inliner pass is exited, as function passes may be run subsequently.
This class captures the data input to the InlineFunction call, and records the auxiliary results prod...
Definition: Cloning.h:203
InlineResult is basically true or false.
Definition: InlineCost.h:179
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:933
PreservedAnalyses run(Module &, ModuleAnalysisManager &)
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
Diagnostic information for missed-optimization remarks.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:155
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
Analysis providing profile information.
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
bool isKnownVectorFunctionInLibrary(StringRef F) const
Check if the function "F" is listed in a library known to LLVM.
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:59
void setInlineRemark(CallBase &CB, StringRef Message)
Set the inline-remark attribute.
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:511
std::unique_ptr< InlineOrder< std::pair< CallBase *, int > > > getInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params, ModuleAnalysisManager &MAM, Module &M)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
InlineResult InlineFunction(CallBase &CB, InlineFunctionInfo &IFI, bool MergeAttributes=false, AAResults *CalleeAAR=nullptr, bool InsertLifetime=true, Function *ForwardVarArgsTo=nullptr)
This function inlines the called function into the basic block of the caller.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1976
bool tryPromoteCall(CallBase &CB)
Try to promote (devirtualize) a virtual call on an Alloca.
Provides context on when an inline advisor is constructed in the pipeline (e.g., link phase,...
Definition: InlineAdvisor.h:60