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/TargetTransformInfo.h"
25 #include "llvm/IR/CallSite.h"
26 #include "llvm/IR/CallingConv.h"
27 #include "llvm/IR/DataLayout.h"
28 #include "llvm/IR/GetElementPtrTypeIterator.h"
29 #include "llvm/IR/GlobalAlias.h"
30 #include "llvm/IR/InstVisitor.h"
31 #include "llvm/IR/IntrinsicInst.h"
32 #include "llvm/IR/Operator.h"
33 #include "llvm/Support/Debug.h"
34 #include "llvm/Support/raw_ostream.h"
38 #define DEBUG_TYPE "inline-cost"
40 STATISTIC(NumCallsAnalyzed, "Number of call sites analyzed");
44 class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
45 typedef InstVisitor<CallAnalyzer, bool> Base;
46 friend class InstVisitor<CallAnalyzer, bool>;
48 /// The TargetTransformInfo available for this compilation.
49 const TargetTransformInfo &TTI;
51 /// The cache of @llvm.assume intrinsics.
52 AssumptionCacheTracker *ACT;
54 // The called function.
57 // The candidate callsite being analyzed. Please do not use this to do
58 // analysis in the caller function; we want the inline cost query to be
59 // easily cacheable. Instead, use the cover function paramHasAttr.
65 bool IsCallerRecursive;
67 bool ExposesReturnsTwice;
68 bool HasDynamicAlloca;
69 bool ContainsNoDuplicateCall;
74 /// Number of bytes allocated statically by the callee.
75 uint64_t AllocatedSize;
76 unsigned NumInstructions, NumVectorInstructions;
77 int FiftyPercentVectorBonus, TenPercentVectorBonus;
80 // While we walk the potentially-inlined instructions, we build up and
81 // maintain a mapping of simplified values specific to this callsite. The
82 // idea is to propagate any special information we have about arguments to
83 // this call through the inlinable section of the function, and account for
84 // likely simplifications post-inlining. The most important aspect we track
85 // is CFG altering simplifications -- when we prove a basic block dead, that
86 // can cause dramatic shifts in the cost of inlining a function.
87 DenseMap<Value *, Constant *> SimplifiedValues;
89 // Keep track of the values which map back (through function arguments) to
90 // allocas on the caller stack which could be simplified through SROA.
91 DenseMap<Value *, Value *> SROAArgValues;
93 // The mapping of caller Alloca values to their accumulated cost savings. If
94 // we have to disable SROA for one of the allocas, this tells us how much
95 // cost must be added.
96 DenseMap<Value *, int> SROAArgCosts;
98 // Keep track of values which map to a pointer base and constant offset.
99 DenseMap<Value *, std::pair<Value *, APInt> > ConstantOffsetPtrs;
101 // Custom simplification helper routines.
102 bool isAllocaDerivedArg(Value *V);
103 bool lookupSROAArgAndCost(Value *V, Value *&Arg,
104 DenseMap<Value *, int>::iterator &CostIt);
105 void disableSROA(DenseMap<Value *, int>::iterator CostIt);
106 void disableSROA(Value *V);
107 void accumulateSROACost(DenseMap<Value *, int>::iterator CostIt,
108 int InstructionCost);
109 bool isGEPOffsetConstant(GetElementPtrInst &GEP);
110 bool accumulateGEPOffset(GEPOperator &GEP, APInt &Offset);
111 bool simplifyCallSite(Function *F, CallSite CS);
112 ConstantInt *stripAndComputeInBoundsConstantOffsets(Value *&V);
114 /// Return true if the given argument to the function being considered for
115 /// inlining has the given attribute set either at the call site or the
116 /// function declaration. Primarily used to inspect call site specific
117 /// attributes since these can be more precise than the ones on the callee
119 bool paramHasAttr(Argument *A, Attribute::AttrKind Attr);
121 /// Return true if the given value is known non null within the callee if
122 /// inlined through this particular callsite.
123 bool isKnownNonNullInCallee(Value *V);
125 // Custom analysis routines.
126 bool analyzeBlock(BasicBlock *BB, SmallPtrSetImpl<const Value *> &EphValues);
128 // Disable several entry points to the visitor so we don't accidentally use
129 // them by declaring but not defining them here.
130 void visit(Module *); void visit(Module &);
131 void visit(Function *); void visit(Function &);
132 void visit(BasicBlock *); void visit(BasicBlock &);
134 // Provide base case for our instruction visit.
135 bool visitInstruction(Instruction &I);
137 // Our visit overrides.
138 bool visitAlloca(AllocaInst &I);
139 bool visitPHI(PHINode &I);
140 bool visitGetElementPtr(GetElementPtrInst &I);
141 bool visitBitCast(BitCastInst &I);
142 bool visitPtrToInt(PtrToIntInst &I);
143 bool visitIntToPtr(IntToPtrInst &I);
144 bool visitCastInst(CastInst &I);
145 bool visitUnaryInstruction(UnaryInstruction &I);
146 bool visitCmpInst(CmpInst &I);
147 bool visitSub(BinaryOperator &I);
148 bool visitBinaryOperator(BinaryOperator &I);
149 bool visitLoad(LoadInst &I);
150 bool visitStore(StoreInst &I);
151 bool visitExtractValue(ExtractValueInst &I);
152 bool visitInsertValue(InsertValueInst &I);
153 bool visitCallSite(CallSite CS);
154 bool visitReturnInst(ReturnInst &RI);
155 bool visitBranchInst(BranchInst &BI);
156 bool visitSwitchInst(SwitchInst &SI);
157 bool visitIndirectBrInst(IndirectBrInst &IBI);
158 bool visitResumeInst(ResumeInst &RI);
159 bool visitUnreachableInst(UnreachableInst &I);
162 CallAnalyzer(const TargetTransformInfo &TTI, AssumptionCacheTracker *ACT,
163 Function &Callee, int Threshold, CallSite CSArg)
164 : TTI(TTI), ACT(ACT), F(Callee), CandidateCS(CSArg), Threshold(Threshold),
165 Cost(0), IsCallerRecursive(false), IsRecursiveCall(false),
166 ExposesReturnsTwice(false), HasDynamicAlloca(false),
167 ContainsNoDuplicateCall(false), HasReturn(false), HasIndirectBr(false),
168 HasFrameEscape(false), AllocatedSize(0), NumInstructions(0),
169 NumVectorInstructions(0), FiftyPercentVectorBonus(0),
170 TenPercentVectorBonus(0), VectorBonus(0), NumConstantArgs(0),
171 NumConstantOffsetPtrArgs(0), NumAllocaArgs(0), NumConstantPtrCmps(0),
172 NumConstantPtrDiffs(0), NumInstructionsSimplified(0),
173 SROACostSavings(0), SROACostSavingsLost(0) {}
175 bool analyzeCall(CallSite CS);
177 int getThreshold() { return Threshold; }
178 int getCost() { return Cost; }
180 // Keep a bunch of stats about the cost savings found so we can print them
181 // out when debugging.
182 unsigned NumConstantArgs;
183 unsigned NumConstantOffsetPtrArgs;
184 unsigned NumAllocaArgs;
185 unsigned NumConstantPtrCmps;
186 unsigned NumConstantPtrDiffs;
187 unsigned NumInstructionsSimplified;
188 unsigned SROACostSavings;
189 unsigned SROACostSavingsLost;
196 /// \brief Test whether the given value is an Alloca-derived function argument.
197 bool CallAnalyzer::isAllocaDerivedArg(Value *V) {
198 return SROAArgValues.count(V);
201 /// \brief Lookup the SROA-candidate argument and cost iterator which V maps to.
202 /// Returns false if V does not map to a SROA-candidate.
203 bool CallAnalyzer::lookupSROAArgAndCost(
204 Value *V, Value *&Arg, DenseMap<Value *, int>::iterator &CostIt) {
205 if (SROAArgValues.empty() || SROAArgCosts.empty())
208 DenseMap<Value *, Value *>::iterator ArgIt = SROAArgValues.find(V);
209 if (ArgIt == SROAArgValues.end())
213 CostIt = SROAArgCosts.find(Arg);
214 return CostIt != SROAArgCosts.end();
217 /// \brief Disable SROA for the candidate marked by this cost iterator.
219 /// This marks the candidate as no longer viable for SROA, and adds the cost
220 /// savings associated with it back into the inline cost measurement.
221 void CallAnalyzer::disableSROA(DenseMap<Value *, int>::iterator CostIt) {
222 // If we're no longer able to perform SROA we need to undo its cost savings
223 // and prevent subsequent analysis.
224 Cost += CostIt->second;
225 SROACostSavings -= CostIt->second;
226 SROACostSavingsLost += CostIt->second;
227 SROAArgCosts.erase(CostIt);
230 /// \brief If 'V' maps to a SROA candidate, disable SROA for it.
231 void CallAnalyzer::disableSROA(Value *V) {
233 DenseMap<Value *, int>::iterator CostIt;
234 if (lookupSROAArgAndCost(V, SROAArg, CostIt))
238 /// \brief Accumulate the given cost for a particular SROA candidate.
239 void CallAnalyzer::accumulateSROACost(DenseMap<Value *, int>::iterator CostIt,
240 int InstructionCost) {
241 CostIt->second += InstructionCost;
242 SROACostSavings += InstructionCost;
245 /// \brief Check whether a GEP's indices are all constant.
247 /// Respects any simplified values known during the analysis of this callsite.
248 bool CallAnalyzer::isGEPOffsetConstant(GetElementPtrInst &GEP) {
249 for (User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end(); I != E; ++I)
250 if (!isa<Constant>(*I) && !SimplifiedValues.lookup(*I))
256 /// \brief Accumulate a constant GEP offset into an APInt if possible.
258 /// Returns false if unable to compute the offset for any reason. Respects any
259 /// simplified values known during the analysis of this callsite.
260 bool CallAnalyzer::accumulateGEPOffset(GEPOperator &GEP, APInt &Offset) {
261 const DataLayout &DL = F.getParent()->getDataLayout();
262 unsigned IntPtrWidth = DL.getPointerSizeInBits();
263 assert(IntPtrWidth == Offset.getBitWidth());
265 for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP);
267 ConstantInt *OpC = dyn_cast<ConstantInt>(GTI.getOperand());
269 if (Constant *SimpleOp = SimplifiedValues.lookup(GTI.getOperand()))
270 OpC = dyn_cast<ConstantInt>(SimpleOp);
273 if (OpC->isZero()) continue;
275 // Handle a struct index, which adds its field offset to the pointer.
276 if (StructType *STy = dyn_cast<StructType>(*GTI)) {
277 unsigned ElementIdx = OpC->getZExtValue();
278 const StructLayout *SL = DL.getStructLayout(STy);
279 Offset += APInt(IntPtrWidth, SL->getElementOffset(ElementIdx));
283 APInt TypeSize(IntPtrWidth, DL.getTypeAllocSize(GTI.getIndexedType()));
284 Offset += OpC->getValue().sextOrTrunc(IntPtrWidth) * TypeSize;
289 bool CallAnalyzer::visitAlloca(AllocaInst &I) {
290 // Check whether inlining will turn a dynamic alloca into a static
291 // alloca, and handle that case.
292 if (I.isArrayAllocation()) {
293 if (Constant *Size = SimplifiedValues.lookup(I.getArraySize())) {
294 ConstantInt *AllocSize = dyn_cast<ConstantInt>(Size);
295 assert(AllocSize && "Allocation size not a constant int?");
296 Type *Ty = I.getAllocatedType();
297 AllocatedSize += Ty->getPrimitiveSizeInBits() * AllocSize->getZExtValue();
298 return Base::visitAlloca(I);
302 // Accumulate the allocated size.
303 if (I.isStaticAlloca()) {
304 const DataLayout &DL = F.getParent()->getDataLayout();
305 Type *Ty = I.getAllocatedType();
306 AllocatedSize += DL.getTypeAllocSize(Ty);
309 // We will happily inline static alloca instructions.
310 if (I.isStaticAlloca())
311 return Base::visitAlloca(I);
313 // FIXME: This is overly conservative. Dynamic allocas are inefficient for
314 // a variety of reasons, and so we would like to not inline them into
315 // functions which don't currently have a dynamic alloca. This simply
316 // disables inlining altogether in the presence of a dynamic alloca.
317 HasDynamicAlloca = true;
321 bool CallAnalyzer::visitPHI(PHINode &I) {
322 // FIXME: We should potentially be tracking values through phi nodes,
323 // especially when they collapse to a single value due to deleted CFG edges
326 // FIXME: We need to propagate SROA *disabling* through phi nodes, even
327 // though we don't want to propagate it's bonuses. The idea is to disable
328 // SROA if it *might* be used in an inappropriate manner.
330 // Phi nodes are always zero-cost.
334 bool CallAnalyzer::visitGetElementPtr(GetElementPtrInst &I) {
336 DenseMap<Value *, int>::iterator CostIt;
337 bool SROACandidate = lookupSROAArgAndCost(I.getPointerOperand(),
340 // Try to fold GEPs of constant-offset call site argument pointers. This
341 // requires target data and inbounds GEPs.
342 if (I.isInBounds()) {
343 // Check if we have a base + offset for the pointer.
344 Value *Ptr = I.getPointerOperand();
345 std::pair<Value *, APInt> BaseAndOffset = ConstantOffsetPtrs.lookup(Ptr);
346 if (BaseAndOffset.first) {
347 // Check if the offset of this GEP is constant, and if so accumulate it
349 if (!accumulateGEPOffset(cast<GEPOperator>(I), BaseAndOffset.second)) {
350 // Non-constant GEPs aren't folded, and disable SROA.
356 // Add the result as a new mapping to Base + Offset.
357 ConstantOffsetPtrs[&I] = BaseAndOffset;
359 // Also handle SROA candidates here, we already know that the GEP is
360 // all-constant indexed.
362 SROAArgValues[&I] = SROAArg;
368 if (isGEPOffsetConstant(I)) {
370 SROAArgValues[&I] = SROAArg;
372 // Constant GEPs are modeled as free.
376 // Variable GEPs will require math and will disable SROA.
382 bool CallAnalyzer::visitBitCast(BitCastInst &I) {
383 // Propagate constants through bitcasts.
384 Constant *COp = dyn_cast<Constant>(I.getOperand(0));
386 COp = SimplifiedValues.lookup(I.getOperand(0));
388 if (Constant *C = ConstantExpr::getBitCast(COp, I.getType())) {
389 SimplifiedValues[&I] = C;
393 // Track base/offsets through casts
394 std::pair<Value *, APInt> BaseAndOffset
395 = ConstantOffsetPtrs.lookup(I.getOperand(0));
396 // Casts don't change the offset, just wrap it up.
397 if (BaseAndOffset.first)
398 ConstantOffsetPtrs[&I] = BaseAndOffset;
400 // Also look for SROA candidates here.
402 DenseMap<Value *, int>::iterator CostIt;
403 if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt))
404 SROAArgValues[&I] = SROAArg;
406 // Bitcasts are always zero cost.
410 bool CallAnalyzer::visitPtrToInt(PtrToIntInst &I) {
411 // Propagate constants through ptrtoint.
412 Constant *COp = dyn_cast<Constant>(I.getOperand(0));
414 COp = SimplifiedValues.lookup(I.getOperand(0));
416 if (Constant *C = ConstantExpr::getPtrToInt(COp, I.getType())) {
417 SimplifiedValues[&I] = C;
421 // Track base/offset pairs when converted to a plain integer provided the
422 // integer is large enough to represent the pointer.
423 unsigned IntegerSize = I.getType()->getScalarSizeInBits();
424 const DataLayout &DL = F.getParent()->getDataLayout();
425 if (IntegerSize >= DL.getPointerSizeInBits()) {
426 std::pair<Value *, APInt> BaseAndOffset
427 = ConstantOffsetPtrs.lookup(I.getOperand(0));
428 if (BaseAndOffset.first)
429 ConstantOffsetPtrs[&I] = BaseAndOffset;
432 // This is really weird. Technically, ptrtoint will disable SROA. However,
433 // unless that ptrtoint is *used* somewhere in the live basic blocks after
434 // inlining, it will be nuked, and SROA should proceed. All of the uses which
435 // would block SROA would also block SROA if applied directly to a pointer,
436 // and so we can just add the integer in here. The only places where SROA is
437 // preserved either cannot fire on an integer, or won't in-and-of themselves
438 // disable SROA (ext) w/o some later use that we would see and disable.
440 DenseMap<Value *, int>::iterator CostIt;
441 if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt))
442 SROAArgValues[&I] = SROAArg;
444 return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I);
447 bool CallAnalyzer::visitIntToPtr(IntToPtrInst &I) {
448 // Propagate constants through ptrtoint.
449 Constant *COp = dyn_cast<Constant>(I.getOperand(0));
451 COp = SimplifiedValues.lookup(I.getOperand(0));
453 if (Constant *C = ConstantExpr::getIntToPtr(COp, I.getType())) {
454 SimplifiedValues[&I] = C;
458 // Track base/offset pairs when round-tripped through a pointer without
459 // modifications provided the integer is not too large.
460 Value *Op = I.getOperand(0);
461 unsigned IntegerSize = Op->getType()->getScalarSizeInBits();
462 const DataLayout &DL = F.getParent()->getDataLayout();
463 if (IntegerSize <= DL.getPointerSizeInBits()) {
464 std::pair<Value *, APInt> BaseAndOffset = ConstantOffsetPtrs.lookup(Op);
465 if (BaseAndOffset.first)
466 ConstantOffsetPtrs[&I] = BaseAndOffset;
469 // "Propagate" SROA here in the same manner as we do for ptrtoint above.
471 DenseMap<Value *, int>::iterator CostIt;
472 if (lookupSROAArgAndCost(Op, SROAArg, CostIt))
473 SROAArgValues[&I] = SROAArg;
475 return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I);
478 bool CallAnalyzer::visitCastInst(CastInst &I) {
479 // Propagate constants through ptrtoint.
480 Constant *COp = dyn_cast<Constant>(I.getOperand(0));
482 COp = SimplifiedValues.lookup(I.getOperand(0));
484 if (Constant *C = ConstantExpr::getCast(I.getOpcode(), COp, I.getType())) {
485 SimplifiedValues[&I] = C;
489 // Disable SROA in the face of arbitrary casts we don't whitelist elsewhere.
490 disableSROA(I.getOperand(0));
492 return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I);
495 bool CallAnalyzer::visitUnaryInstruction(UnaryInstruction &I) {
496 Value *Operand = I.getOperand(0);
497 Constant *COp = dyn_cast<Constant>(Operand);
499 COp = SimplifiedValues.lookup(Operand);
501 const DataLayout &DL = F.getParent()->getDataLayout();
502 if (Constant *C = ConstantFoldInstOperands(I.getOpcode(), I.getType(),
504 SimplifiedValues[&I] = C;
509 // Disable any SROA on the argument to arbitrary unary operators.
510 disableSROA(Operand);
515 bool CallAnalyzer::paramHasAttr(Argument *A, Attribute::AttrKind Attr) {
516 unsigned ArgNo = A->getArgNo();
517 return CandidateCS.paramHasAttr(ArgNo+1, Attr);
520 bool CallAnalyzer::isKnownNonNullInCallee(Value *V) {
521 // Does the *call site* have the NonNull attribute set on an argument? We
522 // use the attribute on the call site to memoize any analysis done in the
523 // caller. This will also trip if the callee function has a non-null
524 // parameter attribute, but that's a less interesting case because hopefully
525 // the callee would already have been simplified based on that.
526 if (Argument *A = dyn_cast<Argument>(V))
527 if (paramHasAttr(A, Attribute::NonNull))
530 // Is this an alloca in the caller? This is distinct from the attribute case
531 // above because attributes aren't updated within the inliner itself and we
532 // always want to catch the alloca derived case.
533 if (isAllocaDerivedArg(V))
534 // We can actually predict the result of comparisons between an
535 // alloca-derived value and null. Note that this fires regardless of
542 bool CallAnalyzer::visitCmpInst(CmpInst &I) {
543 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
544 // First try to handle simplified comparisons.
545 if (!isa<Constant>(LHS))
546 if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
548 if (!isa<Constant>(RHS))
549 if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
551 if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
552 if (Constant *CRHS = dyn_cast<Constant>(RHS))
553 if (Constant *C = ConstantExpr::getCompare(I.getPredicate(), CLHS, CRHS)) {
554 SimplifiedValues[&I] = C;
559 if (I.getOpcode() == Instruction::FCmp)
562 // Otherwise look for a comparison between constant offset pointers with
564 Value *LHSBase, *RHSBase;
565 APInt LHSOffset, RHSOffset;
566 std::tie(LHSBase, LHSOffset) = ConstantOffsetPtrs.lookup(LHS);
568 std::tie(RHSBase, RHSOffset) = ConstantOffsetPtrs.lookup(RHS);
569 if (RHSBase && LHSBase == RHSBase) {
570 // We have common bases, fold the icmp to a constant based on the
572 Constant *CLHS = ConstantInt::get(LHS->getContext(), LHSOffset);
573 Constant *CRHS = ConstantInt::get(RHS->getContext(), RHSOffset);
574 if (Constant *C = ConstantExpr::getICmp(I.getPredicate(), CLHS, CRHS)) {
575 SimplifiedValues[&I] = C;
576 ++NumConstantPtrCmps;
582 // If the comparison is an equality comparison with null, we can simplify it
583 // if we know the value (argument) can't be null
584 if (I.isEquality() && isa<ConstantPointerNull>(I.getOperand(1)) &&
585 isKnownNonNullInCallee(I.getOperand(0))) {
586 bool IsNotEqual = I.getPredicate() == CmpInst::ICMP_NE;
587 SimplifiedValues[&I] = IsNotEqual ? ConstantInt::getTrue(I.getType())
588 : ConstantInt::getFalse(I.getType());
591 // Finally check for SROA candidates in comparisons.
593 DenseMap<Value *, int>::iterator CostIt;
594 if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) {
595 if (isa<ConstantPointerNull>(I.getOperand(1))) {
596 accumulateSROACost(CostIt, InlineConstants::InstrCost);
606 bool CallAnalyzer::visitSub(BinaryOperator &I) {
607 // Try to handle a special case: we can fold computing the difference of two
608 // constant-related pointers.
609 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
610 Value *LHSBase, *RHSBase;
611 APInt LHSOffset, RHSOffset;
612 std::tie(LHSBase, LHSOffset) = ConstantOffsetPtrs.lookup(LHS);
614 std::tie(RHSBase, RHSOffset) = ConstantOffsetPtrs.lookup(RHS);
615 if (RHSBase && LHSBase == RHSBase) {
616 // We have common bases, fold the subtract to a constant based on the
618 Constant *CLHS = ConstantInt::get(LHS->getContext(), LHSOffset);
619 Constant *CRHS = ConstantInt::get(RHS->getContext(), RHSOffset);
620 if (Constant *C = ConstantExpr::getSub(CLHS, CRHS)) {
621 SimplifiedValues[&I] = C;
622 ++NumConstantPtrDiffs;
628 // Otherwise, fall back to the generic logic for simplifying and handling
630 return Base::visitSub(I);
633 bool CallAnalyzer::visitBinaryOperator(BinaryOperator &I) {
634 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
635 const DataLayout &DL = F.getParent()->getDataLayout();
636 if (!isa<Constant>(LHS))
637 if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
639 if (!isa<Constant>(RHS))
640 if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
642 Value *SimpleV = nullptr;
643 if (auto FI = dyn_cast<FPMathOperator>(&I))
645 SimplifyFPBinOp(I.getOpcode(), LHS, RHS, FI->getFastMathFlags(), DL);
647 SimpleV = SimplifyBinOp(I.getOpcode(), LHS, RHS, DL);
649 if (Constant *C = dyn_cast_or_null<Constant>(SimpleV)) {
650 SimplifiedValues[&I] = C;
654 // Disable any SROA on arguments to arbitrary, unsimplified binary operators.
661 bool CallAnalyzer::visitLoad(LoadInst &I) {
663 DenseMap<Value *, int>::iterator CostIt;
664 if (lookupSROAArgAndCost(I.getPointerOperand(), SROAArg, CostIt)) {
666 accumulateSROACost(CostIt, InlineConstants::InstrCost);
676 bool CallAnalyzer::visitStore(StoreInst &I) {
678 DenseMap<Value *, int>::iterator CostIt;
679 if (lookupSROAArgAndCost(I.getPointerOperand(), SROAArg, CostIt)) {
681 accumulateSROACost(CostIt, InlineConstants::InstrCost);
691 bool CallAnalyzer::visitExtractValue(ExtractValueInst &I) {
692 // Constant folding for extract value is trivial.
693 Constant *C = dyn_cast<Constant>(I.getAggregateOperand());
695 C = SimplifiedValues.lookup(I.getAggregateOperand());
697 SimplifiedValues[&I] = ConstantExpr::getExtractValue(C, I.getIndices());
701 // SROA can look through these but give them a cost.
705 bool CallAnalyzer::visitInsertValue(InsertValueInst &I) {
706 // Constant folding for insert value is trivial.
707 Constant *AggC = dyn_cast<Constant>(I.getAggregateOperand());
709 AggC = SimplifiedValues.lookup(I.getAggregateOperand());
710 Constant *InsertedC = dyn_cast<Constant>(I.getInsertedValueOperand());
712 InsertedC = SimplifiedValues.lookup(I.getInsertedValueOperand());
713 if (AggC && InsertedC) {
714 SimplifiedValues[&I] = ConstantExpr::getInsertValue(AggC, InsertedC,
719 // SROA can look through these but give them a cost.
723 /// \brief Try to simplify a call site.
725 /// Takes a concrete function and callsite and tries to actually simplify it by
726 /// analyzing the arguments and call itself with instsimplify. Returns true if
727 /// it has simplified the callsite to some other entity (a constant), making it
729 bool CallAnalyzer::simplifyCallSite(Function *F, CallSite CS) {
730 // FIXME: Using the instsimplify logic directly for this is inefficient
731 // because we have to continually rebuild the argument list even when no
732 // simplifications can be performed. Until that is fixed with remapping
733 // inside of instsimplify, directly constant fold calls here.
734 if (!canConstantFoldCallTo(F))
737 // Try to re-map the arguments to constants.
738 SmallVector<Constant *, 4> ConstantArgs;
739 ConstantArgs.reserve(CS.arg_size());
740 for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end();
742 Constant *C = dyn_cast<Constant>(*I);
744 C = dyn_cast_or_null<Constant>(SimplifiedValues.lookup(*I));
746 return false; // This argument doesn't map to a constant.
748 ConstantArgs.push_back(C);
750 if (Constant *C = ConstantFoldCall(F, ConstantArgs)) {
751 SimplifiedValues[CS.getInstruction()] = C;
758 bool CallAnalyzer::visitCallSite(CallSite CS) {
759 if (CS.hasFnAttr(Attribute::ReturnsTwice) &&
760 !F.hasFnAttribute(Attribute::ReturnsTwice)) {
761 // This aborts the entire analysis.
762 ExposesReturnsTwice = true;
766 cast<CallInst>(CS.getInstruction())->cannotDuplicate())
767 ContainsNoDuplicateCall = true;
769 if (Function *F = CS.getCalledFunction()) {
770 // When we have a concrete function, first try to simplify it directly.
771 if (simplifyCallSite(F, CS))
774 // Next check if it is an intrinsic we know about.
775 // FIXME: Lift this into part of the InstVisitor.
776 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
777 switch (II->getIntrinsicID()) {
779 return Base::visitCallSite(CS);
781 case Intrinsic::memset:
782 case Intrinsic::memcpy:
783 case Intrinsic::memmove:
784 // SROA can usually chew through these intrinsics, but they aren't free.
786 case Intrinsic::frameescape:
787 HasFrameEscape = true;
792 if (F == CS.getInstruction()->getParent()->getParent()) {
793 // This flag will fully abort the analysis, so don't bother with anything
795 IsRecursiveCall = true;
799 if (TTI.isLoweredToCall(F)) {
800 // We account for the average 1 instruction per call argument setup
802 Cost += CS.arg_size() * InlineConstants::InstrCost;
804 // Everything other than inline ASM will also have a significant cost
805 // merely from making the call.
806 if (!isa<InlineAsm>(CS.getCalledValue()))
807 Cost += InlineConstants::CallPenalty;
810 return Base::visitCallSite(CS);
813 // Otherwise we're in a very special case -- an indirect function call. See
814 // if we can be particularly clever about this.
815 Value *Callee = CS.getCalledValue();
817 // First, pay the price of the argument setup. We account for the average
818 // 1 instruction per call argument setup here.
819 Cost += CS.arg_size() * InlineConstants::InstrCost;
821 // Next, check if this happens to be an indirect function call to a known
822 // function in this inline context. If not, we've done all we can.
823 Function *F = dyn_cast_or_null<Function>(SimplifiedValues.lookup(Callee));
825 return Base::visitCallSite(CS);
827 // If we have a constant that we are calling as a function, we can peer
828 // through it and see the function target. This happens not infrequently
829 // during devirtualization and so we want to give it a hefty bonus for
830 // inlining, but cap that bonus in the event that inlining wouldn't pan
831 // out. Pretend to inline the function, with a custom threshold.
832 CallAnalyzer CA(TTI, ACT, *F, InlineConstants::IndirectCallThreshold, CS);
833 if (CA.analyzeCall(CS)) {
834 // We were able to inline the indirect call! Subtract the cost from the
835 // bonus we want to apply, but don't go below zero.
836 Cost -= std::max(0, InlineConstants::IndirectCallThreshold - CA.getCost());
839 return Base::visitCallSite(CS);
842 bool CallAnalyzer::visitReturnInst(ReturnInst &RI) {
843 // At least one return instruction will be free after inlining.
844 bool Free = !HasReturn;
849 bool CallAnalyzer::visitBranchInst(BranchInst &BI) {
850 // We model unconditional branches as essentially free -- they really
851 // shouldn't exist at all, but handling them makes the behavior of the
852 // inliner more regular and predictable. Interestingly, conditional branches
853 // which will fold away are also free.
854 return BI.isUnconditional() || isa<ConstantInt>(BI.getCondition()) ||
855 dyn_cast_or_null<ConstantInt>(
856 SimplifiedValues.lookup(BI.getCondition()));
859 bool CallAnalyzer::visitSwitchInst(SwitchInst &SI) {
860 // We model unconditional switches as free, see the comments on handling
862 if (isa<ConstantInt>(SI.getCondition()))
864 if (Value *V = SimplifiedValues.lookup(SI.getCondition()))
865 if (isa<ConstantInt>(V))
868 // Otherwise, we need to accumulate a cost proportional to the number of
869 // distinct successor blocks. This fan-out in the CFG cannot be represented
870 // for free even if we can represent the core switch as a jumptable that
871 // takes a single instruction.
873 // NB: We convert large switches which are just used to initialize large phi
874 // nodes to lookup tables instead in simplify-cfg, so this shouldn't prevent
875 // inlining those. It will prevent inlining in cases where the optimization
876 // does not (yet) fire.
877 SmallPtrSet<BasicBlock *, 8> SuccessorBlocks;
878 SuccessorBlocks.insert(SI.getDefaultDest());
879 for (auto I = SI.case_begin(), E = SI.case_end(); I != E; ++I)
880 SuccessorBlocks.insert(I.getCaseSuccessor());
881 // Add cost corresponding to the number of distinct destinations. The first
882 // we model as free because of fallthrough.
883 Cost += (SuccessorBlocks.size() - 1) * InlineConstants::InstrCost;
887 bool CallAnalyzer::visitIndirectBrInst(IndirectBrInst &IBI) {
888 // We never want to inline functions that contain an indirectbr. This is
889 // incorrect because all the blockaddress's (in static global initializers
890 // for example) would be referring to the original function, and this
891 // indirect jump would jump from the inlined copy of the function into the
892 // original function which is extremely undefined behavior.
893 // FIXME: This logic isn't really right; we can safely inline functions with
894 // indirectbr's as long as no other function or global references the
895 // blockaddress of a block within the current function.
896 HasIndirectBr = true;
900 bool CallAnalyzer::visitResumeInst(ResumeInst &RI) {
901 // FIXME: It's not clear that a single instruction is an accurate model for
902 // the inline cost of a resume instruction.
906 bool CallAnalyzer::visitUnreachableInst(UnreachableInst &I) {
907 // FIXME: It might be reasonably to discount the cost of instructions leading
908 // to unreachable as they have the lowest possible impact on both runtime and
910 return true; // No actual code is needed for unreachable.
913 bool CallAnalyzer::visitInstruction(Instruction &I) {
914 // Some instructions are free. All of the free intrinsics can also be
915 // handled by SROA, etc.
916 if (TargetTransformInfo::TCC_Free == TTI.getUserCost(&I))
919 // We found something we don't understand or can't handle. Mark any SROA-able
920 // values in the operand list as no longer viable.
921 for (User::op_iterator OI = I.op_begin(), OE = I.op_end(); OI != OE; ++OI)
928 /// \brief Analyze a basic block for its contribution to the inline cost.
930 /// This method walks the analyzer over every instruction in the given basic
931 /// block and accounts for their cost during inlining at this callsite. It
932 /// aborts early if the threshold has been exceeded or an impossible to inline
933 /// construct has been detected. It returns false if inlining is no longer
934 /// viable, and true if inlining remains viable.
935 bool CallAnalyzer::analyzeBlock(BasicBlock *BB,
936 SmallPtrSetImpl<const Value *> &EphValues) {
937 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
938 // FIXME: Currently, the number of instructions in a function regardless of
939 // our ability to simplify them during inline to constants or dead code,
940 // are actually used by the vector bonus heuristic. As long as that's true,
941 // we have to special case debug intrinsics here to prevent differences in
942 // inlining due to debug symbols. Eventually, the number of unsimplified
943 // instructions shouldn't factor into the cost computation, but until then,
944 // hack around it here.
945 if (isa<DbgInfoIntrinsic>(I))
948 // Skip ephemeral values.
949 if (EphValues.count(I))
953 if (isa<ExtractElementInst>(I) || I->getType()->isVectorTy())
954 ++NumVectorInstructions;
956 // If the instruction is floating point, and the target says this operation is
957 // expensive or the function has the "use-soft-float" attribute, this may
958 // eventually become a library call. Treat the cost as such.
959 if (I->getType()->isFloatingPointTy()) {
960 bool hasSoftFloatAttr = false;
962 // If the function has the "use-soft-float" attribute, mark it as expensive.
963 if (F.hasFnAttribute("use-soft-float")) {
964 Attribute Attr = F.getFnAttribute("use-soft-float");
965 StringRef Val = Attr.getValueAsString();
967 hasSoftFloatAttr = true;
970 if (TTI.getFPOpCost(I->getType()) == TargetTransformInfo::TCC_Expensive ||
972 Cost += InlineConstants::CallPenalty;
975 // If the instruction simplified to a constant, there is no cost to this
976 // instruction. Visit the instructions using our InstVisitor to account for
977 // all of the per-instruction logic. The visit tree returns true if we
978 // consumed the instruction in any way, and false if the instruction's base
979 // cost should count against inlining.
981 ++NumInstructionsSimplified;
983 Cost += InlineConstants::InstrCost;
985 // If the visit this instruction detected an uninlinable pattern, abort.
986 if (IsRecursiveCall || ExposesReturnsTwice || HasDynamicAlloca ||
987 HasIndirectBr || HasFrameEscape)
990 // If the caller is a recursive function then we don't want to inline
991 // functions which allocate a lot of stack space because it would increase
992 // the caller stack usage dramatically.
993 if (IsCallerRecursive &&
994 AllocatedSize > InlineConstants::TotalAllocaSizeRecursiveCaller)
997 // Check if we've past the maximum possible threshold so we don't spin in
998 // huge basic blocks that will never inline.
999 if (Cost > Threshold)
1006 /// \brief Compute the base pointer and cumulative constant offsets for V.
1008 /// This strips all constant offsets off of V, leaving it the base pointer, and
1009 /// accumulates the total constant offset applied in the returned constant. It
1010 /// returns 0 if V is not a pointer, and returns the constant '0' if there are
1011 /// no constant offsets applied.
1012 ConstantInt *CallAnalyzer::stripAndComputeInBoundsConstantOffsets(Value *&V) {
1013 if (!V->getType()->isPointerTy())
1016 const DataLayout &DL = F.getParent()->getDataLayout();
1017 unsigned IntPtrWidth = DL.getPointerSizeInBits();
1018 APInt Offset = APInt::getNullValue(IntPtrWidth);
1020 // Even though we don't look through PHI nodes, we could be called on an
1021 // instruction in an unreachable block, which may be on a cycle.
1022 SmallPtrSet<Value *, 4> Visited;
1025 if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
1026 if (!GEP->isInBounds() || !accumulateGEPOffset(*GEP, Offset))
1028 V = GEP->getPointerOperand();
1029 } else if (Operator::getOpcode(V) == Instruction::BitCast) {
1030 V = cast<Operator>(V)->getOperand(0);
1031 } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
1032 if (GA->mayBeOverridden())
1034 V = GA->getAliasee();
1038 assert(V->getType()->isPointerTy() && "Unexpected operand type!");
1039 } while (Visited.insert(V).second);
1041 Type *IntPtrTy = DL.getIntPtrType(V->getContext());
1042 return cast<ConstantInt>(ConstantInt::get(IntPtrTy, Offset));
1045 /// \brief Analyze a call site for potential inlining.
1047 /// Returns true if inlining this call is viable, and false if it is not
1048 /// viable. It computes the cost and adjusts the threshold based on numerous
1049 /// factors and heuristics. If this method returns false but the computed cost
1050 /// is below the computed threshold, then inlining was forcibly disabled by
1051 /// some artifact of the routine.
1052 bool CallAnalyzer::analyzeCall(CallSite CS) {
1055 // Perform some tweaks to the cost and threshold based on the direct
1056 // callsite information.
1058 // We want to more aggressively inline vector-dense kernels, so up the
1059 // threshold, and we'll lower it if the % of vector instructions gets too
1060 // low. Note that these bonuses are some what arbitrary and evolved over time
1061 // by accident as much as because they are principled bonuses.
1063 // FIXME: It would be nice to remove all such bonuses. At least it would be
1064 // nice to base the bonus values on something more scientific.
1065 assert(NumInstructions == 0);
1066 assert(NumVectorInstructions == 0);
1067 FiftyPercentVectorBonus = 3 * Threshold / 2;
1068 TenPercentVectorBonus = 3 * Threshold / 4;
1069 const DataLayout &DL = F.getParent()->getDataLayout();
1071 // Track whether the post-inlining function would have more than one basic
1072 // block. A single basic block is often intended for inlining. Balloon the
1073 // threshold by 50% until we pass the single-BB phase.
1074 bool SingleBB = true;
1075 int SingleBBBonus = Threshold / 2;
1077 // Speculatively apply all possible bonuses to Threshold. If cost exceeds
1078 // this Threshold any time, and cost cannot decrease, we can stop processing
1079 // the rest of the function body.
1080 Threshold += (SingleBBBonus + FiftyPercentVectorBonus);
1082 // Give out bonuses per argument, as the instructions setting them up will
1083 // be gone after inlining.
1084 for (unsigned I = 0, E = CS.arg_size(); I != E; ++I) {
1085 if (CS.isByValArgument(I)) {
1086 // We approximate the number of loads and stores needed by dividing the
1087 // size of the byval type by the target's pointer size.
1088 PointerType *PTy = cast<PointerType>(CS.getArgument(I)->getType());
1089 unsigned TypeSize = DL.getTypeSizeInBits(PTy->getElementType());
1090 unsigned PointerSize = DL.getPointerSizeInBits();
1091 // Ceiling division.
1092 unsigned NumStores = (TypeSize + PointerSize - 1) / PointerSize;
1094 // If it generates more than 8 stores it is likely to be expanded as an
1095 // inline memcpy so we take that as an upper bound. Otherwise we assume
1096 // one load and one store per word copied.
1097 // FIXME: The maxStoresPerMemcpy setting from the target should be used
1098 // here instead of a magic number of 8, but it's not available via
1100 NumStores = std::min(NumStores, 8U);
1102 Cost -= 2 * NumStores * InlineConstants::InstrCost;
1104 // For non-byval arguments subtract off one instruction per call
1106 Cost -= InlineConstants::InstrCost;
1110 // If there is only one call of the function, and it has internal linkage,
1111 // the cost of inlining it drops dramatically.
1112 bool OnlyOneCallAndLocalLinkage = F.hasLocalLinkage() && F.hasOneUse() &&
1113 &F == CS.getCalledFunction();
1114 if (OnlyOneCallAndLocalLinkage)
1115 Cost += InlineConstants::LastCallToStaticBonus;
1117 // If the instruction after the call, or if the normal destination of the
1118 // invoke is an unreachable instruction, the function is noreturn. As such,
1119 // there is little point in inlining this unless there is literally zero
1121 Instruction *Instr = CS.getInstruction();
1122 if (InvokeInst *II = dyn_cast<InvokeInst>(Instr)) {
1123 if (isa<UnreachableInst>(II->getNormalDest()->begin()))
1125 } else if (isa<UnreachableInst>(++BasicBlock::iterator(Instr)))
1128 // If this function uses the coldcc calling convention, prefer not to inline
1130 if (F.getCallingConv() == CallingConv::Cold)
1131 Cost += InlineConstants::ColdccPenalty;
1133 // Check if we're done. This can happen due to bonuses and penalties.
1134 if (Cost > Threshold)
1140 Function *Caller = CS.getInstruction()->getParent()->getParent();
1141 // Check if the caller function is recursive itself.
1142 for (User *U : Caller->users()) {
1146 Instruction *I = Site.getInstruction();
1147 if (I->getParent()->getParent() == Caller) {
1148 IsCallerRecursive = true;
1153 // Populate our simplified values by mapping from function arguments to call
1154 // arguments with known important simplifications.
1155 CallSite::arg_iterator CAI = CS.arg_begin();
1156 for (Function::arg_iterator FAI = F.arg_begin(), FAE = F.arg_end();
1157 FAI != FAE; ++FAI, ++CAI) {
1158 assert(CAI != CS.arg_end());
1159 if (Constant *C = dyn_cast<Constant>(CAI))
1160 SimplifiedValues[FAI] = C;
1162 Value *PtrArg = *CAI;
1163 if (ConstantInt *C = stripAndComputeInBoundsConstantOffsets(PtrArg)) {
1164 ConstantOffsetPtrs[FAI] = std::make_pair(PtrArg, C->getValue());
1166 // We can SROA any pointer arguments derived from alloca instructions.
1167 if (isa<AllocaInst>(PtrArg)) {
1168 SROAArgValues[FAI] = PtrArg;
1169 SROAArgCosts[PtrArg] = 0;
1173 NumConstantArgs = SimplifiedValues.size();
1174 NumConstantOffsetPtrArgs = ConstantOffsetPtrs.size();
1175 NumAllocaArgs = SROAArgValues.size();
1177 // FIXME: If a caller has multiple calls to a callee, we end up recomputing
1178 // the ephemeral values multiple times (and they're completely determined by
1179 // the callee, so this is purely duplicate work).
1180 SmallPtrSet<const Value *, 32> EphValues;
1181 CodeMetrics::collectEphemeralValues(&F, &ACT->getAssumptionCache(F), EphValues);
1183 // The worklist of live basic blocks in the callee *after* inlining. We avoid
1184 // adding basic blocks of the callee which can be proven to be dead for this
1185 // particular call site in order to get more accurate cost estimates. This
1186 // requires a somewhat heavyweight iteration pattern: we need to walk the
1187 // basic blocks in a breadth-first order as we insert live successors. To
1188 // accomplish this, prioritizing for small iterations because we exit after
1189 // crossing our threshold, we use a small-size optimized SetVector.
1190 typedef SetVector<BasicBlock *, SmallVector<BasicBlock *, 16>,
1191 SmallPtrSet<BasicBlock *, 16> > BBSetVector;
1192 BBSetVector BBWorklist;
1193 BBWorklist.insert(&F.getEntryBlock());
1194 // Note that we *must not* cache the size, this loop grows the worklist.
1195 for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
1196 // Bail out the moment we cross the threshold. This means we'll under-count
1197 // the cost, but only when undercounting doesn't matter.
1198 if (Cost > Threshold)
1201 BasicBlock *BB = BBWorklist[Idx];
1205 // Disallow inlining a blockaddress. A blockaddress only has defined
1206 // behavior for an indirect branch in the same function, and we do not
1207 // currently support inlining indirect branches. But, the inliner may not
1208 // see an indirect branch that ends up being dead code at a particular call
1209 // site. If the blockaddress escapes the function, e.g., via a global
1210 // variable, inlining may lead to an invalid cross-function reference.
1211 if (BB->hasAddressTaken())
1214 // Analyze the cost of this block. If we blow through the threshold, this
1215 // returns false, and we can bail on out.
1216 if (!analyzeBlock(BB, EphValues)) {
1217 if (IsRecursiveCall || ExposesReturnsTwice || HasDynamicAlloca ||
1218 HasIndirectBr || HasFrameEscape)
1221 // If the caller is a recursive function then we don't want to inline
1222 // functions which allocate a lot of stack space because it would increase
1223 // the caller stack usage dramatically.
1224 if (IsCallerRecursive &&
1225 AllocatedSize > InlineConstants::TotalAllocaSizeRecursiveCaller)
1231 TerminatorInst *TI = BB->getTerminator();
1233 // Add in the live successors by first checking whether we have terminator
1234 // that may be simplified based on the values simplified by this call.
1235 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
1236 if (BI->isConditional()) {
1237 Value *Cond = BI->getCondition();
1238 if (ConstantInt *SimpleCond
1239 = dyn_cast_or_null<ConstantInt>(SimplifiedValues.lookup(Cond))) {
1240 BBWorklist.insert(BI->getSuccessor(SimpleCond->isZero() ? 1 : 0));
1244 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
1245 Value *Cond = SI->getCondition();
1246 if (ConstantInt *SimpleCond
1247 = dyn_cast_or_null<ConstantInt>(SimplifiedValues.lookup(Cond))) {
1248 BBWorklist.insert(SI->findCaseValue(SimpleCond).getCaseSuccessor());
1253 // If we're unable to select a particular successor, just count all of
1255 for (unsigned TIdx = 0, TSize = TI->getNumSuccessors(); TIdx != TSize;
1257 BBWorklist.insert(TI->getSuccessor(TIdx));
1259 // If we had any successors at this point, than post-inlining is likely to
1260 // have them as well. Note that we assume any basic blocks which existed
1261 // due to branches or switches which folded above will also fold after
1263 if (SingleBB && TI->getNumSuccessors() > 1) {
1264 // Take off the bonus we applied to the threshold.
1265 Threshold -= SingleBBBonus;
1270 // If this is a noduplicate call, we can still inline as long as
1271 // inlining this would cause the removal of the caller (so the instruction
1272 // is not actually duplicated, just moved).
1273 if (!OnlyOneCallAndLocalLinkage && ContainsNoDuplicateCall)
1276 // We applied the maximum possible vector bonus at the beginning. Now,
1277 // subtract the excess bonus, if any, from the Threshold before
1278 // comparing against Cost.
1279 if (NumVectorInstructions <= NumInstructions / 10)
1280 Threshold -= FiftyPercentVectorBonus;
1281 else if (NumVectorInstructions <= NumInstructions / 2)
1282 Threshold -= (FiftyPercentVectorBonus - TenPercentVectorBonus);
1284 return Cost < Threshold;
1287 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1288 /// \brief Dump stats about this call's analysis.
1289 void CallAnalyzer::dump() {
1290 #define DEBUG_PRINT_STAT(x) dbgs() << " " #x ": " << x << "\n"
1291 DEBUG_PRINT_STAT(NumConstantArgs);
1292 DEBUG_PRINT_STAT(NumConstantOffsetPtrArgs);
1293 DEBUG_PRINT_STAT(NumAllocaArgs);
1294 DEBUG_PRINT_STAT(NumConstantPtrCmps);
1295 DEBUG_PRINT_STAT(NumConstantPtrDiffs);
1296 DEBUG_PRINT_STAT(NumInstructionsSimplified);
1297 DEBUG_PRINT_STAT(NumInstructions);
1298 DEBUG_PRINT_STAT(SROACostSavings);
1299 DEBUG_PRINT_STAT(SROACostSavingsLost);
1300 DEBUG_PRINT_STAT(ContainsNoDuplicateCall);
1301 DEBUG_PRINT_STAT(Cost);
1302 DEBUG_PRINT_STAT(Threshold);
1303 #undef DEBUG_PRINT_STAT
1307 INITIALIZE_PASS_BEGIN(InlineCostAnalysis, "inline-cost", "Inline Cost Analysis",
1309 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
1310 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
1311 INITIALIZE_PASS_END(InlineCostAnalysis, "inline-cost", "Inline Cost Analysis",
1314 char InlineCostAnalysis::ID = 0;
1316 InlineCostAnalysis::InlineCostAnalysis() : CallGraphSCCPass(ID) {}
1318 InlineCostAnalysis::~InlineCostAnalysis() {}
1320 void InlineCostAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
1321 AU.setPreservesAll();
1322 AU.addRequired<AssumptionCacheTracker>();
1323 AU.addRequired<TargetTransformInfoWrapperPass>();
1324 CallGraphSCCPass::getAnalysisUsage(AU);
1327 bool InlineCostAnalysis::runOnSCC(CallGraphSCC &SCC) {
1328 TTIWP = &getAnalysis<TargetTransformInfoWrapperPass>();
1329 ACT = &getAnalysis<AssumptionCacheTracker>();
1333 InlineCost InlineCostAnalysis::getInlineCost(CallSite CS, int Threshold) {
1334 return getInlineCost(CS, CS.getCalledFunction(), Threshold);
1337 /// \brief Test that two functions either have or have not the given attribute
1338 /// at the same time.
1339 template<typename AttrKind>
1340 static bool attributeMatches(Function *F1, Function *F2, AttrKind Attr) {
1341 return F1->getFnAttribute(Attr) == F2->getFnAttribute(Attr);
1344 /// \brief Test that there are no attribute conflicts between Caller and Callee
1345 /// that prevent inlining.
1346 static bool functionsHaveCompatibleAttributes(Function *Caller,
1348 TargetTransformInfo &TTI) {
1349 return TTI.hasCompatibleFunctionAttributes(Caller, Callee) &&
1350 attributeMatches(Caller, Callee, Attribute::SanitizeAddress) &&
1351 attributeMatches(Caller, Callee, Attribute::SanitizeMemory) &&
1352 attributeMatches(Caller, Callee, Attribute::SanitizeThread);
1355 InlineCost InlineCostAnalysis::getInlineCost(CallSite CS, Function *Callee,
1357 // Cannot inline indirect calls.
1359 return llvm::InlineCost::getNever();
1361 // Calls to functions with always-inline attributes should be inlined
1362 // whenever possible.
1363 if (CS.hasFnAttr(Attribute::AlwaysInline)) {
1364 if (isInlineViable(*Callee))
1365 return llvm::InlineCost::getAlways();
1366 return llvm::InlineCost::getNever();
1369 // Never inline functions with conflicting attributes (unless callee has
1370 // always-inline attribute).
1371 if (!functionsHaveCompatibleAttributes(CS.getCaller(), Callee,
1372 TTIWP->getTTI(*Callee)))
1373 return llvm::InlineCost::getNever();
1375 // Don't inline this call if the caller has the optnone attribute.
1376 if (CS.getCaller()->hasFnAttribute(Attribute::OptimizeNone))
1377 return llvm::InlineCost::getNever();
1379 // Don't inline functions which can be redefined at link-time to mean
1380 // something else. Don't inline functions marked noinline or call sites
1382 if (Callee->mayBeOverridden() ||
1383 Callee->hasFnAttribute(Attribute::NoInline) || CS.isNoInline())
1384 return llvm::InlineCost::getNever();
1386 DEBUG(llvm::dbgs() << " Analyzing call of " << Callee->getName()
1389 CallAnalyzer CA(TTIWP->getTTI(*Callee), ACT, *Callee, Threshold, CS);
1390 bool ShouldInline = CA.analyzeCall(CS);
1394 // Check if there was a reason to force inlining or no inlining.
1395 if (!ShouldInline && CA.getCost() < CA.getThreshold())
1396 return InlineCost::getNever();
1397 if (ShouldInline && CA.getCost() >= CA.getThreshold())
1398 return InlineCost::getAlways();
1400 return llvm::InlineCost::get(CA.getCost(), CA.getThreshold());
1403 bool InlineCostAnalysis::isInlineViable(Function &F) {
1404 bool ReturnsTwice = F.hasFnAttribute(Attribute::ReturnsTwice);
1405 for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) {
1406 // Disallow inlining of functions which contain indirect branches or
1408 if (isa<IndirectBrInst>(BI->getTerminator()) || BI->hasAddressTaken())
1411 for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE;
1417 // Disallow recursive calls.
1418 if (&F == CS.getCalledFunction())
1421 // Disallow calls which expose returns-twice to a function not previously
1422 // attributed as such.
1423 if (!ReturnsTwice && CS.isCall() &&
1424 cast<CallInst>(CS.getInstruction())->canReturnTwice())
1427 // Disallow inlining functions that call @llvm.frameescape. Doing this
1428 // correctly would require major changes to the inliner.
1429 if (CS.getCalledFunction() &&
1430 CS.getCalledFunction()->getIntrinsicID() ==
1431 llvm::Intrinsic::frameescape)