[InlineCost] Add cl::opt to allow full inline cost to be computed for debugging purposes.

[haicheng]

Summary

Currently, the inline cost model will bail once the inline cost exceeds the inline threshold in order to avoid unnecessary compile-time. However, when debugging I found it useful to compute the full cost, so I added this command line option to override the default behavior.

I wanted to see if others thought this might be useful. I also wanted to have someone more familiar with the inline cost model double check to make sure the patch is correct.

Chad

[haicheng]

lib/Analysis/InlineCost.cpp

1070 ↗

(On Diff #108131)

I think you need to skip this, too.

[mcrosier]

lib/Analysis/InlineCost.cpp

1070 ↗

(On Diff #108131)

I believe you're correct. Thanks, Haicheng.

[chandlerc]

Why abandon? FWIW, this does seem really useful. I'd also suggest wiring it up so that when optimization remarks are enabled, we do the extra compile time work to give that a detailed answer. (Or maybe set a *really high* threshold below which we give a reasonably exact answer...)

[mcrosier]

In D35850#829883, @chandlerc wrote:

Why abandon? FWIW, this does seem really useful. I'd also suggest wiring it up so that when optimization remarks are enabled, we do the extra compile time work to give that a detailed answer. (Or maybe set a *really high* threshold below which we give a reasonably exact answer...)

I just didn't think there was any interest, but if you think it might be useful, I'll revive the patch.

[mcrosier]

@haicheng has offered to take up this work!

[haicheng]

Take the work from Chad.

[haicheng]

Wire up with Optimization Remarks.

[eraman]

analyzeBlock bails out when inlining is not feasible due to things like recursive call, dynamic alloca etc. Arguably it doesn't make sense to compute the full inline cost even with this new option (and that's the behavior with this patch). In that case, especially with the ORE hookup, there should be some indication that the cost is not fully computed because the callee can not get inlined even if cost < threshold.

[haicheng]

In D35850#837071, @eraman wrote:

analyzeBlock bails out when inlining is not feasible due to things like recursive call, dynamic alloca etc. Arguably it doesn't make sense to compute the full inline cost even with this new option (and that's the behavior with this patch). In that case, especially with the ORE hookup, there should be some indication that the cost is not fully computed because the callee can not get inlined even if cost < threshold.

With option -inline-cost-full enabled, the output of optimization remarks is like below if anything like recursive call, dynamic alloca is found.

foz not inlined into bar because it should never be inlined (cost=never)

Pelease let me know how do you want it to be changed.

Haicheng

[haicheng]

Change the output of optimization remarks to something like below if anything like recursive call, dynamic alloca is found

foz is recursive and allocates too much stack space. Cost is not fully computed
foz not inlined into bar because it should never be inlined (cost=never)

Is this okay? Thank you.

[eraman]

In D35850#843955, @haicheng wrote:

Change the output of optimization remarks to something like below if anything like recursive call, dynamic alloca is found

foz is recursive and allocates too much stack space. Cost is not fully computed
foz not inlined into bar because it should never be inlined (cost=never)

Is this okay? Thank you.

Yes, that looks good. Even just a "Cost is not fully computed" is fine.

[mcrosier]

lib/Analysis/InlineCost.cpp

1366 ↗

(On Diff #111454)

unilinable -> uninlinable

[haicheng]

Fixed a typo found by Chad. Thank you.

[mcrosier]

LGTM.

llvm/trunk/include/llvm/Analysis/InlineCost.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_INLINECOST_H
 #define LLVM_ANALYSIS_INLINECOST_H
 
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CallGraphSCCPass.h"
+#include "llvm/Analysis/OptimizationDiagnosticInfo.h"
 #include <cassert>
 #include <climits>
 
 namespace llvm {
 class AssumptionCacheTracker;
 class BlockFrequencyInfo;
 class CallSite;
 class DataLayout;

 /// Note that a default threshold is passed into this function. This threshold
 /// could be modified based on callsite's properties and only costs below this
 /// new threshold are computed with any accuracy. The new threshold can be
 /// used to bound the computation necessary to determine whether the cost is
 /// sufficiently low to warrant inlining.
 ///
 /// Also note that calling this function *dynamically* computes the cost of
 /// inlining the callsite. It is an expensive, heavyweight call.
-InlineCost
-getInlineCost(CallSite CS, const InlineParams &Params,
-              TargetTransformInfo &CalleeTTI,
-              std::function<AssumptionCache &(Function &)> &GetAssumptionCache,
-              Optional<function_ref<BlockFrequencyInfo &(Function &)>> GetBFI,
-              ProfileSummaryInfo *PSI);
+InlineCost getInlineCost(
+    CallSite CS, const InlineParams &Params, TargetTransformInfo &CalleeTTI,
+    ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE = nullptr);
 
 /// \brief Get an InlineCost with the callee explicitly specified.
 /// This allows you to calculate the cost of inlining a function via a
 /// pointer. This behaves exactly as the version with no explicit callee
 /// parameter in all other respects.
 //
 InlineCost
 getInlineCost(CallSite CS, Function *Callee, const InlineParams &Params,
               TargetTransformInfo &CalleeTTI,
               std::function<AssumptionCache &(Function &)> &GetAssumptionCache,
               Optional<function_ref<BlockFrequencyInfo &(Function &)>> GetBFI,
-              ProfileSummaryInfo *PSI);
+              ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE);
 
 /// \brief Minimal filter to detect invalid constructs for inlining.
 bool isInlineViable(Function &Callee);
 }
 
 #endif

llvm/trunk/lib/Analysis/InlineCost.cpp

cl::desc("Maxmimum block frequency, expressed as a percentage of caller's "
              "profile information."));
 
 static cl::opt<int> HotCallSiteRelFreq(
     "hot-callsite-rel-freq", cl::Hidden, cl::init(60), cl::ZeroOrMore,
     cl::desc("Minimum block frequency, expressed as a multiple of caller's "
              "entry frequency, for a callsite to be hot in the absence of "
              "profile information."));
 
+static cl::opt<bool> ComputeFullInlineCost(
+    "inline-cost-full", cl::Hidden, cl::init(false),
+    cl::desc("Compute the full inline cost of a call site even when the cost "
+             "exceeds the threshold."));
+
 namespace {
 
 class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   typedef InstVisitor<CallAnalyzer, bool> Base;
   friend class InstVisitor<CallAnalyzer, bool>;
 
   /// The TargetTransformInfo available for this compilation.
   const TargetTransformInfo &TTI;
 
   /// Getter for the cache of @llvm.assume intrinsics.
   std::function<AssumptionCache &(Function &)> &GetAssumptionCache;
 
   /// Getter for BlockFrequencyInfo
   Optional<function_ref<BlockFrequencyInfo &(Function &)>> &GetBFI;
 
   /// Profile summary information.
   ProfileSummaryInfo *PSI;
 
   /// The called function.
   Function &F;
 
   // Cache the DataLayout since we use it a lot.
   const DataLayout &DL;
 
+  /// The OptimizationRemarkEmitter available for this compilation.
+  OptimizationRemarkEmitter *ORE;
+
   /// The candidate callsite being analyzed. Please do not use this to do
   /// analysis in the caller function; we want the inline cost query to be
   /// easily cacheable. Instead, use the cover function paramHasAttr.
   CallSite CandidateCS;
 
   /// Tunable parameters that control the analysis.
   const InlineParams &Params;
 
class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   bool visitCleanupReturnInst(CleanupReturnInst &RI);
   bool visitCatchReturnInst(CatchReturnInst &RI);
   bool visitUnreachableInst(UnreachableInst &I);
 
 public:
   CallAnalyzer(const TargetTransformInfo &TTI,
                std::function<AssumptionCache &(Function &)> &GetAssumptionCache,
                Optional<function_ref<BlockFrequencyInfo &(Function &)>> &GetBFI,
-               ProfileSummaryInfo *PSI, Function &Callee, CallSite CSArg,
-               const InlineParams &Params)
+               ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE,
+               Function &Callee, CallSite CSArg, const InlineParams &Params)
       : TTI(TTI), GetAssumptionCache(GetAssumptionCache), GetBFI(GetBFI),
-        PSI(PSI), F(Callee), DL(F.getParent()->getDataLayout()),
+        PSI(PSI), F(Callee), DL(F.getParent()->getDataLayout()), ORE(ORE),
         CandidateCS(CSArg), Params(Params), Threshold(Params.DefaultThreshold),
         Cost(0), IsCallerRecursive(false), IsRecursiveCall(false),
         ExposesReturnsTwice(false), HasDynamicAlloca(false),
         ContainsNoDuplicateCall(false), HasReturn(false), HasIndirectBr(false),
         HasFrameEscape(false), AllocatedSize(0), NumInstructions(0),
         NumVectorInstructions(0), VectorBonus(0), SingleBBBonus(0),
         NumConstantArgs(0), NumConstantOffsetPtrArgs(0), NumAllocaArgs(0),
         NumConstantPtrCmps(0), NumConstantPtrDiffs(0),
bool CallAnalyzer::visitCallSite(CallSite CS) {
 
   // If we have a constant that we are calling as a function, we can peer
   // through it and see the function target. This happens not infrequently
   // during devirtualization and so we want to give it a hefty bonus for
   // inlining, but cap that bonus in the event that inlining wouldn't pan
   // out. Pretend to inline the function, with a custom threshold.
   auto IndirectCallParams = Params;
   IndirectCallParams.DefaultThreshold = InlineConstants::IndirectCallThreshold;
-  CallAnalyzer CA(TTI, GetAssumptionCache, GetBFI, PSI, *F, CS,
+  CallAnalyzer CA(TTI, GetAssumptionCache, GetBFI, PSI, ORE, *F, CS,
                   IndirectCallParams);
   if (CA.analyzeCall(CS)) {
     // 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());
   }
 
   return Base::visitCallSite(CS);
bool CallAnalyzer::visitSwitchInst(SwitchInst &SI) {
   // Exit early for a large switch, assuming one case needs at least one
   // instruction.
   // FIXME: This is not true for a bit test, but ignore such case for now to
   // save compile-time.
   int64_t CostLowerBound =
       std::min((int64_t)CostUpperBound,
                (int64_t)SI.getNumCases() * InlineConstants::InstrCost + Cost);
 
-  if (CostLowerBound > Threshold) {
+  if (CostLowerBound > Threshold && !ComputeFullInlineCost) {
     Cost = CostLowerBound;
     return false;
   }
 
   unsigned JumpTableSize = 0;
   unsigned NumCaseCluster =
       TTI.getEstimatedNumberOfCaseClusters(SI, JumpTableSize);
 
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
     // all of the per-instruction logic. The visit tree returns true if we
     // consumed the instruction in any way, and false if the instruction's base
     // cost should count against inlining.
     if (Base::visit(&*I))
       ++NumInstructionsSimplified;
     else
       Cost += InlineConstants::InstrCost;
 
+    using namespace ore;
     // If the visit this instruction detected an uninlinable pattern, abort.
     if (IsRecursiveCall || ExposesReturnsTwice || HasDynamicAlloca ||
-        HasIndirectBr || HasFrameEscape)
+        HasIndirectBr || HasFrameEscape) {
+      if (ORE)
+        ORE->emit(OptimizationRemarkMissed(DEBUG_TYPE, "NeverInline",
+                                           CandidateCS.getInstruction())
+                  << NV("Callee", &F)
+                  << " has uninlinable pattern and cost is not fully computed");
       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) {
+      if (ORE)
+        ORE->emit(
+            OptimizationRemarkMissed(DEBUG_TYPE, "NeverInline",
+                                     CandidateCS.getInstruction())
+            << NV("Callee", &F)
+            << " is recursive and allocates too much stack space. Cost is "
+               "not fully computed");
       return false;
+    }
 
     // Check if we've past the maximum possible threshold so we don't spin in
     // huge basic blocks that will never inline.
-    if (Cost > Threshold)
+    if (Cost > Threshold && !ComputeFullInlineCost)
       return false;
   }
 
   return true;
 }
 
 /// \brief Compute the base pointer and cumulative constant offsets for V.
 ///
bool CallAnalyzer::analyzeCall(CallSite CS) {
   Cost -= getCallsiteCost(CS, DL);
 
   // If this function uses the coldcc calling convention, prefer not to inline
   // it.
   if (F.getCallingConv() == CallingConv::Cold)
     Cost += InlineConstants::ColdccPenalty;
 
   // Check if we're done. This can happen due to bonuses and penalties.
-  if (Cost > Threshold)
+  if (Cost > Threshold && !ComputeFullInlineCost)
     return false;
 
   if (F.empty())
     return true;
 
   Function *Caller = CS.getInstruction()->getParent()->getParent();
   // Check if the caller function is recursive itself.
   for (User *U : Caller->users()) {
typedef SetVector<BasicBlock *, SmallVector<BasicBlock *, 16>,
       BBSetVector;
   BBSetVector BBWorklist;
   BBWorklist.insert(&F.getEntryBlock());
   bool SingleBB = true;
   // Note that we *must not* cache the size, this loop grows the worklist.
   for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
     // Bail out the moment we cross the threshold. This means we'll under-count
     // the cost, but only when undercounting doesn't matter.
-    if (Cost > Threshold)
+    if (Cost > Threshold && !ComputeFullInlineCost)
       break;
 
     BasicBlock *BB = BBWorklist[Idx];
     if (BB->empty())
       continue;
 
     // Disallow inlining a blockaddress. A blockaddress only has defined
     // behavior for an indirect branch in the same function, and we do not
int llvm::getCallsiteCost(CallSite CS, const DataLayout &DL) {
   Cost += InlineConstants::InstrCost + InlineConstants::CallPenalty;
   return Cost;
 }
 
 InlineCost llvm::getInlineCost(
     CallSite CS, const InlineParams &Params, TargetTransformInfo &CalleeTTI,
     std::function<AssumptionCache &(Function &)> &GetAssumptionCache,
     Optional<function_ref<BlockFrequencyInfo &(Function &)>> GetBFI,
-    ProfileSummaryInfo *PSI) {
+    ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE) {
   return getInlineCost(CS, CS.getCalledFunction(), Params, CalleeTTI,
-                       GetAssumptionCache, GetBFI, PSI);
+                       GetAssumptionCache, GetBFI, PSI, ORE);
 }
 
 InlineCost llvm::getInlineCost(
     CallSite CS, Function *Callee, const InlineParams &Params,
     TargetTransformInfo &CalleeTTI,
     std::function<AssumptionCache &(Function &)> &GetAssumptionCache,
     Optional<function_ref<BlockFrequencyInfo &(Function &)>> GetBFI,
-    ProfileSummaryInfo *PSI) {
+    ProfileSummaryInfo *PSI, OptimizationRemarkEmitter *ORE) {
 
   // Cannot inline indirect calls.
   if (!Callee)
     return llvm::InlineCost::getNever();
 
   // Calls to functions with always-inline attributes should be inlined
   // whenever possible.
   if (CS.hasFnAttr(Attribute::AlwaysInline)) {
InlineCost llvm::getInlineCost(
   // 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 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 (ORE)
+    ComputeFullInlineCost = true;
+
   DEBUG(llvm::dbgs() << "      Analyzing call of " << Callee->getName()
                      << "... (caller:" << Caller->getName() << ")\n");
 
-  CallAnalyzer CA(CalleeTTI, GetAssumptionCache, GetBFI, PSI, *Callee, CS,
+  CallAnalyzer CA(CalleeTTI, GetAssumptionCache, GetBFI, PSI, ORE, *Callee, CS,
                   Params);
   bool ShouldInline = CA.analyzeCall(CS);
 
   DEBUG(CA.dump());
 
   // Check if there was a reason to force inlining or no inlining.
   if (!ShouldInline && CA.getCost() < CA.getThreshold())
     return InlineCost::getNever();

llvm/trunk/lib/Transforms/IPO/InlineSimple.cpp

explicit SimpleInliner(InlineParams Params)
     initializeSimpleInlinerPass(*PassRegistry::getPassRegistry());
   }
 
   static char ID; // Pass identification, replacement for typeid
 
   InlineCost getInlineCost(CallSite CS) override {
     Function *Callee = CS.getCalledFunction();
     TargetTransformInfo &TTI = TTIWP->getTTI(*Callee);
+    OptimizationRemarkEmitter ORE(CS.getCaller());
     std::function<AssumptionCache &(Function &)> GetAssumptionCache =
         [&](Function &F) -> AssumptionCache & {
       return ACT->getAssumptionCache(F);
     };
     return llvm::getInlineCost(CS, Params, TTI, GetAssumptionCache,
-                               /*GetBFI=*/None, PSI);
+                               /*GetBFI=*/None, PSI, &ORE);
   }
 
   bool runOnSCC(CallGraphSCC &SCC) override;
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
 private:
   TargetTransformInfoWrapperPass *TTIWP;
 

llvm/trunk/lib/Transforms/IPO/Inliner.cpp

for (int i = 0; i < (int)Calls.size(); ++i) {
     // we're going to mutate this particular function we want to make sure the
     // proxy is in place to forward any invalidation events. We can use the
     // manager we get here for looking up results for functions other than this
     // node however because those functions aren't going to be mutated by this
     // pass.
     FunctionAnalysisManager &FAM =
         AM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG)
             .getManager();
+
+    // Get the remarks emission analysis for the caller.
+    auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
+
     std::function<AssumptionCache &(Function &)> GetAssumptionCache =
         [&](Function &F) -> AssumptionCache & {
       return FAM.getResult<AssumptionAnalysis>(F);
     };
     auto GetBFI = [&](Function &F) -> BlockFrequencyInfo & {
       return FAM.getResult<BlockFrequencyAnalysis>(F);
     };
 
     auto GetInlineCost = [&](CallSite CS) {
       Function &Callee = *CS.getCalledFunction();
       auto &CalleeTTI = FAM.getResult<TargetIRAnalysis>(Callee);
       return getInlineCost(CS, Params, CalleeTTI, GetAssumptionCache, {GetBFI},
-                           PSI);
+                           PSI, &ORE);
     };
 
-    // Get the remarks emission analysis for the caller.
-    auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
-
     // Now process as many calls as we have within this caller in the sequnece.
     // We bail out as soon as the caller has to change so we can update the
     // call graph and prepare the context of that new caller.
     bool DidInline = false;
     for (; i < (int)Calls.size() && Calls[i].first.getCaller() == &F; ++i) {
       int InlineHistoryID;
       CallSite CS;
       std::tie(CS, InlineHistoryID) = Calls[i];

llvm/trunk/lib/Transforms/IPO/PartialInlining.cpp

bool PartialInlinerImpl::shouldPartialInline(
 
   Instruction *Call = CS.getInstruction();
   Function *Callee = CS.getCalledFunction();
   assert(Callee == Cloner.ClonedFunc);
 
   Function *Caller = CS.getCaller();
   auto &CalleeTTI = (*GetTTI)(*Callee);
   InlineCost IC = getInlineCost(CS, getInlineParams(), CalleeTTI,
-                                *GetAssumptionCache, GetBFI, PSI);
+                                *GetAssumptionCache, GetBFI, PSI, &ORE);
 
   if (IC.isAlways()) {
     ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "AlwaysInline", Call)
              << NV("Callee", Cloner.OrigFunc)
              << " should always be fully inlined, not partially");
     return false;
   }