1 //===- InlineCost.cpp - Cost analysis for inliner -------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements inline cost analysis.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Analysis/InlineCost.h"
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/SetVector.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/Analysis/AssumptionCache.h"
21 #include "llvm/Analysis/CodeMetrics.h"
22 #include "llvm/Analysis/ConstantFolding.h"
23 #include "llvm/Analysis/InstructionSimplify.h"
24 #include "llvm/Analysis/ProfileSummaryInfo.h"
25 #include "llvm/Analysis/TargetTransformInfo.h"
26 #include "llvm/IR/CallSite.h"
27 #include "llvm/IR/CallingConv.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/GetElementPtrTypeIterator.h"
30 #include "llvm/IR/GlobalAlias.h"
31 #include "llvm/IR/InstVisitor.h"
32 #include "llvm/IR/IntrinsicInst.h"
33 #include "llvm/IR/Operator.h"
34 #include "llvm/Support/Debug.h"
35 #include "llvm/Support/raw_ostream.h"
39 #define DEBUG_TYPE "inline-cost"
41 STATISTIC(NumCallsAnalyzed, "Number of call sites analyzed");
43 static cl::opt<int> InlineThreshold(
44 "inline-threshold", cl::Hidden, cl::init(225), cl::ZeroOrMore,
45 cl::desc("Control the amount of inlining to perform (default = 225)"));
47 static cl::opt<int> HintThreshold(
48 "inlinehint-threshold", cl::Hidden, cl::init(325),
49 cl::desc("Threshold for inlining functions with inline hint"));
51 // We introduce this threshold to help performance of instrumentation based
52 // PGO before we actually hook up inliner with analysis passes such as BPI and
54 static cl::opt<int> ColdThreshold(
55 "inlinecold-threshold", cl::Hidden, cl::init(225),
56 cl::desc("Threshold for inlining functions with cold attribute"));
59 HotCallSiteThreshold("hot-callsite-threshold", cl::Hidden, cl::init(3000),
61 cl::desc("Threshold for hot callsites "));
65 class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
66 typedef InstVisitor<CallAnalyzer, bool> Base;
67 friend class InstVisitor<CallAnalyzer, bool>;
69 /// The TargetTransformInfo available for this compilation.
70 const TargetTransformInfo &TTI;
72 /// Getter for the cache of @llvm.assume intrinsics.
73 std::function<AssumptionCache &(Function &)> &GetAssumptionCache;
75 /// Profile summary information.
76 ProfileSummaryInfo *PSI;
78 /// The called function.
81 /// The candidate callsite being analyzed. Please do not use this to do
82 /// analysis in the caller function; we want the inline cost query to be
83 /// easily cacheable. Instead, use the cover function paramHasAttr.
86 /// Tunable parameters that control the analysis.
87 const InlineParams &Params;
92 bool IsCallerRecursive;
94 bool ExposesReturnsTwice;
95 bool HasDynamicAlloca;
96 bool ContainsNoDuplicateCall;
101 /// Number of bytes allocated statically by the callee.
102 uint64_t AllocatedSize;
103 unsigned NumInstructions, NumVectorInstructions;
104 int FiftyPercentVectorBonus, TenPercentVectorBonus;
107 /// While we walk the potentially-inlined instructions, we build up and
108 /// maintain a mapping of simplified values specific to this callsite. The
109 /// idea is to propagate any special information we have about arguments to
110 /// this call through the inlinable section of the function, and account for
111 /// likely simplifications post-inlining. The most important aspect we track
112 /// is CFG altering simplifications -- when we prove a basic block dead, that
113 /// can cause dramatic shifts in the cost of inlining a function.
114 DenseMap<Value *, Constant *> SimplifiedValues;
116 /// Keep track of the values which map back (through function arguments) to
117 /// allocas on the caller stack which could be simplified through SROA.
118 DenseMap<Value *, Value *> SROAArgValues;
120 /// The mapping of caller Alloca values to their accumulated cost savings. If
121 /// we have to disable SROA for one of the allocas, this tells us how much
122 /// cost must be added.
123 DenseMap<Value *, int> SROAArgCosts;
125 /// Keep track of values which map to a pointer base and constant offset.
126 DenseMap<Value *, std::pair<Value *, APInt>> ConstantOffsetPtrs;
128 // Custom simplification helper routines.
129 bool isAllocaDerivedArg(Value *V);
130 bool lookupSROAArgAndCost(Value *V, Value *&Arg,
131 DenseMap<Value *, int>::iterator &CostIt);
132 void disableSROA(DenseMap<Value *, int>::iterator CostIt);
133 void disableSROA(Value *V);
134 void accumulateSROACost(DenseMap<Value *, int>::iterator CostIt,
135 int InstructionCost);
136 bool isGEPOffsetConstant(GetElementPtrInst &GEP);
137 bool accumulateGEPOffset(GEPOperator &GEP, APInt &Offset);
138 bool simplifyCallSite(Function *F, CallSite CS);
139 ConstantInt *stripAndComputeInBoundsConstantOffsets(Value *&V);
141 /// Return true if the given argument to the function being considered for
142 /// inlining has the given attribute set either at the call site or the
143 /// function declaration. Primarily used to inspect call site specific
144 /// attributes since these can be more precise than the ones on the callee
146 bool paramHasAttr(Argument *A, Attribute::AttrKind Attr);
148 /// Return true if the given value is known non null within the callee if
149 /// inlined through this particular callsite.
150 bool isKnownNonNullInCallee(Value *V);
152 /// Update Threshold based on callsite properties such as callee
153 /// attributes and callee hotness for PGO builds. The Callee is explicitly
154 /// passed to support analyzing indirect calls whose target is inferred by
156 void updateThreshold(CallSite CS, Function &Callee);
158 /// Return true if size growth is allowed when inlining the callee at CS.
159 bool allowSizeGrowth(CallSite CS);
161 // Custom analysis routines.
162 bool analyzeBlock(BasicBlock *BB, SmallPtrSetImpl<const Value *> &EphValues);
164 // Disable several entry points to the visitor so we don't accidentally use
165 // them by declaring but not defining them here.
166 void visit(Module *);
167 void visit(Module &);
168 void visit(Function *);
169 void visit(Function &);
170 void visit(BasicBlock *);
171 void visit(BasicBlock &);
173 // Provide base case for our instruction visit.
174 bool visitInstruction(Instruction &I);
176 // Our visit overrides.
177 bool visitAlloca(AllocaInst &I);
178 bool visitPHI(PHINode &I);
179 bool visitGetElementPtr(GetElementPtrInst &I);
180 bool visitBitCast(BitCastInst &I);
181 bool visitPtrToInt(PtrToIntInst &I);
182 bool visitIntToPtr(IntToPtrInst &I);
183 bool visitCastInst(CastInst &I);
184 bool visitUnaryInstruction(UnaryInstruction &I);
185 bool visitCmpInst(CmpInst &I);
186 bool visitSub(BinaryOperator &I);
187 bool visitBinaryOperator(BinaryOperator &I);
188 bool visitLoad(LoadInst &I);
189 bool visitStore(StoreInst &I);
190 bool visitExtractValue(ExtractValueInst &I);
191 bool visitInsertValue(InsertValueInst &I);
192 bool visitCallSite(CallSite CS);
193 bool visitReturnInst(ReturnInst &RI);
194 bool visitBranchInst(BranchInst &BI);
195 bool visitSwitchInst(SwitchInst &SI);
196 bool visitIndirectBrInst(IndirectBrInst &IBI);
197 bool visitResumeInst(ResumeInst &RI);
198 bool visitCleanupReturnInst(CleanupReturnInst &RI);
199 bool visitCatchReturnInst(CatchReturnInst &RI);
200 bool visitUnreachableInst(UnreachableInst &I);
203 CallAnalyzer(const TargetTransformInfo &TTI,
204 std::function<AssumptionCache &(Function &)> &GetAssumptionCache,
205 ProfileSummaryInfo *PSI, Function &Callee, CallSite CSArg,
206 const InlineParams &Params)
207 : TTI(TTI), GetAssumptionCache(GetAssumptionCache), PSI(PSI), F(Callee),
208 CandidateCS(CSArg), Params(Params), Threshold(Params.DefaultThreshold),
209 Cost(0), IsCallerRecursive(false), IsRecursiveCall(false),
210 ExposesReturnsTwice(false), HasDynamicAlloca(false),
211 ContainsNoDuplicateCall(false), HasReturn(false), HasIndirectBr(false),
212 HasFrameEscape(false), AllocatedSize(0), NumInstructions(0),
213 NumVectorInstructions(0), FiftyPercentVectorBonus(0),
214 TenPercentVectorBonus(0), VectorBonus(0), NumConstantArgs(0),
215 NumConstantOffsetPtrArgs(0), NumAllocaArgs(0), NumConstantPtrCmps(0),
216 NumConstantPtrDiffs(0), NumInstructionsSimplified(0),
217 SROACostSavings(0), SROACostSavingsLost(0) {}
219 bool analyzeCall(CallSite CS);
221 int getThreshold() { return Threshold; }
222 int getCost() { return Cost; }
224 // Keep a bunch of stats about the cost savings found so we can print them
225 // out when debugging.
226 unsigned NumConstantArgs;
227 unsigned NumConstantOffsetPtrArgs;
228 unsigned NumAllocaArgs;
229 unsigned NumConstantPtrCmps;
230 unsigned NumConstantPtrDiffs;
231 unsigned NumInstructionsSimplified;
232 unsigned SROACostSavings;
233 unsigned SROACostSavingsLost;
240 /// \brief Test whether the given value is an Alloca-derived function argument.
241 bool CallAnalyzer::isAllocaDerivedArg(Value *V) {
242 return SROAArgValues.count(V);
245 /// \brief Lookup the SROA-candidate argument and cost iterator which V maps to.
246 /// Returns false if V does not map to a SROA-candidate.
247 bool CallAnalyzer::lookupSROAArgAndCost(
248 Value *V, Value *&Arg, DenseMap<Value *, int>::iterator &CostIt) {
249 if (SROAArgValues.empty() || SROAArgCosts.empty())
252 DenseMap<Value *, Value *>::iterator ArgIt = SROAArgValues.find(V);
253 if (ArgIt == SROAArgValues.end())
257 CostIt = SROAArgCosts.find(Arg);
258 return CostIt != SROAArgCosts.end();
261 /// \brief Disable SROA for the candidate marked by this cost iterator.
263 /// This marks the candidate as no longer viable for SROA, and adds the cost
264 /// savings associated with it back into the inline cost measurement.
265 void CallAnalyzer::disableSROA(DenseMap<Value *, int>::iterator CostIt) {
266 // If we're no longer able to perform SROA we need to undo its cost savings
267 // and prevent subsequent analysis.
268 Cost += CostIt->second;
269 SROACostSavings -= CostIt->second;
270 SROACostSavingsLost += CostIt->second;
271 SROAArgCosts.erase(CostIt);
274 /// \brief If 'V' maps to a SROA candidate, disable SROA for it.
275 void CallAnalyzer::disableSROA(Value *V) {
277 DenseMap<Value *, int>::iterator CostIt;
278 if (lookupSROAArgAndCost(V, SROAArg, CostIt))
282 /// \brief Accumulate the given cost for a particular SROA candidate.
283 void CallAnalyzer::accumulateSROACost(DenseMap<Value *, int>::iterator CostIt,
284 int InstructionCost) {
285 CostIt->second += InstructionCost;
286 SROACostSavings += InstructionCost;
289 /// \brief Check whether a GEP's indices are all constant.
291 /// Respects any simplified values known during the analysis of this callsite.
292 bool CallAnalyzer::isGEPOffsetConstant(GetElementPtrInst &GEP) {
293 for (User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end(); I != E; ++I)
294 if (!isa<Constant>(*I) && !SimplifiedValues.lookup(*I))
300 /// \brief Accumulate a constant GEP offset into an APInt if possible.
302 /// Returns false if unable to compute the offset for any reason. Respects any
303 /// simplified values known during the analysis of this callsite.
304 bool CallAnalyzer::accumulateGEPOffset(GEPOperator &GEP, APInt &Offset) {
305 const DataLayout &DL = F.getParent()->getDataLayout();
306 unsigned IntPtrWidth = DL.getPointerSizeInBits();
307 assert(IntPtrWidth == Offset.getBitWidth());
309 for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP);
311 ConstantInt *OpC = dyn_cast<ConstantInt>(GTI.getOperand());
313 if (Constant *SimpleOp = SimplifiedValues.lookup(GTI.getOperand()))
314 OpC = dyn_cast<ConstantInt>(SimpleOp);
320 // Handle a struct index, which adds its field offset to the pointer.
321 if (StructType *STy = GTI.getStructTypeOrNull()) {
322 unsigned ElementIdx = OpC->getZExtValue();
323 const StructLayout *SL = DL.getStructLayout(STy);
324 Offset += APInt(IntPtrWidth, SL->getElementOffset(ElementIdx));
328 APInt TypeSize(IntPtrWidth, DL.getTypeAllocSize(GTI.getIndexedType()));
329 Offset += OpC->getValue().sextOrTrunc(IntPtrWidth) * TypeSize;
334 bool CallAnalyzer::visitAlloca(AllocaInst &I) {
335 // Check whether inlining will turn a dynamic alloca into a static
336 // alloca and handle that case.
337 if (I.isArrayAllocation()) {
338 Constant *Size = SimplifiedValues.lookup(I.getArraySize());
339 if (auto *AllocSize = dyn_cast_or_null<ConstantInt>(Size)) {
340 const DataLayout &DL = F.getParent()->getDataLayout();
341 Type *Ty = I.getAllocatedType();
342 AllocatedSize = SaturatingMultiplyAdd(
343 AllocSize->getLimitedValue(), DL.getTypeAllocSize(Ty), AllocatedSize);
344 return Base::visitAlloca(I);
348 // Accumulate the allocated size.
349 if (I.isStaticAlloca()) {
350 const DataLayout &DL = F.getParent()->getDataLayout();
351 Type *Ty = I.getAllocatedType();
352 AllocatedSize = SaturatingAdd(DL.getTypeAllocSize(Ty), AllocatedSize);
355 // We will happily inline static alloca instructions.
356 if (I.isStaticAlloca())
357 return Base::visitAlloca(I);
359 // FIXME: This is overly conservative. Dynamic allocas are inefficient for
360 // a variety of reasons, and so we would like to not inline them into
361 // functions which don't currently have a dynamic alloca. This simply
362 // disables inlining altogether in the presence of a dynamic alloca.
363 HasDynamicAlloca = true;
367 bool CallAnalyzer::visitPHI(PHINode &I) {
368 // FIXME: We should potentially be tracking values through phi nodes,
369 // especially when they collapse to a single value due to deleted CFG edges
372 // FIXME: We need to propagate SROA *disabling* through phi nodes, even
373 // though we don't want to propagate it's bonuses. The idea is to disable
374 // SROA if it *might* be used in an inappropriate manner.
376 // Phi nodes are always zero-cost.
380 bool CallAnalyzer::visitGetElementPtr(GetElementPtrInst &I) {
382 DenseMap<Value *, int>::iterator CostIt;
384 lookupSROAArgAndCost(I.getPointerOperand(), SROAArg, CostIt);
386 // Try to fold GEPs of constant-offset call site argument pointers. This
387 // requires target data and inbounds GEPs.
388 if (I.isInBounds()) {
389 // Check if we have a base + offset for the pointer.
390 Value *Ptr = I.getPointerOperand();
391 std::pair<Value *, APInt> BaseAndOffset = ConstantOffsetPtrs.lookup(Ptr);
392 if (BaseAndOffset.first) {
393 // Check if the offset of this GEP is constant, and if so accumulate it
395 if (!accumulateGEPOffset(cast<GEPOperator>(I), BaseAndOffset.second)) {
396 // Non-constant GEPs aren't folded, and disable SROA.
402 // Add the result as a new mapping to Base + Offset.
403 ConstantOffsetPtrs[&I] = BaseAndOffset;
405 // Also handle SROA candidates here, we already know that the GEP is
406 // all-constant indexed.
408 SROAArgValues[&I] = SROAArg;
414 if (isGEPOffsetConstant(I)) {
416 SROAArgValues[&I] = SROAArg;
418 // Constant GEPs are modeled as free.
422 // Variable GEPs will require math and will disable SROA.
428 bool CallAnalyzer::visitBitCast(BitCastInst &I) {
429 // Propagate constants through bitcasts.
430 Constant *COp = dyn_cast<Constant>(I.getOperand(0));
432 COp = SimplifiedValues.lookup(I.getOperand(0));
434 if (Constant *C = ConstantExpr::getBitCast(COp, I.getType())) {
435 SimplifiedValues[&I] = C;
439 // Track base/offsets through casts
440 std::pair<Value *, APInt> BaseAndOffset =
441 ConstantOffsetPtrs.lookup(I.getOperand(0));
442 // Casts don't change the offset, just wrap it up.
443 if (BaseAndOffset.first)
444 ConstantOffsetPtrs[&I] = BaseAndOffset;
446 // Also look for SROA candidates here.
448 DenseMap<Value *, int>::iterator CostIt;
449 if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt))
450 SROAArgValues[&I] = SROAArg;
452 // Bitcasts are always zero cost.
456 bool CallAnalyzer::visitPtrToInt(PtrToIntInst &I) {
457 // Propagate constants through ptrtoint.
458 Constant *COp = dyn_cast<Constant>(I.getOperand(0));
460 COp = SimplifiedValues.lookup(I.getOperand(0));
462 if (Constant *C = ConstantExpr::getPtrToInt(COp, I.getType())) {
463 SimplifiedValues[&I] = C;
467 // Track base/offset pairs when converted to a plain integer provided the
468 // integer is large enough to represent the pointer.
469 unsigned IntegerSize = I.getType()->getScalarSizeInBits();
470 const DataLayout &DL = F.getParent()->getDataLayout();
471 if (IntegerSize >= DL.getPointerSizeInBits()) {
472 std::pair<Value *, APInt> BaseAndOffset =
473 ConstantOffsetPtrs.lookup(I.getOperand(0));
474 if (BaseAndOffset.first)
475 ConstantOffsetPtrs[&I] = BaseAndOffset;
478 // This is really weird. Technically, ptrtoint will disable SROA. However,
479 // unless that ptrtoint is *used* somewhere in the live basic blocks after
480 // inlining, it will be nuked, and SROA should proceed. All of the uses which
481 // would block SROA would also block SROA if applied directly to a pointer,
482 // and so we can just add the integer in here. The only places where SROA is
483 // preserved either cannot fire on an integer, or won't in-and-of themselves
484 // disable SROA (ext) w/o some later use that we would see and disable.
486 DenseMap<Value *, int>::iterator CostIt;
487 if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt))
488 SROAArgValues[&I] = SROAArg;
490 return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I);
493 bool CallAnalyzer::visitIntToPtr(IntToPtrInst &I) {
494 // Propagate constants through ptrtoint.
495 Constant *COp = dyn_cast<Constant>(I.getOperand(0));
497 COp = SimplifiedValues.lookup(I.getOperand(0));
499 if (Constant *C = ConstantExpr::getIntToPtr(COp, I.getType())) {
500 SimplifiedValues[&I] = C;
504 // Track base/offset pairs when round-tripped through a pointer without
505 // modifications provided the integer is not too large.
506 Value *Op = I.getOperand(0);
507 unsigned IntegerSize = Op->getType()->getScalarSizeInBits();
508 const DataLayout &DL = F.getParent()->getDataLayout();
509 if (IntegerSize <= DL.getPointerSizeInBits()) {
510 std::pair<Value *, APInt> BaseAndOffset = ConstantOffsetPtrs.lookup(Op);
511 if (BaseAndOffset.first)
512 ConstantOffsetPtrs[&I] = BaseAndOffset;
515 // "Propagate" SROA here in the same manner as we do for ptrtoint above.
517 DenseMap<Value *, int>::iterator CostIt;
518 if (lookupSROAArgAndCost(Op, SROAArg, CostIt))
519 SROAArgValues[&I] = SROAArg;
521 return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I);
524 bool CallAnalyzer::visitCastInst(CastInst &I) {
525 // Propagate constants through ptrtoint.
526 Constant *COp = dyn_cast<Constant>(I.getOperand(0));
528 COp = SimplifiedValues.lookup(I.getOperand(0));
530 if (Constant *C = ConstantExpr::getCast(I.getOpcode(), COp, I.getType())) {
531 SimplifiedValues[&I] = C;
535 // Disable SROA in the face of arbitrary casts we don't whitelist elsewhere.
536 disableSROA(I.getOperand(0));
538 return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I);
541 bool CallAnalyzer::visitUnaryInstruction(UnaryInstruction &I) {
542 Value *Operand = I.getOperand(0);
543 Constant *COp = dyn_cast<Constant>(Operand);
545 COp = SimplifiedValues.lookup(Operand);
547 const DataLayout &DL = F.getParent()->getDataLayout();
548 if (Constant *C = ConstantFoldInstOperands(&I, COp, DL)) {
549 SimplifiedValues[&I] = C;
554 // Disable any SROA on the argument to arbitrary unary operators.
555 disableSROA(Operand);
560 bool CallAnalyzer::paramHasAttr(Argument *A, Attribute::AttrKind Attr) {
561 unsigned ArgNo = A->getArgNo();
562 return CandidateCS.paramHasAttr(ArgNo + 1, Attr);
565 bool CallAnalyzer::isKnownNonNullInCallee(Value *V) {
566 // Does the *call site* have the NonNull attribute set on an argument? We
567 // use the attribute on the call site to memoize any analysis done in the
568 // caller. This will also trip if the callee function has a non-null
569 // parameter attribute, but that's a less interesting case because hopefully
570 // the callee would already have been simplified based on that.
571 if (Argument *A = dyn_cast<Argument>(V))
572 if (paramHasAttr(A, Attribute::NonNull))
575 // Is this an alloca in the caller? This is distinct from the attribute case
576 // above because attributes aren't updated within the inliner itself and we
577 // always want to catch the alloca derived case.
578 if (isAllocaDerivedArg(V))
579 // We can actually predict the result of comparisons between an
580 // alloca-derived value and null. Note that this fires regardless of
587 bool CallAnalyzer::allowSizeGrowth(CallSite CS) {
588 // If the normal destination of the invoke or the parent block of the call
589 // site is unreachable-terminated, there is little point in inlining this
590 // unless there is literally zero cost.
591 // FIXME: Note that it is possible that an unreachable-terminated block has a
592 // hot entry. For example, in below scenario inlining hot_call_X() may be
600 // For now, we are not handling this corner case here as it is rare in real
601 // code. In future, we should elaborate this based on BPI and BFI in more
602 // general threshold adjusting heuristics in updateThreshold().
603 Instruction *Instr = CS.getInstruction();
604 if (InvokeInst *II = dyn_cast<InvokeInst>(Instr)) {
605 if (isa<UnreachableInst>(II->getNormalDest()->getTerminator()))
607 } else if (isa<UnreachableInst>(Instr->getParent()->getTerminator()))
613 void CallAnalyzer::updateThreshold(CallSite CS, Function &Callee) {
614 // If no size growth is allowed for this inlining, set Threshold to 0.
615 if (!allowSizeGrowth(CS)) {
620 Function *Caller = CS.getCaller();
622 // return min(A, B) if B is valid.
623 auto MinIfValid = [](int A, Optional<int> B) {
624 return B ? std::min(A, B.getValue()) : A;
627 // return max(A, B) if B is valid.
628 auto MaxIfValid = [](int A, Optional<int> B) {
629 return B ? std::max(A, B.getValue()) : A;
632 // Use the OptMinSizeThreshold or OptSizeThreshold knob if they are available
633 // and reduce the threshold if the caller has the necessary attribute.
634 if (Caller->optForMinSize())
635 Threshold = MinIfValid(Threshold, Params.OptMinSizeThreshold);
636 else if (Caller->optForSize())
637 Threshold = MinIfValid(Threshold, Params.OptSizeThreshold);
639 // Adjust the threshold based on inlinehint attribute and profile based
640 // hotness information if the caller does not have MinSize attribute.
641 if (!Caller->optForMinSize()) {
642 if (Callee.hasFnAttribute(Attribute::InlineHint))
643 Threshold = MaxIfValid(Threshold, Params.HintThreshold);
645 uint64_t TotalWeight;
646 if (CS.getInstruction()->extractProfTotalWeight(TotalWeight) &&
647 PSI->isHotCount(TotalWeight)) {
648 Threshold = MaxIfValid(Threshold, Params.HotCallSiteThreshold);
649 } else if (PSI->isFunctionEntryHot(&Callee)) {
650 // If callsite hotness can not be determined, we may still know
651 // that the callee is hot and treat it as a weaker hint for threshold
653 Threshold = MaxIfValid(Threshold, Params.HintThreshold);
654 } else if (PSI->isFunctionEntryCold(&Callee)) {
655 Threshold = MinIfValid(Threshold, Params.ColdThreshold);
660 // Finally, take the target-specific inlining threshold multiplier into
662 Threshold *= TTI.getInliningThresholdMultiplier();
665 bool CallAnalyzer::visitCmpInst(CmpInst &I) {
666 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
667 // First try to handle simplified comparisons.
668 if (!isa<Constant>(LHS))
669 if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
671 if (!isa<Constant>(RHS))
672 if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
674 if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
675 if (Constant *CRHS = dyn_cast<Constant>(RHS))
677 ConstantExpr::getCompare(I.getPredicate(), CLHS, CRHS)) {
678 SimplifiedValues[&I] = C;
683 if (I.getOpcode() == Instruction::FCmp)
686 // Otherwise look for a comparison between constant offset pointers with
688 Value *LHSBase, *RHSBase;
689 APInt LHSOffset, RHSOffset;
690 std::tie(LHSBase, LHSOffset) = ConstantOffsetPtrs.lookup(LHS);
692 std::tie(RHSBase, RHSOffset) = ConstantOffsetPtrs.lookup(RHS);
693 if (RHSBase && LHSBase == RHSBase) {
694 // We have common bases, fold the icmp to a constant based on the
696 Constant *CLHS = ConstantInt::get(LHS->getContext(), LHSOffset);
697 Constant *CRHS = ConstantInt::get(RHS->getContext(), RHSOffset);
698 if (Constant *C = ConstantExpr::getICmp(I.getPredicate(), CLHS, CRHS)) {
699 SimplifiedValues[&I] = C;
700 ++NumConstantPtrCmps;
706 // If the comparison is an equality comparison with null, we can simplify it
707 // if we know the value (argument) can't be null
708 if (I.isEquality() && isa<ConstantPointerNull>(I.getOperand(1)) &&
709 isKnownNonNullInCallee(I.getOperand(0))) {
710 bool IsNotEqual = I.getPredicate() == CmpInst::ICMP_NE;
711 SimplifiedValues[&I] = IsNotEqual ? ConstantInt::getTrue(I.getType())
712 : ConstantInt::getFalse(I.getType());
715 // Finally check for SROA candidates in comparisons.
717 DenseMap<Value *, int>::iterator CostIt;
718 if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) {
719 if (isa<ConstantPointerNull>(I.getOperand(1))) {
720 accumulateSROACost(CostIt, InlineConstants::InstrCost);
730 bool CallAnalyzer::visitSub(BinaryOperator &I) {
731 // Try to handle a special case: we can fold computing the difference of two
732 // constant-related pointers.
733 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
734 Value *LHSBase, *RHSBase;
735 APInt LHSOffset, RHSOffset;
736 std::tie(LHSBase, LHSOffset) = ConstantOffsetPtrs.lookup(LHS);
738 std::tie(RHSBase, RHSOffset) = ConstantOffsetPtrs.lookup(RHS);
739 if (RHSBase && LHSBase == RHSBase) {
740 // We have common bases, fold the subtract to a constant based on the
742 Constant *CLHS = ConstantInt::get(LHS->getContext(), LHSOffset);
743 Constant *CRHS = ConstantInt::get(RHS->getContext(), RHSOffset);
744 if (Constant *C = ConstantExpr::getSub(CLHS, CRHS)) {
745 SimplifiedValues[&I] = C;
746 ++NumConstantPtrDiffs;
752 // Otherwise, fall back to the generic logic for simplifying and handling
754 return Base::visitSub(I);
757 bool CallAnalyzer::visitBinaryOperator(BinaryOperator &I) {
758 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
759 const DataLayout &DL = F.getParent()->getDataLayout();
760 if (!isa<Constant>(LHS))
761 if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
763 if (!isa<Constant>(RHS))
764 if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
766 Value *SimpleV = nullptr;
767 if (auto FI = dyn_cast<FPMathOperator>(&I))
769 SimplifyFPBinOp(I.getOpcode(), LHS, RHS, FI->getFastMathFlags(), DL);
771 SimpleV = SimplifyBinOp(I.getOpcode(), LHS, RHS, DL);
773 if (Constant *C = dyn_cast_or_null<Constant>(SimpleV)) {
774 SimplifiedValues[&I] = C;
778 // Disable any SROA on arguments to arbitrary, unsimplified binary operators.
785 bool CallAnalyzer::visitLoad(LoadInst &I) {
787 DenseMap<Value *, int>::iterator CostIt;
788 if (lookupSROAArgAndCost(I.getPointerOperand(), SROAArg, CostIt)) {
790 accumulateSROACost(CostIt, InlineConstants::InstrCost);
800 bool CallAnalyzer::visitStore(StoreInst &I) {
802 DenseMap<Value *, int>::iterator CostIt;
803 if (lookupSROAArgAndCost(I.getPointerOperand(), SROAArg, CostIt)) {
805 accumulateSROACost(CostIt, InlineConstants::InstrCost);
815 bool CallAnalyzer::visitExtractValue(ExtractValueInst &I) {
816 // Constant folding for extract value is trivial.
817 Constant *C = dyn_cast<Constant>(I.getAggregateOperand());
819 C = SimplifiedValues.lookup(I.getAggregateOperand());
821 SimplifiedValues[&I] = ConstantExpr::getExtractValue(C, I.getIndices());
825 // SROA can look through these but give them a cost.
829 bool CallAnalyzer::visitInsertValue(InsertValueInst &I) {
830 // Constant folding for insert value is trivial.
831 Constant *AggC = dyn_cast<Constant>(I.getAggregateOperand());
833 AggC = SimplifiedValues.lookup(I.getAggregateOperand());
834 Constant *InsertedC = dyn_cast<Constant>(I.getInsertedValueOperand());
836 InsertedC = SimplifiedValues.lookup(I.getInsertedValueOperand());
837 if (AggC && InsertedC) {
838 SimplifiedValues[&I] =
839 ConstantExpr::getInsertValue(AggC, InsertedC, I.getIndices());
843 // SROA can look through these but give them a cost.
847 /// \brief Try to simplify a call site.
849 /// Takes a concrete function and callsite and tries to actually simplify it by
850 /// analyzing the arguments and call itself with instsimplify. Returns true if
851 /// it has simplified the callsite to some other entity (a constant), making it
853 bool CallAnalyzer::simplifyCallSite(Function *F, CallSite CS) {
854 // FIXME: Using the instsimplify logic directly for this is inefficient
855 // because we have to continually rebuild the argument list even when no
856 // simplifications can be performed. Until that is fixed with remapping
857 // inside of instsimplify, directly constant fold calls here.
858 if (!canConstantFoldCallTo(F))
861 // Try to re-map the arguments to constants.
862 SmallVector<Constant *, 4> ConstantArgs;
863 ConstantArgs.reserve(CS.arg_size());
864 for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E;
866 Constant *C = dyn_cast<Constant>(*I);
868 C = dyn_cast_or_null<Constant>(SimplifiedValues.lookup(*I));
870 return false; // This argument doesn't map to a constant.
872 ConstantArgs.push_back(C);
874 if (Constant *C = ConstantFoldCall(F, ConstantArgs)) {
875 SimplifiedValues[CS.getInstruction()] = C;
882 bool CallAnalyzer::visitCallSite(CallSite CS) {
883 if (CS.hasFnAttr(Attribute::ReturnsTwice) &&
884 !F.hasFnAttribute(Attribute::ReturnsTwice)) {
885 // This aborts the entire analysis.
886 ExposesReturnsTwice = true;
889 if (CS.isCall() && cast<CallInst>(CS.getInstruction())->cannotDuplicate())
890 ContainsNoDuplicateCall = true;
892 if (Function *F = CS.getCalledFunction()) {
893 // When we have a concrete function, first try to simplify it directly.
894 if (simplifyCallSite(F, CS))
897 // Next check if it is an intrinsic we know about.
898 // FIXME: Lift this into part of the InstVisitor.
899 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
900 switch (II->getIntrinsicID()) {
902 return Base::visitCallSite(CS);
904 case Intrinsic::load_relative:
905 // This is normally lowered to 4 LLVM instructions.
906 Cost += 3 * InlineConstants::InstrCost;
909 case Intrinsic::memset:
910 case Intrinsic::memcpy:
911 case Intrinsic::memmove:
912 // SROA can usually chew through these intrinsics, but they aren't free.
914 case Intrinsic::localescape:
915 HasFrameEscape = true;
920 if (F == CS.getInstruction()->getParent()->getParent()) {
921 // This flag will fully abort the analysis, so don't bother with anything
923 IsRecursiveCall = true;
927 if (TTI.isLoweredToCall(F)) {
928 // We account for the average 1 instruction per call argument setup
930 Cost += CS.arg_size() * InlineConstants::InstrCost;
932 // Everything other than inline ASM will also have a significant cost
933 // merely from making the call.
934 if (!isa<InlineAsm>(CS.getCalledValue()))
935 Cost += InlineConstants::CallPenalty;
938 return Base::visitCallSite(CS);
941 // Otherwise we're in a very special case -- an indirect function call. See
942 // if we can be particularly clever about this.
943 Value *Callee = CS.getCalledValue();
945 // First, pay the price of the argument setup. We account for the average
946 // 1 instruction per call argument setup here.
947 Cost += CS.arg_size() * InlineConstants::InstrCost;
949 // Next, check if this happens to be an indirect function call to a known
950 // function in this inline context. If not, we've done all we can.
951 Function *F = dyn_cast_or_null<Function>(SimplifiedValues.lookup(Callee));
953 return Base::visitCallSite(CS);
955 // If we have a constant that we are calling as a function, we can peer
956 // through it and see the function target. This happens not infrequently
957 // during devirtualization and so we want to give it a hefty bonus for
958 // inlining, but cap that bonus in the event that inlining wouldn't pan
959 // out. Pretend to inline the function, with a custom threshold.
960 auto IndirectCallParams = Params;
961 IndirectCallParams.DefaultThreshold = InlineConstants::IndirectCallThreshold;
962 CallAnalyzer CA(TTI, GetAssumptionCache, PSI, *F, CS, IndirectCallParams);
963 if (CA.analyzeCall(CS)) {
964 // We were able to inline the indirect call! Subtract the cost from the
965 // threshold to get the bonus we want to apply, but don't go below zero.
966 Cost -= std::max(0, CA.getThreshold() - CA.getCost());
969 return Base::visitCallSite(CS);
972 bool CallAnalyzer::visitReturnInst(ReturnInst &RI) {
973 // At least one return instruction will be free after inlining.
974 bool Free = !HasReturn;
979 bool CallAnalyzer::visitBranchInst(BranchInst &BI) {
980 // We model unconditional branches as essentially free -- they really
981 // shouldn't exist at all, but handling them makes the behavior of the
982 // inliner more regular and predictable. Interestingly, conditional branches
983 // which will fold away are also free.
984 return BI.isUnconditional() || isa<ConstantInt>(BI.getCondition()) ||
985 dyn_cast_or_null<ConstantInt>(
986 SimplifiedValues.lookup(BI.getCondition()));
989 bool CallAnalyzer::visitSwitchInst(SwitchInst &SI) {
990 // We model unconditional switches as free, see the comments on handling
992 if (isa<ConstantInt>(SI.getCondition()))
994 if (Value *V = SimplifiedValues.lookup(SI.getCondition()))
995 if (isa<ConstantInt>(V))
998 // Otherwise, we need to accumulate a cost proportional to the number of
999 // distinct successor blocks. This fan-out in the CFG cannot be represented
1000 // for free even if we can represent the core switch as a jumptable that
1001 // takes a single instruction.
1003 // NB: We convert large switches which are just used to initialize large phi
1004 // nodes to lookup tables instead in simplify-cfg, so this shouldn't prevent
1005 // inlining those. It will prevent inlining in cases where the optimization
1006 // does not (yet) fire.
1007 SmallPtrSet<BasicBlock *, 8> SuccessorBlocks;
1008 SuccessorBlocks.insert(SI.getDefaultDest());
1009 for (auto I = SI.case_begin(), E = SI.case_end(); I != E; ++I)
1010 SuccessorBlocks.insert(I.getCaseSuccessor());
1011 // Add cost corresponding to the number of distinct destinations. The first
1012 // we model as free because of fallthrough.
1013 Cost += (SuccessorBlocks.size() - 1) * InlineConstants::InstrCost;
1017 bool CallAnalyzer::visitIndirectBrInst(IndirectBrInst &IBI) {
1018 // We never want to inline functions that contain an indirectbr. This is
1019 // incorrect because all the blockaddress's (in static global initializers
1020 // for example) would be referring to the original function, and this
1021 // indirect jump would jump from the inlined copy of the function into the
1022 // original function which is extremely undefined behavior.
1023 // FIXME: This logic isn't really right; we can safely inline functions with
1024 // indirectbr's as long as no other function or global references the
1025 // blockaddress of a block within the current function.
1026 HasIndirectBr = true;
1030 bool CallAnalyzer::visitResumeInst(ResumeInst &RI) {
1031 // FIXME: It's not clear that a single instruction is an accurate model for
1032 // the inline cost of a resume instruction.
1036 bool CallAnalyzer::visitCleanupReturnInst(CleanupReturnInst &CRI) {
1037 // FIXME: It's not clear that a single instruction is an accurate model for
1038 // the inline cost of a cleanupret instruction.
1042 bool CallAnalyzer::visitCatchReturnInst(CatchReturnInst &CRI) {
1043 // FIXME: It's not clear that a single instruction is an accurate model for
1044 // the inline cost of a catchret instruction.
1048 bool CallAnalyzer::visitUnreachableInst(UnreachableInst &I) {
1049 // FIXME: It might be reasonably to discount the cost of instructions leading
1050 // to unreachable as they have the lowest possible impact on both runtime and
1052 return true; // No actual code is needed for unreachable.
1055 bool CallAnalyzer::visitInstruction(Instruction &I) {
1056 // Some instructions are free. All of the free intrinsics can also be
1057 // handled by SROA, etc.
1058 if (TargetTransformInfo::TCC_Free == TTI.getUserCost(&I))
1061 // We found something we don't understand or can't handle. Mark any SROA-able
1062 // values in the operand list as no longer viable.
1063 for (User::op_iterator OI = I.op_begin(), OE = I.op_end(); OI != OE; ++OI)
1069 /// \brief Analyze a basic block for its contribution to the inline cost.
1071 /// This method walks the analyzer over every instruction in the given basic
1072 /// block and accounts for their cost during inlining at this callsite. It
1073 /// aborts early if the threshold has been exceeded or an impossible to inline
1074 /// construct has been detected. It returns false if inlining is no longer
1075 /// viable, and true if inlining remains viable.
1076 bool CallAnalyzer::analyzeBlock(BasicBlock *BB,
1077 SmallPtrSetImpl<const Value *> &EphValues) {
1078 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
1079 // FIXME: Currently, the number of instructions in a function regardless of
1080 // our ability to simplify them during inline to constants or dead code,
1081 // are actually used by the vector bonus heuristic. As long as that's true,
1082 // we have to special case debug intrinsics here to prevent differences in
1083 // inlining due to debug symbols. Eventually, the number of unsimplified
1084 // instructions shouldn't factor into the cost computation, but until then,
1085 // hack around it here.
1086 if (isa<DbgInfoIntrinsic>(I))
1089 // Skip ephemeral values.
1090 if (EphValues.count(&*I))
1094 if (isa<ExtractElementInst>(I) || I->getType()->isVectorTy())
1095 ++NumVectorInstructions;
1097 // If the instruction is floating point, and the target says this operation
1098 // is expensive or the function has the "use-soft-float" attribute, this may
1099 // eventually become a library call. Treat the cost as such.
1100 if (I->getType()->isFloatingPointTy()) {
1101 bool hasSoftFloatAttr = false;
1103 // If the function has the "use-soft-float" attribute, mark it as
1105 if (F.hasFnAttribute("use-soft-float")) {
1106 Attribute Attr = F.getFnAttribute("use-soft-float");
1107 StringRef Val = Attr.getValueAsString();
1109 hasSoftFloatAttr = true;
1112 if (TTI.getFPOpCost(I->getType()) == TargetTransformInfo::TCC_Expensive ||
1114 Cost += InlineConstants::CallPenalty;
1117 // If the instruction simplified to a constant, there is no cost to this
1118 // instruction. Visit the instructions using our InstVisitor to account for
1119 // all of the per-instruction logic. The visit tree returns true if we
1120 // consumed the instruction in any way, and false if the instruction's base
1121 // cost should count against inlining.
1122 if (Base::visit(&*I))
1123 ++NumInstructionsSimplified;
1125 Cost += InlineConstants::InstrCost;
1127 // If the visit this instruction detected an uninlinable pattern, abort.
1128 if (IsRecursiveCall || ExposesReturnsTwice || HasDynamicAlloca ||
1129 HasIndirectBr || HasFrameEscape)
1132 // If the caller is a recursive function then we don't want to inline
1133 // functions which allocate a lot of stack space because it would increase
1134 // the caller stack usage dramatically.
1135 if (IsCallerRecursive &&
1136 AllocatedSize > InlineConstants::TotalAllocaSizeRecursiveCaller)
1139 // Check if we've past the maximum possible threshold so we don't spin in
1140 // huge basic blocks that will never inline.
1141 if (Cost > Threshold)
1148 /// \brief Compute the base pointer and cumulative constant offsets for V.
1150 /// This strips all constant offsets off of V, leaving it the base pointer, and
1151 /// accumulates the total constant offset applied in the returned constant. It
1152 /// returns 0 if V is not a pointer, and returns the constant '0' if there are
1153 /// no constant offsets applied.
1154 ConstantInt *CallAnalyzer::stripAndComputeInBoundsConstantOffsets(Value *&V) {
1155 if (!V->getType()->isPointerTy())
1158 const DataLayout &DL = F.getParent()->getDataLayout();
1159 unsigned IntPtrWidth = DL.getPointerSizeInBits();
1160 APInt Offset = APInt::getNullValue(IntPtrWidth);
1162 // Even though we don't look through PHI nodes, we could be called on an
1163 // instruction in an unreachable block, which may be on a cycle.
1164 SmallPtrSet<Value *, 4> Visited;
1167 if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
1168 if (!GEP->isInBounds() || !accumulateGEPOffset(*GEP, Offset))
1170 V = GEP->getPointerOperand();
1171 } else if (Operator::getOpcode(V) == Instruction::BitCast) {
1172 V = cast<Operator>(V)->getOperand(0);
1173 } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
1174 if (GA->isInterposable())
1176 V = GA->getAliasee();
1180 assert(V->getType()->isPointerTy() && "Unexpected operand type!");
1181 } while (Visited.insert(V).second);
1183 Type *IntPtrTy = DL.getIntPtrType(V->getContext());
1184 return cast<ConstantInt>(ConstantInt::get(IntPtrTy, Offset));
1187 /// \brief Analyze a call site for potential inlining.
1189 /// Returns true if inlining this call is viable, and false if it is not
1190 /// viable. It computes the cost and adjusts the threshold based on numerous
1191 /// factors and heuristics. If this method returns false but the computed cost
1192 /// is below the computed threshold, then inlining was forcibly disabled by
1193 /// some artifact of the routine.
1194 bool CallAnalyzer::analyzeCall(CallSite CS) {
1197 // Perform some tweaks to the cost and threshold based on the direct
1198 // callsite information.
1200 // We want to more aggressively inline vector-dense kernels, so up the
1201 // threshold, and we'll lower it if the % of vector instructions gets too
1202 // low. Note that these bonuses are some what arbitrary and evolved over time
1203 // by accident as much as because they are principled bonuses.
1205 // FIXME: It would be nice to remove all such bonuses. At least it would be
1206 // nice to base the bonus values on something more scientific.
1207 assert(NumInstructions == 0);
1208 assert(NumVectorInstructions == 0);
1210 // Update the threshold based on callsite properties
1211 updateThreshold(CS, F);
1213 FiftyPercentVectorBonus = 3 * Threshold / 2;
1214 TenPercentVectorBonus = 3 * Threshold / 4;
1215 const DataLayout &DL = F.getParent()->getDataLayout();
1217 // Track whether the post-inlining function would have more than one basic
1218 // block. A single basic block is often intended for inlining. Balloon the
1219 // threshold by 50% until we pass the single-BB phase.
1220 bool SingleBB = true;
1221 int SingleBBBonus = Threshold / 2;
1223 // Speculatively apply all possible bonuses to Threshold. If cost exceeds
1224 // this Threshold any time, and cost cannot decrease, we can stop processing
1225 // the rest of the function body.
1226 Threshold += (SingleBBBonus + FiftyPercentVectorBonus);
1228 // Give out bonuses per argument, as the instructions setting them up will
1229 // be gone after inlining.
1230 for (unsigned I = 0, E = CS.arg_size(); I != E; ++I) {
1231 if (CS.isByValArgument(I)) {
1232 // We approximate the number of loads and stores needed by dividing the
1233 // size of the byval type by the target's pointer size.
1234 PointerType *PTy = cast<PointerType>(CS.getArgument(I)->getType());
1235 unsigned TypeSize = DL.getTypeSizeInBits(PTy->getElementType());
1236 unsigned PointerSize = DL.getPointerSizeInBits();
1237 // Ceiling division.
1238 unsigned NumStores = (TypeSize + PointerSize - 1) / PointerSize;
1240 // If it generates more than 8 stores it is likely to be expanded as an
1241 // inline memcpy so we take that as an upper bound. Otherwise we assume
1242 // one load and one store per word copied.
1243 // FIXME: The maxStoresPerMemcpy setting from the target should be used
1244 // here instead of a magic number of 8, but it's not available via
1246 NumStores = std::min(NumStores, 8U);
1248 Cost -= 2 * NumStores * InlineConstants::InstrCost;
1250 // For non-byval arguments subtract off one instruction per call
1252 Cost -= InlineConstants::InstrCost;
1255 // The call instruction also disappears after inlining.
1256 Cost -= InlineConstants::InstrCost + InlineConstants::CallPenalty;
1258 // If there is only one call of the function, and it has internal linkage,
1259 // the cost of inlining it drops dramatically.
1260 bool OnlyOneCallAndLocalLinkage =
1261 F.hasLocalLinkage() && F.hasOneUse() && &F == CS.getCalledFunction();
1262 if (OnlyOneCallAndLocalLinkage)
1263 Cost -= InlineConstants::LastCallToStaticBonus;
1265 // If this function uses the coldcc calling convention, prefer not to inline
1267 if (F.getCallingConv() == CallingConv::Cold)
1268 Cost += InlineConstants::ColdccPenalty;
1270 // Check if we're done. This can happen due to bonuses and penalties.
1271 if (Cost > Threshold)
1277 Function *Caller = CS.getInstruction()->getParent()->getParent();
1278 // Check if the caller function is recursive itself.
1279 for (User *U : Caller->users()) {
1283 Instruction *I = Site.getInstruction();
1284 if (I->getParent()->getParent() == Caller) {
1285 IsCallerRecursive = true;
1290 // Populate our simplified values by mapping from function arguments to call
1291 // arguments with known important simplifications.
1292 CallSite::arg_iterator CAI = CS.arg_begin();
1293 for (Function::arg_iterator FAI = F.arg_begin(), FAE = F.arg_end();
1294 FAI != FAE; ++FAI, ++CAI) {
1295 assert(CAI != CS.arg_end());
1296 if (Constant *C = dyn_cast<Constant>(CAI))
1297 SimplifiedValues[&*FAI] = C;
1299 Value *PtrArg = *CAI;
1300 if (ConstantInt *C = stripAndComputeInBoundsConstantOffsets(PtrArg)) {
1301 ConstantOffsetPtrs[&*FAI] = std::make_pair(PtrArg, C->getValue());
1303 // We can SROA any pointer arguments derived from alloca instructions.
1304 if (isa<AllocaInst>(PtrArg)) {
1305 SROAArgValues[&*FAI] = PtrArg;
1306 SROAArgCosts[PtrArg] = 0;
1310 NumConstantArgs = SimplifiedValues.size();
1311 NumConstantOffsetPtrArgs = ConstantOffsetPtrs.size();
1312 NumAllocaArgs = SROAArgValues.size();
1314 // FIXME: If a caller has multiple calls to a callee, we end up recomputing
1315 // the ephemeral values multiple times (and they're completely determined by
1316 // the callee, so this is purely duplicate work).
1317 SmallPtrSet<const Value *, 32> EphValues;
1318 CodeMetrics::collectEphemeralValues(&F, &GetAssumptionCache(F), EphValues);
1320 // The worklist of live basic blocks in the callee *after* inlining. We avoid
1321 // adding basic blocks of the callee which can be proven to be dead for this
1322 // particular call site in order to get more accurate cost estimates. This
1323 // requires a somewhat heavyweight iteration pattern: we need to walk the
1324 // basic blocks in a breadth-first order as we insert live successors. To
1325 // accomplish this, prioritizing for small iterations because we exit after
1326 // crossing our threshold, we use a small-size optimized SetVector.
1327 typedef SetVector<BasicBlock *, SmallVector<BasicBlock *, 16>,
1328 SmallPtrSet<BasicBlock *, 16>>
1330 BBSetVector BBWorklist;
1331 BBWorklist.insert(&F.getEntryBlock());
1332 // Note that we *must not* cache the size, this loop grows the worklist.
1333 for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
1334 // Bail out the moment we cross the threshold. This means we'll under-count
1335 // the cost, but only when undercounting doesn't matter.
1336 if (Cost > Threshold)
1339 BasicBlock *BB = BBWorklist[Idx];
1343 // Disallow inlining a blockaddress. A blockaddress only has defined
1344 // behavior for an indirect branch in the same function, and we do not
1345 // currently support inlining indirect branches. But, the inliner may not
1346 // see an indirect branch that ends up being dead code at a particular call
1347 // site. If the blockaddress escapes the function, e.g., via a global
1348 // variable, inlining may lead to an invalid cross-function reference.
1349 if (BB->hasAddressTaken())
1352 // Analyze the cost of this block. If we blow through the threshold, this
1353 // returns false, and we can bail on out.
1354 if (!analyzeBlock(BB, EphValues))
1357 TerminatorInst *TI = BB->getTerminator();
1359 // Add in the live successors by first checking whether we have terminator
1360 // that may be simplified based on the values simplified by this call.
1361 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
1362 if (BI->isConditional()) {
1363 Value *Cond = BI->getCondition();
1364 if (ConstantInt *SimpleCond =
1365 dyn_cast_or_null<ConstantInt>(SimplifiedValues.lookup(Cond))) {
1366 BBWorklist.insert(BI->getSuccessor(SimpleCond->isZero() ? 1 : 0));
1370 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
1371 Value *Cond = SI->getCondition();
1372 if (ConstantInt *SimpleCond =
1373 dyn_cast_or_null<ConstantInt>(SimplifiedValues.lookup(Cond))) {
1374 BBWorklist.insert(SI->findCaseValue(SimpleCond).getCaseSuccessor());
1379 // If we're unable to select a particular successor, just count all of
1381 for (unsigned TIdx = 0, TSize = TI->getNumSuccessors(); TIdx != TSize;
1383 BBWorklist.insert(TI->getSuccessor(TIdx));
1385 // If we had any successors at this point, than post-inlining is likely to
1386 // have them as well. Note that we assume any basic blocks which existed
1387 // due to branches or switches which folded above will also fold after
1389 if (SingleBB && TI->getNumSuccessors() > 1) {
1390 // Take off the bonus we applied to the threshold.
1391 Threshold -= SingleBBBonus;
1396 // If this is a noduplicate call, we can still inline as long as
1397 // inlining this would cause the removal of the caller (so the instruction
1398 // is not actually duplicated, just moved).
1399 if (!OnlyOneCallAndLocalLinkage && ContainsNoDuplicateCall)
1402 // We applied the maximum possible vector bonus at the beginning. Now,
1403 // subtract the excess bonus, if any, from the Threshold before
1404 // comparing against Cost.
1405 if (NumVectorInstructions <= NumInstructions / 10)
1406 Threshold -= FiftyPercentVectorBonus;
1407 else if (NumVectorInstructions <= NumInstructions / 2)
1408 Threshold -= (FiftyPercentVectorBonus - TenPercentVectorBonus);
1410 return Cost < std::max(1, Threshold);
1413 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1414 /// \brief Dump stats about this call's analysis.
1415 LLVM_DUMP_METHOD void CallAnalyzer::dump() {
1416 #define DEBUG_PRINT_STAT(x) dbgs() << " " #x ": " << x << "\n"
1417 DEBUG_PRINT_STAT(NumConstantArgs);
1418 DEBUG_PRINT_STAT(NumConstantOffsetPtrArgs);
1419 DEBUG_PRINT_STAT(NumAllocaArgs);
1420 DEBUG_PRINT_STAT(NumConstantPtrCmps);
1421 DEBUG_PRINT_STAT(NumConstantPtrDiffs);
1422 DEBUG_PRINT_STAT(NumInstructionsSimplified);
1423 DEBUG_PRINT_STAT(NumInstructions);
1424 DEBUG_PRINT_STAT(SROACostSavings);
1425 DEBUG_PRINT_STAT(SROACostSavingsLost);
1426 DEBUG_PRINT_STAT(ContainsNoDuplicateCall);
1427 DEBUG_PRINT_STAT(Cost);
1428 DEBUG_PRINT_STAT(Threshold);
1429 #undef DEBUG_PRINT_STAT
1433 /// \brief Test that two functions either have or have not the given attribute
1434 /// at the same time.
1435 template <typename AttrKind>
1436 static bool attributeMatches(Function *F1, Function *F2, AttrKind Attr) {
1437 return F1->getFnAttribute(Attr) == F2->getFnAttribute(Attr);
1440 /// \brief Test that there are no attribute conflicts between Caller and Callee
1441 /// that prevent inlining.
1442 static bool functionsHaveCompatibleAttributes(Function *Caller,
1444 TargetTransformInfo &TTI) {
1445 return TTI.areInlineCompatible(Caller, Callee) &&
1446 AttributeFuncs::areInlineCompatible(*Caller, *Callee);
1449 InlineCost llvm::getInlineCost(
1450 CallSite CS, const InlineParams &Params, TargetTransformInfo &CalleeTTI,
1451 std::function<AssumptionCache &(Function &)> &GetAssumptionCache,
1452 ProfileSummaryInfo *PSI) {
1453 return getInlineCost(CS, CS.getCalledFunction(), Params, CalleeTTI,
1454 GetAssumptionCache, PSI);
1457 InlineCost llvm::getInlineCost(
1458 CallSite CS, Function *Callee, const InlineParams &Params,
1459 TargetTransformInfo &CalleeTTI,
1460 std::function<AssumptionCache &(Function &)> &GetAssumptionCache,
1461 ProfileSummaryInfo *PSI) {
1463 // Cannot inline indirect calls.
1465 return llvm::InlineCost::getNever();
1467 // Calls to functions with always-inline attributes should be inlined
1468 // whenever possible.
1469 if (CS.hasFnAttr(Attribute::AlwaysInline)) {
1470 if (isInlineViable(*Callee))
1471 return llvm::InlineCost::getAlways();
1472 return llvm::InlineCost::getNever();
1475 // Never inline functions with conflicting attributes (unless callee has
1476 // always-inline attribute).
1477 if (!functionsHaveCompatibleAttributes(CS.getCaller(), Callee, CalleeTTI))
1478 return llvm::InlineCost::getNever();
1480 // Don't inline this call if the caller has the optnone attribute.
1481 if (CS.getCaller()->hasFnAttribute(Attribute::OptimizeNone))
1482 return llvm::InlineCost::getNever();
1484 // Don't inline functions which can be interposed at link-time. Don't inline
1485 // functions marked noinline or call sites marked noinline.
1486 // Note: inlining non-exact non-interposable functions is fine, since we know
1487 // we have *a* correct implementation of the source level function.
1488 if (Callee->isInterposable() || Callee->hasFnAttribute(Attribute::NoInline) ||
1490 return llvm::InlineCost::getNever();
1492 DEBUG(llvm::dbgs() << " Analyzing call of " << Callee->getName()
1495 CallAnalyzer CA(CalleeTTI, GetAssumptionCache, PSI, *Callee, CS, Params);
1496 bool ShouldInline = CA.analyzeCall(CS);
1500 // Check if there was a reason to force inlining or no inlining.
1501 if (!ShouldInline && CA.getCost() < CA.getThreshold())
1502 return InlineCost::getNever();
1503 if (ShouldInline && CA.getCost() >= CA.getThreshold())
1504 return InlineCost::getAlways();
1506 return llvm::InlineCost::get(CA.getCost(), CA.getThreshold());
1509 bool llvm::isInlineViable(Function &F) {
1510 bool ReturnsTwice = F.hasFnAttribute(Attribute::ReturnsTwice);
1511 for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) {
1512 // Disallow inlining of functions which contain indirect branches or
1514 if (isa<IndirectBrInst>(BI->getTerminator()) || BI->hasAddressTaken())
1517 for (auto &II : *BI) {
1522 // Disallow recursive calls.
1523 if (&F == CS.getCalledFunction())
1526 // Disallow calls which expose returns-twice to a function not previously
1527 // attributed as such.
1528 if (!ReturnsTwice && CS.isCall() &&
1529 cast<CallInst>(CS.getInstruction())->canReturnTwice())
1532 // Disallow inlining functions that call @llvm.localescape. Doing this
1533 // correctly would require major changes to the inliner.
1534 if (CS.getCalledFunction() &&
1535 CS.getCalledFunction()->getIntrinsicID() ==
1536 llvm::Intrinsic::localescape)
1544 // APIs to create InlineParams based on command line flags and/or other
1547 InlineParams llvm::getInlineParams(int Threshold) {
1548 InlineParams Params;
1550 // This field is the threshold to use for a callee by default. This is
1551 // derived from one or more of:
1552 // * optimization or size-optimization levels,
1553 // * a value passed to createFunctionInliningPass function, or
1554 // * the -inline-threshold flag.
1555 // If the -inline-threshold flag is explicitly specified, that is used
1556 // irrespective of anything else.
1557 if (InlineThreshold.getNumOccurrences() > 0)
1558 Params.DefaultThreshold = InlineThreshold;
1560 Params.DefaultThreshold = Threshold;
1562 // Set the HintThreshold knob from the -inlinehint-threshold.
1563 Params.HintThreshold = HintThreshold;
1565 // Set the HotCallSiteThreshold knob from the -hot-callsite-threshold.
1566 Params.HotCallSiteThreshold = HotCallSiteThreshold;
1568 // Set the OptMinSizeThreshold and OptSizeThreshold params only if the
1569 // Set the OptMinSizeThreshold and OptSizeThreshold params only if the
1570 // -inlinehint-threshold commandline option is not explicitly given. If that
1571 // option is present, then its value applies even for callees with size and
1572 // minsize attributes.
1573 // If the -inline-threshold is not specified, set the ColdThreshold from the
1574 // -inlinecold-threshold even if it is not explicitly passed. If
1575 // -inline-threshold is specified, then -inlinecold-threshold needs to be
1576 // explicitly specified to set the ColdThreshold knob
1577 if (InlineThreshold.getNumOccurrences() == 0) {
1578 Params.OptMinSizeThreshold = InlineConstants::OptMinSizeThreshold;
1579 Params.OptSizeThreshold = InlineConstants::OptSizeThreshold;
1580 Params.ColdThreshold = ColdThreshold;
1581 } else if (ColdThreshold.getNumOccurrences() > 0) {
1582 Params.ColdThreshold = ColdThreshold;
1587 InlineParams llvm::getInlineParams() {
1588 return getInlineParams(InlineThreshold);
1591 // Compute the default threshold for inlining based on the opt level and the
1593 static int computeThresholdFromOptLevels(unsigned OptLevel,
1594 unsigned SizeOptLevel) {
1596 return InlineConstants::OptAggressiveThreshold;
1597 if (SizeOptLevel == 1) // -Os
1598 return InlineConstants::OptSizeThreshold;
1599 if (SizeOptLevel == 2) // -Oz
1600 return InlineConstants::OptMinSizeThreshold;
1601 return InlineThreshold;
1604 InlineParams llvm::getInlineParams(unsigned OptLevel, unsigned SizeOptLevel) {
1605 return getInlineParams(computeThresholdFromOptLevels(OptLevel, SizeOptLevel));