[ADT] Add bit_floor, bit_ceil, and bit_width to bit.h

[kazu]

Summary

This patch adds C++20-style bit_floor, bit_ceil, and bit_width.

In a subsequent patch, I'm going to define PowerOf2Floor in
MathExtras.h in terms of bit_floor.

Unfortunately, PowerOf2Ceil isn't quite the same as bit_ceil because
PowerOf2Ceil(0) == 0, whereas bit_ceil(0) == 1.

MathExtras.h does not have a function directly corresponding to
bit_width, but Log2_32(X) + 1, which occurs in a few places, can be
replaced with bit_width(X).

[RKSimon]

llvm/include/llvm/ADT/bit.h

245

bit_ceil can have UB behaviour for unrepresentable values - maybe at least mention this in the comment?

250

Does this need to be bit_width<T> or llvm::bit_width((T)(Value - 1u)) ?

[barannikov88]

All these functions are constexpr in C++20. Should we do the same?

[RKSimon]

In D142179#4068454, @barannikov88 wrote:

All these functions are constexpr in C++20. Should we do the same?

It'd be nice, but IIRC there were a few problems on some compilers when we tried to do this for some of the previous additions (plus for instance bit_cast uses memcpy).

[kazu]

I've added a comment about the undefined behavior.

I've specified the type like llvm::bit_width((T)(Value - 1u)).

[kazu]

In D142179#4068493, @RKSimon wrote:

In D142179#4068454, @barannikov88 wrote:

All these functions are constexpr in C++20. Should we do the same?

It'd be nice, but IIRC there were a few problems on some compilers when we tried to do this for some of the previous additions (plus for instance bit_cast uses memcpy).

Yes, it would be nice, but for now, I'd focus on providing these functions named consistently with their respective corresponding C++20 functions.

[RKSimon]

LGTM with one minor

llvm/unittests/ADT/BitTest.cpp

129

maybe add tests with the msb set for bit_width / bit_floor?

llvm/include/llvm/ADT/bit.h

 ///
 /// 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);
 }
 
+/// Returns the number of bits needed to represent Value if Value is nonzero.
+/// Returns 0 otherwise.
+///
+/// Ex. bit_width(5) == 3.
+template <typename T> int bit_width(T Value) {
+  static_assert(std::is_unsigned_v<T>,
+                "Only unsigned integral types are allowed.");
+  return std::numeric_limits<T>::digits - llvm::countl_zero(Value);
+}
+
+/// Returns the largest integral power of two no greater than Value if Value is
+/// nonzero.  Returns 0 otherwise.
+///
+/// Ex. bit_floor(5) == 4.
+template <typename T> T bit_floor(T Value) {
+  static_assert(std::is_unsigned_v<T>,
+                "Only unsigned integral types are allowed.");
+  if (!Value)
+    return 0;
+  return T(1) << (llvm::bit_width(Value) - 1);
+}
+
+/// Returns the smallest integral power of two no smaller than Value if Value is
+/// nonzero.  Returns 0 otherwise.
+///
+/// Ex. bit_ceil(5) == 8.
+///
+/// The return value is undefined if the input is larger than the largest power
+/// of two representable in T.
+template <typename T> T bit_ceil(T Value) {
+  static_assert(std::is_unsigned_v<T>,
+                "Only unsigned integral types are allowed.");
+  if (Value < 2)
+    return 1;
+  return T(1) << llvm::bit_width<T>(Value - 1u);
+}
+
 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/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, BitFloor) {
+  EXPECT_EQ(0u, llvm::bit_floor(uint8_t(0)));
+  EXPECT_EQ(0u, llvm::bit_floor(uint16_t(0)));
+  EXPECT_EQ(0u, llvm::bit_floor(uint32_t(0)));
+  EXPECT_EQ(0u, llvm::bit_floor(uint64_t(0)));
+
+  EXPECT_EQ(1u, llvm::bit_floor(uint8_t(1)));
+  EXPECT_EQ(1u, llvm::bit_floor(uint16_t(1)));
+  EXPECT_EQ(1u, llvm::bit_floor(uint32_t(1)));
+  EXPECT_EQ(1u, llvm::bit_floor(uint64_t(1)));
+
+  EXPECT_EQ(2u, llvm::bit_floor(uint8_t(2)));
+  EXPECT_EQ(2u, llvm::bit_floor(uint16_t(2)));
+  EXPECT_EQ(2u, llvm::bit_floor(uint32_t(2)));
+  EXPECT_EQ(2u, llvm::bit_floor(uint64_t(2)));
+
+  EXPECT_EQ(2u, llvm::bit_floor(uint8_t(3)));
+  EXPECT_EQ(2u, llvm::bit_floor(uint16_t(3)));
+  EXPECT_EQ(2u, llvm::bit_floor(uint32_t(3)));
+  EXPECT_EQ(2u, llvm::bit_floor(uint64_t(3)));
+
+  EXPECT_EQ(4u, llvm::bit_floor(uint8_t(4)));
+  EXPECT_EQ(4u, llvm::bit_floor(uint16_t(4)));
+  EXPECT_EQ(4u, llvm::bit_floor(uint32_t(4)));
+  EXPECT_EQ(4u, llvm::bit_floor(uint64_t(4)));
+
+  EXPECT_EQ(0x40u, llvm::bit_floor(uint8_t(0x7f)));
+  EXPECT_EQ(0x4000u, llvm::bit_floor(uint16_t(0x7fff)));
+  EXPECT_EQ(0x40000000u, llvm::bit_floor(uint32_t(0x7fffffffu)));
+  EXPECT_EQ(0x4000000000000000ull,
+            llvm::bit_floor(uint64_t(0x7fffffffffffffffull)));
+
+  EXPECT_EQ(0x80u, llvm::bit_floor(uint8_t(0x80)));
+  EXPECT_EQ(0x8000u, llvm::bit_floor(uint16_t(0x8000)));
+  EXPECT_EQ(0x80000000u, llvm::bit_floor(uint32_t(0x80000000u)));
+  EXPECT_EQ(0x8000000000000000ull,
+            llvm::bit_floor(uint64_t(0x8000000000000000ull)));
+
+  EXPECT_EQ(0x80u, llvm::bit_floor(uint8_t(0xff)));
+  EXPECT_EQ(0x8000u, llvm::bit_floor(uint16_t(0xffff)));
+  EXPECT_EQ(0x80000000u, llvm::bit_floor(uint32_t(0xffffffffu)));
+  EXPECT_EQ(0x8000000000000000ull,
+            llvm::bit_floor(uint64_t(0xffffffffffffffffull)));
+}
+
+TEST(BitTest, BitCeil) {
+  EXPECT_EQ(1u, llvm::bit_ceil(uint8_t(0)));
+  EXPECT_EQ(1u, llvm::bit_ceil(uint16_t(0)));
+  EXPECT_EQ(1u, llvm::bit_ceil(uint32_t(0)));
+  EXPECT_EQ(1u, llvm::bit_ceil(uint64_t(0)));
+
+  EXPECT_EQ(1u, llvm::bit_ceil(uint8_t(1)));
+  EXPECT_EQ(1u, llvm::bit_ceil(uint16_t(1)));
+  EXPECT_EQ(1u, llvm::bit_ceil(uint32_t(1)));
+  EXPECT_EQ(1u, llvm::bit_ceil(uint64_t(1)));
+
+  EXPECT_EQ(2u, llvm::bit_ceil(uint8_t(2)));
+  EXPECT_EQ(2u, llvm::bit_ceil(uint16_t(2)));
+  EXPECT_EQ(2u, llvm::bit_ceil(uint32_t(2)));
+  EXPECT_EQ(2u, llvm::bit_ceil(uint64_t(2)));
+
+  EXPECT_EQ(4u, llvm::bit_ceil(uint8_t(3)));
+  EXPECT_EQ(4u, llvm::bit_ceil(uint16_t(3)));
+  EXPECT_EQ(4u, llvm::bit_ceil(uint32_t(3)));
+  EXPECT_EQ(4u, llvm::bit_ceil(uint64_t(3)));
+
+  EXPECT_EQ(4u, llvm::bit_ceil(uint8_t(4)));
+  EXPECT_EQ(4u, llvm::bit_ceil(uint16_t(4)));
+  EXPECT_EQ(4u, llvm::bit_ceil(uint32_t(4)));
+  EXPECT_EQ(4u, llvm::bit_ceil(uint64_t(4)));
+
+  // The result is the largest representable value for each type.
+  EXPECT_EQ(0x80u, llvm::bit_ceil(uint8_t(0x7f)));
+  EXPECT_EQ(0x8000u, llvm::bit_ceil(uint16_t(0x7fff)));
+  EXPECT_EQ(0x80000000u, llvm::bit_ceil(uint32_t(0x7fffffffu)));
+  EXPECT_EQ(0x8000000000000000ull,
+            llvm::bit_ceil(uint64_t(0x7fffffffffffffffull)));
+}
+
+TEST(BitTest, BitWidth) {
+  EXPECT_EQ(0, llvm::bit_width(uint8_t(0)));
+  EXPECT_EQ(0, llvm::bit_width(uint16_t(0)));
+  EXPECT_EQ(0, llvm::bit_width(uint32_t(0)));
+  EXPECT_EQ(0, llvm::bit_width(uint64_t(0)));
+
+  EXPECT_EQ(1, llvm::bit_width(uint8_t(1)));
+  EXPECT_EQ(1, llvm::bit_width(uint16_t(1)));
+  EXPECT_EQ(1, llvm::bit_width(uint32_t(1)));
+  EXPECT_EQ(1, llvm::bit_width(uint64_t(1)));
+
+  EXPECT_EQ(2, llvm::bit_width(uint8_t(2)));
+  EXPECT_EQ(2, llvm::bit_width(uint16_t(2)));
+  EXPECT_EQ(2, llvm::bit_width(uint32_t(2)));
+  EXPECT_EQ(2, llvm::bit_width(uint64_t(2)));
+
+  EXPECT_EQ(2, llvm::bit_width(uint8_t(3)));
+  EXPECT_EQ(2, llvm::bit_width(uint16_t(3)));
+  EXPECT_EQ(2, llvm::bit_width(uint32_t(3)));
+  EXPECT_EQ(2, llvm::bit_width(uint64_t(3)));
+
+  EXPECT_EQ(3, llvm::bit_width(uint8_t(4)));
+  EXPECT_EQ(3, llvm::bit_width(uint16_t(4)));
+  EXPECT_EQ(3, llvm::bit_width(uint32_t(4)));
+  EXPECT_EQ(3, llvm::bit_width(uint64_t(4)));
+
+  EXPECT_EQ(7, llvm::bit_width(uint8_t(0x7f)));
+  EXPECT_EQ(15, llvm::bit_width(uint16_t(0x7fff)));
+  EXPECT_EQ(31, llvm::bit_width(uint32_t(0x7fffffffu)));
+  EXPECT_EQ(63, llvm::bit_width(uint64_t(0x7fffffffffffffffull)));
+
+  EXPECT_EQ(8, llvm::bit_width(uint8_t(0x80)));
+  EXPECT_EQ(16, llvm::bit_width(uint16_t(0x8000)));
+  EXPECT_EQ(32, llvm::bit_width(uint32_t(0x80000000u)));
+  EXPECT_EQ(64, llvm::bit_width(uint64_t(0x8000000000000000ull)));
+
+  EXPECT_EQ(8, llvm::bit_width(uint8_t(0xff)));
+  EXPECT_EQ(16, llvm::bit_width(uint16_t(0xffff)));
+  EXPECT_EQ(32, llvm::bit_width(uint32_t(0xffffffffu)));
+  EXPECT_EQ(64, llvm::bit_width(uint64_t(0xffffffffffffffffull)));
+}
+
 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));