1 //===- SampleProf.h - Sampling profiling format support ---------*- C++ -*-===//
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 #ifndef LLVM_PROFILEDATA_SAMPLEPROF_H
15 #define LLVM_PROFILEDATA_SAMPLEPROF_H
16
17 #include "llvm/ADT/DenseSet.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/StringMap.h"
20 #include "llvm/ADT/StringRef.h"
21 #include "llvm/ADT/StringSet.h"
22 #include "llvm/IR/Function.h"
23 #include "llvm/IR/GlobalValue.h"
24 #include "llvm/IR/Module.h"
25 #include "llvm/Support/Allocator.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/ErrorOr.h"
28 #include "llvm/Support/MathExtras.h"
29 #include "llvm/Support/raw_ostream.h"
30 #include <algorithm>
31 #include <cstdint>
32 #include <list>
33 #include <map>
34 #include <set>
35 #include <sstream>
36 #include <string>
37 #include <system_error>
38 #include <unordered_map>
39 #include <utility>
40
41 namespace llvm {
42
43 const std::error_category &sampleprof_category();
44
45 enum class sampleprof_error {
46 success = 0,
47 bad_magic,
48 unsupported_version,
49 too_large,
50 truncated,
51 malformed,
52 unrecognized_format,
53 unsupported_writing_format,
54 truncated_name_table,
55 not_implemented,
56 counter_overflow,
57 ostream_seek_unsupported,
58 compress_failed,
59 uncompress_failed,
60 zlib_unavailable,
61 hash_mismatch
62 };
63
make_error_code(sampleprof_error E)64 inline std::error_code make_error_code(sampleprof_error E) {
65 return std::error_code(static_cast<int>(E), sampleprof_category());
66 }
67
MergeResult(sampleprof_error & Accumulator,sampleprof_error Result)68 inline sampleprof_error MergeResult(sampleprof_error &Accumulator,
69 sampleprof_error Result) {
70 // Prefer first error encountered as later errors may be secondary effects of
71 // the initial problem.
72 if (Accumulator == sampleprof_error::success &&
73 Result != sampleprof_error::success)
74 Accumulator = Result;
75 return Accumulator;
76 }
77
78 } // end namespace llvm
79
80 namespace std {
81
82 template <>
83 struct is_error_code_enum<llvm::sampleprof_error> : std::true_type {};
84
85 } // end namespace std
86
87 namespace llvm {
88 namespace sampleprof {
89
90 enum SampleProfileFormat {
91 SPF_None = 0,
92 SPF_Text = 0x1,
93 SPF_Compact_Binary = 0x2,
94 SPF_GCC = 0x3,
95 SPF_Ext_Binary = 0x4,
96 SPF_Binary = 0xff
97 };
98
99 static inline uint64_t SPMagic(SampleProfileFormat Format = SPF_Binary) {
100 return uint64_t('S') << (64 - 8) | uint64_t('P') << (64 - 16) |
101 uint64_t('R') << (64 - 24) | uint64_t('O') << (64 - 32) |
102 uint64_t('F') << (64 - 40) | uint64_t('4') << (64 - 48) |
103 uint64_t('2') << (64 - 56) | uint64_t(Format);
104 }
105
106 /// Get the proper representation of a string according to whether the
107 /// current Format uses MD5 to represent the string.
108 static inline StringRef getRepInFormat(StringRef Name, bool UseMD5,
109 std::string &GUIDBuf) {
110 if (Name.empty() || !UseMD5)
111 return Name;
112 GUIDBuf = std::to_string(Function::getGUID(Name));
113 return GUIDBuf;
114 }
115
116 static inline uint64_t SPVersion() { return 103; }
117
118 // Section Type used by SampleProfileExtBinaryBaseReader and
119 // SampleProfileExtBinaryBaseWriter. Never change the existing
120 // value of enum. Only append new ones.
121 enum SecType {
122 SecInValid = 0,
123 SecProfSummary = 1,
124 SecNameTable = 2,
125 SecProfileSymbolList = 3,
126 SecFuncOffsetTable = 4,
127 SecFuncMetadata = 5,
128 SecCSNameTable = 6,
129 // marker for the first type of profile.
130 SecFuncProfileFirst = 32,
131 SecLBRProfile = SecFuncProfileFirst
132 };
133
134 static inline std::string getSecName(SecType Type) {
135 switch ((int)Type) { // Avoid -Wcovered-switch-default
136 case SecInValid:
137 return "InvalidSection";
138 case SecProfSummary:
139 return "ProfileSummarySection";
140 case SecNameTable:
141 return "NameTableSection";
142 case SecProfileSymbolList:
143 return "ProfileSymbolListSection";
144 case SecFuncOffsetTable:
145 return "FuncOffsetTableSection";
146 case SecFuncMetadata:
147 return "FunctionMetadata";
148 case SecCSNameTable:
149 return "CSNameTableSection";
150 case SecLBRProfile:
151 return "LBRProfileSection";
152 default:
153 return "UnknownSection";
154 }
155 }
156
157 // Entry type of section header table used by SampleProfileExtBinaryBaseReader
158 // and SampleProfileExtBinaryBaseWriter.
159 struct SecHdrTableEntry {
160 SecType Type;
161 uint64_t Flags;
162 uint64_t Offset;
163 uint64_t Size;
164 // The index indicating the location of the current entry in
165 // SectionHdrLayout table.
166 uint32_t LayoutIndex;
167 };
168
169 // Flags common for all sections are defined here. In SecHdrTableEntry::Flags,
170 // common flags will be saved in the lower 32bits and section specific flags
171 // will be saved in the higher 32 bits.
172 enum class SecCommonFlags : uint32_t {
173 SecFlagInValid = 0,
174 SecFlagCompress = (1 << 0),
175 // Indicate the section contains only profile without context.
176 SecFlagFlat = (1 << 1)
177 };
178
179 // Section specific flags are defined here.
180 // !!!Note: Everytime a new enum class is created here, please add
181 // a new check in verifySecFlag.
182 enum class SecNameTableFlags : uint32_t {
183 SecFlagInValid = 0,
184 SecFlagMD5Name = (1 << 0),
185 // Store MD5 in fixed length instead of ULEB128 so NameTable can be
186 // accessed like an array.
187 SecFlagFixedLengthMD5 = (1 << 1),
188 // Profile contains ".__uniq." suffix name. Compiler shouldn't strip
189 // the suffix when doing profile matching when seeing the flag.
190 SecFlagUniqSuffix = (1 << 2)
191 };
192 enum class SecProfSummaryFlags : uint32_t {
193 SecFlagInValid = 0,
194 /// SecFlagPartial means the profile is for common/shared code.
195 /// The common profile is usually merged from profiles collected
196 /// from running other targets.
197 SecFlagPartial = (1 << 0),
198 /// SecFlagContext means this is context-sensitive profile for
199 /// CSSPGO
200 SecFlagFullContext = (1 << 1),
201 /// SecFlagFSDiscriminator means this profile uses flow-sensitive
202 /// discriminators.
203 SecFlagFSDiscriminator = (1 << 2)
204 };
205
206 enum class SecFuncMetadataFlags : uint32_t {
207 SecFlagInvalid = 0,
208 SecFlagIsProbeBased = (1 << 0),
209 SecFlagHasAttribute = (1 << 1)
210 };
211
212 enum class SecFuncOffsetFlags : uint32_t {
213 SecFlagInvalid = 0,
214 // Store function offsets in an order of contexts. The order ensures that
215 // callee contexts of a given context laid out next to it.
216 SecFlagOrdered = (1 << 0),
217 };
218
219 // Verify section specific flag is used for the correct section.
220 template <class SecFlagType>
221 static inline void verifySecFlag(SecType Type, SecFlagType Flag) {
222 // No verification is needed for common flags.
223 if (std::is_same<SecCommonFlags, SecFlagType>())
224 return;
225
226 // Verification starts here for section specific flag.
227 bool IsFlagLegal = false;
228 switch (Type) {
229 case SecNameTable:
230 IsFlagLegal = std::is_same<SecNameTableFlags, SecFlagType>();
231 break;
232 case SecProfSummary:
233 IsFlagLegal = std::is_same<SecProfSummaryFlags, SecFlagType>();
234 break;
235 case SecFuncMetadata:
236 IsFlagLegal = std::is_same<SecFuncMetadataFlags, SecFlagType>();
237 break;
238 default:
239 case SecFuncOffsetTable:
240 IsFlagLegal = std::is_same<SecFuncOffsetFlags, SecFlagType>();
241 break;
242 }
243 if (!IsFlagLegal)
244 llvm_unreachable("Misuse of a flag in an incompatible section");
245 }
246
247 template <class SecFlagType>
248 static inline void addSecFlag(SecHdrTableEntry &Entry, SecFlagType Flag) {
249 verifySecFlag(Entry.Type, Flag);
250 auto FVal = static_cast<uint64_t>(Flag);
251 bool IsCommon = std::is_same<SecCommonFlags, SecFlagType>();
252 Entry.Flags |= IsCommon ? FVal : (FVal << 32);
253 }
254
255 template <class SecFlagType>
256 static inline void removeSecFlag(SecHdrTableEntry &Entry, SecFlagType Flag) {
257 verifySecFlag(Entry.Type, Flag);
258 auto FVal = static_cast<uint64_t>(Flag);
259 bool IsCommon = std::is_same<SecCommonFlags, SecFlagType>();
260 Entry.Flags &= ~(IsCommon ? FVal : (FVal << 32));
261 }
262
263 template <class SecFlagType>
264 static inline bool hasSecFlag(const SecHdrTableEntry &Entry, SecFlagType Flag) {
265 verifySecFlag(Entry.Type, Flag);
266 auto FVal = static_cast<uint64_t>(Flag);
267 bool IsCommon = std::is_same<SecCommonFlags, SecFlagType>();
268 return Entry.Flags & (IsCommon ? FVal : (FVal << 32));
269 }
270
271 /// Represents the relative location of an instruction.
272 ///
273 /// Instruction locations are specified by the line offset from the
274 /// beginning of the function (marked by the line where the function
275 /// header is) and the discriminator value within that line.
276 ///
277 /// The discriminator value is useful to distinguish instructions
278 /// that are on the same line but belong to different basic blocks
279 /// (e.g., the two post-increment instructions in "if (p) x++; else y++;").
280 struct LineLocation {
281 LineLocation(uint32_t L, uint32_t D) : LineOffset(L), Discriminator(D) {}
282
283 void print(raw_ostream &OS) const;
284 void dump() const;
285
286 bool operator<(const LineLocation &O) const {
287 return LineOffset < O.LineOffset ||
288 (LineOffset == O.LineOffset && Discriminator < O.Discriminator);
289 }
290
291 bool operator==(const LineLocation &O) const {
292 return LineOffset == O.LineOffset && Discriminator == O.Discriminator;
293 }
294
295 bool operator!=(const LineLocation &O) const {
296 return LineOffset != O.LineOffset || Discriminator != O.Discriminator;
297 }
298
299 uint32_t LineOffset;
300 uint32_t Discriminator;
301 };
302
303 raw_ostream &operator<<(raw_ostream &OS, const LineLocation &Loc);
304
305 /// Representation of a single sample record.
306 ///
307 /// A sample record is represented by a positive integer value, which
308 /// indicates how frequently was the associated line location executed.
309 ///
310 /// Additionally, if the associated location contains a function call,
311 /// the record will hold a list of all the possible called targets. For
312 /// direct calls, this will be the exact function being invoked. For
313 /// indirect calls (function pointers, virtual table dispatch), this
314 /// will be a list of one or more functions.
315 class SampleRecord {
316 public:
317 using CallTarget = std::pair<StringRef, uint64_t>;
318 struct CallTargetComparator {
319 bool operator()(const CallTarget &LHS, const CallTarget &RHS) const {
320 if (LHS.second != RHS.second)
321 return LHS.second > RHS.second;
322
323 return LHS.first < RHS.first;
324 }
325 };
326
327 using SortedCallTargetSet = std::set<CallTarget, CallTargetComparator>;
328 using CallTargetMap = StringMap<uint64_t>;
329 SampleRecord() = default;
330
331 /// Increment the number of samples for this record by \p S.
332 /// Optionally scale sample count \p S by \p Weight.
333 ///
334 /// Sample counts accumulate using saturating arithmetic, to avoid wrapping
335 /// around unsigned integers.
336 sampleprof_error addSamples(uint64_t S, uint64_t Weight = 1) {
337 bool Overflowed;
338 NumSamples = SaturatingMultiplyAdd(S, Weight, NumSamples, &Overflowed);
339 return Overflowed ? sampleprof_error::counter_overflow
340 : sampleprof_error::success;
341 }
342
343 /// Add called function \p F with samples \p S.
344 /// Optionally scale sample count \p S by \p Weight.
345 ///
346 /// Sample counts accumulate using saturating arithmetic, to avoid wrapping
347 /// around unsigned integers.
348 sampleprof_error addCalledTarget(StringRef F, uint64_t S,
349 uint64_t Weight = 1) {
350 uint64_t &TargetSamples = CallTargets[F];
351 bool Overflowed;
352 TargetSamples =
353 SaturatingMultiplyAdd(S, Weight, TargetSamples, &Overflowed);
354 return Overflowed ? sampleprof_error::counter_overflow
355 : sampleprof_error::success;
356 }
357
358 /// Return true if this sample record contains function calls.
359 bool hasCalls() const { return !CallTargets.empty(); }
360
361 uint64_t getSamples() const { return NumSamples; }
362 const CallTargetMap &getCallTargets() const { return CallTargets; }
363 const SortedCallTargetSet getSortedCallTargets() const {
364 return SortCallTargets(CallTargets);
365 }
366
367 /// Sort call targets in descending order of call frequency.
368 static const SortedCallTargetSet SortCallTargets(const CallTargetMap &Targets) {
369 SortedCallTargetSet SortedTargets;
370 for (const auto &I : Targets) {
371 SortedTargets.emplace(I.first(), I.second);
372 }
373 return SortedTargets;
374 }
375
376 /// Prorate call targets by a distribution factor.
377 static const CallTargetMap adjustCallTargets(const CallTargetMap &Targets,
378 float DistributionFactor) {
379 CallTargetMap AdjustedTargets;
380 for (const auto &I : Targets) {
381 AdjustedTargets[I.first()] = I.second * DistributionFactor;
382 }
383 return AdjustedTargets;
384 }
385
386 /// Merge the samples in \p Other into this record.
387 /// Optionally scale sample counts by \p Weight.
388 sampleprof_error merge(const SampleRecord &Other, uint64_t Weight = 1);
389 void print(raw_ostream &OS, unsigned Indent) const;
390 void dump() const;
391
392 private:
393 uint64_t NumSamples = 0;
394 CallTargetMap CallTargets;
395 };
396
397 raw_ostream &operator<<(raw_ostream &OS, const SampleRecord &Sample);
398
399 // State of context associated with FunctionSamples
400 enum ContextStateMask {
401 UnknownContext = 0x0, // Profile without context
402 RawContext = 0x1, // Full context profile from input profile
403 SyntheticContext = 0x2, // Synthetic context created for context promotion
404 InlinedContext = 0x4, // Profile for context that is inlined into caller
405 MergedContext = 0x8 // Profile for context merged into base profile
406 };
407
408 // Attribute of context associated with FunctionSamples
409 enum ContextAttributeMask {
410 ContextNone = 0x0,
411 ContextWasInlined = 0x1, // Leaf of context was inlined in previous build
412 ContextShouldBeInlined = 0x2, // Leaf of context should be inlined
413 };
414
415 // Represents a context frame with function name and line location
416 struct SampleContextFrame {
417 StringRef FuncName;
418 LineLocation Location;
419
420 SampleContextFrame() : Location(0, 0) {}
421
422 SampleContextFrame(StringRef FuncName, LineLocation Location)
423 : FuncName(FuncName), Location(Location) {}
424
425 bool operator==(const SampleContextFrame &That) const {
426 return Location == That.Location && FuncName == That.FuncName;
427 }
428
429 bool operator!=(const SampleContextFrame &That) const {
430 return !(*this == That);
431 }
432
433 std::string toString(bool OutputLineLocation) const {
434 std::ostringstream OContextStr;
435 OContextStr << FuncName.str();
436 if (OutputLineLocation) {
437 OContextStr << ":" << Location.LineOffset;
438 if (Location.Discriminator)
439 OContextStr << "." << Location.Discriminator;
440 }
441 return OContextStr.str();
442 }
443 };
444
445 static inline hash_code hash_value(const SampleContextFrame &arg) {
446 return hash_combine(arg.FuncName, arg.Location.LineOffset,
447 arg.Location.Discriminator);
448 }
449
450 using SampleContextFrameVector = SmallVector<SampleContextFrame, 10>;
451 using SampleContextFrames = ArrayRef<SampleContextFrame>;
452
453 struct SampleContextFrameHash {
454 uint64_t operator()(const SampleContextFrameVector &S) const {
455 return hash_combine_range(S.begin(), S.end());
456 }
457 };
458
459 // Sample context for FunctionSamples. It consists of the calling context,
460 // the function name and context state. Internally sample context is represented
461 // using ArrayRef, which is also the input for constructing a `SampleContext`.
462 // It can accept and represent both full context string as well as context-less
463 // function name.
464 // For a CS profile, a full context vector can look like:
465 // `main:3 _Z5funcAi:1 _Z8funcLeafi`
466 // For a base CS profile without calling context, the context vector should only
467 // contain the leaf frame name.
468 // For a non-CS profile, the context vector should be empty.
469 class SampleContext {
470 public:
471 SampleContext() : State(UnknownContext), Attributes(ContextNone) {}
472
473 SampleContext(StringRef Name)
474 : Name(Name), State(UnknownContext), Attributes(ContextNone) {}
475
476 SampleContext(SampleContextFrames Context,
477 ContextStateMask CState = RawContext)
478 : Attributes(ContextNone) {
479 assert(!Context.empty() && "Context is empty");
480 setContext(Context, CState);
481 }
482
483 // Give a context string, decode and populate internal states like
484 // Function name, Calling context and context state. Example of input
485 // `ContextStr`: `[main:3 @ _Z5funcAi:1 @ _Z8funcLeafi]`
486 SampleContext(StringRef ContextStr,
487 std::list<SampleContextFrameVector> &CSNameTable,
488 ContextStateMask CState = RawContext)
489 : Attributes(ContextNone) {
490 assert(!ContextStr.empty());
491 // Note that `[]` wrapped input indicates a full context string, otherwise
492 // it's treated as context-less function name only.
493 bool HasContext = ContextStr.startswith("[");
494 if (!HasContext) {
495 State = UnknownContext;
496 Name = ContextStr;
497 } else {
498 // Remove encapsulating '[' and ']' if any
499 ContextStr = ContextStr.substr(1, ContextStr.size() - 2);
500 CSNameTable.emplace_back();
501 SampleContextFrameVector &Context = CSNameTable.back();
502 /// Create a context vector from a given context string and save it in
503 /// `Context`.
504 StringRef ContextRemain = ContextStr;
505 StringRef ChildContext;
506 StringRef CalleeName;
507 while (!ContextRemain.empty()) {
508 auto ContextSplit = ContextRemain.split(" @ ");
509 ChildContext = ContextSplit.first;
510 ContextRemain = ContextSplit.second;
511 LineLocation CallSiteLoc(0, 0);
512 decodeContextString(ChildContext, CalleeName, CallSiteLoc);
513 Context.emplace_back(CalleeName, CallSiteLoc);
514 }
515
516 setContext(Context, CState);
517 }
518 }
519
520 // Promote context by removing top frames with the length of
521 // `ContextFramesToRemove`. Note that with array representation of context,
522 // the promotion is effectively a slice operation with first
523 // `ContextFramesToRemove` elements removed from left.
524 void promoteOnPath(uint32_t ContextFramesToRemove) {
525 assert(ContextFramesToRemove <= FullContext.size() &&
526 "Cannot remove more than the whole context");
527 FullContext = FullContext.drop_front(ContextFramesToRemove);
528 }
529
530 // Decode context string for a frame to get function name and location.
531 // `ContextStr` is in the form of `FuncName:StartLine.Discriminator`.
532 static void decodeContextString(StringRef ContextStr, StringRef &FName,
533 LineLocation &LineLoc) {
534 // Get function name
535 auto EntrySplit = ContextStr.split(':');
536 FName = EntrySplit.first;
537
538 LineLoc = {0, 0};
539 if (!EntrySplit.second.empty()) {
540 // Get line offset, use signed int for getAsInteger so string will
541 // be parsed as signed.
542 int LineOffset = 0;
543 auto LocSplit = EntrySplit.second.split('.');
544 LocSplit.first.getAsInteger(10, LineOffset);
545 LineLoc.LineOffset = LineOffset;
546
547 // Get discriminator
548 if (!LocSplit.second.empty())
549 LocSplit.second.getAsInteger(10, LineLoc.Discriminator);
550 }
551 }
552
553 operator SampleContextFrames() const { return FullContext; }
554 bool hasAttribute(ContextAttributeMask A) { return Attributes & (uint32_t)A; }
555 void setAttribute(ContextAttributeMask A) { Attributes |= (uint32_t)A; }
556 uint32_t getAllAttributes() { return Attributes; }
557 void setAllAttributes(uint32_t A) { Attributes = A; }
558 bool hasState(ContextStateMask S) { return State & (uint32_t)S; }
559 void setState(ContextStateMask S) { State |= (uint32_t)S; }
560 void clearState(ContextStateMask S) { State &= (uint32_t)~S; }
561 bool hasContext() const { return State != UnknownContext; }
562 bool isBaseContext() const { return FullContext.size() == 1; }
563 StringRef getName() const { return Name; }
564 SampleContextFrames getContextFrames() const { return FullContext; }
565
566 static std::string getContextString(SampleContextFrames Context,
567 bool IncludeLeafLineLocation = false) {
568 std::ostringstream OContextStr;
569 for (uint32_t I = 0; I < Context.size(); I++) {
570 if (OContextStr.str().size()) {
571 OContextStr << " @ ";
572 }
573 OContextStr << Context[I].toString(I != Context.size() - 1 ||
574 IncludeLeafLineLocation);
575 }
576 return OContextStr.str();
577 }
578
579 std::string toString() const {
580 if (!hasContext())
581 return Name.str();
582 return getContextString(FullContext, false);
583 }
584
585 uint64_t getHashCode() const {
586 return hasContext() ? hash_value(getContextFrames())
587 : hash_value(getName());
588 }
589
590 /// Set the name of the function.
591 void setName(StringRef FunctionName) {
592 assert(FullContext.empty() &&
593 "setName should only be called for non-CS profile");
594 Name = FunctionName;
595 }
596
597 void setContext(SampleContextFrames Context,
598 ContextStateMask CState = RawContext) {
599 assert(CState != UnknownContext);
600 FullContext = Context;
601 Name = Context.back().FuncName;
602 State = CState;
603 }
604
605 bool operator==(const SampleContext &That) const {
606 return State == That.State && Name == That.Name &&
607 FullContext == That.FullContext;
608 }
609
610 bool operator!=(const SampleContext &That) const { return !(*this == That); }
611
612 bool operator<(const SampleContext &That) const {
613 if (State != That.State)
614 return State < That.State;
615
616 if (!hasContext()) {
617 return (Name.compare(That.Name)) == -1;
618 }
619
620 uint64_t I = 0;
621 while (I < std::min(FullContext.size(), That.FullContext.size())) {
622 auto &Context1 = FullContext[I];
623 auto &Context2 = That.FullContext[I];
624 auto V = Context1.FuncName.compare(Context2.FuncName);
625 if (V)
626 return V == -1;
627 if (Context1.Location != Context2.Location)
628 return Context1.Location < Context2.Location;
629 I++;
630 }
631
632 return FullContext.size() < That.FullContext.size();
633 }
634
635 struct Hash {
636 uint64_t operator()(const SampleContext &Context) const {
637 return Context.getHashCode();
638 }
639 };
640
641 bool IsPrefixOf(const SampleContext &That) const {
642 auto ThisContext = FullContext;
643 auto ThatContext = That.FullContext;
644 if (ThatContext.size() < ThisContext.size())
645 return false;
646 ThatContext = ThatContext.take_front(ThisContext.size());
647 // Compare Leaf frame first
648 if (ThisContext.back().FuncName != ThatContext.back().FuncName)
649 return false;
650 // Compare leading context
651 return ThisContext.drop_back() == ThatContext.drop_back();
652 }
653
654 private:
655 /// Mangled name of the function.
656 StringRef Name;
657 // Full context including calling context and leaf function name
658 SampleContextFrames FullContext;
659 // State of the associated sample profile
660 uint32_t State;
661 // Attribute of the associated sample profile
662 uint32_t Attributes;
663 };
664
665 static inline hash_code hash_value(const SampleContext &arg) {
666 return arg.hasContext() ? hash_value(arg.getContextFrames())
667 : hash_value(arg.getName());
668 }
669
670 class FunctionSamples;
671 class SampleProfileReaderItaniumRemapper;
672
673 using BodySampleMap = std::map<LineLocation, SampleRecord>;
674 // NOTE: Using a StringMap here makes parsed profiles consume around 17% more
675 // memory, which is *very* significant for large profiles.
676 using FunctionSamplesMap = std::map<std::string, FunctionSamples, std::less<>>;
677 using CallsiteSampleMap = std::map<LineLocation, FunctionSamplesMap>;
678
679 /// Representation of the samples collected for a function.
680 ///
681 /// This data structure contains all the collected samples for the body
682 /// of a function. Each sample corresponds to a LineLocation instance
683 /// within the body of the function.
684 class FunctionSamples {
685 public:
686 FunctionSamples() = default;
687
688 void print(raw_ostream &OS = dbgs(), unsigned Indent = 0) const;
689 void dump() const;
690
691 sampleprof_error addTotalSamples(uint64_t Num, uint64_t Weight = 1) {
692 bool Overflowed;
693 TotalSamples =
694 SaturatingMultiplyAdd(Num, Weight, TotalSamples, &Overflowed);
695 return Overflowed ? sampleprof_error::counter_overflow
696 : sampleprof_error::success;
697 }
698
699 void setTotalSamples(uint64_t Num) { TotalSamples = Num; }
700
701 sampleprof_error addHeadSamples(uint64_t Num, uint64_t Weight = 1) {
702 bool Overflowed;
703 TotalHeadSamples =
704 SaturatingMultiplyAdd(Num, Weight, TotalHeadSamples, &Overflowed);
705 return Overflowed ? sampleprof_error::counter_overflow
706 : sampleprof_error::success;
707 }
708
709 sampleprof_error addBodySamples(uint32_t LineOffset, uint32_t Discriminator,
710 uint64_t Num, uint64_t Weight = 1) {
711 return BodySamples[LineLocation(LineOffset, Discriminator)].addSamples(
712 Num, Weight);
713 }
714
715 sampleprof_error addCalledTargetSamples(uint32_t LineOffset,
716 uint32_t Discriminator,
717 StringRef FName, uint64_t Num,
718 uint64_t Weight = 1) {
719 return BodySamples[LineLocation(LineOffset, Discriminator)].addCalledTarget(
720 FName, Num, Weight);
721 }
722
723 sampleprof_error addBodySamplesForProbe(uint32_t Index, uint64_t Num,
724 uint64_t Weight = 1) {
725 SampleRecord S;
726 S.addSamples(Num, Weight);
727 return BodySamples[LineLocation(Index, 0)].merge(S, Weight);
728 }
729
730 /// Return the number of samples collected at the given location.
731 /// Each location is specified by \p LineOffset and \p Discriminator.
732 /// If the location is not found in profile, return error.
733 ErrorOr<uint64_t> findSamplesAt(uint32_t LineOffset,
734 uint32_t Discriminator) const {
735 const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator));
736 if (ret == BodySamples.end())
737 return std::error_code();
738 return ret->second.getSamples();
739 }
740
741 /// Returns the call target map collected at a given location.
742 /// Each location is specified by \p LineOffset and \p Discriminator.
743 /// If the location is not found in profile, return error.
744 ErrorOr<SampleRecord::CallTargetMap>
745 findCallTargetMapAt(uint32_t LineOffset, uint32_t Discriminator) const {
746 const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator));
747 if (ret == BodySamples.end())
748 return std::error_code();
749 return ret->second.getCallTargets();
750 }
751
752 /// Returns the call target map collected at a given location specified by \p
753 /// CallSite. If the location is not found in profile, return error.
754 ErrorOr<SampleRecord::CallTargetMap>
755 findCallTargetMapAt(const LineLocation &CallSite) const {
756 const auto &Ret = BodySamples.find(CallSite);
757 if (Ret == BodySamples.end())
758 return std::error_code();
759 return Ret->second.getCallTargets();
760 }
761
762 /// Return the function samples at the given callsite location.
763 FunctionSamplesMap &functionSamplesAt(const LineLocation &Loc) {
764 return CallsiteSamples[Loc];
765 }
766
767 /// Returns the FunctionSamplesMap at the given \p Loc.
768 const FunctionSamplesMap *
769 findFunctionSamplesMapAt(const LineLocation &Loc) const {
770 auto iter = CallsiteSamples.find(Loc);
771 if (iter == CallsiteSamples.end())
772 return nullptr;
773 return &iter->second;
774 }
775
776 /// Returns a pointer to FunctionSamples at the given callsite location
777 /// \p Loc with callee \p CalleeName. If no callsite can be found, relax
778 /// the restriction to return the FunctionSamples at callsite location
779 /// \p Loc with the maximum total sample count. If \p Remapper is not
780 /// nullptr, use \p Remapper to find FunctionSamples with equivalent name
781 /// as \p CalleeName.
782 const FunctionSamples *
783 findFunctionSamplesAt(const LineLocation &Loc, StringRef CalleeName,
784 SampleProfileReaderItaniumRemapper *Remapper) const;
785
786 bool empty() const { return TotalSamples == 0; }
787
788 /// Return the total number of samples collected inside the function.
789 uint64_t getTotalSamples() const { return TotalSamples; }
790
791 /// Return the total number of branch samples that have the function as the
792 /// branch target. This should be equivalent to the sample of the first
793 /// instruction of the symbol. But as we directly get this info for raw
794 /// profile without referring to potentially inaccurate debug info, this
795 /// gives more accurate profile data and is preferred for standalone symbols.
796 uint64_t getHeadSamples() const { return TotalHeadSamples; }
797
798 /// Return the sample count of the first instruction of the function.
799 /// The function can be either a standalone symbol or an inlined function.
800 uint64_t getEntrySamples() const {
801 if (FunctionSamples::ProfileIsCS && getHeadSamples()) {
802 // For CS profile, if we already have more accurate head samples
803 // counted by branch sample from caller, use them as entry samples.
804 return getHeadSamples();
805 }
806 uint64_t Count = 0;
807 // Use either BodySamples or CallsiteSamples which ever has the smaller
808 // lineno.
809 if (!BodySamples.empty() &&
810 (CallsiteSamples.empty() ||
811 BodySamples.begin()->first < CallsiteSamples.begin()->first))
812 Count = BodySamples.begin()->second.getSamples();
813 else if (!CallsiteSamples.empty()) {
814 // An indirect callsite may be promoted to several inlined direct calls.
815 // We need to get the sum of them.
816 for (const auto &N_FS : CallsiteSamples.begin()->second)
817 Count += N_FS.second.getEntrySamples();
818 }
819 // Return at least 1 if total sample is not 0.
820 return Count ? Count : TotalSamples > 0;
821 }
822
823 /// Return all the samples collected in the body of the function.
824 const BodySampleMap &getBodySamples() const { return BodySamples; }
825
826 /// Return all the callsite samples collected in the body of the function.
827 const CallsiteSampleMap &getCallsiteSamples() const {
828 return CallsiteSamples;
829 }
830
831 /// Return the maximum of sample counts in a function body including functions
832 /// inlined in it.
833 uint64_t getMaxCountInside() const {
834 uint64_t MaxCount = 0;
835 for (const auto &L : getBodySamples())
836 MaxCount = std::max(MaxCount, L.second.getSamples());
837 for (const auto &C : getCallsiteSamples())
838 for (const FunctionSamplesMap::value_type &F : C.second)
839 MaxCount = std::max(MaxCount, F.second.getMaxCountInside());
840 return MaxCount;
841 }
842
843 /// Merge the samples in \p Other into this one.
844 /// Optionally scale samples by \p Weight.
845 sampleprof_error merge(const FunctionSamples &Other, uint64_t Weight = 1) {
846 sampleprof_error Result = sampleprof_error::success;
847 if (!GUIDToFuncNameMap)
848 GUIDToFuncNameMap = Other.GUIDToFuncNameMap;
849 if (Context.getName().empty())
850 Context = Other.getContext();
851 if (FunctionHash == 0) {
852 // Set the function hash code for the target profile.
853 FunctionHash = Other.getFunctionHash();
854 } else if (FunctionHash != Other.getFunctionHash()) {
855 // The two profiles coming with different valid hash codes indicates
856 // either:
857 // 1. They are same-named static functions from different compilation
858 // units (without using -unique-internal-linkage-names), or
859 // 2. They are really the same function but from different compilations.
860 // Let's bail out in either case for now, which means one profile is
861 // dropped.
862 return sampleprof_error::hash_mismatch;
863 }
864
865 MergeResult(Result, addTotalSamples(Other.getTotalSamples(), Weight));
866 MergeResult(Result, addHeadSamples(Other.getHeadSamples(), Weight));
867 for (const auto &I : Other.getBodySamples()) {
868 const LineLocation &Loc = I.first;
869 const SampleRecord &Rec = I.second;
870 MergeResult(Result, BodySamples[Loc].merge(Rec, Weight));
871 }
872 for (const auto &I : Other.getCallsiteSamples()) {
873 const LineLocation &Loc = I.first;
874 FunctionSamplesMap &FSMap = functionSamplesAt(Loc);
875 for (const auto &Rec : I.second)
876 MergeResult(Result, FSMap[Rec.first].merge(Rec.second, Weight));
877 }
878 return Result;
879 }
880
881 /// Recursively traverses all children, if the total sample count of the
882 /// corresponding function is no less than \p Threshold, add its corresponding
883 /// GUID to \p S. Also traverse the BodySamples to add hot CallTarget's GUID
884 /// to \p S.
885 void findInlinedFunctions(DenseSet<GlobalValue::GUID> &S,
886 const StringMap<Function *> &SymbolMap,
887 uint64_t Threshold) const {
888 if (TotalSamples <= Threshold)
889 return;
890 auto isDeclaration = [](const Function *F) {
891 return !F || F->isDeclaration();
892 };
893 if (isDeclaration(SymbolMap.lookup(getFuncName()))) {
894 // Add to the import list only when it's defined out of module.
895 S.insert(getGUID(getName()));
896 }
897 // Import hot CallTargets, which may not be available in IR because full
898 // profile annotation cannot be done until backend compilation in ThinLTO.
899 for (const auto &BS : BodySamples)
900 for (const auto &TS : BS.second.getCallTargets())
901 if (TS.getValue() > Threshold) {
902 const Function *Callee = SymbolMap.lookup(getFuncName(TS.getKey()));
903 if (isDeclaration(Callee))
904 S.insert(getGUID(TS.getKey()));
905 }
906 for (const auto &CS : CallsiteSamples)
907 for (const auto &NameFS : CS.second)
908 NameFS.second.findInlinedFunctions(S, SymbolMap, Threshold);
909 }
910
911 /// Set the name of the function.
912 void setName(StringRef FunctionName) { Context.setName(FunctionName); }
913
914 /// Return the function name.
915 StringRef getName() const { return Context.getName(); }
916
917 /// Return the original function name.
918 StringRef getFuncName() const { return getFuncName(getName()); }
919
920 void setFunctionHash(uint64_t Hash) { FunctionHash = Hash; }
921
922 uint64_t getFunctionHash() const { return FunctionHash; }
923
924 /// Return the canonical name for a function, taking into account
925 /// suffix elision policy attributes.
926 static StringRef getCanonicalFnName(const Function &F) {
927 auto AttrName = "sample-profile-suffix-elision-policy";
928 auto Attr = F.getFnAttribute(AttrName).getValueAsString();
929 return getCanonicalFnName(F.getName(), Attr);
930 }
931
932 /// Name suffixes which canonicalization should handle to avoid
933 /// profile mismatch.
934 static constexpr const char *LLVMSuffix = ".llvm.";
935 static constexpr const char *PartSuffix = ".part.";
936 static constexpr const char *UniqSuffix = ".__uniq.";
937
938 static StringRef getCanonicalFnName(StringRef FnName,
939 StringRef Attr = "selected") {
940 // Note the sequence of the suffixes in the knownSuffixes array matters.
941 // If suffix "A" is appended after the suffix "B", "A" should be in front
942 // of "B" in knownSuffixes.
943 const char *knownSuffixes[] = {LLVMSuffix, PartSuffix, UniqSuffix};
944 if (Attr == "" || Attr == "all") {
945 return FnName.split('.').first;
946 } else if (Attr == "selected") {
947 StringRef Cand(FnName);
948 for (const auto &Suf : knownSuffixes) {
949 StringRef Suffix(Suf);
950 // If the profile contains ".__uniq." suffix, don't strip the
951 // suffix for names in the IR.
952 if (Suffix == UniqSuffix && FunctionSamples::HasUniqSuffix)
953 continue;
954 auto It = Cand.rfind(Suffix);
955 if (It == StringRef::npos)
956 continue;
957 auto Dit = Cand.rfind('.');
958 if (Dit == It + Suffix.size() - 1)
959 Cand = Cand.substr(0, It);
960 }
961 return Cand;
962 } else if (Attr == "none") {
963 return FnName;
964 } else {
965 assert(false && "internal error: unknown suffix elision policy");
966 }
967 return FnName;
968 }
969
970 /// Translate \p Name into its original name.
971 /// When profile doesn't use MD5, \p Name needs no translation.
972 /// When profile uses MD5, \p Name in current FunctionSamples
973 /// is actually GUID of the original function name. getFuncName will
974 /// translate \p Name in current FunctionSamples into its original name
975 /// by looking up in the function map GUIDToFuncNameMap.
976 /// If the original name doesn't exist in the map, return empty StringRef.
977 StringRef getFuncName(StringRef Name) const {
978 if (!UseMD5)
979 return Name;
980
981 assert(GUIDToFuncNameMap && "GUIDToFuncNameMap needs to be populated first");
982 return GUIDToFuncNameMap->lookup(std::stoull(Name.data()));
983 }
984
985 /// Returns the line offset to the start line of the subprogram.
986 /// We assume that a single function will not exceed 65535 LOC.
987 static unsigned getOffset(const DILocation *DIL);
988
989 /// Returns a unique call site identifier for a given debug location of a call
990 /// instruction. This is wrapper of two scenarios, the probe-based profile and
991 /// regular profile, to hide implementation details from the sample loader and
992 /// the context tracker.
993 static LineLocation getCallSiteIdentifier(const DILocation *DIL);
994
995 /// Get the FunctionSamples of the inline instance where DIL originates
996 /// from.
997 ///
998 /// The FunctionSamples of the instruction (Machine or IR) associated to
999 /// \p DIL is the inlined instance in which that instruction is coming from.
1000 /// We traverse the inline stack of that instruction, and match it with the
1001 /// tree nodes in the profile.
1002 ///
1003 /// \returns the FunctionSamples pointer to the inlined instance.
1004 /// If \p Remapper is not nullptr, it will be used to find matching
1005 /// FunctionSamples with not exactly the same but equivalent name.
1006 const FunctionSamples *findFunctionSamples(
1007 const DILocation *DIL,
1008 SampleProfileReaderItaniumRemapper *Remapper = nullptr) const;
1009
1010 static bool ProfileIsProbeBased;
1011
1012 static bool ProfileIsCS;
1013
1014 SampleContext &getContext() const { return Context; }
1015
1016 void setContext(const SampleContext &FContext) { Context = FContext; }
1017
1018 static SampleProfileFormat Format;
1019
1020 /// Whether the profile uses MD5 to represent string.
1021 static bool UseMD5;
1022
1023 /// Whether the profile contains any ".__uniq." suffix in a name.
1024 static bool HasUniqSuffix;
1025
1026 /// If this profile uses flow sensitive discriminators.
1027 static bool ProfileIsFS;
1028
1029 /// GUIDToFuncNameMap saves the mapping from GUID to the symbol name, for
1030 /// all the function symbols defined or declared in current module.
1031 DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap = nullptr;
1032
1033 // Assume the input \p Name is a name coming from FunctionSamples itself.
1034 // If UseMD5 is true, the name is already a GUID and we
1035 // don't want to return the GUID of GUID.
1036 static uint64_t getGUID(StringRef Name) {
1037 return UseMD5 ? std::stoull(Name.data()) : Function::getGUID(Name);
1038 }
1039
1040 // Find all the names in the current FunctionSamples including names in
1041 // all the inline instances and names of call targets.
1042 void findAllNames(DenseSet<StringRef> &NameSet) const;
1043
1044 private:
1045 /// CFG hash value for the function.
1046 uint64_t FunctionHash = 0;
1047
1048 /// Calling context for function profile
1049 mutable SampleContext Context;
1050
1051 /// Total number of samples collected inside this function.
1052 ///
1053 /// Samples are cumulative, they include all the samples collected
1054 /// inside this function and all its inlined callees.
1055 uint64_t TotalSamples = 0;
1056
1057 /// Total number of samples collected at the head of the function.
1058 /// This is an approximation of the number of calls made to this function
1059 /// at runtime.
1060 uint64_t TotalHeadSamples = 0;
1061
1062 /// Map instruction locations to collected samples.
1063 ///
1064 /// Each entry in this map contains the number of samples
1065 /// collected at the corresponding line offset. All line locations
1066 /// are an offset from the start of the function.
1067 BodySampleMap BodySamples;
1068
1069 /// Map call sites to collected samples for the called function.
1070 ///
1071 /// Each entry in this map corresponds to all the samples
1072 /// collected for the inlined function call at the given
1073 /// location. For example, given:
1074 ///
1075 /// void foo() {
1076 /// 1 bar();
1077 /// ...
1078 /// 8 baz();
1079 /// }
1080 ///
1081 /// If the bar() and baz() calls were inlined inside foo(), this
1082 /// map will contain two entries. One for all the samples collected
1083 /// in the call to bar() at line offset 1, the other for all the samples
1084 /// collected in the call to baz() at line offset 8.
1085 CallsiteSampleMap CallsiteSamples;
1086 };
1087
1088 raw_ostream &operator<<(raw_ostream &OS, const FunctionSamples &FS);
1089
1090 using SampleProfileMap =
1091 std::unordered_map<SampleContext, FunctionSamples, SampleContext::Hash>;
1092
1093 using NameFunctionSamples = std::pair<SampleContext, const FunctionSamples *>;
1094
1095 void sortFuncProfiles(const SampleProfileMap &ProfileMap,
1096 std::vector<NameFunctionSamples> &SortedProfiles);
1097
1098 /// Sort a LocationT->SampleT map by LocationT.
1099 ///
1100 /// It produces a sorted list of <LocationT, SampleT> records by ascending
1101 /// order of LocationT.
1102 template <class LocationT, class SampleT> class SampleSorter {
1103 public:
1104 using SamplesWithLoc = std::pair<const LocationT, SampleT>;
1105 using SamplesWithLocList = SmallVector<const SamplesWithLoc *, 20>;
1106
1107 SampleSorter(const std::map<LocationT, SampleT> &Samples) {
1108 for (const auto &I : Samples)
1109 V.push_back(&I);
1110 llvm::stable_sort(V, [](const SamplesWithLoc *A, const SamplesWithLoc *B) {
1111 return A->first < B->first;
1112 });
1113 }
1114
1115 const SamplesWithLocList &get() const { return V; }
1116
1117 private:
1118 SamplesWithLocList V;
1119 };
1120
1121 /// SampleContextTrimmer impelements helper functions to trim, merge cold
1122 /// context profiles. It also supports context profile canonicalization to make
1123 /// sure ProfileMap's key is consistent with FunctionSample's name/context.
1124 class SampleContextTrimmer {
1125 public:
1126 SampleContextTrimmer(SampleProfileMap &Profiles) : ProfileMap(Profiles){};
1127 // Trim and merge cold context profile when requested.
1128 void trimAndMergeColdContextProfiles(uint64_t ColdCountThreshold,
1129 bool TrimColdContext,
1130 bool MergeColdContext,
1131 uint32_t ColdContextFrameLength);
1132 // Canonicalize context profile name and attributes.
1133 void canonicalizeContextProfiles();
1134
1135 private:
1136 SampleProfileMap &ProfileMap;
1137 };
1138
1139 /// ProfileSymbolList records the list of function symbols shown up
1140 /// in the binary used to generate the profile. It is useful to
1141 /// to discriminate a function being so cold as not to shown up
1142 /// in the profile and a function newly added.
1143 class ProfileSymbolList {
1144 public:
1145 /// copy indicates whether we need to copy the underlying memory
1146 /// for the input Name.
1147 void add(StringRef Name, bool copy = false) {
1148 if (!copy) {
1149 Syms.insert(Name);
1150 return;
1151 }
1152 Syms.insert(Name.copy(Allocator));
1153 }
1154
1155 bool contains(StringRef Name) { return Syms.count(Name); }
1156
1157 void merge(const ProfileSymbolList &List) {
1158 for (auto Sym : List.Syms)
1159 add(Sym, true);
1160 }
1161
1162 unsigned size() { return Syms.size(); }
1163
1164 void setToCompress(bool TC) { ToCompress = TC; }
1165 bool toCompress() { return ToCompress; }
1166
1167 std::error_code read(const uint8_t *Data, uint64_t ListSize);
1168 std::error_code write(raw_ostream &OS);
1169 void dump(raw_ostream &OS = dbgs()) const;
1170
1171 private:
1172 // Determine whether or not to compress the symbol list when
1173 // writing it into profile. The variable is unused when the symbol
1174 // list is read from an existing profile.
1175 bool ToCompress = false;
1176 DenseSet<StringRef> Syms;
1177 BumpPtrAllocator Allocator;
1178 };
1179
1180 } // end namespace sampleprof
1181
1182 using namespace sampleprof;
1183 // Provide DenseMapInfo for SampleContext.
1184 template <> struct DenseMapInfo<SampleContext> {
1185 static inline SampleContext getEmptyKey() { return SampleContext(); }
1186
1187 static inline SampleContext getTombstoneKey() { return SampleContext("@"); }
1188
1189 static unsigned getHashValue(const SampleContext &Val) {
1190 return Val.getHashCode();
1191 }
1192
1193 static bool isEqual(const SampleContext &LHS, const SampleContext &RHS) {
1194 return LHS == RHS;
1195 }
1196 };
1197 } // end namespace llvm
1198
1199 #endif // LLVM_PROFILEDATA_SAMPLEPROF_H
1200