Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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 | |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 14 | ConstantArrayBuilder::ConstantArraySlice::ConstantArraySlice( |
| 15 | Zone* zone, size_t start_index, size_t capacity, OperandSize operand_size) |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 16 | : start_index_(start_index), |
| 17 | capacity_(capacity), |
| 18 | reserved_(0), |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 19 | operand_size_(operand_size), |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 20 | constants_(zone) {} |
| 21 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 22 | void ConstantArrayBuilder::ConstantArraySlice::Reserve() { |
| 23 | DCHECK_GT(available(), 0u); |
| 24 | reserved_++; |
| 25 | DCHECK_LE(reserved_, capacity() - constants_.size()); |
| 26 | } |
| 27 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 28 | void ConstantArrayBuilder::ConstantArraySlice::Unreserve() { |
| 29 | DCHECK_GT(reserved_, 0u); |
| 30 | reserved_--; |
| 31 | } |
| 32 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 42 | Handle<Object> ConstantArrayBuilder::ConstantArraySlice::At( |
| 43 | size_t index) const { |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 44 | DCHECK_GE(index, start_index()); |
| 45 | DCHECK_LT(index, start_index() + size()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 46 | return constants_[index - start_index()]; |
| 47 | } |
| 48 | |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 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; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 54 | |
| 55 | ConstantArrayBuilder::ConstantArrayBuilder(Isolate* isolate, Zone* zone) |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 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); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 63 | } |
| 64 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 65 | size_t ConstantArrayBuilder::size() const { |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 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 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 72 | } |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 73 | return idx_slice_[0]->size(); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 74 | } |
| 75 | |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 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 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 86 | |
| 87 | Handle<Object> ConstantArrayBuilder::At(size_t index) const { |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 88 | const ConstantArraySlice* slice = IndexToSlice(index); |
| 89 | if (index < slice->start_index() + slice->size()) { |
| 90 | return slice->At(index); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 91 | } else { |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 92 | DCHECK_LT(index, slice->capacity()); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 93 | return isolate_->factory()->the_hole_value(); |
| 94 | } |
| 95 | } |
| 96 | |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 97 | Handle<FixedArray> ConstantArrayBuilder::ToFixedArray() { |
| 98 | Handle<FixedArray> fixed_array = isolate_->factory()->NewFixedArray( |
| 99 | static_cast<int>(size()), PretenureFlag::TENURED); |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 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 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 118 | } |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 119 | DCHECK_EQ(array_index, fixed_array->length()); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 120 | constants_map()->Clear(); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 121 | return fixed_array; |
| 122 | } |
| 123 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 124 | size_t ConstantArrayBuilder::Insert(Handle<Object> object) { |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 125 | index_t* entry = constants_map()->Find(object); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 126 | return (entry == nullptr) ? AllocateEntry(object) : *entry; |
| 127 | } |
| 128 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 129 | ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateEntry( |
| 130 | Handle<Object> object) { |
| 131 | DCHECK(!object->IsOddball()); |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 132 | index_t* entry = constants_map()->Get(object); |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 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 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 140 | } |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 141 | UNREACHABLE(); |
| 142 | return kMaxUInt32; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 143 | } |
| 144 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 145 | OperandSize ConstantArrayBuilder::CreateReservedEntry() { |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 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 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 151 | } |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 152 | UNREACHABLE(); |
| 153 | return OperandSize::kNone; |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 154 | } |
| 155 | |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 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 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 176 | |
| 177 | size_t ConstantArrayBuilder::CommitReservedEntry(OperandSize operand_size, |
| 178 | Handle<Object> object) { |
| 179 | DiscardReservedEntry(operand_size); |
| 180 | size_t index; |
Ben Murdoch | 097c5b2 | 2016-05-18 11:27:45 +0100 | [diff] [blame] | 181 | index_t* entry = constants_map()->Find(object); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 182 | if (nullptr == entry) { |
| 183 | index = AllocateEntry(object); |
| 184 | } else { |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 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)); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 191 | } |
| 192 | index = *entry; |
| 193 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 194 | return index; |
| 195 | } |
| 196 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 197 | void ConstantArrayBuilder::DiscardReservedEntry(OperandSize operand_size) { |
Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 198 | OperandSizeToSlice(operand_size)->Unreserve(); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 199 | } |
| 200 | |
| 201 | } // namespace interpreter |
| 202 | } // namespace internal |
| 203 | } // namespace v8 |