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   void Subtract(const BitVector& other) {
 141     DCHECK(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 Count() const {
 168     int count = 0;
 169     for (int i = 0; i < data_length_; i++) {
 170       int data = data_[i];
 171       if (data != 0) count += CompilerIntrinsics::CountSetBits(data);
 172     }
 173     return count;
 174   }
 175
 176   int length() const { return length_; }
 177
 178 #ifdef DEBUG
 179   void Print();
 180 #endif
 181
 182  private:
 183   int length_;
 184   int data_length_;
 185   uint32_t* data_;
 186 };
 187
 188 class GrowableBitVector BASE_EMBEDDED {
 189  public:
 190   class Iterator BASE_EMBEDDED {
 191    public:
 192     Iterator(const GrowableBitVector* target, Zone* zone)
 193         : it_(target->bits_ == NULL
 194               ? new(zone) BitVector(1, zone)
 195               : target->bits_) { }
 196     bool Done() const { return it_.Done(); }
 197     void Advance() { it_.Advance(); }
 198     int Current() const { return it_.Current(); }
 199    private:
 200     BitVector::Iterator it_;
 201   };
 202
 203   GrowableBitVector() : bits_(NULL) { }
 204   GrowableBitVector(int length, Zone* zone)
 205       : bits_(new(zone) BitVector(length, zone)) { }
 206
 207   bool Contains(int value) const {
 208     if (!InBitsRange(value)) return false;
 209     return bits_->Contains(value);
 210   }
 211
 212   void Add(int value, Zone* zone) {
 213     EnsureCapacity(value, zone);
 214     bits_->Add(value);
 215   }
 216
 217   void Union(const GrowableBitVector& other, Zone* zone) {
 218     for (Iterator it(&other, zone); !it.Done(); it.Advance()) {
 219       Add(it.Current(), zone);
 220     }
 221   }
 222
 223   void Clear() { if (bits_ != NULL) bits_->Clear(); }
 224
 225  private:
 226   static const int kInitialLength = 1024;
 227
 228   bool InBitsRange(int value) const {
 229     return bits_ != NULL && bits_->length() > value;
 230   }
 231
 232   void EnsureCapacity(int value, Zone* zone) {
 233     if (InBitsRange(value)) return;
 234     int new_length = bits_ == NULL ? kInitialLength : bits_->length();
 235     while (new_length <= value) new_length *= 2;
 236     BitVector* new_bits = new(zone) BitVector(new_length, zone);
 237     if (bits_ != NULL) new_bits->CopyFrom(*bits_);
 238     bits_ = new_bits;
 239   }
 240
 241   BitVector* bits_;
 242 };
 243
 244
 245 } }  // namespace v8::internal
 246
 247
 248 #endif  // V8_DATAFLOW_H_