LLVM: lib/Transforms/Scalar/CallSiteSplitting.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
69
70using namespace llvm;
71using namespace PatternMatch;
72
73#define DEBUG_TYPE "callsite-splitting"
74
75STATISTIC(NumCallSiteSplit, "Number of call-site split");
76
77
78
79
82 cl::desc("Only allow instructions before a call, if "
83 "their cost is below DuplicationThreshold"),
85
87 unsigned ArgNo = 0;
88 for (auto &I : CB.args()) {
91 ++ArgNo;
92 }
93}
94
97 unsigned ArgNo = 0;
98 for (auto &I : CB.args()) {
100
101
104 }
105 ++ArgNo;
106 }
107}
108
110 assert(isa(Cmp->getOperand(1)) && "Expected a constant operand.");
111 Value *Op0 = Cmp->getOperand(0);
112 unsigned ArgNo = 0;
114
115 if (isa(*I) || CB.paramHasAttr(ArgNo, Attribute::NonNull))
116 continue;
117
118 if (*I == Op0)
119 return true;
120 }
121 return false;
122}
123
126
127
128
131 auto *BI = dyn_cast(From->getTerminator());
132 if (!BI || !BI->isConditional())
133 return;
134
136 Value *Cond = BI->getCondition();
138 return;
139
141 if (Pred == ICmpInst::ICMP_EQ || Pred == ICmpInst::ICMP_NE)
143 Conditions.push_back({Cmp, From->getTerminator()->getSuccessor(0) == To
144 ? Pred
145 : Cmp->getInverseCmpPredicate()});
146}
147
148
149
150
151
157 while (To != StopAt && !Visited.count(From->getSinglePredecessor()) &&
158 (From = From->getSinglePredecessor())) {
162 }
163}
164
166 for (const auto &Cond : Conditions) {
167 Value *Arg = Cond.first->getOperand(0);
168 Constant *ConstVal = cast(Cond.first->getOperand(1));
169 if (Cond.second == ICmpInst::ICMP_EQ)
172 assert(Cond.second == ICmpInst::ICMP_NE);
174 }
175 }
176}
177
180 assert(Preds.size() == 2 && "Expected exactly 2 predecessors!");
181 return Preds;
182}
183
186 return false;
187
188
189
190 if (!isa(CB))
191 return false;
192
194
196 if (Preds.size() != 2 || isa(Preds[0]->getTerminator()) ||
197 isa(Preds[1]->getTerminator()))
198 return false;
199
200
201
203 return false;
204
205
206
207
208
210 for (auto &InstBeforeCall :
215 return false;
216 }
217
218 return true;
219}
220
224 Copy->setName(I->getName());
225 Copy->insertBefore(Before);
226 if (V)
227 Copy->setOperand(0, V);
228 return Copy;
229}
230
231
232
233
234
235
236
237
238
243
245 if (BCI)
246 ++II;
247
249 assert(RI && "`musttail` call must be followed by `ret` instruction");
250
252 Value *V = NewCI;
253 if (BCI)
256
257
258
259}
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
303 ArrayRef<std::pair<BasicBlock *, ConditionsTy>> Preds,
307
308 PHINode *CallPN = nullptr;
309
310
311
312
313 if (!IsMustTailCall && !CB.use_empty()) {
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
322
324 for (unsigned i = 0; i < Preds.size(); i++) {
327 TailBB, PredBB, &*std::next(CB.getIterator()), ValueToValueMaps[i],
328 DTU);
330
331 auto *NewCI =
334
335
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 }
346 << "\n");
347 if (CallPN)
349
350
351 if (IsMustTailCall)
353 }
354
355 NumCallSiteSplit++;
356
357
358 if (IsMustTailCall) {
359
360
361
362
364 assert(Splits.size() == 2 && "Expected exactly 2 splits!");
366 BB->getTerminator()->eraseFromParent();
368 }
369
370
372 return;
373 }
374
376
377 if (CallPN) {
378 CallPN->insertBefore(*TailBB, OriginalBegin);
380 }
381
382
383
384
385
386
387
388
390 Instruction *OriginalBeginInst = &*OriginalBegin;
391 while (I != TailBB->rend()) {
394
395
396 if (isa(CurrentI))
397 continue;
400 for (auto &Mapping : ValueToValueMaps)
402 cast(Mapping[CurrentI])->getParent());
404 CurrentI->replaceAllUsesWith(NewPN);
405 }
408
409 if (CurrentI == OriginalBeginInst)
410 break;
411 }
412}
413
414
415
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(PN.getIncomingValue(0)) &&
432 isa(PN.getIncomingValue(1)))
433 return true;
434 }
435 }
436 return false;
437}
438
440
441
442
445 return {};
446
448 return {{Preds[0], {}}, {Preds[1], {}}};
449}
450
451
452
453
457 if (Preds[0] == Preds[1])
458 return {};
459
460
461
462
463
464 assert(DTU.hasDomTree() && "We need a DTU with a valid DT!");
466 BasicBlock *StopAt = CSDTNode ? CSDTNode->getIDom()->getBlock() : nullptr;
467
471
473
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
488
490 return false;
491
493 if (PredsWithConds.empty())
495 if (PredsWithConds.empty())
496 return false;
497
499 return true;
500}
501
504
505 DomTreeUpdater DTU(&DT, DomTreeUpdater::UpdateStrategy::Lazy);
506 bool Changed = false;
508 auto II = BB.getFirstNonPHIOrDbg()->getIterator();
509 auto IE = BB.getTerminator()->getIterator();
510
511
512
513
514 while (II != IE && &*II != BB.getTerminator()) {
515 CallBase *CB = dyn_cast(&*II++);
517 continue;
518
520 if (!Callee || Callee->isDeclaration())
521 continue;
522
523
524
526
528
529
530
531 if (IsMustTail)
532 break;
533 }
534 }
535 return Changed;
536}
537
543
548 return PA;
549}
static const Function * getParent(const Value *V)
BlockVerifier::State From
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...
uint64_t IntrinsicInst * II
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)
This pass exposes codegen information to IR-level passes.
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
const Function * getParent() const
Return the enclosing method, or null if none.
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,...
InstListType::iterator iterator
Instruction iterators...
bool isEHPad() const
Return true if this basic block is an exception handling block.
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...
bool canSplitPredecessors() const
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...
void removeParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
Removes the attribute from the given argument.
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
bool cannotDuplicate() const
Determine if the invoke cannot be duplicated.
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.
bool isMustTailCall() const
Tests if this call site must be tail call optimized.
void setArgOperand(unsigned i, Value *v)
User::op_iterator arg_end()
Return the iterator pointing to the end of the argument list.
bool isConvergent() const
Determine if the invoke is convergent.
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
unsigned arg_size() const
void addParamAttr(unsigned ArgNo, Attribute::AttrKind Kind)
Adds the attribute to the indicated argument.
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
This is an important base class in LLVM.
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
This class represents an Operation in the Expression.
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
Analysis pass which computes a DominatorTree.
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.
Type * getReturnType() const
Returns the type of the ret val.
DomTreeT & getDomTree()
Flush DomTree updates and return DomTree.
void applyUpdatesPermissive(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
bool hasDomTree() const
Returns true if it holds a DomTreeT.
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.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
void dropDbgRecords()
Erase any DbgRecords attached to this instruction.
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="", InsertPosition 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.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void preserve()
Mark an analysis as preserved.
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.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
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.
bool isVoidTy() const
Return true if this is 'void'.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
StringRef getName() const
Return a constant reference to the value's name.
const ParentTy * getParent() const
reverse_self_iterator getReverseIterator()
self_iterator getIterator()
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
bool match(Val *V, const Pattern &P)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
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...
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.
auto reverse(ContainerTy &&C)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
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.