[Inliner] Increase threshold for hot callsites without PGO.

[eraman]

Summary

This increases the inlining threshold for hot callsites. Hotness is
defined in terms of block frequency of the callsite relative to the
caller's entry block's frequency. Since this requires BFI in the
inliner, this only affects the new PM pipeline.

This improves the performance of some internal benchmarks. Notably, an
internal benchmark for Gipfeli compression
(https://github.com/google/gipfeli) improves by ~7%. Povray in SPEC2006
improves by ~2.5%. I am running more experiments and will update the
thread if other benchmarks show improvement/regression.

In terms of text size, LLVM test-suite shows an 1.22% text size
increase. Diving into the results, 13 of the benchmarks in the
test-suite increases by > 10%. Most of these are small, but
Adobe-C++/loop_unroll (17.6% increases) and tramp3d(20.7% size increase)
have >250K text size. On a large application, the text size increases by
2%

[chandlerc]

While the total size increase doesn't concern me much, the >10% code size growth in some benchmarks is a bit concerning. Do these benchmarks also improve performance? If so, then this might be fine in general (once the -Os behavior is fixed, see below). However, if the benchmarks that are growing in size by a lot aren't also getting faster, then it seems a hard sell at O2 where we expect size increase to be at least generally associated with performance wins.

Naturally, this seems completely fine at O3 either way.

lib/Analysis/InlineCost.cpp

782–784 ↗

(On Diff #109250)

I think we need to avoid this for optForSize() functions.

[haicheng]

Hi Easwaran,

What if the callee of a hot callsite also has a inline hint?

Thanks,

Haicheng

[chandlerc]

In D36199#828958, @haicheng wrote:

Hi Easwaran,

What if the callee of a hot callsite also has a inline hint?

(FWIW, my 2 cents here would be that this should win over inline hint, as it should be quite a bit stronger. Anyways, will let Easwaran actually respond as well as I'm curious what he thinks.)

[eraman]

In D36199#829276, @chandlerc wrote:

In D36199#828958, @haicheng wrote:

Hi Easwaran,

What if the callee of a hot callsite also has a inline hint?

(FWIW, my 2 cents here would be that this should win over inline hint, as it should be quite a bit stronger. Anyways, will let Easwaran actually respond as well as I'm curious what he thinks.)

I initially started with a multiplier instead of an absolute threshold, but changed it mainly to be consistent with the PGO based hot callsite. It is definitely a stronger hint, but I think an argument can be made that various "signals" should be composed.

[chandlerc]

In D36199#829525, @eraman wrote:

In D36199#829276, @chandlerc wrote:

In D36199#828958, @haicheng wrote:

Hi Easwaran,

What if the callee of a hot callsite also has a inline hint?

(FWIW, my 2 cents here would be that this should win over inline hint, as it should be quite a bit stronger. Anyways, will let Easwaran actually respond as well as I'm curious what he thinks.)

I initially started with a multiplier instead of an absolute threshold, but changed it mainly to be consistent with the PGO based hot callsite. It is definitely a stronger hint, but I think an argument can be made that various "signals" should be composed.

Maybe a follow-up with benchmarks motivating (and checking for size issues)?

[eraman]

In D36199#828523, @chandlerc wrote:

While the total size increase doesn't concern me much, the >10% code size growth in some benchmarks is a bit concerning. Do these benchmarks also improve performance? If so, then this might be fine in general (once the -Os behavior is fixed, see below). However, if the benchmarks that are growing in size by a lot aren't also getting faster, then it seems a hard sell at O2 where we expect size increase to be at least generally associated with performance wins.

Naturally, this seems completely fine at O3 either way.

There are 5 tests in the test-suite with text size increase > 10% and > 4K. Three of them improve and two don't. For performance numbers, I used the perf tool to collect uops_retired:any on an Intel Xeon E5-2690 since the running time of these are small and noisy.

Test - Size increase KB (%) - Performance improvement

MultiSource/Benchmarks/VersaBench/beamformer - 5K(41.6%) - None
SingleSource/Benchmarks/Linpack/linpack-pc - 7K(36.4%) - +2%
MultiSource/Benchmarks/FreeBench/pifft - 18K(33%) - None
MultiSource/Benchmarks/tramp3d-v4 - 148K(20.7%) - 18%
SingleSource/Benchmarks/Adobe-C++/loop_unroll - 44K(17.6%) - 9%

The C/C++ subset of SPEC2006 increases by 0.5%. Two benchmarks improve in performance: 453.povray (+1.5%) and 473.astar (+1.81%).

If you think this is iffy for O2, I'll do this only for O3 for now and work on tuning it further with the goal of enabling it at O2.

[chandlerc]

In D36199#829818, @eraman wrote:

In D36199#828523, @chandlerc wrote:

While the total size increase doesn't concern me much, the >10% code size growth in some benchmarks is a bit concerning. Do these benchmarks also improve performance? If so, then this might be fine in general (once the -Os behavior is fixed, see below). However, if the benchmarks that are growing in size by a lot aren't also getting faster, then it seems a hard sell at O2 where we expect size increase to be at least generally associated with performance wins.

Naturally, this seems completely fine at O3 either way.

There are 5 tests in the test-suite with text size increase > 10% and > 4K. Three of them improve and two don't. For performance numbers, I used the perf tool to collect uops_retired:any on an Intel Xeon E5-2690 since the running time of these are small and noisy.

Test - Size increase KB (%) - Performance improvement

MultiSource/Benchmarks/VersaBench/beamformer - 5K(41.6%) - None
SingleSource/Benchmarks/Linpack/linpack-pc - 7K(36.4%) - +2%
MultiSource/Benchmarks/FreeBench/pifft - 18K(33%) - None
MultiSource/Benchmarks/tramp3d-v4 - 148K(20.7%) - 18%
SingleSource/Benchmarks/Adobe-C++/loop_unroll - 44K(17.6%) - 9%

The C/C++ subset of SPEC2006 increases by 0.5%. Two benchmarks improve in performance: 453.povray (+1.5%) and 473.astar (+1.81%).

First and foremost, thanks for the excellent data and carefully gathering all of it. =]

If you think this is iffy for O2, I'll do this only for O3 for now and work on tuning it further with the goal of enabling it at O2.

Yeah, I would put it in O3 for now, essentially to be conservative. I think this is a borderline case, but it seems easier to revisit it later than deal with churn of regressing people now, and it seems like a clear win for O3.

[eraman]

• Apply this heuristic only at O3 and disable for optsize

[chandlerc]

LGTM, thanks!

[haicheng]

llvm/trunk/lib/Analysis/InlineCost.cpp

81

Is this a typo? Maximum => Minimum

llvm/trunk/include/llvm/Analysis/InlineCost.h

struct InlineParams {
   Optional<int> OptSizeThreshold;
 
   /// Threshold to use when the caller is optimized for minsize.
   Optional<int> OptMinSizeThreshold;
 
   /// Threshold to use when the callsite is considered hot.
   Optional<int> HotCallSiteThreshold;
 
+  /// Threshold to use when the callsite is considered hot relative to function
+  /// entry.
+  Optional<int> LocallyHotCallSiteThreshold;
+
   /// Threshold to use when the callsite is considered cold.
   Optional<int> ColdCallSiteThreshold;
 };
 
 /// Generate the parameters to tune the inline cost analysis based only on the
 /// commandline options.
 InlineParams getInlineParams();
 

llvm/trunk/lib/Analysis/InlineCost.cpp

static cl::opt<int> ColdThreshold(
     "inlinecold-threshold", cl::Hidden, cl::init(45),
     cl::desc("Threshold for inlining functions with cold attribute"));
 
 static cl::opt<int>
     HotCallSiteThreshold("hot-callsite-threshold", cl::Hidden, cl::init(3000),
                          cl::ZeroOrMore,
                          cl::desc("Threshold for hot callsites "));
 
+static cl::opt<int> LocallyHotCallSiteThreshold(
+    "locally-hot-callsite-threshold", cl::Hidden, cl::init(525), cl::ZeroOrMore,
+    cl::desc("Threshold for locally hot callsites "));
+
 static cl::opt<int> ColdCallSiteRelFreq(
     "cold-callsite-rel-freq", cl::Hidden, cl::init(2), cl::ZeroOrMore,
     cl::desc("Maxmimum block frequency, expressed as a percentage of caller's "
              "entry frequency, for a callsite to be cold in the absence of "
              "profile information."));
 
+static cl::opt<int> HotCallSiteRelFreq(
+    "hot-callsite-rel-freq", cl::Hidden, cl::init(60), cl::ZeroOrMore,
+    cl::desc("Maxmimum block frequency, expressed as a multiple of caller's "
+             "entry frequency, for a callsite to be hot in the absence of "
+             "profile information."));
+
 namespace {
 
 class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   typedef InstVisitor<CallAnalyzer, bool> Base;
   friend class InstVisitor<CallAnalyzer, bool>;
 
   /// The TargetTransformInfo available for this compilation.
   const TargetTransformInfo &TTI;
class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   void updateThreshold(CallSite CS, Function &Callee);
 
   /// Return true if size growth is allowed when inlining the callee at CS.
   bool allowSizeGrowth(CallSite CS);
 
   /// Return true if \p CS is a cold callsite.
   bool isColdCallSite(CallSite CS, BlockFrequencyInfo *CallerBFI);
 
+  /// Return a higher threshold if \p CS is a hot callsite.
+  Optional<int> getHotCallSiteThreshold(CallSite CS,
+                                        BlockFrequencyInfo *CallerBFI);
+
   // Custom analysis routines.
   bool analyzeBlock(BasicBlock *BB, SmallPtrSetImpl<const Value *> &EphValues);
 
   // Disable several entry points to the visitor so we don't accidentally use
   // them by declaring but not defining them here.
   void visit(Module *);
   void visit(Module &);
   void visit(Function *);
bool CallAnalyzer::isColdCallSite(CallSite CS, BlockFrequencyInfo *CallerBFI) {
   const BranchProbability ColdProb(ColdCallSiteRelFreq, 100);
   auto CallSiteBB = CS.getInstruction()->getParent();
   auto CallSiteFreq = CallerBFI->getBlockFreq(CallSiteBB);
   auto CallerEntryFreq =
       CallerBFI->getBlockFreq(&(CS.getCaller()->getEntryBlock()));
   return CallSiteFreq < CallerEntryFreq * ColdProb;
 }
 
+Optional<int>
+CallAnalyzer::getHotCallSiteThreshold(CallSite CS,
+                                      BlockFrequencyInfo *CallerBFI) {
+  // If global profile summary is available, then callsite's hotness is
+  // determined based on that.
+
+  auto HotCallSiteThreshold = Params.HotCallSiteThreshold;
+  if (PSI->hasProfileSummary() && PSI->isHotCallSite(CS, CallerBFI))
+    return HotCallSiteThreshold;
+  if (!CallerBFI)
+    return None;
+
+  HotCallSiteThreshold = Params.LocallyHotCallSiteThreshold;
+  if (!HotCallSiteThreshold)
+    return None;
+
+  // In the absence of global profile summary, determine if the callsite is hot
+  // relative to caller's entry. We could potentially cache the computation of
+  // scaled entry frequency, but the added complexity is not worth it unless
+  // this scaling shows up high in the profiles.
+  auto CallSiteBB = CS.getInstruction()->getParent();
+  auto CallSiteFreq = CallerBFI->getBlockFreq(CallSiteBB).getFrequency();
+  auto CallerEntryFreq = CallerBFI->getEntryFreq();
+  if (CallSiteFreq >= CallerEntryFreq * HotCallSiteRelFreq)
+    return HotCallSiteThreshold;
+  return None;
+}
+
 void CallAnalyzer::updateThreshold(CallSite CS, Function &Callee) {
   // If no size growth is allowed for this inlining, set Threshold to 0.
   if (!allowSizeGrowth(CS)) {
     Threshold = 0;
     return;
   }
 
   Function *Caller = CS.getCaller();
if (PSI) {
       // by checking only the callsite hotness/coldness. The check for CallerBFI
       // exists only because we do not have BFI available with the old PM.
       //
       // Use callee's hotness information only if we have no way of determining
       // callsite's hotness information. Callsite hotness can be determined if
       // sample profile is used (which adds hotness metadata to calls) or if
       // caller's BlockFrequencyInfo is available.
       if (CallerBFI || PSI->hasSampleProfile()) {
-        if (PSI->isHotCallSite(CS, CallerBFI)) {
+        auto HotCallSiteThreshold = getHotCallSiteThreshold(CS, CallerBFI);
+        if (!Caller->optForSize() && HotCallSiteThreshold) {
           DEBUG(dbgs() << "Hot callsite.\n");
-          Threshold = Params.HotCallSiteThreshold.getValue();
+          // FIXME: This should update the threshold only if it exceeds the
+          // current threshold, but AutoFDO + ThinLTO currently relies on this
+          // behavior to prevent inlining of hot callsites during ThinLTO
+          // compile phase.
+          Threshold = HotCallSiteThreshold.getValue();
         } else if (isColdCallSite(CS, CallerBFI)) {
           DEBUG(dbgs() << "Cold callsite.\n");
           // Do not apply bonuses for a cold callsite including the
           // LastCallToStatic bonus. While this bonus might result in code size
           // reduction, it can cause the size of a non-cold caller to increase
           // preventing it from being inlined.
           DisallowAllBonuses();
           Threshold = MinIfValid(Threshold, Params.ColdCallSiteThreshold);
else
     Params.DefaultThreshold = Threshold;
 
   // Set the HintThreshold knob from the -inlinehint-threshold.
   Params.HintThreshold = HintThreshold;
 
   // Set the HotCallSiteThreshold knob from the -hot-callsite-threshold.
   Params.HotCallSiteThreshold = HotCallSiteThreshold;
 
+  // If the -locally-hot-callsite-threshold is explicitly specified, use it to
+  // populate LocallyHotCallSiteThreshold. Later, we populate
+  // Params.LocallyHotCallSiteThreshold from -locally-hot-callsite-threshold if
+  // we know that optimization level is O3 (in the getInlineParams variant that
+  // takes the opt and size levels).
+  // FIXME: Remove this check (and make the assignment unconditional) after
+  // addressing size regression issues at O2.
+  if (LocallyHotCallSiteThreshold.getNumOccurrences() > 0)
+    Params.LocallyHotCallSiteThreshold = LocallyHotCallSiteThreshold;
+
   // Set the ColdCallSiteThreshold knob from the -inline-cold-callsite-threshold.
   Params.ColdCallSiteThreshold = ColdCallSiteThreshold;
 
   // Set the OptMinSizeThreshold and OptSizeThreshold params only if the
   // -inlinehint-threshold commandline option is not explicitly given. If that
   // option is present, then its value applies even for callees with size and
   // minsize attributes.
   // If the -inline-threshold is not specified, set the ColdThreshold from the
static int computeThresholdFromOptLevels(unsigned OptLevel,
   if (SizeOptLevel == 1) // -Os
     return InlineConstants::OptSizeThreshold;
   if (SizeOptLevel == 2) // -Oz
     return InlineConstants::OptMinSizeThreshold;
   return InlineThreshold;
 }
 
 InlineParams llvm::getInlineParams(unsigned OptLevel, unsigned SizeOptLevel) {
-  return getInlineParams(computeThresholdFromOptLevels(OptLevel, SizeOptLevel));
+  auto Params =
+      getInlineParams(computeThresholdFromOptLevels(OptLevel, SizeOptLevel));
+  // At O3, use the value of -locally-hot-callsite-threshold option to populate
+  // Params.LocallyHotCallSiteThreshold. Below O3, this flag has effect only
+  // when it is specified explicitly.
+  if (OptLevel > 2)
+    Params.LocallyHotCallSiteThreshold = LocallyHotCallSiteThreshold;
+  return Params;
 }