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 <cmath>
8 #include <functional>
9 #include <set>
10
11 #include "src/ast/ast-value-factory.h"
12 #include "src/ast/ast.h"
13 #include "src/ast/scopes.h"
14 #include "src/base/functional.h"
15 #include "src/execution/isolate.h"
16 #include "src/heap/local-factory-inl.h"
17 #include "src/objects/objects-inl.h"
18
19 namespace v8 {
20 namespace internal {
21 namespace interpreter {
22
ConstantArraySlice(Zone * zone,size_t start_index,size_t capacity,OperandSize operand_size)23 ConstantArrayBuilder::ConstantArraySlice::ConstantArraySlice(
24 Zone* zone, size_t start_index, size_t capacity, OperandSize operand_size)
25 : start_index_(start_index),
26 capacity_(capacity),
27 reserved_(0),
28 operand_size_(operand_size),
29 constants_(zone) {}
30
Reserve()31 void ConstantArrayBuilder::ConstantArraySlice::Reserve() {
32 DCHECK_GT(available(), 0u);
33 reserved_++;
34 DCHECK_LE(reserved_, capacity() - constants_.size());
35 }
36
Unreserve()37 void ConstantArrayBuilder::ConstantArraySlice::Unreserve() {
38 DCHECK_GT(reserved_, 0u);
39 reserved_--;
40 }
41
Allocate(ConstantArrayBuilder::Entry entry,size_t count)42 size_t ConstantArrayBuilder::ConstantArraySlice::Allocate(
43 ConstantArrayBuilder::Entry entry, size_t count) {
44 DCHECK_GE(available(), count);
45 size_t index = constants_.size();
46 DCHECK_LT(index, capacity());
47 for (size_t i = 0; i < count; ++i) {
48 constants_.push_back(entry);
49 }
50 return index + start_index();
51 }
52
At(size_t index)53 ConstantArrayBuilder::Entry& ConstantArrayBuilder::ConstantArraySlice::At(
54 size_t index) {
55 DCHECK_GE(index, start_index());
56 DCHECK_LT(index, start_index() + size());
57 return constants_[index - start_index()];
58 }
59
At(size_t index) const60 const ConstantArrayBuilder::Entry& ConstantArrayBuilder::ConstantArraySlice::At(
61 size_t index) const {
62 DCHECK_GE(index, start_index());
63 DCHECK_LT(index, start_index() + size());
64 return constants_[index - start_index()];
65 }
66
67 #if DEBUG
68 template <typename IsolateT>
CheckAllElementsAreUnique(IsolateT * isolate) const69 void ConstantArrayBuilder::ConstantArraySlice::CheckAllElementsAreUnique(
70 IsolateT* isolate) const {
71 std::set<Smi> smis;
72 std::set<double> heap_numbers;
73 std::set<const AstRawString*> strings;
74 std::set<const char*> bigints;
75 std::set<const Scope*> scopes;
76 std::set<Object, Object::Comparer> deferred_objects;
77 for (const Entry& entry : constants_) {
78 bool duplicate = false;
79 switch (entry.tag_) {
80 case Entry::Tag::kSmi:
81 duplicate = !smis.insert(entry.smi_).second;
82 break;
83 case Entry::Tag::kHeapNumber:
84 duplicate = !heap_numbers.insert(entry.heap_number_).second;
85 break;
86 case Entry::Tag::kRawString:
87 duplicate = !strings.insert(entry.raw_string_).second;
88 break;
89 case Entry::Tag::kBigInt:
90 duplicate = !bigints.insert(entry.bigint_.c_str()).second;
91 break;
92 case Entry::Tag::kScope:
93 duplicate = !scopes.insert(entry.scope_).second;
94 break;
95 case Entry::Tag::kHandle:
96 duplicate = !deferred_objects.insert(*entry.handle_).second;
97 break;
98 case Entry::Tag::kDeferred:
99 UNREACHABLE(); // Should be kHandle at this point.
100 case Entry::Tag::kJumpTableSmi:
101 case Entry::Tag::kUninitializedJumpTableSmi:
102 // TODO(leszeks): Ignore jump tables because they have to be contiguous,
103 // so they can contain duplicates.
104 break;
105 #define CASE_TAG(NAME, ...) case Entry::Tag::k##NAME:
106 SINGLETON_CONSTANT_ENTRY_TYPES(CASE_TAG)
107 #undef CASE_TAG
108 // Singletons are non-duplicated by definition.
109 break;
110 }
111 if (duplicate) {
112 std::ostringstream os;
113 os << "Duplicate constant found: " << Brief(*entry.ToHandle(isolate))
114 << std::endl;
115 // Print all the entries in the slice to help debug duplicates.
116 size_t i = start_index();
117 for (const Entry& prev_entry : constants_) {
118 os << i++ << ": " << Brief(*prev_entry.ToHandle(isolate)) << std::endl;
119 }
120 FATAL("%s", os.str().c_str());
121 }
122 }
123 }
124 #endif
125
126 STATIC_CONST_MEMBER_DEFINITION const size_t ConstantArrayBuilder::k8BitCapacity;
127 STATIC_CONST_MEMBER_DEFINITION const size_t
128 ConstantArrayBuilder::k16BitCapacity;
129 STATIC_CONST_MEMBER_DEFINITION const size_t
130 ConstantArrayBuilder::k32BitCapacity;
131
ConstantArrayBuilder(Zone * zone)132 ConstantArrayBuilder::ConstantArrayBuilder(Zone* zone)
133 : constants_map_(16, base::KeyEqualityMatcher<intptr_t>(),
134 ZoneAllocationPolicy(zone)),
135 smi_map_(zone),
136 smi_pairs_(zone),
137 heap_number_map_(zone) {
138 idx_slice_[0] =
139 zone->New<ConstantArraySlice>(zone, 0, k8BitCapacity, OperandSize::kByte);
140 idx_slice_[1] = zone->New<ConstantArraySlice>(
141 zone, k8BitCapacity, k16BitCapacity, OperandSize::kShort);
142 idx_slice_[2] = zone->New<ConstantArraySlice>(
143 zone, k8BitCapacity + k16BitCapacity, k32BitCapacity, OperandSize::kQuad);
144 }
145
size() const146 size_t ConstantArrayBuilder::size() const {
147 size_t i = arraysize(idx_slice_);
148 while (i > 0) {
149 ConstantArraySlice* slice = idx_slice_[--i];
150 if (slice->size() > 0) {
151 return slice->start_index() + slice->size();
152 }
153 }
154 return idx_slice_[0]->size();
155 }
156
IndexToSlice(size_t index) const157 ConstantArrayBuilder::ConstantArraySlice* ConstantArrayBuilder::IndexToSlice(
158 size_t index) const {
159 for (ConstantArraySlice* slice : idx_slice_) {
160 if (index <= slice->max_index()) {
161 return slice;
162 }
163 }
164 UNREACHABLE();
165 }
166
167 template <typename IsolateT>
At(size_t index,IsolateT * isolate) const168 MaybeHandle<Object> ConstantArrayBuilder::At(size_t index,
169 IsolateT* isolate) const {
170 const ConstantArraySlice* slice = IndexToSlice(index);
171 DCHECK_LT(index, slice->capacity());
172 if (index < slice->start_index() + slice->size()) {
173 const Entry& entry = slice->At(index);
174 if (!entry.IsDeferred()) return entry.ToHandle(isolate);
175 }
176 return MaybeHandle<Object>();
177 }
178
179 template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
180 MaybeHandle<Object> ConstantArrayBuilder::At(size_t index,
181 Isolate* isolate) const;
182 template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
183 MaybeHandle<Object> ConstantArrayBuilder::At(size_t index,
184 LocalIsolate* isolate) const;
185
186 template <typename IsolateT>
ToFixedArray(IsolateT * isolate)187 Handle<FixedArray> ConstantArrayBuilder::ToFixedArray(IsolateT* isolate) {
188 Handle<FixedArray> fixed_array = isolate->factory()->NewFixedArrayWithHoles(
189 static_cast<int>(size()), AllocationType::kOld);
190 int array_index = 0;
191 for (const ConstantArraySlice* slice : idx_slice_) {
192 DCHECK_EQ(slice->reserved(), 0);
193 DCHECK(array_index == 0 ||
194 base::bits::IsPowerOfTwo(static_cast<uint32_t>(array_index)));
195 #if DEBUG
196 // Different slices might contain the same element due to reservations, but
197 // all elements within a slice should be unique.
198 slice->CheckAllElementsAreUnique(isolate);
199 #endif
200 // Copy objects from slice into array.
201 for (size_t i = 0; i < slice->size(); ++i) {
202 Handle<Object> value =
203 slice->At(slice->start_index() + i).ToHandle(isolate);
204 fixed_array->set(array_index++, *value);
205 }
206 // Leave holes where reservations led to unused slots.
207 size_t padding = slice->capacity() - slice->size();
208 if (static_cast<size_t>(fixed_array->length() - array_index) <= padding) {
209 break;
210 }
211 array_index += padding;
212 }
213 DCHECK_GE(array_index, fixed_array->length());
214 return fixed_array;
215 }
216
217 template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
218 Handle<FixedArray> ConstantArrayBuilder::ToFixedArray(Isolate* isolate);
219 template EXPORT_TEMPLATE_DEFINE(V8_EXPORT_PRIVATE)
220 Handle<FixedArray> ConstantArrayBuilder::ToFixedArray(
221 LocalIsolate* isolate);
222
Insert(Smi smi)223 size_t ConstantArrayBuilder::Insert(Smi smi) {
224 auto entry = smi_map_.find(smi);
225 if (entry == smi_map_.end()) {
226 return AllocateReservedEntry(smi);
227 }
228 return entry->second;
229 }
230
Insert(double number)231 size_t ConstantArrayBuilder::Insert(double number) {
232 if (std::isnan(number)) return InsertNaN();
233 auto entry = heap_number_map_.find(number);
234 if (entry == heap_number_map_.end()) {
235 index_t index = static_cast<index_t>(AllocateIndex(Entry(number)));
236 heap_number_map_[number] = index;
237 return index;
238 }
239 return entry->second;
240 }
241
Insert(const AstRawString * raw_string)242 size_t ConstantArrayBuilder::Insert(const AstRawString* raw_string) {
243 return constants_map_
244 .LookupOrInsert(reinterpret_cast<intptr_t>(raw_string),
245 raw_string->Hash(),
246 [&]() { return AllocateIndex(Entry(raw_string)); })
247 ->value;
248 }
249
Insert(AstBigInt bigint)250 size_t ConstantArrayBuilder::Insert(AstBigInt bigint) {
251 return constants_map_
252 .LookupOrInsert(reinterpret_cast<intptr_t>(bigint.c_str()),
253 static_cast<uint32_t>(base::hash_value(bigint.c_str())),
254 [&]() { return AllocateIndex(Entry(bigint)); })
255 ->value;
256 }
257
Insert(const Scope * scope)258 size_t ConstantArrayBuilder::Insert(const Scope* scope) {
259 return constants_map_
260 .LookupOrInsert(reinterpret_cast<intptr_t>(scope),
261 static_cast<uint32_t>(base::hash_value(scope)),
262 [&]() { return AllocateIndex(Entry(scope)); })
263 ->value;
264 }
265
266 #define INSERT_ENTRY(NAME, LOWER_NAME) \
267 size_t ConstantArrayBuilder::Insert##NAME() { \
268 if (LOWER_NAME##_ < 0) { \
269 LOWER_NAME##_ = AllocateIndex(Entry::NAME()); \
270 } \
271 return LOWER_NAME##_; \
272 }
SINGLETON_CONSTANT_ENTRY_TYPES(INSERT_ENTRY)273 SINGLETON_CONSTANT_ENTRY_TYPES(INSERT_ENTRY)
274 #undef INSERT_ENTRY
275
276 ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateIndex(
277 ConstantArrayBuilder::Entry entry) {
278 return AllocateIndexArray(entry, 1);
279 }
280
AllocateIndexArray(ConstantArrayBuilder::Entry entry,size_t count)281 ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateIndexArray(
282 ConstantArrayBuilder::Entry entry, size_t count) {
283 for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
284 if (idx_slice_[i]->available() >= count) {
285 return static_cast<index_t>(idx_slice_[i]->Allocate(entry, count));
286 }
287 }
288 UNREACHABLE();
289 }
290
291 ConstantArrayBuilder::ConstantArraySlice*
OperandSizeToSlice(OperandSize operand_size) const292 ConstantArrayBuilder::OperandSizeToSlice(OperandSize operand_size) const {
293 ConstantArraySlice* slice = nullptr;
294 switch (operand_size) {
295 case OperandSize::kNone:
296 UNREACHABLE();
297 case OperandSize::kByte:
298 slice = idx_slice_[0];
299 break;
300 case OperandSize::kShort:
301 slice = idx_slice_[1];
302 break;
303 case OperandSize::kQuad:
304 slice = idx_slice_[2];
305 break;
306 }
307 DCHECK(slice->operand_size() == operand_size);
308 return slice;
309 }
310
InsertDeferred()311 size_t ConstantArrayBuilder::InsertDeferred() {
312 return AllocateIndex(Entry::Deferred());
313 }
314
InsertJumpTable(size_t size)315 size_t ConstantArrayBuilder::InsertJumpTable(size_t size) {
316 return AllocateIndexArray(Entry::UninitializedJumpTableSmi(), size);
317 }
318
SetDeferredAt(size_t index,Handle<Object> object)319 void ConstantArrayBuilder::SetDeferredAt(size_t index, Handle<Object> object) {
320 ConstantArraySlice* slice = IndexToSlice(index);
321 return slice->At(index).SetDeferred(object);
322 }
323
SetJumpTableSmi(size_t index,Smi smi)324 void ConstantArrayBuilder::SetJumpTableSmi(size_t index, Smi smi) {
325 ConstantArraySlice* slice = IndexToSlice(index);
326 // Allow others to reuse these Smis, but insert using emplace to avoid
327 // overwriting existing values in the Smi map (which may have a smaller
328 // operand size).
329 smi_map_.emplace(smi, static_cast<index_t>(index));
330 return slice->At(index).SetJumpTableSmi(smi);
331 }
332
CreateReservedEntry()333 OperandSize ConstantArrayBuilder::CreateReservedEntry() {
334 for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
335 if (idx_slice_[i]->available() > 0) {
336 idx_slice_[i]->Reserve();
337 return idx_slice_[i]->operand_size();
338 }
339 }
340 UNREACHABLE();
341 }
342
AllocateReservedEntry(Smi value)343 ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateReservedEntry(
344 Smi value) {
345 index_t index = static_cast<index_t>(AllocateIndex(Entry(value)));
346 smi_map_[value] = index;
347 return index;
348 }
349
CommitReservedEntry(OperandSize operand_size,Smi value)350 size_t ConstantArrayBuilder::CommitReservedEntry(OperandSize operand_size,
351 Smi value) {
352 DiscardReservedEntry(operand_size);
353 size_t index;
354 auto entry = smi_map_.find(value);
355 if (entry == smi_map_.end()) {
356 index = AllocateReservedEntry(value);
357 } else {
358 ConstantArraySlice* slice = OperandSizeToSlice(operand_size);
359 index = entry->second;
360 if (index > slice->max_index()) {
361 // The object is already in the constant array, but may have an
362 // index too big for the reserved operand_size. So, duplicate
363 // entry with the smaller operand size.
364 index = AllocateReservedEntry(value);
365 }
366 DCHECK_LE(index, slice->max_index());
367 }
368 return index;
369 }
370
DiscardReservedEntry(OperandSize operand_size)371 void ConstantArrayBuilder::DiscardReservedEntry(OperandSize operand_size) {
372 OperandSizeToSlice(operand_size)->Unreserve();
373 }
374
375 template <typename IsolateT>
ToHandle(IsolateT * isolate) const376 Handle<Object> ConstantArrayBuilder::Entry::ToHandle(IsolateT* isolate) const {
377 switch (tag_) {
378 case Tag::kDeferred:
379 // We shouldn't have any deferred entries by now.
380 UNREACHABLE();
381 case Tag::kHandle:
382 return handle_;
383 case Tag::kSmi:
384 case Tag::kJumpTableSmi:
385 return handle(smi_, isolate);
386 case Tag::kUninitializedJumpTableSmi:
387 // TODO(leszeks): There's probably a better value we could use here.
388 return isolate->factory()->the_hole_value();
389 case Tag::kRawString:
390 return raw_string_->string();
391 case Tag::kHeapNumber:
392 return isolate->factory()->template NewNumber<AllocationType::kOld>(
393 heap_number_);
394 case Tag::kBigInt:
395 // This should never fail: the parser will never create a BigInt
396 // literal that cannot be allocated.
397 return BigIntLiteral(isolate, bigint_.c_str()).ToHandleChecked();
398 case Tag::kScope:
399 return scope_->scope_info();
400 #define ENTRY_LOOKUP(Name, name) \
401 case Tag::k##Name: \
402 return isolate->factory()->name();
403 SINGLETON_CONSTANT_ENTRY_TYPES(ENTRY_LOOKUP);
404 #undef ENTRY_LOOKUP
405 }
406 UNREACHABLE();
407 }
408
409 template Handle<Object> ConstantArrayBuilder::Entry::ToHandle(
410 Isolate* isolate) const;
411 template Handle<Object> ConstantArrayBuilder::Entry::ToHandle(
412 LocalIsolate* isolate) const;
413
414 } // namespace interpreter
415 } // namespace internal
416 } // namespace v8
417