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