[libc++] Use the __is_trivially_equality_comparable builtin

Reviewed By: ldionne, #libc

Spies: libcxx-commits

Differential Revision: https://reviews.llvm.org/D148553

11 files changed, 346 insertions, 197 deletions

diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt
index 4252ed00f7a4..f42c82c3ab14 100644
--- a/libcxx/include/CMakeLists.txt
+++ b/libcxx/include/CMakeLists.txt
@@ -747,6 +747,7 @@ set(files
   __type_traits/is_trivially_copyable.h
   __type_traits/is_trivially_default_constructible.h
   __type_traits/is_trivially_destructible.h
+  __type_traits/is_trivially_lexicographically_comparable.h
   __type_traits/is_trivially_move_assignable.h
   __type_traits/is_trivially_move_constructible.h
   __type_traits/is_unbounded_array.h
diff --git a/libcxx/include/__algorithm/equal.h b/libcxx/include/__algorithm/equal.h
index a26299acc69d..c07d4e2082c7 100644
--- a/libcxx/include/__algorithm/equal.h
+++ b/libcxx/include/__algorithm/equal.h
@@ -50,7 +50,7 @@ template <
                   int> = 0>
 _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool
 __equal_iter_impl(_Tp* __first1, _Tp* __last1, _Up* __first2, _BinaryPredicate&) {
-  return std::__constexpr_memcmp(__first1, __first2, (__last1 - __first1) * sizeof(_Tp)) == 0;
+  return std::__constexpr_memcmp_equal(__first1, __first2, (__last1 - __first1) * sizeof(_Tp));
 }
 
 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
@@ -100,7 +100,7 @@ template <class _Tp,
                         int> = 0>
 _LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __equal_impl(
     _Tp* __first1, _Tp* __last1, _Up* __first2, _Up*, _Pred&, _Proj1&, _Proj2&) {
-  return std::__constexpr_memcmp(__first1, __first2, (__last1 - __first1) * sizeof(_Tp)) == 0;
+  return std::__constexpr_memcmp_equal(__first1, __first2, (__last1 - __first1) * sizeof(_Tp));
 }
 
 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
diff --git a/libcxx/include/__string/char_traits.h b/libcxx/include/__string/char_traits.h
index e7c63a245cac..a2332829b414 100644
--- a/libcxx/include/__string/char_traits.h
+++ b/libcxx/include/__string/char_traits.h
@@ -212,23 +212,40 @@ struct _LIBCPP_TEMPLATE_VIS char_traits<char>
     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR bool lt(char_type __c1, char_type __c2) _NOEXCEPT
         {return (unsigned char)__c1 < (unsigned char)__c2;}
 
-  static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 int
-  compare(const char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
-    if (__n == 0)
-      return 0;
-    return std::__constexpr_memcmp(__s1, __s2, __n);
-  }
+    // __constexpr_memcmp requires a trivially lexicographically comparable type, but char is not when char is a signed type
+    static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 int
+    compare(const char_type* __lhs, const char_type* __rhs, size_t __count) _NOEXCEPT {
+      if (__libcpp_is_constant_evaluated()) {
+#ifdef _LIBCPP_COMPILER_CLANG_BASED
+        return __builtin_memcmp(__lhs, __rhs, __count);
+#else
+        while (__count != 0) {
+          if (lt(*__lhs, *__rhs))
+            return -1;
+          if (lt(*__rhs, *__lhs))
+            return 1;
 
-  static inline _LIBCPP_HIDE_FROM_ABI size_t _LIBCPP_CONSTEXPR_SINCE_CXX17 length(const char_type* __s)  _NOEXCEPT {
-    return std::__constexpr_strlen(__s);
-  }
+          __count -= sizeof(char_type);
+          ++__lhs;
+          ++__rhs;
+        }
+        return 0;
+#endif // _LIBCPP_COMPILER_CLANG_BASED
+      } else {
+        return __builtin_memcmp(__lhs, __rhs, __count);
+      }
+    }
 
-  static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17
-  const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT {
-    if (__n == 0)
-        return nullptr;
-    return std::__constexpr_char_memchr(__s, static_cast<int>(__a), __n);
-  }
+    static inline _LIBCPP_HIDE_FROM_ABI size_t _LIBCPP_CONSTEXPR_SINCE_CXX17 length(const char_type* __s)  _NOEXCEPT {
+      return std::__constexpr_strlen(__s);
+    }
+
+    static _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17
+    const char_type* find(const char_type* __s, size_t __n, const char_type& __a) _NOEXCEPT {
+      if (__n == 0)
+          return nullptr;
+      return std::__constexpr_char_memchr(__s, static_cast<int>(__a), __n);
+    }
 
     static inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
     char_type* move(char_type* __s1, const char_type* __s2, size_t __n) _NOEXCEPT {
diff --git a/libcxx/include/__string/constexpr_c_functions.h b/libcxx/include/__string/constexpr_c_functions.h
index 500fa473a5b0..ffba78265174 100644
--- a/libcxx/include/__string/constexpr_c_functions.h
+++ b/libcxx/include/__string/constexpr_c_functions.h
@@ -13,6 +13,7 @@
 #include <__type_traits/is_constant_evaluated.h>
 #include <__type_traits/is_equality_comparable.h>
 #include <__type_traits/is_same.h>
+#include <__type_traits/is_trivially_lexicographically_comparable.h>
 #include <cstddef>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
@@ -35,11 +36,14 @@ inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 size_t __constexpr_st
   return __builtin_strlen(__str);
 }
 
+// Because of __libcpp_is_trivially_lexicographically_comparable we know that comparing the object representations is
+// equivalent to a std::memcmp. Since we have multiple objects contiguously in memory, we can call memcmp once instead
+// of invoking it on every object individually.
 template <class _Tp, class _Up>
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 int
 __constexpr_memcmp(const _Tp* __lhs, const _Up* __rhs, size_t __count) {
-  static_assert(__libcpp_is_trivially_equality_comparable<_Tp, _Up>::value,
-                "_Tp and _Up have to be trivially equality comparable");
+  static_assert(__libcpp_is_trivially_lexicographically_comparable<_Tp, _Up>::value,
+                "_Tp and _Up have to be trivially lexicographically comparable");
 
   if (__libcpp_is_constant_evaluated()) {
 #ifdef _LIBCPP_COMPILER_CLANG_BASED
@@ -63,6 +67,34 @@ __constexpr_memcmp(const _Tp* __lhs, const _Up* __rhs, size_t __count) {
   }
 }
 
+// Because of __libcpp_is_trivially_equality_comparable we know that comparing the object representations is equivalent
+// to a std::memcmp(...) == 0. Since we have multiple objects contiguously in memory, we can call memcmp once instead
+// of invoking it on every object individually.
+template <class _Tp, class _Up>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 bool
+__constexpr_memcmp_equal(const _Tp* __lhs, const _Up* __rhs, size_t __count) {
+  static_assert(__libcpp_is_trivially_equality_comparable<_Tp, _Up>::value,
+                "_Tp and _Up have to be trivially equality comparable");
+
+  if (__libcpp_is_constant_evaluated()) {
+#ifdef _LIBCPP_COMPILER_CLANG_BASED
+    if (sizeof(_Tp) == 1 && is_integral<_Tp>::value && !is_same<_Tp, bool>::value)
+      return __builtin_memcmp(__lhs, __rhs, __count) == 0;
+#endif
+    while (__count != 0) {
+      if (*__lhs != *__rhs)
+        return false;
+
+      __count -= sizeof(_Tp);
+      ++__lhs;
+      ++__rhs;
+    }
+    return true;
+  } else {
+    return __builtin_memcmp(__lhs, __rhs, __count) == 0;
+  }
+}
+
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 const char*
 __constexpr_char_memchr(const char* __str, int __char, size_t __count) {
 #if __has_builtin(__builtin_char_memchr)
diff --git a/libcxx/include/__type_traits/is_equality_comparable.h b/libcxx/include/__type_traits/is_equality_comparable.h
index b7a7cd219e30..381108365c00 100644
--- a/libcxx/include/__type_traits/is_equality_comparable.h
+++ b/libcxx/include/__type_traits/is_equality_comparable.h
@@ -15,6 +15,7 @@
 #include <__type_traits/is_same.h>
 #include <__type_traits/is_void.h>
 #include <__type_traits/remove_cv.h>
+#include <__type_traits/remove_cvref.h>
 #include <__type_traits/void_t.h>
 #include <__utility/declval.h>
 
@@ -32,8 +33,9 @@ struct __is_equality_comparable<_Tp, _Up, __void_t<decltype(std::declval<_Tp>()
 };
 
 // A type is_trivially_equality_comparable if the expression `a == b` is equivalent to `std::memcmp(&a, &b, sizeof(T))`
-// (with `a` and `b` being of type `T`). There is no compiler built-in to check this, so we can only do this for known
-// types. In particular, these are the integral types and raw pointers.
+// (with `a` and `b` being of type `T`). For the case where we compare two object of the same type, we can use
+// __is_trivially_equality_comparable. We have special-casing for pointers which point to the same type ignoring
+// cv-qualifications and comparing to void-pointers.
 //
 // The following types are not trivially equality comparable:
 // floating-point types: different bit-patterns can compare equal. (e.g 0.0 and -0.0)
@@ -43,20 +45,34 @@ struct __is_equality_comparable<_Tp, _Up, __void_t<decltype(std::declval<_Tp>()
 //   always compared.
 
 template <class _Tp, class _Up>
-struct __libcpp_is_trivially_equality_comparable
-    : integral_constant<bool,
-                        __is_equality_comparable<_Tp, _Up>::value && is_integral<_Tp>::value &&
-                            is_same<__remove_cv_t<_Tp>, __remove_cv_t<_Up> >::value> {};
+struct __libcpp_is_trivially_equality_comparable_impl : false_type {};
+
+template <class _Tp>
+struct __libcpp_is_trivially_equality_comparable_impl<_Tp, _Tp>
+#if __has_builtin(__is_trivially_equality_comparable)
+    : integral_constant<bool, __is_trivially_equality_comparable(_Tp) && __is_equality_comparable<_Tp, _Tp>::value> {
+};
+#else
+    : is_integral<_Tp> {
+};
+#endif // __has_builtin(__is_trivially_equality_comparable)
+
+template <class _Tp>
+struct __libcpp_is_trivially_equality_comparable_impl<_Tp*, _Tp*> : true_type {};
 
 // TODO: Use is_pointer_inverconvertible_base_of
 template <class _Tp, class _Up>
-struct __libcpp_is_trivially_equality_comparable<_Tp*, _Up*>
+struct __libcpp_is_trivially_equality_comparable_impl<_Tp*, _Up*>
     : integral_constant<
           bool,
           __is_equality_comparable<_Tp*, _Up*>::value &&
               (is_same<__remove_cv_t<_Tp>, __remove_cv_t<_Up> >::value || is_void<_Tp>::value || is_void<_Up>::value)> {
 };
 
+template <class _Tp, class _Up>
+using __libcpp_is_trivially_equality_comparable =
+    __libcpp_is_trivially_equality_comparable_impl<__remove_cv_t<_Tp>, __remove_cv_t<_Up> >;
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___TYPE_TRAITS_IS_EQUAILITY_COMPARABLE_H
diff --git a/libcxx/include/__type_traits/is_trivially_lexicographically_comparable.h b/libcxx/include/__type_traits/is_trivially_lexicographically_comparable.h
new file mode 100644
index 000000000000..a310ea1b87e3
--- /dev/null
+++ b/libcxx/include/__type_traits/is_trivially_lexicographically_comparable.h
@@ -0,0 +1,53 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___TYPE_TRAITS_IS_TRIVIALLY_LEXICOGRAPHICALLY_COMPARABLE_H
+#define _LIBCPP___TYPE_TRAITS_IS_TRIVIALLY_LEXICOGRAPHICALLY_COMPARABLE_H
+
+#include <__config>
+#include <__type_traits/integral_constant.h>
+#include <__type_traits/is_same.h>
+#include <__type_traits/is_unsigned.h>
+#include <__type_traits/remove_cv.h>
+#include <__type_traits/void_t.h>
+#include <__utility/declval.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+// A type is_trivially_lexicographically_comparable if the expression `a <=> b` (or their pre-C++20 equivalents) is
+// equivalent to `std::memcmp(&a, &b, sizeof(T))` (with `a` and `b` being of type `T`). There is currently no builtin to
+// tell us whether that's the case for arbitrary types, so we can only do this for known types. Specifically, these are
+// currently unsigned integer types with a sizeof(T) == 1.
+//
+// bool is trivially lexicographically comparable, because e.g. false <=> true is valid code. Furthermore, the standard
+// says that [basic.fundamental] "Type bool is a distinct type that has the same object representation, value
+// representation, and alignment requirements as an implementation-defined unsigned integer type. The values of type
+// bool are true and false."
+// This means that bool has to be unsigned and has exactly two values. This means that having anything other than the
+// `true` or `false` value representations in a bool is UB.
+//
+// The following types are not trivially lexicographically comparable:
+// signed integer types: `char(-1) < char(1)`, but memcmp compares `unsigned char`s
+// unsigned integer types with sizeof(T) > 1: depending on the endianness, the LSB might be the first byte to be
+//                                            compared. This means that when comparing unsigned(129) and unsigned(2)
+//                                            using memcmp(), the result would be that 2 > 129.
+//                                            TODO: Do we want to enable this on big-endian systems?
+
+template <class _Tp, class _Up>
+struct __libcpp_is_trivially_lexicographically_comparable
+    : integral_constant<bool,
+                        is_same<__remove_cv_t<_Tp>, __remove_cv_t<_Up> >::value && sizeof(_Tp) == 1 &&
+                            is_unsigned<_Tp>::value> {};
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___TYPE_TRAITS_IS_TRIVIALLY_LEXICOGRAPHICALLY_COMPARABLE_H
diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in
index 9d01d36e754a..3f96e685bdc9 100644
--- a/libcxx/include/module.modulemap.in
+++ b/libcxx/include/module.modulemap.in
@@ -1501,164 +1501,165 @@ module std [system] {
     export functional.__functional.unwrap_ref
     export *
 
-    module add_const                           { private header "__type_traits/add_const.h" }
-    module add_cv                              { private header "__type_traits/add_cv.h" }
-    module add_lvalue_reference                { private header "__type_traits/add_lvalue_reference.h" }
-    module add_pointer                         { private header "__type_traits/add_pointer.h" }
-    module add_rvalue_reference                { private header "__type_traits/add_rvalue_reference.h" }
-    module add_volatile                        { private header "__type_traits/add_volatile.h" }
-    module aligned_storage                     { private header "__type_traits/aligned_storage.h" }
-    module aligned_union                       { private header "__type_traits/aligned_union.h" }
-    module alignment_of                        { private header "__type_traits/alignment_of.h" }
-    module apply_cv                            { private header "__type_traits/apply_cv.h" }
-    module can_extract_key                     { private header "__type_traits/can_extract_key.h" }
-    module common_reference                    { private header "__type_traits/common_reference.h" }
-    module common_type                         { private header "__type_traits/common_type.h" }
-    module conditional                         { private header "__type_traits/conditional.h" }
-    module conjunction                         { private header "__type_traits/conjunction.h" }
-    module copy_cv                             { private header "__type_traits/copy_cv.h" }
-    module copy_cvref                          { private header "__type_traits/copy_cvref.h" }
-    module decay                               { private header "__type_traits/decay.h" }
-    module dependent_type                      { private header "__type_traits/dependent_type.h" }
-    module disjunction                         { private header "__type_traits/disjunction.h" }
-    module enable_if                           { private header "__type_traits/enable_if.h" }
-    module extent                              { private header "__type_traits/extent.h" }
-    module has_unique_object_representation    { private header "__type_traits/has_unique_object_representation.h" }
-    module has_virtual_destructor              { private header "__type_traits/has_virtual_destructor.h" }
-    module integral_constant                   { private header "__type_traits/integral_constant.h" }
-    module is_abstract                         { private header "__type_traits/is_abstract.h" }
-    module is_aggregate                        { private header "__type_traits/is_aggregate.h" }
-    module is_allocator                        { private header "__type_traits/is_allocator.h" }
-    module is_always_bitcastable               { private header "__type_traits/is_always_bitcastable.h" }
+    module add_const                                 { private header "__type_traits/add_const.h" }
+    module add_cv                                    { private header "__type_traits/add_cv.h" }
+    module add_lvalue_reference                      { private header "__type_traits/add_lvalue_reference.h" }
+    module add_pointer                               { private header "__type_traits/add_pointer.h" }
+    module add_rvalue_reference                      { private header "__type_traits/add_rvalue_reference.h" }
+    module add_volatile                              { private header "__type_traits/add_volatile.h" }
+    module aligned_storage                           { private header "__type_traits/aligned_storage.h" }
+    module aligned_union                             { private header "__type_traits/aligned_union.h" }
+    module alignment_of                              { private header "__type_traits/alignment_of.h" }
+    module apply_cv                                  { private header "__type_traits/apply_cv.h" }
+    module can_extract_key                           { private header "__type_traits/can_extract_key.h" }
+    module common_reference                          { private header "__type_traits/common_reference.h" }
+    module common_type                               { private header "__type_traits/common_type.h" }
+    module conditional                               { private header "__type_traits/conditional.h" }
+    module conjunction                               { private header "__type_traits/conjunction.h" }
+    module copy_cv                                   { private header "__type_traits/copy_cv.h" }
+    module copy_cvref                                { private header "__type_traits/copy_cvref.h" }
+    module decay                                     { private header "__type_traits/decay.h" }
+    module dependent_type                            { private header "__type_traits/dependent_type.h" }
+    module disjunction                               { private header "__type_traits/disjunction.h" }
+    module enable_if                                 { private header "__type_traits/enable_if.h" }
+    module extent                                    { private header "__type_traits/extent.h" }
+    module has_unique_object_representation          { private header "__type_traits/has_unique_object_representation.h" }
+    module has_virtual_destructor                    { private header "__type_traits/has_virtual_destructor.h" }
+    module integral_constant                         { private header "__type_traits/integral_constant.h" }
+    module is_abstract                               { private header "__type_traits/is_abstract.h" }
+    module is_aggregate                              { private header "__type_traits/is_aggregate.h" }
+    module is_allocator                              { private header "__type_traits/is_allocator.h" }
+    module is_always_bitcastable                     { private header "__type_traits/is_always_bitcastable.h" }
     module is_arithmetic {
       private header "__type_traits/is_arithmetic.h"
       export integral_constant
     }
-    module is_array                            {
+    module is_array                                  {
       private header "__type_traits/is_array.h"
       export integral_constant
     }
-    module is_assignable                       { private header "__type_traits/is_assignable.h" }
-    module is_base_of                          { private header "__type_traits/is_base_of.h" }
-    module is_bounded_array                    { private header "__type_traits/is_bounded_array.h" }
-    module is_callable                         { private header "__type_traits/is_callable.h" }
-    module is_char_like_type                   { private header "__type_traits/is_char_like_type.h" }
-    module is_class                            { private header "__type_traits/is_class.h" }
-    module is_compound                         { private header "__type_traits/is_compound.h" }
-    module is_const                            { private header "__type_traits/is_const.h" }
-    module is_constant_evaluated               { private header "__type_traits/is_constant_evaluated.h" }
-    module is_constructible                    { private header "__type_traits/is_constructible.h" }
-    module is_convertible                      { private header "__type_traits/is_convertible.h" }
-    module is_copy_assignable                  { private header "__type_traits/is_copy_assignable.h" }
-    module is_copy_constructible               { private header "__type_traits/is_copy_constructible.h" }
-    module is_core_convertible                 {
+    module is_assignable                             { private header "__type_traits/is_assignable.h" }
+    module is_base_of                                { private header "__type_traits/is_base_of.h" }
+    module is_bounded_array                          { private header "__type_traits/is_bounded_array.h" }
+    module is_callable                               { private header "__type_traits/is_callable.h" }
+    module is_char_like_type                         { private header "__type_traits/is_char_like_type.h" }
+    module is_class                                  { private header "__type_traits/is_class.h" }
+    module is_compound                               { private header "__type_traits/is_compound.h" }
+    module is_const                                  { private header "__type_traits/is_const.h" }
+    module is_constant_evaluated                     { private header "__type_traits/is_constant_evaluated.h" }
+    module is_constructible                          { private header "__type_traits/is_constructible.h" }
+    module is_convertible                            { private header "__type_traits/is_convertible.h" }
+    module is_copy_assignable                        { private header "__type_traits/is_copy_assignable.h" }
+    module is_copy_constructible                     { private header "__type_traits/is_copy_constructible.h" }
+    module is_core_convertible                       {
       private header "__type_traits/is_core_convertible.h"
       export integral_constant
     }
-    module is_default_constructible            { private header "__type_traits/is_default_constructible.h" }
-    module is_destructible                     { private header "__type_traits/is_destructible.h" }
-    module is_empty                            { private header "__type_traits/is_empty.h" }
-    module is_enum                             {
+    module is_default_constructible                  { private header "__type_traits/is_default_constructible.h" }
+    module is_destructible                           { private header "__type_traits/is_destructible.h" }
+    module is_empty                                  { private header "__type_traits/is_empty.h" }
+    module is_enum                                   {
       private header "__type_traits/is_enum.h"
       export integral_constant
     }
-    module is_equality_comparable                       {
+    module is_equality_comparable                    {
       private header "__type_traits/is_equality_comparable.h"
       export integral_constant
     }
-    module is_execution_policy                 { private header "__type_traits/is_execution_policy.h" }
-    module is_final                            { private header "__type_traits/is_final.h" }
-    module is_floating_point                   { private header "__type_traits/is_floating_point.h" }
-    module is_function                         { private header "__type_traits/is_function.h" }
-    module is_fundamental                      { private header "__type_traits/is_fundamental.h" }
-    module is_implicitly_default_constructible { private header "__type_traits/is_implicitly_default_constructible.h" }
-    module is_integral                         { private header "__type_traits/is_integral.h" }
-    module is_literal_type                     { private header "__type_traits/is_literal_type.h" }
-    module is_member_function_pointer          { private header "__type_traits/is_member_function_pointer.h" }
-    module is_member_object_pointer            { private header "__type_traits/is_member_object_pointer.h" }
-    module is_member_pointer                   { private header "__type_traits/is_member_pointer.h" }
-    module is_move_assignable                  { private header "__type_traits/is_move_assignable.h" }
-    module is_move_constructible               { private header "__type_traits/is_move_constructible.h" }
-    module is_nothrow_assignable               { private header "__type_traits/is_nothrow_assignable.h" }
-    module is_nothrow_constructible            { private header "__type_traits/is_nothrow_constructible.h" }
-    module is_nothrow_convertible              { private header "__type_traits/is_nothrow_convertible.h" }
-    module is_nothrow_copy_assignable          { private header "__type_traits/is_nothrow_copy_assignable.h" }
-    module is_nothrow_copy_constructible       { private header "__type_traits/is_nothrow_copy_constructible.h" }
-    module is_nothrow_default_constructible    { private header "__type_traits/is_nothrow_default_constructible.h" }
-    module is_nothrow_destructible             { private header "__type_traits/is_nothrow_destructible.h" }
-    module is_nothrow_move_assignable          { private header "__type_traits/is_nothrow_move_assignable.h" }
-    module is_nothrow_move_constructible       { private header "__type_traits/is_nothrow_move_constructible.h" }
-    module is_null_pointer                     { private header "__type_traits/is_null_pointer.h" }
-    module is_object                           { private header "__type_traits/is_object.h" }
-    module is_pod                              { private header "__type_traits/is_pod.h" }
-    module is_pointer                          { private header "__type_traits/is_pointer.h" }
-    module is_polymorphic                      { private header "__type_traits/is_polymorphic.h" }
-    module is_primary_template                 { private header "__type_traits/is_primary_template.h" }
-    module is_reference                        { private header "__type_traits/is_reference.h" }
-    module is_reference_wrapper                { private header "__type_traits/is_reference_wrapper.h" }
-    module is_referenceable                    { private header "__type_traits/is_referenceable.h" }
-    module is_same                             {
+    module is_execution_policy                       { private header "__type_traits/is_execution_policy.h" }
+    module is_final                                  { private header "__type_traits/is_final.h" }
+    module is_floating_point                         { private header "__type_traits/is_floating_point.h" }
+    module is_function                               { private header "__type_traits/is_function.h" }
+    module is_fundamental                            { private header "__type_traits/is_fundamental.h" }
+    module is_implicitly_default_constructible       { private header "__type_traits/is_implicitly_default_constructible.h" }
+    module is_integral                               { private header "__type_traits/is_integral.h" }
+    module is_literal_type                           { private header "__type_traits/is_literal_type.h" }
+    module is_member_function_pointer                { private header "__type_traits/is_member_function_pointer.h" }
+    module is_member_object_pointer                  { private header "__type_traits/is_member_object_pointer.h" }
+    module is_member_pointer                         { private header "__type_traits/is_member_pointer.h" }
+    module is_move_assignable                        { private header "__type_traits/is_move_assignable.h" }
+    module is_move_constructible                     { private header "__type_traits/is_move_constructible.h" }
+    module is_nothrow_assignable                     { private header "__type_traits/is_nothrow_assignable.h" }
+    module is_nothrow_constructible                  { private header "__type_traits/is_nothrow_constructible.h" }
+    module is_nothrow_convertible                    { private header "__type_traits/is_nothrow_convertible.h" }
+    module is_nothrow_copy_assignable                { private header "__type_traits/is_nothrow_copy_assignable.h" }
+    module is_nothrow_copy_constructible             { private header "__type_traits/is_nothrow_copy_constructible.h" }
+    module is_nothrow_default_constructible          { private header "__type_traits/is_nothrow_default_constructible.h" }
+    module is_nothrow_destructible                   { private header "__type_traits/is_nothrow_destructible.h" }
+    module is_nothrow_move_assignable                { private header "__type_traits/is_nothrow_move_assignable.h" }
+    module is_nothrow_move_constructible             { private header "__type_traits/is_nothrow_move_constructible.h" }
+    module is_null_pointer                           { private header "__type_traits/is_null_pointer.h" }
+    module is_object                                 { private header "__type_traits/is_object.h" }
+    module is_pod                                    { private header "__type_traits/is_pod.h" }
+    module is_pointer                                { private header "__type_traits/is_pointer.h" }
+    module is_polymorphic                            { private header "__type_traits/is_polymorphic.h" }
+    module is_primary_template                       { private header "__type_traits/is_primary_template.h" }
+    module is_reference                              { private header "__type_traits/is_reference.h" }
+    module is_reference_wrapper                      { private header "__type_traits/is_reference_wrapper.h" }
+    module is_referenceable                          { private header "__type_traits/is_referenceable.h" }
+    module is_same                                   {
       private header "__type_traits/is_same.h"
       export type_traits.integral_constant
     }
-    module is_scalar                           { private header "__type_traits/is_scalar.h" }
-    module is_scoped_enum                      { private header "__type_traits/is_scoped_enum.h" }
-    module is_signed                           { private header "__type_traits/is_signed.h" }
-    module is_signed_integer                   { private header "__type_traits/is_signed_integer.h" }
-    module is_specialization                   { private header "__type_traits/is_specialization.h" }
-    module is_standard_layout                  { private header "__type_traits/is_standard_layout.h" }
-    module is_swappable                        { private header "__type_traits/is_swappable.h" }
-    module is_trivial                          { private header "__type_traits/is_trivial.h" }
-    module is_trivially_assignable             { private header "__type_traits/is_trivially_assignable.h" }
-    module is_trivially_constructible          { private header "__type_traits/is_trivially_constructible.h" }
-    module is_trivially_copy_assignable        { private header "__type_traits/is_trivially_copy_assignable.h" }
-    module is_trivially_copy_constructible     { private header "__type_traits/is_trivially_copy_constructible.h" }
-    module is_trivially_copyable               { private header "__type_traits/is_trivially_copyable.h" }
-    module is_trivially_default_constructible  { private header "__type_traits/is_trivially_default_constructible.h" }
-    module is_trivially_destructible           { private header "__type_traits/is_trivially_destructible.h" }
-    module is_trivially_move_assignable        { private header "__type_traits/is_trivially_move_assignable.h" }
-    module is_trivially_move_constructible     { private header "__type_traits/is_trivially_move_constructible.h" }
-    module is_unbounded_array                  { private header "__type_traits/is_unbounded_array.h" }
-    module is_union                            { private header "__type_traits/is_union.h" }
-    module is_unsigned                         { private header "__type_traits/is_unsigned.h" }
-    module is_unsigned_integer                 { private header "__type_traits/is_unsigned_integer.h" }
-    module is_valid_expansion                  { private header "__type_traits/is_valid_expansion.h" }
-    module is_void                             {
+    module is_scalar                                 { private header "__type_traits/is_scalar.h" }
+    module is_scoped_enum                            { private header "__type_traits/is_scoped_enum.h" }
+    module is_signed                                 { private header "__type_traits/is_signed.h" }
+    module is_signed_integer                         { private header "__type_traits/is_signed_integer.h" }
+    module is_specialization                         { private header "__type_traits/is_specialization.h" }
+    module is_standard_layout                        { private header "__type_traits/is_standard_layout.h" }
+    module is_swappable                              { private header "__type_traits/is_swappable.h" }
+    module is_trivial                                { private header "__type_traits/is_trivial.h" }
+    module is_trivially_assignable                   { private header "__type_traits/is_trivially_assignable.h" }
+    module is_trivially_constructible                { private header "__type_traits/is_trivially_constructible.h" }
+    module is_trivially_copy_assignable              { private header "__type_traits/is_trivially_copy_assignable.h" }
+    module is_trivially_copy_constructible           { private header "__type_traits/is_trivially_copy_constructible.h" }
+    module is_trivially_copyable                     { private header "__type_traits/is_trivially_copyable.h" }
+    module is_trivially_default_constructible        { private header "__type_traits/is_trivially_default_constructible.h" }
+    module is_trivially_destructible                 { private header "__type_traits/is_trivially_destructible.h" }
+    module is_trivially_lexicographically_comparable { private header "__type_traits/is_trivially_lexicographically_comparable.h" }
+    module is_trivially_move_assignable              { private header "__type_traits/is_trivially_move_assignable.h" }
+    module is_trivially_move_constructible           { private header "__type_traits/is_trivially_move_constructible.h" }
+    module is_unbounded_array                        { private header "__type_traits/is_unbounded_array.h" }
+    module is_union                                  { private header "__type_traits/is_union.h" }
+    module is_unsigned                               { private header "__type_traits/is_unsigned.h" }
+    module is_unsigned_integer                       { private header "__type_traits/is_unsigned_integer.h" }
+    module is_valid_expansion                        { private header "__type_traits/is_valid_expansion.h" }
+    module is_void                                   {
       private header "__type_traits/is_void.h"
       export integral_constant
     }
-    module is_volatile                         { private header "__type_traits/is_volatile.h" }
-    module lazy                                { private header "__type_traits/lazy.h" }
-    module make_32_64_or_128_bit               { private header "__type_traits/make_32_64_or_128_bit.h" }
-    module make_const_lvalue_ref               { private header "__type_traits/make_const_lvalue_ref.h" }
-    module make_signed                         { private header "__type_traits/make_signed.h" }
-    module make_unsigned                       { private header "__type_traits/make_unsigned.h" }
-    module maybe_const                         { private header "__type_traits/maybe_const.h" }
-    module nat                                 { private header "__type_traits/nat.h" }
-    module negation                            { private header "__type_traits/negation.h" }
-    module noexcept_move_assign_container      { private header "__type_traits/noexcept_move_assign_container.h" }
-    module predicate_traits                    { private header "__type_traits/predicate_traits.h" }
-    module promote                             { private header "__type_traits/promote.h" }
-    module rank                                { private header "__type_traits/rank.h" }
-    module remove_all_extents                  { private header "__type_traits/remove_all_extents.h" }
-    module remove_const                        { private header "__type_traits/remove_const.h" }
-    module remove_const_ref                    { private header "__type_traits/remove_const_ref.h" }
-    module remove_cv                           { private header "__type_traits/remove_cv.h" }
-    module remove_cvref                        { private header "__type_traits/remove_cvref.h" }
-    module remove_extent                       { private header "__type_traits/remove_extent.h" }
-    module remove_pointer                      { private header "__type_traits/remove_pointer.h" }
-    module remove_reference                    { private header "__type_traits/remove_reference.h" }
-    module remove_volatile                     { private header "__type_traits/remove_volatile.h" }
-    module result_of                           { private header "__type_traits/result_of.h" }
-    module strip_signature                     { private header "__type_traits/strip_signature.h" }
-    module type_identity                       { private header "__type_traits/type_identity.h" }
-    module type_list                           { private header "__type_traits/type_list.h" }
-    module underlying_type                     {
+    module is_volatile                               { private header "__type_traits/is_volatile.h" }
+    module lazy                                      { private header "__type_traits/lazy.h" }
+    module make_32_64_or_128_bit                     { private header "__type_traits/make_32_64_or_128_bit.h" }
+    module make_const_lvalue_ref                     { private header "__type_traits/make_const_lvalue_ref.h" }
+    module make_signed                               { private header "__type_traits/make_signed.h" }
+    module make_unsigned                             { private header "__type_traits/make_unsigned.h" }
+    module maybe_const                               { private header "__type_traits/maybe_const.h" }
+    module nat                                       { private header "__type_traits/nat.h" }
+    module negation                                  { private header "__type_traits/negation.h" }
+    module noexcept_move_assign_container            { private header "__type_traits/noexcept_move_assign_container.h" }
+    module predicate_traits                          { private header "__type_traits/predicate_traits.h" }
+    module promote                                   { private header "__type_traits/promote.h" }
+    module rank                                      { private header "__type_traits/rank.h" }
+    module remove_all_extents                        { private header "__type_traits/remove_all_extents.h" }
+    module remove_const                              { private header "__type_traits/remove_const.h" }
+    module remove_const_ref                          { private header "__type_traits/remove_const_ref.h" }
+    module remove_cv                                 { private header "__type_traits/remove_cv.h" }
+    module remove_cvref                              { private header "__type_traits/remove_cvref.h" }
+    module remove_extent                             { private header "__type_traits/remove_extent.h" }
+    module remove_pointer                            { private header "__type_traits/remove_pointer.h" }
+    module remove_reference                          { private header "__type_traits/remove_reference.h" }
+    module remove_volatile                           { private header "__type_traits/remove_volatile.h" }
+    module result_of                                 { private header "__type_traits/result_of.h" }
+    module strip_signature                           { private header "__type_traits/strip_signature.h" }
+    module type_identity                             { private header "__type_traits/type_identity.h" }
+    module type_list                                 { private header "__type_traits/type_list.h" }
+    module underlying_type                           {
       private header "__type_traits/underlying_type.h"
 
       export type_traits
     }
-    module void_t                              { private header "__type_traits/void_t.h" }
+    module void_t                                    { private header "__type_traits/void_t.h" }
   }
   module typeindex {
     header "typeindex"
diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp
index 0720e1f72a77..d8a821893943 100644
--- a/libcxx/test/libcxx/private_headers.verify.cpp
+++ b/libcxx/test/libcxx/private_headers.verify.cpp
@@ -731,6 +731,7 @@ END-SCRIPT
 #include <__type_traits/is_trivially_copyable.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/is_trivially_copyable.h'}}
 #include <__type_traits/is_trivially_default_constructible.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/is_trivially_default_constructible.h'}}
 #include <__type_traits/is_trivially_destructible.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/is_trivially_destructible.h'}}
+#include <__type_traits/is_trivially_lexicographically_comparable.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/is_trivially_lexicographically_comparable.h'}}
 #include <__type_traits/is_trivially_move_assignable.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/is_trivially_move_assignable.h'}}
 #include <__type_traits/is_trivially_move_constructible.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/is_trivially_move_constructible.h'}}
 #include <__type_traits/is_unbounded_array.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/is_unbounded_array.h'}}
diff --git a/libcxx/test/libcxx/strings/c.strings/constexpr.cstring.compile.pass.cpp b/libcxx/test/libcxx/strings/c.strings/constexpr.cstring.compile.pass.cpp
index f440810fb6f8..576255364e23 100644
--- a/libcxx/test/libcxx/strings/c.strings/constexpr.cstring.compile.pass.cpp
+++ b/libcxx/test/libcxx/strings/c.strings/constexpr.cstring.compile.pass.cpp
@@ -14,10 +14,18 @@
 
 #include <__string/constexpr_c_functions.h>
 
+constexpr unsigned char Banand[] = "Banand";
+constexpr unsigned char Banane[] = "Banane";
+constexpr unsigned char Bananf[] = "Bananf";
+
 static_assert(std::__constexpr_strlen("Banane") == 6, "");
-static_assert(std::__constexpr_memcmp("Banane", "Banand", 6) == 1, "");
-static_assert(std::__constexpr_memcmp("Banane", "Banane", 6) == 0, "");
-static_assert(std::__constexpr_memcmp("Banane", "Bananf", 6) == -1, "");
+static_assert(std::__constexpr_memcmp(Banane, Banand, 6) == 1, "");
+static_assert(std::__constexpr_memcmp(Banane, Banane, 6) == 0, "");
+static_assert(std::__constexpr_memcmp(Banane, Bananf, 6) == -1, "");
+
+static_assert(!std::__constexpr_memcmp_equal(Banane, Banand, 6), "");
+static_assert(std::__constexpr_memcmp_equal(Banane, Banane, 6), "");
+
 
 constexpr bool test_constexpr_wmemchr() {
   const char str[] = "Banane";
diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/equal.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/equal.pass.cpp
index e40f1ed6dbbf..97cf59defc97 100644
--- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/equal.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/equal.pass.cpp
@@ -98,14 +98,33 @@ struct AddressCompare {
   }
 };
 
+#if TEST_STD_VER >= 20
+class trivially_equality_comparable {
+public:
+  constexpr trivially_equality_comparable(int i) : i_(i) {}
+  bool operator==(const trivially_equality_comparable&) const = default;
+
+private:
+  int i_;
+};
+
+#endif
+
 TEST_CONSTEXPR_CXX20 bool test() {
   types::for_each(types::cpp17_input_iterator_list<int*>(), TestIter2<int, types::cpp17_input_iterator_list<int*> >());
-  types::for_each(types::cpp17_input_iterator_list<char*>(), TestIter2<char, types::cpp17_input_iterator_list<char*> >());
+  types::for_each(
+      types::cpp17_input_iterator_list<char*>(), TestIter2<char, types::cpp17_input_iterator_list<char*> >());
   types::for_each(types::cpp17_input_iterator_list<AddressCompare*>(),
-                 TestIter2<AddressCompare, types::cpp17_input_iterator_list<AddressCompare*> >());
+                  TestIter2<AddressCompare, types::cpp17_input_iterator_list<AddressCompare*> >());
 
   types::for_each(types::integral_types(), TestNarrowingEqualTo());
 
+#if TEST_STD_VER >= 20
+  types::for_each(
+      types::cpp17_input_iterator_list<trivially_equality_comparable*>{},
+      TestIter2<trivially_equality_comparable, types::cpp17_input_iterator_list<trivially_equality_comparable*>>{});
+#endif
+
   return true;
 }
 
@@ -119,9 +138,9 @@ int main(int, char**) {
 #endif
 
   types::for_each(types::as_pointers<types::cv_qualified_versions<int> >(),
-                 TestIter2<int, types::as_pointers<types::cv_qualified_versions<int> > >());
+                  TestIter2<int, types::as_pointers<types::cv_qualified_versions<int> > >());
   types::for_each(types::as_pointers<types::cv_qualified_versions<char> >(),
-                 TestIter2<char, types::as_pointers<types::cv_qualified_versions<char> > >());
+                  TestIter2<char, types::as_pointers<types::cv_qualified_versions<char> > >());
 
   {
     Derived d;
diff --git a/libcxx/test/std/strings/char.traits/char.traits.specializations/char.traits.specializations.char/compare.pass.cpp b/libcxx/test/std/strings/char.traits/char.traits.specializations/char.traits.specializations.char/compare.pass.cpp
index 4926b6296e73..fe65667c6944 100644
--- a/libcxx/test/std/strings/char.traits/char.traits.specializations/char.traits.specializations.char/compare.pass.cpp
+++ b/libcxx/test/std/strings/char.traits/char.traits.specializations/char.traits.specializations.char/compare.pass.cpp
@@ -18,40 +18,41 @@
 
 #include "test_macros.h"
 
-#if TEST_STD_VER > 14
-constexpr bool test_constexpr()
-{
-    return std::char_traits<char>::compare("123", "223", 3) < 0
-        && std::char_traits<char>::compare("223", "123", 3) > 0
-        && std::char_traits<char>::compare("123", "123", 3) == 0;
+TEST_CONSTEXPR_CXX17 bool test() {
+  assert(std::char_traits<char>::compare("", "", 0) == 0);
+  assert(std::char_traits<char>::compare(NULL, NULL, 0) == 0);
+
+  assert(std::char_traits<char>::compare("1", "1", 1) == 0);
+  assert(std::char_traits<char>::compare("1", "2", 1) < 0);
+  assert(std::char_traits<char>::compare("2", "1", 1) > 0);
+
+  assert(std::char_traits<char>::compare("12", "12", 2) == 0);
+  assert(std::char_traits<char>::compare("12", "13", 2) < 0);
+  assert(std::char_traits<char>::compare("12", "22", 2) < 0);
+  assert(std::char_traits<char>::compare("13", "12", 2) > 0);
+  assert(std::char_traits<char>::compare("22", "12", 2) > 0);
+
+  assert(std::char_traits<char>::compare("123", "123", 3) == 0);
+  assert(std::char_traits<char>::compare("123", "223", 3) < 0);
+  assert(std::char_traits<char>::compare("123", "133", 3) < 0);
+  assert(std::char_traits<char>::compare("123", "124", 3) < 0);
+  assert(std::char_traits<char>::compare("223", "123", 3) > 0);
+  assert(std::char_traits<char>::compare("133", "123", 3) > 0);
+  assert(std::char_traits<char>::compare("124", "123", 3) > 0);
+
+  {
+    char a[] = {static_cast<char>(-1), 0};
+    char b[] = {1, 0};
+    assert(std::char_traits<char>::compare(a, b, 1) > 0);
+  }
+
+  return true;
 }
-#endif
 
-int main(int, char**)
-{
-    assert(std::char_traits<char>::compare("", "", 0) == 0);
-    assert(std::char_traits<char>::compare(NULL, NULL, 0) == 0);
-
-    assert(std::char_traits<char>::compare("1", "1", 1) == 0);
-    assert(std::char_traits<char>::compare("1", "2", 1) < 0);
-    assert(std::char_traits<char>::compare("2", "1", 1) > 0);
-
-    assert(std::char_traits<char>::compare("12", "12", 2) == 0);
-    assert(std::char_traits<char>::compare("12", "13", 2) < 0);
-    assert(std::char_traits<char>::compare("12", "22", 2) < 0);
-    assert(std::char_traits<char>::compare("13", "12", 2) > 0);
-    assert(std::char_traits<char>::compare("22", "12", 2) > 0);
-
-    assert(std::char_traits<char>::compare("123", "123", 3) == 0);
-    assert(std::char_traits<char>::compare("123", "223", 3) < 0);
-    assert(std::char_traits<char>::compare("123", "133", 3) < 0);
-    assert(std::char_traits<char>::compare("123", "124", 3) < 0);
-    assert(std::char_traits<char>::compare("223", "123", 3) > 0);
-    assert(std::char_traits<char>::compare("133", "123", 3) > 0);
-    assert(std::char_traits<char>::compare("124", "123", 3) > 0);
-
-#if TEST_STD_VER > 14
-    static_assert(test_constexpr(), "" );
+int main(int, char**) {
+  test();
+#if TEST_STD_VER >= 17
+  static_assert(test());
 #endif
 
   return 0;