blob: 5bcfc38c585b2e0bffdca9927b4ff72956ce8e97 [file] [log] [blame]
//===- Inliner.cpp - Code common to all inliners --------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements the mechanics required to implement inlining without
// missing any calls and updating the call graph. The decisions of which calls
// are profitable to inline are implemented elsewhere.
//
//===----------------------------------------------------------------------===//
#include "llvm/Transforms/IPO/Inliner.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PriorityWorklist.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopeExit.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/BasicAliasAnalysis.h"
#include "llvm/Analysis/BlockFrequencyInfo.h"
#include "llvm/Analysis/CGSCCPassManager.h"
#include "llvm/Analysis/CallGraph.h"
#include "llvm/Analysis/InlineAdvisor.h"
#include "llvm/Analysis/InlineCost.h"
#include "llvm/Analysis/LazyCallGraph.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ProfileSummaryInfo.h"
#include "llvm/Analysis/ReplayInlineAdvisor.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/Utils/ImportedFunctionsInliningStatistics.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/DiagnosticInfo.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/CallPromotionUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/ModuleUtils.h"
#include <algorithm>
#include <cassert>
#include <functional>
#include <utility>
#include <vector>
using namespace llvm;
#define DEBUG_TYPE "inline"
STATISTIC(NumInlined, "Number of functions inlined");
STATISTIC(NumCallsDeleted, "Number of call sites deleted, not inlined");
STATISTIC(NumDeleted, "Number of functions deleted because all callers found");
STATISTIC(NumMergedAllocas, "Number of allocas merged together");
/// Flag to disable manual alloca merging.
///
/// Merging of allocas was originally done as a stack-size saving technique
/// prior to LLVM's code generator having support for stack coloring based on
/// lifetime markers. It is now in the process of being removed. To experiment
/// with disabling it and relying fully on lifetime marker based stack
/// coloring, you can pass this flag to LLVM.
static cl::opt<bool>
DisableInlinedAllocaMerging("disable-inlined-alloca-merging",
cl::init(false), cl::Hidden);
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"));
/// A flag for test, so we can print the content of the advisor when running it
/// as part of the default (e.g. -O3) pipeline.
static cl::opt<bool> KeepAdvisorForPrinting("keep-inline-advisor-for-printing",
cl::init(false), cl::Hidden);
/// Allows printing the contents of the advisor after each SCC inliner pass.
static cl::opt<bool>
EnablePostSCCAdvisorPrinting("enable-scc-inline-advisor-printing",
cl::init(false), cl::Hidden);
namespace llvm {
extern cl::opt<InlinerFunctionImportStatsOpts> InlinerFunctionImportStats;
}
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<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<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);
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);
LegacyInlinerBase::LegacyInlinerBase(char &ID) : CallGraphSCCPass(ID) {}
LegacyInlinerBase::LegacyInlinerBase(char &ID, bool InsertLifetime)
: CallGraphSCCPass(ID), InsertLifetime(InsertLifetime) {}
/// For this class, we declare that we require and preserve the call graph.
/// If the derived class implements this method, it should
/// always explicitly call the implementation here.
void LegacyInlinerBase::getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<AssumptionCacheTracker>();
AU.addRequired<ProfileSummaryInfoWrapperPass>();
AU.addRequired<TargetLibraryInfoWrapperPass>();
getAAResultsAnalysisUsage(AU);
CallGraphSCCPass::getAnalysisUsage(AU);
}
using InlinedArrayAllocasTy = DenseMap<ArrayType *, std::vector<AllocaInst *>>;
/// Look at all of the allocas that we inlined through this call site. If we
/// have already inlined other allocas through other calls into this function,
/// then we know that they have disjoint lifetimes and that we can merge them.
///
/// There are many heuristics possible for merging these allocas, and the
/// different options have different tradeoffs. One thing that we *really*
/// don't want to hurt is SRoA: once inlining happens, often allocas are no
/// longer address taken and so they can be promoted.
///
/// Our "solution" for that is to only merge allocas whose outermost type is an
/// array type. These are usually not promoted because someone is using a
/// variable index into them. These are also often the most important ones to
/// merge.
///
/// A better solution would be to have real memory lifetime markers in the IR
/// and not have the inliner do any merging of allocas at all. This would
/// allow the backend to do proper stack slot coloring of all allocas that
/// *actually make it to the backend*, which is really what we want.
///
/// Because we don't have this information, we do this simple and useful hack.
static void mergeInlinedArrayAllocas(Function *Caller, InlineFunctionInfo &IFI,
InlinedArrayAllocasTy &InlinedArrayAllocas,
int InlineHistory) {
SmallPtrSet<AllocaInst *, 16> UsedAllocas;
// When processing our SCC, check to see if the call site was inlined from
// some other call site. For example, if we're processing "A" in this code:
// A() { B() }
// B() { x = alloca ... C() }
// C() { y = alloca ... }
// Assume that C was not inlined into B initially, and so we're processing A
// and decide to inline B into A. Doing this makes an alloca available for
// reuse and makes a callsite (C) available for inlining. When we process
// the C call site we don't want to do any alloca merging between X and Y
// because their scopes are not disjoint. We could make this smarter by
// keeping track of the inline history for each alloca in the
// InlinedArrayAllocas but this isn't likely to be a significant win.
if (InlineHistory != -1) // Only do merging for top-level call sites in SCC.
return;
// Loop over all the allocas we have so far and see if they can be merged with
// a previously inlined alloca. If not, remember that we had it.
for (unsigned AllocaNo = 0, E = IFI.StaticAllocas.size(); AllocaNo != E;
++AllocaNo) {
AllocaInst *AI = IFI.StaticAllocas[AllocaNo];
// Don't bother trying to merge array allocations (they will usually be
// canonicalized to be an allocation *of* an array), or allocations whose
// type is not itself an array (because we're afraid of pessimizing SRoA).
ArrayType *ATy = dyn_cast<ArrayType>(AI->getAllocatedType());
if (!ATy || AI->isArrayAllocation())
continue;
// Get the list of all available allocas for this array type.
std::vector<AllocaInst *> &AllocasForType = InlinedArrayAllocas[ATy];
// Loop over the allocas in AllocasForType to see if we can reuse one. Note
// that we have to be careful not to reuse the same "available" alloca for
// multiple different allocas that we just inlined, we use the 'UsedAllocas'
// set to keep track of which "available" allocas are being used by this
// function. Also, AllocasForType can be empty of course!
bool MergedAwayAlloca = false;
for (AllocaInst *AvailableAlloca : AllocasForType) {
Align Align1 = AI->getAlign();
Align Align2 = AvailableAlloca->getAlign();
// The available alloca has to be in the right function, not in some other
// function in this SCC.
if (AvailableAlloca->getParent() != AI->getParent())
continue;
// If the inlined function already uses this alloca then we can't reuse
// it.
if (!UsedAllocas.insert(AvailableAlloca).second)
continue;
// Otherwise, we *can* reuse it, RAUW AI into AvailableAlloca and declare
// success!
LLVM_DEBUG(dbgs() << " ***MERGED ALLOCA: " << *AI
<< "\n\t\tINTO: " << *AvailableAlloca << '\n');
// Move affected dbg.declare calls immediately after the new alloca to
// avoid the situation when a dbg.declare precedes its alloca.
if (auto *L = LocalAsMetadata::getIfExists(AI))
if (auto *MDV = MetadataAsValue::getIfExists(AI->getContext(), L))
for (User *U : MDV->users())
if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(U))
DDI->moveBefore(AvailableAlloca->getNextNode());
AI->replaceAllUsesWith(AvailableAlloca);
if (Align1 > Align2)
AvailableAlloca->setAlignment(AI->getAlign());
AI->eraseFromParent();
MergedAwayAlloca = true;
++NumMergedAllocas;
IFI.StaticAllocas[AllocaNo] = nullptr;
break;
}
// If we already nuked the alloca, we're done with it.
if (MergedAwayAlloca)
continue;
// If we were unable to merge away the alloca either because there are no
// allocas of the right type available or because we reused them all
// already, remember that this alloca came from an inlined function and mark
// it used so we don't reuse it for other allocas from this inline
// operation.
AllocasForType.push_back(AI);
UsedAllocas.insert(AI);
}
}
/// If it is possible to inline the specified call site,
/// do so and update the CallGraph for this operation.
///
/// This function also does some basic book-keeping to update the IR. The
/// InlinedArrayAllocas map keeps track of any allocas that are already
/// available from other functions inlined into the caller. If we are able to
/// inline this call site we attempt to reuse already available allocas or add
/// any new allocas to the set if not possible.
static InlineResult inlineCallIfPossible(
CallBase &CB, InlineFunctionInfo &IFI,
InlinedArrayAllocasTy &InlinedArrayAllocas, int InlineHistory,
bool InsertLifetime, function_ref<AAResults &(Function &)> &AARGetter,
ImportedFunctionsInliningStatistics &ImportedFunctionsStats) {
Function *Callee = CB.getCalledFunction();
Function *Caller = CB.getCaller();
AAResults &AAR = AARGetter(*Callee);
// Try to inline the function. Get the list of static allocas that were
// inlined.
InlineResult IR =
InlineFunction(CB, IFI,
/*MergeAttributes=*/true, &AAR, InsertLifetime);
if (!IR.isSuccess())
return IR;
if (InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No)
ImportedFunctionsStats.recordInline(*Caller, *Callee);
if (!DisableInlinedAllocaMerging)
mergeInlinedArrayAllocas(Caller, IFI, InlinedArrayAllocas, InlineHistory);
return IR; // success
}
/// Return true if the specified inline history ID
/// indicates an inline history that includes the specified function.
static bool inlineHistoryIncludes(
Function *F, int InlineHistoryID,
const SmallVectorImpl<std::pair<Function *, int>> &InlineHistory) {
while (InlineHistoryID != -1) {
assert(unsigned(InlineHistoryID) < InlineHistory.size() &&
"Invalid inline history ID");
if (InlineHistory[InlineHistoryID].first == F)
return true;
InlineHistoryID = InlineHistory[InlineHistoryID].second;
}
return false;
}
bool LegacyInlinerBase::doInitialization(CallGraph &CG) {
if (InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No)
ImportedFunctionsStats.setModuleInfo(CG.getModule());
return false; // No changes to CallGraph.
}
bool LegacyInlinerBase::runOnSCC(CallGraphSCC &SCC) {
if (skipSCC(SCC))
return false;
return inlineCalls(SCC);
}
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) {
SmallPtrSet<Function *, 8> SCCFunctions;
LLVM_DEBUG(dbgs() << "Inliner visiting SCC:");
for (CallGraphNode *Node : SCC) {
Function *F = Node->getFunction();
if (F)
SCCFunctions.insert(F);
LLVM_DEBUG(dbgs() << " " << (F ? F->getName() : "INDIRECTNODE"));
}
// Scan through and identify all call sites ahead of time so that we only
// inline call sites in the original functions, not call sites that result
// from inlining other functions.
SmallVector<std::pair<CallBase *, int>, 16> CallSites;
// When inlining a callee produces new call sites, we want to keep track of
// the fact that they were inlined from the callee. This allows us to avoid
// infinite inlining in some obscure cases. To represent this, we use an
// index into the InlineHistory vector.
SmallVector<std::pair<Function *, int>, 8> InlineHistory;
for (CallGraphNode *Node : SCC) {
Function *F = Node->getFunction();
if (!F || F->isDeclaration())
continue;
OptimizationRemarkEmitter ORE(F);
for (BasicBlock &BB : *F)
for (Instruction &I : BB) {
auto *CB = dyn_cast<CallBase>(&I);
// If this isn't a call, or it is a call to an intrinsic, it can
// never be inlined.
if (!CB || isa<IntrinsicInst>(I))
continue;
// If this is a direct call to an external function, we can never inline
// it. If it is an indirect call, inlining may resolve it to be a
// direct call, so we keep it.
if (Function *Callee = CB->getCalledFunction())
if (Callee->isDeclaration()) {
using namespace ore;
setInlineRemark(*CB, "unavailable definition");
ORE.emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "NoDefinition", &I)
<< NV("Callee", Callee) << " will not be inlined into "
<< NV("Caller", CB->getCaller())
<< " because its definition is unavailable"
<< setIsVerbose();
});
continue;
}
CallSites.push_back(std::make_pair(CB, -1));
}
}
LLVM_DEBUG(dbgs() << ": " << CallSites.size() << " call sites.\n");
// If there are no calls in this function, exit early.
if (CallSites.empty())
return false;
// Now that we have all of the call sites, move the ones to functions in the
// current SCC to the end of the list.
unsigned FirstCallInSCC = CallSites.size();
for (unsigned I = 0; I < FirstCallInSCC; ++I)
if (Function *F = CallSites[I].first->getCalledFunction())
if (SCCFunctions.count(F))
std::swap(CallSites[I--], CallSites[--FirstCallInSCC]);
InlinedArrayAllocasTy InlinedArrayAllocas;
InlineFunctionInfo InlineInfo(&CG, GetAssumptionCache, PSI);
// Now that we have all of the call sites, loop over them and inline them if
// it looks profitable to do so.
bool Changed = false;
bool LocalChange;
do {
LocalChange = false;
// Iterate over the outer loop because inlining functions can cause indirect
// calls to become direct calls.
// CallSites may be modified inside so ranged for loop can not be used.
for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) {
auto &P = CallSites[CSi];
CallBase &CB = *P.first;
const int InlineHistoryID = P.second;
Function *Caller = CB.getCaller();
Function *Callee = CB.getCalledFunction();
// We can only inline direct calls to non-declarations.
if (!Callee || Callee->isDeclaration())
continue;
bool IsTriviallyDead = isInstructionTriviallyDead(&CB, &GetTLI(*Caller));
if (!IsTriviallyDead) {
// If this call site was obtained by inlining another function, verify
// that the include path for the function did not include the callee
// itself. If so, we'd be recursively inlining the same function,
// which would provide the same callsites, which would cause us to
// infinitely inline.
if (InlineHistoryID != -1 &&
inlineHistoryIncludes(Callee, InlineHistoryID, InlineHistory)) {
setInlineRemark(CB, "recursive");
continue;
}
}
// FIXME for new PM: because of the old PM we currently generate ORE and
// in turn BFI on demand. With the new PM, the ORE dependency should
// just become a regular analysis dependency.
OptimizationRemarkEmitter ORE(Caller);
auto OIC = shouldInline(CB, GetInlineCost, ORE);
// If the policy determines that we should inline this function,
// delete the call instead.
if (!OIC)
continue;
// If this call site is dead and it is to a readonly function, we should
// just delete the call instead of trying to inline it, regardless of
// size. This happens because IPSCCP propagates the result out of the
// call and then we're left with the dead call.
if (IsTriviallyDead) {
LLVM_DEBUG(dbgs() << " -> Deleting dead call: " << CB << "\n");
// Update the call graph by deleting the edge from Callee to Caller.
setInlineRemark(CB, "trivially dead");
CG[Caller]->removeCallEdgeFor(CB);
CB.eraseFromParent();
++NumCallsDeleted;
} else {
// Get DebugLoc to report. CB will be invalid after Inliner.
DebugLoc DLoc = CB.getDebugLoc();
BasicBlock *Block = CB.getParent();
// Attempt to inline the function.
using namespace ore;
InlineResult IR = inlineCallIfPossible(
CB, InlineInfo, InlinedArrayAllocas, InlineHistoryID,
InsertLifetime, AARGetter, ImportedFunctionsStats);
if (!IR.isSuccess()) {
setInlineRemark(CB, std::string(IR.getFailureReason()) + "; " +
inlineCostStr(*OIC));
ORE.emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "NotInlined", DLoc,
Block)
<< NV("Callee", Callee) << " will not be inlined into "
<< NV("Caller", Caller) << ": "
<< NV("Reason", IR.getFailureReason());
});
continue;
}
++NumInlined;
emitInlinedIntoBasedOnCost(ORE, DLoc, Block, *Callee, *Caller, *OIC);
// If inlining this function gave us any new call sites, throw them
// onto our worklist to process. They are useful inline candidates.
if (!InlineInfo.InlinedCalls.empty()) {
// Create a new inline history entry for this, so that we remember
// that these new callsites came about due to inlining Callee.
int NewHistoryID = InlineHistory.size();
InlineHistory.push_back(std::make_pair(Callee, InlineHistoryID));
#ifndef NDEBUG
// Make sure no dupplicates in the inline candidates. This could
// happen when a callsite is simpilfied to reusing the return value
// of another callsite during function cloning, thus the other
// callsite will be reconsidered here.
DenseSet<CallBase *> DbgCallSites;
for (auto &II : CallSites)
DbgCallSites.insert(II.first);
#endif
for (Value *Ptr : InlineInfo.InlinedCalls) {
#ifndef NDEBUG
assert(DbgCallSites.count(dyn_cast<CallBase>(Ptr)) == 0);
#endif
CallSites.push_back(
std::make_pair(dyn_cast<CallBase>(Ptr), NewHistoryID));
}
}
}
// If we inlined or deleted the last possible call site to the function,
// delete the function body now.
if (Callee && Callee->use_empty() && Callee->hasLocalLinkage() &&
// TODO: Can remove if in SCC now.
!SCCFunctions.count(Callee) &&
// The function may be apparently dead, but if there are indirect
// callgraph references to the node, we cannot delete it yet, this
// could invalidate the CGSCC iterator.
CG[Callee]->getNumReferences() == 0) {
LLVM_DEBUG(dbgs() << " -> Deleting dead function: "
<< Callee->getName() << "\n");
CallGraphNode *CalleeNode = CG[Callee];
// Remove any call graph edges from the callee to its callees.
CalleeNode->removeAllCalledFunctions();
// Removing the node for callee from the call graph and delete it.
delete CG.removeFunctionFromModule(CalleeNode);
++NumDeleted;
}
// Remove this call site from the list. If possible, use
// swap/pop_back for efficiency, but do not use it if doing so would
// move a call site to a function in this SCC before the
// 'FirstCallInSCC' barrier.
if (SCC.isSingular()) {
CallSites[CSi] = CallSites.back();
CallSites.pop_back();
} else {
CallSites.erase(CallSites.begin() + CSi);
}
--CSi;
Changed = true;
LocalChange = true;
}
} while (LocalChange);
return Changed;
}
bool LegacyInlinerBase::inlineCalls(CallGraphSCC &SCC) {
CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
ACT = &getAnalysis<AssumptionCacheTracker>();
PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
GetTLI = [&](Function &F) -> const TargetLibraryInfo & {
return getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
};
auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
return ACT->getAssumptionCache(F);
};
return inlineCallsImpl(
SCC, CG, GetAssumptionCache, PSI, GetTLI, InsertLifetime,
[&](CallBase &CB) { return getInlineCost(CB); }, LegacyAARGetter(*this),
ImportedFunctionsStats);
}
/// Remove now-dead linkonce functions at the end of
/// processing to avoid breaking the SCC traversal.
bool LegacyInlinerBase::doFinalization(CallGraph &CG) {
if (InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No)
ImportedFunctionsStats.dump(InlinerFunctionImportStats ==
InlinerFunctionImportStatsOpts::Verbose);
return removeDeadFunctions(CG);
}
/// Remove dead functions that are not included in DNR (Do Not Remove) list.
bool LegacyInlinerBase::removeDeadFunctions(CallGraph &CG,
bool AlwaysInlineOnly) {
SmallVector<CallGraphNode *, 16> FunctionsToRemove;
SmallVector<Function *, 16> DeadFunctionsInComdats;
auto RemoveCGN = [&](CallGraphNode *CGN) {
// Remove any call graph edges from the function to its callees.
CGN->removeAllCalledFunctions();
// Remove any edges from the external node to the function's call graph
// node. These edges might have been made irrelegant due to
// optimization of the program.
CG.getExternalCallingNode()->removeAnyCallEdgeTo(CGN);
// Removing the node for callee from the call graph and delete it.
FunctionsToRemove.push_back(CGN);
};
// Scan for all of the functions, looking for ones that should now be removed
// from the program. Insert the dead ones in the FunctionsToRemove set.
for (const auto &I : CG) {
CallGraphNode *CGN = I.second.get();
Function *F = CGN->getFunction();
if (!F || F->isDeclaration())
continue;
// Handle the case when this function is called and we only want to care
// about always-inline functions. This is a bit of a hack to share code
// between here and the InlineAlways pass.
if (AlwaysInlineOnly && !F->hasFnAttribute(Attribute::AlwaysInline))
continue;
// If the only remaining users of the function are dead constants, remove
// them.
F->removeDeadConstantUsers();
if (!F->isDefTriviallyDead())
continue;
// It is unsafe to drop a function with discardable linkage from a COMDAT
// without also dropping the other members of the COMDAT.
// The inliner doesn't visit non-function entities which are in COMDAT
// groups so it is unsafe to do so *unless* the linkage is local.
if (!F->hasLocalLinkage()) {
if (F->hasComdat()) {
DeadFunctionsInComdats.push_back(F);
continue;
}
}
RemoveCGN(CGN);
}
if (!DeadFunctionsInComdats.empty()) {
// Filter out the functions whose comdats remain alive.
filterDeadComdatFunctions(DeadFunctionsInComdats);
// Remove the rest.
for (Function *F : DeadFunctionsInComdats)
RemoveCGN(CG[F]);
}
if (FunctionsToRemove.empty())
return false;
// Now that we know which functions to delete, do so. We didn't want to do
// this inline, because that would invalidate our CallGraph::iterator
// objects. :(
//
// Note that it doesn't matter that we are iterating over a non-stable order
// here to do this, it doesn't matter which order the functions are deleted
// in.
array_pod_sort(FunctionsToRemove.begin(), FunctionsToRemove.end());
FunctionsToRemove.erase(
std::unique(FunctionsToRemove.begin(), FunctionsToRemove.end()),
FunctionsToRemove.end());
for (CallGraphNode *CGN : FunctionsToRemove) {
delete CG.removeFunctionFromModule(CGN);
++NumDeleted;
}
return true;
}
InlineAdvisor &
InlinerPass::getAdvisor(const ModuleAnalysisManagerCGSCCProxy::Result &MAM,
FunctionAnalysisManager &FAM, Module &M) {
if (OwnedAdvisor)
return *OwnedAdvisor;
auto *IAA = MAM.getCachedResult<InlineAdvisorAnalysis>(M);
if (!IAA) {
// It should still be possible to run the inliner as a stand-alone SCC pass,
// for test scenarios. In that case, we default to the
// DefaultInlineAdvisor, which doesn't need to keep state between SCC pass
// runs. It also uses just the default InlineParams.
// In this case, we need to use the provided FAM, which is valid for the
// duration of the inliner pass, and thus the lifetime of the owned advisor.
// The one we would get from the MAM can be invalidated as a result of the
// inliner's activity.
OwnedAdvisor = std::make_unique<DefaultInlineAdvisor>(
M, FAM, getInlineParams(),
InlineContext{LTOPhase, InlinePass::CGSCCInliner});
if (!CGSCCInlineReplayFile.empty())
OwnedAdvisor = getReplayInlineAdvisor(
M, FAM, M.getContext(), std::move(OwnedAdvisor),
ReplayInlinerSettings{CGSCCInlineReplayFile,
CGSCCInlineReplayScope,
CGSCCInlineReplayFallback,
{CGSCCInlineReplayFormat}},
/*EmitRemarks=*/true,
InlineContext{LTOPhase,
InlinePass::ReplayCGSCCInliner});
return *OwnedAdvisor;
}
assert(IAA->getAdvisor() &&
"Expected a present InlineAdvisorAnalysis also have an "
"InlineAdvisor initialized");
return *IAA->getAdvisor();
}
PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC,
CGSCCAnalysisManager &AM, LazyCallGraph &CG,
CGSCCUpdateResult &UR) {
const auto &MAMProxy =
AM.getResult<ModuleAnalysisManagerCGSCCProxy>(InitialC, CG);
bool Changed = false;
assert(InitialC.size() > 0 && "Cannot handle an empty SCC!");
Module &M = *InitialC.begin()->getFunction().getParent();
ProfileSummaryInfo *PSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(M);
FunctionAnalysisManager &FAM =
AM.getResult<FunctionAnalysisManagerCGSCCProxy>(InitialC, CG)
.getManager();
InlineAdvisor &Advisor = getAdvisor(MAMProxy, FAM, M);
Advisor.onPassEntry(&InitialC);
auto AdvisorOnExit = make_scope_exit([&] { Advisor.onPassExit(&InitialC); });
// We use a single common worklist for calls across the entire SCC. We
// process these in-order and append new calls introduced during inlining to
// the end. The PriorityInlineOrder is optional here, in which the smaller
// callee would have a higher priority to inline.
//
// Note that this particular order of processing is actually critical to
// avoid very bad behaviors. Consider *highly connected* call graphs where
// each function contains a small amount of code and a couple of calls to
// other functions. Because the LLVM inliner is fundamentally a bottom-up
// inliner, it can handle gracefully the fact that these all appear to be
// reasonable inlining candidates as it will flatten things until they become
// too big to inline, and then move on and flatten another batch.
//
// However, when processing call edges *within* an SCC we cannot rely on this
// bottom-up behavior. As a consequence, with heavily connected *SCCs* of
// functions we can end up incrementally inlining N calls into each of
// N functions because each incremental inlining decision looks good and we
// don't have a topological ordering to prevent explosions.
//
// To compensate for this, we don't process transitive edges made immediate
// by inlining until we've done one pass of inlining across the entire SCC.
// Large, highly connected SCCs still lead to some amount of code bloat in
// this model, but it is uniformly spread across all the functions in the SCC
// and eventually they all become too large to inline, rather than
// incrementally maknig a single function grow in a super linear fashion.
SmallVector<std::pair<CallBase *, int>, 16> Calls;
// Populate the initial list of calls in this SCC.
for (auto &N : InitialC) {
auto &ORE =
FAM.getResult<OptimizationRemarkEmitterAnalysis>(N.getFunction());
// We want to generally process call sites top-down in order for
// simplifications stemming from replacing the call with the returned value
// after inlining to be visible to subsequent inlining decisions.
// FIXME: Using instructions sequence is a really bad way to do this.
// Instead we should do an actual RPO walk of the function body.
for (Instruction &I : instructions(N.getFunction()))
if (auto *CB = dyn_cast<CallBase>(&I))
if (Function *Callee = CB->getCalledFunction()) {
if (!Callee->isDeclaration())
Calls.push_back({CB, -1});
else if (!isa<IntrinsicInst>(I)) {
using namespace ore;
setInlineRemark(*CB, "unavailable definition");
ORE.emit([&]() {
return OptimizationRemarkMissed(DEBUG_TYPE, "NoDefinition", &I)
<< NV("Callee", Callee) << " will not be inlined into "
<< NV("Caller", CB->getCaller())
<< " because its definition is unavailable"
<< setIsVerbose();
});
}
}
}
if (Calls.empty())
return PreservedAnalyses::all();
// Capture updatable variable for the current SCC.
auto *C = &InitialC;
// When inlining a callee produces new call sites, we want to keep track of
// the fact that they were inlined from the callee. This allows us to avoid
// infinite inlining in some obscure cases. To represent this, we use an
// index into the InlineHistory vector.
SmallVector<std::pair<Function *, int>, 16> InlineHistory;
// Track a set vector of inlined callees so that we can augment the caller
// with all of their edges in the call graph before pruning out the ones that
// got simplified away.
SmallSetVector<Function *, 4> InlinedCallees;
// Track the dead functions to delete once finished with inlining calls. We
// defer deleting these to make it easier to handle the call graph updates.
SmallVector<Function *, 4> DeadFunctions;
// Track potentially dead non-local functions with comdats to see if they can
// be deleted as a batch after inlining.
SmallVector<Function *, 4> DeadFunctionsInComdats;
// Loop forward over all of the calls. Note that we cannot cache the size as
// inlining can introduce new calls that need to be processed.
for (int I = 0; I < (int)Calls.size(); ++I) {
// We expect the calls to typically be batched with sequences of calls that
// have the same caller, so we first set up some shared infrastructure for
// this caller. We also do any pruning we can at this layer on the caller
// alone.
Function &F = *Calls[I].first->getCaller();
LazyCallGraph::Node &N = *CG.lookup(F);
if (CG.lookupSCC(N) != C)
continue;
LLVM_DEBUG(dbgs() << "Inlining calls in: " << F.getName() << "\n"
<< " Function size: " << F.getInstructionCount()
<< "\n");
auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
return FAM.getResult<AssumptionAnalysis>(F);
};
// Now process as many calls as we have within this caller in the sequence.
// We bail out as soon as the caller has to change so we can update the
// call graph and prepare the context of that new caller.
bool DidInline = false;
for (; I < (int)Calls.size() && Calls[I].first->getCaller() == &F; ++I) {
auto &P = Calls[I];
CallBase *CB = P.first;
const int InlineHistoryID = P.second;
Function &Callee = *CB->getCalledFunction();
if (InlineHistoryID != -1 &&
inlineHistoryIncludes(&Callee, InlineHistoryID, InlineHistory)) {
LLVM_DEBUG(dbgs() << "Skipping inlining due to history: "
<< F.getName() << " -> " << Callee.getName() << "\n");
setInlineRemark(*CB, "recursive");
continue;
}
// Check if this inlining may repeat breaking an SCC apart that has
// already been split once before. In that case, inlining here may
// trigger infinite inlining, much like is prevented within the inliner
// itself by the InlineHistory above, but spread across CGSCC iterations
// and thus hidden from the full inline history.
LazyCallGraph::SCC *CalleeSCC = CG.lookupSCC(*CG.lookup(Callee));
if (CalleeSCC == C && UR.InlinedInternalEdges.count({&N, C})) {
LLVM_DEBUG(dbgs() << "Skipping inlining internal SCC edge from a node "
"previously split out of this SCC by inlining: "
<< F.getName() << " -> " << Callee.getName() << "\n");
setInlineRemark(*CB, "recursive SCC split");
continue;
}
std::unique_ptr<InlineAdvice> Advice =
Advisor.getAdvice(*CB, OnlyMandatory);
// Check whether we want to inline this callsite.
if (!Advice)
continue;
if (!Advice->isInliningRecommended()) {
Advice->recordUnattemptedInlining();
continue;
}
int CBCostMult =
getStringFnAttrAsInt(
*CB, InlineConstants::FunctionInlineCostMultiplierAttributeName)
.value_or(1);
// Setup the data structure used to plumb customization into the
// `InlineFunction` routine.
InlineFunctionInfo IFI(
/*cg=*/nullptr, GetAssumptionCache, PSI,
&FAM.getResult<BlockFrequencyAnalysis>(*(CB->getCaller())),
&FAM.getResult<BlockFrequencyAnalysis>(Callee));
InlineResult IR =
InlineFunction(*CB, IFI, /*MergeAttributes=*/true,
&FAM.getResult<AAManager>(*CB->getCaller()));
if (!IR.isSuccess()) {
Advice->recordUnsuccessfulInlining(IR);
continue;
}
DidInline = true;
InlinedCallees.insert(&Callee);
++NumInlined;
LLVM_DEBUG(dbgs() << " Size after inlining: "
<< F.getInstructionCount() << "\n");
// Add any new callsites to defined functions to the worklist.
if (!IFI.InlinedCallSites.empty()) {
int NewHistoryID = InlineHistory.size();
InlineHistory.push_back({&Callee, InlineHistoryID});
for (CallBase *ICB : reverse(IFI.InlinedCallSites)) {
Function *NewCallee = ICB->getCalledFunction();
assert(!(NewCallee && NewCallee->isIntrinsic()) &&
"Intrinsic calls should not be tracked.");
if (!NewCallee) {
// Try to promote an indirect (virtual) call without waiting for
// the post-inline cleanup and the next DevirtSCCRepeatedPass
// iteration because the next iteration may not happen and we may
// miss inlining it.
if (tryPromoteCall(*ICB))
NewCallee = ICB->getCalledFunction();
}
if (NewCallee) {
if (!NewCallee->isDeclaration()) {
Calls.push_back({ICB, NewHistoryID});
// Continually inlining through an SCC can result in huge compile
// times and bloated code since we arbitrarily stop at some point
// when the inliner decides it's not profitable to inline anymore.
// We attempt to mitigate this by making these calls exponentially
// more expensive.
// This doesn't apply to calls in the same SCC since if we do
// inline through the SCC the function will end up being
// self-recursive which the inliner bails out on, and inlining
// within an SCC is necessary for performance.
if (CalleeSCC != C &&
CalleeSCC == CG.lookupSCC(CG.get(*NewCallee))) {
Attribute NewCBCostMult = Attribute::get(
M.getContext(),
InlineConstants::FunctionInlineCostMultiplierAttributeName,
itostr(CBCostMult * IntraSCCCostMultiplier));
ICB->addFnAttr(NewCBCostMult);
}
}
}
}
}
// For local functions or discardable functions without comdats, check
// whether this makes the callee trivially dead. In that case, we can drop
// the body of the function eagerly which may reduce the number of callers
// of other functions to one, changing inline cost thresholds. Non-local
// discardable functions with comdats are checked later on.
bool CalleeWasDeleted = false;
if (Callee.isDiscardableIfUnused() && Callee.hasZeroLiveUses() &&
!CG.isLibFunction(Callee)) {
if (Callee.hasLocalLinkage() || !Callee.hasComdat()) {
Calls.erase(
std::remove_if(Calls.begin() + I + 1, Calls.end(),
[&](const std::pair<CallBase *, int> &Call) {
return Call.first->getCaller() == &Callee;
}),
Calls.end());
// Clear the body and queue the function itself for deletion when we
// finish inlining and call graph updates.
// Note that after this point, it is an error to do anything other
// than use the callee's address or delete it.
Callee.dropAllReferences();
assert(!is_contained(DeadFunctions, &Callee) &&
"Cannot put cause a function to become dead twice!");
DeadFunctions.push_back(&Callee);
CalleeWasDeleted = true;
} else {
DeadFunctionsInComdats.push_back(&Callee);
}
}
if (CalleeWasDeleted)
Advice->recordInliningWithCalleeDeleted();
else
Advice->recordInlining();
}
// Back the call index up by one to put us in a good position to go around
// the outer loop.
--I;
if (!DidInline)
continue;
Changed = true;
// At this point, since we have made changes we have at least removed
// a call instruction. However, in the process we do some incremental
// simplification of the surrounding code. This simplification can
// essentially do all of the same things as a function pass and we can
// re-use the exact same logic for updating the call graph to reflect the
// change.
// Inside the update, we also update the FunctionAnalysisManager in the
// proxy for this particular SCC. We do this as the SCC may have changed and
// as we're going to mutate this particular function we want to make sure
// the proxy is in place to forward any invalidation events.
LazyCallGraph::SCC *OldC = C;
C = &updateCGAndAnalysisManagerForCGSCCPass(CG, *C, N, AM, UR, FAM);
LLVM_DEBUG(dbgs() << "Updated inlining SCC: " << *C << "\n");
// If this causes an SCC to split apart into multiple smaller SCCs, there
// is a subtle risk we need to prepare for. Other transformations may
// expose an "infinite inlining" opportunity later, and because of the SCC
// mutation, we will revisit this function and potentially re-inline. If we
// do, and that re-inlining also has the potentially to mutate the SCC
// structure, the infinite inlining problem can manifest through infinite
// SCC splits and merges. To avoid this, we capture the originating caller
// node and the SCC containing the call edge. This is a slight over
// approximation of the possible inlining decisions that must be avoided,
// but is relatively efficient to store. We use C != OldC to know when
// a new SCC is generated and the original SCC may be generated via merge
// in later iterations.
//
// It is also possible that even if no new SCC is generated
// (i.e., C == OldC), the original SCC could be split and then merged
// into the same one as itself. and the original SCC will be added into
// UR.CWorklist again, we want to catch such cases too.
//
// FIXME: This seems like a very heavyweight way of retaining the inline
// history, we should look for a more efficient way of tracking it.
if ((C != OldC || UR.CWorklist.count(OldC)) &&
llvm::any_of(InlinedCallees, [&](Function *Callee) {
return CG.lookupSCC(*CG.lookup(*Callee)) == OldC;
})) {
LLVM_DEBUG(dbgs() << "Inlined an internal call edge and split an SCC, "
"retaining this to avoid infinite inlining.\n");
UR.InlinedInternalEdges.insert({&N, OldC});
}
InlinedCallees.clear();
// Invalidate analyses for this function now so that we don't have to
// invalidate analyses for all functions in this SCC later.
FAM.invalidate(F, PreservedAnalyses::none());
}
// We must ensure that we only delete functions with comdats if every function
// in the comdat is going to be deleted.
if (!DeadFunctionsInComdats.empty()) {
filterDeadComdatFunctions(DeadFunctionsInComdats);
for (auto *Callee : DeadFunctionsInComdats)
Callee->dropAllReferences();
DeadFunctions.append(DeadFunctionsInComdats);
}
// Now that we've finished inlining all of the calls across this SCC, delete
// all of the trivially dead functions, updating the call graph and the CGSCC
// pass manager in the process.
//
// Note that this walks a pointer set which has non-deterministic order but
// that is OK as all we do is delete things and add pointers to unordered
// sets.
for (Function *DeadF : DeadFunctions) {
// Get the necessary information out of the call graph and nuke the
// function there. Also, clear out any cached analyses.
auto &DeadC = *CG.lookupSCC(*CG.lookup(*DeadF));
FAM.clear(*DeadF, DeadF->getName());
AM.clear(DeadC, DeadC.getName());
auto &DeadRC = DeadC.getOuterRefSCC();
CG.removeDeadFunction(*DeadF);
// Mark the relevant parts of the call graph as invalid so we don't visit
// them.
UR.InvalidatedSCCs.insert(&DeadC);
UR.InvalidatedRefSCCs.insert(&DeadRC);
// If the updated SCC was the one containing the deleted function, clear it.
if (&DeadC == UR.UpdatedC)
UR.UpdatedC = nullptr;
// And delete the actual function from the module.
M.getFunctionList().erase(DeadF);
++NumDeleted;
}
if (!Changed)
return PreservedAnalyses::all();
PreservedAnalyses PA;
// Even if we change the IR, we update the core CGSCC data structures and so
// can preserve the proxy to the function analysis manager.
PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
// We have already invalidated all analyses on modified functions.
PA.preserveSet<AllAnalysesOn<Function>>();
return PA;
}
ModuleInlinerWrapperPass::ModuleInlinerWrapperPass(InlineParams Params,
bool MandatoryFirst,
InlineContext IC,
InliningAdvisorMode Mode,
unsigned MaxDevirtIterations)
: Params(Params), IC(IC), Mode(Mode),
MaxDevirtIterations(MaxDevirtIterations) {
// Run the inliner first. The theory is that we are walking bottom-up and so
// the callees have already been fully optimized, and we want to inline them
// into the callers so that our optimizations can reflect that.
// For PreLinkThinLTO pass, we disable hot-caller heuristic for sample PGO
// because it makes profile annotation in the backend inaccurate.
if (MandatoryFirst) {
PM.addPass(InlinerPass(/*OnlyMandatory*/ true));
if (EnablePostSCCAdvisorPrinting)
PM.addPass(InlineAdvisorAnalysisPrinterPass(dbgs()));
}
PM.addPass(InlinerPass());
if (EnablePostSCCAdvisorPrinting)
PM.addPass(InlineAdvisorAnalysisPrinterPass(dbgs()));
}
PreservedAnalyses ModuleInlinerWrapperPass::run(Module &M,
ModuleAnalysisManager &MAM) {
auto &IAA = MAM.getResult<InlineAdvisorAnalysis>(M);
if (!IAA.tryCreate(Params, Mode,
{CGSCCInlineReplayFile,
CGSCCInlineReplayScope,
CGSCCInlineReplayFallback,
{CGSCCInlineReplayFormat}},
IC)) {
M.getContext().emitError(
"Could not setup Inlining Advisor for the requested "
"mode and/or options");
return PreservedAnalyses::all();
}
// We wrap the CGSCC pipeline in a devirtualization repeater. This will try
// to detect when we devirtualize indirect calls and iterate the SCC passes
// in that case to try and catch knock-on inlining or function attrs
// opportunities. Then we add it to the module pipeline by walking the SCCs
// in postorder (or bottom-up).
// If MaxDevirtIterations is 0, we just don't use the devirtualization
// wrapper.
if (MaxDevirtIterations == 0)
MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(PM)));
else
MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(
createDevirtSCCRepeatedPass(std::move(PM), MaxDevirtIterations)));
MPM.addPass(std::move(AfterCGMPM));
MPM.run(M, MAM);
// Discard the InlineAdvisor, a subsequent inlining session should construct
// its own.
auto PA = PreservedAnalyses::all();
if (!KeepAdvisorForPrinting)
PA.abandon<InlineAdvisorAnalysis>();
return PA;
}
void InlinerPass::printPipeline(
raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
static_cast<PassInfoMixin<InlinerPass> *>(this)->printPipeline(
OS, MapClassName2PassName);
if (OnlyMandatory)
OS << "<only-mandatory>";
}
void ModuleInlinerWrapperPass::printPipeline(
raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
// Print some info about passes added to the wrapper. This is however
// incomplete as InlineAdvisorAnalysis part isn't included (which also depends
// on Params and Mode).
if (!MPM.isEmpty()) {
MPM.printPipeline(OS, MapClassName2PassName);
OS << ",";
}
OS << "cgscc(";
if (MaxDevirtIterations != 0)
OS << "devirt<" << MaxDevirtIterations << ">(";
PM.printPipeline(OS, MapClassName2PassName);
if (MaxDevirtIterations != 0)
OS << ")";
OS << ")";
}