llvm/lib/Analysis/InlineAdvisor.cpp

   1 //===- InlineAdvisor.cpp - analysis pass implementation -------------------===//
   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 InlineAdvisorAnalysis and DefaultInlineAdvisor, and
  10 // related types.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  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"
  26
  27 using namespace llvm;
  28 #define DEBUG_TYPE "inline"
  29
  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");
  34
  35 /// Flag to add inline messages as callsite attributes 'inline-remark'.
  36 static cl::opt<bool>
  37     InlineRemarkAttribute("inline-remark-attribute", cl::init(false),
  38                           cl::Hidden,
  39                           cl::desc("Enable adding inline-remark attribute to"
  40                                    " callsites processed by inliner but decided"
  41                                    " to be not inlined"));
  42
  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.
  45 static cl::opt<int>
  46     InlineDeferralScale("inline-deferral-scale",
  47                         cl::desc("Scale to limit the cost of inline deferral"),
  48                         cl::init(2), cl::Hidden);
  49
  50 extern cl::opt<InlinerFunctionImportStatsOpts> InlinerFunctionImportStats;
  51
  52 void DefaultInlineAdvice::recordUnsuccessfulInliningImpl(
  53     const InlineResult &Result) {
  54   using namespace ore;
  55   llvm::setInlineRemark(*OriginalCB, std::string(Result.getFailureReason()) +
  56                                          "; " + inlineCostStr(*OIC));
  57   ORE.emit([&]() {
  58     return OptimizationRemarkMissed(DEBUG_TYPE, "NotInlined", DLoc, Block)
  59            << "'" << NV("Callee", Callee) << "' is not inlined into '"
  60            << "'" << NV("Caller", Caller)
  61            << "': " << NV("Reason", Result.getFailureReason());
  62   });
  63 }
  64
  65 void DefaultInlineAdvice::recordInliningWithCalleeDeletedImpl() {
  66   if (EmitRemarks)
  67     emitInlinedInto(ORE, DLoc, Block, *Callee, *Caller, *OIC);
  68 }
  69
  70 void DefaultInlineAdvice::recordInliningImpl() {
  71   if (EmitRemarks)
  72     emitInlinedInto(ORE, DLoc, Block, *Callee, *Caller, *OIC);
  73 }
  74
  75 llvm::Optional<llvm::InlineCost> static getDefaultInlineAdvice(
  76     CallBase &CB, FunctionAnalysisManager &FAM, const InlineParams &Params) {
  77   Function &Caller = *CB.getCaller();
  78   ProfileSummaryInfo *PSI =
  79       FAM.getResult<ModuleAnalysisManagerFunctionProxy>(Caller)
  80           .getCachedResult<ProfileSummaryAnalysis>(
  81               *CB.getParent()->getParent()->getParent());
  82
  83   auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(Caller);
  84   auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
  85     return FAM.getResult<AssumptionAnalysis>(F);
  86   };
  87   auto GetBFI = [&](Function &F) -> BlockFrequencyInfo & {
  88     return FAM.getResult<BlockFrequencyAnalysis>(F);
  89   };
  90   auto GetTLI = [&](Function &F) -> const TargetLibraryInfo & {
  91     return FAM.getResult<TargetLibraryAnalysis>(F);
  92   };
  93
  94   auto GetInlineCost = [&](CallBase &CB) {
  95     Function &Callee = *CB.getCalledFunction();
  96     auto &CalleeTTI = FAM.getResult<TargetIRAnalysis>(Callee);
  97     bool RemarksEnabled =
  98         Callee.getContext().getDiagHandlerPtr()->isMissedOptRemarkEnabled(
  99             DEBUG_TYPE);
 100     return getInlineCost(CB, Params, CalleeTTI, GetAssumptionCache, GetTLI,
 101                          GetBFI, PSI, RemarksEnabled ? &ORE : nullptr);
 102   };
 103   return llvm::shouldInline(CB, GetInlineCost, ORE,
 104                             Params.EnableDeferral.getValueOr(false));
 105 }
 106
 107 std::unique_ptr<InlineAdvice>
 108 DefaultInlineAdvisor::getAdviceImpl(CallBase &CB) {
 109   auto OIC = getDefaultInlineAdvice(CB, FAM, Params);
 110   return std::make_unique<DefaultInlineAdvice>(
 111       this, CB, OIC,
 112       FAM.getResult<OptimizationRemarkEmitterAnalysis>(*CB.getCaller()));
 113 }
 114
 115 InlineAdvice::InlineAdvice(InlineAdvisor *Advisor, CallBase &CB,
 116                            OptimizationRemarkEmitter &ORE,
 117                            bool IsInliningRecommended)
 118     : Advisor(Advisor), Caller(CB.getCaller()), Callee(CB.getCalledFunction()),
 119       DLoc(CB.getDebugLoc()), Block(CB.getParent()), ORE(ORE),
 120       IsInliningRecommended(IsInliningRecommended) {}
 121
 122 void InlineAdvisor::markFunctionAsDeleted(Function *F) {
 123   assert((!DeletedFunctions.count(F)) &&
 124          "Cannot put cause a function to become dead twice!");
 125   DeletedFunctions.insert(F);
 126 }
 127
 128 void InlineAdvisor::freeDeletedFunctions() {
 129   for (auto *F : DeletedFunctions)
 130     delete F;
 131   DeletedFunctions.clear();
 132 }
 133
 134 void InlineAdvice::recordInlineStatsIfNeeded() {
 135   if (Advisor->ImportedFunctionsStats)
 136     Advisor->ImportedFunctionsStats->recordInline(*Caller, *Callee);
 137 }
 138
 139 void InlineAdvice::recordInlining() {
 140   markRecorded();
 141   recordInlineStatsIfNeeded();
 142   recordInliningImpl();
 143 }
 144
 145 void InlineAdvice::recordInliningWithCalleeDeleted() {
 146   markRecorded();
 147   recordInlineStatsIfNeeded();
 148   Advisor->markFunctionAsDeleted(Callee);
 149   recordInliningWithCalleeDeletedImpl();
 150 }
 151
 152 AnalysisKey InlineAdvisorAnalysis::Key;
 153
 154 bool InlineAdvisorAnalysis::Result::tryCreate(InlineParams Params,
 155                                               InliningAdvisorMode Mode,
 156                                               StringRef ReplayFile) {
 157   auto &FAM = MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
 158   switch (Mode) {
 159   case InliningAdvisorMode::Default:
 160     LLVM_DEBUG(dbgs() << "Using default inliner heuristic.\n");
 161     Advisor.reset(new DefaultInlineAdvisor(M, FAM, Params));
 162     // Restrict replay to default advisor, ML advisors are stateful so
 163     // replay will need augmentations to interleave with them correctly.
 164     if (!ReplayFile.empty()) {
 165       Advisor = std::make_unique<ReplayInlineAdvisor>(
 166           M, FAM, M.getContext(), std::move(Advisor), ReplayFile,
 167           /* EmitRemarks =*/true);
 168     }
 169     break;
 170   case InliningAdvisorMode::Development:
 171 #ifdef LLVM_HAVE_TF_API
 172     LLVM_DEBUG(dbgs() << "Using development-mode inliner policy.\n");
 173     Advisor =
 174         llvm::getDevelopmentModeAdvisor(M, MAM, [&FAM, Params](CallBase &CB) {
 175           auto OIC = getDefaultInlineAdvice(CB, FAM, Params);
 176           return OIC.hasValue();
 177         });
 178 #endif
 179     break;
 180   case InliningAdvisorMode::Release:
 181 #ifdef LLVM_HAVE_TF_AOT
 182     LLVM_DEBUG(dbgs() << "Using release-mode inliner policy.\n");
 183     Advisor = llvm::getReleaseModeAdvisor(M, MAM);
 184 #endif
 185     break;
 186   }
 187
 188   return !!Advisor;
 189 }
 190
 191 /// Return true if inlining of CB can block the caller from being
 192 /// inlined which is proved to be more beneficial. \p IC is the
 193 /// estimated inline cost associated with callsite \p CB.
 194 /// \p TotalSecondaryCost will be set to the estimated cost of inlining the
 195 /// caller if \p CB is suppressed for inlining.
 196 static bool
 197 shouldBeDeferred(Function *Caller, InlineCost IC, int &TotalSecondaryCost,
 198                  function_ref<InlineCost(CallBase &CB)> GetInlineCost) {
 199   // For now we only handle local or inline functions.
 200   if (!Caller->hasLocalLinkage() && !Caller->hasLinkOnceODRLinkage())
 201     return false;
 202   // If the cost of inlining CB is non-positive, it is not going to prevent the
 203   // caller from being inlined into its callers and hence we don't need to
 204   // defer.
 205   if (IC.getCost() <= 0)
 206     return false;
 207   // Try to detect the case where the current inlining candidate caller (call
 208   // it B) is a static or linkonce-ODR function and is an inlining candidate
 209   // elsewhere, and the current candidate callee (call it C) is large enough
 210   // that inlining it into B would make B too big to inline later. In these
 211   // circumstances it may be best not to inline C into B, but to inline B into
 212   // its callers.
 213   //
 214   // This only applies to static and linkonce-ODR functions because those are
 215   // expected to be available for inlining in the translation units where they
 216   // are used. Thus we will always have the opportunity to make local inlining
 217   // decisions. Importantly the linkonce-ODR linkage covers inline functions
 218   // and templates in C++.
 219   //
 220   // FIXME: All of this logic should be sunk into getInlineCost. It relies on
 221   // the internal implementation of the inline cost metrics rather than
 222   // treating them as truly abstract units etc.
 223   TotalSecondaryCost = 0;
 224   // The candidate cost to be imposed upon the current function.
 225   int CandidateCost = IC.getCost() - 1;
 226   // If the caller has local linkage and can be inlined to all its callers, we
 227   // can apply a huge negative bonus to TotalSecondaryCost.
 228   bool ApplyLastCallBonus = Caller->hasLocalLinkage() && !Caller->hasOneUse();
 229   // This bool tracks what happens if we DO inline C into B.
 230   bool InliningPreventsSomeOuterInline = false;
 231   unsigned NumCallerUsers = 0;
 232   for (User *U : Caller->users()) {
 233     CallBase *CS2 = dyn_cast<CallBase>(U);
 234
 235     // If this isn't a call to Caller (it could be some other sort
 236     // of reference) skip it.  Such references will prevent the caller
 237     // from being removed.
 238     if (!CS2 || CS2->getCalledFunction() != Caller) {
 239       ApplyLastCallBonus = false;
 240       continue;
 241     }
 242
 243     InlineCost IC2 = GetInlineCost(*CS2);
 244     ++NumCallerCallersAnalyzed;
 245     if (!IC2) {
 246       ApplyLastCallBonus = false;
 247       continue;
 248     }
 249     if (IC2.isAlways())
 250       continue;
 251
 252     // See if inlining of the original callsite would erase the cost delta of
 253     // this callsite. We subtract off the penalty for the call instruction,
 254     // which we would be deleting.
 255     if (IC2.getCostDelta() <= CandidateCost) {
 256       InliningPreventsSomeOuterInline = true;
 257       TotalSecondaryCost += IC2.getCost();
 258       NumCallerUsers++;
 259     }
 260   }
 261
 262   if (!InliningPreventsSomeOuterInline)
 263     return false;
 264
 265   // If all outer calls to Caller would get inlined, the cost for the last
 266   // one is set very low by getInlineCost, in anticipation that Caller will
 267   // be removed entirely.  We did not account for this above unless there
 268   // is only one caller of Caller.
 269   if (ApplyLastCallBonus)
 270     TotalSecondaryCost -= InlineConstants::LastCallToStaticBonus;
 271
 272   // If InlineDeferralScale is negative, then ignore the cost of primary
 273   // inlining -- IC.getCost() multiplied by the number of callers to Caller.
 274   if (InlineDeferralScale < 0)
 275     return TotalSecondaryCost < IC.getCost();
 276
 277   int TotalCost = TotalSecondaryCost + IC.getCost() * NumCallerUsers;
 278   int Allowance = IC.getCost() * InlineDeferralScale;
 279   return TotalCost < Allowance;
 280 }
 281
 282 namespace llvm {
 283 static raw_ostream &operator<<(raw_ostream &R, const ore::NV &Arg) {
 284   return R << Arg.Val;
 285 }
 286
 287 template <class RemarkT>
 288 RemarkT &operator<<(RemarkT &&R, const InlineCost &IC) {
 289   using namespace ore;
 290   if (IC.isAlways()) {
 291     R << "(cost=always)";
 292   } else if (IC.isNever()) {
 293     R << "(cost=never)";
 294   } else {
 295     R << "(cost=" << ore::NV("Cost", IC.getCost())
 296       << ", threshold=" << ore::NV("Threshold", IC.getThreshold()) << ")";
 297   }
 298   if (const char *Reason = IC.getReason())
 299     R << ": " << ore::NV("Reason", Reason);
 300   return R;
 301 }
 302 } // namespace llvm
 303
 304 std::string llvm::inlineCostStr(const InlineCost &IC) {
 305   std::string Buffer;
 306   raw_string_ostream Remark(Buffer);
 307   Remark << IC;
 308   return Remark.str();
 309 }
 310
 311 void llvm::setInlineRemark(CallBase &CB, StringRef Message) {
 312   if (!InlineRemarkAttribute)
 313     return;
 314
 315   Attribute Attr = Attribute::get(CB.getContext(), "inline-remark", Message);
 316   CB.addFnAttr(Attr);
 317 }
 318
 319 /// Return the cost only if the inliner should attempt to inline at the given
 320 /// CallSite. If we return the cost, we will emit an optimisation remark later
 321 /// using that cost, so we won't do so from this function. Return None if
 322 /// inlining should not be attempted.
 323 Optional<InlineCost>
 324 llvm::shouldInline(CallBase &CB,
 325                    function_ref<InlineCost(CallBase &CB)> GetInlineCost,
 326                    OptimizationRemarkEmitter &ORE, bool EnableDeferral) {
 327   using namespace ore;
 328
 329   InlineCost IC = GetInlineCost(CB);
 330   Instruction *Call = &CB;
 331   Function *Callee = CB.getCalledFunction();
 332   Function *Caller = CB.getCaller();
 333
 334   if (IC.isAlways()) {
 335     LLVM_DEBUG(dbgs() << "    Inlining " << inlineCostStr(IC)
 336                       << ", Call: " << CB << "\n");
 337     return IC;
 338   }
 339
 340   if (!IC) {
 341     LLVM_DEBUG(dbgs() << "    NOT Inlining " << inlineCostStr(IC)
 342                       << ", Call: " << CB << "\n");
 343     if (IC.isNever()) {
 344       ORE.emit([&]() {
 345         return OptimizationRemarkMissed(DEBUG_TYPE, "NeverInline", Call)
 346                << "'" << NV("Callee", Callee) << "' not inlined into '"
 347                << NV("Caller", Caller)
 348                << "' because it should never be inlined " << IC;
 349       });
 350     } else {
 351       ORE.emit([&]() {
 352         return OptimizationRemarkMissed(DEBUG_TYPE, "TooCostly", Call)
 353                << "'" << NV("Callee", Callee) << "' not inlined into '"
 354                << NV("Caller", Caller) << "' because too costly to inline "
 355                << IC;
 356       });
 357     }
 358     setInlineRemark(CB, inlineCostStr(IC));
 359     return None;
 360   }
 361
 362   int TotalSecondaryCost = 0;
 363   if (EnableDeferral &&
 364       shouldBeDeferred(Caller, IC, TotalSecondaryCost, GetInlineCost)) {
 365     LLVM_DEBUG(dbgs() << "    NOT Inlining: " << CB
 366                       << " Cost = " << IC.getCost()
 367                       << ", outer Cost = " << TotalSecondaryCost << '\n');
 368     ORE.emit([&]() {
 369       return OptimizationRemarkMissed(DEBUG_TYPE, "IncreaseCostInOtherContexts",
 370                                       Call)
 371              << "Not inlining. Cost of inlining '" << NV("Callee", Callee)
 372              << "' increases the cost of inlining '" << NV("Caller", Caller)
 373              << "' in other contexts";
 374     });
 375     setInlineRemark(CB, "deferred");
 376     // IC does not bool() to false, so get an InlineCost that will.
 377     // This will not be inspected to make an error message.
 378     return None;
 379   }
 380
 381   LLVM_DEBUG(dbgs() << "    Inlining " << inlineCostStr(IC) << ", Call: " << CB
 382                     << '\n');
 383   return IC;
 384 }
 385
 386 std::string llvm::getCallSiteLocation(DebugLoc DLoc) {
 387   std::string Buffer;
 388   raw_string_ostream CallSiteLoc(Buffer);
 389   bool First = true;
 390   for (DILocation *DIL = DLoc.get(); DIL; DIL = DIL->getInlinedAt()) {
 391     if (!First)
 392       CallSiteLoc << " @ ";
 393     // Note that negative line offset is actually possible, but we use
 394     // unsigned int to match line offset representation in remarks so
 395     // it's directly consumable by relay advisor.
 396     uint32_t Offset =
 397         DIL->getLine() - DIL->getScope()->getSubprogram()->getLine();
 398     uint32_t Discriminator = DIL->getBaseDiscriminator();
 399     StringRef Name = DIL->getScope()->getSubprogram()->getLinkageName();
 400     if (Name.empty())
 401       Name = DIL->getScope()->getSubprogram()->getName();
 402     CallSiteLoc << Name.str() << ":" << llvm::utostr(Offset) << ":"
 403                 << llvm::utostr(DIL->getColumn());
 404     if (Discriminator)
 405       CallSiteLoc << "." << llvm::utostr(Discriminator);
 406     First = false;
 407   }
 408
 409   return CallSiteLoc.str();
 410 }
 411
 412 void llvm::addLocationToRemarks(OptimizationRemark &Remark, DebugLoc DLoc) {
 413   if (!DLoc.get()) {
 414     return;
 415   }
 416
 417   bool First = true;
 418   Remark << " at callsite ";
 419   for (DILocation *DIL = DLoc.get(); DIL; DIL = DIL->getInlinedAt()) {
 420     if (!First)
 421       Remark << " @ ";
 422     unsigned int Offset = DIL->getLine();
 423     Offset -= DIL->getScope()->getSubprogram()->getLine();
 424     unsigned int Discriminator = DIL->getBaseDiscriminator();
 425     StringRef Name = DIL->getScope()->getSubprogram()->getLinkageName();
 426     if (Name.empty())
 427       Name = DIL->getScope()->getSubprogram()->getName();
 428     Remark << Name << ":" << ore::NV("Line", Offset) << ":"
 429            << ore::NV("Column", DIL->getColumn());
 430     if (Discriminator)
 431       Remark << "." << ore::NV("Disc", Discriminator);
 432     First = false;
 433   }
 434
 435   Remark << ";";
 436 }
 437
 438 void llvm::emitInlinedInto(OptimizationRemarkEmitter &ORE, DebugLoc DLoc,
 439                            const BasicBlock *Block, const Function &Callee,
 440                            const Function &Caller, const InlineCost &IC,
 441                            bool ForProfileContext, const char *PassName) {
 442   ORE.emit([&]() {
 443     bool AlwaysInline = IC.isAlways();
 444     StringRef RemarkName = AlwaysInline ? "AlwaysInline" : "Inlined";
 445     OptimizationRemark Remark(PassName ? PassName : DEBUG_TYPE, RemarkName,
 446                               DLoc, Block);
 447     Remark << "'" << ore::NV("Callee", &Callee) << "' inlined into '"
 448            << ore::NV("Caller", &Caller) << "'";
 449     if (ForProfileContext)
 450       Remark << " to match profiling context";
 451     Remark << " with " << IC;
 452     addLocationToRemarks(Remark, DLoc);
 453     return Remark;
 454   });
 455 }
 456
 457 InlineAdvisor::InlineAdvisor(Module &M, FunctionAnalysisManager &FAM)
 458     : M(M), FAM(FAM) {
 459   if (InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No) {
 460     ImportedFunctionsStats =
 461         std::make_unique<ImportedFunctionsInliningStatistics>();
 462     ImportedFunctionsStats->setModuleInfo(M);
 463   }
 464 }
 465
 466 InlineAdvisor::~InlineAdvisor() {
 467   if (ImportedFunctionsStats) {
 468     assert(InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No);
 469     ImportedFunctionsStats->dump(InlinerFunctionImportStats ==
 470                                  InlinerFunctionImportStatsOpts::Verbose);
 471   }
 472
 473   freeDeletedFunctions();
 474 }
 475
 476 std::unique_ptr<InlineAdvice> InlineAdvisor::getMandatoryAdvice(CallBase &CB,
 477                                                                 bool Advice) {
 478   return std::make_unique<InlineAdvice>(this, CB, getCallerORE(CB), Advice);
 479 }
 480
 481 InlineAdvisor::MandatoryInliningKind
 482 InlineAdvisor::getMandatoryKind(CallBase &CB, FunctionAnalysisManager &FAM,
 483                                 OptimizationRemarkEmitter &ORE) {
 484   auto &Callee = *CB.getCalledFunction();
 485
 486   auto GetTLI = [&](Function &F) -> const TargetLibraryInfo & {
 487     return FAM.getResult<TargetLibraryAnalysis>(F);
 488   };
 489
 490   auto &TIR = FAM.getResult<TargetIRAnalysis>(Callee);
 491
 492   auto TrivialDecision =
 493       llvm::getAttributeBasedInliningDecision(CB, &Callee, TIR, GetTLI);
 494
 495   if (TrivialDecision.hasValue()) {
 496     if (TrivialDecision->isSuccess())
 497       return MandatoryInliningKind::Always;
 498     else
 499       return MandatoryInliningKind::Never;
 500   }
 501   return MandatoryInliningKind::NotMandatory;
 502 }
 503
 504 std::unique_ptr<InlineAdvice> InlineAdvisor::getAdvice(CallBase &CB,
 505                                                        bool MandatoryOnly) {
 506   if (!MandatoryOnly)
 507     return getAdviceImpl(CB);
 508   bool Advice = CB.getCaller() != CB.getCalledFunction() &&
 509                 MandatoryInliningKind::Always ==
 510                     getMandatoryKind(CB, FAM, getCallerORE(CB));
 511   return getMandatoryAdvice(CB, Advice);
 512 }
 513
 514 OptimizationRemarkEmitter &InlineAdvisor::getCallerORE(CallBase &CB) {
 515   return FAM.getResult<OptimizationRemarkEmitterAnalysis>(*CB.getCaller());
 516 }