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

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