src/interpreter/constant-array-builder.cc - v8/v8.git - Git at Google

 // 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 <functional>
 #include <set>

 #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(
     Handle<Object> object) {
   DCHECK_GT(available(), 0u);
   size_t index = constants_.size();
   DCHECK_LT(index, capacity());
   constants_.push_back(object);
   return index + start_index();
 }

 Handle<Object> ConstantArrayBuilder::ConstantArraySlice::At(
     size_t index) const {
   DCHECK_GE(index, start_index());
   DCHECK_LT(index, start_index() + size());
   return constants_[index - start_index()];
 }

 void ConstantArrayBuilder::ConstantArraySlice::InsertAt(size_t index,
                                                         Handle<Object> object) {
   DCHECK_GE(index, start_index());
   DCHECK_LT(index, start_index() + size());
   constants_[index - start_index()] = object;
 }

 bool ConstantArrayBuilder::ConstantArraySlice::AllElementsAreUnique() const {
   std::set<Object*> elements;
   for (auto constant : constants_) {
     if (elements.find(*constant) != elements.end()) return false;
     elements.insert(*constant);
   }
   return true;
 }

 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,
                                            Handle<Object> the_hole_value)
     : constants_map_(16, base::KeyEqualityMatcher<Address>(),
                      ZoneAllocationPolicy(zone)),
       smi_map_(zone),
       smi_pairs_(zone),
       zone_(zone),
       the_hole_value_(the_hole_value) {
   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();
   return nullptr;
 }

 Handle<Object> ConstantArrayBuilder::At(size_t index) const {
   const ConstantArraySlice* slice = IndexToSlice(index);
   if (index < slice->start_index() + slice->size()) {
     return slice->At(index);
   } else {
     DCHECK_LT(index, slice->capacity());
     return the_hole_value();
   }
 }

 Handle<FixedArray> ConstantArrayBuilder::ToFixedArray(Isolate* isolate) {
   // First insert reserved SMI values.
   for (auto reserved_smi : smi_pairs_) {
     InsertAllocatedEntry(reserved_smi.second,
                          handle(reserved_smi.first, isolate));
   }

   Handle<FixedArray> fixed_array = isolate->factory()->NewFixedArray(
       static_cast<int>(size()), PretenureFlag::TENURED);
   int array_index = 0;
   for (const ConstantArraySlice* slice : idx_slice_) {
     if (array_index == fixed_array->length()) {
       break;
     }
     DCHECK(array_index == 0 ||
            base::bits::IsPowerOfTwo32(static_cast<uint32_t>(array_index)));
     // Different slices might contain the same element due to reservations, but
     // all elements within a slice should be unique. If this DCHECK fails, then
     // the AST nodes are not being internalized within a CanonicalHandleScope.
     DCHECK(slice->AllElementsAreUnique());
     // Copy objects from slice into array.
     for (size_t i = 0; i < slice->size(); ++i) {
       fixed_array->set(array_index++, *slice->At(slice->start_index() + i));
     }
     // Insert holes where reservations led to unused slots.
     size_t padding =
         std::min(static_cast<size_t>(fixed_array->length() - array_index),
                  slice->capacity() - slice->size());
     for (size_t i = 0; i < padding; i++) {
       fixed_array->set(array_index++, *the_hole_value());
     }
   }
   DCHECK_EQ(array_index, fixed_array->length());
   return fixed_array;
 }

 size_t ConstantArrayBuilder::Insert(Handle<Object> object) {
   return constants_map_
       .LookupOrInsert(object.address(), ObjectHash(object.address()),
                       [&]() { return AllocateIndex(object); },
                       ZoneAllocationPolicy(zone_))
       ->value;
 }

 ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateIndex(
     Handle<Object> object) {
   for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
     if (idx_slice_[i]->available() > 0) {
       return static_cast<index_t>(idx_slice_[i]->Allocate(object));
     }
   }
   UNREACHABLE();
   return kMaxUInt32;
 }

 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::AllocateEntry() {
   return AllocateIndex(the_hole_value());
 }

 void ConstantArrayBuilder::InsertAllocatedEntry(size_t index,
                                                 Handle<Object> object) {
   DCHECK_EQ(the_hole_value().address(), At(index).address());
   ConstantArraySlice* slice = IndexToSlice(index);
   slice->InsertAt(index, object);
 }

 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();
   return OperandSize::kNone;
 }

 ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateReservedEntry(
     Smi* value) {
   index_t index = static_cast<index_t>(AllocateEntry());
   smi_map_[value] = index;
   smi_pairs_.push_back(std::make_pair(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();
 }

 }  // namespace interpreter
 }  // namespace internal
 }  // namespace v8
	// 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 <functional>
	#include <set>

	#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(
	Handle<Object> object) {
	DCHECK_GT(available(), 0u);
	size_t index = constants_.size();
	DCHECK_LT(index, capacity());
	constants_.push_back(object);
	return index + start_index();
	}

	Handle<Object> ConstantArrayBuilder::ConstantArraySlice::At(
	size_t index) const {
	DCHECK_GE(index, start_index());
	DCHECK_LT(index, start_index() + size());
	return constants_[index - start_index()];
	}

	void ConstantArrayBuilder::ConstantArraySlice::InsertAt(size_t index,
	Handle<Object> object) {
	DCHECK_GE(index, start_index());
	DCHECK_LT(index, start_index() + size());
	constants_[index - start_index()] = object;
	}

	bool ConstantArrayBuilder::ConstantArraySlice::AllElementsAreUnique() const {
	std::set<Object*> elements;
	for (auto constant : constants_) {
	if (elements.find(*constant) != elements.end()) return false;
	elements.insert(*constant);
	}
	return true;
	}

	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,
	Handle<Object> the_hole_value)
	: constants_map_(16, base::KeyEqualityMatcher<Address>(),
	ZoneAllocationPolicy(zone)),
	smi_map_(zone),
	smi_pairs_(zone),
	zone_(zone),
	the_hole_value_(the_hole_value) {
	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();
	return nullptr;
	}

	Handle<Object> ConstantArrayBuilder::At(size_t index) const {
	const ConstantArraySlice* slice = IndexToSlice(index);
	if (index < slice->start_index() + slice->size()) {
	return slice->At(index);
	} else {
	DCHECK_LT(index, slice->capacity());
	return the_hole_value();
	}
	}

	Handle<FixedArray> ConstantArrayBuilder::ToFixedArray(Isolate* isolate) {
	// First insert reserved SMI values.
	for (auto reserved_smi : smi_pairs_) {
	InsertAllocatedEntry(reserved_smi.second,
	handle(reserved_smi.first, isolate));
	}

	Handle<FixedArray> fixed_array = isolate->factory()->NewFixedArray(
	static_cast<int>(size()), PretenureFlag::TENURED);
	int array_index = 0;
	for (const ConstantArraySlice* slice : idx_slice_) {
	if (array_index == fixed_array->length()) {
	break;
	}
	DCHECK(array_index == 0 \|\|
	base::bits::IsPowerOfTwo32(static_cast<uint32_t>(array_index)));
	// Different slices might contain the same element due to reservations, but
	// all elements within a slice should be unique. If this DCHECK fails, then
	// the AST nodes are not being internalized within a CanonicalHandleScope.
	DCHECK(slice->AllElementsAreUnique());
	// Copy objects from slice into array.
	for (size_t i = 0; i < slice->size(); ++i) {
	fixed_array->set(array_index++, *slice->At(slice->start_index() + i));
	}
	// Insert holes where reservations led to unused slots.
	size_t padding =
	std::min(static_cast<size_t>(fixed_array->length() - array_index),
	slice->capacity() - slice->size());
	for (size_t i = 0; i < padding; i++) {
	fixed_array->set(array_index++, *the_hole_value());
	}
	}
	DCHECK_EQ(array_index, fixed_array->length());
	return fixed_array;
	}

	size_t ConstantArrayBuilder::Insert(Handle<Object> object) {
	return constants_map_
	.LookupOrInsert(object.address(), ObjectHash(object.address()),
	[&]() { return AllocateIndex(object); },
	ZoneAllocationPolicy(zone_))
	->value;
	}

	ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateIndex(
	Handle<Object> object) {
	for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
	if (idx_slice_[i]->available() > 0) {
	return static_cast<index_t>(idx_slice_[i]->Allocate(object));
	}
	}
	UNREACHABLE();
	return kMaxUInt32;
	}

	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::AllocateEntry() {
	return AllocateIndex(the_hole_value());
	}

	void ConstantArrayBuilder::InsertAllocatedEntry(size_t index,
	Handle<Object> object) {
	DCHECK_EQ(the_hole_value().address(), At(index).address());
	ConstantArraySlice* slice = IndexToSlice(index);
	slice->InsertAt(index, object);
	}

	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();
	return OperandSize::kNone;
	}

	ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateReservedEntry(
	Smi* value) {
	index_t index = static_cast<index_t>(AllocateEntry());
	smi_map_[value] = index;
	smi_pairs_.push_back(std::make_pair(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();
	}

	} // namespace interpreter
	} // namespace internal
	} // namespace v8