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

Macros
#define	DEBUG_TYPE "callsite-splitting"

Typedefs
using	ConditionTy = std::pair< ICmpInst *, unsigned >

using	ConditionsTy = SmallVector< ConditionTy, 2 >

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

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

static void	addNonNullAttribute (CallBase &CB, Value *Op)

static void	setConstantInArgument (CallBase &CB, Value Op, Constant ConstValue)

static bool	isCondRelevantToAnyCallArgument (ICmpInst *Cmp, CallBase &CB)

static void	recordCondition (CallBase &CB, 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 CB.

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

static void	addConditions (CallBase &CB, const ConditionsTy &Conditions)

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

static bool	canSplitCallSite (CallBase &CB, 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:

static void	splitCallSite (CallBase &CB, ArrayRef< 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.

static bool	isPredicatedOnPHI (CallBase &CB)

static PredsWithCondsTy	shouldSplitOnPHIPredicatedArgument (CallBase &CB)

static PredsWithCondsTy	shouldSplitOnPredicatedArgument (CallBase &CB, DomTreeUpdater &DTU)

static bool	tryToSplitCallSite (CallBase &CB, TargetTransformInfo &TTI, DomTreeUpdater &DTU)

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

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.

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "callsite-splitting"

Definition at line 73 of file CallSiteSplitting.cpp.

Typedef Documentation

◆ ConditionsTy

using ConditionsTy = SmallVector<ConditionTy, 2>

Definition at line 125 of file CallSiteSplitting.cpp.

◆ ConditionTy

using ConditionTy = std::pair<ICmpInst *, unsigned>

Definition at line 124 of file CallSiteSplitting.cpp.

◆ PredsWithCondsTy

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

Definition at line 439 of file CallSiteSplitting.cpp.

Function Documentation

◆ addConditions()

static void addConditions	(	CallBase &	CB,
		const ConditionsTy &	Conditions
	)

static

Definition at line 165 of file CallSiteSplitting.cpp.

References addNonNullAttribute(), assert(), Cond, llvm::Value::getType(), llvm::Constant::isNullValue(), llvm::Type::isPointerTy(), and setConstantInArgument().

Referenced by splitCallSite().

◆ addNonNullAttribute()

static void addNonNullAttribute	(	CallBase &	CB,
		Value *	Op
	)

static

Definition at line 86 of file CallSiteSplitting.cpp.

References llvm::CallBase::addParamAttr(), llvm::CallBase::args(), and I.

Referenced by addConditions().

◆ canSplitCallSite()

static bool canSplitCallSite	(	CallBase &	CB,
		TargetTransformInfo &	TTI
	)

static

Definition at line 184 of file CallSiteSplitting.cpp.

References llvm::BasicBlock::begin(), llvm::CallBase::cannotDuplicate(), llvm::BasicBlock::canSplitPredecessors(), DuplicationThreshold, llvm::TargetTransformInfo::getInstructionCost(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), llvm::CallBase::isConvergent(), llvm::BasicBlock::isEHPad(), llvm::make_range(), llvm::predecessors(), llvm::SmallVectorBase< Size_T >::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 Before, and I.

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::ilist_node_impl< OptionsT >::getIterator(), llvm::BasicBlock::getParent(), llvm::Function::getReturnType(), llvm::BasicBlock::getTerminator(), II, and llvm::Type::isVoidTy().

Referenced by splitCallSite().

◆ doCallSiteSplitting()

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

static

Definition at line 502 of file CallSiteSplitting.cpp.

References F, llvm::CallBase::getCalledFunction(), II, llvm::isInstructionTriviallyDead(), llvm::CallBase::isMustTailCall(), llvm::make_early_inc_range(), and tryToSplitCallSite().

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

◆ getTwoPredecessors()

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

static

Definition at line 178 of file CallSiteSplitting.cpp.

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

Referenced by shouldSplitOnPHIPredicatedArgument(), and shouldSplitOnPredicatedArgument().

◆ isCondRelevantToAnyCallArgument()

static bool isCondRelevantToAnyCallArgument	(	ICmpInst *	Cmp,
		CallBase &	CB
	)

static

Definition at line 109 of file CallSiteSplitting.cpp.

References llvm::CallBase::arg_begin(), llvm::CallBase::arg_end(), assert(), I, and llvm::CallBase::paramHasAttr().

Referenced by recordCondition().

◆ isPredicatedOnPHI()

static bool isPredicatedOnPHI ( CallBase & CB )

static

Definition at line 416 of file CallSiteSplitting.cpp.

References llvm::CallBase::args(), assert(), llvm::BasicBlock::getFirstNonPHIOrDbg(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), and llvm::BasicBlock::phis().

Referenced by shouldSplitOnPHIPredicatedArgument().

◆ recordCondition()

static void recordCondition	(	CallBase &	CB,
		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 CB.

Definition at line 129 of file CallSiteSplitting.cpp.

References Cond, From, 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	(	CallBase &	CB,
		BasicBlock *	Pred,
		ConditionsTy &	Conditions,
		BasicBlock *	StopAt
	)

static

Record ICmp conditions relevant to any argument in CB 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 152 of file CallSiteSplitting.cpp.

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

Referenced by shouldSplitOnPredicatedArgument().

◆ setConstantInArgument()

static void setConstantInArgument	(	CallBase &	CB,
		Value *	Op,
		Constant *	ConstValue
	)

static

Definition at line 95 of file CallSiteSplitting.cpp.

References llvm::CallBase::args(), I, llvm::CallBase::removeParamAttr(), and llvm::CallBase::setArgOperand().

Referenced by addConditions().

◆ shouldSplitOnPHIPredicatedArgument()

static PredsWithCondsTy shouldSplitOnPHIPredicatedArgument ( CallBase & CB )

static

Definition at line 443 of file CallSiteSplitting.cpp.

References llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), getTwoPredecessors(), and isPredicatedOnPHI().

Referenced by tryToSplitCallSite().

◆ shouldSplitOnPredicatedArgument()

static PredsWithCondsTy shouldSplitOnPredicatedArgument	(	CallBase &	CB,
		DomTreeUpdater &	DTU
	)

static

Definition at line 454 of file CallSiteSplitting.cpp.

References llvm::all_of(), assert(), llvm::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT >::getDomTree(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), getTwoPredecessors(), llvm::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT >::hasDomTree(), P, llvm::SmallVectorTemplateBase< T, bool >::push_back(), recordCondition(), recordConditions(), and llvm::reverse().

Referenced by tryToSplitCallSite().

◆ splitCallSite()

static void splitCallSite	(	CallBase &	CB,
		ArrayRef< 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 @callee (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 @callee (i32* null, i32* b) // CallInst1 br Tail Tail-split2: ca2 = call @callee (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::GenericDomTreeUpdater< DerivedT, DomTreeT, PostDomTreeT >::applyUpdatesPermissive(), llvm::CallBase::args(), assert(), llvm::BasicBlock::begin(), copyMustTailReturn(), llvm::PHINode::Create(), llvm::dbgs(), llvm::DomTreeUpdater::deleteBB(), llvm::Instruction::dropDbgRecords(), llvm::DuplicateInstructionsInSplitBetween(), llvm::Instruction::eraseFromParent(), llvm::Instruction::getDebugLoc(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Value::getName(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), getParent(), llvm::ilist_node_impl< OptionsT >::getReverseIterator(), llvm::BasicBlock::getTerminator(), llvm::Value::getType(), I, llvm::Instruction::insertBefore(), llvm::CallBase::isMustTailCall(), LLVM_DEBUG, llvm::BasicBlock::phis(), llvm::predecessors(), llvm::BasicBlock::rend(), llvm::Value::replaceAllUsesWith(), llvm::Instruction::setDebugLoc(), llvm::SmallVectorBase< Size_T >::size(), llvm::SplitBlock(), and llvm::Value::use_empty().

Referenced by tryToSplitCallSite().

◆ STATISTIC()

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

◆ tryToSplitCallSite()

static bool tryToSplitCallSite	(	CallBase &	CB,
		TargetTransformInfo &	TTI,
		DomTreeUpdater &	DTU
	)

static

Definition at line 486 of file CallSiteSplitting.cpp.

References llvm::CallBase::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))	(	"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().

Macros

Typedefs

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Typedef Documentation

◆ ConditionsTy

◆ ConditionTy

◆ PredsWithCondsTy

Function Documentation

◆ addConditions()

◆ addNonNullAttribute()

◆ canSplitCallSite()

◆ cloneInstForMustTail()

◆ copyMustTailReturn()

◆ doCallSiteSplitting()

◆ getTwoPredecessors()

◆ isCondRelevantToAnyCallArgument()

◆ isPredicatedOnPHI()

◆ recordCondition()

◆ recordConditions()

◆ setConstantInArgument()

◆ shouldSplitOnPHIPredicatedArgument()

◆ shouldSplitOnPredicatedArgument()

◆ splitCallSite()

◆ STATISTIC()

◆ tryToSplitCallSite()

Variable Documentation

◆ DuplicationThreshold