[libc++][PSTL] Implement std::{any, all, none}_of

Reviewed By: ldionne, #libc

Spies: arichardson, libcxx-commits, miyuki

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

33 files changed, 603 insertions, 149 deletions

diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt
index d9a9fd5e660f..b9cb69b14b73 100644
--- a/libcxx/include/CMakeLists.txt
+++ b/libcxx/include/CMakeLists.txt
@@ -69,6 +69,7 @@ set(files
   __algorithm/partition_point.h
   __algorithm/pop_heap.h
   __algorithm/prev_permutation.h
+  __algorithm/pstl_any_all_none_of.h
   __algorithm/push_heap.h
   __algorithm/ranges_adjacent_find.h
   __algorithm/ranges_all_of.h
@@ -698,6 +699,7 @@ set(files
   __type_traits/is_empty.h
   __type_traits/is_enum.h
   __type_traits/is_equality_comparable.h
+  __type_traits/is_execution_policy.h
   __type_traits/is_final.h
   __type_traits/is_floating_point.h
   __type_traits/is_function.h
@@ -798,6 +800,7 @@ set(files
   __utility/priority_tag.h
   __utility/rel_ops.h
   __utility/swap.h
+  __utility/terminate_on_exception.h
   __utility/to_underlying.h
   __utility/unreachable.h
   __variant/monostate.h
diff --git a/libcxx/include/__algorithm/all_of.h b/libcxx/include/__algorithm/all_of.h
index 284c34ffcda9..237f8495c645 100644
--- a/libcxx/include/__algorithm/all_of.h
+++ b/libcxx/include/__algorithm/all_of.h
@@ -19,7 +19,7 @@
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _InputIterator, class _Predicate>
-_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 bool
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool
 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) {
   for (; __first != __last; ++__first)
     if (!__pred(*__first))
diff --git a/libcxx/include/__algorithm/pstl_any_all_none_of.h b/libcxx/include/__algorithm/pstl_any_all_none_of.h
new file mode 100644
index 000000000000..e6446c26f7e6
--- /dev/null
+++ b/libcxx/include/__algorithm/pstl_any_all_none_of.h
@@ -0,0 +1,77 @@
+//===----------------------------------------------------------------------===//
+//
+// 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___ALGORITHM_PSTL_ANY_ALL_NONE_OF_H
+#define _LIBCPP___ALGORITHM_PSTL_ANY_ALL_NONE_OF_H
+
+#include <__algorithm/any_of.h>
+#include <__config>
+#include <__functional/not_fn.h>
+#include <__pstl/internal/parallel_impl.h>
+#include <__pstl/internal/unseq_backend_simd.h>
+#include <__type_traits/enable_if.h>
+#include <__type_traits/is_execution_policy.h>
+#include <__utility/terminate_on_exception.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER >= 17
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Predicate,
+          enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
+_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI bool
+any_of(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
+  if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
+                __is_cpp17_random_access_iterator<_ForwardIterator>::value) {
+    return std::__terminate_on_exception([&] {
+      return __pstl::__internal::__parallel_or(
+          __pstl::__internal::__par_backend_tag{},
+          __policy,
+          __first,
+          __last,
+          [&__policy, &__pred](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
+            return std::any_of(std::__remove_parallel_policy(__policy), __brick_first, __brick_last, __pred);
+          });
+    });
+  } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
+                       __is_cpp17_random_access_iterator<_ForwardIterator>::value) {
+    return __pstl::__unseq_backend::__simd_or(__first, __last - __first, __pred);
+  } else {
+    return std::any_of(__first, __last, __pred);
+  }
+}
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Pred,
+          enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
+_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI bool
+all_of(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred __pred) {
+  return !std::any_of(__policy, __first, __last, std::not_fn(__pred));
+}
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Pred,
+          enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
+_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI bool
+none_of(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred __pred) {
+  return !std::any_of(__policy, __first, __last, __pred);
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER >= 17
+
+#endif // _LIBCPP___ALGORITHM_PSTL_ANY_ALL_NONE_OF_H
diff --git a/libcxx/include/__pstl/internal/algorithm_fwd.h b/libcxx/include/__pstl/internal/algorithm_fwd.h
index d8e1d2cbe7a8..798f0fe23bb5 100644
--- a/libcxx/include/__pstl/internal/algorithm_fwd.h
+++ b/libcxx/include/__pstl/internal/algorithm_fwd.h
@@ -22,29 +22,6 @@ namespace __pstl {
 namespace __internal {
 
 //------------------------------------------------------------------------
-// any_of
-//------------------------------------------------------------------------
-
-template <class _ForwardIterator, class _Pred>
-bool __brick_any_of(const _ForwardIterator,
-                    const _ForwardIterator,
-                    _Pred,
-                    /*__is_vector=*/std::false_type) noexcept;
-
-template <class _RandomAccessIterator, class _Pred>
-bool __brick_any_of(const _RandomAccessIterator,
-                    const _RandomAccessIterator,
-                    _Pred,
-                    /*__is_vector=*/std::true_type) noexcept;
-
-template <class _Tag, class _ExecutionPolicy, class _ForwardIterator, class _Pred>
-bool __pattern_any_of(_Tag, _ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Pred) noexcept;
-
-template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator, class _Pred>
-bool __pattern_any_of(
-    __parallel_tag<_IsVector>, _ExecutionPolicy&&, _RandomAccessIterator, _RandomAccessIterator, _Pred);
-
-//------------------------------------------------------------------------
 // walk1 (pseudo)
 //
 // walk1 evaluates f(x) for each dereferenced value x drawn from [first,last)
diff --git a/libcxx/include/__pstl/internal/algorithm_impl.h b/libcxx/include/__pstl/internal/algorithm_impl.h
index bad22800b9df..da2e7ecbe944 100644
--- a/libcxx/include/__pstl/internal/algorithm_impl.h
+++ b/libcxx/include/__pstl/internal/algorithm_impl.h
@@ -29,52 +29,6 @@ _PSTL_HIDE_FROM_ABI_PUSH
 namespace __pstl {
 namespace __internal {
 
-//------------------------------------------------------------------------
-// any_of
-//------------------------------------------------------------------------
-
-template <class _ForwardIterator, class _Pred>
-bool __brick_any_of(const _ForwardIterator __first,
-                    const _ForwardIterator __last,
-                    _Pred __pred,
-                    /*__is_vector=*/std::false_type) noexcept {
-  return std::any_of(__first, __last, __pred);
-};
-
-template <class _RandomAccessIterator, class _Pred>
-bool __brick_any_of(const _RandomAccessIterator __first,
-                    const _RandomAccessIterator __last,
-                    _Pred __pred,
-                    /*__is_vector=*/std::true_type) noexcept {
-  return __unseq_backend::__simd_or(__first, __last - __first, __pred);
-};
-
-template <class _Tag, class _ExecutionPolicy, class _ForwardIterator, class _Pred>
-bool __pattern_any_of(
-    _Tag, _ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __last, _Pred __pred) noexcept {
-  return __internal::__brick_any_of(__first, __last, __pred, typename _Tag::__is_vector{});
-}
-
-template <class _IsVector, class _ExecutionPolicy, class _RandomAccessIterator, class _Pred>
-bool __pattern_any_of(__parallel_tag<_IsVector> __tag,
-                      _ExecutionPolicy&& __exec,
-                      _RandomAccessIterator __first,
-                      _RandomAccessIterator __last,
-                      _Pred __pred) {
-  using __backend_tag = typename decltype(__tag)::__backend_tag;
-
-  return __internal::__except_handler([&]() {
-    return __internal::__parallel_or(
-        __backend_tag{},
-        std::forward<_ExecutionPolicy>(__exec),
-        __first,
-        __last,
-        [__pred](_RandomAccessIterator __i, _RandomAccessIterator __j) {
-          return __internal::__brick_any_of(__i, __j, __pred, _IsVector{});
-        });
-  });
-}
-
 // [alg.foreach]
 // for_each_n with no policy
 
diff --git a/libcxx/include/__pstl/internal/glue_algorithm_defs.h b/libcxx/include/__pstl/internal/glue_algorithm_defs.h
index 790cf48d8b17..f75bf28da390 100644
--- a/libcxx/include/__pstl/internal/glue_algorithm_defs.h
+++ b/libcxx/include/__pstl/internal/glue_algorithm_defs.h
@@ -20,24 +20,6 @@ _PSTL_HIDE_FROM_ABI_PUSH
 
 namespace std {
 
-// [alg.any_of]
-
-template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
-any_of(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred);
-
-// [alg.all_of]
-
-template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
-all_of(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred);
-
-// [alg.none_of]
-
-template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
-none_of(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred);
-
 // [alg.foreach]
 
 template <class _ExecutionPolicy, class _ForwardIterator, class _Function>
diff --git a/libcxx/include/__pstl/internal/glue_algorithm_impl.h b/libcxx/include/__pstl/internal/glue_algorithm_impl.h
index 6f8206a96d4f..f09b3e977b93 100644
--- a/libcxx/include/__pstl/internal/glue_algorithm_impl.h
+++ b/libcxx/include/__pstl/internal/glue_algorithm_impl.h
@@ -25,33 +25,6 @@ _PSTL_HIDE_FROM_ABI_PUSH
 
 namespace std {
 
-// [alg.any_of]
-
-template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
-any_of(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
-  auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
-
-  return __pstl::__internal::__pattern_any_of(
-      __dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __last, __pred);
-}
-
-// [alg.all_of]
-
-template <class _ExecutionPolicy, class _ForwardIterator, class _Pred>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
-all_of(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Pred __pred) {
-  return !std::any_of(std::forward<_ExecutionPolicy>(__exec), __first, __last, std::not_fn(__pred));
-}
-
-// [alg.none_of]
-
-template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, bool>
-none_of(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
-  return !std::any_of(std::forward<_ExecutionPolicy>(__exec), __first, __last, __pred);
-}
-
 // [alg.foreach]
 
 template <class _ExecutionPolicy, class _ForwardIterator, class _Function>
diff --git a/libcxx/include/__pstl/internal/parallel_backend_serial.h b/libcxx/include/__pstl/internal/parallel_backend_serial.h
index ad2c5fc60ec3..3692d9d19a18 100644
--- a/libcxx/include/__pstl/internal/parallel_backend_serial.h
+++ b/libcxx/include/__pstl/internal/parallel_backend_serial.h
@@ -10,11 +10,9 @@
 #ifndef _PSTL_PARALLEL_BACKEND_SERIAL_H
 #define _PSTL_PARALLEL_BACKEND_SERIAL_H
 
-#include <algorithm>
-#include <cstddef>
-#include <memory>
-#include <numeric>
-#include <utility>
+#include <__memory/allocator.h>
+#include <__pstl/internal/execution_impl.h>
+#include <__utility/forward.h>
 
 #include "pstl_config.h"
 
diff --git a/libcxx/include/__pstl/internal/parallel_impl.h b/libcxx/include/__pstl/internal/parallel_impl.h
index 76b3f43e0d52..aa268de3dc01 100644
--- a/libcxx/include/__pstl/internal/parallel_impl.h
+++ b/libcxx/include/__pstl/internal/parallel_impl.h
@@ -12,6 +12,7 @@
 
 #include "pstl_config.h"
 
+#include <__pstl/internal/parallel_backend.h>
 #include <atomic>
 // This header defines the minimum set of parallel routines required to support Parallel STL,
 // implemented on top of Intel(R) Threading Building Blocks (Intel(R) TBB) library
@@ -66,9 +67,7 @@ __parallel_find(_BackendTag __tag, _ExecutionPolicy&& __exec, _Index __first, _I
 //------------------------------------------------------------------------
 //! Return true if brick f[i,j) returns true for some subrange [i,j) of [first,last)
 template <class _BackendTag, class _ExecutionPolicy, class _Index, class _Brick>
-bool
-__parallel_or(_BackendTag __tag, _ExecutionPolicy&& __exec, _Index __first, _Index __last, _Brick __f)
-{
+bool __parallel_or(_BackendTag __tag, _ExecutionPolicy&& __exec, _Index __first, _Index __last, _Brick __f) {
     std::atomic<bool> __found(false);
     __par_backend::__parallel_for(__tag, std::forward<_ExecutionPolicy>(__exec), __first, __last,
                                   [__f, &__found](_Index __i, _Index __j)
diff --git a/libcxx/include/__pstl/internal/unseq_backend_simd.h b/libcxx/include/__pstl/internal/unseq_backend_simd.h
index af2a143bc58a..746157ff099c 100644
--- a/libcxx/include/__pstl/internal/unseq_backend_simd.h
+++ b/libcxx/include/__pstl/internal/unseq_backend_simd.h
@@ -10,6 +10,7 @@
 #ifndef _PSTL_UNSEQ_BACKEND_SIMD_H
 #define _PSTL_UNSEQ_BACKEND_SIMD_H
 
+#include <__functional/operations.h>
 #include <type_traits>
 
 #include "pstl_config.h"
diff --git a/libcxx/include/__pstl/internal/utils.h b/libcxx/include/__pstl/internal/utils.h
index 43e8dd279ca6..712a314bf07d 100644
--- a/libcxx/include/__pstl/internal/utils.h
+++ b/libcxx/include/__pstl/internal/utils.h
@@ -10,6 +10,7 @@
 #ifndef _PSTL_UTILS_H
 #define _PSTL_UTILS_H
 
+#include <__exception/terminate.h>
 #include <iterator>
 #include <new>
 #include <utility>
diff --git a/libcxx/include/__type_traits/is_execution_policy.h b/libcxx/include/__type_traits/is_execution_policy.h
new file mode 100644
index 000000000000..b97d94edd269
--- /dev/null
+++ b/libcxx/include/__type_traits/is_execution_policy.h
@@ -0,0 +1,48 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_EXECUTION_POLICY_H
+#define _LIBCPP___TYPE_TRAITS_IS_EXECUTION_POLICY_H
+
+#include <__config>
+#include <__type_traits/remove_cvref.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER >= 17
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class>
+inline constexpr bool is_execution_policy_v = false;
+
+template <class>
+inline constexpr bool __is_unsequenced_execution_policy_impl = false;
+
+template <class _Tp>
+inline constexpr bool __is_unsequenced_execution_policy_v =
+    __is_unsequenced_execution_policy_impl<__remove_cvref_t<_Tp>>;
+
+template <class>
+inline constexpr bool __is_parallel_execution_policy_impl = false;
+
+template <class _Tp>
+inline constexpr bool __is_parallel_execution_policy_v = __is_parallel_execution_policy_impl<__remove_cvref_t<_Tp>>;
+
+// Removes the "parallel" part of an execution policy.
+// For example, turns par_unseq into unseq, and par into seq.
+template <class _ExecutionPolicy>
+const auto& __remove_parallel_policy(_ExecutionPolicy&&);
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER >= 17
+
+#endif // _LIBCPP___TYPE_TRAITS_IS_EXECUTION_POLICY_H
diff --git a/libcxx/include/__utility/terminate_on_exception.h b/libcxx/include/__utility/terminate_on_exception.h
new file mode 100644
index 000000000000..532d8eafb2a3
--- /dev/null
+++ b/libcxx/include/__utility/terminate_on_exception.h
@@ -0,0 +1,47 @@
+//===----------------------------------------------------------------------===//
+//
+// 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___UTILITY_TERMINATE_ON_EXCEPTION_H
+#define _LIBCPP___UTILITY_TERMINATE_ON_EXCEPTION_H
+
+#include <__config>
+#include <exception>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER >= 17
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#  ifndef _LIBCPP_HAS_NO_EXCEPTIONS
+
+template <class _Func>
+_LIBCPP_HIDE_FROM_ABI auto __terminate_on_exception(_Func __func) {
+  try {
+    return __func();
+  } catch (...) {
+    std::terminate();
+  }
+}
+
+#  else  // _LIBCPP_HAS_NO_EXCEPTIONS
+
+template <class _Func>
+_LIBCPP_HIDE_FROM_ABI auto __terminate_on_exception(_Func __func) {
+  return __func();
+}
+
+#  endif // _LIBCPP_HAS_NO_EXCEPTIONS
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER >= 17
+
+#endif // _LIBCPP___UTILITY_TERMINATE_ON_EXCEPTION_H
diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm
index f5dcffa0a3f8..d8d38b875c1f 100644
--- a/libcxx/include/algorithm
+++ b/libcxx/include/algorithm
@@ -1908,6 +1908,10 @@ template <class BidirectionalIterator, class Compare>
 #include <__algorithm/unwrap_iter.h>
 #include <__algorithm/upper_bound.h>
 
+#ifdef _LIBCPP_HAS_PARALLEL_ALGORITHMS
+#  include <__algorithm/pstl_any_all_none_of.h>
+#endif
+
 // standard-mandated includes
 
 // [algorithm.syn]
diff --git a/libcxx/include/execution b/libcxx/include/execution
index 2caa60848720..a09e1b3d5ba2 100644
--- a/libcxx/include/execution
+++ b/libcxx/include/execution
@@ -34,7 +34,9 @@ namespace std {
 
 #include <__assert> // all public C++ headers provide the assertion handler
 #include <__config>
-#include <__type_traits/integral_constant.h>
+#include <__type_traits/is_execution_policy.h>
+#include <__type_traits/is_same.h>
+#include <__type_traits/remove_cvref.h>
 #include <version>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
@@ -74,6 +76,14 @@ struct parallel_unsequenced_policy {
 
 inline constexpr parallel_unsequenced_policy par_unseq{__disable_user_instantiations_tag{}};
 
+struct __unsequenced_policy {
+  constexpr explicit __unsequenced_policy(__disable_user_instantiations_tag) {}
+  __unsequenced_policy(const __unsequenced_policy&)            = delete;
+  __unsequenced_policy& operator=(const __unsequenced_policy&) = delete;
+};
+
+constexpr __unsequenced_policy __unseq{__disable_user_instantiations_tag{}};
+
 #  if _LIBCPP_STD_VER >= 20
 
 struct unsequenced_policy {
@@ -88,9 +98,6 @@ inline constexpr unsequenced_policy unseq{__disable_user_instantiations_tag{}};
 
 } // namespace execution
 
-template <class>
-inline constexpr bool is_execution_policy_v = false;
-
 template <>
 inline constexpr bool is_execution_policy_v<execution::sequenced_policy> = true;
 
@@ -100,14 +107,43 @@ inline constexpr bool is_execution_policy_v<execution::parallel_policy> = true;
 template <>
 inline constexpr bool is_execution_policy_v<execution::parallel_unsequenced_policy> = true;
 
+template <>
+inline constexpr bool is_execution_policy_v<execution::__unsequenced_policy> = true;
+
+template <>
+inline constexpr bool __is_parallel_execution_policy_impl<execution::parallel_policy> = true;
+
+template <>
+inline constexpr bool __is_parallel_execution_policy_impl<execution::parallel_unsequenced_policy> = true;
+
+template <>
+inline constexpr bool __is_unsequenced_execution_policy_impl<execution::__unsequenced_policy> = true;
+
+template <>
+inline constexpr bool __is_unsequenced_execution_policy_impl<execution::parallel_unsequenced_policy> = true;
+
 #  if _LIBCPP_STD_VER >= 20
 template <>
 inline constexpr bool is_execution_policy_v<execution::unsequenced_policy> = true;
+
+template <>
+inline constexpr bool __is_unsequenced_execution_policy_impl<execution::unsequenced_policy> = true;
+
 #  endif
 
 template <class _Tp>
 struct is_execution_policy : bool_constant<is_execution_policy_v<_Tp>> {};
 
+template <class _ExecutionPolicy>
+const auto& __remove_parallel_policy(_ExecutionPolicy&&) {
+  using _ExecPol = __remove_cvref_t<_ExecutionPolicy>;
+  if constexpr (is_same_v<_ExecPol, execution::parallel_policy>) {
+    return execution::seq;
+  } else if constexpr (is_same_v<_ExecPol, execution::parallel_unsequenced_policy>) {
+    return execution::__unseq;
+  }
+}
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17
diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in
index 2c5f8d3bd309..01f763d764e6 100644
--- a/libcxx/include/module.modulemap.in
+++ b/libcxx/include/module.modulemap.in
@@ -1555,6 +1555,7 @@ module std [system] {
       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" }
@@ -1672,29 +1673,30 @@ module std [system] {
     export *
 
     module __utility {
-      module as_const            { private header "__utility/as_const.h" }
-      module auto_cast           {
+      module as_const               { private header "__utility/as_const.h" }
+      module auto_cast              {
         private header "__utility/auto_cast.h"
         export type_traits.decay
       }
-      module cmp                 { private header "__utility/cmp.h" }
-      module convert_to_integral { private header "__utility/convert_to_integral.h" }
-      module declval             { private header "__utility/declval.h" }
-      module exception_guard     { private header "__utility/exception_guard.h" }
-      module exchange            { private header "__utility/exchange.h" }
-      module forward             { private header "__utility/forward.h" }
-      module forward_like        { private header "__utility/forward_like.h" }
-      module in_place            { private header "__utility/in_place.h" }
-      module integer_sequence    { private header "__utility/integer_sequence.h" }
-      module move                { private header "__utility/move.h" }
-      module pair                { private header "__utility/pair.h" }
-      module pair_fwd            { private header "__fwd/pair.h" }
-      module piecewise_construct { private header "__utility/piecewise_construct.h" }
-      module priority_tag        { private header "__utility/priority_tag.h" }
-      module rel_ops             { private header "__utility/rel_ops.h" }
-      module swap                { private header "__utility/swap.h" }
-      module to_underlying       { private header "__utility/to_underlying.h" }
-      module unreachable         { private header "__utility/unreachable.h" }
+      module cmp                    { private header "__utility/cmp.h" }
+      module convert_to_integral    { private header "__utility/convert_to_integral.h" }
+      module declval                { private header "__utility/declval.h" }
+      module exception_guard        { private header "__utility/exception_guard.h" }
+      module exchange               { private header "__utility/exchange.h" }
+      module forward                { private header "__utility/forward.h" }
+      module forward_like           { private header "__utility/forward_like.h" }
+      module in_place               { private header "__utility/in_place.h" }
+      module integer_sequence       { private header "__utility/integer_sequence.h" }
+      module move                   { private header "__utility/move.h" }
+      module pair                   { private header "__utility/pair.h" }
+      module pair_fwd               { private header "__fwd/pair.h" }
+      module piecewise_construct    { private header "__utility/piecewise_construct.h" }
+      module priority_tag           { private header "__utility/priority_tag.h" }
+      module rel_ops                { private header "__utility/rel_ops.h" }
+      module swap                   { private header "__utility/swap.h" }
+      module terminate_on_exception { private header "__utility/terminate_on_exception.h" }
+      module to_underlying          { private header "__utility/to_underlying.h" }
+      module unreachable            { private header "__utility/unreachable.h" }
     }
   }
   module valarray {
diff --git a/libcxx/test/libcxx/clang_tidy.sh.cpp b/libcxx/test/libcxx/clang_tidy.sh.cpp
index f04b6a5b3a50..1469d5b09f24 100644
--- a/libcxx/test/libcxx/clang_tidy.sh.cpp
+++ b/libcxx/test/libcxx/clang_tidy.sh.cpp
@@ -8,7 +8,7 @@
 
 // REQUIRES: has-clang-tidy
 
-// FIXME: This should pass with the PSTL enables
+// FIXME: This should pass with the PSTL enabled
 // XFAIL: with-pstl
 
 // The GCC compiler flags are not always compatible with clang-tidy.
diff --git a/libcxx/test/libcxx/diagnostics/pstl.nodiscard_extensions.compile.pass.cpp b/libcxx/test/libcxx/diagnostics/pstl.nodiscard_extensions.compile.pass.cpp
new file mode 100644
index 000000000000..c45c356a625a
--- /dev/null
+++ b/libcxx/test/libcxx/diagnostics/pstl.nodiscard_extensions.compile.pass.cpp
@@ -0,0 +1,27 @@
+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// Check that PSTL algorithms aren't marked [[nodiscard]] when
+// _LIBCPP_DISBALE_NODISCARD_EXT is defined
+
+// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_DISABLE_NODISCARD_EXT
+
+// REQUIRES: with-pstl
+
+// UNSUPPORTED: c++03, c++11, c++14
+
+#include <algorithm>
+#include <execution>
+
+void test() {
+  int a[] = {1};
+  auto pred = [](auto) { return false; };
+  std::all_of(std::execution::par, std::begin(a), std::end(a), pred);
+  std::any_of(std::execution::par, std::begin(a), std::end(a), pred);
+  std::none_of(std::execution::par, std::begin(a), std::end(a), pred);
+}
diff --git a/libcxx/test/libcxx/diagnostics/pstl.nodiscard_extensions.verify.cpp b/libcxx/test/libcxx/diagnostics/pstl.nodiscard_extensions.verify.cpp
new file mode 100644
index 000000000000..c1817adb2951
--- /dev/null
+++ b/libcxx/test/libcxx/diagnostics/pstl.nodiscard_extensions.verify.cpp
@@ -0,0 +1,24 @@
+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// Check that PSTL algorithms are marked [[nodiscard]] as a conforming extension
+
+// REQUIRES: with-pstl
+
+// UNSUPPORTED: c++03, c++11, c++14
+
+#include <algorithm>
+#include <execution>
+
+void test() {
+  int a[] = {1};
+  auto pred = [](auto) { return false; };
+  std::all_of(std::execution::par, std::begin(a), std::end(a), pred); // expected-warning {{ignoring return value of function declared with 'nodiscard' attribute}}
+  std::any_of(std::execution::par, std::begin(a), std::end(a), pred); // expected-warning {{ignoring return value of function declared with 'nodiscard' attribute}}
+  std::none_of(std::execution::par, std::begin(a), std::end(a), pred); // expected-warning {{ignoring return value of function declared with 'nodiscard' attribute}}
+}
diff --git a/libcxx/test/libcxx/nasty_macros.compile.pass.cpp b/libcxx/test/libcxx/nasty_macros.compile.pass.cpp
index 3e3e1340a7e3..e1bf1d5c17bb 100644
--- a/libcxx/test/libcxx/nasty_macros.compile.pass.cpp
+++ b/libcxx/test/libcxx/nasty_macros.compile.pass.cpp
@@ -9,6 +9,9 @@
 // Test that headers are not tripped up by the surrounding code defining various
 // alphabetic macros.
 
+// FIXME: This should pass with the PSTL enabled
+// XFAIL: with-pstl
+
 // Prevent <ext/hash_map> from generating deprecated warnings for this test.
 #if defined(__DEPRECATED)
 #    undef __DEPRECATED
diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp
index 806a6c51eabd..48b9a7f8c574 100644
--- a/libcxx/test/libcxx/private_headers.verify.cpp
+++ b/libcxx/test/libcxx/private_headers.verify.cpp
@@ -683,6 +683,7 @@ END-SCRIPT
 #include <__type_traits/is_empty.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/is_empty.h'}}
 #include <__type_traits/is_enum.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/is_enum.h'}}
 #include <__type_traits/is_equality_comparable.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/is_equality_comparable.h'}}
+#include <__type_traits/is_execution_policy.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/is_execution_policy.h'}}
 #include <__type_traits/is_final.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/is_final.h'}}
 #include <__type_traits/is_floating_point.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/is_floating_point.h'}}
 #include <__type_traits/is_function.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/is_function.h'}}
@@ -782,6 +783,7 @@ END-SCRIPT
 #include <__utility/priority_tag.h> // expected-error@*:* {{use of private header from outside its module: '__utility/priority_tag.h'}}
 #include <__utility/rel_ops.h> // expected-error@*:* {{use of private header from outside its module: '__utility/rel_ops.h'}}
 #include <__utility/swap.h> // expected-error@*:* {{use of private header from outside its module: '__utility/swap.h'}}
+#include <__utility/terminate_on_exception.h> // expected-error@*:* {{use of private header from outside its module: '__utility/terminate_on_exception.h'}}
 #include <__utility/to_underlying.h> // expected-error@*:* {{use of private header from outside its module: '__utility/to_underlying.h'}}
 #include <__utility/unreachable.h> // expected-error@*:* {{use of private header from outside its module: '__utility/unreachable.h'}}
 #include <__variant/monostate.h> // expected-error@*:* {{use of private header from outside its module: '__variant/monostate.h'}}
diff --git a/libcxx/test/libcxx/transitive_includes.sh.cpp b/libcxx/test/libcxx/transitive_includes.sh.cpp
index 28a1ed586b93..8523db6cfa28 100644
--- a/libcxx/test/libcxx/transitive_includes.sh.cpp
+++ b/libcxx/test/libcxx/transitive_includes.sh.cpp
@@ -32,6 +32,9 @@
 // this test instead.
 // UNSUPPORTED: transitive-includes-disabled
 
+// FIXME: This should pass with the PSTL enabled
+// XFAIL: with-pstl
+
 // Prevent <ext/hash_map> from generating deprecated warnings for this test.
 #if defined(__DEPRECATED)
 #    undef __DEPRECATED
diff --git a/libcxx/test/libcxx/transitive_includes/cxx03.csv b/libcxx/test/libcxx/transitive_includes/cxx03.csv
index ef7efa519d4b..efb07e748f56 100644
--- a/libcxx/test/libcxx/transitive_includes/cxx03.csv
+++ b/libcxx/test/libcxx/transitive_includes/cxx03.csv
@@ -213,6 +213,7 @@ exception cstddef
 exception cstdlib
 exception type_traits
 exception version
+execution cstddef
 execution version
 expected cstddef
 expected initializer_list
diff --git a/libcxx/test/libcxx/transitive_includes/cxx11.csv b/libcxx/test/libcxx/transitive_includes/cxx11.csv
index 3eecead0ae1b..0cd572f40290 100644
--- a/libcxx/test/libcxx/transitive_includes/cxx11.csv
+++ b/libcxx/test/libcxx/transitive_includes/cxx11.csv
@@ -213,6 +213,7 @@ exception cstddef
 exception cstdlib
 exception type_traits
 exception version
+execution cstddef
 execution version
 expected cstddef
 expected initializer_list
diff --git a/libcxx/test/libcxx/transitive_includes/cxx14.csv b/libcxx/test/libcxx/transitive_includes/cxx14.csv
index ec68a819d0ae..a0d7ff076dcd 100644
--- a/libcxx/test/libcxx/transitive_includes/cxx14.csv
+++ b/libcxx/test/libcxx/transitive_includes/cxx14.csv
@@ -213,6 +213,7 @@ exception cstddef
 exception cstdlib
 exception type_traits
 exception version
+execution cstddef
 execution version
 expected cstddef
 expected initializer_list
diff --git a/libcxx/test/libcxx/transitive_includes/cxx17.csv b/libcxx/test/libcxx/transitive_includes/cxx17.csv
index ec68a819d0ae..a0d7ff076dcd 100644
--- a/libcxx/test/libcxx/transitive_includes/cxx17.csv
+++ b/libcxx/test/libcxx/transitive_includes/cxx17.csv
@@ -213,6 +213,7 @@ exception cstddef
 exception cstdlib
 exception type_traits
 exception version
+execution cstddef
 execution version
 expected cstddef
 expected initializer_list
diff --git a/libcxx/test/libcxx/transitive_includes/cxx20.csv b/libcxx/test/libcxx/transitive_includes/cxx20.csv
index c3a309a70952..57a75bd9959b 100644
--- a/libcxx/test/libcxx/transitive_includes/cxx20.csv
+++ b/libcxx/test/libcxx/transitive_includes/cxx20.csv
@@ -221,6 +221,7 @@ exception cstddef
 exception cstdlib
 exception type_traits
 exception version
+execution cstddef
 execution version
 expected cstddef
 expected initializer_list
diff --git a/libcxx/test/libcxx/transitive_includes/cxx2b.csv b/libcxx/test/libcxx/transitive_includes/cxx2b.csv
index 7b82ae1016a5..aa2161fe38fb 100644
--- a/libcxx/test/libcxx/transitive_includes/cxx2b.csv
+++ b/libcxx/test/libcxx/transitive_includes/cxx2b.csv
@@ -140,6 +140,7 @@ deque version
 exception cstddef
 exception cstdlib
 exception version
+execution cstddef
 execution version
 expected cstddef
 expected initializer_list
diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.all_of/pstl.all_of.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.all_of/pstl.all_of.pass.cpp
new file mode 100644
index 000000000000..eab06883b4f0
--- /dev/null
+++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.all_of/pstl.all_of.pass.cpp
@@ -0,0 +1,83 @@
+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14
+
+// REQUIRES: with-pstl
+
+// <algorithm>
+
+// template<class ExecutionPolicy, class ForwardIterator, class Predicate>
+//   bool any_of(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
+//               Predicate pred);
+
+#include <algorithm>
+#include <cassert>
+#include <vector>
+
+#include "test_macros.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+EXECUTION_POLICY_SFINAE_TEST(all_of);
+
+static_assert(sfinae_test_all_of<int, int*, int*, bool (*)(int)>);
+static_assert(!sfinae_test_all_of<std::execution::parallel_policy, int*, int*, bool (*)(int)>);
+
+template <class Iter>
+struct Test {
+  template <class Policy>
+  void operator()(Policy&& policy) {
+    int a[] = {1, 2, 3, 4, 5, 6, 7, 8};
+    // simple test
+    assert(std::all_of(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i < 9; }));
+    assert(!std::all_of(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i < 8; }));
+
+    // check that an empty range works
+    assert(std::all_of(policy, Iter(std::begin(a)), Iter(std::begin(a)), [](int) { return true; }));
+
+    // check that a single-element range works
+    assert(std::all_of(policy, Iter(a), Iter(a + 1), [](int i) { return i < 2; }));
+
+    // check that a two-element range works
+    assert(std::all_of(policy, Iter(a), Iter(a + 2), [](int i) { return i < 3; }));
+
+    // check that false is returned if no element satisfies the condition
+    assert(!std::all_of(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i == 9; }));
+
+    // check that false is returned if only one elements satisfies the condition
+    assert(!std::all_of(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i == 1; }));
+
+    // check that a one-element range works
+    assert(std::all_of(policy, Iter(std::begin(a)), Iter(std::begin(a) + 1), [](int i) { return i == 1; }));
+
+    // check that a two-element range works
+    assert(std::all_of(policy, Iter(std::begin(a)), Iter(std::begin(a) + 2), [](int i) { return i < 3; }));
+
+    // check that a large number of elements works
+    std::vector<int> vec(100);
+    std::fill(vec.begin(), vec.end(), 3);
+    assert(std::all_of(Iter(vec.data()), Iter(vec.data() + vec.size()), [](int i) { return i == 3; }));
+  }
+};
+
+int main(int, char**) {
+  types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+  std::set_terminate(terminate_successful);
+  int a[] = {1, 2};
+  try {
+    (void)std::all_of(std::execution::par, std::begin(a), std::end(a), [](int i) -> bool { throw i; });
+  } catch (int) {
+    assert(false);
+  }
+#endif
+
+  return 0;
+}
diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.any_of/pstl.any_of.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.any_of/pstl.any_of.pass.cpp
new file mode 100644
index 000000000000..c47aa1820f26
--- /dev/null
+++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.any_of/pstl.any_of.pass.cpp
@@ -0,0 +1,77 @@
+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14
+
+// REQUIRES: with-pstl
+
+// <algorithm>
+
+// template<class ExecutionPolicy, class ForwardIterator, class Predicate>
+//   bool any_of(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
+//               Predicate pred);
+
+#include <algorithm>
+#include <cassert>
+#include <vector>
+
+#include "test_macros.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+EXECUTION_POLICY_SFINAE_TEST(any_of);
+
+static_assert(sfinae_test_any_of<int, int*, int*, bool (*)(int)>);
+static_assert(!sfinae_test_any_of<std::execution::parallel_policy, int*, int*, bool (*)(int)>);
+
+template <class Iter>
+struct Test {
+  template <class Policy>
+  void operator()(Policy&& policy) {
+    int a[] = {1, 2, 3, 4, 5, 6, 7, 8};
+    // simple test
+    assert(std::any_of(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i < 9; }));
+    assert(!std::any_of(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i > 8; }));
+
+    // check that an empty range works
+    assert(!std::any_of(policy, Iter(std::begin(a)), Iter(std::begin(a)), [](int) { return false; }));
+
+    // check that false is returned if no element satisfies the condition
+    assert(!std::any_of(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i == 9; }));
+
+    // check that true is returned if only one elements satisfies the condition
+    assert(std::any_of(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i == 1; }));
+
+    // check that a one-element range works
+    assert(std::any_of(policy, Iter(std::begin(a)), Iter(std::begin(a) + 1), [](int i) { return i == 1; }));
+
+    // check that a two-element range works
+    assert(std::any_of(policy, Iter(std::begin(a)), Iter(std::begin(a) + 2), [](int i) { return i == 2; }));
+
+    // check that a large number of elements works
+    std::vector<int> vec(100, 2);
+    vec[96] = 3;
+    assert(std::any_of(Iter(vec.data()), Iter(vec.data() + vec.size()), [](int i) { return i == 3; }));
+  }
+};
+
+int main(int, char**) {
+  types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+  std::set_terminate(terminate_successful);
+  int a[] = {1, 2};
+  try {
+    (void)std::any_of(std::execution::par, std::begin(a), std::end(a), [](int i) -> bool { throw i; });
+  } catch (int) {
+    assert(false);
+  }
+#endif
+
+  return 0;
+}
diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.none_of/pstl.none_of.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.none_of/pstl.none_of.pass.cpp
new file mode 100644
index 000000000000..af9482b1f0c2
--- /dev/null
+++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.none_of/pstl.none_of.pass.cpp
@@ -0,0 +1,75 @@
+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: with-pstl
+
+// <algorithm>
+
+// template<class ExecutionPolicy, class ForwardIterator, class Predicate>
+//   bool any_of(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
+//               Predicate pred);
+
+#include <algorithm>
+#include <cassert>
+#include <vector>
+
+#include "test_macros.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+EXECUTION_POLICY_SFINAE_TEST(none_of);
+
+static_assert(sfinae_test_none_of<int, int*, int*, bool (*)(int)>);
+static_assert(!sfinae_test_none_of<std::execution::parallel_policy, int*, int*, bool (*)(int)>);
+
+template <class Iter>
+struct Test {
+  template <class Policy>
+  void operator()(Policy&& policy) {
+    int a[] = {1, 2, 3, 4, 5, 6, 7, 8};
+    // simple test
+    assert(std::none_of(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i > 9; }));
+    assert(!std::none_of(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i >= 8; }));
+
+    // check that an empty range works
+    assert(std::none_of(policy, Iter(std::begin(a)), Iter(std::begin(a)), [](int) { return false; }));
+
+    // check that true is returned if no element satisfies the condition
+    assert(std::none_of(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i == 9; }));
+
+    // check that false is returned if only one elements satisfies the condition
+    assert(!std::none_of(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i == 1; }));
+
+    // check that a one-element range works
+    assert(std::none_of(policy, Iter(std::begin(a)), Iter(std::begin(a) + 1), [](int i) { return i != 1; }));
+
+    // check that a two-element range works
+    assert(std::none_of(policy, Iter(std::begin(a)), Iter(std::begin(a) + 2), [](int i) { return i > 2; }));
+
+    // check that a large number of elements works
+    std::vector<int> vec(100);
+    std::fill(vec.begin(), vec.end(), 3);
+    assert(std::none_of(Iter(vec.data()), Iter(vec.data() + vec.size()), [](int i) { return i != 3; }));
+  }
+};
+
+int main(int, char**) {
+  types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+  std::set_terminate(terminate_successful);
+  int a[] = {1, 2};
+  try {
+    (void)std::none_of(std::execution::par, std::begin(a), std::end(a), [](int i) -> bool { throw i; });
+  } catch (int) {
+    assert(false);
+  }
+#endif
+
+  return 0;
+}
diff --git a/libcxx/test/support/test_execution_policies.h b/libcxx/test/support/test_execution_policies.h
new file mode 100644
index 000000000000..5d106b13c1c0
--- /dev/null
+++ b/libcxx/test/support/test_execution_policies.h
@@ -0,0 +1,52 @@
+//===----------------------------------------------------------------------===//
+//
+// 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 TEST_SUPPORT_TEST_EXECUTION_POLICIES
+#define TEST_SUPPORT_TEST_EXECUTION_POLICIES
+
+#include <cstdlib>
+#include <execution>
+#include <type_traits>
+#include <utility>
+
+#include "test_macros.h"
+
+#define EXECUTION_POLICY_SFINAE_TEST(function)                                                                         \
+  template <class, class...>                                                                                           \
+  struct sfinae_test_##function##_impl : std::true_type {};                                                            \
+                                                                                                                       \
+  template <class... Args>                                                                                             \
+  struct sfinae_test_##function##_impl<std::void_t<decltype(std::function(std::declval<Args>()...))>, Args...>         \
+      : std::false_type {};                                                                                            \
+                                                                                                                       \
+  template <class... Args>                                                                                             \
+  constexpr bool sfinae_test_##function = sfinae_test_##function##_impl<void, Args...>::value;
+
+template <class Functor>
+bool test_execution_policies(Functor func) {
+  func(std::execution::seq);
+#if TEST_STD_VER >= 20
+  func(std::execution::unseq);
+#endif
+  func(std::execution::par);
+  func(std::execution::par_unseq);
+
+  return true;
+}
+
+template <template <class Iter> class TestClass>
+struct TestIteratorWithPolicies {
+  template <class Iter>
+  void operator()() {
+    test_execution_policies(TestClass<Iter>{});
+  }
+};
+
+[[noreturn]] inline void terminate_successful() { std::exit(0); }
+
+#endif // TEST_SUPPORT_TEST_EXECUTION_POLICIES
diff --git a/libcxx/utils/generate_header_tests.py b/libcxx/utils/generate_header_tests.py
index d2f18883f8ab..eacf1f8d8419 100755
--- a/libcxx/utils/generate_header_tests.py
+++ b/libcxx/utils/generate_header_tests.py
@@ -128,7 +128,7 @@ def main():
     experimental_headers = sorted(str(p.relative_to(include)) for p in include.glob('experimental/[a-z]*') if is_header(p))
     extended_headers     = sorted(str(p.relative_to(include)) for p in include.glob('ext/[a-z]*') if is_header(p))
     public_headers       = toplevel_headers + experimental_headers + extended_headers
-    private_headers      = sorted(str(p.relative_to(include)) for p in include.rglob('*') if is_header(p) and str(p.relative_to(include)).startswith('__'))
+    private_headers      = sorted(str(p.relative_to(include)) for p in include.rglob('*') if is_header(p) and str(p.relative_to(include)).startswith('__') and not p.name.startswith('pstl'))
     variables = {
         'toplevel_headers': toplevel_headers,
         'experimental_headers': experimental_headers,