Zachary Turner | 3a57fbd | 2017-05-11 00:03:52 +0000 | [diff] [blame] | 1 | //===- llvm/Support/Parallel.cpp - Parallel algorithms --------------------===// |
Zachary Turner | f7ca8fc | 2017-05-05 21:09:26 +0000 | [diff] [blame] | 2 | // |
Chandler Carruth | 2946cd7 | 2019-01-19 08:50:56 +0000 | [diff] [blame] | 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 |
Zachary Turner | f7ca8fc | 2017-05-05 21:09:26 +0000 | [diff] [blame] | 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | |
Zachary Turner | 3a57fbd | 2017-05-11 00:03:52 +0000 | [diff] [blame] | 9 | #include "llvm/Support/Parallel.h" |
Zachary Turner | 6083b2b | 2017-05-05 21:14:55 +0000 | [diff] [blame] | 10 | #include "llvm/Config/llvm-config.h" |
Andrew Ng | 564481a | 2019-03-16 19:36:29 +0000 | [diff] [blame] | 11 | #include "llvm/Support/ManagedStatic.h" |
Nico Weber | 0f2a48c | 2018-05-11 15:25:38 +0000 | [diff] [blame] | 12 | |
| 13 | #if LLVM_ENABLE_THREADS |
| 14 | |
Rafael Espindola | 8c0ff95 | 2017-10-04 20:27:01 +0000 | [diff] [blame] | 15 | #include "llvm/Support/Threading.h" |
Zachary Turner | f7ca8fc | 2017-05-05 21:09:26 +0000 | [diff] [blame] | 16 | |
| 17 | #include <atomic> |
Andrew Ng | 564481a | 2019-03-16 19:36:29 +0000 | [diff] [blame] | 18 | #include <future> |
Zachary Turner | f7ca8fc | 2017-05-05 21:09:26 +0000 | [diff] [blame] | 19 | #include <stack> |
Rui Ueyama | 552c290 | 2017-05-05 21:27:30 +0000 | [diff] [blame] | 20 | #include <thread> |
Andrew Ng | 564481a | 2019-03-16 19:36:29 +0000 | [diff] [blame] | 21 | #include <vector> |
Zachary Turner | f7ca8fc | 2017-05-05 21:09:26 +0000 | [diff] [blame] | 22 | |
Fangrui Song | f6a6290 | 2019-04-25 11:33:30 +0000 | [diff] [blame] | 23 | namespace llvm { |
| 24 | namespace parallel { |
| 25 | namespace detail { |
Zachary Turner | f7ca8fc | 2017-05-05 21:09:26 +0000 | [diff] [blame] | 26 | |
| 27 | namespace { |
| 28 | |
Adrian Prantl | 5f8f34e4 | 2018-05-01 15:54:18 +0000 | [diff] [blame] | 29 | /// An abstract class that takes closures and runs them asynchronously. |
Zachary Turner | f7ca8fc | 2017-05-05 21:09:26 +0000 | [diff] [blame] | 30 | class Executor { |
| 31 | public: |
| 32 | virtual ~Executor() = default; |
| 33 | virtual void add(std::function<void()> func) = 0; |
| 34 | |
| 35 | static Executor *getDefaultExecutor(); |
| 36 | }; |
| 37 | |
Adrian Prantl | 5f8f34e4 | 2018-05-01 15:54:18 +0000 | [diff] [blame] | 38 | /// An implementation of an Executor that runs closures on a thread pool |
Zachary Turner | f7ca8fc | 2017-05-05 21:09:26 +0000 | [diff] [blame] | 39 | /// in filo order. |
| 40 | class ThreadPoolExecutor : public Executor { |
| 41 | public: |
Alexandre Ganea | 8404aeb | 2020-02-13 22:49:57 -0500 | [diff] [blame] | 42 | explicit ThreadPoolExecutor(ThreadPoolStrategy S = hardware_concurrency()) { |
| 43 | unsigned ThreadCount = S.compute_thread_count(); |
Zachary Turner | f7ca8fc | 2017-05-05 21:09:26 +0000 | [diff] [blame] | 44 | // Spawn all but one of the threads in another thread as spawning threads |
| 45 | // can take a while. |
Andrew Ng | 564481a | 2019-03-16 19:36:29 +0000 | [diff] [blame] | 46 | Threads.reserve(ThreadCount); |
| 47 | Threads.resize(1); |
| 48 | std::lock_guard<std::mutex> Lock(Mutex); |
Alexandre Ganea | 8404aeb | 2020-02-13 22:49:57 -0500 | [diff] [blame] | 49 | Threads[0] = std::thread([this, ThreadCount, S] { |
| 50 | for (unsigned I = 1; I < ThreadCount; ++I) { |
| 51 | Threads.emplace_back([=] { work(S, I); }); |
Andrew Ng | 564481a | 2019-03-16 19:36:29 +0000 | [diff] [blame] | 52 | if (Stop) |
| 53 | break; |
Zachary Turner | f7ca8fc | 2017-05-05 21:09:26 +0000 | [diff] [blame] | 54 | } |
Andrew Ng | 564481a | 2019-03-16 19:36:29 +0000 | [diff] [blame] | 55 | ThreadsCreated.set_value(); |
Alexandre Ganea | 8404aeb | 2020-02-13 22:49:57 -0500 | [diff] [blame] | 56 | work(S, 0); |
Andrew Ng | 564481a | 2019-03-16 19:36:29 +0000 | [diff] [blame] | 57 | }); |
| 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 Turner | f7ca8fc | 2017-05-05 21:09:26 +0000 | [diff] [blame] | 69 | } |
| 70 | |
| 71 | ~ThreadPoolExecutor() override { |
Andrew Ng | 564481a | 2019-03-16 19:36:29 +0000 | [diff] [blame] | 72 | 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 Turner | f7ca8fc | 2017-05-05 21:09:26 +0000 | [diff] [blame] | 79 | } |
| 80 | |
Andrew Ng | 564481a | 2019-03-16 19:36:29 +0000 | [diff] [blame] | 81 | struct Deleter { |
| 82 | static void call(void *Ptr) { ((ThreadPoolExecutor *)Ptr)->stop(); } |
| 83 | }; |
| 84 | |
Zachary Turner | f7ca8fc | 2017-05-05 21:09:26 +0000 | [diff] [blame] | 85 | void add(std::function<void()> F) override { |
Andrew Ng | 564481a | 2019-03-16 19:36:29 +0000 | [diff] [blame] | 86 | { |
| 87 | std::lock_guard<std::mutex> Lock(Mutex); |
| 88 | WorkStack.push(F); |
| 89 | } |
Zachary Turner | f7ca8fc | 2017-05-05 21:09:26 +0000 | [diff] [blame] | 90 | Cond.notify_one(); |
| 91 | } |
| 92 | |
| 93 | private: |
Alexandre Ganea | 8404aeb | 2020-02-13 22:49:57 -0500 | [diff] [blame] | 94 | void work(ThreadPoolStrategy S, unsigned ThreadID) { |
| 95 | S.apply_thread_strategy(ThreadID); |
Zachary Turner | f7ca8fc | 2017-05-05 21:09:26 +0000 | [diff] [blame] | 96 | 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 Turner | f7ca8fc | 2017-05-05 21:09:26 +0000 | [diff] [blame] | 106 | } |
| 107 | |
| 108 | std::atomic<bool> Stop{false}; |
| 109 | std::stack<std::function<void()>> WorkStack; |
| 110 | std::mutex Mutex; |
| 111 | std::condition_variable Cond; |
Andrew Ng | 564481a | 2019-03-16 19:36:29 +0000 | [diff] [blame] | 112 | std::promise<void> ThreadsCreated; |
| 113 | std::vector<std::thread> Threads; |
Zachary Turner | f7ca8fc | 2017-05-05 21:09:26 +0000 | [diff] [blame] | 114 | }; |
| 115 | |
| 116 | Executor *Executor::getDefaultExecutor() { |
Andrew Ng | 564481a | 2019-03-16 19:36:29 +0000 | [diff] [blame] | 117 | // 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 Turner | f7ca8fc | 2017-05-05 21:09:26 +0000 | [diff] [blame] | 139 | } |
Nico Weber | d496003 | 2019-10-10 18:57:23 +0000 | [diff] [blame] | 140 | } // namespace |
Zachary Turner | f7ca8fc | 2017-05-05 21:09:26 +0000 | [diff] [blame] | 141 | |
Fangrui Song | f6a6290 | 2019-04-25 11:33:30 +0000 | [diff] [blame] | 142 | static 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. |
| 148 | TaskGroup::TaskGroup() : Parallel(TaskGroupInstances++ == 0) {} |
| 149 | TaskGroup::~TaskGroup() { --TaskGroupInstances; } |
| 150 | |
| 151 | void 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 Turner | 0a340ce | 2017-05-10 17:39:18 +0000 | [diff] [blame] | 159 | F(); |
Fangrui Song | f6a6290 | 2019-04-25 11:33:30 +0000 | [diff] [blame] | 160 | } |
Zachary Turner | f7ca8fc | 2017-05-05 21:09:26 +0000 | [diff] [blame] | 161 | } |
Fangrui Song | f6a6290 | 2019-04-25 11:33:30 +0000 | [diff] [blame] | 162 | |
| 163 | } // namespace detail |
| 164 | } // namespace parallel |
| 165 | } // namespace llvm |
Nico Weber | 0f2a48c | 2018-05-11 15:25:38 +0000 | [diff] [blame] | 166 | #endif // LLVM_ENABLE_THREADS |