1// -*- C++ -*-
2//===-- unseq_backend_simd.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_UNSEQ_BACKEND_SIMD_H
11#define _PSTL_UNSEQ_BACKEND_SIMD_H
12
13#include <type_traits>
14
15#include "utils.h"
16
17// This header defines the minimum set of vector routines required
18// to support parallel STL.
19namespace __pstl
20{
21namespace __unseq_backend
22{
23
24// Expect vector width up to 64 (or 512 bit)
25const std::size_t __lane_size = 64;
26
27template <class _Iterator, class _DifferenceType, class _Function>
28_Iterator
29__simd_walk_1(_Iterator __first, _DifferenceType __n, _Function __f) noexcept
30{
31 _PSTL_PRAGMA_SIMD
32 for (_DifferenceType __i = 0; __i < __n; ++__i)
33 __f(__first[__i]);
34
35 return __first + __n;
36}
37
38template <class _Iterator1, class _DifferenceType, class _Iterator2, class _Function>
39_Iterator2
40__simd_walk_2(_Iterator1 __first1, _DifferenceType __n, _Iterator2 __first2, _Function __f) noexcept
41{
42 _PSTL_PRAGMA_SIMD
43 for (_DifferenceType __i = 0; __i < __n; ++__i)
44 __f(__first1[__i], __first2[__i]);
45 return __first2 + __n;
46}
47
48template <class _Iterator1, class _DifferenceType, class _Iterator2, class _Iterator3, class _Function>
49_Iterator3
50__simd_walk_3(_Iterator1 __first1, _DifferenceType __n, _Iterator2 __first2, _Iterator3 __first3,
51 _Function __f) noexcept
52{
53 _PSTL_PRAGMA_SIMD
54 for (_DifferenceType __i = 0; __i < __n; ++__i)
55 __f(__first1[__i], __first2[__i], __first3[__i]);
56 return __first3 + __n;
57}
58
59// TODO: check whether __simd_first() can be used here
60template <class _Index, class _DifferenceType, class _Pred>
61bool
62__simd_or(_Index __first, _DifferenceType __n, _Pred __pred) noexcept
63{
64#if _PSTL_EARLYEXIT_PRESENT
65 _DifferenceType __i;
66 _PSTL_PRAGMA_VECTOR_UNALIGNED
67 _PSTL_PRAGMA_SIMD_EARLYEXIT
68 for (__i = 0; __i < __n; ++__i)
69 if (__pred(__first[__i]))
70 break;
71 return __i < __n;
72#else
73 _DifferenceType __block_size = 4 < __n ? 4 : __n;
74 const _Index __last = __first + __n;
75 while (__last != __first)
76 {
77 int32_t __flag = 1;
78 _PSTL_PRAGMA_SIMD_REDUCTION(& : __flag)
79 for (_DifferenceType __i = 0; __i < __block_size; ++__i)
80 if (__pred(*(__first + __i)))
81 __flag = 0;
82 if (!__flag)
83 return true;
84
85 __first += __block_size;
86 if (__last - __first >= __block_size << 1)
87 {
88 // Double the block _Size. Any unnecessary iterations can be amortized against work done so far.
89 __block_size <<= 1;
90 }
91 else
92 {
93 __block_size = __last - __first;
94 }
95 }
96 return false;
97#endif
98}
99
100template <class _Index, class _DifferenceType, class _Compare>
101_Index
102__simd_first(_Index __first, _DifferenceType __begin, _DifferenceType __end, _Compare __comp) noexcept
103{
104#if _PSTL_EARLYEXIT_PRESENT
105 _DifferenceType __i = __begin;
106 _PSTL_PRAGMA_VECTOR_UNALIGNED // Do not generate peel loop part
107 _PSTL_PRAGMA_SIMD_EARLYEXIT for (; __i < __end; ++__i)
108 {
109 if (__comp(__first, __i))
110 {
111 break;
112 }
113 }
114 return __first + __i;
115#else
116 // Experiments show good block sizes like this
117 const _DifferenceType __block_size = 8;
118 alignas(__lane_size) _DifferenceType __lane[__block_size] = {0};
119 while (__end - __begin >= __block_size)
120 {
121 _DifferenceType __found = 0;
122 _PSTL_PRAGMA_VECTOR_UNALIGNED // Do not generate peel loop part
123 _PSTL_PRAGMA_SIMD_REDUCTION(|
124 : __found) for (_DifferenceType __i = __begin; __i < __begin + __block_size;
125 ++__i)
126 {
127 const _DifferenceType __t = __comp(__first, __i);
128 __lane[__i - __begin] = __t;
129 __found |= __t;
130 }
131 if (__found)
132 {
133 _DifferenceType __i;
134 // This will vectorize
135 for (__i = 0; __i < __block_size; ++__i)
136 {
137 if (__lane[__i])
138 {
139 break;
140 }
141 }
142 return __first + __begin + __i;
143 }
144 __begin += __block_size;
145 }
146
147 //Keep remainder scalar
148 while (__begin != __end)
149 {
150 if (__comp(__first, __begin))
151 {
152 return __first + __begin;
153 }
154 ++__begin;
155 }
156 return __first + __end;
157#endif //_PSTL_EARLYEXIT_PRESENT
158}
159
160template <class _Index1, class _DifferenceType, class _Index2, class _Pred>
161std::pair<_Index1, _Index2>
162__simd_first(_Index1 __first1, _DifferenceType __n, _Index2 __first2, _Pred __pred) noexcept
163{
164#if _PSTL_EARLYEXIT_PRESENT
165 _DifferenceType __i = 0;
166 _PSTL_PRAGMA_VECTOR_UNALIGNED
167 _PSTL_PRAGMA_SIMD_EARLYEXIT
168 for (; __i < __n; ++__i)
169 if (__pred(__first1[__i], __first2[__i]))
170 break;
171 return std::make_pair(__first1 + __i, __first2 + __i);
172#else
173 const _Index1 __last1 = __first1 + __n;
174 const _Index2 __last2 = __first2 + __n;
175 // Experiments show good block sizes like this
176 const _DifferenceType __block_size = 8;
177 alignas(__lane_size) _DifferenceType __lane[__block_size] = {0};
178 while (__last1 - __first1 >= __block_size)
179 {
180 _DifferenceType __found = 0;
181 _DifferenceType __i;
182 _PSTL_PRAGMA_VECTOR_UNALIGNED // Do not generate peel loop part
183 _PSTL_PRAGMA_SIMD_REDUCTION(|
184 : __found) for (__i = 0; __i < __block_size; ++__i)
185 {
186 const _DifferenceType __t = __pred(__first1[__i], __first2[__i]);
187 __lane[__i] = __t;
188 __found |= __t;
189 }
190 if (__found)
191 {
192 _DifferenceType __i2;
193 // This will vectorize
194 for (__i2 = 0; __i2 < __block_size; ++__i2)
195 {
196 if (__lane[__i2])
197 break;
198 }
199 return std::make_pair(__first1 + __i2, __first2 + __i2);
200 }
201 __first1 += __block_size;
202 __first2 += __block_size;
203 }
204
205 //Keep remainder scalar
206 for (; __last1 != __first1; ++__first1, ++__first2)
207 if (__pred(*(__first1), *(__first2)))
208 return std::make_pair(__first1, __first2);
209
210 return std::make_pair(__last1, __last2);
211#endif //_PSTL_EARLYEXIT_PRESENT
212}
213
214template <class _Index, class _DifferenceType, class _Pred>
215_DifferenceType
216__simd_count(_Index __index, _DifferenceType __n, _Pred __pred) noexcept
217{
218 _DifferenceType __count = 0;
219 _PSTL_PRAGMA_SIMD_REDUCTION(+ : __count)
220 for (_DifferenceType __i = 0; __i < __n; ++__i)
221 if (__pred(*(__index + __i)))
222 ++__count;
223
224 return __count;
225}
226
227template <class _InputIterator, class _DifferenceType, class _OutputIterator, class _BinaryPredicate>
228_OutputIterator
229__simd_unique_copy(_InputIterator __first, _DifferenceType __n, _OutputIterator __result,
230 _BinaryPredicate __pred) noexcept
231{
232 if (__n == 0)
233 return __result;
234
235 _DifferenceType __cnt = 1;
236 __result[0] = __first[0];
237
238 _PSTL_PRAGMA_SIMD
239 for (_DifferenceType __i = 1; __i < __n; ++__i)
240 {
241 _PSTL_PRAGMA_SIMD_ORDERED_MONOTONIC(__cnt : 1)
242 if (!__pred(__first[__i], __first[__i - 1]))
243 {
244 __result[__cnt] = __first[__i];
245 ++__cnt;
246 }
247 }
248 return __result + __cnt;
249}
250
251template <class _InputIterator, class _DifferenceType, class _OutputIterator, class _Assigner>
252_OutputIterator
253__simd_assign(_InputIterator __first, _DifferenceType __n, _OutputIterator __result, _Assigner __assigner) noexcept
254{
255 _PSTL_USE_NONTEMPORAL_STORES_IF_ALLOWED
256 _PSTL_PRAGMA_SIMD
257 for (_DifferenceType __i = 0; __i < __n; ++__i)
258 __assigner(__first + __i, __result + __i);
259 return __result + __n;
260}
261
262template <class _InputIterator, class _DifferenceType, class _OutputIterator, class _UnaryPredicate>
263_OutputIterator
264__simd_copy_if(_InputIterator __first, _DifferenceType __n, _OutputIterator __result, _UnaryPredicate __pred) noexcept
265{
266 _DifferenceType __cnt = 0;
267
268 _PSTL_PRAGMA_SIMD
269 for (_DifferenceType __i = 0; __i < __n; ++__i)
270 {
271 _PSTL_PRAGMA_SIMD_ORDERED_MONOTONIC(__cnt : 1)
272 if (__pred(__first[__i]))
273 {
274 __result[__cnt] = __first[__i];
275 ++__cnt;
276 }
277 }
278 return __result + __cnt;
279}
280
281template <class _InputIterator, class _DifferenceType, class _BinaryPredicate>
282_DifferenceType
283__simd_calc_mask_2(_InputIterator __first, _DifferenceType __n, bool* __mask, _BinaryPredicate __pred) noexcept
284{
285 _DifferenceType __count = 0;
286
287 _PSTL_PRAGMA_SIMD_REDUCTION(+ : __count)
288 for (_DifferenceType __i = 0; __i < __n; ++__i)
289 {
290 __mask[__i] = !__pred(__first[__i], __first[__i - 1]);
291 __count += __mask[__i];
292 }
293 return __count;
294}
295
296template <class _InputIterator, class _DifferenceType, class _UnaryPredicate>
297_DifferenceType
298__simd_calc_mask_1(_InputIterator __first, _DifferenceType __n, bool* __mask, _UnaryPredicate __pred) noexcept
299{
300 _DifferenceType __count = 0;
301
302 _PSTL_PRAGMA_SIMD_REDUCTION(+ : __count)
303 for (_DifferenceType __i = 0; __i < __n; ++__i)
304 {
305 __mask[__i] = __pred(__first[__i]);
306 __count += __mask[__i];
307 }
308 return __count;
309}
310
311template <class _InputIterator, class _DifferenceType, class _OutputIterator, class _Assigner>
312void
313__simd_copy_by_mask(_InputIterator __first, _DifferenceType __n, _OutputIterator __result, bool* __mask,
314 _Assigner __assigner) noexcept
315{
316 _DifferenceType __cnt = 0;
317 _PSTL_PRAGMA_SIMD
318 for (_DifferenceType __i = 0; __i < __n; ++__i)
319 {
320 if (__mask[__i])
321 {
322 _PSTL_PRAGMA_SIMD_ORDERED_MONOTONIC(__cnt : 1)
323 {
324 __assigner(__first + __i, __result + __cnt);
325 ++__cnt;
326 }
327 }
328 }
329}
330
331template <class _InputIterator, class _DifferenceType, class _OutputIterator1, class _OutputIterator2>
332void
333__simd_partition_by_mask(_InputIterator __first, _DifferenceType __n, _OutputIterator1 __out_true,
334 _OutputIterator2 __out_false, bool* __mask) noexcept
335{
336 _DifferenceType __cnt_true = 0, __cnt_false = 0;
337 _PSTL_PRAGMA_SIMD
338 for (_DifferenceType __i = 0; __i < __n; ++__i)
339 {
340 _PSTL_PRAGMA_SIMD_ORDERED_MONOTONIC_2ARGS(__cnt_true : 1, __cnt_false : 1)
341 if (__mask[__i])
342 {
343 __out_true[__cnt_true] = __first[__i];
344 ++__cnt_true;
345 }
346 else
347 {
348 __out_false[__cnt_false] = __first[__i];
349 ++__cnt_false;
350 }
351 }
352}
353
354template <class _Index, class _DifferenceType, class _Tp>
355_Index
356__simd_fill_n(_Index __first, _DifferenceType __n, const _Tp& __value) noexcept
357{
358 _PSTL_USE_NONTEMPORAL_STORES_IF_ALLOWED
359 _PSTL_PRAGMA_SIMD
360 for (_DifferenceType __i = 0; __i < __n; ++__i)
361 __first[__i] = __value;
362 return __first + __n;
363}
364
365template <class _Index, class _DifferenceType, class _Generator>
366_Index
367__simd_generate_n(_Index __first, _DifferenceType __size, _Generator __g) noexcept
368{
369 _PSTL_USE_NONTEMPORAL_STORES_IF_ALLOWED
370 _PSTL_PRAGMA_SIMD
371 for (_DifferenceType __i = 0; __i < __size; ++__i)
372 __first[__i] = __g();
373 return __first + __size;
374}
375
376template <class _Index, class _BinaryPredicate>
377_Index
378__simd_adjacent_find(_Index __first, _Index __last, _BinaryPredicate __pred, bool __or_semantic) noexcept
379{
380 if (__last - __first < 2)
381 return __last;
382
383 typedef typename std::iterator_traits<_Index>::difference_type _DifferenceType;
384 _DifferenceType __i = 0;
385
386#if _PSTL_EARLYEXIT_PRESENT
387 //Some compiler versions fail to compile the following loop when iterators are used. Indices are used instead
388 const _DifferenceType __n = __last - __first - 1;
389 _PSTL_PRAGMA_VECTOR_UNALIGNED
390 _PSTL_PRAGMA_SIMD_EARLYEXIT
391 for (; __i < __n; ++__i)
392 if (__pred(__first[__i], __first[__i + 1]))
393 break;
394
395 return __i < __n ? __first + __i : __last;
396#else
397 // Experiments show good block sizes like this
398 //TODO: to consider tuning block_size for various data types
399 const _DifferenceType __block_size = 8;
400 alignas(__lane_size) _DifferenceType __lane[__block_size] = {0};
401 while (__last - __first >= __block_size)
402 {
403 _DifferenceType __found = 0;
404 _PSTL_PRAGMA_VECTOR_UNALIGNED // Do not generate peel loop part
405 _PSTL_PRAGMA_SIMD_REDUCTION(|
406 : __found) for (__i = 0; __i < __block_size - 1; ++__i)
407 {
408 //TODO: to improve SIMD vectorization
409 const _DifferenceType __t = __pred(*(__first + __i), *(__first + __i + 1));
410 __lane[__i] = __t;
411 __found |= __t;
412 }
413
414 //Process a pair of elements on a boundary of a data block
415 if (__first + __block_size < __last && __pred(*(__first + __i), *(__first + __i + 1)))
416 __lane[__i] = __found = 1;
417
418 if (__found)
419 {
420 if (__or_semantic)
421 return __first;
422
423 // This will vectorize
424 for (__i = 0; __i < __block_size; ++__i)
425 if (__lane[__i])
426 break;
427 return __first + __i; //As far as found is true a __result (__lane[__i] is true) is guaranteed
428 }
429 __first += __block_size;
430 }
431 //Process the rest elements
432 for (; __last - __first > 1; ++__first)
433 if (__pred(*__first, *(__first + 1)))
434 return __first;
435
436 return __last;
437#endif
438}
439
440// It was created to reduce the code inside std::enable_if
441template <typename _Tp, typename _BinaryOperation>
442using is_arithmetic_plus = std::integral_constant<bool, std::is_arithmetic<_Tp>::value &&
443 std::is_same<_BinaryOperation, std::plus<_Tp>>::value>;
444
445template <typename _DifferenceType, typename _Tp, typename _BinaryOperation, typename _UnaryOperation>
446typename std::enable_if<is_arithmetic_plus<_Tp, _BinaryOperation>::value, _Tp>::type
447__simd_transform_reduce(_DifferenceType __n, _Tp __init, _BinaryOperation, _UnaryOperation __f) noexcept
448{
449 _PSTL_PRAGMA_SIMD_REDUCTION(+ : __init)
450 for (_DifferenceType __i = 0; __i < __n; ++__i)
451 __init += __f(__i);
452 return __init;
453}
454
455template <typename _Size, typename _Tp, typename _BinaryOperation, typename _UnaryOperation>
456typename std::enable_if<!is_arithmetic_plus<_Tp, _BinaryOperation>::value, _Tp>::type
457__simd_transform_reduce(_Size __n, _Tp __init, _BinaryOperation __binary_op, _UnaryOperation __f) noexcept
458{
459 const _Size __block_size = __lane_size / sizeof(_Tp);
460 if (__n > 2 * __block_size && __block_size > 1)
461 {
462 alignas(__lane_size) char __lane_[__lane_size];
463 _Tp* __lane = reinterpret_cast<_Tp*>(__lane_);
464
465 // initializer
466 _PSTL_PRAGMA_SIMD
467 for (_Size __i = 0; __i < __block_size; ++__i)
468 {
469 ::new (__lane + __i) _Tp(__binary_op(__f(__i), __f(__block_size + __i)));
470 }
471 // main loop
472 _Size __i = 2 * __block_size;
473 const _Size last_iteration = __block_size * (__n / __block_size);
474 for (; __i < last_iteration; __i += __block_size)
475 {
476 _PSTL_PRAGMA_SIMD
477 for (_Size __j = 0; __j < __block_size; ++__j)
478 {
479 __lane[__j] = __binary_op(__lane[__j], __f(__i + __j));
480 }
481 }
482 // remainder
483 _PSTL_PRAGMA_SIMD
484 for (_Size __j = 0; __j < __n - last_iteration; ++__j)
485 {
486 __lane[__j] = __binary_op(__lane[__j], __f(last_iteration + __j));
487 }
488 // combiner
489 for (_Size __j = 0; __j < __block_size; ++__j)
490 {
491 __init = __binary_op(__init, __lane[__j]);
492 }
493 // destroyer
494 _PSTL_PRAGMA_SIMD
495 for (_Size __j = 0; __j < __block_size; ++__j)
496 {
497 __lane[__j].~_Tp();
498 }
499 }
500 else
501 {
502 for (_Size __i = 0; __i < __n; ++__i)
503 {
504 __init = __binary_op(__init, __f(__i));
505 }
506 }
507 return __init;
508}
509
510// Exclusive scan for "+" and arithmetic types
511template <class _InputIterator, class _Size, class _OutputIterator, class _UnaryOperation, class _Tp,
512 class _BinaryOperation>
513typename std::enable_if<is_arithmetic_plus<_Tp, _BinaryOperation>::value, std::pair<_OutputIterator, _Tp>>::type
514__simd_scan(_InputIterator __first, _Size __n, _OutputIterator __result, _UnaryOperation __unary_op, _Tp __init,
515 _BinaryOperation, /*Inclusive*/ std::false_type)
516{
517 _PSTL_PRAGMA_SIMD_SCAN(+ : __init)
518 for (_Size __i = 0; __i < __n; ++__i)
519 {
520 __result[__i] = __init;
521 _PSTL_PRAGMA_SIMD_EXCLUSIVE_SCAN(__init)
522 __init += __unary_op(__first[__i]);
523 }
524 return std::make_pair(__result + __n, __init);
525}
526
527// As soon as we cannot call __binary_op in "combiner" we create a wrapper over _Tp to encapsulate __binary_op
528template <typename _Tp, typename _BinaryOp>
529struct _Combiner
530{
531 _Tp __value;
532 _BinaryOp* __bin_op; // Here is a pointer to function because of default ctor
533
534 _Combiner() : __value{}, __bin_op(nullptr) {}
535 _Combiner(const _Tp& value, const _BinaryOp* bin_op) : __value(value), __bin_op(const_cast<_BinaryOp*>(bin_op)) {}
536 _Combiner(const _Combiner& __obj) : __value{}, __bin_op(__obj.__bin_op) {}
537
538 void
539 operator()(const _Combiner& __obj)
540 {
541 __value = (*__bin_op)(__value, __obj.__value);
542 }
543};
544
545// Exclusive scan for other binary operations and types
546template <class _InputIterator, class _Size, class _OutputIterator, class _UnaryOperation, class _Tp,
547 class _BinaryOperation>
548typename std::enable_if<!is_arithmetic_plus<_Tp, _BinaryOperation>::value, std::pair<_OutputIterator, _Tp>>::type
549__simd_scan(_InputIterator __first, _Size __n, _OutputIterator __result, _UnaryOperation __unary_op, _Tp __init,
550 _BinaryOperation __binary_op, /*Inclusive*/ std::false_type)
551{
552 typedef _Combiner<_Tp, _BinaryOperation> _CombinerType;
553 _CombinerType __init_{__init, &__binary_op};
554
555 _PSTL_PRAGMA_DECLARE_REDUCTION(__bin_op, _CombinerType)
556
557 _PSTL_PRAGMA_SIMD_SCAN(__bin_op : __init_)
558 for (_Size __i = 0; __i < __n; ++__i)
559 {
560 __result[__i] = __init_.__value;
561 _PSTL_PRAGMA_SIMD_EXCLUSIVE_SCAN(__init_)
562 _PSTL_PRAGMA_FORCEINLINE
563 __init_.__value = __binary_op(__init_.__value, __unary_op(__first[__i]));
564 }
565 return std::make_pair(__result + __n, __init_.__value);
566}
567
568// Inclusive scan for "+" and arithmetic types
569template <class _InputIterator, class _Size, class _OutputIterator, class _UnaryOperation, class _Tp,
570 class _BinaryOperation>
571typename std::enable_if<is_arithmetic_plus<_Tp, _BinaryOperation>::value, std::pair<_OutputIterator, _Tp>>::type
572__simd_scan(_InputIterator __first, _Size __n, _OutputIterator __result, _UnaryOperation __unary_op, _Tp __init,
573 _BinaryOperation, /*Inclusive*/ std::true_type)
574{
575 _PSTL_PRAGMA_SIMD_SCAN(+ : __init)
576 for (_Size __i = 0; __i < __n; ++__i)
577 {
578 __init += __unary_op(__first[__i]);
579 _PSTL_PRAGMA_SIMD_INCLUSIVE_SCAN(__init)
580 __result[__i] = __init;
581 }
582 return std::make_pair(__result + __n, __init);
583}
584
585// Inclusive scan for other binary operations and types
586template <class _InputIterator, class _Size, class _OutputIterator, class _UnaryOperation, class _Tp,
587 class _BinaryOperation>
588typename std::enable_if<!is_arithmetic_plus<_Tp, _BinaryOperation>::value, std::pair<_OutputIterator, _Tp>>::type
589__simd_scan(_InputIterator __first, _Size __n, _OutputIterator __result, _UnaryOperation __unary_op, _Tp __init,
590 _BinaryOperation __binary_op, std::true_type)
591{
592 typedef _Combiner<_Tp, _BinaryOperation> _CombinerType;
593 _CombinerType __init_{__init, &__binary_op};
594
595 _PSTL_PRAGMA_DECLARE_REDUCTION(__bin_op, _CombinerType)
596
597 _PSTL_PRAGMA_SIMD_SCAN(__bin_op : __init_)
598 for (_Size __i = 0; __i < __n; ++__i)
599 {
600 _PSTL_PRAGMA_FORCEINLINE
601 __init_.__value = __binary_op(__init_.__value, __unary_op(__first[__i]));
602 _PSTL_PRAGMA_SIMD_INCLUSIVE_SCAN(__init_)
603 __result[__i] = __init_.__value;
604 }
605 return std::make_pair(__result + __n, __init_.__value);
606}
607
608// [restriction] - std::iterator_traits<_ForwardIterator>::value_type should be DefaultConstructible.
609// complexity [violation] - We will have at most (__n-1 + number_of_lanes) comparisons instead of at most __n-1.
610template <typename _ForwardIterator, typename _Size, typename _Compare>
611_ForwardIterator
612__simd_min_element(_ForwardIterator __first, _Size __n, _Compare __comp) noexcept
613{
614 if (__n == 0)
615 {
616 return __first;
617 }
618
619 typedef typename std::iterator_traits<_ForwardIterator>::value_type _ValueType;
620 struct _ComplexType
621 {
622 _ValueType __min_val;
623 _Size __min_ind;
624 _Compare* __min_comp;
625
626 _ComplexType() : __min_val{}, __min_ind{}, __min_comp(nullptr) {}
627 _ComplexType(const _ValueType& val, const _Compare* comp)
628 : __min_val(val), __min_ind(0), __min_comp(const_cast<_Compare*>(comp))
629 {
630 }
631 _ComplexType(const _ComplexType& __obj)
632 : __min_val(__obj.__min_val), __min_ind(__obj.__min_ind), __min_comp(__obj.__min_comp)
633 {
634 }
635
636 _PSTL_PRAGMA_DECLARE_SIMD
637 void
638 operator()(const _ComplexType& __obj)
639 {
640 if (!(*__min_comp)(__min_val, __obj.__min_val) &&
641 ((*__min_comp)(__obj.__min_val, __min_val) || __obj.__min_ind - __min_ind < 0))
642 {
643 __min_val = __obj.__min_val;
644 __min_ind = __obj.__min_ind;
645 }
646 }
647 };
648
649 _ComplexType __init{*__first, &__comp};
650
651 _PSTL_PRAGMA_DECLARE_REDUCTION(__min_func, _ComplexType)
652
653 _PSTL_PRAGMA_SIMD_REDUCTION(__min_func : __init)
654 for (_Size __i = 1; __i < __n; ++__i)
655 {
656 const _ValueType __min_val = __init.__min_val;
657 const _ValueType __current = __first[__i];
658 if (__comp(__current, __min_val))
659 {
660 __init.__min_val = __current;
661 __init.__min_ind = __i;
662 }
663 }
664 return __first + __init.__min_ind;
665}
666
667// [restriction] - std::iterator_traits<_ForwardIterator>::value_type should be DefaultConstructible.
668// complexity [violation] - We will have at most (2*(__n-1) + 4*number_of_lanes) comparisons instead of at most [1.5*(__n-1)].
669template <typename _ForwardIterator, typename _Size, typename _Compare>
670std::pair<_ForwardIterator, _ForwardIterator>
671__simd_minmax_element(_ForwardIterator __first, _Size __n, _Compare __comp) noexcept
672{
673 if (__n == 0)
674 {
675 return std::make_pair(__first, __first);
676 }
677 typedef typename std::iterator_traits<_ForwardIterator>::value_type _ValueType;
678
679 struct _ComplexType
680 {
681 _ValueType __min_val;
682 _ValueType __max_val;
683 _Size __min_ind;
684 _Size __max_ind;
685 _Compare* __minmax_comp;
686
687 _ComplexType() : __min_val{}, __max_val{}, __min_ind{}, __max_ind{}, __minmax_comp(nullptr) {}
688 _ComplexType(const _ValueType& min_val, const _ValueType& max_val, const _Compare* comp)
689 : __min_val(min_val), __max_val(max_val), __min_ind(0), __max_ind(0),
690 __minmax_comp(const_cast<_Compare*>(comp))
691 {
692 }
693 _ComplexType(const _ComplexType& __obj)
694 : __min_val(__obj.__min_val), __max_val(__obj.__max_val), __min_ind(__obj.__min_ind),
695 __max_ind(__obj.__max_ind), __minmax_comp(__obj.__minmax_comp)
696 {
697 }
698
699 void
700 operator()(const _ComplexType& __obj)
701 {
702 // min
703 if ((*__minmax_comp)(__obj.__min_val, __min_val))
704 {
705 __min_val = __obj.__min_val;
706 __min_ind = __obj.__min_ind;
707 }
708 else if (!(*__minmax_comp)(__min_val, __obj.__min_val))
709 {
710 __min_val = __obj.__min_val;
711 __min_ind = (__min_ind - __obj.__min_ind < 0) ? __min_ind : __obj.__min_ind;
712 }
713
714 // max
715 if ((*__minmax_comp)(__max_val, __obj.__max_val))
716 {
717 __max_val = __obj.__max_val;
718 __max_ind = __obj.__max_ind;
719 }
720 else if (!(*__minmax_comp)(__obj.__max_val, __max_val))
721 {
722 __max_val = __obj.__max_val;
723 __max_ind = (__max_ind - __obj.__max_ind < 0) ? __obj.__max_ind : __max_ind;
724 }
725 }
726 };
727
728 _ComplexType __init{*__first, *__first, &__comp};
729
730 _PSTL_PRAGMA_DECLARE_REDUCTION(__min_func, _ComplexType);
731
732 _PSTL_PRAGMA_SIMD_REDUCTION(__min_func : __init)
733 for (_Size __i = 1; __i < __n; ++__i)
734 {
735 auto __min_val = __init.__min_val;
736 auto __max_val = __init.__max_val;
737 auto __current = __first + __i;
738 if (__comp(*__current, __min_val))
739 {
740 __init.__min_val = *__current;
741 __init.__min_ind = __i;
742 }
743 else if (!__comp(*__current, __max_val))
744 {
745 __init.__max_val = *__current;
746 __init.__max_ind = __i;
747 }
748 }
749 return std::make_pair(__first + __init.__min_ind, __first + __init.__max_ind);
750}
751
752template <class _InputIterator, class _DifferenceType, class _OutputIterator1, class _OutputIterator2,
753 class _UnaryPredicate>
754std::pair<_OutputIterator1, _OutputIterator2>
755__simd_partition_copy(_InputIterator __first, _DifferenceType __n, _OutputIterator1 __out_true,
756 _OutputIterator2 __out_false, _UnaryPredicate __pred) noexcept
757{
758 _DifferenceType __cnt_true = 0, __cnt_false = 0;
759
760 _PSTL_PRAGMA_SIMD
761 for (_DifferenceType __i = 0; __i < __n; ++__i)
762 {
763 _PSTL_PRAGMA_SIMD_ORDERED_MONOTONIC_2ARGS(__cnt_true : 1, __cnt_false : 1)
764 if (__pred(__first[__i]))
765 {
766 __out_true[__cnt_true] = __first[__i];
767 ++__cnt_true;
768 }
769 else
770 {
771 __out_false[__cnt_false] = __first[__i];
772 ++__cnt_false;
773 }
774 }
775 return std::make_pair(__out_true + __cnt_true, __out_false + __cnt_false);
776}
777
778template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
779_ForwardIterator1
780__simd_find_first_of(_ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __s_first,
781 _ForwardIterator2 __s_last, _BinaryPredicate __pred) noexcept
782{
783 typedef typename std::iterator_traits<_ForwardIterator1>::difference_type _DifferencType;
784
785 const _DifferencType __n1 = __last - __first;
786 const _DifferencType __n2 = __s_last - __s_first;
787 if (__n1 == 0 || __n2 == 0)
788 {
789 return __last; // according to the standard
790 }
791
792 // Common case
793 // If first sequence larger than second then we'll run simd_first with parameters of first sequence.
794 // Otherwise, vice versa.
795 if (__n1 < __n2)
796 {
797 for (; __first != __last; ++__first)
798 {
799 if (__unseq_backend::__simd_or(
800 __s_first, __n2,
801 __internal::__equal_value_by_pred<decltype(*__first), _BinaryPredicate>(*__first, __pred)))
802 {
803 return __first;
804 }
805 }
806 }
807 else
808 {
809 for (; __s_first != __s_last; ++__s_first)
810 {
811 const auto __result = __unseq_backend::__simd_first(
812 __first, _DifferencType(0), __n1, [__s_first, &__pred](_ForwardIterator1 __it, _DifferencType __i) {
813 return __pred(__it[__i], *__s_first);
814 });
815 if (__result != __last)
816 {
817 return __result;
818 }
819 }
820 }
821 return __last;
822}
823
824template <class _RandomAccessIterator, class _DifferenceType, class _UnaryPredicate>
825_RandomAccessIterator
826__simd_remove_if(_RandomAccessIterator __first, _DifferenceType __n, _UnaryPredicate __pred) noexcept
827{
828 // find first element we need to remove
829 auto __current = __unseq_backend::__simd_first(
830 __first, _DifferenceType(0), __n,
831 [&__pred](_RandomAccessIterator __it, _DifferenceType __i) { return __pred(__it[__i]); });
832 __n -= __current - __first;
833
834 // if we have in sequence only one element that pred(__current[1]) != false we can exit the function
835 if (__n < 2)
836 {
837 return __current;
838 }
839
840 _DifferenceType __cnt = 0;
841 _PSTL_PRAGMA_SIMD
842 for (_DifferenceType __i = 1; __i < __n; ++__i)
843 {
844 _PSTL_PRAGMA_SIMD_ORDERED_MONOTONIC(__cnt : 1)
845 if (!__pred(__current[__i]))
846 {
847 __current[__cnt] = std::move(__current[__i]);
848 ++__cnt;
849 }
850 }
851 return __current + __cnt;
852}
853} // namespace __unseq_backend
854} // namespace __pstl
855
856#endif /* _PSTL_UNSEQ_BACKEND_SIMD_H */
857

source code of include/c++/11/pstl/unseq_backend_simd.h