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/ReplayInlineAdvisor.h"
20 #include "llvm/Analysis/TargetLibraryInfo.h"
21 #include "llvm/Analysis/TargetTransformInfo.h"
22 #include "llvm/IR/DebugInfoMetadata.h"
23 #include "llvm/IR/Instructions.h"
24 #include "llvm/Support/CommandLine.h"
25 #include "llvm/Support/raw_ostream.h"
28 #define DEBUG_TYPE "inline"
30 // This weirdly named statistic tracks the number of times that, when attempting
31 // to inline a function A into B, we analyze the callers of B in order to see
32 // if those would be more profitable and blocked inline steps.
33 STATISTIC(NumCallerCallersAnalyzed, "Number of caller-callers analyzed");
35 /// Flag to add inline messages as callsite attributes 'inline-remark'.
37 InlineRemarkAttribute("inline-remark-attribute", cl::init(false),
39 cl::desc("Enable adding inline-remark attribute to"
40 " callsites processed by inliner but decided"
41 " to be not inlined"));
43 // An integer used to limit the cost of inline deferral. The default negative
44 // number tells shouldBeDeferred to only take the secondary cost into account.
46 InlineDeferralScale("inline-deferral-scale",
47 cl::desc("Scale to limit the cost of inline deferral"),
48 cl::init(2), cl::Hidden);
50 extern cl::opt<InlinerFunctionImportStatsOpts> InlinerFunctionImportStats;
53 using namespace llvm::ore;
54 class MandatoryInlineAdvice : public InlineAdvice {
56 MandatoryInlineAdvice(InlineAdvisor *Advisor, CallBase &CB,
57 OptimizationRemarkEmitter &ORE,
58 bool IsInliningMandatory)
59 : InlineAdvice(Advisor, CB, ORE, IsInliningMandatory) {}
62 void recordInliningWithCalleeDeletedImpl() override { recordInliningImpl(); }
64 void recordInliningImpl() override {
65 if (IsInliningRecommended)
66 emitInlinedInto(ORE, DLoc, Block, *Callee, *Caller, IsInliningRecommended,
67 [&](OptimizationRemark &Remark) {
68 Remark << ": always inline attribute";
72 void recordUnsuccessfulInliningImpl(const InlineResult &Result) override {
73 if (IsInliningRecommended)
75 return OptimizationRemarkMissed(DEBUG_TYPE, "NotInlined", DLoc, Block)
76 << "'" << NV("Callee", Callee) << "' is not AlwaysInline into '"
77 << NV("Caller", Caller)
78 << "': " << NV("Reason", Result.getFailureReason());
82 void recordUnattemptedInliningImpl() override {
83 assert(!IsInliningRecommended && "Expected to attempt inlining");
88 void DefaultInlineAdvice::recordUnsuccessfulInliningImpl(
89 const InlineResult &Result) {
91 llvm::setInlineRemark(*OriginalCB, std::string(Result.getFailureReason()) +
92 "; " + inlineCostStr(*OIC));
94 return OptimizationRemarkMissed(DEBUG_TYPE, "NotInlined", DLoc, Block)
95 << "'" << NV("Callee", Callee) << "' is not inlined into '"
96 << NV("Caller", Caller)
97 << "': " << NV("Reason", Result.getFailureReason());
101 void DefaultInlineAdvice::recordInliningWithCalleeDeletedImpl() {
103 emitInlinedIntoBasedOnCost(ORE, DLoc, Block, *Callee, *Caller, *OIC);
106 void DefaultInlineAdvice::recordInliningImpl() {
108 emitInlinedIntoBasedOnCost(ORE, DLoc, Block, *Callee, *Caller, *OIC);
111 llvm::Optional<llvm::InlineCost> static getDefaultInlineAdvice(
112 CallBase &CB, FunctionAnalysisManager &FAM, const InlineParams &Params) {
113 Function &Caller = *CB.getCaller();
114 ProfileSummaryInfo *PSI =
115 FAM.getResult<ModuleAnalysisManagerFunctionProxy>(Caller)
116 .getCachedResult<ProfileSummaryAnalysis>(
117 *CB.getParent()->getParent()->getParent());
119 auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(Caller);
120 auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
121 return FAM.getResult<AssumptionAnalysis>(F);
123 auto GetBFI = [&](Function &F) -> BlockFrequencyInfo & {
124 return FAM.getResult<BlockFrequencyAnalysis>(F);
126 auto GetTLI = [&](Function &F) -> const TargetLibraryInfo & {
127 return FAM.getResult<TargetLibraryAnalysis>(F);
130 auto GetInlineCost = [&](CallBase &CB) {
131 Function &Callee = *CB.getCalledFunction();
132 auto &CalleeTTI = FAM.getResult<TargetIRAnalysis>(Callee);
133 bool RemarksEnabled =
134 Callee.getContext().getDiagHandlerPtr()->isMissedOptRemarkEnabled(
136 return getInlineCost(CB, Params, CalleeTTI, GetAssumptionCache, GetTLI,
137 GetBFI, PSI, RemarksEnabled ? &ORE : nullptr);
139 return llvm::shouldInline(CB, GetInlineCost, ORE,
140 Params.EnableDeferral.getValueOr(false));
143 std::unique_ptr<InlineAdvice>
144 DefaultInlineAdvisor::getAdviceImpl(CallBase &CB) {
145 auto OIC = getDefaultInlineAdvice(CB, FAM, Params);
146 return std::make_unique<DefaultInlineAdvice>(
148 FAM.getResult<OptimizationRemarkEmitterAnalysis>(*CB.getCaller()));
151 InlineAdvice::InlineAdvice(InlineAdvisor *Advisor, CallBase &CB,
152 OptimizationRemarkEmitter &ORE,
153 bool IsInliningRecommended)
154 : Advisor(Advisor), Caller(CB.getCaller()), Callee(CB.getCalledFunction()),
155 DLoc(CB.getDebugLoc()), Block(CB.getParent()), ORE(ORE),
156 IsInliningRecommended(IsInliningRecommended) {}
158 void InlineAdvisor::markFunctionAsDeleted(Function *F) {
159 assert((!DeletedFunctions.count(F)) &&
160 "Cannot put cause a function to become dead twice!");
161 DeletedFunctions.insert(F);
164 void InlineAdvisor::freeDeletedFunctions() {
165 for (auto *F : DeletedFunctions)
167 DeletedFunctions.clear();
170 void InlineAdvice::recordInlineStatsIfNeeded() {
171 if (Advisor->ImportedFunctionsStats)
172 Advisor->ImportedFunctionsStats->recordInline(*Caller, *Callee);
175 void InlineAdvice::recordInlining() {
177 recordInlineStatsIfNeeded();
178 recordInliningImpl();
181 void InlineAdvice::recordInliningWithCalleeDeleted() {
183 recordInlineStatsIfNeeded();
184 Advisor->markFunctionAsDeleted(Callee);
185 recordInliningWithCalleeDeletedImpl();
188 AnalysisKey InlineAdvisorAnalysis::Key;
190 bool InlineAdvisorAnalysis::Result::tryCreate(
191 InlineParams Params, InliningAdvisorMode Mode,
192 const ReplayInlinerSettings &ReplaySettings) {
193 auto &FAM = MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
195 case InliningAdvisorMode::Default:
196 LLVM_DEBUG(dbgs() << "Using default inliner heuristic.\n");
197 Advisor.reset(new DefaultInlineAdvisor(M, FAM, Params));
198 // Restrict replay to default advisor, ML advisors are stateful so
199 // replay will need augmentations to interleave with them correctly.
200 if (!ReplaySettings.ReplayFile.empty()) {
201 Advisor = llvm::getReplayInlineAdvisor(M, FAM, M.getContext(),
202 std::move(Advisor), ReplaySettings,
203 /* EmitRemarks =*/true);
206 case InliningAdvisorMode::Development:
207 #ifdef LLVM_HAVE_TF_API
208 LLVM_DEBUG(dbgs() << "Using development-mode inliner policy.\n");
210 llvm::getDevelopmentModeAdvisor(M, MAM, [&FAM, Params](CallBase &CB) {
211 auto OIC = getDefaultInlineAdvice(CB, FAM, Params);
212 return OIC.hasValue();
216 case InliningAdvisorMode::Release:
217 #ifdef LLVM_HAVE_TF_AOT
218 LLVM_DEBUG(dbgs() << "Using release-mode inliner policy.\n");
219 Advisor = llvm::getReleaseModeAdvisor(M, MAM);
227 /// Return true if inlining of CB can block the caller from being
228 /// inlined which is proved to be more beneficial. \p IC is the
229 /// estimated inline cost associated with callsite \p CB.
230 /// \p TotalSecondaryCost will be set to the estimated cost of inlining the
231 /// caller if \p CB is suppressed for inlining.
233 shouldBeDeferred(Function *Caller, InlineCost IC, int &TotalSecondaryCost,
234 function_ref<InlineCost(CallBase &CB)> GetInlineCost) {
235 // For now we only handle local or inline functions.
236 if (!Caller->hasLocalLinkage() && !Caller->hasLinkOnceODRLinkage())
238 // If the cost of inlining CB is non-positive, it is not going to prevent the
239 // caller from being inlined into its callers and hence we don't need to
241 if (IC.getCost() <= 0)
243 // Try to detect the case where the current inlining candidate caller (call
244 // it B) is a static or linkonce-ODR function and is an inlining candidate
245 // elsewhere, and the current candidate callee (call it C) is large enough
246 // that inlining it into B would make B too big to inline later. In these
247 // circumstances it may be best not to inline C into B, but to inline B into
250 // This only applies to static and linkonce-ODR functions because those are
251 // expected to be available for inlining in the translation units where they
252 // are used. Thus we will always have the opportunity to make local inlining
253 // decisions. Importantly the linkonce-ODR linkage covers inline functions
254 // and templates in C++.
256 // FIXME: All of this logic should be sunk into getInlineCost. It relies on
257 // the internal implementation of the inline cost metrics rather than
258 // treating them as truly abstract units etc.
259 TotalSecondaryCost = 0;
260 // The candidate cost to be imposed upon the current function.
261 int CandidateCost = IC.getCost() - 1;
262 // If the caller has local linkage and can be inlined to all its callers, we
263 // can apply a huge negative bonus to TotalSecondaryCost.
264 bool ApplyLastCallBonus = Caller->hasLocalLinkage() && !Caller->hasOneUse();
265 // This bool tracks what happens if we DO inline C into B.
266 bool InliningPreventsSomeOuterInline = false;
267 unsigned NumCallerUsers = 0;
268 for (User *U : Caller->users()) {
269 CallBase *CS2 = dyn_cast<CallBase>(U);
271 // If this isn't a call to Caller (it could be some other sort
272 // of reference) skip it. Such references will prevent the caller
273 // from being removed.
274 if (!CS2 || CS2->getCalledFunction() != Caller) {
275 ApplyLastCallBonus = false;
279 InlineCost IC2 = GetInlineCost(*CS2);
280 ++NumCallerCallersAnalyzed;
282 ApplyLastCallBonus = false;
288 // See if inlining of the original callsite would erase the cost delta of
289 // this callsite. We subtract off the penalty for the call instruction,
290 // which we would be deleting.
291 if (IC2.getCostDelta() <= CandidateCost) {
292 InliningPreventsSomeOuterInline = true;
293 TotalSecondaryCost += IC2.getCost();
298 if (!InliningPreventsSomeOuterInline)
301 // If all outer calls to Caller would get inlined, the cost for the last
302 // one is set very low by getInlineCost, in anticipation that Caller will
303 // be removed entirely. We did not account for this above unless there
304 // is only one caller of Caller.
305 if (ApplyLastCallBonus)
306 TotalSecondaryCost -= InlineConstants::LastCallToStaticBonus;
308 // If InlineDeferralScale is negative, then ignore the cost of primary
309 // inlining -- IC.getCost() multiplied by the number of callers to Caller.
310 if (InlineDeferralScale < 0)
311 return TotalSecondaryCost < IC.getCost();
313 int TotalCost = TotalSecondaryCost + IC.getCost() * NumCallerUsers;
314 int Allowance = IC.getCost() * InlineDeferralScale;
315 return TotalCost < Allowance;
319 static raw_ostream &operator<<(raw_ostream &R, const ore::NV &Arg) {
323 template <class RemarkT>
324 RemarkT &operator<<(RemarkT &&R, const InlineCost &IC) {
327 R << "(cost=always)";
328 } else if (IC.isNever()) {
331 R << "(cost=" << ore::NV("Cost", IC.getCost())
332 << ", threshold=" << ore::NV("Threshold", IC.getThreshold()) << ")";
334 if (const char *Reason = IC.getReason())
335 R << ": " << ore::NV("Reason", Reason);
340 std::string llvm::inlineCostStr(const InlineCost &IC) {
342 raw_string_ostream Remark(Buffer);
347 void llvm::setInlineRemark(CallBase &CB, StringRef Message) {
348 if (!InlineRemarkAttribute)
351 Attribute Attr = Attribute::get(CB.getContext(), "inline-remark", Message);
355 /// Return the cost only if the inliner should attempt to inline at the given
356 /// CallSite. If we return the cost, we will emit an optimisation remark later
357 /// using that cost, so we won't do so from this function. Return None if
358 /// inlining should not be attempted.
360 llvm::shouldInline(CallBase &CB,
361 function_ref<InlineCost(CallBase &CB)> GetInlineCost,
362 OptimizationRemarkEmitter &ORE, bool EnableDeferral) {
365 InlineCost IC = GetInlineCost(CB);
366 Instruction *Call = &CB;
367 Function *Callee = CB.getCalledFunction();
368 Function *Caller = CB.getCaller();
371 LLVM_DEBUG(dbgs() << " Inlining " << inlineCostStr(IC)
372 << ", Call: " << CB << "\n");
377 LLVM_DEBUG(dbgs() << " NOT Inlining " << inlineCostStr(IC)
378 << ", Call: " << CB << "\n");
381 return OptimizationRemarkMissed(DEBUG_TYPE, "NeverInline", Call)
382 << "'" << NV("Callee", Callee) << "' not inlined into '"
383 << NV("Caller", Caller)
384 << "' because it should never be inlined " << IC;
388 return OptimizationRemarkMissed(DEBUG_TYPE, "TooCostly", Call)
389 << "'" << NV("Callee", Callee) << "' not inlined into '"
390 << NV("Caller", Caller) << "' because too costly to inline "
394 setInlineRemark(CB, inlineCostStr(IC));
398 int TotalSecondaryCost = 0;
399 if (EnableDeferral &&
400 shouldBeDeferred(Caller, IC, TotalSecondaryCost, GetInlineCost)) {
401 LLVM_DEBUG(dbgs() << " NOT Inlining: " << CB
402 << " Cost = " << IC.getCost()
403 << ", outer Cost = " << TotalSecondaryCost << '\n');
405 return OptimizationRemarkMissed(DEBUG_TYPE, "IncreaseCostInOtherContexts",
407 << "Not inlining. Cost of inlining '" << NV("Callee", Callee)
408 << "' increases the cost of inlining '" << NV("Caller", Caller)
409 << "' in other contexts";
411 setInlineRemark(CB, "deferred");
412 // IC does not bool() to false, so get an InlineCost that will.
413 // This will not be inspected to make an error message.
417 LLVM_DEBUG(dbgs() << " Inlining " << inlineCostStr(IC) << ", Call: " << CB
422 std::string llvm::formatCallSiteLocation(DebugLoc DLoc,
423 const CallSiteFormat &Format) {
425 raw_string_ostream CallSiteLoc(Buffer);
427 for (DILocation *DIL = DLoc.get(); DIL; DIL = DIL->getInlinedAt()) {
429 CallSiteLoc << " @ ";
430 // Note that negative line offset is actually possible, but we use
431 // unsigned int to match line offset representation in remarks so
432 // it's directly consumable by relay advisor.
434 DIL->getLine() - DIL->getScope()->getSubprogram()->getLine();
435 uint32_t Discriminator = DIL->getBaseDiscriminator();
436 StringRef Name = DIL->getScope()->getSubprogram()->getLinkageName();
438 Name = DIL->getScope()->getSubprogram()->getName();
439 CallSiteLoc << Name.str() << ":" << llvm::utostr(Offset);
440 if (Format.outputColumn())
441 CallSiteLoc << ":" << llvm::utostr(DIL->getColumn());
442 if (Format.outputDiscriminator() && Discriminator)
443 CallSiteLoc << "." << llvm::utostr(Discriminator);
447 return CallSiteLoc.str();
450 void llvm::addLocationToRemarks(OptimizationRemark &Remark, DebugLoc DLoc) {
456 Remark << " at callsite ";
457 for (DILocation *DIL = DLoc.get(); DIL; DIL = DIL->getInlinedAt()) {
460 unsigned int Offset = DIL->getLine();
461 Offset -= DIL->getScope()->getSubprogram()->getLine();
462 unsigned int Discriminator = DIL->getBaseDiscriminator();
463 StringRef Name = DIL->getScope()->getSubprogram()->getLinkageName();
465 Name = DIL->getScope()->getSubprogram()->getName();
466 Remark << Name << ":" << ore::NV("Line", Offset) << ":"
467 << ore::NV("Column", DIL->getColumn());
469 Remark << "." << ore::NV("Disc", Discriminator);
476 void llvm::emitInlinedInto(
477 OptimizationRemarkEmitter &ORE, DebugLoc DLoc, const BasicBlock *Block,
478 const Function &Callee, const Function &Caller, bool AlwaysInline,
479 function_ref<void(OptimizationRemark &)> ExtraContext,
480 const char *PassName) {
482 StringRef RemarkName = AlwaysInline ? "AlwaysInline" : "Inlined";
483 OptimizationRemark Remark(PassName ? PassName : DEBUG_TYPE, RemarkName,
485 Remark << "'" << ore::NV("Callee", &Callee) << "' inlined into '"
486 << ore::NV("Caller", &Caller) << "'";
488 ExtraContext(Remark);
489 addLocationToRemarks(Remark, DLoc);
494 void llvm::emitInlinedIntoBasedOnCost(
495 OptimizationRemarkEmitter &ORE, DebugLoc DLoc, const BasicBlock *Block,
496 const Function &Callee, const Function &Caller, const InlineCost &IC,
497 bool ForProfileContext, const char *PassName) {
498 llvm::emitInlinedInto(
499 ORE, DLoc, Block, Callee, Caller, IC.isAlways(),
500 [&](OptimizationRemark &Remark) {
501 if (ForProfileContext)
502 Remark << " to match profiling context";
503 Remark << " with " << IC;
508 InlineAdvisor::InlineAdvisor(Module &M, FunctionAnalysisManager &FAM)
510 if (InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No) {
511 ImportedFunctionsStats =
512 std::make_unique<ImportedFunctionsInliningStatistics>();
513 ImportedFunctionsStats->setModuleInfo(M);
517 InlineAdvisor::~InlineAdvisor() {
518 if (ImportedFunctionsStats) {
519 assert(InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No);
520 ImportedFunctionsStats->dump(InlinerFunctionImportStats ==
521 InlinerFunctionImportStatsOpts::Verbose);
524 freeDeletedFunctions();
527 std::unique_ptr<InlineAdvice> InlineAdvisor::getMandatoryAdvice(CallBase &CB,
529 return std::make_unique<MandatoryInlineAdvice>(this, CB, getCallerORE(CB),
533 InlineAdvisor::MandatoryInliningKind
534 InlineAdvisor::getMandatoryKind(CallBase &CB, FunctionAnalysisManager &FAM,
535 OptimizationRemarkEmitter &ORE) {
536 auto &Callee = *CB.getCalledFunction();
538 auto GetTLI = [&](Function &F) -> const TargetLibraryInfo & {
539 return FAM.getResult<TargetLibraryAnalysis>(F);
542 auto &TIR = FAM.getResult<TargetIRAnalysis>(Callee);
544 auto TrivialDecision =
545 llvm::getAttributeBasedInliningDecision(CB, &Callee, TIR, GetTLI);
547 if (TrivialDecision.hasValue()) {
548 if (TrivialDecision->isSuccess())
549 return MandatoryInliningKind::Always;
551 return MandatoryInliningKind::Never;
553 return MandatoryInliningKind::NotMandatory;
556 std::unique_ptr<InlineAdvice> InlineAdvisor::getAdvice(CallBase &CB,
557 bool MandatoryOnly) {
559 return getAdviceImpl(CB);
560 bool Advice = CB.getCaller() != CB.getCalledFunction() &&
561 MandatoryInliningKind::Always ==
562 getMandatoryKind(CB, FAM, getCallerORE(CB));
563 return getMandatoryAdvice(CB, Advice);
566 OptimizationRemarkEmitter &InlineAdvisor::getCallerORE(CallBase &CB) {
567 return FAM.getResult<OptimizationRemarkEmitterAnalysis>(*CB.getCaller());