1749 lines · cpp
1//===- InstrProf.cpp - Instrumented profiling format support --------------===//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-exception6//7//===----------------------------------------------------------------------===//8//9// This file contains support for clang's instrumentation based PGO and10// coverage.11//12//===----------------------------------------------------------------------===//13 14#include "llvm/ProfileData/InstrProf.h"15#include "llvm/ADT/ArrayRef.h"16#include "llvm/ADT/SmallVector.h"17#include "llvm/ADT/StringExtras.h"18#include "llvm/ADT/StringRef.h"19#include "llvm/Config/config.h"20#include "llvm/IR/Constant.h"21#include "llvm/IR/Constants.h"22#include "llvm/IR/Function.h"23#include "llvm/IR/GlobalValue.h"24#include "llvm/IR/GlobalVariable.h"25#include "llvm/IR/Instruction.h"26#include "llvm/IR/LLVMContext.h"27#include "llvm/IR/MDBuilder.h"28#include "llvm/IR/Metadata.h"29#include "llvm/IR/Module.h"30#include "llvm/IR/ProfDataUtils.h"31#include "llvm/IR/Type.h"32#include "llvm/ProfileData/InstrProfReader.h"33#include "llvm/Support/Casting.h"34#include "llvm/Support/CommandLine.h"35#include "llvm/Support/Compiler.h"36#include "llvm/Support/Compression.h"37#include "llvm/Support/Debug.h"38#include "llvm/Support/Endian.h"39#include "llvm/Support/Error.h"40#include "llvm/Support/ErrorHandling.h"41#include "llvm/Support/LEB128.h"42#include "llvm/Support/MathExtras.h"43#include "llvm/Support/Path.h"44#include "llvm/Support/SwapByteOrder.h"45#include "llvm/Support/VirtualFileSystem.h"46#include "llvm/Support/raw_ostream.h"47#include "llvm/TargetParser/Triple.h"48#include <algorithm>49#include <cassert>50#include <cstddef>51#include <cstdint>52#include <cstring>53#include <memory>54#include <string>55#include <system_error>56#include <type_traits>57#include <utility>58#include <vector>59 60using namespace llvm;61 62#define DEBUG_TYPE "instrprof"63 64static cl::opt<bool> StaticFuncFullModulePrefix(65 "static-func-full-module-prefix", cl::init(true), cl::Hidden,66 cl::desc("Use full module build paths in the profile counter names for "67 "static functions."));68 69// This option is tailored to users that have different top-level directory in70// profile-gen and profile-use compilation. Users need to specific the number71// of levels to strip. A value larger than the number of directories in the72// source file will strip all the directory names and only leave the basename.73//74// Note current ThinLTO module importing for the indirect-calls assumes75// the source directory name not being stripped. A non-zero option value here76// can potentially prevent some inter-module indirect-call-promotions.77static cl::opt<unsigned> StaticFuncStripDirNamePrefix(78 "static-func-strip-dirname-prefix", cl::init(0), cl::Hidden,79 cl::desc("Strip specified level of directory name from source path in "80 "the profile counter name for static functions."));81 82static std::string getInstrProfErrString(instrprof_error Err,83 const std::string &ErrMsg = "") {84 std::string Msg;85 raw_string_ostream OS(Msg);86 87 switch (Err) {88 case instrprof_error::success:89 OS << "success";90 break;91 case instrprof_error::eof:92 OS << "end of File";93 break;94 case instrprof_error::unrecognized_format:95 OS << "unrecognized instrumentation profile encoding format";96 break;97 case instrprof_error::bad_magic:98 OS << "invalid instrumentation profile data (bad magic)";99 break;100 case instrprof_error::bad_header:101 OS << "invalid instrumentation profile data (file header is corrupt)";102 break;103 case instrprof_error::unsupported_version:104 OS << "unsupported instrumentation profile format version";105 break;106 case instrprof_error::unsupported_hash_type:107 OS << "unsupported instrumentation profile hash type";108 break;109 case instrprof_error::too_large:110 OS << "too much profile data";111 break;112 case instrprof_error::truncated:113 OS << "truncated profile data";114 break;115 case instrprof_error::malformed:116 OS << "malformed instrumentation profile data";117 break;118 case instrprof_error::missing_correlation_info:119 OS << "debug info/binary for correlation is required";120 break;121 case instrprof_error::unexpected_correlation_info:122 OS << "debug info/binary for correlation is not necessary";123 break;124 case instrprof_error::unable_to_correlate_profile:125 OS << "unable to correlate profile";126 break;127 case instrprof_error::invalid_prof:128 OS << "invalid profile created. Please file a bug "129 "at: " BUG_REPORT_URL130 " and include the profraw files that caused this error.";131 break;132 case instrprof_error::unknown_function:133 OS << "no profile data available for function";134 break;135 case instrprof_error::hash_mismatch:136 OS << "function control flow change detected (hash mismatch)";137 break;138 case instrprof_error::count_mismatch:139 OS << "function basic block count change detected (counter mismatch)";140 break;141 case instrprof_error::bitmap_mismatch:142 OS << "function bitmap size change detected (bitmap size mismatch)";143 break;144 case instrprof_error::counter_overflow:145 OS << "counter overflow";146 break;147 case instrprof_error::value_site_count_mismatch:148 OS << "function value site count change detected (counter mismatch)";149 break;150 case instrprof_error::compress_failed:151 OS << "failed to compress data (zlib)";152 break;153 case instrprof_error::uncompress_failed:154 OS << "failed to uncompress data (zlib)";155 break;156 case instrprof_error::empty_raw_profile:157 OS << "empty raw profile file";158 break;159 case instrprof_error::zlib_unavailable:160 OS << "profile uses zlib compression but the profile reader was built "161 "without zlib support";162 break;163 case instrprof_error::raw_profile_version_mismatch:164 OS << "raw profile version mismatch";165 break;166 case instrprof_error::counter_value_too_large:167 OS << "excessively large counter value suggests corrupted profile data";168 break;169 }170 171 // If optional error message is not empty, append it to the message.172 if (!ErrMsg.empty())173 OS << ": " << ErrMsg;174 175 return OS.str();176}177 178namespace {179 180// FIXME: This class is only here to support the transition to llvm::Error. It181// will be removed once this transition is complete. Clients should prefer to182// deal with the Error value directly, rather than converting to error_code.183class InstrProfErrorCategoryType : public std::error_category {184 const char *name() const noexcept override { return "llvm.instrprof"; }185 186 std::string message(int IE) const override {187 return getInstrProfErrString(static_cast<instrprof_error>(IE));188 }189};190 191} // end anonymous namespace192 193const std::error_category &llvm::instrprof_category() {194 static InstrProfErrorCategoryType ErrorCategory;195 return ErrorCategory;196}197 198namespace {199 200const char *InstrProfSectNameCommon[] = {201#define INSTR_PROF_SECT_ENTRY(Kind, SectNameCommon, SectNameCoff, Prefix) \202 SectNameCommon,203#include "llvm/ProfileData/InstrProfData.inc"204};205 206const char *InstrProfSectNameCoff[] = {207#define INSTR_PROF_SECT_ENTRY(Kind, SectNameCommon, SectNameCoff, Prefix) \208 SectNameCoff,209#include "llvm/ProfileData/InstrProfData.inc"210};211 212const char *InstrProfSectNamePrefix[] = {213#define INSTR_PROF_SECT_ENTRY(Kind, SectNameCommon, SectNameCoff, Prefix) \214 Prefix,215#include "llvm/ProfileData/InstrProfData.inc"216};217 218} // namespace219 220namespace llvm {221 222cl::opt<bool> DoInstrProfNameCompression(223 "enable-name-compression",224 cl::desc("Enable name/filename string compression"), cl::init(true));225 226cl::opt<bool> EnableVTableValueProfiling(227 "enable-vtable-value-profiling", cl::init(false),228 cl::desc("If true, the virtual table address will be instrumented to know "229 "the types of a C++ pointer. The information is used in indirect "230 "call promotion to do selective vtable-based comparison."));231 232cl::opt<bool> EnableVTableProfileUse(233 "enable-vtable-profile-use", cl::init(false),234 cl::desc("If ThinLTO and WPD is enabled and this option is true, vtable "235 "profiles will be used by ICP pass for more efficient indirect "236 "call sequence. If false, type profiles won't be used."));237 238std::string getInstrProfSectionName(InstrProfSectKind IPSK,239 Triple::ObjectFormatType OF,240 bool AddSegmentInfo) {241 std::string SectName;242 243 if (OF == Triple::MachO && AddSegmentInfo)244 SectName = InstrProfSectNamePrefix[IPSK];245 246 if (OF == Triple::COFF)247 SectName += InstrProfSectNameCoff[IPSK];248 else249 SectName += InstrProfSectNameCommon[IPSK];250 251 if (OF == Triple::MachO && IPSK == IPSK_data && AddSegmentInfo)252 SectName += ",regular,live_support";253 254 return SectName;255}256 257std::string InstrProfError::message() const {258 return getInstrProfErrString(Err, Msg);259}260 261char InstrProfError::ID = 0;262 263ProfOStream::ProfOStream(raw_fd_ostream &FD)264 : IsFDOStream(true), OS(FD), LE(FD, llvm::endianness::little) {}265 266ProfOStream::ProfOStream(raw_string_ostream &STR)267 : IsFDOStream(false), OS(STR), LE(STR, llvm::endianness::little) {}268 269uint64_t ProfOStream::tell() const { return OS.tell(); }270void ProfOStream::write(uint64_t V) { LE.write<uint64_t>(V); }271void ProfOStream::write32(uint32_t V) { LE.write<uint32_t>(V); }272void ProfOStream::writeByte(uint8_t V) { LE.write<uint8_t>(V); }273 274void ProfOStream::patch(ArrayRef<PatchItem> P) {275 using namespace support;276 277 if (IsFDOStream) {278 raw_fd_ostream &FDOStream = static_cast<raw_fd_ostream &>(OS);279 const uint64_t LastPos = FDOStream.tell();280 for (const auto &K : P) {281 FDOStream.seek(K.Pos);282 for (uint64_t Elem : K.D)283 write(Elem);284 }285 // Reset the stream to the last position after patching so that users286 // don't accidentally overwrite data. This makes it consistent with287 // the string stream below which replaces the data directly.288 FDOStream.seek(LastPos);289 } else {290 raw_string_ostream &SOStream = static_cast<raw_string_ostream &>(OS);291 std::string &Data = SOStream.str(); // with flush292 for (const auto &K : P) {293 for (int I = 0, E = K.D.size(); I != E; I++) {294 uint64_t Bytes =295 endian::byte_swap<uint64_t>(K.D[I], llvm::endianness::little);296 Data.replace(K.Pos + I * sizeof(uint64_t), sizeof(uint64_t),297 (const char *)&Bytes, sizeof(uint64_t));298 }299 }300 }301}302 303std::string getPGOFuncName(StringRef Name, GlobalValue::LinkageTypes Linkage,304 StringRef FileName,305 [[maybe_unused]] uint64_t Version) {306 // Value names may be prefixed with a binary '1' to indicate307 // that the backend should not modify the symbols due to any platform308 // naming convention. Do not include that '1' in the PGO profile name.309 if (Name[0] == '\1')310 Name = Name.substr(1);311 312 std::string NewName = std::string(Name);313 if (llvm::GlobalValue::isLocalLinkage(Linkage)) {314 // For local symbols, prepend the main file name to distinguish them.315 // Do not include the full path in the file name since there's no guarantee316 // that it will stay the same, e.g., if the files are checked out from317 // version control in different locations.318 if (FileName.empty())319 NewName = NewName.insert(0, "<unknown>:");320 else321 NewName = NewName.insert(0, FileName.str() + ":");322 }323 return NewName;324}325 326// Strip NumPrefix level of directory name from PathNameStr. If the number of327// directory separators is less than NumPrefix, strip all the directories and328// leave base file name only.329static StringRef stripDirPrefix(StringRef PathNameStr, uint32_t NumPrefix) {330 uint32_t Count = NumPrefix;331 uint32_t Pos = 0, LastPos = 0;332 for (const auto &CI : PathNameStr) {333 ++Pos;334 if (llvm::sys::path::is_separator(CI)) {335 LastPos = Pos;336 --Count;337 }338 if (Count == 0)339 break;340 }341 return PathNameStr.substr(LastPos);342}343 344static StringRef getStrippedSourceFileName(const GlobalObject &GO) {345 StringRef FileName(GO.getParent()->getSourceFileName());346 uint32_t StripLevel = StaticFuncFullModulePrefix ? 0 : (uint32_t)-1;347 if (StripLevel < StaticFuncStripDirNamePrefix)348 StripLevel = StaticFuncStripDirNamePrefix;349 if (StripLevel)350 FileName = stripDirPrefix(FileName, StripLevel);351 return FileName;352}353 354// The PGO name has the format [<filepath>;]<mangled-name> where <filepath>; is355// provided if linkage is local and is used to discriminate possibly identical356// mangled names. ";" is used because it is unlikely to be found in either357// <filepath> or <mangled-name>.358//359// Older compilers used getPGOFuncName() which has the format360// [<filepath>:]<mangled-name>. This caused trouble for Objective-C functions361// which commonly have :'s in their names. We still need to compute this name to362// lookup functions from profiles built by older compilers.363static std::string364getIRPGONameForGlobalObject(const GlobalObject &GO,365 GlobalValue::LinkageTypes Linkage,366 StringRef FileName) {367 return GlobalValue::getGlobalIdentifier(GO.getName(), Linkage, FileName);368}369 370static std::optional<std::string> lookupPGONameFromMetadata(MDNode *MD) {371 if (MD != nullptr) {372 StringRef S = cast<MDString>(MD->getOperand(0))->getString();373 return S.str();374 }375 return {};376}377 378// Returns the PGO object name. This function has some special handling379// when called in LTO optimization. The following only applies when calling in380// LTO passes (when \c InLTO is true): LTO's internalization privatizes many381// global linkage symbols. This happens after value profile annotation, but382// those internal linkage functions should not have a source prefix.383// Additionally, for ThinLTO mode, exported internal functions are promoted384// and renamed. We need to ensure that the original internal PGO name is385// used when computing the GUID that is compared against the profiled GUIDs.386// To differentiate compiler generated internal symbols from original ones,387// PGOFuncName meta data are created and attached to the original internal388// symbols in the value profile annotation step389// (PGOUseFunc::annotateIndirectCallSites). If a symbol does not have the meta390// data, its original linkage must be non-internal.391static std::string getIRPGOObjectName(const GlobalObject &GO, bool InLTO,392 MDNode *PGONameMetadata) {393 if (!InLTO) {394 auto FileName = getStrippedSourceFileName(GO);395 return getIRPGONameForGlobalObject(GO, GO.getLinkage(), FileName);396 }397 398 // In LTO mode (when InLTO is true), first check if there is a meta data.399 if (auto IRPGOFuncName = lookupPGONameFromMetadata(PGONameMetadata))400 return *IRPGOFuncName;401 402 // If there is no meta data, the function must be a global before the value403 // profile annotation pass. Its current linkage may be internal if it is404 // internalized in LTO mode.405 return getIRPGONameForGlobalObject(GO, GlobalValue::ExternalLinkage, "");406}407 408// Returns the IRPGO function name and does special handling when called409// in LTO optimization. See the comments of `getIRPGOObjectName` for details.410std::string getIRPGOFuncName(const Function &F, bool InLTO) {411 return getIRPGOObjectName(F, InLTO, getPGOFuncNameMetadata(F));412}413 414// Please use getIRPGOFuncName for LLVM IR instrumentation. This function is415// for front-end (Clang, etc) instrumentation.416// The implementation is kept for profile matching from older profiles.417// This is similar to `getIRPGOFuncName` except that this function calls418// 'getPGOFuncName' to get a name and `getIRPGOFuncName` calls419// 'getIRPGONameForGlobalObject'. See the difference between two callees in the420// comments of `getIRPGONameForGlobalObject`.421std::string getPGOFuncName(const Function &F, bool InLTO, uint64_t Version) {422 if (!InLTO) {423 auto FileName = getStrippedSourceFileName(F);424 return getPGOFuncName(F.getName(), F.getLinkage(), FileName, Version);425 }426 427 // In LTO mode (when InLTO is true), first check if there is a meta data.428 if (auto PGOFuncName = lookupPGONameFromMetadata(getPGOFuncNameMetadata(F)))429 return *PGOFuncName;430 431 // If there is no meta data, the function must be a global before the value432 // profile annotation pass. Its current linkage may be internal if it is433 // internalized in LTO mode.434 return getPGOFuncName(F.getName(), GlobalValue::ExternalLinkage, "");435}436 437std::string getPGOName(const GlobalVariable &V, bool InLTO) {438 // PGONameMetadata should be set by compiler at profile use time439 // and read by symtab creation to look up symbols corresponding to440 // a MD5 hash.441 return getIRPGOObjectName(V, InLTO, V.getMetadata(getPGONameMetadataName()));442}443 444// See getIRPGOObjectName() for a discription of the format.445std::pair<StringRef, StringRef> getParsedIRPGOName(StringRef IRPGOName) {446 auto [FileName, MangledName] = IRPGOName.split(GlobalIdentifierDelimiter);447 if (MangledName.empty())448 return std::make_pair(StringRef(), IRPGOName);449 return std::make_pair(FileName, MangledName);450}451 452StringRef getFuncNameWithoutPrefix(StringRef PGOFuncName, StringRef FileName) {453 if (FileName.empty())454 return PGOFuncName;455 // Drop the file name including ':' or ';'. See getIRPGONameForGlobalObject as456 // well.457 if (PGOFuncName.starts_with(FileName))458 PGOFuncName = PGOFuncName.drop_front(FileName.size() + 1);459 return PGOFuncName;460}461 462// \p FuncName is the string used as profile lookup key for the function. A463// symbol is created to hold the name. Return the legalized symbol name.464std::string getPGOFuncNameVarName(StringRef FuncName,465 GlobalValue::LinkageTypes Linkage) {466 std::string VarName = std::string(getInstrProfNameVarPrefix());467 VarName += FuncName;468 469 if (!GlobalValue::isLocalLinkage(Linkage))470 return VarName;471 472 // Now fix up illegal chars in local VarName that may upset the assembler.473 const char InvalidChars[] = "-:;<>/\"'";474 size_t FoundPos = VarName.find_first_of(InvalidChars);475 while (FoundPos != std::string::npos) {476 VarName[FoundPos] = '_';477 FoundPos = VarName.find_first_of(InvalidChars, FoundPos + 1);478 }479 return VarName;480}481 482bool isGPUProfTarget(const Module &M) {483 const Triple &T = M.getTargetTriple();484 return T.isGPU();485}486 487void setPGOFuncVisibility(Module &M, GlobalVariable *FuncNameVar) {488 // If the target is a GPU, make the symbol protected so it can489 // be read from the host device490 if (isGPUProfTarget(M))491 FuncNameVar->setVisibility(GlobalValue::ProtectedVisibility);492 // Hide the symbol so that we correctly get a copy for each executable.493 else if (!GlobalValue::isLocalLinkage(FuncNameVar->getLinkage()))494 FuncNameVar->setVisibility(GlobalValue::HiddenVisibility);495}496 497GlobalVariable *createPGOFuncNameVar(Module &M,498 GlobalValue::LinkageTypes Linkage,499 StringRef PGOFuncName) {500 // Ensure profiling variables on GPU are visible to be read from host501 if (isGPUProfTarget(M))502 Linkage = GlobalValue::ExternalLinkage;503 // We generally want to match the function's linkage, but available_externally504 // and extern_weak both have the wrong semantics, and anything that doesn't505 // need to link across compilation units doesn't need to be visible at all.506 else if (Linkage == GlobalValue::ExternalWeakLinkage)507 Linkage = GlobalValue::LinkOnceAnyLinkage;508 else if (Linkage == GlobalValue::AvailableExternallyLinkage)509 Linkage = GlobalValue::LinkOnceODRLinkage;510 else if (Linkage == GlobalValue::InternalLinkage ||511 Linkage == GlobalValue::ExternalLinkage)512 Linkage = GlobalValue::PrivateLinkage;513 514 auto *Value =515 ConstantDataArray::getString(M.getContext(), PGOFuncName, false);516 auto *FuncNameVar =517 new GlobalVariable(M, Value->getType(), true, Linkage, Value,518 getPGOFuncNameVarName(PGOFuncName, Linkage));519 520 setPGOFuncVisibility(M, FuncNameVar);521 return FuncNameVar;522}523 524GlobalVariable *createPGOFuncNameVar(Function &F, StringRef PGOFuncName) {525 return createPGOFuncNameVar(*F.getParent(), F.getLinkage(), PGOFuncName);526}527 528Error InstrProfSymtab::create(Module &M, bool InLTO, bool AddCanonical) {529 for (Function &F : M) {530 // Function may not have a name: like using asm("") to overwrite the name.531 // Ignore in this case.532 if (!F.hasName())533 continue;534 if (Error E = addFuncWithName(F, getIRPGOFuncName(F, InLTO), AddCanonical))535 return E;536 // Also use getPGOFuncName() so that we can find records from older profiles537 if (Error E = addFuncWithName(F, getPGOFuncName(F, InLTO), AddCanonical))538 return E;539 }540 541 for (GlobalVariable &G : M.globals()) {542 if (!G.hasName() || !G.hasMetadata(LLVMContext::MD_type))543 continue;544 if (Error E = addVTableWithName(G, getPGOName(G, InLTO)))545 return E;546 }547 548 Sorted = false;549 finalizeSymtab();550 return Error::success();551}552 553Error InstrProfSymtab::addVTableWithName(GlobalVariable &VTable,554 StringRef VTablePGOName) {555 auto NameToGUIDMap = [&](StringRef Name) -> Error {556 if (Error E = addSymbolName(Name))557 return E;558 559 bool Inserted = true;560 std::tie(std::ignore, Inserted) = MD5VTableMap.try_emplace(561 GlobalValue::getGUIDAssumingExternalLinkage(Name), &VTable);562 if (!Inserted)563 LLVM_DEBUG(dbgs() << "GUID conflict within one module");564 return Error::success();565 };566 if (Error E = NameToGUIDMap(VTablePGOName))567 return E;568 569 StringRef CanonicalName = getCanonicalName(VTablePGOName);570 if (CanonicalName != VTablePGOName)571 return NameToGUIDMap(CanonicalName);572 573 return Error::success();574}575 576Error readAndDecodeStrings(StringRef NameStrings,577 std::function<Error(StringRef)> NameCallback) {578 const uint8_t *P = NameStrings.bytes_begin();579 const uint8_t *EndP = NameStrings.bytes_end();580 while (P < EndP) {581 uint32_t N;582 uint64_t UncompressedSize = decodeULEB128(P, &N);583 P += N;584 uint64_t CompressedSize = decodeULEB128(P, &N);585 P += N;586 const bool IsCompressed = (CompressedSize != 0);587 SmallVector<uint8_t, 128> UncompressedNameStrings;588 StringRef NameStrings;589 if (IsCompressed) {590 if (!llvm::compression::zlib::isAvailable())591 return make_error<InstrProfError>(instrprof_error::zlib_unavailable);592 593 if (Error E = compression::zlib::decompress(ArrayRef(P, CompressedSize),594 UncompressedNameStrings,595 UncompressedSize)) {596 consumeError(std::move(E));597 return make_error<InstrProfError>(instrprof_error::uncompress_failed);598 }599 P += CompressedSize;600 NameStrings = toStringRef(UncompressedNameStrings);601 } else {602 NameStrings =603 StringRef(reinterpret_cast<const char *>(P), UncompressedSize);604 P += UncompressedSize;605 }606 // Now parse the name strings.607 SmallVector<StringRef, 0> Names;608 NameStrings.split(Names, getInstrProfNameSeparator());609 for (StringRef &Name : Names)610 if (Error E = NameCallback(Name))611 return E;612 613 while (P < EndP && *P == 0)614 P++;615 }616 return Error::success();617}618 619Error InstrProfSymtab::create(StringRef NameStrings) {620 return readAndDecodeStrings(NameStrings,621 [&](StringRef S) { return addFuncName(S); });622}623 624Error InstrProfSymtab::create(StringRef FuncNameStrings,625 StringRef VTableNameStrings) {626 if (Error E = readAndDecodeStrings(627 FuncNameStrings, [&](StringRef S) { return addFuncName(S); }))628 return E;629 630 return readAndDecodeStrings(VTableNameStrings,631 [&](StringRef S) { return addVTableName(S); });632}633 634Error InstrProfSymtab::initVTableNamesFromCompressedStrings(635 StringRef CompressedVTableStrings) {636 return readAndDecodeStrings(CompressedVTableStrings,637 [&](StringRef S) { return addVTableName(S); });638}639 640StringRef InstrProfSymtab::getCanonicalName(StringRef PGOName) {641 // In ThinLTO, local function may have been promoted to global and have642 // suffix ".llvm." added to the function name. We need to add the643 // stripped function name to the symbol table so that we can find a match644 // from profile.645 //646 // ".__uniq." suffix is used to differentiate internal linkage functions in647 // different modules and should be kept. This is the only suffix with the648 // pattern ".xxx" which is kept before matching, other suffixes similar as649 // ".llvm." will be stripped.650 const std::string UniqSuffix = ".__uniq.";651 size_t Pos = PGOName.find(UniqSuffix);652 if (Pos != StringRef::npos)653 Pos += UniqSuffix.length();654 else655 Pos = 0;656 657 // Search '.' after ".__uniq." if ".__uniq." exists, otherwise search '.' from658 // the beginning.659 Pos = PGOName.find('.', Pos);660 if (Pos != StringRef::npos && Pos != 0)661 return PGOName.substr(0, Pos);662 663 return PGOName;664}665 666Error InstrProfSymtab::addFuncWithName(Function &F, StringRef PGOFuncName,667 bool AddCanonical) {668 auto NameToGUIDMap = [&](StringRef Name) -> Error {669 if (Error E = addFuncName(Name))670 return E;671 MD5FuncMap.emplace_back(Function::getGUIDAssumingExternalLinkage(Name), &F);672 return Error::success();673 };674 if (Error E = NameToGUIDMap(PGOFuncName))675 return E;676 677 if (!AddCanonical)678 return Error::success();679 680 StringRef CanonicalFuncName = getCanonicalName(PGOFuncName);681 if (CanonicalFuncName != PGOFuncName)682 return NameToGUIDMap(CanonicalFuncName);683 684 return Error::success();685}686 687uint64_t InstrProfSymtab::getVTableHashFromAddress(uint64_t Address) const {688 // Given a runtime address, look up the hash value in the interval map, and689 // fallback to value 0 if a hash value is not found.690 return VTableAddrMap.lookup(Address, 0);691}692 693uint64_t InstrProfSymtab::getFunctionHashFromAddress(uint64_t Address) const {694 finalizeSymtab();695 auto It = partition_point(AddrToMD5Map, [=](std::pair<uint64_t, uint64_t> A) {696 return A.first < Address;697 });698 // Raw function pointer collected by value profiler may be from699 // external functions that are not instrumented. They won't have700 // mapping data to be used by the deserializer. Force the value to701 // be 0 in this case.702 if (It != AddrToMD5Map.end() && It->first == Address)703 return (uint64_t)It->second;704 return 0;705}706 707void InstrProfSymtab::dumpNames(raw_ostream &OS) const {708 SmallVector<StringRef, 0> Sorted(NameTab.keys());709 llvm::sort(Sorted);710 for (StringRef S : Sorted)711 OS << S << '\n';712}713 714Error collectGlobalObjectNameStrings(ArrayRef<std::string> NameStrs,715 bool DoCompression, std::string &Result) {716 assert(!NameStrs.empty() && "No name data to emit");717 718 uint8_t Header[20], *P = Header;719 std::string UncompressedNameStrings =720 join(NameStrs.begin(), NameStrs.end(), getInstrProfNameSeparator());721 722 assert(StringRef(UncompressedNameStrings)723 .count(getInstrProfNameSeparator()) == (NameStrs.size() - 1) &&724 "PGO name is invalid (contains separator token)");725 726 unsigned EncLen = encodeULEB128(UncompressedNameStrings.length(), P);727 P += EncLen;728 729 auto WriteStringToResult = [&](size_t CompressedLen, StringRef InputStr) {730 EncLen = encodeULEB128(CompressedLen, P);731 P += EncLen;732 char *HeaderStr = reinterpret_cast<char *>(&Header[0]);733 unsigned HeaderLen = P - &Header[0];734 Result.append(HeaderStr, HeaderLen);735 Result += InputStr;736 return Error::success();737 };738 739 if (!DoCompression) {740 return WriteStringToResult(0, UncompressedNameStrings);741 }742 743 SmallVector<uint8_t, 128> CompressedNameStrings;744 compression::zlib::compress(arrayRefFromStringRef(UncompressedNameStrings),745 CompressedNameStrings,746 compression::zlib::BestSizeCompression);747 748 return WriteStringToResult(CompressedNameStrings.size(),749 toStringRef(CompressedNameStrings));750}751 752StringRef getPGOFuncNameVarInitializer(GlobalVariable *NameVar) {753 auto *Arr = cast<ConstantDataArray>(NameVar->getInitializer());754 StringRef NameStr =755 Arr->isCString() ? Arr->getAsCString() : Arr->getAsString();756 return NameStr;757}758 759Error collectPGOFuncNameStrings(ArrayRef<GlobalVariable *> NameVars,760 std::string &Result, bool DoCompression) {761 std::vector<std::string> NameStrs;762 for (auto *NameVar : NameVars) {763 NameStrs.push_back(std::string(getPGOFuncNameVarInitializer(NameVar)));764 }765 return collectGlobalObjectNameStrings(766 NameStrs, compression::zlib::isAvailable() && DoCompression, Result);767}768 769Error collectVTableStrings(ArrayRef<GlobalVariable *> VTables,770 std::string &Result, bool DoCompression) {771 std::vector<std::string> VTableNameStrs;772 for (auto *VTable : VTables)773 VTableNameStrs.push_back(getPGOName(*VTable));774 return collectGlobalObjectNameStrings(775 VTableNameStrs, compression::zlib::isAvailable() && DoCompression,776 Result);777}778 779void InstrProfRecord::accumulateCounts(CountSumOrPercent &Sum) const {780 uint64_t FuncSum = 0;781 Sum.NumEntries += Counts.size();782 for (uint64_t Count : Counts)783 FuncSum += Count;784 Sum.CountSum += FuncSum;785 786 for (uint32_t VK = IPVK_First; VK <= IPVK_Last; ++VK) {787 uint64_t KindSum = 0;788 uint32_t NumValueSites = getNumValueSites(VK);789 for (size_t I = 0; I < NumValueSites; ++I) {790 for (const auto &V : getValueArrayForSite(VK, I))791 KindSum += V.Count;792 }793 Sum.ValueCounts[VK] += KindSum;794 }795}796 797void InstrProfValueSiteRecord::overlap(InstrProfValueSiteRecord &Input,798 uint32_t ValueKind,799 OverlapStats &Overlap,800 OverlapStats &FuncLevelOverlap) {801 this->sortByTargetValues();802 Input.sortByTargetValues();803 double Score = 0.0f, FuncLevelScore = 0.0f;804 auto I = ValueData.begin();805 auto IE = ValueData.end();806 auto J = Input.ValueData.begin();807 auto JE = Input.ValueData.end();808 while (I != IE && J != JE) {809 if (I->Value == J->Value) {810 Score += OverlapStats::score(I->Count, J->Count,811 Overlap.Base.ValueCounts[ValueKind],812 Overlap.Test.ValueCounts[ValueKind]);813 FuncLevelScore += OverlapStats::score(814 I->Count, J->Count, FuncLevelOverlap.Base.ValueCounts[ValueKind],815 FuncLevelOverlap.Test.ValueCounts[ValueKind]);816 ++I;817 } else if (I->Value < J->Value) {818 ++I;819 continue;820 }821 ++J;822 }823 Overlap.Overlap.ValueCounts[ValueKind] += Score;824 FuncLevelOverlap.Overlap.ValueCounts[ValueKind] += FuncLevelScore;825}826 827// Return false on mismatch.828void InstrProfRecord::overlapValueProfData(uint32_t ValueKind,829 InstrProfRecord &Other,830 OverlapStats &Overlap,831 OverlapStats &FuncLevelOverlap) {832 uint32_t ThisNumValueSites = getNumValueSites(ValueKind);833 assert(ThisNumValueSites == Other.getNumValueSites(ValueKind));834 if (!ThisNumValueSites)835 return;836 837 std::vector<InstrProfValueSiteRecord> &ThisSiteRecords =838 getOrCreateValueSitesForKind(ValueKind);839 MutableArrayRef<InstrProfValueSiteRecord> OtherSiteRecords =840 Other.getValueSitesForKind(ValueKind);841 for (uint32_t I = 0; I < ThisNumValueSites; I++)842 ThisSiteRecords[I].overlap(OtherSiteRecords[I], ValueKind, Overlap,843 FuncLevelOverlap);844}845 846void InstrProfRecord::overlap(InstrProfRecord &Other, OverlapStats &Overlap,847 OverlapStats &FuncLevelOverlap,848 uint64_t ValueCutoff) {849 // FuncLevel CountSum for other should already computed and nonzero.850 assert(FuncLevelOverlap.Test.CountSum >= 1.0f);851 accumulateCounts(FuncLevelOverlap.Base);852 bool Mismatch = (Counts.size() != Other.Counts.size());853 854 // Check if the value profiles mismatch.855 if (!Mismatch) {856 for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind) {857 uint32_t ThisNumValueSites = getNumValueSites(Kind);858 uint32_t OtherNumValueSites = Other.getNumValueSites(Kind);859 if (ThisNumValueSites != OtherNumValueSites) {860 Mismatch = true;861 break;862 }863 }864 }865 if (Mismatch) {866 Overlap.addOneMismatch(FuncLevelOverlap.Test);867 return;868 }869 870 // Compute overlap for value counts.871 for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)872 overlapValueProfData(Kind, Other, Overlap, FuncLevelOverlap);873 874 double Score = 0.0;875 uint64_t MaxCount = 0;876 // Compute overlap for edge counts.877 for (size_t I = 0, E = Other.Counts.size(); I < E; ++I) {878 Score += OverlapStats::score(Counts[I], Other.Counts[I],879 Overlap.Base.CountSum, Overlap.Test.CountSum);880 MaxCount = std::max(Other.Counts[I], MaxCount);881 }882 Overlap.Overlap.CountSum += Score;883 Overlap.Overlap.NumEntries += 1;884 885 if (MaxCount >= ValueCutoff) {886 double FuncScore = 0.0;887 for (size_t I = 0, E = Other.Counts.size(); I < E; ++I)888 FuncScore += OverlapStats::score(Counts[I], Other.Counts[I],889 FuncLevelOverlap.Base.CountSum,890 FuncLevelOverlap.Test.CountSum);891 FuncLevelOverlap.Overlap.CountSum = FuncScore;892 FuncLevelOverlap.Overlap.NumEntries = Other.Counts.size();893 FuncLevelOverlap.Valid = true;894 }895}896 897void InstrProfValueSiteRecord::merge(InstrProfValueSiteRecord &Input,898 uint64_t Weight,899 function_ref<void(instrprof_error)> Warn) {900 this->sortByTargetValues();901 Input.sortByTargetValues();902 auto I = ValueData.begin();903 auto IE = ValueData.end();904 std::vector<InstrProfValueData> Merged;905 Merged.reserve(std::max(ValueData.size(), Input.ValueData.size()));906 for (const InstrProfValueData &J : Input.ValueData) {907 while (I != IE && I->Value < J.Value) {908 Merged.push_back(*I);909 ++I;910 }911 if (I != IE && I->Value == J.Value) {912 bool Overflowed;913 I->Count = SaturatingMultiplyAdd(J.Count, Weight, I->Count, &Overflowed);914 if (Overflowed)915 Warn(instrprof_error::counter_overflow);916 Merged.push_back(*I);917 ++I;918 continue;919 }920 Merged.push_back(J);921 }922 Merged.insert(Merged.end(), I, IE);923 ValueData = std::move(Merged);924}925 926void InstrProfValueSiteRecord::scale(uint64_t N, uint64_t D,927 function_ref<void(instrprof_error)> Warn) {928 for (InstrProfValueData &I : ValueData) {929 bool Overflowed;930 I.Count = SaturatingMultiply(I.Count, N, &Overflowed) / D;931 if (Overflowed)932 Warn(instrprof_error::counter_overflow);933 }934}935 936// Merge Value Profile data from Src record to this record for ValueKind.937// Scale merged value counts by \p Weight.938void InstrProfRecord::mergeValueProfData(939 uint32_t ValueKind, InstrProfRecord &Src, uint64_t Weight,940 function_ref<void(instrprof_error)> Warn) {941 uint32_t ThisNumValueSites = getNumValueSites(ValueKind);942 uint32_t OtherNumValueSites = Src.getNumValueSites(ValueKind);943 if (ThisNumValueSites != OtherNumValueSites) {944 Warn(instrprof_error::value_site_count_mismatch);945 return;946 }947 if (!ThisNumValueSites)948 return;949 std::vector<InstrProfValueSiteRecord> &ThisSiteRecords =950 getOrCreateValueSitesForKind(ValueKind);951 MutableArrayRef<InstrProfValueSiteRecord> OtherSiteRecords =952 Src.getValueSitesForKind(ValueKind);953 for (uint32_t I = 0; I < ThisNumValueSites; I++)954 ThisSiteRecords[I].merge(OtherSiteRecords[I], Weight, Warn);955}956 957void InstrProfRecord::merge(InstrProfRecord &Other, uint64_t Weight,958 function_ref<void(instrprof_error)> Warn) {959 // If the number of counters doesn't match we either have bad data960 // or a hash collision.961 if (Counts.size() != Other.Counts.size()) {962 Warn(instrprof_error::count_mismatch);963 return;964 }965 966 // Special handling of the first count as the PseudoCount.967 CountPseudoKind OtherKind = Other.getCountPseudoKind();968 CountPseudoKind ThisKind = getCountPseudoKind();969 if (OtherKind != NotPseudo || ThisKind != NotPseudo) {970 // We don't allow the merge of a profile with pseudo counts and971 // a normal profile (i.e. without pesudo counts).972 // Profile supplimenation should be done after the profile merge.973 if (OtherKind == NotPseudo || ThisKind == NotPseudo) {974 Warn(instrprof_error::count_mismatch);975 return;976 }977 if (OtherKind == PseudoHot || ThisKind == PseudoHot)978 setPseudoCount(PseudoHot);979 else980 setPseudoCount(PseudoWarm);981 return;982 }983 984 for (size_t I = 0, E = Other.Counts.size(); I < E; ++I) {985 bool Overflowed;986 uint64_t Value =987 SaturatingMultiplyAdd(Other.Counts[I], Weight, Counts[I], &Overflowed);988 if (Value > getInstrMaxCountValue()) {989 Value = getInstrMaxCountValue();990 Overflowed = true;991 }992 Counts[I] = Value;993 if (Overflowed)994 Warn(instrprof_error::counter_overflow);995 }996 997 // If the number of bitmap bytes doesn't match we either have bad data998 // or a hash collision.999 if (BitmapBytes.size() != Other.BitmapBytes.size()) {1000 Warn(instrprof_error::bitmap_mismatch);1001 return;1002 }1003 1004 // Bitmap bytes are merged by simply ORing them together.1005 for (size_t I = 0, E = Other.BitmapBytes.size(); I < E; ++I) {1006 BitmapBytes[I] = Other.BitmapBytes[I] | BitmapBytes[I];1007 }1008 1009 for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)1010 mergeValueProfData(Kind, Other, Weight, Warn);1011}1012 1013void InstrProfRecord::scaleValueProfData(1014 uint32_t ValueKind, uint64_t N, uint64_t D,1015 function_ref<void(instrprof_error)> Warn) {1016 for (auto &R : getValueSitesForKind(ValueKind))1017 R.scale(N, D, Warn);1018}1019 1020void InstrProfRecord::scale(uint64_t N, uint64_t D,1021 function_ref<void(instrprof_error)> Warn) {1022 assert(D != 0 && "D cannot be 0");1023 for (auto &Count : this->Counts) {1024 bool Overflowed;1025 Count = SaturatingMultiply(Count, N, &Overflowed) / D;1026 if (Count > getInstrMaxCountValue()) {1027 Count = getInstrMaxCountValue();1028 Overflowed = true;1029 }1030 if (Overflowed)1031 Warn(instrprof_error::counter_overflow);1032 }1033 for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)1034 scaleValueProfData(Kind, N, D, Warn);1035}1036 1037// Map indirect call target name hash to name string.1038uint64_t InstrProfRecord::remapValue(uint64_t Value, uint32_t ValueKind,1039 InstrProfSymtab *SymTab) {1040 if (!SymTab)1041 return Value;1042 1043 if (ValueKind == IPVK_IndirectCallTarget)1044 return SymTab->getFunctionHashFromAddress(Value);1045 1046 if (ValueKind == IPVK_VTableTarget)1047 return SymTab->getVTableHashFromAddress(Value);1048 1049 return Value;1050}1051 1052void InstrProfRecord::addValueData(uint32_t ValueKind, uint32_t Site,1053 ArrayRef<InstrProfValueData> VData,1054 InstrProfSymtab *ValueMap) {1055 // Remap values.1056 std::vector<InstrProfValueData> RemappedVD;1057 RemappedVD.reserve(VData.size());1058 for (const auto &V : VData) {1059 uint64_t NewValue = remapValue(V.Value, ValueKind, ValueMap);1060 RemappedVD.push_back({NewValue, V.Count});1061 }1062 1063 std::vector<InstrProfValueSiteRecord> &ValueSites =1064 getOrCreateValueSitesForKind(ValueKind);1065 assert(ValueSites.size() == Site);1066 1067 // Add a new value site with remapped value profiling data.1068 ValueSites.emplace_back(std::move(RemappedVD));1069}1070 1071void TemporalProfTraceTy::createBPFunctionNodes(1072 ArrayRef<TemporalProfTraceTy> Traces, std::vector<BPFunctionNode> &Nodes,1073 bool RemoveOutlierUNs) {1074 using IDT = BPFunctionNode::IDT;1075 using UtilityNodeT = BPFunctionNode::UtilityNodeT;1076 UtilityNodeT MaxUN = 0;1077 DenseMap<IDT, size_t> IdToFirstTimestamp;1078 DenseMap<IDT, UtilityNodeT> IdToFirstUN;1079 DenseMap<IDT, SmallVector<UtilityNodeT>> IdToUNs;1080 // TODO: We need to use the Trace.Weight field to give more weight to more1081 // important utilities1082 for (auto &Trace : Traces) {1083 size_t CutoffTimestamp = 1;1084 for (size_t Timestamp = 0; Timestamp < Trace.FunctionNameRefs.size();1085 Timestamp++) {1086 IDT Id = Trace.FunctionNameRefs[Timestamp];1087 auto [It, WasInserted] = IdToFirstTimestamp.try_emplace(Id, Timestamp);1088 if (!WasInserted)1089 It->getSecond() = std::min<size_t>(It->getSecond(), Timestamp);1090 if (Timestamp >= CutoffTimestamp) {1091 ++MaxUN;1092 CutoffTimestamp = 2 * Timestamp;1093 }1094 IdToFirstUN.try_emplace(Id, MaxUN);1095 }1096 for (auto &[Id, FirstUN] : IdToFirstUN)1097 for (auto UN = FirstUN; UN <= MaxUN; ++UN)1098 IdToUNs[Id].push_back(UN);1099 ++MaxUN;1100 IdToFirstUN.clear();1101 }1102 1103 if (RemoveOutlierUNs) {1104 DenseMap<UtilityNodeT, unsigned> UNFrequency;1105 for (auto &[Id, UNs] : IdToUNs)1106 for (auto &UN : UNs)1107 ++UNFrequency[UN];1108 // Filter out utility nodes that are too infrequent or too prevalent to make1109 // BalancedPartitioning more effective.1110 for (auto &[Id, UNs] : IdToUNs)1111 llvm::erase_if(UNs, [&](auto &UN) {1112 unsigned Freq = UNFrequency[UN];1113 return Freq <= 1 || 2 * Freq > IdToUNs.size();1114 });1115 }1116 1117 for (auto &[Id, UNs] : IdToUNs)1118 Nodes.emplace_back(Id, UNs);1119 1120 // Since BalancedPartitioning is sensitive to the initial order, we explicitly1121 // order nodes by their earliest timestamp.1122 llvm::sort(Nodes, [&](auto &L, auto &R) {1123 return std::make_pair(IdToFirstTimestamp[L.Id], L.Id) <1124 std::make_pair(IdToFirstTimestamp[R.Id], R.Id);1125 });1126}1127 1128#define INSTR_PROF_COMMON_API_IMPL1129#include "llvm/ProfileData/InstrProfData.inc"1130 1131/*!1132 * ValueProfRecordClosure Interface implementation for InstrProfRecord1133 * class. These C wrappers are used as adaptors so that C++ code can be1134 * invoked as callbacks.1135 */1136uint32_t getNumValueKindsInstrProf(const void *Record) {1137 return reinterpret_cast<const InstrProfRecord *>(Record)->getNumValueKinds();1138}1139 1140uint32_t getNumValueSitesInstrProf(const void *Record, uint32_t VKind) {1141 return reinterpret_cast<const InstrProfRecord *>(Record)1142 ->getNumValueSites(VKind);1143}1144 1145uint32_t getNumValueDataInstrProf(const void *Record, uint32_t VKind) {1146 return reinterpret_cast<const InstrProfRecord *>(Record)1147 ->getNumValueData(VKind);1148}1149 1150uint32_t getNumValueDataForSiteInstrProf(const void *R, uint32_t VK,1151 uint32_t S) {1152 const auto *IPR = reinterpret_cast<const InstrProfRecord *>(R);1153 return IPR->getValueArrayForSite(VK, S).size();1154}1155 1156void getValueForSiteInstrProf(const void *R, InstrProfValueData *Dst,1157 uint32_t K, uint32_t S) {1158 const auto *IPR = reinterpret_cast<const InstrProfRecord *>(R);1159 llvm::copy(IPR->getValueArrayForSite(K, S), Dst);1160}1161 1162ValueProfData *allocValueProfDataInstrProf(size_t TotalSizeInBytes) {1163 ValueProfData *VD = new (::operator new(TotalSizeInBytes)) ValueProfData();1164 memset(VD, 0, TotalSizeInBytes);1165 return VD;1166}1167 1168static ValueProfRecordClosure InstrProfRecordClosure = {1169 nullptr,1170 getNumValueKindsInstrProf,1171 getNumValueSitesInstrProf,1172 getNumValueDataInstrProf,1173 getNumValueDataForSiteInstrProf,1174 nullptr,1175 getValueForSiteInstrProf,1176 allocValueProfDataInstrProf};1177 1178// Wrapper implementation using the closure mechanism.1179uint32_t ValueProfData::getSize(const InstrProfRecord &Record) {1180 auto Closure = InstrProfRecordClosure;1181 Closure.Record = &Record;1182 return getValueProfDataSize(&Closure);1183}1184 1185// Wrapper implementation using the closure mechanism.1186std::unique_ptr<ValueProfData>1187ValueProfData::serializeFrom(const InstrProfRecord &Record) {1188 InstrProfRecordClosure.Record = &Record;1189 1190 std::unique_ptr<ValueProfData> VPD(1191 serializeValueProfDataFrom(&InstrProfRecordClosure, nullptr));1192 return VPD;1193}1194 1195void ValueProfRecord::deserializeTo(InstrProfRecord &Record,1196 InstrProfSymtab *SymTab) {1197 Record.reserveSites(Kind, NumValueSites);1198 1199 InstrProfValueData *ValueData = getValueProfRecordValueData(this);1200 for (uint64_t VSite = 0; VSite < NumValueSites; ++VSite) {1201 uint8_t ValueDataCount = this->SiteCountArray[VSite];1202 ArrayRef<InstrProfValueData> VDs(ValueData, ValueDataCount);1203 Record.addValueData(Kind, VSite, VDs, SymTab);1204 ValueData += ValueDataCount;1205 }1206}1207 1208// For writing/serializing, Old is the host endianness, and New is1209// byte order intended on disk. For Reading/deserialization, Old1210// is the on-disk source endianness, and New is the host endianness.1211void ValueProfRecord::swapBytes(llvm::endianness Old, llvm::endianness New) {1212 using namespace support;1213 1214 if (Old == New)1215 return;1216 1217 if (llvm::endianness::native != Old) {1218 sys::swapByteOrder<uint32_t>(NumValueSites);1219 sys::swapByteOrder<uint32_t>(Kind);1220 }1221 uint32_t ND = getValueProfRecordNumValueData(this);1222 InstrProfValueData *VD = getValueProfRecordValueData(this);1223 1224 // No need to swap byte array: SiteCountArrray.1225 for (uint32_t I = 0; I < ND; I++) {1226 sys::swapByteOrder<uint64_t>(VD[I].Value);1227 sys::swapByteOrder<uint64_t>(VD[I].Count);1228 }1229 if (llvm::endianness::native == Old) {1230 sys::swapByteOrder<uint32_t>(NumValueSites);1231 sys::swapByteOrder<uint32_t>(Kind);1232 }1233}1234 1235void ValueProfData::deserializeTo(InstrProfRecord &Record,1236 InstrProfSymtab *SymTab) {1237 if (NumValueKinds == 0)1238 return;1239 1240 ValueProfRecord *VR = getFirstValueProfRecord(this);1241 for (uint32_t K = 0; K < NumValueKinds; K++) {1242 VR->deserializeTo(Record, SymTab);1243 VR = getValueProfRecordNext(VR);1244 }1245}1246 1247static std::unique_ptr<ValueProfData> allocValueProfData(uint32_t TotalSize) {1248 return std::unique_ptr<ValueProfData>(new (::operator new(TotalSize))1249 ValueProfData());1250}1251 1252Error ValueProfData::checkIntegrity() {1253 if (NumValueKinds > IPVK_Last + 1)1254 return make_error<InstrProfError>(1255 instrprof_error::malformed, "number of value profile kinds is invalid");1256 // Total size needs to be multiple of quadword size.1257 if (TotalSize % sizeof(uint64_t))1258 return make_error<InstrProfError>(1259 instrprof_error::malformed, "total size is not multiples of quardword");1260 1261 ValueProfRecord *VR = getFirstValueProfRecord(this);1262 for (uint32_t K = 0; K < this->NumValueKinds; K++) {1263 if (VR->Kind > IPVK_Last)1264 return make_error<InstrProfError>(instrprof_error::malformed,1265 "value kind is invalid");1266 VR = getValueProfRecordNext(VR);1267 if ((char *)VR - (char *)this > (ptrdiff_t)TotalSize)1268 return make_error<InstrProfError>(1269 instrprof_error::malformed,1270 "value profile address is greater than total size");1271 }1272 return Error::success();1273}1274 1275Expected<std::unique_ptr<ValueProfData>>1276ValueProfData::getValueProfData(const unsigned char *D,1277 const unsigned char *const BufferEnd,1278 llvm::endianness Endianness) {1279 using namespace support;1280 1281 if (D + sizeof(ValueProfData) > BufferEnd)1282 return make_error<InstrProfError>(instrprof_error::truncated);1283 1284 const unsigned char *Header = D;1285 uint32_t TotalSize = endian::readNext<uint32_t>(Header, Endianness);1286 1287 if (D + TotalSize > BufferEnd)1288 return make_error<InstrProfError>(instrprof_error::too_large);1289 1290 std::unique_ptr<ValueProfData> VPD = allocValueProfData(TotalSize);1291 memcpy(VPD.get(), D, TotalSize);1292 // Byte swap.1293 VPD->swapBytesToHost(Endianness);1294 1295 Error E = VPD->checkIntegrity();1296 if (E)1297 return std::move(E);1298 1299 return std::move(VPD);1300}1301 1302void ValueProfData::swapBytesToHost(llvm::endianness Endianness) {1303 using namespace support;1304 1305 if (Endianness == llvm::endianness::native)1306 return;1307 1308 sys::swapByteOrder<uint32_t>(TotalSize);1309 sys::swapByteOrder<uint32_t>(NumValueKinds);1310 1311 ValueProfRecord *VR = getFirstValueProfRecord(this);1312 for (uint32_t K = 0; K < NumValueKinds; K++) {1313 VR->swapBytes(Endianness, llvm::endianness::native);1314 VR = getValueProfRecordNext(VR);1315 }1316}1317 1318void ValueProfData::swapBytesFromHost(llvm::endianness Endianness) {1319 using namespace support;1320 1321 if (Endianness == llvm::endianness::native)1322 return;1323 1324 ValueProfRecord *VR = getFirstValueProfRecord(this);1325 for (uint32_t K = 0; K < NumValueKinds; K++) {1326 ValueProfRecord *NVR = getValueProfRecordNext(VR);1327 VR->swapBytes(llvm::endianness::native, Endianness);1328 VR = NVR;1329 }1330 sys::swapByteOrder<uint32_t>(TotalSize);1331 sys::swapByteOrder<uint32_t>(NumValueKinds);1332}1333 1334void annotateValueSite(Module &M, Instruction &Inst,1335 const InstrProfRecord &InstrProfR,1336 InstrProfValueKind ValueKind, uint32_t SiteIdx,1337 uint32_t MaxMDCount) {1338 auto VDs = InstrProfR.getValueArrayForSite(ValueKind, SiteIdx);1339 if (VDs.empty())1340 return;1341 uint64_t Sum = 0;1342 for (const InstrProfValueData &V : VDs)1343 Sum = SaturatingAdd(Sum, V.Count);1344 annotateValueSite(M, Inst, VDs, Sum, ValueKind, MaxMDCount);1345}1346 1347void annotateValueSite(Module &M, Instruction &Inst,1348 ArrayRef<InstrProfValueData> VDs,1349 uint64_t Sum, InstrProfValueKind ValueKind,1350 uint32_t MaxMDCount) {1351 if (VDs.empty())1352 return;1353 LLVMContext &Ctx = M.getContext();1354 MDBuilder MDHelper(Ctx);1355 SmallVector<Metadata *, 3> Vals;1356 // Tag1357 Vals.push_back(MDHelper.createString(MDProfLabels::ValueProfile));1358 // Value Kind1359 Vals.push_back(MDHelper.createConstant(1360 ConstantInt::get(Type::getInt32Ty(Ctx), ValueKind)));1361 // Total Count1362 Vals.push_back(1363 MDHelper.createConstant(ConstantInt::get(Type::getInt64Ty(Ctx), Sum)));1364 1365 // Value Profile Data1366 uint32_t MDCount = MaxMDCount;1367 for (const auto &VD : VDs) {1368 Vals.push_back(MDHelper.createConstant(1369 ConstantInt::get(Type::getInt64Ty(Ctx), VD.Value)));1370 Vals.push_back(MDHelper.createConstant(1371 ConstantInt::get(Type::getInt64Ty(Ctx), VD.Count)));1372 if (--MDCount == 0)1373 break;1374 }1375 Inst.setMetadata(LLVMContext::MD_prof, MDNode::get(Ctx, Vals));1376}1377 1378MDNode *mayHaveValueProfileOfKind(const Instruction &Inst,1379 InstrProfValueKind ValueKind) {1380 MDNode *MD = Inst.getMetadata(LLVMContext::MD_prof);1381 if (!MD)1382 return nullptr;1383 1384 if (MD->getNumOperands() < 5)1385 return nullptr;1386 1387 MDString *Tag = cast<MDString>(MD->getOperand(0));1388 if (!Tag || Tag->getString() != MDProfLabels::ValueProfile)1389 return nullptr;1390 1391 // Now check kind:1392 ConstantInt *KindInt = mdconst::dyn_extract<ConstantInt>(MD->getOperand(1));1393 if (!KindInt)1394 return nullptr;1395 if (KindInt->getZExtValue() != ValueKind)1396 return nullptr;1397 1398 return MD;1399}1400 1401SmallVector<InstrProfValueData, 4>1402getValueProfDataFromInst(const Instruction &Inst, InstrProfValueKind ValueKind,1403 uint32_t MaxNumValueData, uint64_t &TotalC,1404 bool GetNoICPValue) {1405 // Four inline elements seem to work well in practice. With MaxNumValueData,1406 // this array won't grow very big anyway.1407 SmallVector<InstrProfValueData, 4> ValueData;1408 MDNode *MD = mayHaveValueProfileOfKind(Inst, ValueKind);1409 if (!MD)1410 return ValueData;1411 const unsigned NOps = MD->getNumOperands();1412 // Get total count1413 ConstantInt *TotalCInt = mdconst::dyn_extract<ConstantInt>(MD->getOperand(2));1414 if (!TotalCInt)1415 return ValueData;1416 TotalC = TotalCInt->getZExtValue();1417 1418 ValueData.reserve((NOps - 3) / 2);1419 for (unsigned I = 3; I < NOps; I += 2) {1420 if (ValueData.size() >= MaxNumValueData)1421 break;1422 ConstantInt *Value = mdconst::dyn_extract<ConstantInt>(MD->getOperand(I));1423 ConstantInt *Count =1424 mdconst::dyn_extract<ConstantInt>(MD->getOperand(I + 1));1425 if (!Value || !Count) {1426 ValueData.clear();1427 return ValueData;1428 }1429 uint64_t CntValue = Count->getZExtValue();1430 if (!GetNoICPValue && (CntValue == NOMORE_ICP_MAGICNUM))1431 continue;1432 InstrProfValueData V;1433 V.Value = Value->getZExtValue();1434 V.Count = CntValue;1435 ValueData.push_back(V);1436 }1437 return ValueData;1438}1439 1440MDNode *getPGOFuncNameMetadata(const Function &F) {1441 return F.getMetadata(getPGOFuncNameMetadataName());1442}1443 1444static void createPGONameMetadata(GlobalObject &GO, StringRef MetadataName,1445 StringRef PGOName) {1446 // Only for internal linkage functions or global variables. The name is not1447 // the same as PGO name for these global objects.1448 if (GO.getName() == PGOName)1449 return;1450 1451 // Don't create duplicated metadata.1452 if (GO.getMetadata(MetadataName))1453 return;1454 1455 LLVMContext &C = GO.getContext();1456 MDNode *N = MDNode::get(C, MDString::get(C, PGOName));1457 GO.setMetadata(MetadataName, N);1458}1459 1460void createPGOFuncNameMetadata(Function &F, StringRef PGOFuncName) {1461 return createPGONameMetadata(F, getPGOFuncNameMetadataName(), PGOFuncName);1462}1463 1464void createPGONameMetadata(GlobalObject &GO, StringRef PGOName) {1465 return createPGONameMetadata(GO, getPGONameMetadataName(), PGOName);1466}1467 1468bool needsComdatForCounter(const GlobalObject &GO, const Module &M) {1469 if (GO.hasComdat())1470 return true;1471 1472 if (!M.getTargetTriple().supportsCOMDAT())1473 return false;1474 1475 // See createPGOFuncNameVar for more details. To avoid link errors, profile1476 // counters for function with available_externally linkage needs to be changed1477 // to linkonce linkage. On ELF based systems, this leads to weak symbols to be1478 // created. Without using comdat, duplicate entries won't be removed by the1479 // linker leading to increased data segement size and raw profile size. Even1480 // worse, since the referenced counter from profile per-function data object1481 // will be resolved to the common strong definition, the profile counts for1482 // available_externally functions will end up being duplicated in raw profile1483 // data. This can result in distorted profile as the counts of those dups1484 // will be accumulated by the profile merger.1485 GlobalValue::LinkageTypes Linkage = GO.getLinkage();1486 if (Linkage != GlobalValue::ExternalWeakLinkage &&1487 Linkage != GlobalValue::AvailableExternallyLinkage)1488 return false;1489 1490 return true;1491}1492 1493// Check if INSTR_PROF_RAW_VERSION_VAR is defined.1494bool isIRPGOFlagSet(const Module *M) {1495 const GlobalVariable *IRInstrVar =1496 M->getNamedGlobal(INSTR_PROF_QUOTE(INSTR_PROF_RAW_VERSION_VAR));1497 if (!IRInstrVar || IRInstrVar->hasLocalLinkage())1498 return false;1499 1500 // For CSPGO+LTO, this variable might be marked as non-prevailing and we only1501 // have the decl.1502 if (IRInstrVar->isDeclaration())1503 return true;1504 1505 // Check if the flag is set.1506 if (!IRInstrVar->hasInitializer())1507 return false;1508 1509 auto *InitVal = dyn_cast_or_null<ConstantInt>(IRInstrVar->getInitializer());1510 if (!InitVal)1511 return false;1512 return (InitVal->getZExtValue() & VARIANT_MASK_IR_PROF) != 0;1513}1514 1515// Check if we can safely rename this Comdat function.1516bool canRenameComdatFunc(const Function &F, bool CheckAddressTaken) {1517 if (F.getName().empty())1518 return false;1519 if (!needsComdatForCounter(F, *(F.getParent())))1520 return false;1521 // Unsafe to rename the address-taken function (which can be used in1522 // function comparison).1523 if (CheckAddressTaken && F.hasAddressTaken())1524 return false;1525 // Only safe to do if this function may be discarded if it is not used1526 // in the compilation unit.1527 if (!GlobalValue::isDiscardableIfUnused(F.getLinkage()))1528 return false;1529 1530 // For AvailableExternallyLinkage functions.1531 if (!F.hasComdat()) {1532 assert(F.getLinkage() == GlobalValue::AvailableExternallyLinkage);1533 return true;1534 }1535 return true;1536}1537 1538// Create the variable for the profile file name.1539void createProfileFileNameVar(Module &M, StringRef InstrProfileOutput) {1540 if (InstrProfileOutput.empty())1541 return;1542 Constant *ProfileNameConst =1543 ConstantDataArray::getString(M.getContext(), InstrProfileOutput, true);1544 GlobalVariable *ProfileNameVar = new GlobalVariable(1545 M, ProfileNameConst->getType(), true, GlobalValue::WeakAnyLinkage,1546 ProfileNameConst, INSTR_PROF_QUOTE(INSTR_PROF_PROFILE_NAME_VAR));1547 ProfileNameVar->setVisibility(GlobalValue::HiddenVisibility);1548 Triple TT(M.getTargetTriple());1549 if (TT.supportsCOMDAT()) {1550 ProfileNameVar->setLinkage(GlobalValue::ExternalLinkage);1551 ProfileNameVar->setComdat(M.getOrInsertComdat(1552 StringRef(INSTR_PROF_QUOTE(INSTR_PROF_PROFILE_NAME_VAR))));1553 }1554}1555 1556Error OverlapStats::accumulateCounts(const std::string &BaseFilename,1557 const std::string &TestFilename,1558 bool IsCS) {1559 auto GetProfileSum = [IsCS](const std::string &Filename,1560 CountSumOrPercent &Sum) -> Error {1561 // This function is only used from llvm-profdata that doesn't use any kind1562 // of VFS. Just create a default RealFileSystem to read profiles.1563 auto FS = vfs::getRealFileSystem();1564 auto ReaderOrErr = InstrProfReader::create(Filename, *FS);1565 if (Error E = ReaderOrErr.takeError()) {1566 return E;1567 }1568 auto Reader = std::move(ReaderOrErr.get());1569 Reader->accumulateCounts(Sum, IsCS);1570 return Error::success();1571 };1572 auto Ret = GetProfileSum(BaseFilename, Base);1573 if (Ret)1574 return Ret;1575 Ret = GetProfileSum(TestFilename, Test);1576 if (Ret)1577 return Ret;1578 this->BaseFilename = &BaseFilename;1579 this->TestFilename = &TestFilename;1580 Valid = true;1581 return Error::success();1582}1583 1584void OverlapStats::addOneMismatch(const CountSumOrPercent &MismatchFunc) {1585 Mismatch.NumEntries += 1;1586 Mismatch.CountSum += MismatchFunc.CountSum / Test.CountSum;1587 for (unsigned I = 0; I < IPVK_Last - IPVK_First + 1; I++) {1588 if (Test.ValueCounts[I] >= 1.0f)1589 Mismatch.ValueCounts[I] +=1590 MismatchFunc.ValueCounts[I] / Test.ValueCounts[I];1591 }1592}1593 1594void OverlapStats::addOneUnique(const CountSumOrPercent &UniqueFunc) {1595 Unique.NumEntries += 1;1596 Unique.CountSum += UniqueFunc.CountSum / Test.CountSum;1597 for (unsigned I = 0; I < IPVK_Last - IPVK_First + 1; I++) {1598 if (Test.ValueCounts[I] >= 1.0f)1599 Unique.ValueCounts[I] += UniqueFunc.ValueCounts[I] / Test.ValueCounts[I];1600 }1601}1602 1603void OverlapStats::dump(raw_fd_ostream &OS) const {1604 if (!Valid)1605 return;1606 1607 const char *EntryName =1608 (Level == ProgramLevel ? "functions" : "edge counters");1609 if (Level == ProgramLevel) {1610 OS << "Profile overlap information for base_profile: " << *BaseFilename1611 << " and test_profile: " << *TestFilename << "\nProgram level:\n";1612 } else {1613 OS << "Function level:\n"1614 << " Function: " << FuncName << " (Hash=" << FuncHash << ")\n";1615 }1616 1617 OS << " # of " << EntryName << " overlap: " << Overlap.NumEntries << "\n";1618 if (Mismatch.NumEntries)1619 OS << " # of " << EntryName << " mismatch: " << Mismatch.NumEntries1620 << "\n";1621 if (Unique.NumEntries)1622 OS << " # of " << EntryName1623 << " only in test_profile: " << Unique.NumEntries << "\n";1624 1625 OS << " Edge profile overlap: " << format("%.3f%%", Overlap.CountSum * 100)1626 << "\n";1627 if (Mismatch.NumEntries)1628 OS << " Mismatched count percentage (Edge): "1629 << format("%.3f%%", Mismatch.CountSum * 100) << "\n";1630 if (Unique.NumEntries)1631 OS << " Percentage of Edge profile only in test_profile: "1632 << format("%.3f%%", Unique.CountSum * 100) << "\n";1633 OS << " Edge profile base count sum: " << format("%.0f", Base.CountSum)1634 << "\n"1635 << " Edge profile test count sum: " << format("%.0f", Test.CountSum)1636 << "\n";1637 1638 for (unsigned I = 0; I < IPVK_Last - IPVK_First + 1; I++) {1639 if (Base.ValueCounts[I] < 1.0f && Test.ValueCounts[I] < 1.0f)1640 continue;1641 char ProfileKindName[20] = {0};1642 switch (I) {1643 case IPVK_IndirectCallTarget:1644 strncpy(ProfileKindName, "IndirectCall", 19);1645 break;1646 case IPVK_MemOPSize:1647 strncpy(ProfileKindName, "MemOP", 19);1648 break;1649 case IPVK_VTableTarget:1650 strncpy(ProfileKindName, "VTable", 19);1651 break;1652 default:1653 snprintf(ProfileKindName, 19, "VP[%d]", I);1654 break;1655 }1656 OS << " " << ProfileKindName1657 << " profile overlap: " << format("%.3f%%", Overlap.ValueCounts[I] * 100)1658 << "\n";1659 if (Mismatch.NumEntries)1660 OS << " Mismatched count percentage (" << ProfileKindName1661 << "): " << format("%.3f%%", Mismatch.ValueCounts[I] * 100) << "\n";1662 if (Unique.NumEntries)1663 OS << " Percentage of " << ProfileKindName1664 << " profile only in test_profile: "1665 << format("%.3f%%", Unique.ValueCounts[I] * 100) << "\n";1666 OS << " " << ProfileKindName1667 << " profile base count sum: " << format("%.0f", Base.ValueCounts[I])1668 << "\n"1669 << " " << ProfileKindName1670 << " profile test count sum: " << format("%.0f", Test.ValueCounts[I])1671 << "\n";1672 }1673}1674 1675namespace IndexedInstrProf {1676Expected<Header> Header::readFromBuffer(const unsigned char *Buffer) {1677 using namespace support;1678 static_assert(std::is_standard_layout_v<Header>,1679 "Use standard layout for Header for simplicity");1680 Header H;1681 1682 H.Magic = endian::readNext<uint64_t, llvm::endianness::little>(Buffer);1683 // Check the magic number.1684 if (H.Magic != IndexedInstrProf::Magic)1685 return make_error<InstrProfError>(instrprof_error::bad_magic);1686 1687 // Read the version.1688 H.Version = endian::readNext<uint64_t, llvm::endianness::little>(Buffer);1689 if (H.getIndexedProfileVersion() >1690 IndexedInstrProf::ProfVersion::CurrentVersion)1691 return make_error<InstrProfError>(instrprof_error::unsupported_version);1692 1693 static_assert(IndexedInstrProf::ProfVersion::CurrentVersion == Version13,1694 "Please update the reader as needed when a new field is added "1695 "or when indexed profile version gets bumped.");1696 1697 Buffer += sizeof(uint64_t); // Skip Header.Unused field.1698 H.HashType = endian::readNext<uint64_t, llvm::endianness::little>(Buffer);1699 H.HashOffset = endian::readNext<uint64_t, llvm::endianness::little>(Buffer);1700 if (H.getIndexedProfileVersion() >= 8)1701 H.MemProfOffset =1702 endian::readNext<uint64_t, llvm::endianness::little>(Buffer);1703 if (H.getIndexedProfileVersion() >= 9)1704 H.BinaryIdOffset =1705 endian::readNext<uint64_t, llvm::endianness::little>(Buffer);1706 // Version 11 is handled by this condition.1707 if (H.getIndexedProfileVersion() >= 10)1708 H.TemporalProfTracesOffset =1709 endian::readNext<uint64_t, llvm::endianness::little>(Buffer);1710 if (H.getIndexedProfileVersion() >= 12)1711 H.VTableNamesOffset =1712 endian::readNext<uint64_t, llvm::endianness::little>(Buffer);1713 return H;1714}1715 1716uint64_t Header::getIndexedProfileVersion() const {1717 return GET_VERSION(Version);1718}1719 1720size_t Header::size() const {1721 switch (getIndexedProfileVersion()) {1722 // To retain backward compatibility, new fields must be appended to the end1723 // of the header, and byte offset of existing fields shouldn't change when1724 // indexed profile version gets incremented.1725 static_assert(1726 IndexedInstrProf::ProfVersion::CurrentVersion == Version13,1727 "Please update the size computation below if a new field has "1728 "been added to the header; for a version bump without new "1729 "fields, add a case statement to fall through to the latest version.");1730 case 13ull:1731 case 12ull:1732 return 72;1733 case 11ull:1734 [[fallthrough]];1735 case 10ull:1736 return 64;1737 case 9ull:1738 return 56;1739 case 8ull:1740 return 48;1741 default: // Version7 (when the backwards compatible header was introduced).1742 return 40;1743 }1744}1745 1746} // namespace IndexedInstrProf1747 1748} // end namespace llvm1749