Index: include/llvm/Analysis/InlineCost.h =================================================================== --- include/llvm/Analysis/InlineCost.h +++ include/llvm/Analysis/InlineCost.h @@ -38,6 +38,70 @@ const unsigned TotalAllocaSizeRecursiveCaller = 1024; } +namespace InlineReportTypes { + +/// \brief Inlining and non-inlining reasons +/// +/// Each element of this enum is a reason why a function was or was not +/// inlined. These are used in the inlining report. Those with names +/// beginning with Inlr are reasons FOR inlining. Those with names +/// beginning with Ninlr are reasons for NOT inlining. +/// +/// NOTE: The order of the values below is significant. Those with a lower +/// enum value are considered more significant and will be given preference +/// when the inlining report is printed. (See the function bestInlineReason() +/// in InlineCost.cpp. +/// +typedef enum { + InlrFirst, // Just a marker placed before the first inlining reason + InlrNoReason, + InlrAlwaysInline, + InlrSingleLocalCall, + InlrSingleBasicBlock, + InlrEmptyFunction, + InlrVectorBonus, + InlrProfitable, + InlrLast, // Just a marker placed after the last inlining reason + NinlrFirst, // Just a marker placed before the first non-inlining reason + NinlrNoReason, + NinlrColdCC, + NinlrDeleted, + NinlrDuplicateCall, + NinlrDynamicAlloca, + NinlrExtern, + NinlrIndirect, + NinlrIndirectBranch, + NinlrBlockAddress, + NinlrCallsLocalEscape, + NinlrNeverInline, + NinlrIntrinsic, + NinlrOuterInlining, + NinlrRecursive, + NinlrReturnsTwice, + NinlrTooMuchStack, + NinlrVarargs, + NinlrMismatchedAttributes, + NinlrMismatchedGC, + NinlrMismatchedPersonality, + NinlrNoinlineAttribute, + NinlrNoinlineCallsite, + NinlrNoReturn, + NinlrOptNone, + NinlrInterposable, + NinlrNotAlwaysInline, + NinlrNewlyCreated, + NinlrNotProfitable, + NinlrOpBundles, + NinlrMSVCEH, + NinlrSEH, + NinlrLast // Just a marker placed after the last non-inlining reason +} InlineReason; + +} + +extern bool IsInlinedReason(InlineReportTypes::InlineReason Reason); +extern bool IsNotInlinedReason(InlineReportTypes::InlineReason Reason); + /// \brief Represents the cost of inlining a function. /// /// This supports special values for functions which should "always" or @@ -48,6 +112,9 @@ /// based on the information available for a particular callsite. They can be /// directly tested to determine if inlining should occur given the cost and /// threshold for this cost metric. +/// +/// This also includes the InlineReason, which is the principal reason that +/// a call site was or was not inlined. class InlineCost { enum SentinelValues { AlwaysInlineCost = INT_MIN, @@ -60,8 +127,12 @@ /// \brief The adjusted threshold against which this cost was computed. const int Threshold; + InlineReportTypes::InlineReason Reason; + // Trivial constructor, interesting logic in the factory functions below. - InlineCost(int Cost, int Threshold) : Cost(Cost), Threshold(Threshold) {} + InlineCost(int Cost, int Threshold, InlineReportTypes::InlineReason Reason + = InlineReportTypes::NinlrNoReason) : Cost(Cost), Threshold(Threshold), + Reason(Reason) {} public: static InlineCost get(int Cost, int Threshold) { @@ -69,9 +140,21 @@ assert(Cost < NeverInlineCost && "Cost crosses sentinel value"); return InlineCost(Cost, Threshold); } + static InlineCost get(int Cost, int Threshold, + InlineReportTypes::InlineReason Reason) { + assert(Cost > AlwaysInlineCost && "Cost crosses sentinel value"); + assert(Cost < NeverInlineCost && "Cost crosses sentinel value"); + return InlineCost(Cost, Threshold, Reason); + } static InlineCost getAlways() { return InlineCost(AlwaysInlineCost, 0); } + static InlineCost getAlways(InlineReportTypes::InlineReason Reason) { + return InlineCost(AlwaysInlineCost, 0, Reason); + } + static InlineCost getNever(InlineReportTypes::InlineReason Reason) { + return InlineCost(NeverInlineCost, 0, Reason); + } static InlineCost getNever() { return InlineCost(NeverInlineCost, 0); } @@ -96,6 +179,11 @@ /// Only valid if the cost is of the variable kind. Returns a negative /// value if the cost is too high to inline. int getCostDelta() const { return Threshold - getCost(); } + + InlineReportTypes::InlineReason getInlineReason() const + { return Reason; } + void setInlineReason(InlineReportTypes::InlineReason MyReason) + { Reason = MyReason; } }; /// \brief Get an InlineCost object representing the cost of inlining this @@ -127,8 +215,18 @@ /// \brief Return the default value of -inline-threshold. int getDefaultInlineThreshold(); +/// \brief Return the default value of -inlinehint-threshold. +int getHintThreshold(); + +/// \brief Return the default value of -inlineoptsize-threshold. +int getOptSizeThreshold(); + +/// \brief Return the default value of -inlinecold-threshold. +int getColdThreshold(); + /// \brief Minimal filter to detect invalid constructs for inlining. -bool isInlineViable(Function &Callee); +bool isInlineViable(Function &Callee, + InlineReportTypes::InlineReason& Reason); } #endif Index: lib/Analysis/InlineCost.cpp =================================================================== --- lib/Analysis/InlineCost.cpp +++ lib/Analysis/InlineCost.cpp @@ -34,11 +34,20 @@ #include "llvm/Support/raw_ostream.h" using namespace llvm; +using namespace InlineReportTypes; #define DEBUG_TYPE "inline-cost" STATISTIC(NumCallsAnalyzed, "Number of call sites analyzed"); +extern bool llvm::IsInlinedReason(InlineReason Reason) { + return Reason > InlrFirst && Reason < InlrLast; +} + +extern bool llvm::IsNotInlinedReason(InlineReason Reason) { + return Reason > NinlrFirst && Reason < NinlrLast; +} + // Threshold to use when optsize is specified (and there is no // -inline-threshold). const int OptSizeThreshold = 75; @@ -209,7 +218,7 @@ NumConstantPtrDiffs(0), NumInstructionsSimplified(0), SROACostSavings(0), SROACostSavingsLost(0) {} - bool analyzeCall(CallSite CS); + bool analyzeCall(CallSite CS, InlineReason* Reason); int getThreshold() { return Threshold; } int getCost() { return Cost; } @@ -601,7 +610,7 @@ return true; } -void CallAnalyzer::updateThreshold(CallSite CS, Function &Callee) { +void CallAnalyzer::updateThreshold(CallSite CS, Function &Callee) { // If no size growth is allowed for this inlining, set Threshold to 0. if (!allowSizeGrowth(CS)) { Threshold = 0; @@ -948,7 +957,7 @@ // inlining, but cap that bonus in the event that inlining wouldn't pan // out. Pretend to inline the function, with a custom threshold. CallAnalyzer CA(TTI, ACT, *F, InlineConstants::IndirectCallThreshold, CS); - if (CA.analyzeCall(CS)) { + if (CA.analyzeCall(CS, nullptr)) { // We were able to inline the indirect call! Subtract the cost from the // threshold to get the bonus we want to apply, but don't go below zero. Cost -= std::max(0, CA.getThreshold() - CA.getCost()); @@ -1134,6 +1143,29 @@ return true; } +/// +/// \brief Find the best inlining or non-inlining reason +/// +/// Given a 'DefaultReason' and a vector of inlining/non-inlining reasons, +/// return the best reason among all of them. Inlining/Non-inlining reasons +/// are considered better if their corresponding enum value is lower. +/// + +typedef SmallVector InlineReasonVector; + +static InlineReason bestInlineReason(const InlineReasonVector& ReasonVector, + InlineReason DefaultReason) +{ + InlineReason Reason = DefaultReason; + for (unsigned i = 0; i < ReasonVector.size(); i++) { + if (ReasonVector[i] < Reason) { + Reason = ReasonVector[i]; + } + } + return Reason; +} + + /// \brief Compute the base pointer and cumulative constant offsets for V. /// /// This strips all constant offsets off of V, leaving it the base pointer, and @@ -1179,9 +1211,15 @@ /// viable. It computes the cost and adjusts the threshold based on numerous /// factors and heuristics. If this method returns false but the computed cost /// is below the computed threshold, then inlining was forcibly disabled by -/// some artifact of the routine. -bool CallAnalyzer::analyzeCall(CallSite CS) { +/// some artifact of the routine. Also sets the value of *Reason to be the +/// principal the call site would be inlined or not inlined. +bool CallAnalyzer::analyzeCall(CallSite CS, InlineReason* Reason) { ++NumCallsAnalyzed; + InlineReason TempReason = NinlrNoReason; + InlineReason* ReasonAddr = Reason == nullptr ? &TempReason : Reason; + InlineReasonVector YesReasonVector; + InlineReasonVector NoReasonVector; + TempReason = NinlrNoReason; // Perform some tweaks to the cost and threshold based on the direct // callsite information. @@ -1246,20 +1284,28 @@ // the cost of inlining it drops dramatically. bool OnlyOneCallAndLocalLinkage = F.hasLocalLinkage() && F.hasOneUse() && &F == CS.getCalledFunction(); - if (OnlyOneCallAndLocalLinkage) + if (OnlyOneCallAndLocalLinkage) { Cost += InlineConstants::LastCallToStaticBonus; + YesReasonVector.push_back(InlrSingleLocalCall); + } // If this function uses the coldcc calling convention, prefer not to inline // it. - if (F.getCallingConv() == CallingConv::Cold) + if (F.getCallingConv() == CallingConv::Cold) { Cost += InlineConstants::ColdccPenalty; + NoReasonVector.push_back(NinlrColdCC); + } // Check if we're done. This can happen due to bonuses and penalties. - if (Cost > Threshold) + if (Cost > Threshold) { + *ReasonAddr = bestInlineReason(NoReasonVector, NinlrNotProfitable); return false; + } - if (F.empty()) + if (F.empty()) { + *ReasonAddr = InlrEmptyFunction; return true; + } Function *Caller = CS.getInstruction()->getParent()->getParent(); // Check if the caller function is recursive itself. @@ -1332,22 +1378,42 @@ // see an indirect branch that ends up being dead code at a particular call // site. If the blockaddress escapes the function, e.g., via a global // variable, inlining may lead to an invalid cross-function reference. - if (BB->hasAddressTaken()) + if (BB->hasAddressTaken()) { + *ReasonAddr = NinlrBlockAddress; return false; + } // Analyze the cost of this block. If we blow through the threshold, this // returns false, and we can bail on out. if (!analyzeBlock(BB, EphValues)) { - if (IsRecursiveCall || ExposesReturnsTwice || HasDynamicAlloca || - HasIndirectBr || HasFrameEscape) - return false; - + if (IsRecursiveCall) { + *ReasonAddr = NinlrRecursive; + return false; + } + if (ExposesReturnsTwice) { + *ReasonAddr = NinlrReturnsTwice; + return false; + } + if (HasDynamicAlloca) { + *ReasonAddr = NinlrDynamicAlloca; + return false; + } + if (HasIndirectBr) { + *ReasonAddr = NinlrIndirectBranch; + return false; + } + if (HasFrameEscape) { + *ReasonAddr = NinlrCallsLocalEscape; + return false; + } // If the caller is a recursive function then we don't want to inline // functions which allocate a lot of stack space because it would increase // the caller stack usage dramatically. if (IsCallerRecursive && - AllocatedSize > InlineConstants::TotalAllocaSizeRecursiveCaller) + AllocatedSize > InlineConstants::TotalAllocaSizeRecursiveCaller) { + *ReasonAddr = NinlrTooMuchStack; return false; + } break; } @@ -1391,11 +1457,17 @@ } } + if (SingleBB) { + YesReasonVector.push_back(InlrSingleBasicBlock); + } + // If this is a noduplicate call, we can still inline as long as // inlining this would cause the removal of the caller (so the instruction // is not actually duplicated, just moved). - if (!OnlyOneCallAndLocalLinkage && ContainsNoDuplicateCall) + if (!OnlyOneCallAndLocalLinkage && ContainsNoDuplicateCall) { + *ReasonAddr = NinlrDuplicateCall; return false; + } // We applied the maximum possible vector bonus at the beginning. Now, // subtract the excess bonus, if any, from the Threshold before @@ -1405,6 +1477,16 @@ else if (NumVectorInstructions <= NumInstructions / 2) Threshold -= (FiftyPercentVectorBonus - TenPercentVectorBonus); + if (VectorBonus > 0) { + YesReasonVector.push_back(InlrVectorBonus); + } + if (Cost < Threshold) { + *ReasonAddr = bestInlineReason(YesReasonVector, InlrProfitable); + } + else { + *ReasonAddr = bestInlineReason(NoReasonVector, NinlrNotProfitable); + } + return Cost < std::max(1, Threshold); } @@ -1464,64 +1546,84 @@ int llvm::getDefaultInlineThreshold() { return DefaultInlineThreshold; } +int llvm::getHintThreshold() { return HintThreshold; } + +int llvm::getOptSizeThreshold() { return OptSizeThreshold; } + +int llvm::getColdThreshold() { return ColdThreshold; } + InlineCost llvm::getInlineCost(CallSite CS, Function *Callee, int DefaultThreshold, TargetTransformInfo &CalleeTTI, AssumptionCacheTracker *ACT) { // Cannot inline indirect calls. - if (!Callee) - return llvm::InlineCost::getNever(); + if (!Callee) { + return llvm::InlineCost::getNever(NinlrIndirect); + } // Calls to functions with always-inline attributes should be inlined // whenever possible. if (CS.hasFnAttr(Attribute::AlwaysInline)) { - if (isInlineViable(*Callee)) - return llvm::InlineCost::getAlways(); - return llvm::InlineCost::getNever(); + InlineReason Reason = InlrNoReason; + if (isInlineViable(*Callee, Reason)) + return llvm::InlineCost::getAlways(InlrAlwaysInline); + assert(IsNotInlinedReason(Reason)); + return llvm::InlineCost::getNever(Reason); } // Never inline functions with conflicting attributes (unless callee has // always-inline attribute). if (!functionsHaveCompatibleAttributes(CS.getCaller(), Callee, CalleeTTI)) - return llvm::InlineCost::getNever(); + return llvm::InlineCost::getNever(NinlrMismatchedAttributes); // Don't inline this call if the caller has the optnone attribute. if (CS.getCaller()->hasFnAttribute(Attribute::OptimizeNone)) - return llvm::InlineCost::getNever(); + return llvm::InlineCost::getNever(NinlrOptNone); // Don't inline functions which can be interposed at link-time. Don't inline // functions marked noinline or call sites marked noinline. - // Note: inlining non-exact non-interposable fucntions is fine, since we know + // Note: inlining non-exact non-interposable functions is fine, since we know // we have *a* correct implementation of the source level function. - if (Callee->isInterposable() || - Callee->hasFnAttribute(Attribute::NoInline) || CS.isNoInline()) - return llvm::InlineCost::getNever(); + if (Callee->isInterposable()) + return llvm::InlineCost::getNever(NinlrInterposable); + if (Callee->hasFnAttribute(Attribute::NoInline)) + return llvm::InlineCost::getNever(NinlrNoinlineAttribute); + if (CS.isNoInline()) + return llvm::InlineCost::getNever(NinlrNoinlineCallsite); DEBUG(llvm::dbgs() << " Analyzing call of " << Callee->getName() << "...\n"); CallAnalyzer CA(CalleeTTI, ACT, *Callee, DefaultThreshold, CS); - bool ShouldInline = CA.analyzeCall(CS); + InlineReason Reason = InlrNoReason; + bool ShouldInline = CA.analyzeCall(CS, &Reason); + assert(Reason != InlrNoReason); DEBUG(CA.dump()); // Check if there was a reason to force inlining or no inlining. if (!ShouldInline && CA.getCost() < CA.getThreshold()) - return InlineCost::getNever(); + return InlineCost::getNever(Reason); if (ShouldInline && CA.getCost() >= CA.getThreshold()) - return InlineCost::getAlways(); + return InlineCost::getAlways(Reason); - return llvm::InlineCost::get(CA.getCost(), CA.getThreshold()); + return llvm::InlineCost::get(CA.getCost(), CA.getThreshold(), Reason); } -bool llvm::isInlineViable(Function &F) { +bool llvm::isInlineViable(Function &F, InlineReason& Reason) { bool ReturnsTwice = F.hasFnAttribute(Attribute::ReturnsTwice); for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) { // Disallow inlining of functions which contain indirect branches or // blockaddresses. - if (isa(BI->getTerminator()) || BI->hasAddressTaken()) + if (isa(BI->getTerminator())) { + Reason = NinlrIndirectBranch; return false; + } + if (BI->hasAddressTaken()) { + Reason = NinlrBlockAddress; + return false; + } for (auto &II : *BI) { CallSite CS(&II); @@ -1529,21 +1631,27 @@ continue; // Disallow recursive calls. - if (&F == CS.getCalledFunction()) + if (&F == CS.getCalledFunction()) { + Reason = NinlrRecursive; return false; + } // Disallow calls which expose returns-twice to a function not previously // attributed as such. if (!ReturnsTwice && CS.isCall() && - cast(CS.getInstruction())->canReturnTwice()) + cast(CS.getInstruction())->canReturnTwice()) { + Reason = NinlrReturnsTwice; return false; + } // Disallow inlining functions that call @llvm.localescape. Doing this // correctly would require major changes to the inliner. if (CS.getCalledFunction() && CS.getCalledFunction()->getIntrinsicID() == - llvm::Intrinsic::localescape) + llvm::Intrinsic::localescape) { + Reason = NinlrCallsLocalEscape; return false; + } } } Index: lib/Transforms/IPO/InlineAlways.cpp =================================================================== --- lib/Transforms/IPO/InlineAlways.cpp +++ lib/Transforms/IPO/InlineAlways.cpp @@ -28,6 +29,7 @@ #include "llvm/Transforms/IPO/InlinerPass.h" using namespace llvm; +using namespace InlineReportTypes; #define DEBUG_TYPE "inline" @@ -90,8 +92,9 @@ // Only inline direct calls to functions with always-inline attributes // that are viable for inlining. FIXME: We shouldn't even get here for // declarations. + InlineReason Reason; if (Callee && !Callee->isDeclaration() && - CS.hasFnAttr(Attribute::AlwaysInline) && isInlineViable(*Callee)) + CS.hasFnAttr(Attribute::AlwaysInline) && isInlineViable(*Callee, Reason)) return InlineCost::getAlways(); return InlineCost::getNever();