Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/ProfileData/SampleProf.h
Line
Count
Source (jump to first uncovered line)
1
//===- SampleProf.h - Sampling profiling format support ---------*- 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 common definitions used in the reading and writing of
11
// sample profile data.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#ifndef LLVM_PROFILEDATA_SAMPLEPROF_H
16
#define LLVM_PROFILEDATA_SAMPLEPROF_H
17
18
#include "llvm/ADT/DenseSet.h"
19
#include "llvm/ADT/SmallVector.h"
20
#include "llvm/ADT/StringMap.h"
21
#include "llvm/ADT/StringRef.h"
22
#include "llvm/IR/Function.h"
23
#include "llvm/IR/GlobalValue.h"
24
#include "llvm/IR/Module.h"
25
#include "llvm/Support/Debug.h"
26
#include "llvm/Support/ErrorOr.h"
27
#include "llvm/Support/MathExtras.h"
28
#include <algorithm>
29
#include <cstdint>
30
#include <map>
31
#include <string>
32
#include <system_error>
33
#include <utility>
34
35
namespace llvm {
36
37
class raw_ostream;
38
39
const std::error_category &sampleprof_category();
40
41
enum class sampleprof_error {
42
  success = 0,
43
  bad_magic,
44
  unsupported_version,
45
  too_large,
46
  truncated,
47
  malformed,
48
  unrecognized_format,
49
  unsupported_writing_format,
50
  truncated_name_table,
51
  not_implemented,
52
  counter_overflow
53
};
54
55
2.50k
inline std::error_code make_error_code(sampleprof_error E) {
56
2.50k
  return std::error_code(static_cast<int>(E), sampleprof_category());
57
2.50k
}
58
59
inline sampleprof_error MergeResult(sampleprof_error &Accumulator,
60
1.31k
                                    sampleprof_error Result) {
61
1.31k
  // Prefer first error encountered as later errors may be secondary effects of
62
1.31k
  // the initial problem.
63
1.31k
  if (Accumulator == sampleprof_error::success &&
64
1.31k
      Result != sampleprof_error::success)
65
5
    Accumulator = Result;
66
1.31k
  return Accumulator;
67
1.31k
}
68
69
} // end namespace llvm
70
71
namespace std {
72
73
template <>
74
struct is_error_code_enum<llvm::sampleprof_error> : std::true_type {};
75
76
} // end namespace std
77
78
namespace llvm {
79
namespace sampleprof {
80
81
120
static inline uint64_t SPMagic() {
82
120
  return uint64_t('S') << (64 - 8) | uint64_t('P') << (64 - 16) |
83
120
         uint64_t('R') << (64 - 24) | uint64_t('O') << (64 - 32) |
84
120
         uint64_t('F') << (64 - 40) | uint64_t('4') << (64 - 48) |
85
120
         uint64_t('2') << (64 - 56) | uint64_t(0xff);
86
120
}
Unexecuted instantiation: ProfileSummaryBuilder.cpp:llvm::sampleprof::SPMagic()
SampleProfReader.cpp:llvm::sampleprof::SPMagic()
Line
Count
Source
81
120
static inline uint64_t SPMagic() {
82
120
  return uint64_t('S') << (64 - 8) | uint64_t('P') << (64 - 16) |
83
120
         uint64_t('R') << (64 - 24) | uint64_t('O') << (64 - 32) |
84
120
         uint64_t('F') << (64 - 40) | uint64_t('4') << (64 - 48) |
85
120
         uint64_t('2') << (64 - 56) | uint64_t(0xff);
86
120
}
Unexecuted instantiation: SampleProfile.cpp:llvm::sampleprof::SPMagic()
Unexecuted instantiation: SampleProf.cpp:llvm::sampleprof::SPMagic()
87
88
12
static inline uint64_t SPVersion() { return 103; }
Unexecuted instantiation: ProfileSummaryBuilder.cpp:llvm::sampleprof::SPVersion()
SampleProfReader.cpp:llvm::sampleprof::SPVersion()
Line
Count
Source
88
12
static inline uint64_t SPVersion() { return 103; }
Unexecuted instantiation: SampleProfile.cpp:llvm::sampleprof::SPVersion()
Unexecuted instantiation: SampleProf.cpp:llvm::sampleprof::SPVersion()
89
90
/// Represents the relative location of an instruction.
91
///
92
/// Instruction locations are specified by the line offset from the
93
/// beginning of the function (marked by the line where the function
94
/// header is) and the discriminator value within that line.
95
///
96
/// The discriminator value is useful to distinguish instructions
97
/// that are on the same line but belong to different basic blocks
98
/// (e.g., the two post-increment instructions in "if (p) x++; else y++;").
99
struct LineLocation {
100
2.49k
  LineLocation(uint32_t L, uint32_t D) : LineOffset(L), Discriminator(D) {}
101
102
  void print(raw_ostream &OS) const;
103
  void dump() const;
104
105
9.00k
  bool operator<(const LineLocation &O) const {
106
9.00k
    return LineOffset < O.LineOffset ||
107
5.96k
           
(LineOffset == O.LineOffset && 5.96k
Discriminator < O.Discriminator3.62k
);
108
9.00k
  }
109
110
  uint32_t LineOffset;
111
  uint32_t Discriminator;
112
};
113
114
raw_ostream &operator<<(raw_ostream &OS, const LineLocation &Loc);
115
116
/// Representation of a single sample record.
117
///
118
/// A sample record is represented by a positive integer value, which
119
/// indicates how frequently was the associated line location executed.
120
///
121
/// Additionally, if the associated location contains a function call,
122
/// the record will hold a list of all the possible called targets. For
123
/// direct calls, this will be the exact function being invoked. For
124
/// indirect calls (function pointers, virtual table dispatch), this
125
/// will be a list of one or more functions.
126
class SampleRecord {
127
public:
128
  using CallTargetMap = StringMap<uint64_t>;
129
130
882
  SampleRecord() = default;
131
132
  /// Increment the number of samples for this record by \p S.
133
  /// Optionally scale sample count \p S by \p Weight.
134
  ///
135
  /// Sample counts accumulate using saturating arithmetic, to avoid wrapping
136
  /// around unsigned integers.
137
943
  sampleprof_error addSamples(uint64_t S, uint64_t Weight = 1) {
138
943
    bool Overflowed;
139
943
    NumSamples = SaturatingMultiplyAdd(S, Weight, NumSamples, &Overflowed);
140
3
    return Overflowed ? sampleprof_error::counter_overflow
141
940
                      : sampleprof_error::success;
142
943
  }
143
144
  /// Add called function \p F with samples \p S.
145
  /// Optionally scale sample count \p S by \p Weight.
146
  ///
147
  /// Sample counts accumulate using saturating arithmetic, to avoid wrapping
148
  /// around unsigned integers.
149
  sampleprof_error addCalledTarget(StringRef F, uint64_t S,
150
84
                                   uint64_t Weight = 1) {
151
84
    uint64_t &TargetSamples = CallTargets[F];
152
84
    bool Overflowed;
153
84
    TargetSamples =
154
84
        SaturatingMultiplyAdd(S, Weight, TargetSamples, &Overflowed);
155
2
    return Overflowed ? sampleprof_error::counter_overflow
156
82
                      : sampleprof_error::success;
157
84
  }
158
159
  /// Return true if this sample record contains function calls.
160
132
  bool hasCalls() const { return !CallTargets.empty(); }
161
162
1.49k
  uint64_t getSamples() const { return NumSamples; }
163
581
  const CallTargetMap &getCallTargets() const { return CallTargets; }
164
165
  /// Merge the samples in \p Other into this record.
166
  /// Optionally scale sample counts by \p Weight.
167
  sampleprof_error merge(const SampleRecord &Other, uint64_t Weight = 1) {
168
    sampleprof_error Result = addSamples(Other.getSamples(), Weight);
169
    for (const auto &I : Other.getCallTargets()) {
170
      MergeResult(Result, addCalledTarget(I.first(), I.second, Weight));
171
    }
172
    return Result;
173
  }
174
175
  void print(raw_ostream &OS, unsigned Indent) const;
176
  void dump() const;
177
178
private:
179
  uint64_t NumSamples = 0;
180
  CallTargetMap CallTargets;
181
};
182
183
raw_ostream &operator<<(raw_ostream &OS, const SampleRecord &Sample);
184
185
class FunctionSamples;
186
187
using BodySampleMap = std::map<LineLocation, SampleRecord>;
188
using FunctionSamplesMap = StringMap<FunctionSamples>;
189
using CallsiteSampleMap = std::map<LineLocation, FunctionSamplesMap>;
190
191
/// Representation of the samples collected for a function.
192
///
193
/// This data structure contains all the collected samples for the body
194
/// of a function. Each sample corresponds to a LineLocation instance
195
/// within the body of the function.
196
class FunctionSamples {
197
public:
198
505
  FunctionSamples() = default;
199
200
  void print(raw_ostream &OS = dbgs(), unsigned Indent = 0) const;
201
  void dump() const;
202
203
530
  sampleprof_error addTotalSamples(uint64_t Num, uint64_t Weight = 1) {
204
530
    bool Overflowed;
205
530
    TotalSamples =
206
530
        SaturatingMultiplyAdd(Num, Weight, TotalSamples, &Overflowed);
207
3
    return Overflowed ? sampleprof_error::counter_overflow
208
527
                      : sampleprof_error::success;
209
530
  }
210
211
259
  sampleprof_error addHeadSamples(uint64_t Num, uint64_t Weight = 1) {
212
259
    bool Overflowed;
213
259
    TotalHeadSamples =
214
259
        SaturatingMultiplyAdd(Num, Weight, TotalHeadSamples, &Overflowed);
215
1
    return Overflowed ? sampleprof_error::counter_overflow
216
258
                      : sampleprof_error::success;
217
259
  }
218
219
  sampleprof_error addBodySamples(uint32_t LineOffset, uint32_t Discriminator,
220
693
                                  uint64_t Num, uint64_t Weight = 1) {
221
693
    return BodySamples[LineLocation(LineOffset, Discriminator)].addSamples(
222
693
        Num, Weight);
223
693
  }
224
225
  sampleprof_error addCalledTargetSamples(uint32_t LineOffset,
226
                                          uint32_t Discriminator,
227
                                          const std::string &FName,
228
63
                                          uint64_t Num, uint64_t Weight = 1) {
229
63
    return BodySamples[LineLocation(LineOffset, Discriminator)].addCalledTarget(
230
63
        FName, Num, Weight);
231
63
  }
232
233
  /// Return the number of samples collected at the given location.
234
  /// Each location is specified by \p LineOffset and \p Discriminator.
235
  /// If the location is not found in profile, return error.
236
  ErrorOr<uint64_t> findSamplesAt(uint32_t LineOffset,
237
712
                                  uint32_t Discriminator) const {
238
712
    const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator));
239
712
    if (ret == BodySamples.end())
240
136
      return std::error_code();
241
712
    else
242
576
      return ret->second.getSamples();
243
712
  }
244
245
  /// Returns the call target map collected at a given location.
246
  /// Each location is specified by \p LineOffset and \p Discriminator.
247
  /// If the location is not found in profile, return error.
248
  ErrorOr<SampleRecord::CallTargetMap>
249
21
  findCallTargetMapAt(uint32_t LineOffset, uint32_t Discriminator) const {
250
21
    const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator));
251
21
    if (ret == BodySamples.end())
252
5
      return std::error_code();
253
16
    return ret->second.getCallTargets();
254
21
  }
255
256
  /// Return the function samples at the given callsite location.
257
157
  FunctionSamplesMap &functionSamplesAt(const LineLocation &Loc) {
258
157
    return CallsiteSamples[Loc];
259
157
  }
260
261
  /// Returns the FunctionSamplesMap at the given \p Loc.
262
  const FunctionSamplesMap *
263
17
  findFunctionSamplesMapAt(const LineLocation &Loc) const {
264
17
    auto iter = CallsiteSamples.find(Loc);
265
17
    if (iter == CallsiteSamples.end())
266
0
      return nullptr;
267
17
    return &iter->second;
268
17
  }
269
270
  /// Returns a pointer to FunctionSamples at the given callsite location \p Loc
271
  /// with callee \p CalleeName. If no callsite can be found, relax the
272
  /// restriction to return the FunctionSamples at callsite location \p Loc
273
  /// with the maximum total sample count.
274
  const FunctionSamples *findFunctionSamplesAt(const LineLocation &Loc,
275
299
                                               StringRef CalleeName) const {
276
299
    auto iter = CallsiteSamples.find(Loc);
277
299
    if (iter == CallsiteSamples.end())
278
138
      return nullptr;
279
161
    auto FS = iter->second.find(CalleeName);
280
161
    if (FS != iter->second.end())
281
126
      return &FS->getValue();
282
161
    // If we cannot find exact match of the callee name, return the FS with
283
161
    // the max total count.
284
35
    uint64_t MaxTotalSamples = 0;
285
35
    const FunctionSamples *R = nullptr;
286
35
    for (const auto &NameFS : iter->second)
287
41
      
if (41
NameFS.second.getTotalSamples() >= MaxTotalSamples41
) {
288
41
        MaxTotalSamples = NameFS.second.getTotalSamples();
289
41
        R = &NameFS.second;
290
41
      }
291
35
    return R;
292
299
  }
293
294
81
  bool empty() const { return TotalSamples == 0; }
295
296
  /// Return the total number of samples collected inside the function.
297
523
  uint64_t getTotalSamples() const { return TotalSamples; }
298
299
  /// Return the total number of samples collected at the head of the
300
  /// function.
301
488
  uint64_t getHeadSamples() const { return TotalHeadSamples; }
302
303
  /// Return all the samples collected in the body of the function.
304
374
  const BodySampleMap &getBodySamples() const { return BodySamples; }
305
306
  /// Return all the callsite samples collected in the body of the function.
307
235
  const CallsiteSampleMap &getCallsiteSamples() const {
308
235
    return CallsiteSamples;
309
235
  }
310
311
  /// Merge the samples in \p Other into this one.
312
  /// Optionally scale samples by \p Weight.
313
  sampleprof_error merge(const FunctionSamples &Other, uint64_t Weight = 1) {
314
    sampleprof_error Result = sampleprof_error::success;
315
    Name = Other.getName();
316
    MergeResult(Result, addTotalSamples(Other.getTotalSamples(), Weight));
317
    MergeResult(Result, addHeadSamples(Other.getHeadSamples(), Weight));
318
    for (const auto &I : Other.getBodySamples()) {
319
      const LineLocation &Loc = I.first;
320
      const SampleRecord &Rec = I.second;
321
      MergeResult(Result, BodySamples[Loc].merge(Rec, Weight));
322
    }
323
    for (const auto &I : Other.getCallsiteSamples()) {
324
      const LineLocation &Loc = I.first;
325
      FunctionSamplesMap &FSMap = functionSamplesAt(Loc);
326
      for (const auto &Rec : I.second)
327
        MergeResult(Result, FSMap[Rec.first()].merge(Rec.second, Weight));
328
    }
329
    return Result;
330
  }
331
332
  /// Recursively traverses all children, if the corresponding function is
333
  /// not defined in module \p M, and its total sample is no less than
334
  /// \p Threshold, add its corresponding GUID to \p S.
335
  void findImportedFunctions(DenseSet<GlobalValue::GUID> &S, const Module *M,
336
15
                             uint64_t Threshold) const {
337
15
    if (TotalSamples <= Threshold)
338
1
      return;
339
14
    Function *F = M->getFunction(Name);
340
14
    if (
!F || 14
!F->getSubprogram()9
)
341
8
      S.insert(Function::getGUID(Name));
342
14
    for (auto CS : CallsiteSamples)
343
2
      for (const auto &NameFS : CS.second)
344
2
        NameFS.second.findImportedFunctions(S, M, Threshold);
345
15
  }
346
347
  /// Set the name of the function.
348
280
  void setName(StringRef FunctionName) { Name = FunctionName; }
349
350
  /// Return the function name.
351
207
  const StringRef &getName() const { return Name; }
352
353
private:
354
  /// Mangled name of the function.
355
  StringRef Name;
356
357
  /// Total number of samples collected inside this function.
358
  ///
359
  /// Samples are cumulative, they include all the samples collected
360
  /// inside this function and all its inlined callees.
361
  uint64_t TotalSamples = 0;
362
363
  /// Total number of samples collected at the head of the function.
364
  /// This is an approximation of the number of calls made to this function
365
  /// at runtime.
366
  uint64_t TotalHeadSamples = 0;
367
368
  /// Map instruction locations to collected samples.
369
  ///
370
  /// Each entry in this map contains the number of samples
371
  /// collected at the corresponding line offset. All line locations
372
  /// are an offset from the start of the function.
373
  BodySampleMap BodySamples;
374
375
  /// Map call sites to collected samples for the called function.
376
  ///
377
  /// Each entry in this map corresponds to all the samples
378
  /// collected for the inlined function call at the given
379
  /// location. For example, given:
380
  ///
381
  ///     void foo() {
382
  ///  1    bar();
383
  ///  ...
384
  ///  8    baz();
385
  ///     }
386
  ///
387
  /// If the bar() and baz() calls were inlined inside foo(), this
388
  /// map will contain two entries.  One for all the samples collected
389
  /// in the call to bar() at line offset 1, the other for all the samples
390
  /// collected in the call to baz() at line offset 8.
391
  CallsiteSampleMap CallsiteSamples;
392
};
393
394
raw_ostream &operator<<(raw_ostream &OS, const FunctionSamples &FS);
395
396
/// Sort a LocationT->SampleT map by LocationT.
397
///
398
/// It produces a sorted list of <LocationT, SampleT> records by ascending
399
/// order of LocationT.
400
template <class LocationT, class SampleT> class SampleSorter {
401
public:
402
  using SamplesWithLoc = std::pair<const LocationT, SampleT>;
403
  using SamplesWithLocList = SmallVector<const SamplesWithLoc *, 20>;
404
405
153
  SampleSorter(const std::map<LocationT, SampleT> &Samples) {
406
153
    for (const auto &I : Samples)
407
333
      V.push_back(&I);
408
153
    std::stable_sort(V.begin(), V.end(),
409
210
                     [](const SamplesWithLoc *A, const SamplesWithLoc *B) {
410
210
                       return A->first < B->first;
411
210
                     });
llvm::sampleprof::SampleSorter<llvm::sampleprof::LineLocation, llvm::StringMap<llvm::sampleprof::FunctionSamples, llvm::MallocAllocator> >::SampleSorter(std::__1::map<llvm::sampleprof::LineLocation, llvm::StringMap<llvm::sampleprof::FunctionSamples, llvm::MallocAllocator>, std::__1::less<llvm::sampleprof::LineLocation>, std::__1::allocator<std::__1::pair<llvm::sampleprof::LineLocation const, llvm::StringMap<llvm::sampleprof::FunctionSamples, llvm::MallocAllocator> > > > const&)::'lambda'(std::__1::pair<llvm::sampleprof::LineLocation const, llvm::StringMap<llvm::sampleprof::FunctionSamples, llvm::MallocAllocator> > const*, std::__1::pair<llvm::sampleprof::LineLocation const, llvm::StringMap<llvm::sampleprof::FunctionSamples, llvm::MallocAllocator> > const*)::operator()(std::__1::pair<llvm::sampleprof::LineLocation const, llvm::StringMap<llvm::sampleprof::FunctionSamples, llvm::MallocAllocator> > const*, std::__1::pair<llvm::sampleprof::LineLocation const, llvm::StringMap<llvm::sampleprof::FunctionSamples, llvm::MallocAllocator> > const*) const
Line
Count
Source
409
24
                     [](const SamplesWithLoc *A, const SamplesWithLoc *B) {
410
24
                       return A->first < B->first;
411
24
                     });
llvm::sampleprof::SampleSorter<llvm::sampleprof::LineLocation, llvm::sampleprof::SampleRecord>::SampleSorter(std::__1::map<llvm::sampleprof::LineLocation, llvm::sampleprof::SampleRecord, std::__1::less<llvm::sampleprof::LineLocation>, std::__1::allocator<std::__1::pair<llvm::sampleprof::LineLocation const, llvm::sampleprof::SampleRecord> > > const&)::'lambda'(std::__1::pair<llvm::sampleprof::LineLocation const, llvm::sampleprof::SampleRecord> const*, std::__1::pair<llvm::sampleprof::LineLocation const, llvm::sampleprof::SampleRecord> const*)::operator()(std::__1::pair<llvm::sampleprof::LineLocation const, llvm::sampleprof::SampleRecord> const*, std::__1::pair<llvm::sampleprof::LineLocation const, llvm::sampleprof::SampleRecord> const*) const
Line
Count
Source
409
186
                     [](const SamplesWithLoc *A, const SamplesWithLoc *B) {
410
186
                       return A->first < B->first;
411
186
                     });
412
153
  }
llvm::sampleprof::SampleSorter<llvm::sampleprof::LineLocation, llvm::StringMap<llvm::sampleprof::FunctionSamples, llvm::MallocAllocator> >::SampleSorter(std::__1::map<llvm::sampleprof::LineLocation, llvm::StringMap<llvm::sampleprof::FunctionSamples, llvm::MallocAllocator>, std::__1::less<llvm::sampleprof::LineLocation>, std::__1::allocator<std::__1::pair<llvm::sampleprof::LineLocation const, llvm::StringMap<llvm::sampleprof::FunctionSamples, llvm::MallocAllocator> > > > const&)
Line
Count
Source
405
58
  SampleSorter(const std::map<LocationT, SampleT> &Samples) {
406
58
    for (const auto &I : Samples)
407
52
      V.push_back(&I);
408
58
    std::stable_sort(V.begin(), V.end(),
409
58
                     [](const SamplesWithLoc *A, const SamplesWithLoc *B) {
410
58
                       return A->first < B->first;
411
58
                     });
412
58
  }
llvm::sampleprof::SampleSorter<llvm::sampleprof::LineLocation, llvm::sampleprof::SampleRecord>::SampleSorter(std::__1::map<llvm::sampleprof::LineLocation, llvm::sampleprof::SampleRecord, std::__1::less<llvm::sampleprof::LineLocation>, std::__1::allocator<std::__1::pair<llvm::sampleprof::LineLocation const, llvm::sampleprof::SampleRecord> > > const&)
Line
Count
Source
405
95
  SampleSorter(const std::map<LocationT, SampleT> &Samples) {
406
95
    for (const auto &I : Samples)
407
281
      V.push_back(&I);
408
95
    std::stable_sort(V.begin(), V.end(),
409
95
                     [](const SamplesWithLoc *A, const SamplesWithLoc *B) {
410
95
                       return A->first < B->first;
411
95
                     });
412
95
  }
413
414
153
  const SamplesWithLocList &get() const { return V; }
llvm::sampleprof::SampleSorter<llvm::sampleprof::LineLocation, llvm::sampleprof::SampleRecord>::get() const
Line
Count
Source
414
95
  const SamplesWithLocList &get() const { return V; }
llvm::sampleprof::SampleSorter<llvm::sampleprof::LineLocation, llvm::StringMap<llvm::sampleprof::FunctionSamples, llvm::MallocAllocator> >::get() const
Line
Count
Source
414
58
  const SamplesWithLocList &get() const { return V; }
415
416
private:
417
  SamplesWithLocList V;
418
};
419
420
} // end namespace sampleprof
421
} // end namespace llvm
422
423
#endif // LLVM_PROFILEDATA_SAMPLEPROF_H