Movatterモバイル変換

[0]ホーム
URL:

LLVM 20.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
89namespacellvm {
90
91namespacebitfields_details {
92
93/// A struct defining useful bit patterns for n-bits integer types.
94template <typename T,unsigned Bits>structBitPatterns {
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.
99usingUnsigned = std::make_unsigned_t<T>;
100static_assert(sizeof(Unsigned) ==sizeof(T),"Types must have same size");
101
102staticconstexprunsignedTypeBits =sizeof(Unsigned) * CHAR_BIT;
103static_assert(TypeBits >= Bits,"n-bit must fit in T");
104
105 /// e.g. with TypeBits == 8 and Bits == 6.
106staticconstexprUnsignedAllZeros =Unsigned(0);// 00000000
107staticconstexprUnsignedAllOnes =~Unsigned(0);// 11111111
108staticconstexprUnsignedUmin =AllZeros;// 00000000
109staticconstexprUnsignedUmax =AllOnes >> (TypeBits - Bits);// 00111111
110staticconstexprUnsignedSignBitMask =Unsigned(1) << (Bits - 1);// 00100000
111staticconstexprUnsignedSmax =Umax >> 1U;// 00011111
112staticconstexprUnsignedSmin = ~Smax;// 11100000
113staticconstexprUnsignedSignExtend =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.
120template <typename T, unsigned Bits, bool = std::is_unsigned<T>::value>
121structCompressor {
122static_assert(std::is_unsigned<T>::value,"T must be unsigned");
123usingBP =BitPatterns<T, Bits>;
124
125staticTpack(T UserValue,T UserMaxValue) {
126assert(UserValue <= UserMaxValue &&"value is too big");
127assert(UserValue <=BP::Umax &&"value is too big");
128return UserValue;
129 }
130
131staticTunpack(T StorageValue) {return StorageValue; }
132};
133
134template <typename T,unsigned Bits>structCompressor<T, Bits,false> {
135static_assert(std::is_signed<T>::value,"T must be signed");
136usingBP =BitPatterns<T, Bits>;
137
138staticTpack(T UserValue,T UserMaxValue) {
139assert(UserValue <= UserMaxValue &&"value is too big");
140assert(UserValue <=T(BP::Smax) &&"value is too big");
141assert(UserValue >=T(BP::Smin) &&"value is too small");
142if (UserValue < 0)
143 UserValue &=~BP::SignExtend;
144return UserValue;
145 }
146
147staticTunpack(T StorageValue) {
148if (StorageValue >=T(BP::SignBitMask))
149 StorageValue |=BP::SignExtend;
150return StorageValue;
151 }
152};
153
154/// Impl is where Bifield description and Storage are put together to interact
155/// with values.
156template <typename Bitfield,typename StorageType>structImpl {
157static_assert(std::is_unsigned<StorageType>::value,
158"Storage must be unsigned");
159usingIntegerType =typename Bitfield::IntegerType;
160usingC =Compressor<IntegerType, Bitfield::Bits>;
161usingBP =BitPatterns<StorageType, Bitfield::Bits>;
162
163staticconstexprsize_tStorageBits =sizeof(StorageType) * CHAR_BIT;
164static_assert(Bitfield::FirstBit <=StorageBits,"Data must fit in mask");
165static_assert(Bitfield::LastBit <=StorageBits,"Data must fit in mask");
166staticconstexpr StorageTypeMask =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.
170staticvoidupdate(StorageType &Packed,IntegerType UserValue) {
171const 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`.
178staticIntegerTypeextract(StorageType Packed) {
179const StorageType StorageValue = (Packed &Mask) >> Bitfield::Shift;
180returnC::unpack(StorageValue);
181 }
182
183 /// Interprets bits between `FirstBit` and `LastBit` of `Packed` as
184 /// an`IntegerType`.
185static StorageTypetest(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.
196template <typename T, bool = std::is_enum<T>::value>
197structResolveUnderlyingType {
198usingtype = std::underlying_type_t<T>;
199};
200template <typename T>structResolveUnderlyingType<T,false> {
201usingtype =T;
202};
203template <>structResolveUnderlyingType<bool,false> {
204 /// In case sizeof(bool) != 1, replace `void` by an additionnal
205 /// std::conditional.
206usingtype = 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.
212structBitfield {
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.
219template <typenameT,unsignedOffset,unsignedSize,
220T MaxValue = std::is_enum<T>::value
221 ?T(0)// coupled with static_assert below
222 : std::numeric_limits<T>::max()>
223structElement {
224usingType =T;
225usingIntegerType =
226typenamebitfields_details::ResolveUnderlyingType<T>::type;
227staticconstexprunsignedShift =Offset;
228staticconstexprunsignedBits =Size;
229staticconstexprunsignedFirstBit =Offset;
230staticconstexprunsignedLastBit =Shift +Bits - 1;
231staticconstexprunsignedNextBit =Shift +Bits;
232
233private:
234template <typename,typename>friendstructbitfields_details::Impl;
235
236static_assert(Bits > 0,"Bits must be non zero");
237staticconstexprsize_t TypeBits =sizeof(IntegerType) * CHAR_BIT;
238static_assert(Bits <= TypeBits,"Bits may not be greater than T size");
239static_assert(!std::is_enum<T>::value || MaxValue !=T(0),
240"Enum Bitfields must provide a MaxValue");
241static_assert(!std::is_enum<T>::value ||
242 std::is_unsigned<IntegerType>::value,
243"Enum must be unsigned");
244static_assert(std::is_integral<IntegerType>::value &&
245 std::numeric_limits<IntegerType>::is_integer,
246"IntegerType must be an integer type");
247
248staticconstexprIntegerType UserMaxValue =
249static_cast<IntegerType>(MaxValue);
250 };
251
252 /// Unpacks the field from the `Packed` value.
253template <typename Bitfield,typename StorageType>
254statictypename Bitfield::Typeget(StorageType Packed) {
255usingI =bitfields_details::Impl<Bitfield, StorageType>;
256returnstatic_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`.
261template <typename Bitfield,typename StorageType>
262static StorageTypetest(StorageType Packed) {
263usingI =bitfields_details::Impl<Bitfield, StorageType>;
264return 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.
269template <typename Bitfield,typename StorageType>
270staticvoidset(StorageType &Packed,typename Bitfield::TypeValue) {
271usingI =bitfields_details::Impl<Bitfield, StorageType>;
272 I::update(Packed,static_cast<typename Bitfield::IntegerType>(Value));
273 }
274
275 /// Returns whether the two bitfields share common bits.
276template <typename A,typename B>staticconstexprboolisOverlapping() {
277return A::LastBit >= B::FirstBit && B::LastBit >= A::FirstBit;
278 }
279
280template <typename A>staticconstexprboolareContiguous() {returntrue; }
281template <typenameA,typenameB,typename... Others>
282staticconstexprboolareContiguous() {
283return A::NextBit == B::FirstBit &&areContiguous<B, Others...>();
284 }
285};
286
287}// namespace llvm
288
289#endif// LLVM_ADT_BITFIELDS_H
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
A
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
Size
uint64_t Size
Definition:ELFObjHandler.cpp:81
I
#define I(x, y, z)
Definition:MD5.cpp:58
T
#define T
Definition:Mips16ISelLowering.cpp:341
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
T
bool
llvm::Value
LLVM Value Representation.
Definition:Value.h:74
uint8_t
false
Definition:StackSlotColoring.cpp:193
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition:AddressRanges.h:18
llvm::Offset
@ Offset
Definition:DWP.cpp:480
llvm::Bitfield::Element
Describes an element of a Bitfield.
Definition:Bitfields.h:223
llvm::Bitfield::Element::IntegerType
typename bitfields_details::ResolveUnderlyingType< T >::type IntegerType
Definition:Bitfields.h:226
llvm::Bitfield::Element::Shift
static constexpr unsigned Shift
Definition:Bitfields.h:227
llvm::Bitfield::Element::Bits
static constexpr unsigned Bits
Definition:Bitfields.h:228
llvm::Bitfield::Element::FirstBit
static constexpr unsigned FirstBit
Definition:Bitfields.h:229
llvm::Bitfield::Element::NextBit
static constexpr unsigned NextBit
Definition:Bitfields.h:231
llvm::Bitfield::Element::LastBit
static constexpr unsigned LastBit
Definition:Bitfields.h:230
llvm::Bitfield
Holds functions to get, set or test bitfields.
Definition:Bitfields.h:212
llvm::Bitfield::areContiguous
static constexpr bool areContiguous()
Definition:Bitfields.h:280
llvm::Bitfield::get
static Bitfield::Type get(StorageType Packed)
Unpacks the field from the Packed value.
Definition:Bitfields.h:254
llvm::Bitfield::areContiguous
static constexpr bool areContiguous()
Definition:Bitfields.h:282
llvm::Bitfield::isOverlapping
static constexpr bool isOverlapping()
Returns whether the two bitfields share common bits.
Definition:Bitfields.h:276
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::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::BitPatterns
A struct defining useful bit patterns for n-bits integer types.
Definition:Bitfields.h:94
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::bitfields_details::BitPatterns::AllOnes
static constexpr Unsigned AllOnes
Definition:Bitfields.h:107
llvm::bitfields_details::BitPatterns::Smax
static constexpr Unsigned Smax
Definition:Bitfields.h:111
llvm::bitfields_details::BitPatterns::SignExtend
static constexpr Unsigned SignExtend
Definition:Bitfields.h:113
llvm::bitfields_details::BitPatterns::Smin
static constexpr Unsigned Smin
Definition:Bitfields.h:112
llvm::bitfields_details::BitPatterns::Umin
static constexpr Unsigned Umin
Definition:Bitfields.h:108
llvm::bitfields_details::BitPatterns::TypeBits
static constexpr unsigned TypeBits
Definition:Bitfields.h:102
llvm::bitfields_details::BitPatterns::SignBitMask
static constexpr Unsigned SignBitMask
Definition:Bitfields.h:110
llvm::bitfields_details::BitPatterns::Umax
static constexpr Unsigned Umax
Definition:Bitfields.h:109
llvm::bitfields_details::BitPatterns::AllZeros
static constexpr Unsigned AllZeros
e.g. with TypeBits == 8 and Bits == 6.
Definition:Bitfields.h:106
llvm::bitfields_details::Compressor< T, Bits, false >::pack
static T pack(T UserValue, T UserMaxValue)
Definition:Bitfields.h:138
llvm::bitfields_details::Compressor< T, Bits, false >::unpack
static T unpack(T StorageValue)
Definition:Bitfields.h:147
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::Compressor::pack
static T pack(T UserValue, T UserMaxValue)
Definition:Bitfields.h:125
llvm::bitfields_details::Compressor::unpack
static T unpack(T StorageValue)
Definition:Bitfields.h:131
llvm::bitfields_details::Impl
Impl is where Bifield description and Storage are put together to interact with values.
Definition:Bitfields.h:156
llvm::bitfields_details::Impl::StorageBits
static constexpr size_t StorageBits
Definition:Bitfields.h:163
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::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::Impl::test
static StorageType test(StorageType Packed)
Interprets bits between FirstBit and LastBit of Packed as anIntegerType.
Definition:Bitfields.h:185
llvm::bitfields_details::Impl::Mask
static constexpr StorageType Mask
Definition:Bitfields.h:166
llvm::bitfields_details::Impl::IntegerType
typename Bitfield::IntegerType IntegerType
Definition:Bitfields.h:159
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::bitfields_details::ResolveUnderlyingType
Bitfield deals with the following type:
Definition:Bitfields.h:197
llvm::bitfields_details::ResolveUnderlyingType::type
std::underlying_type_t< T > type
Definition:Bitfields.h:198
Generated on Thu Jul 17 2025 03:52:02 for LLVM by doxygen 1.9.6
[8]ページ先頭
©2009-2025 Movatter.jp