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/ProfileData/InstrProfData.inc"
  24 #include "llvm/Support/Endian.h"
  25 #include "llvm/Support/ErrorHandling.h"
  26 #include "llvm/Support/ErrorOr.h"
  27 #include "llvm/Support/MD5.h"
  28 #include <cstdint>
  29 #include <list>
  30 #include <system_error>
  31 #include <vector>
  32
  33 #define INSTR_PROF_INDEX_VERSION 3
  34 namespace llvm {
  35
  36 class Function;
  37 class GlobalVariable;
  38 class Module;
  39
  40 /// Return the name of data section containing profile counter variables.
  41 inline StringRef getInstrProfCountersSectionName(bool AddSegment) {
  42   return AddSegment ? "__DATA," INSTR_PROF_CNTS_SECT_NAME_STR
  43                     : INSTR_PROF_CNTS_SECT_NAME_STR;
  44 }
  45
  46 /// Return the name of data section containing names of instrumented
  47 /// functions.
  48 inline StringRef getInstrProfNameSectionName(bool AddSegment) {
  49   return AddSegment ? "__DATA," INSTR_PROF_NAME_SECT_NAME_STR
  50                     : INSTR_PROF_NAME_SECT_NAME_STR;
  51 }
  52
  53 /// Return the name of the data section containing per-function control
  54 /// data.
  55 inline StringRef getInstrProfDataSectionName(bool AddSegment) {
  56   return AddSegment ? "__DATA," INSTR_PROF_DATA_SECT_NAME_STR
  57                     : INSTR_PROF_DATA_SECT_NAME_STR;
  58 }
  59
  60 /// Return the name profile runtime entry point to do value profiling
  61 /// for a given site.
  62 inline StringRef getInstrProfValueProfFuncName() {
  63   return INSTR_PROF_VALUE_PROF_FUNC_STR;
  64 }
  65
  66 /// Return the name of the section containing function coverage mapping
  67 /// data.
  68 inline StringRef getInstrProfCoverageSectionName(bool AddSegment) {
  69   return AddSegment ? "__DATA,__llvm_covmap" : "__llvm_covmap";
  70 }
  71
  72 /// Return the name prefix of variables containing instrumented function names.
  73 inline StringRef getInstrProfNameVarPrefix() { return "__profn_"; }
  74
  75 /// Return the name prefix of variables containing per-function control data.
  76 inline StringRef getInstrProfDataVarPrefix() { return "__profd_"; }
  77
  78 /// Return the name prefix of profile counter variables.
  79 inline StringRef getInstrProfCountersVarPrefix() { return "__profc_"; }
  80
  81 /// Return the name prefix of the COMDAT group for instrumentation variables
  82 /// associated with a COMDAT function.
  83 inline StringRef getInstrProfComdatPrefix() { return "__profv_"; }
  84
  85 /// Return the name of a covarage mapping variable (internal linkage)
  86 /// for each instrumented source module. Such variables are allocated
  87 /// in the __llvm_covmap section.
  88 inline StringRef getCoverageMappingVarName() {
  89   return "__llvm_coverage_mapping";
  90 }
  91
  92 /// Return the name of function that registers all the per-function control
  93 /// data at program startup time by calling __llvm_register_function. This
  94 /// function has internal linkage and is called by  __llvm_profile_init
  95 /// runtime method. This function is not generated for these platforms:
  96 /// Darwin, Linux, and FreeBSD.
  97 inline StringRef getInstrProfRegFuncsName() {
  98   return "__llvm_profile_register_functions";
  99 }
 100
 101 /// Return the name of the runtime interface that registers per-function control
 102 /// data for one instrumented function.
 103 inline StringRef getInstrProfRegFuncName() {
 104   return "__llvm_profile_register_function";
 105 }
 106
 107 /// Return the name of the runtime initialization method that is generated by
 108 /// the compiler. The function calls __llvm_profile_register_functions and
 109 /// __llvm_profile_override_default_filename functions if needed. This function
 110 /// has internal linkage and invoked at startup time via init_array.
 111 inline StringRef getInstrProfInitFuncName() { return "__llvm_profile_init"; }
 112
 113 /// Return the name of the hook variable defined in profile runtime library.
 114 /// A reference to the variable causes the linker to link in the runtime
 115 /// initialization module (which defines the hook variable).
 116 inline StringRef getInstrProfRuntimeHookVarName() {
 117   return "__llvm_profile_runtime";
 118 }
 119
 120 /// Return the name of the compiler generated function that references the
 121 /// runtime hook variable. The function is a weak global.
 122 inline StringRef getInstrProfRuntimeHookVarUseFuncName() {
 123   return "__llvm_profile_runtime_user";
 124 }
 125
 126 /// Return the name of the profile runtime interface that overrides the default
 127 /// profile data file name.
 128 inline StringRef getInstrProfFileOverriderFuncName() {
 129   return "__llvm_profile_override_default_filename";
 130 }
 131
 132 /// Return the modified name for function \c F suitable to be
 133 /// used the key for profile lookup.
 134 std::string getPGOFuncName(const Function &F,
 135                            uint64_t Version = INSTR_PROF_INDEX_VERSION);
 136
 137 /// Return the modified name for a function suitable to be
 138 /// used the key for profile lookup. The function's original
 139 /// name is \c RawFuncName and has linkage of type \c Linkage.
 140 /// The function is defined in module \c FileName.
 141 std::string getPGOFuncName(StringRef RawFuncName,
 142                            GlobalValue::LinkageTypes Linkage,
 143                            StringRef FileName,
 144                            uint64_t Version = INSTR_PROF_INDEX_VERSION);
 145
 146 /// Create and return the global variable for function name used in PGO
 147 /// instrumentation. \c FuncName is the name of the function returned
 148 /// by \c getPGOFuncName call.
 149 GlobalVariable *createPGOFuncNameVar(Function &F, StringRef FuncName);
 150
 151 /// Create and return the global variable for function name used in PGO
 152 /// instrumentation.  /// \c FuncName is the name of the function
 153 /// returned by \c getPGOFuncName call, \c M is the owning module,
 154 /// and \c Linkage is the linkage of the instrumented function.
 155 GlobalVariable *createPGOFuncNameVar(Module &M,
 156                                      GlobalValue::LinkageTypes Linkage,
 157                                      StringRef FuncName);
 158
 159 /// Given a PGO function name, remove the filename prefix and return
 160 /// the original (static) function name.
 161 StringRef getFuncNameWithoutPrefix(StringRef PGOFuncName, StringRef FileName);
 162
 163 const std::error_category &instrprof_category();
 164
 165 enum class instrprof_error {
 166   success = 0,
 167   eof,
 168   unrecognized_format,
 169   bad_magic,
 170   bad_header,
 171   unsupported_version,
 172   unsupported_hash_type,
 173   too_large,
 174   truncated,
 175   malformed,
 176   unknown_function,
 177   hash_mismatch,
 178   count_mismatch,
 179   counter_overflow,
 180   value_site_count_mismatch
 181 };
 182
 183 inline std::error_code make_error_code(instrprof_error E) {
 184   return std::error_code(static_cast<int>(E), instrprof_category());
 185 }
 186
 187 inline instrprof_error MergeResult(instrprof_error &Accumulator,
 188                                    instrprof_error Result) {
 189   // Prefer first error encountered as later errors may be secondary effects of
 190   // the initial problem.
 191   if (Accumulator == instrprof_error::success &&
 192       Result != instrprof_error::success)
 193     Accumulator = Result;
 194   return Accumulator;
 195 }
 196
 197 enum InstrProfValueKind : uint32_t {
 198 #define VALUE_PROF_KIND(Enumerator, Value) Enumerator = Value,
 199 #include "llvm/ProfileData/InstrProfData.inc"
 200 };
 201
 202 namespace object {
 203 class SectionRef;
 204 }
 205
 206 namespace IndexedInstrProf {
 207 uint64_t ComputeHash(StringRef K);
 208 }
 209
 210 /// A symbol table used for function PGO name look-up with keys
 211 /// (such as pointers, md5hash values) to the function. A function's
 212 /// PGO name or name's md5hash are used in retrieving the profile
 213 /// data of the function. See \c getPGOFuncName() method for details
 214 /// on how PGO name is formed.
 215 class InstrProfSymtab {
 216 private:
 217   StringRef Data;
 218   uint64_t Address;
 219   std::vector<std::pair<uint64_t, std::string>> HashNameMap;
 220
 221 public:
 222   InstrProfSymtab() : Data(), Address(0) {}
 223
 224   /// Create InstrProfSymtab from a object file section which
 225   /// contains function PGO names that are uncompressed.
 226   std::error_code create(object::SectionRef &Section);
 227   std::error_code create(StringRef D, uint64_t BaseAddr) {
 228     Data = D;
 229     Address = BaseAddr;
 230     return std::error_code();
 231   }
 232   template <typename NameIterRange> void create(NameIterRange &IterRange) {
 233     for (auto Name : IterRange)
 234       HashNameMap.push_back(
 235           std::make_pair(IndexedInstrProf::ComputeHash(Name), Name.str()));
 236     finalizeSymtab();
 237   }
 238
 239   // If the symtab is created by a series calls to \c addFuncName, \c
 240   // finalizeSymtab needs to
 241   // be called before function name/symbol lookup using MD5 hash. This is
 242   // required because
 243   // the underlying map is vector (for space efficiency) which needs to be
 244   // sorted.
 245   void finalizeSymtab() {
 246     std::sort(HashNameMap.begin(), HashNameMap.end(), less_first());
 247     HashNameMap.erase(std::unique(HashNameMap.begin(), HashNameMap.end()),
 248                       HashNameMap.end());
 249   }
 250
 251   void addFuncName(StringRef FuncName) {
 252     HashNameMap.push_back(std::make_pair(
 253         IndexedInstrProf::ComputeHash(FuncName), FuncName.str()));
 254   }
 255
 256   /// Return function's PGO name from the function name's symabol
 257   /// address in the object file. If an error occurs, Return
 258   /// an empty string.
 259   StringRef getFuncName(uint64_t FuncNameAddress, size_t NameSize);
 260   /// Return function's PGO name from the name's md5 hash value.
 261   /// If not found, return an empty string.
 262   StringRef getFuncName(uint64_t FuncMD5Hash) {
 263     auto Result =
 264         std::lower_bound(HashNameMap.begin(), HashNameMap.end(), FuncMD5Hash,
 265                          [](const std::pair<uint64_t, std::string> &LHS,
 266                             uint64_t RHS) { return LHS.first < RHS; });
 267     if (Result != HashNameMap.end())
 268       return Result->second;
 269     return StringRef();
 270   }
 271 };
 272
 273 struct InstrProfStringTable {
 274   // Set of string values in profiling data.
 275   StringSet<> StringValueSet;
 276   InstrProfStringTable() { StringValueSet.clear(); }
 277   // Get a pointer to internal storage of a string in set
 278   const char *getStringData(StringRef Str) {
 279     auto Result = StringValueSet.find(Str);
 280     return (Result == StringValueSet.end()) ? nullptr : Result->first().data();
 281   }
 282   // Insert a string to StringTable
 283   const char *insertString(StringRef Str) {
 284     auto Result = StringValueSet.insert(Str);
 285     return Result.first->first().data();
 286   }
 287 };
 288
 289 struct InstrProfValueSiteRecord {
 290   /// Value profiling data pairs at a given value site.
 291   std::list<InstrProfValueData> ValueData;
 292
 293   InstrProfValueSiteRecord() { ValueData.clear(); }
 294   template <class InputIterator>
 295   InstrProfValueSiteRecord(InputIterator F, InputIterator L)
 296       : ValueData(F, L) {}
 297
 298   /// Sort ValueData ascending by Value
 299   void sortByTargetValues() {
 300     ValueData.sort(
 301         [](const InstrProfValueData &left, const InstrProfValueData &right) {
 302           return left.Value < right.Value;
 303         });
 304   }
 305
 306   /// Merge data from another InstrProfValueSiteRecord
 307   /// Optionally scale merged counts by \p Weight.
 308   instrprof_error mergeValueData(InstrProfValueSiteRecord &Input,
 309                                  uint64_t Weight = 1);
 310 };
 311
 312 /// Profiling information for a single function.
 313 struct InstrProfRecord {
 314   InstrProfRecord() {}
 315   InstrProfRecord(StringRef Name, uint64_t Hash, std::vector<uint64_t> Counts)
 316       : Name(Name), Hash(Hash), Counts(std::move(Counts)) {}
 317   StringRef Name;
 318   uint64_t Hash;
 319   std::vector<uint64_t> Counts;
 320
 321   typedef std::vector<std::pair<uint64_t, const char *>> ValueMapType;
 322
 323   /// Return the number of value profile kinds with non-zero number
 324   /// of profile sites.
 325   inline uint32_t getNumValueKinds() const;
 326   /// Return the number of instrumented sites for ValueKind.
 327   inline uint32_t getNumValueSites(uint32_t ValueKind) const;
 328   /// Return the total number of ValueData for ValueKind.
 329   inline uint32_t getNumValueData(uint32_t ValueKind) const;
 330   /// Return the number of value data collected for ValueKind at profiling
 331   /// site: Site.
 332   inline uint32_t getNumValueDataForSite(uint32_t ValueKind,
 333                                          uint32_t Site) const;
 334   /// Return the array of profiled values at \p Site.
 335   inline std::unique_ptr<InstrProfValueData[]>
 336   getValueForSite(uint32_t ValueKind, uint32_t Site,
 337                   uint64_t (*ValueMapper)(uint32_t, uint64_t) = 0) const;
 338   inline void
 339   getValueForSite(InstrProfValueData Dest[], uint32_t ValueKind, uint32_t Site,
 340                   uint64_t (*ValueMapper)(uint32_t, uint64_t) = 0) const;
 341   /// Reserve space for NumValueSites sites.
 342   inline void reserveSites(uint32_t ValueKind, uint32_t NumValueSites);
 343   /// Add ValueData for ValueKind at value Site.
 344   void addValueData(uint32_t ValueKind, uint32_t Site,
 345                     InstrProfValueData *VData, uint32_t N,
 346                     ValueMapType *HashKeys);
 347
 348   /// Merge the counts in \p Other into this one.
 349   /// Optionally scale merged counts by \p Weight.
 350   instrprof_error merge(InstrProfRecord &Other, uint64_t Weight = 1);
 351
 352   /// Used by InstrProfWriter: update the value strings to commoned strings in
 353   /// the writer instance.
 354   void updateStrings(InstrProfStringTable *StrTab);
 355
 356   /// Clear value data entries
 357   void clearValueData() {
 358     for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
 359       getValueSitesForKind(Kind).clear();
 360   }
 361
 362 private:
 363   std::vector<InstrProfValueSiteRecord> IndirectCallSites;
 364   const std::vector<InstrProfValueSiteRecord> &
 365   getValueSitesForKind(uint32_t ValueKind) const {
 366     switch (ValueKind) {
 367     case IPVK_IndirectCallTarget:
 368       return IndirectCallSites;
 369     default:
 370       llvm_unreachable("Unknown value kind!");
 371     }
 372     return IndirectCallSites;
 373   }
 374
 375   std::vector<InstrProfValueSiteRecord> &
 376   getValueSitesForKind(uint32_t ValueKind) {
 377     return const_cast<std::vector<InstrProfValueSiteRecord> &>(
 378         const_cast<const InstrProfRecord *>(this)
 379             ->getValueSitesForKind(ValueKind));
 380   }
 381
 382   // Map indirect call target name hash to name string.
 383   uint64_t remapValue(uint64_t Value, uint32_t ValueKind,
 384                       ValueMapType *HashKeys);
 385
 386   // Merge Value Profile data from Src record to this record for ValueKind.
 387   // Scale merged value counts by \p Weight.
 388   instrprof_error mergeValueProfData(uint32_t ValueKind, InstrProfRecord &Src,
 389                                      uint64_t Weight);
 390 };
 391
 392 uint32_t InstrProfRecord::getNumValueKinds() const {
 393   uint32_t NumValueKinds = 0;
 394   for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
 395     NumValueKinds += !(getValueSitesForKind(Kind).empty());
 396   return NumValueKinds;
 397 }
 398
 399 uint32_t InstrProfRecord::getNumValueData(uint32_t ValueKind) const {
 400   uint32_t N = 0;
 401   const std::vector<InstrProfValueSiteRecord> &SiteRecords =
 402       getValueSitesForKind(ValueKind);
 403   for (auto &SR : SiteRecords) {
 404     N += SR.ValueData.size();
 405   }
 406   return N;
 407 }
 408
 409 uint32_t InstrProfRecord::getNumValueSites(uint32_t ValueKind) const {
 410   return getValueSitesForKind(ValueKind).size();
 411 }
 412
 413 uint32_t InstrProfRecord::getNumValueDataForSite(uint32_t ValueKind,
 414                                                  uint32_t Site) const {
 415   return getValueSitesForKind(ValueKind)[Site].ValueData.size();
 416 }
 417
 418 std::unique_ptr<InstrProfValueData[]> InstrProfRecord::getValueForSite(
 419     uint32_t ValueKind, uint32_t Site,
 420     uint64_t (*ValueMapper)(uint32_t, uint64_t)) const {
 421   uint32_t N = getNumValueDataForSite(ValueKind, Site);
 422   if (N == 0)
 423     return std::unique_ptr<InstrProfValueData[]>(nullptr);
 424
 425   auto VD = llvm::make_unique<InstrProfValueData[]>(N);
 426   getValueForSite(VD.get(), ValueKind, Site, ValueMapper);
 427
 428   return VD;
 429 }
 430
 431 void InstrProfRecord::getValueForSite(InstrProfValueData Dest[],
 432                                       uint32_t ValueKind, uint32_t Site,
 433                                       uint64_t (*ValueMapper)(uint32_t,
 434                                                               uint64_t)) const {
 435   uint32_t I = 0;
 436   for (auto V : getValueSitesForKind(ValueKind)[Site].ValueData) {
 437     Dest[I].Value = ValueMapper ? ValueMapper(ValueKind, V.Value) : V.Value;
 438     Dest[I].Count = V.Count;
 439     I++;
 440   }
 441 }
 442
 443 void InstrProfRecord::reserveSites(uint32_t ValueKind, uint32_t NumValueSites) {
 444   std::vector<InstrProfValueSiteRecord> &ValueSites =
 445       getValueSitesForKind(ValueKind);
 446   ValueSites.reserve(NumValueSites);
 447 }
 448
 449 inline support::endianness getHostEndianness() {
 450   return sys::IsLittleEndianHost ? support::little : support::big;
 451 }
 452
 453 // Include definitions for value profile data
 454 #define INSTR_PROF_VALUE_PROF_DATA
 455 #include "llvm/ProfileData/InstrProfData.inc"
 456
 457  /*
 458  * Initialize the record for runtime value profile data.
 459  * Return 0 if the initialization is successful, otherwise
 460  * return 1.
 461  */
 462 int initializeValueProfRuntimeRecord(ValueProfRuntimeRecord *RuntimeRecord,
 463                                      const uint16_t *NumValueSites,
 464                                      ValueProfNode **Nodes);
 465
 466 /* Release memory allocated for the runtime record.  */
 467 void finalizeValueProfRuntimeRecord(ValueProfRuntimeRecord *RuntimeRecord);
 468
 469 /* Return the size of ValueProfData structure that can be used to store
 470    the value profile data collected at runtime. */
 471 uint32_t getValueProfDataSizeRT(const ValueProfRuntimeRecord *Record);
 472
 473 /* Return a ValueProfData instance that stores the data collected at runtime. */
 474 ValueProfData *
 475 serializeValueProfDataFromRT(const ValueProfRuntimeRecord *Record,
 476                              ValueProfData *Dst);
 477
 478 namespace IndexedInstrProf {
 479
 480 enum class HashT : uint32_t {
 481   MD5,
 482
 483   Last = MD5
 484 };
 485
 486 static inline uint64_t MD5Hash(StringRef Str) {
 487   MD5 Hash;
 488   Hash.update(Str);
 489   llvm::MD5::MD5Result Result;
 490   Hash.final(Result);
 491   // Return the least significant 8 bytes. Our MD5 implementation returns the
 492   // result in little endian, so we may need to swap bytes.
 493   using namespace llvm::support;
 494   return endian::read<uint64_t, little, unaligned>(Result);
 495 }
 496
 497 inline uint64_t ComputeHash(HashT Type, StringRef K) {
 498   switch (Type) {
 499   case HashT::MD5:
 500     return IndexedInstrProf::MD5Hash(K);
 501   }
 502   llvm_unreachable("Unhandled hash type");
 503 }
 504
 505 const uint64_t Magic = 0x8169666f72706cff; // "\xfflprofi\x81"
 506 const uint64_t Version = INSTR_PROF_INDEX_VERSION;
 507 const HashT HashType = HashT::MD5;
 508
 509 inline uint64_t ComputeHash(StringRef K) { return ComputeHash(HashType, K); }
 510
 511 // This structure defines the file header of the LLVM profile
 512 // data file in indexed-format.
 513 struct Header {
 514   uint64_t Magic;
 515   uint64_t Version;
 516   uint64_t MaxFunctionCount;
 517   uint64_t HashType;
 518   uint64_t HashOffset;
 519 };
 520
 521 } // end namespace IndexedInstrProf
 522
 523 namespace RawInstrProf {
 524
 525 const uint64_t Version = INSTR_PROF_RAW_VERSION;
 526
 527 template <class IntPtrT> inline uint64_t getMagic();
 528 template <> inline uint64_t getMagic<uint64_t>() {
 529   return INSTR_PROF_RAW_MAGIC_64;
 530 }
 531
 532 template <> inline uint64_t getMagic<uint32_t>() {
 533   return INSTR_PROF_RAW_MAGIC_32;
 534 }
 535
 536 // Per-function profile data header/control structure.
 537 // The definition should match the structure defined in
 538 // compiler-rt/lib/profile/InstrProfiling.h.
 539 // It should also match the synthesized type in
 540 // Transforms/Instrumentation/InstrProfiling.cpp:getOrCreateRegionCounters.
 541 template <class IntPtrT> struct LLVM_ALIGNAS(8) ProfileData {
 542   #define INSTR_PROF_DATA(Type, LLVMType, Name, Init) Type Name;
 543   #include "llvm/ProfileData/InstrProfData.inc"
 544 };
 545
 546 // File header structure of the LLVM profile data in raw format.
 547 // The definition should match the header referenced in
 548 // compiler-rt/lib/profile/InstrProfilingFile.c  and
 549 // InstrProfilingBuffer.c.
 550 struct Header {
 551 #define INSTR_PROF_RAW_HEADER(Type, Name, Init) const Type Name;
 552 #include "llvm/ProfileData/InstrProfData.inc"
 553 };
 554
 555 }  // end namespace RawInstrProf
 556
 557 namespace coverage {
 558
 559 // Profile coverage map has the following layout:
 560 // [CoverageMapFileHeader]
 561 // [ArrayStart]
 562 //  [CovMapFunctionRecord]
 563 //  [CovMapFunctionRecord]
 564 //  ...
 565 // [ArrayEnd]
 566 // [Encoded Region Mapping Data]
 567 LLVM_PACKED_START
 568 template <class IntPtrT> struct CovMapFunctionRecord {
 569   #define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Type Name;
 570   #include "llvm/ProfileData/InstrProfData.inc"
 571 };
 572 LLVM_PACKED_END
 573
 574 }
 575
 576 } // end namespace llvm
 577
 578 namespace std {
 579 template <>
 580 struct is_error_code_enum<llvm::instrprof_error> : std::true_type {};
 581 }
 582
 583 #endif // LLVM_PROFILEDATA_INSTRPROF_H_