llvm/lib/ProfileData/InstrProf.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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file contains support for clang's instrumentation based PGO and
  10 // coverage.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/ProfileData/InstrProf.h"
  15 #include "llvm/ADT/ArrayRef.h"
  16 #include "llvm/ADT/SetVector.h"
  17 #include "llvm/ADT/SmallString.h"
  18 #include "llvm/ADT/SmallVector.h"
  19 #include "llvm/ADT/StringExtras.h"
  20 #include "llvm/ADT/StringRef.h"
  21 #include "llvm/Config/config.h"
  22 #include "llvm/IR/Constant.h"
  23 #include "llvm/IR/Constants.h"
  24 #include "llvm/IR/Function.h"
  25 #include "llvm/IR/GlobalValue.h"
  26 #include "llvm/IR/GlobalVariable.h"
  27 #include "llvm/IR/Instruction.h"
  28 #include "llvm/IR/LLVMContext.h"
  29 #include "llvm/IR/MDBuilder.h"
  30 #include "llvm/IR/Mangler.h"
  31 #include "llvm/IR/Metadata.h"
  32 #include "llvm/IR/Module.h"
  33 #include "llvm/IR/Type.h"
  34 #include "llvm/ProfileData/InstrProfReader.h"
  35 #include "llvm/Support/Casting.h"
  36 #include "llvm/Support/CommandLine.h"
  37 #include "llvm/Support/Compiler.h"
  38 #include "llvm/Support/Compression.h"
  39 #include "llvm/Support/Endian.h"
  40 #include "llvm/Support/Error.h"
  41 #include "llvm/Support/ErrorHandling.h"
  42 #include "llvm/Support/LEB128.h"
  43 #include "llvm/Support/MathExtras.h"
  44 #include "llvm/Support/Path.h"
  45 #include "llvm/Support/SwapByteOrder.h"
  46 #include "llvm/Support/VirtualFileSystem.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
  60 using namespace llvm;
  61
  62 static cl::opt<bool> StaticFuncFullModulePrefix(
  63     "static-func-full-module-prefix", cl::init(true), cl::Hidden,
  64     cl::desc("Use full module build paths in the profile counter names for "
  65              "static functions."));
  66
  67 // This option is tailored to users that have different top-level directory in
  68 // profile-gen and profile-use compilation. Users need to specific the number
  69 // of levels to strip. A value larger than the number of directories in the
  70 // source file will strip all the directory names and only leave the basename.
  71 //
  72 // Note current ThinLTO module importing for the indirect-calls assumes
  73 // the source directory name not being stripped. A non-zero option value here
  74 // can potentially prevent some inter-module indirect-call-promotions.
  75 static cl::opt<unsigned> StaticFuncStripDirNamePrefix(
  76     "static-func-strip-dirname-prefix", cl::init(0), cl::Hidden,
  77     cl::desc("Strip specified level of directory name from source path in "
  78              "the profile counter name for static functions."));
  79
  80 static std::string getInstrProfErrString(instrprof_error Err,
  81                                          const std::string &ErrMsg = "") {
  82   std::string Msg;
  83   raw_string_ostream OS(Msg);
  84
  85   switch (Err) {
  86   case instrprof_error::success:
  87     OS << "success";
  88     break;
  89   case instrprof_error::eof:
  90     OS << "end of File";
  91     break;
  92   case instrprof_error::unrecognized_format:
  93     OS << "unrecognized instrumentation profile encoding format";
  94     break;
  95   case instrprof_error::bad_magic:
  96     OS << "invalid instrumentation profile data (bad magic)";
  97     break;
  98   case instrprof_error::bad_header:
  99     OS << "invalid instrumentation profile data (file header is corrupt)";
 100     break;
 101   case instrprof_error::unsupported_version:
 102     OS << "unsupported instrumentation profile format version";
 103     break;
 104   case instrprof_error::unsupported_hash_type:
 105     OS << "unsupported instrumentation profile hash type";
 106     break;
 107   case instrprof_error::too_large:
 108     OS << "too much profile data";
 109     break;
 110   case instrprof_error::truncated:
 111     OS << "truncated profile data";
 112     break;
 113   case instrprof_error::malformed:
 114     OS << "malformed instrumentation profile data";
 115     break;
 116   case instrprof_error::missing_debug_info_for_correlation:
 117     OS << "debug info for correlation is required";
 118     break;
 119   case instrprof_error::unexpected_debug_info_for_correlation:
 120     OS << "debug info for correlation is not necessary";
 121     break;
 122   case instrprof_error::unable_to_correlate_profile:
 123     OS << "unable to correlate profile";
 124     break;
 125   case instrprof_error::invalid_prof:
 126     OS << "invalid profile created. Please file a bug "
 127           "at: " BUG_REPORT_URL
 128           " and include the profraw files that caused this error.";
 129     break;
 130   case instrprof_error::unknown_function:
 131     OS << "no profile data available for function";
 132     break;
 133   case instrprof_error::hash_mismatch:
 134     OS << "function control flow change detected (hash mismatch)";
 135     break;
 136   case instrprof_error::count_mismatch:
 137     OS << "function basic block count change detected (counter mismatch)";
 138     break;
 139   case instrprof_error::bitmap_mismatch:
 140     OS << "function bitmap size change detected (bitmap size mismatch)";
 141     break;
 142   case instrprof_error::counter_overflow:
 143     OS << "counter overflow";
 144     break;
 145   case instrprof_error::value_site_count_mismatch:
 146     OS << "function value site count change detected (counter mismatch)";
 147     break;
 148   case instrprof_error::compress_failed:
 149     OS << "failed to compress data (zlib)";
 150     break;
 151   case instrprof_error::uncompress_failed:
 152     OS << "failed to uncompress data (zlib)";
 153     break;
 154   case instrprof_error::empty_raw_profile:
 155     OS << "empty raw profile file";
 156     break;
 157   case instrprof_error::zlib_unavailable:
 158     OS << "profile uses zlib compression but the profile reader was built "
 159           "without zlib support";
 160     break;
 161   case instrprof_error::raw_profile_version_mismatch:
 162     OS << "raw profile version mismatch";
 163     break;
 164   case instrprof_error::counter_value_too_large:
 165     OS << "excessively large counter value suggests corrupted profile data";
 166     break;
 167   }
 168
 169   // If optional error message is not empty, append it to the message.
 170   if (!ErrMsg.empty())
 171     OS << ": " << ErrMsg;
 172
 173   return OS.str();
 174 }
 175
 176 namespace {
 177
 178 // FIXME: This class is only here to support the transition to llvm::Error. It
 179 // will be removed once this transition is complete. Clients should prefer to
 180 // deal with the Error value directly, rather than converting to error_code.
 181 class InstrProfErrorCategoryType : public std::error_category {
 182   const char *name() const noexcept override { return "llvm.instrprof"; }
 183
 184   std::string message(int IE) const override {
 185     return getInstrProfErrString(static_cast<instrprof_error>(IE));
 186   }
 187 };
 188
 189 } // end anonymous namespace
 190
 191 const std::error_category &llvm::instrprof_category() {
 192   static InstrProfErrorCategoryType ErrorCategory;
 193   return ErrorCategory;
 194 }
 195
 196 namespace {
 197
 198 const char *InstrProfSectNameCommon[] = {
 199 #define INSTR_PROF_SECT_ENTRY(Kind, SectNameCommon, SectNameCoff, Prefix)      \
 200   SectNameCommon,
 201 #include "llvm/ProfileData/InstrProfData.inc"
 202 };
 203
 204 const char *InstrProfSectNameCoff[] = {
 205 #define INSTR_PROF_SECT_ENTRY(Kind, SectNameCommon, SectNameCoff, Prefix)      \
 206   SectNameCoff,
 207 #include "llvm/ProfileData/InstrProfData.inc"
 208 };
 209
 210 const char *InstrProfSectNamePrefix[] = {
 211 #define INSTR_PROF_SECT_ENTRY(Kind, SectNameCommon, SectNameCoff, Prefix)      \
 212   Prefix,
 213 #include "llvm/ProfileData/InstrProfData.inc"
 214 };
 215
 216 } // namespace
 217
 218 namespace llvm {
 219
 220 cl::opt<bool> DoInstrProfNameCompression(
 221     "enable-name-compression",
 222     cl::desc("Enable name/filename string compression"), cl::init(true));
 223
 224 std::string getInstrProfSectionName(InstrProfSectKind IPSK,
 225                                     Triple::ObjectFormatType OF,
 226                                     bool AddSegmentInfo) {
 227   std::string SectName;
 228
 229   if (OF == Triple::MachO && AddSegmentInfo)
 230     SectName = InstrProfSectNamePrefix[IPSK];
 231
 232   if (OF == Triple::COFF)
 233     SectName += InstrProfSectNameCoff[IPSK];
 234   else
 235     SectName += InstrProfSectNameCommon[IPSK];
 236
 237   if (OF == Triple::MachO && IPSK == IPSK_data && AddSegmentInfo)
 238     SectName += ",regular,live_support";
 239
 240   return SectName;
 241 }
 242
 243 std::string InstrProfError::message() const {
 244   return getInstrProfErrString(Err, Msg);
 245 }
 246
 247 char InstrProfError::ID = 0;
 248
 249 std::string getPGOFuncName(StringRef RawFuncName,
 250                            GlobalValue::LinkageTypes Linkage,
 251                            StringRef FileName,
 252                            uint64_t Version LLVM_ATTRIBUTE_UNUSED) {
 253   return GlobalValue::getGlobalIdentifier(RawFuncName, Linkage, FileName);
 254 }
 255
 256 // Strip NumPrefix level of directory name from PathNameStr. If the number of
 257 // directory separators is less than NumPrefix, strip all the directories and
 258 // leave base file name only.
 259 static StringRef stripDirPrefix(StringRef PathNameStr, uint32_t NumPrefix) {
 260   uint32_t Count = NumPrefix;
 261   uint32_t Pos = 0, LastPos = 0;
 262   for (auto & CI : PathNameStr) {
 263     ++Pos;
 264     if (llvm::sys::path::is_separator(CI)) {
 265       LastPos = Pos;
 266       --Count;
 267     }
 268     if (Count == 0)
 269       break;
 270   }
 271   return PathNameStr.substr(LastPos);
 272 }
 273
 274 static StringRef getStrippedSourceFileName(const GlobalObject &GO) {
 275   StringRef FileName(GO.getParent()->getSourceFileName());
 276   uint32_t StripLevel = StaticFuncFullModulePrefix ? 0 : (uint32_t)-1;
 277   if (StripLevel < StaticFuncStripDirNamePrefix)
 278     StripLevel = StaticFuncStripDirNamePrefix;
 279   if (StripLevel)
 280     FileName = stripDirPrefix(FileName, StripLevel);
 281   return FileName;
 282 }
 283
 284 // The PGO name has the format [<filepath>;]<linkage-name> where <filepath>; is
 285 // provided if linkage is local and <linkage-name> is the mangled function
 286 // name. The filepath is used to discriminate possibly identical function names.
 287 // ; is used because it is unlikely to be found in either <filepath> or
 288 // <linkage-name>.
 289 //
 290 // Older compilers used getPGOFuncName() which has the format
 291 // [<filepath>:]<function-name>. <filepath> is used to discriminate between
 292 // possibly identical function names when linkage is local and <function-name>
 293 // simply comes from F.getName(). This caused trouble for Objective-C functions
 294 // which commonly have :'s in their names. Also, since <function-name> is not
 295 // mangled, they cannot be passed to Mach-O linkers via -order_file. We still
 296 // need to compute this name to lookup functions from profiles built by older
 297 // compilers.
 298 static std::string
 299 getIRPGONameForGlobalObject(const GlobalObject &GO,
 300                             GlobalValue::LinkageTypes Linkage,
 301                             StringRef FileName) {
 302   SmallString<64> Name;
 303   if (llvm::GlobalValue::isLocalLinkage(Linkage)) {
 304     Name.append(FileName.empty() ? "<unknown>" : FileName);
 305     Name.append(";");
 306   }
 307   Mangler().getNameWithPrefix(Name, &GO, /*CannotUsePrivateLabel=*/true);
 308   return Name.str().str();
 309 }
 310
 311 static std::optional<std::string> lookupPGONameFromMetadata(MDNode *MD) {
 312   if (MD != nullptr) {
 313     StringRef S = cast<MDString>(MD->getOperand(0))->getString();
 314     return S.str();
 315   }
 316   return {};
 317 }
 318
 319 // Returns the PGO object name. This function has some special handling
 320 // when called in LTO optimization. The following only applies when calling in
 321 // LTO passes (when \c InLTO is true): LTO's internalization privatizes many
 322 // global linkage symbols. This happens after value profile annotation, but
 323 // those internal linkage functions should not have a source prefix.
 324 // Additionally, for ThinLTO mode, exported internal functions are promoted
 325 // and renamed. We need to ensure that the original internal PGO name is
 326 // used when computing the GUID that is compared against the profiled GUIDs.
 327 // To differentiate compiler generated internal symbols from original ones,
 328 // PGOFuncName meta data are created and attached to the original internal
 329 // symbols in the value profile annotation step
 330 // (PGOUseFunc::annotateIndirectCallSites). If a symbol does not have the meta
 331 // data, its original linkage must be non-internal.
 332 static std::string getIRPGOObjectName(const GlobalObject &GO, bool InLTO,
 333                                       MDNode *PGONameMetadata) {
 334   if (!InLTO) {
 335     auto FileName = getStrippedSourceFileName(GO);
 336     return getIRPGONameForGlobalObject(GO, GO.getLinkage(), FileName);
 337   }
 338
 339   // In LTO mode (when InLTO is true), first check if there is a meta data.
 340   if (auto IRPGOFuncName = lookupPGONameFromMetadata(PGONameMetadata))
 341     return *IRPGOFuncName;
 342
 343   // If there is no meta data, the function must be a global before the value
 344   // profile annotation pass. Its current linkage may be internal if it is
 345   // internalized in LTO mode.
 346   return getIRPGONameForGlobalObject(GO, GlobalValue::ExternalLinkage, "");
 347 }
 348
 349 // Returns the IRPGO function name and does special handling when called
 350 // in LTO optimization. See the comments of `getIRPGOObjectName` for details.
 351 std::string getIRPGOFuncName(const Function &F, bool InLTO) {
 352   return getIRPGOObjectName(F, InLTO, getPGOFuncNameMetadata(F));
 353 }
 354
 355 // This is similar to `getIRPGOFuncName` except that this function calls
 356 // 'getPGOFuncName' to get a name and `getIRPGOFuncName` calls
 357 // 'getIRPGONameForGlobalObject'. See the difference between two callees in the
 358 // comments of `getIRPGONameForGlobalObject`.
 359 std::string getPGOFuncName(const Function &F, bool InLTO, uint64_t Version) {
 360   if (!InLTO) {
 361     auto FileName = getStrippedSourceFileName(F);
 362     return getPGOFuncName(F.getName(), F.getLinkage(), FileName, Version);
 363   }
 364
 365   // In LTO mode (when InLTO is true), first check if there is a meta data.
 366   if (auto PGOFuncName = lookupPGONameFromMetadata(getPGOFuncNameMetadata(F)))
 367     return *PGOFuncName;
 368
 369   // If there is no meta data, the function must be a global before the value
 370   // profile annotation pass. Its current linkage may be internal if it is
 371   // internalized in LTO mode.
 372   return getPGOFuncName(F.getName(), GlobalValue::ExternalLinkage, "");
 373 }
 374
 375 // See getIRPGOFuncName() for a discription of the format.
 376 std::pair<StringRef, StringRef>
 377 getParsedIRPGOFuncName(StringRef IRPGOFuncName) {
 378   auto [FileName, FuncName] = IRPGOFuncName.split(';');
 379   if (FuncName.empty())
 380     return std::make_pair(StringRef(), IRPGOFuncName);
 381   return std::make_pair(FileName, FuncName);
 382 }
 383
 384 StringRef getFuncNameWithoutPrefix(StringRef PGOFuncName, StringRef FileName) {
 385   if (FileName.empty())
 386     return PGOFuncName;
 387   // Drop the file name including ':'. See also getPGOFuncName.
 388   if (PGOFuncName.startswith(FileName))
 389     PGOFuncName = PGOFuncName.drop_front(FileName.size() + 1);
 390   return PGOFuncName;
 391 }
 392
 393 // \p FuncName is the string used as profile lookup key for the function. A
 394 // symbol is created to hold the name. Return the legalized symbol name.
 395 std::string getPGOFuncNameVarName(StringRef FuncName,
 396                                   GlobalValue::LinkageTypes Linkage) {
 397   std::string VarName = std::string(getInstrProfNameVarPrefix());
 398   VarName += FuncName;
 399
 400   if (!GlobalValue::isLocalLinkage(Linkage))
 401     return VarName;
 402
 403   // Now fix up illegal chars in local VarName that may upset the assembler.
 404   const char InvalidChars[] = "-:;<>/\"'";
 405   size_t found = VarName.find_first_of(InvalidChars);
 406   while (found != std::string::npos) {
 407     VarName[found] = '_';
 408     found = VarName.find_first_of(InvalidChars, found + 1);
 409   }
 410   return VarName;
 411 }
 412
 413 GlobalVariable *createPGOFuncNameVar(Module &M,
 414                                      GlobalValue::LinkageTypes Linkage,
 415                                      StringRef PGOFuncName) {
 416   // We generally want to match the function's linkage, but available_externally
 417   // and extern_weak both have the wrong semantics, and anything that doesn't
 418   // need to link across compilation units doesn't need to be visible at all.
 419   if (Linkage == GlobalValue::ExternalWeakLinkage)
 420     Linkage = GlobalValue::LinkOnceAnyLinkage;
 421   else if (Linkage == GlobalValue::AvailableExternallyLinkage)
 422     Linkage = GlobalValue::LinkOnceODRLinkage;
 423   else if (Linkage == GlobalValue::InternalLinkage ||
 424            Linkage == GlobalValue::ExternalLinkage)
 425     Linkage = GlobalValue::PrivateLinkage;
 426
 427   auto *Value =
 428       ConstantDataArray::getString(M.getContext(), PGOFuncName, false);
 429   auto FuncNameVar =
 430       new GlobalVariable(M, Value->getType(), true, Linkage, Value,
 431                          getPGOFuncNameVarName(PGOFuncName, Linkage));
 432
 433   // Hide the symbol so that we correctly get a copy for each executable.
 434   if (!GlobalValue::isLocalLinkage(FuncNameVar->getLinkage()))
 435     FuncNameVar->setVisibility(GlobalValue::HiddenVisibility);
 436
 437   return FuncNameVar;
 438 }
 439
 440 GlobalVariable *createPGOFuncNameVar(Function &F, StringRef PGOFuncName) {
 441   return createPGOFuncNameVar(*F.getParent(), F.getLinkage(), PGOFuncName);
 442 }
 443
 444 Error InstrProfSymtab::create(Module &M, bool InLTO) {
 445   for (Function &F : M) {
 446     // Function may not have a name: like using asm("") to overwrite the name.
 447     // Ignore in this case.
 448     if (!F.hasName())
 449       continue;
 450     if (Error E = addFuncWithName(F, getIRPGOFuncName(F, InLTO)))
 451       return E;
 452     // Also use getPGOFuncName() so that we can find records from older profiles
 453     if (Error E = addFuncWithName(F, getPGOFuncName(F, InLTO)))
 454       return E;
 455   }
 456   Sorted = false;
 457   finalizeSymtab();
 458   return Error::success();
 459 }
 460
 461 Error InstrProfSymtab::addFuncWithName(Function &F, StringRef PGOFuncName) {
 462   if (Error E = addFuncName(PGOFuncName))
 463     return E;
 464   MD5FuncMap.emplace_back(Function::getGUID(PGOFuncName), &F);
 465   // In ThinLTO, local function may have been promoted to global and have
 466   // suffix ".llvm." added to the function name. We need to add the
 467   // stripped function name to the symbol table so that we can find a match
 468   // from profile.
 469   //
 470   // We may have other suffixes similar as ".llvm." which are needed to
 471   // be stripped before the matching, but ".__uniq." suffix which is used
 472   // to differentiate internal linkage functions in different modules
 473   // should be kept. Now this is the only suffix with the pattern ".xxx"
 474   // which is kept before matching.
 475   const std::string UniqSuffix = ".__uniq.";
 476   auto pos = PGOFuncName.find(UniqSuffix);
 477   // Search '.' after ".__uniq." if ".__uniq." exists, otherwise
 478   // search '.' from the beginning.
 479   if (pos != std::string::npos)
 480     pos += UniqSuffix.length();
 481   else
 482     pos = 0;
 483   pos = PGOFuncName.find('.', pos);
 484   if (pos != std::string::npos && pos != 0) {
 485     StringRef OtherFuncName = PGOFuncName.substr(0, pos);
 486     if (Error E = addFuncName(OtherFuncName))
 487       return E;
 488     MD5FuncMap.emplace_back(Function::getGUID(OtherFuncName), &F);
 489   }
 490   return Error::success();
 491 }
 492
 493 uint64_t InstrProfSymtab::getFunctionHashFromAddress(uint64_t Address) {
 494   finalizeSymtab();
 495   auto It = partition_point(AddrToMD5Map, [=](std::pair<uint64_t, uint64_t> A) {
 496     return A.first < Address;
 497   });
 498   // Raw function pointer collected by value profiler may be from
 499   // external functions that are not instrumented. They won't have
 500   // mapping data to be used by the deserializer. Force the value to
 501   // be 0 in this case.
 502   if (It != AddrToMD5Map.end() && It->first == Address)
 503     return (uint64_t)It->second;
 504   return 0;
 505 }
 506
 507 void InstrProfSymtab::dumpNames(raw_ostream &OS) const {
 508   SmallVector<StringRef, 0> Sorted(NameTab.keys());
 509   llvm::sort(Sorted);
 510   for (StringRef S : Sorted)
 511     OS << S << '\n';
 512 }
 513
 514 Error collectGlobalObjectNameStrings(ArrayRef<std::string> NameStrs,
 515                                      bool doCompression, std::string &Result) {
 516   assert(!NameStrs.empty() && "No name data to emit");
 517
 518   uint8_t Header[20], *P = Header;
 519   std::string UncompressedNameStrings =
 520       join(NameStrs.begin(), NameStrs.end(), getInstrProfNameSeparator());
 521
 522   assert(StringRef(UncompressedNameStrings)
 523                  .count(getInstrProfNameSeparator()) == (NameStrs.size() - 1) &&
 524          "PGO name is invalid (contains separator token)");
 525
 526   unsigned EncLen = encodeULEB128(UncompressedNameStrings.length(), P);
 527   P += EncLen;
 528
 529   auto WriteStringToResult = [&](size_t CompressedLen, StringRef InputStr) {
 530     EncLen = encodeULEB128(CompressedLen, P);
 531     P += EncLen;
 532     char *HeaderStr = reinterpret_cast<char *>(&Header[0]);
 533     unsigned HeaderLen = P - &Header[0];
 534     Result.append(HeaderStr, HeaderLen);
 535     Result += InputStr;
 536     return Error::success();
 537   };
 538
 539   if (!doCompression) {
 540     return WriteStringToResult(0, UncompressedNameStrings);
 541   }
 542
 543   SmallVector<uint8_t, 128> CompressedNameStrings;
 544   compression::zlib::compress(arrayRefFromStringRef(UncompressedNameStrings),
 545                               CompressedNameStrings,
 546                               compression::zlib::BestSizeCompression);
 547
 548   return WriteStringToResult(CompressedNameStrings.size(),
 549                              toStringRef(CompressedNameStrings));
 550 }
 551
 552 StringRef getPGOFuncNameVarInitializer(GlobalVariable *NameVar) {
 553   auto *Arr = cast<ConstantDataArray>(NameVar->getInitializer());
 554   StringRef NameStr =
 555       Arr->isCString() ? Arr->getAsCString() : Arr->getAsString();
 556   return NameStr;
 557 }
 558
 559 Error collectPGOFuncNameStrings(ArrayRef<GlobalVariable *> NameVars,
 560                                 std::string &Result, bool doCompression) {
 561   std::vector<std::string> NameStrs;
 562   for (auto *NameVar : NameVars) {
 563     NameStrs.push_back(std::string(getPGOFuncNameVarInitializer(NameVar)));
 564   }
 565   return collectGlobalObjectNameStrings(
 566       NameStrs, compression::zlib::isAvailable() && doCompression, Result);
 567 }
 568
 569 Error readPGOFuncNameStrings(StringRef NameStrings, InstrProfSymtab &Symtab) {
 570   const uint8_t *P = NameStrings.bytes_begin();
 571   const uint8_t *EndP = NameStrings.bytes_end();
 572   while (P < EndP) {
 573     uint32_t N;
 574     uint64_t UncompressedSize = decodeULEB128(P, &N);
 575     P += N;
 576     uint64_t CompressedSize = decodeULEB128(P, &N);
 577     P += N;
 578     bool isCompressed = (CompressedSize != 0);
 579     SmallVector<uint8_t, 128> UncompressedNameStrings;
 580     StringRef NameStrings;
 581     if (isCompressed) {
 582       if (!llvm::compression::zlib::isAvailable())
 583         return make_error<InstrProfError>(instrprof_error::zlib_unavailable);
 584
 585       if (Error E = compression::zlib::decompress(ArrayRef(P, CompressedSize),
 586                                                   UncompressedNameStrings,
 587                                                   UncompressedSize)) {
 588         consumeError(std::move(E));
 589         return make_error<InstrProfError>(instrprof_error::uncompress_failed);
 590       }
 591       P += CompressedSize;
 592       NameStrings = toStringRef(UncompressedNameStrings);
 593     } else {
 594       NameStrings =
 595           StringRef(reinterpret_cast<const char *>(P), UncompressedSize);
 596       P += UncompressedSize;
 597     }
 598     // Now parse the name strings.
 599     SmallVector<StringRef, 0> Names;
 600     NameStrings.split(Names, getInstrProfNameSeparator());
 601     for (StringRef &Name : Names)
 602       if (Error E = Symtab.addFuncName(Name))
 603         return E;
 604
 605     while (P < EndP && *P == 0)
 606       P++;
 607   }
 608   return Error::success();
 609 }
 610
 611 void InstrProfRecord::accumulateCounts(CountSumOrPercent &Sum) const {
 612   uint64_t FuncSum = 0;
 613   Sum.NumEntries += Counts.size();
 614   for (uint64_t Count : Counts)
 615     FuncSum += Count;
 616   Sum.CountSum += FuncSum;
 617
 618   for (uint32_t VK = IPVK_First; VK <= IPVK_Last; ++VK) {
 619     uint64_t KindSum = 0;
 620     uint32_t NumValueSites = getNumValueSites(VK);
 621     for (size_t I = 0; I < NumValueSites; ++I) {
 622       uint32_t NV = getNumValueDataForSite(VK, I);
 623       std::unique_ptr<InstrProfValueData[]> VD = getValueForSite(VK, I);
 624       for (uint32_t V = 0; V < NV; V++)
 625         KindSum += VD[V].Count;
 626     }
 627     Sum.ValueCounts[VK] += KindSum;
 628   }
 629 }
 630
 631 void InstrProfValueSiteRecord::overlap(InstrProfValueSiteRecord &Input,
 632                                        uint32_t ValueKind,
 633                                        OverlapStats &Overlap,
 634                                        OverlapStats &FuncLevelOverlap) {
 635   this->sortByTargetValues();
 636   Input.sortByTargetValues();
 637   double Score = 0.0f, FuncLevelScore = 0.0f;
 638   auto I = ValueData.begin();
 639   auto IE = ValueData.end();
 640   auto J = Input.ValueData.begin();
 641   auto JE = Input.ValueData.end();
 642   while (I != IE && J != JE) {
 643     if (I->Value == J->Value) {
 644       Score += OverlapStats::score(I->Count, J->Count,
 645                                    Overlap.Base.ValueCounts[ValueKind],
 646                                    Overlap.Test.ValueCounts[ValueKind]);
 647       FuncLevelScore += OverlapStats::score(
 648           I->Count, J->Count, FuncLevelOverlap.Base.ValueCounts[ValueKind],
 649           FuncLevelOverlap.Test.ValueCounts[ValueKind]);
 650       ++I;
 651     } else if (I->Value < J->Value) {
 652       ++I;
 653       continue;
 654     }
 655     ++J;
 656   }
 657   Overlap.Overlap.ValueCounts[ValueKind] += Score;
 658   FuncLevelOverlap.Overlap.ValueCounts[ValueKind] += FuncLevelScore;
 659 }
 660
 661 // Return false on mismatch.
 662 void InstrProfRecord::overlapValueProfData(uint32_t ValueKind,
 663                                            InstrProfRecord &Other,
 664                                            OverlapStats &Overlap,
 665                                            OverlapStats &FuncLevelOverlap) {
 666   uint32_t ThisNumValueSites = getNumValueSites(ValueKind);
 667   assert(ThisNumValueSites == Other.getNumValueSites(ValueKind));
 668   if (!ThisNumValueSites)
 669     return;
 670
 671   std::vector<InstrProfValueSiteRecord> &ThisSiteRecords =
 672       getOrCreateValueSitesForKind(ValueKind);
 673   MutableArrayRef<InstrProfValueSiteRecord> OtherSiteRecords =
 674       Other.getValueSitesForKind(ValueKind);
 675   for (uint32_t I = 0; I < ThisNumValueSites; I++)
 676     ThisSiteRecords[I].overlap(OtherSiteRecords[I], ValueKind, Overlap,
 677                                FuncLevelOverlap);
 678 }
 679
 680 void InstrProfRecord::overlap(InstrProfRecord &Other, OverlapStats &Overlap,
 681                               OverlapStats &FuncLevelOverlap,
 682                               uint64_t ValueCutoff) {
 683   // FuncLevel CountSum for other should already computed and nonzero.
 684   assert(FuncLevelOverlap.Test.CountSum >= 1.0f);
 685   accumulateCounts(FuncLevelOverlap.Base);
 686   bool Mismatch = (Counts.size() != Other.Counts.size());
 687
 688   // Check if the value profiles mismatch.
 689   if (!Mismatch) {
 690     for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind) {
 691       uint32_t ThisNumValueSites = getNumValueSites(Kind);
 692       uint32_t OtherNumValueSites = Other.getNumValueSites(Kind);
 693       if (ThisNumValueSites != OtherNumValueSites) {
 694         Mismatch = true;
 695         break;
 696       }
 697     }
 698   }
 699   if (Mismatch) {
 700     Overlap.addOneMismatch(FuncLevelOverlap.Test);
 701     return;
 702   }
 703
 704   // Compute overlap for value counts.
 705   for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
 706     overlapValueProfData(Kind, Other, Overlap, FuncLevelOverlap);
 707
 708   double Score = 0.0;
 709   uint64_t MaxCount = 0;
 710   // Compute overlap for edge counts.
 711   for (size_t I = 0, E = Other.Counts.size(); I < E; ++I) {
 712     Score += OverlapStats::score(Counts[I], Other.Counts[I],
 713                                  Overlap.Base.CountSum, Overlap.Test.CountSum);
 714     MaxCount = std::max(Other.Counts[I], MaxCount);
 715   }
 716   Overlap.Overlap.CountSum += Score;
 717   Overlap.Overlap.NumEntries += 1;
 718
 719   if (MaxCount >= ValueCutoff) {
 720     double FuncScore = 0.0;
 721     for (size_t I = 0, E = Other.Counts.size(); I < E; ++I)
 722       FuncScore += OverlapStats::score(Counts[I], Other.Counts[I],
 723                                        FuncLevelOverlap.Base.CountSum,
 724                                        FuncLevelOverlap.Test.CountSum);
 725     FuncLevelOverlap.Overlap.CountSum = FuncScore;
 726     FuncLevelOverlap.Overlap.NumEntries = Other.Counts.size();
 727     FuncLevelOverlap.Valid = true;
 728   }
 729 }
 730
 731 void InstrProfValueSiteRecord::merge(InstrProfValueSiteRecord &Input,
 732                                      uint64_t Weight,
 733                                      function_ref<void(instrprof_error)> Warn) {
 734   this->sortByTargetValues();
 735   Input.sortByTargetValues();
 736   auto I = ValueData.begin();
 737   auto IE = ValueData.end();
 738   for (const InstrProfValueData &J : Input.ValueData) {
 739     while (I != IE && I->Value < J.Value)
 740       ++I;
 741     if (I != IE && I->Value == J.Value) {
 742       bool Overflowed;
 743       I->Count = SaturatingMultiplyAdd(J.Count, Weight, I->Count, &Overflowed);
 744       if (Overflowed)
 745         Warn(instrprof_error::counter_overflow);
 746       ++I;
 747       continue;
 748     }
 749     ValueData.insert(I, J);
 750   }
 751 }
 752
 753 void InstrProfValueSiteRecord::scale(uint64_t N, uint64_t D,
 754                                      function_ref<void(instrprof_error)> Warn) {
 755   for (InstrProfValueData &I : ValueData) {
 756     bool Overflowed;
 757     I.Count = SaturatingMultiply(I.Count, N, &Overflowed) / D;
 758     if (Overflowed)
 759       Warn(instrprof_error::counter_overflow);
 760   }
 761 }
 762
 763 // Merge Value Profile data from Src record to this record for ValueKind.
 764 // Scale merged value counts by \p Weight.
 765 void InstrProfRecord::mergeValueProfData(
 766     uint32_t ValueKind, InstrProfRecord &Src, uint64_t Weight,
 767     function_ref<void(instrprof_error)> Warn) {
 768   uint32_t ThisNumValueSites = getNumValueSites(ValueKind);
 769   uint32_t OtherNumValueSites = Src.getNumValueSites(ValueKind);
 770   if (ThisNumValueSites != OtherNumValueSites) {
 771     Warn(instrprof_error::value_site_count_mismatch);
 772     return;
 773   }
 774   if (!ThisNumValueSites)
 775     return;
 776   std::vector<InstrProfValueSiteRecord> &ThisSiteRecords =
 777       getOrCreateValueSitesForKind(ValueKind);
 778   MutableArrayRef<InstrProfValueSiteRecord> OtherSiteRecords =
 779       Src.getValueSitesForKind(ValueKind);
 780   for (uint32_t I = 0; I < ThisNumValueSites; I++)
 781     ThisSiteRecords[I].merge(OtherSiteRecords[I], Weight, Warn);
 782 }
 783
 784 void InstrProfRecord::merge(InstrProfRecord &Other, uint64_t Weight,
 785                             function_ref<void(instrprof_error)> Warn) {
 786   // If the number of counters doesn't match we either have bad data
 787   // or a hash collision.
 788   if (Counts.size() != Other.Counts.size()) {
 789     Warn(instrprof_error::count_mismatch);
 790     return;
 791   }
 792
 793   // Special handling of the first count as the PseudoCount.
 794   CountPseudoKind OtherKind = Other.getCountPseudoKind();
 795   CountPseudoKind ThisKind = getCountPseudoKind();
 796   if (OtherKind != NotPseudo || ThisKind != NotPseudo) {
 797     // We don't allow the merge of a profile with pseudo counts and
 798     // a normal profile (i.e. without pesudo counts).
 799     // Profile supplimenation should be done after the profile merge.
 800     if (OtherKind == NotPseudo || ThisKind == NotPseudo) {
 801       Warn(instrprof_error::count_mismatch);
 802       return;
 803     }
 804     if (OtherKind == PseudoHot || ThisKind == PseudoHot)
 805       setPseudoCount(PseudoHot);
 806     else
 807       setPseudoCount(PseudoWarm);
 808     return;
 809   }
 810
 811   for (size_t I = 0, E = Other.Counts.size(); I < E; ++I) {
 812     bool Overflowed;
 813     uint64_t Value =
 814         SaturatingMultiplyAdd(Other.Counts[I], Weight, Counts[I], &Overflowed);
 815     if (Value > getInstrMaxCountValue()) {
 816       Value = getInstrMaxCountValue();
 817       Overflowed = true;
 818     }
 819     Counts[I] = Value;
 820     if (Overflowed)
 821       Warn(instrprof_error::counter_overflow);
 822   }
 823
 824   // If the number of bitmap bytes doesn't match we either have bad data
 825   // or a hash collision.
 826   if (BitmapBytes.size() != Other.BitmapBytes.size()) {
 827     Warn(instrprof_error::bitmap_mismatch);
 828     return;
 829   }
 830
 831   // Bitmap bytes are merged by simply ORing them together.
 832   for (size_t I = 0, E = Other.BitmapBytes.size(); I < E; ++I) {
 833     BitmapBytes[I] = Other.BitmapBytes[I] | BitmapBytes[I];
 834   }
 835
 836   for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
 837     mergeValueProfData(Kind, Other, Weight, Warn);
 838 }
 839
 840 void InstrProfRecord::scaleValueProfData(
 841     uint32_t ValueKind, uint64_t N, uint64_t D,
 842     function_ref<void(instrprof_error)> Warn) {
 843   for (auto &R : getValueSitesForKind(ValueKind))
 844     R.scale(N, D, Warn);
 845 }
 846
 847 void InstrProfRecord::scale(uint64_t N, uint64_t D,
 848                             function_ref<void(instrprof_error)> Warn) {
 849   assert(D != 0 && "D cannot be 0");
 850   for (auto &Count : this->Counts) {
 851     bool Overflowed;
 852     Count = SaturatingMultiply(Count, N, &Overflowed) / D;
 853     if (Count > getInstrMaxCountValue()) {
 854       Count = getInstrMaxCountValue();
 855       Overflowed = true;
 856     }
 857     if (Overflowed)
 858       Warn(instrprof_error::counter_overflow);
 859   }
 860   for (uint32_t Kind = IPVK_First; Kind <= IPVK_Last; ++Kind)
 861     scaleValueProfData(Kind, N, D, Warn);
 862 }
 863
 864 // Map indirect call target name hash to name string.
 865 uint64_t InstrProfRecord::remapValue(uint64_t Value, uint32_t ValueKind,
 866                                      InstrProfSymtab *SymTab) {
 867   if (!SymTab)
 868     return Value;
 869
 870   if (ValueKind == IPVK_IndirectCallTarget)
 871     return SymTab->getFunctionHashFromAddress(Value);
 872
 873   return Value;
 874 }
 875
 876 void InstrProfRecord::addValueData(uint32_t ValueKind, uint32_t Site,
 877                                    InstrProfValueData *VData, uint32_t N,
 878                                    InstrProfSymtab *ValueMap) {
 879   for (uint32_t I = 0; I < N; I++) {
 880     VData[I].Value = remapValue(VData[I].Value, ValueKind, ValueMap);
 881   }
 882   std::vector<InstrProfValueSiteRecord> &ValueSites =
 883       getOrCreateValueSitesForKind(ValueKind);
 884   if (N == 0)
 885     ValueSites.emplace_back();
 886   else
 887     ValueSites.emplace_back(VData, VData + N);
 888 }
 889
 890 std::vector<BPFunctionNode> TemporalProfTraceTy::createBPFunctionNodes(
 891     ArrayRef<TemporalProfTraceTy> Traces) {
 892   using IDT = BPFunctionNode::IDT;
 893   using UtilityNodeT = BPFunctionNode::UtilityNodeT;
 894   // Collect all function IDs ordered by their smallest timestamp. This will be
 895   // used as the initial FunctionNode order.
 896   SetVector<IDT> FunctionIds;
 897   size_t LargestTraceSize = 0;
 898   for (auto &Trace : Traces)
 899     LargestTraceSize =
 900         std::max(LargestTraceSize, Trace.FunctionNameRefs.size());
 901   for (size_t Timestamp = 0; Timestamp < LargestTraceSize; Timestamp++)
 902     for (auto &Trace : Traces)
 903       if (Timestamp < Trace.FunctionNameRefs.size())
 904         FunctionIds.insert(Trace.FunctionNameRefs[Timestamp]);
 905
 906   int N = std::ceil(std::log2(LargestTraceSize));
 907
 908   // TODO: We need to use the Trace.Weight field to give more weight to more
 909   // important utilities
 910   DenseMap<IDT, SmallVector<UtilityNodeT, 4>> FuncGroups;
 911   for (size_t TraceIdx = 0; TraceIdx < Traces.size(); TraceIdx++) {
 912     auto &Trace = Traces[TraceIdx].FunctionNameRefs;
 913     for (size_t Timestamp = 0; Timestamp < Trace.size(); Timestamp++) {
 914       for (int I = std::floor(std::log2(Timestamp + 1)); I < N; I++) {
 915         auto &FunctionId = Trace[Timestamp];
 916         UtilityNodeT GroupId = TraceIdx * N + I;
 917         FuncGroups[FunctionId].push_back(GroupId);
 918       }
 919     }
 920   }
 921
 922   std::vector<BPFunctionNode> Nodes;
 923   for (auto &Id : FunctionIds) {
 924     auto &UNs = FuncGroups[Id];
 925     llvm::sort(UNs);
 926     UNs.erase(std::unique(UNs.begin(), UNs.end()), UNs.end());
 927     Nodes.emplace_back(Id, UNs);
 928   }
 929   return Nodes;
 930 }
 931
 932 #define INSTR_PROF_COMMON_API_IMPL
 933 #include "llvm/ProfileData/InstrProfData.inc"
 934
 935 /*!
 936  * ValueProfRecordClosure Interface implementation for  InstrProfRecord
 937  *  class. These C wrappers are used as adaptors so that C++ code can be
 938  *  invoked as callbacks.
 939  */
 940 uint32_t getNumValueKindsInstrProf(const void *Record) {
 941   return reinterpret_cast<const InstrProfRecord *>(Record)->getNumValueKinds();
 942 }
 943
 944 uint32_t getNumValueSitesInstrProf(const void *Record, uint32_t VKind) {
 945   return reinterpret_cast<const InstrProfRecord *>(Record)
 946       ->getNumValueSites(VKind);
 947 }
 948
 949 uint32_t getNumValueDataInstrProf(const void *Record, uint32_t VKind) {
 950   return reinterpret_cast<const InstrProfRecord *>(Record)
 951       ->getNumValueData(VKind);
 952 }
 953
 954 uint32_t getNumValueDataForSiteInstrProf(const void *R, uint32_t VK,
 955                                          uint32_t S) {
 956   return reinterpret_cast<const InstrProfRecord *>(R)
 957       ->getNumValueDataForSite(VK, S);
 958 }
 959
 960 void getValueForSiteInstrProf(const void *R, InstrProfValueData *Dst,
 961                               uint32_t K, uint32_t S) {
 962   reinterpret_cast<const InstrProfRecord *>(R)->getValueForSite(Dst, K, S);
 963 }
 964
 965 ValueProfData *allocValueProfDataInstrProf(size_t TotalSizeInBytes) {
 966   ValueProfData *VD =
 967       (ValueProfData *)(new (::operator new(TotalSizeInBytes)) ValueProfData());
 968   memset(VD, 0, TotalSizeInBytes);
 969   return VD;
 970 }
 971
 972 static ValueProfRecordClosure InstrProfRecordClosure = {
 973     nullptr,
 974     getNumValueKindsInstrProf,
 975     getNumValueSitesInstrProf,
 976     getNumValueDataInstrProf,
 977     getNumValueDataForSiteInstrProf,
 978     nullptr,
 979     getValueForSiteInstrProf,
 980     allocValueProfDataInstrProf};
 981
 982 // Wrapper implementation using the closure mechanism.
 983 uint32_t ValueProfData::getSize(const InstrProfRecord &Record) {
 984   auto Closure = InstrProfRecordClosure;
 985   Closure.Record = &Record;
 986   return getValueProfDataSize(&Closure);
 987 }
 988
 989 // Wrapper implementation using the closure mechanism.
 990 std::unique_ptr<ValueProfData>
 991 ValueProfData::serializeFrom(const InstrProfRecord &Record) {
 992   InstrProfRecordClosure.Record = &Record;
 993
 994   std::unique_ptr<ValueProfData> VPD(
 995       serializeValueProfDataFrom(&InstrProfRecordClosure, nullptr));
 996   return VPD;
 997 }
 998
 999 void ValueProfRecord::deserializeTo(InstrProfRecord &Record,
1000                                     InstrProfSymtab *SymTab) {
1001   Record.reserveSites(Kind, NumValueSites);
1002
1003   InstrProfValueData *ValueData = getValueProfRecordValueData(this);
1004   for (uint64_t VSite = 0; VSite < NumValueSites; ++VSite) {
1005     uint8_t ValueDataCount = this->SiteCountArray[VSite];
1006     Record.addValueData(Kind, VSite, ValueData, ValueDataCount, SymTab);
1007     ValueData += ValueDataCount;
1008   }
1009 }
1010
1011 // For writing/serializing,  Old is the host endianness, and  New is
1012 // byte order intended on disk. For Reading/deserialization, Old
1013 // is the on-disk source endianness, and New is the host endianness.
1014 void ValueProfRecord::swapBytes(llvm::endianness Old, llvm::endianness New) {
1015   using namespace support;
1016
1017   if (Old == New)
1018     return;
1019
1020   if (llvm::endianness::native != Old) {
1021     sys::swapByteOrder<uint32_t>(NumValueSites);
1022     sys::swapByteOrder<uint32_t>(Kind);
1023   }
1024   uint32_t ND = getValueProfRecordNumValueData(this);
1025   InstrProfValueData *VD = getValueProfRecordValueData(this);
1026
1027   // No need to swap byte array: SiteCountArrray.
1028   for (uint32_t I = 0; I < ND; I++) {
1029     sys::swapByteOrder<uint64_t>(VD[I].Value);
1030     sys::swapByteOrder<uint64_t>(VD[I].Count);
1031   }
1032   if (llvm::endianness::native == Old) {
1033     sys::swapByteOrder<uint32_t>(NumValueSites);
1034     sys::swapByteOrder<uint32_t>(Kind);
1035   }
1036 }
1037
1038 void ValueProfData::deserializeTo(InstrProfRecord &Record,
1039                                   InstrProfSymtab *SymTab) {
1040   if (NumValueKinds == 0)
1041     return;
1042
1043   ValueProfRecord *VR = getFirstValueProfRecord(this);
1044   for (uint32_t K = 0; K < NumValueKinds; K++) {
1045     VR->deserializeTo(Record, SymTab);
1046     VR = getValueProfRecordNext(VR);
1047   }
1048 }
1049
1050 template <class T>
1051 static T swapToHostOrder(const unsigned char *&D, llvm::endianness Orig) {
1052   using namespace support;
1053
1054   if (Orig == llvm::endianness::little)
1055     return endian::readNext<T, llvm::endianness::little, unaligned>(D);
1056   else
1057     return endian::readNext<T, llvm::endianness::big, unaligned>(D);
1058 }
1059
1060 static std::unique_ptr<ValueProfData> allocValueProfData(uint32_t TotalSize) {
1061   return std::unique_ptr<ValueProfData>(new (::operator new(TotalSize))
1062                                             ValueProfData());
1063 }
1064
1065 Error ValueProfData::checkIntegrity() {
1066   if (NumValueKinds > IPVK_Last + 1)
1067     return make_error<InstrProfError>(
1068         instrprof_error::malformed, "number of value profile kinds is invalid");
1069   // Total size needs to be multiple of quadword size.
1070   if (TotalSize % sizeof(uint64_t))
1071     return make_error<InstrProfError>(
1072         instrprof_error::malformed, "total size is not multiples of quardword");
1073
1074   ValueProfRecord *VR = getFirstValueProfRecord(this);
1075   for (uint32_t K = 0; K < this->NumValueKinds; K++) {
1076     if (VR->Kind > IPVK_Last)
1077       return make_error<InstrProfError>(instrprof_error::malformed,
1078                                         "value kind is invalid");
1079     VR = getValueProfRecordNext(VR);
1080     if ((char *)VR - (char *)this > (ptrdiff_t)TotalSize)
1081       return make_error<InstrProfError>(
1082           instrprof_error::malformed,
1083           "value profile address is greater than total size");
1084   }
1085   return Error::success();
1086 }
1087
1088 Expected<std::unique_ptr<ValueProfData>>
1089 ValueProfData::getValueProfData(const unsigned char *D,
1090                                 const unsigned char *const BufferEnd,
1091                                 llvm::endianness Endianness) {
1092   using namespace support;
1093
1094   if (D + sizeof(ValueProfData) > BufferEnd)
1095     return make_error<InstrProfError>(instrprof_error::truncated);
1096
1097   const unsigned char *Header = D;
1098   uint32_t TotalSize = swapToHostOrder<uint32_t>(Header, Endianness);
1099   if (D + TotalSize > BufferEnd)
1100     return make_error<InstrProfError>(instrprof_error::too_large);
1101
1102   std::unique_ptr<ValueProfData> VPD = allocValueProfData(TotalSize);
1103   memcpy(VPD.get(), D, TotalSize);
1104   // Byte swap.
1105   VPD->swapBytesToHost(Endianness);
1106
1107   Error E = VPD->checkIntegrity();
1108   if (E)
1109     return std::move(E);
1110
1111   return std::move(VPD);
1112 }
1113
1114 void ValueProfData::swapBytesToHost(llvm::endianness Endianness) {
1115   using namespace support;
1116
1117   if (Endianness == llvm::endianness::native)
1118     return;
1119
1120   sys::swapByteOrder<uint32_t>(TotalSize);
1121   sys::swapByteOrder<uint32_t>(NumValueKinds);
1122
1123   ValueProfRecord *VR = getFirstValueProfRecord(this);
1124   for (uint32_t K = 0; K < NumValueKinds; K++) {
1125     VR->swapBytes(Endianness, llvm::endianness::native);
1126     VR = getValueProfRecordNext(VR);
1127   }
1128 }
1129
1130 void ValueProfData::swapBytesFromHost(llvm::endianness Endianness) {
1131   using namespace support;
1132
1133   if (Endianness == llvm::endianness::native)
1134     return;
1135
1136   ValueProfRecord *VR = getFirstValueProfRecord(this);
1137   for (uint32_t K = 0; K < NumValueKinds; K++) {
1138     ValueProfRecord *NVR = getValueProfRecordNext(VR);
1139     VR->swapBytes(llvm::endianness::native, Endianness);
1140     VR = NVR;
1141   }
1142   sys::swapByteOrder<uint32_t>(TotalSize);
1143   sys::swapByteOrder<uint32_t>(NumValueKinds);
1144 }
1145
1146 void annotateValueSite(Module &M, Instruction &Inst,
1147                        const InstrProfRecord &InstrProfR,
1148                        InstrProfValueKind ValueKind, uint32_t SiteIdx,
1149                        uint32_t MaxMDCount) {
1150   uint32_t NV = InstrProfR.getNumValueDataForSite(ValueKind, SiteIdx);
1151   if (!NV)
1152     return;
1153
1154   uint64_t Sum = 0;
1155   std::unique_ptr<InstrProfValueData[]> VD =
1156       InstrProfR.getValueForSite(ValueKind, SiteIdx, &Sum);
1157
1158   ArrayRef<InstrProfValueData> VDs(VD.get(), NV);
1159   annotateValueSite(M, Inst, VDs, Sum, ValueKind, MaxMDCount);
1160 }
1161
1162 void annotateValueSite(Module &M, Instruction &Inst,
1163                        ArrayRef<InstrProfValueData> VDs,
1164                        uint64_t Sum, InstrProfValueKind ValueKind,
1165                        uint32_t MaxMDCount) {
1166   LLVMContext &Ctx = M.getContext();
1167   MDBuilder MDHelper(Ctx);
1168   SmallVector<Metadata *, 3> Vals;
1169   // Tag
1170   Vals.push_back(MDHelper.createString("VP"));
1171   // Value Kind
1172   Vals.push_back(MDHelper.createConstant(
1173       ConstantInt::get(Type::getInt32Ty(Ctx), ValueKind)));
1174   // Total Count
1175   Vals.push_back(
1176       MDHelper.createConstant(ConstantInt::get(Type::getInt64Ty(Ctx), Sum)));
1177
1178   // Value Profile Data
1179   uint32_t MDCount = MaxMDCount;
1180   for (auto &VD : VDs) {
1181     Vals.push_back(MDHelper.createConstant(
1182         ConstantInt::get(Type::getInt64Ty(Ctx), VD.Value)));
1183     Vals.push_back(MDHelper.createConstant(
1184         ConstantInt::get(Type::getInt64Ty(Ctx), VD.Count)));
1185     if (--MDCount == 0)
1186       break;
1187   }
1188   Inst.setMetadata(LLVMContext::MD_prof, MDNode::get(Ctx, Vals));
1189 }
1190
1191 bool getValueProfDataFromInst(const Instruction &Inst,
1192                               InstrProfValueKind ValueKind,
1193                               uint32_t MaxNumValueData,
1194                               InstrProfValueData ValueData[],
1195                               uint32_t &ActualNumValueData, uint64_t &TotalC,
1196                               bool GetNoICPValue) {
1197   MDNode *MD = Inst.getMetadata(LLVMContext::MD_prof);
1198   if (!MD)
1199     return false;
1200
1201   unsigned NOps = MD->getNumOperands();
1202
1203   if (NOps < 5)
1204     return false;
1205
1206   // Operand 0 is a string tag "VP":
1207   MDString *Tag = cast<MDString>(MD->getOperand(0));
1208   if (!Tag)
1209     return false;
1210
1211   if (!Tag->getString().equals("VP"))
1212     return false;
1213
1214   // Now check kind:
1215   ConstantInt *KindInt = mdconst::dyn_extract<ConstantInt>(MD->getOperand(1));
1216   if (!KindInt)
1217     return false;
1218   if (KindInt->getZExtValue() != ValueKind)
1219     return false;
1220
1221   // Get total count
1222   ConstantInt *TotalCInt = mdconst::dyn_extract<ConstantInt>(MD->getOperand(2));
1223   if (!TotalCInt)
1224     return false;
1225   TotalC = TotalCInt->getZExtValue();
1226
1227   ActualNumValueData = 0;
1228
1229   for (unsigned I = 3; I < NOps; I += 2) {
1230     if (ActualNumValueData >= MaxNumValueData)
1231       break;
1232     ConstantInt *Value = mdconst::dyn_extract<ConstantInt>(MD->getOperand(I));
1233     ConstantInt *Count =
1234         mdconst::dyn_extract<ConstantInt>(MD->getOperand(I + 1));
1235     if (!Value || !Count)
1236       return false;
1237     uint64_t CntValue = Count->getZExtValue();
1238     if (!GetNoICPValue && (CntValue == NOMORE_ICP_MAGICNUM))
1239       continue;
1240     ValueData[ActualNumValueData].Value = Value->getZExtValue();
1241     ValueData[ActualNumValueData].Count = CntValue;
1242     ActualNumValueData++;
1243   }
1244   return true;
1245 }
1246
1247 MDNode *getPGOFuncNameMetadata(const Function &F) {
1248   return F.getMetadata(getPGOFuncNameMetadataName());
1249 }
1250
1251 void createPGOFuncNameMetadata(Function &F, StringRef PGOFuncName) {
1252   // Only for internal linkage functions.
1253   if (PGOFuncName == F.getName())
1254       return;
1255   // Don't create duplicated meta-data.
1256   if (getPGOFuncNameMetadata(F))
1257     return;
1258   LLVMContext &C = F.getContext();
1259   MDNode *N = MDNode::get(C, MDString::get(C, PGOFuncName));
1260   F.setMetadata(getPGOFuncNameMetadataName(), N);
1261 }
1262
1263 bool needsComdatForCounter(const Function &F, const Module &M) {
1264   if (F.hasComdat())
1265     return true;
1266
1267   if (!Triple(M.getTargetTriple()).supportsCOMDAT())
1268     return false;
1269
1270   // See createPGOFuncNameVar for more details. To avoid link errors, profile
1271   // counters for function with available_externally linkage needs to be changed
1272   // to linkonce linkage. On ELF based systems, this leads to weak symbols to be
1273   // created. Without using comdat, duplicate entries won't be removed by the
1274   // linker leading to increased data segement size and raw profile size. Even
1275   // worse, since the referenced counter from profile per-function data object
1276   // will be resolved to the common strong definition, the profile counts for
1277   // available_externally functions will end up being duplicated in raw profile
1278   // data. This can result in distorted profile as the counts of those dups
1279   // will be accumulated by the profile merger.
1280   GlobalValue::LinkageTypes Linkage = F.getLinkage();
1281   if (Linkage != GlobalValue::ExternalWeakLinkage &&
1282       Linkage != GlobalValue::AvailableExternallyLinkage)
1283     return false;
1284
1285   return true;
1286 }
1287
1288 // Check if INSTR_PROF_RAW_VERSION_VAR is defined.
1289 bool isIRPGOFlagSet(const Module *M) {
1290   auto IRInstrVar =
1291       M->getNamedGlobal(INSTR_PROF_QUOTE(INSTR_PROF_RAW_VERSION_VAR));
1292   if (!IRInstrVar || IRInstrVar->hasLocalLinkage())
1293     return false;
1294
1295   // For CSPGO+LTO, this variable might be marked as non-prevailing and we only
1296   // have the decl.
1297   if (IRInstrVar->isDeclaration())
1298     return true;
1299
1300   // Check if the flag is set.
1301   if (!IRInstrVar->hasInitializer())
1302     return false;
1303
1304   auto *InitVal = dyn_cast_or_null<ConstantInt>(IRInstrVar->getInitializer());
1305   if (!InitVal)
1306     return false;
1307   return (InitVal->getZExtValue() & VARIANT_MASK_IR_PROF) != 0;
1308 }
1309
1310 // Check if we can safely rename this Comdat function.
1311 bool canRenameComdatFunc(const Function &F, bool CheckAddressTaken) {
1312   if (F.getName().empty())
1313     return false;
1314   if (!needsComdatForCounter(F, *(F.getParent())))
1315     return false;
1316   // Unsafe to rename the address-taken function (which can be used in
1317   // function comparison).
1318   if (CheckAddressTaken && F.hasAddressTaken())
1319     return false;
1320   // Only safe to do if this function may be discarded if it is not used
1321   // in the compilation unit.
1322   if (!GlobalValue::isDiscardableIfUnused(F.getLinkage()))
1323     return false;
1324
1325   // For AvailableExternallyLinkage functions.
1326   if (!F.hasComdat()) {
1327     assert(F.getLinkage() == GlobalValue::AvailableExternallyLinkage);
1328     return true;
1329   }
1330   return true;
1331 }
1332
1333 // Create the variable for the profile file name.
1334 void createProfileFileNameVar(Module &M, StringRef InstrProfileOutput) {
1335   if (InstrProfileOutput.empty())
1336     return;
1337   Constant *ProfileNameConst =
1338       ConstantDataArray::getString(M.getContext(), InstrProfileOutput, true);
1339   GlobalVariable *ProfileNameVar = new GlobalVariable(
1340       M, ProfileNameConst->getType(), true, GlobalValue::WeakAnyLinkage,
1341       ProfileNameConst, INSTR_PROF_QUOTE(INSTR_PROF_PROFILE_NAME_VAR));
1342   ProfileNameVar->setVisibility(GlobalValue::HiddenVisibility);
1343   Triple TT(M.getTargetTriple());
1344   if (TT.supportsCOMDAT()) {
1345     ProfileNameVar->setLinkage(GlobalValue::ExternalLinkage);
1346     ProfileNameVar->setComdat(M.getOrInsertComdat(
1347         StringRef(INSTR_PROF_QUOTE(INSTR_PROF_PROFILE_NAME_VAR))));
1348   }
1349 }
1350
1351 Error OverlapStats::accumulateCounts(const std::string &BaseFilename,
1352                                      const std::string &TestFilename,
1353                                      bool IsCS) {
1354   auto getProfileSum = [IsCS](const std::string &Filename,
1355                               CountSumOrPercent &Sum) -> Error {
1356     // This function is only used from llvm-profdata that doesn't use any kind
1357     // of VFS. Just create a default RealFileSystem to read profiles.
1358     auto FS = vfs::getRealFileSystem();
1359     auto ReaderOrErr = InstrProfReader::create(Filename, *FS);
1360     if (Error E = ReaderOrErr.takeError()) {
1361       return E;
1362     }
1363     auto Reader = std::move(ReaderOrErr.get());
1364     Reader->accumulateCounts(Sum, IsCS);
1365     return Error::success();
1366   };
1367   auto Ret = getProfileSum(BaseFilename, Base);
1368   if (Ret)
1369     return Ret;
1370   Ret = getProfileSum(TestFilename, Test);
1371   if (Ret)
1372     return Ret;
1373   this->BaseFilename = &BaseFilename;
1374   this->TestFilename = &TestFilename;
1375   Valid = true;
1376   return Error::success();
1377 }
1378
1379 void OverlapStats::addOneMismatch(const CountSumOrPercent &MismatchFunc) {
1380   Mismatch.NumEntries += 1;
1381   Mismatch.CountSum += MismatchFunc.CountSum / Test.CountSum;
1382   for (unsigned I = 0; I < IPVK_Last - IPVK_First + 1; I++) {
1383     if (Test.ValueCounts[I] >= 1.0f)
1384       Mismatch.ValueCounts[I] +=
1385           MismatchFunc.ValueCounts[I] / Test.ValueCounts[I];
1386   }
1387 }
1388
1389 void OverlapStats::addOneUnique(const CountSumOrPercent &UniqueFunc) {
1390   Unique.NumEntries += 1;
1391   Unique.CountSum += UniqueFunc.CountSum / Test.CountSum;
1392   for (unsigned I = 0; I < IPVK_Last - IPVK_First + 1; I++) {
1393     if (Test.ValueCounts[I] >= 1.0f)
1394       Unique.ValueCounts[I] += UniqueFunc.ValueCounts[I] / Test.ValueCounts[I];
1395   }
1396 }
1397
1398 void OverlapStats::dump(raw_fd_ostream &OS) const {
1399   if (!Valid)
1400     return;
1401
1402   const char *EntryName =
1403       (Level == ProgramLevel ? "functions" : "edge counters");
1404   if (Level == ProgramLevel) {
1405     OS << "Profile overlap infomation for base_profile: " << *BaseFilename
1406        << " and test_profile: " << *TestFilename << "\nProgram level:\n";
1407   } else {
1408     OS << "Function level:\n"
1409        << "  Function: " << FuncName << " (Hash=" << FuncHash << ")\n";
1410   }
1411
1412   OS << "  # of " << EntryName << " overlap: " << Overlap.NumEntries << "\n";
1413   if (Mismatch.NumEntries)
1414     OS << "  # of " << EntryName << " mismatch: " << Mismatch.NumEntries
1415        << "\n";
1416   if (Unique.NumEntries)
1417     OS << "  # of " << EntryName
1418        << " only in test_profile: " << Unique.NumEntries << "\n";
1419
1420   OS << "  Edge profile overlap: " << format("%.3f%%", Overlap.CountSum * 100)
1421      << "\n";
1422   if (Mismatch.NumEntries)
1423     OS << "  Mismatched count percentage (Edge): "
1424        << format("%.3f%%", Mismatch.CountSum * 100) << "\n";
1425   if (Unique.NumEntries)
1426     OS << "  Percentage of Edge profile only in test_profile: "
1427        << format("%.3f%%", Unique.CountSum * 100) << "\n";
1428   OS << "  Edge profile base count sum: " << format("%.0f", Base.CountSum)
1429      << "\n"
1430      << "  Edge profile test count sum: " << format("%.0f", Test.CountSum)
1431      << "\n";
1432
1433   for (unsigned I = 0; I < IPVK_Last - IPVK_First + 1; I++) {
1434     if (Base.ValueCounts[I] < 1.0f && Test.ValueCounts[I] < 1.0f)
1435       continue;
1436     char ProfileKindName[20];
1437     switch (I) {
1438     case IPVK_IndirectCallTarget:
1439       strncpy(ProfileKindName, "IndirectCall", 19);
1440       break;
1441     case IPVK_MemOPSize:
1442       strncpy(ProfileKindName, "MemOP", 19);
1443       break;
1444     default:
1445       snprintf(ProfileKindName, 19, "VP[%d]", I);
1446       break;
1447     }
1448     OS << "  " << ProfileKindName
1449        << " profile overlap: " << format("%.3f%%", Overlap.ValueCounts[I] * 100)
1450        << "\n";
1451     if (Mismatch.NumEntries)
1452       OS << "  Mismatched count percentage (" << ProfileKindName
1453          << "): " << format("%.3f%%", Mismatch.ValueCounts[I] * 100) << "\n";
1454     if (Unique.NumEntries)
1455       OS << "  Percentage of " << ProfileKindName
1456          << " profile only in test_profile: "
1457          << format("%.3f%%", Unique.ValueCounts[I] * 100) << "\n";
1458     OS << "  " << ProfileKindName
1459        << " profile base count sum: " << format("%.0f", Base.ValueCounts[I])
1460        << "\n"
1461        << "  " << ProfileKindName
1462        << " profile test count sum: " << format("%.0f", Test.ValueCounts[I])
1463        << "\n";
1464   }
1465 }
1466
1467 namespace IndexedInstrProf {
1468 // A C++14 compatible version of the offsetof macro.
1469 template <typename T1, typename T2>
1470 inline size_t constexpr offsetOf(T1 T2::*Member) {
1471   constexpr T2 Object{};
1472   return size_t(&(Object.*Member)) - size_t(&Object);
1473 }
1474
1475 static inline uint64_t read(const unsigned char *Buffer, size_t Offset) {
1476   return *reinterpret_cast<const uint64_t *>(Buffer + Offset);
1477 }
1478
1479 uint64_t Header::formatVersion() const {
1480   using namespace support;
1481   return endian::byte_swap<uint64_t, llvm::endianness::little>(Version);
1482 }
1483
1484 Expected<Header> Header::readFromBuffer(const unsigned char *Buffer) {
1485   using namespace support;
1486   static_assert(std::is_standard_layout_v<Header>,
1487                 "The header should be standard layout type since we use offset "
1488                 "of fields to read.");
1489   Header H;
1490
1491   H.Magic = read(Buffer, offsetOf(&Header::Magic));
1492   // Check the magic number.
1493   uint64_t Magic =
1494       endian::byte_swap<uint64_t, llvm::endianness::little>(H.Magic);
1495   if (Magic != IndexedInstrProf::Magic)
1496     return make_error<InstrProfError>(instrprof_error::bad_magic);
1497
1498   // Read the version.
1499   H.Version = read(Buffer, offsetOf(&Header::Version));
1500   if (GET_VERSION(H.formatVersion()) >
1501       IndexedInstrProf::ProfVersion::CurrentVersion)
1502     return make_error<InstrProfError>(instrprof_error::unsupported_version);
1503
1504   switch (GET_VERSION(H.formatVersion())) {
1505     // When a new field is added in the header add a case statement here to
1506     // populate it.
1507     static_assert(
1508         IndexedInstrProf::ProfVersion::CurrentVersion == Version11,
1509         "Please update the reading code below if a new field has been added, "
1510         "if not add a case statement to fall through to the latest version.");
1511   case 11ull:
1512     [[fallthrough]];
1513   case 10ull:
1514     H.TemporalProfTracesOffset =
1515         read(Buffer, offsetOf(&Header::TemporalProfTracesOffset));
1516     [[fallthrough]];
1517   case 9ull:
1518     H.BinaryIdOffset = read(Buffer, offsetOf(&Header::BinaryIdOffset));
1519     [[fallthrough]];
1520   case 8ull:
1521     H.MemProfOffset = read(Buffer, offsetOf(&Header::MemProfOffset));
1522     [[fallthrough]];
1523   default: // Version7 (when the backwards compatible header was introduced).
1524     H.HashType = read(Buffer, offsetOf(&Header::HashType));
1525     H.HashOffset = read(Buffer, offsetOf(&Header::HashOffset));
1526   }
1527
1528   return H;
1529 }
1530
1531 size_t Header::size() const {
1532   switch (GET_VERSION(formatVersion())) {
1533     // When a new field is added to the header add a case statement here to
1534     // compute the size as offset of the new field + size of the new field. This
1535     // relies on the field being added to the end of the list.
1536     static_assert(IndexedInstrProf::ProfVersion::CurrentVersion == Version11,
1537                   "Please update the size computation below if a new field has "
1538                   "been added to the header, if not add a case statement to "
1539                   "fall through to the latest version.");
1540   case 11ull:
1541     [[fallthrough]];
1542   case 10ull:
1543     return offsetOf(&Header::TemporalProfTracesOffset) +
1544            sizeof(Header::TemporalProfTracesOffset);
1545   case 9ull:
1546     return offsetOf(&Header::BinaryIdOffset) + sizeof(Header::BinaryIdOffset);
1547   case 8ull:
1548     return offsetOf(&Header::MemProfOffset) + sizeof(Header::MemProfOffset);
1549   default: // Version7 (when the backwards compatible header was introduced).
1550     return offsetOf(&Header::HashOffset) + sizeof(Header::HashOffset);
1551   }
1552 }
1553
1554 } // namespace IndexedInstrProf
1555
1556 } // end namespace llvm