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/PriorityWorklist.h" 17 #include "llvm/ADT/STLExtras.h" 18 #include "llvm/ADT/ScopeExit.h" 19 #include "llvm/ADT/SetVector.h" 20 #include "llvm/ADT/SmallPtrSet.h" 21 #include "llvm/ADT/SmallVector.h" 22 #include "llvm/ADT/Statistic.h" 23 #include "llvm/ADT/StringExtras.h" 24 #include "llvm/ADT/StringRef.h" 25 #include "llvm/Analysis/AssumptionCache.h" 26 #include "llvm/Analysis/BasicAliasAnalysis.h" 27 #include "llvm/Analysis/BlockFrequencyInfo.h" 28 #include "llvm/Analysis/CGSCCPassManager.h" 29 #include "llvm/Analysis/InlineAdvisor.h" 30 #include "llvm/Analysis/InlineCost.h" 31 #include "llvm/Analysis/LazyCallGraph.h" 32 #include "llvm/Analysis/OptimizationRemarkEmitter.h" 33 #include "llvm/Analysis/ProfileSummaryInfo.h" 34 #include "llvm/Analysis/ReplayInlineAdvisor.h" 35 #include "llvm/Analysis/Utils/ImportedFunctionsInliningStatistics.h" 36 #include "llvm/IR/Attributes.h" 37 #include "llvm/IR/BasicBlock.h" 38 #include "llvm/IR/DebugLoc.h" 39 #include "llvm/IR/DerivedTypes.h" 40 #include "llvm/IR/DiagnosticInfo.h" 41 #include "llvm/IR/Function.h" 42 #include "llvm/IR/InstIterator.h" 43 #include "llvm/IR/Instruction.h" 44 #include "llvm/IR/Instructions.h" 45 #include "llvm/IR/IntrinsicInst.h" 46 #include "llvm/IR/Metadata.h" 47 #include "llvm/IR/Module.h" 48 #include "llvm/IR/PassManager.h" 49 #include "llvm/IR/Value.h" 50 #include "llvm/Pass.h" 51 #include "llvm/Support/Casting.h" 52 #include "llvm/Support/CommandLine.h" 53 #include "llvm/Support/Debug.h" 54 #include "llvm/Support/raw_ostream.h" 55 #include "llvm/Transforms/Utils/CallPromotionUtils.h" 56 #include "llvm/Transforms/Utils/Cloning.h" 57 #include "llvm/Transforms/Utils/Local.h" 58 #include "llvm/Transforms/Utils/ModuleUtils.h" 59 #include <algorithm> 60 #include <cassert> 61 #include <utility> 62 63 using namespace llvm; 64 65 #define DEBUG_TYPE "inline" 66 67 STATISTIC(NumInlined, "Number of functions inlined"); 68 STATISTIC(NumDeleted, "Number of functions deleted because all callers found"); 69 70 static cl::opt<int> IntraSCCCostMultiplier( 71 "intra-scc-cost-multiplier", cl::init(2), cl::Hidden, 72 cl::desc( 73 "Cost multiplier to multiply onto inlined call sites where the " 74 "new call was previously an intra-SCC call (not relevant when the " 75 "original call was already intra-SCC). This can accumulate over " 76 "multiple inlinings (e.g. if a call site already had a cost " 77 "multiplier and one of its inlined calls was also subject to " 78 "this, the inlined call would have the original multiplier " 79 "multiplied by intra-scc-cost-multiplier). This is to prevent tons of " 80 "inlining through a child SCC which can cause terrible compile times")); 81 82 /// A flag for test, so we can print the content of the advisor when running it 83 /// as part of the default (e.g. -O3) pipeline. 84 static cl::opt<bool> KeepAdvisorForPrinting("keep-inline-advisor-for-printing", 85 cl::init(false), cl::Hidden); 86 87 /// Allows printing the contents of the advisor after each SCC inliner pass. 88 static cl::opt<bool> 89 EnablePostSCCAdvisorPrinting("enable-scc-inline-advisor-printing", 90 cl::init(false), cl::Hidden); 91 92 93 static cl::opt<std::string> CGSCCInlineReplayFile( 94 "cgscc-inline-replay", cl::init(""), cl::value_desc("filename"), 95 cl::desc( 96 "Optimization remarks file containing inline remarks to be replayed " 97 "by cgscc inlining."), 98 cl::Hidden); 99 100 static cl::opt<ReplayInlinerSettings::Scope> CGSCCInlineReplayScope( 101 "cgscc-inline-replay-scope", 102 cl::init(ReplayInlinerSettings::Scope::Function), 103 cl::values(clEnumValN(ReplayInlinerSettings::Scope::Function, "Function", 104 "Replay on functions that have remarks associated " 105 "with them (default)"), 106 clEnumValN(ReplayInlinerSettings::Scope::Module, "Module", 107 "Replay on the entire module")), 108 cl::desc("Whether inline replay should be applied to the entire " 109 "Module or just the Functions (default) that are present as " 110 "callers in remarks during cgscc inlining."), 111 cl::Hidden); 112 113 static cl::opt<ReplayInlinerSettings::Fallback> CGSCCInlineReplayFallback( 114 "cgscc-inline-replay-fallback", 115 cl::init(ReplayInlinerSettings::Fallback::Original), 116 cl::values( 117 clEnumValN( 118 ReplayInlinerSettings::Fallback::Original, "Original", 119 "All decisions not in replay send to original advisor (default)"), 120 clEnumValN(ReplayInlinerSettings::Fallback::AlwaysInline, 121 "AlwaysInline", "All decisions not in replay are inlined"), 122 clEnumValN(ReplayInlinerSettings::Fallback::NeverInline, "NeverInline", 123 "All decisions not in replay are not inlined")), 124 cl::desc( 125 "How cgscc inline replay treats sites that don't come from the replay. " 126 "Original: defers to original advisor, AlwaysInline: inline all sites " 127 "not in replay, NeverInline: inline no sites not in replay"), 128 cl::Hidden); 129 130 static cl::opt<CallSiteFormat::Format> CGSCCInlineReplayFormat( 131 "cgscc-inline-replay-format", 132 cl::init(CallSiteFormat::Format::LineColumnDiscriminator), 133 cl::values( 134 clEnumValN(CallSiteFormat::Format::Line, "Line", "<Line Number>"), 135 clEnumValN(CallSiteFormat::Format::LineColumn, "LineColumn", 136 "<Line Number>:<Column Number>"), 137 clEnumValN(CallSiteFormat::Format::LineDiscriminator, 138 "LineDiscriminator", "<Line Number>.<Discriminator>"), 139 clEnumValN(CallSiteFormat::Format::LineColumnDiscriminator, 140 "LineColumnDiscriminator", 141 "<Line Number>:<Column Number>.<Discriminator> (default)")), 142 cl::desc("How cgscc inline replay file is formatted"), cl::Hidden); 143 144 /// Return true if the specified inline history ID 145 /// indicates an inline history that includes the specified function. 146 static bool inlineHistoryIncludes( 147 Function *F, int InlineHistoryID, 148 const SmallVectorImpl<std::pair<Function *, int>> &InlineHistory) { 149 while (InlineHistoryID != -1) { 150 assert(unsigned(InlineHistoryID) < InlineHistory.size() && 151 "Invalid inline history ID"); 152 if (InlineHistory[InlineHistoryID].first == F) 153 return true; 154 InlineHistoryID = InlineHistory[InlineHistoryID].second; 155 } 156 return false; 157 } 158 159 InlineAdvisor & 160 InlinerPass::getAdvisor(const ModuleAnalysisManagerCGSCCProxy::Result &MAM, 161 FunctionAnalysisManager &FAM, Module &M) { 162 if (OwnedAdvisor) 163 return *OwnedAdvisor; 164 165 auto *IAA = MAM.getCachedResult<InlineAdvisorAnalysis>(M); 166 if (!IAA) { 167 // It should still be possible to run the inliner as a stand-alone SCC pass, 168 // for test scenarios. In that case, we default to the 169 // DefaultInlineAdvisor, which doesn't need to keep state between SCC pass 170 // runs. It also uses just the default InlineParams. 171 // In this case, we need to use the provided FAM, which is valid for the 172 // duration of the inliner pass, and thus the lifetime of the owned advisor. 173 // The one we would get from the MAM can be invalidated as a result of the 174 // inliner's activity. 175 OwnedAdvisor = std::make_unique<DefaultInlineAdvisor>( 176 M, FAM, getInlineParams(), 177 InlineContext{LTOPhase, InlinePass::CGSCCInliner}); 178 179 if (!CGSCCInlineReplayFile.empty()) 180 OwnedAdvisor = getReplayInlineAdvisor( 181 M, FAM, M.getContext(), std::move(OwnedAdvisor), 182 ReplayInlinerSettings{CGSCCInlineReplayFile, 183 CGSCCInlineReplayScope, 184 CGSCCInlineReplayFallback, 185 {CGSCCInlineReplayFormat}}, 186 /*EmitRemarks=*/true, 187 InlineContext{LTOPhase, InlinePass::ReplayCGSCCInliner}); 188 189 return *OwnedAdvisor; 190 } 191 assert(IAA->getAdvisor() && 192 "Expected a present InlineAdvisorAnalysis also have an " 193 "InlineAdvisor initialized"); 194 return *IAA->getAdvisor(); 195 } 196 197 void makeFunctionBodyUnreachable(Function &F) { 198 F.dropAllReferences(); 199 for (BasicBlock &BB : make_early_inc_range(F)) 200 BB.eraseFromParent(); 201 BasicBlock *BB = BasicBlock::Create(F.getContext(), "", &F); 202 new UnreachableInst(F.getContext(), BB); 203 } 204 205 PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC, 206 CGSCCAnalysisManager &AM, LazyCallGraph &CG, 207 CGSCCUpdateResult &UR) { 208 const auto &MAMProxy = 209 AM.getResult<ModuleAnalysisManagerCGSCCProxy>(InitialC, CG); 210 bool Changed = false; 211 212 assert(InitialC.size() > 0 && "Cannot handle an empty SCC!"); 213 Module &M = *InitialC.begin()->getFunction().getParent(); 214 ProfileSummaryInfo *PSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(M); 215 216 FunctionAnalysisManager &FAM = 217 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(InitialC, CG) 218 .getManager(); 219 220 InlineAdvisor &Advisor = getAdvisor(MAMProxy, FAM, M); 221 Advisor.onPassEntry(&InitialC); 222 223 // We use a single common worklist for calls across the entire SCC. We 224 // process these in-order and append new calls introduced during inlining to 225 // the end. The PriorityInlineOrder is optional here, in which the smaller 226 // callee would have a higher priority to inline. 227 // 228 // Note that this particular order of processing is actually critical to 229 // avoid very bad behaviors. Consider *highly connected* call graphs where 230 // each function contains a small amount of code and a couple of calls to 231 // other functions. Because the LLVM inliner is fundamentally a bottom-up 232 // inliner, it can handle gracefully the fact that these all appear to be 233 // reasonable inlining candidates as it will flatten things until they become 234 // too big to inline, and then move on and flatten another batch. 235 // 236 // However, when processing call edges *within* an SCC we cannot rely on this 237 // bottom-up behavior. As a consequence, with heavily connected *SCCs* of 238 // functions we can end up incrementally inlining N calls into each of 239 // N functions because each incremental inlining decision looks good and we 240 // don't have a topological ordering to prevent explosions. 241 // 242 // To compensate for this, we don't process transitive edges made immediate 243 // by inlining until we've done one pass of inlining across the entire SCC. 244 // Large, highly connected SCCs still lead to some amount of code bloat in 245 // this model, but it is uniformly spread across all the functions in the SCC 246 // and eventually they all become too large to inline, rather than 247 // incrementally maknig a single function grow in a super linear fashion. 248 SmallVector<std::pair<CallBase *, int>, 16> Calls; 249 250 // Populate the initial list of calls in this SCC. 251 for (auto &N : InitialC) { 252 auto &ORE = 253 FAM.getResult<OptimizationRemarkEmitterAnalysis>(N.getFunction()); 254 // We want to generally process call sites top-down in order for 255 // simplifications stemming from replacing the call with the returned value 256 // after inlining to be visible to subsequent inlining decisions. 257 // FIXME: Using instructions sequence is a really bad way to do this. 258 // Instead we should do an actual RPO walk of the function body. 259 for (Instruction &I : instructions(N.getFunction())) 260 if (auto *CB = dyn_cast<CallBase>(&I)) 261 if (Function *Callee = CB->getCalledFunction()) { 262 if (!Callee->isDeclaration()) 263 Calls.push_back({CB, -1}); 264 else if (!isa<IntrinsicInst>(I)) { 265 using namespace ore; 266 setInlineRemark(*CB, "unavailable definition"); 267 ORE.emit([&]() { 268 return OptimizationRemarkMissed(DEBUG_TYPE, "NoDefinition", &I) 269 << NV("Callee", Callee) << " will not be inlined into " 270 << NV("Caller", CB->getCaller()) 271 << " because its definition is unavailable" 272 << setIsVerbose(); 273 }); 274 } 275 } 276 } 277 278 // Capture updatable variable for the current SCC. 279 auto *C = &InitialC; 280 281 auto AdvisorOnExit = make_scope_exit([&] { Advisor.onPassExit(C); }); 282 283 if (Calls.empty()) 284 return PreservedAnalyses::all(); 285 286 // When inlining a callee produces new call sites, we want to keep track of 287 // the fact that they were inlined from the callee. This allows us to avoid 288 // infinite inlining in some obscure cases. To represent this, we use an 289 // index into the InlineHistory vector. 290 SmallVector<std::pair<Function *, int>, 16> InlineHistory; 291 292 // Track a set vector of inlined callees so that we can augment the caller 293 // with all of their edges in the call graph before pruning out the ones that 294 // got simplified away. 295 SmallSetVector<Function *, 4> InlinedCallees; 296 297 // Track the dead functions to delete once finished with inlining calls. We 298 // defer deleting these to make it easier to handle the call graph updates. 299 SmallVector<Function *, 4> DeadFunctions; 300 301 // Track potentially dead non-local functions with comdats to see if they can 302 // be deleted as a batch after inlining. 303 SmallVector<Function *, 4> DeadFunctionsInComdats; 304 305 // Loop forward over all of the calls. Note that we cannot cache the size as 306 // inlining can introduce new calls that need to be processed. 307 for (int I = 0; I < (int)Calls.size(); ++I) { 308 // We expect the calls to typically be batched with sequences of calls that 309 // have the same caller, so we first set up some shared infrastructure for 310 // this caller. We also do any pruning we can at this layer on the caller 311 // alone. 312 Function &F = *Calls[I].first->getCaller(); 313 LazyCallGraph::Node &N = *CG.lookup(F); 314 if (CG.lookupSCC(N) != C) 315 continue; 316 317 LLVM_DEBUG(dbgs() << "Inlining calls in: " << F.getName() << "\n" 318 << " Function size: " << F.getInstructionCount() 319 << "\n"); 320 321 auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & { 322 return FAM.getResult<AssumptionAnalysis>(F); 323 }; 324 325 // Now process as many calls as we have within this caller in the sequence. 326 // We bail out as soon as the caller has to change so we can update the 327 // call graph and prepare the context of that new caller. 328 bool DidInline = false; 329 for (; I < (int)Calls.size() && Calls[I].first->getCaller() == &F; ++I) { 330 auto &P = Calls[I]; 331 CallBase *CB = P.first; 332 const int InlineHistoryID = P.second; 333 Function &Callee = *CB->getCalledFunction(); 334 335 if (InlineHistoryID != -1 && 336 inlineHistoryIncludes(&Callee, InlineHistoryID, InlineHistory)) { 337 LLVM_DEBUG(dbgs() << "Skipping inlining due to history: " << F.getName() 338 << " -> " << Callee.getName() << "\n"); 339 setInlineRemark(*CB, "recursive"); 340 // Set noinline so that we don't forget this decision across CGSCC 341 // iterations. 342 CB->setIsNoInline(); 343 continue; 344 } 345 346 // Check if this inlining may repeat breaking an SCC apart that has 347 // already been split once before. In that case, inlining here may 348 // trigger infinite inlining, much like is prevented within the inliner 349 // itself by the InlineHistory above, but spread across CGSCC iterations 350 // and thus hidden from the full inline history. 351 LazyCallGraph::SCC *CalleeSCC = CG.lookupSCC(*CG.lookup(Callee)); 352 if (CalleeSCC == C && UR.InlinedInternalEdges.count({&N, C})) { 353 LLVM_DEBUG(dbgs() << "Skipping inlining internal SCC edge from a node " 354 "previously split out of this SCC by inlining: " 355 << F.getName() << " -> " << Callee.getName() << "\n"); 356 setInlineRemark(*CB, "recursive SCC split"); 357 continue; 358 } 359 360 std::unique_ptr<InlineAdvice> Advice = 361 Advisor.getAdvice(*CB, OnlyMandatory); 362 363 // Check whether we want to inline this callsite. 364 if (!Advice) 365 continue; 366 367 if (!Advice->isInliningRecommended()) { 368 Advice->recordUnattemptedInlining(); 369 continue; 370 } 371 372 int CBCostMult = 373 getStringFnAttrAsInt( 374 *CB, InlineConstants::FunctionInlineCostMultiplierAttributeName) 375 .value_or(1); 376 377 // Setup the data structure used to plumb customization into the 378 // `InlineFunction` routine. 379 InlineFunctionInfo IFI( 380 GetAssumptionCache, PSI, 381 &FAM.getResult<BlockFrequencyAnalysis>(*(CB->getCaller())), 382 &FAM.getResult<BlockFrequencyAnalysis>(Callee)); 383 384 InlineResult IR = 385 InlineFunction(*CB, IFI, /*MergeAttributes=*/true, 386 &FAM.getResult<AAManager>(*CB->getCaller())); 387 if (!IR.isSuccess()) { 388 Advice->recordUnsuccessfulInlining(IR); 389 continue; 390 } 391 392 DidInline = true; 393 InlinedCallees.insert(&Callee); 394 ++NumInlined; 395 396 LLVM_DEBUG(dbgs() << " Size after inlining: " 397 << F.getInstructionCount() << "\n"); 398 399 // Add any new callsites to defined functions to the worklist. 400 if (!IFI.InlinedCallSites.empty()) { 401 int NewHistoryID = InlineHistory.size(); 402 InlineHistory.push_back({&Callee, InlineHistoryID}); 403 404 for (CallBase *ICB : reverse(IFI.InlinedCallSites)) { 405 Function *NewCallee = ICB->getCalledFunction(); 406 assert(!(NewCallee && NewCallee->isIntrinsic()) && 407 "Intrinsic calls should not be tracked."); 408 if (!NewCallee) { 409 // Try to promote an indirect (virtual) call without waiting for 410 // the post-inline cleanup and the next DevirtSCCRepeatedPass 411 // iteration because the next iteration may not happen and we may 412 // miss inlining it. 413 if (tryPromoteCall(*ICB)) 414 NewCallee = ICB->getCalledFunction(); 415 } 416 if (NewCallee) { 417 if (!NewCallee->isDeclaration()) { 418 Calls.push_back({ICB, NewHistoryID}); 419 // Continually inlining through an SCC can result in huge compile 420 // times and bloated code since we arbitrarily stop at some point 421 // when the inliner decides it's not profitable to inline anymore. 422 // We attempt to mitigate this by making these calls exponentially 423 // more expensive. 424 // This doesn't apply to calls in the same SCC since if we do 425 // inline through the SCC the function will end up being 426 // self-recursive which the inliner bails out on, and inlining 427 // within an SCC is necessary for performance. 428 if (CalleeSCC != C && 429 CalleeSCC == CG.lookupSCC(CG.get(*NewCallee))) { 430 Attribute NewCBCostMult = Attribute::get( 431 M.getContext(), 432 InlineConstants::FunctionInlineCostMultiplierAttributeName, 433 itostr(CBCostMult * IntraSCCCostMultiplier)); 434 ICB->addFnAttr(NewCBCostMult); 435 } 436 } 437 } 438 } 439 } 440 441 // For local functions or discardable functions without comdats, check 442 // whether this makes the callee trivially dead. In that case, we can drop 443 // the body of the function eagerly which may reduce the number of callers 444 // of other functions to one, changing inline cost thresholds. Non-local 445 // discardable functions with comdats are checked later on. 446 bool CalleeWasDeleted = false; 447 if (Callee.isDiscardableIfUnused() && Callee.hasZeroLiveUses() && 448 !CG.isLibFunction(Callee)) { 449 if (Callee.hasLocalLinkage() || !Callee.hasComdat()) { 450 Calls.erase( 451 std::remove_if(Calls.begin() + I + 1, Calls.end(), 452 [&](const std::pair<CallBase *, int> &Call) { 453 return Call.first->getCaller() == &Callee; 454 }), 455 Calls.end()); 456 457 // Clear the body and queue the function itself for call graph 458 // updating when we finish inlining. 459 makeFunctionBodyUnreachable(Callee); 460 assert(!is_contained(DeadFunctions, &Callee) && 461 "Cannot put cause a function to become dead twice!"); 462 DeadFunctions.push_back(&Callee); 463 CalleeWasDeleted = true; 464 } else { 465 DeadFunctionsInComdats.push_back(&Callee); 466 } 467 } 468 if (CalleeWasDeleted) 469 Advice->recordInliningWithCalleeDeleted(); 470 else 471 Advice->recordInlining(); 472 } 473 474 // Back the call index up by one to put us in a good position to go around 475 // the outer loop. 476 --I; 477 478 if (!DidInline) 479 continue; 480 Changed = true; 481 482 // At this point, since we have made changes we have at least removed 483 // a call instruction. However, in the process we do some incremental 484 // simplification of the surrounding code. This simplification can 485 // essentially do all of the same things as a function pass and we can 486 // re-use the exact same logic for updating the call graph to reflect the 487 // change. 488 489 // Inside the update, we also update the FunctionAnalysisManager in the 490 // proxy for this particular SCC. We do this as the SCC may have changed and 491 // as we're going to mutate this particular function we want to make sure 492 // the proxy is in place to forward any invalidation events. 493 LazyCallGraph::SCC *OldC = C; 494 C = &updateCGAndAnalysisManagerForCGSCCPass(CG, *C, N, AM, UR, FAM); 495 LLVM_DEBUG(dbgs() << "Updated inlining SCC: " << *C << "\n"); 496 497 // If this causes an SCC to split apart into multiple smaller SCCs, there 498 // is a subtle risk we need to prepare for. Other transformations may 499 // expose an "infinite inlining" opportunity later, and because of the SCC 500 // mutation, we will revisit this function and potentially re-inline. If we 501 // do, and that re-inlining also has the potentially to mutate the SCC 502 // structure, the infinite inlining problem can manifest through infinite 503 // SCC splits and merges. To avoid this, we capture the originating caller 504 // node and the SCC containing the call edge. This is a slight over 505 // approximation of the possible inlining decisions that must be avoided, 506 // but is relatively efficient to store. We use C != OldC to know when 507 // a new SCC is generated and the original SCC may be generated via merge 508 // in later iterations. 509 // 510 // It is also possible that even if no new SCC is generated 511 // (i.e., C == OldC), the original SCC could be split and then merged 512 // into the same one as itself. and the original SCC will be added into 513 // UR.CWorklist again, we want to catch such cases too. 514 // 515 // FIXME: This seems like a very heavyweight way of retaining the inline 516 // history, we should look for a more efficient way of tracking it. 517 if ((C != OldC || UR.CWorklist.count(OldC)) && 518 llvm::any_of(InlinedCallees, [&](Function *Callee) { 519 return CG.lookupSCC(*CG.lookup(*Callee)) == OldC; 520 })) { 521 LLVM_DEBUG(dbgs() << "Inlined an internal call edge and split an SCC, " 522 "retaining this to avoid infinite inlining.\n"); 523 UR.InlinedInternalEdges.insert({&N, OldC}); 524 } 525 InlinedCallees.clear(); 526 527 // Invalidate analyses for this function now so that we don't have to 528 // invalidate analyses for all functions in this SCC later. 529 FAM.invalidate(F, PreservedAnalyses::none()); 530 } 531 532 // We must ensure that we only delete functions with comdats if every function 533 // in the comdat is going to be deleted. 534 if (!DeadFunctionsInComdats.empty()) { 535 filterDeadComdatFunctions(DeadFunctionsInComdats); 536 for (auto *Callee : DeadFunctionsInComdats) 537 makeFunctionBodyUnreachable(*Callee); 538 DeadFunctions.append(DeadFunctionsInComdats); 539 } 540 541 // Now that we've finished inlining all of the calls across this SCC, delete 542 // all of the trivially dead functions, updating the call graph and the CGSCC 543 // pass manager in the process. 544 // 545 // Note that this walks a pointer set which has non-deterministic order but 546 // that is OK as all we do is delete things and add pointers to unordered 547 // sets. 548 for (Function *DeadF : DeadFunctions) { 549 CG.markDeadFunction(*DeadF); 550 // Get the necessary information out of the call graph and nuke the 551 // function there. Also, clear out any cached analyses. 552 auto &DeadC = *CG.lookupSCC(*CG.lookup(*DeadF)); 553 FAM.clear(*DeadF, DeadF->getName()); 554 AM.clear(DeadC, DeadC.getName()); 555 556 // Mark the relevant parts of the call graph as invalid so we don't visit 557 // them. 558 UR.InvalidatedSCCs.insert(&DeadC); 559 560 UR.DeadFunctions.push_back(DeadF); 561 562 ++NumDeleted; 563 } 564 565 if (!Changed) 566 return PreservedAnalyses::all(); 567 568 PreservedAnalyses PA; 569 // Even if we change the IR, we update the core CGSCC data structures and so 570 // can preserve the proxy to the function analysis manager. 571 PA.preserve<FunctionAnalysisManagerCGSCCProxy>(); 572 // We have already invalidated all analyses on modified functions. 573 PA.preserveSet<AllAnalysesOn<Function>>(); 574 return PA; 575 } 576 577 ModuleInlinerWrapperPass::ModuleInlinerWrapperPass(InlineParams Params, 578 bool MandatoryFirst, 579 InlineContext IC, 580 InliningAdvisorMode Mode, 581 unsigned MaxDevirtIterations) 582 : Params(Params), IC(IC), Mode(Mode), 583 MaxDevirtIterations(MaxDevirtIterations) { 584 // Run the inliner first. The theory is that we are walking bottom-up and so 585 // the callees have already been fully optimized, and we want to inline them 586 // into the callers so that our optimizations can reflect that. 587 // For PreLinkThinLTO pass, we disable hot-caller heuristic for sample PGO 588 // because it makes profile annotation in the backend inaccurate. 589 if (MandatoryFirst) { 590 PM.addPass(InlinerPass(/*OnlyMandatory*/ true)); 591 if (EnablePostSCCAdvisorPrinting) 592 PM.addPass(InlineAdvisorAnalysisPrinterPass(dbgs())); 593 } 594 PM.addPass(InlinerPass()); 595 if (EnablePostSCCAdvisorPrinting) 596 PM.addPass(InlineAdvisorAnalysisPrinterPass(dbgs())); 597 } 598 599 PreservedAnalyses ModuleInlinerWrapperPass::run(Module &M, 600 ModuleAnalysisManager &MAM) { 601 auto &IAA = MAM.getResult<InlineAdvisorAnalysis>(M); 602 if (!IAA.tryCreate(Params, Mode, 603 {CGSCCInlineReplayFile, 604 CGSCCInlineReplayScope, 605 CGSCCInlineReplayFallback, 606 {CGSCCInlineReplayFormat}}, 607 IC)) { 608 M.getContext().emitError( 609 "Could not setup Inlining Advisor for the requested " 610 "mode and/or options"); 611 return PreservedAnalyses::all(); 612 } 613 614 // We wrap the CGSCC pipeline in a devirtualization repeater. This will try 615 // to detect when we devirtualize indirect calls and iterate the SCC passes 616 // in that case to try and catch knock-on inlining or function attrs 617 // opportunities. Then we add it to the module pipeline by walking the SCCs 618 // in postorder (or bottom-up). 619 // If MaxDevirtIterations is 0, we just don't use the devirtualization 620 // wrapper. 621 if (MaxDevirtIterations == 0) 622 MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(PM))); 623 else 624 MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor( 625 createDevirtSCCRepeatedPass(std::move(PM), MaxDevirtIterations))); 626 627 MPM.addPass(std::move(AfterCGMPM)); 628 MPM.run(M, MAM); 629 630 // Discard the InlineAdvisor, a subsequent inlining session should construct 631 // its own. 632 auto PA = PreservedAnalyses::all(); 633 if (!KeepAdvisorForPrinting) 634 PA.abandon<InlineAdvisorAnalysis>(); 635 return PA; 636 } 637 638 void InlinerPass::printPipeline( 639 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) { 640 static_cast<PassInfoMixin<InlinerPass> *>(this)->printPipeline( 641 OS, MapClassName2PassName); 642 if (OnlyMandatory) 643 OS << "<only-mandatory>"; 644 } 645 646 void ModuleInlinerWrapperPass::printPipeline( 647 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) { 648 // Print some info about passes added to the wrapper. This is however 649 // incomplete as InlineAdvisorAnalysis part isn't included (which also depends 650 // on Params and Mode). 651 if (!MPM.isEmpty()) { 652 MPM.printPipeline(OS, MapClassName2PassName); 653 OS << ','; 654 } 655 OS << "cgscc("; 656 if (MaxDevirtIterations != 0) 657 OS << "devirt<" << MaxDevirtIterations << ">("; 658 PM.printPipeline(OS, MapClassName2PassName); 659 if (MaxDevirtIterations != 0) 660 OS << ')'; 661 OS << ')'; 662 } 663