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