1 //===- CallSiteSplitting.cpp ----------------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a transformation that tries to split a call-site to pass
11 // more constrained arguments if its argument is predicated in the control flow
12 // so that we can expose better context to the later passes (e.g, inliner, jump
13 // threading, or IPA-CP based function cloning, etc.).
14 // As of now we support two cases :
16 // 1) Try to a split call-site with constrained arguments, if any constraints
17 // on any argument can be found by following the single predecessors of the
18 // all site's predecessors. Currently this pass only handles call-sites with 2
19 // predecessors. For example, in the code below, we try to split the call-site
20 // since we can predicate the argument(ptr) based on the OR condition.
27 // callee(null) // set the known constant value
29 // callee(nonnull ptr) // set non-null attribute in the argument
31 // 2) We can also split a call-site based on constant incoming values of a PHI
35 // %c = icmp eq i32 %i1, %i2
36 // br i1 %c, label %Tail, label %TBB
40 // %p = phi i32 [ 0, %Header], [ 1, %TBB]
41 // call void @bar(i32 %p)
44 // %c = icmp eq i32 %i1, %i2
45 // br i1 %c, label %Tail-split0, label %TBB
47 // br label %Tail-split1
49 // call void @bar(i32 0)
52 // call void @bar(i32 1)
55 // %p = phi i32 [ 0, %Tail-split0 ], [ 1, %Tail-split1 ]
57 //===----------------------------------------------------------------------===//
59 #include "llvm/Transforms/Scalar/CallSiteSplitting.h"
60 #include "llvm/ADT/Statistic.h"
61 #include "llvm/Analysis/TargetLibraryInfo.h"
62 #include "llvm/IR/IntrinsicInst.h"
63 #include "llvm/IR/PatternMatch.h"
64 #include "llvm/Support/Debug.h"
65 #include "llvm/Transforms/Scalar.h"
66 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
67 #include "llvm/Transforms/Utils/Local.h"
70 using namespace PatternMatch;
72 #define DEBUG_TYPE "callsite-splitting"
74 STATISTIC(NumCallSiteSplit, "Number of call-site split");
76 static void addNonNullAttribute(Instruction *CallI, Instruction *NewCallI,
78 CallSite CS(NewCallI);
80 for (auto &I : CS.args()) {
82 CS.addParamAttr(ArgNo, Attribute::NonNull);
87 static void setConstantInArgument(Instruction *CallI, Instruction *NewCallI,
88 Value *Op, Constant *ConstValue) {
89 CallSite CS(NewCallI);
91 for (auto &I : CS.args()) {
93 CS.setArgument(ArgNo, ConstValue);
98 static bool isCondRelevantToAnyCallArgument(ICmpInst *Cmp, CallSite CS) {
99 assert(isa<Constant>(Cmp->getOperand(1)) && "Expected a constant operand.");
100 Value *Op0 = Cmp->getOperand(0);
102 for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E;
104 // Don't consider constant or arguments that are already known non-null.
105 if (isa<Constant>(*I) || CS.paramHasAttr(ArgNo, Attribute::NonNull))
114 /// If From has a conditional jump to To, add the condition to Conditions,
115 /// if it is relevant to any argument at CS.
117 recordCondition(const CallSite &CS, BasicBlock *From, BasicBlock *To,
118 SmallVectorImpl<std::pair<ICmpInst *, unsigned>> &Conditions) {
119 auto *BI = dyn_cast<BranchInst>(From->getTerminator());
120 if (!BI || !BI->isConditional())
123 CmpInst::Predicate Pred;
124 Value *Cond = BI->getCondition();
125 if (!match(Cond, m_ICmp(Pred, m_Value(), m_Constant())))
128 ICmpInst *Cmp = cast<ICmpInst>(Cond);
129 if (Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE)
130 if (isCondRelevantToAnyCallArgument(Cmp, CS))
131 Conditions.push_back({Cmp, From->getTerminator()->getSuccessor(0) == To
133 : Cmp->getInversePredicate()});
136 /// Record ICmp conditions relevant to any argument in CS following Pred's
137 /// single successors. If there are conflicting conditions along a path, like
138 /// x == 1 and x == 0, the first condition will be used.
140 recordConditions(const CallSite &CS, BasicBlock *Pred,
141 SmallVectorImpl<std::pair<ICmpInst *, unsigned>> &Conditions) {
142 recordCondition(CS, Pred, CS.getInstruction()->getParent(), Conditions);
143 BasicBlock *From = Pred;
144 BasicBlock *To = Pred;
145 SmallPtrSet<BasicBlock *, 4> Visited = {From};
146 while (!Visited.count(From->getSinglePredecessor()) &&
147 (From = From->getSinglePredecessor())) {
148 recordCondition(CS, From, To, Conditions);
154 addConditions(CallSite &CS,
155 SmallVectorImpl<std::pair<ICmpInst *, unsigned>> &Conditions) {
156 if (Conditions.empty())
159 Instruction *NewCI = CS.getInstruction()->clone();
160 for (auto &Cond : Conditions) {
161 Value *Arg = Cond.first->getOperand(0);
162 Constant *ConstVal = cast<Constant>(Cond.first->getOperand(1));
163 if (Cond.second == ICmpInst::ICMP_EQ)
164 setConstantInArgument(CS.getInstruction(), NewCI, Arg, ConstVal);
165 else if (ConstVal->getType()->isPointerTy() && ConstVal->isNullValue()) {
166 assert(Cond.second == ICmpInst::ICMP_NE);
167 addNonNullAttribute(CS.getInstruction(), NewCI, Arg);
173 static SmallVector<BasicBlock *, 2> getTwoPredecessors(BasicBlock *BB) {
174 SmallVector<BasicBlock *, 2> Preds(predecessors((BB)));
175 assert(Preds.size() == 2 && "Expected exactly 2 predecessors!");
179 static bool canSplitCallSite(CallSite CS) {
180 // FIXME: As of now we handle only CallInst. InvokeInst could be handled
181 // without too much effort.
182 Instruction *Instr = CS.getInstruction();
183 if (!isa<CallInst>(Instr))
186 // Allow splitting a call-site only when there is no instruction before the
187 // call-site in the basic block. Based on this constraint, we only clone the
188 // call instruction, and we do not move a call-site across any other
190 BasicBlock *CallSiteBB = Instr->getParent();
191 if (Instr != CallSiteBB->getFirstNonPHIOrDbg())
194 // Need 2 predecessors and cannot split an edge from an IndirectBrInst.
195 SmallVector<BasicBlock *, 2> Preds(predecessors(CallSiteBB));
196 if (Preds.size() != 2 || isa<IndirectBrInst>(Preds[0]->getTerminator()) ||
197 isa<IndirectBrInst>(Preds[1]->getTerminator()))
200 return CallSiteBB->canSplitPredecessors();
203 /// Return true if the CS is split into its new predecessors which are directly
204 /// hooked to each of its original predecessors pointed by PredBB1 and PredBB2.
205 /// CallInst1 and CallInst2 will be the new call-sites placed in the new
206 /// predecessors split for PredBB1 and PredBB2, respectively.
207 /// For example, in the IR below with an OR condition, the call-site can
208 /// be split. Assuming PredBB1=Header and PredBB2=TBB, CallInst1 will be the
209 /// call-site placed between Header and Tail, and CallInst2 will be the
210 /// call-site between TBB and Tail.
215 /// %c = icmp eq i32* %a, null
216 /// br i1 %c %Tail, %TBB
218 /// %c2 = icmp eq i32* %b, null
219 /// br i1 %c %Tail, %End
221 /// %ca = call i1 @callee (i32* %a, i32* %b)
225 /// Header: // PredBB1 is Header
226 /// %c = icmp eq i32* %a, null
227 /// br i1 %c %Tail-split1, %TBB
228 /// TBB: // PredBB2 is TBB
229 /// %c2 = icmp eq i32* %b, null
230 /// br i1 %c %Tail-split2, %End
232 /// %ca1 = call @callee (i32* null, i32* %b) // CallInst1
235 /// %ca2 = call @callee (i32* nonnull %a, i32* null) // CallInst2
238 /// %p = phi i1 [%ca1, %Tail-split1],[%ca2, %Tail-split2]
240 /// Note that in case any arguments at the call-site are constrained by its
241 /// predecessors, new call-sites with more constrained arguments will be
242 /// created in createCallSitesOnPredicatedArgument().
243 static void splitCallSite(CallSite CS, BasicBlock *PredBB1, BasicBlock *PredBB2,
244 Instruction *CallInst1, Instruction *CallInst2) {
245 Instruction *Instr = CS.getInstruction();
246 BasicBlock *TailBB = Instr->getParent();
247 assert(Instr == (TailBB->getFirstNonPHIOrDbg()) && "Unexpected call-site");
249 BasicBlock *SplitBlock1 =
250 SplitBlockPredecessors(TailBB, PredBB1, ".predBB1.split");
251 BasicBlock *SplitBlock2 =
252 SplitBlockPredecessors(TailBB, PredBB2, ".predBB2.split");
254 assert((SplitBlock1 && SplitBlock2) && "Unexpected new basic block split.");
257 CallInst1 = Instr->clone();
259 CallInst2 = Instr->clone();
261 CallInst1->insertBefore(&*SplitBlock1->getFirstInsertionPt());
262 CallInst2->insertBefore(&*SplitBlock2->getFirstInsertionPt());
264 CallSite CS1(CallInst1);
265 CallSite CS2(CallInst2);
267 // Handle PHIs used as arguments in the call-site.
268 for (auto &PI : *TailBB) {
269 PHINode *PN = dyn_cast<PHINode>(&PI);
273 for (auto &CI : CS.args()) {
275 CS1.setArgument(ArgNo, PN->getIncomingValueForBlock(SplitBlock1));
276 CS2.setArgument(ArgNo, PN->getIncomingValueForBlock(SplitBlock2));
282 // Replace users of the original call with a PHI mering call-sites split.
283 if (Instr->getNumUses()) {
284 PHINode *PN = PHINode::Create(Instr->getType(), 2, "phi.call",
285 TailBB->getFirstNonPHI());
286 PN->addIncoming(CallInst1, SplitBlock1);
287 PN->addIncoming(CallInst2, SplitBlock2);
288 Instr->replaceAllUsesWith(PN);
290 DEBUG(dbgs() << "split call-site : " << *Instr << " into \n");
291 DEBUG(dbgs() << " " << *CallInst1 << " in " << SplitBlock1->getName()
293 DEBUG(dbgs() << " " << *CallInst2 << " in " << SplitBlock2->getName()
295 Instr->eraseFromParent();
299 // Return true if the call-site has an argument which is a PHI with only
300 // constant incoming values.
301 static bool isPredicatedOnPHI(CallSite CS) {
302 Instruction *Instr = CS.getInstruction();
303 BasicBlock *Parent = Instr->getParent();
304 if (Instr != Parent->getFirstNonPHIOrDbg())
307 for (auto &BI : *Parent) {
308 if (PHINode *PN = dyn_cast<PHINode>(&BI)) {
309 for (auto &I : CS.args())
311 assert(PN->getNumIncomingValues() == 2 &&
312 "Unexpected number of incoming values");
313 if (PN->getIncomingBlock(0) == PN->getIncomingBlock(1))
315 if (PN->getIncomingValue(0) == PN->getIncomingValue(1))
317 if (isa<Constant>(PN->getIncomingValue(0)) &&
318 isa<Constant>(PN->getIncomingValue(1)))
327 static bool tryToSplitOnPHIPredicatedArgument(CallSite CS) {
328 if (!isPredicatedOnPHI(CS))
331 auto Preds = getTwoPredecessors(CS.getInstruction()->getParent());
332 splitCallSite(CS, Preds[0], Preds[1], nullptr, nullptr);
336 static bool tryToSplitOnPredicatedArgument(CallSite CS) {
337 auto Preds = getTwoPredecessors(CS.getInstruction()->getParent());
338 if (Preds[0] == Preds[1])
341 SmallVector<std::pair<ICmpInst *, unsigned>, 2> C1, C2;
342 recordConditions(CS, Preds[0], C1);
343 recordConditions(CS, Preds[1], C2);
345 Instruction *CallInst1 = addConditions(CS, C1);
346 Instruction *CallInst2 = addConditions(CS, C2);
347 if (!CallInst1 && !CallInst2)
350 splitCallSite(CS, Preds[1], Preds[0], CallInst2, CallInst1);
354 static bool tryToSplitCallSite(CallSite CS) {
355 if (!CS.arg_size() || !canSplitCallSite(CS))
357 return tryToSplitOnPredicatedArgument(CS) ||
358 tryToSplitOnPHIPredicatedArgument(CS);
361 static bool doCallSiteSplitting(Function &F, TargetLibraryInfo &TLI) {
362 bool Changed = false;
363 for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE;) {
364 BasicBlock &BB = *BI++;
365 for (BasicBlock::iterator II = BB.begin(), IE = BB.end(); II != IE;) {
366 Instruction *I = &*II++;
367 CallSite CS(cast<Value>(I));
368 if (!CS || isa<IntrinsicInst>(I) || isInstructionTriviallyDead(I, &TLI))
371 Function *Callee = CS.getCalledFunction();
372 if (!Callee || Callee->isDeclaration())
374 Changed |= tryToSplitCallSite(CS);
381 struct CallSiteSplittingLegacyPass : public FunctionPass {
383 CallSiteSplittingLegacyPass() : FunctionPass(ID) {
384 initializeCallSiteSplittingLegacyPassPass(*PassRegistry::getPassRegistry());
387 void getAnalysisUsage(AnalysisUsage &AU) const override {
388 AU.addRequired<TargetLibraryInfoWrapperPass>();
389 FunctionPass::getAnalysisUsage(AU);
392 bool runOnFunction(Function &F) override {
396 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
397 return doCallSiteSplitting(F, TLI);
402 char CallSiteSplittingLegacyPass::ID = 0;
403 INITIALIZE_PASS_BEGIN(CallSiteSplittingLegacyPass, "callsite-splitting",
404 "Call-site splitting", false, false)
405 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
406 INITIALIZE_PASS_END(CallSiteSplittingLegacyPass, "callsite-splitting",
407 "Call-site splitting", false, false)
408 FunctionPass *llvm::createCallSiteSplittingPass() {
409 return new CallSiteSplittingLegacyPass();
412 PreservedAnalyses CallSiteSplittingPass::run(Function &F,
413 FunctionAnalysisManager &AM) {
414 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
416 if (!doCallSiteSplitting(F, TLI))
417 return PreservedAnalyses::all();
418 PreservedAnalyses PA;