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 | |
27 | using namespace llvm; |
28 | |
29 | namespace llvm { |
30 | namespace bolt { |
31 | |
32 | void 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 | |
51 | void 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 | |
63 | void 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 = [&](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 | |
252 | void 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 | |
262 | void 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 | |
290 | void 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 | |
300 | void 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 (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 | |
370 | void 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 | |