Implement core support for FixedDoubleArrays.

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 40 matching lines @@
 #endif
 
 namespace v8 {
 namespace internal {
 
 // Getters and setters are stored in a fixed array property.  These are
 // constants for their indices.
 const int kGetterIndex = 0;
 const int kSetterIndex = 1;
 
+uint64_t FixedDoubleArray::kHoleNanInt64 = -1;
+uint64_t FixedDoubleArray:: kCanonoicalNonHoleNanLower32 = 0x7FF00000;

[Mads Ager (chromium), 2011/06/06 07:58:23]

remove space after '::'

Can't you use the V8_UINT64_C macro to avoid the lower32 and shifts here?

[danno, 2011/06/08 12:09:43]

This macro only works with x64 builds. It reports that the int is too long on
ia32 builds. :-(

+uint64_t FixedDoubleArray::kCanonoicalNonHoleNanInt64 =
+    kCanonoicalNonHoleNanLower32 << 32;
 
 MUST_USE_RESULT static MaybeObject* CreateJSValue(JSFunction* constructor,
                                                   Object* value) {
   Object* result;
   { MaybeObject* maybe_result =
         constructor->GetHeap()->AllocateJSObject(constructor);
     if (!maybe_result->ToObject(&result)) return maybe_result;
   }
   JSValue::cast(result)->set_value(value);
   return result;
@@ skipping 2955 matching lines @@
     }
     return DeleteElementWithInterceptor(index);
   }
 
   switch (GetElementsKind()) {
     case FAST_ELEMENTS: {
       Object* obj;
       { MaybeObject* maybe_obj = EnsureWritableFastElements();
         if (!maybe_obj->ToObject(&obj)) return maybe_obj;
       }
-      uint32_t length = IsJSArray() ?
-      static_cast<uint32_t>(Smi::cast(JSArray::cast(this)->length())->value()) :
-      static_cast<uint32_t>(FixedArray::cast(elements())->length());
-      if (index < length) {
+      int length = IsJSArray()
+          ? Smi::cast(JSArray::cast(this)->length())->value()
+          : FixedArray::cast(elements())->length();
+      if (index < static_cast<uint32_t>(length)) {
         FixedArray::cast(elements())->set_the_hole(index);
       }
       break;
     }
+    case FAST_DOUBLE_ELEMENTS: {
+      int length = IsJSArray()
+          ? Smi::cast(JSArray::cast(this)->length())->value()
+          : FixedArray::cast(elements())->length();
+      if (index < static_cast<uint32_t>(length)) {
+        FixedDoubleArray::cast(elements())->set_the_hole(index);
+      }
+      break;
+    }
     case EXTERNAL_PIXEL_ELEMENTS:
     case EXTERNAL_BYTE_ELEMENTS:
     case EXTERNAL_UNSIGNED_BYTE_ELEMENTS:
     case EXTERNAL_SHORT_ELEMENTS:
     case EXTERNAL_UNSIGNED_SHORT_ELEMENTS:
     case EXTERNAL_INT_ELEMENTS:
     case EXTERNAL_UNSIGNED_INT_ELEMENTS:
     case EXTERNAL_FLOAT_ELEMENTS:
     case EXTERNAL_DOUBLE_ELEMENTS:
       // Pixel and external array elements cannot be deleted. Just
@@ skipping 3848 matching lines @@
   { MaybeObject* maybe_obj = heap->AllocateFixedArrayWithHoles(capacity);
     if (!maybe_obj->ToObject(&obj)) return maybe_obj;
   }
   FixedArray* elems = FixedArray::cast(obj);
 
   { MaybeObject* maybe_obj = map()->GetFastElementsMap();
     if (!maybe_obj->ToObject(&obj)) return maybe_obj;
   }
   Map* new_map = Map::cast(obj);
 
-  AssertNoAllocation no_gc;
-  WriteBarrierMode mode = elems->GetWriteBarrierMode(no_gc);
   switch (GetElementsKind()) {
     case FAST_ELEMENTS: {
+      AssertNoAllocation no_gc;
+      WriteBarrierMode mode = elems->GetWriteBarrierMode(no_gc);
       FixedArray* old_elements = FixedArray::cast(elements());
       uint32_t old_length = static_cast<uint32_t>(old_elements->length());
       // Fill out the new array with this content and array holes.
       for (uint32_t i = 0; i < old_length; i++) {
         elems->set(i, old_elements->get(i), mode);
       }
       break;
     }
+    case FAST_DOUBLE_ELEMENTS: {
+      FixedDoubleArray* old_elements = FixedDoubleArray::cast(elements());
+      uint32_t old_length = static_cast<uint32_t>(old_elements->length());
+      // Fill out the new array with this content and array holes.
+      for (uint32_t i = 0; i < old_length; i++) {
+        if (!old_elements->is_the_hole(i)) {
+          Object* obj;
+          // Objects must be allocated in the old object space, since the
+          // overall number of HeapNumbers needed for the conversion might
+          // exceed the capacity of new space, and we would fail repeatedly
+          // trying to convert the FixedDoubleArray.
+          MaybeObject* maybe_value_object =
+              GetHeap()->AllocateHeapNumber(old_elements->get(i), TENURED);
+          if (!maybe_value_object->ToObject(&obj)) return maybe_value_object;
+          elems->set(i, obj, UPDATE_WRITE_BARRIER);

[Mads Ager (chromium), 2011/06/06 07:58:23]

Why not use the WriteBarrierMode of the new elements backing store here? If the
new elements are in new space you do not need to update the write barrier. You
do not allow the allocations here to cause GC, so the elments cannot be moved
out of new space while you are in this method.

[danno, 2011/06/08 12:09:43]

It doesn't really make sense to use GetWriteBarrierMode here, because it needs
an AssertNoAllocation object, which would have to e inside the loop after the
allocation anyway, so it doesn't save any write barrier operations. We could
also test elems for presence in NewSpace explicitly to avoid the write barrier
explicitly, but that seems like a case of premature optimization without hard
evidence that it's a bottleneck.

+        }
+      }
+      break;
+    }
     case DICTIONARY_ELEMENTS: {
+      AssertNoAllocation no_gc;
+      WriteBarrierMode mode = elems->GetWriteBarrierMode(no_gc);
       NumberDictionary* dictionary = NumberDictionary::cast(elements());
       for (int i = 0; i < dictionary->Capacity(); i++) {
         Object* key = dictionary->KeyAt(i);
         if (key->IsNumber()) {
           uint32_t entry = static_cast<uint32_t>(key->Number());
           elems->set(entry, dictionary->ValueAt(i), mode);
         }
       }
       break;
     }
     default:
       UNREACHABLE();
       break;
   }
 
   set_map(new_map);
   set_elements(elems);
 
   if (IsJSArray()) {
     JSArray::cast(this)->set_length(Smi::FromInt(length));
   }
 
   return this;
 }
 
 
+MaybeObject* JSObject::SetFastDoubleElementsCapacityAndLength(
+    int capacity,
+    int length) {
+  Heap* heap = GetHeap();
+  // We should never end in here with a pixel or external array.
+  ASSERT(!HasExternalArrayElements());
+
+  Object* obj;
+  { MaybeObject* maybe_obj = heap->AllocateFixedDoubleArray(capacity);
+    if (!maybe_obj->ToObject(&obj)) return maybe_obj;
+  }
+  FixedDoubleArray* elems = FixedDoubleArray::cast(obj);
+
+  { MaybeObject* maybe_obj = map()->GetFastDoubleElementsMap();
+    if (!maybe_obj->ToObject(&obj)) return maybe_obj;
+  }
+  Map* new_map = Map::cast(obj);
+
+  AssertNoAllocation no_gc;
+  switch (GetElementsKind()) {
+    case FAST_ELEMENTS: {
+      FixedArray* old_elements = FixedArray::cast(elements());
+      elems->Initialize(old_elements);
+      break;
+    }
+    case FAST_DOUBLE_ELEMENTS: {
+      FixedDoubleArray* old_elements = FixedDoubleArray::cast(elements());
+      elems->Initialize(old_elements);
+      break;
+    }
+    case DICTIONARY_ELEMENTS: {
+      NumberDictionary* dictionary = NumberDictionary::cast(elements());
+      elems->Initialize(dictionary);
+      break;
+    }
+    default:
+      UNREACHABLE();
+      break;
+  }
+
+  set_map(new_map);
+  set_elements(elems);
+
+  if (IsJSArray()) {
+    JSArray::cast(this)->set_length(Smi::FromInt(length));
+  }
+
+  return this;
+}
+
+
 MaybeObject* JSObject::SetSlowElements(Object* len) {
   // We should never end in here with a pixel or external array.
   ASSERT(!HasExternalArrayElements());
 
   uint32_t new_length = static_cast<uint32_t>(len->Number());
 
   switch (GetElementsKind()) {
     case FAST_ELEMENTS: {
       // Make sure we never try to shrink dense arrays into sparse arrays.
       ASSERT(static_cast<uint32_t>(FixedArray::cast(elements())->length()) <=
@@ skipping 680 matching lines @@
   if (check_prototype &&
       (index >= elms_length || elms->get(index)->IsTheHole())) {
     bool found;
     MaybeObject* result = SetElementWithCallbackSetterInPrototypes(index,
                                                                    value,
                                                                    &found,
                                                                    strict_mode);
     if (found) return result;
   }
 
-
   // Check whether there is extra space in fixed array..
   if (index < elms_length) {
     elms->set(index, value);
     if (IsJSArray()) {
       // Update the length of the array if needed.
       uint32_t array_length = 0;
       CHECK(JSArray::cast(this)->length()->ToArrayIndex(&array_length));
       if (index >= array_length) {
         JSArray::cast(this)->set_length(Smi::FromInt(index + 1));
       }
@@ skipping 21 matching lines @@
   // Otherwise default to slow case.
   Object* obj;
   { MaybeObject* maybe_obj = NormalizeElements();
     if (!maybe_obj->ToObject(&obj)) return maybe_obj;
   }
   ASSERT(HasDictionaryElements());
   return SetElement(index, value, strict_mode, check_prototype);
 }
 
 
+MUST_USE_RESULT MaybeObject* JSObject::SetFastDoubleElement(
+    uint32_t index,
+    Object* value,
+    StrictModeFlag strict_mode,
+    bool check_prototype) {
+  ASSERT(HasFastDoubleElements());
+
+  FixedDoubleArray* elms = FixedDoubleArray::cast(elements());
+  uint32_t elms_length = static_cast<uint32_t>(elms->length());
+
+  // If storing to an element that isn't in the array, pass the store request
+  // up the prototype chain before storing in the receiver's elements.
+  if (check_prototype &&
+      (index >= elms_length || elms->is_the_hole(index))) {
+    bool found;
+    MaybeObject* result = SetElementWithCallbackSetterInPrototypes(index,
+                                                                   value,
+                                                                   &found,
+                                                                   strict_mode);
+    if (found) return result;
+  }
+
+  // If the value object is not a heap number, switch to fast elements and try
+  // again.
+  bool value_is_smi = value->IsSmi();
+  if (!value_is_smi &&

[Mads Ager (chromium), 2011/06/06 07:58:23]

if (!value->IsNumber()) which covers IsSmi() and IsHeapNumber().

[danno, 2011/06/08 12:09:43]

Done.

+      (HeapObject::cast(value)->map() !=
+       *(GetIsolate()->factory()->heap_number_map()))) {
+    Object* obj;
+    { MaybeObject* maybe_obj =
+          SetFastElementsCapacityAndLength(elms_length, elms_length);

[Mads Ager (chromium), 2011/06/06 07:58:23]

Should you really pass in elms_length for both here? What if the object is a
JSArray and the fixed array backing store is larger than the length? It seems
that this call would update the array length to be larger than it should be?

[danno, 2011/06/08 12:09:43]

Done.

+      if (!maybe_obj->ToObject(&obj)) return maybe_obj;
+    }
+    return SetFastElement(index, value, strict_mode, check_prototype);
+  }
+
+  double double_value = value_is_smi
+      ? static_cast<double>(Smi::cast(value)->value())
+      : HeapNumber::cast(value)->value();
+
+  // Check whether there is extra space in fixed array..

[Mads Ager (chromium), 2011/06/06 07:58:23]

.. -> .

in the fixed array?

[danno, 2011/06/08 12:09:43]

Done.

+  if (index < elms_length) {
+    elms->set(index, double_value);
+    if (IsJSArray()) {
+      // Update the length of the array if needed.
+      uint32_t array_length = 0;
+      CHECK(JSArray::cast(this)->length()->ToArrayIndex(&array_length));
+      if (index >= array_length) {
+        JSArray::cast(this)->set_length(Smi::FromInt(index + 1));
+      }
+    }
+    return value;
+  }
+
+  // Allow gap in fast case.
+  if ((index - elms_length) < kMaxGap) {
+    // Try allocating extra space.
+    int new_capacity = NewElementsCapacity(index+1);
+    if (new_capacity <= kMaxFastElementsLength ||
+        !ShouldConvertToSlowElements(new_capacity)) {
+      ASSERT(static_cast<uint32_t>(new_capacity) > index);
+      Object* obj;
+      { MaybeObject* maybe_obj =
+            SetFastDoubleElementsCapacityAndLength(new_capacity,
+                                                   index + 1);
+        if (!maybe_obj->ToObject(&obj)) return maybe_obj;
+      }
+      FixedDoubleArray::cast(elements())->set(index, double_value);
+      return value;
+    }
+  }
+
+  // Otherwise default to slow case.
+  Object* obj;
+  { MaybeObject* maybe_obj = NormalizeElements();
+    if (!maybe_obj->ToObject(&obj)) return maybe_obj;
+  }
+  ASSERT(HasDictionaryElements());
+  return SetElement(index, value, strict_mode, check_prototype);
+}
+
+
 MaybeObject* JSObject::SetElement(uint32_t index,
                                   Object* value,
                                   StrictModeFlag strict_mode,
                                   bool check_prototype) {
   // Check access rights if needed.
   if (IsAccessCheckNeeded()) {
     Heap* heap = GetHeap();
     if (!heap->isolate()->MayIndexedAccess(this, index, v8::ACCESS_SET)) {
       HandleScope scope;
       Handle<Object> value_handle(value);
@@ skipping 29 matching lines @@
 
 MaybeObject* JSObject::SetElementWithoutInterceptor(uint32_t index,
                                                     Object* value,
                                                     StrictModeFlag strict_mode,
                                                     bool check_prototype) {
   Isolate* isolate = GetIsolate();
   switch (GetElementsKind()) {
     case FAST_ELEMENTS:
       // Fast case.
       return SetFastElement(index, value, strict_mode, check_prototype);
+    case FAST_DOUBLE_ELEMENTS:
+      return SetFastDoubleElement(index, value, strict_mode, check_prototype);
     case EXTERNAL_PIXEL_ELEMENTS: {
       ExternalPixelArray* pixels = ExternalPixelArray::cast(elements());
       return pixels->SetValue(index, value);
     }
     case EXTERNAL_BYTE_ELEMENTS: {
       ExternalByteArray* array = ExternalByteArray::cast(elements());
       return array->SetValue(index, value);
     }
     case EXTERNAL_UNSIGNED_BYTE_ELEMENTS: {
       ExternalUnsignedByteArray* array =
@@ skipping 103 matching lines @@
       }
 
       // Attempt to put this object back in fast case.
       if (ShouldConvertToFastElements()) {
         uint32_t new_length = 0;
         if (IsJSArray()) {
           CHECK(JSArray::cast(this)->length()->ToArrayIndex(&new_length));
         } else {
           new_length = NumberDictionary::cast(elements())->max_number_key() + 1;
         }
-        Object* obj;
-        { MaybeObject* maybe_obj =
-              SetFastElementsCapacityAndLength(new_length, new_length);
-          if (!maybe_obj->ToObject(&obj)) return maybe_obj;
+        if (ShouldConvertToFastDoubleElements()) {
+          Object* obj;
+          { MaybeObject* maybe_obj =
+                SetFastDoubleElementsCapacityAndLength(new_length, new_length);
+            if (!maybe_obj->ToObject(&obj)) return maybe_obj;
+          }
+#ifdef DEBUG
+          if (FLAG_trace_normalization) {
+            PrintF("Object elements are fast double case again:\n");
+            Print();
+          }
+#endif
+        } else {
+          Object* obj;
+          { MaybeObject* maybe_obj =
+                SetFastElementsCapacityAndLength(new_length, new_length);
+            if (!maybe_obj->ToObject(&obj)) return maybe_obj;
+          }
+#ifdef DEBUG
+          if (FLAG_trace_normalization) {
+            PrintF("Object elements are fast case again:\n");
+            Print();
+          }
+#endif
         }
-#ifdef DEBUG
-        if (FLAG_trace_normalization) {
-          PrintF("Object elements are fast case again:\n");
-          Print();
-        }
-#endif
       }
 
       return value;
     }
-    default:
-      UNREACHABLE();
-      break;
   }
   // All possible cases have been handled above. Add a return to avoid the
   // complaints from the compiler.
   UNREACHABLE();
   return isolate->heap()->null_value();
 }
 
 
 MaybeObject* JSArray::JSArrayUpdateLengthFromIndex(uint32_t index,
                                                    Object* value) {
@@ skipping 122 matching lines @@
   // JSArray::length cannot change.
   switch (GetElementsKind()) {
     case FAST_ELEMENTS: {
       FixedArray* elms = FixedArray::cast(elements());
       if (index < static_cast<uint32_t>(elms->length())) {
         Object* value = elms->get(index);
         if (!value->IsTheHole()) return value;
       }
       break;
     }
+    case FAST_DOUBLE_ELEMENTS: {
+      FixedDoubleArray* elms = FixedDoubleArray::cast(elements());
+      if (index < static_cast<uint32_t>(elms->length())) {
+        if (!elms->is_the_hole(index)) {
+          double double_value = elms->get(index);
+          return GetHeap()->AllocateHeapNumber(double_value);
+        }
+      }
+      break;
+    }
     case EXTERNAL_PIXEL_ELEMENTS:
     case EXTERNAL_BYTE_ELEMENTS:
     case EXTERNAL_UNSIGNED_BYTE_ELEMENTS:
     case EXTERNAL_SHORT_ELEMENTS:
     case EXTERNAL_UNSIGNED_SHORT_ELEMENTS:
     case EXTERNAL_INT_ELEMENTS:
     case EXTERNAL_UNSIGNED_INT_ELEMENTS:
     case EXTERNAL_FLOAT_ELEMENTS:
     case EXTERNAL_DOUBLE_ELEMENTS: {
       MaybeObject* maybe_value = GetExternalElement(index);
@@ skipping 99 matching lines @@
       break;
     }
     case EXTERNAL_DOUBLE_ELEMENTS: {
       ExternalDoubleArray* array = ExternalDoubleArray::cast(elements());
       if (index < static_cast<uint32_t>(array->length())) {
         double value = array->get(index);
         return GetHeap()->AllocateHeapNumber(value);
       }
       break;
     }
+    case FAST_DOUBLE_ELEMENTS:
     case FAST_ELEMENTS:
     case DICTIONARY_ELEMENTS:
       UNREACHABLE();
       break;
   }
   return GetHeap()->undefined_value();
 }
 
 
 bool JSObject::HasDenseElements() {
@@ skipping 64 matching lines @@
   if (IsJSArray()) {
     CHECK(JSArray::cast(this)->length()->ToArrayIndex(&length));
   } else {
     length = dictionary->max_number_key();
   }
   return static_cast<uint32_t>(dictionary->Capacity()) >=
       (length / (2 * NumberDictionary::kEntrySize));
 }
 
 
+bool JSObject::ShouldConvertToFastDoubleElements() {
+  if (FLAG_unbox_double_arrays) {
+    ASSERT(HasDictionaryElements());
+    NumberDictionary* dictionary = NumberDictionary::cast(elements());
+    for (int i = 0; i < dictionary->Capacity(); i++) {
+      Object* key = dictionary->KeyAt(i);
+      if (key->IsNumber()) {
+        if (!dictionary->ValueAt(i)->IsNumber()) return false;
+      }
+    }
+    return true;
+  } else {
+    return false;
+  }
+}
+
+
 // Certain compilers request function template instantiation when they
 // see the definition of the other template functions in the
 // class. This requires us to have the template functions put
 // together, so even though this function belongs in objects-debug.cc,
 // we keep it here instead to satisfy certain compilers.
 #ifdef OBJECT_PRINT
 template<typename Shape, typename Key>
 void Dictionary<Shape, Key>::Print(FILE* out) {
   int capacity = HashTable<Shape, Key>::Capacity();
   for (int i = 0; i < capacity; i++) {
@@ skipping 2506 matching lines @@
   if (break_point_objects()->IsUndefined()) return 0;
   // Single beak point.
   if (!break_point_objects()->IsFixedArray()) return 1;
   // Multiple break points.
   return FixedArray::cast(break_point_objects())->length();
 }
 #endif
 
 
 } }  // namespace v8::internal