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