diff --git a/llvm/include/llvm/ADT/bit.h b/llvm/include/llvm/ADT/bit.h --- a/llvm/include/llvm/ADT/bit.h +++ b/llvm/include/llvm/ADT/bit.h @@ -34,6 +34,45 @@ return to; } +namespace detail { +template struct PopulationCounter { + static int count(T Value) { + // Generic version, forward to 32 bits. + static_assert(SizeOfT <= 4, "Not implemented!"); +#if defined(__GNUC__) + return (int)__builtin_popcount(Value); +#else + uint32_t v = Value; + v = v - ((v >> 1) & 0x55555555); + v = (v & 0x33333333) + ((v >> 2) & 0x33333333); + return int(((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24); +#endif + } +}; + +template struct PopulationCounter { + static int count(T Value) { +#if defined(__GNUC__) + return (int)__builtin_popcountll(Value); +#else + uint64_t v = Value; + v = v - ((v >> 1) & 0x5555555555555555ULL); + v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL); + v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL; + return int((uint64_t)(v * 0x0101010101010101ULL) >> 56); +#endif + } +}; +} // namespace detail + +/// Count the number of set bits in a value. +/// Ex. popcount(0xF000F000) = 8 +/// Returns 0 if the word is zero. +template >> +inline int popcount(T Value) noexcept { + return detail::PopulationCounter::count(Value); +} + } // namespace llvm #endif diff --git a/llvm/include/llvm/Support/MathExtras.h b/llvm/include/llvm/Support/MathExtras.h --- a/llvm/include/llvm/Support/MathExtras.h +++ b/llvm/include/llvm/Support/MathExtras.h @@ -13,6 +13,7 @@ #ifndef LLVM_SUPPORT_MATHEXTRAS_H #define LLVM_SUPPORT_MATHEXTRAS_H +#include "llvm/ADT/bit.h" #include "llvm/Support/Compiler.h" #include #include @@ -525,37 +526,6 @@ return countTrailingZeros(~Value, ZB); } -namespace detail { -template struct PopulationCounter { - static unsigned count(T Value) { - // Generic version, forward to 32 bits. - static_assert(SizeOfT <= 4, "Not implemented!"); -#if defined(__GNUC__) - 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 - } -}; - -template struct PopulationCounter { - static unsigned count(T Value) { -#if defined(__GNUC__) - return __builtin_popcountll(Value); -#else - 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 - /// Count the number of set bits in a value. /// Ex. countPopulation(0xF000F000) = 8 /// Returns 0 if the word is zero. @@ -564,7 +534,7 @@ static_assert(std::numeric_limits::is_integer && !std::numeric_limits::is_signed, "Only unsigned integral types are allowed."); - return detail::PopulationCounter::count(Value); + return (unsigned)llvm::popcount(Value); } /// Return true if the argument contains a non-empty sequence of ones with the