Track elements_kind transitions in KeyedStoreICs.

src/objects.cc

 // Copyright 2011 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 1077 matching lines @@
   if (IsString()) {
     String::cast(this)->StringShortPrint(accumulator);
     return;
   }
   if (IsJSObject()) {
     JSObject::cast(this)->JSObjectShortPrint(accumulator);
     return;
   }
   switch (map()->instance_type()) {
     case MAP_TYPE:
-      accumulator->Add("<Map>");
+      accumulator->Add("<Map(elements=%u)>", Map::cast(this)->elements_kind());
       break;
     case FIXED_ARRAY_TYPE:
       accumulator->Add("<FixedArray[%u]>", FixedArray::cast(this)->length());
       break;
     case BYTE_ARRAY_TYPE:
       accumulator->Add("<ByteArray[%u]>", ByteArray::cast(this)->length());
       break;
     case FREE_SPACE_TYPE:
       accumulator->Add("<FreeSpace[%u]>", FreeSpace::cast(this)->Size());
       break;
@@ skipping 1045 matching lines @@
   int i = 0;
   while (i < array->length()) {
     new_array->set(i, array->get(i));
     ++i;
   }
   new_array->set(i, new_map);
   return new_array;
 }
 
 
-MaybeObject* JSObject::GetElementsTransitionMap(ElementsKind elements_kind) {
+// Returns the contents of |map|'s descriptor array for the given string
+// (which might be NULL). |safe_to_add_transition| is set to false and NULL
+// is returned if adding transitions is not allowed.
+static Object* GetDescriptorContents(Map* map,
+                                     String* sentinel_name,
+                                     bool* safe_to_add_transition) {
+  // Get the cached index for the descriptors lookup, or find and cache it.
+  DescriptorArray* descriptors = map->instance_descriptors();
+  DescriptorLookupCache* cache = map->GetIsolate()->descriptor_lookup_cache();
+  int index = cache->Lookup(descriptors, sentinel_name);
+  if (index == DescriptorLookupCache::kAbsent) {
+    index = descriptors->Search(sentinel_name);
+    cache->Update(descriptors, sentinel_name, index);
+  }
+  // If the transition already exists, return its descriptor.
+  if (index != DescriptorArray::kNotFound) {
+    PropertyDetails details(descriptors->GetDetails(index));
+    if (details.type() == ELEMENTS_TRANSITION) {
+      return descriptors->GetValue(index);
+    } else {
+      *safe_to_add_transition = false;
+    }
+  }
+  return NULL;
+}
+
+
+// Returns the map that |original_map| transitions to if its elements_kind
+// is changed to |elements_kind|, or NULL if no such map is cached yet.
+// |safe_to_add_transitions| is set to false if adding transitions is not
+// allowed.
+static Map* LookupElementsTransitionMap(Map* original_map,
+                                        ElementsKind elements_kind,
+                                        String* sentinel_name,
+                                        bool* safe_to_add_transition) {
+  // Special case: indirect SMI->FAST transition (cf. comment in
+  // AddElementsTransition()).
+  if (original_map->elements_kind() == FAST_SMI_ONLY_ELEMENTS &&
+      elements_kind == FAST_ELEMENTS) {
+    Map* double_map = LookupElementsTransitionMap(
+        original_map,
+        FAST_DOUBLE_ELEMENTS,
+        sentinel_name,
+        safe_to_add_transition);
+    if (double_map == NULL) return double_map;
+    return LookupElementsTransitionMap(double_map,
+                                       FAST_ELEMENTS,
+                                       sentinel_name,
+                                       safe_to_add_transition);
+  }
+  Object* descriptor_contents = GetDescriptorContents(
+      original_map, sentinel_name, safe_to_add_transition);
+  if (descriptor_contents != NULL) {
+    Map* maybe_transition_map =
+        GetElementsTransitionMapFromDescriptor(descriptor_contents,
+                                               elements_kind);
+    ASSERT(maybe_transition_map == NULL || maybe_transition_map->IsMap());
+    return maybe_transition_map;
+  }
+  return NULL;
+}
+
+
+// Adds an entry to |original_map|'s descriptor array for a transition to
+// |transitioned_map| when its elements_kind is changed to |elements_kind|,
+// using |sentinel_name| as key for the entry.
+static MaybeObject* AddElementsTransition(Map* original_map,
+                                          ElementsKind elements_kind,
+                                          Map* transitioned_map,
+                                          String* sentinel_name) {
+  // The map transition graph should be a tree, therefore the transition
+  // from SMI to FAST elements is not done directly, but by going through
+  // DOUBLE elements first.
+  if (original_map->elements_kind() == FAST_SMI_ONLY_ELEMENTS &&
+      elements_kind == FAST_ELEMENTS) {
+    bool safe_to_add = true;
+    Map* double_map = LookupElementsTransitionMap(
+        original_map, FAST_DOUBLE_ELEMENTS, sentinel_name, &safe_to_add);
+    // This method is only called when safe_to_add_transition has been found
+    // to be true earlier.
+    ASSERT(safe_to_add);
+
+    if (double_map == NULL) {
+      MaybeObject* maybe_map = original_map->CopyDropTransitions();
+      if (!maybe_map->To(&double_map)) return maybe_map;
+      double_map->set_elements_kind(FAST_DOUBLE_ELEMENTS);
+      MaybeObject* maybe_double_transition = AddElementsTransition(
+          original_map, FAST_DOUBLE_ELEMENTS, double_map, sentinel_name);
+      if (maybe_double_transition->IsFailure()) return maybe_double_transition;
+    }
+    return AddElementsTransition(
+        double_map, FAST_ELEMENTS, transitioned_map, sentinel_name);
+  }
+
+  DescriptorArray* descriptors = original_map->instance_descriptors();
+  bool safe_to_add_transition = true;
+  Object* descriptor_contents = GetDescriptorContents(
+      original_map, sentinel_name, &safe_to_add_transition);
+  // This method is only called when safe_to_add_transition has been found
+  // to be true earlier.
+  ASSERT(safe_to_add_transition);
+  MaybeObject* maybe_new_contents =
+      AddElementsTransitionMapToDescriptor(descriptor_contents,
+                                           transitioned_map);
+  Object* new_contents;
+  if (!maybe_new_contents->ToObject(&new_contents)) {
+    return maybe_new_contents;
+  }
+
+  ElementsTransitionDescriptor desc(sentinel_name, new_contents);
+  Object* new_descriptors;
+  MaybeObject* maybe_new_descriptors =
+      descriptors->CopyInsert(&desc, KEEP_TRANSITIONS);
+  if (!maybe_new_descriptors->ToObject(&new_descriptors)) {
+    return maybe_new_descriptors;
+  }
+  descriptors = DescriptorArray::cast(new_descriptors);
+  original_map->set_instance_descriptors(descriptors);
+  return original_map;
+}
+
+
+MaybeObject* JSObject::GetElementsTransitionMap(ElementsKind to_kind) {
   Heap* current_heap = GetHeap();
   Map* current_map = map();
-  DescriptorArray* descriptors = current_map->instance_descriptors();
+  ElementsKind from_kind = current_map->elements_kind();
   String* elements_transition_sentinel_name = current_heap->empty_symbol();
 
-  if (current_map->elements_kind() == elements_kind) return current_map;
+  if (from_kind == to_kind) return current_map;
 
   // Only objects with FastProperties can have DescriptorArrays and can track
   // element-related maps. Also don't add descriptors to maps that are shared.
   bool safe_to_add_transition = HasFastProperties() &&
       !current_map->IsUndefined() &&
       !current_map->is_shared();
 
-  // Prevent long chains of DICTIONARY -> FAST_ELEMENTS maps cause by objects
+  // Prevent long chains of DICTIONARY -> FAST_ELEMENTS maps caused by objects
   // with elements that switch back and forth between dictionary and fast
   // element mode.
-  if ((current_map->elements_kind() == DICTIONARY_ELEMENTS &&
-       elements_kind == FAST_ELEMENTS)) {
+  if (from_kind == DICTIONARY_ELEMENTS && to_kind == FAST_ELEMENTS) {
     safe_to_add_transition = false;
   }
 
-  Object* descriptor_contents = NULL;
   if (safe_to_add_transition) {
     // It's only safe to manipulate the descriptor array if it would be
     // safe to add a transition.
-
-    // Check if the elements transition already exists.
-    DescriptorLookupCache* cache =
-        current_heap->isolate()->descriptor_lookup_cache();
-    int index = cache->Lookup(descriptors, elements_transition_sentinel_name);
-    if (index == DescriptorLookupCache::kAbsent) {
-      index = descriptors->Search(elements_transition_sentinel_name);
-      cache->Update(descriptors,
-                    elements_transition_sentinel_name,
-                    index);
-    }
-
-    // If the transition already exists, check the type. If there is a match,
-    // return it.
-    if (index != DescriptorArray::kNotFound) {
-      PropertyDetails details(PropertyDetails(descriptors->GetDetails(index)));
-      if (details.type() == ELEMENTS_TRANSITION) {
-        descriptor_contents = descriptors->GetValue(index);
-        Map* maybe_transition_map =
-            GetElementsTransitionMapFromDescriptor(descriptor_contents,
-                                                   elements_kind);
-        if (maybe_transition_map != NULL) {
-          ASSERT(maybe_transition_map->IsMap());
-          return maybe_transition_map;
-        }
-      } else {
-        safe_to_add_transition = false;
-      }
+    Map* maybe_transition_map = LookupElementsTransitionMap(
+        current_map, to_kind, elements_transition_sentinel_name,
+        &safe_to_add_transition);
+    if (maybe_transition_map != NULL) {
+      return maybe_transition_map;
     }
   }
 
+  Map* new_map = NULL;
+
   // No transition to an existing map for the given ElementsKind. Make a new
   // one.
-  Object* obj;
   { MaybeObject* maybe_map = current_map->CopyDropTransitions();
-    if (!maybe_map->ToObject(&obj)) return maybe_map;
+    if (!maybe_map->To(&new_map)) return maybe_map;
   }
-  Map* new_map = Map::cast(obj);
 
-  new_map->set_elements_kind(elements_kind);
+  new_map->set_elements_kind(to_kind);
 
   // Only remember the map transition if the object's map is NOT equal to the
   // global object_function's map and there is not an already existing
   // non-matching element transition.
   bool allow_map_transition = safe_to_add_transition &&
       (GetIsolate()->context()->global_context()->object_function()->map() !=
        map());
   if (allow_map_transition) {
-    MaybeObject* maybe_new_contents =
-        AddElementsTransitionMapToDescriptor(descriptor_contents, new_map);
-    Object* new_contents;
-    if (!maybe_new_contents->ToObject(&new_contents)) {
-      return maybe_new_contents;
-    }
-
-    ElementsTransitionDescriptor desc(elements_transition_sentinel_name,
-                                      new_contents);
-    Object* new_descriptors;
-    MaybeObject* maybe_new_descriptors = descriptors->CopyInsert(
-        &desc,
-        KEEP_TRANSITIONS);
-    if (!maybe_new_descriptors->ToObject(&new_descriptors)) {
-      return maybe_new_descriptors;
-    }
-    descriptors = DescriptorArray::cast(new_descriptors);
-    current_map->set_instance_descriptors(descriptors);
+    MaybeObject* maybe_transition = AddElementsTransition(
+        current_map, to_kind, new_map, elements_transition_sentinel_name);
+    if (maybe_transition->IsFailure()) return maybe_transition;
   }
-
   return new_map;
 }
 
 
 void JSObject::LocalLookupRealNamedProperty(String* name,
                                             LookupResult* result) {
   if (IsJSGlobalProxy()) {
     Object* proto = GetPrototype();
     if (proto->IsNull()) return result->NotFound();
     ASSERT(proto->IsJSGlobalObject());
@@ skipping 4434 matching lines @@
           contents->set_unchecked(i + 1, NullDescriptorDetails);
           contents->set_null_unchecked(heap, i);
           ASSERT(target->prototype() == this ||
                  target->prototype() == real_prototype);
           // Getter prototype() is read-only, set_prototype() has side effects.
           *RawField(target, Map::kPrototypeOffset) = real_prototype;
         }
       } else {
         ASSERT(object->IsFixedArray());
         ASSERT(details.type() == ELEMENTS_TRANSITION);
-        FixedArray* array = reinterpret_cast<FixedArray*>(contents->get(i));
+        FixedArray* array = reinterpret_cast<FixedArray*>(object);
         bool reachable_map_found = false;
         for (int j = 0; j < array->length(); ++j) {
           Map* target = reinterpret_cast<Map*>(array->get(j));
           ASSERT(target->IsHeapObject());
           MarkBit map_mark = Marking::MarkBitFrom(target);
           if (!map_mark.Get()) {
             ASSERT(target->IsMap());
             array->set_undefined(j);
             ASSERT(target->prototype() == this ||
                    target->prototype() == real_prototype);
             // Getter prototype() is read-only, set_prototype() has side
             // effects.
             *RawField(target, Map::kPrototypeOffset) = real_prototype;
-          } else {
+          } else if (target->IsMap()) {
             reachable_map_found = true;
           }
         }
         // If no map was found, make sure the FixedArray also gets collected.
         if (!reachable_map_found) {
           contents->set_unchecked(i + 1, NullDescriptorDetails);
           contents->set_null_unchecked(heap, i);
         }
       }
     }
@@ skipping 5443 matching lines @@
   if (break_point_objects()->IsUndefined()) return 0;
   // Single break point.
   if (!break_point_objects()->IsFixedArray()) return 1;
   // Multiple break points.
   return FixedArray::cast(break_point_objects())->length();
 }
 #endif
 
 
 } }  // namespace v8::internal