1 //===- Inliner.cpp - Code common to all inliners --------------------------===// 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 the mechanics required to implement inlining without 10 // missing any calls and updating the call graph. The decisions of which calls 11 // are profitable to inline are implemented elsewhere. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "llvm/Transforms/IPO/Inliner.h" 16 #include "llvm/ADT/DenseMap.h" 17 #include "llvm/ADT/Optional.h" 18 #include "llvm/ADT/PriorityWorklist.h" 19 #include "llvm/ADT/STLExtras.h" 20 #include "llvm/ADT/ScopeExit.h" 21 #include "llvm/ADT/SetVector.h" 22 #include "llvm/ADT/SmallPtrSet.h" 23 #include "llvm/ADT/SmallVector.h" 24 #include "llvm/ADT/Statistic.h" 25 #include "llvm/ADT/StringExtras.h" 26 #include "llvm/ADT/StringRef.h" 27 #include "llvm/Analysis/AssumptionCache.h" 28 #include "llvm/Analysis/BasicAliasAnalysis.h" 29 #include "llvm/Analysis/BlockFrequencyInfo.h" 30 #include "llvm/Analysis/CGSCCPassManager.h" 31 #include "llvm/Analysis/CallGraph.h" 32 #include "llvm/Analysis/InlineAdvisor.h" 33 #include "llvm/Analysis/InlineCost.h" 34 #include "llvm/Analysis/InlineOrder.h" 35 #include "llvm/Analysis/LazyCallGraph.h" 36 #include "llvm/Analysis/OptimizationRemarkEmitter.h" 37 #include "llvm/Analysis/ProfileSummaryInfo.h" 38 #include "llvm/Analysis/ReplayInlineAdvisor.h" 39 #include "llvm/Analysis/TargetLibraryInfo.h" 40 #include "llvm/Analysis/Utils/ImportedFunctionsInliningStatistics.h" 41 #include "llvm/IR/Attributes.h" 42 #include "llvm/IR/BasicBlock.h" 43 #include "llvm/IR/DebugLoc.h" 44 #include "llvm/IR/DerivedTypes.h" 45 #include "llvm/IR/DiagnosticInfo.h" 46 #include "llvm/IR/Function.h" 47 #include "llvm/IR/InstIterator.h" 48 #include "llvm/IR/Instruction.h" 49 #include "llvm/IR/Instructions.h" 50 #include "llvm/IR/IntrinsicInst.h" 51 #include "llvm/IR/Metadata.h" 52 #include "llvm/IR/Module.h" 53 #include "llvm/IR/PassManager.h" 54 #include "llvm/IR/User.h" 55 #include "llvm/IR/Value.h" 56 #include "llvm/Pass.h" 57 #include "llvm/Support/Casting.h" 58 #include "llvm/Support/CommandLine.h" 59 #include "llvm/Support/Debug.h" 60 #include "llvm/Support/raw_ostream.h" 61 #include "llvm/Transforms/Utils/CallPromotionUtils.h" 62 #include "llvm/Transforms/Utils/Cloning.h" 63 #include "llvm/Transforms/Utils/Local.h" 64 #include "llvm/Transforms/Utils/ModuleUtils.h" 65 #include <algorithm> 66 #include <cassert> 67 #include <functional> 68 #include <utility> 69 #include <vector> 70 71 using namespace llvm; 72 73 #define DEBUG_TYPE "inline" 74 75 STATISTIC(NumInlined, "Number of functions inlined"); 76 STATISTIC(NumCallsDeleted, "Number of call sites deleted, not inlined"); 77 STATISTIC(NumDeleted, "Number of functions deleted because all callers found"); 78 STATISTIC(NumMergedAllocas, "Number of allocas merged together"); 79 80 /// Flag to disable manual alloca merging. 81 /// 82 /// Merging of allocas was originally done as a stack-size saving technique 83 /// prior to LLVM's code generator having support for stack coloring based on 84 /// lifetime markers. It is now in the process of being removed. To experiment 85 /// with disabling it and relying fully on lifetime marker based stack 86 /// coloring, you can pass this flag to LLVM. 87 static cl::opt<bool> 88 DisableInlinedAllocaMerging("disable-inlined-alloca-merging", 89 cl::init(false), cl::Hidden); 90 91 static cl::opt<int> IntraSCCCostMultiplier( 92 "intra-scc-cost-multiplier", cl::init(2), cl::Hidden, 93 cl::desc( 94 "Cost multiplier to multiply onto inlined call sites where the " 95 "new call was previously an intra-SCC call (not relevant when the " 96 "original call was already intra-SCC). This can accumulate over " 97 "multiple inlinings (e.g. if a call site already had a cost " 98 "multiplier and one of its inlined calls was also subject to " 99 "this, the inlined call would have the original multiplier " 100 "multiplied by intra-scc-cost-multiplier). This is to prevent tons of " 101 "inlining through a child SCC which can cause terrible compile times")); 102 103 /// A flag for test, so we can print the content of the advisor when running it 104 /// as part of the default (e.g. -O3) pipeline. 105 static cl::opt<bool> KeepAdvisorForPrinting("keep-inline-advisor-for-printing", 106 cl::init(false), cl::Hidden); 107 108 /// Allows printing the contents of the advisor after each SCC inliner pass. 109 static cl::opt<bool> 110 EnablePostSCCAdvisorPrinting("enable-scc-inline-advisor-printing", 111 cl::init(false), cl::Hidden); 112 113 extern cl::opt<InlinerFunctionImportStatsOpts> InlinerFunctionImportStats; 114 115 static cl::opt<std::string> CGSCCInlineReplayFile( 116 "cgscc-inline-replay", cl::init(""), cl::value_desc("filename"), 117 cl::desc( 118 "Optimization remarks file containing inline remarks to be replayed " 119 "by cgscc inlining."), 120 cl::Hidden); 121 122 static cl::opt<ReplayInlinerSettings::Scope> CGSCCInlineReplayScope( 123 "cgscc-inline-replay-scope", 124 cl::init(ReplayInlinerSettings::Scope::Function), 125 cl::values(clEnumValN(ReplayInlinerSettings::Scope::Function, "Function", 126 "Replay on functions that have remarks associated " 127 "with them (default)"), 128 clEnumValN(ReplayInlinerSettings::Scope::Module, "Module", 129 "Replay on the entire module")), 130 cl::desc("Whether inline replay should be applied to the entire " 131 "Module or just the Functions (default) that are present as " 132 "callers in remarks during cgscc inlining."), 133 cl::Hidden); 134 135 static cl::opt<ReplayInlinerSettings::Fallback> CGSCCInlineReplayFallback( 136 "cgscc-inline-replay-fallback", 137 cl::init(ReplayInlinerSettings::Fallback::Original), 138 cl::values( 139 clEnumValN( 140 ReplayInlinerSettings::Fallback::Original, "Original", 141 "All decisions not in replay send to original advisor (default)"), 142 clEnumValN(ReplayInlinerSettings::Fallback::AlwaysInline, 143 "AlwaysInline", "All decisions not in replay are inlined"), 144 clEnumValN(ReplayInlinerSettings::Fallback::NeverInline, "NeverInline", 145 "All decisions not in replay are not inlined")), 146 cl::desc( 147 "How cgscc inline replay treats sites that don't come from the replay. " 148 "Original: defers to original advisor, AlwaysInline: inline all sites " 149 "not in replay, NeverInline: inline no sites not in replay"), 150 cl::Hidden); 151 152 static cl::opt<CallSiteFormat::Format> CGSCCInlineReplayFormat( 153 "cgscc-inline-replay-format", 154 cl::init(CallSiteFormat::Format::LineColumnDiscriminator), 155 cl::values( 156 clEnumValN(CallSiteFormat::Format::Line, "Line", "<Line Number>"), 157 clEnumValN(CallSiteFormat::Format::LineColumn, "LineColumn", 158 "<Line Number>:<Column Number>"), 159 clEnumValN(CallSiteFormat::Format::LineDiscriminator, 160 "LineDiscriminator", "<Line Number>.<Discriminator>"), 161 clEnumValN(CallSiteFormat::Format::LineColumnDiscriminator, 162 "LineColumnDiscriminator", 163 "<Line Number>:<Column Number>.<Discriminator> (default)")), 164 cl::desc("How cgscc inline replay file is formatted"), cl::Hidden); 165 166 LegacyInlinerBase::LegacyInlinerBase(char &ID) : CallGraphSCCPass(ID) {} 167 168 LegacyInlinerBase::LegacyInlinerBase(char &ID, bool InsertLifetime) 169 : CallGraphSCCPass(ID), InsertLifetime(InsertLifetime) {} 170 171 /// For this class, we declare that we require and preserve the call graph. 172 /// If the derived class implements this method, it should 173 /// always explicitly call the implementation here. 174 void LegacyInlinerBase::getAnalysisUsage(AnalysisUsage &AU) const { 175 AU.addRequired<AssumptionCacheTracker>(); 176 AU.addRequired<ProfileSummaryInfoWrapperPass>(); 177 AU.addRequired<TargetLibraryInfoWrapperPass>(); 178 getAAResultsAnalysisUsage(AU); 179 CallGraphSCCPass::getAnalysisUsage(AU); 180 } 181 182 using InlinedArrayAllocasTy = DenseMap<ArrayType *, std::vector<AllocaInst *>>; 183 184 /// Look at all of the allocas that we inlined through this call site. If we 185 /// have already inlined other allocas through other calls into this function, 186 /// then we know that they have disjoint lifetimes and that we can merge them. 187 /// 188 /// There are many heuristics possible for merging these allocas, and the 189 /// different options have different tradeoffs. One thing that we *really* 190 /// don't want to hurt is SRoA: once inlining happens, often allocas are no 191 /// longer address taken and so they can be promoted. 192 /// 193 /// Our "solution" for that is to only merge allocas whose outermost type is an 194 /// array type. These are usually not promoted because someone is using a 195 /// variable index into them. These are also often the most important ones to 196 /// merge. 197 /// 198 /// A better solution would be to have real memory lifetime markers in the IR 199 /// and not have the inliner do any merging of allocas at all. This would 200 /// allow the backend to do proper stack slot coloring of all allocas that 201 /// *actually make it to the backend*, which is really what we want. 202 /// 203 /// Because we don't have this information, we do this simple and useful hack. 204 static void mergeInlinedArrayAllocas(Function *Caller, InlineFunctionInfo &IFI, 205 InlinedArrayAllocasTy &InlinedArrayAllocas, 206 int InlineHistory) { 207 SmallPtrSet<AllocaInst *, 16> UsedAllocas; 208 209 // When processing our SCC, check to see if the call site was inlined from 210 // some other call site. For example, if we're processing "A" in this code: 211 // A() { B() } 212 // B() { x = alloca ... C() } 213 // C() { y = alloca ... } 214 // Assume that C was not inlined into B initially, and so we're processing A 215 // and decide to inline B into A. Doing this makes an alloca available for 216 // reuse and makes a callsite (C) available for inlining. When we process 217 // the C call site we don't want to do any alloca merging between X and Y 218 // because their scopes are not disjoint. We could make this smarter by 219 // keeping track of the inline history for each alloca in the 220 // InlinedArrayAllocas but this isn't likely to be a significant win. 221 if (InlineHistory != -1) // Only do merging for top-level call sites in SCC. 222 return; 223 224 // Loop over all the allocas we have so far and see if they can be merged with 225 // a previously inlined alloca. If not, remember that we had it. 226 for (unsigned AllocaNo = 0, E = IFI.StaticAllocas.size(); AllocaNo != E; 227 ++AllocaNo) { 228 AllocaInst *AI = IFI.StaticAllocas[AllocaNo]; 229 230 // Don't bother trying to merge array allocations (they will usually be 231 // canonicalized to be an allocation *of* an array), or allocations whose 232 // type is not itself an array (because we're afraid of pessimizing SRoA). 233 ArrayType *ATy = dyn_cast<ArrayType>(AI->getAllocatedType()); 234 if (!ATy || AI->isArrayAllocation()) 235 continue; 236 237 // Get the list of all available allocas for this array type. 238 std::vector<AllocaInst *> &AllocasForType = InlinedArrayAllocas[ATy]; 239 240 // Loop over the allocas in AllocasForType to see if we can reuse one. Note 241 // that we have to be careful not to reuse the same "available" alloca for 242 // multiple different allocas that we just inlined, we use the 'UsedAllocas' 243 // set to keep track of which "available" allocas are being used by this 244 // function. Also, AllocasForType can be empty of course! 245 bool MergedAwayAlloca = false; 246 for (AllocaInst *AvailableAlloca : AllocasForType) { 247 Align Align1 = AI->getAlign(); 248 Align Align2 = AvailableAlloca->getAlign(); 249 250 // The available alloca has to be in the right function, not in some other 251 // function in this SCC. 252 if (AvailableAlloca->getParent() != AI->getParent()) 253 continue; 254 255 // If the inlined function already uses this alloca then we can't reuse 256 // it. 257 if (!UsedAllocas.insert(AvailableAlloca).second) 258 continue; 259 260 // Otherwise, we *can* reuse it, RAUW AI into AvailableAlloca and declare 261 // success! 262 LLVM_DEBUG(dbgs() << " ***MERGED ALLOCA: " << *AI 263 << "\n\t\tINTO: " << *AvailableAlloca << '\n'); 264 265 // Move affected dbg.declare calls immediately after the new alloca to 266 // avoid the situation when a dbg.declare precedes its alloca. 267 if (auto *L = LocalAsMetadata::getIfExists(AI)) 268 if (auto *MDV = MetadataAsValue::getIfExists(AI->getContext(), L)) 269 for (User *U : MDV->users()) 270 if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(U)) 271 DDI->moveBefore(AvailableAlloca->getNextNode()); 272 273 AI->replaceAllUsesWith(AvailableAlloca); 274 275 if (Align1 > Align2) 276 AvailableAlloca->setAlignment(AI->getAlign()); 277 278 AI->eraseFromParent(); 279 MergedAwayAlloca = true; 280 ++NumMergedAllocas; 281 IFI.StaticAllocas[AllocaNo] = nullptr; 282 break; 283 } 284 285 // If we already nuked the alloca, we're done with it. 286 if (MergedAwayAlloca) 287 continue; 288 289 // If we were unable to merge away the alloca either because there are no 290 // allocas of the right type available or because we reused them all 291 // already, remember that this alloca came from an inlined function and mark 292 // it used so we don't reuse it for other allocas from this inline 293 // operation. 294 AllocasForType.push_back(AI); 295 UsedAllocas.insert(AI); 296 } 297 } 298 299 /// If it is possible to inline the specified call site, 300 /// do so and update the CallGraph for this operation. 301 /// 302 /// This function also does some basic book-keeping to update the IR. The 303 /// InlinedArrayAllocas map keeps track of any allocas that are already 304 /// available from other functions inlined into the caller. If we are able to 305 /// inline this call site we attempt to reuse already available allocas or add 306 /// any new allocas to the set if not possible. 307 static InlineResult inlineCallIfPossible( 308 CallBase &CB, InlineFunctionInfo &IFI, 309 InlinedArrayAllocasTy &InlinedArrayAllocas, int InlineHistory, 310 bool InsertLifetime, function_ref<AAResults &(Function &)> &AARGetter, 311 ImportedFunctionsInliningStatistics &ImportedFunctionsStats) { 312 Function *Callee = CB.getCalledFunction(); 313 Function *Caller = CB.getCaller(); 314 315 AAResults &AAR = AARGetter(*Callee); 316 317 // Try to inline the function. Get the list of static allocas that were 318 // inlined. 319 InlineResult IR = InlineFunction(CB, IFI, &AAR, InsertLifetime); 320 if (!IR.isSuccess()) 321 return IR; 322 323 if (InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No) 324 ImportedFunctionsStats.recordInline(*Caller, *Callee); 325 326 AttributeFuncs::mergeAttributesForInlining(*Caller, *Callee); 327 328 if (!DisableInlinedAllocaMerging) 329 mergeInlinedArrayAllocas(Caller, IFI, InlinedArrayAllocas, InlineHistory); 330 331 return IR; // success 332 } 333 334 /// Return true if the specified inline history ID 335 /// indicates an inline history that includes the specified function. 336 static bool inlineHistoryIncludes( 337 Function *F, int InlineHistoryID, 338 const SmallVectorImpl<std::pair<Function *, int>> &InlineHistory) { 339 while (InlineHistoryID != -1) { 340 assert(unsigned(InlineHistoryID) < InlineHistory.size() && 341 "Invalid inline history ID"); 342 if (InlineHistory[InlineHistoryID].first == F) 343 return true; 344 InlineHistoryID = InlineHistory[InlineHistoryID].second; 345 } 346 return false; 347 } 348 349 bool LegacyInlinerBase::doInitialization(CallGraph &CG) { 350 if (InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No) 351 ImportedFunctionsStats.setModuleInfo(CG.getModule()); 352 return false; // No changes to CallGraph. 353 } 354 355 bool LegacyInlinerBase::runOnSCC(CallGraphSCC &SCC) { 356 if (skipSCC(SCC)) 357 return false; 358 return inlineCalls(SCC); 359 } 360 361 static bool 362 inlineCallsImpl(CallGraphSCC &SCC, CallGraph &CG, 363 std::function<AssumptionCache &(Function &)> GetAssumptionCache, 364 ProfileSummaryInfo *PSI, 365 std::function<const TargetLibraryInfo &(Function &)> GetTLI, 366 bool InsertLifetime, 367 function_ref<InlineCost(CallBase &CB)> GetInlineCost, 368 function_ref<AAResults &(Function &)> AARGetter, 369 ImportedFunctionsInliningStatistics &ImportedFunctionsStats) { 370 SmallPtrSet<Function *, 8> SCCFunctions; 371 LLVM_DEBUG(dbgs() << "Inliner visiting SCC:"); 372 for (CallGraphNode *Node : SCC) { 373 Function *F = Node->getFunction(); 374 if (F) 375 SCCFunctions.insert(F); 376 LLVM_DEBUG(dbgs() << " " << (F ? F->getName() : "INDIRECTNODE")); 377 } 378 379 // Scan through and identify all call sites ahead of time so that we only 380 // inline call sites in the original functions, not call sites that result 381 // from inlining other functions. 382 SmallVector<std::pair<CallBase *, int>, 16> CallSites; 383 384 // When inlining a callee produces new call sites, we want to keep track of 385 // the fact that they were inlined from the callee. This allows us to avoid 386 // infinite inlining in some obscure cases. To represent this, we use an 387 // index into the InlineHistory vector. 388 SmallVector<std::pair<Function *, int>, 8> InlineHistory; 389 390 for (CallGraphNode *Node : SCC) { 391 Function *F = Node->getFunction(); 392 if (!F || F->isDeclaration()) 393 continue; 394 395 OptimizationRemarkEmitter ORE(F); 396 for (BasicBlock &BB : *F) 397 for (Instruction &I : BB) { 398 auto *CB = dyn_cast<CallBase>(&I); 399 // If this isn't a call, or it is a call to an intrinsic, it can 400 // never be inlined. 401 if (!CB || isa<IntrinsicInst>(I)) 402 continue; 403 404 // If this is a direct call to an external function, we can never inline 405 // it. If it is an indirect call, inlining may resolve it to be a 406 // direct call, so we keep it. 407 if (Function *Callee = CB->getCalledFunction()) 408 if (Callee->isDeclaration()) { 409 using namespace ore; 410 411 setInlineRemark(*CB, "unavailable definition"); 412 ORE.emit([&]() { 413 return OptimizationRemarkMissed(DEBUG_TYPE, "NoDefinition", &I) 414 << NV("Callee", Callee) << " will not be inlined into " 415 << NV("Caller", CB->getCaller()) 416 << " because its definition is unavailable" 417 << setIsVerbose(); 418 }); 419 continue; 420 } 421 422 CallSites.push_back(std::make_pair(CB, -1)); 423 } 424 } 425 426 LLVM_DEBUG(dbgs() << ": " << CallSites.size() << " call sites.\n"); 427 428 // If there are no calls in this function, exit early. 429 if (CallSites.empty()) 430 return false; 431 432 // Now that we have all of the call sites, move the ones to functions in the 433 // current SCC to the end of the list. 434 unsigned FirstCallInSCC = CallSites.size(); 435 for (unsigned I = 0; I < FirstCallInSCC; ++I) 436 if (Function *F = CallSites[I].first->getCalledFunction()) 437 if (SCCFunctions.count(F)) 438 std::swap(CallSites[I--], CallSites[--FirstCallInSCC]); 439 440 InlinedArrayAllocasTy InlinedArrayAllocas; 441 InlineFunctionInfo InlineInfo(&CG, GetAssumptionCache, PSI); 442 443 // Now that we have all of the call sites, loop over them and inline them if 444 // it looks profitable to do so. 445 bool Changed = false; 446 bool LocalChange; 447 do { 448 LocalChange = false; 449 // Iterate over the outer loop because inlining functions can cause indirect 450 // calls to become direct calls. 451 // CallSites may be modified inside so ranged for loop can not be used. 452 for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) { 453 auto &P = CallSites[CSi]; 454 CallBase &CB = *P.first; 455 const int InlineHistoryID = P.second; 456 457 Function *Caller = CB.getCaller(); 458 Function *Callee = CB.getCalledFunction(); 459 460 // We can only inline direct calls to non-declarations. 461 if (!Callee || Callee->isDeclaration()) 462 continue; 463 464 bool IsTriviallyDead = isInstructionTriviallyDead(&CB, &GetTLI(*Caller)); 465 466 if (!IsTriviallyDead) { 467 // If this call site was obtained by inlining another function, verify 468 // that the include path for the function did not include the callee 469 // itself. If so, we'd be recursively inlining the same function, 470 // which would provide the same callsites, which would cause us to 471 // infinitely inline. 472 if (InlineHistoryID != -1 && 473 inlineHistoryIncludes(Callee, InlineHistoryID, InlineHistory)) { 474 setInlineRemark(CB, "recursive"); 475 continue; 476 } 477 } 478 479 // FIXME for new PM: because of the old PM we currently generate ORE and 480 // in turn BFI on demand. With the new PM, the ORE dependency should 481 // just become a regular analysis dependency. 482 OptimizationRemarkEmitter ORE(Caller); 483 484 auto OIC = shouldInline(CB, GetInlineCost, ORE); 485 // If the policy determines that we should inline this function, 486 // delete the call instead. 487 if (!OIC) 488 continue; 489 490 // If this call site is dead and it is to a readonly function, we should 491 // just delete the call instead of trying to inline it, regardless of 492 // size. This happens because IPSCCP propagates the result out of the 493 // call and then we're left with the dead call. 494 if (IsTriviallyDead) { 495 LLVM_DEBUG(dbgs() << " -> Deleting dead call: " << CB << "\n"); 496 // Update the call graph by deleting the edge from Callee to Caller. 497 setInlineRemark(CB, "trivially dead"); 498 CG[Caller]->removeCallEdgeFor(CB); 499 CB.eraseFromParent(); 500 ++NumCallsDeleted; 501 } else { 502 // Get DebugLoc to report. CB will be invalid after Inliner. 503 DebugLoc DLoc = CB.getDebugLoc(); 504 BasicBlock *Block = CB.getParent(); 505 506 // Attempt to inline the function. 507 using namespace ore; 508 509 InlineResult IR = inlineCallIfPossible( 510 CB, InlineInfo, InlinedArrayAllocas, InlineHistoryID, 511 InsertLifetime, AARGetter, ImportedFunctionsStats); 512 if (!IR.isSuccess()) { 513 setInlineRemark(CB, std::string(IR.getFailureReason()) + "; " + 514 inlineCostStr(*OIC)); 515 ORE.emit([&]() { 516 return OptimizationRemarkMissed(DEBUG_TYPE, "NotInlined", DLoc, 517 Block) 518 << NV("Callee", Callee) << " will not be inlined into " 519 << NV("Caller", Caller) << ": " 520 << NV("Reason", IR.getFailureReason()); 521 }); 522 continue; 523 } 524 ++NumInlined; 525 526 emitInlinedIntoBasedOnCost(ORE, DLoc, Block, *Callee, *Caller, *OIC); 527 528 // If inlining this function gave us any new call sites, throw them 529 // onto our worklist to process. They are useful inline candidates. 530 if (!InlineInfo.InlinedCalls.empty()) { 531 // Create a new inline history entry for this, so that we remember 532 // that these new callsites came about due to inlining Callee. 533 int NewHistoryID = InlineHistory.size(); 534 InlineHistory.push_back(std::make_pair(Callee, InlineHistoryID)); 535 536 #ifndef NDEBUG 537 // Make sure no dupplicates in the inline candidates. This could 538 // happen when a callsite is simpilfied to reusing the return value 539 // of another callsite during function cloning, thus the other 540 // callsite will be reconsidered here. 541 DenseSet<CallBase *> DbgCallSites; 542 for (auto &II : CallSites) 543 DbgCallSites.insert(II.first); 544 #endif 545 546 for (Value *Ptr : InlineInfo.InlinedCalls) { 547 #ifndef NDEBUG 548 assert(DbgCallSites.count(dyn_cast<CallBase>(Ptr)) == 0); 549 #endif 550 CallSites.push_back( 551 std::make_pair(dyn_cast<CallBase>(Ptr), NewHistoryID)); 552 } 553 } 554 } 555 556 // If we inlined or deleted the last possible call site to the function, 557 // delete the function body now. 558 if (Callee && Callee->use_empty() && Callee->hasLocalLinkage() && 559 // TODO: Can remove if in SCC now. 560 !SCCFunctions.count(Callee) && 561 // The function may be apparently dead, but if there are indirect 562 // callgraph references to the node, we cannot delete it yet, this 563 // could invalidate the CGSCC iterator. 564 CG[Callee]->getNumReferences() == 0) { 565 LLVM_DEBUG(dbgs() << " -> Deleting dead function: " 566 << Callee->getName() << "\n"); 567 CallGraphNode *CalleeNode = CG[Callee]; 568 569 // Remove any call graph edges from the callee to its callees. 570 CalleeNode->removeAllCalledFunctions(); 571 572 // Removing the node for callee from the call graph and delete it. 573 delete CG.removeFunctionFromModule(CalleeNode); 574 ++NumDeleted; 575 } 576 577 // Remove this call site from the list. If possible, use 578 // swap/pop_back for efficiency, but do not use it if doing so would 579 // move a call site to a function in this SCC before the 580 // 'FirstCallInSCC' barrier. 581 if (SCC.isSingular()) { 582 CallSites[CSi] = CallSites.back(); 583 CallSites.pop_back(); 584 } else { 585 CallSites.erase(CallSites.begin() + CSi); 586 } 587 --CSi; 588 589 Changed = true; 590 LocalChange = true; 591 } 592 } while (LocalChange); 593 594 return Changed; 595 } 596 597 bool LegacyInlinerBase::inlineCalls(CallGraphSCC &SCC) { 598 CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph(); 599 ACT = &getAnalysis<AssumptionCacheTracker>(); 600 PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); 601 GetTLI = [&](Function &F) -> const TargetLibraryInfo & { 602 return getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F); 603 }; 604 auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & { 605 return ACT->getAssumptionCache(F); 606 }; 607 return inlineCallsImpl( 608 SCC, CG, GetAssumptionCache, PSI, GetTLI, InsertLifetime, 609 [&](CallBase &CB) { return getInlineCost(CB); }, LegacyAARGetter(*this), 610 ImportedFunctionsStats); 611 } 612 613 /// Remove now-dead linkonce functions at the end of 614 /// processing to avoid breaking the SCC traversal. 615 bool LegacyInlinerBase::doFinalization(CallGraph &CG) { 616 if (InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No) 617 ImportedFunctionsStats.dump(InlinerFunctionImportStats == 618 InlinerFunctionImportStatsOpts::Verbose); 619 return removeDeadFunctions(CG); 620 } 621 622 /// Remove dead functions that are not included in DNR (Do Not Remove) list. 623 bool LegacyInlinerBase::removeDeadFunctions(CallGraph &CG, 624 bool AlwaysInlineOnly) { 625 SmallVector<CallGraphNode *, 16> FunctionsToRemove; 626 SmallVector<Function *, 16> DeadFunctionsInComdats; 627 628 auto RemoveCGN = [&](CallGraphNode *CGN) { 629 // Remove any call graph edges from the function to its callees. 630 CGN->removeAllCalledFunctions(); 631 632 // Remove any edges from the external node to the function's call graph 633 // node. These edges might have been made irrelegant due to 634 // optimization of the program. 635 CG.getExternalCallingNode()->removeAnyCallEdgeTo(CGN); 636 637 // Removing the node for callee from the call graph and delete it. 638 FunctionsToRemove.push_back(CGN); 639 }; 640 641 // Scan for all of the functions, looking for ones that should now be removed 642 // from the program. Insert the dead ones in the FunctionsToRemove set. 643 for (const auto &I : CG) { 644 CallGraphNode *CGN = I.second.get(); 645 Function *F = CGN->getFunction(); 646 if (!F || F->isDeclaration()) 647 continue; 648 649 // Handle the case when this function is called and we only want to care 650 // about always-inline functions. This is a bit of a hack to share code 651 // between here and the InlineAlways pass. 652 if (AlwaysInlineOnly && !F->hasFnAttribute(Attribute::AlwaysInline)) 653 continue; 654 655 // If the only remaining users of the function are dead constants, remove 656 // them. 657 F->removeDeadConstantUsers(); 658 659 if (!F->isDefTriviallyDead()) 660 continue; 661 662 // It is unsafe to drop a function with discardable linkage from a COMDAT 663 // without also dropping the other members of the COMDAT. 664 // The inliner doesn't visit non-function entities which are in COMDAT 665 // groups so it is unsafe to do so *unless* the linkage is local. 666 if (!F->hasLocalLinkage()) { 667 if (F->hasComdat()) { 668 DeadFunctionsInComdats.push_back(F); 669 continue; 670 } 671 } 672 673 RemoveCGN(CGN); 674 } 675 if (!DeadFunctionsInComdats.empty()) { 676 // Filter out the functions whose comdats remain alive. 677 filterDeadComdatFunctions(DeadFunctionsInComdats); 678 // Remove the rest. 679 for (Function *F : DeadFunctionsInComdats) 680 RemoveCGN(CG[F]); 681 } 682 683 if (FunctionsToRemove.empty()) 684 return false; 685 686 // Now that we know which functions to delete, do so. We didn't want to do 687 // this inline, because that would invalidate our CallGraph::iterator 688 // objects. :( 689 // 690 // Note that it doesn't matter that we are iterating over a non-stable order 691 // here to do this, it doesn't matter which order the functions are deleted 692 // in. 693 array_pod_sort(FunctionsToRemove.begin(), FunctionsToRemove.end()); 694 FunctionsToRemove.erase( 695 std::unique(FunctionsToRemove.begin(), FunctionsToRemove.end()), 696 FunctionsToRemove.end()); 697 for (CallGraphNode *CGN : FunctionsToRemove) { 698 delete CG.removeFunctionFromModule(CGN); 699 ++NumDeleted; 700 } 701 return true; 702 } 703 704 InlineAdvisor & 705 InlinerPass::getAdvisor(const ModuleAnalysisManagerCGSCCProxy::Result &MAM, 706 FunctionAnalysisManager &FAM, Module &M) { 707 if (OwnedAdvisor) 708 return *OwnedAdvisor; 709 710 auto *IAA = MAM.getCachedResult<InlineAdvisorAnalysis>(M); 711 if (!IAA) { 712 // It should still be possible to run the inliner as a stand-alone SCC pass, 713 // for test scenarios. In that case, we default to the 714 // DefaultInlineAdvisor, which doesn't need to keep state between SCC pass 715 // runs. It also uses just the default InlineParams. 716 // In this case, we need to use the provided FAM, which is valid for the 717 // duration of the inliner pass, and thus the lifetime of the owned advisor. 718 // The one we would get from the MAM can be invalidated as a result of the 719 // inliner's activity. 720 OwnedAdvisor = std::make_unique<DefaultInlineAdvisor>( 721 M, FAM, getInlineParams(), 722 InlineContext{LTOPhase, InlinePass::CGSCCInliner}); 723 724 if (!CGSCCInlineReplayFile.empty()) 725 OwnedAdvisor = getReplayInlineAdvisor( 726 M, FAM, M.getContext(), std::move(OwnedAdvisor), 727 ReplayInlinerSettings{CGSCCInlineReplayFile, 728 CGSCCInlineReplayScope, 729 CGSCCInlineReplayFallback, 730 {CGSCCInlineReplayFormat}}, 731 /*EmitRemarks=*/true, 732 InlineContext{LTOPhase, 733 InlinePass::ReplayCGSCCInliner}); 734 735 return *OwnedAdvisor; 736 } 737 assert(IAA->getAdvisor() && 738 "Expected a present InlineAdvisorAnalysis also have an " 739 "InlineAdvisor initialized"); 740 return *IAA->getAdvisor(); 741 } 742 743 PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC, 744 CGSCCAnalysisManager &AM, LazyCallGraph &CG, 745 CGSCCUpdateResult &UR) { 746 const auto &MAMProxy = 747 AM.getResult<ModuleAnalysisManagerCGSCCProxy>(InitialC, CG); 748 bool Changed = false; 749 750 assert(InitialC.size() > 0 && "Cannot handle an empty SCC!"); 751 Module &M = *InitialC.begin()->getFunction().getParent(); 752 ProfileSummaryInfo *PSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(M); 753 754 FunctionAnalysisManager &FAM = 755 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(InitialC, CG) 756 .getManager(); 757 758 InlineAdvisor &Advisor = getAdvisor(MAMProxy, FAM, M); 759 Advisor.onPassEntry(&InitialC); 760 761 auto AdvisorOnExit = make_scope_exit([&] { Advisor.onPassExit(&InitialC); }); 762 763 // We use a single common worklist for calls across the entire SCC. We 764 // process these in-order and append new calls introduced during inlining to 765 // the end. The PriorityInlineOrder is optional here, in which the smaller 766 // callee would have a higher priority to inline. 767 // 768 // Note that this particular order of processing is actually critical to 769 // avoid very bad behaviors. Consider *highly connected* call graphs where 770 // each function contains a small amount of code and a couple of calls to 771 // other functions. Because the LLVM inliner is fundamentally a bottom-up 772 // inliner, it can handle gracefully the fact that these all appear to be 773 // reasonable inlining candidates as it will flatten things until they become 774 // too big to inline, and then move on and flatten another batch. 775 // 776 // However, when processing call edges *within* an SCC we cannot rely on this 777 // bottom-up behavior. As a consequence, with heavily connected *SCCs* of 778 // functions we can end up incrementally inlining N calls into each of 779 // N functions because each incremental inlining decision looks good and we 780 // don't have a topological ordering to prevent explosions. 781 // 782 // To compensate for this, we don't process transitive edges made immediate 783 // by inlining until we've done one pass of inlining across the entire SCC. 784 // Large, highly connected SCCs still lead to some amount of code bloat in 785 // this model, but it is uniformly spread across all the functions in the SCC 786 // and eventually they all become too large to inline, rather than 787 // incrementally maknig a single function grow in a super linear fashion. 788 DefaultInlineOrder<std::pair<CallBase *, int>> Calls; 789 790 // Populate the initial list of calls in this SCC. 791 for (auto &N : InitialC) { 792 auto &ORE = 793 FAM.getResult<OptimizationRemarkEmitterAnalysis>(N.getFunction()); 794 // We want to generally process call sites top-down in order for 795 // simplifications stemming from replacing the call with the returned value 796 // after inlining to be visible to subsequent inlining decisions. 797 // FIXME: Using instructions sequence is a really bad way to do this. 798 // Instead we should do an actual RPO walk of the function body. 799 for (Instruction &I : instructions(N.getFunction())) 800 if (auto *CB = dyn_cast<CallBase>(&I)) 801 if (Function *Callee = CB->getCalledFunction()) { 802 if (!Callee->isDeclaration()) 803 Calls.push({CB, -1}); 804 else if (!isa<IntrinsicInst>(I)) { 805 using namespace ore; 806 setInlineRemark(*CB, "unavailable definition"); 807 ORE.emit([&]() { 808 return OptimizationRemarkMissed(DEBUG_TYPE, "NoDefinition", &I) 809 << NV("Callee", Callee) << " will not be inlined into " 810 << NV("Caller", CB->getCaller()) 811 << " because its definition is unavailable" 812 << setIsVerbose(); 813 }); 814 } 815 } 816 } 817 if (Calls.empty()) 818 return PreservedAnalyses::all(); 819 820 // Capture updatable variable for the current SCC. 821 auto *C = &InitialC; 822 823 // When inlining a callee produces new call sites, we want to keep track of 824 // the fact that they were inlined from the callee. This allows us to avoid 825 // infinite inlining in some obscure cases. To represent this, we use an 826 // index into the InlineHistory vector. 827 SmallVector<std::pair<Function *, int>, 16> InlineHistory; 828 829 // Track a set vector of inlined callees so that we can augment the caller 830 // with all of their edges in the call graph before pruning out the ones that 831 // got simplified away. 832 SmallSetVector<Function *, 4> InlinedCallees; 833 834 // Track the dead functions to delete once finished with inlining calls. We 835 // defer deleting these to make it easier to handle the call graph updates. 836 SmallVector<Function *, 4> DeadFunctions; 837 838 // Track potentially dead non-local functions with comdats to see if they can 839 // be deleted as a batch after inlining. 840 SmallVector<Function *, 4> DeadFunctionsInComdats; 841 842 // Loop forward over all of the calls. 843 while (!Calls.empty()) { 844 // We expect the calls to typically be batched with sequences of calls that 845 // have the same caller, so we first set up some shared infrastructure for 846 // this caller. We also do any pruning we can at this layer on the caller 847 // alone. 848 Function &F = *Calls.front().first->getCaller(); 849 LazyCallGraph::Node &N = *CG.lookup(F); 850 if (CG.lookupSCC(N) != C) { 851 Calls.pop(); 852 continue; 853 } 854 855 LLVM_DEBUG(dbgs() << "Inlining calls in: " << F.getName() << "\n" 856 << " Function size: " << F.getInstructionCount() 857 << "\n"); 858 859 auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & { 860 return FAM.getResult<AssumptionAnalysis>(F); 861 }; 862 863 // Now process as many calls as we have within this caller in the sequence. 864 // We bail out as soon as the caller has to change so we can update the 865 // call graph and prepare the context of that new caller. 866 bool DidInline = false; 867 while (!Calls.empty() && Calls.front().first->getCaller() == &F) { 868 auto P = Calls.pop(); 869 CallBase *CB = P.first; 870 const int InlineHistoryID = P.second; 871 Function &Callee = *CB->getCalledFunction(); 872 873 if (InlineHistoryID != -1 && 874 inlineHistoryIncludes(&Callee, InlineHistoryID, InlineHistory)) { 875 LLVM_DEBUG(dbgs() << "Skipping inlining due to history: " 876 << F.getName() << " -> " << Callee.getName() << "\n"); 877 setInlineRemark(*CB, "recursive"); 878 continue; 879 } 880 881 // Check if this inlining may repeat breaking an SCC apart that has 882 // already been split once before. In that case, inlining here may 883 // trigger infinite inlining, much like is prevented within the inliner 884 // itself by the InlineHistory above, but spread across CGSCC iterations 885 // and thus hidden from the full inline history. 886 LazyCallGraph::SCC *CalleeSCC = CG.lookupSCC(*CG.lookup(Callee)); 887 if (CalleeSCC == C && UR.InlinedInternalEdges.count({&N, C})) { 888 LLVM_DEBUG(dbgs() << "Skipping inlining internal SCC edge from a node " 889 "previously split out of this SCC by inlining: " 890 << F.getName() << " -> " << Callee.getName() << "\n"); 891 setInlineRemark(*CB, "recursive SCC split"); 892 continue; 893 } 894 895 std::unique_ptr<InlineAdvice> Advice = 896 Advisor.getAdvice(*CB, OnlyMandatory); 897 898 // Check whether we want to inline this callsite. 899 if (!Advice) 900 continue; 901 902 if (!Advice->isInliningRecommended()) { 903 Advice->recordUnattemptedInlining(); 904 continue; 905 } 906 907 int CBCostMult = 908 getStringFnAttrAsInt( 909 *CB, InlineConstants::FunctionInlineCostMultiplierAttributeName) 910 .value_or(1); 911 912 // Setup the data structure used to plumb customization into the 913 // `InlineFunction` routine. 914 InlineFunctionInfo IFI( 915 /*cg=*/nullptr, GetAssumptionCache, PSI, 916 &FAM.getResult<BlockFrequencyAnalysis>(*(CB->getCaller())), 917 &FAM.getResult<BlockFrequencyAnalysis>(Callee)); 918 919 InlineResult IR = 920 InlineFunction(*CB, IFI, &FAM.getResult<AAManager>(*CB->getCaller())); 921 if (!IR.isSuccess()) { 922 Advice->recordUnsuccessfulInlining(IR); 923 continue; 924 } 925 926 DidInline = true; 927 InlinedCallees.insert(&Callee); 928 ++NumInlined; 929 930 LLVM_DEBUG(dbgs() << " Size after inlining: " 931 << F.getInstructionCount() << "\n"); 932 933 // Add any new callsites to defined functions to the worklist. 934 if (!IFI.InlinedCallSites.empty()) { 935 int NewHistoryID = InlineHistory.size(); 936 InlineHistory.push_back({&Callee, InlineHistoryID}); 937 938 for (CallBase *ICB : reverse(IFI.InlinedCallSites)) { 939 Function *NewCallee = ICB->getCalledFunction(); 940 assert(!(NewCallee && NewCallee->isIntrinsic()) && 941 "Intrinsic calls should not be tracked."); 942 if (!NewCallee) { 943 // Try to promote an indirect (virtual) call without waiting for 944 // the post-inline cleanup and the next DevirtSCCRepeatedPass 945 // iteration because the next iteration may not happen and we may 946 // miss inlining it. 947 if (tryPromoteCall(*ICB)) 948 NewCallee = ICB->getCalledFunction(); 949 } 950 if (NewCallee) { 951 if (!NewCallee->isDeclaration()) { 952 Calls.push({ICB, NewHistoryID}); 953 // Continually inlining through an SCC can result in huge compile 954 // times and bloated code since we arbitrarily stop at some point 955 // when the inliner decides it's not profitable to inline anymore. 956 // We attempt to mitigate this by making these calls exponentially 957 // more expensive. 958 // This doesn't apply to calls in the same SCC since if we do 959 // inline through the SCC the function will end up being 960 // self-recursive which the inliner bails out on, and inlining 961 // within an SCC is necessary for performance. 962 if (CalleeSCC != C && 963 CalleeSCC == CG.lookupSCC(CG.get(*NewCallee))) { 964 Attribute NewCBCostMult = Attribute::get( 965 M.getContext(), 966 InlineConstants::FunctionInlineCostMultiplierAttributeName, 967 itostr(CBCostMult * IntraSCCCostMultiplier)); 968 ICB->addFnAttr(NewCBCostMult); 969 } 970 } 971 } 972 } 973 } 974 975 // Merge the attributes based on the inlining. 976 AttributeFuncs::mergeAttributesForInlining(F, Callee); 977 978 // For local functions or discardable functions without comdats, check 979 // whether this makes the callee trivially dead. In that case, we can drop 980 // the body of the function eagerly which may reduce the number of callers 981 // of other functions to one, changing inline cost thresholds. Non-local 982 // discardable functions with comdats are checked later on. 983 bool CalleeWasDeleted = false; 984 if (Callee.isDiscardableIfUnused() && Callee.hasZeroLiveUses() && 985 !CG.isLibFunction(Callee)) { 986 if (Callee.hasLocalLinkage() || !Callee.hasComdat()) { 987 Calls.erase_if([&](const std::pair<CallBase *, int> &Call) { 988 return Call.first->getCaller() == &Callee; 989 }); 990 // Clear the body and queue the function itself for deletion when we 991 // finish inlining and call graph updates. 992 // Note that after this point, it is an error to do anything other 993 // than use the callee's address or delete it. 994 Callee.dropAllReferences(); 995 assert(!is_contained(DeadFunctions, &Callee) && 996 "Cannot put cause a function to become dead twice!"); 997 DeadFunctions.push_back(&Callee); 998 CalleeWasDeleted = true; 999 } else { 1000 DeadFunctionsInComdats.push_back(&Callee); 1001 } 1002 } 1003 if (CalleeWasDeleted) 1004 Advice->recordInliningWithCalleeDeleted(); 1005 else 1006 Advice->recordInlining(); 1007 } 1008 1009 if (!DidInline) 1010 continue; 1011 Changed = true; 1012 1013 // At this point, since we have made changes we have at least removed 1014 // a call instruction. However, in the process we do some incremental 1015 // simplification of the surrounding code. This simplification can 1016 // essentially do all of the same things as a function pass and we can 1017 // re-use the exact same logic for updating the call graph to reflect the 1018 // change. 1019 1020 // Inside the update, we also update the FunctionAnalysisManager in the 1021 // proxy for this particular SCC. We do this as the SCC may have changed and 1022 // as we're going to mutate this particular function we want to make sure 1023 // the proxy is in place to forward any invalidation events. 1024 LazyCallGraph::SCC *OldC = C; 1025 C = &updateCGAndAnalysisManagerForCGSCCPass(CG, *C, N, AM, UR, FAM); 1026 LLVM_DEBUG(dbgs() << "Updated inlining SCC: " << *C << "\n"); 1027 1028 // If this causes an SCC to split apart into multiple smaller SCCs, there 1029 // is a subtle risk we need to prepare for. Other transformations may 1030 // expose an "infinite inlining" opportunity later, and because of the SCC 1031 // mutation, we will revisit this function and potentially re-inline. If we 1032 // do, and that re-inlining also has the potentially to mutate the SCC 1033 // structure, the infinite inlining problem can manifest through infinite 1034 // SCC splits and merges. To avoid this, we capture the originating caller 1035 // node and the SCC containing the call edge. This is a slight over 1036 // approximation of the possible inlining decisions that must be avoided, 1037 // but is relatively efficient to store. We use C != OldC to know when 1038 // a new SCC is generated and the original SCC may be generated via merge 1039 // in later iterations. 1040 // 1041 // It is also possible that even if no new SCC is generated 1042 // (i.e., C == OldC), the original SCC could be split and then merged 1043 // into the same one as itself. and the original SCC will be added into 1044 // UR.CWorklist again, we want to catch such cases too. 1045 // 1046 // FIXME: This seems like a very heavyweight way of retaining the inline 1047 // history, we should look for a more efficient way of tracking it. 1048 if ((C != OldC || UR.CWorklist.count(OldC)) && 1049 llvm::any_of(InlinedCallees, [&](Function *Callee) { 1050 return CG.lookupSCC(*CG.lookup(*Callee)) == OldC; 1051 })) { 1052 LLVM_DEBUG(dbgs() << "Inlined an internal call edge and split an SCC, " 1053 "retaining this to avoid infinite inlining.\n"); 1054 UR.InlinedInternalEdges.insert({&N, OldC}); 1055 } 1056 InlinedCallees.clear(); 1057 1058 // Invalidate analyses for this function now so that we don't have to 1059 // invalidate analyses for all functions in this SCC later. 1060 FAM.invalidate(F, PreservedAnalyses::none()); 1061 } 1062 1063 // We must ensure that we only delete functions with comdats if every function 1064 // in the comdat is going to be deleted. 1065 if (!DeadFunctionsInComdats.empty()) { 1066 filterDeadComdatFunctions(DeadFunctionsInComdats); 1067 for (auto *Callee : DeadFunctionsInComdats) 1068 Callee->dropAllReferences(); 1069 DeadFunctions.append(DeadFunctionsInComdats); 1070 } 1071 1072 // Now that we've finished inlining all of the calls across this SCC, delete 1073 // all of the trivially dead functions, updating the call graph and the CGSCC 1074 // pass manager in the process. 1075 // 1076 // Note that this walks a pointer set which has non-deterministic order but 1077 // that is OK as all we do is delete things and add pointers to unordered 1078 // sets. 1079 for (Function *DeadF : DeadFunctions) { 1080 // Get the necessary information out of the call graph and nuke the 1081 // function there. Also, clear out any cached analyses. 1082 auto &DeadC = *CG.lookupSCC(*CG.lookup(*DeadF)); 1083 FAM.clear(*DeadF, DeadF->getName()); 1084 AM.clear(DeadC, DeadC.getName()); 1085 auto &DeadRC = DeadC.getOuterRefSCC(); 1086 CG.removeDeadFunction(*DeadF); 1087 1088 // Mark the relevant parts of the call graph as invalid so we don't visit 1089 // them. 1090 UR.InvalidatedSCCs.insert(&DeadC); 1091 UR.InvalidatedRefSCCs.insert(&DeadRC); 1092 1093 // If the updated SCC was the one containing the deleted function, clear it. 1094 if (&DeadC == UR.UpdatedC) 1095 UR.UpdatedC = nullptr; 1096 1097 // And delete the actual function from the module. 1098 M.getFunctionList().erase(DeadF); 1099 1100 ++NumDeleted; 1101 } 1102 1103 if (!Changed) 1104 return PreservedAnalyses::all(); 1105 1106 PreservedAnalyses PA; 1107 // Even if we change the IR, we update the core CGSCC data structures and so 1108 // can preserve the proxy to the function analysis manager. 1109 PA.preserve<FunctionAnalysisManagerCGSCCProxy>(); 1110 // We have already invalidated all analyses on modified functions. 1111 PA.preserveSet<AllAnalysesOn<Function>>(); 1112 return PA; 1113 } 1114 1115 ModuleInlinerWrapperPass::ModuleInlinerWrapperPass(InlineParams Params, 1116 bool MandatoryFirst, 1117 InlineContext IC, 1118 InliningAdvisorMode Mode, 1119 unsigned MaxDevirtIterations) 1120 : Params(Params), IC(IC), Mode(Mode), 1121 MaxDevirtIterations(MaxDevirtIterations) { 1122 // Run the inliner first. The theory is that we are walking bottom-up and so 1123 // the callees have already been fully optimized, and we want to inline them 1124 // into the callers so that our optimizations can reflect that. 1125 // For PreLinkThinLTO pass, we disable hot-caller heuristic for sample PGO 1126 // because it makes profile annotation in the backend inaccurate. 1127 if (MandatoryFirst) { 1128 PM.addPass(InlinerPass(/*OnlyMandatory*/ true)); 1129 if (EnablePostSCCAdvisorPrinting) 1130 PM.addPass(InlineAdvisorAnalysisPrinterPass(dbgs())); 1131 } 1132 PM.addPass(InlinerPass()); 1133 if (EnablePostSCCAdvisorPrinting) 1134 PM.addPass(InlineAdvisorAnalysisPrinterPass(dbgs())); 1135 } 1136 1137 PreservedAnalyses ModuleInlinerWrapperPass::run(Module &M, 1138 ModuleAnalysisManager &MAM) { 1139 auto &IAA = MAM.getResult<InlineAdvisorAnalysis>(M); 1140 if (!IAA.tryCreate(Params, Mode, 1141 {CGSCCInlineReplayFile, 1142 CGSCCInlineReplayScope, 1143 CGSCCInlineReplayFallback, 1144 {CGSCCInlineReplayFormat}}, 1145 IC)) { 1146 M.getContext().emitError( 1147 "Could not setup Inlining Advisor for the requested " 1148 "mode and/or options"); 1149 return PreservedAnalyses::all(); 1150 } 1151 1152 // We wrap the CGSCC pipeline in a devirtualization repeater. This will try 1153 // to detect when we devirtualize indirect calls and iterate the SCC passes 1154 // in that case to try and catch knock-on inlining or function attrs 1155 // opportunities. Then we add it to the module pipeline by walking the SCCs 1156 // in postorder (or bottom-up). 1157 // If MaxDevirtIterations is 0, we just don't use the devirtualization 1158 // wrapper. 1159 if (MaxDevirtIterations == 0) 1160 MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(PM))); 1161 else 1162 MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor( 1163 createDevirtSCCRepeatedPass(std::move(PM), MaxDevirtIterations))); 1164 1165 MPM.addPass(std::move(AfterCGMPM)); 1166 MPM.run(M, MAM); 1167 1168 // Discard the InlineAdvisor, a subsequent inlining session should construct 1169 // its own. 1170 auto PA = PreservedAnalyses::all(); 1171 if (!KeepAdvisorForPrinting) 1172 PA.abandon<InlineAdvisorAnalysis>(); 1173 return PA; 1174 } 1175 1176 void InlinerPass::printPipeline( 1177 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) { 1178 static_cast<PassInfoMixin<InlinerPass> *>(this)->printPipeline( 1179 OS, MapClassName2PassName); 1180 if (OnlyMandatory) 1181 OS << "<only-mandatory>"; 1182 } 1183 1184 void ModuleInlinerWrapperPass::printPipeline( 1185 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) { 1186 // Print some info about passes added to the wrapper. This is however 1187 // incomplete as InlineAdvisorAnalysis part isn't included (which also depends 1188 // on Params and Mode). 1189 if (!MPM.isEmpty()) { 1190 MPM.printPipeline(OS, MapClassName2PassName); 1191 OS << ","; 1192 } 1193 OS << "cgscc("; 1194 if (MaxDevirtIterations != 0) 1195 OS << "devirt<" << MaxDevirtIterations << ">("; 1196 PM.printPipeline(OS, MapClassName2PassName); 1197 if (MaxDevirtIterations != 0) 1198 OS << ")"; 1199 OS << ")"; 1200 } 1201