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