Go to the documentation of this file.
13 #ifndef LLVM_SUPPORT_MATHEXTRAS_H
14 #define LLVM_SUPPORT_MATHEXTRAS_H
23 #include <type_traits>
25 #ifdef __ANDROID_NDK__
26 #include <android/api-level.h>
34 unsigned char _BitScanForward(
unsigned long *_Index,
unsigned long _Mask);
35 unsigned char _BitScanForward64(
unsigned long *_Index,
unsigned __int64 _Mask);
36 unsigned char _BitScanReverse(
unsigned long *_Index,
unsigned long _Mask);
37 unsigned char _BitScanReverse64(
unsigned long *_Index,
unsigned __int64 _Mask);
57 constexpr
double e = 2.7182818284590452354,
59 ln2 = .69314718055994530942,
60 ln10 = 2.3025850929940456840,
63 pi = 3.1415926535897932385,
71 phi = 1.6180339887498948482;
72 constexpr
float ef = 2.71828183F,
93 return std::numeric_limits<T>::digits;
98 unsigned ZeroBits = 0;
99 T Shift = std::numeric_limits<T>::digits >> 1;
102 if ((Val &
Mask) == 0) {
113 #if defined(__GNUC__) || defined(_MSC_VER)
114 template <
typename T>
struct TrailingZerosCounter<
T, 4> {
119 #if __has_builtin(__builtin_ctz) || defined(__GNUC__)
120 return __builtin_ctz(Val);
121 #elif defined(_MSC_VER)
123 _BitScanForward(&
Index, Val);
129 #if !defined(_MSC_VER) || defined(_M_X64)
130 template <
typename T>
struct TrailingZerosCounter<
T, 8> {
135 #if __has_builtin(__builtin_ctzll) || defined(__GNUC__)
136 return __builtin_ctzll(Val);
137 #elif defined(_MSC_VER)
139 _BitScanForward64(&Index, Val);
155 template <
typename T>
157 static_assert(std::numeric_limits<T>::is_integer &&
158 !std::numeric_limits<T>::is_signed,
159 "Only unsigned integral types are allowed.");
167 return std::numeric_limits<T>::digits;
170 unsigned ZeroBits = 0;
182 #if defined(__GNUC__) || defined(_MSC_VER)
183 template <
typename T>
struct LeadingZerosCounter<
T, 4> {
188 #if __has_builtin(__builtin_clz) || defined(__GNUC__)
189 return __builtin_clz(Val);
190 #elif defined(_MSC_VER)
192 _BitScanReverse(&
Index, Val);
198 #if !defined(_MSC_VER) || defined(_M_X64)
199 template <
typename T>
struct LeadingZerosCounter<
T, 8> {
204 #if __has_builtin(__builtin_clzll) || defined(__GNUC__)
205 return __builtin_clzll(Val);
206 #elif defined(_MSC_VER)
208 _BitScanReverse64(&Index, Val);
224 template <
typename T>
226 static_assert(std::numeric_limits<T>::is_integer &&
227 !std::numeric_limits<T>::is_signed,
228 "Only unsigned integral types are allowed.");
240 if (ZB ==
ZB_Max && Val == 0)
249 static_assert(std::is_unsigned<T>::value,
"Invalid type!");
250 const unsigned Bits = CHAR_BIT *
sizeof(
T);
252 return N == 0 ? 0 : (
T(-1) >> (
Bits -
N));
258 return ~maskTrailingOnes<T>(CHAR_BIT *
sizeof(
T) -
N);
264 return maskLeadingOnes<T>(CHAR_BIT *
sizeof(
T) -
N);
270 return maskTrailingOnes<T>(CHAR_BIT *
sizeof(
T) -
N);
281 if (ZB ==
ZB_Max && Val == 0)
287 (std::numeric_limits<T>::digits - 1);
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)
304 template <
typename T>
306 unsigned char in[
sizeof(Val)];
307 unsigned char out[
sizeof(Val)];
309 for (
unsigned i = 0;
i <
sizeof(Val); ++
i)
315 #if __has_builtin(__builtin_bitreverse8)
317 inline uint8_t reverseBits<uint8_t>(uint8_t Val) {
318 return __builtin_bitreverse8(Val);
322 #if __has_builtin(__builtin_bitreverse16)
325 return __builtin_bitreverse16(Val);
329 #if __has_builtin(__builtin_bitreverse32)
332 return __builtin_bitreverse32(Val);
336 #if __has_builtin(__builtin_bitreverse64)
339 return __builtin_bitreverse64(Val);
363 template <
unsigned N> constexpr
inline bool isInt(int64_t
x) {
364 return N >= 64 || (-(INT64_C(1)<<(
N-1)) <=
x &&
x < (INT64_C(1)<<(
N-1)));
368 return static_cast<int8_t
>(
x) ==
x;
371 return static_cast<int16_t
>(
x) ==
x;
374 return static_cast<int32_t
>(
x) ==
x;
378 template <
unsigned N,
unsigned S>
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) <<
S) == 0);
394 template <
unsigned N>
396 static_assert(
N > 0,
"isUInt<0> doesn't make sense");
397 return X < (UINT64_C(1) << (
N));
399 template <
unsigned N>
400 constexpr
inline std::enable_if_t<N >= 64,
bool>
isUInt(
uint64_t) {
406 return static_cast<uint8_t
>(
x) ==
x;
416 template <
unsigned N,
unsigned S>
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.");
424 return isUInt<N + S>(
x) && (
x % (UINT64_C(1) <<
S) == 0);
429 assert(
N > 0 &&
N <= 64 &&
"integer width out of range");
440 assert(
N > 0 &&
N <= 64 &&
"integer width out of range");
442 return UINT64_C(1) + ~(UINT64_C(1) << (
N - 1));
447 assert(
N > 0 &&
N <= 64 &&
"integer width out of range");
451 return (UINT64_C(1) << (
N - 1)) - 1;
508 template <
typename T>
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);
524 template <
typename T>
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);
536 static_assert(SizeOfT <= 4,
"Not implemented!");
537 #if defined(__GNUC__)
538 return __builtin_popcount(
Value);
541 v = v - ((v >> 1) & 0x55555555);
542 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
543 return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
550 #if defined(__GNUC__)
551 return __builtin_popcountll(
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);
566 template <
typename T>
568 static_assert(std::numeric_limits<T>::is_integer &&
569 !std::numeric_limits<T>::is_signed,
570 "Only unsigned integral types are allowed.");
603 template <
size_t kValue> constexpr
inline size_t CTLog2() {
605 "Value is not a valid power of 2");
606 return 1 +
CTLog2<kValue / 2>();
609 template <> constexpr
inline size_t CTLog2<1>() {
return 0; }
613 #if defined(__ANDROID_API__) && __ANDROID_API__ < 18
614 return __builtin_log(
Value) / __builtin_log(2.0);
647 template <
typename T>
658 return greatestCommonDivisor<uint64_t>(A,
B);
664 static_assert(
sizeof(
uint64_t) ==
sizeof(
double),
"Unexpected type sizes");
672 static_assert(
sizeof(
uint32_t) ==
sizeof(
float),
"Unexpected type sizes");
682 static_assert(
sizeof(
uint64_t) ==
sizeof(
double),
"Unexpected type sizes");
692 static_assert(
sizeof(
uint32_t) ==
sizeof(
float),
"Unexpected type sizes");
705 return (A |
B) & (1 + ~(A |
B));
771 static_assert(
Align != 0u,
"Align must be non-zero");
777 return alignTo(Numerator, Denominator) / Denominator;
782 return (Numerator + (Denominator / 2)) / Denominator;
796 static_assert(
B > 0,
"Bit width can't be 0.");
797 static_assert(
B <= 32,
"Bit width out of range.");
798 return int32_t(
X << (32 -
B)) >> (32 -
B);
804 assert(
B > 0 &&
"Bit width can't be 0.");
805 assert(
B <= 32 &&
"Bit width out of range.");
806 return int32_t(
X << (32 -
B)) >> (32 -
B);
812 static_assert(
B > 0,
"Bit width can't be 0.");
813 static_assert(
B <= 64,
"Bit width out of range.");
814 return int64_t(
x << (64 -
B)) >> (64 -
B);
820 assert(
B > 0 &&
"Bit width can't be 0.");
821 assert(
B <= 64 &&
"Bit width out of range.");
822 return int64_t(
X << (64 -
B)) >> (64 -
B);
827 template <
typename T>
829 return X >
Y ? (
X -
Y) : (
Y -
X);
835 template <
typename T>
836 std::enable_if_t<std::is_unsigned<T>::value,
T>
839 bool &Overflowed = ResultOverflowed ? *ResultOverflowed :
Dummy;
842 Overflowed = (Z <
X || Z <
Y);
852 template <
typename T>
853 std::enable_if_t<std::is_unsigned<T>::value,
T>
856 bool &Overflowed = ResultOverflowed ? *ResultOverflowed :
Dummy;
871 if (Log2Z < Log2Max) {
874 if (Log2Z > Log2Max) {
883 if (Z & ~(Max >> 1)) {
898 template <
typename T>
899 std::enable_if_t<std::is_unsigned<T>::value,
T>
902 bool &Overflowed = ResultOverflowed ? *ResultOverflowed :
Dummy;
917 template <
typename T>
919 #if __has_builtin(__builtin_add_overflow)
920 return __builtin_add_overflow(
X,
Y, &Result);
923 using U = std::make_unsigned_t<T>;
924 const U UX =
static_cast<U
>(
X);
925 const U UY =
static_cast<U
>(
Y);
926 const U UResult = UX + UY;
929 Result =
static_cast<T>(UResult);
943 template <
typename T>
945 #if __has_builtin(__builtin_sub_overflow)
946 return __builtin_sub_overflow(
X,
Y, &Result);
949 using U = std::make_unsigned_t<T>;
950 const U UX =
static_cast<U
>(
X);
951 const U UY =
static_cast<U
>(
Y);
952 const U UResult = UX - UY;
955 Result =
static_cast<T>(UResult);
969 template <
typename T>
972 using U = std::make_unsigned_t<T>;
973 const U UX =
X < 0 ? (0 -
static_cast<U
>(
X)) :
static_cast<U
>(
X);
974 const U UY =
Y < 0 ? (0 -
static_cast<U
>(
Y)) :
static_cast<U
>(
Y);
975 const U UResult = UX * UY;
978 const bool IsNegative = (
X < 0) ^ (
Y < 0);
979 Result = IsNegative ? (0 - UResult) : UResult;
982 if (UX == 0 || UY == 0)
std::enable_if_t< std::is_unsigned< T >::value, T > SaturatingMultiply(T X, T Y, bool *ResultOverflowed=nullptr)
Multiply two unsigned integers, X and Y, of type T.
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
T findFirstSet(T Val, ZeroBehavior ZB=ZB_Max)
Get the index of the first set bit starting from the least significant bit.
constexpr size_t CTLog2< 1 >()
This is an optimization pass for GlobalISel generic memory operations.
static unsigned count(T Val, ZeroBehavior)
std::enable_if_t< std::is_unsigned< T >::value, T > SaturatingAdd(T X, T Y, bool *ResultOverflowed=nullptr)
Add two unsigned integers, X and Y, of type T.
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.
T reverseBits(T Val)
Reverse the bits in Val.
static unsigned count(T Val, ZeroBehavior)
T greatestCommonDivisor(T A, T B)
Return the greatest common divisor of the values using Euclid's algorithm.
constexpr size_t CTLog2()
Compile time Log2.
const float huge_valf
Use this rather than HUGE_VALF; the latter causes warnings on MSVC.
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...
uint32_t FloatToBits(float Float)
This function takes a float and returns the bit equivalent 32-bit integer.
int64_t maxIntN(int64_t N)
Gets the maximum value for a N-bit signed integer.
uint64_t GreatestCommonDivisor64(uint64_t A, uint64_t B)
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
uint64_t PowerOf2Ceil(uint64_t A)
Returns the power of two which is greater than or equal to the given value.
@ ZB_Width
The returned value is numeric_limits<T>::digits.
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
unsigned countLeadingOnes(T Value, ZeroBehavior ZB=ZB_Width)
Count the number of ones from the most significant bit to the first zero bit.
constexpr bool isInt(int64_t x)
Checks if an integer fits into the given bit width.
constexpr uint32_t Lo_32(uint64_t Value)
Return the low 32 bits of a 64 bit value.
@ ZB_Undefined
The returned value is undefined.
static unsigned count(T Value)
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
constexpr uint64_t MinAlign(uint64_t A, uint64_t B)
A and B are either alignments or offsets.
unsigned Log2_64(uint64_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
constexpr double inv_sqrt2
uint64_t PowerOf2Floor(uint64_t A)
Returns the power of two which is less than or equal to the given value.
unsigned Log2(Align A)
Returns the log2 of the alignment.
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...
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
uint64_t DoubleToBits(double Double)
This function takes a double and returns the bit equivalent 64-bit integer.
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew=0)
Returns the largest uint64_t less than or equal to Value and is Skew mod Align.
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
The object format emitted by the WebAssembly backed is documented in
@ Low
Lower the current thread's priority such that it does not affect foreground tasks significantly.
std::enable_if_t< std::is_signed< T >::value, T > AddOverflow(T X, T Y, T &Result)
Add two signed integers, computing the two's complement truncated result, returning true if overflow ...
constexpr float inv_sqrt3f
This struct is a compact representation of a valid (non-zero power of two) alignment.
constexpr float inv_sqrt2f
bool isIntN(unsigned N, int64_t x)
Checks if an signed integer fits into the given (dynamic) bit width.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
unsigned Log2_32_Ceil(uint32_t Value)
Return the ceil log base 2 of the specified value, 32 if the value is zero.
constexpr uint32_t Hi_32(uint64_t Value)
Return the high 32 bits of a 64 bit value.
constexpr bool isInt< 8 >(int64_t x)
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.
static unsigned count(T Value)
constexpr int32_t SignExtend32(uint32_t X)
Sign-extend the number in the bottom B bits of X to a 32-bit integer.
uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator)
Returns the integer ceil(Numerator / Denominator).
unsigned countPopulation(T Value)
Count the number of set bits in a value.
constexpr bool isInt< 32 >(int64_t x)
int64_t minIntN(int64_t N)
Gets the minimum value for a N-bit signed integer.
constexpr bool isUInt< 16 >(uint64_t x)
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
constexpr double inv_sqrt3
@ ZB_Max
The returned value is numeric_limits<T>::max()
std::enable_if_t< std::is_unsigned< T >::value, 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.
unsigned countTrailingOnes(T Value, ZeroBehavior ZB=ZB_Width)
Count the number of ones from the least significant bit to the first zero bit.
T maskLeadingZeros(unsigned N)
Create a bitmask with the N left-most bits set to 0, and all other bits set to 1.
unsigned Log2_64_Ceil(uint64_t Value)
Return the ceil log base 2 of the specified value, 64 if the value is zero.
SSE has instructions for doing operations on complex numbers
constexpr bool isUInt< 32 >(uint64_t x)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
constexpr bool isUInt< 8 >(uint64_t x)
<%struct.s * > cast struct s *S to sbyte *< sbyte * > sbyte uint cast struct s *agg result to sbyte *< sbyte * > sbyte uint cast struct s *memtmp to sbyte *< sbyte * > sbyte uint ret void llc ends up issuing two memcpy or custom lower memcpy(of small size) to be ldmia/stmia. I think option 2 is better but the current register allocator cannot allocate a chunk of registers at a time. A feasible temporary solution is to use specific physical registers at the lowering time for small(<
constexpr bool isShiftedUInt(uint64_t x)
Checks if a unsigned integer is an N bit number shifted left by S.
T findLastSet(T Val, ZeroBehavior ZB=ZB_Max)
Get the index of the last set bit starting from the least significant bit.
constexpr double inv_sqrtpi
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...
unsigned countTrailingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Count number of 0's from the least significant bit to the most stopping at the first 1.
static const unsigned char BitReverseTable256[256]
Macro compressed bit reversal table for 256 bits.
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
float BitsToFloat(uint32_t Bits)
This function takes a 32-bit integer and returns the bit equivalent float.
constexpr int64_t SignExtend64(uint64_t x)
Sign-extend the number in the bottom B bits of X to a 64-bit integer.
ZeroBehavior
The behavior an operation has on an input of 0.
constexpr bool isInt< 16 >(int64_t x)
constexpr float inv_sqrtpif
T maskLeadingOnes(unsigned N)
Create a bitmask with the N left-most bits set to 1, and all other bits set to 0.
std::enable_if_t< std::is_signed< T >::value, T > MulOverflow(T X, T Y, T &Result)
Multiply two signed integers, computing the two's complement truncated result, returning true if an o...
constexpr bool isShiftedInt(int64_t x)
Checks if a signed integer is an N bit number shifted left by S.
static double log2(double V)
unsigned countLeadingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Count number of 0's from the most significant bit to the least stopping at the first 1.
std::enable_if_t< std::is_signed< T >::value, T > SubOverflow(T X, T Y, T &Result)
Subtract two signed integers, computing the two's complement truncated result, returning true if an o...
double BitsToDouble(uint64_t Bits)
This function takes a 64-bit integer and returns the bit equivalent double.
uint64_t maxUIntN(uint64_t N)
Gets the maximum value for a N-bit unsigned integer.
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...
constexpr std::enable_if_t<(N< 64), bool > isUInt(uint64_t X)
Checks if an unsigned integer fits into the given bit width.
constexpr bool isPowerOf2_64(uint64_t Value)
Return true if the argument is a power of two > 0 (64 bit edition.)
uint64_t divideNearest(uint64_t Numerator, uint64_t Denominator)
Returns the integer nearest(Numerator / Denominator).
LLVM Value Representation.
std::enable_if_t< std::is_unsigned< T >::value, T > AbsoluteDifference(T X, T Y)
Subtract two unsigned integers, X and Y, of type T and return the absolute value of the result.