| //===- subzero/src/IceThreading.h - Threading functions ---------*- C++ -*-===// |
| // |
| // The Subzero Code Generator |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| /// |
| /// \file |
| /// This file declares threading-related functions. |
| /// |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef SUBZERO_SRC_ICETHREADING_H |
| #define SUBZERO_SRC_ICETHREADING_H |
| |
| #include "IceDefs.h" |
| |
| #include <condition_variable> |
| #include <mutex> |
| |
| namespace Ice { |
| |
| /// BoundedProducerConsumerQueue is a work queue that allows multiple producers |
| /// and multiple consumers. A producer adds entries using blockingPush(), and |
| /// may block if the queue is "full". A producer uses notifyEnd() to indicate |
| /// that no more entries will be added. A consumer removes an item using |
| /// blockingPop(), which will return nullptr if notifyEnd() has been called and |
| /// the queue is empty (it never returns nullptr if the queue contained any |
| /// items). |
| /// |
| /// The MaxSize ctor arg controls the maximum size the queue can grow to |
| /// (subject to a hard limit of MaxStaticSize-1). The Sequential arg indicates |
| /// purely sequential execution in which the single thread should never wait(). |
| /// |
| /// Two condition variables are used in the implementation. GrewOrEnded signals |
| /// a waiting worker that a producer has changed the state of the queue. Shrunk |
| /// signals a blocked producer that a consumer has changed the state of the |
| /// queue. |
| /// |
| /// The methods begin with Sequential-specific code to be most clear. The lock |
| /// and condition variables are not used in the Sequential case. |
| /// |
| /// Internally, the queue is implemented as a circular array of size |
| /// MaxStaticSize, where the queue boundaries are denoted by the Front and Back |
| /// fields. Front==Back indicates an empty queue. |
| template <typename T, size_t MaxStaticSize = 128> |
| class BoundedProducerConsumerQueue { |
| BoundedProducerConsumerQueue() = delete; |
| BoundedProducerConsumerQueue(const BoundedProducerConsumerQueue &) = delete; |
| BoundedProducerConsumerQueue & |
| operator=(const BoundedProducerConsumerQueue &) = delete; |
| |
| public: |
| BoundedProducerConsumerQueue(bool Sequential, size_t MaxSize = MaxStaticSize) |
| : MaxSize(std::min(MaxSize, MaxStaticSize)), Sequential(Sequential) {} |
| void blockingPush(T *Item) { |
| { |
| std::unique_lock<GlobalLockType> L(Lock); |
| // If the work queue is already "full", wait for a consumer to grab an |
| // element and shrink the queue. |
| Shrunk.wait(L, [this] { return size() < MaxSize || Sequential; }); |
| push(Item); |
| } |
| GrewOrEnded.notify_one(); |
| } |
| T *blockingPop() { |
| T *Item = nullptr; |
| bool ShouldNotifyProducer = false; |
| { |
| std::unique_lock<GlobalLockType> L(Lock); |
| GrewOrEnded.wait(L, [this] { return IsEnded || !empty() || Sequential; }); |
| if (!empty()) { |
| Item = pop(); |
| ShouldNotifyProducer = !IsEnded; |
| } |
| } |
| if (ShouldNotifyProducer) |
| Shrunk.notify_one(); |
| return Item; |
| } |
| void notifyEnd() { |
| { |
| std::lock_guard<GlobalLockType> L(Lock); |
| IsEnded = true; |
| } |
| GrewOrEnded.notify_all(); |
| } |
| |
| private: |
| const static size_t MaxStaticSizeMask = MaxStaticSize - 1; |
| static_assert(!(MaxStaticSize & (MaxStaticSize - 1)), |
| "MaxStaticSize must be a power of 2"); |
| |
| ICE_CACHELINE_BOUNDARY; |
| /// WorkItems and Lock are read/written by all. |
| T *WorkItems[MaxStaticSize]; |
| ICE_CACHELINE_BOUNDARY; |
| /// Lock guards access to WorkItems, Front, Back, and IsEnded. |
| GlobalLockType Lock; |
| |
| ICE_CACHELINE_BOUNDARY; |
| /// GrewOrEnded is written by the producers and read by the consumers. It is |
| /// notified (by the producer) when something is added to the queue, in case |
| /// consumers are waiting for a non-empty queue. |
| std::condition_variable GrewOrEnded; |
| /// Back is the index into WorkItems[] of where the next element will be |
| /// pushed. (More precisely, Back&MaxStaticSize is the index.) It is written |
| /// by the producers, and read by all via size() and empty(). |
| size_t Back = 0; |
| |
| ICE_CACHELINE_BOUNDARY; |
| /// Shrunk is notified (by the consumer) when something is removed from the |
| /// queue, in case a producer is waiting for the queue to drop below maximum |
| /// capacity. It is written by the consumers and read by the producers. |
| std::condition_variable Shrunk; |
| /// Front is the index into WorkItems[] of the oldest element, i.e. the next |
| /// to be popped. (More precisely Front&MaxStaticSize is the index.) It is |
| /// written by the consumers, and read by all via size() and empty(). |
| size_t Front = 0; |
| |
| ICE_CACHELINE_BOUNDARY; |
| |
| /// MaxSize and Sequential are read by all and written by none. |
| const size_t MaxSize; |
| const bool Sequential; |
| /// IsEnded is read by the consumers, and only written once by the producer. |
| bool IsEnded = false; |
| |
| /// The lock must be held when the following methods are called. |
| bool empty() const { return Front == Back; } |
| size_t size() const { return Back - Front; } |
| void push(T *Item) { |
| WorkItems[Back++ & MaxStaticSizeMask] = Item; |
| assert(size() <= MaxStaticSize); |
| } |
| T *pop() { |
| assert(!empty()); |
| return WorkItems[Front++ & MaxStaticSizeMask]; |
| } |
| }; |
| |
| /// EmitterWorkItem is a simple wrapper around a pointer that represents a work |
| /// item to be emitted, i.e. a function or a set of global declarations and |
| /// initializers, and it includes a sequence number so that work items can be |
| /// emitted in a particular order for deterministic output. It acts like an |
| /// interface class, but instead of making the classes of interest inherit from |
| /// EmitterWorkItem, it wraps pointers to these classes. Some space is wasted |
| /// compared to storing the pointers in a union, but not too much due to the |
| /// work granularity. |
| class EmitterWorkItem { |
| EmitterWorkItem() = delete; |
| EmitterWorkItem(const EmitterWorkItem &) = delete; |
| EmitterWorkItem &operator=(const EmitterWorkItem &) = delete; |
| |
| public: |
| /// ItemKind can be one of the following: |
| /// |
| /// WI_Nop: No actual work. This is a placeholder to maintain sequence numbers |
| /// in case there is a translation error. |
| /// |
| /// WI_GlobalInits: A list of global declarations and initializers. |
| /// |
| /// WI_Asm: A function that has already had emitIAS() called on it. The work |
| /// is transferred via the Assembler buffer, and the originating Cfg has been |
| /// deleted (to recover lots of memory). |
| /// |
| /// WI_Cfg: A Cfg that has not yet had emit() or emitIAS() called on it. This |
| /// is only used as a debugging configuration when we want to emit "readable" |
| /// assembly code, possibly annotated with liveness and other information only |
| /// available in the Cfg and not in the Assembler buffer. |
| enum ItemKind { WI_Nop, WI_GlobalInits, WI_Asm, WI_Cfg }; |
| /// Constructor for a WI_Nop work item. |
| explicit EmitterWorkItem(uint32_t Seq); |
| /// Constructor for a WI_GlobalInits work item. |
| EmitterWorkItem(uint32_t Seq, VariableDeclarationList *D); |
| /// Constructor for a WI_Asm work item. |
| EmitterWorkItem(uint32_t Seq, Assembler *A); |
| /// Constructor for a WI_Cfg work item. |
| EmitterWorkItem(uint32_t Seq, Cfg *F); |
| uint32_t getSequenceNumber() const { return Sequence; } |
| ItemKind getKind() const { return Kind; } |
| void setGlobalInits(std::unique_ptr<VariableDeclarationList> GloblInits); |
| std::unique_ptr<VariableDeclarationList> getGlobalInits(); |
| std::unique_ptr<Assembler> getAsm(); |
| std::unique_ptr<Cfg> getCfg(); |
| |
| private: |
| const uint32_t Sequence; |
| const ItemKind Kind; |
| std::unique_ptr<VariableDeclarationList> GlobalInits; |
| std::unique_ptr<Assembler> Function; |
| std::unique_ptr<Cfg> RawFunc; |
| }; |
| |
| } // end of namespace Ice |
| |
| #endif // SUBZERO_SRC_ICETHREADING_H |