llvm/lib/ProfileData/SampleProf.cpp

   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 void sampleprof::sortFuncProfiles(
 202     const StringMap<FunctionSamples> &ProfileMap,
 203     std::vector<NameFunctionSamples> &SortedProfiles) {
 204   for (const auto &I : ProfileMap) {
 205     assert(I.getKey() == I.second.getNameWithContext() &&
 206            "Inconsistent profile map");
 207     SortedProfiles.push_back(
 208         std::make_pair(I.second.getNameWithContext(), &I.second));
 209   }
 210   llvm::stable_sort(SortedProfiles, [](const NameFunctionSamples &A,
 211                                        const NameFunctionSamples &B) {
 212     if (A.second->getTotalSamples() == B.second->getTotalSamples())
 213       return A.first > B.first;
 214     return A.second->getTotalSamples() > B.second->getTotalSamples();
 215   });
 216 }
 217
 218 unsigned FunctionSamples::getOffset(const DILocation *DIL) {
 219   return (DIL->getLine() - DIL->getScope()->getSubprogram()->getLine()) &
 220       0xffff;
 221 }
 222
 223 LineLocation FunctionSamples::getCallSiteIdentifier(const DILocation *DIL) {
 224   if (FunctionSamples::ProfileIsProbeBased)
 225     // In a pseudo-probe based profile, a callsite is simply represented by the
 226     // ID of the probe associated with the call instruction. The probe ID is
 227     // encoded in the Discriminator field of the call instruction's debug
 228     // metadata.
 229     return LineLocation(PseudoProbeDwarfDiscriminator::extractProbeIndex(
 230                             DIL->getDiscriminator()),
 231                         0);
 232   else
 233     return LineLocation(FunctionSamples::getOffset(DIL),
 234                         DIL->getBaseDiscriminator());
 235 }
 236
 237 const FunctionSamples *FunctionSamples::findFunctionSamples(
 238     const DILocation *DIL, SampleProfileReaderItaniumRemapper *Remapper) const {
 239   assert(DIL);
 240   SmallVector<std::pair<LineLocation, StringRef>, 10> S;
 241
 242   const DILocation *PrevDIL = DIL;
 243   for (DIL = DIL->getInlinedAt(); DIL; DIL = DIL->getInlinedAt()) {
 244     unsigned Discriminator;
 245     if (ProfileIsFS)
 246       Discriminator = DIL->getDiscriminator();
 247     else
 248       Discriminator = DIL->getBaseDiscriminator();
 249
 250     S.push_back(
 251         std::make_pair(LineLocation(getOffset(DIL), Discriminator),
 252                        PrevDIL->getScope()->getSubprogram()->getLinkageName()));
 253     PrevDIL = DIL;
 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
 264 void FunctionSamples::findAllNames(DenseSet<StringRef> &NameSet) const {
 265   NameSet.insert(Name);
 266   for (const auto &BS : BodySamples)
 267     for (const auto &TS : BS.second.getCallTargets())
 268       NameSet.insert(TS.getKey());
 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
 278 const FunctionSamples *FunctionSamples::findFunctionSamplesAt(
 279     const LineLocation &Loc, StringRef CalleeName,
 280     SampleProfileReaderItaniumRemapper *Remapper) const {
 281   CalleeName = getCanonicalFnName(CalleeName);
 282
 283   std::string CalleeGUID;
 284   CalleeName = getRepInFormat(CalleeName, UseMD5, CalleeGUID);
 285
 286   auto iter = CallsiteSamples.find(Loc);
 287   if (iter == CallsiteSamples.end())
 288     return nullptr;
 289   auto FS = iter->second.find(CalleeName);
 290   if (FS != iter->second.end())
 291     return &FS->second;
 292   if (Remapper) {
 293     if (auto NameInProfile = Remapper->lookUpNameInProfile(CalleeName)) {
 294       auto FS = iter->second.find(*NameInProfile);
 295       if (FS != iter->second.end())
 296         return &FS->second;
 297     }
 298   }
 299   // If we cannot find exact match of the callee name, return the FS with
 300   // the max total count. Only do this when CalleeName is not provided,
 301   // i.e., only for indirect calls.
 302   if (!CalleeName.empty())
 303     return nullptr;
 304   uint64_t MaxTotalSamples = 0;
 305   const FunctionSamples *R = nullptr;
 306   for (const auto &NameFS : iter->second)
 307     if (NameFS.second.getTotalSamples() >= MaxTotalSamples) {
 308       MaxTotalSamples = NameFS.second.getTotalSamples();
 309       R = &NameFS.second;
 310     }
 311   return R;
 312 }
 313
 314 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 315 LLVM_DUMP_METHOD void FunctionSamples::dump() const { print(dbgs(), 0); }
 316 #endif
 317
 318 std::error_code ProfileSymbolList::read(const uint8_t *Data,
 319                                         uint64_t ListSize) {
 320   const char *ListStart = reinterpret_cast<const char *>(Data);
 321   uint64_t Size = 0;
 322   uint64_t StrNum = 0;
 323   while (Size < ListSize && StrNum < ProfileSymbolListCutOff) {
 324     StringRef Str(ListStart + Size);
 325     add(Str);
 326     Size += Str.size() + 1;
 327     StrNum++;
 328   }
 329   if (Size != ListSize && StrNum != ProfileSymbolListCutOff)
 330     return sampleprof_error::malformed;
 331   return sampleprof_error::success;
 332 }
 333
 334 void SampleContextTrimmer::trimAndMergeColdContextProfiles(
 335     uint64_t ColdCountThreshold, bool TrimColdContext, bool MergeColdContext,
 336     uint32_t ColdContextFrameLength) {
 337   if (!TrimColdContext && !MergeColdContext)
 338     return;
 339
 340   // Nothing to merge if sample threshold is zero
 341   if (ColdCountThreshold == 0)
 342     return;
 343
 344   // Filter the cold profiles from ProfileMap and move them into a tmp
 345   // container
 346   std::vector<std::pair<StringRef, const FunctionSamples *>> ColdProfiles;
 347   for (const auto &I : ProfileMap) {
 348     const FunctionSamples &FunctionProfile = I.second;
 349     if (FunctionProfile.getTotalSamples() >= ColdCountThreshold)
 350       continue;
 351     ColdProfiles.emplace_back(I.getKey(), &I.second);
 352   }
 353
 354   // Remove the cold profile from ProfileMap and merge them into
 355   // MergedProfileMap by the last K frames of context
 356   StringMap<FunctionSamples> MergedProfileMap;
 357   for (const auto &I : ColdProfiles) {
 358     if (MergeColdContext) {
 359       auto Ret = MergedProfileMap.try_emplace(
 360           I.second->getContext().getContextWithLastKFrames(
 361               ColdContextFrameLength),
 362           FunctionSamples());
 363       FunctionSamples &MergedProfile = Ret.first->second;
 364       MergedProfile.merge(*I.second);
 365     }
 366     ProfileMap.erase(I.first);
 367   }
 368
 369   // Move the merged profiles into ProfileMap;
 370   for (const auto &I : MergedProfileMap) {
 371     // Filter the cold merged profile
 372     if (TrimColdContext && I.second.getTotalSamples() < ColdCountThreshold &&
 373         ProfileMap.find(I.getKey()) == ProfileMap.end())
 374       continue;
 375     // Merge the profile if the original profile exists, otherwise just insert
 376     // as a new profile
 377     auto Ret = ProfileMap.try_emplace(I.getKey(), FunctionSamples());
 378     if (Ret.second) {
 379       SampleContext FContext(Ret.first->first(), RawContext);
 380       FunctionSamples &FProfile = Ret.first->second;
 381       FProfile.setContext(FContext);
 382       FProfile.setName(FContext.getNameWithoutContext());
 383     }
 384     FunctionSamples &OrigProfile = Ret.first->second;
 385     OrigProfile.merge(I.second);
 386   }
 387 }
 388
 389 void SampleContextTrimmer::canonicalizeContextProfiles() {
 390   std::vector<StringRef> ProfilesToBeRemoved;
 391   StringMap<FunctionSamples> ProfilesToBeAdded;
 392   for (auto &I : ProfileMap) {
 393     FunctionSamples &FProfile = I.second;
 394     StringRef ContextStr = FProfile.getNameWithContext();
 395     if (I.first() == ContextStr)
 396       continue;
 397
 398     // Use the context string from FunctionSamples to update the keys of
 399     // ProfileMap. They can get out of sync after context profile promotion
 400     // through pre-inliner.
 401     // Duplicate the function profile for later insertion to avoid a conflict
 402     // caused by a context both to be add and to be removed. This could happen
 403     // when a context is promoted to another context which is also promoted to
 404     // the third context. For example, given an original context A @ B @ C that
 405     // is promoted to B @ C and the original context B @ C which is promoted to
 406     // just C, adding B @ C to the profile map while removing same context (but
 407     // with different profiles) from the map can cause a conflict if they are
 408     // not handled in a right order. This can be solved by just caching the
 409     // profiles to be added.
 410     auto Ret = ProfilesToBeAdded.try_emplace(ContextStr, FProfile);
 411     (void)Ret;
 412     assert(Ret.second && "Context conflict during canonicalization");
 413     ProfilesToBeRemoved.push_back(I.first());
 414   }
 415
 416   for (auto &I : ProfilesToBeRemoved) {
 417     ProfileMap.erase(I);
 418   }
 419
 420   for (auto &I : ProfilesToBeAdded) {
 421     ProfileMap.try_emplace(I.first(), I.second);
 422   }
 423 }
 424
 425 std::error_code ProfileSymbolList::write(raw_ostream &OS) {
 426   // Sort the symbols before output. If doing compression.
 427   // It will make the compression much more effective.
 428   std::vector<StringRef> SortedList(Syms.begin(), Syms.end());
 429   llvm::sort(SortedList);
 430
 431   std::string OutputString;
 432   for (auto &Sym : SortedList) {
 433     OutputString.append(Sym.str());
 434     OutputString.append(1, '\0');
 435   }
 436
 437   OS << OutputString;
 438   return sampleprof_error::success;
 439 }
 440
 441 void ProfileSymbolList::dump(raw_ostream &OS) const {
 442   OS << "======== Dump profile symbol list ========\n";
 443   std::vector<StringRef> SortedList(Syms.begin(), Syms.end());
 444   llvm::sort(SortedList);
 445
 446   for (auto &Sym : SortedList)
 447     OS << Sym << "\n";
 448 }