blob: 0272a53beb39319d1f8b9d30c7c2b56875e6f35d [file] [log] [blame]
Zachary Turner3a57fbd2017-05-11 00:03:52 +00001//===- llvm/Support/Parallel.cpp - Parallel algorithms --------------------===//
Zachary Turnerf7ca8fc2017-05-05 21:09:26 +00002//
Chandler Carruth2946cd72019-01-19 08:50:56 +00003// 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
Zachary Turnerf7ca8fc2017-05-05 21:09:26 +00006//
7//===----------------------------------------------------------------------===//
8
Zachary Turner3a57fbd2017-05-11 00:03:52 +00009#include "llvm/Support/Parallel.h"
Zachary Turner6083b2b2017-05-05 21:14:55 +000010#include "llvm/Config/llvm-config.h"
Andrew Ng564481a2019-03-16 19:36:29 +000011#include "llvm/Support/ManagedStatic.h"
Nico Weber0f2a48c2018-05-11 15:25:38 +000012
13#if LLVM_ENABLE_THREADS
14
Rafael Espindola8c0ff952017-10-04 20:27:01 +000015#include "llvm/Support/Threading.h"
Zachary Turnerf7ca8fc2017-05-05 21:09:26 +000016
17#include <atomic>
Andrew Ng564481a2019-03-16 19:36:29 +000018#include <future>
Zachary Turnerf7ca8fc2017-05-05 21:09:26 +000019#include <stack>
Rui Ueyama552c2902017-05-05 21:27:30 +000020#include <thread>
Andrew Ng564481a2019-03-16 19:36:29 +000021#include <vector>
Zachary Turnerf7ca8fc2017-05-05 21:09:26 +000022
Fangrui Songf6a62902019-04-25 11:33:30 +000023namespace llvm {
24namespace parallel {
25namespace detail {
Zachary Turnerf7ca8fc2017-05-05 21:09:26 +000026
27namespace {
28
Adrian Prantl5f8f34e42018-05-01 15:54:18 +000029/// An abstract class that takes closures and runs them asynchronously.
Zachary Turnerf7ca8fc2017-05-05 21:09:26 +000030class Executor {
31public:
32 virtual ~Executor() = default;
33 virtual void add(std::function<void()> func) = 0;
34
35 static Executor *getDefaultExecutor();
36};
37
Adrian Prantl5f8f34e42018-05-01 15:54:18 +000038/// An implementation of an Executor that runs closures on a thread pool
Zachary Turnerf7ca8fc2017-05-05 21:09:26 +000039/// in filo order.
40class ThreadPoolExecutor : public Executor {
41public:
Alexandre Ganea8404aeb2020-02-13 22:49:57 -050042 explicit ThreadPoolExecutor(ThreadPoolStrategy S = hardware_concurrency()) {
43 unsigned ThreadCount = S.compute_thread_count();
Zachary Turnerf7ca8fc2017-05-05 21:09:26 +000044 // Spawn all but one of the threads in another thread as spawning threads
45 // can take a while.
Andrew Ng564481a2019-03-16 19:36:29 +000046 Threads.reserve(ThreadCount);
47 Threads.resize(1);
48 std::lock_guard<std::mutex> Lock(Mutex);
Alexandre Ganea8404aeb2020-02-13 22:49:57 -050049 Threads[0] = std::thread([this, ThreadCount, S] {
50 for (unsigned I = 1; I < ThreadCount; ++I) {
51 Threads.emplace_back([=] { work(S, I); });
Andrew Ng564481a2019-03-16 19:36:29 +000052 if (Stop)
53 break;
Zachary Turnerf7ca8fc2017-05-05 21:09:26 +000054 }
Andrew Ng564481a2019-03-16 19:36:29 +000055 ThreadsCreated.set_value();
Alexandre Ganea8404aeb2020-02-13 22:49:57 -050056 work(S, 0);
Andrew Ng564481a2019-03-16 19:36:29 +000057 });
58 }
59
60 void stop() {
61 {
62 std::lock_guard<std::mutex> Lock(Mutex);
63 if (Stop)
64 return;
65 Stop = true;
66 }
67 Cond.notify_all();
68 ThreadsCreated.get_future().wait();
Zachary Turnerf7ca8fc2017-05-05 21:09:26 +000069 }
70
71 ~ThreadPoolExecutor() override {
Andrew Ng564481a2019-03-16 19:36:29 +000072 stop();
73 std::thread::id CurrentThreadId = std::this_thread::get_id();
74 for (std::thread &T : Threads)
75 if (T.get_id() == CurrentThreadId)
76 T.detach();
77 else
78 T.join();
Zachary Turnerf7ca8fc2017-05-05 21:09:26 +000079 }
80
Andrew Ng564481a2019-03-16 19:36:29 +000081 struct Deleter {
82 static void call(void *Ptr) { ((ThreadPoolExecutor *)Ptr)->stop(); }
83 };
84
Zachary Turnerf7ca8fc2017-05-05 21:09:26 +000085 void add(std::function<void()> F) override {
Andrew Ng564481a2019-03-16 19:36:29 +000086 {
87 std::lock_guard<std::mutex> Lock(Mutex);
88 WorkStack.push(F);
89 }
Zachary Turnerf7ca8fc2017-05-05 21:09:26 +000090 Cond.notify_one();
91 }
92
93private:
Alexandre Ganea8404aeb2020-02-13 22:49:57 -050094 void work(ThreadPoolStrategy S, unsigned ThreadID) {
95 S.apply_thread_strategy(ThreadID);
Zachary Turnerf7ca8fc2017-05-05 21:09:26 +000096 while (true) {
97 std::unique_lock<std::mutex> Lock(Mutex);
98 Cond.wait(Lock, [&] { return Stop || !WorkStack.empty(); });
99 if (Stop)
100 break;
101 auto Task = WorkStack.top();
102 WorkStack.pop();
103 Lock.unlock();
104 Task();
105 }
Zachary Turnerf7ca8fc2017-05-05 21:09:26 +0000106 }
107
108 std::atomic<bool> Stop{false};
109 std::stack<std::function<void()>> WorkStack;
110 std::mutex Mutex;
111 std::condition_variable Cond;
Andrew Ng564481a2019-03-16 19:36:29 +0000112 std::promise<void> ThreadsCreated;
113 std::vector<std::thread> Threads;
Zachary Turnerf7ca8fc2017-05-05 21:09:26 +0000114};
115
116Executor *Executor::getDefaultExecutor() {
Andrew Ng564481a2019-03-16 19:36:29 +0000117 // The ManagedStatic enables the ThreadPoolExecutor to be stopped via
118 // llvm_shutdown() which allows a "clean" fast exit, e.g. via _exit(). This
119 // stops the thread pool and waits for any worker thread creation to complete
120 // but does not wait for the threads to finish. The wait for worker thread
121 // creation to complete is important as it prevents intermittent crashes on
122 // Windows due to a race condition between thread creation and process exit.
123 //
124 // The ThreadPoolExecutor will only be destroyed when the static unique_ptr to
125 // it is destroyed, i.e. in a normal full exit. The ThreadPoolExecutor
126 // destructor ensures it has been stopped and waits for worker threads to
127 // finish. The wait is important as it prevents intermittent crashes on
128 // Windows when the process is doing a full exit.
129 //
130 // The Windows crashes appear to only occur with the MSVC static runtimes and
131 // are more frequent with the debug static runtime.
132 //
133 // This also prevents intermittent deadlocks on exit with the MinGW runtime.
134 static ManagedStatic<ThreadPoolExecutor, object_creator<ThreadPoolExecutor>,
135 ThreadPoolExecutor::Deleter>
136 ManagedExec;
137 static std::unique_ptr<ThreadPoolExecutor> Exec(&(*ManagedExec));
138 return Exec.get();
Zachary Turnerf7ca8fc2017-05-05 21:09:26 +0000139}
Nico Weberd4960032019-10-10 18:57:23 +0000140} // namespace
Zachary Turnerf7ca8fc2017-05-05 21:09:26 +0000141
Fangrui Songf6a62902019-04-25 11:33:30 +0000142static std::atomic<int> TaskGroupInstances;
143
144// Latch::sync() called by the dtor may cause one thread to block. If is a dead
145// lock if all threads in the default executor are blocked. To prevent the dead
146// lock, only allow the first TaskGroup to run tasks parallelly. In the scenario
147// of nested parallel_for_each(), only the outermost one runs parallelly.
148TaskGroup::TaskGroup() : Parallel(TaskGroupInstances++ == 0) {}
149TaskGroup::~TaskGroup() { --TaskGroupInstances; }
150
151void TaskGroup::spawn(std::function<void()> F) {
152 if (Parallel) {
153 L.inc();
154 Executor::getDefaultExecutor()->add([&, F] {
155 F();
156 L.dec();
157 });
158 } else {
Zachary Turner0a340ce2017-05-10 17:39:18 +0000159 F();
Fangrui Songf6a62902019-04-25 11:33:30 +0000160 }
Zachary Turnerf7ca8fc2017-05-05 21:09:26 +0000161}
Fangrui Songf6a62902019-04-25 11:33:30 +0000162
163} // namespace detail
164} // namespace parallel
165} // namespace llvm
Nico Weber0f2a48c2018-05-11 15:25:38 +0000166#endif // LLVM_ENABLE_THREADS