contrib/llvm-project/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/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"
  25
  26 #include <sstream>
  27
  28 using namespace llvm;
  29 #define DEBUG_TYPE "inline"
  30
  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");
  35
  36 /// Flag to add inline messages as callsite attributes 'inline-remark'.
  37 static cl::opt<bool>
  38     InlineRemarkAttribute("inline-remark-attribute", cl::init(false),
  39                           cl::Hidden,
  40                           cl::desc("Enable adding inline-remark attribute to"
  41                                    " callsites processed by inliner but decided"
  42                                    " to be not inlined"));
  43
  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.
  46 static cl::opt<int>
  47     InlineDeferralScale("inline-deferral-scale",
  48                         cl::desc("Scale to limit the cost of inline deferral"),
  49                         cl::init(2), cl::Hidden);
  50
  51 namespace {
  52 class DefaultInlineAdvice : public InlineAdvice {
  53 public:
  54   DefaultInlineAdvice(DefaultInlineAdvisor *Advisor, CallBase &CB,
  55                       Optional<InlineCost> OIC, OptimizationRemarkEmitter &ORE)
  56       : InlineAdvice(Advisor, CB, ORE, OIC.hasValue()), OriginalCB(&CB),
  57         OIC(OIC) {}
  58
  59 private:
  60   void recordUnsuccessfulInliningImpl(const InlineResult &Result) override {
  61     using namespace ore;
  62     llvm::setInlineRemark(*OriginalCB, std::string(Result.getFailureReason()) +
  63                                            "; " + inlineCostStr(*OIC));
  64     ORE.emit([&]() {
  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());
  69     });
  70   }
  71
  72   void recordInliningWithCalleeDeletedImpl() override {
  73     emitInlinedInto(ORE, DLoc, Block, *Callee, *Caller, *OIC);
  74   }
  75
  76   void recordInliningImpl() override {
  77     emitInlinedInto(ORE, DLoc, Block, *Callee, *Caller, *OIC);
  78   }
  79
  80 private:
  81   CallBase *const OriginalCB;
  82   Optional<InlineCost> OIC;
  83 };
  84
  85 } // namespace
  86
  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());
  95
  96   auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(Caller);
  97   auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
  98     return FAM.getResult<AssumptionAnalysis>(F);
  99   };
 100   auto GetBFI = [&](Function &F) -> BlockFrequencyInfo & {
 101     return FAM.getResult<BlockFrequencyAnalysis>(F);
 102   };
 103   auto GetTLI = [&](Function &F) -> const TargetLibraryInfo & {
 104     return FAM.getResult<TargetLibraryAnalysis>(F);
 105   };
 106
 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(
 112             DEBUG_TYPE);
 113     return getInlineCost(CB, Params, CalleeTTI, GetAssumptionCache, GetTLI,
 114                          GetBFI, PSI, RemarksEnabled ? &ORE : nullptr);
 115   };
 116   return llvm::shouldInline(CB, GetInlineCost, ORE,
 117                             Params.EnableDeferral.hasValue() &&
 118                                 Params.EnableDeferral.getValue());
 119 }
 120
 121 std::unique_ptr<InlineAdvice> DefaultInlineAdvisor::getAdvice(CallBase &CB) {
 122   auto OIC = getDefaultInlineAdvice(CB, FAM, Params);
 123   return std::make_unique<DefaultInlineAdvice>(
 124       this, CB, OIC,
 125       FAM.getResult<OptimizationRemarkEmitterAnalysis>(*CB.getCaller()));
 126 }
 127
 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) {}
 134
 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);
 139 }
 140
 141 void InlineAdvisor::freeDeletedFunctions() {
 142   for (auto *F : DeletedFunctions)
 143     delete F;
 144   DeletedFunctions.clear();
 145 }
 146
 147 void InlineAdvice::recordInliningWithCalleeDeleted() {
 148   markRecorded();
 149   Advisor->markFunctionAsDeleted(Callee);
 150   recordInliningWithCalleeDeletedImpl();
 151 }
 152
 153 AnalysisKey InlineAdvisorAnalysis::Key;
 154
 155 bool InlineAdvisorAnalysis::Result::tryCreate(InlineParams Params,
 156                                               InliningAdvisorMode Mode) {
 157   auto &FAM = MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
 158   switch (Mode) {
 159   case InliningAdvisorMode::Default:
 160     Advisor.reset(new DefaultInlineAdvisor(FAM, Params));
 161     break;
 162   case InliningAdvisorMode::Development:
 163     // To be added subsequently under conditional compilation.
 164     break;
 165   case InliningAdvisorMode::Release:
 166 #ifdef LLVM_HAVE_TF_AOT
 167     Advisor = llvm::getReleaseModeAdvisor(M, MAM);
 168 #endif
 169     break;
 170   }
 171   return !!Advisor;
 172 }
 173
 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.
 179 static bool
 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())
 184     return false;
 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
 187   // defer.
 188   if (IC.getCost() <= 0)
 189     return false;
 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
 195   // its callers.
 196   //
 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++.
 202   //
 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);
 217
 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;
 223       continue;
 224     }
 225
 226     InlineCost IC2 = GetInlineCost(*CS2);
 227     ++NumCallerCallersAnalyzed;
 228     if (!IC2) {
 229       ApplyLastCallBonus = false;
 230       continue;
 231     }
 232     if (IC2.isAlways())
 233       continue;
 234
 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();
 241       NumCallerUsers++;
 242     }
 243   }
 244
 245   if (!InliningPreventsSomeOuterInline)
 246     return false;
 247
 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;
 254
 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();
 259
 260   int TotalCost = TotalSecondaryCost + IC.getCost() * NumCallerUsers;
 261   int Allowance = IC.getCost() * InlineDeferralScale;
 262   return TotalCost < Allowance;
 263 }
 264
 265 namespace llvm {
 266 static std::basic_ostream<char> &operator<<(std::basic_ostream<char> &R,
 267                                             const ore::NV &Arg) {
 268   return R << Arg.Val;
 269 }
 270
 271 template <class RemarkT>
 272 RemarkT &operator<<(RemarkT &&R, const InlineCost &IC) {
 273   using namespace ore;
 274   if (IC.isAlways()) {
 275     R << "(cost=always)";
 276   } else if (IC.isNever()) {
 277     R << "(cost=never)";
 278   } else {
 279     R << "(cost=" << ore::NV("Cost", IC.getCost())
 280       << ", threshold=" << ore::NV("Threshold", IC.getThreshold()) << ")";
 281   }
 282   if (const char *Reason = IC.getReason())
 283     R << ": " << ore::NV("Reason", Reason);
 284   return R;
 285 }
 286 } // namespace llvm
 287
 288 std::string llvm::inlineCostStr(const InlineCost &IC) {
 289   std::stringstream Remark;
 290   Remark << IC;
 291   return Remark.str();
 292 }
 293
 294 void llvm::setInlineRemark(CallBase &CB, StringRef Message) {
 295   if (!InlineRemarkAttribute)
 296     return;
 297
 298   Attribute Attr = Attribute::get(CB.getContext(), "inline-remark", Message);
 299   CB.addAttribute(AttributeList::FunctionIndex, Attr);
 300 }
 301
 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.
 306 Optional<InlineCost>
 307 llvm::shouldInline(CallBase &CB,
 308                    function_ref<InlineCost(CallBase &CB)> GetInlineCost,
 309                    OptimizationRemarkEmitter &ORE, bool EnableDeferral) {
 310   using namespace ore;
 311
 312   InlineCost IC = GetInlineCost(CB);
 313   Instruction *Call = &CB;
 314   Function *Callee = CB.getCalledFunction();
 315   Function *Caller = CB.getCaller();
 316
 317   if (IC.isAlways()) {
 318     LLVM_DEBUG(dbgs() << "    Inlining " << inlineCostStr(IC)
 319                       << ", Call: " << CB << "\n");
 320     return IC;
 321   }
 322
 323   if (!IC) {
 324     LLVM_DEBUG(dbgs() << "    NOT Inlining " << inlineCostStr(IC)
 325                       << ", Call: " << CB << "\n");
 326     if (IC.isNever()) {
 327       ORE.emit([&]() {
 328         return OptimizationRemarkMissed(DEBUG_TYPE, "NeverInline", Call)
 329                << NV("Callee", Callee) << " not inlined into "
 330                << NV("Caller", Caller) << " because it should never be inlined "
 331                << IC;
 332       });
 333     } else {
 334       ORE.emit([&]() {
 335         return OptimizationRemarkMissed(DEBUG_TYPE, "TooCostly", Call)
 336                << NV("Callee", Callee) << " not inlined into "
 337                << NV("Caller", Caller) << " because too costly to inline "
 338                << IC;
 339       });
 340     }
 341     setInlineRemark(CB, inlineCostStr(IC));
 342     return None;
 343   }
 344
 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');
 351     ORE.emit([&]() {
 352       return OptimizationRemarkMissed(DEBUG_TYPE, "IncreaseCostInOtherContexts",
 353                                       Call)
 354              << "Not inlining. Cost of inlining " << NV("Callee", Callee)
 355              << " increases the cost of inlining " << NV("Caller", Caller)
 356              << " in other contexts";
 357     });
 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.
 361     return None;
 362   }
 363
 364   LLVM_DEBUG(dbgs() << "    Inlining " << inlineCostStr(IC) << ", Call: " << CB
 365                     << '\n');
 366   return IC;
 367 }
 368
 369 void llvm::addLocationToRemarks(OptimizationRemark &Remark, DebugLoc DLoc) {
 370   if (!DLoc.get())
 371     return;
 372
 373   bool First = true;
 374   Remark << " at callsite ";
 375   for (DILocation *DIL = DLoc.get(); DIL; DIL = DIL->getInlinedAt()) {
 376     if (!First)
 377       Remark << " @ ";
 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();
 382     if (Name.empty())
 383       Name = DIL->getScope()->getSubprogram()->getName();
 384     Remark << Name << ":" << ore::NV("Line", Offset);
 385     if (Discriminator)
 386       Remark << "." << ore::NV("Disc", Discriminator);
 387     First = false;
 388   }
 389 }
 390
 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) {
 395   ORE.emit([&]() {
 396     bool AlwaysInline = IC.isAlways();
 397     StringRef RemarkName = AlwaysInline ? "AlwaysInline" : "Inlined";
 398     OptimizationRemark Remark(PassName ? PassName : DEBUG_TYPE, RemarkName,
 399                               DLoc, Block);
 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);
 406     return Remark;
 407   });
 408 }