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/Twine.h"
12 #include "llvm/Support/CommandLine.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 <cmath>
20 #include <vector>
21 
22 #define DEBUG_TYPE "bolt-heatmap"
23 
24 using namespace llvm;
25 
26 namespace llvm {
27 namespace bolt {
28 
29 void Heatmap::registerAddressRange(uint64_t StartAddress, uint64_t EndAddress,
30                                    uint64_t Count) {
31   if (ignoreAddress(StartAddress)) {
32     ++NumSkippedRanges;
33     return;
34   }
35 
36   if (StartAddress > EndAddress || EndAddress - StartAddress > 64 * 1024) {
37     LLVM_DEBUG(dbgs() << "invalid range : 0x" << Twine::utohexstr(StartAddress)
38                       << " -> 0x" << Twine::utohexstr(EndAddress) << '\n');
39     ++NumSkippedRanges;
40     return;
41   }
42 
43   for (uint64_t Bucket = StartAddress / BucketSize;
44        Bucket <= EndAddress / BucketSize; ++Bucket)
45     Map[Bucket] += Count;
46 }
47 
48 void Heatmap::print(StringRef FileName) const {
49   std::error_code EC;
50   raw_fd_ostream OS(FileName, EC, sys::fs::OpenFlags::OF_None);
51   if (EC) {
52     errs() << "error opening output file: " << EC.message() << '\n';
53     exit(1);
54   }
55   print(OS);
56 }
57 
58 void Heatmap::print(raw_ostream &OS) const {
59   const char FillChar = '.';
60 
61   const auto DefaultColor = raw_ostream::WHITE;
62   auto changeColor = [&](raw_ostream::Colors Color) -> void {
63     static auto CurrentColor = raw_ostream::BLACK;
64     if (CurrentColor == Color)
65       return;
66     OS.changeColor(Color);
67     CurrentColor = Color;
68   };
69 
70   const uint64_t BytesPerLine = opts::BucketsPerLine * BucketSize;
71 
72   // Calculate the max value for scaling.
73   uint64_t MaxValue = 0;
74   for (const std::pair<const uint64_t, uint64_t> &Entry : Map)
75     MaxValue = std::max<uint64_t>(MaxValue, Entry.second);
76 
77   // Print start of the line and fill it with an empty space right before
78   // the Address.
79   auto startLine = [&](uint64_t Address, bool Empty = false) {
80     changeColor(DefaultColor);
81     const uint64_t LineAddress = Address / BytesPerLine * BytesPerLine;
82 
83     if (MaxAddress > 0xffffffff)
84       OS << format("0x%016" PRIx64 ": ", LineAddress);
85     else
86       OS << format("0x%08" PRIx64 ": ", LineAddress);
87 
88     if (Empty)
89       Address = LineAddress + BytesPerLine;
90     for (uint64_t Fill = LineAddress; Fill < Address; Fill += BucketSize)
91       OS << FillChar;
92   };
93 
94   // Finish line after \p Address was printed.
95   auto finishLine = [&](uint64_t Address) {
96     const uint64_t End = alignTo(Address + 1, BytesPerLine);
97     for (uint64_t Fill = Address + BucketSize; Fill < End; Fill += BucketSize)
98       OS << FillChar;
99     OS << '\n';
100   };
101 
102   // Fill empty space in (Start, End) range.
103   auto fillRange = [&](uint64_t Start, uint64_t End) {
104     if ((Start / BytesPerLine) == (End / BytesPerLine)) {
105       for (uint64_t Fill = Start + BucketSize; Fill < End; Fill += BucketSize) {
106         changeColor(DefaultColor);
107         OS << FillChar;
108       }
109       return;
110     }
111 
112     changeColor(DefaultColor);
113     finishLine(Start);
114     Start = alignTo(Start, BytesPerLine);
115 
116     uint64_t NumEmptyLines = (End - Start) / BytesPerLine;
117 
118     if (NumEmptyLines > 32) {
119       OS << '\n';
120     } else {
121       while (NumEmptyLines--) {
122         startLine(Start, /*Empty=*/true);
123         OS << '\n';
124         Start += BytesPerLine;
125       }
126     }
127 
128     startLine(End);
129   };
130 
131   static raw_ostream::Colors Colors[] = {
132       raw_ostream::WHITE, raw_ostream::WHITE,  raw_ostream::CYAN,
133       raw_ostream::GREEN, raw_ostream::YELLOW, raw_ostream::RED};
134   constexpr size_t NumRanges = sizeof(Colors) / sizeof(Colors[0]);
135 
136   uint64_t Range[NumRanges];
137   for (uint64_t I = 0; I < NumRanges; ++I)
138     Range[I] = std::max(I + 1, (uint64_t)std::pow((double)MaxValue,
139                                                   (double)(I + 1) / NumRanges));
140   Range[NumRanges - 1] = std::max((uint64_t)NumRanges, MaxValue);
141 
142   // Print scaled value
143   auto printValue = [&](uint64_t Value, bool ResetColor = false) {
144     assert(Value && "should only print positive values");
145     for (unsigned I = 0; I < sizeof(Range) / sizeof(Range[0]); ++I) {
146       if (Value <= Range[I]) {
147         changeColor(Colors[I]);
148         break;
149       }
150     }
151     if (Value <= Range[0])
152       OS << 'o';
153     else
154       OS << 'O';
155 
156     if (ResetColor)
157       changeColor(DefaultColor);
158   };
159 
160   // Print against black background
161   OS.changeColor(raw_ostream::BLACK, /*Bold=*/false, /*Background=*/true);
162   changeColor(DefaultColor);
163 
164   // Print map legend
165   OS << "Legend:\n";
166   uint64_t PrevValue = 0;
167   for (unsigned I = 0; I < sizeof(Range) / sizeof(Range[0]); ++I) {
168     const uint64_t Value = Range[I];
169     OS << "  ";
170     printValue(Value, true);
171     OS << " : (" << PrevValue << ", " << Value << "]\n";
172     PrevValue = Value;
173   }
174 
175   // Pos - character position from right in hex form.
176   auto printHeader = [&](unsigned Pos) {
177     OS << "            ";
178     if (MaxAddress > 0xffffffff)
179       OS << "        ";
180     unsigned PrevValue = unsigned(-1);
181     for (unsigned I = 0; I < BytesPerLine; I += BucketSize) {
182       const unsigned Value = (I & ((1 << Pos * 4) - 1)) >> (Pos - 1) * 4;
183       if (Value != PrevValue) {
184         OS << Twine::utohexstr(Value);
185         PrevValue = Value;
186       } else {
187         OS << ' ';
188       }
189     }
190     OS << '\n';
191   };
192   for (unsigned I = 5; I > 0; --I)
193     printHeader(I);
194 
195   uint64_t PrevAddress = 0;
196   for (auto MI = Map.begin(), ME = Map.end(); MI != ME; ++MI) {
197     const std::pair<const uint64_t, uint64_t> &Entry = *MI;
198     uint64_t Address = Entry.first * BucketSize;
199 
200     if (PrevAddress)
201       fillRange(PrevAddress, Address);
202     else
203       startLine(Address);
204 
205     printValue(Entry.second);
206 
207     PrevAddress = Address;
208   }
209 
210   if (PrevAddress) {
211     changeColor(DefaultColor);
212     finishLine(PrevAddress);
213   }
214 }
215 
216 void Heatmap::printCDF(StringRef FileName) const {
217   std::error_code EC;
218   raw_fd_ostream OS(FileName, EC, sys::fs::OpenFlags::OF_None);
219   if (EC) {
220     errs() << "error opening output file: " << EC.message() << '\n';
221     exit(1);
222   }
223   printCDF(OS);
224 }
225 
226 void Heatmap::printCDF(raw_ostream &OS) const {
227   uint64_t NumTotalCounts = 0;
228   std::vector<uint64_t> Counts;
229 
230   for (const std::pair<const uint64_t, uint64_t> &KV : Map) {
231     Counts.push_back(KV.second);
232     NumTotalCounts += KV.second;
233   }
234 
235   std::sort(Counts.begin(), Counts.end(), std::greater<uint64_t>());
236 
237   double RatioLeftInKB = (1.0 * BucketSize) / 1024;
238   assert(NumTotalCounts > 0 &&
239          "total number of heatmap buckets should be greater than 0");
240   double RatioRightInPercent = 100.0 / NumTotalCounts;
241   uint64_t RunningCount = 0;
242 
243   OS << "Bucket counts, Size (KB), CDF (%)\n";
244   for (uint64_t I = 0; I < Counts.size(); I++) {
245     RunningCount += Counts[I];
246     OS << format("%llu", (I + 1)) << ", "
247        << format("%.4f", RatioLeftInKB * (I + 1)) << ", "
248        << format("%.4f", RatioRightInPercent * (RunningCount)) << "\n";
249   }
250 
251   Counts.clear();
252 }
253 
254 } // namespace bolt
255 } // namespace llvm
256