LLVM 19.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 for (Instruction &I : instructions(F))
148 if (auto *CB = dyn_cast<CallBase>(&I))
149 if (Function *Callee = CB->getCalledFunction()) {
150 if (!Callee->isDeclaration())
151 Calls->push({CB, -1});
152 else if (!isa<IntrinsicInst>(I)) {
153 using namespace ore;
154 setInlineRemark(*CB, "unavailable definition");
155 ORE.emit([&]() {
156 return OptimizationRemarkMissed(DEBUG_TYPE, "NoDefinition", &I)
157 << NV("Callee", Callee) << " will not be inlined into "
158 << NV("Caller", CB->getCaller())
159 << " because its definition is unavailable"
160 << setIsVerbose();
161 });
162 }
163 }
164 }
165 if (Calls->empty())
166 return PreservedAnalyses::all();
167
168 // When inlining a callee produces new call sites, we want to keep track of
169 // the fact that they were inlined from the callee. This allows us to avoid
170 // infinite inlining in some obscure cases. To represent this, we use an
171 // index into the InlineHistory vector.
173
174 // Track the dead functions to delete once finished with inlining calls. We
175 // defer deleting these to make it easier to handle the call graph updates.
176 SmallVector<Function *, 4> DeadFunctions;
177
178 // Loop forward over all of the calls.
179 while (!Calls->empty()) {
180 auto P = Calls->pop();
181 CallBase *CB = P.first;
182 const int InlineHistoryID = P.second;
183 Function &F = *CB->getCaller();
184 Function &Callee = *CB->getCalledFunction();
185
186 LLVM_DEBUG(dbgs() << "Inlining calls in: " << F.getName() << "\n"
187 << " Function size: " << F.getInstructionCount()
188 << "\n");
189 (void)F;
190
191 auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
193 };
194
195 if (InlineHistoryID != -1 &&
196 inlineHistoryIncludes(&Callee, InlineHistoryID, InlineHistory)) {
197 setInlineRemark(*CB, "recursive");
198 continue;
199 }
200
201 auto Advice = Advisor.getAdvice(*CB, /*OnlyMandatory*/ false);
202 // Check whether we want to inline this callsite.
203 if (!Advice->isInliningRecommended()) {
204 Advice->recordUnattemptedInlining();
205 continue;
206 }
207
208 // Setup the data structure used to plumb customization into the
209 // `InlineFunction` routine.
211 GetAssumptionCache, PSI,
214
216 InlineFunction(*CB, IFI, /*MergeAttributes=*/true,
217 &FAM.getResult<AAManager>(*CB->getCaller()));
218 if (!IR.isSuccess()) {
219 Advice->recordUnsuccessfulInlining(IR);
220 continue;
221 }
222
223 Changed = true;
224 ++NumInlined;
225
226 LLVM_DEBUG(dbgs() << " Size after inlining: " << F.getInstructionCount()
227 << "\n");
228
229 // Add any new callsites to defined functions to the worklist.
230 if (!IFI.InlinedCallSites.empty()) {
231 int NewHistoryID = InlineHistory.size();
232 InlineHistory.push_back({&Callee, InlineHistoryID});
233
234 for (CallBase *ICB : reverse(IFI.InlinedCallSites)) {
235 Function *NewCallee = ICB->getCalledFunction();
236 if (!NewCallee) {
237 // Try to promote an indirect (virtual) call without waiting for
238 // the post-inline cleanup and the next DevirtSCCRepeatedPass
239 // iteration because the next iteration may not happen and we may
240 // miss inlining it.
241 if (tryPromoteCall(*ICB))
242 NewCallee = ICB->getCalledFunction();
243 }
244 if (NewCallee)
245 if (!NewCallee->isDeclaration())
246 Calls->push({ICB, NewHistoryID});
247 }
248 }
249
250 // For local functions, check whether this makes the callee trivially
251 // dead. In that case, we can drop the body of the function eagerly
252 // which may reduce the number of callers of other functions to one,
253 // changing inline cost thresholds.
254 bool CalleeWasDeleted = false;
255 if (Callee.hasLocalLinkage()) {
256 // To check this we also need to nuke any dead constant uses (perhaps
257 // made dead by this operation on other functions).
258 Callee.removeDeadConstantUsers();
259 // if (Callee.use_empty() && !CG.isLibFunction(Callee)) {
260 if (Callee.use_empty() && !isKnownLibFunction(Callee, GetTLI(Callee))) {
261 Calls->erase_if([&](const std::pair<CallBase *, int> &Call) {
262 return Call.first->getCaller() == &Callee;
263 });
264 // Clear the body and queue the function itself for deletion when we
265 // finish inlining.
266 // Note that after this point, it is an error to do anything other
267 // than use the callee's address or delete it.
268 Callee.dropAllReferences();
269 assert(!is_contained(DeadFunctions, &Callee) &&
270 "Cannot put cause a function to become dead twice!");
271 DeadFunctions.push_back(&Callee);
272 CalleeWasDeleted = true;
273 }
274 }
275 if (CalleeWasDeleted)
276 Advice->recordInliningWithCalleeDeleted();
277 else
278 Advice->recordInlining();
279 }
280
281 // Now that we've finished inlining all of the calls across this module,
282 // delete all of the trivially dead functions.
283 //
284 // Note that this walks a pointer set which has non-deterministic order but
285 // that is OK as all we do is delete things and add pointers to unordered
286 // sets.
287 for (Function *DeadF : DeadFunctions) {
288 // Clear out any cached analyses.
289 FAM.clear(*DeadF, DeadF->getName());
290
291 // And delete the actual function from the module.
292 M.getFunctionList().erase(DeadF);
293
294 ++NumDeleted;
295 }
296
297 if (!Changed)
298 return PreservedAnalyses::all();
299
301}
Expand Atomic instructions
#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:149
static bool isKnownLibFunction(Function &F, TargetLibraryInfo &TLI)
Legalize the Machine IR a function s Machine IR
Definition: Legalizer.cpp:81
#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.
#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:348
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:519
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
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:1461
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1709
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:274
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:202
InlineResult is basically true or false.
Definition: InlineCost.h:180
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:658
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: Analysis.h:109
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
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:586
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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:428
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:1888
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:59