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