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/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(Address: 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(status: 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>(a: MaxValue, b: Entry.second);
81
82 // Print start of the line and fill it with an empty space right before
83 // 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(Fmt: "0x%016" PRIx64 ": ", Vals: LineAddress);
90 else
91 OS << format(Fmt: "0x%08" PRIx64 ": ", Vals: 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(Value: Address + 1, Align: 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(Value: Start, Align: 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(a: I + 1, b: (uint64_t)std::pow(x: (double)MaxValue,
144 y: (double)(I + 1) / NumRanges));
145 Range[NumRanges - 1] = std::max(a: (uint64_t)NumRanges, b: MaxValue);
146
147 // Print scaled value
148 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(c: Character));
158 else
159 OS << static_cast<char>(std::toupper(c: Character));
160
161 if (ResetColor)
162 changeColor(DefaultColor);
163 };
164
165 // Print against black background
166 OS.changeColor(Color: raw_ostream::BLACK, /*Bold=*/false, /*Background=*/BG: true);
167 changeColor(DefaultColor);
168
169 // Print map legend
170 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(c: Upper));
186 OS << formatv(Fmt: " {0}/{1} : {2,-10} ", Vals: Lower, Vals: Upper, Vals&: TxtSeg.Name);
187 if (MaxAddress > 0xffffffff)
188 OS << format(Fmt: "0x%016" PRIx64, Vals: TxtSeg.BeginAddress) << "-"
189 << format(Fmt: "0x%016" PRIx64, Vals: TxtSeg.EndAddress) << "\n";
190 else
191 OS << format(Fmt: "0x%08" PRIx64, Vals: TxtSeg.BeginAddress) << "-"
192 << format(Fmt: "0x%08" PRIx64, Vals: 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(Val: 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 first: SectionStart, last: TextSections.end(), pred: [&](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 else
239 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(status: 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(x: KV.second);
268 NumTotalCounts += KV.second;
269 }
270
271 llvm::sort(C&: Counts, Comp: 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(Fmt: "%llu", Vals: (I + 1)) << ", "
283 << format(Fmt: "%.4f", Vals: RatioLeftInKB * (I + 1)) << ", "
284 << format(Fmt: "%.4f", Vals: 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(status: 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(Val: Address) << ", 0x"
314 << Twine::utohexstr(Val: 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(Addr: 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 TextSections
345 if (!HotTextRange.empty())
346 Sections.emplace_back(args: SectionNameAndRange{.Name: HotTextName, .BeginAddress: HotStart, .EndAddress: 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(Fmt: "{0}, {1:x}, {2:x}, {3:f4}, {4:f4}, {5:f4}\n", Vals: Name, Vals: Begin,
363 Vals: End, Vals: 100. * Hotness, Vals: 100. * Utilization, Vals: PartitionScore);
364 }
365 if (UnmappedHotness > 0)
366 OS << formatv(Fmt: "[unmapped], 0x0, 0x0, {0:f4}, 0, 0\n",
367 Vals: 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 bolt
378} // namespace llvm
379

source code of bolt/lib/Profile/Heatmap.cpp