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
16 #include "llvm/Transforms/IPO/ModuleInliner.h"
17 #include "llvm/ADT/ScopeExit.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/Analysis/AliasAnalysis.h"
21 #include "llvm/Analysis/AssumptionCache.h"
22 #include "llvm/Analysis/BlockFrequencyInfo.h"
23 #include "llvm/Analysis/InlineAdvisor.h"
24 #include "llvm/Analysis/InlineCost.h"
25 #include "llvm/Analysis/InlineOrder.h"
26 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
27 #include "llvm/Analysis/ProfileSummaryInfo.h"
28 #include "llvm/Analysis/ReplayInlineAdvisor.h"
29 #include "llvm/Analysis/TargetLibraryInfo.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"
37 #include "llvm/Support/CommandLine.h"
38 #include "llvm/Support/Debug.h"
39 #include "llvm/Support/raw_ostream.h"
40 #include "llvm/Transforms/Utils/CallPromotionUtils.h"
41 #include "llvm/Transforms/Utils/Cloning.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.
inlineHistoryIncludes(Function * F,int InlineHistoryID,const SmallVectorImpl<std::pair<Function *,int>> & InlineHistory)53 static bool inlineHistoryIncludes(
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
getAdvisor(const ModuleAnalysisManager & MAM,FunctionAnalysisManager & FAM,Module & M)66 InlineAdvisor &ModuleInlinerPass::getAdvisor(const ModuleAnalysisManager &MAM,
67 FunctionAnalysisManager &FAM,
68 Module &M) {
69 if (OwnedAdvisor)
70 return *OwnedAdvisor;
71
72 auto *IAA = MAM.getCachedResult<InlineAdvisorAnalysis>(M);
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
isKnownLibFunction(Function & F,TargetLibraryInfo & TLI)93 static bool isKnownLibFunction(Function &F, TargetLibraryInfo &TLI) {
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
run(Module & M,ModuleAnalysisManager & MAM)103 PreservedAnalyses ModuleInlinerPass::run(Module &M,
104 ModuleAnalysisManager &MAM) {
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
118 ProfileSummaryInfo *PSI = MAM.getCachedResult<ProfileSummaryAnalysis>(M);
119
120 FunctionAnalysisManager &FAM =
121 MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
122
123 auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & {
124 return FAM.getResult<TargetLibraryAnalysis>(F);
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) {
146 auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
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();
189 Function &Callee = *CB->getCalledFunction();
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 & {
197 return FAM.getResult<AssumptionAnalysis>(F);
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,
217 &FAM.getResult<BlockFrequencyAnalysis>(*(CB->getCaller())),
218 &FAM.getResult<BlockFrequencyAnalysis>(Callee));
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 }
307