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
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.
53static 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
66InlineAdvisor &ModuleInlinerPass::getAdvisor(const ModuleAnalysisManager &MAM,
67 FunctionAnalysisManager &FAM,
68 Module &M) {
69 if (OwnedAdvisor)
70 return *OwnedAdvisor;
71
72 auto *IAA = MAM.getCachedResult<InlineAdvisorAnalysis>(IR&: 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 args&: M, args&: FAM, args: Params, args: InlineContext{.LTOPhase: LTOPhase, .Pass: 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
93static 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(FDecl: F, F&: LF) ||
100 TLI.isKnownVectorFunctionInLibrary(F: F.getName());
101}
102
103PreservedAnalyses ModuleInlinerPass::run(Module &M,
104 ModuleAnalysisManager &MAM) {
105 LLVM_DEBUG(dbgs() << "---- Module Inliner is Running ---- \n");
106
107 auto &IAA = MAM.getResult<InlineAdvisorAnalysis>(IR&: M);
108 if (!IAA.tryCreate(Params, Mode, ReplaySettings: {},
109 IC: InlineContext{.LTOPhase: LTOPhase, .Pass: InlinePass::ModuleInliner})) {
110 M.getContext().emitError(
111 ErrorStr: "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>(IR&: M);
119
120 FunctionAnalysisManager &FAM =
121 MAM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
122
123 auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & {
124 return FAM.getResult<TargetLibraryAnalysis>(IR&: F);
125 };
126
127 InlineAdvisor &Advisor = getAdvisor(MAM, FAM, M);
128 Advisor.onPassEntry();
129
130 auto AdvisorOnExit = make_scope_exit(F: [&] { 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) {
146 auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: F);
147 for (Instruction &I : instructions(F))
148 if (auto *CB = dyn_cast<CallBase>(Val: &I))
149 if (Function *Callee = CB->getCalledFunction()) {
150 if (!Callee->isDeclaration())
151 Calls->push(Elt: {CB, -1});
152 else if (!isa<IntrinsicInst>(Val: I)) {
153 using namespace ore;
154 setInlineRemark(CB&: *CB, Message: "unavailable definition");
155 ORE.emit(RemarkBuilder: [&]() {
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.
172 SmallVector<std::pair<Function *, int>, 16> InlineHistory;
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 & {
192 return FAM.getResult<AssumptionAnalysis>(IR&: F);
193 };
194
195 if (InlineHistoryID != -1 &&
196 inlineHistoryIncludes(F: &Callee, InlineHistoryID, InlineHistory)) {
197 setInlineRemark(CB&: *CB, Message: "recursive");
198 continue;
199 }
200
201 auto Advice = Advisor.getAdvice(CB&: *CB, /*OnlyMandatory*/ MandatoryOnly: 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.
210 InlineFunctionInfo IFI(
211 GetAssumptionCache, PSI,
212 &FAM.getResult<BlockFrequencyAnalysis>(IR&: *(CB->getCaller())),
213 &FAM.getResult<BlockFrequencyAnalysis>(IR&: Callee));
214
215 InlineResult IR =
216 InlineFunction(CB&: *CB, IFI, /*MergeAttributes=*/true,
217 CalleeAAR: &FAM.getResult<AAManager>(IR&: *CB->getCaller()));
218 if (!IR.isSuccess()) {
219 Advice->recordUnsuccessfulInlining(Result: 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(Elt: {&Callee, InlineHistoryID});
233
234 for (CallBase *ICB : reverse(C&: 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(CB&: *ICB))
242 NewCallee = ICB->getCalledFunction();
243 }
244 if (NewCallee)
245 if (!NewCallee->isDeclaration())
246 Calls->push(Elt: {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(F&: Callee, TLI&: GetTLI(Callee))) {
261 Calls->erase_if(Pred: [&](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(Elt: &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(IR&: *DeadF, Name: DeadF->getName());
290
291 // And delete the actual function from the module.
292 M.getFunctionList().erase(IT: DeadF);
293
294 ++NumDeleted;
295 }
296
297 if (!Changed)
298 return PreservedAnalyses::all();
299
300 return PreservedAnalyses::none();
301}
302