contrib/llvm/include/llvm/ProfileData/InstrProf.h

   1 //===- InstrProf.h - Instrumented 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 // Instrumentation-based profiling data is generated by instrumented
  11 // binaries through library functions in compiler-rt, and read by the clang
  12 // frontend to feed PGO.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_PROFILEDATA_INSTRPROF_H
  17 #define LLVM_PROFILEDATA_INSTRPROF_H
  18
  19 #include "llvm/ADT/ArrayRef.h"
  20 #include "llvm/ADT/STLExtras.h"
  21 #include "llvm/ADT/StringRef.h"
  22 #include "llvm/ADT/StringSet.h"
  23 #include "llvm/ADT/Triple.h"
  24 #include "llvm/IR/GlobalValue.h"
  25 #include "llvm/IR/ProfileSummary.h"
  26 #include "llvm/ProfileData/InstrProfData.inc"
  27 #include "llvm/Support/Compiler.h"
  28 #include "llvm/Support/Endian.h"
  29 #include "llvm/Support/Error.h"
  30 #include "llvm/Support/ErrorHandling.h"
  31 #include "llvm/Support/Host.h"
  32 #include "llvm/Support/MD5.h"
  33 #include "llvm/Support/MathExtras.h"
  34 #include "llvm/Support/raw_ostream.h"
  35 #include <algorithm>
  36 #include <cassert>
  37 #include <cstddef>
  38 #include <cstdint>
  39 #include <cstring>
  40 #include <list>
  41 #include <memory>
  42 #include <string>
  43 #include <system_error>
  44 #include <utility>
  45 #include <vector>
  46
  47 namespace llvm {
  48
  49 class Function;
  50 class GlobalVariable;
  51 struct InstrProfRecord;
  52 class InstrProfSymtab;
  53 class Instruction;
  54 class MDNode;
  55 class Module;
  56
  57 enum InstrProfSectKind {
  58 #define INSTR_PROF_SECT_ENTRY(Kind, SectNameCommon, SectNameCoff, Prefix) Kind,
  59 #include "llvm/ProfileData/InstrProfData.inc"
  60 };
  61
  62 /// Return the name of the profile section corresponding to \p IPSK.
  63 ///
  64 /// The name of the section depends on the object format type \p OF. If
  65 /// \p AddSegmentInfo is true, a segment prefix and additional linker hints may
  66 /// be added to the section name (this is the default).
  67 std::string getInstrProfSectionName(InstrProfSectKind IPSK,
  68                                     Triple::ObjectFormatType OF,
  69                                     bool AddSegmentInfo = true);
  70
  71 /// Return the name profile runtime entry point to do value profiling
  72 /// for a given site.
  73 inline StringRef getInstrProfValueProfFuncName() {
  74   return INSTR_PROF_VALUE_PROF_FUNC_STR;
  75 }
  76
  77 /// Return the name profile runtime entry point to do value range profiling.
  78 inline StringRef getInstrProfValueRangeProfFuncName() {
  79   return INSTR_PROF_VALUE_RANGE_PROF_FUNC_STR;
  80 }
  81
  82 /// Return the name of the section containing function coverage mapping
  83 /// data.
  84 std::string getInstrProfCoverageSectionName(const Module *M = nullptr);
  85 /// Similar to the above, but used by host tool (e.g, coverage) which has
  86 /// object format information. The section name returned is not prefixed
  87 /// with segment name.
  88 std::string getInstrProfCoverageSectionNameInObject(bool isCoff);
  89
  90 /// Return the name prefix of variables containing instrumented function names.
  91 inline StringRef getInstrProfNameVarPrefix() { return "__profn_"; }
  92
  93 /// Return the name prefix of variables containing per-function control data.
  94 inline StringRef getInstrProfDataVarPrefix() { return "__profd_"; }
  95
  96 /// Return the name prefix of profile counter variables.
  97 inline StringRef getInstrProfCountersVarPrefix() { return "__profc_"; }
  98
  99 /// Return the name prefix of value profile variables.
 100 inline StringRef getInstrProfValuesVarPrefix() { return "__profvp_"; }
 101
 102 /// Return the name of value profile node array variables:
 103 inline StringRef getInstrProfVNodesVarName() { return "__llvm_prf_vnodes"; }
 104
 105 /// Return the name prefix of the COMDAT group for instrumentation variables
 106 /// associated with a COMDAT function.
 107 inline StringRef getInstrProfComdatPrefix() { return "__profv_"; }
 108
 109 /// Return the name of the variable holding the strings (possibly compressed)
 110 /// of all function's PGO names.
 111 inline StringRef getInstrProfNamesVarName() {
 112   return "__llvm_prf_nm";
 113 }
 114
 115 /// Return the name of a covarage mapping variable (internal linkage)
 116 /// for each instrumented source module. Such variables are allocated
 117 /// in the __llvm_covmap section.
 118 inline StringRef getCoverageMappingVarName() {
 119   return "__llvm_coverage_mapping";
 120 }
 121
 122 /// Return the name of the internal variable recording the array
 123 /// of PGO name vars referenced by the coverage mapping. The owning
 124 /// functions of those names are not emitted by FE (e.g, unused inline
 125 /// functions.)
 126 inline StringRef getCoverageUnusedNamesVarName() {
 127   return "__llvm_coverage_names";
 128 }
 129
 130 /// Return the name of function that registers all the per-function control
 131 /// data at program startup time by calling __llvm_register_function. This
 132 /// function has internal linkage and is called by  __llvm_profile_init
 133 /// runtime method. This function is not generated for these platforms:
 134 /// Darwin, Linux, and FreeBSD.
 135 inline StringRef getInstrProfRegFuncsName() {
 136   return "__llvm_profile_register_functions";
 137 }
 138
 139 /// Return the name of the runtime interface that registers per-function control
 140 /// data for one instrumented function.
 141 inline StringRef getInstrProfRegFuncName() {
 142   return "__llvm_profile_register_function";
 143 }
 144
 145 /// Return the name of the runtime interface that registers the PGO name strings.
 146 inline StringRef getInstrProfNamesRegFuncName() {
 147   return "__llvm_profile_register_names_function";
 148 }
 149
 150 /// Return the name of the runtime initialization method that is generated by
 151 /// the compiler. The function calls __llvm_profile_register_functions and
 152 /// __llvm_profile_override_default_filename functions if needed. This function
 153 /// has internal linkage and invoked at startup time via init_array.
 154 inline StringRef getInstrProfInitFuncName() { return "__llvm_profile_init"; }
 155
 156 /// Return the name of the hook variable defined in profile runtime library.
 157 /// A reference to the variable causes the linker to link in the runtime
 158 /// initialization module (which defines the hook variable).
 159 inline StringRef getInstrProfRuntimeHookVarName() {
 160   return INSTR_PROF_QUOTE(INSTR_PROF_PROFILE_RUNTIME_VAR);
 161 }
 162
 163 /// Return the name of the compiler generated function that references the
 164 /// runtime hook variable. The function is a weak global.
 165 inline StringRef getInstrProfRuntimeHookVarUseFuncName() {
 166   return "__llvm_profile_runtime_user";
 167 }
 168
 169 /// Return the marker used to separate PGO names during serialization.
 170 inline StringRef getInstrProfNameSeparator() { return "\01"; }
 171
 172 /// Return the modified name for function \c F suitable to be
 173 /// used the key for profile lookup. Variable \c InLTO indicates if this
 174 /// is called in LTO optimization passes.
 175 std::string getPGOFuncName(const Function &F, bool InLTO = false,
 176                            uint64_t Version = INSTR_PROF_INDEX_VERSION);
 177
 178 /// Return the modified name for a function suitable to be
 179 /// used the key for profile lookup. The function's original
 180 /// name is \c RawFuncName and has linkage of type \c Linkage.
 181 /// The function is defined in module \c FileName.
 182 std::string getPGOFuncName(StringRef RawFuncName,
 183                            GlobalValue::LinkageTypes Linkage,
 184                            StringRef FileName,
 185                            uint64_t Version = INSTR_PROF_INDEX_VERSION);
 186
 187 /// Return the name of the global variable used to store a function
 188 /// name in PGO instrumentation. \c FuncName is the name of the function
 189 /// returned by the \c getPGOFuncName call.
 190 std::string getPGOFuncNameVarName(StringRef FuncName,
 191                                   GlobalValue::LinkageTypes Linkage);
 192
 193 /// Create and return the global variable for function name used in PGO
 194 /// instrumentation. \c FuncName is the name of the function returned
 195 /// by \c getPGOFuncName call.
 196 GlobalVariable *createPGOFuncNameVar(Function &F, StringRef PGOFuncName);
 197
 198 /// Create and return the global variable for function name used in PGO
 199 /// instrumentation.  /// \c FuncName is the name of the function
 200 /// returned by \c getPGOFuncName call, \c M is the owning module,
 201 /// and \c Linkage is the linkage of the instrumented function.
 202 GlobalVariable *createPGOFuncNameVar(Module &M,
 203                                      GlobalValue::LinkageTypes Linkage,
 204                                      StringRef PGOFuncName);
 205
 206 /// Return the initializer in string of the PGO name var \c NameVar.
 207 StringRef getPGOFuncNameVarInitializer(GlobalVariable *NameVar);
 208
 209 /// Given a PGO function name, remove the filename prefix and return
 210 /// the original (static) function name.
 211 StringRef getFuncNameWithoutPrefix(StringRef PGOFuncName,
 212                                    StringRef FileName = "<unknown>");
 213
 214 /// Given a vector of strings (function PGO names) \c NameStrs, the
 215 /// method generates a combined string \c Result thatis ready to be
 216 /// serialized.  The \c Result string is comprised of three fields:
 217 /// The first field is the legnth of the uncompressed strings, and the
 218 /// the second field is the length of the zlib-compressed string.
 219 /// Both fields are encoded in ULEB128.  If \c doCompress is false, the
 220 ///  third field is the uncompressed strings; otherwise it is the
 221 /// compressed string. When the string compression is off, the
 222 /// second field will have value zero.
 223 Error collectPGOFuncNameStrings(const std::vector<std::string> &NameStrs,
 224                                 bool doCompression, std::string &Result);
 225
 226 /// Produce \c Result string with the same format described above. The input
 227 /// is vector of PGO function name variables that are referenced.
 228 Error collectPGOFuncNameStrings(const std::vector<GlobalVariable *> &NameVars,
 229                                 std::string &Result, bool doCompression = true);
 230
 231 /// \c NameStrings is a string composed of one of more sub-strings encoded in
 232 /// the format described above. The substrings are separated by 0 or more zero
 233 /// bytes. This method decodes the string and populates the \c Symtab.
 234 Error readPGOFuncNameStrings(StringRef NameStrings, InstrProfSymtab &Symtab);
 235
 236 /// Check if INSTR_PROF_RAW_VERSION_VAR is defined. This global is only being
 237 /// set in IR PGO compilation.
 238 bool isIRPGOFlagSet(const Module *M);
 239
 240 /// Check if we can safely rename this Comdat function. Instances of the same
 241 /// comdat function may have different control flows thus can not share the
 242 /// same counter variable.
 243 bool canRenameComdatFunc(const Function &F, bool CheckAddressTaken = false);
 244
 245 enum InstrProfValueKind : uint32_t {
 246 #define VALUE_PROF_KIND(Enumerator, Value) Enumerator = Value,
 247 #include "llvm/ProfileData/InstrProfData.inc"
 248 };
 249
 250 /// Get the value profile data for value site \p SiteIdx from \p InstrProfR
 251 /// and annotate the instruction \p Inst with the value profile meta data.
 252 /// Annotate up to \p MaxMDCount (default 3) number of records per value site.
 253 void annotateValueSite(Module &M, Instruction &Inst,
 254                        const InstrProfRecord &InstrProfR,
 255                        InstrProfValueKind ValueKind, uint32_t SiteIndx,
 256                        uint32_t MaxMDCount = 3);
 257
 258 /// Same as the above interface but using an ArrayRef, as well as \p Sum.
 259 void annotateValueSite(Module &M, Instruction &Inst,
 260                        ArrayRef<InstrProfValueData> VDs,
 261                        uint64_t Sum, InstrProfValueKind ValueKind,
 262                        uint32_t MaxMDCount);
 263
 264 /// Extract the value profile data from \p Inst which is annotated with
 265 /// value profile meta data. Return false if there is no value data annotated,
 266 /// otherwise  return true.
 267 bool getValueProfDataFromInst(const Instruction &Inst,
 268                               InstrProfValueKind ValueKind,
 269                               uint32_t MaxNumValueData,
 270                               InstrProfValueData ValueData[],
 271                               uint32_t &ActualNumValueData, uint64_t &TotalC);
 272
 273 inline StringRef getPGOFuncNameMetadataName() { return "PGOFuncName"; }
 274
 275 /// Return the PGOFuncName meta data associated with a function.
 276 MDNode *getPGOFuncNameMetadata(const Function &F);
 277
 278 /// Create the PGOFuncName meta data if PGOFuncName is different from
 279 /// function's raw name. This should only apply to internal linkage functions
 280 /// declared by users only.
 281 void createPGOFuncNameMetadata(Function &F, StringRef PGOFuncName);
 282
 283 /// Check if we can use Comdat for profile variables. This will eliminate
 284 /// the duplicated profile variables for Comdat functions.
 285 bool needsComdatForCounter(const Function &F, const Module &M);
 286
 287 const std::error_category &instrprof_category();
 288
 289 enum class instrprof_error {
 290   success = 0,
 291   eof,
 292   unrecognized_format,
 293   bad_magic,
 294   bad_header,
 295   unsupported_version,
 296   unsupported_hash_type,
 297   too_large,
 298   truncated,
 299   malformed,
 300   unknown_function,
 301   hash_mismatch,
 302   count_mismatch,
 303   counter_overflow,
 304   value_site_count_mismatch,
 305   compress_failed,
 306   uncompress_failed,
 307   empty_raw_profile
 308 };
 309
 310 inline std::error_code make_error_code(instrprof_error E) {
 311   return std::error_code(static_cast<int>(E), instrprof_category());
 312 }
 313
 314 class InstrProfError : public ErrorInfo<InstrProfError> {
 315 public:
 316   InstrProfError(instrprof_error Err) : Err(Err) {
 317     assert(Err != instrprof_error::success && "Not an error");
 318   }
 319
 320   std::string message() const override;
 321
 322   void log(raw_ostream &OS) const override { OS << message(); }
 323
 324   std::error_code convertToErrorCode() const override {
 325     return make_error_code(Err);
 326   }
 327
 328   instrprof_error get() const { return Err; }
 329
 330   /// Consume an Error and return the raw enum value contained within it. The
 331   /// Error must either be a success value, or contain a single InstrProfError.
 332   static instrprof_error take(Error E) {
 333     auto Err = instrprof_error::success;
 334     handleAllErrors(std::move(E), [&Err](const InstrProfError &IPE) {
 335       assert(Err == instrprof_error::success && "Multiple errors encountered");
 336       Err = IPE.get();
 337     });
 338     return Err;
 339   }
 340
 341   static char ID;
 342
 343 private:
 344   instrprof_error Err;
 345 };
 346
 347 class SoftInstrProfErrors {
 348   /// Count the number of soft instrprof_errors encountered and keep track of
 349   /// the first such error for reporting purposes.
 350
 351   /// The first soft error encountered.
 352   instrprof_error FirstError = instrprof_error::success;
 353
 354   /// The number of hash mismatches.
 355   unsigned NumHashMismatches = 0;
 356
 357   /// The number of count mismatches.
 358   unsigned NumCountMismatches = 0;
 359
 360   /// The number of counter overflows.
 361   unsigned NumCounterOverflows = 0;
 362
 363   /// The number of value site count mismatches.
 364   unsigned NumValueSiteCountMismatches = 0;
 365
 366 public:
 367   SoftInstrProfErrors() = default;
 368
 369   ~SoftInstrProfErrors() {
 370     assert(FirstError == instrprof_error::success &&
 371            "Unchecked soft error encountered");
 372   }
 373
 374   /// Track a soft error (\p IE) and increment its associated counter.
 375   void addError(instrprof_error IE);
 376
 377   /// Get the number of hash mismatches.
 378   unsigned getNumHashMismatches() const { return NumHashMismatches; }
 379
 380   /// Get the number of count mismatches.
 381   unsigned getNumCountMismatches() const { return NumCountMismatches; }
 382
 383   /// Get the number of counter overflows.
 384   unsigned getNumCounterOverflows() const { return NumCounterOverflows; }
 385
 386   /// Get the number of value site count mismatches.
 387   unsigned getNumValueSiteCountMismatches() const {
 388     return NumValueSiteCountMismatches;
 389   }
 390
 391   /// Return the first encountered error and reset FirstError to a success
 392   /// value.
 393   Error takeError() {
 394     if (FirstError == instrprof_error::success)
 395       return Error::success();
 396     auto E = make_error<InstrProfError>(FirstError);
 397     FirstError = instrprof_error::success;
 398     return E;
 399   }
 400 };
 401
 402 namespace object {
 403
 404 class SectionRef;
 405
 406 } // end namespace object
 407
 408 namespace IndexedInstrProf {
 409
 410 uint64_t ComputeHash(StringRef K);
 411
 412 } // end namespace IndexedInstrProf
 413
 414 /// A symbol table used for function PGO name look-up with keys
 415 /// (such as pointers, md5hash values) to the function. A function's
 416 /// PGO name or name's md5hash are used in retrieving the profile
 417 /// data of the function. See \c getPGOFuncName() method for details
 418 /// on how PGO name is formed.
 419 class InstrProfSymtab {
 420 public:
 421   typedef std::vector<std::pair<uint64_t, uint64_t>> AddrHashMap;
 422
 423 private:
 424   StringRef Data;
 425   uint64_t Address = 0;
 426   // Unique name strings.
 427   StringSet<> NameTab;
 428   // A map from MD5 keys to function name strings.
 429   std::vector<std::pair<uint64_t, StringRef>> MD5NameMap;
 430   // A map from MD5 keys to function define. We only populate this map
 431   // when build the Symtab from a Module.
 432   std::vector<std::pair<uint64_t, Function *>> MD5FuncMap;
 433   // A map from function runtime address to function name MD5 hash.
 434   // This map is only populated and used by raw instr profile reader.
 435   AddrHashMap AddrToMD5Map;
 436
 437 public:
 438   InstrProfSymtab() = default;
 439
 440   /// Create InstrProfSymtab from an object file section which
 441   /// contains function PGO names. When section may contain raw
 442   /// string data or string data in compressed form. This method
 443   /// only initialize the symtab with reference to the data and
 444   /// the section base address. The decompression will be delayed
 445   /// until before it is used. See also \c create(StringRef) method.
 446   Error create(object::SectionRef &Section);
 447
 448   /// This interface is used by reader of CoverageMapping test
 449   /// format.
 450   inline Error create(StringRef D, uint64_t BaseAddr);
 451
 452   /// \c NameStrings is a string composed of one of more sub-strings
 453   ///  encoded in the format described in \c collectPGOFuncNameStrings.
 454   /// This method is a wrapper to \c readPGOFuncNameStrings method.
 455   inline Error create(StringRef NameStrings);
 456
 457   /// A wrapper interface to populate the PGO symtab with functions
 458   /// decls from module \c M. This interface is used by transformation
 459   /// passes such as indirect function call promotion. Variable \c InLTO
 460   /// indicates if this is called from LTO optimization passes.
 461   void create(Module &M, bool InLTO = false);
 462
 463   /// Create InstrProfSymtab from a set of names iteratable from
 464   /// \p IterRange. This interface is used by IndexedProfReader.
 465   template <typename NameIterRange> void create(const NameIterRange &IterRange);
 466
 467   // If the symtab is created by a series of calls to \c addFuncName, \c
 468   // finalizeSymtab needs to be called before looking up function names.
 469   // This is required because the underlying map is a vector (for space
 470   // efficiency) which needs to be sorted.
 471   inline void finalizeSymtab();
 472
 473   /// Update the symtab by adding \p FuncName to the table. This interface
 474   /// is used by the raw and text profile readers.
 475   void addFuncName(StringRef FuncName) {
 476     auto Ins = NameTab.insert(FuncName);
 477     if (Ins.second)
 478       MD5NameMap.push_back(std::make_pair(
 479           IndexedInstrProf::ComputeHash(FuncName), Ins.first->getKey()));
 480   }
 481
 482   /// Map a function address to its name's MD5 hash. This interface
 483   /// is only used by the raw profiler reader.
 484   void mapAddress(uint64_t Addr, uint64_t MD5Val) {
 485     AddrToMD5Map.push_back(std::make_pair(Addr, MD5Val));
 486   }
 487
 488   AddrHashMap &getAddrHashMap() { return AddrToMD5Map; }
 489
 490   /// Return function's PGO name from the function name's symbol
 491   /// address in the object file. If an error occurs, return
 492   /// an empty string.
 493   StringRef getFuncName(uint64_t FuncNameAddress, size_t NameSize);
 494
 495   /// Return function's PGO name from the name's md5 hash value.
 496   /// If not found, return an empty string.
 497   inline StringRef getFuncName(uint64_t FuncMD5Hash);
 498
 499   /// Return function from the name's md5 hash. Return nullptr if not found.
 500   inline Function *getFunction(uint64_t FuncMD5Hash);
 501
 502   /// Return the function's original assembly name by stripping off
 503   /// the prefix attached (to symbols with priviate linkage). For
 504   /// global functions, it returns the same string as getFuncName.
 505   inline StringRef getOrigFuncName(uint64_t FuncMD5Hash);
 506
 507   /// Return the name section data.
 508   inline StringRef getNameData() const { return Data; }
 509 };
 510
 511 Error InstrProfSymtab::create(StringRef D, uint64_t BaseAddr) {
 512   Data = D;
 513   Address = BaseAddr;
 514   return Error::success();
 515 }
 516
 517 Error InstrProfSymtab::create(StringRef NameStrings) {
 518   return readPGOFuncNameStrings(NameStrings, *this);
 519 }
 520
 521 template <typename NameIterRange>
 522 void InstrProfSymtab::create(const NameIterRange &IterRange) {
 523   for (auto Name : IterRange)
 524     addFuncName(Name);
 525
 526   finalizeSymtab();
 527 }
 528
 529 void InstrProfSymtab::finalizeSymtab() {
 530   std::sort(MD5NameMap.begin(), MD5NameMap.end(), less_first());
 531   std::sort(MD5FuncMap.begin(), MD5FuncMap.end(), less_first());
 532   std::sort(AddrToMD5Map.begin(), AddrToMD5Map.end(), less_first());
 533   AddrToMD5Map.erase(std::unique(AddrToMD5Map.begin(), AddrToMD5Map.end()),
 534                      AddrToMD5Map.end());
 535 }
 536
 537 StringRef InstrProfSymtab::getFuncName(uint64_t FuncMD5Hash) {
 538   auto Result =
 539       std::lower_bound(MD5NameMap.begin(), MD5NameMap.end(), FuncMD5Hash,
 540                        [](const std::pair<uint64_t, std::string> &LHS,
 541                           uint64_t RHS) { return LHS.first < RHS; });
 542   if (Result != MD5NameMap.end() && Result->first == FuncMD5Hash)
 543     return Result->second;
 544   return StringRef();
 545 }
 546
 547 Function* InstrProfSymtab::getFunction(uint64_t FuncMD5Hash) {
 548   auto Result =
 549       std::lower_bound(MD5FuncMap.begin(), MD5FuncMap.end(), FuncMD5Hash,
 550                        [](const std::pair<uint64_t, Function*> &LHS,
 551                           uint64_t RHS) { return LHS.first < RHS; });
 552   if (Result != MD5FuncMap.end() && Result->first == FuncMD5Hash)
 553     return Result->second;
 554   return nullptr;
 555 }
 556
 557 // See also getPGOFuncName implementation. These two need to be
 558 // matched.
 559 StringRef InstrProfSymtab::getOrigFuncName(uint64_t FuncMD5Hash) {
 560   StringRef PGOName = getFuncName(FuncMD5Hash);
 561   size_t S = PGOName.find_first_of(':');
 562   if (S == StringRef::npos)
 563     return PGOName;
 564   return PGOName.drop_front(S + 1);
 565 }
 566
 567 struct InstrProfValueSiteRecord {
 568   /// Value profiling data pairs at a given value site.
 569   std::list<InstrProfValueData> ValueData;
 570
 571   InstrProfValueSiteRecord() { ValueData.clear(); }
 572   template <class InputIterator>
 573   InstrProfValueSiteRecord(InputIterator F, InputIterator L)
 574       : ValueData(F, L) {}
 575
 576   /// Sort ValueData ascending by Value
 577   void sortByTargetValues() {
 578     ValueData.sort(
 579         [](const InstrProfValueData &left, const InstrProfValueData &right) {
 580           return left.Value < right.Value;
 581         });
 582   }
 583   /// Sort ValueData Descending by Count
 584   inline void sortByCount();
 585
 586   /// Merge data from another InstrProfValueSiteRecord
 587   /// Optionally scale merged counts by \p Weight.
 588   void merge(SoftInstrProfErrors &SIPE, InstrProfValueSiteRecord &Input,
 589              uint64_t Weight = 1);
 590   /// Scale up value profile data counts.
 591   void scale(SoftInstrProfErrors &SIPE, uint64_t Weight);
 592 };
 593
 594 /// Profiling information for a single function.
 595 struct InstrProfRecord {
 596   StringRef Name;
 597   uint64_t Hash;
 598   std::vector<uint64_t> Counts;
 599   SoftInstrProfErrors SIPE;
 600
 601   InstrProfRecord() = default;
 602   InstrProfRecord(StringRef Name, uint64_t Hash, std::vector<uint64_t> Counts)
 603       : Name(Name), Hash(Hash), Counts(std::move(Counts)) {}
 604
 605   typedef std::vector<std::pair<uint64_t, uint64_t>> ValueMapType;
 606
 607   /// Return the number of value profile kinds with non-zero number
 608   /// of profile sites.
 609   inline uint32_t getNumValueKinds() const;
 610
 611   /// Return the number of instrumented sites for ValueKind.
 612   inline uint32_t getNumValueSites(uint32_t ValueKind) const;
 613
 614   /// Return the total number of ValueData for ValueKind.
 615   inline uint32_t getNumValueData(uint32_t ValueKind) const;
 616
 617   /// Return the number of value data collected for ValueKind at profiling
 618   /// site: Site.
 619   inline uint32_t getNumValueDataForSite(uint32_t ValueKind,
 620                                          uint32_t Site) const;
 621
 622   /// Return the array of profiled values at \p Site. If \p TotalC
 623   /// is not null, the total count of all target values at this site
 624   /// will be stored in \c *TotalC.
 625   inline std::unique_ptr<InstrProfValueData[]>
 626   getValueForSite(uint32_t ValueKind, uint32_t Site,
 627                   uint64_t *TotalC = nullptr) const;
 628
 629   /// Get the target value/counts of kind \p ValueKind collected at site
 630   /// \p Site and store the result in array \p Dest. Return the total
 631   /// counts of all target values at this site.
 632   inline uint64_t getValueForSite(InstrProfValueData Dest[], uint32_t ValueKind,
 633                                   uint32_t Site) const;
 634
 635   /// Reserve space for NumValueSites sites.
 636   inline void reserveSites(uint32_t ValueKind, uint32_t NumValueSites);
 637
 638   /// Add ValueData for ValueKind at value Site.
 639   void addValueData(uint32_t ValueKind, uint32_t Site,
 640                     InstrProfValueData *VData, uint32_t N,
 641                     ValueMapType *ValueMap);
 642
 643   /// Merge the counts in \p Other into this one.
 644   /// Optionally scale merged counts by \p Weight.
 645   void merge(InstrProfRecord &Other, uint64_t Weight = 1);
 646
 647   /// Scale up profile counts (including value profile data) by
 648   /// \p Weight.
 649   void scale(uint64_t Weight);
 650
 651   /// Sort value profile data (per site) by count.
 652   void sortValueData() {
 653     for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind) {
 654       std::vector<InstrProfValueSiteRecord> &SiteRecords =
 655           getValueSitesForKind(Kind);
 656       for (auto &SR : SiteRecords)
 657         SR.sortByCount();
 658     }
 659   }
 660
 661   /// Clear value data entries and edge counters.
 662   void Clear() {
 663     Counts.clear();
 664     clearValueData();
 665   }
 666
 667   /// Clear value data entries
 668   void clearValueData() {
 669     for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
 670       getValueSitesForKind(Kind).clear();
 671   }
 672
 673   /// Get the error contained within the record's soft error counter.
 674   Error takeError() { return SIPE.takeError(); }
 675
 676 private:
 677   std::vector<InstrProfValueSiteRecord> IndirectCallSites;
 678   std::vector<InstrProfValueSiteRecord> MemOPSizes;
 679   const std::vector<InstrProfValueSiteRecord> &
 680
 681   getValueSitesForKind(uint32_t ValueKind) const {
 682     switch (ValueKind) {
 683     case IPVK_IndirectCallTarget:
 684       return IndirectCallSites;
 685     case IPVK_MemOPSize:
 686       return MemOPSizes;
 687     default:
 688       llvm_unreachable("Unknown value kind!");
 689     }
 690     return IndirectCallSites;
 691   }
 692
 693   std::vector<InstrProfValueSiteRecord> &
 694   getValueSitesForKind(uint32_t ValueKind) {
 695     return const_cast<std::vector<InstrProfValueSiteRecord> &>(
 696         const_cast<const InstrProfRecord *>(this)
 697             ->getValueSitesForKind(ValueKind));
 698   }
 699
 700   // Map indirect call target name hash to name string.
 701   uint64_t remapValue(uint64_t Value, uint32_t ValueKind,
 702                       ValueMapType *HashKeys);
 703
 704   // Merge Value Profile data from Src record to this record for ValueKind.
 705   // Scale merged value counts by \p Weight.
 706   void mergeValueProfData(uint32_t ValueKind, InstrProfRecord &Src,
 707                           uint64_t Weight);
 708
 709   // Scale up value profile data count.
 710   void scaleValueProfData(uint32_t ValueKind, uint64_t Weight);
 711 };
 712
 713 uint32_t InstrProfRecord::getNumValueKinds() const {
 714   uint32_t NumValueKinds = 0;
 715   for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
 716     NumValueKinds += !(getValueSitesForKind(Kind).empty());
 717   return NumValueKinds;
 718 }
 719
 720 uint32_t InstrProfRecord::getNumValueData(uint32_t ValueKind) const {
 721   uint32_t N = 0;
 722   const std::vector<InstrProfValueSiteRecord> &SiteRecords =
 723       getValueSitesForKind(ValueKind);
 724   for (auto &SR : SiteRecords) {
 725     N += SR.ValueData.size();
 726   }
 727   return N;
 728 }
 729
 730 uint32_t InstrProfRecord::getNumValueSites(uint32_t ValueKind) const {
 731   return getValueSitesForKind(ValueKind).size();
 732 }
 733
 734 uint32_t InstrProfRecord::getNumValueDataForSite(uint32_t ValueKind,
 735                                                  uint32_t Site) const {
 736   return getValueSitesForKind(ValueKind)[Site].ValueData.size();
 737 }
 738
 739 std::unique_ptr<InstrProfValueData[]>
 740 InstrProfRecord::getValueForSite(uint32_t ValueKind, uint32_t Site,
 741                                  uint64_t *TotalC) const {
 742   uint64_t Dummy;
 743   uint64_t &TotalCount = (TotalC == nullptr ? Dummy : *TotalC);
 744   uint32_t N = getNumValueDataForSite(ValueKind, Site);
 745   if (N == 0) {
 746     TotalCount = 0;
 747     return std::unique_ptr<InstrProfValueData[]>(nullptr);
 748   }
 749
 750   auto VD = llvm::make_unique<InstrProfValueData[]>(N);
 751   TotalCount = getValueForSite(VD.get(), ValueKind, Site);
 752
 753   return VD;
 754 }
 755
 756 uint64_t InstrProfRecord::getValueForSite(InstrProfValueData Dest[],
 757                                           uint32_t ValueKind,
 758                                           uint32_t Site) const {
 759   uint32_t I = 0;
 760   uint64_t TotalCount = 0;
 761   for (auto V : getValueSitesForKind(ValueKind)[Site].ValueData) {
 762     Dest[I].Value = V.Value;
 763     Dest[I].Count = V.Count;
 764     TotalCount = SaturatingAdd(TotalCount, V.Count);
 765     I++;
 766   }
 767   return TotalCount;
 768 }
 769
 770 void InstrProfRecord::reserveSites(uint32_t ValueKind, uint32_t NumValueSites) {
 771   std::vector<InstrProfValueSiteRecord> &ValueSites =
 772       getValueSitesForKind(ValueKind);
 773   ValueSites.reserve(NumValueSites);
 774 }
 775
 776 inline support::endianness getHostEndianness() {
 777   return sys::IsLittleEndianHost ? support::little : support::big;
 778 }
 779
 780 // Include definitions for value profile data
 781 #define INSTR_PROF_VALUE_PROF_DATA
 782 #include "llvm/ProfileData/InstrProfData.inc"
 783
 784 void InstrProfValueSiteRecord::sortByCount() {
 785   ValueData.sort(
 786       [](const InstrProfValueData &left, const InstrProfValueData &right) {
 787         return left.Count > right.Count;
 788       });
 789   // Now truncate
 790   size_t max_s = INSTR_PROF_MAX_NUM_VAL_PER_SITE;
 791   if (ValueData.size() > max_s)
 792     ValueData.resize(max_s);
 793 }
 794
 795 namespace IndexedInstrProf {
 796
 797 enum class HashT : uint32_t {
 798   MD5,
 799   Last = MD5
 800 };
 801
 802 inline uint64_t ComputeHash(HashT Type, StringRef K) {
 803   switch (Type) {
 804   case HashT::MD5:
 805     return MD5Hash(K);
 806   }
 807   llvm_unreachable("Unhandled hash type");
 808 }
 809
 810 const uint64_t Magic = 0x8169666f72706cff; // "\xfflprofi\x81"
 811
 812 enum ProfVersion {
 813   // Version 1 is the first version. In this version, the value of
 814   // a key/value pair can only include profile data of a single function.
 815   // Due to this restriction, the number of block counters for a given
 816   // function is not recorded but derived from the length of the value.
 817   Version1 = 1,
 818   // The version 2 format supports recording profile data of multiple
 819   // functions which share the same key in one value field. To support this,
 820   // the number block counters is recorded as an uint64_t field right after the
 821   // function structural hash.
 822   Version2 = 2,
 823   // Version 3 supports value profile data. The value profile data is expected
 824   // to follow the block counter profile data.
 825   Version3 = 3,
 826   // In this version, profile summary data \c IndexedInstrProf::Summary is
 827   // stored after the profile header.
 828   Version4 = 4,
 829   // The current version is 4.
 830   CurrentVersion = INSTR_PROF_INDEX_VERSION
 831 };
 832 const uint64_t Version = ProfVersion::CurrentVersion;
 833
 834 const HashT HashType = HashT::MD5;
 835
 836 inline uint64_t ComputeHash(StringRef K) { return ComputeHash(HashType, K); }
 837
 838 // This structure defines the file header of the LLVM profile
 839 // data file in indexed-format.
 840 struct Header {
 841   uint64_t Magic;
 842   uint64_t Version;
 843   uint64_t Unused; // Becomes unused since version 4
 844   uint64_t HashType;
 845   uint64_t HashOffset;
 846 };
 847
 848 // Profile summary data recorded in the profile data file in indexed
 849 // format. It is introduced in version 4. The summary data follows
 850 // right after the profile file header.
 851 struct Summary {
 852   struct Entry {
 853     uint64_t Cutoff; ///< The required percentile of total execution count.
 854     uint64_t
 855         MinBlockCount;  ///< The minimum execution count for this percentile.
 856     uint64_t NumBlocks; ///< Number of blocks >= the minumum execution count.
 857   };
 858   // The field kind enumerator to assigned value mapping should remain
 859   // unchanged  when a new kind is added or an old kind gets deleted in
 860   // the future.
 861   enum SummaryFieldKind {
 862     /// The total number of functions instrumented.
 863     TotalNumFunctions = 0,
 864     /// Total number of instrumented blocks/edges.
 865     TotalNumBlocks = 1,
 866     /// The maximal execution count among all functions.
 867     /// This field does not exist for profile data from IR based
 868     /// instrumentation.
 869     MaxFunctionCount = 2,
 870     /// Max block count of the program.
 871     MaxBlockCount = 3,
 872     /// Max internal block count of the program (excluding entry blocks).
 873     MaxInternalBlockCount = 4,
 874     /// The sum of all instrumented block counts.
 875     TotalBlockCount = 5,
 876     NumKinds = TotalBlockCount + 1
 877   };
 878
 879   // The number of summmary fields following the summary header.
 880   uint64_t NumSummaryFields;
 881   // The number of Cutoff Entries (Summary::Entry) following summary fields.
 882   uint64_t NumCutoffEntries;
 883
 884   static uint32_t getSize(uint32_t NumSumFields, uint32_t NumCutoffEntries) {
 885     return sizeof(Summary) + NumCutoffEntries * sizeof(Entry) +
 886            NumSumFields * sizeof(uint64_t);
 887   }
 888
 889   const uint64_t *getSummaryDataBase() const {
 890     return reinterpret_cast<const uint64_t *>(this + 1);
 891   }
 892
 893   uint64_t *getSummaryDataBase() {
 894     return reinterpret_cast<uint64_t *>(this + 1);
 895   }
 896
 897   const Entry *getCutoffEntryBase() const {
 898     return reinterpret_cast<const Entry *>(
 899         &getSummaryDataBase()[NumSummaryFields]);
 900   }
 901
 902   Entry *getCutoffEntryBase() {
 903     return reinterpret_cast<Entry *>(&getSummaryDataBase()[NumSummaryFields]);
 904   }
 905
 906   uint64_t get(SummaryFieldKind K) const {
 907     return getSummaryDataBase()[K];
 908   }
 909
 910   void set(SummaryFieldKind K, uint64_t V) {
 911     getSummaryDataBase()[K] = V;
 912   }
 913
 914   const Entry &getEntry(uint32_t I) const { return getCutoffEntryBase()[I]; }
 915
 916   void setEntry(uint32_t I, const ProfileSummaryEntry &E) {
 917     Entry &ER = getCutoffEntryBase()[I];
 918     ER.Cutoff = E.Cutoff;
 919     ER.MinBlockCount = E.MinCount;
 920     ER.NumBlocks = E.NumCounts;
 921   }
 922
 923   Summary(uint32_t Size) { memset(this, 0, Size); }
 924   void operator delete(void *ptr) { ::operator delete(ptr); }
 925
 926   Summary() = delete;
 927 };
 928
 929 inline std::unique_ptr<Summary> allocSummary(uint32_t TotalSize) {
 930   return std::unique_ptr<Summary>(new (::operator new(TotalSize))
 931                                       Summary(TotalSize));
 932 }
 933
 934 } // end namespace IndexedInstrProf
 935
 936 namespace RawInstrProf {
 937
 938 // Version 1: First version
 939 // Version 2: Added value profile data section. Per-function control data
 940 // struct has more fields to describe value profile information.
 941 // Version 3: Compressed name section support. Function PGO name reference
 942 // from control data struct is changed from raw pointer to Name's MD5 value.
 943 // Version 4: ValueDataBegin and ValueDataSizes fields are removed from the
 944 // raw header.
 945 const uint64_t Version = INSTR_PROF_RAW_VERSION;
 946
 947 template <class IntPtrT> inline uint64_t getMagic();
 948 template <> inline uint64_t getMagic<uint64_t>() {
 949   return INSTR_PROF_RAW_MAGIC_64;
 950 }
 951
 952 template <> inline uint64_t getMagic<uint32_t>() {
 953   return INSTR_PROF_RAW_MAGIC_32;
 954 }
 955
 956 // Per-function profile data header/control structure.
 957 // The definition should match the structure defined in
 958 // compiler-rt/lib/profile/InstrProfiling.h.
 959 // It should also match the synthesized type in
 960 // Transforms/Instrumentation/InstrProfiling.cpp:getOrCreateRegionCounters.
 961 template <class IntPtrT> struct LLVM_ALIGNAS(8) ProfileData {
 962   #define INSTR_PROF_DATA(Type, LLVMType, Name, Init) Type Name;
 963   #include "llvm/ProfileData/InstrProfData.inc"
 964 };
 965
 966 // File header structure of the LLVM profile data in raw format.
 967 // The definition should match the header referenced in
 968 // compiler-rt/lib/profile/InstrProfilingFile.c  and
 969 // InstrProfilingBuffer.c.
 970 struct Header {
 971 #define INSTR_PROF_RAW_HEADER(Type, Name, Init) const Type Name;
 972 #include "llvm/ProfileData/InstrProfData.inc"
 973 };
 974
 975 } // end namespace RawInstrProf
 976
 977 // Parse MemOP Size range option.
 978 void getMemOPSizeRangeFromOption(std::string Str, int64_t &RangeStart,
 979                                  int64_t &RangeLast);
 980
 981 } // end namespace llvm
 982
 983 #endif // LLVM_PROFILEDATA_INSTRPROF_H