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