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