diff options
Diffstat (limited to 'include/llvm/Support/MathExtras.h')
-rw-r--r-- | include/llvm/Support/MathExtras.h | 187 |
1 files changed, 140 insertions, 47 deletions
diff --git a/include/llvm/Support/MathExtras.h b/include/llvm/Support/MathExtras.h index 249139e824b5..004a6f5f6eb8 100644 --- a/include/llvm/Support/MathExtras.h +++ b/include/llvm/Support/MathExtras.h @@ -39,6 +39,7 @@ unsigned char _BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask); #endif namespace llvm { + /// The behavior an operation has on an input of 0. enum ZeroBehavior { /// The returned value is undefined. @@ -49,6 +50,42 @@ enum ZeroBehavior { ZB_Width }; +/// Mathematical constants. +namespace numbers { +// TODO: Track C++20 std::numbers. +// TODO: Favor using the hexadecimal FP constants (requires C++17). +constexpr double e = 2.7182818284590452354, // (0x1.5bf0a8b145749P+1) https://oeis.org/A001113 + egamma = .57721566490153286061, // (0x1.2788cfc6fb619P-1) https://oeis.org/A001620 + ln2 = .69314718055994530942, // (0x1.62e42fefa39efP-1) https://oeis.org/A002162 + ln10 = 2.3025850929940456840, // (0x1.24bb1bbb55516P+1) https://oeis.org/A002392 + log2e = 1.4426950408889634074, // (0x1.71547652b82feP+0) + log10e = .43429448190325182765, // (0x1.bcb7b1526e50eP-2) + pi = 3.1415926535897932385, // (0x1.921fb54442d18P+1) https://oeis.org/A000796 + inv_pi = .31830988618379067154, // (0x1.45f306bc9c883P-2) https://oeis.org/A049541 + sqrtpi = 1.7724538509055160273, // (0x1.c5bf891b4ef6bP+0) https://oeis.org/A002161 + inv_sqrtpi = .56418958354775628695, // (0x1.20dd750429b6dP-1) https://oeis.org/A087197 + sqrt2 = 1.4142135623730950488, // (0x1.6a09e667f3bcdP+0) https://oeis.org/A00219 + inv_sqrt2 = .70710678118654752440, // (0x1.6a09e667f3bcdP-1) + sqrt3 = 1.7320508075688772935, // (0x1.bb67ae8584caaP+0) https://oeis.org/A002194 + inv_sqrt3 = .57735026918962576451, // (0x1.279a74590331cP-1) + phi = 1.6180339887498948482; // (0x1.9e3779b97f4a8P+0) https://oeis.org/A001622 +constexpr float ef = 2.71828183F, // (0x1.5bf0a8P+1) https://oeis.org/A001113 + egammaf = .577215665F, // (0x1.2788d0P-1) https://oeis.org/A001620 + ln2f = .693147181F, // (0x1.62e430P-1) https://oeis.org/A002162 + ln10f = 2.30258509F, // (0x1.26bb1cP+1) https://oeis.org/A002392 + log2ef = 1.44269504F, // (0x1.715476P+0) + log10ef = .434294482F, // (0x1.bcb7b2P-2) + pif = 3.14159265F, // (0x1.921fb6P+1) https://oeis.org/A000796 + inv_pif = .318309886F, // (0x1.45f306P-2) https://oeis.org/A049541 + sqrtpif = 1.77245385F, // (0x1.c5bf8aP+0) https://oeis.org/A002161 + inv_sqrtpif = .564189584F, // (0x1.20dd76P-1) https://oeis.org/A087197 + sqrt2f = 1.41421356F, // (0x1.6a09e6P+0) https://oeis.org/A002193 + inv_sqrt2f = .707106781F, // (0x1.6a09e6P-1) + sqrt3f = 1.73205081F, // (0x1.bb67aeP+0) https://oeis.org/A002194 + inv_sqrt3f = .577350269F, // (0x1.279a74P-1) + phif = 1.61803399F; // (0x1.9e377aP+0) https://oeis.org/A001622 +} // namespace numbers + namespace detail { template <typename T, std::size_t SizeOfT> struct TrailingZerosCounter { static unsigned count(T Val, ZeroBehavior) { @@ -73,13 +110,13 @@ template <typename T, std::size_t SizeOfT> struct TrailingZerosCounter { } }; -#if __GNUC__ >= 4 || defined(_MSC_VER) +#if defined(__GNUC__) || defined(_MSC_VER) template <typename T> struct TrailingZerosCounter<T, 4> { static unsigned count(T Val, ZeroBehavior ZB) { if (ZB != ZB_Undefined && Val == 0) return 32; -#if __has_builtin(__builtin_ctz) || LLVM_GNUC_PREREQ(4, 0, 0) +#if __has_builtin(__builtin_ctz) || defined(__GNUC__) return __builtin_ctz(Val); #elif defined(_MSC_VER) unsigned long Index; @@ -95,7 +132,7 @@ template <typename T> struct TrailingZerosCounter<T, 8> { if (ZB != ZB_Undefined && Val == 0) return 64; -#if __has_builtin(__builtin_ctzll) || LLVM_GNUC_PREREQ(4, 0, 0) +#if __has_builtin(__builtin_ctzll) || defined(__GNUC__) return __builtin_ctzll(Val); #elif defined(_MSC_VER) unsigned long Index; @@ -142,13 +179,13 @@ template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter { } }; -#if __GNUC__ >= 4 || defined(_MSC_VER) +#if defined(__GNUC__) || defined(_MSC_VER) template <typename T> struct LeadingZerosCounter<T, 4> { static unsigned count(T Val, ZeroBehavior ZB) { if (ZB != ZB_Undefined && Val == 0) return 32; -#if __has_builtin(__builtin_clz) || LLVM_GNUC_PREREQ(4, 0, 0) +#if __has_builtin(__builtin_clz) || defined(__GNUC__) return __builtin_clz(Val); #elif defined(_MSC_VER) unsigned long Index; @@ -164,7 +201,7 @@ template <typename T> struct LeadingZerosCounter<T, 8> { if (ZB != ZB_Undefined && Val == 0) return 64; -#if __has_builtin(__builtin_clzll) || LLVM_GNUC_PREREQ(4, 0, 0) +#if __has_builtin(__builtin_clzll) || defined(__GNUC__) return __builtin_clzll(Val); #elif defined(_MSC_VER) unsigned long Index; @@ -486,7 +523,7 @@ 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 +#if defined(__GNUC__) return __builtin_popcount(Value); #else uint32_t v = Value; @@ -499,7 +536,7 @@ template <typename T, std::size_t SizeOfT> struct PopulationCounter { template <typename T> struct PopulationCounter<T, 8> { static unsigned count(T Value) { -#if __GNUC__ >= 4 +#if defined(__GNUC__) return __builtin_popcountll(Value); #else uint64_t v = Value; @@ -523,6 +560,16 @@ inline unsigned countPopulation(T Value) { return detail::PopulationCounter<T, sizeof(T)>::count(Value); } +/// Compile time Log2. +/// Valid only for positive powers of two. +template <size_t kValue> constexpr inline size_t CTLog2() { + static_assert(kValue > 0 && llvm::isPowerOf2_64(kValue), + "Value is not a valid power of 2"); + return 1 + CTLog2<kValue / 2>(); +} + +template <> constexpr inline size_t CTLog2<1>() { return 0; } + /// Return the log base 2 of the specified value. inline double Log2(double Value) { #if defined(__ANDROID_API__) && __ANDROID_API__ < 18 @@ -620,25 +667,6 @@ constexpr inline uint64_t MinAlign(uint64_t A, uint64_t B) { return (A | B) & (1 + ~(A | B)); } -/// Aligns \c Addr to \c Alignment bytes, rounding up. -/// -/// 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(const void *Addr, size_t Alignment) { - assert(Alignment && isPowerOf2_64((uint64_t)Alignment) && - "Alignment is not a power of two!"); - - assert((uintptr_t)Addr + Alignment - 1 >= (uintptr_t)Addr); - - return (((uintptr_t)Addr + Alignment - 1) & ~(uintptr_t)(Alignment - 1)); -} - -/// Returns the necessary adjustment for aligning \c Ptr to \c Alignment -/// bytes, rounding up. -inline size_t alignmentAdjustment(const void *Ptr, size_t Alignment) { - return alignAddr(Ptr, Alignment) - (uintptr_t)Ptr; -} - /// Returns the next power of two (in 64-bits) that is strictly greater than A. /// Returns zero on overflow. inline uint64_t NextPowerOf2(uint64_t A) { @@ -704,19 +732,6 @@ inline uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator) { return alignTo(Numerator, Denominator) / Denominator; } -/// \c alignTo for contexts where a constant expression is required. -/// \sa alignTo -/// -/// \todo FIXME: remove when \c constexpr becomes really \c constexpr -template <uint64_t Align> -struct AlignTo { - static_assert(Align != 0u, "Align must be non-zero"); - template <uint64_t Value> - struct from_value { - static const uint64_t value = (Value + Align - 1) / Align * Align; - }; -}; - /// Returns the largest uint64_t less than or equal to \p Value and is /// \p Skew mod \p Align. \p Align must be non-zero inline uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew = 0) { @@ -725,13 +740,6 @@ inline uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew = 0) { return (Value - Skew) / Align * Align + Skew; } -/// Returns the offset to the next integer (mod 2**64) that is greater than -/// or equal to \p Value and is a multiple of \p Align. \p Align must be -/// non-zero. -inline uint64_t OffsetToAlignment(uint64_t Value, uint64_t Align) { - return alignTo(Value, Align) - Value; -} - /// Sign-extend the number in the bottom B bits of X to a 32-bit integer. /// Requires 0 < B <= 32. template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) { @@ -853,6 +861,91 @@ SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed = nullptr) { /// Use this rather than HUGE_VALF; the latter causes warnings on MSVC. extern const float huge_valf; + + +/// Add two signed integers, computing the two's complement truncated result, +/// returning true if overflow occured. +template <typename T> +typename std::enable_if<std::is_signed<T>::value, T>::type +AddOverflow(T X, T Y, T &Result) { +#if __has_builtin(__builtin_add_overflow) + return __builtin_add_overflow(X, Y, &Result); +#else + // Perform the unsigned addition. + using U = typename std::make_unsigned<T>::type; + const U UX = static_cast<U>(X); + const U UY = static_cast<U>(Y); + const U UResult = UX + UY; + + // Convert to signed. + Result = static_cast<T>(UResult); + + // Adding two positive numbers should result in a positive number. + if (X > 0 && Y > 0) + return Result <= 0; + // Adding two negatives should result in a negative number. + if (X < 0 && Y < 0) + return Result >= 0; + return false; +#endif +} + +/// Subtract two signed integers, computing the two's complement truncated +/// result, returning true if an overflow ocurred. +template <typename T> +typename std::enable_if<std::is_signed<T>::value, T>::type +SubOverflow(T X, T Y, T &Result) { +#if __has_builtin(__builtin_sub_overflow) + return __builtin_sub_overflow(X, Y, &Result); +#else + // Perform the unsigned addition. + using U = typename std::make_unsigned<T>::type; + const U UX = static_cast<U>(X); + const U UY = static_cast<U>(Y); + const U UResult = UX - UY; + + // Convert to signed. + Result = static_cast<T>(UResult); + + // Subtracting a positive number from a negative results in a negative number. + if (X <= 0 && Y > 0) + return Result >= 0; + // Subtracting a negative number from a positive results in a positive number. + if (X >= 0 && Y < 0) + return Result <= 0; + return false; +#endif +} + + +/// Multiply two signed integers, computing the two's complement truncated +/// result, returning true if an overflow ocurred. +template <typename T> +typename std::enable_if<std::is_signed<T>::value, T>::type +MulOverflow(T X, T Y, T &Result) { + // Perform the unsigned multiplication on absolute values. + using U = typename std::make_unsigned<T>::type; + const U UX = X < 0 ? (0 - static_cast<U>(X)) : static_cast<U>(X); + const U UY = Y < 0 ? (0 - static_cast<U>(Y)) : static_cast<U>(Y); + const U UResult = UX * UY; + + // Convert to signed. + const bool IsNegative = (X < 0) ^ (Y < 0); + Result = IsNegative ? (0 - UResult) : UResult; + + // If any of the args was 0, result is 0 and no overflow occurs. + if (UX == 0 || UY == 0) + return false; + + // UX and UY are in [1, 2^n], where n is the number of digits. + // Check how the max allowed absolute value (2^n for negative, 2^(n-1) for + // positive) divided by an argument compares to the other. + if (IsNegative) + return UX > (static_cast<U>(std::numeric_limits<T>::max()) + U(1)) / UY; + else + return UX > (static_cast<U>(std::numeric_limits<T>::max())) / UY; +} + } // End llvm namespace #endif |