[ADT] Add Bitfield utilities - design #3

[gchatelet]

Summary

Alternative design to D81580 with the following change in API

before: using Bool = Bitfield<bool, 0, 1>;
after:  using Bool = Bitfield::Element<bool, 0, 1>;

// Testing a field
before: if(Bool::testField(Storage))
after:  if(Bitfield::test<Bool>(Storage))

// Getting a field
before: auto Value = Bool::getField(Storage);
after:  auto Value = Bitfield::get<Bool>(Storage);

// Setting a field
before: Bool::setField(Storage, Value);
after:  Bitfield::set<Bool>(Storage, Value);

[courbet]

llvm/include/llvm/ADT/Bitfields.h

77

details::Impl is a bit too generic and might collide. bitfields_detail ?

[gchatelet]

• Address comments

[rriddle]

llvm/include/llvm/ADT/Bitfields.h

205

typo: conditionnal

213

nit: Why the newline here?

215

Did you intend for \param T to be on the next line?

220

You could likely simplify this with SFINAE:

template <typename T, unsigned Offset, unsigned Size,
        T MaxValue = std::numeric_limits<T>::max(),
        bool IsEnum = std::is_enum<T>::value>
struct Element {
};

template <typename T, unsigned Offset, unsigned Size, T MaxValue>
struct Element<T, Offset, Size, MaxValue, true>
   : public Element<typename std::underlying_type<T>::type, Offset, Size, MaxValue> {
  using Type = T;
};

[gchatelet]

• Address comments

llvm/include/llvm/ADT/Bitfields.h

215

Good catch. Documentation was half-done and clang-format messed up with the lines.

220

I've tried that but we need a few more tweaks to make it compile:

• cast MaxValue to the underlying type in the enum specialization,
• add a using directive to be able to access IntegerTypeat instantiation time.

With this, it's not that much simpler. Especially with the fact that you need to consider more code to understand the whole thing. WDYT?

template <typename T, unsigned Offset, unsigned Size,
          T MaxValue = std::numeric_limits<T>::max(),
          bool IsEnum = std::is_enum<T>::value>
struct Element {
};

template <typename T, unsigned Offset, unsigned Size, T MaxValue>
struct Element<T, Offset, Size, MaxValue, true>
    : public Element<typename std::underlying_type<T>::type, Offset, Size,
                     static_cast<typename std::underlying_type<T>::type>(
                         MaxValue)> {
  using Type = T;

private:
  using BaseT =
      Element<typename std::underlying_type<T>::type, Offset, Size,
              static_cast<typename std::underlying_type<T>::type>(MaxValue)>;
  static_assert(std::is_unsigned<typename BaseT::IntegerType>::value,
                "Enum must be unsigned");
};

[gchatelet]

@serge-sans-paille let me know what you think of this version.
It's not object oriented but I find it pretty compelling.

[serge-sans-paille]

In D82454#2116409, @gchatelet wrote:

@serge-sans-paille let me know what you think of this version.
It's not object oriented but I find it pretty compelling.

I'm fine with that API too, and it's implementation is simpler. I'll have a look to the implementation.

[serge-sans-paille]

LGTM.

[aprantl]

llvm/include/llvm/ADT/Bitfields.h

16

consistent

94

Could you please use /// doxygen comments for (pretty much) all comments in this file?

[rriddle]

llvm/include/llvm/ADT/Bitfields.h

220

SGTM

[gchatelet]

• Fix typo and doxygen comments

[courbet]

llvm/include/llvm/ADT/Bitfields.h

22

ensure

194

semantics

[gchatelet]

@courbet I've addressed the typos in rGb7ca06b74505fb2daaee746403cc9ee3b78ac1d0.

[gchatelet]

submitted as rGb56b467a9a84510bd1c5a573c863cb86c98afbcd

llvm/include/llvm/ADT/Bitfields.h

+//===-- llvm/ADT/Bitfield.h - Get and Set bits in an integer ---*- 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
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// This file implements methods to test, set and extract typed bits from packed
+/// unsigned integers.
+/// \code{.cpp}
+///  uint8_t Storage = 0;
+///
+///  // Store and retrieve a single bit as bool.
+///  using Bool = Bitfield::Element<bool, 0, 1>;
+///  Bitfield::set<Bool>(Storage, true);
+///  EXPECT_EQ(Storage, 0b00000001);
+///  //                          ^
+///  EXPECT_EQ(Bitfield::get<Bool>(Storage), true);
+///
+///  // Store and retrieve a 2 bit typed enum.
+///  // Note: enum underlying type must be unsigned.
+///  enum class SuitEnum : uint8_t { CLUBS, DIAMONDS, HEARTS, SPADES };
+///  // Note: enum maximum value needs to be passed in as last parameter.
+///  using Suit = Bitfield::Element<SuitEnum, 1, 2, SuitEnum::SPADES>;
+///  Bitfield::set<Suit>(Storage, SuitEnum::HEARTS);
+///  EXPECT_EQ(Storage, 0b00000101);
+///  //                        ^^
+///  EXPECT_EQ(Bitfield::get<Suit>(Storage), SuitEnum::HEARTS);
+///
+///  // Store and retrieve a 5 bit value as unsigned.
+///  using Value = Bitfield::Element<unsigned, 3, 5>;
+///  Bitfield::set<Value>(Storage, 10);
+///  EXPECT_EQ(Storage, 0b01010101);
+///  //                   ^^^^^
+///  EXPECT_EQ(Bitfield::get<Value>(Storage), 10U);
+///
+///  // Interpret the same 5 bit value as signed.
+///  using SignedValue = Bitfield::Element<int, 3, 5>;
+///  Bitfield::set<SignedValue>(Storage, -2);
+///  EXPECT_EQ(Storage, 0b11110101);
+///  //                   ^^^^^
+///  EXPECT_EQ(Bitfield::get<SignedValue>(Storage), -2);
+///
+///  // Ability to efficiently test if a field is non zero.
+///  EXPECT_TRUE(Bitfield::test<Value>(Storage));
+///
+///  // Alter Storage changes value.
+///  Storage = 0;
+///  EXPECT_EQ(Bitfield::get<Bool>(Storage), false);
+///  EXPECT_EQ(Bitfield::get<Suit>(Storage), SuitEnum::CLUBS);
+///  EXPECT_EQ(Bitfield::get<Value>(Storage), 0U);
+///  EXPECT_EQ(Bitfield::get<SignedValue>(Storage), 0);
+///
+///  Storage = 255;
+///  EXPECT_EQ(Bitfield::get<Bool>(Storage), true);
+///  EXPECT_EQ(Bitfield::get<Suit>(Storage), SuitEnum::SPADES);
+///  EXPECT_EQ(Bitfield::get<Value>(Storage), 31U);
+///  EXPECT_EQ(Bitfield::get<SignedValue>(Storage), -1);
+/// \endcode
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_BITFIELDS_H
+#define LLVM_ADT_BITFIELDS_H
+
+#include <cassert>
+#include <climits> // CHAR_BIT
+#include <cstddef> // size_t
+#include <cstdint> // uintXX_t
+#include <limits>  // numeric_limits
+#include <type_traits>
+
+namespace llvm {
+
+namespace details {
+
+// A struct defining useful bit patterns for n-bits integer types.
+template <typename T, unsigned Bits> struct BitPatterns {
+  // Bit patterns are forged using the equivalent `Unsigned` type because of
+  // undefined operations over signed types (e.g. Bitwise shift operators).
+  // Moreover same size casting from unsigned to signed is well defined but not
+  // the other way around.
+  using Unsigned = typename std::make_unsigned<T>::type;
+  static_assert(sizeof(Unsigned) == sizeof(T), "Types must have same size");
+
+  static constexpr unsigned TypeBits = sizeof(Unsigned) * CHAR_BIT;
+  static_assert(TypeBits >= Bits, "n-bit must fit in T");
+
+  // e.g. with TypeBits == 8 and Bits == 6.
+  static constexpr Unsigned AllZeros = Unsigned(0);                  // 00000000
+  static constexpr Unsigned AllOnes = ~Unsigned(0);                  // 11111111
+  static constexpr Unsigned Umin = AllZeros;                         // 00000000
+  static constexpr Unsigned Umax = AllOnes >> (TypeBits - Bits);     // 00111111
+  static constexpr Unsigned SignBitMask = Unsigned(1) << (Bits - 1); // 00100000
+  static constexpr Unsigned Smax = Umax >> 1U;                       // 00011111
+  static constexpr Unsigned Smin = ~Smax;                            // 11100000
+  static constexpr Unsigned SignExtend = Smin << 1U;                 // 11000000
+};
+
+// `Compressor` is used to manipulate the bits of a (possibly signed) integer
+// type so it can be packed and unpacked into a `bits` sized integer,
+// `Compressor` is specialized on signed-ness so no runtime cost is incurred.
+// The `pack` method also checks that the passed in `UserValue` is valid.
+template <typename T, unsigned Bits, bool = std::is_unsigned<T>::value>
+struct Compressor {
+  static_assert(std::is_unsigned<T>::value, "T is unsigned");
+  using BP = BitPatterns<T, Bits>;
+
+  static T pack(T UserValue, T UserMaxValue) {
+    assert(UserValue <= UserMaxValue && "value is too big");
+    assert(UserValue <= BP::Umax && "value is too big");
+    return UserValue;
+  }
+
+  static T unpack(T StorageValue) { return StorageValue; }
+};
+
+template <typename T, unsigned Bits> struct Compressor<T, Bits, false> {
+  static_assert(std::is_signed<T>::value, "T is signed");
+  using BP = BitPatterns<T, Bits>;
+
+  static T pack(T UserValue, T UserMaxValue) {
+    assert(UserValue <= UserMaxValue && "value is too big");
+    assert(UserValue <= T(BP::Smax) && "value is too big");
+    assert(UserValue >= T(BP::Smin) && "value is too small");
+    if (UserValue < 0)
+      UserValue &= ~BP::SignExtend;
+    return UserValue;
+  }
+
+  static T unpack(T StorageValue) {
+    if (StorageValue >= T(BP::SignBitMask))
+      StorageValue |= BP::SignExtend;
+    return StorageValue;
+  }
+};
+
+// Impl is where Bifield description and Storage are put together to interact
+// with values.
+template <typename Bitfield, typename StorageType> struct Impl {
+  static_assert(std::is_unsigned<StorageType>::value,
+                "Storage must be unsigned");
+  using IntegerType = typename Bitfield::IntegerType;
+  using C = Compressor<IntegerType, Bitfield::Bits>;
+  using BP = BitPatterns<StorageType, Bitfield::Bits>;
+
+  static constexpr size_t StorageBits = sizeof(StorageType) * CHAR_BIT;
+  static_assert(Bitfield::FirstBit <= StorageBits, "Data must fit in mask");
+  static_assert(Bitfield::LastBit <= StorageBits, "Data must fit in mask");
+  static constexpr StorageType Mask = BP::Umax << Bitfield::Shift;
+
+  // Checks `UserValue` is within bounds and packs it between `FirstBit` and
+  // `LastBit` of `Packed` leaving the rest unchanged.
+  static void update(StorageType &Packed, IntegerType UserValue) {
+    const StorageType StorageValue = C::pack(UserValue, Bitfield::maxValue);
+    Packed &= ~Mask;
+    Packed |= StorageValue << Bitfield::Shift;
+  }
+
+  // Interprets bits between `FirstBit` and `LastBit` of `Packed` as
+  // an`IntegerType`.
+  static IntegerType extract(StorageType Packed) {
+    const StorageType StorageValue = (Packed & Mask) >> Bitfield::Shift;
+    return C::unpack(StorageValue);
+  }
+
+  // Interprets bits between `FirstBit` and `LastBit` of `Packed` as
+  // an`IntegerType`.
+  static StorageType test(StorageType Packed) { return Packed & Mask; }
+};
+
+// `Bitfield` deals with the following type:
+// - unsigned enums
+// - signed and unsigned integer
+// - `bool`
+// Internally though we only manipulate integer with well defined and consistent
+// semantic, this excludes typed enums and `bool` that are replaced with their
+// unsigned counterparts. The correct type is restored in the public API.
+template <typename T, bool = std::is_enum<T>::value>
+struct ResolveUnderlyingType {
+  using type = typename std::underlying_type<T>::type;
+};
+template <typename T> struct ResolveUnderlyingType<T, false> {
+  using type = T;
+};
+template <> struct ResolveUnderlyingType<bool, false> {
+  // In case sizeof(bool) != 1, replace `void` by an additionnal
+  // std::conditionnal.
+  using type = std::conditional<sizeof(bool) == 1, uint8_t, void>::type;
+};
+
+} // namespace details
+
+/// Holds functions to get, set or test bitfields.
+struct Bitfield {
+
+  /// Describes an element of a Bitfield. This type is then used with
+  /// Bitfield::get \param T, the type of the field once in unpacked form,
+  /// \param Offset, the position of the first bit,
+  /// \param Size, the size of the field,
+  /// \param MaxValue, For enums the maximum enum allowed.
+  template <typename T, unsigned Offset, unsigned Size,
+            T MaxValue = std::is_enum<T>::value
+                             ? T(0) // coupled with static_assert below
+                             : std::numeric_limits<T>::max()>
+  struct Element {
+    using Type = T;
+    using IntegerType = typename details::ResolveUnderlyingType<T>::type;
+    static constexpr unsigned Shift = Offset;
+    static constexpr unsigned Bits = Size;
+    static constexpr unsigned FirstBit = Offset;
+    static constexpr unsigned LastBit = Shift + Bits;
+
+  private:
+    template <typename, typename> friend struct details::Impl;
+
+    static_assert(Bits > 0, "Bits must be non zero");
+    static constexpr size_t TypeBits = sizeof(IntegerType) * CHAR_BIT;
+    static_assert(Bits <= TypeBits, "Bits may not be greater than T size");
+    static_assert(!std::is_enum<T>::value || MaxValue != T(0),
+                  "Enum Bitfields must provide a MaxValue");
+    static_assert(!std::is_enum<T>::value ||
+                      std::is_unsigned<IntegerType>::value,
+                  "Enum must be unsigned");
+    static_assert(std::is_integral<IntegerType>::value &&
+                      std::numeric_limits<IntegerType>::is_integer,
+                  "IntegerType must be an integer type");
+
+    static constexpr IntegerType maxValue = static_cast<IntegerType>(MaxValue);
+  };
+
+  /// Unpacks the field from the `Packed` value.
+  template <typename Bitfield, typename StorageType>
+  static typename Bitfield::Type get(StorageType Packed) {
+    using I = details::Impl<Bitfield, StorageType>;
+    return static_cast<typename Bitfield::Type>(I::extract(Packed));
+  }
+
+  /// Return a non-zero value if the field is non-zero.
+  /// It is more efficient than `getField`.
+  template <typename Bitfield, typename StorageType>
+  static StorageType test(StorageType Packed) {
+    using I = details::Impl<Bitfield, StorageType>;
+    return I::test(Packed);
+  }
+
+  /// Sets the typed value in the provided `Packed` value.
+  /// The method will asserts if the provided value is too big to fit in.
+  template <typename Bitfield, typename StorageType>
+  static void set(StorageType &Packed, typename Bitfield::Type Value) {
+    using I = details::Impl<Bitfield, StorageType>;
+    I::update(Packed, static_cast<typename Bitfield::IntegerType>(Value));
+  }
+
+  /// Returns whether the two bitfields share common bits.
+  template <typename A, typename B> static constexpr bool isOverlapping() {
+    return A::LastBit > B::FirstBit && B::LastBit > A::FirstBit;
+  }
+};
+
+} // namespace llvm
+
+#endif // LLVM_ADT_BITFIELDS_H

llvm/unittests/ADT/BitFieldsTest.cpp

+//===- llvm/unittests/ADT/BitFieldsTest.cpp - BitFields unit tests --------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/Bitfields.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+
+TEST(BitfieldsTest, Example) {
+  uint8_t Storage = 0;
+
+  // Store and retrieve a single bit as bool.
+  using Bool = Bitfield::Element<bool, 0, 1>;
+  Bitfield::set<Bool>(Storage, true);
+  EXPECT_EQ(Storage, 0b00000001);
+  //                          ^
+  EXPECT_EQ(Bitfield::get<Bool>(Storage), true);
+
+  // Store and retrieve a 2 bit typed enum.
+  // Note: enum underlying type must be unsigned.
+  enum class SuitEnum : uint8_t { CLUBS, DIAMONDS, HEARTS, SPADES };
+  // Note: enum maximum value needs to be passed in as last parameter.
+  using Suit = Bitfield::Element<SuitEnum, 1, 2, SuitEnum::SPADES>;
+  Bitfield::set<Suit>(Storage, SuitEnum::HEARTS);
+  EXPECT_EQ(Storage, 0b00000101);
+  //                        ^^
+  EXPECT_EQ(Bitfield::get<Suit>(Storage), SuitEnum::HEARTS);
+
+  // Store and retrieve a 5 bit value as unsigned.
+  using Value = Bitfield::Element<unsigned, 3, 5>;
+  Bitfield::set<Value>(Storage, 10);
+  EXPECT_EQ(Storage, 0b01010101);
+  //                   ^^^^^
+  EXPECT_EQ(Bitfield::get<Value>(Storage), 10U);
+
+  // Interpret the same 5 bit value as signed.
+  using SignedValue = Bitfield::Element<int, 3, 5>;
+  Bitfield::set<SignedValue>(Storage, -2);
+  EXPECT_EQ(Storage, 0b11110101);
+  //                   ^^^^^
+  EXPECT_EQ(Bitfield::get<SignedValue>(Storage), -2);
+
+  // Ability to efficiently test if a field is non zero.
+  EXPECT_TRUE(Bitfield::test<Value>(Storage));
+
+  // Alter Storage changes value.
+  Storage = 0;
+  EXPECT_EQ(Bitfield::get<Bool>(Storage), false);
+  EXPECT_EQ(Bitfield::get<Suit>(Storage), SuitEnum::CLUBS);
+  EXPECT_EQ(Bitfield::get<Value>(Storage), 0U);
+  EXPECT_EQ(Bitfield::get<SignedValue>(Storage), 0);
+
+  Storage = 255;
+  EXPECT_EQ(Bitfield::get<Bool>(Storage), true);
+  EXPECT_EQ(Bitfield::get<Suit>(Storage), SuitEnum::SPADES);
+  EXPECT_EQ(Bitfield::get<Value>(Storage), 31U);
+  EXPECT_EQ(Bitfield::get<SignedValue>(Storage), -1);
+}
+
+TEST(BitfieldsTest, FirstBit) {
+  uint8_t Storage = 0;
+  using FirstBit = Bitfield::Element<bool, 0, 1>;
+  // Set true
+  Bitfield::set<FirstBit>(Storage, true);
+  EXPECT_EQ(Bitfield::get<FirstBit>(Storage), true);
+  EXPECT_EQ(Storage, 0x1ULL);
+  // Set false
+  Bitfield::set<FirstBit>(Storage, false);
+  EXPECT_EQ(Bitfield::get<FirstBit>(Storage), false);
+  EXPECT_EQ(Storage, 0x0ULL);
+}
+
+TEST(BitfieldsTest, SecondBit) {
+  uint8_t Storage = 0;
+  using SecondBit = Bitfield::Element<bool, 1, 1>;
+  // Set true
+  Bitfield::set<SecondBit>(Storage, true);
+  EXPECT_EQ(Bitfield::get<SecondBit>(Storage), true);
+  EXPECT_EQ(Storage, 0x2ULL);
+  // Set false
+  Bitfield::set<SecondBit>(Storage, false);
+  EXPECT_EQ(Bitfield::get<SecondBit>(Storage), false);
+  EXPECT_EQ(Storage, 0x0ULL);
+}
+
+TEST(BitfieldsTest, LastBit) {
+  uint8_t Storage = 0;
+  using LastBit = Bitfield::Element<bool, 7, 1>;
+  // Set true
+  Bitfield::set<LastBit>(Storage, true);
+  EXPECT_EQ(Bitfield::get<LastBit>(Storage), true);
+  EXPECT_EQ(Storage, 0x80ULL);
+  // Set false
+  Bitfield::set<LastBit>(Storage, false);
+  EXPECT_EQ(Bitfield::get<LastBit>(Storage), false);
+  EXPECT_EQ(Storage, 0x0ULL);
+}
+
+TEST(BitfieldsTest, LastBitUint64) {
+  uint64_t Storage = 0;
+  using LastBit = Bitfield::Element<bool, 63, 1>;
+  // Set true
+  Bitfield::set<LastBit>(Storage, true);
+  EXPECT_EQ(Bitfield::get<LastBit>(Storage), true);
+  EXPECT_EQ(Storage, 0x8000000000000000ULL);
+  // Set false
+  Bitfield::set<LastBit>(Storage, false);
+  EXPECT_EQ(Bitfield::get<LastBit>(Storage), false);
+  EXPECT_EQ(Storage, 0x0ULL);
+}
+
+TEST(BitfieldsTest, Enum) {
+  enum Enum : unsigned { Zero = 0, Two = 2, LAST = Two };
+
+  uint8_t Storage = 0;
+  using OrderingField = Bitfield::Element<Enum, 1, 2, LAST>;
+  EXPECT_EQ(Bitfield::get<OrderingField>(Storage), Zero);
+  Bitfield::set<OrderingField>(Storage, Two);
+  EXPECT_EQ(Bitfield::get<OrderingField>(Storage), Two);
+  EXPECT_EQ(Storage, 0b00000100);
+  // value 2 in             ^^
+}
+
+TEST(BitfieldsTest, EnumClass) {
+  enum class Enum : unsigned { Zero = 0, Two = 2, LAST = Two };
+
+  uint8_t Storage = 0;
+  using OrderingField = Bitfield::Element<Enum, 1, 2, Enum::LAST>;
+  EXPECT_EQ(Bitfield::get<OrderingField>(Storage), Enum::Zero);
+  Bitfield::set<OrderingField>(Storage, Enum::Two);
+  EXPECT_EQ(Bitfield::get<OrderingField>(Storage), Enum::Two);
+  EXPECT_EQ(Storage, 0b00000100);
+  // value 2 in             ^^
+}
+
+TEST(BitfieldsTest, OneBitSigned) {
+  uint8_t Storage = 0;
+  using SignedField = Bitfield::Element<int, 1, 1>;
+  EXPECT_EQ(Bitfield::get<SignedField>(Storage), 0);
+  EXPECT_EQ(Storage, 0b00000000);
+  // value 0 in              ^
+  Bitfield::set<SignedField>(Storage, -1);
+  EXPECT_EQ(Bitfield::get<SignedField>(Storage), -1);
+  EXPECT_EQ(Storage, 0b00000010);
+  // value 1 in              ^
+}
+
+TEST(BitfieldsTest, TwoBitSigned) {
+  uint8_t Storage = 0;
+  using SignedField = Bitfield::Element<int, 1, 2>;
+  EXPECT_EQ(Bitfield::get<SignedField>(Storage), 0);
+  EXPECT_EQ(Storage, 0b00000000);
+  // value 0 in             ^^
+  Bitfield::set<SignedField>(Storage, 1);
+  EXPECT_EQ(Bitfield::get<SignedField>(Storage), 1);
+  EXPECT_EQ(Storage, 0b00000010);
+  // value 1 in             ^^
+  Bitfield::set<SignedField>(Storage, -1);
+  EXPECT_EQ(Bitfield::get<SignedField>(Storage), -1);
+  EXPECT_EQ(Storage, 0b00000110);
+  // value -1 in            ^^
+  Bitfield::set<SignedField>(Storage, -2);
+  EXPECT_EQ(Bitfield::get<SignedField>(Storage), -2);
+  EXPECT_EQ(Storage, 0b00000100);
+  // value -2 in            ^^
+}
+
+TEST(BitfieldsTest, isOverlapping) {
+  //    01234567
+  // A: --------
+  // B:    ---
+  // C:  ---
+  // D:     ---
+  using A = Bitfield::Element<unsigned, 0, 8>;
+  using B = Bitfield::Element<unsigned, 3, 3>;
+  using C = Bitfield::Element<unsigned, 1, 3>;
+  using D = Bitfield::Element<unsigned, 4, 3>;
+  EXPECT_TRUE((Bitfield::isOverlapping<A, B>()));
+  EXPECT_TRUE((Bitfield::isOverlapping<A, C>()));
+  EXPECT_TRUE((Bitfield::isOverlapping<A, B>()));
+  EXPECT_TRUE((Bitfield::isOverlapping<A, D>()));
+
+  EXPECT_TRUE((Bitfield::isOverlapping<B, C>()));
+  EXPECT_TRUE((Bitfield::isOverlapping<B, D>()));
+  EXPECT_FALSE((Bitfield::isOverlapping<C, D>()));
+}
+
+TEST(BitfieldsTest, FullUint64) {
+  uint64_t Storage = 0;
+  using Value = Bitfield::Element<uint64_t, 0, 64>;
+  Bitfield::set<Value>(Storage, -1ULL);
+  EXPECT_EQ(Bitfield::get<Value>(Storage), -1ULL);
+  Bitfield::set<Value>(Storage, 0ULL);
+  EXPECT_EQ(Bitfield::get<Value>(Storage), 0ULL);
+}
+
+TEST(BitfieldsTest, FullInt64) {
+  uint64_t Storage = 0;
+  using Value = Bitfield::Element<int64_t, 0, 64>;
+  Bitfield::set<Value>(Storage, -1);
+  EXPECT_EQ(Bitfield::get<Value>(Storage), -1);
+  Bitfield::set<Value>(Storage, 0);
+  EXPECT_EQ(Bitfield::get<Value>(Storage), 0);
+}
+
+#ifdef EXPECT_DEBUG_DEATH
+
+TEST(BitfieldsTest, ValueTooBigBool) {
+  uint64_t Storage = 0;
+  using A = Bitfield::Element<unsigned, 0, 1>;
+  Bitfield::set<A>(Storage, true);
+  Bitfield::set<A>(Storage, false);
+  EXPECT_DEBUG_DEATH(Bitfield::set<A>(Storage, 2), "value is too big");
+}
+
+TEST(BitfieldsTest, ValueTooBigInt) {
+  uint64_t Storage = 0;
+  using A = Bitfield::Element<unsigned, 0, 2>;
+  Bitfield::set<A>(Storage, 3);
+  EXPECT_DEBUG_DEATH(Bitfield::set<A>(Storage, 4), "value is too big");
+  EXPECT_DEBUG_DEATH(Bitfield::set<A>(Storage, -1), "value is too big");
+}
+
+TEST(BitfieldsTest, ValueTooBigBounded) {
+  uint8_t Storage = 0;
+  using A = Bitfield::Element<int, 1, 2>;
+  Bitfield::set<A>(Storage, 1);
+  Bitfield::set<A>(Storage, 0);
+  Bitfield::set<A>(Storage, -1);
+  Bitfield::set<A>(Storage, -2);
+  EXPECT_DEBUG_DEATH(Bitfield::set<A>(Storage, 2), "value is too big");
+  EXPECT_DEBUG_DEATH(Bitfield::set<A>(Storage, -3), "value is too small");
+}
+
+#endif
+
+} // namespace

llvm/unittests/ADT/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 add_llvm_unittest(ADTTests
   AnyTest.cpp
   APFloatTest.cpp
   APIntTest.cpp
   APSIntTest.cpp
   ArrayRefTest.cpp
+  BitFieldsTest.cpp
   BitmaskEnumTest.cpp
   BitVectorTest.cpp
   BreadthFirstIteratorTest.cpp
   BumpPtrListTest.cpp
   CoalescingBitVectorTest.cpp
   DAGDeltaAlgorithmTest.cpp
   DeltaAlgorithmTest.cpp
   DenseMapTest.cpp