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 <functional>
8 #include <set>
9
10 #include "src/isolate.h"
11 #include "src/objects-inl.h"
12
13 namespace v8 {
14 namespace internal {
15 namespace interpreter {
16
ConstantArraySlice(Zone * zone,size_t start_index,size_t capacity,OperandSize operand_size)17 ConstantArrayBuilder::ConstantArraySlice::ConstantArraySlice(
18 Zone* zone, size_t start_index, size_t capacity, OperandSize operand_size)
19 : start_index_(start_index),
20 capacity_(capacity),
21 reserved_(0),
22 operand_size_(operand_size),
23 constants_(zone) {}
24
Reserve()25 void ConstantArrayBuilder::ConstantArraySlice::Reserve() {
26 DCHECK_GT(available(), 0u);
27 reserved_++;
28 DCHECK_LE(reserved_, capacity() - constants_.size());
29 }
30
Unreserve()31 void ConstantArrayBuilder::ConstantArraySlice::Unreserve() {
32 DCHECK_GT(reserved_, 0u);
33 reserved_--;
34 }
35
Allocate(Handle<Object> object)36 size_t ConstantArrayBuilder::ConstantArraySlice::Allocate(
37 Handle<Object> object) {
38 DCHECK_GT(available(), 0u);
39 size_t index = constants_.size();
40 DCHECK_LT(index, capacity());
41 constants_.push_back(object);
42 return index + start_index();
43 }
44
At(size_t index) const45 Handle<Object> ConstantArrayBuilder::ConstantArraySlice::At(
46 size_t index) const {
47 DCHECK_GE(index, start_index());
48 DCHECK_LT(index, start_index() + size());
49 return constants_[index - start_index()];
50 }
51
InsertAt(size_t index,Handle<Object> object)52 void ConstantArrayBuilder::ConstantArraySlice::InsertAt(size_t index,
53 Handle<Object> object) {
54 DCHECK_GE(index, start_index());
55 DCHECK_LT(index, start_index() + size());
56 constants_[index - start_index()] = object;
57 }
58
AllElementsAreUnique() const59 bool ConstantArrayBuilder::ConstantArraySlice::AllElementsAreUnique() const {
60 std::set<Object*> elements;
61 for (auto constant : constants_) {
62 if (elements.find(*constant) != elements.end()) return false;
63 elements.insert(*constant);
64 }
65 return true;
66 }
67
68 STATIC_CONST_MEMBER_DEFINITION const size_t ConstantArrayBuilder::k8BitCapacity;
69 STATIC_CONST_MEMBER_DEFINITION const size_t
70 ConstantArrayBuilder::k16BitCapacity;
71 STATIC_CONST_MEMBER_DEFINITION const size_t
72 ConstantArrayBuilder::k32BitCapacity;
73
ConstantArrayBuilder(Zone * zone,Handle<Object> the_hole_value)74 ConstantArrayBuilder::ConstantArrayBuilder(Zone* zone,
75 Handle<Object> the_hole_value)
76 : constants_map_(16, base::KeyEqualityMatcher<Address>(),
77 ZoneAllocationPolicy(zone)),
78 smi_map_(zone),
79 smi_pairs_(zone),
80 zone_(zone),
81 the_hole_value_(the_hole_value) {
82 idx_slice_[0] =
83 new (zone) ConstantArraySlice(zone, 0, k8BitCapacity, OperandSize::kByte);
84 idx_slice_[1] = new (zone) ConstantArraySlice(
85 zone, k8BitCapacity, k16BitCapacity, OperandSize::kShort);
86 idx_slice_[2] = new (zone) ConstantArraySlice(
87 zone, k8BitCapacity + k16BitCapacity, k32BitCapacity, OperandSize::kQuad);
88 }
89
size() const90 size_t ConstantArrayBuilder::size() const {
91 size_t i = arraysize(idx_slice_);
92 while (i > 0) {
93 ConstantArraySlice* slice = idx_slice_[--i];
94 if (slice->size() > 0) {
95 return slice->start_index() + slice->size();
96 }
97 }
98 return idx_slice_[0]->size();
99 }
100
IndexToSlice(size_t index) const101 ConstantArrayBuilder::ConstantArraySlice* ConstantArrayBuilder::IndexToSlice(
102 size_t index) const {
103 for (ConstantArraySlice* slice : idx_slice_) {
104 if (index <= slice->max_index()) {
105 return slice;
106 }
107 }
108 UNREACHABLE();
109 return nullptr;
110 }
111
At(size_t index) const112 Handle<Object> ConstantArrayBuilder::At(size_t index) const {
113 const ConstantArraySlice* slice = IndexToSlice(index);
114 if (index < slice->start_index() + slice->size()) {
115 return slice->At(index);
116 } else {
117 DCHECK_LT(index, slice->capacity());
118 return the_hole_value();
119 }
120 }
121
ToFixedArray(Isolate * isolate)122 Handle<FixedArray> ConstantArrayBuilder::ToFixedArray(Isolate* isolate) {
123 // First insert reserved SMI values.
124 for (auto reserved_smi : smi_pairs_) {
125 InsertAllocatedEntry(reserved_smi.second,
126 handle(reserved_smi.first, isolate));
127 }
128
129 Handle<FixedArray> fixed_array = isolate->factory()->NewFixedArray(
130 static_cast<int>(size()), PretenureFlag::TENURED);
131 int array_index = 0;
132 for (const ConstantArraySlice* slice : idx_slice_) {
133 if (array_index == fixed_array->length()) {
134 break;
135 }
136 DCHECK(array_index == 0 ||
137 base::bits::IsPowerOfTwo32(static_cast<uint32_t>(array_index)));
138 // Different slices might contain the same element due to reservations, but
139 // all elements within a slice should be unique. If this DCHECK fails, then
140 // the AST nodes are not being internalized within a CanonicalHandleScope.
141 DCHECK(slice->AllElementsAreUnique());
142 // Copy objects from slice into array.
143 for (size_t i = 0; i < slice->size(); ++i) {
144 fixed_array->set(array_index++, *slice->At(slice->start_index() + i));
145 }
146 // Insert holes where reservations led to unused slots.
147 size_t padding =
148 std::min(static_cast<size_t>(fixed_array->length() - array_index),
149 slice->capacity() - slice->size());
150 for (size_t i = 0; i < padding; i++) {
151 fixed_array->set(array_index++, *the_hole_value());
152 }
153 }
154 DCHECK_EQ(array_index, fixed_array->length());
155 return fixed_array;
156 }
157
Insert(Handle<Object> object)158 size_t ConstantArrayBuilder::Insert(Handle<Object> object) {
159 return constants_map_
160 .LookupOrInsert(object.address(), ObjectHash(object.address()),
161 [&]() { return AllocateIndex(object); },
162 ZoneAllocationPolicy(zone_))
163 ->value;
164 }
165
AllocateIndex(Handle<Object> object)166 ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateIndex(
167 Handle<Object> object) {
168 for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
169 if (idx_slice_[i]->available() > 0) {
170 return static_cast<index_t>(idx_slice_[i]->Allocate(object));
171 }
172 }
173 UNREACHABLE();
174 return kMaxUInt32;
175 }
176
177 ConstantArrayBuilder::ConstantArraySlice*
OperandSizeToSlice(OperandSize operand_size) const178 ConstantArrayBuilder::OperandSizeToSlice(OperandSize operand_size) const {
179 ConstantArraySlice* slice = nullptr;
180 switch (operand_size) {
181 case OperandSize::kNone:
182 UNREACHABLE();
183 break;
184 case OperandSize::kByte:
185 slice = idx_slice_[0];
186 break;
187 case OperandSize::kShort:
188 slice = idx_slice_[1];
189 break;
190 case OperandSize::kQuad:
191 slice = idx_slice_[2];
192 break;
193 }
194 DCHECK(slice->operand_size() == operand_size);
195 return slice;
196 }
197
AllocateEntry()198 size_t ConstantArrayBuilder::AllocateEntry() {
199 return AllocateIndex(the_hole_value());
200 }
201
InsertAllocatedEntry(size_t index,Handle<Object> object)202 void ConstantArrayBuilder::InsertAllocatedEntry(size_t index,
203 Handle<Object> object) {
204 DCHECK_EQ(the_hole_value().address(), At(index).address());
205 ConstantArraySlice* slice = IndexToSlice(index);
206 slice->InsertAt(index, object);
207 }
208
CreateReservedEntry()209 OperandSize ConstantArrayBuilder::CreateReservedEntry() {
210 for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
211 if (idx_slice_[i]->available() > 0) {
212 idx_slice_[i]->Reserve();
213 return idx_slice_[i]->operand_size();
214 }
215 }
216 UNREACHABLE();
217 return OperandSize::kNone;
218 }
219
AllocateReservedEntry(Smi * value)220 ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateReservedEntry(
221 Smi* value) {
222 index_t index = static_cast<index_t>(AllocateEntry());
223 smi_map_[value] = index;
224 smi_pairs_.push_back(std::make_pair(value, index));
225 return index;
226 }
227
CommitReservedEntry(OperandSize operand_size,Smi * value)228 size_t ConstantArrayBuilder::CommitReservedEntry(OperandSize operand_size,
229 Smi* value) {
230 DiscardReservedEntry(operand_size);
231 size_t index;
232 auto entry = smi_map_.find(value);
233 if (entry == smi_map_.end()) {
234 index = AllocateReservedEntry(value);
235 } else {
236 ConstantArraySlice* slice = OperandSizeToSlice(operand_size);
237 index = entry->second;
238 if (index > slice->max_index()) {
239 // The object is already in the constant array, but may have an
240 // index too big for the reserved operand_size. So, duplicate
241 // entry with the smaller operand size.
242 index = AllocateReservedEntry(value);
243 }
244 DCHECK_LE(index, slice->max_index());
245 }
246 return index;
247 }
248
DiscardReservedEntry(OperandSize operand_size)249 void ConstantArrayBuilder::DiscardReservedEntry(OperandSize operand_size) {
250 OperandSizeToSlice(operand_size)->Unreserve();
251 }
252
253 } // namespace interpreter
254 } // namespace internal
255 } // namespace v8
256