1 //===- SampleProfReader.h - Read LLVM sample profile data -------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // This file contains definitions needed for reading sample profiles.
11 // NOTE: If you are making changes to this file format, please remember
12 // to document them in the Clang documentation at
13 // tools/clang/docs/UsersManual.rst.
18 // Sample profiles are written as ASCII text. The file is divided into
19 // sections, which correspond to each of the functions executed at runtime.
20 // Each section has the following format
22 // function1:total_samples:total_head_samples
23 // offset1[.discriminator]: number_of_samples [fn1:num fn2:num ... ]
24 // offset2[.discriminator]: number_of_samples [fn3:num fn4:num ... ]
26 // offsetN[.discriminator]: number_of_samples [fn5:num fn6:num ... ]
27 // offsetA[.discriminator]: fnA:num_of_total_samples
28 // offsetA1[.discriminator]: number_of_samples [fn7:num fn8:num ... ]
31 // This is a nested tree in which the identation represents the nesting level
32 // of the inline stack. There are no blank lines in the file. And the spacing
33 // within a single line is fixed. Additional spaces will result in an error
34 // while reading the file.
36 // Any line starting with the '#' character is completely ignored.
38 // Inlined calls are represented with indentation. The Inline stack is a
39 // stack of source locations in which the top of the stack represents the
40 // leaf function, and the bottom of the stack represents the actual
41 // symbol to which the instruction belongs.
43 // Function names must be mangled in order for the profile loader to
44 // match them in the current translation unit. The two numbers in the
45 // function header specify how many total samples were accumulated in the
46 // function (first number), and the total number of samples accumulated
47 // in the prologue of the function (second number). This head sample
48 // count provides an indicator of how frequently the function is invoked.
50 // There are two types of lines in the function body.
52 // * Sampled line represents the profile information of a source location.
53 // * Callsite line represents the profile information of a callsite.
55 // Each sampled line may contain several items. Some are optional (marked
58 // a. Source line offset. This number represents the line number
59 // in the function where the sample was collected. The line number is
60 // always relative to the line where symbol of the function is
61 // defined. So, if the function has its header at line 280, the offset
62 // 13 is at line 293 in the file.
64 // Note that this offset should never be a negative number. This could
65 // happen in cases like macros. The debug machinery will register the
66 // line number at the point of macro expansion. So, if the macro was
67 // expanded in a line before the start of the function, the profile
68 // converter should emit a 0 as the offset (this means that the optimizers
69 // will not be able to associate a meaningful weight to the instructions
72 // b. [OPTIONAL] Discriminator. This is used if the sampled program
73 // was compiled with DWARF discriminator support
74 // (http://wiki.dwarfstd.org/index.php?title=Path_Discriminators).
75 // DWARF discriminators are unsigned integer values that allow the
76 // compiler to distinguish between multiple execution paths on the
77 // same source line location.
79 // For example, consider the line of code ``if (cond) foo(); else bar();``.
80 // If the predicate ``cond`` is true 80% of the time, then the edge
81 // into function ``foo`` should be considered to be taken most of the
82 // time. But both calls to ``foo`` and ``bar`` are at the same source
83 // line, so a sample count at that line is not sufficient. The
84 // compiler needs to know which part of that line is taken more
87 // This is what discriminators provide. In this case, the calls to
88 // ``foo`` and ``bar`` will be at the same line, but will have
89 // different discriminator values. This allows the compiler to correctly
90 // set edge weights into ``foo`` and ``bar``.
92 // c. Number of samples. This is an integer quantity representing the
93 // number of samples collected by the profiler at this source
96 // d. [OPTIONAL] Potential call targets and samples. If present, this
97 // line contains a call instruction. This models both direct and
98 // number of samples. For example,
100 // 130: 7 foo:3 bar:2 baz:7
102 // The above means that at relative line offset 130 there is a call
103 // instruction that calls one of ``foo()``, ``bar()`` and ``baz()``,
104 // with ``baz()`` being the relatively more frequently called target.
106 // Each callsite line may contain several items. Some are optional.
108 // a. Source line offset. This number represents the line number of the
109 // callsite that is inlined in the profiled binary.
111 // b. [OPTIONAL] Discriminator. Same as the discriminator for sampled line.
113 // c. Number of samples. This is an integer quantity representing the
114 // total number of samples collected for the inlined instance at this
121 // This is a more compact encoding. Numbers are encoded as ULEB128 values
122 // and all strings are encoded in a name table. The file is organized in
123 // the following sections:
126 // File identifier computed by function SPMagic() (0x5350524f463432ff)
128 // VERSION (uint32_t)
129 // File format version number computed by SPVersion()
132 // TOTAL_COUNT (uint64_t)
133 // Total number of samples in the profile.
134 // MAX_COUNT (uint64_t)
135 // Maximum value of samples on a line.
136 // MAX_FUNCTION_COUNT (uint64_t)
137 // Maximum number of samples at function entry (head samples).
138 // NUM_COUNTS (uint64_t)
139 // Number of lines with samples.
140 // NUM_FUNCTIONS (uint64_t)
141 // Number of functions with samples.
142 // NUM_DETAILED_SUMMARY_ENTRIES (size_t)
143 // Number of entries in detailed summary
145 // A list of detailed summary entry. Each entry consists of
147 // Required percentile of total sample count expressed as a fraction
148 // multiplied by 1000000.
149 // MIN_COUNT (uint64_t)
150 // The minimum number of samples required to reach the target
152 // NUM_COUNTS (uint64_t)
153 // Number of samples to get to the desrired percentile.
157 // Number of entries in the name table.
159 // A NUL-separated list of SIZE strings.
161 // FUNCTION BODY (one for each uninlined function body present in the profile)
162 // HEAD_SAMPLES (uint64_t) [only for top-level functions]
163 // Total number of samples collected at the head (prologue) of the
165 // NOTE: This field should only be present for top-level functions
166 // (i.e., not inlined into any caller). Inlined function calls
167 // have no prologue, so they don't need this.
168 // NAME_IDX (uint32_t)
169 // Index into the name table indicating the function name.
170 // SAMPLES (uint64_t)
171 // Total number of samples collected in this function.
173 // Total number of sampling records this function's profile.
175 // A list of NRECS entries. Each entry contains:
177 // Line offset from the start of the function.
178 // DISCRIMINATOR (uint32_t)
179 // Discriminator value (see description of discriminators
180 // in the text format documentation above).
181 // SAMPLES (uint64_t)
182 // Number of samples collected at this location.
183 // NUM_CALLS (uint32_t)
184 // Number of non-inlined function calls made at this location. In the
185 // case of direct calls, this number will always be 1. For indirect
186 // calls (virtual functions and function pointers) this will
187 // represent all the actual functions called at runtime.
189 // A list of NUM_CALLS entries for each called function:
190 // NAME_IDX (uint32_t)
191 // Index into the name table with the callee name.
192 // SAMPLES (uint64_t)
193 // Number of samples collected at the call site.
194 // NUM_INLINED_FUNCTIONS (uint32_t)
195 // Number of callees inlined into this function.
196 // INLINED FUNCTION RECORDS
197 // A list of NUM_INLINED_FUNCTIONS entries describing each of the inlined
200 // Line offset from the start of the function.
201 // DISCRIMINATOR (uint32_t)
202 // Discriminator value (see description of discriminators
203 // in the text format documentation above).
205 // A FUNCTION BODY entry describing the inlined function.
206 //===----------------------------------------------------------------------===//
208 #ifndef LLVM_PROFILEDATA_SAMPLEPROFREADER_H
209 #define LLVM_PROFILEDATA_SAMPLEPROFREADER_H
211 #include "llvm/ADT/SmallVector.h"
212 #include "llvm/ADT/StringMap.h"
213 #include "llvm/ADT/StringRef.h"
214 #include "llvm/ADT/Twine.h"
215 #include "llvm/IR/DiagnosticInfo.h"
216 #include "llvm/IR/Function.h"
217 #include "llvm/IR/LLVMContext.h"
218 #include "llvm/IR/ProfileSummary.h"
219 #include "llvm/ProfileData/GCOV.h"
220 #include "llvm/ProfileData/SampleProf.h"
221 #include "llvm/Support/Debug.h"
222 #include "llvm/Support/ErrorOr.h"
223 #include "llvm/Support/MemoryBuffer.h"
224 #include "llvm/Support/SymbolRemappingReader.h"
229 #include <system_error>
236 namespace sampleprof {
238 /// Sample-based profile reader.
240 /// Each profile contains sample counts for all the functions
241 /// executed. Inside each function, statements are annotated with the
242 /// collected samples on all the instructions associated with that
245 /// For this to produce meaningful data, the program needs to be
246 /// compiled with some debug information (at minimum, line numbers:
247 /// -gline-tables-only). Otherwise, it will be impossible to match IR
248 /// instructions to the line numbers collected by the profiler.
250 /// From the profile file, we are interested in collecting the
251 /// following information:
253 /// * A list of functions included in the profile (mangled names).
255 /// * For each function F:
256 /// 1. The total number of samples collected in F.
258 /// 2. The samples collected at each line in F. To provide some
259 /// protection against source code shuffling, line numbers should
260 /// be relative to the start of the function.
262 /// The reader supports two file formats: text and binary. The text format
263 /// is useful for debugging and testing, while the binary format is more
264 /// compact and I/O efficient. They can both be used interchangeably.
265 class SampleProfileReader {
267 SampleProfileReader(std::unique_ptr<MemoryBuffer> B, LLVMContext &C,
268 SampleProfileFormat Format = SPF_None)
269 : Profiles(0), Ctx(C), Buffer(std::move(B)), Format(Format) {}
271 virtual ~SampleProfileReader() = default;
273 /// Read and validate the file header.
274 virtual std::error_code readHeader() = 0;
276 /// Read sample profiles from the associated file.
277 virtual std::error_code read() = 0;
279 /// Print the profile for \p FName on stream \p OS.
280 void dumpFunctionProfile(StringRef FName, raw_ostream &OS = dbgs());
282 virtual void collectFuncsToUse(const Module &M) {}
284 /// Print all the profiles on stream \p OS.
285 void dump(raw_ostream &OS = dbgs());
287 /// Return the samples collected for function \p F.
288 FunctionSamples *getSamplesFor(const Function &F) {
289 // The function name may have been updated by adding suffix. Call
290 // a helper to (optionally) strip off suffixes so that we can
291 // match against the original function name in the profile.
292 StringRef CanonName = FunctionSamples::getCanonicalFnName(F);
293 return getSamplesFor(CanonName);
296 /// Return the samples collected for function \p F.
297 virtual FunctionSamples *getSamplesFor(StringRef Fname) {
299 Fname = getRepInFormat(Fname, getFormat(), FGUID);
300 auto It = Profiles.find(Fname);
301 if (It != Profiles.end())
306 /// Return all the profiles.
307 StringMap<FunctionSamples> &getProfiles() { return Profiles; }
309 /// Report a parse error message.
310 void reportError(int64_t LineNumber, Twine Msg) const {
311 Ctx.diagnose(DiagnosticInfoSampleProfile(Buffer->getBufferIdentifier(),
315 /// Create a sample profile reader appropriate to the file format.
316 static ErrorOr<std::unique_ptr<SampleProfileReader>>
317 create(const Twine &Filename, LLVMContext &C);
319 /// Create a sample profile reader from the supplied memory buffer.
320 static ErrorOr<std::unique_ptr<SampleProfileReader>>
321 create(std::unique_ptr<MemoryBuffer> &B, LLVMContext &C);
323 /// Return the profile summary.
324 ProfileSummary &getSummary() { return *(Summary.get()); }
326 /// \brief Return the profile format.
327 SampleProfileFormat getFormat() { return Format; }
330 /// Map every function to its associated profile.
332 /// The profile of every function executed at runtime is collected
333 /// in the structure FunctionSamples. This maps function objects
334 /// to their corresponding profiles.
335 StringMap<FunctionSamples> Profiles;
337 /// LLVM context used to emit diagnostics.
340 /// Memory buffer holding the profile file.
341 std::unique_ptr<MemoryBuffer> Buffer;
343 /// Profile summary information.
344 std::unique_ptr<ProfileSummary> Summary;
346 /// Take ownership of the summary of this reader.
347 static std::unique_ptr<ProfileSummary>
348 takeSummary(SampleProfileReader &Reader) {
349 return std::move(Reader.Summary);
352 /// Compute summary for this profile.
353 void computeSummary();
355 /// \brief The format of sample.
356 SampleProfileFormat Format = SPF_None;
359 class SampleProfileReaderText : public SampleProfileReader {
361 SampleProfileReaderText(std::unique_ptr<MemoryBuffer> B, LLVMContext &C)
362 : SampleProfileReader(std::move(B), C, SPF_Text) {}
364 /// Read and validate the file header.
365 std::error_code readHeader() override { return sampleprof_error::success; }
367 /// Read sample profiles from the associated file.
368 std::error_code read() override;
370 /// Return true if \p Buffer is in the format supported by this class.
371 static bool hasFormat(const MemoryBuffer &Buffer);
374 class SampleProfileReaderBinary : public SampleProfileReader {
376 SampleProfileReaderBinary(std::unique_ptr<MemoryBuffer> B, LLVMContext &C,
377 SampleProfileFormat Format = SPF_None)
378 : SampleProfileReader(std::move(B), C, Format) {}
380 /// Read and validate the file header.
381 virtual std::error_code readHeader() override;
383 /// Read sample profiles from the associated file.
384 std::error_code read() override;
387 /// Read a numeric value of type T from the profile.
389 /// If an error occurs during decoding, a diagnostic message is emitted and
392 /// \returns the read value.
393 template <typename T> ErrorOr<T> readNumber();
395 /// Read a numeric value of type T from the profile. The value is saved
397 template <typename T> ErrorOr<T> readUnencodedNumber();
399 /// Read a string from the profile.
401 /// If an error occurs during decoding, a diagnostic message is emitted and
404 /// \returns the read value.
405 ErrorOr<StringRef> readString();
407 /// Read the string index and check whether it overflows the table.
408 template <typename T> inline ErrorOr<uint32_t> readStringIndex(T &Table);
410 /// Return true if we've reached the end of file.
411 bool at_eof() const { return Data >= End; }
413 /// Read the next function profile instance.
414 std::error_code readFuncProfile();
416 /// Read the contents of the given profile instance.
417 std::error_code readProfile(FunctionSamples &FProfile);
419 /// Points to the current location in the buffer.
420 const uint8_t *Data = nullptr;
422 /// Points to the end of the buffer.
423 const uint8_t *End = nullptr;
426 std::error_code readSummaryEntry(std::vector<ProfileSummaryEntry> &Entries);
427 virtual std::error_code verifySPMagic(uint64_t Magic) = 0;
429 /// Read profile summary.
430 std::error_code readSummary();
432 /// Read the whole name table.
433 virtual std::error_code readNameTable() = 0;
435 /// Read a string indirectly via the name table.
436 virtual ErrorOr<StringRef> readStringFromTable() = 0;
439 class SampleProfileReaderRawBinary : public SampleProfileReaderBinary {
441 /// Function name table.
442 std::vector<StringRef> NameTable;
443 virtual std::error_code verifySPMagic(uint64_t Magic) override;
444 virtual std::error_code readNameTable() override;
445 /// Read a string indirectly via the name table.
446 virtual ErrorOr<StringRef> readStringFromTable() override;
449 SampleProfileReaderRawBinary(std::unique_ptr<MemoryBuffer> B, LLVMContext &C)
450 : SampleProfileReaderBinary(std::move(B), C, SPF_Binary) {}
452 /// \brief Return true if \p Buffer is in the format supported by this class.
453 static bool hasFormat(const MemoryBuffer &Buffer);
456 class SampleProfileReaderCompactBinary : public SampleProfileReaderBinary {
458 /// Function name table.
459 std::vector<std::string> NameTable;
460 /// The table mapping from function name to the offset of its FunctionSample
461 /// towards file start.
462 DenseMap<StringRef, uint64_t> FuncOffsetTable;
463 /// The set containing the functions to use when compiling a module.
464 DenseSet<StringRef> FuncsToUse;
465 virtual std::error_code verifySPMagic(uint64_t Magic) override;
466 virtual std::error_code readNameTable() override;
467 /// Read a string indirectly via the name table.
468 virtual ErrorOr<StringRef> readStringFromTable() override;
469 virtual std::error_code readHeader() override;
470 std::error_code readFuncOffsetTable();
473 SampleProfileReaderCompactBinary(std::unique_ptr<MemoryBuffer> B,
475 : SampleProfileReaderBinary(std::move(B), C, SPF_Compact_Binary) {}
477 /// \brief Return true if \p Buffer is in the format supported by this class.
478 static bool hasFormat(const MemoryBuffer &Buffer);
480 /// Read samples only for functions to use.
481 std::error_code read() override;
483 /// Collect functions to be used when compiling Module \p M.
484 void collectFuncsToUse(const Module &M) override;
487 using InlineCallStack = SmallVector<FunctionSamples *, 10>;
489 // Supported histogram types in GCC. Currently, we only need support for
490 // call target histograms.
494 HIST_TYPE_SINGLE_VALUE,
495 HIST_TYPE_CONST_DELTA,
496 HIST_TYPE_INDIR_CALL,
499 HIST_TYPE_INDIR_CALL_TOPN
502 class SampleProfileReaderGCC : public SampleProfileReader {
504 SampleProfileReaderGCC(std::unique_ptr<MemoryBuffer> B, LLVMContext &C)
505 : SampleProfileReader(std::move(B), C, SPF_GCC),
506 GcovBuffer(Buffer.get()) {}
508 /// Read and validate the file header.
509 std::error_code readHeader() override;
511 /// Read sample profiles from the associated file.
512 std::error_code read() override;
514 /// Return true if \p Buffer is in the format supported by this class.
515 static bool hasFormat(const MemoryBuffer &Buffer);
518 std::error_code readNameTable();
519 std::error_code readOneFunctionProfile(const InlineCallStack &InlineStack,
520 bool Update, uint32_t Offset);
521 std::error_code readFunctionProfiles();
522 std::error_code skipNextWord();
523 template <typename T> ErrorOr<T> readNumber();
524 ErrorOr<StringRef> readString();
526 /// Read the section tag and check that it's the same as \p Expected.
527 std::error_code readSectionTag(uint32_t Expected);
529 /// GCOV buffer containing the profile.
530 GCOVBuffer GcovBuffer;
532 /// Function names in this profile.
533 std::vector<std::string> Names;
535 /// GCOV tags used to separate sections in the profile file.
536 static const uint32_t GCOVTagAFDOFileNames = 0xaa000000;
537 static const uint32_t GCOVTagAFDOFunction = 0xac000000;
540 /// A profile data reader proxy that remaps the profile data from another
541 /// sample profile data reader, by applying a provided set of equivalences
542 /// between components of the symbol names in the profile.
543 class SampleProfileReaderItaniumRemapper : public SampleProfileReader {
545 SampleProfileReaderItaniumRemapper(
546 std::unique_ptr<MemoryBuffer> B, LLVMContext &C,
547 std::unique_ptr<SampleProfileReader> Underlying)
548 : SampleProfileReader(std::move(B), C, Underlying->getFormat()) {
549 Profiles = std::move(Underlying->getProfiles());
550 Summary = takeSummary(*Underlying);
551 // Keep the underlying reader alive; the profile data may contain
552 // StringRefs referencing names in its name table.
553 UnderlyingReader = std::move(Underlying);
556 /// Create a remapped sample profile from the given remapping file and
557 /// underlying samples.
558 static ErrorOr<std::unique_ptr<SampleProfileReader>>
559 create(const Twine &Filename, LLVMContext &C,
560 std::unique_ptr<SampleProfileReader> Underlying);
562 /// Read and validate the file header.
563 std::error_code readHeader() override { return sampleprof_error::success; }
565 /// Read remapping file and apply it to the sample profile.
566 std::error_code read() override;
568 /// Return the samples collected for function \p F.
569 FunctionSamples *getSamplesFor(StringRef FunctionName) override;
570 using SampleProfileReader::getSamplesFor;
573 SymbolRemappingReader Remappings;
574 DenseMap<SymbolRemappingReader::Key, FunctionSamples*> SampleMap;
575 std::unique_ptr<SampleProfileReader> UnderlyingReader;
578 } // end namespace sampleprof
580 } // end namespace llvm
582 #endif // LLVM_PROFILEDATA_SAMPLEPROFREADER_H