1// Copyright 2015 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#include "src/interpreter/constant-array-builder.h" 6 7#include "src/isolate.h" 8#include "src/objects-inl.h" 9 10namespace v8 { 11namespace internal { 12namespace interpreter { 13 14ConstantArrayBuilder::ConstantArraySlice::ConstantArraySlice( 15 Zone* zone, size_t start_index, size_t capacity, OperandSize operand_size) 16 : start_index_(start_index), 17 capacity_(capacity), 18 reserved_(0), 19 operand_size_(operand_size), 20 constants_(zone) {} 21 22void ConstantArrayBuilder::ConstantArraySlice::Reserve() { 23 DCHECK_GT(available(), 0u); 24 reserved_++; 25 DCHECK_LE(reserved_, capacity() - constants_.size()); 26} 27 28void ConstantArrayBuilder::ConstantArraySlice::Unreserve() { 29 DCHECK_GT(reserved_, 0u); 30 reserved_--; 31} 32 33size_t ConstantArrayBuilder::ConstantArraySlice::Allocate( 34 Handle<Object> object) { 35 DCHECK_GT(available(), 0u); 36 size_t index = constants_.size(); 37 DCHECK_LT(index, capacity()); 38 constants_.push_back(object); 39 return index + start_index(); 40} 41 42Handle<Object> ConstantArrayBuilder::ConstantArraySlice::At( 43 size_t index) const { 44 DCHECK_GE(index, start_index()); 45 DCHECK_LT(index, start_index() + size()); 46 return constants_[index - start_index()]; 47} 48 49STATIC_CONST_MEMBER_DEFINITION const size_t ConstantArrayBuilder::k8BitCapacity; 50STATIC_CONST_MEMBER_DEFINITION const size_t 51 ConstantArrayBuilder::k16BitCapacity; 52STATIC_CONST_MEMBER_DEFINITION const size_t 53 ConstantArrayBuilder::k32BitCapacity; 54 55ConstantArrayBuilder::ConstantArrayBuilder(Isolate* isolate, Zone* zone) 56 : isolate_(isolate), constants_map_(isolate->heap(), zone) { 57 idx_slice_[0] = 58 new (zone) ConstantArraySlice(zone, 0, k8BitCapacity, OperandSize::kByte); 59 idx_slice_[1] = new (zone) ConstantArraySlice( 60 zone, k8BitCapacity, k16BitCapacity, OperandSize::kShort); 61 idx_slice_[2] = new (zone) ConstantArraySlice( 62 zone, k8BitCapacity + k16BitCapacity, k32BitCapacity, OperandSize::kQuad); 63} 64 65size_t ConstantArrayBuilder::size() const { 66 size_t i = arraysize(idx_slice_); 67 while (i > 0) { 68 ConstantArraySlice* slice = idx_slice_[--i]; 69 if (slice->size() > 0) { 70 return slice->start_index() + slice->size(); 71 } 72 } 73 return idx_slice_[0]->size(); 74} 75 76const ConstantArrayBuilder::ConstantArraySlice* 77ConstantArrayBuilder::IndexToSlice(size_t index) const { 78 for (const ConstantArraySlice* slice : idx_slice_) { 79 if (index <= slice->max_index()) { 80 return slice; 81 } 82 } 83 UNREACHABLE(); 84 return nullptr; 85} 86 87Handle<Object> ConstantArrayBuilder::At(size_t index) const { 88 const ConstantArraySlice* slice = IndexToSlice(index); 89 if (index < slice->start_index() + slice->size()) { 90 return slice->At(index); 91 } else { 92 DCHECK_LT(index, slice->capacity()); 93 return isolate_->factory()->the_hole_value(); 94 } 95} 96 97Handle<FixedArray> ConstantArrayBuilder::ToFixedArray() { 98 Handle<FixedArray> fixed_array = isolate_->factory()->NewFixedArray( 99 static_cast<int>(size()), PretenureFlag::TENURED); 100 int array_index = 0; 101 for (const ConstantArraySlice* slice : idx_slice_) { 102 if (array_index == fixed_array->length()) { 103 break; 104 } 105 DCHECK(array_index == 0 || 106 base::bits::IsPowerOfTwo32(static_cast<uint32_t>(array_index))); 107 // Copy objects from slice into array. 108 for (size_t i = 0; i < slice->size(); ++i) { 109 fixed_array->set(array_index++, *slice->At(slice->start_index() + i)); 110 } 111 // Insert holes where reservations led to unused slots. 112 size_t padding = 113 std::min(static_cast<size_t>(fixed_array->length() - array_index), 114 slice->capacity() - slice->size()); 115 for (size_t i = 0; i < padding; i++) { 116 fixed_array->set(array_index++, *isolate_->factory()->the_hole_value()); 117 } 118 } 119 DCHECK_EQ(array_index, fixed_array->length()); 120 constants_map()->Clear(); 121 return fixed_array; 122} 123 124size_t ConstantArrayBuilder::Insert(Handle<Object> object) { 125 index_t* entry = constants_map()->Find(object); 126 return (entry == nullptr) ? AllocateEntry(object) : *entry; 127} 128 129ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateEntry( 130 Handle<Object> object) { 131 DCHECK(!object->IsOddball()); 132 index_t* entry = constants_map()->Get(object); 133 for (size_t i = 0; i < arraysize(idx_slice_); ++i) { 134 if (idx_slice_[i]->available() > 0) { 135 size_t index = idx_slice_[i]->Allocate(object); 136 *entry = static_cast<index_t>(index); 137 return *entry; 138 break; 139 } 140 } 141 UNREACHABLE(); 142 return kMaxUInt32; 143} 144 145OperandSize ConstantArrayBuilder::CreateReservedEntry() { 146 for (size_t i = 0; i < arraysize(idx_slice_); ++i) { 147 if (idx_slice_[i]->available() > 0) { 148 idx_slice_[i]->Reserve(); 149 return idx_slice_[i]->operand_size(); 150 } 151 } 152 UNREACHABLE(); 153 return OperandSize::kNone; 154} 155 156ConstantArrayBuilder::ConstantArraySlice* 157ConstantArrayBuilder::OperandSizeToSlice(OperandSize operand_size) const { 158 ConstantArraySlice* slice = nullptr; 159 switch (operand_size) { 160 case OperandSize::kNone: 161 UNREACHABLE(); 162 break; 163 case OperandSize::kByte: 164 slice = idx_slice_[0]; 165 break; 166 case OperandSize::kShort: 167 slice = idx_slice_[1]; 168 break; 169 case OperandSize::kQuad: 170 slice = idx_slice_[2]; 171 break; 172 } 173 DCHECK(slice->operand_size() == operand_size); 174 return slice; 175} 176 177size_t ConstantArrayBuilder::CommitReservedEntry(OperandSize operand_size, 178 Handle<Object> object) { 179 DiscardReservedEntry(operand_size); 180 size_t index; 181 index_t* entry = constants_map()->Find(object); 182 if (nullptr == entry) { 183 index = AllocateEntry(object); 184 } else { 185 ConstantArraySlice* slice = OperandSizeToSlice(operand_size); 186 if (*entry > slice->max_index()) { 187 // The object is already in the constant array, but may have an 188 // index too big for the reserved operand_size. So, duplicate 189 // entry with the smaller operand size. 190 *entry = static_cast<index_t>(slice->Allocate(object)); 191 } 192 index = *entry; 193 } 194 return index; 195} 196 197void ConstantArrayBuilder::DiscardReservedEntry(OperandSize operand_size) { 198 OperandSizeToSlice(operand_size)->Unreserve(); 199} 200 201} // namespace interpreter 202} // namespace internal 203} // namespace v8 204