[ADT] Add llvm::rotl and llvm::rotr to bit.h

Differential Revision: https://reviews.llvm.org/D143882

[ADT] Add llvm::byteswap to bit.h

This patch adds C++23-style byteswap to bit.h.

The implementation and tests are largely taken from
llvm/include/llvm/Support/SwapByteOrder.h and
llvm/unittests/Sup

[ADT] Add llvm::byteswap to bit.h

This patch adds C++23-style byteswap to bit.h.

The implementation and tests are largely taken from
llvm/include/llvm/Support/SwapByteOrder.h and
llvm/unittests/Support/SwapByteOrderTest.cpp, respectively.

Differential Revision: https://reviews.llvm.org/D142274

show more ...

[ADT] Add bit_floor, bit_ceil, and bit_width to bit.h

This patch adds C++20-style bit_floor, bit_ceil, and bit_width.

In a subsequent patch, I'm going to define PowerOf2Floor in
MathExtras.h in ter

[ADT] Add bit_floor, bit_ceil, and bit_width to bit.h

This patch adds C++20-style bit_floor, bit_ceil, and bit_width.

In a subsequent patch, I'm going to define PowerOf2Floor in
MathExtras.h in terms of bit_floor.

Unfortunately, PowerOf2Ceil isn't quite the same as bit_ceil because
PowerOf2Ceil(0) == 0, whereas bit_ceil(0) == 1.

MathExtras.h does not have a function directly corresponding to
bit_width, but Log2_32(X) + 1, which occurs in a few places, can be
replaced with bit_width(X).

Differential Revision: https://reviews.llvm.org/D142179

show more ...

Reland: Drop the ZeroBehavior parameter from countLeadingZeros and the like (NFC)

This patch drops the ZeroBehavior parameter from bit counting
functions like countLeadingZeros. ZeroBehavior specif

Reland: Drop the ZeroBehavior parameter from countLeadingZeros and the like (NFC)

This patch drops the ZeroBehavior parameter from bit counting
functions like countLeadingZeros. ZeroBehavior specifies the behavior
when the input to count{Leading,Trailing}Zeros is zero and when the
input to count{Leading,Trailing}Ones is all ones.

ZeroBehavior was first introduced on May 24, 2013 in commit
eb91eac9fb866ab1243366d2e238b9961895612d. While that patch did not
state the intention, I would guess ZeroBehavior was for performance
reasons. The x86 machines around that time required a conditional
branch to implement countLeadingZero<uint32_t> that returns the 32 on
zero:

test edi, edi
je .LBB0_2
bsr eax, edi
xor eax, 31
.LBB1_2:
mov eax, 32

That is, we can remove the conditional branch if we don't care about
the behavior on zero.

IIUC, Intel's Haswell architecture, launched on June 4, 2013,
introduced several bit manipulation instructions, including lzcnt and
tzcnt, which eliminated the need for the conditional branch.

I think it's time to retire ZeroBehavior as its utility is very
limited. If you care about compilation speed, you should build LLVM
with an appropriate -march= to take advantage of lzcnt and tzcnt.
Even if not, modern host compilers should be able to optimize away
quite a few conditional branches because the input is often known to
be nonzero from dominating conditional branches.

In this iteration, I've moved the forward declarations of
_BitScanForward outside the llvm space to fix builds on Windows.

Differential Revision: https://reviews.llvm.org/D141798

show more ...

Revert "[llvm] Move bit counting functions to bit.h (NFC)"

This reverts commit f37614b25ccaa9c0710cc8a4fc2ba2fb0fcb9159.
Doesn't build on Windows: https://reviews.llvm.org/D142078#4068417

[llvm] Move bit counting functions to bit.h (NFC)

This patch provides C++20-style countl_zero, countr_zero, countl_one,
and countr_one in bit.h. Existing functions like countLeadingZeros
become wra

[llvm] Move bit counting functions to bit.h (NFC)

This patch provides C++20-style countl_zero, countr_zero, countl_one,
and countr_one in bit.h. Existing functions like countLeadingZeros
become wrappers around the new functions.

Note that I cannot quite declare countLeadingZeros as:

template <class T> using countLeadingZeros = countl_zero<T>;

because countl_zero returns int, whereas countLeadingZeros returns
unsigned.

Differential Revision: https://reviews.llvm.org/D142078

show more ...

[ADT] Add llvm::has_single_bit helper similar to the c++20 std::has_single_bit implementation

Converted the llvm::isPowerOf2_32/64 helpers into wrappers

[ADT] Add unittest coverage for ADT/bit.h header