LLVM 17.0.0git
Inliner.cpp
Go to the documentation of this file.
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
16#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/STLExtras.h"
19#include "llvm/ADT/ScopeExit.h"
20#include "llvm/ADT/SetVector.h"
23#include "llvm/ADT/Statistic.h"
25#include "llvm/ADT/StringRef.h"
39#include "llvm/IR/Attributes.h"
40#include "llvm/IR/BasicBlock.h"
41#include "llvm/IR/DebugLoc.h"
44#include "llvm/IR/Function.h"
46#include "llvm/IR/Instruction.h"
49#include "llvm/IR/Metadata.h"
50#include "llvm/IR/Module.h"
51#include "llvm/IR/PassManager.h"
52#include "llvm/IR/User.h"
53#include "llvm/IR/Value.h"
54#include "llvm/Pass.h"
57#include "llvm/Support/Debug.h"
63#include <algorithm>
64#include <cassert>
65#include <functional>
66#include <utility>
67#include <vector>
68
69using namespace llvm;
70
71#define DEBUG_TYPE "inline"
72
73STATISTIC(NumInlined, "Number of functions inlined");
74STATISTIC(NumCallsDeleted, "Number of call sites deleted, not inlined");
75STATISTIC(NumDeleted, "Number of functions deleted because all callers found");
76
78 "intra-scc-cost-multiplier", cl::init(2), cl::Hidden,
80 "Cost multiplier to multiply onto inlined call sites where the "
81 "new call was previously an intra-SCC call (not relevant when the "
82 "original call was already intra-SCC). This can accumulate over "
83 "multiple inlinings (e.g. if a call site already had a cost "
84 "multiplier and one of its inlined calls was also subject to "
85 "this, the inlined call would have the original multiplier "
86 "multiplied by intra-scc-cost-multiplier). This is to prevent tons of "
87 "inlining through a child SCC which can cause terrible compile times"));
88
89/// A flag for test, so we can print the content of the advisor when running it
90/// as part of the default (e.g. -O3) pipeline.
91static cl::opt<bool> KeepAdvisorForPrinting("keep-inline-advisor-for-printing",
92 cl::init(false), cl::Hidden);
93
94/// Allows printing the contents of the advisor after each SCC inliner pass.
95static cl::opt<bool>
96 EnablePostSCCAdvisorPrinting("enable-scc-inline-advisor-printing",
97 cl::init(false), cl::Hidden);
98
99namespace llvm {
101}
102
104 "cgscc-inline-replay", cl::init(""), 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
111 "cgscc-inline-replay-scope",
112 cl::init(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
124 "cgscc-inline-replay-fallback",
125 cl::init(ReplayInlinerSettings::Fallback::Original),
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
141 "cgscc-inline-replay-format",
142 cl::init(CallSiteFormat::Format::LineColumnDiscriminator),
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
155
156LegacyInlinerBase::LegacyInlinerBase(char &ID, bool InsertLifetime)
157 : CallGraphSCCPass(ID), InsertLifetime(InsertLifetime) {}
158
159/// For this class, we declare that we require and preserve the call graph.
160/// If the derived class implements this method, it should
161/// always explicitly call the implementation here.
168}
169
171
172/// If it is possible to inline the specified call site,
173/// do so and update the CallGraph for this operation.
174///
175/// This function also does some basic book-keeping to update the IR. The
176/// InlinedArrayAllocas map keeps track of any allocas that are already
177/// available from other functions inlined into the caller. If we are able to
178/// inline this call site we attempt to reuse already available allocas or add
179/// any new allocas to the set if not possible.
182 InlinedArrayAllocasTy &InlinedArrayAllocas, int InlineHistory,
183 bool InsertLifetime, function_ref<AAResults &(Function &)> &AARGetter,
184 ImportedFunctionsInliningStatistics &ImportedFunctionsStats) {
186 Function *Caller = CB.getCaller();
187
188 AAResults &AAR = AARGetter(*Callee);
189
190 // Try to inline the function. Get the list of static allocas that were
191 // inlined.
193 InlineFunction(CB, IFI,
194 /*MergeAttributes=*/true, &AAR, InsertLifetime);
195 if (!IR.isSuccess())
196 return IR;
197
199 ImportedFunctionsStats.recordInline(*Caller, *Callee);
200
201 return IR; // success
202}
203
204/// Return true if the specified inline history ID
205/// indicates an inline history that includes the specified function.
207 Function *F, int InlineHistoryID,
208 const SmallVectorImpl<std::pair<Function *, int>> &InlineHistory) {
209 while (InlineHistoryID != -1) {
210 assert(unsigned(InlineHistoryID) < InlineHistory.size() &&
211 "Invalid inline history ID");
212 if (InlineHistory[InlineHistoryID].first == F)
213 return true;
214 InlineHistoryID = InlineHistory[InlineHistoryID].second;
215 }
216 return false;
217}
218
222 return false; // No changes to CallGraph.
223}
224
226 if (skipSCC(SCC))
227 return false;
228 return inlineCalls(SCC);
229}
230
231static bool
233 std::function<AssumptionCache &(Function &)> GetAssumptionCache,
235 std::function<const TargetLibraryInfo &(Function &)> GetTLI,
236 bool InsertLifetime,
237 function_ref<InlineCost(CallBase &CB)> GetInlineCost,
238 function_ref<AAResults &(Function &)> AARGetter,
239 ImportedFunctionsInliningStatistics &ImportedFunctionsStats) {
240 SmallPtrSet<Function *, 8> SCCFunctions;
241 LLVM_DEBUG(dbgs() << "Inliner visiting SCC:");
242 for (CallGraphNode *Node : SCC) {
243 Function *F = Node->getFunction();
244 if (F)
245 SCCFunctions.insert(F);
246 LLVM_DEBUG(dbgs() << " " << (F ? F->getName() : "INDIRECTNODE"));
247 }
248
249 // Scan through and identify all call sites ahead of time so that we only
250 // inline call sites in the original functions, not call sites that result
251 // from inlining other functions.
253
254 // When inlining a callee produces new call sites, we want to keep track of
255 // the fact that they were inlined from the callee. This allows us to avoid
256 // infinite inlining in some obscure cases. To represent this, we use an
257 // index into the InlineHistory vector.
259
260 for (CallGraphNode *Node : SCC) {
261 Function *F = Node->getFunction();
262 if (!F || F->isDeclaration())
263 continue;
264
266 for (BasicBlock &BB : *F)
267 for (Instruction &I : BB) {
268 auto *CB = dyn_cast<CallBase>(&I);
269 // If this isn't a call, or it is a call to an intrinsic, it can
270 // never be inlined.
271 if (!CB || isa<IntrinsicInst>(I))
272 continue;
273
274 // If this is a direct call to an external function, we can never inline
275 // it. If it is an indirect call, inlining may resolve it to be a
276 // direct call, so we keep it.
277 if (Function *Callee = CB->getCalledFunction())
278 if (Callee->isDeclaration()) {
279 using namespace ore;
280
281 setInlineRemark(*CB, "unavailable definition");
282 ORE.emit([&]() {
283 return OptimizationRemarkMissed(DEBUG_TYPE, "NoDefinition", &I)
284 << NV("Callee", Callee) << " will not be inlined into "
285 << NV("Caller", CB->getCaller())
286 << " because its definition is unavailable"
287 << setIsVerbose();
288 });
289 continue;
290 }
291
292 CallSites.push_back(std::make_pair(CB, -1));
293 }
294 }
295
296 LLVM_DEBUG(dbgs() << ": " << CallSites.size() << " call sites.\n");
297
298 // If there are no calls in this function, exit early.
299 if (CallSites.empty())
300 return false;
301
302 // Now that we have all of the call sites, move the ones to functions in the
303 // current SCC to the end of the list.
304 unsigned FirstCallInSCC = CallSites.size();
305 for (unsigned I = 0; I < FirstCallInSCC; ++I)
306 if (Function *F = CallSites[I].first->getCalledFunction())
307 if (SCCFunctions.count(F))
308 std::swap(CallSites[I--], CallSites[--FirstCallInSCC]);
309
310 InlinedArrayAllocasTy InlinedArrayAllocas;
311 InlineFunctionInfo InlineInfo(&CG, GetAssumptionCache, PSI);
312
313 // Now that we have all of the call sites, loop over them and inline them if
314 // it looks profitable to do so.
315 bool Changed = false;
316 bool LocalChange;
317 do {
318 LocalChange = false;
319 // Iterate over the outer loop because inlining functions can cause indirect
320 // calls to become direct calls.
321 // CallSites may be modified inside so ranged for loop can not be used.
322 for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) {
323 auto &P = CallSites[CSi];
324 CallBase &CB = *P.first;
325 const int InlineHistoryID = P.second;
326
327 Function *Caller = CB.getCaller();
329
330 // We can only inline direct calls to non-declarations.
331 if (!Callee || Callee->isDeclaration())
332 continue;
333
334 bool IsTriviallyDead = isInstructionTriviallyDead(&CB, &GetTLI(*Caller));
335
336 if (!IsTriviallyDead) {
337 // If this call site was obtained by inlining another function, verify
338 // that the include path for the function did not include the callee
339 // itself. If so, we'd be recursively inlining the same function,
340 // which would provide the same callsites, which would cause us to
341 // infinitely inline.
342 if (InlineHistoryID != -1 &&
343 inlineHistoryIncludes(Callee, InlineHistoryID, InlineHistory)) {
344 setInlineRemark(CB, "recursive");
345 continue;
346 }
347 }
348
349 // FIXME for new PM: because of the old PM we currently generate ORE and
350 // in turn BFI on demand. With the new PM, the ORE dependency should
351 // just become a regular analysis dependency.
352 OptimizationRemarkEmitter ORE(Caller);
353
354 auto OIC = shouldInline(CB, GetInlineCost, ORE);
355 // If the policy determines that we should inline this function,
356 // delete the call instead.
357 if (!OIC)
358 continue;
359
360 // If this call site is dead and it is to a readonly function, we should
361 // just delete the call instead of trying to inline it, regardless of
362 // size. This happens because IPSCCP propagates the result out of the
363 // call and then we're left with the dead call.
364 if (IsTriviallyDead) {
365 LLVM_DEBUG(dbgs() << " -> Deleting dead call: " << CB << "\n");
366 // Update the call graph by deleting the edge from Callee to Caller.
367 setInlineRemark(CB, "trivially dead");
368 CG[Caller]->removeCallEdgeFor(CB);
369 CB.eraseFromParent();
370 ++NumCallsDeleted;
371 } else {
372 // Get DebugLoc to report. CB will be invalid after Inliner.
373 DebugLoc DLoc = CB.getDebugLoc();
374 BasicBlock *Block = CB.getParent();
375
376 // Attempt to inline the function.
377 using namespace ore;
378
380 CB, InlineInfo, InlinedArrayAllocas, InlineHistoryID,
381 InsertLifetime, AARGetter, ImportedFunctionsStats);
382 if (!IR.isSuccess()) {
383 setInlineRemark(CB, std::string(IR.getFailureReason()) + "; " +
384 inlineCostStr(*OIC));
385 ORE.emit([&]() {
386 return OptimizationRemarkMissed(DEBUG_TYPE, "NotInlined", DLoc,
387 Block)
388 << NV("Callee", Callee) << " will not be inlined into "
389 << NV("Caller", Caller) << ": "
390 << NV("Reason", IR.getFailureReason());
391 });
392 continue;
393 }
394 ++NumInlined;
395
396 emitInlinedIntoBasedOnCost(ORE, DLoc, Block, *Callee, *Caller, *OIC);
397
398 // If inlining this function gave us any new call sites, throw them
399 // onto our worklist to process. They are useful inline candidates.
400 if (!InlineInfo.InlinedCalls.empty()) {
401 // Create a new inline history entry for this, so that we remember
402 // that these new callsites came about due to inlining Callee.
403 int NewHistoryID = InlineHistory.size();
404 InlineHistory.push_back(std::make_pair(Callee, InlineHistoryID));
405
406#ifndef NDEBUG
407 // Make sure no dupplicates in the inline candidates. This could
408 // happen when a callsite is simpilfied to reusing the return value
409 // of another callsite during function cloning, thus the other
410 // callsite will be reconsidered here.
411 DenseSet<CallBase *> DbgCallSites;
412 for (auto &II : CallSites)
413 DbgCallSites.insert(II.first);
414#endif
415
416 for (Value *Ptr : InlineInfo.InlinedCalls) {
417#ifndef NDEBUG
418 assert(DbgCallSites.count(dyn_cast<CallBase>(Ptr)) == 0);
419#endif
420 CallSites.push_back(
421 std::make_pair(dyn_cast<CallBase>(Ptr), NewHistoryID));
422 }
423 }
424 }
425
426 // If we inlined or deleted the last possible call site to the function,
427 // delete the function body now.
428 assert(Callee && "Expected to be non-null due to check at start of loop");
429 if (Callee->use_empty() && Callee->hasLocalLinkage() &&
430 // TODO: Can remove if in SCC now.
431 !SCCFunctions.count(Callee) &&
432 // The function may be apparently dead, but if there are indirect
433 // callgraph references to the node, we cannot delete it yet, this
434 // could invalidate the CGSCC iterator.
435 CG[Callee]->getNumReferences() == 0) {
436 LLVM_DEBUG(dbgs() << " -> Deleting dead function: "
437 << Callee->getName() << "\n");
438 CallGraphNode *CalleeNode = CG[Callee];
439
440 // Remove any call graph edges from the callee to its callees.
441 CalleeNode->removeAllCalledFunctions();
442
443 // Removing the node for callee from the call graph and delete it.
444 delete CG.removeFunctionFromModule(CalleeNode);
445 ++NumDeleted;
446 }
447
448 // Remove this call site from the list. If possible, use
449 // swap/pop_back for efficiency, but do not use it if doing so would
450 // move a call site to a function in this SCC before the
451 // 'FirstCallInSCC' barrier.
452 if (SCC.isSingular()) {
453 CallSites[CSi] = CallSites.back();
454 CallSites.pop_back();
455 } else {
456 CallSites.erase(CallSites.begin() + CSi);
457 }
458 --CSi;
459
460 Changed = true;
461 LocalChange = true;
462 }
463 } while (LocalChange);
464
465 return Changed;
466}
467
469 CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
470 ACT = &getAnalysis<AssumptionCacheTracker>();
471 PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
472 GetTLI = [&](Function &F) -> const TargetLibraryInfo & {
473 return getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
474 };
475 auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
476 return ACT->getAssumptionCache(F);
477 };
478 return inlineCallsImpl(
479 SCC, CG, GetAssumptionCache, PSI, GetTLI, InsertLifetime,
480 [&](CallBase &CB) { return getInlineCost(CB); }, LegacyAARGetter(*this),
482}
483
484/// Remove now-dead linkonce functions at the end of
485/// processing to avoid breaking the SCC traversal.
490 return removeDeadFunctions(CG);
491}
492
493/// Remove dead functions that are not included in DNR (Do Not Remove) list.
495 bool AlwaysInlineOnly) {
496 SmallVector<CallGraphNode *, 16> FunctionsToRemove;
497 SmallVector<Function *, 16> DeadFunctionsInComdats;
498
499 auto RemoveCGN = [&](CallGraphNode *CGN) {
500 // Remove any call graph edges from the function to its callees.
501 CGN->removeAllCalledFunctions();
502
503 // Remove any edges from the external node to the function's call graph
504 // node. These edges might have been made irrelegant due to
505 // optimization of the program.
507
508 // Removing the node for callee from the call graph and delete it.
509 FunctionsToRemove.push_back(CGN);
510 };
511
512 // Scan for all of the functions, looking for ones that should now be removed
513 // from the program. Insert the dead ones in the FunctionsToRemove set.
514 for (const auto &I : CG) {
515 CallGraphNode *CGN = I.second.get();
516 Function *F = CGN->getFunction();
517 if (!F || F->isDeclaration())
518 continue;
519
520 // Handle the case when this function is called and we only want to care
521 // about always-inline functions. This is a bit of a hack to share code
522 // between here and the InlineAlways pass.
523 if (AlwaysInlineOnly && !F->hasFnAttribute(Attribute::AlwaysInline))
524 continue;
525
526 // If the only remaining users of the function are dead constants, remove
527 // them.
528 F->removeDeadConstantUsers();
529
530 if (!F->isDefTriviallyDead())
531 continue;
532
533 // It is unsafe to drop a function with discardable linkage from a COMDAT
534 // without also dropping the other members of the COMDAT.
535 // The inliner doesn't visit non-function entities which are in COMDAT
536 // groups so it is unsafe to do so *unless* the linkage is local.
537 if (!F->hasLocalLinkage()) {
538 if (F->hasComdat()) {
539 DeadFunctionsInComdats.push_back(F);
540 continue;
541 }
542 }
543
544 RemoveCGN(CGN);
545 }
546 if (!DeadFunctionsInComdats.empty()) {
547 // Filter out the functions whose comdats remain alive.
548 filterDeadComdatFunctions(DeadFunctionsInComdats);
549 // Remove the rest.
550 for (Function *F : DeadFunctionsInComdats)
551 RemoveCGN(CG[F]);
552 }
553
554 if (FunctionsToRemove.empty())
555 return false;
556
557 // Now that we know which functions to delete, do so. We didn't want to do
558 // this inline, because that would invalidate our CallGraph::iterator
559 // objects. :(
560 //
561 // Note that it doesn't matter that we are iterating over a non-stable order
562 // here to do this, it doesn't matter which order the functions are deleted
563 // in.
564 array_pod_sort(FunctionsToRemove.begin(), FunctionsToRemove.end());
565 FunctionsToRemove.erase(
566 std::unique(FunctionsToRemove.begin(), FunctionsToRemove.end()),
567 FunctionsToRemove.end());
568 for (CallGraphNode *CGN : FunctionsToRemove) {
569 delete CG.removeFunctionFromModule(CGN);
570 ++NumDeleted;
571 }
572 return true;
573}
574
576InlinerPass::getAdvisor(const ModuleAnalysisManagerCGSCCProxy::Result &MAM,
578 if (OwnedAdvisor)
579 return *OwnedAdvisor;
580
582 if (!IAA) {
583 // It should still be possible to run the inliner as a stand-alone SCC pass,
584 // for test scenarios. In that case, we default to the
585 // DefaultInlineAdvisor, which doesn't need to keep state between SCC pass
586 // runs. It also uses just the default InlineParams.
587 // In this case, we need to use the provided FAM, which is valid for the
588 // duration of the inliner pass, and thus the lifetime of the owned advisor.
589 // The one we would get from the MAM can be invalidated as a result of the
590 // inliner's activity.
591 OwnedAdvisor = std::make_unique<DefaultInlineAdvisor>(
592 M, FAM, getInlineParams(),
594
595 if (!CGSCCInlineReplayFile.empty())
596 OwnedAdvisor = getReplayInlineAdvisor(
597 M, FAM, M.getContext(), std::move(OwnedAdvisor),
598 ReplayInlinerSettings{CGSCCInlineReplayFile,
599 CGSCCInlineReplayScope,
600 CGSCCInlineReplayFallback,
601 {CGSCCInlineReplayFormat}},
602 /*EmitRemarks=*/true,
604
605 return *OwnedAdvisor;
606 }
607 assert(IAA->getAdvisor() &&
608 "Expected a present InlineAdvisorAnalysis also have an "
609 "InlineAdvisor initialized");
610 return *IAA->getAdvisor();
611}
612
615 CGSCCUpdateResult &UR) {
616 const auto &MAMProxy =
618 bool Changed = false;
619
620 assert(InitialC.size() > 0 && "Cannot handle an empty SCC!");
621 Module &M = *InitialC.begin()->getFunction().getParent();
622 ProfileSummaryInfo *PSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(M);
623
626 .getManager();
627
628 InlineAdvisor &Advisor = getAdvisor(MAMProxy, FAM, M);
629 Advisor.onPassEntry(&InitialC);
630
631 auto AdvisorOnExit = make_scope_exit([&] { Advisor.onPassExit(&InitialC); });
632
633 // We use a single common worklist for calls across the entire SCC. We
634 // process these in-order and append new calls introduced during inlining to
635 // the end. The PriorityInlineOrder is optional here, in which the smaller
636 // callee would have a higher priority to inline.
637 //
638 // Note that this particular order of processing is actually critical to
639 // avoid very bad behaviors. Consider *highly connected* call graphs where
640 // each function contains a small amount of code and a couple of calls to
641 // other functions. Because the LLVM inliner is fundamentally a bottom-up
642 // inliner, it can handle gracefully the fact that these all appear to be
643 // reasonable inlining candidates as it will flatten things until they become
644 // too big to inline, and then move on and flatten another batch.
645 //
646 // However, when processing call edges *within* an SCC we cannot rely on this
647 // bottom-up behavior. As a consequence, with heavily connected *SCCs* of
648 // functions we can end up incrementally inlining N calls into each of
649 // N functions because each incremental inlining decision looks good and we
650 // don't have a topological ordering to prevent explosions.
651 //
652 // To compensate for this, we don't process transitive edges made immediate
653 // by inlining until we've done one pass of inlining across the entire SCC.
654 // Large, highly connected SCCs still lead to some amount of code bloat in
655 // this model, but it is uniformly spread across all the functions in the SCC
656 // and eventually they all become too large to inline, rather than
657 // incrementally maknig a single function grow in a super linear fashion.
659
660 // Populate the initial list of calls in this SCC.
661 for (auto &N : InitialC) {
662 auto &ORE =
664 // We want to generally process call sites top-down in order for
665 // simplifications stemming from replacing the call with the returned value
666 // after inlining to be visible to subsequent inlining decisions.
667 // FIXME: Using instructions sequence is a really bad way to do this.
668 // Instead we should do an actual RPO walk of the function body.
669 for (Instruction &I : instructions(N.getFunction()))
670 if (auto *CB = dyn_cast<CallBase>(&I))
671 if (Function *Callee = CB->getCalledFunction()) {
672 if (!Callee->isDeclaration())
673 Calls.push_back({CB, -1});
674 else if (!isa<IntrinsicInst>(I)) {
675 using namespace ore;
676 setInlineRemark(*CB, "unavailable definition");
677 ORE.emit([&]() {
678 return OptimizationRemarkMissed(DEBUG_TYPE, "NoDefinition", &I)
679 << NV("Callee", Callee) << " will not be inlined into "
680 << NV("Caller", CB->getCaller())
681 << " because its definition is unavailable"
682 << setIsVerbose();
683 });
684 }
685 }
686 }
687 if (Calls.empty())
688 return PreservedAnalyses::all();
689
690 // Capture updatable variable for the current SCC.
691 auto *C = &InitialC;
692
693 // When inlining a callee produces new call sites, we want to keep track of
694 // the fact that they were inlined from the callee. This allows us to avoid
695 // infinite inlining in some obscure cases. To represent this, we use an
696 // index into the InlineHistory vector.
698
699 // Track a set vector of inlined callees so that we can augment the caller
700 // with all of their edges in the call graph before pruning out the ones that
701 // got simplified away.
702 SmallSetVector<Function *, 4> InlinedCallees;
703
704 // Track the dead functions to delete once finished with inlining calls. We
705 // defer deleting these to make it easier to handle the call graph updates.
706 SmallVector<Function *, 4> DeadFunctions;
707
708 // Track potentially dead non-local functions with comdats to see if they can
709 // be deleted as a batch after inlining.
710 SmallVector<Function *, 4> DeadFunctionsInComdats;
711
712 // Loop forward over all of the calls. Note that we cannot cache the size as
713 // inlining can introduce new calls that need to be processed.
714 for (int I = 0; I < (int)Calls.size(); ++I) {
715 // We expect the calls to typically be batched with sequences of calls that
716 // have the same caller, so we first set up some shared infrastructure for
717 // this caller. We also do any pruning we can at this layer on the caller
718 // alone.
719 Function &F = *Calls[I].first->getCaller();
720 LazyCallGraph::Node &N = *CG.lookup(F);
721 if (CG.lookupSCC(N) != C)
722 continue;
723
724 LLVM_DEBUG(dbgs() << "Inlining calls in: " << F.getName() << "\n"
725 << " Function size: " << F.getInstructionCount()
726 << "\n");
727
728 auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
730 };
731
732 // Now process as many calls as we have within this caller in the sequence.
733 // We bail out as soon as the caller has to change so we can update the
734 // call graph and prepare the context of that new caller.
735 bool DidInline = false;
736 for (; I < (int)Calls.size() && Calls[I].first->getCaller() == &F; ++I) {
737 auto &P = Calls[I];
738 CallBase *CB = P.first;
739 const int InlineHistoryID = P.second;
741
742 if (InlineHistoryID != -1 &&
743 inlineHistoryIncludes(&Callee, InlineHistoryID, InlineHistory)) {
744 LLVM_DEBUG(dbgs() << "Skipping inlining due to history: " << F.getName()
745 << " -> " << Callee.getName() << "\n");
746 setInlineRemark(*CB, "recursive");
747 continue;
748 }
749
750 // Check if this inlining may repeat breaking an SCC apart that has
751 // already been split once before. In that case, inlining here may
752 // trigger infinite inlining, much like is prevented within the inliner
753 // itself by the InlineHistory above, but spread across CGSCC iterations
754 // and thus hidden from the full inline history.
755 LazyCallGraph::SCC *CalleeSCC = CG.lookupSCC(*CG.lookup(Callee));
756 if (CalleeSCC == C && UR.InlinedInternalEdges.count({&N, C})) {
757 LLVM_DEBUG(dbgs() << "Skipping inlining internal SCC edge from a node "
758 "previously split out of this SCC by inlining: "
759 << F.getName() << " -> " << Callee.getName() << "\n");
760 setInlineRemark(*CB, "recursive SCC split");
761 continue;
762 }
763
764 std::unique_ptr<InlineAdvice> Advice =
765 Advisor.getAdvice(*CB, OnlyMandatory);
766
767 // Check whether we want to inline this callsite.
768 if (!Advice)
769 continue;
770
771 if (!Advice->isInliningRecommended()) {
772 Advice->recordUnattemptedInlining();
773 continue;
774 }
775
776 int CBCostMult =
779 .value_or(1);
780
781 // Setup the data structure used to plumb customization into the
782 // `InlineFunction` routine.
784 /*cg=*/nullptr, GetAssumptionCache, PSI,
787
789 InlineFunction(*CB, IFI, /*MergeAttributes=*/true,
790 &FAM.getResult<AAManager>(*CB->getCaller()));
791 if (!IR.isSuccess()) {
792 Advice->recordUnsuccessfulInlining(IR);
793 continue;
794 }
795
796 DidInline = true;
797 InlinedCallees.insert(&Callee);
798 ++NumInlined;
799
800 LLVM_DEBUG(dbgs() << " Size after inlining: "
801 << F.getInstructionCount() << "\n");
802
803 // Add any new callsites to defined functions to the worklist.
804 if (!IFI.InlinedCallSites.empty()) {
805 int NewHistoryID = InlineHistory.size();
806 InlineHistory.push_back({&Callee, InlineHistoryID});
807
808 for (CallBase *ICB : reverse(IFI.InlinedCallSites)) {
809 Function *NewCallee = ICB->getCalledFunction();
810 assert(!(NewCallee && NewCallee->isIntrinsic()) &&
811 "Intrinsic calls should not be tracked.");
812 if (!NewCallee) {
813 // Try to promote an indirect (virtual) call without waiting for
814 // the post-inline cleanup and the next DevirtSCCRepeatedPass
815 // iteration because the next iteration may not happen and we may
816 // miss inlining it.
817 if (tryPromoteCall(*ICB))
818 NewCallee = ICB->getCalledFunction();
819 }
820 if (NewCallee) {
821 if (!NewCallee->isDeclaration()) {
822 Calls.push_back({ICB, NewHistoryID});
823 // Continually inlining through an SCC can result in huge compile
824 // times and bloated code since we arbitrarily stop at some point
825 // when the inliner decides it's not profitable to inline anymore.
826 // We attempt to mitigate this by making these calls exponentially
827 // more expensive.
828 // This doesn't apply to calls in the same SCC since if we do
829 // inline through the SCC the function will end up being
830 // self-recursive which the inliner bails out on, and inlining
831 // within an SCC is necessary for performance.
832 if (CalleeSCC != C &&
833 CalleeSCC == CG.lookupSCC(CG.get(*NewCallee))) {
834 Attribute NewCBCostMult = Attribute::get(
835 M.getContext(),
837 itostr(CBCostMult * IntraSCCCostMultiplier));
838 ICB->addFnAttr(NewCBCostMult);
839 }
840 }
841 }
842 }
843 }
844
845 // For local functions or discardable functions without comdats, check
846 // whether this makes the callee trivially dead. In that case, we can drop
847 // the body of the function eagerly which may reduce the number of callers
848 // of other functions to one, changing inline cost thresholds. Non-local
849 // discardable functions with comdats are checked later on.
850 bool CalleeWasDeleted = false;
851 if (Callee.isDiscardableIfUnused() && Callee.hasZeroLiveUses() &&
852 !CG.isLibFunction(Callee)) {
853 if (Callee.hasLocalLinkage() || !Callee.hasComdat()) {
854 Calls.erase(
855 std::remove_if(Calls.begin() + I + 1, Calls.end(),
856 [&](const std::pair<CallBase *, int> &Call) {
857 return Call.first->getCaller() == &Callee;
858 }),
859 Calls.end());
860
861 // Clear the body and queue the function itself for deletion when we
862 // finish inlining and call graph updates.
863 // Note that after this point, it is an error to do anything other
864 // than use the callee's address or delete it.
865 Callee.dropAllReferences();
866 assert(!is_contained(DeadFunctions, &Callee) &&
867 "Cannot put cause a function to become dead twice!");
868 DeadFunctions.push_back(&Callee);
869 CalleeWasDeleted = true;
870 } else {
871 DeadFunctionsInComdats.push_back(&Callee);
872 }
873 }
874 if (CalleeWasDeleted)
875 Advice->recordInliningWithCalleeDeleted();
876 else
877 Advice->recordInlining();
878 }
879
880 // Back the call index up by one to put us in a good position to go around
881 // the outer loop.
882 --I;
883
884 if (!DidInline)
885 continue;
886 Changed = true;
887
888 // At this point, since we have made changes we have at least removed
889 // a call instruction. However, in the process we do some incremental
890 // simplification of the surrounding code. This simplification can
891 // essentially do all of the same things as a function pass and we can
892 // re-use the exact same logic for updating the call graph to reflect the
893 // change.
894
895 // Inside the update, we also update the FunctionAnalysisManager in the
896 // proxy for this particular SCC. We do this as the SCC may have changed and
897 // as we're going to mutate this particular function we want to make sure
898 // the proxy is in place to forward any invalidation events.
899 LazyCallGraph::SCC *OldC = C;
901 LLVM_DEBUG(dbgs() << "Updated inlining SCC: " << *C << "\n");
902
903 // If this causes an SCC to split apart into multiple smaller SCCs, there
904 // is a subtle risk we need to prepare for. Other transformations may
905 // expose an "infinite inlining" opportunity later, and because of the SCC
906 // mutation, we will revisit this function and potentially re-inline. If we
907 // do, and that re-inlining also has the potentially to mutate the SCC
908 // structure, the infinite inlining problem can manifest through infinite
909 // SCC splits and merges. To avoid this, we capture the originating caller
910 // node and the SCC containing the call edge. This is a slight over
911 // approximation of the possible inlining decisions that must be avoided,
912 // but is relatively efficient to store. We use C != OldC to know when
913 // a new SCC is generated and the original SCC may be generated via merge
914 // in later iterations.
915 //
916 // It is also possible that even if no new SCC is generated
917 // (i.e., C == OldC), the original SCC could be split and then merged
918 // into the same one as itself. and the original SCC will be added into
919 // UR.CWorklist again, we want to catch such cases too.
920 //
921 // FIXME: This seems like a very heavyweight way of retaining the inline
922 // history, we should look for a more efficient way of tracking it.
923 if ((C != OldC || UR.CWorklist.count(OldC)) &&
924 llvm::any_of(InlinedCallees, [&](Function *Callee) {
925 return CG.lookupSCC(*CG.lookup(*Callee)) == OldC;
926 })) {
927 LLVM_DEBUG(dbgs() << "Inlined an internal call edge and split an SCC, "
928 "retaining this to avoid infinite inlining.\n");
929 UR.InlinedInternalEdges.insert({&N, OldC});
930 }
931 InlinedCallees.clear();
932
933 // Invalidate analyses for this function now so that we don't have to
934 // invalidate analyses for all functions in this SCC later.
936 }
937
938 // We must ensure that we only delete functions with comdats if every function
939 // in the comdat is going to be deleted.
940 if (!DeadFunctionsInComdats.empty()) {
941 filterDeadComdatFunctions(DeadFunctionsInComdats);
942 for (auto *Callee : DeadFunctionsInComdats)
943 Callee->dropAllReferences();
944 DeadFunctions.append(DeadFunctionsInComdats);
945 }
946
947 // Now that we've finished inlining all of the calls across this SCC, delete
948 // all of the trivially dead functions, updating the call graph and the CGSCC
949 // pass manager in the process.
950 //
951 // Note that this walks a pointer set which has non-deterministic order but
952 // that is OK as all we do is delete things and add pointers to unordered
953 // sets.
954 for (Function *DeadF : DeadFunctions) {
955 // Get the necessary information out of the call graph and nuke the
956 // function there. Also, clear out any cached analyses.
957 auto &DeadC = *CG.lookupSCC(*CG.lookup(*DeadF));
958 FAM.clear(*DeadF, DeadF->getName());
959 AM.clear(DeadC, DeadC.getName());
960 auto &DeadRC = DeadC.getOuterRefSCC();
961 CG.removeDeadFunction(*DeadF);
962
963 // Mark the relevant parts of the call graph as invalid so we don't visit
964 // them.
965 UR.InvalidatedSCCs.insert(&DeadC);
966 UR.InvalidatedRefSCCs.insert(&DeadRC);
967
968 // If the updated SCC was the one containing the deleted function, clear it.
969 if (&DeadC == UR.UpdatedC)
970 UR.UpdatedC = nullptr;
971
972 // And delete the actual function from the module.
973 M.getFunctionList().erase(DeadF);
974
975 ++NumDeleted;
976 }
977
978 if (!Changed)
979 return PreservedAnalyses::all();
980
982 // Even if we change the IR, we update the core CGSCC data structures and so
983 // can preserve the proxy to the function analysis manager.
985 // We have already invalidated all analyses on modified functions.
987 return PA;
988}
989
991 bool MandatoryFirst,
992 InlineContext IC,
994 unsigned MaxDevirtIterations)
995 : Params(Params), IC(IC), Mode(Mode),
997 // Run the inliner first. The theory is that we are walking bottom-up and so
998 // the callees have already been fully optimized, and we want to inline them
999 // into the callers so that our optimizations can reflect that.
1000 // For PreLinkThinLTO pass, we disable hot-caller heuristic for sample PGO
1001 // because it makes profile annotation in the backend inaccurate.
1002 if (MandatoryFirst) {
1003 PM.addPass(InlinerPass(/*OnlyMandatory*/ true));
1006 }
1007 PM.addPass(InlinerPass());
1010}
1011
1014 auto &IAA = MAM.getResult<InlineAdvisorAnalysis>(M);
1015 if (!IAA.tryCreate(Params, Mode,
1016 {CGSCCInlineReplayFile,
1017 CGSCCInlineReplayScope,
1018 CGSCCInlineReplayFallback,
1019 {CGSCCInlineReplayFormat}},
1020 IC)) {
1021 M.getContext().emitError(
1022 "Could not setup Inlining Advisor for the requested "
1023 "mode and/or options");
1024 return PreservedAnalyses::all();
1025 }
1026
1027 // We wrap the CGSCC pipeline in a devirtualization repeater. This will try
1028 // to detect when we devirtualize indirect calls and iterate the SCC passes
1029 // in that case to try and catch knock-on inlining or function attrs
1030 // opportunities. Then we add it to the module pipeline by walking the SCCs
1031 // in postorder (or bottom-up).
1032 // If MaxDevirtIterations is 0, we just don't use the devirtualization
1033 // wrapper.
1034 if (MaxDevirtIterations == 0)
1036 else
1039
1040 MPM.addPass(std::move(AfterCGMPM));
1041 MPM.run(M, MAM);
1042
1043 // Discard the InlineAdvisor, a subsequent inlining session should construct
1044 // its own.
1045 auto PA = PreservedAnalyses::all();
1047 PA.abandon<InlineAdvisorAnalysis>();
1048 return PA;
1049}
1050
1052 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
1053 static_cast<PassInfoMixin<InlinerPass> *>(this)->printPipeline(
1054 OS, MapClassName2PassName);
1055 if (OnlyMandatory)
1056 OS << "<only-mandatory>";
1057}
1058
1060 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
1061 // Print some info about passes added to the wrapper. This is however
1062 // incomplete as InlineAdvisorAnalysis part isn't included (which also depends
1063 // on Params and Mode).
1064 if (!MPM.isEmpty()) {
1065 MPM.printPipeline(OS, MapClassName2PassName);
1066 OS << ',';
1067 }
1068 OS << "cgscc(";
1069 if (MaxDevirtIterations != 0)
1070 OS << "devirt<" << MaxDevirtIterations << ">(";
1071 PM.printPipeline(OS, MapClassName2PassName);
1072 if (MaxDevirtIterations != 0)
1073 OS << ')';
1074 OS << ')';
1075}
amdgpu Simplify well known AMD library false FunctionCallee Callee
This file contains the simple types necessary to represent the attributes associated with functions a...
This is the interface for LLVM's primary stateless and local alias analysis.
This header provides classes for managing passes over SCCs of the call graph.
This file provides interfaces used to build and manipulate a call graph, which is a very useful tool ...
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
Definition: CommandLine.h:678
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
@ InlineInfo
#define DEBUG_TYPE
static bool inlineCallsImpl(CallGraphSCC &SCC, CallGraph &CG, std::function< AssumptionCache &(Function &)> GetAssumptionCache, ProfileSummaryInfo *PSI, std::function< const TargetLibraryInfo &(Function &)> GetTLI, bool InsertLifetime, function_ref< InlineCost(CallBase &CB)> GetInlineCost, function_ref< AAResults &(Function &)> AARGetter, ImportedFunctionsInliningStatistics &ImportedFunctionsStats)
Definition: Inliner.cpp:232
static bool inlineHistoryIncludes(Function *F, int InlineHistoryID, const SmallVectorImpl< std::pair< Function *, int > > &InlineHistory)
Return true if the specified inline history ID indicates an inline history that includes the specifie...
Definition: Inliner.cpp:206
static cl::opt< ReplayInlinerSettings::Scope > CGSCCInlineReplayScope("cgscc-inline-replay-scope", cl::init(ReplayInlinerSettings::Scope::Function), cl::values(clEnumValN(ReplayInlinerSettings::Scope::Function, "Function", "Replay on functions that have remarks associated " "with them (default)"), clEnumValN(ReplayInlinerSettings::Scope::Module, "Module", "Replay on the entire module")), cl::desc("Whether inline replay should be applied to the entire " "Module or just the Functions (default) that are present as " "callers in remarks during cgscc inlining."), cl::Hidden)
static cl::opt< bool > KeepAdvisorForPrinting("keep-inline-advisor-for-printing", cl::init(false), cl::Hidden)
A flag for test, so we can print the content of the advisor when running it as part of the default (e...
static InlineResult inlineCallIfPossible(CallBase &CB, InlineFunctionInfo &IFI, InlinedArrayAllocasTy &InlinedArrayAllocas, int InlineHistory, bool InsertLifetime, function_ref< AAResults &(Function &)> &AARGetter, ImportedFunctionsInliningStatistics &ImportedFunctionsStats)
If it is possible to inline the specified call site, do so and update the CallGraph for this operatio...
Definition: Inliner.cpp:180
static cl::opt< std::string > CGSCCInlineReplayFile("cgscc-inline-replay", cl::init(""), cl::value_desc("filename"), cl::desc("Optimization remarks file containing inline remarks to be replayed " "by cgscc inlining."), cl::Hidden)
static cl::opt< bool > EnablePostSCCAdvisorPrinting("enable-scc-inline-advisor-printing", cl::init(false), cl::Hidden)
Allows printing the contents of the advisor after each SCC inliner pass.
static cl::opt< int > IntraSCCCostMultiplier("intra-scc-cost-multiplier", cl::init(2), cl::Hidden, cl::desc("Cost multiplier to multiply onto inlined call sites where the " "new call was previously an intra-SCC call (not relevant when the " "original call was already intra-SCC). This can accumulate over " "multiple inlinings (e.g. if a call site already had a cost " "multiplier and one of its inlined calls was also subject to " "this, the inlined call would have the original multiplier " "multiplied by intra-scc-cost-multiplier). This is to prevent tons of " "inlining through a child SCC which can cause terrible compile times"))
static cl::opt< CallSiteFormat::Format > CGSCCInlineReplayFormat("cgscc-inline-replay-format", cl::init(CallSiteFormat::Format::LineColumnDiscriminator), cl::values(clEnumValN(CallSiteFormat::Format::Line, "Line", "<Line Number>"), clEnumValN(CallSiteFormat::Format::LineColumn, "LineColumn", "<Line Number>:<Column Number>"), clEnumValN(CallSiteFormat::Format::LineDiscriminator, "LineDiscriminator", "<Line Number>.<Discriminator>"), clEnumValN(CallSiteFormat::Format::LineColumnDiscriminator, "LineColumnDiscriminator", "<Line Number>:<Column Number>.<Discriminator> (default)")), cl::desc("How cgscc inline replay file is formatted"), cl::Hidden)
static cl::opt< ReplayInlinerSettings::Fallback > CGSCCInlineReplayFallback("cgscc-inline-replay-fallback", cl::init(ReplayInlinerSettings::Fallback::Original), cl::values(clEnumValN(ReplayInlinerSettings::Fallback::Original, "Original", "All decisions not in replay send to original advisor (default)"), clEnumValN(ReplayInlinerSettings::Fallback::AlwaysInline, "AlwaysInline", "All decisions not in replay are inlined"), clEnumValN(ReplayInlinerSettings::Fallback::NeverInline, "NeverInline", "All decisions not in replay are not inlined")), cl::desc("How cgscc inline replay treats sites that don't come from the replay. " "Original: defers to original advisor, AlwaysInline: inline all sites " "not in replay, NeverInline: inline no sites not in replay"), cl::Hidden)
Implements a lazy call graph analysis and related passes for the new pass manager.
Statically lint checks LLVM IR
Definition: Lint.cpp:746
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This file contains the declarations for metadata subclasses.
Module.h This file contains the declarations for the Module class.
print must be executed print the must be executed context for all instructions
#define P(N)
ModulePassManager MPM
FunctionAnalysisManager FAM
ModuleAnalysisManager MAM
This header defines various interfaces for pass management in LLVM.
This file provides a priority worklist.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
raw_pwrite_stream & OS
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
This file contains some functions that are useful when dealing with strings.
A manager for alias analyses.
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: PassManager.h:90
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
void clear(IRUnitT &IR, llvm::StringRef Name)
Clear any cached analysis results for a single unit of IR.
void invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Invalidate cached analyses for an IR unit.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:793
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
AssumptionCache & getAssumptionCache(Function &F)
Get the cached assumptions for a function.
A cache of @llvm.assume calls within a function.
static Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
Definition: Attributes.cpp:91
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
Analysis pass which computes BlockFrequencyInfo.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1186
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1408
Function * getCaller()
Helper to get the caller (the parent function).
A node in the call graph for a module.
Definition: CallGraph.h:166
Function * getFunction() const
Returns the function that this call graph node represents.
Definition: CallGraph.h:197
void removeAllCalledFunctions()
Removes all edges from this CallGraphNode to any functions it calls.
Definition: CallGraph.h:227
void removeAnyCallEdgeTo(CallGraphNode *Callee)
Removes all call edges from this node to the specified callee function.
Definition: CallGraph.cpp:229
void getAnalysisUsage(AnalysisUsage &Info) const override
getAnalysisUsage - For this class, we declare that we require and preserve the call graph.
bool skipSCC(CallGraphSCC &SCC) const
Optional passes call this function to check whether the pass should be skipped.
CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on.
The basic data container for the call graph of a Module of IR.
Definition: CallGraph.h:72
Function * removeFunctionFromModule(CallGraphNode *CGN)
Unlink the function from this module, returning it.
Definition: CallGraph.cpp:157
Module & getModule() const
Returns the module the call graph corresponds to.
Definition: CallGraph.h:101
CallGraphNode * getExternalCallingNode() const
Returns the CallGraphNode which is used to represent undetermined calls into the callgraph.
Definition: CallGraph.h:127
A debug info location.
Definition: DebugLoc.h:33
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
A proxy from a FunctionAnalysisManager to an SCC.
bool isIntrinsic() const
isIntrinsic - Returns true if the function's name starts with "llvm.".
Definition: Function.h:209
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:275
Calculate and dump ThinLTO specific inliner stats.
void setModuleInfo(const Module &M)
Set information like AllFunctions, ImportedFunctions, ModuleName.
void dump(bool Verbose)
Dump stats computed with InlinerStatistics class.
void recordInline(const Function &Caller, const Function &Callee)
Record inline of.
Printer pass for the FunctionPropertiesAnalysis results.
The InlineAdvisorAnalysis is a module pass because the InlineAdvisor needs to capture state right bef...
Interface for deciding whether to inline a call site or not.
virtual void onPassEntry(LazyCallGraph::SCC *SCC=nullptr)
This must be called when the Inliner pass is entered, to allow the InlineAdvisor update internal stat...
virtual void onPassExit(LazyCallGraph::SCC *SCC=nullptr)
This must be called when the Inliner pass is exited, as function passes may be run subsequently.
Represents the cost of inlining a function.
Definition: InlineCost.h:89
This class captures the data input to the InlineFunction call, and records the auxiliary results prod...
Definition: Cloning.h:203
SmallVector< CallBase *, 8 > InlinedCallSites
All of the new call sites inlined into the caller.
Definition: Cloning.h:235
InlineResult is basically true or false.
Definition: InlineCost.h:179
The inliner pass for the new pass manager.
Definition: Inliner.h:96
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: Inliner.cpp:1051
PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG, CGSCCUpdateResult &UR)
Definition: Inliner.cpp:613
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:358
const BasicBlock * getParent() const
Definition: Instruction.h:90
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:82
A node in the call graph.
An SCC of the call graph.
iterator begin() const
A lazily constructed view of the call graph of a module.
This class is a functor to be used in legacy module or SCC passes for computing AA results for a func...
PreservedAnalyses run(Module &, ModuleAnalysisManager &)
Definition: Inliner.cpp:1012
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: Inliner.cpp:1059
ModuleInlinerWrapperPass(InlineParams Params=getInlineParams(), bool MandatoryFirst=true, InlineContext IC={}, InliningAdvisorMode Mode=InliningAdvisorMode::Default, unsigned MaxDevirtIterations=0)
Definition: Inliner.cpp:990
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
The optimization diagnostic interface.
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file.
Diagnostic information for missed-optimization remarks.
Result proxy object for OuterAnalysisManagerProxy.
Definition: PassManager.h:1061
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1058
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: PassManager.h:486
LLVM_ATTRIBUTE_MINSIZE std::enable_if_t<!std::is_same< PassT, PassManager >::value > addPass(PassT &&Pass)
Definition: PassManager.h:544
PreservedAnalyses run(IRUnitT &IR, AnalysisManagerT &AM, ExtraArgTs... ExtraArgs)
Run all of the passes in this manager over the given unit of IR.
Definition: PassManager.h:498
bool isEmpty() const
Returns if the pass manager contains any passes.
Definition: PassManager.h:568
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:155
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
Analysis providing profile information.
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
void clear()
Completely clear the SetVector.
Definition: SetVector.h:213
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:301
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
iterator erase(const_iterator CI)
Definition: SmallVector.h:741
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:687
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
Provides information about what library functions are available for the current target.
LLVM Value Representation.
Definition: Value.h:74
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
An efficient, type-erasing, non-owning reference to a callable.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
const char FunctionInlineCostMultiplierAttributeName[]
Definition: InlineCost.h:59
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:703
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
Definition: ScopeExit.h:59
std::string inlineCostStr(const InlineCost &IC)
Utility for extracting the inline cost message to a string.
InliningAdvisorMode
There are 4 scenarios we can use the InlineAdvisor:
Definition: InlineAdvisor.h:44
std::optional< int > getStringFnAttrAsInt(CallBase &CB, StringRef AttrKind)
Definition: InlineCost.cpp:175
DevirtSCCRepeatedPass createDevirtSCCRepeatedPass(CGSCCPassT &&Pass, int MaxIterations)
A function to deduce a function pass type and wrap it in the templated adaptor.
LazyCallGraph::SCC & updateCGAndAnalysisManagerForCGSCCPass(LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N, CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR, FunctionAnalysisManager &FAM)
Helper to update the call graph after running a CGSCC pass.
void setInlineRemark(CallBase &CB, StringRef Message)
Set the inline-remark attribute.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1789
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
Definition: Local.cpp:398
ModuleToPostOrderCGSCCPassAdaptor createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT &&Pass)
A function to deduce a function pass type and wrap it in the templated adaptor.
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:495
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void emitInlinedIntoBasedOnCost(OptimizationRemarkEmitter &ORE, DebugLoc DLoc, const BasicBlock *Block, const Function &Callee, const Function &Caller, const InlineCost &IC, bool ForProfileContext=false, const char *PassName=nullptr)
Emit ORE message based in cost (default heuristic).
std::unique_ptr< InlineAdvisor > getReplayInlineAdvisor(Module &M, FunctionAnalysisManager &FAM, LLVMContext &Context, std::unique_ptr< InlineAdvisor > OriginalAdvisor, const ReplayInlinerSettings &ReplaySettings, bool EmitRemarks, InlineContext IC)
cl::opt< InlinerFunctionImportStatsOpts > InlinerFunctionImportStats("inliner-function-import-stats", cl::init(InlinerFunctionImportStatsOpts::No), cl::values(clEnumValN(InlinerFunctionImportStatsOpts::Basic, "basic", "basic statistics"), clEnumValN(InlinerFunctionImportStatsOpts::Verbose, "verbose", "printing of statistics for each inlined function")), cl::Hidden, cl::desc("Enable inliner stats for imported functions"))
std::optional< InlineCost > shouldInline(CallBase &CB, function_ref< InlineCost(CallBase &CB)> GetInlineCost, OptimizationRemarkEmitter &ORE, bool EnableDeferral=true)
Return the cost only if the inliner should attempt to inline at the given CallSite.
InlineResult InlineFunction(CallBase &CB, InlineFunctionInfo &IFI, bool MergeAttributes=false, AAResults *CalleeAAR=nullptr, bool InsertLifetime=true, Function *ForwardVarArgsTo=nullptr)
This function inlines the called function into the basic block of the caller.
InlineParams getInlineParams()
Generate the parameters to tune the inline cost analysis based only on the commandline options.
void getAAResultsAnalysisUsage(AnalysisUsage &AU)
A helper for the legacy pass manager to populate AU to add uses to make sure the analyses required by...
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1939
void filterDeadComdatFunctions(SmallVectorImpl< Function * > &DeadComdatFunctions)
Filter out potentially dead comdat functions where other entries keep the entire comdat group alive.
bool tryPromoteCall(CallBase &CB)
Try to promote (devirtualize) a virtual call on an Alloca.
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
Definition: STLExtras.h:1690
cl::opt< unsigned > MaxDevirtIterations("max-devirt-iterations", cl::ReallyHidden, cl::init(4))
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
#define N
Support structure for SCC passes to communicate updates the call graph back to the CGSCC pass manager...
Provides context on when an inline advisor is constructed in the pipeline (e.g., link phase,...
Definition: InlineAdvisor.h:60
Thresholds to tune inline cost analysis.
Definition: InlineCost.h:205
bool removeDeadFunctions(CallGraph &CG, bool AlwaysInlineOnly=false)
Remove dead functions.
Definition: Inliner.cpp:494
ProfileSummaryInfo * PSI
Definition: Inliner.h:77
ImportedFunctionsInliningStatistics ImportedFunctionsStats
Definition: Inliner.h:79
std::function< const TargetLibraryInfo &(Function &)> GetTLI
Definition: Inliner.h:78
AssumptionCacheTracker * ACT
Definition: Inliner.h:76
LegacyInlinerBase(char &ID)
Definition: Inliner.cpp:154
virtual InlineCost getInlineCost(CallBase &CB)=0
This method must be implemented by the subclass to determine the cost of inlining the specified call ...
bool doFinalization(CallGraph &CG) override
Remove now-dead linkonce functions at the end of processing to avoid breaking the SCC traversal.
Definition: Inliner.cpp:486
bool inlineCalls(CallGraphSCC &SCC)
This function performs the main work of the pass.
Definition: Inliner.cpp:468
bool doInitialization(CallGraph &CG) override
doInitialization - This method is called before the SCC's of the program has been processed,...
Definition: Inliner.cpp:219
void getAnalysisUsage(AnalysisUsage &Info) const override
For this class, we declare that we require and preserve the call graph.
Definition: Inliner.cpp:162
bool runOnSCC(CallGraphSCC &SCC) override
Main run interface method, this implements the interface required by the Pass class.
Definition: Inliner.cpp:225
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371