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 <map>
33 #include <set>
34 #include <string>
35 #include <system_error>
36 #include <utility>
37
38 namespace llvm {
39
40 class raw_ostream;
41
42 const std::error_category &sampleprof_category();
43
44 enum class sampleprof_error {
45 success = 0,
46 bad_magic,
47 unsupported_version,
48 too_large,
49 truncated,
50 malformed,
51 unrecognized_format,
52 unsupported_writing_format,
53 truncated_name_table,
54 not_implemented,
55 counter_overflow,
56 ostream_seek_unsupported,
57 compress_failed,
58 uncompress_failed,
59 zlib_unavailable
60 };
61
make_error_code(sampleprof_error E)62 inline std::error_code make_error_code(sampleprof_error E) {
63 return std::error_code(static_cast<int>(E), sampleprof_category());
64 }
65
MergeResult(sampleprof_error & Accumulator,sampleprof_error Result)66 inline sampleprof_error MergeResult(sampleprof_error &Accumulator,
67 sampleprof_error Result) {
68 // Prefer first error encountered as later errors may be secondary effects of
69 // the initial problem.
70 if (Accumulator == sampleprof_error::success &&
71 Result != sampleprof_error::success)
72 Accumulator = Result;
73 return Accumulator;
74 }
75
76 } // end namespace llvm
77
78 namespace std {
79
80 template <>
81 struct is_error_code_enum<llvm::sampleprof_error> : std::true_type {};
82
83 } // end namespace std
84
85 namespace llvm {
86 namespace sampleprof {
87
88 enum SampleProfileFormat {
89 SPF_None = 0,
90 SPF_Text = 0x1,
91 SPF_Compact_Binary = 0x2,
92 SPF_GCC = 0x3,
93 SPF_Ext_Binary = 0x4,
94 SPF_Binary = 0xff
95 };
96
97 static inline uint64_t SPMagic(SampleProfileFormat Format = SPF_Binary) {
98 return uint64_t('S') << (64 - 8) | uint64_t('P') << (64 - 16) |
99 uint64_t('R') << (64 - 24) | uint64_t('O') << (64 - 32) |
100 uint64_t('F') << (64 - 40) | uint64_t('4') << (64 - 48) |
101 uint64_t('2') << (64 - 56) | uint64_t(Format);
102 }
103
104 /// Get the proper representation of a string according to whether the
105 /// current Format uses MD5 to represent the string.
106 static inline StringRef getRepInFormat(StringRef Name, bool UseMD5,
107 std::string &GUIDBuf) {
108 if (Name.empty())
109 return Name;
110 GUIDBuf = std::to_string(Function::getGUID(Name));
111 return UseMD5 ? StringRef(GUIDBuf) : Name;
112 }
113
114 static inline uint64_t SPVersion() { return 103; }
115
116 // Section Type used by SampleProfileExtBinaryBaseReader and
117 // SampleProfileExtBinaryBaseWriter. Never change the existing
118 // value of enum. Only append new ones.
119 enum SecType {
120 SecInValid = 0,
121 SecProfSummary = 1,
122 SecNameTable = 2,
123 SecProfileSymbolList = 3,
124 SecFuncOffsetTable = 4,
125 // marker for the first type of profile.
126 SecFuncProfileFirst = 32,
127 SecLBRProfile = SecFuncProfileFirst
128 };
129
130 static inline std::string getSecName(SecType Type) {
131 switch (Type) {
132 case SecInValid:
133 return "InvalidSection";
134 case SecProfSummary:
135 return "ProfileSummarySection";
136 case SecNameTable:
137 return "NameTableSection";
138 case SecProfileSymbolList:
139 return "ProfileSymbolListSection";
140 case SecFuncOffsetTable:
141 return "FuncOffsetTableSection";
142 case SecLBRProfile:
143 return "LBRProfileSection";
144 }
145 llvm_unreachable("A SecType has no name for output");
146 }
147
148 // Entry type of section header table used by SampleProfileExtBinaryBaseReader
149 // and SampleProfileExtBinaryBaseWriter.
150 struct SecHdrTableEntry {
151 SecType Type;
152 uint64_t Flags;
153 uint64_t Offset;
154 uint64_t Size;
155 };
156
157 // Flags common for all sections are defined here. In SecHdrTableEntry::Flags,
158 // common flags will be saved in the lower 32bits and section specific flags
159 // will be saved in the higher 32 bits.
160 enum class SecCommonFlags : uint32_t {
161 SecFlagInValid = 0,
162 SecFlagCompress = (1 << 0)
163 };
164
165 // Section specific flags are defined here.
166 // !!!Note: Everytime a new enum class is created here, please add
167 // a new check in verifySecFlag.
168 enum class SecNameTableFlags : uint32_t {
169 SecFlagInValid = 0,
170 SecFlagMD5Name = (1 << 0)
171 };
172 enum class SecProfSummaryFlags : uint32_t {
173 SecFlagInValid = 0,
174 /// SecFlagPartial means the profile is for common/shared code.
175 /// The common profile is usually merged from profiles collected
176 /// from running other targets.
177 SecFlagPartial = (1 << 0)
178 };
179
180 // Verify section specific flag is used for the correct section.
181 template <class SecFlagType>
182 static inline void verifySecFlag(SecType Type, SecFlagType Flag) {
183 // No verification is needed for common flags.
184 if (std::is_same<SecCommonFlags, SecFlagType>())
185 return;
186
187 // Verification starts here for section specific flag.
188 bool IsFlagLegal = false;
189 switch (Type) {
190 case SecNameTable:
191 IsFlagLegal = std::is_same<SecNameTableFlags, SecFlagType>();
192 break;
193 case SecProfSummary:
194 IsFlagLegal = std::is_same<SecProfSummaryFlags, SecFlagType>();
195 break;
196 default:
197 break;
198 }
199 if (!IsFlagLegal)
200 llvm_unreachable("Misuse of a flag in an incompatible section");
201 }
202
203 template <class SecFlagType>
204 static inline void addSecFlag(SecHdrTableEntry &Entry, SecFlagType Flag) {
205 verifySecFlag(Entry.Type, Flag);
206 auto FVal = static_cast<uint64_t>(Flag);
207 bool IsCommon = std::is_same<SecCommonFlags, SecFlagType>();
208 Entry.Flags |= IsCommon ? FVal : (FVal << 32);
209 }
210
211 template <class SecFlagType>
212 static inline void removeSecFlag(SecHdrTableEntry &Entry, SecFlagType Flag) {
213 verifySecFlag(Entry.Type, Flag);
214 auto FVal = static_cast<uint64_t>(Flag);
215 bool IsCommon = std::is_same<SecCommonFlags, SecFlagType>();
216 Entry.Flags &= ~(IsCommon ? FVal : (FVal << 32));
217 }
218
219 template <class SecFlagType>
220 static inline bool hasSecFlag(const SecHdrTableEntry &Entry, SecFlagType Flag) {
221 verifySecFlag(Entry.Type, Flag);
222 auto FVal = static_cast<uint64_t>(Flag);
223 bool IsCommon = std::is_same<SecCommonFlags, SecFlagType>();
224 return Entry.Flags & (IsCommon ? FVal : (FVal << 32));
225 }
226
227 /// Represents the relative location of an instruction.
228 ///
229 /// Instruction locations are specified by the line offset from the
230 /// beginning of the function (marked by the line where the function
231 /// header is) and the discriminator value within that line.
232 ///
233 /// The discriminator value is useful to distinguish instructions
234 /// that are on the same line but belong to different basic blocks
235 /// (e.g., the two post-increment instructions in "if (p) x++; else y++;").
236 struct LineLocation {
237 LineLocation(uint32_t L, uint32_t D) : LineOffset(L), Discriminator(D) {}
238
239 void print(raw_ostream &OS) const;
240 void dump() const;
241
242 bool operator<(const LineLocation &O) const {
243 return LineOffset < O.LineOffset ||
244 (LineOffset == O.LineOffset && Discriminator < O.Discriminator);
245 }
246
247 uint32_t LineOffset;
248 uint32_t Discriminator;
249 };
250
251 raw_ostream &operator<<(raw_ostream &OS, const LineLocation &Loc);
252
253 /// Representation of a single sample record.
254 ///
255 /// A sample record is represented by a positive integer value, which
256 /// indicates how frequently was the associated line location executed.
257 ///
258 /// Additionally, if the associated location contains a function call,
259 /// the record will hold a list of all the possible called targets. For
260 /// direct calls, this will be the exact function being invoked. For
261 /// indirect calls (function pointers, virtual table dispatch), this
262 /// will be a list of one or more functions.
263 class SampleRecord {
264 public:
265 using CallTarget = std::pair<StringRef, uint64_t>;
266 struct CallTargetComparator {
267 bool operator()(const CallTarget &LHS, const CallTarget &RHS) const {
268 if (LHS.second != RHS.second)
269 return LHS.second > RHS.second;
270
271 return LHS.first < RHS.first;
272 }
273 };
274
275 using SortedCallTargetSet = std::set<CallTarget, CallTargetComparator>;
276 using CallTargetMap = StringMap<uint64_t>;
277 SampleRecord() = default;
278
279 /// Increment the number of samples for this record by \p S.
280 /// Optionally scale sample count \p S by \p Weight.
281 ///
282 /// Sample counts accumulate using saturating arithmetic, to avoid wrapping
283 /// around unsigned integers.
284 sampleprof_error addSamples(uint64_t S, uint64_t Weight = 1) {
285 bool Overflowed;
286 NumSamples = SaturatingMultiplyAdd(S, Weight, NumSamples, &Overflowed);
287 return Overflowed ? sampleprof_error::counter_overflow
288 : sampleprof_error::success;
289 }
290
291 /// Add called function \p F with samples \p S.
292 /// Optionally scale sample count \p S by \p Weight.
293 ///
294 /// Sample counts accumulate using saturating arithmetic, to avoid wrapping
295 /// around unsigned integers.
296 sampleprof_error addCalledTarget(StringRef F, uint64_t S,
297 uint64_t Weight = 1) {
298 uint64_t &TargetSamples = CallTargets[F];
299 bool Overflowed;
300 TargetSamples =
301 SaturatingMultiplyAdd(S, Weight, TargetSamples, &Overflowed);
302 return Overflowed ? sampleprof_error::counter_overflow
303 : sampleprof_error::success;
304 }
305
306 /// Return true if this sample record contains function calls.
307 bool hasCalls() const { return !CallTargets.empty(); }
308
309 uint64_t getSamples() const { return NumSamples; }
310 const CallTargetMap &getCallTargets() const { return CallTargets; }
311 const SortedCallTargetSet getSortedCallTargets() const {
312 return SortCallTargets(CallTargets);
313 }
314
315 /// Sort call targets in descending order of call frequency.
316 static const SortedCallTargetSet SortCallTargets(const CallTargetMap &Targets) {
317 SortedCallTargetSet SortedTargets;
318 for (const auto &I : Targets) {
319 SortedTargets.emplace(I.first(), I.second);
320 }
321 return SortedTargets;
322 }
323
324 /// Merge the samples in \p Other into this record.
325 /// Optionally scale sample counts by \p Weight.
326 sampleprof_error merge(const SampleRecord &Other, uint64_t Weight = 1) {
327 sampleprof_error Result = addSamples(Other.getSamples(), Weight);
328 for (const auto &I : Other.getCallTargets()) {
329 MergeResult(Result, addCalledTarget(I.first(), I.second, Weight));
330 }
331 return Result;
332 }
333
334 void print(raw_ostream &OS, unsigned Indent) const;
335 void dump() const;
336
337 private:
338 uint64_t NumSamples = 0;
339 CallTargetMap CallTargets;
340 };
341
342 raw_ostream &operator<<(raw_ostream &OS, const SampleRecord &Sample);
343
344 class FunctionSamples;
345
346 using BodySampleMap = std::map<LineLocation, SampleRecord>;
347 // NOTE: Using a StringMap here makes parsed profiles consume around 17% more
348 // memory, which is *very* significant for large profiles.
349 using FunctionSamplesMap = std::map<std::string, FunctionSamples, std::less<>>;
350 using CallsiteSampleMap = std::map<LineLocation, FunctionSamplesMap>;
351
352 /// Representation of the samples collected for a function.
353 ///
354 /// This data structure contains all the collected samples for the body
355 /// of a function. Each sample corresponds to a LineLocation instance
356 /// within the body of the function.
357 class FunctionSamples {
358 public:
359 FunctionSamples() = default;
360
361 void print(raw_ostream &OS = dbgs(), unsigned Indent = 0) const;
362 void dump() const;
363
364 sampleprof_error addTotalSamples(uint64_t Num, uint64_t Weight = 1) {
365 bool Overflowed;
366 TotalSamples =
367 SaturatingMultiplyAdd(Num, Weight, TotalSamples, &Overflowed);
368 return Overflowed ? sampleprof_error::counter_overflow
369 : sampleprof_error::success;
370 }
371
372 sampleprof_error addHeadSamples(uint64_t Num, uint64_t Weight = 1) {
373 bool Overflowed;
374 TotalHeadSamples =
375 SaturatingMultiplyAdd(Num, Weight, TotalHeadSamples, &Overflowed);
376 return Overflowed ? sampleprof_error::counter_overflow
377 : sampleprof_error::success;
378 }
379
380 sampleprof_error addBodySamples(uint32_t LineOffset, uint32_t Discriminator,
381 uint64_t Num, uint64_t Weight = 1) {
382 return BodySamples[LineLocation(LineOffset, Discriminator)].addSamples(
383 Num, Weight);
384 }
385
386 sampleprof_error addCalledTargetSamples(uint32_t LineOffset,
387 uint32_t Discriminator,
388 StringRef FName, uint64_t Num,
389 uint64_t Weight = 1) {
390 return BodySamples[LineLocation(LineOffset, Discriminator)].addCalledTarget(
391 FName, Num, Weight);
392 }
393
394 /// Return the number of samples collected at the given location.
395 /// Each location is specified by \p LineOffset and \p Discriminator.
396 /// If the location is not found in profile, return error.
397 ErrorOr<uint64_t> findSamplesAt(uint32_t LineOffset,
398 uint32_t Discriminator) const {
399 const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator));
400 if (ret == BodySamples.end())
401 return std::error_code();
402 else
403 return ret->second.getSamples();
404 }
405
406 /// Returns the call target map collected at a given location.
407 /// Each location is specified by \p LineOffset and \p Discriminator.
408 /// If the location is not found in profile, return error.
409 ErrorOr<SampleRecord::CallTargetMap>
410 findCallTargetMapAt(uint32_t LineOffset, uint32_t Discriminator) const {
411 const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator));
412 if (ret == BodySamples.end())
413 return std::error_code();
414 return ret->second.getCallTargets();
415 }
416
417 /// Return the function samples at the given callsite location.
418 FunctionSamplesMap &functionSamplesAt(const LineLocation &Loc) {
419 return CallsiteSamples[Loc];
420 }
421
422 /// Returns the FunctionSamplesMap at the given \p Loc.
423 const FunctionSamplesMap *
424 findFunctionSamplesMapAt(const LineLocation &Loc) const {
425 auto iter = CallsiteSamples.find(Loc);
426 if (iter == CallsiteSamples.end())
427 return nullptr;
428 return &iter->second;
429 }
430
431 /// Returns a pointer to FunctionSamples at the given callsite location \p Loc
432 /// with callee \p CalleeName. If no callsite can be found, relax the
433 /// restriction to return the FunctionSamples at callsite location \p Loc
434 /// with the maximum total sample count.
435 const FunctionSamples *findFunctionSamplesAt(const LineLocation &Loc,
436 StringRef CalleeName) const {
437 std::string CalleeGUID;
438 CalleeName = getRepInFormat(CalleeName, UseMD5, CalleeGUID);
439
440 auto iter = CallsiteSamples.find(Loc);
441 if (iter == CallsiteSamples.end())
442 return nullptr;
443 auto FS = iter->second.find(CalleeName);
444 if (FS != iter->second.end())
445 return &FS->second;
446 // If we cannot find exact match of the callee name, return the FS with
447 // the max total count. Only do this when CalleeName is not provided,
448 // i.e., only for indirect calls.
449 if (!CalleeName.empty())
450 return nullptr;
451 uint64_t MaxTotalSamples = 0;
452 const FunctionSamples *R = nullptr;
453 for (const auto &NameFS : iter->second)
454 if (NameFS.second.getTotalSamples() >= MaxTotalSamples) {
455 MaxTotalSamples = NameFS.second.getTotalSamples();
456 R = &NameFS.second;
457 }
458 return R;
459 }
460
461 bool empty() const { return TotalSamples == 0; }
462
463 /// Return the total number of samples collected inside the function.
464 uint64_t getTotalSamples() const { return TotalSamples; }
465
466 /// Return the total number of branch samples that have the function as the
467 /// branch target. This should be equivalent to the sample of the first
468 /// instruction of the symbol. But as we directly get this info for raw
469 /// profile without referring to potentially inaccurate debug info, this
470 /// gives more accurate profile data and is preferred for standalone symbols.
471 uint64_t getHeadSamples() const { return TotalHeadSamples; }
472
473 /// Return the sample count of the first instruction of the function.
474 /// The function can be either a standalone symbol or an inlined function.
475 uint64_t getEntrySamples() const {
476 uint64_t Count = 0;
477 // Use either BodySamples or CallsiteSamples which ever has the smaller
478 // lineno.
479 if (!BodySamples.empty() &&
480 (CallsiteSamples.empty() ||
481 BodySamples.begin()->first < CallsiteSamples.begin()->first))
482 Count = BodySamples.begin()->second.getSamples();
483 else if (!CallsiteSamples.empty()) {
484 // An indirect callsite may be promoted to several inlined direct calls.
485 // We need to get the sum of them.
486 for (const auto &N_FS : CallsiteSamples.begin()->second)
487 Count += N_FS.second.getEntrySamples();
488 }
489 // Return at least 1 if total sample is not 0.
490 return Count ? Count : TotalSamples > 0;
491 }
492
493 /// Return all the samples collected in the body of the function.
494 const BodySampleMap &getBodySamples() const { return BodySamples; }
495
496 /// Return all the callsite samples collected in the body of the function.
497 const CallsiteSampleMap &getCallsiteSamples() const {
498 return CallsiteSamples;
499 }
500
501 /// Return the maximum of sample counts in a function body including functions
502 /// inlined in it.
503 uint64_t getMaxCountInside() const {
504 uint64_t MaxCount = 0;
505 for (const auto &L : getBodySamples())
506 MaxCount = std::max(MaxCount, L.second.getSamples());
507 for (const auto &C : getCallsiteSamples())
508 for (const FunctionSamplesMap::value_type &F : C.second)
509 MaxCount = std::max(MaxCount, F.second.getMaxCountInside());
510 return MaxCount;
511 }
512
513 /// Merge the samples in \p Other into this one.
514 /// Optionally scale samples by \p Weight.
515 sampleprof_error merge(const FunctionSamples &Other, uint64_t Weight = 1) {
516 sampleprof_error Result = sampleprof_error::success;
517 Name = Other.getName();
518 MergeResult(Result, addTotalSamples(Other.getTotalSamples(), Weight));
519 MergeResult(Result, addHeadSamples(Other.getHeadSamples(), Weight));
520 for (const auto &I : Other.getBodySamples()) {
521 const LineLocation &Loc = I.first;
522 const SampleRecord &Rec = I.second;
523 MergeResult(Result, BodySamples[Loc].merge(Rec, Weight));
524 }
525 for (const auto &I : Other.getCallsiteSamples()) {
526 const LineLocation &Loc = I.first;
527 FunctionSamplesMap &FSMap = functionSamplesAt(Loc);
528 for (const auto &Rec : I.second)
529 MergeResult(Result, FSMap[Rec.first].merge(Rec.second, Weight));
530 }
531 return Result;
532 }
533
534 /// Recursively traverses all children, if the total sample count of the
535 /// corresponding function is no less than \p Threshold, add its corresponding
536 /// GUID to \p S. Also traverse the BodySamples to add hot CallTarget's GUID
537 /// to \p S.
538 void findInlinedFunctions(DenseSet<GlobalValue::GUID> &S, const Module *M,
539 uint64_t Threshold) const {
540 if (TotalSamples <= Threshold)
541 return;
542 auto isDeclaration = [](const Function *F) {
543 return !F || F->isDeclaration();
544 };
545 if (isDeclaration(M->getFunction(getFuncName()))) {
546 // Add to the import list only when it's defined out of module.
547 S.insert(getGUID(Name));
548 }
549 // Import hot CallTargets, which may not be available in IR because full
550 // profile annotation cannot be done until backend compilation in ThinLTO.
551 for (const auto &BS : BodySamples)
552 for (const auto &TS : BS.second.getCallTargets())
553 if (TS.getValue() > Threshold) {
554 const Function *Callee = M->getFunction(getFuncName(TS.getKey()));
555 if (isDeclaration(Callee))
556 S.insert(getGUID(TS.getKey()));
557 }
558 for (const auto &CS : CallsiteSamples)
559 for (const auto &NameFS : CS.second)
560 NameFS.second.findInlinedFunctions(S, M, Threshold);
561 }
562
563 /// Set the name of the function.
564 void setName(StringRef FunctionName) { Name = FunctionName; }
565
566 /// Return the function name.
567 StringRef getName() const { return Name; }
568
569 /// Return the original function name.
570 StringRef getFuncName() const { return getFuncName(Name); }
571
572 /// Return the canonical name for a function, taking into account
573 /// suffix elision policy attributes.
574 static StringRef getCanonicalFnName(const Function &F) {
575 static const char *knownSuffixes[] = { ".llvm.", ".part." };
576 auto AttrName = "sample-profile-suffix-elision-policy";
577 auto Attr = F.getFnAttribute(AttrName).getValueAsString();
578 if (Attr == "" || Attr == "all") {
579 return F.getName().split('.').first;
580 } else if (Attr == "selected") {
581 StringRef Cand(F.getName());
582 for (const auto &Suf : knownSuffixes) {
583 StringRef Suffix(Suf);
584 auto It = Cand.rfind(Suffix);
585 if (It == StringRef::npos)
586 return Cand;
587 auto Dit = Cand.rfind('.');
588 if (Dit == It + Suffix.size() - 1)
589 Cand = Cand.substr(0, It);
590 }
591 return Cand;
592 } else if (Attr == "none") {
593 return F.getName();
594 } else {
595 assert(false && "internal error: unknown suffix elision policy");
596 }
597 return F.getName();
598 }
599
600 /// Translate \p Name into its original name.
601 /// When profile doesn't use MD5, \p Name needs no translation.
602 /// When profile uses MD5, \p Name in current FunctionSamples
603 /// is actually GUID of the original function name. getFuncName will
604 /// translate \p Name in current FunctionSamples into its original name
605 /// by looking up in the function map GUIDToFuncNameMap.
606 /// If the original name doesn't exist in the map, return empty StringRef.
607 StringRef getFuncName(StringRef Name) const {
608 if (!UseMD5)
609 return Name;
610
611 assert(GUIDToFuncNameMap && "GUIDToFuncNameMap needs to be popluated first");
612 auto iter = GUIDToFuncNameMap->find(std::stoull(Name.data()));
613 if (iter == GUIDToFuncNameMap->end())
614 return StringRef();
615 return iter->second;
616 }
617
618 /// Returns the line offset to the start line of the subprogram.
619 /// We assume that a single function will not exceed 65535 LOC.
620 static unsigned getOffset(const DILocation *DIL);
621
622 /// Get the FunctionSamples of the inline instance where DIL originates
623 /// from.
624 ///
625 /// The FunctionSamples of the instruction (Machine or IR) associated to
626 /// \p DIL is the inlined instance in which that instruction is coming from.
627 /// We traverse the inline stack of that instruction, and match it with the
628 /// tree nodes in the profile.
629 ///
630 /// \returns the FunctionSamples pointer to the inlined instance.
631 const FunctionSamples *findFunctionSamples(const DILocation *DIL) const;
632
633 static SampleProfileFormat Format;
634
635 /// Whether the profile uses MD5 to represent string.
636 static bool UseMD5;
637
638 /// GUIDToFuncNameMap saves the mapping from GUID to the symbol name, for
639 /// all the function symbols defined or declared in current module.
640 DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap = nullptr;
641
642 // Assume the input \p Name is a name coming from FunctionSamples itself.
643 // If UseMD5 is true, the name is already a GUID and we
644 // don't want to return the GUID of GUID.
645 static uint64_t getGUID(StringRef Name) {
646 return UseMD5 ? std::stoull(Name.data()) : Function::getGUID(Name);
647 }
648
649 private:
650 /// Mangled name of the function.
651 StringRef Name;
652
653 /// Total number of samples collected inside this function.
654 ///
655 /// Samples are cumulative, they include all the samples collected
656 /// inside this function and all its inlined callees.
657 uint64_t TotalSamples = 0;
658
659 /// Total number of samples collected at the head of the function.
660 /// This is an approximation of the number of calls made to this function
661 /// at runtime.
662 uint64_t TotalHeadSamples = 0;
663
664 /// Map instruction locations to collected samples.
665 ///
666 /// Each entry in this map contains the number of samples
667 /// collected at the corresponding line offset. All line locations
668 /// are an offset from the start of the function.
669 BodySampleMap BodySamples;
670
671 /// Map call sites to collected samples for the called function.
672 ///
673 /// Each entry in this map corresponds to all the samples
674 /// collected for the inlined function call at the given
675 /// location. For example, given:
676 ///
677 /// void foo() {
678 /// 1 bar();
679 /// ...
680 /// 8 baz();
681 /// }
682 ///
683 /// If the bar() and baz() calls were inlined inside foo(), this
684 /// map will contain two entries. One for all the samples collected
685 /// in the call to bar() at line offset 1, the other for all the samples
686 /// collected in the call to baz() at line offset 8.
687 CallsiteSampleMap CallsiteSamples;
688 };
689
690 raw_ostream &operator<<(raw_ostream &OS, const FunctionSamples &FS);
691
692 /// Sort a LocationT->SampleT map by LocationT.
693 ///
694 /// It produces a sorted list of <LocationT, SampleT> records by ascending
695 /// order of LocationT.
696 template <class LocationT, class SampleT> class SampleSorter {
697 public:
698 using SamplesWithLoc = std::pair<const LocationT, SampleT>;
699 using SamplesWithLocList = SmallVector<const SamplesWithLoc *, 20>;
700
701 SampleSorter(const std::map<LocationT, SampleT> &Samples) {
702 for (const auto &I : Samples)
703 V.push_back(&I);
704 llvm::stable_sort(V, [](const SamplesWithLoc *A, const SamplesWithLoc *B) {
705 return A->first < B->first;
706 });
707 }
708
709 const SamplesWithLocList &get() const { return V; }
710
711 private:
712 SamplesWithLocList V;
713 };
714
715 /// ProfileSymbolList records the list of function symbols shown up
716 /// in the binary used to generate the profile. It is useful to
717 /// to discriminate a function being so cold as not to shown up
718 /// in the profile and a function newly added.
719 class ProfileSymbolList {
720 public:
721 /// copy indicates whether we need to copy the underlying memory
722 /// for the input Name.
723 void add(StringRef Name, bool copy = false) {
724 if (!copy) {
725 Syms.insert(Name);
726 return;
727 }
728 Syms.insert(Name.copy(Allocator));
729 }
730
731 bool contains(StringRef Name) { return Syms.count(Name); }
732
733 void merge(const ProfileSymbolList &List) {
734 for (auto Sym : List.Syms)
735 add(Sym, true);
736 }
737
738 unsigned size() { return Syms.size(); }
739
740 void setToCompress(bool TC) { ToCompress = TC; }
741 bool toCompress() { return ToCompress; }
742
743 std::error_code read(const uint8_t *Data, uint64_t ListSize);
744 std::error_code write(raw_ostream &OS);
745 void dump(raw_ostream &OS = dbgs()) const;
746
747 private:
748 // Determine whether or not to compress the symbol list when
749 // writing it into profile. The variable is unused when the symbol
750 // list is read from an existing profile.
751 bool ToCompress = false;
752 DenseSet<StringRef> Syms;
753 BumpPtrAllocator Allocator;
754 };
755
756 } // end namespace sampleprof
757 } // end namespace llvm
758
759 #endif // LLVM_PROFILEDATA_SAMPLEPROF_H
760