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 "IPOOptions.h"
18#include "llvm/ADT/ScopeExit.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/ADT/Statistic.h"
21#include "llvm/Analysis/AliasAnalysis.h"
22#include "llvm/Analysis/AssumptionCache.h"
23#include "llvm/Analysis/BlockFrequencyInfo.h"
24#include "llvm/Analysis/CtxProfAnalysis.h"
25#include "llvm/Analysis/InlineAdvisor.h"
26#include "llvm/Analysis/InlineCost.h"
27#include "llvm/Analysis/InlineOrder.h"
28#include "llvm/Analysis/OptimizationRemarkEmitter.h"
29#include "llvm/Analysis/ProfileSummaryInfo.h"
30#include "llvm/Analysis/ReplayInlineAdvisor.h"
31#include "llvm/Analysis/TargetLibraryInfo.h"
32#include "llvm/IR/DiagnosticInfo.h"
33#include "llvm/IR/Function.h"
34#include "llvm/IR/InstIterator.h"
35#include "llvm/IR/Instruction.h"
36#include "llvm/IR/IntrinsicInst.h"
37#include "llvm/IR/Module.h"
38#include "llvm/IR/PassManager.h"
39#include "llvm/Support/Debug.h"
40#include "llvm/Support/raw_ostream.h"
41#include "llvm/Transforms/Utils/CallPromotionUtils.h"
42#include "llvm/Transforms/Utils/Cloning.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
52InlineAdvisor &ModuleInlinerPass::getAdvisor(const ModuleAnalysisManager &MAM,
53 FunctionAnalysisManager &FAM,
54 Module &M) {
55 if (OwnedAdvisor)
56 return *OwnedAdvisor;
57
58 auto *IAA = MAM.getCachedResult<InlineAdvisorAnalysis>(IR&: M);
59 if (!IAA) {
60 // It should still be possible to run the inliner as a stand-alone module
61 // pass, for test scenarios. In that case, we default to the
62 // DefaultInlineAdvisor, which doesn't need to keep state between module
63 // pass runs. It also uses just the default InlineParams. In this case, we
64 // need to use the provided FAM, which is valid for the duration of the
65 // inliner pass, and thus the lifetime of the owned advisor. The one we
66 // would get from the MAM can be invalidated as a result of the inliner's
67 // activity.
68 OwnedAdvisor = std::make_unique<DefaultInlineAdvisor>(
69 args&: M, args&: FAM, args: Params, args: InlineContext{.LTOPhase: LTOPhase, .Pass: InlinePass::ModuleInliner});
70
71 return *OwnedAdvisor;
72 }
73 assert(IAA->getAdvisor() &&
74 "Expected a present InlineAdvisorAnalysis also have an "
75 "InlineAdvisor initialized");
76 return *IAA->getAdvisor();
77}
78
79static bool isKnownLibFunction(Function &F, TargetLibraryInfo &TLI) {
80 // Either this is a normal library function or a "vectorizable"
81 // function. Not using the VFDatabase here because this query
82 // is related only to libraries handled via the TLI.
83 return TLI.getLibFunc(FDecl: F) != NotLibFunc ||
84 TLI.isKnownVectorFunctionInLibrary(F: F.getName());
85}
86
87PreservedAnalyses ModuleInlinerPass::run(Module &M,
88 ModuleAnalysisManager &MAM) {
89 const IPOOptions &Opts = getIPOOptions(M);
90 LLVM_DEBUG(dbgs() << "---- Module Inliner is Running ---- \n");
91
92 auto &IAA = MAM.getResult<InlineAdvisorAnalysis>(IR&: M);
93 if (!IAA.tryCreate(Params, Mode, ReplaySettings: {},
94 IC: InlineContext{.LTOPhase: LTOPhase, .Pass: InlinePass::ModuleInliner})) {
95 M.getContext().emitError(
96 ErrorStr: "Could not setup Inlining Advisor for the requested "
97 "mode and/or options");
98 return PreservedAnalyses::all();
99 }
100
101 auto &CtxProf = MAM.getResult<CtxProfAnalysis>(IR&: M);
102
103 bool Changed = false;
104
105 ProfileSummaryInfo *PSI = MAM.getCachedResult<ProfileSummaryAnalysis>(IR&: M);
106
107 FunctionAnalysisManager &FAM =
108 MAM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
109
110 auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & {
111 return FAM.getResult<TargetLibraryAnalysis>(IR&: F);
112 };
113
114 InlineAdvisor &Advisor = getAdvisor(MAM, FAM, M);
115 Advisor.onPassEntry();
116
117 llvm::scope_exit AdvisorOnExit([&] { Advisor.onPassExit(); });
118
119 // In the module inliner, a priority-based worklist is used for calls across
120 // the entire Module. With this module inliner, the inline order is not
121 // limited to bottom-up order. More globally scope inline order is enabled.
122 // Also, the inline deferral logic become unnecessary in this module inliner.
123 // It is possible to use other priority heuristics, e.g. profile-based
124 // heuristic.
125 //
126 // TODO: Here is a huge amount duplicate code between the module inliner and
127 // the SCC inliner, which need some refactoring.
128 auto Calls = getInlineOrder(FAM, Params, MAM, M);
129 assert(Calls != nullptr && "Expected an initialized InlineOrder");
130
131 // Populate the initial list of calls in this module.
132 SetVector<std::pair<CallBase *, Function *>> ICPCandidates;
133 for (Function &F : M) {
134 if (F.isDeclaration())
135 continue;
136 auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: F);
137 for (Instruction &I : instructions(F)) {
138 if (auto *CB = dyn_cast<CallBase>(Val: &I)) {
139 if (Function *Callee = CB->getCalledFunction()) {
140 if (!Callee->isDeclaration())
141 Calls->push(Elt: CB);
142 else if (!isa<IntrinsicInst>(Val: I)) {
143 using namespace ore;
144 setInlineRemark(CB&: *CB, Message: "unavailable definition");
145 ORE.emit(RemarkBuilder: [&]() {
146 return OptimizationRemarkMissed(DEBUG_TYPE, "NoDefinition", &I)
147 << NV("Callee", Callee) << " will not be inlined into "
148 << NV("Caller", CB->getCaller())
149 << " because its definition is unavailable"
150 << setIsVerbose();
151 });
152 }
153 } else if (Opts.ctx_prof_promote_alwaysinline &&
154 CtxProf.isInSpecializedModule() && CB->isIndirectCall()) {
155 CtxProfAnalysis::collectIndirectCallPromotionList(IC&: *CB, Profile&: CtxProf,
156 Candidates&: ICPCandidates);
157 }
158 }
159 }
160 }
161 for (auto &[CB, Target] : ICPCandidates) {
162 if (auto *DirectCB = promoteCallWithIfThenElse(CB&: *CB, Callee&: *Target, CtxProf))
163 Calls->push(Elt: DirectCB);
164 }
165 if (Calls->empty())
166 return PreservedAnalyses::all();
167
168 // Track the dead functions to delete once finished with inlining calls. We
169 // defer deleting these to make it easier to handle the call graph updates.
170 SmallVector<Function *, 4> DeadFunctions;
171
172 // Loop forward over all of the calls.
173 while (!Calls->empty()) {
174 CallBase *CB = Calls->pop();
175 Function &F = *CB->getCaller();
176 Function &Callee = *CB->getCalledFunction();
177
178 LLVM_DEBUG(dbgs() << "Inlining calls in: " << F.getName() << "\n"
179 << " Function size: " << F.getInstructionCount()
180 << "\n");
181 (void)F;
182
183 auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
184 return FAM.getResult<AssumptionAnalysis>(IR&: F);
185 };
186
187 auto Advice = Advisor.getAdvice(CB&: *CB, /*OnlyMandatory*/ MandatoryOnly: false);
188 // Check whether we want to inline this callsite.
189 if (!Advice->isInliningRecommended()) {
190 Advice->recordUnattemptedInlining();
191 continue;
192 }
193
194 // Setup the data structure used to plumb customization into the
195 // `InlineFunction` routine.
196 InlineFunctionInfo IFI(
197 GetAssumptionCache, PSI,
198 &FAM.getResult<BlockFrequencyAnalysis>(IR&: *(CB->getCaller())),
199 &FAM.getResult<BlockFrequencyAnalysis>(IR&: Callee));
200
201 InlineResult IR =
202 InlineFunction(CB&: *CB, IFI, CtxProf, /*MergeAttributes=*/true,
203 CalleeAAR: &FAM.getResult<AAManager>(IR&: *CB->getCaller()),
204 /*InsertLifetime=*/true,
205 /*TrackInlineHistory=*/true);
206 if (!IR.isSuccess()) {
207 Advice->recordUnsuccessfulInlining(Result: IR);
208 continue;
209 }
210
211 Changed = true;
212 ++NumInlined;
213
214 LLVM_DEBUG(dbgs() << " Size after inlining: " << F.getInstructionCount()
215 << "\n");
216
217 // Add any new callsites to defined functions to the worklist.
218 if (!IFI.InlinedCallSites.empty()) {
219 for (CallBase *ICB : reverse(C&: IFI.InlinedCallSites)) {
220 Function *NewCallee = ICB->getCalledFunction();
221 if (!NewCallee) {
222 // Try to promote an indirect (virtual) call without waiting for
223 // the post-inline cleanup and the next DevirtSCCRepeatedPass
224 // iteration because the next iteration may not happen and we may
225 // miss inlining it.
226 // FIXME: enable for ctxprof.
227 if (CtxProf.isInSpecializedModule())
228 if (tryPromoteCall(CB&: *ICB))
229 NewCallee = ICB->getCalledFunction();
230 }
231 if (NewCallee)
232 if (!NewCallee->isDeclaration())
233 Calls->push(Elt: ICB);
234 }
235 }
236
237 // For local functions, check whether this makes the callee trivially
238 // dead. In that case, we can drop the body of the function eagerly
239 // which may reduce the number of callers of other functions to one,
240 // changing inline cost thresholds.
241 bool CalleeWasDeleted = false;
242 if (Callee.hasLocalLinkage()) {
243 // To check this we also need to nuke any dead constant uses (perhaps
244 // made dead by this operation on other functions).
245 Callee.removeDeadConstantUsers();
246 // if (Callee.use_empty() && !CG.isLibFunction(Callee)) {
247 if (Callee.use_empty() && !isKnownLibFunction(F&: Callee, TLI&: GetTLI(Callee))) {
248 Calls->erase_if(
249 Pred: [&](const CallBase *CB) { return CB->getCaller() == &Callee; });
250
251 // Report inlining decision BEFORE deleting function contents, so we
252 // can still access e.g. the DebugLoc
253 Advice->recordInliningWithCalleeDeleted();
254 // Clear the body and queue the function itself for deletion when we
255 // finish inlining.
256 // Note that after this point, it is an error to do anything other
257 // than use the callee's address or delete it.
258 Callee.dropAllReferences();
259 assert(!is_contained(DeadFunctions, &Callee) &&
260 "Cannot put cause a function to become dead twice!");
261 DeadFunctions.push_back(Elt: &Callee);
262 CalleeWasDeleted = true;
263 }
264 }
265 if (!CalleeWasDeleted)
266 Advice->recordInlining();
267 }
268
269 // Now that we've finished inlining all of the calls across this module,
270 // delete all of the trivially dead functions.
271 //
272 // Note that this walks a pointer set which has non-deterministic order but
273 // that is OK as all we do is delete things and add pointers to unordered
274 // sets.
275 for (Function *DeadF : DeadFunctions) {
276 // Clear out any cached analyses.
277 FAM.clear(IR&: *DeadF, Name: DeadF->getName());
278
279 // And delete the actual function from the module.
280 M.getFunctionList().erase(IT: DeadF);
281
282 ++NumDeleted;
283 }
284
285 if (!Changed)
286 return PreservedAnalyses::all();
287
288 return PreservedAnalyses::none();
289}
290