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