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: 19 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 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 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 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 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 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 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 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 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 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