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 } 409