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