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/Debug.h"
  14 #include "llvm/Support/FileSystem.h"
  15 #include "llvm/Support/Format.h"
  16 #include "llvm/Support/FormatVariadic.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   OS << "\nRanges:\n";
 169   uint64_t PrevValue = 0;
 170   for (unsigned I = 0; I < sizeof(Range) / sizeof(Range[0]); ++I) {
 171     const uint64_t Value = Range[I];
 172     OS << "  ";
 173     printValue(Value, 'o', /*ResetColor=*/true);
 174     OS << " : (" << PrevValue << ", " << Value << "]\n";
 175     PrevValue = Value;
 176   }
 177   if (opts::HeatmapPrintMappings) {
 178     OS << "\nSections:\n";
 179     unsigned SectionIdx = 0;
 180     for (auto TxtSeg : TextSections) {
 181       const char Upper = static_cast<char>('A' + ((SectionIdx++) % 26));
 182       const char Lower = static_cast<char>(std::tolower(Upper));
 183       OS << formatv("  {0}/{1} : {2,-10} ", Lower, Upper, TxtSeg.Name);
 184       if (MaxAddress > 0xffffffff)
 185         OS << format("0x%016" PRIx64, TxtSeg.BeginAddress) << "-"
 186            << format("0x%016" PRIx64, TxtSeg.EndAddress) << "\n";
 187       else
 188         OS << format("0x%08" PRIx64, TxtSeg.BeginAddress) << "-"
 189            << format("0x%08" PRIx64, TxtSeg.EndAddress) << "\n";
 190     }
 191     OS << "\n";
 192   }
 193
 194   // Pos - character position from right in hex form.
 195   auto printHeader = [&](unsigned Pos) {
 196     OS << "            ";
 197     if (MaxAddress > 0xffffffff)
 198       OS << "        ";
 199     unsigned PrevValue = unsigned(-1);
 200     for (unsigned I = 0; I < BytesPerLine; I += BucketSize) {
 201       const unsigned Value = (I & ((1 << Pos * 4) - 1)) >> (Pos - 1) * 4;
 202       if (Value != PrevValue) {
 203         OS << Twine::utohexstr(Value);
 204         PrevValue = Value;
 205       } else {
 206         OS << ' ';
 207       }
 208     }
 209     OS << '\n';
 210   };
 211   for (unsigned I = 5; I > 0; --I)
 212     printHeader(I);
 213
 214   auto SectionStart = TextSections.begin();
 215   uint64_t PrevAddress = 0;
 216   for (auto MI = Map.begin(), ME = Map.end(); MI != ME; ++MI) {
 217     const std::pair<const uint64_t, uint64_t> &Entry = *MI;
 218     uint64_t Address = Entry.first * BucketSize;
 219     char Character = 'o';
 220
 221     // Check if address is in the current or any later section.
 222     auto Section = std::find_if(
 223         SectionStart, TextSections.end(), [&](const SectionNameAndRange &S) {
 224           return Address >= S.BeginAddress && Address < S.EndAddress;
 225         });
 226     if (Section != TextSections.end()) {
 227       // Shift the section forward (if SectionStart is different from Section).
 228       // This works, because TextSections is sorted by start address.
 229       SectionStart = Section;
 230       Character = 'a' + ((Section - TextSections.begin()) % 26);
 231     }
 232
 233     if (PrevAddress)
 234       fillRange(PrevAddress, Address);
 235     else
 236       startLine(Address);
 237
 238     printValue(Entry.second, Character, /*ResetColor=*/false);
 239
 240     PrevAddress = Address;
 241   }
 242
 243   if (PrevAddress) {
 244     changeColor(DefaultColor);
 245     finishLine(PrevAddress);
 246   }
 247 }
 248
 249 void Heatmap::printCDF(StringRef FileName) const {
 250   std::error_code EC;
 251   raw_fd_ostream OS(FileName, EC, sys::fs::OpenFlags::OF_None);
 252   if (EC) {
 253     errs() << "error opening output file: " << EC.message() << '\n';
 254     exit(1);
 255   }
 256   printCDF(OS);
 257 }
 258
 259 void Heatmap::printCDF(raw_ostream &OS) const {
 260   uint64_t NumTotalCounts = 0;
 261   std::vector<uint64_t> Counts;
 262
 263   for (const std::pair<const uint64_t, uint64_t> &KV : Map) {
 264     Counts.push_back(KV.second);
 265     NumTotalCounts += KV.second;
 266   }
 267
 268   llvm::sort(Counts, std::greater<uint64_t>());
 269
 270   double RatioLeftInKB = (1.0 * BucketSize) / 1024;
 271   assert(NumTotalCounts > 0 &&
 272          "total number of heatmap buckets should be greater than 0");
 273   double RatioRightInPercent = 100.0 / NumTotalCounts;
 274   uint64_t RunningCount = 0;
 275
 276   OS << "Bucket counts, Size (KB), CDF (%)\n";
 277   for (uint64_t I = 0; I < Counts.size(); I++) {
 278     RunningCount += Counts[I];
 279     OS << format("%llu", (I + 1)) << ", "
 280        << format("%.4f", RatioLeftInKB * (I + 1)) << ", "
 281        << format("%.4f", RatioRightInPercent * (RunningCount)) << "\n";
 282   }
 283
 284   Counts.clear();
 285 }
 286
 287 void Heatmap::printSectionHotness(StringRef FileName) const {
 288   std::error_code EC;
 289   raw_fd_ostream OS(FileName, EC, sys::fs::OpenFlags::OF_None);
 290   if (EC) {
 291     errs() << "error opening output file: " << EC.message() << '\n';
 292     exit(1);
 293   }
 294   printSectionHotness(OS);
 295 }
 296
 297 void Heatmap::printSectionHotness(raw_ostream &OS) const {
 298   uint64_t NumTotalCounts = 0;
 299   StringMap<uint64_t> SectionHotness;
 300   unsigned TextSectionIndex = 0;
 301
 302   if (TextSections.empty())
 303     return;
 304
 305   uint64_t UnmappedHotness = 0;
 306   auto RecordUnmappedBucket = [&](uint64_t Address, uint64_t Frequency) {
 307     errs() << "Couldn't map the address bucket [0x" << Twine::utohexstr(Address)
 308            << ", 0x" << Twine::utohexstr(Address + BucketSize)
 309            << "] containing " << Frequency
 310            << " samples to a text section in the binary.";
 311     UnmappedHotness += Frequency;
 312   };
 313
 314   for (const std::pair<const uint64_t, uint64_t> &KV : Map) {
 315     NumTotalCounts += KV.second;
 316     // We map an address bucket to the first section (lowest address)
 317     // overlapping with that bucket.
 318     auto Address = KV.first * BucketSize;
 319     while (TextSectionIndex < TextSections.size() &&
 320            Address >= TextSections[TextSectionIndex].EndAddress)
 321       TextSectionIndex++;
 322     if (TextSectionIndex >= TextSections.size() ||
 323         Address + BucketSize < TextSections[TextSectionIndex].BeginAddress) {
 324       RecordUnmappedBucket(Address, KV.second);
 325       continue;
 326     }
 327     SectionHotness[TextSections[TextSectionIndex].Name] += KV.second;
 328   }
 329
 330   assert(NumTotalCounts > 0 &&
 331          "total number of heatmap buckets should be greater than 0");
 332
 333   OS << "Section Name, Begin Address, End Address, Percentage Hotness\n";
 334   for (auto &TextSection : TextSections) {
 335     OS << TextSection.Name << ", 0x"
 336        << Twine::utohexstr(TextSection.BeginAddress) << ", 0x"
 337        << Twine::utohexstr(TextSection.EndAddress) << ", "
 338        << format("%.4f",
 339                  100.0 * SectionHotness[TextSection.Name] / NumTotalCounts)
 340        << "\n";
 341   }
 342   if (UnmappedHotness > 0)
 343     OS << "[unmapped], 0x0, 0x0, "
 344        << format("%.4f", 100.0 * UnmappedHotness / NumTotalCounts) << "\n";
 345 }
 346 } // namespace bolt
 347 } // namespace llvm