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.h"
10
11namespace v8 {
12namespace internal {
13
14class 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          current_value_(target->data_[0]),
23          current_(-1) {
24      DCHECK(target->data_length_ > 0);
25      Advance();
26    }
27    ~Iterator() {}
28
29    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      while ((val & 0xFF) == 0) {
40        val >>= 8;
41        current_ += 8;
42      }
43      return val;
44    }
45    uintptr_t SkipZeroBits(uintptr_t val) {
46      while ((val & 0x1) == 0) {
47        val >>= 1;
48        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  BitVector(int length, Zone* zone)
66      : length_(length),
67        data_length_(SizeFor(length)),
68        data_(zone->NewArray<uintptr_t>(data_length_)) {
69    DCHECK_LE(0, length);
70    Clear();
71  }
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    if (length == 0) return 1;
82    return 1 + ((length - 1) / kDataBits);
83  }
84
85  void CopyFrom(const BitVector& other) {
86    DCHECK(other.length() <= length());
87    for (int i = 0; i < other.data_length_; i++) {
88      data_[i] = other.data_[i];
89    }
90    for (int i = other.data_length_; i < data_length_; i++) {
91      data_[i] = 0;
92    }
93  }
94
95  bool Contains(int i) const {
96    DCHECK(i >= 0 && i < length());
97    uintptr_t block = data_[i / kDataBits];
98    return (block & (kOne << (i % kDataBits))) != 0;
99  }
100
101  void Add(int i) {
102    DCHECK(i >= 0 && i < length());
103    data_[i / kDataBits] |= (kOne << (i % kDataBits));
104  }
105
106  void AddAll() { memset(data_, -1, sizeof(uintptr_t) * data_length_); }
107
108  void Remove(int i) {
109    DCHECK(i >= 0 && i < length());
110    data_[i / kDataBits] &= ~(kOne << (i % kDataBits));
111  }
112
113  void Union(const BitVector& other) {
114    DCHECK(other.length() == length());
115    for (int i = 0; i < data_length_; i++) {
116      data_[i] |= other.data_[i];
117    }
118  }
119
120  bool UnionIsChanged(const BitVector& other) {
121    DCHECK(other.length() == length());
122    bool changed = false;
123    for (int i = 0; i < data_length_; i++) {
124      uintptr_t old_data = data_[i];
125      data_[i] |= other.data_[i];
126      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    for (int i = 0; i < data_length_; i++) {
142      uintptr_t old_data = data_[i];
143      data_[i] &= other.data_[i];
144      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    for (int i = 0; i < data_length_; i++) {
158      data_[i] = 0;
159    }
160  }
161
162  bool IsEmpty() const {
163    for (int i = 0; i < data_length_; i++) {
164      if (data_[i] != 0) return false;
165    }
166    return true;
167  }
168
169  bool Equals(const BitVector& other) {
170    for (int i = 0; i < data_length_; i++) {
171      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
193class GrowableBitVector BASE_EMBEDDED {
194 public:
195  class Iterator BASE_EMBEDDED {
196   public:
197    Iterator(const GrowableBitVector* target, Zone* zone)
198        : it_(target->bits_ == NULL ? new (zone) BitVector(1, zone)
199                                    : target->bits_) {}
200    bool Done() const { return it_.Done(); }
201    void Advance() { it_.Advance(); }
202    int Current() const { return it_.Current(); }
203
204   private:
205    BitVector::Iterator it_;
206  };
207
208  GrowableBitVector() : bits_(NULL) {}
209  GrowableBitVector(int length, Zone* zone)
210      : bits_(new (zone) BitVector(length, zone)) {}
211
212  bool Contains(int value) const {
213    if (!InBitsRange(value)) return false;
214    return bits_->Contains(value);
215  }
216
217  void Add(int value, Zone* zone) {
218    EnsureCapacity(value, zone);
219    bits_->Add(value);
220  }
221
222  void Union(const GrowableBitVector& other, Zone* zone) {
223    for (Iterator it(&other, zone); !it.Done(); it.Advance()) {
224      Add(it.Current(), zone);
225    }
226  }
227
228  void Clear() {
229    if (bits_ != NULL) bits_->Clear();
230  }
231
232 private:
233  static const int kInitialLength = 1024;
234
235  bool InBitsRange(int value) const {
236    return bits_ != NULL && bits_->length() > value;
237  }
238
239  void EnsureCapacity(int value, Zone* zone) {
240    if (InBitsRange(value)) return;
241    int new_length = bits_ == NULL ? kInitialLength : bits_->length();
242    while (new_length <= value) new_length *= 2;
243    BitVector* new_bits = new (zone) BitVector(new_length, zone);
244    if (bits_ != NULL) new_bits->CopyFrom(*bits_);
245    bits_ = new_bits;
246  }
247
248  BitVector* bits_;
249};
250
251}  // namespace internal
252}  // namespace v8
253
254#endif  // V8_DATAFLOW_H_
255