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