1 //===- InlineAdvisor.cpp - analysis pass implementation -------------------===//
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
7 //===----------------------------------------------------------------------===//
9 // This file implements InlineAdvisorAnalysis and DefaultInlineAdvisor, and
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Analysis/InlineAdvisor.h"
15 #include "llvm/ADT/Statistic.h"
16 #include "llvm/Analysis/InlineCost.h"
17 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
18 #include "llvm/Analysis/ProfileSummaryInfo.h"
19 #include "llvm/Analysis/TargetLibraryInfo.h"
20 #include "llvm/Analysis/TargetTransformInfo.h"
21 #include "llvm/IR/DebugInfoMetadata.h"
22 #include "llvm/IR/Instructions.h"
23 #include "llvm/Support/CommandLine.h"
24 #include "llvm/Support/raw_ostream.h"
29 #define DEBUG_TYPE "inline"
31 // This weirdly named statistic tracks the number of times that, when attempting
32 // to inline a function A into B, we analyze the callers of B in order to see
33 // if those would be more profitable and blocked inline steps.
34 STATISTIC(NumCallerCallersAnalyzed, "Number of caller-callers analyzed");
36 /// Flag to add inline messages as callsite attributes 'inline-remark'.
38 InlineRemarkAttribute("inline-remark-attribute", cl::init(false),
40 cl::desc("Enable adding inline-remark attribute to"
41 " callsites processed by inliner but decided"
42 " to be not inlined"));
44 // An integer used to limit the cost of inline deferral. The default negative
45 // number tells shouldBeDeferred to only take the secondary cost into account.
47 InlineDeferralScale("inline-deferral-scale",
48 cl::desc("Scale to limit the cost of inline deferral"),
49 cl::init(2), cl::Hidden);
52 class DefaultInlineAdvice : public InlineAdvice {
54 DefaultInlineAdvice(DefaultInlineAdvisor *Advisor, CallBase &CB,
55 Optional<InlineCost> OIC, OptimizationRemarkEmitter &ORE)
56 : InlineAdvice(Advisor, CB, ORE, OIC.hasValue()), OriginalCB(&CB),
60 void recordUnsuccessfulInliningImpl(const InlineResult &Result) override {
62 llvm::setInlineRemark(*OriginalCB, std::string(Result.getFailureReason()) +
63 "; " + inlineCostStr(*OIC));
65 return OptimizationRemarkMissed(DEBUG_TYPE, "NotInlined", DLoc, Block)
66 << NV("Callee", Callee) << " will not be inlined into "
67 << NV("Caller", Caller) << ": "
68 << NV("Reason", Result.getFailureReason());
72 void recordInliningWithCalleeDeletedImpl() override {
73 emitInlinedInto(ORE, DLoc, Block, *Callee, *Caller, *OIC);
76 void recordInliningImpl() override {
77 emitInlinedInto(ORE, DLoc, Block, *Callee, *Caller, *OIC);
81 CallBase *const OriginalCB;
82 Optional<InlineCost> OIC;
87 llvm::Optional<llvm::InlineCost>
88 getDefaultInlineAdvice(CallBase &CB, FunctionAnalysisManager &FAM,
89 const InlineParams &Params) {
90 Function &Caller = *CB.getCaller();
91 ProfileSummaryInfo *PSI =
92 FAM.getResult<ModuleAnalysisManagerFunctionProxy>(Caller)
93 .getCachedResult<ProfileSummaryAnalysis>(
94 *CB.getParent()->getParent()->getParent());
96 auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(Caller);
97 auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
98 return FAM.getResult<AssumptionAnalysis>(F);
100 auto GetBFI = [&](Function &F) -> BlockFrequencyInfo & {
101 return FAM.getResult<BlockFrequencyAnalysis>(F);
103 auto GetTLI = [&](Function &F) -> const TargetLibraryInfo & {
104 return FAM.getResult<TargetLibraryAnalysis>(F);
107 auto GetInlineCost = [&](CallBase &CB) {
108 Function &Callee = *CB.getCalledFunction();
109 auto &CalleeTTI = FAM.getResult<TargetIRAnalysis>(Callee);
110 bool RemarksEnabled =
111 Callee.getContext().getDiagHandlerPtr()->isMissedOptRemarkEnabled(
113 return getInlineCost(CB, Params, CalleeTTI, GetAssumptionCache, GetTLI,
114 GetBFI, PSI, RemarksEnabled ? &ORE : nullptr);
116 return llvm::shouldInline(CB, GetInlineCost, ORE,
117 Params.EnableDeferral.hasValue() &&
118 Params.EnableDeferral.getValue());
121 std::unique_ptr<InlineAdvice> DefaultInlineAdvisor::getAdvice(CallBase &CB) {
122 auto OIC = getDefaultInlineAdvice(CB, FAM, Params);
123 return std::make_unique<DefaultInlineAdvice>(
125 FAM.getResult<OptimizationRemarkEmitterAnalysis>(*CB.getCaller()));
128 InlineAdvice::InlineAdvice(InlineAdvisor *Advisor, CallBase &CB,
129 OptimizationRemarkEmitter &ORE,
130 bool IsInliningRecommended)
131 : Advisor(Advisor), Caller(CB.getCaller()), Callee(CB.getCalledFunction()),
132 DLoc(CB.getDebugLoc()), Block(CB.getParent()), ORE(ORE),
133 IsInliningRecommended(IsInliningRecommended) {}
135 void InlineAdvisor::markFunctionAsDeleted(Function *F) {
136 assert((!DeletedFunctions.count(F)) &&
137 "Cannot put cause a function to become dead twice!");
138 DeletedFunctions.insert(F);
141 void InlineAdvisor::freeDeletedFunctions() {
142 for (auto *F : DeletedFunctions)
144 DeletedFunctions.clear();
147 void InlineAdvice::recordInliningWithCalleeDeleted() {
149 Advisor->markFunctionAsDeleted(Callee);
150 recordInliningWithCalleeDeletedImpl();
153 AnalysisKey InlineAdvisorAnalysis::Key;
155 bool InlineAdvisorAnalysis::Result::tryCreate(InlineParams Params,
156 InliningAdvisorMode Mode) {
157 auto &FAM = MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
159 case InliningAdvisorMode::Default:
160 Advisor.reset(new DefaultInlineAdvisor(FAM, Params));
162 case InliningAdvisorMode::Development:
163 // To be added subsequently under conditional compilation.
165 case InliningAdvisorMode::Release:
166 #ifdef LLVM_HAVE_TF_AOT
167 Advisor = llvm::getReleaseModeAdvisor(M, MAM);
174 /// Return true if inlining of CB can block the caller from being
175 /// inlined which is proved to be more beneficial. \p IC is the
176 /// estimated inline cost associated with callsite \p CB.
177 /// \p TotalSecondaryCost will be set to the estimated cost of inlining the
178 /// caller if \p CB is suppressed for inlining.
180 shouldBeDeferred(Function *Caller, InlineCost IC, int &TotalSecondaryCost,
181 function_ref<InlineCost(CallBase &CB)> GetInlineCost) {
182 // For now we only handle local or inline functions.
183 if (!Caller->hasLocalLinkage() && !Caller->hasLinkOnceODRLinkage())
185 // If the cost of inlining CB is non-positive, it is not going to prevent the
186 // caller from being inlined into its callers and hence we don't need to
188 if (IC.getCost() <= 0)
190 // Try to detect the case where the current inlining candidate caller (call
191 // it B) is a static or linkonce-ODR function and is an inlining candidate
192 // elsewhere, and the current candidate callee (call it C) is large enough
193 // that inlining it into B would make B too big to inline later. In these
194 // circumstances it may be best not to inline C into B, but to inline B into
197 // This only applies to static and linkonce-ODR functions because those are
198 // expected to be available for inlining in the translation units where they
199 // are used. Thus we will always have the opportunity to make local inlining
200 // decisions. Importantly the linkonce-ODR linkage covers inline functions
201 // and templates in C++.
203 // FIXME: All of this logic should be sunk into getInlineCost. It relies on
204 // the internal implementation of the inline cost metrics rather than
205 // treating them as truly abstract units etc.
206 TotalSecondaryCost = 0;
207 // The candidate cost to be imposed upon the current function.
208 int CandidateCost = IC.getCost() - 1;
209 // If the caller has local linkage and can be inlined to all its callers, we
210 // can apply a huge negative bonus to TotalSecondaryCost.
211 bool ApplyLastCallBonus = Caller->hasLocalLinkage() && !Caller->hasOneUse();
212 // This bool tracks what happens if we DO inline C into B.
213 bool InliningPreventsSomeOuterInline = false;
214 unsigned NumCallerUsers = 0;
215 for (User *U : Caller->users()) {
216 CallBase *CS2 = dyn_cast<CallBase>(U);
218 // If this isn't a call to Caller (it could be some other sort
219 // of reference) skip it. Such references will prevent the caller
220 // from being removed.
221 if (!CS2 || CS2->getCalledFunction() != Caller) {
222 ApplyLastCallBonus = false;
226 InlineCost IC2 = GetInlineCost(*CS2);
227 ++NumCallerCallersAnalyzed;
229 ApplyLastCallBonus = false;
235 // See if inlining of the original callsite would erase the cost delta of
236 // this callsite. We subtract off the penalty for the call instruction,
237 // which we would be deleting.
238 if (IC2.getCostDelta() <= CandidateCost) {
239 InliningPreventsSomeOuterInline = true;
240 TotalSecondaryCost += IC2.getCost();
245 if (!InliningPreventsSomeOuterInline)
248 // If all outer calls to Caller would get inlined, the cost for the last
249 // one is set very low by getInlineCost, in anticipation that Caller will
250 // be removed entirely. We did not account for this above unless there
251 // is only one caller of Caller.
252 if (ApplyLastCallBonus)
253 TotalSecondaryCost -= InlineConstants::LastCallToStaticBonus;
255 // If InlineDeferralScale is negative, then ignore the cost of primary
256 // inlining -- IC.getCost() multiplied by the number of callers to Caller.
257 if (InlineDeferralScale < 0)
258 return TotalSecondaryCost < IC.getCost();
260 int TotalCost = TotalSecondaryCost + IC.getCost() * NumCallerUsers;
261 int Allowance = IC.getCost() * InlineDeferralScale;
262 return TotalCost < Allowance;
266 static std::basic_ostream<char> &operator<<(std::basic_ostream<char> &R,
267 const ore::NV &Arg) {
271 template <class RemarkT>
272 RemarkT &operator<<(RemarkT &&R, const InlineCost &IC) {
275 R << "(cost=always)";
276 } else if (IC.isNever()) {
279 R << "(cost=" << ore::NV("Cost", IC.getCost())
280 << ", threshold=" << ore::NV("Threshold", IC.getThreshold()) << ")";
282 if (const char *Reason = IC.getReason())
283 R << ": " << ore::NV("Reason", Reason);
288 std::string llvm::inlineCostStr(const InlineCost &IC) {
289 std::stringstream Remark;
294 void llvm::setInlineRemark(CallBase &CB, StringRef Message) {
295 if (!InlineRemarkAttribute)
298 Attribute Attr = Attribute::get(CB.getContext(), "inline-remark", Message);
299 CB.addAttribute(AttributeList::FunctionIndex, Attr);
302 /// Return the cost only if the inliner should attempt to inline at the given
303 /// CallSite. If we return the cost, we will emit an optimisation remark later
304 /// using that cost, so we won't do so from this function. Return None if
305 /// inlining should not be attempted.
307 llvm::shouldInline(CallBase &CB,
308 function_ref<InlineCost(CallBase &CB)> GetInlineCost,
309 OptimizationRemarkEmitter &ORE, bool EnableDeferral) {
312 InlineCost IC = GetInlineCost(CB);
313 Instruction *Call = &CB;
314 Function *Callee = CB.getCalledFunction();
315 Function *Caller = CB.getCaller();
318 LLVM_DEBUG(dbgs() << " Inlining " << inlineCostStr(IC)
319 << ", Call: " << CB << "\n");
324 LLVM_DEBUG(dbgs() << " NOT Inlining " << inlineCostStr(IC)
325 << ", Call: " << CB << "\n");
328 return OptimizationRemarkMissed(DEBUG_TYPE, "NeverInline", Call)
329 << NV("Callee", Callee) << " not inlined into "
330 << NV("Caller", Caller) << " because it should never be inlined "
335 return OptimizationRemarkMissed(DEBUG_TYPE, "TooCostly", Call)
336 << NV("Callee", Callee) << " not inlined into "
337 << NV("Caller", Caller) << " because too costly to inline "
341 setInlineRemark(CB, inlineCostStr(IC));
345 int TotalSecondaryCost = 0;
346 if (EnableDeferral &&
347 shouldBeDeferred(Caller, IC, TotalSecondaryCost, GetInlineCost)) {
348 LLVM_DEBUG(dbgs() << " NOT Inlining: " << CB
349 << " Cost = " << IC.getCost()
350 << ", outer Cost = " << TotalSecondaryCost << '\n');
352 return OptimizationRemarkMissed(DEBUG_TYPE, "IncreaseCostInOtherContexts",
354 << "Not inlining. Cost of inlining " << NV("Callee", Callee)
355 << " increases the cost of inlining " << NV("Caller", Caller)
356 << " in other contexts";
358 setInlineRemark(CB, "deferred");
359 // IC does not bool() to false, so get an InlineCost that will.
360 // This will not be inspected to make an error message.
364 LLVM_DEBUG(dbgs() << " Inlining " << inlineCostStr(IC) << ", Call: " << CB
369 void llvm::addLocationToRemarks(OptimizationRemark &Remark, DebugLoc DLoc) {
374 Remark << " at callsite ";
375 for (DILocation *DIL = DLoc.get(); DIL; DIL = DIL->getInlinedAt()) {
378 unsigned int Offset = DIL->getLine();
379 Offset -= DIL->getScope()->getSubprogram()->getLine();
380 unsigned int Discriminator = DIL->getBaseDiscriminator();
381 StringRef Name = DIL->getScope()->getSubprogram()->getLinkageName();
383 Name = DIL->getScope()->getSubprogram()->getName();
384 Remark << Name << ":" << ore::NV("Line", Offset);
386 Remark << "." << ore::NV("Disc", Discriminator);
391 void llvm::emitInlinedInto(OptimizationRemarkEmitter &ORE, DebugLoc DLoc,
392 const BasicBlock *Block, const Function &Callee,
393 const Function &Caller, const InlineCost &IC,
394 bool ForProfileContext, const char *PassName) {
396 bool AlwaysInline = IC.isAlways();
397 StringRef RemarkName = AlwaysInline ? "AlwaysInline" : "Inlined";
398 OptimizationRemark Remark(PassName ? PassName : DEBUG_TYPE, RemarkName,
400 Remark << ore::NV("Callee", &Callee) << " inlined into ";
401 Remark << ore::NV("Caller", &Caller);
402 if (ForProfileContext)
403 Remark << " to match profiling context";
404 Remark << " with " << IC;
405 addLocationToRemarks(Remark, DLoc);