lib/Transforms/Scalar/CallSiteSplitting.cpp

   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) If a call site is dominated by an OR condition and if any of its arguments
  17 // are predicated on this OR condition, try to split the condition with more
  18 // constrained arguments. For example, in the code below, we try to split the
  19 // call site since we can predicate the argument(ptr) based on the OR condition.
  20 //
  21 // Split from :
  22 //   if (!ptr || c)
  23 //     callee(ptr);
  24 // to :
  25 //   if (!ptr)
  26 //     callee(null)         // set the known constant value
  27 //   else if (c)
  28 //     callee(nonnull ptr)  // set non-null attribute in the argument
  29 //
  30 // 2) We can also split a call-site based on constant incoming values of a PHI
  31 // For example,
  32 // from :
  33 //   Header:
  34 //    %c = icmp eq i32 %i1, %i2
  35 //    br i1 %c, label %Tail, label %TBB
  36 //   TBB:
  37 //    br label Tail%
  38 //   Tail:
  39 //    %p = phi i32 [ 0, %Header], [ 1, %TBB]
  40 //    call void @bar(i32 %p)
  41 // to
  42 //   Header:
  43 //    %c = icmp eq i32 %i1, %i2
  44 //    br i1 %c, label %Tail-split0, label %TBB
  45 //   TBB:
  46 //    br label %Tail-split1
  47 //   Tail-split0:
  48 //    call void @bar(i32 0)
  49 //    br label %Tail
  50 //   Tail-split1:
  51 //    call void @bar(i32 1)
  52 //    br label %Tail
  53 //   Tail:
  54 //    %p = phi i32 [ 0, %Tail-split0 ], [ 1, %Tail-split1 ]
  55 //
  56 //===----------------------------------------------------------------------===//
  57
  58 #include "llvm/Transforms/Scalar/CallSiteSplitting.h"
  59 #include "llvm/ADT/Statistic.h"
  60 #include "llvm/Analysis/TargetLibraryInfo.h"
  61 #include "llvm/IR/IntrinsicInst.h"
  62 #include "llvm/IR/PatternMatch.h"
  63 #include "llvm/Support/Debug.h"
  64 #include "llvm/Transforms/Scalar.h"
  65 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  66 #include "llvm/Transforms/Utils/Local.h"
  67
  68 using namespace llvm;
  69 using namespace PatternMatch;
  70
  71 #define DEBUG_TYPE "callsite-splitting"
  72
  73 STATISTIC(NumCallSiteSplit, "Number of call-site split");
  74
  75 static void addNonNullAttribute(Instruction *CallI, Instruction *&NewCallI,
  76                                 Value *Op) {
  77   if (!NewCallI)
  78     NewCallI = CallI->clone();
  79   CallSite CS(NewCallI);
  80   unsigned ArgNo = 0;
  81   for (auto &I : CS.args()) {
  82     if (&*I == Op)
  83       CS.addParamAttr(ArgNo, Attribute::NonNull);
  84     ++ArgNo;
  85   }
  86 }
  87
  88 static void setConstantInArgument(Instruction *CallI, Instruction *&NewCallI,
  89                                   Value *Op, Constant *ConstValue) {
  90   if (!NewCallI)
  91     NewCallI = CallI->clone();
  92   CallSite CS(NewCallI);
  93   unsigned ArgNo = 0;
  94   for (auto &I : CS.args()) {
  95     if (&*I == Op)
  96       CS.setArgument(ArgNo, ConstValue);
  97     ++ArgNo;
  98   }
  99 }
 100
 101 static bool createCallSitesOnOrPredicatedArgument(
 102     CallSite CS, Instruction *&NewCSTakenFromHeader,
 103     Instruction *&NewCSTakenFromNextCond,
 104     SmallVectorImpl<BranchInst *> &BranchInsts, BasicBlock *HeaderBB) {
 105   assert(BranchInsts.size() <= 2 &&
 106          "Unexpected number of blocks in the OR predicated condition");
 107   Instruction *Instr = CS.getInstruction();
 108   BasicBlock *CallSiteBB = Instr->getParent();
 109   TerminatorInst *HeaderTI = HeaderBB->getTerminator();
 110   bool IsCSInTakenPath = CallSiteBB == HeaderTI->getSuccessor(0);
 111
 112   for (unsigned I = 0, E = BranchInsts.size(); I != E; ++I) {
 113     BranchInst *PBI = BranchInsts[I];
 114     assert(isa<ICmpInst>(PBI->getCondition()) &&
 115            "Unexpected condition in a conditional branch.");
 116     ICmpInst *Cmp = cast<ICmpInst>(PBI->getCondition());
 117     Value *Arg = Cmp->getOperand(0);
 118     assert(isa<Constant>(Cmp->getOperand(1)) &&
 119            "Expected op1 to be a constant.");
 120     Constant *ConstVal = cast<Constant>(Cmp->getOperand(1));
 121     CmpInst::Predicate Pred = Cmp->getPredicate();
 122
 123     if (PBI->getParent() == HeaderBB) {
 124       Instruction *&CallTakenFromHeader =
 125           IsCSInTakenPath ? NewCSTakenFromHeader : NewCSTakenFromNextCond;
 126       Instruction *&CallUntakenFromHeader =
 127           IsCSInTakenPath ? NewCSTakenFromNextCond : NewCSTakenFromHeader;
 128
 129       assert((Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE) &&
 130              "Unexpected predicate in an OR condition");
 131
 132       // Set the constant value for agruments in the call predicated based on
 133       // the OR condition.
 134       Instruction *&CallToSetConst = Pred == ICmpInst::ICMP_EQ
 135                                          ? CallTakenFromHeader
 136                                          : CallUntakenFromHeader;
 137       setConstantInArgument(Instr, CallToSetConst, Arg, ConstVal);
 138
 139       // Add the NonNull attribute if compared with the null pointer.
 140       if (ConstVal->getType()->isPointerTy() && ConstVal->isNullValue()) {
 141         Instruction *&CallToSetAttr = Pred == ICmpInst::ICMP_EQ
 142                                           ? CallUntakenFromHeader
 143                                           : CallTakenFromHeader;
 144         addNonNullAttribute(Instr, CallToSetAttr, Arg);
 145       }
 146       continue;
 147     }
 148
 149     if (Pred == ICmpInst::ICMP_EQ) {
 150       if (PBI->getSuccessor(0) == Instr->getParent()) {
 151         // Set the constant value for the call taken from the second block in
 152         // the OR condition.
 153         setConstantInArgument(Instr, NewCSTakenFromNextCond, Arg, ConstVal);
 154       } else {
 155         // Add the NonNull attribute if compared with the null pointer for the
 156         // call taken from the second block in the OR condition.
 157         if (ConstVal->getType()->isPointerTy() && ConstVal->isNullValue())
 158           addNonNullAttribute(Instr, NewCSTakenFromNextCond, Arg);
 159       }
 160     } else {
 161       if (PBI->getSuccessor(0) == Instr->getParent()) {
 162         // Add the NonNull attribute if compared with the null pointer for the
 163         // call taken from the second block in the OR condition.
 164         if (ConstVal->getType()->isPointerTy() && ConstVal->isNullValue())
 165           addNonNullAttribute(Instr, NewCSTakenFromNextCond, Arg);
 166       } else if (Pred == ICmpInst::ICMP_NE) {
 167         // Set the constant value for the call in the untaken path from the
 168         // header block.
 169         setConstantInArgument(Instr, NewCSTakenFromNextCond, Arg, ConstVal);
 170       } else
 171         llvm_unreachable("Unexpected condition");
 172     }
 173   }
 174   return NewCSTakenFromHeader || NewCSTakenFromNextCond;
 175 }
 176
 177 static bool canSplitCallSite(CallSite CS) {
 178   // FIXME: As of now we handle only CallInst. InvokeInst could be handled
 179   // without too much effort.
 180   Instruction *Instr = CS.getInstruction();
 181   if (!isa<CallInst>(Instr))
 182     return false;
 183
 184   // Allow splitting a call-site only when there is no instruction before the
 185   // call-site in the basic block. Based on this constraint, we only clone the
 186   // call instruction, and we do not move a call-site across any other
 187   // instruction.
 188   BasicBlock *CallSiteBB = Instr->getParent();
 189   if (Instr != CallSiteBB->getFirstNonPHI())
 190     return false;
 191
 192   pred_iterator PII = pred_begin(CallSiteBB);
 193   pred_iterator PIE = pred_end(CallSiteBB);
 194   unsigned NumPreds = std::distance(PII, PIE);
 195
 196   // Allow only one extra call-site. No more than two from one call-site.
 197   if (NumPreds != 2)
 198     return false;
 199
 200   // Cannot split an edge from an IndirectBrInst.
 201   BasicBlock *Preds[2] = {*PII++, *PII};
 202   if (isa<IndirectBrInst>(Preds[0]->getTerminator()) ||
 203       isa<IndirectBrInst>(Preds[1]->getTerminator()))
 204     return false;
 205
 206   return CallSiteBB->canSplitPredecessors();
 207 }
 208
 209 /// Return true if the CS is split into its new predecessors which are directly
 210 /// hooked to each of its orignial predecessors pointed by PredBB1 and PredBB2.
 211 /// Note that PredBB1 and PredBB2 are decided in findPredicatedArgument(),
 212 /// especially for the OR predicated case where PredBB1 will point the header,
 213 /// and PredBB2 will point the the second compare block. CallInst1 and CallInst2
 214 /// will be the new call-sites placed in the new predecessors split for PredBB1
 215 /// and PredBB2, repectively. Therefore, CallInst1 will be the call-site placed
 216 /// between Header and Tail, and CallInst2 will be the call-site between TBB and
 217 /// Tail. For example, in the IR below with an OR condition, the call-site can
 218 /// be split
 219 ///
 220 /// from :
 221 ///
 222 ///   Header:
 223 ///     %c = icmp eq i32* %a, null
 224 ///     br i1 %c %Tail, %TBB
 225 ///   TBB:
 226 ///     %c2 = icmp eq i32* %b, null
 227 ///     br i1 %c %Tail, %End
 228 ///   Tail:
 229 ///     %ca = call i1  @callee (i32* %a, i32* %b)
 230 ///
 231 ///  to :
 232 ///
 233 ///   Header:                          // PredBB1 is Header
 234 ///     %c = icmp eq i32* %a, null
 235 ///     br i1 %c %Tail-split1, %TBB
 236 ///   TBB:                             // PredBB2 is TBB
 237 ///     %c2 = icmp eq i32* %b, null
 238 ///     br i1 %c %Tail-split2, %End
 239 ///   Tail-split1:
 240 ///     %ca1 = call @callee (i32* null, i32* %b)         // CallInst1
 241 ///    br %Tail
 242 ///   Tail-split2:
 243 ///     %ca2 = call @callee (i32* nonnull %a, i32* null) // CallInst2
 244 ///    br %Tail
 245 ///   Tail:
 246 ///    %p = phi i1 [%ca1, %Tail-split1],[%ca2, %Tail-split2]
 247 ///
 248 /// Note that for an OR predicated case, CallInst1 and CallInst2 should be
 249 /// created with more constrained arguments in
 250 /// createCallSitesOnOrPredicatedArgument().
 251 static void splitCallSite(CallSite CS, BasicBlock *PredBB1, BasicBlock *PredBB2,
 252                           Instruction *CallInst1, Instruction *CallInst2) {
 253   Instruction *Instr = CS.getInstruction();
 254   BasicBlock *TailBB = Instr->getParent();
 255   assert(Instr == (TailBB->getFirstNonPHI()) && "Unexpected call-site");
 256
 257   BasicBlock *SplitBlock1 =
 258       SplitBlockPredecessors(TailBB, PredBB1, ".predBB1.split");
 259   BasicBlock *SplitBlock2 =
 260       SplitBlockPredecessors(TailBB, PredBB2, ".predBB2.split");
 261
 262   assert((SplitBlock1 && SplitBlock2) && "Unexpected new basic block split.");
 263
 264   if (!CallInst1)
 265     CallInst1 = Instr->clone();
 266   if (!CallInst2)
 267     CallInst2 = Instr->clone();
 268
 269   CallInst1->insertBefore(&*SplitBlock1->getFirstInsertionPt());
 270   CallInst2->insertBefore(&*SplitBlock2->getFirstInsertionPt());
 271
 272   CallSite CS1(CallInst1);
 273   CallSite CS2(CallInst2);
 274
 275   // Handle PHIs used as arguments in the call-site.
 276   for (auto &PI : *TailBB) {
 277     PHINode *PN = dyn_cast<PHINode>(&PI);
 278     if (!PN)
 279       break;
 280     unsigned ArgNo = 0;
 281     for (auto &CI : CS.args()) {
 282       if (&*CI == PN) {
 283         CS1.setArgument(ArgNo, PN->getIncomingValueForBlock(SplitBlock1));
 284         CS2.setArgument(ArgNo, PN->getIncomingValueForBlock(SplitBlock2));
 285       }
 286       ++ArgNo;
 287     }
 288   }
 289
 290   // Replace users of the original call with a PHI mering call-sites split.
 291   if (Instr->getNumUses()) {
 292     PHINode *PN = PHINode::Create(Instr->getType(), 2, "phi.call", Instr);
 293     PN->addIncoming(CallInst1, SplitBlock1);
 294     PN->addIncoming(CallInst2, SplitBlock2);
 295     Instr->replaceAllUsesWith(PN);
 296   }
 297   DEBUG(dbgs() << "split call-site : " << *Instr << " into \n");
 298   DEBUG(dbgs() << "    " << *CallInst1 << " in " << SplitBlock1->getName()
 299                << "\n");
 300   DEBUG(dbgs() << "    " << *CallInst2 << " in " << SplitBlock2->getName()
 301                << "\n");
 302   Instr->eraseFromParent();
 303   NumCallSiteSplit++;
 304 }
 305
 306 static bool isCondRelevantToAnyCallArgument(ICmpInst *Cmp, CallSite CS) {
 307   assert(isa<Constant>(Cmp->getOperand(1)) && "Expected a constant operand.");
 308   Value *Op0 = Cmp->getOperand(0);
 309   unsigned ArgNo = 0;
 310   for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E;
 311        ++I, ++ArgNo) {
 312     // Don't consider constant or arguments that are already known non-null.
 313     if (isa<Constant>(*I) || CS.paramHasAttr(ArgNo, Attribute::NonNull))
 314       continue;
 315
 316     if (*I == Op0)
 317       return true;
 318   }
 319   return false;
 320 }
 321
 322 static void findOrCondRelevantToCallArgument(
 323     CallSite CS, BasicBlock *PredBB, BasicBlock *OtherPredBB,
 324     SmallVectorImpl<BranchInst *> &BranchInsts, BasicBlock *&HeaderBB) {
 325   auto *PBI = dyn_cast<BranchInst>(PredBB->getTerminator());
 326   if (!PBI || !PBI->isConditional())
 327     return;
 328
 329   if (PBI->getSuccessor(0) == OtherPredBB ||
 330       PBI->getSuccessor(1) == OtherPredBB)
 331     if (PredBB == OtherPredBB->getSinglePredecessor()) {
 332       assert(!HeaderBB && "Expect to find only a single header block");
 333       HeaderBB = PredBB;
 334     }
 335
 336   CmpInst::Predicate Pred;
 337   Value *Cond = PBI->getCondition();
 338   if (!match(Cond, m_ICmp(Pred, m_Value(), m_Constant())))
 339     return;
 340   ICmpInst *Cmp = cast<ICmpInst>(Cond);
 341   if (Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE)
 342     if (isCondRelevantToAnyCallArgument(Cmp, CS))
 343       BranchInsts.push_back(PBI);
 344 }
 345
 346 // Return true if the call-site has an argument which is a PHI with only
 347 // constant incoming values.
 348 static bool isPredicatedOnPHI(CallSite CS) {
 349   Instruction *Instr = CS.getInstruction();
 350   BasicBlock *Parent = Instr->getParent();
 351   if (Instr != Parent->getFirstNonPHI())
 352     return false;
 353
 354   for (auto &BI : *Parent) {
 355     if (PHINode *PN = dyn_cast<PHINode>(&BI)) {
 356       for (auto &I : CS.args())
 357         if (&*I == PN) {
 358           assert(PN->getNumIncomingValues() == 2 &&
 359                  "Unexpected number of incoming values");
 360           if (PN->getIncomingBlock(0) == PN->getIncomingBlock(1))
 361             return false;
 362           if (PN->getIncomingValue(0) == PN->getIncomingValue(1))
 363             continue;
 364           if (isa<Constant>(PN->getIncomingValue(0)) &&
 365               isa<Constant>(PN->getIncomingValue(1)))
 366             return true;
 367         }
 368     }
 369     break;
 370   }
 371   return false;
 372 }
 373
 374 // Return true if an agument in CS is predicated on an 'or' condition.
 375 // Create new call-site with arguments constrained based on the OR condition.
 376 static bool findPredicatedOnOrCondition(CallSite CS, BasicBlock *PredBB1,
 377                                         BasicBlock *PredBB2,
 378                                         Instruction *&NewCallTakenFromHeader,
 379                                         Instruction *&NewCallTakenFromNextCond,
 380                                         BasicBlock *&HeaderBB) {
 381   SmallVector<BranchInst *, 4> BranchInsts;
 382   findOrCondRelevantToCallArgument(CS, PredBB1, PredBB2, BranchInsts, HeaderBB);
 383   findOrCondRelevantToCallArgument(CS, PredBB2, PredBB1, BranchInsts, HeaderBB);
 384   if (BranchInsts.empty() || !HeaderBB)
 385     return false;
 386
 387   // If an OR condition is detected, try to create call sites with constrained
 388   // arguments (e.g., NonNull attribute or constant value).
 389   return createCallSitesOnOrPredicatedArgument(CS, NewCallTakenFromHeader,
 390                                                NewCallTakenFromNextCond,
 391                                                BranchInsts, HeaderBB);
 392 }
 393
 394 static bool findPredicatedArgument(CallSite CS, Instruction *&CallInst1,
 395                                    Instruction *&CallInst2,
 396                                    BasicBlock *&PredBB1, BasicBlock *&PredBB2) {
 397   BasicBlock *CallSiteBB = CS.getInstruction()->getParent();
 398   pred_iterator PII = pred_begin(CallSiteBB);
 399   pred_iterator PIE = pred_end(CallSiteBB);
 400   assert(std::distance(PII, PIE) == 2 && "Expect only two predecessors.");
 401   (void)PIE;
 402   BasicBlock *Preds[2] = {*PII++, *PII};
 403   BasicBlock *&HeaderBB = PredBB1;
 404   if (!findPredicatedOnOrCondition(CS, Preds[0], Preds[1], CallInst1, CallInst2,
 405                                    HeaderBB) &&
 406       !isPredicatedOnPHI(CS))
 407     return false;
 408
 409   if (!PredBB1)
 410     PredBB1 = Preds[0];
 411
 412   PredBB2 = PredBB1 == Preds[0] ? Preds[1] : Preds[0];
 413   return true;
 414 }
 415
 416 static bool tryToSplitCallSite(CallSite CS) {
 417   if (!CS.arg_size())
 418     return false;
 419
 420   BasicBlock *PredBB1 = nullptr;
 421   BasicBlock *PredBB2 = nullptr;
 422   Instruction *CallInst1 = nullptr;
 423   Instruction *CallInst2 = nullptr;
 424   if (!canSplitCallSite(CS) ||
 425       !findPredicatedArgument(CS, CallInst1, CallInst2, PredBB1, PredBB2)) {
 426     assert(!CallInst1 && !CallInst2 && "Unexpected new call-sites cloned.");
 427     return false;
 428   }
 429   splitCallSite(CS, PredBB1, PredBB2, CallInst1, CallInst2);
 430   return true;
 431 }
 432
 433 static bool doCallSiteSplitting(Function &F, TargetLibraryInfo &TLI) {
 434   bool Changed = false;
 435   for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE;) {
 436     BasicBlock &BB = *BI++;
 437     for (BasicBlock::iterator II = BB.begin(), IE = BB.end(); II != IE;) {
 438       Instruction *I = &*II++;
 439       CallSite CS(cast<Value>(I));
 440       if (!CS || isa<IntrinsicInst>(I) || isInstructionTriviallyDead(I, &TLI))
 441         continue;
 442
 443       Function *Callee = CS.getCalledFunction();
 444       if (!Callee || Callee->isDeclaration())
 445         continue;
 446       Changed |= tryToSplitCallSite(CS);
 447     }
 448   }
 449   return Changed;
 450 }
 451
 452 namespace {
 453 struct CallSiteSplittingLegacyPass : public FunctionPass {
 454   static char ID;
 455   CallSiteSplittingLegacyPass() : FunctionPass(ID) {
 456     initializeCallSiteSplittingLegacyPassPass(*PassRegistry::getPassRegistry());
 457   }
 458
 459   void getAnalysisUsage(AnalysisUsage &AU) const override {
 460     AU.addRequired<TargetLibraryInfoWrapperPass>();
 461     FunctionPass::getAnalysisUsage(AU);
 462   }
 463
 464   bool runOnFunction(Function &F) override {
 465     if (skipFunction(F))
 466       return false;
 467
 468     auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 469     return doCallSiteSplitting(F, TLI);
 470   }
 471 };
 472 } // namespace
 473
 474 char CallSiteSplittingLegacyPass::ID = 0;
 475 INITIALIZE_PASS_BEGIN(CallSiteSplittingLegacyPass, "callsite-splitting",
 476                       "Call-site splitting", false, false)
 477 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 478 INITIALIZE_PASS_END(CallSiteSplittingLegacyPass, "callsite-splitting",
 479                     "Call-site splitting", false, false)
 480 FunctionPass *llvm::createCallSiteSplittingPass() {
 481   return new CallSiteSplittingLegacyPass();
 482 }
 483
 484 PreservedAnalyses CallSiteSplittingPass::run(Function &F,
 485                                              FunctionAnalysisManager &AM) {
 486   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
 487
 488   if (!doCallSiteSplitting(F, TLI))
 489     return PreservedAnalyses::all();
 490   PreservedAnalyses PA;
 491   return PA;
 492 }