include/llvm/ProfileData/SampleProf.h

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