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 PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC, 201 CGSCCAnalysisManager &AM, LazyCallGraph &CG, 202 CGSCCUpdateResult &UR) { 203 const auto &MAMProxy = 204 AM.getResult<ModuleAnalysisManagerCGSCCProxy>(InitialC, CG); 205 bool Changed = false; 206 207 assert(InitialC.size() > 0 && "Cannot handle an empty SCC!"); 208 Module &M = *InitialC.begin()->getFunction().getParent(); 209 ProfileSummaryInfo *PSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(M); 210 211 FunctionAnalysisManager &FAM = 212 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(InitialC, CG) 213 .getManager(); 214 215 InlineAdvisor &Advisor = getAdvisor(MAMProxy, FAM, M); 216 Advisor.onPassEntry(&InitialC); 217 218 auto AdvisorOnExit = make_scope_exit([&] { Advisor.onPassExit(&InitialC); }); 219 220 // We use a single common worklist for calls across the entire SCC. We 221 // process these in-order and append new calls introduced during inlining to 222 // the end. The PriorityInlineOrder is optional here, in which the smaller 223 // callee would have a higher priority to inline. 224 // 225 // Note that this particular order of processing is actually critical to 226 // avoid very bad behaviors. Consider *highly connected* call graphs where 227 // each function contains a small amount of code and a couple of calls to 228 // other functions. Because the LLVM inliner is fundamentally a bottom-up 229 // inliner, it can handle gracefully the fact that these all appear to be 230 // reasonable inlining candidates as it will flatten things until they become 231 // too big to inline, and then move on and flatten another batch. 232 // 233 // However, when processing call edges *within* an SCC we cannot rely on this 234 // bottom-up behavior. As a consequence, with heavily connected *SCCs* of 235 // functions we can end up incrementally inlining N calls into each of 236 // N functions because each incremental inlining decision looks good and we 237 // don't have a topological ordering to prevent explosions. 238 // 239 // To compensate for this, we don't process transitive edges made immediate 240 // by inlining until we've done one pass of inlining across the entire SCC. 241 // Large, highly connected SCCs still lead to some amount of code bloat in 242 // this model, but it is uniformly spread across all the functions in the SCC 243 // and eventually they all become too large to inline, rather than 244 // incrementally maknig a single function grow in a super linear fashion. 245 SmallVector<std::pair<CallBase *, int>, 16> Calls; 246 247 // Populate the initial list of calls in this SCC. 248 for (auto &N : InitialC) { 249 auto &ORE = 250 FAM.getResult<OptimizationRemarkEmitterAnalysis>(N.getFunction()); 251 // We want to generally process call sites top-down in order for 252 // simplifications stemming from replacing the call with the returned value 253 // after inlining to be visible to subsequent inlining decisions. 254 // FIXME: Using instructions sequence is a really bad way to do this. 255 // Instead we should do an actual RPO walk of the function body. 256 for (Instruction &I : instructions(N.getFunction())) 257 if (auto *CB = dyn_cast<CallBase>(&I)) 258 if (Function *Callee = CB->getCalledFunction()) { 259 if (!Callee->isDeclaration()) 260 Calls.push_back({CB, -1}); 261 else if (!isa<IntrinsicInst>(I)) { 262 using namespace ore; 263 setInlineRemark(*CB, "unavailable definition"); 264 ORE.emit([&]() { 265 return OptimizationRemarkMissed(DEBUG_TYPE, "NoDefinition", &I) 266 << NV("Callee", Callee) << " will not be inlined into " 267 << NV("Caller", CB->getCaller()) 268 << " because its definition is unavailable" 269 << setIsVerbose(); 270 }); 271 } 272 } 273 } 274 if (Calls.empty()) 275 return PreservedAnalyses::all(); 276 277 // Capture updatable variable for the current SCC. 278 auto *C = &InitialC; 279 280 // When inlining a callee produces new call sites, we want to keep track of 281 // the fact that they were inlined from the callee. This allows us to avoid 282 // infinite inlining in some obscure cases. To represent this, we use an 283 // index into the InlineHistory vector. 284 SmallVector<std::pair<Function *, int>, 16> InlineHistory; 285 286 // Track a set vector of inlined callees so that we can augment the caller 287 // with all of their edges in the call graph before pruning out the ones that 288 // got simplified away. 289 SmallSetVector<Function *, 4> InlinedCallees; 290 291 // Track the dead functions to delete once finished with inlining calls. We 292 // defer deleting these to make it easier to handle the call graph updates. 293 SmallVector<Function *, 4> DeadFunctions; 294 295 // Track potentially dead non-local functions with comdats to see if they can 296 // be deleted as a batch after inlining. 297 SmallVector<Function *, 4> DeadFunctionsInComdats; 298 299 // Loop forward over all of the calls. Note that we cannot cache the size as 300 // inlining can introduce new calls that need to be processed. 301 for (int I = 0; I < (int)Calls.size(); ++I) { 302 // We expect the calls to typically be batched with sequences of calls that 303 // have the same caller, so we first set up some shared infrastructure for 304 // this caller. We also do any pruning we can at this layer on the caller 305 // alone. 306 Function &F = *Calls[I].first->getCaller(); 307 LazyCallGraph::Node &N = *CG.lookup(F); 308 if (CG.lookupSCC(N) != C) 309 continue; 310 311 LLVM_DEBUG(dbgs() << "Inlining calls in: " << F.getName() << "\n" 312 << " Function size: " << F.getInstructionCount() 313 << "\n"); 314 315 auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & { 316 return FAM.getResult<AssumptionAnalysis>(F); 317 }; 318 319 // Now process as many calls as we have within this caller in the sequence. 320 // We bail out as soon as the caller has to change so we can update the 321 // call graph and prepare the context of that new caller. 322 bool DidInline = false; 323 for (; I < (int)Calls.size() && Calls[I].first->getCaller() == &F; ++I) { 324 auto &P = Calls[I]; 325 CallBase *CB = P.first; 326 const int InlineHistoryID = P.second; 327 Function &Callee = *CB->getCalledFunction(); 328 329 if (InlineHistoryID != -1 && 330 inlineHistoryIncludes(&Callee, InlineHistoryID, InlineHistory)) { 331 LLVM_DEBUG(dbgs() << "Skipping inlining due to history: " << F.getName() 332 << " -> " << Callee.getName() << "\n"); 333 setInlineRemark(*CB, "recursive"); 334 // Set noinline so that we don't forget this decision across CGSCC 335 // iterations. 336 CB->setIsNoInline(); 337 continue; 338 } 339 340 // Check if this inlining may repeat breaking an SCC apart that has 341 // already been split once before. In that case, inlining here may 342 // trigger infinite inlining, much like is prevented within the inliner 343 // itself by the InlineHistory above, but spread across CGSCC iterations 344 // and thus hidden from the full inline history. 345 LazyCallGraph::SCC *CalleeSCC = CG.lookupSCC(*CG.lookup(Callee)); 346 if (CalleeSCC == C && UR.InlinedInternalEdges.count({&N, C})) { 347 LLVM_DEBUG(dbgs() << "Skipping inlining internal SCC edge from a node " 348 "previously split out of this SCC by inlining: " 349 << F.getName() << " -> " << Callee.getName() << "\n"); 350 setInlineRemark(*CB, "recursive SCC split"); 351 continue; 352 } 353 354 std::unique_ptr<InlineAdvice> Advice = 355 Advisor.getAdvice(*CB, OnlyMandatory); 356 357 // Check whether we want to inline this callsite. 358 if (!Advice) 359 continue; 360 361 if (!Advice->isInliningRecommended()) { 362 Advice->recordUnattemptedInlining(); 363 continue; 364 } 365 366 int CBCostMult = 367 getStringFnAttrAsInt( 368 *CB, InlineConstants::FunctionInlineCostMultiplierAttributeName) 369 .value_or(1); 370 371 // Setup the data structure used to plumb customization into the 372 // `InlineFunction` routine. 373 InlineFunctionInfo IFI( 374 GetAssumptionCache, PSI, 375 &FAM.getResult<BlockFrequencyAnalysis>(*(CB->getCaller())), 376 &FAM.getResult<BlockFrequencyAnalysis>(Callee)); 377 378 InlineResult IR = 379 InlineFunction(*CB, IFI, /*MergeAttributes=*/true, 380 &FAM.getResult<AAManager>(*CB->getCaller())); 381 if (!IR.isSuccess()) { 382 Advice->recordUnsuccessfulInlining(IR); 383 continue; 384 } 385 386 DidInline = true; 387 InlinedCallees.insert(&Callee); 388 ++NumInlined; 389 390 LLVM_DEBUG(dbgs() << " Size after inlining: " 391 << F.getInstructionCount() << "\n"); 392 393 // Add any new callsites to defined functions to the worklist. 394 if (!IFI.InlinedCallSites.empty()) { 395 int NewHistoryID = InlineHistory.size(); 396 InlineHistory.push_back({&Callee, InlineHistoryID}); 397 398 for (CallBase *ICB : reverse(IFI.InlinedCallSites)) { 399 Function *NewCallee = ICB->getCalledFunction(); 400 assert(!(NewCallee && NewCallee->isIntrinsic()) && 401 "Intrinsic calls should not be tracked."); 402 if (!NewCallee) { 403 // Try to promote an indirect (virtual) call without waiting for 404 // the post-inline cleanup and the next DevirtSCCRepeatedPass 405 // iteration because the next iteration may not happen and we may 406 // miss inlining it. 407 if (tryPromoteCall(*ICB)) 408 NewCallee = ICB->getCalledFunction(); 409 } 410 if (NewCallee) { 411 if (!NewCallee->isDeclaration()) { 412 Calls.push_back({ICB, NewHistoryID}); 413 // Continually inlining through an SCC can result in huge compile 414 // times and bloated code since we arbitrarily stop at some point 415 // when the inliner decides it's not profitable to inline anymore. 416 // We attempt to mitigate this by making these calls exponentially 417 // more expensive. 418 // This doesn't apply to calls in the same SCC since if we do 419 // inline through the SCC the function will end up being 420 // self-recursive which the inliner bails out on, and inlining 421 // within an SCC is necessary for performance. 422 if (CalleeSCC != C && 423 CalleeSCC == CG.lookupSCC(CG.get(*NewCallee))) { 424 Attribute NewCBCostMult = Attribute::get( 425 M.getContext(), 426 InlineConstants::FunctionInlineCostMultiplierAttributeName, 427 itostr(CBCostMult * IntraSCCCostMultiplier)); 428 ICB->addFnAttr(NewCBCostMult); 429 } 430 } 431 } 432 } 433 } 434 435 // For local functions or discardable functions without comdats, check 436 // whether this makes the callee trivially dead. In that case, we can drop 437 // the body of the function eagerly which may reduce the number of callers 438 // of other functions to one, changing inline cost thresholds. Non-local 439 // discardable functions with comdats are checked later on. 440 bool CalleeWasDeleted = false; 441 if (Callee.isDiscardableIfUnused() && Callee.hasZeroLiveUses() && 442 !CG.isLibFunction(Callee)) { 443 if (Callee.hasLocalLinkage() || !Callee.hasComdat()) { 444 Calls.erase( 445 std::remove_if(Calls.begin() + I + 1, Calls.end(), 446 [&](const std::pair<CallBase *, int> &Call) { 447 return Call.first->getCaller() == &Callee; 448 }), 449 Calls.end()); 450 451 // Clear the body and queue the function itself for deletion when we 452 // finish inlining and call graph updates. 453 // Note that after this point, it is an error to do anything other 454 // than use the callee's address or delete it. 455 Callee.dropAllReferences(); 456 assert(!is_contained(DeadFunctions, &Callee) && 457 "Cannot put cause a function to become dead twice!"); 458 DeadFunctions.push_back(&Callee); 459 CalleeWasDeleted = true; 460 } else { 461 DeadFunctionsInComdats.push_back(&Callee); 462 } 463 } 464 if (CalleeWasDeleted) 465 Advice->recordInliningWithCalleeDeleted(); 466 else 467 Advice->recordInlining(); 468 } 469 470 // Back the call index up by one to put us in a good position to go around 471 // the outer loop. 472 --I; 473 474 if (!DidInline) 475 continue; 476 Changed = true; 477 478 // At this point, since we have made changes we have at least removed 479 // a call instruction. However, in the process we do some incremental 480 // simplification of the surrounding code. This simplification can 481 // essentially do all of the same things as a function pass and we can 482 // re-use the exact same logic for updating the call graph to reflect the 483 // change. 484 485 // Inside the update, we also update the FunctionAnalysisManager in the 486 // proxy for this particular SCC. We do this as the SCC may have changed and 487 // as we're going to mutate this particular function we want to make sure 488 // the proxy is in place to forward any invalidation events. 489 LazyCallGraph::SCC *OldC = C; 490 C = &updateCGAndAnalysisManagerForCGSCCPass(CG, *C, N, AM, UR, FAM); 491 LLVM_DEBUG(dbgs() << "Updated inlining SCC: " << *C << "\n"); 492 493 // If this causes an SCC to split apart into multiple smaller SCCs, there 494 // is a subtle risk we need to prepare for. Other transformations may 495 // expose an "infinite inlining" opportunity later, and because of the SCC 496 // mutation, we will revisit this function and potentially re-inline. If we 497 // do, and that re-inlining also has the potentially to mutate the SCC 498 // structure, the infinite inlining problem can manifest through infinite 499 // SCC splits and merges. To avoid this, we capture the originating caller 500 // node and the SCC containing the call edge. This is a slight over 501 // approximation of the possible inlining decisions that must be avoided, 502 // but is relatively efficient to store. We use C != OldC to know when 503 // a new SCC is generated and the original SCC may be generated via merge 504 // in later iterations. 505 // 506 // It is also possible that even if no new SCC is generated 507 // (i.e., C == OldC), the original SCC could be split and then merged 508 // into the same one as itself. and the original SCC will be added into 509 // UR.CWorklist again, we want to catch such cases too. 510 // 511 // FIXME: This seems like a very heavyweight way of retaining the inline 512 // history, we should look for a more efficient way of tracking it. 513 if ((C != OldC || UR.CWorklist.count(OldC)) && 514 llvm::any_of(InlinedCallees, [&](Function *Callee) { 515 return CG.lookupSCC(*CG.lookup(*Callee)) == OldC; 516 })) { 517 LLVM_DEBUG(dbgs() << "Inlined an internal call edge and split an SCC, " 518 "retaining this to avoid infinite inlining.\n"); 519 UR.InlinedInternalEdges.insert({&N, OldC}); 520 } 521 InlinedCallees.clear(); 522 523 // Invalidate analyses for this function now so that we don't have to 524 // invalidate analyses for all functions in this SCC later. 525 FAM.invalidate(F, PreservedAnalyses::none()); 526 } 527 528 // We must ensure that we only delete functions with comdats if every function 529 // in the comdat is going to be deleted. 530 if (!DeadFunctionsInComdats.empty()) { 531 filterDeadComdatFunctions(DeadFunctionsInComdats); 532 for (auto *Callee : DeadFunctionsInComdats) 533 Callee->dropAllReferences(); 534 DeadFunctions.append(DeadFunctionsInComdats); 535 } 536 537 // Now that we've finished inlining all of the calls across this SCC, delete 538 // all of the trivially dead functions, updating the call graph and the CGSCC 539 // pass manager in the process. 540 // 541 // Note that this walks a pointer set which has non-deterministic order but 542 // that is OK as all we do is delete things and add pointers to unordered 543 // sets. 544 for (Function *DeadF : DeadFunctions) { 545 // Get the necessary information out of the call graph and nuke the 546 // function there. Also, clear out any cached analyses. 547 auto &DeadC = *CG.lookupSCC(*CG.lookup(*DeadF)); 548 FAM.clear(*DeadF, DeadF->getName()); 549 AM.clear(DeadC, DeadC.getName()); 550 auto &DeadRC = DeadC.getOuterRefSCC(); 551 CG.removeDeadFunction(*DeadF); 552 553 // Mark the relevant parts of the call graph as invalid so we don't visit 554 // them. 555 UR.InvalidatedSCCs.insert(&DeadC); 556 UR.InvalidatedRefSCCs.insert(&DeadRC); 557 558 // If the updated SCC was the one containing the deleted function, clear it. 559 if (&DeadC == UR.UpdatedC) 560 UR.UpdatedC = nullptr; 561 562 // And delete the actual function from the module. 563 M.getFunctionList().erase(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