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

source code of llvm/lib/ProfileData/InstrProf.cpp