libstdc++: Workaround is_trivially_copyable<volatile T> (PR 94013)

Several algorithms check the is_trivially_copyable trait to decide
whether to dispatch to memmove or memcmp as an optimization. Since
r271435 (CWG DR 2094) the trait is true for volatile-qualified scalars,
but we can't use memmove or memcmp when the type is volatile. We need to
also check for volatile types.

This is complicated by the fact that in C++20 (but not earlier standards)
iterator_traits<volatile T*>::value_type is T, so we can't just check
whether the value_type is volatile.

The solution in this patch is to introduce new traits __memcpyable and
__memcmpable which combine into a single trait the checks for pointers,
the value types being the same, and the type being trivially copyable
but not volatile-qualified.

	PR libstdc++/94013
	* include/bits/cpp_type_traits.h (__memcpyable, __memcmpable): New
	traits to control when to use memmove and memcmp optimizations.
	(__is_nonvolatile_trivially_copyable): New helper trait.
	* include/bits/ranges_algo.h (__lexicographical_compare_fn): Do not
	use memcmp optimization with volatile data.
	* include/bits/ranges_algobase.h (__equal_fn): Use __memcmpable.
	(__copy_or_move, __copy_or_move_backward): Use __memcpyable.
	* include/bits/stl_algobase.h (__copy_move_a2): Use __memcpyable.
	(__copy_move_backward_a2): Likewise.
	(__equal_aux1): Use __memcmpable.
	(__lexicographical_compare_aux): Do not use memcmp optimization with
	volatile data.
	* testsuite/25_algorithms/copy/94013.cc: New test.
	* testsuite/25_algorithms/copy_backward/94013.cc: New test.
	* testsuite/25_algorithms/equal/94013.cc: New test.
	* testsuite/25_algorithms/fill/94013.cc: New test.
	* testsuite/25_algorithms/lexicographical_compare/94013.cc: New test.
	* testsuite/25_algorithms/move/94013.cc: New test.
	* testsuite/25_algorithms/move_backward/94013.cc: New test.

4 files changed, 84 insertions, 43 deletions

diff --git a/libstdc++-v3/include/bits/cpp_type_traits.h b/libstdc++-v3/include/bits/cpp_type_traits.h
index 63b6d6c..fac6e4b 100644
--- a/libstdc++-v3/include/bits/cpp_type_traits.h
+++ b/libstdc++-v3/include/bits/cpp_type_traits.h
@@ -420,6 +420,65 @@ __INT_N(__GLIBCXX_TYPE_INT_N_3)
     };
 #endif
 
+  template<typename> struct iterator_traits;
+
+  // A type that is safe for use with memcpy, memmove, memcmp etc.
+  template<typename _Tp>
+    struct __is_nonvolatile_trivially_copyable
+    {
+      enum { __value = __is_trivially_copyable(_Tp) };
+    };
+
+  // Cannot use memcpy/memmove/memcmp on volatile types, but before C++20
+  // iterator_traits<volatile T*>::value_type is volatile T and so the
+  // partial specializations below match for volatile-qualified pointers
+  // e.g. __memcpyable<volatile int*, volatile int*, volatile int>.
+  template<typename _Tp>
+    struct __is_nonvolatile_trivially_copyable<volatile _Tp>
+    {
+      enum { __value = 0 };
+    };
+
+  // Whether two iterator types can be used with memcpy/memmove.
+  template<typename _OutputIter, typename _InputIter>
+    struct __memcpyable
+    {
+      enum { __value = 0 };
+    };
+
+  template<typename _Tp>
+    struct __memcpyable<_Tp*, _Tp*>
+    : __is_nonvolatile_trivially_copyable<_Tp>
+    { };
+
+  template<typename _Tp>
+    struct __memcpyable<_Tp*, const _Tp*>
+    : __is_nonvolatile_trivially_copyable<_Tp>
+    { };
+
+  // Whether two iterator types can be used with memcmp.
+  template<typename _Iter1, typename _Iter2>
+    struct __memcmpable
+    {
+      enum { __value = 0 };
+    };
+
+  // OK to use memcmp with pointers to trivially copyable types.
+  template<typename _Tp>
+    struct __memcmpable<_Tp*, _Tp*>
+    : __is_nonvolatile_trivially_copyable<_Tp>
+    { };
+
+  template<typename _Tp>
+    struct __memcmpable<const _Tp*, _Tp*>
+    : __is_nonvolatile_trivially_copyable<_Tp>
+    { };
+
+  template<typename _Tp>
+    struct __memcmpable<_Tp*, const _Tp*>
+    : __is_nonvolatile_trivially_copyable<_Tp>
+    { };
+
   //
   // Move iterator type
   //
diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index a34f75f..56fbd50 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -3473,8 +3473,8 @@ namespace ranges
 		     && __is_byte<_ValueType2>::__value
 		     && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed
 		     && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed
-		     && is_pointer_v<_Iter1>
-		     && is_pointer_v<_Iter2>
+		     && __ptr_to_nonvolatile<_Iter1>
+		     && __ptr_to_nonvolatile<_Iter2>
 		     && (is_same_v<_Comp, ranges::less>
 			 || is_same_v<_Comp, ranges::greater>)
 		     && is_same_v<_Proj1, identity>
@@ -3537,6 +3537,11 @@ namespace ranges
 		       std::move(__comp),
 		       std::move(__proj1), std::move(__proj2));
       }
+
+  private:
+    template<typename _Iter, typename _Ref = iter_reference_t<_Iter>>
+      static constexpr bool __ptr_to_nonvolatile
+	= is_pointer_v<_Iter> && !is_volatile_v<remove_reference_t<_Ref>>;
   };
 
   inline constexpr __lexicographical_compare_fn lexicographical_compare;
diff --git a/libstdc++-v3/include/bits/ranges_algobase.h b/libstdc++-v3/include/bits/ranges_algobase.h
index feb6c57..c0102f5 100644
--- a/libstdc++-v3/include/bits/ranges_algobase.h
+++ b/libstdc++-v3/include/bits/ranges_algobase.h
@@ -104,9 +104,7 @@ namespace ranges
 	    using _ValueType2 = iter_value_t<_Iter2>;
 	    constexpr bool __use_memcmp
 	      = ((is_integral_v<_ValueType1> || is_pointer_v<_ValueType1>)
-		 && is_same_v<_ValueType1, _ValueType2>
-		 && is_pointer_v<_Iter1>
-		 && is_pointer_v<_Iter2>
+		 && __memcmpable<_Iter1, _Iter2>::__value
 		 && is_same_v<_Pred, ranges::equal_to>
 		 && is_same_v<_Proj1, identity>
 		 && is_same_v<_Proj2, identity>);
@@ -252,16 +250,9 @@ namespace ranges
 	  if (!std::is_constant_evaluated())
 #endif
 	    {
-	      using _ValueTypeI = iter_value_t<_Iter>;
-	      using _ValueTypeO = typename iterator_traits<_Out>::value_type;
-	      constexpr bool __use_memmove
-		= (is_trivially_copyable_v<_ValueTypeI>
-		    && is_same_v<_ValueTypeI, _ValueTypeO>
-		    && is_pointer_v<_Iter>
-		    && is_pointer_v<_Out>);
-
-	      if constexpr (__use_memmove)
+	      if constexpr (__memcpyable<_Iter, _Out>::__value)
 		{
+		  using _ValueTypeI = iter_value_t<_Iter>;
 		  static_assert(_IsMove
 		      ? is_move_assignable_v<_ValueTypeI>
 		      : is_copy_assignable_v<_ValueTypeI>);
@@ -393,15 +384,9 @@ namespace ranges
 	  if (!std::is_constant_evaluated())
 #endif
 	    {
-	      using _ValueTypeI = iter_value_t<_Iter>;
-	      using _ValueTypeO = typename iterator_traits<_Out>::value_type;
-	      constexpr bool __use_memmove
-		= (is_trivially_copyable_v<_ValueTypeI>
-		    && is_same_v<_ValueTypeI, _ValueTypeO>
-		    && is_pointer_v<_Iter>
-		    && is_pointer_v<_Out>);
-	      if constexpr (__use_memmove)
+	      if constexpr (__memcpyable<_Out, _Iter>::__value)
 		{
+		  using _ValueTypeI = iter_value_t<_Iter>;
 		  static_assert(_IsMove
 		      ? is_move_assignable_v<_ValueTypeI>
 		      : is_copy_assignable_v<_ValueTypeI>);
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index 4b63086..8f3ca88 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -468,13 +468,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	return std::__copy_move<_IsMove, false, _Category>::
 	  __copy_m(__first, __last, __result);
 #endif
-      typedef typename iterator_traits<_II>::value_type _ValueTypeI;
-      typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
-      const bool __simple = (__is_trivially_copyable(_ValueTypeI)
-			     && __is_pointer<_II>::__value
-			     && __is_pointer<_OI>::__value
-			     && __are_same<_ValueTypeI, _ValueTypeO>::__value);
-      return std::__copy_move<_IsMove, __simple,
+      return std::__copy_move<_IsMove, __memcpyable<_OI, _II>::__value,
 			      _Category>::__copy_m(__first, __last, __result);
     }
 
@@ -710,14 +704,8 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
 	return std::__copy_move_backward<_IsMove, false, _Category>::
 	  __copy_move_b(__first, __last, __result);
 #endif
-      typedef typename iterator_traits<_BI1>::value_type _ValueType1;
-      typedef typename iterator_traits<_BI2>::value_type _ValueType2;
-      const bool __simple = (__is_trivially_copyable(_ValueType1)
-			     && __is_pointer<_BI1>::__value
-			     && __is_pointer<_BI2>::__value
-			     && __are_same<_ValueType1, _ValueType2>::__value);
-
-      return std::__copy_move_backward<_IsMove, __simple,
+      return std::__copy_move_backward<_IsMove,
+				       __memcpyable<_BI2, _BI1>::__value,
 				       _Category>::__copy_move_b(__first,
 								 __last,
 								 __result);
@@ -1153,13 +1141,9 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
     __equal_aux1(_II1 __first1, _II1 __last1, _II2 __first2)
     {
       typedef typename iterator_traits<_II1>::value_type _ValueType1;
-      typedef typename iterator_traits<_II2>::value_type _ValueType2;
       const bool __simple = ((__is_integer<_ValueType1>::__value
 			      || __is_pointer<_ValueType1>::__value)
-			     && __is_pointer<_II1>::__value
-			     && __is_pointer<_II2>::__value
-			     && __are_same<_ValueType1, _ValueType2>::__value);
-
+			     && __memcmpable<_II1, _II2>::__value);
       return std::__equal<__simple>::equal(__first1, __last1, __first2);
     }
 
@@ -1298,7 +1282,15 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
 	 && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed
 	 && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed
 	 && __is_pointer<_II1>::__value
-	 && __is_pointer<_II2>::__value);
+	 && __is_pointer<_II2>::__value
+#if __cplusplus > 201703L
+	 // For C++20 iterator_traits<volatile T*>::value_type is non-volatile
+	 // so __is_byte<T> could be true, but we can't use memcmp with
+	 // volatile data.
+	 && !is_volatile_v<remove_reference_t<iter_reference_t<_II1>>>
+	 && !is_volatile_v<remove_reference_t<iter_reference_t<_II2>>>
+#endif
+	 );
 
       return std::__lexicographical_compare<__simple>::__lc(__first1, __last1,
 							    __first2, __last2);