Bug Summary

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

/build/source/llvm/lib/Object/ELFObjectFile.cpp

→
1//===- ELFObjectFile.cpp - ELF object file implementation -----------------===//
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// Part of the ELFObjectFile class implementation.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/Object/ELFObjectFile.h"
14#include "llvm/ADT/Triple.h"
15#include "llvm/BinaryFormat/ELF.h"
16#include "llvm/MC/MCInstrAnalysis.h"
17#include "llvm/MC/SubtargetFeature.h"
18#include "llvm/MC/TargetRegistry.h"
19#include "llvm/Object/ELF.h"
20#include "llvm/Object/ELFTypes.h"
21#include "llvm/Object/Error.h"
22#include "llvm/Support/ARMAttributeParser.h"
23#include "llvm/Support/ARMBuildAttributes.h"
24#include "llvm/Support/ErrorHandling.h"
25#include "llvm/Support/MathExtras.h"
26#include "llvm/Support/RISCVAttributeParser.h"
27#include "llvm/Support/RISCVAttributes.h"
28#include "llvm/Support/RISCVISAInfo.h"
29#include <algorithm>
30#include <cstddef>
31#include <cstdint>
32#include <memory>
33#include <optional>
34#include <string>
35#include <utility>
36
37using namespace llvm;
38using namespace object;
39
40const EnumEntry<unsigned> llvm::object::ElfSymbolTypes[NumElfSymbolTypes] = {
41 {"None", "NOTYPE", ELF::STT_NOTYPE},
42 {"Object", "OBJECT", ELF::STT_OBJECT},
43 {"Function", "FUNC", ELF::STT_FUNC},
44 {"Section", "SECTION", ELF::STT_SECTION},
45 {"File", "FILE", ELF::STT_FILE},
46 {"Common", "COMMON", ELF::STT_COMMON},
47 {"TLS", "TLS", ELF::STT_TLS},
48 {"Unknown", "<unknown>: 7", 7},
49 {"Unknown", "<unknown>: 8", 8},
50 {"Unknown", "<unknown>: 9", 9},
51 {"GNU_IFunc", "IFUNC", ELF::STT_GNU_IFUNC},
52 {"OS Specific", "<OS specific>: 11", 11},
53 {"OS Specific", "<OS specific>: 12", 12},
54 {"Proc Specific", "<processor specific>: 13", 13},
55 {"Proc Specific", "<processor specific>: 14", 14},
56 {"Proc Specific", "<processor specific>: 15", 15}
57};
58
59ELFObjectFileBase::ELFObjectFileBase(unsigned int Type, MemoryBufferRef Source)
60 : ObjectFile(Type, Source) {}
61
62template <class ELFT>
63static Expected<std::unique_ptr<ELFObjectFile<ELFT>>>
64createPtr(MemoryBufferRef Object, bool InitContent) {
65 auto Ret = ELFObjectFile<ELFT>::create(Object, InitContent);
66 if (Error E = Ret.takeError())
67 return std::move(E);
68 return std::make_unique<ELFObjectFile<ELFT>>(std::move(*Ret));
69}
70
71Expected<std::unique_ptr<ObjectFile>>
72ObjectFile::createELFObjectFile(MemoryBufferRef Obj, bool InitContent) {
73 std::pair<unsigned char, unsigned char> Ident =
74 getElfArchType(Obj.getBuffer());
75 std::size_t MaxAlignment =
76 1ULL << countTrailingZeros(
1
Calling 'countTrailingZeros<unsigned long>'
→
11
←
Returning from 'countTrailingZeros<unsigned long>'
→
12
←
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'
77 reinterpret_cast<uintptr_t>(Obj.getBufferStart()));
78
79 if (MaxAlignment < 2)
80 return createError("Insufficient alignment");
81
82 if (Ident.first == ELF::ELFCLASS32) {
83 if (Ident.second == ELF::ELFDATA2LSB)
84 return createPtr<ELF32LE>(Obj, InitContent);
85 else if (Ident.second == ELF::ELFDATA2MSB)
86 return createPtr<ELF32BE>(Obj, InitContent);
87 else
88 return createError("Invalid ELF data");
89 } else if (Ident.first == ELF::ELFCLASS64) {
90 if (Ident.second == ELF::ELFDATA2LSB)
91 return createPtr<ELF64LE>(Obj, InitContent);
92 else if (Ident.second == ELF::ELFDATA2MSB)
93 return createPtr<ELF64BE>(Obj, InitContent);
94 else
95 return createError("Invalid ELF data");
96 }
97 return createError("Invalid ELF class");
98}
99
100SubtargetFeatures ELFObjectFileBase::getMIPSFeatures() const {
101 SubtargetFeatures Features;
102 unsigned PlatformFlags = getPlatformFlags();
103
104 switch (PlatformFlags & ELF::EF_MIPS_ARCH) {
105 case ELF::EF_MIPS_ARCH_1:
106 break;
107 case ELF::EF_MIPS_ARCH_2:
108 Features.AddFeature("mips2");
109 break;
110 case ELF::EF_MIPS_ARCH_3:
111 Features.AddFeature("mips3");
112 break;
113 case ELF::EF_MIPS_ARCH_4:
114 Features.AddFeature("mips4");
115 break;
116 case ELF::EF_MIPS_ARCH_5:
117 Features.AddFeature("mips5");
118 break;
119 case ELF::EF_MIPS_ARCH_32:
120 Features.AddFeature("mips32");
121 break;
122 case ELF::EF_MIPS_ARCH_64:
123 Features.AddFeature("mips64");
124 break;
125 case ELF::EF_MIPS_ARCH_32R2:
126 Features.AddFeature("mips32r2");
127 break;
128 case ELF::EF_MIPS_ARCH_64R2:
129 Features.AddFeature("mips64r2");
130 break;
131 case ELF::EF_MIPS_ARCH_32R6:
132 Features.AddFeature("mips32r6");
133 break;
134 case ELF::EF_MIPS_ARCH_64R6:
135 Features.AddFeature("mips64r6");
136 break;
137 default:
138 llvm_unreachable("Unknown EF_MIPS_ARCH value")::llvm::llvm_unreachable_internal("Unknown EF_MIPS_ARCH value"
, "llvm/lib/Object/ELFObjectFile.cpp", 138);
139 }
140
141 switch (PlatformFlags & ELF::EF_MIPS_MACH) {
142 case ELF::EF_MIPS_MACH_NONE:
143 // No feature associated with this value.
144 break;
145 case ELF::EF_MIPS_MACH_OCTEON:
146 Features.AddFeature("cnmips");
147 break;
148 default:
149 llvm_unreachable("Unknown EF_MIPS_ARCH value")::llvm::llvm_unreachable_internal("Unknown EF_MIPS_ARCH value"
, "llvm/lib/Object/ELFObjectFile.cpp", 149);
150 }
151
152 if (PlatformFlags & ELF::EF_MIPS_ARCH_ASE_M16)
153 Features.AddFeature("mips16");
154 if (PlatformFlags & ELF::EF_MIPS_MICROMIPS)
155 Features.AddFeature("micromips");
156
157 return Features;
158}
159
160SubtargetFeatures ELFObjectFileBase::getARMFeatures() const {
161 SubtargetFeatures Features;
162 ARMAttributeParser Attributes;
163 if (Error E = getBuildAttributes(Attributes)) {
164 consumeError(std::move(E));
165 return SubtargetFeatures();
166 }
167
168 // both ARMv7-M and R have to support thumb hardware div
169 bool isV7 = false;
170 std::optional<unsigned> Attr =
171 Attributes.getAttributeValue(ARMBuildAttrs::CPU_arch);
172 if (Attr)
173 isV7 = *Attr == ARMBuildAttrs::v7;
174
175 Attr = Attributes.getAttributeValue(ARMBuildAttrs::CPU_arch_profile);
176 if (Attr) {
177 switch (*Attr) {
178 case ARMBuildAttrs::ApplicationProfile:
179 Features.AddFeature("aclass");
180 break;
181 case ARMBuildAttrs::RealTimeProfile:
182 Features.AddFeature("rclass");
183 if (isV7)
184 Features.AddFeature("hwdiv");
185 break;
186 case ARMBuildAttrs::MicroControllerProfile:
187 Features.AddFeature("mclass");
188 if (isV7)
189 Features.AddFeature("hwdiv");
190 break;
191 }
192 }
193
194 Attr = Attributes.getAttributeValue(ARMBuildAttrs::THUMB_ISA_use);
195 if (Attr) {
196 switch (*Attr) {
197 default:
198 break;
199 case ARMBuildAttrs::Not_Allowed:
200 Features.AddFeature("thumb", false);
201 Features.AddFeature("thumb2", false);
202 break;
203 case ARMBuildAttrs::AllowThumb32:
204 Features.AddFeature("thumb2");
205 break;
206 }
207 }
208
209 Attr = Attributes.getAttributeValue(ARMBuildAttrs::FP_arch);
210 if (Attr) {
211 switch (*Attr) {
212 default:
213 break;
214 case ARMBuildAttrs::Not_Allowed:
215 Features.AddFeature("vfp2sp", false);
216 Features.AddFeature("vfp3d16sp", false);
217 Features.AddFeature("vfp4d16sp", false);
218 break;
219 case ARMBuildAttrs::AllowFPv2:
220 Features.AddFeature("vfp2");
221 break;
222 case ARMBuildAttrs::AllowFPv3A:
223 case ARMBuildAttrs::AllowFPv3B:
224 Features.AddFeature("vfp3");
225 break;
226 case ARMBuildAttrs::AllowFPv4A:
227 case ARMBuildAttrs::AllowFPv4B:
228 Features.AddFeature("vfp4");
229 break;
230 }
231 }
232
233 Attr = Attributes.getAttributeValue(ARMBuildAttrs::Advanced_SIMD_arch);
234 if (Attr) {
235 switch (*Attr) {
236 default:
237 break;
238 case ARMBuildAttrs::Not_Allowed:
239 Features.AddFeature("neon", false);
240 Features.AddFeature("fp16", false);
241 break;
242 case ARMBuildAttrs::AllowNeon:
243 Features.AddFeature("neon");
244 break;
245 case ARMBuildAttrs::AllowNeon2:
246 Features.AddFeature("neon");
247 Features.AddFeature("fp16");
248 break;
249 }
250 }
251
252 Attr = Attributes.getAttributeValue(ARMBuildAttrs::MVE_arch);
253 if (Attr) {
254 switch (*Attr) {
255 default:
256 break;
257 case ARMBuildAttrs::Not_Allowed:
258 Features.AddFeature("mve", false);
259 Features.AddFeature("mve.fp", false);
260 break;
261 case ARMBuildAttrs::AllowMVEInteger:
262 Features.AddFeature("mve.fp", false);
263 Features.AddFeature("mve");
264 break;
265 case ARMBuildAttrs::AllowMVEIntegerAndFloat:
266 Features.AddFeature("mve.fp");
267 break;
268 }
269 }
270
271 Attr = Attributes.getAttributeValue(ARMBuildAttrs::DIV_use);
272 if (Attr) {
273 switch (*Attr) {
274 default:
275 break;
276 case ARMBuildAttrs::DisallowDIV:
277 Features.AddFeature("hwdiv", false);
278 Features.AddFeature("hwdiv-arm", false);
279 break;
280 case ARMBuildAttrs::AllowDIVExt:
281 Features.AddFeature("hwdiv");
282 Features.AddFeature("hwdiv-arm");
283 break;
284 }
285 }
286
287 return Features;
288}
289
290Expected<SubtargetFeatures> ELFObjectFileBase::getRISCVFeatures() const {
291 SubtargetFeatures Features;
292 unsigned PlatformFlags = getPlatformFlags();
293
294 if (PlatformFlags & ELF::EF_RISCV_RVC) {
295 Features.AddFeature("c");
296 }
297
298 RISCVAttributeParser Attributes;
299 if (Error E = getBuildAttributes(Attributes)) {
300 return std::move(E);
301 }
302
303 std::optional<StringRef> Attr =
304 Attributes.getAttributeString(RISCVAttrs::ARCH);
305 if (Attr) {
306 // Suppress version checking for experimental extensions to prevent erroring
307 // when getting any unknown version of experimental extension.
308 auto ParseResult = RISCVISAInfo::parseArchString(
309 *Attr, /*EnableExperimentalExtension=*/true,
310 /*ExperimentalExtensionVersionCheck=*/false,
311 /*IgnoreUnknown=*/true);
312 if (!ParseResult)
313 return ParseResult.takeError();
314 auto &ISAInfo = *ParseResult;
315
316 if (ISAInfo->getXLen() == 32)
317 Features.AddFeature("64bit", false);
318 else if (ISAInfo->getXLen() == 64)
319 Features.AddFeature("64bit");
320 else
321 llvm_unreachable("XLEN should be 32 or 64.")::llvm::llvm_unreachable_internal("XLEN should be 32 or 64.",
"llvm/lib/Object/ELFObjectFile.cpp", 321);
322
323 Features.addFeaturesVector(ISAInfo->toFeatureVector());
324 }
325
326 return Features;
327}
328
329SubtargetFeatures ELFObjectFileBase::getLoongArchFeatures() const {
330 SubtargetFeatures Features;
331
332 switch (getPlatformFlags() & ELF::EF_LOONGARCH_ABI_MODIFIER_MASK) {
333 case ELF::EF_LOONGARCH_ABI_SOFT_FLOAT:
334 break;
335 case ELF::EF_LOONGARCH_ABI_DOUBLE_FLOAT:
336 Features.AddFeature("d");
337 // D implies F according to LoongArch ISA spec.
338 [[fallthrough]];
339 case ELF::EF_LOONGARCH_ABI_SINGLE_FLOAT:
340 Features.AddFeature("f");
341 break;
342 }
343
344 return Features;
345}
346
347Expected<SubtargetFeatures> ELFObjectFileBase::getFeatures() const {
348 switch (getEMachine()) {
349 case ELF::EM_MIPS:
350 return getMIPSFeatures();
351 case ELF::EM_ARM:
352 return getARMFeatures();
353 case ELF::EM_RISCV:
354 return getRISCVFeatures();
355 case ELF::EM_LOONGARCH:
356 return getLoongArchFeatures();
357 default:
358 return SubtargetFeatures();
359 }
360}
361
362std::optional<StringRef> ELFObjectFileBase::tryGetCPUName() const {
363 switch (getEMachine()) {
364 case ELF::EM_AMDGPU:
365 return getAMDGPUCPUName();
366 case ELF::EM_PPC64:
367 return StringRef("future");
368 default:
369 return std::nullopt;
370 }
371}
372
373StringRef ELFObjectFileBase::getAMDGPUCPUName() const {
374 assert(getEMachine() == ELF::EM_AMDGPU)(static_cast <bool> (getEMachine() == ELF::EM_AMDGPU) ?
void (0) : __assert_fail ("getEMachine() == ELF::EM_AMDGPU",
"llvm/lib/Object/ELFObjectFile.cpp", 374, __extension__ __PRETTY_FUNCTION__
));
375 unsigned CPU = getPlatformFlags() & ELF::EF_AMDGPU_MACH;
376
377 switch (CPU) {
378 // Radeon HD 2000/3000 Series (R600).
379 case ELF::EF_AMDGPU_MACH_R600_R600:
380 return "r600";
381 case ELF::EF_AMDGPU_MACH_R600_R630:
382 return "r630";
383 case ELF::EF_AMDGPU_MACH_R600_RS880:
384 return "rs880";
385 case ELF::EF_AMDGPU_MACH_R600_RV670:
386 return "rv670";
387
388 // Radeon HD 4000 Series (R700).
389 case ELF::EF_AMDGPU_MACH_R600_RV710:
390 return "rv710";
391 case ELF::EF_AMDGPU_MACH_R600_RV730:
392 return "rv730";
393 case ELF::EF_AMDGPU_MACH_R600_RV770:
394 return "rv770";
395
396 // Radeon HD 5000 Series (Evergreen).
397 case ELF::EF_AMDGPU_MACH_R600_CEDAR:
398 return "cedar";
399 case ELF::EF_AMDGPU_MACH_R600_CYPRESS:
400 return "cypress";
401 case ELF::EF_AMDGPU_MACH_R600_JUNIPER:
402 return "juniper";
403 case ELF::EF_AMDGPU_MACH_R600_REDWOOD:
404 return "redwood";
405 case ELF::EF_AMDGPU_MACH_R600_SUMO:
406 return "sumo";
407
408 // Radeon HD 6000 Series (Northern Islands).
409 case ELF::EF_AMDGPU_MACH_R600_BARTS:
410 return "barts";
411 case ELF::EF_AMDGPU_MACH_R600_CAICOS:
412 return "caicos";
413 case ELF::EF_AMDGPU_MACH_R600_CAYMAN:
414 return "cayman";
415 case ELF::EF_AMDGPU_MACH_R600_TURKS:
416 return "turks";
417
418 // AMDGCN GFX6.
419 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX600:
420 return "gfx600";
421 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX601:
422 return "gfx601";
423 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX602:
424 return "gfx602";
425
426 // AMDGCN GFX7.
427 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX700:
428 return "gfx700";
429 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX701:
430 return "gfx701";
431 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX702:
432 return "gfx702";
433 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX703:
434 return "gfx703";
435 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX704:
436 return "gfx704";
437 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX705:
438 return "gfx705";
439
440 // AMDGCN GFX8.
441 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX801:
442 return "gfx801";
443 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX802:
444 return "gfx802";
445 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX803:
446 return "gfx803";
447 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX805:
448 return "gfx805";
449 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX810:
450 return "gfx810";
451
452 // AMDGCN GFX9.
453 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX900:
454 return "gfx900";
455 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX902:
456 return "gfx902";
457 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX904:
458 return "gfx904";
459 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX906:
460 return "gfx906";
461 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX908:
462 return "gfx908";
463 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX909:
464 return "gfx909";
465 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX90A:
466 return "gfx90a";
467 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX90C:
468 return "gfx90c";
469 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX940:
470 return "gfx940";
471
472 // AMDGCN GFX10.
473 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1010:
474 return "gfx1010";
475 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1011:
476 return "gfx1011";
477 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1012:
478 return "gfx1012";
479 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1013:
480 return "gfx1013";
481 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1030:
482 return "gfx1030";
483 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1031:
484 return "gfx1031";
485 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1032:
486 return "gfx1032";
487 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1033:
488 return "gfx1033";
489 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1034:
490 return "gfx1034";
491 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1035:
492 return "gfx1035";
493 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1036:
494 return "gfx1036";
495
496 // AMDGCN GFX11.
497 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1100:
498 return "gfx1100";
499 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1101:
500 return "gfx1101";
501 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1102:
502 return "gfx1102";
503 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1103:
504 return "gfx1103";
505 default:
506 llvm_unreachable("Unknown EF_AMDGPU_MACH value")::llvm::llvm_unreachable_internal("Unknown EF_AMDGPU_MACH value"
, "llvm/lib/Object/ELFObjectFile.cpp", 506);
507 }
508}
509
510// FIXME Encode from a tablegen description or target parser.
511void ELFObjectFileBase::setARMSubArch(Triple &TheTriple) const {
512 if (TheTriple.getSubArch() != Triple::NoSubArch)
513 return;
514
515 ARMAttributeParser Attributes;
516 if (Error E = getBuildAttributes(Attributes)) {
517 // TODO Propagate Error.
518 consumeError(std::move(E));
519 return;
520 }
521
522 std::string Triple;
523 // Default to ARM, but use the triple if it's been set.
524 if (TheTriple.isThumb())
525 Triple = "thumb";
526 else
527 Triple = "arm";
528
529 std::optional<unsigned> Attr =
530 Attributes.getAttributeValue(ARMBuildAttrs::CPU_arch);
531 if (Attr) {
532 switch (*Attr) {
533 case ARMBuildAttrs::v4:
534 Triple += "v4";
535 break;
536 case ARMBuildAttrs::v4T:
537 Triple += "v4t";
538 break;
539 case ARMBuildAttrs::v5T:
540 Triple += "v5t";
541 break;
542 case ARMBuildAttrs::v5TE:
543 Triple += "v5te";
544 break;
545 case ARMBuildAttrs::v5TEJ:
546 Triple += "v5tej";
547 break;
548 case ARMBuildAttrs::v6:
549 Triple += "v6";
550 break;
551 case ARMBuildAttrs::v6KZ:
552 Triple += "v6kz";
553 break;
554 case ARMBuildAttrs::v6T2:
555 Triple += "v6t2";
556 break;
557 case ARMBuildAttrs::v6K:
558 Triple += "v6k";
559 break;
560 case ARMBuildAttrs::v7: {
561 std::optional<unsigned> ArchProfileAttr =
562 Attributes.getAttributeValue(ARMBuildAttrs::CPU_arch_profile);
563 if (ArchProfileAttr &&
564 *ArchProfileAttr == ARMBuildAttrs::MicroControllerProfile)
565 Triple += "v7m";
566 else
567 Triple += "v7";
568 break;
569 }
570 case ARMBuildAttrs::v6_M:
571 Triple += "v6m";
572 break;
573 case ARMBuildAttrs::v6S_M:
574 Triple += "v6sm";
575 break;
576 case ARMBuildAttrs::v7E_M:
577 Triple += "v7em";
578 break;
579 case ARMBuildAttrs::v8_A:
580 Triple += "v8a";
581 break;
582 case ARMBuildAttrs::v8_R:
583 Triple += "v8r";
584 break;
585 case ARMBuildAttrs::v8_M_Base:
586 Triple += "v8m.base";
587 break;
588 case ARMBuildAttrs::v8_M_Main:
589 Triple += "v8m.main";
590 break;
591 case ARMBuildAttrs::v8_1_M_Main:
592 Triple += "v8.1m.main";
593 break;
594 case ARMBuildAttrs::v9_A:
595 Triple += "v9a";
596 break;
597 }
598 }
599 if (!isLittleEndian())
600 Triple += "eb";
601
602 TheTriple.setArchName(Triple);
603}
604
605std::vector<std::pair<std::optional<DataRefImpl>, uint64_t>>
606ELFObjectFileBase::getPltAddresses() const {
607 std::string Err;
608 const auto Triple = makeTriple();
609 const auto *T = TargetRegistry::lookupTarget(Triple.str(), Err);
610 if (!T)
611 return {};
612 uint64_t JumpSlotReloc = 0;
613 switch (Triple.getArch()) {
614 case Triple::x86:
615 JumpSlotReloc = ELF::R_386_JUMP_SLOT;
616 break;
617 case Triple::x86_64:
618 JumpSlotReloc = ELF::R_X86_64_JUMP_SLOT;
619 break;
620 case Triple::aarch64:
621 case Triple::aarch64_be:
622 JumpSlotReloc = ELF::R_AARCH64_JUMP_SLOT;
623 break;
624 default:
625 return {};
626 }
627 std::unique_ptr<const MCInstrInfo> MII(T->createMCInstrInfo());
628 std::unique_ptr<const MCInstrAnalysis> MIA(
629 T->createMCInstrAnalysis(MII.get()));
630 if (!MIA)
631 return {};
632 std::optional<SectionRef> Plt, RelaPlt, GotPlt;
633 for (const SectionRef &Section : sections()) {
634 Expected<StringRef> NameOrErr = Section.getName();
635 if (!NameOrErr) {
636 consumeError(NameOrErr.takeError());
637 continue;
638 }
639 StringRef Name = *NameOrErr;
640
641 if (Name == ".plt")
642 Plt = Section;
643 else if (Name == ".rela.plt" || Name == ".rel.plt")
644 RelaPlt = Section;
645 else if (Name == ".got.plt")
646 GotPlt = Section;
647 }
648 if (!Plt || !RelaPlt || !GotPlt)
649 return {};
650 Expected<StringRef> PltContents = Plt->getContents();
651 if (!PltContents) {
652 consumeError(PltContents.takeError());
653 return {};
654 }
655 auto PltEntries = MIA->findPltEntries(Plt->getAddress(),
656 arrayRefFromStringRef(*PltContents),
657 GotPlt->getAddress(), Triple);
658 // Build a map from GOT entry virtual address to PLT entry virtual address.
659 DenseMap<uint64_t, uint64_t> GotToPlt;
660 for (const auto &Entry : PltEntries)
661 GotToPlt.insert(std::make_pair(Entry.second, Entry.first));
662 // Find the relocations in the dynamic relocation table that point to
663 // locations in the GOT for which we know the corresponding PLT entry.
664 std::vector<std::pair<std::optional<DataRefImpl>, uint64_t>> Result;
665 for (const auto &Relocation : RelaPlt->relocations()) {
666 if (Relocation.getType() != JumpSlotReloc)
667 continue;
668 auto PltEntryIter = GotToPlt.find(Relocation.getOffset());
669 if (PltEntryIter != GotToPlt.end()) {
670 symbol_iterator Sym = Relocation.getSymbol();
671 if (Sym == symbol_end())
672 Result.emplace_back(std::nullopt, PltEntryIter->second);
673 else
674 Result.emplace_back(Sym->getRawDataRefImpl(), PltEntryIter->second);
675 }
676 }
677 return Result;
678}
679
680template <class ELFT>
681Expected<std::vector<BBAddrMap>> static readBBAddrMapImpl(
682 const ELFFile<ELFT> &EF, std::optional<unsigned> TextSectionIndex) {
683 using Elf_Shdr = typename ELFT::Shdr;
684 std::vector<BBAddrMap> BBAddrMaps;
685 const auto &Sections = cantFail(EF.sections());
686 for (const Elf_Shdr &Sec : Sections) {
687 if (Sec.sh_type != ELF::SHT_LLVM_BB_ADDR_MAP &&
688 Sec.sh_type != ELF::SHT_LLVM_BB_ADDR_MAP_V0)
689 continue;
690 if (TextSectionIndex) {
691 Expected<const Elf_Shdr *> TextSecOrErr = EF.getSection(Sec.sh_link);
692 if (!TextSecOrErr)
693 return createError("unable to get the linked-to section for " +
694 describe(EF, Sec) + ": " +
695 toString(TextSecOrErr.takeError()));
696 if (*TextSectionIndex != std::distance(Sections.begin(), *TextSecOrErr))
697 continue;
698 }
699 Expected<std::vector<BBAddrMap>> BBAddrMapOrErr = EF.decodeBBAddrMap(Sec);
700 if (!BBAddrMapOrErr)
701 return createError("unable to read " + describe(EF, Sec) + ": " +
702 toString(BBAddrMapOrErr.takeError()));
703 std::move(BBAddrMapOrErr->begin(), BBAddrMapOrErr->end(),
704 std::back_inserter(BBAddrMaps));
705 }
706 return BBAddrMaps;
707}
708
709template <class ELFT>
710static Expected<std::vector<VersionEntry>>
711readDynsymVersionsImpl(const ELFFile<ELFT> &EF,
712 ELFObjectFileBase::elf_symbol_iterator_range Symbols) {
713 using Elf_Shdr = typename ELFT::Shdr;
714 const Elf_Shdr *VerSec = nullptr;
715 const Elf_Shdr *VerNeedSec = nullptr;
716 const Elf_Shdr *VerDefSec = nullptr;
717 // The user should ensure sections() can't fail here.
718 for (const Elf_Shdr &Sec : cantFail(EF.sections())) {
719 if (Sec.sh_type == ELF::SHT_GNU_versym)
720 VerSec = &Sec;
721 else if (Sec.sh_type == ELF::SHT_GNU_verdef)
722 VerDefSec = &Sec;
723 else if (Sec.sh_type == ELF::SHT_GNU_verneed)
724 VerNeedSec = &Sec;
725 }
726 if (!VerSec)
727 return std::vector<VersionEntry>();
728
729 Expected<SmallVector<std::optional<VersionEntry>, 0>> MapOrErr =
730 EF.loadVersionMap(VerNeedSec, VerDefSec);
731 if (!MapOrErr)
732 return MapOrErr.takeError();
733
734 std::vector<VersionEntry> Ret;
735 size_t I = 0;
736 for (const ELFSymbolRef &Sym : Symbols) {
737 ++I;
738 Expected<const typename ELFT::Versym *> VerEntryOrErr =
739 EF.template getEntry<typename ELFT::Versym>(*VerSec, I);
740 if (!VerEntryOrErr)
741 return createError("unable to read an entry with index " + Twine(I) +
742 " from " + describe(EF, *VerSec) + ": " +
743 toString(VerEntryOrErr.takeError()));
744
745 Expected<uint32_t> FlagsOrErr = Sym.getFlags();
746 if (!FlagsOrErr)
747 return createError("unable to read flags for symbol with index " +
748 Twine(I) + ": " + toString(FlagsOrErr.takeError()));
749
750 bool IsDefault;
751 Expected<StringRef> VerOrErr = EF.getSymbolVersionByIndex(
752 (*VerEntryOrErr)->vs_index, IsDefault, *MapOrErr,
753 (*FlagsOrErr) & SymbolRef::SF_Undefined);
754 if (!VerOrErr)
755 return createError("unable to get a version for entry " + Twine(I) +
756 " of " + describe(EF, *VerSec) + ": " +
757 toString(VerOrErr.takeError()));
758
759 Ret.push_back({(*VerOrErr).str(), IsDefault});
760 }
761
762 return Ret;
763}
764
765Expected<std::vector<VersionEntry>>
766ELFObjectFileBase::readDynsymVersions() const {
767 elf_symbol_iterator_range Symbols = getDynamicSymbolIterators();
768 if (const auto *Obj = dyn_cast<ELF32LEObjectFile>(this))
769 return readDynsymVersionsImpl(Obj->getELFFile(), Symbols);
770 if (const auto *Obj = dyn_cast<ELF32BEObjectFile>(this))
771 return readDynsymVersionsImpl(Obj->getELFFile(), Symbols);
772 if (const auto *Obj = dyn_cast<ELF64LEObjectFile>(this))
773 return readDynsymVersionsImpl(Obj->getELFFile(), Symbols);
774 return readDynsymVersionsImpl(cast<ELF64BEObjectFile>(this)->getELFFile(),
775 Symbols);
776}
777
778Expected<std::vector<BBAddrMap>> ELFObjectFileBase::readBBAddrMap(
779 std::optional<unsigned> TextSectionIndex) const {
780 if (const auto *Obj = dyn_cast<ELF32LEObjectFile>(this))
781 return readBBAddrMapImpl(Obj->getELFFile(), TextSectionIndex);
782 if (const auto *Obj = dyn_cast<ELF64LEObjectFile>(this))
783 return readBBAddrMapImpl(Obj->getELFFile(), TextSectionIndex);
784 if (const auto *Obj = dyn_cast<ELF32BEObjectFile>(this))
785 return readBBAddrMapImpl(Obj->getELFFile(), TextSectionIndex);
786 if (const auto *Obj = cast<ELF64BEObjectFile>(this))
787 return readBBAddrMapImpl(Obj->getELFFile(), TextSectionIndex);
788 else
789 llvm_unreachable("Unsupported binary format")::llvm::llvm_unreachable_internal("Unsupported binary format"
, "llvm/lib/Object/ELFObjectFile.cpp", 789);
790}
←

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

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

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

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