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