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 10 namespace v8 { 11 namespace internal { 12 namespace interpreter { 13 14 ConstantArrayBuilder::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 22 void ConstantArrayBuilder::ConstantArraySlice::Reserve() { 23 DCHECK_GT(available(), 0u); 24 reserved_++; 25 DCHECK_LE(reserved_, capacity() - constants_.size()); 26 } 27 28 void ConstantArrayBuilder::ConstantArraySlice::Unreserve() { 29 DCHECK_GT(reserved_, 0u); 30 reserved_--; 31 } 32 33 size_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 42 Handle<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 49 STATIC_CONST_MEMBER_DEFINITION const size_t ConstantArrayBuilder::k8BitCapacity; 50 STATIC_CONST_MEMBER_DEFINITION const size_t 51 ConstantArrayBuilder::k16BitCapacity; 52 STATIC_CONST_MEMBER_DEFINITION const size_t 53 ConstantArrayBuilder::k32BitCapacity; 54 55 ConstantArrayBuilder::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 65 size_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 76 const ConstantArrayBuilder::ConstantArraySlice* 77 ConstantArrayBuilder::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 87 Handle<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 97 Handle<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 124 size_t ConstantArrayBuilder::Insert(Handle<Object> object) { 125 index_t* entry = constants_map()->Find(object); 126 return (entry == nullptr) ? AllocateEntry(object) : *entry; 127 } 128 129 ConstantArrayBuilder::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 145 OperandSize 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 156 ConstantArrayBuilder::ConstantArraySlice* 157 ConstantArrayBuilder::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 177 size_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 197 void ConstantArrayBuilder::DiscardReservedEntry(OperandSize operand_size) { 198 OperandSizeToSlice(operand_size)->Unreserve(); 199 } 200 201 } // namespace interpreter 202 } // namespace internal 203 } // namespace v8 204
