blob: 71d69b20c2ddb5a0862104ce5e902a97f48a6300 [file] [log] [blame]
// Copyright 2012 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef V8_DATAFLOW_H_
#define V8_DATAFLOW_H_
#include "src/allocation.h"
#include "src/zone/zone.h"
namespace v8 {
namespace internal {
class BitVector : public ZoneObject {
public:
union DataStorage {
uintptr_t* ptr_; // valid if data_length_ > 1
uintptr_t inline_; // valid if data_length_ == 1
DataStorage(uintptr_t value) : inline_(value) {}
};
// Iterator for the elements of this BitVector.
class Iterator BASE_EMBEDDED {
public:
explicit Iterator(BitVector* target)
: target_(target),
current_index_(0),
current_value_(target->is_inline() ? target->data_.inline_
: target->data_.ptr_[0]),
current_(-1) {
Advance();
}
~Iterator() {}
bool Done() const { return current_index_ >= target_->data_length_; }
void Advance();
int Current() const {
DCHECK(!Done());
return current_;
}
private:
uintptr_t SkipZeroBytes(uintptr_t val) {
while ((val & 0xFF) == 0) {
val >>= 8;
current_ += 8;
}
return val;
}
uintptr_t SkipZeroBits(uintptr_t val) {
while ((val & 0x1) == 0) {
val >>= 1;
current_++;
}
return val;
}
BitVector* target_;
int current_index_;
uintptr_t current_value_;
int current_;
friend class BitVector;
};
static const int kDataLengthForInline = 1;
static const int kDataBits = kPointerSize * 8;
static const int kDataBitShift = kPointerSize == 8 ? 6 : 5;
static const uintptr_t kOne = 1; // This saves some static_casts.
BitVector() : length_(0), data_length_(kDataLengthForInline), data_(0) {}
BitVector(int length, Zone* zone)
: length_(length), data_length_(SizeFor(length)), data_(0) {
DCHECK_LE(0, length);
if (!is_inline()) {
data_.ptr_ = zone->NewArray<uintptr_t>(data_length_);
Clear();
}
// Otherwise, clearing is implicit
}
BitVector(const BitVector& other, Zone* zone)
: length_(other.length_),
data_length_(other.data_length_),
data_(other.data_.inline_) {
if (!is_inline()) {
data_.ptr_ = zone->NewArray<uintptr_t>(data_length_);
for (int i = 0; i < other.data_length_; i++) {
data_.ptr_[i] = other.data_.ptr_[i];
}
}
}
static int SizeFor(int length) {
if (length <= kDataBits) {
return kDataLengthForInline;
}
int data_length = 1 + ((length - 1) / kDataBits);
DCHECK_GT(data_length, kDataLengthForInline);
return data_length;
}
void CopyFrom(const BitVector& other) {
DCHECK_LE(other.length(), length());
CopyFrom(other.data_, other.data_length_);
}
void Resize(int new_length, Zone* zone) {
DCHECK_GT(new_length, length());
int new_data_length = SizeFor(new_length);
if (new_data_length > data_length_) {
DataStorage old_data = data_;
int old_data_length = data_length_;
// Make sure the new data length is large enough to need allocation.
DCHECK_GT(new_data_length, kDataLengthForInline);
data_.ptr_ = zone->NewArray<uintptr_t>(new_data_length);
data_length_ = new_data_length;
CopyFrom(old_data, old_data_length);
}
length_ = new_length;
}
bool Contains(int i) const {
DCHECK(i >= 0 && i < length());
uintptr_t block = is_inline() ? data_.inline_ : data_.ptr_[i / kDataBits];
return (block & (kOne << (i % kDataBits))) != 0;
}
void Add(int i) {
DCHECK(i >= 0 && i < length());
if (is_inline()) {
data_.inline_ |= (kOne << i);
} else {
data_.ptr_[i / kDataBits] |= (kOne << (i % kDataBits));
}
}
void AddAll() {
// TODO(leszeks): This sets bits outside of the length of this bit-vector,
// which is observable if we resize it or copy from it. If this is a
// problem, we should clear the high bits either on add, or on resize/copy.
if (is_inline()) {
data_.inline_ = -1;
} else {
memset(data_.ptr_, -1, sizeof(uintptr_t) * data_length_);
}
}
void Remove(int i) {
DCHECK(i >= 0 && i < length());
if (is_inline()) {
data_.inline_ &= ~(kOne << i);
} else {
data_.ptr_[i / kDataBits] &= ~(kOne << (i % kDataBits));
}
}
void Union(const BitVector& other) {
DCHECK(other.length() == length());
if (is_inline()) {
DCHECK(other.is_inline());
data_.inline_ |= other.data_.inline_;
} else {
for (int i = 0; i < data_length_; i++) {
data_.ptr_[i] |= other.data_.ptr_[i];
}
}
}
bool UnionIsChanged(const BitVector& other) {
DCHECK(other.length() == length());
if (is_inline()) {
DCHECK(other.is_inline());
uintptr_t old_data = data_.inline_;
data_.inline_ |= other.data_.inline_;
return data_.inline_ != old_data;
} else {
bool changed = false;
for (int i = 0; i < data_length_; i++) {
uintptr_t old_data = data_.ptr_[i];
data_.ptr_[i] |= other.data_.ptr_[i];
if (data_.ptr_[i] != old_data) changed = true;
}
return changed;
}
}
void Intersect(const BitVector& other) {
DCHECK(other.length() == length());
if (is_inline()) {
DCHECK(other.is_inline());
data_.inline_ &= other.data_.inline_;
} else {
for (int i = 0; i < data_length_; i++) {
data_.ptr_[i] &= other.data_.ptr_[i];
}
}
}
bool IntersectIsChanged(const BitVector& other) {
DCHECK(other.length() == length());
if (is_inline()) {
DCHECK(other.is_inline());
uintptr_t old_data = data_.inline_;
data_.inline_ &= other.data_.inline_;
return data_.inline_ != old_data;
} else {
bool changed = false;
for (int i = 0; i < data_length_; i++) {
uintptr_t old_data = data_.ptr_[i];
data_.ptr_[i] &= other.data_.ptr_[i];
if (data_.ptr_[i] != old_data) changed = true;
}
return changed;
}
}
void Subtract(const BitVector& other) {
DCHECK(other.length() == length());
if (is_inline()) {
DCHECK(other.is_inline());
data_.inline_ &= ~other.data_.inline_;
} else {
for (int i = 0; i < data_length_; i++) {
data_.ptr_[i] &= ~other.data_.ptr_[i];
}
}
}
void Clear() {
if (is_inline()) {
data_.inline_ = 0;
} else {
for (int i = 0; i < data_length_; i++) {
data_.ptr_[i] = 0;
}
}
}
bool IsEmpty() const {
if (is_inline()) {
return data_.inline_ == 0;
} else {
for (int i = 0; i < data_length_; i++) {
if (data_.ptr_[i] != 0) return false;
}
return true;
}
}
bool Equals(const BitVector& other) const {
DCHECK(other.length() == length());
if (is_inline()) {
DCHECK(other.is_inline());
return data_.inline_ == other.data_.inline_;
} else {
for (int i = 0; i < data_length_; i++) {
if (data_.ptr_[i] != other.data_.ptr_[i]) return false;
}
return true;
}
}
int Count() const;
int length() const { return length_; }
#ifdef DEBUG
void Print();
#endif
private:
int length_;
int data_length_;
DataStorage data_;
bool is_inline() const { return data_length_ == kDataLengthForInline; }
void CopyFrom(DataStorage other_data, int other_data_length) {
DCHECK_LE(other_data_length, data_length_);
if (is_inline()) {
DCHECK_EQ(other_data_length, kDataLengthForInline);
data_.inline_ = other_data.inline_;
} else if (other_data_length == kDataLengthForInline) {
data_.ptr_[0] = other_data.inline_;
for (int i = 1; i < data_length_; i++) {
data_.ptr_[i] = 0;
}
} else {
for (int i = 0; i < other_data_length; i++) {
data_.ptr_[i] = other_data.ptr_[i];
}
for (int i = other_data_length; i < data_length_; i++) {
data_.ptr_[i] = 0;
}
}
}
DISALLOW_COPY_AND_ASSIGN(BitVector);
};
class GrowableBitVector BASE_EMBEDDED {
public:
class Iterator BASE_EMBEDDED {
public:
Iterator(const GrowableBitVector* target, Zone* zone)
: it_(target->bits_ == nullptr ? new (zone) BitVector(1, zone)
: target->bits_) {}
bool Done() const { return it_.Done(); }
void Advance() { it_.Advance(); }
int Current() const { return it_.Current(); }
private:
BitVector::Iterator it_;
};
GrowableBitVector() : bits_(nullptr) {}
GrowableBitVector(int length, Zone* zone)
: bits_(new (zone) BitVector(length, zone)) {}
bool Contains(int value) const {
if (!InBitsRange(value)) return false;
return bits_->Contains(value);
}
void Add(int value, Zone* zone) {
EnsureCapacity(value, zone);
bits_->Add(value);
}
void Union(const GrowableBitVector& other, Zone* zone) {
for (Iterator it(&other, zone); !it.Done(); it.Advance()) {
Add(it.Current(), zone);
}
}
void Clear() {
if (bits_ != nullptr) bits_->Clear();
}
private:
static const int kInitialLength = 1024;
bool InBitsRange(int value) const {
return bits_ != nullptr && bits_->length() > value;
}
void EnsureCapacity(int value, Zone* zone) {
if (InBitsRange(value)) return;
int new_length = bits_ == nullptr ? kInitialLength : bits_->length();
while (new_length <= value) new_length *= 2;
if (bits_ == nullptr) {
bits_ = new (zone) BitVector(new_length, zone);
} else {
bits_->Resize(new_length, zone);
}
}
BitVector* bits_;
};
} // namespace internal
} // namespace v8
#endif // V8_DATAFLOW_H_