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/ErrorHandling.h"
23#include "llvm/Support/raw_ostream.h"
24#include <string>
25#include <system_error>
26
27using namespace llvm;
28using namespace sampleprof;
29
30static cl::opt<uint64_t> ProfileSymbolListCutOff(
31    "profile-symbol-list-cutoff", cl::Hidden, cl::init(-1),
32    cl::desc("Cutoff value about how many symbols in profile symbol list "
33             "will be used. This is very useful for performance debugging"));
34
35static cl::opt<bool> GenerateMergedBaseProfiles(
36    "generate-merged-base-profiles",
37    cl::desc("When generating nested context-sensitive profiles, always "
38             "generate extra base profile for function with all its context "
39             "profiles merged into it."));
40
41namespace llvm {
42namespace sampleprof {
43bool FunctionSamples::ProfileIsProbeBased = false;
44bool FunctionSamples::ProfileIsCS = false;
45bool FunctionSamples::ProfileIsPreInlined = false;
46bool FunctionSamples::UseMD5 = false;
47bool FunctionSamples::HasUniqSuffix = true;
48bool FunctionSamples::ProfileIsFS = false;
49} // namespace sampleprof
50} // namespace llvm
51
52namespace {
53
54// FIXME: This class is only here to support the transition to llvm::Error. It
55// will be removed once this transition is complete. Clients should prefer to
56// deal with the Error value directly, rather than converting to error_code.
57class SampleProfErrorCategoryType : public std::error_category {
58  const char *name() const noexcept override { return "llvm.sampleprof"; }
59
60  std::string message(int IE) const override {
61    sampleprof_error E = static_cast<sampleprof_error>(IE);
62    switch (E) {
63    case sampleprof_error::success:
64      return "Success";
65    case sampleprof_error::bad_magic:
66      return "Invalid sample profile data (bad magic)";
67    case sampleprof_error::unsupported_version:
68      return "Unsupported sample profile format version";
69    case sampleprof_error::too_large:
70      return "Too much profile data";
71    case sampleprof_error::truncated:
72      return "Truncated profile data";
73    case sampleprof_error::malformed:
74      return "Malformed sample profile data";
75    case sampleprof_error::unrecognized_format:
76      return "Unrecognized sample profile encoding format";
77    case sampleprof_error::unsupported_writing_format:
78      return "Profile encoding format unsupported for writing operations";
79    case sampleprof_error::truncated_name_table:
80      return "Truncated function name table";
81    case sampleprof_error::not_implemented:
82      return "Unimplemented feature";
83    case sampleprof_error::counter_overflow:
84      return "Counter overflow";
85    case sampleprof_error::ostream_seek_unsupported:
86      return "Ostream does not support seek";
87    case sampleprof_error::uncompress_failed:
88      return "Uncompress failure";
89    case sampleprof_error::zlib_unavailable:
90      return "Zlib is unavailable";
91    case sampleprof_error::hash_mismatch:
92      return "Function hash mismatch";
93    }
94    llvm_unreachable("A value of sampleprof_error has no message.");
95  }
96};
97
98} // end anonymous namespace
99
100const std::error_category &llvm::sampleprof_category() {
101  static SampleProfErrorCategoryType ErrorCategory;
102  return ErrorCategory;
103}
104
105void LineLocation::print(raw_ostream &OS) const {
106  OS << LineOffset;
107  if (Discriminator > 0)
108    OS << "." << Discriminator;
109}
110
111raw_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.
119sampleprof_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)
130LLVM_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.
134void 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)
145LLVM_DUMP_METHOD void SampleRecord::dump() const { print(dbgs(), 0); }
146#endif
147
148raw_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.
155void 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.getFunction()
185           << ": ";
186        FS.second.print(OS, Indent + 4);
187      }
188    }
189    OS.indent(Indent);
190    OS << "}\n";
191  } else {
192    OS << "No inlined callsites in this function\n";
193  }
194}
195
196raw_ostream &llvm::sampleprof::operator<<(raw_ostream &OS,
197                                          const FunctionSamples &FS) {
198  FS.print(OS);
199  return OS;
200}
201
202void sampleprof::sortFuncProfiles(
203    const SampleProfileMap &ProfileMap,
204    std::vector<NameFunctionSamples> &SortedProfiles) {
205  for (const auto &I : ProfileMap) {
206    SortedProfiles.push_back(std::make_pair(I.first, &I.second));
207  }
208  llvm::stable_sort(SortedProfiles, [](const NameFunctionSamples &A,
209                                       const NameFunctionSamples &B) {
210    if (A.second->getTotalSamples() == B.second->getTotalSamples())
211      return A.second->getContext() < B.second->getContext();
212    return A.second->getTotalSamples() > B.second->getTotalSamples();
213  });
214}
215
216unsigned FunctionSamples::getOffset(const DILocation *DIL) {
217  return (DIL->getLine() - DIL->getScope()->getSubprogram()->getLine()) &
218      0xffff;
219}
220
221LineLocation FunctionSamples::getCallSiteIdentifier(const DILocation *DIL,
222                                                    bool ProfileIsFS) {
223  if (FunctionSamples::ProfileIsProbeBased) {
224    // In a pseudo-probe based profile, a callsite is simply represented by the
225    // ID of the probe associated with the call instruction. The probe ID is
226    // encoded in the Discriminator field of the call instruction's debug
227    // metadata.
228    return LineLocation(PseudoProbeDwarfDiscriminator::extractProbeIndex(
229                            DIL->getDiscriminator()),
230                        0);
231  } else {
232    unsigned Discriminator =
233        ProfileIsFS ? DIL->getDiscriminator() : DIL->getBaseDiscriminator();
234    return LineLocation(FunctionSamples::getOffset(DIL), Discriminator);
235  }
236}
237
238const FunctionSamples *FunctionSamples::findFunctionSamples(
239    const DILocation *DIL, SampleProfileReaderItaniumRemapper *Remapper) const {
240  assert(DIL);
241  SmallVector<std::pair<LineLocation, StringRef>, 10> S;
242
243  const DILocation *PrevDIL = DIL;
244  for (DIL = DIL->getInlinedAt(); DIL; DIL = DIL->getInlinedAt()) {
245    // Use C++ linkage name if possible.
246    StringRef Name = PrevDIL->getScope()->getSubprogram()->getLinkageName();
247    if (Name.empty())
248      Name = PrevDIL->getScope()->getSubprogram()->getName();
249    S.emplace_back(FunctionSamples::getCallSiteIdentifier(
250                       DIL, FunctionSamples::ProfileIsFS),
251                   Name);
252    PrevDIL = DIL;
253  }
254
255  if (S.size() == 0)
256    return this;
257  const FunctionSamples *FS = this;
258  for (int i = S.size() - 1; i >= 0 && FS != nullptr; i--) {
259    FS = FS->findFunctionSamplesAt(S[i].first, S[i].second, Remapper);
260  }
261  return FS;
262}
263
264void FunctionSamples::findAllNames(DenseSet<FunctionId> &NameSet) const {
265  NameSet.insert(getFunction());
266  for (const auto &BS : BodySamples)
267    for (const auto &TS : BS.second.getCallTargets())
268      NameSet.insert(TS.first);
269
270  for (const auto &CS : CallsiteSamples) {
271    for (const auto &NameFS : CS.second) {
272      NameSet.insert(NameFS.first);
273      NameFS.second.findAllNames(NameSet);
274    }
275  }
276}
277
278const FunctionSamples *FunctionSamples::findFunctionSamplesAt(
279    const LineLocation &Loc, StringRef CalleeName,
280    SampleProfileReaderItaniumRemapper *Remapper) const {
281  CalleeName = getCanonicalFnName(CalleeName);
282
283  auto iter = CallsiteSamples.find(mapIRLocToProfileLoc(Loc));
284  if (iter == CallsiteSamples.end())
285    return nullptr;
286  auto FS = iter->second.find(getRepInFormat(CalleeName));
287  if (FS != iter->second.end())
288    return &FS->second;
289  if (Remapper) {
290    if (auto NameInProfile = Remapper->lookUpNameInProfile(CalleeName)) {
291      auto FS = iter->second.find(getRepInFormat(*NameInProfile));
292      if (FS != iter->second.end())
293        return &FS->second;
294    }
295  }
296  // If we cannot find exact match of the callee name, return the FS with
297  // the max total count. Only do this when CalleeName is not provided,
298  // i.e., only for indirect calls.
299  if (!CalleeName.empty())
300    return nullptr;
301  uint64_t MaxTotalSamples = 0;
302  const FunctionSamples *R = nullptr;
303  for (const auto &NameFS : iter->second)
304    if (NameFS.second.getTotalSamples() >= MaxTotalSamples) {
305      MaxTotalSamples = NameFS.second.getTotalSamples();
306      R = &NameFS.second;
307    }
308  return R;
309}
310
311#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
312LLVM_DUMP_METHOD void FunctionSamples::dump() const { print(dbgs(), 0); }
313#endif
314
315std::error_code ProfileSymbolList::read(const uint8_t *Data,
316                                        uint64_t ListSize) {
317  const char *ListStart = reinterpret_cast<const char *>(Data);
318  uint64_t Size = 0;
319  uint64_t StrNum = 0;
320  while (Size < ListSize && StrNum < ProfileSymbolListCutOff) {
321    StringRef Str(ListStart + Size);
322    add(Str);
323    Size += Str.size() + 1;
324    StrNum++;
325  }
326  if (Size != ListSize && StrNum != ProfileSymbolListCutOff)
327    return sampleprof_error::malformed;
328  return sampleprof_error::success;
329}
330
331void SampleContextTrimmer::trimAndMergeColdContextProfiles(
332    uint64_t ColdCountThreshold, bool TrimColdContext, bool MergeColdContext,
333    uint32_t ColdContextFrameLength, bool TrimBaseProfileOnly) {
334  if (!TrimColdContext && !MergeColdContext)
335    return;
336
337  // Nothing to merge if sample threshold is zero
338  if (ColdCountThreshold == 0)
339    return;
340
341  // Trimming base profiles only is mainly to honor the preinliner decsion. When
342  // MergeColdContext is true preinliner decsion is not honored anyway so turn
343  // off TrimBaseProfileOnly.
344  if (MergeColdContext)
345    TrimBaseProfileOnly = false;
346
347  // Filter the cold profiles from ProfileMap and move them into a tmp
348  // container
349  std::vector<std::pair<hash_code, const FunctionSamples *>> ColdProfiles;
350  for (const auto &I : ProfileMap) {
351    const SampleContext &Context = I.second.getContext();
352    const FunctionSamples &FunctionProfile = I.second;
353    if (FunctionProfile.getTotalSamples() < ColdCountThreshold &&
354        (!TrimBaseProfileOnly || Context.isBaseContext()))
355      ColdProfiles.emplace_back(I.first, &I.second);
356  }
357
358  // Remove the cold profile from ProfileMap and merge them into
359  // MergedProfileMap by the last K frames of context
360  SampleProfileMap MergedProfileMap;
361  for (const auto &I : ColdProfiles) {
362    if (MergeColdContext) {
363      auto MergedContext = I.second->getContext().getContextFrames();
364      if (ColdContextFrameLength < MergedContext.size())
365        MergedContext = MergedContext.take_back(ColdContextFrameLength);
366      // Need to set MergedProfile's context here otherwise it will be lost.
367      FunctionSamples &MergedProfile = MergedProfileMap.Create(MergedContext);
368      MergedProfile.merge(*I.second);
369    }
370    ProfileMap.erase(I.first);
371  }
372
373  // Move the merged profiles into ProfileMap;
374  for (const auto &I : MergedProfileMap) {
375    // Filter the cold merged profile
376    if (TrimColdContext && I.second.getTotalSamples() < ColdCountThreshold &&
377        ProfileMap.find(I.second.getContext()) == ProfileMap.end())
378      continue;
379    // Merge the profile if the original profile exists, otherwise just insert
380    // as a new profile. If inserted as a new profile from MergedProfileMap, it
381    // already has the right context.
382    auto Ret = ProfileMap.emplace(I.second.getContext(), FunctionSamples());
383    FunctionSamples &OrigProfile = Ret.first->second;
384    OrigProfile.merge(I.second);
385  }
386}
387
388std::error_code ProfileSymbolList::write(raw_ostream &OS) {
389  // Sort the symbols before output. If doing compression.
390  // It will make the compression much more effective.
391  std::vector<StringRef> SortedList(Syms.begin(), Syms.end());
392  llvm::sort(SortedList);
393
394  std::string OutputString;
395  for (auto &Sym : SortedList) {
396    OutputString.append(Sym.str());
397    OutputString.append(1, '\0');
398  }
399
400  OS << OutputString;
401  return sampleprof_error::success;
402}
403
404void ProfileSymbolList::dump(raw_ostream &OS) const {
405  OS << "======== Dump profile symbol list ========\n";
406  std::vector<StringRef> SortedList(Syms.begin(), Syms.end());
407  llvm::sort(SortedList);
408
409  for (auto &Sym : SortedList)
410    OS << Sym << "\n";
411}
412
413ProfileConverter::FrameNode *
414ProfileConverter::FrameNode::getOrCreateChildFrame(const LineLocation &CallSite,
415                                                   FunctionId CalleeName) {
416  uint64_t Hash = FunctionSamples::getCallSiteHash(CalleeName, CallSite);
417  auto It = AllChildFrames.find(Hash);
418  if (It != AllChildFrames.end()) {
419    assert(It->second.FuncName == CalleeName &&
420           "Hash collision for child context node");
421    return &It->second;
422  }
423
424  AllChildFrames[Hash] = FrameNode(CalleeName, nullptr, CallSite);
425  return &AllChildFrames[Hash];
426}
427
428ProfileConverter::ProfileConverter(SampleProfileMap &Profiles)
429    : ProfileMap(Profiles) {
430  for (auto &FuncSample : Profiles) {
431    FunctionSamples *FSamples = &FuncSample.second;
432    auto *NewNode = getOrCreateContextPath(FSamples->getContext());
433    assert(!NewNode->FuncSamples && "New node cannot have sample profile");
434    NewNode->FuncSamples = FSamples;
435  }
436}
437
438ProfileConverter::FrameNode *
439ProfileConverter::getOrCreateContextPath(const SampleContext &Context) {
440  auto Node = &RootFrame;
441  LineLocation CallSiteLoc(0, 0);
442  for (auto &Callsite : Context.getContextFrames()) {
443    Node = Node->getOrCreateChildFrame(CallSiteLoc, Callsite.Func);
444    CallSiteLoc = Callsite.Location;
445  }
446  return Node;
447}
448
449void ProfileConverter::convertCSProfiles(ProfileConverter::FrameNode &Node) {
450  // Process each child profile. Add each child profile to callsite profile map
451  // of the current node `Node` if `Node` comes with a profile. Otherwise
452  // promote the child profile to a standalone profile.
453  auto *NodeProfile = Node.FuncSamples;
454  for (auto &It : Node.AllChildFrames) {
455    auto &ChildNode = It.second;
456    convertCSProfiles(ChildNode);
457    auto *ChildProfile = ChildNode.FuncSamples;
458    if (!ChildProfile)
459      continue;
460    SampleContext OrigChildContext = ChildProfile->getContext();
461    uint64_t OrigChildContextHash = OrigChildContext.getHashCode();
462    // Reset the child context to be contextless.
463    ChildProfile->getContext().setFunction(OrigChildContext.getFunction());
464    if (NodeProfile) {
465      // Add child profile to the callsite profile map.
466      auto &SamplesMap = NodeProfile->functionSamplesAt(ChildNode.CallSiteLoc);
467      SamplesMap.emplace(OrigChildContext.getFunction(), *ChildProfile);
468      NodeProfile->addTotalSamples(ChildProfile->getTotalSamples());
469      // Remove the corresponding body sample for the callsite and update the
470      // total weight.
471      auto Count = NodeProfile->removeCalledTargetAndBodySample(
472          ChildNode.CallSiteLoc.LineOffset, ChildNode.CallSiteLoc.Discriminator,
473          OrigChildContext.getFunction());
474      NodeProfile->removeTotalSamples(Count);
475    }
476
477    uint64_t NewChildProfileHash = 0;
478    // Separate child profile to be a standalone profile, if the current parent
479    // profile doesn't exist. This is a duplicating operation when the child
480    // profile is already incorporated into the parent which is still useful and
481    // thus done optionally. It is seen that duplicating context profiles into
482    // base profiles improves the code quality for thinlto build by allowing a
483    // profile in the prelink phase for to-be-fully-inlined functions.
484    if (!NodeProfile) {
485      ProfileMap[ChildProfile->getContext()].merge(*ChildProfile);
486      NewChildProfileHash = ChildProfile->getContext().getHashCode();
487    } else if (GenerateMergedBaseProfiles) {
488      ProfileMap[ChildProfile->getContext()].merge(*ChildProfile);
489      NewChildProfileHash = ChildProfile->getContext().getHashCode();
490      auto &SamplesMap = NodeProfile->functionSamplesAt(ChildNode.CallSiteLoc);
491      SamplesMap[ChildProfile->getFunction()].getContext().setAttribute(
492          ContextDuplicatedIntoBase);
493    }
494
495    // Remove the original child profile. Check if MD5 of new child profile
496    // collides with old profile, in this case the [] operator already
497    // overwritten it without the need of erase.
498    if (NewChildProfileHash != OrigChildContextHash)
499      ProfileMap.erase(OrigChildContextHash);
500  }
501}
502
503void ProfileConverter::convertCSProfiles() { convertCSProfiles(RootFrame); }
504