[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

908–912

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

91

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(

95

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.

891–903

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.

916

Remove this empty inline for consistency with the block above.

920

// 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

1 ↗

(On Diff #557191)

Remove this empty line.

69 ↗

(On Diff #557191)

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

69 ↗

(On Diff #557191)

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 Vector bonus in percent.
   ///
   /// Vector bonuses: We want to more aggressively inline vector-dense kernels
   /// and apply this bonus based on the percentage of vector instructions. A
   /// bonus is applied if the vector instructions exceed 50% and half that
public:
   virtual InstructionCost getGEPCost(Type *PointeeType, const Value *Ptr,
                                      ArrayRef<const Value *> Operands,
                                      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 InstructionCost getMemcpyCost(const Instruction *I) = 0;
   virtual unsigned
   getEstimatedNumberOfCaseClusters(const SwitchInst &SI, unsigned &JTSize,
                                    ProfileSummaryInfo *PSI,
                                    BlockFrequencyInfo *BFI) = 0;
   virtual InstructionCost getInstructionCost(const User *U,
InstructionCost getPointersChainCost(ArrayRef<const Value *> Ptrs,
                                        const PointersChainInfo &Info,
                                        Type *AccessTy,
                                        TargetCostKind CostKind) override {
     return Impl.getPointersChainCost(Ptrs, Base, Info, AccessTy, CostKind);
   }
   unsigned getInliningThresholdMultiplier() const override {
     return Impl.getInliningThresholdMultiplier();
   }
+  unsigned getInliningCostBenefitAnalysisSavingsMultiplier() const override {
+    return Impl.getInliningCostBenefitAnalysisSavingsMultiplier();
+  }
+  unsigned getInliningCostBenefitAnalysisProfitableMultiplier() const override {
+    return Impl.getInliningCostBenefitAnalysisProfitableMultiplier();
+  }
   unsigned adjustInliningThreshold(const CallBase *CB) override {
     return Impl.adjustInliningThreshold(CB);
   }
   int getInlinerVectorBonusPercent() const override {
     return Impl.getInlinerVectorBonusPercent();
   }
   InstructionCost getMemcpyCost(const Instruction *I) override {
     return Impl.getMemcpyCost(I);

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; }
 
   int getInlinerVectorBonusPercent() const { return 150; }
 
   InstructionCost getMemcpyCost(const Instruction *I) const {
     return TTI::TCC_Expensive;
   }
 

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"));
 
 static cl::opt<int> InlineSavingsMultiplier(
     "inline-savings-multiplier", cl::Hidden, cl::init(8),
     cl::desc("Multiplier to multiply cycle savings by during inlining"));
 
 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.
 static cl::opt<int> ColdThreshold(
std::optional<bool> costBenefitAnalysis() {
     int Size = Cost - ColdSize;
 
     // Allow tiny callees to be inlined regardless of whether they meet the
     // savings threshold.
     Size = Size > InlineSizeAllowance ? Size - InlineSizeAllowance : 1;
 
     CostBenefit.emplace(APInt(128, Size), CycleSavings);
 
-    // Return true if the savings justify the cost of inlining.  Specifically,
+    // Inline 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;
+    LHS *= TTI.getInliningCostBenefitAnalysisSavingsMultiplier();
     APInt RHS(128, PSI->getOrCompHotCountThreshold());
     RHS *= Size;
-    return LHS.uge(RHS);
+    if (LHS.uge(RHS))
+      return true;
+
+    // If the savings doesn't justify the size cost, do not inline.
+    APInt ProfitableThreshold = CycleSavings;
+    ProfitableThreshold *= TTI.getInliningCostBenefitAnalysisProfitableMultiplier();
+
+    if (RHS.ule(ProfitableThreshold))
+      return false;
+
+    // Otherwise, fallback to cost-threshold 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).
     auto *Caller = CandidateCall.getFunction();
     if (Caller->hasMinSize()) {
       DominatorTree DT(F);
       LoopInfo LI(DT);
       int NumLoops = 0;

llvm/lib/Analysis/TargetTransformInfo.cpp

TargetTransformInfo &TargetTransformInfo::operator=(TargetTransformInfo &&RHS) {
   TTIImpl = std::move(RHS.TTIImpl);
   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);
 }
 
 int TargetTransformInfo::getInlinerVectorBonusPercent() const {
   return TTIImpl->getInlinerVectorBonusPercent();
 }