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