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