1 //===----------------------------------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_ANY_OF_H 10 #define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_ANY_OF_H 11 12 #include <__algorithm/any_of.h> 13 #include <__algorithm/find_if.h> 14 #include <__algorithm/pstl_backends/cpu_backends/backend.h> 15 #include <__atomic/atomic.h> 16 #include <__atomic/memory_order.h> 17 #include <__config> 18 #include <__functional/operations.h> 19 #include <__iterator/iterator_traits.h> 20 #include <__type_traits/is_execution_policy.h> 21 #include <__utility/pair.h> 22 #include <__utility/terminate_on_exception.h> 23 #include <cstdint> 24 25 #if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17 26 27 _LIBCPP_BEGIN_NAMESPACE_STD 28 29 template <class _Index, class _Brick> 30 _LIBCPP_HIDE_FROM_ABI bool __parallel_or(_Index __first, _Index __last, _Brick __f) { 31 std::atomic<bool> __found(false); 32 __par_backend::__parallel_for(__first, __last, [__f, &__found](_Index __i, _Index __j) { 33 if (!__found.load(std::memory_order_relaxed) && __f(__i, __j)) { 34 __found.store(true, std::memory_order_relaxed); 35 __par_backend::__cancel_execution(); 36 } 37 }); 38 return __found; 39 } 40 41 // TODO: check whether __simd_first() can be used here 42 template <class _Index, class _DifferenceType, class _Pred> 43 _LIBCPP_HIDE_FROM_ABI bool __simd_or(_Index __first, _DifferenceType __n, _Pred __pred) noexcept { 44 _DifferenceType __block_size = 4 < __n ? 4 : __n; 45 const _Index __last = __first + __n; 46 while (__last != __first) { 47 int32_t __flag = 1; 48 _PSTL_PRAGMA_SIMD_REDUCTION(& : __flag) 49 for (_DifferenceType __i = 0; __i < __block_size; ++__i) 50 if (__pred(*(__first + __i))) 51 __flag = 0; 52 if (!__flag) 53 return true; 54 55 __first += __block_size; 56 if (__last - __first >= __block_size << 1) { 57 // Double the block _Size. Any unnecessary iterations can be amortized against work done so far. 58 __block_size <<= 1; 59 } else { 60 __block_size = __last - __first; 61 } 62 } 63 return false; 64 } 65 66 template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate> 67 _LIBCPP_HIDE_FROM_ABI bool 68 __pstl_any_of(__cpu_backend_tag, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) { 69 if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> && 70 __has_random_access_iterator_category<_ForwardIterator>::value) { 71 return std::__terminate_on_exception([&] { 72 return std::__parallel_or( 73 __first, __last, [&__pred](_ForwardIterator __brick_first, _ForwardIterator __brick_last) { 74 return std::__pstl_any_of<__remove_parallel_policy_t<_ExecutionPolicy>>( 75 __cpu_backend_tag{}, __brick_first, __brick_last, __pred); 76 }); 77 }); 78 } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> && 79 __has_random_access_iterator_category<_ForwardIterator>::value) { 80 return std::__simd_or(__first, __last - __first, __pred); 81 } else { 82 return std::any_of(__first, __last, __pred); 83 } 84 } 85 86 _LIBCPP_END_NAMESPACE_STD 87 88 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17 89 90 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_ANY_OF_H 91