1 //===- CallSiteSplitting.cpp ----------------------------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 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 : 15 // 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. 21 // 22 // Split from : 23 // if (!ptr || c) 24 // callee(ptr); 25 // to : 26 // if (!ptr) 27 // callee(null) // set the known constant value 28 // else if (c) 29 // callee(nonnull ptr) // set non-null attribute in the argument 30 // 31 // 2) We can also split a call-site based on constant incoming values of a PHI 32 // For example, 33 // from : 34 // Header: 35 // %c = icmp eq i32 %i1, %i2 36 // br i1 %c, label %Tail, label %TBB 37 // TBB: 38 // br label Tail% 39 // Tail: 40 // %p = phi i32 [ 0, %Header], [ 1, %TBB] 41 // call void @bar(i32 %p) 42 // to 43 // Header: 44 // %c = icmp eq i32 %i1, %i2 45 // br i1 %c, label %Tail-split0, label %TBB 46 // TBB: 47 // br label %Tail-split1 48 // Tail-split0: 49 // call void @bar(i32 0) 50 // br label %Tail 51 // Tail-split1: 52 // call void @bar(i32 1) 53 // br label %Tail 54 // Tail: 55 // %p = phi i32 [ 0, %Tail-split0 ], [ 1, %Tail-split1 ] 56 // 57 //===----------------------------------------------------------------------===// 58 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" 68 69 using namespace llvm; 70 using namespace PatternMatch; 71 72 #define DEBUG_TYPE "callsite-splitting" 73 74 STATISTIC(NumCallSiteSplit, "Number of call-site split"); 75 76 static void addNonNullAttribute(Instruction *CallI, Instruction *NewCallI, 77 Value *Op) { 78 CallSite CS(NewCallI); 79 unsigned ArgNo = 0; 80 for (auto &I : CS.args()) { 81 if (&*I == Op) 82 CS.addParamAttr(ArgNo, Attribute::NonNull); 83 ++ArgNo; 84 } 85 } 86 87 static void setConstantInArgument(Instruction *CallI, Instruction *NewCallI, 88 Value *Op, Constant *ConstValue) { 89 CallSite CS(NewCallI); 90 unsigned ArgNo = 0; 91 for (auto &I : CS.args()) { 92 if (&*I == Op) 93 CS.setArgument(ArgNo, ConstValue); 94 ++ArgNo; 95 } 96 } 97 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); 101 unsigned ArgNo = 0; 102 for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; 103 ++I, ++ArgNo) { 104 // Don't consider constant or arguments that are already known non-null. 105 if (isa<Constant>(*I) || CS.paramHasAttr(ArgNo, Attribute::NonNull)) 106 continue; 107 108 if (*I == Op0) 109 return true; 110 } 111 return false; 112 } 113 114 /// If From has a conditional jump to To, add the condition to Conditions, 115 /// if it is relevant to any argument at CS. 116 static void 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()) 121 return; 122 123 CmpInst::Predicate Pred; 124 Value *Cond = BI->getCondition(); 125 if (!match(Cond, m_ICmp(Pred, m_Value(), m_Constant()))) 126 return; 127 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 132 ? Pred 133 : Cmp->getInversePredicate()}); 134 } 135 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. 139 static void 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); 149 To = From; 150 } 151 } 152 153 static Instruction * 154 addConditions(CallSite &CS, 155 SmallVectorImpl<std::pair<ICmpInst *, unsigned>> &Conditions) { 156 if (Conditions.empty()) 157 return nullptr; 158 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); 168 } 169 } 170 return NewCI; 171 } 172 173 static SmallVector<BasicBlock *, 2> getTwoPredecessors(BasicBlock *BB) { 174 SmallVector<BasicBlock *, 2> Preds(predecessors((BB))); 175 assert(Preds.size() == 2 && "Expected exactly 2 predecessors!"); 176 return Preds; 177 } 178 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)) 184 return false; 185 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 189 // instruction. 190 BasicBlock *CallSiteBB = Instr->getParent(); 191 if (Instr != CallSiteBB->getFirstNonPHIOrDbg()) 192 return false; 193 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())) 198 return false; 199 200 return CallSiteBB->canSplitPredecessors(); 201 } 202 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. 211 /// 212 /// From : 213 /// 214 /// Header: 215 /// %c = icmp eq i32* %a, null 216 /// br i1 %c %Tail, %TBB 217 /// TBB: 218 /// %c2 = icmp eq i32* %b, null 219 /// br i1 %c %Tail, %End 220 /// Tail: 221 /// %ca = call i1 @callee (i32* %a, i32* %b) 222 /// 223 /// to : 224 /// 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 231 /// Tail-split1: 232 /// %ca1 = call @callee (i32* null, i32* %b) // CallInst1 233 /// br %Tail 234 /// Tail-split2: 235 /// %ca2 = call @callee (i32* nonnull %a, i32* null) // CallInst2 236 /// br %Tail 237 /// Tail: 238 /// %p = phi i1 [%ca1, %Tail-split1],[%ca2, %Tail-split2] 239 /// 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"); 248 249 BasicBlock *SplitBlock1 = 250 SplitBlockPredecessors(TailBB, PredBB1, ".predBB1.split"); 251 BasicBlock *SplitBlock2 = 252 SplitBlockPredecessors(TailBB, PredBB2, ".predBB2.split"); 253 254 assert((SplitBlock1 && SplitBlock2) && "Unexpected new basic block split."); 255 256 if (!CallInst1) 257 CallInst1 = Instr->clone(); 258 if (!CallInst2) 259 CallInst2 = Instr->clone(); 260 261 CallInst1->insertBefore(&*SplitBlock1->getFirstInsertionPt()); 262 CallInst2->insertBefore(&*SplitBlock2->getFirstInsertionPt()); 263 264 CallSite CS1(CallInst1); 265 CallSite CS2(CallInst2); 266 267 // Handle PHIs used as arguments in the call-site. 268 for (PHINode &PN : TailBB->phis()) { 269 unsigned ArgNo = 0; 270 for (auto &CI : CS.args()) { 271 if (&*CI == &PN) { 272 CS1.setArgument(ArgNo, PN.getIncomingValueForBlock(SplitBlock1)); 273 CS2.setArgument(ArgNo, PN.getIncomingValueForBlock(SplitBlock2)); 274 } 275 ++ArgNo; 276 } 277 } 278 279 // Replace users of the original call with a PHI mering call-sites split. 280 if (Instr->getNumUses()) { 281 PHINode *PN = PHINode::Create(Instr->getType(), 2, "phi.call", 282 TailBB->getFirstNonPHI()); 283 PN->addIncoming(CallInst1, SplitBlock1); 284 PN->addIncoming(CallInst2, SplitBlock2); 285 Instr->replaceAllUsesWith(PN); 286 } 287 DEBUG(dbgs() << "split call-site : " << *Instr << " into \n"); 288 DEBUG(dbgs() << " " << *CallInst1 << " in " << SplitBlock1->getName() 289 << "\n"); 290 DEBUG(dbgs() << " " << *CallInst2 << " in " << SplitBlock2->getName() 291 << "\n"); 292 Instr->eraseFromParent(); 293 NumCallSiteSplit++; 294 } 295 296 // Return true if the call-site has an argument which is a PHI with only 297 // constant incoming values. 298 static bool isPredicatedOnPHI(CallSite CS) { 299 Instruction *Instr = CS.getInstruction(); 300 BasicBlock *Parent = Instr->getParent(); 301 if (Instr != Parent->getFirstNonPHIOrDbg()) 302 return false; 303 304 for (auto &BI : *Parent) { 305 if (PHINode *PN = dyn_cast<PHINode>(&BI)) { 306 for (auto &I : CS.args()) 307 if (&*I == PN) { 308 assert(PN->getNumIncomingValues() == 2 && 309 "Unexpected number of incoming values"); 310 if (PN->getIncomingBlock(0) == PN->getIncomingBlock(1)) 311 return false; 312 if (PN->getIncomingValue(0) == PN->getIncomingValue(1)) 313 continue; 314 if (isa<Constant>(PN->getIncomingValue(0)) && 315 isa<Constant>(PN->getIncomingValue(1))) 316 return true; 317 } 318 } 319 break; 320 } 321 return false; 322 } 323 324 static bool tryToSplitOnPHIPredicatedArgument(CallSite CS) { 325 if (!isPredicatedOnPHI(CS)) 326 return false; 327 328 auto Preds = getTwoPredecessors(CS.getInstruction()->getParent()); 329 splitCallSite(CS, Preds[0], Preds[1], nullptr, nullptr); 330 return true; 331 } 332 333 static bool tryToSplitOnPredicatedArgument(CallSite CS) { 334 auto Preds = getTwoPredecessors(CS.getInstruction()->getParent()); 335 if (Preds[0] == Preds[1]) 336 return false; 337 338 SmallVector<std::pair<ICmpInst *, unsigned>, 2> C1, C2; 339 recordConditions(CS, Preds[0], C1); 340 recordConditions(CS, Preds[1], C2); 341 342 Instruction *CallInst1 = addConditions(CS, C1); 343 Instruction *CallInst2 = addConditions(CS, C2); 344 if (!CallInst1 && !CallInst2) 345 return false; 346 347 splitCallSite(CS, Preds[1], Preds[0], CallInst2, CallInst1); 348 return true; 349 } 350 351 static bool tryToSplitCallSite(CallSite CS) { 352 if (!CS.arg_size() || !canSplitCallSite(CS)) 353 return false; 354 return tryToSplitOnPredicatedArgument(CS) || 355 tryToSplitOnPHIPredicatedArgument(CS); 356 } 357 358 static bool doCallSiteSplitting(Function &F, TargetLibraryInfo &TLI) { 359 bool Changed = false; 360 for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE;) { 361 BasicBlock &BB = *BI++; 362 for (BasicBlock::iterator II = BB.begin(), IE = BB.end(); II != IE;) { 363 Instruction *I = &*II++; 364 CallSite CS(cast<Value>(I)); 365 if (!CS || isa<IntrinsicInst>(I) || isInstructionTriviallyDead(I, &TLI)) 366 continue; 367 368 Function *Callee = CS.getCalledFunction(); 369 if (!Callee || Callee->isDeclaration()) 370 continue; 371 Changed |= tryToSplitCallSite(CS); 372 } 373 } 374 return Changed; 375 } 376 377 namespace { 378 struct CallSiteSplittingLegacyPass : public FunctionPass { 379 static char ID; 380 CallSiteSplittingLegacyPass() : FunctionPass(ID) { 381 initializeCallSiteSplittingLegacyPassPass(*PassRegistry::getPassRegistry()); 382 } 383 384 void getAnalysisUsage(AnalysisUsage &AU) const override { 385 AU.addRequired<TargetLibraryInfoWrapperPass>(); 386 FunctionPass::getAnalysisUsage(AU); 387 } 388 389 bool runOnFunction(Function &F) override { 390 if (skipFunction(F)) 391 return false; 392 393 auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(); 394 return doCallSiteSplitting(F, TLI); 395 } 396 }; 397 } // namespace 398 399 char CallSiteSplittingLegacyPass::ID = 0; 400 INITIALIZE_PASS_BEGIN(CallSiteSplittingLegacyPass, "callsite-splitting", 401 "Call-site splitting", false, false) 402 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 403 INITIALIZE_PASS_END(CallSiteSplittingLegacyPass, "callsite-splitting", 404 "Call-site splitting", false, false) 405 FunctionPass *llvm::createCallSiteSplittingPass() { 406 return new CallSiteSplittingLegacyPass(); 407 } 408 409 PreservedAnalyses CallSiteSplittingPass::run(Function &F, 410 FunctionAnalysisManager &AM) { 411 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); 412 413 if (!doCallSiteSplitting(F, TLI)) 414 return PreservedAnalyses::all(); 415 PreservedAnalyses PA; 416 return PA; 417 } 418