Promoting elements transitions to their own field.

src/objects-inl.h

 // Copyright 2012 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 1853 matching lines @@
 }
 
 
 Object** FixedArray::data_start() {
   return HeapObject::RawField(this, kHeaderSize);
 }
 
 
 bool DescriptorArray::IsEmpty() {
   ASSERT(this->IsSmi() ||
-         this->length() > kFirstIndex ||
+         this->MayContainTransitions() ||
          this == HEAP->empty_descriptor_array());
-  return this->IsSmi() || length() <= kFirstIndex;
+  return this->IsSmi() || length() < kFirstIndex;
 }
 
 
+bool DescriptorArray::MayContainTransitions() {
+  return length() >= kTransitionsIndex;
+}
+
+
 int DescriptorArray::bit_field3_storage() {
   Object* storage = READ_FIELD(this, kBitField3StorageOffset);
   return Smi::cast(storage)->value();
 }
 
 void DescriptorArray::set_bit_field3_storage(int value) {
-  ASSERT(!IsEmpty());
+  ASSERT(this->MayContainTransitions());
   WRITE_FIELD(this, kBitField3StorageOffset, Smi::FromInt(value));
 }
 
 
 void DescriptorArray::NoIncrementalWriteBarrierSwap(FixedArray* array,
                                                     int first,
                                                     int second) {
   Object* tmp = array->get(first);
   NoIncrementalWriteBarrierSet(array, first, array->get(second));
   NoIncrementalWriteBarrierSet(array, second, tmp);
 }
 
 
 int DescriptorArray::Search(String* name) {
   SLOW_ASSERT(IsSortedNoDuplicates());
 
   // Check for empty descriptor array.
   int nof = number_of_descriptors();
   if (nof == 0) return kNotFound;
 
   // Fast case: do linear search for small arrays.
   const int kMaxElementsForLinearSearch = 8;
   if (StringShape(name).IsSymbol() && nof < kMaxElementsForLinearSearch) {
-    return LinearSearch(name, nof);
+    return LinearSearch(EXPECT_SORTED, name, nof);
   }
 
   // Slow case: perform binary search.
   return BinarySearch(name, 0, nof - 1);
 }
 
 
 int DescriptorArray::SearchWithCache(String* name) {
   int number = GetIsolate()->descriptor_lookup_cache()->Lookup(this, name);
   if (number == DescriptorLookupCache::kAbsent) {
     number = Search(name);
     GetIsolate()->descriptor_lookup_cache()->Update(this, name, number);
   }
   return number;
 }
 
 
+Map* DescriptorArray::elements_transition_map() {
+  if (!this->MayContainTransitions()) {
+    return NULL;
+  }
+  Object* transition_map = get(kTransitionsIndex);
+  if (transition_map == Smi::FromInt(0)) {
+    return NULL;
+  } else {
+    return Map::cast(transition_map);
+  }
+}
+
+
+void DescriptorArray::set_elements_transition_map(
+    Map* transition_map, WriteBarrierMode mode) {
+  ASSERT(this->length() > kTransitionsIndex);
+  Heap* heap = GetHeap();
+  WRITE_FIELD(this, kTransitionsOffset, transition_map);
+  CONDITIONAL_WRITE_BARRIER(
+      heap, this, kTransitionsOffset, transition_map, mode);
+  ASSERT(DescriptorArray::cast(this));
+}
+
+
 Object** DescriptorArray::GetKeySlot(int descriptor_number) {
   ASSERT(descriptor_number < number_of_descriptors());
   return HeapObject::RawField(
       reinterpret_cast<HeapObject*>(this),
       OffsetOfElementAt(ToKeyIndex(descriptor_number)));
 }
 
 
 String* DescriptorArray::GetKey(int descriptor_number) {
   ASSERT(descriptor_number < number_of_descriptors());
@@ skipping 65 matching lines @@
 bool DescriptorArray::IsProperty(int descriptor_number) {
   Entry entry(this, descriptor_number);
   return IsPropertyDescriptor(&entry);
 }
 
 
 bool DescriptorArray::IsTransitionOnly(int descriptor_number) {
   switch (GetType(descriptor_number)) {
     case MAP_TRANSITION:
     case CONSTANT_TRANSITION:
-    case ELEMENTS_TRANSITION:
       return true;
     case CALLBACKS: {
       Object* value = GetValue(descriptor_number);
       if (!value->IsAccessorPair()) return false;
       AccessorPair* accessors = AccessorPair::cast(value);
       return accessors->getter()->IsMap() && accessors->setter()->IsMap();
     }
     case NORMAL:
     case FIELD:
     case CONSTANT_FUNCTION:
@@ skipping 1421 matching lines @@
 Object* Map::GetBackPointer() {
   Object* object = READ_FIELD(this, kPrototypeTransitionsOrBackPointerOffset);
   if (object->IsFixedArray()) {
     return FixedArray::cast(object)->get(kProtoTransitionBackPointerOffset);
   } else {
     return object;
   }
 }
 
 
+Map* Map::elements_transition_map() {
+  return instance_descriptors()->elements_transition_map();
+}
+
+
+void Map::set_elements_transition_map(Map* transitioned_map) {
+  return instance_descriptors()->set_elements_transition_map(transitioned_map);
+}
+
+
 void Map::SetBackPointer(Object* value, WriteBarrierMode mode) {
   Heap* heap = GetHeap();
   ASSERT(instance_type() >= FIRST_JS_RECEIVER_TYPE);
   ASSERT((value->IsUndefined() && GetBackPointer()->IsMap()) ||
          (value->IsMap() && GetBackPointer()->IsUndefined()));
   Object* object = READ_FIELD(this, kPrototypeTransitionsOrBackPointerOffset);
   if (object->IsFixedArray()) {
     FixedArray::cast(object)->set(
         kProtoTransitionBackPointerOffset, value, mode);
   } else {
@@ skipping 577 matching lines @@
         heap->AllocateFixedArrayWithHoles(kElementsKindCount);
     FixedArray* maps;
     if (!maybe_maps->To(&maps)) return maybe_maps;
 
     Map* current_map = initial_map;
     ElementsKind kind = current_map->elements_kind();
     ASSERT(kind == GetInitialFastElementsKind());
     maps->set(kind, current_map);
     for (int i = GetSequenceIndexFromFastElementsKind(kind) + 1;
          i < kFastElementsKindCount; ++i) {
-      ElementsKind transitioned_kind = GetFastElementsKindFromSequenceIndex(i);
-      MaybeObject* maybe_new_map = current_map->CopyDropTransitions();
-      Map* new_map = NULL;
-      if (!maybe_new_map->To<Map>(&new_map)) return maybe_new_map;
-      new_map->set_elements_kind(transitioned_kind);
-      maybe_new_map = current_map->AddElementsTransition(transitioned_kind,
-                                                         new_map);
-      if (maybe_new_map->IsFailure()) return maybe_new_map;
-      maps->set(transitioned_kind, new_map);
+      Map* new_map;
+      ElementsKind next_kind = GetFastElementsKindFromSequenceIndex(i);
+      MaybeObject* maybe_new_map =
+          current_map->CreateNextElementsTransition(next_kind);
+      if (!maybe_new_map->To(&new_map)) return maybe_new_map;
+      maps->set(next_kind, new_map);
       current_map = new_map;
     }
     global_context->set_js_array_maps(maps);
   }
   set_initial_map(initial_map);
   return this;
 }
 
 
 bool JSFunction::has_initial_map() {
@@ skipping 991 matching lines @@
 #undef WRITE_UINT32_FIELD
 #undef READ_SHORT_FIELD
 #undef WRITE_SHORT_FIELD
 #undef READ_BYTE_FIELD
 #undef WRITE_BYTE_FIELD
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_OBJECTS_INL_H_