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 #ifndef LLVM_PROFILEDATA_SAMPLEPROF_H_
  15 #define LLVM_PROFILEDATA_SAMPLEPROF_H_
  16
  17 #include "llvm/ADT/DenseMap.h"
  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 #include <system_error>
  24
  25 namespace llvm {
  26
  27 const std::error_category &sampleprof_category();
  28
  29 enum class sampleprof_error {
  30   success = 0,
  31   bad_magic,
  32   unsupported_version,
  33   too_large,
  34   truncated,
  35   malformed,
  36   unrecognized_format,
  37   unsupported_writing_format,
  38   truncated_name_table,
  39   not_implemented
  40 };
  41
  42 inline std::error_code make_error_code(sampleprof_error E) {
  43   return std::error_code(static_cast<int>(E), sampleprof_category());
  44 }
  45
  46 } // end namespace llvm
  47
  48 namespace std {
  49 template <>
  50 struct is_error_code_enum<llvm::sampleprof_error> : std::true_type {};
  51 }
  52
  53 namespace llvm {
  54
  55 namespace sampleprof {
  56
  57 static inline uint64_t SPMagic() {
  58   return uint64_t('S') << (64 - 8) | uint64_t('P') << (64 - 16) |
  59          uint64_t('R') << (64 - 24) | uint64_t('O') << (64 - 32) |
  60          uint64_t('F') << (64 - 40) | uint64_t('4') << (64 - 48) |
  61          uint64_t('2') << (64 - 56) | uint64_t(0xff);
  62 }
  63
  64 static inline uint64_t SPVersion() { return 101; }
  65
  66 /// Represents the relative location of an instruction.
  67 ///
  68 /// Instruction locations are specified by the line offset from the
  69 /// beginning of the function (marked by the line where the function
  70 /// header is) and the discriminator value within that line.
  71 ///
  72 /// The discriminator value is useful to distinguish instructions
  73 /// that are on the same line but belong to different basic blocks
  74 /// (e.g., the two post-increment instructions in "if (p) x++; else y++;").
  75 struct LineLocation {
  76   LineLocation(uint32_t L, uint32_t D) : LineOffset(L), Discriminator(D) {}
  77   uint32_t LineOffset;
  78   uint32_t Discriminator;
  79 };
  80
  81 /// Represents the relative location of a callsite.
  82 ///
  83 /// Callsite locations are specified by the line offset from the
  84 /// beginning of the function (marked by the line where the function
  85 /// head is), the discriminator value within that line, and the callee
  86 /// function name.
  87 struct CallsiteLocation : public LineLocation {
  88   CallsiteLocation(uint32_t L, uint32_t D, StringRef N)
  89       : LineLocation(L, D), CalleeName(N) {}
  90   StringRef CalleeName;
  91 };
  92
  93 } // End namespace sampleprof
  94
  95 template <> struct DenseMapInfo<sampleprof::LineLocation> {
  96   typedef DenseMapInfo<uint32_t> OffsetInfo;
  97   typedef DenseMapInfo<uint32_t> DiscriminatorInfo;
  98   static inline sampleprof::LineLocation getEmptyKey() {
  99     return sampleprof::LineLocation(OffsetInfo::getEmptyKey(),
 100                                     DiscriminatorInfo::getEmptyKey());
 101   }
 102   static inline sampleprof::LineLocation getTombstoneKey() {
 103     return sampleprof::LineLocation(OffsetInfo::getTombstoneKey(),
 104                                     DiscriminatorInfo::getTombstoneKey());
 105   }
 106   static inline unsigned getHashValue(sampleprof::LineLocation Val) {
 107     return DenseMapInfo<std::pair<uint32_t, uint32_t>>::getHashValue(
 108         std::pair<uint32_t, uint32_t>(Val.LineOffset, Val.Discriminator));
 109   }
 110   static inline bool isEqual(sampleprof::LineLocation LHS,
 111                              sampleprof::LineLocation RHS) {
 112     return LHS.LineOffset == RHS.LineOffset &&
 113            LHS.Discriminator == RHS.Discriminator;
 114   }
 115 };
 116
 117 template <> struct DenseMapInfo<sampleprof::CallsiteLocation> {
 118   typedef DenseMapInfo<uint32_t> OffsetInfo;
 119   typedef DenseMapInfo<uint32_t> DiscriminatorInfo;
 120   typedef DenseMapInfo<StringRef> CalleeNameInfo;
 121   static inline sampleprof::CallsiteLocation getEmptyKey() {
 122     return sampleprof::CallsiteLocation(OffsetInfo::getEmptyKey(),
 123                                         DiscriminatorInfo::getEmptyKey(), "");
 124   }
 125   static inline sampleprof::CallsiteLocation getTombstoneKey() {
 126     return sampleprof::CallsiteLocation(OffsetInfo::getTombstoneKey(),
 127                                         DiscriminatorInfo::getTombstoneKey(),
 128                                         "");
 129   }
 130   static inline unsigned getHashValue(sampleprof::CallsiteLocation Val) {
 131     return DenseMapInfo<std::pair<uint32_t, uint32_t>>::getHashValue(
 132         std::pair<uint32_t, uint32_t>(Val.LineOffset, Val.Discriminator));
 133   }
 134   static inline bool isEqual(sampleprof::CallsiteLocation LHS,
 135                              sampleprof::CallsiteLocation RHS) {
 136     return LHS.LineOffset == RHS.LineOffset &&
 137            LHS.Discriminator == RHS.Discriminator &&
 138            LHS.CalleeName.equals(RHS.CalleeName);
 139   }
 140 };
 141
 142 namespace sampleprof {
 143
 144 /// Representation of a single sample record.
 145 ///
 146 /// A sample record is represented by a positive integer value, which
 147 /// indicates how frequently was the associated line location executed.
 148 ///
 149 /// Additionally, if the associated location contains a function call,
 150 /// the record will hold a list of all the possible called targets. For
 151 /// direct calls, this will be the exact function being invoked. For
 152 /// indirect calls (function pointers, virtual table dispatch), this
 153 /// will be a list of one or more functions.
 154 class SampleRecord {
 155 public:
 156   typedef StringMap<uint64_t> CallTargetMap;
 157
 158   SampleRecord() : NumSamples(0), CallTargets() {}
 159
 160   /// Increment the number of samples for this record by \p S.
 161   ///
 162   /// Sample counts accumulate using saturating arithmetic, to avoid wrapping
 163   /// around unsigned integers.
 164   void addSamples(uint64_t S) {
 165     if (NumSamples <= std::numeric_limits<uint64_t>::max() - S)
 166       NumSamples += S;
 167     else
 168       NumSamples = std::numeric_limits<uint64_t>::max();
 169   }
 170
 171   /// Add called function \p F with samples \p S.
 172   ///
 173   /// Sample counts accumulate using saturating arithmetic, to avoid wrapping
 174   /// around unsigned integers.
 175   void addCalledTarget(StringRef F, uint64_t S) {
 176     uint64_t &TargetSamples = CallTargets[F];
 177     if (TargetSamples <= std::numeric_limits<uint64_t>::max() - S)
 178       TargetSamples += S;
 179     else
 180       TargetSamples = std::numeric_limits<uint64_t>::max();
 181   }
 182
 183   /// Return true if this sample record contains function calls.
 184   bool hasCalls() const { return CallTargets.size() > 0; }
 185
 186   uint64_t getSamples() const { return NumSamples; }
 187   const CallTargetMap &getCallTargets() const { return CallTargets; }
 188
 189   /// Merge the samples in \p Other into this record.
 190   void merge(const SampleRecord &Other) {
 191     addSamples(Other.getSamples());
 192     for (const auto &I : Other.getCallTargets())
 193       addCalledTarget(I.first(), I.second);
 194   }
 195
 196 private:
 197   uint64_t NumSamples;
 198   CallTargetMap CallTargets;
 199 };
 200
 201 typedef DenseMap<LineLocation, SampleRecord> BodySampleMap;
 202 class FunctionSamples;
 203 typedef DenseMap<CallsiteLocation, FunctionSamples> CallsiteSampleMap;
 204
 205 /// Representation of the samples collected for a function.
 206 ///
 207 /// This data structure contains all the collected samples for the body
 208 /// of a function. Each sample corresponds to a LineLocation instance
 209 /// within the body of the function.
 210 class FunctionSamples {
 211 public:
 212   FunctionSamples() : TotalSamples(0), TotalHeadSamples(0) {}
 213   void print(raw_ostream &OS = dbgs(), unsigned Indent = 0) const;
 214   void addTotalSamples(uint64_t Num) { TotalSamples += Num; }
 215   void addHeadSamples(uint64_t Num) { TotalHeadSamples += Num; }
 216   void addBodySamples(uint32_t LineOffset, uint32_t Discriminator,
 217                       uint64_t Num) {
 218     assert(LineOffset >= 0);
 219     BodySamples[LineLocation(LineOffset, Discriminator)].addSamples(Num);
 220   }
 221   void addCalledTargetSamples(uint32_t LineOffset, uint32_t Discriminator,
 222                               std::string FName, uint64_t Num) {
 223     assert(LineOffset >= 0);
 224     BodySamples[LineLocation(LineOffset, Discriminator)].addCalledTarget(FName,
 225                                                                          Num);
 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 NULL;
 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   void merge(const FunctionSamples &Other) {
 275     addTotalSamples(Other.getTotalSamples());
 276     addHeadSamples(Other.getHeadSamples());
 277     for (const auto &I : Other.getBodySamples()) {
 278       const LineLocation &Loc = I.first;
 279       const SampleRecord &Rec = I.second;
 280       BodySamples[Loc].merge(Rec);
 281     }
 282     for (const auto &I : Other.getCallsiteSamples()) {
 283       const CallsiteLocation &Loc = I.first;
 284       const FunctionSamples &Rec = I.second;
 285       functionSamplesAt(Loc).merge(Rec);
 286     }
 287   }
 288
 289 private:
 290   /// Total number of samples collected inside this function.
 291   ///
 292   /// Samples are cumulative, they include all the samples collected
 293   /// inside this function and all its inlined callees.
 294   uint64_t TotalSamples;
 295
 296   /// Total number of samples collected at the head of the function.
 297   /// This is an approximation of the number of calls made to this function
 298   /// at runtime.
 299   uint64_t TotalHeadSamples;
 300
 301   /// Map instruction locations to collected samples.
 302   ///
 303   /// Each entry in this map contains the number of samples
 304   /// collected at the corresponding line offset. All line locations
 305   /// are an offset from the start of the function.
 306   BodySampleMap BodySamples;
 307
 308   /// Map call sites to collected samples for the called function.
 309   ///
 310   /// Each entry in this map corresponds to all the samples
 311   /// collected for the inlined function call at the given
 312   /// location. For example, given:
 313   ///
 314   ///     void foo() {
 315   ///  1    bar();
 316   ///  ...
 317   ///  8    baz();
 318   ///     }
 319   ///
 320   /// If the bar() and baz() calls were inlined inside foo(), this
 321   /// map will contain two entries.  One for all the samples collected
 322   /// in the call to bar() at line offset 1, the other for all the samples
 323   /// collected in the call to baz() at line offset 8.
 324   CallsiteSampleMap CallsiteSamples;
 325 };
 326
 327 } // End namespace sampleprof
 328
 329 } // End namespace llvm
 330
 331 #endif // LLVM_PROFILEDATA_SAMPLEPROF_H_