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 = false;
44 bool FunctionSamples::HasUniqSuffix = true;
45 bool FunctionSamples::ProfileIsFS = false;
46 } // namespace sampleprof
47 } // namespace llvm
48 
49 namespace {
50 
51 // FIXME: This class is only here to support the transition to llvm::Error. It
52 // will be removed once this transition is complete. Clients should prefer to
53 // deal with the Error value directly, rather than converting to error_code.
54 class SampleProfErrorCategoryType : public std::error_category {
55   const char *name() const noexcept override { return "llvm.sampleprof"; }
56 
57   std::string message(int IE) const override {
58     sampleprof_error E = static_cast<sampleprof_error>(IE);
59     switch (E) {
60     case sampleprof_error::success:
61       return "Success";
62     case sampleprof_error::bad_magic:
63       return "Invalid sample profile data (bad magic)";
64     case sampleprof_error::unsupported_version:
65       return "Unsupported sample profile format version";
66     case sampleprof_error::too_large:
67       return "Too much profile data";
68     case sampleprof_error::truncated:
69       return "Truncated profile data";
70     case sampleprof_error::malformed:
71       return "Malformed sample profile data";
72     case sampleprof_error::unrecognized_format:
73       return "Unrecognized sample profile encoding format";
74     case sampleprof_error::unsupported_writing_format:
75       return "Profile encoding format unsupported for writing operations";
76     case sampleprof_error::truncated_name_table:
77       return "Truncated function name table";
78     case sampleprof_error::not_implemented:
79       return "Unimplemented feature";
80     case sampleprof_error::counter_overflow:
81       return "Counter overflow";
82     case sampleprof_error::ostream_seek_unsupported:
83       return "Ostream does not support seek";
84     case sampleprof_error::compress_failed:
85       return "Compress failure";
86     case sampleprof_error::uncompress_failed:
87       return "Uncompress failure";
88     case sampleprof_error::zlib_unavailable:
89       return "Zlib is unavailable";
90     case sampleprof_error::hash_mismatch:
91       return "Function hash mismatch";
92     }
93     llvm_unreachable("A value of sampleprof_error has no message.");
94   }
95 };
96 
97 } // end anonymous namespace
98 
99 static ManagedStatic<SampleProfErrorCategoryType> ErrorCategory;
100 
101 const std::error_category &llvm::sampleprof_category() {
102   return *ErrorCategory;
103 }
104 
105 void LineLocation::print(raw_ostream &OS) const {
106   OS << LineOffset;
107   if (Discriminator > 0)
108     OS << "." << Discriminator;
109 }
110 
111 raw_ostream &llvm::sampleprof::operator<<(raw_ostream &OS,
112                                           const LineLocation &Loc) {
113   Loc.print(OS);
114   return OS;
115 }
116 
117 /// Merge the samples in \p Other into this record.
118 /// Optionally scale sample counts by \p Weight.
119 sampleprof_error SampleRecord::merge(const SampleRecord &Other,
120                                      uint64_t Weight) {
121   sampleprof_error Result;
122   Result = addSamples(Other.getSamples(), Weight);
123   for (const auto &I : Other.getCallTargets()) {
124     MergeResult(Result, addCalledTarget(I.first(), I.second, Weight));
125   }
126   return Result;
127 }
128 
129 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
130 LLVM_DUMP_METHOD void LineLocation::dump() const { print(dbgs()); }
131 #endif
132 
133 /// Print the sample record to the stream \p OS indented by \p Indent.
134 void SampleRecord::print(raw_ostream &OS, unsigned Indent) const {
135   OS << NumSamples;
136   if (hasCalls()) {
137     OS << ", calls:";
138     for (const auto &I : getSortedCallTargets())
139       OS << " " << I.first << ":" << I.second;
140   }
141   OS << "\n";
142 }
143 
144 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
145 LLVM_DUMP_METHOD void SampleRecord::dump() const { print(dbgs(), 0); }
146 #endif
147 
148 raw_ostream &llvm::sampleprof::operator<<(raw_ostream &OS,
149                                           const SampleRecord &Sample) {
150   Sample.print(OS, 0);
151   return OS;
152 }
153 
154 /// Print the samples collected for a function on stream \p OS.
155 void FunctionSamples::print(raw_ostream &OS, unsigned Indent) const {
156   if (getFunctionHash())
157     OS << "CFG checksum " << getFunctionHash() << "\n";
158 
159   OS << TotalSamples << ", " << TotalHeadSamples << ", " << BodySamples.size()
160      << " sampled lines\n";
161 
162   OS.indent(Indent);
163   if (!BodySamples.empty()) {
164     OS << "Samples collected in the function's body {\n";
165     SampleSorter<LineLocation, SampleRecord> SortedBodySamples(BodySamples);
166     for (const auto &SI : SortedBodySamples.get()) {
167       OS.indent(Indent + 2);
168       OS << SI->first << ": " << SI->second;
169     }
170     OS.indent(Indent);
171     OS << "}\n";
172   } else {
173     OS << "No samples collected in the function's body\n";
174   }
175 
176   OS.indent(Indent);
177   if (!CallsiteSamples.empty()) {
178     OS << "Samples collected in inlined callsites {\n";
179     SampleSorter<LineLocation, FunctionSamplesMap> SortedCallsiteSamples(
180         CallsiteSamples);
181     for (const auto &CS : SortedCallsiteSamples.get()) {
182       for (const auto &FS : CS->second) {
183         OS.indent(Indent + 2);
184         OS << CS->first << ": inlined callee: " << FS.second.getName() << ": ";
185         FS.second.print(OS, Indent + 4);
186       }
187     }
188     OS.indent(Indent);
189     OS << "}\n";
190   } else {
191     OS << "No inlined callsites in this function\n";
192   }
193 }
194 
195 raw_ostream &llvm::sampleprof::operator<<(raw_ostream &OS,
196                                           const FunctionSamples &FS) {
197   FS.print(OS);
198   return OS;
199 }
200 
201 unsigned FunctionSamples::getOffset(const DILocation *DIL) {
202   return (DIL->getLine() - DIL->getScope()->getSubprogram()->getLine()) &
203       0xffff;
204 }
205 
206 LineLocation FunctionSamples::getCallSiteIdentifier(const DILocation *DIL) {
207   if (FunctionSamples::ProfileIsProbeBased)
208     // In a pseudo-probe based profile, a callsite is simply represented by the
209     // ID of the probe associated with the call instruction. The probe ID is
210     // encoded in the Discriminator field of the call instruction's debug
211     // metadata.
212     return LineLocation(PseudoProbeDwarfDiscriminator::extractProbeIndex(
213                             DIL->getDiscriminator()),
214                         0);
215   else
216     return LineLocation(FunctionSamples::getOffset(DIL),
217                         DIL->getBaseDiscriminator());
218 }
219 
220 const FunctionSamples *FunctionSamples::findFunctionSamples(
221     const DILocation *DIL, SampleProfileReaderItaniumRemapper *Remapper) const {
222   assert(DIL);
223   SmallVector<std::pair<LineLocation, StringRef>, 10> S;
224 
225   const DILocation *PrevDIL = DIL;
226   for (DIL = DIL->getInlinedAt(); DIL; DIL = DIL->getInlinedAt()) {
227     unsigned Discriminator;
228     if (ProfileIsFS)
229       Discriminator = DIL->getDiscriminator();
230     else
231       Discriminator = DIL->getBaseDiscriminator();
232 
233     S.push_back(
234         std::make_pair(LineLocation(getOffset(DIL), Discriminator),
235                        PrevDIL->getScope()->getSubprogram()->getLinkageName()));
236     PrevDIL = DIL;
237   }
238   if (S.size() == 0)
239     return this;
240   const FunctionSamples *FS = this;
241   for (int i = S.size() - 1; i >= 0 && FS != nullptr; i--) {
242     FS = FS->findFunctionSamplesAt(S[i].first, S[i].second, Remapper);
243   }
244   return FS;
245 }
246 
247 void FunctionSamples::findAllNames(DenseSet<StringRef> &NameSet) const {
248   NameSet.insert(Name);
249   for (const auto &BS : BodySamples)
250     for (const auto &TS : BS.second.getCallTargets())
251       NameSet.insert(TS.getKey());
252 
253   for (const auto &CS : CallsiteSamples) {
254     for (const auto &NameFS : CS.second) {
255       NameSet.insert(NameFS.first);
256       NameFS.second.findAllNames(NameSet);
257     }
258   }
259 }
260 
261 const FunctionSamples *FunctionSamples::findFunctionSamplesAt(
262     const LineLocation &Loc, StringRef CalleeName,
263     SampleProfileReaderItaniumRemapper *Remapper) const {
264   CalleeName = getCanonicalFnName(CalleeName);
265 
266   std::string CalleeGUID;
267   CalleeName = getRepInFormat(CalleeName, UseMD5, CalleeGUID);
268 
269   auto iter = CallsiteSamples.find(Loc);
270   if (iter == CallsiteSamples.end())
271     return nullptr;
272   auto FS = iter->second.find(CalleeName);
273   if (FS != iter->second.end())
274     return &FS->second;
275   if (Remapper) {
276     if (auto NameInProfile = Remapper->lookUpNameInProfile(CalleeName)) {
277       auto FS = iter->second.find(*NameInProfile);
278       if (FS != iter->second.end())
279         return &FS->second;
280     }
281   }
282   // If we cannot find exact match of the callee name, return the FS with
283   // the max total count. Only do this when CalleeName is not provided,
284   // i.e., only for indirect calls.
285   if (!CalleeName.empty())
286     return nullptr;
287   uint64_t MaxTotalSamples = 0;
288   const FunctionSamples *R = nullptr;
289   for (const auto &NameFS : iter->second)
290     if (NameFS.second.getTotalSamples() >= MaxTotalSamples) {
291       MaxTotalSamples = NameFS.second.getTotalSamples();
292       R = &NameFS.second;
293     }
294   return R;
295 }
296 
297 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
298 LLVM_DUMP_METHOD void FunctionSamples::dump() const { print(dbgs(), 0); }
299 #endif
300 
301 std::error_code ProfileSymbolList::read(const uint8_t *Data,
302                                         uint64_t ListSize) {
303   const char *ListStart = reinterpret_cast<const char *>(Data);
304   uint64_t Size = 0;
305   uint64_t StrNum = 0;
306   while (Size < ListSize && StrNum < ProfileSymbolListCutOff) {
307     StringRef Str(ListStart + Size);
308     add(Str);
309     Size += Str.size() + 1;
310     StrNum++;
311   }
312   if (Size != ListSize && StrNum != ProfileSymbolListCutOff)
313     return sampleprof_error::malformed;
314   return sampleprof_error::success;
315 }
316 
317 void SampleContextTrimmer::trimAndMergeColdContextProfiles(
318     uint64_t ColdCountThreshold, bool TrimColdContext, bool MergeColdContext,
319     uint32_t ColdContextFrameLength) {
320   if (!TrimColdContext && !MergeColdContext)
321     return;
322 
323   // Nothing to merge if sample threshold is zero
324   if (ColdCountThreshold == 0)
325     return;
326 
327   // Filter the cold profiles from ProfileMap and move them into a tmp
328   // container
329   std::vector<std::pair<StringRef, const FunctionSamples *>> ColdProfiles;
330   for (const auto &I : ProfileMap) {
331     const FunctionSamples &FunctionProfile = I.second;
332     if (FunctionProfile.getTotalSamples() >= ColdCountThreshold)
333       continue;
334     ColdProfiles.emplace_back(I.getKey(), &I.second);
335   }
336 
337   // Remove the cold profile from ProfileMap and merge them into
338   // MergedProfileMap by the last K frames of context
339   StringMap<FunctionSamples> MergedProfileMap;
340   for (const auto &I : ColdProfiles) {
341     if (MergeColdContext) {
342       auto Ret = MergedProfileMap.try_emplace(
343           I.second->getContext().getContextWithLastKFrames(
344               ColdContextFrameLength),
345           FunctionSamples());
346       FunctionSamples &MergedProfile = Ret.first->second;
347       MergedProfile.merge(*I.second);
348     }
349     ProfileMap.erase(I.first);
350   }
351 
352   // Move the merged profiles into ProfileMap;
353   for (const auto &I : MergedProfileMap) {
354     // Filter the cold merged profile
355     if (TrimColdContext && I.second.getTotalSamples() < ColdCountThreshold &&
356         ProfileMap.find(I.getKey()) == ProfileMap.end())
357       continue;
358     // Merge the profile if the original profile exists, otherwise just insert
359     // as a new profile
360     auto Ret = ProfileMap.try_emplace(I.getKey(), FunctionSamples());
361     if (Ret.second) {
362       SampleContext FContext(Ret.first->first(), RawContext);
363       FunctionSamples &FProfile = Ret.first->second;
364       FProfile.setContext(FContext);
365       FProfile.setName(FContext.getNameWithoutContext());
366     }
367     FunctionSamples &OrigProfile = Ret.first->second;
368     OrigProfile.merge(I.second);
369   }
370 }
371 
372 void SampleContextTrimmer::canonicalizeContextProfiles() {
373   std::vector<StringRef> ProfilesToBeRemoved;
374   StringMap<FunctionSamples> ProfilesToBeAdded;
375   for (auto &I : ProfileMap) {
376     FunctionSamples &FProfile = I.second;
377     StringRef ContextStr = FProfile.getNameWithContext();
378     if (I.first() == ContextStr)
379       continue;
380 
381     // Use the context string from FunctionSamples to update the keys of
382     // ProfileMap. They can get out of sync after context profile promotion
383     // through pre-inliner.
384     // Duplicate the function profile for later insertion to avoid a conflict
385     // caused by a context both to be add and to be removed. This could happen
386     // when a context is promoted to another context which is also promoted to
387     // the third context. For example, given an original context A @ B @ C that
388     // is promoted to B @ C and the original context B @ C which is promoted to
389     // just C, adding B @ C to the profile map while removing same context (but
390     // with different profiles) from the map can cause a conflict if they are
391     // not handled in a right order. This can be solved by just caching the
392     // profiles to be added.
393     auto Ret = ProfilesToBeAdded.try_emplace(ContextStr, FProfile);
394     (void)Ret;
395     assert(Ret.second && "Context conflict during canonicalization");
396     ProfilesToBeRemoved.push_back(I.first());
397   }
398 
399   for (auto &I : ProfilesToBeRemoved) {
400     ProfileMap.erase(I);
401   }
402 
403   for (auto &I : ProfilesToBeAdded) {
404     ProfileMap.try_emplace(I.first(), I.second);
405   }
406 }
407 
408 std::error_code ProfileSymbolList::write(raw_ostream &OS) {
409   // Sort the symbols before output. If doing compression.
410   // It will make the compression much more effective.
411   std::vector<StringRef> SortedList(Syms.begin(), Syms.end());
412   llvm::sort(SortedList);
413 
414   std::string OutputString;
415   for (auto &Sym : SortedList) {
416     OutputString.append(Sym.str());
417     OutputString.append(1, '\0');
418   }
419 
420   OS << OutputString;
421   return sampleprof_error::success;
422 }
423 
424 void ProfileSymbolList::dump(raw_ostream &OS) const {
425   OS << "======== Dump profile symbol list ========\n";
426   std::vector<StringRef> SortedList(Syms.begin(), Syms.end());
427   llvm::sort(SortedList);
428 
429   for (auto &Sym : SortedList)
430     OS << Sym << "\n";
431 }
432