bolt/lib/Profile/Heatmap.cpp

   1 //===- bolt/Profile/Heatmap.cpp -------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "bolt/Profile/Heatmap.h"
  10 #include "bolt/Utils/CommandLineOpts.h"
  11 #include "llvm/ADT/StringMap.h"
  12 #include "llvm/ADT/Twine.h"
  13 #include "llvm/Support/CommandLine.h"
  14 #include "llvm/Support/Debug.h"
  15 #include "llvm/Support/FileSystem.h"
  16 #include "llvm/Support/Format.h"
  17 #include "llvm/Support/MathExtras.h"
  18 #include "llvm/Support/raw_ostream.h"
  19 #include <algorithm>
  20 #include <cctype>
  21 #include <cmath>
  22 #include <vector>
  23
  24 #define DEBUG_TYPE "bolt-heatmap"
  25
  26 using namespace llvm;
  27
  28 namespace llvm {
  29 namespace bolt {
  30
  31 void Heatmap::registerAddressRange(uint64_t StartAddress, uint64_t EndAddress,
  32                                    uint64_t Count) {
  33   if (ignoreAddress(StartAddress)) {
  34     ++NumSkippedRanges;
  35     return;
  36   }
  37
  38   if (StartAddress > EndAddress || EndAddress - StartAddress > 64 * 1024) {
  39     LLVM_DEBUG(dbgs() << "invalid range : 0x" << Twine::utohexstr(StartAddress)
  40                       << " -> 0x" << Twine::utohexstr(EndAddress) << '\n');
  41     ++NumSkippedRanges;
  42     return;
  43   }
  44
  45   for (uint64_t Bucket = StartAddress / BucketSize;
  46        Bucket <= EndAddress / BucketSize; ++Bucket)
  47     Map[Bucket] += Count;
  48 }
  49
  50 void Heatmap::print(StringRef FileName) const {
  51   std::error_code EC;
  52   raw_fd_ostream OS(FileName, EC, sys::fs::OpenFlags::OF_None);
  53   if (EC) {
  54     errs() << "error opening output file: " << EC.message() << '\n';
  55     exit(1);
  56   }
  57   print(OS);
  58 }
  59
  60 void Heatmap::print(raw_ostream &OS) const {
  61   const char FillChar = '.';
  62
  63   const auto DefaultColor = raw_ostream::WHITE;
  64   auto changeColor = [&](raw_ostream::Colors Color) -> void {
  65     static auto CurrentColor = raw_ostream::BLACK;
  66     if (CurrentColor == Color)
  67       return;
  68     OS.changeColor(Color);
  69     CurrentColor = Color;
  70   };
  71
  72   const uint64_t BytesPerLine = opts::BucketsPerLine * BucketSize;
  73
  74   // Calculate the max value for scaling.
  75   uint64_t MaxValue = 0;
  76   for (const std::pair<const uint64_t, uint64_t> &Entry : Map)
  77     MaxValue = std::max<uint64_t>(MaxValue, Entry.second);
  78
  79   // Print start of the line and fill it with an empty space right before
  80   // the Address.
  81   auto startLine = [&](uint64_t Address, bool Empty = false) {
  82     changeColor(DefaultColor);
  83     const uint64_t LineAddress = Address / BytesPerLine * BytesPerLine;
  84
  85     if (MaxAddress > 0xffffffff)
  86       OS << format("0x%016" PRIx64 ": ", LineAddress);
  87     else
  88       OS << format("0x%08" PRIx64 ": ", LineAddress);
  89
  90     if (Empty)
  91       Address = LineAddress + BytesPerLine;
  92     for (uint64_t Fill = LineAddress; Fill < Address; Fill += BucketSize)
  93       OS << FillChar;
  94   };
  95
  96   // Finish line after \p Address was printed.
  97   auto finishLine = [&](uint64_t Address) {
  98     const uint64_t End = alignTo(Address + 1, BytesPerLine);
  99     for (uint64_t Fill = Address + BucketSize; Fill < End; Fill += BucketSize)
 100       OS << FillChar;
 101     OS << '\n';
 102   };
 103
 104   // Fill empty space in (Start, End) range.
 105   auto fillRange = [&](uint64_t Start, uint64_t End) {
 106     if ((Start / BytesPerLine) == (End / BytesPerLine)) {
 107       for (uint64_t Fill = Start + BucketSize; Fill < End; Fill += BucketSize) {
 108         changeColor(DefaultColor);
 109         OS << FillChar;
 110       }
 111       return;
 112     }
 113
 114     changeColor(DefaultColor);
 115     finishLine(Start);
 116     Start = alignTo(Start, BytesPerLine);
 117
 118     uint64_t NumEmptyLines = (End - Start) / BytesPerLine;
 119
 120     if (NumEmptyLines > 32) {
 121       OS << '\n';
 122     } else {
 123       while (NumEmptyLines--) {
 124         startLine(Start, /*Empty=*/true);
 125         OS << '\n';
 126         Start += BytesPerLine;
 127       }
 128     }
 129
 130     startLine(End);
 131   };
 132
 133   static raw_ostream::Colors Colors[] = {
 134       raw_ostream::WHITE, raw_ostream::WHITE,  raw_ostream::CYAN,
 135       raw_ostream::GREEN, raw_ostream::YELLOW, raw_ostream::RED};
 136   constexpr size_t NumRanges = sizeof(Colors) / sizeof(Colors[0]);
 137
 138   uint64_t Range[NumRanges];
 139   for (uint64_t I = 0; I < NumRanges; ++I)
 140     Range[I] = std::max(I + 1, (uint64_t)std::pow((double)MaxValue,
 141                                                   (double)(I + 1) / NumRanges));
 142   Range[NumRanges - 1] = std::max((uint64_t)NumRanges, MaxValue);
 143
 144   // Print scaled value
 145   auto printValue = [&](uint64_t Value, char Character, bool ResetColor) {
 146     assert(Value && "should only print positive values");
 147     for (unsigned I = 0; I < sizeof(Range) / sizeof(Range[0]); ++I) {
 148       if (Value <= Range[I]) {
 149         changeColor(Colors[I]);
 150         break;
 151       }
 152     }
 153     if (Value <= Range[0])
 154       OS << static_cast<char>(std::tolower(Character));
 155     else
 156       OS << static_cast<char>(std::toupper(Character));
 157
 158     if (ResetColor)
 159       changeColor(DefaultColor);
 160   };
 161
 162   // Print against black background
 163   OS.changeColor(raw_ostream::BLACK, /*Bold=*/false, /*Background=*/true);
 164   changeColor(DefaultColor);
 165
 166   // Print map legend
 167   OS << "Legend:\n";
 168   uint64_t PrevValue = 0;
 169   for (unsigned I = 0; I < sizeof(Range) / sizeof(Range[0]); ++I) {
 170     const uint64_t Value = Range[I];
 171     OS << "  ";
 172     printValue(Value, 'o', /*ResetColor=*/true);
 173     OS << " : (" << PrevValue << ", " << Value << "]\n";
 174     PrevValue = Value;
 175   }
 176
 177   // Pos - character position from right in hex form.
 178   auto printHeader = [&](unsigned Pos) {
 179     OS << "            ";
 180     if (MaxAddress > 0xffffffff)
 181       OS << "        ";
 182     unsigned PrevValue = unsigned(-1);
 183     for (unsigned I = 0; I < BytesPerLine; I += BucketSize) {
 184       const unsigned Value = (I & ((1 << Pos * 4) - 1)) >> (Pos - 1) * 4;
 185       if (Value != PrevValue) {
 186         OS << Twine::utohexstr(Value);
 187         PrevValue = Value;
 188       } else {
 189         OS << ' ';
 190       }
 191     }
 192     OS << '\n';
 193   };
 194   for (unsigned I = 5; I > 0; --I)
 195     printHeader(I);
 196
 197   auto SectionStart = TextSections.begin();
 198   uint64_t PrevAddress = 0;
 199   for (auto MI = Map.begin(), ME = Map.end(); MI != ME; ++MI) {
 200     const std::pair<const uint64_t, uint64_t> &Entry = *MI;
 201     uint64_t Address = Entry.first * BucketSize;
 202     char Character = 'o';
 203
 204     // Check if address is in the current or any later section.
 205     auto Section = std::find_if(
 206         SectionStart, TextSections.end(), [&](const SectionNameAndRange &S) {
 207           return Address >= S.BeginAddress && Address < S.EndAddress;
 208         });
 209     if (Section != TextSections.end()) {
 210       // Shift the section forward (if SectionStart is different from Section).
 211       // This works, because TextSections is sorted by start address.
 212       SectionStart = Section;
 213       Character = 'a' + ((Section - TextSections.begin()) % 26);
 214     }
 215
 216     if (PrevAddress)
 217       fillRange(PrevAddress, Address);
 218     else
 219       startLine(Address);
 220
 221     printValue(Entry.second, Character, /*ResetColor=*/false);
 222
 223     PrevAddress = Address;
 224   }
 225
 226   if (PrevAddress) {
 227     changeColor(DefaultColor);
 228     finishLine(PrevAddress);
 229   }
 230 }
 231
 232 void Heatmap::printCDF(StringRef FileName) const {
 233   std::error_code EC;
 234   raw_fd_ostream OS(FileName, EC, sys::fs::OpenFlags::OF_None);
 235   if (EC) {
 236     errs() << "error opening output file: " << EC.message() << '\n';
 237     exit(1);
 238   }
 239   printCDF(OS);
 240 }
 241
 242 void Heatmap::printCDF(raw_ostream &OS) const {
 243   uint64_t NumTotalCounts = 0;
 244   std::vector<uint64_t> Counts;
 245
 246   for (const std::pair<const uint64_t, uint64_t> &KV : Map) {
 247     Counts.push_back(KV.second);
 248     NumTotalCounts += KV.second;
 249   }
 250
 251   llvm::sort(Counts, std::greater<uint64_t>());
 252
 253   double RatioLeftInKB = (1.0 * BucketSize) / 1024;
 254   assert(NumTotalCounts > 0 &&
 255          "total number of heatmap buckets should be greater than 0");
 256   double RatioRightInPercent = 100.0 / NumTotalCounts;
 257   uint64_t RunningCount = 0;
 258
 259   OS << "Bucket counts, Size (KB), CDF (%)\n";
 260   for (uint64_t I = 0; I < Counts.size(); I++) {
 261     RunningCount += Counts[I];
 262     OS << format("%llu", (I + 1)) << ", "
 263        << format("%.4f", RatioLeftInKB * (I + 1)) << ", "
 264        << format("%.4f", RatioRightInPercent * (RunningCount)) << "\n";
 265   }
 266
 267   Counts.clear();
 268 }
 269
 270 void Heatmap::printSectionHotness(StringRef FileName) const {
 271   std::error_code EC;
 272   raw_fd_ostream OS(FileName, EC, sys::fs::OpenFlags::OF_None);
 273   if (EC) {
 274     errs() << "error opening output file: " << EC.message() << '\n';
 275     exit(1);
 276   }
 277   printSectionHotness(OS);
 278 }
 279
 280 void Heatmap::printSectionHotness(raw_ostream &OS) const {
 281   uint64_t NumTotalCounts = 0;
 282   StringMap<uint64_t> SectionHotness;
 283   unsigned TextSectionIndex = 0;
 284
 285   if (TextSections.empty())
 286     return;
 287
 288   uint64_t UnmappedHotness = 0;
 289   auto RecordUnmappedBucket = [&](uint64_t Address, uint64_t Frequency) {
 290     errs() << "Couldn't map the address bucket [0x" << Twine::utohexstr(Address)
 291            << ", 0x" << Twine::utohexstr(Address + BucketSize)
 292            << "] containing " << Frequency
 293            << " samples to a text section in the binary.";
 294     UnmappedHotness += Frequency;
 295   };
 296
 297   for (const std::pair<const uint64_t, uint64_t> &KV : Map) {
 298     NumTotalCounts += KV.second;
 299     // We map an address bucket to the first section (lowest address)
 300     // overlapping with that bucket.
 301     auto Address = KV.first * BucketSize;
 302     while (TextSectionIndex < TextSections.size() &&
 303            Address >= TextSections[TextSectionIndex].EndAddress)
 304       TextSectionIndex++;
 305     if (TextSectionIndex >= TextSections.size() ||
 306         Address + BucketSize < TextSections[TextSectionIndex].BeginAddress) {
 307       RecordUnmappedBucket(Address, KV.second);
 308       continue;
 309     }
 310     SectionHotness[TextSections[TextSectionIndex].Name] += KV.second;
 311   }
 312
 313   assert(NumTotalCounts > 0 &&
 314          "total number of heatmap buckets should be greater than 0");
 315
 316   OS << "Section Name, Begin Address, End Address, Percentage Hotness\n";
 317   for (auto &TextSection : TextSections) {
 318     OS << TextSection.Name << ", 0x"
 319        << Twine::utohexstr(TextSection.BeginAddress) << ", 0x"
 320        << Twine::utohexstr(TextSection.EndAddress) << ", "
 321        << format("%.4f",
 322                  100.0 * SectionHotness[TextSection.Name] / NumTotalCounts)
 323        << "\n";
 324   }
 325   if (UnmappedHotness > 0)
 326     OS << "[unmapped], 0x0, 0x0, "
 327        << format("%.4f", 100.0 * UnmappedHotness / NumTotalCounts) << "\n";
 328 }
 329 } // namespace bolt
 330 } // namespace llvm