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

Add simple summary data such as MaxFunctionCount and MaxBlockCount here.

63

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

addCount(const InstrProfRecord &)

63

AddCount --> addCount

82

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

getProfileSummary

83

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

91

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

381–382

This should be moved to ProfileSummary

381–382

PS.addCount(Func);

382

Remove this

[vsk]

Thanks eraman! Comments inline --

tools/llvm-profdata/llvm-profdata.cpp

45

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

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

109

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

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

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

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

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

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

83

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

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

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

109

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

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

Let me know if this looks better.

[davidxl]

test/tools/llvm-profdata/general.proftext

66

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

78

Add a test with more than one explicit cutoffs?

tools/llvm-profdata/llvm-profdata.cpp

132

Return vector<..>&.

488

the scale is defined to be 1000000

[eraman]

test/tools/llvm-profdata/general.proftext

66

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

78

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

Looks great!

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=60 %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.

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
+// Cutoff (expressed as percentage in the range 0-100), we compute the smallest
+// Top-N counts such that their sum equals or exceeds Cutoff x (sum of all
+// counts). The N in the above Top-N is the NumBlocks of the triplet and the
+// smallest count in the Top-N is the MinBlockCount.
+struct ProfileSummaryEntry {
+  float Cutoff;
+  uint64_t MinBlockCount;
+  uint64_t NumBlocks;
+};
+
+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<float> DetailedSummaryCutoffs;
+  // Sum of all counts.
+  uint64_t TotalCount;
+  uint64_t MaxBlockCount, MaxFunctionCount;
+  uint32_t NumBlocks, NumFunctions;
+  void addCount(uint64_t Count);
+  void computeDetailedSummary();
+
+public:
+  ProfileSummary(std::vector<float> 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 = DetailedSummaryCutoffs.begin();
+  auto End = DetailedSummaryCutoffs.end();
+
+  std::sort(DetailedSummaryCutoffs.begin(), DetailedSummaryCutoffs.end());
+  uint32_t BlocksSeen = 0;
+  bool Done = false;
+  uint64_t CurrSum = 0;
+  // CountFrequencies is sorted in the descending order of keys (counts).
+  for (auto Entry : CountFrequencies) {
+    uint64_t Count = Entry.first;
+    uint32_t Freq = Entry.second;
+    BlocksSeen += Freq;
+    // CurrSum contains the sum of all counts we have seen so far.
+    CurrSum += (Count * Freq);
+    // *Iter is the desired Cutoff. We check if the current sum equals or
+    // exceeds Cutoff times total. We might have exceeded more than one cutoffs
+    // and hence we need the while loop.
+    while (CurrSum >= (*Iter) / 100 * TotalCount) {
+      ProfileSummaryEntry PSE = {*Iter, Count, BlocksSeen};
+      DetailedSummary.push_back(PSE);
+      Iter++;
+      if (Iter == End) {
+        Done = true;
+        break;
+      }
+    }
+    if (Done)
+      break;
+  }
+  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<float> DetailedSummaryCutoffs,
+                            bool ShowAllFunctions, std::string ShowFunction,
+                            bool TextFormat, raw_fd_ostream &OS) {
   auto ReaderOrErr = InstrProfReader::create(Filename);
+  std::vector<float> Cutoffs(DetailedSummaryCutoffs);
+  if (ShowDetailedSummary && DetailedSummaryCutoffs.empty()) {
+    Cutoffs = {80, 90, 95, 99, 99.9, 99.99, 99.999};
+  }
+  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", Entry.Cutoff)
+         << " 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<float> DetailedSummaryCutoffs(
+      "detailed-summary-cutoffs",
+      cl::desc("Cutoff percentages for generating detailed summary"),
+      cl::value_desc("80,90.1,99.99"));
   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<float> 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.