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

   1 //===- SampleProf.h - Sampling profiling format support ---------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file contains common definitions used in the reading and writing of
  10 // sample profile data.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_PROFILEDATA_SAMPLEPROF_H
  15 #define LLVM_PROFILEDATA_SAMPLEPROF_H
  16
  17 #include "llvm/ADT/DenseSet.h"
  18 #include "llvm/ADT/SmallVector.h"
  19 #include "llvm/ADT/StringMap.h"
  20 #include "llvm/ADT/StringRef.h"
  21 #include "llvm/ADT/StringSet.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 "llvm/Support/raw_ostream.h"
  29 #include <algorithm>
  30 #include <cstdint>
  31 #include <map>
  32 #include <set>
  33 #include <string>
  34 #include <system_error>
  35 #include <utility>
  36
  37 namespace llvm {
  38
  39 class raw_ostream;
  40
  41 const std::error_category &sampleprof_category();
  42
  43 enum class sampleprof_error {
  44   success = 0,
  45   bad_magic,
  46   unsupported_version,
  47   too_large,
  48   truncated,
  49   malformed,
  50   unrecognized_format,
  51   unsupported_writing_format,
  52   truncated_name_table,
  53   not_implemented,
  54   counter_overflow,
  55   ostream_seek_unsupported,
  56   compress_failed,
  57   uncompress_failed,
  58   zlib_unavailable
  59 };
  60
  61 inline std::error_code make_error_code(sampleprof_error E) {
  62   return std::error_code(static_cast<int>(E), sampleprof_category());
  63 }
  64
  65 inline sampleprof_error MergeResult(sampleprof_error &Accumulator,
  66                                     sampleprof_error Result) {
  67   // Prefer first error encountered as later errors may be secondary effects of
  68   // the initial problem.
  69   if (Accumulator == sampleprof_error::success &&
  70       Result != sampleprof_error::success)
  71     Accumulator = Result;
  72   return Accumulator;
  73 }
  74
  75 } // end namespace llvm
  76
  77 namespace std {
  78
  79 template <>
  80 struct is_error_code_enum<llvm::sampleprof_error> : std::true_type {};
  81
  82 } // end namespace std
  83
  84 namespace llvm {
  85 namespace sampleprof {
  86
  87 enum SampleProfileFormat {
  88   SPF_None = 0,
  89   SPF_Text = 0x1,
  90   SPF_Compact_Binary = 0x2,
  91   SPF_GCC = 0x3,
  92   SPF_Ext_Binary = 0x4,
  93   SPF_Binary = 0xff
  94 };
  95
  96 static inline uint64_t SPMagic(SampleProfileFormat Format = SPF_Binary) {
  97   return uint64_t('S') << (64 - 8) | uint64_t('P') << (64 - 16) |
  98          uint64_t('R') << (64 - 24) | uint64_t('O') << (64 - 32) |
  99          uint64_t('F') << (64 - 40) | uint64_t('4') << (64 - 48) |
 100          uint64_t('2') << (64 - 56) | uint64_t(Format);
 101 }
 102
 103 // Get the proper representation of a string in the input Format.
 104 static inline StringRef getRepInFormat(StringRef Name,
 105                                        SampleProfileFormat Format,
 106                                        std::string &GUIDBuf) {
 107   if (Name.empty())
 108     return Name;
 109   GUIDBuf = std::to_string(Function::getGUID(Name));
 110   return (Format == SPF_Compact_Binary) ? StringRef(GUIDBuf) : Name;
 111 }
 112
 113 static inline uint64_t SPVersion() { return 103; }
 114
 115 // Section Type used by SampleProfileExtBinaryBaseReader and
 116 // SampleProfileExtBinaryBaseWriter. Never change the existing
 117 // value of enum. Only append new ones.
 118 enum SecType {
 119   SecInValid = 0,
 120   SecProfSummary = 1,
 121   SecNameTable = 2,
 122   SecProfileSymbolList = 3,
 123   SecFuncOffsetTable = 4,
 124   // marker for the first type of profile.
 125   SecFuncProfileFirst = 32,
 126   SecLBRProfile = SecFuncProfileFirst
 127 };
 128
 129 static inline std::string getSecName(SecType Type) {
 130   switch (Type) {
 131   case SecInValid:
 132     return "InvalidSection";
 133   case SecProfSummary:
 134     return "ProfileSummarySection";
 135   case SecNameTable:
 136     return "NameTableSection";
 137   case SecProfileSymbolList:
 138     return "ProfileSymbolListSection";
 139   case SecFuncOffsetTable:
 140     return "FuncOffsetTableSection";
 141   case SecLBRProfile:
 142     return "LBRProfileSection";
 143   }
 144   llvm_unreachable("A SecType has no name for output");
 145 }
 146
 147 // Entry type of section header table used by SampleProfileExtBinaryBaseReader
 148 // and SampleProfileExtBinaryBaseWriter.
 149 struct SecHdrTableEntry {
 150   SecType Type;
 151   uint64_t Flags;
 152   uint64_t Offset;
 153   uint64_t Size;
 154 };
 155
 156 enum SecFlags { SecFlagInValid = 0, SecFlagCompress = (1 << 0) };
 157
 158 static inline void addSecFlags(SecHdrTableEntry &Entry, uint64_t Flags) {
 159   Entry.Flags |= Flags;
 160 }
 161
 162 static inline void removeSecFlags(SecHdrTableEntry &Entry, uint64_t Flags) {
 163   Entry.Flags &= ~Flags;
 164 }
 165
 166 static inline bool hasSecFlag(SecHdrTableEntry &Entry, SecFlags Flag) {
 167   return Entry.Flags & Flag;
 168 }
 169
 170 /// Represents the relative location of an instruction.
 171 ///
 172 /// Instruction locations are specified by the line offset from the
 173 /// beginning of the function (marked by the line where the function
 174 /// header is) and the discriminator value within that line.
 175 ///
 176 /// The discriminator value is useful to distinguish instructions
 177 /// that are on the same line but belong to different basic blocks
 178 /// (e.g., the two post-increment instructions in "if (p) x++; else y++;").
 179 struct LineLocation {
 180   LineLocation(uint32_t L, uint32_t D) : LineOffset(L), Discriminator(D) {}
 181
 182   void print(raw_ostream &OS) const;
 183   void dump() const;
 184
 185   bool operator<(const LineLocation &O) const {
 186     return LineOffset < O.LineOffset ||
 187            (LineOffset == O.LineOffset && Discriminator < O.Discriminator);
 188   }
 189
 190   uint32_t LineOffset;
 191   uint32_t Discriminator;
 192 };
 193
 194 raw_ostream &operator<<(raw_ostream &OS, const LineLocation &Loc);
 195
 196 /// Representation of a single sample record.
 197 ///
 198 /// A sample record is represented by a positive integer value, which
 199 /// indicates how frequently was the associated line location executed.
 200 ///
 201 /// Additionally, if the associated location contains a function call,
 202 /// the record will hold a list of all the possible called targets. For
 203 /// direct calls, this will be the exact function being invoked. For
 204 /// indirect calls (function pointers, virtual table dispatch), this
 205 /// will be a list of one or more functions.
 206 class SampleRecord {
 207 public:
 208   using CallTarget = std::pair<StringRef, uint64_t>;
 209   struct CallTargetComparator {
 210     bool operator()(const CallTarget &LHS, const CallTarget &RHS) const {
 211       if (LHS.second != RHS.second)
 212         return LHS.second > RHS.second;
 213
 214       return LHS.first < RHS.first;
 215     }
 216   };
 217
 218   using SortedCallTargetSet = std::set<CallTarget, CallTargetComparator>;
 219   using CallTargetMap = StringMap<uint64_t>;
 220   SampleRecord() = default;
 221
 222   /// Increment the number of samples for this record by \p S.
 223   /// Optionally scale sample count \p S by \p Weight.
 224   ///
 225   /// Sample counts accumulate using saturating arithmetic, to avoid wrapping
 226   /// around unsigned integers.
 227   sampleprof_error addSamples(uint64_t S, uint64_t Weight = 1) {
 228     bool Overflowed;
 229     NumSamples = SaturatingMultiplyAdd(S, Weight, NumSamples, &Overflowed);
 230     return Overflowed ? sampleprof_error::counter_overflow
 231                       : sampleprof_error::success;
 232   }
 233
 234   /// Add called function \p F with samples \p S.
 235   /// Optionally scale sample count \p S by \p Weight.
 236   ///
 237   /// Sample counts accumulate using saturating arithmetic, to avoid wrapping
 238   /// around unsigned integers.
 239   sampleprof_error addCalledTarget(StringRef F, uint64_t S,
 240                                    uint64_t Weight = 1) {
 241     uint64_t &TargetSamples = CallTargets[F];
 242     bool Overflowed;
 243     TargetSamples =
 244         SaturatingMultiplyAdd(S, Weight, TargetSamples, &Overflowed);
 245     return Overflowed ? sampleprof_error::counter_overflow
 246                       : sampleprof_error::success;
 247   }
 248
 249   /// Return true if this sample record contains function calls.
 250   bool hasCalls() const { return !CallTargets.empty(); }
 251
 252   uint64_t getSamples() const { return NumSamples; }
 253   const CallTargetMap &getCallTargets() const { return CallTargets; }
 254   const SortedCallTargetSet getSortedCallTargets() const {
 255     return SortCallTargets(CallTargets);
 256   }
 257
 258   /// Sort call targets in descending order of call frequency.
 259   static const SortedCallTargetSet SortCallTargets(const CallTargetMap &Targets) {
 260     SortedCallTargetSet SortedTargets;
 261     for (const auto &I : Targets) {
 262       SortedTargets.emplace(I.first(), I.second);
 263     }
 264     return SortedTargets;
 265   }
 266
 267   /// Merge the samples in \p Other into this record.
 268   /// Optionally scale sample counts by \p Weight.
 269   sampleprof_error merge(const SampleRecord &Other, uint64_t Weight = 1) {
 270     sampleprof_error Result = addSamples(Other.getSamples(), Weight);
 271     for (const auto &I : Other.getCallTargets()) {
 272       MergeResult(Result, addCalledTarget(I.first(), I.second, Weight));
 273     }
 274     return Result;
 275   }
 276
 277   void print(raw_ostream &OS, unsigned Indent) const;
 278   void dump() const;
 279
 280 private:
 281   uint64_t NumSamples = 0;
 282   CallTargetMap CallTargets;
 283 };
 284
 285 raw_ostream &operator<<(raw_ostream &OS, const SampleRecord &Sample);
 286
 287 class FunctionSamples;
 288
 289 using BodySampleMap = std::map<LineLocation, SampleRecord>;
 290 // NOTE: Using a StringMap here makes parsed profiles consume around 17% more
 291 // memory, which is *very* significant for large profiles.
 292 using FunctionSamplesMap = std::map<std::string, FunctionSamples, std::less<>>;
 293 using CallsiteSampleMap = std::map<LineLocation, FunctionSamplesMap>;
 294
 295 /// Representation of the samples collected for a function.
 296 ///
 297 /// This data structure contains all the collected samples for the body
 298 /// of a function. Each sample corresponds to a LineLocation instance
 299 /// within the body of the function.
 300 class FunctionSamples {
 301 public:
 302   FunctionSamples() = default;
 303
 304   void print(raw_ostream &OS = dbgs(), unsigned Indent = 0) const;
 305   void dump() const;
 306
 307   sampleprof_error addTotalSamples(uint64_t Num, uint64_t Weight = 1) {
 308     bool Overflowed;
 309     TotalSamples =
 310         SaturatingMultiplyAdd(Num, Weight, TotalSamples, &Overflowed);
 311     return Overflowed ? sampleprof_error::counter_overflow
 312                       : sampleprof_error::success;
 313   }
 314
 315   sampleprof_error addHeadSamples(uint64_t Num, uint64_t Weight = 1) {
 316     bool Overflowed;
 317     TotalHeadSamples =
 318         SaturatingMultiplyAdd(Num, Weight, TotalHeadSamples, &Overflowed);
 319     return Overflowed ? sampleprof_error::counter_overflow
 320                       : sampleprof_error::success;
 321   }
 322
 323   sampleprof_error addBodySamples(uint32_t LineOffset, uint32_t Discriminator,
 324                                   uint64_t Num, uint64_t Weight = 1) {
 325     return BodySamples[LineLocation(LineOffset, Discriminator)].addSamples(
 326         Num, Weight);
 327   }
 328
 329   sampleprof_error addCalledTargetSamples(uint32_t LineOffset,
 330                                           uint32_t Discriminator,
 331                                           StringRef FName, uint64_t Num,
 332                                           uint64_t Weight = 1) {
 333     return BodySamples[LineLocation(LineOffset, Discriminator)].addCalledTarget(
 334         FName, Num, Weight);
 335   }
 336
 337   /// Return the number of samples collected at the given location.
 338   /// Each location is specified by \p LineOffset and \p Discriminator.
 339   /// If the location is not found in profile, return error.
 340   ErrorOr<uint64_t> findSamplesAt(uint32_t LineOffset,
 341                                   uint32_t Discriminator) const {
 342     const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator));
 343     if (ret == BodySamples.end())
 344       return std::error_code();
 345     else
 346       return ret->second.getSamples();
 347   }
 348
 349   /// Returns the call target map collected at a given location.
 350   /// Each location is specified by \p LineOffset and \p Discriminator.
 351   /// If the location is not found in profile, return error.
 352   ErrorOr<SampleRecord::CallTargetMap>
 353   findCallTargetMapAt(uint32_t LineOffset, uint32_t Discriminator) const {
 354     const auto &ret = BodySamples.find(LineLocation(LineOffset, Discriminator));
 355     if (ret == BodySamples.end())
 356       return std::error_code();
 357     return ret->second.getCallTargets();
 358   }
 359
 360   /// Return the function samples at the given callsite location.
 361   FunctionSamplesMap &functionSamplesAt(const LineLocation &Loc) {
 362     return CallsiteSamples[Loc];
 363   }
 364
 365   /// Returns the FunctionSamplesMap at the given \p Loc.
 366   const FunctionSamplesMap *
 367   findFunctionSamplesMapAt(const LineLocation &Loc) const {
 368     auto iter = CallsiteSamples.find(Loc);
 369     if (iter == CallsiteSamples.end())
 370       return nullptr;
 371     return &iter->second;
 372   }
 373
 374   /// Returns a pointer to FunctionSamples at the given callsite location \p Loc
 375   /// with callee \p CalleeName. If no callsite can be found, relax the
 376   /// restriction to return the FunctionSamples at callsite location \p Loc
 377   /// with the maximum total sample count.
 378   const FunctionSamples *findFunctionSamplesAt(const LineLocation &Loc,
 379                                                StringRef CalleeName) const {
 380     std::string CalleeGUID;
 381     CalleeName = getRepInFormat(CalleeName, Format, CalleeGUID);
 382
 383     auto iter = CallsiteSamples.find(Loc);
 384     if (iter == CallsiteSamples.end())
 385       return nullptr;
 386     auto FS = iter->second.find(CalleeName);
 387     if (FS != iter->second.end())
 388       return &FS->second;
 389     // If we cannot find exact match of the callee name, return the FS with
 390     // the max total count. Only do this when CalleeName is not provided,
 391     // i.e., only for indirect calls.
 392     if (!CalleeName.empty())
 393       return nullptr;
 394     uint64_t MaxTotalSamples = 0;
 395     const FunctionSamples *R = nullptr;
 396     for (const auto &NameFS : iter->second)
 397       if (NameFS.second.getTotalSamples() >= MaxTotalSamples) {
 398         MaxTotalSamples = NameFS.second.getTotalSamples();
 399         R = &NameFS.second;
 400       }
 401     return R;
 402   }
 403
 404   bool empty() const { return TotalSamples == 0; }
 405
 406   /// Return the total number of samples collected inside the function.
 407   uint64_t getTotalSamples() const { return TotalSamples; }
 408
 409   /// Return the total number of branch samples that have the function as the
 410   /// branch target. This should be equivalent to the sample of the first
 411   /// instruction of the symbol. But as we directly get this info for raw
 412   /// profile without referring to potentially inaccurate debug info, this
 413   /// gives more accurate profile data and is preferred for standalone symbols.
 414   uint64_t getHeadSamples() const { return TotalHeadSamples; }
 415
 416   /// Return the sample count of the first instruction of the function.
 417   /// The function can be either a standalone symbol or an inlined function.
 418   uint64_t getEntrySamples() const {
 419     // Use either BodySamples or CallsiteSamples which ever has the smaller
 420     // lineno.
 421     if (!BodySamples.empty() &&
 422         (CallsiteSamples.empty() ||
 423          BodySamples.begin()->first < CallsiteSamples.begin()->first))
 424       return BodySamples.begin()->second.getSamples();
 425     if (!CallsiteSamples.empty()) {
 426       uint64_t T = 0;
 427       // An indirect callsite may be promoted to several inlined direct calls.
 428       // We need to get the sum of them.
 429       for (const auto &N_FS : CallsiteSamples.begin()->second)
 430         T += N_FS.second.getEntrySamples();
 431       return T;
 432     }
 433     return 0;
 434   }
 435
 436   /// Return all the samples collected in the body of the function.
 437   const BodySampleMap &getBodySamples() const { return BodySamples; }
 438
 439   /// Return all the callsite samples collected in the body of the function.
 440   const CallsiteSampleMap &getCallsiteSamples() const {
 441     return CallsiteSamples;
 442   }
 443
 444   /// Merge the samples in \p Other into this one.
 445   /// Optionally scale samples by \p Weight.
 446   sampleprof_error merge(const FunctionSamples &Other, uint64_t Weight = 1) {
 447     sampleprof_error Result = sampleprof_error::success;
 448     Name = Other.getName();
 449     MergeResult(Result, addTotalSamples(Other.getTotalSamples(), Weight));
 450     MergeResult(Result, addHeadSamples(Other.getHeadSamples(), Weight));
 451     for (const auto &I : Other.getBodySamples()) {
 452       const LineLocation &Loc = I.first;
 453       const SampleRecord &Rec = I.second;
 454       MergeResult(Result, BodySamples[Loc].merge(Rec, Weight));
 455     }
 456     for (const auto &I : Other.getCallsiteSamples()) {
 457       const LineLocation &Loc = I.first;
 458       FunctionSamplesMap &FSMap = functionSamplesAt(Loc);
 459       for (const auto &Rec : I.second)
 460         MergeResult(Result, FSMap[Rec.first].merge(Rec.second, Weight));
 461     }
 462     return Result;
 463   }
 464
 465   /// Recursively traverses all children, if the total sample count of the
 466   /// corresponding function is no less than \p Threshold, add its corresponding
 467   /// GUID to \p S. Also traverse the BodySamples to add hot CallTarget's GUID
 468   /// to \p S.
 469   void findInlinedFunctions(DenseSet<GlobalValue::GUID> &S, const Module *M,
 470                             uint64_t Threshold) const {
 471     if (TotalSamples <= Threshold)
 472       return;
 473     S.insert(getGUID(Name));
 474     // Import hot CallTargets, which may not be available in IR because full
 475     // profile annotation cannot be done until backend compilation in ThinLTO.
 476     for (const auto &BS : BodySamples)
 477       for (const auto &TS : BS.second.getCallTargets())
 478         if (TS.getValue() > Threshold) {
 479           const Function *Callee =
 480               M->getFunction(getNameInModule(TS.getKey(), M));
 481           if (!Callee || !Callee->getSubprogram())
 482             S.insert(getGUID(TS.getKey()));
 483         }
 484     for (const auto &CS : CallsiteSamples)
 485       for (const auto &NameFS : CS.second)
 486         NameFS.second.findInlinedFunctions(S, M, Threshold);
 487   }
 488
 489   /// Set the name of the function.
 490   void setName(StringRef FunctionName) { Name = FunctionName; }
 491
 492   /// Return the function name.
 493   StringRef getName() const { return Name; }
 494
 495   /// Return the original function name if it exists in Module \p M.
 496   StringRef getFuncNameInModule(const Module *M) const {
 497     return getNameInModule(Name, M);
 498   }
 499
 500   /// Return the canonical name for a function, taking into account
 501   /// suffix elision policy attributes.
 502   static StringRef getCanonicalFnName(const Function &F) {
 503     static const char *knownSuffixes[] = { ".llvm.", ".part." };
 504     auto AttrName = "sample-profile-suffix-elision-policy";
 505     auto Attr = F.getFnAttribute(AttrName).getValueAsString();
 506     if (Attr == "" || Attr == "all") {
 507       return F.getName().split('.').first;
 508     } else if (Attr == "selected") {
 509       StringRef Cand(F.getName());
 510       for (const auto &Suf : knownSuffixes) {
 511         StringRef Suffix(Suf);
 512         auto It = Cand.rfind(Suffix);
 513         if (It == StringRef::npos)
 514           return Cand;
 515         auto Dit = Cand.rfind('.');
 516         if (Dit == It + Suffix.size() - 1)
 517           Cand = Cand.substr(0, It);
 518       }
 519       return Cand;
 520     } else if (Attr == "none") {
 521       return F.getName();
 522     } else {
 523       assert(false && "internal error: unknown suffix elision policy");
 524     }
 525     return F.getName();
 526   }
 527
 528   /// Translate \p Name into its original name in Module.
 529   /// When the Format is not SPF_Compact_Binary, \p Name needs no translation.
 530   /// When the Format is SPF_Compact_Binary, \p Name in current FunctionSamples
 531   /// is actually GUID of the original function name. getNameInModule will
 532   /// translate \p Name in current FunctionSamples into its original name.
 533   /// If the original name doesn't exist in \p M, return empty StringRef.
 534   StringRef getNameInModule(StringRef Name, const Module *M) const {
 535     if (Format != SPF_Compact_Binary)
 536       return Name;
 537
 538     assert(GUIDToFuncNameMap && "GUIDToFuncNameMap needs to be popluated first");
 539     auto iter = GUIDToFuncNameMap->find(std::stoull(Name.data()));
 540     if (iter == GUIDToFuncNameMap->end())
 541       return StringRef();
 542     return iter->second;
 543   }
 544
 545   /// Returns the line offset to the start line of the subprogram.
 546   /// We assume that a single function will not exceed 65535 LOC.
 547   static unsigned getOffset(const DILocation *DIL);
 548
 549   /// Get the FunctionSamples of the inline instance where DIL originates
 550   /// from.
 551   ///
 552   /// The FunctionSamples of the instruction (Machine or IR) associated to
 553   /// \p DIL is the inlined instance in which that instruction is coming from.
 554   /// We traverse the inline stack of that instruction, and match it with the
 555   /// tree nodes in the profile.
 556   ///
 557   /// \returns the FunctionSamples pointer to the inlined instance.
 558   const FunctionSamples *findFunctionSamples(const DILocation *DIL) const;
 559
 560   static SampleProfileFormat Format;
 561
 562   /// GUIDToFuncNameMap saves the mapping from GUID to the symbol name, for
 563   /// all the function symbols defined or declared in current module.
 564   DenseMap<uint64_t, StringRef> *GUIDToFuncNameMap = nullptr;
 565
 566   // Assume the input \p Name is a name coming from FunctionSamples itself.
 567   // If the format is SPF_Compact_Binary, the name is already a GUID and we
 568   // don't want to return the GUID of GUID.
 569   static uint64_t getGUID(StringRef Name) {
 570     return (Format == SPF_Compact_Binary) ? std::stoull(Name.data())
 571                                           : Function::getGUID(Name);
 572   }
 573
 574 private:
 575   /// Mangled name of the function.
 576   StringRef Name;
 577
 578   /// Total number of samples collected inside this function.
 579   ///
 580   /// Samples are cumulative, they include all the samples collected
 581   /// inside this function and all its inlined callees.
 582   uint64_t TotalSamples = 0;
 583
 584   /// Total number of samples collected at the head of the function.
 585   /// This is an approximation of the number of calls made to this function
 586   /// at runtime.
 587   uint64_t TotalHeadSamples = 0;
 588
 589   /// Map instruction locations to collected samples.
 590   ///
 591   /// Each entry in this map contains the number of samples
 592   /// collected at the corresponding line offset. All line locations
 593   /// are an offset from the start of the function.
 594   BodySampleMap BodySamples;
 595
 596   /// Map call sites to collected samples for the called function.
 597   ///
 598   /// Each entry in this map corresponds to all the samples
 599   /// collected for the inlined function call at the given
 600   /// location. For example, given:
 601   ///
 602   ///     void foo() {
 603   ///  1    bar();
 604   ///  ...
 605   ///  8    baz();
 606   ///     }
 607   ///
 608   /// If the bar() and baz() calls were inlined inside foo(), this
 609   /// map will contain two entries.  One for all the samples collected
 610   /// in the call to bar() at line offset 1, the other for all the samples
 611   /// collected in the call to baz() at line offset 8.
 612   CallsiteSampleMap CallsiteSamples;
 613 };
 614
 615 raw_ostream &operator<<(raw_ostream &OS, const FunctionSamples &FS);
 616
 617 /// Sort a LocationT->SampleT map by LocationT.
 618 ///
 619 /// It produces a sorted list of <LocationT, SampleT> records by ascending
 620 /// order of LocationT.
 621 template <class LocationT, class SampleT> class SampleSorter {
 622 public:
 623   using SamplesWithLoc = std::pair<const LocationT, SampleT>;
 624   using SamplesWithLocList = SmallVector<const SamplesWithLoc *, 20>;
 625
 626   SampleSorter(const std::map<LocationT, SampleT> &Samples) {
 627     for (const auto &I : Samples)
 628       V.push_back(&I);
 629     llvm::stable_sort(V, [](const SamplesWithLoc *A, const SamplesWithLoc *B) {
 630       return A->first < B->first;
 631     });
 632   }
 633
 634   const SamplesWithLocList &get() const { return V; }
 635
 636 private:
 637   SamplesWithLocList V;
 638 };
 639
 640 /// ProfileSymbolList records the list of function symbols shown up
 641 /// in the binary used to generate the profile. It is useful to
 642 /// to discriminate a function being so cold as not to shown up
 643 /// in the profile and a function newly added.
 644 class ProfileSymbolList {
 645 public:
 646   /// copy indicates whether we need to copy the underlying memory
 647   /// for the input Name.
 648   void add(StringRef Name, bool copy = false) {
 649     if (!copy) {
 650       Syms.insert(Name);
 651       return;
 652     }
 653     Syms.insert(Name.copy(Allocator));
 654   }
 655
 656   bool contains(StringRef Name) { return Syms.count(Name); }
 657
 658   void merge(const ProfileSymbolList &List) {
 659     for (auto Sym : List.Syms)
 660       add(Sym, true);
 661   }
 662
 663   unsigned size() { return Syms.size(); }
 664
 665   void setToCompress(bool TC) { ToCompress = TC; }
 666   bool toCompress() { return ToCompress; }
 667
 668   std::error_code read(const uint8_t *Data, uint64_t ListSize);
 669   std::error_code write(raw_ostream &OS);
 670   void dump(raw_ostream &OS = dbgs()) const;
 671
 672 private:
 673   // Determine whether or not to compress the symbol list when
 674   // writing it into profile. The variable is unused when the symbol
 675   // list is read from an existing profile.
 676   bool ToCompress = false;
 677   DenseSet<StringRef> Syms;
 678   BumpPtrAllocator Allocator;
 679 };
 680
 681 } // end namespace sampleprof
 682 } // end namespace llvm
 683
 684 #endif // LLVM_PROFILEDATA_SAMPLEPROF_H