Implement tracking and optimizations of packed arrays

src/builtins.cc

 // 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 182 matching lines @@
 
   JSArray* array;
   if (CalledAsConstructor(isolate)) {
     array = JSArray::cast((*args)[0]);
     // Initialize elements and length in case later allocations fail so that the
     // array object is initialized in a valid state.
     array->set_length(Smi::FromInt(0));
     array->set_elements(heap->empty_fixed_array());
     if (!FLAG_smi_only_arrays) {
       Context* global_context = isolate->context()->global_context();
-      if (array->GetElementsKind() == FAST_SMI_ONLY_ELEMENTS &&
-          !global_context->object_js_array_map()->IsUndefined()) {
-        array->set_map(Map::cast(global_context->object_js_array_map()));
+      if (array->GetElementsKind() == GetInitialFastElementsKind() &&
+          !global_context->js_array_maps()->IsUndefined()) {
+        FixedArray* map_array =
+            FixedArray::cast(global_context->js_array_maps());
+        array->set_map(Map::cast(map_array->
+                                 get(TERMINAL_FAST_ELEMENTS_KIND)));
       }
     }
   } else {
     // Allocate the JS Array
     MaybeObject* maybe_obj = heap->AllocateJSObject(constructor);
     if (!maybe_obj->To(&array)) return maybe_obj;
   }
 
   // Optimize the case where there is one argument and the argument is a
   // small smi.
   if (args->length() == 2) {
     Object* obj = (*args)[1];
     if (obj->IsSmi()) {
       int len = Smi::cast(obj)->value();
       if (len >= 0 && len < JSObject::kInitialMaxFastElementArray) {
         Object* fixed_array;
         { MaybeObject* maybe_obj = heap->AllocateFixedArrayWithHoles(len);
           if (!maybe_obj->ToObject(&fixed_array)) return maybe_obj;
         }
+        ElementsKind elements_kind = array->GetElementsKind();
+        if (!IsFastHoleyElementsKind(elements_kind)) {
+          elements_kind = GetHoleyElementsKind(elements_kind);
+          MaybeObject* maybe_array =
+              array->TransitionElementsKind(elements_kind);
+          if (maybe_array->IsFailure()) return maybe_array;
+        }
         // We do not use SetContent to skip the unnecessary elements type check.
         array->set_elements(FixedArray::cast(fixed_array));
         array->set_length(Smi::cast(obj));
         return array;
       }
     }
     // Take the argument as the length.
     { MaybeObject* maybe_obj = array->Initialize(0);
       if (!maybe_obj->ToObject(&obj)) return maybe_obj;
     }
     return array->SetElementsLength((*args)[1]);
   }
 
   // Optimize the case where there are no parameters passed.
   if (args->length() == 1) {
     return array->Initialize(JSArray::kPreallocatedArrayElements);
   }
 
   // Set length and elements on the array.
   int number_of_elements = args->length() - 1;
   MaybeObject* maybe_object =
       array->EnsureCanContainElements(args, 1, number_of_elements,
                                       ALLOW_CONVERTED_DOUBLE_ELEMENTS);
   if (maybe_object->IsFailure()) return maybe_object;
 
   // Allocate an appropriately typed elements array.
   MaybeObject* maybe_elms;
   ElementsKind elements_kind = array->GetElementsKind();
-  if (elements_kind == FAST_DOUBLE_ELEMENTS) {
+  if (IsFastDoubleElementsKind(elements_kind)) {
     maybe_elms = heap->AllocateUninitializedFixedDoubleArray(
         number_of_elements);
   } else {
     maybe_elms = heap->AllocateFixedArrayWithHoles(number_of_elements);
   }
   FixedArrayBase* elms;
   if (!maybe_elms->To<FixedArrayBase>(&elms)) return maybe_elms;
 
   // Fill in the content
   switch (array->GetElementsKind()) {
-    case FAST_SMI_ONLY_ELEMENTS: {
+    case FAST_HOLEY_SMI_ELEMENTS:
+    case FAST_SMI_ELEMENTS: {
       FixedArray* smi_elms = FixedArray::cast(elms);
       for (int index = 0; index < number_of_elements; index++) {
         smi_elms->set(index, (*args)[index+1], SKIP_WRITE_BARRIER);
       }
       break;
     }
+    case FAST_HOLEY_ELEMENTS:
     case FAST_ELEMENTS: {
       AssertNoAllocation no_gc;
       WriteBarrierMode mode = elms->GetWriteBarrierMode(no_gc);
       FixedArray* object_elms = FixedArray::cast(elms);
       for (int index = 0; index < number_of_elements; index++) {
         object_elms->set(index, (*args)[index+1], mode);
       }
       break;
     }
+    case FAST_HOLEY_DOUBLE_ELEMENTS:
     case FAST_DOUBLE_ELEMENTS: {
       FixedDoubleArray* double_elms = FixedDoubleArray::cast(elms);
       for (int index = 0; index < number_of_elements; index++) {
         double_elms->set(index, (*args)[index+1]->Number());
       }
       break;
     }
     default:
       UNREACHABLE();
       break;
@@ skipping 115 matching lines @@
 
 
 MUST_USE_RESULT
 static inline MaybeObject* EnsureJSArrayWithWritableFastElements(
     Heap* heap, Object* receiver, Arguments* args, int first_added_arg) {
   if (!receiver->IsJSArray()) return NULL;
   JSArray* array = JSArray::cast(receiver);
   HeapObject* elms = array->elements();
   Map* map = elms->map();
   if (map == heap->fixed_array_map()) {
-    if (args == NULL || array->HasFastElements()) return elms;
+    if (args == NULL || array->HasFastObjectElements()) return elms;
     if (array->HasFastDoubleElements()) {
       ASSERT(elms == heap->empty_fixed_array());
       MaybeObject* maybe_transition =
           array->TransitionElementsKind(FAST_ELEMENTS);
       if (maybe_transition->IsFailure()) return maybe_transition;
       return elms;
     }
   } else if (map == heap->fixed_cow_array_map()) {
     MaybeObject* maybe_writable_result = array->EnsureWritableFastElements();
-    if (args == NULL || array->HasFastElements() ||
+    if (args == NULL || array->HasFastObjectElements() ||
         maybe_writable_result->IsFailure()) {
       return maybe_writable_result;
     }
   } else {
     return NULL;
   }
 
   // Need to ensure that the arguments passed in args can be contained in
   // the array.
   int args_length = args->length();
@@ skipping 73 matching lines @@
 
   if (new_length > elms->length()) {
     // New backing storage is needed.
     int capacity = new_length + (new_length >> 1) + 16;
     Object* obj;
     { MaybeObject* maybe_obj = heap->AllocateUninitializedFixedArray(capacity);
       if (!maybe_obj->ToObject(&obj)) return maybe_obj;
     }
     FixedArray* new_elms = FixedArray::cast(obj);
 
-    CopyObjectToObjectElements(elms, FAST_ELEMENTS, 0,
-                               new_elms, FAST_ELEMENTS, 0, len);
+    ElementsKind kind = array->GetElementsKind();
+    CopyObjectToObjectElements(elms, kind, 0, new_elms, kind, 0, len);
     FillWithHoles(heap, new_elms, new_length, capacity);
 
     elms = new_elms;
   }
 
   // Add the provided values.
   AssertNoAllocation no_gc;
   WriteBarrierMode mode = elms->GetWriteBarrierMode(no_gc);
   for (int index = 0; index < to_add; index++) {
     elms->set(index + len, args[index + 1], mode);
@@ skipping 50 matching lines @@
         EnsureJSArrayWithWritableFastElements(heap, receiver, NULL, 0);
     if (maybe_elms_obj == NULL)
         return CallJsBuiltin(isolate, "ArrayShift", args);
     if (!maybe_elms_obj->ToObject(&elms_obj)) return maybe_elms_obj;
   }
   if (!IsJSArrayFastElementMovingAllowed(heap, JSArray::cast(receiver))) {
     return CallJsBuiltin(isolate, "ArrayShift", args);
   }
   FixedArray* elms = FixedArray::cast(elms_obj);
   JSArray* array = JSArray::cast(receiver);
-  ASSERT(array->HasFastTypeElements());
+  ASSERT(array->HasFastSmiOrObjectElements());
 
   int len = Smi::cast(array->length())->value();
   if (len == 0) return heap->undefined_value();
 
   // Get first element
   Object* first = elms->get(0);
   if (first->IsTheHole()) {
     first = heap->undefined_value();
   }
 
@@ skipping 21 matching lines @@
         EnsureJSArrayWithWritableFastElements(heap, receiver, NULL, 0);
     if (maybe_elms_obj == NULL)
         return CallJsBuiltin(isolate, "ArrayUnshift", args);
     if (!maybe_elms_obj->ToObject(&elms_obj)) return maybe_elms_obj;
   }
   if (!IsJSArrayFastElementMovingAllowed(heap, JSArray::cast(receiver))) {
     return CallJsBuiltin(isolate, "ArrayUnshift", args);
   }
   FixedArray* elms = FixedArray::cast(elms_obj);
   JSArray* array = JSArray::cast(receiver);
-  ASSERT(array->HasFastTypeElements());
+  ASSERT(array->HasFastSmiOrObjectElements());
 
   int len = Smi::cast(array->length())->value();
   int to_add = args.length() - 1;
   int new_length = len + to_add;
   // Currently fixed arrays cannot grow too big, so
   // we should never hit this case.
   ASSERT(to_add <= (Smi::kMaxValue - len));
 
   MaybeObject* maybe_object =
       array->EnsureCanContainElements(&args, 1, to_add,
                                       DONT_ALLOW_DOUBLE_ELEMENTS);
   if (maybe_object->IsFailure()) return maybe_object;
 
   if (new_length > elms->length()) {
     // New backing storage is needed.
     int capacity = new_length + (new_length >> 1) + 16;
     Object* obj;
     { MaybeObject* maybe_obj = heap->AllocateUninitializedFixedArray(capacity);
       if (!maybe_obj->ToObject(&obj)) return maybe_obj;
     }
     FixedArray* new_elms = FixedArray::cast(obj);
-    CopyObjectToObjectElements(elms, FAST_ELEMENTS, 0,
-                               new_elms, FAST_ELEMENTS, to_add, len);
+    ElementsKind kind = array->GetElementsKind();
+    CopyObjectToObjectElements(elms, kind, 0, new_elms, kind, to_add, len);
     FillWithHoles(heap, new_elms, new_length, capacity);
     elms = new_elms;
     array->set_elements(elms);
   } else {
     AssertNoAllocation no_gc;
     MoveElements(heap, &no_gc, elms, to_add, elms, 0, len);
   }
 
   // Add the provided values.
   AssertNoAllocation no_gc;
   WriteBarrierMode mode = elms->GetWriteBarrierMode(no_gc);
   for (int i = 0; i < to_add; i++) {
     elms->set(i, args[i + 1], mode);
   }
 
   // Set the length.
   array->set_length(Smi::FromInt(new_length));
   return Smi::FromInt(new_length);
 }
 
 
 BUILTIN(ArraySlice) {
   Heap* heap = isolate->heap();
   Object* receiver = *args.receiver();
   FixedArray* elms;
   int len = -1;
   if (receiver->IsJSArray()) {
     JSArray* array = JSArray::cast(receiver);
-    if (!array->HasFastTypeElements() ||
+    if (!array->HasFastSmiOrObjectElements() ||
         !IsJSArrayFastElementMovingAllowed(heap, array)) {
       return CallJsBuiltin(isolate, "ArraySlice", args);
     }
 
     elms = FixedArray::cast(array->elements());
     len = Smi::cast(array->length())->value();
   } else {
     // Array.slice(arguments, ...) is quite a common idiom (notably more
     // than 50% of invocations in Web apps).  Treat it in C++ as well.
     Map* arguments_map =
         isolate->context()->global_context()->arguments_boilerplate()->map();
 
     bool is_arguments_object_with_fast_elements =
         receiver->IsJSObject()
         && JSObject::cast(receiver)->map() == arguments_map
-        && JSObject::cast(receiver)->HasFastTypeElements();
+        && JSObject::cast(receiver)->HasFastSmiOrObjectElements();
     if (!is_arguments_object_with_fast_elements) {
       return CallJsBuiltin(isolate, "ArraySlice", args);
     }
     elms = FixedArray::cast(JSObject::cast(receiver)->elements());
     Object* len_obj = JSObject::cast(receiver)
         ->InObjectPropertyAt(Heap::kArgumentsLengthIndex);
     if (!len_obj->IsSmi()) {
       return CallJsBuiltin(isolate, "ArraySlice", args);
     }
     len = Smi::cast(len_obj)->value();
@@ skipping 44 matching lines @@
   // Calculate the length of result array.
   int result_len = Max(final - k, 0);
 
   MaybeObject* maybe_array =
       heap->AllocateJSArrayAndStorage(elements_kind,
                                       result_len,
                                       result_len);
   JSArray* result_array;
   if (!maybe_array->To(&result_array)) return maybe_array;
 
-  CopyObjectToObjectElements(elms, FAST_ELEMENTS, k,
+  CopyObjectToObjectElements(elms, elements_kind, k,
                              FixedArray::cast(result_array->elements()),
-                             FAST_ELEMENTS, 0, result_len);
+                             elements_kind, 0, result_len);
 
   return result_array;
 }
 
 
 BUILTIN(ArraySplice) {
   Heap* heap = isolate->heap();
   Object* receiver = *args.receiver();
   Object* elms_obj;
   { MaybeObject* maybe_elms_obj =
         EnsureJSArrayWithWritableFastElements(heap, receiver, &args, 3);
     if (maybe_elms_obj == NULL)
         return CallJsBuiltin(isolate, "ArraySplice", args);
     if (!maybe_elms_obj->ToObject(&elms_obj)) return maybe_elms_obj;
   }
   if (!IsJSArrayFastElementMovingAllowed(heap, JSArray::cast(receiver))) {
     return CallJsBuiltin(isolate, "ArraySplice", args);
   }
   FixedArray* elms = FixedArray::cast(elms_obj);
   JSArray* array = JSArray::cast(receiver);
-  ASSERT(array->HasFastTypeElements());
+  ASSERT(array->HasFastSmiOrObjectElements());
 
   int len = Smi::cast(array->length())->value();
 
   int n_arguments = args.length() - 1;
 
   int relative_start = 0;
   if (n_arguments > 0) {
     Object* arg1 = args[1];
     if (arg1->IsSmi()) {
       relative_start = Smi::cast(arg1)->value();
@@ skipping 30 matching lines @@
   ElementsKind elements_kind =
       JSObject::cast(receiver)->GetElementsKind();
   MaybeObject* maybe_array =
       heap->AllocateJSArrayAndStorage(elements_kind,
                                       actual_delete_count,
                                       actual_delete_count);
   if (!maybe_array->To(&result_array)) return maybe_array;
 
   {
     // Fill newly created array.
-    CopyObjectToObjectElements(elms, FAST_ELEMENTS, actual_start,
+    CopyObjectToObjectElements(elms, elements_kind, actual_start,
                                FixedArray::cast(result_array->elements()),
-                               FAST_ELEMENTS, 0, actual_delete_count);
+                               elements_kind, 0, actual_delete_count);
   }
 
   int item_count = (n_arguments > 1) ? (n_arguments - 2) : 0;
   int new_length = len - actual_delete_count + item_count;
 
   bool elms_changed = false;
   if (item_count < actual_delete_count) {
     // Shrink the array.
     const bool trim_array = !heap->lo_space()->Contains(elms) &&
       ((actual_start + item_count) <
@@ skipping 28 matching lines @@
       int capacity = new_length + (new_length >> 1) + 16;
       Object* obj;
       { MaybeObject* maybe_obj =
             heap->AllocateUninitializedFixedArray(capacity);
         if (!maybe_obj->ToObject(&obj)) return maybe_obj;
       }
       FixedArray* new_elms = FixedArray::cast(obj);
 
       {
         // Copy the part before actual_start as is.
-        CopyObjectToObjectElements(elms, FAST_ELEMENTS, 0,
-                                   new_elms, FAST_ELEMENTS, 0, actual_start);
+        ElementsKind kind = array->GetElementsKind();
+        CopyObjectToObjectElements(elms, kind, 0,
+                                   new_elms, kind, 0, actual_start);
         const int to_copy = len - actual_delete_count - actual_start;
-        CopyObjectToObjectElements(elms, FAST_ELEMENTS,
+        CopyObjectToObjectElements(elms, kind,
                                    actual_start + actual_delete_count,
-                                   new_elms, FAST_ELEMENTS,
+                                   new_elms, kind,
                                    actual_start + item_count, to_copy);
       }
 
       FillWithHoles(heap, new_elms, new_length, capacity);
 
       elms = new_elms;
       elms_changed = true;
     } else {
       AssertNoAllocation no_gc;
       MoveElements(heap, &no_gc,
@@ skipping 26 matching lines @@
   JSObject* array_proto =
       JSObject::cast(global_context->array_function()->prototype());
   if (!ArrayPrototypeHasNoElements(heap, global_context, array_proto)) {
     return CallJsBuiltin(isolate, "ArrayConcat", args);
   }
 
   // Iterate through all the arguments performing checks
   // and calculating total length.
   int n_arguments = args.length();
   int result_len = 0;
-  ElementsKind elements_kind = FAST_SMI_ONLY_ELEMENTS;
+  ElementsKind elements_kind = GetInitialFastElementsKind();
   for (int i = 0; i < n_arguments; i++) {
     Object* arg = args[i];
-    if (!arg->IsJSArray() || !JSArray::cast(arg)->HasFastTypeElements()
-        || JSArray::cast(arg)->GetPrototype() != array_proto) {
+    if (!arg->IsJSArray() ||
+        !JSArray::cast(arg)->HasFastSmiOrObjectElements() ||
+        JSArray::cast(arg)->GetPrototype() != array_proto) {
       return CallJsBuiltin(isolate, "ArrayConcat", args);
     }
 
     int len = Smi::cast(JSArray::cast(arg)->length())->value();
 
     // We shouldn't overflow when adding another len.
     const int kHalfOfMaxInt = 1 << (kBitsPerInt - 2);
     STATIC_ASSERT(FixedArray::kMaxLength < kHalfOfMaxInt);
     USE(kHalfOfMaxInt);
     result_len += len;
     ASSERT(result_len >= 0);
 
     if (result_len > FixedArray::kMaxLength) {
       return CallJsBuiltin(isolate, "ArrayConcat", args);
     }
 
-    if (!JSArray::cast(arg)->HasFastSmiOnlyElements()) {
-      elements_kind = FAST_ELEMENTS;
+    if (!JSArray::cast(arg)->HasFastSmiElements()) {
+      if (IsFastSmiElementsKind(elements_kind)) {
+        if (IsFastHoleyElementsKind(elements_kind)) {
+          elements_kind = FAST_HOLEY_ELEMENTS;
+        } else {
+          elements_kind = FAST_ELEMENTS;
+        }
+      }
+    }
+
+    if (JSArray::cast(arg)->HasFastHoleyElements()) {
+      elements_kind = GetHoleyElementsKind(elements_kind);
     }
   }
 
   // Allocate result.
   JSArray* result_array;
   MaybeObject* maybe_array =
       heap->AllocateJSArrayAndStorage(elements_kind,
                                       result_len,
                                       result_len);
   if (!maybe_array->To(&result_array)) return maybe_array;
   if (result_len == 0) return result_array;
 
   // Copy data.
   int start_pos = 0;
   FixedArray* result_elms(FixedArray::cast(result_array->elements()));
   for (int i = 0; i < n_arguments; i++) {
     JSArray* array = JSArray::cast(args[i]);
     int len = Smi::cast(array->length())->value();
     FixedArray* elms = FixedArray::cast(array->elements());
-    CopyObjectToObjectElements(elms, FAST_ELEMENTS, 0,
-                               result_elms, FAST_ELEMENTS,
+    CopyObjectToObjectElements(elms, elements_kind, 0,
+                               result_elms, elements_kind,
                                start_pos, len);
     start_pos += len;
   }
   ASSERT(start_pos == result_len);
 
   return result_array;
 }
 
 
 // -----------------------------------------------------------------------------
@@ skipping 681 matching lines @@
   return Handle<Code>(code_address);                        \
 }
 BUILTIN_LIST_C(DEFINE_BUILTIN_ACCESSOR_C)
 BUILTIN_LIST_A(DEFINE_BUILTIN_ACCESSOR_A)
 BUILTIN_LIST_DEBUG_A(DEFINE_BUILTIN_ACCESSOR_A)
 #undef DEFINE_BUILTIN_ACCESSOR_C
 #undef DEFINE_BUILTIN_ACCESSOR_A
 
 
 } }  // namespace v8::internal