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 
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 
49 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 
59 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 
217 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 
227 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 
255 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 
265 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