Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/ProfileData/SampleProfReader.h
Line
Count
Source (jump to first uncovered line)
1
//===- SampleProfReader.h - Read LLVM sample profile data -------*- 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 definitions needed for reading sample profiles.
10
//
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.
14
//
15
// Text format
16
// -----------
17
//
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
21
//
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 ... ]
25
//      ...
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 ... ]
29
//       ...
30
//
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.
35
//
36
// Any line starting with the '#' character is completely ignored.
37
//
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.
42
//
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.
49
//
50
// There are two types of lines in the function body.
51
//
52
// * Sampled line represents the profile information of a source location.
53
// * Callsite line represents the profile information of a callsite.
54
//
55
// Each sampled line may contain several items. Some are optional (marked
56
// below):
57
//
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.
63
//
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
70
//    in the macro).
71
//
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.
78
//
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
85
//    frequently.
86
//
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``.
91
//
92
// c. Number of samples. This is an integer quantity representing the
93
//    number of samples collected by the profiler at this source
94
//    location.
95
//
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,
99
//
100
//      130: 7  foo:3  bar:2  baz:7
101
//
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.
105
//
106
// Each callsite line may contain several items. Some are optional.
107
//
108
// a. Source line offset. This number represents the line number of the
109
//    callsite that is inlined in the profiled binary.
110
//
111
// b. [OPTIONAL] Discriminator. Same as the discriminator for sampled line.
112
//
113
// c. Number of samples. This is an integer quantity representing the
114
//    total number of samples collected for the inlined instance at this
115
//    callsite
116
//
117
//
118
// Binary format
119
// -------------
120
//
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:
124
//
125
// MAGIC (uint64_t)
126
//    File identifier computed by function SPMagic() (0x5350524f463432ff)
127
//
128
// VERSION (uint32_t)
129
//    File format version number computed by SPVersion()
130
//
131
// SUMMARY
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
144
//    DETAILED_SUMMARY
145
//        A list of detailed summary entry. Each entry consists of
146
//        CUTOFF (uint32_t)
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
151
//            CUTOFF.
152
//        NUM_COUNTS (uint64_t)
153
//            Number of samples to get to the desrired percentile.
154
//
155
// NAME TABLE
156
//    SIZE (uint32_t)
157
//        Number of entries in the name table.
158
//    NAMES
159
//        A NUL-separated list of SIZE strings.
160
//
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
164
//        function.
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.
172
//    NRECS (uint32_t)
173
//        Total number of sampling records this function's profile.
174
//    BODY RECORDS
175
//        A list of NRECS entries. Each entry contains:
176
//          OFFSET (uint32_t)
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.
188
//          CALL_TARGETS
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
198
//      callees.
199
//        OFFSET (uint32_t)
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).
204
//        FUNCTION BODY
205
//          A FUNCTION BODY entry describing the inlined function.
206
//===----------------------------------------------------------------------===//
207
208
#ifndef LLVM_PROFILEDATA_SAMPLEPROFREADER_H
209
#define LLVM_PROFILEDATA_SAMPLEPROFREADER_H
210
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"
225
#include <algorithm>
226
#include <cstdint>
227
#include <memory>
228
#include <string>
229
#include <system_error>
230
#include <vector>
231
232
namespace llvm {
233
234
class raw_ostream;
235
236
namespace sampleprof {
237
238
/// Sample-based profile reader.
239
///
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
243
/// statement.
244
///
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.
249
///
250
/// From the profile file, we are interested in collecting the
251
/// following information:
252
///
253
/// * A list of functions included in the profile (mangled names).
254
///
255
/// * For each function F:
256
///   1. The total number of samples collected in F.
257
///
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.
261
///
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 {
266
public:
267
  SampleProfileReader(std::unique_ptr<MemoryBuffer> B, LLVMContext &C,
268
                      SampleProfileFormat Format = SPF_None)
269
167
      : Profiles(0), Ctx(C), Buffer(std::move(B)), Format(Format) {}
270
271
159
  virtual ~SampleProfileReader() = default;
272
273
  /// Read and validate the file header.
274
  virtual std::error_code readHeader() = 0;
275
276
  /// Read sample profiles from the associated file.
277
  virtual std::error_code read() = 0;
278
279
  /// Print the profile for \p FName on stream \p OS.
280
  void dumpFunctionProfile(StringRef FName, raw_ostream &OS = dbgs());
281
282
105
  virtual void collectFuncsToUse(const Module &M) {}
283
284
  /// Print all the profiles on stream \p OS.
285
  void dump(raw_ostream &OS = dbgs());
286
287
  /// Return the samples collected for function \p F.
288
208
  FunctionSamples *getSamplesFor(const Function &F) {
289
208
    // The function name may have been updated by adding suffix. Call
290
208
    // a helper to (optionally) strip off suffixes so that we can
291
208
    // match against the original function name in the profile.
292
208
    StringRef CanonName = FunctionSamples::getCanonicalFnName(F);
293
208
    return getSamplesFor(CanonName);
294
208
  }
295
296
  /// Return the samples collected for function \p F.
297
230
  virtual FunctionSamples *getSamplesFor(StringRef Fname) {
298
230
    std::string FGUID;
299
230
    Fname = getRepInFormat(Fname, getFormat(), FGUID);
300
230
    auto It = Profiles.find(Fname);
301
230
    if (It != Profiles.end())
302
144
      return &It->second;
303
86
    return nullptr;
304
86
  }
305
306
  /// Return all the profiles.
307
138
  StringMap<FunctionSamples> &getProfiles() { return Profiles; }
308
309
  /// Report a parse error message.
310
8
  void reportError(int64_t LineNumber, Twine Msg) const {
311
8
    Ctx.diagnose(DiagnosticInfoSampleProfile(Buffer->getBufferIdentifier(),
312
8
                                             LineNumber, Msg));
313
8
  }
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
96
  ProfileSummary &getSummary() { return *(Summary.get()); }
325
326
  /// \brief Return the profile format.
327
401
  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
4
  takeSummary(SampleProfileReader &Reader) {
349
4
    return std::move(Reader.Summary);
350
4
  }
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
130
      : SampleProfileReader(std::move(B), C, SPF_Text) {}
363
364
  /// Read and validate the file header.
365
130
  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
25
      : 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
58
  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
17
      : 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
  SampleProfileReaderCompactBinary(std::unique_ptr<MemoryBuffer> B,
474
                                   LLVMContext &C)
475
8
      : 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
      : 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
  SampleProfileReaderItaniumRemapper(
546
      std::unique_ptr<MemoryBuffer> B, LLVMContext &C,
547
      std::unique_ptr<SampleProfileReader> Underlying)
548
4
      : SampleProfileReader(std::move(B), C, Underlying->getFormat()) {
549
4
    Profiles = std::move(Underlying->getProfiles());
550
4
    Summary = takeSummary(*Underlying);
551
4
    // Keep the underlying reader alive; the profile data may contain
552
4
    // StringRefs referencing names in its name table.
553
4
    UnderlyingReader = std::move(Underlying);
554
4
  }
555
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);
561
562
  /// Read and validate the file header.
563
0
  std::error_code readHeader() override { return sampleprof_error::success; }
564
565
  /// Read remapping file and apply it to the sample profile.
566
  std::error_code read() override;
567
568
  /// Return the samples collected for function \p F.
569
  FunctionSamples *getSamplesFor(StringRef FunctionName) override;
570
  using SampleProfileReader::getSamplesFor;
571
572
private:
573
  SymbolRemappingReader Remappings;
574
  DenseMap<SymbolRemappingReader::Key, FunctionSamples*> SampleMap;
575
  std::unique_ptr<SampleProfileReader> UnderlyingReader;
576
};
577
578
} // end namespace sampleprof
579
580
} // end namespace llvm
581
582
#endif // LLVM_PROFILEDATA_SAMPLEPROFREADER_H