1 //=-- SampleProf.cpp - Sample profiling format support --------------------===//
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 // This file contains common definitions used in the reading and writing of
10 // sample profile data.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "llvm/ProfileData/SampleProf.h"
15 #include "llvm/Config/llvm-config.h"
16 #include "llvm/IR/DebugInfoMetadata.h"
17 #include "llvm/IR/PseudoProbe.h"
18 #include "llvm/ProfileData/SampleProfReader.h"
19 #include "llvm/Support/CommandLine.h"
20 #include "llvm/Support/Compiler.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Support/Error.h"
23 #include "llvm/Support/ErrorHandling.h"
24 #include "llvm/Support/LEB128.h"
25 #include "llvm/Support/ManagedStatic.h"
26 #include "llvm/Support/raw_ostream.h"
27 #include <string>
28 #include <system_error>
29 
30 using namespace llvm;
31 using namespace sampleprof;
32 
33 static cl::opt<uint64_t> ProfileSymbolListCutOff(
34     "profile-symbol-list-cutoff", cl::Hidden, cl::init(-1), cl::ZeroOrMore,
35     cl::desc("Cutoff value about how many symbols in profile symbol list "
36              "will be used. This is very useful for performance debugging"));
37 
38 namespace llvm {
39 namespace sampleprof {
40 SampleProfileFormat FunctionSamples::Format;
41 bool FunctionSamples::ProfileIsProbeBased = false;
42 bool FunctionSamples::ProfileIsCS = false;
43 bool FunctionSamples::UseMD5;
44 } // namespace sampleprof
45 } // namespace llvm
46 
47 namespace {
48 
49 // FIXME: This class is only here to support the transition to llvm::Error. It
50 // will be removed once this transition is complete. Clients should prefer to
51 // deal with the Error value directly, rather than converting to error_code.
52 class SampleProfErrorCategoryType : public std::error_category {
53   const char *name() const noexcept override { return "llvm.sampleprof"; }
54 
55   std::string message(int IE) const override {
56     sampleprof_error E = static_cast<sampleprof_error>(IE);
57     switch (E) {
58     case sampleprof_error::success:
59       return "Success";
60     case sampleprof_error::bad_magic:
61       return "Invalid sample profile data (bad magic)";
62     case sampleprof_error::unsupported_version:
63       return "Unsupported sample profile format version";
64     case sampleprof_error::too_large:
65       return "Too much profile data";
66     case sampleprof_error::truncated:
67       return "Truncated profile data";
68     case sampleprof_error::malformed:
69       return "Malformed sample profile data";
70     case sampleprof_error::unrecognized_format:
71       return "Unrecognized sample profile encoding format";
72     case sampleprof_error::unsupported_writing_format:
73       return "Profile encoding format unsupported for writing operations";
74     case sampleprof_error::truncated_name_table:
75       return "Truncated function name table";
76     case sampleprof_error::not_implemented:
77       return "Unimplemented feature";
78     case sampleprof_error::counter_overflow:
79       return "Counter overflow";
80     case sampleprof_error::ostream_seek_unsupported:
81       return "Ostream does not support seek";
82     case sampleprof_error::compress_failed:
83       return "Compress failure";
84     case sampleprof_error::uncompress_failed:
85       return "Uncompress failure";
86     case sampleprof_error::zlib_unavailable:
87       return "Zlib is unavailable";
88     case sampleprof_error::hash_mismatch:
89       return "Function hash mismatch";
90     }
91     llvm_unreachable("A value of sampleprof_error has no message.");
92   }
93 };
94 
95 } // end anonymous namespace
96 
97 static ManagedStatic<SampleProfErrorCategoryType> ErrorCategory;
98 
99 const std::error_category &llvm::sampleprof_category() {
100   return *ErrorCategory;
101 }
102 
103 void LineLocation::print(raw_ostream &OS) const {
104   OS << LineOffset;
105   if (Discriminator > 0)
106     OS << "." << Discriminator;
107 }
108 
109 raw_ostream &llvm::sampleprof::operator<<(raw_ostream &OS,
110                                           const LineLocation &Loc) {
111   Loc.print(OS);
112   return OS;
113 }
114 
115 /// Merge the samples in \p Other into this record.
116 /// Optionally scale sample counts by \p Weight.
117 sampleprof_error SampleRecord::merge(const SampleRecord &Other,
118                                      uint64_t Weight) {
119   sampleprof_error Result;
120   // With pseudo probes, merge a dangling sample with a non-dangling sample
121   // should result in a dangling sample.
122   if (FunctionSamples::ProfileIsProbeBased &&
123       (getSamples() == FunctionSamples::InvalidProbeCount ||
124        Other.getSamples() == FunctionSamples::InvalidProbeCount)) {
125     NumSamples = FunctionSamples::InvalidProbeCount;
126     Result = sampleprof_error::success;
127   } else {
128     Result = addSamples(Other.getSamples(), Weight);
129   }
130   for (const auto &I : Other.getCallTargets()) {
131     MergeResult(Result, addCalledTarget(I.first(), I.second, Weight));
132   }
133   return Result;
134 }
135 
136 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
137 LLVM_DUMP_METHOD void LineLocation::dump() const { print(dbgs()); }
138 #endif
139 
140 /// Print the sample record to the stream \p OS indented by \p Indent.
141 void SampleRecord::print(raw_ostream &OS, unsigned Indent) const {
142   OS << NumSamples;
143   if (hasCalls()) {
144     OS << ", calls:";
145     for (const auto &I : getSortedCallTargets())
146       OS << " " << I.first << ":" << I.second;
147   }
148   OS << "\n";
149 }
150 
151 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
152 LLVM_DUMP_METHOD void SampleRecord::dump() const { print(dbgs(), 0); }
153 #endif
154 
155 raw_ostream &llvm::sampleprof::operator<<(raw_ostream &OS,
156                                           const SampleRecord &Sample) {
157   Sample.print(OS, 0);
158   return OS;
159 }
160 
161 /// Print the samples collected for a function on stream \p OS.
162 void FunctionSamples::print(raw_ostream &OS, unsigned Indent) const {
163   if (getFunctionHash())
164     OS << "CFG checksum " << getFunctionHash() << "\n";
165 
166   OS << TotalSamples << ", " << TotalHeadSamples << ", " << BodySamples.size()
167      << " sampled lines\n";
168 
169   OS.indent(Indent);
170   if (!BodySamples.empty()) {
171     OS << "Samples collected in the function's body {\n";
172     SampleSorter<LineLocation, SampleRecord> SortedBodySamples(BodySamples);
173     for (const auto &SI : SortedBodySamples.get()) {
174       OS.indent(Indent + 2);
175       OS << SI->first << ": " << SI->second;
176     }
177     OS.indent(Indent);
178     OS << "}\n";
179   } else {
180     OS << "No samples collected in the function's body\n";
181   }
182 
183   OS.indent(Indent);
184   if (!CallsiteSamples.empty()) {
185     OS << "Samples collected in inlined callsites {\n";
186     SampleSorter<LineLocation, FunctionSamplesMap> SortedCallsiteSamples(
187         CallsiteSamples);
188     for (const auto &CS : SortedCallsiteSamples.get()) {
189       for (const auto &FS : CS->second) {
190         OS.indent(Indent + 2);
191         OS << CS->first << ": inlined callee: " << FS.second.getName() << ": ";
192         FS.second.print(OS, Indent + 4);
193       }
194     }
195     OS.indent(Indent);
196     OS << "}\n";
197   } else {
198     OS << "No inlined callsites in this function\n";
199   }
200 }
201 
202 raw_ostream &llvm::sampleprof::operator<<(raw_ostream &OS,
203                                           const FunctionSamples &FS) {
204   FS.print(OS);
205   return OS;
206 }
207 
208 unsigned FunctionSamples::getOffset(const DILocation *DIL) {
209   return (DIL->getLine() - DIL->getScope()->getSubprogram()->getLine()) &
210       0xffff;
211 }
212 
213 LineLocation FunctionSamples::getCallSiteIdentifier(const DILocation *DIL) {
214   if (FunctionSamples::ProfileIsProbeBased)
215     // In a pseudo-probe based profile, a callsite is simply represented by the
216     // ID of the probe associated with the call instruction. The probe ID is
217     // encoded in the Discriminator field of the call instruction's debug
218     // metadata.
219     return LineLocation(PseudoProbeDwarfDiscriminator::extractProbeIndex(
220                             DIL->getDiscriminator()),
221                         0);
222   else
223     return LineLocation(FunctionSamples::getOffset(DIL),
224                         DIL->getBaseDiscriminator());
225 }
226 
227 const FunctionSamples *FunctionSamples::findFunctionSamples(
228     const DILocation *DIL, SampleProfileReaderItaniumRemapper *Remapper) const {
229   assert(DIL);
230   SmallVector<std::pair<LineLocation, StringRef>, 10> S;
231 
232   const DILocation *PrevDIL = DIL;
233   for (DIL = DIL->getInlinedAt(); DIL; DIL = DIL->getInlinedAt()) {
234     S.push_back(std::make_pair(
235         LineLocation(getOffset(DIL), DIL->getBaseDiscriminator()),
236         PrevDIL->getScope()->getSubprogram()->getLinkageName()));
237     PrevDIL = DIL;
238   }
239   if (S.size() == 0)
240     return this;
241   const FunctionSamples *FS = this;
242   for (int i = S.size() - 1; i >= 0 && FS != nullptr; i--) {
243     FS = FS->findFunctionSamplesAt(S[i].first, S[i].second, Remapper);
244   }
245   return FS;
246 }
247 
248 void FunctionSamples::findAllNames(DenseSet<StringRef> &NameSet) const {
249   NameSet.insert(Name);
250   for (const auto &BS : BodySamples)
251     for (const auto &TS : BS.second.getCallTargets())
252       NameSet.insert(TS.getKey());
253 
254   for (const auto &CS : CallsiteSamples) {
255     for (const auto &NameFS : CS.second) {
256       NameSet.insert(NameFS.first);
257       NameFS.second.findAllNames(NameSet);
258     }
259   }
260 }
261 
262 const FunctionSamples *FunctionSamples::findFunctionSamplesAt(
263     const LineLocation &Loc, StringRef CalleeName,
264     SampleProfileReaderItaniumRemapper *Remapper) const {
265   std::string CalleeGUID;
266   CalleeName = getRepInFormat(CalleeName, UseMD5, CalleeGUID);
267 
268   auto iter = CallsiteSamples.find(Loc);
269   if (iter == CallsiteSamples.end())
270     return nullptr;
271   auto FS = iter->second.find(CalleeName);
272   if (FS != iter->second.end())
273     return &FS->second;
274   if (Remapper) {
275     if (auto NameInProfile = Remapper->lookUpNameInProfile(CalleeName)) {
276       auto FS = iter->second.find(*NameInProfile);
277       if (FS != iter->second.end())
278         return &FS->second;
279     }
280   }
281   // If we cannot find exact match of the callee name, return the FS with
282   // the max total count. Only do this when CalleeName is not provided,
283   // i.e., only for indirect calls.
284   if (!CalleeName.empty())
285     return nullptr;
286   uint64_t MaxTotalSamples = 0;
287   const FunctionSamples *R = nullptr;
288   for (const auto &NameFS : iter->second)
289     if (NameFS.second.getTotalSamples() >= MaxTotalSamples) {
290       MaxTotalSamples = NameFS.second.getTotalSamples();
291       R = &NameFS.second;
292     }
293   return R;
294 }
295 
296 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
297 LLVM_DUMP_METHOD void FunctionSamples::dump() const { print(dbgs(), 0); }
298 #endif
299 
300 std::error_code ProfileSymbolList::read(const uint8_t *Data,
301                                         uint64_t ListSize) {
302   const char *ListStart = reinterpret_cast<const char *>(Data);
303   uint64_t Size = 0;
304   uint64_t StrNum = 0;
305   while (Size < ListSize && StrNum < ProfileSymbolListCutOff) {
306     StringRef Str(ListStart + Size);
307     add(Str);
308     Size += Str.size() + 1;
309     StrNum++;
310   }
311   if (Size != ListSize && StrNum != ProfileSymbolListCutOff)
312     return sampleprof_error::malformed;
313   return sampleprof_error::success;
314 }
315 
316 std::error_code ProfileSymbolList::write(raw_ostream &OS) {
317   // Sort the symbols before output. If doing compression.
318   // It will make the compression much more effective.
319   std::vector<StringRef> SortedList(Syms.begin(), Syms.end());
320   llvm::sort(SortedList);
321 
322   std::string OutputString;
323   for (auto &Sym : SortedList) {
324     OutputString.append(Sym.str());
325     OutputString.append(1, '\0');
326   }
327 
328   OS << OutputString;
329   return sampleprof_error::success;
330 }
331 
332 void ProfileSymbolList::dump(raw_ostream &OS) const {
333   OS << "======== Dump profile symbol list ========\n";
334   std::vector<StringRef> SortedList(Syms.begin(), Syms.end());
335   llvm::sort(SortedList);
336 
337   for (auto &Sym : SortedList)
338     OS << Sym << "\n";
339 }
340