#include "llvm/Transforms/Scalar/CallSiteSplitting.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Support/Debug.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"

Include dependency graph for CallSiteSplitting.cpp:

Macros
#define	DEBUG_TYPE "callsite-splitting"

Typedefs
typedef std::pair< ICmpInst *, unsigned >	ConditionTy

typedef SmallVector< ConditionTy, 2 >	ConditionsTy

using	PredsWithCondsTy = SmallVector< std::pair< BasicBlock *, ConditionsTy >, 2 >

Functions
	STATISTIC (NumCallSiteSplit, "Number of call-site split")

static void	addNonNullAttribute (CallSite CS, Value *Op)

static void	setConstantInArgument (CallSite CS, Value Op, Constant ConstValue)

static bool	isCondRelevantToAnyCallArgument (ICmpInst *Cmp, CallSite CS)

static void	recordCondition (CallSite CS, BasicBlock From, BasicBlock To, ConditionsTy &Conditions)
	If From has a conditional jump to To, add the condition to Conditions, if it is relevant to any argument at CS. More...

static void	recordConditions (CallSite CS, BasicBlock Pred, ConditionsTy &Conditions, BasicBlock StopAt)
	Record ICmp conditions relevant to any argument in CS following Pred's single predecessors. More...

static void	addConditions (CallSite CS, const ConditionsTy &Conditions)

static SmallVector< BasicBlock *, 2 >	getTwoPredecessors (BasicBlock *BB)

static bool	canSplitCallSite (CallSite CS, TargetTransformInfo &TTI)

static Instruction *	cloneInstForMustTail (Instruction I, Instruction Before, Value *V)

static void	copyMustTailReturn (BasicBlock SplitBB, Instruction CI, Instruction *NewCI)
	Copy mandatory `musttail` return sequence that follows original `CI`, and link it up to `NewCI` value instead: More...

static void	splitCallSite (CallSite CS, const SmallVectorImpl< std::pair< BasicBlock *, ConditionsTy >> &Preds, DomTreeUpdater &DTU)
	For each (predecessor, conditions from predecessors) pair, it will split the basic block containing the call site, hook it up to the predecessor and replace the call instruction with new call instructions, which contain constraints based on the conditions from their predecessors. More...

static bool	isPredicatedOnPHI (CallSite CS)

static PredsWithCondsTy	shouldSplitOnPHIPredicatedArgument (CallSite CS)

static PredsWithCondsTy	shouldSplitOnPredicatedArgument (CallSite CS, DomTreeUpdater &DTU)

static bool	tryToSplitCallSite (CallSite CS, TargetTransformInfo &TTI, DomTreeUpdater &DTU)

static bool	doCallSiteSplitting (Function &F, TargetLibraryInfo &TLI, TargetTransformInfo &TTI, DominatorTree &DT)

	INITIALIZE_PASS_BEGIN (CallSiteSplittingLegacyPass, "callsite-splitting", "Call-site splitting", false, false) INITIALIZE_PASS_END(CallSiteSplittingLegacyPass

Variables
static cl::opt< unsigned >	DuplicationThreshold ("callsite-splitting-duplication-threshold", cl::Hidden, cl::desc("Only allow instructions before a call, if " "their cost is below DuplicationThreshold"), cl::init(5))
	Only allow instructions before a call, if their CodeSize cost is below DuplicationThreshold. More...

callsite	splitting

callsite Call site	false

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "callsite-splitting"

Definition at line 74 of file CallSiteSplitting.cpp.

Typedef Documentation

◆ ConditionsTy

typedef SmallVector<ConditionTy, 2> ConditionsTy

Definition at line 127 of file CallSiteSplitting.cpp.

◆ ConditionTy

typedef std::pair<ICmpInst *, unsigned> ConditionTy

Definition at line 126 of file CallSiteSplitting.cpp.

◆ PredsWithCondsTy

using PredsWithCondsTy = SmallVector<std::pair<BasicBlock *, ConditionsTy>, 2>

Definition at line 443 of file CallSiteSplitting.cpp.

Function Documentation

◆ addConditions()

static void addConditions	(	CallSite	CS,
		const ConditionsTy &	Conditions
	)

static

Definition at line 167 of file CallSiteSplitting.cpp.

References addNonNullAttribute(), Arg, assert(), llvm::Value::getType(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::Constant::isNullValue(), llvm::Type::isPointerTy(), and setConstantInArgument().

Referenced by splitCallSite().

◆ addNonNullAttribute()

static void addNonNullAttribute	(	CallSite	CS,
		Value *	Op
	)

static

Definition at line 87 of file CallSiteSplitting.cpp.

References llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::addParamAttr(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::args(), I, and llvm::Attribute::NonNull.

Referenced by addConditions().

◆ canSplitCallSite()

static bool canSplitCallSite	(	CallSite	CS,
		TargetTransformInfo &	TTI
	)

static

Definition at line 186 of file CallSiteSplitting.cpp.

References llvm::BasicBlock::begin(), llvm::BasicBlock::canSplitPredecessors(), DuplicationThreshold, llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::getInstruction(), llvm::TargetTransformInfo::getInstructionCost(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Instruction::getParent(), llvm::BasicBlock::isEHPad(), llvm::make_range(), llvm::predecessors(), llvm::SmallVectorBase::size(), and llvm::TargetTransformInfo::TCK_CodeSize.

Referenced by tryToSplitCallSite().

◆ cloneInstForMustTail()

static Instruction* cloneInstForMustTail	(	Instruction *	I,
		Instruction *	Before,
		Value *	V
	)

static

Definition at line 221 of file CallSiteSplitting.cpp.

References llvm::Instruction::clone(), llvm::Value::getName(), llvm::Instruction::insertBefore(), llvm::Value::setName(), and llvm::User::setOperand().

Referenced by copyMustTailReturn().

◆ copyMustTailReturn()

static void copyMustTailReturn	(	BasicBlock *	SplitBB,
		Instruction *	CI,
		Instruction *	NewCI
	)

static

Copy mandatory musttail return sequence that follows original CI, and link it up to NewCI value instead:

(optional) bitcast NewCI to ...
ret bitcast or NewCI

Insert this sequence right before SplitBB's terminator, which will be cleaned up later in splitCallSite below.

Definition at line 239 of file CallSiteSplitting.cpp.

References assert(), cloneInstForMustTail(), llvm::dyn_cast(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::BasicBlock::getParent(), llvm::Function::getReturnType(), llvm::BasicBlock::getTerminator(), and llvm::Type::isVoidTy().

Referenced by splitCallSite().

◆ doCallSiteSplitting()

static bool doCallSiteSplitting	(	Function &	F,
		TargetLibraryInfo &	TLI,
		TargetTransformInfo &	TTI,
		DominatorTree &	DT
	)

static

Definition at line 506 of file CallSiteSplitting.cpp.

References llvm::AnalysisUsage::addPreserved(), llvm::AnalysisUsage::addRequired(), llvm::Function::begin(), Callee, llvm::Function::end(), F(), llvm::Pass::getAnalysisUsage(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::getCalledFunction(), llvm::BasicBlock::getFirstNonPHIOrDbg(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::PassRegistry::getPassRegistry(), llvm::BasicBlock::getTerminator(), I, llvm::ARM_PROC::IE, INITIALIZE_PASS_BEGIN(), INITIALIZE_PASS_DEPENDENCY, llvm::initializeCallSiteSplittingLegacyPassPass(), llvm::GlobalValue::isDeclaration(), llvm::isInstructionTriviallyDead(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::isMustTailCall(), llvm::DomTreeUpdater::Lazy, runOnFunction(), and tryToSplitCallSite().

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

◆ getTwoPredecessors()

static SmallVector<BasicBlock *, 2> getTwoPredecessors ( BasicBlock * BB )

static

Definition at line 180 of file CallSiteSplitting.cpp.

References assert(), llvm::predecessors(), and llvm::SmallVectorBase::size().

Referenced by shouldSplitOnPHIPredicatedArgument(), and shouldSplitOnPredicatedArgument().

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	CallSiteSplittingLegacyPass	,
		"callsite-splitting"	,
		"Call-site splitting"	,
		false	,
		false
	)

Referenced by doCallSiteSplitting().

◆ isCondRelevantToAnyCallArgument()

static bool isCondRelevantToAnyCallArgument	(	ICmpInst *	Cmp,
		CallSite	CS
	)

static

Definition at line 110 of file CallSiteSplitting.cpp.

References llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::arg_begin(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::arg_end(), assert(), E, llvm::User::getOperand(), I, llvm::Attribute::NonNull, and llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::paramHasAttr().

Referenced by recordCondition().

◆ isPredicatedOnPHI()

static bool isPredicatedOnPHI ( CallSite CS )

static

Definition at line 417 of file CallSiteSplitting.cpp.

References llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::args(), assert(), llvm::BasicBlock::getFirstNonPHIOrDbg(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::getInstruction(), llvm::Instruction::getParent(), and I.

Referenced by shouldSplitOnPHIPredicatedArgument().

◆ recordCondition()

static void recordCondition	(	CallSite	CS,
		BasicBlock *	From,
		BasicBlock *	To,
		ConditionsTy &	Conditions
	)

static

If From has a conditional jump to To, add the condition to Conditions, if it is relevant to any argument at CS.

Definition at line 131 of file CallSiteSplitting.cpp.

References llvm::dyn_cast(), llvm::BasicBlock::getTerminator(), llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, isCondRelevantToAnyCallArgument(), llvm::PatternMatch::m_Constant(), llvm::PatternMatch::m_ICmp(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by recordConditions(), and shouldSplitOnPredicatedArgument().

◆ recordConditions()

static void recordConditions	(	CallSite	CS,
		BasicBlock *	Pred,
		ConditionsTy &	Conditions,
		BasicBlock *	StopAt
	)

static

Record ICmp conditions relevant to any argument in CS following Pred's single predecessors.

If there are conflicting conditions along a path, like x == 1 and x == 0, the first condition will be used. We stop once we reach an edge to StopAt.

Definition at line 154 of file CallSiteSplitting.cpp.

References llvm::SmallPtrSetImpl< PtrType >::count(), From, llvm::BasicBlock::getSinglePredecessor(), llvm::SmallPtrSetImpl< PtrType >::insert(), and recordCondition().

Referenced by shouldSplitOnPredicatedArgument().

◆ setConstantInArgument()

static void setConstantInArgument	(	CallSite	CS,
		Value *	Op,
		Constant *	ConstValue
	)

static

Definition at line 96 of file CallSiteSplitting.cpp.

References llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::args(), I, llvm::Attribute::NonNull, llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::removeParamAttr(), and llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::setArgument().

Referenced by addConditions().

◆ shouldSplitOnPHIPredicatedArgument()

static PredsWithCondsTy shouldSplitOnPHIPredicatedArgument ( CallSite CS )

static

Definition at line 447 of file CallSiteSplitting.cpp.

References llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::getInstruction(), llvm::Instruction::getParent(), getTwoPredecessors(), and isPredicatedOnPHI().

Referenced by tryToSplitCallSite().

◆ shouldSplitOnPredicatedArgument()

static PredsWithCondsTy shouldSplitOnPredicatedArgument	(	CallSite	CS,
		DomTreeUpdater &	DTU
	)

static

Definition at line 458 of file CallSiteSplitting.cpp.

References llvm::all_of(), assert(), llvm::SmallVectorBase::empty(), llvm::DomTreeUpdater::getDomTree(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::getInstruction(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::Instruction::getParent(), getTwoPredecessors(), llvm::DomTreeUpdater::hasDomTree(), llvm::make_range(), P, llvm::SmallVectorTemplateBase< T >::push_back(), recordCondition(), and recordConditions().

Referenced by tryToSplitCallSite().

◆ splitCallSite()

static void splitCallSite	(	CallSite	CS,
		const SmallVectorImpl< std::pair< BasicBlock *, ConditionsTy >> &	Preds,
		DomTreeUpdater &	DTU
	)

static

For each (predecessor, conditions from predecessors) pair, it will split the basic block containing the call site, hook it up to the predecessor and replace the call instruction with new call instructions, which contain constraints based on the conditions from their predecessors.

For example, in the IR below with an OR condition, the call-site can be split. In this case, Preds for Tail is [(Header, a == null), (TBB, a != null, b == null)]. Tail is replaced by 2 split blocks, containing CallInst1, which has constraints based on the conditions from Head and CallInst2, which has constraints based on the conditions coming from TBB.

From :

Header: c = icmp eq i32* a, null br i1 c Tail, TBB TBB: c2 = icmp eq i32* b, null br i1 c Tail, End Tail: ca = call i1 (i32* a, i32* b)

to :

Header: // PredBB1 is Header c = icmp eq i32* a, null br i1 c Tail-split1, TBB TBB: // PredBB2 is TBB c2 = icmp eq i32* b, null br i1 c Tail-split2, End Tail-split1: ca1 = call (i32* null, i32* b) // CallInst1 br Tail Tail-split2: ca2 = call (i32* nonnull a, i32* null) // CallInst2 br Tail Tail: p = phi i1 [ca1, Tail-split1],[ca2, Tail-split2]

Note that in case any arguments at the call-site are constrained by its predecessors, new call-sites with more constrained arguments will be created in createCallSitesOnPredicatedArgument().

Definition at line 302 of file CallSiteSplitting.cpp.

References addConditions(), llvm::PHINode::addIncoming(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::args(), assert(), llvm::BasicBlock::begin(), copyMustTailReturn(), llvm::PHINode::Create(), llvm::dbgs(), llvm::DomTreeUpdater::deleteBB(), llvm::DomTreeUpdater::deleteEdge(), llvm::DuplicateInstructionsInSplitBetween(), llvm::Instruction::eraseFromParent(), llvm::Instruction::getDebugLoc(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::getInstruction(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Value::getName(), llvm::Instruction::getParent(), getParent(), llvm::ilist_node_impl< OptionsT >::getReverseIterator(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), I, llvm::Instruction::insertBefore(), llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::isMustTailCall(), LLVM_DEBUG, llvm::BasicBlock::phis(), llvm::predecessors(), llvm::BasicBlock::rend(), llvm::Value::replaceAllUsesWith(), second, llvm::Instruction::setDebugLoc(), llvm::SmallVectorBase::size(), llvm::SplitBlock(), and llvm::Value::use_empty().

Referenced by tryToSplitCallSite().

◆ STATISTIC()

STATISTIC	(	NumCallSiteSplit	,
		"Number of call-site split"
	)

◆ tryToSplitCallSite()

static bool tryToSplitCallSite	(	CallSite	CS,
		TargetTransformInfo &	TTI,
		DomTreeUpdater &	DTU
	)

static

Definition at line 490 of file CallSiteSplitting.cpp.

References llvm::CallSiteBase< FunTy, BBTy, ValTy, UserTy, UseTy, InstrTy, CallTy, InvokeTy, IterTy >::arg_size(), canSplitCallSite(), shouldSplitOnPHIPredicatedArgument(), shouldSplitOnPredicatedArgument(), and splitCallSite().

Referenced by doCallSiteSplitting().

Variable Documentation

◆ DuplicationThreshold

cl::opt<unsigned> DuplicationThreshold("callsite-splitting-duplication-threshold", cl::Hidden, cl::desc("Only allow instructions before a call, if " "their cost is below DuplicationThreshold"), cl::init(5))

static

Only allow instructions before a call, if their CodeSize cost is below DuplicationThreshold.

Those instructions need to be duplicated in all split blocks.

Referenced by canSplitCallSite().

◆ false

callsite Call site false

Definition at line 577 of file CallSiteSplitting.cpp.

◆ splitting

callsite Call site splitting

Definition at line 577 of file CallSiteSplitting.cpp.

Macros

Typedefs

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Typedef Documentation

◆ ConditionsTy

◆ ConditionTy

◆ PredsWithCondsTy

Function Documentation

◆ addConditions()

◆ addNonNullAttribute()

◆ canSplitCallSite()

◆ cloneInstForMustTail()

◆ copyMustTailReturn()

◆ doCallSiteSplitting()

◆ getTwoPredecessors()

◆ INITIALIZE_PASS_BEGIN()

◆ isCondRelevantToAnyCallArgument()

◆ isPredicatedOnPHI()

◆ recordCondition()

◆ recordConditions()

◆ setConstantInArgument()

◆ shouldSplitOnPHIPredicatedArgument()

◆ shouldSplitOnPredicatedArgument()

◆ splitCallSite()

◆ STATISTIC()

◆ tryToSplitCallSite()

Variable Documentation

◆ DuplicationThreshold

◆ false

◆ splitting