diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -70,9 +70,15 @@ __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 --- /dev/null +++ b/libcxx/include/__algorithm/pstl_backend.h @@ -0,0 +1,81 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +#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 + 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 + void __pstl_for_each_n(_Backend, _ExecutionPolicy&&, _Iterator __first, _Size __n, _Func __f); + +// TODO: Complete this list + +*/ + +template +struct __select_backend; + +template <> +struct __select_backend { + using type = __cpu_backend_tag; +}; + +template <> +struct __select_backend { + using type = __cpu_backend_tag; +}; + +# if defined(_PSTL_CPU_BACKEND_SERIAL) +# include <__algorithm/pstl_backends/cpu_backend.h> +template <> +struct __select_backend { + using type = __cpu_backend_tag; +}; + +template <> +struct __select_backend { + 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 --- /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 + 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 --- /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 --- /dev/null +++ b/libcxx/include/__algorithm/pstl_backends/cpu_backends/for_each.h @@ -0,0 +1,56 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +_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 +_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 // _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 --- /dev/null +++ b/libcxx/include/__algorithm/pstl_backends/cpu_backends/serial.h @@ -0,0 +1,38 @@ +// -*- 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 __serial_cpu_backend { + +template +_LIBCPP_HIDE_FROM_ABI void __parallel_for(_RandomAccessIterator __first, _RandomAccessIterator __last, _Fp __f) { + __f(__first, __last); +} + +// TODO: Complete this list + +} // namespace __par_backend::inline __serial_cpu_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 --- a/libcxx/include/__algorithm/pstl_for_each.h +++ b/libcxx/include/__algorithm/pstl_for_each.h @@ -11,12 +11,15 @@ #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/unseq_backend_simd.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) @@ -30,41 +33,37 @@ template >, int> = 0> + class _RawPolicy = __remove_cvref_t<_ExecutionPolicy>, + enable_if_t, 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); - } + using _Backend = typename __select_backend<_RawPolicy>::type; + std::__pstl_for_each<_RawPolicy>(_Backend{}, std::move(__first), std::move(__last), std::move(__func)); } +template +void __pstl_for_each_n(); // declaration needed for the frontend dispatch below + template >, int> = 0> + class _RawPolicy = __remove_cvref_t<_ExecutionPolicy>, + enable_if_t, 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 __first, _Size __size, _Function __func) { + if constexpr (__is_cpp17_random_access_iterator<_ForwardIterator>::value) { + std::for_each(__policy, std::move(__first), __first + __size, std::move(__func)); + } else { + std::for_each_n(std::move(__first), __size, std::move(__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 --- /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(__args)...)) { \ + return std::name<_RawPolicy>( \ + typename __select_backend<_RawPolicy>::type{}, std::forward(__args)...); \ + } + +template +_LIBCPP_HIDE_FROM_ABI decltype(auto) +__pstl_frontend_dispatch(_SpecializedImpl __specialized, _GenericImpl __generic, _Args&&... __args) { + if constexpr (__is_callable<_SpecializedImpl, _Args...>::value) { + return __specialized(std::forward<_Args>(__args)...); + } else { + return __generic(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 --- a/libcxx/include/__config +++ b/libcxx/include/__config @@ -1273,6 +1273,7 @@ // 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 --- a/libcxx/include/__type_traits/is_execution_policy.h +++ b/libcxx/include/__type_traits/is_execution_policy.h @@ -36,10 +36,21 @@ template 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 +_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 -_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 --- a/libcxx/include/execution +++ b/libcxx/include/execution @@ -48,10 +48,6 @@ _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 @@ struct is_execution_policy : bool_constant> {}; template -_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/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -114,6 +114,10 @@ #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/utils/data/ignore_format.txt b/libcxx/utils/data/ignore_format.txt --- a/libcxx/utils/data/ignore_format.txt +++ b/libcxx/utils/data/ignore_format.txt @@ -95,6 +95,7 @@ libcxx/include/__algorithm/partition_point.h libcxx/include/__algorithm/pop_heap.h libcxx/include/__algorithm/prev_permutation.h +libcxx/include/__algorithm/pstl_backends/cpu_backends/serial.h libcxx/include/__algorithm/push_heap.h libcxx/include/__algorithm/ranges_adjacent_find.h libcxx/include/__algorithm/ranges_all_of.h