[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

483

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?

674

it's auto*, right?

725

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.

480

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

483

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

626

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

670

Check function entry count first for both caller and callee.

670

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

681

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

684

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

[kazu]

Incorporated feedback.

[kazu]

PTAL. Thanks!

llvm/lib/Analysis/InlineCost.cpp

480

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

483

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.

670

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.

725

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

480

In comment, it should be Cost - CostAtBBStart

628

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.

630

should assert that it has value

686

checker CallerEntry count earlier than this check can be removed.

[kazu]

Incorporated the feedback.

[kazu]

PTAL. Thanks!

llvm/lib/Analysis/InlineCost.cpp

628

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

690

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

742

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("Inline savings multiplier"));
+
+static cl::opt<int> InlineSizeAllowance("inline-size-allowance", cl::Hidden,
+                                        cl::init(100), cl::ZeroOrMore,
+                                        cl::desc("Inline size allowance"));
+
 // 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.
+  int CostAtBBStart = 0;
+
+  // The cost of cold basic blocks.
+  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 {
+    // Keep track of the cost of 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 *BFI = GetBFI ? &(GetBFI(F)) : nullptr;
+    if (!BFI)
+      return None;
+
+    auto CallerBB = CandidateCall.getParent();
+    BlockFrequencyInfo *CallerBFI =
+        GetBFI ? &(GetBFI(*(CallerBB->getParent()))) : nullptr;
+    if (!CallerBFI)
+      return None;
+
+    auto CallerProfileCount = CallerBFI->getBlockProfileCount(CallerBB);
+    if (!CallerProfileCount.hasValue())
+      return None;
+
+    for (auto &BB : F) {
+      auto ProfileCount = BFI->getBlockProfileCount(&BB);
+      if (!ProfileCount.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;
+
+    uint64_t WeightedSavings = 0;
+    for (auto &BB : F) {
+      uint64_t CurrentSavings = 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 = BFI->getBlockProfileCount(&BB);
+      assert(ProfileCount.hasValue());
+      WeightedSavings += ProfileCount.getValue() * CurrentSavings;
+    }
+
+    // Compute the weighted savings per call.
+    auto EntryProfileCount = BFI->getBlockProfileCount(&(F.getEntryBlock()));
+    assert(EntryProfileCount.hasValue());
+    if (EntryProfileCount.getValue())
+      WeightedSavings = ((WeightedSavings + EntryProfileCount.getValue() / 2) /
+                         EntryProfileCount.getValue());
+    else
+      WeightedSavings = 0;
+
+    // Compute the total savings for the given call.
+    WeightedSavings += getCallsiteCost(this->CandidateCall, DL);
+    WeightedSavings *= 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:
+    //
+    //  WeightedSavings      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.
+    auto LHS = WeightedSavings * InlineSavingsMultiplier;
+    auto RHS = Size * PSI->getOrCompHotCountThreshold();
+    return LHS >= 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.