1349cc55cSDimitry Andric //===- ModuleInliner.cpp - Code related to module inliner -----------------===//
2349cc55cSDimitry Andric //
3349cc55cSDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4349cc55cSDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
5349cc55cSDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6349cc55cSDimitry Andric //
7349cc55cSDimitry Andric //===----------------------------------------------------------------------===//
8349cc55cSDimitry Andric //
9349cc55cSDimitry Andric // This file implements the mechanics required to implement inlining without
10349cc55cSDimitry Andric // missing any calls in the module level. It doesn't need any infromation about
11349cc55cSDimitry Andric // SCC or call graph, which is different from the SCC inliner. The decisions of
12349cc55cSDimitry Andric // which calls are profitable to inline are implemented elsewhere.
13349cc55cSDimitry Andric //
14349cc55cSDimitry Andric //===----------------------------------------------------------------------===//
15349cc55cSDimitry Andric
16349cc55cSDimitry Andric #include "llvm/Transforms/IPO/ModuleInliner.h"
17349cc55cSDimitry Andric #include "llvm/ADT/ScopeExit.h"
18349cc55cSDimitry Andric #include "llvm/ADT/SmallVector.h"
19349cc55cSDimitry Andric #include "llvm/ADT/Statistic.h"
2081ad6265SDimitry Andric #include "llvm/Analysis/AliasAnalysis.h"
21349cc55cSDimitry Andric #include "llvm/Analysis/AssumptionCache.h"
22349cc55cSDimitry Andric #include "llvm/Analysis/BlockFrequencyInfo.h"
23349cc55cSDimitry Andric #include "llvm/Analysis/InlineAdvisor.h"
24349cc55cSDimitry Andric #include "llvm/Analysis/InlineCost.h"
25349cc55cSDimitry Andric #include "llvm/Analysis/InlineOrder.h"
26349cc55cSDimitry Andric #include "llvm/Analysis/OptimizationRemarkEmitter.h"
27349cc55cSDimitry Andric #include "llvm/Analysis/ProfileSummaryInfo.h"
2881ad6265SDimitry Andric #include "llvm/Analysis/ReplayInlineAdvisor.h"
29349cc55cSDimitry Andric #include "llvm/Analysis/TargetLibraryInfo.h"
30349cc55cSDimitry Andric #include "llvm/IR/DiagnosticInfo.h"
31349cc55cSDimitry Andric #include "llvm/IR/Function.h"
32349cc55cSDimitry Andric #include "llvm/IR/InstIterator.h"
33349cc55cSDimitry Andric #include "llvm/IR/Instruction.h"
34349cc55cSDimitry Andric #include "llvm/IR/IntrinsicInst.h"
35349cc55cSDimitry Andric #include "llvm/IR/Module.h"
36349cc55cSDimitry Andric #include "llvm/IR/PassManager.h"
37349cc55cSDimitry Andric #include "llvm/Support/CommandLine.h"
38349cc55cSDimitry Andric #include "llvm/Support/Debug.h"
39349cc55cSDimitry Andric #include "llvm/Support/raw_ostream.h"
40349cc55cSDimitry Andric #include "llvm/Transforms/Utils/CallPromotionUtils.h"
41349cc55cSDimitry Andric #include "llvm/Transforms/Utils/Cloning.h"
42349cc55cSDimitry Andric #include <cassert>
43349cc55cSDimitry Andric
44349cc55cSDimitry Andric using namespace llvm;
45349cc55cSDimitry Andric
46349cc55cSDimitry Andric #define DEBUG_TYPE "module-inline"
47349cc55cSDimitry Andric
48349cc55cSDimitry Andric STATISTIC(NumInlined, "Number of functions inlined");
49349cc55cSDimitry Andric STATISTIC(NumDeleted, "Number of functions deleted because all callers found");
50349cc55cSDimitry Andric
51349cc55cSDimitry Andric /// Return true if the specified inline history ID
52349cc55cSDimitry Andric /// indicates an inline history that includes the specified function.
inlineHistoryIncludes(Function * F,int InlineHistoryID,const SmallVectorImpl<std::pair<Function *,int>> & InlineHistory)53349cc55cSDimitry Andric static bool inlineHistoryIncludes(
54349cc55cSDimitry Andric Function *F, int InlineHistoryID,
55349cc55cSDimitry Andric const SmallVectorImpl<std::pair<Function *, int>> &InlineHistory) {
56349cc55cSDimitry Andric while (InlineHistoryID != -1) {
57349cc55cSDimitry Andric assert(unsigned(InlineHistoryID) < InlineHistory.size() &&
58349cc55cSDimitry Andric "Invalid inline history ID");
59349cc55cSDimitry Andric if (InlineHistory[InlineHistoryID].first == F)
60349cc55cSDimitry Andric return true;
61349cc55cSDimitry Andric InlineHistoryID = InlineHistory[InlineHistoryID].second;
62349cc55cSDimitry Andric }
63349cc55cSDimitry Andric return false;
64349cc55cSDimitry Andric }
65349cc55cSDimitry Andric
getAdvisor(const ModuleAnalysisManager & MAM,FunctionAnalysisManager & FAM,Module & M)66349cc55cSDimitry Andric InlineAdvisor &ModuleInlinerPass::getAdvisor(const ModuleAnalysisManager &MAM,
67349cc55cSDimitry Andric FunctionAnalysisManager &FAM,
68349cc55cSDimitry Andric Module &M) {
69349cc55cSDimitry Andric if (OwnedAdvisor)
70349cc55cSDimitry Andric return *OwnedAdvisor;
71349cc55cSDimitry Andric
72349cc55cSDimitry Andric auto *IAA = MAM.getCachedResult<InlineAdvisorAnalysis>(M);
73349cc55cSDimitry Andric if (!IAA) {
74349cc55cSDimitry Andric // It should still be possible to run the inliner as a stand-alone module
75349cc55cSDimitry Andric // pass, for test scenarios. In that case, we default to the
76349cc55cSDimitry Andric // DefaultInlineAdvisor, which doesn't need to keep state between module
77349cc55cSDimitry Andric // pass runs. It also uses just the default InlineParams. In this case, we
78349cc55cSDimitry Andric // need to use the provided FAM, which is valid for the duration of the
79349cc55cSDimitry Andric // inliner pass, and thus the lifetime of the owned advisor. The one we
80349cc55cSDimitry Andric // would get from the MAM can be invalidated as a result of the inliner's
81349cc55cSDimitry Andric // activity.
8281ad6265SDimitry Andric OwnedAdvisor = std::make_unique<DefaultInlineAdvisor>(
83bdd1243dSDimitry Andric M, FAM, Params, InlineContext{LTOPhase, InlinePass::ModuleInliner});
84349cc55cSDimitry Andric
85349cc55cSDimitry Andric return *OwnedAdvisor;
86349cc55cSDimitry Andric }
87349cc55cSDimitry Andric assert(IAA->getAdvisor() &&
88349cc55cSDimitry Andric "Expected a present InlineAdvisorAnalysis also have an "
89349cc55cSDimitry Andric "InlineAdvisor initialized");
90349cc55cSDimitry Andric return *IAA->getAdvisor();
91349cc55cSDimitry Andric }
92349cc55cSDimitry Andric
isKnownLibFunction(Function & F,TargetLibraryInfo & TLI)93349cc55cSDimitry Andric static bool isKnownLibFunction(Function &F, TargetLibraryInfo &TLI) {
94349cc55cSDimitry Andric LibFunc LF;
95349cc55cSDimitry Andric
96349cc55cSDimitry Andric // Either this is a normal library function or a "vectorizable"
97349cc55cSDimitry Andric // function. Not using the VFDatabase here because this query
98349cc55cSDimitry Andric // is related only to libraries handled via the TLI.
99349cc55cSDimitry Andric return TLI.getLibFunc(F, LF) ||
100349cc55cSDimitry Andric TLI.isKnownVectorFunctionInLibrary(F.getName());
101349cc55cSDimitry Andric }
102349cc55cSDimitry Andric
run(Module & M,ModuleAnalysisManager & MAM)103349cc55cSDimitry Andric PreservedAnalyses ModuleInlinerPass::run(Module &M,
104349cc55cSDimitry Andric ModuleAnalysisManager &MAM) {
105349cc55cSDimitry Andric LLVM_DEBUG(dbgs() << "---- Module Inliner is Running ---- \n");
106349cc55cSDimitry Andric
107349cc55cSDimitry Andric auto &IAA = MAM.getResult<InlineAdvisorAnalysis>(M);
108bdd1243dSDimitry Andric if (!IAA.tryCreate(Params, Mode, {},
10981ad6265SDimitry Andric InlineContext{LTOPhase, InlinePass::ModuleInliner})) {
110349cc55cSDimitry Andric M.getContext().emitError(
111349cc55cSDimitry Andric "Could not setup Inlining Advisor for the requested "
112349cc55cSDimitry Andric "mode and/or options");
113349cc55cSDimitry Andric return PreservedAnalyses::all();
114349cc55cSDimitry Andric }
115349cc55cSDimitry Andric
116349cc55cSDimitry Andric bool Changed = false;
117349cc55cSDimitry Andric
118349cc55cSDimitry Andric ProfileSummaryInfo *PSI = MAM.getCachedResult<ProfileSummaryAnalysis>(M);
119349cc55cSDimitry Andric
120349cc55cSDimitry Andric FunctionAnalysisManager &FAM =
121349cc55cSDimitry Andric MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
122349cc55cSDimitry Andric
123349cc55cSDimitry Andric auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & {
124349cc55cSDimitry Andric return FAM.getResult<TargetLibraryAnalysis>(F);
125349cc55cSDimitry Andric };
126349cc55cSDimitry Andric
127349cc55cSDimitry Andric InlineAdvisor &Advisor = getAdvisor(MAM, FAM, M);
128349cc55cSDimitry Andric Advisor.onPassEntry();
129349cc55cSDimitry Andric
130349cc55cSDimitry Andric auto AdvisorOnExit = make_scope_exit([&] { Advisor.onPassExit(); });
131349cc55cSDimitry Andric
132349cc55cSDimitry Andric // In the module inliner, a priority-based worklist is used for calls across
133349cc55cSDimitry Andric // the entire Module. With this module inliner, the inline order is not
134349cc55cSDimitry Andric // limited to bottom-up order. More globally scope inline order is enabled.
135349cc55cSDimitry Andric // Also, the inline deferral logic become unnecessary in this module inliner.
136349cc55cSDimitry Andric // It is possible to use other priority heuristics, e.g. profile-based
137349cc55cSDimitry Andric // heuristic.
138349cc55cSDimitry Andric //
139349cc55cSDimitry Andric // TODO: Here is a huge amount duplicate code between the module inliner and
140349cc55cSDimitry Andric // the SCC inliner, which need some refactoring.
141*06c3fb27SDimitry Andric auto Calls = getInlineOrder(FAM, Params, MAM, M);
142349cc55cSDimitry Andric assert(Calls != nullptr && "Expected an initialized InlineOrder");
143349cc55cSDimitry Andric
144349cc55cSDimitry Andric // Populate the initial list of calls in this module.
145349cc55cSDimitry Andric for (Function &F : M) {
146349cc55cSDimitry Andric auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
147349cc55cSDimitry Andric for (Instruction &I : instructions(F))
148349cc55cSDimitry Andric if (auto *CB = dyn_cast<CallBase>(&I))
149349cc55cSDimitry Andric if (Function *Callee = CB->getCalledFunction()) {
150349cc55cSDimitry Andric if (!Callee->isDeclaration())
151349cc55cSDimitry Andric Calls->push({CB, -1});
152349cc55cSDimitry Andric else if (!isa<IntrinsicInst>(I)) {
153349cc55cSDimitry Andric using namespace ore;
154349cc55cSDimitry Andric setInlineRemark(*CB, "unavailable definition");
155349cc55cSDimitry Andric ORE.emit([&]() {
156349cc55cSDimitry Andric return OptimizationRemarkMissed(DEBUG_TYPE, "NoDefinition", &I)
157349cc55cSDimitry Andric << NV("Callee", Callee) << " will not be inlined into "
158349cc55cSDimitry Andric << NV("Caller", CB->getCaller())
159349cc55cSDimitry Andric << " because its definition is unavailable"
160349cc55cSDimitry Andric << setIsVerbose();
161349cc55cSDimitry Andric });
162349cc55cSDimitry Andric }
163349cc55cSDimitry Andric }
164349cc55cSDimitry Andric }
165349cc55cSDimitry Andric if (Calls->empty())
166349cc55cSDimitry Andric return PreservedAnalyses::all();
167349cc55cSDimitry Andric
168349cc55cSDimitry Andric // When inlining a callee produces new call sites, we want to keep track of
169349cc55cSDimitry Andric // the fact that they were inlined from the callee. This allows us to avoid
170349cc55cSDimitry Andric // infinite inlining in some obscure cases. To represent this, we use an
171349cc55cSDimitry Andric // index into the InlineHistory vector.
172349cc55cSDimitry Andric SmallVector<std::pair<Function *, int>, 16> InlineHistory;
173349cc55cSDimitry Andric
174349cc55cSDimitry Andric // Track the dead functions to delete once finished with inlining calls. We
175349cc55cSDimitry Andric // defer deleting these to make it easier to handle the call graph updates.
176349cc55cSDimitry Andric SmallVector<Function *, 4> DeadFunctions;
177349cc55cSDimitry Andric
178349cc55cSDimitry Andric // Loop forward over all of the calls.
179349cc55cSDimitry Andric while (!Calls->empty()) {
180bdd1243dSDimitry Andric auto P = Calls->pop();
181bdd1243dSDimitry Andric CallBase *CB = P.first;
182bdd1243dSDimitry Andric const int InlineHistoryID = P.second;
183bdd1243dSDimitry Andric Function &F = *CB->getCaller();
184bdd1243dSDimitry Andric Function &Callee = *CB->getCalledFunction();
185349cc55cSDimitry Andric
186349cc55cSDimitry Andric LLVM_DEBUG(dbgs() << "Inlining calls in: " << F.getName() << "\n"
187349cc55cSDimitry Andric << " Function size: " << F.getInstructionCount()
188349cc55cSDimitry Andric << "\n");
189bdd1243dSDimitry Andric (void)F;
190349cc55cSDimitry Andric
191349cc55cSDimitry Andric auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
192349cc55cSDimitry Andric return FAM.getResult<AssumptionAnalysis>(F);
193349cc55cSDimitry Andric };
194349cc55cSDimitry Andric
195349cc55cSDimitry Andric if (InlineHistoryID != -1 &&
196349cc55cSDimitry Andric inlineHistoryIncludes(&Callee, InlineHistoryID, InlineHistory)) {
197349cc55cSDimitry Andric setInlineRemark(*CB, "recursive");
198349cc55cSDimitry Andric continue;
199349cc55cSDimitry Andric }
200349cc55cSDimitry Andric
201349cc55cSDimitry Andric auto Advice = Advisor.getAdvice(*CB, /*OnlyMandatory*/ false);
202349cc55cSDimitry Andric // Check whether we want to inline this callsite.
203349cc55cSDimitry Andric if (!Advice->isInliningRecommended()) {
204349cc55cSDimitry Andric Advice->recordUnattemptedInlining();
205349cc55cSDimitry Andric continue;
206349cc55cSDimitry Andric }
207349cc55cSDimitry Andric
208349cc55cSDimitry Andric // Setup the data structure used to plumb customization into the
209349cc55cSDimitry Andric // `InlineFunction` routine.
210349cc55cSDimitry Andric InlineFunctionInfo IFI(
211*06c3fb27SDimitry Andric GetAssumptionCache, PSI,
212349cc55cSDimitry Andric &FAM.getResult<BlockFrequencyAnalysis>(*(CB->getCaller())),
213349cc55cSDimitry Andric &FAM.getResult<BlockFrequencyAnalysis>(Callee));
214349cc55cSDimitry Andric
215349cc55cSDimitry Andric InlineResult IR =
216bdd1243dSDimitry Andric InlineFunction(*CB, IFI, /*MergeAttributes=*/true,
217bdd1243dSDimitry Andric &FAM.getResult<AAManager>(*CB->getCaller()));
218349cc55cSDimitry Andric if (!IR.isSuccess()) {
219349cc55cSDimitry Andric Advice->recordUnsuccessfulInlining(IR);
220349cc55cSDimitry Andric continue;
221349cc55cSDimitry Andric }
222349cc55cSDimitry Andric
223bdd1243dSDimitry Andric Changed = true;
224349cc55cSDimitry Andric ++NumInlined;
225349cc55cSDimitry Andric
226bdd1243dSDimitry Andric LLVM_DEBUG(dbgs() << " Size after inlining: " << F.getInstructionCount()
227bdd1243dSDimitry Andric << "\n");
228349cc55cSDimitry Andric
229349cc55cSDimitry Andric // Add any new callsites to defined functions to the worklist.
230349cc55cSDimitry Andric if (!IFI.InlinedCallSites.empty()) {
231349cc55cSDimitry Andric int NewHistoryID = InlineHistory.size();
232349cc55cSDimitry Andric InlineHistory.push_back({&Callee, InlineHistoryID});
233349cc55cSDimitry Andric
234349cc55cSDimitry Andric for (CallBase *ICB : reverse(IFI.InlinedCallSites)) {
235349cc55cSDimitry Andric Function *NewCallee = ICB->getCalledFunction();
236349cc55cSDimitry Andric if (!NewCallee) {
237349cc55cSDimitry Andric // Try to promote an indirect (virtual) call without waiting for
238349cc55cSDimitry Andric // the post-inline cleanup and the next DevirtSCCRepeatedPass
239349cc55cSDimitry Andric // iteration because the next iteration may not happen and we may
240349cc55cSDimitry Andric // miss inlining it.
241349cc55cSDimitry Andric if (tryPromoteCall(*ICB))
242349cc55cSDimitry Andric NewCallee = ICB->getCalledFunction();
243349cc55cSDimitry Andric }
244349cc55cSDimitry Andric if (NewCallee)
245349cc55cSDimitry Andric if (!NewCallee->isDeclaration())
246349cc55cSDimitry Andric Calls->push({ICB, NewHistoryID});
247349cc55cSDimitry Andric }
248349cc55cSDimitry Andric }
249349cc55cSDimitry Andric
250349cc55cSDimitry Andric // For local functions, check whether this makes the callee trivially
251349cc55cSDimitry Andric // dead. In that case, we can drop the body of the function eagerly
252349cc55cSDimitry Andric // which may reduce the number of callers of other functions to one,
253349cc55cSDimitry Andric // changing inline cost thresholds.
254349cc55cSDimitry Andric bool CalleeWasDeleted = false;
255349cc55cSDimitry Andric if (Callee.hasLocalLinkage()) {
256349cc55cSDimitry Andric // To check this we also need to nuke any dead constant uses (perhaps
257349cc55cSDimitry Andric // made dead by this operation on other functions).
258349cc55cSDimitry Andric Callee.removeDeadConstantUsers();
259349cc55cSDimitry Andric // if (Callee.use_empty() && !CG.isLibFunction(Callee)) {
260349cc55cSDimitry Andric if (Callee.use_empty() && !isKnownLibFunction(Callee, GetTLI(Callee))) {
261349cc55cSDimitry Andric Calls->erase_if([&](const std::pair<CallBase *, int> &Call) {
262349cc55cSDimitry Andric return Call.first->getCaller() == &Callee;
263349cc55cSDimitry Andric });
264349cc55cSDimitry Andric // Clear the body and queue the function itself for deletion when we
265349cc55cSDimitry Andric // finish inlining.
266349cc55cSDimitry Andric // Note that after this point, it is an error to do anything other
267349cc55cSDimitry Andric // than use the callee's address or delete it.
268349cc55cSDimitry Andric Callee.dropAllReferences();
269349cc55cSDimitry Andric assert(!is_contained(DeadFunctions, &Callee) &&
270349cc55cSDimitry Andric "Cannot put cause a function to become dead twice!");
271349cc55cSDimitry Andric DeadFunctions.push_back(&Callee);
272349cc55cSDimitry Andric CalleeWasDeleted = true;
273349cc55cSDimitry Andric }
274349cc55cSDimitry Andric }
275349cc55cSDimitry Andric if (CalleeWasDeleted)
276349cc55cSDimitry Andric Advice->recordInliningWithCalleeDeleted();
277349cc55cSDimitry Andric else
278349cc55cSDimitry Andric Advice->recordInlining();
279349cc55cSDimitry Andric }
280349cc55cSDimitry Andric
281349cc55cSDimitry Andric // Now that we've finished inlining all of the calls across this module,
282349cc55cSDimitry Andric // delete all of the trivially dead functions.
283349cc55cSDimitry Andric //
284349cc55cSDimitry Andric // Note that this walks a pointer set which has non-deterministic order but
285349cc55cSDimitry Andric // that is OK as all we do is delete things and add pointers to unordered
286349cc55cSDimitry Andric // sets.
287349cc55cSDimitry Andric for (Function *DeadF : DeadFunctions) {
288349cc55cSDimitry Andric // Clear out any cached analyses.
289349cc55cSDimitry Andric FAM.clear(*DeadF, DeadF->getName());
290349cc55cSDimitry Andric
291349cc55cSDimitry Andric // And delete the actual function from the module.
29204eeddc0SDimitry Andric M.getFunctionList().erase(DeadF);
293349cc55cSDimitry Andric
294349cc55cSDimitry Andric ++NumDeleted;
295349cc55cSDimitry Andric }
296349cc55cSDimitry Andric
297349cc55cSDimitry Andric if (!Changed)
298349cc55cSDimitry Andric return PreservedAnalyses::all();
299349cc55cSDimitry Andric
300349cc55cSDimitry Andric return PreservedAnalyses::none();
301349cc55cSDimitry Andric }
302