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 6314798 : constants_(zone) {}
28 :
29 0 : void ConstantArrayBuilder::ConstantArraySlice::Reserve() {
30 : DCHECK_GT(available(), 0u);
31 3053527 : reserved_++;
32 : DCHECK_LE(reserved_, capacity() - constants_.size());
33 0 : }
34 :
35 0 : void ConstantArrayBuilder::ConstantArraySlice::Unreserve() {
36 : DCHECK_GT(reserved_, 0u);
37 3053530 : reserved_--;
38 0 : }
39 :
40 0 : size_t ConstantArrayBuilder::ConstantArraySlice::Allocate(
41 12380537 : ConstantArrayBuilder::Entry entry) {
42 : DCHECK_GT(available(), 0u);
43 0 : size_t index = constants_.size();
44 : DCHECK_LT(index, capacity());
45 12380531 : constants_.push_back(entry);
46 12380537 : return index + start_index();
47 : }
48 :
49 0 : ConstantArrayBuilder::Entry& ConstantArrayBuilder::ConstantArraySlice::At(
50 3994782 : size_t index) {
51 : DCHECK_GE(index, start_index());
52 : DCHECK_LT(index, start_index() + size());
53 3994782 : return constants_[index - start_index()];
54 : }
55 :
56 0 : const ConstantArrayBuilder::Entry& ConstantArrayBuilder::ConstantArraySlice::At(
57 0 : size_t index) const {
58 : DCHECK_GE(index, start_index());
59 : DCHECK_LT(index, start_index() + size());
60 12555885 : return constants_[index - start_index()];
61 : }
62 :
63 : #if DEBUG
64 : 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 :
90 2104926 : 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 4209848 : zone_(zone) {
99 : idx_slice_[0] =
100 2104934 : new (zone) ConstantArraySlice(zone, 0, k8BitCapacity, OperandSize::kByte);
101 : idx_slice_[1] = new (zone) ConstantArraySlice(
102 2104933 : zone, k8BitCapacity, k16BitCapacity, OperandSize::kShort);
103 : idx_slice_[2] = new (zone) ConstantArraySlice(
104 2104931 : zone, k8BitCapacity + k16BitCapacity, k32BitCapacity, OperandSize::kQuad);
105 2104931 : }
106 :
107 2114511 : size_t ConstantArrayBuilder::size() const {
108 : size_t i = arraysize(idx_slice_);
109 8791140 : while (i > 0) {
110 8106960 : ConstantArraySlice* slice = idx_slice_[--i];
111 6334539 : if (slice->size() > 0) {
112 1772421 : return slice->start_index() + slice->size();
113 : }
114 : }
115 684180 : return idx_slice_[0]->size();
116 : }
117 :
118 4303327 : ConstantArrayBuilder::ConstantArraySlice* ConstantArrayBuilder::IndexToSlice(
119 : size_t index) const {
120 5006891 : for (ConstantArraySlice* slice : idx_slice_) {
121 5006891 : if (index <= slice->max_index()) {
122 : return slice;
123 : }
124 : }
125 0 : UNREACHABLE();
126 : return nullptr;
127 : }
128 :
129 308545 : MaybeHandle<Object> ConstantArrayBuilder::At(size_t index,
130 : Isolate* isolate) const {
131 308545 : const ConstantArraySlice* slice = IndexToSlice(index);
132 : DCHECK_LT(index, slice->capacity());
133 308545 : if (index < slice->start_index() + slice->size()) {
134 308289 : const Entry& entry = slice->At(index);
135 308289 : if (!entry.IsDeferred()) return entry.ToHandle(isolate);
136 : }
137 : return MaybeHandle<Object>();
138 : }
139 :
140 2103833 : Handle<FixedArray> ConstantArrayBuilder::ToFixedArray(Isolate* isolate) {
141 : Handle<FixedArray> fixed_array = isolate->factory()->NewFixedArrayWithHoles(
142 2103833 : static_cast<int>(size()), PretenureFlag::TENURED);
143 : int array_index = 0;
144 16462875 : 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 28710470 : for (size_t i = 0; i < slice->size(); ++i) {
156 : fixed_array->set(array_index++,
157 48990378 : *slice->At(slice->start_index() + i).ToHandle(isolate));
158 : }
159 : // Leave holes where reservations led to unused slots.
160 2107639 : size_t padding = slice->capacity() - slice->size();
161 2107639 : if (static_cast<size_t>(fixed_array->length() - array_index) <= padding) {
162 : break;
163 : }
164 3798 : array_index += padding;
165 : }
166 : DCHECK_GE(array_index, fixed_array->length());
167 2103841 : return fixed_array;
168 : }
169 :
170 32640 : size_t ConstantArrayBuilder::Insert(Smi* smi) {
171 : auto entry = smi_map_.find(smi);
172 32640 : if (entry == smi_map_.end()) {
173 32640 : return AllocateReservedEntry(smi);
174 : }
175 0 : return entry->second;
176 : }
177 :
178 11202964 : 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 14226122 : [&]() { return AllocateIndex(Entry(raw_string)); },
183 33608891 : ZoneAllocationPolicy(zone_))
184 22405926 : ->value;
185 : }
186 :
187 861815 : 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 1723114 : [&]() { return AllocateIndex(Entry(heap_number)); },
198 3447260 : ZoneAllocationPolicy(zone_))
199 1723630 : ->value;
200 : }
201 :
202 184273 : 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 368542 : [&]() { return AllocateIndex(Entry(scope)); },
207 737092 : ZoneAllocationPolicy(zone_))
208 368546 : ->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 : }
218 94262 : SINGLETON_CONSTANT_ENTRY_TYPES(INSERT_ENTRY)
219 : #undef INSERT_ENTRY
220 :
221 12380531 : ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateIndex(
222 : ConstantArrayBuilder::Entry entry) {
223 13948014 : for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
224 27896028 : if (idx_slice_[i]->available() > 0) {
225 12380537 : return static_cast<index_t>(idx_slice_[i]->Allocate(entry));
226 : }
227 : }
228 0 : UNREACHABLE();
229 : return kMaxUInt32;
230 : }
231 :
232 : ConstantArrayBuilder::ConstantArraySlice*
233 3055237 : ConstantArrayBuilder::OperandSizeToSlice(OperandSize operand_size) const {
234 : ConstantArraySlice* slice = nullptr;
235 3055237 : switch (operand_size) {
236 : case OperandSize::kNone:
237 0 : UNREACHABLE();
238 : break;
239 : case OperandSize::kByte:
240 2800552 : slice = idx_slice_[0];
241 2800552 : break;
242 : case OperandSize::kShort:
243 189142 : slice = idx_slice_[1];
244 189142 : break;
245 : case OperandSize::kQuad:
246 65543 : slice = idx_slice_[2];
247 65543 : break;
248 : }
249 : DCHECK(slice->operand_size() == operand_size);
250 3055237 : return slice;
251 : }
252 :
253 3994775 : size_t ConstantArrayBuilder::InsertDeferred() {
254 3994775 : return AllocateIndex(Entry::Deferred());
255 : }
256 :
257 3994782 : void ConstantArrayBuilder::SetDeferredAt(size_t index, Handle<Object> object) {
258 3994782 : ConstantArraySlice* slice = IndexToSlice(index);
259 3994782 : return slice->At(index).SetDeferred(object);
260 : }
261 :
262 3053527 : OperandSize ConstantArrayBuilder::CreateReservedEntry() {
263 3373391 : for (size_t i = 0; i < arraysize(idx_slice_); ++i) {
264 9800309 : if (idx_slice_[i]->available() > 0) {
265 : idx_slice_[i]->Reserve();
266 : return idx_slice_[i]->operand_size();
267 : }
268 : }
269 0 : UNREACHABLE();
270 : return OperandSize::kNone;
271 : }
272 :
273 157444 : ConstantArrayBuilder::index_t ConstantArrayBuilder::AllocateReservedEntry(
274 : Smi* value) {
275 314888 : index_t index = static_cast<index_t>(AllocateIndex(Entry(value)));
276 157444 : smi_map_[value] = index;
277 157444 : return index;
278 : }
279 :
280 126255 : 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 126255 : if (entry == smi_map_.end()) {
286 124548 : index = AllocateReservedEntry(value);
287 : } else {
288 1707 : ConstantArraySlice* slice = OperandSizeToSlice(operand_size);
289 1707 : index = entry->second;
290 1707 : 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 256 : index = AllocateReservedEntry(value);
295 : }
296 : DCHECK_LE(index, slice->max_index());
297 : }
298 126255 : return index;
299 : }
300 :
301 2927275 : void ConstantArrayBuilder::DiscardReservedEntry(OperandSize operand_size) {
302 3053530 : OperandSizeToSlice(operand_size)->Unreserve();
303 2927275 : }
304 :
305 12523244 : Handle<Object> ConstantArrayBuilder::Entry::ToHandle(Isolate* isolate) const {
306 12523244 : switch (tag_) {
307 : case Tag::kDeferred:
308 : // We shouldn't have any deferred entries by now.
309 0 : UNREACHABLE();
310 : return Handle<Object>::null();
311 : case Tag::kHandle:
312 3994781 : return handle_;
313 : case Tag::kSmi:
314 454914 : return handle(smi_, isolate);
315 : case Tag::kRawString:
316 7111983 : return raw_string_->string();
317 : case Tag::kHeapNumber:
318 : DCHECK(heap_number_->IsHeapNumber());
319 935327 : return heap_number_->value();
320 : case Tag::kScope:
321 184259 : return scope_->scope_info();
322 : #define ENTRY_LOOKUP(Name, name) \
323 : case Tag::k##Name: \
324 : return isolate->factory()->name();
325 69437 : SINGLETON_CONSTANT_ENTRY_TYPES(ENTRY_LOOKUP);
326 : #undef ENTRY_LOOKUP
327 : }
328 0 : UNREACHABLE();
329 : return Handle<Object>::null();
330 : }
331 :
332 : } // namespace interpreter
333 : } // namespace internal
334 : } // namespace v8
|
