Line data Source code
1 : // Copyright 2012 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_DATAFLOW_H_
6 : #define V8_DATAFLOW_H_
7 :
8 : #include "src/allocation.h"
9 : #include "src/zone/zone.h"
10 :
11 : namespace v8 {
12 : namespace internal {
13 :
14 : class BitVector : public ZoneObject {
15 : public:
16 : union DataStorage {
17 : uintptr_t* ptr_; // valid if data_length_ > 1
18 : uintptr_t inline_; // valid if data_length_ == 1
19 :
20 49523170 : DataStorage(uintptr_t value) : inline_(value) {}
21 : };
22 :
23 : // Iterator for the elements of this BitVector.
24 : class Iterator BASE_EMBEDDED {
25 : public:
26 44331274 : explicit Iterator(BitVector* target)
27 : : target_(target),
28 : current_index_(0),
29 : current_value_(target->is_inline() ? target->data_.inline_
30 10268571 : : target->data_.ptr_[0]),
31 54599845 : current_(-1) {
32 22165637 : Advance();
33 22165668 : }
34 : ~Iterator() {}
35 :
36 240177268 : bool Done() const { return current_index_ >= target_->data_length_; }
37 : void Advance();
38 :
39 : int Current() const {
40 : DCHECK(!Done());
41 : return current_;
42 : }
43 :
44 : private:
45 : uintptr_t SkipZeroBytes(uintptr_t val) {
46 194858487 : while ((val & 0xFF) == 0) {
47 62028405 : val >>= 8;
48 62028405 : current_ += 8;
49 : }
50 : return val;
51 : }
52 : uintptr_t SkipZeroBits(uintptr_t val) {
53 406783765 : while ((val & 0x1) == 0) {
54 273953683 : val >>= 1;
55 273953683 : current_++;
56 : }
57 : return val;
58 : }
59 :
60 : BitVector* target_;
61 : int current_index_;
62 : uintptr_t current_value_;
63 : int current_;
64 :
65 : friend class BitVector;
66 : };
67 :
68 : static const int kDataLengthForInline = 1;
69 : static const int kDataBits = kPointerSize * 8;
70 : static const int kDataBitShift = kPointerSize == 8 ? 6 : 5;
71 : static const uintptr_t kOne = 1; // This saves some static_casts.
72 :
73 : BitVector() : length_(0), data_length_(kDataLengthForInline), data_(0) {}
74 :
75 49523164 : BitVector(int length, Zone* zone)
76 99046328 : : length_(length), data_length_(SizeFor(length)), data_(0) {
77 : DCHECK_LE(0, length);
78 49523164 : if (!is_inline()) {
79 17663684 : data_.ptr_ = zone->NewArray<uintptr_t>(data_length_);
80 : Clear();
81 : }
82 : // Otherwise, clearing is implicit
83 49523112 : }
84 :
85 6 : BitVector(const BitVector& other, Zone* zone)
86 : : length_(other.length_),
87 : data_length_(other.data_length_),
88 6 : data_(other.data_.inline_) {
89 6 : if (!is_inline()) {
90 0 : data_.ptr_ = zone->NewArray<uintptr_t>(data_length_);
91 0 : for (int i = 0; i < other.data_length_; i++) {
92 0 : data_.ptr_[i] = other.data_.ptr_[i];
93 : }
94 : }
95 6 : }
96 :
97 : static int SizeFor(int length) {
98 49523177 : if (length <= kDataBits) {
99 : return kDataLengthForInline;
100 : }
101 :
102 8831874 : int data_length = 1 + ((length - 1) / kDataBits);
103 : DCHECK_GT(data_length, kDataLengthForInline);
104 : return data_length;
105 : }
106 :
107 : void CopyFrom(const BitVector& other) {
108 : DCHECK_LE(other.length(), length());
109 18077658 : CopyFrom(other.data_, other.data_length_);
110 : }
111 :
112 13 : void Resize(int new_length, Zone* zone) {
113 : DCHECK_GT(new_length, length());
114 : int new_data_length = SizeFor(new_length);
115 13 : if (new_data_length > data_length_) {
116 6 : DataStorage old_data = data_;
117 : int old_data_length = data_length_;
118 :
119 : // Make sure the new data length is large enough to need allocation.
120 : DCHECK_GT(new_data_length, kDataLengthForInline);
121 12 : data_.ptr_ = zone->NewArray<uintptr_t>(new_data_length);
122 6 : data_length_ = new_data_length;
123 6 : CopyFrom(old_data, old_data_length);
124 : }
125 13 : length_ = new_length;
126 13 : }
127 :
128 113402525 : bool Contains(int i) const {
129 : DCHECK(i >= 0 && i < length());
130 113402639 : uintptr_t block = is_inline() ? data_.inline_ : data_.ptr_[i / kDataBits];
131 113402639 : return (block & (kOne << (i % kDataBits))) != 0;
132 : }
133 :
134 129094638 : void Add(int i) {
135 : DCHECK(i >= 0 && i < length());
136 134299147 : if (is_inline()) {
137 87834988 : data_.inline_ |= (kOne << i);
138 : } else {
139 46464159 : data_.ptr_[i / kDataBits] |= (kOne << (i % kDataBits));
140 : }
141 : }
142 :
143 : void AddAll() {
144 : // TODO(leszeks): This sets bits outside of the length of this bit-vector,
145 : // which is observable if we resize it or copy from it. If this is a
146 : // problem, we should clear the high bits either on add, or on resize/copy.
147 : if (is_inline()) {
148 : data_.inline_ = -1;
149 : } else {
150 : memset(data_.ptr_, -1, sizeof(uintptr_t) * data_length_);
151 : }
152 : }
153 :
154 41012392 : void Remove(int i) {
155 : DCHECK(i >= 0 && i < length());
156 41012392 : if (is_inline()) {
157 25367310 : data_.inline_ &= ~(kOne << i);
158 : } else {
159 15645082 : data_.ptr_[i / kDataBits] &= ~(kOne << (i % kDataBits));
160 : }
161 41012392 : }
162 :
163 36247352 : void Union(const BitVector& other) {
164 : DCHECK(other.length() == length());
165 36247352 : if (is_inline()) {
166 : DCHECK(other.is_inline());
167 25186678 : data_.inline_ |= other.data_.inline_;
168 : } else {
169 253393637 : for (int i = 0; i < data_length_; i++) {
170 253393637 : data_.ptr_[i] |= other.data_.ptr_[i];
171 : }
172 : }
173 36247352 : }
174 :
175 61216 : bool UnionIsChanged(const BitVector& other) {
176 : DCHECK(other.length() == length());
177 61216 : if (is_inline()) {
178 : DCHECK(other.is_inline());
179 60974 : uintptr_t old_data = data_.inline_;
180 60974 : data_.inline_ |= other.data_.inline_;
181 60974 : return data_.inline_ != old_data;
182 : } else {
183 : bool changed = false;
184 1378 : for (int i = 0; i < data_length_; i++) {
185 1378 : uintptr_t old_data = data_.ptr_[i];
186 1378 : data_.ptr_[i] |= other.data_.ptr_[i];
187 1378 : if (data_.ptr_[i] != old_data) changed = true;
188 : }
189 : return changed;
190 : }
191 : }
192 :
193 12 : void Intersect(const BitVector& other) {
194 : DCHECK(other.length() == length());
195 12 : if (is_inline()) {
196 : DCHECK(other.is_inline());
197 12 : data_.inline_ &= other.data_.inline_;
198 : } else {
199 0 : for (int i = 0; i < data_length_; i++) {
200 0 : data_.ptr_[i] &= other.data_.ptr_[i];
201 : }
202 : }
203 12 : }
204 :
205 68 : bool IntersectIsChanged(const BitVector& other) {
206 : DCHECK(other.length() == length());
207 68 : if (is_inline()) {
208 : DCHECK(other.is_inline());
209 68 : uintptr_t old_data = data_.inline_;
210 68 : data_.inline_ &= other.data_.inline_;
211 68 : return data_.inline_ != old_data;
212 : } else {
213 : bool changed = false;
214 0 : for (int i = 0; i < data_length_; i++) {
215 0 : uintptr_t old_data = data_.ptr_[i];
216 0 : data_.ptr_[i] &= other.data_.ptr_[i];
217 0 : if (data_.ptr_[i] != old_data) changed = true;
218 : }
219 : return changed;
220 : }
221 : }
222 :
223 : void Subtract(const BitVector& other) {
224 : DCHECK(other.length() == length());
225 : if (is_inline()) {
226 : DCHECK(other.is_inline());
227 : data_.inline_ &= ~other.data_.inline_;
228 : } else {
229 : for (int i = 0; i < data_length_; i++) {
230 : data_.ptr_[i] &= ~other.data_.ptr_[i];
231 : }
232 : }
233 : }
234 :
235 8831816 : void Clear() {
236 8831816 : if (is_inline()) {
237 0 : data_.inline_ = 0;
238 : } else {
239 406050918 : for (int i = 0; i < data_length_; i++) {
240 406050918 : data_.ptr_[i] = 0;
241 : }
242 : }
243 : }
244 :
245 320882 : bool IsEmpty() const {
246 320882 : if (is_inline()) {
247 320882 : return data_.inline_ == 0;
248 : } else {
249 0 : for (int i = 0; i < data_length_; i++) {
250 0 : if (data_.ptr_[i] != 0) return false;
251 : }
252 : return true;
253 : }
254 : }
255 :
256 : bool Equals(const BitVector& other) const {
257 : DCHECK(other.length() == length());
258 : if (is_inline()) {
259 : DCHECK(other.is_inline());
260 : return data_.inline_ == other.data_.inline_;
261 : } else {
262 : for (int i = 0; i < data_length_; i++) {
263 : if (data_.ptr_[i] != other.data_.ptr_[i]) return false;
264 : }
265 : return true;
266 : }
267 : }
268 :
269 : int Count() const;
270 :
271 : int length() const { return length_; }
272 :
273 : #ifdef DEBUG
274 : void Print();
275 : #endif
276 :
277 : private:
278 : int length_;
279 : int data_length_;
280 : DataStorage data_;
281 :
282 : bool is_inline() const { return data_length_ == kDataLengthForInline; }
283 :
284 18077658 : void CopyFrom(DataStorage other_data, int other_data_length) {
285 : DCHECK_LE(other_data_length, data_length_);
286 :
287 18077658 : if (is_inline()) {
288 : DCHECK_EQ(other_data_length, kDataLengthForInline);
289 16982396 : data_.inline_ = other_data.inline_;
290 1095262 : } else if (other_data_length == kDataLengthForInline) {
291 6 : data_.ptr_[0] = other_data.inline_;
292 30 : for (int i = 1; i < data_length_; i++) {
293 24 : data_.ptr_[i] = 0;
294 : }
295 : } else {
296 179611840 : for (int i = 0; i < other_data_length; i++) {
297 179611840 : data_.ptr_[i] = other_data.ptr_[i];
298 : }
299 0 : for (int i = other_data_length; i < data_length_; i++) {
300 0 : data_.ptr_[i] = 0;
301 : }
302 : }
303 18077658 : }
304 :
305 : DISALLOW_COPY_AND_ASSIGN(BitVector);
306 : };
307 :
308 :
309 : class GrowableBitVector BASE_EMBEDDED {
310 : public:
311 : class Iterator BASE_EMBEDDED {
312 : public:
313 : Iterator(const GrowableBitVector* target, Zone* zone)
314 : : it_(target->bits_ == nullptr ? new (zone) BitVector(1, zone)
315 : : target->bits_) {}
316 : bool Done() const { return it_.Done(); }
317 : void Advance() { it_.Advance(); }
318 : int Current() const { return it_.Current(); }
319 :
320 : private:
321 : BitVector::Iterator it_;
322 : };
323 :
324 : GrowableBitVector() : bits_(nullptr) {}
325 : GrowableBitVector(int length, Zone* zone)
326 : : bits_(new (zone) BitVector(length, zone)) {}
327 :
328 : bool Contains(int value) const {
329 : if (!InBitsRange(value)) return false;
330 : return bits_->Contains(value);
331 : }
332 :
333 : void Add(int value, Zone* zone) {
334 : EnsureCapacity(value, zone);
335 : bits_->Add(value);
336 : }
337 :
338 : void Union(const GrowableBitVector& other, Zone* zone) {
339 : for (Iterator it(&other, zone); !it.Done(); it.Advance()) {
340 : Add(it.Current(), zone);
341 : }
342 : }
343 :
344 : void Clear() {
345 : if (bits_ != nullptr) bits_->Clear();
346 : }
347 :
348 : private:
349 : static const int kInitialLength = 1024;
350 :
351 : bool InBitsRange(int value) const {
352 : return bits_ != nullptr && bits_->length() > value;
353 : }
354 :
355 : void EnsureCapacity(int value, Zone* zone) {
356 : if (InBitsRange(value)) return;
357 : int new_length = bits_ == nullptr ? kInitialLength : bits_->length();
358 : while (new_length <= value) new_length *= 2;
359 :
360 : if (bits_ == nullptr) {
361 : bits_ = new (zone) BitVector(new_length, zone);
362 : } else {
363 : bits_->Resize(new_length, zone);
364 : }
365 : }
366 :
367 : BitVector* bits_;
368 : };
369 :
370 : } // namespace internal
371 : } // namespace v8
372 :
373 : #endif // V8_DATAFLOW_H_
|
