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.

12 files changed, 603 insertions, 43 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index b8cf579fdb3..640c5be90ab 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,5 +1,26 @@
 2020-03-03  Jonathan Wakely  <jwakely@redhat.com>
 
+	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.
+
 	* include/bits/stl_algobase.h (lexicographical_compare_three_way):
 	Avoid redundant iterator comparisons (LWG 3410).
 
diff --git a/libstdc++-v3/include/bits/cpp_type_traits.h b/libstdc++-v3/include/bits/cpp_type_traits.h
index 63b6d6c346f..fac6e4bbea2 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 a34f75f53d8..56fbd50ce8e 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 feb6c5723dd..c0102f5ab11 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 4b63086965d..8f3ca885f03 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);
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/94013.cc b/libstdc++-v3/testsuite/25_algorithms/copy/94013.cc
new file mode 100644
index 00000000000..8e72637aad1
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/94013.cc
@@ -0,0 +1,78 @@
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+void
+test01()
+{
+  volatile int i[2] = { 1, 2 };
+  volatile int j[2] = { 0, 0 };
+  int k[2] = { 0, 0 };
+
+  std::copy(i, i+2, j);
+  VERIFY( j[0] == 1 && j[1] == 2 );
+  std::copy(i, i+2, k);
+  VERIFY( k[0] == 1 && k[1] == 2 );
+  std::copy(k+1, k+2, i);
+  VERIFY( i[0] == 2 );
+
+  const volatile int* cj = j;
+  std::copy(cj, cj+2, i);
+  VERIFY( i[0] == 1 && i[1] == 2 );
+  std::copy(cj+1, cj+2, k);
+  VERIFY( k[0] == 2 );
+  const int* ck = k;
+  std::copy(ck, ck+2, i);
+  VERIFY( i[0] == 2 && i[1] == 2 );
+}
+
+void
+test02()
+{
+#if __cplusplus > 201703L
+  volatile int i[2] = { 1, 2 };
+  volatile int j[2] = { 0, 0 };
+  int k[2] = { 0, 0 };
+
+  std::ranges::copy(i, i+2, j);
+  VERIFY( j[0] == 1 && j[1] == 2 );
+  std::ranges::copy(i, i+2, k);
+  VERIFY( k[0] == 1 && k[1] == 2 );
+  std::ranges::copy(k+1, k+2, i);
+  VERIFY( i[0] == 2 );
+
+  const volatile int* cj = j;
+  std::ranges::copy(cj, cj+2, i);
+  VERIFY( i[0] == 1 && i[1] == 2 );
+  std::ranges::copy(cj+1, cj+2, k);
+  VERIFY( k[0] == 2 );
+  const int* ck = k;
+  std::ranges::copy(ck, ck+2, i);
+  VERIFY( i[0] == 2 && i[1] == 2 );
+#endif
+}
+
+int
+main()
+{
+  test01();
+  test02();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy_backward/94013.cc b/libstdc++-v3/testsuite/25_algorithms/copy_backward/94013.cc
new file mode 100644
index 00000000000..18411521c54
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy_backward/94013.cc
@@ -0,0 +1,78 @@
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+void
+test01()
+{
+  volatile int i[2] = { 1, 2 };
+  volatile int j[2] = { 0, 0 };
+  int k[2] = { 0, 0 };
+
+  std::copy_backward(i, i+2, j+2);
+  VERIFY( j[0] == 1 && j[1] == 2 );
+  std::copy_backward(i, i+2, k+2);
+  VERIFY( k[0] == 1 && k[1] == 2 );
+  std::copy_backward(k+1, k+2, i+1);
+  VERIFY( i[0] == 2 );
+
+  const volatile int* cj = j;
+  std::copy_backward(cj, cj+2, i+2);
+  VERIFY( i[0] == 1 && i[1] == 2 );
+  std::copy_backward(cj+1, cj+2, k+1);
+  VERIFY( k[0] == 2 );
+  const int* ck = k;
+  std::copy_backward(ck, ck+2, i+2);
+  VERIFY( i[0] == 2 && i[1] == 2 );
+}
+
+void
+test02()
+{
+#if __cplusplus > 201703L
+  volatile int i[2] = { 1, 2 };
+  volatile int j[2] = { 0, 0 };
+  int k[2] = { 0, 0 };
+
+  std::ranges::copy_backward(i, i+2, j+2);
+  VERIFY( j[0] == 1 && j[1] == 2 );
+  std::ranges::copy_backward(i, i+2, k+2);
+  VERIFY( k[0] == 1 && k[1] == 2 );
+  std::ranges::copy_backward(k+1, k+2, i+1);
+  VERIFY( i[0] == 2 );
+
+  const volatile int* cj = j;
+  std::ranges::copy_backward(cj, cj+2, i+2);
+  VERIFY( i[0] == 1 && i[1] == 2 );
+  std::ranges::copy_backward(cj+1, cj+2, k+1);
+  VERIFY( k[0] == 2 );
+  const int* ck = k;
+  std::ranges::copy_backward(ck, ck+2, i+2);
+  VERIFY( i[0] == 2 && i[1] == 2 );
+#endif
+}
+
+int
+main()
+{
+  test01();
+  test02();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/94013.cc b/libstdc++-v3/testsuite/25_algorithms/equal/94013.cc
new file mode 100644
index 00000000000..a5d275a1e92
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/94013.cc
@@ -0,0 +1,69 @@
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+void
+test01()
+{
+  volatile int i[] = { 0, 1, 2, 3 };
+  volatile int j[] = { 1, 2, 3 };
+  int k[] = { 2, 3, 4 };
+
+  VERIFY( std::equal(i+1, i+4, j) );	  // volatile, volatile
+  VERIFY( std::equal(i+2, i+4, k) );	  // volatile, unqual
+  VERIFY( ! std::equal(k, k+3, i+1) );	  // unqual, volatile
+
+  const volatile int* cj = j;
+  VERIFY( ! std::equal(cj, cj+2, cj+1) ); // const volatile, const volatile
+  VERIFY( std::equal(cj, cj+3, i+1) );	  // const volatile, volatile
+  VERIFY( ! std::equal(i, i+2, cj) );	  // volatile, const volatile
+  VERIFY( std::equal(cj+1, cj+3, k) );	  // const volatile, unqual
+  VERIFY( ! std::equal(k, k+2, cj) );	  // unqual, const volatile
+  const int* ck = k;
+  VERIFY( std::equal(ck, ck+2, i+2) );	  // const, volatile
+  VERIFY( ! std::equal(i, i+3, ck) );	  // volatile, const
+  VERIFY( std::equal(cj+1, cj+3, ck) );	  // const volatile, const
+  VERIFY( ! std::equal(ck, ck+1, cj) );	  // const, const volatile
+
+#if __cplusplus > 201703L
+  using std::ranges::equal;
+  VERIFY( equal(i+1, i+4, j, j+3) );	  // volatile, volatile
+  VERIFY( equal(i+2, i+4, k, k+2) );	  // volatile, unqual
+  VERIFY( ! equal(k, k+3, i+1, i+4) );	  // unqual, volatile
+
+  VERIFY( ! equal(cj, cj+2, cj+1, cj+3) );// const volatile, const volatile
+  VERIFY( equal(cj, cj+3, i+1, i+4) );	  // const volatile, volatile
+  VERIFY( ! equal(i, i+2, cj, cj+2) );	  // volatile, const volatile
+  VERIFY( equal(cj+1, cj+3, k, k+2) );	  // const volatile, unqual
+  VERIFY( ! equal(k, k+2, cj, cj+2) );	  // unqual, const volatile
+
+  VERIFY( equal(ck, ck+2, i+2, i+4) );	  // const, volatile
+  VERIFY( ! equal(i, i+3, ck, ck+3) );	  // volatile, const
+  VERIFY( equal(cj+1, cj+3, ck, ck+2) );  // const volatile, const
+  VERIFY( ! equal(ck, ck+1, cj, cj+1) );  // const, const volatile
+#endif
+}
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/fill/94013.cc b/libstdc++-v3/testsuite/25_algorithms/fill/94013.cc
new file mode 100644
index 00000000000..b28eb76157b
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/fill/94013.cc
@@ -0,0 +1,46 @@
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+void
+test01()
+{
+  volatile unsigned char a[2] = { 1, 2 };
+  volatile unsigned char c = 3;
+
+  std::fill(a, a+2, c);
+  VERIFY( a[0] == 3 && a[1] == 3 );
+
+#if __cplusplus > 201703L
+  c = 4;
+  std::ranges::fill(a, c);
+  VERIFY( a[0] == 4 && a[1] == 4 );
+  // currently fails, see PR 94017
+  // unsigned char c2 = 5;
+  // std::ranges::fill(a, c2);
+#endif
+}
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/94013.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/94013.cc
new file mode 100644
index 00000000000..70cb0e7e2ca
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/94013.cc
@@ -0,0 +1,71 @@
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+void
+test01()
+{
+  volatile unsigned char i[] = { 0, 1, 2, 3 };
+  volatile unsigned char j[] = { 1, 2, 3 };
+  unsigned char k[] = { 2, 3, 4 };
+
+  // v = volatile, c = const, cv = const volatile, u = unqualified
+
+  VERIFY( ! std::lexicographical_compare(i+1, i+4, j, j+2) ); // v v
+  VERIFY( std::lexicographical_compare(i+2, i+4, k, k+3) );   // v u
+  VERIFY( ! std::lexicographical_compare(k, k+3, i+1, i+4) ); // u v
+
+  const volatile unsigned char* cj = j;
+  VERIFY( std::lexicographical_compare(cj, cj+2, cj+1, cj+3) );	// cv cv
+  VERIFY( ! std::lexicographical_compare(cj, cj+3, i+1, i+4) );	// cv v
+  VERIFY( std::lexicographical_compare(i, i+2, cj, cj+2) );	// v cv
+  VERIFY( std::lexicographical_compare(cj+1, cj+3, k, k+3) );	// cv u
+  VERIFY( ! std::lexicographical_compare(k, k+2, cj, cj+3) );	// u cv
+  const unsigned char* ck = k;
+  VERIFY( ! std::lexicographical_compare(ck, ck+2, i+1, i+2) );	// c v
+  VERIFY( std::lexicographical_compare(i, i+3, ck, ck+3) );	// v c
+  VERIFY( std::lexicographical_compare(cj+1, cj+3, ck, ck+3) );	// cv c
+  VERIFY( ! std::lexicographical_compare(ck, ck+1, cj, cj+2) );	// c cv
+
+#if __cplusplus > 201703L
+  using std::ranges::lexicographical_compare;
+  VERIFY( ! lexicographical_compare(i+1, i+4, j, j+2) ); // v v
+  VERIFY( lexicographical_compare(i+2, i+4, k, k+3) );   // v u
+  VERIFY( ! lexicographical_compare(k, k+3, i+1, i+4) ); // u v
+
+  VERIFY( lexicographical_compare(cj, cj+2, cj+1, cj+3) );	// cv cv
+  VERIFY( ! lexicographical_compare(cj, cj+3, i+1, i+4) );	// cv v
+  VERIFY( lexicographical_compare(i, i+2, cj, cj+2) );		// v cv
+  VERIFY( lexicographical_compare(cj+1, cj+3, k, k+3) );	// cv u
+  VERIFY( ! lexicographical_compare(k, k+2, cj, cj+3) );	// u cv
+
+  VERIFY( ! lexicographical_compare(ck, ck+2, i+1, i+2) );	// c v
+  VERIFY( lexicographical_compare(i, i+3, ck, ck+3) );		// v c
+  VERIFY( lexicographical_compare(cj+1, cj+3, ck, ck+3) );	// cv c
+  VERIFY( ! lexicographical_compare(ck, ck+1, cj, cj+2) );	// c cv
+#endif
+}
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/move/94013.cc b/libstdc++-v3/testsuite/25_algorithms/move/94013.cc
new file mode 100644
index 00000000000..45ee475244f
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/move/94013.cc
@@ -0,0 +1,78 @@
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run { target c++11 } }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+void
+test01()
+{
+  volatile int i[2] = { 1, 2 };
+  volatile int j[2] = { 0, 0 };
+  int k[2] = { 0, 0 };
+
+  std::move(i, i+2, j);
+  VERIFY( j[0] == 1 && j[1] == 2 );
+  std::move(i, i+2, k);
+  VERIFY( k[0] == 1 && k[1] == 2 );
+  std::move(k+1, k+2, i);
+  VERIFY( i[0] == 2 );
+
+  const volatile int* cj = j;
+  std::move(cj, cj+2, i);
+  VERIFY( i[0] == 1 && i[1] == 2 );
+  std::move(cj+1, cj+2, k);
+  VERIFY( k[0] == 2 );
+  const int* ck = k;
+  std::move(ck, ck+2, i);
+  VERIFY( i[0] == 2 && i[1] == 2 );
+}
+
+void
+test02()
+{
+#if __cplusplus > 201703L
+  volatile int i[2] = { 1, 2 };
+  volatile int j[2] = { 0, 0 };
+  int k[2] = { 0, 0 };
+
+  std::ranges::move(i, i+2, j);
+  VERIFY( j[0] == 1 && j[1] == 2 );
+  std::ranges::move(i, i+2, k);
+  VERIFY( k[0] == 1 && k[1] == 2 );
+  std::ranges::move(k+1, k+2, i);
+  VERIFY( i[0] == 2 );
+
+  const volatile int* cj = j;
+  std::ranges::move(cj, cj+2, i);
+  VERIFY( i[0] == 1 && i[1] == 2 );
+  std::ranges::move(cj+1, cj+2, k);
+  VERIFY( k[0] == 2 );
+  const int* ck = k;
+  std::ranges::move(ck, ck+2, i);
+  VERIFY( i[0] == 2 && i[1] == 2 );
+#endif
+}
+
+int
+main()
+{
+  test01();
+  test02();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/move_backward/94013.cc b/libstdc++-v3/testsuite/25_algorithms/move_backward/94013.cc
new file mode 100644
index 00000000000..2fc68f94e71
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/move_backward/94013.cc
@@ -0,0 +1,78 @@
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do run { target c++11 } }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+void
+test01()
+{
+  volatile int i[2] = { 1, 2 };
+  volatile int j[2] = { 0, 0 };
+  int k[2] = { 0, 0 };
+
+  std::move_backward(i, i+2, j+2);
+  VERIFY( j[0] == 1 && j[1] == 2 );
+  std::move_backward(i, i+2, k+2);
+  VERIFY( k[0] == 1 && k[1] == 2 );
+  std::move_backward(k+1, k+2, i+1);
+  VERIFY( i[0] == 2 );
+
+  const volatile int* cj = j;
+  std::move_backward(cj, cj+2, i+2);
+  VERIFY( i[0] == 1 && i[1] == 2 );
+  std::move_backward(cj+1, cj+2, k+1);
+  VERIFY( k[0] == 2 );
+  const int* ck = k;
+  std::move_backward(ck, ck+2, i+2);
+  VERIFY( i[0] == 2 && i[1] == 2 );
+}
+
+void
+test02()
+{
+#if __cplusplus > 201703L
+  volatile int i[2] = { 1, 2 };
+  volatile int j[2] = { 0, 0 };
+  int k[2] = { 0, 0 };
+
+  std::ranges::move_backward(i, i+2, j+2);
+  VERIFY( j[0] == 1 && j[1] == 2 );
+  std::ranges::move_backward(i, i+2, k+2);
+  VERIFY( k[0] == 1 && k[1] == 2 );
+  std::ranges::move_backward(k+1, k+2, i+1);
+  VERIFY( i[0] == 2 );
+
+  const volatile int* cj = j;
+  std::ranges::move_backward(cj, cj+2, i+2);
+  VERIFY( i[0] == 1 && i[1] == 2 );
+  std::ranges::move_backward(cj+1, cj+2, k+1);
+  VERIFY( k[0] == 2 );
+  const int* ck = k;
+  std::ranges::move_backward(ck, ck+2, i+2);
+  VERIFY( i[0] == 2 && i[1] == 2 );
+#endif
+}
+
+int
+main()
+{
+  test01();
+  test02();
+}