Bug Summary

File:build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/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-store=region -analyzer-opt-analyze-nested-blocks -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-15~++20220420111733+e13d2efed663/build-llvm -resource-dir /usr/lib/llvm-15/lib/clang/15.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-15~++20220420111733+e13d2efed663/llvm/lib/Object -I include -I /build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/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-15/lib/clang/15.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-15~++20220420111733+e13d2efed663/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/= -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 -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/= -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-04-20-140412-16051-1 -x c++ /build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/llvm/lib/Object/ELFObjectFile.cpp

/build/llvm-toolchain-snapshot-15~++20220420111733+e13d2efed663/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.hasValue())
171 isV7 = Attr.getValue() == ARMBuildAttrs::v7;
172
173 Attr = Attributes.getAttributeValue(ARMBuildAttrs::CPU_arch_profile);
174 if (Attr.hasValue()) {
175 switch (Attr.getValue()) {
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.hasValue()) {
194 switch (Attr.getValue()) {
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.hasValue()) {
209 switch (Attr.getValue()) {
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.hasValue()) {
233 switch (Attr.getValue()) {
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.hasValue()) {
252 switch (Attr.getValue()) {
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.hasValue()) {
271 switch (Attr.getValue()) {
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.hasValue()) {
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.getValue();
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 LLVM_FALLTHROUGH[[gnu::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 default:
362 return None;
363 }
364}
365
366StringRef ELFObjectFileBase::getAMDGPUCPUName() const {
367 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", 367, __extension__ __PRETTY_FUNCTION__
));
368 unsigned CPU = getPlatformFlags() & ELF::EF_AMDGPU_MACH;
369
370 switch (CPU) {
371 // Radeon HD 2000/3000 Series (R600).
372 case ELF::EF_AMDGPU_MACH_R600_R600:
373 return "r600";
374 case ELF::EF_AMDGPU_MACH_R600_R630:
375 return "r630";
376 case ELF::EF_AMDGPU_MACH_R600_RS880:
377 return "rs880";
378 case ELF::EF_AMDGPU_MACH_R600_RV670:
379 return "rv670";
380
381 // Radeon HD 4000 Series (R700).
382 case ELF::EF_AMDGPU_MACH_R600_RV710:
383 return "rv710";
384 case ELF::EF_AMDGPU_MACH_R600_RV730:
385 return "rv730";
386 case ELF::EF_AMDGPU_MACH_R600_RV770:
387 return "rv770";
388
389 // Radeon HD 5000 Series (Evergreen).
390 case ELF::EF_AMDGPU_MACH_R600_CEDAR:
391 return "cedar";
392 case ELF::EF_AMDGPU_MACH_R600_CYPRESS:
393 return "cypress";
394 case ELF::EF_AMDGPU_MACH_R600_JUNIPER:
395 return "juniper";
396 case ELF::EF_AMDGPU_MACH_R600_REDWOOD:
397 return "redwood";
398 case ELF::EF_AMDGPU_MACH_R600_SUMO:
399 return "sumo";
400
401 // Radeon HD 6000 Series (Northern Islands).
402 case ELF::EF_AMDGPU_MACH_R600_BARTS:
403 return "barts";
404 case ELF::EF_AMDGPU_MACH_R600_CAICOS:
405 return "caicos";
406 case ELF::EF_AMDGPU_MACH_R600_CAYMAN:
407 return "cayman";
408 case ELF::EF_AMDGPU_MACH_R600_TURKS:
409 return "turks";
410
411 // AMDGCN GFX6.
412 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX600:
413 return "gfx600";
414 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX601:
415 return "gfx601";
416 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX602:
417 return "gfx602";
418
419 // AMDGCN GFX7.
420 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX700:
421 return "gfx700";
422 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX701:
423 return "gfx701";
424 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX702:
425 return "gfx702";
426 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX703:
427 return "gfx703";
428 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX704:
429 return "gfx704";
430 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX705:
431 return "gfx705";
432
433 // AMDGCN GFX8.
434 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX801:
435 return "gfx801";
436 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX802:
437 return "gfx802";
438 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX803:
439 return "gfx803";
440 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX805:
441 return "gfx805";
442 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX810:
443 return "gfx810";
444
445 // AMDGCN GFX9.
446 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX900:
447 return "gfx900";
448 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX902:
449 return "gfx902";
450 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX904:
451 return "gfx904";
452 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX906:
453 return "gfx906";
454 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX908:
455 return "gfx908";
456 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX909:
457 return "gfx909";
458 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX90A:
459 return "gfx90a";
460 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX90C:
461 return "gfx90c";
462 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX940:
463 return "gfx940";
464
465 // AMDGCN GFX10.
466 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1010:
467 return "gfx1010";
468 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1011:
469 return "gfx1011";
470 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1012:
471 return "gfx1012";
472 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1013:
473 return "gfx1013";
474 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1030:
475 return "gfx1030";
476 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1031:
477 return "gfx1031";
478 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1032:
479 return "gfx1032";
480 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1033:
481 return "gfx1033";
482 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1034:
483 return "gfx1034";
484 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1035:
485 return "gfx1035";
486 case ELF::EF_AMDGPU_MACH_AMDGCN_GFX1036:
487 return "gfx1036";
488 default:
489 llvm_unreachable("Unknown EF_AMDGPU_MACH value")::llvm::llvm_unreachable_internal("Unknown EF_AMDGPU_MACH value"
, "llvm/lib/Object/ELFObjectFile.cpp", 489);
490 }
491}
492
493// FIXME Encode from a tablegen description or target parser.
494void ELFObjectFileBase::setARMSubArch(Triple &TheTriple) const {
495 if (TheTriple.getSubArch() != Triple::NoSubArch)
496 return;
497
498 ARMAttributeParser Attributes;
499 if (Error E = getBuildAttributes(Attributes)) {
500 // TODO Propagate Error.
501 consumeError(std::move(E));
502 return;
503 }
504
505 std::string Triple;
506 // Default to ARM, but use the triple if it's been set.
507 if (TheTriple.isThumb())
508 Triple = "thumb";
509 else
510 Triple = "arm";
511
512 Optional<unsigned> Attr =
513 Attributes.getAttributeValue(ARMBuildAttrs::CPU_arch);
514 if (Attr.hasValue()) {
515 switch (Attr.getValue()) {
516 case ARMBuildAttrs::v4:
517 Triple += "v4";
518 break;
519 case ARMBuildAttrs::v4T:
520 Triple += "v4t";
521 break;
522 case ARMBuildAttrs::v5T:
523 Triple += "v5t";
524 break;
525 case ARMBuildAttrs::v5TE:
526 Triple += "v5te";
527 break;
528 case ARMBuildAttrs::v5TEJ:
529 Triple += "v5tej";
530 break;
531 case ARMBuildAttrs::v6:
532 Triple += "v6";
533 break;
534 case ARMBuildAttrs::v6KZ:
535 Triple += "v6kz";
536 break;
537 case ARMBuildAttrs::v6T2:
538 Triple += "v6t2";
539 break;
540 case ARMBuildAttrs::v6K:
541 Triple += "v6k";
542 break;
543 case ARMBuildAttrs::v7: {
544 Optional<unsigned> ArchProfileAttr =
545 Attributes.getAttributeValue(ARMBuildAttrs::CPU_arch_profile);
546 if (ArchProfileAttr.hasValue() &&
547 ArchProfileAttr.getValue() == ARMBuildAttrs::MicroControllerProfile)
548 Triple += "v7m";
549 else
550 Triple += "v7";
551 break;
552 }
553 case ARMBuildAttrs::v6_M:
554 Triple += "v6m";
555 break;
556 case ARMBuildAttrs::v6S_M:
557 Triple += "v6sm";
558 break;
559 case ARMBuildAttrs::v7E_M:
560 Triple += "v7em";
561 break;
562 case ARMBuildAttrs::v8_A:
563 Triple += "v8a";
564 break;
565 case ARMBuildAttrs::v8_R:
566 Triple += "v8r";
567 break;
568 case ARMBuildAttrs::v8_M_Base:
569 Triple += "v8m.base";
570 break;
571 case ARMBuildAttrs::v8_M_Main:
572 Triple += "v8m.main";
573 break;
574 case ARMBuildAttrs::v8_1_M_Main:
575 Triple += "v8.1m.main";
576 break;
577 }
578 }
579 if (!isLittleEndian())
580 Triple += "eb";
581
582 TheTriple.setArchName(Triple);
583}
584
585std::vector<std::pair<Optional<DataRefImpl>, uint64_t>>
586ELFObjectFileBase::getPltAddresses() const {
587 std::string Err;
588 const auto Triple = makeTriple();
589 const auto *T = TargetRegistry::lookupTarget(Triple.str(), Err);
590 if (!T)
591 return {};
592 uint64_t JumpSlotReloc = 0;
593 switch (Triple.getArch()) {
594 case Triple::x86:
595 JumpSlotReloc = ELF::R_386_JUMP_SLOT;
596 break;
597 case Triple::x86_64:
598 JumpSlotReloc = ELF::R_X86_64_JUMP_SLOT;
599 break;
600 case Triple::aarch64:
601 case Triple::aarch64_be:
602 JumpSlotReloc = ELF::R_AARCH64_JUMP_SLOT;
603 break;
604 default:
605 return {};
606 }
607 std::unique_ptr<const MCInstrInfo> MII(T->createMCInstrInfo());
608 std::unique_ptr<const MCInstrAnalysis> MIA(
609 T->createMCInstrAnalysis(MII.get()));
610 if (!MIA)
611 return {};
612 Optional<SectionRef> Plt = None, RelaPlt = None, GotPlt = None;
613 for (const SectionRef &Section : sections()) {
614 Expected<StringRef> NameOrErr = Section.getName();
615 if (!NameOrErr) {
616 consumeError(NameOrErr.takeError());
617 continue;
618 }
619 StringRef Name = *NameOrErr;
620
621 if (Name == ".plt")
622 Plt = Section;
623 else if (Name == ".rela.plt" || Name == ".rel.plt")
624 RelaPlt = Section;
625 else if (Name == ".got.plt")
626 GotPlt = Section;
627 }
628 if (!Plt || !RelaPlt || !GotPlt)
629 return {};
630 Expected<StringRef> PltContents = Plt->getContents();
631 if (!PltContents) {
632 consumeError(PltContents.takeError());
633 return {};
634 }
635 auto PltEntries = MIA->findPltEntries(Plt->getAddress(),
636 arrayRefFromStringRef(*PltContents),
637 GotPlt->getAddress(), Triple);
638 // Build a map from GOT entry virtual address to PLT entry virtual address.
639 DenseMap<uint64_t, uint64_t> GotToPlt;
640 for (const auto &Entry : PltEntries)
641 GotToPlt.insert(std::make_pair(Entry.second, Entry.first));
642 // Find the relocations in the dynamic relocation table that point to
643 // locations in the GOT for which we know the corresponding PLT entry.
644 std::vector<std::pair<Optional<DataRefImpl>, uint64_t>> Result;
645 for (const auto &Relocation : RelaPlt->relocations()) {
646 if (Relocation.getType() != JumpSlotReloc)
647 continue;
648 auto PltEntryIter = GotToPlt.find(Relocation.getOffset());
649 if (PltEntryIter != GotToPlt.end()) {
650 symbol_iterator Sym = Relocation.getSymbol();
651 if (Sym == symbol_end())
652 Result.emplace_back(None, PltEntryIter->second);
653 else
654 Result.emplace_back(Sym->getRawDataRefImpl(), PltEntryIter->second);
655 }
656 }
657 return Result;
658}
659
660template <class ELFT>
661static Expected<std::vector<VersionEntry>>
662readDynsymVersionsImpl(const ELFFile<ELFT> &EF,
663 ELFObjectFileBase::elf_symbol_iterator_range Symbols) {
664 using Elf_Shdr = typename ELFT::Shdr;
665 const Elf_Shdr *VerSec = nullptr;
666 const Elf_Shdr *VerNeedSec = nullptr;
667 const Elf_Shdr *VerDefSec = nullptr;
668 // The user should ensure sections() can't fail here.
669 for (const Elf_Shdr &Sec : cantFail(EF.sections())) {
670 if (Sec.sh_type == ELF::SHT_GNU_versym)
671 VerSec = &Sec;
672 else if (Sec.sh_type == ELF::SHT_GNU_verdef)
673 VerDefSec = &Sec;
674 else if (Sec.sh_type == ELF::SHT_GNU_verneed)
675 VerNeedSec = &Sec;
676 }
677 if (!VerSec)
678 return std::vector<VersionEntry>();
679
680 Expected<SmallVector<Optional<VersionEntry>, 0>> MapOrErr =
681 EF.loadVersionMap(VerNeedSec, VerDefSec);
682 if (!MapOrErr)
683 return MapOrErr.takeError();
684
685 std::vector<VersionEntry> Ret;
686 size_t I = 0;
687 for (const ELFSymbolRef &Sym : Symbols) {
688 ++I;
689 Expected<const typename ELFT::Versym *> VerEntryOrErr =
690 EF.template getEntry<typename ELFT::Versym>(*VerSec, I);
691 if (!VerEntryOrErr)
692 return createError("unable to read an entry with index " + Twine(I) +
693 " from " + describe(EF, *VerSec) + ": " +
694 toString(VerEntryOrErr.takeError()));
695
696 Expected<uint32_t> FlagsOrErr = Sym.getFlags();
697 if (!FlagsOrErr)
698 return createError("unable to read flags for symbol with index " +
699 Twine(I) + ": " + toString(FlagsOrErr.takeError()));
700
701 bool IsDefault;
702 Expected<StringRef> VerOrErr = EF.getSymbolVersionByIndex(
703 (*VerEntryOrErr)->vs_index, IsDefault, *MapOrErr,
704 (*FlagsOrErr) & SymbolRef::SF_Undefined);
705 if (!VerOrErr)
706 return createError("unable to get a version for entry " + Twine(I) +
707 " of " + describe(EF, *VerSec) + ": " +
708 toString(VerOrErr.takeError()));
709
710 Ret.push_back({(*VerOrErr).str(), IsDefault});
711 }
712
713 return Ret;
714}
715
716Expected<std::vector<VersionEntry>>
717ELFObjectFileBase::readDynsymVersions() const {
718 elf_symbol_iterator_range Symbols = getDynamicSymbolIterators();
719 if (const auto *Obj = dyn_cast<ELF32LEObjectFile>(this))
720 return readDynsymVersionsImpl(Obj->getELFFile(), Symbols);
721 if (const auto *Obj = dyn_cast<ELF32BEObjectFile>(this))
722 return readDynsymVersionsImpl(Obj->getELFFile(), Symbols);
723 if (const auto *Obj = dyn_cast<ELF64LEObjectFile>(this))
724 return readDynsymVersionsImpl(Obj->getELFFile(), Symbols);
725 return readDynsymVersionsImpl(cast<ELF64BEObjectFile>(this)->getELFFile(),
726 Symbols);
727}
←

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