X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FSupport%2FMathExtras.h;h=2cf7e0e5d0b3972053017ca426c8299480c7bb85;hb=00552e3875ee5f382db6c98286a241a7d0efe1b8;hp=cb3188c78f8940e7d708429aa894eaf84341ec94;hpb=9df41118765391f5025c8278ddc2024505e47fa5;p=oota-llvm.git diff --git a/include/llvm/Support/MathExtras.h b/include/llvm/Support/MathExtras.h index cb3188c78f8..2cf7e0e5d0b 100644 --- a/include/llvm/Support/MathExtras.h +++ b/include/llvm/Support/MathExtras.h @@ -24,6 +24,10 @@ #include #endif +#ifdef __ANDROID_NDK__ +#include +#endif + namespace llvm { /// \brief The behavior an operation has on an input of 0. enum ZeroBehavior { @@ -318,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 @@ -375,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); +/// \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 +std::size_t countLeadingOnes(T Value, ZeroBehavior ZB = ZB_Width) { + static_assert(std::numeric_limits::is_integer && + !std::numeric_limits::is_signed, + "Only unsigned integral types are allowed."); + return countLeadingZeros(~Value, ZB); } -/// 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 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 +std::size_t countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) { + static_assert(std::numeric_limits::is_integer && + !std::numeric_limits::is_signed, + "Only unsigned integral types are allowed."); + return countTrailingZeros(~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); -} +namespace detail { +template 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 struct PopulationCounter { + 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 +inline unsigned countPopulation(T Value) { + static_assert(std::numeric_limits::is_integer && + !std::numeric_limits::is_signed, + "Only unsigned integral types are allowed."); + return detail::PopulationCounter::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 } @@ -518,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) { @@ -541,7 +562,7 @@ inline uint64_t MinAlign(uint64_t A, uint64_t B) { /// /// Alignment should be a power of two. This method rounds up, so /// alignAddr(7, 4) == 8 and alignAddr(8, 4) == 8. -inline uintptr_t alignAddr(void *Addr, size_t Alignment) { +inline uintptr_t alignAddr(const void *Addr, size_t Alignment) { assert(Alignment && isPowerOf2_64((uint64_t)Alignment) && "Alignment is not a power of two!"); @@ -552,7 +573,7 @@ inline uintptr_t alignAddr(void *Addr, size_t Alignment) { /// \brief Returns the necessary adjustment for aligning \c Ptr to \c Alignment /// bytes, rounding up. -inline size_t alignmentAdjustment(void *Ptr, size_t Alignment) { +inline size_t alignmentAdjustment(const void *Ptr, size_t Alignment) { return alignAddr(Ptr, Alignment) - (uintptr_t)Ptr; } @@ -596,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 inline int32_t SignExtend32(uint32_t x) {