From 9df41118765391f5025c8278ddc2024505e47fa5 Mon Sep 17 00:00:00 2001 From: Benjamin Kramer Date: Thu, 12 Feb 2015 13:47:29 +0000 Subject: [PATCH] MathExtras: Parametrize count(Trailing|Leading)Zeros on the type size. Otherwise we will always select the generic version for e.g. unsigned long if uint64_t is typedef'd to 'unsigned long long'. Also remove enable_if hacks in favor of static_assert. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@228921 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/MathExtras.h | 222 ++++++++++++++++++-------------------- 1 file changed, 105 insertions(+), 117 deletions(-) diff --git a/include/llvm/Support/MathExtras.h b/include/llvm/Support/MathExtras.h index 698363614ac..cb3188c78f8 100644 --- a/include/llvm/Support/MathExtras.h +++ b/include/llvm/Support/MathExtras.h @@ -35,78 +35,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 std::enable_if::is_integer && - !std::numeric_limits::is_signed, std::size_t>::type -countTrailingZeros(T Val, ZeroBehavior ZB = ZB_Width) { - (void)ZB; - - if (!Val) - return std::numeric_limits::digits; - if (Val & 0x1) - return 0; - - // Bisection method. - std::size_t ZeroBits = 0; - T Shift = std::numeric_limits::digits >> 1; - T Mask = std::numeric_limits::max() >> Shift; - while (Shift) { - if ((Val & Mask) == 0) { - Val >>= Shift; - ZeroBits |= Shift; +namespace detail { +template struct TrailingZerosCounter { + static std::size_t count(T Val, ZeroBehavior) { + if (!Val) + return std::numeric_limits::digits; + if (Val & 0x1) + return 0; + + // Bisection method. + std::size_t ZeroBits = 0; + T Shift = std::numeric_limits::digits >> 1; + T Mask = std::numeric_limits::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 std::enable_if::is_integer && - std::numeric_limits::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 Val, ZeroBehavior ZB) { - if (ZB != ZB_Undefined && Val == 0) - return 32; +template struct TrailingZerosCounter { + 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 Val, ZeroBehavior ZB) { - if (ZB != ZB_Undefined && Val == 0) - return 64; +template struct TrailingZerosCounter { + 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 +102,81 @@ inline std::size_t countTrailingZeros(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 std::enable_if::is_integer && - !std::numeric_limits::is_signed, std::size_t>::type -countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) { - (void)ZB; - - if (!Val) - return std::numeric_limits::digits; - - // Bisection method. - std::size_t ZeroBits = 0; - for (T Shift = std::numeric_limits::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::is_integer && + !std::numeric_limits::is_signed, + "Only unsigned integral types are allowed."); + return detail::TrailingZerosCounter::count(Val, ZB); +} + +namespace detail { +template struct LeadingZerosCounter { + static std::size_t count(T Val, ZeroBehavior) { + if (!Val) + return std::numeric_limits::digits; + + // Bisection method. + std::size_t ZeroBits = 0; + for (T Shift = std::numeric_limits::digits >> 1; Shift; Shift >>= 1) { + T Tmp = Val >> Shift; + if (Tmp) + Val = Tmp; + else + ZeroBits |= Shift; + } + return ZeroBits; } - return ZeroBits; -} - -// Disable signed. -template -typename std::enable_if::is_integer && - std::numeric_limits::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 Val, ZeroBehavior ZB) { - if (ZB != ZB_Undefined && Val == 0) - return 32; +template struct LeadingZerosCounter { + 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 Val, ZeroBehavior ZB) { - if (ZB != ZB_Undefined && Val == 0) - return 64; +template struct LeadingZerosCounter { + 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 +std::size_t countLeadingZeros(T Val, ZeroBehavior ZB = ZB_Width) { + static_assert(std::numeric_limits::is_integer && + !std::numeric_limits::is_signed, + "Only unsigned integral types are allowed."); + return detail::LeadingZerosCounter::count(Val, ZB); +} /// \brief Get the index of the first set bit starting from the least /// significant bit. @@ -179,22 +185,13 @@ inline std::size_t countLeadingZeros(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 std::enable_if::is_integer && - !std::numeric_limits::is_signed, T>::type -findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) { +template T findFirstSet(T Val, ZeroBehavior ZB = ZB_Max) { if (ZB == ZB_Max && Val == 0) return std::numeric_limits::max(); return countTrailingZeros(Val, ZB_Undefined); } -// Disable signed. -template -typename std::enable_if::is_integer && - std::numeric_limits::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 +199,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 std::enable_if::is_integer && - !std::numeric_limits::is_signed, T>::type -findLastSet(T Val, ZeroBehavior ZB = ZB_Max) { +template T findLastSet(T Val, ZeroBehavior ZB = ZB_Max) { if (ZB == ZB_Max && Val == 0) return std::numeric_limits::max(); @@ -215,12 +209,6 @@ findLastSet(T Val, ZeroBehavior ZB = ZB_Max) { (std::numeric_limits::digits - 1); } -// Disable signed. -template -typename std::enable_if::is_integer && - std::numeric_limits::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 -- 2.11.0