libcxx-compat: revert llvmorg-21-init-9130-g9e3982d9ae81:

  [libc++] Replace __libcpp_{ctz, clz} with __builtin_{ctzg, clzg} (#133920)

  `__libcpp_{ctz, clz}` were previously used as fallbacks for `__builtin_{ctzg, clzg}` to ensure compatibility with older compilers (Clang 18 and earlier), as `__builtin_{ctzg, clzg}` became available in Clang 19. Now that support for Clang 18 has been officially dropped in #130142, we can now safely  replace all instances of `__libcpp_{ctz, clz}` with `__count{l,r}_zero` (which internally call `__builtin_{ctzg, clzg}` and eliminate the fallback logic.

  Closes #131179.

This is part of making libc++ 21 build with clang 18.

PR:		292067
MFC after:	1 month

2 files changed, 61 insertions, 0 deletions

diff --git a/contrib/llvm-project/libcxx/include/__bit/countl.h b/contrib/llvm-project/libcxx/include/__bit/countl.h
index 075914020879..11de5f214682 100644
--- a/contrib/llvm-project/libcxx/include/__bit/countl.h
+++ b/contrib/llvm-project/libcxx/include/__bit/countl.h
@@ -9,6 +9,7 @@
 #ifndef _LIBCPP___BIT_COUNTL_H
 #define _LIBCPP___BIT_COUNTL_H
 
+#include <__bit/rotate.h>
 #include <__config>
 #include <__type_traits/integer_traits.h>
 #include <limits>
@@ -25,7 +26,34 @@ _LIBCPP_BEGIN_NAMESPACE_STD
 template <class _Tp>
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 int __countl_zero(_Tp __t) _NOEXCEPT {
   static_assert(__is_unsigned_integer_v<_Tp>, "__countl_zero requires an unsigned integer type");
+#if __has_builtin(__builtin_clzg)
   return __builtin_clzg(__t, numeric_limits<_Tp>::digits);
+#else  // __has_builtin(__builtin_clzg)
+  if (__t == 0)
+    return numeric_limits<_Tp>::digits;
+
+  if (sizeof(_Tp) <= sizeof(unsigned int))
+    return __builtin_clz(static_cast<unsigned int>(__t)) -
+           (numeric_limits<unsigned int>::digits - numeric_limits<_Tp>::digits);
+  else if (sizeof(_Tp) <= sizeof(unsigned long))
+    return __builtin_clzl(static_cast<unsigned long>(__t)) -
+           (numeric_limits<unsigned long>::digits - numeric_limits<_Tp>::digits);
+  else if (sizeof(_Tp) <= sizeof(unsigned long long))
+    return __builtin_clzll(static_cast<unsigned long long>(__t)) -
+           (numeric_limits<unsigned long long>::digits - numeric_limits<_Tp>::digits);
+  else {
+    int __ret                      = 0;
+    int __iter                     = 0;
+    const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits;
+    while (true) {
+      __t = std::__rotl(__t, __ulldigits);
+      if ((__iter = std::__countl_zero(static_cast<unsigned long long>(__t))) != __ulldigits)
+        break;
+      __ret += __iter;
+    }
+    return __ret + __iter;
+  }
+#endif // __has_builtin(__builtin_clzg)
 }
 
 #if _LIBCPP_STD_VER >= 20
diff --git a/contrib/llvm-project/libcxx/include/__bit/countr.h b/contrib/llvm-project/libcxx/include/__bit/countr.h
index f6c98695d3d0..2179eeae9e3d 100644
--- a/contrib/llvm-project/libcxx/include/__bit/countr.h
+++ b/contrib/llvm-project/libcxx/include/__bit/countr.h
@@ -22,10 +22,43 @@ _LIBCPP_PUSH_MACROS
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+// A constexpr implementation for C++11 and later (using clang extensions for constexpr support)
+// Precondition: __t != 0 (the caller __countr_zero handles __t == 0 as a special case)
+template <class _Tp>
+[[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int __countr_zero_impl(_Tp __t) _NOEXCEPT {
+  _LIBCPP_ASSERT_INTERNAL(__t != 0, "__countr_zero_impl called with zero value");
+  static_assert(__is_unsigned_integer_v<_Tp>, "__countr_zero_impl only works with unsigned types");
+  if _LIBCPP_CONSTEXPR (sizeof(_Tp) <= sizeof(unsigned int)) {
+    return __builtin_ctz(static_cast<unsigned int>(__t));
+  } else if _LIBCPP_CONSTEXPR (sizeof(_Tp) <= sizeof(unsigned long)) {
+    return __builtin_ctzl(static_cast<unsigned long>(__t));
+  } else if _LIBCPP_CONSTEXPR (sizeof(_Tp) <= sizeof(unsigned long long)) {
+    return __builtin_ctzll(static_cast<unsigned long long>(__t));
+  } else {
+#if _LIBCPP_STD_VER == 11
+    unsigned long long __ull       = static_cast<unsigned long long>(__t);
+    const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits;
+    return __ull == 0ull ? __ulldigits + std::__countr_zero_impl<_Tp>(__t >> __ulldigits) : __builtin_ctzll(__ull);
+#else
+    int __ret                      = 0;
+    const unsigned int __ulldigits = numeric_limits<unsigned long long>::digits;
+    while (static_cast<unsigned long long>(__t) == 0uLL) {
+      __ret += __ulldigits;
+      __t >>= __ulldigits;
+    }
+    return __ret + __builtin_ctzll(static_cast<unsigned long long>(__t));
+#endif
+  }
+}
+
 template <class _Tp>
 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR int __countr_zero(_Tp __t) _NOEXCEPT {
   static_assert(__is_unsigned_integer_v<_Tp>, "__countr_zero only works with unsigned types");
+#if __has_builtin(__builtin_ctzg) // TODO (LLVM 21): This can be dropped once we only support Clang >= 19.
   return __builtin_ctzg(__t, numeric_limits<_Tp>::digits);
+#else
+  return __t != 0 ? std::__countr_zero_impl(__t) : numeric_limits<_Tp>::digits;
+#endif
 }
 
 #if _LIBCPP_STD_VER >= 20