[InlineCost] Implement cost-benefit-based inliner

[kazu]

Summary

This patch adds an alternative cost metric for the inliner to take
into account both the cost (i.e. size) and cycle count savings into
account.

Without this patch, we decide to inline a given call site if the size
of inlining the call site is below the threshold that is computed
according to the hotness of the call site.

This patch adds a new cost metric, turned off by default, to take over
the handling of hot call sites. Specifically, with the new cost
metric, we decide to inline a given call site if the ratio of cycle
savings to size exceeds a threshold. The cycle savings are computed
from call site costs, parameter propagation, folded conditional
branches, etc, all weighted by their respective profile counts. The
size is primarily the callee size, but we subtract call site costs and
the size of basic blocks that are never executed.

The new cost metric implicitly takes advantage of the machine function
splitter recently introduced by Snehasish Kumar, which dramatically
reduces the cost of duplicating (e.g. inlining) cold basic blocks by
placing cold basic blocks of hot functions in the .text.unlikely
section.

We evaluated the new cost metric on clang bootstrap and SPECInt 2017.

For clang bootstrap, we observe 0.69% runtime improvement.

For SPECInt we report the change in IntRate the C/C++ benchmarks. All
benchmarks apart from perlbench and omnetpp improve, on average by
0.21% with the max for mcf at 1.96%.

Benchmark % Change
500.perlbench_r -0.45
502.gcc_r 0.13
505.mcf_r 1.96
520.omnetpp_r -0.28
523.xalancbmk_r 0.49
525.x264_r 0.00
531.deepsjeng_r 0.00
541.leela_r 0.35
557.xz_r 0.21

[mtrofin]

llvm/lib/Analysis/InlineCost.cpp

484

can size be negative? Should it be int64_t?

Also, is it a size, or it's a cost - judging from its usage, probably the latter. Should it be ColdSizeCost?

680

it's auto*, right?

731

for really large profile counts (e.g. worker thread that blocks, waiting for work) this may overflow. Do we care?

[davidxl]

llvm/lib/Analysis/InlineCost.cpp

81

Make the documentation string more detailed.

481

To differentiate existing (static) cost which models size, perhaps name it 'weightedCostAtBBStart'? or 'DynamicCostAtBBStart'?

484

The naming needs to be consistent. Is it computing static size or weighted cost?

630

If function entry has no count, early skip -- to avoid compile time impact to nonPGO build.

676

Check function entry count first for both caller and callee.

676

Is 'F' callee? if so, name BFI CalleeBFI .

687

if caller entry has count, this should assert to be true.

690

No need for this loop if the entry count is checked at beginning.

[kazu]

Incorporated feedback.

[kazu]

PTAL. Thanks!

llvm/lib/Analysis/InlineCost.cpp

481

This is part of static size computation. I've expanded the comments.

484

I'm computing the static size here. CostAtBBStart is just a copy of Cost at the beginning of the basic block being processed so that we can compute the size of the the basic block in case it's cold.

Since I'm just copying Cost, I'd like to use the same type as Cost.

676

I've renamed BFI to CalleeBFI.

I've moved up the entry count for Callee.

For the caller, do I need to check its entry count? All I need is the profile count at the call site. In any event, I've moved up the code to obtain the profile count at the call site.

731

I've switched to 128-bit APInt. I've put justification for the bit size as a comment for CycleSavings.

[davidxl]

llvm/lib/Analysis/InlineCost.cpp

481

In comment, it should be Cost - CostAtBBStart

632

Are these guards needed? It is already checked in costBenefitAnalysis. Perhaps move the checking in a common place and set it to boolean variable: costBenefitAnalysisEnabled and the value of the variable can be checked here.

634

should assert that it has value

692

checker CallerEntry count earlier than this check can be removed.

[kazu]

Incorporated the feedback.

[kazu]

PTAL. Thanks!

llvm/lib/Analysis/InlineCost.cpp

632

I've created a function called isCostBenefitAnalysisEnabled.

[kazu]

Friendly ping. Thanks!

[mtrofin]

lgtm, but see if @davidxl has any additional comments.

[davidxl]

I suggest also dumping some opt remarks under --pass-remarks-analysis. This also allows you to write test cases to cover various types of savings.

llvm/lib/Analysis/InlineCost.cpp

696

Use interface Function::getEntryCount or Function::hasProfileData instead.

748

how about load & store instructions that can be SROAed?

[aemerson]

FYI I left a comment on https://reviews.llvm.org/D98213 about why I think this feature should not have been enabled.

llvm/lib/Analysis/InlineCost.cpp

static cl::opt<int> HintThreshold(
     "inlinehint-threshold", cl::Hidden, cl::init(325), cl::ZeroOrMore,
     cl::desc("Threshold for inlining functions with inline hint"));
 
 static cl::opt<int>
     ColdCallSiteThreshold("inline-cold-callsite-threshold", cl::Hidden,
                           cl::init(45), cl::ZeroOrMore,
                           cl::desc("Threshold for inlining cold callsites"));
 
+static cl::opt<bool> InlineEnableCostBenefitAnalysis(
+    "inline-enable-cost-benefit-analysis", cl::Hidden, cl::init(true),
+    cl::desc("Enable the cost-benefit analysis for the inliner"));
+
+static cl::opt<int> InlineSavingsMultiplier(
+    "inline-savings-multiplier", cl::Hidden, cl::init(8), cl::ZeroOrMore,
+    cl::desc("Multiplier to multiply cycle savings by during inlining"));
+
+static cl::opt<int>
+    InlineSizeAllowance("inline-size-allowance", cl::Hidden, cl::init(100),
+                        cl::ZeroOrMore,
+                        cl::desc("The maximum size of a callee that get's "
+                                 "inlined without sufficient cycle savings"));
+
 // We introduce this threshold to help performance of instrumentation based
 // PGO before we actually hook up inliner with analysis passes such as BPI and
 // BFI.
 static cl::opt<int> ColdThreshold(
     "inlinecold-threshold", cl::Hidden, cl::init(45), cl::ZeroOrMore,
     cl::desc("Threshold for inlining functions with cold attribute"));
 
 static cl::opt<int>
protected:
   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.
   CallBase &CandidateCall;
 
   /// Extension points for handling callsite features.
+  // Called before a basic block was analyzed.
+  virtual void onBlockStart(const BasicBlock *BB) {}
+
   /// Called after a basic block was analyzed.
   virtual void onBlockAnalyzed(const BasicBlock *BB) {}
 
   /// Called before an instruction was analyzed
   virtual void onInstructionAnalysisStart(const Instruction *I) {}
 
   /// Called after an instruction was analyzed
   virtual void onInstructionAnalysisFinish(const Instruction *I) {}
class InlineCostCallAnalyzer final : public CallAnalyzer {
   const bool IgnoreThreshold;
 
   /// Inlining cost measured in abstract units, accounts for all the
   /// instructions expected to be executed for a given function invocation.
   /// Instructions that are statically proven to be dead based on call-site
   /// arguments are not counted here.
   int Cost = 0;
 
+  // The cumulative cost at the beginning of the basic block being analyzed.  At
+  // the end of analyzing each basic block, "CostAtBBStart - Cost" represents
+  // the size of that basic block.
+  int CostAtBBStart = 0;
+
+  // The static size of live but cold basic blocks.  This is "static" in the
+  // sense that it's not weighted by profile counts at all.
+  int ColdSize = 0;
+
   bool SingleBB = true;
 
   unsigned SROACostSavings = 0;
   unsigned SROACostSavingsLost = 0;
 
   /// The mapping of caller Alloca values to their accumulated cost savings. If
   /// we have to disable SROA for one of the allocas, this tells us how much
   /// cost must be added.
class InlineCostCallAnalyzer final : public CallAnalyzer {
   void onAggregateSROAUse(AllocaInst *SROAArg) override {
     auto CostIt = SROAArgCosts.find(SROAArg);
     assert(CostIt != SROAArgCosts.end() &&
            "expected this argument to have a cost");
     CostIt->second += InlineConstants::InstrCost;
     SROACostSavings += InlineConstants::InstrCost;
   }
 
+  void onBlockStart(const BasicBlock *BB) override { CostAtBBStart = Cost; }
+
   void onBlockAnalyzed(const BasicBlock *BB) override {
+    if (PSI && PSI->hasProfileSummary()) {
+      // Keep track of the static size of live but cold basic blocks.  For now,
+      // we define a cold basic block to be one that's never executed.
+      if (BlockFrequencyInfo *BFI = GetBFI ? &(GetBFI(F)) : nullptr) {
+        auto ProfileCount = BFI->getBlockProfileCount(BB);
+        if (ProfileCount.hasValue() && ProfileCount.getValue() == 0)
+          ColdSize += Cost - CostAtBBStart;
+      }
+    }
+
     auto *TI = BB->getTerminator();
     // If we had any successors at this point, than post-inlining is likely to
     // have them as well. Note that we assume any basic blocks which existed
     // due to branches or switches which folded above will also fold after
     // inlining.
     if (SingleBB && TI->getNumSuccessors() > 1) {
       // Take off the bonus we applied to the threshold.
       Threshold -= SingleBBBonus;
void onInstructionAnalysisFinish(const Instruction *I) override {
     // This function is called to find new values of cost and threshold after
     // the instruction has been assessed.
     if (!PrintInstructionComments)
       return;
     InstructionCostDetailMap[I].CostAfter = Cost;
     InstructionCostDetailMap[I].ThresholdAfter = Threshold;
   }
 
+  // Determine whether we should inline the given call site, taking into account
+  // both the size cost and the cycle savings.  Return None if we don't have
+  // suficient profiling information to determine.
+  Optional<bool> costBenefitAnalysis() {
+    if (!PSI || !PSI->hasProfileSummary())
+      return None;
+
+    BlockFrequencyInfo *CalleeBFI = GetBFI ? &(GetBFI(F)) : nullptr;
+    if (!CalleeBFI)
+      return None;
+
+    auto *CallerBB = CandidateCall.getParent();
+    BlockFrequencyInfo *CallerBFI =
+        GetBFI ? &(GetBFI(*(CallerBB->getParent()))) : nullptr;
+    if (!CallerBFI)
+      return None;
+
+    auto EntryProfileCount =
+        CalleeBFI->getBlockProfileCount(&(F.getEntryBlock()));
+    if (!EntryProfileCount.hasValue())
+      return None;
+
+    auto CallerProfileCount = CallerBFI->getBlockProfileCount(CallerBB);
+    if (!CallerProfileCount.hasValue())
+      return None;
+
+    // buildInlinerPipeline in the pass builder sets HotCallSiteThreshold to 0
+    // for the prelink phase of the AutoFDO + ThinLTO build.  Honor the logic by
+    // falling back to the cost-based metric.
+    // TODO: Improve this hacky condition.
+    if (Threshold == 0)
+      return None;
+
+    // For now, limit to hot call site.
+    if (!PSI->isHotCallSite(CandidateCall, CallerBFI))
+      return None;
+
+    // The cycle savings expressed as the sum of InlineConstants::InstrCost
+    // multiplied by the estimated dynamic count of each instruction we can
+    // avoid.  Savings come from the call site cost, such as argument setup and
+    // the call instruction, as well as the instructions that are folded.
+    //
+    // We use 128-bit APInt here to avoid potential overflow.  This variable
+    // should stay well below 10^^24 (or 2^^80) in practice.  This "worst" case
+    // assumes that we can avoid or fold a billion instructions, each with a
+    // profile count of 10^^15 -- roughly the number of cycles for a 24-hour
+    // period on a 4GHz machine.
+    APInt CycleSavings(128, 0);
+
+    for (auto &BB : F) {
+      APInt CurrentSavings(128, 0);
+      for (auto &I : BB) {
+        if (BranchInst *BI = dyn_cast<BranchInst>(&I)) {
+          // Count a conditional branch as savings if it becomes unconditional.
+          if (BI->isConditional() &&
+              dyn_cast_or_null<ConstantInt>(
+                  SimplifiedValues.lookup(BI->getCondition()))) {
+            CurrentSavings += InlineConstants::InstrCost;
+          }
+        } else if (Value *V = dyn_cast<Value>(&I)) {
+          // Count an instruction as savings if we can fold it.
+          if (SimplifiedValues.count(V)) {
+            CurrentSavings += InlineConstants::InstrCost;
+          }
+        }
+        // TODO: Consider other forms of savings like switch statements,
+        // indirect calls becoming direct, SROACostSavings, LoadEliminationCost,
+        // etc.
+      }
+
+      auto ProfileCount = CalleeBFI->getBlockProfileCount(&BB);
+      assert(ProfileCount.hasValue());
+      CurrentSavings *= ProfileCount.getValue();
+      CycleSavings += CurrentSavings;
+    }
+
+    // Compute the weighted savings per call.
+    auto EntryCount = EntryProfileCount.getValue();
+    CycleSavings += EntryCount / 2;
+    CycleSavings = CycleSavings.udiv(EntryCount);
+
+    // Compute the total savings for the given call.
+    CycleSavings += getCallsiteCost(this->CandidateCall, DL);
+    CycleSavings *= CallerProfileCount.getValue();
+
+    // Remove the cost of the cold basic blocks.
+    int Size = Cost - ColdSize;
+
+    // Allow tiny callees to be inlined regardless of whether they meet the
+    // savings threshold.
+    Size = Size > InlineSizeAllowance ? Size - InlineSizeAllowance : 1;
+
+    // Return true if the savings justify the cost of inlining.  Specifically,
+    // we evaluate the following inequality:
+    //
+    //  CycleSavings      PSI->getOrCompHotCountThreshold()
+    // -------------- >= -----------------------------------
+    //       Size              InlineSavingsMultiplier
+    //
+    // Note that the left hand side is specific to a call site.  The right hand
+    // side is a constant for the entire executable.
+    APInt LHS = CycleSavings;
+    LHS *= InlineSavingsMultiplier;
+    APInt RHS(128, PSI->getOrCompHotCountThreshold());
+    RHS *= Size;
+    return LHS.uge(RHS);
+  }
+
   InlineResult finalizeAnalysis() override {
     // Loops generally act a lot like calls in that they act like barriers to
     // movement, require a certain amount of setup, etc. So when optimising for
     // size, we penalise any call sites that perform loops. We do this after all
     // other costs here, so will likely only be dealing with relatively small
     // functions (and hence DT and LI will hopefully be cheap).
     auto *Caller = CandidateCall.getFunction();
     if (Caller->hasMinSize()) {
InlineResult finalizeAnalysis() override {
     // We applied the maximum possible vector bonus at the beginning. Now,
     // subtract the excess bonus, if any, from the Threshold before
     // comparing against Cost.
     if (NumVectorInstructions <= NumInstructions / 10)
       Threshold -= VectorBonus;
     else if (NumVectorInstructions <= NumInstructions / 2)
       Threshold -= VectorBonus / 2;
 
+    if (InlineEnableCostBenefitAnalysis) {
+      auto CostBenefitAnalysisResult = costBenefitAnalysis();
+      if (CostBenefitAnalysisResult.hasValue()) {
+        if (CostBenefitAnalysisResult.getValue())
+          return InlineResult::success();
+        else
+          return InlineResult::failure("Cost over threshold.");
+      }
+    }
+
     if (IgnoreThreshold || Cost < std::max(1, Threshold))
       return InlineResult::success();
     return InlineResult::failure("Cost over threshold.");
   }
   bool shouldStop() override {
     // Bail out the moment we cross the threshold. This means we'll under-count
     // the cost, but only when undercounting doesn't matter.
     return !IgnoreThreshold && Cost >= Threshold && !ComputeFullInlineCost;
InlineResult CallAnalyzer::analyze() {
   for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
     if (shouldStop())
       break;
 
     BasicBlock *BB = BBWorklist[Idx];
     if (BB->empty())
       continue;
 
+    onBlockStart(BB);
+
     // Disallow inlining a blockaddress with uses other than strictly callbr.
     // A blockaddress only has defined behavior for an indirect branch in the
     // same function, and we do not currently support inlining indirect
     // branches.  But, the inliner may not 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.
     // FIXME: pr/39560: continue relaxing this overt restriction.