LLVM  9.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  // FIXME: As of now we handle only CallInst. InvokeInst could be handled
187  // without too much effort.
188  Instruction *Instr = CS.getInstruction();
189  if (!isa<CallInst>(Instr))
190  return false;
191 
192  BasicBlock *CallSiteBB = Instr->getParent();
193  // Need 2 predecessors and cannot split an edge from an IndirectBrInst.
194  SmallVector<BasicBlock *, 2> Preds(predecessors(CallSiteBB));
195  if (Preds.size() != 2 || isa<IndirectBrInst>(Preds[0]->getTerminator()) ||
196  isa<IndirectBrInst>(Preds[1]->getTerminator()))
197  return false;
198 
199  // BasicBlock::canSplitPredecessors is more aggressive, so checking for
200  // BasicBlock::isEHPad as well.
201  if (!CallSiteBB->canSplitPredecessors() || CallSiteBB->isEHPad())
202  return false;
203 
204  // Allow splitting a call-site only when the CodeSize cost of the
205  // instructions before the call is less then DuplicationThreshold. The
206  // instructions before the call will be duplicated in the split blocks and
207  // corresponding uses will be updated.
208  unsigned Cost = 0;
209  for (auto &InstBeforeCall :
210  llvm::make_range(CallSiteBB->begin(), Instr->getIterator())) {
211  Cost += TTI.getInstructionCost(&InstBeforeCall,
213  if (Cost >= DuplicationThreshold)
214  return false;
215  }
216 
217  return true;
218 }
219 
221  Value *V) {
222  Instruction *Copy = I->clone();
223  Copy->setName(I->getName());
224  Copy->insertBefore(Before);
225  if (V)
226  Copy->setOperand(0, V);
227  return Copy;
228 }
229 
230 /// Copy mandatory `musttail` return sequence that follows original `CI`, and
231 /// link it up to `NewCI` value instead:
232 ///
233 /// * (optional) `bitcast NewCI to ...`
234 /// * `ret bitcast or NewCI`
235 ///
236 /// Insert this sequence right before `SplitBB`'s terminator, which will be
237 /// cleaned up later in `splitCallSite` below.
238 static void copyMustTailReturn(BasicBlock *SplitBB, Instruction *CI,
239  Instruction *NewCI) {
240  bool IsVoid = SplitBB->getParent()->getReturnType()->isVoidTy();
241  auto II = std::next(CI->getIterator());
242 
243  BitCastInst* BCI = dyn_cast<BitCastInst>(&*II);
244  if (BCI)
245  ++II;
246 
247  ReturnInst* RI = dyn_cast<ReturnInst>(&*II);
248  assert(RI && "`musttail` call must be followed by `ret` instruction");
249 
250  Instruction *TI = SplitBB->getTerminator();
251  Value *V = NewCI;
252  if (BCI)
253  V = cloneInstForMustTail(BCI, TI, V);
254  cloneInstForMustTail(RI, TI, IsVoid ? nullptr : V);
255 
256  // FIXME: remove TI here, `DuplicateInstructionsInSplitBetween` has a bug
257  // that prevents doing this now.
258 }
259 
260 /// For each (predecessor, conditions from predecessors) pair, it will split the
261 /// basic block containing the call site, hook it up to the predecessor and
262 /// replace the call instruction with new call instructions, which contain
263 /// constraints based on the conditions from their predecessors.
264 /// For example, in the IR below with an OR condition, the call-site can
265 /// be split. In this case, Preds for Tail is [(Header, a == null),
266 /// (TBB, a != null, b == null)]. Tail is replaced by 2 split blocks, containing
267 /// CallInst1, which has constraints based on the conditions from Head and
268 /// CallInst2, which has constraints based on the conditions coming from TBB.
269 ///
270 /// From :
271 ///
272 /// Header:
273 /// %c = icmp eq i32* %a, null
274 /// br i1 %c %Tail, %TBB
275 /// TBB:
276 /// %c2 = icmp eq i32* %b, null
277 /// br i1 %c %Tail, %End
278 /// Tail:
279 /// %ca = call i1 @callee (i32* %a, i32* %b)
280 ///
281 /// to :
282 ///
283 /// Header: // PredBB1 is Header
284 /// %c = icmp eq i32* %a, null
285 /// br i1 %c %Tail-split1, %TBB
286 /// TBB: // PredBB2 is TBB
287 /// %c2 = icmp eq i32* %b, null
288 /// br i1 %c %Tail-split2, %End
289 /// Tail-split1:
290 /// %ca1 = call @callee (i32* null, i32* %b) // CallInst1
291 /// br %Tail
292 /// Tail-split2:
293 /// %ca2 = call @callee (i32* nonnull %a, i32* null) // CallInst2
294 /// br %Tail
295 /// Tail:
296 /// %p = phi i1 [%ca1, %Tail-split1],[%ca2, %Tail-split2]
297 ///
298 /// Note that in case any arguments at the call-site are constrained by its
299 /// predecessors, new call-sites with more constrained arguments will be
300 /// created in createCallSitesOnPredicatedArgument().
301 static void splitCallSite(
302  CallSite CS,
303  const SmallVectorImpl<std::pair<BasicBlock *, ConditionsTy>> &Preds,
304  DomTreeUpdater &DTU) {
305  Instruction *Instr = CS.getInstruction();
306  BasicBlock *TailBB = Instr->getParent();
307  bool IsMustTailCall = CS.isMustTailCall();
308 
309  PHINode *CallPN = nullptr;
310 
311  // `musttail` calls must be followed by optional `bitcast`, and `ret`. The
312  // split blocks will be terminated right after that so there're no users for
313  // this phi in a `TailBB`.
314  if (!IsMustTailCall && !Instr->use_empty()) {
315  CallPN = PHINode::Create(Instr->getType(), Preds.size(), "phi.call");
316  CallPN->setDebugLoc(Instr->getDebugLoc());
317  }
318 
319  LLVM_DEBUG(dbgs() << "split call-site : " << *Instr << " into \n");
320 
321  assert(Preds.size() == 2 && "The ValueToValueMaps array has size 2.");
322  // ValueToValueMapTy is neither copy nor moveable, so we use a simple array
323  // here.
324  ValueToValueMapTy ValueToValueMaps[2];
325  for (unsigned i = 0; i < Preds.size(); i++) {
326  BasicBlock *PredBB = Preds[i].first;
328  TailBB, PredBB, &*std::next(Instr->getIterator()), ValueToValueMaps[i],
329  DTU);
330  assert(SplitBlock && "Unexpected new basic block split.");
331 
332  Instruction *NewCI =
333  &*std::prev(SplitBlock->getTerminator()->getIterator());
334  CallSite NewCS(NewCI);
335  addConditions(NewCS, Preds[i].second);
336 
337  // Handle PHIs used as arguments in the call-site.
338  for (PHINode &PN : TailBB->phis()) {
339  unsigned ArgNo = 0;
340  for (auto &CI : CS.args()) {
341  if (&*CI == &PN) {
342  NewCS.setArgument(ArgNo, PN.getIncomingValueForBlock(SplitBlock));
343  }
344  ++ArgNo;
345  }
346  }
347  LLVM_DEBUG(dbgs() << " " << *NewCI << " in " << SplitBlock->getName()
348  << "\n");
349  if (CallPN)
350  CallPN->addIncoming(NewCI, SplitBlock);
351 
352  // Clone and place bitcast and return instructions before `TI`
353  if (IsMustTailCall)
354  copyMustTailReturn(SplitBlock, Instr, NewCI);
355  }
356 
357  NumCallSiteSplit++;
358 
359  // FIXME: remove TI in `copyMustTailReturn`
360  if (IsMustTailCall) {
361  // Remove superfluous `br` terminators from the end of the Split blocks
362  // NOTE: Removing terminator removes the SplitBlock from the TailBB's
363  // predecessors. Therefore we must get complete list of Splits before
364  // attempting removal.
365  SmallVector<BasicBlock *, 2> Splits(predecessors((TailBB)));
366  assert(Splits.size() == 2 && "Expected exactly 2 splits!");
367  for (unsigned i = 0; i < Splits.size(); i++) {
368  Splits[i]->getTerminator()->eraseFromParent();
369  DTU.applyUpdatesPermissive({{DominatorTree::Delete, Splits[i], TailBB}});
370  }
371 
372  // Erase the tail block once done with musttail patching
373  DTU.deleteBB(TailBB);
374  return;
375  }
376 
377  auto *OriginalBegin = &*TailBB->begin();
378  // Replace users of the original call with a PHI mering call-sites split.
379  if (CallPN) {
380  CallPN->insertBefore(OriginalBegin);
381  Instr->replaceAllUsesWith(CallPN);
382  }
383 
384  // Remove instructions moved to split blocks from TailBB, from the duplicated
385  // call instruction to the beginning of the basic block. If an instruction
386  // has any uses, add a new PHI node to combine the values coming from the
387  // split blocks. The new PHI nodes are placed before the first original
388  // instruction, so we do not end up deleting them. By using reverse-order, we
389  // do not introduce unnecessary PHI nodes for def-use chains from the call
390  // instruction to the beginning of the block.
391  auto I = Instr->getReverseIterator();
392  while (I != TailBB->rend()) {
393  Instruction *CurrentI = &*I++;
394  if (!CurrentI->use_empty()) {
395  // If an existing PHI has users after the call, there is no need to create
396  // a new one.
397  if (isa<PHINode>(CurrentI))
398  continue;
399  PHINode *NewPN = PHINode::Create(CurrentI->getType(), Preds.size());
400  NewPN->setDebugLoc(CurrentI->getDebugLoc());
401  for (auto &Mapping : ValueToValueMaps)
402  NewPN->addIncoming(Mapping[CurrentI],
403  cast<Instruction>(Mapping[CurrentI])->getParent());
404  NewPN->insertBefore(&*TailBB->begin());
405  CurrentI->replaceAllUsesWith(NewPN);
406  }
407  CurrentI->eraseFromParent();
408  // We are done once we handled the first original instruction in TailBB.
409  if (CurrentI == OriginalBegin)
410  break;
411  }
412 }
413 
414 // Return true if the call-site has an argument which is a PHI with only
415 // constant incoming values.
416 static bool isPredicatedOnPHI(CallSite CS) {
417  Instruction *Instr = CS.getInstruction();
418  BasicBlock *Parent = Instr->getParent();
419  if (Instr != Parent->getFirstNonPHIOrDbg())
420  return false;
421 
422  for (auto &BI : *Parent) {
423  if (PHINode *PN = dyn_cast<PHINode>(&BI)) {
424  for (auto &I : CS.args())
425  if (&*I == PN) {
426  assert(PN->getNumIncomingValues() == 2 &&
427  "Unexpected number of incoming values");
428  if (PN->getIncomingBlock(0) == PN->getIncomingBlock(1))
429  return false;
430  if (PN->getIncomingValue(0) == PN->getIncomingValue(1))
431  continue;
432  if (isa<Constant>(PN->getIncomingValue(0)) &&
433  isa<Constant>(PN->getIncomingValue(1)))
434  return true;
435  }
436  }
437  break;
438  }
439  return false;
440 }
441 
443 
444 // Check if any of the arguments in CS are predicated on a PHI node and return
445 // the set of predecessors we should use for splitting.
447  if (!isPredicatedOnPHI(CS))
448  return {};
449 
450  auto Preds = getTwoPredecessors(CS.getInstruction()->getParent());
451  return {{Preds[0], {}}, {Preds[1], {}}};
452 }
453 
454 // Checks if any of the arguments in CS are predicated in a predecessor and
455 // returns a list of predecessors with the conditions that hold on their edges
456 // to CS.
458  DomTreeUpdater &DTU) {
459  auto Preds = getTwoPredecessors(CS.getInstruction()->getParent());
460  if (Preds[0] == Preds[1])
461  return {};
462 
463  // We can stop recording conditions once we reached the immediate dominator
464  // for the block containing the call site. Conditions in predecessors of the
465  // that node will be the same for all paths to the call site and splitting
466  // is not beneficial.
467  assert(DTU.hasDomTree() && "We need a DTU with a valid DT!");
468  auto *CSDTNode = DTU.getDomTree().getNode(CS.getInstruction()->getParent());
469  BasicBlock *StopAt = CSDTNode ? CSDTNode->getIDom()->getBlock() : nullptr;
470 
472  for (auto *Pred : make_range(Preds.rbegin(), Preds.rend())) {
473  ConditionsTy Conditions;
474  // Record condition on edge BB(CS) <- Pred
475  recordCondition(CS, Pred, CS.getInstruction()->getParent(), Conditions);
476  // Record conditions following Pred's single predecessors.
477  recordConditions(CS, Pred, Conditions, StopAt);
478  PredsCS.push_back({Pred, Conditions});
479  }
480 
481  if (all_of(PredsCS, [](const std::pair<BasicBlock *, ConditionsTy> &P) {
482  return P.second.empty();
483  }))
484  return {};
485 
486  return PredsCS;
487 }
488 
490  DomTreeUpdater &DTU) {
491  // Check if we can split the call site.
492  if (!CS.arg_size() || !canSplitCallSite(CS, TTI))
493  return false;
494 
495  auto PredsWithConds = shouldSplitOnPredicatedArgument(CS, DTU);
496  if (PredsWithConds.empty())
497  PredsWithConds = shouldSplitOnPHIPredicatedArgument(CS);
498  if (PredsWithConds.empty())
499  return false;
500 
501  splitCallSite(CS, PredsWithConds, DTU);
502  return true;
503 }
504 
507 
509  bool Changed = false;
510  for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE;) {
511  BasicBlock &BB = *BI++;
512  auto II = BB.getFirstNonPHIOrDbg()->getIterator();
513  auto IE = BB.getTerminator()->getIterator();
514  // Iterate until we reach the terminator instruction. tryToSplitCallSite
515  // can replace BB's terminator in case BB is a successor of itself. In that
516  // case, IE will be invalidated and we also have to check the current
517  // terminator.
518  while (II != IE && &*II != BB.getTerminator()) {
519  Instruction *I = &*II++;
520  CallSite CS(cast<Value>(I));
521  if (!CS || isa<IntrinsicInst>(I) || isInstructionTriviallyDead(I, &TLI))
522  continue;
523 
525  if (!Callee || Callee->isDeclaration())
526  continue;
527 
528  // Successful musttail call-site splits result in erased CI and erased BB.
529  // Check if such path is possible before attempting the splitting.
530  bool IsMustTail = CS.isMustTailCall();
531 
532  Changed |= tryToSplitCallSite(CS, TTI, DTU);
533 
534  // There're no interesting instructions after this. The call site
535  // itself might have been erased on splitting.
536  if (IsMustTail)
537  break;
538  }
539  }
540  return Changed;
541 }
542 
543 namespace {
544 struct CallSiteSplittingLegacyPass : public FunctionPass {
545  static char ID;
546  CallSiteSplittingLegacyPass() : FunctionPass(ID) {
548  }
549 
550  void getAnalysisUsage(AnalysisUsage &AU) const override {
556  }
557 
558  bool runOnFunction(Function &F) override {
559  if (skipFunction(F))
560  return false;
561 
562  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
563  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
564  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
565  return doCallSiteSplitting(F, TLI, TTI, DT);
566  }
567 };
568 } // namespace
569 
571 INITIALIZE_PASS_BEGIN(CallSiteSplittingLegacyPass, "callsite-splitting",
572  "Call-site splitting", false, false)
576 INITIALIZE_PASS_END(CallSiteSplittingLegacyPass, "callsite-splitting",
577  "Call-site splitting", false, false)
579  return new CallSiteSplittingLegacyPass();
580 }
581 
584  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
585  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
586  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
587 
588  if (!doCallSiteSplitting(F, TLI, TTI, DT))
589  return PreservedAnalyses::all();
592  return PA;
593 }
IterTy arg_end() const
Definition: CallSite.h:583
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:769
IterTy arg_begin() const
Definition: CallSite.h:579
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:657
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:1185
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:244
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:655
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:423
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:321
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.
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:646
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:841
Provides information about what library functions are available for the current target.
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:324
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:322
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:205
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:398
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:349
LLVM Value Representation.
Definition: Value.h:72
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: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:322
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()