Line data Source code
1 : // Copyright 2014 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/v8.h"
6 :
7 : #include "src/ast/ast-value-factory.h"
8 : #include "src/handles-inl.h"
9 : #include "src/heap/factory.h"
10 : #include "src/interpreter/constant-array-builder.h"
11 : #include "src/isolate.h"
12 : #include "src/objects-inl.h"
13 : #include "test/unittests/test-utils.h"
14 :
15 : namespace v8 {
16 : namespace internal {
17 : namespace interpreter {
18 :
19 : class ConstantArrayBuilderTest : public TestWithIsolateAndZone {
20 : public:
21 11 : ConstantArrayBuilderTest() = default;
22 11 : ~ConstantArrayBuilderTest() override = default;
23 :
24 : static const size_t k8BitCapacity = ConstantArrayBuilder::k8BitCapacity;
25 : static const size_t k16BitCapacity = ConstantArrayBuilder::k16BitCapacity;
26 : };
27 :
28 : STATIC_CONST_MEMBER_DEFINITION const size_t
29 : ConstantArrayBuilderTest::k16BitCapacity;
30 : STATIC_CONST_MEMBER_DEFINITION const size_t
31 : ConstantArrayBuilderTest::k8BitCapacity;
32 :
33 15129 : TEST_F(ConstantArrayBuilderTest, AllocateAllEntries) {
34 1 : CanonicalHandleScope canonical(isolate());
35 1 : ConstantArrayBuilder builder(zone());
36 : AstValueFactory ast_factory(zone(), isolate()->ast_string_constants(),
37 2 : isolate()->heap()->HashSeed());
38 65281 : for (size_t i = 0; i < k16BitCapacity; i++) {
39 65280 : builder.Insert(i + 0.5);
40 : }
41 1 : CHECK_EQ(builder.size(), k16BitCapacity);
42 1 : ast_factory.Internalize(isolate());
43 65281 : for (size_t i = 0; i < k16BitCapacity; i++) {
44 261120 : CHECK_EQ(
45 : Handle<HeapNumber>::cast(builder.At(i, isolate()).ToHandleChecked())
46 : ->value(),
47 : i + 0.5);
48 1 : }
49 1 : }
50 :
51 15129 : TEST_F(ConstantArrayBuilderTest, ToFixedArray) {
52 1 : CanonicalHandleScope canonical(isolate());
53 1 : ConstantArrayBuilder builder(zone());
54 : static const int kNumberOfElements = 37;
55 38 : for (int i = 0; i < kNumberOfElements; i++) {
56 37 : builder.Insert(i + 0.5);
57 : }
58 1 : Handle<FixedArray> constant_array = builder.ToFixedArray(isolate());
59 2 : ASSERT_EQ(kNumberOfElements, constant_array->length());
60 38 : for (int i = 0; i < kNumberOfElements; i++) {
61 : Handle<Object> actual(constant_array->get(i), isolate());
62 74 : Handle<Object> expected = builder.At(i, isolate()).ToHandleChecked();
63 111 : ASSERT_EQ(expected->Number(), actual->Number()) << "Failure at index " << i;
64 1 : }
65 : }
66 :
67 15129 : TEST_F(ConstantArrayBuilderTest, ToLargeFixedArray) {
68 1 : CanonicalHandleScope canonical(isolate());
69 1 : ConstantArrayBuilder builder(zone());
70 : static const int kNumberOfElements = 37373;
71 37374 : for (int i = 0; i < kNumberOfElements; i++) {
72 37373 : builder.Insert(i + 0.5);
73 : }
74 1 : Handle<FixedArray> constant_array = builder.ToFixedArray(isolate());
75 2 : ASSERT_EQ(kNumberOfElements, constant_array->length());
76 37374 : for (int i = 0; i < kNumberOfElements; i++) {
77 : Handle<Object> actual(constant_array->get(i), isolate());
78 74746 : Handle<Object> expected = builder.At(i, isolate()).ToHandleChecked();
79 112119 : ASSERT_EQ(expected->Number(), actual->Number()) << "Failure at index " << i;
80 1 : }
81 : }
82 :
83 15129 : TEST_F(ConstantArrayBuilderTest, ToLargeFixedArrayWithReservations) {
84 1 : CanonicalHandleScope canonical(isolate());
85 1 : ConstantArrayBuilder builder(zone());
86 : AstValueFactory ast_factory(zone(), isolate()->ast_string_constants(),
87 2 : isolate()->heap()->HashSeed());
88 : static const int kNumberOfElements = 37373;
89 37374 : for (int i = 0; i < kNumberOfElements; i++) {
90 37373 : builder.CommitReservedEntry(builder.CreateReservedEntry(), Smi::FromInt(i));
91 : }
92 1 : ast_factory.Internalize(isolate());
93 1 : Handle<FixedArray> constant_array = builder.ToFixedArray(isolate());
94 2 : ASSERT_EQ(kNumberOfElements, constant_array->length());
95 37374 : for (int i = 0; i < kNumberOfElements; i++) {
96 : Handle<Object> actual(constant_array->get(i), isolate());
97 74746 : Handle<Object> expected = builder.At(i, isolate()).ToHandleChecked();
98 112119 : ASSERT_EQ(expected->Number(), actual->Number()) << "Failure at index " << i;
99 1 : }
100 : }
101 :
102 15129 : TEST_F(ConstantArrayBuilderTest, AllocateEntriesWithIdx8Reservations) {
103 1 : CanonicalHandleScope canonical(isolate());
104 7 : for (size_t reserved = 1; reserved < k8BitCapacity; reserved *= 3) {
105 6 : ConstantArrayBuilder builder(zone());
106 : AstValueFactory ast_factory(zone(), isolate()->ast_string_constants(),
107 12 : isolate()->heap()->HashSeed());
108 370 : for (size_t i = 0; i < reserved; i++) {
109 364 : OperandSize operand_size = builder.CreateReservedEntry();
110 364 : CHECK_EQ(operand_size, OperandSize::kByte);
111 : }
112 3072 : for (size_t i = 0; i < 2 * k8BitCapacity; i++) {
113 : builder.CommitReservedEntry(builder.CreateReservedEntry(),
114 6144 : Smi::FromInt(static_cast<int>(i)));
115 3072 : if (i + reserved < k8BitCapacity) {
116 1172 : CHECK_LE(builder.size(), k8BitCapacity);
117 1172 : CHECK_EQ(builder.size(), i + 1);
118 : } else {
119 1900 : CHECK_GE(builder.size(), k8BitCapacity);
120 1900 : CHECK_EQ(builder.size(), i + reserved + 1);
121 : }
122 : }
123 6 : CHECK_EQ(builder.size(), 2 * k8BitCapacity + reserved);
124 :
125 : // Commit reserved entries with duplicates and check size does not change.
126 : DCHECK_EQ(reserved + 2 * k8BitCapacity, builder.size());
127 : size_t duplicates_in_idx8_space =
128 12 : std::min(reserved, k8BitCapacity - reserved);
129 140 : for (size_t i = 0; i < duplicates_in_idx8_space; i++) {
130 : builder.CommitReservedEntry(OperandSize::kByte,
131 268 : Smi::FromInt(static_cast<int>(i)));
132 : DCHECK_EQ(reserved + 2 * k8BitCapacity, builder.size());
133 : }
134 :
135 : // Now make reservations, and commit them with unique entries.
136 134 : for (size_t i = 0; i < duplicates_in_idx8_space; i++) {
137 134 : OperandSize operand_size = builder.CreateReservedEntry();
138 134 : CHECK_EQ(operand_size, OperandSize::kByte);
139 : }
140 134 : for (size_t i = 0; i < duplicates_in_idx8_space; i++) {
141 268 : Smi value = Smi::FromInt(static_cast<int>(2 * k8BitCapacity + i));
142 134 : size_t index = builder.CommitReservedEntry(OperandSize::kByte, value);
143 134 : CHECK_EQ(index, k8BitCapacity - reserved + i);
144 : }
145 :
146 : // Clear any remaining uncommited reservations.
147 230 : for (size_t i = 0; i < reserved - duplicates_in_idx8_space; i++) {
148 230 : builder.DiscardReservedEntry(OperandSize::kByte);
149 : }
150 :
151 6 : ast_factory.Internalize(isolate());
152 6 : Handle<FixedArray> constant_array = builder.ToFixedArray(isolate());
153 12 : CHECK_EQ(constant_array->length(),
154 : static_cast<int>(2 * k8BitCapacity + reserved));
155 :
156 : // Check all committed values match expected
157 1172 : for (size_t i = 0; i < k8BitCapacity - reserved; i++) {
158 2344 : Object value = constant_array->get(static_cast<int>(i));
159 1172 : Smi smi = Smi::FromInt(static_cast<int>(i));
160 1172 : CHECK(value->SameValue(smi));
161 : }
162 1900 : for (size_t i = k8BitCapacity; i < 2 * k8BitCapacity + reserved; i++) {
163 3800 : Object value = constant_array->get(static_cast<int>(i));
164 3800 : Smi smi = Smi::FromInt(static_cast<int>(i - reserved));
165 1900 : CHECK(value->SameValue(smi));
166 : }
167 1 : }
168 1 : }
169 :
170 15129 : TEST_F(ConstantArrayBuilderTest, AllocateEntriesWithWideReservations) {
171 1 : CanonicalHandleScope canonical(isolate());
172 7 : for (size_t reserved = 1; reserved < k8BitCapacity; reserved *= 3) {
173 6 : ConstantArrayBuilder builder(zone());
174 : AstValueFactory ast_factory(zone(), isolate()->ast_string_constants(),
175 12 : isolate()->heap()->HashSeed());
176 6 : for (size_t i = 0; i < k8BitCapacity; i++) {
177 : builder.CommitReservedEntry(builder.CreateReservedEntry(),
178 3072 : Smi::FromInt(static_cast<int>(i)));
179 1536 : CHECK_EQ(builder.size(), i + 1);
180 : }
181 364 : for (size_t i = 0; i < reserved; i++) {
182 364 : OperandSize operand_size = builder.CreateReservedEntry();
183 364 : CHECK_EQ(operand_size, OperandSize::kShort);
184 364 : CHECK_EQ(builder.size(), k8BitCapacity);
185 : }
186 364 : for (size_t i = 0; i < reserved; i++) {
187 364 : builder.DiscardReservedEntry(OperandSize::kShort);
188 364 : CHECK_EQ(builder.size(), k8BitCapacity);
189 : }
190 364 : for (size_t i = 0; i < reserved; i++) {
191 364 : OperandSize operand_size = builder.CreateReservedEntry();
192 364 : CHECK_EQ(operand_size, OperandSize::kShort);
193 : builder.CommitReservedEntry(operand_size,
194 728 : Smi::FromInt(static_cast<int>(i)));
195 364 : CHECK_EQ(builder.size(), k8BitCapacity);
196 : }
197 370 : for (size_t i = k8BitCapacity; i < k8BitCapacity + reserved; i++) {
198 364 : OperandSize operand_size = builder.CreateReservedEntry();
199 364 : CHECK_EQ(operand_size, OperandSize::kShort);
200 : builder.CommitReservedEntry(operand_size,
201 728 : Smi::FromInt(static_cast<int>(i)));
202 364 : CHECK_EQ(builder.size(), i + 1);
203 : }
204 :
205 6 : ast_factory.Internalize(isolate());
206 6 : Handle<FixedArray> constant_array = builder.ToFixedArray(isolate());
207 12 : CHECK_EQ(constant_array->length(),
208 : static_cast<int>(k8BitCapacity + reserved));
209 1900 : for (size_t i = 0; i < k8BitCapacity + reserved; i++) {
210 3800 : Object value = constant_array->get(static_cast<int>(i));
211 3800 : CHECK(value->SameValue(*isolate()->factory()->NewNumberFromSize(i)));
212 : }
213 1 : }
214 1 : }
215 :
216 15129 : TEST_F(ConstantArrayBuilderTest, GapFilledWhenLowReservationCommitted) {
217 1 : CanonicalHandleScope canonical(isolate());
218 1 : ConstantArrayBuilder builder(zone());
219 : AstValueFactory ast_factory(zone(), isolate()->ast_string_constants(),
220 2 : isolate()->heap()->HashSeed());
221 257 : for (size_t i = 0; i < k8BitCapacity; i++) {
222 256 : OperandSize operand_size = builder.CreateReservedEntry();
223 256 : CHECK_EQ(OperandSize::kByte, operand_size);
224 256 : CHECK_EQ(builder.size(), 0u);
225 : }
226 256 : for (size_t i = 0; i < k8BitCapacity; i++) {
227 : builder.CommitReservedEntry(builder.CreateReservedEntry(),
228 512 : Smi::FromInt(static_cast<int>(i)));
229 256 : CHECK_EQ(builder.size(), i + k8BitCapacity + 1);
230 : }
231 256 : for (size_t i = 0; i < k8BitCapacity; i++) {
232 : builder.CommitReservedEntry(OperandSize::kByte,
233 512 : Smi::FromInt(static_cast<int>(i)));
234 256 : CHECK_EQ(builder.size(), 2 * k8BitCapacity);
235 : }
236 1 : ast_factory.Internalize(isolate());
237 1 : Handle<FixedArray> constant_array = builder.ToFixedArray(isolate());
238 1 : CHECK_EQ(constant_array->length(), static_cast<int>(2 * k8BitCapacity));
239 256 : for (size_t i = 0; i < k8BitCapacity; i++) {
240 512 : Object original = constant_array->get(static_cast<int>(k8BitCapacity + i));
241 512 : Object duplicate = constant_array->get(static_cast<int>(i));
242 256 : CHECK(original->SameValue(duplicate));
243 256 : Handle<Object> reference = isolate()->factory()->NewNumberFromSize(i);
244 256 : CHECK(original->SameValue(*reference));
245 1 : }
246 1 : }
247 :
248 15129 : TEST_F(ConstantArrayBuilderTest, GapNotFilledWhenLowReservationDiscarded) {
249 1 : CanonicalHandleScope canonical(isolate());
250 1 : ConstantArrayBuilder builder(zone());
251 257 : for (size_t i = 0; i < k8BitCapacity; i++) {
252 256 : OperandSize operand_size = builder.CreateReservedEntry();
253 256 : CHECK_EQ(OperandSize::kByte, operand_size);
254 256 : CHECK_EQ(builder.size(), 0u);
255 : }
256 : double values[k8BitCapacity];
257 256 : for (size_t i = 0; i < k8BitCapacity; i++) {
258 256 : values[i] = i + 0.5;
259 : }
260 :
261 256 : for (size_t i = 0; i < k8BitCapacity; i++) {
262 256 : builder.Insert(values[i]);
263 256 : CHECK_EQ(builder.size(), i + k8BitCapacity + 1);
264 : }
265 256 : for (size_t i = 0; i < k8BitCapacity; i++) {
266 256 : builder.DiscardReservedEntry(OperandSize::kByte);
267 256 : builder.Insert(values[i]);
268 256 : CHECK_EQ(builder.size(), 2 * k8BitCapacity);
269 : }
270 256 : for (size_t i = 0; i < k8BitCapacity; i++) {
271 512 : Handle<Object> reference = isolate()->factory()->NewNumber(i + 0.5);
272 : Handle<Object> original =
273 512 : builder.At(k8BitCapacity + i, isolate()).ToHandleChecked();
274 256 : CHECK(original->SameValue(*reference));
275 256 : MaybeHandle<Object> duplicate = builder.At(i, isolate());
276 256 : CHECK(duplicate.is_null());
277 1 : }
278 1 : }
279 :
280 15129 : TEST_F(ConstantArrayBuilderTest, HolesWithUnusedReservations) {
281 1 : CanonicalHandleScope canonical(isolate());
282 : static int kNumberOfHoles = 128;
283 : static int k8BitCapacity = ConstantArrayBuilder::k8BitCapacity;
284 1 : ConstantArrayBuilder builder(zone());
285 : AstValueFactory ast_factory(zone(), isolate()->ast_string_constants(),
286 2 : isolate()->heap()->HashSeed());
287 129 : for (int i = 0; i < kNumberOfHoles; ++i) {
288 128 : CHECK_EQ(builder.CreateReservedEntry(), OperandSize::kByte);
289 : }
290 : // Values are placed before the reserved entries in the same slice.
291 128 : for (int i = 0; i < k8BitCapacity - kNumberOfHoles; ++i) {
292 128 : CHECK_EQ(builder.Insert(i + 0.5), static_cast<size_t>(i));
293 : }
294 : // The next value is pushed into the next slice.
295 2 : CHECK_EQ(builder.Insert(k8BitCapacity + 0.5), k8BitCapacity);
296 :
297 : // Discard the reserved entries.
298 128 : for (int i = 0; i < kNumberOfHoles; ++i) {
299 128 : builder.DiscardReservedEntry(OperandSize::kByte);
300 : }
301 :
302 1 : ast_factory.Internalize(isolate());
303 1 : Handle<FixedArray> constant_array = builder.ToFixedArray(isolate());
304 2 : CHECK_EQ(constant_array->length(), k8BitCapacity + 1);
305 129 : for (int i = kNumberOfHoles; i < k8BitCapacity; i++) {
306 256 : CHECK(constant_array->get(i)->SameValue(
307 : *isolate()->factory()->the_hole_value()));
308 : }
309 2 : CHECK(!constant_array->get(kNumberOfHoles - 1)
310 : ->SameValue(*isolate()->factory()->the_hole_value()));
311 2 : CHECK(!constant_array->get(k8BitCapacity)
312 1 : ->SameValue(*isolate()->factory()->the_hole_value()));
313 1 : }
314 :
315 15129 : TEST_F(ConstantArrayBuilderTest, ReservationsAtAllScales) {
316 1 : CanonicalHandleScope canonical(isolate());
317 1 : ConstantArrayBuilder builder(zone());
318 : AstValueFactory ast_factory(zone(), isolate()->ast_string_constants(),
319 2 : isolate()->heap()->HashSeed());
320 257 : for (int i = 0; i < 256; i++) {
321 256 : CHECK_EQ(builder.CreateReservedEntry(), OperandSize::kByte);
322 : }
323 65280 : for (int i = 256; i < 65536; ++i) {
324 65280 : CHECK_EQ(builder.CreateReservedEntry(), OperandSize::kShort);
325 : }
326 65536 : for (int i = 65536; i < 131072; ++i) {
327 65536 : CHECK_EQ(builder.CreateReservedEntry(), OperandSize::kQuad);
328 : }
329 1 : CHECK_EQ(builder.CommitReservedEntry(OperandSize::kByte, Smi::FromInt(1)),
330 : 0u);
331 1 : CHECK_EQ(builder.CommitReservedEntry(OperandSize::kShort, Smi::FromInt(2)),
332 : 256u);
333 1 : CHECK_EQ(builder.CommitReservedEntry(OperandSize::kQuad, Smi::FromInt(3)),
334 : 65536u);
335 255 : for (int i = 1; i < 256; i++) {
336 255 : builder.DiscardReservedEntry(OperandSize::kByte);
337 : }
338 65279 : for (int i = 257; i < 65536; ++i) {
339 65279 : builder.DiscardReservedEntry(OperandSize::kShort);
340 : }
341 65535 : for (int i = 65537; i < 131072; ++i) {
342 65535 : builder.DiscardReservedEntry(OperandSize::kQuad);
343 : }
344 :
345 1 : ast_factory.Internalize(isolate());
346 1 : Handle<FixedArray> constant_array = builder.ToFixedArray(isolate());
347 1 : CHECK_EQ(constant_array->length(), 65537);
348 : int count = 1;
349 131075 : for (int i = 0; i < constant_array->length(); ++i) {
350 : Handle<Object> expected;
351 65537 : if (i == 0 || i == 256 || i == 65536) {
352 6 : expected = isolate()->factory()->NewNumber(count++);
353 : } else {
354 : expected = isolate()->factory()->the_hole_value();
355 : }
356 65537 : CHECK(constant_array->get(i)->SameValue(*expected));
357 1 : }
358 1 : }
359 :
360 15129 : TEST_F(ConstantArrayBuilderTest, AllocateEntriesWithFixedReservations) {
361 1 : CanonicalHandleScope canonical(isolate());
362 1 : ConstantArrayBuilder builder(zone());
363 65281 : for (size_t i = 0; i < k16BitCapacity; i++) {
364 65280 : if ((i % 2) == 0) {
365 32640 : CHECK_EQ(i, builder.InsertDeferred());
366 : } else {
367 65280 : builder.Insert(Smi::FromInt(static_cast<int>(i)));
368 : }
369 : }
370 1 : CHECK_EQ(builder.size(), k16BitCapacity);
371 :
372 : // Check values before reserved entries are inserted.
373 65280 : for (size_t i = 0; i < k16BitCapacity; i++) {
374 65280 : if ((i % 2) == 0) {
375 : // Check reserved values are null.
376 32640 : MaybeHandle<Object> empty = builder.At(i, isolate());
377 32640 : CHECK(empty.is_null());
378 : } else {
379 130560 : CHECK_EQ(Handle<Smi>::cast(builder.At(i, isolate()).ToHandleChecked())
380 : ->value(),
381 : static_cast<int>(i));
382 : }
383 : }
384 :
385 : // Insert reserved entries.
386 32640 : for (size_t i = 0; i < k16BitCapacity; i += 2) {
387 : builder.SetDeferredAt(i,
388 65280 : handle(Smi::FromInt(static_cast<int>(i)), isolate()));
389 : }
390 :
391 : // Check values after reserved entries are inserted.
392 65280 : for (size_t i = 0; i < k16BitCapacity; i++) {
393 261120 : CHECK_EQ(
394 : Handle<Smi>::cast(builder.At(i, isolate()).ToHandleChecked())->value(),
395 : static_cast<int>(i));
396 1 : }
397 1 : }
398 :
399 : } // namespace interpreter
400 : } // namespace internal
401 9075 : } // namespace v8
|
