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