1//===- InstrProf.h - Instrumented profiling format support ------*- C++ -*-===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8// 9// Instrumentation-based profiling data is generated by instrumented 10// binaries through library functions in compiler-rt, and read by the clang 11// frontend to feed PGO. 12// 13//===----------------------------------------------------------------------===// 14 15#ifndef LLVM_PROFILEDATA_INSTRPROF_H 16#define LLVM_PROFILEDATA_INSTRPROF_H 17 18#include "llvm/ADT/ArrayRef.h" 19#include "llvm/ADT/BitmaskEnum.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/CommandLine.h" 28#include "llvm/Support/Compiler.h" 29#include "llvm/Support/Endian.h" 30#include "llvm/Support/Error.h" 31#include "llvm/Support/ErrorHandling.h" 32#include "llvm/Support/Host.h" 33#include "llvm/Support/MD5.h" 34#include "llvm/Support/MathExtras.h" 35#include "llvm/Support/raw_ostream.h" 36#include <algorithm> 37#include <cassert> 38#include <cstddef> 39#include <cstdint> 40#include <cstring> 41#include <list> 42#include <memory> 43#include <string> 44#include <system_error> 45#include <utility> 46#include <vector> 47 48namespace llvm { 49 50class Function; 51class GlobalVariable; 52struct InstrProfRecord; 53class InstrProfSymtab; 54class Instruction; 55class MDNode; 56class Module; 57 58enum InstrProfSectKind { 59#define INSTR_PROF_SECT_ENTRY(Kind, SectNameCommon, SectNameCoff, Prefix) Kind, 60#include "llvm/ProfileData/InstrProfData.inc" 61}; 62 63/// Return the max count value. We reserver a few large values for special use. 64inline uint64_t getInstrMaxCountValue() { 65 return std::numeric_limits<uint64_t>::max() - 2; 66} 67 68/// Return the name of the profile section corresponding to \p IPSK. 69/// 70/// The name of the section depends on the object format type \p OF. If 71/// \p AddSegmentInfo is true, a segment prefix and additional linker hints may 72/// be added to the section name (this is the default). 73std::string getInstrProfSectionName(InstrProfSectKind IPSK, 74 Triple::ObjectFormatType OF, 75 bool AddSegmentInfo = true); 76 77/// Return the name profile runtime entry point to do value profiling 78/// for a given site. 79inline StringRef getInstrProfValueProfFuncName() { 80 return INSTR_PROF_VALUE_PROF_FUNC_STR; 81} 82 83/// Return the name profile runtime entry point to do memop size value 84/// profiling. 85inline StringRef getInstrProfValueProfMemOpFuncName() { 86 return INSTR_PROF_VALUE_PROF_MEMOP_FUNC_STR; 87} 88 89/// Return the name prefix of variables containing instrumented function names. 90inline StringRef getInstrProfNameVarPrefix() { return "__profn_"; } 91 92/// Return the name prefix of variables containing per-function control data. 93inline StringRef getInstrProfDataVarPrefix() { return "__profd_"; } 94 95/// Return the name prefix of profile counter variables. 96inline StringRef getInstrProfCountersVarPrefix() { return "__profc_"; } 97 98/// Return the name prefix of value profile variables. 99inline StringRef getInstrProfValuesVarPrefix() { return "__profvp_"; } 100 101/// Return the name of value profile node array variables: 102inline StringRef getInstrProfVNodesVarName() { return "__llvm_prf_vnodes"; } 103 104/// Return the name of the variable holding the strings (possibly compressed) 105/// of all function's PGO names. 106inline StringRef getInstrProfNamesVarName() { 107 return "__llvm_prf_nm"; 108} 109 110/// Return the name of a covarage mapping variable (internal linkage) 111/// for each instrumented source module. Such variables are allocated 112/// in the __llvm_covmap section. 113inline StringRef getCoverageMappingVarName() { 114 return "__llvm_coverage_mapping"; 115} 116 117/// Return the name of the internal variable recording the array 118/// of PGO name vars referenced by the coverage mapping. The owning 119/// functions of those names are not emitted by FE (e.g, unused inline 120/// functions.) 121inline StringRef getCoverageUnusedNamesVarName() { 122 return "__llvm_coverage_names"; 123} 124 125/// Return the name of function that registers all the per-function control 126/// data at program startup time by calling __llvm_register_function. This 127/// function has internal linkage and is called by __llvm_profile_init 128/// runtime method. This function is not generated for these platforms: 129/// Darwin, Linux, and FreeBSD. 130inline StringRef getInstrProfRegFuncsName() { 131 return "__llvm_profile_register_functions"; 132} 133 134/// Return the name of the runtime interface that registers per-function control 135/// data for one instrumented function. 136inline StringRef getInstrProfRegFuncName() { 137 return "__llvm_profile_register_function"; 138} 139 140/// Return the name of the runtime interface that registers the PGO name strings. 141inline StringRef getInstrProfNamesRegFuncName() { 142 return "__llvm_profile_register_names_function"; 143} 144 145/// Return the name of the runtime initialization method that is generated by 146/// the compiler. The function calls __llvm_profile_register_functions and 147/// __llvm_profile_override_default_filename functions if needed. This function 148/// has internal linkage and invoked at startup time via init_array. 149inline StringRef getInstrProfInitFuncName() { return "__llvm_profile_init"; } 150 151/// Return the name of the hook variable defined in profile runtime library. 152/// A reference to the variable causes the linker to link in the runtime 153/// initialization module (which defines the hook variable). 154inline StringRef getInstrProfRuntimeHookVarName() { 155 return INSTR_PROF_QUOTE(INSTR_PROF_PROFILE_RUNTIME_VAR); 156} 157 158/// Return the name of the compiler generated function that references the 159/// runtime hook variable. The function is a weak global. 160inline StringRef getInstrProfRuntimeHookVarUseFuncName() { 161 return "__llvm_profile_runtime_user"; 162} 163 164inline StringRef getInstrProfCounterBiasVarName() { 165 return INSTR_PROF_QUOTE(INSTR_PROF_PROFILE_COUNTER_BIAS_VAR); 166} 167 168/// Return the marker used to separate PGO names during serialization. 169inline 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. 174std::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. 181std::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. 189std::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. 195GlobalVariable *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. 201GlobalVariable *createPGOFuncNameVar(Module &M, 202 GlobalValue::LinkageTypes Linkage, 203 StringRef PGOFuncName); 204 205/// Return the initializer in string of the PGO name var \c NameVar. 206StringRef getPGOFuncNameVarInitializer(GlobalVariable *NameVar); 207 208/// Given a PGO function name, remove the filename prefix and return 209/// the original (static) function name. 210StringRef getFuncNameWithoutPrefix(StringRef PGOFuncName, 211 StringRef FileName = "<unknown>"); 212 213/// Given a vector of strings (function PGO names) \c NameStrs, the 214/// method generates a combined string \c Result that is ready to be 215/// serialized. The \c Result string is comprised of three fields: 216/// The first field is the length of the uncompressed strings, and the 217/// the second field is the length of the zlib-compressed string. 218/// Both fields are encoded in ULEB128. If \c doCompress is false, the 219/// third field is the uncompressed strings; otherwise it is the 220/// compressed string. When the string compression is off, the 221/// second field will have value zero. 222Error collectPGOFuncNameStrings(ArrayRef<std::string> NameStrs, 223 bool doCompression, std::string &Result); 224 225/// Produce \c Result string with the same format described above. The input 226/// is vector of PGO function name variables that are referenced. 227Error collectPGOFuncNameStrings(ArrayRef<GlobalVariable *> NameVars, 228 std::string &Result, bool doCompression = true); 229 230/// \c NameStrings is a string composed of one of more sub-strings encoded in 231/// the format described above. The substrings are separated by 0 or more zero 232/// bytes. This method decodes the string and populates the \c Symtab. 233Error readPGOFuncNameStrings(StringRef NameStrings, InstrProfSymtab &Symtab); 234 235/// Check if INSTR_PROF_RAW_VERSION_VAR is defined. This global is only being 236/// set in IR PGO compilation. 237bool isIRPGOFlagSet(const Module *M); 238 239/// Check if we can safely rename this Comdat function. Instances of the same 240/// comdat function may have different control flows thus can not share the 241/// same counter variable. 242bool canRenameComdatFunc(const Function &F, bool CheckAddressTaken = false); 243 244enum InstrProfValueKind : uint32_t { 245#define VALUE_PROF_KIND(Enumerator, Value, Descr) Enumerator = Value, 246#include "llvm/ProfileData/InstrProfData.inc" 247}; 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. 252void annotateValueSite(Module &M, Instruction &Inst, 253 const InstrProfRecord &InstrProfR, 254 InstrProfValueKind ValueKind, uint32_t SiteIndx, 255 uint32_t MaxMDCount = 3); 256 257/// Same as the above interface but using an ArrayRef, as well as \p Sum. 258void annotateValueSite(Module &M, Instruction &Inst, 259 ArrayRef<InstrProfValueData> VDs, uint64_t Sum, 260 InstrProfValueKind ValueKind, 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. 265bool getValueProfDataFromInst(const Instruction &Inst, 266 InstrProfValueKind ValueKind, 267 uint32_t MaxNumValueData, 268 InstrProfValueData ValueData[], 269 uint32_t &ActualNumValueData, uint64_t &TotalC, 270 bool GetNoICPValue = false); 271 272inline StringRef getPGOFuncNameMetadataName() { return "PGOFuncName"; } 273 274/// Return the PGOFuncName meta data associated with a function. 275MDNode *getPGOFuncNameMetadata(const Function &F); 276 277/// Create the PGOFuncName meta data if PGOFuncName is different from 278/// function's raw name. This should only apply to internal linkage functions 279/// declared by users only. 280void createPGOFuncNameMetadata(Function &F, StringRef PGOFuncName); 281 282/// Check if we can use Comdat for profile variables. This will eliminate 283/// the duplicated profile variables for Comdat functions. 284bool needsComdatForCounter(const Function &F, const Module &M); 285 286/// An enum describing the attributes of an instrumented profile. 287enum class InstrProfKind { 288 Unknown = 0x0, 289 // A frontend clang profile, incompatible with other attrs. 290 FrontendInstrumentation = 0x1, 291 // An IR-level profile (default when -fprofile-generate is used). 292 IRInstrumentation = 0x2, 293 // A profile with entry basic block instrumentation. 294 FunctionEntryInstrumentation = 0x4, 295 // A context sensitive IR-level profile. 296 ContextSensitive = 0x8, 297 // Use single byte probes for coverage. 298 SingleByteCoverage = 0x10, 299 // Only instrument the function entry basic block. 300 FunctionEntryOnly = 0x20, 301 // A memory profile collected using -fprofile=memory. 302 MemProf = 0x40, 303 LLVM_MARK_AS_BITMASK_ENUM(/*LargestValue=*/MemProf) 304}; 305 306const std::error_category &instrprof_category(); 307 308enum class instrprof_error { 309 success = 0, 310 eof, 311 unrecognized_format, 312 bad_magic, 313 bad_header, 314 unsupported_version, 315 unsupported_hash_type, 316 too_large, 317 truncated, 318 malformed, 319 missing_debug_info_for_correlation, 320 unexpected_debug_info_for_correlation, 321 unable_to_correlate_profile, 322 unknown_function, 323 invalid_prof, 324 hash_mismatch, 325 count_mismatch, 326 counter_overflow, 327 value_site_count_mismatch, 328 compress_failed, 329 uncompress_failed, 330 empty_raw_profile, 331 zlib_unavailable 332}; 333 334inline std::error_code make_error_code(instrprof_error E) { 335 return std::error_code(static_cast<int>(E), instrprof_category()); 336} 337 338class InstrProfError : public ErrorInfo<InstrProfError> { 339public: 340 InstrProfError(instrprof_error Err, const Twine &ErrStr = Twine()) 341 : Err(Err), Msg(ErrStr.str()) { 342 assert(Err != instrprof_error::success && "Not an error"); 343 } 344 345 std::string message() const override; 346 347 void log(raw_ostream &OS) const override { OS << message(); } 348 349 std::error_code convertToErrorCode() const override { 350 return make_error_code(Err); 351 } 352 353 instrprof_error get() const { return Err; } 354 const std::string &getMessage() const { return Msg; } 355 356 /// Consume an Error and return the raw enum value contained within it. The 357 /// Error must either be a success value, or contain a single InstrProfError. 358 static instrprof_error take(Error E) { 359 auto Err = instrprof_error::success; 360 handleAllErrors(std::move(E), [&Err](const InstrProfError &IPE) { 361 assert(Err == instrprof_error::success && "Multiple errors encountered"); 362 Err = IPE.get(); 363 }); 364 return Err; 365 } 366 367 static char ID; 368 369private: 370 instrprof_error Err; 371 std::string Msg; 372}; 373 374class SoftInstrProfErrors { 375 /// Count the number of soft instrprof_errors encountered and keep track of 376 /// the first such error for reporting purposes. 377 378 /// The first soft error encountered. 379 instrprof_error FirstError = instrprof_error::success; 380 381 /// The number of hash mismatches. 382 unsigned NumHashMismatches = 0; 383 384 /// The number of count mismatches. 385 unsigned NumCountMismatches = 0; 386 387 /// The number of counter overflows. 388 unsigned NumCounterOverflows = 0; 389 390 /// The number of value site count mismatches. 391 unsigned NumValueSiteCountMismatches = 0; 392 393public: 394 SoftInstrProfErrors() = default; 395 396 ~SoftInstrProfErrors() { 397 assert(FirstError == instrprof_error::success && 398 "Unchecked soft error encountered"); 399 } 400 401 /// Track a soft error (\p IE) and increment its associated counter. 402 void addError(instrprof_error IE); 403 404 /// Get the number of hash mismatches. 405 unsigned getNumHashMismatches() const { return NumHashMismatches; } 406 407 /// Get the number of count mismatches. 408 unsigned getNumCountMismatches() const { return NumCountMismatches; } 409 410 /// Get the number of counter overflows. 411 unsigned getNumCounterOverflows() const { return NumCounterOverflows; } 412 413 /// Get the number of value site count mismatches. 414 unsigned getNumValueSiteCountMismatches() const { 415 return NumValueSiteCountMismatches; 416 } 417 418 /// Return the first encountered error and reset FirstError to a success 419 /// value. 420 Error takeError() { 421 if (FirstError == instrprof_error::success) 422 return Error::success(); 423 auto E = make_error<InstrProfError>(FirstError); 424 FirstError = instrprof_error::success; 425 return E; 426 } 427}; 428 429namespace object { 430 431class SectionRef; 432 433} // end namespace object 434 435namespace IndexedInstrProf { 436 437uint64_t ComputeHash(StringRef K); 438 439} // end namespace IndexedInstrProf 440 441/// A symbol table used for function PGO name look-up with keys 442/// (such as pointers, md5hash values) to the function. A function's 443/// PGO name or name's md5hash are used in retrieving the profile 444/// data of the function. See \c getPGOFuncName() method for details 445/// on how PGO name is formed. 446class InstrProfSymtab { 447public: 448 using AddrHashMap = std::vector<std::pair<uint64_t, uint64_t>>; 449 450private: 451 StringRef Data; 452 uint64_t Address = 0; 453 // Unique name strings. 454 StringSet<> NameTab; 455 // A map from MD5 keys to function name strings. 456 std::vector<std::pair<uint64_t, StringRef>> MD5NameMap; 457 // A map from MD5 keys to function define. We only populate this map 458 // when build the Symtab from a Module. 459 std::vector<std::pair<uint64_t, Function *>> MD5FuncMap; 460 // A map from function runtime address to function name MD5 hash. 461 // This map is only populated and used by raw instr profile reader. 462 AddrHashMap AddrToMD5Map; 463 bool Sorted = false; 464 465 static StringRef getExternalSymbol() { 466 return "** External Symbol **"; 467 } 468 469 // If the symtab is created by a series of calls to \c addFuncName, \c 470 // finalizeSymtab needs to be called before looking up function names. 471 // This is required because the underlying map is a vector (for space 472 // efficiency) which needs to be sorted. 473 inline void finalizeSymtab(); 474 475public: 476 InstrProfSymtab() = default; 477 478 /// Create InstrProfSymtab from an object file section which 479 /// contains function PGO names. When section may contain raw 480 /// string data or string data in compressed form. This method 481 /// only initialize the symtab with reference to the data and 482 /// the section base address. The decompression will be delayed 483 /// until before it is used. See also \c create(StringRef) method. 484 Error create(object::SectionRef &Section); 485 486 /// This interface is used by reader of CoverageMapping test 487 /// format. 488 inline Error create(StringRef D, uint64_t BaseAddr); 489 490 /// \c NameStrings is a string composed of one of more sub-strings 491 /// encoded in the format described in \c collectPGOFuncNameStrings. 492 /// This method is a wrapper to \c readPGOFuncNameStrings method. 493 inline Error create(StringRef NameStrings); 494 495 /// A wrapper interface to populate the PGO symtab with functions 496 /// decls from module \c M. This interface is used by transformation 497 /// passes such as indirect function call promotion. Variable \c InLTO 498 /// indicates if this is called from LTO optimization passes. 499 Error create(Module &M, bool InLTO = false); 500 501 /// Create InstrProfSymtab from a set of names iteratable from 502 /// \p IterRange. This interface is used by IndexedProfReader. 503 template <typename NameIterRange> Error create(const NameIterRange &IterRange); 504 505 /// Update the symtab by adding \p FuncName to the table. This interface 506 /// is used by the raw and text profile readers. 507 Error addFuncName(StringRef FuncName) { 508 if (FuncName.empty()) 509 return make_error<InstrProfError>(instrprof_error::malformed, 510 "function name is empty"); 511 auto Ins = NameTab.insert(FuncName); 512 if (Ins.second) { 513 MD5NameMap.push_back(std::make_pair( 514 IndexedInstrProf::ComputeHash(FuncName), Ins.first->getKey())); 515 Sorted = false; 516 } 517 return Error::success(); 518 } 519 520 /// Map a function address to its name's MD5 hash. This interface 521 /// is only used by the raw profiler reader. 522 void mapAddress(uint64_t Addr, uint64_t MD5Val) { 523 AddrToMD5Map.push_back(std::make_pair(Addr, MD5Val)); 524 } 525 526 /// Return a function's hash, or 0, if the function isn't in this SymTab. 527 uint64_t getFunctionHashFromAddress(uint64_t Address); 528 529 /// Return function's PGO name from the function name's symbol 530 /// address in the object file. If an error occurs, return 531 /// an empty string. 532 StringRef getFuncName(uint64_t FuncNameAddress, size_t NameSize); 533 534 /// Return function's PGO name from the name's md5 hash value. 535 /// If not found, return an empty string. 536 inline StringRef getFuncName(uint64_t FuncMD5Hash); 537 538 /// Just like getFuncName, except that it will return a non-empty StringRef 539 /// if the function is external to this symbol table. All such cases 540 /// will be represented using the same StringRef value. 541 inline StringRef getFuncNameOrExternalSymbol(uint64_t FuncMD5Hash); 542 543 /// True if Symbol is the value used to represent external symbols. 544 static bool isExternalSymbol(const StringRef &Symbol) { 545 return Symbol == InstrProfSymtab::getExternalSymbol(); 546 } 547 548 /// Return function from the name's md5 hash. Return nullptr if not found. 549 inline Function *getFunction(uint64_t FuncMD5Hash); 550 551 /// Return the function's original assembly name by stripping off 552 /// the prefix attached (to symbols with priviate linkage). For 553 /// global functions, it returns the same string as getFuncName. 554 inline StringRef getOrigFuncName(uint64_t FuncMD5Hash); 555 556 /// Return the name section data. 557 inline StringRef getNameData() const { return Data; } 558 559 /// Dump the symbols in this table. 560 void dumpNames(raw_ostream &OS) const { 561 for (StringRef S : NameTab.keys()) 562 OS << S << "\n"; 563 } 564}; 565 566Error InstrProfSymtab::create(StringRef D, uint64_t BaseAddr) { 567 Data = D; 568 Address = BaseAddr; 569 return Error::success(); 570} 571 572Error InstrProfSymtab::create(StringRef NameStrings) { 573 return readPGOFuncNameStrings(NameStrings, *this); 574} 575 576template <typename NameIterRange> 577Error InstrProfSymtab::create(const NameIterRange &IterRange) { 578 for (auto Name : IterRange) 579 if (Error E = addFuncName(Name)) 580 return E; 581 582 finalizeSymtab(); 583 return Error::success(); 584} 585 586void InstrProfSymtab::finalizeSymtab() { 587 if (Sorted) 588 return; 589 llvm::sort(MD5NameMap, less_first()); 590 llvm::sort(MD5FuncMap, less_first()); 591 llvm::sort(AddrToMD5Map, less_first()); 592 AddrToMD5Map.erase(std::unique(AddrToMD5Map.begin(), AddrToMD5Map.end()), 593 AddrToMD5Map.end()); 594 Sorted = true; 595} 596 597StringRef InstrProfSymtab::getFuncNameOrExternalSymbol(uint64_t FuncMD5Hash) { 598 StringRef ret = getFuncName(FuncMD5Hash); 599 if (ret.empty()) 600 return InstrProfSymtab::getExternalSymbol(); 601 return ret; 602} 603 604StringRef InstrProfSymtab::getFuncName(uint64_t FuncMD5Hash) { 605 finalizeSymtab(); 606 auto Result = llvm::lower_bound(MD5NameMap, FuncMD5Hash, 607 [](const std::pair<uint64_t, StringRef> &LHS, 608 uint64_t RHS) { return LHS.first < RHS; }); 609 if (Result != MD5NameMap.end() && Result->first == FuncMD5Hash) 610 return Result->second; 611 return StringRef(); 612} 613 614Function* InstrProfSymtab::getFunction(uint64_t FuncMD5Hash) { 615 finalizeSymtab(); 616 auto Result = llvm::lower_bound(MD5FuncMap, FuncMD5Hash, 617 [](const std::pair<uint64_t, Function *> &LHS, 618 uint64_t RHS) { return LHS.first < RHS; }); 619 if (Result != MD5FuncMap.end() && Result->first == FuncMD5Hash) 620 return Result->second; 621 return nullptr; 622} 623 624// See also getPGOFuncName implementation. These two need to be 625// matched. 626StringRef InstrProfSymtab::getOrigFuncName(uint64_t FuncMD5Hash) { 627 StringRef PGOName = getFuncName(FuncMD5Hash); 628 size_t S = PGOName.find_first_of(':'); 629 if (S == StringRef::npos) 630 return PGOName; 631 return PGOName.drop_front(S + 1); 632} 633 634// To store the sums of profile count values, or the percentage of 635// the sums of the total count values. 636struct CountSumOrPercent { 637 uint64_t NumEntries; 638 double CountSum; 639 double ValueCounts[IPVK_Last - IPVK_First + 1]; 640 CountSumOrPercent() : NumEntries(0), CountSum(0.0f), ValueCounts() {} 641 void reset() { 642 NumEntries = 0; 643 CountSum = 0.0f; 644 for (double &VC : ValueCounts) 645 VC = 0.0f; 646 } 647}; 648 649// Function level or program level overlap information. 650struct OverlapStats { 651 enum OverlapStatsLevel { ProgramLevel, FunctionLevel }; 652 // Sum of the total count values for the base profile. 653 CountSumOrPercent Base; 654 // Sum of the total count values for the test profile. 655 CountSumOrPercent Test; 656 // Overlap lap score. Should be in range of [0.0f to 1.0f]. 657 CountSumOrPercent Overlap; 658 CountSumOrPercent Mismatch; 659 CountSumOrPercent Unique; 660 OverlapStatsLevel Level; 661 const std::string *BaseFilename; 662 const std::string *TestFilename; 663 StringRef FuncName; 664 uint64_t FuncHash; 665 bool Valid; 666 667 OverlapStats(OverlapStatsLevel L = ProgramLevel) 668 : Level(L), BaseFilename(nullptr), TestFilename(nullptr), FuncHash(0), 669 Valid(false) {} 670 671 void dump(raw_fd_ostream &OS) const; 672 673 void setFuncInfo(StringRef Name, uint64_t Hash) { 674 FuncName = Name; 675 FuncHash = Hash; 676 } 677 678 Error accumulateCounts(const std::string &BaseFilename, 679 const std::string &TestFilename, bool IsCS); 680 void addOneMismatch(const CountSumOrPercent &MismatchFunc); 681 void addOneUnique(const CountSumOrPercent &UniqueFunc); 682 683 static inline double score(uint64_t Val1, uint64_t Val2, double Sum1, 684 double Sum2) { 685 if (Sum1 < 1.0f || Sum2 < 1.0f) 686 return 0.0f; 687 return std::min(Val1 / Sum1, Val2 / Sum2); 688 } 689}; 690 691// This is used to filter the functions whose overlap information 692// to be output. 693struct OverlapFuncFilters { 694 uint64_t ValueCutoff; 695 const std::string NameFilter; 696}; 697 698struct InstrProfValueSiteRecord { 699 /// Value profiling data pairs at a given value site. 700 std::list<InstrProfValueData> ValueData; 701 702 InstrProfValueSiteRecord() { ValueData.clear(); } 703 template <class InputIterator> 704 InstrProfValueSiteRecord(InputIterator F, InputIterator L) 705 : ValueData(F, L) {} 706 707 /// Sort ValueData ascending by Value 708 void sortByTargetValues() { 709 ValueData.sort( 710 [](const InstrProfValueData &left, const InstrProfValueData &right) { 711 return left.Value < right.Value; 712 }); 713 } 714 /// Sort ValueData Descending by Count 715 inline void sortByCount(); 716 717 /// Merge data from another InstrProfValueSiteRecord 718 /// Optionally scale merged counts by \p Weight. 719 void merge(InstrProfValueSiteRecord &Input, uint64_t Weight, 720 function_ref<void(instrprof_error)> Warn); 721 /// Scale up value profile data counts by N (Numerator) / D (Denominator). 722 void scale(uint64_t N, uint64_t D, function_ref<void(instrprof_error)> Warn); 723 724 /// Compute the overlap b/w this record and Input record. 725 void overlap(InstrProfValueSiteRecord &Input, uint32_t ValueKind, 726 OverlapStats &Overlap, OverlapStats &FuncLevelOverlap); 727}; 728 729/// Profiling information for a single function. 730struct InstrProfRecord { 731 std::vector<uint64_t> Counts; 732 733 InstrProfRecord() = default; 734 InstrProfRecord(std::vector<uint64_t> Counts) : Counts(std::move(Counts)) {} 735 InstrProfRecord(InstrProfRecord &&) = default; 736 InstrProfRecord(const InstrProfRecord &RHS) 737 : Counts(RHS.Counts), 738 ValueData(RHS.ValueData 739 ? std::make_unique<ValueProfData>(*RHS.ValueData) 740 : nullptr) {} 741 InstrProfRecord &operator=(InstrProfRecord &&) = default; 742 InstrProfRecord &operator=(const InstrProfRecord &RHS) { 743 Counts = RHS.Counts; 744 if (!RHS.ValueData) { 745 ValueData = nullptr; 746 return *this; 747 } 748 if (!ValueData) 749 ValueData = std::make_unique<ValueProfData>(*RHS.ValueData); 750 else 751 *ValueData = *RHS.ValueData; 752 return *this; 753 } 754 755 /// Return the number of value profile kinds with non-zero number 756 /// of profile sites. 757 inline uint32_t getNumValueKinds() const; 758 /// Return the number of instrumented sites for ValueKind. 759 inline uint32_t getNumValueSites(uint32_t ValueKind) const; 760 761 /// Return the total number of ValueData for ValueKind. 762 inline uint32_t getNumValueData(uint32_t ValueKind) const; 763 764 /// Return the number of value data collected for ValueKind at profiling 765 /// site: Site. 766 inline uint32_t getNumValueDataForSite(uint32_t ValueKind, 767 uint32_t Site) const; 768 769 /// Return the array of profiled values at \p Site. If \p TotalC 770 /// is not null, the total count of all target values at this site 771 /// will be stored in \c *TotalC. 772 inline std::unique_ptr<InstrProfValueData[]> 773 getValueForSite(uint32_t ValueKind, uint32_t Site, 774 uint64_t *TotalC = nullptr) const; 775 776 /// Get the target value/counts of kind \p ValueKind collected at site 777 /// \p Site and store the result in array \p Dest. Return the total 778 /// counts of all target values at this site. 779 inline uint64_t getValueForSite(InstrProfValueData Dest[], uint32_t ValueKind, 780 uint32_t Site) const; 781 782 /// Reserve space for NumValueSites sites. 783 inline void reserveSites(uint32_t ValueKind, uint32_t NumValueSites); 784 785 /// Add ValueData for ValueKind at value Site. 786 void addValueData(uint32_t ValueKind, uint32_t Site, 787 InstrProfValueData *VData, uint32_t N, 788 InstrProfSymtab *SymTab); 789 790 /// Merge the counts in \p Other into this one. 791 /// Optionally scale merged counts by \p Weight. 792 void merge(InstrProfRecord &Other, uint64_t Weight, 793 function_ref<void(instrprof_error)> Warn); 794 795 /// Scale up profile counts (including value profile data) by 796 /// a factor of (N / D). 797 void scale(uint64_t N, uint64_t D, function_ref<void(instrprof_error)> Warn); 798 799 /// Sort value profile data (per site) by count. 800 void sortValueData() { 801 for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind) 802 for (auto &SR : getValueSitesForKind(Kind)) 803 SR.sortByCount(); 804 } 805 806 /// Clear value data entries and edge counters. 807 void Clear() { 808 Counts.clear(); 809 clearValueData(); 810 } 811 812 /// Clear value data entries 813 void clearValueData() { ValueData = nullptr; } 814 815 /// Compute the sums of all counts and store in Sum. 816 void accumulateCounts(CountSumOrPercent &Sum) const; 817 818 /// Compute the overlap b/w this IntrprofRecord and Other. 819 void overlap(InstrProfRecord &Other, OverlapStats &Overlap, 820 OverlapStats &FuncLevelOverlap, uint64_t ValueCutoff); 821 822 /// Compute the overlap of value profile counts. 823 void overlapValueProfData(uint32_t ValueKind, InstrProfRecord &Src, 824 OverlapStats &Overlap, 825 OverlapStats &FuncLevelOverlap); 826 827 enum CountPseudoKind { 828 NotPseudo = 0, 829 PseudoHot, 830 PseudoWarm, 831 }; 832 enum PseudoCountVal { 833 HotFunctionVal = -1, 834 WarmFunctionVal = -2, 835 }; 836 CountPseudoKind getCountPseudoKind() const { 837 uint64_t FirstCount = Counts[0]; 838 if (FirstCount == (uint64_t)HotFunctionVal) 839 return PseudoHot; 840 if (FirstCount == (uint64_t)WarmFunctionVal) 841 return PseudoWarm; 842 return NotPseudo; 843 } 844 void setPseudoCount(CountPseudoKind Kind) { 845 if (Kind == PseudoHot) 846 Counts[0] = (uint64_t)HotFunctionVal; 847 else if (Kind == PseudoWarm) 848 Counts[0] = (uint64_t)WarmFunctionVal; 849 } 850 851private: 852 struct ValueProfData { 853 std::vector<InstrProfValueSiteRecord> IndirectCallSites; 854 std::vector<InstrProfValueSiteRecord> MemOPSizes; 855 }; 856 std::unique_ptr<ValueProfData> ValueData; 857 858 MutableArrayRef<InstrProfValueSiteRecord> 859 getValueSitesForKind(uint32_t ValueKind) { 860 // Cast to /add/ const (should be an implicit_cast, ideally, if that's ever 861 // implemented in LLVM) to call the const overload of this function, then 862 // cast away the constness from the result. 863 auto AR = const_cast<const InstrProfRecord *>(this)->getValueSitesForKind( 864 ValueKind); 865 return MutableArrayRef( 866 const_cast<InstrProfValueSiteRecord *>(AR.data()), AR.size()); 867 } 868 ArrayRef<InstrProfValueSiteRecord> 869 getValueSitesForKind(uint32_t ValueKind) const { 870 if (!ValueData) 871 return std::nullopt; 872 switch (ValueKind) { 873 case IPVK_IndirectCallTarget: 874 return ValueData->IndirectCallSites; 875 case IPVK_MemOPSize: 876 return ValueData->MemOPSizes; 877 default: 878 llvm_unreachable("Unknown value kind!"); 879 } 880 } 881 882 std::vector<InstrProfValueSiteRecord> & 883 getOrCreateValueSitesForKind(uint32_t ValueKind) { 884 if (!ValueData) 885 ValueData = std::make_unique<ValueProfData>(); 886 switch (ValueKind) { 887 case IPVK_IndirectCallTarget: 888 return ValueData->IndirectCallSites; 889 case IPVK_MemOPSize: 890 return ValueData->MemOPSizes; 891 default: 892 llvm_unreachable("Unknown value kind!"); 893 } 894 } 895 896 // Map indirect call target name hash to name string. 897 uint64_t remapValue(uint64_t Value, uint32_t ValueKind, 898 InstrProfSymtab *SymTab); 899 900 // Merge Value Profile data from Src record to this record for ValueKind. 901 // Scale merged value counts by \p Weight. 902 void mergeValueProfData(uint32_t ValkeKind, InstrProfRecord &Src, 903 uint64_t Weight, 904 function_ref<void(instrprof_error)> Warn); 905 906 // Scale up value profile data count by N (Numerator) / D (Denominator). 907 void scaleValueProfData(uint32_t ValueKind, uint64_t N, uint64_t D, 908 function_ref<void(instrprof_error)> Warn); 909}; 910 911struct NamedInstrProfRecord : InstrProfRecord { 912 StringRef Name; 913 uint64_t Hash; 914 915 // We reserve this bit as the flag for context sensitive profile record. 916 static const int CS_FLAG_IN_FUNC_HASH = 60; 917 918 NamedInstrProfRecord() = default; 919 NamedInstrProfRecord(StringRef Name, uint64_t Hash, 920 std::vector<uint64_t> Counts) 921 : InstrProfRecord(std::move(Counts)), Name(Name), Hash(Hash) {} 922 923 static bool hasCSFlagInHash(uint64_t FuncHash) { 924 return ((FuncHash >> CS_FLAG_IN_FUNC_HASH) & 1); 925 } 926 static void setCSFlagInHash(uint64_t &FuncHash) { 927 FuncHash |= ((uint64_t)1 << CS_FLAG_IN_FUNC_HASH); 928 } 929}; 930 931uint32_t InstrProfRecord::getNumValueKinds() const { 932 uint32_t NumValueKinds = 0; 933 for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind) 934 NumValueKinds += !(getValueSitesForKind(Kind).empty()); 935 return NumValueKinds; 936} 937 938uint32_t InstrProfRecord::getNumValueData(uint32_t ValueKind) const { 939 uint32_t N = 0; 940 for (const auto &SR : getValueSitesForKind(ValueKind)) 941 N += SR.ValueData.size(); 942 return N; 943} 944 945uint32_t InstrProfRecord::getNumValueSites(uint32_t ValueKind) const { 946 return getValueSitesForKind(ValueKind).size(); 947} 948 949uint32_t InstrProfRecord::getNumValueDataForSite(uint32_t ValueKind, 950 uint32_t Site) const { 951 return getValueSitesForKind(ValueKind)[Site].ValueData.size(); 952} 953 954std::unique_ptr<InstrProfValueData[]> 955InstrProfRecord::getValueForSite(uint32_t ValueKind, uint32_t Site, 956 uint64_t *TotalC) const { 957 uint64_t Dummy = 0; 958 uint64_t &TotalCount = (TotalC == nullptr ? Dummy : *TotalC); 959 uint32_t N = getNumValueDataForSite(ValueKind, Site); 960 if (N == 0) { 961 TotalCount = 0; 962 return std::unique_ptr<InstrProfValueData[]>(nullptr); 963 } 964 965 auto VD = std::make_unique<InstrProfValueData[]>(N); 966 TotalCount = getValueForSite(VD.get(), ValueKind, Site); 967 968 return VD; 969} 970 971uint64_t InstrProfRecord::getValueForSite(InstrProfValueData Dest[], 972 uint32_t ValueKind, 973 uint32_t Site) const { 974 uint32_t I = 0; 975 uint64_t TotalCount = 0; 976 for (auto V : getValueSitesForKind(ValueKind)[Site].ValueData) { 977 Dest[I].Value = V.Value; 978 Dest[I].Count = V.Count; 979 TotalCount = SaturatingAdd(TotalCount, V.Count); 980 I++; 981 } 982 return TotalCount; 983} 984 985void InstrProfRecord::reserveSites(uint32_t ValueKind, uint32_t NumValueSites) { 986 if (!NumValueSites) 987 return; 988 getOrCreateValueSitesForKind(ValueKind).reserve(NumValueSites); 989} 990 991inline support::endianness getHostEndianness() { 992 return sys::IsLittleEndianHost ? support::little : support::big; 993} 994 995// Include definitions for value profile data 996#define INSTR_PROF_VALUE_PROF_DATA 997#include "llvm/ProfileData/InstrProfData.inc" 998 999void InstrProfValueSiteRecord::sortByCount() { 1000 ValueData.sort( 1001 [](const InstrProfValueData &left, const InstrProfValueData &right) { 1002 return left.Count > right.Count; 1003 }); 1004 // Now truncate 1005 size_t max_s = INSTR_PROF_MAX_NUM_VAL_PER_SITE; 1006 if (ValueData.size() > max_s) 1007 ValueData.resize(max_s); 1008} 1009 1010namespace IndexedInstrProf { 1011 1012enum class HashT : uint32_t { 1013 MD5, 1014 Last = MD5 1015}; 1016 1017inline uint64_t ComputeHash(HashT Type, StringRef K) { 1018 switch (Type) { 1019 case HashT::MD5: 1020 return MD5Hash(K); 1021 } 1022 llvm_unreachable("Unhandled hash type"); 1023} 1024 1025const uint64_t Magic = 0x8169666f72706cff; // "\xfflprofi\x81" 1026 1027enum ProfVersion { 1028 // Version 1 is the first version. In this version, the value of 1029 // a key/value pair can only include profile data of a single function. 1030 // Due to this restriction, the number of block counters for a given 1031 // function is not recorded but derived from the length of the value. 1032 Version1 = 1, 1033 // The version 2 format supports recording profile data of multiple 1034 // functions which share the same key in one value field. To support this, 1035 // the number block counters is recorded as an uint64_t field right after the 1036 // function structural hash. 1037 Version2 = 2, 1038 // Version 3 supports value profile data. The value profile data is expected 1039 // to follow the block counter profile data. 1040 Version3 = 3, 1041 // In this version, profile summary data \c IndexedInstrProf::Summary is 1042 // stored after the profile header. 1043 Version4 = 4, 1044 // In this version, the frontend PGO stable hash algorithm defaults to V2. 1045 Version5 = 5, 1046 // In this version, the frontend PGO stable hash algorithm got fixed and 1047 // may produce hashes different from Version5. 1048 Version6 = 6, 1049 // An additional counter is added around logical operators. 1050 Version7 = 7, 1051 // An additional (optional) memory profile type is added. 1052 Version8 = 8, 1053 // Binary ids are added. 1054 Version9 = 9, 1055 // The current version is 9. 1056 CurrentVersion = INSTR_PROF_INDEX_VERSION 1057}; 1058const uint64_t Version = ProfVersion::CurrentVersion; 1059 1060const HashT HashType = HashT::MD5; 1061 1062inline uint64_t ComputeHash(StringRef K) { return ComputeHash(HashType, K); } 1063 1064// This structure defines the file header of the LLVM profile 1065// data file in indexed-format. 1066struct Header { 1067 uint64_t Magic; 1068 uint64_t Version; 1069 uint64_t Unused; // Becomes unused since version 4 1070 uint64_t HashType; 1071 uint64_t HashOffset; 1072 uint64_t MemProfOffset; 1073 uint64_t BinaryIdOffset; 1074 // New fields should only be added at the end to ensure that the size 1075 // computation is correct. The methods below need to be updated to ensure that 1076 // the new field is read correctly. 1077 1078 // Reads a header struct from the buffer. 1079 static Expected<Header> readFromBuffer(const unsigned char *Buffer); 1080 1081 // Returns the size of the header in bytes for all valid fields based on the 1082 // version. I.e a older version header will return a smaller size. 1083 size_t size() const; 1084 1085 // Returns the format version in little endian. The header retains the version 1086 // in native endian of the compiler runtime. 1087 uint64_t formatVersion() const; 1088}; 1089 1090// Profile summary data recorded in the profile data file in indexed 1091// format. It is introduced in version 4. The summary data follows 1092// right after the profile file header. 1093struct Summary { 1094 struct Entry { 1095 uint64_t Cutoff; ///< The required percentile of total execution count. 1096 uint64_t 1097 MinBlockCount; ///< The minimum execution count for this percentile. 1098 uint64_t NumBlocks; ///< Number of blocks >= the minumum execution count. 1099 }; 1100 // The field kind enumerator to assigned value mapping should remain 1101 // unchanged when a new kind is added or an old kind gets deleted in 1102 // the future. 1103 enum SummaryFieldKind { 1104 /// The total number of functions instrumented. 1105 TotalNumFunctions = 0, 1106 /// Total number of instrumented blocks/edges. 1107 TotalNumBlocks = 1, 1108 /// The maximal execution count among all functions. 1109 /// This field does not exist for profile data from IR based 1110 /// instrumentation. 1111 MaxFunctionCount = 2, 1112 /// Max block count of the program. 1113 MaxBlockCount = 3, 1114 /// Max internal block count of the program (excluding entry blocks). 1115 MaxInternalBlockCount = 4, 1116 /// The sum of all instrumented block counts. 1117 TotalBlockCount = 5, 1118 NumKinds = TotalBlockCount + 1 1119 }; 1120 1121 // The number of summmary fields following the summary header. 1122 uint64_t NumSummaryFields; 1123 // The number of Cutoff Entries (Summary::Entry) following summary fields. 1124 uint64_t NumCutoffEntries; 1125 1126 Summary() = delete; 1127 Summary(uint32_t Size) { memset(this, 0, Size); } 1128 1129 void operator delete(void *ptr) { ::operator delete(ptr); } 1130 1131 static uint32_t getSize(uint32_t NumSumFields, uint32_t NumCutoffEntries) { 1132 return sizeof(Summary) + NumCutoffEntries * sizeof(Entry) + 1133 NumSumFields * sizeof(uint64_t); 1134 } 1135 1136 const uint64_t *getSummaryDataBase() const { 1137 return reinterpret_cast<const uint64_t *>(this + 1); 1138 } 1139 1140 uint64_t *getSummaryDataBase() { 1141 return reinterpret_cast<uint64_t *>(this + 1); 1142 } 1143 1144 const Entry *getCutoffEntryBase() const { 1145 return reinterpret_cast<const Entry *>( 1146 &getSummaryDataBase()[NumSummaryFields]); 1147 } 1148 1149 Entry *getCutoffEntryBase() { 1150 return reinterpret_cast<Entry *>(&getSummaryDataBase()[NumSummaryFields]); 1151 } 1152 1153 uint64_t get(SummaryFieldKind K) const { 1154 return getSummaryDataBase()[K]; 1155 } 1156 1157 void set(SummaryFieldKind K, uint64_t V) { 1158 getSummaryDataBase()[K] = V; 1159 } 1160 1161 const Entry &getEntry(uint32_t I) const { return getCutoffEntryBase()[I]; } 1162 1163 void setEntry(uint32_t I, const ProfileSummaryEntry &E) { 1164 Entry &ER = getCutoffEntryBase()[I]; 1165 ER.Cutoff = E.Cutoff; 1166 ER.MinBlockCount = E.MinCount; 1167 ER.NumBlocks = E.NumCounts; 1168 } 1169}; 1170 1171inline std::unique_ptr<Summary> allocSummary(uint32_t TotalSize) { 1172 return std::unique_ptr<Summary>(new (::operator new(TotalSize)) 1173 Summary(TotalSize)); 1174} 1175 1176} // end namespace IndexedInstrProf 1177 1178namespace RawInstrProf { 1179 1180// Version 1: First version 1181// Version 2: Added value profile data section. Per-function control data 1182// struct has more fields to describe value profile information. 1183// Version 3: Compressed name section support. Function PGO name reference 1184// from control data struct is changed from raw pointer to Name's MD5 value. 1185// Version 4: ValueDataBegin and ValueDataSizes fields are removed from the 1186// raw header. 1187// Version 5: Bit 60 of FuncHash is reserved for the flag for the context 1188// sensitive records. 1189// Version 6: Added binary id. 1190// Version 7: Reorder binary id and include version in signature. 1191// Version 8: Use relative counter pointer. 1192const uint64_t Version = INSTR_PROF_RAW_VERSION; 1193 1194template <class IntPtrT> inline uint64_t getMagic(); 1195template <> inline uint64_t getMagic<uint64_t>() { 1196 return INSTR_PROF_RAW_MAGIC_64; 1197} 1198 1199template <> inline uint64_t getMagic<uint32_t>() { 1200 return INSTR_PROF_RAW_MAGIC_32; 1201} 1202 1203// Per-function profile data header/control structure. 1204// The definition should match the structure defined in 1205// compiler-rt/lib/profile/InstrProfiling.h. 1206// It should also match the synthesized type in 1207// Transforms/Instrumentation/InstrProfiling.cpp:getOrCreateRegionCounters. 1208template <class IntPtrT> struct alignas(8) ProfileData { 1209 #define INSTR_PROF_DATA(Type, LLVMType, Name, Init) Type Name; 1210 #include "llvm/ProfileData/InstrProfData.inc" 1211}; 1212 1213// File header structure of the LLVM profile data in raw format. 1214// The definition should match the header referenced in 1215// compiler-rt/lib/profile/InstrProfilingFile.c and 1216// InstrProfilingBuffer.c. 1217struct Header { 1218#define INSTR_PROF_RAW_HEADER(Type, Name, Init) const Type Name; 1219#include "llvm/ProfileData/InstrProfData.inc" 1220}; 1221 1222} // end namespace RawInstrProf 1223 1224// Parse MemOP Size range option. 1225void getMemOPSizeRangeFromOption(StringRef Str, int64_t &RangeStart, 1226 int64_t &RangeLast); 1227 1228// Create the variable for the profile file name. 1229void createProfileFileNameVar(Module &M, StringRef InstrProfileOutput); 1230 1231// Whether to compress function names in profile records, and filenames in 1232// code coverage mappings. Used by the Instrumentation library and unit tests. 1233extern cl::opt<bool> DoInstrProfNameCompression; 1234 1235} // end namespace llvm 1236#endif // LLVM_PROFILEDATA_INSTRPROF_H 1237