diff options
Diffstat (limited to 'include/llvm/Support/MathExtras.h')
| -rw-r--r-- | include/llvm/Support/MathExtras.h | 378 |
1 files changed, 190 insertions, 188 deletions
diff --git a/include/llvm/Support/MathExtras.h b/include/llvm/Support/MathExtras.h index 6983636..e316616 100644 --- a/include/llvm/Support/MathExtras.h +++ b/include/llvm/Support/MathExtras.h @@ -24,6 +24,10 @@ #include <intrin.h> #endif +#ifdef __ANDROID_NDK__ +#include <android/api-level.h> +#endif + namespace llvm { /// \brief The behavior an operation has on an input of 0. enum ZeroBehavior { @@ -35,78 +39,66 @@ enum ZeroBehavior { ZB_Width }; -/// \brief Count number of 0's from the least significant bit to the most -/// stopping at the first 1. -/// -/// Only unsigned integral types are allowed. -/// -/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are -/// valid arguments. -template <typename T> -typename std::enable_if<std::numeric_limits<T>::is_integer && - !std::numeric_limits<T>::is_signed, std::size_t>::type -countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) { - (void)ZB; - - if (!Val) - return std::numeric_limits<T>::digits; - if (Val & 0x1) - return 0; - - // Bisection method. - std::size_t ZeroBits = 0; - T Shift = std::numeric_limits<T>::digits >> 1; - T Mask = std::numeric_limits<T>::max() >> Shift; - while (Shift) { - if ((Val & Mask) == 0) { - Val >>= Shift; - ZeroBits |= Shift; +namespace detail { +template <typename T, std::size_t SizeOfT> struct TrailingZerosCounter { + static std::size_t count(T Val, ZeroBehavior) { + if (!Val) + return std::numeric_limits<T>::digits; + if (Val & 0x1) + return 0; + + // Bisection method. + std::size_t ZeroBits = 0; + T Shift = std::numeric_limits<T>::digits >> 1; + T Mask = std::numeric_limits<T>::max() >> Shift; + while (Shift) { + if ((Val & Mask) == 0) { + Val >>= Shift; + ZeroBits |= Shift; + } + Shift >>= 1; + Mask >>= Shift; } - Shift >>= 1; - Mask >>= Shift; + return ZeroBits; } - return ZeroBits; -} - -// Disable signed. -template <typename T> -typename std::enable_if<std::numeric_limits<T>::is_integer && - std::numeric_limits<T>::is_signed, std::size_t>::type -countTrailingZeros(T, ZeroBehavior = ZB_Width) LLVM_DELETED_FUNCTION; +}; #if __GNUC__ >= 4 || _MSC_VER -template <> -inline std::size_t countTrailingZeros<uint32_t>(uint32_t Val, ZeroBehavior ZB) { - if (ZB != ZB_Undefined && Val == 0) - return 32; +template <typename T> struct TrailingZerosCounter<T, 4> { + static std::size_t count(T Val, ZeroBehavior ZB) { + if (ZB != ZB_Undefined && Val == 0) + return 32; #if __has_builtin(__builtin_ctz) || LLVM_GNUC_PREREQ(4, 0, 0) - return __builtin_ctz(Val); + return __builtin_ctz(Val); #elif _MSC_VER - unsigned long Index; - _BitScanForward(&Index, Val); - return Index; + unsigned long Index; + _BitScanForward(&Index, Val); + return Index; #endif -} + } +}; #if !defined(_MSC_VER) || defined(_M_X64) -template <> -inline std::size_t countTrailingZeros<uint64_t>(uint64_t Val, ZeroBehavior ZB) { - if (ZB != ZB_Undefined && Val == 0) - return 64; +template <typename T> struct TrailingZerosCounter<T, 8> { + static std::size_t count(T Val, ZeroBehavior ZB) { + if (ZB != ZB_Undefined && Val == 0) + return 64; #if __has_builtin(__builtin_ctzll) || LLVM_GNUC_PREREQ(4, 0, 0) - return __builtin_ctzll(Val); + return __builtin_ctzll(Val); #elif _MSC_VER - unsigned long Index; - _BitScanForward64(&Index, Val); - return Index; + unsigned long Index; + _BitScanForward64(&Index, Val); + return Index; #endif -} + } +}; #endif #endif +} // namespace detail -/// \brief Count number of 0's from the most significant bit to the least +/// \brief Count number of 0's from the least significant bit to the most /// stopping at the first 1. /// /// Only unsigned integral types are allowed. @@ -114,63 +106,81 @@ inline std::size_t countTrailingZeros<uint64_t>(uint64_t Val, ZeroBehavior ZB) { /// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are /// valid arguments. template <typename T> -typename std::enable_if<std::numeric_limits<T>::is_integer && - !std::numeric_limits<T>::is_signed, std::size_t>::type -countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) { - (void)ZB; - - if (!Val) - return std::numeric_limits<T>::digits; - - // Bisection method. - std::size_t ZeroBits = 0; - for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) { - T Tmp = Val >> Shift; - if (Tmp) - Val = Tmp; - else - ZeroBits |= Shift; +std::size_t countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) { + static_assert(std::numeric_limits<T>::is_integer && + !std::numeric_limits<T>::is_signed, + "Only unsigned integral types are allowed."); + return detail::TrailingZerosCounter<T, sizeof(T)>::count(Val, ZB); +} + +namespace detail { +template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter { + static std::size_t count(T Val, ZeroBehavior) { + if (!Val) + return std::numeric_limits<T>::digits; + + // Bisection method. + std::size_t ZeroBits = 0; + for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) { + T Tmp = Val >> Shift; + if (Tmp) + Val = Tmp; + else + ZeroBits |= Shift; + } + return ZeroBits; } - return ZeroBits; -} - -// Disable signed. -template <typename T> -typename std::enable_if<std::numeric_limits<T>::is_integer && - std::numeric_limits<T>::is_signed, std::size_t>::type -countLeadingZeros(T, ZeroBehavior = ZB_Width) LLVM_DELETED_FUNCTION; +}; #if __GNUC__ >= 4 || _MSC_VER -template <> -inline std::size_t countLeadingZeros<uint32_t>(uint32_t Val, ZeroBehavior ZB) { - if (ZB != ZB_Undefined && Val == 0) - return 32; +template <typename T> struct LeadingZerosCounter<T, 4> { + static std::size_t count(T Val, ZeroBehavior ZB) { + if (ZB != ZB_Undefined && Val == 0) + return 32; #if __has_builtin(__builtin_clz) || LLVM_GNUC_PREREQ(4, 0, 0) - return __builtin_clz(Val); + return __builtin_clz(Val); #elif _MSC_VER - unsigned long Index; - _BitScanReverse(&Index, Val); - return Index ^ 31; + unsigned long Index; + _BitScanReverse(&Index, Val); + return Index ^ 31; #endif -} + } +}; #if !defined(_MSC_VER) || defined(_M_X64) -template <> -inline std::size_t countLeadingZeros<uint64_t>(uint64_t Val, ZeroBehavior ZB) { - if (ZB != ZB_Undefined && Val == 0) - return 64; +template <typename T> struct LeadingZerosCounter<T, 8> { + static std::size_t count(T Val, ZeroBehavior ZB) { + if (ZB != ZB_Undefined && Val == 0) + return 64; #if __has_builtin(__builtin_clzll) || LLVM_GNUC_PREREQ(4, 0, 0) - return __builtin_clzll(Val); + return __builtin_clzll(Val); #elif _MSC_VER - unsigned long Index; - _BitScanReverse64(&Index, Val); - return Index ^ 63; + unsigned long Index; + _BitScanReverse64(&Index, Val); + return Index ^ 63; #endif -} + } +}; #endif #endif +} // namespace detail + +/// \brief Count number of 0's from the most significant bit to the least +/// stopping at the first 1. +/// +/// Only unsigned integral types are allowed. +/// +/// \param ZB the behavior on an input of 0. Only ZB_Width and ZB_Undefined are +/// valid arguments. +template <typename T> +std::size_t countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) { + static_assert(std::numeric_limits<T>::is_integer && + !std::numeric_limits<T>::is_signed, + "Only unsigned integral types are allowed."); + return detail::LeadingZerosCounter<T, sizeof(T)>::count(Val, ZB); +} /// \brief Get the index of the first set bit starting from the least /// significant bit. @@ -179,22 +189,13 @@ inline std::size_t countLeadingZeros<uint64_t>(uint64_t Val, ZeroBehavior ZB) { /// /// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are /// valid arguments. -template <typename T> -typename std::enable_if<std::numeric_limits<T>::is_integer && - !std::numeric_limits<T>::is_signed, T>::type -findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) { +template <typename T> T findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) { if (ZB == ZB_Max && Val == 0) return std::numeric_limits<T>::max(); return countTrailingZeros(Val, ZB_Undefined); } -// Disable signed. -template <typename T> -typename std::enable_if<std::numeric_limits<T>::is_integer && - std::numeric_limits<T>::is_signed, T>::type -findFirstSet(T, ZeroBehavior = ZB_Max) LLVM_DELETED_FUNCTION; - /// \brief Get the index of the last set bit starting from the least /// significant bit. /// @@ -202,10 +203,7 @@ findFirstSet(T, ZeroBehavior = ZB_Max) LLVM_DELETED_FUNCTION; /// /// \param ZB the behavior on an input of 0. Only ZB_Max and ZB_Undefined are /// valid arguments. -template <typename T> -typename std::enable_if<std::numeric_limits<T>::is_integer && - !std::numeric_limits<T>::is_signed, T>::type -findLastSet(T Val, ZeroBehavior ZB = ZB_Max) { +template <typename T> T findLastSet(T Val, ZeroBehavior ZB = ZB_Max) { if (ZB == ZB_Max && Val == 0) return std::numeric_limits<T>::max(); @@ -215,12 +213,6 @@ findLastSet(T Val, ZeroBehavior ZB = ZB_Max) { (std::numeric_limits<T>::digits - 1); } -// Disable signed. -template <typename T> -typename std::enable_if<std::numeric_limits<T>::is_integer && - std::numeric_limits<T>::is_signed, T>::type -findLastSet(T, ZeroBehavior = ZB_Max) LLVM_DELETED_FUNCTION; - /// \brief Macro compressed bit reversal table for 256 bits. /// /// http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable @@ -330,31 +322,31 @@ inline bool isIntN(unsigned N, int64_t x) { return N >= 64 || (-(INT64_C(1)<<(N-1)) <= x && x < (INT64_C(1)<<(N-1))); } -/// isMask_32 - This function returns true if the argument is a sequence of ones -/// starting at the least significant bit with the remainder zero (32 bit -/// version). Ex. isMask_32(0x0000FFFFU) == true. +/// isMask_32 - This function returns true if the argument is a non-empty +/// sequence of ones starting at the least significant bit with the remainder +/// zero (32 bit version). Ex. isMask_32(0x0000FFFFU) == true. inline bool isMask_32(uint32_t Value) { return Value && ((Value + 1) & Value) == 0; } -/// isMask_64 - This function returns true if the argument is a sequence of ones -/// starting at the least significant bit with the remainder zero (64 bit -/// version). +/// isMask_64 - This function returns true if the argument is a non-empty +/// sequence of ones starting at the least significant bit with the remainder +/// zero (64 bit version). inline bool isMask_64(uint64_t Value) { return Value && ((Value + 1) & Value) == 0; } /// isShiftedMask_32 - This function returns true if the argument contains a -/// sequence of ones with the remainder zero (32 bit version.) +/// non-empty sequence of ones with the remainder zero (32 bit version.) /// Ex. isShiftedMask_32(0x0000FF00U) == true. inline bool isShiftedMask_32(uint32_t Value) { - return isMask_32((Value - 1) | Value); + return Value && isMask_32((Value - 1) | Value); } /// isShiftedMask_64 - This function returns true if the argument contains a -/// sequence of ones with the remainder zero (64 bit version.) +/// non-empty sequence of ones with the remainder zero (64 bit version.) inline bool isShiftedMask_64(uint64_t Value) { - return isMask_64((Value - 1) | Value); + return Value && isMask_64((Value - 1) | Value); } /// isPowerOf2_32 - This function returns true if the argument is a power of @@ -387,61 +379,86 @@ inline uint64_t ByteSwap_64(uint64_t Value) { return sys::SwapByteOrder_64(Value); } -/// CountLeadingOnes_32 - this function performs the operation of -/// counting the number of ones from the most significant bit to the first zero -/// bit. Ex. CountLeadingOnes_32(0xFF0FFF00) == 8. -/// Returns 32 if the word is all ones. -inline unsigned CountLeadingOnes_32(uint32_t Value) { - return countLeadingZeros(~Value); -} - -/// CountLeadingOnes_64 - This function performs the operation -/// of counting the number of ones from the most significant bit to the first -/// zero bit (64 bit edition.) -/// Returns 64 if the word is all ones. -inline unsigned CountLeadingOnes_64(uint64_t Value) { - return countLeadingZeros(~Value); -} - -/// CountTrailingOnes_32 - this function performs the operation of -/// counting the number of ones from the least significant bit to the first zero -/// bit. Ex. CountTrailingOnes_32(0x00FF00FF) == 8. -/// Returns 32 if the word is all ones. -inline unsigned CountTrailingOnes_32(uint32_t Value) { - return countTrailingZeros(~Value); +/// \brief Count the number of ones from the most significant bit to the first +/// zero bit. +/// +/// Ex. CountLeadingOnes(0xFF0FFF00) == 8. +/// Only unsigned integral types are allowed. +/// +/// \param ZB the behavior on an input of all ones. Only ZB_Width and +/// ZB_Undefined are valid arguments. +template <typename T> +std::size_t countLeadingOnes(T Value, ZeroBehavior ZB = ZB_Width) { + static_assert(std::numeric_limits<T>::is_integer && + !std::numeric_limits<T>::is_signed, + "Only unsigned integral types are allowed."); + return countLeadingZeros(~Value, ZB); } -/// CountTrailingOnes_64 - This function performs the operation -/// of counting the number of ones from the least significant bit to the first -/// zero bit (64 bit edition.) -/// Returns 64 if the word is all ones. -inline unsigned CountTrailingOnes_64(uint64_t Value) { - return countTrailingZeros(~Value); -} +/// \brief Count the number of ones from the least significant bit to the first +/// zero bit. +/// +/// Ex. countTrailingOnes(0x00FF00FF) == 8. +/// Only unsigned integral types are allowed. +/// +/// \param ZB the behavior on an input of all ones. Only ZB_Width and +/// ZB_Undefined are valid arguments. +template <typename T> +std::size_t countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) { + static_assert(std::numeric_limits<T>::is_integer && + !std::numeric_limits<T>::is_signed, + "Only unsigned integral types are allowed."); + return countTrailingZeros(~Value, ZB); +} + +namespace detail { +template <typename T, std::size_t SizeOfT> struct PopulationCounter { + static unsigned count(T Value) { + // Generic version, forward to 32 bits. + static_assert(SizeOfT <= 4, "Not implemented!"); +#if __GNUC__ >= 4 + return __builtin_popcount(Value); +#else + uint32_t v = Value; + v = v - ((v >> 1) & 0x55555555); + v = (v & 0x33333333) + ((v >> 2) & 0x33333333); + return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; +#endif + } +}; -/// CountPopulation_32 - this function counts the number of set bits in a value. -/// Ex. CountPopulation(0xF000F000) = 8 -/// Returns 0 if the word is zero. -inline unsigned CountPopulation_32(uint32_t Value) { +template <typename T> struct PopulationCounter<T, 8> { + static unsigned count(T Value) { #if __GNUC__ >= 4 - return __builtin_popcount(Value); + return __builtin_popcountll(Value); #else - uint32_t v = Value - ((Value >> 1) & 0x55555555); - v = (v & 0x33333333) + ((v >> 2) & 0x33333333); - return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; + uint64_t v = Value; + v = v - ((v >> 1) & 0x5555555555555555ULL); + v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL); + v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL; + return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56); #endif + } +}; +} // namespace detail + +/// \brief Count the number of set bits in a value. +/// Ex. countPopulation(0xF000F000) = 8 +/// Returns 0 if the word is zero. +template <typename T> +inline unsigned countPopulation(T Value) { + static_assert(std::numeric_limits<T>::is_integer && + !std::numeric_limits<T>::is_signed, + "Only unsigned integral types are allowed."); + return detail::PopulationCounter<T, sizeof(T)>::count(Value); } -/// CountPopulation_64 - this function counts the number of set bits in a value, -/// (64 bit edition.) -inline unsigned CountPopulation_64(uint64_t Value) { -#if __GNUC__ >= 4 - return __builtin_popcountll(Value); +/// Log2 - This function returns the log base 2 of the specified value +inline double Log2(double Value) { +#if defined(__ANDROID_API__) && __ANDROID_API__ < 18 + return __builtin_log(Value) / __builtin_log(2.0); #else - uint64_t v = Value - ((Value >> 1) & 0x5555555555555555ULL); - v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL); - v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL; - return unsigned((uint64_t)(v * 0x0101010101010101ULL) >> 56); + return log2(Value); #endif } @@ -530,14 +547,6 @@ inline uint32_t FloatToBits(float Float) { return T.I; } -/// Platform-independent wrappers for the C99 isnan() function. -int IsNAN(float f); -int IsNAN(double d); - -/// Platform-independent wrappers for the C99 isinf() function. -int IsInf(float f); -int IsInf(double d); - /// MinAlign - A and B are either alignments or offsets. Return the minimum /// alignment that may be assumed after adding the two together. inline uint64_t MinAlign(uint64_t A, uint64_t B) { @@ -608,13 +617,6 @@ inline uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align) { return RoundUpToAlignment(Value, Align) - Value; } -/// abs64 - absolute value of a 64-bit int. Not all environments support -/// "abs" on whatever their name for the 64-bit int type is. The absolute -/// value of the largest negative number is undefined, as with "abs". -inline int64_t abs64(int64_t x) { - return (x < 0) ? -x : x; -} - /// SignExtend32 - Sign extend B-bit number x to 32-bit int. /// Usage int32_t r = SignExtend32<5>(x); template <unsigned B> inline int32_t SignExtend32(uint32_t x) { |
