Go to the documentation of this file.
73 using namespace PatternMatch;
75 #define DEBUG_TYPE "callsite-splitting"
77 STATISTIC(NumCallSiteSplit,
"Number of call-site split");
84 cl::desc(
"Only allow instructions before a call, if "
85 "their cost is below DuplicationThreshold"),
90 for (
auto &
I : CB.
args()) {
100 for (
auto &
I : CB.
args()) {
112 assert(isa<Constant>(Cmp->getOperand(1)) &&
"Expected a constant operand.");
113 Value *Op0 = Cmp->getOperand(0);
117 if (isa<Constant>(*
I) || CB.
paramHasAttr(ArgNo, Attribute::NonNull))
133 auto *BI = dyn_cast<BranchInst>(
From->getTerminator());
134 if (!BI || !BI->isConditional())
145 Conditions.push_back({Cmp,
From->getTerminator()->getSuccessor(0) == To
147 : Cmp->getInversePredicate()});
159 while (To != StopAt && !Visited.
count(
From->getSinglePredecessor()) &&
160 (
From =
From->getSinglePredecessor())) {
168 for (
auto &
Cond : Conditions) {
170 Constant *ConstVal = cast<Constant>(
Cond.first->getOperand(1));
182 assert(Preds.size() == 2 &&
"Expected exactly 2 predecessors!");
192 if (!isa<CallInst>(CB))
198 if (Preds.size() != 2 || isa<IndirectBrInst>(Preds[0]->getTerminator()) ||
199 isa<IndirectBrInst>(Preds[1]->getTerminator()))
212 for (
auto &InstBeforeCall :
226 Copy->setName(
I->getName());
227 Copy->insertBefore(Before);
229 Copy->setOperand(0, V);
251 assert(RI &&
"`musttail` call must be followed by `ret` instruction");
305 ArrayRef<std::pair<BasicBlock *, ConditionsTy>> Preds,
315 if (!IsMustTailCall && !CB.
use_empty()) {
322 assert(Preds.size() == 2 &&
"The ValueToValueMaps array has size 2.");
326 for (
unsigned i = 0;
i < Preds.size();
i++) {
329 TailBB, PredBB, &*std::next(CB.
getIterator()), ValueToValueMaps[
i],
340 for (
auto &CI : CB.
args()) {
342 NewCI->setArgOperand(ArgNo, PN.getIncomingValueForBlock(
SplitBlock));
360 if (IsMustTailCall) {
366 assert(Splits.size() == 2 &&
"Expected exactly 2 splits!");
367 for (
unsigned i = 0;
i < Splits.size();
i++) {
368 Splits[
i]->getTerminator()->eraseFromParent();
377 auto *OriginalBegin = &*TailBB->
begin();
392 while (
I != TailBB->
rend()) {
397 if (isa<PHINode>(CurrentI))
401 for (
auto &Mapping : ValueToValueMaps)
403 cast<Instruction>(Mapping[CurrentI])->
getParent());
405 CurrentI->replaceAllUsesWith(NewPN);
409 if (CurrentI == OriginalBegin)
421 for (
auto &PN : Parent->
phis()) {
425 assert(PN.getNumIncomingValues() == 2 &&
426 "Unexpected number of incoming values");
427 if (PN.getIncomingBlock(0) == PN.getIncomingBlock(1))
429 if (PN.getIncomingValue(0) == PN.getIncomingValue(1))
431 if (isa<Constant>(PN.getIncomingValue(0)) &&
432 isa<Constant>(PN.getIncomingValue(1)))
448 return {{Preds[0], {}}, {Preds[1], {}}};
457 if (Preds[0] == Preds[1])
466 BasicBlock *StopAt = CSDTNode ? CSDTNode->getIDom()->getBlock() :
nullptr;
475 PredsCS.push_back({Pred, Conditions});
478 if (
all_of(PredsCS, [](
const std::pair<BasicBlock *, ConditionsTy> &
P) {
479 return P.second.empty();
493 if (PredsWithConds.empty())
495 if (PredsWithConds.empty())
506 bool Changed =
false;
508 auto II =
BB.getFirstNonPHIOrDbg()->getIterator();
509 auto IE =
BB.getTerminator()->getIterator();
514 while (II !=
IE && &*II !=
BB.getTerminator()) {
515 CallBase *CB = dyn_cast<CallBase>(&*II++);
539 struct CallSiteSplittingLegacyPass :
public FunctionPass {
557 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
558 auto &
TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
559 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
567 "Call-site splitting",
false,
false)
574 return new CallSiteSplittingLegacyPass();
A set of analyses that are preserved following a run of a transformation pass.
Analysis pass providing the TargetTransformInfo.
std::pair< ICmpInst *, unsigned > ConditionTy
This is an optimization pass for GlobalISel generic memory operations.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
Return a value (possibly void), from a function.
void initializeCallSiteSplittingLegacyPassPass(PassRegistry &)
static SmallVector< BasicBlock *, 2 > getTwoPredecessors(BasicBlock *BB)
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
const Function * getParent() const
Return the enclosing method, or null if none.
bool isPointerTy() const
True if this is an instance of PointerType.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
This class represents a no-op cast from one type to another.
static void addConditions(CallBase &CB, const ConditionsTy &Conditions)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
static Instruction * cloneInstForMustTail(Instruction *I, Instruction *Before, Value *V)
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
static PredsWithCondsTy shouldSplitOnPredicatedArgument(CallBase &CB, DomTreeUpdater &DTU)
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
reverse_self_iterator getReverseIterator()
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
bool isMustTailCall() const
Tests if this call site must be tail call optimized.
INITIALIZE_PASS_BEGIN(CallSiteSplittingLegacyPass, "callsite-splitting", "Call-site splitting", false, false) INITIALIZE_PASS_END(CallSiteSplittingLegacyPass
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
User::op_iterator arg_begin()
Return the iterator pointing to the beginning of the argument list.
bool canSplitPredecessors() const
FunctionPass * createCallSiteSplittingPass()
void addParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
Adds the attribute to the indicated argument.
LLVM Basic Block Representation.
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.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
void removeParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
Removes the attribute from the given argument.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
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 argum...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool match(Val *V, const Pattern &P)
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
iterator begin()
Instruction iterator methods.
Represent the analysis usage information of a pass.
bool isConvergent() const
Determine if the invoke is convergent.
Legacy analysis pass which computes a DominatorTree.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
STATISTIC(NumFunctions, "Total number of functions")
auto predecessors(MachineBasicBlock *BB)
static void addNonNullAttribute(CallBase &CB, Value *Op)
bool hasDomTree() const
Returns true if it holds a DominatorTree.
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 t...
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
static bool canSplitCallSite(CallBase &CB, TargetTransformInfo &TTI)
BasicBlock * DuplicateInstructionsInSplitBetween(BasicBlock *BB, BasicBlock *PredBB, Instruction *StopAt, ValueToValueMapTy &ValueMapping, DomTreeUpdater &DTU)
Split edge between BB and PredBB and duplicate all non-Phi instructions from BB between its beginning...
This is an important base class in LLVM.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Type * getReturnType() const
Returns the type of the ret val.
This instruction compares its operands according to the predicate given to the constructor.
void preserve()
Mark an analysis as preserved.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
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 inste...
static bool doCallSiteSplitting(Function &F, TargetLibraryInfo &TLI, TargetTransformInfo &TTI, DominatorTree &DT)
initializer< Ty > init(const Ty &Val)
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
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.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static void setConstantInArgument(CallBase &CB, Value *Op, Constant *ConstValue)
bool isVoidTy() const
Return true if this is 'void'.
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
User::op_iterator arg_end()
Return the iterator pointing to the end of the argument list.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
static PredsWithCondsTy shouldSplitOnPHIPredicatedArgument(CallBase &CB)
static bool tryToSplitCallSite(CallBase &CB, TargetTransformInfo &TTI, DomTreeUpdater &DTU)
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
SmallVector< MachineOperand, 4 > Cond
bool cannotDuplicate() const
Determine if the invoke cannot be duplicated.
Type * getType() const
All values are typed, get the type of this value.
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
static const Function * getParent(const Value *V)
self_iterator getIterator()
StringRef getName() const
Return a constant reference to the value's name.
bool paramHasAttr(unsigned ArgNo, Attribute::AttrKind Kind) const
Determine whether the argument or parameter has the given attribute.
void setArgOperand(unsigned i, Value *v)
amdgpu Simplify well known AMD library false FunctionCallee Callee
static bool runOnFunction(Function &F, bool PostInlining)
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
unsigned arg_size() const
Provides information about what library functions are available for the current target.
Analysis pass which computes a DominatorTree.
static bool isPredicatedOnPHI(CallBase &CB)
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
const BasicBlock * getParent() const
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
A container for analyses that lazily runs them and caches their results.
FunctionPass class - This class is used to implement most global optimizations.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
AnalysisUsage & addRequired()
BlockVerifier::State From
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
bool isEHPad() const
Return true if this basic block is an exception handling block.
LLVM Value Representation.
Analysis pass providing the TargetLibraryInfo.
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
static constexpr UpdateKind Delete
static bool isCondRelevantToAnyCallArgument(ICmpInst *Cmp, CallBase &CB)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.