[ADT] Add Bitfield utilities - design #1

[gchatelet]

Summary

Context: There are places in LLVM where we need to pack typed fields into opaque values.
For instance, the XXXInst classes in llvm/include/llvm/IR/Instructions.h that extract informations from Value::SubclassData via getSubclassDataFromInstruction().
The bit twiddling is done manually: this impairs readability and prevent consistent handling of out of range values (e.g. Instructions.h)
More importantly, the bit pattern is scattered throughout the implementation making it hard to pack additionnal fields or check for overlapping bits.

Design: The Bitfield structs are to be declared together so it is clear which bits are used or not.
The code is designed with simplicity in mind, hence a few limitations:

• Storage is limited to a single integer that cannot be bigger than uint64_t,
• Values and storage have to be unsigned or enum (enum class works), (edit: the new design allows signed integer but not signed enums)
• Is is not possible to store a full uint64_t at once i.e. Bitfield<uint64_t, 0, 64> will fail, (edit: the new design allows this)
• There are no automatic detection of overlapping fields (packed bitfield declaration should help though),
• The interface is C like so storage needs to be passed in every time (code is simpler and lifetime considerations more obvious)

Feedback welcome

[courbet]

Can you create an example patch rebased on this to show how this changes the bit twiddling code for an example instruction ? Maybe this could go through an RFC ? I'm personally, this would make the code much cleaner.

The only thing that this would not handle is if an instruction does its bit twidling based on some dynamic property, e.g. SubclassData & 1 << (dynamic_value) . But your proposal does not have to be used for that case.

[gchatelet]

In D81580#2086998, @courbet wrote:

Can you create an example patch rebased on this to show how this changes the bit twiddling code for an example instruction ?

Here it is D81662 (edit - this was the wrong patch)
I've added comments to highlight dubious logic.

Maybe this could go through an RFC ?

You're right. I'll send an email, thank you.

The only thing that this would not handle is if an instruction does its bit twidling based on some dynamic property, e.g. SubclassData & 1 << (dynamic_value) . But your proposal does not have to be used for that case.

Yes indeed, this code is for compile time bit fields.

[gchatelet]

• Update implementation to reflect changes D81662

[gchatelet]

• Fix style

[gchatelet]

• Fix various typos

[courbet]

I have not seen any concerns raised on the mailing lists after your proposal. Let's give it a couple more days before submitting.

[kpdev42]

llvm/include/llvm/ADT/Bitfields.h

91

Maybe it is worth to use std::numeric_limits<T>::digits here?
Like this:

static constexpr auto TypeBits = std::numeric_limits<Unsigned>::digits;

then it will be possible to remove #include <climits> // CHAR_BIT

[gchatelet]

llvm/include/llvm/ADT/Bitfields.h

91

Thx for the suggestion. Unfortunately I also use CHAR_BIT elsewhere in the file and cppreference.com says:

For integer types, this is the number of bits not counting the sign bit and the padding bits (if any)

• For Bitfield::TypeBits the type may be signed,
• For Bitfield::Impl::StorageBits I need the full storage space so padding bit must be accounted for.

With this in mind it seems to me that it's still beneficial to keep the climits include.

[gchatelet]

• Regular enums under MSVC are always considered signed

[gchatelet]

@serge-sans-paille the main review is here. I intend to submit this one first, then D81662.

[serge-sans-paille]

llvm/unittests/ADT/BitFieldsTest.cpp

22

Would that make sense to use the following syntax instead of the setField method ?

Bitfield<bool, 0, 1>(Storage) = true;

This would also have the pro of not providing a relatively generic name setField in the llvm namespace.

[gchatelet]

llvm/unittests/ADT/BitFieldsTest.cpp

22

Are you suggesting the following API changes?

// testField becomes cast to bool operator
if(Bitfield<bool, 0, 1>::testField(Storage))
=>
if(Bitfield<bool, 0, 1>(Storage))

// getField becomes cast to UserType
auto Value = Bitfield<bool, 0, 1>::getField(Storage);
=>
auto Value = Bitfield<bool, 0, 1>(Storage);

// setField becomes returning a UserType assignable object
Bitfield<bool, 0, 1>::setField(Storage, Value);
=>
Bitfield<bool, 0, 1>(Storage) = Value;

Implementation wise this is more complex:

• we need to create one or two objects (one for test/get, and two for set),
• for the setter we need to return a type with a reference to Storage so we have to consider Storage lifetime,
• the returned object must not be copyable nor movable to prevent passing it to functions,
• cast operators may introduce type promotion so it's harder to understand what's going on,
• object may introduce indirection that prevent the compiler from generating clean code.

@courbet what do you think?

[courbet]

llvm/unittests/ADT/BitFieldsTest.cpp

22

No strong opinion. Just make sure that the wrapper object for set is non movable and copyable for lifetime issues.

[gchatelet]

llvm/unittests/ADT/BitFieldsTest.cpp

22

I've created an alternative design in D81662.
I couldn't get the test function as a cast operator because it would conflict with the cast to UserType when UserType is bool.
It is not possible to use enable_if to disable the offending function because SFINAE only works for deduced template arguments, and nothing is to be deduced in this case (see this stackoverflow).

Let me know what you think.

[gchatelet]

llvm/unittests/ADT/BitFieldsTest.cpp

22

Sorry I mixed up the patches. the alternative design is here D82058

[gchatelet]

rebase

[gchatelet]

Fix style

[gchatelet]

Revert bad patch

[gchatelet]

Dropped in favor of D82454

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.
+///
+//===----------------------------------------------------------------------===//
+
+#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>
+
+/// Helpers to pack / unpack typed bitfields into an unsigned integer.
+/// e.g.
+///
+///  uint8_t Storage = 0;
+///
+///  // Store and retrieve a single bit as bool.
+///  using Bool = Bitfield<bool, 0, 1>;
+///  setField<Bool>(Storage, true);
+///  EXPECT_EQ(Storage, 0b00000001);
+///  //                          ^
+///  EXPECT_EQ(getField<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.
+///  using Suit = Bitfield<SuitEnum, 1, 2, SuitEnum::SPADES>;
+///  setField<Suit>(Storage, SuitEnum::HEARTS);
+///  EXPECT_EQ(Storage, 0b00000101);
+///  //                        ^^
+///  EXPECT_EQ(getField<Suit>(Storage), SuitEnum::HEARTS);
+///
+///  // Store and retrieve a 5 bit value as unsigned.
+///  using Value = Bitfield<unsigned, 3, 5>;
+///  setField<Value>(Storage, 10);
+///  EXPECT_EQ(Storage, 0b01010101);
+///  //                   ^^^^^
+///  EXPECT_EQ(getField<Value>(Storage), 10U);
+///
+///  // Interpret the same 5 bit value as signed.
+///  using SignedValue = Bitfield<int, 3, 5>;
+///  setField<SignedValue>(Storage, -2);
+///  EXPECT_EQ(Storage, 0b11110101);
+///  //                   ^^^^^
+///  EXPECT_EQ(getField<SignedValue>(Storage), -2);
+///
+///  // Ability to efficiently test if a field is non zero.
+///  EXPECT_TRUE(testField<Value>(Storage) != 0U);
+///
+///  // Alter Storage changes value.
+///  Storage = 0;
+///  EXPECT_EQ(getField<Bool>(Storage), false);
+///  EXPECT_EQ(getField<Suit>(Storage), SuitEnum::CLUBS);
+///  EXPECT_EQ(getField<Value>(Storage), 0U);
+///  EXPECT_EQ(getField<SignedValue>(Storage), 0);
+///
+///  Storage = 255;
+///  EXPECT_EQ(getField<Bool>(Storage), true);
+///  EXPECT_EQ(getField<Suit>(Storage), SuitEnum::SPADES);
+///  EXPECT_EQ(getField<Value>(Storage), 31U);
+///  EXPECT_EQ(getField<SignedValue>(Storage), -1);
+
+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;
+  }
+};
+
+/// `BitfieldProperties` stores important properties about the Bitfield.
+/// It only deals with proper integer types. The conversion from/to enum/bool
+/// are done in the public API outside of this template.
+template <typename T, unsigned Offset, unsigned Bits,
+          T MaxValue = std::numeric_limits<T>::max(),
+          T MinValue = std::numeric_limits<T>::min()>
+struct BitfieldProperties {
+  using IntegerType = T;
+  static_assert(std::is_integral<T>::value &&
+                    std::numeric_limits<T>::is_integer,
+                "T must be an integer type");
+
+  static constexpr size_t TypeBits = sizeof(IntegerType) * CHAR_BIT;
+  static constexpr unsigned FirstBit = Offset;
+  static constexpr unsigned LastBit = Offset + Bits;
+
+  static_assert(Bits > 0, "Bits must be non zero");
+  static_assert(Bits <= TypeBits, "Bits may not be greater than T size");
+
+  /// Impl is where Bifield description and storage are put together to interact
+  /// with values.
+  template <typename StorageType> struct Impl {
+    static_assert(std::is_unsigned<StorageType>::value,
+                  "Storage must be unsigned");
+    using C = Compressor<IntegerType, Bits>;
+    using BP = BitPatterns<StorageType, Bits>;
+
+    static constexpr size_t StorageBits = sizeof(StorageType) * CHAR_BIT;
+    static_assert(FirstBit <= StorageBits, "Data must fit in mask");
+    static_assert(LastBit <= StorageBits, "Data must fit in mask");
+    static constexpr StorageType Mask = BP::Umax << Offset;
+
+    /// 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, MaxValue);
+      Packed &= ~Mask;
+      Packed |= StorageValue << Offset;
+    }
+
+    /// Interprets bits between `FirstBit` and `LastBit` of `Packed` as an
+    /// `IntegerType`.
+    static IntegerType extract(StorageType Packed) {
+      const StorageType StorageValue = (Packed & Mask) >> Offset;
+      return C::unpack(StorageValue);
+    }
+  };
+};
+
+/// `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
+
+/// A struct to hold the bitfield informations.
+/// \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 Bitfield {
+  using Type = T;
+  using IntegerType = typename details::ResolveUnderlyingType<T>::type;
+  using Properties =
+      typename details::BitfieldProperties<IntegerType, Offset, Size,
+                                           static_cast<IntegerType>(MaxValue)>;
+
+  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");
+};
+
+/// Returns whether the two bitfields share common bits.
+template <typename A, typename B> static constexpr bool isOverlapping() {
+  using PA = typename A::Properties;
+  using PB = typename B::Properties;
+  return PA::LastBit > PB::FirstBit && PB::LastBit > PA::FirstBit;
+}
+
+/// Unpacks the field from the `Packed` value.
+template <typename Bitfield, typename StorageType>
+static typename Bitfield::Type getField(StorageType Packed) {
+  using Impl = typename Bitfield::Properties::template Impl<StorageType>;
+  return static_cast<typename Bitfield::Type>(Impl::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 testField(StorageType Packed) {
+  using Impl = typename Bitfield::Properties::template Impl<StorageType>;
+  return Packed & Impl::Mask;
+}
+
+/// 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 setField(StorageType &Packed, typename Bitfield::Type Value) {
+  using Impl = typename Bitfield::Properties::template Impl<StorageType>;
+  Impl::update(Packed, static_cast<typename Bitfield::IntegerType>(Value));
+}
+
+} // 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<bool, 0, 1>;
+  setField<Bool>(Storage, true);
+  EXPECT_EQ(Storage, 0b00000001);
+  //                          ^
+  EXPECT_EQ(getField<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.
+  using Suit = Bitfield<SuitEnum, 1, 2, SuitEnum::SPADES>;
+  setField<Suit>(Storage, SuitEnum::HEARTS);
+  EXPECT_EQ(Storage, 0b00000101);
+  //                        ^^
+  EXPECT_EQ(getField<Suit>(Storage), SuitEnum::HEARTS);
+
+  // Store and retrieve a 5 bit value as unsigned.
+  using Value = Bitfield<unsigned, 3, 5>;
+  setField<Value>(Storage, 10);
+  EXPECT_EQ(Storage, 0b01010101);
+  //                   ^^^^^
+  EXPECT_EQ(getField<Value>(Storage), 10U);
+
+  // Interpret the same 5 bit value as signed.
+  using SignedValue = Bitfield<int, 3, 5>;
+  setField<SignedValue>(Storage, -2);
+  EXPECT_EQ(Storage, 0b11110101);
+  //                   ^^^^^
+  EXPECT_EQ(getField<SignedValue>(Storage), -2);
+
+  // Ability to efficiently test if a field is non zero.
+  EXPECT_TRUE(testField<Value>(Storage) != 0U);
+
+  // Alter Storage changes value.
+  Storage = 0;
+  EXPECT_EQ(getField<Bool>(Storage), false);
+  EXPECT_EQ(getField<Suit>(Storage), SuitEnum::CLUBS);
+  EXPECT_EQ(getField<Value>(Storage), 0U);
+  EXPECT_EQ(getField<SignedValue>(Storage), 0);
+
+  Storage = 255;
+  EXPECT_EQ(getField<Bool>(Storage), true);
+  EXPECT_EQ(getField<Suit>(Storage), SuitEnum::SPADES);
+  EXPECT_EQ(getField<Value>(Storage), 31U);
+  EXPECT_EQ(getField<SignedValue>(Storage), -1);
+}
+
+TEST(BitfieldsTest, FirstBit) {
+  uint8_t Storage = 0;
+  using FirstBit = Bitfield<bool, 0, 1>;
+  // Set true
+  setField<FirstBit>(Storage, true);
+  EXPECT_EQ(getField<FirstBit>(Storage), true);
+  EXPECT_EQ(Storage, 0x1ULL);
+  // Set false
+  setField<FirstBit>(Storage, false);
+  EXPECT_EQ(getField<FirstBit>(Storage), false);
+  EXPECT_EQ(Storage, 0x0ULL);
+}
+
+TEST(BitfieldsTest, SecondBit) {
+  uint8_t Storage = 0;
+  using SecondBit = Bitfield<bool, 1, 1>;
+  // Set true
+  setField<SecondBit>(Storage, true);
+  EXPECT_EQ(getField<SecondBit>(Storage), true);
+  EXPECT_EQ(Storage, 0x2ULL);
+  // Set false
+  setField<SecondBit>(Storage, false);
+  EXPECT_EQ(getField<SecondBit>(Storage), false);
+  EXPECT_EQ(Storage, 0x0ULL);
+}
+
+TEST(BitfieldsTest, LastBit) {
+  uint8_t Storage = 0;
+  using LastBit = Bitfield<bool, 7, 1>;
+  // Set true
+  setField<LastBit>(Storage, true);
+  EXPECT_EQ(getField<LastBit>(Storage), true);
+  EXPECT_EQ(Storage, 0x80ULL);
+  // Set false
+  setField<LastBit>(Storage, false);
+  EXPECT_EQ(getField<LastBit>(Storage), false);
+  EXPECT_EQ(Storage, 0x0ULL);
+}
+
+TEST(BitfieldsTest, LastBitUint64) {
+  uint64_t Storage = 0;
+  using LastBit = Bitfield<bool, 63, 1>;
+  // Set true
+  setField<LastBit>(Storage, true);
+  EXPECT_EQ(getField<LastBit>(Storage), true);
+  EXPECT_EQ(Storage, 0x8000000000000000ULL);
+  // Set false
+  setField<LastBit>(Storage, false);
+  EXPECT_EQ(getField<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<Enum, 1, 2, LAST>;
+  EXPECT_EQ(getField<OrderingField>(Storage), Zero);
+  setField<OrderingField>(Storage, Two);
+  EXPECT_EQ(getField<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<Enum, 1, 2, Enum::LAST>;
+  EXPECT_EQ(getField<OrderingField>(Storage), Enum::Zero);
+  setField<OrderingField>(Storage, Enum::Two);
+  EXPECT_EQ(getField<OrderingField>(Storage), Enum::Two);
+  EXPECT_EQ(Storage, 0b00000100);
+  // value 2 in             ^^
+}
+
+TEST(BitfieldsTest, OneBitSigned) {
+  uint8_t Storage = 0;
+  using SignedField = Bitfield<int, 1, 1>;
+  EXPECT_EQ(getField<SignedField>(Storage), 0);
+  EXPECT_EQ(Storage, 0b00000000);
+  // value 0 in              ^
+  setField<SignedField>(Storage, -1);
+  EXPECT_EQ(getField<SignedField>(Storage), -1);
+  EXPECT_EQ(Storage, 0b00000010);
+  // value 1 in              ^
+}
+
+TEST(BitfieldsTest, TwoBitSigned) {
+  uint8_t Storage = 0;
+  using SignedField = Bitfield<int, 1, 2>;
+  EXPECT_EQ(getField<SignedField>(Storage), 0);
+  EXPECT_EQ(Storage, 0b00000000);
+  // value 0 in             ^^
+  setField<SignedField>(Storage, 1);
+  EXPECT_EQ(getField<SignedField>(Storage), 1);
+  EXPECT_EQ(Storage, 0b00000010);
+  // value 1 in             ^^
+  setField<SignedField>(Storage, -1);
+  EXPECT_EQ(getField<SignedField>(Storage), -1);
+  EXPECT_EQ(Storage, 0b00000110);
+  // value -1 in            ^^
+  setField<SignedField>(Storage, -2);
+  EXPECT_EQ(getField<SignedField>(Storage), -2);
+  EXPECT_EQ(Storage, 0b00000100);
+  // value -2 in            ^^
+}
+
+TEST(BitfieldsTest, isOverlapping) {
+  //    01234567
+  // A: --------
+  // B:    ---
+  // C:  ---
+  // D:     ---
+  using A = Bitfield<unsigned, 0, 8>;
+  using B = Bitfield<unsigned, 3, 3>;
+  using C = Bitfield<unsigned, 1, 3>;
+  using D = Bitfield<unsigned, 4, 3>;
+  EXPECT_TRUE((isOverlapping<A, B>()));
+  EXPECT_TRUE((isOverlapping<A, C>()));
+  EXPECT_TRUE((isOverlapping<A, B>()));
+  EXPECT_TRUE((isOverlapping<A, D>()));
+
+  EXPECT_TRUE((isOverlapping<B, C>()));
+  EXPECT_TRUE((isOverlapping<B, D>()));
+  EXPECT_FALSE((isOverlapping<C, D>()));
+}
+
+TEST(BitfieldsTest, FullUint64) {
+  uint64_t Storage = 0;
+  using Value = Bitfield<uint64_t, 0, 64>;
+  setField<Value>(Storage, -1ULL);
+  EXPECT_EQ(getField<Value>(Storage), -1ULL);
+  setField<Value>(Storage, 0ULL);
+  EXPECT_EQ(getField<Value>(Storage), 0ULL);
+}
+
+TEST(BitfieldsTest, FullInt64) {
+  uint64_t Storage = 0;
+  using Value = Bitfield<int64_t, 0, 64>;
+  setField<Value>(Storage, -1);
+  EXPECT_EQ(getField<Value>(Storage), -1);
+  setField<Value>(Storage, 0);
+  EXPECT_EQ(getField<Value>(Storage), 0);
+}
+
+#ifdef EXPECT_DEBUG_DEATH
+
+TEST(BitfieldsTest, ValueTooBigBool) {
+  uint64_t Storage = 0;
+  using A = Bitfield<unsigned, 0, 1>;
+  setField<A>(Storage, true);
+  setField<A>(Storage, false);
+  EXPECT_DEBUG_DEATH(setField<A>(Storage, 2), "value is too big");
+}
+
+TEST(BitfieldsTest, ValueTooBigInt) {
+  uint64_t Storage = 0;
+  using A = Bitfield<unsigned, 0, 2>;
+  setField<A>(Storage, 3);
+  EXPECT_DEBUG_DEATH(setField<A>(Storage, 4), "value is too big");
+  EXPECT_DEBUG_DEATH(setField<A>(Storage, -1), "value is too big");
+}
+
+TEST(BitfieldsTest, ValueTooBigBounded) {
+  uint8_t Storage = 0;
+  using A = Bitfield<int, 1, 2>;
+  setField<A>(Storage, 1);
+  setField<A>(Storage, 0);
+  setField<A>(Storage, -1);
+  setField<A>(Storage, -2);
+  EXPECT_DEBUG_DEATH(setField<A>(Storage, 2), "value is too big");
+  EXPECT_DEBUG_DEATH(setField<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