Bug Summary

File:build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/lib/Object/ELFObjectFile.cpp
Warning:line 74, 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/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm -resource-dir /usr/lib/llvm-16/lib/clang/16.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/Object -I /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/lib/Object -I include -I /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/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~++20220904122748+c444af1c20b3/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/= -O3 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-09-04-125545-48738-1 -x c++ /build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/lib/Object/ELFObjectFile.cpp

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

/build/llvm-toolchain-snapshot-16~++20220904122748+c444af1c20b3/llvm/include/llvm/Support/MathExtras.h

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