[NFC][Inliner] Introduce another multiplier for cost benefit analysis and make multipliers overriddable in TargetTransformInfo.

[mingmingl]

Summary

• The motivation is to expose tunable knobs to control the aggressiveness of inlines for different backend (e.g., machines with different icache size, and workload with different icache/itlb PMU counters). Tuning inline aggressiveness shows a small (~+0.3%) but stable improvement on workload/hardware that is more frontend bound.
• Both multipliers could be overridden from command line.

[mingmingl]

Update patch to have per-target parameters. Tests WIP

[kazu]

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

72

IIUC, with this patch, we stop honoring the command line option -inline-savings-multiplier. Is there any way you could retain the ability to specify the multiplier as a command line option so that we can easily experiment with different values without rebuilding the compiler? You could do something like:

if (InlineSavingsMultiplier.getNumOccurrences()) {
  // Honor the option.
  ...
} else {
  // Do whatever architecture-specific things we need to do.
  ...
}

llvm/lib/Analysis/InlineCost.cpp

947–951

IIUC, we are returning false if the cost-benefit ratio is below some threshold. Could you somehow mention that we are comparing the cost-benefit ratio against some threshold as a comment?

// Do not inline if the savings does not justify the cost of inlining.                                                  
// Specifically, we evaluate the following inequality:                                                                  
//                                                                                                                      
//  CycleSavings                PSI->getOrCompHotCountThreshold()                                                       
// -------------- <= --------------------------------------------------------                                           
//       Size        TTI.getInliningCostBenefitAnalysisProfitableMultiplier()

If you come with some concise language instead of nearly repeating the entire comment block, that's even better.

[mingmingl]

Revive this NFC patch to expose tunable knobs for workloads/hardwares that could be more frontend bound.

Address feedback.

[mingmingl]

Let me know if you'd prefer to review this on Github PR or use Phabricator. I'm fine with both.

[kazu]

llvm/lib/Analysis/InlineCost.cpp

94

I am the one that suggested:

if (InlineSavingsMultiplier.getNumOccurrences()) {
  // Honor the option.
  ...
} else {
  // Do whatever architecture-specific things we need to do.
  ...
}

below. That said, with this approach, we do not use the default value of InlineSavingsMultiplier at all. That is, changing the default value at the source code level (as opposed to the command-line level) has no effect. This is very confusing.

I am not sure if there is a better way to juggle three things -- the compiler-wide default, the architecture-specific default, and the command-line override. May I suggest a comment like this?

// We honor this option only when it is explicitly specified.
// The default value below isn't used at all.  If you wish to change it, update
// TargetTransformInfoImplBase::getInliningCostBenefitAnalysisSavingsMultiplier.
static cl::opt<int> InlineSavingsMultiplier(

98

Likewise, may I suggest a comment like this?

// We honor this option only when it is explicitly specified.
// The default value below isn't used at all.  If you wish to change it, update
// TargetTransformInfoImplBase::getInliningCostBenefitAnalysisProfitableMultiplier.

935–943

IIUC, you want to return true if the ratio of the cycle savings to the size is really high and false if it's really low. If the ratio falls somewhere in the middle, then you want to fall back to the cost-based analysis. If you are making this change, I would like to make this picture clear, especially given that it's not easy to read the code that tries to avoid divisions.

May I suggest replacing the comment above with something like this?

// Let R be the ratio of CycleSavings to Size.  We accept the inlining
// opportunity if R is really high and reject if R is really low.  If R is
// somewhere in the middle, we fall back to the cost-based analysis.
//
// Specifically, we accept the inlining opportunity if:
//
//             PSI->getOrCompHotCountThreshold()
// R > -------------------------------------------------
//     getInliningCostBenefitAnalysisSavingsMultiplier()
//
// and reject the inlining opportunity if:
//
//                PSI->getOrCompHotCountThreshold()
// R <= ----------------------------------------------------
//      getInliningCostBenefitAnalysisProfitableMultiplier()
//
// Otherwise, we fall back to the cost-based analysis.

Sure, we would be repeating comments like "Otherwise, we fall back to" below, but IMHO it's much more important to get the high-level idea across.

955

Remove this empty inline for consistency with the block above.

959

// Otherwise, fall back to the cost-based analysis.

• Use "fall back" (with a space in between) as a verb.
• We are falling back to the specific analysis, so insert "the".
• "Cost-benefit analysis" is a proverbial phrase, but "cost-threshold analysis" isn't. May I suggest "cost-based analysis" or "cost-only analysis"?

llvm/test/Transforms/Inline/inline-cost-benefit-multiplier-override.ll

2

Remove this empty line.

68

Insert a new line at the end.

[mingmingl]

Thanks for the suggestions around readability! Resolve comments.

llvm/test/Transforms/Inline/inline-cost-benefit-multiplier-override.ll

68

Whoops. This No newline at end of file should be an inserted by the editor. I removed it.

[kazu]

LGTM. Thanks!

[mingmingl]

thanks for the reviews and suggestions! It's great to keep this in Phab (before reviews are fully on Github PR) ˙ᵕ˙

I'll do a sanity check of run, add a brief comment to explain the motivation (hardwares with much smaller icache and weaker frontend might need a per-target multiplier), and then land this.

[mingmingl]

I did a sanity check of this NFC change; the performance result is neutral (expected).

llvm/include/llvm/Analysis/TargetTransformInfo.h

public:
   /// \returns A value by which our inlining threshold should be multiplied.
   /// This is primarily used to bump up the inlining threshold wholesale on
   /// targets where calls are unusually expensive.
   ///
   /// TODO: This is a rather blunt instrument.  Perhaps altering the costs of
   /// individual classes of instructions would be better.
   unsigned getInliningThresholdMultiplier() const;
 
+  unsigned getInliningCostBenefitAnalysisSavingsMultiplier() const;
+  unsigned getInliningCostBenefitAnalysisProfitableMultiplier() const;
+
   /// \returns A value to be added to the inlining threshold.
   unsigned adjustInliningThreshold(const CallBase *CB) const;
 
   /// \returns The cost of having an Alloca in the caller if not inlined, to be
   /// added to the threshold
   unsigned getCallerAllocaCost(const CallBase *CB, const AllocaInst *AI) const;
 
   /// \returns Vector bonus in percent.
virtual InstructionCost getGEPCost(Type *PointeeType, const Value *Ptr,
                                      ArrayRef<const Value *> Operands,
                                      Type *AccessType,
                                      TTI::TargetCostKind CostKind) = 0;
   virtual InstructionCost
   getPointersChainCost(ArrayRef<const Value *> Ptrs, const Value *Base,
                        const TTI::PointersChainInfo &Info, Type *AccessTy,
                        TTI::TargetCostKind CostKind) = 0;
   virtual unsigned getInliningThresholdMultiplier() const = 0;
+  virtual unsigned getInliningCostBenefitAnalysisSavingsMultiplier() const = 0;
+  virtual unsigned
+  getInliningCostBenefitAnalysisProfitableMultiplier() const = 0;
   virtual unsigned adjustInliningThreshold(const CallBase *CB) = 0;
   virtual int getInlinerVectorBonusPercent() const = 0;
   virtual unsigned getCallerAllocaCost(const CallBase *CB,
                                        const AllocaInst *AI) const = 0;
   virtual InstructionCost getMemcpyCost(const Instruction *I) = 0;
   virtual uint64_t getMaxMemIntrinsicInlineSizeThreshold() const = 0;
   virtual unsigned
   getEstimatedNumberOfCaseClusters(const SwitchInst &SI, unsigned &JTSize,
InstructionCost getPointersChainCost(ArrayRef<const Value *> Ptrs,
     return Impl.getPointersChainCost(Ptrs, Base, Info, AccessTy, CostKind);
   }
   unsigned getInliningThresholdMultiplier() const override {
     return Impl.getInliningThresholdMultiplier();
   }
   unsigned adjustInliningThreshold(const CallBase *CB) override {
     return Impl.adjustInliningThreshold(CB);
   }
+  unsigned getInliningCostBenefitAnalysisSavingsMultiplier() const override {
+    return Impl.getInliningCostBenefitAnalysisSavingsMultiplier();
+  }
+  unsigned getInliningCostBenefitAnalysisProfitableMultiplier() const override {
+    return Impl.getInliningCostBenefitAnalysisProfitableMultiplier();
+  }
   int getInlinerVectorBonusPercent() const override {
     return Impl.getInlinerVectorBonusPercent();
   }
   unsigned getCallerAllocaCost(const CallBase *CB,
                                const AllocaInst *AI) const override {
     return Impl.getCallerAllocaCost(CB, AI);
   }
   InstructionCost getMemcpyCost(const Instruction *I) override {

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

unsigned getEstimatedNumberOfCaseClusters(const SwitchInst &SI,
                                             BlockFrequencyInfo *BFI) const {
     (void)PSI;
     (void)BFI;
     JTSize = 0;
     return SI.getNumCases();
   }
 
   unsigned getInliningThresholdMultiplier() const { return 1; }
+  unsigned getInliningCostBenefitAnalysisSavingsMultiplier() const { return 8; }
+  unsigned getInliningCostBenefitAnalysisProfitableMultiplier() const {
+    return 8;
+  }
   unsigned adjustInliningThreshold(const CallBase *CB) const { return 0; }
   unsigned getCallerAllocaCost(const CallBase *CB, const AllocaInst *AI) const {
     return 0;
   };
 
   int getInlinerVectorBonusPercent() const { return 150; }
 
   InstructionCost getMemcpyCost(const Instruction *I) const {

llvm/lib/Analysis/InlineCost.cpp

static cl::opt<int>
     ColdCallSiteThreshold("inline-cold-callsite-threshold", cl::Hidden,
                           cl::init(45),
                           cl::desc("Threshold for inlining cold callsites"));
 
 static cl::opt<bool> InlineEnableCostBenefitAnalysis(
     "inline-enable-cost-benefit-analysis", cl::Hidden, cl::init(false),
     cl::desc("Enable the cost-benefit analysis for the inliner"));
 
+// InlineSavingsMultiplier overrides per TTI multipliers iff it is
+// specified explicitly in command line options. This option is exposed
+// for tuning and testing.
 static cl::opt<int> InlineSavingsMultiplier(
     "inline-savings-multiplier", cl::Hidden, cl::init(8),
     cl::desc("Multiplier to multiply cycle savings by during inlining"));
 
+// InlineSavingsProfitableMultiplier overrides per TTI multipliers iff it is
+// specified explicitly in command line options. This option is exposed
+// for tuning and testing.
+static cl::opt<int> InlineSavingsProfitableMultiplier(
+    "inline-savings-profitable-multiplier", cl::Hidden, cl::init(4),
+    cl::desc("A multiplier on top of cycle savings to decide whether the "
+             "savings won't justify the cost"));
+
 static cl::opt<int>
     InlineSizeAllowance("inline-size-allowance", cl::Hidden, cl::init(100),
                         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.
bool isCostBenefitAnalysisEnabled() {
 
     BlockFrequencyInfo *CalleeBFI = &(GetBFI(F));
     if (!CalleeBFI)
       return false;
 
     return true;
   }
 
+  // A helper function to choose between command line override and default.
+  unsigned getInliningCostBenefitAnalysisSavingsMultiplier() const {
+    if (InlineSavingsMultiplier.getNumOccurrences())
+      return InlineSavingsMultiplier;
+    return TTI.getInliningCostBenefitAnalysisSavingsMultiplier();
+  }
+
+  // A helper function to choose between command line override and default.
+  unsigned getInliningCostBenefitAnalysisProfitableMultiplier() const {
+    if (InlineSavingsProfitableMultiplier.getNumOccurrences())
+      return InlineSavingsProfitableMultiplier;
+    return TTI.getInliningCostBenefitAnalysisProfitableMultiplier();
+  }
+
+  void OverrideCycleSavingsAndSizeForTesting(APInt &CycleSavings, int &Size) {
+    if (std::optional<int> AttrCycleSavings = getStringFnAttrAsInt(
+            CandidateCall, "inline-cycle-savings-for-test")) {
+      CycleSavings = *AttrCycleSavings;
+    }
+
+    if (std::optional<int> AttrRuntimeCost = getStringFnAttrAsInt(
+            CandidateCall, "inline-runtime-cost-for-test")) {
+      Size = *AttrRuntimeCost;
+    }
+  }
+
   // Determine whether we should inline the given call site, taking into account
   // both the size cost and the cycle savings.  Return std::nullopt if we don't
   // have sufficient profiling information to determine.
   std::optional<bool> costBenefitAnalysis() {
     if (!CostBenefitAnalysisEnabled)
       return std::nullopt;
 
     // buildInlinerPipeline in the pass builder sets HotCallSiteThreshold to 0
std::optional<bool> costBenefitAnalysis() {
     CycleSavings = CycleSavings.udiv(EntryCount);
 
     // Compute the total savings for the call site.
     auto *CallerBB = CandidateCall.getParent();
     BlockFrequencyInfo *CallerBFI = &(GetBFI(*(CallerBB->getParent())));
     CycleSavings += getCallsiteCost(this->CandidateCall, DL);
     CycleSavings *= *CallerBFI->getBlockProfileCount(CallerBB);
 
-    // Remove the cost of the cold basic blocks.
+    // Remove the cost of the cold basic blocks to model the runtime cost more
+    // accurately. Both machine block placement and function splitting could
+    // place cold blocks further from hot 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;
 
+    OverrideCycleSavingsAndSizeForTesting(CycleSavings, Size);
     CostBenefit.emplace(APInt(128, Size), CycleSavings);
 
-    // Return true if the savings justify the cost of inlining.  Specifically,
-    // we evaluate the following inequality:
+    // Let R be the ratio of CycleSavings to Size.  We accept the inlining
+    // opportunity if R is really high and reject if R is really low.  If R is
+    // somewhere in the middle, we fall back to the cost-based analysis.
     //
-    //  CycleSavings      PSI->getOrCompHotCountThreshold()
-    // -------------- >= -----------------------------------
-    //       Size              InlineSavingsMultiplier
+    // Specifically, let R = CycleSavings / Size, we accept the inlining
+    // opportunity if:
     //
-    // 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);
+    //             PSI->getOrCompHotCountThreshold()
+    // R > -------------------------------------------------
+    //     getInliningCostBenefitAnalysisSavingsMultiplier()
+    //
+    // and reject the inlining opportunity if:
+    //
+    //                PSI->getOrCompHotCountThreshold()
+    // R <= ----------------------------------------------------
+    //      getInliningCostBenefitAnalysisProfitableMultiplier()
+    //
+    // Otherwise, we fall back to the cost-based analysis.
+    //
+    // Implementation-wise, use multiplication (CycleSavings * Multiplier,
+    // HotCountThreshold * Size) rather than division to avoid precision loss.
+    APInt Threshold(128, PSI->getOrCompHotCountThreshold());
+    Threshold *= Size;
+
+    APInt UpperBoundCycleSavings = CycleSavings;
+    UpperBoundCycleSavings *= getInliningCostBenefitAnalysisSavingsMultiplier();
+    if (UpperBoundCycleSavings.uge(Threshold))
+      return true;
+
+    APInt LowerBoundCycleSavings = CycleSavings;
+    LowerBoundCycleSavings *=
+        getInliningCostBenefitAnalysisProfitableMultiplier();
+    if (LowerBoundCycleSavings.ult(Threshold))
+      return false;
+
+    // Otherwise, fall back to the cost-based analysis.
+    return std::nullopt;
   }
 
   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).

llvm/lib/Analysis/TargetTransformInfo.cpp

TargetTransformInfo &TargetTransformInfo::operator=(TargetTransformInfo &&RHS) {
   return *this;
 }
 
 unsigned TargetTransformInfo::getInliningThresholdMultiplier() const {
   return TTIImpl->getInliningThresholdMultiplier();
 }
 
 unsigned
+TargetTransformInfo::getInliningCostBenefitAnalysisSavingsMultiplier() const {
+  return TTIImpl->getInliningCostBenefitAnalysisSavingsMultiplier();
+}
+
+unsigned
+TargetTransformInfo::getInliningCostBenefitAnalysisProfitableMultiplier()
+    const {
+  return TTIImpl->getInliningCostBenefitAnalysisProfitableMultiplier();
+}
+
+unsigned
 TargetTransformInfo::adjustInliningThreshold(const CallBase *CB) const {
   return TTIImpl->adjustInliningThreshold(CB);
 }
 
 unsigned TargetTransformInfo::getCallerAllocaCost(const CallBase *CB,
                                                   const AllocaInst *AI) const {
   return TTIImpl->getCallerAllocaCost(CB, AI);
 }

llvm/test/Transforms/Inline/inline-cost-benefit-multiplier-override.ll

+; RUN: opt < %s -passes='require<profile-summary>,cgscc(inline)' -pass-remarks=inline -pass-remarks-missed=inline -inline-savings-multiplier=4 -inline-savings-profitable-multiplier=5 -S 2>&1| FileCheck %s
+
+; Test that inline cost benefit multipler could be configured from command line.
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; @inlined_caleee is inlined by cost-benefit anlysis.
+; @not_inlined_callee is not inlined, decided by cost-benefit analysis
+; CHECK: remark: <unknown>:0:0: 'inlined_callee' inlined into 'caller' with (cost=always): benefit over cost
+; CHECK: remark: <unknown>:0:0: 'not_inlined_callee' not inlined into 'caller' because it should never be inlined (cost=never): cost over benefit
+
+define i32 @inlined_callee(i32 %c) !prof !17 {
+entry:
+  %mul = mul nsw i32 %c, %c
+  ret i32 %mul
+}
+
+define i32 @not_inlined_callee(i32 %c) !prof !18 {
+entry:
+  %add = add nsw i32 %c, 2
+  ret i32 %add
+}
+
+define i32 @caller(i32 %a, i32 %c)  !prof !15 {
+entry:
+  %rem = srem i32 %a, 3
+  %cmp = icmp eq i32 %rem, 0
+  br i1 %cmp, label %if.then, label %if.end, !prof !16
+
+if.then:
+; CHECK-LABEL: if.then:
+; CHECK-NOT: call i32 @inlined_callee
+  %call = tail call i32 @inlined_callee(i32 %c) "inline-cycle-savings-for-test"="26" "inline-runtime-cost-for-test"="1"
+  br label %return
+
+if.end:
+; CHECK-LABEL: if.end:
+; CHECK: call i32 @not_inlined_callee
+  %call1 = tail call i32 @not_inlined_callee(i32 %c) "inline-cycle-savings-for-test"="19" "inline-runtime-cost-for-test"="1"
+  br label %return
+
+return:
+  %retval.0 = phi i32 [ %call, %if.then ], [ %call1, %if.end ]
+  ret i32 %retval.0
+}
+
+!llvm.module.flags = !{!1}
+
+!1 = !{i32 1, !"ProfileSummary", !2}
+!2 = !{!3, !4, !5, !6, !7, !8, !9, !10}
+!3 = !{!"ProfileFormat", !"InstrProf"}
+!4 = !{!"TotalCount", i64 10000}
+!5 = !{!"MaxCount", i64 1000}
+!6 = !{!"MaxInternalCount", i64 1}
+!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 990000, i64 100, i32 1}
+!14 = !{i32 999999, i64 1, i32 2}
+!15 = !{!"function_entry_count", i64 500}
+!16 = !{!"branch_weights", i32 1, i32 2}
+!17 = !{!"function_entry_count", i64 200}
+!18 = !{!"function_entry_count", i64 400}