[ProfileData] Add new option to dump top N hottest functions

[davidxl]

Summary

The command line is:

llvm-profdata show --topn=<N>  <profile_data>

This is useful for user to do focused analysis. With top function names dumped, user can use option --counters --function=<FuncName> to dump counters of the specified function and do comparisons.

[vsk]

test/tools/llvm-profdata/c-general.test

13

Add --check-prefix=TOPN?

14

I think --topn and --all-functions should be mutually incompatible.

tools/llvm-profdata/llvm-profdata.cpp

528

Wdyt of using a std::priority_queue, s.t the function with the lowest count is always at the top? While adding records into the PQ, you'd do if PQ.size() > TopN: PQ.pop(). It wouldn't be functionally different, just less typing.

[davidxl]

test/tools/llvm-profdata/c-general.test

14

They are compatible. One use case is to dump them together into one file. User can first look at the top functions and examine the counter details for the function of interest.

[davidxl]

Addressed review feedback.

[vsk]

Lgtm with two nitpicks.

test/tools/llvm-profdata/c-general.test

14

Ah ok.

tools/llvm-profdata/llvm-profdata.cpp

508

The coding standards have an explicit rule against 'using namespace std', which is more stylistic than practical when applied to implementation files, but still important for consistency.

630

const auto &

[vsk]

Oh, the --topn flag also needs a short entry in docs/CommandGuide/llvm-profdata.rst.

[davidxl]

Added documentation.

test/tools/llvm-profdata/c-general.test

 REGENERATE: You need a checkout of clang with compiler-rt to generate the
 REGENERATE: binary file here.  These shell commands can be used to regenerate
 REGENERATE: it.
 REGENERATE:
 REGENERATE: $ SRC=path/to/llvm
 REGENERATE: $ CFE=$SRC/tools/clang
 REGENERATE: $ TESTDIR=$SRC/test/tools/llvm-profdata
 REGENERATE: $ CFE_TESTDIR=$CFE/test/Profile
 REGENERATE: $ clang -o a.out -fprofile-instr-generate $CFE_TESTDIR/c-general.c
 REGENERATE: $ LLVM_PROFILE_FILE=$TESTDIR/Inputs/c-general.profraw ./a.out
 
 RUN: llvm-profdata show %p/Inputs/c-general.profraw -o - | FileCheck %s
+RUN: llvm-profdata show %p/Inputs/c-general.profraw --topn=3 -o - | FileCheck %s
 RUN: llvm-profdata show %p/Inputs/c-general.profraw -o - --function=switches | FileCheck %s -check-prefix=SWITCHES -check-prefix=CHECK
 
 SWITCHES-LABEL: Counters:
 SWITCHES-NEXT:   switches:
 SWITCHES-NEXT:     Hash: 0x2618e4f23f2e8daa
 SWITCHES-NEXT:     Counters: 19
 SWITCHES-NEXT:     Function count: 1
 SWITCHES-LABEL: Functions shown: 1
 
 CHECK-LABEL: Total functions: 12
 CHECK-NEXT: Maximum function count: 1
 CHECK-NEXT: Maximum internal block count: 100
+TOPN: simple_loops, max count = 100
+TOPN-NEXT:  conditionals, max count = 100
+TOPN-NEXT:  early_exits, max count = 51
+

tools/llvm-profdata/llvm-profdata.cpp

   OS << "  Value sites histogram:\n\tNumTargets, SiteCount\n";
   for (unsigned I = 0; I < Stats.ValueSitesHistogram.size(); I++) {
     if (Stats.ValueSitesHistogram[I] > 0)
       OS << "\t" << I + 1 << ", " << Stats.ValueSitesHistogram[I] << "\n";
   }
 }
 
 static int showInstrProfile(const std::string &Filename, bool ShowCounts,
-                            bool ShowIndirectCallTargets, bool ShowMemOPSizes,
-                            bool ShowDetailedSummary,
+                            uint32_t TopN, bool ShowIndirectCallTargets,
+                            bool ShowMemOPSizes, bool ShowDetailedSummary,
                             std::vector<uint32_t> DetailedSummaryCutoffs,
                             bool ShowAllFunctions,
                             const std::string &ShowFunction, bool TextFormat,
                             raw_fd_ostream &OS) {
   auto ReaderOrErr = InstrProfReader::create(Filename);
   std::vector<uint32_t> Cutoffs = std::move(DetailedSummaryCutoffs);
   if (ShowDetailedSummary && Cutoffs.empty()) {
     Cutoffs = {800000, 900000, 950000, 990000, 999000, 999900, 999990};
   }
   InstrProfSummaryBuilder Builder(std::move(Cutoffs));
   if (Error E = ReaderOrErr.takeError())
     exitWithError(std::move(E), Filename);
 
   auto Reader = std::move(ReaderOrErr.get());
   bool IsIRInstr = Reader->isIRLevelProfile();
   size_t ShownFunctions = 0;
   int NumVPKind = IPVK_Last - IPVK_First + 1;
   std::vector<ValueSitesStats> VPStats(NumVPKind);
+
+  std::vector<std::pair<std::string, uint64_t>> HottestFuncs;
+  auto MinCmp = [](const std::pair<std::string, uint64_t> &v1,
+                   const std::pair<std::string, uint64_t> &v2) {
+    return v1.second > v2.second;
+  };
+  std::make_heap(HottestFuncs.begin(), HottestFuncs.end(), MinCmp);
+
   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.Name, Func.Hash, Func, Symtab,
                                          OS);
       continue;
     }
 
     assert(Func.Counts.size() > 0 && "function missing entry counter");
     Builder.addRecord(Func);
 
+    if (TopN) {
+      uint64_t FuncMax = 0;
+      for (size_t I = 0, E = Func.Counts.size(); I < E; ++I)
+        FuncMax = std::max(FuncMax, Func.Counts[I]);
+
+      if (HottestFuncs.size() == TopN) {
+        if (HottestFuncs.front().second < FuncMax) {
+          pop_heap(HottestFuncs.begin(), HottestFuncs.end(), MinCmp);
+          HottestFuncs.pop_back();
+          HottestFuncs.emplace_back(
+              std::make_pair(std::string(Func.Name), FuncMax));
+          push_heap(HottestFuncs.begin(), HottestFuncs.end(), MinCmp);
+        }
+      } else
+        HottestFuncs.emplace_back(
+            std::make_pair(std::string(Func.Name), FuncMax));
+    }
+
     if (Show) {
 
       if (!ShownFunctions)
         OS << "Counters:\n";
 
       ++ShownFunctions;
 
       OS << "  " << Func.Name << ":\n"

     return 0;
   std::unique_ptr<ProfileSummary> PS(Builder.getSummary());
   if (ShowAllFunctions || !ShowFunction.empty())
     OS << "Functions shown: " << ShownFunctions << "\n";
   OS << "Total functions: " << PS->getNumFunctions() << "\n";
   OS << "Maximum function count: " << PS->getMaxFunctionCount() << "\n";
   OS << "Maximum internal block count: " << PS->getMaxInternalCount() << "\n";
 
+  if (TopN) {
+    std::sort(HottestFuncs.begin(), HottestFuncs.end(), MinCmp);
+
+    OS << "Top " << TopN
+       << " functions with the largest internal block counts: \n";
+    for (auto hotfunc : HottestFuncs)
+      OS << "  " << hotfunc.first << ", max count = " << hotfunc.second << "\n";
+  }
+
   if (ShownFunctions && ShowIndirectCallTargets) {
     OS << "Statistics for indirect call sites profile:\n";
     showValueSitesStats(OS, IPVK_IndirectCallTarget,
                         VPStats[IPVK_IndirectCallTarget]);
   }
 
   if (ShownFunctions && ShowMemOPSizes) {
     OS << "Statistics for memory intrinsic calls sizes profile:\n";

   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"),
                             cl::aliasopt(OutputFilename));
   cl::opt<ProfileKinds> ProfileKind(
       cl::desc("Profile kind:"), cl::init(instr),
       cl::values(clEnumVal(instr, "Instrumentation profile (default)"),
                  clEnumVal(sample, "Sample profile")));
+  cl::opt<uint32_t> TopNFunctions(
+      "topn", cl::init(0),
+      cl::desc("Show the list of functions with the largest internal counts"));
 
   cl::ParseCommandLineOptions(argc, argv, "LLVM profile data summary\n");
 
   if (OutputFilename.empty())
     OutputFilename = "-";
 
   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,
-                            ShowMemOPSizes, ShowDetailedSummary,
-                            DetailedSummaryCutoffs, ShowAllFunctions,
-                            ShowFunction, TextFormat, OS);
+    return showInstrProfile(Filename, ShowCounts, TopNFunctions,
+                            ShowIndirectCallTargets, ShowMemOPSizes,
+                            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.
   sys::PrintStackTraceOnErrorSignal(argv[0]);