13#ifndef LLVM_SUPPORT_MATHEXTRAS_H
14#define LLVM_SUPPORT_MATHEXTRAS_H
31template <
typename T,
typename U>
33 std::enable_if_t<std::is_integral_v<T> && std::is_integral_v<U>>;
36template <
typename T,
typename U,
typename = enableif_
int<T, U>>
38 std::common_type_t<std::make_unsigned_t<T>, std::make_unsigned_t<U>>;
39template <
typename T,
typename U,
typename = enableif_
int<T, U>>
41 std::common_type_t<std::make_signed_t<T>, std::make_signed_t<U>>;
47constexpr double e = 0x1.5bf0a8b145769P+1,
49 ln2 = 0x1.62e42fefa39efP-1,
50 ln10 = 0x1.26bb1bbb55516P+1,
53 pi = 0x1.921fb54442d18P+1,
61 phi = 0x1.9e3779b97f4a8P+0;
62constexpr float ef = 0x1.5bf0a8P+1F,
83 static_assert(std::is_unsigned_v<T>,
"Invalid type!");
84 const unsigned Bits = CHAR_BIT *
sizeof(
T);
85 assert(
N <= Bits &&
"Invalid bit index");
88 return T(-1) >> (Bits -
N);
94 return ~maskTrailingOnes<T>(CHAR_BIT *
sizeof(
T) -
N);
100 return maskLeadingOnes<T>(CHAR_BIT *
sizeof(
T) -
N);
106 return maskTrailingOnes<T>(CHAR_BIT *
sizeof(
T) -
N);
113#define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64
114#define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16)
115#define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4)
124#if __has_builtin(__builtin_bitreverse8)
125 if constexpr (std::is_same_v<T, uint8_t>)
126 return __builtin_bitreverse8(Val);
128#if __has_builtin(__builtin_bitreverse16)
129 if constexpr (std::is_same_v<T, uint16_t>)
130 return __builtin_bitreverse16(Val);
132#if __has_builtin(__builtin_bitreverse32)
133 if constexpr (std::is_same_v<T, uint32_t>)
134 return __builtin_bitreverse32(Val);
136#if __has_builtin(__builtin_bitreverse64)
137 if constexpr (std::is_same_v<T, uint64_t>)
138 return __builtin_bitreverse64(Val);
141 unsigned char in[
sizeof(Val)];
142 unsigned char out[
sizeof(Val)];
143 std::memcpy(in, &Val,
sizeof(Val));
144 for (
unsigned i = 0; i <
sizeof(Val); ++i)
146 std::memcpy(&Val, out,
sizeof(Val));
170template <
unsigned N>
constexpr bool isInt(int64_t x) {
171 if constexpr (
N == 0)
173 if constexpr (
N == 8)
174 return static_cast<int8_t
>(x) == x;
175 if constexpr (
N == 16)
176 return static_cast<int16_t
>(x) == x;
177 if constexpr (
N == 32)
178 return static_cast<int32_t
>(x) == x;
179 if constexpr (
N < 64)
180 return -(INT64_C(1) << (
N - 1)) <= x && x < (INT64_C(1) << (
N - 1));
186template <
unsigned N,
unsigned S>
188 static_assert(S < 64,
"isShiftedInt<N, S> with S >= 64 is too much.");
189 static_assert(
N + S <= 64,
"isShiftedInt<N, S> with N + S > 64 is too wide.");
190 return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
195 if constexpr (
N == 0)
197 if constexpr (
N == 8)
198 return static_cast<uint8_t>(x) == x;
199 if constexpr (
N == 16)
200 return static_cast<uint16_t>(x) == x;
201 if constexpr (
N == 32)
202 return static_cast<uint32_t>(x) == x;
203 if constexpr (
N < 64)
204 return x < (UINT64_C(1) << (
N));
210template <
unsigned N,
unsigned S>
212 static_assert(S < 64,
"isShiftedUInt<N, S> with S >= 64 is too much.");
213 static_assert(
N + S <= 64,
214 "isShiftedUInt<N, S> with N + S > 64 is too wide.");
216 return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
221 assert(
N <= 64 &&
"integer width out of range");
237 assert(
N <= 64 &&
"integer width out of range");
241 return UINT64_C(1) + ~(UINT64_C(1) << (
N - 1));
246 assert(
N <= 64 &&
"integer width out of range");
252 return (UINT64_C(1) << (
N - 1)) - 1;
330template <
size_t kValue>
constexpr size_t CTLog2() {
332 "Value is not a valid power of 2");
333 return 1 +
CTLog2<kValue / 2>();
366template <
typename U,
typename V,
typename T = common_u
int<U, V>>
373 return (
A |
B) & (1 + ~(
A |
B));
378 return (
A |
B) & (1 + ~(
A |
B));
403template <
typename U,
typename V,
typename T = common_u
int<U, V>>
405 assert(Denominator &&
"Division by zero");
406 T Bias = (Numerator != 0);
407 return (Numerator - Bias) / Denominator + Bias;
412 assert(Denominator &&
"Division by zero");
414 return (Numerator - Bias) / Denominator + Bias;
419template <
typename U,
typename V>
421 return Numerator == std::numeric_limits<U>::min() && Denominator == -1;
426template <
typename U,
typename V,
typename T = common_s
int<U, V>>
428 assert(Denominator &&
"Division by zero");
430 "Divide would overflow");
434 T Bias = Denominator >= 0 ? 1 : -1;
435 bool SameSign = (Numerator >= 0) == (Denominator >= 0);
436 return SameSign ? (Numerator - Bias) / Denominator + 1
437 : Numerator / Denominator;
442template <
typename U,
typename V,
typename T = common_s
int<U, V>>
444 assert(Denominator &&
"Division by zero");
446 "Divide would overflow");
450 T Bias = Denominator >= 0 ? -1 : 1;
451 bool SameSign = (Numerator >= 0) == (Denominator >= 0);
452 return SameSign ? Numerator / Denominator
453 : (Numerator - Bias) / Denominator - 1;
458template <
typename U,
typename V,
typename T = common_s
int<U, V>>
459constexpr T mod(U Numerator, V Denominator) {
460 assert(Denominator >= 1 &&
"Mod by non-positive number");
461 T Mod = Numerator % Denominator;
462 return Mod < 0 ?
Mod + Denominator :
Mod;
467template <
typename U,
typename V,
typename T = common_u
int<U, V>>
469 assert(Denominator &&
"Division by zero");
470 T Mod = Numerator % Denominator;
471 return (Numerator / Denominator) +
472 (
Mod > (
static_cast<T>(Denominator) - 1) / 2);
487template <
typename U,
typename V,
typename T = common_u
int<U, V>>
491 return CeilDiv *
Align;
498 return CeilDiv *
Align;
502template <
typename U,
typename V,
typename T = common_u
int<U, V>>
505 "Align must be a power of 2");
506 T NegAlign =
static_cast<T>(0) -
Align;
513 "Align must be a power of 2");
532template <
typename U,
typename V,
typename W,
533 typename T = common_uint<common_uint<U, V>, W>>
544template <auto Align,
typename V,
typename T = common_u
int<decltype(Align), V>>
546 static_assert(
Align != 0u,
"Align must be non-zero");
548 return CeilDiv *
Align;
554template <
typename U,
typename V,
typename W =
uint8_t,
555 typename T = common_uint<common_uint<U, V>, W>>
565 static_assert(
B <= 32,
"Bit width out of range.");
566 if constexpr (
B == 0)
568 return int32_t(
X << (32 -
B)) >> (32 -
B);
574 assert(
B <= 32 &&
"Bit width out of range.");
577 return int32_t(
X << (32 -
B)) >> (32 -
B);
583 static_assert(
B <= 64,
"Bit width out of range.");
584 if constexpr (
B == 0)
586 return int64_t(x << (64 -
B)) >> (64 -
B);
592 assert(
B <= 64 &&
"Bit width out of range.");
595 return int64_t(
X << (64 -
B)) >> (64 -
B);
600template <
typename U,
typename V,
typename T = common_u
int<U, V>>
602 return X >
Y ? (
X -
Y) : (
Y -
X);
609std::enable_if_t<std::is_unsigned_v<T>,
T>
612 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
615 Overflowed = (Z <
X || Z <
Y);
617 return std::numeric_limits<T>::max();
624template <
class T,
class... Ts>
627 bool Overflowed =
false;
630 return SaturatingAdd(std::numeric_limits<T>::max(),
T(1), Args...);
638std::enable_if_t<std::is_unsigned_v<T>,
T>
641 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
654 const T Max = std::numeric_limits<T>::max();
656 if (Log2Z < Log2Max) {
659 if (Log2Z > Log2Max) {
668 if (Z & ~(Max >> 1)) {
684std::enable_if_t<std::is_unsigned_v<T>,
T>
687 bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy;
703#if __has_builtin(__builtin_add_overflow)
704 return __builtin_add_overflow(
X,
Y, &Result);
707 using U = std::make_unsigned_t<T>;
708 const U UX =
static_cast<U
>(
X);
709 const U UY =
static_cast<U
>(
Y);
710 const U UResult = UX + UY;
713 Result =
static_cast<T>(UResult);
729#if __has_builtin(__builtin_sub_overflow)
730 return __builtin_sub_overflow(
X,
Y, &Result);
733 using U = std::make_unsigned_t<T>;
734 const U UX =
static_cast<U
>(
X);
735 const U UY =
static_cast<U
>(
Y);
736 const U UResult = UX - UY;
739 Result =
static_cast<T>(UResult);
755#if __has_builtin(__builtin_mul_overflow)
756 return __builtin_mul_overflow(
X,
Y, &Result);
759 using U = std::make_unsigned_t<T>;
760 const U UX =
X < 0 ? (0 -
static_cast<U
>(
X)) :
static_cast<U
>(
X);
761 const U UY =
Y < 0 ? (0 -
static_cast<U
>(
Y)) :
static_cast<U
>(
Y);
762 const U UResult = UX * UY;
765 const bool IsNegative = (
X < 0) ^ (
Y < 0);
766 Result = IsNegative ? (0 - UResult) : UResult;
769 if (UX == 0 || UY == 0)
776 return UX > (
static_cast<U
>(std::numeric_limits<T>::max()) + U(1)) / UY;
778 return UX > (
static_cast<U
>(std::numeric_limits<T>::max())) / UY;
784#if defined(__i386__) || defined(_M_IX86)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements the C++20 <bit> header.
LLVM Value Representation.
constexpr float inv_sqrtpif
constexpr double inv_sqrt2
constexpr double inv_sqrt3
constexpr double inv_sqrtpi
constexpr float inv_sqrt2f
constexpr float inv_sqrt3f
This is an optimization pass for GlobalISel generic memory operations.
std::common_type_t< std::make_unsigned_t< T >, std::make_unsigned_t< U > > common_uint
float stack_float_t
Type to force float point values onto the stack, so that x86 doesn't add hidden precision,...
@ Low
Lower the current thread's priority such that it does not affect foreground tasks significantly.
unsigned Log2_32_Ceil(uint32_t Value)
Return the ceil log base 2 of the specified value, 32 if the value is zero.
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...
int64_t maxIntN(int64_t N)
Gets the maximum value for a N-bit signed integer.
constexpr bool divideSignedWouldOverflow(U Numerator, V Denominator)
LLVM_ATTRIBUTE_ALWAYS_INLINE DynamicAPInt mod(const DynamicAPInt &LHS, const DynamicAPInt &RHS)
is always non-negative.
int popcount(T Value) noexcept
Count the number of set bits in a value.
constexpr size_t CTLog2()
Compile time Log2.
constexpr bool isInt(int64_t x)
Checks if an integer fits into the given bit width.
bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
constexpr size_t CTLog2< 1 >()
unsigned Log2_64_Ceil(uint64_t Value)
Return the ceil log base 2 of the specified value, 64 if the value is zero.
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...
constexpr T divideFloorSigned(U Numerator, V Denominator)
Returns the integer floor(Numerator / Denominator).
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.
constexpr bool isPowerOf2_64(uint64_t Value)
Return true if the argument is a power of two > 0 (64 bit edition.)
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...
unsigned Log2_64(uint64_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
uint64_t PowerOf2Ceil(uint64_t A)
Returns the power of two which is greater than or equal to the given value.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
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...
constexpr T MinAlign(U A, V B)
A and B are either alignments or offsets.
constexpr T divideNearest(U Numerator, V Denominator)
Returns (Numerator / Denominator) rounded by round-half-up.
constexpr bool has_single_bit(T Value) noexcept
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
int countl_zero(T Val)
Count number of 0's from the most significant bit to the least stopping at the first 1.
T maskLeadingZeros(unsigned N)
Create a bitmask with the N left-most bits set to 0, and all other bits set to 1.
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
T maskTrailingOnes(unsigned N)
Create a bitmask with the N right-most bits set to 1, and all other bits set to 0.
T maskTrailingZeros(unsigned N)
Create a bitmask with the N right-most bits set to 0, and all other bits set to 1.
constexpr uint32_t Hi_32(uint64_t Value)
Return the high 32 bits of a 64 bit value.
std::common_type_t< std::make_signed_t< T >, std::make_signed_t< U > > common_sint
constexpr T alignToPowerOf2(U Value, V Align)
Will overflow only if result is not representable in T.
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...
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.
constexpr bool isUInt(uint64_t x)
Checks if an unsigned integer fits into the given bit width.
constexpr T divideCeilSigned(U Numerator, V Denominator)
Returns the integer ceil(Numerator / Denominator).
constexpr uint32_t Lo_32(uint64_t Value)
Return the low 32 bits of a 64 bit value.
@ Mod
The access may modify the value stored in memory.
constexpr T divideCeil(U Numerator, V Denominator)
Returns the integer ceil(Numerator / Denominator).
const float huge_valf
Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
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.
bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
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.
int64_t minIntN(int64_t N)
Gets the minimum value for a N-bit signed integer.
constexpr bool isShiftedInt(int64_t x)
Checks if a signed integer is an N bit number shifted left by S.
constexpr int32_t SignExtend32(uint32_t X)
Sign-extend the number in the bottom B bits of X to a 32-bit integer.
T maskLeadingOnes(unsigned N)
Create a bitmask with the N left-most bits set to 1, and all other bits set to 0.
constexpr int64_t SignExtend64(uint64_t x)
Sign-extend the number in the bottom B bits of X to a 64-bit integer.
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 ...
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...
static const unsigned char BitReverseTable256[256]
Macro compressed bit reversal table for 256 bits.
T reverseBits(T Val)
Reverse the bits in Val.
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.
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.
constexpr bool isShiftedUInt(uint64_t x)
Checks if a unsigned integer is an N bit number shifted left by S.
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.
uint64_t maxUIntN(uint64_t N)
Gets the maximum value for a N-bit unsigned integer.
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
This struct is a compact representation of a valid (non-zero power of two) alignment.