LLVM 18.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"
66#include "llvm/Support/Debug.h"
69
70using namespace llvm;
71using namespace PatternMatch;
72
73#define DEBUG_TYPE "callsite-splitting"
74
75STATISTIC(NumCallSiteSplit, "Number of call-site split");
76
77/// Only allow instructions before a call, if their CodeSize cost is below
78/// DuplicationThreshold. Those instructions need to be duplicated in all
79/// split blocks.
81 DuplicationThreshold("callsite-splitting-duplication-threshold", cl::Hidden,
82 cl::desc("Only allow instructions before a call, if "
83 "their cost is below DuplicationThreshold"),
84 cl::init(5));
85
87 unsigned ArgNo = 0;
88 for (auto &I : CB.args()) {
89 if (&*I == Op)
90 CB.addParamAttr(ArgNo, Attribute::NonNull);
91 ++ArgNo;
92 }
93}
94
96 Constant *ConstValue) {
97 unsigned ArgNo = 0;
98 for (auto &I : CB.args()) {
99 if (&*I == Op) {
100 // It is possible we have already added the non-null attribute to the
101 // parameter by using an earlier constraining condition.
102 CB.removeParamAttr(ArgNo, Attribute::NonNull);
103 CB.setArgOperand(ArgNo, ConstValue);
104 }
105 ++ArgNo;
106 }
107}
108
110 assert(isa<Constant>(Cmp->getOperand(1)) && "Expected a constant operand.");
111 Value *Op0 = Cmp->getOperand(0);
112 unsigned ArgNo = 0;
113 for (auto I = CB.arg_begin(), E = CB.arg_end(); I != E; ++I, ++ArgNo) {
114 // Don't consider constant or arguments that are already known non-null.
115 if (isa<Constant>(*I) || CB.paramHasAttr(ArgNo, Attribute::NonNull))
116 continue;
117
118 if (*I == Op0)
119 return true;
120 }
121 return false;
122}
123
124using ConditionTy = std::pair<ICmpInst *, unsigned>;
126
127/// If From has a conditional jump to To, add the condition to Conditions,
128/// if it is relevant to any argument at CB.
130 ConditionsTy &Conditions) {
131 auto *BI = dyn_cast<BranchInst>(From->getTerminator());
132 if (!BI || !BI->isConditional())
133 return;
134
136 Value *Cond = BI->getCondition();
137 if (!match(Cond, m_ICmp(Pred, m_Value(), m_Constant())))
138 return;
139
140 ICmpInst *Cmp = cast<ICmpInst>(Cond);
141 if (Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE)
143 Conditions.push_back({Cmp, From->getTerminator()->getSuccessor(0) == To
144 ? Pred
145 : Cmp->getInversePredicate()});
146}
147
148/// Record ICmp conditions relevant to any argument in CB following Pred's
149/// single predecessors. If there are conflicting conditions along a path, like
150/// x == 1 and x == 0, the first condition will be used. We stop once we reach
151/// an edge to StopAt.
152static void recordConditions(CallBase &CB, BasicBlock *Pred,
153 ConditionsTy &Conditions, BasicBlock *StopAt) {
154 BasicBlock *From = Pred;
155 BasicBlock *To = Pred;
157 while (To != StopAt && !Visited.count(From->getSinglePredecessor()) &&
158 (From = From->getSinglePredecessor())) {
159 recordCondition(CB, From, To, Conditions);
160 Visited.insert(From);
161 To = From;
162 }
163}
164
165static void addConditions(CallBase &CB, const ConditionsTy &Conditions) {
166 for (const auto &Cond : Conditions) {
167 Value *Arg = Cond.first->getOperand(0);
168 Constant *ConstVal = cast<Constant>(Cond.first->getOperand(1));
169 if (Cond.second == ICmpInst::ICMP_EQ)
170 setConstantInArgument(CB, Arg, ConstVal);
171 else if (ConstVal->getType()->isPointerTy() && ConstVal->isNullValue()) {
172 assert(Cond.second == ICmpInst::ICMP_NE);
173 addNonNullAttribute(CB, Arg);
174 }
175 }
176}
177
180 assert(Preds.size() == 2 && "Expected exactly 2 predecessors!");
181 return Preds;
182}
183
185 if (CB.isConvergent() || CB.cannotDuplicate())
186 return false;
187
188 // FIXME: As of now we handle only CallInst. InvokeInst could be handled
189 // without too much effort.
190 if (!isa<CallInst>(CB))
191 return false;
192
193 BasicBlock *CallSiteBB = CB.getParent();
194 // Need 2 predecessors and cannot split an edge from an IndirectBrInst.
196 if (Preds.size() != 2 || isa<IndirectBrInst>(Preds[0]->getTerminator()) ||
197 isa<IndirectBrInst>(Preds[1]->getTerminator()))
198 return false;
199
200 // BasicBlock::canSplitPredecessors is more aggressive, so checking for
201 // BasicBlock::isEHPad as well.
202 if (!CallSiteBB->canSplitPredecessors() || CallSiteBB->isEHPad())
203 return false;
204
205 // Allow splitting a call-site only when the CodeSize cost of the
206 // instructions before the call is less then DuplicationThreshold. The
207 // instructions before the call will be duplicated in the split blocks and
208 // corresponding uses will be updated.
210 for (auto &InstBeforeCall :
211 llvm::make_range(CallSiteBB->begin(), CB.getIterator())) {
212 Cost += TTI.getInstructionCost(&InstBeforeCall,
215 return false;
216 }
217
218 return true;
219}
220
222 Value *V) {
223 Instruction *Copy = I->clone();
224 Copy->setName(I->getName());
225 Copy->insertBefore(Before);
226 if (V)
227 Copy->setOperand(0, V);
228 return Copy;
229}
230
231/// Copy mandatory `musttail` return sequence that follows original `CI`, and
232/// link it up to `NewCI` value instead:
233///
234/// * (optional) `bitcast NewCI to ...`
235/// * `ret bitcast or NewCI`
236///
237/// Insert this sequence right before `SplitBB`'s terminator, which will be
238/// cleaned up later in `splitCallSite` below.
239static void copyMustTailReturn(BasicBlock *SplitBB, Instruction *CI,
240 Instruction *NewCI) {
241 bool IsVoid = SplitBB->getParent()->getReturnType()->isVoidTy();
242 auto II = std::next(CI->getIterator());
243
244 BitCastInst* BCI = dyn_cast<BitCastInst>(&*II);
245 if (BCI)
246 ++II;
247
248 ReturnInst* RI = dyn_cast<ReturnInst>(&*II);
249 assert(RI && "`musttail` call must be followed by `ret` instruction");
250
251 Instruction *TI = SplitBB->getTerminator();
252 Value *V = NewCI;
253 if (BCI)
254 V = cloneInstForMustTail(BCI, TI, V);
255 cloneInstForMustTail(RI, TI, IsVoid ? nullptr : V);
256
257 // FIXME: remove TI here, `DuplicateInstructionsInSplitBetween` has a bug
258 // that prevents doing this now.
259}
260
261/// For each (predecessor, conditions from predecessors) pair, it will split the
262/// basic block containing the call site, hook it up to the predecessor and
263/// replace the call instruction with new call instructions, which contain
264/// constraints based on the conditions from their predecessors.
265/// For example, in the IR below with an OR condition, the call-site can
266/// be split. In this case, Preds for Tail is [(Header, a == null),
267/// (TBB, a != null, b == null)]. Tail is replaced by 2 split blocks, containing
268/// CallInst1, which has constraints based on the conditions from Head and
269/// CallInst2, which has constraints based on the conditions coming from TBB.
270///
271/// From :
272///
273/// Header:
274/// %c = icmp eq i32* %a, null
275/// br i1 %c %Tail, %TBB
276/// TBB:
277/// %c2 = icmp eq i32* %b, null
278/// br i1 %c %Tail, %End
279/// Tail:
280/// %ca = call i1 @callee (i32* %a, i32* %b)
281///
282/// to :
283///
284/// Header: // PredBB1 is Header
285/// %c = icmp eq i32* %a, null
286/// br i1 %c %Tail-split1, %TBB
287/// TBB: // PredBB2 is TBB
288/// %c2 = icmp eq i32* %b, null
289/// br i1 %c %Tail-split2, %End
290/// Tail-split1:
291/// %ca1 = call @callee (i32* null, i32* %b) // CallInst1
292/// br %Tail
293/// Tail-split2:
294/// %ca2 = call @callee (i32* nonnull %a, i32* null) // CallInst2
295/// br %Tail
296/// Tail:
297/// %p = phi i1 [%ca1, %Tail-split1],[%ca2, %Tail-split2]
298///
299/// Note that in case any arguments at the call-site are constrained by its
300/// predecessors, new call-sites with more constrained arguments will be
301/// created in createCallSitesOnPredicatedArgument().
302static void splitCallSite(CallBase &CB,
303 ArrayRef<std::pair<BasicBlock *, ConditionsTy>> Preds,
304 DomTreeUpdater &DTU) {
305 BasicBlock *TailBB = CB.getParent();
306 bool IsMustTailCall = CB.isMustTailCall();
307
308 PHINode *CallPN = nullptr;
309
310 // `musttail` calls must be followed by optional `bitcast`, and `ret`. The
311 // split blocks will be terminated right after that so there're no users for
312 // this phi in a `TailBB`.
313 if (!IsMustTailCall && !CB.use_empty()) {
314 CallPN = PHINode::Create(CB.getType(), Preds.size(), "phi.call");
315 CallPN->setDebugLoc(CB.getDebugLoc());
316 }
317
318 LLVM_DEBUG(dbgs() << "split call-site : " << CB << " into \n");
319
320 assert(Preds.size() == 2 && "The ValueToValueMaps array has size 2.");
321 // ValueToValueMapTy is neither copy nor moveable, so we use a simple array
322 // here.
323 ValueToValueMapTy ValueToValueMaps[2];
324 for (unsigned i = 0; i < Preds.size(); i++) {
325 BasicBlock *PredBB = Preds[i].first;
327 TailBB, PredBB, &*std::next(CB.getIterator()), ValueToValueMaps[i],
328 DTU);
329 assert(SplitBlock && "Unexpected new basic block split.");
330
331 auto *NewCI =
332 cast<CallBase>(&*std::prev(SplitBlock->getTerminator()->getIterator()));
333 addConditions(*NewCI, Preds[i].second);
334
335 // Handle PHIs used as arguments in the call-site.
336 for (PHINode &PN : TailBB->phis()) {
337 unsigned ArgNo = 0;
338 for (auto &CI : CB.args()) {
339 if (&*CI == &PN) {
340 NewCI->setArgOperand(ArgNo, PN.getIncomingValueForBlock(SplitBlock));
341 }
342 ++ArgNo;
343 }
344 }
345 LLVM_DEBUG(dbgs() << " " << *NewCI << " in " << SplitBlock->getName()
346 << "\n");
347 if (CallPN)
348 CallPN->addIncoming(NewCI, SplitBlock);
349
350 // Clone and place bitcast and return instructions before `TI`
351 if (IsMustTailCall)
352 copyMustTailReturn(SplitBlock, &CB, NewCI);
353 }
354
355 NumCallSiteSplit++;
356
357 // FIXME: remove TI in `copyMustTailReturn`
358 if (IsMustTailCall) {
359 // Remove superfluous `br` terminators from the end of the Split blocks
360 // NOTE: Removing terminator removes the SplitBlock from the TailBB's
361 // predecessors. Therefore we must get complete list of Splits before
362 // attempting removal.
364 assert(Splits.size() == 2 && "Expected exactly 2 splits!");
365 for (BasicBlock *BB : Splits) {
366 BB->getTerminator()->eraseFromParent();
367 DTU.applyUpdatesPermissive({{DominatorTree::Delete, BB, TailBB}});
368 }
369
370 // Erase the tail block once done with musttail patching
371 DTU.deleteBB(TailBB);
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 CB.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 = CB.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 NewPN->setDebugLoc(CurrentI->getDebugLoc());
399 for (auto &Mapping : ValueToValueMaps)
400 NewPN->addIncoming(Mapping[CurrentI],
401 cast<Instruction>(Mapping[CurrentI])->getParent());
402 NewPN->insertBefore(&*TailBB->begin());
403 CurrentI->replaceAllUsesWith(NewPN);
404 }
405 CurrentI->eraseFromParent();
406 // We are done once we handled the first original instruction in TailBB.
407 if (CurrentI == OriginalBegin)
408 break;
409 }
410}
411
412// Return true if the call-site has an argument which is a PHI with only
413// constant incoming values.
414static bool isPredicatedOnPHI(CallBase &CB) {
415 BasicBlock *Parent = CB.getParent();
416 if (&CB != Parent->getFirstNonPHIOrDbg())
417 return false;
418
419 for (auto &PN : Parent->phis()) {
420 for (auto &Arg : CB.args()) {
421 if (&*Arg != &PN)
422 continue;
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 return false;
435}
436
438
439// Check if any of the arguments in CS are predicated on a PHI node and return
440// the set of predecessors we should use for splitting.
442 if (!isPredicatedOnPHI(CB))
443 return {};
444
445 auto Preds = getTwoPredecessors(CB.getParent());
446 return {{Preds[0], {}}, {Preds[1], {}}};
447}
448
449// Checks if any of the arguments in CS are predicated in a predecessor and
450// returns a list of predecessors with the conditions that hold on their edges
451// to CS.
453 DomTreeUpdater &DTU) {
454 auto Preds = getTwoPredecessors(CB.getParent());
455 if (Preds[0] == Preds[1])
456 return {};
457
458 // We can stop recording conditions once we reached the immediate dominator
459 // for the block containing the call site. Conditions in predecessors of the
460 // that node will be the same for all paths to the call site and splitting
461 // is not beneficial.
462 assert(DTU.hasDomTree() && "We need a DTU with a valid DT!");
463 auto *CSDTNode = DTU.getDomTree().getNode(CB.getParent());
464 BasicBlock *StopAt = CSDTNode ? CSDTNode->getIDom()->getBlock() : nullptr;
465
467 for (auto *Pred : llvm::reverse(Preds)) {
468 ConditionsTy Conditions;
469 // Record condition on edge BB(CS) <- Pred
470 recordCondition(CB, Pred, CB.getParent(), Conditions);
471 // Record conditions following Pred's single predecessors.
472 recordConditions(CB, Pred, Conditions, StopAt);
473 PredsCS.push_back({Pred, Conditions});
474 }
475
476 if (all_of(PredsCS, [](const std::pair<BasicBlock *, ConditionsTy> &P) {
477 return P.second.empty();
478 }))
479 return {};
480
481 return PredsCS;
482}
483
485 DomTreeUpdater &DTU) {
486 // Check if we can split the call site.
487 if (!CB.arg_size() || !canSplitCallSite(CB, TTI))
488 return false;
489
490 auto PredsWithConds = shouldSplitOnPredicatedArgument(CB, DTU);
491 if (PredsWithConds.empty())
492 PredsWithConds = shouldSplitOnPHIPredicatedArgument(CB);
493 if (PredsWithConds.empty())
494 return false;
495
496 splitCallSite(CB, PredsWithConds, DTU);
497 return true;
498}
499
502
503 DomTreeUpdater DTU(&DT, DomTreeUpdater::UpdateStrategy::Lazy);
504 bool Changed = false;
506 auto II = BB.getFirstNonPHIOrDbg()->getIterator();
507 auto IE = BB.getTerminator()->getIterator();
508 // Iterate until we reach the terminator instruction. tryToSplitCallSite
509 // can replace BB's terminator in case BB is a successor of itself. In that
510 // case, IE will be invalidated and we also have to check the current
511 // terminator.
512 while (II != IE && &*II != BB.getTerminator()) {
513 CallBase *CB = dyn_cast<CallBase>(&*II++);
514 if (!CB || isa<IntrinsicInst>(CB) || isInstructionTriviallyDead(CB, &TLI))
515 continue;
516
517 Function *Callee = CB->getCalledFunction();
518 if (!Callee || Callee->isDeclaration())
519 continue;
520
521 // Successful musttail call-site splits result in erased CI and erased BB.
522 // Check if such path is possible before attempting the splitting.
523 bool IsMustTail = CB->isMustTailCall();
524
525 Changed |= tryToSplitCallSite(*CB, TTI, DTU);
526
527 // There're no interesting instructions after this. The call site
528 // itself might have been erased on splitting.
529 if (IsMustTail)
530 break;
531 }
532 }
533 return Changed;
534}
535
538 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
539 auto &TTI = AM.getResult<TargetIRAnalysis>(F);
540 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
541
542 if (!doCallSiteSplitting(F, TLI, TTI, DT))
543 return PreservedAnalyses::all();
546 return PA;
547}
static const Function * getParent(const Value *V)
BlockVerifier::State From
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static void addConditions(CallBase &CB, const ConditionsTy &Conditions)
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...
static bool isCondRelevantToAnyCallArgument(ICmpInst *Cmp, CallBase &CB)
static bool doCallSiteSplitting(Function &F, TargetLibraryInfo &TLI, TargetTransformInfo &TTI, DominatorTree &DT)
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.
static bool isPredicatedOnPHI(CallBase &CB)
static PredsWithCondsTy shouldSplitOnPredicatedArgument(CallBase &CB, DomTreeUpdater &DTU)
static Instruction * cloneInstForMustTail(Instruction *I, Instruction *Before, Value *V)
static void addNonNullAttribute(CallBase &CB, Value *Op)
static void setConstantInArgument(CallBase &CB, Value *Op, Constant *ConstValue)
static bool canSplitCallSite(CallBase &CB, TargetTransformInfo &TTI)
static bool tryToSplitCallSite(CallBase &CB, TargetTransformInfo &TTI, DomTreeUpdater &DTU)
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...
static PredsWithCondsTy shouldSplitOnPHIPredicatedArgument(CallBase &CB)
static SmallVector< BasicBlock *, 2 > getTwoPredecessors(BasicBlock *BB)
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.
std::pair< ICmpInst *, unsigned > ConditionTy
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...
#define LLVM_DEBUG(X)
Definition: Debug.h:101
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define P(N)
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
This pass exposes codegen information to IR-level passes.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:335
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:393
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:112
reverse_iterator rend()
Definition: BasicBlock.h:342
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:227
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:533
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:127
bool canSplitPredecessors() const
Definition: BasicBlock.cpp:382
This class represents a no-op cast from one type to another.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1190
void removeParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
Removes the attribute from the given argument.
Definition: InstrTypes.h:1588
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
Definition: InstrTypes.h:1412
bool cannotDuplicate() const
Determine if the invoke cannot be duplicated.
Definition: InstrTypes.h:1930
bool paramHasAttr(unsigned ArgNo, Attribute::AttrKind Kind) const
Determine whether the argument or parameter has the given attribute.
User::op_iterator arg_begin()
Return the iterator pointing to the beginning of the argument list.
Definition: InstrTypes.h:1332
bool isMustTailCall() const
Tests if this call site must be tail call optimized.
void setArgOperand(unsigned i, Value *v)
Definition: InstrTypes.h:1362
User::op_iterator arg_end()
Return the iterator pointing to the end of the argument list.
Definition: InstrTypes.h:1338
bool isConvergent() const
Determine if the invoke is convergent.
Definition: InstrTypes.h:1938
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1348
unsigned arg_size() const
Definition: InstrTypes.h:1355
void addParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
Adds the attribute to the indicated argument.
Definition: InstrTypes.h:1541
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:711
This is an important base class in LLVM.
Definition: Constant.h:41
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
Definition: Constants.cpp:76
This class represents an Operation in the Expression.
bool hasDomTree() const
Returns true if it holds a DominatorTree.
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:181
This instruction compares its operands according to the predicate given to the constructor.
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
Definition: Instruction.cpp:89
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:392
const BasicBlock * getParent() const
Definition: Instruction.h:90
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:83
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:389
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
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...
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
Return a value (possibly void), from a function.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:384
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:366
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
size_t size() const
Definition: SmallVector.h:91
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
Analysis pass providing the TargetTransformInfo.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
@ TCK_CodeSize
Instruction code size.
InstructionCost getInstructionCost(const User *U, ArrayRef< const Value * > Operands, TargetCostKind CostKind) const
Estimate the cost of a given IR user when lowered.
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:255
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:140
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:535
bool use_empty() const
Definition: Value.h:344
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
reverse_self_iterator getReverseIterator()
Definition: ilist_node.h:85
self_iterator getIterator()
Definition: ilist_node.h:82
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:144
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:1727
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
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:666
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...
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:398
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:429
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="", bool Before=false)
Split the specified block at the specified instruction.
auto predecessors(const MachineBasicBlock *BB)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Run the pass over the function.