OLD | NEW |
1 // Copyright 2012 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef V8_DATAFLOW_H_ | 5 #ifndef V8_DATAFLOW_H_ |
6 #define V8_DATAFLOW_H_ | 6 #define V8_DATAFLOW_H_ |
7 | 7 |
8 #include "src/v8.h" | 8 #include "src/v8.h" |
9 | 9 |
10 #include "src/allocation.h" | 10 #include "src/allocation.h" |
11 #include "src/ast.h" | 11 #include "src/ast.h" |
12 #include "src/compiler.h" | 12 #include "src/compiler.h" |
13 #include "src/zone-inl.h" | 13 #include "src/zone-inl.h" |
14 | 14 |
15 namespace v8 { | 15 namespace v8 { |
16 namespace internal { | 16 namespace internal { |
17 | 17 |
18 class BitVector: public ZoneObject { | 18 class BitVector : public ZoneObject { |
19 public: | 19 public: |
20 // Iterator for the elements of this BitVector. | 20 // Iterator for the elements of this BitVector. |
21 class Iterator BASE_EMBEDDED { | 21 class Iterator BASE_EMBEDDED { |
22 public: | 22 public: |
23 explicit Iterator(BitVector* target) | 23 explicit Iterator(BitVector* target) |
24 : target_(target), | 24 : target_(target), |
25 current_index_(0), | 25 current_index_(0), |
26 current_value_(target->data_[0]), | 26 current_value_(target->data_[0]), |
27 current_(-1) { | 27 current_(-1) { |
28 DCHECK(target->data_length_ > 0); | 28 DCHECK(target->data_length_ > 0); |
29 Advance(); | 29 Advance(); |
30 } | 30 } |
31 ~Iterator() { } | 31 ~Iterator() {} |
32 | 32 |
33 bool Done() const { return current_index_ >= target_->data_length_; } | 33 bool Done() const { return current_index_ >= target_->data_length_; } |
34 void Advance(); | 34 void Advance(); |
35 | 35 |
36 int Current() const { | 36 int Current() const { |
37 DCHECK(!Done()); | 37 DCHECK(!Done()); |
38 return current_; | 38 return current_; |
39 } | 39 } |
40 | 40 |
41 private: | 41 private: |
42 uint32_t SkipZeroBytes(uint32_t val) { | 42 uintptr_t SkipZeroBytes(uintptr_t val) { |
43 while ((val & 0xFF) == 0) { | 43 while ((val & 0xFF) == 0) { |
44 val >>= 8; | 44 val >>= 8; |
45 current_ += 8; | 45 current_ += 8; |
46 } | 46 } |
47 return val; | 47 return val; |
48 } | 48 } |
49 uint32_t SkipZeroBits(uint32_t val) { | 49 uintptr_t SkipZeroBits(uintptr_t val) { |
50 while ((val & 0x1) == 0) { | 50 while ((val & 0x1) == 0) { |
51 val >>= 1; | 51 val >>= 1; |
52 current_++; | 52 current_++; |
53 } | 53 } |
54 return val; | 54 return val; |
55 } | 55 } |
56 | 56 |
57 BitVector* target_; | 57 BitVector* target_; |
58 int current_index_; | 58 int current_index_; |
59 uint32_t current_value_; | 59 uintptr_t current_value_; |
60 int current_; | 60 int current_; |
61 | 61 |
62 friend class BitVector; | 62 friend class BitVector; |
63 }; | 63 }; |
64 | 64 |
| 65 static const int kDataBits = kPointerSize * 8; |
| 66 static const int kDataBitShift = kPointerSize == 8 ? 6 : 5; |
| 67 static const uintptr_t kOne = 1; // This saves some static_casts. |
| 68 |
65 BitVector(int length, Zone* zone) | 69 BitVector(int length, Zone* zone) |
66 : length_(length), | 70 : length_(length), |
67 data_length_(SizeFor(length)), | 71 data_length_(SizeFor(length)), |
68 data_(zone->NewArray<uint32_t>(data_length_)) { | 72 data_(zone->NewArray<uintptr_t>(data_length_)) { |
69 DCHECK(length > 0); | 73 DCHECK(length > 0); |
70 Clear(); | 74 Clear(); |
71 } | 75 } |
72 | 76 |
73 BitVector(const BitVector& other, Zone* zone) | 77 BitVector(const BitVector& other, Zone* zone) |
74 : length_(other.length()), | 78 : length_(other.length()), |
75 data_length_(SizeFor(length_)), | 79 data_length_(SizeFor(length_)), |
76 data_(zone->NewArray<uint32_t>(data_length_)) { | 80 data_(zone->NewArray<uintptr_t>(data_length_)) { |
77 CopyFrom(other); | 81 CopyFrom(other); |
78 } | 82 } |
79 | 83 |
80 static int SizeFor(int length) { | 84 static int SizeFor(int length) { return 1 + ((length - 1) / kDataBits); } |
81 return 1 + ((length - 1) / 32); | |
82 } | |
83 | |
84 BitVector& operator=(const BitVector& rhs) { | |
85 if (this != &rhs) CopyFrom(rhs); | |
86 return *this; | |
87 } | |
88 | 85 |
89 void CopyFrom(const BitVector& other) { | 86 void CopyFrom(const BitVector& other) { |
90 DCHECK(other.length() <= length()); | 87 DCHECK(other.length() <= length()); |
91 for (int i = 0; i < other.data_length_; i++) { | 88 for (int i = 0; i < other.data_length_; i++) { |
92 data_[i] = other.data_[i]; | 89 data_[i] = other.data_[i]; |
93 } | 90 } |
94 for (int i = other.data_length_; i < data_length_; i++) { | 91 for (int i = other.data_length_; i < data_length_; i++) { |
95 data_[i] = 0; | 92 data_[i] = 0; |
96 } | 93 } |
97 } | 94 } |
98 | 95 |
99 bool Contains(int i) const { | 96 bool Contains(int i) const { |
100 DCHECK(i >= 0 && i < length()); | 97 DCHECK(i >= 0 && i < length()); |
101 uint32_t block = data_[i / 32]; | 98 uintptr_t block = data_[i / kDataBits]; |
102 return (block & (1U << (i % 32))) != 0; | 99 return (block & (kOne << (i % kDataBits))) != 0; |
103 } | 100 } |
104 | 101 |
105 void Add(int i) { | 102 void Add(int i) { |
106 DCHECK(i >= 0 && i < length()); | 103 DCHECK(i >= 0 && i < length()); |
107 data_[i / 32] |= (1U << (i % 32)); | 104 data_[i / kDataBits] |= (kOne << (i % kDataBits)); |
108 } | 105 } |
109 | 106 |
110 void Remove(int i) { | 107 void Remove(int i) { |
111 DCHECK(i >= 0 && i < length()); | 108 DCHECK(i >= 0 && i < length()); |
112 data_[i / 32] &= ~(1U << (i % 32)); | 109 data_[i / kDataBits] &= ~(kOne << (i % kDataBits)); |
113 } | 110 } |
114 | 111 |
115 void Union(const BitVector& other) { | 112 void Union(const BitVector& other) { |
116 DCHECK(other.length() == length()); | 113 DCHECK(other.length() == length()); |
117 for (int i = 0; i < data_length_; i++) { | 114 for (int i = 0; i < data_length_; i++) { |
118 data_[i] |= other.data_[i]; | 115 data_[i] |= other.data_[i]; |
119 } | 116 } |
120 } | 117 } |
121 | 118 |
122 bool UnionIsChanged(const BitVector& other) { | 119 bool UnionIsChanged(const BitVector& other) { |
123 DCHECK(other.length() == length()); | 120 DCHECK(other.length() == length()); |
124 bool changed = false; | 121 bool changed = false; |
125 for (int i = 0; i < data_length_; i++) { | 122 for (int i = 0; i < data_length_; i++) { |
126 uint32_t old_data = data_[i]; | 123 uintptr_t old_data = data_[i]; |
127 data_[i] |= other.data_[i]; | 124 data_[i] |= other.data_[i]; |
128 if (data_[i] != old_data) changed = true; | 125 if (data_[i] != old_data) changed = true; |
129 } | 126 } |
130 return changed; | 127 return changed; |
131 } | 128 } |
132 | 129 |
133 void Intersect(const BitVector& other) { | 130 void Intersect(const BitVector& other) { |
134 DCHECK(other.length() == length()); | 131 DCHECK(other.length() == length()); |
135 for (int i = 0; i < data_length_; i++) { | 132 for (int i = 0; i < data_length_; i++) { |
136 data_[i] &= other.data_[i]; | 133 data_[i] &= other.data_[i]; |
137 } | 134 } |
138 } | 135 } |
139 | 136 |
140 bool IntersectIsChanged(const BitVector& other) { | 137 bool IntersectIsChanged(const BitVector& other) { |
141 DCHECK(other.length() == length()); | 138 DCHECK(other.length() == length()); |
142 bool changed = false; | 139 bool changed = false; |
143 for (int i = 0; i < data_length_; i++) { | 140 for (int i = 0; i < data_length_; i++) { |
144 uint32_t old_data = data_[i]; | 141 uintptr_t old_data = data_[i]; |
145 data_[i] &= other.data_[i]; | 142 data_[i] &= other.data_[i]; |
146 if (data_[i] != old_data) changed = true; | 143 if (data_[i] != old_data) changed = true; |
147 } | 144 } |
148 return changed; | 145 return changed; |
149 } | 146 } |
150 | 147 |
151 void Subtract(const BitVector& other) { | 148 void Subtract(const BitVector& other) { |
152 DCHECK(other.length() == length()); | 149 DCHECK(other.length() == length()); |
153 for (int i = 0; i < data_length_; i++) { | 150 for (int i = 0; i < data_length_; i++) { |
154 data_[i] &= ~other.data_[i]; | 151 data_[i] &= ~other.data_[i]; |
(...skipping 22 matching lines...) Expand all Loading... |
177 | 174 |
178 int Count() const; | 175 int Count() const; |
179 | 176 |
180 int length() const { return length_; } | 177 int length() const { return length_; } |
181 | 178 |
182 #ifdef DEBUG | 179 #ifdef DEBUG |
183 void Print(); | 180 void Print(); |
184 #endif | 181 #endif |
185 | 182 |
186 private: | 183 private: |
187 int length_; | 184 const int length_; |
188 int data_length_; | 185 const int data_length_; |
189 uint32_t* data_; | 186 uintptr_t* const data_; |
| 187 |
| 188 DISALLOW_COPY_AND_ASSIGN(BitVector); |
190 }; | 189 }; |
191 | 190 |
192 | 191 |
193 class GrowableBitVector BASE_EMBEDDED { | 192 class GrowableBitVector BASE_EMBEDDED { |
194 public: | 193 public: |
195 class Iterator BASE_EMBEDDED { | 194 class Iterator BASE_EMBEDDED { |
196 public: | 195 public: |
197 Iterator(const GrowableBitVector* target, Zone* zone) | 196 Iterator(const GrowableBitVector* target, Zone* zone) |
198 : it_(target->bits_ == NULL | 197 : it_(target->bits_ == NULL ? new (zone) BitVector(1, zone) |
199 ? new(zone) BitVector(1, zone) | 198 : target->bits_) {} |
200 : target->bits_) { } | |
201 bool Done() const { return it_.Done(); } | 199 bool Done() const { return it_.Done(); } |
202 void Advance() { it_.Advance(); } | 200 void Advance() { it_.Advance(); } |
203 int Current() const { return it_.Current(); } | 201 int Current() const { return it_.Current(); } |
| 202 |
204 private: | 203 private: |
205 BitVector::Iterator it_; | 204 BitVector::Iterator it_; |
206 }; | 205 }; |
207 | 206 |
208 GrowableBitVector() : bits_(NULL) { } | 207 GrowableBitVector() : bits_(NULL) {} |
209 GrowableBitVector(int length, Zone* zone) | 208 GrowableBitVector(int length, Zone* zone) |
210 : bits_(new(zone) BitVector(length, zone)) { } | 209 : bits_(new (zone) BitVector(length, zone)) {} |
211 | 210 |
212 bool Contains(int value) const { | 211 bool Contains(int value) const { |
213 if (!InBitsRange(value)) return false; | 212 if (!InBitsRange(value)) return false; |
214 return bits_->Contains(value); | 213 return bits_->Contains(value); |
215 } | 214 } |
216 | 215 |
217 void Add(int value, Zone* zone) { | 216 void Add(int value, Zone* zone) { |
218 EnsureCapacity(value, zone); | 217 EnsureCapacity(value, zone); |
219 bits_->Add(value); | 218 bits_->Add(value); |
220 } | 219 } |
221 | 220 |
222 void Union(const GrowableBitVector& other, Zone* zone) { | 221 void Union(const GrowableBitVector& other, Zone* zone) { |
223 for (Iterator it(&other, zone); !it.Done(); it.Advance()) { | 222 for (Iterator it(&other, zone); !it.Done(); it.Advance()) { |
224 Add(it.Current(), zone); | 223 Add(it.Current(), zone); |
225 } | 224 } |
226 } | 225 } |
227 | 226 |
228 void Clear() { if (bits_ != NULL) bits_->Clear(); } | 227 void Clear() { |
| 228 if (bits_ != NULL) bits_->Clear(); |
| 229 } |
229 | 230 |
230 private: | 231 private: |
231 static const int kInitialLength = 1024; | 232 static const int kInitialLength = 1024; |
232 | 233 |
233 bool InBitsRange(int value) const { | 234 bool InBitsRange(int value) const { |
234 return bits_ != NULL && bits_->length() > value; | 235 return bits_ != NULL && bits_->length() > value; |
235 } | 236 } |
236 | 237 |
237 void EnsureCapacity(int value, Zone* zone) { | 238 void EnsureCapacity(int value, Zone* zone) { |
238 if (InBitsRange(value)) return; | 239 if (InBitsRange(value)) return; |
239 int new_length = bits_ == NULL ? kInitialLength : bits_->length(); | 240 int new_length = bits_ == NULL ? kInitialLength : bits_->length(); |
240 while (new_length <= value) new_length *= 2; | 241 while (new_length <= value) new_length *= 2; |
241 BitVector* new_bits = new(zone) BitVector(new_length, zone); | 242 BitVector* new_bits = new (zone) BitVector(new_length, zone); |
242 if (bits_ != NULL) new_bits->CopyFrom(*bits_); | 243 if (bits_ != NULL) new_bits->CopyFrom(*bits_); |
243 bits_ = new_bits; | 244 bits_ = new_bits; |
244 } | 245 } |
245 | 246 |
246 BitVector* bits_; | 247 BitVector* bits_; |
247 }; | 248 }; |
248 | 249 |
249 } // namespace internal | 250 } // namespace internal |
250 } // namespace v8 | 251 } // namespace v8 |
251 | 252 |
252 #endif // V8_DATAFLOW_H_ | 253 #endif // V8_DATAFLOW_H_ |
OLD | NEW |