1//===- llvm/Support/Parallel.h - Parallel algorithms ----------------------===// 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 7//===----------------------------------------------------------------------===// 9#ifndef LLVM_SUPPORT_PARALLEL_H 10#define LLVM_SUPPORT_PARALLEL_H 13#include "llvm/Config/llvm-config.h" 19#include <condition_variable> 27// Strategy for the default executor used by the parallel routines provided by 28// this file. It defaults to using all hardware threads and should be 29// initialized before the first use of parallel routines. 32#if LLVM_ENABLE_THREADS 33#define GET_THREAD_INDEX_IMPL \ 34 if (parallel::strategy.ThreadsRequested == 1) \ 36 assert((threadIndex != UINT_MAX) && \ 37 "getThreadIndex() must be called from a thread created by " \
38 "ThreadPoolExecutor"); \
42// Direct access to thread_local variables from a different DLL isn't 43// possible with Windows Native TLS. 46// Don't access this directly, use the getThreadIndex wrapper. 47externthread_localunsigned threadIndex;
61mutable std::mutex
Mutex;
62mutable std::condition_variable Cond;
67// Ensure at least that sync() was called. 72 std::lock_guard<std::mutex> lock(
Mutex);
77 std::lock_guard<std::mutex> lock(
Mutex);
83 std::unique_lock<std::mutex> lock(
Mutex);
84Cond.wait(lock, [&] {
return Count == 0; });
97// Spawn a task, but does not wait for it to finish. 98// Tasks marked with \p Sequential will be executed 99// exactly in the order which they were spawned. 100voidspawn(std::function<
void()> f);
109#if LLVM_ENABLE_THREADS 113template <
class RandomAccessIterator,
class Comparator>
114RandomAccessIterator medianOf3(RandomAccessIterator Start,
115 RandomAccessIterator
End,
116const Comparator &Comp) {
117 RandomAccessIterator Mid = Start + (std::distance(Start,
End) / 2);
118return Comp(*Start, *(
End - 1))
119 ? (Comp(*Mid, *(
End - 1)) ? (Comp(*Start, *Mid) ? Mid : Start)
121 : (Comp(*Mid, *Start) ? (Comp(*(
End - 1), *Mid) ? Mid :
End - 1)
125template <
class RandomAccessIterator,
class Comparator>
126void parallel_quick_sort(RandomAccessIterator Start, RandomAccessIterator
End,
127const Comparator &Comp, TaskGroup &TG,
size_tDepth) {
128// Do a sequential sort for small inputs. 129if (std::distance(Start,
End) < detail::MinParallelSize ||
Depth == 0) {
135auto Pivot = medianOf3(Start,
End, Comp);
138 Pivot = std::partition(Start,
End - 1, [&Comp,
End](
decltype(*Start) V) {
139return Comp(V, *(
End - 1));
141// Move Pivot to middle of partition. 145 TG.spawn([=, &Comp, &TG] {
146 parallel_quick_sort(Start, Pivot, Comp, TG,
Depth - 1);
148 parallel_quick_sort(Pivot + 1,
End, Comp, TG,
Depth - 1);
151template <
class RandomAccessIterator,
class Comparator>
152void parallel_sort(RandomAccessIterator Start, RandomAccessIterator
End,
153const Comparator &Comp) {
155 parallel_quick_sort(Start,
End, Comp, TG,
159// TaskGroup has a relatively high overhead, so we want to reduce 160// the number of spawn() calls. We'll create up to 1024 tasks here. 161// (Note that 1024 is an arbitrary number. This code probably needs 162// improving to take the number of available cores into account.) 163enum { MaxTasksPerGroup = 1024 };
165template <
classIterTy,
classResultTy,
classReduceFuncTy,
167ResultTy parallel_transform_reduce(IterTy Begin, IterTy
End, ResultTy Init,
169 TransformFuncTy Transform) {
170// Limit the number of tasks to MaxTasksPerGroup to limit job scheduling 171// overhead on large inputs. 172size_t NumInputs = std::distance(Begin,
End);
174return std::move(Init);
175size_t NumTasks = std::min(
static_cast<size_t>(MaxTasksPerGroup), NumInputs);
176 std::vector<ResultTy>
Results(NumTasks, Init);
178// Each task processes either TaskSize or TaskSize+1 inputs. Any inputs 179// remaining after dividing them equally amongst tasks are distributed as 180// one extra input over the first tasks. 182size_t TaskSize = NumInputs / NumTasks;
183size_t RemainingInputs = NumInputs % NumTasks;
184 IterTy TBegin = Begin;
185for (
size_t TaskId = 0; TaskId < NumTasks; ++TaskId) {
186 IterTy TEnd = TBegin + TaskSize + (TaskId < RemainingInputs ? 1 : 0);
187 TG.spawn([=, &Transform, &Reduce, &
Results] {
188// Reduce the result of transformation eagerly within each task. 190for (IterTy It = TBegin; It != TEnd; ++It)
191 R = Reduce(R, Transform(*It));
199// Do a final reduction. There are at most 1024 tasks, so this only adds 200// constant single-threaded overhead for large inputs. Hopefully most 201// reductions are cheaper than the transformation. 202 ResultTy FinalResult = std::move(
Results.front());
203for (ResultTy &PartialResult :
205 FinalResult = Reduce(FinalResult, std::move(PartialResult));
206return std::move(FinalResult);
212}
// namespace parallel 214template <
classRandomAccessIterator,
215classComparator = std::less<
216typename std::iterator_traits<RandomAccessIterator>::value_type>>
218const Comparator &Comp = Comparator()) {
219#if LLVM_ENABLE_THREADS 221 parallel::detail::parallel_sort(Start,
End, Comp);
228voidparallelFor(
size_t Begin,
size_tEnd, function_ref<
void(
size_t)> Fn);
230template <
class IterTy,
class FuncTy>
235template <
classIterTy,
classResultTy,
classReduceFuncTy,
239 TransformFuncTy Transform) {
240#if LLVM_ENABLE_THREADS 242return parallel::detail::parallel_transform_reduce(Begin,
End,
Init, Reduce,
246for (IterTy
I = Begin;
I !=
End; ++
I)
247Init = Reduce(std::move(
Init), Transform(*
I));
248return std::move(
Init);
252template <
classRangeTy,
253classComparator = std::less<
decltype(*std::begin(RangeTy()))>>
258template <
class RangeTy,
class FuncTy>
263template <
classRangeTy,
classResultTy,
classReduceFuncTy,
267 TransformFuncTy Transform) {
272// Parallel for-each, but with error handling. 273template <
class RangeTy,
class FuncTy>
275// The transform_reduce algorithm requires that the initial value be copyable. 276// Error objects are uncopyable. We only need to copy initial success values, 277// so work around this mismatch via the C API. The C API represents success 278// values with a null pointer. The joinErrors discards null values and joins 279// multiple errors into an ErrorList. 285 [&Fn](
auto &&V) {
returnwrap(Fn(V)); }));
290#endif// LLVM_SUPPORT_PARALLEL_H Function Alias Analysis Results
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
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 spawn(std::function< void()> f)
struct LLVMOpaqueError * LLVMErrorRef
Opaque reference to an error instance.
ThreadPoolStrategy strategy
unsigned getThreadIndex()
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())
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)
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)
void parallelForEach(IterTy Begin, IterTy End, FuncTy Fn)
Error parallelForEachError(RangeTy &&R, FuncTy Fn)
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
