OLD | NEW |
1 //===- subzero/src/IceThreading.h - Threading functions ---------*- C++ -*-===// | 1 //===- subzero/src/IceThreading.h - Threading functions ---------*- C++ -*-===// |
2 // | 2 // |
3 // The Subzero Code Generator | 3 // The Subzero Code Generator |
4 // | 4 // |
5 // This file is distributed under the University of Illinois Open Source | 5 // This file is distributed under the University of Illinois Open Source |
6 // License. See LICENSE.TXT for details. | 6 // License. See LICENSE.TXT for details. |
7 // | 7 // |
8 //===----------------------------------------------------------------------===// | 8 //===----------------------------------------------------------------------===// |
9 /// | 9 /// |
10 /// \file | 10 /// \file |
11 /// This file declares threading-related functions. | 11 /// This file declares threading-related functions. |
12 /// | 12 /// |
13 //===----------------------------------------------------------------------===// | 13 //===----------------------------------------------------------------------===// |
14 | 14 |
15 #ifndef SUBZERO_SRC_ICETHREADING_H | 15 #ifndef SUBZERO_SRC_ICETHREADING_H |
16 #define SUBZERO_SRC_ICETHREADING_H | 16 #define SUBZERO_SRC_ICETHREADING_H |
17 | 17 |
18 #include "IceDefs.h" | 18 #include "IceDefs.h" |
19 | 19 |
20 #include <condition_variable> | 20 #include <condition_variable> |
21 #include <mutex> | 21 #include <mutex> |
22 | 22 |
23 namespace Ice { | 23 namespace Ice { |
24 | 24 |
25 /// BoundedProducerConsumerQueue is a work queue that allows multiple | 25 /// BoundedProducerConsumerQueue is a work queue that allows multiple producers |
26 /// producers and multiple consumers. A producer adds entries using | 26 /// and multiple consumers. A producer adds entries using blockingPush(), and |
27 /// blockingPush(), and may block if the queue is "full". A producer | 27 /// may block if the queue is "full". A producer uses notifyEnd() to indicate |
28 /// uses notifyEnd() to indicate that no more entries will be added. A | 28 /// that no more entries will be added. A consumer removes an item using |
29 /// consumer removes an item using blockingPop(), which will return | 29 /// blockingPop(), which will return nullptr if notifyEnd() has been called and |
30 /// nullptr if notifyEnd() has been called and the queue is empty (it | 30 /// the queue is empty (it never returns nullptr if the queue contained any |
31 /// never returns nullptr if the queue contained any items). | 31 /// items). |
32 /// | 32 /// |
33 /// The MaxSize ctor arg controls the maximum size the queue can grow | 33 /// The MaxSize ctor arg controls the maximum size the queue can grow to |
34 /// to (subject to a hard limit of MaxStaticSize-1). The Sequential | 34 /// (subject to a hard limit of MaxStaticSize-1). The Sequential arg indicates |
35 /// arg indicates purely sequential execution in which the single | 35 /// purely sequential execution in which the single thread should never wait(). |
36 /// thread should never wait(). | |
37 /// | 36 /// |
38 /// Two condition variables are used in the implementation. | 37 /// Two condition variables are used in the implementation. GrewOrEnded signals |
39 /// GrewOrEnded signals a waiting worker that a producer has changed | 38 /// a waiting worker that a producer has changed the state of the queue. Shrunk |
40 /// the state of the queue. Shrunk signals a blocked producer that a | 39 /// signals a blocked producer that a consumer has changed the state of the |
41 /// consumer has changed the state of the queue. | 40 /// queue. |
42 /// | 41 /// |
43 /// The methods begin with Sequential-specific code to be most clear. | 42 /// The methods begin with Sequential-specific code to be most clear. The lock |
44 /// The lock and condition variables are not used in the Sequential | 43 /// and condition variables are not used in the Sequential case. |
45 /// case. | |
46 /// | 44 /// |
47 /// Internally, the queue is implemented as a circular array of size | 45 /// Internally, the queue is implemented as a circular array of size |
48 /// MaxStaticSize, where the queue boundaries are denoted by the Front | 46 /// MaxStaticSize, where the queue boundaries are denoted by the Front and Back |
49 /// and Back fields. Front==Back indicates an empty queue. | 47 /// fields. Front==Back indicates an empty queue. |
50 template <typename T, size_t MaxStaticSize = 128> | 48 template <typename T, size_t MaxStaticSize = 128> |
51 class BoundedProducerConsumerQueue { | 49 class BoundedProducerConsumerQueue { |
52 BoundedProducerConsumerQueue() = delete; | 50 BoundedProducerConsumerQueue() = delete; |
53 BoundedProducerConsumerQueue(const BoundedProducerConsumerQueue &) = delete; | 51 BoundedProducerConsumerQueue(const BoundedProducerConsumerQueue &) = delete; |
54 BoundedProducerConsumerQueue & | 52 BoundedProducerConsumerQueue & |
55 operator=(const BoundedProducerConsumerQueue &) = delete; | 53 operator=(const BoundedProducerConsumerQueue &) = delete; |
56 | 54 |
57 public: | 55 public: |
58 BoundedProducerConsumerQueue(bool Sequential, size_t MaxSize = MaxStaticSize) | 56 BoundedProducerConsumerQueue(bool Sequential, size_t MaxSize = MaxStaticSize) |
59 : MaxSize(std::min(MaxSize, MaxStaticSize)), Sequential(Sequential) {} | 57 : MaxSize(std::min(MaxSize, MaxStaticSize)), Sequential(Sequential) {} |
60 void blockingPush(T *Item) { | 58 void blockingPush(T *Item) { |
61 { | 59 { |
62 std::unique_lock<GlobalLockType> L(Lock); | 60 std::unique_lock<GlobalLockType> L(Lock); |
63 // If the work queue is already "full", wait for a consumer to | 61 // If the work queue is already "full", wait for a consumer to grab an |
64 // grab an element and shrink the queue. | 62 // element and shrink the queue. |
65 Shrunk.wait(L, [this] { return size() < MaxSize || Sequential; }); | 63 Shrunk.wait(L, [this] { return size() < MaxSize || Sequential; }); |
66 push(Item); | 64 push(Item); |
67 } | 65 } |
68 GrewOrEnded.notify_one(); | 66 GrewOrEnded.notify_one(); |
69 } | 67 } |
70 T *blockingPop() { | 68 T *blockingPop() { |
71 T *Item = nullptr; | 69 T *Item = nullptr; |
72 bool ShouldNotifyProducer = false; | 70 bool ShouldNotifyProducer = false; |
73 { | 71 { |
74 std::unique_lock<GlobalLockType> L(Lock); | 72 std::unique_lock<GlobalLockType> L(Lock); |
(...skipping 21 matching lines...) Expand all Loading... |
96 "MaxStaticSize must be a power of 2"); | 94 "MaxStaticSize must be a power of 2"); |
97 | 95 |
98 ICE_CACHELINE_BOUNDARY; | 96 ICE_CACHELINE_BOUNDARY; |
99 /// WorkItems and Lock are read/written by all. | 97 /// WorkItems and Lock are read/written by all. |
100 T *WorkItems[MaxStaticSize]; | 98 T *WorkItems[MaxStaticSize]; |
101 ICE_CACHELINE_BOUNDARY; | 99 ICE_CACHELINE_BOUNDARY; |
102 /// Lock guards access to WorkItems, Front, Back, and IsEnded. | 100 /// Lock guards access to WorkItems, Front, Back, and IsEnded. |
103 GlobalLockType Lock; | 101 GlobalLockType Lock; |
104 | 102 |
105 ICE_CACHELINE_BOUNDARY; | 103 ICE_CACHELINE_BOUNDARY; |
106 /// GrewOrEnded is written by the producers and read by the | 104 /// GrewOrEnded is written by the producers and read by the consumers. It is |
107 /// consumers. It is notified (by the producer) when something is | 105 /// notified (by the producer) when something is added to the queue, in case |
108 /// added to the queue, in case consumers are waiting for a non-empty | 106 /// consumers are waiting for a non-empty queue. |
109 /// queue. | |
110 std::condition_variable GrewOrEnded; | 107 std::condition_variable GrewOrEnded; |
111 /// Back is the index into WorkItems[] of where the next element will | 108 /// Back is the index into WorkItems[] of where the next element will be |
112 /// be pushed. (More precisely, Back&MaxStaticSize is the index.) | 109 /// pushed. (More precisely, Back&MaxStaticSize is the index.) It is written |
113 /// It is written by the producers, and read by all via size() and | 110 /// by the producers, and read by all via size() and empty(). |
114 /// empty(). | |
115 size_t Back = 0; | 111 size_t Back = 0; |
116 | 112 |
117 ICE_CACHELINE_BOUNDARY; | 113 ICE_CACHELINE_BOUNDARY; |
118 /// Shrunk is notified (by the consumer) when something is removed | 114 /// Shrunk is notified (by the consumer) when something is removed from the |
119 /// from the queue, in case a producer is waiting for the queue to | 115 /// queue, in case a producer is waiting for the queue to drop below maximum |
120 /// drop below maximum capacity. It is written by the consumers and | 116 /// capacity. It is written by the consumers and read by the producers. |
121 /// read by the producers. | |
122 std::condition_variable Shrunk; | 117 std::condition_variable Shrunk; |
123 /// Front is the index into WorkItems[] of the oldest element, | 118 /// Front is the index into WorkItems[] of the oldest element, i.e. the next |
124 /// i.e. the next to be popped. (More precisely Front&MaxStaticSize | 119 /// to be popped. (More precisely Front&MaxStaticSize is the index.) It is |
125 /// is the index.) It is written by the consumers, and read by all | 120 /// written by the consumers, and read by all via size() and empty(). |
126 /// via size() and empty(). | |
127 size_t Front = 0; | 121 size_t Front = 0; |
128 | 122 |
129 ICE_CACHELINE_BOUNDARY; | 123 ICE_CACHELINE_BOUNDARY; |
130 | 124 |
131 /// MaxSize and Sequential are read by all and written by none. | 125 /// MaxSize and Sequential are read by all and written by none. |
132 const size_t MaxSize; | 126 const size_t MaxSize; |
133 const bool Sequential; | 127 const bool Sequential; |
134 /// IsEnded is read by the consumers, and only written once by the | 128 /// IsEnded is read by the consumers, and only written once by the producer. |
135 /// producer. | |
136 bool IsEnded = false; | 129 bool IsEnded = false; |
137 | 130 |
138 /// The lock must be held when the following methods are called. | 131 /// The lock must be held when the following methods are called. |
139 bool empty() const { return Front == Back; } | 132 bool empty() const { return Front == Back; } |
140 size_t size() const { return Back - Front; } | 133 size_t size() const { return Back - Front; } |
141 void push(T *Item) { | 134 void push(T *Item) { |
142 WorkItems[Back++ & MaxStaticSizeMask] = Item; | 135 WorkItems[Back++ & MaxStaticSizeMask] = Item; |
143 assert(size() <= MaxStaticSize); | 136 assert(size() <= MaxStaticSize); |
144 } | 137 } |
145 T *pop() { | 138 T *pop() { |
146 assert(!empty()); | 139 assert(!empty()); |
147 return WorkItems[Front++ & MaxStaticSizeMask]; | 140 return WorkItems[Front++ & MaxStaticSizeMask]; |
148 } | 141 } |
149 }; | 142 }; |
150 | 143 |
151 /// EmitterWorkItem is a simple wrapper around a pointer that | 144 /// EmitterWorkItem is a simple wrapper around a pointer that represents a work |
152 /// represents a work item to be emitted, i.e. a function or a set of | 145 /// item to be emitted, i.e. a function or a set of global declarations and |
153 /// global declarations and initializers, and it includes a sequence | 146 /// initializers, and it includes a sequence number so that work items can be |
154 /// number so that work items can be emitted in a particular order for | 147 /// emitted in a particular order for deterministic output. It acts like an |
155 /// deterministic output. It acts like an interface class, but instead | 148 /// interface class, but instead of making the classes of interest inherit from |
156 /// of making the classes of interest inherit from EmitterWorkItem, it | 149 /// EmitterWorkItem, it wraps pointers to these classes. Some space is wasted |
157 /// wraps pointers to these classes. Some space is wasted compared to | 150 /// compared to storing the pointers in a union, but not too much due to the |
158 /// storing the pointers in a union, but not too much due to the work | 151 /// work granularity. |
159 /// granularity. | |
160 class EmitterWorkItem { | 152 class EmitterWorkItem { |
161 EmitterWorkItem() = delete; | 153 EmitterWorkItem() = delete; |
162 EmitterWorkItem(const EmitterWorkItem &) = delete; | 154 EmitterWorkItem(const EmitterWorkItem &) = delete; |
163 EmitterWorkItem &operator=(const EmitterWorkItem &) = delete; | 155 EmitterWorkItem &operator=(const EmitterWorkItem &) = delete; |
164 | 156 |
165 public: | 157 public: |
166 /// ItemKind can be one of the following: | 158 /// ItemKind can be one of the following: |
167 /// | 159 /// |
168 /// WI_Nop: No actual work. This is a placeholder to maintain | 160 /// WI_Nop: No actual work. This is a placeholder to maintain sequence numbers |
169 /// sequence numbers in case there is a translation error. | 161 /// in case there is a translation error. |
170 /// | 162 /// |
171 /// WI_GlobalInits: A list of global declarations and initializers. | 163 /// WI_GlobalInits: A list of global declarations and initializers. |
172 /// | 164 /// |
173 /// WI_Asm: A function that has already had emitIAS() called on it. | 165 /// WI_Asm: A function that has already had emitIAS() called on it. The work |
174 /// The work is transferred via the Assembler buffer, and the | 166 /// is transferred via the Assembler buffer, and the originating Cfg has been |
175 /// originating Cfg has been deleted (to recover lots of memory). | 167 /// deleted (to recover lots of memory). |
176 /// | 168 /// |
177 /// WI_Cfg: A Cfg that has not yet had emit() or emitIAS() called on | 169 /// WI_Cfg: A Cfg that has not yet had emit() or emitIAS() called on it. This |
178 /// it. This is only used as a debugging configuration when we want | 170 /// is only used as a debugging configuration when we want to emit "readable" |
179 /// to emit "readable" assembly code, possibly annotated with | 171 /// assembly code, possibly annotated with liveness and other information only |
180 /// liveness and other information only available in the Cfg and not | 172 /// available in the Cfg and not in the Assembler buffer. |
181 /// in the Assembler buffer. | |
182 enum ItemKind { WI_Nop, WI_GlobalInits, WI_Asm, WI_Cfg }; | 173 enum ItemKind { WI_Nop, WI_GlobalInits, WI_Asm, WI_Cfg }; |
183 /// Constructor for a WI_Nop work item. | 174 /// Constructor for a WI_Nop work item. |
184 explicit EmitterWorkItem(uint32_t Seq); | 175 explicit EmitterWorkItem(uint32_t Seq); |
185 /// Constructor for a WI_GlobalInits work item. | 176 /// Constructor for a WI_GlobalInits work item. |
186 EmitterWorkItem(uint32_t Seq, VariableDeclarationList *D); | 177 EmitterWorkItem(uint32_t Seq, VariableDeclarationList *D); |
187 /// Constructor for a WI_Asm work item. | 178 /// Constructor for a WI_Asm work item. |
188 EmitterWorkItem(uint32_t Seq, Assembler *A); | 179 EmitterWorkItem(uint32_t Seq, Assembler *A); |
189 /// Constructor for a WI_Cfg work item. | 180 /// Constructor for a WI_Cfg work item. |
190 EmitterWorkItem(uint32_t Seq, Cfg *F); | 181 EmitterWorkItem(uint32_t Seq, Cfg *F); |
191 uint32_t getSequenceNumber() const { return Sequence; } | 182 uint32_t getSequenceNumber() const { return Sequence; } |
192 ItemKind getKind() const { return Kind; } | 183 ItemKind getKind() const { return Kind; } |
193 void setGlobalInits(std::unique_ptr<VariableDeclarationList> GloblInits); | 184 void setGlobalInits(std::unique_ptr<VariableDeclarationList> GloblInits); |
194 std::unique_ptr<VariableDeclarationList> getGlobalInits(); | 185 std::unique_ptr<VariableDeclarationList> getGlobalInits(); |
195 std::unique_ptr<Assembler> getAsm(); | 186 std::unique_ptr<Assembler> getAsm(); |
196 std::unique_ptr<Cfg> getCfg(); | 187 std::unique_ptr<Cfg> getCfg(); |
197 | 188 |
198 private: | 189 private: |
199 const uint32_t Sequence; | 190 const uint32_t Sequence; |
200 const ItemKind Kind; | 191 const ItemKind Kind; |
201 std::unique_ptr<VariableDeclarationList> GlobalInits; | 192 std::unique_ptr<VariableDeclarationList> GlobalInits; |
202 std::unique_ptr<Assembler> Function; | 193 std::unique_ptr<Assembler> Function; |
203 std::unique_ptr<Cfg> RawFunc; | 194 std::unique_ptr<Cfg> RawFunc; |
204 }; | 195 }; |
205 | 196 |
206 } // end of namespace Ice | 197 } // end of namespace Ice |
207 | 198 |
208 #endif // SUBZERO_SRC_ICETHREADING_H | 199 #endif // SUBZERO_SRC_ICETHREADING_H |
OLD | NEW |