Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(140)

Side by Side Diff: src/IceUtils.h

Issue 916653004: Subzero: Emit functions and global initializers in a separate thread. (Closed) Base URL: https://chromium.googlesource.com/native_client/pnacl-subzero.git@master
Patch Set: Const change Created 5 years, 10 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/IceTranslator.cpp ('k') | src/PNaClTranslator.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 //===- subzero/src/IceUtils.h - Utility functions ---------------*- C++ -*-===// 1 //===- subzero/src/IceUtils.h - Utility 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 some utility functions. 10 // This file declares some utility functions.
11 // 11 //
12 //===----------------------------------------------------------------------===// 12 //===----------------------------------------------------------------------===//
13 13
14 #ifndef SUBZERO_SRC_ICEUTILS_H 14 #ifndef SUBZERO_SRC_ICEUTILS_H
15 #define SUBZERO_SRC_ICEUTILS_H 15 #define SUBZERO_SRC_ICEUTILS_H
16
17 #include <climits> 16 #include <climits>
18 #include <condition_variable>
19 17
20 namespace Ice { 18 namespace Ice {
21 19
22 // Similar to bit_cast, but allows copying from types of unrelated 20 // Similar to bit_cast, but allows copying from types of unrelated
23 // sizes. This method was introduced to enable the strict aliasing 21 // sizes. This method was introduced to enable the strict aliasing
24 // optimizations of GCC 4.4. Basically, GCC mindlessly relies on 22 // optimizations of GCC 4.4. Basically, GCC mindlessly relies on
25 // obscure details in the C++ standard that make reinterpret_cast 23 // obscure details in the C++ standard that make reinterpret_cast
26 // virtually useless. 24 // virtually useless.
27 template <class D, class S> inline D bit_copy(const S &source) { 25 template <class D, class S> inline D bit_copy(const S &source) {
28 D destination; 26 D destination;
(...skipping 27 matching lines...) Expand all
56 54
57 static inline uint64_t OffsetToAlignment(uint64_t Pos, uint64_t Align) { 55 static inline uint64_t OffsetToAlignment(uint64_t Pos, uint64_t Align) {
58 assert(llvm::isPowerOf2_64(Align)); 56 assert(llvm::isPowerOf2_64(Align));
59 uint64_t Mod = Pos & (Align - 1); 57 uint64_t Mod = Pos & (Align - 1);
60 if (Mod == 0) 58 if (Mod == 0)
61 return 0; 59 return 0;
62 return Align - Mod; 60 return Align - Mod;
63 } 61 }
64 }; 62 };
65 63
66 // BoundedProducerConsumerQueue is a work queue that allows multiple
67 // producers and multiple consumers. A producer adds entries using
68 // blockingPush(), and may block if the queue is "full". A producer
69 // uses notifyEnd() to indicate that no more entries will be added. A
70 // consumer removes an item using blockingPop(), which will return
71 // nullptr if notifyEnd() has been called and the queue is empty (it
72 // never returns nullptr if the queue contained any items).
73 //
74 // The MaxSize ctor arg controls the maximum size the queue can grow
75 // to (subject to a hard limit of MaxStaticSize-1). The Sequential
76 // arg indicates purely sequential execution in which the single
77 // thread should never wait().
78 //
79 // Two condition variables are used in the implementation.
80 // GrewOrEnded signals a waiting worker that a producer has changed
81 // the state of the queue. Shrunk signals a blocked producer that a
82 // consumer has changed the state of the queue.
83 //
84 // The methods begin with Sequential-specific code to be most clear.
85 // The lock and condition variables are not used in the Sequential
86 // case.
87 //
88 // Internally, the queue is implemented as a circular array of size
89 // MaxStaticSize, where the queue boundaries are denoted by the Front
90 // and Back fields. Front==Back indicates an empty queue.
91 template <typename T, size_t MaxStaticSize = 128>
92 class BoundedProducerConsumerQueue {
93 BoundedProducerConsumerQueue() = delete;
94 BoundedProducerConsumerQueue(const BoundedProducerConsumerQueue &) = delete;
95 BoundedProducerConsumerQueue &
96 operator=(const BoundedProducerConsumerQueue &) = delete;
97
98 public:
99 BoundedProducerConsumerQueue(size_t MaxSize, bool Sequential)
100 : Back(0), Front(0), MaxSize(std::min(MaxSize, MaxStaticSize)),
101 Sequential(Sequential), IsEnded(false) {}
102 void blockingPush(T *Item) {
103 {
104 std::unique_lock<GlobalLockType> L(Lock);
105 // If the work queue is already "full", wait for a consumer to
106 // grab an element and shrink the queue.
107 Shrunk.wait(L, [this] { return size() < MaxSize || Sequential; });
108 push(Item);
109 }
110 GrewOrEnded.notify_one();
111 }
112 T *blockingPop() {
113 T *Item = nullptr;
114 bool ShouldNotifyProducer = false;
115 {
116 std::unique_lock<GlobalLockType> L(Lock);
117 GrewOrEnded.wait(L, [this] { return IsEnded || !empty() || Sequential; });
118 if (!empty()) {
119 Item = pop();
120 ShouldNotifyProducer = !IsEnded;
121 }
122 }
123 if (ShouldNotifyProducer)
124 Shrunk.notify_one();
125 return Item;
126 }
127 void notifyEnd() {
128 {
129 std::lock_guard<GlobalLockType> L(Lock);
130 IsEnded = true;
131 }
132 GrewOrEnded.notify_all();
133 }
134
135 private:
136 const static size_t MaxStaticSizeMask = MaxStaticSize - 1;
137 static_assert(!(MaxStaticSize & (MaxStaticSize - 1)),
138 "MaxStaticSize must be a power of 2");
139
140 // WorkItems and Lock are read/written by all.
141 ICE_CACHELINE_BOUNDARY;
142 T *WorkItems[MaxStaticSize];
143 ICE_CACHELINE_BOUNDARY;
144 // Lock guards access to WorkItems, Front, Back, and IsEnded.
145 GlobalLockType Lock;
146
147 ICE_CACHELINE_BOUNDARY;
148 // GrewOrEnded is written by the producers and read by the
149 // consumers. It is notified (by the producer) when something is
150 // added to the queue, in case consumers are waiting for a non-empty
151 // queue.
152 std::condition_variable GrewOrEnded;
153 // Back is the index into WorkItems[] of where the next element will
154 // be pushed. (More precisely, Back&MaxStaticSize is the index.)
155 // It is written by the producers, and read by all via size() and
156 // empty().
157 size_t Back;
158
159 ICE_CACHELINE_BOUNDARY;
160 // Shrunk is notified (by the consumer) when something is removed
161 // from the queue, in case a producer is waiting for the queue to
162 // drop below maximum capacity. It is written by the consumers and
163 // read by the producers.
164 std::condition_variable Shrunk;
165 // Front is the index into WorkItems[] of the oldest element,
166 // i.e. the next to be popped. (More precisely Front&MaxStaticSize
167 // is the index.) It is written by the consumers, and read by all
168 // via size() and empty().
169 size_t Front;
170
171 ICE_CACHELINE_BOUNDARY;
172
173 // MaxSize and Sequential are read by all and written by none.
174 const size_t MaxSize;
175 const bool Sequential;
176 // IsEnded is read by the consumers, and only written once by the
177 // producer.
178 bool IsEnded;
179
180 // The lock must be held when the following methods are called.
181 bool empty() const { return Front == Back; }
182 size_t size() const { return Back - Front; }
183 void push(T *Item) {
184 WorkItems[Back++ & MaxStaticSizeMask] = Item;
185 assert(size() <= MaxStaticSize);
186 }
187 T *pop() {
188 assert(!empty());
189 return WorkItems[Front++ & MaxStaticSizeMask];
190 }
191 };
192
193 } // end of namespace Ice 64 } // end of namespace Ice
194 65
195 #endif // SUBZERO_SRC_ICEUTILS_H 66 #endif // SUBZERO_SRC_ICEUTILS_H
OLDNEW
« no previous file with comments | « src/IceTranslator.cpp ('k') | src/PNaClTranslator.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698