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