Display detailed profile summary in llvm-profdata tool

[eraman]

Summary

This adds a detailed profile summary in llvm-profdata. The summary is in the form of one or more triples of the form (P, N, M) which is interpreted as if we look at the Top-N counts in the profile, their sum accounts for P percentage of the sum of all counts in the program and the minimum count in the Top-N is M.

[davidxl]

tools/llvm-profdata/llvm-profdata.cpp

59 ↗

(On Diff #44353)

Add simple summary data such as MaxFunctionCount and MaxBlockCount here.

63 ↗

(On Diff #44353)

Make this a private method. Instead add a public method:

addCount(const InstrProfRecord &)

63 ↗

(On Diff #44353)

AddCount --> addCount

82 ↗

(On Diff #44353)

Make this vector a member of the ProfileSummary class.

The use model (and in the future by InstrProfWriter ) should be like this:

ProfileSummary PS;

for each InstrProfRecord R:

PS.addCount(R);

PS.computeProfileSummary(cutoffs);

vector<..>& sums = PS.getProfSummary(..);
... dump

83 ↗

(On Diff #44353)

getProfileSummary

83 ↗

(On Diff #44353)

Use a scaled up integer to represent percentage. Talk to Cong about introducing a common interface for that (similar to BranchProbability)

91 ↗

(On Diff #44353)

use a different name for the local variable (conflict with member variable)

360 ↗

(On Diff #44353)

This should be moved to ProfileSummary

362 ↗

(On Diff #44353)

PS.addCount(Func);

364 ↗

(On Diff #44353)

Remove this

[vsk]

Thanks eraman! Comments inline --

tools/llvm-profdata/llvm-profdata.cpp

45 ↗

(On Diff #44353)

Nit: I have a hard time parsing this comment. Wdyt of omitting this paragraph and opting for shorter comments on the fields instead? I suggest;

float Cutoff;  //< The execution count percentile, [0, 100].
uint64_t MinExecuteCount;  //< Minimum execution count for this percentile.
uint64_t NumBlocks; //< Number of blocks in this percentile.

Or something along those lines, I don't think my wording there is perfect :).

74 ↗

(On Diff #44353)

I believe this entire conditional can be safely replaced with ++CountFrequencies[Count];.

109 ↗

(On Diff #44353)

You can avoid this construct by inverting the order of your loops, i.e iterate over the cutoffs then the histogram entries. Briefly;

PSE NextEntry;
for (float Cutoff : Cutoffs)
  NextEntry.Cutoff = Cutoff;
  std::tie(NextEntry.MinExecuteCount, NextEntry.NumBlocks) = AccumulateCountsTo(Cutoff);

[eraman]

Addressed reviewers' comments

tools/llvm-profdata/llvm-profdata.cpp

45 ↗

(On Diff #44353)

I agree that the comments I have leave much to be desired, but I am not sure the comments on the fields, in isolation, give a clear picture on what is being done.

82 ↗

(On Diff #44353)

My problem with this approach is what this allows doing

PS.computeProfileSummary(cutoffs1);
PS.computeProfileSummary(cutoffs2);

PS.getProfSummary();

If you want to separate compute and get calls, I prefer passing the cutoffs in the constructor, provide a public get method which returns cached results if available and calls compute method if no cached data is available. This is what I have done now.

83 ↗

(On Diff #44353)

cl::opt<float> is used in a few places, so this is not new. I don't do much FP computation here. Letting the user pass a scaled up percentage value as an integer seems inconvenient to me (especially documenting how to use it). Alternatively, I can get the floats, scale it to an integer value and then use integer arithmetic elsewhere. Thoughts?

109 ↗

(On Diff #44353)

I don't see a good way of doing this without passing an iterator of the CountFrequencies map to the Accumulate method. Do you prefer that over the current implementation?

[davidxl]

tools/llvm-profdata/llvm-profdata.cpp

82 ↗

(On Diff #44577)

This is reasonable -- the benefit of allowing computing summary of different cutoffs with the same PS is minimal.

83 ↗

(On Diff #44577)

so -- for option part, using float is fine. What I am concerned is PorgramSummaryEntry has a float member. Eventually, I will need to write those entries to Indexed Profile header, so an integer representation there is better.

109 ↗

(On Diff #44577)

current accumuated count can be passed to the Accumator methods. I think vsk's suggestion makes the code slightly more readable.

[vsk]

tools/llvm-profdata/llvm-profdata.cpp

45 ↗

(On Diff #44577)

Fair enough. Maybe comments on the fields could help trim down the long-form comment?

109 ↗

(On Diff #44577)

You could use a lambda to capture the map iterator, or go with David's suggestion. I imagine both would be clean. I'm mostly concerned about avoiding the 'double-break' pattern, and would prefer less direct manipulation of iterator objects.

[eraman]

Address review comments.

tools/llvm-profdata/llvm-profdata.cpp

83 ↗

(On Diff #44577)

Ok, I've changed even the options to use ints. Main issue is whether the help message makes it clear what the numbers mean.

[eraman]

tools/llvm-profdata/llvm-profdata.cpp

45 ↗

(On Diff #44670)

Let me know if this looks better.

[davidxl]

test/tools/llvm-profdata/general.proftext

66 ↗

(On Diff #44670)

The default cutoffs only have 3 percentiles, how come the dump shows more?

78 ↗

(On Diff #44670)

Add a test with more than one explicit cutoffs?

tools/llvm-profdata/llvm-profdata.cpp

132 ↗

(On Diff #44670)

Return vector<..>&.

488 ↗

(On Diff #44670)

the scale is defined to be 1000000

[eraman]

test/tools/llvm-profdata/general.proftext

66 ↗

(On Diff #44681)

Those are not the default values. That's the value description string shown in the help message.

78 ↗

(On Diff #44681)

Good point. It helped me identify a bug - I've fixed that and added the test case.

[davidxl]

LTGM (after making getDetailedSummary() method return reference).

What is the plan to add similar support for Sample FDO?

[eraman]

In D16005#325251, @davidxl wrote:

LTGM (after making getDetailedSummary() method return reference).

I had addressed it in my last revision.

What is the plan to add similar support for Sample FDO?

I assume we want to treat line numbers as blocks for this purpose. I'll work on it.

[eraman]

Vedant, does this look good to you?

[vsk]

Lgtm, thanks.

tools/llvm-profdata/llvm-profdata.cpp

45 ↗

(On Diff #44670)

Looks great!

llvm/trunk/test/tools/llvm-profdata/general.proftext

 # SOMEFUNCS: Functions shown: 3
 
 # RUN: llvm-profdata show %t.profdata | FileCheck %s -check-prefix=SUMMARY
 # SUMMARY-NOT: Counters:
 # SUMMARY-NOT: Functions shown:
 # SUMMARY: Total functions: 4
 # SUMMARY: Maximum function count: 2305843009213693952
 # SUMMARY: Maximum internal block count: 1152921504606846976
+
+# RUN: llvm-profdata show --detailed-summary %t.profdata | FileCheck %s -check-prefix=DETAILED-SUMMARY
+# DETAILED-SUMMARY: Detailed summary:
+# DETAILED-SUMMARY: Total number of blocks: 6
+# DETAILED-SUMMARY: Total count: 2233785415175766016
+# DETAILED-SUMMARY: 3 blocks with count >= 288230376151711744 account for 80 percentage of the total counts
+# DETAILED-SUMMARY: 3 blocks with count >= 288230376151711744 account for 90 percentage of the total counts
+# DETAILED-SUMMARY: 4 blocks with count >= 144115188075855872 account for 95 percentage of the total counts.
+# DETAILED-SUMMARY: 5 blocks with count >= 72057594037927936 account for 99 percentage of the total counts.
+# DETAILED-SUMMARY: 5 blocks with count >= 72057594037927936 account for 99.9 percentage of the total counts.
+# DETAILED-SUMMARY: 5 blocks with count >= 72057594037927936 account for 99.99 percentage of the total counts.
+# DETAILED-SUMMARY: 5 blocks with count >= 72057594037927936 account for 99.999 percentage of the total counts.
+
+# RUN: llvm-profdata show --detailed-summary --detailed-summary-cutoffs=600000 %t.profdata | FileCheck %s -check-prefix=DETAILED-SUMMARY-2
+# DETAILED-SUMMARY-2: 2 blocks with count >= 576460752303423488 account for 60 percentage of the total counts.
+#
+# RUN: llvm-profdata show --detailed-summary --detailed-summary-cutoffs=600000,900000,999999 %t.profdata | FileCheck %s -check-prefix=DETAILED-SUMMARY-3
+# DETAILED-SUMMARY-3: 2 blocks with count >= 576460752303423488 account for 60 percentage of the total counts.
+# DETAILED-SUMMARY-3: 3 blocks with count >= 288230376151711744 account for 90 percentage of the total counts
+# DETAILED-SUMMARY-3: 5 blocks with count >= 72057594037927936 account for 99.9999 percentage of the total counts.

llvm/trunk/tools/llvm-profdata/llvm-profdata.cpp

 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <tuple>
 
 using namespace llvm;
 
 enum ProfileFormat { PF_None = 0, PF_Text, PF_Binary, PF_GCC };
 
+///// Profile summary computation ////
+// The 'show' command displays richer summary of the profile data. The profile
+// summary is one or more (Cutoff, MinBlockCount, NumBlocks) triplets. Given a
+// target execution count percentile, we compute the minimum number of blocks
+// needed to reach this target and the minimum execution count of these blocks.
+struct ProfileSummaryEntry {
+  uint32_t Cutoff;        //< The required percentile of total execution count.
+  uint64_t MinBlockCount; //< The minimum execution count for this percentile.
+  uint64_t NumBlocks;     //< Number of blocks >= the minumum execution count.
+};
+
+class ProfileSummary {
+  // We keep track of the number of times a count appears in the profile and
+  // keep the map sorted in the descending order of counts.
+  std::map<uint64_t, uint32_t, std::greater<uint64_t>> CountFrequencies;
+  std::vector<ProfileSummaryEntry> DetailedSummary;
+  std::vector<uint32_t> DetailedSummaryCutoffs;
+  // Sum of all counts.
+  uint64_t TotalCount;
+  uint64_t MaxBlockCount, MaxFunctionCount;
+  uint32_t NumBlocks, NumFunctions;
+  void addCount(uint64_t Count);
+  void computeDetailedSummary();
+
+public:
+  static const int Scale = 1000000;
+  ProfileSummary(std::vector<uint32_t> Cutoffs)
+      : DetailedSummaryCutoffs(Cutoffs), TotalCount(0), MaxBlockCount(0),
+        MaxFunctionCount(0), NumBlocks(0), NumFunctions(0) {}
+  void addRecord(const InstrProfRecord &);
+  std::vector<ProfileSummaryEntry> &getDetailedSummary();
+  uint32_t getNumBlocks() { return NumBlocks; }
+  uint64_t getTotalCount() { return TotalCount; }
+  uint32_t getNumFunctions() { return NumFunctions; }
+  uint64_t getMaxFunctionCount() { return MaxFunctionCount; }
+  uint64_t getMaxBlockCount() { return MaxBlockCount; }
+};
+
+// This is called when a count is seen in the profile.
+void ProfileSummary::addCount(uint64_t Count) {
+  TotalCount += Count;
+  if (Count > MaxBlockCount)
+    MaxBlockCount = Count;
+  NumBlocks++;
+  CountFrequencies[Count]++;
+}
+
+void ProfileSummary::addRecord(const InstrProfRecord &R) {
+  NumFunctions++;
+  if (R.Counts[0] > MaxFunctionCount)
+    MaxFunctionCount = R.Counts[0];
+
+  for (size_t I = 1, E = R.Counts.size(); I < E; ++I)
+    addCount(R.Counts[I]);
+}
+
+// The argument to this method is a vector of cutoff percentages and the return
+// value is a vector of (Cutoff, MinBlockCount, NumBlocks) triplets.
+void ProfileSummary::computeDetailedSummary() {
+  if (DetailedSummaryCutoffs.empty())
+    return;
+  auto Iter = CountFrequencies.begin();
+  auto End = CountFrequencies.end();
+  std::sort(DetailedSummaryCutoffs.begin(), DetailedSummaryCutoffs.end());
+
+  uint32_t BlocksSeen = 0;
+  uint64_t CurrSum = 0, Count;
+
+  for (uint32_t Cutoff : DetailedSummaryCutoffs) {
+    assert(Cutoff <= 999999);
+    APInt Temp(128, TotalCount);
+    APInt N(128, Cutoff);
+    APInt D(128, ProfileSummary::Scale);
+    Temp *= N;
+    Temp = Temp.sdiv(D);
+    uint64_t DesiredCount = Temp.getZExtValue();
+    dbgs() << "Cutoff = " << Cutoff << "\n";
+    dbgs() << "DesiredCount = " << DesiredCount << "\n";
+    assert(DesiredCount <= TotalCount);
+    while (CurrSum < DesiredCount && Iter != End) {
+      Count = Iter->first;
+      uint32_t Freq = Iter->second;
+      CurrSum += (Count * Freq);
+      BlocksSeen += Freq;
+      Iter++;
+    }
+    assert(CurrSum >= DesiredCount);
+    ProfileSummaryEntry PSE = {Cutoff, Count, BlocksSeen};
+    DetailedSummary.push_back(PSE);
+  }
+  return;
+}
+
+std::vector<ProfileSummaryEntry> &ProfileSummary::getDetailedSummary() {
+  if (!DetailedSummaryCutoffs.empty() && DetailedSummary.empty())
+    computeDetailedSummary();
+  return DetailedSummary;
+}
+
 static void exitWithError(const Twine &Message, StringRef Whence = "",
                           StringRef Hint = "") {
   errs() << "error: ";
   if (!Whence.empty())
     errs() << Whence << ": ";
   errs() << Message << "\n";
   if (!Hint.empty())
     errs() << Hint << "\n";
if (ProfileKind == instr)
     mergeInstrProfile(WeightedInputs, OutputFilename, OutputFormat);
   else
     mergeSampleProfile(WeightedInputs, OutputFilename, OutputFormat);
 
   return 0;
 }
 
 static int showInstrProfile(std::string Filename, bool ShowCounts,
-                            bool ShowIndirectCallTargets, bool ShowAllFunctions,
-                            std::string ShowFunction, bool TextFormat,
-                            raw_fd_ostream &OS) {
+                            bool ShowIndirectCallTargets,
+                            bool ShowDetailedSummary,
+                            std::vector<uint32_t> DetailedSummaryCutoffs,
+                            bool ShowAllFunctions, std::string ShowFunction,
+                            bool TextFormat, raw_fd_ostream &OS) {
   auto ReaderOrErr = InstrProfReader::create(Filename);
+  std::vector<uint32_t> Cutoffs(DetailedSummaryCutoffs);
+  if (ShowDetailedSummary && DetailedSummaryCutoffs.empty()) {
+    Cutoffs = {800000, 900000, 950000, 990000, 999000, 999900, 999990};
+  }
+  ProfileSummary PS(Cutoffs);
   if (std::error_code EC = ReaderOrErr.getError())
     exitWithErrorCode(EC, Filename);
 
   auto Reader = std::move(ReaderOrErr.get());
-  uint64_t MaxFunctionCount = 0, MaxBlockCount = 0;
-  size_t ShownFunctions = 0, TotalFunctions = 0;
+  size_t ShownFunctions = 0;
   for (const auto &Func : *Reader) {
     bool Show =
         ShowAllFunctions || (!ShowFunction.empty() &&
                              Func.Name.find(ShowFunction) != Func.Name.npos);
 
     bool doTextFormatDump = (Show && ShowCounts && TextFormat);
 
     if (doTextFormatDump) {
       InstrProfSymtab &Symtab = Reader->getSymtab();
       InstrProfWriter::writeRecordInText(Func, Symtab, OS);
       continue;
     }
 
-    ++TotalFunctions;
     assert(Func.Counts.size() > 0 && "function missing entry counter");
-    if (Func.Counts[0] > MaxFunctionCount)
-      MaxFunctionCount = Func.Counts[0];
-
-    for (size_t I = 1, E = Func.Counts.size(); I < E; ++I) {
-      if (Func.Counts[I] > MaxBlockCount)
-        MaxBlockCount = Func.Counts[I];
-    }
+    PS.addRecord(Func);
 
     if (Show) {
 
       if (!ShownFunctions)
         OS << "Counters:\n";
 
       ++ShownFunctions;
 
static int showInstrProfile(std::string Filename, bool ShowCounts,
   if (Reader->hasError())
     exitWithErrorCode(Reader->getError(), Filename);
 
   if (ShowCounts && TextFormat)
     return 0;
 
   if (ShowAllFunctions || !ShowFunction.empty())
     OS << "Functions shown: " << ShownFunctions << "\n";
-  OS << "Total functions: " << TotalFunctions << "\n";
-  OS << "Maximum function count: " << MaxFunctionCount << "\n";
-  OS << "Maximum internal block count: " << MaxBlockCount << "\n";
+  OS << "Total functions: " << PS.getNumFunctions() << "\n";
+  OS << "Maximum function count: " << PS.getMaxFunctionCount() << "\n";
+  OS << "Maximum internal block count: " << PS.getMaxBlockCount() << "\n";
+
+  if (ShowDetailedSummary) {
+    OS << "Detailed summary:\n";
+    OS << "Total number of blocks: " << PS.getNumBlocks() << "\n";
+    OS << "Total count: " << PS.getTotalCount() << "\n";
+    for (auto Entry : PS.getDetailedSummary()) {
+      OS << Entry.NumBlocks << " blocks with count >= " << Entry.MinBlockCount
+         << " account for "
+         << format("%0.6g", (float)Entry.Cutoff / ProfileSummary::Scale * 100)
+         << " percentage of the total counts.\n";
+    }
+  }
   return 0;
 }
 
 static int showSampleProfile(std::string Filename, bool ShowCounts,
                              bool ShowAllFunctions, std::string ShowFunction,
                              raw_fd_ostream &OS) {
   using namespace sampleprof;
   auto ReaderOrErr = SampleProfileReader::create(Filename, getGlobalContext());
static int show_main(int argc, const char *argv[]) {
   cl::opt<bool> ShowCounts("counts", cl::init(false),
                            cl::desc("Show counter values for shown functions"));
   cl::opt<bool> TextFormat(
       "text", cl::init(false),
       cl::desc("Show instr profile data in text dump format"));
   cl::opt<bool> ShowIndirectCallTargets(
       "ic-targets", cl::init(false),
       cl::desc("Show indirect call site target values for shown functions"));
+  cl::opt<bool> ShowDetailedSummary("detailed-summary", cl::init(false),
+                                    cl::desc("Show detailed profile summary"));
+  cl::list<uint32_t> DetailedSummaryCutoffs(
+      cl::CommaSeparated, "detailed-summary-cutoffs",
+      cl::desc(
+          "Cutoff percentages (times 10000) for generating detailed summary"),
+      cl::value_desc("800000,901000,999999"));
   cl::opt<bool> ShowAllFunctions("all-functions", cl::init(false),
                                  cl::desc("Details for every function"));
   cl::opt<std::string> ShowFunction("function",
                                     cl::desc("Details for matching functions"));
 
   cl::opt<std::string> OutputFilename("output", cl::value_desc("output"),
                                       cl::init("-"), cl::desc("Output file"));
   cl::alias OutputFilenameA("o", cl::desc("Alias for --output"),
static int show_main(int argc, const char *argv[]) {
   std::error_code EC;
   raw_fd_ostream OS(OutputFilename.data(), EC, sys::fs::F_Text);
   if (EC)
     exitWithErrorCode(EC, OutputFilename);
 
   if (ShowAllFunctions && !ShowFunction.empty())
     errs() << "warning: -function argument ignored: showing all functions\n";
 
+  std::vector<uint32_t> Cutoffs(DetailedSummaryCutoffs.begin(),
+                                DetailedSummaryCutoffs.end());
   if (ProfileKind == instr)
     return showInstrProfile(Filename, ShowCounts, ShowIndirectCallTargets,
+                            ShowDetailedSummary, DetailedSummaryCutoffs,
                             ShowAllFunctions, ShowFunction, TextFormat, OS);
   else
     return showSampleProfile(Filename, ShowCounts, ShowAllFunctions,
                              ShowFunction, OS);
 }
 
 int main(int argc, const char *argv[]) {
   // Print a stack trace if we signal out.