[BOLT] Report per-section hotness in bolt-heatmap.

[rahmanl]

Summary

This patch adds a new feature to bolt heatmap to print the hotness of each section in terms of the percentage of samples within that section.

Sample output generated for the clang binary:

Section Name, Begin Address, End Address, Percentage Hotness
.text, 0x1a7b9b0, 0x20a2cc0, 1.4709
.init, 0x20a2cc0, 0x20a2ce1, 0.0001
.fini, 0x20a2ce4, 0x20a2cf2, 0.0000
.text.unlikely, 0x20a2d00, 0x431990c, 0.3061
.text.hot, 0x4319910, 0x4bc6927, 97.2197
.text.startup, 0x4bc6930, 0x4c10c89, 0.0058
.plt, 0x4c10c90, 0x4c12010, 0.9974

[rahmanl]

Refactoring.

[rahmanl]

WIP.

[rahmanl]

Refactoring.

[rahmanl]

Cleanup.

[rafauler]

That's a nice functionality, thanks!

bolt/include/bolt/Profile/Heatmap.h

57–61

What happens if I want a heatmap that shows activity in addresses that are not mapped to a text section? (e.g. jitted code)

We need to support recording samples in unmapped regions as well.

bolt/lib/Profile/DataAggregator.cpp

114

Instead of using static, wrap it in an anonymous namespace (just the extend the one we already have in lines 132-137).

bolt/lib/Profile/Heatmap.cpp

255–258

271

276

This and the next comment are optional. Either do that or assert(). The intent is to avoid crashing if Address is greater than the last EndAddress (I know this doesn't happen, but it is an invariant that would be nice if made explicit via an assertion).

278

[rahmanl]

Add entry for unmapped regions.

[rahmanl]

bolt/include/bolt/Profile/Heatmap.h

57–61

Good idea. I removed this check and instead added a separate (unmapped) entry in the text section hotness data.

[rafauler]

LGTM

bolt/include/bolt/Core/BinaryContext.h

public:
   }
 
   /// Return section name containing the given \p Address.
   ErrorOr<StringRef> getSectionNameForAddress(uint64_t Address) const;
 
   /// Print all sections.
   void printSections(raw_ostream &OS) const;
 
+  /// Return a map from section names to the address range.
+  StringMap<std::pair<uint64_t, uint64_t>>
+  getSectionNameToAddressRangeMap() const;
+
   /// Return largest section containing the given \p Address.  These
   /// functions only work for allocatable sections, i.e. ones with non-zero
   /// addresses.
   ErrorOr<BinarySection &> getSectionForAddress(uint64_t Address);
   ErrorOr<const BinarySection &> getSectionForAddress(uint64_t Address) const {
     return const_cast<BinaryContext *>(this)->getSectionForAddress(Address);
   }
 

bolt/include/bolt/Profile/Heatmap.h

 //===- bolt/Profile/Heatmap.h -----------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef BOLT_PROFILE_HEATMAP_H
 #define BOLT_PROFILE_HEATMAP_H
 
+#include "bolt/Core/BinaryContext.h"
+#include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include <cstdint>
 #include <map>
 
 namespace llvm {
 class raw_ostream;
 
 namespace bolt {
 
+/// Struct representing a section name and its address range in the binary.
+struct SectionNameAndRange {
+  StringRef Name;
+  uint64_t BeginAddress;
+  uint64_t EndAddress;
+};
+
 class Heatmap {
   /// Number of bytes per entry in the heat map.
   size_t BucketSize;
 
   /// Minimum address that is considered to be valid.
   uint64_t MinAddress;
 
   /// Maximum address that is considered to be valid.
   uint64_t MaxAddress;
 
   /// Count invalid ranges.
   uint64_t NumSkippedRanges{0};
 
   /// Map buckets to the number of samples.
   std::map<uint64_t, uint64_t> Map;
 
+  /// Map section names to their address range.
+  const std::vector<SectionNameAndRange> TextSections;
+
 public:
   explicit Heatmap(uint64_t BucketSize = 4096, uint64_t MinAddress = 0,
-                   uint64_t MaxAddress = std::numeric_limits<uint64_t>::max())
-      : BucketSize(BucketSize), MinAddress(MinAddress),
-        MaxAddress(MaxAddress){};
+                   uint64_t MaxAddress = std::numeric_limits<uint64_t>::max(),
+                   std::vector<SectionNameAndRange> TextSections = {})
+      : BucketSize(BucketSize), MinAddress(MinAddress), MaxAddress(MaxAddress),
+        TextSections(TextSections) {}
 
   inline bool ignoreAddress(uint64_t Address) const {
-    return (Address > MaxAddress) || (Address < MinAddress);
+    return (Address > MaxAddress) || (Address < MinAddress) ||
+           (!TextSections.empty() &&
+            (Address > TextSections.back().EndAddress ||
+             Address < TextSections.front().BeginAddress));
   }
 
   /// Register a single sample at \p Address.
   void registerAddress(uint64_t Address) {
     if (!ignoreAddress(Address))
       ++Map[Address / BucketSize];
   }
 
   /// Register \p Count samples at [\p StartAddress, \p EndAddress ].
   void registerAddressRange(uint64_t StartAddress, uint64_t EndAddress,
                             uint64_t Count);
 
   /// Return the number of ranges that failed to register.
   uint64_t getNumInvalidRanges() const { return NumSkippedRanges; }
 
   void print(StringRef FileName) const;
 
   void print(raw_ostream &OS) const;
 
   void printCDF(StringRef FileName) const;
 
   void printCDF(raw_ostream &OS) const;
 
+  void printSectionHotness(StringRef Filename) const;
+
+  void printSectionHotness(raw_ostream &OS) const;
+
   size_t size() const { return Map.size(); }
 };
 
 } // namespace bolt
 } // namespace llvm
 
 #endif

bolt/lib/Core/BinaryContext.cpp

BinarySection &BinaryContext::registerSection(BinarySection *Section) {
   if (Section->isAllocatable() && Section->getAddress())
     AddressToSection.insert(std::make_pair(Section->getAddress(), Section));
   NameToSection.insert(
       std::make_pair(std::string(Section->getName()), Section));
   LLVM_DEBUG(dbgs() << "BOLT-DEBUG: registering " << *Section << "\n");
   return *Section;
 }
 
+StringMap<std::pair<uint64_t, uint64_t>>
+BinaryContext::getSectionNameToAddressRangeMap() const {
+  StringMap<std::pair<uint64_t, uint64_t>> M;
+  for (const auto &elem : AddressToSection) {
+    M[elem.second->getName()] =
+        std::make_pair(elem.second->getAddress(), elem.second->getEndAddress());
+  }
+  return M;
+}
+
 BinarySection &BinaryContext::registerSection(SectionRef Section) {
   return registerSection(new BinarySection(*this, Section));
 }
 
 BinarySection &
 BinaryContext::registerSection(StringRef SectionName,
                                const BinarySection &OriginalSection) {
   return registerSection(

bolt/lib/Profile/DataAggregator.cpp

 WriteAutoFDOData("autofdo",
   cl::desc("generate autofdo textual data instead of bolt data"),
   cl::init(false),
   cl::ZeroOrMore,
   cl::cat(AggregatorCategory));
 
 } // namespace opts
 
+static std::vector<SectionNameAndRange>
+getTextSections(const BinaryContext *BC) {
+  std::vector<SectionNameAndRange> sections;
+  for (BinarySection &Section : BC->sections()) {
+    if (!Section.isText())
+      continue;
+    if (Section.getSize() == 0)
+      continue;
+    sections.push_back(
+        {Section.getName(), Section.getAddress(), Section.getEndAddress()});
+  }
+  std::sort(sections.begin(), sections.end(),
+            [](const SectionNameAndRange &A, const SectionNameAndRange &B) {
+              return A.BeginAddress < B.BeginAddress;
+            });
+  return sections;
+}
+
 namespace {
 
 const char TimerGroupName[] = "aggregator";
 const char TimerGroupDesc[] = "Aggregator";
 
 }
 
 constexpr uint64_t DataAggregator::KernelBaseAddr;
std::error_code DataAggregator::printLBRHeatMap() {
   NamedRegionTimer T("parseBranch", "Parsing branch events", TimerGroupName,
                      TimerGroupDesc, opts::TimeAggregator);
 
   if (opts::LinuxKernelMode) {
     opts::HeatmapMaxAddress = 0xffffffffffffffff;
     opts::HeatmapMinAddress = KernelBaseAddr;
   }
   Heatmap HM(opts::HeatmapBlock, opts::HeatmapMinAddress,
-             opts::HeatmapMaxAddress);
+             opts::HeatmapMaxAddress, getTextSections(BC));
   uint64_t NumTotalSamples = 0;
 
   if (opts::BasicAggregation) {
     while (hasData()) {
       ErrorOr<PerfBasicSample> SampleRes = parseBasicSample();
       if (std::error_code EC = SampleRes.getError()) {
         if (EC == errc::no_such_process)
           continue;
if (!HM.size()) {
     exit(1);
   }
 
   HM.print(opts::OutputFilename);
   if (opts::OutputFilename == "-")
     HM.printCDF(opts::OutputFilename);
   else
     HM.printCDF(opts::OutputFilename + ".csv");
+  if (opts::OutputFilename == "-")
+    HM.printSectionHotness(opts::OutputFilename);
+  else
+    HM.printSectionHotness(opts::OutputFilename + "-section-hotness.csv");
 
   return std::error_code();
 }
 
 std::error_code DataAggregator::parseBranchEvents() {
   outs() << "PERF2BOLT: parse branch events...\n";
   NamedRegionTimer T("parseBranch", "Parsing branch events", TimerGroupName,
                      TimerGroupDesc, opts::TimeAggregator);

bolt/lib/Profile/Heatmap.cpp

for (uint64_t I = 0; I < Counts.size(); I++) {
     OS << format("%llu", (I + 1)) << ", "
        << format("%.4f", RatioLeftInKB * (I + 1)) << ", "
        << format("%.4f", RatioRightInPercent * (RunningCount)) << "\n";
   }
 
   Counts.clear();
 }
 
+void Heatmap::printSectionHotness(StringRef FileName) const {
+  if (TextSections.empty()) {
+    errs() << "No text sections captured from the binary.";
+    exit(1);
+  }
+  std::error_code EC;
+  raw_fd_ostream OS(FileName, EC, sys::fs::OpenFlags::OF_None);
+  if (EC) {
+    errs() << "error opening output file: " << EC.message() << '\n';
+    exit(1);
+  }
+  printSectionHotness(OS);
+}
+
+void Heatmap::printSectionHotness(raw_ostream &OS) const {
+  uint64_t NumTotalCounts = 0;
+  StringMap<uint64_t> SectionHotness;
+  int TextSectionIndex = 0;
+
+  for (const std::pair<const uint64_t, uint64_t> &KV : Map) {
+    // Take the middle of the bucket as the representative address.
+    auto Address = KV.first * BucketSize;
+    while (Address >= TextSections[TextSectionIndex].EndAddress)
+      TextSectionIndex++;
+    if (Address + BucketSize < TextSections[TextSectionIndex].BeginAddress) {
+      errs() << "Couldn't map the address bucket [0x"
+             << Twine::utohexstr(Address) << ", 0x"
+             << Twine::utohexstr(Address + BucketSize)
+             << "] to a text section in the binary.";
+      continue;
+    }
+    SectionHotness[TextSections[TextSectionIndex].Name] += KV.second;
+    NumTotalCounts += KV.second;
+  }
+
+  assert(NumTotalCounts > 0 &&
+         "total number of heatmap buckets should be greater than 0");
+
+  OS << "Section Name, Begin Address, End Address, Percentage Hotness\n";
+  for (auto &TextSection : TextSections) {
+    OS << TextSection.Name << ", 0x"
+       << Twine::utohexstr(TextSection.BeginAddress) << ", 0x"
+       << Twine::utohexstr(TextSection.EndAddress) << ", "
+       << format("%.4f",
+                 100.0 * SectionHotness[TextSection.Name] / NumTotalCounts)
+       << "\n";
+  }
+}
 } // namespace bolt
 } // namespace llvm