LLVM 20.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"
32#include "llvm/IR/Function.h"
34#include "llvm/IR/Instruction.h"
36#include "llvm/IR/Module.h"
37#include "llvm/IR/PassManager.h"
39#include "llvm/Support/Debug.h"
43#include <cassert>
44
45using namespace llvm;
46
47#define DEBUG_TYPE "module-inline"
48
49STATISTIC(NumInlined, "Number of functions inlined");
50STATISTIC(NumDeleted, "Number of functions deleted because all callers found");
51
53 "ctx-prof-promote-alwaysinline", cl::init(false), cl::Hidden,
54 cl::desc("If using a contextual profile in this module, and an indirect "
55 "call target is marked as alwaysinline, perform indirect call "
56 "promotion for that target. If multiple targets for an indirect "
57 "call site fit this description, they are all promoted."));
58
59/// Return true if the specified inline history ID
60/// indicates an inline history that includes the specified function.
62 Function *F, int InlineHistoryID,
63 const SmallVectorImpl<std::pair<Function *, int>> &InlineHistory) {
64 while (InlineHistoryID != -1) {
65 assert(unsigned(InlineHistoryID) < InlineHistory.size() &&
66 "Invalid inline history ID");
67 if (InlineHistory[InlineHistoryID].first == F)
68 return true;
69 InlineHistoryID = InlineHistory[InlineHistoryID].second;
70 }
71 return false;
72}
73
74InlineAdvisor &ModuleInlinerPass::getAdvisor(const ModuleAnalysisManager &MAM,
76 Module &M) {
77 if (OwnedAdvisor)
78 return *OwnedAdvisor;
79
81 if (!IAA) {
82 // It should still be possible to run the inliner as a stand-alone module
83 // pass, for test scenarios. In that case, we default to the
84 // DefaultInlineAdvisor, which doesn't need to keep state between module
85 // pass runs. It also uses just the default InlineParams. In this case, we
86 // need to use the provided FAM, which is valid for the duration of the
87 // inliner pass, and thus the lifetime of the owned advisor. The one we
88 // would get from the MAM can be invalidated as a result of the inliner's
89 // activity.
90 OwnedAdvisor = std::make_unique<DefaultInlineAdvisor>(
91 M, FAM, Params, InlineContext{LTOPhase, InlinePass::ModuleInliner});
92
93 return *OwnedAdvisor;
94 }
95 assert(IAA->getAdvisor() &&
96 "Expected a present InlineAdvisorAnalysis also have an "
97 "InlineAdvisor initialized");
98 return *IAA->getAdvisor();
99}
100
102 LibFunc LF;
103
104 // Either this is a normal library function or a "vectorizable"
105 // function. Not using the VFDatabase here because this query
106 // is related only to libraries handled via the TLI.
107 return TLI.getLibFunc(F, LF) ||
108 TLI.isKnownVectorFunctionInLibrary(F.getName());
109}
110
113 LLVM_DEBUG(dbgs() << "---- Module Inliner is Running ---- \n");
114
115 auto &IAA = MAM.getResult<InlineAdvisorAnalysis>(M);
116 if (!IAA.tryCreate(Params, Mode, {},
117 InlineContext{LTOPhase, InlinePass::ModuleInliner})) {
118 M.getContext().emitError(
119 "Could not setup Inlining Advisor for the requested "
120 "mode and/or options");
121 return PreservedAnalyses::all();
122 }
123
124 auto &CtxProf = MAM.getResult<CtxProfAnalysis>(M);
125
126 bool Changed = false;
127
129
132
133 auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & {
135 };
136
137 InlineAdvisor &Advisor = getAdvisor(MAM, FAM, M);
138 Advisor.onPassEntry();
139
140 auto AdvisorOnExit = make_scope_exit([&] { Advisor.onPassExit(); });
141
142 // In the module inliner, a priority-based worklist is used for calls across
143 // the entire Module. With this module inliner, the inline order is not
144 // limited to bottom-up order. More globally scope inline order is enabled.
145 // Also, the inline deferral logic become unnecessary in this module inliner.
146 // It is possible to use other priority heuristics, e.g. profile-based
147 // heuristic.
148 //
149 // TODO: Here is a huge amount duplicate code between the module inliner and
150 // the SCC inliner, which need some refactoring.
151 auto Calls = getInlineOrder(FAM, Params, MAM, M);
152 assert(Calls != nullptr && "Expected an initialized InlineOrder");
153
154 // Populate the initial list of calls in this module.
156 for (Function &F : M) {
158 for (Instruction &I : instructions(F)) {
159 if (auto *CB = dyn_cast<CallBase>(&I)) {
160 if (Function *Callee = CB->getCalledFunction()) {
161 if (!Callee->isDeclaration())
162 Calls->push({CB, -1});
163 else if (!isa<IntrinsicInst>(I)) {
164 using namespace ore;
165 setInlineRemark(*CB, "unavailable definition");
166 ORE.emit([&]() {
167 return OptimizationRemarkMissed(DEBUG_TYPE, "NoDefinition", &I)
168 << NV("Callee", Callee) << " will not be inlined into "
169 << NV("Caller", CB->getCaller())
170 << " because its definition is unavailable"
171 << setIsVerbose();
172 });
173 }
174 } else if (CtxProfPromoteAlwaysInline && CtxProf &&
175 CB->isIndirectCall()) {
177 ICPCandidates);
178 }
179 }
180 }
181 }
182 for (auto &[CB, Target] : ICPCandidates) {
183 if (auto *DirectCB = promoteCallWithIfThenElse(*CB, *Target, CtxProf))
184 Calls->push({DirectCB, -1});
185 }
186 if (Calls->empty())
187 return PreservedAnalyses::all();
188
189 // When inlining a callee produces new call sites, we want to keep track of
190 // the fact that they were inlined from the callee. This allows us to avoid
191 // infinite inlining in some obscure cases. To represent this, we use an
192 // index into the InlineHistory vector.
194
195 // Track the dead functions to delete once finished with inlining calls. We
196 // defer deleting these to make it easier to handle the call graph updates.
197 SmallVector<Function *, 4> DeadFunctions;
198
199 // Loop forward over all of the calls.
200 while (!Calls->empty()) {
201 auto P = Calls->pop();
202 CallBase *CB = P.first;
203 const int InlineHistoryID = P.second;
204 Function &F = *CB->getCaller();
206
207 LLVM_DEBUG(dbgs() << "Inlining calls in: " << F.getName() << "\n"
208 << " Function size: " << F.getInstructionCount()
209 << "\n");
210 (void)F;
211
212 auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
214 };
215
216 if (InlineHistoryID != -1 &&
217 inlineHistoryIncludes(&Callee, InlineHistoryID, InlineHistory)) {
218 setInlineRemark(*CB, "recursive");
219 continue;
220 }
221
222 auto Advice = Advisor.getAdvice(*CB, /*OnlyMandatory*/ false);
223 // Check whether we want to inline this callsite.
224 if (!Advice->isInliningRecommended()) {
225 Advice->recordUnattemptedInlining();
226 continue;
227 }
228
229 // Setup the data structure used to plumb customization into the
230 // `InlineFunction` routine.
232 GetAssumptionCache, PSI,
235
237 InlineFunction(*CB, IFI, CtxProf, /*MergeAttributes=*/true,
238 &FAM.getResult<AAManager>(*CB->getCaller()));
239 if (!IR.isSuccess()) {
240 Advice->recordUnsuccessfulInlining(IR);
241 continue;
242 }
243
244 Changed = true;
245 ++NumInlined;
246
247 LLVM_DEBUG(dbgs() << " Size after inlining: " << F.getInstructionCount()
248 << "\n");
249
250 // Add any new callsites to defined functions to the worklist.
251 if (!IFI.InlinedCallSites.empty()) {
252 int NewHistoryID = InlineHistory.size();
253 InlineHistory.push_back({&Callee, InlineHistoryID});
254
255 for (CallBase *ICB : reverse(IFI.InlinedCallSites)) {
256 Function *NewCallee = ICB->getCalledFunction();
257 if (!NewCallee) {
258 // Try to promote an indirect (virtual) call without waiting for
259 // the post-inline cleanup and the next DevirtSCCRepeatedPass
260 // iteration because the next iteration may not happen and we may
261 // miss inlining it.
262 // FIXME: enable for ctxprof.
263 if (!CtxProf)
264 if (tryPromoteCall(*ICB))
265 NewCallee = ICB->getCalledFunction();
266 }
267 if (NewCallee)
268 if (!NewCallee->isDeclaration())
269 Calls->push({ICB, NewHistoryID});
270 }
271 }
272
273 // For local functions, check whether this makes the callee trivially
274 // dead. In that case, we can drop the body of the function eagerly
275 // which may reduce the number of callers of other functions to one,
276 // changing inline cost thresholds.
277 bool CalleeWasDeleted = false;
278 if (Callee.hasLocalLinkage()) {
279 // To check this we also need to nuke any dead constant uses (perhaps
280 // made dead by this operation on other functions).
281 Callee.removeDeadConstantUsers();
282 // if (Callee.use_empty() && !CG.isLibFunction(Callee)) {
283 if (Callee.use_empty() && !isKnownLibFunction(Callee, GetTLI(Callee))) {
284 Calls->erase_if([&](const std::pair<CallBase *, int> &Call) {
285 return Call.first->getCaller() == &Callee;
286 });
287 // Clear the body and queue the function itself for deletion when we
288 // finish inlining.
289 // Note that after this point, it is an error to do anything other
290 // than use the callee's address or delete it.
291 Callee.dropAllReferences();
292 assert(!is_contained(DeadFunctions, &Callee) &&
293 "Cannot put cause a function to become dead twice!");
294 DeadFunctions.push_back(&Callee);
295 CalleeWasDeleted = true;
296 }
297 }
298 if (CalleeWasDeleted)
299 Advice->recordInliningWithCalleeDeleted();
300 else
301 Advice->recordInlining();
302 }
303
304 // Now that we've finished inlining all of the calls across this module,
305 // delete all of the trivially dead functions.
306 //
307 // Note that this walks a pointer set which has non-deterministic order but
308 // that is OK as all we do is delete things and add pointers to unordered
309 // sets.
310 for (Function *DeadF : DeadFunctions) {
311 // Clear out any cached analyses.
312 FAM.clear(*DeadF, DeadF->getName());
313
314 // And delete the actual function from the module.
315 M.getFunctionList().erase(DeadF);
316
317 ++NumDeleted;
318 }
319
320 if (!Changed)
321 return PreservedAnalyses::all();
322
324}
Expand Atomic instructions
#define LLVM_DEBUG(...)
Definition: Debug.h:106
#define DEBUG_TYPE
Module.h This file contains the declarations for the Module class.
This header defines various interfaces for pass management in LLVM.
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:146
static bool isKnownLibFunction(Function &F, TargetLibraryInfo &TLI)
Legalize the Machine IR a function s Machine IR
Definition: Legalizer.cpp:80
#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...
cl::opt< bool > CtxProfPromoteAlwaysInline("ctx-prof-promote-alwaysinline", cl::init(false), cl::Hidden, cl::desc("If using a contextual profile in this module, and an indirect " "call target is marked as alwaysinline, perform indirect call " "promotion for that target. If multiple targets for an indirect " "call site fit this description, they are all promoted."))
#define P(N)
FunctionAnalysisManager FAM
ModuleAnalysisManager MAM
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:166
A manager for alias analyses.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
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:429
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:410
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:1120
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1349
Function * getCaller()
Helper to get the caller (the parent function).
static void collectIndirectCallPromotionList(CallBase &IC, Result &Profile, SetVector< std::pair< CallBase *, Function * > > &Candidates)
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:296
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:255
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:567
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:111
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: Analysis.h:114
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:117
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
Analysis providing profile information.
A vector that has set insertion semantics.
Definition: SetVector.h:57
size_t size() const
Definition: SmallVector.h:78
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:573
void push_back(const T &Elt)
Definition: SmallVector.h:413
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1196
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.
Target - Wrapper for Target specific information.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
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
CallBase & promoteCallWithIfThenElse(CallBase &CB, Function *Callee, MDNode *BranchWeights=nullptr)
Promote the given indirect call site to conditionally call Callee.
void setInlineRemark(CallBase &CB, StringRef Message)
Set the inline-remark attribute.
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:420
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:1903
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:58