src/3rdparty/v8/src/data-flow.h

   1 // Copyright 2012 the V8 project authors. All rights reserved.
   2 // Redistribution and use in source and binary forms, with or without
   3 // modification, are permitted provided that the following conditions are
   4 // met:
   5 //
   6 //     * Redistributions of source code must retain the above copyright
   7 //       notice, this list of conditions and the following disclaimer.
   8 //     * Redistributions in binary form must reproduce the above
   9 //       copyright notice, this list of conditions and the following
  10 //       disclaimer in the documentation and/or other materials provided
  11 //       with the distribution.
  12 //     * Neither the name of Google Inc. nor the names of its
  13 //       contributors may be used to endorse or promote products derived
  14 //       from this software without specific prior written permission.
  15 //
  16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27
  28 #ifndef V8_DATAFLOW_H_
  29 #define V8_DATAFLOW_H_
  30
  31 #include "v8.h"
  32
  33 #include "allocation.h"
  34 #include "ast.h"
  35 #include "compiler.h"
  36 #include "zone-inl.h"
  37
  38 namespace v8 {
  39 namespace internal {
  40
  41 class BitVector: public ZoneObject {
  42  public:
  43   // Iterator for the elements of this BitVector.
  44   class Iterator BASE_EMBEDDED {
  45    public:
  46     explicit Iterator(BitVector* target)
  47         : target_(target),
  48           current_index_(0),
  49           current_value_(target->data_[0]),
  50           current_(-1) {
  51       ASSERT(target->data_length_ > 0);
  52       Advance();
  53     }
  54     ~Iterator() { }
  55
  56     bool Done() const { return current_index_ >= target_->data_length_; }
  57     void Advance();
  58
  59     int Current() const {
  60       ASSERT(!Done());
  61       return current_;
  62     }
  63
  64    private:
  65     uint32_t SkipZeroBytes(uint32_t val) {
  66       while ((val & 0xFF) == 0) {
  67         val >>= 8;
  68         current_ += 8;
  69       }
  70       return val;
  71     }
  72     uint32_t SkipZeroBits(uint32_t val) {
  73       while ((val & 0x1) == 0) {
  74         val >>= 1;
  75         current_++;
  76       }
  77       return val;
  78     }
  79
  80     BitVector* target_;
  81     int current_index_;
  82     uint32_t current_value_;
  83     int current_;
  84
  85     friend class BitVector;
  86   };
  87
  88   BitVector(int length, Zone* zone)
  89       : length_(length),
  90         data_length_(SizeFor(length)),
  91         data_(zone->NewArray<uint32_t>(data_length_)) {
  92     ASSERT(length > 0);
  93     Clear();
  94   }
  95
  96   BitVector(const BitVector& other, Zone* zone)
  97       : length_(other.length()),
  98         data_length_(SizeFor(length_)),
  99         data_(zone->NewArray<uint32_t>(data_length_)) {
 100     CopyFrom(other);
 101   }
 102
 103   static int SizeFor(int length) {
 104     return 1 + ((length - 1) / 32);
 105   }
 106
 107   BitVector& operator=(const BitVector& rhs) {
 108     if (this != &rhs) CopyFrom(rhs);
 109     return *this;
 110   }
 111
 112   void CopyFrom(const BitVector& other) {
 113     ASSERT(other.length() <= length());
 114     for (int i = 0; i < other.data_length_; i++) {
 115       data_[i] = other.data_[i];
 116     }
 117     for (int i = other.data_length_; i < data_length_; i++) {
 118       data_[i] = 0;
 119     }
 120   }
 121
 122   bool Contains(int i) const {
 123     ASSERT(i >= 0 && i < length());
 124     uint32_t block = data_[i / 32];
 125     return (block & (1U << (i % 32))) != 0;
 126   }
 127
 128   void Add(int i) {
 129     ASSERT(i >= 0 && i < length());
 130     data_[i / 32] |= (1U << (i % 32));
 131   }
 132
 133   void Remove(int i) {
 134     ASSERT(i >= 0 && i < length());
 135     data_[i / 32] &= ~(1U << (i % 32));
 136   }
 137
 138   void Union(const BitVector& other) {
 139     ASSERT(other.length() == length());
 140     for (int i = 0; i < data_length_; i++) {
 141       data_[i] |= other.data_[i];
 142     }
 143   }
 144
 145   bool UnionIsChanged(const BitVector& other) {
 146     ASSERT(other.length() == length());
 147     bool changed = false;
 148     for (int i = 0; i < data_length_; i++) {
 149       uint32_t old_data = data_[i];
 150       data_[i] |= other.data_[i];
 151       if (data_[i] != old_data) changed = true;
 152     }
 153     return changed;
 154   }
 155
 156   void Intersect(const BitVector& other) {
 157     ASSERT(other.length() == length());
 158     for (int i = 0; i < data_length_; i++) {
 159       data_[i] &= other.data_[i];
 160     }
 161   }
 162
 163   void Subtract(const BitVector& other) {
 164     ASSERT(other.length() == length());
 165     for (int i = 0; i < data_length_; i++) {
 166       data_[i] &= ~other.data_[i];
 167     }
 168   }
 169
 170   void Clear() {
 171     for (int i = 0; i < data_length_; i++) {
 172       data_[i] = 0;
 173     }
 174   }
 175
 176   bool IsEmpty() const {
 177     for (int i = 0; i < data_length_; i++) {
 178       if (data_[i] != 0) return false;
 179     }
 180     return true;
 181   }
 182
 183   bool Equals(const BitVector& other) {
 184     for (int i = 0; i < data_length_; i++) {
 185       if (data_[i] != other.data_[i]) return false;
 186     }
 187     return true;
 188   }
 189
 190   int length() const { return length_; }
 191
 192 #ifdef DEBUG
 193   void Print();
 194 #endif
 195
 196  private:
 197   int length_;
 198   int data_length_;
 199   uint32_t* data_;
 200 };
 201
 202 } }  // namespace v8::internal
 203
 204
 205 #endif  // V8_DATAFLOW_H_