[InlineCost] Make cost-benefit decision explicit

[wenlei]

Summary

With cost-benefit analysis for inlining, we bypass the cost-threshold by returning inline result from call analyzer early.

However the cost and threshold are still available from call analyzer, and when cost is actually higher than threshold, we incorrect set the reason.

The change makes the decision from cost-benefit analysis explicit. It's mostly NFC, except that it allows the priority-based sample loader inliner used by CSSPGO to use cost-benefit heuristic.

[davidxl]

llvm/lib/Analysis/InlineCost.cpp

2635

Should this be folded into line 2622?

[wenlei]

llvm/lib/Analysis/InlineCost.cpp

2635

We wanted any positive cost-benefit decision to be distinguishable from a regular cost-threshold decision. This is because sample loader inlining looks at cost, and compare against its own threshold (SampleProfileLoader::shouldInlineCandidate). But we want cost-benefit decision to take precedence there too. I can give the three flat if some structure..

Perhaps it'd be good to make negative cost-benefit decision distinguishable too, by using never. An alternative is to add a field in InlineCost indicating a decision is made through cost-benefit analysis.

[davidxl]

llvm/lib/Analysis/InlineCost.cpp

2635

what I meant is re-organize your change a little:

if (ShouldInline.isSuccess()) {

if (CA.wasDecidedByCostBenefit() {
 ...
} 
if (CA.getCost() >= CA.getThreshold() ) {
}

}

[wenlei]

llvm/lib/Analysis/InlineCost.cpp

2635

How about this above the existing checks. On 2nd thought, I think it makes sense to make negative cost-benefit decision explicit too.

// Always make cost benefit based decision explicit.
// We use always/never here since threshold is not meaningful,
// as it's not what drives cost-benefit analysis.
if (CA.wasDecidedByCostBenefit()) {
  if (ShouldInline.isSuccess())
    return InlineCost::getAlways("benefit over cost");
  else
    return InlineCost::getNever("cost over benefit");
}

[davidxl]

llvm/lib/Analysis/InlineCost.cpp

2635

Sounds good.

[wenlei]

Address David's feedback, also make negative decision explicit.

[davidxl]

lgtm

[wenlei]

Rebase, update test.

llvm/lib/Analysis/InlineCost.cpp

class InlineCostCallAnalyzer final : public CallAnalyzer {
   // the end of analyzing each basic block, "Cost - CostAtBBStart" 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;
 
+  // Whether inlining is decided by cost-benefit analysis.
+  bool DecidedByCostBenefit = false;
+
   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.
InlineResult finalizeAnalysis() override {
     // 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 (auto Result = costBenefitAnalysis()) {
+      DecidedByCostBenefit = true;
       if (Result.getValue())
         return InlineResult::success();
       else
         return InlineResult::failure("Cost over threshold.");
     }
 
     if (IgnoreThreshold || Cost < std::max(1, Threshold))
       return InlineResult::success();
Optional<InstructionCostDetail> getCostDetails(const Instruction *I) {
     if (InstructionCostDetailMap.find(I) != InstructionCostDetailMap.end())
       return InstructionCostDetailMap[I];
     return None;
   }
 
   virtual ~InlineCostCallAnalyzer() {}
   int getThreshold() { return Threshold; }
   int getCost() { return Cost; }
+  bool wasDecidedByCostBenefit() { return DecidedByCostBenefit; }
 };
 } // namespace
 
 /// Test whether the given value is an Alloca-derived function argument.
 bool CallAnalyzer::isAllocaDerivedArg(Value *V) {
   return SROAArgValues.count(V);
 }
 
LLVM_DEBUG(llvm::dbgs() << "      Analyzing call of " << Callee->getName()
                           << ")\n");
 
   InlineCostCallAnalyzer CA(*Callee, Call, Params, CalleeTTI,
                             GetAssumptionCache, GetBFI, PSI, ORE);
   InlineResult ShouldInline = CA.analyze();
 
   LLVM_DEBUG(CA.dump());
 
+  // Always make cost benefit based decision explicit.
+  // We use always/never here since threshold is not meaningful,
+  // as it's not what drives cost-benefit analysis.
+  if (CA.wasDecidedByCostBenefit()) {
+    if (ShouldInline.isSuccess())
+      return InlineCost::getAlways("benefit over cost");
+    else
+      return InlineCost::getNever("cost over benefit");
+  }
+
   // Check if there was a reason to force inlining or no inlining.
   if (!ShouldInline.isSuccess() && CA.getCost() < CA.getThreshold())
     return InlineCost::getNever(ShouldInline.getFailureReason());
   if (ShouldInline.isSuccess() && CA.getCost() >= CA.getThreshold())
     return InlineCost::getAlways("empty function");
 
   return llvm::InlineCost::get(CA.getCost(), CA.getThreshold());
 }
 
 InlineResult llvm::isInlineViable(Function &F) {

llvm/test/Other/optimization-remarks-auto.ll

 ;; This test verifies 'auto' hotness threshold when profile summary is available.
 ;;
 ;; new PM
 ; RUN: rm -f %t.yaml %t.hot.yaml
 ; RUN: opt < %s --disable-output --enable-new-pm \
 ; RUN: --passes='inline' \
 ; RUN: --pass-remarks-output=%t.yaml --pass-remarks-filter='inline' \
 ; RUN: --pass-remarks-with-hotness
 ; RUN: FileCheck %s -check-prefix=YAML-PASS < %t.yaml
 ; RUN: FileCheck %s -check-prefix=YAML-MISS < %t.yaml
 
 ;; test 'auto' threshold
-; RUN: opt < %s --disable-output --enable-new-pm \
+; RUN: opt < %s --disable-output --enable-new-pm --inline-enable-cost-benefit-analysis=0 \
 ; RUN: --passes='module(print-profile-summary,cgscc(inline))' \
 ; RUN: --pass-remarks-output=%t.hot.yaml --pass-remarks-filter='inline' \
 ; RUN: --pass-remarks-with-hotness --pass-remarks-hotness-threshold=auto 2>&1 | FileCheck %s
 ; RUN: FileCheck %s -check-prefix=YAML-PASS < %t.hot.yaml
 ; RUN: not FileCheck %s -check-prefix=YAML-MISS < %t.hot.yaml
 
-; RUN: opt < %s --disable-output --enable-new-pm \
+; RUN: opt < %s --disable-output --enable-new-pm --inline-enable-cost-benefit-analysis=0  \
 ; RUN: --passes='module(print-profile-summary,cgscc(inline))' \
 ; RUN: --pass-remarks=inline --pass-remarks-missed=inline --pass-remarks-analysis=inline \
 ; RUN: --pass-remarks-with-hotness --pass-remarks-hotness-threshold=auto 2>&1 | FileCheck %s -check-prefix=CHECK-RPASS
 
 ; YAML-PASS:      --- !Passed
 ; YAML-PASS-NEXT: Pass:            inline
 ; YAML-PASS-NEXT: Name:            Inlined
 ; YAML-PASS-NEXT: Function:        caller1

 !7 = !{!"MaxFunctionCount", i64 1000}
 !8 = !{!"NumCounts", i64 3}
 !9 = !{!"NumFunctions", i64 3}
 !10 = !{!"DetailedSummary", !11}
 !11 = !{!12, !13, !14}
 !12 = !{i32 10000, i64 100, i32 1}
 !13 = !{i32 999000, i64 100, i32 1}
 !14 = !{i32 999999, i64 1, i32 2}
-