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