contrib/llvm/include/llvm/ProfileData/SampleProf.h

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