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