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 <cmath>
21 #include <vector>
22
23 #define DEBUG_TYPE "bolt-heatmap"
24
25 using namespace llvm;
26
27 namespace llvm {
28 namespace bolt {
29
registerAddressRange(uint64_t StartAddress,uint64_t EndAddress,uint64_t Count)30 void Heatmap::registerAddressRange(uint64_t StartAddress, uint64_t EndAddress,
31 uint64_t Count) {
32 if (ignoreAddress(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
print(StringRef FileName) const49 void 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(1);
55 }
56 print(OS);
57 }
58
print(raw_ostream & OS) const59 void 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>(MaxValue, 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("0x%016" PRIx64 ": ", LineAddress);
86 else
87 OS << format("0x%08" PRIx64 ": ", 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(Address + 1, 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(Start, 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(I + 1, (uint64_t)std::pow((double)MaxValue,
140 (double)(I + 1) / NumRanges));
141 Range[NumRanges - 1] = std::max((uint64_t)NumRanges, MaxValue);
142
143 // Print scaled value
144 auto printValue = [&](uint64_t Value, bool ResetColor = false) {
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 << 'o';
154 else
155 OS << 'O';
156
157 if (ResetColor)
158 changeColor(DefaultColor);
159 };
160
161 // Print against black background
162 OS.changeColor(raw_ostream::BLACK, /*Bold=*/false, /*Background=*/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, 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(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 uint64_t PrevAddress = 0;
197 for (auto MI = Map.begin(), ME = Map.end(); MI != ME; ++MI) {
198 const std::pair<const uint64_t, uint64_t> &Entry = *MI;
199 uint64_t Address = Entry.first * BucketSize;
200
201 if (PrevAddress)
202 fillRange(PrevAddress, Address);
203 else
204 startLine(Address);
205
206 printValue(Entry.second);
207
208 PrevAddress = Address;
209 }
210
211 if (PrevAddress) {
212 changeColor(DefaultColor);
213 finishLine(PrevAddress);
214 }
215 }
216
printCDF(StringRef FileName) const217 void Heatmap::printCDF(StringRef FileName) const {
218 std::error_code EC;
219 raw_fd_ostream OS(FileName, EC, sys::fs::OpenFlags::OF_None);
220 if (EC) {
221 errs() << "error opening output file: " << EC.message() << '\n';
222 exit(1);
223 }
224 printCDF(OS);
225 }
226
printCDF(raw_ostream & OS) const227 void Heatmap::printCDF(raw_ostream &OS) const {
228 uint64_t NumTotalCounts = 0;
229 std::vector<uint64_t> Counts;
230
231 for (const std::pair<const uint64_t, uint64_t> &KV : Map) {
232 Counts.push_back(KV.second);
233 NumTotalCounts += KV.second;
234 }
235
236 llvm::sort(Counts, std::greater<uint64_t>());
237
238 double RatioLeftInKB = (1.0 * BucketSize) / 1024;
239 assert(NumTotalCounts > 0 &&
240 "total number of heatmap buckets should be greater than 0");
241 double RatioRightInPercent = 100.0 / NumTotalCounts;
242 uint64_t RunningCount = 0;
243
244 OS << "Bucket counts, Size (KB), CDF (%)\n";
245 for (uint64_t I = 0; I < Counts.size(); I++) {
246 RunningCount += Counts[I];
247 OS << format("%llu", (I + 1)) << ", "
248 << format("%.4f", RatioLeftInKB * (I + 1)) << ", "
249 << format("%.4f", RatioRightInPercent * (RunningCount)) << "\n";
250 }
251
252 Counts.clear();
253 }
254
printSectionHotness(StringRef FileName) const255 void Heatmap::printSectionHotness(StringRef FileName) const {
256 std::error_code EC;
257 raw_fd_ostream OS(FileName, EC, sys::fs::OpenFlags::OF_None);
258 if (EC) {
259 errs() << "error opening output file: " << EC.message() << '\n';
260 exit(1);
261 }
262 printSectionHotness(OS);
263 }
264
printSectionHotness(raw_ostream & OS) const265 void Heatmap::printSectionHotness(raw_ostream &OS) const {
266 uint64_t NumTotalCounts = 0;
267 StringMap<uint64_t> SectionHotness;
268 unsigned TextSectionIndex = 0;
269
270 if (TextSections.empty())
271 return;
272
273 uint64_t UnmappedHotness = 0;
274 auto RecordUnmappedBucket = [&](uint64_t Address, uint64_t Frequency) {
275 errs() << "Couldn't map the address bucket [0x" << Twine::utohexstr(Address)
276 << ", 0x" << Twine::utohexstr(Address + BucketSize)
277 << "] containing " << Frequency
278 << " samples to a text section in the binary.";
279 UnmappedHotness += Frequency;
280 };
281
282 for (const std::pair<const uint64_t, uint64_t> &KV : Map) {
283 NumTotalCounts += KV.second;
284 // We map an address bucket to the first section (lowest address)
285 // overlapping with that bucket.
286 auto Address = KV.first * BucketSize;
287 while (TextSectionIndex < TextSections.size() &&
288 Address >= TextSections[TextSectionIndex].EndAddress)
289 TextSectionIndex++;
290 if (TextSectionIndex >= TextSections.size() ||
291 Address + BucketSize < TextSections[TextSectionIndex].BeginAddress) {
292 RecordUnmappedBucket(Address, KV.second);
293 continue;
294 }
295 SectionHotness[TextSections[TextSectionIndex].Name] += KV.second;
296 }
297
298 assert(NumTotalCounts > 0 &&
299 "total number of heatmap buckets should be greater than 0");
300
301 OS << "Section Name, Begin Address, End Address, Percentage Hotness\n";
302 for (auto &TextSection : TextSections) {
303 OS << TextSection.Name << ", 0x"
304 << Twine::utohexstr(TextSection.BeginAddress) << ", 0x"
305 << Twine::utohexstr(TextSection.EndAddress) << ", "
306 << format("%.4f",
307 100.0 * SectionHotness[TextSection.Name] / NumTotalCounts)
308 << "\n";
309 }
310 if (UnmappedHotness > 0)
311 OS << "[unmapped], 0x0, 0x0, "
312 << format("%.4f", 100.0 * UnmappedHotness / NumTotalCounts) << "\n";
313 }
314 } // namespace bolt
315 } // namespace llvm
316