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/ErrorHandling.h"
  23 #include "llvm/Support/raw_ostream.h"
  24 #include <string>
  25 #include <system_error>
  26
  27 using namespace llvm;
  28 using namespace sampleprof;
  29
  30 static 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
  35 static 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
  41 namespace llvm {
  42 namespace sampleprof {
  43 bool FunctionSamples::ProfileIsProbeBased = false;
  44 bool FunctionSamples::ProfileIsCS = false;
  45 bool FunctionSamples::ProfileIsPreInlined = false;
  46 bool FunctionSamples::UseMD5 = false;
  47 bool FunctionSamples::HasUniqSuffix = true;
  48 bool FunctionSamples::ProfileIsFS = false;
  49 } // namespace sampleprof
  50 } // namespace llvm
  51
  52 namespace {
  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.
  57 class 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
 100 const std::error_category &llvm::sampleprof_category() {
 101   static SampleProfErrorCategoryType ErrorCategory;
 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.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
 196 raw_ostream &llvm::sampleprof::operator<<(raw_ostream &OS,
 197                                           const FunctionSamples &FS) {
 198   FS.print(OS);
 199   return OS;
 200 }
 201
 202 void 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
 216 unsigned FunctionSamples::getOffset(const DILocation *DIL) {
 217   return (DIL->getLine() - DIL->getScope()->getSubprogram()->getLine()) &
 218       0xffff;
 219 }
 220
 221 LineLocation 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
 238 const 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
 264 void 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
 278 const 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)
 312 LLVM_DUMP_METHOD void FunctionSamples::dump() const { print(dbgs(), 0); }
 313 #endif
 314
 315 std::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
 331 void 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
 388 std::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
 404 void 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
 413 ProfileConverter::FrameNode *
 414 ProfileConverter::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
 428 ProfileConverter::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
 438 ProfileConverter::FrameNode *
 439 ProfileConverter::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
 449 void 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
 503 void ProfileConverter::convertCSProfiles() { convertCSProfiles(RootFrame); }