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/factory.h"
8 #include "src/handles-inl.h"
9 #include "src/interpreter/constant-array-builder.h"
10 #include "src/isolate.h"
11 #include "test/unittests/test-utils.h"
12
13 namespace v8 {
14 namespace internal {
15 namespace interpreter {
16
17 class ConstantArrayBuilderTest : public TestWithIsolateAndZone {
18 public:
ConstantArrayBuilderTest()19 ConstantArrayBuilderTest() {}
~ConstantArrayBuilderTest()20 ~ConstantArrayBuilderTest() override {}
21
22 static const size_t k8BitCapacity = ConstantArrayBuilder::k8BitCapacity;
23 static const size_t k16BitCapacity = ConstantArrayBuilder::k16BitCapacity;
24 };
25
26 STATIC_CONST_MEMBER_DEFINITION const size_t
27 ConstantArrayBuilderTest::k16BitCapacity;
28 STATIC_CONST_MEMBER_DEFINITION const size_t
29 ConstantArrayBuilderTest::k8BitCapacity;
30
TEST_F(ConstantArrayBuilderTest,AllocateAllEntries)31 TEST_F(ConstantArrayBuilderTest, AllocateAllEntries) {
32 ConstantArrayBuilder builder(isolate(), zone());
33 for (size_t i = 0; i < k16BitCapacity; i++) {
34 builder.Insert(handle(Smi::FromInt(static_cast<int>(i)), isolate()));
35 }
36 CHECK_EQ(builder.size(), k16BitCapacity);
37 for (size_t i = 0; i < k16BitCapacity; i++) {
38 CHECK_EQ(Handle<Smi>::cast(builder.At(i))->value(), i);
39 }
40 }
41
TEST_F(ConstantArrayBuilderTest,AllocateEntriesWithIdx8Reservations)42 TEST_F(ConstantArrayBuilderTest, AllocateEntriesWithIdx8Reservations) {
43 for (size_t reserved = 1; reserved < k8BitCapacity; reserved *= 3) {
44 ConstantArrayBuilder builder(isolate(), zone());
45 for (size_t i = 0; i < reserved; i++) {
46 OperandSize operand_size = builder.CreateReservedEntry();
47 CHECK(operand_size == OperandSize::kByte);
48 }
49 for (size_t i = 0; i < 2 * k8BitCapacity; i++) {
50 Handle<Object> object = isolate()->factory()->NewNumberFromSize(i);
51 builder.Insert(object);
52 if (i + reserved < k8BitCapacity) {
53 CHECK_LE(builder.size(), k8BitCapacity);
54 CHECK_EQ(builder.size(), i + 1);
55 CHECK(builder.At(i)->SameValue(*object));
56 } else {
57 CHECK_GE(builder.size(), k8BitCapacity);
58 CHECK_EQ(builder.size(), i + reserved + 1);
59 CHECK(builder.At(i + reserved)->SameValue(*object));
60 }
61 }
62 CHECK_EQ(builder.size(), 2 * k8BitCapacity + reserved);
63
64 // Check reserved values represented by the hole.
65 for (size_t i = 0; i < reserved; i++) {
66 Handle<Object> empty = builder.At(k8BitCapacity - reserved + i);
67 CHECK(empty->SameValue(isolate()->heap()->the_hole_value()));
68 }
69
70 // Commmit reserved entries with duplicates and check size does not change.
71 DCHECK_EQ(reserved + 2 * k8BitCapacity, builder.size());
72 size_t duplicates_in_idx8_space =
73 std::min(reserved, k8BitCapacity - reserved);
74 for (size_t i = 0; i < duplicates_in_idx8_space; i++) {
75 builder.CommitReservedEntry(OperandSize::kByte,
76 isolate()->factory()->NewNumberFromSize(i));
77 DCHECK_EQ(reserved + 2 * k8BitCapacity, builder.size());
78 }
79
80 // Check all committed values match expected (holes where
81 // duplicates_in_idx8_space allocated).
82 for (size_t i = 0; i < k8BitCapacity - reserved; i++) {
83 Smi* smi = Smi::FromInt(static_cast<int>(i));
84 CHECK(Handle<Smi>::cast(builder.At(i))->SameValue(smi));
85 }
86 for (size_t i = k8BitCapacity; i < 2 * k8BitCapacity + reserved; i++) {
87 Smi* smi = Smi::FromInt(static_cast<int>(i - reserved));
88 CHECK(Handle<Smi>::cast(builder.At(i))->SameValue(smi));
89 }
90 for (size_t i = 0; i < reserved; i++) {
91 size_t index = k8BitCapacity - reserved + i;
92 CHECK(builder.At(index)->IsTheHole(isolate()));
93 }
94
95 // Now make reservations, and commit them with unique entries.
96 for (size_t i = 0; i < duplicates_in_idx8_space; i++) {
97 OperandSize operand_size = builder.CreateReservedEntry();
98 CHECK(operand_size == OperandSize::kByte);
99 }
100 for (size_t i = 0; i < duplicates_in_idx8_space; i++) {
101 Handle<Object> object =
102 isolate()->factory()->NewNumberFromSize(2 * k8BitCapacity + i);
103 size_t index = builder.CommitReservedEntry(OperandSize::kByte, object);
104 CHECK_EQ(static_cast<int>(index), k8BitCapacity - reserved + i);
105 CHECK(builder.At(static_cast<int>(index))->SameValue(*object));
106 }
107 CHECK_EQ(builder.size(), 2 * k8BitCapacity + reserved);
108 }
109 }
110
TEST_F(ConstantArrayBuilderTest,AllocateEntriesWithWideReservations)111 TEST_F(ConstantArrayBuilderTest, AllocateEntriesWithWideReservations) {
112 for (size_t reserved = 1; reserved < k8BitCapacity; reserved *= 3) {
113 ConstantArrayBuilder builder(isolate(), zone());
114 for (size_t i = 0; i < k8BitCapacity; i++) {
115 Handle<Object> object = isolate()->factory()->NewNumberFromSize(i);
116 builder.Insert(object);
117 CHECK(builder.At(i)->SameValue(*object));
118 CHECK_EQ(builder.size(), i + 1);
119 }
120 for (size_t i = 0; i < reserved; i++) {
121 OperandSize operand_size = builder.CreateReservedEntry();
122 CHECK(operand_size == OperandSize::kShort);
123 CHECK_EQ(builder.size(), k8BitCapacity);
124 }
125 for (size_t i = 0; i < reserved; i++) {
126 builder.DiscardReservedEntry(OperandSize::kShort);
127 CHECK_EQ(builder.size(), k8BitCapacity);
128 }
129 for (size_t i = 0; i < reserved; i++) {
130 OperandSize operand_size = builder.CreateReservedEntry();
131 CHECK(operand_size == OperandSize::kShort);
132 Handle<Object> object = isolate()->factory()->NewNumberFromSize(i);
133 builder.CommitReservedEntry(operand_size, object);
134 CHECK_EQ(builder.size(), k8BitCapacity);
135 }
136 for (size_t i = k8BitCapacity; i < k8BitCapacity + reserved; i++) {
137 OperandSize operand_size = builder.CreateReservedEntry();
138 CHECK(operand_size == OperandSize::kShort);
139 Handle<Object> object = isolate()->factory()->NewNumberFromSize(i);
140 builder.CommitReservedEntry(operand_size, object);
141 CHECK_EQ(builder.size(), i + 1);
142 }
143 }
144 }
145
146
TEST_F(ConstantArrayBuilderTest,ToFixedArray)147 TEST_F(ConstantArrayBuilderTest, ToFixedArray) {
148 ConstantArrayBuilder builder(isolate(), zone());
149 static const size_t kNumberOfElements = 37;
150 for (size_t i = 0; i < kNumberOfElements; i++) {
151 Handle<Object> object = isolate()->factory()->NewNumberFromSize(i);
152 builder.Insert(object);
153 CHECK(builder.At(i)->SameValue(*object));
154 }
155 Handle<FixedArray> constant_array = builder.ToFixedArray();
156 CHECK_EQ(constant_array->length(), kNumberOfElements);
157 for (size_t i = 0; i < kNumberOfElements; i++) {
158 CHECK(constant_array->get(static_cast<int>(i))->SameValue(*builder.At(i)));
159 }
160 }
161
TEST_F(ConstantArrayBuilderTest,ToLargeFixedArray)162 TEST_F(ConstantArrayBuilderTest, ToLargeFixedArray) {
163 ConstantArrayBuilder builder(isolate(), zone());
164 static const size_t kNumberOfElements = 37373;
165 for (size_t i = 0; i < kNumberOfElements; i++) {
166 Handle<Object> object = isolate()->factory()->NewNumberFromSize(i);
167 builder.Insert(object);
168 CHECK(builder.At(i)->SameValue(*object));
169 }
170 Handle<FixedArray> constant_array = builder.ToFixedArray();
171 CHECK_EQ(constant_array->length(), kNumberOfElements);
172 for (size_t i = 0; i < kNumberOfElements; i++) {
173 CHECK(constant_array->get(static_cast<int>(i))->SameValue(*builder.At(i)));
174 }
175 }
176
TEST_F(ConstantArrayBuilderTest,GapFilledWhenLowReservationCommitted)177 TEST_F(ConstantArrayBuilderTest, GapFilledWhenLowReservationCommitted) {
178 ConstantArrayBuilder builder(isolate(), zone());
179 for (size_t i = 0; i < k8BitCapacity; i++) {
180 OperandSize operand_size = builder.CreateReservedEntry();
181 CHECK(OperandSize::kByte == operand_size);
182 CHECK_EQ(builder.size(), 0);
183 }
184 for (size_t i = 0; i < k8BitCapacity; i++) {
185 Handle<Object> object = isolate()->factory()->NewNumberFromSize(i);
186 builder.Insert(object);
187 CHECK_EQ(builder.size(), i + k8BitCapacity + 1);
188 }
189 for (size_t i = 0; i < k8BitCapacity; i++) {
190 builder.CommitReservedEntry(OperandSize::kByte,
191 builder.At(i + k8BitCapacity));
192 CHECK_EQ(builder.size(), 2 * k8BitCapacity);
193 }
194 for (size_t i = 0; i < k8BitCapacity; i++) {
195 Handle<Object> original = builder.At(k8BitCapacity + i);
196 Handle<Object> duplicate = builder.At(i);
197 CHECK(original->SameValue(*duplicate));
198 Handle<Object> reference = isolate()->factory()->NewNumberFromSize(i);
199 CHECK(original->SameValue(*reference));
200 }
201 }
202
TEST_F(ConstantArrayBuilderTest,GapNotFilledWhenLowReservationDiscarded)203 TEST_F(ConstantArrayBuilderTest, GapNotFilledWhenLowReservationDiscarded) {
204 ConstantArrayBuilder builder(isolate(), zone());
205 for (size_t i = 0; i < k8BitCapacity; i++) {
206 OperandSize operand_size = builder.CreateReservedEntry();
207 CHECK(OperandSize::kByte == operand_size);
208 CHECK_EQ(builder.size(), 0);
209 }
210 for (size_t i = 0; i < k8BitCapacity; i++) {
211 Handle<Object> object = isolate()->factory()->NewNumberFromSize(i);
212 builder.Insert(object);
213 CHECK_EQ(builder.size(), i + k8BitCapacity + 1);
214 }
215 for (size_t i = 0; i < k8BitCapacity; i++) {
216 builder.DiscardReservedEntry(OperandSize::kByte);
217 builder.Insert(builder.At(i + k8BitCapacity));
218 CHECK_EQ(builder.size(), 2 * k8BitCapacity);
219 }
220 for (size_t i = 0; i < k8BitCapacity; i++) {
221 Handle<Object> reference = isolate()->factory()->NewNumberFromSize(i);
222 Handle<Object> original = builder.At(k8BitCapacity + i);
223 CHECK(original->SameValue(*reference));
224 Handle<Object> duplicate = builder.At(i);
225 CHECK(duplicate->SameValue(*isolate()->factory()->the_hole_value()));
226 }
227 }
228
TEST_F(ConstantArrayBuilderTest,HolesWithUnusedReservations)229 TEST_F(ConstantArrayBuilderTest, HolesWithUnusedReservations) {
230 static int kNumberOfHoles = 128;
231 ConstantArrayBuilder builder(isolate(), zone());
232 for (int i = 0; i < kNumberOfHoles; ++i) {
233 CHECK_EQ(builder.CreateReservedEntry(), OperandSize::kByte);
234 }
235 for (int i = 0; i < 128; ++i) {
236 CHECK_EQ(builder.Insert(isolate()->factory()->NewNumber(i)), i);
237 }
238 CHECK_EQ(builder.Insert(isolate()->factory()->NewNumber(256)), 256);
239
240 Handle<FixedArray> constant_array = builder.ToFixedArray();
241 CHECK_EQ(constant_array->length(), 257);
242 for (int i = 128; i < 256; i++) {
243 CHECK(constant_array->get(i)->SameValue(
244 *isolate()->factory()->the_hole_value()));
245 }
246 CHECK(!constant_array->get(127)->SameValue(
247 *isolate()->factory()->the_hole_value()));
248 CHECK(!constant_array->get(256)->SameValue(
249 *isolate()->factory()->the_hole_value()));
250 }
251
TEST_F(ConstantArrayBuilderTest,ReservationsAtAllScales)252 TEST_F(ConstantArrayBuilderTest, ReservationsAtAllScales) {
253 ConstantArrayBuilder builder(isolate(), zone());
254 for (int i = 0; i < 256; i++) {
255 CHECK_EQ(builder.CreateReservedEntry(), OperandSize::kByte);
256 }
257 for (int i = 256; i < 65536; ++i) {
258 CHECK_EQ(builder.CreateReservedEntry(), OperandSize::kShort);
259 }
260 for (int i = 65536; i < 131072; ++i) {
261 CHECK_EQ(builder.CreateReservedEntry(), OperandSize::kQuad);
262 }
263 CHECK_EQ(builder.CommitReservedEntry(OperandSize::kByte,
264 isolate()->factory()->NewNumber(1)),
265 0);
266 CHECK_EQ(builder.CommitReservedEntry(OperandSize::kShort,
267 isolate()->factory()->NewNumber(2)),
268 256);
269 CHECK_EQ(builder.CommitReservedEntry(OperandSize::kQuad,
270 isolate()->factory()->NewNumber(3)),
271 65536);
272 Handle<FixedArray> constant_array = builder.ToFixedArray();
273 CHECK_EQ(constant_array->length(), 65537);
274 int count = 1;
275 for (int i = 0; i < constant_array->length(); ++i) {
276 Handle<Object> expected;
277 if (i == 0 || i == 256 || i == 65536) {
278 expected = isolate()->factory()->NewNumber(count++);
279 } else {
280 expected = isolate()->factory()->the_hole_value();
281 }
282 CHECK(constant_array->get(i)->SameValue(*expected));
283 }
284 }
285
286 } // namespace interpreter
287 } // namespace internal
288 } // namespace v8
289