1 //===- SampleProfReader.h - Read LLVM sample profile data -----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file contains definitions needed for reading sample profiles.
12 // NOTE: If you are making changes to this file format, please remember
13 // to document them in the Clang documentation at
14 // tools/clang/docs/UsersManual.rst.
19 // Sample profiles are written as ASCII text. The file is divided into
20 // sections, which correspond to each of the functions executed at runtime.
21 // Each section has the following format
23 // function1:total_samples:total_head_samples
24 // offset1[.discriminator]: number_of_samples [fn1:num fn2:num ... ]
25 // offset2[.discriminator]: number_of_samples [fn3:num fn4:num ... ]
27 // offsetN[.discriminator]: number_of_samples [fn5:num fn6:num ... ]
28 // offsetA[.discriminator]: fnA:num_of_total_samples
29 // offsetA1[.discriminator]: number_of_samples [fn7:num fn8:num ... ]
32 // This is a nested tree in which the identation represents the nesting level
33 // of the inline stack. There are no blank lines in the file. And the spacing
34 // within a single line is fixed. Additional spaces will result in an error
35 // while reading the file.
37 // Any line starting with the '#' character is completely ignored.
39 // Inlined calls are represented with indentation. The Inline stack is a
40 // stack of source locations in which the top of the stack represents the
41 // leaf function, and the bottom of the stack represents the actual
42 // symbol to which the instruction belongs.
44 // Function names must be mangled in order for the profile loader to
45 // match them in the current translation unit. The two numbers in the
46 // function header specify how many total samples were accumulated in the
47 // function (first number), and the total number of samples accumulated
48 // in the prologue of the function (second number). This head sample
49 // count provides an indicator of how frequently the function is invoked.
51 // There are two types of lines in the function body.
53 // * Sampled line represents the profile information of a source location.
54 // * Callsite line represents the profile information of a callsite.
56 // Each sampled line may contain several items. Some are optional (marked
59 // a. Source line offset. This number represents the line number
60 // in the function where the sample was collected. The line number is
61 // always relative to the line where symbol of the function is
62 // defined. So, if the function has its header at line 280, the offset
63 // 13 is at line 293 in the file.
65 // Note that this offset should never be a negative number. This could
66 // happen in cases like macros. The debug machinery will register the
67 // line number at the point of macro expansion. So, if the macro was
68 // expanded in a line before the start of the function, the profile
69 // converter should emit a 0 as the offset (this means that the optimizers
70 // will not be able to associate a meaningful weight to the instructions
73 // b. [OPTIONAL] Discriminator. This is used if the sampled program
74 // was compiled with DWARF discriminator support
75 // (http://wiki.dwarfstd.org/index.php?title=Path_Discriminators).
76 // DWARF discriminators are unsigned integer values that allow the
77 // compiler to distinguish between multiple execution paths on the
78 // same source line location.
80 // For example, consider the line of code ``if (cond) foo(); else bar();``.
81 // If the predicate ``cond`` is true 80% of the time, then the edge
82 // into function ``foo`` should be considered to be taken most of the
83 // time. But both calls to ``foo`` and ``bar`` are at the same source
84 // line, so a sample count at that line is not sufficient. The
85 // compiler needs to know which part of that line is taken more
88 // This is what discriminators provide. In this case, the calls to
89 // ``foo`` and ``bar`` will be at the same line, but will have
90 // different discriminator values. This allows the compiler to correctly
91 // set edge weights into ``foo`` and ``bar``.
93 // c. Number of samples. This is an integer quantity representing the
94 // number of samples collected by the profiler at this source
97 // d. [OPTIONAL] Potential call targets and samples. If present, this
98 // line contains a call instruction. This models both direct and
99 // number of samples. For example,
101 // 130: 7 foo:3 bar:2 baz:7
103 // The above means that at relative line offset 130 there is a call
104 // instruction that calls one of ``foo()``, ``bar()`` and ``baz()``,
105 // with ``baz()`` being the relatively more frequently called target.
107 // Each callsite line may contain several items. Some are optional.
109 // a. Source line offset. This number represents the line number of the
110 // callsite that is inlined in the profiled binary.
112 // b. [OPTIONAL] Discriminator. Same as the discriminator for sampled line.
114 // c. Number of samples. This is an integer quantity representing the
115 // total number of samples collected for the inlined instance at this
122 // This is a more compact encoding. Numbers are encoded as ULEB128 values
123 // and all strings are encoded in a name table. The file is organized in
124 // the following sections:
127 // File identifier computed by function SPMagic() (0x5350524f463432ff)
129 // VERSION (uint32_t)
130 // File format version number computed by SPVersion()
134 // Number of entries in the name table.
136 // A NUL-separated list of SIZE strings.
138 // FUNCTION BODY (one for each uninlined function body present in the profile)
139 // NAME_IDX (uint32_t)
140 // Index into the name table indicating the function name.
141 // SAMPLES (uint32_t)
142 // Total number of samples collected in this function.
143 // FIXME(dnovillo) this should be a uint64_t value.
144 // HEAD_SAMPLES (uint32_t)
145 // Total number of samples collected at the head of the function.
147 // Total number of sampling records this function's profile.
149 // A list of NRECS entries. Each entry contains:
151 // Line offset from the start of the function.
152 // DISCRIMINATOR (uint32_t)
153 // Discriminator value (see description of discriminators
154 // in the text format documentation above).
155 // SAMPLES (uint64_t)
156 // Number of samples collected at this location.
157 // NUM_CALLS (uint32_t)
158 // Number of non-inlined function calls made at this location. In the
159 // case of direct calls, this number will always be 1. For indirect
160 // calls (virtual functions and function pointers) this will
161 // represent all the actual functions called at runtime.
163 // A list of NUM_CALLS entries for each called function:
164 // NAME_IDX (uint32_t)
165 // Index into the name table with the callee name.
166 // SAMPLES (uint64_t)
167 // Number of samples collected at the call site.
168 // NUM_INLINED_FUNCTIONS (uint32_t)
169 // Number of callees inlined into this function.
170 // INLINED FUNCTION RECORDS
171 // A list of NUM_INLINED_FUNCTIONS entries describing each of the inlined
174 // Line offset from the start of the function.
175 // DISCRIMINATOR (uint32_t)
176 // Discriminator value (see description of discriminators
177 // in the text format documentation above).
179 // A FUNCTION BODY entry describing the inlined function.
180 //===----------------------------------------------------------------------===//
181 #ifndef LLVM_PROFILEDATA_SAMPLEPROFREADER_H
182 #define LLVM_PROFILEDATA_SAMPLEPROFREADER_H
184 #include "llvm/ADT/DenseMap.h"
185 #include "llvm/ADT/StringMap.h"
186 #include "llvm/ADT/StringRef.h"
187 #include "llvm/ADT/Twine.h"
188 #include "llvm/IR/DiagnosticInfo.h"
189 #include "llvm/IR/Function.h"
190 #include "llvm/IR/LLVMContext.h"
191 #include "llvm/ProfileData/SampleProf.h"
192 #include "llvm/Support/Debug.h"
193 #include "llvm/Support/ErrorHandling.h"
194 #include "llvm/Support/ErrorOr.h"
195 #include "llvm/Support/GCOV.h"
196 #include "llvm/Support/MemoryBuffer.h"
197 #include "llvm/Support/raw_ostream.h"
201 namespace sampleprof {
203 /// \brief Sample-based profile reader.
205 /// Each profile contains sample counts for all the functions
206 /// executed. Inside each function, statements are annotated with the
207 /// collected samples on all the instructions associated with that
210 /// For this to produce meaningful data, the program needs to be
211 /// compiled with some debug information (at minimum, line numbers:
212 /// -gline-tables-only). Otherwise, it will be impossible to match IR
213 /// instructions to the line numbers collected by the profiler.
215 /// From the profile file, we are interested in collecting the
216 /// following information:
218 /// * A list of functions included in the profile (mangled names).
220 /// * For each function F:
221 /// 1. The total number of samples collected in F.
223 /// 2. The samples collected at each line in F. To provide some
224 /// protection against source code shuffling, line numbers should
225 /// be relative to the start of the function.
227 /// The reader supports two file formats: text and binary. The text format
228 /// is useful for debugging and testing, while the binary format is more
229 /// compact and I/O efficient. They can both be used interchangeably.
230 class SampleProfileReader {
232 SampleProfileReader(std::unique_ptr<MemoryBuffer> B, LLVMContext &C)
233 : Profiles(0), Ctx(C), Buffer(std::move(B)) {}
235 virtual ~SampleProfileReader() {}
237 /// \brief Read and validate the file header.
238 virtual std::error_code readHeader() = 0;
240 /// \brief Read sample profiles from the associated file.
241 virtual std::error_code read() = 0;
243 /// \brief Print the profile for \p FName on stream \p OS.
244 void dumpFunctionProfile(StringRef FName, raw_ostream &OS = dbgs());
246 /// \brief Print all the profiles on stream \p OS.
247 void dump(raw_ostream &OS = dbgs());
249 /// \brief Return the samples collected for function \p F.
250 FunctionSamples *getSamplesFor(const Function &F) {
251 return &Profiles[F.getName()];
254 /// \brief Return all the profiles.
255 StringMap<FunctionSamples> &getProfiles() { return Profiles; }
257 /// \brief Report a parse error message.
258 void reportError(int64_t LineNumber, Twine Msg) const {
259 Ctx.diagnose(DiagnosticInfoSampleProfile(Buffer->getBufferIdentifier(),
263 /// \brief Create a sample profile reader appropriate to the file format.
264 static ErrorOr<std::unique_ptr<SampleProfileReader>>
265 create(StringRef Filename, LLVMContext &C);
268 /// \brief Map every function to its associated profile.
270 /// The profile of every function executed at runtime is collected
271 /// in the structure FunctionSamples. This maps function objects
272 /// to their corresponding profiles.
273 StringMap<FunctionSamples> Profiles;
275 /// \brief LLVM context used to emit diagnostics.
278 /// \brief Memory buffer holding the profile file.
279 std::unique_ptr<MemoryBuffer> Buffer;
282 class SampleProfileReaderText : public SampleProfileReader {
284 SampleProfileReaderText(std::unique_ptr<MemoryBuffer> B, LLVMContext &C)
285 : SampleProfileReader(std::move(B), C) {}
287 /// \brief Read and validate the file header.
288 std::error_code readHeader() override { return sampleprof_error::success; }
290 /// \brief Read sample profiles from the associated file.
291 std::error_code read() override;
294 class SampleProfileReaderBinary : public SampleProfileReader {
296 SampleProfileReaderBinary(std::unique_ptr<MemoryBuffer> B, LLVMContext &C)
297 : SampleProfileReader(std::move(B), C), Data(nullptr), End(nullptr) {}
299 /// \brief Read and validate the file header.
300 std::error_code readHeader() override;
302 /// \brief Read sample profiles from the associated file.
303 std::error_code read() override;
305 /// \brief Return true if \p Buffer is in the format supported by this class.
306 static bool hasFormat(const MemoryBuffer &Buffer);
309 /// \brief Read a numeric value of type T from the profile.
311 /// If an error occurs during decoding, a diagnostic message is emitted and
314 /// \returns the read value.
315 template <typename T> ErrorOr<T> readNumber();
317 /// \brief Read a string from the profile.
319 /// If an error occurs during decoding, a diagnostic message is emitted and
322 /// \returns the read value.
323 ErrorOr<StringRef> readString();
325 /// Read a string indirectly via the name table.
326 ErrorOr<StringRef> readStringFromTable();
328 /// \brief Return true if we've reached the end of file.
329 bool at_eof() const { return Data >= End; }
331 /// Read the contents of the given profile instance.
332 std::error_code readProfile(FunctionSamples &FProfile);
334 /// \brief Points to the current location in the buffer.
337 /// \brief Points to the end of the buffer.
340 /// Function name table.
341 std::vector<StringRef> NameTable;
344 typedef SmallVector<FunctionSamples *, 10> InlineCallStack;
346 // Supported histogram types in GCC. Currently, we only need support for
347 // call target histograms.
351 HIST_TYPE_SINGLE_VALUE,
352 HIST_TYPE_CONST_DELTA,
353 HIST_TYPE_INDIR_CALL,
356 HIST_TYPE_INDIR_CALL_TOPN
359 class SampleProfileReaderGCC : public SampleProfileReader {
361 SampleProfileReaderGCC(std::unique_ptr<MemoryBuffer> B, LLVMContext &C)
362 : SampleProfileReader(std::move(B), C), GcovBuffer(Buffer.get()) {}
364 /// \brief Read and validate the file header.
365 std::error_code readHeader() override;
367 /// \brief Read sample profiles from the associated file.
368 std::error_code read() override;
370 /// \brief Return true if \p Buffer is in the format supported by this class.
371 static bool hasFormat(const MemoryBuffer &Buffer);
374 std::error_code readNameTable();
375 std::error_code readOneFunctionProfile(const InlineCallStack &InlineStack,
376 bool Update, uint32_t Offset);
377 std::error_code readFunctionProfiles();
378 std::error_code skipNextWord();
379 template <typename T> ErrorOr<T> readNumber();
380 ErrorOr<StringRef> readString();
382 /// \brief Read the section tag and check that it's the same as \p Expected.
383 std::error_code readSectionTag(uint32_t Expected);
385 /// GCOV buffer containing the profile.
386 GCOVBuffer GcovBuffer;
388 /// Function names in this profile.
389 std::vector<std::string> Names;
391 /// GCOV tags used to separate sections in the profile file.
392 static const uint32_t GCOVTagAFDOFileNames = 0xaa000000;
393 static const uint32_t GCOVTagAFDOFunction = 0xac000000;
396 } // End namespace sampleprof
398 } // End namespace llvm
400 #endif // LLVM_PROFILEDATA_SAMPLEPROFREADER_H