LLVM: include/llvm/Support/MathExtras.h Source File

LLVM 22.0.0git
MathExtras.h
Go to the documentation of this file.
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/STLForwardCompat.h"
17#include "llvm/ADT/bit.h"
18#include "llvm/Support/Compiler.h"
19#include <cassert>
20#include <climits>
21#include <cstdint>
22#include <cstring>
23#include <limits>
24#include <type_traits>
25
26namespace llvm {
27/// Some template parameter helpers to optimize for bitwidth, for functions that
28/// take multiple arguments.
29
30// We can't verify signedness, since callers rely on implicit coercions to
31// signed/unsigned.
32template <typename T, typename U>
33 using enableif_int =
34 std::enable_if_t<std::is_integral_v<T> && std::is_integral_v<U>>;
35
36// Use std::common_type_t to widen only up to the widest argument.
37template <typename T, typename U, typename = enableif_int<T, U>>
38 using common_uint =
39 std::common_type_t<std::make_unsigned_t<T>, std::make_unsigned_t<U>>;
40template <typename T, typename U, typename = enableif_int<T, U>>
41 using common_sint =
42 std::common_type_t<std::make_signed_t<T>, std::make_signed_t<U>>;
43
44/// Mathematical constants.
45namespace numbers {
46// clang-format off
47 inline constexpr float ef = e_v<float>;
48 inline constexpr float egammaf = egamma_v<float>;
49 inline constexpr float ln2f = ln2_v<float>;
50 inline constexpr float ln10f = ln10_v<float>;
51 inline constexpr float log2ef = log2e_v<float>;
52 inline constexpr float log10ef = log10e_v<float>;
53 inline constexpr float pif = pi_v<float>;
54 inline constexpr float inv_pif = inv_pi_v<float>;
55 inline constexpr float inv_sqrtpif = inv_sqrtpi_v<float>;
56 inline constexpr float sqrt2f = sqrt2_v<float>;
57 inline constexpr float inv_sqrt2f = inv_sqrt2_v<float>;
58 inline constexpr float sqrt3f = sqrt3_v<float>;
59 inline constexpr float inv_sqrt3f = inv_sqrt3_v<float>;
60 inline constexpr float phif = phi_v<float>;
61
62// sqrtpi is not in C++20 std::numbers.
63template <typename T, typename = std::enable_if_t<std::is_floating_point_v<T>>>
64 inline constexpr T sqrtpi_v = T(0x1.c5bf891b4ef6bP+0); // (1.7724538509055160273) https://oeis.org/A002161
65 inline constexpr double sqrtpi = sqrtpi_v<double>;
66 inline constexpr float sqrtpif = sqrtpi_v<float>;
67
68// These string literals are taken from below:
69// https://github.com/bminor/glibc/blob/8543577b04ded6d979ffcc5a818930e4d74d0645/math/math.h#L1215-L1229
70 constexpr const char *pis = "3.141592653589793238462643383279502884",
71 *inv_pis = "0.318309886183790671537767526745028724";
72// clang-format on
73} // namespace numbers
74
75/// Create a bitmask with the N right-most bits set to 1, and all other
76/// bits set to 0. Only unsigned types are allowed.
77 template <typename T> constexpr T maskTrailingOnes(unsigned N) {
78 static_assert(std::is_unsigned_v<T>, "Invalid type!");
79 const unsigned Bits = CHAR_BIT * sizeof(T);
80 assert(N <= Bits && "Invalid bit index");
81 if (N == 0)
82 return 0;
83 return T(-1) >> (Bits - N);
84}
85
86/// Create a bitmask with the N left-most bits set to 1, and all other
87/// bits set to 0. Only unsigned types are allowed.
88 template <typename T> constexpr T maskLeadingOnes(unsigned N) {
89 return ~maskTrailingOnes<T>(CHAR_BIT * sizeof(T) - N);
90}
91
92/// Create a bitmask with the N right-most bits set to 0, and all other
93/// bits set to 1. Only unsigned types are allowed.
94 template <typename T> constexpr T maskTrailingZeros(unsigned N) {
95 return maskLeadingOnes<T>(CHAR_BIT * sizeof(T) - N);
96}
97
98/// Create a bitmask with the N left-most bits set to 0, and all other
99/// bits set to 1. Only unsigned types are allowed.
100 template <typename T> constexpr T maskLeadingZeros(unsigned N) {
101 return maskTrailingOnes<T>(CHAR_BIT * sizeof(T) - N);
102}
103
104/// Macro compressed bit reversal table for 256 bits.
105///
106/// http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable
107 static const unsigned char BitReverseTable256[256] = {
108#define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64
109#define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16)
110#define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4)
111 R6(0), R6(2), R6(1), R6(3)
112#undef R2
113#undef R4
114#undef R6
115};
116
117/// Reverse the bits in \p Val.
118 template <typename T> constexpr T reverseBits(T Val) {
119#if __has_builtin(__builtin_bitreverse8)
120 if constexpr (std::is_same_v<T, uint8_t>)
121 return __builtin_bitreverse8(Val);
122#endif
123#if __has_builtin(__builtin_bitreverse16)
124 if constexpr (std::is_same_v<T, uint16_t>)
125 return __builtin_bitreverse16(Val);
126#endif
127#if __has_builtin(__builtin_bitreverse32)
128 if constexpr (std::is_same_v<T, uint32_t>)
129 return __builtin_bitreverse32(Val);
130#endif
131#if __has_builtin(__builtin_bitreverse64)
132 if constexpr (std::is_same_v<T, uint64_t>)
133 return __builtin_bitreverse64(Val);
134#endif
135
136 unsigned char in[sizeof(Val)];
137 unsigned char out[sizeof(Val)];
138 std::memcpy(in, &Val, sizeof(Val));
139 for (unsigned i = 0; i < sizeof(Val); ++i)
140 out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]];
141 std::memcpy(&Val, out, sizeof(Val));
142 return Val;
143}
144
145// NOTE: The following support functions use the _32/_64 extensions instead of
146// type overloading so that signed and unsigned integers can be used without
147// ambiguity.
148
149/// Return the high 32 bits of a 64 bit value.
151 return static_cast<uint32_t >(Value >> 32);
152}
153
154/// Return the low 32 bits of a 64 bit value.
156 return static_cast<uint32_t >(Value);
157}
158
159/// Make a 64-bit integer from a high / low pair of 32-bit integers.
161 return ((uint64_t)High << 32) | (uint64_t)Low;
162}
163
164/// Checks if an integer fits into the given bit width.
165 template <unsigned N> constexpr bool isInt(int64_t x) {
166 if constexpr (N == 0)
167 return 0 == x;
168 if constexpr (N == 8)
169 return static_cast<int8_t>(x) == x;
170 if constexpr (N == 16)
171 return static_cast<int16_t>(x) == x;
172 if constexpr (N == 32)
173 return static_cast<int32_t>(x) == x;
174 if constexpr (N < 64)
175 return -(INT64_C(1) << (N - 1)) <= x && x < (INT64_C(1) << (N - 1));
176 (void)x; // MSVC v19.25 warns that x is unused.
177 return true;
178}
179
180/// Checks if a signed integer is an N bit number shifted left by S.
181template <unsigned N, unsigned S>
182 constexpr bool isShiftedInt(int64_t x) {
183 static_assert(S < 64, "isShiftedInt<N, S> with S >= 64 is too much.");
184 static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
185 return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
186}
187
188/// Checks if an unsigned integer fits into the given bit width.
189 template <unsigned N> constexpr bool isUInt(uint64_t x) {
190 if constexpr (N < 64)
191 return (x >> N) == 0;
192 (void)x; // MSVC v19.25 warns that x is unused.
193 return true;
194}
195
196/// Checks if a unsigned integer is an N bit number shifted left by S.
197template <unsigned N, unsigned S>
198 constexpr bool isShiftedUInt(uint64_t x) {
199 static_assert(S < 64, "isShiftedUInt<N, S> with S >= 64 is too much.");
200 static_assert(N + S <= 64,
201 "isShiftedUInt<N, S> with N + S > 64 is too wide.");
202 // S must be strictly less than 64. So 1 << S is not undefined behavior.
203 return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
204}
205
206/// Gets the maximum value for a N-bit unsigned integer.
207 inline constexpr uint64_t maxUIntN(uint64_t N) {
208 assert(N <= 64 && "integer width out of range");
209
210 // uint64_t(1) << 64 is undefined behavior, so we can't do
211 // (uint64_t(1) << N) - 1
212 // without checking first that N != 64. But this works and doesn't have a
213 // branch for N != 0.
214 // Unfortunately, shifting a uint64_t right by 64 bit is undefined
215 // behavior, so the condition on N == 0 is necessary. Fortunately, most
216 // optimizers do not emit branches for this check.
217 if (N == 0)
218 return 0;
219 return UINT64_MAX >> (64 - N);
220}
221
222/// Gets the minimum value for a N-bit signed integer.
223 inline constexpr int64_t minIntN(int64_t N) {
224 assert(N <= 64 && "integer width out of range");
225
226 if (N == 0)
227 return 0;
228 return UINT64_C(1) + ~(UINT64_C(1) << (N - 1));
229}
230
231/// Gets the maximum value for a N-bit signed integer.
232 inline constexpr int64_t maxIntN(int64_t N) {
233 assert(N <= 64 && "integer width out of range");
234
235 // This relies on two's complement wraparound when N == 64, so we convert to
236 // int64_t only at the very end to avoid UB.
237 if (N == 0)
238 return 0;
239 return (UINT64_C(1) << (N - 1)) - 1;
240}
241
242/// Checks if an unsigned integer fits into the given (dynamic) bit width.
243 inline constexpr bool isUIntN(unsigned N, uint64_t x) {
244 return N >= 64 || x <= maxUIntN(N);
245}
246
247/// Checks if an signed integer fits into the given (dynamic) bit width.
248 inline constexpr bool isIntN(unsigned N, int64_t x) {
249 return N >= 64 || (minIntN(N) <= x && x <= maxIntN(N));
250}
251
252/// Return true if the argument is a non-empty sequence of ones starting at the
253/// least significant bit with the remainder zero (32 bit version).
254/// Ex. isMask_32(0x0000FFFFU) == true.
255 constexpr bool isMask_32(uint32_t Value) {
256 return Value && ((Value + 1) & Value) == 0;
257}
258
259/// Return true if the argument is a non-empty sequence of ones starting at the
260/// least significant bit with the remainder zero (64 bit version).
261 constexpr bool isMask_64(uint64_t Value) {
262 return Value && ((Value + 1) & Value) == 0;
263}
264
265/// Return true if the argument contains a non-empty sequence of ones with the
266/// remainder zero (32 bit version.) Ex. isShiftedMask_32(0x0000FF00U) == true.
268 return Value && isMask_32((Value - 1) | Value);
269}
270
271/// Return true if the argument contains a non-empty sequence of ones with the
272/// remainder zero (64 bit version.)
274 return Value && isMask_64((Value - 1) | Value);
275}
276
277/// Return true if the argument is a power of two > 0.
278/// Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.)
279 constexpr bool isPowerOf2_32(uint32_t Value) {
281}
282
283/// Return true if the argument is a power of two > 0 (64 bit edition.)
284 constexpr bool isPowerOf2_64(uint64_t Value) {
286}
287
288/// Return true if the argument contains a non-empty sequence of ones with the
289/// remainder zero (32 bit version.) Ex. isShiftedMask_32(0x0000FF00U) == true.
290/// If true, \p MaskIdx will specify the index of the lowest set bit and \p
291/// MaskLen is updated to specify the length of the mask, else neither are
292/// updated.
293 inline bool isShiftedMask_32(uint32_t Value, unsigned &MaskIdx,
294 unsigned &MaskLen) {
296 return false;
297 MaskIdx = llvm::countr_zero(Value);
298 MaskLen = llvm::popcount(Value);
299 return true;
300}
301
302/// Return true if the argument contains a non-empty sequence of ones with the
303/// remainder zero (64 bit version.) If true, \p MaskIdx will specify the index
304/// of the lowest set bit and \p MaskLen is updated to specify the length of the
305/// mask, else neither are updated.
306 inline bool isShiftedMask_64(uint64_t Value, unsigned &MaskIdx,
307 unsigned &MaskLen) {
309 return false;
310 MaskIdx = llvm::countr_zero(Value);
311 MaskLen = llvm::popcount(Value);
312 return true;
313}
314
315/// Compile time Log2.
316/// Valid only for positive powers of two.
317 template <size_t kValue> constexpr size_t ConstantLog2() {
318 static_assert(llvm::isPowerOf2_64(kValue), "Value is not a valid power of 2");
319 return llvm::countr_zero_constexpr(kValue);
320}
321
322template <size_t kValue>
323LLVM_DEPRECATED("Use ConstantLog2 instead", "ConstantLog2")
324 constexpr size_t CTLog2() {
325 return ConstantLog2<kValue>();
326}
327
328/// Return the floor log base 2 of the specified value, -1 if the value is zero.
329/// (32 bit edition.)
330/// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2
331 inline unsigned Log2_32(uint32_t Value) {
332 return 31 - llvm::countl_zero(Value);
333}
334
335/// Return the floor log base 2 of the specified value, -1 if the value is zero.
336/// (64 bit edition.)
337 inline unsigned Log2_64(uint64_t Value) {
338 return 63 - llvm::countl_zero(Value);
339}
340
341/// Return the ceil log base 2 of the specified value, 32 if the value is zero.
342/// (32 bit edition).
343/// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3
344 inline unsigned Log2_32_Ceil(uint32_t Value) {
345 return 32 - llvm::countl_zero(Value - 1);
346}
347
348/// Return the ceil log base 2 of the specified value, 64 if the value is zero.
349/// (64 bit edition.)
350 inline unsigned Log2_64_Ceil(uint64_t Value) {
351 return 64 - llvm::countl_zero(Value - 1);
352}
353
354/// A and B are either alignments or offsets. Return the minimum alignment that
355/// may be assumed after adding the two together.
356template <typename U, typename V, typename T = common_uint<U, V>>
357 constexpr T MinAlign(U A, V B) {
358 // The largest power of 2 that divides both A and B.
359 //
360 // Replace "-Value" by "1+~Value" in the following commented code to avoid
361 // MSVC warning C4146
362 // return (A | B) & -(A | B);
363 return (A | B) & (1 + ~(A | B));
364}
365
366/// Fallback when arguments aren't integral.
368 return (A | B) & (1 + ~(A | B));
369}
370
371/// Returns the next power of two (in 64-bits) that is strictly greater than A.
372/// Returns zero on overflow.
374 A |= (A >> 1);
375 A |= (A >> 2);
376 A |= (A >> 4);
377 A |= (A >> 8);
378 A |= (A >> 16);
379 A |= (A >> 32);
380 return A + 1;
381}
382
383/// Returns the power of two which is greater than or equal to the given value.
384/// Essentially, it is a ceil operation across the domain of powers of two.
386 if (!A || A > UINT64_MAX / 2)
387 return 0;
388 return UINT64_C(1) << Log2_64_Ceil(A);
389}
390
391/// Returns the integer ceil(Numerator / Denominator). Unsigned version.
392/// Guaranteed to never overflow.
393template <typename U, typename V, typename T = common_uint<U, V>>
394 constexpr T divideCeil(U Numerator, V Denominator) {
395 assert(Denominator && "Division by zero");
396 T Bias = (Numerator != 0);
397 return (Numerator - Bias) / Denominator + Bias;
398}
399
400/// Fallback when arguments aren't integral.
401 constexpr uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator) {
402 assert(Denominator && "Division by zero");
403 uint64_t Bias = (Numerator != 0);
404 return (Numerator - Bias) / Denominator + Bias;
405}
406
407// Check whether divideCeilSigned or divideFloorSigned would overflow. This
408// happens only when Numerator = INT_MIN and Denominator = -1.
409template <typename U, typename V>
410 constexpr bool divideSignedWouldOverflow(U Numerator, V Denominator) {
411 return Numerator == std::numeric_limits<U>::min() && Denominator == -1;
412}
413
414/// Returns the integer ceil(Numerator / Denominator). Signed version.
415/// Overflow is explicitly forbidden with an assert.
416template <typename U, typename V, typename T = common_sint<U, V>>
417 constexpr T divideCeilSigned(U Numerator, V Denominator) {
418 assert(Denominator && "Division by zero");
419 assert(!divideSignedWouldOverflow(Numerator, Denominator) &&
420 "Divide would overflow");
421 if (!Numerator)
422 return 0;
423 // C's integer division rounds towards 0.
424 T Bias = Denominator >= 0 ? 1 : -1;
425 bool SameSign = (Numerator >= 0) == (Denominator >= 0);
426 return SameSign ? (Numerator - Bias) / Denominator + 1
427 : Numerator / Denominator;
428}
429
430/// Returns the integer floor(Numerator / Denominator). Signed version.
431/// Overflow is explicitly forbidden with an assert.
432template <typename U, typename V, typename T = common_sint<U, V>>
433 constexpr T divideFloorSigned(U Numerator, V Denominator) {
434 assert(Denominator && "Division by zero");
435 assert(!divideSignedWouldOverflow(Numerator, Denominator) &&
436 "Divide would overflow");
437 if (!Numerator)
438 return 0;
439 // C's integer division rounds towards 0.
440 T Bias = Denominator >= 0 ? -1 : 1;
441 bool SameSign = (Numerator >= 0) == (Denominator >= 0);
442 return SameSign ? Numerator / Denominator
443 : (Numerator - Bias) / Denominator - 1;
444}
445
446/// Returns the remainder of the Euclidean division of LHS by RHS. Result is
447/// always non-negative.
448template <typename U, typename V, typename T = common_sint<U, V>>
449 constexpr T mod(U Numerator, V Denominator) {
450 assert(Denominator >= 1 && "Mod by non-positive number");
451 T Mod = Numerator % Denominator;
452 return Mod < 0 ? Mod + Denominator : Mod;
453}
454
455/// Returns (Numerator / Denominator) rounded by round-half-up. Guaranteed to
456/// never overflow.
457template <typename U, typename V, typename T = common_uint<U, V>>
458 constexpr T divideNearest(U Numerator, V Denominator) {
459 assert(Denominator && "Division by zero");
460 T Mod = Numerator % Denominator;
461 return (Numerator / Denominator) +
462 (Mod > (static_cast<T >(Denominator) - 1) / 2);
463}
464
465/// Returns the next integer (mod 2**nbits) that is greater than or equal to
466/// \p Value and is a multiple of \p Align. \p Align must be non-zero.
467///
468/// Examples:
469/// \code
470/// alignTo(5, 8) = 8
471/// alignTo(17, 8) = 24
472/// alignTo(~0LL, 8) = 0
473/// alignTo(321, 255) = 510
474/// \endcode
475///
476/// Will overflow only if result is not representable in T.
477template <typename U, typename V, typename T = common_uint<U, V>>
478 constexpr T alignTo(U Value, V Align) {
479 assert(Align != 0u && "Align can't be 0.");
480 T CeilDiv = divideCeil(Value, Align);
481 return CeilDiv * Align;
482}
483
484/// Fallback when arguments aren't integral.
486 assert(Align != 0u && "Align can't be 0.");
487 uint64_t CeilDiv = divideCeil(Value, Align);
488 return CeilDiv * Align;
489}
490
491/// Will overflow only if result is not representable in T.
492template <typename U, typename V, typename T = common_uint<U, V>>
493 constexpr T alignToPowerOf2(U Value, V Align) {
494 assert(Align != 0 && (Align & (Align - 1)) == 0 &&
495 "Align must be a power of 2");
496 T NegAlign = static_cast<T >(0) - Align;
497 return (Value + (Align - 1)) & NegAlign;
498}
499
500/// Fallback when arguments aren't integral.
502 assert(Align != 0 && (Align & (Align - 1)) == 0 &&
503 "Align must be a power of 2");
504 uint64_t NegAlign = 0 - Align;
505 return (Value + (Align - 1)) & NegAlign;
506}
507
508/// If non-zero \p Skew is specified, the return value will be a minimal integer
509/// that is greater than or equal to \p Size and equal to \p A * N + \p Skew for
510/// some integer N. If \p Skew is larger than \p A, its value is adjusted to '\p
511/// Skew mod \p A'. \p Align must be non-zero.
512///
513/// Examples:
514/// \code
515/// alignTo(5, 8, 7) = 7
516/// alignTo(17, 8, 1) = 17
517/// alignTo(~0LL, 8, 3) = 3
518/// alignTo(321, 255, 42) = 552
519/// \endcode
520///
521/// May overflow.
522template <typename U, typename V, typename W,
523 typename T = common_uint<common_uint<U, V>, W>>
524 constexpr T alignTo(U Value, V Align, W Skew) {
525 assert(Align != 0u && "Align can't be 0.");
526 Skew %= Align;
527 return alignTo(Value - Skew, Align) + Skew;
528}
529
530/// Returns the next integer (mod 2**nbits) that is greater than or equal to
531/// \p Value and is a multiple of \c Align. \c Align must be non-zero.
532///
533/// Will overflow only if result is not representable in T.
534template <auto Align, typename V, typename T = common_uint<decltype(Align), V>>
535 constexpr T alignTo(V Value) {
536 static_assert(Align != 0u, "Align must be non-zero");
537 T CeilDiv = divideCeil(Value, Align);
538 return CeilDiv * Align;
539}
540
541/// Returns the largest unsigned integer less than or equal to \p Value and is
542/// \p Skew mod \p Align. \p Align must be non-zero. Guaranteed to never
543/// overflow.
544template <typename U, typename V, typename W = uint8_t,
545 typename T = common_uint<common_uint<U, V>, W>>
546 constexpr T alignDown(U Value, V Align, W Skew = 0) {
547 assert(Align != 0u && "Align can't be 0.");
548 Skew %= Align;
549 return (Value - Skew) / Align * Align + Skew;
550}
551
552/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
553/// Requires B <= 32.
554 template <unsigned B> constexpr int32_t SignExtend32(uint32_t X) {
555 static_assert(B <= 32, "Bit width out of range.");
556 if constexpr (B == 0)
557 return 0;
558 return int32_t(X << (32 - B)) >> (32 - B);
559}
560
561/// Sign-extend the number in the bottom B bits of X to a 32-bit integer.
562/// Requires B <= 32.
563 inline int32_t SignExtend32(uint32_t X, unsigned B) {
564 assert(B <= 32 && "Bit width out of range.");
565 if (B == 0)
566 return 0;
567 return int32_t(X << (32 - B)) >> (32 - B);
568}
569
570/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
571/// Requires B <= 64.
572 template <unsigned B> constexpr int64_t SignExtend64(uint64_t x) {
573 static_assert(B <= 64, "Bit width out of range.");
574 if constexpr (B == 0)
575 return 0;
576 return int64_t(x << (64 - B)) >> (64 - B);
577}
578
579/// Sign-extend the number in the bottom B bits of X to a 64-bit integer.
580/// Requires B <= 64.
581 inline int64_t SignExtend64(uint64_t X, unsigned B) {
582 assert(B <= 64 && "Bit width out of range.");
583 if (B == 0)
584 return 0;
585 return int64_t(X << (64 - B)) >> (64 - B);
586}
587
588/// Return the absolute value of a signed integer, converted to the
589/// corresponding unsigned integer type. Avoids undefined behavior in std::abs
590/// when you pass it INT_MIN or similar.
591template <typename T, typename U = std::make_unsigned_t<T>>
592 constexpr U AbsoluteValue(T X) {
593 // If X is negative, cast it to the unsigned type _before_ negating it.
594 return X < 0 ? -static_cast<U>(X) : X;
595}
596
597/// Subtract two unsigned integers, X and Y, of type T and return the absolute
598/// value of the result.
599template <typename U, typename V, typename T = common_uint<U, V>>
600 constexpr T AbsoluteDifference(U X, V Y) {
601 return X > Y ? (X - Y) : (Y - X);
602}
603
604/// Add two unsigned integers, X and Y, of type T. Clamp the result to the
605/// maximum representable value of T on overflow. ResultOverflowed indicates if
606/// the result is larger than the maximum representable value of type T.
607template <typename T>
608std::enable_if_t<std::is_unsigned_v<T>, T>
609 SaturatingAdd(T X, T Y, bool *ResultOverflowed = nullptr) {
610 bool Dummy;
611 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
612 // Hacker's Delight, p. 29
613 T Z = X + Y;
614 Overflowed = (Z < X || Z < Y);
615 if (Overflowed)
616 return std::numeric_limits<T>::max();
617 else
618 return Z;
619}
620
621/// Add multiple unsigned integers of type T. Clamp the result to the
622/// maximum representable value of T on overflow.
623template <class T, class... Ts>
624 std::enable_if_t<std::is_unsigned_v<T>, T> SaturatingAdd(T X, T Y, T Z,
625 Ts... Args) {
626 bool Overflowed = false;
627 T XY = SaturatingAdd(X, Y, &Overflowed);
628 if (Overflowed)
629 return SaturatingAdd(std::numeric_limits<T>::max(), T(1), Args...);
630 return SaturatingAdd(XY, Z, Args...);
631}
632
633/// Multiply two unsigned integers, X and Y, of type T. Clamp the result to the
634/// maximum representable value of T on overflow. ResultOverflowed indicates if
635/// the result is larger than the maximum representable value of type T.
636template <typename T>
637std::enable_if_t<std::is_unsigned_v<T>, T>
638 SaturatingMultiply(T X, T Y, bool *ResultOverflowed = nullptr) {
639 bool Dummy;
640 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
641
642 // Hacker's Delight, p. 30 has a different algorithm, but we don't use that
643 // because it fails for uint16_t (where multiplication can have undefined
644 // behavior due to promotion to int), and requires a division in addition
645 // to the multiplication.
646
647 Overflowed = false;
648
649 // Log2(Z) would be either Log2Z or Log2Z + 1.
650 // Special case: if X or Y is 0, Log2_64 gives -1, and Log2Z
651 // will necessarily be less than Log2Max as desired.
652 int Log2Z = Log2_64(X) + Log2_64(Y);
653 const T Max = std::numeric_limits<T>::max();
654 int Log2Max = Log2_64(Max);
655 if (Log2Z < Log2Max) {
656 return X * Y;
657 }
658 if (Log2Z > Log2Max) {
659 Overflowed = true;
660 return Max;
661 }
662
663 // We're going to use the top bit, and maybe overflow one
664 // bit past it. Multiply all but the bottom bit then add
665 // that on at the end.
666 T Z = (X >> 1) * Y;
667 if (Z & ~(Max >> 1)) {
668 Overflowed = true;
669 return Max;
670 }
671 Z <<= 1;
672 if (X & 1)
673 return SaturatingAdd(Z, Y, ResultOverflowed);
674
675 return Z;
676}
677
678/// Multiply two unsigned integers, X and Y, and add the unsigned integer, A to
679/// the product. Clamp the result to the maximum representable value of T on
680/// overflow. ResultOverflowed indicates if the result is larger than the
681/// maximum representable value of type T.
682template <typename T>
683std::enable_if_t<std::is_unsigned_v<T>, T>
684 SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed = nullptr) {
685 bool Dummy;
686 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
687
688 T Product = SaturatingMultiply(X, Y, &Overflowed);
689 if (Overflowed)
690 return Product;
691
692 return SaturatingAdd(A, Product, &Overflowed);
693}
694
695/// Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
696LLVM_ABI extern const float huge_valf;
697
698/// Add two signed integers, computing the two's complement truncated result,
699/// returning true if overflow occurred.
700template <typename T>
701 std::enable_if_t<std::is_signed_v<T>, T> AddOverflow(T X, T Y, T &Result) {
702#if __has_builtin(__builtin_add_overflow)
703 return __builtin_add_overflow(X, Y, &Result);
704#else
705 // Perform the unsigned addition.
706 using U = std::make_unsigned_t<T>;
707 const U UX = static_cast<U>(X);
708 const U UY = static_cast<U>(Y);
709 const U UResult = UX + UY;
710
711 // Convert to signed.
712 Result = static_cast<T >(UResult);
713
714 // Adding two positive numbers should result in a positive number.
715 if (X > 0 && Y > 0)
716 return Result <= 0;
717 // Adding two negatives should result in a negative number.
718 if (X < 0 && Y < 0)
719 return Result >= 0;
720 return false;
721#endif
722}
723
724/// Subtract two signed integers, computing the two's complement truncated
725/// result, returning true if an overflow occurred.
726template <typename T>
727 std::enable_if_t<std::is_signed_v<T>, T> SubOverflow(T X, T Y, T &Result) {
728#if __has_builtin(__builtin_sub_overflow)
729 return __builtin_sub_overflow(X, Y, &Result);
730#else
731 // Perform the unsigned addition.
732 using U = std::make_unsigned_t<T>;
733 const U UX = static_cast<U>(X);
734 const U UY = static_cast<U>(Y);
735 const U UResult = UX - UY;
736
737 // Convert to signed.
738 Result = static_cast<T >(UResult);
739
740 // Subtracting a positive number from a negative results in a negative number.
741 if (X <= 0 && Y > 0)
742 return Result >= 0;
743 // Subtracting a negative number from a positive results in a positive number.
744 if (X >= 0 && Y < 0)
745 return Result <= 0;
746 return false;
747#endif
748}
749
750/// Multiply two signed integers, computing the two's complement truncated
751/// result, returning true if an overflow occurred.
752template <typename T>
753 std::enable_if_t<std::is_signed_v<T>, T> MulOverflow(T X, T Y, T &Result) {
754#if __has_builtin(__builtin_mul_overflow)
755 return __builtin_mul_overflow(X, Y, &Result);
756#else
757 // Perform the unsigned multiplication on absolute values.
758 using U = std::make_unsigned_t<T>;
759 const U UX = X < 0 ? (0 - static_cast<U>(X)) : static_cast<U>(X);
760 const U UY = Y < 0 ? (0 - static_cast<U>(Y)) : static_cast<U>(Y);
761 const U UResult = UX * UY;
762
763 // Convert to signed.
764 const bool IsNegative = (X < 0) ^ (Y < 0);
765 Result = IsNegative ? (0 - UResult) : UResult;
766
767 // If any of the args was 0, result is 0 and no overflow occurs.
768 if (UX == 0 || UY == 0)
769 return false;
770
771 // UX and UY are in [1, 2^n], where n is the number of digits.
772 // Check how the max allowed absolute value (2^n for negative, 2^(n-1) for
773 // positive) divided by an argument compares to the other.
774 if (IsNegative)
775 return UX > (static_cast<U>(std::numeric_limits<T>::max()) + U(1)) / UY;
776 else
777 return UX > (static_cast<U>(std::numeric_limits<T>::max())) / UY;
778#endif
779}
780
781/// Type to force float point values onto the stack, so that x86 doesn't add
782/// hidden precision, avoiding rounding differences on various platforms.
783#if defined(__i386__) || defined(_M_IX86)
784using stack_float_t = volatile float;
785#else
786 using stack_float_t = float;
787#endif
788
789} // namespace llvm
790
791#endif
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
A
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DEPRECATED(MSG, FIX)
Definition Compiler.h:252
#define LLVM_ABI
Definition Compiler.h:213
#define R6(n)
T
#define T
uint64_t High
This file contains library features backported from future STL versions.
Y
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
X
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
This file implements the C++20 <bit> header.
LLVM Value Representation.
Definition Value.h:75
#define UINT64_MAX
Definition DataTypes.h:77
Mathematical constants.
constexpr T log10e_v
constexpr float inv_sqrtpif
Definition MathExtras.h:55
constexpr T e_v
constexpr T log2e_v
constexpr double sqrtpi
Definition MathExtras.h:65
constexpr float pif
Definition MathExtras.h:53
constexpr float sqrtpif
Definition MathExtras.h:66
constexpr float log10ef
Definition MathExtras.h:52
constexpr T egamma_v
constexpr float ln10f
Definition MathExtras.h:50
constexpr T sqrt3_v
constexpr T sqrt2_v
constexpr float phif
Definition MathExtras.h:60
constexpr T inv_sqrt3_v
constexpr const char * pis
Definition MathExtras.h:70
constexpr float sqrt3f
Definition MathExtras.h:58
constexpr T inv_sqrtpi_v
constexpr float log2ef
Definition MathExtras.h:51
constexpr T ln10_v
constexpr float sqrt2f
Definition MathExtras.h:56
constexpr const char * inv_pis
Definition MathExtras.h:71
constexpr T pi_v
constexpr float inv_pif
Definition MathExtras.h:54
constexpr T sqrtpi_v
Definition MathExtras.h:64
constexpr T phi_v
constexpr float inv_sqrt2f
Definition MathExtras.h:57
constexpr T ln2_v
constexpr float egammaf
Definition MathExtras.h:48
constexpr T inv_pi_v
constexpr T inv_sqrt2_v
constexpr float ln2f
Definition MathExtras.h:49
constexpr float ef
Definition MathExtras.h:47
constexpr float inv_sqrt3f
Definition MathExtras.h:59
This is an optimization pass for GlobalISel generic memory operations.
Definition AddressRanges.h:18
@ Low
Lower the current thread's priority such that it does not affect foreground tasks significantly.
Definition Threading.h:280
unsigned Log2_32_Ceil(uint32_t Value)
Return the ceil log base 2 of the specified value, 32 if the value is zero.
Definition MathExtras.h:344
std::enable_if_t< std::is_signed_v< T >, T > MulOverflow(T X, T Y, T &Result)
Multiply two signed integers, computing the two's complement truncated result, returning true if an o...
Definition MathExtras.h:753
constexpr bool divideSignedWouldOverflow(U Numerator, V Denominator)
Definition MathExtras.h:410
LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt mod(const DynamicAPInt &LHS, const DynamicAPInt &RHS)
is always non-negative.
Definition DynamicAPInt.h:395
constexpr uint64_t maxUIntN(uint64_t N)
Gets the maximum value for a N-bit unsigned integer.
Definition MathExtras.h:207
constexpr size_t CTLog2()
Definition MathExtras.h:324
constexpr bool isInt(int64_t x)
Checks if an integer fits into the given bit width.
Definition MathExtras.h:165
unsigned Log2_64_Ceil(uint64_t Value)
Return the ceil log base 2 of the specified value, 64 if the value is zero.
Definition MathExtras.h:350
constexpr bool isMask_32(uint32_t Value)
Return true if the argument is a non-empty sequence of ones starting at the least significant bit wit...
Definition MathExtras.h:255
constexpr T divideFloorSigned(U Numerator, V Denominator)
Returns the integer floor(Numerator / Denominator).
Definition MathExtras.h:433
constexpr int64_t minIntN(int64_t N)
Gets the minimum value for a N-bit signed integer.
Definition MathExtras.h:223
constexpr size_t ConstantLog2()
Compile time Log2.
Definition MathExtras.h:317
constexpr T maskLeadingOnes(unsigned N)
Create a bitmask with the N left-most bits set to 1, and all other bits set to 0.
Definition MathExtras.h:88
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
Definition MathExtras.h:243
constexpr T alignDown(U Value, V Align, W Skew=0)
Returns the largest unsigned integer less than or equal to Value and is Skew mod Align.
Definition MathExtras.h:546
constexpr bool isPowerOf2_64(uint64_t Value)
Return true if the argument is a power of two > 0 (64 bit edition.)
Definition MathExtras.h:284
constexpr bool isShiftedMask_32(uint32_t Value)
Return true if the argument contains a non-empty sequence of ones with the remainder zero (32 bit ver...
Definition MathExtras.h:267
constexpr int popcount(T Value) noexcept
Count the number of set bits in a value.
Definition bit.h:154
unsigned Log2_64(uint64_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
Definition MathExtras.h:337
uint64_t PowerOf2Ceil(uint64_t A)
Returns the power of two which is greater than or equal to the given value.
Definition MathExtras.h:385
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
Definition bit.h:202
constexpr bool isShiftedMask_64(uint64_t Value)
Return true if the argument contains a non-empty sequence of ones with the remainder zero (64 bit ver...
Definition MathExtras.h:273
constexpr T MinAlign(U A, V B)
A and B are either alignments or offsets.
Definition MathExtras.h:357
constexpr T divideNearest(U Numerator, V Denominator)
Returns (Numerator / Denominator) rounded by round-half-up.
Definition MathExtras.h:458
constexpr bool has_single_bit(T Value) noexcept
Definition bit.h:147
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
Definition MathExtras.h:331
int countl_zero(T Val)
Count number of 0's from the most significant bit to the least stopping at the first 1.
Definition bit.h:236
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition MathExtras.h:279
constexpr uint32_t Hi_32(uint64_t Value)
Return the high 32 bits of a 64 bit value.
Definition MathExtras.h:150
constexpr T alignToPowerOf2(U Value, V Align)
Will overflow only if result is not representable in T.
Definition MathExtras.h:493
constexpr bool isMask_64(uint64_t Value)
Return true if the argument is a non-empty sequence of ones starting at the least significant bit wit...
Definition MathExtras.h:261
std::enable_if_t< std::is_unsigned_v< T >, T > SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed=nullptr)
Multiply two unsigned integers, X and Y, and add the unsigned integer, A to the product.
Definition MathExtras.h:684
constexpr bool isUInt(uint64_t x)
Checks if an unsigned integer fits into the given bit width.
Definition MathExtras.h:189
std::common_type_t< std::make_unsigned_t< T >, std::make_unsigned_t< U > > common_uint
Definition MathExtras.h:38
constexpr T divideCeilSigned(U Numerator, V Denominator)
Returns the integer ceil(Numerator / Denominator).
Definition MathExtras.h:417
constexpr uint32_t Lo_32(uint64_t Value)
Return the low 32 bits of a 64 bit value.
Definition MathExtras.h:155
constexpr T maskLeadingZeros(unsigned N)
Create a bitmask with the N left-most bits set to 0, and all other bits set to 1.
Definition MathExtras.h:100
@ Mod
The access may modify the value stored in memory.
Definition ModRef.h:34
constexpr T divideCeil(U Numerator, V Denominator)
Returns the integer ceil(Numerator / Denominator).
Definition MathExtras.h:394
LLVM_ABI const float huge_valf
Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
Definition MathExtras.cpp:28
std::enable_if_t< std::is_unsigned_v< T >, T > SaturatingMultiply(T X, T Y, bool *ResultOverflowed=nullptr)
Multiply two unsigned integers, X and Y, of type T.
Definition MathExtras.h:638
constexpr T maskTrailingZeros(unsigned N)
Create a bitmask with the N right-most bits set to 0, and all other bits set to 1.
Definition MathExtras.h:94
std::common_type_t< std::make_signed_t< T >, std::make_signed_t< U > > common_sint
Definition MathExtras.h:41
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition Alignment.h:144
constexpr T AbsoluteDifference(U X, V Y)
Subtract two unsigned integers, X and Y, of type T and return the absolute value of the result.
Definition MathExtras.h:600
constexpr U AbsoluteValue(T X)
Return the absolute value of a signed integer, converted to the corresponding unsigned integer type.
Definition MathExtras.h:592
constexpr bool isShiftedInt(int64_t x)
Checks if a signed integer is an N bit number shifted left by S.
Definition MathExtras.h:182
constexpr int64_t maxIntN(int64_t N)
Gets the maximum value for a N-bit signed integer.
Definition MathExtras.h:232
constexpr int32_t SignExtend32(uint32_t X)
Sign-extend the number in the bottom B bits of X to a 32-bit integer.
Definition MathExtras.h:554
constexpr int countr_zero_constexpr(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
Definition bit.h:188
constexpr bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
Definition MathExtras.h:248
constexpr T reverseBits(T Val)
Reverse the bits in Val.
Definition MathExtras.h:118
constexpr int64_t SignExtend64(uint64_t x)
Sign-extend the number in the bottom B bits of X to a 64-bit integer.
Definition MathExtras.h:572
std::enable_if_t< std::is_signed_v< T >, T > AddOverflow(T X, T Y, T &Result)
Add two signed integers, computing the two's complement truncated result, returning true if overflow ...
Definition MathExtras.h:701
float stack_float_t
Type to force float point values onto the stack, so that x86 doesn't add hidden precision,...
Definition MathExtras.h:786
std::enable_if_t< std::is_signed_v< T >, T > SubOverflow(T X, T Y, T &Result)
Subtract two signed integers, computing the two's complement truncated result, returning true if an o...
Definition MathExtras.h:727
std::enable_if_t< std::is_integral_v< T > &&std::is_integral_v< U > > enableif_int
Some template parameter helpers to optimize for bitwidth, for functions that take multiple arguments.
Definition MathExtras.h:33
static const unsigned char BitReverseTable256[256]
Macro compressed bit reversal table for 256 bits.
Definition MathExtras.h:107
constexpr T maskTrailingOnes(unsigned N)
Create a bitmask with the N right-most bits set to 1, and all other bits set to 0.
Definition MathExtras.h:77
std::enable_if_t< std::is_unsigned_v< T >, T > SaturatingAdd(T X, T Y, bool *ResultOverflowed=nullptr)
Add two unsigned integers, X and Y, of type T.
Definition MathExtras.h:609
constexpr bool isShiftedUInt(uint64_t x)
Checks if a unsigned integer is an N bit number shifted left by S.
Definition MathExtras.h:198
constexpr uint64_t Make_64(uint32_t High, uint32_t Low)
Make a 64-bit integer from a high / low pair of 32-bit integers.
Definition MathExtras.h:160
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
Definition MathExtras.h:373
N
#define N
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition Alignment.h:39
Generated on for LLVM by doxygen 1.14.0

AltStyle によって変換されたページ (->オリジナル) /