1 // -*- C++ -*-
2 // -*-===----------------------------------------------------------------------===//
3 //
4 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
5 //
6 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
7 // See https://llvm.org/LICENSE.txt for license information.
8 //
9 //===----------------------------------------------------------------------===//
10
11 #ifndef _PSTL_INTERNAL_OMP_PARALLEL_REDUCE_H
12 #define _PSTL_INTERNAL_OMP_PARALLEL_REDUCE_H
13
14 #include "util.h"
15
16 namespace __pstl
17 {
18 namespace __omp_backend
19 {
20
21 template <class _RandomAccessIterator, class _Value, typename _RealBody, typename _Reduction>
22 _Value
__parallel_reduce_body(_RandomAccessIterator __first,_RandomAccessIterator __last,_Value __identity,_RealBody __real_body,_Reduction __reduce)23 __parallel_reduce_body(_RandomAccessIterator __first, _RandomAccessIterator __last, _Value __identity,
24 _RealBody __real_body, _Reduction __reduce)
25 {
26 if (__should_run_serial(__first, __last))
27 {
28 return __real_body(__first, __last, __identity);
29 }
30
31 auto __middle = __first + ((__last - __first) / 2);
32 _Value __v1(__identity), __v2(__identity);
33 __parallel_invoke_body(
34 [&]() { __v1 = __parallel_reduce_body(__first, __middle, __identity, __real_body, __reduce); },
35 [&]() { __v2 = __parallel_reduce_body(__middle, __last, __identity, __real_body, __reduce); });
36
37 return __reduce(__v1, __v2);
38 }
39
40 //------------------------------------------------------------------------
41 // Notation:
42 // r(i,j,init) returns reduction of init with reduction over [i,j)
43 // c(x,y) combines values x and y that were the result of r
44 //------------------------------------------------------------------------
45
46 template <class _ExecutionPolicy, class _RandomAccessIterator, class _Value, typename _RealBody, typename _Reduction>
47 _Value
__parallel_reduce(__pstl::__internal::__openmp_backend_tag,_ExecutionPolicy &&,_RandomAccessIterator __first,_RandomAccessIterator __last,_Value __identity,_RealBody __real_body,_Reduction __reduction)48 __parallel_reduce(__pstl::__internal::__openmp_backend_tag, _ExecutionPolicy&&, _RandomAccessIterator __first,
49 _RandomAccessIterator __last, _Value __identity, _RealBody __real_body, _Reduction __reduction)
50 {
51 // We don't create a nested parallel region in an existing parallel region:
52 // just create tasks.
53 if (omp_in_parallel())
54 {
55 return __pstl::__omp_backend::__parallel_reduce_body(__first, __last, __identity, __real_body, __reduction);
56 }
57
58 // In any case (nested or non-nested) one parallel region is created and only
59 // one thread creates a set of tasks.
60 _Value __res = __identity;
61
62 _PSTL_PRAGMA(omp parallel)
63 _PSTL_PRAGMA(omp single nowait)
64 {
65 __res = __pstl::__omp_backend::__parallel_reduce_body(__first, __last, __identity, __real_body, __reduction);
66 }
67
68 return __res;
69 }
70
71 } // namespace __omp_backend
72 } // namespace __pstl
73 #endif // _PSTL_INTERNAL_OMP_PARALLEL_REDUCE_H
74