[PATCH] libstdc++: Make internal bit manipulation functions available in C++11.

For __countl_zero, __countr_zero, __popcount we split defintions
using generic builtin (constexpr in C++11), and typed-builtin (constexpr
since 20). The __countl_one, __countr_one and __has_single bit, that
are implemented with single return, as also left constexpr since C++11.

Specializations of __countl_zero, __countr_zero, __popcount and __bit_width
are provided for __rand_unit128. Using template specializations instead
of separate overloads, allow them to be selected by __countl_one, and
other functions that are implemented in terms of above. Despite being
implemented in terms of __countl_zero, __bit_width is specialized to
avoid dependency on __gnu_cxx::__int_traits.

The implementation of __bit_floor uses (std::__bit_width(__x) - 1) instead
of (_Nd - std::__countl_zero((_Tp)(__x >> 1)). This provide supports by
__rand_uint128 by using new overload. For that type __bit_width(__x) -1,
is more optimal that __bit_width(__x >> 1).

libstdc++-v3/ChangeLog:

	* include/bits/random.h (std::__rotr, std::__rotl, std::__bit_ceil):
 	[__cplusplus >= 201103L]: Define as _GLIBCXX14_CONSTEXPR.
	(std::__countl_zero, std::__countr_zero, std::__popcount)
	[__cplusplus >= 201103L]: Split implementation using generic
	builtin, define other as _GLIBCXX14_CONSTEXPR.
	(std::__bit_width, std::__bit_floor) [__cplusplus >= 201103L]:
	Modify to use single return statement.
	* include/bits/random.tcc (std::__countl_zero, std::__countr_zero)
	(std::__popcount, std::__bit_width): Define explicit specializations
	for __detail::__rand_uint128.
	* include/std/bit (std::__generate_canonical_pow2):
	(std::__generate_canonical_any): Replace builtins call with
	<bit> function calls.
---
The followup enabling <bit> header in C++11, I have mentioned.
It makes the function constexpr when possible.

Testing on x86_64 and powerpc64le. *random* tested in all standard
modes, -m32, debug and assertions.

 libstdc++-v3/include/bits/random.h   | 43 +++++++++++++--
 libstdc++-v3/include/bits/random.tcc | 17 ++----
 libstdc++-v3/include/std/bit         | 79 ++++++++++++++++------------
 3 files changed, 88 insertions(+), 51 deletions(-)

diff --git a/libstdc++-v3/include/bits/random.h b/libstdc++-v3/include/bits/random.h
index b01b92862cc..cfec087f0cd 100644
--- a/libstdc++-v3/include/bits/random.h
+++ b/libstdc++-v3/include/bits/random.h
@@ -31,6 +31,7 @@
 #ifndef _RANDOM_H
 #define _RANDOM_H 1
 
+#include <bit>     // std::__bit_width
 #include <vector>
 #include <bits/ios_base.h>
 #include <bits/uniform_int_dist.h>
@@ -68,13 +69,13 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
 #endif
 
   /// @cond undocumented
-  // Implementation-space details.
-  namespace __detail
-  {
 #pragma GCC diagnostic push
 #pragma GCC diagnostic ignored "-Wc++17-extensions"
 
 #ifndef __SIZEOF_INT128__
+  // Implementation-space details.
+  namespace __detail
+  {
     // Emulate 128-bit integer type, for the arithmetic ops used in <random>.
     // The __detail::__mod function needs: (type(a) * x + c) % m.
     // std::philox_engine needs multiplication and bitwise ops.
@@ -522,8 +523,42 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
       uint64_t _M_hi = 0;
       uint64_t _M_lo = 0;
     };
-#endif // ! __SIZEOF_INT128__
+  } // namespace __detail
+
+  template<>
+    constexpr int
+    __countl_zero(__detail::__rand_uint128 __val) noexcept
+    {
+      return __val._M_hi ? std::__countl_zero(__val._M_hi)
+			 : std::__countl_zero(__val._M_lo) + 64;
+    }
 
+  template<>
+    constexpr int
+    __countr_zero(__detail::__rand_uint128 __val) noexcept
+    {
+      return __val._M_lo ? std::__countr_zero(__val._M_lo)
+			 : std::__countr_zero(__val._M_hi) + 64;
+    }
+
+  template<>
+    constexpr int
+    __popcount(__detail::__rand_uint128 __val) noexcept
+    {
+      return std::__popcount(__val._M_hi) + std::__popcount(__val._M_lo);
+    }
+
+  template<>
+    constexpr int
+    __bit_width(__detail::__rand_uint128 __val) noexcept
+    {
+      return __val._M_hi ? std::__bit_width(__val._M_hi) + 64
+			 : std::__bit_width(__val._M_lo);
+    }
+
+#endif // ! __SIZEOF_INT128__
+  namespace __detail
+  {
     template<typename _UIntType, size_t __w,
 	     bool = __w < static_cast<size_t>
 			  (std::numeric_limits<_UIntType>::digits)>
diff --git a/libstdc++-v3/include/bits/random.tcc b/libstdc++-v3/include/bits/random.tcc
index b2afe411a7c..370109bd04f 100644
--- a/libstdc++-v3/include/bits/random.tcc
+++ b/libstdc++-v3/include/bits/random.tcc
@@ -3706,10 +3706,10 @@ namespace __detail
       // Commented-out assignments below are of values specified in
       //  the Standard, but not used here for reasons noted.
       // r = 2;  // Redundant, we only support radix 2.
-      using _Rng = decltype(_Urbg::max());
-      const _Rng __rng_range_less_1 = _Urbg::max() - _Urbg::min();
+      using _URng = typename make_unsigned<decltype(_Urbg::max())>::type;
+      const _URng __rng_range_less_1(_Urbg::max() - _Urbg::min());
       // R = _UInt(__rng_range_less_1) + 1;  // May wrap to 0.
-      const auto __log2_R = __builtin_popcountg(__rng_range_less_1);
+      const auto __log2_R = std::__popcount(__rng_range_less_1);
       const auto __log2_uint_max = sizeof(_UInt) * __CHAR_BIT__;
       // rd = _UInt(1) << __d;  // Could overflow, UB.
       const unsigned __k = (__d + __log2_R - 1) / __log2_R;
@@ -3804,8 +3804,7 @@ namespace __detail
       // Cannot overflow, as _Urbg::max() - _Urbg::min() is not power of
       // two minus one
       constexpr _UIntR __R = _UIntR(_Urbg::max() - _Urbg::min()) + 1;
-      constexpr unsigned __log2R
-	= sizeof(_UIntR) * __CHAR_BIT__ - __builtin_clzg(__R) - 1;
+      constexpr unsigned __log2R = std::__bit_width(__R) - 1;
       // We overstimate number of required bits, by computing
       // m such that m * log2(R) >= d, so:
       // R^m >= (2 ^ log2(R)) ^ m == 2 ^ (log2(R) * m) >= 2^d
@@ -3872,13 +3871,7 @@ namespace __detail
 
 	  // __abits is maximum bit width of the value, that can
 	  // be multiplied by R^l without overflowing 128 bit integer
-	  _GLIBCXX_GEN_CANON_CONST unsigned __bwRl
-#ifndef __SIZEOF_INT128__
-	    = __Rl._M_hi ? 128 - __builtin_clzg(__Rl._M_hi)
-			 : 64 - __builtin_clzg(__Rl._M_lo);
-#else
-	    = 128 - __builtin_clzg(__Rl);
-#endif
+	  _GLIBCXX_GEN_CANON_CONST unsigned __bwRl = std::__bit_width(__Rl);
 
 	  // For __R close to power of two, the actual __k may be smaller than __m,
 	  // and will use less than 128bits, default to two 32 bits chunks.
diff --git a/libstdc++-v3/include/std/bit b/libstdc++-v3/include/std/bit
index 6ea0f6eef83..b735044ca18 100644
--- a/libstdc++-v3/include/std/bit
+++ b/libstdc++-v3/include/std/bit
@@ -33,7 +33,7 @@
 #pragma GCC system_header
 #endif
 
-#if __cplusplus >= 201402L
+#if __cplusplus >= 201103L
 
 #include <concepts> // for std::integral
 #include <type_traits>
@@ -157,7 +157,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
 
   template<typename _Tp>
-    constexpr _Tp
+    _GLIBCXX14_CONSTEXPR _Tp
     __rotl(_Tp __x, int __s) noexcept
     {
       constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
@@ -179,7 +179,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     }
 
   template<typename _Tp>
-    constexpr _Tp
+    _GLIBCXX14_CONSTEXPR _Tp
     __rotr(_Tp __x, int __s) noexcept
     {
       constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
@@ -200,16 +200,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	return (__x << -__r) | (__x >> ((_Nd + __r) % _Nd)); // rotl(x, -r)
     }
 
+#if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_clzg)
   template<typename _Tp>
     constexpr int
     __countl_zero(_Tp __x) noexcept
+    {
+      return __builtin_clzg(__x, __gnu_cxx::__int_traits<_Tp>::__digits);
+    }
+#else
+  template<typename _Tp>
+    _GLIBCXX14_CONSTEXPR int
+    __countl_zero(_Tp __x) noexcept
     {
       using __gnu_cxx::__int_traits;
       constexpr auto _Nd = __int_traits<_Tp>::__digits;
-
-#if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_clzg)
-      return __builtin_clzg(__x, _Nd);
-#else
       if (__x == 0)
         return _Nd;
 
@@ -247,8 +251,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  unsigned long long __low = __x & __max_ull;
 	  return (_Nd - _Nd_ull) + __builtin_clzll(__low);
 	}
-#endif
     }
+#endif
 
   template<typename _Tp>
     constexpr int
@@ -257,16 +261,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return std::__countl_zero<_Tp>((_Tp)~__x);
     }
 
-  template<typename _Tp>
+#if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_ctzg)
+   template<typename _Tp>
     constexpr int
     __countr_zero(_Tp __x) noexcept
+    {
+      return __builtin_ctzg(__x, __gnu_cxx::__int_traits<_Tp>::__digits);
+    } 
+#else
+  template<typename _Tp>
+    _GLIBCXX14_CONSTEXPR int
+    __countr_zero(_Tp __x) noexcept
     {
       using __gnu_cxx::__int_traits;
       constexpr auto _Nd = __int_traits<_Tp>::__digits;
-
-#if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_ctzg)
-      return __builtin_ctzg(__x, _Nd);
-#else
       if (__x == 0)
         return _Nd;
 
@@ -292,8 +300,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  unsigned long long __high = __x >> _Nd_ull;
 	  return __builtin_ctzll(__high) + _Nd_ull;
 	}
-#endif
     }
+#endif
 
   template<typename _Tp>
     constexpr int
@@ -302,13 +310,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return std::__countr_zero((_Tp)~__x);
     }
 
+#if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_popcountg)
   template<typename _Tp>
     constexpr int
     __popcount(_Tp __x) noexcept
     {
-#if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_popcountg)
       return __builtin_popcountg(__x);
+    }
 #else
+  template<typename _Tp>
+    _GLIBCXX14_CONSTEXPR int
+    __popcount(_Tp __x) noexcept
+    {
       using __gnu_cxx::__int_traits;
       constexpr auto _Nd = __int_traits<_Tp>::__digits;
 
@@ -332,16 +345,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  unsigned long long __high = __x >> _Nd_ull;
 	  return __builtin_popcountll(__low) + __builtin_popcountll(__high);
 	}
-#endif
     }
+#endif
 
   template<typename _Tp>
     constexpr bool
     __has_single_bit(_Tp __x) noexcept
     { return std::__popcount(__x) == 1; }
 
+  template<typename _Tp>
+    constexpr int
+    __bit_width(_Tp __x) noexcept
+    {
+      return __gnu_cxx::__int_traits<_Tp>::__digits - std::__countl_zero(__x);
+    }
+
   template<typename _Tp>
     constexpr _Tp
+    __bit_floor(_Tp __x) noexcept
+    {
+      return (__x == 0) ? (_Tp)0 : ((_Tp)1u << (std::__bit_width(__x) - 1));
+    }
+
+  template<typename _Tp>
+    _GLIBCXX14_CONSTEXPR _Tp
     __bit_ceil(_Tp __x) noexcept
     {
       using __gnu_cxx::__int_traits;
@@ -372,24 +399,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return (_Tp)1u << __shift_exponent;
     }
 
-  template<typename _Tp>
-    constexpr _Tp
-    __bit_floor(_Tp __x) noexcept
-    {
-      constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
-      if (__x == 0)
-        return 0;
-      return (_Tp)1u << (_Nd - std::__countl_zero((_Tp)(__x >> 1)));
-    }
-
-  template<typename _Tp>
-    constexpr int
-    __bit_width(_Tp __x) noexcept
-    {
-      constexpr auto _Nd = __gnu_cxx::__int_traits<_Tp>::__digits;
-      return _Nd - std::__countl_zero(__x);
-    }
-
 #pragma GCC diagnostic pop
   /// @endcond
 
@@ -499,5 +508,5 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace std
 
-#endif // C++14
+#endif // C++11
 #endif // _GLIBCXX_BIT
-- 
2.55.0