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.
153 static void recordConditions(CallSite CS, BasicBlock *Pred,
154  ConditionsTy &Conditions) {
155  recordCondition(CS, Pred, CS.getInstruction()->getParent(), Conditions);
156  BasicBlock *From = Pred;
157  BasicBlock *To = Pred;
159  while (!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 agressive, 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  TerminatorInst *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  DominatorTree *DT) {
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  DT);
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 
371  // Erase the tail block once done with musttail patching
372  TailBB->eraseFromParent();
373  return;
374  }
375 
376  auto *OriginalBegin = &*TailBB->begin();
377  // Replace users of the original call with a PHI mering call-sites split.
378  if (CallPN) {
379  CallPN->insertBefore(OriginalBegin);
380  Instr->replaceAllUsesWith(CallPN);
381  }
382 
383  // Remove instructions moved to split blocks from TailBB, from the duplicated
384  // call instruction to the beginning of the basic block. If an instruction
385  // has any uses, add a new PHI node to combine the values coming from the
386  // split blocks. The new PHI nodes are placed before the first original
387  // instruction, so we do not end up deleting them. By using reverse-order, we
388  // do not introduce unnecessary PHI nodes for def-use chains from the call
389  // instruction to the beginning of the block.
390  auto I = Instr->getReverseIterator();
391  while (I != TailBB->rend()) {
392  Instruction *CurrentI = &*I++;
393  if (!CurrentI->use_empty()) {
394  // If an existing PHI has users after the call, there is no need to create
395  // a new one.
396  if (isa<PHINode>(CurrentI))
397  continue;
398  PHINode *NewPN = PHINode::Create(CurrentI->getType(), Preds.size());
399  NewPN->setDebugLoc(CurrentI->getDebugLoc());
400  for (auto &Mapping : ValueToValueMaps)
401  NewPN->addIncoming(Mapping[CurrentI],
402  cast<Instruction>(Mapping[CurrentI])->getParent());
403  NewPN->insertBefore(&*TailBB->begin());
404  CurrentI->replaceAllUsesWith(NewPN);
405  }
406  CurrentI->eraseFromParent();
407  // We are done once we handled the first original instruction in TailBB.
408  if (CurrentI == OriginalBegin)
409  break;
410  }
411 }
412 
413 // Return true if the call-site has an argument which is a PHI with only
414 // constant incoming values.
415 static bool isPredicatedOnPHI(CallSite CS) {
416  Instruction *Instr = CS.getInstruction();
417  BasicBlock *Parent = Instr->getParent();
418  if (Instr != Parent->getFirstNonPHIOrDbg())
419  return false;
420 
421  for (auto &BI : *Parent) {
422  if (PHINode *PN = dyn_cast<PHINode>(&BI)) {
423  for (auto &I : CS.args())
424  if (&*I == PN) {
425  assert(PN->getNumIncomingValues() == 2 &&
426  "Unexpected number of incoming values");
427  if (PN->getIncomingBlock(0) == PN->getIncomingBlock(1))
428  return false;
429  if (PN->getIncomingValue(0) == PN->getIncomingValue(1))
430  continue;
431  if (isa<Constant>(PN->getIncomingValue(0)) &&
432  isa<Constant>(PN->getIncomingValue(1)))
433  return true;
434  }
435  }
436  break;
437  }
438  return false;
439 }
440 
442  if (!isPredicatedOnPHI(CS))
443  return false;
444 
445  auto Preds = getTwoPredecessors(CS.getInstruction()->getParent());
447  {Preds[0], {}}, {Preds[1], {}}};
448  splitCallSite(CS, PredsCS, DT);
449  return true;
450 }
451 
453  auto Preds = getTwoPredecessors(CS.getInstruction()->getParent());
454  if (Preds[0] == Preds[1])
455  return false;
456 
458  for (auto *Pred : make_range(Preds.rbegin(), Preds.rend())) {
459  ConditionsTy Conditions;
460  recordConditions(CS, Pred, Conditions);
461  PredsCS.push_back({Pred, Conditions});
462  }
463 
464  if (std::all_of(PredsCS.begin(), PredsCS.end(),
465  [](const std::pair<BasicBlock *, ConditionsTy> &P) {
466  return P.second.empty();
467  }))
468  return false;
469 
470  splitCallSite(CS, PredsCS, DT);
471  return true;
472 }
473 
475  DominatorTree *DT) {
476  if (!CS.arg_size() || !canSplitCallSite(CS, TTI))
477  return false;
478  return tryToSplitOnPredicatedArgument(CS, DT) ||
480 }
481 
484  bool Changed = false;
485  for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE;) {
486  BasicBlock &BB = *BI++;
487  auto II = BB.getFirstNonPHIOrDbg()->getIterator();
488  auto IE = BB.getTerminator()->getIterator();
489  // Iterate until we reach the terminator instruction. tryToSplitCallSite
490  // can replace BB's terminator in case BB is a successor of itself. In that
491  // case, IE will be invalidated and we also have to check the current
492  // terminator.
493  while (II != IE && &*II != BB.getTerminator()) {
494  Instruction *I = &*II++;
495  CallSite CS(cast<Value>(I));
496  if (!CS || isa<IntrinsicInst>(I) || isInstructionTriviallyDead(I, &TLI))
497  continue;
498 
500  if (!Callee || Callee->isDeclaration())
501  continue;
502 
503  // Successful musttail call-site splits result in erased CI and erased BB.
504  // Check if such path is possible before attempting the splitting.
505  bool IsMustTail = CS.isMustTailCall();
506 
507  Changed |= tryToSplitCallSite(CS, TTI, DT);
508 
509  // There're no interesting instructions after this. The call site
510  // itself might have been erased on splitting.
511  if (IsMustTail)
512  break;
513  }
514  }
515  return Changed;
516 }
517 
518 namespace {
519 struct CallSiteSplittingLegacyPass : public FunctionPass {
520  static char ID;
521  CallSiteSplittingLegacyPass() : FunctionPass(ID) {
523  }
524 
525  void getAnalysisUsage(AnalysisUsage &AU) const override {
530  }
531 
532  bool runOnFunction(Function &F) override {
533  if (skipFunction(F))
534  return false;
535 
536  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
537  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
538  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
539  return doCallSiteSplitting(F, TLI, TTI,
540  DTWP ? &DTWP->getDomTree() : nullptr);
541  }
542 };
543 } // namespace
544 
546 INITIALIZE_PASS_BEGIN(CallSiteSplittingLegacyPass, "callsite-splitting",
547  "Call-site splitting", false, false)
550 INITIALIZE_PASS_END(CallSiteSplittingLegacyPass, "callsite-splitting",
551  "Call-site splitting", false, false)
553  return new CallSiteSplittingLegacyPass();
554 }
555 
558  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
559  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
560  auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F);
561 
562  if (!doCallSiteSplitting(F, TLI, TTI, DT))
563  return PreservedAnalyses::all();
566  return PA;
567 }
static void splitCallSite(CallSite CS, const SmallVectorImpl< std::pair< BasicBlock *, ConditionsTy >> &Preds, DominatorTree *DT)
For each (predecessor, conditions from predecessors) pair, it will split the basic block containing t...
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
void push_back(const T &Elt)
Definition: SmallVector.h:218
bool canSplitPredecessors() const
Definition: BasicBlock.cpp:365
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
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:770
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
iterator end()
Definition: Function.h:658
SmallVector< ConditionTy, 2 > ConditionsTy
BasicBlock * DuplicateInstructionsInSplitBetween(BasicBlock *BB, BasicBlock *PredBB, Instruction *StopAt, ValueToValueMapTy &ValueMapping, DominatorTree *DT=nullptr)
Split edge between BB and PredBB and duplicate all non-Phi instructions from BB between its beginning...
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:1042
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:231
F(f)
reverse_iterator rend()
Definition: BasicBlock.h:271
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:264
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
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:295
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:439
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:410
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:169
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:55
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:304
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:59
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
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:129
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:685
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
static bool doCallSiteSplitting(Function &F, TargetLibraryInfo &TLI, TargetTransformInfo &TTI, DominatorTree *DT)
size_t size() const
Definition: SmallVector.h:53
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
static bool tryToSplitCallSite(CallSite CS, TargetTransformInfo &TTI, DominatorTree *DT)
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:123
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
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:133
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:307
reverse_self_iterator getReverseIterator()
Definition: ilist_node.h:85
static bool tryToSplitOnPHIPredicatedArgument(CallSite CS, DominatorTree *DT)
static bool tryToSplitOnPredicatedArgument(CallSite CS, DominatorTree *DT)
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink &#39;this&#39; from the containing function and delete it.
Definition: BasicBlock.cpp:115
#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)
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:789
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:320
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:394
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:196
static void recordConditions(CallSite CS, BasicBlock *Pred, ConditionsTy &Conditions)
Record ICmp conditions relevant to any argument in CS following Pred&#39;s single predecessors.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:260
This pass exposes codegen information to IR-level passes.
const TerminatorInst * 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
#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)
Definition: PatternMatch.h:983
FunctionPass * createCallSiteSplittingPass()