1 files changed, 364 insertions, 0 deletions
diff --git a/contrib/llvm-project/libcxx/include/__pstl/internal/numeric_impl.h b/contrib/llvm-project/libcxx/include/__pstl/internal/numeric_impl.h
new file mode 100644
index 000000000000..484f26ade22c
--- /dev/null
+++ b/contrib/llvm-project/libcxx/include/__pstl/internal/numeric_impl.h
@@ -0,0 +1,364 @@
+// -*- 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 _PSTL_NUMERIC_IMPL_H
+#define _PSTL_NUMERIC_IMPL_H
+
+#include <__assert>
+#include <__config>
+#include <iterator>
+#include <type_traits>
+#include <numeric>
+
+#include "parallel_backend.h"
+#include "execution_impl.h"
+#include "unseq_backend_simd.h"
+#include "algorithm_fwd.h"
+
+namespace __pstl {
+namespace __internal {
+
+//------------------------------------------------------------------------
+// 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(
+    _ForwardIterator __first,
+    _ForwardIterator __last,
+    _OutputIterator __result,
+    _UnaryOperation __unary_op,
+    _Tp __init,
+    _BinaryOperation __binary_op,
+    /*Inclusive*/ std::false_type,
+    /*is_vector=*/std::false_type) noexcept {
+  for (; __first != __last; ++__first, ++__result) {
+    *__result = __init;
+    __init = __binary_op(__init, __unary_op(*__first));
+  }
+  return std::make_pair(__result, __init);
+}
+
+// Inclusive form
+template <class _RandomAccessIterator, class _OutputIterator, class _UnaryOperation, class _Tp, class _BinaryOperation>
+std::pair<_OutputIterator, _Tp> __brick_transform_scan(
+    _RandomAccessIterator __first,
+    _RandomAccessIterator __last,
+    _OutputIterator __result,
+    _UnaryOperation __unary_op,
+    _Tp __init,
+    _BinaryOperation __binary_op,
+    /*Inclusive*/ std::true_type,
+    /*is_vector=*/std::false_type) noexcept {
+  for (; __first != __last; ++__first, ++__result) {
+    __init    = __binary_op(__init, __unary_op(*__first));
+    *__result = __init;
+  }
+  return std::make_pair(__result, __init);
+}
+
+// type is arithmetic and binary operation is a user defined operation.
+template <typename _Tp, typename _BinaryOperation>
+using is_arithmetic_udop =
+    std::integral_constant<bool,
+                           std::is_arithmetic<_Tp>::value && !std::is_same<_BinaryOperation, std::plus<_Tp>>::value>;
+
+// [restriction] - T shall be DefaultConstructible.
+// [violation] - default ctor of T shall set the identity value for binary_op.
+template <class _RandomAccessIterator,
+          class _OutputIterator,
+          class _UnaryOperation,
+          class _Tp,
+          class _BinaryOperation,
+          class _Inclusive>
+typename std::enable_if<!is_arithmetic_udop<_Tp, _BinaryOperation>::value, std::pair<_OutputIterator, _Tp>>::type
+__brick_transform_scan(
+    _RandomAccessIterator __first,
+    _RandomAccessIterator __last,
+    _OutputIterator __result,
+    _UnaryOperation __unary_op,
+    _Tp __init,
+    _BinaryOperation __binary_op,
+    _Inclusive,
+    /*is_vector=*/std::true_type) noexcept {
+#if defined(_PSTL_UDS_PRESENT)
+  return __unseq_backend::__simd_scan(
+      __first, __last - __first, __result, __unary_op, __init, __binary_op, _Inclusive());
+#else
+  // We need to call serial brick here to call function for inclusive and exclusive scan that depends on _Inclusive()
+  // value
+  return __internal::__brick_transform_scan(
+      __first,
+      __last,
+      __result,
+      __unary_op,
+      __init,
+      __binary_op,
+      _Inclusive(),
+      /*is_vector=*/std::false_type());
+#endif
+}
+
+template <class _RandomAccessIterator,
+          class _OutputIterator,
+          class _UnaryOperation,
+          class _Tp,
+          class _BinaryOperation,
+          class _Inclusive>
+typename std::enable_if<is_arithmetic_udop<_Tp, _BinaryOperation>::value, std::pair<_OutputIterator, _Tp>>::type
+__brick_transform_scan(
+    _RandomAccessIterator __first,
+    _RandomAccessIterator __last,
+    _OutputIterator __result,
+    _UnaryOperation __unary_op,
+    _Tp __init,
+    _BinaryOperation __binary_op,
+    _Inclusive,
+    /*is_vector=*/std::true_type) noexcept {
+  return __internal::__brick_transform_scan(
+      __first,
+      __last,
+      __result,
+      __unary_op,
+      __init,
+      __binary_op,
+      _Inclusive(),
+      /*is_vector=*/std::false_type());
+}
+
+template <class _Tag,
+          class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _OutputIterator,
+          class _UnaryOperation,
+          class _Tp,
+          class _BinaryOperation,
+          class _Inclusive>
+_OutputIterator __pattern_transform_scan(
+    _Tag,
+    _ExecutionPolicy&&,
+    _ForwardIterator __first,
+    _ForwardIterator __last,
+    _OutputIterator __result,
+    _UnaryOperation __unary_op,
+    _Tp __init,
+    _BinaryOperation __binary_op,
+    _Inclusive) noexcept {
+  return __internal::__brick_transform_scan(
+             __first, __last, __result, __unary_op, __init, __binary_op, _Inclusive(), typename _Tag::__is_vector{})
+      .first;
+}
+
+template <class _IsVector,
+          class _ExecutionPolicy,
+          class _RandomAccessIterator,
+          class _OutputIterator,
+          class _UnaryOperation,
+          class _Tp,
+          class _BinaryOperation,
+          class _Inclusive>
+typename std::enable_if<!std::is_floating_point<_Tp>::value, _OutputIterator>::type __pattern_transform_scan(
+    __parallel_tag<_IsVector> __tag,
+    _ExecutionPolicy&& __exec,
+    _RandomAccessIterator __first,
+    _RandomAccessIterator __last,
+    _OutputIterator __result,
+    _UnaryOperation __unary_op,
+    _Tp __init,
+    _BinaryOperation __binary_op,
+    _Inclusive) {
+  using __backend_tag = typename decltype(__tag)::__backend_tag;
+
+  typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _DifferenceType;
+
+  return __internal::__except_handler([&]() {
+    __par_backend::__parallel_transform_scan(
+        __backend_tag{},
+        std::forward<_ExecutionPolicy>(__exec),
+        __last - __first,
+        [__first, __unary_op](_DifferenceType __i) mutable { return __unary_op(__first[__i]); },
+        __init,
+        __binary_op,
+        [__first, __unary_op, __binary_op](_DifferenceType __i, _DifferenceType __j, _Tp __init) {
+          // Execute serial __brick_transform_reduce, due to the explicit SIMD vectorization (reduction) requires a
+          // commutative operation for the guarantee of correct scan.
+          return __internal::__brick_transform_reduce(
+              __first + __i,
+              __first + __j,
+              __init,
+              __binary_op,
+              __unary_op,
+              /*__is_vector*/ std::false_type());
+        },
+        [__first, __unary_op, __binary_op, __result](_DifferenceType __i, _DifferenceType __j, _Tp __init) {
+          return __internal::__brick_transform_scan(
+                     __first + __i,
+                     __first + __j,
+                     __result + __i,
+                     __unary_op,
+                     __init,
+                     __binary_op,
+                     _Inclusive(),
+                     _IsVector{})
+              .second;
+        });
+    return __result + (__last - __first);
+  });
+}
+
+template <class _IsVector,
+          class _ExecutionPolicy,
+          class _RandomAccessIterator,
+          class _OutputIterator,
+          class _UnaryOperation,
+          class _Tp,
+          class _BinaryOperation,
+          class _Inclusive>
+typename std::enable_if<std::is_floating_point<_Tp>::value, _OutputIterator>::type __pattern_transform_scan(
+    __parallel_tag<_IsVector> __tag,
+    _ExecutionPolicy&& __exec,
+    _RandomAccessIterator __first,
+    _RandomAccessIterator __last,
+    _OutputIterator __result,
+    _UnaryOperation __unary_op,
+    _Tp __init,
+    _BinaryOperation __binary_op,
+    _Inclusive) {
+  using __backend_tag = typename decltype(__tag)::__backend_tag;
+
+  typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _DifferenceType;
+  _DifferenceType __n = __last - __first;
+
+  if (__n <= 0) {
+    return __result;
+  }
+  return __internal::__except_handler([&]() {
+    __par_backend::__parallel_strict_scan(
+        __backend_tag{},
+        std::forward<_ExecutionPolicy>(__exec),
+        __n,
+        __init,
+        [__first, __unary_op, __binary_op, __result](_DifferenceType __i, _DifferenceType __len) {
+          return __internal::__brick_transform_scan(
+                     __first + __i,
+                     __first + (__i + __len),
+                     __result + __i,
+                     __unary_op,
+                     _Tp{},
+                     __binary_op,
+                     _Inclusive(),
+                     _IsVector{})
+              .second;
+        },
+        __binary_op,
+        [__result, &__binary_op](_DifferenceType __i, _DifferenceType __len, _Tp __initial) {
+          return *(std::transform(__result + __i,
+                                  __result + __i + __len,
+                                  __result + __i,
+                                  [&__initial, &__binary_op](const _Tp& __x) {
+                                    return __binary_op(__initial, __x);
+                                  }) -
+                   1);
+        },
+        [](_Tp) {});
+    return __result + (__last - __first);
+  });
+}
+
+//------------------------------------------------------------------------
+// adjacent_difference
+//------------------------------------------------------------------------
+
+template <class _ForwardIterator, class _OutputIterator, class _BinaryOperation>
+_OutputIterator __brick_adjacent_difference(
+    _ForwardIterator __first,
+    _ForwardIterator __last,
+    _OutputIterator __d_first,
+    _BinaryOperation __op,
+    /*is_vector*/ std::false_type) noexcept {
+  return std::adjacent_difference(__first, __last, __d_first, __op);
+}
+
+template <class _RandomAccessIterator1, class _RandomAccessIterator2, class BinaryOperation>
+_RandomAccessIterator2 __brick_adjacent_difference(
+    _RandomAccessIterator1 __first,
+    _RandomAccessIterator1 __last,
+    _RandomAccessIterator2 __d_first,
+    BinaryOperation __op,
+    /*is_vector=*/std::true_type) noexcept {
+  _LIBCPP_ASSERT_UNCATEGORIZED(__first != __last, "Range cannot be empty");
+
+  typedef typename std::iterator_traits<_RandomAccessIterator1>::reference _ReferenceType1;
+  typedef typename std::iterator_traits<_RandomAccessIterator2>::reference _ReferenceType2;
+
+  auto __n   = __last - __first;
+  *__d_first = *__first;
+  return __unseq_backend::__simd_walk_3(
+      __first + 1,
+      __n - 1,
+      __first,
+      __d_first + 1,
+      [&__op](_ReferenceType1 __x, _ReferenceType1 __y, _ReferenceType2 __z) { __z = __op(__x, __y); });
+}
+
+template <class _Tag, class _ExecutionPolicy, class _ForwardIterator, class _OutputIterator, class _BinaryOperation>
+_OutputIterator __pattern_adjacent_difference(
+    _Tag,
+    _ExecutionPolicy&&,
+    _ForwardIterator __first,
+    _ForwardIterator __last,
+    _OutputIterator __d_first,
+    _BinaryOperation __op) noexcept {
+  return __internal::__brick_adjacent_difference(__first, __last, __d_first, __op, typename _Tag::__is_vector{});
+}
+
+template <class _IsVector,
+          class _ExecutionPolicy,
+          class _RandomAccessIterator1,
+          class _RandomAccessIterator2,
+          class _BinaryOperation>
+_RandomAccessIterator2 __pattern_adjacent_difference(
+    __parallel_tag<_IsVector> __tag,
+    _ExecutionPolicy&& __exec,
+    _RandomAccessIterator1 __first,
+    _RandomAccessIterator1 __last,
+    _RandomAccessIterator2 __d_first,
+    _BinaryOperation __op) {
+  _LIBCPP_ASSERT_UNCATEGORIZED(__first != __last, "range cannot be empty");
+  typedef typename std::iterator_traits<_RandomAccessIterator1>::reference _ReferenceType1;
+  typedef typename std::iterator_traits<_RandomAccessIterator2>::reference _ReferenceType2;
+
+  using __backend_tag = typename decltype(__tag)::__backend_tag;
+
+  *__d_first = *__first;
+  __par_backend::__parallel_for(
+      __backend_tag{},
+      std::forward<_ExecutionPolicy>(__exec),
+      __first,
+      __last - 1,
+      [&__op, __d_first, __first](_RandomAccessIterator1 __b, _RandomAccessIterator1 __e) {
+        _RandomAccessIterator2 __d_b = __d_first + (__b - __first);
+        __internal::__brick_walk3(
+            __b,
+            __e,
+            __b + 1,
+            __d_b + 1,
+            [&__op](_ReferenceType1 __x, _ReferenceType1 __y, _ReferenceType2 __z) { __z = __op(__y, __x); },
+            _IsVector{});
+      });
+  return __d_first + (__last - __first);
+}
+
+} // namespace __internal
+} // namespace __pstl
+
+#endif /* _PSTL_NUMERIC_IMPL_H */