Bug Summary

File:build/source/llvm/lib/Target/ARM/MCTargetDesc/ARMUnwindOpAsm.cpp
Warning:line 82, column 27
The result of the left shift is undefined due to shifting by '32', which is greater or equal to the width of type 'unsigned int'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name ARMUnwindOpAsm.cpp -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -resource-dir /usr/lib/llvm-17/lib/clang/17 -D _DEBUG -D _GLIBCXX_ASSERTIONS -D _GNU_SOURCE -D _LIBCPP_ENABLE_ASSERTIONS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/Target/ARM/MCTargetDesc -I /build/source/llvm/lib/Target/ARM/MCTargetDesc -I /build/source/llvm/lib/Target/ARM -I lib/Target/ARM -I include -I /build/source/llvm/include -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-17/lib/clang/17/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fmacro-prefix-map=/build/source/= -fcoverage-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fcoverage-prefix-map=/build/source/= -source-date-epoch 1683717183 -O2 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/source/build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/build-llvm/tools/clang/stage2-bins=build-llvm/tools/clang/stage2-bins -fdebug-prefix-map=/build/source/= -ferror-limit 19 -fvisibility=hidden -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2023-05-10-133810-16478-1 -x c++ /build/source/llvm/lib/Target/ARM/MCTargetDesc/ARMUnwindOpAsm.cpp

/build/source/llvm/lib/Target/ARM/MCTargetDesc/ARMUnwindOpAsm.cpp

→
1//===-- ARMUnwindOpAsm.cpp - ARM Unwind Opcodes Assembler -------*- 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// This file implements the unwind opcode assembler for ARM exception handling
10// table.
11//
12//===----------------------------------------------------------------------===//
13
14#include "ARMUnwindOpAsm.h"
15#include "llvm/Support/ARMEHABI.h"
16#include "llvm/Support/LEB128.h"
17#include "llvm/Support/MathExtras.h"
18#include <cassert>
19
20using namespace llvm;
21
22namespace {
23
24 /// UnwindOpcodeStreamer - The simple wrapper over SmallVector to emit bytes
25 /// with MSB to LSB per uint32_t ordering. For example, the first byte will
26 /// be placed in Vec[3], and the following bytes will be placed in 2, 1, 0,
27 /// 7, 6, 5, 4, 11, 10, 9, 8, and so on.
28 class UnwindOpcodeStreamer {
29 private:
30 SmallVectorImpl<uint8_t> &Vec;
31 size_t Pos = 3;
32
33 public:
34 UnwindOpcodeStreamer(SmallVectorImpl<uint8_t> &V) : Vec(V) {}
35
36 /// Emit the byte in MSB to LSB per uint32_t order.
37 void EmitByte(uint8_t elem) {
38 Vec[Pos] = elem;
39 Pos = (((Pos ^ 0x3u) + 1) ^ 0x3u);
40 }
41
42 /// Emit the size prefix.
43 void EmitSize(size_t Size) {
44 size_t SizeInWords = (Size + 3) / 4;
45 assert(SizeInWords <= 0x100u &&(static_cast <bool> (SizeInWords <= 0x100u &&
"Only 256 additional words are allowed for unwind opcodes") ?
void (0) : __assert_fail ("SizeInWords <= 0x100u && \"Only 256 additional words are allowed for unwind opcodes\""
, "llvm/lib/Target/ARM/MCTargetDesc/ARMUnwindOpAsm.cpp", 46, __extension__
__PRETTY_FUNCTION__))
46 "Only 256 additional words are allowed for unwind opcodes")(static_cast <bool> (SizeInWords <= 0x100u &&
"Only 256 additional words are allowed for unwind opcodes") ?
void (0) : __assert_fail ("SizeInWords <= 0x100u && \"Only 256 additional words are allowed for unwind opcodes\""
, "llvm/lib/Target/ARM/MCTargetDesc/ARMUnwindOpAsm.cpp", 46, __extension__
__PRETTY_FUNCTION__));
47 EmitByte(static_cast<uint8_t>(SizeInWords - 1));
48 }
49
50 /// Emit the personality index prefix.
51 void EmitPersonalityIndex(unsigned PI) {
52 assert(PI < ARM::EHABI::NUM_PERSONALITY_INDEX &&(static_cast <bool> (PI < ARM::EHABI::NUM_PERSONALITY_INDEX
&& "Invalid personality prefix") ? void (0) : __assert_fail
("PI < ARM::EHABI::NUM_PERSONALITY_INDEX && \"Invalid personality prefix\""
, "llvm/lib/Target/ARM/MCTargetDesc/ARMUnwindOpAsm.cpp", 53, __extension__
__PRETTY_FUNCTION__))
53 "Invalid personality prefix")(static_cast <bool> (PI < ARM::EHABI::NUM_PERSONALITY_INDEX
&& "Invalid personality prefix") ? void (0) : __assert_fail
("PI < ARM::EHABI::NUM_PERSONALITY_INDEX && \"Invalid personality prefix\""
, "llvm/lib/Target/ARM/MCTargetDesc/ARMUnwindOpAsm.cpp", 53, __extension__
__PRETTY_FUNCTION__));
54 EmitByte(ARM::EHABI::EHT_COMPACT | PI);
55 }
56
57 /// Fill the rest of bytes with FINISH opcode.
58 void FillFinishOpcode() {
59 while (Pos < Vec.size())
60 EmitByte(ARM::EHABI::UNWIND_OPCODE_FINISH);
61 }
62 };
63
64} // end anonymous namespace
65
66void UnwindOpcodeAssembler::EmitRegSave(uint32_t RegSave) {
67 if (RegSave == 0u) {
1
Assuming 'RegSave' is not equal to 0
→
2
←
Taking false branch
→
68 // That's the special case for RA PAC.
69 EmitInt8(ARM::EHABI::UNWIND_OPCODE_POP_RA_AUTH_CODE);
70 return;
71 }
72
73 // One byte opcode to save register r14 and r11-r4
74 if (RegSave & (1u << 4)) {
3
←
Assuming the condition is true
→
4
←
Taking true branch
→
75 // The one byte opcode will always save r4, thus we can't use the one byte
76 // opcode when r4 is not in .save directive.
77
78 // Compute the consecutive registers from r4 to r11.
79 uint32_t Mask = RegSave & 0xff0u;
80 uint32_t Range = llvm::countr_one(Mask >> 5); // Exclude r4.
5
←
Calling 'countr_one<unsigned int>'
→
15
←
Returning from 'countr_one<unsigned int>'
→
16
←
'Range' initialized to 32
→
81 // Mask off non-consecutive registers. Keep r4.
82 Mask &= ~(0xffffffe0u << Range);
17
←
The result of the left shift is undefined due to shifting by '32', which is greater or equal to the width of type 'unsigned int'
83
84 // Emit this opcode when the mask covers every registers.
85 uint32_t UnmaskedReg = RegSave & 0xfff0u & (~Mask);
86 if (UnmaskedReg == 0u) {
87 // Pop r[4 : (4 + n)]
88 EmitInt8(ARM::EHABI::UNWIND_OPCODE_POP_REG_RANGE_R4 | Range);
89 RegSave &= 0x000fu;
90 } else if (UnmaskedReg == (1u << 14)) {
91 // Pop r[14] + r[4 : (4 + n)]
92 EmitInt8(ARM::EHABI::UNWIND_OPCODE_POP_REG_RANGE_R4_R14 | Range);
93 RegSave &= 0x000fu;
94 }
95 }
96
97 // Two bytes opcode to save register r15-r4
98 if ((RegSave & 0xfff0u) != 0)
99 EmitInt16(ARM::EHABI::UNWIND_OPCODE_POP_REG_MASK_R4 | (RegSave >> 4));
100
101 // Opcode to save register r3-r0
102 if ((RegSave & 0x000fu) != 0)
103 EmitInt16(ARM::EHABI::UNWIND_OPCODE_POP_REG_MASK | (RegSave & 0x000fu));
104}
105
106/// Emit unwind opcodes for .vsave directives
107void UnwindOpcodeAssembler::EmitVFPRegSave(uint32_t VFPRegSave) {
108 // We only have 4 bits to save the offset in the opcode so look at the lower
109 // and upper 16 bits separately.
110 for (uint32_t Regs : {VFPRegSave & 0xffff0000u, VFPRegSave & 0x0000ffffu}) {
111 while (Regs) {
112 // Now look for a run of set bits. Remember the MSB and LSB of the run.
113 auto RangeMSB = llvm::bit_width(Regs);
114 auto RangeLen = llvm::countl_one(Regs << (32 - RangeMSB));
115 auto RangeLSB = RangeMSB - RangeLen;
116
117 int Opcode = RangeLSB >= 16
118 ? ARM::EHABI::UNWIND_OPCODE_POP_VFP_REG_RANGE_FSTMFDD_D16
119 : ARM::EHABI::UNWIND_OPCODE_POP_VFP_REG_RANGE_FSTMFDD;
120
121 EmitInt16(Opcode | ((RangeLSB % 16) << 4) | (RangeLen - 1));
122
123 // Zero out bits we're done with.
124 Regs &= ~(-1u << RangeLSB);
125 }
126 }
127}
128
129/// Emit unwind opcodes to copy address from source register to $sp.
130void UnwindOpcodeAssembler::EmitSetSP(uint16_t Reg) {
131 EmitInt8(ARM::EHABI::UNWIND_OPCODE_SET_VSP | Reg);
132}
133
134/// Emit unwind opcodes to add $sp with an offset.
135void UnwindOpcodeAssembler::EmitSPOffset(int64_t Offset) {
136 if (Offset > 0x200) {
137 uint8_t Buff[16];
138 Buff[0] = ARM::EHABI::UNWIND_OPCODE_INC_VSP_ULEB128;
139 size_t ULEBSize = encodeULEB128((Offset - 0x204) >> 2, Buff + 1);
140 emitBytes(Buff, ULEBSize + 1);
141 } else if (Offset > 0) {
142 if (Offset > 0x100) {
143 EmitInt8(ARM::EHABI::UNWIND_OPCODE_INC_VSP | 0x3fu);
144 Offset -= 0x100;
145 }
146 EmitInt8(ARM::EHABI::UNWIND_OPCODE_INC_VSP |
147 static_cast<uint8_t>((Offset - 4) >> 2));
148 } else if (Offset < 0) {
149 while (Offset < -0x100) {
150 EmitInt8(ARM::EHABI::UNWIND_OPCODE_DEC_VSP | 0x3fu);
151 Offset += 0x100;
152 }
153 EmitInt8(ARM::EHABI::UNWIND_OPCODE_DEC_VSP |
154 static_cast<uint8_t>(((-Offset) - 4) >> 2));
155 }
156}
157
158void UnwindOpcodeAssembler::Finalize(unsigned &PersonalityIndex,
159 SmallVectorImpl<uint8_t> &Result) {
160 UnwindOpcodeStreamer OpStreamer(Result);
161
162 if (HasPersonality) {
163 // User-specifed personality routine: [ SIZE , OP1 , OP2 , ... ]
164 PersonalityIndex = ARM::EHABI::NUM_PERSONALITY_INDEX;
165 size_t TotalSize = Ops.size() + 1;
166 size_t RoundUpSize = (TotalSize + 3) / 4 * 4;
167 Result.resize(RoundUpSize);
168 OpStreamer.EmitSize(RoundUpSize);
169 } else {
170 // If no personalityindex is specified, select ane
171 if (PersonalityIndex == ARM::EHABI::NUM_PERSONALITY_INDEX)
172 PersonalityIndex = (Ops.size() <= 3) ? ARM::EHABI::AEABI_UNWIND_CPP_PR0
173 : ARM::EHABI::AEABI_UNWIND_CPP_PR1;
174 if (PersonalityIndex == ARM::EHABI::AEABI_UNWIND_CPP_PR0) {
175 // __aeabi_unwind_cpp_pr0: [ 0x80 , OP1 , OP2 , OP3 ]
176 assert(Ops.size() <= 3 && "too many opcodes for __aeabi_unwind_cpp_pr0")(static_cast <bool> (Ops.size() <= 3 && "too many opcodes for __aeabi_unwind_cpp_pr0"
) ? void (0) : __assert_fail ("Ops.size() <= 3 && \"too many opcodes for __aeabi_unwind_cpp_pr0\""
, "llvm/lib/Target/ARM/MCTargetDesc/ARMUnwindOpAsm.cpp", 176,
__extension__ __PRETTY_FUNCTION__));
177 Result.resize(4);
178 OpStreamer.EmitPersonalityIndex(PersonalityIndex);
179 } else {
180 // __aeabi_unwind_cpp_pr{1,2}: [ {0x81,0x82} , SIZE , OP1 , OP2 , ... ]
181 size_t TotalSize = Ops.size() + 2;
182 size_t RoundUpSize = (TotalSize + 3) / 4 * 4;
183 Result.resize(RoundUpSize);
184 OpStreamer.EmitPersonalityIndex(PersonalityIndex);
185 OpStreamer.EmitSize(RoundUpSize);
186 }
187 }
188
189 // Copy the unwind opcodes
190 for (size_t i = OpBegins.size() - 1; i > 0; --i)
191 for (size_t j = OpBegins[i - 1], end = OpBegins[i]; j < end; ++j)
192 OpStreamer.EmitByte(Ops[j]);
193
194 // Emit the padding finish opcodes if the size is not multiple of 4.
195 OpStreamer.FillFinishOpcode();
196
197 // Reset the assembler state
198 Reset();
199}
←

/build/source/llvm/include/llvm/ADT/bit.h

1//===-- llvm/ADT/bit.h - C++20 <bit> ----------------------------*- 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 the C++20 <bit> header.
11///
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ADT_BIT_H
15#define LLVM_ADT_BIT_H
16
17#include "llvm/Support/Compiler.h"
18#include <cstdint>
19#include <limits>
20#include <type_traits>
21
22#if !__has_builtin(__builtin_bit_cast)1
23#include <cstring>
24#endif
25
26#if defined(_MSC_VER) && !defined(_DEBUG1)
27#include <cstdlib> // for _byteswap_{ushort,ulong,uint64}
28#endif
29
30#ifdef _MSC_VER
31// Declare these intrinsics manually rather including intrin.h. It's very
32// expensive, and bit.h is popular via MathExtras.h.
33// #include <intrin.h>
34extern "C" {
35unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask);
36unsigned char _BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask);
37unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask);
38unsigned char _BitScanReverse64(unsigned long *_Index, unsigned __int64 _Mask);
39}
40#endif
41
42namespace llvm {
43
44// This implementation of bit_cast is different from the C++20 one in two ways:
45// - It isn't constexpr because that requires compiler support.
46// - It requires trivially-constructible To, to avoid UB in the implementation.
47template <
48 typename To, typename From,
49 typename = std::enable_if_t<sizeof(To) == sizeof(From)>,
50 typename = std::enable_if_t<std::is_trivially_constructible<To>::value>,
51 typename = std::enable_if_t<std::is_trivially_copyable<To>::value>,
52 typename = std::enable_if_t<std::is_trivially_copyable<From>::value>>
53[[nodiscard]] inline To bit_cast(const From &from) noexcept {
54#if __has_builtin(__builtin_bit_cast)1
55 return __builtin_bit_cast(To, from);
56#else
57 To to;
58 std::memcpy(&to, &from, sizeof(To));
59 return to;
60#endif
61}
62
63/// Reverses the bytes in the given integer value V.
64template <typename T, typename = std::enable_if_t<std::is_integral_v<T>>>
65[[nodiscard]] constexpr T byteswap(T V) noexcept {
66 if constexpr (sizeof(T) == 1) {
67 return V;
68 } else if constexpr (sizeof(T) == 2) {
69 uint16_t UV = V;
70#if defined(_MSC_VER) && !defined(_DEBUG1)
71 // The DLL version of the runtime lacks these functions (bug!?), but in a
72 // release build they're replaced with BSWAP instructions anyway.
73 return _byteswap_ushort(UV);
74#else
75 uint16_t Hi = UV << 8;
76 uint16_t Lo = UV >> 8;
77 return Hi | Lo;
78#endif
79 } else if constexpr (sizeof(T) == 4) {
80 uint32_t UV = V;
81#if __has_builtin(__builtin_bswap32)1
82 return __builtin_bswap32(UV);
83#elif defined(_MSC_VER) && !defined(_DEBUG1)
84 return _byteswap_ulong(UV);
85#else
86 uint32_t Byte0 = UV & 0x000000FF;
87 uint32_t Byte1 = UV & 0x0000FF00;
88 uint32_t Byte2 = UV & 0x00FF0000;
89 uint32_t Byte3 = UV & 0xFF000000;
90 return (Byte0 << 24) | (Byte1 << 8) | (Byte2 >> 8) | (Byte3 >> 24);
91#endif
92 } else if constexpr (sizeof(T) == 8) {
93 uint64_t UV = V;
94#if __has_builtin(__builtin_bswap64)1
95 return __builtin_bswap64(UV);
96#elif defined(_MSC_VER) && !defined(_DEBUG1)
97 return _byteswap_uint64(UV);
98#else
99 uint64_t Hi = llvm::byteswap<uint32_t>(UV);
100 uint32_t Lo = llvm::byteswap<uint32_t>(UV >> 32);
101 return (Hi << 32) | Lo;
102#endif
103 } else {
104 static_assert(!sizeof(T *), "Don't know how to handle the given type.");
105 return 0;
106 }
107}
108
109template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
110[[nodiscard]] constexpr inline bool has_single_bit(T Value) noexcept {
111 return (Value != 0) && ((Value & (Value - 1)) == 0);
112}
113
114namespace detail {
115template <typename T, std::size_t SizeOfT> struct TrailingZerosCounter {
116 static unsigned count(T Val) {
117 if (!Val)
118 return std::numeric_limits<T>::digits;
119 if (Val & 0x1)
120 return 0;
121
122 // Bisection method.
123 unsigned ZeroBits = 0;
124 T Shift = std::numeric_limits<T>::digits >> 1;
125 T Mask = std::numeric_limits<T>::max() >> Shift;
126 while (Shift) {
127 if ((Val & Mask) == 0) {
128 Val >>= Shift;
129 ZeroBits |= Shift;
130 }
131 Shift >>= 1;
132 Mask >>= Shift;
133 }
134 return ZeroBits;
135 }
136};
137
138#if defined(__GNUC__4) || defined(_MSC_VER)
139template <typename T> struct TrailingZerosCounter<T, 4> {
140 static unsigned count(T Val) {
141 if (Val == 0)
8
←
Assuming 'Val' is equal to 0
→
9
←
Taking true branch
→
142 return 32;
10
←
Returning the value 32
→
143
144#if __has_builtin(__builtin_ctz)1 || defined(__GNUC__4)
145 return __builtin_ctz(Val);
146#elif defined(_MSC_VER)
147 unsigned long Index;
148 _BitScanForward(&Index, Val);
149 return Index;
150#endif
151 }
152};
153
154#if !defined(_MSC_VER) || defined(_M_X64)
155template <typename T> struct TrailingZerosCounter<T, 8> {
156 static unsigned count(T Val) {
157 if (Val == 0)
158 return 64;
159
160#if __has_builtin(__builtin_ctzll)1 || defined(__GNUC__4)
161 return __builtin_ctzll(Val);
162#elif defined(_MSC_VER)
163 unsigned long Index;
164 _BitScanForward64(&Index, Val);
165 return Index;
166#endif
167 }
168};
169#endif
170#endif
171} // namespace detail
172
173/// Count number of 0's from the least significant bit to the most
174/// stopping at the first 1.
175///
176/// Only unsigned integral types are allowed.
177///
178/// Returns std::numeric_limits<T>::digits on an input of 0.
179template <typename T> [[nodiscard]] int countr_zero(T Val) {
180 static_assert(std::is_unsigned_v<T>,
181 "Only unsigned integral types are allowed.");
182 return llvm::detail::TrailingZerosCounter<T, sizeof(T)>::count(Val);
7
←
Calling 'TrailingZerosCounter::count'
→
11
←
Returning from 'TrailingZerosCounter::count'
→
12
←
Returning the value 32
→
183}
184
185namespace detail {
186template <typename T, std::size_t SizeOfT> struct LeadingZerosCounter {
187 static unsigned count(T Val) {
188 if (!Val)
189 return std::numeric_limits<T>::digits;
190
191 // Bisection method.
192 unsigned ZeroBits = 0;
193 for (T Shift = std::numeric_limits<T>::digits >> 1; Shift; Shift >>= 1) {
194 T Tmp = Val >> Shift;
195 if (Tmp)
196 Val = Tmp;
197 else
198 ZeroBits |= Shift;
199 }
200 return ZeroBits;
201 }
202};
203
204#if defined(__GNUC__4) || defined(_MSC_VER)
205template <typename T> struct LeadingZerosCounter<T, 4> {
206 static unsigned count(T Val) {
207 if (Val == 0)
208 return 32;
209
210#if __has_builtin(__builtin_clz)1 || defined(__GNUC__4)
211 return __builtin_clz(Val);
212#elif defined(_MSC_VER)
213 unsigned long Index;
214 _BitScanReverse(&Index, Val);
215 return Index ^ 31;
216#endif
217 }
218};
219
220#if !defined(_MSC_VER) || defined(_M_X64)
221template <typename T> struct LeadingZerosCounter<T, 8> {
222 static unsigned count(T Val) {
223 if (Val == 0)
224 return 64;
225
226#if __has_builtin(__builtin_clzll)1 || defined(__GNUC__4)
227 return __builtin_clzll(Val);
228#elif defined(_MSC_VER)
229 unsigned long Index;
230 _BitScanReverse64(&Index, Val);
231 return Index ^ 63;
232#endif
233 }
234};
235#endif
236#endif
237} // namespace detail
238
239/// Count number of 0's from the most significant bit to the least
240/// stopping at the first 1.
241///
242/// Only unsigned integral types are allowed.
243///
244/// Returns std::numeric_limits<T>::digits on an input of 0.
245template <typename T> [[nodiscard]] int countl_zero(T Val) {
246 static_assert(std::is_unsigned_v<T>,
247 "Only unsigned integral types are allowed.");
248 return llvm::detail::LeadingZerosCounter<T, sizeof(T)>::count(Val);
249}
250
251/// Count the number of ones from the most significant bit to the first
252/// zero bit.
253///
254/// Ex. countl_one(0xFF0FFF00) == 8.
255/// Only unsigned integral types are allowed.
256///
257/// Returns std::numeric_limits<T>::digits on an input of all ones.
258template <typename T> [[nodiscard]] int countl_one(T Value) {
259 static_assert(std::is_unsigned_v<T>,
260 "Only unsigned integral types are allowed.");
261 return llvm::countl_zero<T>(~Value);
262}
263
264/// Count the number of ones from the least significant bit to the first
265/// zero bit.
266///
267/// Ex. countr_one(0x00FF00FF) == 8.
268/// Only unsigned integral types are allowed.
269///
270/// Returns std::numeric_limits<T>::digits on an input of all ones.
271template <typename T> [[nodiscard]] int countr_one(T Value) {
272 static_assert(std::is_unsigned_v<T>,
273 "Only unsigned integral types are allowed.");
274 return llvm::countr_zero<T>(~Value);
6
←
Calling 'countr_zero<unsigned int>'
→
13
←
Returning from 'countr_zero<unsigned int>'
→
14
←
Returning the value 32
→
275}
276
277/// Returns the number of bits needed to represent Value if Value is nonzero.
278/// Returns 0 otherwise.
279///
280/// Ex. bit_width(5) == 3.
281template <typename T> [[nodiscard]] int bit_width(T Value) {
282 static_assert(std::is_unsigned_v<T>,
283 "Only unsigned integral types are allowed.");
284 return std::numeric_limits<T>::digits - llvm::countl_zero(Value);
285}
286
287/// Returns the largest integral power of two no greater than Value if Value is
288/// nonzero. Returns 0 otherwise.
289///
290/// Ex. bit_floor(5) == 4.
291template <typename T> [[nodiscard]] T bit_floor(T Value) {
292 static_assert(std::is_unsigned_v<T>,
293 "Only unsigned integral types are allowed.");
294 if (!Value)
295 return 0;
296 return T(1) << (llvm::bit_width(Value) - 1);
297}
298
299/// Returns the smallest integral power of two no smaller than Value if Value is
300/// nonzero. Returns 1 otherwise.
301///
302/// Ex. bit_ceil(5) == 8.
303///
304/// The return value is undefined if the input is larger than the largest power
305/// of two representable in T.
306template <typename T> [[nodiscard]] T bit_ceil(T Value) {
307 static_assert(std::is_unsigned_v<T>,
308 "Only unsigned integral types are allowed.");
309 if (Value < 2)
310 return 1;
311 return T(1) << llvm::bit_width<T>(Value - 1u);
312}
313
314namespace detail {
315template <typename T, std::size_t SizeOfT> struct PopulationCounter {
316 static int count(T Value) {
317 // Generic version, forward to 32 bits.
318 static_assert(SizeOfT <= 4, "Not implemented!");
319#if defined(__GNUC__4)
320 return (int)__builtin_popcount(Value);
321#else
322 uint32_t v = Value;
323 v = v - ((v >> 1) & 0x55555555);
324 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
325 return int(((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24);
326#endif
327 }
328};
329
330template <typename T> struct PopulationCounter<T, 8> {
331 static int count(T Value) {
332#if defined(__GNUC__4)
333 return (int)__builtin_popcountll(Value);
334#else
335 uint64_t v = Value;
336 v = v - ((v >> 1) & 0x5555555555555555ULL);
337 v = (v & 0x3333333333333333ULL) + ((v >> 2) & 0x3333333333333333ULL);
338 v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
339 return int((uint64_t)(v * 0x0101010101010101ULL) >> 56);
340#endif
341 }
342};
343} // namespace detail
344
345/// Count the number of set bits in a value.
346/// Ex. popcount(0xF000F000) = 8
347/// Returns 0 if the word is zero.
348template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
349[[nodiscard]] inline int popcount(T Value) noexcept {
350 return detail::PopulationCounter<T, sizeof(T)>::count(Value);
351}
352
353// Forward-declare rotr so that rotl can use it.
354template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
355[[nodiscard]] constexpr T rotr(T V, int R);
356
357template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
358[[nodiscard]] constexpr T rotl(T V, int R) {
359 unsigned N = std::numeric_limits<T>::digits;
360
361 R = R % N;
362 if (!R)
363 return V;
364
365 if (R < 0)
366 return llvm::rotr(V, -R);
367
368 return (V << R) | (V >> (N - R));
369}
370
371template <typename T, typename> [[nodiscard]] constexpr T rotr(T V, int R) {
372 unsigned N = std::numeric_limits<T>::digits;
373
374 R = R % N;
375 if (!R)
376 return V;
377
378 if (R < 0)
379 return llvm::rotl(V, -R);
380
381 return (V >> R) | (V << (N - R));
382}
383
384} // namespace llvm
385
386#endif