Line data Source code
1 : //===- SampleProfReader.h - Read LLVM sample profile data -------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file contains definitions needed for reading sample profiles.
11 : //
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.
15 : //
16 : // Text format
17 : // -----------
18 : //
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
22 : //
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 ... ]
26 : // ...
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 ... ]
30 : // ...
31 : //
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.
36 : //
37 : // Any line starting with the '#' character is completely ignored.
38 : //
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.
43 : //
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.
50 : //
51 : // There are two types of lines in the function body.
52 : //
53 : // * Sampled line represents the profile information of a source location.
54 : // * Callsite line represents the profile information of a callsite.
55 : //
56 : // Each sampled line may contain several items. Some are optional (marked
57 : // below):
58 : //
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.
64 : //
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
71 : // in the macro).
72 : //
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.
79 : //
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
86 : // frequently.
87 : //
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``.
92 : //
93 : // c. Number of samples. This is an integer quantity representing the
94 : // number of samples collected by the profiler at this source
95 : // location.
96 : //
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,
100 : //
101 : // 130: 7 foo:3 bar:2 baz:7
102 : //
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.
106 : //
107 : // Each callsite line may contain several items. Some are optional.
108 : //
109 : // a. Source line offset. This number represents the line number of the
110 : // callsite that is inlined in the profiled binary.
111 : //
112 : // b. [OPTIONAL] Discriminator. Same as the discriminator for sampled line.
113 : //
114 : // c. Number of samples. This is an integer quantity representing the
115 : // total number of samples collected for the inlined instance at this
116 : // callsite
117 : //
118 : //
119 : // Binary format
120 : // -------------
121 : //
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:
125 : //
126 : // MAGIC (uint64_t)
127 : // File identifier computed by function SPMagic() (0x5350524f463432ff)
128 : //
129 : // VERSION (uint32_t)
130 : // File format version number computed by SPVersion()
131 : //
132 : // SUMMARY
133 : // TOTAL_COUNT (uint64_t)
134 : // Total number of samples in the profile.
135 : // MAX_COUNT (uint64_t)
136 : // Maximum value of samples on a line.
137 : // MAX_FUNCTION_COUNT (uint64_t)
138 : // Maximum number of samples at function entry (head samples).
139 : // NUM_COUNTS (uint64_t)
140 : // Number of lines with samples.
141 : // NUM_FUNCTIONS (uint64_t)
142 : // Number of functions with samples.
143 : // NUM_DETAILED_SUMMARY_ENTRIES (size_t)
144 : // Number of entries in detailed summary
145 : // DETAILED_SUMMARY
146 : // A list of detailed summary entry. Each entry consists of
147 : // CUTOFF (uint32_t)
148 : // Required percentile of total sample count expressed as a fraction
149 : // multiplied by 1000000.
150 : // MIN_COUNT (uint64_t)
151 : // The minimum number of samples required to reach the target
152 : // CUTOFF.
153 : // NUM_COUNTS (uint64_t)
154 : // Number of samples to get to the desrired percentile.
155 : //
156 : // NAME TABLE
157 : // SIZE (uint32_t)
158 : // Number of entries in the name table.
159 : // NAMES
160 : // A NUL-separated list of SIZE strings.
161 : //
162 : // FUNCTION BODY (one for each uninlined function body present in the profile)
163 : // HEAD_SAMPLES (uint64_t) [only for top-level functions]
164 : // Total number of samples collected at the head (prologue) of the
165 : // function.
166 : // NOTE: This field should only be present for top-level functions
167 : // (i.e., not inlined into any caller). Inlined function calls
168 : // have no prologue, so they don't need this.
169 : // NAME_IDX (uint32_t)
170 : // Index into the name table indicating the function name.
171 : // SAMPLES (uint64_t)
172 : // Total number of samples collected in this function.
173 : // NRECS (uint32_t)
174 : // Total number of sampling records this function's profile.
175 : // BODY RECORDS
176 : // A list of NRECS entries. Each entry contains:
177 : // OFFSET (uint32_t)
178 : // Line offset from the start of the function.
179 : // DISCRIMINATOR (uint32_t)
180 : // Discriminator value (see description of discriminators
181 : // in the text format documentation above).
182 : // SAMPLES (uint64_t)
183 : // Number of samples collected at this location.
184 : // NUM_CALLS (uint32_t)
185 : // Number of non-inlined function calls made at this location. In the
186 : // case of direct calls, this number will always be 1. For indirect
187 : // calls (virtual functions and function pointers) this will
188 : // represent all the actual functions called at runtime.
189 : // CALL_TARGETS
190 : // A list of NUM_CALLS entries for each called function:
191 : // NAME_IDX (uint32_t)
192 : // Index into the name table with the callee name.
193 : // SAMPLES (uint64_t)
194 : // Number of samples collected at the call site.
195 : // NUM_INLINED_FUNCTIONS (uint32_t)
196 : // Number of callees inlined into this function.
197 : // INLINED FUNCTION RECORDS
198 : // A list of NUM_INLINED_FUNCTIONS entries describing each of the inlined
199 : // callees.
200 : // OFFSET (uint32_t)
201 : // Line offset from the start of the function.
202 : // DISCRIMINATOR (uint32_t)
203 : // Discriminator value (see description of discriminators
204 : // in the text format documentation above).
205 : // FUNCTION BODY
206 : // A FUNCTION BODY entry describing the inlined function.
207 : //===----------------------------------------------------------------------===//
208 :
209 : #ifndef LLVM_PROFILEDATA_SAMPLEPROFREADER_H
210 : #define LLVM_PROFILEDATA_SAMPLEPROFREADER_H
211 :
212 : #include "llvm/ADT/SmallVector.h"
213 : #include "llvm/ADT/StringMap.h"
214 : #include "llvm/ADT/StringRef.h"
215 : #include "llvm/ADT/Twine.h"
216 : #include "llvm/IR/DiagnosticInfo.h"
217 : #include "llvm/IR/Function.h"
218 : #include "llvm/IR/LLVMContext.h"
219 : #include "llvm/IR/ProfileSummary.h"
220 : #include "llvm/ProfileData/GCOV.h"
221 : #include "llvm/ProfileData/SampleProf.h"
222 : #include "llvm/Support/Debug.h"
223 : #include "llvm/Support/ErrorOr.h"
224 : #include "llvm/Support/MemoryBuffer.h"
225 : #include "llvm/Support/SymbolRemappingReader.h"
226 : #include <algorithm>
227 : #include <cstdint>
228 : #include <memory>
229 : #include <string>
230 : #include <system_error>
231 : #include <vector>
232 :
233 : namespace llvm {
234 :
235 : class raw_ostream;
236 :
237 : namespace sampleprof {
238 :
239 : /// Sample-based profile reader.
240 : ///
241 : /// Each profile contains sample counts for all the functions
242 : /// executed. Inside each function, statements are annotated with the
243 : /// collected samples on all the instructions associated with that
244 : /// statement.
245 : ///
246 : /// For this to produce meaningful data, the program needs to be
247 : /// compiled with some debug information (at minimum, line numbers:
248 : /// -gline-tables-only). Otherwise, it will be impossible to match IR
249 : /// instructions to the line numbers collected by the profiler.
250 : ///
251 : /// From the profile file, we are interested in collecting the
252 : /// following information:
253 : ///
254 : /// * A list of functions included in the profile (mangled names).
255 : ///
256 : /// * For each function F:
257 : /// 1. The total number of samples collected in F.
258 : ///
259 : /// 2. The samples collected at each line in F. To provide some
260 : /// protection against source code shuffling, line numbers should
261 : /// be relative to the start of the function.
262 : ///
263 : /// The reader supports two file formats: text and binary. The text format
264 : /// is useful for debugging and testing, while the binary format is more
265 : /// compact and I/O efficient. They can both be used interchangeably.
266 : class SampleProfileReader {
267 : public:
268 : SampleProfileReader(std::unique_ptr<MemoryBuffer> B, LLVMContext &C,
269 : SampleProfileFormat Format = SPF_None)
270 129 : : Profiles(0), Ctx(C), Buffer(std::move(B)), Format(Format) {}
271 :
272 242 : virtual ~SampleProfileReader() = default;
273 :
274 : /// Read and validate the file header.
275 : virtual std::error_code readHeader() = 0;
276 :
277 : /// Read sample profiles from the associated file.
278 : virtual std::error_code read() = 0;
279 :
280 : /// Print the profile for \p FName on stream \p OS.
281 : void dumpFunctionProfile(StringRef FName, raw_ostream &OS = dbgs());
282 :
283 83 : virtual void collectFuncsToUse(const Module &M) {}
284 :
285 : /// Print all the profiles on stream \p OS.
286 : void dump(raw_ostream &OS = dbgs());
287 :
288 : /// Return the samples collected for function \p F.
289 170 : FunctionSamples *getSamplesFor(const Function &F) {
290 : // The function name may have been updated by adding suffix. In sample
291 : // profile, the function names are all stripped, so we need to strip
292 : // the function name suffix before matching with profile.
293 340 : return getSamplesFor(F.getName().split('.').first);
294 : }
295 :
296 : /// Return the samples collected for function \p F.
297 174 : virtual FunctionSamples *getSamplesFor(StringRef Fname) {
298 : std::string FGUID;
299 174 : Fname = getRepInFormat(Fname, getFormat(), FGUID);
300 174 : auto It = Profiles.find(Fname);
301 348 : if (It != Profiles.end())
302 109 : return &It->second;
303 : return nullptr;
304 : }
305 :
306 : /// Return all the profiles.
307 : StringMap<FunctionSamples> &getProfiles() { return Profiles; }
308 :
309 : /// Report a parse error message.
310 8 : void reportError(int64_t LineNumber, Twine Msg) const {
311 16 : Ctx.diagnose(DiagnosticInfoSampleProfile(Buffer->getBufferIdentifier(),
312 : LineNumber, Msg));
313 0 : }
314 :
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);
318 :
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);
322 :
323 : /// Return the profile summary.
324 : ProfileSummary &getSummary() { return *(Summary.get()); }
325 :
326 : /// \brief Return the profile format.
327 0 : SampleProfileFormat getFormat() { return Format; }
328 :
329 : protected:
330 : /// Map every function to its associated profile.
331 : ///
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;
336 :
337 : /// LLVM context used to emit diagnostics.
338 : LLVMContext &Ctx;
339 :
340 : /// Memory buffer holding the profile file.
341 : std::unique_ptr<MemoryBuffer> Buffer;
342 :
343 : /// Profile summary information.
344 : std::unique_ptr<ProfileSummary> Summary;
345 :
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);
350 : }
351 :
352 : /// Compute summary for this profile.
353 : void computeSummary();
354 :
355 : /// \brief The format of sample.
356 : SampleProfileFormat Format = SPF_None;
357 : };
358 :
359 : class SampleProfileReaderText : public SampleProfileReader {
360 : public:
361 : SampleProfileReaderText(std::unique_ptr<MemoryBuffer> B, LLVMContext &C)
362 99 : : SampleProfileReader(std::move(B), C, SPF_Text) {}
363 :
364 : /// Read and validate the file header.
365 99 : std::error_code readHeader() override { return sampleprof_error::success; }
366 :
367 : /// Read sample profiles from the associated file.
368 : std::error_code read() override;
369 :
370 : /// Return true if \p Buffer is in the format supported by this class.
371 : static bool hasFormat(const MemoryBuffer &Buffer);
372 : };
373 :
374 : class SampleProfileReaderBinary : public SampleProfileReader {
375 : public:
376 : SampleProfileReaderBinary(std::unique_ptr<MemoryBuffer> B, LLVMContext &C,
377 : SampleProfileFormat Format = SPF_None)
378 5 : : SampleProfileReader(std::move(B), C, Format) {}
379 :
380 : /// Read and validate the file header.
381 : virtual std::error_code readHeader() override;
382 :
383 : /// Read sample profiles from the associated file.
384 : std::error_code read() override;
385 :
386 : protected:
387 : /// Read a numeric value of type T from the profile.
388 : ///
389 : /// If an error occurs during decoding, a diagnostic message is emitted and
390 : /// EC is set.
391 : ///
392 : /// \returns the read value.
393 : template <typename T> ErrorOr<T> readNumber();
394 :
395 : /// Read a numeric value of type T from the profile. The value is saved
396 : /// without encoded.
397 : template <typename T> ErrorOr<T> readUnencodedNumber();
398 :
399 : /// Read a string from the profile.
400 : ///
401 : /// If an error occurs during decoding, a diagnostic message is emitted and
402 : /// EC is set.
403 : ///
404 : /// \returns the read value.
405 : ErrorOr<StringRef> readString();
406 :
407 : /// Read the string index and check whether it overflows the table.
408 : template <typename T> inline ErrorOr<uint32_t> readStringIndex(T &Table);
409 :
410 : /// Return true if we've reached the end of file.
411 0 : bool at_eof() const { return Data >= End; }
412 :
413 : /// Read the next function profile instance.
414 : std::error_code readFuncProfile();
415 :
416 : /// Read the contents of the given profile instance.
417 : std::error_code readProfile(FunctionSamples &FProfile);
418 :
419 : /// Points to the current location in the buffer.
420 : const uint8_t *Data = nullptr;
421 :
422 : /// Points to the end of the buffer.
423 : const uint8_t *End = nullptr;
424 :
425 : private:
426 : std::error_code readSummaryEntry(std::vector<ProfileSummaryEntry> &Entries);
427 : virtual std::error_code verifySPMagic(uint64_t Magic) = 0;
428 :
429 : /// Read profile summary.
430 : std::error_code readSummary();
431 :
432 : /// Read the whole name table.
433 : virtual std::error_code readNameTable() = 0;
434 :
435 : /// Read a string indirectly via the name table.
436 : virtual ErrorOr<StringRef> readStringFromTable() = 0;
437 : };
438 :
439 : class SampleProfileReaderRawBinary : public SampleProfileReaderBinary {
440 : private:
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;
447 :
448 : public:
449 : SampleProfileReaderRawBinary(std::unique_ptr<MemoryBuffer> B, LLVMContext &C)
450 13 : : SampleProfileReaderBinary(std::move(B), C, SPF_Binary) {}
451 :
452 : /// \brief Return true if \p Buffer is in the format supported by this class.
453 : static bool hasFormat(const MemoryBuffer &Buffer);
454 : };
455 :
456 : class SampleProfileReaderCompactBinary : public SampleProfileReaderBinary {
457 : private:
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();
471 :
472 : public:
473 5 : SampleProfileReaderCompactBinary(std::unique_ptr<MemoryBuffer> B,
474 : LLVMContext &C)
475 5 : : SampleProfileReaderBinary(std::move(B), C, SPF_Compact_Binary) {}
476 :
477 : /// \brief Return true if \p Buffer is in the format supported by this class.
478 : static bool hasFormat(const MemoryBuffer &Buffer);
479 :
480 : /// Read samples only for functions to use.
481 : std::error_code read() override;
482 :
483 : /// Collect functions to be used when compiling Module \p M.
484 : void collectFuncsToUse(const Module &M) override;
485 : };
486 :
487 : using InlineCallStack = SmallVector<FunctionSamples *, 10>;
488 :
489 : // Supported histogram types in GCC. Currently, we only need support for
490 : // call target histograms.
491 : enum HistType {
492 : HIST_TYPE_INTERVAL,
493 : HIST_TYPE_POW2,
494 : HIST_TYPE_SINGLE_VALUE,
495 : HIST_TYPE_CONST_DELTA,
496 : HIST_TYPE_INDIR_CALL,
497 : HIST_TYPE_AVERAGE,
498 : HIST_TYPE_IOR,
499 : HIST_TYPE_INDIR_CALL_TOPN
500 : };
501 :
502 : class SampleProfileReaderGCC : public SampleProfileReader {
503 : public:
504 : SampleProfileReaderGCC(std::unique_ptr<MemoryBuffer> B, LLVMContext &C)
505 8 : : SampleProfileReader(std::move(B), C, SPF_GCC),
506 8 : GcovBuffer(Buffer.get()) {}
507 :
508 : /// Read and validate the file header.
509 : std::error_code readHeader() override;
510 :
511 : /// Read sample profiles from the associated file.
512 : std::error_code read() override;
513 :
514 : /// Return true if \p Buffer is in the format supported by this class.
515 : static bool hasFormat(const MemoryBuffer &Buffer);
516 :
517 : protected:
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();
525 :
526 : /// Read the section tag and check that it's the same as \p Expected.
527 : std::error_code readSectionTag(uint32_t Expected);
528 :
529 : /// GCOV buffer containing the profile.
530 : GCOVBuffer GcovBuffer;
531 :
532 : /// Function names in this profile.
533 : std::vector<std::string> Names;
534 :
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;
538 : };
539 :
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 {
544 : public:
545 4 : SampleProfileReaderItaniumRemapper(
546 : std::unique_ptr<MemoryBuffer> B, LLVMContext &C,
547 : std::unique_ptr<SampleProfileReader> Underlying)
548 8 : : SampleProfileReader(std::move(B), C, Underlying->getFormat()) {
549 4 : Profiles = std::move(Underlying->getProfiles());
550 : Summary = takeSummary(*Underlying);
551 4 : }
552 :
553 : /// Create a remapped sample profile from the given remapping file and
554 : /// underlying samples.
555 : static ErrorOr<std::unique_ptr<SampleProfileReader>>
556 : create(const Twine &Filename, LLVMContext &C,
557 : std::unique_ptr<SampleProfileReader> Underlying);
558 :
559 : /// Read and validate the file header.
560 0 : std::error_code readHeader() override { return sampleprof_error::success; }
561 :
562 : /// Read remapping file and apply it to the sample profile.
563 : std::error_code read() override;
564 :
565 : /// Return the samples collected for function \p F.
566 : FunctionSamples *getSamplesFor(StringRef FunctionName) override;
567 : using SampleProfileReader::getSamplesFor;
568 :
569 : private:
570 : SymbolRemappingReader Remappings;
571 : DenseMap<SymbolRemappingReader::Key, FunctionSamples*> SampleMap;
572 : };
573 :
574 : } // end namespace sampleprof
575 :
576 : } // end namespace llvm
577 :
578 : #endif // LLVM_PROFILEDATA_SAMPLEPROFREADER_H
|
