Bug Summary

File:build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/lld/ELF/InputFiles.cpp
Warning:line 1340, column 16
The result of the left shift is undefined due to shifting by '64', which is greater or equal to the width of type 'unsigned long long'

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 InputFiles.cpp -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm -resource-dir /usr/lib/llvm-16/lib/clang/16.0.0 -D LLD_VENDOR="Debian" -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I tools/lld/ELF -I /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/lld/ELF -I /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/lld/include -I tools/lld/include -I include -I /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-16/lib/clang/16.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/= -O3 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-10-03-140002-15933-1 -x c++ /build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/lld/ELF/InputFiles.cpp

/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/lld/ELF/InputFiles.cpp

1//===- InputFiles.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 "InputFiles.h"
10#include "Config.h"
11#include "DWARF.h"
12#include "Driver.h"
13#include "InputSection.h"
14#include "LinkerScript.h"
15#include "SymbolTable.h"
16#include "Symbols.h"
17#include "SyntheticSections.h"
18#include "Target.h"
19#include "lld/Common/CommonLinkerContext.h"
20#include "lld/Common/DWARF.h"
21#include "llvm/ADT/CachedHashString.h"
22#include "llvm/ADT/STLExtras.h"
23#include "llvm/LTO/LTO.h"
24#include "llvm/Object/IRObjectFile.h"
25#include "llvm/Support/ARMAttributeParser.h"
26#include "llvm/Support/ARMBuildAttributes.h"
27#include "llvm/Support/Endian.h"
28#include "llvm/Support/FileSystem.h"
29#include "llvm/Support/Path.h"
30#include "llvm/Support/RISCVAttributeParser.h"
31#include "llvm/Support/TarWriter.h"
32#include "llvm/Support/raw_ostream.h"
33
34using namespace llvm;
35using namespace llvm::ELF;
36using namespace llvm::object;
37using namespace llvm::sys;
38using namespace llvm::sys::fs;
39using namespace llvm::support::endian;
40using namespace lld;
41using namespace lld::elf;
42
43bool InputFile::isInGroup;
44uint32_t InputFile::nextGroupId;
45
46std::unique_ptr<TarWriter> elf::tar;
47
48// Returns "<internal>", "foo.a(bar.o)" or "baz.o".
49std::string lld::toString(const InputFile *f) {
50 static std::mutex mu;
51 if (!f)
52 return "<internal>";
53
54 {
55 std::lock_guard<std::mutex> lock(mu);
56 if (f->toStringCache.empty()) {
57 if (f->archiveName.empty())
58 f->toStringCache = f->getName();
59 else
60 (f->archiveName + "(" + f->getName() + ")").toVector(f->toStringCache);
61 }
62 }
63 return std::string(f->toStringCache);
64}
65
66static ELFKind getELFKind(MemoryBufferRef mb, StringRef archiveName) {
67 unsigned char size;
68 unsigned char endian;
69 std::tie(size, endian) = getElfArchType(mb.getBuffer());
70
71 auto report = [&](StringRef msg) {
72 StringRef filename = mb.getBufferIdentifier();
73 if (archiveName.empty())
74 fatal(filename + ": " + msg);
75 else
76 fatal(archiveName + "(" + filename + "): " + msg);
77 };
78
79 if (!mb.getBuffer().startswith(ElfMagic))
80 report("not an ELF file");
81 if (endian != ELFDATA2LSB && endian != ELFDATA2MSB)
82 report("corrupted ELF file: invalid data encoding");
83 if (size != ELFCLASS32 && size != ELFCLASS64)
84 report("corrupted ELF file: invalid file class");
85
86 size_t bufSize = mb.getBuffer().size();
87 if ((size == ELFCLASS32 && bufSize < sizeof(Elf32_Ehdr)) ||
88 (size == ELFCLASS64 && bufSize < sizeof(Elf64_Ehdr)))
89 report("corrupted ELF file: file is too short");
90
91 if (size == ELFCLASS32)
92 return (endian == ELFDATA2LSB) ? ELF32LEKind : ELF32BEKind;
93 return (endian == ELFDATA2LSB) ? ELF64LEKind : ELF64BEKind;
94}
95
96// For ARM only, to set the EF_ARM_ABI_FLOAT_SOFT or EF_ARM_ABI_FLOAT_HARD
97// flag in the ELF Header we need to look at Tag_ABI_VFP_args to find out how
98// the input objects have been compiled.
99static void updateARMVFPArgs(const ARMAttributeParser &attributes,
100 const InputFile *f) {
101 Optional<unsigned> attr =
102 attributes.getAttributeValue(ARMBuildAttrs::ABI_VFP_args);
103 if (!attr)
104 // If an ABI tag isn't present then it is implicitly given the value of 0
105 // which maps to ARMBuildAttrs::BaseAAPCS. However many assembler files,
106 // including some in glibc that don't use FP args (and should have value 3)
107 // don't have the attribute so we do not consider an implicit value of 0
108 // as a clash.
109 return;
110
111 unsigned vfpArgs = *attr;
112 ARMVFPArgKind arg;
113 switch (vfpArgs) {
114 case ARMBuildAttrs::BaseAAPCS:
115 arg = ARMVFPArgKind::Base;
116 break;
117 case ARMBuildAttrs::HardFPAAPCS:
118 arg = ARMVFPArgKind::VFP;
119 break;
120 case ARMBuildAttrs::ToolChainFPPCS:
121 // Tool chain specific convention that conforms to neither AAPCS variant.
122 arg = ARMVFPArgKind::ToolChain;
123 break;
124 case ARMBuildAttrs::CompatibleFPAAPCS:
125 // Object compatible with all conventions.
126 return;
127 default:
128 error(toString(f) + ": unknown Tag_ABI_VFP_args value: " + Twine(vfpArgs));
129 return;
130 }
131 // Follow ld.bfd and error if there is a mix of calling conventions.
132 if (config->armVFPArgs != arg && config->armVFPArgs != ARMVFPArgKind::Default)
133 error(toString(f) + ": incompatible Tag_ABI_VFP_args");
134 else
135 config->armVFPArgs = arg;
136}
137
138// The ARM support in lld makes some use of instructions that are not available
139// on all ARM architectures. Namely:
140// - Use of BLX instruction for interworking between ARM and Thumb state.
141// - Use of the extended Thumb branch encoding in relocation.
142// - Use of the MOVT/MOVW instructions in Thumb Thunks.
143// The ARM Attributes section contains information about the architecture chosen
144// at compile time. We follow the convention that if at least one input object
145// is compiled with an architecture that supports these features then lld is
146// permitted to use them.
147static void updateSupportedARMFeatures(const ARMAttributeParser &attributes) {
148 Optional<unsigned> attr =
149 attributes.getAttributeValue(ARMBuildAttrs::CPU_arch);
150 if (!attr)
151 return;
152 auto arch = attr.value();
153 switch (arch) {
154 case ARMBuildAttrs::Pre_v4:
155 case ARMBuildAttrs::v4:
156 case ARMBuildAttrs::v4T:
157 // Architectures prior to v5 do not support BLX instruction
158 break;
159 case ARMBuildAttrs::v5T:
160 case ARMBuildAttrs::v5TE:
161 case ARMBuildAttrs::v5TEJ:
162 case ARMBuildAttrs::v6:
163 case ARMBuildAttrs::v6KZ:
164 case ARMBuildAttrs::v6K:
165 config->armHasBlx = true;
166 // Architectures used in pre-Cortex processors do not support
167 // The J1 = 1 J2 = 1 Thumb branch range extension, with the exception
168 // of Architecture v6T2 (arm1156t2-s and arm1156t2f-s) that do.
169 break;
170 default:
171 // All other Architectures have BLX and extended branch encoding
172 config->armHasBlx = true;
173 config->armJ1J2BranchEncoding = true;
174 if (arch != ARMBuildAttrs::v6_M && arch != ARMBuildAttrs::v6S_M)
175 // All Architectures used in Cortex processors with the exception
176 // of v6-M and v6S-M have the MOVT and MOVW instructions.
177 config->armHasMovtMovw = true;
178 break;
179 }
180}
181
182InputFile::InputFile(Kind k, MemoryBufferRef m)
183 : mb(m), groupId(nextGroupId), fileKind(k) {
184 // All files within the same --{start,end}-group get the same group ID.
185 // Otherwise, a new file will get a new group ID.
186 if (!isInGroup)
187 ++nextGroupId;
188}
189
190Optional<MemoryBufferRef> elf::readFile(StringRef path) {
191 llvm::TimeTraceScope timeScope("Load input files", path);
192
193 // The --chroot option changes our virtual root directory.
194 // This is useful when you are dealing with files created by --reproduce.
195 if (!config->chroot.empty() && path.startswith("/"))
196 path = saver().save(config->chroot + path);
197
198 log(path);
199 config->dependencyFiles.insert(llvm::CachedHashString(path));
200
201 auto mbOrErr = MemoryBuffer::getFile(path, /*IsText=*/false,
202 /*RequiresNullTerminator=*/false);
203 if (auto ec = mbOrErr.getError()) {
204 error("cannot open " + path + ": " + ec.message());
205 return None;
206 }
207
208 MemoryBufferRef mbref = (*mbOrErr)->getMemBufferRef();
209 ctx.memoryBuffers.push_back(std::move(*mbOrErr)); // take MB ownership
210
211 if (tar)
212 tar->append(relativeToRoot(path), mbref.getBuffer());
213 return mbref;
214}
215
216// All input object files must be for the same architecture
217// (e.g. it does not make sense to link x86 object files with
218// MIPS object files.) This function checks for that error.
219static bool isCompatible(InputFile *file) {
220 if (!file->isElf() && !isa<BitcodeFile>(file))
221 return true;
222
223 if (file->ekind == config->ekind && file->emachine == config->emachine) {
224 if (config->emachine != EM_MIPS)
225 return true;
226 if (isMipsN32Abi(file) == config->mipsN32Abi)
227 return true;
228 }
229
230 StringRef target =
231 !config->bfdname.empty() ? config->bfdname : config->emulation;
232 if (!target.empty()) {
233 error(toString(file) + " is incompatible with " + target);
234 return false;
235 }
236
237 InputFile *existing = nullptr;
238 if (!ctx.objectFiles.empty())
239 existing = ctx.objectFiles[0];
240 else if (!ctx.sharedFiles.empty())
241 existing = ctx.sharedFiles[0];
242 else if (!ctx.bitcodeFiles.empty())
243 existing = ctx.bitcodeFiles[0];
244 std::string with;
245 if (existing)
246 with = " with " + toString(existing);
247 error(toString(file) + " is incompatible" + with);
248 return false;
249}
250
251template <class ELFT> static void doParseFile(InputFile *file) {
252 if (!isCompatible(file))
1
Taking false branch
253 return;
254
255 // Binary file
256 if (auto *f
2.1
'f' is null
2.1
'f' is null
= dyn_cast<BinaryFile>(file)) {
2
Assuming 'file' is not a 'CastReturnType'
3
Taking false branch
257 ctx.binaryFiles.push_back(f);
258 f->parse();
259 return;
260 }
261
262 // Lazy object file
263 if (file->lazy) {
4
Assuming field 'lazy' is false
5
Taking false branch
264 if (auto *f = dyn_cast<BitcodeFile>(file)) {
265 ctx.lazyBitcodeFiles.push_back(f);
266 f->parseLazy();
267 } else {
268 cast<ObjFile<ELFT>>(file)->parseLazy();
269 }
270 return;
271 }
272
273 if (config->trace)
6
Assuming field 'trace' is false
7
Taking false branch
274 message(toString(file));
275
276 // .so file
277 if (auto *f
8.1
'f' is non-null
8.1
'f' is non-null
= dyn_cast<SharedFile>(file)) {
8
Assuming 'file' is a 'CastReturnType'
9
Taking true branch
278 f->parse<ELFT>();
10
Calling 'SharedFile::parse'
279 return;
280 }
281
282 // LLVM bitcode file
283 if (auto *f = dyn_cast<BitcodeFile>(file)) {
284 ctx.bitcodeFiles.push_back(f);
285 f->parse();
286 return;
287 }
288
289 // Regular object file
290 ctx.objectFiles.push_back(cast<ELFFileBase>(file));
291 cast<ObjFile<ELFT>>(file)->parse();
292}
293
294// Add symbols in File to the symbol table.
295void elf::parseFile(InputFile *file) { invokeELFT(doParseFile, file)switch (config->ekind) { case ELF32LEKind: doParseFile<
ELF32LE>(file); break; case ELF32BEKind: doParseFile<ELF32BE
>(file); break; case ELF64LEKind: doParseFile<ELF64LE>
(file); break; case ELF64BEKind: doParseFile<ELF64BE>(file
); break; default: ::llvm::llvm_unreachable_internal("unknown config->ekind"
, "lld/ELF/InputFiles.cpp", 295); }
; }
296
297// Concatenates arguments to construct a string representing an error location.
298static std::string createFileLineMsg(StringRef path, unsigned line) {
299 std::string filename = std::string(path::filename(path));
300 std::string lineno = ":" + std::to_string(line);
301 if (filename == path)
302 return filename + lineno;
303 return filename + lineno + " (" + path.str() + lineno + ")";
304}
305
306template <class ELFT>
307static std::string getSrcMsgAux(ObjFile<ELFT> &file, const Symbol &sym,
308 InputSectionBase &sec, uint64_t offset) {
309 // In DWARF, functions and variables are stored to different places.
310 // First, look up a function for a given offset.
311 if (Optional<DILineInfo> info = file.getDILineInfo(&sec, offset))
312 return createFileLineMsg(info->FileName, info->Line);
313
314 // If it failed, look up again as a variable.
315 if (Optional<std::pair<std::string, unsigned>> fileLine =
316 file.getVariableLoc(sym.getName()))
317 return createFileLineMsg(fileLine->first, fileLine->second);
318
319 // File.sourceFile contains STT_FILE symbol, and that is a last resort.
320 return std::string(file.sourceFile);
321}
322
323std::string InputFile::getSrcMsg(const Symbol &sym, InputSectionBase &sec,
324 uint64_t offset) {
325 if (kind() != ObjKind)
326 return "";
327 switch (ekind) {
328 default:
329 llvm_unreachable("Invalid kind")::llvm::llvm_unreachable_internal("Invalid kind", "lld/ELF/InputFiles.cpp"
, 329)
;
330 case ELF32LEKind:
331 return getSrcMsgAux(cast<ObjFile<ELF32LE>>(*this), sym, sec, offset);
332 case ELF32BEKind:
333 return getSrcMsgAux(cast<ObjFile<ELF32BE>>(*this), sym, sec, offset);
334 case ELF64LEKind:
335 return getSrcMsgAux(cast<ObjFile<ELF64LE>>(*this), sym, sec, offset);
336 case ELF64BEKind:
337 return getSrcMsgAux(cast<ObjFile<ELF64BE>>(*this), sym, sec, offset);
338 }
339}
340
341StringRef InputFile::getNameForScript() const {
342 if (archiveName.empty())
343 return getName();
344
345 if (nameForScriptCache.empty())
346 nameForScriptCache = (archiveName + Twine(':') + getName()).str();
347
348 return nameForScriptCache;
349}
350
351// An ELF object file may contain a `.deplibs` section. If it exists, the
352// section contains a list of library specifiers such as `m` for libm. This
353// function resolves a given name by finding the first matching library checking
354// the various ways that a library can be specified to LLD. This ELF extension
355// is a form of autolinking and is called `dependent libraries`. It is currently
356// unique to LLVM and lld.
357static void addDependentLibrary(StringRef specifier, const InputFile *f) {
358 if (!config->dependentLibraries)
359 return;
360 if (Optional<std::string> s = searchLibraryBaseName(specifier))
361 ctx.driver.addFile(saver().save(*s), /*withLOption=*/true);
362 else if (Optional<std::string> s = findFromSearchPaths(specifier))
363 ctx.driver.addFile(saver().save(*s), /*withLOption=*/true);
364 else if (fs::exists(specifier))
365 ctx.driver.addFile(specifier, /*withLOption=*/false);
366 else
367 error(toString(f) +
368 ": unable to find library from dependent library specifier: " +
369 specifier);
370}
371
372// Record the membership of a section group so that in the garbage collection
373// pass, section group members are kept or discarded as a unit.
374template <class ELFT>
375static void handleSectionGroup(ArrayRef<InputSectionBase *> sections,
376 ArrayRef<typename ELFT::Word> entries) {
377 bool hasAlloc = false;
378 for (uint32_t index : entries.slice(1)) {
379 if (index >= sections.size())
380 return;
381 if (InputSectionBase *s = sections[index])
382 if (s != &InputSection::discarded && s->flags & SHF_ALLOC)
383 hasAlloc = true;
384 }
385
386 // If any member has the SHF_ALLOC flag, the whole group is subject to garbage
387 // collection. See the comment in markLive(). This rule retains .debug_types
388 // and .rela.debug_types.
389 if (!hasAlloc)
390 return;
391
392 // Connect the members in a circular doubly-linked list via
393 // nextInSectionGroup.
394 InputSectionBase *head;
395 InputSectionBase *prev = nullptr;
396 for (uint32_t index : entries.slice(1)) {
397 InputSectionBase *s = sections[index];
398 if (!s || s == &InputSection::discarded)
399 continue;
400 if (prev)
401 prev->nextInSectionGroup = s;
402 else
403 head = s;
404 prev = s;
405 }
406 if (prev)
407 prev->nextInSectionGroup = head;
408}
409
410template <class ELFT> DWARFCache *ObjFile<ELFT>::getDwarf() {
411 llvm::call_once(initDwarf, [this]() {
412 dwarf = std::make_unique<DWARFCache>(std::make_unique<DWARFContext>(
413 std::make_unique<LLDDwarfObj<ELFT>>(this), "",
414 [&](Error err) { warn(getName() + ": " + toString(std::move(err))); },
415 [&](Error warning) {
416 warn(getName() + ": " + toString(std::move(warning)));
417 }));
418 });
419
420 return dwarf.get();
421}
422
423// Returns the pair of file name and line number describing location of data
424// object (variable, array, etc) definition.
425template <class ELFT>
426Optional<std::pair<std::string, unsigned>>
427ObjFile<ELFT>::getVariableLoc(StringRef name) {
428 return getDwarf()->getVariableLoc(name);
429}
430
431// Returns source line information for a given offset
432// using DWARF debug info.
433template <class ELFT>
434Optional<DILineInfo> ObjFile<ELFT>::getDILineInfo(InputSectionBase *s,
435 uint64_t offset) {
436 // Detect SectionIndex for specified section.
437 uint64_t sectionIndex = object::SectionedAddress::UndefSection;
438 ArrayRef<InputSectionBase *> sections = s->file->getSections();
439 for (uint64_t curIndex = 0; curIndex < sections.size(); ++curIndex) {
440 if (s == sections[curIndex]) {
441 sectionIndex = curIndex;
442 break;
443 }
444 }
445
446 return getDwarf()->getDILineInfo(offset, sectionIndex);
447}
448
449ELFFileBase::ELFFileBase(Kind k, ELFKind ekind, MemoryBufferRef mb)
450 : InputFile(k, mb) {
451 this->ekind = ekind;
452}
453
454template <typename Elf_Shdr>
455static const Elf_Shdr *findSection(ArrayRef<Elf_Shdr> sections, uint32_t type) {
456 for (const Elf_Shdr &sec : sections)
457 if (sec.sh_type == type)
458 return &sec;
459 return nullptr;
460}
461
462void ELFFileBase::init() {
463 switch (ekind) {
464 case ELF32LEKind:
465 init<ELF32LE>(fileKind);
466 break;
467 case ELF32BEKind:
468 init<ELF32BE>(fileKind);
469 break;
470 case ELF64LEKind:
471 init<ELF64LE>(fileKind);
472 break;
473 case ELF64BEKind:
474 init<ELF64BE>(fileKind);
475 break;
476 default:
477 llvm_unreachable("getELFKind")::llvm::llvm_unreachable_internal("getELFKind", "lld/ELF/InputFiles.cpp"
, 477)
;
478 }
479}
480
481template <class ELFT> void ELFFileBase::init(InputFile::Kind k) {
482 using Elf_Shdr = typename ELFT::Shdr;
483 using Elf_Sym = typename ELFT::Sym;
484
485 // Initialize trivial attributes.
486 const ELFFile<ELFT> &obj = getObj<ELFT>();
487 emachine = obj.getHeader().e_machine;
488 osabi = obj.getHeader().e_ident[llvm::ELF::EI_OSABI];
489 abiVersion = obj.getHeader().e_ident[llvm::ELF::EI_ABIVERSION];
490
491 ArrayRef<Elf_Shdr> sections = CHECK(obj.sections(), this)check2((obj.sections()), [&] { return toString(this); });
492 elfShdrs = sections.data();
493 numELFShdrs = sections.size();
494
495 // Find a symbol table.
496 const Elf_Shdr *symtabSec =
497 findSection(sections, k == SharedKind ? SHT_DYNSYM : SHT_SYMTAB);
498
499 if (!symtabSec)
500 return;
501
502 // Initialize members corresponding to a symbol table.
503 firstGlobal = symtabSec->sh_info;
504
505 ArrayRef<Elf_Sym> eSyms = CHECK(obj.symbols(symtabSec), this)check2((obj.symbols(symtabSec)), [&] { return toString(this
); })
;
506 if (firstGlobal == 0 || firstGlobal > eSyms.size())
507 fatal(toString(this) + ": invalid sh_info in symbol table");
508
509 elfSyms = reinterpret_cast<const void *>(eSyms.data());
510 numELFSyms = uint32_t(eSyms.size());
511 stringTable = CHECK(obj.getStringTableForSymtab(*symtabSec, sections), this)check2((obj.getStringTableForSymtab(*symtabSec, sections)), [
&] { return toString(this); })
;
512}
513
514template <class ELFT>
515uint32_t ObjFile<ELFT>::getSectionIndex(const Elf_Sym &sym) const {
516 return CHECK(check2((this->getObj().getSectionIndex(sym, getELFSyms<
ELFT>(), shndxTable)), [&] { return toString(this); })
517 this->getObj().getSectionIndex(sym, getELFSyms<ELFT>(), shndxTable),check2((this->getObj().getSectionIndex(sym, getELFSyms<
ELFT>(), shndxTable)), [&] { return toString(this); })
518 this)check2((this->getObj().getSectionIndex(sym, getELFSyms<
ELFT>(), shndxTable)), [&] { return toString(this); })
;
519}
520
521template <class ELFT> void ObjFile<ELFT>::parse(bool ignoreComdats) {
522 object::ELFFile<ELFT> obj = this->getObj();
523 // Read a section table. justSymbols is usually false.
524 if (this->justSymbols) {
525 initializeJustSymbols();
526 initializeSymbols(obj);
527 return;
528 }
529
530 // Handle dependent libraries and selection of section groups as these are not
531 // done in parallel.
532 ArrayRef<Elf_Shdr> objSections = getELFShdrs<ELFT>();
533 StringRef shstrtab = CHECK(obj.getSectionStringTable(objSections), this)check2((obj.getSectionStringTable(objSections)), [&] { return
toString(this); })
;
534 uint64_t size = objSections.size();
535 sections.resize(size);
536 for (size_t i = 0; i != size; ++i) {
537 const Elf_Shdr &sec = objSections[i];
538 if (sec.sh_type == SHT_LLVM_DEPENDENT_LIBRARIES && !config->relocatable) {
539 StringRef name = check(obj.getSectionName(sec, shstrtab));
540 ArrayRef<char> data = CHECK(check2((this->getObj().template getSectionContentsAsArray<
char>(sec)), [&] { return toString(this); })
541 this->getObj().template getSectionContentsAsArray<char>(sec), this)check2((this->getObj().template getSectionContentsAsArray<
char>(sec)), [&] { return toString(this); })
;
542 if (!data.empty() && data.back() != '\0') {
543 error(
544 toString(this) +
545 ": corrupted dependent libraries section (unterminated string): " +
546 name);
547 } else {
548 for (const char *d = data.begin(), *e = data.end(); d < e;) {
549 StringRef s(d);
550 addDependentLibrary(s, this);
551 d += s.size() + 1;
552 }
553 }
554 this->sections[i] = &InputSection::discarded;
555 continue;
556 }
557
558 if (sec.sh_type == SHT_ARM_ATTRIBUTES && config->emachine == EM_ARM) {
559 ARMAttributeParser attributes;
560 ArrayRef<uint8_t> contents =
561 check(this->getObj().getSectionContents(sec));
562 StringRef name = check(obj.getSectionName(sec, shstrtab));
563 this->sections[i] = &InputSection::discarded;
564 if (Error e =
565 attributes.parse(contents, ekind == ELF32LEKind ? support::little
566 : support::big)) {
567 InputSection isec(*this, sec, name);
568 warn(toString(&isec) + ": " + llvm::toString(std::move(e)));
569 } else {
570 updateSupportedARMFeatures(attributes);
571 updateARMVFPArgs(attributes, this);
572
573 // FIXME: Retain the first attribute section we see. The eglibc ARM
574 // dynamic loaders require the presence of an attribute section for
575 // dlopen to work. In a full implementation we would merge all attribute
576 // sections.
577 if (in.attributes == nullptr) {
578 in.attributes = std::make_unique<InputSection>(*this, sec, name);
579 this->sections[i] = in.attributes.get();
580 }
581 }
582 }
583
584 if (sec.sh_type == SHT_RISCV_ATTRIBUTES && config->emachine == EM_RISCV) {
585 RISCVAttributeParser attributes;
586 ArrayRef<uint8_t> contents =
587 check(this->getObj().getSectionContents(sec));
588 StringRef name = check(obj.getSectionName(sec, shstrtab));
589 this->sections[i] = &InputSection::discarded;
590 if (Error e = attributes.parse(contents, support::little)) {
591 InputSection isec(*this, sec, name);
592 warn(toString(&isec) + ": " + llvm::toString(std::move(e)));
593 } else {
594 // FIXME: Validate arch tag contains C if and only if EF_RISCV_RVC is
595 // present.
596
597 // FIXME: Retain the first attribute section we see. Tools such as
598 // llvm-objdump make use of the attribute section to determine which
599 // standard extensions to enable. In a full implementation we would
600 // merge all attribute sections.
601 if (in.attributes == nullptr) {
602 in.attributes = std::make_unique<InputSection>(*this, sec, name);
603 this->sections[i] = in.attributes.get();
604 }
605 }
606 }
607
608 if (sec.sh_type != SHT_GROUP)
609 continue;
610 StringRef signature = getShtGroupSignature(objSections, sec);
611 ArrayRef<Elf_Word> entries =
612 CHECK(obj.template getSectionContentsAsArray<Elf_Word>(sec), this)check2((obj.template getSectionContentsAsArray<Elf_Word>
(sec)), [&] { return toString(this); })
;
613 if (entries.empty())
614 fatal(toString(this) + ": empty SHT_GROUP");
615
616 Elf_Word flag = entries[0];
617 if (flag && flag != GRP_COMDAT)
618 fatal(toString(this) + ": unsupported SHT_GROUP format");
619
620 bool keepGroup =
621 (flag & GRP_COMDAT) == 0 || ignoreComdats ||
622 symtab.comdatGroups.try_emplace(CachedHashStringRef(signature), this)
623 .second;
624 if (keepGroup) {
625 if (config->relocatable)
626 this->sections[i] = createInputSection(
627 i, sec, check(obj.getSectionName(sec, shstrtab)));
628 continue;
629 }
630
631 // Otherwise, discard group members.
632 for (uint32_t secIndex : entries.slice(1)) {
633 if (secIndex >= size)
634 fatal(toString(this) +
635 ": invalid section index in group: " + Twine(secIndex));
636 this->sections[secIndex] = &InputSection::discarded;
637 }
638 }
639
640 // Read a symbol table.
641 initializeSymbols(obj);
642}
643
644// Sections with SHT_GROUP and comdat bits define comdat section groups.
645// They are identified and deduplicated by group name. This function
646// returns a group name.
647template <class ELFT>
648StringRef ObjFile<ELFT>::getShtGroupSignature(ArrayRef<Elf_Shdr> sections,
649 const Elf_Shdr &sec) {
650 typename ELFT::SymRange symbols = this->getELFSyms<ELFT>();
651 if (sec.sh_info >= symbols.size())
652 fatal(toString(this) + ": invalid symbol index");
653 const typename ELFT::Sym &sym = symbols[sec.sh_info];
654 return CHECK(sym.getName(this->stringTable), this)check2((sym.getName(this->stringTable)), [&] { return toString
(this); })
;
655}
656
657template <class ELFT>
658bool ObjFile<ELFT>::shouldMerge(const Elf_Shdr &sec, StringRef name) {
659 // On a regular link we don't merge sections if -O0 (default is -O1). This
660 // sometimes makes the linker significantly faster, although the output will
661 // be bigger.
662 //
663 // Doing the same for -r would create a problem as it would combine sections
664 // with different sh_entsize. One option would be to just copy every SHF_MERGE
665 // section as is to the output. While this would produce a valid ELF file with
666 // usable SHF_MERGE sections, tools like (llvm-)?dwarfdump get confused when
667 // they see two .debug_str. We could have separate logic for combining
668 // SHF_MERGE sections based both on their name and sh_entsize, but that seems
669 // to be more trouble than it is worth. Instead, we just use the regular (-O1)
670 // logic for -r.
671 if (config->optimize == 0 && !config->relocatable)
672 return false;
673
674 // A mergeable section with size 0 is useless because they don't have
675 // any data to merge. A mergeable string section with size 0 can be
676 // argued as invalid because it doesn't end with a null character.
677 // We'll avoid a mess by handling them as if they were non-mergeable.
678 if (sec.sh_size == 0)
679 return false;
680
681 // Check for sh_entsize. The ELF spec is not clear about the zero
682 // sh_entsize. It says that "the member [sh_entsize] contains 0 if
683 // the section does not hold a table of fixed-size entries". We know
684 // that Rust 1.13 produces a string mergeable section with a zero
685 // sh_entsize. Here we just accept it rather than being picky about it.
686 uint64_t entSize = sec.sh_entsize;
687 if (entSize == 0)
688 return false;
689 if (sec.sh_size % entSize)
690 fatal(toString(this) + ":(" + name + "): SHF_MERGE section size (" +
691 Twine(sec.sh_size) + ") must be a multiple of sh_entsize (" +
692 Twine(entSize) + ")");
693
694 if (sec.sh_flags & SHF_WRITE)
695 fatal(toString(this) + ":(" + name +
696 "): writable SHF_MERGE section is not supported");
697
698 return true;
699}
700
701// This is for --just-symbols.
702//
703// --just-symbols is a very minor feature that allows you to link your
704// output against other existing program, so that if you load both your
705// program and the other program into memory, your output can refer the
706// other program's symbols.
707//
708// When the option is given, we link "just symbols". The section table is
709// initialized with null pointers.
710template <class ELFT> void ObjFile<ELFT>::initializeJustSymbols() {
711 sections.resize(numELFShdrs);
712}
713
714template <class ELFT>
715void ObjFile<ELFT>::initializeSections(bool ignoreComdats,
716 const llvm::object::ELFFile<ELFT> &obj) {
717 ArrayRef<Elf_Shdr> objSections = getELFShdrs<ELFT>();
718 StringRef shstrtab = CHECK(obj.getSectionStringTable(objSections), this)check2((obj.getSectionStringTable(objSections)), [&] { return
toString(this); })
;
719 uint64_t size = objSections.size();
720 SmallVector<ArrayRef<Elf_Word>, 0> selectedGroups;
721 for (size_t i = 0; i != size; ++i) {
722 if (this->sections[i] == &InputSection::discarded)
723 continue;
724 const Elf_Shdr &sec = objSections[i];
725
726 // SHF_EXCLUDE'ed sections are discarded by the linker. However,
727 // if -r is given, we'll let the final link discard such sections.
728 // This is compatible with GNU.
729 if ((sec.sh_flags & SHF_EXCLUDE) && !config->relocatable) {
730 if (sec.sh_type == SHT_LLVM_CALL_GRAPH_PROFILE)
731 cgProfileSectionIndex = i;
732 if (sec.sh_type == SHT_LLVM_ADDRSIG) {
733 // We ignore the address-significance table if we know that the object
734 // file was created by objcopy or ld -r. This is because these tools
735 // will reorder the symbols in the symbol table, invalidating the data
736 // in the address-significance table, which refers to symbols by index.
737 if (sec.sh_link != 0)
738 this->addrsigSec = &sec;
739 else if (config->icf == ICFLevel::Safe)
740 warn(toString(this) +
741 ": --icf=safe conservatively ignores "
742 "SHT_LLVM_ADDRSIG [index " +
743 Twine(i) +
744 "] with sh_link=0 "
745 "(likely created using objcopy or ld -r)");
746 }
747 this->sections[i] = &InputSection::discarded;
748 continue;
749 }
750
751 switch (sec.sh_type) {
752 case SHT_GROUP: {
753 if (!config->relocatable)
754 sections[i] = &InputSection::discarded;
755 StringRef signature =
756 cantFail(this->getELFSyms<ELFT>()[sec.sh_info].getName(stringTable));
757 ArrayRef<Elf_Word> entries =
758 cantFail(obj.template getSectionContentsAsArray<Elf_Word>(sec));
759 if ((entries[0] & GRP_COMDAT) == 0 || ignoreComdats ||
760 symtab.comdatGroups.find(CachedHashStringRef(signature))->second ==
761 this)
762 selectedGroups.push_back(entries);
763 break;
764 }
765 case SHT_SYMTAB_SHNDX:
766 shndxTable = CHECK(obj.getSHNDXTable(sec, objSections), this)check2((obj.getSHNDXTable(sec, objSections)), [&] { return
toString(this); })
;
767 break;
768 case SHT_SYMTAB:
769 case SHT_STRTAB:
770 case SHT_REL:
771 case SHT_RELA:
772 case SHT_NULL:
773 break;
774 case SHT_LLVM_SYMPART:
775 ctx.hasSympart.store(true, std::memory_order_relaxed);
776 [[fallthrough]];
777 default:
778 this->sections[i] =
779 createInputSection(i, sec, check(obj.getSectionName(sec, shstrtab)));
780 }
781 }
782
783 // We have a second loop. It is used to:
784 // 1) handle SHF_LINK_ORDER sections.
785 // 2) create SHT_REL[A] sections. In some cases the section header index of a
786 // relocation section may be smaller than that of the relocated section. In
787 // such cases, the relocation section would attempt to reference a target
788 // section that has not yet been created. For simplicity, delay creation of
789 // relocation sections until now.
790 for (size_t i = 0; i != size; ++i) {
791 if (this->sections[i] == &InputSection::discarded)
792 continue;
793 const Elf_Shdr &sec = objSections[i];
794
795 if (sec.sh_type == SHT_REL || sec.sh_type == SHT_RELA) {
796 // Find a relocation target section and associate this section with that.
797 // Target may have been discarded if it is in a different section group
798 // and the group is discarded, even though it's a violation of the spec.
799 // We handle that situation gracefully by discarding dangling relocation
800 // sections.
801 const uint32_t info = sec.sh_info;
802 InputSectionBase *s = getRelocTarget(i, sec, info);
803 if (!s)
804 continue;
805
806 // ELF spec allows mergeable sections with relocations, but they are rare,
807 // and it is in practice hard to merge such sections by contents, because
808 // applying relocations at end of linking changes section contents. So, we
809 // simply handle such sections as non-mergeable ones. Degrading like this
810 // is acceptable because section merging is optional.
811 if (auto *ms = dyn_cast<MergeInputSection>(s)) {
812 s = makeThreadLocal<InputSection>(ms->file, ms->flags, ms->type,
813 ms->alignment, ms->data(), ms->name);
814 sections[info] = s;
815 }
816
817 if (s->relSecIdx != 0)
818 error(
819 toString(s) +
820 ": multiple relocation sections to one section are not supported");
821 s->relSecIdx = i;
822
823 // Relocation sections are usually removed from the output, so return
824 // `nullptr` for the normal case. However, if -r or --emit-relocs is
825 // specified, we need to copy them to the output. (Some post link analysis
826 // tools specify --emit-relocs to obtain the information.)
827 if (config->copyRelocs) {
828 auto *isec = makeThreadLocal<InputSection>(
829 *this, sec, check(obj.getSectionName(sec, shstrtab)));
830 // If the relocated section is discarded (due to /DISCARD/ or
831 // --gc-sections), the relocation section should be discarded as well.
832 s->dependentSections.push_back(isec);
833 sections[i] = isec;
834 }
835 continue;
836 }
837
838 // A SHF_LINK_ORDER section with sh_link=0 is handled as if it did not have
839 // the flag.
840 if (!sec.sh_link || !(sec.sh_flags & SHF_LINK_ORDER))
841 continue;
842
843 InputSectionBase *linkSec = nullptr;
844 if (sec.sh_link < size)
845 linkSec = this->sections[sec.sh_link];
846 if (!linkSec)
847 fatal(toString(this) + ": invalid sh_link index: " + Twine(sec.sh_link));
848
849 // A SHF_LINK_ORDER section is discarded if its linked-to section is
850 // discarded.
851 InputSection *isec = cast<InputSection>(this->sections[i]);
852 linkSec->dependentSections.push_back(isec);
853 if (!isa<InputSection>(linkSec))
854 error("a section " + isec->name +
855 " with SHF_LINK_ORDER should not refer a non-regular section: " +
856 toString(linkSec));
857 }
858
859 for (ArrayRef<Elf_Word> entries : selectedGroups)
860 handleSectionGroup<ELFT>(this->sections, entries);
861}
862
863// If a source file is compiled with x86 hardware-assisted call flow control
864// enabled, the generated object file contains feature flags indicating that
865// fact. This function reads the feature flags and returns it.
866//
867// Essentially we want to read a single 32-bit value in this function, but this
868// function is rather complicated because the value is buried deep inside a
869// .note.gnu.property section.
870//
871// The section consists of one or more NOTE records. Each NOTE record consists
872// of zero or more type-length-value fields. We want to find a field of a
873// certain type. It seems a bit too much to just store a 32-bit value, perhaps
874// the ABI is unnecessarily complicated.
875template <class ELFT> static uint32_t readAndFeatures(const InputSection &sec) {
876 using Elf_Nhdr = typename ELFT::Nhdr;
877 using Elf_Note = typename ELFT::Note;
878
879 uint32_t featuresSet = 0;
880 ArrayRef<uint8_t> data = sec.rawData;
881 auto reportFatal = [&](const uint8_t *place, const char *msg) {
882 fatal(toString(sec.file) + ":(" + sec.name + "+0x" +
883 Twine::utohexstr(place - sec.rawData.data()) + "): " + msg);
884 };
885 while (!data.empty()) {
886 // Read one NOTE record.
887 auto *nhdr = reinterpret_cast<const Elf_Nhdr *>(data.data());
888 if (data.size() < sizeof(Elf_Nhdr) || data.size() < nhdr->getSize())
889 reportFatal(data.data(), "data is too short");
890
891 Elf_Note note(*nhdr);
892 if (nhdr->n_type != NT_GNU_PROPERTY_TYPE_0 || note.getName() != "GNU") {
893 data = data.slice(nhdr->getSize());
894 continue;
895 }
896
897 uint32_t featureAndType = config->emachine == EM_AARCH64
898 ? GNU_PROPERTY_AARCH64_FEATURE_1_AND
899 : GNU_PROPERTY_X86_FEATURE_1_AND;
900
901 // Read a body of a NOTE record, which consists of type-length-value fields.
902 ArrayRef<uint8_t> desc = note.getDesc();
903 while (!desc.empty()) {
904 const uint8_t *place = desc.data();
905 if (desc.size() < 8)
906 reportFatal(place, "program property is too short");
907 uint32_t type = read32<ELFT::TargetEndianness>(desc.data());
908 uint32_t size = read32<ELFT::TargetEndianness>(desc.data() + 4);
909 desc = desc.slice(8);
910 if (desc.size() < size)
911 reportFatal(place, "program property is too short");
912
913 if (type == featureAndType) {
914 // We found a FEATURE_1_AND field. There may be more than one of these
915 // in a .note.gnu.property section, for a relocatable object we
916 // accumulate the bits set.
917 if (size < 4)
918 reportFatal(place, "FEATURE_1_AND entry is too short");
919 featuresSet |= read32<ELFT::TargetEndianness>(desc.data());
920 }
921
922 // Padding is present in the note descriptor, if necessary.
923 desc = desc.slice(alignTo<(ELFT::Is64Bits ? 8 : 4)>(size));
924 }
925
926 // Go to next NOTE record to look for more FEATURE_1_AND descriptions.
927 data = data.slice(nhdr->getSize());
928 }
929
930 return featuresSet;
931}
932
933template <class ELFT>
934InputSectionBase *ObjFile<ELFT>::getRelocTarget(uint32_t idx,
935 const Elf_Shdr &sec,
936 uint32_t info) {
937 if (info < this->sections.size()) {
938 InputSectionBase *target = this->sections[info];
939
940 // Strictly speaking, a relocation section must be included in the
941 // group of the section it relocates. However, LLVM 3.3 and earlier
942 // would fail to do so, so we gracefully handle that case.
943 if (target == &InputSection::discarded)
944 return nullptr;
945
946 if (target != nullptr)
947 return target;
948 }
949
950 error(toString(this) + Twine(": relocation section (index ") + Twine(idx) +
951 ") has invalid sh_info (" + Twine(info) + ")");
952 return nullptr;
953}
954
955// The function may be called concurrently for different input files. For
956// allocation, prefer makeThreadLocal which does not require holding a lock.
957template <class ELFT>
958InputSectionBase *ObjFile<ELFT>::createInputSection(uint32_t idx,
959 const Elf_Shdr &sec,
960 StringRef name) {
961 if (name.startswith(".n")) {
962 // The GNU linker uses .note.GNU-stack section as a marker indicating
963 // that the code in the object file does not expect that the stack is
964 // executable (in terms of NX bit). If all input files have the marker,
965 // the GNU linker adds a PT_GNU_STACK segment to tells the loader to
966 // make the stack non-executable. Most object files have this section as
967 // of 2017.
968 //
969 // But making the stack non-executable is a norm today for security
970 // reasons. Failure to do so may result in a serious security issue.
971 // Therefore, we make LLD always add PT_GNU_STACK unless it is
972 // explicitly told to do otherwise (by -z execstack). Because the stack
973 // executable-ness is controlled solely by command line options,
974 // .note.GNU-stack sections are simply ignored.
975 if (name == ".note.GNU-stack")
976 return &InputSection::discarded;
977
978 // Object files that use processor features such as Intel Control-Flow
979 // Enforcement (CET) or AArch64 Branch Target Identification BTI, use a
980 // .note.gnu.property section containing a bitfield of feature bits like the
981 // GNU_PROPERTY_X86_FEATURE_1_IBT flag. Read a bitmap containing the flag.
982 //
983 // Since we merge bitmaps from multiple object files to create a new
984 // .note.gnu.property containing a single AND'ed bitmap, we discard an input
985 // file's .note.gnu.property section.
986 if (name == ".note.gnu.property") {
987 this->andFeatures = readAndFeatures<ELFT>(InputSection(*this, sec, name));
988 return &InputSection::discarded;
989 }
990
991 // Split stacks is a feature to support a discontiguous stack,
992 // commonly used in the programming language Go. For the details,
993 // see https://gcc.gnu.org/wiki/SplitStacks. An object file compiled
994 // for split stack will include a .note.GNU-split-stack section.
995 if (name == ".note.GNU-split-stack") {
996 if (config->relocatable) {
997 error(
998 "cannot mix split-stack and non-split-stack in a relocatable link");
999 return &InputSection::discarded;
1000 }
1001 this->splitStack = true;
1002 return &InputSection::discarded;
1003 }
1004
1005 // An object file compiled for split stack, but where some of the
1006 // functions were compiled with the no_split_stack_attribute will
1007 // include a .note.GNU-no-split-stack section.
1008 if (name == ".note.GNU-no-split-stack") {
1009 this->someNoSplitStack = true;
1010 return &InputSection::discarded;
1011 }
1012
1013 // Strip existing .note.gnu.build-id sections so that the output won't have
1014 // more than one build-id. This is not usually a problem because input
1015 // object files normally don't have .build-id sections, but you can create
1016 // such files by "ld.{bfd,gold,lld} -r --build-id", and we want to guard
1017 // against it.
1018 if (name == ".note.gnu.build-id")
1019 return &InputSection::discarded;
1020 }
1021
1022 // The linker merges EH (exception handling) frames and creates a
1023 // .eh_frame_hdr section for runtime. So we handle them with a special
1024 // class. For relocatable outputs, they are just passed through.
1025 if (name == ".eh_frame" && !config->relocatable)
1026 return makeThreadLocal<EhInputSection>(*this, sec, name);
1027
1028 if ((sec.sh_flags & SHF_MERGE) && shouldMerge(sec, name))
1029 return makeThreadLocal<MergeInputSection>(*this, sec, name);
1030 return makeThreadLocal<InputSection>(*this, sec, name);
1031}
1032
1033// Initialize this->Symbols. this->Symbols is a parallel array as
1034// its corresponding ELF symbol table.
1035template <class ELFT>
1036void ObjFile<ELFT>::initializeSymbols(const object::ELFFile<ELFT> &obj) {
1037 ArrayRef<Elf_Sym> eSyms = this->getELFSyms<ELFT>();
1038 symbols.resize(eSyms.size());
1039
1040 // Some entries have been filled by LazyObjFile.
1041 for (size_t i = firstGlobal, end = eSyms.size(); i != end; ++i)
1042 if (!symbols[i])
1043 symbols[i] = symtab.insert(CHECK(eSyms[i].getName(stringTable), this)check2((eSyms[i].getName(stringTable)), [&] { return toString
(this); })
);
1044
1045 // Perform symbol resolution on non-local symbols.
1046 SmallVector<unsigned, 32> undefineds;
1047 for (size_t i = firstGlobal, end = eSyms.size(); i != end; ++i) {
1048 const Elf_Sym &eSym = eSyms[i];
1049 uint32_t secIdx = eSym.st_shndx;
1050 if (secIdx == SHN_UNDEF) {
1051 undefineds.push_back(i);
1052 continue;
1053 }
1054
1055 uint8_t binding = eSym.getBinding();
1056 uint8_t stOther = eSym.st_other;
1057 uint8_t type = eSym.getType();
1058 uint64_t value = eSym.st_value;
1059 uint64_t size = eSym.st_size;
1060
1061 Symbol *sym = symbols[i];
1062 sym->isUsedInRegularObj = true;
1063 if (LLVM_UNLIKELY(eSym.st_shndx == SHN_COMMON)__builtin_expect((bool)(eSym.st_shndx == SHN_COMMON), false)) {
1064 if (value == 0 || value >= UINT32_MAX(4294967295U))
1065 fatal(toString(this) + ": common symbol '" + sym->getName() +
1066 "' has invalid alignment: " + Twine(value));
1067 hasCommonSyms = true;
1068 sym->resolve(
1069 CommonSymbol{this, StringRef(), binding, stOther, type, value, size});
1070 continue;
1071 }
1072
1073 // Handle global defined symbols. Defined::section will be set in postParse.
1074 sym->resolve(Defined{this, StringRef(), binding, stOther, type, value, size,
1075 nullptr});
1076 }
1077
1078 // Undefined symbols (excluding those defined relative to non-prevailing
1079 // sections) can trigger recursive extract. Process defined symbols first so
1080 // that the relative order between a defined symbol and an undefined symbol
1081 // does not change the symbol resolution behavior. In addition, a set of
1082 // interconnected symbols will all be resolved to the same file, instead of
1083 // being resolved to different files.
1084 for (unsigned i : undefineds) {
1085 const Elf_Sym &eSym = eSyms[i];
1086 Symbol *sym = symbols[i];
1087 sym->resolve(Undefined{this, StringRef(), eSym.getBinding(), eSym.st_other,
1088 eSym.getType()});
1089 sym->isUsedInRegularObj = true;
1090 sym->referenced = true;
1091 }
1092}
1093
1094template <class ELFT>
1095void ObjFile<ELFT>::initSectionsAndLocalSyms(bool ignoreComdats) {
1096 if (!justSymbols)
1097 initializeSections(ignoreComdats, getObj());
1098
1099 if (!firstGlobal)
1100 return;
1101 SymbolUnion *locals = makeThreadLocalN<SymbolUnion>(firstGlobal);
1102 memset(locals, 0, sizeof(SymbolUnion) * firstGlobal);
1103
1104 ArrayRef<Elf_Sym> eSyms = this->getELFSyms<ELFT>();
1105 for (size_t i = 0, end = firstGlobal; i != end; ++i) {
1106 const Elf_Sym &eSym = eSyms[i];
1107 uint32_t secIdx = eSym.st_shndx;
1108 if (LLVM_UNLIKELY(secIdx == SHN_XINDEX)__builtin_expect((bool)(secIdx == SHN_XINDEX), false))
1109 secIdx = check(getExtendedSymbolTableIndex<ELFT>(eSym, i, shndxTable));
1110 else if (secIdx >= SHN_LORESERVE)
1111 secIdx = 0;
1112 if (LLVM_UNLIKELY(secIdx >= sections.size())__builtin_expect((bool)(secIdx >= sections.size()), false))
1113 fatal(toString(this) + ": invalid section index: " + Twine(secIdx));
1114 if (LLVM_UNLIKELY(eSym.getBinding() != STB_LOCAL)__builtin_expect((bool)(eSym.getBinding() != STB_LOCAL), false
)
)
1115 error(toString(this) + ": non-local symbol (" + Twine(i) +
1116 ") found at index < .symtab's sh_info (" + Twine(end) + ")");
1117
1118 InputSectionBase *sec = sections[secIdx];
1119 uint8_t type = eSym.getType();
1120 if (type == STT_FILE)
1121 sourceFile = CHECK(eSym.getName(stringTable), this)check2((eSym.getName(stringTable)), [&] { return toString
(this); })
;
1122 if (LLVM_UNLIKELY(stringTable.size() <= eSym.st_name)__builtin_expect((bool)(stringTable.size() <= eSym.st_name
), false)
)
1123 fatal(toString(this) + ": invalid symbol name offset");
1124 StringRef name(stringTable.data() + eSym.st_name);
1125
1126 symbols[i] = reinterpret_cast<Symbol *>(locals + i);
1127 if (eSym.st_shndx == SHN_UNDEF || sec == &InputSection::discarded)
1128 new (symbols[i]) Undefined(this, name, STB_LOCAL, eSym.st_other, type,
1129 /*discardedSecIdx=*/secIdx);
1130 else
1131 new (symbols[i]) Defined(this, name, STB_LOCAL, eSym.st_other, type,
1132 eSym.st_value, eSym.st_size, sec);
1133 symbols[i]->partition = 1;
1134 symbols[i]->isUsedInRegularObj = true;
1135 }
1136}
1137
1138// Called after all ObjFile::parse is called for all ObjFiles. This checks
1139// duplicate symbols and may do symbol property merge in the future.
1140template <class ELFT> void ObjFile<ELFT>::postParse() {
1141 static std::mutex mu;
1142 ArrayRef<Elf_Sym> eSyms = this->getELFSyms<ELFT>();
1143 for (size_t i = firstGlobal, end = eSyms.size(); i != end; ++i) {
1144 const Elf_Sym &eSym = eSyms[i];
1145 Symbol &sym = *symbols[i];
1146 uint32_t secIdx = eSym.st_shndx;
1147 uint8_t binding = eSym.getBinding();
1148 if (LLVM_UNLIKELY(binding != STB_GLOBAL && binding != STB_WEAK &&__builtin_expect((bool)(binding != STB_GLOBAL && binding
!= STB_WEAK && binding != STB_GNU_UNIQUE), false)
1149 binding != STB_GNU_UNIQUE)__builtin_expect((bool)(binding != STB_GLOBAL && binding
!= STB_WEAK && binding != STB_GNU_UNIQUE), false)
)
1150 errorOrWarn(toString(this) + ": symbol (" + Twine(i) +
1151 ") has invalid binding: " + Twine((int)binding));
1152
1153 // st_value of STT_TLS represents the assigned offset, not the actual
1154 // address which is used by STT_FUNC and STT_OBJECT. STT_TLS symbols can
1155 // only be referenced by special TLS relocations. It is usually an error if
1156 // a STT_TLS symbol is replaced by a non-STT_TLS symbol, vice versa.
1157 if (LLVM_UNLIKELY(sym.isTls())__builtin_expect((bool)(sym.isTls()), false) && eSym.getType() != STT_TLS &&
1158 eSym.getType() != STT_NOTYPE)
1159 errorOrWarn("TLS attribute mismatch: " + toString(sym) + "\n>>> in " +
1160 toString(sym.file) + "\n>>> in " + toString(this));
1161
1162 // Handle non-COMMON defined symbol below. !sym.file allows a symbol
1163 // assignment to redefine a symbol without an error.
1164 if (!sym.file || !sym.isDefined() || secIdx == SHN_UNDEF ||
1165 secIdx == SHN_COMMON)
1166 continue;
1167
1168 if (LLVM_UNLIKELY(secIdx == SHN_XINDEX)__builtin_expect((bool)(secIdx == SHN_XINDEX), false))
1169 secIdx = check(getExtendedSymbolTableIndex<ELFT>(eSym, i, shndxTable));
1170 else if (secIdx >= SHN_LORESERVE)
1171 secIdx = 0;
1172 if (LLVM_UNLIKELY(secIdx >= sections.size())__builtin_expect((bool)(secIdx >= sections.size()), false))
1173 fatal(toString(this) + ": invalid section index: " + Twine(secIdx));
1174 InputSectionBase *sec = sections[secIdx];
1175 if (sec == &InputSection::discarded) {
1176 if (sym.traced) {
1177 printTraceSymbol(Undefined{this, sym.getName(), sym.binding,
1178 sym.stOther, sym.type, secIdx},
1179 sym.getName());
1180 }
1181 if (sym.file == this) {
1182 std::lock_guard<std::mutex> lock(mu);
1183 ctx.nonPrevailingSyms.emplace_back(&sym, secIdx);
1184 }
1185 continue;
1186 }
1187
1188 if (sym.file == this) {
1189 cast<Defined>(sym).section = sec;
1190 continue;
1191 }
1192
1193 if (binding == STB_WEAK)
1194 continue;
1195 std::lock_guard<std::mutex> lock(mu);
1196 ctx.duplicates.push_back({&sym, this, sec, eSym.st_value});
1197 }
1198}
1199
1200// The handling of tentative definitions (COMMON symbols) in archives is murky.
1201// A tentative definition will be promoted to a global definition if there are
1202// no non-tentative definitions to dominate it. When we hold a tentative
1203// definition to a symbol and are inspecting archive members for inclusion
1204// there are 2 ways we can proceed:
1205//
1206// 1) Consider the tentative definition a 'real' definition (ie promotion from
1207// tentative to real definition has already happened) and not inspect
1208// archive members for Global/Weak definitions to replace the tentative
1209// definition. An archive member would only be included if it satisfies some
1210// other undefined symbol. This is the behavior Gold uses.
1211//
1212// 2) Consider the tentative definition as still undefined (ie the promotion to
1213// a real definition happens only after all symbol resolution is done).
1214// The linker searches archive members for STB_GLOBAL definitions to
1215// replace the tentative definition with. This is the behavior used by
1216// GNU ld.
1217//
1218// The second behavior is inherited from SysVR4, which based it on the FORTRAN
1219// COMMON BLOCK model. This behavior is needed for proper initialization in old
1220// (pre F90) FORTRAN code that is packaged into an archive.
1221//
1222// The following functions search archive members for definitions to replace
1223// tentative definitions (implementing behavior 2).
1224static bool isBitcodeNonCommonDef(MemoryBufferRef mb, StringRef symName,
1225 StringRef archiveName) {
1226 IRSymtabFile symtabFile = check(readIRSymtab(mb));
1227 for (const irsymtab::Reader::SymbolRef &sym :
1228 symtabFile.TheReader.symbols()) {
1229 if (sym.isGlobal() && sym.getName() == symName)
1230 return !sym.isUndefined() && !sym.isWeak() && !sym.isCommon();
1231 }
1232 return false;
1233}
1234
1235template <class ELFT>
1236static bool isNonCommonDef(ELFKind ekind, MemoryBufferRef mb, StringRef symName,
1237 StringRef archiveName) {
1238 ObjFile<ELFT> *obj = make<ObjFile<ELFT>>(ekind, mb, archiveName);
1239 obj->init();
1240 StringRef stringtable = obj->getStringTable();
1241
1242 for (auto sym : obj->template getGlobalELFSyms<ELFT>()) {
1243 Expected<StringRef> name = sym.getName(stringtable);
1244 if (name && name.get() == symName)
1245 return sym.isDefined() && sym.getBinding() == STB_GLOBAL &&
1246 !sym.isCommon();
1247 }
1248 return false;
1249}
1250
1251static bool isNonCommonDef(MemoryBufferRef mb, StringRef symName,
1252 StringRef archiveName) {
1253 switch (getELFKind(mb, archiveName)) {
1254 case ELF32LEKind:
1255 return isNonCommonDef<ELF32LE>(ELF32LEKind, mb, symName, archiveName);
1256 case ELF32BEKind:
1257 return isNonCommonDef<ELF32BE>(ELF32BEKind, mb, symName, archiveName);
1258 case ELF64LEKind:
1259 return isNonCommonDef<ELF64LE>(ELF64LEKind, mb, symName, archiveName);
1260 case ELF64BEKind:
1261 return isNonCommonDef<ELF64BE>(ELF64BEKind, mb, symName, archiveName);
1262 default:
1263 llvm_unreachable("getELFKind")::llvm::llvm_unreachable_internal("getELFKind", "lld/ELF/InputFiles.cpp"
, 1263)
;
1264 }
1265}
1266
1267unsigned SharedFile::vernauxNum;
1268
1269SharedFile::SharedFile(MemoryBufferRef m, StringRef defaultSoName)
1270 : ELFFileBase(SharedKind, getELFKind(m, ""), m), soName(defaultSoName),
1271 isNeeded(!config->asNeeded) {}
1272
1273// Parse the version definitions in the object file if present, and return a
1274// vector whose nth element contains a pointer to the Elf_Verdef for version
1275// identifier n. Version identifiers that are not definitions map to nullptr.
1276template <typename ELFT>
1277static SmallVector<const void *, 0>
1278parseVerdefs(const uint8_t *base, const typename ELFT::Shdr *sec) {
1279 if (!sec)
1280 return {};
1281
1282 // Build the Verdefs array by following the chain of Elf_Verdef objects
1283 // from the start of the .gnu.version_d section.
1284 SmallVector<const void *, 0> verdefs;
1285 const uint8_t *verdef = base + sec->sh_offset;
1286 for (unsigned i = 0, e = sec->sh_info; i != e; ++i) {
1287 auto *curVerdef = reinterpret_cast<const typename ELFT::Verdef *>(verdef);
1288 verdef += curVerdef->vd_next;
1289 unsigned verdefIndex = curVerdef->vd_ndx;
1290 if (verdefIndex >= verdefs.size())
1291 verdefs.resize(verdefIndex + 1);
1292 verdefs[verdefIndex] = curVerdef;
1293 }
1294 return verdefs;
1295}
1296
1297// Parse SHT_GNU_verneed to properly set the name of a versioned undefined
1298// symbol. We detect fatal issues which would cause vulnerabilities, but do not
1299// implement sophisticated error checking like in llvm-readobj because the value
1300// of such diagnostics is low.
1301template <typename ELFT>
1302std::vector<uint32_t> SharedFile::parseVerneed(const ELFFile<ELFT> &obj,
1303 const typename ELFT::Shdr *sec) {
1304 if (!sec)
1305 return {};
1306 std::vector<uint32_t> verneeds;
1307 ArrayRef<uint8_t> data = CHECK(obj.getSectionContents(*sec), this)check2((obj.getSectionContents(*sec)), [&] { return toString
(this); })
;
1308 const uint8_t *verneedBuf = data.begin();
1309 for (unsigned i = 0; i != sec->sh_info; ++i) {
1310 if (verneedBuf + sizeof(typename ELFT::Verneed) > data.end())
1311 fatal(toString(this) + " has an invalid Verneed");
1312 auto *vn = reinterpret_cast<const typename ELFT::Verneed *>(verneedBuf);
1313 const uint8_t *vernauxBuf = verneedBuf + vn->vn_aux;
1314 for (unsigned j = 0; j != vn->vn_cnt; ++j) {
1315 if (vernauxBuf + sizeof(typename ELFT::Vernaux) > data.end())
1316 fatal(toString(this) + " has an invalid Vernaux");
1317 auto *aux = reinterpret_cast<const typename ELFT::Vernaux *>(vernauxBuf);
1318 if (aux->vna_name >= this->stringTable.size())
1319 fatal(toString(this) + " has a Vernaux with an invalid vna_name");
1320 uint16_t version = aux->vna_other & VERSYM_VERSION;
1321 if (version >= verneeds.size())
1322 verneeds.resize(version + 1);
1323 verneeds[version] = aux->vna_name;
1324 vernauxBuf += aux->vna_next;
1325 }
1326 verneedBuf += vn->vn_next;
1327 }
1328 return verneeds;
1329}
1330
1331// We do not usually care about alignments of data in shared object
1332// files because the loader takes care of it. However, if we promote a
1333// DSO symbol to point to .bss due to copy relocation, we need to keep
1334// the original alignment requirements. We infer it in this function.
1335template <typename ELFT>
1336static uint64_t getAlignment(ArrayRef<typename ELFT::Shdr> sections,
1337 const typename ELFT::Sym &sym) {
1338 uint64_t ret = UINT64_MAX(18446744073709551615UL);
1339 if (sym.st_value)
23
Assuming the condition is true
24
Taking true branch
1340 ret = 1ULL << countTrailingZeros((uint64_t)sym.st_value);
25
Calling 'countTrailingZeros<unsigned long>'
32
Returning from 'countTrailingZeros<unsigned long>'
33
The result of the left shift is undefined due to shifting by '64', which is greater or equal to the width of type 'unsigned long long'
1341 if (0 < sym.st_shndx && sym.st_shndx < sections.size())
1342 ret = std::min<uint64_t>(ret, sections[sym.st_shndx].sh_addralign);
1343 return (ret > UINT32_MAX(4294967295U)) ? 0 : ret;
1344}
1345
1346// Fully parse the shared object file.
1347//
1348// This function parses symbol versions. If a DSO has version information,
1349// the file has a ".gnu.version_d" section which contains symbol version
1350// definitions. Each symbol is associated to one version through a table in
1351// ".gnu.version" section. That table is a parallel array for the symbol
1352// table, and each table entry contains an index in ".gnu.version_d".
1353//
1354// The special index 0 is reserved for VERF_NDX_LOCAL and 1 is for
1355// VER_NDX_GLOBAL. There's no table entry for these special versions in
1356// ".gnu.version_d".
1357//
1358// The file format for symbol versioning is perhaps a bit more complicated
1359// than necessary, but you can easily understand the code if you wrap your
1360// head around the data structure described above.
1361template <class ELFT> void SharedFile::parse() {
1362 using Elf_Dyn = typename ELFT::Dyn;
1363 using Elf_Shdr = typename ELFT::Shdr;
1364 using Elf_Sym = typename ELFT::Sym;
1365 using Elf_Verdef = typename ELFT::Verdef;
1366 using Elf_Versym = typename ELFT::Versym;
1367
1368 ArrayRef<Elf_Dyn> dynamicTags;
1369 const ELFFile<ELFT> obj = this->getObj<ELFT>();
1370 ArrayRef<Elf_Shdr> sections = getELFShdrs<ELFT>();
1371
1372 const Elf_Shdr *versymSec = nullptr;
1373 const Elf_Shdr *verdefSec = nullptr;
1374 const Elf_Shdr *verneedSec = nullptr;
1375
1376 // Search for .dynsym, .dynamic, .symtab, .gnu.version and .gnu.version_d.
1377 for (const Elf_Shdr &sec : sections) {
11
Assuming '__begin0' is equal to '__end0'
1378 switch (sec.sh_type) {
1379 default:
1380 continue;
1381 case SHT_DYNAMIC:
1382 dynamicTags =
1383 CHECK(obj.template getSectionContentsAsArray<Elf_Dyn>(sec), this)check2((obj.template getSectionContentsAsArray<Elf_Dyn>
(sec)), [&] { return toString(this); })
;
1384 break;
1385 case SHT_GNU_versym:
1386 versymSec = &sec;
1387 break;
1388 case SHT_GNU_verdef:
1389 verdefSec = &sec;
1390 break;
1391 case SHT_GNU_verneed:
1392 verneedSec = &sec;
1393 break;
1394 }
1395 }
1396
1397 if (versymSec
11.1
'versymSec' is null
11.1
'versymSec' is null
&& numELFSyms == 0) {
1398 error("SHT_GNU_versym should be associated with symbol table");
1399 return;
1400 }
1401
1402 // Search for a DT_SONAME tag to initialize this->soName.
1403 for (const Elf_Dyn &dyn : dynamicTags) {
12
Assuming '__begin0' is equal to '__end0'
1404 if (dyn.d_tag == DT_NEEDED) {
1405 uint64_t val = dyn.getVal();
1406 if (val >= this->stringTable.size())
1407 fatal(toString(this) + ": invalid DT_NEEDED entry");
1408 dtNeeded.push_back(this->stringTable.data() + val);
1409 } else if (dyn.d_tag == DT_SONAME) {
1410 uint64_t val = dyn.getVal();
1411 if (val >= this->stringTable.size())
1412 fatal(toString(this) + ": invalid DT_SONAME entry");
1413 soName = this->stringTable.data() + val;
1414 }
1415 }
1416
1417 // DSOs are uniquified not by filename but by soname.
1418 DenseMap<CachedHashStringRef, SharedFile *>::iterator it;
1419 bool wasInserted;
1420 std::tie(it, wasInserted) =
1421 symtab.soNames.try_emplace(CachedHashStringRef(soName), this);
1422
1423 // If a DSO appears more than once on the command line with and without
1424 // --as-needed, --no-as-needed takes precedence over --as-needed because a
1425 // user can add an extra DSO with --no-as-needed to force it to be added to
1426 // the dependency list.
1427 it->second->isNeeded |= isNeeded;
1428 if (!wasInserted)
13
Assuming 'wasInserted' is true
14
Taking false branch
1429 return;
1430
1431 ctx.sharedFiles.push_back(this);
1432
1433 verdefs = parseVerdefs<ELFT>(obj.base(), verdefSec);
1434 std::vector<uint32_t> verneeds = parseVerneed<ELFT>(obj, verneedSec);
1435
1436 // Parse ".gnu.version" section which is a parallel array for the symbol
1437 // table. If a given file doesn't have a ".gnu.version" section, we use
1438 // VER_NDX_GLOBAL.
1439 size_t size = numELFSyms - firstGlobal;
1440 std::vector<uint16_t> versyms(size, VER_NDX_GLOBAL);
1441 if (versymSec
14.1
'versymSec' is null
14.1
'versymSec' is null
) {
15
Taking false branch
1442 ArrayRef<Elf_Versym> versym =
1443 CHECK(obj.template getSectionContentsAsArray<Elf_Versym>(*versymSec),check2((obj.template getSectionContentsAsArray<Elf_Versym>
(*versymSec)), [&] { return toString(this); })
1444 this)check2((obj.template getSectionContentsAsArray<Elf_Versym>
(*versymSec)), [&] { return toString(this); })
1445 .slice(firstGlobal);
1446 for (size_t i = 0; i < size; ++i)
1447 versyms[i] = versym[i].vs_index;
1448 }
1449
1450 // System libraries can have a lot of symbols with versions. Using a
1451 // fixed buffer for computing the versions name (foo@ver) can save a
1452 // lot of allocations.
1453 SmallString<0> versionedNameBuffer;
1454
1455 // Add symbols to the symbol table.
1456 ArrayRef<Elf_Sym> syms = this->getGlobalELFSyms<ELFT>();
1457 for (size_t i = 0, e = syms.size(); i != e; ++i) {
16
Assuming 'i' is not equal to 'e'
17
Loop condition is true. Entering loop body
1458 const Elf_Sym &sym = syms[i];
1459
1460 // ELF spec requires that all local symbols precede weak or global
1461 // symbols in each symbol table, and the index of first non-local symbol
1462 // is stored to sh_info. If a local symbol appears after some non-local
1463 // symbol, that's a violation of the spec.
1464 StringRef name = CHECK(sym.getName(stringTable), this)check2((sym.getName(stringTable)), [&] { return toString(
this); })
;
1465 if (sym.getBinding() == STB_LOCAL) {
18
Assuming the condition is false
19
Taking false branch
1466 errorOrWarn(toString(this) + ": invalid local symbol '" + name +
1467 "' in global part of symbol table");
1468 continue;
1469 }
1470
1471 const uint16_t ver = versyms[i], idx = ver & ~VERSYM_HIDDEN;
1472 if (sym.isUndefined()) {
1473 // For unversioned undefined symbols, VER_NDX_GLOBAL makes more sense but
1474 // as of binutils 2.34, GNU ld produces VER_NDX_LOCAL.
1475 if (ver != VER_NDX_LOCAL && ver != VER_NDX_GLOBAL) {
1476 if (idx >= verneeds.size()) {
1477 error("corrupt input file: version need index " + Twine(idx) +
1478 " for symbol " + name + " is out of bounds\n>>> defined in " +
1479 toString(this));
1480 continue;
1481 }
1482 StringRef verName = stringTable.data() + verneeds[idx];
1483 versionedNameBuffer.clear();
1484 name = saver().save(
1485 (name + "@" + verName).toStringRef(versionedNameBuffer));
1486 }
1487 Symbol *s = symtab.addSymbol(
1488 Undefined{this, name, sym.getBinding(), sym.st_other, sym.getType()});
1489 s->exportDynamic = true;
1490 if (s->isUndefined() && sym.getBinding() != STB_WEAK &&
1491 config->unresolvedSymbolsInShlib != UnresolvedPolicy::Ignore)
1492 requiredSymbols.push_back(s);
1493 continue;
1494 }
1495
1496 if (ver == VER_NDX_LOCAL ||
20
Assuming 'ver' is not equal to VER_NDX_LOCAL
1497 (ver != VER_NDX_GLOBAL && idx >= verdefs.size())) {
21
Assuming 'ver' is equal to VER_NDX_GLOBAL
1498 // In GNU ld < 2.31 (before 3be08ea4728b56d35e136af4e6fd3086ade17764), the
1499 // MIPS port puts _gp_disp symbol into DSO files and incorrectly assigns
1500 // VER_NDX_LOCAL. Workaround this bug.
1501 if (config->emachine == EM_MIPS && name == "_gp_disp")
1502 continue;
1503 error("corrupt input file: version definition index " + Twine(idx) +
1504 " for symbol " + name + " is out of bounds\n>>> defined in " +
1505 toString(this));
1506 continue;
1507 }
1508
1509 uint32_t alignment = getAlignment<ELFT>(sections, sym);
22
Calling 'getAlignment<llvm::object::ELFType<llvm::support::little, false>>'
1510 if (ver == idx) {
1511 auto *s = symtab.addSymbol(
1512 SharedSymbol{*this, name, sym.getBinding(), sym.st_other,
1513 sym.getType(), sym.st_value, sym.st_size, alignment});
1514 if (s->file == this)
1515 s->verdefIndex = ver;
1516 }
1517
1518 // Also add the symbol with the versioned name to handle undefined symbols
1519 // with explicit versions.
1520 if (ver == VER_NDX_GLOBAL)
1521 continue;
1522
1523 StringRef verName =
1524 stringTable.data() +
1525 reinterpret_cast<const Elf_Verdef *>(verdefs[idx])->getAux()->vda_name;
1526 versionedNameBuffer.clear();
1527 name = (name + "@" + verName).toStringRef(versionedNameBuffer);
1528 auto *s = symtab.addSymbol(
1529 SharedSymbol{*this, saver().save(name), sym.getBinding(), sym.st_other,
1530 sym.getType(), sym.st_value, sym.st_size, alignment});
1531 if (s->file == this)
1532 s->verdefIndex = idx;
1533 }
1534}
1535
1536static ELFKind getBitcodeELFKind(const Triple &t) {
1537 if (t.isLittleEndian())
1538 return t.isArch64Bit() ? ELF64LEKind : ELF32LEKind;
1539 return t.isArch64Bit() ? ELF64BEKind : ELF32BEKind;
1540}
1541
1542static uint16_t getBitcodeMachineKind(StringRef path, const Triple &t) {
1543 switch (t.getArch()) {
1544 case Triple::aarch64:
1545 case Triple::aarch64_be:
1546 return EM_AARCH64;
1547 case Triple::amdgcn:
1548 case Triple::r600:
1549 return EM_AMDGPU;
1550 case Triple::arm:
1551 case Triple::thumb:
1552 return EM_ARM;
1553 case Triple::avr:
1554 return EM_AVR;
1555 case Triple::hexagon:
1556 return EM_HEXAGON;
1557 case Triple::mips:
1558 case Triple::mipsel:
1559 case Triple::mips64:
1560 case Triple::mips64el:
1561 return EM_MIPS;
1562 case Triple::msp430:
1563 return EM_MSP430;
1564 case Triple::ppc:
1565 case Triple::ppcle:
1566 return EM_PPC;
1567 case Triple::ppc64:
1568 case Triple::ppc64le:
1569 return EM_PPC64;
1570 case Triple::riscv32:
1571 case Triple::riscv64:
1572 return EM_RISCV;
1573 case Triple::x86:
1574 return t.isOSIAMCU() ? EM_IAMCU : EM_386;
1575 case Triple::x86_64:
1576 return EM_X86_64;
1577 default:
1578 error(path + ": could not infer e_machine from bitcode target triple " +
1579 t.str());
1580 return EM_NONE;
1581 }
1582}
1583
1584static uint8_t getOsAbi(const Triple &t) {
1585 switch (t.getOS()) {
1586 case Triple::AMDHSA:
1587 return ELF::ELFOSABI_AMDGPU_HSA;
1588 case Triple::AMDPAL:
1589 return ELF::ELFOSABI_AMDGPU_PAL;
1590 case Triple::Mesa3D:
1591 return ELF::ELFOSABI_AMDGPU_MESA3D;
1592 default:
1593 return ELF::ELFOSABI_NONE;
1594 }
1595}
1596
1597BitcodeFile::BitcodeFile(MemoryBufferRef mb, StringRef archiveName,
1598 uint64_t offsetInArchive, bool lazy)
1599 : InputFile(BitcodeKind, mb) {
1600 this->archiveName = archiveName;
1601 this->lazy = lazy;
1602
1603 std::string path = mb.getBufferIdentifier().str();
1604 if (config->thinLTOIndexOnly)
1605 path = replaceThinLTOSuffix(mb.getBufferIdentifier());
1606
1607 // ThinLTO assumes that all MemoryBufferRefs given to it have a unique
1608 // name. If two archives define two members with the same name, this
1609 // causes a collision which result in only one of the objects being taken
1610 // into consideration at LTO time (which very likely causes undefined
1611 // symbols later in the link stage). So we append file offset to make
1612 // filename unique.
1613 StringRef name = archiveName.empty()
1614 ? saver().save(path)
1615 : saver().save(archiveName + "(" + path::filename(path) +
1616 " at " + utostr(offsetInArchive) + ")");
1617 MemoryBufferRef mbref(mb.getBuffer(), name);
1618
1619 obj = CHECK(lto::InputFile::create(mbref), this)check2((lto::InputFile::create(mbref)), [&] { return toString
(this); })
;
1620
1621 Triple t(obj->getTargetTriple());
1622 ekind = getBitcodeELFKind(t);
1623 emachine = getBitcodeMachineKind(mb.getBufferIdentifier(), t);
1624 osabi = getOsAbi(t);
1625}
1626
1627static uint8_t mapVisibility(GlobalValue::VisibilityTypes gvVisibility) {
1628 switch (gvVisibility) {
1629 case GlobalValue::DefaultVisibility:
1630 return STV_DEFAULT;
1631 case GlobalValue::HiddenVisibility:
1632 return STV_HIDDEN;
1633 case GlobalValue::ProtectedVisibility:
1634 return STV_PROTECTED;
1635 }
1636 llvm_unreachable("unknown visibility")::llvm::llvm_unreachable_internal("unknown visibility", "lld/ELF/InputFiles.cpp"
, 1636)
;
1637}
1638
1639static void
1640createBitcodeSymbol(Symbol *&sym, const std::vector<bool> &keptComdats,
1641 const lto::InputFile::Symbol &objSym, BitcodeFile &f) {
1642 uint8_t binding = objSym.isWeak() ? STB_WEAK : STB_GLOBAL;
1643 uint8_t type = objSym.isTLS() ? STT_TLS : STT_NOTYPE;
1644 uint8_t visibility = mapVisibility(objSym.getVisibility());
1645
1646 if (!sym)
1647 sym = symtab.insert(saver().save(objSym.getName()));
1648
1649 int c = objSym.getComdatIndex();
1650 if (objSym.isUndefined() || (c != -1 && !keptComdats[c])) {
1651 Undefined newSym(&f, StringRef(), binding, visibility, type);
1652 sym->resolve(newSym);
1653 sym->referenced = true;
1654 return;
1655 }
1656
1657 if (objSym.isCommon()) {
1658 sym->resolve(CommonSymbol{&f, StringRef(), binding, visibility, STT_OBJECT,
1659 objSym.getCommonAlignment(),
1660 objSym.getCommonSize()});
1661 } else {
1662 Defined newSym(&f, StringRef(), binding, visibility, type, 0, 0, nullptr);
1663 if (objSym.canBeOmittedFromSymbolTable())
1664 newSym.exportDynamic = false;
1665 sym->resolve(newSym);
1666 }
1667}
1668
1669void BitcodeFile::parse() {
1670 for (std::pair<StringRef, Comdat::SelectionKind> s : obj->getComdatTable()) {
1671 keptComdats.push_back(
1672 s.second == Comdat::NoDeduplicate ||
1673 symtab.comdatGroups.try_emplace(CachedHashStringRef(s.first), this)
1674 .second);
1675 }
1676
1677 symbols.resize(obj->symbols().size());
1678 // Process defined symbols first. See the comment in
1679 // ObjFile<ELFT>::initializeSymbols.
1680 for (auto [i, irSym] : llvm::enumerate(obj->symbols()))
1681 if (!irSym.isUndefined())
1682 createBitcodeSymbol(symbols[i], keptComdats, irSym, *this);
1683 for (auto [i, irSym] : llvm::enumerate(obj->symbols()))
1684 if (irSym.isUndefined())
1685 createBitcodeSymbol(symbols[i], keptComdats, irSym, *this);
1686
1687 for (auto l : obj->getDependentLibraries())
1688 addDependentLibrary(l, this);
1689}
1690
1691void BitcodeFile::parseLazy() {
1692 symbols.resize(obj->symbols().size());
1693 for (auto [i, irSym] : llvm::enumerate(obj->symbols()))
1694 if (!irSym.isUndefined()) {
1695 auto *sym = symtab.insert(saver().save(irSym.getName()));
1696 sym->resolve(LazyObject{*this});
1697 symbols[i] = sym;
1698 }
1699}
1700
1701void BitcodeFile::postParse() {
1702 for (auto [i, irSym] : llvm::enumerate(obj->symbols())) {
1703 const Symbol &sym = *symbols[i];
1704 if (sym.file == this || !sym.isDefined() || irSym.isUndefined() ||
1705 irSym.isCommon() || irSym.isWeak())
1706 continue;
1707 int c = irSym.getComdatIndex();
1708 if (c != -1 && !keptComdats[c])
1709 continue;
1710 reportDuplicate(sym, this, nullptr, 0);
1711 }
1712}
1713
1714void BinaryFile::parse() {
1715 ArrayRef<uint8_t> data = arrayRefFromStringRef(mb.getBuffer());
1716 auto *section = make<InputSection>(this, SHF_ALLOC | SHF_WRITE, SHT_PROGBITS,
1717 8, data, ".data");
1718 sections.push_back(section);
1719
1720 // For each input file foo that is embedded to a result as a binary
1721 // blob, we define _binary_foo_{start,end,size} symbols, so that
1722 // user programs can access blobs by name. Non-alphanumeric
1723 // characters in a filename are replaced with underscore.
1724 std::string s = "_binary_" + mb.getBufferIdentifier().str();
1725 for (size_t i = 0; i < s.size(); ++i)
1726 if (!isAlnum(s[i]))
1727 s[i] = '_';
1728
1729 llvm::StringSaver &saver = lld::saver();
1730
1731 symtab.addAndCheckDuplicate(Defined{nullptr, saver.save(s + "_start"),
1732 STB_GLOBAL, STV_DEFAULT, STT_OBJECT, 0, 0,
1733 section});
1734 symtab.addAndCheckDuplicate(Defined{nullptr, saver.save(s + "_end"),
1735 STB_GLOBAL, STV_DEFAULT, STT_OBJECT,
1736 data.size(), 0, section});
1737 symtab.addAndCheckDuplicate(Defined{nullptr, saver.save(s + "_size"),
1738 STB_GLOBAL, STV_DEFAULT, STT_OBJECT,
1739 data.size(), 0, nullptr});
1740}
1741
1742ELFFileBase *elf::createObjFile(MemoryBufferRef mb, StringRef archiveName,
1743 bool lazy) {
1744 ELFFileBase *f;
1745 switch (getELFKind(mb, archiveName)) {
1746 case ELF32LEKind:
1747 f = make<ObjFile<ELF32LE>>(ELF32LEKind, mb, archiveName);
1748 break;
1749 case ELF32BEKind:
1750 f = make<ObjFile<ELF32BE>>(ELF32BEKind, mb, archiveName);
1751 break;
1752 case ELF64LEKind:
1753 f = make<ObjFile<ELF64LE>>(ELF64LEKind, mb, archiveName);
1754 break;
1755 case ELF64BEKind:
1756 f = make<ObjFile<ELF64BE>>(ELF64BEKind, mb, archiveName);
1757 break;
1758 default:
1759 llvm_unreachable("getELFKind")::llvm::llvm_unreachable_internal("getELFKind", "lld/ELF/InputFiles.cpp"
, 1759)
;
1760 }
1761 f->init();
1762 f->lazy = lazy;
1763 return f;
1764}
1765
1766template <class ELFT> void ObjFile<ELFT>::parseLazy() {
1767 const ArrayRef<typename ELFT::Sym> eSyms = this->getELFSyms<ELFT>();
1768 symbols.resize(eSyms.size());
1769 for (size_t i = firstGlobal, end = eSyms.size(); i != end; ++i)
1770 if (eSyms[i].st_shndx != SHN_UNDEF)
1771 symbols[i] = symtab.insert(CHECK(eSyms[i].getName(stringTable), this)check2((eSyms[i].getName(stringTable)), [&] { return toString
(this); })
);
1772
1773 // Replace existing symbols with LazyObject symbols.
1774 //
1775 // resolve() may trigger this->extract() if an existing symbol is an undefined
1776 // symbol. If that happens, this function has served its purpose, and we can
1777 // exit from the loop early.
1778 for (Symbol *sym : makeArrayRef(symbols).slice(firstGlobal))
1779 if (sym) {
1780 sym->resolve(LazyObject{*this});
1781 if (!lazy)
1782 return;
1783 }
1784}
1785
1786bool InputFile::shouldExtractForCommon(StringRef name) {
1787 if (isa<BitcodeFile>(this))
1788 return isBitcodeNonCommonDef(mb, name, archiveName);
1789
1790 return isNonCommonDef(mb, name, archiveName);
1791}
1792
1793std::string elf::replaceThinLTOSuffix(StringRef path) {
1794 StringRef suffix = config->thinLTOObjectSuffixReplace.first;
1795 StringRef repl = config->thinLTOObjectSuffixReplace.second;
1796
1797 if (path.consume_back(suffix))
1798 return (path + repl).str();
1799 return std::string(path);
1800}
1801
1802template class elf::ObjFile<ELF32LE>;
1803template class elf::ObjFile<ELF32BE>;
1804template class elf::ObjFile<ELF64LE>;
1805template class elf::ObjFile<ELF64BE>;
1806
1807template void SharedFile::parse<ELF32LE>();
1808template void SharedFile::parse<ELF32BE>();
1809template void SharedFile::parse<ELF64LE>();
1810template void SharedFile::parse<ELF64BE>();

/build/llvm-toolchain-snapshot-16~++20221003111214+1fa2019828ca/llvm/include/llvm/Support/MathExtras.h

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