[libc++][PSTL] Add more specialized backend customization points

This allows backends to customize arbitrary parallel algorithms, which was requested pretty often.

Reviewed By: #libc, ldionne

Spies: arichardson, miyuki, crtrott, dalg24, __simt__, philnik, libcxx-commits

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

20 files changed, 348 insertions, 37 deletions

diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt
index 9222b5284464..74464427348a 100644
--- a/libcxx/include/CMakeLists.txt
+++ b/libcxx/include/CMakeLists.txt
@@ -70,9 +70,15 @@ set(files
   __algorithm/pop_heap.h
   __algorithm/prev_permutation.h
   __algorithm/pstl_any_all_none_of.h
+  __algorithm/pstl_backend.h
+  __algorithm/pstl_backends/cpu_backend.h
+  __algorithm/pstl_backends/cpu_backends/backend.h
+  __algorithm/pstl_backends/cpu_backends/for_each.h
+  __algorithm/pstl_backends/cpu_backends/serial.h
   __algorithm/pstl_fill.h
   __algorithm/pstl_find.h
   __algorithm/pstl_for_each.h
+  __algorithm/pstl_frontend_dispatch.h
   __algorithm/push_heap.h
   __algorithm/ranges_adjacent_find.h
   __algorithm/ranges_all_of.h
diff --git a/libcxx/include/__algorithm/pstl_backend.h b/libcxx/include/__algorithm/pstl_backend.h
new file mode 100644
index 000000000000..587720e0ddf3
--- /dev/null
+++ b/libcxx/include/__algorithm/pstl_backend.h
@@ -0,0 +1,82 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_BACKEND_H
+#define _LIBCPP___ALGORITHM_PSTL_BACKEND_H
+
+#include <__algorithm/pstl_backends/cpu_backend.h>
+#include <__config>
+#include <execution>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+/*
+TODO: Documentation of how backends work
+
+A PSTL parallel backend is a tag type to which the following functions are associated, at minimum:
+
+  template <class _ExecutionPolicy, class _Iterator, class _Func>
+  void __pstl_for_each(_Backend, _ExecutionPolicy&&, _Iterator __first, _Iterator __last, _Func __f);
+
+// TODO: Complete this list
+
+The following functions are optional but can be provided. If provided, they are used by the corresponding
+algorithms, otherwise they are implemented in terms of other algorithms. If none of the optional algorithms are
+implemented, all the algorithms will eventually forward to the basis algorithms listed above:
+
+  template <class _ExecutionPolicy, class _Iterator, class _Size, class _Func>
+  void __pstl_for_each_n(_Backend, _ExecutionPolicy&&, _Iterator __first, _Size __n, _Func __f);
+
+// TODO: Complete this list
+
+*/
+
+template <class _ExecutionPolicy>
+struct __select_backend;
+
+template <>
+struct __select_backend<std::execution::sequenced_policy> {
+  using type = __cpu_backend_tag;
+};
+
+#  if _LIBCPP_STD_VER >= 20
+template <>
+struct __select_backend<std::execution::unsequenced_policy> {
+  using type = __cpu_backend_tag;
+};
+#  endif
+
+#  if defined(_PSTL_CPU_BACKEND_SERIAL)
+template <>
+struct __select_backend<std::execution::parallel_policy> {
+  using type = __cpu_backend_tag;
+};
+
+template <>
+struct __select_backend<std::execution::parallel_unsequenced_policy> {
+  using type = __cpu_backend_tag;
+};
+
+#  else
+
+// ...New vendors can add parallel backends here...
+
+#    error "Invalid choice of a PSTL parallel backend"
+#  endif
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+#endif // _LIBCPP___ALGORITHM_PSTL_BACKEND_H
diff --git a/libcxx/include/__algorithm/pstl_backends/cpu_backend.h b/libcxx/include/__algorithm/pstl_backends/cpu_backend.h
new file mode 100644
index 000000000000..b12d45462546
--- /dev/null
+++ b/libcxx/include/__algorithm/pstl_backends/cpu_backend.h
@@ -0,0 +1,25 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_BACKENDS_CPU_BACKEND_H
+#define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_H
+
+#include <__config>
+
+/*
+
+  // _Functor takes a subrange for [__first, __last) that should be executed in serial
+  template <class _RandomAccessIterator, class _Functor>
+  void __parallel_for(_RandomAccessIterator __first, _RandomAccessIterator __last, _Functor __func);
+
+  TODO: Document the parallel backend
+*/
+
+#include <__algorithm/pstl_backends/cpu_backends/for_each.h>
+
+#endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_H
diff --git a/libcxx/include/__algorithm/pstl_backends/cpu_backends/backend.h b/libcxx/include/__algorithm/pstl_backends/cpu_backends/backend.h
new file mode 100644
index 000000000000..d6b03d282bd3
--- /dev/null
+++ b/libcxx/include/__algorithm/pstl_backends/cpu_backends/backend.h
@@ -0,0 +1,30 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_BACKENDS_CPU_BACKEND_BACKEND_H
+#define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_BACKEND_H
+
+#include <__config>
+
+#if defined(_LIBCPP_HAS_NO_THREADS) || defined(_PSTL_CPU_BACKEND_SERIAL)
+#  include <__algorithm/pstl_backends/cpu_backends/serial.h>
+#else
+#  error "Invalid CPU backend choice"
+#endif
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+struct __cpu_backend_tag {};
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_BACKEND_H
diff --git a/libcxx/include/__algorithm/pstl_backends/cpu_backends/for_each.h b/libcxx/include/__algorithm/pstl_backends/cpu_backends/for_each.h
new file mode 100644
index 000000000000..1d3ca817f4e0
--- /dev/null
+++ b/libcxx/include/__algorithm/pstl_backends/cpu_backends/for_each.h
@@ -0,0 +1,60 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_BACKENDS_CPU_BACKNEDS_FOR_EACH_H
+#define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKNEDS_FOR_EACH_H
+
+#include <__algorithm/for_each.h>
+#include <__algorithm/pstl_backends/cpu_backends/backend.h>
+#include <__config>
+#include <__iterator/iterator_traits.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 !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _Iterator, class _DifferenceType, class _Function>
+_LIBCPP_HIDE_FROM_ABI _Iterator __simd_walk_1(_Iterator __first, _DifferenceType __n, _Function __f) noexcept {
+  _PSTL_PRAGMA_SIMD
+  for (_DifferenceType __i = 0; __i < __n; ++__i)
+    __f(__first[__i]);
+
+  return __first + __n;
+}
+
+template <class _ExecutionPolicy, class _ForwardIterator, class _Functor>
+_LIBCPP_HIDE_FROM_ABI void
+__pstl_for_each(__cpu_backend_tag, _ForwardIterator __first, _ForwardIterator __last, _Functor __func) {
+  if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
+                __is_cpp17_random_access_iterator<_ForwardIterator>::value) {
+    std::__terminate_on_exception([&] {
+      std::__par_backend::__parallel_for(
+          __first, __last, [__func](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
+            std::__pstl_for_each<__remove_parallel_policy_t<_ExecutionPolicy>>(
+                __cpu_backend_tag{}, __brick_first, __brick_last, __func);
+          });
+    });
+  } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
+                       __is_cpp17_random_access_iterator<_ForwardIterator>::value) {
+    std::__simd_walk_1(__first, __last - __first, __func);
+  } else {
+    std::for_each(__first, __last, __func);
+  }
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+#endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKNEDS_FOR_EACH_H
diff --git a/libcxx/include/__algorithm/pstl_backends/cpu_backends/serial.h b/libcxx/include/__algorithm/pstl_backends/cpu_backends/serial.h
new file mode 100644
index 000000000000..24bac4fc26a9
--- /dev/null
+++ b/libcxx/include/__algorithm/pstl_backends/cpu_backends/serial.h
@@ -0,0 +1,40 @@
+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// 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_BACKENDS_CPU_BACKENDS_SERIAL_H
+#define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_SERIAL_H
+
+#include <__config>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace __par_backend {
+inline namespace __serial_cpu_backend {
+
+template <class _RandomAccessIterator, class _Fp>
+_LIBCPP_HIDE_FROM_ABI void __parallel_for(_RandomAccessIterator __first, _RandomAccessIterator __last, _Fp __f) {
+  __f(__first, __last);
+}
+
+// TODO: Complete this list
+
+} // namespace __serial_cpu_backend
+} // namespace __par_backend
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && && _LIBCPP_STD_VER >= 17
+
+#endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_SERIAL_H
diff --git a/libcxx/include/__algorithm/pstl_for_each.h b/libcxx/include/__algorithm/pstl_for_each.h
index 339e7268f82e..4e183c6f388b 100644
--- a/libcxx/include/__algorithm/pstl_for_each.h
+++ b/libcxx/include/__algorithm/pstl_for_each.h
@@ -11,6 +11,8 @@
 
 #include <__algorithm/for_each.h>
 #include <__algorithm/for_each_n.h>
+#include <__algorithm/pstl_backend.h>
+#include <__algorithm/pstl_frontend_dispatch.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__pstl/internal/parallel_backend.h>
@@ -19,6 +21,7 @@
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/remove_cvref.h>
+#include <__type_traits/void_t.h>
 #include <__utility/terminate_on_exception.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
@@ -32,41 +35,37 @@ _LIBCPP_BEGIN_NAMESPACE_STD
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _Function,
-          enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
 _LIBCPP_HIDE_FROM_ABI void
-for_each(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Function __func) {
-  if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
-                __is_cpp17_random_access_iterator<_ForwardIterator>::value) {
-    std::__terminate_on_exception([&] {
-      __pstl::__par_backend::__parallel_for(
-          {},
-          __policy,
-          __first,
-          __last,
-          [&__policy, __func](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
-            std::for_each(std::__remove_parallel_policy(__policy), __brick_first, __brick_last, __func);
-          });
-    });
-  } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
-                       __is_cpp17_random_access_iterator<_ForwardIterator>::value) {
-    __pstl::__unseq_backend::__simd_walk_1(__first, __last - __first, __func);
-  } else {
-    std::for_each(__first, __last, __func);
-  }
+for_each(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __last, _Function __func) {
+  using _Backend = typename __select_backend<_RawPolicy>::type;
+  std::__pstl_for_each<_RawPolicy>(_Backend{}, std::move(__first), std::move(__last), std::move(__func));
 }
 
+template <class>
+void __pstl_for_each_n(); // declaration needed for the frontend dispatch below
+
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _Size,
           class _Function,
-          enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
 _LIBCPP_HIDE_FROM_ABI void
 for_each_n(_ExecutionPolicy&& __policy, _ForwardIterator __first, _Size __size, _Function __func) {
-  if constexpr (__is_cpp17_random_access_iterator<_ForwardIterator>::value) {
-    std::for_each(__policy, __first, __first + __size, __func);
-  } else {
-    std::for_each_n(__first, __size, __func);
-  }
+  return std::__pstl_frontend_dispatch(
+      _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_for_each_n),
+      [&](_ForwardIterator __g_first, _Size __g_size, _Function __g_func) {
+        if constexpr (__is_cpp17_random_access_iterator<_ForwardIterator>::value) {
+          std::for_each(__policy, std::move(__g_first), __g_first + __g_size, std::move(__g_func));
+        } else {
+          std::for_each_n(std::move(__g_first), __g_size, std::move(__g_func));
+        }
+      },
+      __first,
+      __size,
+      std::move(__func));
 }
 
 _LIBCPP_END_NAMESPACE_STD
diff --git a/libcxx/include/__algorithm/pstl_frontend_dispatch.h b/libcxx/include/__algorithm/pstl_frontend_dispatch.h
new file mode 100644
index 000000000000..dc49f3e5163a
--- /dev/null
+++ b/libcxx/include/__algorithm/pstl_frontend_dispatch.h
@@ -0,0 +1,45 @@
+//===----------------------------------------------------------------------===//
+//
+// 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_FRONTEND_DISPATCH
+#define _LIBCPP___ALGORITHM_PSTL_FRONTEND_DISPATCH
+
+#include <__config>
+#include <__type_traits/is_callable.h>
+#include <__utility/forward.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER >= 17
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#  define _LIBCPP_PSTL_CUSTOMIZATION_POINT(name)                                                                       \
+    [](auto&&... __args) -> decltype(std::name<_RawPolicy>(typename __select_backend<_RawPolicy>::type{},              \
+                                                           std::forward<decltype(__args)>(__args)...)) {               \
+      return std::name<_RawPolicy>(                                                                                    \
+          typename __select_backend<_RawPolicy>::type{}, std::forward<decltype(__args)>(__args)...);                   \
+    }
+
+template <class _SpecializedImpl, class _GenericImpl, class... _Args>
+_LIBCPP_HIDE_FROM_ABI decltype(auto)
+__pstl_frontend_dispatch(_SpecializedImpl __specialized_impl, _GenericImpl __generic_impl, _Args&&... __args) {
+  if constexpr (__is_callable<_SpecializedImpl, _Args...>::value) {
+    return __specialized_impl(std::forward<_Args>(__args)...);
+  } else {
+    return __generic_impl(std::forward<_Args>(__args)...);
+  }
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER >= 17
+
+#endif // _LIBCPP___ALGORITHM_PSTL_FRONTEND_DISPATCH
diff --git a/libcxx/include/__config b/libcxx/include/__config
index b08646b2465f..86156c8521fd 100644
--- a/libcxx/include/__config
+++ b/libcxx/include/__config
@@ -1273,6 +1273,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD _LIBCPP_END_NAMESPACE_STD
 
 // TODO: Make this a proper configuration option
 #define _PSTL_PAR_BACKEND_SERIAL
+#define _PSTL_CPU_BACKEND_SERIAL
 
 #define _PSTL_PRAGMA(x) _Pragma(#    x)
 
diff --git a/libcxx/include/__type_traits/is_execution_policy.h b/libcxx/include/__type_traits/is_execution_policy.h
index fabc345b6c09..6884f17ba16c 100644
--- a/libcxx/include/__type_traits/is_execution_policy.h
+++ b/libcxx/include/__type_traits/is_execution_policy.h
@@ -36,10 +36,21 @@ 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>>;
 
+namespace execution {
+struct __disable_user_instantiations_tag {
+  explicit __disable_user_instantiations_tag() = default;
+};
+} // namespace execution
+
+// TODO: Remove default argument once algorithms are using the new backend dispatching
+template <class _ExecutionPolicy>
+_LIBCPP_HIDE_FROM_ABI auto
+__remove_parallel_policy(const _ExecutionPolicy& = _ExecutionPolicy{execution::__disable_user_instantiations_tag{}});
+
 // Removes the "parallel" part of an execution policy.
 // For example, turns par_unseq into unseq, and par into seq.
 template <class _ExecutionPolicy>
-_LIBCPP_HIDE_FROM_ABI const auto& __remove_parallel_policy(_ExecutionPolicy&&);
+using __remove_parallel_policy_t = decltype(std::__remove_parallel_policy<_ExecutionPolicy>());
 
 _LIBCPP_END_NAMESPACE_STD
 
diff --git a/libcxx/include/execution b/libcxx/include/execution
index d20fea0f05c8..56facc87379e 100644
--- a/libcxx/include/execution
+++ b/libcxx/include/execution
@@ -48,10 +48,6 @@ namespace std {
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace execution {
-struct __disable_user_instantiations_tag {
-  explicit __disable_user_instantiations_tag() = default;
-};
-
 struct sequenced_policy {
   _LIBCPP_HIDE_FROM_ABI constexpr explicit sequenced_policy(__disable_user_instantiations_tag) {}
   sequenced_policy(const sequenced_policy&)            = delete;
@@ -135,12 +131,11 @@ template <class _Tp>
 struct is_execution_policy : bool_constant<is_execution_policy_v<_Tp>> {};
 
 template <class _ExecutionPolicy>
-_LIBCPP_HIDE_FROM_ABI 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_HIDE_FROM_ABI auto __remove_parallel_policy(const _ExecutionPolicy&) {
+  if constexpr (is_same_v<_ExecutionPolicy, execution::parallel_policy>) {
+    return execution::sequenced_policy(execution::__disable_user_instantiations_tag{});
+  } else if constexpr (is_same_v<_ExecutionPolicy, execution::parallel_unsequenced_policy>) {
+    return execution::__unsequenced_policy{execution::__disable_user_instantiations_tag{}};
   }
 }
 
diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in
index 6b7bba1d1d41..33baaf6efead 100644
--- a/libcxx/include/module.modulemap.in
+++ b/libcxx/include/module.modulemap.in
@@ -320,6 +320,12 @@ module std [system] {
       module partition_point                 { private header "__algorithm/partition_point.h" }
       module pop_heap                        { private header "__algorithm/pop_heap.h" }
       module prev_permutation                { private header "__algorithm/prev_permutation.h" }
+      module pstl {
+        private header "__algorithm/pstl_backends/cpu_backend.h"
+        private header "__algorithm/pstl_backends/cpu_backends/backend.h"
+        private header "__algorithm/pstl_backends/cpu_backends/for_each.h"
+        private header "__algorithm/pstl_backends/cpu_backends/serial.h"
+      }
       module push_heap                       { private header "__algorithm/push_heap.h" }
       module ranges_adjacent_find            { private header "__algorithm/ranges_adjacent_find.h" }
       module ranges_all_of                   { private header "__algorithm/ranges_all_of.h" }
diff --git a/libcxx/test/libcxx/nasty_macros.compile.pass.cpp b/libcxx/test/libcxx/nasty_macros.compile.pass.cpp
index 28b3162678d5..5254e0d78e88 100644
--- a/libcxx/test/libcxx/nasty_macros.compile.pass.cpp
+++ b/libcxx/test/libcxx/nasty_macros.compile.pass.cpp
@@ -54,6 +54,7 @@
 // Test that libc++ doesn't use names that collide with FreeBSD system macros.
 #ifndef __FreeBSD__
 #  define __null_sentinel NASTY_MACRO
+#  define __generic
 #endif
 
 // tchar.h defines these macros on Windows
diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp
index c7d035274c56..9dd2607f1dc1 100644
--- a/libcxx/test/libcxx/private_headers.verify.cpp
+++ b/libcxx/test/libcxx/private_headers.verify.cpp
@@ -114,6 +114,10 @@ END-SCRIPT
 #include <__algorithm/partition_point.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/partition_point.h'}}
 #include <__algorithm/pop_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pop_heap.h'}}
 #include <__algorithm/prev_permutation.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/prev_permutation.h'}}
+#include <__algorithm/pstl_backends/cpu_backend.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backend.h'}}
+#include <__algorithm/pstl_backends/cpu_backends/backend.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/backend.h'}}
+#include <__algorithm/pstl_backends/cpu_backends/for_each.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/for_each.h'}}
+#include <__algorithm/pstl_backends/cpu_backends/serial.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/serial.h'}}
 #include <__algorithm/push_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/push_heap.h'}}
 #include <__algorithm/ranges_adjacent_find.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_adjacent_find.h'}}
 #include <__algorithm/ranges_all_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_all_of.h'}}
diff --git a/libcxx/test/libcxx/transitive_includes/cxx03.csv b/libcxx/test/libcxx/transitive_includes/cxx03.csv
index 408fe33c61c3..172f222d18cb 100644
--- a/libcxx/test/libcxx/transitive_includes/cxx03.csv
+++ b/libcxx/test/libcxx/transitive_includes/cxx03.csv
@@ -7,6 +7,7 @@ algorithm cstdint
 algorithm cstdlib
 algorithm cstring
 algorithm ctime
+algorithm execution
 algorithm initializer_list
 algorithm iosfwd
 algorithm iterator
diff --git a/libcxx/test/libcxx/transitive_includes/cxx11.csv b/libcxx/test/libcxx/transitive_includes/cxx11.csv
index a14e23db18f6..f75a9987622e 100644
--- a/libcxx/test/libcxx/transitive_includes/cxx11.csv
+++ b/libcxx/test/libcxx/transitive_includes/cxx11.csv
@@ -7,6 +7,7 @@ algorithm cstdint
 algorithm cstdlib
 algorithm cstring
 algorithm ctime
+algorithm execution
 algorithm initializer_list
 algorithm iosfwd
 algorithm iterator
diff --git a/libcxx/test/libcxx/transitive_includes/cxx14.csv b/libcxx/test/libcxx/transitive_includes/cxx14.csv
index 6d780f829cb7..f402f3e2e66d 100644
--- a/libcxx/test/libcxx/transitive_includes/cxx14.csv
+++ b/libcxx/test/libcxx/transitive_includes/cxx14.csv
@@ -7,6 +7,7 @@ algorithm cstdint
 algorithm cstdlib
 algorithm cstring
 algorithm ctime
+algorithm execution
 algorithm initializer_list
 algorithm iosfwd
 algorithm iterator
diff --git a/libcxx/test/libcxx/transitive_includes/cxx17.csv b/libcxx/test/libcxx/transitive_includes/cxx17.csv
index 6d780f829cb7..f402f3e2e66d 100644
--- a/libcxx/test/libcxx/transitive_includes/cxx17.csv
+++ b/libcxx/test/libcxx/transitive_includes/cxx17.csv
@@ -7,6 +7,7 @@ algorithm cstdint
 algorithm cstdlib
 algorithm cstring
 algorithm ctime
+algorithm execution
 algorithm initializer_list
 algorithm iosfwd
 algorithm iterator
diff --git a/libcxx/test/libcxx/transitive_includes/cxx20.csv b/libcxx/test/libcxx/transitive_includes/cxx20.csv
index d7090b6470ca..79ad40506851 100644
--- a/libcxx/test/libcxx/transitive_includes/cxx20.csv
+++ b/libcxx/test/libcxx/transitive_includes/cxx20.csv
@@ -7,6 +7,7 @@ algorithm cstdint
 algorithm cstdlib
 algorithm cstring
 algorithm ctime
+algorithm execution
 algorithm initializer_list
 algorithm iosfwd
 algorithm iterator
diff --git a/libcxx/test/libcxx/transitive_includes/cxx2b.csv b/libcxx/test/libcxx/transitive_includes/cxx2b.csv
index a950e70633c7..833df27c70f5 100644
--- a/libcxx/test/libcxx/transitive_includes/cxx2b.csv
+++ b/libcxx/test/libcxx/transitive_includes/cxx2b.csv
@@ -3,6 +3,7 @@ algorithm cstddef
 algorithm cstdint
 algorithm cstring
 algorithm ctime
+algorithm execution
 algorithm initializer_list
 algorithm iosfwd
 algorithm limits