/build/source/lld/MachO/SyntheticSections.cpp

Bug Summary

File:	build/source/lld/MachO/SyntheticSections.cpp
Warning:	line 1644, column 29 The result of the left shift is undefined due to shifting by '32', which is greater or equal to the width of type 'int'

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 SyntheticSections.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 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/source/build-llvm -resource-dir /usr/lib/llvm-16/lib/clang/16 -I tools/lld/MachO -I /build/source/lld/MachO -I /build/source/lld/include -I tools/lld/include -I include -I /build/source/llvm/include -I /build/source/llvm/../libunwind/include -D LLD_VENDOR="Debian" -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -D _FORTIFY_SOURCE=2 -D NDEBUG -U 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-16/lib/clang/16/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 -fmacro-prefix-map=/build/source/build-llvm=build-llvm -fmacro-prefix-map=/build/source/= -fcoverage-prefix-map=/build/source/build-llvm=build-llvm -fcoverage-prefix-map=/build/source/= -source-date-epoch 1674602410 -O3 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/source/build-llvm -fdebug-prefix-map=/build/source/build-llvm=build-llvm -fdebug-prefix-map=/build/source/= -fdebug-prefix-map=/build/source/build-llvm=build-llvm -fdebug-prefix-map=/build/source/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2023-01-25-024556-16494-1 -x c++ /build/source/lld/MachO/SyntheticSections.cpp

/build/source/lld/MachO/SyntheticSections.cpp

→

1//===- SyntheticSections.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//===----------------------------------------------------------------------===//

9#include "SyntheticSections.h"
10#include "ConcatOutputSection.h"
11#include "Config.h"
12#include "ExportTrie.h"
13#include "InputFiles.h"
14#include "MachOStructs.h"
15#include "OutputSegment.h"
16#include "SymbolTable.h"
17#include "Symbols.h"

19#include "lld/Common/CommonLinkerContext.h"
20#include "llvm/ADT/STLExtras.h"
21#include "llvm/Config/llvm-config.h"
22#include "llvm/Support/EndianStream.h"
23#include "llvm/Support/FileSystem.h"
24#include "llvm/Support/LEB128.h"
25#include "llvm/Support/Parallel.h"
26#include "llvm/Support/Path.h"
27#include "llvm/Support/xxhash.h"

29#if defined(__APPLE__)
30#include <sys/mman.h>

32#define COMMON_DIGEST_FOR_OPENSSL
33#include <CommonCrypto/CommonDigest.h>
34#else
35#include "llvm/Support/SHA256.h"
36#endif

38#ifdef LLVM_HAVE_LIBXAR
39#include <fcntl.h>
40extern "C" {
41#include <xar/xar.h>
42}
43#endif

45using namespace llvm;
46using namespace llvm::MachO;
47using namespace llvm::support;
48using namespace llvm::support::endian;
49using namespace lld;
50using namespace lld::macho;

52// Reads `len` bytes at data and writes the 32-byte SHA256 checksum to `output`.
53static void sha256(const uint8_t *data, size_t len, uint8_t *output) {
54#if defined(__APPLE__)
// FIXME: Make LLVM's SHA256 faster and use it unconditionally. See PR56121
// for some notes on this.
CC_SHA256(data, len, output);
58#else
ArrayRef<uint8_t> block(data, len);
std::array<uint8_t, 32> hash = SHA256::hash(block);
static_assert(hash.size() == CodeSignatureSection::hashSize);
memcpy(output, hash.data(), hash.size());
63#endif
64}

66InStruct macho::in;
67std::vector<SyntheticSection *> macho::syntheticSections;

69SyntheticSection::SyntheticSection(const char *segname, const char *name)
  : OutputSection(SyntheticKind, name) {
std::tie(this->segname, this->name) = maybeRenameSection({segname, name});
isec = makeSyntheticInputSection(segname, name);
isec->parent = this;
syntheticSections.push_back(this);
75}

77// dyld3's MachOLoaded::getSlide() assumes that the __TEXT segment starts
78// from the beginning of the file (i.e. the header).
79MachHeaderSection::MachHeaderSection()
  : SyntheticSection(segment_names::text, section_names::header) {
// XXX: This is a hack. (See D97007)
// Setting the index to 1 to pretend that this section is the text
// section.
index = 1;
isec->isFinal = true;
86}

88void MachHeaderSection::addLoadCommand(LoadCommand *lc) {
loadCommands.push_back(lc);
sizeOfCmds += lc->getSize();
91}

93uint64_t MachHeaderSection::getSize() const {
uint64_t size = target->headerSize + sizeOfCmds + config->headerPad;
// If we are emitting an encryptable binary, our load commands must have a
// separate (non-encrypted) page to themselves.
if (config->emitEncryptionInfo)
  size = alignTo(size, target->getPageSize());
return size;
100}

102static uint32_t cpuSubtype() {
uint32_t subtype = target->cpuSubtype;

if (config->outputType == MH_EXECUTE && !config->staticLink &&
    target->cpuSubtype == CPU_SUBTYPE_X86_64_ALL &&
    config->platform() == PLATFORM_MACOS &&
    config->platformInfo.minimum >= VersionTuple(10, 5))
  subtype |= CPU_SUBTYPE_LIB64;

return subtype;
112}

114static bool hasWeakBinding() {
return config->emitChainedFixups ? in.chainedFixups->hasWeakBinding()
                                 : in.weakBinding->hasEntry();
117}

119static bool hasNonWeakDefinition() {
return config->emitChainedFixups ? in.chainedFixups->hasNonWeakDefinition()
                                 : in.weakBinding->hasNonWeakDefinition();
122}

124void MachHeaderSection::writeTo(uint8_t *buf) const {
auto *hdr = reinterpret_cast<mach_header *>(buf);
hdr->magic = target->magic;
hdr->cputype = target->cpuType;
hdr->cpusubtype = cpuSubtype();
hdr->filetype = config->outputType;
hdr->ncmds = loadCommands.size();
hdr->sizeofcmds = sizeOfCmds;
hdr->flags = MH_DYLDLINK;

if (config->namespaceKind == NamespaceKind::twolevel)
  hdr->flags |= MH_NOUNDEFS | MH_TWOLEVEL;

if (config->outputType == MH_DYLIB && !config->hasReexports)
  hdr->flags |= MH_NO_REEXPORTED_DYLIBS;

if (config->markDeadStrippableDylib)
  hdr->flags |= MH_DEAD_STRIPPABLE_DYLIB;

if (config->outputType == MH_EXECUTE && config->isPic)
  hdr->flags |= MH_PIE;

if (config->outputType == MH_DYLIB && config->applicationExtension)
  hdr->flags |= MH_APP_EXTENSION_SAFE;

if (in.exports->hasWeakSymbol || hasNonWeakDefinition())
  hdr->flags |= MH_WEAK_DEFINES;

if (in.exports->hasWeakSymbol || hasWeakBinding())
  hdr->flags |= MH_BINDS_TO_WEAK;

for (const OutputSegment *seg : outputSegments) {
  for (const OutputSection *osec : seg->getSections()) {
    if (isThreadLocalVariables(osec->flags)) {
      hdr->flags |= MH_HAS_TLV_DESCRIPTORS;
      break;
    }
  }
}

uint8_t *p = reinterpret_cast<uint8_t *>(hdr) + target->headerSize;
for (const LoadCommand *lc : loadCommands) {
  lc->writeTo(p);
  p += lc->getSize();
}
169}

171PageZeroSection::PageZeroSection()
  : SyntheticSection(segment_names::pageZero, section_names::pageZero) {}

174RebaseSection::RebaseSection()
  : LinkEditSection(segment_names::linkEdit, section_names::rebase) {}

177namespace {
178struct RebaseState {
uint64_t sequenceLength;
uint64_t skipLength;
181};
182} // namespace

184static void emitIncrement(uint64_t incr, raw_svector_ostream &os) {
assert(incr != 0)(static_cast <bool> (incr != 0) ? void (0) : __assert_fail
 ("incr != 0", "lld/MachO/SyntheticSections.cpp", 185, __extension__
 __PRETTY_FUNCTION__));

if ((incr >> target->p2WordSize) <= REBASE_IMMEDIATE_MASK &&
    (incr % target->wordSize) == 0) {
  os << static_cast<uint8_t>(REBASE_OPCODE_ADD_ADDR_IMM_SCALED |
                             (incr >> target->p2WordSize));
} else {
  os << static_cast<uint8_t>(REBASE_OPCODE_ADD_ADDR_ULEB);
  encodeULEB128(incr, os);
}
195}

197static void flushRebase(const RebaseState &state, raw_svector_ostream &os) {
assert(state.sequenceLength > 0)(static_cast <bool> (state.sequenceLength > 0) ? void
 (0) : __assert_fail ("state.sequenceLength > 0", "lld/MachO/SyntheticSections.cpp"
, 198, __extension__ __PRETTY_FUNCTION__));

if (state.skipLength == target->wordSize) {
  if (state.sequenceLength <= REBASE_IMMEDIATE_MASK) {
    os << static_cast<uint8_t>(REBASE_OPCODE_DO_REBASE_IMM_TIMES |
                               state.sequenceLength);
  } else {
    os << static_cast<uint8_t>(REBASE_OPCODE_DO_REBASE_ULEB_TIMES);
    encodeULEB128(state.sequenceLength, os);
  }
} else if (state.sequenceLength == 1) {
  os << static_cast<uint8_t>(REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB);
  encodeULEB128(state.skipLength - target->wordSize, os);
} else {
  os << static_cast<uint8_t>(
      REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB);
  encodeULEB128(state.sequenceLength, os);
  encodeULEB128(state.skipLength - target->wordSize, os);
}
217}

219// Rebases are communicated to dyld using a bytecode, whose opcodes cause the
220// memory location at a specific address to be rebased and/or the address to be
221// incremented.
222//
223// Opcode REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB is the most generic
224// one, encoding a series of evenly spaced addresses. This algorithm works by
225// splitting up the sorted list of addresses into such chunks. If the locations
226// are consecutive or the sequence consists of a single location, flushRebase
227// will use a smaller, more specialized encoding.
228static void encodeRebases(const OutputSegment *seg,
                        MutableArrayRef<Location> locations,
                        raw_svector_ostream &os) {
// dyld operates on segments. Translate section offsets into segment offsets.
for (Location &loc : locations)
  loc.offset =
      loc.isec->parent->getSegmentOffset() + loc.isec->getOffset(loc.offset);
// The algorithm assumes that locations are unique.
Location *end =
    llvm::unique(locations, [](const Location &a, const Location &b) {
      return a.offset == b.offset;
    });
size_t count = end - locations.begin();

os << static_cast<uint8_t>(REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB |
                           seg->index);
assert(!locations.empty())(static_cast <bool> (!locations.empty()) ? void (0) : __assert_fail
 ("!locations.empty()", "lld/MachO/SyntheticSections.cpp", 244
, __extension__ __PRETTY_FUNCTION__));
uint64_t offset = locations[0].offset;
encodeULEB128(offset, os);

RebaseState state{1, target->wordSize};

for (size_t i = 1; i < count; ++i) {
  offset = locations[i].offset;

  uint64_t skip = offset - locations[i - 1].offset;
  assert(skip != 0 && "duplicate locations should have been weeded out")(static_cast <bool> (skip != 0 && "duplicate locations should have been weeded out"
) ? void (0) : __assert_fail ("skip != 0 && \"duplicate locations should have been weeded out\""
, "lld/MachO/SyntheticSections.cpp", 254, __extension__ __PRETTY_FUNCTION__
));

  if (skip == state.skipLength) {
    ++state.sequenceLength;
  } else if (state.sequenceLength == 1) {
    ++state.sequenceLength;
    state.skipLength = skip;
  } else if (skip < state.skipLength) {
    // The address is lower than what the rebase pointer would be if the last
    // location would be part of a sequence. We start a new sequence from the
    // previous location.
    --state.sequenceLength;
    flushRebase(state, os);

    state.sequenceLength = 2;
    state.skipLength = skip;
  } else {
    // The address is at some positive offset from the rebase pointer. We
    // start a new sequence which begins with the current location.
    flushRebase(state, os);
    emitIncrement(skip - state.skipLength, os);
    state.sequenceLength = 1;
    state.skipLength = target->wordSize;
  }
}
flushRebase(state, os);
280}

282void RebaseSection::finalizeContents() {
if (locations.empty())
  return;

raw_svector_ostream os{contents};
os << static_cast<uint8_t>(REBASE_OPCODE_SET_TYPE_IMM | REBASE_TYPE_POINTER);

llvm::sort(locations, [](const Location &a, const Location &b) {
  return a.isec->getVA(a.offset) < b.isec->getVA(b.offset);
});

for (size_t i = 0, count = locations.size(); i < count;) {
  const OutputSegment *seg = locations[i].isec->parent->parent;
  size_t j = i + 1;
  while (j < count && locations[j].isec->parent->parent == seg)
    ++j;
  encodeRebases(seg, {locations.data() + i, locations.data() + j}, os);
  i = j;
}
os << static_cast<uint8_t>(REBASE_OPCODE_DONE);
302}

304void RebaseSection::writeTo(uint8_t *buf) const {
memcpy(buf, contents.data(), contents.size());
306}

308NonLazyPointerSectionBase::NonLazyPointerSectionBase(const char *segname,
                                                   const char *name)
  : SyntheticSection(segname, name) {
align = target->wordSize;
312}

314void macho::addNonLazyBindingEntries(const Symbol *sym,
                                   const InputSection *isec, uint64_t offset,
                                   int64_t addend) {
if (config->emitChainedFixups) {
  if (needsBinding(sym))
    in.chainedFixups->addBinding(sym, isec, offset, addend);
  else if (isa<Defined>(sym))
    in.chainedFixups->addRebase(isec, offset);
  else
    llvm_unreachable("cannot bind to an undefined symbol")::llvm::llvm_unreachable_internal("cannot bind to an undefined symbol"
, "lld/MachO/SyntheticSections.cpp", 323);
  return;
}

if (const auto *dysym = dyn_cast<DylibSymbol>(sym)) {
  in.binding->addEntry(dysym, isec, offset, addend);
  if (dysym->isWeakDef())
    in.weakBinding->addEntry(sym, isec, offset, addend);
} else if (const auto *defined = dyn_cast<Defined>(sym)) {
  in.rebase->addEntry(isec, offset);
  if (defined->isExternalWeakDef())
    in.weakBinding->addEntry(sym, isec, offset, addend);
  else if (defined->interposable)
    in.binding->addEntry(sym, isec, offset, addend);
} else {
  // Undefined symbols are filtered out in scanRelocations(); we should never
  // get here
  llvm_unreachable("cannot bind to an undefined symbol")::llvm::llvm_unreachable_internal("cannot bind to an undefined symbol"
, "lld/MachO/SyntheticSections.cpp", 340);
}
342}

344void NonLazyPointerSectionBase::addEntry(Symbol *sym) {
if (entries.insert(sym)) {
  assert(!sym->isInGot())(static_cast <bool> (!sym->isInGot()) ? void (0) : __assert_fail
 ("!sym->isInGot()", "lld/MachO/SyntheticSections.cpp", 346
, __extension__ __PRETTY_FUNCTION__));
  sym->gotIndex = entries.size() - 1;

  addNonLazyBindingEntries(sym, isec, sym->gotIndex * target->wordSize);
}
351}

353void macho::writeChainedRebase(uint8_t *buf, uint64_t targetVA) {
assert(config->emitChainedFixups)(static_cast <bool> (config->emitChainedFixups) ? void
 (0) : __assert_fail ("config->emitChainedFixups", "lld/MachO/SyntheticSections.cpp"
, 354, __extension__ __PRETTY_FUNCTION__));
assert(target->wordSize == 8 && "Only 64-bit platforms are supported")(static_cast <bool> (target->wordSize == 8 &&
 "Only 64-bit platforms are supported") ? void (0) : __assert_fail
 ("target->wordSize == 8 && \"Only 64-bit platforms are supported\""
, "lld/MachO/SyntheticSections.cpp", 355, __extension__ __PRETTY_FUNCTION__
));
auto *rebase = reinterpret_cast<dyld_chained_ptr_64_rebase *>(buf);
rebase->target = targetVA & 0xf'ffff'ffff;
rebase->high8 = (targetVA >> 56);
rebase->reserved = 0;
rebase->next = 0;
rebase->bind = 0;

// The fixup format places a 64 GiB limit on the output's size.
// Should we handle this gracefully?
uint64_t encodedVA = rebase->target | ((uint64_t)rebase->high8 << 56);
if (encodedVA != targetVA)
  error("rebase target address 0x" + Twine::utohexstr(targetVA) +
        " does not fit into chained fixup. Re-link with -no_fixup_chains");
369}

371static void writeChainedBind(uint8_t *buf, const Symbol *sym, int64_t addend) {
assert(config->emitChainedFixups)(static_cast <bool> (config->emitChainedFixups) ? void
 (0) : __assert_fail ("config->emitChainedFixups", "lld/MachO/SyntheticSections.cpp"
, 372, __extension__ __PRETTY_FUNCTION__));
assert(target->wordSize == 8 && "Only 64-bit platforms are supported")(static_cast <bool> (target->wordSize == 8 &&
 "Only 64-bit platforms are supported") ? void (0) : __assert_fail
 ("target->wordSize == 8 && \"Only 64-bit platforms are supported\""
, "lld/MachO/SyntheticSections.cpp", 373, __extension__ __PRETTY_FUNCTION__
));
auto *bind = reinterpret_cast<dyld_chained_ptr_64_bind *>(buf);
auto [ordinal, inlineAddend] = in.chainedFixups->getBinding(sym, addend);
bind->ordinal = ordinal;
bind->addend = inlineAddend;
bind->reserved = 0;
bind->next = 0;
bind->bind = 1;
381}

383void macho::writeChainedFixup(uint8_t *buf, const Symbol *sym, int64_t addend) {
if (needsBinding(sym))
  writeChainedBind(buf, sym, addend);
else
  writeChainedRebase(buf, sym->getVA() + addend);
388}

390void NonLazyPointerSectionBase::writeTo(uint8_t *buf) const {
if (config->emitChainedFixups) {
  for (const auto &[i, entry] : llvm::enumerate(entries))
    writeChainedFixup(&buf[i * target->wordSize], entry, 0);
} else {
  for (const auto &[i, entry] : llvm::enumerate(entries))
    if (auto *defined = dyn_cast<Defined>(entry))
      write64le(&buf[i * target->wordSize], defined->getVA());
}
399}

401GotSection::GotSection()
  : NonLazyPointerSectionBase(segment_names::data, section_names::got) {
flags = S_NON_LAZY_SYMBOL_POINTERS;
404}

406TlvPointerSection::TlvPointerSection()
  : NonLazyPointerSectionBase(segment_names::data,
                              section_names::threadPtrs) {
flags = S_THREAD_LOCAL_VARIABLE_POINTERS;
410}

412BindingSection::BindingSection()
  : LinkEditSection(segment_names::linkEdit, section_names::binding) {}

415namespace {
416struct Binding {
OutputSegment *segment = nullptr;
uint64_t offset = 0;
int64_t addend = 0;
420};
421struct BindIR {
// Default value of 0xF0 is not valid opcode and should make the program
// scream instead of accidentally writing "valid" values.
uint8_t opcode = 0xF0;
uint64_t data = 0;
uint64_t consecutiveCount = 0;
427};
428} // namespace

430// Encode a sequence of opcodes that tell dyld to write the address of symbol +
431// addend at osec->addr + outSecOff.
432//
433// The bind opcode "interpreter" remembers the values of each binding field, so
434// we only need to encode the differences between bindings. Hence the use of
435// lastBinding.
436static void encodeBinding(const OutputSection *osec, uint64_t outSecOff,
                        int64_t addend, Binding &lastBinding,
                        std::vector<BindIR> &opcodes) {
OutputSegment *seg = osec->parent;
uint64_t offset = osec->getSegmentOffset() + outSecOff;
if (lastBinding.segment != seg) {
  opcodes.push_back(
      {static_cast<uint8_t>(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB |
                            seg->index),
       offset});
  lastBinding.segment = seg;
  lastBinding.offset = offset;
} else if (lastBinding.offset != offset) {
  opcodes.push_back({BIND_OPCODE_ADD_ADDR_ULEB, offset - lastBinding.offset});
  lastBinding.offset = offset;
}

if (lastBinding.addend != addend) {
  opcodes.push_back(
      {BIND_OPCODE_SET_ADDEND_SLEB, static_cast<uint64_t>(addend)});
  lastBinding.addend = addend;
}

opcodes.push_back({BIND_OPCODE_DO_BIND, 0});
// DO_BIND causes dyld to both perform the binding and increment the offset
lastBinding.offset += target->wordSize;
462}

464static void optimizeOpcodes(std::vector<BindIR> &opcodes) {
// Pass 1: Combine bind/add pairs
size_t i;
int pWrite = 0;
for (i = 1; i < opcodes.size(); ++i, ++pWrite) {
  if ((opcodes[i].opcode == BIND_OPCODE_ADD_ADDR_ULEB) &&
      (opcodes[i - 1].opcode == BIND_OPCODE_DO_BIND)) {
    opcodes[pWrite].opcode = BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB;
    opcodes[pWrite].data = opcodes[i].data;
    ++i;
  } else {
    opcodes[pWrite] = opcodes[i - 1];
  }
}
if (i == opcodes.size())
  opcodes[pWrite] = opcodes[i - 1];
opcodes.resize(pWrite + 1);

// Pass 2: Compress two or more bind_add opcodes
pWrite = 0;
for (i = 1; i < opcodes.size(); ++i, ++pWrite) {
  if ((opcodes[i].opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB) &&
      (opcodes[i - 1].opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB) &&
      (opcodes[i].data == opcodes[i - 1].data)) {
    opcodes[pWrite].opcode = BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB;
    opcodes[pWrite].consecutiveCount = 2;
    opcodes[pWrite].data = opcodes[i].data;
    ++i;
    while (i < opcodes.size() &&
           (opcodes[i].opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB) &&
           (opcodes[i].data == opcodes[i - 1].data)) {
      opcodes[pWrite].consecutiveCount++;
      ++i;
    }
  } else {
    opcodes[pWrite] = opcodes[i - 1];
  }
}
if (i == opcodes.size())
  opcodes[pWrite] = opcodes[i - 1];
opcodes.resize(pWrite + 1);

// Pass 3: Use immediate encodings
// Every binding is the size of one pointer. If the next binding is a
// multiple of wordSize away that is within BIND_IMMEDIATE_MASK, the
// opcode can be scaled by wordSize into a single byte and dyld will
// expand it to the correct address.
for (auto &p : opcodes) {
  // It's unclear why the check needs to be less than BIND_IMMEDIATE_MASK,
  // but ld64 currently does this. This could be a potential bug, but
  // for now, perform the same behavior to prevent mysterious bugs.
  if ((p.opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB) &&
      ((p.data / target->wordSize) < BIND_IMMEDIATE_MASK) &&
      ((p.data % target->wordSize) == 0)) {
    p.opcode = BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED;
    p.data /= target->wordSize;
  }
}
522}

524static void flushOpcodes(const BindIR &op, raw_svector_ostream &os) {
uint8_t opcode = op.opcode & BIND_OPCODE_MASK;
switch (opcode) {
case BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB:
case BIND_OPCODE_ADD_ADDR_ULEB:
case BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB:
  os << op.opcode;
  encodeULEB128(op.data, os);
  break;
case BIND_OPCODE_SET_ADDEND_SLEB:
  os << op.opcode;
  encodeSLEB128(static_cast<int64_t>(op.data), os);
  break;
case BIND_OPCODE_DO_BIND:
  os << op.opcode;
  break;
case BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB:
  os << op.opcode;
  encodeULEB128(op.consecutiveCount, os);
  encodeULEB128(op.data, os);
  break;
case BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED:
  os << static_cast<uint8_t>(op.opcode | op.data);
  break;
default:
  llvm_unreachable("cannot bind to an unrecognized symbol")::llvm::llvm_unreachable_internal("cannot bind to an unrecognized symbol"
, "lld/MachO/SyntheticSections.cpp", 549);
}
551}

553// Non-weak bindings need to have their dylib ordinal encoded as well.
554static int16_t ordinalForDylibSymbol(const DylibSymbol &dysym) {
if (config->namespaceKind == NamespaceKind::flat || dysym.isDynamicLookup())
  return static_cast<int16_t>(BIND_SPECIAL_DYLIB_FLAT_LOOKUP);
assert(dysym.getFile()->isReferenced())(static_cast <bool> (dysym.getFile()->isReferenced()
) ? void (0) : __assert_fail ("dysym.getFile()->isReferenced()"
, "lld/MachO/SyntheticSections.cpp", 557, __extension__ __PRETTY_FUNCTION__
));
return dysym.getFile()->ordinal;
559}

561static int16_t ordinalForSymbol(const Symbol &sym) {
if (const auto *dysym = dyn_cast<DylibSymbol>(&sym))
  return ordinalForDylibSymbol(*dysym);
assert(cast<Defined>(&sym)->interposable)(static_cast <bool> (cast<Defined>(&sym)->
interposable) ? void (0) : __assert_fail ("cast<Defined>(&sym)->interposable"
, "lld/MachO/SyntheticSections.cpp", 564, __extension__ __PRETTY_FUNCTION__
));
return BIND_SPECIAL_DYLIB_FLAT_LOOKUP;
566}

568static void encodeDylibOrdinal(int16_t ordinal, raw_svector_ostream &os) {
if (ordinal <= 0) {
  os << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_SPECIAL_IMM |
                             (ordinal & BIND_IMMEDIATE_MASK));
} else if (ordinal <= BIND_IMMEDIATE_MASK) {
  os << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_ORDINAL_IMM | ordinal);
} else {
  os << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB);
  encodeULEB128(ordinal, os);
}
578}

580static void encodeWeakOverride(const Defined *defined,
                             raw_svector_ostream &os) {
os << static_cast<uint8_t>(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM |
                           BIND_SYMBOL_FLAGS_NON_WEAK_DEFINITION)
   << defined->getName() << '\0';
585}

587// Organize the bindings so we can encoded them with fewer opcodes.
588//
589// First, all bindings for a given symbol should be grouped together.
590// BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM is the largest opcode (since it
591// has an associated symbol string), so we only want to emit it once per symbol.
592//
593// Within each group, we sort the bindings by address. Since bindings are
594// delta-encoded, sorting them allows for a more compact result. Note that
595// sorting by address alone ensures that bindings for the same segment / section
596// are located together, minimizing the number of times we have to emit
597// BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB.
598//
599// Finally, we sort the symbols by the address of their first binding, again
600// to facilitate the delta-encoding process.
601template <class Sym>
602std::vector<std::pair<const Sym *, std::vector<BindingEntry>>>
603sortBindings(const BindingsMap<const Sym *> &bindingsMap) {
std::vector<std::pair<const Sym *, std::vector<BindingEntry>>> bindingsVec(
    bindingsMap.begin(), bindingsMap.end());
for (auto &p : bindingsVec) {
  std::vector<BindingEntry> &bindings = p.second;
  llvm::sort(bindings, [](const BindingEntry &a, const BindingEntry &b) {
    return a.target.getVA() < b.target.getVA();
  });
}
llvm::sort(bindingsVec, [](const auto &a, const auto &b) {
  return a.second[0].target.getVA() < b.second[0].target.getVA();
});
return bindingsVec;
616}

618// Emit bind opcodes, which are a stream of byte-sized opcodes that dyld
619// interprets to update a record with the following fields:
620//  * segment index (of the segment to write the symbol addresses to, typically
621//    the __DATA_CONST segment which contains the GOT)
622//  * offset within the segment, indicating the next location to write a binding
623//  * symbol type
624//  * symbol library ordinal (the index of its library's LC_LOAD_DYLIB command)
625//  * symbol name
626//  * addend
627// When dyld sees BIND_OPCODE_DO_BIND, it uses the current record state to bind
628// a symbol in the GOT, and increments the segment offset to point to the next
629// entry. It does *not* clear the record state after doing the bind, so
630// subsequent opcodes only need to encode the differences between bindings.
631void BindingSection::finalizeContents() {
raw_svector_ostream os{contents};
Binding lastBinding;
int16_t lastOrdinal = 0;

for (auto &p : sortBindings(bindingsMap)) {
  const Symbol *sym = p.first;
  std::vector<BindingEntry> &bindings = p.second;
  uint8_t flags = BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM;
  if (sym->isWeakRef())
    flags |= BIND_SYMBOL_FLAGS_WEAK_IMPORT;
  os << flags << sym->getName() << '\0'
     << static_cast<uint8_t>(BIND_OPCODE_SET_TYPE_IMM | BIND_TYPE_POINTER);
  int16_t ordinal = ordinalForSymbol(*sym);
  if (ordinal != lastOrdinal) {
    encodeDylibOrdinal(ordinal, os);
    lastOrdinal = ordinal;
  }
  std::vector<BindIR> opcodes;
  for (const BindingEntry &b : bindings)
    encodeBinding(b.target.isec->parent,
                  b.target.isec->getOffset(b.target.offset), b.addend,
                  lastBinding, opcodes);
  if (config->optimize > 1)
    optimizeOpcodes(opcodes);
  for (const auto &op : opcodes)
    flushOpcodes(op, os);
}
if (!bindingsMap.empty())
  os << static_cast<uint8_t>(BIND_OPCODE_DONE);
661}

663void BindingSection::writeTo(uint8_t *buf) const {
memcpy(buf, contents.data(), contents.size());
665}

667WeakBindingSection::WeakBindingSection()
  : LinkEditSection(segment_names::linkEdit, section_names::weakBinding) {}

670void WeakBindingSection::finalizeContents() {
raw_svector_ostream os{contents};
Binding lastBinding;

for (const Defined *defined : definitions)
  encodeWeakOverride(defined, os);

for (auto &p : sortBindings(bindingsMap)) {
  const Symbol *sym = p.first;
  std::vector<BindingEntry> &bindings = p.second;
  os << static_cast<uint8_t>(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM)
     << sym->getName() << '\0'
     << static_cast<uint8_t>(BIND_OPCODE_SET_TYPE_IMM | BIND_TYPE_POINTER);
  std::vector<BindIR> opcodes;
  for (const BindingEntry &b : bindings)
    encodeBinding(b.target.isec->parent,
                  b.target.isec->getOffset(b.target.offset), b.addend,
                  lastBinding, opcodes);
  if (config->optimize > 1)
    optimizeOpcodes(opcodes);
  for (const auto &op : opcodes)
    flushOpcodes(op, os);
}
if (!bindingsMap.empty() || !definitions.empty())
  os << static_cast<uint8_t>(BIND_OPCODE_DONE);
695}

697void WeakBindingSection::writeTo(uint8_t *buf) const {
memcpy(buf, contents.data(), contents.size());
699}

701StubsSection::StubsSection()
  : SyntheticSection(segment_names::text, section_names::stubs) {
flags = S_SYMBOL_STUBS | S_ATTR_SOME_INSTRUCTIONS | S_ATTR_PURE_INSTRUCTIONS;
// The stubs section comprises machine instructions, which are aligned to
// 4 bytes on the archs we care about.
align = 4;
reserved2 = target->stubSize;
708}

710uint64_t StubsSection::getSize() const {
return entries.size() * target->stubSize;
712}

714void StubsSection::writeTo(uint8_t *buf) const {
size_t off = 0;
for (const Symbol *sym : entries) {
  uint64_t pointerVA =
      config->emitChainedFixups ? sym->getGotVA() : sym->getLazyPtrVA();
  target->writeStub(buf + off, *sym, pointerVA);
  off += target->stubSize;
}
722}

724void StubsSection::finalize() { isFinal = true; }

726static void addBindingsForStub(Symbol *sym) {
assert(!config->emitChainedFixups)(static_cast <bool> (!config->emitChainedFixups) ? void
 (0) : __assert_fail ("!config->emitChainedFixups", "lld/MachO/SyntheticSections.cpp"
, 727, __extension__ __PRETTY_FUNCTION__));
if (auto *dysym = dyn_cast<DylibSymbol>(sym)) {
  if (sym->isWeakDef()) {
    in.binding->addEntry(dysym, in.lazyPointers->isec,
                         sym->stubsIndex * target->wordSize);
    in.weakBinding->addEntry(sym, in.lazyPointers->isec,
                             sym->stubsIndex * target->wordSize);
  } else {
    in.lazyBinding->addEntry(dysym);
  }
} else if (auto *defined = dyn_cast<Defined>(sym)) {
  if (defined->isExternalWeakDef()) {
    in.rebase->addEntry(in.lazyPointers->isec,
                        sym->stubsIndex * target->wordSize);
    in.weakBinding->addEntry(sym, in.lazyPointers->isec,
                             sym->stubsIndex * target->wordSize);
  } else if (defined->interposable) {
    in.lazyBinding->addEntry(sym);
  } else {
    llvm_unreachable("invalid stub target")::llvm::llvm_unreachable_internal("invalid stub target", "lld/MachO/SyntheticSections.cpp"
, 746);
  }
} else {
  llvm_unreachable("invalid stub target symbol type")::llvm::llvm_unreachable_internal("invalid stub target symbol type"
, "lld/MachO/SyntheticSections.cpp", 749);
}
751}

753void StubsSection::addEntry(Symbol *sym) {
bool inserted = entries.insert(sym);
if (inserted) {
  sym->stubsIndex = entries.size() - 1;

  if (config->emitChainedFixups)
    in.got->addEntry(sym);
  else
    addBindingsForStub(sym);
}
763}

765StubHelperSection::StubHelperSection()
  : SyntheticSection(segment_names::text, section_names::stubHelper) {
flags = S_ATTR_SOME_INSTRUCTIONS | S_ATTR_PURE_INSTRUCTIONS;
align = 4; // This section comprises machine instructions
769}

771uint64_t StubHelperSection::getSize() const {
return target->stubHelperHeaderSize +
       in.lazyBinding->getEntries().size() * target->stubHelperEntrySize;
774}

776bool StubHelperSection::isNeeded() const { return in.lazyBinding->isNeeded(); }

778void StubHelperSection::writeTo(uint8_t *buf) const {
target->writeStubHelperHeader(buf);
size_t off = target->stubHelperHeaderSize;
for (const Symbol *sym : in.lazyBinding->getEntries()) {
  target->writeStubHelperEntry(buf + off, *sym, addr + off);
  off += target->stubHelperEntrySize;
}
785}

787void StubHelperSection::setUp() {
Symbol *binder = symtab->addUndefined("dyld_stub_binder", /*file=*/nullptr,
                                      /*isWeakRef=*/false);
if (auto *undefined = dyn_cast<Undefined>(binder))
  treatUndefinedSymbol(*undefined,
                       "lazy binding (normally in libSystem.dylib)");

// treatUndefinedSymbol() can replace binder with a DylibSymbol; re-check.
stubBinder = dyn_cast_or_null<DylibSymbol>(binder);
if (stubBinder == nullptr)
  return;

in.got->addEntry(stubBinder);

in.imageLoaderCache->parent =
    ConcatOutputSection::getOrCreateForInput(in.imageLoaderCache);
inputSections.push_back(in.imageLoaderCache);
// Since this isn't in the symbol table or in any input file, the noDeadStrip
// argument doesn't matter.
dyldPrivate =
    make<Defined>("__dyld_private", nullptr, in.imageLoaderCache, 0, 0,
                  /*isWeakDef=*/false,
                  /*isExternal=*/false, /*isPrivateExtern=*/false,
                  /*includeInSymtab=*/true,
                  /*isThumb=*/false, /*isReferencedDynamically=*/false,
                  /*noDeadStrip=*/false);
dyldPrivate->used = true;
814}

816ObjCStubsSection::ObjCStubsSection()
  : SyntheticSection(segment_names::text, section_names::objcStubs) {
flags = S_ATTR_SOME_INSTRUCTIONS | S_ATTR_PURE_INSTRUCTIONS;
align = target->objcStubsAlignment;
820}

822void ObjCStubsSection::addEntry(Symbol *sym) {
assert(sym->getName().startswith(symbolPrefix) && "not an objc stub")(static_cast <bool> (sym->getName().startswith(symbolPrefix
) && "not an objc stub") ? void (0) : __assert_fail (
"sym->getName().startswith(symbolPrefix) && \"not an objc stub\""
, "lld/MachO/SyntheticSections.cpp", 823, __extension__ __PRETTY_FUNCTION__
));
StringRef methname = sym->getName().drop_front(symbolPrefix.size());
offsets.push_back(
    in.objcMethnameSection->getStringOffset(methname).outSecOff);
Defined *newSym = replaceSymbol<Defined>(
    sym, sym->getName(), nullptr, isec,
    /*value=*/symbols.size() * target->objcStubsFastSize,
    /*size=*/target->objcStubsFastSize,
    /*isWeakDef=*/false, /*isExternal=*/true, /*isPrivateExtern=*/true,
    /*includeInSymtab=*/true, /*isThumb=*/false,
    /*isReferencedDynamically=*/false, /*noDeadStrip=*/false);
symbols.push_back(newSym);
835}

837void ObjCStubsSection::setUp() {
Symbol *objcMsgSend = symtab->addUndefined("_objc_msgSend", /*file=*/nullptr,
                                           /*isWeakRef=*/false);
objcMsgSend->used = true;
in.got->addEntry(objcMsgSend);
assert(objcMsgSend->isInGot())(static_cast <bool> (objcMsgSend->isInGot()) ? void (
0) : __assert_fail ("objcMsgSend->isInGot()", "lld/MachO/SyntheticSections.cpp"
, 842, __extension__ __PRETTY_FUNCTION__));
objcMsgSendGotIndex = objcMsgSend->gotIndex;

size_t size = offsets.size() * target->wordSize;
uint8_t *selrefsData = bAlloc().Allocate<uint8_t>(size);
for (size_t i = 0, n = offsets.size(); i < n; ++i)
  write64le(&selrefsData[i * target->wordSize], offsets[i]);

in.objcSelrefs =
    makeSyntheticInputSection(segment_names::data, section_names::objcSelrefs,
                              S_LITERAL_POINTERS | S_ATTR_NO_DEAD_STRIP,
                              ArrayRef<uint8_t>{selrefsData, size},
                              /*align=*/target->wordSize);
in.objcSelrefs->live = true;

for (size_t i = 0, n = offsets.size(); i < n; ++i) {
  in.objcSelrefs->relocs.push_back(
      {/*type=*/target->unsignedRelocType,
       /*pcrel=*/false, /*length=*/3,
       /*offset=*/static_cast<uint32_t>(i * target->wordSize),
       /*addend=*/offsets[i] * in.objcMethnameSection->align,
       /*referent=*/in.objcMethnameSection->isec});
}

in.objcSelrefs->parent =
    ConcatOutputSection::getOrCreateForInput(in.objcSelrefs);
inputSections.push_back(in.objcSelrefs);
in.objcSelrefs->isFinal = true;
870}

872uint64_t ObjCStubsSection::getSize() const {
return target->objcStubsFastSize * symbols.size();
874}

876void ObjCStubsSection::writeTo(uint8_t *buf) const {
assert(in.objcSelrefs->live)(static_cast <bool> (in.objcSelrefs->live) ? void (0
) : __assert_fail ("in.objcSelrefs->live", "lld/MachO/SyntheticSections.cpp"
, 877, __extension__ __PRETTY_FUNCTION__));
assert(in.objcSelrefs->isFinal)(static_cast <bool> (in.objcSelrefs->isFinal) ? void
 (0) : __assert_fail ("in.objcSelrefs->isFinal", "lld/MachO/SyntheticSections.cpp"
, 878, __extension__ __PRETTY_FUNCTION__));

uint64_t stubOffset = 0;
for (size_t i = 0, n = symbols.size(); i < n; ++i) {
  Defined *sym = symbols[i];
  target->writeObjCMsgSendStub(buf + stubOffset, sym, in.objcStubs->addr,
                               stubOffset, in.objcSelrefs->getVA(), i,
                               in.got->addr, objcMsgSendGotIndex);
  stubOffset += target->objcStubsFastSize;
}
888}

890LazyPointerSection::LazyPointerSection()
  : SyntheticSection(segment_names::data, section_names::lazySymbolPtr) {
align = target->wordSize;
flags = S_LAZY_SYMBOL_POINTERS;
894}

896uint64_t LazyPointerSection::getSize() const {
return in.stubs->getEntries().size() * target->wordSize;
898}

900bool LazyPointerSection::isNeeded() const {
return !in.stubs->getEntries().empty();
902}

904void LazyPointerSection::writeTo(uint8_t *buf) const {
size_t off = 0;
for (const Symbol *sym : in.stubs->getEntries()) {
  if (const auto *dysym = dyn_cast<DylibSymbol>(sym)) {
    if (dysym->hasStubsHelper()) {
      uint64_t stubHelperOffset =
          target->stubHelperHeaderSize +
          dysym->stubsHelperIndex * target->stubHelperEntrySize;
      write64le(buf + off, in.stubHelper->addr + stubHelperOffset);
    }
  } else {
    write64le(buf + off, sym->getVA());
  }
  off += target->wordSize;
}
919}

921LazyBindingSection::LazyBindingSection()
  : LinkEditSection(segment_names::linkEdit, section_names::lazyBinding) {}

924void LazyBindingSection::finalizeContents() {
// TODO: Just precompute output size here instead of writing to a temporary
// buffer
for (Symbol *sym : entries)
  sym->lazyBindOffset = encode(*sym);
929}

931void LazyBindingSection::writeTo(uint8_t *buf) const {
memcpy(buf, contents.data(), contents.size());
933}

935void LazyBindingSection::addEntry(Symbol *sym) {
assert(!config->emitChainedFixups && "Chained fixups always bind eagerly")(static_cast <bool> (!config->emitChainedFixups &&
 "Chained fixups always bind eagerly") ? void (0) : __assert_fail
 ("!config->emitChainedFixups && \"Chained fixups always bind eagerly\""
, "lld/MachO/SyntheticSections.cpp", 936, __extension__ __PRETTY_FUNCTION__
));
if (entries.insert(sym)) {
  sym->stubsHelperIndex = entries.size() - 1;
  in.rebase->addEntry(in.lazyPointers->isec,
                      sym->stubsIndex * target->wordSize);
}
942}

944// Unlike the non-lazy binding section, the bind opcodes in this section aren't
945// interpreted all at once. Rather, dyld will start interpreting opcodes at a
946// given offset, typically only binding a single symbol before it finds a
947// BIND_OPCODE_DONE terminator. As such, unlike in the non-lazy-binding case,
948// we cannot encode just the differences between symbols; we have to emit the
949// complete bind information for each symbol.
950uint32_t LazyBindingSection::encode(const Symbol &sym) {
uint32_t opstreamOffset = contents.size();
OutputSegment *dataSeg = in.lazyPointers->parent;
os << static_cast<uint8_t>(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB |
                           dataSeg->index);
uint64_t offset =
    in.lazyPointers->addr - dataSeg->addr + sym.stubsIndex * target->wordSize;
encodeULEB128(offset, os);
encodeDylibOrdinal(ordinalForSymbol(sym), os);

uint8_t flags = BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM;
if (sym.isWeakRef())
  flags |= BIND_SYMBOL_FLAGS_WEAK_IMPORT;

os << flags << sym.getName() << '\0'
   << static_cast<uint8_t>(BIND_OPCODE_DO_BIND)
   << static_cast<uint8_t>(BIND_OPCODE_DONE);
return opstreamOffset;
968}

970ExportSection::ExportSection()
  : LinkEditSection(segment_names::linkEdit, section_names::export_) {}

973void ExportSection::finalizeContents() {
trieBuilder.setImageBase(in.header->addr);
for (const Symbol *sym : symtab->getSymbols()) {
  if (const auto *defined = dyn_cast<Defined>(sym)) {
    if (defined->privateExtern || !defined->isLive())
      continue;
    trieBuilder.addSymbol(*defined);
    hasWeakSymbol = hasWeakSymbol || sym->isWeakDef();
  }
}
size = trieBuilder.build();
984}

986void ExportSection::writeTo(uint8_t *buf) const { trieBuilder.writeTo(buf); }

988DataInCodeSection::DataInCodeSection()
  : LinkEditSection(segment_names::linkEdit, section_names::dataInCode) {}

991template <class LP>
992static std::vector<MachO::data_in_code_entry> collectDataInCodeEntries() {
std::vector<MachO::data_in_code_entry> dataInCodeEntries;
for (const InputFile *inputFile : inputFiles) {
  if (!isa<ObjFile>(inputFile))
    continue;
  const ObjFile *objFile = cast<ObjFile>(inputFile);
  ArrayRef<MachO::data_in_code_entry> entries = objFile->getDataInCode();
  if (entries.empty())
    continue;

  assert(is_sorted(entries, [](const data_in_code_entry &lhs,(static_cast <bool> (is_sorted(entries, [](const data_in_code_entry
 &lhs, const data_in_code_entry &rhs) { return lhs.offset
 < rhs.offset; })) ? void (0) : __assert_fail ("is_sorted(entries, [](const data_in_code_entry &lhs, const data_in_code_entry &rhs) { return lhs.offset < rhs.offset; })"
, "lld/MachO/SyntheticSections.cpp", 1005, __extension__ __PRETTY_FUNCTION__
))
                               const data_in_code_entry &rhs) {(static_cast <bool> (is_sorted(entries, [](const data_in_code_entry
 &lhs, const data_in_code_entry &rhs) { return lhs.offset
 < rhs.offset; })) ? void (0) : __assert_fail ("is_sorted(entries, [](const data_in_code_entry &lhs, const data_in_code_entry &rhs) { return lhs.offset < rhs.offset; })"
, "lld/MachO/SyntheticSections.cpp", 1005, __extension__ __PRETTY_FUNCTION__
))
    return lhs.offset < rhs.offset;(static_cast <bool> (is_sorted(entries, [](const data_in_code_entry
 &lhs, const data_in_code_entry &rhs) { return lhs.offset
 < rhs.offset; })) ? void (0) : __assert_fail ("is_sorted(entries, [](const data_in_code_entry &lhs, const data_in_code_entry &rhs) { return lhs.offset < rhs.offset; })"
, "lld/MachO/SyntheticSections.cpp", 1005, __extension__ __PRETTY_FUNCTION__
))
  }))(static_cast <bool> (is_sorted(entries, [](const data_in_code_entry
 &lhs, const data_in_code_entry &rhs) { return lhs.offset
 < rhs.offset; })) ? void (0) : __assert_fail ("is_sorted(entries, [](const data_in_code_entry &lhs, const data_in_code_entry &rhs) { return lhs.offset < rhs.offset; })"
, "lld/MachO/SyntheticSections.cpp", 1005, __extension__ __PRETTY_FUNCTION__
));
  // For each code subsection find 'data in code' entries residing in it.
  // Compute the new offset values as
  // <offset within subsection> + <subsection address> - <__TEXT address>.
  for (const Section *section : objFile->sections) {
    for (const Subsection &subsec : section->subsections) {
      const InputSection *isec = subsec.isec;
      if (!isCodeSection(isec))
        continue;
      if (cast<ConcatInputSection>(isec)->shouldOmitFromOutput())
        continue;
      const uint64_t beginAddr = section->addr + subsec.offset;
      auto it = llvm::lower_bound(
          entries, beginAddr,
          [](const MachO::data_in_code_entry &entry, uint64_t addr) {
            return entry.offset < addr;
          });
      const uint64_t endAddr = beginAddr + isec->getSize();
      for (const auto end = entries.end();
           it != end && it->offset + it->length <= endAddr; ++it)
        dataInCodeEntries.push_back(
            {static_cast<uint32_t>(isec->getVA(it->offset - beginAddr) -
                                   in.header->addr),
             it->length, it->kind});
    }
  }
}

// ld64 emits the table in sorted order too.
llvm::sort(dataInCodeEntries,
           [](const data_in_code_entry &lhs, const data_in_code_entry &rhs) {
             return lhs.offset < rhs.offset;
           });
return dataInCodeEntries;
1039}

1041void DataInCodeSection::finalizeContents() {
entries = target->wordSize == 8 ? collectDataInCodeEntries<LP64>()
                                : collectDataInCodeEntries<ILP32>();
1044}

1046void DataInCodeSection::writeTo(uint8_t *buf) const {
if (!entries.empty())
  memcpy(buf, entries.data(), getRawSize());
1049}

1051FunctionStartsSection::FunctionStartsSection()
  : LinkEditSection(segment_names::linkEdit, section_names::functionStarts) {}

1054void FunctionStartsSection::finalizeContents() {
raw_svector_ostream os{contents};
std::vector<uint64_t> addrs;
for (const InputFile *file : inputFiles) {
  if (auto *objFile = dyn_cast<ObjFile>(file)) {
    for (const Symbol *sym : objFile->symbols) {
      if (const auto *defined = dyn_cast_or_null<Defined>(sym)) {
        if (!defined->isec || !isCodeSection(defined->isec) ||
            !defined->isLive())
          continue;
        // TODO: Add support for thumbs, in that case
        // the lowest bit of nextAddr needs to be set to 1.
        addrs.push_back(defined->getVA());
      }
    }
  }
}
llvm::sort(addrs);
uint64_t addr = in.header->addr;
for (uint64_t nextAddr : addrs) {
  uint64_t delta = nextAddr - addr;
  if (delta == 0)
    continue;
  encodeULEB128(delta, os);
  addr = nextAddr;
}
os << '\0';
1081}

1083void FunctionStartsSection::writeTo(uint8_t *buf) const {
memcpy(buf, contents.data(), contents.size());
1085}

1087SymtabSection::SymtabSection(StringTableSection &stringTableSection)
  : LinkEditSection(segment_names::linkEdit, section_names::symbolTable),
    stringTableSection(stringTableSection) {}

1091void SymtabSection::emitBeginSourceStab(StringRef sourceFile) {
StabsEntry stab(N_SO);
stab.strx = stringTableSection.addString(saver().save(sourceFile));
stabs.emplace_back(std::move(stab));
1095}

1097void SymtabSection::emitEndSourceStab() {
StabsEntry stab(N_SO);
stab.sect = 1;
stabs.emplace_back(std::move(stab));
1101}

1103void SymtabSection::emitObjectFileStab(ObjFile *file) {
StabsEntry stab(N_OSO);
stab.sect = target->cpuSubtype;
SmallString<261> path(!file->archiveName.empty() ? file->archiveName
                                                 : file->getName());
std::error_code ec = sys::fs::make_absolute(path);
if (ec)
  fatal("failed to get absolute path for " + path);

if (!file->archiveName.empty())
  path.append({"(", file->getName(), ")"});

StringRef adjustedPath = saver().save(path.str());
adjustedPath.consume_front(config->osoPrefix);

stab.strx = stringTableSection.addString(adjustedPath);
stab.desc = 1;
stab.value = file->modTime;
stabs.emplace_back(std::move(stab));
1122}

1124void SymtabSection::emitEndFunStab(Defined *defined) {
StabsEntry stab(N_FUN);
stab.value = defined->size;
stabs.emplace_back(std::move(stab));
1128}

1130void SymtabSection::emitStabs() {
if (config->omitDebugInfo)
  return;

for (const std::string &s : config->astPaths) {
  StabsEntry astStab(N_AST);
  astStab.strx = stringTableSection.addString(s);
  stabs.emplace_back(std::move(astStab));
}

// Cache the file ID for each symbol in an std::pair for faster sorting.
using SortingPair = std::pair<Defined *, int>;
std::vector<SortingPair> symbolsNeedingStabs;
for (const SymtabEntry &entry :
     concat<SymtabEntry>(localSymbols, externalSymbols)) {
  Symbol *sym = entry.sym;
  assert(sym->isLive() &&(static_cast <bool> (sym->isLive() && "dead symbols should not be in localSymbols, externalSymbols"
) ? void (0) : __assert_fail ("sym->isLive() && \"dead symbols should not be in localSymbols, externalSymbols\""
, "lld/MachO/SyntheticSections.cpp", 1147, __extension__ __PRETTY_FUNCTION__
))
         "dead symbols should not be in localSymbols, externalSymbols")(static_cast <bool> (sym->isLive() && "dead symbols should not be in localSymbols, externalSymbols"
) ? void (0) : __assert_fail ("sym->isLive() && \"dead symbols should not be in localSymbols, externalSymbols\""
, "lld/MachO/SyntheticSections.cpp", 1147, __extension__ __PRETTY_FUNCTION__
));
  if (auto *defined = dyn_cast<Defined>(sym)) {
    // Excluded symbols should have been filtered out in finalizeContents().
    assert(defined->includeInSymtab)(static_cast <bool> (defined->includeInSymtab) ? void
 (0) : __assert_fail ("defined->includeInSymtab", "lld/MachO/SyntheticSections.cpp"
, 1150, __extension__ __PRETTY_FUNCTION__));

    if (defined->isAbsolute())
      continue;

    // Constant-folded symbols go in the executable's symbol table, but don't
    // get a stabs entry.
    if (defined->wasIdenticalCodeFolded)
      continue;

    ObjFile *file = defined->getObjectFile();
    if (!file || !file->compileUnit)
      continue;

    symbolsNeedingStabs.emplace_back(defined, defined->isec->getFile()->id);
  }
}

llvm::stable_sort(symbolsNeedingStabs,
                  [&](const SortingPair &a, const SortingPair &b) {
                    return a.second < b.second;
                  });

// Emit STABS symbols so that dsymutil and/or the debugger can map address
// regions in the final binary to the source and object files from which they
// originated.
InputFile *lastFile = nullptr;
for (SortingPair &pair : symbolsNeedingStabs) {
  Defined *defined = pair.first;
  InputSection *isec = defined->isec;
  ObjFile *file = cast<ObjFile>(isec->getFile());

  if (lastFile == nullptr || lastFile != file) {
    if (lastFile != nullptr)
      emitEndSourceStab();
    lastFile = file;

    emitBeginSourceStab(file->sourceFile());
    emitObjectFileStab(file);
  }

  StabsEntry symStab;
  symStab.sect = defined->isec->parent->index;
  symStab.strx = stringTableSection.addString(defined->getName());
  symStab.value = defined->getVA();

  if (isCodeSection(isec)) {
    symStab.type = N_FUN;
    stabs.emplace_back(std::move(symStab));
    emitEndFunStab(defined);
  } else {
    symStab.type = defined->isExternal() ? N_GSYM : N_STSYM;
    stabs.emplace_back(std::move(symStab));
  }
}

if (!stabs.empty())
  emitEndSourceStab();
1208}

1210void SymtabSection::finalizeContents() {
auto addSymbol = [&](std::vector<SymtabEntry> &symbols, Symbol *sym) {
  uint32_t strx = stringTableSection.addString(sym->getName());
  symbols.push_back({sym, strx});
};

std::function<void(Symbol *)> localSymbolsHandler;
switch (config->localSymbolsPresence) {
case SymtabPresence::All:
  localSymbolsHandler = [&](Symbol *sym) { addSymbol(localSymbols, sym); };
  break;
case SymtabPresence::None:
  localSymbolsHandler = [&](Symbol *) { /* Do nothing*/ };
  break;
case SymtabPresence::SelectivelyIncluded:
  localSymbolsHandler = [&](Symbol *sym) {
    if (config->localSymbolPatterns.match(sym->getName()))
      addSymbol(localSymbols, sym);
  };
  break;
case SymtabPresence::SelectivelyExcluded:
  localSymbolsHandler = [&](Symbol *sym) {
    if (!config->localSymbolPatterns.match(sym->getName()))
      addSymbol(localSymbols, sym);
  };
  break;
}

// Local symbols aren't in the SymbolTable, so we walk the list of object
// files to gather them.
// But if `-x` is set, then we don't need to. localSymbolsHandler() will do
// the right thing regardless, but this check is a perf optimization because
// iterating through all the input files and their symbols is expensive.
if (config->localSymbolsPresence != SymtabPresence::None) {
  for (const InputFile *file : inputFiles) {
    if (auto *objFile = dyn_cast<ObjFile>(file)) {
      for (Symbol *sym : objFile->symbols) {
        if (auto *defined = dyn_cast_or_null<Defined>(sym)) {
          if (defined->isExternal() || !defined->isLive() ||
              !defined->includeInSymtab)
            continue;
          localSymbolsHandler(sym);
        }
      }
    }
  }
}

// __dyld_private is a local symbol too. It's linker-created and doesn't
// exist in any object file.
if (in.stubHelper && in.stubHelper->dyldPrivate)
  localSymbolsHandler(in.stubHelper->dyldPrivate);

for (Symbol *sym : symtab->getSymbols()) {
  if (!sym->isLive())
    continue;
  if (auto *defined = dyn_cast<Defined>(sym)) {
    if (!defined->includeInSymtab)
      continue;
    assert(defined->isExternal())(static_cast <bool> (defined->isExternal()) ? void (
0) : __assert_fail ("defined->isExternal()", "lld/MachO/SyntheticSections.cpp"
, 1269, __extension__ __PRETTY_FUNCTION__));
    if (defined->privateExtern)
      localSymbolsHandler(defined);
    else
      addSymbol(externalSymbols, defined);
  } else if (auto *dysym = dyn_cast<DylibSymbol>(sym)) {
    if (dysym->isReferenced())
      addSymbol(undefinedSymbols, sym);
  }
}

emitStabs();
uint32_t symtabIndex = stabs.size();
for (const SymtabEntry &entry :
     concat<SymtabEntry>(localSymbols, externalSymbols, undefinedSymbols)) {
  entry.sym->symtabIndex = symtabIndex++;
}
1286}

1288uint32_t SymtabSection::getNumSymbols() const {
return stabs.size() + localSymbols.size() + externalSymbols.size() +
       undefinedSymbols.size();
1291}

1293// This serves to hide (type-erase) the template parameter from SymtabSection.
1294template <class LP> class SymtabSectionImpl final : public SymtabSection {
1295public:
SymtabSectionImpl(StringTableSection &stringTableSection)
    : SymtabSection(stringTableSection) {}
uint64_t getRawSize() const override;
void writeTo(uint8_t *buf) const override;
1300};

1302template <class LP> uint64_t SymtabSectionImpl<LP>::getRawSize() const {
return getNumSymbols() * sizeof(typename LP::nlist);
1304}

1306template <class LP> void SymtabSectionImpl<LP>::writeTo(uint8_t *buf) const {
auto *nList = reinterpret_cast<typename LP::nlist *>(buf);
// Emit the stabs entries before the "real" symbols. We cannot emit them
// after as that would render Symbol::symtabIndex inaccurate.
for (const StabsEntry &entry : stabs) {
  nList->n_strx = entry.strx;
  nList->n_type = entry.type;
  nList->n_sect = entry.sect;
  nList->n_desc = entry.desc;
  nList->n_value = entry.value;
  ++nList;
}

for (const SymtabEntry &entry : concat<const SymtabEntry>(
         localSymbols, externalSymbols, undefinedSymbols)) {
  nList->n_strx = entry.strx;
  // TODO populate n_desc with more flags
  if (auto *defined = dyn_cast<Defined>(entry.sym)) {
    uint8_t scope = 0;
    if (defined->privateExtern) {
      // Private external -- dylib scoped symbol.
      // Promote to non-external at link time.
      scope = N_PEXT;
    } else if (defined->isExternal()) {
      // Normal global symbol.
      scope = N_EXT;
    } else {
      // TU-local symbol from localSymbols.
      scope = 0;
    }

    if (defined->isAbsolute()) {
      nList->n_type = scope | N_ABS;
      nList->n_sect = NO_SECT;
      nList->n_value = defined->value;
    } else {
      nList->n_type = scope | N_SECT;
      nList->n_sect = defined->isec->parent->index;
      // For the N_SECT symbol type, n_value is the address of the symbol
      nList->n_value = defined->getVA();
    }
    nList->n_desc |= defined->thumb ? N_ARM_THUMB_DEF : 0;
    nList->n_desc |= defined->isExternalWeakDef() ? N_WEAK_DEF : 0;
    nList->n_desc |=
        defined->referencedDynamically ? REFERENCED_DYNAMICALLY : 0;
  } else if (auto *dysym = dyn_cast<DylibSymbol>(entry.sym)) {
    uint16_t n_desc = nList->n_desc;
    int16_t ordinal = ordinalForDylibSymbol(*dysym);
    if (ordinal == BIND_SPECIAL_DYLIB_FLAT_LOOKUP)
      SET_LIBRARY_ORDINAL(n_desc, DYNAMIC_LOOKUP_ORDINAL);
    else if (ordinal == BIND_SPECIAL_DYLIB_MAIN_EXECUTABLE)
      SET_LIBRARY_ORDINAL(n_desc, EXECUTABLE_ORDINAL);
    else {
      assert(ordinal > 0)(static_cast <bool> (ordinal > 0) ? void (0) : __assert_fail
 ("ordinal > 0", "lld/MachO/SyntheticSections.cpp", 1359, __extension__
 __PRETTY_FUNCTION__));
      SET_LIBRARY_ORDINAL(n_desc, static_cast<uint8_t>(ordinal));
    }

    nList->n_type = N_EXT;
    n_desc |= dysym->isWeakDef() ? N_WEAK_DEF : 0;
    n_desc |= dysym->isWeakRef() ? N_WEAK_REF : 0;
    nList->n_desc = n_desc;
  }
  ++nList;
}
1370}

1372template <class LP>
1373SymtabSection *
1374macho::makeSymtabSection(StringTableSection &stringTableSection) {
return make<SymtabSectionImpl<LP>>(stringTableSection);
1376}

1378IndirectSymtabSection::IndirectSymtabSection()
  : LinkEditSection(segment_names::linkEdit,
                    section_names::indirectSymbolTable) {}

1382uint32_t IndirectSymtabSection::getNumSymbols() const {
uint32_t size = in.got->getEntries().size() +
                in.tlvPointers->getEntries().size() +
                in.stubs->getEntries().size();
if (!config->emitChainedFixups)
  size += in.stubs->getEntries().size();
return size;
1389}

1391bool IndirectSymtabSection::isNeeded() const {
return in.got->isNeeded() || in.tlvPointers->isNeeded() ||
       in.stubs->isNeeded();
1394}

1396void IndirectSymtabSection::finalizeContents() {
uint32_t off = 0;
in.got->reserved1 = off;
off += in.got->getEntries().size();
in.tlvPointers->reserved1 = off;
off += in.tlvPointers->getEntries().size();
in.stubs->reserved1 = off;
if (in.lazyPointers) {
  off += in.stubs->getEntries().size();
  in.lazyPointers->reserved1 = off;
}
1407}

1409static uint32_t indirectValue(const Symbol *sym) {
if (sym->symtabIndex == UINT32_MAX(4294967295U))
  return INDIRECT_SYMBOL_LOCAL;
if (auto *defined = dyn_cast<Defined>(sym))
  if (defined->privateExtern)
    return INDIRECT_SYMBOL_LOCAL;
return sym->symtabIndex;
1416}

1418void IndirectSymtabSection::writeTo(uint8_t *buf) const {
uint32_t off = 0;
for (const Symbol *sym : in.got->getEntries()) {
  write32le(buf + off * sizeof(uint32_t), indirectValue(sym));
  ++off;
}
for (const Symbol *sym : in.tlvPointers->getEntries()) {
  write32le(buf + off * sizeof(uint32_t), indirectValue(sym));
  ++off;
}
for (const Symbol *sym : in.stubs->getEntries()) {
  write32le(buf + off * sizeof(uint32_t), indirectValue(sym));
  ++off;
}

if (in.lazyPointers) {
  // There is a 1:1 correspondence between stubs and LazyPointerSection
  // entries. But giving __stubs and __la_symbol_ptr the same reserved1
  // (the offset into the indirect symbol table) so that they both refer
  // to the same range of offsets confuses `strip`, so write the stubs
  // symbol table offsets a second time.
  for (const Symbol *sym : in.stubs->getEntries()) {
    write32le(buf + off * sizeof(uint32_t), indirectValue(sym));
    ++off;
  }
}
1444}

1446StringTableSection::StringTableSection()
  : LinkEditSection(segment_names::linkEdit, section_names::stringTable) {}

1449uint32_t StringTableSection::addString(StringRef str) {
uint32_t strx = size;
strings.push_back(str); // TODO: consider deduplicating strings
size += str.size() + 1; // account for null terminator
return strx;
1454}

1456void StringTableSection::writeTo(uint8_t *buf) const {
uint32_t off = 0;
for (StringRef str : strings) {
  memcpy(buf + off, str.data(), str.size());
  off += str.size() + 1; // account for null terminator
}
1462}

1464static_assert((CodeSignatureSection::blobHeadersSize % 8) == 0);
1465static_assert((CodeSignatureSection::fixedHeadersSize % 8) == 0);

1467CodeSignatureSection::CodeSignatureSection()
  : LinkEditSection(segment_names::linkEdit, section_names::codeSignature) {
align = 16; // required by libstuff
// FIXME: Consider using finalOutput instead of outputFile.
fileName = config->outputFile;
size_t slashIndex = fileName.rfind("/");
if (slashIndex != std::string::npos)
  fileName = fileName.drop_front(slashIndex + 1);

// NOTE: Any changes to these calculations should be repeated
// in llvm-objcopy's MachOLayoutBuilder::layoutTail.
allHeadersSize = alignTo<16>(fixedHeadersSize + fileName.size() + 1);
fileNamePad = allHeadersSize - fixedHeadersSize - fileName.size();
1480}

1482uint32_t CodeSignatureSection::getBlockCount() const {
return (fileOff + blockSize - 1) / blockSize;
1484}

1486uint64_t CodeSignatureSection::getRawSize() const {
return allHeadersSize + getBlockCount() * hashSize;
1488}

1490void CodeSignatureSection::writeHashes(uint8_t *buf) const {
// NOTE: Changes to this functionality should be repeated in llvm-objcopy's
// MachOWriter::writeSignatureData.
uint8_t *hashes = buf + fileOff + allHeadersSize;
parallelFor(0, getBlockCount(), [&](size_t i) {
  sha256(buf + i * blockSize,
         std::min(static_cast<size_t>(fileOff - i * blockSize), blockSize),
         hashes + i * hashSize);
});
1499#if defined(__APPLE__)
// This is macOS-specific work-around and makes no sense for any
// other host OS. See https://openradar.appspot.com/FB8914231
//
// The macOS kernel maintains a signature-verification cache to
// quickly validate applications at time of execve(2).  The trouble
// is that for the kernel creates the cache entry at the time of the
// mmap(2) call, before we have a chance to write either the code to
// sign or the signature header+hashes.  The fix is to invalidate
// all cached data associated with the output file, thus discarding
// the bogus prematurely-cached signature.
msync(buf, fileOff + getSize(), MS_INVALIDATE);
1511#endif
1512}

1514void CodeSignatureSection::writeTo(uint8_t *buf) const {
// NOTE: Changes to this functionality should be repeated in llvm-objcopy's
// MachOWriter::writeSignatureData.
uint32_t signatureSize = static_cast<uint32_t>(getSize());
auto *superBlob = reinterpret_cast<CS_SuperBlob *>(buf);
write32be(&superBlob->magic, CSMAGIC_EMBEDDED_SIGNATURE);
write32be(&superBlob->length, signatureSize);
write32be(&superBlob->count, 1);
auto *blobIndex = reinterpret_cast<CS_BlobIndex *>(&superBlob[1]);
write32be(&blobIndex->type, CSSLOT_CODEDIRECTORY);
write32be(&blobIndex->offset, blobHeadersSize);
auto *codeDirectory =
    reinterpret_cast<CS_CodeDirectory *>(buf + blobHeadersSize);
write32be(&codeDirectory->magic, CSMAGIC_CODEDIRECTORY);
write32be(&codeDirectory->length, signatureSize - blobHeadersSize);
write32be(&codeDirectory->version, CS_SUPPORTSEXECSEG);
write32be(&codeDirectory->flags, CS_ADHOC | CS_LINKER_SIGNED);
write32be(&codeDirectory->hashOffset,
          sizeof(CS_CodeDirectory) + fileName.size() + fileNamePad);
write32be(&codeDirectory->identOffset, sizeof(CS_CodeDirectory));
codeDirectory->nSpecialSlots = 0;
write32be(&codeDirectory->nCodeSlots, getBlockCount());
write32be(&codeDirectory->codeLimit, fileOff);
codeDirectory->hashSize = static_cast<uint8_t>(hashSize);
codeDirectory->hashType = kSecCodeSignatureHashSHA256;
codeDirectory->platform = 0;
codeDirectory->pageSize = blockSizeShift;
codeDirectory->spare2 = 0;
codeDirectory->scatterOffset = 0;
codeDirectory->teamOffset = 0;
codeDirectory->spare3 = 0;
codeDirectory->codeLimit64 = 0;
OutputSegment *textSeg = getOrCreateOutputSegment(segment_names::text);
write64be(&codeDirectory->execSegBase, textSeg->fileOff);
write64be(&codeDirectory->execSegLimit, textSeg->fileSize);
write64be(&codeDirectory->execSegFlags,
          config->outputType == MH_EXECUTE ? CS_EXECSEG_MAIN_BINARY : 0);
auto *id = reinterpret_cast<char *>(&codeDirectory[1]);
memcpy(id, fileName.begin(), fileName.size());
memset(id + fileName.size(), 0, fileNamePad);
1554}

1556BitcodeBundleSection::BitcodeBundleSection()
  : SyntheticSection(segment_names::llvm, section_names::bitcodeBundle) {}

1559class ErrorCodeWrapper {
1560public:
explicit ErrorCodeWrapper(std::error_code ec) : errorCode(ec.value()) {}
explicit ErrorCodeWrapper(int ec) : errorCode(ec) {}
operator int() const { return errorCode; }

1565private:
int errorCode;
1567};

1569#define CHECK_EC(exp)do { ErrorCodeWrapper ec(exp); if (ec) fatal(Twine("operation failed with error code "
) + Twine(ec) + ": " + "exp"); } while (0);                                                          \
do {                                                                         \
  ErrorCodeWrapper ec(exp);                                                  \
  if (ec)                                                                    \
    fatal(Twine("operation failed with error code ") + Twine(ec) + ": " +    \
          #exp);                                                             \
} while (0);

1577void BitcodeBundleSection::finalize() {
1578#ifdef LLVM_HAVE_LIBXAR
using namespace llvm::sys::fs;
CHECK_EC(createTemporaryFile("bitcode-bundle", "xar", xarPath))do { ErrorCodeWrapper ec(createTemporaryFile("bitcode-bundle"
, "xar", xarPath)); if (ec) fatal(Twine("operation failed with error code "
) + Twine(ec) + ": " + "createTemporaryFile(\"bitcode-bundle\", \"xar\", xarPath)"
); } while (0);;

1582#pragma clang diagnostic push
1583#pragma clang diagnostic ignored "-Wdeprecated-declarations"
xar_t xar(xar_open(xarPath.data(), O_RDWR));
1585#pragma clang diagnostic pop
if (!xar)
  fatal("failed to open XAR temporary file at " + xarPath);
CHECK_EC(xar_opt_set(xar, XAR_OPT_COMPRESSION, XAR_OPT_VAL_NONE))do { ErrorCodeWrapper ec(xar_opt_set(xar, XAR_OPT_COMPRESSION
, XAR_OPT_VAL_NONE)); if (ec) fatal(Twine("operation failed with error code "
) + Twine(ec) + ": " + "xar_opt_set(xar, XAR_OPT_COMPRESSION, XAR_OPT_VAL_NONE)"
); } while (0);;
// FIXME: add more data to XAR
CHECK_EC(xar_close(xar))do { ErrorCodeWrapper ec(xar_close(xar)); if (ec) fatal(Twine
("operation failed with error code ") + Twine(ec) + ": " + "xar_close(xar)"
); } while (0);;

file_size(xarPath, xarSize);
1593#endif // defined(LLVM_HAVE_LIBXAR)
1594}

1596void BitcodeBundleSection::writeTo(uint8_t *buf) const {
using namespace llvm::sys::fs;
file_t handle =
    CHECK(openNativeFile(xarPath, CD_OpenExisting, FA_Read, OF_None),check2((openNativeFile(xarPath, CD_OpenExisting, FA_Read, OF_None
)), [&] { return toString("failed to open XAR file"); })
          "failed to open XAR file")check2((openNativeFile(xarPath, CD_OpenExisting, FA_Read, OF_None
)), [&] { return toString("failed to open XAR file"); });
std::error_code ec;
mapped_file_region xarMap(handle, mapped_file_region::mapmode::readonly,
                          xarSize, 0, ec);
if (ec)
  fatal("failed to map XAR file");
memcpy(buf, xarMap.const_data(), xarSize);

closeFile(handle);
remove(xarPath);
1610}

1612CStringSection::CStringSection(const char *name)
  : SyntheticSection(segment_names::text, name) {
flags = S_CSTRING_LITERALS;
1615}

1617void CStringSection::addInput(CStringInputSection *isec) {
isec->parent = this;
inputs.push_back(isec);
if (isec->align > align)
  align = isec->align;
1622}

1624void CStringSection::writeTo(uint8_t *buf) const {
for (const CStringInputSection *isec : inputs) {
  for (const auto &[i, piece] : llvm::enumerate(isec->pieces)) {
    if (!piece.live)
      continue;
    StringRef string = isec->getStringRef(i);
    memcpy(buf + piece.outSecOff, string.data(), string.size());
  }
}
1633}

1635void CStringSection::finalizeContents() {
uint64_t offset = 0;
for (CStringInputSection *isec : inputs) {
  for (const auto &[i, piece] : llvm::enumerate(isec->pieces)) {
    if (!piece.live)
1
Assuming field 'live' is not equal to 0→
2
←
Taking false branch→
      continue;
    // See comment above DeduplicatedCStringSection for how alignment is
    // handled.
    uint32_t pieceAlign = 1
                          << countTrailingZeros(isec->align | piece.inSecOff);
3
←
Calling 'countTrailingZeros<unsigned int>'→
13
←
Returning from 'countTrailingZeros<unsigned int>'→
14
←
The result of the left shift is undefined due to shifting by '32', which is greater or equal to the width of type 'int'
    offset = alignTo(offset, pieceAlign);
    piece.outSecOff = offset;
    isec->isFinal = true;
    StringRef string = isec->getStringRef(i);
    offset += string.size() + 1; // account for null terminator
  }
}
size = offset;
1653}

1655// Mergeable cstring literals are found under the __TEXT,__cstring section. In
1656// contrast to ELF, which puts strings that need different alignments into
1657// different sections, clang's Mach-O backend puts them all in one section.
1658// Strings that need to be aligned have the .p2align directive emitted before
1659// them, which simply translates into zero padding in the object file. In other
1660// words, we have to infer the desired alignment of these cstrings from their
1661// addresses.
1662//
1663// We differ slightly from ld64 in how we've chosen to align these cstrings.
1664// Both LLD and ld64 preserve the number of trailing zeros in each cstring's
1665// address in the input object files. When deduplicating identical cstrings,
1666// both linkers pick the cstring whose address has more trailing zeros, and
1667// preserve the alignment of that address in the final binary. However, ld64
1668// goes a step further and also preserves the offset of the cstring from the
1669// last section-aligned address.  I.e. if a cstring is at offset 18 in the
1670// input, with a section alignment of 16, then both LLD and ld64 will ensure the
1671// final address is 2-byte aligned (since 18 == 16 + 2). But ld64 will also
1672// ensure that the final address is of the form 16 * k + 2 for some k.
1673//
1674// Note that ld64's heuristic means that a dedup'ed cstring's final address is
1675// dependent on the order of the input object files. E.g. if in addition to the
1676// cstring at offset 18 above, we have a duplicate one in another file with a
1677// `.cstring` section alignment of 2 and an offset of zero, then ld64 will pick
1678// the cstring from the object file earlier on the command line (since both have
1679// the same number of trailing zeros in their address). So the final cstring may
1680// either be at some address `16 * k + 2` or at some address `2 * k`.
1681//
1682// I've opted not to follow this behavior primarily for implementation
1683// simplicity, and secondarily to save a few more bytes. It's not clear to me
1684// that preserving the section alignment + offset is ever necessary, and there
1685// are many cases that are clearly redundant. In particular, if an x86_64 object
1686// file contains some strings that are accessed via SIMD instructions, then the
1687// .cstring section in the object file will be 16-byte-aligned (since SIMD
1688// requires its operand addresses to be 16-byte aligned). However, there will
1689// typically also be other cstrings in the same file that aren't used via SIMD
1690// and don't need this alignment. They will be emitted at some arbitrary address
1691// `A`, but ld64 will treat them as being 16-byte aligned with an offset of `16
1692// % A`.
1693void DeduplicatedCStringSection::finalizeContents() {
// Find the largest alignment required for each string.
for (const CStringInputSection *isec : inputs) {
  for (const auto &[i, piece] : llvm::enumerate(isec->pieces)) {
    if (!piece.live)
      continue;
    auto s = isec->getCachedHashStringRef(i);
    assert(isec->align != 0)(static_cast <bool> (isec->align != 0) ? void (0) : __assert_fail
 ("isec->align != 0", "lld/MachO/SyntheticSections.cpp", 1700
, __extension__ __PRETTY_FUNCTION__));
    uint8_t trailingZeros = countTrailingZeros(isec->align | piece.inSecOff);
    auto it = stringOffsetMap.insert(
        std::make_pair(s, StringOffset(trailingZeros)));
    if (!it.second && it.first->second.trailingZeros < trailingZeros)
      it.first->second.trailingZeros = trailingZeros;
  }
}

// Assign an offset for each string and save it to the corresponding
// StringPieces for easy access.
for (CStringInputSection *isec : inputs) {
  for (const auto &[i, piece] : llvm::enumerate(isec->pieces)) {
    if (!piece.live)
      continue;
    auto s = isec->getCachedHashStringRef(i);
    auto it = stringOffsetMap.find(s);
    assert(it != stringOffsetMap.end())(static_cast <bool> (it != stringOffsetMap.end()) ? void
 (0) : __assert_fail ("it != stringOffsetMap.end()", "lld/MachO/SyntheticSections.cpp"
, 1717, __extension__ __PRETTY_FUNCTION__));
    StringOffset &offsetInfo = it->second;
    if (offsetInfo.outSecOff == UINT64_MAX(18446744073709551615UL)) {
      offsetInfo.outSecOff = alignTo(size, 1ULL << offsetInfo.trailingZeros);
      size =
          offsetInfo.outSecOff + s.size() + 1; // account for null terminator
    }
    piece.outSecOff = offsetInfo.outSecOff;
  }
  isec->isFinal = true;
}
1728}

1730void DeduplicatedCStringSection::writeTo(uint8_t *buf) const {
for (const auto &p : stringOffsetMap) {
  StringRef data = p.first.val();
  uint64_t off = p.second.outSecOff;
  if (!data.empty())
    memcpy(buf + off, data.data(), data.size());
}
1737}

1739DeduplicatedCStringSection::StringOffset
1740DeduplicatedCStringSection::getStringOffset(StringRef str) const {
// StringPiece uses 31 bits to store the hashes, so we replicate that
uint32_t hash = xxHash64(str) & 0x7fffffff;
auto offset = stringOffsetMap.find(CachedHashStringRef(str, hash));
assert(offset != stringOffsetMap.end() &&(static_cast <bool> (offset != stringOffsetMap.end() &&
 "Looked-up strings should always exist in section") ? void (
0) : __assert_fail ("offset != stringOffsetMap.end() && \"Looked-up strings should always exist in section\""
, "lld/MachO/SyntheticSections.cpp", 1745, __extension__ __PRETTY_FUNCTION__
))
       "Looked-up strings should always exist in section")(static_cast <bool> (offset != stringOffsetMap.end() &&
 "Looked-up strings should always exist in section") ? void (
0) : __assert_fail ("offset != stringOffsetMap.end() && \"Looked-up strings should always exist in section\""
, "lld/MachO/SyntheticSections.cpp", 1745, __extension__ __PRETTY_FUNCTION__
));
return offset->second;
1747}

1749// This section is actually emitted as __TEXT,__const by ld64, but clang may
1750// emit input sections of that name, and LLD doesn't currently support mixing
1751// synthetic and concat-type OutputSections. To work around this, I've given
1752// our merged-literals section a different name.
1753WordLiteralSection::WordLiteralSection()
  : SyntheticSection(segment_names::text, section_names::literals) {
align = 16;
1756}

1758void WordLiteralSection::addInput(WordLiteralInputSection *isec) {
isec->parent = this;
inputs.push_back(isec);
1761}

1763void WordLiteralSection::finalizeContents() {
for (WordLiteralInputSection *isec : inputs) {
  // We do all processing of the InputSection here, so it will be effectively
  // finalized.
  isec->isFinal = true;
  const uint8_t *buf = isec->data.data();
  switch (sectionType(isec->getFlags())) {
  case S_4BYTE_LITERALS: {
    for (size_t off = 0, e = isec->data.size(); off < e; off += 4) {
      if (!isec->isLive(off))
        continue;
      uint32_t value = *reinterpret_cast<const uint32_t *>(buf + off);
      literal4Map.emplace(value, literal4Map.size());
    }
    break;
  }
  case S_8BYTE_LITERALS: {
    for (size_t off = 0, e = isec->data.size(); off < e; off += 8) {
      if (!isec->isLive(off))
        continue;
      uint64_t value = *reinterpret_cast<const uint64_t *>(buf + off);
      literal8Map.emplace(value, literal8Map.size());
    }
    break;
  }
  case S_16BYTE_LITERALS: {
    for (size_t off = 0, e = isec->data.size(); off < e; off += 16) {
      if (!isec->isLive(off))
        continue;
      UInt128 value = *reinterpret_cast<const UInt128 *>(buf + off);
      literal16Map.emplace(value, literal16Map.size());
    }
    break;
  }
  default:
    llvm_unreachable("invalid literal section type")::llvm::llvm_unreachable_internal("invalid literal section type"
, "lld/MachO/SyntheticSections.cpp", 1798);
  }
}
1801}

1803void WordLiteralSection::writeTo(uint8_t *buf) const {
// Note that we don't attempt to do any endianness conversion in addInput(),
// so we don't do it here either -- just write out the original value,
// byte-for-byte.
for (const auto &p : literal16Map)
  memcpy(buf + p.second * 16, &p.first, 16);
buf += literal16Map.size() * 16;

for (const auto &p : literal8Map)
  memcpy(buf + p.second * 8, &p.first, 8);
buf += literal8Map.size() * 8;

for (const auto &p : literal4Map)
  memcpy(buf + p.second * 4, &p.first, 4);
1817}

1819ObjCImageInfoSection::ObjCImageInfoSection()
  : SyntheticSection(segment_names::data, section_names::objCImageInfo) {}

1822ObjCImageInfoSection::ImageInfo
1823ObjCImageInfoSection::parseImageInfo(const InputFile *file) {
ImageInfo info;
ArrayRef<uint8_t> data = file->objCImageInfo;
// The image info struct has the following layout:
// struct {
//   uint32_t version;
//   uint32_t flags;
// };
if (data.size() < 8) {
  warn(toString(file) + ": invalid __objc_imageinfo size");
  return info;
}

auto *buf = reinterpret_cast<const uint32_t *>(data.data());
if (read32le(buf) != 0) {
  warn(toString(file) + ": invalid __objc_imageinfo version");
  return info;
}

uint32_t flags = read32le(buf + 1);
info.swiftVersion = (flags >> 8) & 0xff;
info.hasCategoryClassProperties = flags & 0x40;
return info;
1846}

1848static std::string swiftVersionString(uint8_t version) {
switch (version) {
  case 1:
    return "1.0";
  case 2:
    return "1.1";
  case 3:
    return "2.0";
  case 4:
    return "3.0";
  case 5:
    return "4.0";
  default:
    return ("0x" + Twine::utohexstr(version)).str();
}
1863}

1865// Validate each object file's __objc_imageinfo and use them to generate the
1866// image info for the output binary. Only two pieces of info are relevant:
1867// 1. The Swift version (should be identical across inputs)
1868// 2. `bool hasCategoryClassProperties` (true only if true for all inputs)
1869void ObjCImageInfoSection::finalizeContents() {
assert(files.size() != 0)(static_cast <bool> (files.size() != 0) ? void (0) : __assert_fail
 ("files.size() != 0", "lld/MachO/SyntheticSections.cpp", 1870
, __extension__ __PRETTY_FUNCTION__)); // should have already been checked via isNeeded()

info.hasCategoryClassProperties = true;
const InputFile *firstFile;
for (auto file : files) {
  ImageInfo inputInfo = parseImageInfo(file);
  info.hasCategoryClassProperties &= inputInfo.hasCategoryClassProperties;

  // swiftVersion 0 means no Swift is present, so no version checking required
  if (inputInfo.swiftVersion == 0)
    continue;

  if (info.swiftVersion != 0 && info.swiftVersion != inputInfo.swiftVersion) {
    error("Swift version mismatch: " + toString(firstFile) + " has version " +
          swiftVersionString(info.swiftVersion) + " but " + toString(file) +
          " has version " + swiftVersionString(inputInfo.swiftVersion));
  } else {
    info.swiftVersion = inputInfo.swiftVersion;
    firstFile = file;
  }
}
1891}

1893void ObjCImageInfoSection::writeTo(uint8_t *buf) const {
uint32_t flags = info.hasCategoryClassProperties ? 0x40 : 0x0;
flags |= info.swiftVersion << 8;
write32le(buf + 4, flags);
1897}

1899InitOffsetsSection::InitOffsetsSection()
  : SyntheticSection(segment_names::text, section_names::initOffsets) {
flags = S_INIT_FUNC_OFFSETS;
align = 4; // This section contains 32-bit integers.
1903}

1905uint64_t InitOffsetsSection::getSize() const {
size_t count = 0;
for (const ConcatInputSection *isec : sections)
  count += isec->relocs.size();
return count * sizeof(uint32_t);
1910}

1912void InitOffsetsSection::writeTo(uint8_t *buf) const {
// FIXME: Add function specified by -init when that argument is implemented.
for (ConcatInputSection *isec : sections) {
  for (const Reloc &rel : isec->relocs) {
    const Symbol *referent = rel.referent.dyn_cast<Symbol *>();
    assert(referent && "section relocation should have been rejected")(static_cast <bool> (referent && "section relocation should have been rejected"
) ? void (0) : __assert_fail ("referent && \"section relocation should have been rejected\""
, "lld/MachO/SyntheticSections.cpp", 1917, __extension__ __PRETTY_FUNCTION__
));
    uint64_t offset = referent->getVA() - in.header->addr;
    // FIXME: Can we handle this gracefully?
    if (offset > UINT32_MAX(4294967295U))
      fatal(isec->getLocation(rel.offset) + ": offset to initializer " +
            referent->getName() + " (" + utohexstr(offset) +
            ") does not fit in 32 bits");

    // Entries need to be added in the order they appear in the section, but
    // relocations aren't guaranteed to be sorted.
    size_t index = rel.offset >> target->p2WordSize;
    write32le(&buf[index * sizeof(uint32_t)], offset);
  }
  buf += isec->relocs.size() * sizeof(uint32_t);
}
1932}

1934// The inputs are __mod_init_func sections, which contain pointers to
1935// initializer functions, therefore all relocations should be of the UNSIGNED
1936// type. InitOffsetsSection stores offsets, so if the initializer's address is
1937// not known at link time, stub-indirection has to be used.
1938void InitOffsetsSection::setUp() {
for (const ConcatInputSection *isec : sections) {
  for (const Reloc &rel : isec->relocs) {
    RelocAttrs attrs = target->getRelocAttrs(rel.type);
    if (!attrs.hasAttr(RelocAttrBits::UNSIGNED))
      error(isec->getLocation(rel.offset) +
            ": unsupported relocation type: " + attrs.name);
    if (rel.addend != 0)
      error(isec->getLocation(rel.offset) +
            ": relocation addend is not representable in __init_offsets");
    if (rel.referent.is<InputSection *>())
      error(isec->getLocation(rel.offset) +
            ": unexpected section relocation");

    Symbol *sym = rel.referent.dyn_cast<Symbol *>();
    if (auto *undefined = dyn_cast<Undefined>(sym))
      treatUndefinedSymbol(*undefined, isec, rel.offset);
    if (needsBinding(sym))
      in.stubs->addEntry(sym);
  }
}
1959}

1961void macho::createSyntheticSymbols() {
auto addHeaderSymbol = [](const char *name) {
  symtab->addSynthetic(name, in.header->isec, /*value=*/0,
                       /*isPrivateExtern=*/true, /*includeInSymtab=*/false,
                       /*referencedDynamically=*/false);
};

switch (config->outputType) {
  // FIXME: Assign the right address value for these symbols
  // (rather than 0). But we need to do that after assignAddresses().
case MH_EXECUTE:
  // If linking PIE, __mh_execute_header is a defined symbol in
  //  __TEXT, __text)
  // Otherwise, it's an absolute symbol.
  if (config->isPic)
    symtab->addSynthetic("__mh_execute_header", in.header->isec, /*value=*/0,
                         /*isPrivateExtern=*/false, /*includeInSymtab=*/true,
                         /*referencedDynamically=*/true);
  else
    symtab->addSynthetic("__mh_execute_header", /*isec=*/nullptr, /*value=*/0,
                         /*isPrivateExtern=*/false, /*includeInSymtab=*/true,
                         /*referencedDynamically=*/true);
  break;

  // The following symbols are N_SECT symbols, even though the header is not
  // part of any section and that they are private to the bundle/dylib/object
  // they are part of.
case MH_BUNDLE:
  addHeaderSymbol("__mh_bundle_header");
  break;
case MH_DYLIB:
  addHeaderSymbol("__mh_dylib_header");
  break;
case MH_DYLINKER:
  addHeaderSymbol("__mh_dylinker_header");
  break;
case MH_OBJECT:
  addHeaderSymbol("__mh_object_header");
  break;
default:
  llvm_unreachable("unexpected outputType")::llvm::llvm_unreachable_internal("unexpected outputType", "lld/MachO/SyntheticSections.cpp"
, 2001);
  break;
}

// The Itanium C++ ABI requires dylibs to pass a pointer to __cxa_atexit
// which does e.g. cleanup of static global variables. The ABI document
// says that the pointer can point to any address in one of the dylib's
// segments, but in practice ld64 seems to set it to point to the header,
// so that's what's implemented here.
addHeaderSymbol("___dso_handle");
2011}

2013ChainedFixupsSection::ChainedFixupsSection()
  : LinkEditSection(segment_names::linkEdit, section_names::chainFixups) {}

2016bool ChainedFixupsSection::isNeeded() const {
assert(config->emitChainedFixups)(static_cast <bool> (config->emitChainedFixups) ? void
 (0) : __assert_fail ("config->emitChainedFixups", "lld/MachO/SyntheticSections.cpp"
, 2017, __extension__ __PRETTY_FUNCTION__));
// dyld always expects LC_DYLD_CHAINED_FIXUPS to point to a valid
// dyld_chained_fixups_header, so we create this section even if there aren't
// any fixups.
return true;
2022}

2024static bool needsWeakBind(const Symbol &sym) {
if (auto *dysym = dyn_cast<DylibSymbol>(&sym))
  return dysym->isWeakDef();
if (auto *defined = dyn_cast<Defined>(&sym))
  return defined->isExternalWeakDef();
return false;
2030}

2032void ChainedFixupsSection::addBinding(const Symbol *sym,
                                    const InputSection *isec, uint64_t offset,
                                    int64_t addend) {
locations.emplace_back(isec, offset);
int64_t outlineAddend = (addend < 0 || addend > 0xFF) ? addend : 0;
auto [it, inserted] = bindings.insert(
    {{sym, outlineAddend}, static_cast<uint32_t>(bindings.size())});

if (inserted) {
  symtabSize += sym->getName().size() + 1;
  hasWeakBind = hasWeakBind || needsWeakBind(*sym);
  if (!isInt<23>(outlineAddend))
    needsLargeAddend = true;
  else if (outlineAddend != 0)
    needsAddend = true;
}
2048}

2050std::pair<uint32_t, uint8_t>
2051ChainedFixupsSection::getBinding(const Symbol *sym, int64_t addend) const {
int64_t outlineAddend = (addend < 0 || addend > 0xFF) ? addend : 0;
auto it = bindings.find({sym, outlineAddend});
assert(it != bindings.end() && "binding not found in the imports table")(static_cast <bool> (it != bindings.end() && "binding not found in the imports table"
) ? void (0) : __assert_fail ("it != bindings.end() && \"binding not found in the imports table\""
, "lld/MachO/SyntheticSections.cpp", 2054, __extension__ __PRETTY_FUNCTION__
));
if (outlineAddend == 0)
  return {it->second, addend};
return {it->second, 0};
2058}

2060static size_t writeImport(uint8_t *buf, int format, uint32_t libOrdinal,
                        bool weakRef, uint32_t nameOffset, int64_t addend) {
switch (format) {
case DYLD_CHAINED_IMPORT: {
  auto *import = reinterpret_cast<dyld_chained_import *>(buf);
  import->lib_ordinal = libOrdinal;
  import->weak_import = weakRef;
  import->name_offset = nameOffset;
  return sizeof(dyld_chained_import);
}
case DYLD_CHAINED_IMPORT_ADDEND: {
  auto *import = reinterpret_cast<dyld_chained_import_addend *>(buf);
  import->lib_ordinal = libOrdinal;
  import->weak_import = weakRef;
  import->name_offset = nameOffset;
  import->addend = addend;
  return sizeof(dyld_chained_import_addend);
}
case DYLD_CHAINED_IMPORT_ADDEND64: {
  auto *import = reinterpret_cast<dyld_chained_import_addend64 *>(buf);
  import->lib_ordinal = libOrdinal;
  import->weak_import = weakRef;
  import->name_offset = nameOffset;
  import->addend = addend;
  return sizeof(dyld_chained_import_addend64);
}
default:
  llvm_unreachable("Unknown import format")::llvm::llvm_unreachable_internal("Unknown import format", "lld/MachO/SyntheticSections.cpp"
, 2087);
}
2089}

2091size_t ChainedFixupsSection::SegmentInfo::getSize() const {
assert(pageStarts.size() > 0 && "SegmentInfo for segment with no fixups?")(static_cast <bool> (pageStarts.size() > 0 &&
 "SegmentInfo for segment with no fixups?") ? void (0) : __assert_fail
 ("pageStarts.size() > 0 && \"SegmentInfo for segment with no fixups?\""
, "lld/MachO/SyntheticSections.cpp", 2092, __extension__ __PRETTY_FUNCTION__
));
return alignTo<8>(sizeof(dyld_chained_starts_in_segment) +
                  pageStarts.back().first * sizeof(uint16_t));
2095}

2097size_t ChainedFixupsSection::SegmentInfo::writeTo(uint8_t *buf) const {
auto *segInfo = reinterpret_cast<dyld_chained_starts_in_segment *>(buf);
segInfo->size = getSize();
segInfo->page_size = target->getPageSize();
// FIXME: Use DYLD_CHAINED_PTR_64_OFFSET on newer OS versions.
segInfo->pointer_format = DYLD_CHAINED_PTR_64;
segInfo->segment_offset = oseg->addr - in.header->addr;
segInfo->max_valid_pointer = 0; // not used on 64-bit
segInfo->page_count = pageStarts.back().first + 1;

uint16_t *starts = segInfo->page_start;
for (size_t i = 0; i < segInfo->page_count; ++i)
  starts[i] = DYLD_CHAINED_PTR_START_NONE;

for (auto [pageIdx, startAddr] : pageStarts)
  starts[pageIdx] = startAddr;
return segInfo->size;
2114}

2116static size_t importEntrySize(int format) {
switch (format) {
case DYLD_CHAINED_IMPORT:
  return sizeof(dyld_chained_import);
case DYLD_CHAINED_IMPORT_ADDEND:
  return sizeof(dyld_chained_import_addend);
case DYLD_CHAINED_IMPORT_ADDEND64:
  return sizeof(dyld_chained_import_addend64);
default:
  llvm_unreachable("Unknown import format")::llvm::llvm_unreachable_internal("Unknown import format", "lld/MachO/SyntheticSections.cpp"
, 2125);
}
2127}

2129// This is step 3 of the algorithm described in the class comment of
2130// ChainedFixupsSection.
2131//
2132// LC_DYLD_CHAINED_FIXUPS data consists of (in this order):
2133// * A dyld_chained_fixups_header
2134// * A dyld_chained_starts_in_image
2135// * One dyld_chained_starts_in_segment per segment
2136// * List of all imports (dyld_chained_import, dyld_chained_import_addend, or
2137//   dyld_chained_import_addend64)
2138// * Names of imported symbols
2139void ChainedFixupsSection::writeTo(uint8_t *buf) const {
auto *header = reinterpret_cast<dyld_chained_fixups_header *>(buf);
header->fixups_version = 0;
header->imports_count = bindings.size();
header->imports_format = importFormat;
header->symbols_format = 0;

buf += alignTo<8>(sizeof(*header));

auto curOffset = [&buf, &header]() -> uint32_t {
  return buf - reinterpret_cast<uint8_t *>(header);
};

header->starts_offset = curOffset();

auto *imageInfo = reinterpret_cast<dyld_chained_starts_in_image *>(buf);
imageInfo->seg_count = outputSegments.size();
uint32_t *segStarts = imageInfo->seg_info_offset;

// dyld_chained_starts_in_image ends in a flexible array member containing an
// uint32_t for each segment. Leave room for it, and fill it via segStarts.
buf += alignTo<8>(offsetof(dyld_chained_starts_in_image, seg_info_offset)__builtin_offsetof(dyld_chained_starts_in_image, seg_info_offset
) +
                  outputSegments.size() * sizeof(uint32_t));

// Initialize all offsets to 0, which indicates that the segment does not have
// fixups. Those that do have them will be filled in below.
for (size_t i = 0; i < outputSegments.size(); ++i)
  segStarts[i] = 0;

for (const SegmentInfo &seg : fixupSegments) {
  segStarts[seg.oseg->index] = curOffset() - header->starts_offset;
  buf += seg.writeTo(buf);
}

// Write imports table.
header->imports_offset = curOffset();
uint64_t nameOffset = 0;
for (auto [import, idx] : bindings) {
  const Symbol &sym = *import.first;
  int16_t libOrdinal = needsWeakBind(sym)
                           ? (int64_t)BIND_SPECIAL_DYLIB_WEAK_LOOKUP
                           : ordinalForSymbol(sym);
  buf += writeImport(buf, importFormat, libOrdinal, sym.isWeakRef(),
                     nameOffset, import.second);
  nameOffset += sym.getName().size() + 1;
}

// Write imported symbol names.
header->symbols_offset = curOffset();
for (auto [import, idx] : bindings) {
  StringRef name = import.first->getName();
  memcpy(buf, name.data(), name.size());
  buf += name.size() + 1; // account for null terminator
}

assert(curOffset() == getRawSize())(static_cast <bool> (curOffset() == getRawSize()) ? void
 (0) : __assert_fail ("curOffset() == getRawSize()", "lld/MachO/SyntheticSections.cpp"
, 2194, __extension__ __PRETTY_FUNCTION__));
2195}

2197// This is step 2 of the algorithm described in the class comment of
2198// ChainedFixupsSection.
2199void ChainedFixupsSection::finalizeContents() {
assert(target->wordSize == 8 && "Only 64-bit platforms are supported")(static_cast <bool> (target->wordSize == 8 &&
 "Only 64-bit platforms are supported") ? void (0) : __assert_fail
 ("target->wordSize == 8 && \"Only 64-bit platforms are supported\""
, "lld/MachO/SyntheticSections.cpp", 2200, __extension__ __PRETTY_FUNCTION__
));
assert(config->emitChainedFixups)(static_cast <bool> (config->emitChainedFixups) ? void
 (0) : __assert_fail ("config->emitChainedFixups", "lld/MachO/SyntheticSections.cpp"
, 2201, __extension__ __PRETTY_FUNCTION__));

if (!isUInt<32>(symtabSize))
  error("cannot encode chained fixups: imported symbols table size " +
        Twine(symtabSize) + " exceeds 4 GiB");

if (needsLargeAddend || !isUInt<23>(symtabSize))
  importFormat = DYLD_CHAINED_IMPORT_ADDEND64;
else if (needsAddend)
  importFormat = DYLD_CHAINED_IMPORT_ADDEND;
else
  importFormat = DYLD_CHAINED_IMPORT;

for (Location &loc : locations)
  loc.offset =
      loc.isec->parent->getSegmentOffset() + loc.isec->getOffset(loc.offset);

llvm::sort(locations, [](const Location &a, const Location &b) {
  const OutputSegment *segA = a.isec->parent->parent;
  const OutputSegment *segB = b.isec->parent->parent;
  if (segA == segB)
    return a.offset < b.offset;
  return segA->addr < segB->addr;
});

auto sameSegment = [](const Location &a, const Location &b) {
  return a.isec->parent->parent == b.isec->parent->parent;
};

const uint64_t pageSize = target->getPageSize();
for (size_t i = 0, count = locations.size(); i < count;) {
  const Location &firstLoc = locations[i];
  fixupSegments.emplace_back(firstLoc.isec->parent->parent);
  while (i < count && sameSegment(locations[i], firstLoc)) {
    uint32_t pageIdx = locations[i].offset / pageSize;
    fixupSegments.back().pageStarts.emplace_back(
        pageIdx, locations[i].offset % pageSize);
    ++i;
    while (i < count && sameSegment(locations[i], firstLoc) &&
           locations[i].offset / pageSize == pageIdx)
      ++i;
  }
}

// Compute expected encoded size.
size = alignTo<8>(sizeof(dyld_chained_fixups_header));
size += alignTo<8>(offsetof(dyld_chained_starts_in_image, seg_info_offset)__builtin_offsetof(dyld_chained_starts_in_image, seg_info_offset
) +
                   outputSegments.size() * sizeof(uint32_t));
for (const SegmentInfo &seg : fixupSegments)
  size += seg.getSize();
size += importEntrySize(importFormat) * bindings.size();
size += symtabSize;
2253}

2255template SymtabSection *macho::makeSymtabSection<LP64>(StringTableSection &);
2256template SymtabSection *macho::makeSymtabSection<ILP32>(StringTableSection &);

←

/build/source/llvm/include/llvm/Support/MathExtras.h

→

1//===-- llvm/Support/MathExtras.h - Useful math functions -------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains some functions that are useful for math stuff.
10//
11//===----------------------------------------------------------------------===//
12 
13#ifndef LLVM_SUPPORT_MATHEXTRAS_H
14#define LLVM_SUPPORT_MATHEXTRAS_H
15 
16#include "llvm/ADT/bit.h"
17#include "llvm/Support/Compiler.h"
18#include <cassert>
19#include <climits>
20#include <cstdint>
21#include <cstring>
22#include <limits>
23#include <type_traits>
24 
25namespace llvm {
26 
27/// The behavior an operation has on an input of 0.
28enum ZeroBehavior {
29  /// The returned value is undefined.
30  ZB_Undefined,
31  /// The returned value is numeric_limits<T>::max()
32  ZB_Max
33};
34 
35/// Mathematical constants.
36namespace numbers {
37// TODO: Track C++20 std::numbers.
38// TODO: Favor using the hexadecimal FP constants (requires C++17).
39constexpr double e          = 2.7182818284590452354, // (0x1.5bf0a8b145749P+1) https://oeis.org/A001113
40                 egamma     = .57721566490153286061, // (0x1.2788cfc6fb619P-1) https://oeis.org/A001620
41                 ln2        = .69314718055994530942, // (0x1.62e42fefa39efP-1) https://oeis.org/A002162
42                 ln10       = 2.3025850929940456840, // (0x1.24bb1bbb55516P+1) https://oeis.org/A002392
43                 log2e      = 1.4426950408889634074, // (0x1.71547652b82feP+0)
44                 log10e     = .43429448190325182765, // (0x1.bcb7b1526e50eP-2)
45                 pi         = 3.1415926535897932385, // (0x1.921fb54442d18P+1) https://oeis.org/A000796
46                 inv_pi     = .31830988618379067154, // (0x1.45f306bc9c883P-2) https://oeis.org/A049541
47                 sqrtpi     = 1.7724538509055160273, // (0x1.c5bf891b4ef6bP+0) https://oeis.org/A002161
48                 inv_sqrtpi = .56418958354775628695, // (0x1.20dd750429b6dP-1) https://oeis.org/A087197
49                 sqrt2      = 1.4142135623730950488, // (0x1.6a09e667f3bcdP+0) https://oeis.org/A00219
50                 inv_sqrt2  = .70710678118654752440, // (0x1.6a09e667f3bcdP-1)
51                 sqrt3      = 1.7320508075688772935, // (0x1.bb67ae8584caaP+0) https://oeis.org/A002194
52                 inv_sqrt3  = .57735026918962576451, // (0x1.279a74590331cP-1)
53                 phi        = 1.6180339887498948482; // (0x1.9e3779b97f4a8P+0) https://oeis.org/A001622
54constexpr float ef          = 2.71828183F, // (0x1.5bf0a8P+1) https://oeis.org/A001113
55                egammaf     = .577215665F, // (0x1.2788d0P-1) https://oeis.org/A001620
56                ln2f        = .693147181F, // (0x1.62e430P-1) https://oeis.org/A002162
57                ln10f       = 2.30258509F, // (0x1.26bb1cP+1) https://oeis.org/A002392
58                log2ef      = 1.44269504F, // (0x1.715476P+0)
59                log10ef     = .434294482F, // (0x1.bcb7b2P-2)
60                pif         = 3.14159265F, // (0x1.921fb6P+1) https://oeis.org/A000796
61                inv_pif     = .318309886F, // (0x1.45f306P-2) https://oeis.org/A049541
62                sqrtpif     = 1.77245385F, // (0x1.c5bf8aP+0) https://oeis.org/A002161
63                inv_sqrtpif = .564189584F, // (0x1.20dd76P-1) https://oeis.org/A087197
64                sqrt2f      = 1.41421356F, // (0x1.6a09e6P+0) https://oeis.org/A002193
65                inv_sqrt2f  = .707106781F, // (0x1.6a09e6P-1)
66                sqrt3f      = 1.73205081F, // (0x1.bb67aeP+0) https://oeis.org/A002194
67                inv_sqrt3f  = .577350269F, // (0x1.279a74P-1)
68                phif        = 1.61803399F; // (0x1.9e377aP+0) https://oeis.org/A001622
69} // namespace numbers
70 
71/// Count number of 0's from the least significant bit to the most
72///   stopping at the first 1.
73///
74/// Only unsigned integral types are allowed.
75///
76/// Returns std::numeric_limits<T>::digits on an input of 0.
77template <typename T> unsigned countTrailingZeros(T Val) {
78  static_assert(std::is_unsigned_v<T>,
79                "Only unsigned integral types are allowed.");
80  return llvm::countr_zero(Val);
4
←
Calling 'countr_zero<unsigned int>'→
11
←
Returning from 'countr_zero<unsigned int>'→
12
←
Returning the value 32→
81}
82 
83/// Count number of 0's from the most significant bit to the least
84///   stopping at the first 1.
85///
86/// Only unsigned integral types are allowed.
87///
88/// Returns std::numeric_limits<T>::digits on an input of 0.
89template <typename T> unsigned countLeadingZeros(T Val) {
90  static_assert(std::is_unsigned_v<T>,
91                "Only unsigned integral types are allowed.");
92  return llvm::countl_zero(Val);
93}
94 
95/// Get the index of the first set bit starting from the least
96///   significant bit.
97///
98/// Only unsigned integral types are allowed.
99///
100/// \param ZB the behavior on an input of 0.
101template <typename T> T findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) {
102  if (ZB == ZB_Max && Val == 0)
103    return std::numeric_limits<T>::max();
104 
105  return llvm::countr_zero(Val);
106}
107 
108/// Create a bitmask with the N right-most bits set to 1, and all other
109/// bits set to 0.  Only unsigned types are allowed.
110template <typename T> T maskTrailingOnes(unsigned N) {
111  static_assert(std::is_unsigned<T>::value, "Invalid type!");
112  const unsigned Bits = CHAR_BIT8 * sizeof(T);
113  assert(N <= Bits && "Invalid bit index")(static_cast <bool> (N <= Bits && "Invalid bit index"
) ? void (0) : __assert_fail ("N <= Bits && \"Invalid bit index\""
, "llvm/include/llvm/Support/MathExtras.h", 113, __extension__
 __PRETTY_FUNCTION__));
114  return N == 0 ? 0 : (T(-1) >> (Bits - N));
115}
116 
117/// Create a bitmask with the N left-most bits set to 1, and all other
118/// bits set to 0.  Only unsigned types are allowed.
119template <typename T> T maskLeadingOnes(unsigned N) {
120  return ~maskTrailingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
121}
122 
123/// Create a bitmask with the N right-most bits set to 0, and all other
124/// bits set to 1.  Only unsigned types are allowed.
125template <typename T> T maskTrailingZeros(unsigned N) {
126  return maskLeadingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
127}
128 
129/// Create a bitmask with the N left-most bits set to 0, and all other
130/// bits set to 1.  Only unsigned types are allowed.
131template <typename T> T maskLeadingZeros(unsigned N) {
132  return maskTrailingOnes<T>(CHAR_BIT8 * sizeof(T) - N);
133}
134 
135/// Get the index of the last set bit starting from the least
136///   significant bit.
137///
138/// Only unsigned integral types are allowed.
139///
140/// \param ZB the behavior on an input of 0.
141template <typename T> T findLastSet(T Val, ZeroBehavior ZB = ZB_Max) {
142  if (ZB == ZB_Max && Val == 0)
143    return std::numeric_limits<T>::max();
144 
145  // Use ^ instead of - because both gcc and llvm can remove the associated ^
146  // in the __builtin_clz intrinsic on x86.
147  return llvm::countl_zero(Val) ^ (std::numeric_limits<T>::digits - 1);
148}
149 
150/// Macro compressed bit reversal table for 256 bits.
151///
152/// http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
153static const unsigned char BitReverseTable256[256] = {
154#define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64
155#define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16)
156#define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4)
157  R6(0), R6(2), R6(1), R6(3)
158#undef R2
159#undef R4
160#undef R6
161};
162 
163/// Reverse the bits in \p Val.
164template <typename T> T reverseBits(T Val) {
165#if __has_builtin(__builtin_bitreverse8)1
166  if constexpr (std::is_same_v<T, uint8_t>)
167    return __builtin_bitreverse8(Val);
168#endif
169#if __has_builtin(__builtin_bitreverse16)1
170  if constexpr (std::is_same_v<T, uint16_t>)
171    return __builtin_bitreverse16(Val);
172#endif
173#if __has_builtin(__builtin_bitreverse32)1
174  if constexpr (std::is_same_v<T, uint32_t>)
175    return __builtin_bitreverse32(Val);
176#endif
177#if __has_builtin(__builtin_bitreverse64)1
178  if constexpr (std::is_same_v<T, uint64_t>)
179    return __builtin_bitreverse64(Val);
180#endif
181 
182  unsigned char in[sizeof(Val)];
183  unsigned char out[sizeof(Val)];
184  std::memcpy(in, &Val, sizeof(Val));
185  for (unsigned i = 0; i < sizeof(Val); ++i)
186    out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
187  std::memcpy(&Val, out, sizeof(Val));
188  return Val;
189}
190 
191// NOTE: The following support functions use the _32/_64 extensions instead of
192// type overloading so that signed and unsigned integers can be used without
193// ambiguity.
194 
195/// Return the high 32 bits of a 64 bit value.
196constexpr inline uint32_t Hi_32(uint64_t Value) {
197  return static_cast<uint32_t>(Value >> 32);
198}
199 
200/// Return the low 32 bits of a 64 bit value.
201constexpr inline uint32_t Lo_32(uint64_t Value) {
202  return static_cast<uint32_t>(Value);
203}
204 
205/// Make a 64-bit integer from a high / low pair of 32-bit integers.
206constexpr inline uint64_t Make_64(uint32_t High, uint32_t Low) {
207  return ((uint64_t)High << 32) | (uint64_t)Low;
208}
209 
210/// Checks if an integer fits into the given bit width.
211template <unsigned N> constexpr inline bool isInt(int64_t x) {
212  if constexpr (N == 8)
213    return static_cast<int8_t>(x) == x;
214  if constexpr (N == 16)
215    return static_cast<int16_t>(x) == x;
216  if constexpr (N == 32)
217    return static_cast<int32_t>(x) == x;
218  if constexpr (N < 64)
219    return -(INT64_C(1)1L << (N - 1)) <= x && x < (INT64_C(1)1L << (N - 1));
220  (void)x; // MSVC v19.25 warns that x is unused.
221  return true;
222}
223 
224/// Checks if a signed integer is an N bit number shifted left by S.
225template <unsigned N, unsigned S>
226constexpr inline bool isShiftedInt(int64_t x) {
227  static_assert(
228      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
229  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
230  return isInt<N + S>(x) && (x % (UINT64_C(1)1UL << S) == 0);
231}
232 
233/// Checks if an unsigned integer fits into the given bit width.
234template <unsigned N> constexpr inline bool isUInt(uint64_t x) {
235  static_assert(N > 0, "isUInt<0> doesn't make sense");
236  if constexpr (N == 8)
237    return static_cast<uint8_t>(x) == x;
238  if constexpr (N == 16)
239    return static_cast<uint16_t>(x) == x;
240  if constexpr (N == 32)
241    return static_cast<uint32_t>(x) == x;
242  if constexpr (N < 64)
243    return x < (UINT64_C(1)1UL << (N));
244  (void)x; // MSVC v19.25 warns that x is unused.
245  return true;
246}
247 
248/// Checks if a unsigned integer is an N bit number shifted left by S.
249template <unsigned N, unsigned S>
250constexpr inline bool isShiftedUInt(uint64_t x) {
251  static_assert(
252      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
253  static_assert(N + S <= 64,
254                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
255  // Per the two static_asserts above, S must be strictly less than 64.  So
256  // 1 << S is not undefined behavior.
257  return isUInt<N + S>(x) && (x % (UINT64_C(1)1UL << S) == 0);
258}
259 
260/// Gets the maximum value for a N-bit unsigned integer.
261inline uint64_t maxUIntN(uint64_t N) {
262  assert(N > 0 && N <= 64 && "integer width out of range")(static_cast <bool> (N > 0 && N <= 64 &&
 "integer width out of range") ? void (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\""
, "llvm/include/llvm/Support/MathExtras.h", 262, __extension__
 __PRETTY_FUNCTION__));
263 
264  // uint64_t(1) << 64 is undefined behavior, so we can't do
265  //   (uint64_t(1) << N) - 1
266  // without checking first that N != 64.  But this works and doesn't have a
267  // branch.
268  return UINT64_MAX(18446744073709551615UL) >> (64 - N);
269}
270 
271/// Gets the minimum value for a N-bit signed integer.
272inline int64_t minIntN(int64_t N) {
273  assert(N > 0 && N <= 64 && "integer width out of range")(static_cast <bool> (N > 0 && N <= 64 &&
 "integer width out of range") ? void (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\""
, "llvm/include/llvm/Support/MathExtras.h", 273, __extension__
 __PRETTY_FUNCTION__));
274 
275  return UINT64_C(1)1UL + ~(UINT64_C(1)1UL << (N - 1));
276}
277 
278/// Gets the maximum value for a N-bit signed integer.
279inline int64_t maxIntN(int64_t N) {
280  assert(N > 0 && N <= 64 && "integer width out of range")(static_cast <bool> (N > 0 && N <= 64 &&
 "integer width out of range") ? void (0) : __assert_fail ("N > 0 && N <= 64 && \"integer width out of range\""
, "llvm/include/llvm/Support/MathExtras.h", 280, __extension__
 __PRETTY_FUNCTION__));
281 
282  // This relies on two's complement wraparound when N == 64, so we convert to
283  // int64_t only at the very end to avoid UB.
284  return (UINT64_C(1)1UL << (N - 1)) - 1;
285}
286 
287/// Checks if an unsigned integer fits into the given (dynamic) bit width.
288inline bool isUIntN(unsigned N, uint64_t x) {
289  return N >= 64 || x <= maxUIntN(N);
290}
291 
292/// Checks if an signed integer fits into the given (dynamic) bit width.
293inline bool isIntN(unsigned N, int64_t x) {
294  return N >= 64 || (minIntN(N) <= x && x <= maxIntN(N));
295}
296 
297/// Return true if the argument is a non-empty sequence of ones starting at the
298/// least significant bit with the remainder zero (32 bit version).
299/// Ex. isMask_32(0x0000FFFFU) == true.
300constexpr inline bool isMask_32(uint32_t Value) {
301  return Value && ((Value + 1) & Value) == 0;
302}
303 
304/// Return true if the argument is a non-empty sequence of ones starting at the
305/// least significant bit with the remainder zero (64 bit version).
306constexpr inline bool isMask_64(uint64_t Value) {
307  return Value && ((Value + 1) & Value) == 0;
308}
309 
310/// Return true if the argument contains a non-empty sequence of ones with the
311/// remainder zero (32 bit version.) Ex. isShiftedMask_32(0x0000FF00U) == true.
312constexpr inline bool isShiftedMask_32(uint32_t Value) {
313  return Value && isMask_32((Value - 1) | Value);
314}
315 
316/// Return true if the argument contains a non-empty sequence of ones with the
317/// remainder zero (64 bit version.)
318constexpr inline bool isShiftedMask_64(uint64_t Value) {
319  return Value && isMask_64((Value - 1) | Value);
320}
321 
322/// Return true if the argument is a power of two > 0.
323/// Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
324constexpr inline bool isPowerOf2_32(uint32_t Value) {
325  return llvm::has_single_bit(Value);
326}
327 
328/// Return true if the argument is a power of two > 0 (64 bit edition.)
329constexpr inline bool isPowerOf2_64(uint64_t Value) {
330  return llvm::has_single_bit(Value);
331}
332 
333/// Count the number of ones from the most significant bit to the first
334/// zero bit.
335///
336/// Ex. countLeadingOnes(0xFF0FFF00) == 8.
337/// Only unsigned integral types are allowed.
338///
339/// Returns std::numeric_limits<T>::digits on an input of all ones.
340template <typename T> unsigned countLeadingOnes(T Value) {
341  static_assert(std::is_unsigned_v<T>,
342                "Only unsigned integral types are allowed.");
343  return llvm::countl_one<T>(Value);
344}
345 
346/// Count the number of ones from the least significant bit to the first
347/// zero bit.
348///
349/// Ex. countTrailingOnes(0x00FF00FF) == 8.
350/// Only unsigned integral types are allowed.
351///
352/// Returns std::numeric_limits<T>::digits on an input of all ones.
353template <typename T> unsigned countTrailingOnes(T Value) {
354  static_assert(std::is_unsigned_v<T>,
355                "Only unsigned integral types are allowed.");
356  return llvm::countr_one<T>(Value);
357}
358 
359/// Count the number of set bits in a value.
360/// Ex. countPopulation(0xF000F000) = 8
361/// Returns 0 if the word is zero.
362template <typename T>
363inline unsigned countPopulation(T Value) {
364  static_assert(std::is_unsigned_v<T>,
365                "Only unsigned integral types are allowed.");
366  return (unsigned)llvm::popcount(Value);
367}
368 
369/// Return true if the argument contains a non-empty sequence of ones with the
370/// remainder zero (32 bit version.) Ex. isShiftedMask_32(0x0000FF00U) == true.
371/// If true, \p MaskIdx will specify the index of the lowest set bit and \p
372/// MaskLen is updated to specify the length of the mask, else neither are
373/// updated.
374inline bool isShiftedMask_32(uint32_t Value, unsigned &MaskIdx,
375                             unsigned &MaskLen) {
376  if (!isShiftedMask_32(Value))
377    return false;
378  MaskIdx = llvm::countr_zero(Value);
379  MaskLen = llvm::popcount(Value);
380  return true;
381}
382 
383/// Return true if the argument contains a non-empty sequence of ones with the
384/// remainder zero (64 bit version.) If true, \p MaskIdx will specify the index
385/// of the lowest set bit and \p MaskLen is updated to specify the length of the
386/// mask, else neither are updated.
387inline bool isShiftedMask_64(uint64_t Value, unsigned &MaskIdx,
388                             unsigned &MaskLen) {
389  if (!isShiftedMask_64(Value))
390    return false;
391  MaskIdx = llvm::countr_zero(Value);
392  MaskLen = llvm::popcount(Value);
393  return true;
394}
395 
396/// Compile time Log2.
397/// Valid only for positive powers of two.
398template <size_t kValue> constexpr inline size_t CTLog2() {
399  static_assert(kValue > 0 && llvm::isPowerOf2_64(kValue),
400                "Value is not a valid power of 2");
401  return 1 + CTLog2<kValue / 2>();
402}
403 
404template <> constexpr inline size_t CTLog2<1>() { return 0; }
405 
406/// Return the floor log base 2 of the specified value, -1 if the value is zero.
407/// (32 bit edition.)
408/// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
409inline unsigned Log2_32(uint32_t Value) {
410  return 31 - llvm::countl_zero(Value);
411}
412 
413/// Return the floor log base 2 of the specified value, -1 if the value is zero.
414/// (64 bit edition.)
415inline unsigned Log2_64(uint64_t Value) {
416  return 63 - llvm::countl_zero(Value);
417}
418 
419/// Return the ceil log base 2 of the specified value, 32 if the value is zero.
420/// (32 bit edition).
421/// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
422inline unsigned Log2_32_Ceil(uint32_t Value) {
423  return 32 - llvm::countl_zero(Value - 1);
424}
425 
426/// Return the ceil log base 2 of the specified value, 64 if the value is zero.
427/// (64 bit edition.)
428inline unsigned Log2_64_Ceil(uint64_t Value) {
429  return 64 - llvm::countl_zero(Value - 1);
430}
431 
432/// This function takes a 64-bit integer and returns the bit equivalent double.
433inline double BitsToDouble(uint64_t Bits) {
434  static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
435  return llvm::bit_cast<double>(Bits);
436}
437 
438/// This function takes a 32-bit integer and returns the bit equivalent float.
439inline float BitsToFloat(uint32_t Bits) {
440  static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
441  return llvm::bit_cast<float>(Bits);
442}
443 
444/// This function takes a double and returns the bit equivalent 64-bit integer.
445/// Note that copying doubles around changes the bits of NaNs on some hosts,
446/// notably x86, so this routine cannot be used if these bits are needed.
447inline uint64_t DoubleToBits(double Double) {
448  static_assert(sizeof(uint64_t) == sizeof(double), "Unexpected type sizes");
449  return llvm::bit_cast<uint64_t>(Double);
450}
451 
452/// This function takes a float and returns the bit equivalent 32-bit integer.
453/// Note that copying floats around changes the bits of NaNs on some hosts,
454/// notably x86, so this routine cannot be used if these bits are needed.
455inline uint32_t FloatToBits(float Float) {
456  static_assert(sizeof(uint32_t) == sizeof(float), "Unexpected type sizes");
457  return llvm::bit_cast<uint32_t>(Float);
458}
459 
460/// A and B are either alignments or offsets. Return the minimum alignment that
461/// may be assumed after adding the two together.
462constexpr inline uint64_t MinAlign(uint64_t A, uint64_t B) {
463  // The largest power of 2 that divides both A and B.
464  //
465  // Replace "-Value" by "1+~Value" in the following commented code to avoid
466  // MSVC warning C4146
467  //    return (A | B) & -(A | B);
468  return (A | B) & (1 + ~(A | B));
469}
470 
471/// Returns the next power of two (in 64-bits) that is strictly greater than A.
472/// Returns zero on overflow.
473constexpr inline uint64_t NextPowerOf2(uint64_t A) {
474  A |= (A >> 1);
475  A |= (A >> 2);
476  A |= (A >> 4);
477  A |= (A >> 8);
478  A |= (A >> 16);
479  A |= (A >> 32);
480  return A + 1;
481}
482 
483/// Returns the power of two which is less than or equal to the given value.
484/// Essentially, it is a floor operation across the domain of powers of two.
485inline uint64_t PowerOf2Floor(uint64_t A) {
486  return llvm::bit_floor(A);
487}
488 
489/// Returns the power of two which is greater than or equal to the given value.
490/// Essentially, it is a ceil operation across the domain of powers of two.
491inline uint64_t PowerOf2Ceil(uint64_t A) {
492  if (!A)
493    return 0;
494  return NextPowerOf2(A - 1);
495}
496 
497/// Returns the next integer (mod 2**64) that is greater than or equal to
498/// \p Value and is a multiple of \p Align. \p Align must be non-zero.
499///
500/// Examples:
501/// \code
502///   alignTo(5, 8) = 8
503///   alignTo(17, 8) = 24
504///   alignTo(~0LL, 8) = 0
505///   alignTo(321, 255) = 510
506/// \endcode
507inline uint64_t alignTo(uint64_t Value, uint64_t Align) {
508  assert(Align != 0u && "Align can't be 0.")(static_cast <bool> (Align != 0u && "Align can't be 0."
) ? void (0) : __assert_fail ("Align != 0u && \"Align can't be 0.\""
, "llvm/include/llvm/Support/MathExtras.h", 508, __extension__
 __PRETTY_FUNCTION__));
509  return (Value + Align - 1) / Align * Align;
510}
511 
512inline uint64_t alignToPowerOf2(uint64_t Value, uint64_t Align) {
513  assert(Align != 0 && (Align & (Align - 1)) == 0 &&(static_cast <bool> (Align != 0 && (Align &
 (Align - 1)) == 0 && "Align must be a power of 2") ?
 void (0) : __assert_fail ("Align != 0 && (Align & (Align - 1)) == 0 && \"Align must be a power of 2\""
, "llvm/include/llvm/Support/MathExtras.h", 514, __extension__
 __PRETTY_FUNCTION__))
514         "Align must be a power of 2")(static_cast <bool> (Align != 0 && (Align &
 (Align - 1)) == 0 && "Align must be a power of 2") ?
 void (0) : __assert_fail ("Align != 0 && (Align & (Align - 1)) == 0 && \"Align must be a power of 2\""
, "llvm/include/llvm/Support/MathExtras.h", 514, __extension__
 __PRETTY_FUNCTION__));
515  return (Value + Align - 1) & -Align;
516}
517 
518/// If non-zero \p Skew is specified, the return value will be a minimal integer
519/// that is greater than or equal to \p Size and equal to \p A * N + \p Skew for
520/// some integer N. If \p Skew is larger than \p A, its value is adjusted to '\p
521/// Skew mod \p A'. \p Align must be non-zero.
522///
523/// Examples:
524/// \code
525///   alignTo(5, 8, 7) = 7
526///   alignTo(17, 8, 1) = 17
527///   alignTo(~0LL, 8, 3) = 3
528///   alignTo(321, 255, 42) = 552
529/// \endcode
530inline uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew) {
531  assert(Align != 0u && "Align can't be 0.")(static_cast <bool> (Align != 0u && "Align can't be 0."
) ? void (0) : __assert_fail ("Align != 0u && \"Align can't be 0.\""
, "llvm/include/llvm/Support/MathExtras.h", 531, __extension__
 __PRETTY_FUNCTION__));
532  Skew %= Align;
533  return alignTo(Value - Skew, Align) + Skew;
534}
535 
536/// Returns the next integer (mod 2**64) that is greater than or equal to
537/// \p Value and is a multiple of \c Align. \c Align must be non-zero.
538template <uint64_t Align> constexpr inline uint64_t alignTo(uint64_t Value) {
539  static_assert(Align != 0u, "Align must be non-zero");
540  return (Value + Align - 1) / Align * Align;
541}
542 
543/// Returns the integer ceil(Numerator / Denominator).
544inline uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator) {
545  return alignTo(Numerator, Denominator) / Denominator;
546}
547 
548/// Returns the integer nearest(Numerator / Denominator).
549inline uint64_t divideNearest(uint64_t Numerator, uint64_t Denominator) {
550  return (Numerator + (Denominator / 2)) / Denominator;
551}
552 
553/// Returns the largest uint64_t less than or equal to \p Value and is
554/// \p Skew mod \p Align. \p Align must be non-zero
555inline uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew = 0) {
556  assert(Align != 0u && "Align can't be 0.")(static_cast <bool> (Align != 0u && "Align can't be 0."
) ? void (0) : __assert_fail ("Align != 0u && \"Align can't be 0.\""
, "llvm/include/llvm/Support/MathExtras.h", 556, __extension__
 __PRETTY_FUNCTION__));
557  Skew %= Align;
558  return (Value - Skew) / Align * Align + Skew;
559}
560 
561/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
562/// Requires 0 < B <= 32.
563template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) {
564  static_assert(B > 0, "Bit width can't be 0.");
565  static_assert(B <= 32, "Bit width out of range.");
566  return int32_t(X << (32 - B)) >> (32 - B);
567}
568 
569/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
570/// Requires 0 < B <= 32.
571inline int32_t SignExtend32(uint32_t X, unsigned B) {
572  assert(B > 0 && "Bit width can't be 0.")(static_cast <bool> (B > 0 && "Bit width can't be 0."
) ? void (0) : __assert_fail ("B > 0 && \"Bit width can't be 0.\""
, "llvm/include/llvm/Support/MathExtras.h", 572, __extension__
 __PRETTY_FUNCTION__));
573  assert(B <= 32 && "Bit width out of range.")(static_cast <bool> (B <= 32 && "Bit width out of range."
) ? void (0) : __assert_fail ("B <= 32 && \"Bit width out of range.\""
, "llvm/include/llvm/Support/MathExtras.h", 573, __extension__
 __PRETTY_FUNCTION__));
574  return int32_t(X << (32 - B)) >> (32 - B);
575}
576 
577/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
578/// Requires 0 < B <= 64.
579template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) {
580  static_assert(B > 0, "Bit width can't be 0.");
581  static_assert(B <= 64, "Bit width out of range.");
582  return int64_t(x << (64 - B)) >> (64 - B);
583}
584 
585/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
586/// Requires 0 < B <= 64.
587inline int64_t SignExtend64(uint64_t X, unsigned B) {
588  assert(B > 0 && "Bit width can't be 0.")(static_cast <bool> (B > 0 && "Bit width can't be 0."
) ? void (0) : __assert_fail ("B > 0 && \"Bit width can't be 0.\""
, "llvm/include/llvm/Support/MathExtras.h", 588, __extension__
 __PRETTY_FUNCTION__));
589  assert(B <= 64 && "Bit width out of range.")(static_cast <bool> (B <= 64 && "Bit width out of range."
) ? void (0) : __assert_fail ("B <= 64 && \"Bit width out of range.\""
, "llvm/include/llvm/Support/MathExtras.h", 589, __extension__
 __PRETTY_FUNCTION__));
590  return int64_t(X << (64 - B)) >> (64 - B);
591}
592 
593/// Subtract two unsigned integers, X and Y, of type T and return the absolute
594/// value of the result.
595template <typename T>
596std::enable_if_t<std::is_unsigned<T>::value, T> AbsoluteDifference(T X, T Y) {
597  return X > Y ? (X - Y) : (Y - X);
598}
599 
600/// Add two unsigned integers, X and Y, of type T.  Clamp the result to the
601/// maximum representable value of T on overflow.  ResultOverflowed indicates if
602/// the result is larger than the maximum representable value of type T.
603template <typename T>
604std::enable_if_t<std::is_unsigned<T>::value, T>
605SaturatingAdd(T X, T Y, bool *ResultOverflowed = nullptr) {
606  bool Dummy;
607  bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
608  // Hacker's Delight, p. 29
609  T Z = X + Y;
610  Overflowed = (Z < X || Z < Y);
611  if (Overflowed)
612    return std::numeric_limits<T>::max();
613  else
614    return Z;
615}
616 
617/// Add multiple unsigned integers of type T.  Clamp the result to the
618/// maximum representable value of T on overflow.
619template <class T, class... Ts>
620std::enable_if_t<std::is_unsigned_v<T>, T> SaturatingAdd(T X, T Y, T Z,
621                                                         Ts... Args) {
622  bool Overflowed = false;
623  T XY = SaturatingAdd(X, Y, &Overflowed);
624  if (Overflowed)
625    return SaturatingAdd(std::numeric_limits<T>::max(), T(1), Args...);
626  return SaturatingAdd(XY, Z, Args...);
627}
628 
629/// Multiply two unsigned integers, X and Y, of type T.  Clamp the result to the
630/// maximum representable value of T on overflow.  ResultOverflowed indicates if
631/// the result is larger than the maximum representable value of type T.
632template <typename T>
633std::enable_if_t<std::is_unsigned<T>::value, T>
634SaturatingMultiply(T X, T Y, bool *ResultOverflowed = nullptr) {
635  bool Dummy;
636  bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
637 
638  // Hacker's Delight, p. 30 has a different algorithm, but we don't use that
639  // because it fails for uint16_t (where multiplication can have undefined
640  // behavior due to promotion to int), and requires a division in addition
641  // to the multiplication.
642 
643  Overflowed = false;
644 
645  // Log2(Z) would be either Log2Z or Log2Z + 1.
646  // Special case: if X or Y is 0, Log2_64 gives -1, and Log2Z
647  // will necessarily be less than Log2Max as desired.
648  int Log2Z = Log2_64(X) + Log2_64(Y);
649  const T Max = std::numeric_limits<T>::max();
650  int Log2Max = Log2_64(Max);
651  if (Log2Z < Log2Max) {
652    return X * Y;
653  }
654  if (Log2Z > Log2Max) {
655    Overflowed = true;
656    return Max;
657  }
658 
659  // We're going to use the top bit, and maybe overflow one
660  // bit past it. Multiply all but the bottom bit then add
661  // that on at the end.
662  T Z = (X >> 1) * Y;
663  if (Z & ~(Max >> 1)) {
664    Overflowed = true;
665    return Max;
666  }
667  Z <<= 1;
668  if (X & 1)
669    return SaturatingAdd(Z, Y, ResultOverflowed);
670 
671  return Z;
672}
673 
674/// Multiply two unsigned integers, X and Y, and add the unsigned integer, A to
675/// the product. Clamp the result to the maximum representable value of T on
676/// overflow. ResultOverflowed indicates if the result is larger than the
677/// maximum representable value of type T.
678template <typename T>
679std::enable_if_t<std::is_unsigned<T>::value, T>
680SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed = nullptr) {
681  bool Dummy;
682  bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
683 
684  T Product = SaturatingMultiply(X, Y, &Overflowed);
685  if (Overflowed)
686    return Product;
687 
688  return SaturatingAdd(A, Product, &Overflowed);
689}
690 
691/// Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
692extern const float huge_valf;
693 
694 
695/// Add two signed integers, computing the two's complement truncated result,
696/// returning true if overflow occurred.
697template <typename T>
698std::enable_if_t<std::is_signed<T>::value, T> AddOverflow(T X, T Y, T &Result) {
699#if __has_builtin(__builtin_add_overflow)1
700  return __builtin_add_overflow(X, Y, &Result);
701#else
702  // Perform the unsigned addition.
703  using U = std::make_unsigned_t<T>;
704  const U UX = static_cast<U>(X);
705  const U UY = static_cast<U>(Y);
706  const U UResult = UX + UY;
707 
708  // Convert to signed.
709  Result = static_cast<T>(UResult);
710 
711  // Adding two positive numbers should result in a positive number.
712  if (X > 0 && Y > 0)
713    return Result <= 0;
714  // Adding two negatives should result in a negative number.
715  if (X < 0 && Y < 0)
716    return Result >= 0;
717  return false;
718#endif
719}
720 
721/// Subtract two signed integers, computing the two's complement truncated
722/// result, returning true if an overflow ocurred.
723template <typename T>
724std::enable_if_t<std::is_signed<T>::value, T> SubOverflow(T X, T Y, T &Result) {
725#if __has_builtin(__builtin_sub_overflow)1
726  return __builtin_sub_overflow(X, Y, &Result);
727#else
728  // Perform the unsigned addition.
729  using U = std::make_unsigned_t<T>;
730  const U UX = static_cast<U>(X);
731  const U UY = static_cast<U>(Y);
732  const U UResult = UX - UY;
733 
734  // Convert to signed.
735  Result = static_cast<T>(UResult);
736 
737  // Subtracting a positive number from a negative results in a negative number.
738  if (X <= 0 && Y > 0)
739    return Result >= 0;
740  // Subtracting a negative number from a positive results in a positive number.
741  if (X >= 0 && Y < 0)
742    return Result <= 0;
743  return false;
744#endif
745}
746 
747/// Multiply two signed integers, computing the two's complement truncated
748/// result, returning true if an overflow ocurred.
749template <typename T>
750std::enable_if_t<std::is_signed<T>::value, T> MulOverflow(T X, T Y, T &Result) {
751  // Perform the unsigned multiplication on absolute values.
752  using U = std::make_unsigned_t<T>;
753  const U UX = X < 0 ? (0 - static_cast<U>(X)) : static_cast<U>(X);
754  const U UY = Y < 0 ? (0 - static_cast<U>(Y)) : static_cast<U>(Y);
755  const U UResult = UX * UY;
756 
757  // Convert to signed.
758  const bool IsNegative = (X < 0) ^ (Y < 0);
759  Result = IsNegative ? (0 - UResult) : UResult;
760 
761  // If any of the args was 0, result is 0 and no overflow occurs.
762  if (UX == 0 || UY == 0)
763    return false;
764 
765  // UX and UY are in [1, 2^n], where n is the number of digits.
766  // Check how the max allowed absolute value (2^n for negative, 2^(n-1) for
767  // positive) divided by an argument compares to the other.
768  if (IsNegative)
769    return UX > (static_cast<U>(std::numeric_limits<T>::max()) + U(1)) / UY;
770  else
771    return UX > (static_cast<U>(std::numeric_limits<T>::max())) / UY;
772}
773 
774} // End llvm namespace
775 
776#endif

←

/build/source/llvm/include/llvm/ADT/bit.h

1//===-- llvm/ADT/bit.h - C++20 <bit> ----------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// This file implements the C++20 <bit> header.
11///
12//===----------------------------------------------------------------------===//
13 
14#ifndef LLVM_ADT_BIT_H
15#define LLVM_ADT_BIT_H
16 
17#include "llvm/Support/Compiler.h"
18#include <cstdint>
19#include <limits>
20#include <type_traits>
21 
22#if !__has_builtin(__builtin_bit_cast)1
23#include <cstring>
24#endif
25 
26#if defined(_MSC_VER) && !defined(_DEBUG1)
27#include <cstdlib>  // for _byteswap_{ushort,ulong,uint64}
28#endif
29 
30#ifdef _MSC_VER
31// Declare these intrinsics manually rather including intrin.h. It's very
32// expensive, and bit.h is popular via MathExtras.h.
33// #include <intrin.h>
34extern "C" {
35unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask);
36unsigned char _BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask);
37unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask);
38unsigned char _BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask);
39}
40#endif
41 
42namespace llvm {
43 
44// This implementation of bit_cast is different from the C++20 one in two ways:
45//  - It isn't constexpr because that requires compiler support.
46//  - It requires trivially-constructible To, to avoid UB in the implementation.
47template <
48    typename To, typename From,
49    typename = std::enable_if_t<sizeof(To) == sizeof(From)>,
50    typename = std::enable_if_t<std::is_trivially_constructible<To>::value>,
51    typename = std::enable_if_t<std::is_trivially_copyable<To>::value>,
52    typename = std::enable_if_t<std::is_trivially_copyable<From>::value>>
53[[nodiscard]] inline To bit_cast(const From &from) noexcept {
54#if __has_builtin(__builtin_bit_cast)1
55  return __builtin_bit_cast(To, from);
56#else
57  To to;
58  std::memcpy(&to, &from, sizeof(To));
59  return to;
60#endif
61}
62 
63/// Reverses the bytes in the given integer value V.
64template <typename T, typename = std::enable_if_t<std::is_integral_v<T>>>
65[[nodiscard]] constexpr T byteswap(T V) noexcept {
66  if constexpr (sizeof(T) == 1) {
67    return V;
68  } else if constexpr (sizeof(T) == 2) {
69    uint16_t UV = V;
70#if defined(_MSC_VER) && !defined(_DEBUG1)
71    // The DLL version of the runtime lacks these functions (bug!?), but in a
72    // release build they're replaced with BSWAP instructions anyway.
73    return _byteswap_ushort(UV);
74#else
75    uint16_t Hi = UV << 8;
76    uint16_t Lo = UV >> 8;
77    return Hi | Lo;
78#endif
79  } else if constexpr (sizeof(T) == 4) {
80    uint32_t UV = V;
81#if __has_builtin(__builtin_bswap32)1
82    return __builtin_bswap32(UV);
83#elif defined(_MSC_VER) && !defined(_DEBUG1)
84    return _byteswap_ulong(UV);
85#else
86    uint32_t Byte0 = UV & 0x000000FF;
87    uint32_t Byte1 = UV & 0x0000FF00;
88    uint32_t Byte2 = UV & 0x00FF0000;
89    uint32_t Byte3 = UV & 0xFF000000;
90    return (Byte0 << 24) | (Byte1 << 8) | (Byte2 >> 8) | (Byte3 >> 24);
91#endif
92  } else if constexpr (sizeof(T) == 8) {
93    uint64_t UV = V;
94#if __has_builtin(__builtin_bswap64)1
95    return __builtin_bswap64(UV);
96#elif defined(_MSC_VER) && !defined(_DEBUG1)
97    return _byteswap_uint64(UV);
98#else
99    uint64_t Hi = llvm::byteswap<uint32_t>(UV);
100    uint32_t Lo = llvm::byteswap<uint32_t>(UV >> 32);
101    return (Hi << 32) | Lo;
102#endif
103  } else {
104    static_assert(!sizeof(T *), "Don't know how to handle the given type.");
105    return 0;
106  }
107}
108 
109template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
110[[nodiscard]] constexpr inline bool has_single_bit(T Value) noexcept {
111  return (Value != 0) && ((Value & (Value - 1)) == 0);
112}
113 
114namespace detail {
115template <typename T, std::size_t SizeOfT> struct TrailingZerosCounter {
116  static unsigned count(T Val) {
117    if (!Val)
118      return std::numeric_limits<T>::digits;
119    if (Val & 0x1)
120      return 0;
121 
122    // Bisection method.
123    unsigned ZeroBits = 0;
124    T Shift = std::numeric_limits<T>::digits >> 1;
125    T Mask = std::numeric_limits<T>::max() >> Shift;
126    while (Shift) {
127      if ((Val & Mask) == 0) {
128        Val >>= Shift;
129        ZeroBits |= Shift;
130      }
131      Shift >>= 1;
132      Mask >>= Shift;
133    }
134    return ZeroBits;
135  }
136};
137 
138#if defined(__GNUC__4) || defined(_MSC_VER)
139template <typename T> struct TrailingZerosCounter<T, 4> {
140  static unsigned count(T Val) {
141    if (Val == 0)
6
←
Assuming 'Val' is equal to 0→
7
←
Taking true branch→
142      return 32;
8
←
Returning the value 32→
143 
144#if __has_builtin(__builtin_ctz)1 || defined(__GNUC__4)
145    return __builtin_ctz(Val);
146#elif defined(_MSC_VER)
147    unsigned long Index;
148    _BitScanForward(&Index, Val);
149    return Index;
150#endif
151  }
152};
153 
154#if !defined(_MSC_VER) || defined(_M_X64)
155template <typename T> struct TrailingZerosCounter<T, 8> {
156  static unsigned count(T Val) {
157    if (Val == 0)
158      return 64;
159 
160#if __has_builtin(__builtin_ctzll)1 || defined(__GNUC__4)
161    return __builtin_ctzll(Val);
162#elif defined(_MSC_VER)
163    unsigned long Index;
164    _BitScanForward64(&Index, Val);
165    return Index;
166#endif
167  }
168};
169#endif
170#endif
171} // namespace detail
172 
173/// Count number of 0's from the least significant bit to the most
174///   stopping at the first 1.
175///
176/// Only unsigned integral types are allowed.
177///
178/// Returns std::numeric_limits<T>::digits on an input of 0.
179template <typename T> [[nodiscard]] int countr_zero(T Val) {
180  static_assert(std::is_unsigned_v<T>,
181                "Only unsigned integral types are allowed.");
182  return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val);
5
←
Calling 'TrailingZerosCounter::count'→
9
←
Returning from 'TrailingZerosCounter::count'→
10
←
Returning the value 32→
183}
184 
185namespace detail {
186template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter {
187  static unsigned count(T Val) {
188    if (!Val)
189      return std::numeric_limits<T>::digits;
190 
191    // Bisection method.
192    unsigned ZeroBits = 0;
193    for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) {
194      T Tmp = Val >> Shift;
195      if (Tmp)
196        Val = Tmp;
197      else
198        ZeroBits |= Shift;
199    }
200    return ZeroBits;
201  }
202};
203 
204#if defined(__GNUC__4) || defined(_MSC_VER)
205template <typename T> struct LeadingZerosCounter<T, 4> {
206  static unsigned count(T Val) {
207    if (Val == 0)
208      return 32;
209 
210#if __has_builtin(__builtin_clz)1 || defined(__GNUC__4)
211    return __builtin_clz(Val);
212#elif defined(_MSC_VER)
213    unsigned long Index;
214    _BitScanReverse(&Index, Val);
215    return Index ^ 31;
216#endif
217  }
218};
219 
220#if !defined(_MSC_VER) || defined(_M_X64)
221template <typename T> struct LeadingZerosCounter<T, 8> {
222  static unsigned count(T Val) {
223    if (Val == 0)
224      return 64;
225 
226#if __has_builtin(__builtin_clzll)1 || defined(__GNUC__4)
227    return __builtin_clzll(Val);
228#elif defined(_MSC_VER)
229    unsigned long Index;
230    _BitScanReverse64(&Index, Val);
231    return Index ^ 63;
232#endif
233  }
234};
235#endif
236#endif
237} // namespace detail
238 
239/// Count number of 0's from the most significant bit to the least
240///   stopping at the first 1.
241///
242/// Only unsigned integral types are allowed.
243///
244/// Returns std::numeric_limits<T>::digits on an input of 0.
245template <typename T> [[nodiscard]] int countl_zero(T Val) {
246  static_assert(std::is_unsigned_v<T>,
247                "Only unsigned integral types are allowed.");
248  return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val);
249}
250 
251/// Count the number of ones from the most significant bit to the first
252/// zero bit.
253///
254/// Ex. countl_one(0xFF0FFF00) == 8.
255/// Only unsigned integral types are allowed.
256///
257/// Returns std::numeric_limits<T>::digits on an input of all ones.
258template <typename T> [[nodiscard]] int countl_one(T Value) {
259  static_assert(std::is_unsigned_v<T>,
260                "Only unsigned integral types are allowed.");
261  return llvm::countl_zero<T>(~Value);
262}
263 
264/// Count the number of ones from the least significant bit to the first
265/// zero bit.
266///
267/// Ex. countr_one(0x00FF00FF) == 8.
268/// Only unsigned integral types are allowed.
269///
270/// Returns std::numeric_limits<T>::digits on an input of all ones.
271template <typename T> [[nodiscard]] int countr_one(T Value) {
272  static_assert(std::is_unsigned_v<T>,
273                "Only unsigned integral types are allowed.");
274  return llvm::countr_zero<T>(~Value);
275}
276 
277/// Returns the number of bits needed to represent Value if Value is nonzero.
278/// Returns 0 otherwise.
279///
280/// Ex. bit_width(5) == 3.
281template <typename T> [[nodiscard]] int bit_width(T Value) {
282  static_assert(std::is_unsigned_v<T>,
283                "Only unsigned integral types are allowed.");
284  return std::numeric_limits<T>::digits - llvm::countl_zero(Value);
285}
286 
287/// Returns the largest integral power of two no greater than Value if Value is
288/// nonzero.  Returns 0 otherwise.
289///
290/// Ex. bit_floor(5) == 4.
291template <typename T> [[nodiscard]] T bit_floor(T Value) {
292  static_assert(std::is_unsigned_v<T>,
293                "Only unsigned integral types are allowed.");
294  if (!Value)
295    return 0;
296  return T(1) << (llvm::bit_width(Value) - 1);
297}
298 
299/// Returns the smallest integral power of two no smaller than Value if Value is
300/// nonzero.  Returns 0 otherwise.
301///
302/// Ex. bit_ceil(5) == 8.
303///
304/// The return value is undefined if the input is larger than the largest power
305/// of two representable in T.
306template <typename T> [[nodiscard]] T bit_ceil(T Value) {
307  static_assert(std::is_unsigned_v<T>,
308                "Only unsigned integral types are allowed.");
309  if (Value < 2)
310    return 1;
311  return T(1) << llvm::bit_width<T>(Value - 1u);
312}
313 
314namespace detail {
315template <typename T, std::size_t SizeOfT> struct PopulationCounter {
316  static int count(T Value) {
317    // Generic version, forward to 32 bits.
318    static_assert(SizeOfT <= 4, "Not implemented!");
319#if defined(__GNUC__4)
320    return (int)__builtin_popcount(Value);
321#else
322    uint32_t v = Value;
323    v = v - ((v >> 1) & 0x55555555);
324    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
325    return int(((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24);
326#endif
327  }
328};
329 
330template <typename T> struct PopulationCounter<T, 8> {
331  static int count(T Value) {
332#if defined(__GNUC__4)
333    return (int)__builtin_popcountll(Value);
334#else
335    uint64_t v = Value;
336    v = v - ((v >> 1) & 0x5555555555555555ULL);
337    v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
338    v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
339    return int((uint64_t)(v * 0x0101010101010101ULL) >> 56);
340#endif
341  }
342};
343} // namespace detail
344 
345/// Count the number of set bits in a value.
346/// Ex. popcount(0xF000F000) = 8
347/// Returns 0 if the word is zero.
348template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
349[[nodiscard]] inline int popcount(T Value) noexcept {
350  return detail::PopulationCounter<T, sizeof(T)>::count(Value);
351}
352 
353} // namespace llvm
354 
355#endif