LLVM  17.0.0git
Bitfields.h
Go to the documentation of this file.
1 //===-- llvm/ADT/Bitfield.h - Get and Set bits in an integer ---*- C++ -*--===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 ///
9 /// \file
10 /// This file implements methods to test, set and extract typed bits from packed
11 /// unsigned integers.
12 ///
13 /// Why not C++ bitfields?
14 /// ----------------------
15 /// C++ bitfields do not offer control over the bit layout nor consistent
16 /// behavior when it comes to out of range values.
17 /// For instance, the layout is implementation defined and adjacent bits may be
18 /// packed together but are not required to. This is problematic when storage is
19 /// sparse and data must be stored in a particular integer type.
20 ///
21 /// The methods provided in this file ensure precise control over the
22 /// layout/storage as well as protection against out of range values.
23 ///
24 /// Usage example
25 /// -------------
26 /// \code{.cpp}
27 /// uint8_t Storage = 0;
28 ///
29 /// // Store and retrieve a single bit as bool.
30 /// using Bool = Bitfield::Element<bool, 0, 1>;
31 /// Bitfield::set<Bool>(Storage, true);
32 /// EXPECT_EQ(Storage, 0b00000001);
33 /// // ^
34 /// EXPECT_EQ(Bitfield::get<Bool>(Storage), true);
35 ///
36 /// // Store and retrieve a 2 bit typed enum.
37 /// // Note: enum underlying type must be unsigned.
38 /// enum class SuitEnum : uint8_t { CLUBS, DIAMONDS, HEARTS, SPADES };
39 /// // Note: enum maximum value needs to be passed in as last parameter.
40 /// using Suit = Bitfield::Element<SuitEnum, 1, 2, SuitEnum::SPADES>;
41 /// Bitfield::set<Suit>(Storage, SuitEnum::HEARTS);
42 /// EXPECT_EQ(Storage, 0b00000101);
43 /// // ^^
44 /// EXPECT_EQ(Bitfield::get<Suit>(Storage), SuitEnum::HEARTS);
45 ///
46 /// // Store and retrieve a 5 bit value as unsigned.
47 /// using Value = Bitfield::Element<unsigned, 3, 5>;
48 /// Bitfield::set<Value>(Storage, 10);
49 /// EXPECT_EQ(Storage, 0b01010101);
50 /// // ^^^^^
51 /// EXPECT_EQ(Bitfield::get<Value>(Storage), 10U);
52 ///
53 /// // Interpret the same 5 bit value as signed.
54 /// using SignedValue = Bitfield::Element<int, 3, 5>;
55 /// Bitfield::set<SignedValue>(Storage, -2);
56 /// EXPECT_EQ(Storage, 0b11110101);
57 /// // ^^^^^
58 /// EXPECT_EQ(Bitfield::get<SignedValue>(Storage), -2);
59 ///
60 /// // Ability to efficiently test if a field is non zero.
61 /// EXPECT_TRUE(Bitfield::test<Value>(Storage));
62 ///
63 /// // Alter Storage changes value.
64 /// Storage = 0;
65 /// EXPECT_EQ(Bitfield::get<Bool>(Storage), false);
66 /// EXPECT_EQ(Bitfield::get<Suit>(Storage), SuitEnum::CLUBS);
67 /// EXPECT_EQ(Bitfield::get<Value>(Storage), 0U);
68 /// EXPECT_EQ(Bitfield::get<SignedValue>(Storage), 0);
69 ///
70 /// Storage = 255;
71 /// EXPECT_EQ(Bitfield::get<Bool>(Storage), true);
72 /// EXPECT_EQ(Bitfield::get<Suit>(Storage), SuitEnum::SPADES);
73 /// EXPECT_EQ(Bitfield::get<Value>(Storage), 31U);
74 /// EXPECT_EQ(Bitfield::get<SignedValue>(Storage), -1);
75 /// \endcode
76 ///
77 //===----------------------------------------------------------------------===//
78 
79 #ifndef LLVM_ADT_BITFIELDS_H
80 #define LLVM_ADT_BITFIELDS_H
81 
82 #include <cassert>
83 #include <climits> // CHAR_BIT
84 #include <cstddef> // size_t
85 #include <cstdint> // uintXX_t
86 #include <limits> // numeric_limits
87 #include <type_traits>
88 
89 namespace llvm {
90 
91 namespace bitfields_details {
92 
93 /// A struct defining useful bit patterns for n-bits integer types.
94 template <typename T, unsigned Bits> struct BitPatterns {
95  /// Bit patterns are forged using the equivalent `Unsigned` type because of
96  /// undefined operations over signed types (e.g. Bitwise shift operators).
97  /// Moreover same size casting from unsigned to signed is well defined but not
98  /// the other way around.
99  using Unsigned = std::make_unsigned_t<T>;
100  static_assert(sizeof(Unsigned) == sizeof(T), "Types must have same size");
101 
102  static constexpr unsigned TypeBits = sizeof(Unsigned) * CHAR_BIT;
103  static_assert(TypeBits >= Bits, "n-bit must fit in T");
104 
105  /// e.g. with TypeBits == 8 and Bits == 6.
106  static constexpr Unsigned AllZeros = Unsigned(0); // 00000000
107  static constexpr Unsigned AllOnes = ~Unsigned(0); // 11111111
108  static constexpr Unsigned Umin = AllZeros; // 00000000
109  static constexpr Unsigned Umax = AllOnes >> (TypeBits - Bits); // 00111111
110  static constexpr Unsigned SignBitMask = Unsigned(1) << (Bits - 1); // 00100000
111  static constexpr Unsigned Smax = Umax >> 1U; // 00011111
112  static constexpr Unsigned Smin = ~Smax; // 11100000
113  static constexpr Unsigned SignExtend = Unsigned(Smin << 1U); // 11000000
114 };
115 
116 /// `Compressor` is used to manipulate the bits of a (possibly signed) integer
117 /// type so it can be packed and unpacked into a `bits` sized integer,
118 /// `Compressor` is specialized on signed-ness so no runtime cost is incurred.
119 /// The `pack` method also checks that the passed in `UserValue` is valid.
120 template <typename T, unsigned Bits, bool = std::is_unsigned<T>::value>
121 struct Compressor {
122  static_assert(std::is_unsigned<T>::value, "T must be unsigned");
124 
125  static T pack(T UserValue, T UserMaxValue) {
126  assert(UserValue <= UserMaxValue && "value is too big");
127  assert(UserValue <= BP::Umax && "value is too big");
128  return UserValue;
129  }
130 
131  static T unpack(T StorageValue) { return StorageValue; }
132 };
133 
134 template <typename T, unsigned Bits> struct Compressor<T, Bits, false> {
135  static_assert(std::is_signed<T>::value, "T must be signed");
137 
138  static T pack(T UserValue, T UserMaxValue) {
139  assert(UserValue <= UserMaxValue && "value is too big");
140  assert(UserValue <= T(BP::Smax) && "value is too big");
141  assert(UserValue >= T(BP::Smin) && "value is too small");
142  if (UserValue < 0)
143  UserValue &= ~BP::SignExtend;
144  return UserValue;
145  }
146 
147  static T unpack(T StorageValue) {
148  if (StorageValue >= T(BP::SignBitMask))
149  StorageValue |= BP::SignExtend;
150  return StorageValue;
151  }
152 };
153 
154 /// Impl is where Bifield description and Storage are put together to interact
155 /// with values.
156 template <typename Bitfield, typename StorageType> struct Impl {
157  static_assert(std::is_unsigned<StorageType>::value,
158  "Storage must be unsigned");
159  using IntegerType = typename Bitfield::IntegerType;
162 
163  static constexpr size_t StorageBits = sizeof(StorageType) * CHAR_BIT;
164  static_assert(Bitfield::FirstBit <= StorageBits, "Data must fit in mask");
165  static_assert(Bitfield::LastBit <= StorageBits, "Data must fit in mask");
166  static constexpr StorageType Mask = BP::Umax << Bitfield::Shift;
167 
168  /// Checks `UserValue` is within bounds and packs it between `FirstBit` and
169  /// `LastBit` of `Packed` leaving the rest unchanged.
170  static void update(StorageType &Packed, IntegerType UserValue) {
171  const StorageType StorageValue = C::pack(UserValue, Bitfield::UserMaxValue);
172  Packed &= ~Mask;
173  Packed |= StorageValue << Bitfield::Shift;
174  }
175 
176  /// Interprets bits between `FirstBit` and `LastBit` of `Packed` as
177  /// an`IntegerType`.
178  static IntegerType extract(StorageType Packed) {
179  const StorageType StorageValue = (Packed & Mask) >> Bitfield::Shift;
180  return C::unpack(StorageValue);
181  }
182 
183  /// Interprets bits between `FirstBit` and `LastBit` of `Packed` as
184  /// an`IntegerType`.
185  static StorageType test(StorageType Packed) { return Packed & Mask; }
186 };
187 
188 /// `Bitfield` deals with the following type:
189 /// - unsigned enums
190 /// - signed and unsigned integer
191 /// - `bool`
192 /// Internally though we only manipulate integer with well defined and
193 /// consistent semantics, this excludes typed enums and `bool` that are replaced
194 /// with their unsigned counterparts. The correct type is restored in the public
195 /// API.
196 template <typename T, bool = std::is_enum<T>::value>
198  using type = std::underlying_type_t<T>;
199 };
200 template <typename T> struct ResolveUnderlyingType<T, false> {
201  using type = T;
202 };
203 template <> struct ResolveUnderlyingType<bool, false> {
204  /// In case sizeof(bool) != 1, replace `void` by an additionnal
205  /// std::conditional.
206  using type = std::conditional_t<sizeof(bool) == 1, uint8_t, void>;
207 };
208 
209 } // namespace bitfields_details
210 
211 /// Holds functions to get, set or test bitfields.
212 struct Bitfield {
213  /// Describes an element of a Bitfield. This type is then used with the
214  /// Bitfield static member functions.
215  /// \tparam T The type of the field once in unpacked form.
216  /// \tparam Offset The position of the first bit.
217  /// \tparam Size The size of the field.
218  /// \tparam MaxValue For enums the maximum enum allowed.
219  template <typename T, unsigned Offset, unsigned Size,
220  T MaxValue = std::is_enum<T>::value
221  ? T(0) // coupled with static_assert below
223  struct Element {
224  using Type = T;
225  using IntegerType =
227  static constexpr unsigned Shift = Offset;
228  static constexpr unsigned Bits = Size;
229  static constexpr unsigned FirstBit = Offset;
230  static constexpr unsigned LastBit = Shift + Bits - 1;
231  static constexpr unsigned NextBit = Shift + Bits;
232 
233  private:
234  template <typename, typename> friend struct bitfields_details::Impl;
235 
236  static_assert(Bits > 0, "Bits must be non zero");
237  static constexpr size_t TypeBits = sizeof(IntegerType) * CHAR_BIT;
238  static_assert(Bits <= TypeBits, "Bits may not be greater than T size");
239  static_assert(!std::is_enum<T>::value || MaxValue != T(0),
240  "Enum Bitfields must provide a MaxValue");
241  static_assert(!std::is_enum<T>::value ||
242  std::is_unsigned<IntegerType>::value,
243  "Enum must be unsigned");
244  static_assert(std::is_integral<IntegerType>::value &&
245  std::numeric_limits<IntegerType>::is_integer,
246  "IntegerType must be an integer type");
247 
248  static constexpr IntegerType UserMaxValue =
249  static_cast<IntegerType>(MaxValue);
250  };
251 
252  /// Unpacks the field from the `Packed` value.
253  template <typename Bitfield, typename StorageType>
254  static typename Bitfield::Type get(StorageType Packed) {
256  return static_cast<typename Bitfield::Type>(I::extract(Packed));
257  }
258 
259  /// Return a non-zero value if the field is non-zero.
260  /// It is more efficient than `getField`.
261  template <typename Bitfield, typename StorageType>
262  static StorageType test(StorageType Packed) {
264  return I::test(Packed);
265  }
266 
267  /// Sets the typed value in the provided `Packed` value.
268  /// The method will asserts if the provided value is too big to fit in.
269  template <typename Bitfield, typename StorageType>
270  static void set(StorageType &Packed, typename Bitfield::Type Value) {
272  I::update(Packed, static_cast<typename Bitfield::IntegerType>(Value));
273  }
274 
275  /// Returns whether the two bitfields share common bits.
276  template <typename A, typename B> static constexpr bool isOverlapping() {
277  return A::LastBit >= B::FirstBit && B::LastBit >= A::FirstBit;
278  }
279 
280  template <typename A> static constexpr bool areContiguous() { return true; }
281  template <typename A, typename B, typename... Others>
282  static constexpr bool areContiguous() {
283  return A::NextBit == B::FirstBit && areContiguous<B, Others...>();
284  }
285 };
286 
287 } // namespace llvm
288 
289 #endif // LLVM_ADT_BITFIELDS_H
llvm::Bitfield::Element::LastBit
static constexpr unsigned LastBit
Definition: Bitfields.h:230
llvm::bitfields_details::Compressor< T, Bits, false >::pack
static T pack(T UserValue, T UserMaxValue)
Definition: Bitfields.h:138
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::bitfields_details::Impl::update
static void update(StorageType &Packed, IntegerType UserValue)
Checks UserValue is within bounds and packs it between FirstBit and LastBit of Packed leaving the res...
Definition: Bitfields.h:170
llvm::bitfields_details::Compressor::pack
static T pack(T UserValue, T UserMaxValue)
Definition: Bitfields.h:125
llvm::bitfields_details::ResolveUnderlyingType< bool, false >::type
std::conditional_t< sizeof(bool)==1, uint8_t, void > type
In case sizeof(bool) != 1, replace void by an additionnal std::conditional.
Definition: Bitfields.h:206
llvm::Bitfield::Element::IntegerType
typename bitfields_details::ResolveUnderlyingType< T >::type IntegerType
Definition: Bitfields.h:226
Shift
bool Shift
Definition: README.txt:468
llvm::tgtok::Bits
@ Bits
Definition: TGLexer.h:50
llvm::Bitfield::Element::Type
T Type
Definition: Bitfields.h:224
llvm::bitfields_details::BitPatterns::Umin
static constexpr Unsigned Umin
Definition: Bitfields.h:108
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::Bitfield::Element::Bits
static constexpr unsigned Bits
Definition: Bitfields.h:228
llvm::bitfields_details::Impl::StorageBits
static constexpr size_t StorageBits
Definition: Bitfields.h:163
llvm::Bitfield
Holds functions to get, set or test bitfields.
Definition: Bitfields.h:212
llvm::Bitfield::Element::FirstBit
static constexpr unsigned FirstBit
Definition: Bitfields.h:229
llvm::bitfields_details::Compressor::unpack
static T unpack(T StorageValue)
Definition: Bitfields.h:131
llvm::bitfields_details::Impl::Mask
static constexpr StorageType Mask
Definition: Bitfields.h:166
llvm::bitfields_details::Compressor
Compressor is used to manipulate the bits of a (possibly signed) integer type so it can be packed and...
Definition: Bitfields.h:121
llvm::bitfields_details::BitPatterns::Smax
static constexpr Unsigned Smax
Definition: Bitfields.h:111
llvm::bitfields_details::BitPatterns::Umax
static constexpr Unsigned Umax
Definition: Bitfields.h:109
false
Definition: StackSlotColoring.cpp:141
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::bitfields_details::BitPatterns::Smin
static constexpr Unsigned Smin
Definition: Bitfields.h:112
llvm::Bitfield::areContiguous
static constexpr bool areContiguous()
Definition: Bitfields.h:280
llvm::bitfields_details::Compressor< T, Bits, false >::unpack
static T unpack(T StorageValue)
Definition: Bitfields.h:147
llvm::Bitfield::isOverlapping
static constexpr bool isOverlapping()
Returns whether the two bitfields share common bits.
Definition: Bitfields.h:276
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::Bitfield::areContiguous
static constexpr bool areContiguous()
Definition: Bitfields.h:282
llvm::Bitfield::get
static Bitfield::Type get(StorageType Packed)
Unpacks the field from the Packed value.
Definition: Bitfields.h:254
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
extract
loop extract
Definition: LoopExtractor.cpp:92
llvm::Bitfield::test
static StorageType test(StorageType Packed)
Return a non-zero value if the field is non-zero.
Definition: Bitfields.h:262
llvm::bitfields_details::Impl
Impl is where Bifield description and Storage are put together to interact with values.
Definition: Bitfields.h:156
llvm::Bitfield::Element::Shift
static constexpr unsigned Shift
Definition: Bitfields.h:227
llvm::Bitfield::set
static void set(StorageType &Packed, typename Bitfield::Type Value)
Sets the typed value in the provided Packed value.
Definition: Bitfields.h:270
llvm::Offset
@ Offset
Definition: DWP.cpp:406
A
* A
Definition: README_ALTIVEC.txt:89
llvm::Bitfield::Element::NextBit
static constexpr unsigned NextBit
Definition: Bitfields.h:231
llvm::bitfields_details::Impl::IntegerType
typename Bitfield::IntegerType IntegerType
Definition: Bitfields.h:159
llvm::bitfields_details::ResolveUnderlyingType
Bitfield deals with the following type:
Definition: Bitfields.h:197
llvm::bitfields_details::Impl::test
static StorageType test(StorageType Packed)
Interprets bits between FirstBit and LastBit of Packed as anIntegerType.
Definition: Bitfields.h:185
llvm::bitfields_details::BitPatterns
A struct defining useful bit patterns for n-bits integer types.
Definition: Bitfields.h:94
llvm::Bitfield::Element
Describes an element of a Bitfield.
Definition: Bitfields.h:223
llvm::bitfields_details::ResolveUnderlyingType< T, false >::type
T type
Definition: Bitfields.h:201
llvm::bitfields_details::BitPatterns::SignBitMask
static constexpr Unsigned SignBitMask
Definition: Bitfields.h:110
llvm::bitfields_details::BitPatterns::AllZeros
static constexpr Unsigned AllZeros
e.g. with TypeBits == 8 and Bits == 6.
Definition: Bitfields.h:106
llvm::bitfields_details::BitPatterns::Unsigned
std::make_unsigned_t< T > Unsigned
Bit patterns are forged using the equivalent Unsigned type because of undefined operations over signe...
Definition: Bitfields.h:99
llvm::msgpack::Type
Type
MessagePack types as defined in the standard, with the exception of Integer being divided into a sign...
Definition: MsgPackReader.h:48
llvm::bitfields_details::BitPatterns::TypeBits
static constexpr unsigned TypeBits
Definition: Bitfields.h:102
llvm::bitfields_details::BitPatterns::SignExtend
static constexpr Unsigned SignExtend
Definition: Bitfields.h:113
llvm::bitfields_details::ResolveUnderlyingType::type
std::underlying_type_t< T > type
Definition: Bitfields.h:198
llvm::bitfields_details::BitPatterns::AllOnes
static constexpr Unsigned AllOnes
Definition: Bitfields.h:107
test
modulo schedule test
Definition: ModuloSchedule.cpp:2143
llvm::bitfields_details::Impl::extract
static IntegerType extract(StorageType Packed)
Interprets bits between FirstBit and LastBit of Packed as anIntegerType.
Definition: Bitfields.h:178
llvm::Value
LLVM Value Representation.
Definition: Value.h:74