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       ASSERT(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       ASSERT(!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     ASSERT(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     ASSERT(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     ASSERT(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     ASSERT(i >= 0 && i < length());
 107     data_[i / 32] |= (1U << (i % 32));
 108   }
 109
 110   void Remove(int i) {
 111     ASSERT(i >= 0 && i < length());
 112     data_[i / 32] &= ~(1U << (i % 32));
 113   }
 114
 115   void Union(const BitVector& other) {
 116     ASSERT(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     ASSERT(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     ASSERT(other.length() == length());
 135     for (int i = 0; i < data_length_; i++) {
 136       data_[i] &= other.data_[i];
 137     }
 138   }
 139
 140   void Subtract(const BitVector& other) {
 141     ASSERT(other.length() == length());
 142     for (int i = 0; i < data_length_; i++) {
 143       data_[i] &= ~other.data_[i];
 144     }
 145   }
 146
 147   void Clear() {
 148     for (int i = 0; i < data_length_; i++) {
 149       data_[i] = 0;
 150     }
 151   }
 152
 153   bool IsEmpty() const {
 154     for (int i = 0; i < data_length_; i++) {
 155       if (data_[i] != 0) return false;
 156     }
 157     return true;
 158   }
 159
 160   bool Equals(const BitVector& other) {
 161     for (int i = 0; i < data_length_; i++) {
 162       if (data_[i] != other.data_[i]) return false;
 163     }
 164     return true;
 165   }
 166
 167   int length() const { return length_; }
 168
 169 #ifdef DEBUG
 170   void Print();
 171 #endif
 172
 173  private:
 174   int length_;
 175   int data_length_;
 176   uint32_t* data_;
 177 };
 178
 179 class GrowableBitVector BASE_EMBEDDED {
 180  public:
 181   class Iterator BASE_EMBEDDED {
 182    public:
 183     Iterator(const GrowableBitVector* target, Zone* zone)
 184         : it_(target->bits_ == NULL
 185               ? new(zone) BitVector(1, zone)
 186               : target->bits_) { }
 187     bool Done() const { return it_.Done(); }
 188     void Advance() { it_.Advance(); }
 189     int Current() const { return it_.Current(); }
 190    private:
 191     BitVector::Iterator it_;
 192   };
 193
 194   GrowableBitVector() : bits_(NULL) { }
 195   GrowableBitVector(int length, Zone* zone)
 196       : bits_(new(zone) BitVector(length, zone)) { }
 197
 198   bool Contains(int value) const {
 199     if (!InBitsRange(value)) return false;
 200     return bits_->Contains(value);
 201   }
 202
 203   void Add(int value, Zone* zone) {
 204     EnsureCapacity(value, zone);
 205     bits_->Add(value);
 206   }
 207
 208   void Union(const GrowableBitVector& other, Zone* zone) {
 209     for (Iterator it(&other, zone); !it.Done(); it.Advance()) {
 210       Add(it.Current(), zone);
 211     }
 212   }
 213
 214   void Clear() { if (bits_ != NULL) bits_->Clear(); }
 215
 216  private:
 217   static const int kInitialLength = 1024;
 218
 219   bool InBitsRange(int value) const {
 220     return bits_ != NULL && bits_->length() > value;
 221   }
 222
 223   void EnsureCapacity(int value, Zone* zone) {
 224     if (InBitsRange(value)) return;
 225     int new_length = bits_ == NULL ? kInitialLength : bits_->length();
 226     while (new_length <= value) new_length *= 2;
 227     BitVector* new_bits = new(zone) BitVector(new_length, zone);
 228     if (bits_ != NULL) new_bits->CopyFrom(*bits_);
 229     bits_ = new_bits;
 230   }
 231
 232   BitVector* bits_;
 233 };
 234
 235
 236 } }  // namespace v8::internal
 237
 238
 239 #endif  // V8_DATAFLOW_H_