Revert of Simplify and compact transitions storage

src/objects.cc

 // Copyright 2013 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include <iomanip>
 #include <sstream>
 
 #include "src/v8.h"
 
 #include "src/accessors.h"
@@ skipping 1882 matching lines @@
     if (!new_map->is_dictionary_map()) {
       Handle<Map> old_map(object->map());
       MigrateFastToFast(object, new_map);
       if (old_map->is_prototype_map()) {
         // Clear out the old descriptor array to avoid problems to sharing
         // the descriptor array without using an explicit.
         old_map->InitializeDescriptors(
             old_map->GetHeap()->empty_descriptor_array(),
             LayoutDescriptor::FastPointerLayout());
         // Ensure that no transition was inserted for prototype migrations.
-        DCHECK_EQ(0, TransitionArray::NumberOfTransitions(
-                         old_map->raw_transitions()));
+        DCHECK(!old_map->HasTransitionArray());
         DCHECK(new_map->GetBackPointer()->IsUndefined());
       }
     } else {
       MigrateFastToSlow(object, new_map, 0);
     }
   } else {
     // For slow-to-fast migrations JSObject::TransformToFastProperties()
     // must be used instead.
     CHECK(new_map->is_dictionary_map());
 
@@ skipping 265 matching lines @@
           details.representation(), Representation::Tagged(), field_type,
           HeapType::Any());
     }
   }
   return new_map;
 }
 
 
 void Map::DeprecateTransitionTree() {
   if (is_deprecated()) return;
-  Object* transitions = raw_transitions();
-  int num_transitions = TransitionArray::NumberOfTransitions(transitions);
-  for (int i = 0; i < num_transitions; ++i) {
-    TransitionArray::GetTarget(transitions, i)->DeprecateTransitionTree();
+  if (HasTransitionArray()) {
+    TransitionArray* transitions = this->transitions();
+    for (int i = 0; i < transitions->number_of_transitions(); i++) {
+      transitions->GetTarget(i)->DeprecateTransitionTree();
+    }
   }
   deprecate();
   dependent_code()->DeoptimizeDependentCodeGroup(
       GetIsolate(), DependentCode::kTransitionGroup);
   NotifyLeafMapLayoutChange();
 }
 
 
 static inline bool EqualImmutableValues(Object* obj1, Object* obj2) {
   if (obj1 == obj2) return true;  // Valid for both kData and kAccessor kinds.
   // TODO(ishell): compare AccessorPairs.
   return false;
 }
 
 
 // Invalidates a transition target at |key|, and installs |new_descriptors| over
 // the current instance_descriptors to ensure proper sharing of descriptor
 // arrays.
 // Returns true if the transition target at given key was deprecated.
 bool Map::DeprecateTarget(PropertyKind kind, Name* key,
                           PropertyAttributes attributes,
                           DescriptorArray* new_descriptors,
                           LayoutDescriptor* new_layout_descriptor) {
   bool transition_target_deprecated = false;
-  Map* maybe_transition =
-      TransitionArray::SearchTransition(this, kind, key, attributes);
-  if (maybe_transition != NULL) {
-    maybe_transition->DeprecateTransitionTree();
-    transition_target_deprecated = true;
+  if (HasTransitionArray()) {
+    TransitionArray* transitions = this->transitions();
+    int transition = transitions->Search(kind, key, attributes);
+    if (transition != TransitionArray::kNotFound) {
+      transitions->GetTarget(transition)->DeprecateTransitionTree();
+      transition_target_deprecated = true;
+    }
   }
 
   // Don't overwrite the empty descriptor array.
   if (NumberOfOwnDescriptors() == 0) return transition_target_deprecated;
 
   DescriptorArray* to_replace = instance_descriptors();
   Map* current = this;
   GetHeap()->incremental_marking()->RecordWrites(to_replace);
   while (current->instance_descriptors() == to_replace) {
     current->SetEnumLength(kInvalidEnumCacheSentinel);
@@ skipping 22 matching lines @@
                            int length,
                            DescriptorArray* descriptors) {
   DisallowHeapAllocation no_allocation;
 
   // This can only be called on roots of transition trees.
   DCHECK_EQ(verbatim, NumberOfOwnDescriptors());
 
   Map* current = this;
 
   for (int i = verbatim; i < length; i++) {
+    if (!current->HasTransitionArray()) break;
     Name* name = descriptors->GetKey(i);
     PropertyDetails details = descriptors->GetDetails(i);
-    Map* next = TransitionArray::SearchTransition(current, details.kind(), name,
-                                                  details.attributes());
-    if (next == NULL) break;
+    TransitionArray* transitions = current->transitions();
+    int transition =
+        transitions->Search(details.kind(), name, details.attributes());
+    if (transition == TransitionArray::kNotFound) break;
+
+    Map* next = transitions->GetTarget(transition);
     DescriptorArray* next_descriptors = next->instance_descriptors();
 
     PropertyDetails next_details = next_descriptors->GetDetails(i);
     DCHECK_EQ(details.kind(), next_details.kind());
     DCHECK_EQ(details.attributes(), next_details.attributes());
     if (details.location() != next_details.location()) break;
     if (!details.representation().Equals(next_details.representation())) break;
 
     if (next_details.location() == kField) {
       HeapType* next_field_type = next_descriptors->GetFieldType(i);
@@ skipping 27 matching lines @@
 }
 
 
 void Map::UpdateFieldType(int descriptor, Handle<Name> name,
                           Representation new_representation,
                           Handle<Object> new_wrapped_type) {
   DCHECK(new_wrapped_type->IsSmi() || new_wrapped_type->IsWeakCell());
   DisallowHeapAllocation no_allocation;
   PropertyDetails details = instance_descriptors()->GetDetails(descriptor);
   if (details.type() != DATA) return;
-  Object* transitions = raw_transitions();
-  int num_transitions = TransitionArray::NumberOfTransitions(transitions);
-  for (int i = 0; i < num_transitions; ++i) {
-    Map* target = TransitionArray::GetTarget(transitions, i);
-    target->UpdateFieldType(descriptor, name, new_representation,
-                            new_wrapped_type);
+  if (HasTransitionArray()) {
+    TransitionArray* transitions = this->transitions();
+    for (int i = 0; i < transitions->number_of_transitions(); ++i) {
+      transitions->GetTarget(i)->UpdateFieldType(
+          descriptor, name, new_representation, new_wrapped_type);
+    }
   }
   // It is allowed to change representation here only from None to something.
   DCHECK(details.representation().Equals(new_representation) ||
          details.representation().IsNone());
 
   // Skip if already updated the shared descriptor.
   if (instance_descriptors()->GetValue(descriptor) == *new_wrapped_type) return;
   DataDescriptor d(name, instance_descriptors()->GetFieldIndex(descriptor),
                    new_wrapped_type, details.attributes(), new_representation);
   instance_descriptors()->Replace(descriptor, &d);
@@ skipping 219 matching lines @@
         next_representation =
             next_representation.generalize(old_details.representation());
       }
 
     } else {
       next_kind = old_details.kind();
       next_location = old_details.location();
       next_attributes = old_details.attributes();
       next_representation = old_details.representation();
     }
-    Map* transition = TransitionArray::SearchTransition(
-        *target_map, next_kind, old_descriptors->GetKey(i), next_attributes);
-    if (transition == NULL) break;
-    Handle<Map> tmp_map(transition, isolate);
-
+    int j = target_map->SearchTransition(next_kind, old_descriptors->GetKey(i),
+                                         next_attributes);
+    if (j == TransitionArray::kNotFound) break;
+    Handle<Map> tmp_map(target_map->GetTransition(j), isolate);
     Handle<DescriptorArray> tmp_descriptors = handle(
         tmp_map->instance_descriptors(), isolate);
 
     // Check if target map is incompatible.
     PropertyDetails tmp_details = tmp_descriptors->GetDetails(i);
     DCHECK_EQ(next_kind, tmp_details.kind());
     DCHECK_EQ(next_attributes, tmp_details.attributes());
     if (next_kind == kAccessor &&
         !EqualImmutableValues(old_descriptors->GetValue(i),
                               tmp_descriptors->GetValue(i))) {
@@ skipping 64 matching lines @@
     PropertyDetails old_details = old_descriptors->GetDetails(i);
     PropertyKind next_kind;
     PropertyAttributes next_attributes;
     if (modify_index == i) {
       next_kind = new_kind;
       next_attributes = new_attributes;
     } else {
       next_kind = old_details.kind();
       next_attributes = old_details.attributes();
     }
-    Map* transition = TransitionArray::SearchTransition(
-        *target_map, next_kind, old_descriptors->GetKey(i), next_attributes);
-    if (transition == NULL) break;
-    Handle<Map> tmp_map(transition, isolate);
+    int j = target_map->SearchTransition(next_kind, old_descriptors->GetKey(i),
+                                         next_attributes);
+    if (j == TransitionArray::kNotFound) break;
+    Handle<Map> tmp_map(target_map->GetTransition(j), isolate);
     Handle<DescriptorArray> tmp_descriptors(
         tmp_map->instance_descriptors(), isolate);
 
     // Check if target map is compatible.
 #ifdef DEBUG
     PropertyDetails tmp_details = tmp_descriptors->GetDetails(i);
     DCHECK_EQ(next_kind, tmp_details.kind());
     DCHECK_EQ(next_attributes, tmp_details.attributes());
 #endif
     if (next_kind == kAccessor &&
@@ skipping 217 matching lines @@
     split_kind = split_prop_details.kind();
     split_attributes = split_prop_details.attributes();
   }
   bool transition_target_deprecated = split_map->DeprecateTarget(
       split_kind, old_descriptors->GetKey(split_nof), split_attributes,
       *new_descriptors, *new_layout_descriptor);
 
   // If |transition_target_deprecated| is true then the transition array
   // already contains entry for given descriptor. This means that the transition
   // could be inserted regardless of whether transitions array is full or not.
-  if (!transition_target_deprecated &&
-      !TransitionArray::CanHaveMoreTransitions(split_map)) {
+  if (!transition_target_deprecated && !split_map->CanHaveMoreTransitions()) {
     return CopyGeneralizeAllRepresentations(old_map, modify_index, store_mode,
                                             new_kind, new_attributes,
                                             "GenAll_CantHaveMoreTransitions");
   }
 
   if (FLAG_trace_generalization && modify_index >= 0) {
     PropertyDetails old_details = old_descriptors->GetDetails(modify_index);
     PropertyDetails new_details = new_descriptors->GetDetails(modify_index);
     Handle<HeapType> old_field_type =
         (old_details.type() == DATA)
@@ skipping 52 matching lines @@
   Map* root_map = old_map->FindRootMap();
   if (!old_map->EquivalentToForTransition(root_map)) return MaybeHandle<Map>();
   int root_nof = root_map->NumberOfOwnDescriptors();
 
   int old_nof = old_map->NumberOfOwnDescriptors();
   DescriptorArray* old_descriptors = old_map->instance_descriptors();
 
   Map* new_map = root_map;
   for (int i = root_nof; i < old_nof; ++i) {
     PropertyDetails old_details = old_descriptors->GetDetails(i);
-    Map* transition = TransitionArray::SearchTransition(
-        new_map, old_details.kind(), old_descriptors->GetKey(i),
-        old_details.attributes());
-    if (transition == NULL) return MaybeHandle<Map>();
-    new_map = transition;
+    int j = new_map->SearchTransition(old_details.kind(),
+                                      old_descriptors->GetKey(i),
+                                      old_details.attributes());
+    if (j == TransitionArray::kNotFound) return MaybeHandle<Map>();
+    new_map = new_map->GetTransition(j);
     DescriptorArray* new_descriptors = new_map->instance_descriptors();
 
     PropertyDetails new_details = new_descriptors->GetDetails(i);
     DCHECK_EQ(old_details.kind(), new_details.kind());
     DCHECK_EQ(old_details.attributes(), new_details.attributes());
     if (!old_details.representation().fits_into(new_details.representation())) {
       return MaybeHandle<Map>();
     }
     switch (new_details.type()) {
       case DATA: {
@@ skipping 621 matching lines @@
       IsFastElementsKind(to_kind) || IsExternalArrayElementsKind(to_kind)
       ? to_kind
       : TERMINAL_FAST_ELEMENTS_KIND;
 
   // Support for legacy API: SetIndexedPropertiesTo{External,Pixel}Data
   // allows to change elements from arbitrary kind to any ExternalArray
   // elements kind. Satisfy its requirements, checking whether we already
   // have the cached transition.
   if (IsExternalArrayElementsKind(to_kind) &&
       !IsFixedTypedArrayElementsKind(map->elements_kind())) {
-    Map* next_map = map->ElementsTransitionMap();
-    if (next_map != NULL && next_map->elements_kind() == to_kind) {
-      return next_map;
+    if (map->HasElementsTransition()) {
+        Map* next_map = map->elements_transition_map();
+        if (next_map->elements_kind() == to_kind) return next_map;
     }
     return map;
   }
 
   ElementsKind kind = map->elements_kind();
   while (kind != target_kind) {
     kind = GetNextTransitionElementsKind(kind);
-    Map* next_map = current_map->ElementsTransitionMap();
-    if (next_map == NULL) return current_map;
-    current_map = next_map;
+    if (!current_map->HasElementsTransition()) return current_map;
+    current_map = current_map->elements_transition_map();
   }
 
-  Map* next_map = current_map->ElementsTransitionMap();
-  if (to_kind != kind && next_map != NULL) {
+  if (to_kind != kind && current_map->HasElementsTransition()) {
     DCHECK(to_kind == DICTIONARY_ELEMENTS);
+    Map* next_map = current_map->elements_transition_map();
     if (next_map->elements_kind() == to_kind) return next_map;
   }
 
   DCHECK(current_map->elements_kind() == target_kind);
   return current_map;
 }
 
 
 Map* Map::LookupElementsTransitionMap(ElementsKind to_kind) {
   Map* to_map = FindClosestElementsTransition(this, to_kind);
@@ skipping 2079 matching lines @@
   if (attrs == NONE) {
     transition_marker = isolate->factory()->nonextensible_symbol();
   } else if (attrs == SEALED) {
     transition_marker = isolate->factory()->sealed_symbol();
   } else {
     DCHECK(attrs == FROZEN);
     transition_marker = isolate->factory()->frozen_symbol();
   }
 
   Handle<Map> old_map(object->map(), isolate);
-  Map* transition =
-      TransitionArray::SearchSpecial(*old_map, *transition_marker);
-  if (transition != NULL) {
-    Handle<Map> transition_map(transition, isolate);
+  int transition_index = old_map->SearchSpecialTransition(*transition_marker);
+  if (transition_index != TransitionArray::kNotFound) {
+    Handle<Map> transition_map(old_map->GetTransition(transition_index));
     DCHECK(transition_map->has_dictionary_elements());
     DCHECK(!transition_map->is_extensible());
     JSObject::MigrateToMap(object, transition_map);
-  } else if (object->HasFastProperties() &&
-             TransitionArray::CanHaveMoreTransitions(old_map)) {
+  } else if (object->HasFastProperties() && old_map->CanHaveMoreTransitions()) {
     // Create a new descriptor array with the appropriate property attributes
     Handle<Map> new_map = Map::CopyForPreventExtensions(
         old_map, attrs, transition_marker, "CopyForPreventExtensions");
     JSObject::MigrateToMap(object, new_map);
   } else {
     DCHECK(old_map->is_dictionary_map() || !old_map->is_prototype_map());
     // Slow path: need to normalize properties for safety
     NormalizeProperties(object, CLEAR_INOBJECT_PROPERTIES, 0,
                         "SlowPreventExtensions");
 
@@ skipping 38 matching lines @@
 }
 
 
 void JSObject::SetObserved(Handle<JSObject> object) {
   DCHECK(!object->IsJSGlobalProxy());
   DCHECK(!object->IsJSGlobalObject());
   Isolate* isolate = object->GetIsolate();
   Handle<Map> new_map;
   Handle<Map> old_map(object->map(), isolate);
   DCHECK(!old_map->is_observed());
-  Map* transition = TransitionArray::SearchSpecial(
-      *old_map, isolate->heap()->observed_symbol());
-  if (transition != NULL) {
-    new_map = handle(transition, isolate);
+  int transition_index =
+      old_map->SearchSpecialTransition(isolate->heap()->observed_symbol());
+  if (transition_index != TransitionArray::kNotFound) {
+    new_map = handle(old_map->GetTransition(transition_index), isolate);
     DCHECK(new_map->is_observed());
-  } else if (object->HasFastProperties() &&
-             TransitionArray::CanHaveMoreTransitions(old_map)) {
+  } else if (object->HasFastProperties() && old_map->CanHaveMoreTransitions()) {
     new_map = Map::CopyForObserved(old_map);
   } else {
     new_map = Map::Copy(old_map, "SlowObserved");
     new_map->set_is_observed();
   }
   JSObject::MigrateToMap(object, new_map);
 }
 
 
 Handle<Object> JSObject::FastPropertyAt(Handle<JSObject> object,
@@ skipping 1198 matching lines @@
     PrintF("[TraceMaps: %s from= %p to= %p name= ", what,
            reinterpret_cast<void*>(from), reinterpret_cast<void*>(to));
     name->NameShortPrint();
     PrintF(" ]\n");
   }
 }
 
 
 // static
 void Map::TraceAllTransitions(Map* map) {
-  Object* transitions = map->raw_transitions();
-  int num_transitions = TransitionArray::NumberOfTransitions(transitions);
-  for (int i = -0; i < num_transitions; ++i) {
-    Map* target = TransitionArray::GetTarget(transitions, i);
-    Name* key = TransitionArray::GetKey(transitions, i);
-    Map::TraceTransition("Transition", map, target, key);
+  if (!map->HasTransitionArray()) return;
+  TransitionArray* transitions = map->transitions();
+  for (int i = 0; i < transitions->number_of_transitions(); ++i) {
+    Map* target = transitions->GetTarget(i);
+    Map::TraceTransition("Transition", map, target, transitions->GetKey(i));
     Map::TraceAllTransitions(target);
   }
 }
 
 #endif  // TRACE_MAPS
 
 
 void Map::ConnectTransition(Handle<Map> parent, Handle<Map> child,
                             Handle<Name> name, SimpleTransitionFlag flag) {
   parent->set_owns_descriptors(false);
   if (parent->is_prototype_map()) {
     DCHECK(child->is_prototype_map());
 #if TRACE_MAPS
     Map::TraceTransition("NoTransition", *parent, *child, *name);
 #endif
   } else {
-    TransitionArray::Insert(parent, name, child, flag);
+    Handle<TransitionArray> transitions =
+        TransitionArray::Insert(parent, name, child, flag);
+    if (!parent->HasTransitionArray() ||
+        *transitions != parent->transitions()) {
+      parent->set_transitions(*transitions);
+    }
+    child->SetBackPointer(*parent);
     if (child->prototype()->IsJSObject()) {
       Handle<JSObject> proto(JSObject::cast(child->prototype()));
       if (!child->ShouldRegisterAsPrototypeUser(proto)) {
         JSObject::UnregisterPrototypeUser(proto, child);
       }
     }
 #if TRACE_MAPS
     Map::TraceTransition("Transition", *parent, *child, *name);
 #endif
   }
 }
 
 
 Handle<Map> Map::CopyReplaceDescriptors(
     Handle<Map> map, Handle<DescriptorArray> descriptors,
     Handle<LayoutDescriptor> layout_descriptor, TransitionFlag flag,
     MaybeHandle<Name> maybe_name, const char* reason,
     SimpleTransitionFlag simple_flag) {
   DCHECK(descriptors->IsSortedNoDuplicates());
 
   Handle<Map> result = CopyDropDescriptors(map);
 
   if (!map->is_prototype_map()) {
-    if (flag == INSERT_TRANSITION &&
-        TransitionArray::CanHaveMoreTransitions(map)) {
+    if (flag == INSERT_TRANSITION && map->CanHaveMoreTransitions()) {
       result->InitializeDescriptors(*descriptors, *layout_descriptor);
 
       Handle<Name> name;
       CHECK(maybe_name.ToHandle(&name));
       ConnectTransition(map, result, name, simple_flag);
     } else {
       int length = descriptors->number_of_descriptors();
       for (int i = 0; i < length; i++) {
         descriptors->SetRepresentation(i, Representation::Tagged());
         if (descriptors->GetDetails(i).type() == DATA) {
           descriptors->SetValue(i, HeapType::Any());
         }
       }
       result->InitializeDescriptors(*descriptors,
                                     LayoutDescriptor::FastPointerLayout());
     }
   } else {
     result->InitializeDescriptors(*descriptors, *layout_descriptor);
   }
 #if TRACE_MAPS
   if (FLAG_trace_maps &&
       // Mirror conditions above that did not call ConnectTransition().
       (map->is_prototype_map() ||
-       !(flag == INSERT_TRANSITION &&
-         TransitionArray::CanHaveMoreTransitions(map)))) {
+       !(flag == INSERT_TRANSITION && map->CanHaveMoreTransitions()))) {
     PrintF("[TraceMaps: ReplaceDescriptors from= %p to= %p reason= %s ]\n",
            reinterpret_cast<void*>(*map), reinterpret_cast<void*>(*result),
            reason);
   }
 #endif
 
   return result;
 }
 
 
@@ skipping 37 matching lines @@
 
   Handle<Name> name = handle(descriptors->GetKey(new_descriptor));
   ConnectTransition(map, result, name, SIMPLE_PROPERTY_TRANSITION);
 
   return result;
 }
 
 
 Handle<Map> Map::CopyAsElementsKind(Handle<Map> map, ElementsKind kind,
                                     TransitionFlag flag) {
-  Map* maybe_elements_transition_map = NULL;
   if (flag == INSERT_TRANSITION) {
-    maybe_elements_transition_map = map->ElementsTransitionMap();
-    DCHECK(
-        maybe_elements_transition_map == NULL ||
-        ((maybe_elements_transition_map->elements_kind() ==
-              DICTIONARY_ELEMENTS ||
+    DCHECK(!map->HasElementsTransition() ||
+        ((map->elements_transition_map()->elements_kind() ==
+          DICTIONARY_ELEMENTS ||
           IsExternalArrayElementsKind(
-              maybe_elements_transition_map->elements_kind())) &&
-         (kind == DICTIONARY_ELEMENTS || IsExternalArrayElementsKind(kind))));
+              map->elements_transition_map()->elements_kind())) &&
+         (kind == DICTIONARY_ELEMENTS ||
+          IsExternalArrayElementsKind(kind))));
     DCHECK(!IsFastElementsKind(kind) ||
            IsMoreGeneralElementsKindTransition(map->elements_kind(), kind));
     DCHECK(kind != map->elements_kind());
   }
 
   bool insert_transition = flag == INSERT_TRANSITION &&
-                           TransitionArray::CanHaveMoreTransitions(map) &&
-                           maybe_elements_transition_map == NULL;
+                           map->CanHaveMoreTransitions() &&
+                           !map->HasElementsTransition();
 
   if (insert_transition) {
     Handle<Map> new_map = CopyForTransition(map, "CopyAsElementsKind");
     new_map->set_elements_kind(kind);
 
     ConnectElementsTransition(map, new_map);
 
     return new_map;
   }
 
   // Create a new free-floating map only if we are not allowed to store it.
   Handle<Map> new_map = Copy(map, "CopyAsElementsKind");
   new_map->set_elements_kind(kind);
   return new_map;
 }
 
 
 Handle<Map> Map::CopyForObserved(Handle<Map> map) {
   DCHECK(!map->is_observed());
 
   Isolate* isolate = map->GetIsolate();
 
   bool insert_transition =
-      TransitionArray::CanHaveMoreTransitions(map) && !map->is_prototype_map();
+      map->CanHaveMoreTransitions() && !map->is_prototype_map();
 
   if (insert_transition) {
     Handle<Map> new_map = CopyForTransition(map, "CopyForObserved");
     new_map->set_is_observed();
 
     Handle<Name> name = isolate->factory()->observed_symbol();
     ConnectTransition(map, new_map, name, SPECIAL_TRANSITION);
     return new_map;
   }
 
@@ skipping 145 matching lines @@
 Handle<Map> Map::TransitionToDataProperty(Handle<Map> map, Handle<Name> name,
                                           Handle<Object> value,
                                           PropertyAttributes attributes,
                                           StoreFromKeyed store_mode) {
   // Dictionary maps can always have additional data properties.
   if (map->is_dictionary_map()) return map;
 
   // Migrate to the newest map before storing the property.
   map = Update(map);
 
-  Map* maybe_transition =
-      TransitionArray::SearchTransition(*map, kData, *name, attributes);
-  if (maybe_transition != NULL) {
-    Handle<Map> transition(maybe_transition);
+  int index = map->SearchTransition(kData, *name, attributes);
+  if (index != TransitionArray::kNotFound) {
+    Handle<Map> transition(map->GetTransition(index));
     int descriptor = transition->LastAdded();
 
     DCHECK_EQ(attributes, transition->instance_descriptors()
                               ->GetDetails(descriptor)
                               .attributes());
 
     return Map::PrepareForDataProperty(transition, descriptor, value);
   }
 
   TransitionFlag flag = INSERT_TRANSITION;
@@ skipping 68 matching lines @@
     return map;
   }
 
   // Migrate to the newest map before transitioning to the new property.
   map = Update(map);
 
   PropertyNormalizationMode mode = map->is_prototype_map()
                                        ? KEEP_INOBJECT_PROPERTIES
                                        : CLEAR_INOBJECT_PROPERTIES;
 
-  Map* maybe_transition =
-      TransitionArray::SearchTransition(*map, kAccessor, *name, attributes);
-  if (maybe_transition != NULL) {
-    Handle<Map> transition(maybe_transition, isolate);
+  int index = map->SearchTransition(kAccessor, *name, attributes);
+  if (index != TransitionArray::kNotFound) {
+    Handle<Map> transition(map->GetTransition(index));
     DescriptorArray* descriptors = transition->instance_descriptors();
     int descriptor = transition->LastAdded();
     DCHECK(descriptors->GetKey(descriptor)->Equals(*name));
 
     DCHECK_EQ(kAccessor, descriptors->GetDetails(descriptor).kind());
     DCHECK_EQ(attributes, descriptors->GetDetails(descriptor).attributes());
 
     Handle<Object> maybe_pair(descriptors->GetValue(descriptor), isolate);
     if (!maybe_pair->IsAccessorPair()) {
       return Map::Normalize(map, mode, "TransitionToAccessorFromNonPair");
@@ skipping 51 matching lines @@
 
 
 Handle<Map> Map::CopyAddDescriptor(Handle<Map> map,
                                    Descriptor* descriptor,
                                    TransitionFlag flag) {
   Handle<DescriptorArray> descriptors(map->instance_descriptors());
 
   // Ensure the key is unique.
   descriptor->KeyToUniqueName();
 
-  if (flag == INSERT_TRANSITION && map->owns_descriptors() &&
-      TransitionArray::CanHaveMoreTransitions(map)) {
+  if (flag == INSERT_TRANSITION &&
+      map->owns_descriptors() &&
+      map->CanHaveMoreTransitions()) {
     return ShareDescriptor(map, descriptors, descriptor);
   }
 
   int nof = map->NumberOfOwnDescriptors();
   Handle<DescriptorArray> new_descriptors =
       DescriptorArray::CopyUpTo(descriptors, nof, 1);
   new_descriptors->Append(descriptor);
 
   Handle<LayoutDescriptor> new_layout_descriptor =
       FLAG_unbox_double_fields
@@ skipping 143 matching lines @@
 
 
 void Map::RemoveFromCodeCache(Name* name, Code* code, int index) {
   // No GC is supposed to happen between a call to IndexInCodeCache and
   // RemoveFromCodeCache so the code cache must be there.
   DCHECK(!code_cache()->IsFixedArray());
   CodeCache::cast(code_cache())->RemoveByIndex(name, code, index);
 }
 
 
+static void TraverseTransitionTreeInternal(Map* map,
+                                           Map::TraverseCallback callback,
+                                           void* data) {
+  if (map->HasTransitionArray()) {
+    TransitionArray* transitions = map->transitions();
+    if (transitions->HasPrototypeTransitions()) {
+      FixedArray* proto_trans = transitions->GetPrototypeTransitions();
+      Object* num_obj =
+          proto_trans->get(Map::kProtoTransitionNumberOfEntriesOffset);
+      int num = Smi::cast(num_obj)->value();
+      for (int i = 0; i < num; ++i) {
+        int index = Map::kProtoTransitionHeaderSize + i;
+        TraverseTransitionTreeInternal(Map::cast(proto_trans->get(index)),
+                                       callback, data);
+      }
+    }
+    for (int i = 0; i < transitions->number_of_transitions(); ++i) {
+      TraverseTransitionTreeInternal(transitions->GetTarget(i), callback, data);
+    }
+  }
+  callback(map, data);
+}
+
+
+// Traverse the transition tree in postorder.
+void Map::TraverseTransitionTree(TraverseCallback callback, void* data) {
+  // Make sure that we do not allocate in the callback.
+  DisallowHeapAllocation no_allocation;
+  TraverseTransitionTreeInternal(this, callback, data);
+}
+
+
 void CodeCache::Update(
     Handle<CodeCache> code_cache, Handle<Name> name, Handle<Code> code) {
   // The number of monomorphic stubs for normal load/store/call IC's can grow to
   // a large number and therefore they need to go into a hash table. They are
   // used to load global properties from cells.
   if (code->type() == Code::NORMAL) {
     // Make sure that a hash table is allocated for the normal load code cache.
     if (code_cache->normal_type_cache()->IsUndefined()) {
       Handle<Object> result =
           CodeCacheHashTable::New(code_cache->GetIsolate(),
@@ skipping 2153 matching lines @@
 
 
 void JSFunction::CompleteInobjectSlackTracking() {
   DCHECK(has_initial_map());
   Map* map = initial_map();
 
   DCHECK(map->counter() >= Map::kSlackTrackingCounterEnd - 1);
   map->set_counter(Map::kRetainingCounterStart);
 
   int slack = map->unused_property_fields();
-  TransitionArray::TraverseTransitionTree(map, &GetMinInobjectSlack, &slack);
+  map->TraverseTransitionTree(&GetMinInobjectSlack, &slack);
   if (slack != 0) {
     // Resize the initial map and all maps in its transition tree.
-    TransitionArray::TraverseTransitionTree(map, &ShrinkInstanceSize, &slack);
+    map->TraverseTransitionTree(&ShrinkInstanceSize, &slack);
   }
 }
 
 
 static bool PrototypeBenefitsFromNormalization(Handle<JSObject> object) {
   DisallowHeapAllocation no_gc;
   if (!object->HasFastProperties()) return false;
   Map* map = object->map();
   if (map->is_prototype_map()) return false;
   DescriptorArray* descriptors = map->instance_descriptors();
@@ skipping 132 matching lines @@
       kElementsKindCount, TENURED);
 
   Handle<Map> current_map = initial_map;
   ElementsKind kind = current_map->elements_kind();
   DCHECK(kind == GetInitialFastElementsKind());
   maps->set(kind, *current_map);
   for (int i = GetSequenceIndexFromFastElementsKind(kind) + 1;
        i < kFastElementsKindCount; ++i) {
     Handle<Map> new_map;
     ElementsKind next_kind = GetFastElementsKindFromSequenceIndex(i);
-    Map* maybe_elements_transition = current_map->ElementsTransitionMap();
-    if (maybe_elements_transition != NULL) {
-      new_map = handle(maybe_elements_transition);
+    if (current_map->HasElementsTransition()) {
+      new_map = handle(current_map->elements_transition_map());
       DCHECK(new_map->elements_kind() == next_kind);
     } else {
       new_map = Map::CopyAsElementsKind(
           current_map, next_kind, INSERT_TRANSITION);
     }
     maps->set(next_kind, *new_map);
     current_map = new_map;
   }
   native_context->set_js_array_maps(*maps);
   return initial_map;
@@ skipping 1900 matching lines @@
         Object);
   }
 
   RETURN_ON_EXCEPTION(
       isolate, EnqueueSpliceRecord(array, index, deleted, add_count), Object);
 
   return hresult;
 }
 
 
+Handle<Map> Map::GetPrototypeTransition(Handle<Map> map,
+                                        Handle<Object> prototype) {
+  DisallowHeapAllocation no_gc;
+  FixedArray* cache = map->GetPrototypeTransitions();
+  int number_of_transitions = map->NumberOfProtoTransitions();
+  for (int i = 0; i < number_of_transitions; i++) {
+    Map* map = Map::cast(cache->get(kProtoTransitionHeaderSize + i));
+    if (map->prototype() == *prototype) return handle(map);
+  }
+  return Handle<Map>();
+}
+
+
+Handle<Map> Map::PutPrototypeTransition(Handle<Map> map,
+                                        Handle<Object> prototype,
+                                        Handle<Map> target_map) {
+  DCHECK(target_map->IsMap());
+  DCHECK(HeapObject::cast(*prototype)->map()->IsMap());
+  // Don't cache prototype transition if this map is either shared, or a map of
+  // a prototype.
+  if (map->is_prototype_map()) return map;
+  if (map->is_dictionary_map() || !FLAG_cache_prototype_transitions) return map;
+
+  const int header = kProtoTransitionHeaderSize;
+
+  Handle<FixedArray> cache(map->GetPrototypeTransitions());
+  int capacity = cache->length() - header;
+  int transitions = map->NumberOfProtoTransitions() + 1;
+
+  if (transitions > capacity) {
+    // Grow array by factor 2 up to MaxCachedPrototypeTransitions.
+    int new_capacity = Min(kMaxCachedPrototypeTransitions, transitions * 2);
+    if (new_capacity == capacity) return map;
+
+    cache = FixedArray::CopySize(cache, header + new_capacity);
+
+    SetPrototypeTransitions(map, cache);
+  }
+
+  // Reload number of transitions as GC might shrink them.
+  int last = map->NumberOfProtoTransitions();
+  int entry = header + last;
+
+  cache->set(entry, *target_map);
+  map->SetNumberOfProtoTransitions(last + 1);
+
+  return map;
+}
+
+
+void Map::ZapTransitions() {
+  TransitionArray* transition_array = transitions();
+  // TODO(mstarzinger): Temporarily use a slower version instead of the faster
+  // MemsetPointer to investigate a crasher. Switch back to MemsetPointer.
+  Object** data = transition_array->data_start();
+  Object* the_hole = GetHeap()->the_hole_value();
+  int length = transition_array->length();
+  for (int i = 0; i < length; i++) {
+    data[i] = the_hole;
+  }
+}
+
+
+void Map::ZapPrototypeTransitions() {
+  FixedArray* proto_transitions = GetPrototypeTransitions();
+  MemsetPointer(proto_transitions->data_start(),
+                GetHeap()->the_hole_value(),
+                proto_transitions->length());
+}
+
+
 // static
 void Map::AddDependentCompilationInfo(Handle<Map> map,
                                       DependentCode::DependencyGroup group,
                                       CompilationInfo* info) {
   Handle<DependentCode> codes = DependentCode::InsertCompilationInfo(
       handle(map->dependent_code(), info->isolate()), group,
       info->object_wrapper());
   if (*codes != map->dependent_code()) map->set_dependent_code(*codes);
   info->dependencies(group)->Add(map, info->zone());
 }
@@ skipping 285 matching lines @@
       return "allocation-site-transition-changed";
   }
   UNREACHABLE();
   return "?";
 }
 
 
 Handle<Map> Map::TransitionToPrototype(Handle<Map> map,
                                        Handle<Object> prototype,
                                        PrototypeOptimizationMode mode) {
-  Handle<Map> new_map = TransitionArray::GetPrototypeTransition(map, prototype);
+  Handle<Map> new_map = GetPrototypeTransition(map, prototype);
   if (new_map.is_null()) {
     new_map = Copy(map, "TransitionToPrototype");
-    TransitionArray::PutPrototypeTransition(map, prototype, new_map);
+    PutPrototypeTransition(map, prototype, new_map);
     new_map->SetPrototype(prototype, mode);
   }
   return new_map;
 }
 
 
 MaybeHandle<Object> JSObject::SetPrototype(Handle<JSObject> object,
                                            Handle<Object> value,
                                            bool from_javascript) {
 #ifdef DEBUG
@@ skipping 4803 matching lines @@
                                                CompilationInfo* info) {
   Handle<DependentCode> codes = DependentCode::InsertCompilationInfo(
       handle(cell->dependent_code(), info->isolate()),
       DependentCode::kPropertyCellChangedGroup, info->object_wrapper());
   if (*codes != cell->dependent_code()) cell->set_dependent_code(*codes);
   info->dependencies(DependentCode::kPropertyCellChangedGroup)->Add(
       cell, info->zone());
 }
 
 } }  // namespace v8::internal