[libc++][PSTL] Implement std::reduce and std::transform_reduce

[philnik]

Generate files

[philnik]

Try to fix CI

[ldionne]

libcxx/include/__algorithm/pstl_backends/cpu_backend.h

19–22

You should document the new customization point here for the CPU backend.

And you should also document the new "customization points" in the general backend.

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

33

inline constexpr?

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

165

Do we not have a simd version for this one?

libcxx/include/__numeric/pstl_reduce.h

37

We should be dispatching here and below.

I think we should add a test that allows catching that. It would also give us confidence that our dispatching mechanism works as intended, which we don't know right now:

struct TestPolicy { };
struct TestBackendTag { };

template <>
struct std::__select_backend<TestPolicy> { using type = TestBackendTag; };

It would also confirm that we're able to add new implementation-defined policies if need be, which is clearly one of the design points of our dispatching mechanism.

libcxx/include/__numeric/pstl_transform_reduce.h

57

I don't think so, because we are able to detect that this has been called in the generic version via the operation traits. I would leave a comment explaining why this one doesn't get a dispatch.

libcxx/test/std/algorithms/numeric.ops/reduce/pstl.reduce.pass.cpp

28

Same!

50

Probably a leftover from debugging?

78

We can do with lambdas?

libcxx/test/std/algorithms/numeric.ops/transform.reduce/pstl.transform_reduce.binary.pass.cpp

91

Can be done with lambdas.

libcxx/test/std/algorithms/numeric.ops/transform.reduce/pstl.transform_reduce.unary.pass.cpp

26

Here and below.

65

Lambdas.

[philnik]

Address comments

[philnik]

Try to fix CI

[ldionne]

libcxx/include/__algorithm/pstl_backend.h

61

_Backend parameter missing

99

_Backend missing here and below.

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

24

You will need to also implement this for the std::thread backend.

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

117

Once you add a test for move-only types, I would assume that this line is going to fail cause you're missing a std::move.

135

This should also fail with move-only types. If it doesn't, we are missing coverage.

libcxx/include/__numeric/pstl_reduce.h

44

Can you capture the __policy by name explicitly? Otherwise one might wonder whether you're capturing a variable that you're moving in the lines below.

61

Same comment as above for capturing.

libcxx/test/std/algorithms/numeric.ops/transform.reduce/pstl.transform_reduce.binary.pass.cpp

2

Can you please take a look at the stuff we test for the serial version of these algorithms and make sure we have coverage for that? For example, std::transform_reduce has tests for move-only types but we don't seem to test that here.

[philnik]

Address comments

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Try to fix CI

libcxx/include/CMakeLists.txt

set(files
   __algorithm/pstl_backends/cpu_backends/backend.h
   __algorithm/pstl_backends/cpu_backends/fill.h
   __algorithm/pstl_backends/cpu_backends/find_if.h
   __algorithm/pstl_backends/cpu_backends/for_each.h
   __algorithm/pstl_backends/cpu_backends/merge.h
   __algorithm/pstl_backends/cpu_backends/serial.h
   __algorithm/pstl_backends/cpu_backends/thread.h
   __algorithm/pstl_backends/cpu_backends/transform.h
+  __algorithm/pstl_backends/cpu_backends/transform_reduce.h
   __algorithm/pstl_copy.h
   __algorithm/pstl_fill.h
   __algorithm/pstl_find.h
   __algorithm/pstl_for_each.h
   __algorithm/pstl_frontend_dispatch.h
   __algorithm/pstl_merge.h
   __algorithm/pstl_transform.h
   __algorithm/push_heap.h
set(files
   __numeric/adjacent_difference.h
   __numeric/exclusive_scan.h
   __numeric/gcd_lcm.h
   __numeric/inclusive_scan.h
   __numeric/inner_product.h
   __numeric/iota.h
   __numeric/midpoint.h
   __numeric/partial_sum.h
+  __numeric/pstl_reduce.h
+  __numeric/pstl_transform_reduce.h
   __numeric/reduce.h
   __numeric/transform_exclusive_scan.h
   __numeric/transform_inclusive_scan.h
   __numeric/transform_reduce.h
   __pstl/internal/algorithm_fwd.h
   __pstl/internal/algorithm_impl.h
   __pstl/internal/execution_defs.h
   __pstl/internal/execution_impl.h
set(files
   __type_traits/make_32_64_or_128_bit.h
   __type_traits/make_const_lvalue_ref.h
   __type_traits/make_signed.h
   __type_traits/make_unsigned.h
   __type_traits/maybe_const.h
   __type_traits/nat.h
   __type_traits/negation.h
   __type_traits/noexcept_move_assign_container.h
+  __type_traits/operation_traits.h
   __type_traits/predicate_traits.h
   __type_traits/promote.h
   __type_traits/rank.h
   __type_traits/remove_all_extents.h
   __type_traits/remove_const.h
   __type_traits/remove_const_ref.h
   __type_traits/remove_cv.h
   __type_traits/remove_cvref.h

libcxx/include/__algorithm/pstl_backend.h

A PSTL parallel backend is a tag type to which the following functions are associated, at minimum:
 
   template <class _ExecutionPolicy, class _InIterator1, class _InIterator2, class _OutIterator, class _BinaryOperation>
   _OutIterator __pstl_transform(_InIterator1 __first1,
                                 _InIterator1 __last1,
                                 _InIterator2 __first2,
                                 _OutIterator __result,
                                 _BinaryOperation __op);
 
+  template <class _ExecutionPolicy,
+            class _Iterator1,
+            class _Iterator2,
+            class _Tp,
+            class _BinaryOperation1,
+            class _BinaryOperation2>
+  _Tp __pstl_transform_reduce(_Backend,
+                              _Iterator1 __first1,
+                              _Iterator1 __last1,
+                              _Iterator2 __first2,
+                              _Iterator2 __last2,
+                              _Tp __init,
+                              _BinaryOperation1 __reduce,
+                              _BinaryOperation2 __transform);
+
+  template <class _ExecutionPolicy, class _Iterator, class _Tp, class _BinaryOperation, class _UnaryOperation>
+  _Tp __pstl_transform_reduce(_Backend,
+                              _Iterator __first,
+                              _Iterator __last,
+                              _Tp __init,
+                              _BinaryOperation __reduce,
+                              _UnaryOperation __transform);
+
 // 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, _Iterator __first, _Size __n, _Func __f);
implemented, all the algorithms will eventually forward to the basis algorithms listed above:
 
   template <class _ExecutionPolicy, class _Iterator, class _Tp>
   void __pstl_fill(_Backend, _Iterator __first, _Iterator __last, const _Tp& __value);
 
   template <class _ExecutionPolicy, class _Iterator, class _SizeT, class _Tp>
   void __pstl_fill_n(_Backend, _Iterator __first, _SizeT __n, const _Tp& __value);
 
   template <class _ExecutionPolicy, class _terator1, class _Iterator2, class _OutIterator, class _Comp>
   _OutIterator __pstl_merge(_Backend,
                             _Iterator1 __first1,
                             _Iterator1 __last1,
                             _Iterator2 __first2,
                             _Iterator2 __last2,
                             _OutIterator __result,
                             _Comp __comp);
 
+  template <class _ExecutionPolicy, class _Iterator, class _Tp, class _BinaryOperation>
+  _Tp __pstl_reduce(_Backend, _Iterator __first, _Iterator __last, _Tp __init, _BinaryOperation __op);
+
+  temlate <class _ExecutionPolicy, class _Iterator>
+  __iter_value_type<_Iterator> __pstl_reduce(_Backend, _Iterator __first, _Iterator __last);
+
 // TODO: Complete this list
 
 */
 
 template <class _ExecutionPolicy>
 struct __select_backend;
 
 template <>

libcxx/include/__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);
 
+  template <class _Iterator, class _UnaryOp, class _Tp, class _BinaryOp, class _Reduction>
+  _Tp __parallel_transform_reduce(_Iterator __first, _Iterator __last, _UnaryOp, _Tp __init, _BinaryOp, _Reduction);
+
   // Cancel the execution of other jobs - they aren't needed anymore
   void __cancel_execution();
 
   template <class _RandomAccessIterator1,
             class _RandomAccessIterator2,
             class _RandomAccessIterator3,
             class _Compare,
             class _LeafMerge>
   void __parallel_merge(
       _RandomAccessIterator1 __first1,
       _RandomAccessIterator1 __last1,
       _RandomAccessIterator2 __first2,
       _RandomAccessIterator2 __last2,
       _RandomAccessIterator3 __outit,
       _Compare __comp,
       _LeafMerge __leaf_merge);
 
   TODO: Document the parallel backend
 */
 
 #include <__algorithm/pstl_backends/cpu_backends/any_of.h>
+#include <__algorithm/pstl_backends/cpu_backends/backend.h>
 #include <__algorithm/pstl_backends/cpu_backends/fill.h>
 #include <__algorithm/pstl_backends/cpu_backends/find_if.h>
 #include <__algorithm/pstl_backends/cpu_backends/for_each.h>
 #include <__algorithm/pstl_backends/cpu_backends/merge.h>
 #include <__algorithm/pstl_backends/cpu_backends/transform.h>
+#include <__algorithm/pstl_backends/cpu_backends/transform_reduce.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>
+#include <cstddef>
 
 #if defined(_LIBCPP_PSTL_CPU_BACKEND_SERIAL)
 #  include <__algorithm/pstl_backends/cpu_backends/serial.h>
 #elif defined(_LIBCPP_PSTL_CPU_BACKEND_THREAD)
 #  include <__algorithm/pstl_backends/cpu_backends/thread.h>
 #else
 #  error "Invalid CPU backend choice"
 #endif
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
+#if _LIBCPP_STD_VER >= 17
+
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 struct __cpu_backend_tag {};
 
+inline constexpr size_t __lane_size = 64;
+
 _LIBCPP_END_NAMESPACE_STD
 
+#endif // _LIBCPP_STD_VER >= 17
+
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_BACKEND_H

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

if (__comp(__i - __first, __extremum)) {
           __extremum.compare_exchange_weak(__old, __k);
         }
       }
     }
   });
   return __extremum != __initial_dist ? __first + __extremum : __last;
 }
 
-const std::size_t __lane_size = 64;
-
 template <class _Index, class _DifferenceType, class _Compare>
 _LIBCPP_HIDE_FROM_ABI _Index
 __simd_first(_Index __first, _DifferenceType __begin, _DifferenceType __end, _Compare __comp) noexcept {
   // Experiments show good block sizes like this
   const _DifferenceType __block_size                        = 8;
   alignas(__lane_size) _DifferenceType __lane[__block_size] = {0};
   while (__end - __begin >= __block_size) {
     _DifferenceType __found = 0;

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>
+#include <__utility/move.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
 
 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);
 }
 
+template <class _Index, class _UnaryOp, class _Tp, class _BinaryOp, class _Reduce>
+_LIBCPP_HIDE_FROM_ABI _Tp
+__parallel_transform_reduce(_Index __first, _Index __last, _UnaryOp, _Tp __init, _BinaryOp, _Reduce __reduce) {
+  return __reduce(std::move(__first), std::move(__last), std::move(__init));
+}
+
 _LIBCPP_HIDE_FROM_ABI inline void __cancel_execution() {}
 
 template <class _RandomAccessIterator1,
           class _RandomAccessIterator2,
           class _RandomAccessIterator3,
           class _Compare,
           class _LeafMerge>
 _LIBCPP_HIDE_FROM_ABI void __parallel_merge(

libcxx/include/__algorithm/pstl_backends/cpu_backends/thread.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_BACKENDS_THREAD_H
 #define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_THREAD_H
 
 #include <__assert>
 #include <__config>
+#include <__utility/move.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
 
 // This backend implementation is for testing purposes only and not meant for production use. This will be replaced
 // by a proper implementation once the PSTL implementation is somewhat stable.
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace __par_backend {
 inline namespace __thread_cpu_backend {
 
 template <class _RandomAccessIterator, class _Fp>
 _LIBCPP_HIDE_FROM_ABI void __parallel_for(_RandomAccessIterator __first, _RandomAccessIterator __last, _Fp __f) {
   __f(__first, __last);
 }
 
+template <class _Index, class _UnaryOp, class _Tp, class _BinaryOp, class _Reduce>
+_LIBCPP_HIDE_FROM_ABI _Tp
+__parallel_transform_reduce(_Index __first, _Index __last, _UnaryOp, _Tp __init, _BinaryOp, _Reduce __reduce) {
+  return __reduce(std::move(__first), std::move(__last), std::move(__init));
+}
+
 _LIBCPP_HIDE_FROM_ABI inline void __cancel_execution() {}
 
 template <class _RandomAccessIterator1,
           class _RandomAccessIterator2,
           class _RandomAccessIterator3,
           class _Compare,
           class _LeafMerge>
 _LIBCPP_HIDE_FROM_ABI void __parallel_merge(

libcxx/include/__algorithm/pstl_backends/cpu_backends/transform_reduce.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_BACKENDS_TRANSFORM_REDUCE_H
+#define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_TRANSFORM_REDUCE_H
+
+#include <__algorithm/pstl_backends/cpu_backends/backend.h>
+#include <__config>
+#include <__iterator/iterator_traits.h>
+#include <__numeric/transform_reduce.h>
+#include <__type_traits/is_arithmetic.h>
+#include <__type_traits/is_execution_policy.h>
+#include <__type_traits/operation_traits.h>
+#include <__utility/move.h>
+#include <__utility/terminate_on_exception.h>
+#include <new>
+
+#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 <
+    typename _DifferenceType,
+    typename _Tp,
+    typename _BinaryOperation,
+    typename _UnaryOperation,
+    __enable_if_t<__is_trivial_plus_operation<_BinaryOperation, _Tp, _Tp>::value && is_arithmetic_v<_Tp>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _Tp
+__simd_transform_reduce(_DifferenceType __n, _Tp __init, _BinaryOperation, _UnaryOperation __f) noexcept {
+  _PSTL_PRAGMA_SIMD_REDUCTION(+ : __init)
+  for (_DifferenceType __i = 0; __i < __n; ++__i)
+    __init += __f(__i);
+  return __init;
+}
+
+template <
+    typename _Size,
+    typename _Tp,
+    typename _BinaryOperation,
+    typename _UnaryOperation,
+    __enable_if_t<!(__is_trivial_plus_operation<_BinaryOperation, _Tp, _Tp>::value && is_arithmetic_v<_Tp>), int> = 0>
+_LIBCPP_HIDE_FROM_ABI _Tp
+__simd_transform_reduce(_Size __n, _Tp __init, _BinaryOperation __binary_op, _UnaryOperation __f) noexcept {
+  const _Size __block_size = __lane_size / sizeof(_Tp);
+  if (__n > 2 * __block_size && __block_size > 1) {
+    alignas(__lane_size) char __lane_buffer[__lane_size];
+    _Tp* __lane = reinterpret_cast<_Tp*>(__lane_buffer);
+
+    // initializer
+    _PSTL_PRAGMA_SIMD
+    for (_Size __i = 0; __i < __block_size; ++__i) {
+      ::new (__lane + __i) _Tp(__binary_op(__f(__i), __f(__block_size + __i)));
+    }
+    // main loop
+    _Size __i                    = 2 * __block_size;
+    const _Size __last_iteration = __block_size * (__n / __block_size);
+    for (; __i < __last_iteration; __i += __block_size) {
+      _PSTL_PRAGMA_SIMD
+      for (_Size __j = 0; __j < __block_size; ++__j) {
+        __lane[__j] = __binary_op(std::move(__lane[__j]), __f(__i + __j));
+      }
+    }
+    // remainder
+    _PSTL_PRAGMA_SIMD
+    for (_Size __j = 0; __j < __n - __last_iteration; ++__j) {
+      __lane[__j] = __binary_op(std::move(__lane[__j]), __f(__last_iteration + __j));
+    }
+    // combiner
+    for (_Size __j = 0; __j < __block_size; ++__j) {
+      __init = __binary_op(std::move(__init), std::move(__lane[__j]));
+    }
+    // destroyer
+    _PSTL_PRAGMA_SIMD
+    for (_Size __j = 0; __j < __block_size; ++__j) {
+      __lane[__j].~_Tp();
+    }
+  } else {
+    for (_Size __i = 0; __i < __n; ++__i) {
+      __init = __binary_op(std::move(__init), __f(__i));
+    }
+  }
+  return __init;
+}
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator1,
+          class _ForwardIterator2,
+          class _Tp,
+          class _BinaryOperation1,
+          class _BinaryOperation2>
+_LIBCPP_HIDE_FROM_ABI _Tp __pstl_transform_reduce(
+    __cpu_backend_tag,
+    _ForwardIterator1 __first1,
+    _ForwardIterator1 __last1,
+    _ForwardIterator2 __first2,
+    _Tp __init,
+    _BinaryOperation1 __reduce,
+    _BinaryOperation2 __transform) {
+  if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
+                __has_random_access_iterator_category<_ForwardIterator1>::value &&
+                __has_random_access_iterator_category<_ForwardIterator2>::value) {
+    return std::__terminate_on_exception([&] {
+      return __par_backend::__parallel_transform_reduce(
+          __first1,
+          std::move(__last1),
+          [__first1, __first2, __transform](_ForwardIterator1 __iter) {
+            return __transform(*__iter, *(__first2 + (__iter - __first1)));
+          },
+          std::move(__init),
+          std::move(__reduce),
+          [__first1, __first2, __reduce, __transform](
+              _ForwardIterator1 __brick_first, _ForwardIterator1 __brick_last, _Tp __brick_init) {
+            return std::__pstl_transform_reduce<__remove_parallel_policy_t<_ExecutionPolicy>>(
+                __cpu_backend_tag{},
+                __brick_first,
+                std::move(__brick_last),
+                __first2 + (__brick_first - __first1),
+                std::move(__brick_init),
+                std::move(__reduce),
+                std::move(__transform));
+          });
+    });
+  } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
+                       __has_random_access_iterator_category<_ForwardIterator1>::value &&
+                       __has_random_access_iterator_category<_ForwardIterator2>::value) {
+    return std::__simd_transform_reduce(
+        __last1 - __first1, std::move(__init), std::move(__reduce), [&](__iter_diff_t<_ForwardIterator1> __i) {
+          return __transform(__first1[__i], __first2[__i]);
+        });
+  } else {
+    return std::transform_reduce(
+        std::move(__first1),
+        std::move(__last1),
+        std::move(__first2),
+        std::move(__init),
+        std::move(__reduce),
+        std::move(__transform));
+  }
+}
+
+template <class _ExecutionPolicy, class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation>
+_LIBCPP_HIDE_FROM_ABI _Tp __pstl_transform_reduce(
+    __cpu_backend_tag,
+    _ForwardIterator __first,
+    _ForwardIterator __last,
+    _Tp __init,
+    _BinaryOperation __reduce,
+    _UnaryOperation __transform) {
+  if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
+                __has_random_access_iterator_category<_ForwardIterator>::value) {
+    return std::__terminate_on_exception([&] {
+      return __par_backend::__parallel_transform_reduce(
+          std::move(__first),
+          std::move(__last),
+          [__transform](_ForwardIterator __iter) { return __transform(*__iter); },
+          std::move(__init),
+          std::move(__reduce),
+          [=](_ForwardIterator __brick_first, _ForwardIterator __brick_last, _Tp __brick_init) {
+            return std::__pstl_transform_reduce<__remove_parallel_policy_t<_ExecutionPolicy>>(
+                __cpu_backend_tag{},
+                std::move(__brick_first),
+                std::move(__brick_last),
+                std::move(__brick_init),
+                std::move(__reduce),
+                std::move(__transform));
+          });
+    });
+  } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
+                       __has_random_access_iterator_category<_ForwardIterator>::value) {
+    return std::__simd_transform_reduce(
+        __last - __first,
+        std::move(__init),
+        std::move(__reduce),
+        [=, &__transform](__iter_diff_t<_ForwardIterator> __i) { return __transform(__first[__i]); });
+  } else {
+    return std::transform_reduce(
+        std::move(__first), std::move(__last), std::move(__init), std::move(__reduce), std::move(__transform));
+  }
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+#endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_TRANSFORM_REDUCE_H

libcxx/include/__functional/operations.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___FUNCTIONAL_OPERATIONS_H
 #define _LIBCPP___FUNCTIONAL_OPERATIONS_H
 
 #include <__config>
 #include <__functional/binary_function.h>
 #include <__functional/unary_function.h>
 #include <__type_traits/integral_constant.h>
+#include <__type_traits/operation_traits.h>
 #include <__type_traits/predicate_traits.h>
 #include <__utility/forward.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD

 {
     typedef _Tp __result_type;  // used by valarray
     _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_INLINE_VISIBILITY
     _Tp operator()(const _Tp& __x, const _Tp& __y) const
         {return __x + __y;}
 };
 _LIBCPP_CTAD_SUPPORTED_FOR_TYPE(plus);
 
+template <class _Tp>
+struct __is_trivial_plus_operation<plus<_Tp>, _Tp, _Tp> : true_type {};
+
+#if _LIBCPP_STD_VER >= 14
+template <class _Tp, class _Up>
+struct __is_trivial_plus_operation<plus<>, _Tp, _Up> : true_type {};
+#endif
+
 #if _LIBCPP_STD_VER >= 14
 template <>
 struct _LIBCPP_TEMPLATE_VIS plus<void>
 {
     template <class _T1, class _T2>
     _LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_INLINE_VISIBILITY
     auto operator()(_T1&& __t, _T2&& __u) const
         noexcept(noexcept(_VSTD::forward<_T1>(__t) + _VSTD::forward<_T2>(__u)))

libcxx/include/__numeric/pstl_reduce.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___NUMERIC_PSTL_REDUCE_H
+#define _LIBCPP___NUMERIC_PSTL_REDUCE_H
+
+#include <__algorithm/pstl_frontend_dispatch.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__iterator/iterator_traits.h>
+#include <__numeric/pstl_transform_reduce.h>
+#include <__type_traits/is_execution_policy.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>
+void __pstl_reduce();
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Tp,
+          class _BinaryOperation                              = plus<>,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _Tp
+reduce(_ExecutionPolicy&& __policy,
+       _ForwardIterator __first,
+       _ForwardIterator __last,
+       _Tp __init,
+       _BinaryOperation __op = {}) {
+  return std::__pstl_frontend_dispatch(
+      _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_reduce),
+      [&__policy](_ForwardIterator __g_first, _ForwardIterator __g_last, _Tp __g_init, _BinaryOperation __g_op) {
+        return std::transform_reduce(
+            __policy, std::move(__g_first), std::move(__g_last), std::move(__g_init), std::move(__g_op), __identity{});
+      },
+      std::move(__first),
+      std::move(__last),
+      std::move(__init),
+      std::move(__op));
+}
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI __iter_value_type<_ForwardIterator>
+reduce(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last) {
+  return std::__pstl_frontend_dispatch(
+      _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_reduce),
+      [&__policy](_ForwardIterator __g_first, _ForwardIterator __g_last) {
+        return std::reduce(__policy, __g_first, __g_last, __iter_value_type<_ForwardIterator>());
+      },
+      std::move(__first),
+      std::move(__last));
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+#endif // _LIBCPP___NUMERIC_PSTL_REDUCE_H

libcxx/include/__numeric/pstl_transform_reduce.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___NUMERIC_PSTL_TRANSFORM_REDUCE_H
+#define _LIBCPP___NUMERIC_PSTL_TRANSFORM_REDUCE_H
+
+#include <__algorithm/pstl_backend.h>
+#include <__algorithm/pstl_frontend_dispatch.h>
+#include <__config>
+#include <__functional/operations.h>
+#include <__numeric/transform_reduce.h>
+#include <__type_traits/is_execution_policy.h>
+#include <__utility/move.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 _ForwardIterator1,
+          class _ForwardIterator2,
+          class _Tp,
+          class _BinaryOperation1,
+          class _BinaryOperation2,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _Tp transform_reduce(
+    _ExecutionPolicy&&,
+    _ForwardIterator1 __first1,
+    _ForwardIterator1 __last1,
+    _ForwardIterator2 __first2,
+    _Tp __init,
+    _BinaryOperation1 __reduce,
+    _BinaryOperation2 __transform) {
+  using _Backend = typename __select_backend<_RawPolicy>::type;
+  return std::__pstl_transform_reduce<_RawPolicy>(
+      _Backend{},
+      std::move(__first1),
+      std::move(__last1),
+      std::move(__first2),
+      std::move(__init),
+      std::move(__reduce),
+      std::move(__transform));
+}
+
+// This overload doesn't get a customization point because it's trivial to detect (through e.g.
+// __is_trivial_plus_operation) when specializing the more general variant, which should always be preferred
+template <class _ExecutionPolicy,
+          class _ForwardIterator1,
+          class _ForwardIterator2,
+          class _Tp,
+          enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _Tp transform_reduce(
+    _ExecutionPolicy&& __policy,
+    _ForwardIterator1 __first1,
+    _ForwardIterator1 __last1,
+    _ForwardIterator2 __first2,
+    _Tp __init) {
+  return std::transform_reduce(__policy, __first1, __last1, __first2, __init, plus{}, multiplies{});
+}
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Tp,
+          class _BinaryOperation,
+          class _UnaryOperation,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _Tp transform_reduce(
+    _ExecutionPolicy&&,
+    _ForwardIterator __first,
+    _ForwardIterator __last,
+    _Tp __init,
+    _BinaryOperation __reduce,
+    _UnaryOperation __transform) {
+  using _Backend = typename __select_backend<_RawPolicy>::type;
+  return std::__pstl_transform_reduce<_RawPolicy>(
+      _Backend{},
+      std::move(__first),
+      std::move(__last),
+      std::move(__init),
+      std::move(__reduce),
+      std::move(__transform));
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+#endif // _LIBCPP___NUMERIC_PSTL_TRANSFORM_REDUCE_H

libcxx/include/__numeric/transform_reduce.h

 _LIBCPP_BEGIN_NAMESPACE_STD
 
 #if _LIBCPP_STD_VER >= 17
 template <class _InputIterator, class _Tp, class _BinaryOp, class _UnaryOp>
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 _Tp transform_reduce(_InputIterator __first,
                                                                              _InputIterator __last, _Tp __init,
                                                                              _BinaryOp __b, _UnaryOp __u) {
   for (; __first != __last; ++__first)
-    __init = __b(__init, __u(*__first));
+    __init = __b(std::move(__init), __u(*__first));
   return __init;
 }
 
 template <class _InputIterator1, class _InputIterator2, class _Tp, class _BinaryOp1, class _BinaryOp2>
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 _Tp transform_reduce(_InputIterator1 __first1,
                                                                              _InputIterator1 __last1,
                                                                              _InputIterator2 __first2, _Tp __init,
                                                                              _BinaryOp1 __b1, _BinaryOp2 __b2) {
   for (; __first1 != __last1; ++__first1, (void)++__first2)
-    __init = __b1(__init, __b2(*__first1, *__first2));
+    __init = __b1(std::move(__init), __b2(*__first1, *__first2));
   return __init;
 }
 
 template <class _InputIterator1, class _InputIterator2, class _Tp>
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 _Tp transform_reduce(_InputIterator1 __first1,
                                                                              _InputIterator1 __last1,
                                                                              _InputIterator2 __first2, _Tp __init) {
   return _VSTD::transform_reduce(__first1, __last1, __first2, _VSTD::move(__init), _VSTD::plus<>(),
                                  _VSTD::multiplies<>());
 }
 #endif
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___NUMERIC_TRANSFORM_REDUCE_H

libcxx/include/__pstl/internal/glue_numeric_defs.h

 #define _PSTL_GLUE_NUMERIC_DEFS_H
 
 #include <__config>
 #include <iterator>
 
 #include "execution_defs.h"
 
 namespace std {
-// [reduce]
-
-template <class _ExecutionPolicy, class _ForwardIterator, class _Tp, class _BinaryOperation>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp>
-reduce(_ExecutionPolicy&& __exec,
-       _ForwardIterator __first,
-       _ForwardIterator __last,
-       _Tp __init,
-       _BinaryOperation __binary_op);
-
-template <class _ExecutionPolicy, class _ForwardIterator, class _Tp>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp>
-reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Tp __init);
-
-template <class _ExecutionPolicy, class _ForwardIterator>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy,
-                                                 typename iterator_traits<_ForwardIterator>::value_type>
-reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last);
-
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Tp>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp> transform_reduce(
-    _ExecutionPolicy&& __exec,
-    _ForwardIterator1 __first1,
-    _ForwardIterator1 __last1,
-    _ForwardIterator2 __first2,
-    _Tp __init);
-
-template <class _ExecutionPolicy,
-          class _ForwardIterator1,
-          class _ForwardIterator2,
-          class _Tp,
-          class _BinaryOperation1,
-          class _BinaryOperation2>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp> transform_reduce(
-    _ExecutionPolicy&& __exec,
-    _ForwardIterator1 __first1,
-    _ForwardIterator1 __last1,
-    _ForwardIterator2 __first2,
-    _Tp __init,
-    _BinaryOperation1 __binary_op1,
-    _BinaryOperation2 __binary_op2);
-
-template <class _ExecutionPolicy, class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp> transform_reduce(
-    _ExecutionPolicy&& __exec,
-    _ForwardIterator __first,
-    _ForwardIterator __last,
-    _Tp __init,
-    _BinaryOperation __binary_op,
-    _UnaryOperation __unary_op);
-
 // [exclusive.scan]
 
 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Tp>
 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> exclusive_scan(
     _ExecutionPolicy&& __exec,
     _ForwardIterator1 __first,
     _ForwardIterator1 __last,
     _ForwardIterator2 __result,

libcxx/include/__pstl/internal/glue_numeric_impl.h

 #include <functional>
 
 #include "execution_impl.h"
 #include "numeric_fwd.h"
 #include "utils.h"
 
 namespace std {
 
-// [reduce]
-
-template <class _ExecutionPolicy, class _ForwardIterator, class _Tp, class _BinaryOperation>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp>
-reduce(_ExecutionPolicy&& __exec,
-       _ForwardIterator __first,
-       _ForwardIterator __last,
-       _Tp __init,
-       _BinaryOperation __binary_op) {
-  return transform_reduce(
-      std::forward<_ExecutionPolicy>(__exec), __first, __last, __init, __binary_op, __pstl::__internal::__no_op());
-}
-
-template <class _ExecutionPolicy, class _ForwardIterator, class _Tp>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp>
-reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Tp __init) {
-  return transform_reduce(
-      std::forward<_ExecutionPolicy>(__exec), __first, __last, __init, std::plus<_Tp>(), __pstl::__internal::__no_op());
-}
-
-template <class _ExecutionPolicy, class _ForwardIterator>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy,
-                                                 typename iterator_traits<_ForwardIterator>::value_type>
-reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last) {
-  typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
-  return transform_reduce(
-      std::forward<_ExecutionPolicy>(__exec),
-      __first,
-      __last,
-      _ValueType{},
-      std::plus<_ValueType>(),
-      __pstl::__internal::__no_op());
-}
-
-// [transform.reduce]
-
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Tp>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp> transform_reduce(
-    _ExecutionPolicy&& __exec,
-    _ForwardIterator1 __first1,
-    _ForwardIterator1 __last1,
-    _ForwardIterator2 __first2,
-    _Tp __init) {
-  auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first1, __first2);
-
-  typedef typename iterator_traits<_ForwardIterator1>::value_type _InputType;
-  return __pstl::__internal::__pattern_transform_reduce(
-      __dispatch_tag,
-      std::forward<_ExecutionPolicy>(__exec),
-      __first1,
-      __last1,
-      __first2,
-      __init,
-      std::plus<_InputType>(),
-      std::multiplies<_InputType>());
-}
-
-template <class _ExecutionPolicy,
-          class _ForwardIterator1,
-          class _ForwardIterator2,
-          class _Tp,
-          class _BinaryOperation1,
-          class _BinaryOperation2>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp> transform_reduce(
-    _ExecutionPolicy&& __exec,
-    _ForwardIterator1 __first1,
-    _ForwardIterator1 __last1,
-    _ForwardIterator2 __first2,
-    _Tp __init,
-    _BinaryOperation1 __binary_op1,
-    _BinaryOperation2 __binary_op2) {
-  auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first1, __first2);
-  return __pstl::__internal::__pattern_transform_reduce(
-      __dispatch_tag,
-      std::forward<_ExecutionPolicy>(__exec),
-      __first1,
-      __last1,
-      __first2,
-      __init,
-      __binary_op1,
-      __binary_op2);
-}
-
-template <class _ExecutionPolicy, class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _Tp> transform_reduce(
-    _ExecutionPolicy&& __exec,
-    _ForwardIterator __first,
-    _ForwardIterator __last,
-    _Tp __init,
-    _BinaryOperation __binary_op,
-    _UnaryOperation __unary_op) {
-  auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first);
-  return __pstl::__internal::__pattern_transform_reduce(
-      __dispatch_tag, std::forward<_ExecutionPolicy>(__exec), __first, __last, __init, __binary_op, __unary_op);
-}
-
 // [exclusive.scan]
 
 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Tp>
 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> exclusive_scan(
     _ExecutionPolicy&& __exec,
     _ForwardIterator1 __first,
     _ForwardIterator1 __last,
     _ForwardIterator2 __result,

libcxx/include/__pstl/internal/numeric_fwd.h

 #include <__config>
 #include <type_traits>
 #include <utility>
 
 namespace __pstl {
 namespace __internal {
 
 //------------------------------------------------------------------------
-// transform_reduce (version with two binary functions, according to draft N4659)
-//------------------------------------------------------------------------
-
-template <class _RandomAccessIterator1,
-          class _RandomAccessIterator2,
-          class _Tp,
-          class _BinaryOperation1,
-          class _BinaryOperation2>
-_Tp __brick_transform_reduce(
-    _RandomAccessIterator1,
-    _RandomAccessIterator1,
-    _RandomAccessIterator2,
-    _Tp,
-    _BinaryOperation1,
-    _BinaryOperation2,
-    /*__is_vector=*/std::true_type) noexcept;
-
-template <class _ForwardIterator1, class _ForwardIterator2, class _Tp, class _BinaryOperation1, class _BinaryOperation2>
-_Tp __brick_transform_reduce(
-    _ForwardIterator1,
-    _ForwardIterator1,
-    _ForwardIterator2,
-    _Tp,
-    _BinaryOperation1,
-    _BinaryOperation2,
-    /*__is_vector=*/std::false_type) noexcept;
-
-template <class _Tag,
-          class _ExecutionPolicy,
-          class _ForwardIterator1,
-          class _ForwardIterator2,
-          class _Tp,
-          class _BinaryOperation1,
-          class _BinaryOperation2>
-_Tp __pattern_transform_reduce(
-    _Tag,
-    _ExecutionPolicy&&,
-    _ForwardIterator1,
-    _ForwardIterator1,
-    _ForwardIterator2,
-    _Tp,
-    _BinaryOperation1,
-    _BinaryOperation2) noexcept;
-
-template <class _IsVector,
-          class _ExecutionPolicy,
-          class _RandomAccessIterator1,
-          class _RandomAccessIterator2,
-          class _Tp,
-          class _BinaryOperation1,
-          class _BinaryOperation2>
-_Tp __pattern_transform_reduce(
-    __parallel_tag<_IsVector>,
-    _ExecutionPolicy&&,
-    _RandomAccessIterator1,
-    _RandomAccessIterator1,
-    _RandomAccessIterator2,
-    _Tp,
-    _BinaryOperation1,
-    _BinaryOperation2);
-
-//------------------------------------------------------------------------
-// transform_reduce (version with unary and binary functions)
-//------------------------------------------------------------------------
-
-template <class _RandomAccessIterator, class _Tp, class _UnaryOperation, class _BinaryOperation>
-_Tp __brick_transform_reduce(
-    _RandomAccessIterator,
-    _RandomAccessIterator,
-    _Tp,
-    _BinaryOperation,
-    _UnaryOperation,
-    /*is_vector=*/std::true_type) noexcept;
-
-template <class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation>
-_Tp __brick_transform_reduce(
-    _ForwardIterator,
-    _ForwardIterator,
-    _Tp,
-    _BinaryOperation,
-    _UnaryOperation,
-    /*is_vector=*/std::false_type) noexcept;
-
-template <class _Tag,
-          class _ExecutionPolicy,
-          class _ForwardIterator,
-          class _Tp,
-          class _BinaryOperation,
-          class _UnaryOperation>
-_Tp __pattern_transform_reduce(
-    _Tag, _ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, _Tp, _BinaryOperation, _UnaryOperation) noexcept;
-
-template <class _IsVector,
-          class _ExecutionPolicy,
-          class _RandomAccessIterator,
-          class _Tp,
-          class _BinaryOperation,
-          class _UnaryOperation>
-_Tp __pattern_transform_reduce(
-    __parallel_tag<_IsVector>,
-    _ExecutionPolicy&&,
-    _RandomAccessIterator,
-    _RandomAccessIterator,
-    _Tp,
-    _BinaryOperation,
-    _UnaryOperation);
-
-//------------------------------------------------------------------------
 // transform_exclusive_scan
 //
 // walk3 evaluates f(x,y,z) for (x,y,z) drawn from [first1,last1), [first2,...), [first3,...)
 //------------------------------------------------------------------------
 
 template <class _ForwardIterator, class _OutputIterator, class _UnaryOperation, class _Tp, class _BinaryOperation>
 std::pair<_OutputIterator, _Tp> __brick_transform_scan(
     _ForwardIterator,

libcxx/include/__pstl/internal/numeric_impl.h

 #include "execution_impl.h"
 #include "unseq_backend_simd.h"
 #include "algorithm_fwd.h"
 
 namespace __pstl {
 namespace __internal {
 
 //------------------------------------------------------------------------
-// transform_reduce (version with two binary functions, according to draft N4659)
-//------------------------------------------------------------------------
-
-template <class _ForwardIterator1, class _ForwardIterator2, class _Tp, class _BinaryOperation1, class _BinaryOperation2>
-_Tp __brick_transform_reduce(
-    _ForwardIterator1 __first1,
-    _ForwardIterator1 __last1,
-    _ForwardIterator2 __first2,
-    _Tp __init,
-    _BinaryOperation1 __binary_op1,
-    _BinaryOperation2 __binary_op2,
-    /*is_vector=*/std::false_type) noexcept {
-  return std::inner_product(__first1, __last1, __first2, __init, __binary_op1, __binary_op2);
-}
-
-template <class _RandomAccessIterator1,
-          class _RandomAccessIterator2,
-          class _Tp,
-          class _BinaryOperation1,
-          class _BinaryOperation2>
-_Tp __brick_transform_reduce(
-    _RandomAccessIterator1 __first1,
-    _RandomAccessIterator1 __last1,
-    _RandomAccessIterator2 __first2,
-    _Tp __init,
-    _BinaryOperation1 __binary_op1,
-    _BinaryOperation2 __binary_op2,
-    /*is_vector=*/std::true_type) noexcept {
-  typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType;
-  return __unseq_backend::__simd_transform_reduce(
-      __last1 - __first1, __init, __binary_op1, [=, &__binary_op2](_DifferenceType __i) {
-        return __binary_op2(__first1[__i], __first2[__i]);
-      });
-}
-
-template <class _Tag,
-          class _ExecutionPolicy,
-          class _ForwardIterator1,
-          class _ForwardIterator2,
-          class _Tp,
-          class _BinaryOperation1,
-          class _BinaryOperation2>
-_Tp __pattern_transform_reduce(
-    _Tag,
-    _ExecutionPolicy&&,
-    _ForwardIterator1 __first1,
-    _ForwardIterator1 __last1,
-    _ForwardIterator2 __first2,
-    _Tp __init,
-    _BinaryOperation1 __binary_op1,
-    _BinaryOperation2 __binary_op2) noexcept {
-  return __brick_transform_reduce(
-      __first1, __last1, __first2, __init, __binary_op1, __binary_op2, typename _Tag::__is_vector{});
-}
-
-template <class _IsVector,
-          class _ExecutionPolicy,
-          class _RandomAccessIterator1,
-          class _RandomAccessIterator2,
-          class _Tp,
-          class _BinaryOperation1,
-          class _BinaryOperation2>
-_Tp __pattern_transform_reduce(
-    __parallel_tag<_IsVector> __tag,
-    _ExecutionPolicy&& __exec,
-    _RandomAccessIterator1 __first1,
-    _RandomAccessIterator1 __last1,
-    _RandomAccessIterator2 __first2,
-    _Tp __init,
-    _BinaryOperation1 __binary_op1,
-    _BinaryOperation2 __binary_op2) {
-  using __backend_tag = typename decltype(__tag)::__backend_tag;
-
-  return __internal::__except_handler([&]() {
-    return __par_backend::__parallel_transform_reduce(
-        __backend_tag{},
-        std::forward<_ExecutionPolicy>(__exec),
-        __first1,
-        __last1,
-        [__first1, __first2, __binary_op2](_RandomAccessIterator1 __i) mutable {
-          return __binary_op2(*__i, *(__first2 + (__i - __first1)));
-        },
-        __init,
-        __binary_op1, // Combine
-        [__first1, __first2, __binary_op1, __binary_op2](
-            _RandomAccessIterator1 __i, _RandomAccessIterator1 __j, _Tp __init) -> _Tp {
-          return __internal::__brick_transform_reduce(
-              __i, __j, __first2 + (__i - __first1), __init, __binary_op1, __binary_op2, _IsVector{});
-        });
-  });
-}
-
-//------------------------------------------------------------------------
-// transform_reduce (version with unary and binary functions)
-//------------------------------------------------------------------------
-
-template <class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation>
-_Tp __brick_transform_reduce(
-    _ForwardIterator __first,
-    _ForwardIterator __last,
-    _Tp __init,
-    _BinaryOperation __binary_op,
-    _UnaryOperation __unary_op,
-    /*is_vector=*/std::false_type) noexcept {
-  return std::transform_reduce(__first, __last, __init, __binary_op, __unary_op);
-}
-
-template <class _RandomAccessIterator, class _Tp, class _UnaryOperation, class _BinaryOperation>
-_Tp __brick_transform_reduce(
-    _RandomAccessIterator __first,
-    _RandomAccessIterator __last,
-    _Tp __init,
-    _BinaryOperation __binary_op,
-    _UnaryOperation __unary_op,
-    /*is_vector=*/std::true_type) noexcept {
-  typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _DifferenceType;
-  return __unseq_backend::__simd_transform_reduce(
-      __last - __first, __init, __binary_op, [=, &__unary_op](_DifferenceType __i) {
-        return __unary_op(__first[__i]);
-      });
-}
-
-template <class _Tag,
-          class _ExecutionPolicy,
-          class _ForwardIterator,
-          class _Tp,
-          class _BinaryOperation,
-          class _UnaryOperation>
-_Tp __pattern_transform_reduce(
-    _Tag,
-    _ExecutionPolicy&&,
-    _ForwardIterator __first,
-    _ForwardIterator __last,
-    _Tp __init,
-    _BinaryOperation __binary_op,
-    _UnaryOperation __unary_op) noexcept {
-  return __internal::__brick_transform_reduce(
-      __first, __last, __init, __binary_op, __unary_op, typename _Tag::__is_vector{});
-}
-
-template <class _IsVector,
-          class _ExecutionPolicy,
-          class _RandomAccessIterator,
-          class _Tp,
-          class _BinaryOperation,
-          class _UnaryOperation>
-_Tp __pattern_transform_reduce(
-    __parallel_tag<_IsVector> __tag,
-    _ExecutionPolicy&& __exec,
-    _RandomAccessIterator __first,
-    _RandomAccessIterator __last,
-    _Tp __init,
-    _BinaryOperation __binary_op,
-    _UnaryOperation __unary_op) {
-  using __backend_tag = typename decltype(__tag)::__backend_tag;
-
-  return __internal::__except_handler([&]() {
-    return __par_backend::__parallel_transform_reduce(
-        __backend_tag{},
-        std::forward<_ExecutionPolicy>(__exec),
-        __first,
-        __last,
-        [__unary_op](_RandomAccessIterator __i) mutable { return __unary_op(*__i); },
-        __init,
-        __binary_op,
-        [__unary_op, __binary_op](_RandomAccessIterator __i, _RandomAccessIterator __j, _Tp __init) {
-          return __internal::__brick_transform_reduce(__i, __j, __init, __binary_op, __unary_op, _IsVector{});
-        });
-  });
-}
-
-//------------------------------------------------------------------------
 // transform_exclusive_scan
 //
 // walk3 evaluates f(x,y,z) for (x,y,z) drawn from [first1,last1), [first2,...), [first3,...)
 //------------------------------------------------------------------------
 
 // Exclusive form
 template <class _ForwardIterator, class _OutputIterator, class _UnaryOperation, class _Tp, class _BinaryOperation>
 std::pair<_OutputIterator, _Tp> __brick_transform_scan(

libcxx/include/__pstl/internal/parallel_backend_serial.h

if (__first == __last)
         return __identity;
     }
     else
     {
         return __real_body(__first, __last, __identity);
     }
 }
 
-template <class _ExecutionPolicy, class _Index, class _UnaryOp, class _Tp, class _BinaryOp, class _Reduce>
-_LIBCPP_HIDE_FROM_ABI _Tp
-__parallel_transform_reduce(__pstl::__internal::__serial_backend_tag, _ExecutionPolicy&&, _Index __first, _Index __last,
-                            _UnaryOp, _Tp __init, _BinaryOp, _Reduce __reduce)
-{
-    return __reduce(__first, __last, __init);
-}
-
 template <class _ExecutionPolicy, typename _Index, typename _Tp, typename _Rp, typename _Cp, typename _Sp, typename _Ap>
 _LIBCPP_HIDE_FROM_ABI void
 __parallel_strict_scan(__pstl::__internal::__serial_backend_tag, _ExecutionPolicy&&, _Index __n, _Tp __initial,
                        _Rp __reduce, _Cp __combine, _Sp __scan, _Ap __apex)
 {
     _Tp __sum = __initial;
     if (__n)
         __sum = __combine(__sum, __reduce(_Index(0), __n));

libcxx/include/__pstl/internal/unseq_backend_simd.h

__simd_adjacent_find(_Index __first, _Index __last, _BinaryPredicate __pred, bool __or_semantic) noexcept
     return __last;
 }
 
 // It was created to reduce the code inside std::enable_if
 template <typename _Tp, typename _BinaryOperation>
 using is_arithmetic_plus = std::integral_constant<bool, std::is_arithmetic<_Tp>::value &&
                                                             std::is_same<_BinaryOperation, std::plus<_Tp>>::value>;
 
-template <typename _DifferenceType, typename _Tp, typename _BinaryOperation, typename _UnaryOperation>
-_LIBCPP_HIDE_FROM_ABI typename std::enable_if<is_arithmetic_plus<_Tp, _BinaryOperation>::value, _Tp>::type
-__simd_transform_reduce(_DifferenceType __n, _Tp __init, _BinaryOperation, _UnaryOperation __f) noexcept
-{
-    _PSTL_PRAGMA_SIMD_REDUCTION(+ : __init)
-    for (_DifferenceType __i = 0; __i < __n; ++__i)
-        __init += __f(__i);
-    return __init;
-}
-
-template <typename _Size, typename _Tp, typename _BinaryOperation, typename _UnaryOperation>
-_LIBCPP_HIDE_FROM_ABI typename std::enable_if<!is_arithmetic_plus<_Tp, _BinaryOperation>::value, _Tp>::type
-__simd_transform_reduce(_Size __n, _Tp __init, _BinaryOperation __binary_op, _UnaryOperation __f) noexcept
-{
-    const _Size __block_size = __lane_size / sizeof(_Tp);
-    if (__n > 2 * __block_size && __block_size > 1)
-    {
-        alignas(__lane_size) char __lane_buffer[__lane_size];
-        _Tp* __lane = reinterpret_cast<_Tp*>(__lane_buffer);
-
-        // initializer
-        _PSTL_PRAGMA_SIMD
-        for (_Size __i = 0; __i < __block_size; ++__i)
-        {
-            ::new (__lane + __i) _Tp(__binary_op(__f(__i), __f(__block_size + __i)));
-        }
-        // main loop
-        _Size __i = 2 * __block_size;
-        const _Size __last_iteration = __block_size * (__n / __block_size);
-        for (; __i < __last_iteration; __i += __block_size)
-        {
-            _PSTL_PRAGMA_SIMD
-            for (_Size __j = 0; __j < __block_size; ++__j)
-            {
-                __lane[__j] = __binary_op(__lane[__j], __f(__i + __j));
-            }
-        }
-        // remainder
-        _PSTL_PRAGMA_SIMD
-        for (_Size __j = 0; __j < __n - __last_iteration; ++__j)
-        {
-            __lane[__j] = __binary_op(__lane[__j], __f(__last_iteration + __j));
-        }
-        // combiner
-        for (_Size __j = 0; __j < __block_size; ++__j)
-        {
-            __init = __binary_op(__init, __lane[__j]);
-        }
-        // destroyer
-        _PSTL_PRAGMA_SIMD
-        for (_Size __j = 0; __j < __block_size; ++__j)
-        {
-            __lane[__j].~_Tp();
-        }
-    }
-    else
-    {
-        for (_Size __i = 0; __i < __n; ++__i)
-        {
-            __init = __binary_op(__init, __f(__i));
-        }
-    }
-    return __init;
-}
-
 // Exclusive scan for "+" and arithmetic types
 template <class _InputIterator, class _Size, class _OutputIterator, class _UnaryOperation, class _Tp,
           class _BinaryOperation>
 _LIBCPP_HIDE_FROM_ABI
 typename std::enable_if<is_arithmetic_plus<_Tp, _BinaryOperation>::value, std::pair<_OutputIterator, _Tp>>::type
 __simd_scan(_InputIterator __first, _Size __n, _OutputIterator __result, _UnaryOperation __unary_op, _Tp __init,
             _BinaryOperation, /*Inclusive*/ std::false_type)
 {

libcxx/include/__type_traits/operation_traits.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
+#ifndef _LIBCPP___TYPE_TRAITS_OPERATION_TRAITS_H
+#define _LIBCPP___TYPE_TRAITS_OPERATION_TRAITS_H
 
 #include <__config>
-
-#if defined(_LIBCPP_PSTL_CPU_BACKEND_SERIAL)
-#  include <__algorithm/pstl_backends/cpu_backends/serial.h>
-#elif defined(_LIBCPP_PSTL_CPU_BACKEND_THREAD)
-#  include <__algorithm/pstl_backends/cpu_backends/thread.h>
-#else
-#  error "Invalid CPU backend choice"
-#endif
+#include <__type_traits/integral_constant.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-struct __cpu_backend_tag {};
+template <class _Pred, class _Lhs, class _Rhs>
+struct __is_trivial_plus_operation : false_type {};
 
 _LIBCPP_END_NAMESPACE_STD
 
-#endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_BACKEND_H
+#endif // _LIBCPP___TYPE_TRAITS_OPERATION_TRAITS_H

libcxx/include/module.modulemap.in

module __algorithm {
         private header "__algorithm/pstl_backends/cpu_backends/serial.h"
       }
       module pstl_backends_cpu_backends_thread {
         private header "__algorithm/pstl_backends/cpu_backends/thread.h"
       }
       module pstl_backends_cpu_backends_transform {
         private header "__algorithm/pstl_backends/cpu_backends/transform.h"
       }
+      module pstl_backends_cpu_backends_transform_reduce {
+        private header "__algorithm/pstl_backends/cpu_backends/transform_reduce.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
       }
module type_traits {
     module make_32_64_or_128_bit                     { private header "__type_traits/make_32_64_or_128_bit.h" }
     module make_const_lvalue_ref                     { private header "__type_traits/make_const_lvalue_ref.h" }
     module make_signed                               { private header "__type_traits/make_signed.h" }
     module make_unsigned                             { private header "__type_traits/make_unsigned.h" }
     module maybe_const                               { private header "__type_traits/maybe_const.h" }
     module nat                                       { private header "__type_traits/nat.h" }
     module negation                                  { private header "__type_traits/negation.h" }
     module noexcept_move_assign_container            { private header "__type_traits/noexcept_move_assign_container.h" }
+    module operation_traits                          { private header "__type_traits/operation_traits.h" }
     module predicate_traits                          { private header "__type_traits/predicate_traits.h" }
     module promote                                   { private header "__type_traits/promote.h" }
     module rank                                      { private header "__type_traits/rank.h" }
     module remove_all_extents                        { private header "__type_traits/remove_all_extents.h" }
     module remove_const                              { private header "__type_traits/remove_const.h" }
     module remove_const_ref                          { private header "__type_traits/remove_const_ref.h" }
     module remove_cv                                 { private header "__type_traits/remove_cv.h" }
     module remove_cvref                              { private header "__type_traits/remove_cvref.h" }

libcxx/include/numeric

 #include <__numeric/adjacent_difference.h>
 #include <__numeric/exclusive_scan.h>
 #include <__numeric/gcd_lcm.h>
 #include <__numeric/inclusive_scan.h>
 #include <__numeric/inner_product.h>
 #include <__numeric/iota.h>
 #include <__numeric/midpoint.h>
 #include <__numeric/partial_sum.h>
+#include <__numeric/pstl_reduce.h>
+#include <__numeric/pstl_transform_reduce.h>
 #include <__numeric/reduce.h>
 #include <__numeric/transform_exclusive_scan.h>
 #include <__numeric/transform_inclusive_scan.h>
 #include <__numeric/transform_reduce.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif

libcxx/test/libcxx/algorithms/pstl.robust_against_customization_points_not_working.pass.cpp

 // UNSUPPORTED: libcpp-has-no-incomplete-pstl
 
 // Having a customization point outside the module doesn't work, so this test is inherintly module-hostile.
 // UNSUPPORTED: modules-build
 
 // Make sure that the customization points get called properly when overloaded
 
 #include <__config>
+#include <__iterator/iterator_traits.h>
+#include <__iterator/readable_traits.h>
 #include <cassert>
 
 struct TestPolicy {};
 struct TestBackend {};
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 bool pstl_any_of_called = false;

 template <class, class ForwardIterator1, class ForwardIterator2, class ForwardOutIterator, class BinaryOperation>
 ForwardOutIterator __pstl_transform(
     TestBackend, ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardOutIterator, BinaryOperation) {
   assert(!pstl_binary_transform_called);
   pstl_binary_transform_called = true;
   return {};
 }
 
+bool pstl_reduce_with_init_called = false;
+
+template <class, class ForwardIterator, class T, class BinaryOperation>
+T __pstl_reduce(TestBackend, ForwardIterator, ForwardIterator, T, BinaryOperation) {
+  assert(!pstl_reduce_with_init_called);
+  pstl_reduce_with_init_called = true;
+  return {};
+}
+
+bool pstl_reduce_without_init_called = false;
+
+template <class, class ForwardIterator>
+typename std::iterator_traits<ForwardIterator>::value_type
+__pstl_reduce(TestBackend, ForwardIterator, ForwardIterator) {
+  assert(!pstl_reduce_without_init_called);
+  pstl_reduce_without_init_called = true;
+  return {};
+}
+
+bool pstl_unary_transform_reduce_called = false;
+
+template <class, class ForwardIterator, class T, class UnaryOperation, class BinaryOperation>
+T __pstl_transform_reduce(TestBackend, ForwardIterator, ForwardIterator, T, UnaryOperation, BinaryOperation) {
+  assert(!pstl_unary_transform_reduce_called);
+  pstl_unary_transform_reduce_called = true;
+  return {};
+}
+
+bool pstl_binary_transform_reduce_called = false;
+
+template <class,
+          class ForwardIterator1,
+          class ForwardIterator2,
+          class T,
+          class BinaryOperation1,
+          class BinaryOperation2>
+typename std::iterator_traits<ForwardIterator1>::value_type __pstl_transform_reduce(
+    TestBackend, ForwardIterator1, ForwardIterator1, ForwardIterator2, T, BinaryOperation1, BinaryOperation2) {
+  assert(!pstl_binary_transform_reduce_called);
+  pstl_binary_transform_reduce_called = true;
+  return {};
+}
+
 _LIBCPP_END_NAMESPACE_STD
 
 #include <algorithm>
 #include <cassert>
 #include <iterator>
+#include <numeric>
 
 template <>
 inline constexpr bool std::is_execution_policy_v<TestPolicy> = true;
 
 template <>
 struct std::__select_backend<TestPolicy> {
   using type = TestBackend;
 };
int main(int, char**) {
   (void)std::for_each(TestPolicy{}, std::begin(a), std::end(a), pred);
   assert(std::pstl_for_each_called);
   (void)std::for_each_n(TestPolicy{}, std::begin(a), std::size(a), pred);
   assert(std::pstl_for_each_n_called);
   (void)std::transform(TestPolicy{}, std::begin(a), std::end(a), std::begin(a), pred);
   assert(std::pstl_unary_transform_called);
   (void)std::transform(TestPolicy{}, std::begin(a), std::end(a), std::begin(a), std::begin(a), pred);
   assert(std::pstl_unary_transform_called);
+  (void)std::reduce(TestPolicy{}, std::begin(a), std::end(a), 0, pred);
+  assert(std::pstl_reduce_with_init_called);
+  (void)std::reduce(TestPolicy{}, std::begin(a), std::end(a));
+  assert(std::pstl_reduce_without_init_called);
+  (void)std::transform_reduce(TestPolicy{}, std::begin(a), std::end(a), 0, pred, pred);
+  assert(std::pstl_unary_transform_reduce_called);
+  (void)std::transform_reduce(TestPolicy{}, std::begin(a), std::end(a), std::begin(a), 0, pred, pred);
+  assert(std::pstl_binary_transform_reduce_called);
 
   return 0;
 }

libcxx/test/libcxx/private_headers.verify.cpp

 #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/fill.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/fill.h'}}
 #include <__algorithm/pstl_backends/cpu_backends/find_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/find_if.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/merge.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/merge.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/pstl_backends/cpu_backends/thread.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/thread.h'}}
 #include <__algorithm/pstl_backends/cpu_backends/transform.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/transform.h'}}
+#include <__algorithm/pstl_backends/cpu_backends/transform_reduce.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/transform_reduce.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'}}

 #include <__type_traits/make_32_64_or_128_bit.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/make_32_64_or_128_bit.h'}}
 #include <__type_traits/make_const_lvalue_ref.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/make_const_lvalue_ref.h'}}
 #include <__type_traits/make_signed.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/make_signed.h'}}
 #include <__type_traits/make_unsigned.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/make_unsigned.h'}}
 #include <__type_traits/maybe_const.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/maybe_const.h'}}
 #include <__type_traits/nat.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/nat.h'}}
 #include <__type_traits/negation.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/negation.h'}}
 #include <__type_traits/noexcept_move_assign_container.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/noexcept_move_assign_container.h'}}
+#include <__type_traits/operation_traits.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/operation_traits.h'}}
 #include <__type_traits/predicate_traits.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/predicate_traits.h'}}
 #include <__type_traits/promote.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/promote.h'}}
 #include <__type_traits/rank.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/rank.h'}}
 #include <__type_traits/remove_all_extents.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/remove_all_extents.h'}}
 #include <__type_traits/remove_const.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/remove_const.h'}}
 #include <__type_traits/remove_const_ref.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/remove_const_ref.h'}}
 #include <__type_traits/remove_cv.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/remove_cv.h'}}
 #include <__type_traits/remove_cvref.h> // expected-error@*:* {{use of private header from outside its module: '__type_traits/remove_cvref.h'}}

libcxx/test/libcxx/transitive_includes/cxx03.csv

 new type_traits
 new version
 numbers concepts
 numbers type_traits
 numbers version
 numeric cmath
 numeric concepts
 numeric cstddef
+numeric cstdint
+numeric cstring
+numeric ctime
+numeric execution
 numeric functional
+numeric initializer_list
+numeric iosfwd
 numeric iterator
 numeric limits
+numeric new
+numeric ratio
 numeric type_traits
 numeric version
 optional atomic
 optional climits
 optional compare
 optional concepts
 optional cstddef
 optional cstdint

libcxx/test/libcxx/transitive_includes/cxx11.csv

 new type_traits
 new version
 numbers concepts
 numbers type_traits
 numbers version
 numeric cmath
 numeric concepts
 numeric cstddef
+numeric cstdint
+numeric cstring
+numeric ctime
+numeric execution
 numeric functional
+numeric initializer_list
+numeric iosfwd
 numeric iterator
 numeric limits
+numeric new
+numeric ratio
 numeric type_traits
 numeric version
 optional atomic
 optional climits
 optional compare
 optional concepts
 optional cstddef
 optional cstdint

libcxx/test/libcxx/transitive_includes/cxx14.csv

 new type_traits
 new version
 numbers concepts
 numbers type_traits
 numbers version
 numeric cmath
 numeric concepts
 numeric cstddef
+numeric cstdint
+numeric cstring
+numeric ctime
+numeric execution
 numeric functional
+numeric initializer_list
+numeric iosfwd
 numeric iterator
 numeric limits
+numeric new
+numeric ratio
 numeric type_traits
 numeric version
 optional atomic
 optional climits
 optional compare
 optional concepts
 optional cstddef
 optional cstdint

libcxx/test/libcxx/transitive_includes/cxx17.csv

 new type_traits
 new version
 numbers concepts
 numbers type_traits
 numbers version
 numeric cmath
 numeric concepts
 numeric cstddef
+numeric cstdint
+numeric cstring
+numeric ctime
+numeric execution
 numeric functional
+numeric initializer_list
+numeric iosfwd
 numeric iterator
 numeric limits
+numeric new
+numeric ratio
 numeric type_traits
 numeric version
 optional atomic
 optional climits
 optional compare
 optional concepts
 optional cstddef
 optional cstdint

libcxx/test/libcxx/transitive_includes/cxx20.csv

 new type_traits
 new version
 numbers concepts
 numbers type_traits
 numbers version
 numeric cmath
 numeric concepts
 numeric cstddef
+numeric cstdint
+numeric cstring
+numeric ctime
+numeric execution
 numeric functional
+numeric initializer_list
+numeric iosfwd
 numeric iterator
 numeric limits
+numeric new
+numeric ratio
 numeric type_traits
 numeric version
 optional atomic
 optional climits
 optional compare
 optional concepts
 optional cstddef
 optional cstdint

libcxx/test/libcxx/transitive_includes/cxx23.csv

 mutex typeinfo
 mutex version
 new cstddef
 new cstdlib
 new version
 numbers version
 numeric cmath
 numeric cstddef
+numeric cstdint
+numeric cstring
+numeric ctime
+numeric execution
+numeric initializer_list
+numeric iosfwd
 numeric limits
+numeric new
+numeric ratio
 numeric version
 optional compare
 optional cstddef
 optional cstdint
 optional cstring
 optional initializer_list
 optional limits
 optional new

libcxx/test/libcxx/transitive_includes/cxx26.csv

 mutex typeinfo
 mutex version
 new cstddef
 new cstdlib
 new version
 numbers version
 numeric cmath
 numeric cstddef
+numeric cstdint
+numeric cstring
+numeric ctime
+numeric execution
+numeric initializer_list
+numeric iosfwd
 numeric limits
+numeric new
+numeric ratio
 numeric version
 optional compare
 optional cstddef
 optional cstdint
 optional cstring
 optional initializer_list
 optional limits
 optional new

libcxx/test/std/algorithms/numeric.ops/reduce/pstl.reduce.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// <algorithm>
+
+// template<class ExecutionPolicy, class ForwardIterator>
+//   typename iterator_traits<ForwardIterator>::value_type
+//     reduce(ExecutionPolicy&& exec,
+//            ForwardIterator first, ForwardIterator last);
+// template<class ExecutionPolicy, class ForwardIterator, class T, class BinaryOperation>
+//   T reduce(ExecutionPolicy&& exec,
+//            ForwardIterator first, ForwardIterator last, T init,
+//            BinaryOperation binary_op);
+
+#include <numeric>
+#include <vector>
+
+#include "MoveOnly.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+#include "test_macros.h"
+
+template <class Iter, class ValueT>
+struct Test {
+  template <class Policy>
+  void operator()(Policy&& policy) {
+    for (const auto& pair : {std::pair{0, 34}, {1, 36}, {2, 39}, {100, 5184}, {350, 61809}}) {
+      auto [size, expected] = pair;
+      std::vector<int> a(size);
+      for (int i = 0; i != size; ++i)
+        a[i] = i;
+
+      {
+        decltype(auto) ret = std::reduce(
+            policy, Iter(std::data(a)), Iter(std::data(a) + std::size(a)), ValueT(34), [](ValueT i, ValueT j) {
+              return i + j + 2;
+            });
+        static_assert(std::is_same_v<decltype(ret), ValueT>);
+        assert(ret == ValueT(expected));
+      }
+      {
+        decltype(auto) ret = std::reduce(policy, Iter(std::data(a)), Iter(std::data(a) + std::size(a)), ValueT(34));
+        static_assert(std::is_same_v<decltype(ret), ValueT>);
+        assert(ret == expected - 2 * size);
+      }
+      {
+        decltype(auto) ret = std::reduce(policy, Iter(std::data(a)), Iter(std::data(a) + std::size(a)));
+        static_assert(std::is_same_v<decltype(ret), typename std::iterator_traits<Iter>::value_type>);
+        assert(ret == expected - 2 * size - 34);
+      }
+    }
+  }
+};
+
+int main(int, char**) {
+  types::for_each(types::forward_iterator_list<int*>{}, types::apply_type_identity{[](auto v) {
+                    using Iter = typename decltype(v)::type;
+                    types::for_each(
+                        types::type_list<int, MoveOnly>{},
+                        TestIteratorWithPolicies<types::partial_instantiation<Test, Iter>::template apply>{});
+                  }});
+
+  return 0;
+}

libcxx/test/std/algorithms/numeric.ops/transform.reduce/pstl.transform_reduce.binary.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// <algorithm>
+
+// template<class ExecutionPolicy,
+//          class ForwardIterator1, class ForwardIterator2, class T>
+//   T transform_reduce(ExecutionPolicy&& exec,
+//                      ForwardIterator1 first1, ForwardIterator1 last1,
+//                      ForwardIterator2 first2,
+//                      T init);
+//
+// template<class ExecutionPolicy,
+//          class ForwardIterator1, class ForwardIterator2, class T,
+//          class BinaryOperation1, class BinaryOperation2>
+//   T transform_reduce(ExecutionPolicy&& exec,
+//                      ForwardIterator1 first1, ForwardIterator1 last1,
+//                      ForwardIterator2 first2,
+//                      T init,
+//                      BinaryOperation1 binary_op1,
+//                      BinaryOperation2 binary_op2);
+
+#include <numeric>
+#include <vector>
+
+#include "MoveOnly.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+#include "test_macros.h"
+#include "type_algorithms.h"
+
+template <class Iter1, class Iter2, class ValueT>
+struct Test {
+  template <class Policy>
+  void operator()(Policy&& policy) {
+    for (const auto& pair : {std::pair{0, 34}, {1, 33}, {2, 30}, {100, 313434}, {350, 14046934}}) {
+      auto [size, expected] = pair;
+      std::vector<int> a(size);
+      std::vector<int> b(size);
+      for (int i = 0; i != size; ++i) {
+        a[i] = i + 1;
+        b[i] = i - 4;
+      }
+
+      decltype(auto) ret = std::transform_reduce(
+          policy,
+          Iter1(std::data(a)),
+          Iter1(std::data(a) + std::size(a)),
+          Iter2(std::data(b)),
+          ValueT(34),
+          [](ValueT i, ValueT j) { return i + j + 3; },
+          [](ValueT i, ValueT j) { return i * j; });
+      static_assert(std::is_same_v<decltype(ret), ValueT>);
+      assert(ret == expected);
+    }
+
+    for (const auto& pair : {std::pair{0, 34}, {1, 30}, {2, 24}, {100, 313134}, {350, 14045884}}) {
+      auto [size, expected] = pair;
+      std::vector<int> a(size);
+      std::vector<int> b(size);
+      for (int i = 0; i != size; ++i) {
+        a[i] = i + 1;
+        b[i] = i - 4;
+      }
+
+      decltype(auto) ret = std::transform_reduce(
+          policy, Iter1(std::data(a)), Iter1(std::data(a) + std::size(a)), Iter2(std::data(b)), 34);
+      static_assert(std::is_same_v<decltype(ret), int>);
+      assert(ret == expected);
+    }
+  }
+};
+
+int main(int, char**) {
+  types::for_each(
+      types::forward_iterator_list<int*>{}, types::apply_type_identity{[](auto v) {
+        using Iter2 = typename decltype(v)::type;
+        types::for_each(
+            types::forward_iterator_list<int*>{}, types::apply_type_identity{[](auto v2) {
+              using Iter1 = typename decltype(v2)::type;
+              types::for_each(
+                  types::type_list<int, MoveOnly>{},
+                  TestIteratorWithPolicies<types::partial_instantiation<Test, Iter1, Iter2>::template apply>{});
+            }});
+      }});
+
+  return 0;
+}

libcxx/test/std/algorithms/numeric.ops/transform.reduce/pstl.transform_reduce.unary.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// <algorithm>
+
+// template<class ExecutionPolicy,
+//          class ForwardIterator, class T,
+//          class BinaryOperation, class UnaryOperation>
+//   T transform_reduce(ExecutionPolicy&& exec,
+//                      ForwardIterator first, ForwardIterator last,
+//                      T init, BinaryOperation binary_op, UnaryOperation unary_op);
+
+#include <numeric>
+#include <vector>
+
+#include "MoveOnly.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+#include "test_macros.h"
+
+template <class Iter1, class ValueT>
+struct Test {
+  template <class Policy>
+  void operator()(Policy&& policy) {
+    for (const auto& pair : {std::pair{0, 34}, {1, 35}, {2, 37}, {100, 5084}, {350, 61459}}) {
+      auto [size, expected] = pair;
+      std::vector<int> a(size);
+      for (int i = 0; i != size; ++i)
+        a[i] = i;
+
+      decltype(auto) ret = std::transform_reduce(
+          policy,
+          Iter1(std::data(a)),
+          Iter1(std::data(a) + std::size(a)),
+          ValueT(34),
+          [](ValueT i, ValueT j) { return i + j; },
+          [](ValueT i) { return i + 1; });
+      static_assert(std::is_same_v<decltype(ret), ValueT>);
+      assert(ret == expected);
+    }
+  }
+};
+
+int main(int, char**) {
+  types::for_each(types::forward_iterator_list<int*>{}, types::apply_type_identity{[](auto v) {
+                    using Iter2 = typename decltype(v)::type;
+                    types::for_each(
+                        types::type_list<int, MoveOnly>{},
+                        TestIteratorWithPolicies<types::partial_instantiation<Test, Iter2>::template apply>{});
+                  }});
+
+  return 0;
+}