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 : // Iterator for the elements of this BitVector.
17 : class Iterator BASE_EMBEDDED {
18 : public:
19 : explicit Iterator(BitVector* target)
20 : : target_(target),
21 : current_index_(0),
22 45284944 : current_value_(target->data_[0]),
23 90569888 : current_(-1) {
24 : DCHECK(target->data_length_ > 0);
25 45284944 : Advance();
26 : }
27 : ~Iterator() {}
28 :
29 226430033 : bool Done() const { return current_index_ >= target_->data_length_; }
30 : void Advance();
31 :
32 : int Current() const {
33 : DCHECK(!Done());
34 : return current_;
35 : }
36 :
37 : private:
38 : uintptr_t SkipZeroBytes(uintptr_t val) {
39 288174265 : while ((val & 0xFF) == 0) {
40 107067646 : val >>= 8;
41 107067646 : current_ += 8;
42 : }
43 : return val;
44 : }
45 : uintptr_t SkipZeroBits(uintptr_t val) {
46 525486354 : while ((val & 0x1) == 0) {
47 344379735 : val >>= 1;
48 344379735 : current_++;
49 : }
50 : return val;
51 : }
52 :
53 : BitVector* target_;
54 : int current_index_;
55 : uintptr_t current_value_;
56 : int current_;
57 :
58 : friend class BitVector;
59 : };
60 :
61 : static const int kDataBits = kPointerSize * 8;
62 : static const int kDataBitShift = kPointerSize == 8 ? 6 : 5;
63 : static const uintptr_t kOne = 1; // This saves some static_casts.
64 :
65 177609650 : BitVector(int length, Zone* zone)
66 : : length_(length),
67 : data_length_(SizeFor(length)),
68 266414341 : data_(zone->NewArray<uintptr_t>(data_length_)) {
69 : DCHECK_LE(0, length);
70 : Clear();
71 88804959 : }
72 :
73 : BitVector(const BitVector& other, Zone* zone)
74 : : length_(other.length()),
75 : data_length_(SizeFor(length_)),
76 : data_(zone->NewArray<uintptr_t>(data_length_)) {
77 : CopyFrom(other);
78 : }
79 :
80 : static int SizeFor(int length) {
81 88804691 : if (length == 0) return 1;
82 88803242 : return 1 + ((length - 1) / kDataBits);
83 : }
84 :
85 : void CopyFrom(const BitVector& other) {
86 : DCHECK(other.length() <= length());
87 303010238 : for (int i = 0; i < other.data_length_; i++) {
88 303010238 : data_[i] = other.data_[i];
89 : }
90 5024 : for (int i = other.data_length_; i < data_length_; i++) {
91 5024 : data_[i] = 0;
92 : }
93 : }
94 :
95 : bool Contains(int i) const {
96 : DCHECK(i >= 0 && i < length());
97 217059159 : uintptr_t block = data_[i / kDataBits];
98 217059159 : return (block & (kOne << (i % kDataBits))) != 0;
99 : }
100 :
101 : void Add(int i) {
102 : DCHECK(i >= 0 && i < length());
103 230175291 : data_[i / kDataBits] |= (kOne << (i % kDataBits));
104 : }
105 :
106 11626 : void AddAll() { memset(data_, -1, sizeof(uintptr_t) * data_length_); }
107 :
108 : void Remove(int i) {
109 : DCHECK(i >= 0 && i < length());
110 52322939 : data_[i / kDataBits] &= ~(kOne << (i % kDataBits));
111 : }
112 :
113 : void Union(const BitVector& other) {
114 : DCHECK(other.length() == length());
115 928048652 : for (int i = 0; i < data_length_; i++) {
116 928048652 : data_[i] |= other.data_[i];
117 : }
118 : }
119 :
120 : bool UnionIsChanged(const BitVector& other) {
121 : DCHECK(other.length() == length());
122 : bool changed = false;
123 6199899 : for (int i = 0; i < data_length_; i++) {
124 6199899 : uintptr_t old_data = data_[i];
125 6199899 : data_[i] |= other.data_[i];
126 6199899 : if (data_[i] != old_data) changed = true;
127 : }
128 : return changed;
129 : }
130 :
131 : void Intersect(const BitVector& other) {
132 : DCHECK(other.length() == length());
133 : for (int i = 0; i < data_length_; i++) {
134 : data_[i] &= other.data_[i];
135 : }
136 : }
137 :
138 : bool IntersectIsChanged(const BitVector& other) {
139 : DCHECK(other.length() == length());
140 : bool changed = false;
141 68 : for (int i = 0; i < data_length_; i++) {
142 68 : uintptr_t old_data = data_[i];
143 68 : data_[i] &= other.data_[i];
144 68 : if (data_[i] != old_data) changed = true;
145 : }
146 : return changed;
147 : }
148 :
149 : void Subtract(const BitVector& other) {
150 : DCHECK(other.length() == length());
151 : for (int i = 0; i < data_length_; i++) {
152 : data_[i] &= ~other.data_[i];
153 : }
154 : }
155 :
156 : void Clear() {
157 1169432575 : for (int i = 0; i < data_length_; i++) {
158 1169432575 : data_[i] = 0;
159 : }
160 : }
161 :
162 : bool IsEmpty() const {
163 325280 : for (int i = 0; i < data_length_; i++) {
164 972644 : if (data_[i] != 0) return false;
165 : }
166 : return true;
167 : }
168 :
169 : bool Equals(const BitVector& other) const {
170 4627875 : for (int i = 0; i < data_length_; i++) {
171 4876377 : if (data_[i] != other.data_[i]) return false;
172 : }
173 : return true;
174 : }
175 :
176 : int Count() const;
177 :
178 : int length() const { return length_; }
179 :
180 : #ifdef DEBUG
181 : void Print();
182 : #endif
183 :
184 : private:
185 : const int length_;
186 : const int data_length_;
187 : uintptr_t* const data_;
188 :
189 : DISALLOW_COPY_AND_ASSIGN(BitVector);
190 : };
191 :
192 :
193 : class GrowableBitVector BASE_EMBEDDED {
194 : public:
195 : class Iterator BASE_EMBEDDED {
196 : public:
197 18903558 : Iterator(const GrowableBitVector* target, Zone* zone)
198 33673796 : : it_(target->bits_ == NULL ? new (zone) BitVector(1, zone)
199 56710850 : : target->bits_) {}
200 24834730 : bool Done() const { return it_.Done(); }
201 5930698 : void Advance() { it_.Advance(); }
202 5930684 : int Current() const { return it_.Current(); }
203 :
204 : private:
205 : BitVector::Iterator it_;
206 : };
207 :
208 14800255 : GrowableBitVector() : bits_(NULL) {}
209 11649257 : GrowableBitVector(int length, Zone* zone)
210 11649255 : : bits_(new (zone) BitVector(length, zone)) {}
211 :
212 58211909 : bool Contains(int value) const {
213 58211909 : if (!InBitsRange(value)) return false;
214 115801076 : return bits_->Contains(value);
215 : }
216 :
217 42215558 : void Add(int value, Zone* zone) {
218 42215558 : EnsureCapacity(value, zone);
219 42215629 : bits_->Add(value);
220 42215629 : }
221 :
222 13938985 : void Union(const GrowableBitVector& other, Zone* zone) {
223 32849775 : for (Iterator it(&other, zone); !it.Done(); it.Advance()) {
224 4971635 : Add(it.Current(), zone);
225 : }
226 13939155 : }
227 :
228 : void Clear() {
229 5844364 : if (bits_ != NULL) bits_->Clear();
230 : }
231 :
232 : private:
233 : static const int kInitialLength = 1024;
234 :
235 : bool InBitsRange(int value) const {
236 100427480 : return bits_ != NULL && bits_->length() > value;
237 : }
238 :
239 42215571 : void EnsureCapacity(int value, Zone* zone) {
240 84431159 : if (InBitsRange(value)) return;
241 2512956 : int new_length = bits_ == NULL ? kInitialLength : bits_->length();
242 2491253 : while (new_length <= value) new_length *= 2;
243 2512964 : BitVector* new_bits = new (zone) BitVector(new_length, zone);
244 2491270 : if (bits_ != NULL) new_bits->CopyFrom(*bits_);
245 2491270 : bits_ = new_bits;
246 : }
247 :
248 : BitVector* bits_;
249 : };
250 :
251 : } // namespace internal
252 : } // namespace v8
253 :
254 : #endif // V8_DATAFLOW_H_
|
