Line data Source code
1 : // Copyright 2013 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #ifndef V8_CRANKSHAFT_UNIQUE_H_
6 : #define V8_CRANKSHAFT_UNIQUE_H_
7 :
8 : #include <ostream> // NOLINT(readability/streams)
9 :
10 : #include "src/assert-scope.h"
11 : #include "src/base/functional.h"
12 : #include "src/handles.h"
13 : #include "src/utils.h"
14 : #include "src/zone/zone.h"
15 :
16 : namespace v8 {
17 : namespace internal {
18 :
19 :
20 : template <typename T>
21 : class UniqueSet;
22 :
23 :
24 : // Represents a handle to an object on the heap, but with the additional
25 : // ability of checking for equality and hashing without accessing the heap.
26 : //
27 : // Creating a Unique<T> requires first dereferencing the handle to obtain
28 : // the address of the object, which is used as the hashcode and the basis for
29 : // comparison. The object can be moved later by the GC, but comparison
30 : // and hashing use the old address of the object, without dereferencing it.
31 : //
32 : // Careful! Comparison of two Uniques is only correct if both were created
33 : // in the same "era" of GC or if at least one is a non-movable object.
34 : template <typename T>
35 : class Unique final {
36 : public:
37 1134592 : Unique<T>() : raw_address_(NULL) {}
38 :
39 : // TODO(titzer): make private and introduce a uniqueness scope.
40 : explicit Unique(Handle<T> handle) {
41 4813263 : if (handle.is_null()) {
42 10567642 : raw_address_ = NULL;
43 : } else {
44 : // This is a best-effort check to prevent comparing Unique<T>'s created
45 : // in different GC eras; we require heap allocation to be disallowed at
46 : // creation time.
47 : // NOTE: we currently consider maps to be non-movable, so no special
48 : // assurance is required for creating a Unique<Map>.
49 : // TODO(titzer): other immortable immovable objects are also fine.
50 : DCHECK(!AllowHeapAllocation::IsAllowed() || handle->IsMap());
51 1612 : raw_address_ = reinterpret_cast<Address>(*handle);
52 : DCHECK_NOT_NULL(raw_address_); // Non-null should imply non-zero address.
53 : }
54 1612 : handle_ = handle;
55 : }
56 :
57 : // Constructor for handling automatic up casting.
58 : // Eg. Unique<JSFunction> can be passed when Unique<Object> is expected.
59 : template <class S> Unique(Unique<S> uniq) {
60 : #ifdef DEBUG
61 : T* a = NULL;
62 : S* b = NULL;
63 : a = b; // Fake assignment to enforce type checks.
64 : USE(a);
65 : #endif
66 1838 : raw_address_ = uniq.raw_address_;
67 1838 : handle_ = uniq.handle_;
68 : }
69 :
70 : template <typename U>
71 : inline bool operator==(const Unique<U>& other) const {
72 : DCHECK(IsInitialized() && other.IsInitialized());
73 4025774 : return raw_address_ == other.raw_address_;
74 : }
75 :
76 : template <typename U>
77 : inline bool operator!=(const Unique<U>& other) const {
78 : DCHECK(IsInitialized() && other.IsInitialized());
79 : return raw_address_ != other.raw_address_;
80 : }
81 :
82 : friend inline size_t hash_value(Unique<T> const& unique) {
83 : DCHECK(unique.IsInitialized());
84 : return base::hash<void*>()(unique.raw_address_);
85 : }
86 :
87 : inline intptr_t Hashcode() const {
88 : DCHECK(IsInitialized());
89 10691403 : return reinterpret_cast<intptr_t>(raw_address_);
90 : }
91 :
92 : inline bool IsNull() const {
93 : DCHECK(IsInitialized());
94 : return raw_address_ == NULL;
95 : }
96 :
97 : inline bool IsKnownGlobal(void* global) const {
98 : DCHECK(IsInitialized());
99 : return raw_address_ == reinterpret_cast<Address>(global);
100 : }
101 :
102 : inline Handle<T> handle() const {
103 : return handle_;
104 : }
105 :
106 : template <class S> static Unique<T> cast(Unique<S> that) {
107 : // Allow fetching location() to unsafe-cast the handle. This is necessary
108 : // since we can't concurrently safe-cast. Safe-casting requires looking at
109 : // the heap which may be moving concurrently to the compiler thread.
110 : AllowHandleDereference allow_deref;
111 : return Unique<T>(that.raw_address_,
112 : Handle<T>(reinterpret_cast<T**>(that.handle_.location())));
113 : }
114 :
115 : inline bool IsInitialized() const {
116 164504 : return raw_address_ != NULL || handle_.is_null();
117 : }
118 :
119 : // TODO(titzer): this is a hack to migrate to Unique<T> incrementally.
120 : static Unique<T> CreateUninitialized(Handle<T> handle) {
121 : return Unique<T>(NULL, handle);
122 : }
123 :
124 : static Unique<T> CreateImmovable(Handle<T> handle) {
125 : return Unique<T>(reinterpret_cast<Address>(*handle), handle);
126 : }
127 :
128 : private:
129 : Unique(Address raw_address, Handle<T> handle)
130 : : raw_address_(raw_address), handle_(handle) {}
131 :
132 : Address raw_address_;
133 : Handle<T> handle_;
134 :
135 : friend class UniqueSet<T>; // Uses internal details for speed.
136 : template <class U>
137 : friend class Unique; // For comparing raw_address values.
138 : };
139 :
140 : template <typename T>
141 : inline std::ostream& operator<<(std::ostream& os, Unique<T> uniq) {
142 : return os << Brief(*uniq.handle());
143 : }
144 :
145 :
146 : template <typename T>
147 : class UniqueSet final : public ZoneObject {
148 : public:
149 : // Constructor. A new set will be empty.
150 0 : UniqueSet() : size_(0), capacity_(0), array_(NULL) { }
151 :
152 : // Capacity constructor. A new set will be empty.
153 : UniqueSet(int capacity, Zone* zone)
154 : : size_(0), capacity_(capacity),
155 2862064 : array_(zone->NewArray<Unique<T> >(capacity)) {
156 : DCHECK(capacity <= kMaxCapacity);
157 : }
158 :
159 : // Singleton constructor.
160 : UniqueSet(Unique<T> uniq, Zone* zone)
161 431462 : : size_(1), capacity_(1), array_(zone->NewArray<Unique<T> >(1)) {
162 215731 : array_[0] = uniq;
163 : }
164 :
165 : // Add a new element to this unique set. Mutates this set. O(|this|).
166 6444364 : void Add(Unique<T> uniq, Zone* zone) {
167 : DCHECK(uniq.IsInitialized());
168 : // Keep the set sorted by the {raw_address} of the unique elements.
169 56126045 : for (int i = 0; i < size_; i++) {
170 53597893 : if (array_[i] == uniq) return;
171 53597800 : if (array_[i].raw_address_ > uniq.raw_address_) {
172 : // Insert in the middle.
173 3916119 : Grow(size_ + 1, zone);
174 3916110 : for (int j = size_ - 1; j >= i; j--) array_[j + 1] = array_[j];
175 3916110 : array_[i] = uniq;
176 3916110 : size_++;
177 3916110 : return;
178 : }
179 : }
180 : // Append the element to the the end.
181 2528152 : Grow(size_ + 1, zone);
182 2528142 : array_[size_++] = uniq;
183 : }
184 :
185 : // Remove an element from this set. Mutates this set. O(|this|)
186 6794 : void Remove(Unique<T> uniq) {
187 3228 : for (int i = 0; i < size_; i++) {
188 9950 : if (array_[i] == uniq) {
189 852 : while (++i < size_) array_[i - 1] = array_[i];
190 6722 : size_--;
191 6794 : return;
192 : }
193 : }
194 : }
195 :
196 : // Compare this set against another set. O(|this|).
197 : bool Equals(const UniqueSet<T>* that) const {
198 113062 : if (that->size_ != this->size_) return false;
199 113518 : for (int i = 0; i < this->size_; i++) {
200 113586 : if (this->array_[i] != that->array_[i]) return false;
201 : }
202 : return true;
203 : }
204 :
205 : // Check whether this set contains the given element. O(|this|)
206 : // TODO(titzer): use binary search for large sets to make this O(log|this|)
207 : template <typename U>
208 : bool Contains(const Unique<U> elem) const {
209 3172 : for (int i = 0; i < this->size_; ++i) {
210 9970 : Unique<T> cand = this->array_[i];
211 9970 : if (cand.raw_address_ >= elem.raw_address_) {
212 6798 : return cand.raw_address_ == elem.raw_address_;
213 : }
214 : }
215 : return false;
216 : }
217 :
218 : // Check if this set is a subset of the given set. O(|this| + |that|).
219 25325 : bool IsSubset(const UniqueSet<T>* that) const {
220 25325 : if (that->size_ < this->size_) return false;
221 : int j = 0;
222 24769 : for (int i = 0; i < this->size_; i++) {
223 24962 : Unique<T> sought = this->array_[i];
224 : while (true) {
225 25307 : if (sought == that->array_[j++]) break;
226 : // Fail whenever there are more elements in {this} than {that}.
227 538 : if ((this->size_ - i) > (that->size_ - j)) return false;
228 : }
229 : }
230 : return true;
231 : }
232 :
233 : // Returns a new set representing the intersection of this set and the other.
234 : // O(|this| + |that|).
235 2282 : UniqueSet<T>* Intersect(const UniqueSet<T>* that, Zone* zone) const {
236 2282 : if (that->size_ == 0 || this->size_ == 0) return new(zone) UniqueSet<T>();
237 :
238 : UniqueSet<T>* out = new(zone) UniqueSet<T>(
239 : Min(this->size_, that->size_), zone);
240 :
241 : int i = 0, j = 0, k = 0;
242 7413 : while (i < this->size_ && j < that->size_) {
243 2849 : Unique<T> a = this->array_[i];
244 2849 : Unique<T> b = that->array_[j];
245 2849 : if (a == b) {
246 2200 : out->array_[k++] = a;
247 2200 : i++;
248 2200 : j++;
249 649 : } else if (a.raw_address_ < b.raw_address_) {
250 178 : i++;
251 : } else {
252 471 : j++;
253 : }
254 : }
255 :
256 2282 : out->size_ = k;
257 2282 : return out;
258 : }
259 :
260 : // Returns a new set representing the union of this set and the other.
261 : // O(|this| + |that|).
262 933457 : UniqueSet<T>* Union(const UniqueSet<T>* that, Zone* zone) const {
263 933457 : if (that->size_ == 0) return this->Copy(zone);
264 933457 : if (this->size_ == 0) return that->Copy(zone);
265 :
266 : UniqueSet<T>* out = new(zone) UniqueSet<T>(
267 933461 : this->size_ + that->size_, zone);
268 :
269 : int i = 0, j = 0, k = 0;
270 3051715 : while (i < this->size_ && j < that->size_) {
271 1184781 : Unique<T> a = this->array_[i];
272 1184781 : Unique<T> b = that->array_[j];
273 1184781 : if (a == b) {
274 1161532 : out->array_[k++] = a;
275 1161532 : i++;
276 1161532 : j++;
277 23249 : } else if (a.raw_address_ < b.raw_address_) {
278 8897 : out->array_[k++] = a;
279 8897 : i++;
280 : } else {
281 14352 : out->array_[k++] = b;
282 14352 : j++;
283 : }
284 : }
285 :
286 14559 : while (i < this->size_) out->array_[k++] = this->array_[i++];
287 6662 : while (j < that->size_) out->array_[k++] = that->array_[j++];
288 :
289 933467 : out->size_ = k;
290 933467 : return out;
291 : }
292 :
293 : // Returns a new set representing all elements from this set which are not in
294 : // that set. O(|this| * |that|).
295 12 : UniqueSet<T>* Subtract(const UniqueSet<T>* that, Zone* zone) const {
296 6 : if (that->size_ == 0) return this->Copy(zone);
297 :
298 6 : UniqueSet<T>* out = new(zone) UniqueSet<T>(this->size_, zone);
299 :
300 : int i = 0, j = 0;
301 18 : while (i < this->size_) {
302 6 : Unique<T> cand = this->array_[i];
303 6 : if (!that->Contains(cand)) {
304 6 : out->array_[j++] = cand;
305 : }
306 6 : i++;
307 : }
308 :
309 6 : out->size_ = j;
310 6 : return out;
311 : }
312 :
313 : // Makes an exact copy of this set. O(|this|).
314 22390 : UniqueSet<T>* Copy(Zone* zone) const {
315 22392 : UniqueSet<T>* copy = new(zone) UniqueSet<T>(this->size_, zone);
316 22392 : copy->size_ = this->size_;
317 22392 : memcpy(copy->array_, this->array_, this->size_ * sizeof(Unique<T>));
318 22392 : return copy;
319 : }
320 :
321 : void Clear() {
322 : size_ = 0;
323 : }
324 :
325 : inline int size() const {
326 1145370 : return size_;
327 : }
328 :
329 : inline Unique<T> at(int index) const {
330 : DCHECK(index >= 0 && index < size_);
331 710591 : return array_[index];
332 : }
333 :
334 : private:
335 : // These sets should be small, since operations are implemented with simple
336 : // linear algorithms. Enforce a maximum size.
337 : static const int kMaxCapacity = 65535;
338 :
339 : uint16_t size_;
340 : uint16_t capacity_;
341 : Unique<T>* array_;
342 :
343 : // Grow the size of internal storage to be at least {size} elements.
344 6444220 : void Grow(int size, Zone* zone) {
345 6444220 : CHECK(size < kMaxCapacity); // Enforce maximum size.
346 6444220 : if (capacity_ < size) {
347 0 : int new_capacity = 2 * capacity_ + size;
348 0 : if (new_capacity > kMaxCapacity) new_capacity = kMaxCapacity;
349 0 : Unique<T>* new_array = zone->NewArray<Unique<T> >(new_capacity);
350 0 : if (size_ > 0) {
351 0 : memcpy(new_array, array_, size_ * sizeof(Unique<T>));
352 : }
353 0 : capacity_ = new_capacity;
354 0 : array_ = new_array;
355 : }
356 6444220 : }
357 : };
358 :
359 : } // namespace internal
360 : } // namespace v8
361 :
362 : #endif // V8_CRANKSHAFT_UNIQUE_H_
|
