[ADT] Add llvm::popcount to <bit> helper wrapper

[RKSimon]

Summary

This patch proposes to move the llvm::detail::PopulationCounter internal helpers into ADT/bit.h and provide a llvm::popcount implementation.

I've left the countPopulation implementation in place in MathExtras.h for now, but updated it to use llvm::popcount.

Hopefully I've got the type_traits correct - I don't use them very often.

Someday we'll move to C++20 with an actual <bit> std header, and we already have this header in place to simplify matters. We'd probably benefit from moving the other <bit> helpers here at some point, but this is a first step.

[tschuett]

clang also supports __builtin_popcount:
https://clang.llvm.org/docs/LanguageExtensions.html

[RKSimon]

In D132407#3740594, @tschuett wrote:

clang also supports __builtin_popcount:
https://clang.llvm.org/docs/LanguageExtensions.html

Yeah - its just a copy + paste from MathExtras.h so far - I'll add a __has_builtin()

[Tyker]

llvm/include/llvm/ADT/bit.h

72–73

std::is_unsigned already implies std::is_integral
and it is preferable to use the *_v variants instead of adding the ::value

[RKSimon]

Use std::is_unsigned_v

No need to change #if defined(__GNUC__) as clang defines this as well

[kazu]

Great cleanup! Thanks!

[dblaikie]

In D132407#3740646, @RKSimon wrote:

In D132407#3740594, @tschuett wrote:

clang also supports __builtin_popcount:
https://clang.llvm.org/docs/LanguageExtensions.html

Yeah - its just a copy + paste from MathExtras.h so far - I'll add a __has_builtin()

Does it help? Or can LLVM pretty reliably optimize the code down to the same thing anyway? (be nice to avoid maintaining the different codepaths if they amount to the same thing anyway)

Looks like at least here clang uses the same code in either case (but doesn't use a CPU intrinsic, whereas GCC does (but GCC doesn't optimize the non-intrinsic code into the intrinsic...)): https://godbolt.org/z/G5YM4bcM6 ?

[RKSimon]

In D132407#3740750, @dblaikie wrote:

In D132407#3740646, @RKSimon wrote:

In D132407#3740594, @tschuett wrote:

clang also supports __builtin_popcount:
https://clang.llvm.org/docs/LanguageExtensions.html

Yeah - its just a copy + paste from MathExtras.h so far - I'll add a __has_builtin()

Does it help? Or can LLVM pretty reliably optimize the code down to the same thing anyway? (be nice to avoid maintaining the different codepaths if they amount to the same thing anyway)

Looks like at least here clang uses the same code in either case (but doesn't use a CPU intrinsic, whereas GCC does (but GCC doesn't optimize the non-intrinsic code into the intrinsic...)): https://godbolt.org/z/G5YM4bcM6 ?

Sorry I wasn't thinking when I replied - clang has always defined __GNUC__ so it already uses that path - unless we want to handle other compilers that support __has_builtin and __builtin_popcount I don't think we need it.

[kazu]

Looks like at least here clang uses the same code in either case (but doesn't use a CPU intrinsic, whereas GCC does (but GCC doesn't optimize the non-intrinsic code into the intrinsic...)): https://godbolt.org/z/G5YM4bcM6 ?

I get popcnt with -march=native.

[dblaikie]

In D132407#3740805, @kazu wrote:

Looks like at least here clang uses the same code in either case (but doesn't use a CPU intrinsic, whereas GCC does (but GCC doesn't optimize the non-intrinsic code into the intrinsic...)): https://godbolt.org/z/G5YM4bcM6 ?

I get popcnt with -march=native.

Ah, great.

Could we remove the intrinsic special case then, and just keep the explicit implementation - if it boils down to the same thing anyway, it saves us maintaining conditional code, etc?

llvm/include/llvm/ADT/bit.h

42–49

55–63

[MaskRay]

The subject should mention llvm::popcount instead of (Rust style name) llvm::ctpop

[RKSimon]

In D132407#3741645, @MaskRay wrote:

The subject should mention llvm::popcount instead of (Rust style name) llvm::ctpop

Done - my mind was obviously on other things while writing that summary!

llvm/include/llvm/ADT/bit.h

template <
     typename = std::enable_if_t<std::is_trivially_copyable<To>::value>,
     typename = std::enable_if_t<std::is_trivially_copyable<From>::value>>
 inline To bit_cast(const From &from) noexcept {
   To to;
   std::memcpy(&to, &from, sizeof(To));
   return to;
 }
 
+namespace detail {
+template <typename T, std::size_t SizeOfT> 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 <typename T> struct PopulationCounter<T, 8> {
+  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 <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
+inline int popcount(T Value) noexcept {
+  return detail::PopulationCounter<T, sizeof(T)>::count(Value);
+}
+
 } // namespace llvm
 
 #endif

llvm/include/llvm/Support/MathExtras.h

 //===-- llvm/Support/MathExtras.h - Useful math functions -------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains some functions that are useful for math stuff.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_MATHEXTRAS_H
 #define LLVM_SUPPORT_MATHEXTRAS_H
 
+#include "llvm/ADT/bit.h"
 #include "llvm/Support/Compiler.h"
 #include <cassert>
 #include <climits>
 #include <cmath>
 #include <cstdint>
 #include <cstring>
 #include <limits>
 #include <type_traits>

 template <typename T>
 unsigned countTrailingOnes(T Value, ZeroBehavior ZB = ZB_Width) {
   static_assert(std::numeric_limits<T>::is_integer &&
                     !std::numeric_limits<T>::is_signed,
                 "Only unsigned integral types are allowed.");
   return countTrailingZeros<T>(~Value, ZB);
 }
 
-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);
-#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);
-#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.
 template <typename T>
 inline unsigned countPopulation(T Value) {
   static_assert(std::numeric_limits<T>::is_integer &&
                     !std::numeric_limits<T>::is_signed,
                 "Only unsigned integral types are allowed.");
-  return detail::PopulationCounter<T, sizeof(T)>::count(Value);
+  return (unsigned)llvm::popcount(Value);
 }
 
 /// Return true if the argument contains a non-empty sequence of ones with the
 /// remainder zero (32 bit version.) Ex. isShiftedMask_32(0x0000FF00U) == true.
 /// If true, \p MaskIdx will specify the index of the lowest set bit and \p
 /// MaskLen is updated to specify the length of the mask, else neither are
 /// updated.
 inline bool isShiftedMask_32(uint32_t Value, unsigned &MaskIdx,