/build/source/bolt/runtime/instr.cpp

Bug Summary

File:	bolt/runtime/instr.cpp
Warning:	line 666, column 10 Branch condition evaluates to a garbage value

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name instr.cpp -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -fhalf-no-semantic-interposition -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -ffreestanding -target-cpu x86-64 -target-feature -x87 -target-feature -mmx -target-feature -sse -tune-cpu generic -debugger-tuning=gdb -fdebug-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins/tools/bolt/bolt_rt-bins -fcoverage-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins/tools/bolt/bolt_rt-bins -resource-dir /usr/lib/llvm-18/lib/clang/18 -I . -D NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-18/lib/clang/18/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -source-date-epoch 1695640452 -O3 -std=c++17 -fdeprecated-macro -ferror-limit 19 -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2023-09-25-133158-16089-1 -x c++ /build/source/bolt/runtime/instr.cpp

/build/source/bolt/runtime/instr.cpp

→

1//===- bolt/runtime/instr.cpp ---------------------------------------------===//
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// BOLT runtime instrumentation library for x86 Linux. Currently, BOLT does
10// not support linking modules with dependencies on one another into the final
11// binary (TODO?), which means this library has to be self-contained in a single
12// module.
13//
14// All extern declarations here need to be defined by BOLT itself. Those will be
15// undefined symbols that BOLT needs to resolve by emitting these symbols with
16// MCStreamer. Currently, Passes/Instrumentation.cpp is the pass responsible
17// for defining the symbols here and these two files have a tight coupling: one
18// working statically when you run BOLT and another during program runtime when
19// you run an instrumented binary. The main goal here is to output an fdata file
20// (BOLT profile) with the instrumentation counters inserted by the static pass.
21// Counters for indirect calls are an exception, as we can't know them
22// statically. These counters are created and managed here. To allow this, we
23// need a minimal framework for allocating memory dynamically. We provide this
24// with the BumpPtrAllocator class (not LLVM's, but our own version of it).
25//
26// Since this code is intended to be inserted into any executable, we decided to
27// make it standalone and do not depend on any external libraries (i.e. language
28// support libraries, such as glibc or stdc++). To allow this, we provide a few
29// light implementations of common OS interacting functionalities using direct
30// syscall wrappers. Our simple allocator doesn't manage deallocations that
31// fragment the memory space, so it's stack based. This is the minimal framework
32// provided here to allow processing instrumented counters and writing fdata.
33//
34// In the C++ idiom used here, we never use or rely on constructors or
35// destructors for global objects. That's because those need support from the
36// linker in initialization/finalization code, and we want to keep our linker
37// very simple. Similarly, we don't create any global objects that are zero
38// initialized, since those would need to go .bss, which our simple linker also
39// don't support (TODO?).
40//
41//===----------------------------------------------------------------------===//

43#include "common.h"

45// Enables a very verbose logging to stderr useful when debugging
46//#define ENABLE_DEBUG

48#ifdef ENABLE_DEBUG
49#define DEBUG(X){}                                                               \
{ X; }
51#else
52#define DEBUG(X){}                                                               \
{}
54#endif

56#pragma GCC visibility push(hidden)

58extern "C" {

60#if defined(__APPLE__)
61extern uint64_t* _bolt_instr_locations_getter();
62extern uint32_t _bolt_num_counters_getter();

64extern uint8_t* _bolt_instr_tables_getter();
65extern uint32_t _bolt_instr_num_funcs_getter();

67#else

69// Main counters inserted by instrumentation, incremented during runtime when
70// points of interest (locations) in the program are reached. Those are direct
71// calls and direct and indirect branches (local ones). There are also counters
72// for basic block execution if they are a spanning tree leaf and need to be
73// counted in order to infer the execution count of other edges of the CFG.
74extern uint64_t __bolt_instr_locations[];
75extern uint32_t __bolt_num_counters;
76// Descriptions are serialized metadata about binary functions written by BOLT,
77// so we have a minimal understanding about the program structure. For a
78// reference on the exact format of this metadata, see *Description structs,
79// Location, IntrumentedNode and EntryNode.
80// Number of indirect call site descriptions
81extern uint32_t __bolt_instr_num_ind_calls;
82// Number of indirect call target descriptions
83extern uint32_t __bolt_instr_num_ind_targets;
84// Number of function descriptions
85extern uint32_t __bolt_instr_num_funcs;
86// Time to sleep across dumps (when we write the fdata profile to disk)
87extern uint32_t __bolt_instr_sleep_time;
88// Do not clear counters across dumps, rewrite file with the updated values
89extern bool __bolt_instr_no_counters_clear;
90// Wait until all forks of instrumented process will finish
91extern bool __bolt_instr_wait_forks;
92// Filename to dump data to
93extern char __bolt_instr_filename[];
94// Instumented binary file path
95extern char __bolt_instr_binpath[];
96// If true, append current PID to the fdata filename when creating it so
97// different invocations of the same program can be differentiated.
98extern bool __bolt_instr_use_pid;
99// Functions that will be used to instrument indirect calls. BOLT static pass
100// will identify indirect calls and modify them to load the address in these
101// trampolines and call this address instead. BOLT can't use direct calls to
102// our handlers because our addresses here are not known at analysis time. We
103// only support resolving dependencies from this file to the output of BOLT,
104// *not* the other way around.
105// TODO: We need better linking support to make that happen.
106extern void (*__bolt_ind_call_counter_func_pointer)();
107extern void (*__bolt_ind_tailcall_counter_func_pointer)();
108// Function pointers to init/fini trampoline routines in the binary, so we can
109// resume regular execution of these functions that we hooked
110extern void __bolt_start_trampoline();
111extern void __bolt_fini_trampoline();

113#endif
114}

116namespace {

118/// A simple allocator that mmaps a fixed size region and manages this space
119/// in a stack fashion, meaning you always deallocate the last element that
120/// was allocated. In practice, we don't need to deallocate individual elements.
121/// We monotonically increase our usage and then deallocate everything once we
122/// are done processing something.
123class BumpPtrAllocator {
/// This is written before each allocation and act as a canary to detect when
/// a bug caused our program to cross allocation boundaries.
struct EntryMetadata {
  uint64_t Magic;
  uint64_t AllocSize;
};

131public:
void *allocate(size_t Size) {
  Lock L(M);

  if (StackBase == nullptr) {
    StackBase = reinterpret_cast<uint8_t *>(
        __mmap(0, MaxSize, PROT_READ0x1 | PROT_WRITE0x2,
               (Shared ? MAP_SHARED0x01 : MAP_PRIVATE0x02) | MAP_ANONYMOUS0x20, -1, 0));
    assert(StackBase != MAP_FAILED((void *)-1),
           "BumpPtrAllocator: failed to mmap stack!");
    StackSize = 0;
  }

  Size = alignTo(Size + sizeof(EntryMetadata), 16);
  uint8_t *AllocAddress = StackBase + StackSize + sizeof(EntryMetadata);
  auto *M = reinterpret_cast<EntryMetadata *>(StackBase + StackSize);
  M->Magic = Magic;
  M->AllocSize = Size;
  StackSize += Size;
  assert(StackSize < MaxSize, "allocator ran out of memory");
  return AllocAddress;
}

154#ifdef DEBUG
/// Element-wise deallocation is only used for debugging to catch memory
/// bugs by checking magic bytes. Ordinarily, we reset the allocator once
/// we are done with it. Reset is done with clear(). There's no need
/// to deallocate each element individually.
void deallocate(void *Ptr) {
  Lock L(M);
  uint8_t MetadataOffset = sizeof(EntryMetadata);
  auto *M = reinterpret_cast<EntryMetadata *>(
      reinterpret_cast<uint8_t *>(Ptr) - MetadataOffset);
  const uint8_t *StackTop = StackBase + StackSize + MetadataOffset;
  // Validate size
  if (Ptr != StackTop - M->AllocSize) {
    // Failed validation, check if it is a pointer returned by operator new []
    MetadataOffset +=
        sizeof(uint64_t); // Space for number of elements alloc'ed
    M = reinterpret_cast<EntryMetadata *>(reinterpret_cast<uint8_t *>(Ptr) -
                                          MetadataOffset);
    // Ok, it failed both checks if this assertion fails. Stop the program, we
    // have a memory bug.
    assert(Ptr == StackTop - M->AllocSize,
           "must deallocate the last element alloc'ed");
  }
  assert(M->Magic == Magic, "allocator magic is corrupt");
  StackSize -= M->AllocSize;
}
180#else
void deallocate(void *) {}
182#endif

void clear() {
  Lock L(M);
  StackSize = 0;
}

/// Set mmap reservation size (only relevant before first allocation)
void setMaxSize(uint64_t Size) { MaxSize = Size; }

/// Set mmap reservation privacy (only relevant before first allocation)
void setShared(bool S) { Shared = S; }

void destroy() {
  if (StackBase == nullptr)
    return;
  __munmap(StackBase, MaxSize);
}

// Placement operator to construct allocator in possibly shared mmaped memory
static void *operator new(size_t, void *Ptr) { return Ptr; };

204private:
static constexpr uint64_t Magic = 0x1122334455667788ull;
uint64_t MaxSize = 0xa00000;
uint8_t *StackBase{nullptr};
uint64_t StackSize{0};
bool Shared{false};
Mutex M;
211};

213/// Used for allocating indirect call instrumentation counters. Initialized by
214/// __bolt_instr_setup, our initialization routine.
215BumpPtrAllocator *GlobalAlloc;

217// Base address which we substract from recorded PC values when searching for
218// indirect call description entries. Needed because indCall descriptions are
219// mapped read-only and contain static addresses. Initialized in
220// __bolt_instr_setup.
221uint64_t TextBaseAddress = 0;

223// Storage for GlobalAlloc which can be shared if not using
224// instrumentation-file-append-pid.
225void *GlobalMetadataStorage;

227} // anonymous namespace

229// User-defined placement new operators. We only use those (as opposed to
230// overriding the regular operator new) so we can keep our allocator in the
231// stack instead of in a data section (global).
232void *operator new(size_t Sz, BumpPtrAllocator &A) { return A.allocate(Sz); }
233void *operator new(size_t Sz, BumpPtrAllocator &A, char C) {
auto *Ptr = reinterpret_cast<char *>(A.allocate(Sz));
memset(Ptr, C, Sz);
return Ptr;
237}
238void *operator new[](size_t Sz, BumpPtrAllocator &A) {
return A.allocate(Sz);
240}
241void *operator new[](size_t Sz, BumpPtrAllocator &A, char C) {
auto *Ptr = reinterpret_cast<char *>(A.allocate(Sz));
memset(Ptr, C, Sz);
return Ptr;
245}
246// Only called during exception unwinding (useless). We must manually dealloc.
247// C++ language weirdness
248void operator delete(void *Ptr, BumpPtrAllocator &A) { A.deallocate(Ptr); }

250namespace {

252// Disable instrumentation optimizations that sacrifice profile accuracy
253extern "C" bool __bolt_instr_conservative;

255/// Basic key-val atom stored in our hash
256struct SimpleHashTableEntryBase {
uint64_t Key;
uint64_t Val;
void dump(const char *Msg = nullptr) {
  // TODO: make some sort of formatting function
  // Currently we have to do it the ugly way because
  // we want every message to be printed atomically via a single call to
  // __write. If we use reportNumber() and others nultiple times, we'll get
  // garbage in mulithreaded environment
  char Buf[BufSize];
  char *Ptr = Buf;
  Ptr = intToStr(Ptr, __getpid(), 10);
  *Ptr++ = ':';
  *Ptr++ = ' ';
  if (Msg)
    Ptr = strCopy(Ptr, Msg, strLen(Msg));
  *Ptr++ = '0';
  *Ptr++ = 'x';
  Ptr = intToStr(Ptr, (uint64_t)this, 16);
  *Ptr++ = ':';
  *Ptr++ = ' ';
  Ptr = strCopy(Ptr, "MapEntry(0x", sizeof("MapEntry(0x") - 1);
  Ptr = intToStr(Ptr, Key, 16);
  *Ptr++ = ',';
  *Ptr++ = ' ';
  *Ptr++ = '0';
  *Ptr++ = 'x';
  Ptr = intToStr(Ptr, Val, 16);
  *Ptr++ = ')';
  *Ptr++ = '\n';
  assert(Ptr - Buf < BufSize, "Buffer overflow!");
  // print everything all at once for atomicity
  __write(2, Buf, Ptr - Buf);
}
290};

292/// This hash table implementation starts by allocating a table of size
293/// InitialSize. When conflicts happen in this main table, it resolves
294/// them by chaining a new table of size IncSize. It never reallocs as our
295/// allocator doesn't support it. The key is intended to be function pointers.
296/// There's no clever hash function (it's just x mod size, size being prime).
297/// I never tuned the coefficientes in the modular equation (TODO)
298/// This is used for indirect calls (each call site has one of this, so it
299/// should have a small footprint) and for tallying call counts globally for
300/// each target to check if we missed the origin of some calls (this one is a
301/// large instantiation of this template, since it is global for all call sites)
302template <typename T = SimpleHashTableEntryBase, uint32_t InitialSize = 7,
        uint32_t IncSize = 7>
304class SimpleHashTable {
305public:
using MapEntry = T;

/// Increment by 1 the value of \p Key. If it is not in this table, it will be
/// added to the table and its value set to 1.
void incrementVal(uint64_t Key, BumpPtrAllocator &Alloc) {
  if (!__bolt_instr_conservative) {
    TryLock L(M);
    if (!L.isLocked())
      return;
    auto &E = getOrAllocEntry(Key, Alloc);
    ++E.Val;
    return;
  }
  Lock L(M);
  auto &E = getOrAllocEntry(Key, Alloc);
  ++E.Val;
}

/// Basic member accessing interface. Here we pass the allocator explicitly to
/// avoid storing a pointer to it as part of this table (remember there is one
/// hash for each indirect call site, so we wan't to minimize our footprint).
MapEntry &get(uint64_t Key, BumpPtrAllocator &Alloc) {
  if (!__bolt_instr_conservative) {
    TryLock L(M);
    if (!L.isLocked())
      return NoEntry;
    return getOrAllocEntry(Key, Alloc);
  }
  Lock L(M);
  return getOrAllocEntry(Key, Alloc);
}

/// Traverses all elements in the table
template <typename... Args>
void forEachElement(void (*Callback)(MapEntry &, Args...), Args... args) {
  Lock L(M);
  if (!TableRoot)
    return;
  return forEachElement(Callback, InitialSize, TableRoot, args...);
}

void resetCounters();

349private:
constexpr static uint64_t VacantMarker = 0;
constexpr static uint64_t FollowUpTableMarker = 0x8000000000000000ull;

MapEntry *TableRoot{nullptr};
MapEntry NoEntry;
Mutex M;

template <typename... Args>
void forEachElement(void (*Callback)(MapEntry &, Args...),
                    uint32_t NumEntries, MapEntry *Entries, Args... args) {
  for (uint32_t I = 0; I < NumEntries; ++I) {
    MapEntry &Entry = Entries[I];
    if (Entry.Key == VacantMarker)
      continue;
    if (Entry.Key & FollowUpTableMarker) {
      MapEntry *Next =
          reinterpret_cast<MapEntry *>(Entry.Key & ~FollowUpTableMarker);
      assert(Next != Entries, "Circular reference!");
      forEachElement(Callback, IncSize, Next, args...);
      continue;
    }
    Callback(Entry, args...);
  }
}

MapEntry &firstAllocation(uint64_t Key, BumpPtrAllocator &Alloc) {
  TableRoot = new (Alloc, 0) MapEntry[InitialSize];
  MapEntry &Entry = TableRoot[Key % InitialSize];
  Entry.Key = Key;
  // DEBUG(Entry.dump("Created root entry: "));
  return Entry;
}

MapEntry &getEntry(MapEntry *Entries, uint64_t Key, uint64_t Selector,
                   BumpPtrAllocator &Alloc, int CurLevel) {
  // DEBUG(reportNumber("getEntry called, level ", CurLevel, 10));
  const uint32_t NumEntries = CurLevel == 0 ? InitialSize : IncSize;
  uint64_t Remainder = Selector / NumEntries;
  Selector = Selector % NumEntries;
  MapEntry &Entry = Entries[Selector];

  // A hit
  if (Entry.Key == Key) {
    // DEBUG(Entry.dump("Hit: "));
    return Entry;
  }

  // Vacant - add new entry
  if (Entry.Key == VacantMarker) {
    Entry.Key = Key;
    // DEBUG(Entry.dump("Adding new entry: "));
    return Entry;
  }

  // Defer to the next level
  if (Entry.Key & FollowUpTableMarker) {
    return getEntry(
        reinterpret_cast<MapEntry *>(Entry.Key & ~FollowUpTableMarker),
        Key, Remainder, Alloc, CurLevel + 1);
  }

  // Conflict - create the next level
  // DEBUG(Entry.dump("Creating new level: "));

  MapEntry *NextLevelTbl = new (Alloc, 0) MapEntry[IncSize];
  // DEBUG(
  //     reportNumber("Newly allocated level: 0x", uint64_t(NextLevelTbl),
  //     16));
  uint64_t CurEntrySelector = Entry.Key / InitialSize;
  for (int I = 0; I < CurLevel; ++I)
    CurEntrySelector /= IncSize;
  CurEntrySelector = CurEntrySelector % IncSize;
  NextLevelTbl[CurEntrySelector] = Entry;
  Entry.Key = reinterpret_cast<uint64_t>(NextLevelTbl) | FollowUpTableMarker;
  assert((NextLevelTbl[CurEntrySelector].Key & ~FollowUpTableMarker) !=
             uint64_t(Entries),
         "circular reference created!\n");
  // DEBUG(NextLevelTbl[CurEntrySelector].dump("New level entry: "));
  // DEBUG(Entry.dump("Updated old entry: "));
  return getEntry(NextLevelTbl, Key, Remainder, Alloc, CurLevel + 1);
}

MapEntry &getOrAllocEntry(uint64_t Key, BumpPtrAllocator &Alloc) {
  if (TableRoot) {
    MapEntry &E = getEntry(TableRoot, Key, Key, Alloc, 0);
    assert(!(E.Key & FollowUpTableMarker), "Invalid entry!");
    return E;
  }
  return firstAllocation(Key, Alloc);
}
440};

442template <typename T> void resetIndCallCounter(T &Entry) {
Entry.Val = 0;
444}

446template <typename T, uint32_t X, uint32_t Y>
447void SimpleHashTable<T, X, Y>::resetCounters() {
forEachElement(resetIndCallCounter);
449}

451/// Represents a hash table mapping a function target address to its counter.
452using IndirectCallHashTable = SimpleHashTable<>;

454/// Initialize with number 1 instead of 0 so we don't go into .bss. This is the
455/// global array of all hash tables storing indirect call destinations happening
456/// during runtime, one table per call site.
457IndirectCallHashTable *GlobalIndCallCounters{
  reinterpret_cast<IndirectCallHashTable *>(1)};

460/// Don't allow reentrancy in the fdata writing phase - only one thread writes
461/// it
462Mutex *GlobalWriteProfileMutex{reinterpret_cast<Mutex *>(1)};

464/// Store number of calls in additional to target address (Key) and frequency
465/// as perceived by the basic block counter (Val).
466struct CallFlowEntryBase : public SimpleHashTableEntryBase {
uint64_t Calls;
468};

470using CallFlowHashTableBase = SimpleHashTable<CallFlowEntryBase, 11939, 233>;

472/// This is a large table indexing all possible call targets (indirect and
473/// direct ones). The goal is to find mismatches between number of calls (for
474/// those calls we were able to track) and the entry basic block counter of the
475/// callee. In most cases, these two should be equal. If not, there are two
476/// possible scenarios here:
477///
478///  * Entry BB has higher frequency than all known calls to this function.
479///    In this case, we have dynamic library code or any uninstrumented code
480///    calling this function. We will write the profile for these untracked
481///    calls as having source "0 [unknown] 0" in the fdata file.
482///
483///  * Number of known calls is higher than the frequency of entry BB
484///    This only happens when there is no counter for the entry BB / callee
485///    function is not simple (in BOLT terms). We don't do anything special
486///    here and just ignore those (we still report all calls to the non-simple
487///    function, though).
488///
489class CallFlowHashTable : public CallFlowHashTableBase {
490public:
CallFlowHashTable(BumpPtrAllocator &Alloc) : Alloc(Alloc) {}

MapEntry &get(uint64_t Key) { return CallFlowHashTableBase::get(Key, Alloc); }

495private:
// Different than the hash table for indirect call targets, we do store the
// allocator here since there is only one call flow hash and space overhead
// is negligible.
BumpPtrAllocator &Alloc;
500};

502///
503/// Description metadata emitted by BOLT to describe the program - refer to
504/// Passes/Instrumentation.cpp - Instrumentation::emitTablesAsELFNote()
505///
506struct Location {
uint32_t FunctionName;
uint32_t Offset;
509};

511struct CallDescription {
Location From;
uint32_t FromNode;
Location To;
uint32_t Counter;
uint64_t TargetAddress;
517};

519using IndCallDescription = Location;

521struct IndCallTargetDescription {
Location Loc;
uint64_t Address;
524};

526struct EdgeDescription {
Location From;
uint32_t FromNode;
Location To;
uint32_t ToNode;
uint32_t Counter;
532};

534struct InstrumentedNode {
uint32_t Node;
uint32_t Counter;
537};

539struct EntryNode {
uint64_t Node;
uint64_t Address;
542};

544struct FunctionDescription {
uint32_t NumLeafNodes;
const InstrumentedNode *LeafNodes;
uint32_t NumEdges;
const EdgeDescription *Edges;
uint32_t NumCalls;
const CallDescription *Calls;
uint32_t NumEntryNodes;
const EntryNode *EntryNodes;

/// Constructor will parse the serialized function metadata written by BOLT
FunctionDescription(const uint8_t *FuncDesc);

uint64_t getSize() const {
  return 16 + NumLeafNodes * sizeof(InstrumentedNode) +
         NumEdges * sizeof(EdgeDescription) +
         NumCalls * sizeof(CallDescription) +
         NumEntryNodes * sizeof(EntryNode);
}
563};

565/// The context is created when the fdata profile needs to be written to disk
566/// and we need to interpret our runtime counters. It contains pointers to the
567/// mmaped binary (only the BOLT written metadata section). Deserialization
568/// should be straightforward as most data is POD or an array of POD elements.
569/// This metadata is used to reconstruct function CFGs.
570struct ProfileWriterContext {
IndCallDescription *IndCallDescriptions;
IndCallTargetDescription *IndCallTargets;
uint8_t *FuncDescriptions;
char *Strings;  // String table with function names used in this binary
int FileDesc;   // File descriptor for the file on disk backing this
                // information in memory via mmap
void *MMapPtr;  // The mmap ptr
int MMapSize;   // The mmap size

/// Hash table storing all possible call destinations to detect untracked
/// calls and correctly report them as [unknown] in output fdata.
CallFlowHashTable *CallFlowTable;

/// Lookup the sorted indirect call target vector to fetch function name and
/// offset for an arbitrary function pointer.
const IndCallTargetDescription *lookupIndCallTarget(uint64_t Target) const;
587};

589/// Perform a string comparison and returns zero if Str1 matches Str2. Compares
590/// at most Size characters.
591int compareStr(const char *Str1, const char *Str2, int Size) {
while (*Str1 == *Str2) {
  if (*Str1 == '\0' || --Size == 0)
    return 0;
  ++Str1;
  ++Str2;
}
return 1;
599}

601/// Output Location to the fdata file
602char *serializeLoc(const ProfileWriterContext &Ctx, char *OutBuf,
                 const Location Loc, uint32_t BufSize) {
// fdata location format: Type Name Offset
// Type 1 - regular symbol
OutBuf = strCopy(OutBuf, "1 ");
const char *Str = Ctx.Strings + Loc.FunctionName;
uint32_t Size = 25;
while (*Str) {
  *OutBuf++ = *Str++;
  if (++Size >= BufSize)
    break;
}
assert(!*Str, "buffer overflow, function name too large");
*OutBuf++ = ' ';
OutBuf = intToStr(OutBuf, Loc.Offset, 16);
*OutBuf++ = ' ';
return OutBuf;
619}

621/// Read and deserialize a function description written by BOLT. \p FuncDesc
622/// points at the beginning of the function metadata structure in the file.
623/// See Instrumentation::emitTablesAsELFNote()
624FunctionDescription::FunctionDescription(const uint8_t *FuncDesc) {
NumLeafNodes = *reinterpret_cast<const uint32_t *>(FuncDesc);
DEBUG(reportNumber("NumLeafNodes = ", NumLeafNodes, 10)){};
LeafNodes = reinterpret_cast<const InstrumentedNode *>(FuncDesc + 4);

NumEdges = *reinterpret_cast<const uint32_t *>(
    FuncDesc + 4 + NumLeafNodes * sizeof(InstrumentedNode));
DEBUG(reportNumber("NumEdges = ", NumEdges, 10)){};
Edges = reinterpret_cast<const EdgeDescription *>(
    FuncDesc + 8 + NumLeafNodes * sizeof(InstrumentedNode));

NumCalls = *reinterpret_cast<const uint32_t *>(
    FuncDesc + 8 + NumLeafNodes * sizeof(InstrumentedNode) +
    NumEdges * sizeof(EdgeDescription));
DEBUG(reportNumber("NumCalls = ", NumCalls, 10)){};
Calls = reinterpret_cast<const CallDescription *>(
    FuncDesc + 12 + NumLeafNodes * sizeof(InstrumentedNode) +
    NumEdges * sizeof(EdgeDescription));
NumEntryNodes = *reinterpret_cast<const uint32_t *>(
    FuncDesc + 12 + NumLeafNodes * sizeof(InstrumentedNode) +
    NumEdges * sizeof(EdgeDescription) + NumCalls * sizeof(CallDescription));
DEBUG(reportNumber("NumEntryNodes = ", NumEntryNodes, 10)){};
EntryNodes = reinterpret_cast<const EntryNode *>(
    FuncDesc + 16 + NumLeafNodes * sizeof(InstrumentedNode) +
    NumEdges * sizeof(EdgeDescription) + NumCalls * sizeof(CallDescription));
649}

651/// Read and mmap descriptions written by BOLT from the executable's notes
652/// section
653#if defined(HAVE_ELF_H) and !defined(__APPLE__)

655void *__attribute__((noinline)) __get_pc() {
return __builtin_extract_return_addr(__builtin_return_address(0));
657}

659/// Get string with address and parse it to hex pair <StartAddress, EndAddress>
660bool parseAddressRange(const char *Str, uint64_t &StartAddress,
                     uint64_t &EndAddress) {
if (!Str19.1
'Str' is non-null
1
'Str' is non-null
)
20
←
Taking false branch→
  return false;
// Parsed string format: <hex1>-<hex2>
StartAddress = hexToLong(Str, '-');
while (*Str && *Str != '-')
21
←
Branch condition evaluates to a garbage value
  ++Str;
if (!*Str)
  return false;
++Str; // swallow '-'
EndAddress = hexToLong(Str);
return true;
673}

675/// Get full path to the real binary by getting current virtual address
676/// and searching for the appropriate link in address range in
677/// /proc/self/map_files
678static char *getBinaryPath() {
const uint32_t BufSize = 1024;
const uint32_t NameMax = 4096;
const char DirPath[] = "/proc/self/map_files/";
static char TargetPath[NameMax] = {};
char Buf[BufSize];

if (__bolt_instr_binpath[0] != '\0')
9
←
Assuming the condition is false→
10
←
Taking false branch→
  return __bolt_instr_binpath;

if (TargetPath[0] != '\0')
11
←
Taking false branch→
  return TargetPath;

unsigned long CurAddr = (unsigned long)__get_pc();
uint64_t FDdir = __open(DirPath, O_RDONLY0,
                        /*mode=*/0666);
assert(static_cast<int64_t>(FDdir) >= 0,
12
←
Assuming 'FDdir' is >= 0→
       "failed to open /proc/self/map_files");

while (long Nread = __getdents64(FDdir, (struct dirent64 *)Buf, BufSize)) {
13
←
Calling '__getdents64'→
14
←
Returning from '__getdents64'→
15
←
Loop condition is true.  Entering loop body→
  assert(static_cast<int64_t>(Nread) != -1, "failed to get folder entries");
16
←
Assuming the condition is true→

  struct dirent64 *d;
  for (long Bpos = 0; Bpos < Nread; Bpos += d->d_reclen) {
17
←
Assuming 'Bpos' is < 'Nread'→
18
←
Loop condition is true.  Entering loop body→
    d = (struct dirent64 *)(Buf + Bpos);

    uint64_t StartAddress, EndAddress;
    if (!parseAddressRange(d->d_name, StartAddress, EndAddress))
19
←
Calling 'parseAddressRange'→
      continue;
    if (CurAddr < StartAddress || CurAddr > EndAddress)
      continue;
    char FindBuf[NameMax];
    char *C = strCopy(FindBuf, DirPath, NameMax);
    C = strCopy(C, d->d_name, NameMax - (C - FindBuf));
    *C = '\0';
    uint32_t Ret = __readlink(FindBuf, TargetPath, sizeof(TargetPath));
    assert(Ret != -1 && Ret != BufSize, "readlink error");
    TargetPath[Ret] = '\0';
    return TargetPath;
  }
}
return nullptr;
720}

722ProfileWriterContext readDescriptions() {
ProfileWriterContext Result;
char *BinPath = getBinaryPath();
8
←
Calling 'getBinaryPath'→
assert(BinPath && BinPath[0] != '\0', "failed to find binary path");

uint64_t FD = __open(BinPath, O_RDONLY0,
                     /*mode=*/0666);
assert(static_cast<int64_t>(FD) >= 0, "failed to open binary path");

Result.FileDesc = FD;

// mmap our binary to memory
uint64_t Size = __lseek(FD, 0, SEEK_END2);
uint8_t *BinContents = reinterpret_cast<uint8_t *>(
    __mmap(0, Size, PROT_READ0x1, MAP_PRIVATE0x02, FD, 0));
assert(BinContents != MAP_FAILED((void *)-1), "readDescriptions: Failed to mmap self!");
Result.MMapPtr = BinContents;
Result.MMapSize = Size;
Elf64_Ehdr *Hdr = reinterpret_cast<Elf64_Ehdr *>(BinContents);
Elf64_Shdr *Shdr = reinterpret_cast<Elf64_Shdr *>(BinContents + Hdr->e_shoff);
Elf64_Shdr *StringTblHeader = reinterpret_cast<Elf64_Shdr *>(
    BinContents + Hdr->e_shoff + Hdr->e_shstrndx * Hdr->e_shentsize);

// Find .bolt.instr.tables with the data we need and set pointers to it
for (int I = 0; I < Hdr->e_shnum; ++I) {
  char *SecName = reinterpret_cast<char *>(
      BinContents + StringTblHeader->sh_offset + Shdr->sh_name);
  if (compareStr(SecName, ".bolt.instr.tables", 64) != 0) {
    Shdr = reinterpret_cast<Elf64_Shdr *>(BinContents + Hdr->e_shoff +
                                          (I + 1) * Hdr->e_shentsize);
    continue;
  }
  // Actual contents of the ELF note start after offset 20 decimal:
  // Offset 0: Producer name size (4 bytes)
  // Offset 4: Contents size (4 bytes)
  // Offset 8: Note type (4 bytes)
  // Offset 12: Producer name (BOLT\0) (5 bytes + align to 4-byte boundary)
  // Offset 20: Contents
  uint32_t IndCallDescSize =
      *reinterpret_cast<uint32_t *>(BinContents + Shdr->sh_offset + 20);
  uint32_t IndCallTargetDescSize = *reinterpret_cast<uint32_t *>(
      BinContents + Shdr->sh_offset + 24 + IndCallDescSize);
  uint32_t FuncDescSize =
      *reinterpret_cast<uint32_t *>(BinContents + Shdr->sh_offset + 28 +
                                    IndCallDescSize + IndCallTargetDescSize);
  Result.IndCallDescriptions = reinterpret_cast<IndCallDescription *>(
      BinContents + Shdr->sh_offset + 24);
  Result.IndCallTargets = reinterpret_cast<IndCallTargetDescription *>(
      BinContents + Shdr->sh_offset + 28 + IndCallDescSize);
  Result.FuncDescriptions = BinContents + Shdr->sh_offset + 32 +
                            IndCallDescSize + IndCallTargetDescSize;
  Result.Strings = reinterpret_cast<char *>(
      BinContents + Shdr->sh_offset + 32 + IndCallDescSize +
      IndCallTargetDescSize + FuncDescSize);
  return Result;
}
const char ErrMsg[] =
    "BOLT instrumentation runtime error: could not find section "
    ".bolt.instr.tables\n";
reportError(ErrMsg, sizeof(ErrMsg));
return Result;
783}

785#else

787ProfileWriterContext readDescriptions() {
ProfileWriterContext Result;
uint8_t *Tables = _bolt_instr_tables_getter();
uint32_t IndCallDescSize = *reinterpret_cast<uint32_t *>(Tables);
uint32_t IndCallTargetDescSize =
    *reinterpret_cast<uint32_t *>(Tables + 4 + IndCallDescSize);
uint32_t FuncDescSize = *reinterpret_cast<uint32_t *>(
    Tables + 8 + IndCallDescSize + IndCallTargetDescSize);
Result.IndCallDescriptions =
    reinterpret_cast<IndCallDescription *>(Tables + 4);
Result.IndCallTargets = reinterpret_cast<IndCallTargetDescription *>(
    Tables + 8 + IndCallDescSize);
Result.FuncDescriptions =
    Tables + 12 + IndCallDescSize + IndCallTargetDescSize;
Result.Strings = reinterpret_cast<char *>(
    Tables + 12 + IndCallDescSize + IndCallTargetDescSize + FuncDescSize);
return Result;
804}

806#endif

808#if !defined(__APPLE__)
809/// Debug by printing overall metadata global numbers to check it is sane
810void printStats(const ProfileWriterContext &Ctx) {
char StatMsg[BufSize];
char *StatPtr = StatMsg;
StatPtr =
    strCopy(StatPtr,
            "\nBOLT INSTRUMENTATION RUNTIME STATISTICS\n\nIndCallDescSize: ");
StatPtr = intToStr(StatPtr,
                   Ctx.FuncDescriptions -
                       reinterpret_cast<uint8_t *>(Ctx.IndCallDescriptions),
                   10);
StatPtr = strCopy(StatPtr, "\nFuncDescSize: ");
StatPtr = intToStr(
    StatPtr,
    reinterpret_cast<uint8_t *>(Ctx.Strings) - Ctx.FuncDescriptions, 10);
StatPtr = strCopy(StatPtr, "\n__bolt_instr_num_ind_calls: ");
StatPtr = intToStr(StatPtr, __bolt_instr_num_ind_calls, 10);
StatPtr = strCopy(StatPtr, "\n__bolt_instr_num_funcs: ");
StatPtr = intToStr(StatPtr, __bolt_instr_num_funcs, 10);
StatPtr = strCopy(StatPtr, "\n");
__write(2, StatMsg, StatPtr - StatMsg);
830}
831#endif


834/// This is part of a simple CFG representation in memory, where we store
835/// a dynamically sized array of input and output edges per node, and store
836/// a dynamically sized array of nodes per graph. We also store the spanning
837/// tree edges for that CFG in a separate array of nodes in
838/// \p SpanningTreeNodes, while the regular nodes live in \p CFGNodes.
839struct Edge {
uint32_t Node; // Index in nodes array regarding the destination of this edge
uint32_t ID;   // Edge index in an array comprising all edges of the graph
842};

844/// A regular graph node or a spanning tree node
845struct Node {
uint32_t NumInEdges{0};  // Input edge count used to size InEdge
uint32_t NumOutEdges{0}; // Output edge count used to size OutEdges
Edge *InEdges{nullptr};  // Created and managed by \p Graph
Edge *OutEdges{nullptr}; // ditto
850};

852/// Main class for CFG representation in memory. Manages object creation and
853/// destruction, populates an array of CFG nodes as well as corresponding
854/// spanning tree nodes.
855struct Graph {
uint32_t NumNodes;
Node *CFGNodes;
Node *SpanningTreeNodes;
uint64_t *EdgeFreqs;
uint64_t *CallFreqs;
BumpPtrAllocator &Alloc;
const FunctionDescription &D;

/// Reads a list of edges from function description \p D and builds
/// the graph from it. Allocates several internal dynamic structures that are
/// later destroyed by ~Graph() and uses \p Alloc. D.LeafNodes contain all
/// spanning tree leaf nodes descriptions (their counters). They are the seed
/// used to compute the rest of the missing edge counts in a bottom-up
/// traversal of the spanning tree.
Graph(BumpPtrAllocator &Alloc, const FunctionDescription &D,
      const uint64_t *Counters, ProfileWriterContext &Ctx);
~Graph();
void dump() const;

875private:
void computeEdgeFrequencies(const uint64_t *Counters,
                            ProfileWriterContext &Ctx);
void dumpEdgeFreqs() const;
879};

881Graph::Graph(BumpPtrAllocator &Alloc, const FunctionDescription &D,
           const uint64_t *Counters, ProfileWriterContext &Ctx)
  : Alloc(Alloc), D(D) {
DEBUG(reportNumber("G = 0x", (uint64_t)this, 16)){};
// First pass to determine number of nodes
int32_t MaxNodes = -1;
CallFreqs = nullptr;
EdgeFreqs = nullptr;
for (int I = 0; I < D.NumEdges; ++I) {
  if (static_cast<int32_t>(D.Edges[I].FromNode) > MaxNodes)
    MaxNodes = D.Edges[I].FromNode;
  if (static_cast<int32_t>(D.Edges[I].ToNode) > MaxNodes)
    MaxNodes = D.Edges[I].ToNode;
}

for (int I = 0; I < D.NumLeafNodes; ++I)
  if (static_cast<int32_t>(D.LeafNodes[I].Node) > MaxNodes)
    MaxNodes = D.LeafNodes[I].Node;

for (int I = 0; I < D.NumCalls; ++I)
  if (static_cast<int32_t>(D.Calls[I].FromNode) > MaxNodes)
    MaxNodes = D.Calls[I].FromNode;

// No nodes? Nothing to do
if (MaxNodes < 0) {
  DEBUG(report("No nodes!\n")){};
  CFGNodes = nullptr;
  SpanningTreeNodes = nullptr;
  NumNodes = 0;
  return;
}
++MaxNodes;
DEBUG(reportNumber("NumNodes = ", MaxNodes, 10)){};
NumNodes = static_cast<uint32_t>(MaxNodes);

// Initial allocations
CFGNodes = new (Alloc) Node[MaxNodes];

DEBUG(reportNumber("G->CFGNodes = 0x", (uint64_t)CFGNodes, 16)){};
SpanningTreeNodes = new (Alloc) Node[MaxNodes];
DEBUG(reportNumber("G->SpanningTreeNodes = 0x",{}
                   (uint64_t)SpanningTreeNodes, 16)){};

// Figure out how much to allocate to each vector (in/out edge sets)
for (int I = 0; I < D.NumEdges; ++I) {
  CFGNodes[D.Edges[I].FromNode].NumOutEdges++;
  CFGNodes[D.Edges[I].ToNode].NumInEdges++;
  if (D.Edges[I].Counter != 0xffffffff)
    continue;

  SpanningTreeNodes[D.Edges[I].FromNode].NumOutEdges++;
  SpanningTreeNodes[D.Edges[I].ToNode].NumInEdges++;
}

// Allocate in/out edge sets
for (int I = 0; I < MaxNodes; ++I) {
  if (CFGNodes[I].NumInEdges > 0)
    CFGNodes[I].InEdges = new (Alloc) Edge[CFGNodes[I].NumInEdges];
  if (CFGNodes[I].NumOutEdges > 0)
    CFGNodes[I].OutEdges = new (Alloc) Edge[CFGNodes[I].NumOutEdges];
  if (SpanningTreeNodes[I].NumInEdges > 0)
    SpanningTreeNodes[I].InEdges =
        new (Alloc) Edge[SpanningTreeNodes[I].NumInEdges];
  if (SpanningTreeNodes[I].NumOutEdges > 0)
    SpanningTreeNodes[I].OutEdges =
        new (Alloc) Edge[SpanningTreeNodes[I].NumOutEdges];
  CFGNodes[I].NumInEdges = 0;
  CFGNodes[I].NumOutEdges = 0;
  SpanningTreeNodes[I].NumInEdges = 0;
  SpanningTreeNodes[I].NumOutEdges = 0;
}

// Fill in/out edge sets
for (int I = 0; I < D.NumEdges; ++I) {
  const uint32_t Src = D.Edges[I].FromNode;
  const uint32_t Dst = D.Edges[I].ToNode;
  Edge *E = &CFGNodes[Src].OutEdges[CFGNodes[Src].NumOutEdges++];
  E->Node = Dst;
  E->ID = I;

  E = &CFGNodes[Dst].InEdges[CFGNodes[Dst].NumInEdges++];
  E->Node = Src;
  E->ID = I;

  if (D.Edges[I].Counter != 0xffffffff)
    continue;

  E = &SpanningTreeNodes[Src]
           .OutEdges[SpanningTreeNodes[Src].NumOutEdges++];
  E->Node = Dst;
  E->ID = I;

  E = &SpanningTreeNodes[Dst]
           .InEdges[SpanningTreeNodes[Dst].NumInEdges++];
  E->Node = Src;
  E->ID = I;
}

computeEdgeFrequencies(Counters, Ctx);
980}

982Graph::~Graph() {
if (CallFreqs)
  Alloc.deallocate(CallFreqs);
if (EdgeFreqs)
  Alloc.deallocate(EdgeFreqs);
for (int I = NumNodes - 1; I >= 0; --I) {
  if (SpanningTreeNodes[I].OutEdges)
    Alloc.deallocate(SpanningTreeNodes[I].OutEdges);
  if (SpanningTreeNodes[I].InEdges)
    Alloc.deallocate(SpanningTreeNodes[I].InEdges);
  if (CFGNodes[I].OutEdges)
    Alloc.deallocate(CFGNodes[I].OutEdges);
  if (CFGNodes[I].InEdges)
    Alloc.deallocate(CFGNodes[I].InEdges);
}
if (SpanningTreeNodes)
  Alloc.deallocate(SpanningTreeNodes);
if (CFGNodes)
  Alloc.deallocate(CFGNodes);
1001}

1003void Graph::dump() const {
reportNumber("Dumping graph with number of nodes: ", NumNodes, 10);
report("  Full graph:\n");
for (int I = 0; I < NumNodes; ++I) {
  const Node *N = &CFGNodes[I];
  reportNumber("    Node #", I, 10);
  reportNumber("      InEdges total ", N->NumInEdges, 10);
  for (int J = 0; J < N->NumInEdges; ++J)
    reportNumber("        ", N->InEdges[J].Node, 10);
  reportNumber("      OutEdges total ", N->NumOutEdges, 10);
  for (int J = 0; J < N->NumOutEdges; ++J)
    reportNumber("        ", N->OutEdges[J].Node, 10);
  report("\n");
}
report("  Spanning tree:\n");
for (int I = 0; I < NumNodes; ++I) {
  const Node *N = &SpanningTreeNodes[I];
  reportNumber("    Node #", I, 10);
  reportNumber("      InEdges total ", N->NumInEdges, 10);
  for (int J = 0; J < N->NumInEdges; ++J)
    reportNumber("        ", N->InEdges[J].Node, 10);
  reportNumber("      OutEdges total ", N->NumOutEdges, 10);
  for (int J = 0; J < N->NumOutEdges; ++J)
    reportNumber("        ", N->OutEdges[J].Node, 10);
  report("\n");
}
1029}

1031void Graph::dumpEdgeFreqs() const {
reportNumber(
    "Dumping edge frequencies for graph with num edges: ", D.NumEdges, 10);
for (int I = 0; I < D.NumEdges; ++I) {
  reportNumber("* Src: ", D.Edges[I].FromNode, 10);
  reportNumber("  Dst: ", D.Edges[I].ToNode, 10);
  reportNumber("    Cnt: ", EdgeFreqs[I], 10);
}
1039}

1041/// Auxiliary map structure for fast lookups of which calls map to each node of
1042/// the function CFG
1043struct NodeToCallsMap {
struct MapEntry {
  uint32_t NumCalls;
  uint32_t *Calls;
};
MapEntry *Entries;
BumpPtrAllocator &Alloc;
const uint32_t NumNodes;

NodeToCallsMap(BumpPtrAllocator &Alloc, const FunctionDescription &D,
               uint32_t NumNodes)
    : Alloc(Alloc), NumNodes(NumNodes) {
  Entries = new (Alloc, 0) MapEntry[NumNodes];
  for (int I = 0; I < D.NumCalls; ++I) {
    DEBUG(reportNumber("Registering call in node ", D.Calls[I].FromNode, 10)){};
    ++Entries[D.Calls[I].FromNode].NumCalls;
  }
  for (int I = 0; I < NumNodes; ++I) {
    Entries[I].Calls = Entries[I].NumCalls ? new (Alloc)
                                                 uint32_t[Entries[I].NumCalls]
                                           : nullptr;
    Entries[I].NumCalls = 0;
  }
  for (int I = 0; I < D.NumCalls; ++I) {
    MapEntry &Entry = Entries[D.Calls[I].FromNode];
    Entry.Calls[Entry.NumCalls++] = I;
  }
}

/// Set the frequency of all calls in node \p NodeID to Freq. However, if
/// the calls have their own counters and do not depend on the basic block
/// counter, this means they have landing pads and throw exceptions. In this
/// case, set their frequency with their counters and return the maximum
/// value observed in such counters. This will be used as the new frequency
/// at basic block entry. This is used to fix the CFG edge frequencies in the
/// presence of exceptions.
uint64_t visitAllCallsIn(uint32_t NodeID, uint64_t Freq, uint64_t *CallFreqs,
                         const FunctionDescription &D,
                         const uint64_t *Counters,
                         ProfileWriterContext &Ctx) const {
  const MapEntry &Entry = Entries[NodeID];
  uint64_t MaxValue = 0ull;
  for (int I = 0, E = Entry.NumCalls; I != E; ++I) {
    const uint32_t CallID = Entry.Calls[I];
    DEBUG(reportNumber("  Setting freq for call ID: ", CallID, 10)){};
    const CallDescription &CallDesc = D.Calls[CallID];
    if (CallDesc.Counter == 0xffffffff) {
      CallFreqs[CallID] = Freq;
      DEBUG(reportNumber("  with : ", Freq, 10)){};
    } else {
      const uint64_t CounterVal = Counters[CallDesc.Counter];
      CallFreqs[CallID] = CounterVal;
      MaxValue = CounterVal > MaxValue ? CounterVal : MaxValue;
      DEBUG(reportNumber("  with (private counter) : ", CounterVal, 10)){};
    }
    DEBUG(reportNumber("  Address: 0x", CallDesc.TargetAddress, 16)){};
    if (CallFreqs[CallID] > 0)
      Ctx.CallFlowTable->get(CallDesc.TargetAddress).Calls +=
          CallFreqs[CallID];
  }
  return MaxValue;
}

~NodeToCallsMap() {
  for (int I = NumNodes - 1; I >= 0; --I)
    if (Entries[I].Calls)
      Alloc.deallocate(Entries[I].Calls);
  Alloc.deallocate(Entries);
}
1112};

1114/// Fill an array with the frequency of each edge in the function represented
1115/// by G, as well as another array for each call.
1116void Graph::computeEdgeFrequencies(const uint64_t *Counters,
                                 ProfileWriterContext &Ctx) {
if (NumNodes == 0)
  return;

EdgeFreqs = D.NumEdges ? new (Alloc, 0) uint64_t [D.NumEdges] : nullptr;
CallFreqs = D.NumCalls ? new (Alloc, 0) uint64_t [D.NumCalls] : nullptr;

// Setup a lookup for calls present in each node (BB)
NodeToCallsMap *CallMap = new (Alloc) NodeToCallsMap(Alloc, D, NumNodes);

// Perform a bottom-up, BFS traversal of the spanning tree in G. Edges in the
// spanning tree don't have explicit counters. We must infer their value using
// a linear combination of other counters (sum of counters of the outgoing
// edges minus sum of counters of the incoming edges).
uint32_t *Stack = new (Alloc) uint32_t [NumNodes];
uint32_t StackTop = 0;
enum Status : uint8_t { S_NEW = 0, S_VISITING, S_VISITED };
Status *Visited = new (Alloc, 0) Status[NumNodes];
uint64_t *LeafFrequency = new (Alloc, 0) uint64_t[NumNodes];
uint64_t *EntryAddress = new (Alloc, 0) uint64_t[NumNodes];

// Setup a fast lookup for frequency of leaf nodes, which have special
// basic block frequency instrumentation (they are not edge profiled).
for (int I = 0; I < D.NumLeafNodes; ++I) {
  LeafFrequency[D.LeafNodes[I].Node] = Counters[D.LeafNodes[I].Counter];
  DEBUG({{}
    if (Counters[D.LeafNodes[I].Counter] > 0) {{}
      reportNumber("Leaf Node# ", D.LeafNodes[I].Node, 10);{}
      reportNumber("     Counter: ", Counters[D.LeafNodes[I].Counter], 10);{}
    }{}
  }){};
}
for (int I = 0; I < D.NumEntryNodes; ++I) {
  EntryAddress[D.EntryNodes[I].Node] = D.EntryNodes[I].Address;
  DEBUG({{}
      reportNumber("Entry Node# ", D.EntryNodes[I].Node, 10);{}
      reportNumber("      Address: ", D.EntryNodes[I].Address, 16);{}
  }){};
}
// Add all root nodes to the stack
for (int I = 0; I < NumNodes; ++I)
  if (SpanningTreeNodes[I].NumInEdges == 0)
    Stack[StackTop++] = I;

// Empty stack?
if (StackTop == 0) {
  DEBUG(report("Empty stack!\n")){};
  Alloc.deallocate(EntryAddress);
  Alloc.deallocate(LeafFrequency);
  Alloc.deallocate(Visited);
  Alloc.deallocate(Stack);
  CallMap->~NodeToCallsMap();
  Alloc.deallocate(CallMap);
  if (CallFreqs)
    Alloc.deallocate(CallFreqs);
  if (EdgeFreqs)
    Alloc.deallocate(EdgeFreqs);
  EdgeFreqs = nullptr;
  CallFreqs = nullptr;
  return;
}
// Add all known edge counts, will infer the rest
for (int I = 0; I < D.NumEdges; ++I) {
  const uint32_t C = D.Edges[I].Counter;
  if (C == 0xffffffff) // inferred counter - we will compute its value
    continue;
  EdgeFreqs[I] = Counters[C];
}

while (StackTop > 0) {
  const uint32_t Cur = Stack[--StackTop];
  DEBUG({{}
    if (Visited[Cur] == S_VISITING){}
      report("(visiting) ");{}
    else{}
      report("(new) ");{}
    reportNumber("Cur: ", Cur, 10);{}
  }){};

  // This shouldn't happen in a tree
  assert(Visited[Cur] != S_VISITED, "should not have visited nodes in stack");
  if (Visited[Cur] == S_NEW) {
    Visited[Cur] = S_VISITING;
    Stack[StackTop++] = Cur;
    assert(StackTop <= NumNodes, "stack grew too large");
    for (int I = 0, E = SpanningTreeNodes[Cur].NumOutEdges; I < E; ++I) {
      const uint32_t Succ = SpanningTreeNodes[Cur].OutEdges[I].Node;
      Stack[StackTop++] = Succ;
      assert(StackTop <= NumNodes, "stack grew too large");
    }
    continue;
  }
  Visited[Cur] = S_VISITED;

  // Establish our node frequency based on outgoing edges, which should all be
  // resolved by now.
  int64_t CurNodeFreq = LeafFrequency[Cur];
  // Not a leaf?
  if (!CurNodeFreq) {
    for (int I = 0, E = CFGNodes[Cur].NumOutEdges; I != E; ++I) {
      const uint32_t SuccEdge = CFGNodes[Cur].OutEdges[I].ID;
      CurNodeFreq += EdgeFreqs[SuccEdge];
    }
  }
  if (CurNodeFreq < 0)
    CurNodeFreq = 0;

  const uint64_t CallFreq = CallMap->visitAllCallsIn(
      Cur, CurNodeFreq > 0 ? CurNodeFreq : 0, CallFreqs, D, Counters, Ctx);

  // Exception handling affected our output flow? Fix with calls info
  DEBUG({{}
    if (CallFreq > CurNodeFreq){}
      report("Bumping node frequency with call info\n");{}
  }){};
  CurNodeFreq = CallFreq > CurNodeFreq ? CallFreq : CurNodeFreq;

  if (CurNodeFreq > 0) {
    if (uint64_t Addr = EntryAddress[Cur]) {
      DEBUG({}
          reportNumber("  Setting flow at entry point address 0x", Addr, 16)){};
      DEBUG(reportNumber("  with: ", CurNodeFreq, 10)){};
      Ctx.CallFlowTable->get(Addr).Val = CurNodeFreq;
    }
  }

  // No parent? Reached a tree root, limit to call frequency updating.
  if (SpanningTreeNodes[Cur].NumInEdges == 0)
    continue;

  assert(SpanningTreeNodes[Cur].NumInEdges == 1, "must have 1 parent");
  const uint32_t Parent = SpanningTreeNodes[Cur].InEdges[0].Node;
  const uint32_t ParentEdge = SpanningTreeNodes[Cur].InEdges[0].ID;

  // Calculate parent edge freq.
  int64_t ParentEdgeFreq = CurNodeFreq;
  for (int I = 0, E = CFGNodes[Cur].NumInEdges; I != E; ++I) {
    const uint32_t PredEdge = CFGNodes[Cur].InEdges[I].ID;
    ParentEdgeFreq -= EdgeFreqs[PredEdge];
  }

  // Sometimes the conservative CFG that BOLT builds will lead to incorrect
  // flow computation. For example, in a BB that transitively calls the exit
  // syscall, BOLT will add a fall-through successor even though it should not
  // have any successors. So this block execution will likely be wrong. We
  // tolerate this imperfection since this case should be quite infrequent.
  if (ParentEdgeFreq < 0) {
    DEBUG(dumpEdgeFreqs()){};
    DEBUG(report("WARNING: incorrect flow")){};
    ParentEdgeFreq = 0;
  }
  DEBUG(reportNumber("  Setting freq for ParentEdge: ", ParentEdge, 10)){};
  DEBUG(reportNumber("  with ParentEdgeFreq: ", ParentEdgeFreq, 10)){};
  EdgeFreqs[ParentEdge] = ParentEdgeFreq;
}

Alloc.deallocate(EntryAddress);
Alloc.deallocate(LeafFrequency);
Alloc.deallocate(Visited);
Alloc.deallocate(Stack);
CallMap->~NodeToCallsMap();
Alloc.deallocate(CallMap);
DEBUG(dumpEdgeFreqs()){};
1280}

1282/// Write to \p FD all of the edge profiles for function \p FuncDesc. Uses
1283/// \p Alloc to allocate helper dynamic structures used to compute profile for
1284/// edges that we do not explictly instrument.
1285const uint8_t *writeFunctionProfile(int FD, ProfileWriterContext &Ctx,
                                  const uint8_t *FuncDesc,
                                  BumpPtrAllocator &Alloc) {
const FunctionDescription F(FuncDesc);
const uint8_t *next = FuncDesc + F.getSize();

1291#if !defined(__APPLE__)
uint64_t *bolt_instr_locations = __bolt_instr_locations;
1293#else
uint64_t *bolt_instr_locations = _bolt_instr_locations_getter();
1295#endif

// Skip funcs we know are cold
1298#ifndef ENABLE_DEBUG
uint64_t CountersFreq = 0;
for (int I = 0; I < F.NumLeafNodes; ++I)
  CountersFreq += bolt_instr_locations[F.LeafNodes[I].Counter];

if (CountersFreq == 0) {
  for (int I = 0; I < F.NumEdges; ++I) {
    const uint32_t C = F.Edges[I].Counter;
    if (C == 0xffffffff)
      continue;
    CountersFreq += bolt_instr_locations[C];
  }
  if (CountersFreq == 0) {
    for (int I = 0; I < F.NumCalls; ++I) {
      const uint32_t C = F.Calls[I].Counter;
      if (C == 0xffffffff)
        continue;
      CountersFreq += bolt_instr_locations[C];
    }
    if (CountersFreq == 0)
      return next;
  }
}
1321#endif

Graph *G = new (Alloc) Graph(Alloc, F, bolt_instr_locations, Ctx);
DEBUG(G->dump()){};

if (!G->EdgeFreqs && !G->CallFreqs) {
  G->~Graph();
  Alloc.deallocate(G);
  return next;
}

for (int I = 0; I < F.NumEdges; ++I) {
  const uint64_t Freq = G->EdgeFreqs[I];
  if (Freq == 0)
    continue;
  const EdgeDescription *Desc = &F.Edges[I];
  char LineBuf[BufSize];
  char *Ptr = LineBuf;
  Ptr = serializeLoc(Ctx, Ptr, Desc->From, BufSize);
  Ptr = serializeLoc(Ctx, Ptr, Desc->To, BufSize - (Ptr - LineBuf));
  Ptr = strCopy(Ptr, "0 ", BufSize - (Ptr - LineBuf) - 22);
  Ptr = intToStr(Ptr, Freq, 10);
  *Ptr++ = '\n';
  __write(FD, LineBuf, Ptr - LineBuf);
}

for (int I = 0; I < F.NumCalls; ++I) {
  const uint64_t Freq = G->CallFreqs[I];
  if (Freq == 0)
    continue;
  char LineBuf[BufSize];
  char *Ptr = LineBuf;
  const CallDescription *Desc = &F.Calls[I];
  Ptr = serializeLoc(Ctx, Ptr, Desc->From, BufSize);
  Ptr = serializeLoc(Ctx, Ptr, Desc->To, BufSize - (Ptr - LineBuf));
  Ptr = strCopy(Ptr, "0 ", BufSize - (Ptr - LineBuf) - 25);
  Ptr = intToStr(Ptr, Freq, 10);
  *Ptr++ = '\n';
  __write(FD, LineBuf, Ptr - LineBuf);
}

G->~Graph();
Alloc.deallocate(G);
return next;
1365}

1367#if !defined(__APPLE__)
1368const IndCallTargetDescription *
1369ProfileWriterContext::lookupIndCallTarget(uint64_t Target) const {
uint32_t B = 0;
uint32_t E = __bolt_instr_num_ind_targets;
if (E == 0)
  return nullptr;
do {
  uint32_t I = (E - B) / 2 + B;
  if (IndCallTargets[I].Address == Target)
    return &IndCallTargets[I];
  if (IndCallTargets[I].Address < Target)
    B = I + 1;
  else
    E = I;
} while (B < E);
return nullptr;
1384}

1386/// Write a single indirect call <src, target> pair to the fdata file
1387void visitIndCallCounter(IndirectCallHashTable::MapEntry &Entry,
                       int FD, int CallsiteID,
                       ProfileWriterContext *Ctx) {
if (Entry.Val == 0)
  return;
DEBUG(reportNumber("Target func 0x", Entry.Key, 16)){};
DEBUG(reportNumber("Target freq: ", Entry.Val, 10)){};
const IndCallDescription *CallsiteDesc =
    &Ctx->IndCallDescriptions[CallsiteID];
const IndCallTargetDescription *TargetDesc =
    Ctx->lookupIndCallTarget(Entry.Key - TextBaseAddress);
if (!TargetDesc) {
  DEBUG(report("Failed to lookup indirect call target\n")){};
  char LineBuf[BufSize];
  char *Ptr = LineBuf;
  Ptr = serializeLoc(*Ctx, Ptr, *CallsiteDesc, BufSize);
  Ptr = strCopy(Ptr, "0 [unknown] 0 0 ", BufSize - (Ptr - LineBuf) - 40);
  Ptr = intToStr(Ptr, Entry.Val, 10);
  *Ptr++ = '\n';
  __write(FD, LineBuf, Ptr - LineBuf);
  return;
}
Ctx->CallFlowTable->get(TargetDesc->Address).Calls += Entry.Val;
char LineBuf[BufSize];
char *Ptr = LineBuf;
Ptr = serializeLoc(*Ctx, Ptr, *CallsiteDesc, BufSize);
Ptr = serializeLoc(*Ctx, Ptr, TargetDesc->Loc, BufSize - (Ptr - LineBuf));
Ptr = strCopy(Ptr, "0 ", BufSize - (Ptr - LineBuf) - 25);
Ptr = intToStr(Ptr, Entry.Val, 10);
*Ptr++ = '\n';
__write(FD, LineBuf, Ptr - LineBuf);
1418}

1420/// Write to \p FD all of the indirect call profiles.
1421void writeIndirectCallProfile(int FD, ProfileWriterContext &Ctx) {
for (int I = 0; I < __bolt_instr_num_ind_calls; ++I) {
  DEBUG(reportNumber("IndCallsite #", I, 10)){};
  GlobalIndCallCounters[I].forEachElement(visitIndCallCounter, FD, I, &Ctx);
}
1426}

1428/// Check a single call flow for a callee versus all known callers. If there are
1429/// less callers than what the callee expects, write the difference with source
1430/// [unknown] in the profile.
1431void visitCallFlowEntry(CallFlowHashTable::MapEntry &Entry, int FD,
                      ProfileWriterContext *Ctx) {
DEBUG(reportNumber("Call flow entry address: 0x", Entry.Key, 16)){};
DEBUG(reportNumber("Calls: ", Entry.Calls, 10)){};
DEBUG(reportNumber("Reported entry frequency: ", Entry.Val, 10)){};
DEBUG({{}
  if (Entry.Calls > Entry.Val){}
    report("  More calls than expected!\n");{}
}){};
if (Entry.Val <= Entry.Calls)
  return;
DEBUG(reportNumber({}
    "  Balancing calls with traffic: ", Entry.Val - Entry.Calls, 10)){};
const IndCallTargetDescription *TargetDesc =
    Ctx->lookupIndCallTarget(Entry.Key);
if (!TargetDesc) {
  // There is probably something wrong with this callee and this should be
  // investigated, but I don't want to assert and lose all data collected.
  DEBUG(report("WARNING: failed to look up call target!\n")){};
  return;
}
char LineBuf[BufSize];
char *Ptr = LineBuf;
Ptr = strCopy(Ptr, "0 [unknown] 0 ", BufSize);
Ptr = serializeLoc(*Ctx, Ptr, TargetDesc->Loc, BufSize - (Ptr - LineBuf));
Ptr = strCopy(Ptr, "0 ", BufSize - (Ptr - LineBuf) - 25);
Ptr = intToStr(Ptr, Entry.Val - Entry.Calls, 10);
*Ptr++ = '\n';
__write(FD, LineBuf, Ptr - LineBuf);
1460}

1462/// Open fdata file for writing and return a valid file descriptor, aborting
1463/// program upon failure.
1464int openProfile() {
// Build the profile name string by appending our PID
char Buf[BufSize];
char *Ptr = Buf;
uint64_t PID = __getpid();
Ptr = strCopy(Buf, __bolt_instr_filename, BufSize);
if (__bolt_instr_use_pid) {
  Ptr = strCopy(Ptr, ".", BufSize - (Ptr - Buf + 1));
  Ptr = intToStr(Ptr, PID, 10);
  Ptr = strCopy(Ptr, ".fdata", BufSize - (Ptr - Buf + 1));
}
*Ptr++ = '\0';
uint64_t FD = __open(Buf, O_WRONLY1 | O_TRUNC512 | O_CREAT64,
                     /*mode=*/0666);
if (static_cast<int64_t>(FD) < 0) {
  report("Error while trying to open profile file for writing: ");
  report(Buf);
  reportNumber("\nFailed with error number: 0x",
               0 - static_cast<int64_t>(FD), 16);
  __exit(1);
}
return FD;
1486}

1488#endif

1490} // anonymous namespace

1492#if !defined(__APPLE__)

1494/// Reset all counters in case you want to start profiling a new phase of your
1495/// program independently of prior phases.
1496/// The address of this function is printed by BOLT and this can be called by
1497/// any attached debugger during runtime. There is a useful oneliner for gdb:
1498///
1499///   gdb -p $(pgrep -xo PROCESSNAME) -ex 'p ((void(*)())0xdeadbeef)()' \
1500///     -ex 'set confirm off' -ex quit
1501///
1502/// Where 0xdeadbeef is this function address and PROCESSNAME your binary file
1503/// name.
1504extern "C" void __bolt_instr_clear_counters() {
memset(reinterpret_cast<char *>(__bolt_instr_locations), 0,
       __bolt_num_counters * 8);
for (int I = 0; I < __bolt_instr_num_ind_calls; ++I)
  GlobalIndCallCounters[I].resetCounters();
1509}

1511/// This is the entry point for profile writing.
1512/// There are three ways of getting here:
1513///
1514///  * Program execution ended, finalization methods are running and BOLT
1515///    hooked into FINI from your binary dynamic section;
1516///  * You used the sleep timer option and during initialization we forked
1517///    a separete process that will call this function periodically;
1518///  * BOLT prints this function address so you can attach a debugger and
1519///    call this function directly to get your profile written to disk
1520///    on demand.
1521///
1522extern "C" void __attribute((force_align_arg_pointer))
1523__bolt_instr_data_dump(int FD) {
// Already dumping
if (!GlobalWriteProfileMutex->acquire())
4
←
Taking false branch→
  return;

int ret = __lseek(FD, 0, SEEK_SET0);
assert(ret == 0, "Failed to lseek!");
5
←
Assuming 'ret' is equal to 0→
ret = __ftruncate(FD, 0);
assert(ret == 0, "Failed to ftruncate!");
6
←
Assuming 'ret' is equal to 0→
BumpPtrAllocator HashAlloc;
HashAlloc.setMaxSize(0x6400000);
ProfileWriterContext Ctx = readDescriptions();
7
←
Calling 'readDescriptions'→
Ctx.CallFlowTable = new (HashAlloc, 0) CallFlowHashTable(HashAlloc);

DEBUG(printStats(Ctx)){};

BumpPtrAllocator Alloc;
Alloc.setMaxSize(0x6400000);
const uint8_t *FuncDesc = Ctx.FuncDescriptions;
for (int I = 0, E = __bolt_instr_num_funcs; I < E; ++I) {
  FuncDesc = writeFunctionProfile(FD, Ctx, FuncDesc, Alloc);
  Alloc.clear();
  DEBUG(reportNumber("FuncDesc now: ", (uint64_t)FuncDesc, 16)){};
}
assert(FuncDesc == (void *)Ctx.Strings,
       "FuncDesc ptr must be equal to stringtable");

writeIndirectCallProfile(FD, Ctx);
Ctx.CallFlowTable->forEachElement(visitCallFlowEntry, FD, &Ctx);

__fsync(FD);
__munmap(Ctx.MMapPtr, Ctx.MMapSize);
__close(Ctx.FileDesc);
HashAlloc.destroy();
GlobalWriteProfileMutex->release();
DEBUG(report("Finished writing profile.\n")){};
1559}

1561/// Event loop for our child process spawned during setup to dump profile data
1562/// at user-specified intervals
1563void watchProcess() {
timespec ts, rem;
uint64_t Ellapsed = 0ull;
int FD = openProfile();
uint64_t ppid;
if (__bolt_instr_wait_forks) {
  // Store parent pgid
  ppid = -__getpgid(0);
  // And leave parent process group
  __setpgid(0, 0);
} else {
  // Store parent pid
  ppid = __getppid();
  if (ppid == 1) {
    // Parent already dead
    __bolt_instr_data_dump(FD);
    goto out;
  }
}

ts.tv_sec = 1;
ts.tv_nsec = 0;
while (1) {
  __nanosleep(&ts, &rem);
  // This means our parent process or all its forks are dead,
  // so no need for us to keep dumping.
  if (__kill(ppid, 0) < 0) {
    if (__bolt_instr_no_counters_clear)
      __bolt_instr_data_dump(FD);
    break;
  }

  if (++Ellapsed < __bolt_instr_sleep_time)
    continue;

  Ellapsed = 0;
  __bolt_instr_data_dump(FD);
  if (__bolt_instr_no_counters_clear == false)
    __bolt_instr_clear_counters();
}

1604out:;
DEBUG(report("My parent process is dead, bye!\n")){};
__close(FD);
__exit(0);
1608}

1610extern "C" void __bolt_instr_indirect_call();
1611extern "C" void __bolt_instr_indirect_tailcall();

1613/// Initialization code
1614extern "C" void __attribute((force_align_arg_pointer)) __bolt_instr_setup() {
__bolt_ind_call_counter_func_pointer = __bolt_instr_indirect_call;
__bolt_ind_tailcall_counter_func_pointer = __bolt_instr_indirect_tailcall;
TextBaseAddress = getTextBaseAddress();

const uint64_t CountersStart =
    reinterpret_cast<uint64_t>(&__bolt_instr_locations[0]);
const uint64_t CountersEnd = alignTo(
    reinterpret_cast<uint64_t>(&__bolt_instr_locations[__bolt_num_counters]),
    0x1000);
DEBUG(reportNumber("replace mmap start: ", CountersStart, 16)){};
DEBUG(reportNumber("replace mmap stop: ", CountersEnd, 16)){};
assert(CountersEnd > CountersStart, "no counters");

const bool Shared = !__bolt_instr_use_pid;
const uint64_t MapPrivateOrShared = Shared ? MAP_SHARED0x01 : MAP_PRIVATE0x02;

void *Ret =
    __mmap(CountersStart, CountersEnd - CountersStart, PROT_READ0x1 | PROT_WRITE0x2,
           MAP_ANONYMOUS0x20 | MapPrivateOrShared | MAP_FIXED0x10, -1, 0);
assert(Ret != MAP_FAILED((void *)-1), "__bolt_instr_setup: Failed to mmap counters!");

GlobalMetadataStorage = __mmap(0, 4096, PROT_READ0x1 | PROT_WRITE0x2,
                               MapPrivateOrShared | MAP_ANONYMOUS0x20, -1, 0);
assert(GlobalMetadataStorage != MAP_FAILED((void *)-1),
       "__bolt_instr_setup: failed to mmap page for metadata!");

GlobalAlloc = new (GlobalMetadataStorage) BumpPtrAllocator;
// Conservatively reserve 100MiB
GlobalAlloc->setMaxSize(0x6400000);
GlobalAlloc->setShared(Shared);
GlobalWriteProfileMutex = new (*GlobalAlloc, 0) Mutex();
if (__bolt_instr_num_ind_calls > 0)
  GlobalIndCallCounters =
      new (*GlobalAlloc, 0) IndirectCallHashTable[__bolt_instr_num_ind_calls];

if (__bolt_instr_sleep_time != 0) {
  // Separate instrumented process to the own process group
  if (__bolt_instr_wait_forks)
    __setpgid(0, 0);

  if (long PID = __fork())
    return;
  watchProcess();
}
1659}

1661extern "C" __attribute((force_align_arg_pointer)) void
1662instrumentIndirectCall(uint64_t Target, uint64_t IndCallID) {
GlobalIndCallCounters[IndCallID].incrementVal(Target, *GlobalAlloc);
1664}

1666/// We receive as in-stack arguments the identifier of the indirect call site
1667/// as well as the target address for the call
1668extern "C" __attribute((naked)) void __bolt_instr_indirect_call()
1669{
1670#if defined(__aarch64__)
// clang-format off
__asm__ __volatile__(SAVE_ALL"push %%rax\n" "push %%rbx\n" "push %%rcx\n" "push %%rdx\n" "push %%rdi\n"
 "push %%rsi\n" "push %%rbp\n" "push %%r8\n" "push %%r9\n" "push %%r10\n"
 "push %%r11\n" "push %%r12\n" "push %%r13\n" "push %%r14\n" "push %%r15\n"
 "sub $8, %%rsp\n"
                     "ldp x0, x1, [sp, #288]\n"
                     "bl instrumentIndirectCall\n"
                     RESTORE_ALL"add $8, %%rsp\n" "pop %%r15\n" "pop %%r14\n" "pop %%r13\n" "pop %%r12\n"
 "pop %%r11\n" "pop %%r10\n" "pop %%r9\n" "pop %%r8\n" "pop %%rbp\n"
 "pop %%rsi\n" "pop %%rdi\n" "pop %%rdx\n" "pop %%rcx\n" "pop %%rbx\n"
 "pop %%rax\n"
                     "ret\n"
                     :::);
// clang-format on
1679#else
// clang-format off
__asm__ __volatile__(SAVE_ALL"push %%rax\n" "push %%rbx\n" "push %%rcx\n" "push %%rdx\n" "push %%rdi\n"
 "push %%rsi\n" "push %%rbp\n" "push %%r8\n" "push %%r9\n" "push %%r10\n"
 "push %%r11\n" "push %%r12\n" "push %%r13\n" "push %%r14\n" "push %%r15\n"
 "sub $8, %%rsp\n"
                     "mov 0xa0(%%rsp), %%rdi\n"
                     "mov 0x98(%%rsp), %%rsi\n"
                     "call instrumentIndirectCall\n"
                     RESTORE_ALL"add $8, %%rsp\n" "pop %%r15\n" "pop %%r14\n" "pop %%r13\n" "pop %%r12\n"
 "pop %%r11\n" "pop %%r10\n" "pop %%r9\n" "pop %%r8\n" "pop %%rbp\n"
 "pop %%rsi\n" "pop %%rdi\n" "pop %%rdx\n" "pop %%rcx\n" "pop %%rbx\n"
 "pop %%rax\n"
                     "ret\n"
                     :::);
// clang-format on
1689#endif
1690}

1692extern "C" __attribute((naked)) void __bolt_instr_indirect_tailcall()
1693{
1694#if defined(__aarch64__)
// clang-format off
__asm__ __volatile__(SAVE_ALL"push %%rax\n" "push %%rbx\n" "push %%rcx\n" "push %%rdx\n" "push %%rdi\n"
 "push %%rsi\n" "push %%rbp\n" "push %%r8\n" "push %%r9\n" "push %%r10\n"
 "push %%r11\n" "push %%r12\n" "push %%r13\n" "push %%r14\n" "push %%r15\n"
 "sub $8, %%rsp\n"
                     "ldp x0, x1, [sp, #288]\n"
                     "bl instrumentIndirectCall\n"
                     RESTORE_ALL"add $8, %%rsp\n" "pop %%r15\n" "pop %%r14\n" "pop %%r13\n" "pop %%r12\n"
 "pop %%r11\n" "pop %%r10\n" "pop %%r9\n" "pop %%r8\n" "pop %%rbp\n"
 "pop %%rsi\n" "pop %%rdi\n" "pop %%rdx\n" "pop %%rcx\n" "pop %%rbx\n"
 "pop %%rax\n"
                     "ret\n"
                     :::);
// clang-format on
1703#else
// clang-format off
__asm__ __volatile__(SAVE_ALL"push %%rax\n" "push %%rbx\n" "push %%rcx\n" "push %%rdx\n" "push %%rdi\n"
 "push %%rsi\n" "push %%rbp\n" "push %%r8\n" "push %%r9\n" "push %%r10\n"
 "push %%r11\n" "push %%r12\n" "push %%r13\n" "push %%r14\n" "push %%r15\n"
 "sub $8, %%rsp\n"
                     "mov 0x98(%%rsp), %%rdi\n"
                     "mov 0x90(%%rsp), %%rsi\n"
                     "call instrumentIndirectCall\n"
                     RESTORE_ALL"add $8, %%rsp\n" "pop %%r15\n" "pop %%r14\n" "pop %%r13\n" "pop %%r12\n"
 "pop %%r11\n" "pop %%r10\n" "pop %%r9\n" "pop %%r8\n" "pop %%rbp\n"
 "pop %%rsi\n" "pop %%rdi\n" "pop %%rdx\n" "pop %%rcx\n" "pop %%rbx\n"
 "pop %%rax\n"
                     "ret\n"
                     :::);
// clang-format on
1713#endif
1714}

1716/// This is hooking ELF's entry, it needs to save all machine state.
1717extern "C" __attribute((naked)) void __bolt_instr_start()
1718{
1719#if defined(__aarch64__)
// clang-format off
__asm__ __volatile__(SAVE_ALL"push %%rax\n" "push %%rbx\n" "push %%rcx\n" "push %%rdx\n" "push %%rdi\n"
 "push %%rsi\n" "push %%rbp\n" "push %%r8\n" "push %%r9\n" "push %%r10\n"
 "push %%r11\n" "push %%r12\n" "push %%r13\n" "push %%r14\n" "push %%r15\n"
 "sub $8, %%rsp\n"
                     "bl __bolt_instr_setup\n"
                     RESTORE_ALL"add $8, %%rsp\n" "pop %%r15\n" "pop %%r14\n" "pop %%r13\n" "pop %%r12\n"
 "pop %%r11\n" "pop %%r10\n" "pop %%r9\n" "pop %%r8\n" "pop %%rbp\n"
 "pop %%rsi\n" "pop %%rdi\n" "pop %%rdx\n" "pop %%rcx\n" "pop %%rbx\n"
 "pop %%rax\n"
                     "adrp x16, __bolt_start_trampoline\n"
                     "add x16, x16, #:lo12:__bolt_start_trampoline\n"
                     "br x16\n"
                     :::);
// clang-format on
1729#else
// clang-format off
__asm__ __volatile__(SAVE_ALL"push %%rax\n" "push %%rbx\n" "push %%rcx\n" "push %%rdx\n" "push %%rdi\n"
 "push %%rsi\n" "push %%rbp\n" "push %%r8\n" "push %%r9\n" "push %%r10\n"
 "push %%r11\n" "push %%r12\n" "push %%r13\n" "push %%r14\n" "push %%r15\n"
 "sub $8, %%rsp\n"
                     "call __bolt_instr_setup\n"
                     RESTORE_ALL"add $8, %%rsp\n" "pop %%r15\n" "pop %%r14\n" "pop %%r13\n" "pop %%r12\n"
 "pop %%r11\n" "pop %%r10\n" "pop %%r9\n" "pop %%r8\n" "pop %%rbp\n"
 "pop %%rsi\n" "pop %%rdi\n" "pop %%rdx\n" "pop %%rcx\n" "pop %%rbx\n"
 "pop %%rax\n"
                     "jmp __bolt_start_trampoline\n"
                     :::);
// clang-format on
1737#endif
1738}

1740/// This is hooking into ELF's DT_FINI
1741extern "C" void __bolt_instr_fini() {
1742#if defined(__aarch64__)
// clang-format off
__asm__ __volatile__(SAVE_ALL"push %%rax\n" "push %%rbx\n" "push %%rcx\n" "push %%rdx\n" "push %%rdi\n"
 "push %%rsi\n" "push %%rbp\n" "push %%r8\n" "push %%r9\n" "push %%r10\n"
 "push %%r11\n" "push %%r12\n" "push %%r13\n" "push %%r14\n" "push %%r15\n"
 "sub $8, %%rsp\n"
                     "adrp x16, __bolt_fini_trampoline\n"
                     "add x16, x16, #:lo12:__bolt_fini_trampoline\n"
                     "blr x16\n"
                     RESTORE_ALL"add $8, %%rsp\n" "pop %%r15\n" "pop %%r14\n" "pop %%r13\n" "pop %%r12\n"
 "pop %%r11\n" "pop %%r10\n" "pop %%r9\n" "pop %%r8\n" "pop %%rbp\n"
 "pop %%rsi\n" "pop %%rdi\n" "pop %%rdx\n" "pop %%rcx\n" "pop %%rbx\n"
 "pop %%rax\n"
                     :::);
// clang-format on
1751#else
__asm__ __volatile__("call __bolt_fini_trampoline\n" :::);
1753#endif
if (__bolt_instr_sleep_time == 0) {
1
Assuming '__bolt_instr_sleep_time' is equal to 0→
2
←
Taking true branch→
  int FD = openProfile();
  __bolt_instr_data_dump(FD);
3
←
Calling '__bolt_instr_data_dump'→
  __close(FD);
}
DEBUG(report("Finished.\n")){};
1760}

1762#endif

1764#if defined(__APPLE__)

1766extern "C" void __bolt_instr_data_dump() {
ProfileWriterContext Ctx = readDescriptions();

int FD = 2;
BumpPtrAllocator Alloc;
const uint8_t *FuncDesc = Ctx.FuncDescriptions;
uint32_t bolt_instr_num_funcs = _bolt_instr_num_funcs_getter();

for (int I = 0, E = bolt_instr_num_funcs; I < E; ++I) {
  FuncDesc = writeFunctionProfile(FD, Ctx, FuncDesc, Alloc);
  Alloc.clear();
  DEBUG(reportNumber("FuncDesc now: ", (uint64_t)FuncDesc, 16)){};
}
assert(FuncDesc == (void *)Ctx.Strings,
       "FuncDesc ptr must be equal to stringtable");
1781}

1783// On OSX/iOS the final symbol name of an extern "C" function/variable contains
1784// one extra leading underscore: _bolt_instr_setup -> __bolt_instr_setup.
1785extern "C"
1786__attribute__((section("__TEXT,__setup")))
1787__attribute__((force_align_arg_pointer))
1788void _bolt_instr_setup() {
__asm__ __volatile__(SAVE_ALL"push %%rax\n" "push %%rbx\n" "push %%rcx\n" "push %%rdx\n" "push %%rdi\n"
 "push %%rsi\n" "push %%rbp\n" "push %%r8\n" "push %%r9\n" "push %%r10\n"
 "push %%r11\n" "push %%r12\n" "push %%r13\n" "push %%r14\n" "push %%r15\n"
 "sub $8, %%rsp\n" :::);

report("Hello!\n");

__asm__ __volatile__(RESTORE_ALL"add $8, %%rsp\n" "pop %%r15\n" "pop %%r14\n" "pop %%r13\n" "pop %%r12\n"
 "pop %%r11\n" "pop %%r10\n" "pop %%r9\n" "pop %%r8\n" "pop %%rbp\n"
 "pop %%rsi\n" "pop %%rdi\n" "pop %%rdx\n" "pop %%rcx\n" "pop %%rbx\n"
 "pop %%rax\n" :::);
1794}

1796extern "C"
1797__attribute__((section("__TEXT,__fini")))
1798__attribute__((force_align_arg_pointer))
1799void _bolt_instr_fini() {
report("Bye!\n");
__bolt_instr_data_dump();
1802}

1804#endif

←

/build/source/bolt/runtime/sys_x86_64.h

1	#ifndef LLVM_TOOLS_LLVM_BOLT_SYS_X86_64
2	#define LLVM_TOOLS_LLVM_BOLT_SYS_X86_64
3
4	// Save all registers while keeping 16B stack alignment
5	#define SAVE_ALL"push %%rax\n" "push %%rbx\n" "push %%rcx\n" "push %%rdx\n" "push %%rdi\n" "push %%rsi\n" "push %%rbp\n" "push %%r8\n" "push %%r9\n" "push %%r10\n" "push %%r11\n" "push %%r12\n" "push %%r13\n" "push %%r14\n" "push %%r15\n" "sub $8, %%rsp\n" \
6	"push %%rax\n" \
7	"push %%rbx\n" \
8	"push %%rcx\n" \
9	"push %%rdx\n" \
10	"push %%rdi\n" \
11	"push %%rsi\n" \
12	"push %%rbp\n" \
13	"push %%r8\n" \
14	"push %%r9\n" \
15	"push %%r10\n" \
16	"push %%r11\n" \
17	"push %%r12\n" \
18	"push %%r13\n" \
19	"push %%r14\n" \
20	"push %%r15\n" \
21	"sub $8, %%rsp\n"
22	// Mirrors SAVE_ALL
23	#define RESTORE_ALL"add $8, %%rsp\n" "pop %%r15\n" "pop %%r14\n" "pop %%r13\n" "pop %%r12\n" "pop %%r11\n" "pop %%r10\n" "pop %%r9\n" "pop %%r8\n" "pop %%rbp\n" "pop %%rsi\n" "pop %%rdi\n" "pop %%rdx\n" "pop %%rcx\n" "pop %%rbx\n" "pop %%rax\n" \
24	"add $8, %%rsp\n" \
25	"pop %%r15\n" \
26	"pop %%r14\n" \
27	"pop %%r13\n" \
28	"pop %%r12\n" \
29	"pop %%r11\n" \
30	"pop %%r10\n" \
31	"pop %%r9\n" \
32	"pop %%r8\n" \
33	"pop %%rbp\n" \
34	"pop %%rsi\n" \
35	"pop %%rdi\n" \
36	"pop %%rdx\n" \
37	"pop %%rcx\n" \
38	"pop %%rbx\n" \
39	"pop %%rax\n"
40
41	namespace {
42
43	// Get the difference between runtime addrress of .text section and
44	// static address in section header table. Can be extracted from arbitrary
45	// pc value recorded at runtime to get the corresponding static address, which
46	// in turn can be used to search for indirect call description. Needed because
47	// indirect call descriptions are read-only non-relocatable data.
48	uint64_t getTextBaseAddress() {
49	uint64_t DynAddr;
50	uint64_t StaticAddr;
51	__asm__ volatile("leaq __hot_end(%%rip), %0\n\t"
52	"movabsq $__hot_end, %1\n\t"
53	: "=r"(DynAddr), "=r"(StaticAddr));
54	return DynAddr - StaticAddr;
55	}
56
57	#define _STRINGIFY(x)"x" #x
58	#define STRINGIFY(x)"x" _STRINGIFY(x)"x"
59
60	uint64_t __read(uint64_t fd, const void *buf, uint64_t count) {
61	uint64_t ret;
62	#if defined(__APPLE__)
63	#define READ_SYSCALL0 0x2000003
64	#else
65	#define READ_SYSCALL0 0
66	#endif
67	__asm__ __volatile__("movq $" STRINGIFY(READ_SYSCALL)"0" ", %%rax\n"
68	"syscall\n"
69	: "=a"(ret)
70	: "D"(fd), "S"(buf), "d"(count)
71	: "cc", "rcx", "r11", "memory");
72	return ret;
73	}
74
75	uint64_t __write(uint64_t fd, const void *buf, uint64_t count) {
76	uint64_t ret;
77	#if defined(__APPLE__)
78	#define WRITE_SYSCALL1 0x2000004
79	#else
80	#define WRITE_SYSCALL1 1
81	#endif
82	__asm__ __volatile__("movq $" STRINGIFY(WRITE_SYSCALL)"1" ", %%rax\n"
83	"syscall\n"
84	: "=a"(ret)
85	: "D"(fd), "S"(buf), "d"(count)
86	: "cc", "rcx", "r11", "memory");
87	return ret;
88	}
89
90	void *__mmap(uint64_t addr, uint64_t size, uint64_t prot, uint64_t flags,
91	uint64_t fd, uint64_t offset) {
92	#if defined(__APPLE__)
93	#define MMAP_SYSCALL9 0x20000c5
94	#else
95	#define MMAP_SYSCALL9 9
96	#endif
97	void *ret;
98	register uint64_t r8 asm("r8") = fd;
99	register uint64_t r9 asm("r9") = offset;
100	register uint64_t r10 asm("r10") = flags;
101	__asm__ __volatile__("movq $" STRINGIFY(MMAP_SYSCALL)"9" ", %%rax\n"
102	"syscall\n"
103	: "=a"(ret)
104	: "D"(addr), "S"(size), "d"(prot), "r"(r10), "r"(r8),
105	"r"(r9)
106	: "cc", "rcx", "r11", "memory");
107	return ret;
108	}
109
110	uint64_t __munmap(void *addr, uint64_t size) {
111	#if defined(__APPLE__)
112	#define MUNMAP_SYSCALL11 0x2000049
113	#else
114	#define MUNMAP_SYSCALL11 11
115	#endif
116	uint64_t ret;
117	__asm__ __volatile__("movq $" STRINGIFY(MUNMAP_SYSCALL)"11" ", %%rax\n"
118	"syscall\n"
119	: "=a"(ret)
120	: "D"(addr), "S"(size)
121	: "cc", "rcx", "r11", "memory");
122	return ret;
123	}
124
125	uint64_t __sigprocmask(int how, const void set, void oldset) {
126	#if defined(__APPLE__)
127	#define SIGPROCMASK_SYSCALL14 0x2000030
128	#else
129	#define SIGPROCMASK_SYSCALL14 14
130	#endif
131	uint64_t ret;
132	register long r10 asm("r10") = sizeof(uint64_t);
133	__asm__ __volatile__("movq $" STRINGIFY(SIGPROCMASK_SYSCALL)"14" ", %%rax\n"
134	"syscall\n"
135	: "=a"(ret)
136	: "D"(how), "S"(set), "d"(oldset), "r"(r10)
137	: "cc", "rcx", "r11", "memory");
138	return ret;
139	}
140
141	uint64_t __getpid() {
142	uint64_t ret;
143	#if defined(__APPLE__)
144	#define GETPID_SYSCALL39 20
145	#else
146	#define GETPID_SYSCALL39 39
147	#endif
148	__asm__ __volatile__("movq $" STRINGIFY(GETPID_SYSCALL)"39" ", %%rax\n"
149	"syscall\n"
150	: "=a"(ret)
151	:
152	: "cc", "rcx", "r11", "memory");
153	return ret;
154	}
155
156	uint64_t __exit(uint64_t code) {
157	#if defined(__APPLE__)
158	#define EXIT_SYSCALL231 0x2000001
159	#else
160	#define EXIT_SYSCALL231 231
161	#endif
162	uint64_t ret;
163	__asm__ __volatile__("movq $" STRINGIFY(EXIT_SYSCALL)"231" ", %%rax\n"
164	"syscall\n"
165	: "=a"(ret)
166	: "D"(code)
167	: "cc", "rcx", "r11", "memory");
168	return ret;
169	}
170
171	#if !defined(__APPLE__)
172	// We use a stack-allocated buffer for string manipulation in many pieces of
173	// this code, including the code that prints each line of the fdata file. This
174	// buffer needs to accomodate large function names, but shouldn't be arbitrarily
175	// large (dynamically allocated) for simplicity of our memory space usage.
176
177	// Declare some syscall wrappers we use throughout this code to avoid linking
178	// against system libc.
179	uint64_t __open(const char *pathname, uint64_t flags, uint64_t mode) {
180	uint64_t ret;
181	__asm__ __volatile__("movq $2, %%rax\n"
182	"syscall"
183	: "=a"(ret)
184	: "D"(pathname), "S"(flags), "d"(mode)
185	: "cc", "rcx", "r11", "memory");
186	return ret;
187	}
188
189	long __getdents64(unsigned int fd, dirent64 *dirp, size_t count) {
190	long ret;
191	__asm__ __volatile__("movq $217, %%rax\n"
192	"syscall"
193	: "=a"(ret)
194	: "D"(fd), "S"(dirp), "d"(count)
195	: "cc", "rcx", "r11", "memory");
196	return ret;
197	}
198
199	uint64_t __readlink(const char pathname, char buf, size_t bufsize) {
200	uint64_t ret;
201	__asm__ __volatile__("movq $89, %%rax\n"
202	"syscall"
203	: "=a"(ret)
204	: "D"(pathname), "S"(buf), "d"(bufsize)
205	: "cc", "rcx", "r11", "memory");
206	return ret;
207	}
208
209	uint64_t __lseek(uint64_t fd, uint64_t pos, uint64_t whence) {
210	uint64_t ret;
211	__asm__ __volatile__("movq $8, %%rax\n"
212	"syscall\n"
213	: "=a"(ret)
214	: "D"(fd), "S"(pos), "d"(whence)
215	: "cc", "rcx", "r11", "memory");
216	return ret;
217	}
218
219	int __ftruncate(uint64_t fd, uint64_t length) {
220	int ret;
221	__asm__ __volatile__("movq $77, %%rax\n"
222	"syscall\n"
223	: "=a"(ret)
224	: "D"(fd), "S"(length)
225	: "cc", "rcx", "r11", "memory");
226	return ret;
227	}
228
229	int __close(uint64_t fd) {
230	uint64_t ret;
231	__asm__ __volatile__("movq $3, %%rax\n"
232	"syscall\n"
233	: "=a"(ret)
234	: "D"(fd)
235	: "cc", "rcx", "r11", "memory");
236	return ret;
237	}
238
239	int __madvise(void *addr, size_t length, int advice) {
240	int ret;
241	__asm__ __volatile__("movq $28, %%rax\n"
242	"syscall\n"
243	: "=a"(ret)
244	: "D"(addr), "S"(length), "d"(advice)
245	: "cc", "rcx", "r11", "memory");
246	return ret;
247	}
248
249	int __uname(struct UtsNameTy *Buf) {
250	int Ret;
251	__asm__ __volatile__("movq $63, %%rax\n"
252	"syscall\n"
253	: "=a"(Ret)
254	: "D"(Buf)
255	: "cc", "rcx", "r11", "memory");
256	return Ret;
257	}
258
259	uint64_t __nanosleep(const timespec req, timespec rem) {
260	uint64_t ret;
261	__asm__ __volatile__("movq $35, %%rax\n"
262	"syscall\n"
263	: "=a"(ret)
264	: "D"(req), "S"(rem)
265	: "cc", "rcx", "r11", "memory");
266	return ret;
267	}
268
269	int64_t __fork() {
270	uint64_t ret;
271	__asm__ __volatile__("movq $57, %%rax\n"
272	"syscall\n"
273	: "=a"(ret)
274	:
275	: "cc", "rcx", "r11", "memory");
276	return ret;
277	}
278
279	int __mprotect(void *addr, size_t len, int prot) {
280	int ret;
281	__asm__ __volatile__("movq $10, %%rax\n"
282	"syscall\n"
283	: "=a"(ret)
284	: "D"(addr), "S"(len), "d"(prot)
285	: "cc", "rcx", "r11", "memory");
286	return ret;
287	}
288
289	uint64_t __getppid() {
290	uint64_t ret;
291	__asm__ __volatile__("movq $110, %%rax\n"
292	"syscall\n"
293	: "=a"(ret)
294	:
295	: "cc", "rcx", "r11", "memory");
296	return ret;
297	}
298
299	int __setpgid(uint64_t pid, uint64_t pgid) {
300	int ret;
301	__asm__ __volatile__("movq $109, %%rax\n"
302	"syscall\n"
303	: "=a"(ret)
304	: "D"(pid), "S"(pgid)
305	: "cc", "rcx", "r11", "memory");
306	return ret;
307	}
308
309	uint64_t __getpgid(uint64_t pid) {
310	uint64_t ret;
311	__asm__ __volatile__("movq $121, %%rax\n"
312	"syscall\n"
313	: "=a"(ret)
314	: "D"(pid)
315	: "cc", "rcx", "r11", "memory");
316	return ret;
317	}
318
319	int __kill(uint64_t pid, int sig) {
320	int ret;
321	__asm__ __volatile__("movq $62, %%rax\n"
322	"syscall\n"
323	: "=a"(ret)
324	: "D"(pid), "S"(sig)
325	: "cc", "rcx", "r11", "memory");
326	return ret;
327	}
328
329	int __fsync(int fd) {
330	int ret;
331	__asm__ __volatile__("movq $74, %%rax\n"
332	"syscall\n"
333	: "=a"(ret)
334	: "D"(fd)
335	: "cc", "rcx", "r11", "memory");
336	return ret;
337	}
338
339	// %rdi %rsi %rdx %r10 %r8
340	// sys_prctl int option unsigned unsigned unsigned unsigned
341	// long arg2 long arg3 long arg4 long arg5
342	int __prctl(int Option, unsigned long Arg2, unsigned long Arg3,
343	unsigned long Arg4, unsigned long Arg5) {
344	int Ret;
345	register long rdx asm("rdx") = Arg3;
346	register long r8 asm("r8") = Arg5;
347	register long r10 asm("r10") = Arg4;
348	__asm__ __volatile__("movq $157, %%rax\n"
349	"syscall\n"
350	: "=a"(Ret)
351	: "D"(Option), "S"(Arg2), "d"(rdx), "r"(r10), "r"(r8)
352	:);
353	return Ret;
354	}
355
356	#endif
357
358	} // anonymous namespace
359
360	#endif