#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/InitializePasses.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Transforms/Scalar.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)

	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.

callsite	splitting

callsite Call site	false

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "callsite-splitting"

Definition at line 75 of file CallSiteSplitting.cpp.

Typedef Documentation

◆ ConditionsTy

using ConditionsTy = SmallVector<ConditionTy, 2>

Definition at line 127 of file CallSiteSplitting.cpp.

◆ ConditionTy

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

Definition at line 126 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 167 of file CallSiteSplitting.cpp.

References addNonNullAttribute(), Arg, 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 88 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 186 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::Instruction::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 223 of file CallSiteSplitting.cpp.

References 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 241 of file CallSiteSplitting.cpp.

References assert(), cloneInstForMustTail(), 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 502 of file CallSiteSplitting.cpp.

References Callee, F, llvm::CallBase::getCalledFunction(), 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 180 of file CallSiteSplitting.cpp.

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

Referenced by shouldSplitOnPHIPredicatedArgument(), and shouldSplitOnPredicatedArgument().

◆ INITIALIZE_PASS_BEGIN()

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

◆ isCondRelevantToAnyCallArgument()

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

static

Definition at line 111 of file CallSiteSplitting.cpp.

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

Referenced by recordCondition().

◆ isPredicatedOnPHI()

static bool isPredicatedOnPHI ( CallBase & CB )

static

Definition at line 416 of file CallSiteSplitting.cpp.

References Arg, llvm::CallBase::args(), assert(), llvm::BasicBlock::getFirstNonPHIOrDbg(), llvm::Instruction::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 131 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 154 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 97 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::Instruction::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::DomTreeUpdater::getDomTree(), llvm::DominatorTreeBase< NodeT, IsPostDom >::getNode(), llvm::Instruction::getParent(), getTwoPredecessors(), llvm::DomTreeUpdater::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 304 of file CallSiteSplitting.cpp.

References addConditions(), llvm::PHINode::addIncoming(), llvm::DomTreeUpdater::applyUpdatesPermissive(), llvm::CallBase::args(), assert(), llvm::BasicBlock::begin(), copyMustTailReturn(), llvm::PHINode::Create(), llvm::dbgs(), llvm::DomTreeUpdater::deleteBB(), llvm::DuplicateInstructionsInSplitBetween(), llvm::Instruction::eraseFromParent(), llvm::Instruction::getDebugLoc(), 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::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().

◆ false

callsite Call site false

Definition at line 572 of file CallSiteSplitting.cpp.

◆ splitting

callsite Call site splitting

Definition at line 571 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