LLVM  6.0.0svn
SampleProf.h
Go to the documentation of this file.
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"
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 
40 
41 enum class sampleprof_error {
42  success = 0,
43  bad_magic,
45  too_large,
46  truncated,
47  malformed,
53 };
54 
55 inline std::error_code make_error_code(sampleprof_error E) {
56  return std::error_code(static_cast<int>(E), sampleprof_category());
57 }
58 
60  sampleprof_error Result) {
61  // Prefer first error encountered as later errors may be secondary effects of
62  // the initial problem.
63  if (Accumulator == sampleprof_error::success &&
64  Result != sampleprof_error::success)
65  Accumulator = Result;
66  return Accumulator;
67 }
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 static inline uint64_t SPMagic() {
82  return uint64_t('S') << (64 - 8) | uint64_t('P') << (64 - 16) |
83  uint64_t('R') << (64 - 24) | uint64_t('O') << (64 - 32) |
84  uint64_t('F') << (64 - 40) | uint64_t('4') << (64 - 48) |
85  uint64_t('2') << (64 - 56) | uint64_t(0xff);
86 }
87 
88 static inline uint64_t SPVersion() { return 103; }
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  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  bool operator<(const LineLocation &O) const {
106  return LineOffset < O.LineOffset ||
107  (LineOffset == O.LineOffset && Discriminator < O.Discriminator);
108  }
109 
112 };
113 
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.
127 public:
129 
130  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  sampleprof_error addSamples(uint64_t S, uint64_t Weight = 1) {
138  bool Overflowed;
139  NumSamples = SaturatingMultiplyAdd(S, Weight, NumSamples, &Overflowed);
140  return Overflowed ? sampleprof_error::counter_overflow
142  }
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.
150  uint64_t Weight = 1) {
151  uint64_t &TargetSamples = CallTargets[F];
152  bool Overflowed;
153  TargetSamples =
154  SaturatingMultiplyAdd(S, Weight, TargetSamples, &Overflowed);
155  return Overflowed ? sampleprof_error::counter_overflow
157  }
158 
159  /// Return true if this sample record contains function calls.
160  bool hasCalls() const { return !CallTargets.empty(); }
161 
162  uint64_t getSamples() const { return NumSamples; }
163  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>;
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.
197 public:
198  FunctionSamples() = default;
199 
200  void print(raw_ostream &OS = dbgs(), unsigned Indent = 0) const;
201  void dump() const;
202 
203  sampleprof_error addTotalSamples(uint64_t Num, uint64_t Weight = 1) {
204  bool Overflowed;
205  TotalSamples =
206  SaturatingMultiplyAdd(Num, Weight, TotalSamples, &Overflowed);
207  return Overflowed ? sampleprof_error::counter_overflow
209  }
210 
211  sampleprof_error addHeadSamples(uint64_t Num, uint64_t Weight = 1) {
212  bool Overflowed;
213  TotalHeadSamples =
214  SaturatingMultiplyAdd(Num, Weight, TotalHeadSamples, &Overflowed);
215  return Overflowed ? sampleprof_error::counter_overflow
217  }
218 
220  uint64_t Num, uint64_t Weight = 1) {
221  return BodySamples[LineLocation(LineOffset, Discriminator)].addSamples(
222  Num, Weight);
223  }
224 
226  uint32_t Discriminator,
227  const std::string &FName,
228  uint64_t Num, uint64_t Weight = 1) {
229  return BodySamples[LineLocation(LineOffset, Discriminator)].addCalledTarget(
230  FName, Num, Weight);
231  }
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.
237  uint32_t Discriminator) const {
238  const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator));
239  if (ret == BodySamples.end())
240  return std::error_code();
241  else
242  return ret->second.getSamples();
243  }
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.
249  findCallTargetMapAt(uint32_t LineOffset, uint32_t Discriminator) const {
250  const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator));
251  if (ret == BodySamples.end())
252  return std::error_code();
253  return ret->second.getCallTargets();
254  }
255 
256  /// Return the function samples at the given callsite location.
258  return CallsiteSamples[Loc];
259  }
260 
261  /// Returns the FunctionSamplesMap at the given \p Loc.
262  const FunctionSamplesMap *
264  auto iter = CallsiteSamples.find(Loc);
265  if (iter == CallsiteSamples.end())
266  return nullptr;
267  return &iter->second;
268  }
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.
275  StringRef CalleeName) const {
276  auto iter = CallsiteSamples.find(Loc);
277  if (iter == CallsiteSamples.end())
278  return nullptr;
279  auto FS = iter->second.find(CalleeName);
280  if (FS != iter->second.end())
281  return &FS->getValue();
282  // If we cannot find exact match of the callee name, return the FS with
283  // the max total count.
284  uint64_t MaxTotalSamples = 0;
285  const FunctionSamples *R = nullptr;
286  for (const auto &NameFS : iter->second)
287  if (NameFS.second.getTotalSamples() >= MaxTotalSamples) {
288  MaxTotalSamples = NameFS.second.getTotalSamples();
289  R = &NameFS.second;
290  }
291  return R;
292  }
293 
294  bool empty() const { return TotalSamples == 0; }
295 
296  /// Return the total number of samples collected inside the function.
297  uint64_t getTotalSamples() const { return TotalSamples; }
298 
299  /// Return the total number of branch samples that have the function as the
300  /// branch target. This should be equivalent to the sample of the first
301  /// instruction of the symbol. But as we directly get this info for raw
302  /// profile without referring to potentially inaccurate debug info, this
303  /// gives more accurate profile data and is preferred for standalone symbols.
304  uint64_t getHeadSamples() const { return TotalHeadSamples; }
305 
306  /// Return the sample count of the first instruction of the function.
307  /// The function can be either a standalone symbol or an inlined function.
308  uint64_t getEntrySamples() const {
309  // Use either BodySamples or CallsiteSamples which ever has the smaller
310  // lineno.
311  if (!BodySamples.empty() &&
312  (CallsiteSamples.empty() ||
313  BodySamples.begin()->first < CallsiteSamples.begin()->first))
314  return BodySamples.begin()->second.getSamples();
315  if (!CallsiteSamples.empty()) {
316  uint64_t T = 0;
317  // An indirect callsite may be promoted to several inlined direct calls.
318  // We need to get the sum of them.
319  for (const auto &N_FS : CallsiteSamples.begin()->second)
320  T += N_FS.second.getEntrySamples();
321  return T;
322  }
323  return 0;
324  }
325 
326  /// Return all the samples collected in the body of the function.
327  const BodySampleMap &getBodySamples() const { return BodySamples; }
328 
329  /// Return all the callsite samples collected in the body of the function.
331  return CallsiteSamples;
332  }
333 
334  /// Merge the samples in \p Other into this one.
335  /// Optionally scale samples by \p Weight.
336  sampleprof_error merge(const FunctionSamples &Other, uint64_t Weight = 1) {
338  Name = Other.getName();
339  MergeResult(Result, addTotalSamples(Other.getTotalSamples(), Weight));
340  MergeResult(Result, addHeadSamples(Other.getHeadSamples(), Weight));
341  for (const auto &I : Other.getBodySamples()) {
342  const LineLocation &Loc = I.first;
343  const SampleRecord &Rec = I.second;
344  MergeResult(Result, BodySamples[Loc].merge(Rec, Weight));
345  }
346  for (const auto &I : Other.getCallsiteSamples()) {
347  const LineLocation &Loc = I.first;
348  FunctionSamplesMap &FSMap = functionSamplesAt(Loc);
349  for (const auto &Rec : I.second)
350  MergeResult(Result, FSMap[Rec.first()].merge(Rec.second, Weight));
351  }
352  return Result;
353  }
354 
355  /// Recursively traverses all children, if the total sample count of the
356  /// corresponding function is no less than \p Threshold, add its corresponding
357  /// GUID to \p S. Also traverse the BodySamples to add hot CallTarget's GUID
358  /// to \p S.
360  uint64_t Threshold) const {
361  if (TotalSamples <= Threshold)
362  return;
364  // Import hot CallTargets, which may not be available in IR because full
365  // profile annotation cannot be done until backend compilation in ThinLTO.
366  for (const auto &BS : BodySamples)
367  for (const auto &TS : BS.second.getCallTargets())
368  if (TS.getValue() > Threshold) {
369  Function *Callee = M->getFunction(TS.getKey());
370  if (!Callee || !Callee->getSubprogram())
371  S.insert(Function::getGUID(TS.getKey()));
372  }
373  for (const auto &CS : CallsiteSamples)
374  for (const auto &NameFS : CS.second)
375  NameFS.second.findInlinedFunctions(S, M, Threshold);
376  }
377 
378  /// Set the name of the function.
379  void setName(StringRef FunctionName) { Name = FunctionName; }
380 
381  /// Return the function name.
382  const StringRef &getName() const { return Name; }
383 
384 private:
385  /// Mangled name of the function.
386  StringRef Name;
387 
388  /// Total number of samples collected inside this function.
389  ///
390  /// Samples are cumulative, they include all the samples collected
391  /// inside this function and all its inlined callees.
392  uint64_t TotalSamples = 0;
393 
394  /// Total number of samples collected at the head of the function.
395  /// This is an approximation of the number of calls made to this function
396  /// at runtime.
397  uint64_t TotalHeadSamples = 0;
398 
399  /// Map instruction locations to collected samples.
400  ///
401  /// Each entry in this map contains the number of samples
402  /// collected at the corresponding line offset. All line locations
403  /// are an offset from the start of the function.
404  BodySampleMap BodySamples;
405 
406  /// Map call sites to collected samples for the called function.
407  ///
408  /// Each entry in this map corresponds to all the samples
409  /// collected for the inlined function call at the given
410  /// location. For example, given:
411  ///
412  /// void foo() {
413  /// 1 bar();
414  /// ...
415  /// 8 baz();
416  /// }
417  ///
418  /// If the bar() and baz() calls were inlined inside foo(), this
419  /// map will contain two entries. One for all the samples collected
420  /// in the call to bar() at line offset 1, the other for all the samples
421  /// collected in the call to baz() at line offset 8.
422  CallsiteSampleMap CallsiteSamples;
423 };
424 
426 
427 /// Sort a LocationT->SampleT map by LocationT.
428 ///
429 /// It produces a sorted list of <LocationT, SampleT> records by ascending
430 /// order of LocationT.
431 template <class LocationT, class SampleT> class SampleSorter {
432 public:
433  using SamplesWithLoc = std::pair<const LocationT, SampleT>;
435 
436  SampleSorter(const std::map<LocationT, SampleT> &Samples) {
437  for (const auto &I : Samples)
438  V.push_back(&I);
439  std::stable_sort(V.begin(), V.end(),
440  [](const SamplesWithLoc *A, const SamplesWithLoc *B) {
441  return A->first < B->first;
442  });
443  }
444 
445  const SamplesWithLocList &get() const { return V; }
446 
447 private:
449 };
450 
451 } // end namespace sampleprof
452 } // end namespace llvm
453 
454 #endif // LLVM_PROFILEDATA_SAMPLEPROF_H
const FunctionSamplesMap * findFunctionSamplesMapAt(const LineLocation &Loc) const
Returns the FunctionSamplesMap at the given Loc.
Definition: SampleProf.h:263
Represents either an error or a value T.
Definition: ErrorOr.h:69
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
Implements a dense probed hash-table based set.
Definition: DenseSet.h:221
sampleprof_error merge(const SampleRecord &Other, uint64_t Weight=1)
Merge the samples in Other into this record.
Definition: SampleProf.h:167
LineLocation(uint32_t L, uint32_t D)
Definition: SampleProf.h:100
SampleSorter(const std::map< LocationT, SampleT > &Samples)
Definition: SampleProf.h:436
iterator find(StringRef Key)
Definition: StringMap.h:337
ErrorOr< uint64_t > findSamplesAt(uint32_t LineOffset, uint32_t Discriminator) const
Return the number of samples collected at the given location.
Definition: SampleProf.h:236
F(f)
std::pair< const LocationT, SampleT > SamplesWithLoc
Definition: SampleProf.h:433
void findInlinedFunctions(DenseSet< GlobalValue::GUID > &S, const Module *M, uint64_t Threshold) const
Recursively traverses all children, if the total sample count of the corresponding function is no les...
Definition: SampleProf.h:359
const StringRef & getName() const
Return the function name.
Definition: SampleProf.h:382
bool operator<(const LineLocation &O) const
Definition: SampleProf.h:105
Representation of the samples collected for a function.
Definition: SampleProf.h:196
Definition: BitVector.h:920
std::error_code make_error_code(BitcodeError E)
#define T
sampleprof_error addCalledTarget(StringRef F, uint64_t S, uint64_t Weight=1)
Add called function F with samples S.
Definition: SampleProf.h:149
Representation of a single sample record.
Definition: SampleProf.h:126
void setName(StringRef FunctionName)
Set the name of the function.
Definition: SampleProf.h:379
std::map< LineLocation, SampleRecord > BodySampleMap
Definition: SampleProf.h:187
static uint64_t SPVersion()
Definition: SampleProf.h:88
amdgpu Simplify well known AMD library false Value * Callee
Sort a LocationT->SampleT map by LocationT.
Definition: SampleProf.h:431
uint64_t getHeadSamples() const
Return the total number of branch samples that have the function as the branch target.
Definition: SampleProf.h:304
uint64_t getSamples() const
Definition: SampleProf.h:162
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
sampleprof_error
Definition: SampleProf.h:41
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1497
const BodySampleMap & getBodySamples() const
Return all the samples collected in the body of the function.
Definition: SampleProf.h:327
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
sampleprof_error addBodySamples(uint32_t LineOffset, uint32_t Discriminator, uint64_t Num, uint64_t Weight=1)
Definition: SampleProf.h:219
sampleprof_error addSamples(uint64_t S, uint64_t Weight=1)
Increment the number of samples for this record by S.
Definition: SampleProf.h:137
static ManagedStatic< _object_error_category > error_category
Definition: Error.cpp:74
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
std::enable_if< std::is_unsigned< T >::value, T >::type SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed=nullptr)
Multiply two unsigned integers, X and Y, and add the unsigned integer, A to the product.
Definition: MathExtras.h:831
const FunctionSamples * findFunctionSamplesAt(const LineLocation &Loc, StringRef CalleeName) const
Returns a pointer to FunctionSamples at the given callsite location Loc with callee CalleeName...
Definition: SampleProf.h:274
sampleprof_error addCalledTargetSamples(uint32_t LineOffset, uint32_t Discriminator, const std::string &FName, uint64_t Num, uint64_t Weight=1)
Definition: SampleProf.h:225
sampleprof_error addTotalSamples(uint64_t Num, uint64_t Weight=1)
Definition: SampleProf.h:203
Module.h This file contains the declarations for the Module class.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
FunctionSamplesMap & functionSamplesAt(const LineLocation &Loc)
Return the function samples at the given callsite location.
Definition: SampleProf.h:257
ErrorOr< SampleRecord::CallTargetMap > findCallTargetMapAt(uint32_t LineOffset, uint32_t Discriminator) const
Returns the call target map collected at a given location.
Definition: SampleProf.h:249
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Function * getFunction(StringRef Name) const
Look up the specified function in the module symbol table.
Definition: Module.cpp:172
const std::error_category & sampleprof_category()
Definition: SampleProf.cpp:69
GUID getGUID() const
Return a 64-bit global unique ID constructed from global value name (i.e.
Definition: GlobalValue.h:491
bool hasCalls() const
Return true if this sample record contains function calls.
Definition: SampleProf.h:160
std::map< LineLocation, FunctionSamplesMap > CallsiteSampleMap
Definition: SampleProf.h:189
static uint64_t SPMagic()
Definition: SampleProf.h:81
Represents the relative location of an instruction.
Definition: SampleProf.h:99
#define I(x, y, z)
Definition: MD5.cpp:58
const CallTargetMap & getCallTargets() const
Definition: SampleProf.h:163
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2018
sampleprof_error addHeadSamples(uint64_t Num, uint64_t Weight=1)
Definition: SampleProf.h:211
Provides ErrorOr<T> smart pointer.
static int const Threshold
TODO: Write a new FunctionPass AliasAnalysis so that it can keep a cache.
uint64_t getTotalSamples() const
Return the total number of samples collected inside the function.
Definition: SampleProf.h:297
const CallsiteSampleMap & getCallsiteSamples() const
Return all the callsite samples collected in the body of the function.
Definition: SampleProf.h:330
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
uint64_t getEntrySamples() const
Return the sample count of the first instruction of the function.
Definition: SampleProf.h:308
sampleprof_error merge(const FunctionSamples &Other, uint64_t Weight=1)
Merge the samples in Other into this one.
Definition: SampleProf.h:336
sampleprof_error MergeResult(sampleprof_error &Accumulator, sampleprof_error Result)
Definition: SampleProf.h:59