Bug Summary

File:build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/lld/MachO/SyntheticSections.cpp
Warning:line 1564, 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

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~++20220904122748+c444af1c20b3/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~++20220904122748+c444af1c20b3/lld/MachO -I /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/lld/include -I tools/lld/include -I include -I /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/include -I /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/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~++20220904122748+c444af1c20b3/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/= -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~++20220904122748+c444af1c20b3/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/= -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-09-04-125545-48738-1 -x c++ /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/lld/MachO/SyntheticSections.cpp

/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/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//===----------------------------------------------------------------------===//
8
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"
18
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"
28
29#if defined(__APPLE__)
30#include <sys/mman.h>
31
32#define COMMON_DIGEST_FOR_OPENSSL
33#include <CommonCrypto/CommonDigest.h>
34#else
35#include "llvm/Support/SHA256.h"
36#endif
37
38#ifdef LLVM_HAVE_LIBXAR
39#include <fcntl.h>
40extern "C" {
41#include <xar/xar.h>
42}
43#endif
44
45using namespace llvm;
46using namespace llvm::MachO;
47using namespace llvm::support;
48using namespace llvm::support::endian;
49using namespace lld;
50using namespace lld::macho;
51
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__)
55 // FIXME: Make LLVM's SHA256 faster and use it unconditionally. See PR56121
56 // for some notes on this.
57 CC_SHA256(data, len, output);
58#else
59 ArrayRef<uint8_t> block(data, len);
60 std::array<uint8_t, 32> hash = SHA256::hash(block);
61 static_assert(hash.size() == CodeSignatureSection::hashSize);
62 memcpy(output, hash.data(), hash.size());
63#endif
64}
65
66InStruct macho::in;
67std::vector<SyntheticSection *> macho::syntheticSections;
68
69SyntheticSection::SyntheticSection(const char *segname, const char *name)
70 : OutputSection(SyntheticKind, name) {
71 std::tie(this->segname, this->name) = maybeRenameSection({segname, name});
72 isec = makeSyntheticInputSection(segname, name);
73 isec->parent = this;
74 syntheticSections.push_back(this);
75}
76
77// dyld3's MachOLoaded::getSlide() assumes that the __TEXT segment starts
78// from the beginning of the file (i.e. the header).
79MachHeaderSection::MachHeaderSection()
80 : SyntheticSection(segment_names::text, section_names::header) {
81 // XXX: This is a hack. (See D97007)
82 // Setting the index to 1 to pretend that this section is the text
83 // section.
84 index = 1;
85 isec->isFinal = true;
86}
87
88void MachHeaderSection::addLoadCommand(LoadCommand *lc) {
89 loadCommands.push_back(lc);
90 sizeOfCmds += lc->getSize();
91}
92
93uint64_t MachHeaderSection::getSize() const {
94 uint64_t size = target->headerSize + sizeOfCmds + config->headerPad;
95 // If we are emitting an encryptable binary, our load commands must have a
96 // separate (non-encrypted) page to themselves.
97 if (config->emitEncryptionInfo)
98 size = alignTo(size, target->getPageSize());
99 return size;
100}
101
102static uint32_t cpuSubtype() {
103 uint32_t subtype = target->cpuSubtype;
104
105 if (config->outputType == MH_EXECUTE && !config->staticLink &&
106 target->cpuSubtype == CPU_SUBTYPE_X86_64_ALL &&
107 config->platform() == PLATFORM_MACOS &&
108 config->platformInfo.minimum >= VersionTuple(10, 5))
109 subtype |= CPU_SUBTYPE_LIB64;
110
111 return subtype;
112}
113
114void MachHeaderSection::writeTo(uint8_t *buf) const {
115 auto *hdr = reinterpret_cast<mach_header *>(buf);
116 hdr->magic = target->magic;
117 hdr->cputype = target->cpuType;
118 hdr->cpusubtype = cpuSubtype();
119 hdr->filetype = config->outputType;
120 hdr->ncmds = loadCommands.size();
121 hdr->sizeofcmds = sizeOfCmds;
122 hdr->flags = MH_DYLDLINK;
123
124 if (config->namespaceKind == NamespaceKind::twolevel)
125 hdr->flags |= MH_NOUNDEFS | MH_TWOLEVEL;
126
127 if (config->outputType == MH_DYLIB && !config->hasReexports)
128 hdr->flags |= MH_NO_REEXPORTED_DYLIBS;
129
130 if (config->markDeadStrippableDylib)
131 hdr->flags |= MH_DEAD_STRIPPABLE_DYLIB;
132
133 if (config->outputType == MH_EXECUTE && config->isPic)
134 hdr->flags |= MH_PIE;
135
136 if (config->outputType == MH_DYLIB && config->applicationExtension)
137 hdr->flags |= MH_APP_EXTENSION_SAFE;
138
139 if (in.exports->hasWeakSymbol || in.weakBinding->hasNonWeakDefinition())
140 hdr->flags |= MH_WEAK_DEFINES;
141
142 if (in.exports->hasWeakSymbol || in.weakBinding->hasEntry())
143 hdr->flags |= MH_BINDS_TO_WEAK;
144
145 for (const OutputSegment *seg : outputSegments) {
146 for (const OutputSection *osec : seg->getSections()) {
147 if (isThreadLocalVariables(osec->flags)) {
148 hdr->flags |= MH_HAS_TLV_DESCRIPTORS;
149 break;
150 }
151 }
152 }
153
154 uint8_t *p = reinterpret_cast<uint8_t *>(hdr) + target->headerSize;
155 for (const LoadCommand *lc : loadCommands) {
156 lc->writeTo(p);
157 p += lc->getSize();
158 }
159}
160
161PageZeroSection::PageZeroSection()
162 : SyntheticSection(segment_names::pageZero, section_names::pageZero) {}
163
164RebaseSection::RebaseSection()
165 : LinkEditSection(segment_names::linkEdit, section_names::rebase) {}
166
167namespace {
168struct RebaseState {
169 uint64_t sequenceLength;
170 uint64_t skipLength;
171};
172} // namespace
173
174static void emitIncrement(uint64_t incr, raw_svector_ostream &os) {
175 assert(incr != 0)(static_cast <bool> (incr != 0) ? void (0) : __assert_fail
("incr != 0", "lld/MachO/SyntheticSections.cpp", 175, __extension__
__PRETTY_FUNCTION__))
;
176
177 if ((incr >> target->p2WordSize) <= REBASE_IMMEDIATE_MASK &&
178 (incr % target->wordSize) == 0) {
179 os << static_cast<uint8_t>(REBASE_OPCODE_ADD_ADDR_IMM_SCALED |
180 (incr >> target->p2WordSize));
181 } else {
182 os << static_cast<uint8_t>(REBASE_OPCODE_ADD_ADDR_ULEB);
183 encodeULEB128(incr, os);
184 }
185}
186
187static void flushRebase(const RebaseState &state, raw_svector_ostream &os) {
188 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__))
;
189
190 if (state.skipLength == target->wordSize) {
191 if (state.sequenceLength <= REBASE_IMMEDIATE_MASK) {
192 os << static_cast<uint8_t>(REBASE_OPCODE_DO_REBASE_IMM_TIMES |
193 state.sequenceLength);
194 } else {
195 os << static_cast<uint8_t>(REBASE_OPCODE_DO_REBASE_ULEB_TIMES);
196 encodeULEB128(state.sequenceLength, os);
197 }
198 } else if (state.sequenceLength == 1) {
199 os << static_cast<uint8_t>(REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB);
200 encodeULEB128(state.skipLength - target->wordSize, os);
201 } else {
202 os << static_cast<uint8_t>(
203 REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB);
204 encodeULEB128(state.sequenceLength, os);
205 encodeULEB128(state.skipLength - target->wordSize, os);
206 }
207}
208
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,
219 MutableArrayRef<Location> locations,
220 raw_svector_ostream &os) {
221 // dyld operates on segments. Translate section offsets into segment offsets.
222 for (Location &loc : locations)
223 loc.offset =
224 loc.isec->parent->getSegmentOffset() + loc.isec->getOffset(loc.offset);
225 // The algorithm assumes that locations are unique.
226 Location *end =
227 llvm::unique(locations, [](const Location &a, const Location &b) {
228 return a.offset == b.offset;
229 });
230 size_t count = end - locations.begin();
231
232 os << static_cast<uint8_t>(REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB |
233 seg->index);
234 assert(!locations.empty())(static_cast <bool> (!locations.empty()) ? void (0) : __assert_fail
("!locations.empty()", "lld/MachO/SyntheticSections.cpp", 234
, __extension__ __PRETTY_FUNCTION__))
;
235 uint64_t offset = locations[0].offset;
236 encodeULEB128(offset, os);
237
238 RebaseState state{1, target->wordSize};
239
240 for (size_t i = 1; i < count; ++i) {
241 offset = locations[i].offset;
242
243 uint64_t skip = offset - locations[i - 1].offset;
244 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__
))
;
245
246 if (skip == state.skipLength) {
247 ++state.sequenceLength;
248 } else if (state.sequenceLength == 1) {
249 ++state.sequenceLength;
250 state.skipLength = skip;
251 } else if (skip < state.skipLength) {
252 // The address is lower than what the rebase pointer would be if the last
253 // location would be part of a sequence. We start a new sequence from the
254 // previous location.
255 --state.sequenceLength;
256 flushRebase(state, os);
257
258 state.sequenceLength = 2;
259 state.skipLength = skip;
260 } else {
261 // The address is at some positive offset from the rebase pointer. We
262 // start a new sequence which begins with the current location.
263 flushRebase(state, os);
264 emitIncrement(skip - state.skipLength, os);
265 state.sequenceLength = 1;
266 state.skipLength = target->wordSize;
267 }
268 }
269 flushRebase(state, os);
270}
271
272void RebaseSection::finalizeContents() {
273 if (locations.empty())
274 return;
275
276 raw_svector_ostream os{contents};
277 os << static_cast<uint8_t>(REBASE_OPCODE_SET_TYPE_IMM | REBASE_TYPE_POINTER);
278
279 llvm::sort(locations, [](const Location &a, const Location &b) {
280 return a.isec->getVA(a.offset) < b.isec->getVA(b.offset);
281 });
282
283 for (size_t i = 0, count = locations.size(); i < count;) {
284 const OutputSegment *seg = locations[i].isec->parent->parent;
285 size_t j = i + 1;
286 while (j < count && locations[j].isec->parent->parent == seg)
287 ++j;
288 encodeRebases(seg, {locations.data() + i, locations.data() + j}, os);
289 i = j;
290 }
291 os << static_cast<uint8_t>(REBASE_OPCODE_DONE);
292}
293
294void RebaseSection::writeTo(uint8_t *buf) const {
295 memcpy(buf, contents.data(), contents.size());
296}
297
298NonLazyPointerSectionBase::NonLazyPointerSectionBase(const char *segname,
299 const char *name)
300 : SyntheticSection(segname, name) {
301 align = target->wordSize;
302}
303
304void macho::addNonLazyBindingEntries(const Symbol *sym,
305 const InputSection *isec, uint64_t offset,
306 int64_t addend) {
307 if (const auto *dysym = dyn_cast<DylibSymbol>(sym)) {
308 in.binding->addEntry(dysym, isec, offset, addend);
309 if (dysym->isWeakDef())
310 in.weakBinding->addEntry(sym, isec, offset, addend);
311 } else if (const auto *defined = dyn_cast<Defined>(sym)) {
312 in.rebase->addEntry(isec, offset);
313 if (defined->isExternalWeakDef())
314 in.weakBinding->addEntry(sym, isec, offset, addend);
315 else if (defined->interposable)
316 in.binding->addEntry(sym, isec, offset, addend);
317 } else {
318 // Undefined symbols are filtered out in scanRelocations(); we should never
319 // get here
320 llvm_unreachable("cannot bind to an undefined symbol")::llvm::llvm_unreachable_internal("cannot bind to an undefined symbol"
, "lld/MachO/SyntheticSections.cpp", 320)
;
321 }
322}
323
324void NonLazyPointerSectionBase::addEntry(Symbol *sym) {
325 if (entries.insert(sym)) {
326 assert(!sym->isInGot())(static_cast <bool> (!sym->isInGot()) ? void (0) : __assert_fail
("!sym->isInGot()", "lld/MachO/SyntheticSections.cpp", 326
, __extension__ __PRETTY_FUNCTION__))
;
327 sym->gotIndex = entries.size() - 1;
328
329 addNonLazyBindingEntries(sym, isec, sym->gotIndex * target->wordSize);
330 }
331}
332
333void NonLazyPointerSectionBase::writeTo(uint8_t *buf) const {
334 for (size_t i = 0, n = entries.size(); i < n; ++i)
335 if (auto *defined = dyn_cast<Defined>(entries[i]))
336 write64le(&buf[i * target->wordSize], defined->getVA());
337}
338
339GotSection::GotSection()
340 : NonLazyPointerSectionBase(segment_names::data, section_names::got) {
341 flags = S_NON_LAZY_SYMBOL_POINTERS;
342}
343
344TlvPointerSection::TlvPointerSection()
345 : NonLazyPointerSectionBase(segment_names::data,
346 section_names::threadPtrs) {
347 flags = S_THREAD_LOCAL_VARIABLE_POINTERS;
348}
349
350BindingSection::BindingSection()
351 : LinkEditSection(segment_names::linkEdit, section_names::binding) {}
352
353namespace {
354struct Binding {
355 OutputSegment *segment = nullptr;
356 uint64_t offset = 0;
357 int64_t addend = 0;
358};
359struct BindIR {
360 // Default value of 0xF0 is not valid opcode and should make the program
361 // scream instead of accidentally writing "valid" values.
362 uint8_t opcode = 0xF0;
363 uint64_t data = 0;
364 uint64_t consecutiveCount = 0;
365};
366} // namespace
367
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,
375 int64_t addend, Binding &lastBinding,
376 std::vector<BindIR> &opcodes) {
377 OutputSegment *seg = osec->parent;
378 uint64_t offset = osec->getSegmentOffset() + outSecOff;
379 if (lastBinding.segment != seg) {
380 opcodes.push_back(
381 {static_cast<uint8_t>(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB |
382 seg->index),
383 offset});
384 lastBinding.segment = seg;
385 lastBinding.offset = offset;
386 } else if (lastBinding.offset != offset) {
387 opcodes.push_back({BIND_OPCODE_ADD_ADDR_ULEB, offset - lastBinding.offset});
388 lastBinding.offset = offset;
389 }
390
391 if (lastBinding.addend != addend) {
392 opcodes.push_back(
393 {BIND_OPCODE_SET_ADDEND_SLEB, static_cast<uint64_t>(addend)});
394 lastBinding.addend = addend;
395 }
396
397 opcodes.push_back({BIND_OPCODE_DO_BIND, 0});
398 // DO_BIND causes dyld to both perform the binding and increment the offset
399 lastBinding.offset += target->wordSize;
400}
401
402static void optimizeOpcodes(std::vector<BindIR> &opcodes) {
403 // Pass 1: Combine bind/add pairs
404 size_t i;
405 int pWrite = 0;
406 for (i = 1; i < opcodes.size(); ++i, ++pWrite) {
407 if ((opcodes[i].opcode == BIND_OPCODE_ADD_ADDR_ULEB) &&
408 (opcodes[i - 1].opcode == BIND_OPCODE_DO_BIND)) {
409 opcodes[pWrite].opcode = BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB;
410 opcodes[pWrite].data = opcodes[i].data;
411 ++i;
412 } else {
413 opcodes[pWrite] = opcodes[i - 1];
414 }
415 }
416 if (i == opcodes.size())
417 opcodes[pWrite] = opcodes[i - 1];
418 opcodes.resize(pWrite + 1);
419
420 // Pass 2: Compress two or more bind_add opcodes
421 pWrite = 0;
422 for (i = 1; i < opcodes.size(); ++i, ++pWrite) {
423 if ((opcodes[i].opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB) &&
424 (opcodes[i - 1].opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB) &&
425 (opcodes[i].data == opcodes[i - 1].data)) {
426 opcodes[pWrite].opcode = BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB;
427 opcodes[pWrite].consecutiveCount = 2;
428 opcodes[pWrite].data = opcodes[i].data;
429 ++i;
430 while (i < opcodes.size() &&
431 (opcodes[i].opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB) &&
432 (opcodes[i].data == opcodes[i - 1].data)) {
433 opcodes[pWrite].consecutiveCount++;
434 ++i;
435 }
436 } else {
437 opcodes[pWrite] = opcodes[i - 1];
438 }
439 }
440 if (i == opcodes.size())
441 opcodes[pWrite] = opcodes[i - 1];
442 opcodes.resize(pWrite + 1);
443
444 // Pass 3: Use immediate encodings
445 // Every binding is the size of one pointer. If the next binding is a
446 // multiple of wordSize away that is within BIND_IMMEDIATE_MASK, the
447 // opcode can be scaled by wordSize into a single byte and dyld will
448 // expand it to the correct address.
449 for (auto &p : opcodes) {
450 // It's unclear why the check needs to be less than BIND_IMMEDIATE_MASK,
451 // but ld64 currently does this. This could be a potential bug, but
452 // for now, perform the same behavior to prevent mysterious bugs.
453 if ((p.opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB) &&
454 ((p.data / target->wordSize) < BIND_IMMEDIATE_MASK) &&
455 ((p.data % target->wordSize) == 0)) {
456 p.opcode = BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED;
457 p.data /= target->wordSize;
458 }
459 }
460}
461
462static void flushOpcodes(const BindIR &op, raw_svector_ostream &os) {
463 uint8_t opcode = op.opcode & BIND_OPCODE_MASK;
464 switch (opcode) {
465 case BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB:
466 case BIND_OPCODE_ADD_ADDR_ULEB:
467 case BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB:
468 os << op.opcode;
469 encodeULEB128(op.data, os);
470 break;
471 case BIND_OPCODE_SET_ADDEND_SLEB:
472 os << op.opcode;
473 encodeSLEB128(static_cast<int64_t>(op.data), os);
474 break;
475 case BIND_OPCODE_DO_BIND:
476 os << op.opcode;
477 break;
478 case BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB:
479 os << op.opcode;
480 encodeULEB128(op.consecutiveCount, os);
481 encodeULEB128(op.data, os);
482 break;
483 case BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED:
484 os << static_cast<uint8_t>(op.opcode | op.data);
485 break;
486 default:
487 llvm_unreachable("cannot bind to an unrecognized symbol")::llvm::llvm_unreachable_internal("cannot bind to an unrecognized symbol"
, "lld/MachO/SyntheticSections.cpp", 487)
;
488 }
489}
490
491// Non-weak bindings need to have their dylib ordinal encoded as well.
492static int16_t ordinalForDylibSymbol(const DylibSymbol &dysym) {
493 if (config->namespaceKind == NamespaceKind::flat || dysym.isDynamicLookup())
494 return static_cast<int16_t>(BIND_SPECIAL_DYLIB_FLAT_LOOKUP);
495 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__
))
;
496 return dysym.getFile()->ordinal;
497}
498
499static int16_t ordinalForSymbol(const Symbol &sym) {
500 if (const auto *dysym = dyn_cast<DylibSymbol>(&sym))
501 return ordinalForDylibSymbol(*dysym);
502 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__
))
;
503 return BIND_SPECIAL_DYLIB_FLAT_LOOKUP;
504}
505
506static void encodeDylibOrdinal(int16_t ordinal, raw_svector_ostream &os) {
507 if (ordinal <= 0) {
508 os << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_SPECIAL_IMM |
509 (ordinal & BIND_IMMEDIATE_MASK));
510 } else if (ordinal <= BIND_IMMEDIATE_MASK) {
511 os << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_ORDINAL_IMM | ordinal);
512 } else {
513 os << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB);
514 encodeULEB128(ordinal, os);
515 }
516}
517
518static void encodeWeakOverride(const Defined *defined,
519 raw_svector_ostream &os) {
520 os << static_cast<uint8_t>(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM |
521 BIND_SYMBOL_FLAGS_NON_WEAK_DEFINITION)
522 << defined->getName() << '\0';
523}
524
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) {
542 std::vector<std::pair<const Sym *, std::vector<BindingEntry>>> bindingsVec(
543 bindingsMap.begin(), bindingsMap.end());
544 for (auto &p : bindingsVec) {
545 std::vector<BindingEntry> &bindings = p.second;
546 llvm::sort(bindings, [](const BindingEntry &a, const BindingEntry &b) {
547 return a.target.getVA() < b.target.getVA();
548 });
549 }
550 llvm::sort(bindingsVec, [](const auto &a, const auto &b) {
551 return a.second[0].target.getVA() < b.second[0].target.getVA();
552 });
553 return bindingsVec;
554}
555
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() {
570 raw_svector_ostream os{contents};
571 Binding lastBinding;
572 int16_t lastOrdinal = 0;
573
574 for (auto &p : sortBindings(bindingsMap)) {
575 const Symbol *sym = p.first;
576 std::vector<BindingEntry> &bindings = p.second;
577 uint8_t flags = BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM;
578 if (sym->isWeakRef())
579 flags |= BIND_SYMBOL_FLAGS_WEAK_IMPORT;
580 os << flags << sym->getName() << '\0'
581 << static_cast<uint8_t>(BIND_OPCODE_SET_TYPE_IMM | BIND_TYPE_POINTER);
582 int16_t ordinal = ordinalForSymbol(*sym);
583 if (ordinal != lastOrdinal) {
584 encodeDylibOrdinal(ordinal, os);
585 lastOrdinal = ordinal;
586 }
587 std::vector<BindIR> opcodes;
588 for (const BindingEntry &b : bindings)
589 encodeBinding(b.target.isec->parent,
590 b.target.isec->getOffset(b.target.offset), b.addend,
591 lastBinding, opcodes);
592 if (config->optimize > 1)
593 optimizeOpcodes(opcodes);
594 for (const auto &op : opcodes)
595 flushOpcodes(op, os);
596 }
597 if (!bindingsMap.empty())
598 os << static_cast<uint8_t>(BIND_OPCODE_DONE);
599}
600
601void BindingSection::writeTo(uint8_t *buf) const {
602 memcpy(buf, contents.data(), contents.size());
603}
604
605WeakBindingSection::WeakBindingSection()
606 : LinkEditSection(segment_names::linkEdit, section_names::weakBinding) {}
607
608void WeakBindingSection::finalizeContents() {
609 raw_svector_ostream os{contents};
610 Binding lastBinding;
611
612 for (const Defined *defined : definitions)
613 encodeWeakOverride(defined, os);
614
615 for (auto &p : sortBindings(bindingsMap)) {
616 const Symbol *sym = p.first;
617 std::vector<BindingEntry> &bindings = p.second;
618 os << static_cast<uint8_t>(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM)
619 << sym->getName() << '\0'
620 << static_cast<uint8_t>(BIND_OPCODE_SET_TYPE_IMM | BIND_TYPE_POINTER);
621 std::vector<BindIR> opcodes;
622 for (const BindingEntry &b : bindings)
623 encodeBinding(b.target.isec->parent,
624 b.target.isec->getOffset(b.target.offset), b.addend,
625 lastBinding, opcodes);
626 if (config->optimize > 1)
627 optimizeOpcodes(opcodes);
628 for (const auto &op : opcodes)
629 flushOpcodes(op, os);
630 }
631 if (!bindingsMap.empty() || !definitions.empty())
632 os << static_cast<uint8_t>(BIND_OPCODE_DONE);
633}
634
635void WeakBindingSection::writeTo(uint8_t *buf) const {
636 memcpy(buf, contents.data(), contents.size());
637}
638
639StubsSection::StubsSection()
640 : SyntheticSection(segment_names::text, section_names::stubs) {
641 flags = S_SYMBOL_STUBS | S_ATTR_SOME_INSTRUCTIONS | S_ATTR_PURE_INSTRUCTIONS;
642 // The stubs section comprises machine instructions, which are aligned to
643 // 4 bytes on the archs we care about.
644 align = 4;
645 reserved2 = target->stubSize;
646}
647
648uint64_t StubsSection::getSize() const {
649 return entries.size() * target->stubSize;
650}
651
652void StubsSection::writeTo(uint8_t *buf) const {
653 size_t off = 0;
654 for (const Symbol *sym : entries) {
655 target->writeStub(buf + off, *sym);
656 off += target->stubSize;
657 }
658}
659
660void StubsSection::finalize() { isFinal = true; }
661
662static void addBindingsForStub(Symbol *sym) {
663 if (auto *dysym = dyn_cast<DylibSymbol>(sym)) {
664 if (sym->isWeakDef()) {
665 in.binding->addEntry(dysym, in.lazyPointers->isec,
666 sym->stubsIndex * target->wordSize);
667 in.weakBinding->addEntry(sym, in.lazyPointers->isec,
668 sym->stubsIndex * target->wordSize);
669 } else {
670 in.lazyBinding->addEntry(dysym);
671 }
672 } else if (auto *defined = dyn_cast<Defined>(sym)) {
673 if (defined->isExternalWeakDef()) {
674 in.rebase->addEntry(in.lazyPointers->isec,
675 sym->stubsIndex * target->wordSize);
676 in.weakBinding->addEntry(sym, in.lazyPointers->isec,
677 sym->stubsIndex * target->wordSize);
678 } else if (defined->interposable) {
679 in.lazyBinding->addEntry(sym);
680 } else {
681 llvm_unreachable("invalid stub target")::llvm::llvm_unreachable_internal("invalid stub target", "lld/MachO/SyntheticSections.cpp"
, 681)
;
682 }
683 } else {
684 llvm_unreachable("invalid stub target symbol type")::llvm::llvm_unreachable_internal("invalid stub target symbol type"
, "lld/MachO/SyntheticSections.cpp", 684)
;
685 }
686}
687
688void StubsSection::addEntry(Symbol *sym) {
689 bool inserted = entries.insert(sym);
690 if (inserted) {
691 sym->stubsIndex = entries.size() - 1;
692 addBindingsForStub(sym);
693 }
694}
695
696StubHelperSection::StubHelperSection()
697 : SyntheticSection(segment_names::text, section_names::stubHelper) {
698 flags = S_ATTR_SOME_INSTRUCTIONS | S_ATTR_PURE_INSTRUCTIONS;
699 align = 4; // This section comprises machine instructions
700}
701
702uint64_t StubHelperSection::getSize() const {
703 return target->stubHelperHeaderSize +
704 in.lazyBinding->getEntries().size() * target->stubHelperEntrySize;
705}
706
707bool StubHelperSection::isNeeded() const { return in.lazyBinding->isNeeded(); }
708
709void StubHelperSection::writeTo(uint8_t *buf) const {
710 target->writeStubHelperHeader(buf);
711 size_t off = target->stubHelperHeaderSize;
712 for (const Symbol *sym : in.lazyBinding->getEntries()) {
713 target->writeStubHelperEntry(buf + off, *sym, addr + off);
714 off += target->stubHelperEntrySize;
715 }
716}
717
718void StubHelperSection::setUp() {
719 Symbol *binder = symtab->addUndefined("dyld_stub_binder", /*file=*/nullptr,
720 /*isWeakRef=*/false);
721 if (auto *undefined = dyn_cast<Undefined>(binder))
722 treatUndefinedSymbol(*undefined,
723 "lazy binding (normally in libSystem.dylib)");
724
725 // treatUndefinedSymbol() can replace binder with a DylibSymbol; re-check.
726 stubBinder = dyn_cast_or_null<DylibSymbol>(binder);
727 if (stubBinder == nullptr)
728 return;
729
730 in.got->addEntry(stubBinder);
731
732 in.imageLoaderCache->parent =
733 ConcatOutputSection::getOrCreateForInput(in.imageLoaderCache);
734 inputSections.push_back(in.imageLoaderCache);
735 // Since this isn't in the symbol table or in any input file, the noDeadStrip
736 // argument doesn't matter.
737 dyldPrivate =
738 make<Defined>("__dyld_private", nullptr, in.imageLoaderCache, 0, 0,
739 /*isWeakDef=*/false,
740 /*isExternal=*/false, /*isPrivateExtern=*/false,
741 /*includeInSymtab=*/true,
742 /*isThumb=*/false, /*isReferencedDynamically=*/false,
743 /*noDeadStrip=*/false);
744 dyldPrivate->used = true;
745}
746
747ObjCStubsSection::ObjCStubsSection()
748 : SyntheticSection(segment_names::text, section_names::objcStubs) {
749 flags = S_ATTR_SOME_INSTRUCTIONS | S_ATTR_PURE_INSTRUCTIONS;
750 align = target->objcStubsAlignment;
751}
752
753void ObjCStubsSection::addEntry(Symbol *sym) {
754 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__
))
;
755 // Ensure our lookup string has the length of the actual string + the null
756 // terminator to mirror
757 StringRef methname =
758 StringRef(sym->getName().data() + symbolPrefix.size(),
759 sym->getName().size() - symbolPrefix.size() + 1);
760 offsets.push_back(
761 in.objcMethnameSection->getStringOffset(methname).outSecOff);
762 Defined *newSym = replaceSymbol<Defined>(
763 sym, sym->getName(), nullptr, isec,
764 /*value=*/symbols.size() * target->objcStubsFastSize,
765 /*size=*/target->objcStubsFastSize,
766 /*isWeakDef=*/false, /*isExternal=*/true, /*isPrivateExtern=*/true,
767 /*includeInSymtab=*/true, /*isThumb=*/false,
768 /*isReferencedDynamically=*/false, /*noDeadStrip=*/false);
769 symbols.push_back(newSym);
770}
771
772void ObjCStubsSection::setUp() {
773 Symbol *objcMsgSend = symtab->addUndefined("_objc_msgSend", /*file=*/nullptr,
774 /*isWeakRef=*/false);
775 objcMsgSend->used = true;
776 in.got->addEntry(objcMsgSend);
777 assert(objcMsgSend->isInGot())(static_cast <bool> (objcMsgSend->isInGot()) ? void (
0) : __assert_fail ("objcMsgSend->isInGot()", "lld/MachO/SyntheticSections.cpp"
, 777, __extension__ __PRETTY_FUNCTION__))
;
778 objcMsgSendGotIndex = objcMsgSend->gotIndex;
779
780 size_t size = offsets.size() * target->wordSize;
781 uint8_t *selrefsData = bAlloc().Allocate<uint8_t>(size);
782 for (size_t i = 0, n = offsets.size(); i < n; ++i)
783 write64le(&selrefsData[i * target->wordSize], offsets[i]);
784
785 in.objcSelrefs =
786 makeSyntheticInputSection(segment_names::data, section_names::objcSelrefs,
787 S_LITERAL_POINTERS | S_ATTR_NO_DEAD_STRIP,
788 ArrayRef<uint8_t>{selrefsData, size},
789 /*align=*/target->wordSize);
790 in.objcSelrefs->live = true;
791
792 for (size_t i = 0, n = offsets.size(); i < n; ++i) {
793 in.objcSelrefs->relocs.push_back(
794 {/*type=*/target->unsignedRelocType,
795 /*pcrel=*/false, /*length=*/3,
796 /*offset=*/static_cast<uint32_t>(i * target->wordSize),
797 /*addend=*/offsets[i] * in.objcMethnameSection->align,
798 /*referent=*/in.objcMethnameSection->isec});
799 }
800
801 in.objcSelrefs->parent =
802 ConcatOutputSection::getOrCreateForInput(in.objcSelrefs);
803 inputSections.push_back(in.objcSelrefs);
804 in.objcSelrefs->isFinal = true;
805}
806
807uint64_t ObjCStubsSection::getSize() const {
808 return target->objcStubsFastSize * symbols.size();
809}
810
811void ObjCStubsSection::writeTo(uint8_t *buf) const {
812 assert(in.objcSelrefs->live)(static_cast <bool> (in.objcSelrefs->live) ? void (0
) : __assert_fail ("in.objcSelrefs->live", "lld/MachO/SyntheticSections.cpp"
, 812, __extension__ __PRETTY_FUNCTION__))
;
813 assert(in.objcSelrefs->isFinal)(static_cast <bool> (in.objcSelrefs->isFinal) ? void
(0) : __assert_fail ("in.objcSelrefs->isFinal", "lld/MachO/SyntheticSections.cpp"
, 813, __extension__ __PRETTY_FUNCTION__))
;
814
815 uint64_t stubOffset = 0;
816 for (size_t i = 0, n = symbols.size(); i < n; ++i) {
817 Defined *sym = symbols[i];
818 target->writeObjCMsgSendStub(buf + stubOffset, sym, in.objcStubs->addr,
819 stubOffset, in.objcSelrefs->getVA(), i,
820 in.got->addr, objcMsgSendGotIndex);
821 stubOffset += target->objcStubsFastSize;
822 }
823}
824
825LazyPointerSection::LazyPointerSection()
826 : SyntheticSection(segment_names::data, section_names::lazySymbolPtr) {
827 align = target->wordSize;
828 flags = S_LAZY_SYMBOL_POINTERS;
829}
830
831uint64_t LazyPointerSection::getSize() const {
832 return in.stubs->getEntries().size() * target->wordSize;
833}
834
835bool LazyPointerSection::isNeeded() const {
836 return !in.stubs->getEntries().empty();
837}
838
839void LazyPointerSection::writeTo(uint8_t *buf) const {
840 size_t off = 0;
841 for (const Symbol *sym : in.stubs->getEntries()) {
842 if (const auto *dysym = dyn_cast<DylibSymbol>(sym)) {
843 if (dysym->hasStubsHelper()) {
844 uint64_t stubHelperOffset =
845 target->stubHelperHeaderSize +
846 dysym->stubsHelperIndex * target->stubHelperEntrySize;
847 write64le(buf + off, in.stubHelper->addr + stubHelperOffset);
848 }
849 } else {
850 write64le(buf + off, sym->getVA());
851 }
852 off += target->wordSize;
853 }
854}
855
856LazyBindingSection::LazyBindingSection()
857 : LinkEditSection(segment_names::linkEdit, section_names::lazyBinding) {}
858
859void LazyBindingSection::finalizeContents() {
860 // TODO: Just precompute output size here instead of writing to a temporary
861 // buffer
862 for (Symbol *sym : entries)
863 sym->lazyBindOffset = encode(*sym);
864}
865
866void LazyBindingSection::writeTo(uint8_t *buf) const {
867 memcpy(buf, contents.data(), contents.size());
868}
869
870void LazyBindingSection::addEntry(Symbol *sym) {
871 if (entries.insert(sym)) {
872 sym->stubsHelperIndex = entries.size() - 1;
873 in.rebase->addEntry(in.lazyPointers->isec,
874 sym->stubsIndex * target->wordSize);
875 }
876}
877
878// Unlike the non-lazy binding section, the bind opcodes in this section aren't
879// interpreted all at once. Rather, dyld will start interpreting opcodes at a
880// given offset, typically only binding a single symbol before it finds a
881// BIND_OPCODE_DONE terminator. As such, unlike in the non-lazy-binding case,
882// we cannot encode just the differences between symbols; we have to emit the
883// complete bind information for each symbol.
884uint32_t LazyBindingSection::encode(const Symbol &sym) {
885 uint32_t opstreamOffset = contents.size();
886 OutputSegment *dataSeg = in.lazyPointers->parent;
887 os << static_cast<uint8_t>(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB |
888 dataSeg->index);
889 uint64_t offset =
890 in.lazyPointers->addr - dataSeg->addr + sym.stubsIndex * target->wordSize;
891 encodeULEB128(offset, os);
892 encodeDylibOrdinal(ordinalForSymbol(sym), os);
893
894 uint8_t flags = BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM;
895 if (sym.isWeakRef())
896 flags |= BIND_SYMBOL_FLAGS_WEAK_IMPORT;
897
898 os << flags << sym.getName() << '\0'
899 << static_cast<uint8_t>(BIND_OPCODE_DO_BIND)
900 << static_cast<uint8_t>(BIND_OPCODE_DONE);
901 return opstreamOffset;
902}
903
904ExportSection::ExportSection()
905 : LinkEditSection(segment_names::linkEdit, section_names::export_) {}
906
907void ExportSection::finalizeContents() {
908 trieBuilder.setImageBase(in.header->addr);
909 for (const Symbol *sym : symtab->getSymbols()) {
910 if (const auto *defined = dyn_cast<Defined>(sym)) {
911 if (defined->privateExtern || !defined->isLive())
912 continue;
913 trieBuilder.addSymbol(*defined);
914 hasWeakSymbol = hasWeakSymbol || sym->isWeakDef();
915 }
916 }
917 size = trieBuilder.build();
918}
919
920void ExportSection::writeTo(uint8_t *buf) const { trieBuilder.writeTo(buf); }
921
922DataInCodeSection::DataInCodeSection()
923 : LinkEditSection(segment_names::linkEdit, section_names::dataInCode) {}
924
925template <class LP>
926static std::vector<MachO::data_in_code_entry> collectDataInCodeEntries() {
927 std::vector<MachO::data_in_code_entry> dataInCodeEntries;
928 for (const InputFile *inputFile : inputFiles) {
929 if (!isa<ObjFile>(inputFile))
930 continue;
931 const ObjFile *objFile = cast<ObjFile>(inputFile);
932 ArrayRef<MachO::data_in_code_entry> entries = objFile->getDataInCode();
933 if (entries.empty())
934 continue;
935
936 assert(is_sorted(dataInCodeEntries, [](const data_in_code_entry &lhs,(static_cast <bool> (is_sorted(dataInCodeEntries, [](const
data_in_code_entry &lhs, const data_in_code_entry &rhs
) { return lhs.offset < rhs.offset; })) ? void (0) : __assert_fail
("is_sorted(dataInCodeEntries, [](const data_in_code_entry &lhs, const data_in_code_entry &rhs) { return lhs.offset < rhs.offset; })"
, "lld/MachO/SyntheticSections.cpp", 939, __extension__ __PRETTY_FUNCTION__
))
937 const data_in_code_entry &rhs) {(static_cast <bool> (is_sorted(dataInCodeEntries, [](const
data_in_code_entry &lhs, const data_in_code_entry &rhs
) { return lhs.offset < rhs.offset; })) ? void (0) : __assert_fail
("is_sorted(dataInCodeEntries, [](const data_in_code_entry &lhs, const data_in_code_entry &rhs) { return lhs.offset < rhs.offset; })"
, "lld/MachO/SyntheticSections.cpp", 939, __extension__ __PRETTY_FUNCTION__
))
938 return lhs.offset < rhs.offset;(static_cast <bool> (is_sorted(dataInCodeEntries, [](const
data_in_code_entry &lhs, const data_in_code_entry &rhs
) { return lhs.offset < rhs.offset; })) ? void (0) : __assert_fail
("is_sorted(dataInCodeEntries, [](const data_in_code_entry &lhs, const data_in_code_entry &rhs) { return lhs.offset < rhs.offset; })"
, "lld/MachO/SyntheticSections.cpp", 939, __extension__ __PRETTY_FUNCTION__
))
939 }))(static_cast <bool> (is_sorted(dataInCodeEntries, [](const
data_in_code_entry &lhs, const data_in_code_entry &rhs
) { return lhs.offset < rhs.offset; })) ? void (0) : __assert_fail
("is_sorted(dataInCodeEntries, [](const data_in_code_entry &lhs, const data_in_code_entry &rhs) { return lhs.offset < rhs.offset; })"
, "lld/MachO/SyntheticSections.cpp", 939, __extension__ __PRETTY_FUNCTION__
))
;
940 // For each code subsection find 'data in code' entries residing in it.
941 // Compute the new offset values as
942 // <offset within subsection> + <subsection address> - <__TEXT address>.
943 for (const Section *section : objFile->sections) {
944 for (const Subsection &subsec : section->subsections) {
945 const InputSection *isec = subsec.isec;
946 if (!isCodeSection(isec))
947 continue;
948 if (cast<ConcatInputSection>(isec)->shouldOmitFromOutput())
949 continue;
950 const uint64_t beginAddr = section->addr + subsec.offset;
951 auto it = llvm::lower_bound(
952 entries, beginAddr,
953 [](const MachO::data_in_code_entry &entry, uint64_t addr) {
954 return entry.offset < addr;
955 });
956 const uint64_t endAddr = beginAddr + isec->getSize();
957 for (const auto end = entries.end();
958 it != end && it->offset + it->length <= endAddr; ++it)
959 dataInCodeEntries.push_back(
960 {static_cast<uint32_t>(isec->getVA(it->offset - beginAddr) -
961 in.header->addr),
962 it->length, it->kind});
963 }
964 }
965 }
966 return dataInCodeEntries;
967}
968
969void DataInCodeSection::finalizeContents() {
970 entries = target->wordSize == 8 ? collectDataInCodeEntries<LP64>()
971 : collectDataInCodeEntries<ILP32>();
972}
973
974void DataInCodeSection::writeTo(uint8_t *buf) const {
975 if (!entries.empty())
976 memcpy(buf, entries.data(), getRawSize());
977}
978
979FunctionStartsSection::FunctionStartsSection()
980 : LinkEditSection(segment_names::linkEdit, section_names::functionStarts) {}
981
982void FunctionStartsSection::finalizeContents() {
983 raw_svector_ostream os{contents};
984 std::vector<uint64_t> addrs;
985 for (const InputFile *file : inputFiles) {
986 if (auto *objFile = dyn_cast<ObjFile>(file)) {
987 for (const Symbol *sym : objFile->symbols) {
988 if (const auto *defined = dyn_cast_or_null<Defined>(sym)) {
989 if (!defined->isec || !isCodeSection(defined->isec) ||
990 !defined->isLive())
991 continue;
992 // TODO: Add support for thumbs, in that case
993 // the lowest bit of nextAddr needs to be set to 1.
994 addrs.push_back(defined->getVA());
995 }
996 }
997 }
998 }
999 llvm::sort(addrs);
1000 uint64_t addr = in.header->addr;
1001 for (uint64_t nextAddr : addrs) {
1002 uint64_t delta = nextAddr - addr;
1003 if (delta == 0)
1004 continue;
1005 encodeULEB128(delta, os);
1006 addr = nextAddr;
1007 }
1008 os << '\0';
1009}
1010
1011void FunctionStartsSection::writeTo(uint8_t *buf) const {
1012 memcpy(buf, contents.data(), contents.size());
1013}
1014
1015SymtabSection::SymtabSection(StringTableSection &stringTableSection)
1016 : LinkEditSection(segment_names::linkEdit, section_names::symbolTable),
1017 stringTableSection(stringTableSection) {}
1018
1019void SymtabSection::emitBeginSourceStab(StringRef sourceFile) {
1020 StabsEntry stab(N_SO);
1021 stab.strx = stringTableSection.addString(saver().save(sourceFile));
1022 stabs.emplace_back(std::move(stab));
1023}
1024
1025void SymtabSection::emitEndSourceStab() {
1026 StabsEntry stab(N_SO);
1027 stab.sect = 1;
1028 stabs.emplace_back(std::move(stab));
1029}
1030
1031void SymtabSection::emitObjectFileStab(ObjFile *file) {
1032 StabsEntry stab(N_OSO);
1033 stab.sect = target->cpuSubtype;
1034 SmallString<261> path(!file->archiveName.empty() ? file->archiveName
1035 : file->getName());
1036 std::error_code ec = sys::fs::make_absolute(path);
1037 if (ec)
1038 fatal("failed to get absolute path for " + path);
1039
1040 if (!file->archiveName.empty())
1041 path.append({"(", file->getName(), ")"});
1042
1043 StringRef adjustedPath = saver().save(path.str());
1044 adjustedPath.consume_front(config->osoPrefix);
1045
1046 stab.strx = stringTableSection.addString(adjustedPath);
1047 stab.desc = 1;
1048 stab.value = file->modTime;
1049 stabs.emplace_back(std::move(stab));
1050}
1051
1052void SymtabSection::emitEndFunStab(Defined *defined) {
1053 StabsEntry stab(N_FUN);
1054 stab.value = defined->size;
1055 stabs.emplace_back(std::move(stab));
1056}
1057
1058void SymtabSection::emitStabs() {
1059 if (config->omitDebugInfo)
1060 return;
1061
1062 for (const std::string &s : config->astPaths) {
1063 StabsEntry astStab(N_AST);
1064 astStab.strx = stringTableSection.addString(s);
1065 stabs.emplace_back(std::move(astStab));
1066 }
1067
1068 // Cache the file ID for each symbol in an std::pair for faster sorting.
1069 using SortingPair = std::pair<Defined *, int>;
1070 std::vector<SortingPair> symbolsNeedingStabs;
1071 for (const SymtabEntry &entry :
1072 concat<SymtabEntry>(localSymbols, externalSymbols)) {
1073 Symbol *sym = entry.sym;
1074 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", 1075, __extension__ __PRETTY_FUNCTION__
))
1075 "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", 1075, __extension__ __PRETTY_FUNCTION__
))
;
1076 if (auto *defined = dyn_cast<Defined>(sym)) {
1077 // Excluded symbols should have been filtered out in finalizeContents().
1078 assert(defined->includeInSymtab)(static_cast <bool> (defined->includeInSymtab) ? void
(0) : __assert_fail ("defined->includeInSymtab", "lld/MachO/SyntheticSections.cpp"
, 1078, __extension__ __PRETTY_FUNCTION__))
;
1079
1080 if (defined->isAbsolute())
1081 continue;
1082
1083 // Constant-folded symbols go in the executable's symbol table, but don't
1084 // get a stabs entry.
1085 if (defined->wasIdenticalCodeFolded)
1086 continue;
1087
1088 InputSection *isec = defined->isec;
1089 ObjFile *file = dyn_cast_or_null<ObjFile>(isec->getFile());
1090 if (!file || !file->compileUnit)
1091 continue;
1092
1093 symbolsNeedingStabs.emplace_back(defined, defined->isec->getFile()->id);
1094 }
1095 }
1096
1097 llvm::stable_sort(symbolsNeedingStabs,
1098 [&](const SortingPair &a, const SortingPair &b) {
1099 return a.second < b.second;
1100 });
1101
1102 // Emit STABS symbols so that dsymutil and/or the debugger can map address
1103 // regions in the final binary to the source and object files from which they
1104 // originated.
1105 InputFile *lastFile = nullptr;
1106 for (SortingPair &pair : symbolsNeedingStabs) {
1107 Defined *defined = pair.first;
1108 InputSection *isec = defined->isec;
1109 ObjFile *file = cast<ObjFile>(isec->getFile());
1110
1111 if (lastFile == nullptr || lastFile != file) {
1112 if (lastFile != nullptr)
1113 emitEndSourceStab();
1114 lastFile = file;
1115
1116 emitBeginSourceStab(file->sourceFile());
1117 emitObjectFileStab(file);
1118 }
1119
1120 StabsEntry symStab;
1121 symStab.sect = defined->isec->parent->index;
1122 symStab.strx = stringTableSection.addString(defined->getName());
1123 symStab.value = defined->getVA();
1124
1125 if (isCodeSection(isec)) {
1126 symStab.type = N_FUN;
1127 stabs.emplace_back(std::move(symStab));
1128 emitEndFunStab(defined);
1129 } else {
1130 symStab.type = defined->isExternal() ? N_GSYM : N_STSYM;
1131 stabs.emplace_back(std::move(symStab));
1132 }
1133 }
1134
1135 if (!stabs.empty())
1136 emitEndSourceStab();
1137}
1138
1139void SymtabSection::finalizeContents() {
1140 auto addSymbol = [&](std::vector<SymtabEntry> &symbols, Symbol *sym) {
1141 uint32_t strx = stringTableSection.addString(sym->getName());
1142 symbols.push_back({sym, strx});
1143 };
1144
1145 std::function<void(Symbol *)> localSymbolsHandler;
1146 switch (config->localSymbolsPresence) {
1147 case SymtabPresence::All:
1148 localSymbolsHandler = [&](Symbol *sym) { addSymbol(localSymbols, sym); };
1149 break;
1150 case SymtabPresence::None:
1151 localSymbolsHandler = [&](Symbol *) { /* Do nothing*/ };
1152 break;
1153 case SymtabPresence::SelectivelyIncluded:
1154 localSymbolsHandler = [&](Symbol *sym) {
1155 if (config->localSymbolPatterns.match(sym->getName()))
1156 addSymbol(localSymbols, sym);
1157 };
1158 break;
1159 case SymtabPresence::SelectivelyExcluded:
1160 localSymbolsHandler = [&](Symbol *sym) {
1161 if (!config->localSymbolPatterns.match(sym->getName()))
1162 addSymbol(localSymbols, sym);
1163 };
1164 break;
1165 }
1166
1167 // Local symbols aren't in the SymbolTable, so we walk the list of object
1168 // files to gather them.
1169 // But if `-x` is set, then we don't need to. localSymbolsHandler() will do
1170 // the right thing regardless, but this check is a perf optimization because
1171 // iterating through all the input files and their symbols is expensive.
1172 if (config->localSymbolsPresence != SymtabPresence::None) {
1173 for (const InputFile *file : inputFiles) {
1174 if (auto *objFile = dyn_cast<ObjFile>(file)) {
1175 for (Symbol *sym : objFile->symbols) {
1176 if (auto *defined = dyn_cast_or_null<Defined>(sym)) {
1177 if (defined->isExternal() || !defined->isLive() ||
1178 !defined->includeInSymtab)
1179 continue;
1180 localSymbolsHandler(sym);
1181 }
1182 }
1183 }
1184 }
1185 }
1186
1187 // __dyld_private is a local symbol too. It's linker-created and doesn't
1188 // exist in any object file.
1189 if (Defined *dyldPrivate = in.stubHelper->dyldPrivate)
1190 localSymbolsHandler(dyldPrivate);
1191
1192 for (Symbol *sym : symtab->getSymbols()) {
1193 if (!sym->isLive())
1194 continue;
1195 if (auto *defined = dyn_cast<Defined>(sym)) {
1196 if (!defined->includeInSymtab)
1197 continue;
1198 assert(defined->isExternal())(static_cast <bool> (defined->isExternal()) ? void (
0) : __assert_fail ("defined->isExternal()", "lld/MachO/SyntheticSections.cpp"
, 1198, __extension__ __PRETTY_FUNCTION__))
;
1199 if (defined->privateExtern)
1200 localSymbolsHandler(defined);
1201 else
1202 addSymbol(externalSymbols, defined);
1203 } else if (auto *dysym = dyn_cast<DylibSymbol>(sym)) {
1204 if (dysym->isReferenced())
1205 addSymbol(undefinedSymbols, sym);
1206 }
1207 }
1208
1209 emitStabs();
1210 uint32_t symtabIndex = stabs.size();
1211 for (const SymtabEntry &entry :
1212 concat<SymtabEntry>(localSymbols, externalSymbols, undefinedSymbols)) {
1213 entry.sym->symtabIndex = symtabIndex++;
1214 }
1215}
1216
1217uint32_t SymtabSection::getNumSymbols() const {
1218 return stabs.size() + localSymbols.size() + externalSymbols.size() +
1219 undefinedSymbols.size();
1220}
1221
1222// This serves to hide (type-erase) the template parameter from SymtabSection.
1223template <class LP> class SymtabSectionImpl final : public SymtabSection {
1224public:
1225 SymtabSectionImpl(StringTableSection &stringTableSection)
1226 : SymtabSection(stringTableSection) {}
1227 uint64_t getRawSize() const override;
1228 void writeTo(uint8_t *buf) const override;
1229};
1230
1231template <class LP> uint64_t SymtabSectionImpl<LP>::getRawSize() const {
1232 return getNumSymbols() * sizeof(typename LP::nlist);
1233}
1234
1235template <class LP> void SymtabSectionImpl<LP>::writeTo(uint8_t *buf) const {
1236 auto *nList = reinterpret_cast<typename LP::nlist *>(buf);
1237 // Emit the stabs entries before the "real" symbols. We cannot emit them
1238 // after as that would render Symbol::symtabIndex inaccurate.
1239 for (const StabsEntry &entry : stabs) {
1240 nList->n_strx = entry.strx;
1241 nList->n_type = entry.type;
1242 nList->n_sect = entry.sect;
1243 nList->n_desc = entry.desc;
1244 nList->n_value = entry.value;
1245 ++nList;
1246 }
1247
1248 for (const SymtabEntry &entry : concat<const SymtabEntry>(
1249 localSymbols, externalSymbols, undefinedSymbols)) {
1250 nList->n_strx = entry.strx;
1251 // TODO populate n_desc with more flags
1252 if (auto *defined = dyn_cast<Defined>(entry.sym)) {
1253 uint8_t scope = 0;
1254 if (defined->privateExtern) {
1255 // Private external -- dylib scoped symbol.
1256 // Promote to non-external at link time.
1257 scope = N_PEXT;
1258 } else if (defined->isExternal()) {
1259 // Normal global symbol.
1260 scope = N_EXT;
1261 } else {
1262 // TU-local symbol from localSymbols.
1263 scope = 0;
1264 }
1265
1266 if (defined->isAbsolute()) {
1267 nList->n_type = scope | N_ABS;
1268 nList->n_sect = NO_SECT;
1269 nList->n_value = defined->value;
1270 } else {
1271 nList->n_type = scope | N_SECT;
1272 nList->n_sect = defined->isec->parent->index;
1273 // For the N_SECT symbol type, n_value is the address of the symbol
1274 nList->n_value = defined->getVA();
1275 }
1276 nList->n_desc |= defined->thumb ? N_ARM_THUMB_DEF : 0;
1277 nList->n_desc |= defined->isExternalWeakDef() ? N_WEAK_DEF : 0;
1278 nList->n_desc |=
1279 defined->referencedDynamically ? REFERENCED_DYNAMICALLY : 0;
1280 } else if (auto *dysym = dyn_cast<DylibSymbol>(entry.sym)) {
1281 uint16_t n_desc = nList->n_desc;
1282 int16_t ordinal = ordinalForDylibSymbol(*dysym);
1283 if (ordinal == BIND_SPECIAL_DYLIB_FLAT_LOOKUP)
1284 SET_LIBRARY_ORDINAL(n_desc, DYNAMIC_LOOKUP_ORDINAL);
1285 else if (ordinal == BIND_SPECIAL_DYLIB_MAIN_EXECUTABLE)
1286 SET_LIBRARY_ORDINAL(n_desc, EXECUTABLE_ORDINAL);
1287 else {
1288 assert(ordinal > 0)(static_cast <bool> (ordinal > 0) ? void (0) : __assert_fail
("ordinal > 0", "lld/MachO/SyntheticSections.cpp", 1288, __extension__
__PRETTY_FUNCTION__))
;
1289 SET_LIBRARY_ORDINAL(n_desc, static_cast<uint8_t>(ordinal));
1290 }
1291
1292 nList->n_type = N_EXT;
1293 n_desc |= dysym->isWeakDef() ? N_WEAK_DEF : 0;
1294 n_desc |= dysym->isWeakRef() ? N_WEAK_REF : 0;
1295 nList->n_desc = n_desc;
1296 }
1297 ++nList;
1298 }
1299}
1300
1301template <class LP>
1302SymtabSection *
1303macho::makeSymtabSection(StringTableSection &stringTableSection) {
1304 return make<SymtabSectionImpl<LP>>(stringTableSection);
1305}
1306
1307IndirectSymtabSection::IndirectSymtabSection()
1308 : LinkEditSection(segment_names::linkEdit,
1309 section_names::indirectSymbolTable) {}
1310
1311uint32_t IndirectSymtabSection::getNumSymbols() const {
1312 return in.got->getEntries().size() + in.tlvPointers->getEntries().size() +
1313 2 * in.stubs->getEntries().size();
1314}
1315
1316bool IndirectSymtabSection::isNeeded() const {
1317 return in.got->isNeeded() || in.tlvPointers->isNeeded() ||
1318 in.stubs->isNeeded();
1319}
1320
1321void IndirectSymtabSection::finalizeContents() {
1322 uint32_t off = 0;
1323 in.got->reserved1 = off;
1324 off += in.got->getEntries().size();
1325 in.tlvPointers->reserved1 = off;
1326 off += in.tlvPointers->getEntries().size();
1327 in.stubs->reserved1 = off;
1328 off += in.stubs->getEntries().size();
1329 in.lazyPointers->reserved1 = off;
1330}
1331
1332static uint32_t indirectValue(const Symbol *sym) {
1333 if (sym->symtabIndex == UINT32_MAX(4294967295U))
1334 return INDIRECT_SYMBOL_LOCAL;
1335 if (auto *defined = dyn_cast<Defined>(sym))
1336 if (defined->privateExtern)
1337 return INDIRECT_SYMBOL_LOCAL;
1338 return sym->symtabIndex;
1339}
1340
1341void IndirectSymtabSection::writeTo(uint8_t *buf) const {
1342 uint32_t off = 0;
1343 for (const Symbol *sym : in.got->getEntries()) {
1344 write32le(buf + off * sizeof(uint32_t), indirectValue(sym));
1345 ++off;
1346 }
1347 for (const Symbol *sym : in.tlvPointers->getEntries()) {
1348 write32le(buf + off * sizeof(uint32_t), indirectValue(sym));
1349 ++off;
1350 }
1351 for (const Symbol *sym : in.stubs->getEntries()) {
1352 write32le(buf + off * sizeof(uint32_t), indirectValue(sym));
1353 ++off;
1354 }
1355 // There is a 1:1 correspondence between stubs and LazyPointerSection
1356 // entries. But giving __stubs and __la_symbol_ptr the same reserved1
1357 // (the offset into the indirect symbol table) so that they both refer
1358 // to the same range of offsets confuses `strip`, so write the stubs
1359 // symbol table offsets a second time.
1360 for (const Symbol *sym : in.stubs->getEntries()) {
1361 write32le(buf + off * sizeof(uint32_t), indirectValue(sym));
1362 ++off;
1363 }
1364}
1365
1366StringTableSection::StringTableSection()
1367 : LinkEditSection(segment_names::linkEdit, section_names::stringTable) {}
1368
1369uint32_t StringTableSection::addString(StringRef str) {
1370 uint32_t strx = size;
1371 strings.push_back(str); // TODO: consider deduplicating strings
1372 size += str.size() + 1; // account for null terminator
1373 return strx;
1374}
1375
1376void StringTableSection::writeTo(uint8_t *buf) const {
1377 uint32_t off = 0;
1378 for (StringRef str : strings) {
1379 memcpy(buf + off, str.data(), str.size());
1380 off += str.size() + 1; // account for null terminator
1381 }
1382}
1383
1384static_assert((CodeSignatureSection::blobHeadersSize % 8) == 0);
1385static_assert((CodeSignatureSection::fixedHeadersSize % 8) == 0);
1386
1387CodeSignatureSection::CodeSignatureSection()
1388 : LinkEditSection(segment_names::linkEdit, section_names::codeSignature) {
1389 align = 16; // required by libstuff
1390 // FIXME: Consider using finalOutput instead of outputFile.
1391 fileName = config->outputFile;
1392 size_t slashIndex = fileName.rfind("/");
1393 if (slashIndex != std::string::npos)
1394 fileName = fileName.drop_front(slashIndex + 1);
1395
1396 // NOTE: Any changes to these calculations should be repeated
1397 // in llvm-objcopy's MachOLayoutBuilder::layoutTail.
1398 allHeadersSize = alignTo<16>(fixedHeadersSize + fileName.size() + 1);
1399 fileNamePad = allHeadersSize - fixedHeadersSize - fileName.size();
1400}
1401
1402uint32_t CodeSignatureSection::getBlockCount() const {
1403 return (fileOff + blockSize - 1) / blockSize;
1404}
1405
1406uint64_t CodeSignatureSection::getRawSize() const {
1407 return allHeadersSize + getBlockCount() * hashSize;
1408}
1409
1410void CodeSignatureSection::writeHashes(uint8_t *buf) const {
1411 // NOTE: Changes to this functionality should be repeated in llvm-objcopy's
1412 // MachOWriter::writeSignatureData.
1413 uint8_t *hashes = buf + fileOff + allHeadersSize;
1414 parallelFor(0, getBlockCount(), [&](size_t i) {
1415 sha256(buf + i * blockSize,
1416 std::min(static_cast<size_t>(fileOff - i * blockSize), blockSize),
1417 hashes + i * hashSize);
1418 });
1419#if defined(__APPLE__)
1420 // This is macOS-specific work-around and makes no sense for any
1421 // other host OS. See https://openradar.appspot.com/FB8914231
1422 //
1423 // The macOS kernel maintains a signature-verification cache to
1424 // quickly validate applications at time of execve(2). The trouble
1425 // is that for the kernel creates the cache entry at the time of the
1426 // mmap(2) call, before we have a chance to write either the code to
1427 // sign or the signature header+hashes. The fix is to invalidate
1428 // all cached data associated with the output file, thus discarding
1429 // the bogus prematurely-cached signature.
1430 msync(buf, fileOff + getSize(), MS_INVALIDATE);
1431#endif
1432}
1433
1434void CodeSignatureSection::writeTo(uint8_t *buf) const {
1435 // NOTE: Changes to this functionality should be repeated in llvm-objcopy's
1436 // MachOWriter::writeSignatureData.
1437 uint32_t signatureSize = static_cast<uint32_t>(getSize());
1438 auto *superBlob = reinterpret_cast<CS_SuperBlob *>(buf);
1439 write32be(&superBlob->magic, CSMAGIC_EMBEDDED_SIGNATURE);
1440 write32be(&superBlob->length, signatureSize);
1441 write32be(&superBlob->count, 1);
1442 auto *blobIndex = reinterpret_cast<CS_BlobIndex *>(&superBlob[1]);
1443 write32be(&blobIndex->type, CSSLOT_CODEDIRECTORY);
1444 write32be(&blobIndex->offset, blobHeadersSize);
1445 auto *codeDirectory =
1446 reinterpret_cast<CS_CodeDirectory *>(buf + blobHeadersSize);
1447 write32be(&codeDirectory->magic, CSMAGIC_CODEDIRECTORY);
1448 write32be(&codeDirectory->length, signatureSize - blobHeadersSize);
1449 write32be(&codeDirectory->version, CS_SUPPORTSEXECSEG);
1450 write32be(&codeDirectory->flags, CS_ADHOC | CS_LINKER_SIGNED);
1451 write32be(&codeDirectory->hashOffset,
1452 sizeof(CS_CodeDirectory) + fileName.size() + fileNamePad);
1453 write32be(&codeDirectory->identOffset, sizeof(CS_CodeDirectory));
1454 codeDirectory->nSpecialSlots = 0;
1455 write32be(&codeDirectory->nCodeSlots, getBlockCount());
1456 write32be(&codeDirectory->codeLimit, fileOff);
1457 codeDirectory->hashSize = static_cast<uint8_t>(hashSize);
1458 codeDirectory->hashType = kSecCodeSignatureHashSHA256;
1459 codeDirectory->platform = 0;
1460 codeDirectory->pageSize = blockSizeShift;
1461 codeDirectory->spare2 = 0;
1462 codeDirectory->scatterOffset = 0;
1463 codeDirectory->teamOffset = 0;
1464 codeDirectory->spare3 = 0;
1465 codeDirectory->codeLimit64 = 0;
1466 OutputSegment *textSeg = getOrCreateOutputSegment(segment_names::text);
1467 write64be(&codeDirectory->execSegBase, textSeg->fileOff);
1468 write64be(&codeDirectory->execSegLimit, textSeg->fileSize);
1469 write64be(&codeDirectory->execSegFlags,
1470 config->outputType == MH_EXECUTE ? CS_EXECSEG_MAIN_BINARY : 0);
1471 auto *id = reinterpret_cast<char *>(&codeDirectory[1]);
1472 memcpy(id, fileName.begin(), fileName.size());
1473 memset(id + fileName.size(), 0, fileNamePad);
1474}
1475
1476BitcodeBundleSection::BitcodeBundleSection()
1477 : SyntheticSection(segment_names::llvm, section_names::bitcodeBundle) {}
1478
1479class ErrorCodeWrapper {
1480public:
1481 explicit ErrorCodeWrapper(std::error_code ec) : errorCode(ec.value()) {}
1482 explicit ErrorCodeWrapper(int ec) : errorCode(ec) {}
1483 operator int() const { return errorCode; }
1484
1485private:
1486 int errorCode;
1487};
1488
1489#define CHECK_EC(exp)do { ErrorCodeWrapper ec(exp); if (ec) fatal(Twine("operation failed with error code "
) + Twine(ec) + ": " + "exp"); } while (0);
\
1490 do { \
1491 ErrorCodeWrapper ec(exp); \
1492 if (ec) \
1493 fatal(Twine("operation failed with error code ") + Twine(ec) + ": " + \
1494 #exp); \
1495 } while (0);
1496
1497void BitcodeBundleSection::finalize() {
1498#ifdef LLVM_HAVE_LIBXAR
1499 using namespace llvm::sys::fs;
1500 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);
;
1501
1502#pragma clang diagnostic push
1503#pragma clang diagnostic ignored "-Wdeprecated-declarations"
1504 xar_t xar(xar_open(xarPath.data(), O_RDWR));
1505#pragma clang diagnostic pop
1506 if (!xar)
1507 fatal("failed to open XAR temporary file at " + xarPath);
1508 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);
;
1509 // FIXME: add more data to XAR
1510 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);
;
1511
1512 file_size(xarPath, xarSize);
1513#endif // defined(LLVM_HAVE_LIBXAR)
1514}
1515
1516void BitcodeBundleSection::writeTo(uint8_t *buf) const {
1517 using namespace llvm::sys::fs;
1518 file_t handle =
1519 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"); })
1520 "failed to open XAR file")check2((openNativeFile(xarPath, CD_OpenExisting, FA_Read, OF_None
)), [&] { return toString("failed to open XAR file"); })
;
1521 std::error_code ec;
1522 mapped_file_region xarMap(handle, mapped_file_region::mapmode::readonly,
1523 xarSize, 0, ec);
1524 if (ec)
1525 fatal("failed to map XAR file");
1526 memcpy(buf, xarMap.const_data(), xarSize);
1527
1528 closeFile(handle);
1529 remove(xarPath);
1530}
1531
1532CStringSection::CStringSection(const char *name)
1533 : SyntheticSection(segment_names::text, name) {
1534 flags = S_CSTRING_LITERALS;
1535}
1536
1537void CStringSection::addInput(CStringInputSection *isec) {
1538 isec->parent = this;
1539 inputs.push_back(isec);
1540 if (isec->align > align)
1541 align = isec->align;
1542}
1543
1544void CStringSection::writeTo(uint8_t *buf) const {
1545 for (const CStringInputSection *isec : inputs) {
1546 for (size_t i = 0, e = isec->pieces.size(); i != e; ++i) {
1547 if (!isec->pieces[i].live)
1548 continue;
1549 StringRef string = isec->getStringRef(i);
1550 memcpy(buf + isec->pieces[i].outSecOff, string.data(), string.size());
1551 }
1552 }
1553}
1554
1555void CStringSection::finalizeContents() {
1556 uint64_t offset = 0;
1557 for (CStringInputSection *isec : inputs) {
1558 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
1559 if (!isec->pieces[i].live)
3
Assuming field 'live' is not equal to 0
4
Taking false branch
1560 continue;
1561 // See comment above DeduplicatedCStringSection for how alignment is
1562 // handled.
1563 uint32_t pieceAlign =
1564 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'
1565 offset = alignTo(offset, pieceAlign);
1566 isec->pieces[i].outSecOff = offset;
1567 isec->isFinal = true;
1568 StringRef string = isec->getStringRef(i);
1569 offset += string.size();
1570 }
1571 }
1572 size = offset;
1573}
1574
1575// Mergeable cstring literals are found under the __TEXT,__cstring section. In
1576// contrast to ELF, which puts strings that need different alignments into
1577// different sections, clang's Mach-O backend puts them all in one section.
1578// Strings that need to be aligned have the .p2align directive emitted before
1579// them, which simply translates into zero padding in the object file. In other
1580// words, we have to infer the desired alignment of these cstrings from their
1581// addresses.
1582//
1583// We differ slightly from ld64 in how we've chosen to align these cstrings.
1584// Both LLD and ld64 preserve the number of trailing zeros in each cstring's
1585// address in the input object files. When deduplicating identical cstrings,
1586// both linkers pick the cstring whose address has more trailing zeros, and
1587// preserve the alignment of that address in the final binary. However, ld64
1588// goes a step further and also preserves the offset of the cstring from the
1589// last section-aligned address. I.e. if a cstring is at offset 18 in the
1590// input, with a section alignment of 16, then both LLD and ld64 will ensure the
1591// final address is 2-byte aligned (since 18 == 16 + 2). But ld64 will also
1592// ensure that the final address is of the form 16 * k + 2 for some k.
1593//
1594// Note that ld64's heuristic means that a dedup'ed cstring's final address is
1595// dependent on the order of the input object files. E.g. if in addition to the
1596// cstring at offset 18 above, we have a duplicate one in another file with a
1597// `.cstring` section alignment of 2 and an offset of zero, then ld64 will pick
1598// the cstring from the object file earlier on the command line (since both have
1599// the same number of trailing zeros in their address). So the final cstring may
1600// either be at some address `16 * k + 2` or at some address `2 * k`.
1601//
1602// I've opted not to follow this behavior primarily for implementation
1603// simplicity, and secondarily to save a few more bytes. It's not clear to me
1604// that preserving the section alignment + offset is ever necessary, and there
1605// are many cases that are clearly redundant. In particular, if an x86_64 object
1606// file contains some strings that are accessed via SIMD instructions, then the
1607// .cstring section in the object file will be 16-byte-aligned (since SIMD
1608// requires its operand addresses to be 16-byte aligned). However, there will
1609// typically also be other cstrings in the same file that aren't used via SIMD
1610// and don't need this alignment. They will be emitted at some arbitrary address
1611// `A`, but ld64 will treat them as being 16-byte aligned with an offset of `16
1612// % A`.
1613void DeduplicatedCStringSection::finalizeContents() {
1614 // Find the largest alignment required for each string.
1615 for (const CStringInputSection *isec : inputs) {
1616 for (size_t i = 0, e = isec->pieces.size(); i != e; ++i) {
1617 const StringPiece &piece = isec->pieces[i];
1618 if (!piece.live)
1619 continue;
1620 auto s = isec->getCachedHashStringRef(i);
1621 assert(isec->align != 0)(static_cast <bool> (isec->align != 0) ? void (0) : __assert_fail
("isec->align != 0", "lld/MachO/SyntheticSections.cpp", 1621
, __extension__ __PRETTY_FUNCTION__))
;
1622 uint8_t trailingZeros = countTrailingZeros(isec->align | piece.inSecOff);
1623 auto it = stringOffsetMap.insert(
1624 std::make_pair(s, StringOffset(trailingZeros)));
1625 if (!it.second && it.first->second.trailingZeros < trailingZeros)
1626 it.first->second.trailingZeros = trailingZeros;
1627 }
1628 }
1629
1630 // Assign an offset for each string and save it to the corresponding
1631 // StringPieces for easy access.
1632 for (CStringInputSection *isec : inputs) {
1633 for (size_t i = 0, e = isec->pieces.size(); i != e; ++i) {
1634 if (!isec->pieces[i].live)
1635 continue;
1636 auto s = isec->getCachedHashStringRef(i);
1637 auto it = stringOffsetMap.find(s);
1638 assert(it != stringOffsetMap.end())(static_cast <bool> (it != stringOffsetMap.end()) ? void
(0) : __assert_fail ("it != stringOffsetMap.end()", "lld/MachO/SyntheticSections.cpp"
, 1638, __extension__ __PRETTY_FUNCTION__))
;
1639 StringOffset &offsetInfo = it->second;
1640 if (offsetInfo.outSecOff == UINT64_MAX(18446744073709551615UL)) {
1641 offsetInfo.outSecOff = alignTo(size, 1ULL << offsetInfo.trailingZeros);
1642 size = offsetInfo.outSecOff + s.size();
1643 }
1644 isec->pieces[i].outSecOff = offsetInfo.outSecOff;
1645 }
1646 isec->isFinal = true;
1647 }
1648}
1649
1650void DeduplicatedCStringSection::writeTo(uint8_t *buf) const {
1651 for (const auto &p : stringOffsetMap) {
1652 StringRef data = p.first.val();
1653 uint64_t off = p.second.outSecOff;
1654 if (!data.empty())
1655 memcpy(buf + off, data.data(), data.size());
1656 }
1657}
1658
1659DeduplicatedCStringSection::StringOffset
1660DeduplicatedCStringSection::getStringOffset(StringRef str) const {
1661 // StringPiece uses 31 bits to store the hashes, so we replicate that
1662 uint32_t hash = xxHash64(str) & 0x7fffffff;
1663 auto offset = stringOffsetMap.find(CachedHashStringRef(str, hash));
1664 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", 1665, __extension__ __PRETTY_FUNCTION__
))
1665 "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", 1665, __extension__ __PRETTY_FUNCTION__
))
;
1666 return offset->second;
1667}
1668
1669// This section is actually emitted as __TEXT,__const by ld64, but clang may
1670// emit input sections of that name, and LLD doesn't currently support mixing
1671// synthetic and concat-type OutputSections. To work around this, I've given
1672// our merged-literals section a different name.
1673WordLiteralSection::WordLiteralSection()
1674 : SyntheticSection(segment_names::text, section_names::literals) {
1675 align = 16;
1676}
1677
1678void WordLiteralSection::addInput(WordLiteralInputSection *isec) {
1679 isec->parent = this;
1680 inputs.push_back(isec);
1681}
1682
1683void WordLiteralSection::finalizeContents() {
1684 for (WordLiteralInputSection *isec : inputs) {
1685 // We do all processing of the InputSection here, so it will be effectively
1686 // finalized.
1687 isec->isFinal = true;
1688 const uint8_t *buf = isec->data.data();
1689 switch (sectionType(isec->getFlags())) {
1690 case S_4BYTE_LITERALS: {
1691 for (size_t off = 0, e = isec->data.size(); off < e; off += 4) {
1692 if (!isec->isLive(off))
1693 continue;
1694 uint32_t value = *reinterpret_cast<const uint32_t *>(buf + off);
1695 literal4Map.emplace(value, literal4Map.size());
1696 }
1697 break;
1698 }
1699 case S_8BYTE_LITERALS: {
1700 for (size_t off = 0, e = isec->data.size(); off < e; off += 8) {
1701 if (!isec->isLive(off))
1702 continue;
1703 uint64_t value = *reinterpret_cast<const uint64_t *>(buf + off);
1704 literal8Map.emplace(value, literal8Map.size());
1705 }
1706 break;
1707 }
1708 case S_16BYTE_LITERALS: {
1709 for (size_t off = 0, e = isec->data.size(); off < e; off += 16) {
1710 if (!isec->isLive(off))
1711 continue;
1712 UInt128 value = *reinterpret_cast<const UInt128 *>(buf + off);
1713 literal16Map.emplace(value, literal16Map.size());
1714 }
1715 break;
1716 }
1717 default:
1718 llvm_unreachable("invalid literal section type")::llvm::llvm_unreachable_internal("invalid literal section type"
, "lld/MachO/SyntheticSections.cpp", 1718)
;
1719 }
1720 }
1721}
1722
1723void WordLiteralSection::writeTo(uint8_t *buf) const {
1724 // Note that we don't attempt to do any endianness conversion in addInput(),
1725 // so we don't do it here either -- just write out the original value,
1726 // byte-for-byte.
1727 for (const auto &p : literal16Map)
1728 memcpy(buf + p.second * 16, &p.first, 16);
1729 buf += literal16Map.size() * 16;
1730
1731 for (const auto &p : literal8Map)
1732 memcpy(buf + p.second * 8, &p.first, 8);
1733 buf += literal8Map.size() * 8;
1734
1735 for (const auto &p : literal4Map)
1736 memcpy(buf + p.second * 4, &p.first, 4);
1737}
1738
1739ObjCImageInfoSection::ObjCImageInfoSection()
1740 : SyntheticSection(segment_names::data, section_names::objCImageInfo) {}
1741
1742ObjCImageInfoSection::ImageInfo
1743ObjCImageInfoSection::parseImageInfo(const InputFile *file) {
1744 ImageInfo info;
1745 ArrayRef<uint8_t> data = file->objCImageInfo;
1746 // The image info struct has the following layout:
1747 // struct {
1748 // uint32_t version;
1749 // uint32_t flags;
1750 // };
1751 if (data.size() < 8) {
1752 warn(toString(file) + ": invalid __objc_imageinfo size");
1753 return info;
1754 }
1755
1756 auto *buf = reinterpret_cast<const uint32_t *>(data.data());
1757 if (read32le(buf) != 0) {
1758 warn(toString(file) + ": invalid __objc_imageinfo version");
1759 return info;
1760 }
1761
1762 uint32_t flags = read32le(buf + 1);
1763 info.swiftVersion = (flags >> 8) & 0xff;
1764 info.hasCategoryClassProperties = flags & 0x40;
1765 return info;
1766}
1767
1768static std::string swiftVersionString(uint8_t version) {
1769 switch (version) {
1770 case 1:
1771 return "1.0";
1772 case 2:
1773 return "1.1";
1774 case 3:
1775 return "2.0";
1776 case 4:
1777 return "3.0";
1778 case 5:
1779 return "4.0";
1780 default:
1781 return ("0x" + Twine::utohexstr(version)).str();
1782 }
1783}
1784
1785// Validate each object file's __objc_imageinfo and use them to generate the
1786// image info for the output binary. Only two pieces of info are relevant:
1787// 1. The Swift version (should be identical across inputs)
1788// 2. `bool hasCategoryClassProperties` (true only if true for all inputs)
1789void ObjCImageInfoSection::finalizeContents() {
1790 assert(files.size() != 0)(static_cast <bool> (files.size() != 0) ? void (0) : __assert_fail
("files.size() != 0", "lld/MachO/SyntheticSections.cpp", 1790
, __extension__ __PRETTY_FUNCTION__))
; // should have already been checked via isNeeded()
1791
1792 info.hasCategoryClassProperties = true;
1793 const InputFile *firstFile;
1794 for (auto file : files) {
1795 ImageInfo inputInfo = parseImageInfo(file);
1796 info.hasCategoryClassProperties &= inputInfo.hasCategoryClassProperties;
1797
1798 // swiftVersion 0 means no Swift is present, so no version checking required
1799 if (inputInfo.swiftVersion == 0)
1800 continue;
1801
1802 if (info.swiftVersion != 0 && info.swiftVersion != inputInfo.swiftVersion) {
1803 error("Swift version mismatch: " + toString(firstFile) + " has version " +
1804 swiftVersionString(info.swiftVersion) + " but " + toString(file) +
1805 " has version " + swiftVersionString(inputInfo.swiftVersion));
1806 } else {
1807 info.swiftVersion = inputInfo.swiftVersion;
1808 firstFile = file;
1809 }
1810 }
1811}
1812
1813void ObjCImageInfoSection::writeTo(uint8_t *buf) const {
1814 uint32_t flags = info.hasCategoryClassProperties ? 0x40 : 0x0;
1815 flags |= info.swiftVersion << 8;
1816 write32le(buf + 4, flags);
1817}
1818
1819InitOffsetsSection::InitOffsetsSection()
1820 : SyntheticSection(segment_names::text, section_names::initOffsets) {
1821 flags = S_INIT_FUNC_OFFSETS;
1822}
1823
1824uint64_t InitOffsetsSection::getSize() const {
1825 size_t count = 0;
1826 for (const ConcatInputSection *isec : sections)
1827 count += isec->relocs.size();
1828 return count * sizeof(uint32_t);
1829}
1830
1831void InitOffsetsSection::writeTo(uint8_t *buf) const {
1832 uint64_t textVA = 0;
1833 for (const OutputSegment *oseg : outputSegments)
1834 if (oseg->name == segment_names::text) {
1835 textVA = oseg->addr;
1836 break;
1837 }
1838
1839 // FIXME: Add function specified by -init when that argument is implemented.
1840 for (ConcatInputSection *isec : sections) {
1841 for (const Reloc &rel : isec->relocs) {
1842 const Symbol *referent = rel.referent.dyn_cast<Symbol *>();
1843 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", 1843, __extension__ __PRETTY_FUNCTION__
))
;
1844 uint64_t offset = referent->getVA() - textVA;
1845 // FIXME: Can we handle this gracefully?
1846 if (offset > UINT32_MAX(4294967295U))
1847 fatal(isec->getLocation(rel.offset) + ": offset to initializer " +
1848 referent->getName() + " (" + utohexstr(offset) +
1849 ") does not fit in 32 bits");
1850
1851 // Entries need to be added in the order they appear in the section, but
1852 // relocations aren't guaranteed to be sorted.
1853 size_t index = rel.offset >> target->p2WordSize;
1854 write32le(&buf[index * sizeof(uint32_t)], offset);
1855 }
1856 buf += isec->relocs.size() * sizeof(uint32_t);
1857 }
1858}
1859
1860// The inputs are __mod_init_func sections, which contain pointers to
1861// initializer functions, therefore all relocations should be of the UNSIGNED
1862// type. InitOffsetsSection stores offsets, so if the initializer's address is
1863// not known at link time, stub-indirection has to be used.
1864void InitOffsetsSection::setUp() {
1865 for (const ConcatInputSection *isec : sections) {
1866 for (const Reloc &rel : isec->relocs) {
1867 RelocAttrs attrs = target->getRelocAttrs(rel.type);
1868 if (!attrs.hasAttr(RelocAttrBits::UNSIGNED))
1869 error(isec->getLocation(rel.offset) +
1870 ": unsupported relocation type: " + attrs.name);
1871 if (rel.addend != 0)
1872 error(isec->getLocation(rel.offset) +
1873 ": relocation addend is not representable in __init_offsets");
1874 if (rel.referent.is<InputSection *>())
1875 error(isec->getLocation(rel.offset) +
1876 ": unexpected section relocation");
1877
1878 Symbol *sym = rel.referent.dyn_cast<Symbol *>();
1879 if (auto *undefined = dyn_cast<Undefined>(sym))
1880 treatUndefinedSymbol(*undefined, isec, rel.offset);
1881 if (needsBinding(sym))
1882 in.stubs->addEntry(sym);
1883 }
1884 }
1885}
1886
1887void macho::createSyntheticSymbols() {
1888 auto addHeaderSymbol = [](const char *name) {
1889 symtab->addSynthetic(name, in.header->isec, /*value=*/0,
1890 /*isPrivateExtern=*/true, /*includeInSymtab=*/false,
1891 /*referencedDynamically=*/false);
1892 };
1893
1894 switch (config->outputType) {
1895 // FIXME: Assign the right address value for these symbols
1896 // (rather than 0). But we need to do that after assignAddresses().
1897 case MH_EXECUTE:
1898 // If linking PIE, __mh_execute_header is a defined symbol in
1899 // __TEXT, __text)
1900 // Otherwise, it's an absolute symbol.
1901 if (config->isPic)
1902 symtab->addSynthetic("__mh_execute_header", in.header->isec, /*value=*/0,
1903 /*isPrivateExtern=*/false, /*includeInSymtab=*/true,
1904 /*referencedDynamically=*/true);
1905 else
1906 symtab->addSynthetic("__mh_execute_header", /*isec=*/nullptr, /*value=*/0,
1907 /*isPrivateExtern=*/false, /*includeInSymtab=*/true,
1908 /*referencedDynamically=*/true);
1909 break;
1910
1911 // The following symbols are N_SECT symbols, even though the header is not
1912 // part of any section and that they are private to the bundle/dylib/object
1913 // they are part of.
1914 case MH_BUNDLE:
1915 addHeaderSymbol("__mh_bundle_header");
1916 break;
1917 case MH_DYLIB:
1918 addHeaderSymbol("__mh_dylib_header");
1919 break;
1920 case MH_DYLINKER:
1921 addHeaderSymbol("__mh_dylinker_header");
1922 break;
1923 case MH_OBJECT:
1924 addHeaderSymbol("__mh_object_header");
1925 break;
1926 default:
1927 llvm_unreachable("unexpected outputType")::llvm::llvm_unreachable_internal("unexpected outputType", "lld/MachO/SyntheticSections.cpp"
, 1927)
;
1928 break;
1929 }
1930
1931 // The Itanium C++ ABI requires dylibs to pass a pointer to __cxa_atexit
1932 // which does e.g. cleanup of static global variables. The ABI document
1933 // says that the pointer can point to any address in one of the dylib's
1934 // segments, but in practice ld64 seems to set it to point to the header,
1935 // so that's what's implemented here.
1936 addHeaderSymbol("___dso_handle");
1937}
1938
1939template SymtabSection *macho::makeSymtabSection<LP64>(StringTableSection &);
1940template SymtabSection *macho::makeSymtabSection<ILP32>(StringTableSection &);

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