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 45184207 : current_value_(target->data_[0]),
23 90368414 : current_(-1) {
24 : DCHECK(target->data_length_ > 0);
25 45184207 : Advance();
26 : }
27 : ~Iterator() {}
28 :
29 226293696 : 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 288224638 : while ((val & 0xFF) == 0) {
40 107148018 : val >>= 8;
41 107148018 : current_ += 8;
42 : }
43 : return val;
44 : }
45 : uintptr_t SkipZeroBits(uintptr_t val) {
46 525428300 : while ((val & 0x1) == 0) {
47 344351680 : val >>= 1;
48 344351680 : 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 177316857 : BitVector(int length, Zone* zone)
66 : : length_(length),
67 : data_length_(SizeFor(length)),
68 265975195 : data_(zone->NewArray<uintptr_t>(data_length_)) {
69 : DCHECK_LE(0, length);
70 : Clear();
71 88658519 : }
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 88658338 : if (length == 0) return 1;
82 88656917 : return 1 + ((length - 1) / kDataBits);
83 : }
84 :
85 : void CopyFrom(const BitVector& other) {
86 : DCHECK(other.length() <= length());
87 303390124 : for (int i = 0; i < other.data_length_; i++) {
88 303390124 : data_[i] = other.data_[i];
89 : }
90 5168 : for (int i = other.data_length_; i < data_length_; i++) {
91 5168 : data_[i] = 0;
92 : }
93 : }
94 :
95 : bool Contains(int i) const {
96 : DCHECK(i >= 0 && i < length());
97 216914616 : uintptr_t block = data_[i / kDataBits];
98 216914616 : return (block & (kOne << (i % kDataBits))) != 0;
99 : }
100 :
101 : void Add(int i) {
102 : DCHECK(i >= 0 && i < length());
103 229893319 : data_[i / kDataBits] |= (kOne << (i % kDataBits));
104 : }
105 :
106 11644 : void AddAll() { memset(data_, -1, sizeof(uintptr_t) * data_length_); }
107 :
108 : void Remove(int i) {
109 : DCHECK(i >= 0 && i < length());
110 52309897 : data_[i / kDataBits] &= ~(kOne << (i % kDataBits));
111 : }
112 :
113 : void Union(const BitVector& other) {
114 : DCHECK(other.length() == length());
115 927797975 : for (int i = 0; i < data_length_; i++) {
116 927797975 : data_[i] |= other.data_[i];
117 : }
118 : }
119 :
120 : bool UnionIsChanged(const BitVector& other) {
121 : DCHECK(other.length() == length());
122 : bool changed = false;
123 6176630 : for (int i = 0; i < data_length_; i++) {
124 6176630 : uintptr_t old_data = data_[i];
125 6176630 : data_[i] |= other.data_[i];
126 6176630 : 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 1169358088 : for (int i = 0; i < data_length_; i++) {
158 1169358088 : data_[i] = 0;
159 : }
160 : }
161 :
162 : bool IsEmpty() const {
163 324535 : for (int i = 0; i < data_length_; i++) {
164 974876 : if (data_[i] != 0) return false;
165 : }
166 : return true;
167 : }
168 :
169 : bool Equals(const BitVector& other) const {
170 4607771 : for (int i = 0; i < data_length_; i++) {
171 4855124 : 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 18836978 : Iterator(const GrowableBitVector* target, Zone* zone)
198 33548333 : : it_(target->bits_ == NULL ? new (zone) BitVector(1, zone)
199 56511197 : : target->bits_) {}
200 24752618 : bool Done() const { return it_.Done(); }
201 5915291 : void Advance() { it_.Advance(); }
202 5915292 : int Current() const { return it_.Current(); }
203 :
204 : private:
205 : BitVector::Iterator it_;
206 : };
207 :
208 14742346 : GrowableBitVector() : bits_(NULL) {}
209 11615012 : GrowableBitVector(int length, Zone* zone)
210 11615026 : : bits_(new (zone) BitVector(length, zone)) {}
211 :
212 58115524 : bool Contains(int value) const {
213 58115524 : if (!InBitsRange(value)) return false;
214 115612408 : return bits_->Contains(value);
215 : }
216 :
217 42094260 : void Add(int value, Zone* zone) {
218 42094260 : EnsureCapacity(value, zone);
219 42094338 : bits_->Add(value);
220 42094338 : }
221 :
222 13882134 : void Union(const GrowableBitVector& other, Zone* zone) {
223 32719261 : for (Iterator it(&other, zone); !it.Done(); it.Advance()) {
224 4954847 : Add(it.Current(), zone);
225 : }
226 13882280 : }
227 :
228 : void Clear() {
229 5833217 : if (bits_ != NULL) bits_->Clear();
230 : }
231 :
232 : private:
233 : static const int kInitialLength = 1024;
234 :
235 : bool InBitsRange(int value) const {
236 100209794 : return bits_ != NULL && bits_->length() > value;
237 : }
238 :
239 42094270 : void EnsureCapacity(int value, Zone* zone) {
240 84188537 : if (InBitsRange(value)) return;
241 2505115 : int new_length = bits_ == NULL ? kInitialLength : bits_->length();
242 2483415 : while (new_length <= value) new_length *= 2;
243 2505122 : BitVector* new_bits = new (zone) BitVector(new_length, zone);
244 2483412 : if (bits_ != NULL) new_bits->CopyFrom(*bits_);
245 2483412 : bits_ = new_bits;
246 : }
247 :
248 : BitVector* bits_;
249 : };
250 :
251 : } // namespace internal
252 : } // namespace v8
253 :
254 : #endif // V8_DATAFLOW_H_
|
