LLVM  13.0.0git
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"
62 #include "llvm/IR/IntrinsicInst.h"
63 #include "llvm/IR/PatternMatch.h"
64 #include "llvm/InitializePasses.h"
66 #include "llvm/Support/Debug.h"
67 #include "llvm/Transforms/Scalar.h"
71 
72 using namespace llvm;
73 using namespace PatternMatch;
74 
75 #define DEBUG_TYPE "callsite-splitting"
76 
77 STATISTIC(NumCallSiteSplit, "Number of call-site split");
78 
79 /// Only allow instructions before a call, if their CodeSize cost is below
80 /// DuplicationThreshold. Those instructions need to be duplicated in all
81 /// split blocks.
82 static cl::opt<unsigned>
83  DuplicationThreshold("callsite-splitting-duplication-threshold", cl::Hidden,
84  cl::desc("Only allow instructions before a call, if "
85  "their cost is below DuplicationThreshold"),
86  cl::init(5));
87 
88 static void addNonNullAttribute(CallBase &CB, Value *Op) {
89  unsigned ArgNo = 0;
90  for (auto &I : CB.args()) {
91  if (&*I == Op)
92  CB.addParamAttr(ArgNo, Attribute::NonNull);
93  ++ArgNo;
94  }
95 }
96 
98  Constant *ConstValue) {
99  unsigned ArgNo = 0;
100  for (auto &I : CB.args()) {
101  if (&*I == Op) {
102  // It is possible we have already added the non-null attribute to the
103  // parameter by using an earlier constraining condition.
104  CB.removeParamAttr(ArgNo, Attribute::NonNull);
105  CB.setArgOperand(ArgNo, ConstValue);
106  }
107  ++ArgNo;
108  }
109 }
110 
112  assert(isa<Constant>(Cmp->getOperand(1)) && "Expected a constant operand.");
113  Value *Op0 = Cmp->getOperand(0);
114  unsigned ArgNo = 0;
115  for (auto I = CB.arg_begin(), E = CB.arg_end(); I != E; ++I, ++ArgNo) {
116  // Don't consider constant or arguments that are already known non-null.
117  if (isa<Constant>(*I) || CB.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 CB.
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, CB))
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 CB following Pred's
151 /// single predecessors. If there are conflicting conditions along a path, like
152 /// x == 1 and x == 0, the first condition will be used. We stop once we reach
153 /// an edge to StopAt.
154 static void recordConditions(CallBase &CB, BasicBlock *Pred,
155  ConditionsTy &Conditions, BasicBlock *StopAt) {
156  BasicBlock *From = Pred;
157  BasicBlock *To = Pred;
159  while (To != StopAt && !Visited.count(From->getSinglePredecessor()) &&
160  (From = From->getSinglePredecessor())) {
161  recordCondition(CB, From, To, Conditions);
162  Visited.insert(From);
163  To = From;
164  }
165 }
166 
167 static void addConditions(CallBase &CB, 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(CB, Arg, ConstVal);
173  else if (ConstVal->getType()->isPointerTy() && ConstVal->isNullValue()) {
174  assert(Cond.second == ICmpInst::ICMP_NE);
176  }
177  }
178 }
179 
182  assert(Preds.size() == 2 && "Expected exactly 2 predecessors!");
183  return Preds;
184 }
185 
187  if (CB.isConvergent() || CB.cannotDuplicate())
188  return false;
189 
190  // FIXME: As of now we handle only CallInst. InvokeInst could be handled
191  // without too much effort.
192  if (!isa<CallInst>(CB))
193  return false;
194 
195  BasicBlock *CallSiteBB = CB.getParent();
196  // Need 2 predecessors and cannot split an edge from an IndirectBrInst.
197  SmallVector<BasicBlock *, 2> Preds(predecessors(CallSiteBB));
198  if (Preds.size() != 2 || isa<IndirectBrInst>(Preds[0]->getTerminator()) ||
199  isa<IndirectBrInst>(Preds[1]->getTerminator()))
200  return false;
201 
202  // BasicBlock::canSplitPredecessors is more aggressive, so checking for
203  // BasicBlock::isEHPad as well.
204  if (!CallSiteBB->canSplitPredecessors() || CallSiteBB->isEHPad())
205  return false;
206 
207  // Allow splitting a call-site only when the CodeSize cost of the
208  // instructions before the call is less then DuplicationThreshold. The
209  // instructions before the call will be duplicated in the split blocks and
210  // corresponding uses will be updated.
211  InstructionCost Cost = 0;
212  for (auto &InstBeforeCall :
213  llvm::make_range(CallSiteBB->begin(), CB.getIterator())) {
214  Cost += TTI.getInstructionCost(&InstBeforeCall,
216  if (Cost >= DuplicationThreshold)
217  return false;
218  }
219 
220  return true;
221 }
222 
224  Value *V) {
225  Instruction *Copy = I->clone();
226  Copy->setName(I->getName());
227  Copy->insertBefore(Before);
228  if (V)
229  Copy->setOperand(0, V);
230  return Copy;
231 }
232 
233 /// Copy mandatory `musttail` return sequence that follows original `CI`, and
234 /// link it up to `NewCI` value instead:
235 ///
236 /// * (optional) `bitcast NewCI to ...`
237 /// * `ret bitcast or NewCI`
238 ///
239 /// Insert this sequence right before `SplitBB`'s terminator, which will be
240 /// cleaned up later in `splitCallSite` below.
241 static void copyMustTailReturn(BasicBlock *SplitBB, Instruction *CI,
242  Instruction *NewCI) {
243  bool IsVoid = SplitBB->getParent()->getReturnType()->isVoidTy();
244  auto II = std::next(CI->getIterator());
245 
246  BitCastInst* BCI = dyn_cast<BitCastInst>(&*II);
247  if (BCI)
248  ++II;
249 
250  ReturnInst* RI = dyn_cast<ReturnInst>(&*II);
251  assert(RI && "`musttail` call must be followed by `ret` instruction");
252 
253  Instruction *TI = SplitBB->getTerminator();
254  Value *V = NewCI;
255  if (BCI)
256  V = cloneInstForMustTail(BCI, TI, V);
257  cloneInstForMustTail(RI, TI, IsVoid ? nullptr : V);
258 
259  // FIXME: remove TI here, `DuplicateInstructionsInSplitBetween` has a bug
260  // that prevents doing this now.
261 }
262 
263 /// For each (predecessor, conditions from predecessors) pair, it will split the
264 /// basic block containing the call site, hook it up to the predecessor and
265 /// replace the call instruction with new call instructions, which contain
266 /// constraints based on the conditions from their predecessors.
267 /// For example, in the IR below with an OR condition, the call-site can
268 /// be split. In this case, Preds for Tail is [(Header, a == null),
269 /// (TBB, a != null, b == null)]. Tail is replaced by 2 split blocks, containing
270 /// CallInst1, which has constraints based on the conditions from Head and
271 /// CallInst2, which has constraints based on the conditions coming from TBB.
272 ///
273 /// From :
274 ///
275 /// Header:
276 /// %c = icmp eq i32* %a, null
277 /// br i1 %c %Tail, %TBB
278 /// TBB:
279 /// %c2 = icmp eq i32* %b, null
280 /// br i1 %c %Tail, %End
281 /// Tail:
282 /// %ca = call i1 @callee (i32* %a, i32* %b)
283 ///
284 /// to :
285 ///
286 /// Header: // PredBB1 is Header
287 /// %c = icmp eq i32* %a, null
288 /// br i1 %c %Tail-split1, %TBB
289 /// TBB: // PredBB2 is TBB
290 /// %c2 = icmp eq i32* %b, null
291 /// br i1 %c %Tail-split2, %End
292 /// Tail-split1:
293 /// %ca1 = call @callee (i32* null, i32* %b) // CallInst1
294 /// br %Tail
295 /// Tail-split2:
296 /// %ca2 = call @callee (i32* nonnull %a, i32* null) // CallInst2
297 /// br %Tail
298 /// Tail:
299 /// %p = phi i1 [%ca1, %Tail-split1],[%ca2, %Tail-split2]
300 ///
301 /// Note that in case any arguments at the call-site are constrained by its
302 /// predecessors, new call-sites with more constrained arguments will be
303 /// created in createCallSitesOnPredicatedArgument().
304 static void splitCallSite(
305  CallBase &CB,
306  const SmallVectorImpl<std::pair<BasicBlock *, ConditionsTy>> &Preds,
307  DomTreeUpdater &DTU) {
308  BasicBlock *TailBB = CB.getParent();
309  bool IsMustTailCall = CB.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 && !CB.use_empty()) {
317  CallPN = PHINode::Create(CB.getType(), Preds.size(), "phi.call");
318  CallPN->setDebugLoc(CB.getDebugLoc());
319  }
320 
321  LLVM_DEBUG(dbgs() << "split call-site : " << CB << " into \n");
322 
323  assert(Preds.size() == 2 && "The ValueToValueMaps array has size 2.");
324  // ValueToValueMapTy is neither copy nor moveable, so we use a simple array
325  // here.
326  ValueToValueMapTy ValueToValueMaps[2];
327  for (unsigned i = 0; i < Preds.size(); i++) {
328  BasicBlock *PredBB = Preds[i].first;
330  TailBB, PredBB, &*std::next(CB.getIterator()), ValueToValueMaps[i],
331  DTU);
332  assert(SplitBlock && "Unexpected new basic block split.");
333 
334  auto *NewCI =
335  cast<CallBase>(&*std::prev(SplitBlock->getTerminator()->getIterator()));
336  addConditions(*NewCI, 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 : CB.args()) {
342  if (&*CI == &PN) {
343  NewCI->setArgOperand(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, &CB, NewCI);
356  }
357 
358  NumCallSiteSplit++;
359 
360  // FIXME: remove TI in `copyMustTailReturn`
361  if (IsMustTailCall) {
362  // Remove superfluous `br` terminators from the end of the Split blocks
363  // NOTE: Removing terminator removes the SplitBlock from the TailBB's
364  // predecessors. Therefore we must get complete list of Splits before
365  // attempting removal.
366  SmallVector<BasicBlock *, 2> Splits(predecessors((TailBB)));
367  assert(Splits.size() == 2 && "Expected exactly 2 splits!");
368  for (unsigned i = 0; i < Splits.size(); i++) {
369  Splits[i]->getTerminator()->eraseFromParent();
370  DTU.applyUpdatesPermissive({{DominatorTree::Delete, Splits[i], TailBB}});
371  }
372 
373  // Erase the tail block once done with musttail patching
374  DTU.deleteBB(TailBB);
375  return;
376  }
377 
378  auto *OriginalBegin = &*TailBB->begin();
379  // Replace users of the original call with a PHI mering call-sites split.
380  if (CallPN) {
381  CallPN->insertBefore(OriginalBegin);
382  CB.replaceAllUsesWith(CallPN);
383  }
384 
385  // Remove instructions moved to split blocks from TailBB, from the duplicated
386  // call instruction to the beginning of the basic block. If an instruction
387  // has any uses, add a new PHI node to combine the values coming from the
388  // split blocks. The new PHI nodes are placed before the first original
389  // instruction, so we do not end up deleting them. By using reverse-order, we
390  // do not introduce unnecessary PHI nodes for def-use chains from the call
391  // instruction to the beginning of the block.
392  auto I = CB.getReverseIterator();
393  while (I != TailBB->rend()) {
394  Instruction *CurrentI = &*I++;
395  if (!CurrentI->use_empty()) {
396  // If an existing PHI has users after the call, there is no need to create
397  // a new one.
398  if (isa<PHINode>(CurrentI))
399  continue;
400  PHINode *NewPN = PHINode::Create(CurrentI->getType(), Preds.size());
401  NewPN->setDebugLoc(CurrentI->getDebugLoc());
402  for (auto &Mapping : ValueToValueMaps)
403  NewPN->addIncoming(Mapping[CurrentI],
404  cast<Instruction>(Mapping[CurrentI])->getParent());
405  NewPN->insertBefore(&*TailBB->begin());
406  CurrentI->replaceAllUsesWith(NewPN);
407  }
408  CurrentI->eraseFromParent();
409  // We are done once we handled the first original instruction in TailBB.
410  if (CurrentI == OriginalBegin)
411  break;
412  }
413 }
414 
415 // Return true if the call-site has an argument which is a PHI with only
416 // constant incoming values.
417 static bool isPredicatedOnPHI(CallBase &CB) {
418  BasicBlock *Parent = CB.getParent();
419  if (&CB != Parent->getFirstNonPHIOrDbg())
420  return false;
421 
422  for (auto &PN : Parent->phis()) {
423  for (auto &Arg : CB.args()) {
424  if (&*Arg != &PN)
425  continue;
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  return false;
438 }
439 
441 
442 // Check if any of the arguments in CS are predicated on a PHI node and return
443 // the set of predecessors we should use for splitting.
445  if (!isPredicatedOnPHI(CB))
446  return {};
447 
448  auto Preds = getTwoPredecessors(CB.getParent());
449  return {{Preds[0], {}}, {Preds[1], {}}};
450 }
451 
452 // Checks if any of the arguments in CS are predicated in a predecessor and
453 // returns a list of predecessors with the conditions that hold on their edges
454 // to CS.
456  DomTreeUpdater &DTU) {
457  auto Preds = getTwoPredecessors(CB.getParent());
458  if (Preds[0] == Preds[1])
459  return {};
460 
461  // We can stop recording conditions once we reached the immediate dominator
462  // for the block containing the call site. Conditions in predecessors of the
463  // that node will be the same for all paths to the call site and splitting
464  // is not beneficial.
465  assert(DTU.hasDomTree() && "We need a DTU with a valid DT!");
466  auto *CSDTNode = DTU.getDomTree().getNode(CB.getParent());
467  BasicBlock *StopAt = CSDTNode ? CSDTNode->getIDom()->getBlock() : nullptr;
468 
470  for (auto *Pred : make_range(Preds.rbegin(), Preds.rend())) {
471  ConditionsTy Conditions;
472  // Record condition on edge BB(CS) <- Pred
473  recordCondition(CB, Pred, CB.getParent(), Conditions);
474  // Record conditions following Pred's single predecessors.
475  recordConditions(CB, Pred, Conditions, StopAt);
476  PredsCS.push_back({Pred, Conditions});
477  }
478 
479  if (all_of(PredsCS, [](const std::pair<BasicBlock *, ConditionsTy> &P) {
480  return P.second.empty();
481  }))
482  return {};
483 
484  return PredsCS;
485 }
486 
488  DomTreeUpdater &DTU) {
489  // Check if we can split the call site.
490  if (!CB.arg_size() || !canSplitCallSite(CB, TTI))
491  return false;
492 
493  auto PredsWithConds = shouldSplitOnPredicatedArgument(CB, DTU);
494  if (PredsWithConds.empty())
495  PredsWithConds = shouldSplitOnPHIPredicatedArgument(CB);
496  if (PredsWithConds.empty())
497  return false;
498 
499  splitCallSite(CB, PredsWithConds, DTU);
500  return true;
501 }
502 
505 
507  bool Changed = false;
508  for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE;) {
509  BasicBlock &BB = *BI++;
510  auto II = BB.getFirstNonPHIOrDbg()->getIterator();
511  auto IE = BB.getTerminator()->getIterator();
512  // Iterate until we reach the terminator instruction. tryToSplitCallSite
513  // can replace BB's terminator in case BB is a successor of itself. In that
514  // case, IE will be invalidated and we also have to check the current
515  // terminator.
516  while (II != IE && &*II != BB.getTerminator()) {
517  CallBase *CB = dyn_cast<CallBase>(&*II++);
518  if (!CB || isa<IntrinsicInst>(CB) || isInstructionTriviallyDead(CB, &TLI))
519  continue;
520 
522  if (!Callee || Callee->isDeclaration())
523  continue;
524 
525  // Successful musttail call-site splits result in erased CI and erased BB.
526  // Check if such path is possible before attempting the splitting.
527  bool IsMustTail = CB->isMustTailCall();
528 
529  Changed |= tryToSplitCallSite(*CB, TTI, DTU);
530 
531  // There're no interesting instructions after this. The call site
532  // itself might have been erased on splitting.
533  if (IsMustTail)
534  break;
535  }
536  }
537  return Changed;
538 }
539 
540 namespace {
541 struct CallSiteSplittingLegacyPass : public FunctionPass {
542  static char ID;
543  CallSiteSplittingLegacyPass() : FunctionPass(ID) {
545  }
546 
547  void getAnalysisUsage(AnalysisUsage &AU) const override {
553  }
554 
555  bool runOnFunction(Function &F) override {
556  if (skipFunction(F))
557  return false;
558 
559  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
560  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
561  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
562  return doCallSiteSplitting(F, TLI, TTI, DT);
563  }
564 };
565 } // namespace
566 
568 INITIALIZE_PASS_BEGIN(CallSiteSplittingLegacyPass, "callsite-splitting",
569  "Call-site splitting", false, false)
573 INITIALIZE_PASS_END(CallSiteSplittingLegacyPass, "callsite-splitting",
574  "Call-site splitting", false, false)
576  return new CallSiteSplittingLegacyPass();
577 }
578 
581  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
582  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
583  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
584 
585  if (!doCallSiteSplitting(F, TLI, TTI, DT))
586  return PreservedAnalyses::all();
589  return PA;
590 }
i
i
Definition: README.txt:29
llvm::InstructionCost
Definition: InstructionCost.h:26
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2265
llvm::predecessors
pred_range predecessors(BasicBlock *BB)
Definition: CFG.h:127
llvm
Definition: AllocatorList.h:23
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:743
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::DomTreeUpdater::deleteBB
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
Definition: DomTreeUpdater.cpp:177
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:2923
llvm::initializeCallSiteSplittingLegacyPassPass
void initializeCallSiteSplittingLegacyPassPass(PassRegistry &)
llvm::BasicBlock::getFirstNonPHIOrDbg
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=false) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
Definition: BasicBlock.cpp:219
getTwoPredecessors
static SmallVector< BasicBlock *, 2 > getTwoPredecessors(BasicBlock *BB)
Definition: CallSiteSplitting.cpp:180
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:722
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
IntrinsicInst.h
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:229
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:785
Scalar.h
llvm::Function
Definition: Function.h:61
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::CallSiteSplittingPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.
Definition: CallSiteSplitting.cpp:579
llvm::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5136
addConditions
static void addConditions(CallBase &CB, const ConditionsTy &Conditions)
Definition: CallSiteSplitting.cpp:167
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:744
cloneInstForMustTail
static Instruction * cloneInstForMustTail(Instruction *I, Instruction *Before, Value *V)
Definition: CallSiteSplitting.cpp:223
Local.h
llvm::Instruction::insertBefore
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:84
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::TargetTransformInfo::TCK_CodeSize
@ TCK_CodeSize
Instruction code size.
Definition: TargetTransformInfo.h:214
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
shouldSplitOnPredicatedArgument
static PredsWithCondsTy shouldSplitOnPredicatedArgument(CallBase &CB, DomTreeUpdater &DTU)
Definition: CallSiteSplitting.cpp:455
llvm::ilist_node_impl::getReverseIterator
reverse_self_iterator getReverseIterator()
Definition: ilist_node.h:84
llvm::DominatorTreeBase::getNode
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: GenericDomTree.h:351
llvm::CallBase::isMustTailCall
bool isMustTailCall() const
Tests if this call site must be tail call optimized.
Definition: Instructions.cpp:294
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(CallSiteSplittingLegacyPass, "callsite-splitting", "Call-site splitting", false, false) INITIALIZE_PASS_END(CallSiteSplittingLegacyPass
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::CallBase::arg_begin
User::op_iterator arg_begin()
Return the iterator pointing to the beginning of the argument list.
Definition: InstrTypes.h:1306
llvm::BasicBlock::canSplitPredecessors
bool canSplitPredecessors() const
Definition: BasicBlock.cpp:350
llvm::createCallSiteSplittingPass
FunctionPass * createCallSiteSplittingPass()
Definition: CallSiteSplitting.cpp:575
llvm::CallBase::addParamAttr
void addParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
Adds the attribute to the indicated argument.
Definition: InstrTypes.h:1507
llvm::BasicBlock::rend
reverse_iterator rend()
Definition: BasicBlock.h:303
INITIALIZE_PASS_END
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
Definition: RegBankSelect.cpp:69
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::DomTreeUpdater::UpdateStrategy::Lazy
@ Lazy
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
DuplicationThreshold
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.
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:205
CommandLine.h
llvm::CallBase::removeParamAttr
void removeParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
Removes the attribute from the given argument.
Definition: InstrTypes.h:1543
llvm::all_of
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:1505
recordCondition
static void recordCondition(CallBase &CB, 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...
Definition: CallSiteSplitting.cpp:131
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::Constant::isNullValue
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
Definition: Constants.cpp:86
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
ConditionsTy
SmallVector< ConditionTy, 2 > ConditionsTy
Definition: CallSiteSplitting.cpp:127
llvm::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1396
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
TargetLibraryInfo.h
false
Definition: StackSlotColoring.cpp:142
llvm::CallBase::isConvergent
bool isConvergent() const
Determine if the invoke is convergent.
Definition: InstrTypes.h:1865
llvm::Instruction
Definition: Instruction.h:45
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:281
llvm::BasicBlock::phis
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:354
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
PatternMatch.h
addNonNullAttribute
static void addNonNullAttribute(CallBase &CB, Value *Op)
Definition: CallSiteSplitting.cpp:88
llvm::DomTreeUpdater::hasDomTree
bool hasDomTree() const
Returns true if it holds a DominatorTree.
Definition: DomTreeUpdater.h:57
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:357
llvm::ARM_PROC::IE
@ IE
Definition: ARMBaseInfo.h:27
llvm::cl::opt
Definition: CommandLine.h:1419
canSplitCallSite
static bool canSplitCallSite(CallBase &CB, TargetTransformInfo &TTI)
Definition: CallSiteSplitting.cpp:186
llvm::DuplicateInstructionsInSplitBetween
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...
Definition: CloneFunction.cpp:884
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
llvm::Function::getReturnType
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:170
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1178
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:446
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2321
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:176
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2720
llvm::DomTreeUpdater::getDomTree
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
Definition: DomTreeUpdater.cpp:303
copyMustTailReturn
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...
Definition: CallSiteSplitting.cpp:241
I
#define I(x, y, z)
Definition: MD5.cpp:59
Cloning.h
doCallSiteSplitting
static bool doCallSiteSplitting(Function &F, TargetLibraryInfo &TLI, TargetTransformInfo &TTI, DominatorTree &DT)
Definition: CallSiteSplitting.cpp:503
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:440
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:362
recordConditions
static void recordConditions(CallBase &CB, BasicBlock *Pred, ConditionsTy &Conditions, BasicBlock *StopAt)
Record ICmp conditions relevant to any argument in CB following Pred's single predecessors.
Definition: CallSiteSplitting.cpp:154
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
ConditionTy
std::pair< ICmpInst *, unsigned > ConditionTy
Definition: CallSiteSplitting.cpp:126
setConstantInArgument
static void setConstantInArgument(CallBase &CB, Value *Op, Constant *ConstValue)
Definition: CallSiteSplitting.cpp:97
llvm::Type::isVoidTy
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:139
llvm::PatternMatch::m_Constant
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:98
llvm::CallBase::arg_end
User::op_iterator arg_end()
Return the iterator pointing to the end of the argument list.
Definition: InstrTypes.h:1312
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
shouldSplitOnPHIPredicatedArgument
static PredsWithCondsTy shouldSplitOnPHIPredicatedArgument(CallBase &CB)
Definition: CallSiteSplitting.cpp:444
tryToSplitCallSite
static bool tryToSplitCallSite(CallBase &CB, TargetTransformInfo &TTI, DomTreeUpdater &DTU)
Definition: CallSiteSplitting.cpp:487
llvm::isInstructionTriviallyDead
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:389
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:167
llvm::CallBase::cannotDuplicate
bool cannotDuplicate() const
Determine if the invoke cannot be duplicated.
Definition: InstrTypes.h:1853
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:526
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:759
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
CallSiteSplitting.h
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:298
llvm::ValueMap< const Value *, WeakTrackingVH >
llvm::CallBase::paramHasAttr
bool paramHasAttr(unsigned ArgNo, Attribute::AttrKind Kind) const
Determine whether the argument or parameter has the given attribute.
Definition: Instructions.cpp:339
llvm::BasicBlock::getTerminator
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:148
llvm::CallBase::setArgOperand
void setArgOperand(unsigned i, Value *v)
Definition: InstrTypes.h:1346
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:205
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::PHINode::Create
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...
Definition: Instructions.h:2612
llvm::CallBase::arg_size
unsigned arg_size() const
Definition: InstrTypes.h:1329
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:207
llvm::TargetTransformInfo::getInstructionCost
InstructionCost getInstructionCost(const Instruction *I, enum TargetCostKind kind) const
Query the cost of a specified instruction.
Definition: TargetTransformInfo.h:225
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
isPredicatedOnPHI
static bool isPredicatedOnPHI(CallBase &CB)
Definition: CallSiteSplitting.cpp:417
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:365
llvm::PatternMatch::m_ICmp
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Definition: PatternMatch.h:1355
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
TargetTransformInfo.h
llvm::PHINode
Definition: Instructions.h:2572
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1164
llvm::Pass::getAnalysisUsage
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:93
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:43
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::cl::desc
Definition: CommandLine.h:411
splitting
callsite splitting
Definition: CallSiteSplitting.cpp:573
BasicBlockUtils.h
llvm::SplitBlock
BasicBlock * SplitBlock(BasicBlock *Old, Instruction *SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
Definition: BasicBlockUtils.cpp:820
splitCallSite
static void splitCallSite(CallBase &CB, const SmallVectorImpl< std::pair< BasicBlock *, ConditionsTy >> &Preds, DomTreeUpdater &DTU)
For each (predecessor, conditions from predecessors) pair, it will split the basic block containing t...
Definition: CallSiteSplitting.cpp:304
InitializePasses.h
llvm::DomTreeUpdater::applyUpdatesPermissive
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:249
llvm::BasicBlock::isEHPad
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:465
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:421
llvm::CallBase::args
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1322
llvm::DominatorTreeBase< BasicBlock, false >::Delete
static constexpr UpdateKind Delete
Definition: GenericDomTree.h:243
isCondRelevantToAnyCallArgument
static bool isCondRelevantToAnyCallArgument(ICmpInst *Cmp, CallBase &CB)
Definition: CallSiteSplitting.cpp:111
llvm::Function::iterator
BasicBlockListType::iterator iterator
Definition: Function.h:66
llvm::SmallPtrSetImpl::insert
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:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38