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 enum SampleProfileFormat {
  82   SPF_None = 0,
  83   SPF_Text = 0x1,
  84   SPF_Compact_Binary = 0x2,
  85   SPF_GCC = 0x3,
  86   SPF_Binary = 0xff
  87 };
  88
  89 static inline uint64_t SPMagic(SampleProfileFormat Format = SPF_Binary) {
  90   return uint64_t('S') << (64 - 8) | uint64_t('P') << (64 - 16) |
  91          uint64_t('R') << (64 - 24) | uint64_t('O') << (64 - 32) |
  92          uint64_t('F') << (64 - 40) | uint64_t('4') << (64 - 48) |
  93          uint64_t('2') << (64 - 56) | uint64_t(Format);
  94 }
  95
  96 // Get the proper representation of a string in the input Format.
  97 static inline StringRef getRepInFormat(StringRef Name,
  98                                        SampleProfileFormat Format,
  99                                        std::string &GUIDBuf) {
 100   if (Name.empty())
 101     return Name;
 102   GUIDBuf = std::to_string(Function::getGUID(Name));
 103   return (Format == SPF_Compact_Binary) ? StringRef(GUIDBuf) : Name;
 104 }
 105
 106 static inline uint64_t SPVersion() { return 103; }
 107
 108 /// Represents the relative location of an instruction.
 109 ///
 110 /// Instruction locations are specified by the line offset from the
 111 /// beginning of the function (marked by the line where the function
 112 /// header is) and the discriminator value within that line.
 113 ///
 114 /// The discriminator value is useful to distinguish instructions
 115 /// that are on the same line but belong to different basic blocks
 116 /// (e.g., the two post-increment instructions in "if (p) x++; else y++;").
 117 struct LineLocation {
 118   LineLocation(uint32_t L, uint32_t D) : LineOffset(L), Discriminator(D) {}
 119
 120   void print(raw_ostream &OS) const;
 121   void dump() const;
 122
 123   bool operator<(const LineLocation &O) const {
 124     return LineOffset < O.LineOffset ||
 125            (LineOffset == O.LineOffset && Discriminator < O.Discriminator);
 126   }
 127
 128   uint32_t LineOffset;
 129   uint32_t Discriminator;
 130 };
 131
 132 raw_ostream &operator<<(raw_ostream &OS, const LineLocation &Loc);
 133
 134 /// Representation of a single sample record.
 135 ///
 136 /// A sample record is represented by a positive integer value, which
 137 /// indicates how frequently was the associated line location executed.
 138 ///
 139 /// Additionally, if the associated location contains a function call,
 140 /// the record will hold a list of all the possible called targets. For
 141 /// direct calls, this will be the exact function being invoked. For
 142 /// indirect calls (function pointers, virtual table dispatch), this
 143 /// will be a list of one or more functions.
 144 class SampleRecord {
 145 public:
 146   using CallTargetMap = StringMap<uint64_t>;
 147
 148   SampleRecord() = default;
 149
 150   /// Increment the number of samples for this record by \p S.
 151   /// Optionally scale sample count \p S by \p Weight.
 152   ///
 153   /// Sample counts accumulate using saturating arithmetic, to avoid wrapping
 154   /// around unsigned integers.
 155   sampleprof_error addSamples(uint64_t S, uint64_t Weight = 1) {
 156     bool Overflowed;
 157     NumSamples = SaturatingMultiplyAdd(S, Weight, NumSamples, &Overflowed);
 158     return Overflowed ? sampleprof_error::counter_overflow
 159                       : sampleprof_error::success;
 160   }
 161
 162   /// Add called function \p F with samples \p S.
 163   /// Optionally scale sample count \p S by \p Weight.
 164   ///
 165   /// Sample counts accumulate using saturating arithmetic, to avoid wrapping
 166   /// around unsigned integers.
 167   sampleprof_error addCalledTarget(StringRef F, uint64_t S,
 168                                    uint64_t Weight = 1) {
 169     uint64_t &TargetSamples = CallTargets[F];
 170     bool Overflowed;
 171     TargetSamples =
 172         SaturatingMultiplyAdd(S, Weight, TargetSamples, &Overflowed);
 173     return Overflowed ? sampleprof_error::counter_overflow
 174                       : sampleprof_error::success;
 175   }
 176
 177   /// Return true if this sample record contains function calls.
 178   bool hasCalls() const { return !CallTargets.empty(); }
 179
 180   uint64_t getSamples() const { return NumSamples; }
 181   const CallTargetMap &getCallTargets() const { return CallTargets; }
 182
 183   /// Merge the samples in \p Other into this record.
 184   /// Optionally scale sample counts by \p Weight.
 185   sampleprof_error merge(const SampleRecord &Other, uint64_t Weight = 1) {
 186     sampleprof_error Result = addSamples(Other.getSamples(), Weight);
 187     for (const auto &I : Other.getCallTargets()) {
 188       MergeResult(Result, addCalledTarget(I.first(), I.second, Weight));
 189     }
 190     return Result;
 191   }
 192
 193   void print(raw_ostream &OS, unsigned Indent) const;
 194   void dump() const;
 195
 196 private:
 197   uint64_t NumSamples = 0;
 198   CallTargetMap CallTargets;
 199 };
 200
 201 raw_ostream &operator<<(raw_ostream &OS, const SampleRecord &Sample);
 202
 203 class FunctionSamples;
 204
 205 using BodySampleMap = std::map<LineLocation, SampleRecord>;
 206 // NOTE: Using a StringMap here makes parsed profiles consume around 17% more
 207 // memory, which is *very* significant for large profiles.
 208 using FunctionSamplesMap = std::map<std::string, FunctionSamples>;
 209 using CallsiteSampleMap = std::map<LineLocation, FunctionSamplesMap>;
 210
 211 /// Representation of the samples collected for a function.
 212 ///
 213 /// This data structure contains all the collected samples for the body
 214 /// of a function. Each sample corresponds to a LineLocation instance
 215 /// within the body of the function.
 216 class FunctionSamples {
 217 public:
 218   FunctionSamples() = default;
 219
 220   void print(raw_ostream &OS = dbgs(), unsigned Indent = 0) const;
 221   void dump() const;
 222
 223   sampleprof_error addTotalSamples(uint64_t Num, uint64_t Weight = 1) {
 224     bool Overflowed;
 225     TotalSamples =
 226         SaturatingMultiplyAdd(Num, Weight, TotalSamples, &Overflowed);
 227     return Overflowed ? sampleprof_error::counter_overflow
 228                       : sampleprof_error::success;
 229   }
 230
 231   sampleprof_error addHeadSamples(uint64_t Num, uint64_t Weight = 1) {
 232     bool Overflowed;
 233     TotalHeadSamples =
 234         SaturatingMultiplyAdd(Num, Weight, TotalHeadSamples, &Overflowed);
 235     return Overflowed ? sampleprof_error::counter_overflow
 236                       : sampleprof_error::success;
 237   }
 238
 239   sampleprof_error addBodySamples(uint32_t LineOffset, uint32_t Discriminator,
 240                                   uint64_t Num, uint64_t Weight = 1) {
 241     return BodySamples[LineLocation(LineOffset, Discriminator)].addSamples(
 242         Num, Weight);
 243   }
 244
 245   sampleprof_error addCalledTargetSamples(uint32_t LineOffset,
 246                                           uint32_t Discriminator,
 247                                           StringRef FName, uint64_t Num,
 248                                           uint64_t Weight = 1) {
 249     return BodySamples[LineLocation(LineOffset, Discriminator)].addCalledTarget(
 250         FName, Num, Weight);
 251   }
 252
 253   /// Return the number of samples collected at the given location.
 254   /// Each location is specified by \p LineOffset and \p Discriminator.
 255   /// If the location is not found in profile, return error.
 256   ErrorOr<uint64_t> findSamplesAt(uint32_t LineOffset,
 257                                   uint32_t Discriminator) const {
 258     const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator));
 259     if (ret == BodySamples.end())
 260       return std::error_code();
 261     else
 262       return ret->second.getSamples();
 263   }
 264
 265   /// Returns the call target map collected at a given location.
 266   /// Each location is specified by \p LineOffset and \p Discriminator.
 267   /// If the location is not found in profile, return error.
 268   ErrorOr<SampleRecord::CallTargetMap>
 269   findCallTargetMapAt(uint32_t LineOffset, uint32_t Discriminator) const {
 270     const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator));
 271     if (ret == BodySamples.end())
 272       return std::error_code();
 273     return ret->second.getCallTargets();
 274   }
 275
 276   /// Return the function samples at the given callsite location.
 277   FunctionSamplesMap &functionSamplesAt(const LineLocation &Loc) {
 278     return CallsiteSamples[Loc];
 279   }
 280
 281   /// Returns the FunctionSamplesMap at the given \p Loc.
 282   const FunctionSamplesMap *
 283   findFunctionSamplesMapAt(const LineLocation &Loc) const {
 284     auto iter = CallsiteSamples.find(Loc);
 285     if (iter == CallsiteSamples.end())
 286       return nullptr;
 287     return &iter->second;
 288   }
 289
 290   /// Returns a pointer to FunctionSamples at the given callsite location \p Loc
 291   /// with callee \p CalleeName. If no callsite can be found, relax the
 292   /// restriction to return the FunctionSamples at callsite location \p Loc
 293   /// with the maximum total sample count.
 294   const FunctionSamples *findFunctionSamplesAt(const LineLocation &Loc,
 295                                                StringRef CalleeName) const {
 296     auto iter = CallsiteSamples.find(Loc);
 297     if (iter == CallsiteSamples.end())
 298       return nullptr;
 299     auto FS = iter->second.find(CalleeName);
 300     if (FS != iter->second.end())
 301       return &FS->second;
 302     // If we cannot find exact match of the callee name, return the FS with
 303     // the max total count.
 304     uint64_t MaxTotalSamples = 0;
 305     const FunctionSamples *R = nullptr;
 306     for (const auto &NameFS : iter->second)
 307       if (NameFS.second.getTotalSamples() >= MaxTotalSamples) {
 308         MaxTotalSamples = NameFS.second.getTotalSamples();
 309         R = &NameFS.second;
 310       }
 311     return R;
 312   }
 313
 314   bool empty() const { return TotalSamples == 0; }
 315
 316   /// Return the total number of samples collected inside the function.
 317   uint64_t getTotalSamples() const { return TotalSamples; }
 318
 319   /// Return the total number of branch samples that have the function as the
 320   /// branch target. This should be equivalent to the sample of the first
 321   /// instruction of the symbol. But as we directly get this info for raw
 322   /// profile without referring to potentially inaccurate debug info, this
 323   /// gives more accurate profile data and is preferred for standalone symbols.
 324   uint64_t getHeadSamples() const { return TotalHeadSamples; }
 325
 326   /// Return the sample count of the first instruction of the function.
 327   /// The function can be either a standalone symbol or an inlined function.
 328   uint64_t getEntrySamples() const {
 329     // Use either BodySamples or CallsiteSamples which ever has the smaller
 330     // lineno.
 331     if (!BodySamples.empty() &&
 332         (CallsiteSamples.empty() ||
 333          BodySamples.begin()->first < CallsiteSamples.begin()->first))
 334       return BodySamples.begin()->second.getSamples();
 335     if (!CallsiteSamples.empty()) {
 336       uint64_t T = 0;
 337       // An indirect callsite may be promoted to several inlined direct calls.
 338       // We need to get the sum of them.
 339       for (const auto &N_FS : CallsiteSamples.begin()->second)
 340         T += N_FS.second.getEntrySamples();
 341       return T;
 342     }
 343     return 0;
 344   }
 345
 346   /// Return all the samples collected in the body of the function.
 347   const BodySampleMap &getBodySamples() const { return BodySamples; }
 348
 349   /// Return all the callsite samples collected in the body of the function.
 350   const CallsiteSampleMap &getCallsiteSamples() const {
 351     return CallsiteSamples;
 352   }
 353
 354   /// Merge the samples in \p Other into this one.
 355   /// Optionally scale samples by \p Weight.
 356   sampleprof_error merge(const FunctionSamples &Other, uint64_t Weight = 1) {
 357     sampleprof_error Result = sampleprof_error::success;
 358     Name = Other.getName();
 359     MergeResult(Result, addTotalSamples(Other.getTotalSamples(), Weight));
 360     MergeResult(Result, addHeadSamples(Other.getHeadSamples(), Weight));
 361     for (const auto &I : Other.getBodySamples()) {
 362       const LineLocation &Loc = I.first;
 363       const SampleRecord &Rec = I.second;
 364       MergeResult(Result, BodySamples[Loc].merge(Rec, Weight));
 365     }
 366     for (const auto &I : Other.getCallsiteSamples()) {
 367       const LineLocation &Loc = I.first;
 368       FunctionSamplesMap &FSMap = functionSamplesAt(Loc);
 369       for (const auto &Rec : I.second)
 370         MergeResult(Result, FSMap[Rec.first].merge(Rec.second, Weight));
 371     }
 372     return Result;
 373   }
 374
 375   /// Recursively traverses all children, if the total sample count of the
 376   /// corresponding function is no less than \p Threshold, add its corresponding
 377   /// GUID to \p S. Also traverse the BodySamples to add hot CallTarget's GUID
 378   /// to \p S.
 379   void findInlinedFunctions(DenseSet<GlobalValue::GUID> &S, const Module *M,
 380                             uint64_t Threshold, bool isCompact) const {
 381     if (TotalSamples <= Threshold)
 382       return;
 383     S.insert(Function::getGUID(Name));
 384     // Import hot CallTargets, which may not be available in IR because full
 385     // profile annotation cannot be done until backend compilation in ThinLTO.
 386     for (const auto &BS : BodySamples)
 387       for (const auto &TS : BS.second.getCallTargets())
 388         if (TS.getValue() > Threshold) {
 389           Function *Callee = M->getFunction(TS.getKey());
 390           if (!Callee || !Callee->getSubprogram())
 391             S.insert(isCompact ? std::stol(TS.getKey().data())
 392                                : Function::getGUID(TS.getKey()));
 393         }
 394     for (const auto &CS : CallsiteSamples)
 395       for (const auto &NameFS : CS.second)
 396         NameFS.second.findInlinedFunctions(S, M, Threshold, isCompact);
 397   }
 398
 399   /// Set the name of the function.
 400   void setName(StringRef FunctionName) { Name = FunctionName; }
 401
 402   /// Return the function name.
 403   const StringRef &getName() const { return Name; }
 404
 405   /// Returns the line offset to the start line of the subprogram.
 406   /// We assume that a single function will not exceed 65535 LOC.
 407   static unsigned getOffset(const DILocation *DIL);
 408
 409   /// Get the FunctionSamples of the inline instance where DIL originates
 410   /// from.
 411   ///
 412   /// The FunctionSamples of the instruction (Machine or IR) associated to
 413   /// \p DIL is the inlined instance in which that instruction is coming from.
 414   /// We traverse the inline stack of that instruction, and match it with the
 415   /// tree nodes in the profile.
 416   ///
 417   /// \returns the FunctionSamples pointer to the inlined instance.
 418   const FunctionSamples *findFunctionSamples(const DILocation *DIL) const;
 419
 420 private:
 421   /// Mangled name of the function.
 422   StringRef Name;
 423
 424   /// Total number of samples collected inside this function.
 425   ///
 426   /// Samples are cumulative, they include all the samples collected
 427   /// inside this function and all its inlined callees.
 428   uint64_t TotalSamples = 0;
 429
 430   /// Total number of samples collected at the head of the function.
 431   /// This is an approximation of the number of calls made to this function
 432   /// at runtime.
 433   uint64_t TotalHeadSamples = 0;
 434
 435   /// Map instruction locations to collected samples.
 436   ///
 437   /// Each entry in this map contains the number of samples
 438   /// collected at the corresponding line offset. All line locations
 439   /// are an offset from the start of the function.
 440   BodySampleMap BodySamples;
 441
 442   /// Map call sites to collected samples for the called function.
 443   ///
 444   /// Each entry in this map corresponds to all the samples
 445   /// collected for the inlined function call at the given
 446   /// location. For example, given:
 447   ///
 448   ///     void foo() {
 449   ///  1    bar();
 450   ///  ...
 451   ///  8    baz();
 452   ///     }
 453   ///
 454   /// If the bar() and baz() calls were inlined inside foo(), this
 455   /// map will contain two entries.  One for all the samples collected
 456   /// in the call to bar() at line offset 1, the other for all the samples
 457   /// collected in the call to baz() at line offset 8.
 458   CallsiteSampleMap CallsiteSamples;
 459 };
 460
 461 raw_ostream &operator<<(raw_ostream &OS, const FunctionSamples &FS);
 462
 463 /// Sort a LocationT->SampleT map by LocationT.
 464 ///
 465 /// It produces a sorted list of <LocationT, SampleT> records by ascending
 466 /// order of LocationT.
 467 template <class LocationT, class SampleT> class SampleSorter {
 468 public:
 469   using SamplesWithLoc = std::pair<const LocationT, SampleT>;
 470   using SamplesWithLocList = SmallVector<const SamplesWithLoc *, 20>;
 471
 472   SampleSorter(const std::map<LocationT, SampleT> &Samples) {
 473     for (const auto &I : Samples)
 474       V.push_back(&I);
 475     std::stable_sort(V.begin(), V.end(),
 476                      [](const SamplesWithLoc *A, const SamplesWithLoc *B) {
 477                        return A->first < B->first;
 478                      });
 479   }
 480
 481   const SamplesWithLocList &get() const { return V; }
 482
 483 private:
 484   SamplesWithLocList V;
 485 };
 486
 487 } // end namespace sampleprof
 488 } // end namespace llvm
 489
 490 #endif // LLVM_PROFILEDATA_SAMPLEPROF_H