[libc] Use __builtin_clz to find leading 1 in hypot

[cratonica]

Summary

This is an optimization that using a single CPU instruction on supported
architectures (amd64 and aarch64, but possibly others) to replace what was
previously an iterative look-up-table algorithm.

Originally I suggested using inline assembly for this in
https://reviews.llvm.org/D117584.

[lntue]

libc/src/__support/FPUtil/Hypot.h

26

builtin_clzl is just extended to either builtin_clz or builtin_clzll depending on the size of unsigned long. It might be better to keep uint32_t and uint64_t specializations and directly use __builtin_clz for uint32_t, builtin_clzll for uint64_t, together with static_assert(sizeof(unsigned int) == 4) and static_assert(sizeof(unsigned long long) == 8) instead?

[sivachandra]

libc/src/__support/FPUtil/Hypot.h

26

Considering that uint32_t and uint64_t are just type sugar and not actual types, the existing code seems to me like the best approach and keeps it really straighforward with no assumptions of any sizes.

35

Use a pattern like sizeof(unsigned int) - 1 instead of hard coding here and below. For, in the unsigned long case, 63 - <...>can be more than the width of unsigned long.

[lntue]

libc/src/__support/FPUtil/Hypot.h

26

If using this pattern then the output type for unsigned int should be kept as unsigned int, and I agree that we should use sizeof(...)*8 - 1 instead of hard-coded values.

[cratonica]

Use sizeof instead of assuming width of types

[cratonica]

Thanks, PTAL

libc/src/__support/FPUtil/Hypot.h

26

Yes, sorry for that oversight. I originally used the uintxx_t values until I pivoted to using the non-aliased types, but forgot to drop the assumptions about bit width after that change.

35

Note that this assumes CHAR_BIT is 8, but I can't #include <climits> according to the lint rules.

[cratonica]

Fix bitwidth assumption on long long as well

[sivachandra]

libc/src/__support/FPUtil/Hypot.h

31–32

Nit: Use unsigned int here?

35

Assuming that a byte is 8 bits wide is going to be almost always right on real world systems :)

[cratonica]

s/uint32_t/unsigned int/ on return type for find_leading_one

[cratonica]

Thanks for the review. Since I don't yet have repo access, could someone please commit this on my behalf per https://llvm.org/docs/Phabricator.html#committing-someone-s-change-from-phabricator ?

Thanks.

[lntue]

In D117684#3258342, @cratonica wrote:

Thanks for the review. Since I don't yet have repo access, could someone please commit this on my behalf per https://llvm.org/docs/Phabricator.html#committing-someone-s-change-from-phabricator ?

Thanks.

You can check with @sivachandra about the process to obtain access to llvm repo.

[sivachandra]

I will submit this for you shortly.

libc/src/__support/FPUtil/Hypot.h

 namespace __llvm_libc {
 namespace fputil {
 
 namespace internal {
 
 template <typename T>
 static inline T find_leading_one(T mant, int &shift_length);
 
+// The following overloads are matched based on what is accepted by
+// __builtin_clz* rather than using the exactly-sized aliases from stdint.h
+// (such as uint32_t). There are 3 overloads even though 2 will only ever be
+// used by a specific platform, since unsigned long varies in size depending on
+// the word size of the architecture.
+
 template <>
-inline uint32_t find_leading_one<uint32_t>(uint32_t mant, int &shift_length) {
+inline unsigned int find_leading_one<unsigned int>(unsigned int 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];
-    }
+  if (mant > 0) {
+    shift_length = (sizeof(mant) * 8) - 1 - __builtin_clz(mant);
   }
   return 1U << shift_length;
 }
 
 template <>
-inline uint64_t find_leading_one<uint64_t>(uint64_t mant, int &shift_length) {
+inline unsigned long find_leading_one<unsigned long>(unsigned long 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];
-    }
+  if (mant > 0) {
+    shift_length = (sizeof(mant) * 8) - 1 - __builtin_clzl(mant);
+  }
+  return 1UL << shift_length;
+
+template <>
+inline unsigned long long
+find_leading_one<unsigned long long>(unsigned long long mant,
+                                     int &shift_length) {
+  shift_length = 0;
+  if (mant > 0) {
+    shift_length = (sizeof(mant) * 8) - 1 - __builtin_clzll(mant);
   }
   return 1ULL << shift_length;
 }
 
 } // namespace internal
 
 template <typename T> struct DoubleLength;