Support all fast elements kinds in the major array operations.

src/runtime.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 4085 matching lines @@
     } else if (FLAG_smi_only_arrays && args.at<Object>(1)->IsSmi()) {
       // JSObject without a string key. If the key is a Smi, check for a
       // definite out-of-bounds access to elements, which is a strong indicator
       // that subsequent accesses will also call the runtime. Proactively
       // transition elements to FAST_*_ELEMENTS to avoid excessive boxing of
       // doubles for those future calls in the case that the elements would
       // become FAST_DOUBLE_ELEMENTS.
       Handle<JSObject> js_object(args.at<JSObject>(0));
       ElementsKind elements_kind = js_object->GetElementsKind();
       if (IsFastElementsKind(elements_kind) &&
-          !IsFastObjectElementsKind(elements_kind)) {
+          !IsFastSmiOrObjectElementsKind(elements_kind)) {

[danno, 2012/11/13 22:05:12]

Can't you reduce the entire multi-part test above to
IsFastDoubleelementsKind(element_kind)?

[Toon Verwaest, 2012/11/14 11:53:13]

Done. Added ASSERT to easily find the place back when adding more raw
elementskinds.

         FixedArrayBase* elements = js_object->elements();
         if (args.at<Smi>(1)->value() >= elements->length()) {
           if (IsFastHoleyElementsKind(elements_kind)) {
             elements_kind = FAST_HOLEY_ELEMENTS;
           } else {
             elements_kind = FAST_ELEMENTS;
           }
           MaybeObject* maybe_object = TransitionElements(js_object,
                                                          elements_kind,
                                                          isolate);
@@ skipping 5179 matching lines @@
     ASSERT(!fast_elements_);
     Handle<SeededNumberDictionary> dict(
         SeededNumberDictionary::cast(*storage_));
     Handle<SeededNumberDictionary> result =
         isolate_->factory()->DictionaryAtNumberPut(dict, index, elm);
     if (!result.is_identical_to(dict)) {
       // Dictionary needed to grow.
       clear_storage();
       set_storage(*result);
     }
-}
+  }
 
   void increase_index_offset(uint32_t delta) {
     if (JSObject::kMaxElementCount - index_offset_ < delta) {
       index_offset_ = JSObject::kMaxElementCount;
     } else {
       index_offset_ += delta;
     }
   }
 
   Handle<JSArray> ToArray() {
@@ skipping 70 matching lines @@
       // a 32-bit signed integer.
       ASSERT(static_cast<int32_t>(FixedArray::kMaxLength) >= 0);
       int fast_length = static_cast<int>(length);
       Handle<FixedArray> elements(FixedArray::cast(array->elements()));
       for (int i = 0; i < fast_length; i++) {
         if (!elements->get(i)->IsTheHole()) element_count++;
       }
       break;
     }
     case FAST_DOUBLE_ELEMENTS:
-    case FAST_HOLEY_DOUBLE_ELEMENTS:
-      // TODO(1810): Decide if it's worthwhile to implement this.
-      UNREACHABLE();
+    case FAST_HOLEY_DOUBLE_ELEMENTS: {
+      // Fast elements can't have lengths that are not representable by
+      // a 32-bit signed integer.
+      ASSERT(static_cast<int32_t>(FixedDoubleArray::kMaxLength) >= 0);
+      int fast_length = static_cast<int>(length);
+      if (array->elements()->IsFixedArray()) {
+        ASSERT(FixedArray::cast(array->elements())->length() == 0);
+        break;
+      }
+      Handle<FixedDoubleArray> elements(
+          FixedDoubleArray::cast(array->elements()));
+      for (int i = 0; i < fast_length; i++) {
+        if (!elements->is_the_hole(i)) element_count++;
+      }
       break;
+    }
     case DICTIONARY_ELEMENTS: {
       Handle<SeededNumberDictionary> dictionary(
           SeededNumberDictionary::cast(array->elements()));
       int capacity = dictionary->Capacity();
       for (int i = 0; i < capacity; i++) {
         Handle<Object> key(dictionary->KeyAt(i));
         if (dictionary->IsKey(*key)) {
           element_count++;
         }
       }
@@ skipping 222 matching lines @@
           // have the correct receiver.
           element_value = Object::GetElement(receiver, j);
           RETURN_IF_EMPTY_HANDLE_VALUE(isolate, element_value, false);
           visitor->visit(j, element_value);
         }
       }
       break;
     }
     case FAST_HOLEY_DOUBLE_ELEMENTS:
     case FAST_DOUBLE_ELEMENTS: {
-      // TODO(1810): Decide if it's worthwhile to implement this.
-      UNREACHABLE();
+      // Run through the elements FixedArray and use HasElement and GetElement
+      // to check the prototype for missing elements.
+      Handle<FixedDoubleArray> elements(
+          FixedDoubleArray::cast(receiver->elements()));
+      int fast_length = static_cast<int>(length);
+      ASSERT(fast_length <= elements->length());
+      for (int j = 0; j < fast_length; j++) {
+        HandleScope loop_scope(isolate);
+        if (!elements->is_the_hole(j)) {
+          double double_value = elements->get_scalar(j);
+          Handle<Object> element_value =
+              isolate->factory()->NewNumber(double_value);
+          visitor->visit(j, element_value);
+        } else if (receiver->HasElement(j)) {
+          // Call GetElement on receiver, not its prototype, or getters won't
+          // have the correct receiver.
+          Handle<Object> element_value = Object::GetElement(receiver, j);
+          RETURN_IF_EMPTY_HANDLE_VALUE(isolate, element_value, false);
+          visitor->visit(j, element_value);
+        }
+      }
       break;
     }
     case DICTIONARY_ELEMENTS: {
       Handle<SeededNumberDictionary> dict(receiver->element_dictionary());
       List<uint32_t> indices(dict->Capacity() / 2);
       // Collect all indices in the object and the prototypes less
       // than length. This might introduce duplicates in the indices list.
       CollectElementIndices(receiver, length, &indices);
       indices.Sort(&compareUInt32);
       int j = 0;
@@ skipping 82 matching lines @@
   CONVERT_ARG_HANDLE_CHECKED(JSArray, arguments, 0);
   int argument_count = static_cast<int>(arguments->length()->Number());
   RUNTIME_ASSERT(arguments->HasFastObjectElements());
   Handle<FixedArray> elements(FixedArray::cast(arguments->elements()));
 
   // Pass 1: estimate the length and number of elements of the result.
   // The actual length can be larger if any of the arguments have getters
   // that mutate other arguments (but will otherwise be precise).
   // The number of elements is precise if there are no inherited elements.
 
+  ElementsKind kind = FAST_SMI_ELEMENTS;
+
   uint32_t estimate_result_length = 0;
   uint32_t estimate_nof_elements = 0;
-  {
-    for (int i = 0; i < argument_count; i++) {
-      HandleScope loop_scope;
-      Handle<Object> obj(elements->get(i));
-      uint32_t length_estimate;
-      uint32_t element_estimate;
-      if (obj->IsJSArray()) {
-        Handle<JSArray> array(Handle<JSArray>::cast(obj));
-        // TODO(1810): Find out if it's worthwhile to properly support
-        // arbitrary ElementsKinds. For now, pessimistically transition to
-        // FAST_*_ELEMENTS.
-        if (array->HasFastDoubleElements()) {
-          ElementsKind to_kind = FAST_ELEMENTS;
-          if (array->HasFastHoleyElements()) {
-            to_kind = FAST_HOLEY_ELEMENTS;
+  for (int i = 0; i < argument_count; i++) {
+    HandleScope loop_scope;
+    Handle<Object> obj(elements->get(i));
+    uint32_t length_estimate;
+    uint32_t element_estimate;
+    if (obj->IsJSArray()) {
+      Handle<JSArray> array(Handle<JSArray>::cast(obj));
+      length_estimate = static_cast<uint32_t>(array->length()->Number());
+      if (length_estimate != 0) {
+        ElementsKind array_kind =
+            GetPackedElementsKind(array->map()->elements_kind());
+        if (IsMoreGeneralElementsKindTransition(kind, array_kind)) {
+          kind = array_kind;
+        }
+      }
+      element_estimate = EstimateElementCount(array);
+    } else {
+      if (obj->IsHeapObject()) {
+        if (obj->IsNumber()) {
+          if (IsMoreGeneralElementsKindTransition(kind, FAST_DOUBLE_ELEMENTS)) {
+            kind = FAST_DOUBLE_ELEMENTS;
           }
-          array = Handle<JSArray>::cast(
-              JSObject::TransitionElementsKind(array, to_kind));
+        } else if (IsMoreGeneralElementsKindTransition(kind, FAST_ELEMENTS)) {
+          kind = FAST_ELEMENTS;
         }
-        length_estimate =
-            static_cast<uint32_t>(array->length()->Number());
-        element_estimate =
-            EstimateElementCount(array);
-      } else {
-        length_estimate = 1;
-        element_estimate = 1;
       }
-      // Avoid overflows by capping at kMaxElementCount.
-      if (JSObject::kMaxElementCount - estimate_result_length <
-          length_estimate) {
-        estimate_result_length = JSObject::kMaxElementCount;
-      } else {
-        estimate_result_length += length_estimate;
-      }
-      if (JSObject::kMaxElementCount - estimate_nof_elements <
-          element_estimate) {
-        estimate_nof_elements = JSObject::kMaxElementCount;
-      } else {
-        estimate_nof_elements += element_estimate;
-      }
+      length_estimate = 1;
+      element_estimate = 1;
+    }
+    // Avoid overflows by capping at kMaxElementCount.
+    if (JSObject::kMaxElementCount - estimate_result_length <
+        length_estimate) {
+      estimate_result_length = JSObject::kMaxElementCount;
+    } else {
+      estimate_result_length += length_estimate;
+    }
+    if (JSObject::kMaxElementCount - estimate_nof_elements <
+        element_estimate) {
+      estimate_nof_elements = JSObject::kMaxElementCount;
+    } else {
+      estimate_nof_elements += element_estimate;
     }
   }
 
   // If estimated number of elements is more than half of length, a
   // fixed array (fast case) is more time and space-efficient than a
   // dictionary.
   bool fast_case = (estimate_nof_elements * 2) >= estimate_result_length;
 
   Handle<FixedArray> storage;
   if (fast_case) {
-    // The backing storage array must have non-existing elements to
-    // preserve holes across concat operations.
+    if (kind == FAST_DOUBLE_ELEMENTS) {
+      Handle<FixedDoubleArray> double_storage =
+          isolate->factory()->NewFixedDoubleArray(estimate_result_length);
+      int j = 0;
+      bool failure = false;
+      for (int i = 0; i < argument_count; i++) {
+        Handle<Object> obj(elements->get(i));
+        if (obj->IsSmi()) {
+          double_storage->set(j, Smi::cast(*obj)->value());
+          j++;
+        } else if (obj->IsNumber()) {
+          double_storage->set(j, obj->Number());
+          j++;
+        } else {
+          JSArray* array = JSArray::cast(*obj);
+          uint32_t length = static_cast<uint32_t>(array->length()->Number());
+          switch (array->map()->elements_kind()) {
+            case FAST_HOLEY_DOUBLE_ELEMENTS:
+            case FAST_DOUBLE_ELEMENTS: {
+              // Empty fixed array indicates that there are no elements.
+              if (array->elements()->IsFixedArray()) break;
+              FixedDoubleArray* elements =
+                  FixedDoubleArray::cast(array->elements());
+              for (uint32_t i = 0; i < length; i++) {
+                if (elements->is_the_hole(i)) {
+                  failure = true;
+                  break;
+                }
+                double double_value = elements->get_scalar(i);
+                double_storage->set(j, double_value);
+                j++;
+              }
+              break;
+            }
+            case FAST_HOLEY_SMI_ELEMENTS:
+            case FAST_SMI_ELEMENTS: {
+              FixedArray* elements(
+                  FixedArray::cast(array->elements()));
+              for (uint32_t i = 0; i < length; i++) {
+                Object* element = elements->get(i);
+                if (element->IsTheHole()) {
+                  failure = true;
+                  break;
+                }
+                int32_t int_value = Smi::cast(element)->value();
+                double_storage->set(j, int_value);
+                j++;
+              }
+              break;
+            }
+            case FAST_HOLEY_ELEMENTS:
+              ASSERT_EQ(0, length);
+              break;
+            default:
+              UNREACHABLE();
+          }
+        }
+        if (failure) break;
+      }
+      Handle<JSArray> array = isolate->factory()->NewJSArray(0);
+      Smi* length = Smi::FromInt(j);
+      Handle<Map> map;
+      map = isolate->factory()->GetElementsTransitionMap(array, kind);
+      array->set_map(*map);
+      array->set_length(length);
+      array->set_elements(*double_storage);
+      return *array;
+    }
+    // The backing storage array must have non-existing elements to preserve
+    // holes across concat operations.
     storage = isolate->factory()->NewFixedArrayWithHoles(
         estimate_result_length);
   } else {
     // TODO(126): move 25% pre-allocation logic into Dictionary::Allocate
     uint32_t at_least_space_for = estimate_nof_elements +
                                   (estimate_nof_elements >> 2);
     storage = Handle<FixedArray>::cast(
         isolate->factory()->NewSeededNumberDictionary(at_least_space_for));
   }
 
@@ skipping 3506 matching lines @@
     // Handle last resort GC and make sure to allow future allocations
     // to grow the heap without causing GCs (if possible).
     isolate->counters()->gc_last_resort_from_js()->Increment();
     isolate->heap()->CollectAllGarbage(Heap::kNoGCFlags,
                                        "Runtime::PerformGC");
   }
 }
 
 
 } }  // namespace v8::internal