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