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