contrib/llvm/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) 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 }