[libc.search] [PATCH 2/6] add ctz/clz for unsigned short

[SchrodingerZhu]

Summary

This patch adds support for calculating ctz/clz of unsigned short.
The idea is to use builtin_clzs/builtin_ctzs when available
or fallback to use unsigned int version with additional bit number
manipulations.

[gchatelet]

What would be the use case here?
I'd rather keep these functions to what's strictly required. The smallest the code base, the better.

[SchrodingerZhu]

@gchatelet Hi, this is intended to be used in https://reviews.llvm.org/D136490. SSE2 movemask operations on byte vectors will give 16-bit masks and we want to use that to locate available bucket slot in hash table.

[gchatelet]

In D136488#3880100, @SchrodingerZhu wrote:

@gchatelet Hi, this is intended to be used in https://reviews.llvm.org/D136490. SSE2 movemask operations on byte vectors will give 16-bit masks and we want to use that to locate available bucket slot in hash table.

I see, thx for the context.

I would like to get some tests as well.

Also __has_builtin only exists from gcc 10.0 on. You first need to check that it is defined first.

libc/src/__support/builtin_wrappers.h

50

sizeof is a function not a template, these should be parentheses and not brackets.

68

This is supposed to be __builtin_ctz right?

[SchrodingerZhu]

Address code reviews:

• fix silly bugs created during my dream walking.
• add unit tests

[gchatelet]

Thx!

[SchrodingerZhu]

Rebase

[SchrodingerZhu]

Rebase

[gchatelet]

@SchrodingerZhu are you planning to land this patch?
If so you'd need to use LLVM_LIBC_HAS_BUILTIN from libc/src/__support/compiler_features.h.

libc/src/__support/builtin_wrappers.h

 //===--Convenient template for builtins -------------------------*- C++ -*-===//
 //             (Count Lead Zeroes) and (Count Trailing Zeros)
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIBC_SRC_SUPPORT_BUILTIN_WRAPPERS_H
 #define LLVM_LIBC_SRC_SUPPORT_BUILTIN_WRAPPERS_H
 
 #include "named_pair.h"
 #include "src/__support/CPP/type_traits.h"
 #include "src/__support/compiler_features.h"
 
+#if defined __has_builtin
+#if __has_builtin(__builtin_clzs)
+#define LLVM_LIBC_HAS_BUILTIN_CLZS
+#endif
+#endif
+
+#if defined __has_builtin
+#if __has_builtin(__builtin_ctzs)
+#define LLVM_LIBC_HAS_BUILTIN_CTZS
+#endif
+#endif
+
 namespace __llvm_libc {
 
 // The following overloads are matched based on what is accepted by
 // __builtin_clz/ctz* rather than using the exactly-sized aliases from stdint.h.
 // This way, we can avoid making any assumptions about integer sizes and let the
 // compiler match for us.
 namespace __internal {
 
 template <typename T> static inline int correct_zero(T val, int bits) {
   if (val == T(0))
     return sizeof(T(0)) * 8;
   else
     return bits;
 }
 
 template <typename T> static inline int clz(T val);
+template <> inline int clz<unsigned short>(unsigned short val) {
+#if defined LLVM_LIBC_HAS_BUILTIN_CLZS
+  return __builtin_clzs(val);
+#else
+  return __builtin_clz(static_cast<unsigned int>(val)) -
+         8 * (sizeof(unsigned int) - sizeof(unsigned short));
+#endif
+}
 template <> inline int clz<unsigned int>(unsigned int val) {
   return __builtin_clz(val);
 }
 template <> inline int clz<unsigned long int>(unsigned long int val) {
   return __builtin_clzl(val);
 }
 template <> inline int clz<unsigned long long int>(unsigned long long int val) {
   return __builtin_clzll(val);
 }
 
 template <typename T> static inline int ctz(T val);
+template <> inline int ctz<unsigned short>(unsigned short val) {
+#if defined LLVM_LIBC_HAS_BUILTIN_CTZS
+  return __builtin_ctzs(val);
+#else
+  return __builtin_ctz(static_cast<unsigned int>(val));
+#endif
+}
 template <> inline int ctz<unsigned int>(unsigned int val) {
   return __builtin_ctz(val);
 }
 template <> inline int ctz<unsigned long int>(unsigned long int val) {
   return __builtin_ctzl(val);
 }
 template <> inline int ctz<unsigned long long int>(unsigned long long int val) {
   return __builtin_ctzll(val);

libc/test/src/__support/CMakeLists.txt

add_libc_unittest(
   SUITE
     libc_support_unittests
   SRCS
     fixedvector_test.cpp
   DEPENDS
     libc.src.__support.fixedvector
 )
 
+add_libc_unittest(
+  builtin_wrappers_test
+  SUITE
+    libc_support_unittests
+  SRCS
+    builtin_wrappers_test.cpp
+  DEPENDS
+    libc.src.__support.builtin_wrappers
+    libc.src.__support.CPP.limits
+)
+
 add_executable(
   libc_str_to_float_comparison_test
   str_to_float_comparison_test.cpp
 )
 
 target_link_libraries(libc_str_to_float_comparison_test
   PRIVATE
     "${LIBC_TARGET}"

libc/test/src/__support/builtin_wrappers_test.cpp

+//===-- Unittests for Builtin Wrappers ------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "src/__support/CPP/limits.h"
+#include "src/__support/builtin_wrappers.h"
+#include "utils/UnitTest/LibcTest.h"
+
+namespace __llvm_libc {
+
+template <class T> static int trivial_ctz(T x) {
+  size_t i = 0;
+  while (i < 8 * sizeof(T)) {
+    if (x & 1)
+      break;
+    i++;
+    x >>= 1;
+  }
+  return static_cast<int>(i);
+}
+
+template <class T> static int trivial_clz(T x) {
+  size_t i = 0;
+  while (x != 0) {
+    i++;
+    x >>= 1;
+  }
+  return 8 * sizeof(T) - static_cast<int>(i);
+}
+
+template <class T, int (&Trivial)(T), int (&Safe)(T), int (&Unsafe)(T)>
+struct LlvmLibcBuiltinWrapperZeroCount : testing::Test {
+  using Type = T;
+  void check_all(const T min, const T max) {
+
+    for (T i = min; i <= max; i++) {
+      if (i != 0) {
+        ASSERT_EQ(Trivial(i), Unsafe(i));
+      }
+      ASSERT_EQ(Trivial(i), Safe(i));
+      if (i == max)
+        break;
+    }
+  }
+  void per_byte() {
+    for (size_t i = 0; i < sizeof(T); ++i) {
+      for (T j = 0; j <= 0xFF; ++j) {
+        T target = j << (8 * i);
+        if (target != 0) {
+          ASSERT_EQ(Trivial(target), Unsafe(target));
+        }
+        ASSERT_EQ(Trivial(target), Safe(target));
+      }
+    }
+  }
+};
+
+template <class T>
+using LlvmLibcBuiltinWrapperClz =
+    LlvmLibcBuiltinWrapperZeroCount<T, trivial_clz<T>, safe_clz<T>,
+                                    unsafe_clz<T>>;
+
+template <class T>
+using LlvmLibcBuiltinWrapperCtz =
+    LlvmLibcBuiltinWrapperZeroCount<T, trivial_ctz<T>, safe_ctz<T>,
+                                    unsafe_ctz<T>>;
+
+using LlvmLibcBuiltinWrapperUnsignedShortClz =
+    LlvmLibcBuiltinWrapperClz<unsigned short>;
+
+using LlvmLibcBuiltinWrapperUnsignedShortCtz =
+    LlvmLibcBuiltinWrapperCtz<unsigned short>;
+
+using LlvmLibcBuiltinWrapperUnsignedIntClz =
+    LlvmLibcBuiltinWrapperClz<unsigned int>;
+
+using LlvmLibcBuiltinWrapperUnsignedIntCtz =
+    LlvmLibcBuiltinWrapperCtz<unsigned int>;
+
+using LlvmLibcBuiltinWrapperUnsignedLongClz =
+    LlvmLibcBuiltinWrapperClz<unsigned long>;
+
+using LlvmLibcBuiltinWrapperUnsignedLongCtz =
+    LlvmLibcBuiltinWrapperCtz<unsigned long>;
+
+using LlvmLibcBuiltinWrapperUnsignedLongLongClz =
+    LlvmLibcBuiltinWrapperClz<unsigned long long>;
+
+using LlvmLibcBuiltinWrapperUnsignedLongLongCtz =
+    LlvmLibcBuiltinWrapperCtz<unsigned long long>;
+
+TEST_F(LlvmLibcBuiltinWrapperUnsignedShortClz, CheckAll) {
+  check_all(cpp::numeric_limits<Type>::min(), cpp::numeric_limits<Type>::max());
+}
+
+TEST_F(LlvmLibcBuiltinWrapperUnsignedShortCtz, CheckAll) {
+  check_all(cpp::numeric_limits<Type>::min(), cpp::numeric_limits<Type>::max());
+}
+
+TEST_F(LlvmLibcBuiltinWrapperUnsignedIntClz, CheckPerByte) { per_byte(); }
+
+TEST_F(LlvmLibcBuiltinWrapperUnsignedIntCtz, CheckPerByte) { per_byte(); }
+
+TEST_F(LlvmLibcBuiltinWrapperUnsignedLongClz, CheckPerByte) { per_byte(); }
+
+TEST_F(LlvmLibcBuiltinWrapperUnsignedLongCtz, CheckPerByte) { per_byte(); }
+
+TEST_F(LlvmLibcBuiltinWrapperUnsignedLongLongClz, CheckPerByte) { per_byte(); }
+
+TEST_F(LlvmLibcBuiltinWrapperUnsignedLongLongCtz, CheckPerByte) { per_byte(); }
+
+} // namespace __llvm_libc