blob: 8e37f0d48aa842d4684c963159adbaab963114af [file] [log] [blame]
// Copyright 2015 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.
#include "src/interpreter/constant-array-builder.h"
#include <cmath>
#include <functional>
#include <set>
#include "src/ast/ast-value-factory.h"
#include "src/ast/ast.h"
#include "src/ast/scopes.h"
#include "src/base/functional.h"
#include "src/isolate.h"
#include "src/objects-inl.h"
namespace v8 {
namespace internal {
namespace interpreter {
ConstantArrayBuilder::ConstantArraySlice::ConstantArraySlice(
Zone* zone, size_t start_index, size_t capacity, OperandSize operand_size)
: start_index_(start_index),
capacity_(capacity),
reserved_(0),
operand_size_(operand_size),
constants_(zone) {}
void ConstantArrayBuilder::ConstantArraySlice::Reserve() {
DCHECK_GT(available(), 0u);
reserved_++;
DCHECK_LE(reserved_, capacity() - constants_.size());
}
void ConstantArrayBuilder::ConstantArraySlice::Unreserve() {
DCHECK_GT(reserved_, 0u);
reserved_--;
}
size_t ConstantArrayBuilder::ConstantArraySlice::Allocate(
ConstantArrayBuilder::Entry entry, size_t count) {
DCHECK_GE(available(), count);
size_t index = constants_.size();
DCHECK_LT(index, capacity());
for (size_t i = 0; i < count; ++i) {
constants_.push_back(entry);
}
return index + start_index();
}
ConstantArrayBuilder::Entry& ConstantArrayBuilder::ConstantArraySlice::At(
size_t index) {
DCHECK_GE(index, start_index());
DCHECK_LT(index, start_index() + size());
return constants_[index - start_index()];
}
const ConstantArrayBuilder::Entry& ConstantArrayBuilder::ConstantArraySlice::At(
size_t index) const {
DCHECK_GE(index, start_index());
DCHECK_LT(index, start_index() + size());
return constants_[index - start_index()];
}
#if DEBUG
void ConstantArrayBuilder::ConstantArraySlice::CheckAllElementsAreUnique(
Isolate* isolate) const {
std::set<Smi> smis;
std::set<double> heap_numbers;
std::set<const AstRawString*> strings;
std::set<const char*> bigints;
std::set<const Scope*> scopes;
std::set<Object, Object::Comparer> deferred_objects;
for (const Entry& entry : constants_) {
bool duplicate = false;
switch (entry.tag_) {
case Entry::Tag::kSmi:
duplicate = !smis.insert(entry.smi_).second;
break;
case Entry::Tag::kHeapNumber:
duplicate = !heap_numbers.insert(entry.heap_number_).second;
break;
case Entry::Tag::kRawString:
duplicate = !strings.insert(entry.raw_string_).second;
break;
case Entry::Tag::kBigInt:
duplicate = !bigints.insert(entry.bigint_.c_str()).second;
break;
case Entry::Tag::kScope:
duplicate = !scopes.insert(entry.scope_).second;
break;
case Entry::Tag::kHandle:
duplicate = !deferred_objects.insert(*entry.handle_).second;
break;
case Entry::Tag::kDeferred:
UNREACHABLE(); // Should be kHandle at this point.
case Entry::Tag::kJumpTableSmi:
case Entry::Tag::kUninitializedJumpTableSmi:
// TODO(leszeks): Ignore jump tables because they have to be contiguous,
// so they can contain duplicates.
break;
#define CASE_TAG(NAME, ...) case Entry::Tag::k##NAME:
SINGLETON_CONSTANT_ENTRY_TYPES(CASE_TAG)
#undef CASE_TAG
// Singletons are non-duplicated by definition.
break;
}
if (duplicate) {
std::ostringstream os;
os << "Duplicate constant found: " << Brief(*entry.ToHandle(isolate))
<< std::endl;
// Print all the entries in the slice to help debug duplicates.
size_t i = start_index();
for (const Entry& prev_entry : constants_) {
os << i++ << ": " << Brief(*prev_entry.ToHandle(isolate)) << std::endl;
}
FATAL("%s", os.str().c_str());
}
}
}
#endif
STATIC_CONST_MEMBER_DEFINITION const size_t ConstantArrayBuilder::k8BitCapacity;
STATIC_CONST_MEMBER_DEFINITION const size_t
ConstantArrayBuilder::k16BitCapacity;
STATIC_CONST_MEMBER_DEFINITION const size_t
ConstantArrayBuilder::k32BitCapacity;
ConstantArrayBuilder::ConstantArrayBuilder(Zone* zone)
: constants_map_(16, base::KeyEqualityMatcher<intptr_t>(),
ZoneAllocationPolicy(zone)),
smi_map_(zone),
smi_pairs_(zone),
heap_number_map_(zone),
#define INIT_SINGLETON_ENTRY_FIELD(NAME, LOWER_NAME) LOWER_NAME##_(-1),
SINGLETON_CONSTANT_ENTRY_TYPES(INIT_SINGLETON_ENTRY_FIELD)
#undef INIT_SINGLETON_ENTRY_FIELD
zone_(zone) {
idx_slice_[0] =
new (zone) ConstantArraySlice(zone, 0, k8BitCapacity, OperandSize::kByte);
idx_slice_[1] = new (zone) ConstantArraySlice(
zone, k8BitCapacity, k16BitCapacity, OperandSize::kShort);
idx_slice_[2] = new (zone) ConstantArraySlice(
zone, k8BitCapacity + k16BitCapacity, k32BitCapacity, OperandSize::kQuad);
}
size_t ConstantArrayBuilder::size() const {
size_t i = arraysize(idx_slice_);
while (i > 0) {
ConstantArraySlice* slice = idx_slice_[--i];
if (slice->size() > 0) {
return slice->start_index() + slice->size();
}
}
return idx_slice_[0]->size();
}
ConstantArrayBuilder::ConstantArraySlice* ConstantArrayBuilder::IndexToSlice(
size_t index) const {
for (ConstantArraySlice* slice : idx_slice_) {
if (index <= slice->max_index()) {
return slice;
}
}
UNREACHABLE();
}
MaybeHandle<Object> ConstantArrayBuilder::At(size_t index,
Isolate* isolate) const {
const ConstantArraySlice* slice = IndexToSlice(index);
DCHECK_LT(index, slice->capacity());
if (index < slice->start_index() + slice->size()) {
const Entry& entry = slice->At(index);
if (!entry.IsDeferred()) return entry.ToHandle(isolate);
}
return MaybeHandle<Object>();
}
Handle<FixedArray> ConstantArrayBuilder::ToFixedArray(Isolate* isolate) {
Handle<FixedArray> fixed_array = isolate->factory()->NewFixedArrayWithHoles(
static_cast<int>(size()), AllocationType::kOld);
int array_index = 0;
for (const ConstantArraySlice* slice : idx_slice_) {
DCHECK_EQ(slice->reserved(), 0);
DCHECK(array_index == 0 ||
base::bits::IsPowerOfTwo(static_cast<uint32_t>(array_index)));
#if DEBUG
// Different slices might contain the same element due to reservations, but
// all elements within a slice should be unique.
slice->CheckAllElementsAreUnique(isolate);
#endif
// Copy objects from slice into array.
for (size_t i = 0; i < slice->size(); ++i) {
Handle<Object> value =
slice->At(slice->start_index() + i).ToHandle(isolate);
fixed_array->set(array_index++, *value);
}
// Leave holes where reservations led to unused slots.
size_t padding = slice->capacity() - slice->size();
if (static_cast<size_t>(fixed_array->length() - array_index) <= padding) {
break;
}
array_index += padding;
}
DCHECK_GE(array_index, fixed_array->length());
return fixed_array;
}
size_t ConstantArrayBuilder::Insert(Smi smi) {
auto entry = smi_map_.find(smi);
if (entry == smi_map_.end()) {
return AllocateReservedEntry(smi);
}
return entry->second;
}
size_t ConstantArrayBuilder::Insert(double number) {
if (std::isnan(number)) return InsertNaN();
auto entry = heap_number_map_.find(number);
if (entry == heap_number_map_.end()) {
index_t index = static_cast<index_t>(AllocateIndex(Entry(number)));
heap_number_map_[number] = index;
return index;
}
return entry->second;
}
size_t ConstantArrayBuilder::Insert(const AstRawString* raw_string) {
return constants_map_
.LookupOrInsert(reinterpret_cast<intptr_t>(raw_string),
raw_string->Hash(),
[&]() { return AllocateIndex(Entry(raw_string)); },
ZoneAllocationPolicy(zone_))
->value;
}
size_t ConstantArrayBuilder::Insert(AstBigInt bigint) {
return constants_map_
.LookupOrInsert(reinterpret_cast<intptr_t>(bigint.c_str()),
static_cast<uint32_t>(base::hash_value(bigint.c_str())),
[&]() { return AllocateIndex(Entry(bigint)); },
ZoneAllocationPolicy(zone_))
->value;
}
size_t ConstantArrayBuilder::Insert(const Scope* scope) {
return constants_map_
.LookupOrInsert(reinterpret_cast<intptr_t>(scope),
static_cast<uint32_t>(base::hash_value(scope)),
[&]() { return AllocateIndex(Entry(scope)); },
ZoneAllocationPolicy(zone_))
->value;
}
#define INSERT_ENTRY(NAME, LOWER_NAME) \
size_t ConstantArrayBuilder::Insert##NAME() { \
if (LOWER_NAME##_ < 0) { \
LOWER_NAME##_ = AllocateIndex(Entry::NAME()); \
} \
return LOWER_NAME##_; \
}
SINGLETON_CONSTANT_ENTRY_TYPES(INSERT_ENTRY)
#undef INSERT_ENTRY
ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateIndex(
ConstantArrayBuilder::Entry entry) {
return AllocateIndexArray(entry, 1);
}
ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateIndexArray(
ConstantArrayBuilder::Entry entry, size_t count) {
for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
if (idx_slice_[i]->available() >= count) {
return static_cast<index_t>(idx_slice_[i]->Allocate(entry, count));
}
}
UNREACHABLE();
}
ConstantArrayBuilder::ConstantArraySlice*
ConstantArrayBuilder::OperandSizeToSlice(OperandSize operand_size) const {
ConstantArraySlice* slice = nullptr;
switch (operand_size) {
case OperandSize::kNone:
UNREACHABLE();
break;
case OperandSize::kByte:
slice = idx_slice_[0];
break;
case OperandSize::kShort:
slice = idx_slice_[1];
break;
case OperandSize::kQuad:
slice = idx_slice_[2];
break;
}
DCHECK(slice->operand_size() == operand_size);
return slice;
}
size_t ConstantArrayBuilder::InsertDeferred() {
return AllocateIndex(Entry::Deferred());
}
size_t ConstantArrayBuilder::InsertJumpTable(size_t size) {
return AllocateIndexArray(Entry::UninitializedJumpTableSmi(), size);
}
void ConstantArrayBuilder::SetDeferredAt(size_t index, Handle<Object> object) {
ConstantArraySlice* slice = IndexToSlice(index);
return slice->At(index).SetDeferred(object);
}
void ConstantArrayBuilder::SetJumpTableSmi(size_t index, Smi smi) {
ConstantArraySlice* slice = IndexToSlice(index);
// Allow others to reuse these Smis, but insert using emplace to avoid
// overwriting existing values in the Smi map (which may have a smaller
// operand size).
smi_map_.emplace(smi, static_cast<index_t>(index));
return slice->At(index).SetJumpTableSmi(smi);
}
OperandSize ConstantArrayBuilder::CreateReservedEntry() {
for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
if (idx_slice_[i]->available() > 0) {
idx_slice_[i]->Reserve();
return idx_slice_[i]->operand_size();
}
}
UNREACHABLE();
}
ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateReservedEntry(
Smi value) {
index_t index = static_cast<index_t>(AllocateIndex(Entry(value)));
smi_map_[value] = index;
return index;
}
size_t ConstantArrayBuilder::CommitReservedEntry(OperandSize operand_size,
Smi value) {
DiscardReservedEntry(operand_size);
size_t index;
auto entry = smi_map_.find(value);
if (entry == smi_map_.end()) {
index = AllocateReservedEntry(value);
} else {
ConstantArraySlice* slice = OperandSizeToSlice(operand_size);
index = entry->second;
if (index > slice->max_index()) {
// The object is already in the constant array, but may have an
// index too big for the reserved operand_size. So, duplicate
// entry with the smaller operand size.
index = AllocateReservedEntry(value);
}
DCHECK_LE(index, slice->max_index());
}
return index;
}
void ConstantArrayBuilder::DiscardReservedEntry(OperandSize operand_size) {
OperandSizeToSlice(operand_size)->Unreserve();
}
Handle<Object> ConstantArrayBuilder::Entry::ToHandle(Isolate* isolate) const {
switch (tag_) {
case Tag::kDeferred:
// We shouldn't have any deferred entries by now.
UNREACHABLE();
case Tag::kHandle:
return handle_;
case Tag::kSmi:
case Tag::kJumpTableSmi:
return handle(smi_, isolate);
case Tag::kUninitializedJumpTableSmi:
// TODO(leszeks): There's probably a better value we could use here.
return isolate->factory()->the_hole_value();
case Tag::kRawString:
return raw_string_->string();
case Tag::kHeapNumber:
return isolate->factory()->NewNumber(heap_number_, AllocationType::kOld);
case Tag::kBigInt:
// This should never fail: the parser will never create a BigInt
// literal that cannot be allocated.
return BigIntLiteral(isolate, bigint_.c_str()).ToHandleChecked();
case Tag::kScope:
return scope_->scope_info();
#define ENTRY_LOOKUP(Name, name) \
case Tag::k##Name: \
return isolate->factory()->name();
SINGLETON_CONSTANT_ENTRY_TYPES(ENTRY_LOOKUP);
#undef ENTRY_LOOKUP
}
UNREACHABLE();
}
} // namespace interpreter
} // namespace internal
} // namespace v8