LLVM  16.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"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/Statistic.h"
30 #include "llvm/IR/DiagnosticInfo.h"
31 #include "llvm/IR/Function.h"
32 #include "llvm/IR/InstIterator.h"
33 #include "llvm/IR/Instruction.h"
34 #include "llvm/IR/IntrinsicInst.h"
35 #include "llvm/IR/Module.h"
36 #include "llvm/IR/PassManager.h"
38 #include "llvm/Support/Debug.h"
42 #include <cassert>
43 
44 using namespace llvm;
45 
46 #define DEBUG_TYPE "module-inline"
47 
48 STATISTIC(NumInlined, "Number of functions inlined");
49 STATISTIC(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 
66 InlineAdvisor &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);
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.
177  SmallVector<std::pair<Function *, int>, 16> InlineHistory;
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.
215  InlineFunctionInfo IFI(
216  /*cg=*/nullptr, GetAssumptionCache, PSI,
219 
220  InlineResult IR =
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 
305  return PreservedAnalyses::none();
306 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::InlineAdvisor::onPassEntry
virtual void onPassEntry(LazyCallGraph::SCC *SCC=nullptr)
This must be called when the Inliner pass is entered, to allow the InlineAdvisor update internal stat...
Definition: InlineAdvisor.h:184
isKnownLibFunction
static bool isKnownLibFunction(Function &F, TargetLibraryInfo &TLI)
Definition: ModuleInliner.cpp:93
AssumptionCache.h
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:876
llvm::OptimizationRemarkMissed
Diagnostic information for missed-optimization remarks.
Definition: DiagnosticInfo.h:734
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
IntrinsicInst.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
InstIterator.h
llvm::Function
Definition: Function.h:60
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::InlineFunction
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.
Definition: InlineFunction.cpp:2046
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
Statistic.h
OptimizationRemarkEmitter.h
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
llvm::PreservedAnalyses::none
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:155
Module.h
llvm::ore::NV
DiagnosticInfoOptimizationBase::Argument NV
Definition: OptimizationRemarkEmitter.h:136
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
AliasAnalysis.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Instruction.h
CommandLine.h
llvm::GlobalValue::isDeclaration
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:271
llvm::InlineAdvisor::onPassExit
virtual void onPassExit(LazyCallGraph::SCC *SCC=nullptr)
This must be called when the Inliner pass is exited, as function passes may be run subsequently.
Definition: InlineAdvisor.h:189
llvm::LibFunc
LibFunc
Definition: TargetLibraryInfo.h:35
llvm::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1396
MAM
ModuleAnalysisManager MAM
Definition: PassBuilderBindings.cpp:61
llvm::AnalysisManager::clear
void clear(IRUnitT &IR, llvm::StringRef Name)
Clear any cached analysis results for a single unit of IR.
Definition: PassManagerImpl.h:36
TargetLibraryInfo.h
InlineAdvisor.h
llvm::TargetLibraryInfo::getLibFunc
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
Definition: TargetLibraryInfo.h:297
llvm::Instruction
Definition: Instruction.h:42
InlineOrder.h
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
IR
Statically lint checks LLVM IR
Definition: Lint.cpp:746
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:155
llvm::InlineContext
Provides context on when an inline advisor is constructed in the pipeline (e.g., link phase,...
Definition: InlineAdvisor.h:58
llvm::BlockFrequencyAnalysis
Analysis pass which computes BlockFrequencyInfo.
Definition: BlockFrequencyInfo.h:112
llvm::CallBase::getCaller
Function * getCaller()
Helper to get the caller (the parent function).
Definition: Instructions.cpp:284
llvm::ProfileSummaryInfo
Analysis providing profile information.
Definition: ProfileSummaryInfo.h:39
llvm::ModuleInlinerPass::run
PreservedAnalyses run(Module &, ModuleAnalysisManager &)
Definition: ModuleInliner.cpp:103
ReplayInlineAdvisor.h
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::getInlineOrder
std::unique_ptr< InlineOrder< std::pair< CallBase *, int > > > getInlineOrder(FunctionAnalysisManager &FAM, const InlineParams &Params)
Definition: InlineOrder.cpp:263
ProfileSummaryInfo.h
ModuleInliner.h
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:173
I
#define I(x, y, z)
Definition: MD5.cpp:58
Cloning.h
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1843
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::setInlineRemark
void setInlineRemark(CallBase &CB, StringRef Message)
Set the inline-remark attribute.
Definition: InlineAdvisor.cpp:357
InlineCost.h
llvm::TargetLibraryInfo::isKnownVectorFunctionInLibrary
bool isKnownVectorFunctionInLibrary(StringRef F) const
Check if the function "F" is listed in a library known to LLVM.
Definition: TargetLibraryInfo.h:440
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::ProfileSummaryAnalysis
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
Definition: ProfileSummaryInfo.h:211
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm::InlineAdvisor
Interface for deciding whether to inline a call site or not.
Definition: InlineAdvisor.h:163
CallPromotionUtils.h
BlockFrequencyInfo.h
llvm::make_scope_exit
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:59
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:187
llvm::InlinePass::ModuleInliner
@ ModuleInliner
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::AnalysisManager::getCachedResult
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:793
DiagnosticInfo.h
Function.h
PassManager.h
DEBUG_TYPE
#define DEBUG_TYPE
Definition: ModuleInliner.cpp:46
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:225
llvm::InlineFunctionInfo
This class captures the data input to the InlineFunction call, and records the auxiliary results prod...
Definition: Cloning.h:203
inlineHistoryIncludes
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: ModuleInliner.cpp:53
llvm::InlineAdvisorAnalysis
The InlineAdvisorAnalysis is a module pass because the InlineAdvisor needs to capture state right bef...
Definition: InlineAdvisor.h:243
SmallVector.h
ScopeExit.h
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:485
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1174
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::InnerAnalysisManagerProxy
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:931
raw_ostream.h
llvm::OptimizationRemarkEmitterAnalysis
Definition: OptimizationRemarkEmitter.h:164
llvm::InlineResult
InlineResult is basically true or false.
Definition: InlineCost.h:177
Debug.h
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:449
llvm::tryPromoteCall
bool tryPromoteCall(CallBase &CB)
Try to promote (devirtualize) a virtual call on an Alloca.
Definition: CallPromotionUtils.cpp:549
llvm::ore::setIsVerbose
DiagnosticInfoOptimizationBase::setIsVerbose setIsVerbose
Definition: OptimizationRemarkEmitter.h:137