#include "llvm/Transforms/IPO/Inliner.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/None.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/AliasAnalysis.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/InlineCost.h"
#include "llvm/Analysis/LazyCallGraph.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ProfileSummaryInfo.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CallSite.h"
#include "llvm/IR/DataLayout.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/Cloning.h"
#include "llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h"
#include "llvm/Transforms/Utils/ModuleUtils.h"
#include <algorithm>
#include <cassert>
#include <functional>
#include <sstream>
#include <tuple>
#include <utility>
#include <vector>

Macros
#define	DEBUG_TYPE "inline"

Typedefs
using	InlinedArrayAllocasTy = DenseMap< ArrayType , std::vector< AllocaInst > >

Enumerations
enum	InlinerFunctionImportStatsOpts

Functions
	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")

	STATISTIC (NumCallerCallersAnalyzed, "Number of caller-callers analyzed")

static void	mergeInlinedArrayAllocas (Function *Caller, InlineFunctionInfo &IFI, InlinedArrayAllocasTy &InlinedArrayAllocas, int InlineHistory)
	Look at all of the allocas that we inlined through this call site. More...

static InlineResult	InlineCallIfPossible (CallSite CS, 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 operation. More...

static bool	shouldBeDeferred (Function *Caller, CallSite CS, InlineCost IC, int &TotalSecondaryCost, function_ref< InlineCost(CallSite CS)> GetInlineCost)
	Return true if inlining of CS can block the caller from being inlined which is proved to be more beneficial. More...

static std::basic_ostream< char > &	operator<< (std::basic_ostream< char > &R, const ore::NV &Arg)

template<class RemarkT >
RemarkT &	operator<< (RemarkT &&R, const InlineCost &IC)

static std::string	inlineCostStr (const InlineCost &IC)

static Optional< InlineCost >	shouldInline (CallSite CS, function_ref< InlineCost(CallSite CS)> GetInlineCost, OptimizationRemarkEmitter &ORE)
	Return the cost only if the inliner should attempt to inline at the given CallSite. More...

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 specified function. More...

static void	emit_inlined_into (OptimizationRemarkEmitter &ORE, DebugLoc &DLoc, const BasicBlock *Block, const Function &Callee, const Function &Caller, const InlineCost &IC)

static void	setInlineRemark (CallSite &CS, StringRef message)

static bool	inlineCallsImpl (CallGraphSCC &SCC, CallGraph &CG, std::function< AssumptionCache &(Function &)> GetAssumptionCache, ProfileSummaryInfo *PSI, TargetLibraryInfo &TLI, bool InsertLifetime, function_ref< InlineCost(CallSite CS)> GetInlineCost, function_ref< AAResults &(Function &)> AARGetter, ImportedFunctionsInliningStatistics &ImportedFunctionsStats)

Variables
static cl::opt< bool >	DisableInlinedAllocaMerging ("disable-inlined-alloca-merging", cl::init(false), cl::Hidden)
	Flag to disable manual alloca merging. More...

static 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"))

static cl::opt< bool >	InlineRemarkAttribute ("inline-remark-attribute", cl::init(false), cl::Hidden, cl::desc("Enable adding inline-remark attribute to" " callsites processed by inliner but decided" " to be not inlined"))
	Flag to add inline messages as callsite attributes 'inline-remark'. More...

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "inline"

Definition at line 74 of file Inliner.cpp.

Referenced by emit_inlined_into(), llvm::InlinerPass::run(), and shouldInline().

Typedef Documentation

◆ InlinedArrayAllocasTy

using InlinedArrayAllocasTy = DenseMap<ArrayType *, std::vector<AllocaInst *> >

Definition at line 140 of file Inliner.cpp.

Enumeration Type Documentation

◆ InlinerFunctionImportStatsOpts

enum InlinerFunctionImportStatsOpts

strong

Definition at line 99 of file Inliner.cpp.

Function Documentation

◆ emit_inlined_into()

static void emit_inlined_into	(	OptimizationRemarkEmitter &	ORE,
		DebugLoc &	DLoc,
		const BasicBlock *	Block,
		const Function &	Callee,
		const Function &	Caller,
		const InlineCost &	IC
	)

static

Definition at line 508 of file Inliner.cpp.

References DEBUG_TYPE, llvm::OptimizationRemarkEmitter::emit(), and llvm::InlineCost::isAlways().

Referenced by llvm::InlinerPass::run().

◆ InlineCallIfPossible()

static InlineResult InlineCallIfPossible	(	CallSite	CS,
		InlineFunctionInfo &	IFI,
		InlinedArrayAllocasTy &	InlinedArrayAllocas,
		int	InlineHistory,
		bool	InsertLifetime,
		function_ref< AAResults &(Function &)> &	AARGetter,
		ImportedFunctionsInliningStatistics &	ImportedFunctionsStats
	)

static

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.

Definition at line 275 of file Inliner.cpp.

References Callee, DisableInlinedAllocaMerging, llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::getCalledFunction(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::getCaller(), llvm::InlineFunction(), IR, llvm::AttributeFuncs::mergeAttributesForInlining(), mergeInlinedArrayAllocas(), llvm::No, and llvm::ImportedFunctionsInliningStatistics::recordInline().

◆ inlineCallsImpl()

static bool inlineCallsImpl	(	CallGraphSCC &	SCC,
		CallGraph &	CG,
		std::function< AssumptionCache &(Function &)>	GetAssumptionCache,
		ProfileSummaryInfo *	PSI,
		TargetLibraryInfo &	TLI,
		bool	InsertLifetime,
		function_ref< InlineCost(CallSite CS)>	GetInlineCost,
		function_ref< AAResults &(Function &)>	AARGetter,
		ImportedFunctionsInliningStatistics &	ImportedFunctionsStats
	)

static

Definition at line 529 of file Inliner.cpp.

References llvm::dbgs(), and LLVM_DEBUG.

Referenced by llvm::LegacyInlinerBase::inlineCalls().

◆ inlineCostStr()

static std::string inlineCostStr ( const InlineCost & IC )

static

Definition at line 410 of file Inliner.cpp.

References llvm::Remark.

Referenced by llvm::InlinerPass::run(), and shouldInline().

◆ InlineHistoryIncludes()

static bool InlineHistoryIncludes	(	Function *	F,
		int	InlineHistoryID,
		const SmallVectorImpl< std::pair< Function *, int >> &	InlineHistory
	)

static

Return true if the specified inline history ID indicates an inline history that includes the specified function.

Definition at line 483 of file Inliner.cpp.

References assert(), and first.

Referenced by llvm::InlinerPass::run().

◆ mergeInlinedArrayAllocas()

static void mergeInlinedArrayAllocas	(	Function *	Caller,
		InlineFunctionInfo &	IFI,
		InlinedArrayAllocasTy &	InlinedArrayAllocas,
		int	InlineHistory
	)

static

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.

Definition at line 162 of file Inliner.cpp.

References llvm::dbgs(), llvm::dyn_cast(), llvm::Instruction::eraseFromParent(), llvm::DataLayout::getABITypeAlignment(), llvm::AllocaInst::getAlignment(), llvm::AllocaInst::getAllocatedType(), llvm::Value::getContext(), llvm::Module::getDataLayout(), llvm::MetadataAsValue::getIfExists(), llvm::LocalAsMetadata::getIfExists(), llvm::Instruction::getParent(), llvm::GlobalValue::getParent(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::AllocaInst::isArrayAllocation(), LLVM_DEBUG, llvm::Value::replaceAllUsesWith(), llvm::InlineFunctionInfo::StaticAllocas, and llvm::Value::users().

Referenced by InlineCallIfPossible().

◆ operator<<() [1/2]

static std::basic_ostream<char>& operator<<	(	std::basic_ostream< char > &	R,
		const ore::NV &	Arg
	)

static

Definition at line 389 of file Inliner.cpp.

References Arg.

◆ operator<<() [2/2]

template<class RemarkT >

RemarkT& operator<<	(	RemarkT &&	R,
		const InlineCost &	IC
	)

Definition at line 395 of file Inliner.cpp.

References llvm::InlineCost::getCost(), llvm::InlineCost::getReason(), llvm::InlineCost::getThreshold(), llvm::InlineCost::isAlways(), and llvm::InlineCost::isNever().

◆ setInlineRemark()

static void setInlineRemark	(	CallSite &	CS,
		StringRef	message
	)

static

Definition at line 520 of file Inliner.cpp.

References llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::addAttribute(), llvm::AttributeList::FunctionIndex, and llvm::Attribute::get().

Referenced by llvm::InlinerPass::run().

◆ shouldBeDeferred()

static bool shouldBeDeferred	(	Function *	Caller,
		CallSite	CS,
		InlineCost	IC,
		int &	TotalSecondaryCost,
		function_ref< InlineCost(CallSite CS)>	GetInlineCost
	)

static

Return true if inlining of CS can block the caller from being inlined which is proved to be more beneficial.

IC is the estimated inline cost associated with callsite CS. TotalSecondaryCost will be set to the estimated cost of inlining the caller if CS is suppressed for inlining.

Definition at line 308 of file Inliner.cpp.

References llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::getCalledFunction(), llvm::InlineCost::getCost(), llvm::InlineCost::getCostDelta(), llvm::GlobalValue::hasLinkOnceODRLinkage(), llvm::GlobalValue::hasLocalLinkage(), llvm::Value::hasOneUse(), llvm::InlineCost::isAlways(), llvm::InlineConstants::LastCallToStaticBonus, and llvm::Value::users().

Referenced by shouldInline().

◆ shouldInline()

static Optional<InlineCost> shouldInline	(	CallSite	CS,
		function_ref< InlineCost(CallSite CS)>	GetInlineCost,
		OptimizationRemarkEmitter &	ORE
	)

static

Return the cost only if the inliner should attempt to inline at the given CallSite.

If we return the cost, we will emit an optimisation remark later using that cost, so we won't do so from this function.

Definition at line 420 of file Inliner.cpp.

References Callee, llvm::dbgs(), DEBUG_TYPE, llvm::OptimizationRemarkEmitter::emit(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::getCalledFunction(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::getCaller(), llvm::InlineCost::getCost(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::getInstruction(), inlineCostStr(), llvm::InlineCost::isAlways(), llvm::InlineCost::isNever(), LLVM_DEBUG, llvm::None, and shouldBeDeferred().

Referenced by llvm::InlinerPass::run().

◆ STATISTIC() [1/5]

STATISTIC	(	NumInlined	,
		"Number of functions inlined"
	)

◆ STATISTIC() [2/5]

STATISTIC	(	NumCallsDeleted	,
		"Number of call sites	deleted,
		not inlined"
	)

◆ STATISTIC() [3/5]

STATISTIC	(	NumDeleted	,
		"Number of functions deleted because all callers found"
	)

◆ STATISTIC() [4/5]

STATISTIC	(	NumMergedAllocas	,
		"Number of allocas merged together"
	)

◆ STATISTIC() [5/5]

STATISTIC	(	NumCallerCallersAnalyzed	,
		"Number of caller-callers analyzed"
	)

Variable Documentation

◆ DisableInlinedAllocaMerging

cl::opt<bool> DisableInlinedAllocaMerging("disable-inlined-alloca-merging", cl::init(false), cl::Hidden)

static

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.

Referenced by InlineCallIfPossible().

◆ InlineRemarkAttribute

cl::opt<bool> InlineRemarkAttribute("inline-remark-attribute", cl::init(false), cl::Hidden, cl::desc("Enable adding inline-remark attribute to" " callsites processed by inliner but decided" " to be not inlined"))

static

Flag to add inline messages as callsite attributes 'inline-remark'.

◆ InlinerFunctionImportStats

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"))

static

Macros

Typedefs

Enumerations

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Typedef Documentation

◆ InlinedArrayAllocasTy

Enumeration Type Documentation

◆ InlinerFunctionImportStatsOpts

Function Documentation

◆ emit_inlined_into()

◆ InlineCallIfPossible()

◆ inlineCallsImpl()

◆ inlineCostStr()

◆ InlineHistoryIncludes()

◆ mergeInlinedArrayAllocas()

◆ operator<<() [1/2]

◆ operator<<() [2/2]

◆ setInlineRemark()

◆ shouldBeDeferred()

◆ shouldInline()

◆ STATISTIC() [1/5]

◆ STATISTIC() [2/5]

◆ STATISTIC() [3/5]

◆ STATISTIC() [4/5]

◆ STATISTIC() [5/5]

Variable Documentation

◆ DisableInlinedAllocaMerging

◆ InlineRemarkAttribute

◆ InlinerFunctionImportStats