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

[kazu]

Summary

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.

[RKSimon]

llvm/unittests/ADT/BitTest.cpp

126

Why not just merge these into a single TEST(BitTest, ByteSwap) ?

[kazu]

I've grouped small tests in this iteration.

[kazu]

Please take a look. Thanks!

llvm/unittests/ADT/BitTest.cpp

126

I've grouped small ones. I've left the ones involving loops untouched as they are a little big.

[RKSimon]

Are you planning to update SwapByteOrder.h to use this?

llvm/include/llvm/ADT/bit.h

66

Looking at SwapByteOrder.h suggests this might need #include <cstdlib>?

74

use has_builtin ?

[kazu]

In D142274#4071228, @RKSimon wrote:

Are you planning to update SwapByteOrder.h to use this?

Yes, and users of getSwappedBytes for integer types.

llvm/include/llvm/ADT/bit.h

74

Shall we stop using the intrinsics and just stick to the ANDs and ORs? This way, we don't have to worry about the availability of intrinsics, the availability of has_builtin itself, whether we are using ICC, etc. (I couldn't find out why ICC is excluded here.) According to compiler explorer, gcc-4.5.3 and clang-10.0.0 generate bswap for the following code snippet:

#include <stdint.h>

uint32_t bs32(uint32_t v) { 
    uint32_t Byte0 = v & 0x000000FF;
    uint32_t Byte1 = v & 0x0000FF00;
    uint32_t Byte2 = v & 0x00FF0000;
    uint32_t Byte3 = v & 0xFF000000;
    return (Byte0 << 24) | (Byte1 << 8) | (Byte2 >> 8) | (Byte3 >> 24);
}

uint64_t bs64(uint64_t v) {
    uint64_t Hi = bs32(v);
    uint32_t Lo = bs32(v >> 32);
    return (Hi << 32) | Lo;
}

clang prior to 10.0.0 does not generate 64-bit bswap, but we don't attempt to use 64-bit bswap intrinsic in this patch or SwapByteOrder.h anyway.

Note that I mention gcc-4.5.3 above, but we require gcc-7.1.0.

[kazu]

In this iteration, I've removed all the dependence on intrinsics
except for the 64-bit case on MSVC, which does not recognize the
idiom.

I'm also including stdlib.h for _byteswap_uint64.

[kazu]

Guarded #include <stdlib.h> with defined(_MSC_VER) && !defined(_DEBUG).

[kazu]

Please take a look. Thanks!

llvm/include/llvm/ADT/bit.h

66

I've added

#if defined(_MSC_VER) && !defined(_DEBUG)
#include <stdlib.h>  // for _byteswap_uint64                                                                           
#endif

74

I've removed the dependence on GCC-style __builtin_xxx, so I don't use __has_builtin,

Both gcc and clang generate good code.

[barannikov88]

llvm/include/llvm/ADT/bit.h

74

According to compiler explorer, gcc-4.5.3 and clang-10.0.0 generate bswap for the following code snippet

They may generate the intrinsic for this sample code, but they also may fail to do so when this function is inlined.
I'd prefer seeing the intrinsic.

[kazu]

I've restored calls to intrinsics in this iteration.

I am now using __has_builtin to check for the availability of
intrinsics.

[kazu]

Please take a look. Thanks!

llvm/include/llvm/ADT/bit.h

74

OK. I've restored the calls to intrinsics.

[barannikov88]

LGTM, thanks.
Please wait for @RKSimon acknowledgement.

[RKSimon]

llvm/include/llvm/ADT/bit.h

74

Shouldn't this be __has_builtin(__builtin_bswap32) ?

88

Shouldn't this be __has_builtin(__builtin_bswap64) ?

[RKSimon]

llvm/include/llvm/ADT/bit.h

24

<cstdlib>

[kazu]

I've switched to ctsdlib from stdlib.h.

I've fixed the names inside __has_builtin.

[dblaikie]

llvm/include/llvm/ADT/bit.h

74

According to compiler explorer, gcc-4.5.3 and clang-10.0.0 generate bswap for the following code snippet

They may generate the intrinsic for this sample code, but they also may fail to do so when this function is inlined.

I'd prefer seeing the intrinsic.

Are there examples of this failing? If not, I'd prefer not to maintain #ifdef'd codepaths that can diverge/introduce build failures that are harder to test (because they don't show up for some people, etc).

Generally we rely on "sufficiently" well-performing compilers (specifically/especially sometimes as aggressively as "clang with LTO") to get good performance out of LLVM, so if Clang gets this right, that's probably enough justification to remove the special case.

[barannikov88]

llvm/include/llvm/ADT/bit.h

74

Are there examples of this failing?

I didn't do actual testing, but this comment suggests that MSVC fails to recognize 64-bit version even when the function is not inlined.

Generally we rely on "sufficiently" well-performing compilers (specifically/especially sometimes as aggressively as "clang with LTO") to get good performance out of LLVM, so if Clang gets this right, that's probably enough justification to remove the special case.

It is possible that expanded version may even perform better than the "builtin" version in some cases. My judgement was only relying on the fact that there are these builtins, so there must have been a good reason for introducing them.

If not, I'd prefer not to maintain #ifdef'd codepaths that can diverge/introduce build failures that are harder to test (because they don't show up for some people, etc).

It is hard to disagree with it. I guess this particular change could rely on compiler optimizations (compared to e.g. popcount below), and that's why I only expressed my personal preference, not a requirement. Should I have marked it as "(optional)" or something like that?

[dblaikie]

llvm/include/llvm/ADT/bit.h

74

Are there examples of this failing?

I didn't do actual testing, but this comment suggests that MSVC fails to recognize 64-bit version even when the function is not inlined.

Yeah, I'd be willing to have slightly worse perf on MSVC really - now that we have clang-cl, a bootstrap would recover the performance, I guess.

Generally we rely on "sufficiently" well-performing compilers (specifically/especially sometimes as aggressively as "clang with LTO") to get good performance out of LLVM, so if Clang gets this right, that's probably enough justification to remove the special case.

It is possible that expanded version may even perform better than the "builtin" version in some cases. My judgement was only relying on the fact that there are these builtins, so there must have been a good reason for introducing them.

There's probably loads of history there - perhaps some folks need it for correctness, maybe in the past compilers couldn't optimize it as well as they can now.

If not, I'd prefer not to maintain #ifdef'd codepaths that can diverge/introduce build failures that are harder to test (because they don't show up for some people, etc).

It is hard to disagree with it. I guess this particular change could rely on compiler optimizations (compared to e.g. popcount below), and that's why I only expressed my personal preference, not a requirement. Should I have marked it as "(optional)" or something like that?

(I think even popcount can be pretty well identified/optimized by clang these days?)

Eh, no worries - not enough I'd bother writing a patch now/arguing for changes later. Would've if this wasn't already committed, but just a thing/note for next time sort of thing.

llvm/include/llvm/ADT/bit.h

 #define LLVM_ADT_BIT_H
 
 #include "llvm/Support/Compiler.h"
 #include <cstdint>
 #include <cstring>
 #include <limits>
 #include <type_traits>
 
+#if defined(_MSC_VER) && !defined(_DEBUG)
+#include <cstdlib>  // for _byteswap_{ushort,ulong,uint64}
+#endif
+
 #ifdef _MSC_VER
 // Declare these intrinsics manually rather including intrin.h. It's very
 // expensive, and bit.h is popular via MathExtras.h.
 // #include <intrin.h>
 extern "C" {
 unsigned char _BitScanForward(unsigned long *_Index, unsigned long _Mask);
 unsigned char _BitScanForward64(unsigned long *_Index, unsigned __int64 _Mask);
 unsigned char _BitScanReverse(unsigned long *_Index, unsigned long _Mask);
template <
     typename = std::enable_if_t<std::is_trivially_copyable<To>::value>,
     typename = std::enable_if_t<std::is_trivially_copyable<From>::value>>
 [[nodiscard]] inline To bit_cast(const From &from) noexcept {
   To to;
   std::memcpy(&to, &from, sizeof(To));
   return to;
 }
 
+/// Reverses the bytes in the given integer value V.
+template <typename T, typename = std::enable_if_t<std::is_integral_v<T>>>
+[[nodiscard]] constexpr T byteswap(T V) noexcept {
+  if constexpr (sizeof(T) == 1) {
+    return V;
+  } else if constexpr (sizeof(T) == 2) {
+    uint16_t UV = V;
+#if defined(_MSC_VER) && !defined(_DEBUG)
+    // The DLL version of the runtime lacks these functions (bug!?), but in a
+    // release build they're replaced with BSWAP instructions anyway.
+    return _byteswap_ushort(UV);
+#else
+    uint16_t Hi = UV << 8;
+    uint16_t Lo = UV >> 8;
+    return Hi | Lo;
+#endif
+  } else if constexpr (sizeof(T) == 4) {
+    uint32_t UV = V;
+#if __has_builtin(__builtin_bswap32)
+    return __builtin_bswap32(UV);
+#elif defined(_MSC_VER) && !defined(_DEBUG)
+    return _byteswap_ulong(UV);
+#else
+    uint32_t Byte0 = UV & 0x000000FF;
+    uint32_t Byte1 = UV & 0x0000FF00;
+    uint32_t Byte2 = UV & 0x00FF0000;
+    uint32_t Byte3 = UV & 0xFF000000;
+    return (Byte0 << 24) | (Byte1 << 8) | (Byte2 >> 8) | (Byte3 >> 24);
+#endif
+  } else if constexpr (sizeof(T) == 8) {
+    uint64_t UV = V;
+#if __has_builtin(__builtin_bswap64)
+    return __builtin_bswap64(UV);
+#elif defined(_MSC_VER) && !defined(_DEBUG)
+    return _byteswap_uint64(UV);
+#else
+    uint64_t Hi = llvm::byteswap<uint32_t>(UV);
+    uint32_t Lo = llvm::byteswap<uint32_t>(UV >> 32);
+    return (Hi << 32) | Lo;
+#endif
+  } else {
+    static_assert(!sizeof(T *), "Don't know how to handle the given type.");
+    return 0;
+  }
+}
+
 template <typename T, typename = std::enable_if_t<std::is_unsigned_v<T>>>
 [[nodiscard]] constexpr inline bool has_single_bit(T Value) noexcept {
   return (Value != 0) && ((Value & (Value - 1)) == 0);
 }
 
 namespace detail {
 template <typename T, std::size_t SizeOfT> struct TrailingZerosCounter {
   static unsigned count(T Val) {

llvm/unittests/ADT/BitTest.cpp

TEST(BitTest, BitCast) {
   EXPECT_FLOAT_EQ(kValueF32,
                   llvm::bit_cast<float>(llvm::bit_cast<uint32_t>(kValueF32)));
 
   static const double kValueF64 = 87987234.983498;
   EXPECT_DOUBLE_EQ(kValueF64,
                    llvm::bit_cast<double>(llvm::bit_cast<uint64_t>(kValueF64)));
 }
 
+// In these first two tests all of the original_uintx values are truncated
+// except for 64. We could avoid this, but there's really no point.
+
+TEST(BitTest, ByteSwapUnsignedRoundTrip) {
+  // The point of the bit twiddling of magic is to test with and without bits
+  // in every byte.
+  uint64_t value = 1;
+  for (std::size_t i = 0; i <= sizeof(value); ++i) {
+    uint8_t original_uint8 = static_cast<uint8_t>(value);
+    EXPECT_EQ(original_uint8, llvm::byteswap(llvm::byteswap(original_uint8)));
+
+    uint16_t original_uint16 = static_cast<uint16_t>(value);
+    EXPECT_EQ(original_uint16, llvm::byteswap(llvm::byteswap(original_uint16)));
+
+    uint32_t original_uint32 = static_cast<uint32_t>(value);
+    EXPECT_EQ(original_uint32, llvm::byteswap(llvm::byteswap(original_uint32)));
+
+    uint64_t original_uint64 = static_cast<uint64_t>(value);
+    EXPECT_EQ(original_uint64, llvm::byteswap(llvm::byteswap(original_uint64)));
+
+    value = (value << 8) | 0x55; // binary 0101 0101.
+  }
+}
+
+TEST(BitTest, ByteSwapSignedRoundTrip) {
+  // The point of the bit twiddling of magic is to test with and without bits
+  // in every byte.
+  uint64_t value = 1;
+  for (std::size_t i = 0; i <= sizeof(value); ++i) {
+    int8_t original_int8 = static_cast<int8_t>(value);
+    EXPECT_EQ(original_int8, llvm::byteswap(llvm::byteswap(original_int8)));
+
+    int16_t original_int16 = static_cast<int16_t>(value);
+    EXPECT_EQ(original_int16, llvm::byteswap(llvm::byteswap(original_int16)));
+
+    int32_t original_int32 = static_cast<int32_t>(value);
+    EXPECT_EQ(original_int32, llvm::byteswap(llvm::byteswap(original_int32)));
+
+    int64_t original_int64 = static_cast<int64_t>(value);
+    EXPECT_EQ(original_int64, llvm::byteswap(llvm::byteswap(original_int64)));
+
+    // Test other sign.
+    value *= -1;
+
+    original_int8 = static_cast<int8_t>(value);
+    EXPECT_EQ(original_int8, llvm::byteswap(llvm::byteswap(original_int8)));
+
+    original_int16 = static_cast<int16_t>(value);
+    EXPECT_EQ(original_int16, llvm::byteswap(llvm::byteswap(original_int16)));
+
+    original_int32 = static_cast<int32_t>(value);
+    EXPECT_EQ(original_int32, llvm::byteswap(llvm::byteswap(original_int32)));
+
+    original_int64 = static_cast<int64_t>(value);
+    EXPECT_EQ(original_int64, llvm::byteswap(llvm::byteswap(original_int64)));
+
+    // Return to normal sign and twiddle.
+    value *= -1;
+    value = (value << 8) | 0x55; // binary 0101 0101.
+  }
+}
+
+TEST(BitTest, ByteSwap) {
+  // Unsigned types.
+  EXPECT_EQ(uint8_t(0x11), llvm::byteswap(uint8_t(0x11)));
+  EXPECT_EQ(uint16_t(0x1122), llvm::byteswap(uint16_t(0x2211)));
+  EXPECT_EQ(uint32_t(0x11223344), llvm::byteswap(uint32_t(0x44332211)));
+  EXPECT_EQ(uint64_t(0x1122334455667788ULL),
+            llvm::byteswap(uint64_t(0x8877665544332211ULL)));
+
+  // Signed types.
+  EXPECT_EQ(int8_t(0x11), llvm::byteswap(int8_t(0x11)));
+  EXPECT_EQ(int16_t(0x1122), llvm::byteswap(int16_t(0x2211)));
+  EXPECT_EQ(int32_t(0x11223344), llvm::byteswap(int32_t(0x44332211)));
+  EXPECT_EQ(int64_t(0x1122334455667788LL),
+            llvm::byteswap(int64_t(0x8877665544332211LL)));
+}
+
 TEST(BitTest, HasSingleBit) {
   EXPECT_FALSE(llvm::has_single_bit(0U));
   EXPECT_FALSE(llvm::has_single_bit(0ULL));
 
   EXPECT_FALSE(llvm::has_single_bit(~0U));
   EXPECT_FALSE(llvm::has_single_bit(~0ULL));
 
   EXPECT_TRUE(llvm::has_single_bit(1U));
   EXPECT_TRUE(llvm::has_single_bit(1ULL));
 
   static const int8_t kValueS8 = -128;
   EXPECT_TRUE(llvm::has_single_bit(static_cast<uint8_t>(kValueS8)));
 
   static const int16_t kValueS16 = -32768;
   EXPECT_TRUE(llvm::has_single_bit(static_cast<uint16_t>(kValueS16)));
 }
 
 TEST(BitTest, BitFloor) {
   EXPECT_EQ(0u, llvm::bit_floor(uint8_t(0)));
   EXPECT_EQ(0u, llvm::bit_floor(uint16_t(0)));
   EXPECT_EQ(0u, llvm::bit_floor(uint32_t(0)));
   EXPECT_EQ(0u, llvm::bit_floor(uint64_t(0)));