9 #ifndef LLVM_SUPPORT_PARALLEL_H
10 #define LLVM_SUPPORT_PARALLEL_H
13 #include "llvm/Config/llvm-config.h"
19 #include <condition_variable>
34 #if LLVM_ENABLE_THREADS
38 mutable std::mutex
Mutex;
39 mutable std::condition_variable Cond;
49 std::lock_guard<std::mutex> lock(
Mutex);
54 std::lock_guard<std::mutex> lock(
Mutex);
60 std::unique_lock<std::mutex> lock(
Mutex);
61 Cond.wait(lock, [&] {
return Count == 0; });
81 template <
class RandomAccessIterator,
class Comparator>
82 RandomAccessIterator
medianOf3(RandomAccessIterator Start,
83 RandomAccessIterator End,
84 const Comparator &Comp) {
85 RandomAccessIterator Mid = Start + (std::distance(Start, End) / 2);
86 return Comp(*Start, *(End - 1))
87 ? (Comp(*Mid, *(End - 1)) ? (Comp(*Start, *Mid) ? Mid : Start)
89 : (Comp(*Mid, *Start) ? (Comp(*(End - 1), *Mid) ? Mid : End - 1)
93 template <
class RandomAccessIterator,
class Comparator>
95 const Comparator &Comp,
TaskGroup &TG,
size_t Depth) {
103 auto Pivot =
medianOf3(Start, End, Comp);
106 Pivot =
std::partition(Start, End - 1, [&Comp, End](decltype(*Start) V) {
107 return Comp(V, *(End - 1));
113 TG.
spawn([=, &Comp, &TG] {
119 template <
class RandomAccessIterator,
class Comparator>
121 const Comparator &Comp) {
133 template <
class IterTy,
class ResultTy,
class ReduceFuncTy,
134 class TransformFuncTy>
137 TransformFuncTy Transform) {
140 size_t NumInputs = std::distance(Begin, End);
150 size_t TaskSize = NumInputs / NumTasks;
151 size_t RemainingInputs = NumInputs % NumTasks;
152 IterTy TBegin = Begin;
153 for (
size_t TaskId = 0; TaskId < NumTasks; ++TaskId) {
154 IterTy TEnd = TBegin + TaskSize + (TaskId < RemainingInputs ? 1 : 0);
158 for (IterTy It = TBegin; It != TEnd; ++It)
159 R = Reduce(R, Transform(*It));
171 for (ResultTy &PartialResult :
173 FinalResult = Reduce(FinalResult,
std::move(PartialResult));
182 template <
class RandomAccessIterator,
184 typename std::iterator_traits<RandomAccessIterator>::value_type>>
185 void parallelSort(RandomAccessIterator Start, RandomAccessIterator End,
186 const Comparator &Comp = Comparator()) {
187 #if LLVM_ENABLE_THREADS
196 void parallelForEachN(
size_t Begin,
size_t End, function_ref<
void(
size_t)> Fn);
198 template <
class IterTy,
class FuncTy>
203 template <
class IterTy,
class ResultTy,
class ReduceFuncTy,
204 class TransformFuncTy>
207 TransformFuncTy Transform) {
208 #if LLVM_ENABLE_THREADS
214 for (IterTy
I = Begin;
I != End; ++
I)
220 template <
class RangeTy,
222 void parallelSort(RangeTy &&R,
const Comparator &Comp = Comparator()) {
226 template <
class RangeTy,
class FuncTy>
231 template <
class RangeTy,
class ResultTy,
class ReduceFuncTy,
232 class TransformFuncTy>
235 TransformFuncTy Transform) {
241 template <
class RangeTy,
class FuncTy>
253 [&Fn](
auto &&V) {
return wrap(Fn(V)); }));
258 #endif // LLVM_SUPPORT_PARALLEL_H