[PGO][PGSO] ProfileSummary changes.

[hjyamauchi]

Summary

(Split of off D67120)

ProfileSummary changes for profile guided size optimization.

[tejohnson]

The abbreviation PGSO is used throughout the code but never defined. Suggest defining it in a few places (e.g. on the new data members and function declarations).

llvm/include/llvm/Analysis/ProfileSummaryInfo.h

55

Please add comments for these 2 new data members

llvm/lib/Analysis/ProfileSummaryInfo.cpp

83

Should this instead be one of the -pgso-cutoff-* options?

[hjyamauchi]

Update.

llvm/lib/Analysis/ProfileSummaryInfo.cpp

83

No, this is meant to be like ProfileSummaryHugeWorkingSetSizeThreshold but separately tuned for PGSO to decide whether to have PGSO applied, based on the same profile-summary-cutoff-hot, rather than a different definition of huge working set size that changes based on pgso-cutoff-*. Turning up or down pgso-cutoff-* and choosing whether to having PGSO applied are meant to be independent. Added a comment.

[hjyamauchi]

In D67377#1664837, @tejohnson wrote:

The abbreviation PGSO is used throughout the code but never defined. Suggest defining it in a few places (e.g. on the new data members and function declarations).

Done.

[davidxl]

I don't think we should use 'PGSO' in the profile summary class. Instead, we should differentiate it from 'hot' with other categories like VeryHot, LukeWarm etc ...

llvm/include/llvm/Analysis/ProfileSummaryInfo.h

110

Why can't PGSO huge working set size be unified with the regular one?

llvm/lib/Analysis/ProfileSummaryInfo.cpp

67

Call it ProfileSummaryCutoffInstVeryHot

73

ProfileSummaryCutoffSampleVeryHot

[hjyamauchi]

In D67377#1664995, @davidxl wrote:

I don't think we should use 'PGSO' in the profile summary class. Instead, we should differentiate it from 'hot' with other categories like VeryHot, LukeWarm etc ...

I used to do similar to that, but I got to the current form where the notion of "the PGSO cutoff" is built into PSI and that cutoff is specific to PGSO because it's simple (the code to handle this profile percentile is all in PSI, etc.).

We could move it outside PSI and add the notion of VeryHot in PSI and map the PGSO cutoff choice that we want to those Cold/Hot/VeryHot and adjust the right flag, but I thought that that seemed complicated (if we want the 25 percentile as the cutoff, know that it's above Hot and set the PGSO cutoff to VeryHot and adjust ProfileSummaryCutoffVeryHot=25, etc. The thinking was why not just say "the PGSO cutoff = 25 (or 99.98 or 0)" regardless of the values of Cold/Hot/..?

In addition, we could try to achieve the same thing instead by set the PGSO cutoff to Hot and adjust ProfileSummaryCutoffHot=25 (and adjust ProfileSummaryCutoffVeryHot < 25 so that to maintain the invariant ProfileSummaryCutoffHot > ProfileSummaryCutoffVeryHot) but that would be odd (why allow this odd flexibility?) and would affect a lot of other optimizations. As "VeryHot" would be more generic than 'PGSO' is implied to be used by other optimizations, it'd affect them even when we want to tune PGSO specifically.

An alternative that occurs to me would be to avoid using the 'PGSO' name in PSI by adding a more generic interface to PSI like "isNPercentileCount(25)" and "isNPercentileBlock(50)" and use it from PGSO.

Thoughts?

llvm/include/llvm/Analysis/ProfileSummaryInfo.h

110

So it could be tuned separately from the regular one. One of the internal apps had a working set size lower than the regular threshold but still benefited more from PGSO under the huge working set size condition. It'd be simpler to have one for sure. If it's unified, the app still benefits even without the huge working set size condition. It could be unified.

Or we could add a generic PSI::getWorkingSetSize() and use it from PGSO.

[davidxl]

It is useful to have generic interface like isHotCountNthPercentile(..) to check if a count is hot relative to a given percentile cutoff. In theory, PGSO does not have a fixed hotness threshold as it depends on workingset size. If we partition working set size into ranges like small, medium, large, huge, then PGSO can use different hotness thresholds based on that.

[hjyamauchi]

Moved 'PGSO' out of ProfileSummary.

[hjyamauchi]

PTAL.

[davidxl]

llvm/lib/Analysis/ProfileSummaryInfo.cpp

271

Why Optional?

272

since illegal PercentilCutoff will result in assertion, there seems no need to cap the cache.

274

Since you are not checking insert status, it is cleaner to use

ThresholdCache[PercentileCutoff] = CountThreshold;

[hjyamauchi]

Address comments.

[davidxl]

Some unit tests can be added to llvm/unittests/ProfileData/InstrProfTest.cpp -- there are existing profile summary tests that can be extended.

[hjyamauchi]

Added unit tests.

[davidxl]

lgtm

llvm/include/llvm/Analysis/ProfileSummaryInfo.h

private:
   bool computeSummary();
   void computeThresholds();
   // Count thresholds to answer isHotCount and isColdCount queries.
   Optional<uint64_t> HotCountThreshold, ColdCountThreshold;
   // True if the working set size of the code is considered huge,
   // because the number of profile counts required to reach the hot
   // percentile is above a huge threshold.
   Optional<bool> HasHugeWorkingSetSize;
+  // True if the working set size of the code is considered large,
+  // because the number of profile counts required to reach the hot
+  // percentile is above a large threshold.
+  Optional<bool> HasLargeWorkingSetSize;
+  // Compute the threshold for a given cutoff.
+  Optional<uint64_t> computeThreshold(int PercentileCutoff);
+  // The map that caches the threshold values. The keys are the percentile
+  // cutoff values and the values are the corresponding threshold values.
+  DenseMap<int, uint64_t> ThresholdCache;
 
 public:
   ProfileSummaryInfo(Module &M) : M(M) {}
   ProfileSummaryInfo(ProfileSummaryInfo &&Arg)
       : M(Arg.M), Summary(std::move(Arg.Summary)) {}
 
   /// Returns true if profile summary is available.
   bool hasProfileSummary() { return computeSummary(); }
public:
   }
 
   /// Returns the profile count for \p CallInst.
   Optional<uint64_t> getProfileCount(const Instruction *CallInst,
                                      BlockFrequencyInfo *BFI,
                                      bool AllowSynthetic = false);
   /// Returns true if the working set size of the code is considered huge.
   bool hasHugeWorkingSetSize();
+  /// Returns true if the working set size of the code is considered large.
+  bool hasLargeWorkingSetSize();
   /// Returns true if \p F has hot function entry.
   bool isFunctionEntryHot(const Function *F);
   /// Returns true if \p F contains hot code.
   bool isFunctionHotInCallGraph(const Function *F, BlockFrequencyInfo &BFI);
   /// Returns true if \p F has cold function entry.
   bool isFunctionEntryCold(const Function *F);
   /// Returns true if \p F contains only cold code.
   bool isFunctionColdInCallGraph(const Function *F, BlockFrequencyInfo &BFI);
+  /// Returns true if \p F contains hot code with regard to a given hot
+  /// percentile cutoff value.
+  bool isFunctionHotInCallGraphNthPercentile(int PercentileCutoff,
+                                             const Function *F,
+                                             BlockFrequencyInfo &BFI);
   /// Returns true if count \p C is considered hot.
   bool isHotCount(uint64_t C);
   /// Returns true if count \p C is considered cold.
   bool isColdCount(uint64_t C);
+  /// Returns true if count \p C is considered hot with regard to a given
+  /// hot percentile cutoff value.
+  bool isHotCountNthPercentile(int PercentileCutoff, uint64_t C);
   /// Returns true if BasicBlock \p BB is considered hot.
   bool isHotBlock(const BasicBlock *BB, BlockFrequencyInfo *BFI);
   /// Returns true if BasicBlock \p BB is considered cold.
   bool isColdBlock(const BasicBlock *BB, BlockFrequencyInfo *BFI);
+  /// Returns true if BasicBlock \p BB is considered hot with regard to a given
+  /// hot percentile cutoff value.
+  bool isHotBlockNthPercentile(int PercentileCutoff,
+                               const BasicBlock *BB, BlockFrequencyInfo *BFI);
   /// Returns true if CallSite \p CS is considered hot.
   bool isHotCallSite(const CallSite &CS, BlockFrequencyInfo *BFI);
   /// Returns true if Callsite \p CS is considered cold.
   bool isColdCallSite(const CallSite &CS, BlockFrequencyInfo *BFI);
   /// Returns HotCountThreshold if set. Recompute HotCountThreshold
   /// if not set.
   uint64_t getOrCompHotCountThreshold();
   /// Returns ColdCountThreshold if set. Recompute HotCountThreshold

llvm/lib/Analysis/ProfileSummaryInfo.cpp

 
 static cl::opt<unsigned> ProfileSummaryHugeWorkingSetSizeThreshold(
     "profile-summary-huge-working-set-size-threshold", cl::Hidden,
     cl::init(15000), cl::ZeroOrMore,
     cl::desc("The code working set size is considered huge if the number of"
              " blocks required to reach the -profile-summary-cutoff-hot"
              " percentile exceeds this count."));
 
+static cl::opt<unsigned> ProfileSummaryLargeWorkingSetSizeThreshold(
+    "profile-summary-large-working-set-size-threshold", cl::Hidden,
+    cl::init(12500), cl::ZeroOrMore,
+    cl::desc("The code working set size is considered large if the number of"
+             " blocks required to reach the -profile-summary-cutoff-hot"
+             " percentile exceeds this count."));
+
 // The next two options override the counts derived from summary computation and
 // are useful for debugging purposes.
 static cl::opt<int> ProfileSummaryHotCount(
     "profile-summary-hot-count", cl::ReallyHidden, cl::ZeroOrMore,
     cl::desc("A fixed hot count that overrides the count derived from"
              " profile-summary-cutoff-hot"));
 
 static cl::opt<int> ProfileSummaryColdCount(
     "profile-summary-cold-count", cl::ReallyHidden, cl::ZeroOrMore,
     cl::desc("A fixed cold count that overrides the count derived from"
              " profile-summary-cutoff-cold"));
 
 // Find the summary entry for a desired percentile of counts.
 static const ProfileSummaryEntry &getEntryForPercentile(SummaryEntryVector &DS,
                                                         uint64_t Percentile) {
   auto It = partition_point(DS, [=](const ProfileSummaryEntry &Entry) {
     return Entry.Cutoff < Percentile;
   });
   // The required percentile has to be <= one of the percentiles in the
   // detailed summary.
   if (It == DS.end())
     report_fatal_error("Desired percentile exceeds the maximum cutoff");
   return *It;
 }
 
 // The profile summary metadata may be attached either by the frontend or by
 // any backend passes (IR level instrumentation, for example). This method
 // checks if the Summary is null and if so checks if the summary metadata is now
 // available in the module and parses it to get the Summary object. Returns true
 // if a valid Summary is available.
 bool ProfileSummaryInfo::computeSummary() {
   if (Summary)
     return true;
   // First try to get context sensitive ProfileSummary.
   auto *SummaryMD = M.getProfileSummary(/* IsCS */ true);
   if (SummaryMD) {
     Summary.reset(ProfileSummary::getFromMD(SummaryMD));
if (!isColdCount(TotalCallCount))
       return false;
   }
   for (const auto &BB : *F)
     if (!isColdBlock(&BB, &BFI))
       return false;
   return true;
 }
 
+// Like isFunctionHotInCallGraph but for a given cutoff.
+bool ProfileSummaryInfo::isFunctionHotInCallGraphNthPercentile(
+    int PercentileCutoff, const Function *F, BlockFrequencyInfo &BFI) {
+  if (!F || !computeSummary())
+    return false;
+  if (auto FunctionCount = F->getEntryCount())
+    if (isHotCountNthPercentile(PercentileCutoff, FunctionCount.getCount()))
+      return true;
+
+  if (hasSampleProfile()) {
+    uint64_t TotalCallCount = 0;
+    for (const auto &BB : *F)
+      for (const auto &I : BB)
+        if (isa<CallInst>(I) || isa<InvokeInst>(I))
+          if (auto CallCount = getProfileCount(&I, nullptr))
+            TotalCallCount += CallCount.getValue();
+    if (isHotCountNthPercentile(PercentileCutoff, TotalCallCount))
+      return true;
+  }
+  for (const auto &BB : *F)
+    if (isHotBlockNthPercentile(PercentileCutoff, &BB, &BFI))
+      return true;
+  return false;
+}
+
 /// Returns true if the function's entry is a cold. If it returns false, it
 /// either means it is not cold or it is unknown whether it is cold or not (for
 /// example, no profile data is available).
 bool ProfileSummaryInfo::isFunctionEntryCold(const Function *F) {
   if (!F)
     return false;
   if (F->hasFnAttribute(Attribute::Cold))
     return true;
auto &ColdEntry =
       getEntryForPercentile(DetailedSummary, ProfileSummaryCutoffCold);
   ColdCountThreshold = ColdEntry.MinCount;
   if (ProfileSummaryColdCount.getNumOccurrences() > 0)
     ColdCountThreshold = ProfileSummaryColdCount;
   assert(ColdCountThreshold <= HotCountThreshold &&
          "Cold count threshold cannot exceed hot count threshold!");
   HasHugeWorkingSetSize =
       HotEntry.NumCounts > ProfileSummaryHugeWorkingSetSizeThreshold;
+  HasLargeWorkingSetSize =
+      HotEntry.NumCounts > ProfileSummaryLargeWorkingSetSizeThreshold;
+}
+
+Optional<uint64_t> ProfileSummaryInfo::computeThreshold(int PercentileCutoff) {
+  if (!computeSummary())
+    return None;
+  auto iter = ThresholdCache.find(PercentileCutoff);
+  if (iter != ThresholdCache.end()) {
+    return iter->second;
+  }
+  auto &DetailedSummary = Summary->getDetailedSummary();
+  auto &Entry =
+      getEntryForPercentile(DetailedSummary, PercentileCutoff);
+  uint64_t CountThreshold = Entry.MinCount;
+  ThresholdCache[PercentileCutoff] = CountThreshold;
+  return CountThreshold;
 }
 
 bool ProfileSummaryInfo::hasHugeWorkingSetSize() {
   if (!HasHugeWorkingSetSize)
     computeThresholds();
   return HasHugeWorkingSetSize && HasHugeWorkingSetSize.getValue();
 }
 
+bool ProfileSummaryInfo::hasLargeWorkingSetSize() {
+  if (!HasLargeWorkingSetSize)
+    computeThresholds();
+  return HasLargeWorkingSetSize && HasLargeWorkingSetSize.getValue();
+}
+
 bool ProfileSummaryInfo::isHotCount(uint64_t C) {
   if (!HotCountThreshold)
     computeThresholds();
   return HotCountThreshold && C >= HotCountThreshold.getValue();
 }
 
 bool ProfileSummaryInfo::isColdCount(uint64_t C) {
   if (!ColdCountThreshold)
     computeThresholds();
   return ColdCountThreshold && C <= ColdCountThreshold.getValue();
 }
 
+bool ProfileSummaryInfo::isHotCountNthPercentile(int PercentileCutoff, uint64_t C) {
+  auto CountThreshold = computeThreshold(PercentileCutoff);
+  return CountThreshold && C >= CountThreshold.getValue();
+}
+
 uint64_t ProfileSummaryInfo::getOrCompHotCountThreshold() {
   if (!HotCountThreshold)
     computeThresholds();
   return HotCountThreshold ? HotCountThreshold.getValue() : UINT64_MAX;
 }
 
 uint64_t ProfileSummaryInfo::getOrCompColdCountThreshold() {
   if (!ColdCountThreshold)
     computeThresholds();
   return ColdCountThreshold ? ColdCountThreshold.getValue() : 0;
 }
 
 bool ProfileSummaryInfo::isHotBlock(const BasicBlock *BB, BlockFrequencyInfo *BFI) {
   auto Count = BFI->getBlockProfileCount(BB);
   return Count && isHotCount(*Count);
 }
 
 bool ProfileSummaryInfo::isColdBlock(const BasicBlock *BB,
                                   BlockFrequencyInfo *BFI) {
   auto Count = BFI->getBlockProfileCount(BB);
   return Count && isColdCount(*Count);
 }
 
+bool ProfileSummaryInfo::isHotBlockNthPercentile(int PercentileCutoff,
+                                                 const BasicBlock *BB,
+                                                 BlockFrequencyInfo *BFI) {
+  auto Count = BFI->getBlockProfileCount(BB);
+  return Count && isHotCountNthPercentile(PercentileCutoff, *Count);
+}
+
 bool ProfileSummaryInfo::isHotCallSite(const CallSite &CS,
                                        BlockFrequencyInfo *BFI) {
   auto C = getProfileCount(CS.getInstruction(), BFI);
   return C && isHotCount(*C);
 }
 
 bool ProfileSummaryInfo::isColdCallSite(const CallSite &CS,
                                         BlockFrequencyInfo *BFI) {

llvm/unittests/Analysis/ProfileSummaryInfoTest.cpp

TEST_F(ProfileSummaryInfoTest, TestCommon) {
 
   ProfileSummaryInfo PSI = buildPSI(M.get());
   EXPECT_TRUE(PSI.hasProfileSummary());
   EXPECT_TRUE(PSI.isHotCount(400));
   EXPECT_TRUE(PSI.isColdCount(2));
   EXPECT_FALSE(PSI.isColdCount(100));
   EXPECT_FALSE(PSI.isHotCount(100));
 
+  EXPECT_TRUE(PSI.isHotCountNthPercentile(990000, 400));
+  EXPECT_FALSE(PSI.isHotCountNthPercentile(990000, 100));
+  EXPECT_FALSE(PSI.isHotCountNthPercentile(990000, 2));
+
+  EXPECT_TRUE(PSI.isHotCountNthPercentile(999999, 400));
+  EXPECT_TRUE(PSI.isHotCountNthPercentile(999999, 100));
+  EXPECT_FALSE(PSI.isHotCountNthPercentile(999999, 2));
+
+  EXPECT_FALSE(PSI.isHotCountNthPercentile(10000, 400));
+  EXPECT_FALSE(PSI.isHotCountNthPercentile(10000, 100));
+  EXPECT_FALSE(PSI.isHotCountNthPercentile(10000, 2));
+
   EXPECT_TRUE(PSI.isFunctionEntryHot(F));
   EXPECT_FALSE(PSI.isFunctionEntryHot(G));
   EXPECT_FALSE(PSI.isFunctionEntryHot(H));
 }
 
 TEST_F(ProfileSummaryInfoTest, InstrProf) {
   auto M = makeLLVMModule("InstrProf");
   Function *F = M->getFunction("f");
   ProfileSummaryInfo PSI = buildPSI(M.get());
   EXPECT_TRUE(PSI.hasProfileSummary());
   EXPECT_TRUE(PSI.hasInstrumentationProfile());
 
   BasicBlock &BB0 = F->getEntryBlock();
   BasicBlock *BB1 = BB0.getTerminator()->getSuccessor(0);
   BasicBlock *BB2 = BB0.getTerminator()->getSuccessor(1);
   BasicBlock *BB3 = BB1->getSingleSuccessor();
 
   BlockFrequencyInfo BFI = buildBFI(*F);
   EXPECT_TRUE(PSI.isHotBlock(&BB0, &BFI));
   EXPECT_TRUE(PSI.isHotBlock(BB1, &BFI));
   EXPECT_FALSE(PSI.isHotBlock(BB2, &BFI));
   EXPECT_TRUE(PSI.isHotBlock(BB3, &BFI));
 
+  EXPECT_TRUE(PSI.isHotBlockNthPercentile(990000, &BB0, &BFI));
+  EXPECT_TRUE(PSI.isHotBlockNthPercentile(990000, BB1, &BFI));
+  EXPECT_FALSE(PSI.isHotBlockNthPercentile(990000, BB2, &BFI));
+  EXPECT_TRUE(PSI.isHotBlockNthPercentile(990000, BB3, &BFI));
+
+  EXPECT_TRUE(PSI.isHotBlockNthPercentile(999900, &BB0, &BFI));
+  EXPECT_TRUE(PSI.isHotBlockNthPercentile(999900, BB1, &BFI));
+  EXPECT_TRUE(PSI.isHotBlockNthPercentile(999900, BB2, &BFI));
+  EXPECT_TRUE(PSI.isHotBlockNthPercentile(999900, BB3, &BFI));
+
+  EXPECT_FALSE(PSI.isHotBlockNthPercentile(10000, &BB0, &BFI));
+  EXPECT_FALSE(PSI.isHotBlockNthPercentile(10000, BB1, &BFI));
+  EXPECT_FALSE(PSI.isHotBlockNthPercentile(10000, BB2, &BFI));
+  EXPECT_FALSE(PSI.isHotBlockNthPercentile(10000, BB3, &BFI));
+
   CallSite CS1(BB1->getFirstNonPHI());
   auto *CI2 = BB2->getFirstNonPHI();
   CallSite CS2(CI2);
 
   EXPECT_TRUE(PSI.isHotCallSite(CS1, &BFI));
   EXPECT_FALSE(PSI.isHotCallSite(CS2, &BFI));
 
   // Test that adding an MD_prof metadata with a hot count on CS2 does not
TEST_F(ProfileSummaryInfoTest, SampleProf) {
   BasicBlock *BB3 = BB1->getSingleSuccessor();
 
   BlockFrequencyInfo BFI = buildBFI(*F);
   EXPECT_TRUE(PSI.isHotBlock(&BB0, &BFI));
   EXPECT_TRUE(PSI.isHotBlock(BB1, &BFI));
   EXPECT_FALSE(PSI.isHotBlock(BB2, &BFI));
   EXPECT_TRUE(PSI.isHotBlock(BB3, &BFI));
 
+  EXPECT_TRUE(PSI.isHotBlockNthPercentile(990000, &BB0, &BFI));
+  EXPECT_TRUE(PSI.isHotBlockNthPercentile(990000, BB1, &BFI));
+  EXPECT_FALSE(PSI.isHotBlockNthPercentile(990000, BB2, &BFI));
+  EXPECT_TRUE(PSI.isHotBlockNthPercentile(990000, BB3, &BFI));
+
+  EXPECT_TRUE(PSI.isHotBlockNthPercentile(999900, &BB0, &BFI));
+  EXPECT_TRUE(PSI.isHotBlockNthPercentile(999900, BB1, &BFI));
+  EXPECT_TRUE(PSI.isHotBlockNthPercentile(999900, BB2, &BFI));
+  EXPECT_TRUE(PSI.isHotBlockNthPercentile(999900, BB3, &BFI));
+
+  EXPECT_FALSE(PSI.isHotBlockNthPercentile(10000, &BB0, &BFI));
+  EXPECT_FALSE(PSI.isHotBlockNthPercentile(10000, BB1, &BFI));
+  EXPECT_FALSE(PSI.isHotBlockNthPercentile(10000, BB2, &BFI));
+  EXPECT_FALSE(PSI.isHotBlockNthPercentile(10000, BB3, &BFI));
+
   CallSite CS1(BB1->getFirstNonPHI());
   auto *CI2 = BB2->getFirstNonPHI();
   // Manually attach branch weights metadata to the call instruction.
   SmallVector<uint32_t, 1> Weights;
   Weights.push_back(1000);
   MDBuilder MDB(M->getContext());
   CI2->setMetadata(LLVMContext::MD_prof, MDB.createBranchWeights(Weights));
   CallSite CS2(CI2);