/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/lld/MachO/SyntheticSections.cpp

Bug Summary

File:	build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/lld/MachO/SyntheticSections.cpp
Warning:	line 1566, column 13 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/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm -resource-dir /usr/lib/llvm-16/lib/clang/16.0.0 -D LLD_VENDOR="Debian" -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I tools/lld/MachO -I /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/lld/MachO -I /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/lld/include -I tools/lld/include -I include -I /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/llvm/include -I /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/llvm/../libunwind/include -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.0.0/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/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/= -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/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/= -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-2022-10-03-140002-15933-1 -x c++ /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/lld/MachO/SyntheticSections.cpp

/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/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}

114void 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 || in.weakBinding->hasNonWeakDefinition())
  hdr->flags |= MH_WEAK_DEFINES;

if (in.exports->hasWeakSymbol || in.weakBinding->hasEntry())
  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();
}
159}

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

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

167namespace {
168struct RebaseState {
uint64_t sequenceLength;
uint64_t skipLength;
171};
172} // namespace

174static 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", 175, __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);
}
185}

187static 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"
, 188, __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);
}
207}

209// Rebases are communicated to dyld using a bytecode, whose opcodes cause the
210// memory location at a specific address to be rebased and/or the address to be
211// incremented.
212//
213// Opcode REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB is the most generic
214// one, encoding a series of evenly spaced addresses. This algorithm works by
215// splitting up the sorted list of addresses into such chunks. If the locations
216// are consecutive or the sequence consists of a single location, flushRebase
217// will use a smaller, more specialized encoding.
218static 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", 234
, __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", 244, __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);
270}

272void 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);
292}

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

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

304void macho::addNonLazyBindingEntries(const Symbol *sym,
                                   const InputSection *isec, uint64_t offset,
                                   int64_t addend) {
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", 320);
}
322}

324void 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", 326
, __extension__ __PRETTY_FUNCTION__));
  sym->gotIndex = entries.size() - 1;

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

333void NonLazyPointerSectionBase::writeTo(uint8_t *buf) const {
for (size_t i = 0, n = entries.size(); i < n; ++i)
  if (auto *defined = dyn_cast<Defined>(entries[i]))
    write64le(&buf[i * target->wordSize], defined->getVA());
337}

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

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

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

353namespace {
354struct Binding {
OutputSegment *segment = nullptr;
uint64_t offset = 0;
int64_t addend = 0;
358};
359struct 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;
365};
366} // namespace

368// Encode a sequence of opcodes that tell dyld to write the address of symbol +
369// addend at osec->addr + outSecOff.
370//
371// The bind opcode "interpreter" remembers the values of each binding field, so
372// we only need to encode the differences between bindings. Hence the use of
373// lastBinding.
374static 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;
400}

402static 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;
  }
}
460}

462static 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", 487);
}
489}

491// Non-weak bindings need to have their dylib ordinal encoded as well.
492static 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", 495, __extension__ __PRETTY_FUNCTION__
));
return dysym.getFile()->ordinal;
497}

499static 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", 502, __extension__ __PRETTY_FUNCTION__
));
return BIND_SPECIAL_DYLIB_FLAT_LOOKUP;
504}

506static 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);
}
516}

518static 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';
523}

525// Organize the bindings so we can encoded them with fewer opcodes.
526//
527// First, all bindings for a given symbol should be grouped together.
528// BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM is the largest opcode (since it
529// has an associated symbol string), so we only want to emit it once per symbol.
530//
531// Within each group, we sort the bindings by address. Since bindings are
532// delta-encoded, sorting them allows for a more compact result. Note that
533// sorting by address alone ensures that bindings for the same segment / section
534// are located together, minimizing the number of times we have to emit
535// BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB.
536//
537// Finally, we sort the symbols by the address of their first binding, again
538// to facilitate the delta-encoding process.
539template <class Sym>
540std::vector<std::pair<const Sym *, std::vector<BindingEntry>>>
541sortBindings(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;
554}

556// Emit bind opcodes, which are a stream of byte-sized opcodes that dyld
557// interprets to update a record with the following fields:
558//  * segment index (of the segment to write the symbol addresses to, typically
559//    the __DATA_CONST segment which contains the GOT)
560//  * offset within the segment, indicating the next location to write a binding
561//  * symbol type
562//  * symbol library ordinal (the index of its library's LC_LOAD_DYLIB command)
563//  * symbol name
564//  * addend
565// When dyld sees BIND_OPCODE_DO_BIND, it uses the current record state to bind
566// a symbol in the GOT, and increments the segment offset to point to the next
567// entry. It does *not* clear the record state after doing the bind, so
568// subsequent opcodes only need to encode the differences between bindings.
569void 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);
599}

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

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

608void 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);
633}

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

639StubsSection::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;
646}

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

652void StubsSection::writeTo(uint8_t *buf) const {
size_t off = 0;
for (const Symbol *sym : entries) {
  target->writeStub(buf + off, *sym);
  off += target->stubSize;
}
658}

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

662static void addBindingsForStub(Symbol *sym) {
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"
, 681);
  }
} else {
  llvm_unreachable("invalid stub target symbol type")::llvm::llvm_unreachable_internal("invalid stub target symbol type"
, "lld/MachO/SyntheticSections.cpp", 684);
}
686}

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

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

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

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

709void 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;
}
716}

718void 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;
745}

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

753void 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", 754, __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);
766}

768void 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"
, 773, __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;
801}

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

807void 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"
, 808, __extension__ __PRETTY_FUNCTION__));
assert(in.objcSelrefs->isFinal)(static_cast <bool> (in.objcSelrefs->isFinal) ? void
 (0) : __assert_fail ("in.objcSelrefs->isFinal", "lld/MachO/SyntheticSections.cpp"
, 809, __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;
}
819}

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

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

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

835void 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;
}
850}

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

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

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

866void LazyBindingSection::addEntry(Symbol *sym) {
if (entries.insert(sym)) {
  sym->stubsHelperIndex = entries.size() - 1;
  in.rebase->addEntry(in.lazyPointers->isec,
                      sym->stubsIndex * target->wordSize);
}
872}

874// Unlike the non-lazy binding section, the bind opcodes in this section aren't
875// interpreted all at once. Rather, dyld will start interpreting opcodes at a
876// given offset, typically only binding a single symbol before it finds a
877// BIND_OPCODE_DONE terminator. As such, unlike in the non-lazy-binding case,
878// we cannot encode just the differences between symbols; we have to emit the
879// complete bind information for each symbol.
880uint32_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;
898}

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

903void 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();
914}

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

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

921template <class LP>
922static 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", 935, __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", 935, __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", 935, __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", 935, __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;
969}

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

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

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

984void 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';
1011}

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

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

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

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

1033void 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));
1052}

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

1060void 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", 1077, __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", 1077, __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"
, 1080, __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;

    InputSection *isec = defined->isec;
    ObjFile *file = dyn_cast_or_null<ObjFile>(isec->getFile());
    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();
1139}

1141void 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 (Defined *dyldPrivate = in.stubHelper->dyldPrivate)
  localSymbolsHandler(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"
, 1200, __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++;
}
1217}

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

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

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

1237template <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", 1290, __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;
}
1301}

1303template <class LP>
1304SymtabSection *
1305macho::makeSymtabSection(StringTableSection &stringTableSection) {
return make<SymtabSectionImpl<LP>>(stringTableSection);
1307}

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

1313uint32_t IndirectSymtabSection::getNumSymbols() const {
return in.got->getEntries().size() + in.tlvPointers->getEntries().size() +
       2 * in.stubs->getEntries().size();
1316}

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

1323void 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;
off += in.stubs->getEntries().size();
in.lazyPointers->reserved1 = off;
1332}

1334static 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;
1341}

1343void 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;
}
// 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;
}
1366}

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

1371uint32_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;
1376}

1378void 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
}
1384}

1386static_assert((CodeSignatureSection::blobHeadersSize % 8) == 0);
1387static_assert((CodeSignatureSection::fixedHeadersSize % 8) == 0);

1389CodeSignatureSection::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();
1402}

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

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

1412void 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);
});
1421#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);
1433#endif
1434}

1436void 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);
1476}

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

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

1487private:
int errorCode;
1489};

1491#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);

1499void BitcodeBundleSection::finalize() {
1500#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);;

1504#pragma clang diagnostic push
1505#pragma clang diagnostic ignored "-Wdeprecated-declarations"
xar_t xar(xar_open(xarPath.data(), O_RDWR));
1507#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);
1515#endif // defined(LLVM_HAVE_LIBXAR)
1516}

1518void 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);
1532}

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

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

1546void CStringSection::writeTo(uint8_t *buf) const {
for (const CStringInputSection *isec : inputs) {
  for (size_t i = 0, e = isec->pieces.size(); i != e; ++i) {
    if (!isec->pieces[i].live)
      continue;
    StringRef string = isec->getStringRef(i);
    memcpy(buf + isec->pieces[i].outSecOff, string.data(), string.size());
  }
}
1555}

1557void CStringSection::finalizeContents() {
uint64_t offset = 0;
for (CStringInputSection *isec : inputs) {
  for (size_t i = 0, e = isec->pieces.size(); i != e; ++i) {
1
Assuming 'i' is not equal to 'e'→
2
←
Loop condition is true.  Entering loop body→
    if (!isec->pieces[i].live)
3
←
Assuming field 'live' is not equal to 0→
4
←
Taking false branch→
      continue;
    // See comment above DeduplicatedCStringSection for how alignment is
    // handled.
    uint32_t pieceAlign =
        1 << countTrailingZeros(isec->align | isec->pieces[i].inSecOff);
5
←
Calling 'countTrailingZeros<unsigned int>'→
12
←
Returning from 'countTrailingZeros<unsigned int>'→
13
←
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);
    isec->pieces[i].outSecOff = offset;
    isec->isFinal = true;
    StringRef string = isec->getStringRef(i);
    offset += string.size() + 1; // account for null terminator
  }
}
size = offset;
1575}

1577// Mergeable cstring literals are found under the __TEXT,__cstring section. In
1578// contrast to ELF, which puts strings that need different alignments into
1579// different sections, clang's Mach-O backend puts them all in one section.
1580// Strings that need to be aligned have the .p2align directive emitted before
1581// them, which simply translates into zero padding in the object file. In other
1582// words, we have to infer the desired alignment of these cstrings from their
1583// addresses.
1584//
1585// We differ slightly from ld64 in how we've chosen to align these cstrings.
1586// Both LLD and ld64 preserve the number of trailing zeros in each cstring's
1587// address in the input object files. When deduplicating identical cstrings,
1588// both linkers pick the cstring whose address has more trailing zeros, and
1589// preserve the alignment of that address in the final binary. However, ld64
1590// goes a step further and also preserves the offset of the cstring from the
1591// last section-aligned address.  I.e. if a cstring is at offset 18 in the
1592// input, with a section alignment of 16, then both LLD and ld64 will ensure the
1593// final address is 2-byte aligned (since 18 == 16 + 2). But ld64 will also
1594// ensure that the final address is of the form 16 * k + 2 for some k.
1595//
1596// Note that ld64's heuristic means that a dedup'ed cstring's final address is
1597// dependent on the order of the input object files. E.g. if in addition to the
1598// cstring at offset 18 above, we have a duplicate one in another file with a
1599// `.cstring` section alignment of 2 and an offset of zero, then ld64 will pick
1600// the cstring from the object file earlier on the command line (since both have
1601// the same number of trailing zeros in their address). So the final cstring may
1602// either be at some address `16 * k + 2` or at some address `2 * k`.
1603//
1604// I've opted not to follow this behavior primarily for implementation
1605// simplicity, and secondarily to save a few more bytes. It's not clear to me
1606// that preserving the section alignment + offset is ever necessary, and there
1607// are many cases that are clearly redundant. In particular, if an x86_64 object
1608// file contains some strings that are accessed via SIMD instructions, then the
1609// .cstring section in the object file will be 16-byte-aligned (since SIMD
1610// requires its operand addresses to be 16-byte aligned). However, there will
1611// typically also be other cstrings in the same file that aren't used via SIMD
1612// and don't need this alignment. They will be emitted at some arbitrary address
1613// `A`, but ld64 will treat them as being 16-byte aligned with an offset of `16
1614// % A`.
1615void DeduplicatedCStringSection::finalizeContents() {
// Find the largest alignment required for each string.
for (const CStringInputSection *isec : inputs) {
  for (size_t i = 0, e = isec->pieces.size(); i != e; ++i) {
    const StringPiece &piece = isec->pieces[i];
    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", 1623
, __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 (size_t i = 0, e = isec->pieces.size(); i != e; ++i) {
    if (!isec->pieces[i].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"
, 1640, __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
    }
    isec->pieces[i].outSecOff = offsetInfo.outSecOff;
  }
  isec->isFinal = true;
}
1651}

1653void 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());
}
1660}

1662DeduplicatedCStringSection::StringOffset
1663DeduplicatedCStringSection::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", 1668, __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", 1668, __extension__ __PRETTY_FUNCTION__
));
return offset->second;
1670}

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

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

1686void 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", 1721);
  }
}
1724}

1726void 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);
1740}

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

1745ObjCImageInfoSection::ImageInfo
1746ObjCImageInfoSection::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;
1769}

1771static 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();
}
1786}

1788// Validate each object file's __objc_imageinfo and use them to generate the
1789// image info for the output binary. Only two pieces of info are relevant:
1790// 1. The Swift version (should be identical across inputs)
1791// 2. `bool hasCategoryClassProperties` (true only if true for all inputs)
1792void ObjCImageInfoSection::finalizeContents() {
assert(files.size() != 0)(static_cast <bool> (files.size() != 0) ? void (0) : __assert_fail
 ("files.size() != 0", "lld/MachO/SyntheticSections.cpp", 1793
, __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;
  }
}
1814}

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

1822InitOffsetsSection::InitOffsetsSection()
  : SyntheticSection(segment_names::text, section_names::initOffsets) {
flags = S_INIT_FUNC_OFFSETS;
1825}

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

1834void 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", 1839, __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);
}
1854}

1856// The inputs are __mod_init_func sections, which contain pointers to
1857// initializer functions, therefore all relocations should be of the UNSIGNED
1858// type. InitOffsetsSection stores offsets, so if the initializer's address is
1859// not known at link time, stub-indirection has to be used.
1860void 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);
  }
}
1881}

1883void 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"
, 1923);
  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");
1933}

1935template SymtabSection *macho::makeSymtabSection<LP64>(StringTableSection &);
1936template SymtabSection *macho::makeSymtabSection<ILP32>(StringTableSection &);

←

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