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

[philnik]

Summary

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

[ldionne]

libcxx/include/__algorithm/pstl_for_each.h

57

I guess we could do an ADL call here and if that resolves, we use that, otherwise we use this implementation. There's still difficulties with the fact that we have both a par and an unseq backend, though.

[crtrott]

I generally feel that we are better served with a overload set based on internal execution policy types. One problem I see is that we very, very fast are gonna get asked how to for example choose either SIMD or OpenMP based parallelism on a per invocation basis. The overload set based approach makes it easy to support this. Note we ARE allowed to ship implementation defined execution policies: "The semantics of parallel algorithms invoked with an execution policy object of implementation-defined type are implementation-defined." This is not undefined behavior, we just need to say what it does. That means for example we could ship std::omp_par std::omp_par_simd, std::gcd etc.. Or rather the LLVM-OpenMP project could ship std::omp_par together with a customization implementation of the algorithms. And AMD in their ROCm toolchain could add std::par_hip or something like that.

Then the only configuration decision is essentially what to map the mandated execution policies too.

Here is some code from our std::linalg prototype which does something like this:

c++
template<class .........>
void matrix_vector_product(
  ExecutionPolicy&& exec, mdspan<...> A, mdspan<...> x, mdspan<...> y)
{
  constexpr bool use_custom = is_custom_mat_vec_product_avail<
    decltype(execpolicy_mapper(exec)), decltype(A), decltype(x), decltype(y)>::value;

  if constexpr(use_custom) {
    matrix_vector_product(execpolicy_mapper(exec), A, x, y);
  } else {
    matrix_vector_product(std::experimental::linalg::impl::inline_exec_t(), A, x, y);
  }
}

Basically there are no real implementations which take any of the standard std::execution policies. We implement overloads with internal execution policies. The execpolicy_mapper(exec) will by default return exec, except for the official std::execution. policies which map to an internal one (right now for us its all mapping to
std::experimental::linalg::impl::inline_exec_t ). That actually has the advantage that you know what the internal impl does.

The is_custom_mat_vec_product_avail will check whether an overload is visible for the provided args. In linalg that allows vendor plugins to for example only provide implementations for the scalar types they got (like the fortran BLAS). That latter point probably doesn't matter to PSTL.

So a vendor shipping LLVM would be able to modify the mapper to let say std::execution::par_unseq map to hip::gpu_exec or whatever. They then can still only provide the overloads their customers asked for, while the other stuff will fallback to the default impl.

A non-llvm-shipper like Kokkos can also provide their own overloads, but they would only be called if you call std::linalg::matrix_vector_product(Kokkos::exec_policy, ...);

The last little piece not up there is that one would probably want to not just call inline_exec_t() in the else branch (if more than one internal implementation exists) but maybe check what public thing the handed exec policy is convertible too and then call the corresponding internal thing of that. I.e. you get Kokkos::exec_policy but no overload Kokkos::sort exists, however Kokkos::exec_policy is convertible to std::execution::par_unseq, so you could call impl::par_unseq overload or so.

[crtrott]

Oh if you like to I am happy to draft a different revision sketching out the above approach similar to the one here.

[philnik]

In D149686#4313646, @crtrott wrote:

I generally feel that we are better served with a overload set based on internal execution policy types. One problem I see is that we very, very fast are gonna get asked how to for example choose either SIMD or OpenMP based parallelism on a per invocation basis.

I don't understand what distinction you are making here. You can use OpenMP to generate SIMD instructions or you can use it to multi-thread your code, but there is no SIMD or OpenMP.

The overload set based approach makes it easy to support this. Note we ARE allowed to ship implementation defined execution policies: "The semantics of parallel algorithms invoked with an execution policy object of implementation-defined type are implementation-defined." This is not undefined behavior, we just need to say what it does. That means for example we could ship std::omp_par std::omp_par_simd, std::gcd etc.. Or rather the LLVM-OpenMP project could ship std::omp_par together with a customization implementation of the algorithms. And AMD in their ROCm toolchain could add std::par_hip or something like that.

That's a lot more complicated than it seems to be at first. There are a few problems I see:

• is_execution_policy_v<std::omp_par> has to return true for implementation-defined execution policies, so we wouldn't be able to use it inside the implementation of the algorithms
• We would have to push/pop macros everywhere to avoid users #defineing our implementation non-conforming
• using OpenMP, std::threads, GCD and whatever other mechanism together seems to defeat the purpose of the interface. At least as I understand it, the idea is to have an interface which brings you >90% of the way compared to writing it by hand.
• I don't really see the purpose of having the choice of selecting the backend. If there is a significant performance improvement, the implementation should be tuned instead of having the user try out X different backends to find the best one.
• This kind of customization is there in the PSTL, but it never materialized, so I don't think it's actually asked for that much

BTW the "implementation-defined" only forces us to document this. If it weren't mentioned, it would still be allowed for an implementation to support other execution policies, it just wouldn't have to be documented.

[crtrott]

I don't understand what distinction you are making here. You can use OpenMP to generate SIMD instructions or you can use it to multi-thread your code, but there is no SIMD or OpenMP.

The current draft thingy has macros to at configure time decide whether to use PSTL_UNSEQ_BACKEND_SIMD or PSTL_UNSEQ_BACKEND_SERIAL my example was just riffing off that.
But even if we just talk OpenMP there is a difference between #pragma omp parallel for and #pragma omp parallel for simd. Now we could just have that map to std::par and std::par_unseq if OpenMP is detected as enabled,
but I certainly don't want folks to need to install to versions of libcxx - one with OpenMP enabled and one with it disabled. We don't install to versions of clang for this right now.
Furthermore, in our use cases one would enable for example in ROCM HIP and OpenMP at the same time. So now users want to decide on a case by case basis whether a for_each runs with OpenMP "parallel for" "parallel for simd" or "hip_gpu". And both the "omp parallel for simd" and the "hip_gpu" presumably have the semantic meaning of "par_unseq".

That's a lot more complicated than it seems to be at first. There are a few problems I see:

• is_execution_policy_v<std::omp_par> has to return true for implementation-defined execution policies, so we wouldn't be able to use it inside the implementation of the algorithms

That is what the mapper to fully internal exec policies is for, and there would never be actual implementations using std::execution::par etc.. Those ones would always hit the "dispatch" overload, not an implementation overload.

• We would have to push/pop macros everywhere to avoid users #defineing our implementation non-conforming

How so? At most we would need to have a check function in each dispatch function which tests whether the execution policy is an allowed one in "no-implementation-defined-behavior" mode, and so that one check function needs an ifdef.

• using OpenMP, std::threads, GCD and whatever other mechanism together seems to defeat the purpose of the interface. At least as I understand it, the idea is to have an interface which brings you >90% of the way compared to writing it by hand.
• I don't really see the purpose of having the choice of selecting the backend. If there is a significant performance improvement, the implementation should be tuned instead of having the user try out X different backends to find the best one.

But for different uses of the same algorithm (i.e. different callable, different number of iterations) a different backend will be optimal. There is no way to automatically choose that optimally on the backend side.

• This kind of customization is there in the PSTL, but it never materialized, so I don't think it's actually asked for that much

Nobody really worked on this, partly because we didn't have the right people or time to do this. We (as in the HPC community and explicitly DOE) had to get ready for Exascale and there wasn't a clear path for us how to do that with pstl. Now however we are shipping implementations of pstl (in our own namespaces). Kokkos, Intel's OneAPI and NVIDIA are all doing their own version. One common thing across all of them is that we pass in stateful execution policies, because users need to provide some information in an important subset of cases. On our side probably 75% of use cases get away with defaults and then there are some which don't. More importantly we got more than one par_unseq equivalent users choose from.

BTW the "implementation-defined" only forces us to document this. If it weren't mentioned, it would still be allowed for an implementation to support other execution policies, it just wouldn't have to be documented.

Agreed, however this wording means we are allowed to have other execution policies for which is_execution_policy is true. I don't think users are allowed to provide a specialization of is_execution_policy.

[ldionne]

Update after today's discussion

[ldionne]

Update per discussion with @philnik

[ldionne]

libcxx/include/__algorithm/pstl_for_each.h

42

As @philnik pointed out, we actually can't use ADL here because our code needs to be "robust-against-adl" (tm).

[philnik]

Updated approach

[ldionne]

I like this. I think this answers all the constraints we had determined yesterday.

libcxx/include/__algorithm/pstl_backend.h

30–42

67–91

#  if defined(_PSTL_PAR_BACKEND_STD_THREAD) || defined(_PSTL_PAR_BACKEND_GCD) || defined(_PSTL_PAR_BACKEND_TBB) || defined(_PSTL_PAR_BACKEND_SERIAL)
#    include <__algorithm/pstl_backends/cpu_backend.h>
template <> struct __select_backend<std::parallel_policy> { using type = __cpu_backend; };
template <> struct __select_backend<std::parallel_unsequenced_policy> { using type = __cpu_backend; };

#elif defined(_PSTL_PAR_BACKEND_SOME_FUNKY_GPU)
#    include <__algorithm/pstl_backends/funky_gpu_backend.h>
template <> struct __select_backend<std::parallel_policy> { using type = __funky_gpu_backend; };
template <> struct __select_backend<std::parallel_unsequenced_policy> { using type = __funky_gpu_backend; };

#  else

// ...New vendors can add parallel backends here...

#    error "Invalid choice of a PSTL parallel backend"
#  endif

libcxx/include/__algorithm/pstl_backends/cpu_backend.h

19–23

#ifdef _LIBCPP_HAS_NO_THREADS
#  include <__algorithm/pstl_backends/cpu_backends/serial.h>
#elif defined(_PSTL_PAR_BACKEND_STD_THREAD)
#  include <__algorithm/pstl_backends/cpu_backends/thread.h>
#elif defined(_PSTL_PAR_BACKEND_GCD)
#  include <__algorithm/pstl_backends/cpu_backends/gcd.h>
#elif defined(_PSTL_PAR_BACKEND_TBB)
#  include <__algorithm/pstl_backends/cpu_backends/tbb.h>
#elif defined(_PSTL_PAR_BACKEND_SERIAL)
#  include <__algorithm/pstl_backends/cpu_backends/serial.h>
#else
#  error "Invalid backend choice for a CPU backend"
#endif

libcxx/include/__algorithm/pstl_for_each.h

58

[ldionne]

libcxx/include/__algorithm/pstl_for_each.h

57

We could do this in C++17:

auto __for_each_n_test = [](auto&& ...args) -> void_t<decltype(std::__pstl_for_each_n<_RawPolicy>(args...))> {};
if constexpr (__is_valid(__for_each_n_test, _Backend{}, __first, __size, __func)) {
  // ...
} else {
  // ...
}

Where:

template <typename _Func, typename ..._Args, typename = decltype(
  std::declval<_Func&&>()(std::declval<_Args&&>()...)
)>
constexpr bool __is_valid_impl(int) { return true; }

template <typename _Func, typename ..._Args>
constexpr bool __is_valid_impl(...) { return false; }

template <typename _Func, typename ..._Args>
constexpr bool __is_valid(_Func&&, _Args&& ...) {
  return __is_valid_impl<_Func&&, _Args&&...>(int{});
}

You might run into issues with __is_valid(__for_each_n_test, _Backend{}, __first, __size, __func) not being a constant expression because you are passing references to function arguments. Not sure if it'll be a problem cause you never actually read them. But if it is, then you can switch to returning -> auto std::true_c{} and -> auto std::false_c{} from your __is_valid function, and then you call it like:

if constexpr (decltype(__is_valid(as-before)){}) {
  // ...
}

OK, not quite as nice, but it works around the constexpr issue.

If you don't like this, you can also try to pass the argument types directly instead of the arguments themselves, like __is_valid<decltype(__for_each_n_test), args...>(). I'm not sure I quite like this, but it's an option on the table.

[philnik]

Refactor to making this a proper patch (and not a draft anymore)

[philnik]

Try to fix CI

[philnik]

Update wording

[philnik]

Design updated after trying to implement a few more algorithms

[philnik]

Fix the implementation

[philnik]

Generate files

[philnik]

Try to fix CI

[ldionne]

I think this is an excellent start. Then we can clean up some stuff, improve comments and move all the existing algorithms to this approach.

It turns out that once we get to the CPU backend, we basically do what the original PSTL did -- we're really just adding an additional layer of customizability on top for backends where the par/non-par split might not make sense. LGTM w/ green CI and comments addressed.

libcxx/include/__algorithm/pstl_backend.h

46–47

Let's move this to pstl_for_each.h, it seems to belong there more than here. We can also add // declaration needed for the frontend dispatch below.

libcxx/include/__algorithm/pstl_backends/cpu_backends/for_each.h

36

_HIDE_FROM_ABI

libcxx/include/__algorithm/pstl_for_each.h

61

Nit but I don't think you can move(__first) here since you are then using __first + __size.

libcxx/include/__type_traits/is_execution_policy.h

47

// TODO: Remove default argument once algorithms are using the new backend dispatching

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[crtrott]

I did not look it over super careful, but I agree that this looks like it can do the things I was most interested in having available. So I am good with merging this.

[philnik]

Next try

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Fix formatting

[philnik]

Next try

libcxx/include/CMakeLists.txt

set(files
   __algorithm/partial_sort.h
   __algorithm/partial_sort_copy.h
   __algorithm/partition.h
   __algorithm/partition_copy.h
   __algorithm/partition_point.h
   __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
   __algorithm/ranges_any_of.h
   __algorithm/ranges_binary_search.h
   __algorithm/ranges_clamp.h
   __algorithm/ranges_copy.h
   __algorithm/ranges_copy_backward.h

libcxx/include/__algorithm/pstl_backend.h

+//===----------------------------------------------------------------------===//
+//
+// 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

libcxx/include/__algorithm/pstl_backends/cpu_backend.h

+//===----------------------------------------------------------------------===//
+//
+// 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

libcxx/include/__algorithm/pstl_backends/cpu_backends/backend.h

+//===----------------------------------------------------------------------===//
+//
+// 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

libcxx/include/__algorithm/pstl_backends/cpu_backends/for_each.h

+//===----------------------------------------------------------------------===//
+//
+// 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

libcxx/include/__algorithm/pstl_backends/cpu_backends/serial.h

+// -*- 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

libcxx/include/__algorithm/pstl_for_each.h

 //===----------------------------------------------------------------------===//
 //
 // 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_FOR_EACH_H
 #define _LIBCPP___ALGORITHM_PSTL_FOR_EACH_H
 
 #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>
 #include <__pstl/internal/parallel_backend_serial.h>
 #include <__pstl/internal/unseq_backend_simd.h>
 #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)
 #  pragma GCC system_header
 #endif
 
 #if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 _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) {
+  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, __first, __first + __size, __func);
+          std::for_each(__policy, std::move(__g_first), __g_first + __g_size, std::move(__g_func));
         } else {
-    std::for_each_n(__first, __size, __func);
+          std::for_each_n(std::move(__g_first), __g_size, std::move(__g_func));
         }
+      },
+      __first,
+      __size,
+      std::move(__func));
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_FOR_EACH_H

libcxx/include/__algorithm/pstl_frontend_dispatch.h

+//===----------------------------------------------------------------------===//
+//
+// 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

libcxx/include/__config

 // TODO(varconst): currently, there are bugs in Clang's intrinsics when handling Objective-C++ `id`, so don't use
 // compiler intrinsics in the Objective-C++ mode.
 #  ifdef __OBJC__
 #    define _LIBCPP_WORKAROUND_OBJCXX_COMPILER_INTRINSICS
 #  endif
 
 // TODO: Make this a proper configuration option
 #define _PSTL_PAR_BACKEND_SERIAL
+#define _PSTL_CPU_BACKEND_SERIAL
 
 #define _PSTL_PRAGMA(x) _Pragma(#    x)
 
 // Enable SIMD for compilers that support OpenMP 4.0
 #if (defined(_OPENMP) && _OPENMP >= 201307)
 
 #  define _PSTL_UDR_PRESENT
 #  define _PSTL_PRAGMA_SIMD _PSTL_PRAGMA(omp simd)

libcxx/include/__type_traits/is_execution_policy.h

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>>;
 
+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
 
 #endif // _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___TYPE_TRAITS_IS_EXECUTION_POLICY_H

libcxx/include/execution

 #  pragma GCC system_header
 #endif
 
 #if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 _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;
   sequenced_policy& operator=(const sequenced_policy&) = delete;
 };
 
 inline constexpr sequenced_policy seq{__disable_user_instantiations_tag{}};
 

 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>
-_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{}};
   }
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP_EXECUTION

libcxx/include/module.modulemap.in

module __algorithm {
       module nth_element                     { private header "__algorithm/nth_element.h" }
       module partial_sort                    { private header "__algorithm/partial_sort.h" }
       module partial_sort_copy               { private header "__algorithm/partial_sort_copy.h" }
       module partition                       { private header "__algorithm/partition.h" }
       module partition_copy                  { private header "__algorithm/partition_copy.h" }
       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" }
       module ranges_any_of                   { private header "__algorithm/ranges_any_of.h" }
       module ranges_binary_search {
         private header "__algorithm/ranges_binary_search.h"
         export functional.__functional.ranges_operations
       }

libcxx/test/libcxx/nasty_macros.compile.pass.cpp

 //
 #ifdef __FreeBSD__
 # undef _M
 #endif
 
 // 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
 #ifndef _WIN32
 # define _UI   NASTY_MACRO
 # define _PUC  NASTY_MACRO
 # define _CPUC NASTY_MACRO
 # define _PC   NASTY_MACRO

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__algorithm/nth_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/nth_element.h'}}
 #include <__algorithm/partial_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/partial_sort.h'}}
 #include <__algorithm/partial_sort_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/partial_sort_copy.h'}}
 #include <__algorithm/partition.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/partition.h'}}
 #include <__algorithm/partition_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/partition_copy.h'}}
 #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'}}
 #include <__algorithm/ranges_any_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_any_of.h'}}
 #include <__algorithm/ranges_binary_search.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_binary_search.h'}}
 #include <__algorithm/ranges_clamp.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_clamp.h'}}
 #include <__algorithm/ranges_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy.h'}}
 #include <__algorithm/ranges_copy_backward.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy_backward.h'}}

libcxx/test/libcxx/transitive_includes/cxx03.csv

 algorithm atomic
 algorithm bit
 algorithm climits
 algorithm concepts
 algorithm cstddef
 algorithm cstdint
 algorithm cstdlib
 algorithm cstring
 algorithm ctime
+algorithm execution
 algorithm initializer_list
 algorithm iosfwd
 algorithm iterator
 algorithm limits
 algorithm memory
 algorithm new
 algorithm ratio
 algorithm stdexcept

libcxx/test/libcxx/transitive_includes/cxx11.csv

 algorithm atomic
 algorithm bit
 algorithm climits
 algorithm concepts
 algorithm cstddef
 algorithm cstdint
 algorithm cstdlib
 algorithm cstring
 algorithm ctime
+algorithm execution
 algorithm initializer_list
 algorithm iosfwd
 algorithm iterator
 algorithm limits
 algorithm memory
 algorithm new
 algorithm ratio
 algorithm stdexcept

libcxx/test/libcxx/transitive_includes/cxx14.csv

 algorithm atomic
 algorithm bit
 algorithm climits
 algorithm concepts
 algorithm cstddef
 algorithm cstdint
 algorithm cstdlib
 algorithm cstring
 algorithm ctime
+algorithm execution
 algorithm initializer_list
 algorithm iosfwd
 algorithm iterator
 algorithm limits
 algorithm memory
 algorithm new
 algorithm ratio
 algorithm stdexcept

libcxx/test/libcxx/transitive_includes/cxx17.csv

 algorithm atomic
 algorithm bit
 algorithm climits
 algorithm concepts
 algorithm cstddef
 algorithm cstdint
 algorithm cstdlib
 algorithm cstring
 algorithm ctime
+algorithm execution
 algorithm initializer_list
 algorithm iosfwd
 algorithm iterator
 algorithm limits
 algorithm memory
 algorithm new
 algorithm ratio
 algorithm stdexcept

libcxx/test/libcxx/transitive_includes/cxx20.csv

 algorithm atomic
 algorithm bit
 algorithm climits
 algorithm concepts
 algorithm cstddef
 algorithm cstdint
 algorithm cstdlib
 algorithm cstring
 algorithm ctime
+algorithm execution
 algorithm initializer_list
 algorithm iosfwd
 algorithm iterator
 algorithm limits
 algorithm memory
 algorithm new
 algorithm ratio
 algorithm stdexcept

libcxx/test/libcxx/transitive_includes/cxx2b.csv

 algorithm climits
 algorithm cstddef
 algorithm cstdint
 algorithm cstring
 algorithm ctime
+algorithm execution
 algorithm initializer_list
 algorithm iosfwd
 algorithm limits
 algorithm new
 algorithm ratio
 algorithm version
 any cstddef
 any cstdint