src/v8/src/data-flow.h

   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/v8.h"
   9
  10 #include "src/allocation.h"
  11 #include "src/ast.h"
  12 #include "src/compiler.h"
  13 #include "src/zone-inl.h"
  14
  15 namespace v8 {
  16 namespace internal {
  17
  18 class BitVector: public ZoneObject {
  19  public:
  20   // Iterator for the elements of this BitVector.
  21   class Iterator BASE_EMBEDDED {
  22    public:
  23     explicit Iterator(BitVector* target)
  24         : target_(target),
  25           current_index_(0),
  26           current_value_(target->data_[0]),
  27           current_(-1) {
  28       DCHECK(target->data_length_ > 0);
  29       Advance();
  30     }
  31     ~Iterator() { }
  32
  33     bool Done() const { return current_index_ >= target_->data_length_; }
  34     void Advance();
  35
  36     int Current() const {
  37       DCHECK(!Done());
  38       return current_;
  39     }
  40
  41    private:
  42     uint32_t SkipZeroBytes(uint32_t val) {
  43       while ((val & 0xFF) == 0) {
  44         val >>= 8;
  45         current_ += 8;
  46       }
  47       return val;
  48     }
  49     uint32_t SkipZeroBits(uint32_t val) {
  50       while ((val & 0x1) == 0) {
  51         val >>= 1;
  52         current_++;
  53       }
  54       return val;
  55     }
  56
  57     BitVector* target_;
  58     int current_index_;
  59     uint32_t current_value_;
  60     int current_;
  61
  62     friend class BitVector;
  63   };
  64
  65   BitVector(int length, Zone* zone)
  66       : length_(length),
  67         data_length_(SizeFor(length)),
  68         data_(zone->NewArray<uint32_t>(data_length_)) {
  69     DCHECK(length > 0);
  70     Clear();
  71   }
  72
  73   BitVector(const BitVector& other, Zone* zone)
  74       : length_(other.length()),
  75         data_length_(SizeFor(length_)),
  76         data_(zone->NewArray<uint32_t>(data_length_)) {
  77     CopyFrom(other);
  78   }
  79
  80   static int SizeFor(int length) {
  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
  89   void CopyFrom(const BitVector& other) {
  90     DCHECK(other.length() <= length());
  91     for (int i = 0; i < other.data_length_; i++) {
  92       data_[i] = other.data_[i];
  93     }
  94     for (int i = other.data_length_; i < data_length_; i++) {
  95       data_[i] = 0;
  96     }
  97   }
  98
  99   bool Contains(int i) const {
 100     DCHECK(i >= 0 && i < length());
 101     uint32_t block = data_[i / 32];
 102     return (block & (1U << (i % 32))) != 0;
 103   }
 104
 105   void Add(int i) {
 106     DCHECK(i >= 0 && i < length());
 107     data_[i / 32] |= (1U << (i % 32));
 108   }
 109
 110   void Remove(int i) {
 111     DCHECK(i >= 0 && i < length());
 112     data_[i / 32] &= ~(1U << (i % 32));
 113   }
 114
 115   void Union(const BitVector& other) {
 116     DCHECK(other.length() == length());
 117     for (int i = 0; i < data_length_; i++) {
 118       data_[i] |= other.data_[i];
 119     }
 120   }
 121
 122   bool UnionIsChanged(const BitVector& other) {
 123     DCHECK(other.length() == length());
 124     bool changed = false;
 125     for (int i = 0; i < data_length_; i++) {
 126       uint32_t old_data = data_[i];
 127       data_[i] |= other.data_[i];
 128       if (data_[i] != old_data) changed = true;
 129     }
 130     return changed;
 131   }
 132
 133   void Intersect(const BitVector& other) {
 134     DCHECK(other.length() == length());
 135     for (int i = 0; i < data_length_; i++) {
 136       data_[i] &= other.data_[i];
 137     }
 138   }
 139
 140   bool IntersectIsChanged(const BitVector& other) {
 141     DCHECK(other.length() == length());
 142     bool changed = false;
 143     for (int i = 0; i < data_length_; i++) {
 144       uint32_t old_data = data_[i];
 145       data_[i] &= other.data_[i];
 146       if (data_[i] != old_data) changed = true;
 147     }
 148     return changed;
 149   }
 150
 151   void Subtract(const BitVector& other) {
 152     DCHECK(other.length() == length());
 153     for (int i = 0; i < data_length_; i++) {
 154       data_[i] &= ~other.data_[i];
 155     }
 156   }
 157
 158   void Clear() {
 159     for (int i = 0; i < data_length_; i++) {
 160       data_[i] = 0;
 161     }
 162   }
 163
 164   bool IsEmpty() const {
 165     for (int i = 0; i < data_length_; i++) {
 166       if (data_[i] != 0) return false;
 167     }
 168     return true;
 169   }
 170
 171   bool Equals(const BitVector& other) {
 172     for (int i = 0; i < data_length_; i++) {
 173       if (data_[i] != other.data_[i]) return false;
 174     }
 175     return true;
 176   }
 177
 178   int Count() const;
 179
 180   int length() const { return length_; }
 181
 182 #ifdef DEBUG
 183   void Print();
 184 #endif
 185
 186  private:
 187   int length_;
 188   int data_length_;
 189   uint32_t* data_;
 190 };
 191
 192
 193 class GrowableBitVector BASE_EMBEDDED {
 194  public:
 195   class Iterator BASE_EMBEDDED {
 196    public:
 197     Iterator(const GrowableBitVector* target, Zone* zone)
 198         : it_(target->bits_ == NULL
 199               ? new(zone) BitVector(1, zone)
 200               : target->bits_) { }
 201     bool Done() const { return it_.Done(); }
 202     void Advance() { it_.Advance(); }
 203     int Current() const { return it_.Current(); }
 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() { if (bits_ != NULL) bits_->Clear(); }
 229
 230  private:
 231   static const int kInitialLength = 1024;
 232
 233   bool InBitsRange(int value) const {
 234     return bits_ != NULL && bits_->length() > value;
 235   }
 236
 237   void EnsureCapacity(int value, Zone* zone) {
 238     if (InBitsRange(value)) return;
 239     int new_length = bits_ == NULL ? kInitialLength : bits_->length();
 240     while (new_length <= value) new_length *= 2;
 241     BitVector* new_bits = new(zone) BitVector(new_length, zone);
 242     if (bits_ != NULL) new_bits->CopyFrom(*bits_);
 243     bits_ = new_bits;
 244   }
 245
 246   BitVector* bits_;
 247 };
 248
 249 }  // namespace internal
 250 }  // namespace v8
 251
 252 #endif  // V8_DATAFLOW_H_