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   counter_overflow
  43 };
  44
  45 inline std::error_code make_error_code(sampleprof_error E) {
  46   return std::error_code(static_cast<int>(E), sampleprof_category());
  47 }
  48
  49 inline 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
  61 namespace std {
  62 template <>
  63 struct is_error_code_enum<llvm::sampleprof_error> : std::true_type {};
  64 }
  65
  66 namespace llvm {
  67
  68 namespace sampleprof {
  69
  70 static 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
  77 static 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++;").
  88 struct 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
 101 raw_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.
 109 struct 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
 118 raw_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.
 130 class SampleRecord {
 131 public:
 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
 195 private:
 196   uint64_t NumSamples;
 197   CallTargetMap CallTargets;
 198 };
 199
 200 raw_ostream &operator<<(raw_ostream &OS, const SampleRecord &Sample);
 201
 202 typedef std::map<LineLocation, SampleRecord> BodySampleMap;
 203 class FunctionSamples;
 204 typedef 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.
 211 class FunctionSamples {
 212 public:
 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
 319 private:
 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
 357 raw_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.
 363 template <class LocationT, class SampleT> class SampleSorter {
 364 public:
 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
 378 private:
 379   SamplesWithLocList V;
 380 };
 381
 382 } // end namespace sampleprof
 383
 384 } // end namespace llvm
 385
 386 #endif // LLVM_PROFILEDATA_SAMPLEPROF_H_