LLVM: include/llvm/ADT/bit.h Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14#ifndef LLVM_ADT_BIT_H
15#define LLVM_ADT_BIT_H
16
18#include
19#include
20#include <type_traits>
21
22#if !__has_builtin(__builtin_bit_cast)
23#include
24#endif
25
26#if defined(_MSC_VER) && !defined(_DEBUG)
27#include
28#endif
29
30#if defined(__linux__) || defined(__GNU__) || defined(__HAIKU__) || \
31 defined(__Fuchsia__) || defined(__EMSCRIPTEN__) || defined(__NetBSD__) || \
32 defined(__OpenBSD__) || defined(__DragonFly__)
33#include <endian.h>
34#elif defined(_AIX)
35#include <sys/machine.h>
36#elif defined(__sun)
37
38#include <sys/types.h>
39#define BIG_ENDIAN 4321
40#define LITTLE_ENDIAN 1234
41#if defined(_BIG_ENDIAN)
42#define BYTE_ORDER BIG_ENDIAN
43#else
44#define BYTE_ORDER LITTLE_ENDIAN
45#endif
46#elif defined(__MVS__)
47#define BIG_ENDIAN 4321
48#define LITTLE_ENDIAN 1234
49#define BYTE_ORDER BIG_ENDIAN
50#else
51#if !defined(BYTE_ORDER) && !defined(_WIN32)
52#include <machine/endian.h>
53#endif
54#endif
55
56#ifdef _MSC_VER
57
58
59
60extern "C" {
61unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask);
62unsigned char _BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask);
63unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask);
64unsigned char _BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask);
65}
66#endif
67
68namespace llvm {
69
73#if defined(BYTE_ORDER) && defined(BIG_ENDIAN) && BYTE_ORDER == BIG_ENDIAN
75#else
77#endif
78};
79
80
81
82
83template <
84 typename To, typename From,
85 typename = std::enable_if_t<sizeof(To) == sizeof(From)>,
86 typename = std::enable_if_t<std::is_trivially_constructible::value>,
87 typename = std::enable_if_t<std::is_trivially_copyable::value>,
88 typename = std::enable_if_t<std::is_trivially_copyable::value>>
89[[nodiscard]] inline To bit_cast(const From &from) noexcept {
90#if __has_builtin(__builtin_bit_cast)
91 return __builtin_bit_cast(To, from);
92#else
93 To to;
94 std::memcpy(&to, &from, sizeof(To));
95 return to;
96#endif
97}
98
99
100template <typename T, typename = std::enable_if_t<std::is_integral_v>>
101[[nodiscard]] constexpr T byteswap(T V) noexcept {
102 if constexpr (sizeof(T) == 1) {
103 return V;
104 } else if constexpr (sizeof(T) == 2) {
106#if defined(_MSC_VER) && !defined(_DEBUG)
107
108
109 return _byteswap_ushort(UV);
110#else
114#endif
115 } else if constexpr (sizeof(T) == 4) {
117#if __has_builtin(__builtin_bswap32)
118 return __builtin_bswap32(UV);
119#elif defined(_MSC_VER) && !defined(_DEBUG)
120 return _byteswap_ulong(UV);
121#else
122 uint32_t Byte0 = UV & 0x000000FF;
123 uint32_t Byte1 = UV & 0x0000FF00;
124 uint32_t Byte2 = UV & 0x00FF0000;
125 uint32_t Byte3 = UV & 0xFF000000;
126 return (Byte0 << 24) | (Byte1 << 8) | (Byte2 >> 8) | (Byte3 >> 24);
127#endif
128 } else if constexpr (sizeof(T) == 8) {
130#if __has_builtin(__builtin_bswap64)
131 return __builtin_bswap64(UV);
132#elif defined(_MSC_VER) && !defined(_DEBUG)
133 return _byteswap_uint64(UV);
134#else
135 uint64_t Hi = llvm::byteswap<uint32_t>(UV);
136 uint32_t Lo = llvm::byteswap<uint32_t>(UV >> 32);
138#endif
139 } else {
140 static_assert(!sizeof(T *), "Don't know how to handle the given type.");
141 return 0;
142 }
143}
144
145template <typename T, typename = std::enable_if_t<std::is_unsigned_v>>
148}
149
153 if (!Val)
154 return std::numeric_limits::digits;
155 if (Val & 0x1)
156 return 0;
157
158
159 unsigned ZeroBits = 0;
160 T Shift = std::numeric_limits::digits >> 1;
161 T Mask = std::numeric_limits::max() >> Shift;
162 while (Shift) {
163 if ((Val & Mask) == 0) {
164 Val >>= Shift;
165 ZeroBits |= Shift;
166 }
167 Shift >>= 1;
168 Mask >>= Shift;
169 }
170 return ZeroBits;
171 }
172};
173
174#if defined(__GNUC__) || defined(_MSC_VER)
175template struct TrailingZerosCounter<T, 4> {
176 static unsigned count(T Val) {
177 if (Val == 0)
178 return 32;
179
180#if __has_builtin(__builtin_ctz) || defined(__GNUC__)
181 return __builtin_ctz(Val);
182#elif defined(_MSC_VER)
183 unsigned long Index;
184 _BitScanForward(&Index, Val);
186#endif
187 }
188};
189
190#if !defined(_MSC_VER) || defined(_M_X64)
191template struct TrailingZerosCounter<T, 8> {
192 static unsigned count(T Val) {
193 if (Val == 0)
194 return 64;
195
196#if __has_builtin(__builtin_ctzll) || defined(__GNUC__)
197 return __builtin_ctzll(Val);
198#elif defined(_MSC_VER)
199 unsigned long Index;
200 _BitScanForward64(&Index, Val);
202#endif
203 }
204};
205#endif
206#endif
207}
208
209
210
211
212
213
214
215template [[nodiscard]] int countr_zero(T Val) {
216 static_assert(std::is_unsigned_v,
217 "Only unsigned integral types are allowed.");
219}
220
224 if (!Val)
225 return std::numeric_limits::digits;
226
227
228 unsigned ZeroBits = 0;
229 for (T Shift = std::numeric_limits::digits >> 1; Shift; Shift >>= 1) {
230 T Tmp = Val >> Shift;
231 if (Tmp)
232 Val = Tmp;
233 else
234 ZeroBits |= Shift;
235 }
236 return ZeroBits;
237 }
238};
239
240#if defined(__GNUC__) || defined(_MSC_VER)
241template struct LeadingZerosCounter<T, 4> {
242 static unsigned count(T Val) {
243 if (Val == 0)
244 return 32;
245
246#if __has_builtin(__builtin_clz) || defined(__GNUC__)
247 return __builtin_clz(Val);
248#elif defined(_MSC_VER)
249 unsigned long Index;
250 _BitScanReverse(&Index, Val);
251 return Index ^ 31;
252#endif
253 }
254};
255
256#if !defined(_MSC_VER) || defined(_M_X64)
257template struct LeadingZerosCounter<T, 8> {
258 static unsigned count(T Val) {
259 if (Val == 0)
260 return 64;
261
262#if __has_builtin(__builtin_clzll) || defined(__GNUC__)
263 return __builtin_clzll(Val);
264#elif defined(_MSC_VER)
265 unsigned long Index;
266 _BitScanReverse64(&Index, Val);
267 return Index ^ 63;
268#endif
269 }
270};
271#endif
272#endif
273}
274
275
276
277
278
279
280
281template [[nodiscard]] int countl_zero(T Val) {
282 static_assert(std::is_unsigned_v,
283 "Only unsigned integral types are allowed.");
285}
286
287
288
289
290
291
292
293
295 static_assert(std::is_unsigned_v,
296 "Only unsigned integral types are allowed.");
297 return llvm::countl_zero(~Value);
298}
299
300
301
302
303
304
305
306
308 static_assert(std::is_unsigned_v,
309 "Only unsigned integral types are allowed.");
310 return llvm::countr_zero(~Value);
311}
312
313
314
315
316
318 static_assert(std::is_unsigned_v,
319 "Only unsigned integral types are allowed.");
321}
322
323
324
325
326
328 static_assert(std::is_unsigned_v,
329 "Only unsigned integral types are allowed.");
331 return 0;
333}
334
335
336
337
338
339
340
341
343 static_assert(std::is_unsigned_v,
344 "Only unsigned integral types are allowed.");
346 return 1;
347 return T(1) << llvm::bit_width(Value - 1u);
348}
349
353
354 static_assert(SizeOfT <= 4, "Not implemented!");
355#if defined(__GNUC__)
356 return (int)__builtin_popcount(Value);
357#else
359 v = v - ((v >> 1) & 0x55555555);
360 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
361 return int(((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24);
362#endif
363 }
364};
365
368#if defined(__GNUC__)
369 return (int)__builtin_popcountll(Value);
370#else
372 v = v - ((v >> 1) & 0x5555555555555555ULL);
373 v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
374 v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
375 return int((uint64_t)(v * 0x0101010101010101ULL) >> 56);
376#endif
377 }
378};
379}
380
381
382
383
384template <typename T, typename = std::enable_if_t<std::is_unsigned_v>>
387}
388
389
390template <typename T, typename = std::enable_if_t<std::is_unsigned_v>>
391[[nodiscard]] constexpr T rotr(T V, int R);
392
393template <typename T, typename = std::enable_if_t<std::is_unsigned_v>>
394[[nodiscard]] constexpr T rotl(T V, int R) {
395 unsigned N = std::numeric_limits::digits;
396
397 R = R % N;
398 if (!R)
399 return V;
400
401 if (R < 0)
403
404 return (V << R) | (V >> (N - R));
405}
406
407template <typename T, typename> [[nodiscard]] constexpr T rotr(T V, int R) {
408 unsigned N = std::numeric_limits::digits;
409
410 R = R % N;
411 if (!R)
412 return V;
413
414 if (R < 0)
416
417 return (V >> R) | (V << (N - R));
418}
419
420}
421
422#endif
BlockVerifier::State From
LLVM Value Representation.
This is an optimization pass for GlobalISel generic memory operations.
constexpr T rotr(T V, int R)
int popcount(T Value) noexcept
Count the number of set bits in a value.
int countr_one(T Value)
Count the number of ones from the least significant bit to the first zero bit.
constexpr T byteswap(T V) noexcept
Reverses the bytes in the given integer value V.
int bit_width(T Value)
Returns the number of bits needed to represent Value if Value is nonzero.
T bit_ceil(T Value)
Returns the smallest integral power of two no smaller than Value if Value is nonzero.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
constexpr bool has_single_bit(T Value) noexcept
int countl_zero(T Val)
Count number of 0's from the most significant bit to the least stopping at the first 1.
int countl_one(T Value)
Count the number of ones from the most significant bit to the first zero bit.
To bit_cast(const From &from) noexcept
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
T bit_floor(T Value)
Returns the largest integral power of two no greater than Value if Value is nonzero.
constexpr T rotl(T V, int R)
static unsigned count(T Val)
static int count(T Value)
static int count(T Value)
static unsigned count(T Val)