LLVM  16.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"
63 #include "llvm/IR/IntrinsicInst.h"
64 #include "llvm/IR/PatternMatch.h"
65 #include "llvm/InitializePasses.h"
67 #include "llvm/Support/Debug.h"
68 #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 using ConditionTy = std::pair<ICmpInst *, unsigned>;
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 (const 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(CallBase &CB,
305  ArrayRef<std::pair<BasicBlock *, ConditionsTy>> Preds,
306  DomTreeUpdater &DTU) {
307  BasicBlock *TailBB = CB.getParent();
308  bool IsMustTailCall = CB.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 && !CB.use_empty()) {
316  CallPN = PHINode::Create(CB.getType(), Preds.size(), "phi.call");
317  CallPN->setDebugLoc(CB.getDebugLoc());
318  }
319 
320  LLVM_DEBUG(dbgs() << "split call-site : " << CB << " 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(CB.getIterator()), ValueToValueMaps[i],
330  DTU);
331  assert(SplitBlock && "Unexpected new basic block split.");
332 
333  auto *NewCI =
334  cast<CallBase>(&*std::prev(SplitBlock->getTerminator()->getIterator()));
335  addConditions(*NewCI, 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 : CB.args()) {
341  if (&*CI == &PN) {
342  NewCI->setArgOperand(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, &CB, 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 (BasicBlock *BB : Splits) {
368  BB->getTerminator()->eraseFromParent();
370  }
371 
372  // Erase the tail block once done with musttail patching
373  DTU.deleteBB(TailBB);
374  return;
375  }
376 
377  auto *OriginalBegin = &*TailBB->begin();
378  // Replace users of the original call with a PHI mering call-sites split.
379  if (CallPN) {
380  CallPN->insertBefore(OriginalBegin);
381  CB.replaceAllUsesWith(CallPN);
382  }
383 
384  // Remove instructions moved to split blocks from TailBB, from the duplicated
385  // call instruction to the beginning of the basic block. If an instruction
386  // has any uses, add a new PHI node to combine the values coming from the
387  // split blocks. The new PHI nodes are placed before the first original
388  // instruction, so we do not end up deleting them. By using reverse-order, we
389  // do not introduce unnecessary PHI nodes for def-use chains from the call
390  // instruction to the beginning of the block.
391  auto I = CB.getReverseIterator();
392  while (I != TailBB->rend()) {
393  Instruction *CurrentI = &*I++;
394  if (!CurrentI->use_empty()) {
395  // If an existing PHI has users after the call, there is no need to create
396  // a new one.
397  if (isa<PHINode>(CurrentI))
398  continue;
399  PHINode *NewPN = PHINode::Create(CurrentI->getType(), Preds.size());
400  NewPN->setDebugLoc(CurrentI->getDebugLoc());
401  for (auto &Mapping : ValueToValueMaps)
402  NewPN->addIncoming(Mapping[CurrentI],
403  cast<Instruction>(Mapping[CurrentI])->getParent());
404  NewPN->insertBefore(&*TailBB->begin());
405  CurrentI->replaceAllUsesWith(NewPN);
406  }
407  CurrentI->eraseFromParent();
408  // We are done once we handled the first original instruction in TailBB.
409  if (CurrentI == OriginalBegin)
410  break;
411  }
412 }
413 
414 // Return true if the call-site has an argument which is a PHI with only
415 // constant incoming values.
416 static bool isPredicatedOnPHI(CallBase &CB) {
417  BasicBlock *Parent = CB.getParent();
418  if (&CB != Parent->getFirstNonPHIOrDbg())
419  return false;
420 
421  for (auto &PN : Parent->phis()) {
422  for (auto &Arg : CB.args()) {
423  if (&*Arg != &PN)
424  continue;
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  return false;
437 }
438 
440 
441 // Check if any of the arguments in CS are predicated on a PHI node and return
442 // the set of predecessors we should use for splitting.
444  if (!isPredicatedOnPHI(CB))
445  return {};
446 
447  auto Preds = getTwoPredecessors(CB.getParent());
448  return {{Preds[0], {}}, {Preds[1], {}}};
449 }
450 
451 // Checks if any of the arguments in CS are predicated in a predecessor and
452 // returns a list of predecessors with the conditions that hold on their edges
453 // to CS.
455  DomTreeUpdater &DTU) {
456  auto Preds = getTwoPredecessors(CB.getParent());
457  if (Preds[0] == Preds[1])
458  return {};
459 
460  // We can stop recording conditions once we reached the immediate dominator
461  // for the block containing the call site. Conditions in predecessors of the
462  // that node will be the same for all paths to the call site and splitting
463  // is not beneficial.
464  assert(DTU.hasDomTree() && "We need a DTU with a valid DT!");
465  auto *CSDTNode = DTU.getDomTree().getNode(CB.getParent());
466  BasicBlock *StopAt = CSDTNode ? CSDTNode->getIDom()->getBlock() : nullptr;
467 
469  for (auto *Pred : llvm::reverse(Preds)) {
470  ConditionsTy Conditions;
471  // Record condition on edge BB(CS) <- Pred
472  recordCondition(CB, Pred, CB.getParent(), Conditions);
473  // Record conditions following Pred's single predecessors.
474  recordConditions(CB, Pred, Conditions, StopAt);
475  PredsCS.push_back({Pred, Conditions});
476  }
477 
478  if (all_of(PredsCS, [](const std::pair<BasicBlock *, ConditionsTy> &P) {
479  return P.second.empty();
480  }))
481  return {};
482 
483  return PredsCS;
484 }
485 
487  DomTreeUpdater &DTU) {
488  // Check if we can split the call site.
489  if (!CB.arg_size() || !canSplitCallSite(CB, TTI))
490  return false;
491 
492  auto PredsWithConds = shouldSplitOnPredicatedArgument(CB, DTU);
493  if (PredsWithConds.empty())
494  PredsWithConds = shouldSplitOnPHIPredicatedArgument(CB);
495  if (PredsWithConds.empty())
496  return false;
497 
498  splitCallSite(CB, PredsWithConds, DTU);
499  return true;
500 }
501 
504 
506  bool Changed = false;
508  auto II = BB.getFirstNonPHIOrDbg()->getIterator();
509  auto IE = BB.getTerminator()->getIterator();
510  // Iterate until we reach the terminator instruction. tryToSplitCallSite
511  // can replace BB's terminator in case BB is a successor of itself. In that
512  // case, IE will be invalidated and we also have to check the current
513  // terminator.
514  while (II != IE && &*II != BB.getTerminator()) {
515  CallBase *CB = dyn_cast<CallBase>(&*II++);
516  if (!CB || isa<IntrinsicInst>(CB) || isInstructionTriviallyDead(CB, &TLI))
517  continue;
518 
520  if (!Callee || Callee->isDeclaration())
521  continue;
522 
523  // Successful musttail call-site splits result in erased CI and erased BB.
524  // Check if such path is possible before attempting the splitting.
525  bool IsMustTail = CB->isMustTailCall();
526 
527  Changed |= tryToSplitCallSite(*CB, TTI, DTU);
528 
529  // There're no interesting instructions after this. The call site
530  // itself might have been erased on splitting.
531  if (IsMustTail)
532  break;
533  }
534  }
535  return Changed;
536 }
537 
538 namespace {
539 struct CallSiteSplittingLegacyPass : public FunctionPass {
540  static char ID;
541  CallSiteSplittingLegacyPass() : FunctionPass(ID) {
543  }
544 
545  void getAnalysisUsage(AnalysisUsage &AU) const override {
551  }
552 
553  bool runOnFunction(Function &F) override {
554  if (skipFunction(F))
555  return false;
556 
557  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
558  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
559  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
560  return doCallSiteSplitting(F, TLI, TTI, DT);
561  }
562 };
563 } // namespace
564 
566 INITIALIZE_PASS_BEGIN(CallSiteSplittingLegacyPass, "callsite-splitting",
567  "Call-site splitting", false, false)
571 INITIALIZE_PASS_END(CallSiteSplittingLegacyPass, "callsite-splitting",
572  "Call-site splitting", false, false)
574  return new CallSiteSplittingLegacyPass();
575 }
576 
579  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
580  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
581  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
582 
583  if (!doCallSiteSplitting(F, TLI, TTI, DT))
584  return PreservedAnalyses::all();
587  return PA;
588 }
i
i
Definition: README.txt:29
llvm::InstructionCost
Definition: InstructionCost.h:30
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2586
ConditionTy
std::pair< ICmpInst *, unsigned > ConditionTy
Definition: CallSiteSplitting.cpp:126
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::TargetTransformInfo::getInstructionCost
InstructionCost getInstructionCost(const User *U, ArrayRef< const Value * > Operands, TargetCostKind CostKind) const
Estimate the cost of a given IR user when lowered.
Definition: TargetTransformInfo.cpp:224
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:741
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:3052
llvm::initializeCallSiteSplittingLegacyPassPass
void initializeCallSiteSplittingLegacyPassPass(PassRegistry &)
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
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:720
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:104
IntrinsicInst.h
llvm::Type::isPointerTy
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:237
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:774
Scalar.h
llvm::Function
Definition: Function.h:60
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:577
llvm::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5256
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:1199
Statistic.h
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:173
DomTreeUpdater.h
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:742
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:87
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::TargetTransformInfo::TCK_CodeSize
@ TCK_CodeSize
Instruction code size.
Definition: TargetTransformInfo.h:221
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
shouldSplitOnPredicatedArgument
static PredsWithCondsTy shouldSplitOnPredicatedArgument(CallBase &CB, DomTreeUpdater &DTU)
Definition: CallSiteSplitting.cpp:454
llvm::ilist_node_impl::getReverseIterator
reverse_self_iterator getReverseIterator()
Definition: ilist_node.h:85
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:300
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:450
llvm::CallBase::arg_begin
User::op_iterator arg_begin()
Return the iterator pointing to the beginning of the argument list.
Definition: InstrTypes.h:1317
llvm::BasicBlock::canSplitPredecessors
bool canSplitPredecessors() const
Definition: BasicBlock.cpp:371
llvm::createCallSiteSplittingPass
FunctionPass * createCallSiteSplittingPass()
Definition: CallSiteSplitting.cpp:573
llvm::CallBase::addParamAttr
void addParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
Adds the attribute to the indicated argument.
Definition: InstrTypes.h:1527
llvm::BasicBlock::rend
reverse_iterator rend()
Definition: BasicBlock.h:313
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::DomTreeUpdater::UpdateStrategy::Lazy
@ Lazy
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
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:163
Arg
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Definition: AMDGPULibCalls.cpp:187
CommandLine.h
llvm::CallBase::removeParamAttr
void removeParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
Removes the attribute from the given argument.
Definition: InstrTypes.h:1569
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:1734
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:24
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:76
InlinePriorityMode::Cost
@ Cost
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1397
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:306
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
TargetLibraryInfo.h
false
Definition: StackSlotColoring.cpp:141
llvm::CallBase::isConvergent
bool isConvergent() const
Determine if the invoke is convergent.
Definition: InstrTypes.h:1902
llvm::Instruction
Definition: Instruction.h:42
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:302
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:364
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::predecessors
auto predecessors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:30
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
splitCallSite
static void splitCallSite(CallBase &CB, ArrayRef< 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
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:344
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::ARM_PROC::IE
@ IE
Definition: ARMBaseInfo.h:27
llvm::cl::opt
Definition: CommandLine.h:1412
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:1026
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:81
llvm::Function::getReturnType
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:180
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1186
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:475
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2642
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
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:2849
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:58
Cloning.h
doCallSiteSplitting
static bool doCallSiteSplitting(Function &F, TargetLibraryInfo &TLI, TargetTransformInfo &TTI, DominatorTree &DT)
Definition: CallSiteSplitting.cpp:502
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:447
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:716
llvm::Instruction::setDebugLoc
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:356
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())
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:144
llvm::CallBase::arg_end
User::op_iterator arg_end()
Return the iterator pointing to the end of the argument list.
Definition: InstrTypes.h:1323
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:383
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:443
tryToSplitCallSite
static bool tryToSplitCallSite(CallBase &CB, TargetTransformInfo &TTI, DomTreeUpdater &DTU)
Definition: CallSiteSplitting.cpp:486
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
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 will return.
Definition: Local.cpp:396
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:138
llvm::CallBase::cannotDuplicate
bool cannotDuplicate() const
Determine if the invoke cannot be duplicated.
Definition: InstrTypes.h:1894
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
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:532
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:805
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
CallSiteSplitting.h
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
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:343
llvm::CallBase::setArgOperand
void setArgOperand(unsigned i, Value *v)
Definition: InstrTypes.h:1347
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:187
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:85
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
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:2741
llvm::CallBase::arg_size
unsigned arg_size() const
Definition: InstrTypes.h:1340
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:226
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
isPredicatedOnPHI
static bool isPredicatedOnPHI(CallBase &CB)
Definition: CallSiteSplitting.cpp:416
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:359
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:1394
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
TargetTransformInfo.h
llvm::BasicBlock::getFirstNonPHIOrDbg
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
Definition: BasicBlock.cpp:216
llvm::PHINode
Definition: Instructions.h:2699
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.h:119
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:485
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1175
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:98
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
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:413
splitting
callsite splitting
Definition: CallSiteSplitting.cpp:571
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:918
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:475
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:450
llvm::CallBase::args
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1333
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::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:365