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 } // End namespace sampleprof
  80
  81 template <> struct DenseMapInfo<sampleprof::LineLocation> {
  82   typedef DenseMapInfo<int> OffsetInfo;
  83   typedef DenseMapInfo<unsigned> DiscriminatorInfo;
  84   static inline sampleprof::LineLocation getEmptyKey() {
  85     return sampleprof::LineLocation(OffsetInfo::getEmptyKey(),
  86                                     DiscriminatorInfo::getEmptyKey());
  87   }
  88   static inline sampleprof::LineLocation getTombstoneKey() {
  89     return sampleprof::LineLocation(OffsetInfo::getTombstoneKey(),
  90                                     DiscriminatorInfo::getTombstoneKey());
  91   }
  92   static inline unsigned getHashValue(sampleprof::LineLocation Val) {
  93     return DenseMapInfo<std::pair<int, unsigned>>::getHashValue(
  94         std::pair<int, unsigned>(Val.LineOffset, Val.Discriminator));
  95   }
  96   static inline bool isEqual(sampleprof::LineLocation LHS,
  97                              sampleprof::LineLocation RHS) {
  98     return LHS.LineOffset == RHS.LineOffset &&
  99            LHS.Discriminator == RHS.Discriminator;
 100   }
 101 };
 102
 103 namespace sampleprof {
 104
 105 /// Representation of a single sample record.
 106 ///
 107 /// A sample record is represented by a positive integer value, which
 108 /// indicates how frequently was the associated line location executed.
 109 ///
 110 /// Additionally, if the associated location contains a function call,
 111 /// the record will hold a list of all the possible called targets. For
 112 /// direct calls, this will be the exact function being invoked. For
 113 /// indirect calls (function pointers, virtual table dispatch), this
 114 /// will be a list of one or more functions.
 115 class SampleRecord {
 116 public:
 117   typedef StringMap<unsigned> CallTargetMap;
 118
 119   SampleRecord() : NumSamples(0), CallTargets() {}
 120
 121   /// Increment the number of samples for this record by \p S.
 122   ///
 123   /// Sample counts accumulate using saturating arithmetic, to avoid wrapping
 124   /// around unsigned integers.
 125   void addSamples(unsigned S) {
 126     if (NumSamples <= std::numeric_limits<unsigned>::max() - S)
 127       NumSamples += S;
 128     else
 129       NumSamples = std::numeric_limits<unsigned>::max();
 130   }
 131
 132   /// Add called function \p F with samples \p S.
 133   ///
 134   /// Sample counts accumulate using saturating arithmetic, to avoid wrapping
 135   /// around unsigned integers.
 136   void addCalledTarget(StringRef F, unsigned S) {
 137     unsigned &TargetSamples = CallTargets[F];
 138     if (TargetSamples <= std::numeric_limits<unsigned>::max() - S)
 139       TargetSamples += S;
 140     else
 141       TargetSamples = std::numeric_limits<unsigned>::max();
 142   }
 143
 144   /// Return true if this sample record contains function calls.
 145   bool hasCalls() const { return CallTargets.size() > 0; }
 146
 147   unsigned getSamples() const { return NumSamples; }
 148   const CallTargetMap &getCallTargets() const { return CallTargets; }
 149
 150   /// Merge the samples in \p Other into this record.
 151   void merge(const SampleRecord &Other) {
 152     addSamples(Other.getSamples());
 153     for (const auto &I : Other.getCallTargets())
 154       addCalledTarget(I.first(), I.second);
 155   }
 156
 157 private:
 158   unsigned NumSamples;
 159   CallTargetMap CallTargets;
 160 };
 161
 162 typedef DenseMap<LineLocation, SampleRecord> BodySampleMap;
 163
 164 /// Representation of the samples collected for a function.
 165 ///
 166 /// This data structure contains all the collected samples for the body
 167 /// of a function. Each sample corresponds to a LineLocation instance
 168 /// within the body of the function.
 169 class FunctionSamples {
 170 public:
 171   FunctionSamples() : TotalSamples(0), TotalHeadSamples(0) {}
 172   void print(raw_ostream &OS = dbgs());
 173   void addTotalSamples(unsigned Num) { TotalSamples += Num; }
 174   void addHeadSamples(unsigned Num) { TotalHeadSamples += Num; }
 175   void addBodySamples(int LineOffset, unsigned Discriminator, unsigned Num) {
 176     assert(LineOffset >= 0);
 177     // When dealing with instruction weights, we use the value
 178     // zero to indicate the absence of a sample. If we read an
 179     // actual zero from the profile file, use the value 1 to
 180     // avoid the confusion later on.
 181     if (Num == 0)
 182       Num = 1;
 183     BodySamples[LineLocation(LineOffset, Discriminator)].addSamples(Num);
 184   }
 185   void addCalledTargetSamples(int LineOffset, unsigned Discriminator,
 186                               std::string FName, unsigned Num) {
 187     assert(LineOffset >= 0);
 188     BodySamples[LineLocation(LineOffset, Discriminator)].addCalledTarget(FName,
 189                                                                          Num);
 190   }
 191
 192   /// Return the number of samples collected at the given location.
 193   /// Each location is specified by \p LineOffset and \p Discriminator.
 194   /// If the location is not found in profile, return error.
 195   ErrorOr<unsigned> findSamplesAt(int LineOffset,
 196                                   unsigned Discriminator) const {
 197     const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator));
 198     if (ret == BodySamples.end())
 199       return std::error_code();
 200     else
 201       return ret->second.getSamples();
 202   }
 203
 204   bool empty() const { return BodySamples.empty(); }
 205
 206   /// Return the total number of samples collected inside the function.
 207   unsigned getTotalSamples() const { return TotalSamples; }
 208
 209   /// Return the total number of samples collected at the head of the
 210   /// function.
 211   unsigned getHeadSamples() const { return TotalHeadSamples; }
 212
 213   /// Return all the samples collected in the body of the function.
 214   const BodySampleMap &getBodySamples() const { return BodySamples; }
 215
 216   /// Merge the samples in \p Other into this one.
 217   void merge(const FunctionSamples &Other) {
 218     addTotalSamples(Other.getTotalSamples());
 219     addHeadSamples(Other.getHeadSamples());
 220     for (const auto &I : Other.getBodySamples()) {
 221       const LineLocation &Loc = I.first;
 222       const SampleRecord &Rec = I.second;
 223       BodySamples[Loc].merge(Rec);
 224     }
 225   }
 226
 227 private:
 228   /// Total number of samples collected inside this function.
 229   ///
 230   /// Samples are cumulative, they include all the samples collected
 231   /// inside this function and all its inlined callees.
 232   unsigned TotalSamples;
 233
 234   /// Total number of samples collected at the head of the function.
 235   /// This is an approximation of the number of calls made to this function
 236   /// at runtime.
 237   unsigned TotalHeadSamples;
 238
 239   /// Map instruction locations to collected samples.
 240   ///
 241   /// Each entry in this map contains the number of samples
 242   /// collected at the corresponding line offset. All line locations
 243   /// are an offset from the start of the function.
 244   BodySampleMap BodySamples;
 245 };
 246
 247 } // End namespace sampleprof
 248
 249 } // End namespace llvm
 250
 251 #endif // LLVM_PROFILEDATA_SAMPLEPROF_H_