[libc] Specialize portion of hypot for x86_64 CPUs.

[cratonica]

Summary

This changes leverages the BSR instruction to find the leading 1 bit, reducing
what was previously an iterative look-up-table approach to a single
instruction on supported CPUs.

[lntue]

libc/src/__support/find_leading_one.h

26

Is the BSR instruction available for x86 also? If so then I think LLVM_LIBC_ARCH_X86 should be better. And if that's the case, you can just leave the implementation in the x86_64 folder, I don't think we need separate folders for x86 and x86-64.

[cratonica]

libc/src/__support/find_leading_one.h

26

My understanding is that we'd be limited to 32-bit operands in that case and would therefore need to make this conditional upon both the size of the data and the architecture, which might be messier (so, x86 would drop back to the generic implementation for 64-bit numbers, or I suppose I could implement it as two BSR calls if it's possible to test this in 32-bit mode).

Happy to do whatever you think is best.

[lntue]

libc/src/__support/find_leading_one.h

26

If that's the case then I'm fine with the current specialization. We can always specialize further if there are requests for non-64-bit x86 arch.

[sivachandra]

libc/src/__support/x86_64/find_leading_one.h

20

Nit: msbit_pos is probably a more appropriate name?

28–31

It seems to me like one can use __builtin_clz and avoid target assembly? For example: https://godbolt.org/z/eY8n8P118

[cratonica]

libc/src/__support/x86_64/find_leading_one.h

28–31

Nice, that also works for ARM: https://godbolt.org/z/bY9nfEd16

Are we OK using such builtins in this library ? If so, should we get rid of the original find_leading_one() function altogether and just call __builtin_clz ? Or should it still be specialized for each architecture and delegate at that level?

[sivachandra]

libc/src/__support/x86_64/find_leading_one.h

28–31

Yes, it is OK to use compiler builtins for this use case. We can get rid of the original find_leading_one.

[cratonica]

libc/src/__support/x86_64/find_leading_one.h

28–31

Sent https://reviews.llvm.org/D117684

[lntue]

libc/src/__support/x86_64/find_leading_one.h

28–31

Normally you could just amend the commit and update the patch review with $ arc diff --update D.... instead of creating a new one, unless you want to keep the old review around.

[cratonica]

libc/src/__support/x86_64/find_leading_one.h

28–31

I'd like to hang onto it for a few reasons:

• This approach is much different, so I wanted to require you to approve it again rather than sneaking in an entirely new approach under the radar
  • The diff between revisions would be messy, since the new code is much closer to HEAD than it is to where this branch (all new unit tests and the refactor to its own library would be deleted)
  • I'd like to be able to reference the original revision in the future.

That being said, I don't want to deviate from the norms used by LLVM, so I can amend it here if you'd prefer.

[lntue]

libc/src/__support/x86_64/find_leading_one.h

28–31

It's totally fine to me to have the a separate review patch, especially when you want to refer back to the original one in the future. Just a few comments about how Phabricator works as I know of:

• If there is any update to the patch, I'd need to re-approve again (you will see that any accepted tick next reviewers will be changed from green to gray)
• If you amend the commit, Phabricator will show the diff between the latest change and HEAD by default. But it still records all of your previous revisions (each time you run arc diff --update), and we can selectively diff between them if we want to.
• But yes, the default workflow from LLVM is a bit different from normal git workflow, where they prefer to have a single commit for each patch, and having their code review tools revolve around that.

[cratonica]

Superseded by https://reviews.llvm.org/D117684

libc/src/__support/CMakeLists.txt

 
 add_header_library(
   ctype_utils
   HDRS
     ctype_utils.h
 )
 
 add_header_library(
+  find_leading_one
+  HDRS
+    find_leading_one.h
+)
+
+add_header_library(
   high_precision_decimal
   HDRS
     high_precision_decimal.h
 
 )
 
 add_header_library(
   str_to_integer

libc/src/__support/FPUtil/CMakeLists.txt

HDRS
     BasicOperations.h
     ManipulationFunctions.h
     NearestIntegerOperations.h
     NormalFloat.h
     PlatformDefs.h
     PolyEval.h
     UInt.h
     XFloat.h
+    Hypot.h
   DEPENDS
     libc.include.math
     libc.include.errno
     libc.include.fenv
     libc.src.__support.common
+    libc.src.__support.find_leading_one
     libc.src.__support.CPP.standalone_cpp
 )

libc/src/__support/FPUtil/Hypot.h

 //===-- Implementation of hypotf function ---------------------------------===//
 //
 // 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_FPUTIL_HYPOT_H
 #define LLVM_LIBC_SRC_SUPPORT_FPUTIL_HYPOT_H
 
 #include "BasicOperations.h"
 #include "FPBits.h"
 #include "src/__support/CPP/TypeTraits.h"
+#include "src/__support/find_leading_one.h"
 
 namespace __llvm_libc {
 namespace fputil {
 
-namespace internal {
-
-template <typename T>
-static inline T find_leading_one(T mant, int &shift_length);
-
-template <>
-inline uint32_t find_leading_one<uint32_t>(uint32_t mant, int &shift_length) {
-  shift_length = 0;
-  constexpr int NSTEPS = 5;
-  constexpr uint32_t BOUNDS[NSTEPS] = {1 << 16, 1 << 8, 1 << 4, 1 << 2, 1 << 1};
-  constexpr int SHIFTS[NSTEPS] = {16, 8, 4, 2, 1};
-  for (int i = 0; i < NSTEPS; ++i) {
-    if (mant >= BOUNDS[i]) {
-      shift_length += SHIFTS[i];
-      mant >>= SHIFTS[i];
-    }
-  }
-  return 1U << shift_length;
-}
-
-template <>
-inline uint64_t find_leading_one<uint64_t>(uint64_t mant, int &shift_length) {
-  shift_length = 0;
-  constexpr int NSTEPS = 6;
-  constexpr uint64_t BOUNDS[NSTEPS] = {1ULL << 32, 1ULL << 16, 1ULL << 8,
-                                       1ULL << 4,  1ULL << 2,  1ULL << 1};
-  constexpr int SHIFTS[NSTEPS] = {32, 16, 8, 4, 2, 1};
-  for (int i = 0; i < NSTEPS; ++i) {
-    if (mant >= BOUNDS[i]) {
-      shift_length += SHIFTS[i];
-      mant >>= SHIFTS[i];
-    }
-  }
-  return 1ULL << shift_length;
-}
-
-} // namespace internal
-
 template <typename T> struct DoubleLength;
 
 template <> struct DoubleLength<uint16_t> { using Type = uint32_t; };
 
 template <> struct DoubleLength<uint32_t> { using Type = uint64_t; };
 
 template <> struct DoubleLength<uint64_t> { using Type = __uint128_t; };
 
static inline T hypot(T x, T y) {
 
   UIntType leading_one;
   int y_mant_width;
   if (a_exp != 0) {
     leading_one = ONE;
     a_mant |= ONE;
     y_mant_width = MantissaWidth<T>::VALUE + 1;
   } else {
-    leading_one = internal::find_leading_one(a_mant, y_mant_width);
+    y_mant_width = __llvm_libc::internal::find_leading_one(a_mant);
+    leading_one = UIntType(1) << y_mant_width;
     a_exp = 1;
   }
 
   if (b_exp != 0) {
     b_mant |= ONE;
   } else {
     b_exp = 1;
   }

libc/src/__support/find_leading_one.h

+//===-- Utility for finding position of leading 1 in integer ----*- C++ -*-===//
+//
+// 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_FIND_LEADING_ONE_H
+#define LLVM_LIBC_SRC_SUPPORT_FIND_LEADING_ONE_H
+
+#include "src/__support/architectures.h"
+
+namespace __llvm_libc {
+namespace internal {
+/// Finds the position of the most-significant 1 bit in the given integer.
+///
+/// \param value the integer to scan. Should be a positive number.
+///
+/// \returns the position of the bit as an offset from the LSB (e.g., passing
+//   0b0101 would return 2). Returns 0 on domain error (e.g., if 0 is passed).
+template <typename T> static inline int find_leading_one(T value);
+} // namespace internal
+} // namespace __llvm_libc
+
+#if defined(LLVM_LIBC_ARCH_X86_64)
+#include "src/__support/x86_64/find_leading_one.h"
+#else
+#include "src/__support/generic/find_leading_one.h"
+#endif
+
+#endif // LLVM_LIBC_SRC_SUPPORT_FIND_LEADING_ONE_H

libc/src/__support/generic/find_leading_one.h

+//===-- Utility for finding position of leading 1 in integer ----*- C++ -*-===//
+//
+// 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_GENERIC_FIND_LEADING_ONE_H
+#define LLVM_LIBC_SRC_SUPPORT_GENERIC_FIND_LEADING_ONE_H
+
+#include "src/__support/CPP/TypeTraits.h"
+#include <stdint.h>
+
+template <>
+inline int __llvm_libc::internal::find_leading_one<uint32_t>(uint32_t value) {
+  int shift_length = 0;
+  constexpr int NSTEPS = 5;
+  constexpr uint32_t BOUNDS[NSTEPS] = {1 << 16, 1 << 8, 1 << 4, 1 << 2, 1 << 1};
+  constexpr int SHIFTS[NSTEPS] = {16, 8, 4, 2, 1};
+  for (int i = 0; i < NSTEPS; ++i) {
+    if (value >= BOUNDS[i]) {
+      shift_length += SHIFTS[i];
+      value >>= SHIFTS[i];
+    }
+  }
+  return shift_length;
+}
+
+template <>
+inline int __llvm_libc::internal::find_leading_one<uint64_t>(uint64_t value) {
+  int shift_length = 0;
+  constexpr int NSTEPS = 6;
+  constexpr uint64_t BOUNDS[NSTEPS] = {1ULL << 32, 1ULL << 16, 1ULL << 8,
+                                       1ULL << 4,  1ULL << 2,  1ULL << 1};
+  constexpr int SHIFTS[NSTEPS] = {32, 16, 8, 4, 2, 1};
+  for (int i = 0; i < NSTEPS; ++i) {
+    if (value >= BOUNDS[i]) {
+      shift_length += SHIFTS[i];
+      value >>= SHIFTS[i];
+    }
+  }
+  return shift_length;
+}
+
+#endif // LLVM_LIBC_SRC_SUPPORT_GENERIC_FIND_LEADING_ONE_H

libc/src/__support/x86_64/find_leading_one.h

+//===-- Utility for finding position of leading 1 in integer ----*- C++ -*-===//
+//
+// 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_X86_64_FIND_LEADING_ONE_H
+#define LLVM_LIBC_SRC_SUPPORT_X86_64_FIND_LEADING_ONE_H
+
+#include "src/__support/CPP/TypeTraits.h"
+#include <stdint.h>
+
+#if !defined(LLVM_LIBC_ARCH_X86_64)
+#error Must be LLVM_LIBC_ARCH_X86_64 to include this file
+#endif
+
+template <typename T>
+inline int __llvm_libc::internal::find_leading_one(T value) {
+  static_assert(
+      cpp::IsSame<T, uint32_t>::Value || cpp::IsSame<T, uint64_t>::Value, "");
+
+  if (value == 0) {
+    return 0;
+  }
+
+  __asm__("bsr %[value], %[value]"
+          : [value] "=r"(value)
+          : "0"(value)
+          : "flags"); // Clobbers ZF
+
+  return static_cast<int>(value);
+}
+
+#endif // LLVM_LIBC_SRC_SUPPORT_X86_64_FIND_LEADING_ONE_H

libc/test/src/__support/CMakeLists.txt

 add_libc_testsuite(libc_support_unittests)
 
 add_libc_unittest(
   endian_test
   SUITE
     libc_support_unittests
   SRCS
     endian_test.cpp
   DEPENDS
     libc.src.__support.common
 )
 
 add_libc_unittest(
+  find_leading_one_test
+  SUITE
+    libc_support_unittests
+  SRCS
+    find_leading_one_test.cpp
+  DEPENDS
+    libc.src.__support.find_leading_one
+)
+
+add_libc_unittest(
   high_precision_decimal_test
   SUITE
     libc_support_unittests
   SRCS
   high_precision_decimal_test.cpp
   DEPENDS
     libc.src.__support.high_precision_decimal
 )

libc/test/src/__support/find_leading_one_test.cpp

+//===-- Unittests for find_leading_one ------------------------------------===//
+//
+// 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/find_leading_one.h"
+#include "utils/UnitTest/Test.h"
+#include <climits>
+
+namespace __llvm_libc {
+
+struct LlvmLibcFindLeadingOne : testing::Test {
+  template <typename T> void exhaustive_test() {
+    for (std::size_t i = 0; i < sizeof(T) * CHAR_BIT; i++) {
+      const T value = static_cast<T>(1ULL << i);
+      EXPECT_EQ(internal::find_leading_one(value), static_cast<int>(i));
+    }
+  }
+};
+
+TEST_F(LlvmLibcFindLeadingOne, Zero) {
+  EXPECT_EQ(internal::find_leading_one(0U), 0);
+}
+
+TEST_F(LlvmLibcFindLeadingOne, One) {
+  EXPECT_EQ(internal::find_leading_one(1U), 0);
+}
+
+TEST_F(LlvmLibcFindLeadingOne, Two) {
+  EXPECT_EQ(internal::find_leading_one(2U), 1);
+}
+
+TEST_F(LlvmLibcFindLeadingOne, Three) {
+  EXPECT_EQ(internal::find_leading_one(3U), 1);
+}
+
+TEST_F(LlvmLibcFindLeadingOne, Exhaustive32Bit) { exhaustive_test<uint32_t>(); }
+
+TEST_F(LlvmLibcFindLeadingOne, Exhaustive64Bit) { exhaustive_test<uint64_t>(); }
+
+} // namespace __llvm_libc