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/IR/PassManager.h"
25 #include "llvm/Support/CommandLine.h"
26 #include "llvm/Support/raw_ostream.h"
29 #define DEBUG_TYPE "inline"
30 #ifdef LLVM_HAVE_TF_AOT_INLINERSIZEMODEL
31 #define LLVM_HAVE_TF_AOT
34 // This weirdly named statistic tracks the number of times that, when attempting
35 // to inline a function A into B, we analyze the callers of B in order to see
36 // if those would be more profitable and blocked inline steps.
37 STATISTIC(NumCallerCallersAnalyzed, "Number of caller-callers analyzed");
39 /// Flag to add inline messages as callsite attributes 'inline-remark'.
41 InlineRemarkAttribute("inline-remark-attribute", cl::init(false),
43 cl::desc("Enable adding inline-remark attribute to"
44 " callsites processed by inliner but decided"
45 " to be not inlined"));
47 static cl::opt<bool> EnableInlineDeferral("inline-deferral", cl::init(false),
49 cl::desc("Enable deferred inlining"));
51 // An integer used to limit the cost of inline deferral. The default negative
52 // number tells shouldBeDeferred to only take the secondary cost into account.
54 InlineDeferralScale("inline-deferral-scale",
55 cl::desc("Scale to limit the cost of inline deferral"),
56 cl::init(2), cl::Hidden);
58 extern cl::opt<InlinerFunctionImportStatsOpts> InlinerFunctionImportStats;
61 using namespace llvm::ore;
62 class MandatoryInlineAdvice : public InlineAdvice {
64 MandatoryInlineAdvice(InlineAdvisor *Advisor, CallBase &CB,
65 OptimizationRemarkEmitter &ORE,
66 bool IsInliningMandatory)
67 : InlineAdvice(Advisor, CB, ORE, IsInliningMandatory) {}
70 void recordInliningWithCalleeDeletedImpl() override { recordInliningImpl(); }
72 void recordInliningImpl() override {
73 if (IsInliningRecommended)
74 emitInlinedInto(ORE, DLoc, Block, *Callee, *Caller, IsInliningRecommended,
75 [&](OptimizationRemark &Remark) {
76 Remark << ": always inline attribute";
80 void recordUnsuccessfulInliningImpl(const InlineResult &Result) override {
81 if (IsInliningRecommended)
83 return OptimizationRemarkMissed(DEBUG_TYPE, "NotInlined", DLoc, Block)
84 << "'" << NV("Callee", Callee) << "' is not AlwaysInline into '"
85 << NV("Caller", Caller)
86 << "': " << NV("Reason", Result.getFailureReason());
90 void recordUnattemptedInliningImpl() override {
91 assert(!IsInliningRecommended && "Expected to attempt inlining");
96 void DefaultInlineAdvice::recordUnsuccessfulInliningImpl(
97 const InlineResult &Result) {
99 llvm::setInlineRemark(*OriginalCB, std::string(Result.getFailureReason()) +
100 "; " + inlineCostStr(*OIC));
102 return OptimizationRemarkMissed(DEBUG_TYPE, "NotInlined", DLoc, Block)
103 << "'" << NV("Callee", Callee) << "' is not inlined into '"
104 << NV("Caller", Caller)
105 << "': " << NV("Reason", Result.getFailureReason());
109 void DefaultInlineAdvice::recordInliningWithCalleeDeletedImpl() {
111 emitInlinedIntoBasedOnCost(ORE, DLoc, Block, *Callee, *Caller, *OIC);
114 void DefaultInlineAdvice::recordInliningImpl() {
116 emitInlinedIntoBasedOnCost(ORE, DLoc, Block, *Callee, *Caller, *OIC);
119 llvm::Optional<llvm::InlineCost> static getDefaultInlineAdvice(
120 CallBase &CB, FunctionAnalysisManager &FAM, const InlineParams &Params) {
121 Function &Caller = *CB.getCaller();
122 ProfileSummaryInfo *PSI =
123 FAM.getResult<ModuleAnalysisManagerFunctionProxy>(Caller)
124 .getCachedResult<ProfileSummaryAnalysis>(
125 *CB.getParent()->getParent()->getParent());
127 auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(Caller);
128 auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
129 return FAM.getResult<AssumptionAnalysis>(F);
131 auto GetBFI = [&](Function &F) -> BlockFrequencyInfo & {
132 return FAM.getResult<BlockFrequencyAnalysis>(F);
134 auto GetTLI = [&](Function &F) -> const TargetLibraryInfo & {
135 return FAM.getResult<TargetLibraryAnalysis>(F);
138 auto GetInlineCost = [&](CallBase &CB) {
139 Function &Callee = *CB.getCalledFunction();
140 auto &CalleeTTI = FAM.getResult<TargetIRAnalysis>(Callee);
141 bool RemarksEnabled =
142 Callee.getContext().getDiagHandlerPtr()->isMissedOptRemarkEnabled(
144 return getInlineCost(CB, Params, CalleeTTI, GetAssumptionCache, GetTLI,
145 GetBFI, PSI, RemarksEnabled ? &ORE : nullptr);
147 return llvm::shouldInline(
148 CB, GetInlineCost, ORE,
149 Params.EnableDeferral.getValueOr(EnableInlineDeferral));
152 std::unique_ptr<InlineAdvice>
153 DefaultInlineAdvisor::getAdviceImpl(CallBase &CB) {
154 auto OIC = getDefaultInlineAdvice(CB, FAM, Params);
155 return std::make_unique<DefaultInlineAdvice>(
157 FAM.getResult<OptimizationRemarkEmitterAnalysis>(*CB.getCaller()));
160 InlineAdvice::InlineAdvice(InlineAdvisor *Advisor, CallBase &CB,
161 OptimizationRemarkEmitter &ORE,
162 bool IsInliningRecommended)
163 : Advisor(Advisor), Caller(CB.getCaller()), Callee(CB.getCalledFunction()),
164 DLoc(CB.getDebugLoc()), Block(CB.getParent()), ORE(ORE),
165 IsInliningRecommended(IsInliningRecommended) {}
167 void InlineAdvice::recordInlineStatsIfNeeded() {
168 if (Advisor->ImportedFunctionsStats)
169 Advisor->ImportedFunctionsStats->recordInline(*Caller, *Callee);
172 void InlineAdvice::recordInlining() {
174 recordInlineStatsIfNeeded();
175 recordInliningImpl();
178 void InlineAdvice::recordInliningWithCalleeDeleted() {
180 recordInlineStatsIfNeeded();
181 recordInliningWithCalleeDeletedImpl();
184 AnalysisKey InlineAdvisorAnalysis::Key;
186 bool InlineAdvisorAnalysis::Result::tryCreate(
187 InlineParams Params, InliningAdvisorMode Mode,
188 const ReplayInlinerSettings &ReplaySettings) {
189 auto &FAM = MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
191 case InliningAdvisorMode::Default:
192 LLVM_DEBUG(dbgs() << "Using default inliner heuristic.\n");
193 Advisor.reset(new DefaultInlineAdvisor(M, FAM, Params));
194 // Restrict replay to default advisor, ML advisors are stateful so
195 // replay will need augmentations to interleave with them correctly.
196 if (!ReplaySettings.ReplayFile.empty()) {
197 Advisor = llvm::getReplayInlineAdvisor(M, FAM, M.getContext(),
198 std::move(Advisor), ReplaySettings,
199 /* EmitRemarks =*/true);
202 case InliningAdvisorMode::Development:
203 #ifdef LLVM_HAVE_TF_API
204 LLVM_DEBUG(dbgs() << "Using development-mode inliner policy.\n");
206 llvm::getDevelopmentModeAdvisor(M, MAM, [&FAM, Params](CallBase &CB) {
207 auto OIC = getDefaultInlineAdvice(CB, FAM, Params);
208 return OIC.hasValue();
212 case InliningAdvisorMode::Release:
213 #ifdef LLVM_HAVE_TF_AOT
214 LLVM_DEBUG(dbgs() << "Using release-mode inliner policy.\n");
215 Advisor = llvm::getReleaseModeAdvisor(M, MAM);
223 /// Return true if inlining of CB can block the caller from being
224 /// inlined which is proved to be more beneficial. \p IC is the
225 /// estimated inline cost associated with callsite \p CB.
226 /// \p TotalSecondaryCost will be set to the estimated cost of inlining the
227 /// caller if \p CB is suppressed for inlining.
229 shouldBeDeferred(Function *Caller, InlineCost IC, int &TotalSecondaryCost,
230 function_ref<InlineCost(CallBase &CB)> GetInlineCost) {
231 // For now we only handle local or inline functions.
232 if (!Caller->hasLocalLinkage() && !Caller->hasLinkOnceODRLinkage())
234 // If the cost of inlining CB is non-positive, it is not going to prevent the
235 // caller from being inlined into its callers and hence we don't need to
237 if (IC.getCost() <= 0)
239 // Try to detect the case where the current inlining candidate caller (call
240 // it B) is a static or linkonce-ODR function and is an inlining candidate
241 // elsewhere, and the current candidate callee (call it C) is large enough
242 // that inlining it into B would make B too big to inline later. In these
243 // circumstances it may be best not to inline C into B, but to inline B into
246 // This only applies to static and linkonce-ODR functions because those are
247 // expected to be available for inlining in the translation units where they
248 // are used. Thus we will always have the opportunity to make local inlining
249 // decisions. Importantly the linkonce-ODR linkage covers inline functions
250 // and templates in C++.
252 // FIXME: All of this logic should be sunk into getInlineCost. It relies on
253 // the internal implementation of the inline cost metrics rather than
254 // treating them as truly abstract units etc.
255 TotalSecondaryCost = 0;
256 // The candidate cost to be imposed upon the current function.
257 int CandidateCost = IC.getCost() - 1;
258 // If the caller has local linkage and can be inlined to all its callers, we
259 // can apply a huge negative bonus to TotalSecondaryCost.
260 bool ApplyLastCallBonus = Caller->hasLocalLinkage() && !Caller->hasOneUse();
261 // This bool tracks what happens if we DO inline C into B.
262 bool InliningPreventsSomeOuterInline = false;
263 unsigned NumCallerUsers = 0;
264 for (User *U : Caller->users()) {
265 CallBase *CS2 = dyn_cast<CallBase>(U);
267 // If this isn't a call to Caller (it could be some other sort
268 // of reference) skip it. Such references will prevent the caller
269 // from being removed.
270 if (!CS2 || CS2->getCalledFunction() != Caller) {
271 ApplyLastCallBonus = false;
275 InlineCost IC2 = GetInlineCost(*CS2);
276 ++NumCallerCallersAnalyzed;
278 ApplyLastCallBonus = false;
284 // See if inlining of the original callsite would erase the cost delta of
285 // this callsite. We subtract off the penalty for the call instruction,
286 // which we would be deleting.
287 if (IC2.getCostDelta() <= CandidateCost) {
288 InliningPreventsSomeOuterInline = true;
289 TotalSecondaryCost += IC2.getCost();
294 if (!InliningPreventsSomeOuterInline)
297 // If all outer calls to Caller would get inlined, the cost for the last
298 // one is set very low by getInlineCost, in anticipation that Caller will
299 // be removed entirely. We did not account for this above unless there
300 // is only one caller of Caller.
301 if (ApplyLastCallBonus)
302 TotalSecondaryCost -= InlineConstants::LastCallToStaticBonus;
304 // If InlineDeferralScale is negative, then ignore the cost of primary
305 // inlining -- IC.getCost() multiplied by the number of callers to Caller.
306 if (InlineDeferralScale < 0)
307 return TotalSecondaryCost < IC.getCost();
309 int TotalCost = TotalSecondaryCost + IC.getCost() * NumCallerUsers;
310 int Allowance = IC.getCost() * InlineDeferralScale;
311 return TotalCost < Allowance;
315 static raw_ostream &operator<<(raw_ostream &R, const ore::NV &Arg) {
319 template <class RemarkT>
320 RemarkT &operator<<(RemarkT &&R, const InlineCost &IC) {
323 R << "(cost=always)";
324 } else if (IC.isNever()) {
327 R << "(cost=" << ore::NV("Cost", IC.getCost())
328 << ", threshold=" << ore::NV("Threshold", IC.getThreshold()) << ")";
330 if (const char *Reason = IC.getReason())
331 R << ": " << ore::NV("Reason", Reason);
336 std::string llvm::inlineCostStr(const InlineCost &IC) {
338 raw_string_ostream Remark(Buffer);
343 void llvm::setInlineRemark(CallBase &CB, StringRef Message) {
344 if (!InlineRemarkAttribute)
347 Attribute Attr = Attribute::get(CB.getContext(), "inline-remark", Message);
351 /// Return the cost only if the inliner should attempt to inline at the given
352 /// CallSite. If we return the cost, we will emit an optimisation remark later
353 /// using that cost, so we won't do so from this function. Return None if
354 /// inlining should not be attempted.
356 llvm::shouldInline(CallBase &CB,
357 function_ref<InlineCost(CallBase &CB)> GetInlineCost,
358 OptimizationRemarkEmitter &ORE, bool EnableDeferral) {
361 InlineCost IC = GetInlineCost(CB);
362 Instruction *Call = &CB;
363 Function *Callee = CB.getCalledFunction();
364 Function *Caller = CB.getCaller();
367 LLVM_DEBUG(dbgs() << " Inlining " << inlineCostStr(IC)
368 << ", Call: " << CB << "\n");
373 LLVM_DEBUG(dbgs() << " NOT Inlining " << inlineCostStr(IC)
374 << ", Call: " << CB << "\n");
377 return OptimizationRemarkMissed(DEBUG_TYPE, "NeverInline", Call)
378 << "'" << NV("Callee", Callee) << "' not inlined into '"
379 << NV("Caller", Caller)
380 << "' because it should never be inlined " << IC;
384 return OptimizationRemarkMissed(DEBUG_TYPE, "TooCostly", Call)
385 << "'" << NV("Callee", Callee) << "' not inlined into '"
386 << NV("Caller", Caller) << "' because too costly to inline "
390 setInlineRemark(CB, inlineCostStr(IC));
394 int TotalSecondaryCost = 0;
395 if (EnableDeferral &&
396 shouldBeDeferred(Caller, IC, TotalSecondaryCost, GetInlineCost)) {
397 LLVM_DEBUG(dbgs() << " NOT Inlining: " << CB
398 << " Cost = " << IC.getCost()
399 << ", outer Cost = " << TotalSecondaryCost << '\n');
401 return OptimizationRemarkMissed(DEBUG_TYPE, "IncreaseCostInOtherContexts",
403 << "Not inlining. Cost of inlining '" << NV("Callee", Callee)
404 << "' increases the cost of inlining '" << NV("Caller", Caller)
405 << "' in other contexts";
407 setInlineRemark(CB, "deferred");
411 LLVM_DEBUG(dbgs() << " Inlining " << inlineCostStr(IC) << ", Call: " << CB
416 std::string llvm::formatCallSiteLocation(DebugLoc DLoc,
417 const CallSiteFormat &Format) {
419 raw_string_ostream CallSiteLoc(Buffer);
421 for (DILocation *DIL = DLoc.get(); DIL; DIL = DIL->getInlinedAt()) {
423 CallSiteLoc << " @ ";
424 // Note that negative line offset is actually possible, but we use
425 // unsigned int to match line offset representation in remarks so
426 // it's directly consumable by relay advisor.
428 DIL->getLine() - DIL->getScope()->getSubprogram()->getLine();
429 uint32_t Discriminator = DIL->getBaseDiscriminator();
430 StringRef Name = DIL->getScope()->getSubprogram()->getLinkageName();
432 Name = DIL->getScope()->getSubprogram()->getName();
433 CallSiteLoc << Name.str() << ":" << llvm::utostr(Offset);
434 if (Format.outputColumn())
435 CallSiteLoc << ":" << llvm::utostr(DIL->getColumn());
436 if (Format.outputDiscriminator() && Discriminator)
437 CallSiteLoc << "." << llvm::utostr(Discriminator);
441 return CallSiteLoc.str();
444 void llvm::addLocationToRemarks(OptimizationRemark &Remark, DebugLoc DLoc) {
450 Remark << " at callsite ";
451 for (DILocation *DIL = DLoc.get(); DIL; DIL = DIL->getInlinedAt()) {
454 unsigned int Offset = DIL->getLine();
455 Offset -= DIL->getScope()->getSubprogram()->getLine();
456 unsigned int Discriminator = DIL->getBaseDiscriminator();
457 StringRef Name = DIL->getScope()->getSubprogram()->getLinkageName();
459 Name = DIL->getScope()->getSubprogram()->getName();
460 Remark << Name << ":" << ore::NV("Line", Offset) << ":"
461 << ore::NV("Column", DIL->getColumn());
463 Remark << "." << ore::NV("Disc", Discriminator);
470 void llvm::emitInlinedInto(
471 OptimizationRemarkEmitter &ORE, DebugLoc DLoc, const BasicBlock *Block,
472 const Function &Callee, const Function &Caller, bool AlwaysInline,
473 function_ref<void(OptimizationRemark &)> ExtraContext,
474 const char *PassName) {
476 StringRef RemarkName = AlwaysInline ? "AlwaysInline" : "Inlined";
477 OptimizationRemark Remark(PassName ? PassName : DEBUG_TYPE, RemarkName,
479 Remark << "'" << ore::NV("Callee", &Callee) << "' inlined into '"
480 << ore::NV("Caller", &Caller) << "'";
482 ExtraContext(Remark);
483 addLocationToRemarks(Remark, DLoc);
488 void llvm::emitInlinedIntoBasedOnCost(
489 OptimizationRemarkEmitter &ORE, DebugLoc DLoc, const BasicBlock *Block,
490 const Function &Callee, const Function &Caller, const InlineCost &IC,
491 bool ForProfileContext, const char *PassName) {
492 llvm::emitInlinedInto(
493 ORE, DLoc, Block, Callee, Caller, IC.isAlways(),
494 [&](OptimizationRemark &Remark) {
495 if (ForProfileContext)
496 Remark << " to match profiling context";
497 Remark << " with " << IC;
502 InlineAdvisor::InlineAdvisor(Module &M, FunctionAnalysisManager &FAM)
504 if (InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No) {
505 ImportedFunctionsStats =
506 std::make_unique<ImportedFunctionsInliningStatistics>();
507 ImportedFunctionsStats->setModuleInfo(M);
511 InlineAdvisor::~InlineAdvisor() {
512 if (ImportedFunctionsStats) {
513 assert(InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No);
514 ImportedFunctionsStats->dump(InlinerFunctionImportStats ==
515 InlinerFunctionImportStatsOpts::Verbose);
519 std::unique_ptr<InlineAdvice> InlineAdvisor::getMandatoryAdvice(CallBase &CB,
521 return std::make_unique<MandatoryInlineAdvice>(this, CB, getCallerORE(CB),
525 InlineAdvisor::MandatoryInliningKind
526 InlineAdvisor::getMandatoryKind(CallBase &CB, FunctionAnalysisManager &FAM,
527 OptimizationRemarkEmitter &ORE) {
528 auto &Callee = *CB.getCalledFunction();
530 auto GetTLI = [&](Function &F) -> const TargetLibraryInfo & {
531 return FAM.getResult<TargetLibraryAnalysis>(F);
534 auto &TIR = FAM.getResult<TargetIRAnalysis>(Callee);
536 auto TrivialDecision =
537 llvm::getAttributeBasedInliningDecision(CB, &Callee, TIR, GetTLI);
539 if (TrivialDecision.hasValue()) {
540 if (TrivialDecision->isSuccess())
541 return MandatoryInliningKind::Always;
543 return MandatoryInliningKind::Never;
545 return MandatoryInliningKind::NotMandatory;
548 std::unique_ptr<InlineAdvice> InlineAdvisor::getAdvice(CallBase &CB,
549 bool MandatoryOnly) {
551 return getAdviceImpl(CB);
552 bool Advice = CB.getCaller() != CB.getCalledFunction() &&
553 MandatoryInliningKind::Always ==
554 getMandatoryKind(CB, FAM, getCallerORE(CB));
555 return getMandatoryAdvice(CB, Advice);
558 OptimizationRemarkEmitter &InlineAdvisor::getCallerORE(CallBase &CB) {
559 return FAM.getResult<OptimizationRemarkEmitterAnalysis>(*CB.getCaller());
563 InlineAdvisorAnalysisPrinterPass::run(Module &M, ModuleAnalysisManager &MAM) {
564 const auto *IA = MAM.getCachedResult<InlineAdvisorAnalysis>(M);
566 OS << "No Inline Advisor\n";
568 IA->getAdvisor()->print(OS);
569 return PreservedAnalyses::all();