LLVM: include/llvm/Support/Parallel.h Source File (original) (raw)
1
2
3
4
5
6
7
8
9#ifndef LLVM_SUPPORT_PARALLEL_H
10#define LLVM_SUPPORT_PARALLEL_H
11
13#include "llvm/Config/llvm-config.h"
18
19#include
20#include <condition_variable>
21#include
22#include
23
24namespace llvm {
25
27
28
29
30
32
33#if LLVM_ENABLE_THREADS
34#define GET_THREAD_INDEX_IMPL \
35 if (parallel::strategy.ThreadsRequested == 1) \
36 return 0; \
37 assert((threadIndex != UINT_MAX) && \
38 "getThreadIndex() must be called from a thread created by " \
39 "ThreadPoolExecutor"); \
40 return threadIndex;
41
42#ifdef _WIN32
43
44
46#else
47
48LLVM_ABI extern thread_local unsigned threadIndex;
49
50inline unsigned getThreadIndex() { GET_THREAD_INDEX_IMPL; }
51#endif
52
54#else
57#endif
58
62 mutable std::mutex Mutex;
63 mutable std::condition_variable Cond;
64
65public:
71
73 std::lock_guardstd::mutex lock(Mutex);
74 ++Count;
75 }
76
78 std::lock_guardstd::mutex lock(Mutex);
79 if (--Count == 0)
80 Cond.notify_all();
81 }
82
84 std::unique_lockstd::mutex lock(Mutex);
85 Cond.wait(lock, [&] { return Count == 0; });
86 }
87};
88}
89
92 bool Parallel;
93
94public:
97
98
99
100
102
103 void sync() const { L.sync(); }
104
106};
107
109
110#if LLVM_ENABLE_THREADS
111const ptrdiff_t MinParallelSize = 1024;
112
113
114template <class RandomAccessIterator, class Comparator>
115RandomAccessIterator medianOf3(RandomAccessIterator Start,
116 RandomAccessIterator End,
117 const Comparator &Comp) {
118 RandomAccessIterator Mid = Start + (std::distance(Start, End) / 2);
119 return Comp(*Start, *(End - 1))
120 ? (Comp(*Mid, *(End - 1)) ? (Comp(*Start, *Mid) ? Mid : Start)
121 : End - 1)
122 : (Comp(*Mid, *Start) ? (Comp(*(End - 1), *Mid) ? Mid : End - 1)
123 : Start);
124}
125
126template <class RandomAccessIterator, class Comparator>
127void parallel_quick_sort(RandomAccessIterator Start, RandomAccessIterator End,
128 const Comparator &Comp, TaskGroup &TG, size_t Depth) {
129
130 if (std::distance(Start, End) < detail::MinParallelSize || Depth == 0) {
132 return;
133 }
134
135
136 auto Pivot = medianOf3(Start, End, Comp);
137
139 Pivot = std::partition(Start, End - 1, [&Comp, End](decltype(*Start) V) {
140 return Comp(V, *(End - 1));
141 });
142
144
145
146 TG.spawn([=, &Comp, &TG] {
147 parallel_quick_sort(Start, Pivot, Comp, TG, Depth - 1);
148 });
149 parallel_quick_sort(Pivot + 1, End, Comp, TG, Depth - 1);
150}
151
152template <class RandomAccessIterator, class Comparator>
153void parallel_sort(RandomAccessIterator Start, RandomAccessIterator End,
154 const Comparator &Comp) {
155 TaskGroup TG;
156 parallel_quick_sort(Start, End, Comp, TG,
158}
159
160
161
162
163
164enum { MaxTasksPerGroup = 1024 };
165
166template <class IterTy, class ResultTy, class ReduceFuncTy,
167 class TransformFuncTy>
168ResultTy parallel_transform_reduce(IterTy Begin, IterTy End, ResultTy Init,
169 ReduceFuncTy Reduce,
170 TransformFuncTy Transform) {
171
172
173 size_t NumInputs = std::distance(Begin, End);
174 if (NumInputs == 0)
175 return std::move(Init);
176 size_t NumTasks = std::min(static_cast<size_t>(MaxTasksPerGroup), NumInputs);
177 std::vector Results(NumTasks, Init);
178 {
179
180
181
182 TaskGroup TG;
183 size_t TaskSize = NumInputs / NumTasks;
184 size_t RemainingInputs = NumInputs % NumTasks;
185 IterTy TBegin = Begin;
186 for (size_t TaskId = 0; TaskId < NumTasks; ++TaskId) {
187 IterTy TEnd = TBegin + TaskSize + (TaskId < RemainingInputs ? 1 : 0);
188 TG.spawn([=, &Transform, &Reduce, &Results] {
189
190 ResultTy R = Init;
191 for (IterTy It = TBegin; It != TEnd; ++It)
192 R = Reduce(R, Transform(*It));
194 });
195 TBegin = TEnd;
196 }
197 assert(TBegin == End);
198 }
199
200
201
202
203 ResultTy FinalResult = std::move(Results.front());
204 for (ResultTy &PartialResult :
206 FinalResult = Reduce(FinalResult, std::move(PartialResult));
207 return std::move(FinalResult);
208}
209
210#endif
211
212}
213}
214
215template <class RandomAccessIterator,
216 class Comparator = std::less<
217 typename std::iterator_traits::value_type>>
218void parallelSort(RandomAccessIterator Start, RandomAccessIterator End,
219 const Comparator &Comp = Comparator()) {
220#if LLVM_ENABLE_THREADS
222 parallel::detail::parallel_sort(Start, End, Comp);
223 return;
224 }
225#endif
227}
228
230 function_ref<void(size_t)> Fn);
231
232template <class IterTy, class FuncTy>
234 parallelFor(0, End - Begin, [&](size_t I) { Fn(Begin[I]); });
235}
236
237template <class IterTy, class ResultTy, class ReduceFuncTy,
238 class TransformFuncTy>
240 ReduceFuncTy Reduce,
241 TransformFuncTy Transform) {
242#if LLVM_ENABLE_THREADS
244 return parallel::detail::parallel_transform_reduce(Begin, End, Init, Reduce,
245 Transform);
246 }
247#endif
248 for (IterTy I = Begin; I != End; ++I)
249 Init = Reduce(std::move(Init), Transform(*I));
250 return std::move(Init);
251}
252
253
254template <class RangeTy,
255 class Comparator = std::less<decltype(*std::begin(RangeTy()))>>
259
260template <class RangeTy, class FuncTy>
264
265template <class RangeTy, class ResultTy, class ReduceFuncTy,
266 class TransformFuncTy>
268 ReduceFuncTy Reduce,
269 TransformFuncTy Transform) {
271 Transform);
272}
273
274
275template <class RangeTy, class FuncTy>
277
278
279
280
281
286 },
287 [&Fn](auto &&V) { return wrap(Fn(V)); }));
288}
289
290}
291
292#endif
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
Function Alias Analysis Results
Lightweight error class with error context and mandatory checking.
static ErrorSuccess success()
Create a success value.
This tells how a thread pool will be used.
void sync() const
Definition Parallel.h:103
LLVM_ABI void spawn(std::function< void()> f)
bool isParallel() const
Definition Parallel.h:105
void inc()
Definition Parallel.h:72
void dec()
Definition Parallel.h:77
void sync() const
Definition Parallel.h:83
Latch(uint32_t Count=0)
Definition Parallel.h:66
~Latch()
Definition Parallel.h:67
struct LLVMOpaqueError * LLVMErrorRef
Opaque reference to an error instance.
LLVM_ABI ThreadPoolStrategy strategy
unsigned getThreadIndex()
Definition Parallel.h:55
size_t getThreadCount()
Definition Parallel.h:56
This is an optimization pass for GlobalISel generic memory operations.
unsigned Log2_64(uint64_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
void parallelSort(RandomAccessIterator Start, RandomAccessIterator End, const Comparator &Comp=Comparator())
Definition Parallel.h:218
Error joinErrors(Error E1, Error E2)
Concatenate errors.
void sort(IteratorTy Start, IteratorTy End)
MutableArrayRef(T &OneElt) -> MutableArrayRef< T >
Attribute unwrap(LLVMAttributeRef Attr)
LLVMAttributeRef wrap(Attribute Attr)
LLVM_ABI void parallelFor(size_t Begin, size_t End, function_ref< void(size_t)> Fn)
ResultTy parallelTransformReduce(IterTy Begin, IterTy End, ResultTy Init, ReduceFuncTy Reduce, TransformFuncTy Transform)
Definition Parallel.h:239
void parallelForEach(IterTy Begin, IterTy End, FuncTy Fn)
Definition Parallel.h:233
Error parallelForEachError(RangeTy &&R, FuncTy Fn)
Definition Parallel.h:276
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.