594 lines · 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-exception6//7//===----------------------------------------------------------------------===//8//9// This file contains common definitions used in the reading and writing of10// 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/LEB128.h"24#include "llvm/Support/raw_ostream.h"25#include <algorithm>26#include <cstdint>27#include <string>28#include <system_error>29 30using namespace llvm;31using namespace sampleprof;32 33static cl::opt<uint64_t> ProfileSymbolListCutOff(34 "profile-symbol-list-cutoff", cl::Hidden, cl::init(-1),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 38static cl::opt<bool> GenerateMergedBaseProfiles(39 "generate-merged-base-profiles",40 cl::desc("When generating nested context-sensitive profiles, always "41 "generate extra base profile for function with all its context "42 "profiles merged into it."));43 44namespace llvm {45namespace sampleprof {46bool FunctionSamples::ProfileIsProbeBased = false;47bool FunctionSamples::ProfileIsCS = false;48bool FunctionSamples::ProfileIsPreInlined = false;49bool FunctionSamples::UseMD5 = false;50bool FunctionSamples::HasUniqSuffix = true;51bool FunctionSamples::ProfileIsFS = false;52 53std::error_code54serializeTypeMap(const TypeCountMap &Map,55 const MapVector<FunctionId, uint32_t> &NameTable,56 raw_ostream &OS) {57 encodeULEB128(Map.size(), OS);58 for (const auto &[TypeName, SampleCount] : Map) {59 if (auto NameIndexIter = NameTable.find(TypeName);60 NameIndexIter != NameTable.end()) {61 encodeULEB128(NameIndexIter->second, OS);62 } else {63 // If the type is not in the name table, we cannot serialize it.64 return sampleprof_error::truncated_name_table;65 }66 encodeULEB128(SampleCount, OS);67 }68 return sampleprof_error::success;69}70} // namespace sampleprof71} // namespace llvm72 73namespace {74 75// FIXME: This class is only here to support the transition to llvm::Error. It76// will be removed once this transition is complete. Clients should prefer to77// deal with the Error value directly, rather than converting to error_code.78class SampleProfErrorCategoryType : public std::error_category {79 const char *name() const noexcept override { return "llvm.sampleprof"; }80 81 std::string message(int IE) const override {82 sampleprof_error E = static_cast<sampleprof_error>(IE);83 switch (E) {84 case sampleprof_error::success:85 return "Success";86 case sampleprof_error::bad_magic:87 return "Invalid sample profile data (bad magic)";88 case sampleprof_error::unsupported_version:89 return "Unsupported sample profile format version";90 case sampleprof_error::too_large:91 return "Too much profile data";92 case sampleprof_error::truncated:93 return "Truncated profile data";94 case sampleprof_error::malformed:95 return "Malformed sample profile data";96 case sampleprof_error::unrecognized_format:97 return "Unrecognized sample profile encoding format";98 case sampleprof_error::unsupported_writing_format:99 return "Profile encoding format unsupported for writing operations";100 case sampleprof_error::truncated_name_table:101 return "Truncated function name table";102 case sampleprof_error::not_implemented:103 return "Unimplemented feature";104 case sampleprof_error::counter_overflow:105 return "Counter overflow";106 case sampleprof_error::ostream_seek_unsupported:107 return "Ostream does not support seek";108 case sampleprof_error::uncompress_failed:109 return "Uncompress failure";110 case sampleprof_error::zlib_unavailable:111 return "Zlib is unavailable";112 case sampleprof_error::hash_mismatch:113 return "Function hash mismatch";114 case sampleprof_error::illegal_line_offset:115 return "Illegal line offset in sample profile data";116 }117 llvm_unreachable("A value of sampleprof_error has no message.");118 }119};120 121} // end anonymous namespace122 123const std::error_category &llvm::sampleprof_category() {124 static SampleProfErrorCategoryType ErrorCategory;125 return ErrorCategory;126}127 128void LineLocation::print(raw_ostream &OS) const {129 OS << LineOffset;130 if (Discriminator > 0)131 OS << "." << Discriminator;132}133 134raw_ostream &llvm::sampleprof::operator<<(raw_ostream &OS,135 const LineLocation &Loc) {136 Loc.print(OS);137 return OS;138}139 140/// Merge the samples in \p Other into this record.141/// Optionally scale sample counts by \p Weight.142sampleprof_error SampleRecord::merge(const SampleRecord &Other,143 uint64_t Weight) {144 sampleprof_error Result;145 Result = addSamples(Other.getSamples(), Weight);146 for (const auto &I : Other.getCallTargets()) {147 mergeSampleProfErrors(Result, addCalledTarget(I.first, I.second, Weight));148 }149 return Result;150}151 152std::error_code SampleRecord::serialize(153 raw_ostream &OS, const MapVector<FunctionId, uint32_t> &NameTable) const {154 encodeULEB128(getSamples(), OS);155 encodeULEB128(getCallTargets().size(), OS);156 for (const auto &J : getSortedCallTargets()) {157 FunctionId Callee = J.first;158 uint64_t CalleeSamples = J.second;159 if (auto NameIndexIter = NameTable.find(Callee);160 NameIndexIter != NameTable.end()) {161 encodeULEB128(NameIndexIter->second, OS);162 } else {163 // If the callee is not in the name table, we cannot serialize it.164 return sampleprof_error::truncated_name_table;165 }166 encodeULEB128(CalleeSamples, OS);167 }168 return sampleprof_error::success;169}170 171#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)172LLVM_DUMP_METHOD void LineLocation::dump() const { print(dbgs()); }173#endif174 175void LineLocation::serialize(raw_ostream &OS) const {176 encodeULEB128(LineOffset, OS);177 encodeULEB128(Discriminator, OS);178}179 180/// Print the sample record to the stream \p OS indented by \p Indent.181void SampleRecord::print(raw_ostream &OS, unsigned Indent) const {182 OS << NumSamples;183 if (hasCalls()) {184 OS << ", calls:";185 for (const auto &I : getSortedCallTargets())186 OS << " " << I.first << ":" << I.second;187 }188 OS << "\n";189}190 191#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)192LLVM_DUMP_METHOD void SampleRecord::dump() const { print(dbgs(), 0); }193#endif194 195raw_ostream &llvm::sampleprof::operator<<(raw_ostream &OS,196 const SampleRecord &Sample) {197 Sample.print(OS, 0);198 return OS;199}200 201static void printTypeCountMap(raw_ostream &OS, LineLocation Loc,202 const TypeCountMap &TypeCountMap) {203 if (TypeCountMap.empty()) {204 return;205 }206 OS << Loc << ": vtables: ";207 for (const auto &[Type, Count] : TypeCountMap)208 OS << Type << ":" << Count << " ";209 OS << "\n";210}211 212/// Print the samples collected for a function on stream \p OS.213void FunctionSamples::print(raw_ostream &OS, unsigned Indent) const {214 if (getFunctionHash())215 OS << "CFG checksum " << getFunctionHash() << "\n";216 217 OS << TotalSamples << ", " << TotalHeadSamples << ", " << BodySamples.size()218 << " sampled lines\n";219 220 OS.indent(Indent);221 if (!BodySamples.empty()) {222 OS << "Samples collected in the function's body {\n";223 SampleSorter<LineLocation, SampleRecord> SortedBodySamples(BodySamples);224 for (const auto &SI : SortedBodySamples.get()) {225 OS.indent(Indent + 2);226 const auto &Loc = SI->first;227 OS << SI->first << ": " << SI->second;228 if (const TypeCountMap *TypeCountMap =229 this->findCallsiteTypeSamplesAt(Loc)) {230 OS.indent(Indent + 2);231 printTypeCountMap(OS, Loc, *TypeCountMap);232 }233 }234 OS.indent(Indent);235 OS << "}\n";236 } else {237 OS << "No samples collected in the function's body\n";238 }239 240 OS.indent(Indent);241 if (!CallsiteSamples.empty()) {242 OS << "Samples collected in inlined callsites {\n";243 SampleSorter<LineLocation, FunctionSamplesMap> SortedCallsiteSamples(244 CallsiteSamples);245 for (const auto *Element : SortedCallsiteSamples.get()) {246 // Element is a pointer to a pair of LineLocation and FunctionSamplesMap.247 const auto &[Loc, FunctionSampleMap] = *Element;248 for (const FunctionSamples &FuncSample :249 llvm::make_second_range(FunctionSampleMap)) {250 OS.indent(Indent + 2);251 OS << Loc << ": inlined callee: " << FuncSample.getFunction() << ": ";252 FuncSample.print(OS, Indent + 4);253 }254 auto TypeSamplesIter = VirtualCallsiteTypeCounts.find(Loc);255 if (TypeSamplesIter != VirtualCallsiteTypeCounts.end()) {256 OS.indent(Indent + 2);257 printTypeCountMap(OS, Loc, TypeSamplesIter->second);258 }259 }260 OS.indent(Indent);261 OS << "}\n";262 } else {263 OS << "No inlined callsites in this function\n";264 }265}266 267raw_ostream &llvm::sampleprof::operator<<(raw_ostream &OS,268 const FunctionSamples &FS) {269 FS.print(OS);270 return OS;271}272 273void sampleprof::sortFuncProfiles(274 const SampleProfileMap &ProfileMap,275 std::vector<NameFunctionSamples> &SortedProfiles) {276 for (const auto &I : ProfileMap) {277 SortedProfiles.push_back(std::make_pair(I.first, &I.second));278 }279 llvm::stable_sort(SortedProfiles, [](const NameFunctionSamples &A,280 const NameFunctionSamples &B) {281 if (A.second->getTotalSamples() == B.second->getTotalSamples())282 return A.second->getContext() < B.second->getContext();283 return A.second->getTotalSamples() > B.second->getTotalSamples();284 });285}286 287unsigned FunctionSamples::getOffset(const DILocation *DIL) {288 return (DIL->getLine() - DIL->getScope()->getSubprogram()->getLine()) &289 0xffff;290}291 292LineLocation FunctionSamples::getCallSiteIdentifier(const DILocation *DIL,293 bool ProfileIsFS) {294 if (FunctionSamples::ProfileIsProbeBased) {295 // In a pseudo-probe based profile, a callsite is simply represented by the296 // ID of the probe associated with the call instruction. The probe ID is297 // encoded in the Discriminator field of the call instruction's debug298 // metadata.299 return LineLocation(PseudoProbeDwarfDiscriminator::extractProbeIndex(300 DIL->getDiscriminator()),301 0);302 } else {303 unsigned Discriminator =304 ProfileIsFS ? DIL->getDiscriminator() : DIL->getBaseDiscriminator();305 return LineLocation(FunctionSamples::getOffset(DIL), Discriminator);306 }307}308 309const FunctionSamples *FunctionSamples::findFunctionSamples(310 const DILocation *DIL, SampleProfileReaderItaniumRemapper *Remapper,311 const HashKeyMap<std::unordered_map, FunctionId, FunctionId>312 *FuncNameToProfNameMap) const {313 assert(DIL);314 SmallVector<std::pair<LineLocation, StringRef>, 10> S;315 316 const DILocation *PrevDIL = DIL;317 for (DIL = DIL->getInlinedAt(); DIL; DIL = DIL->getInlinedAt()) {318 // Use C++ linkage name if possible.319 StringRef Name = PrevDIL->getScope()->getSubprogram()->getLinkageName();320 if (Name.empty())321 Name = PrevDIL->getScope()->getSubprogram()->getName();322 S.emplace_back(FunctionSamples::getCallSiteIdentifier(323 DIL, FunctionSamples::ProfileIsFS),324 Name);325 PrevDIL = DIL;326 }327 328 if (S.size() == 0)329 return this;330 const FunctionSamples *FS = this;331 for (int i = S.size() - 1; i >= 0 && FS != nullptr; i--) {332 FS = FS->findFunctionSamplesAt(S[i].first, S[i].second, Remapper,333 FuncNameToProfNameMap);334 }335 return FS;336}337 338void FunctionSamples::findAllNames(DenseSet<FunctionId> &NameSet) const {339 NameSet.insert(getFunction());340 for (const auto &BS : BodySamples)341 NameSet.insert_range(llvm::make_first_range(BS.second.getCallTargets()));342 343 for (const auto &CS : CallsiteSamples) {344 for (const auto &NameFS : CS.second) {345 NameSet.insert(NameFS.first);346 NameFS.second.findAllNames(NameSet);347 }348 }349}350 351const FunctionSamples *FunctionSamples::findFunctionSamplesAt(352 const LineLocation &Loc, StringRef CalleeName,353 SampleProfileReaderItaniumRemapper *Remapper,354 const HashKeyMap<std::unordered_map, FunctionId, FunctionId>355 *FuncNameToProfNameMap) const {356 CalleeName = getCanonicalFnName(CalleeName);357 358 auto I = CallsiteSamples.find(mapIRLocToProfileLoc(Loc));359 if (I == CallsiteSamples.end())360 return nullptr;361 auto FS = I->second.find(getRepInFormat(CalleeName));362 if (FS != I->second.end())363 return &FS->second;364 365 if (FuncNameToProfNameMap && !FuncNameToProfNameMap->empty()) {366 auto R = FuncNameToProfNameMap->find(FunctionId(CalleeName));367 if (R != FuncNameToProfNameMap->end()) {368 CalleeName = R->second.stringRef();369 auto FS = I->second.find(getRepInFormat(CalleeName));370 if (FS != I->second.end())371 return &FS->second;372 }373 }374 375 if (Remapper) {376 if (auto NameInProfile = Remapper->lookUpNameInProfile(CalleeName)) {377 auto FS = I->second.find(getRepInFormat(*NameInProfile));378 if (FS != I->second.end())379 return &FS->second;380 }381 }382 // If we cannot find exact match of the callee name, return the FS with383 // the max total count. Only do this when CalleeName is not provided,384 // i.e., only for indirect calls.385 if (!CalleeName.empty())386 return nullptr;387 uint64_t MaxTotalSamples = 0;388 const FunctionSamples *R = nullptr;389 for (const auto &NameFS : I->second)390 if (NameFS.second.getTotalSamples() >= MaxTotalSamples) {391 MaxTotalSamples = NameFS.second.getTotalSamples();392 R = &NameFS.second;393 }394 return R;395}396 397#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)398LLVM_DUMP_METHOD void FunctionSamples::dump() const { print(dbgs(), 0); }399#endif400 401std::error_code ProfileSymbolList::read(const uint8_t *Data,402 uint64_t ListSize) {403 // Scan forward to see how many elements we expect.404 reserve(std::min<uint64_t>(ProfileSymbolListCutOff,405 std::count(Data, Data + ListSize, 0)));406 407 const char *ListStart = reinterpret_cast<const char *>(Data);408 uint64_t Size = 0;409 uint64_t StrNum = 0;410 while (Size < ListSize && StrNum < ProfileSymbolListCutOff) {411 StringRef Str(ListStart + Size);412 add(Str);413 Size += Str.size() + 1;414 StrNum++;415 }416 if (Size != ListSize && StrNum != ProfileSymbolListCutOff)417 return sampleprof_error::malformed;418 return sampleprof_error::success;419}420 421void SampleContextTrimmer::trimAndMergeColdContextProfiles(422 uint64_t ColdCountThreshold, bool TrimColdContext, bool MergeColdContext,423 uint32_t ColdContextFrameLength, bool TrimBaseProfileOnly) {424 if (!TrimColdContext && !MergeColdContext)425 return;426 427 // Nothing to merge if sample threshold is zero428 if (ColdCountThreshold == 0)429 return;430 431 // Trimming base profiles only is mainly to honor the preinliner decsion. When432 // MergeColdContext is true preinliner decsion is not honored anyway so turn433 // off TrimBaseProfileOnly.434 if (MergeColdContext)435 TrimBaseProfileOnly = false;436 437 // Filter the cold profiles from ProfileMap and move them into a tmp438 // container439 std::vector<std::pair<hash_code, const FunctionSamples *>> ColdProfiles;440 for (const auto &I : ProfileMap) {441 const SampleContext &Context = I.second.getContext();442 const FunctionSamples &FunctionProfile = I.second;443 if (FunctionProfile.getTotalSamples() < ColdCountThreshold &&444 (!TrimBaseProfileOnly || Context.isBaseContext()))445 ColdProfiles.emplace_back(I.first, &I.second);446 }447 448 // Remove the cold profile from ProfileMap and merge them into449 // MergedProfileMap by the last K frames of context450 SampleProfileMap MergedProfileMap;451 for (const auto &I : ColdProfiles) {452 if (MergeColdContext) {453 auto MergedContext = I.second->getContext().getContextFrames();454 if (ColdContextFrameLength < MergedContext.size())455 MergedContext = MergedContext.take_back(ColdContextFrameLength);456 // Need to set MergedProfile's context here otherwise it will be lost.457 FunctionSamples &MergedProfile = MergedProfileMap.create(MergedContext);458 MergedProfile.merge(*I.second);459 }460 ProfileMap.erase(I.first);461 }462 463 // Move the merged profiles into ProfileMap;464 for (const auto &I : MergedProfileMap) {465 // Filter the cold merged profile466 if (TrimColdContext && I.second.getTotalSamples() < ColdCountThreshold &&467 ProfileMap.find(I.second.getContext()) == ProfileMap.end())468 continue;469 // Merge the profile if the original profile exists, otherwise just insert470 // as a new profile. If inserted as a new profile from MergedProfileMap, it471 // already has the right context.472 auto Ret = ProfileMap.emplace(I.second.getContext(), FunctionSamples());473 FunctionSamples &OrigProfile = Ret.first->second;474 OrigProfile.merge(I.second);475 }476}477 478std::error_code ProfileSymbolList::write(raw_ostream &OS) {479 // Sort the symbols before output. If doing compression.480 // It will make the compression much more effective.481 std::vector<StringRef> SortedList(Syms.begin(), Syms.end());482 llvm::sort(SortedList);483 484 std::string OutputString;485 for (auto &Sym : SortedList) {486 OutputString.append(Sym.str());487 OutputString.append(1, '\0');488 }489 490 OS << OutputString;491 return sampleprof_error::success;492}493 494void ProfileSymbolList::dump(raw_ostream &OS) const {495 OS << "======== Dump profile symbol list ========\n";496 std::vector<StringRef> SortedList(Syms.begin(), Syms.end());497 llvm::sort(SortedList);498 499 for (auto &Sym : SortedList)500 OS << Sym << "\n";501}502 503ProfileConverter::FrameNode *504ProfileConverter::FrameNode::getOrCreateChildFrame(const LineLocation &CallSite,505 FunctionId CalleeName) {506 uint64_t Hash = FunctionSamples::getCallSiteHash(CalleeName, CallSite);507 auto It = AllChildFrames.find(Hash);508 if (It != AllChildFrames.end()) {509 assert(It->second.FuncName == CalleeName &&510 "Hash collision for child context node");511 return &It->second;512 }513 514 AllChildFrames[Hash] = FrameNode(CalleeName, nullptr, CallSite);515 return &AllChildFrames[Hash];516}517 518ProfileConverter::ProfileConverter(SampleProfileMap &Profiles)519 : ProfileMap(Profiles) {520 for (auto &FuncSample : Profiles) {521 FunctionSamples *FSamples = &FuncSample.second;522 auto *NewNode = getOrCreateContextPath(FSamples->getContext());523 assert(!NewNode->FuncSamples && "New node cannot have sample profile");524 NewNode->FuncSamples = FSamples;525 }526}527 528ProfileConverter::FrameNode *529ProfileConverter::getOrCreateContextPath(const SampleContext &Context) {530 auto Node = &RootFrame;531 LineLocation CallSiteLoc(0, 0);532 for (auto &Callsite : Context.getContextFrames()) {533 Node = Node->getOrCreateChildFrame(CallSiteLoc, Callsite.Func);534 CallSiteLoc = Callsite.Location;535 }536 return Node;537}538 539void ProfileConverter::convertCSProfiles(ProfileConverter::FrameNode &Node) {540 // Process each child profile. Add each child profile to callsite profile map541 // of the current node `Node` if `Node` comes with a profile. Otherwise542 // promote the child profile to a standalone profile.543 auto *NodeProfile = Node.FuncSamples;544 for (auto &It : Node.AllChildFrames) {545 auto &ChildNode = It.second;546 convertCSProfiles(ChildNode);547 auto *ChildProfile = ChildNode.FuncSamples;548 if (!ChildProfile)549 continue;550 SampleContext OrigChildContext = ChildProfile->getContext();551 uint64_t OrigChildContextHash = OrigChildContext.getHashCode();552 // Reset the child context to be contextless.553 ChildProfile->getContext().setFunction(OrigChildContext.getFunction());554 if (NodeProfile) {555 // Add child profile to the callsite profile map.556 auto &SamplesMap = NodeProfile->functionSamplesAt(ChildNode.CallSiteLoc);557 SamplesMap.emplace(OrigChildContext.getFunction(), *ChildProfile);558 NodeProfile->addTotalSamples(ChildProfile->getTotalSamples());559 // Remove the corresponding body sample for the callsite and update the560 // total weight.561 auto Count = NodeProfile->removeCalledTargetAndBodySample(562 ChildNode.CallSiteLoc.LineOffset, ChildNode.CallSiteLoc.Discriminator,563 OrigChildContext.getFunction());564 NodeProfile->removeTotalSamples(Count);565 }566 567 uint64_t NewChildProfileHash = 0;568 // Separate child profile to be a standalone profile, if the current parent569 // profile doesn't exist. This is a duplicating operation when the child570 // profile is already incorporated into the parent which is still useful and571 // thus done optionally. It is seen that duplicating context profiles into572 // base profiles improves the code quality for thinlto build by allowing a573 // profile in the prelink phase for to-be-fully-inlined functions.574 if (!NodeProfile) {575 ProfileMap[ChildProfile->getContext()].merge(*ChildProfile);576 NewChildProfileHash = ChildProfile->getContext().getHashCode();577 } else if (GenerateMergedBaseProfiles) {578 ProfileMap[ChildProfile->getContext()].merge(*ChildProfile);579 NewChildProfileHash = ChildProfile->getContext().getHashCode();580 auto &SamplesMap = NodeProfile->functionSamplesAt(ChildNode.CallSiteLoc);581 SamplesMap[ChildProfile->getFunction()].getContext().setAttribute(582 ContextDuplicatedIntoBase);583 }584 585 // Remove the original child profile. Check if MD5 of new child profile586 // collides with old profile, in this case the [] operator already587 // overwritten it without the need of erase.588 if (NewChildProfileHash != OrigChildContextHash)589 ProfileMap.erase(OrigChildContextHash);590 }591}592 593void ProfileConverter::convertCSProfiles() { convertCSProfiles(RootFrame); }594