LLVM  7.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.
131 static void recordCondition(CallSite CS, BasicBlock *From, BasicBlock *To,
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  // Allow splitting a call-site only when the CodeSize cost of the
195  // instructions before the call is less then DuplicationThreshold. The
196  // instructions before the call will be duplicated in the split blocks and
197  // corresponding uses will be updated.
198  unsigned Cost = 0;
199  for (auto &InstBeforeCall :
200  llvm::make_range(CallSiteBB->begin(), Instr->getIterator())) {
201  Cost += TTI.getInstructionCost(&InstBeforeCall,
203  if (Cost >= DuplicationThreshold)
204  return false;
205  }
206 
207  // Need 2 predecessors and cannot split an edge from an IndirectBrInst.
208  SmallVector<BasicBlock *, 2> Preds(predecessors(CallSiteBB));
209  if (Preds.size() != 2 || isa<IndirectBrInst>(Preds[0]->getTerminator()) ||
210  isa<IndirectBrInst>(Preds[1]->getTerminator()))
211  return false;
212 
213  // Do not split a call-site in an exception handling block. This check
214  // prevents triggering an assertion in SplitEdge used via
215  // DuplicateInstructionsInSplitBetween.
216  if (CallSiteBB->isEHPad())
217  return false;
218 
219  return CallSiteBB->canSplitPredecessors();
220 }
221 
223  Value *V) {
224  Instruction *Copy = I->clone();
225  Copy->setName(I->getName());
226  Copy->insertBefore(Before);
227  if (V)
228  Copy->setOperand(0, V);
229  return Copy;
230 }
231 
232 /// Copy mandatory `musttail` return sequence that follows original `CI`, and
233 /// link it up to `NewCI` value instead:
234 ///
235 /// * (optional) `bitcast NewCI to ...`
236 /// * `ret bitcast or NewCI`
237 ///
238 /// Insert this sequence right before `SplitBB`'s terminator, which will be
239 /// cleaned up later in `splitCallSite` below.
240 static void copyMustTailReturn(BasicBlock *SplitBB, Instruction *CI,
241  Instruction *NewCI) {
242  bool IsVoid = SplitBB->getParent()->getReturnType()->isVoidTy();
243  auto II = std::next(CI->getIterator());
244 
245  BitCastInst* BCI = dyn_cast<BitCastInst>(&*II);
246  if (BCI)
247  ++II;
248 
249  ReturnInst* RI = dyn_cast<ReturnInst>(&*II);
250  assert(RI && "`musttail` call must be followed by `ret` instruction");
251 
252  TerminatorInst *TI = SplitBB->getTerminator();
253  Value *V = NewCI;
254  if (BCI)
255  V = cloneInstForMustTail(BCI, TI, V);
256  cloneInstForMustTail(RI, TI, IsVoid ? nullptr : V);
257 
258  // FIXME: remove TI here, `DuplicateInstructionsInSplitBetween` has a bug
259  // that prevents doing this now.
260 }
261 
262 /// For each (predecessor, conditions from predecessors) pair, it will split the
263 /// basic block containing the call site, hook it up to the predecessor and
264 /// replace the call instruction with new call instructions, which contain
265 /// constraints based on the conditions from their predecessors.
266 /// For example, in the IR below with an OR condition, the call-site can
267 /// be split. In this case, Preds for Tail is [(Header, a == null),
268 /// (TBB, a != null, b == null)]. Tail is replaced by 2 split blocks, containing
269 /// CallInst1, which has constraints based on the conditions from Head and
270 /// CallInst2, which has constraints based on the conditions coming from TBB.
271 ///
272 /// From :
273 ///
274 /// Header:
275 /// %c = icmp eq i32* %a, null
276 /// br i1 %c %Tail, %TBB
277 /// TBB:
278 /// %c2 = icmp eq i32* %b, null
279 /// br i1 %c %Tail, %End
280 /// Tail:
281 /// %ca = call i1 @callee (i32* %a, i32* %b)
282 ///
283 /// to :
284 ///
285 /// Header: // PredBB1 is Header
286 /// %c = icmp eq i32* %a, null
287 /// br i1 %c %Tail-split1, %TBB
288 /// TBB: // PredBB2 is TBB
289 /// %c2 = icmp eq i32* %b, null
290 /// br i1 %c %Tail-split2, %End
291 /// Tail-split1:
292 /// %ca1 = call @callee (i32* null, i32* %b) // CallInst1
293 /// br %Tail
294 /// Tail-split2:
295 /// %ca2 = call @callee (i32* nonnull %a, i32* null) // CallInst2
296 /// br %Tail
297 /// Tail:
298 /// %p = phi i1 [%ca1, %Tail-split1],[%ca2, %Tail-split2]
299 ///
300 /// Note that in case any arguments at the call-site are constrained by its
301 /// predecessors, new call-sites with more constrained arguments will be
302 /// created in createCallSitesOnPredicatedArgument().
303 static void splitCallSite(
304  CallSite CS,
305  const SmallVectorImpl<std::pair<BasicBlock *, ConditionsTy>> &Preds,
306  DominatorTree *DT) {
307  Instruction *Instr = CS.getInstruction();
308  BasicBlock *TailBB = Instr->getParent();
309  bool IsMustTailCall = CS.isMustTailCall();
310 
311  PHINode *CallPN = nullptr;
312 
313  // `musttail` calls must be followed by optional `bitcast`, and `ret`. The
314  // split blocks will be terminated right after that so there're no users for
315  // this phi in a `TailBB`.
316  if (!IsMustTailCall && !Instr->use_empty())
317  CallPN = PHINode::Create(Instr->getType(), Preds.size(), "phi.call");
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  DT);
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 
370  // Erase the tail block once done with musttail patching
371  TailBB->eraseFromParent();
372  return;
373  }
374 
375  auto *OriginalBegin = &*TailBB->begin();
376  // Replace users of the original call with a PHI mering call-sites split.
377  if (CallPN) {
378  CallPN->insertBefore(OriginalBegin);
379  Instr->replaceAllUsesWith(CallPN);
380  }
381 
382  // Remove instructions moved to split blocks from TailBB, from the duplicated
383  // call instruction to the beginning of the basic block. If an instruction
384  // has any uses, add a new PHI node to combine the values coming from the
385  // split blocks. The new PHI nodes are placed before the first original
386  // instruction, so we do not end up deleting them. By using reverse-order, we
387  // do not introduce unnecessary PHI nodes for def-use chains from the call
388  // instruction to the beginning of the block.
389  auto I = Instr->getReverseIterator();
390  while (I != TailBB->rend()) {
391  Instruction *CurrentI = &*I++;
392  if (!CurrentI->use_empty()) {
393  // If an existing PHI has users after the call, there is no need to create
394  // a new one.
395  if (isa<PHINode>(CurrentI))
396  continue;
397  PHINode *NewPN = PHINode::Create(CurrentI->getType(), Preds.size());
398  for (auto &Mapping : ValueToValueMaps)
399  NewPN->addIncoming(Mapping[CurrentI],
400  cast<Instruction>(Mapping[CurrentI])->getParent());
401  NewPN->insertBefore(&*TailBB->begin());
402  CurrentI->replaceAllUsesWith(NewPN);
403  }
404  CurrentI->eraseFromParent();
405  // We are done once we handled the first original instruction in TailBB.
406  if (CurrentI == OriginalBegin)
407  break;
408  }
409 }
410 
411 // Return true if the call-site has an argument which is a PHI with only
412 // constant incoming values.
413 static bool isPredicatedOnPHI(CallSite CS) {
414  Instruction *Instr = CS.getInstruction();
415  BasicBlock *Parent = Instr->getParent();
416  if (Instr != Parent->getFirstNonPHIOrDbg())
417  return false;
418 
419  for (auto &BI : *Parent) {
420  if (PHINode *PN = dyn_cast<PHINode>(&BI)) {
421  for (auto &I : CS.args())
422  if (&*I == PN) {
423  assert(PN->getNumIncomingValues() == 2 &&
424  "Unexpected number of incoming values");
425  if (PN->getIncomingBlock(0) == PN->getIncomingBlock(1))
426  return false;
427  if (PN->getIncomingValue(0) == PN->getIncomingValue(1))
428  continue;
429  if (isa<Constant>(PN->getIncomingValue(0)) &&
430  isa<Constant>(PN->getIncomingValue(1)))
431  return true;
432  }
433  }
434  break;
435  }
436  return false;
437 }
438 
440  if (!isPredicatedOnPHI(CS))
441  return false;
442 
443  auto Preds = getTwoPredecessors(CS.getInstruction()->getParent());
445  {Preds[0], {}}, {Preds[1], {}}};
446  splitCallSite(CS, PredsCS, DT);
447  return true;
448 }
449 
451  auto Preds = getTwoPredecessors(CS.getInstruction()->getParent());
452  if (Preds[0] == Preds[1])
453  return false;
454 
456  for (auto *Pred : make_range(Preds.rbegin(), Preds.rend())) {
457  ConditionsTy Conditions;
458  recordConditions(CS, Pred, Conditions);
459  PredsCS.push_back({Pred, Conditions});
460  }
461 
462  if (std::all_of(PredsCS.begin(), PredsCS.end(),
463  [](const std::pair<BasicBlock *, ConditionsTy> &P) {
464  return P.second.empty();
465  }))
466  return false;
467 
468  splitCallSite(CS, PredsCS, DT);
469  return true;
470 }
471 
473  DominatorTree *DT) {
474  if (!CS.arg_size() || !canSplitCallSite(CS, TTI))
475  return false;
476  return tryToSplitOnPredicatedArgument(CS, DT) ||
478 }
479 
482  bool Changed = false;
483  for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE;) {
484  BasicBlock &BB = *BI++;
485  auto II = BB.getFirstNonPHIOrDbg()->getIterator();
486  auto IE = BB.getTerminator()->getIterator();
487  // Iterate until we reach the terminator instruction. tryToSplitCallSite
488  // can replace BB's terminator in case BB is a successor of itself. In that
489  // case, IE will be invalidated and we also have to check the current
490  // terminator.
491  while (II != IE && &*II != BB.getTerminator()) {
492  Instruction *I = &*II++;
493  CallSite CS(cast<Value>(I));
494  if (!CS || isa<IntrinsicInst>(I) || isInstructionTriviallyDead(I, &TLI))
495  continue;
496 
498  if (!Callee || Callee->isDeclaration())
499  continue;
500 
501  // Successful musttail call-site splits result in erased CI and erased BB.
502  // Check if such path is possible before attempting the splitting.
503  bool IsMustTail = CS.isMustTailCall();
504 
505  Changed |= tryToSplitCallSite(CS, TTI, DT);
506 
507  // There're no interesting instructions after this. The call site
508  // itself might have been erased on splitting.
509  if (IsMustTail)
510  break;
511  }
512  }
513  return Changed;
514 }
515 
516 namespace {
517 struct CallSiteSplittingLegacyPass : public FunctionPass {
518  static char ID;
519  CallSiteSplittingLegacyPass() : FunctionPass(ID) {
521  }
522 
523  void getAnalysisUsage(AnalysisUsage &AU) const override {
528  }
529 
530  bool runOnFunction(Function &F) override {
531  if (skipFunction(F))
532  return false;
533 
534  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
535  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
536  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
537  return doCallSiteSplitting(F, TLI, TTI,
538  DTWP ? &DTWP->getDomTree() : nullptr);
539  }
540 };
541 } // namespace
542 
544 INITIALIZE_PASS_BEGIN(CallSiteSplittingLegacyPass, "callsite-splitting",
545  "Call-site splitting", false, false)
548 INITIALIZE_PASS_END(CallSiteSplittingLegacyPass, "callsite-splitting",
549  "Call-site splitting", false, false)
551  return new CallSiteSplittingLegacyPass();
552 }
553 
556  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
557  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
558  auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F);
559 
560  if (!doCallSiteSplitting(F, TLI, TTI, DT))
561  return PreservedAnalyses::all();
564  return PA;
565 }
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:213
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:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr)
Split the specified block at the specified instruction - everything before SplitPt stays in Old and e...
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:137
iterator end()
Definition: Function.h:644
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:908
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:225
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:642
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:142
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:155
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:153
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:117
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:221
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:885
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:159
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
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
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:861
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:113
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:121
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:706
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:174
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:201
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:346
LLVM Value Representation.
Definition: Value.h:73
static void addConditions(CallSite CS, const ConditionsTy &Conditions)
static const Function * getParent(const Value *V)
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:254
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:119
bool isMustTailCall() const
Tests if this call site must be tail call optimized.
Definition: CallSite.h:271
bool use_empty() const
Definition: Value.h:322
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:974
FunctionPass * createCallSiteSplittingPass()