[MathExtras] Add intrinsic for the PopulationCounter in Visual Studio

[ekatz]

Summary

The Visual Studio popcnt and popcnt64 intrinsics should be used the same way the GNU __builtin_popcount is already used.

[craig.topper]

I'm pretty sure MSVC will always turn this into a popcnt instruction on X86. It has no fall back because MSVC doesn't have a concept of a target CPU. So this would only work on a Nehalem or newer CPU that implements the instruction.

[ekatz]

In D69334#1719297, @craig.topper wrote:

I'm pretty sure MSVC will always turn this into a popcnt instruction on X86. It has no fall back because MSVC doesn't have a concept of a target CPU. So this would only work on a Nehalem or newer CPU that implements the instruction.

Actually, it seems MSVC never does that optimization. Not on 32-bit or 64-bit.
Regarding the supported CPU issue; Nehalem is over a decade old. How far back do we want to support? I think it is reasonable to assume popcnt is always available.

[craig.topper]

In D69334#1724314, @ekatz wrote:

In D69334#1719297, @craig.topper wrote:

I'm pretty sure MSVC will always turn this into a popcnt instruction on X86. It has no fall back because MSVC doesn't have a concept of a target CPU. So this would only work on a Nehalem or newer CPU that implements the instruction.

Actually, it seems MSVC never does that optimization. Not on 32-bit or 64-bit.

Never does what optimization?

Regarding the supported CPU issue; Nehalem is over a decade old. How far back do we want to support? I think it is reasonable to assume popcnt is always ava

[ekatz]

In D69334#1724435, @craig.topper wrote:

Never does what optimization?

Sorry, I though you meant that MSVC will automatically convert the popcnt bit twiddling pattern to the popcnt intrinsic. This optimization is done in LLVM, but not in MSVC.

In any case, as I wrote:

In D69334#1724314, @ekatz wrote:

Regarding the supported CPU issue; Nehalem is over a decade old. How far back do we want to support? I think it is reasonable to assume popcnt is always available.

[RKSimon]

GCC's __builtin_popcnt guarantees fallback to generic code if the cpu doesn't support a CTPOP-style instruction, I'm not sure how many people build clang with -march=native (or whatever) but I'd expect most people to just build for generic x86_64, which means we're probably executing a slow generic path anyhow.

The MSVC popcnt intrinsics always generates a x86 POPCNT instruction and we can't assume that this is available - its annoying but I can guarantee that somebody out there is building/running on an old box (or VM) that will fail.

As Craig mentioned MSVC is awful at building with target cpu defines - its gotten better and defines AVX__/AVX2__ etc. more recently but that's a poor wrapper for checking whether POPCNT can be used.

[RKSimon]

Abandon this? As I explained, MSVC doesn't provide a guaranteed fallback for targets without the POPCNT instruction.

[ekatz]

I thought I might add a dynamic detection to the CMake files, as it already does that for headers and other supported functionalities. Didn't find the time for it, as it is a pretty low priority. But, what do you think?

[RKSimon]

TBH I don't think this is worth it unless you can demonstrate actual reductions in compile time - once C++20 lands and we're allowed to use its features we can move to using std::popcount and avoid all of this.

[ekatz]

I agree. This seems like too much of a hassle. I'll abandon this patch.

llvm/include/llvm/Support/MathExtras.h

 // Declare these intrinsics manually rather including intrin.h. It's very
 // expensive, and MathExtras.h is popular.
 // #include <intrin.h>
 extern "C" {
 unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask);
 unsigned char _BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask);
 unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask);
 unsigned char _BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask);
+unsigned int __popcnt(unsigned int);
+unsigned __int64 __popcnt64(unsigned __int64);
 }
 #endif
 
 namespace llvm {
 
 /// The behavior an operation has on an input of 0.
 enum ZeroBehavior {
   /// The returned value is undefined.

 
 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 defined(__GNUC__)
     return __builtin_popcount(Value);
+#elif defined(_MSC_VER) && _MSC_VER >= 1500 &&                                 \
+    (defined(_M_IX86) || defined(_M_X64))
+    return __popcnt(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 <typename T> struct PopulationCounter<T, 8> {
   static unsigned count(T Value) {
 #if defined(__GNUC__)
     return __builtin_popcountll(Value);
+#elif defined(_MSC_VER) && _MSC_VER >= 1500 && defined(_M_X64)
+    return (unsigned)__popcnt64(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
   }