LLVM  14.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.
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 is 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 is 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>
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<sizeof(bool) == 1, uint8_t, void>::type;
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::Check::Size
@ Size
Definition: FileCheck.h:73
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
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
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::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
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
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:142
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::bitfields_details::ResolveUnderlyingType< bool, false >::type
std::conditional< sizeof(bool)==1, uint8_t, void >::type type
In case sizeof(bool) != 1, replace void by an additionnal std::conditional.
Definition: Bitfields.h:206
llvm::bitfields_details::ResolveUnderlyingType::type
typename std::underlying_type< T >::type type
Definition: Bitfields.h:198
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
type
AMD64 Optimization Manual has some nice information about optimizing integer multiplication by a constant How much of it applies to Intel s X86 implementation There are definite trade offs to xmm0 cvttss2siq rdx jb L3 subss xmm0 rax cvttss2siq rdx xorq rdx rax ret instead of xmm1 cvttss2siq rcx movaps xmm2 subss xmm2 cvttss2siq rax rdx xorq rax ucomiss xmm0 cmovb rax ret Seems like the jb branch has high likelihood of being taken It would have saved a few instructions It s not possible to reference and DH registers in an instruction requiring REX prefix divb and mulb both produce results in AH If isel emits a CopyFromReg which gets turned into a movb and that can be allocated a r8b r15b To get around isel emits a CopyFromReg from AX and then right shift it down by and truncate it It s not pretty but it works We need some register allocation magic to make the hack go which would often require a callee saved register Callees usually need to keep this value live for most of their body so it doesn t add a significant burden on them We currently implement this in however this is suboptimal because it means that it would be quite awkward to implement the optimization for callers A better implementation would be to relax the LLVM IR rules for sret arguments to allow a function with an sret argument to have a non void return type
Definition: README-X86-64.txt:70
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:59
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:97
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
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::BitPatterns::Unsigned
typename std::make_unsigned< T >::type Unsigned
Bit patterns are forged using the equivalent Unsigned type because of undefined operations over signe...
Definition: Bitfields.h:99
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::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::msgpack::Type
Type
MessagePack types as defined in the standard, with the exception of Integer being divided into a sign...
Definition: MsgPackReader.h:49
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::BitPatterns::AllOnes
static constexpr Unsigned AllOnes
Definition: Bitfields.h:107
test
modulo schedule test
Definition: ModuloSchedule.cpp:2125
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:75