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
ConstantArraySlice(Zone * zone,size_t start_index,size_t capacity,OperandSize operand_size)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
Reserve()22 void ConstantArrayBuilder::ConstantArraySlice::Reserve() {
23 DCHECK_GT(available(), 0u);
24 reserved_++;
25 DCHECK_LE(reserved_, capacity() - constants_.size());
26 }
27
Unreserve()28 void ConstantArrayBuilder::ConstantArraySlice::Unreserve() {
29 DCHECK_GT(reserved_, 0u);
30 reserved_--;
31 }
32
Allocate(Handle<Object> object)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
At(size_t index) const42 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
ConstantArrayBuilder(Isolate * isolate,Zone * zone)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
size() const65 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*
IndexToSlice(size_t index) const77 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
At(size_t index) const87 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
ToFixedArray()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
Insert(Handle<Object> object)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
AllocateEntry(Handle<Object> object)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
CreateReservedEntry()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*
OperandSizeToSlice(OperandSize operand_size) const157 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
CommitReservedEntry(OperandSize operand_size,Handle<Object> object)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
DiscardReservedEntry(OperandSize operand_size)197 void ConstantArrayBuilder::DiscardReservedEntry(OperandSize operand_size) {
198 OperandSizeToSlice(operand_size)->Unreserve();
199 }
200
201 } // namespace interpreter
202 } // namespace internal
203 } // namespace v8
204