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