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/ast/ast-value-factory.h"
11 #include "src/ast/ast.h"
12 #include "src/ast/scopes.h"
13 #include "src/base/functional.h"
14 #include "src/isolate.h"
15 #include "src/objects-inl.h"
16
17 namespace v8 {
18 namespace internal {
19 namespace interpreter {
20
ConstantArraySlice(Zone * zone,size_t start_index,size_t capacity,OperandSize operand_size)21 ConstantArrayBuilder::ConstantArraySlice::ConstantArraySlice(
22 Zone* zone, size_t start_index, size_t capacity, OperandSize operand_size)
23 : start_index_(start_index),
24 capacity_(capacity),
25 reserved_(0),
26 operand_size_(operand_size),
27 constants_(zone) {}
28
Reserve()29 void ConstantArrayBuilder::ConstantArraySlice::Reserve() {
30 DCHECK_GT(available(), 0u);
31 reserved_++;
32 DCHECK_LE(reserved_, capacity() - constants_.size());
33 }
34
Unreserve()35 void ConstantArrayBuilder::ConstantArraySlice::Unreserve() {
36 DCHECK_GT(reserved_, 0u);
37 reserved_--;
38 }
39
Allocate(ConstantArrayBuilder::Entry entry)40 size_t ConstantArrayBuilder::ConstantArraySlice::Allocate(
41 ConstantArrayBuilder::Entry entry) {
42 DCHECK_GT(available(), 0u);
43 size_t index = constants_.size();
44 DCHECK_LT(index, capacity());
45 constants_.push_back(entry);
46 return index + start_index();
47 }
48
At(size_t index)49 ConstantArrayBuilder::Entry& ConstantArrayBuilder::ConstantArraySlice::At(
50 size_t index) {
51 DCHECK_GE(index, start_index());
52 DCHECK_LT(index, start_index() + size());
53 return constants_[index - start_index()];
54 }
55
At(size_t index) const56 const ConstantArrayBuilder::Entry& ConstantArrayBuilder::ConstantArraySlice::At(
57 size_t index) const {
58 DCHECK_GE(index, start_index());
59 DCHECK_LT(index, start_index() + size());
60 return constants_[index - start_index()];
61 }
62
63 #if DEBUG
CheckAllElementsAreUnique(Isolate * isolate) const64 void ConstantArrayBuilder::ConstantArraySlice::CheckAllElementsAreUnique(
65 Isolate* isolate) const {
66 std::set<Object*> elements;
67 for (const Entry& entry : constants_) {
68 Handle<Object> handle = entry.ToHandle(isolate);
69 if (elements.find(*handle) != elements.end()) {
70 std::ostringstream os;
71 os << "Duplicate constant found: " << Brief(*handle) << std::endl;
72 // Print all the entries in the slice to help debug duplicates.
73 size_t i = start_index();
74 for (const Entry& prev_entry : constants_) {
75 os << i++ << ": " << Brief(*prev_entry.ToHandle(isolate)) << std::endl;
76 }
77 FATAL(os.str().c_str());
78 }
79 elements.insert(*handle);
80 }
81 }
82 #endif
83
84 STATIC_CONST_MEMBER_DEFINITION const size_t ConstantArrayBuilder::k8BitCapacity;
85 STATIC_CONST_MEMBER_DEFINITION const size_t
86 ConstantArrayBuilder::k16BitCapacity;
87 STATIC_CONST_MEMBER_DEFINITION const size_t
88 ConstantArrayBuilder::k32BitCapacity;
89
ConstantArrayBuilder(Zone * zone)90 ConstantArrayBuilder::ConstantArrayBuilder(Zone* zone)
91 : constants_map_(16, base::KeyEqualityMatcher<intptr_t>(),
92 ZoneAllocationPolicy(zone)),
93 smi_map_(zone),
94 smi_pairs_(zone),
95 #define INIT_SINGLETON_ENTRY_FIELD(NAME, LOWER_NAME) LOWER_NAME##_(-1),
96 SINGLETON_CONSTANT_ENTRY_TYPES(INIT_SINGLETON_ENTRY_FIELD)
97 #undef INIT_SINGLETON_ENTRY_FIELD
98 zone_(zone) {
99 idx_slice_[0] =
100 new (zone) ConstantArraySlice(zone, 0, k8BitCapacity, OperandSize::kByte);
101 idx_slice_[1] = new (zone) ConstantArraySlice(
102 zone, k8BitCapacity, k16BitCapacity, OperandSize::kShort);
103 idx_slice_[2] = new (zone) ConstantArraySlice(
104 zone, k8BitCapacity + k16BitCapacity, k32BitCapacity, OperandSize::kQuad);
105 }
106
size() const107 size_t ConstantArrayBuilder::size() const {
108 size_t i = arraysize(idx_slice_);
109 while (i > 0) {
110 ConstantArraySlice* slice = idx_slice_[--i];
111 if (slice->size() > 0) {
112 return slice->start_index() + slice->size();
113 }
114 }
115 return idx_slice_[0]->size();
116 }
117
IndexToSlice(size_t index) const118 ConstantArrayBuilder::ConstantArraySlice* ConstantArrayBuilder::IndexToSlice(
119 size_t index) const {
120 for (ConstantArraySlice* slice : idx_slice_) {
121 if (index <= slice->max_index()) {
122 return slice;
123 }
124 }
125 UNREACHABLE();
126 return nullptr;
127 }
128
At(size_t index,Isolate * isolate) const129 MaybeHandle<Object> ConstantArrayBuilder::At(size_t index,
130 Isolate* isolate) const {
131 const ConstantArraySlice* slice = IndexToSlice(index);
132 DCHECK_LT(index, slice->capacity());
133 if (index < slice->start_index() + slice->size()) {
134 const Entry& entry = slice->At(index);
135 if (!entry.IsDeferred()) return entry.ToHandle(isolate);
136 }
137 return MaybeHandle<Object>();
138 }
139
ToFixedArray(Isolate * isolate)140 Handle<FixedArray> ConstantArrayBuilder::ToFixedArray(Isolate* isolate) {
141 Handle<FixedArray> fixed_array = isolate->factory()->NewFixedArrayWithHoles(
142 static_cast<int>(size()), PretenureFlag::TENURED);
143 int array_index = 0;
144 for (const ConstantArraySlice* slice : idx_slice_) {
145 DCHECK_EQ(slice->reserved(), 0);
146 DCHECK(array_index == 0 ||
147 base::bits::IsPowerOfTwo32(static_cast<uint32_t>(array_index)));
148 #if DEBUG
149 // Different slices might contain the same element due to reservations, but
150 // all elements within a slice should be unique. If this DCHECK fails, then
151 // the AST nodes are not being internalized within a CanonicalHandleScope.
152 slice->CheckAllElementsAreUnique(isolate);
153 #endif
154 // Copy objects from slice into array.
155 for (size_t i = 0; i < slice->size(); ++i) {
156 fixed_array->set(array_index++,
157 *slice->At(slice->start_index() + i).ToHandle(isolate));
158 }
159 // Leave holes where reservations led to unused slots.
160 size_t padding = slice->capacity() - slice->size();
161 if (static_cast<size_t>(fixed_array->length() - array_index) <= padding) {
162 break;
163 }
164 array_index += padding;
165 }
166 DCHECK_GE(array_index, fixed_array->length());
167 return fixed_array;
168 }
169
Insert(Smi * smi)170 size_t ConstantArrayBuilder::Insert(Smi* smi) {
171 auto entry = smi_map_.find(smi);
172 if (entry == smi_map_.end()) {
173 return AllocateReservedEntry(smi);
174 }
175 return entry->second;
176 }
177
Insert(const AstRawString * raw_string)178 size_t ConstantArrayBuilder::Insert(const AstRawString* raw_string) {
179 return constants_map_
180 .LookupOrInsert(reinterpret_cast<intptr_t>(raw_string),
181 raw_string->hash(),
182 [&]() { return AllocateIndex(Entry(raw_string)); },
183 ZoneAllocationPolicy(zone_))
184 ->value;
185 }
186
Insert(const AstValue * heap_number)187 size_t ConstantArrayBuilder::Insert(const AstValue* heap_number) {
188 // This method only accepts heap numbers. Other types of ast value should
189 // either be passed through as raw values (in the case of strings), use the
190 // singleton Insert methods (in the case of symbols), or skip the constant
191 // pool entirely and use bytecodes with immediate values (Smis, booleans,
192 // undefined, etc.).
193 DCHECK(heap_number->IsHeapNumber());
194 return constants_map_
195 .LookupOrInsert(reinterpret_cast<intptr_t>(heap_number),
196 static_cast<uint32_t>(base::hash_value(heap_number)),
197 [&]() { return AllocateIndex(Entry(heap_number)); },
198 ZoneAllocationPolicy(zone_))
199 ->value;
200 }
201
Insert(const Scope * scope)202 size_t ConstantArrayBuilder::Insert(const Scope* scope) {
203 return constants_map_
204 .LookupOrInsert(reinterpret_cast<intptr_t>(scope),
205 static_cast<uint32_t>(base::hash_value(scope)),
206 [&]() { return AllocateIndex(Entry(scope)); },
207 ZoneAllocationPolicy(zone_))
208 ->value;
209 }
210
211 #define INSERT_ENTRY(NAME, LOWER_NAME) \
212 size_t ConstantArrayBuilder::Insert##NAME() { \
213 if (LOWER_NAME##_ < 0) { \
214 LOWER_NAME##_ = AllocateIndex(Entry::NAME()); \
215 } \
216 return LOWER_NAME##_; \
217 }
SINGLETON_CONSTANT_ENTRY_TYPES(INSERT_ENTRY)218 SINGLETON_CONSTANT_ENTRY_TYPES(INSERT_ENTRY)
219 #undef INSERT_ENTRY
220
221 ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateIndex(
222 ConstantArrayBuilder::Entry entry) {
223 for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
224 if (idx_slice_[i]->available() > 0) {
225 return static_cast<index_t>(idx_slice_[i]->Allocate(entry));
226 }
227 }
228 UNREACHABLE();
229 return kMaxUInt32;
230 }
231
232 ConstantArrayBuilder::ConstantArraySlice*
OperandSizeToSlice(OperandSize operand_size) const233 ConstantArrayBuilder::OperandSizeToSlice(OperandSize operand_size) const {
234 ConstantArraySlice* slice = nullptr;
235 switch (operand_size) {
236 case OperandSize::kNone:
237 UNREACHABLE();
238 break;
239 case OperandSize::kByte:
240 slice = idx_slice_[0];
241 break;
242 case OperandSize::kShort:
243 slice = idx_slice_[1];
244 break;
245 case OperandSize::kQuad:
246 slice = idx_slice_[2];
247 break;
248 }
249 DCHECK(slice->operand_size() == operand_size);
250 return slice;
251 }
252
InsertDeferred()253 size_t ConstantArrayBuilder::InsertDeferred() {
254 return AllocateIndex(Entry::Deferred());
255 }
256
SetDeferredAt(size_t index,Handle<Object> object)257 void ConstantArrayBuilder::SetDeferredAt(size_t index, Handle<Object> object) {
258 ConstantArraySlice* slice = IndexToSlice(index);
259 return slice->At(index).SetDeferred(object);
260 }
261
CreateReservedEntry()262 OperandSize ConstantArrayBuilder::CreateReservedEntry() {
263 for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
264 if (idx_slice_[i]->available() > 0) {
265 idx_slice_[i]->Reserve();
266 return idx_slice_[i]->operand_size();
267 }
268 }
269 UNREACHABLE();
270 return OperandSize::kNone;
271 }
272
AllocateReservedEntry(Smi * value)273 ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateReservedEntry(
274 Smi* value) {
275 index_t index = static_cast<index_t>(AllocateIndex(Entry(value)));
276 smi_map_[value] = index;
277 return index;
278 }
279
CommitReservedEntry(OperandSize operand_size,Smi * value)280 size_t ConstantArrayBuilder::CommitReservedEntry(OperandSize operand_size,
281 Smi* value) {
282 DiscardReservedEntry(operand_size);
283 size_t index;
284 auto entry = smi_map_.find(value);
285 if (entry == smi_map_.end()) {
286 index = AllocateReservedEntry(value);
287 } else {
288 ConstantArraySlice* slice = OperandSizeToSlice(operand_size);
289 index = entry->second;
290 if (index > slice->max_index()) {
291 // The object is already in the constant array, but may have an
292 // index too big for the reserved operand_size. So, duplicate
293 // entry with the smaller operand size.
294 index = AllocateReservedEntry(value);
295 }
296 DCHECK_LE(index, slice->max_index());
297 }
298 return index;
299 }
300
DiscardReservedEntry(OperandSize operand_size)301 void ConstantArrayBuilder::DiscardReservedEntry(OperandSize operand_size) {
302 OperandSizeToSlice(operand_size)->Unreserve();
303 }
304
ToHandle(Isolate * isolate) const305 Handle<Object> ConstantArrayBuilder::Entry::ToHandle(Isolate* isolate) const {
306 switch (tag_) {
307 case Tag::kDeferred:
308 // We shouldn't have any deferred entries by now.
309 UNREACHABLE();
310 return Handle<Object>::null();
311 case Tag::kHandle:
312 return handle_;
313 case Tag::kSmi:
314 return handle(smi_, isolate);
315 case Tag::kRawString:
316 return raw_string_->string();
317 case Tag::kHeapNumber:
318 DCHECK(heap_number_->IsHeapNumber());
319 return heap_number_->value();
320 case Tag::kScope:
321 return scope_->scope_info();
322 #define ENTRY_LOOKUP(Name, name) \
323 case Tag::k##Name: \
324 return isolate->factory()->name();
325 SINGLETON_CONSTANT_ENTRY_TYPES(ENTRY_LOOKUP);
326 #undef ENTRY_LOOKUP
327 }
328 UNREACHABLE();
329 return Handle<Object>::null();
330 }
331
332 } // namespace interpreter
333 } // namespace internal
334 } // namespace v8
335