Implement tracking and optimizations of packed arrays

src/objects-inl.h

Index: src/objects-inl.h
diff --git a/src/objects-inl.h b/src/objects-inl.h
index 3aa3942909d86b1edb01ac54f3b87d10eaa27841..e0fa4593957a4966bfe3eda28e8c0104caf2c948 100644
--- a/src/objects-inl.h
+++ b/src/objects-inl.h
@@ -128,18 +128,6 @@ PropertyDetails PropertyDetails::AsDeleted() {
   }
 
 
-bool IsMoreGeneralElementsKindTransition(ElementsKind from_kind,
-                                         ElementsKind to_kind) {
-  if (to_kind == FAST_ELEMENTS) {
-    return from_kind == FAST_SMI_ONLY_ELEMENTS ||
-        from_kind == FAST_DOUBLE_ELEMENTS;
-  } else {
-    return to_kind == FAST_DOUBLE_ELEMENTS &&
-        from_kind == FAST_SMI_ONLY_ELEMENTS;
-  }
-}
-
-
 bool Object::IsFixedArrayBase() {
   return IsFixedArray() || IsFixedDoubleArray();
 }
@@ -1244,35 +1232,26 @@ FixedArrayBase* JSObject::elements() {
   return static_cast<FixedArrayBase*>(array);
 }
 
-void JSObject::ValidateSmiOnlyElements() {
+
+void JSObject::ValidateElements() {
 #if DEBUG
-  if (map()->elements_kind() == FAST_SMI_ONLY_ELEMENTS) {
-    Heap* heap = GetHeap();
-    // Don't use elements, since integrity checks will fail if there
-    // are filler pointers in the array.
-    FixedArray* fixed_array =
-        reinterpret_cast<FixedArray*>(READ_FIELD(this, kElementsOffset));
-    Map* map = fixed_array->map();
-    // Arrays that have been shifted in place can't be verified.
-    if (map != heap->raw_unchecked_one_pointer_filler_map() &&
-        map != heap->raw_unchecked_two_pointer_filler_map() &&
-        map != heap->free_space_map()) {
-      for (int i = 0; i < fixed_array->length(); i++) {
-        Object* current = fixed_array->get(i);
-        ASSERT(current->IsSmi() || current->IsTheHole());
-      }
-    }
+  if (FLAG_enable_slow_asserts) {
+    ElementsAccessor* accessor = GetElementsAccessor();
+    accessor->Validate(this);
   }
 #endif
 }
 
 
 MaybeObject* JSObject::EnsureCanContainHeapObjectElements() {
-#if DEBUG
-  ValidateSmiOnlyElements();
-#endif
-  if ((map()->elements_kind() != FAST_ELEMENTS)) {
-    return TransitionElementsKind(FAST_ELEMENTS);
+  ValidateElements();
+  ElementsKind elements_kind = map()->elements_kind();
+  if (!IsFastObjectElementsKind(elements_kind)) {
+    if (IsFastHoleyElementsKind(elements_kind)) {
+      return TransitionElementsKind(FAST_HOLEY_ELEMENTS);
+    } else {
+      return TransitionElementsKind(FAST_ELEMENTS);
+    }
   }
   return this;
 }
@@ -1284,20 +1263,34 @@ MaybeObject* JSObject::EnsureCanContainElements(Object** objects,
   ElementsKind current_kind = map()->elements_kind();
   ElementsKind target_kind = current_kind;
   ASSERT(mode != ALLOW_COPIED_DOUBLE_ELEMENTS);
-  if (current_kind == FAST_ELEMENTS) return this;
-
+  bool is_holey = IsFastHoleyElementsKind(current_kind);
+  if (current_kind == FAST_HOLEY_ELEMENTS) return this;
   Heap* heap = GetHeap();
   Object* the_hole = heap->the_hole_value();
   Object* heap_number_map = heap->heap_number_map();
   for (uint32_t i = 0; i < count; ++i) {
     Object* current = *objects++;
-    if (!current->IsSmi() && current != the_hole) {
+    if (current == the_hole) {
+      is_holey = true;
+      target_kind = GetHoleyElementsKind(target_kind);
+    } else if (!current->IsSmi()) {
       if (mode == ALLOW_CONVERTED_DOUBLE_ELEMENTS &&
-          HeapObject::cast(current)->map() == heap_number_map) {
-        target_kind = FAST_DOUBLE_ELEMENTS;
+          HeapObject::cast(current)->map() == heap_number_map &&
+          IsFastSmiElementsKind(target_kind)) {
+        if (is_holey) {
+          target_kind = FAST_HOLEY_DOUBLE_ELEMENTS;
+        } else {
+          target_kind = FAST_DOUBLE_ELEMENTS;
+        }
       } else {
-        target_kind = FAST_ELEMENTS;
-        break;
+        if (!current->IsNumber()) {
+          if (is_holey) {
+            target_kind = FAST_HOLEY_ELEMENTS;
+            break;
+          } else {
+            target_kind = FAST_ELEMENTS;
+          }
+        }
       }
     }
   }
@@ -1310,6 +1303,7 @@ MaybeObject* JSObject::EnsureCanContainElements(Object** objects,
 
 
 MaybeObject* JSObject::EnsureCanContainElements(FixedArrayBase* elements,
+                                                uint32_t length,
                                                 EnsureElementsMode mode) {
   if (elements->map() != GetHeap()->fixed_double_array_map()) {
     ASSERT(elements->map() == GetHeap()->fixed_array_map() ||
@@ -1318,11 +1312,19 @@ MaybeObject* JSObject::EnsureCanContainElements(FixedArrayBase* elements,
       mode = DONT_ALLOW_DOUBLE_ELEMENTS;
     }
     Object** objects = FixedArray::cast(elements)->GetFirstElementAddress();
-    return EnsureCanContainElements(objects, elements->length(), mode);
+    return EnsureCanContainElements(objects, length, mode);
   }
 
   ASSERT(mode == ALLOW_COPIED_DOUBLE_ELEMENTS);
-  if (GetElementsKind() == FAST_SMI_ONLY_ELEMENTS) {
+  if (GetElementsKind() == FAST_HOLEY_SMI_ELEMENTS) {
+    return TransitionElementsKind(FAST_HOLEY_DOUBLE_ELEMENTS);
+  } else if (GetElementsKind() == FAST_SMI_ELEMENTS) {
+    FixedDoubleArray* double_array = FixedDoubleArray::cast(elements);
+    for (uint32_t i = 0; i < length; ++i) {
+      if (double_array->is_the_hole(i)) {
+        return TransitionElementsKind(FAST_HOLEY_DOUBLE_ELEMENTS);
+      }
+    }
     return TransitionElementsKind(FAST_DOUBLE_ELEMENTS);
   }
 
@@ -1334,21 +1336,21 @@ MaybeObject* JSObject::GetElementsTransitionMap(Isolate* isolate,
                                                 ElementsKind to_kind) {
   Map* current_map = map();
   ElementsKind from_kind = current_map->elements_kind();
-
   if (from_kind == to_kind) return current_map;
 
   Context* global_context = isolate->context()->global_context();
-  if (current_map == global_context->smi_js_array_map()) {
-    if (to_kind == FAST_ELEMENTS) {
-      return global_context->object_js_array_map();
-    } else {
-      if (to_kind == FAST_DOUBLE_ELEMENTS) {
-        return global_context->double_js_array_map();
-      } else {
-        ASSERT(to_kind == DICTIONARY_ELEMENTS);
+  Object* maybe_array_maps =
+      global_context->js_array_maps();

[Jakob Kummerow, 2012/05/13 21:55:27]

nit: fits on one line

[danno, 2012/05/22 11:05:21]

Done.

+  if (maybe_array_maps->IsFixedArray()) {
+    FixedArray* array_maps = FixedArray::cast(maybe_array_maps);
+    if (array_maps->get(from_kind) == current_map) {
+      Object* maybe_transitioned_map = array_maps->get(to_kind);
+      if (maybe_transitioned_map->IsMap()) {
+        return Map::cast(maybe_transitioned_map);
       }
     }
   }
+
   return GetElementsTransitionMapSlow(to_kind);
 }
 
@@ -1357,9 +1359,6 @@ void JSObject::set_map_and_elements(Map* new_map,
                                     FixedArrayBase* value,
                                     WriteBarrierMode mode) {
   ASSERT(value->HasValidElements());
-#ifdef DEBUG
-  ValidateSmiOnlyElements();
-#endif
   if (new_map != NULL) {
     if (mode == UPDATE_WRITE_BARRIER) {
       set_map(new_map);
@@ -1368,8 +1367,7 @@ void JSObject::set_map_and_elements(Map* new_map,
       set_map_no_write_barrier(new_map);
     }
   }
-  ASSERT((map()->has_fast_elements() ||
-          map()->has_fast_smi_only_elements() ||
+  ASSERT((map()->has_fast_smi_or_object_elements() ||
           (value == GetHeap()->empty_fixed_array())) ==
          (value->map() == GetHeap()->fixed_array_map() ||
           value->map() == GetHeap()->fixed_cow_array_map()));
@@ -1392,8 +1390,7 @@ void JSObject::initialize_properties() {
 
 
 void JSObject::initialize_elements() {
-  ASSERT(map()->has_fast_elements() ||
-         map()->has_fast_smi_only_elements() ||
+  ASSERT(map()->has_fast_smi_or_object_elements() ||
          map()->has_fast_double_elements());
   ASSERT(!GetHeap()->InNewSpace(GetHeap()->empty_fixed_array()));
   WRITE_FIELD(this, kElementsOffset, GetHeap()->empty_fixed_array());
@@ -1402,9 +1399,10 @@ void JSObject::initialize_elements() {
 
 MaybeObject* JSObject::ResetElements() {
   Object* obj;
-  ElementsKind elements_kind = FLAG_smi_only_arrays
-      ? FAST_SMI_ONLY_ELEMENTS
-      : FAST_ELEMENTS;
+  ElementsKind elements_kind = GetInitialFastElementsKind();
+  if (!FLAG_smi_only_arrays) {
+    elements_kind = FastSmiToObjectElementsKind(elements_kind);
+  }
   MaybeObject* maybe_obj = GetElementsTransitionMap(GetIsolate(),
                                                     elements_kind);
   if (!maybe_obj->ToObject(&obj)) return maybe_obj;
@@ -1676,6 +1674,12 @@ Object* FixedArray::get(int index) {
 }
 
 
+bool FixedArray::is_the_hole(int index) {
+  ASSERT(index >= 0 && index < this->length());

[Jakob Kummerow, 2012/05/13 21:55:27]

nit: this ASSERT, while correct, is not necessary, as it's covered by the
"get(index)" call anyway. Feel free to leave it in if you prefer, though.

[danno, 2012/05/22 11:05:21]

Done.

+  return get(index) == GetHeap()->the_hole_value();
+}
+
+
 void FixedArray::set(int index, Smi* value) {
   ASSERT(map() != HEAP->fixed_cow_array_map());
   ASSERT(index >= 0 && index < this->length());
@@ -2857,15 +2861,15 @@ bool Map::has_non_instance_prototype() {
 
 void Map::set_function_with_prototype(bool value) {
   if (value) {
-    set_bit_field2(bit_field2() | (1 << kFunctionWithPrototype));
+    set_bit_field3(bit_field3() | (1 << kFunctionWithPrototype));
   } else {
-    set_bit_field2(bit_field2() & ~(1 << kFunctionWithPrototype));
+    set_bit_field3(bit_field3() & ~(1 << kFunctionWithPrototype));
   }
 }
 
 
 bool Map::function_with_prototype() {
-  return ((1 << kFunctionWithPrototype) & bit_field2()) != 0;
+  return ((1 << kFunctionWithPrototype) & bit_field3()) != 0;
 }
 
 
@@ -3943,27 +3947,32 @@ MaybeObject* JSFunction::set_initial_map_and_cache_transitions(
       global_context->get(Context::ARRAY_FUNCTION_INDEX);
   if (array_function->IsJSFunction() &&
       this == JSFunction::cast(array_function)) {
-    ASSERT(initial_map->elements_kind() == FAST_SMI_ONLY_ELEMENTS);
-
-    MaybeObject* maybe_map = initial_map->CopyDropTransitions();
-    Map* new_double_map = NULL;
-    if (!maybe_map->To<Map>(&new_double_map)) return maybe_map;
-    new_double_map->set_elements_kind(FAST_DOUBLE_ELEMENTS);
-    maybe_map = initial_map->AddElementsTransition(FAST_DOUBLE_ELEMENTS,
-                                                   new_double_map);
-    if (maybe_map->IsFailure()) return maybe_map;
-
-    maybe_map = new_double_map->CopyDropTransitions();
-    Map* new_object_map = NULL;
-    if (!maybe_map->To<Map>(&new_object_map)) return maybe_map;
-    new_object_map->set_elements_kind(FAST_ELEMENTS);
-    maybe_map = new_double_map->AddElementsTransition(FAST_ELEMENTS,
-                                                      new_object_map);
-    if (maybe_map->IsFailure()) return maybe_map;
-
-    global_context->set_smi_js_array_map(initial_map);
-    global_context->set_double_js_array_map(new_double_map);
-    global_context->set_object_js_array_map(new_object_map);
+    // Replace all of the cached initial array maps in the global context with
+    // the appropriate transitioned elements kind maps.
+    Heap* heap = GetHeap();
+    MaybeObject* maybe_maps =
+        heap->AllocateFixedArrayWithHoles(kElementsKindCount);

[Jakob Kummerow, 2012/05/13 21:55:27]

Do you mean kFastElementsKindCount here?

[danno, 2012/05/22 11:05:21]

kElementsKindCount is better here, since it removes the need to implement
special cases when testing against DICTIONARY and other maps. In this array,
they are initialize with holes, so comparisons always fail without having to
gate code elsewhere with IsFastElementKind() checks before looking into the map
array.

+    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);
+      current_map = new_map;
+    }
+    global_context->set_js_array_maps(maps);
   }
   set_initial_map(initial_map);
   return this;
@@ -4299,18 +4308,18 @@ ElementsKind JSObject::GetElementsKind() {
   FixedArrayBase* fixed_array =
       reinterpret_cast<FixedArrayBase*>(READ_FIELD(this, kElementsOffset));
   Map* map = fixed_array->map();
-    ASSERT(((kind == FAST_ELEMENTS || kind == FAST_SMI_ONLY_ELEMENTS) &&
-            (map == GetHeap()->fixed_array_map() ||
-             map == GetHeap()->fixed_cow_array_map())) ||
-           (kind == FAST_DOUBLE_ELEMENTS &&
-            (fixed_array->IsFixedDoubleArray() ||
-            fixed_array == GetHeap()->empty_fixed_array())) ||
-           (kind == DICTIONARY_ELEMENTS &&
+  ASSERT((IsFastSmiOrObjectElementsKind(kind) &&
+          (map == GetHeap()->fixed_array_map() ||
+           map == GetHeap()->fixed_cow_array_map())) ||
+         (IsFastDoubleElementsKind(kind) &&
+          (fixed_array->IsFixedDoubleArray() ||
+           fixed_array == GetHeap()->empty_fixed_array())) ||
+         (kind == DICTIONARY_ELEMENTS &&
             fixed_array->IsFixedArray() &&
-            fixed_array->IsDictionary()) ||
-           (kind > DICTIONARY_ELEMENTS));
-    ASSERT((kind != NON_STRICT_ARGUMENTS_ELEMENTS) ||
-           (elements()->IsFixedArray() && elements()->length() >= 2));
+          fixed_array->IsDictionary()) ||
+         (kind > DICTIONARY_ELEMENTS));
+  ASSERT((kind != NON_STRICT_ARGUMENTS_ELEMENTS) ||
+         (elements()->IsFixedArray() && elements()->length() >= 2));
 #endif
   return kind;
 }
@@ -4321,25 +4330,28 @@ ElementsAccessor* JSObject::GetElementsAccessor() {
 }
 
 
-bool JSObject::HasFastElements() {
-  return GetElementsKind() == FAST_ELEMENTS;
+bool JSObject::HasFastObjectElements() {
+  return IsFastObjectElementsKind(GetElementsKind());
 }
 
 
-bool JSObject::HasFastSmiOnlyElements() {
-  return GetElementsKind() == FAST_SMI_ONLY_ELEMENTS;
+bool JSObject::HasFastSmiElements() {
+  return IsFastSmiElementsKind(GetElementsKind());
 }
 
 
-bool JSObject::HasFastTypeElements() {
-  ElementsKind elements_kind = GetElementsKind();
-  return elements_kind == FAST_SMI_ONLY_ELEMENTS ||
-      elements_kind == FAST_ELEMENTS;
+bool JSObject::HasFastSmiOrObjectElements() {
+  return IsFastSmiOrObjectElementsKind(GetElementsKind());
 }
 
 
 bool JSObject::HasFastDoubleElements() {
-  return GetElementsKind() == FAST_DOUBLE_ELEMENTS;
+  return IsFastDoubleElementsKind(GetElementsKind());
+}
+
+
+bool JSObject::HasFastHoleyElements() {
+  return IsFastHoleyElementsKind(GetElementsKind());
 }
 
 
@@ -4396,7 +4408,7 @@ bool JSObject::HasIndexedInterceptor() {
 
 
 MaybeObject* JSObject::EnsureWritableFastElements() {
-  ASSERT(HasFastTypeElements());
+  ASSERT(HasFastSmiOrObjectElements());
   FixedArray* elems = FixedArray::cast(elements());
   Isolate* isolate = GetIsolate();
   if (elems->map() != isolate->heap()->fixed_cow_array_map()) return elems;
@@ -4754,7 +4766,7 @@ void Map::ClearCodeCache(Heap* heap) {
 
 
 void JSArray::EnsureSize(int required_size) {
-  ASSERT(HasFastTypeElements());
+  ASSERT(HasFastSmiOrObjectElements());
   FixedArray* elts = FixedArray::cast(elements());
   const int kArraySizeThatFitsComfortablyInNewSpace = 128;
   if (elts->length() < required_size) {
@@ -4786,13 +4798,13 @@ bool JSArray::AllowsSetElementsLength() {
 
 MaybeObject* JSArray::SetContent(FixedArrayBase* storage) {
   MaybeObject* maybe_result = EnsureCanContainElements(
-      storage, ALLOW_COPIED_DOUBLE_ELEMENTS);
+      storage, storage->length(), ALLOW_COPIED_DOUBLE_ELEMENTS);
   if (maybe_result->IsFailure()) return maybe_result;
   ASSERT((storage->map() == GetHeap()->fixed_double_array_map() &&
-          GetElementsKind() == FAST_DOUBLE_ELEMENTS) ||
+          IsFastDoubleElementsKind(GetElementsKind())) ||
          ((storage->map() != GetHeap()->fixed_double_array_map()) &&
-          ((GetElementsKind() == FAST_ELEMENTS) ||
-           (GetElementsKind() == FAST_SMI_ONLY_ELEMENTS &&
+          (IsFastObjectElementsKind(GetElementsKind()) ||
+           (IsFastElementsKind(GetElementsKind()) &&

[Jakob Kummerow, 2012/05/13 21:55:27]

Did you mean IsFastSmiElementsKind?

[danno, 2012/05/22 11:05:21]

Done.

             FixedArray::cast(storage)->ContainsOnlySmisOrHoles()))));
   set_elements(storage);
   set_length(Smi::FromInt(storage->length()));