[llvm] Move bit counting functions to bit.h (NFC)

[kazu]

Summary

This patch provides C++20-style countl_zero, countr_zero, countl_one,
and countl_one in bit.h. Existing functions like countLeadingZeros
become wrappers around the new functions.

Note that I cannot quite declare countLeadingZeros as:

template <class T> using countLeadingZeros = countl_zero<T>;

because countl_zero returns int, whereas countLeadingZeros returns
unsigned.

[dblaikie]

Is the plan to migrate callers over to this eventually, and remove the countNnn wrappers?

llvm/include/llvm/ADT/bit.h

44–54

Instead of this, perhaps we could write small/simple wrappers, avoiding the need to forward declare things from platform headers? & possibly wrapping the basic operations/differences between the platforms in a more direct way, then exposing these higher level primitives based on those abstractions?

[kazu]

In D142078#4064301, @dblaikie wrote:

Is the plan to migrate callers over to this eventually, and remove the countNnn wrappers?

Yes.

llvm/include/llvm/ADT/bit.h

44–54

Do you mean something like this?

namespace detail {
#if __has_builtin(__builtin_clz) || defined(__GNUC__)
inline constexpr bool has_clz = true;
inline unsigned clz(unsigned Val) {
  return __builtin_clz(Val)
}
#else defined(_MSC_VER)
inline constexpr bool has_clz = true;
inline unsigned clz(unsigned Val) {
  unsigned long Index;
  _BitScanForward(&Index, Val);
  return Index;
}
#else
inline constexpr bool has_clz = false;
#endif
}  // namespace detail

Then implement llvm::countl_zero with llvm::detail::has_clz and llvm::detail:clz?

If so, I like this idea, but I don't see how we can avoid forward-declaring things. The comment says intrin.h is very expensive although I don't know whether the comment is still applicable today or how old the comment is.

[RKSimon]

Thanks @kazu!

Please can you add test coverage to ADT/BitTest.cpp ? By the looks of it we never added any equivalent to Support/MathExtrasTest.cpp :(

llvm/include/llvm/ADT/bit.h

44–54

intrin.h is still (or possibly more) expensive to include, so avoiding use in a common header like this would be best.

46

MathExtras.h ?

llvm/include/llvm/Support/MathExtras.h

22

Can you confirm are all of these still needed?

[dblaikie]

llvm/include/llvm/ADT/bit.h

44–54

I was thinking of an out of line solution - where the use of __builtin_clz and _BitScanForward are in a .cpp file, not in a header. I guess then performance is so bad that LTO is required to get to something reasonable? Maybe that's OK?

[kazu]

I've moved the forward declarations of _BitScan* functions to bit.h
instead of copying them.

I've also added unit tests.

I've removed #include "llvm/Support/Compiler.h" in MathExtras.h as we
don't need it according to include-what-you-use.

[kazu]

Please take a look. Thanks!

llvm/include/llvm/ADT/bit.h

44–54

Hmm. I am not sure if I want to go as far as requiring users to have LTO.

I think what to do with these forward declarations is somewhat orthogonal to moving these bit counting functions to bit.h.

46

I've updated the comment.

llvm/include/llvm/Support/MathExtras.h

22

include-what-you-use tells me that I can remove:

#include "llvm/Support/Compiler.h"

at least on a x86_64 Linux machine.

We still need all the others.

[dblaikie]

llvm/include/llvm/ADT/bit.h

44–54

Oh, sorry, fair enough - if it's just moving things around they might be unfortunate but it's no worse and not bad enough to relitigate. Sorry for the distraction.

[vzakhari]

llvm/include/llvm/Support/MathExtras.h

17

This removal breaks the build with GCC-9*, because __has_builtin seems to be available starting GCC-10. Now we are missing this useful code from Compiler.h:

#ifndef __has_builtin
# define __has_builtin(x) 0
#endif

Can you please bring the include back to both MathExtras.h and bit.h?

[vzakhari]

llvm/include/llvm/Support/MathExtras.h

17

This buildbot is broken as well: https://lab.llvm.org/buildbot/#/builders/94/builds/12995

[kazu]

llvm/include/llvm/Support/MathExtras.h

17

I just checked in:

https://github.com/llvm/llvm-project/commit/dddcf3014aa094d3ecd0430511a5c10045fefbd6

Thank you for reporting the problem!

[thakis]

This breaks building on windows: http://45.33.8.238/win/73448/step_4.txt

Please take a look and revert for now if it takes a while to fix.

[barannikov88]

I guess forward declarations should be moved to global namespace?

[thakis]

Reverted in 95914abd13ef0e447392f9f5e38487d8471a92b7 for now.

[kazu]

In D142078#4069670, @thakis wrote:

Reverted in 95914abd13ef0e447392f9f5e38487d8471a92b7 for now.

Thank you for taking care of this!

llvm/include/llvm/ADT/bit.h

 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_BIT_H
 #define LLVM_ADT_BIT_H
 
 #include <cstdint>
 #include <cstring>
+#include <limits>
 #include <type_traits>
 
 namespace llvm {
 
 // This implementation of bit_cast is different from the C++20 one in two ways:
 //  - It isn't constexpr because that requires compiler support.
 //  - It requires trivially-constructible To, to avoid UB in the implementation.
 template <
     typename To, typename From,
     typename = std::enable_if_t<sizeof(To) == sizeof(From)>,
     typename = std::enable_if_t<std::is_trivially_constructible<To>::value>,
     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;
 }
 
 template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
 constexpr inline bool has_single_bit(T Value) noexcept {
   return (Value != 0) && ((Value & (Value - 1)) == 0);
 }
 
+#ifdef _MSC_VER
+// Declare these intrinsics manually rather including intrin.h. It's very
+// expensive, and bit.h is popular via MathExtras.h.
+// #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);
+}
+#endif
+
+namespace detail {
+template <typename T, std::size_t SizeOfT> struct TrailingZerosCounter {
+  static unsigned count(T Val) {
+    if (!Val)
+      return std::numeric_limits<T>::digits;
+    if (Val & 0x1)
+      return 0;
+
+    // Bisection method.
+    unsigned ZeroBits = 0;
+    T Shift = std::numeric_limits<T>::digits >> 1;
+    T Mask = std::numeric_limits<T>::max() >> Shift;
+    while (Shift) {
+      if ((Val & Mask) == 0) {
+        Val >>= Shift;
+        ZeroBits |= Shift;
+      }
+      Shift >>= 1;
+      Mask >>= Shift;
+    }
+    return ZeroBits;
+  }
+};
+
+#if defined(__GNUC__) || defined(_MSC_VER)
+template <typename T> struct TrailingZerosCounter<T, 4> {
+  static unsigned count(T Val) {
+    if (Val == 0)
+      return 32;
+
+#if __has_builtin(__builtin_ctz) || defined(__GNUC__)
+    return __builtin_ctz(Val);
+#elif defined(_MSC_VER)
+    unsigned long Index;
+    _BitScanForward(&Index, Val);
+    return Index;
+#endif
+  }
+};
+
+#if !defined(_MSC_VER) || defined(_M_X64)
+template <typename T> struct TrailingZerosCounter<T, 8> {
+  static unsigned count(T Val) {
+    if (Val == 0)
+      return 64;
+
+#if __has_builtin(__builtin_ctzll) || defined(__GNUC__)
+    return __builtin_ctzll(Val);
+#elif defined(_MSC_VER)
+    unsigned long Index;
+    _BitScanForward64(&Index, Val);
+    return Index;
+#endif
+  }
+};
+#endif
+#endif
+} // namespace detail
+
+/// Count number of 0's from the least significant bit to the most
+///   stopping at the first 1.
+///
+/// Only unsigned integral types are allowed.
+///
+/// Returns std::numeric_limits<T>::digits on an input of 0.
+template <typename T> int countr_zero(T Val) {
+  static_assert(std::is_unsigned_v<T>,
+                "Only unsigned integral types are allowed.");
+  return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val);
+}
+
+namespace detail {
+template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter {
+  static unsigned count(T Val) {
+    if (!Val)
+      return std::numeric_limits<T>::digits;
+
+    // Bisection method.
+    unsigned ZeroBits = 0;
+    for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) {
+      T Tmp = Val >> Shift;
+      if (Tmp)
+        Val = Tmp;
+      else
+        ZeroBits |= Shift;
+    }
+    return ZeroBits;
+  }
+};
+
+#if defined(__GNUC__) || defined(_MSC_VER)
+template <typename T> struct LeadingZerosCounter<T, 4> {
+  static unsigned count(T Val) {
+    if (Val == 0)
+      return 32;
+
+#if __has_builtin(__builtin_clz) || defined(__GNUC__)
+    return __builtin_clz(Val);
+#elif defined(_MSC_VER)
+    unsigned long Index;
+    _BitScanReverse(&Index, Val);
+    return Index ^ 31;
+#endif
+  }
+};
+
+#if !defined(_MSC_VER) || defined(_M_X64)
+template <typename T> struct LeadingZerosCounter<T, 8> {
+  static unsigned count(T Val) {
+    if (Val == 0)
+      return 64;
+
+#if __has_builtin(__builtin_clzll) || defined(__GNUC__)
+    return __builtin_clzll(Val);
+#elif defined(_MSC_VER)
+    unsigned long Index;
+    _BitScanReverse64(&Index, Val);
+    return Index ^ 63;
+#endif
+  }
+};
+#endif
+#endif
+} // namespace detail
+
+/// Count number of 0's from the most significant bit to the least
+///   stopping at the first 1.
+///
+/// Only unsigned integral types are allowed.
+///
+/// Returns std::numeric_limits<T>::digits on an input of 0.
+template <typename T> int countl_zero(T Val) {
+  static_assert(std::is_unsigned_v<T>,
+                "Only unsigned integral types are allowed.");
+  return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val);
+}
+
+/// Count the number of ones from the most significant bit to the first
+/// zero bit.
+///
+/// Ex. countl_one(0xFF0FFF00) == 8.
+/// Only unsigned integral types are allowed.
+///
+/// Returns std::numeric_limits<T>::digits on an input of all ones.
+template <typename T> int countl_one(T Value) {
+  static_assert(std::is_unsigned_v<T>,
+                "Only unsigned integral types are allowed.");
+  return llvm::countl_zero<T>(~Value);
+}
+
+/// Count the number of ones from the least significant bit to the first
+/// zero bit.
+///
+/// Ex. countr_one(0x00FF00FF) == 8.
+/// Only unsigned integral types are allowed.
+///
+/// Returns std::numeric_limits<T>::digits on an input of all ones.
+template <typename T> int countr_one(T Value) {
+  static_assert(std::is_unsigned_v<T>,
+                "Only unsigned integral types are allowed.");
+  return llvm::countr_zero<T>(~Value);
+}
+
 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

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 <cstdint>
 #include <cstring>
 #include <limits>
 #include <type_traits>
 
-#ifdef _MSC_VER
-// 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);
-}
-#endif
-
 namespace llvm {
 
 /// The behavior an operation has on an input of 0.
 enum ZeroBehavior {
   /// The returned value is undefined.
   ZB_Undefined,
   /// The returned value is numeric_limits<T>::max()
   ZB_Max
constexpr float ef          = 2.71828183F, // (0x1.5bf0a8P+1) https://oeis.org/A001113
                 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) {
-    if (!Val)
-      return std::numeric_limits<T>::digits;
-    if (Val & 0x1)
-      return 0;
-
-    // Bisection method.
-    unsigned ZeroBits = 0;
-    T Shift = std::numeric_limits<T>::digits >> 1;
-    T Mask = std::numeric_limits<T>::max() >> Shift;
-    while (Shift) {
-      if ((Val & Mask) == 0) {
-        Val >>= Shift;
-        ZeroBits |= Shift;
-      }
-      Shift >>= 1;
-      Mask >>= Shift;
-    }
-    return ZeroBits;
-  }
-};
-
-#if defined(__GNUC__) || defined(_MSC_VER)
-template <typename T> struct TrailingZerosCounter<T, 4> {
-  static unsigned count(T Val) {
-    if (Val == 0)
-      return 32;
-
-#if __has_builtin(__builtin_ctz) || defined(__GNUC__)
-    return __builtin_ctz(Val);
-#elif defined(_MSC_VER)
-    unsigned long Index;
-    _BitScanForward(&Index, Val);
-    return Index;
-#endif
-  }
-};
-
-#if !defined(_MSC_VER) || defined(_M_X64)
-template <typename T> struct TrailingZerosCounter<T, 8> {
-  static unsigned count(T Val) {
-    if (Val == 0)
-      return 64;
-
-#if __has_builtin(__builtin_ctzll) || defined(__GNUC__)
-    return __builtin_ctzll(Val);
-#elif defined(_MSC_VER)
-    unsigned long Index;
-    _BitScanForward64(&Index, Val);
-    return Index;
-#endif
-  }
-};
-#endif
-#endif
-} // namespace detail
-
 /// Count number of 0's from the least significant bit to the most
 ///   stopping at the first 1.
 ///
 /// Only unsigned integral types are allowed.
 ///
 /// Returns std::numeric_limits<T>::digits on an input of 0.
 template <typename T> unsigned countTrailingZeros(T Val) {
   static_assert(std::is_unsigned_v<T>,
                 "Only unsigned integral types are allowed.");
-  return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val);
-}
-
-namespace detail {
-template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter {
-  static unsigned count(T Val) {
-    if (!Val)
-      return std::numeric_limits<T>::digits;
-
-    // Bisection method.
-    unsigned ZeroBits = 0;
-    for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) {
-      T Tmp = Val >> Shift;
-      if (Tmp)
-        Val = Tmp;
-      else
-        ZeroBits |= Shift;
-    }
-    return ZeroBits;
-  }
-};
-
-#if defined(__GNUC__) || defined(_MSC_VER)
-template <typename T> struct LeadingZerosCounter<T, 4> {
-  static unsigned count(T Val) {
-    if (Val == 0)
-      return 32;
-
-#if __has_builtin(__builtin_clz) || defined(__GNUC__)
-    return __builtin_clz(Val);
-#elif defined(_MSC_VER)
-    unsigned long Index;
-    _BitScanReverse(&Index, Val);
-    return Index ^ 31;
-#endif
-  }
-};
-
-#if !defined(_MSC_VER) || defined(_M_X64)
-template <typename T> struct LeadingZerosCounter<T, 8> {
-  static unsigned count(T Val) {
-    if (Val == 0)
-      return 64;
-
-#if __has_builtin(__builtin_clzll) || defined(__GNUC__)
-    return __builtin_clzll(Val);
-#elif defined(_MSC_VER)
-    unsigned long Index;
-    _BitScanReverse64(&Index, Val);
-    return Index ^ 63;
-#endif
-  }
-};
-#endif
-#endif
-} // namespace detail
+  return llvm::countr_zero(Val);
 
 /// Count number of 0's from the most significant bit to the least
 ///   stopping at the first 1.
 ///
 /// Only unsigned integral types are allowed.
 ///
 /// Returns std::numeric_limits<T>::digits on an input of 0.
 template <typename T> unsigned countLeadingZeros(T Val) {
   static_assert(std::is_unsigned_v<T>,
                 "Only unsigned integral types are allowed.");
-  return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val);
+  return llvm::countl_zero(Val);
 }
 
 /// Get the index of the first set bit starting from the least
 ///   significant bit.
 ///
 /// Only unsigned integral types are allowed.
 ///
 /// \param ZB the behavior on an input of 0.

 ///
 /// Ex. countLeadingOnes(0xFF0FFF00) == 8.
 /// Only unsigned integral types are allowed.
 ///
 /// Returns std::numeric_limits<T>::digits on an input of all ones.
 template <typename T> unsigned countLeadingOnes(T Value) {
   static_assert(std::is_unsigned_v<T>,
                 "Only unsigned integral types are allowed.");
-  return countLeadingZeros<T>(~Value);
+  return llvm::countl_one<T>(Value);
 }
 
 /// Count the number of ones from the least significant bit to the first
 /// zero bit.
 ///
 /// Ex. countTrailingOnes(0x00FF00FF) == 8.
 /// Only unsigned integral types are allowed.
 ///
 /// Returns std::numeric_limits<T>::digits on an input of all ones.
 template <typename T> unsigned countTrailingOnes(T Value) {
   static_assert(std::is_unsigned_v<T>,
                 "Only unsigned integral types are allowed.");
-  return countTrailingZeros<T>(~Value);
+  return llvm::countr_one<T>(Value);
 }
 
 /// 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::is_unsigned_v<T>,

llvm/unittests/ADT/BitTest.cpp

TEST(BitTest, HasSingleBit) {
 
   static const int8_t kValueS8 = -128;
   EXPECT_TRUE(llvm::has_single_bit(static_cast<uint8_t>(kValueS8)));
 
   static const int16_t kValueS16 = -32768;
   EXPECT_TRUE(llvm::has_single_bit(static_cast<uint16_t>(kValueS16)));
 }
 
+TEST(BitTest, CountlZero) {
+  uint8_t Z8 = 0;
+  uint16_t Z16 = 0;
+  uint32_t Z32 = 0;
+  uint64_t Z64 = 0;
+  EXPECT_EQ(8, llvm::countl_zero(Z8));
+  EXPECT_EQ(16, llvm::countl_zero(Z16));
+  EXPECT_EQ(32, llvm::countl_zero(Z32));
+  EXPECT_EQ(64, llvm::countl_zero(Z64));
+
+  uint8_t NZ8 = 42;
+  uint16_t NZ16 = 42;
+  uint32_t NZ32 = 42;
+  uint64_t NZ64 = 42;
+  EXPECT_EQ(2, llvm::countl_zero(NZ8));
+  EXPECT_EQ(10, llvm::countl_zero(NZ16));
+  EXPECT_EQ(26, llvm::countl_zero(NZ32));
+  EXPECT_EQ(58, llvm::countl_zero(NZ64));
+
+  EXPECT_EQ(8, llvm::countl_zero(0x00F000FFu));
+  EXPECT_EQ(8, llvm::countl_zero(0x00F12345u));
+  for (unsigned i = 0; i <= 30; ++i) {
+    EXPECT_EQ(int(31 - i), llvm::countl_zero(1u << i));
+  }
+
+  EXPECT_EQ(8, llvm::countl_zero(0x00F1234500F12345ULL));
+  EXPECT_EQ(1, llvm::countl_zero(1ULL << 62));
+  for (unsigned i = 0; i <= 62; ++i) {
+    EXPECT_EQ(int(63 - i), llvm::countl_zero(1ULL << i));
+  }
+}
+
+TEST(BitTest, CountrZero) {
+  uint8_t Z8 = 0;
+  uint16_t Z16 = 0;
+  uint32_t Z32 = 0;
+  uint64_t Z64 = 0;
+  EXPECT_EQ(8, llvm::countr_zero(Z8));
+  EXPECT_EQ(16, llvm::countr_zero(Z16));
+  EXPECT_EQ(32, llvm::countr_zero(Z32));
+  EXPECT_EQ(64, llvm::countr_zero(Z64));
+
+  uint8_t NZ8 = 42;
+  uint16_t NZ16 = 42;
+  uint32_t NZ32 = 42;
+  uint64_t NZ64 = 42;
+  EXPECT_EQ(1, llvm::countr_zero(NZ8));
+  EXPECT_EQ(1, llvm::countr_zero(NZ16));
+  EXPECT_EQ(1, llvm::countr_zero(NZ32));
+  EXPECT_EQ(1, llvm::countr_zero(NZ64));
+}
+
+TEST(BitTest, CountlOne) {
+  for (int i = 30; i >= 0; --i) {
+    // Start with all ones and unset some bit.
+    EXPECT_EQ(31 - i, llvm::countl_one(0xFFFFFFFF ^ (1 << i)));
+  }
+  for (int i = 62; i >= 0; --i) {
+    // Start with all ones and unset some bit.
+    EXPECT_EQ(63 - i, llvm::countl_one(0xFFFFFFFFFFFFFFFFULL ^ (1LL << i)));
+  }
+  for (int i = 30; i >= 0; --i) {
+    // Start with all ones and unset some bit.
+    EXPECT_EQ(31 - i, llvm::countl_one(0xFFFFFFFF ^ (1 << i)));
+  }
+}
+
+TEST(BitTest, CountrOne) {
+  uint8_t AllOnes8 = ~(uint8_t)0;
+  uint16_t AllOnes16 = ~(uint16_t)0;
+  uint32_t AllOnes32 = ~(uint32_t)0;
+  uint64_t AllOnes64 = ~(uint64_t)0;
+  EXPECT_EQ(8, llvm::countr_one(AllOnes8));
+  EXPECT_EQ(16, llvm::countr_one(AllOnes16));
+  EXPECT_EQ(32, llvm::countr_one(AllOnes32));
+  EXPECT_EQ(64, llvm::countr_one(AllOnes64));
+
+  uint8_t X8 = 6;
+  uint16_t X16 = 6;
+  uint32_t X32 = 6;
+  uint64_t X64 = 6;
+  EXPECT_EQ(0, llvm::countr_one(X8));
+  EXPECT_EQ(0, llvm::countr_one(X16));
+  EXPECT_EQ(0, llvm::countr_one(X32));
+  EXPECT_EQ(0, llvm::countr_one(X64));
+
+  uint8_t Y8 = 23;
+  uint16_t Y16 = 23;
+  uint32_t Y32 = 23;
+  uint64_t Y64 = 23;
+  EXPECT_EQ(3, llvm::countr_one(Y8));
+  EXPECT_EQ(3, llvm::countr_one(Y16));
+  EXPECT_EQ(3, llvm::countr_one(Y32));
+  EXPECT_EQ(3, llvm::countr_one(Y64));
+}
+
 TEST(BitTest, PopCount) {
   EXPECT_EQ(0, llvm::popcount(0U));
   EXPECT_EQ(0, llvm::popcount(0ULL));
 
   EXPECT_EQ(32, llvm::popcount(~0U));
   EXPECT_EQ(64, llvm::popcount(~0ULL));
 
   for (int I = 0; I != 32; ++I)
     EXPECT_EQ(1, llvm::popcount(1U << I));
 }
 
 } // anonymous namespace