LLVM  8.0.0svn
CallSiteSplitting.cpp
Go to the documentation of this file.
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 
60 #include "llvm/ADT/Statistic.h"
64 #include "llvm/IR/IntrinsicInst.h"
65 #include "llvm/IR/PatternMatch.h"
66 #include "llvm/Support/Debug.h"
67 #include "llvm/Transforms/Scalar.h"
70 
71 using namespace llvm;
72 using namespace PatternMatch;
73 
74 #define DEBUG_TYPE "callsite-splitting"
75 
76 STATISTIC(NumCallSiteSplit, "Number of call-site split");
77 
78 /// Only allow instructions before a call, if their CodeSize cost is below
79 /// DuplicationThreshold. Those instructions need to be duplicated in all
80 /// split blocks.
81 static cl::opt<unsigned>
82  DuplicationThreshold("callsite-splitting-duplication-threshold", cl::Hidden,
83  cl::desc("Only allow instructions before a call, if "
84  "their cost is below DuplicationThreshold"),
85  cl::init(5));
86 
87 static void addNonNullAttribute(CallSite CS, Value *Op) {
88  unsigned ArgNo = 0;
89  for (auto &I : CS.args()) {
90  if (&*I == Op)
91  CS.addParamAttr(ArgNo, Attribute::NonNull);
92  ++ArgNo;
93  }
94 }
95 
97  Constant *ConstValue) {
98  unsigned ArgNo = 0;
99  for (auto &I : CS.args()) {
100  if (&*I == Op) {
101  // It is possible we have already added the non-null attribute to the
102  // parameter by using an earlier constraining condition.
103  CS.removeParamAttr(ArgNo, Attribute::NonNull);
104  CS.setArgument(ArgNo, ConstValue);
105  }
106  ++ArgNo;
107  }
108 }
109 
111  assert(isa<Constant>(Cmp->getOperand(1)) && "Expected a constant operand.");
112  Value *Op0 = Cmp->getOperand(0);
113  unsigned ArgNo = 0;
114  for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E;
115  ++I, ++ArgNo) {
116  // Don't consider constant or arguments that are already known non-null.
117  if (isa<Constant>(*I) || CS.paramHasAttr(ArgNo, Attribute::NonNull))
118  continue;
119 
120  if (*I == Op0)
121  return true;
122  }
123  return false;
124 }
125 
126 typedef std::pair<ICmpInst *, unsigned> ConditionTy;
128 
129 /// If From has a conditional jump to To, add the condition to Conditions,
130 /// if it is relevant to any argument at CS.
132  ConditionsTy &Conditions) {
133  auto *BI = dyn_cast<BranchInst>(From->getTerminator());
134  if (!BI || !BI->isConditional())
135  return;
136 
137  CmpInst::Predicate Pred;
138  Value *Cond = BI->getCondition();
139  if (!match(Cond, m_ICmp(Pred, m_Value(), m_Constant())))
140  return;
141 
142  ICmpInst *Cmp = cast<ICmpInst>(Cond);
143  if (Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE)
144  if (isCondRelevantToAnyCallArgument(Cmp, CS))
145  Conditions.push_back({Cmp, From->getTerminator()->getSuccessor(0) == To
146  ? Pred
147  : Cmp->getInversePredicate()});
148 }
149 
150 /// Record ICmp conditions relevant to any argument in CS following Pred's
151 /// single predecessors. If there are conflicting conditions along a path, like
152 /// x == 1 and x == 0, the first condition will be used. We stop once we reach
153 /// an edge to StopAt.
154 static void recordConditions(CallSite CS, BasicBlock *Pred,
155  ConditionsTy &Conditions, BasicBlock *StopAt) {
156  BasicBlock *From = Pred;
157  BasicBlock *To = Pred;
159  while (To != StopAt && !Visited.count(From->getSinglePredecessor()) &&
160  (From = From->getSinglePredecessor())) {
161  recordCondition(CS, From, To, Conditions);
162  Visited.insert(From);
163  To = From;
164  }
165 }
166 
167 static void addConditions(CallSite CS, const ConditionsTy &Conditions) {
168  for (auto &Cond : Conditions) {
169  Value *Arg = Cond.first->getOperand(0);
170  Constant *ConstVal = cast<Constant>(Cond.first->getOperand(1));
171  if (Cond.second == ICmpInst::ICMP_EQ)
172  setConstantInArgument(CS, Arg, ConstVal);
173  else if (ConstVal->getType()->isPointerTy() && ConstVal->isNullValue()) {
174  assert(Cond.second == ICmpInst::ICMP_NE);
175  addNonNullAttribute(CS, Arg);
176  }
177  }
178 }
179 
182  assert(Preds.size() == 2 && "Expected exactly 2 predecessors!");
183  return Preds;
184 }
185 
187  // FIXME: As of now we handle only CallInst. InvokeInst could be handled
188  // without too much effort.
189  Instruction *Instr = CS.getInstruction();
190  if (!isa<CallInst>(Instr))
191  return false;
192 
193  BasicBlock *CallSiteBB = Instr->getParent();
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  // BasicBlock::canSplitPredecessors is more aggressive, so checking for
201  // BasicBlock::isEHPad as well.
202  if (!CallSiteBB->canSplitPredecessors() || CallSiteBB->isEHPad())
203  return false;
204 
205  // Allow splitting a call-site only when the CodeSize cost of the
206  // instructions before the call is less then DuplicationThreshold. The
207  // instructions before the call will be duplicated in the split blocks and
208  // corresponding uses will be updated.
209  unsigned Cost = 0;
210  for (auto &InstBeforeCall :
211  llvm::make_range(CallSiteBB->begin(), Instr->getIterator())) {
212  Cost += TTI.getInstructionCost(&InstBeforeCall,
214  if (Cost >= DuplicationThreshold)
215  return false;
216  }
217 
218  return true;
219 }
220 
222  Value *V) {
223  Instruction *Copy = I->clone();
224  Copy->setName(I->getName());
225  Copy->insertBefore(Before);
226  if (V)
227  Copy->setOperand(0, V);
228  return Copy;
229 }
230 
231 /// Copy mandatory `musttail` return sequence that follows original `CI`, and
232 /// link it up to `NewCI` value instead:
233 ///
234 /// * (optional) `bitcast NewCI to ...`
235 /// * `ret bitcast or NewCI`
236 ///
237 /// Insert this sequence right before `SplitBB`'s terminator, which will be
238 /// cleaned up later in `splitCallSite` below.
239 static void copyMustTailReturn(BasicBlock *SplitBB, Instruction *CI,
240  Instruction *NewCI) {
241  bool IsVoid = SplitBB->getParent()->getReturnType()->isVoidTy();
242  auto II = std::next(CI->getIterator());
243 
244  BitCastInst* BCI = dyn_cast<BitCastInst>(&*II);
245  if (BCI)
246  ++II;
247 
248  ReturnInst* RI = dyn_cast<ReturnInst>(&*II);
249  assert(RI && "`musttail` call must be followed by `ret` instruction");
250 
251  Instruction *TI = SplitBB->getTerminator();
252  Value *V = NewCI;
253  if (BCI)
254  V = cloneInstForMustTail(BCI, TI, V);
255  cloneInstForMustTail(RI, TI, IsVoid ? nullptr : V);
256 
257  // FIXME: remove TI here, `DuplicateInstructionsInSplitBetween` has a bug
258  // that prevents doing this now.
259 }
260 
261 /// For each (predecessor, conditions from predecessors) pair, it will split the
262 /// basic block containing the call site, hook it up to the predecessor and
263 /// replace the call instruction with new call instructions, which contain
264 /// constraints based on the conditions from their predecessors.
265 /// For example, in the IR below with an OR condition, the call-site can
266 /// be split. In this case, Preds for Tail is [(Header, a == null),
267 /// (TBB, a != null, b == null)]. Tail is replaced by 2 split blocks, containing
268 /// CallInst1, which has constraints based on the conditions from Head and
269 /// CallInst2, which has constraints based on the conditions coming from TBB.
270 ///
271 /// From :
272 ///
273 /// Header:
274 /// %c = icmp eq i32* %a, null
275 /// br i1 %c %Tail, %TBB
276 /// TBB:
277 /// %c2 = icmp eq i32* %b, null
278 /// br i1 %c %Tail, %End
279 /// Tail:
280 /// %ca = call i1 @callee (i32* %a, i32* %b)
281 ///
282 /// to :
283 ///
284 /// Header: // PredBB1 is Header
285 /// %c = icmp eq i32* %a, null
286 /// br i1 %c %Tail-split1, %TBB
287 /// TBB: // PredBB2 is TBB
288 /// %c2 = icmp eq i32* %b, null
289 /// br i1 %c %Tail-split2, %End
290 /// Tail-split1:
291 /// %ca1 = call @callee (i32* null, i32* %b) // CallInst1
292 /// br %Tail
293 /// Tail-split2:
294 /// %ca2 = call @callee (i32* nonnull %a, i32* null) // CallInst2
295 /// br %Tail
296 /// Tail:
297 /// %p = phi i1 [%ca1, %Tail-split1],[%ca2, %Tail-split2]
298 ///
299 /// Note that in case any arguments at the call-site are constrained by its
300 /// predecessors, new call-sites with more constrained arguments will be
301 /// created in createCallSitesOnPredicatedArgument().
302 static void splitCallSite(
303  CallSite CS,
304  const SmallVectorImpl<std::pair<BasicBlock *, ConditionsTy>> &Preds,
305  DomTreeUpdater &DTU) {
306  Instruction *Instr = CS.getInstruction();
307  BasicBlock *TailBB = Instr->getParent();
308  bool IsMustTailCall = CS.isMustTailCall();
309 
310  PHINode *CallPN = nullptr;
311 
312  // `musttail` calls must be followed by optional `bitcast`, and `ret`. The
313  // split blocks will be terminated right after that so there're no users for
314  // this phi in a `TailBB`.
315  if (!IsMustTailCall && !Instr->use_empty()) {
316  CallPN = PHINode::Create(Instr->getType(), Preds.size(), "phi.call");
317  CallPN->setDebugLoc(Instr->getDebugLoc());
318  }
319 
320  LLVM_DEBUG(dbgs() << "split call-site : " << *Instr << " into \n");
321 
322  assert(Preds.size() == 2 && "The ValueToValueMaps array has size 2.");
323  // ValueToValueMapTy is neither copy nor moveable, so we use a simple array
324  // here.
325  ValueToValueMapTy ValueToValueMaps[2];
326  for (unsigned i = 0; i < Preds.size(); i++) {
327  BasicBlock *PredBB = Preds[i].first;
329  TailBB, PredBB, &*std::next(Instr->getIterator()), ValueToValueMaps[i],
330  DTU);
331  assert(SplitBlock && "Unexpected new basic block split.");
332 
333  Instruction *NewCI =
334  &*std::prev(SplitBlock->getTerminator()->getIterator());
335  CallSite NewCS(NewCI);
336  addConditions(NewCS, Preds[i].second);
337 
338  // Handle PHIs used as arguments in the call-site.
339  for (PHINode &PN : TailBB->phis()) {
340  unsigned ArgNo = 0;
341  for (auto &CI : CS.args()) {
342  if (&*CI == &PN) {
343  NewCS.setArgument(ArgNo, PN.getIncomingValueForBlock(SplitBlock));
344  }
345  ++ArgNo;
346  }
347  }
348  LLVM_DEBUG(dbgs() << " " << *NewCI << " in " << SplitBlock->getName()
349  << "\n");
350  if (CallPN)
351  CallPN->addIncoming(NewCI, SplitBlock);
352 
353  // Clone and place bitcast and return instructions before `TI`
354  if (IsMustTailCall)
355  copyMustTailReturn(SplitBlock, Instr, NewCI);
356  }
357 
358  NumCallSiteSplit++;
359 
360  // FIXME: remove TI in `copyMustTailReturn`
361  if (IsMustTailCall) {
362  // Remove superfluous `br` terminators from the end of the Split blocks
363  // NOTE: Removing terminator removes the SplitBlock from the TailBB's
364  // predecessors. Therefore we must get complete list of Splits before
365  // attempting removal.
366  SmallVector<BasicBlock *, 2> Splits(predecessors((TailBB)));
367  assert(Splits.size() == 2 && "Expected exactly 2 splits!");
368  for (unsigned i = 0; i < Splits.size(); i++) {
369  Splits[i]->getTerminator()->eraseFromParent();
370  DTU.deleteEdge(Splits[i], TailBB);
371  }
372 
373  // Erase the tail block once done with musttail patching
374  DTU.deleteBB(TailBB);
375  return;
376  }
377 
378  auto *OriginalBegin = &*TailBB->begin();
379  // Replace users of the original call with a PHI mering call-sites split.
380  if (CallPN) {
381  CallPN->insertBefore(OriginalBegin);
382  Instr->replaceAllUsesWith(CallPN);
383  }
384 
385  // Remove instructions moved to split blocks from TailBB, from the duplicated
386  // call instruction to the beginning of the basic block. If an instruction
387  // has any uses, add a new PHI node to combine the values coming from the
388  // split blocks. The new PHI nodes are placed before the first original
389  // instruction, so we do not end up deleting them. By using reverse-order, we
390  // do not introduce unnecessary PHI nodes for def-use chains from the call
391  // instruction to the beginning of the block.
392  auto I = Instr->getReverseIterator();
393  while (I != TailBB->rend()) {
394  Instruction *CurrentI = &*I++;
395  if (!CurrentI->use_empty()) {
396  // If an existing PHI has users after the call, there is no need to create
397  // a new one.
398  if (isa<PHINode>(CurrentI))
399  continue;
400  PHINode *NewPN = PHINode::Create(CurrentI->getType(), Preds.size());
401  NewPN->setDebugLoc(CurrentI->getDebugLoc());
402  for (auto &Mapping : ValueToValueMaps)
403  NewPN->addIncoming(Mapping[CurrentI],
404  cast<Instruction>(Mapping[CurrentI])->getParent());
405  NewPN->insertBefore(&*TailBB->begin());
406  CurrentI->replaceAllUsesWith(NewPN);
407  }
408  CurrentI->eraseFromParent();
409  // We are done once we handled the first original instruction in TailBB.
410  if (CurrentI == OriginalBegin)
411  break;
412  }
413 }
414 
415 // Return true if the call-site has an argument which is a PHI with only
416 // constant incoming values.
417 static bool isPredicatedOnPHI(CallSite CS) {
418  Instruction *Instr = CS.getInstruction();
419  BasicBlock *Parent = Instr->getParent();
420  if (Instr != Parent->getFirstNonPHIOrDbg())
421  return false;
422 
423  for (auto &BI : *Parent) {
424  if (PHINode *PN = dyn_cast<PHINode>(&BI)) {
425  for (auto &I : CS.args())
426  if (&*I == PN) {
427  assert(PN->getNumIncomingValues() == 2 &&
428  "Unexpected number of incoming values");
429  if (PN->getIncomingBlock(0) == PN->getIncomingBlock(1))
430  return false;
431  if (PN->getIncomingValue(0) == PN->getIncomingValue(1))
432  continue;
433  if (isa<Constant>(PN->getIncomingValue(0)) &&
434  isa<Constant>(PN->getIncomingValue(1)))
435  return true;
436  }
437  }
438  break;
439  }
440  return false;
441 }
442 
444 
445 // Check if any of the arguments in CS are predicated on a PHI node and return
446 // the set of predecessors we should use for splitting.
448  if (!isPredicatedOnPHI(CS))
449  return {};
450 
451  auto Preds = getTwoPredecessors(CS.getInstruction()->getParent());
452  return {{Preds[0], {}}, {Preds[1], {}}};
453 }
454 
455 // Checks if any of the arguments in CS are predicated in a predecessor and
456 // returns a list of predecessors with the conditions that hold on their edges
457 // to CS.
459  DomTreeUpdater &DTU) {
460  auto Preds = getTwoPredecessors(CS.getInstruction()->getParent());
461  if (Preds[0] == Preds[1])
462  return {};
463 
464  // We can stop recording conditions once we reached the immediate dominator
465  // for the block containing the call site. Conditions in predecessors of the
466  // that node will be the same for all paths to the call site and splitting
467  // is not beneficial.
468  assert(DTU.hasDomTree() && "We need a DTU with a valid DT!");
469  auto *CSDTNode = DTU.getDomTree().getNode(CS.getInstruction()->getParent());
470  BasicBlock *StopAt = CSDTNode ? CSDTNode->getIDom()->getBlock() : nullptr;
471 
473  for (auto *Pred : make_range(Preds.rbegin(), Preds.rend())) {
474  ConditionsTy Conditions;
475  // Record condition on edge BB(CS) <- Pred
476  recordCondition(CS, Pred, CS.getInstruction()->getParent(), Conditions);
477  // Record conditions following Pred's single predecessors.
478  recordConditions(CS, Pred, Conditions, StopAt);
479  PredsCS.push_back({Pred, Conditions});
480  }
481 
482  if (all_of(PredsCS, [](const std::pair<BasicBlock *, ConditionsTy> &P) {
483  return P.second.empty();
484  }))
485  return {};
486 
487  return PredsCS;
488 }
489 
491  DomTreeUpdater &DTU) {
492  // Check if we can split the call site.
493  if (!CS.arg_size() || !canSplitCallSite(CS, TTI))
494  return false;
495 
496  auto PredsWithConds = shouldSplitOnPredicatedArgument(CS, DTU);
497  if (PredsWithConds.empty())
498  PredsWithConds = shouldSplitOnPHIPredicatedArgument(CS);
499  if (PredsWithConds.empty())
500  return false;
501 
502  splitCallSite(CS, PredsWithConds, DTU);
503  return true;
504 }
505 
508 
510  bool Changed = false;
511  for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE;) {
512  BasicBlock &BB = *BI++;
513  auto II = BB.getFirstNonPHIOrDbg()->getIterator();
514  auto IE = BB.getTerminator()->getIterator();
515  // Iterate until we reach the terminator instruction. tryToSplitCallSite
516  // can replace BB's terminator in case BB is a successor of itself. In that
517  // case, IE will be invalidated and we also have to check the current
518  // terminator.
519  while (II != IE && &*II != BB.getTerminator()) {
520  Instruction *I = &*II++;
521  CallSite CS(cast<Value>(I));
522  if (!CS || isa<IntrinsicInst>(I) || isInstructionTriviallyDead(I, &TLI))
523  continue;
524 
526  if (!Callee || Callee->isDeclaration())
527  continue;
528 
529  // Successful musttail call-site splits result in erased CI and erased BB.
530  // Check if such path is possible before attempting the splitting.
531  bool IsMustTail = CS.isMustTailCall();
532 
533  Changed |= tryToSplitCallSite(CS, TTI, DTU);
534 
535  // There're no interesting instructions after this. The call site
536  // itself might have been erased on splitting.
537  if (IsMustTail)
538  break;
539  }
540  }
541  return Changed;
542 }
543 
544 namespace {
545 struct CallSiteSplittingLegacyPass : public FunctionPass {
546  static char ID;
547  CallSiteSplittingLegacyPass() : FunctionPass(ID) {
549  }
550 
551  void getAnalysisUsage(AnalysisUsage &AU) const override {
557  }
558 
559  bool runOnFunction(Function &F) override {
560  if (skipFunction(F))
561  return false;
562 
563  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
564  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
565  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
566  return doCallSiteSplitting(F, TLI, TTI, DT);
567  }
568 };
569 } // namespace
570 
572 INITIALIZE_PASS_BEGIN(CallSiteSplittingLegacyPass, "callsite-splitting",
573  "Call-site splitting", false, false)
577 INITIALIZE_PASS_END(CallSiteSplittingLegacyPass, "callsite-splitting",
578  "Call-site splitting", false, false)
580  return new CallSiteSplittingLegacyPass();
581 }
582 
585  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
586  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
587  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
588 
589  if (!doCallSiteSplitting(F, TLI, TTI, DT))
590  return PreservedAnalyses::all();
593  return PA;
594 }
Return a value (possibly void), from a function.
User::op_iterator arg_iterator
The type of iterator to use when looping over actual arguments at this call site. ...
Definition: CallSite.h:213
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:68
bool canSplitPredecessors() const
Definition: BasicBlock.cpp:374
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:72
static bool canSplitCallSite(CallSite CS, TargetTransformInfo &TTI)
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
unsigned arg_size() const
Definition: CallSite.h:219
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...
static PredsWithCondsTy shouldSplitOnPHIPredicatedArgument(CallSite CS)
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:770
This class represents lattice values for constants.
Definition: AllocatorList.h:24
static bool tryToSplitCallSite(CallSite CS, TargetTransformInfo &TTI, DomTreeUpdater &DTU)
iterator end()
Definition: Function.h:658
SmallVector< ConditionTy, 2 > ConditionsTy
void push_back(const T &Elt)
Definition: SmallVector.h:218
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:91
iterator_range< IterTy > args() const
Definition: CallSite.h:215
Analysis pass providing the TargetTransformInfo.
unsigned second
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1176
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:231
F(f)
reverse_iterator rend()
Definition: BasicBlock.h:276
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...
Definition: BasicBlock.cpp:138
static void recordConditions(CallSite CS, BasicBlock *Pred, ConditionsTy &Conditions, BasicBlock *StopAt)
Record ICmp conditions relevant to any argument in CS following Pred&#39;s single predecessors.
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...
int getInstructionCost(const Instruction *I, enum TargetCostKind kind) const
Query the cost of a specified instruction.
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:269
INITIALIZE_PASS_BEGIN(CallSiteSplittingLegacyPass, "callsite-splitting", "Call-site splitting", false, false) INITIALIZE_PASS_END(CallSiteSplittingLegacyPass
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
static void splitCallSite(CallSite CS, const SmallVectorImpl< std::pair< BasicBlock *, ConditionsTy >> &Preds, DomTreeUpdater &DTU)
For each (predecessor, conditions from predecessors) pair, it will split the basic block containing t...
IterTy arg_end() const
Definition: CallSite.h:575
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
void initializeCallSiteSplittingLegacyPassPass(PassRegistry &)
InstrTy * getInstruction() const
Definition: CallSite.h:92
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:286
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.
void setArgument(unsigned ArgNo, Value *newVal)
Definition: CallSite.h:191
Instruction * clone() const
Create a copy of &#39;this&#39; instruction that is identical in all ways except the following: ...
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
Definition: Constants.cpp:85
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:92
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
This class represents a no-op cast from one type to another.
bool paramHasAttr(unsigned ArgNo, Attribute::AttrKind Kind) const
Return true if the call or the callee has the given attribute.
Definition: CallSite.h:377
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:430
iterator begin()
Definition: Function.h:656
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
amdgpu Simplify well known AMD library false Value * Callee
Value * getOperand(unsigned i) const
Definition: User.h:170
bool isVoidTy() const
Return true if this is &#39;void&#39;.
Definition: Type.h:141
static bool runOnFunction(Function &F, bool PostInlining)
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:419
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:169
Wrapper pass for TargetTransformInfo.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:308
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:236
static void addNonNullAttribute(CallSite CS, Value *Op)
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction...
Definition: Instruction.cpp:74
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
Conditional or Unconditional Branch instruction.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:42
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:224
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
void removeParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
Definition: CallSite.h:357
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Represent the analysis usage information of a pass.
This instruction compares its operands according to the predicate given to the constructor.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:642
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
self_iterator getIterator()
Definition: ilist_node.h:82
static void setConstantInArgument(CallSite CS, Value *Op, Constant *ConstValue)
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
size_t size() const
Definition: SmallVector.h:53
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
static bool doCallSiteSplitting(Function &F, TargetLibraryInfo &TLI, TargetTransformInfo &TTI, DominatorTree &DT)
void deleteEdge(BasicBlock *From, BasicBlock *To)
Notify all available trees on an edge deletion.
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
std::pair< ICmpInst *, unsigned > ConditionTy
Iterator for intrusive lists based on ilist_node.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
BlockVerifier::State From
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
IterTy arg_begin() const
Definition: CallSite.h:571
static void recordCondition(CallSite CS, 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...
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
Provides information about what library functions are available for the current target.
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...
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:125
void setOperand(unsigned i, Value *Val)
Definition: User.h:175
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
static bool isCondRelevantToAnyCallArgument(ICmpInst *Cmp, CallSite CS)
amdgpu Simplify well known AMD library false Value Value * Arg
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:311
reverse_self_iterator getReverseIterator()
Definition: ilist_node.h:85
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:215
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
#define I(x, y, z)
Definition: MD5.cpp:58
static Instruction * cloneInstForMustTail(Instruction *I, Instruction *Before, Value *V)
callsite splitting
static bool isPredicatedOnPHI(CallSite CS)
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
static SmallVector< BasicBlock *, 2 > getTwoPredecessors(BasicBlock *BB)
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:175
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:325
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:206
FunTy * getCalledFunction() const
Return the function being called if this is a direct call, otherwise return null (if it&#39;s an indirect...
Definition: CallSite.h:107
Analysis pass providing the TargetLibraryInfo.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:399
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction has no side ef...
Definition: Local.cpp:348
LLVM Value Representation.
Definition: Value.h:73
static void addConditions(CallSite CS, const ConditionsTy &Conditions)
static const Function * getParent(const Value *V)
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Split the specified block at the specified instruction - everything before SplitPt stays in Old and e...
A container for analyses that lazily runs them and caches their results.
const Instruction * getFirstNonPHIOrDbg() const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic...
Definition: BasicBlock.cpp:197
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:260
bool hasDomTree() const
Returns true if it holds a DominatorTree.
This pass exposes codegen information to IR-level passes.
#define LLVM_DEBUG(X)
Definition: Debug.h:123
bool isMustTailCall() const
Tests if this call site must be tail call optimized.
Definition: CallSite.h:271
bool use_empty() const
Definition: Value.h:323
void addParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
Definition: CallSite.h:345
const BasicBlock * getParent() const
Definition: Instruction.h:67
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
static PredsWithCondsTy shouldSplitOnPredicatedArgument(CallSite CS, DomTreeUpdater &DTU)
FunctionPass * createCallSiteSplittingPass()