1 // Copyright 2017 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/map-updater.h"
6
7 #include "src/field-type.h"
8 #include "src/handles.h"
9 #include "src/isolate.h"
10 #include "src/objects-inl.h"
11 #include "src/objects.h"
12 #include "src/transitions.h"
13
14 namespace v8 {
15 namespace internal {
16
17 namespace {
18
EqualImmutableValues(Object * obj1,Object * obj2)19 inline bool EqualImmutableValues(Object* obj1, Object* obj2) {
20 if (obj1 == obj2) return true; // Valid for both kData and kAccessor kinds.
21 // TODO(ishell): compare AccessorPairs.
22 return false;
23 }
24
25 } // namespace
26
GetKey(int descriptor) const27 Name* MapUpdater::GetKey(int descriptor) const {
28 return old_descriptors_->GetKey(descriptor);
29 }
30
GetDetails(int descriptor) const31 PropertyDetails MapUpdater::GetDetails(int descriptor) const {
32 DCHECK_LE(0, descriptor);
33 if (descriptor == modified_descriptor_) {
34 return PropertyDetails(new_kind_, new_attributes_, new_location_,
35 new_constness_, new_representation_);
36 }
37 return old_descriptors_->GetDetails(descriptor);
38 }
39
GetValue(int descriptor) const40 Object* MapUpdater::GetValue(int descriptor) const {
41 DCHECK_LE(0, descriptor);
42 if (descriptor == modified_descriptor_) {
43 DCHECK_EQ(kDescriptor, new_location_);
44 return *new_value_;
45 }
46 DCHECK_EQ(kDescriptor, GetDetails(descriptor).location());
47 return old_descriptors_->GetValue(descriptor);
48 }
49
GetFieldType(int descriptor) const50 FieldType* MapUpdater::GetFieldType(int descriptor) const {
51 DCHECK_LE(0, descriptor);
52 if (descriptor == modified_descriptor_) {
53 DCHECK_EQ(kField, new_location_);
54 return *new_field_type_;
55 }
56 DCHECK_EQ(kField, GetDetails(descriptor).location());
57 return old_descriptors_->GetFieldType(descriptor);
58 }
59
GetOrComputeFieldType(int descriptor,PropertyLocation location,Representation representation) const60 Handle<FieldType> MapUpdater::GetOrComputeFieldType(
61 int descriptor, PropertyLocation location,
62 Representation representation) const {
63 DCHECK_LE(0, descriptor);
64 // |location| is just a pre-fetched GetDetails(descriptor).location().
65 DCHECK_EQ(location, GetDetails(descriptor).location());
66 if (location == kField) {
67 return handle(GetFieldType(descriptor), isolate_);
68 } else {
69 return GetValue(descriptor)->OptimalType(isolate_, representation);
70 }
71 }
72
GetOrComputeFieldType(Handle<DescriptorArray> descriptors,int descriptor,PropertyLocation location,Representation representation)73 Handle<FieldType> MapUpdater::GetOrComputeFieldType(
74 Handle<DescriptorArray> descriptors, int descriptor,
75 PropertyLocation location, Representation representation) {
76 // |location| is just a pre-fetched GetDetails(descriptor).location().
77 DCHECK_EQ(descriptors->GetDetails(descriptor).location(), location);
78 if (location == kField) {
79 return handle(descriptors->GetFieldType(descriptor), isolate_);
80 } else {
81 return descriptors->GetValue(descriptor)
82 ->OptimalType(isolate_, representation);
83 }
84 }
85
ReconfigureToDataField(int descriptor,PropertyAttributes attributes,PropertyConstness constness,Representation representation,Handle<FieldType> field_type)86 Handle<Map> MapUpdater::ReconfigureToDataField(int descriptor,
87 PropertyAttributes attributes,
88 PropertyConstness constness,
89 Representation representation,
90 Handle<FieldType> field_type) {
91 DCHECK_EQ(kInitialized, state_);
92 DCHECK_LE(0, descriptor);
93 DCHECK(!old_map_->is_dictionary_map());
94 modified_descriptor_ = descriptor;
95 new_kind_ = kData;
96 new_attributes_ = attributes;
97 new_location_ = kField;
98
99 PropertyDetails old_details =
100 old_descriptors_->GetDetails(modified_descriptor_);
101
102 // If property kind is not reconfigured merge the result with
103 // representation/field type from the old descriptor.
104 if (old_details.kind() == new_kind_) {
105 new_constness_ = GeneralizeConstness(constness, old_details.constness());
106
107 Representation old_representation = old_details.representation();
108 new_representation_ = representation.generalize(old_representation);
109
110 Handle<FieldType> old_field_type =
111 GetOrComputeFieldType(old_descriptors_, modified_descriptor_,
112 old_details.location(), new_representation_);
113
114 new_field_type_ =
115 Map::GeneralizeFieldType(old_representation, old_field_type,
116 new_representation_, field_type, isolate_);
117 } else {
118 // We don't know if this is a first property kind reconfiguration
119 // and we don't know which value was in this property previously
120 // therefore we can't treat such a property as constant.
121 new_constness_ = kMutable;
122 new_representation_ = representation;
123 new_field_type_ = field_type;
124 }
125
126 Map::GeneralizeIfCanHaveTransitionableFastElementsKind(
127 isolate_, old_map_->instance_type(), &new_constness_,
128 &new_representation_, &new_field_type_);
129
130 if (TryRecofigureToDataFieldInplace() == kEnd) return result_map_;
131 if (FindRootMap() == kEnd) return result_map_;
132 if (FindTargetMap() == kEnd) return result_map_;
133 ConstructNewMap();
134 DCHECK_EQ(kEnd, state_);
135 return result_map_;
136 }
137
ReconfigureElementsKind(ElementsKind elements_kind)138 Handle<Map> MapUpdater::ReconfigureElementsKind(ElementsKind elements_kind) {
139 DCHECK_EQ(kInitialized, state_);
140 new_elements_kind_ = elements_kind;
141 is_transitionable_fast_elements_kind_ =
142 IsTransitionableFastElementsKind(new_elements_kind_);
143
144 if (FindRootMap() == kEnd) return result_map_;
145 if (FindTargetMap() == kEnd) return result_map_;
146 ConstructNewMap();
147 DCHECK_EQ(kEnd, state_);
148 return result_map_;
149 }
150
Update()151 Handle<Map> MapUpdater::Update() {
152 DCHECK_EQ(kInitialized, state_);
153 DCHECK(old_map_->is_deprecated());
154
155 if (FindRootMap() == kEnd) return result_map_;
156 if (FindTargetMap() == kEnd) return result_map_;
157 ConstructNewMap();
158 DCHECK_EQ(kEnd, state_);
159 return result_map_;
160 }
161
GeneralizeField(Handle<Map> map,int modify_index,PropertyConstness new_constness,Representation new_representation,Handle<FieldType> new_field_type)162 void MapUpdater::GeneralizeField(Handle<Map> map, int modify_index,
163 PropertyConstness new_constness,
164 Representation new_representation,
165 Handle<FieldType> new_field_type) {
166 Map::GeneralizeField(map, modify_index, new_constness, new_representation,
167 new_field_type);
168
169 DCHECK_EQ(*old_descriptors_, old_map_->instance_descriptors());
170 }
171
CopyGeneralizeAllFields(const char * reason)172 MapUpdater::State MapUpdater::CopyGeneralizeAllFields(const char* reason) {
173 result_map_ = Map::CopyGeneralizeAllFields(old_map_, new_elements_kind_,
174 modified_descriptor_, new_kind_,
175 new_attributes_, reason);
176 state_ = kEnd;
177 return state_; // Done.
178 }
179
TryRecofigureToDataFieldInplace()180 MapUpdater::State MapUpdater::TryRecofigureToDataFieldInplace() {
181 // If it's just a representation generalization case (i.e. property kind and
182 // attributes stays unchanged) it's fine to transition from None to anything
183 // but double without any modification to the object, because the default
184 // uninitialized value for representation None can be overwritten by both
185 // smi and tagged values. Doubles, however, would require a box allocation.
186 if (new_representation_.IsNone() || new_representation_.IsDouble()) {
187 return state_; // Not done yet.
188 }
189
190 PropertyDetails old_details =
191 old_descriptors_->GetDetails(modified_descriptor_);
192 Representation old_representation = old_details.representation();
193 if (!old_representation.IsNone()) {
194 return state_; // Not done yet.
195 }
196
197 DCHECK_EQ(new_kind_, old_details.kind());
198 DCHECK_EQ(new_attributes_, old_details.attributes());
199 DCHECK_EQ(kField, old_details.location());
200 if (FLAG_trace_generalization) {
201 old_map_->PrintGeneralization(
202 stdout, "uninitialized field", modified_descriptor_, old_nof_, old_nof_,
203 false, old_representation, new_representation_,
204 handle(old_descriptors_->GetFieldType(modified_descriptor_), isolate_),
205 MaybeHandle<Object>(), new_field_type_, MaybeHandle<Object>());
206 }
207 Handle<Map> field_owner(old_map_->FindFieldOwner(modified_descriptor_),
208 isolate_);
209
210 GeneralizeField(field_owner, modified_descriptor_, new_constness_,
211 new_representation_, new_field_type_);
212 // Check that the descriptor array was updated.
213 DCHECK(old_descriptors_->GetDetails(modified_descriptor_)
214 .representation()
215 .Equals(new_representation_));
216 DCHECK(old_descriptors_->GetFieldType(modified_descriptor_)
217 ->NowIs(new_field_type_));
218
219 result_map_ = old_map_;
220 state_ = kEnd;
221 return state_; // Done.
222 }
223
FindRootMap()224 MapUpdater::State MapUpdater::FindRootMap() {
225 DCHECK_EQ(kInitialized, state_);
226 // Check the state of the root map.
227 root_map_ = handle(old_map_->FindRootMap(), isolate_);
228 ElementsKind from_kind = root_map_->elements_kind();
229 ElementsKind to_kind = new_elements_kind_;
230 if (root_map_->is_deprecated()) {
231 state_ = kEnd;
232 result_map_ = handle(
233 JSFunction::cast(root_map_->GetConstructor())->initial_map(), isolate_);
234 if (from_kind != to_kind) {
235 result_map_ = Map::AsElementsKind(result_map_, to_kind);
236 }
237 DCHECK(result_map_->is_dictionary_map());
238 return state_;
239 }
240 int root_nof = root_map_->NumberOfOwnDescriptors();
241 if (!old_map_->EquivalentToForTransition(*root_map_)) {
242 return CopyGeneralizeAllFields("GenAll_NotEquivalent");
243 }
244
245 // TODO(ishell): Add a test for SLOW_SLOPPY_ARGUMENTS_ELEMENTS.
246 if (from_kind != to_kind && to_kind != DICTIONARY_ELEMENTS &&
247 to_kind != SLOW_STRING_WRAPPER_ELEMENTS &&
248 to_kind != SLOW_SLOPPY_ARGUMENTS_ELEMENTS &&
249 !(IsTransitionableFastElementsKind(from_kind) &&
250 IsMoreGeneralElementsKindTransition(from_kind, to_kind))) {
251 return CopyGeneralizeAllFields("GenAll_InvalidElementsTransition");
252 }
253
254 if (modified_descriptor_ >= 0 && modified_descriptor_ < root_nof) {
255 PropertyDetails old_details =
256 old_descriptors_->GetDetails(modified_descriptor_);
257 if (old_details.kind() != new_kind_ ||
258 old_details.attributes() != new_attributes_) {
259 return CopyGeneralizeAllFields("GenAll_RootModification1");
260 }
261 if (old_details.location() != kField) {
262 return CopyGeneralizeAllFields("GenAll_RootModification2");
263 }
264 if (new_constness_ != old_details.constness() &&
265 (!FLAG_modify_map_inplace || !old_map_->is_prototype_map())) {
266 return CopyGeneralizeAllFields("GenAll_RootModification3");
267 }
268 if (!new_representation_.fits_into(old_details.representation())) {
269 return CopyGeneralizeAllFields("GenAll_RootModification4");
270 }
271
272 DCHECK_EQ(kData, old_details.kind());
273 DCHECK_EQ(kData, new_kind_);
274 DCHECK_EQ(kField, new_location_);
275 FieldType* old_field_type =
276 old_descriptors_->GetFieldType(modified_descriptor_);
277 if (!new_field_type_->NowIs(old_field_type)) {
278 return CopyGeneralizeAllFields("GenAll_RootModification5");
279 }
280
281 // Modify root map in-place.
282 if (FLAG_modify_map_inplace && new_constness_ != old_details.constness()) {
283 // Only prototype root maps are allowed to be updated in-place.
284 // TODO(ishell): fix all the stubs that use prototype map check to
285 // ensure that the prototype was not modified.
286 DCHECK(old_map_->is_prototype_map());
287 DCHECK(old_map_->is_stable());
288 DCHECK(IsGeneralizableTo(old_details.constness(), new_constness_));
289 GeneralizeField(old_map_, modified_descriptor_, new_constness_,
290 old_details.representation(),
291 handle(old_field_type, isolate_));
292 }
293 }
294
295 // From here on, use the map with correct elements kind as root map.
296 if (from_kind != to_kind) {
297 root_map_ = Map::AsElementsKind(root_map_, to_kind);
298 }
299 state_ = kAtRootMap;
300 return state_; // Not done yet.
301 }
302
FindTargetMap()303 MapUpdater::State MapUpdater::FindTargetMap() {
304 DCHECK_EQ(kAtRootMap, state_);
305 target_map_ = root_map_;
306
307 int root_nof = root_map_->NumberOfOwnDescriptors();
308 for (int i = root_nof; i < old_nof_; ++i) {
309 PropertyDetails old_details = GetDetails(i);
310 Map* transition = TransitionsAccessor(target_map_)
311 .SearchTransition(GetKey(i), old_details.kind(),
312 old_details.attributes());
313 if (transition == nullptr) break;
314 Handle<Map> tmp_map(transition, isolate_);
315
316 Handle<DescriptorArray> tmp_descriptors(tmp_map->instance_descriptors(),
317 isolate_);
318
319 // Check if target map is incompatible.
320 PropertyDetails tmp_details = tmp_descriptors->GetDetails(i);
321 DCHECK_EQ(old_details.kind(), tmp_details.kind());
322 DCHECK_EQ(old_details.attributes(), tmp_details.attributes());
323 if (old_details.kind() == kAccessor &&
324 !EqualImmutableValues(GetValue(i), tmp_descriptors->GetValue(i))) {
325 // TODO(ishell): mutable accessors are not implemented yet.
326 return CopyGeneralizeAllFields("GenAll_Incompatible");
327 }
328 PropertyConstness tmp_constness = tmp_details.constness();
329 if (!FLAG_modify_map_inplace &&
330 !IsGeneralizableTo(old_details.constness(), tmp_constness)) {
331 break;
332 }
333 if (!IsGeneralizableTo(old_details.location(), tmp_details.location())) {
334 break;
335 }
336 Representation tmp_representation = tmp_details.representation();
337 if (!old_details.representation().fits_into(tmp_representation)) {
338 break;
339 }
340
341 if (tmp_details.location() == kField) {
342 Handle<FieldType> old_field_type =
343 GetOrComputeFieldType(i, old_details.location(), tmp_representation);
344 PropertyConstness constness =
345 FLAG_modify_map_inplace ? old_details.constness() : tmp_constness;
346 GeneralizeField(tmp_map, i, constness, tmp_representation,
347 old_field_type);
348 } else {
349 // kDescriptor: Check that the value matches.
350 if (!EqualImmutableValues(GetValue(i), tmp_descriptors->GetValue(i))) {
351 break;
352 }
353 }
354 DCHECK(!tmp_map->is_deprecated());
355 target_map_ = tmp_map;
356 }
357
358 // Directly change the map if the target map is more general.
359 int target_nof = target_map_->NumberOfOwnDescriptors();
360 if (target_nof == old_nof_) {
361 #ifdef DEBUG
362 if (modified_descriptor_ >= 0) {
363 DescriptorArray* target_descriptors = target_map_->instance_descriptors();
364 PropertyDetails details =
365 target_descriptors->GetDetails(modified_descriptor_);
366 DCHECK_EQ(new_kind_, details.kind());
367 DCHECK_EQ(new_attributes_, details.attributes());
368 DCHECK(IsGeneralizableTo(new_constness_, details.constness()));
369 DCHECK_EQ(new_location_, details.location());
370 DCHECK(new_representation_.fits_into(details.representation()));
371 if (new_location_ == kField) {
372 DCHECK_EQ(kField, details.location());
373 DCHECK(new_field_type_->NowIs(
374 target_descriptors->GetFieldType(modified_descriptor_)));
375 } else {
376 DCHECK(details.location() == kField ||
377 EqualImmutableValues(*new_value_, target_descriptors->GetValue(
378 modified_descriptor_)));
379 }
380 }
381 #endif
382 if (*target_map_ != *old_map_) {
383 old_map_->NotifyLeafMapLayoutChange();
384 }
385 result_map_ = target_map_;
386 state_ = kEnd;
387 return state_; // Done.
388 }
389
390 // Find the last compatible target map in the transition tree.
391 for (int i = target_nof; i < old_nof_; ++i) {
392 PropertyDetails old_details = GetDetails(i);
393 Map* transition = TransitionsAccessor(target_map_)
394 .SearchTransition(GetKey(i), old_details.kind(),
395 old_details.attributes());
396 if (transition == nullptr) break;
397 Handle<Map> tmp_map(transition, isolate_);
398 Handle<DescriptorArray> tmp_descriptors(tmp_map->instance_descriptors(),
399 isolate_);
400 #ifdef DEBUG
401 // Check that target map is compatible.
402 PropertyDetails tmp_details = tmp_descriptors->GetDetails(i);
403 DCHECK_EQ(old_details.kind(), tmp_details.kind());
404 DCHECK_EQ(old_details.attributes(), tmp_details.attributes());
405 #endif
406 if (old_details.kind() == kAccessor &&
407 !EqualImmutableValues(GetValue(i), tmp_descriptors->GetValue(i))) {
408 return CopyGeneralizeAllFields("GenAll_Incompatible");
409 }
410 DCHECK(!tmp_map->is_deprecated());
411 target_map_ = tmp_map;
412 }
413
414 state_ = kAtTargetMap;
415 return state_; // Not done yet.
416 }
417
BuildDescriptorArray()418 Handle<DescriptorArray> MapUpdater::BuildDescriptorArray() {
419 InstanceType instance_type = old_map_->instance_type();
420 int target_nof = target_map_->NumberOfOwnDescriptors();
421 Handle<DescriptorArray> target_descriptors(
422 target_map_->instance_descriptors(), isolate_);
423
424 // Allocate a new descriptor array large enough to hold the required
425 // descriptors, with minimally the exact same size as the old descriptor
426 // array.
427 int new_slack =
428 Max(old_nof_, old_descriptors_->number_of_descriptors()) - old_nof_;
429 Handle<DescriptorArray> new_descriptors =
430 DescriptorArray::Allocate(isolate_, old_nof_, new_slack);
431 DCHECK(new_descriptors->length() > target_descriptors->length() ||
432 new_descriptors->NumberOfSlackDescriptors() > 0 ||
433 new_descriptors->number_of_descriptors() ==
434 old_descriptors_->number_of_descriptors());
435 DCHECK(new_descriptors->number_of_descriptors() == old_nof_);
436
437 int root_nof = root_map_->NumberOfOwnDescriptors();
438
439 // Given that we passed root modification check in FindRootMap() so
440 // the root descriptors are either not modified at all or already more
441 // general than we requested. Take |root_nof| entries as is.
442 // 0 -> |root_nof|
443 int current_offset = 0;
444 for (int i = 0; i < root_nof; ++i) {
445 PropertyDetails old_details = old_descriptors_->GetDetails(i);
446 if (old_details.location() == kField) {
447 current_offset += old_details.field_width_in_words();
448 }
449 Descriptor d(handle(GetKey(i), isolate_),
450 handle(old_descriptors_->GetValue(i), isolate_), old_details);
451 new_descriptors->Set(i, &d);
452 }
453
454 // Merge "updated" old_descriptor entries with target_descriptor entries.
455 // |root_nof| -> |target_nof|
456 for (int i = root_nof; i < target_nof; ++i) {
457 Handle<Name> key(GetKey(i), isolate_);
458 PropertyDetails old_details = GetDetails(i);
459 PropertyDetails target_details = target_descriptors->GetDetails(i);
460
461 PropertyKind next_kind = old_details.kind();
462 PropertyAttributes next_attributes = old_details.attributes();
463 DCHECK_EQ(next_kind, target_details.kind());
464 DCHECK_EQ(next_attributes, target_details.attributes());
465
466 PropertyConstness next_constness = GeneralizeConstness(
467 old_details.constness(), target_details.constness());
468
469 // Note: failed values equality check does not invalidate per-object
470 // property constness.
471 PropertyLocation next_location =
472 old_details.location() == kField ||
473 target_details.location() == kField ||
474 !EqualImmutableValues(target_descriptors->GetValue(i),
475 GetValue(i))
476 ? kField
477 : kDescriptor;
478
479 if (!FLAG_track_constant_fields && next_location == kField) {
480 next_constness = kMutable;
481 }
482 // Ensure that mutable values are stored in fields.
483 DCHECK_IMPLIES(next_constness == kMutable, next_location == kField);
484
485 Representation next_representation =
486 old_details.representation().generalize(
487 target_details.representation());
488
489 if (next_location == kField) {
490 Handle<FieldType> old_field_type =
491 GetOrComputeFieldType(i, old_details.location(), next_representation);
492
493 Handle<FieldType> target_field_type =
494 GetOrComputeFieldType(target_descriptors, i,
495 target_details.location(), next_representation);
496
497 Handle<FieldType> next_field_type = Map::GeneralizeFieldType(
498 old_details.representation(), old_field_type, next_representation,
499 target_field_type, isolate_);
500
501 Map::GeneralizeIfCanHaveTransitionableFastElementsKind(
502 isolate_, instance_type, &next_constness, &next_representation,
503 &next_field_type);
504
505 Handle<Object> wrapped_type(Map::WrapFieldType(next_field_type));
506 Descriptor d;
507 if (next_kind == kData) {
508 d = Descriptor::DataField(key, current_offset, next_attributes,
509 next_constness, next_representation,
510 wrapped_type);
511 } else {
512 // TODO(ishell): mutable accessors are not implemented yet.
513 UNIMPLEMENTED();
514 }
515 current_offset += d.GetDetails().field_width_in_words();
516 new_descriptors->Set(i, &d);
517 } else {
518 DCHECK_EQ(kDescriptor, next_location);
519 DCHECK_EQ(kConst, next_constness);
520
521 Handle<Object> value(GetValue(i), isolate_);
522 Descriptor d;
523 if (next_kind == kData) {
524 DCHECK(!FLAG_track_constant_fields);
525 d = Descriptor::DataConstant(key, value, next_attributes);
526 } else {
527 DCHECK_EQ(kAccessor, next_kind);
528 d = Descriptor::AccessorConstant(key, value, next_attributes);
529 }
530 new_descriptors->Set(i, &d);
531 }
532 }
533
534 // Take "updated" old_descriptor entries.
535 // |target_nof| -> |old_nof|
536 for (int i = target_nof; i < old_nof_; ++i) {
537 PropertyDetails old_details = GetDetails(i);
538 Handle<Name> key(GetKey(i), isolate_);
539
540 PropertyKind next_kind = old_details.kind();
541 PropertyAttributes next_attributes = old_details.attributes();
542 PropertyConstness next_constness = old_details.constness();
543 PropertyLocation next_location = old_details.location();
544 Representation next_representation = old_details.representation();
545
546 Descriptor d;
547 if (next_location == kField) {
548 Handle<FieldType> next_field_type =
549 GetOrComputeFieldType(i, old_details.location(), next_representation);
550
551 // If the |new_elements_kind_| is still transitionable then the old map's
552 // elements kind is also transitionable and therefore the old descriptors
553 // array must already have non in-place generalizable fields.
554 CHECK_IMPLIES(is_transitionable_fast_elements_kind_,
555 !Map::IsInplaceGeneralizableField(
556 next_constness, next_representation, *next_field_type));
557
558 Handle<Object> wrapped_type(Map::WrapFieldType(next_field_type));
559 Descriptor d;
560 if (next_kind == kData) {
561 DCHECK_IMPLIES(!FLAG_track_constant_fields, next_constness == kMutable);
562 d = Descriptor::DataField(key, current_offset, next_attributes,
563 next_constness, next_representation,
564 wrapped_type);
565 } else {
566 // TODO(ishell): mutable accessors are not implemented yet.
567 UNIMPLEMENTED();
568 }
569 current_offset += d.GetDetails().field_width_in_words();
570 new_descriptors->Set(i, &d);
571 } else {
572 DCHECK_EQ(kDescriptor, next_location);
573 DCHECK_EQ(kConst, next_constness);
574
575 Handle<Object> value(GetValue(i), isolate_);
576 if (next_kind == kData) {
577 d = Descriptor::DataConstant(key, value, next_attributes);
578 } else {
579 DCHECK_EQ(kAccessor, next_kind);
580 d = Descriptor::AccessorConstant(key, value, next_attributes);
581 }
582 new_descriptors->Set(i, &d);
583 }
584 }
585
586 new_descriptors->Sort();
587 return new_descriptors;
588 }
589
FindSplitMap(Handle<DescriptorArray> descriptors)590 Handle<Map> MapUpdater::FindSplitMap(Handle<DescriptorArray> descriptors) {
591 DisallowHeapAllocation no_allocation;
592
593 int root_nof = root_map_->NumberOfOwnDescriptors();
594 Map* current = *root_map_;
595 for (int i = root_nof; i < old_nof_; i++) {
596 Name* name = descriptors->GetKey(i);
597 PropertyDetails details = descriptors->GetDetails(i);
598 Map* next =
599 TransitionsAccessor(current, &no_allocation)
600 .SearchTransition(name, details.kind(), details.attributes());
601 if (next == nullptr) break;
602 DescriptorArray* next_descriptors = next->instance_descriptors();
603
604 PropertyDetails next_details = next_descriptors->GetDetails(i);
605 DCHECK_EQ(details.kind(), next_details.kind());
606 DCHECK_EQ(details.attributes(), next_details.attributes());
607 if (details.constness() != next_details.constness()) break;
608 if (details.location() != next_details.location()) break;
609 if (!details.representation().Equals(next_details.representation())) break;
610
611 if (next_details.location() == kField) {
612 FieldType* next_field_type = next_descriptors->GetFieldType(i);
613 if (!descriptors->GetFieldType(i)->NowIs(next_field_type)) {
614 break;
615 }
616 } else {
617 if (!EqualImmutableValues(descriptors->GetValue(i),
618 next_descriptors->GetValue(i))) {
619 break;
620 }
621 }
622 current = next;
623 }
624 return handle(current, isolate_);
625 }
626
ConstructNewMap()627 MapUpdater::State MapUpdater::ConstructNewMap() {
628 Handle<DescriptorArray> new_descriptors = BuildDescriptorArray();
629
630 Handle<Map> split_map = FindSplitMap(new_descriptors);
631 int split_nof = split_map->NumberOfOwnDescriptors();
632 DCHECK_NE(old_nof_, split_nof);
633
634 PropertyDetails split_details = GetDetails(split_nof);
635 TransitionsAccessor transitions(split_map);
636
637 // Invalidate a transition target at |key|.
638 Map* maybe_transition = transitions.SearchTransition(
639 GetKey(split_nof), split_details.kind(), split_details.attributes());
640 if (maybe_transition != nullptr) {
641 maybe_transition->DeprecateTransitionTree();
642 }
643
644 // If |maybe_transition| is not nullptr then the transition array already
645 // contains entry for given descriptor. This means that the transition
646 // could be inserted regardless of whether transitions array is full or not.
647 if (maybe_transition == nullptr && !transitions.CanHaveMoreTransitions()) {
648 return CopyGeneralizeAllFields("GenAll_CantHaveMoreTransitions");
649 }
650
651 old_map_->NotifyLeafMapLayoutChange();
652
653 if (FLAG_trace_generalization && modified_descriptor_ >= 0) {
654 PropertyDetails old_details =
655 old_descriptors_->GetDetails(modified_descriptor_);
656 PropertyDetails new_details =
657 new_descriptors->GetDetails(modified_descriptor_);
658 MaybeHandle<FieldType> old_field_type;
659 MaybeHandle<FieldType> new_field_type;
660 MaybeHandle<Object> old_value;
661 MaybeHandle<Object> new_value;
662 if (old_details.location() == kField) {
663 old_field_type = handle(
664 old_descriptors_->GetFieldType(modified_descriptor_), isolate_);
665 } else {
666 old_value =
667 handle(old_descriptors_->GetValue(modified_descriptor_), isolate_);
668 }
669 if (new_details.location() == kField) {
670 new_field_type =
671 handle(new_descriptors->GetFieldType(modified_descriptor_), isolate_);
672 } else {
673 new_value =
674 handle(new_descriptors->GetValue(modified_descriptor_), isolate_);
675 }
676
677 old_map_->PrintGeneralization(
678 stdout, "", modified_descriptor_, split_nof, old_nof_,
679 old_details.location() == kDescriptor && new_location_ == kField,
680 old_details.representation(), new_details.representation(),
681 old_field_type, old_value, new_field_type, new_value);
682 }
683
684 Handle<LayoutDescriptor> new_layout_descriptor =
685 LayoutDescriptor::New(split_map, new_descriptors, old_nof_);
686
687 Handle<Map> new_map = Map::AddMissingTransitions(split_map, new_descriptors,
688 new_layout_descriptor);
689
690 // Deprecated part of the transition tree is no longer reachable, so replace
691 // current instance descriptors in the "survived" part of the tree with
692 // the new descriptors to maintain descriptors sharing invariant.
693 split_map->ReplaceDescriptors(*new_descriptors, *new_layout_descriptor);
694
695 result_map_ = new_map;
696 state_ = kEnd;
697 return state_; // Done.
698 }
699
700 } // namespace internal
701 } // namespace v8
702