Line data Source code
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 :
21 0 : 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 6464448 : constants_(zone) {}
28 :
29 0 : void ConstantArrayBuilder::ConstantArraySlice::Reserve() {
30 : DCHECK_GT(available(), 0u);
31 2390744 : reserved_++;
32 : DCHECK_LE(reserved_, capacity() - constants_.size());
33 0 : }
34 :
35 0 : void ConstantArrayBuilder::ConstantArraySlice::Unreserve() {
36 : DCHECK_GT(reserved_, 0u);
37 2390745 : reserved_--;
38 0 : }
39 :
40 0 : size_t ConstantArrayBuilder::ConstantArraySlice::Allocate(
41 12988221 : ConstantArrayBuilder::Entry entry, size_t count) {
42 : DCHECK_GE(available(), count);
43 0 : size_t index = constants_.size();
44 : DCHECK_LT(index, capacity());
45 13022448 : for (size_t i = 0; i < count; ++i) {
46 13022447 : constants_.push_back(entry);
47 : }
48 12988221 : return index + start_index();
49 : }
50 :
51 0 : ConstantArrayBuilder::Entry& ConstantArrayBuilder::ConstantArraySlice::At(
52 4523979 : size_t index) {
53 : DCHECK_GE(index, start_index());
54 : DCHECK_LT(index, start_index() + size());
55 4523979 : return constants_[index - start_index()];
56 : }
57 :
58 0 : const ConstantArrayBuilder::Entry& ConstantArrayBuilder::ConstantArraySlice::At(
59 0 : size_t index) const {
60 : DCHECK_GE(index, start_index());
61 : DCHECK_LT(index, start_index() + size());
62 13198126 : return constants_[index - start_index()];
63 : }
64 :
65 : #if DEBUG
66 : void ConstantArrayBuilder::ConstantArraySlice::CheckAllElementsAreUnique(
67 : Isolate* isolate) const {
68 : std::set<Object*> elements;
69 : for (const Entry& entry : constants_) {
70 : // TODO(leszeks): Ignore jump tables because they have to be contiguous,
71 : // so they can contain duplicates.
72 : if (entry.IsJumpTableEntry()) continue;
73 :
74 : Handle<Object> handle = entry.ToHandle(isolate);
75 :
76 : if (elements.find(*handle) != elements.end()) {
77 : std::ostringstream os;
78 : os << "Duplicate constant found: " << Brief(*handle) << std::endl;
79 : // Print all the entries in the slice to help debug duplicates.
80 : size_t i = start_index();
81 : for (const Entry& prev_entry : constants_) {
82 : os << i++ << ": " << Brief(*prev_entry.ToHandle(isolate)) << std::endl;
83 : }
84 : FATAL(os.str().c_str());
85 : }
86 : elements.insert(*handle);
87 : }
88 : }
89 : #endif
90 :
91 : STATIC_CONST_MEMBER_DEFINITION const size_t ConstantArrayBuilder::k8BitCapacity;
92 : STATIC_CONST_MEMBER_DEFINITION const size_t
93 : ConstantArrayBuilder::k16BitCapacity;
94 : STATIC_CONST_MEMBER_DEFINITION const size_t
95 : ConstantArrayBuilder::k32BitCapacity;
96 :
97 2154813 : ConstantArrayBuilder::ConstantArrayBuilder(Zone* zone)
98 : : constants_map_(16, base::KeyEqualityMatcher<intptr_t>(),
99 : ZoneAllocationPolicy(zone)),
100 : smi_map_(zone),
101 : smi_pairs_(zone),
102 : #define INIT_SINGLETON_ENTRY_FIELD(NAME, LOWER_NAME) LOWER_NAME##_(-1),
103 : SINGLETON_CONSTANT_ENTRY_TYPES(INIT_SINGLETON_ENTRY_FIELD)
104 : #undef INIT_SINGLETON_ENTRY_FIELD
105 4309626 : zone_(zone) {
106 : idx_slice_[0] =
107 2154816 : new (zone) ConstantArraySlice(zone, 0, k8BitCapacity, OperandSize::kByte);
108 : idx_slice_[1] = new (zone) ConstantArraySlice(
109 2154817 : zone, k8BitCapacity, k16BitCapacity, OperandSize::kShort);
110 : idx_slice_[2] = new (zone) ConstantArraySlice(
111 2154815 : zone, k8BitCapacity + k16BitCapacity, k32BitCapacity, OperandSize::kQuad);
112 2154815 : }
113 :
114 2164574 : size_t ConstantArrayBuilder::size() const {
115 : size_t i = arraysize(idx_slice_);
116 9025485 : while (i > 0) {
117 8271697 : ConstantArraySlice* slice = idx_slice_[--i];
118 6484017 : if (slice->size() > 0) {
119 1787680 : return slice->start_index() + slice->size();
120 : }
121 : }
122 753788 : return idx_slice_[0]->size();
123 : }
124 :
125 4832524 : ConstantArrayBuilder::ConstantArraySlice* ConstantArrayBuilder::IndexToSlice(
126 : size_t index) const {
127 5652379 : for (ConstantArraySlice* slice : idx_slice_) {
128 5652379 : if (index <= slice->max_index()) {
129 4832524 : return slice;
130 : }
131 : }
132 0 : UNREACHABLE();
133 : }
134 :
135 308545 : MaybeHandle<Object> ConstantArrayBuilder::At(size_t index,
136 : Isolate* isolate) const {
137 308545 : const ConstantArraySlice* slice = IndexToSlice(index);
138 : DCHECK_LT(index, slice->capacity());
139 308545 : if (index < slice->start_index() + slice->size()) {
140 308289 : const Entry& entry = slice->At(index);
141 308289 : if (!entry.IsDeferred()) return entry.ToHandle(isolate);
142 : }
143 32896 : return MaybeHandle<Object>();
144 : }
145 :
146 2153894 : Handle<FixedArray> ConstantArrayBuilder::ToFixedArray(Isolate* isolate) {
147 : Handle<FixedArray> fixed_array = isolate->factory()->NewFixedArrayWithHoles(
148 2153894 : static_cast<int>(size()), PretenureFlag::TENURED);
149 : int array_index = 0;
150 17206643 : for (const ConstantArraySlice* slice : idx_slice_) {
151 : DCHECK_EQ(slice->reserved(), 0);
152 : DCHECK(array_index == 0 ||
153 : base::bits::IsPowerOfTwo(static_cast<uint32_t>(array_index)));
154 : #if DEBUG
155 : // Different slices might contain the same element due to reservations, but
156 : // all elements within a slice should be unique. If this DCHECK fails, then
157 : // the AST nodes are not being internalized within a CanonicalHandleScope.
158 : slice->CheckAllElementsAreUnique(isolate);
159 : #endif
160 : // Copy objects from slice into array.
161 30096480 : for (size_t i = 0; i < slice->size(); ++i) {
162 : fixed_array->set(array_index++,
163 51559348 : *slice->At(slice->start_index() + i).ToHandle(isolate));
164 : }
165 : // Leave holes where reservations led to unused slots.
166 2158403 : size_t padding = slice->capacity() - slice->size();
167 2158403 : if (static_cast<size_t>(fixed_array->length() - array_index) <= padding) {
168 : break;
169 : }
170 4509 : array_index += padding;
171 : }
172 : DCHECK_GE(array_index, fixed_array->length());
173 2153894 : return fixed_array;
174 : }
175 :
176 32640 : size_t ConstantArrayBuilder::Insert(Smi* smi) {
177 : auto entry = smi_map_.find(smi);
178 32640 : if (entry == smi_map_.end()) {
179 32640 : return AllocateReservedEntry(smi);
180 : }
181 0 : return entry->second;
182 : }
183 :
184 12120278 : size_t ConstantArrayBuilder::Insert(const AstRawString* raw_string) {
185 : return constants_map_
186 : .LookupOrInsert(reinterpret_cast<intptr_t>(raw_string),
187 : raw_string->Hash(),
188 14685361 : [&]() { return AllocateIndex(Entry(raw_string)); },
189 48481109 : ZoneAllocationPolicy(zone_))
190 24240550 : ->value;
191 : }
192 :
193 829769 : size_t ConstantArrayBuilder::Insert(const AstValue* heap_number) {
194 : // This method only accepts heap numbers and BigInts. Other types of
195 : // AstValue should either be passed through as raw values (in the
196 : // case of strings), use the singleton Insert methods (in the case
197 : // of symbols), or skip the constant pool entirely and use bytecodes
198 : // with immediate values (Smis, booleans, undefined, etc.).
199 : DCHECK(heap_number->IsHeapNumber() || heap_number->IsBigInt());
200 : return constants_map_
201 : .LookupOrInsert(reinterpret_cast<intptr_t>(heap_number),
202 : static_cast<uint32_t>(base::hash_value(heap_number)),
203 1659022 : [&]() { return AllocateIndex(Entry(heap_number)); },
204 3319076 : ZoneAllocationPolicy(zone_))
205 1659538 : ->value;
206 : }
207 :
208 170339 : size_t ConstantArrayBuilder::Insert(const Scope* scope) {
209 : return constants_map_
210 : .LookupOrInsert(reinterpret_cast<intptr_t>(scope),
211 : static_cast<uint32_t>(base::hash_value(scope)),
212 340674 : [&]() { return AllocateIndex(Entry(scope)); },
213 681356 : ZoneAllocationPolicy(zone_))
214 340678 : ->value;
215 : }
216 :
217 : #define INSERT_ENTRY(NAME, LOWER_NAME) \
218 : size_t ConstantArrayBuilder::Insert##NAME() { \
219 : if (LOWER_NAME##_ < 0) { \
220 : LOWER_NAME##_ = AllocateIndex(Entry::NAME()); \
221 : } \
222 : return LOWER_NAME##_; \
223 : }
224 204339 : SINGLETON_CONSTANT_ENTRY_TYPES(INSERT_ENTRY)
225 : #undef INSERT_ENTRY
226 :
227 0 : ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateIndex(
228 : ConstantArrayBuilder::Entry entry) {
229 12959532 : return AllocateIndexArray(entry, 1);
230 : }
231 :
232 12988220 : ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateIndexArray(
233 : ConstantArrayBuilder::Entry entry, size_t count) {
234 14645920 : for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
235 29291840 : if (idx_slice_[i]->available() >= count) {
236 12988221 : return static_cast<index_t>(idx_slice_[i]->Allocate(entry, count));
237 : }
238 : }
239 0 : UNREACHABLE();
240 : }
241 :
242 : ConstantArrayBuilder::ConstantArraySlice*
243 2392311 : ConstantArrayBuilder::OperandSizeToSlice(OperandSize operand_size) const {
244 : ConstantArraySlice* slice = nullptr;
245 2392311 : switch (operand_size) {
246 : case OperandSize::kNone:
247 0 : UNREACHABLE();
248 : break;
249 : case OperandSize::kByte:
250 2153971 : slice = idx_slice_[0];
251 2153971 : break;
252 : case OperandSize::kShort:
253 172798 : slice = idx_slice_[1];
254 172798 : break;
255 : case OperandSize::kQuad:
256 65542 : slice = idx_slice_[2];
257 65542 : break;
258 : }
259 : DCHECK(slice->operand_size() == operand_size);
260 2392311 : return slice;
261 : }
262 :
263 4461148 : size_t ConstantArrayBuilder::InsertDeferred() {
264 4461151 : return AllocateIndex(Entry::Deferred());
265 : }
266 :
267 28694 : size_t ConstantArrayBuilder::InsertJumpTable(size_t size) {
268 28694 : return AllocateIndexArray(Entry::UninitializedJumpTableSmi(), size);
269 : }
270 :
271 4461146 : void ConstantArrayBuilder::SetDeferredAt(size_t index, Handle<Object> object) {
272 4461146 : ConstantArraySlice* slice = IndexToSlice(index);
273 4461146 : return slice->At(index).SetDeferred(object);
274 : }
275 :
276 62833 : void ConstantArrayBuilder::SetJumpTableSmi(size_t index, Smi* smi) {
277 62833 : ConstantArraySlice* slice = IndexToSlice(index);
278 : // Allow others to reuse these Smis, but insert using emplace to avoid
279 : // overwriting existing values in the Smi map (which may have a smaller
280 : // operand size).
281 125666 : smi_map_.emplace(smi, static_cast<index_t>(index));
282 125666 : return slice->At(index).SetJumpTableSmi(smi);
283 : }
284 :
285 2390744 : OperandSize ConstantArrayBuilder::CreateReservedEntry() {
286 2694262 : for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
287 7779268 : if (idx_slice_[i]->available() > 0) {
288 : idx_slice_[i]->Reserve();
289 4781488 : return idx_slice_[i]->operand_size();
290 : }
291 : }
292 0 : UNREACHABLE();
293 : }
294 :
295 107237 : ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateReservedEntry(
296 : Smi* value) {
297 107237 : index_t index = static_cast<index_t>(AllocateIndex(Entry(value)));
298 107237 : smi_map_[value] = index;
299 107237 : return index;
300 : }
301 :
302 75907 : size_t ConstantArrayBuilder::CommitReservedEntry(OperandSize operand_size,
303 : Smi* value) {
304 : DiscardReservedEntry(operand_size);
305 : size_t index;
306 : auto entry = smi_map_.find(value);
307 75907 : if (entry == smi_map_.end()) {
308 74341 : index = AllocateReservedEntry(value);
309 : } else {
310 1566 : ConstantArraySlice* slice = OperandSizeToSlice(operand_size);
311 1566 : index = entry->second;
312 1566 : if (index > slice->max_index()) {
313 : // The object is already in the constant array, but may have an
314 : // index too big for the reserved operand_size. So, duplicate
315 : // entry with the smaller operand size.
316 256 : index = AllocateReservedEntry(value);
317 : }
318 : DCHECK_LE(index, slice->max_index());
319 : }
320 75907 : return index;
321 : }
322 :
323 2314838 : void ConstantArrayBuilder::DiscardReservedEntry(OperandSize operand_size) {
324 2390745 : OperandSizeToSlice(operand_size)->Unreserve();
325 2314838 : }
326 :
327 13165486 : Handle<Object> ConstantArrayBuilder::Entry::ToHandle(Isolate* isolate) const {
328 13165486 : switch (tag_) {
329 : case Tag::kDeferred:
330 : // We shouldn't have any deferred entries by now.
331 0 : UNREACHABLE();
332 : case Tag::kHandle:
333 4461146 : return handle_;
334 : case Tag::kSmi:
335 : case Tag::kJumpTableSmi:
336 480166 : return handle(smi_, isolate);
337 : case Tag::kUninitializedJumpTableSmi:
338 : // TODO(leszeks): There's probably a better value we could use here.
339 86 : return isolate->factory()->the_hole_value();
340 : case Tag::kRawString:
341 7341785 : return raw_string_->string();
342 : case Tag::kHeapNumber:
343 : DCHECK(heap_number_->IsHeapNumber() || heap_number_->IsBigInt());
344 903431 : return heap_number_->value();
345 : case Tag::kScope:
346 170337 : return scope_->scope_info();
347 : #define ENTRY_LOOKUP(Name, name) \
348 : case Tag::k##Name: \
349 : return isolate->factory()->name();
350 48618 : SINGLETON_CONSTANT_ENTRY_TYPES(ENTRY_LOOKUP);
351 : #undef ENTRY_LOOKUP
352 : }
353 0 : UNREACHABLE();
354 : }
355 :
356 : } // namespace interpreter
357 : } // namespace internal
358 : } // namespace v8
|
