1 // -*- C++ -*-
2 //===-- numeric_impl.h ----------------------------------------------------===//
3 //
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //
8 //===----------------------------------------------------------------------===//
9
10 #ifndef _PSTL_NUMERIC_IMPL_H
11 #define _PSTL_NUMERIC_IMPL_H
12
13 #include <iterator>
14 #include <type_traits>
15 #include <numeric>
16
17 #include "parallel_backend.h"
18 #include "pstl_config.h"
19 #include "execution_impl.h"
20 #include "unseq_backend_simd.h"
21 #include "algorithm_fwd.h"
22
23 namespace __pstl
24 {
25 namespace __internal
26 {
27
28 //------------------------------------------------------------------------
29 // transform_reduce (version with two binary functions, according to draft N4659)
30 //------------------------------------------------------------------------
31
32 template <class _ForwardIterator1, class _ForwardIterator2, class _Tp, class _BinaryOperation1, class _BinaryOperation2>
33 _Tp
34 __brick_transform_reduce(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _Tp __init,
35 _BinaryOperation1 __binary_op1, _BinaryOperation2 __binary_op2,
36 /*is_vector=*/std::false_type) noexcept
37 {
38 return std::inner_product(__first1, __last1, __first2, __init, __binary_op1, __binary_op2);
39 }
40
41 template <class _ForwardIterator1, class _ForwardIterator2, class _Tp, class _BinaryOperation1, class _BinaryOperation2>
42 _Tp
43 __brick_transform_reduce(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _Tp __init,
44 _BinaryOperation1 __binary_op1, _BinaryOperation2 __binary_op2,
45 /*is_vector=*/std::true_type) noexcept
46 {
47 typedef typename std::iterator_traits<_ForwardIterator1>::difference_type _DifferenceType;
48 return __unseq_backend::__simd_transform_reduce(
49 __last1 - __first1, __init, __binary_op1,
50 [=, &__binary_op2](_DifferenceType __i) { return __binary_op2(__first1[__i], __first2[__i]); });
51 }
52
53 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Tp, class _BinaryOperation1,
54 class _BinaryOperation2, class _IsVector>
55 _Tp
56 __pattern_transform_reduce(_ExecutionPolicy&&, _ForwardIterator1 __first1, _ForwardIterator1 __last1,
57 _ForwardIterator2 __first2, _Tp __init, _BinaryOperation1 __binary_op1,
58 _BinaryOperation2 __binary_op2, _IsVector __is_vector,
59 /*is_parallel=*/std::false_type) noexcept
60 {
61 return __brick_transform_reduce(__first1, __last1, __first2, __init, __binary_op1, __binary_op2, __is_vector);
62 }
63
64 template <class _ExecutionPolicy, class _RandomAccessIterator1, class _RandomAccessIterator2, class _Tp,
65 class _BinaryOperation1, class _BinaryOperation2, class _IsVector>
66 _Tp
67 __pattern_transform_reduce(_ExecutionPolicy&& __exec, _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
68 _RandomAccessIterator2 __first2, _Tp __init, _BinaryOperation1 __binary_op1,
69 _BinaryOperation2 __binary_op2, _IsVector __is_vector, /*is_parallel=*/std::true_type)
70 {
71 return __internal::__except_handler([&]() {
72 return __par_backend::__parallel_transform_reduce(
73 std::forward<_ExecutionPolicy>(__exec), __first1, __last1,
74 [__first1, __first2, __binary_op2](_RandomAccessIterator1 __i) mutable {
75 return __binary_op2(*__i, *(__first2 + (__i - __first1)));
76 },
77 __init,
78 __binary_op1, // Combine
79 [__first1, __first2, __binary_op1, __binary_op2,
80 __is_vector](_RandomAccessIterator1 __i, _RandomAccessIterator1 __j, _Tp __init) -> _Tp {
81 return __internal::__brick_transform_reduce(__i, __j, __first2 + (__i - __first1), __init, __binary_op1,
82 __binary_op2, __is_vector);
83 });
84 });
85 }
86
87 //------------------------------------------------------------------------
88 // transform_reduce (version with unary and binary functions)
89 //------------------------------------------------------------------------
90
91 template <class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation>
92 _Tp
93 __brick_transform_reduce(_ForwardIterator __first, _ForwardIterator __last, _Tp __init, _BinaryOperation __binary_op,
94 _UnaryOperation __unary_op, /*is_vector=*/std::false_type) noexcept
95 {
96 return std::transform_reduce(__first, __last, __init, __binary_op, __unary_op);
97 }
98
99 template <class _ForwardIterator, class _Tp, class _UnaryOperation, class _BinaryOperation>
100 _Tp
101 __brick_transform_reduce(_ForwardIterator __first, _ForwardIterator __last, _Tp __init, _BinaryOperation __binary_op,
102 _UnaryOperation __unary_op, /*is_vector=*/std::true_type) noexcept
103 {
104 typedef typename std::iterator_traits<_ForwardIterator>::difference_type _DifferenceType;
105 return __unseq_backend::__simd_transform_reduce(
106 __last - __first, __init, __binary_op,
107 [=, &__unary_op](_DifferenceType __i) { return __unary_op(__first[__i]); });
108 }
109
110 template <class _ExecutionPolicy, class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation,
111 class _IsVector>
112 _Tp
113 __pattern_transform_reduce(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __last, _Tp __init,
114 _BinaryOperation __binary_op, _UnaryOperation __unary_op, _IsVector __is_vector,
115 /*is_parallel=*/std::false_type) noexcept
116 {
117 return __internal::__brick_transform_reduce(__first, __last, __init, __binary_op, __unary_op, __is_vector);
118 }
119
120 template <class _ExecutionPolicy, class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation,
121 class _IsVector>
122 _Tp
123 __pattern_transform_reduce(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Tp __init,
124 _BinaryOperation __binary_op, _UnaryOperation __unary_op, _IsVector __is_vector,
125 /*is_parallel=*/std::true_type)
126 {
127 return __internal::__except_handler([&]() {
128 return __par_backend::__parallel_transform_reduce(
129 std::forward<_ExecutionPolicy>(__exec), __first, __last,
130 [__unary_op](_ForwardIterator __i) mutable { return __unary_op(*__i); }, __init, __binary_op,
131 [__unary_op, __binary_op, __is_vector](_ForwardIterator __i, _ForwardIterator __j, _Tp __init) {
132 return __internal::__brick_transform_reduce(__i, __j, __init, __binary_op, __unary_op, __is_vector);
133 });
134 });
135 }
136
137 //------------------------------------------------------------------------
138 // transform_exclusive_scan
139 //
140 // walk3 evaluates f(x,y,z) for (x,y,z) drawn from [first1,last1), [first2,...), [first3,...)
141 //------------------------------------------------------------------------
142
143 // Exclusive form
144 template <class _ForwardIterator, class _OutputIterator, class _UnaryOperation, class _Tp, class _BinaryOperation>
145 std::pair<_OutputIterator, _Tp>
146 __brick_transform_scan(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result,
147 _UnaryOperation __unary_op, _Tp __init, _BinaryOperation __binary_op,
148 /*Inclusive*/ std::false_type, /*is_vector=*/std::false_type) noexcept
149 {
150 for (; __first != __last; ++__first, ++__result)
151 {
152 *__result = __init;
153 _PSTL_PRAGMA_FORCEINLINE
154 __init = __binary_op(__init, __unary_op(*__first));
155 }
156 return std::make_pair(__result, __init);
157 }
158
159 // Inclusive form
160 template <class _ForwardIterator, class _OutputIterator, class _UnaryOperation, class _Tp, class _BinaryOperation>
161 std::pair<_OutputIterator, _Tp>
162 __brick_transform_scan(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result,
163 _UnaryOperation __unary_op, _Tp __init, _BinaryOperation __binary_op,
164 /*Inclusive*/ std::true_type, /*is_vector=*/std::false_type) noexcept
165 {
166 for (; __first != __last; ++__first, ++__result)
167 {
168 _PSTL_PRAGMA_FORCEINLINE
169 __init = __binary_op(__init, __unary_op(*__first));
170 *__result = __init;
171 }
172 return std::make_pair(__result, __init);
173 }
174
175 // type is arithmetic and binary operation is a user defined operation.
176 template <typename _Tp, typename _BinaryOperation>
177 using is_arithmetic_udop = std::integral_constant<bool, std::is_arithmetic<_Tp>::value &&
178 !std::is_same<_BinaryOperation, std::plus<_Tp>>::value>;
179
180 // [restriction] - T shall be DefaultConstructible.
181 // [violation] - default ctor of T shall set the identity value for binary_op.
182 template <class _ForwardIterator, class _OutputIterator, class _UnaryOperation, class _Tp, class _BinaryOperation,
183 class _Inclusive>
184 typename std::enable_if<!is_arithmetic_udop<_Tp, _BinaryOperation>::value, std::pair<_OutputIterator, _Tp>>::type
185 __brick_transform_scan(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result,
186 _UnaryOperation __unary_op, _Tp __init, _BinaryOperation __binary_op, _Inclusive,
187 /*is_vector=*/std::true_type) noexcept
188 {
189 #if (_PSTL_UDS_PRESENT)
190 return __unseq_backend::__simd_scan(__first, __last - __first, __result, __unary_op, __init, __binary_op,
191 _Inclusive());
192 #else
193 // We need to call serial brick here to call function for inclusive and exclusive scan that depends on _Inclusive() value
194 return __internal::__brick_transform_scan(__first, __last, __result, __unary_op, __init, __binary_op, _Inclusive(),
195 /*is_vector=*/std::false_type());
196 #endif
197 }
198
199 template <class _ForwardIterator, class _OutputIterator, class _UnaryOperation, class _Tp, class _BinaryOperation,
200 class _Inclusive>
201 typename std::enable_if<is_arithmetic_udop<_Tp, _BinaryOperation>::value, std::pair<_OutputIterator, _Tp>>::type
202 __brick_transform_scan(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result,
203 _UnaryOperation __unary_op, _Tp __init, _BinaryOperation __binary_op, _Inclusive,
204 /*is_vector=*/std::true_type) noexcept
205 {
206 return __internal::__brick_transform_scan(__first, __last, __result, __unary_op, __init, __binary_op, _Inclusive(),
207 /*is_vector=*/std::false_type());
208 }
209
210 template <class _ExecutionPolicy, class _ForwardIterator, class _OutputIterator, class _UnaryOperation, class _Tp,
211 class _BinaryOperation, class _Inclusive, class _IsVector>
212 _OutputIterator
213 __pattern_transform_scan(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __last,
214 _OutputIterator __result, _UnaryOperation __unary_op, _Tp __init, _BinaryOperation __binary_op,
215 _Inclusive, _IsVector __is_vector, /*is_parallel=*/std::false_type) noexcept
216 {
217 return __internal::__brick_transform_scan(__first, __last, __result, __unary_op, __init, __binary_op, _Inclusive(),
218 __is_vector)
219 .first;
220 }
221
222 template <class _ExecutionPolicy, class _RandomAccessIterator, class _OutputIterator, class _UnaryOperation, class _Tp,
223 class _BinaryOperation, class _Inclusive, class _IsVector>
224 typename std::enable_if<!std::is_floating_point<_Tp>::value, _OutputIterator>::type
225 __pattern_transform_scan(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last,
226 _OutputIterator __result, _UnaryOperation __unary_op, _Tp __init, _BinaryOperation __binary_op,
227 _Inclusive, _IsVector __is_vector, /*is_parallel=*/std::true_type)
228 {
229 typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _DifferenceType;
230
231 return __internal::__except_handler([&]() {
232 __par_backend::__parallel_transform_scan(
233 std::forward<_ExecutionPolicy>(__exec), __last - __first,
234 [__first, __unary_op](_DifferenceType __i) mutable { return __unary_op(__first[__i]); }, __init,
235 __binary_op,
236 [__first, __unary_op, __binary_op](_DifferenceType __i, _DifferenceType __j, _Tp __init) {
237 // Execute serial __brick_transform_reduce, due to the explicit SIMD vectorization (reduction) requires a commutative operation for the guarantee of correct scan.
238 return __internal::__brick_transform_reduce(__first + __i, __first + __j, __init, __binary_op,
239 __unary_op,
240 /*__is_vector*/ std::false_type());
241 },
242 [__first, __unary_op, __binary_op, __result, __is_vector](_DifferenceType __i, _DifferenceType __j,
243 _Tp __init) {
244 return __internal::__brick_transform_scan(__first + __i, __first + __j, __result + __i, __unary_op,
245 __init, __binary_op, _Inclusive(), __is_vector)
246 .second;
247 });
248 return __result + (__last - __first);
249 });
250 }
251
252 template <class _ExecutionPolicy, class _RandomAccessIterator, class _OutputIterator, class _UnaryOperation, class _Tp,
253 class _BinaryOperation, class _Inclusive, class _IsVector>
254 typename std::enable_if<std::is_floating_point<_Tp>::value, _OutputIterator>::type
255 __pattern_transform_scan(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last,
256 _OutputIterator __result, _UnaryOperation __unary_op, _Tp __init, _BinaryOperation __binary_op,
257 _Inclusive, _IsVector __is_vector, /*is_parallel=*/std::true_type)
258 {
259 typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _DifferenceType;
260 _DifferenceType __n = __last - __first;
261
262 if (__n <= 0)
263 {
264 return __result;
265 }
266 return __internal::__except_handler([&]() {
267 __par_backend::__parallel_strict_scan(
268 std::forward<_ExecutionPolicy>(__exec), __n, __init,
269 [__first, __unary_op, __binary_op, __result, __is_vector](_DifferenceType __i, _DifferenceType __len) {
270 return __internal::__brick_transform_scan(__first + __i, __first + (__i + __len), __result + __i,
271 __unary_op, _Tp{}, __binary_op, _Inclusive(), __is_vector)
272 .second;
273 },
274 __binary_op,
275 [__result, &__binary_op](_DifferenceType __i, _DifferenceType __len, _Tp __initial) {
276 return *(std::transform(__result + __i, __result + __i + __len, __result + __i,
277 [&__initial, &__binary_op](const _Tp& __x) {
278 _PSTL_PRAGMA_FORCEINLINE
279 return __binary_op(__initial, __x);
280 }) -
281 1);
282 },
283 [](_Tp) {});
284 return __result + (__last - __first);
285 });
286 }
287
288 //------------------------------------------------------------------------
289 // adjacent_difference
290 //------------------------------------------------------------------------
291
292 template <class _ForwardIterator, class _OutputIterator, class _BinaryOperation>
293 _OutputIterator
294 __brick_adjacent_difference(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __d_first,
295 _BinaryOperation __op, /*is_vector*/ std::false_type) noexcept
296 {
297 return std::adjacent_difference(__first, __last, __d_first, __op);
298 }
299
300 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryOperation>
301 _ForwardIterator2
302 __brick_adjacent_difference(_ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __d_first,
303 _BinaryOperation __op, /*is_vector=*/std::true_type) noexcept
304 {
305 _PSTL_ASSERT(__first != __last);
306
307 typedef typename std::iterator_traits<_ForwardIterator1>::reference _ReferenceType1;
308 typedef typename std::iterator_traits<_ForwardIterator2>::reference _ReferenceType2;
309
310 auto __n = __last - __first;
311 *__d_first = *__first;
312 return __unseq_backend::__simd_walk_3(
313 __first + 1, __n - 1, __first, __d_first + 1,
314 [&__op](_ReferenceType1 __x, _ReferenceType1 __y, _ReferenceType2 __z) { __z = __op(__x, __y); });
315 }
316
317 template <class _ExecutionPolicy, class _ForwardIterator, class _OutputIterator, class _BinaryOperation,
318 class _IsVector>
319 _OutputIterator
320 __pattern_adjacent_difference(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __last,
321 _OutputIterator __d_first, _BinaryOperation __op, _IsVector __is_vector,
322 /*is_parallel*/ std::false_type) noexcept
323 {
324 return __internal::__brick_adjacent_difference(__first, __last, __d_first, __op, __is_vector);
325 }
326
327 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _BinaryOperation,
328 class _IsVector>
329 _ForwardIterator2
330 __pattern_adjacent_difference(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last,
331 _ForwardIterator2 __d_first, _BinaryOperation __op, _IsVector __is_vector,
332 /*is_parallel=*/std::true_type)
333 {
334 _PSTL_ASSERT(__first != __last);
335 typedef typename std::iterator_traits<_ForwardIterator1>::reference _ReferenceType1;
336 typedef typename std::iterator_traits<_ForwardIterator2>::reference _ReferenceType2;
337
338 *__d_first = *__first;
339 __par_backend::__parallel_for(
340 std::forward<_ExecutionPolicy>(__exec), __first, __last - 1,
341 [&__op, __is_vector, __d_first, __first](_ForwardIterator1 __b, _ForwardIterator1 __e) {
342 _ForwardIterator2 __d_b = __d_first + (__b - __first);
343 __internal::__brick_walk3(
344 __b, __e, __b + 1, __d_b + 1,
345 [&__op](_ReferenceType1 __x, _ReferenceType1 __y, _ReferenceType2 __z) { __z = __op(__y, __x); },
346 __is_vector);
347 });
348 return __d_first + (__last - __first);
349 }
350
351 } // namespace __internal
352 } // namespace __pstl
353
354 #endif /* _PSTL_NUMERIC_IMPL_H */