- Restructure the Canonicalization of instances in preparation for adding a

runtime/vm/object.cc

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/object.h"
 
 #include "include/dart_api.h"
 #include "platform/assert.h"
 #include "vm/assembler.h"
 #include "vm/cpu.h"
@@ skipping 4381 matching lines @@
     const Array& new_canonical_list =
         Array::Handle(Array::Grow(canonical_list, new_length, Heap::kOld));
     set_constants(new_canonical_list);
     new_canonical_list.SetAt(index, constant);
   } else {
     canonical_list.SetAt(index, constant);
   }
 }
 
 
+void Class::InsertCanonicalNumber(Zone* zone,
+                                  intptr_t index,
+                                  const Number& constant) const {
+  // The constant needs to be added to the list. Grow the list if it is full.
+  Array& canonical_list = Array::Handle(zone, constants());
+  const intptr_t list_len = canonical_list.Length();
+  if (index >= list_len) {
+    const intptr_t new_length = (list_len == 0) ? 4 : list_len + 4;
+    canonical_list ^= Array::Grow(canonical_list, new_length, Heap::kOld);
+    set_constants(canonical_list);
+  }
+  canonical_list.SetAt(index, constant);
+}
+
+
 RawUnresolvedClass* UnresolvedClass::New(const LibraryPrefix& library_prefix,
                                          const String& ident,
                                          TokenPosition token_pos) {
   const UnresolvedClass& type = UnresolvedClass::Handle(UnresolvedClass::New());
   type.set_library_prefix(library_prefix);
   type.set_ident(ident);
   type.set_token_pos(token_pos);
   return type.raw();
 }
 
@@ skipping 10216 matching lines @@
   }
 
  private:
   bool has_pointers_;
 
   DISALLOW_COPY_AND_ASSIGN(CheckForPointers);
 };
 #endif  // DEBUG
 
 
-bool Instance::CheckAndCanonicalizeFields(const char** error_str) const {
-  const Class& cls = Class::Handle(this->clazz());
+bool Instance::CheckAndCanonicalizeFields(Zone* zone,
+                                          const char** error_str) const {
+  const Class& cls = Class::Handle(zone, this->clazz());
   if (cls.id() >= kNumPredefinedCids) {
     // Iterate over all fields, canonicalize numbers and strings, expect all
     // other instances to be canonical otherwise report error (return false).
-    Object& obj = Object::Handle();
+    Object& obj = Object::Handle(zone);
     intptr_t end_field_offset = cls.instance_size() - kWordSize;
     for (intptr_t field_offset = 0;
          field_offset <= end_field_offset;
          field_offset += kWordSize) {
       obj = *this->FieldAddrAtOffset(field_offset);
       if (obj.IsInstance() && !obj.IsSmi() && !obj.IsCanonical()) {
         if (obj.IsNumber() || obj.IsString()) {
           obj = Instance::Cast(obj).CheckAndCanonicalize(NULL);
           ASSERT(!obj.IsNull());
           this->SetFieldAtOffset(field_offset, obj);
         } else {
           ASSERT(error_str != NULL);
           char* chars = OS::SCreate(Thread::Current()->zone(),

[srdjan, 2016/04/06 22:32:44]

zone

[siva, 2016/04/06 22:35:33]

Done.

               "field: %s\n", obj.ToCString());
           *error_str = chars;
           return false;
         }
       }
     }
   } else {
 #if defined(DEBUG)
     // Make sure that we are not missing any fields.
     CheckForPointers has_pointers(Isolate::Current());
     this->raw()->VisitPointers(&has_pointers);
     ASSERT(!has_pointers.has_pointers());
 #endif  // DEBUG
   }
   return true;
 }
 
 
 RawInstance* Instance::CheckAndCanonicalize(const char** error_str) const {
   ASSERT(!IsNull());
   if (this->IsCanonical()) {
     return this->raw();
   }
-  if (!CheckAndCanonicalizeFields(error_str)) {
+  Thread* thread = Thread::Current();
+  Zone* zone = thread->zone();
+  if (!CheckAndCanonicalizeFields(zone, error_str)) {
     return Instance::null();
   }
-  Thread* thread = Thread::Current();
-  Zone* zone = thread->zone();
   Isolate* isolate = thread->isolate();
   Instance& result = Instance::Handle(zone);
   const Class& cls = Class::Handle(zone, this->clazz());
   intptr_t index = 0;
   result ^= cls.LookupCanonicalInstance(zone, *this, &index);
   if (!result.IsNull()) {
     return result.raw();
   }
   {
     SafepointMutexLocker ml(isolate->constant_canonicalization_mutex());
     // Retry lookup.
     {
-      Instance& temp_result = Instance::Handle(zone,
-          cls.LookupCanonicalInstance(zone, *this, &index));
-      if (!temp_result.IsNull()) {
-        return temp_result.raw();
+      result ^= cls.LookupCanonicalInstance(zone, *this, &index);
+      if (!result.IsNull()) {
+        return result.raw();
       }
     }
 
     // The value needs to be added to the list. Grow the list if
     // it is full.
     result ^= this->raw();
-    if (result.IsNew() ||
-        (result.InVMHeap() && (isolate != Dart::vm_isolate()))) {
-      /**
-       * When a snapshot is generated on a 64 bit architecture and then read
-       * into a 32 bit architecture, values which are Smi on the 64 bit
-       * architecture could potentially be converted to Mint objects, however
-       * since Smi values do not have any notion of canonical bits we lose
-       * that information when the object becomes a Mint.
-       * Some of these values could be literal values and end up in the
-       * VM isolate heap. Later when these values are referenced in a
-       * constant list we try to ensure that all the objects in the list
-       * are canonical and try to canonicalize them. When these Mint objects
-       * are encountered they do not have the canonical bit set and
-       * canonicalizing them won't work as the VM heap is read only now.
-       * In these cases we clone the object into the isolate and then
-       * canonicalize it.
-       */
+    ASSERT((isolate == Dart::vm_isolate()) || !result.InVMHeap());
+    if (result.IsNew()) {
       // Create a canonical object in old space.
       result ^= Object::Clone(result, Heap::kOld);
     }
     ASSERT(result.IsOld());
-
     result.SetCanonical();
     cls.InsertCanonicalConstant(index, result);
     return result.raw();
   }
 }
 
 
 RawAbstractType* Instance::GetType() const {
   if (IsNull()) {
     return Type::NullType();
@@ skipping 191 matching lines @@
   return DartLibraryCalls::Equals(*this, other) == Object::bool_true().raw();
 }
 
 
 bool Instance::IsIdenticalTo(const Instance& other) const {
   if (raw() == other.raw()) return true;
   if (IsInteger() && other.IsInteger()) {
     return Integer::Cast(*this).Equals(other);
   }
   if (IsDouble() && other.IsDouble()) {
-    return Double::Cast(*this).CanonicalizeEquals(other);
+    double other_value = Double::Cast(other).value();
+    return Double::Cast(*this).BitwiseEqualsToDouble(other_value);
   }
   return false;
 }
 
 
 intptr_t* Instance::NativeFieldsDataAddr() const {
   ASSERT(Thread::Current()->no_safepoint_scope_depth() > 0);
   RawTypedData* native_fields =
       reinterpret_cast<RawTypedData*>(*NativeFieldsAddr());
   if (native_fields == TypedData::null()) {
@@ skipping 2383 matching lines @@
 
 RawMixinAppType* MixinAppType::New(const AbstractType& super_type,
                                    const Array& mixin_types) {
   const MixinAppType& result = MixinAppType::Handle(MixinAppType::New());
   result.set_super_type(super_type);
   result.set_mixin_types(mixin_types);
   return result.raw();
 }
 
 
+RawInstance* Number::CheckAndCanonicalize(const char** error_str) const {
+  intptr_t cid = GetClassId();
+  switch (cid) {
+    case kSmiCid:
+      return reinterpret_cast<RawSmi*>(raw_value());
+    case kMintCid:
+      return Mint::NewCanonical(Mint::Cast(*this).value());
+    case kDoubleCid:
+      return Double::NewCanonical(Double::Cast(*this).value());
+    case kBigintCid: {

[regis, 2016/04/06 22:02:39]

Why are you not calling the existing Bigint::NewCanonical as for Mint and Double
above?

[siva, 2016/04/06 22:26:36]

Bigint::NewCanonical requires a String object which is scanned and converted
into a bigint, it would be expensive to convert the bigint object back to a
string and then call Bigint::NewCanonical.

I could have called Instance::CheckAndCanonicalize here but that is the code I
am going to change next for instance/arrays to use a HashMap and hence that code
appears to be duplicated here.

[regis, 2016/04/06 22:42:44]

I missed the fact that the argument is a String.

+      Thread* thread = Thread::Current();
+      Zone* zone = thread->zone();
+      Isolate* isolate = thread->isolate();
+      if (!CheckAndCanonicalizeFields(zone, error_str)) {
+        return Instance::null();
+      }
+      Bigint& result = Bigint::Handle(zone);
+      const Class& cls = Class::Handle(zone, this->clazz());
+      intptr_t index = 0;
+      result ^= cls.LookupCanonicalBigint(zone, Bigint::Cast(*this), &index);
+      if (!result.IsNull()) {
+        return result.raw();
+      }
+      {
+        SafepointMutexLocker ml(isolate->constant_canonicalization_mutex());
+        // Retry lookup.
+        {
+          result ^= cls.LookupCanonicalBigint(
+              zone, Bigint::Cast(*this), &index);
+          if (!result.IsNull()) {
+            return result.raw();
+          }
+        }
+
+        // The value needs to be added to the list. Grow the list if
+        // it is full.
+        result ^= this->raw();
+        ASSERT((isolate == Dart::vm_isolate()) || !result.InVMHeap());
+        if (result.IsNew()) {
+          // Create a canonical object in old space.
+          result ^= Object::Clone(result, Heap::kOld);
+        }
+        ASSERT(result.IsOld());
+        result.SetCanonical();
+        cls.InsertCanonicalNumber(zone, index, result);
+        return result.raw();
+      }
+    }
+    default:
+      UNREACHABLE();
+  }
+  return Instance::null();
+}
+
+
 const char* Number::ToCString() const {
   // Number is an interface. No instances of Number should exist.
   UNREACHABLE();
   return "Number";
 }
 
 
 const char* Integer::ToCString() const {
   // Integer is an interface. No instances of Integer should exist except null.
   ASSERT(IsNull());
@@ skipping 403 matching lines @@
   Mint& canonical_value = Mint::Handle(zone);
   intptr_t index = 0;
   canonical_value ^= cls.LookupCanonicalMint(zone, value, &index);
   if (!canonical_value.IsNull()) {
     return canonical_value.raw();
   }
   {
     SafepointMutexLocker ml(isolate->constant_canonicalization_mutex());
     // Retry lookup.
     {
-      const Mint& result =
-          Mint::Handle(zone, cls.LookupCanonicalMint(zone, value, &index));
-      if (!result.IsNull()) {
-        return result.raw();
+      canonical_value ^= cls.LookupCanonicalMint(zone, value, &index);
+      if (!canonical_value.IsNull()) {
+        return canonical_value.raw();
       }
     }
     canonical_value = Mint::New(value, Heap::kOld);
     canonical_value.SetCanonical();
     // The value needs to be added to the constants list. Grow the list if
     // it is full.
-    cls.InsertCanonicalConstant(index, canonical_value);
+    cls.InsertCanonicalNumber(zone, index, canonical_value);
     return canonical_value.raw();
   }
 }
 
 
 bool Mint::Equals(const Instance& other) const {
   if (this->raw() == other.raw()) {
     // Both handles point to the same raw instance.
     return true;
   }
@@ skipping 122 matching lines @@
   intptr_t index = 0;
 
   canonical_value ^= cls.LookupCanonicalDouble(zone, value, &index);
   if (!canonical_value.IsNull()) {
     return canonical_value.raw();
   }
   {
     SafepointMutexLocker ml(isolate->constant_canonicalization_mutex());
     // Retry lookup.
     {
-      const Double& result =
-          Double::Handle(zone, cls.LookupCanonicalDouble(zone, value, &index));
-      if (!result.IsNull()) {
-        return result.raw();
+      canonical_value ^= cls.LookupCanonicalDouble(zone, value, &index);
+      if (!canonical_value.IsNull()) {
+        return canonical_value.raw();
       }
     }
     canonical_value = Double::New(value, Heap::kOld);
     canonical_value.SetCanonical();
     // The value needs to be added to the constants list. Grow the list if
     // it is full.
-    cls.InsertCanonicalConstant(index, canonical_value);
+    cls.InsertCanonicalNumber(zone, index, canonical_value);
     return canonical_value.raw();
   }
 }
 
 
 RawDouble* Double::NewCanonical(const String& str) {
   double double_value;
   if (!CStringToDouble(str.ToCString(), str.Length(), &double_value)) {
     return Double::Handle().raw();
   }
@@ skipping 106 matching lines @@
 
   for (intptr_t i = 0; i < used; i++) {
     if (this->DigitAt(i) != other_bgi.DigitAt(i)) {
       return false;
     }
   }
   return true;
 }
 
 
-bool Bigint::CheckAndCanonicalizeFields(const char** error_str) const {
+bool Bigint::CheckAndCanonicalizeFields(Zone* zone,
+                                        const char** error_str) const {
   // Bool field neg should always be canonical.
-  ASSERT(Bool::Handle(neg()).IsCanonical());
+  ASSERT(Bool::Handle(zone, neg()).IsCanonical());
   // Smi field used is canonical by definition.
   if (Used() > 0) {
     // Canonicalize TypedData field digits.
-    TypedData& digits_ = TypedData::Handle(digits());
+    TypedData& digits_ = TypedData::Handle(zone, digits());
     digits_ ^= digits_.CheckAndCanonicalize(NULL);
     ASSERT(!digits_.IsNull());
     set_digits(digits_);
   } else {
     ASSERT(digits() == TypedData::EmptyUint32Array(Thread::Current()));
   }
   return true;
 }
 
 
@@ skipping 137 matching lines @@
 
 RawBigint* Bigint::NewCanonical(const String& str) {
   Thread* thread = Thread::Current();
   Zone* zone = thread->zone();
   Isolate* isolate = thread->isolate();
   const Bigint& value = Bigint::Handle(
       zone, Bigint::NewFromCString(str.ToCString(), Heap::kOld));
   const Class& cls =
       Class::Handle(zone, isolate->object_store()->bigint_class());
   intptr_t index = 0;
-  const Bigint& canonical_value =
-      Bigint::Handle(zone, cls.LookupCanonicalBigint(zone, value, &index));
+  Bigint& canonical_value = Bigint::Handle(zone);
+  canonical_value ^= cls.LookupCanonicalBigint(zone, value, &index);
   if (!canonical_value.IsNull()) {
     return canonical_value.raw();
   }
   {
     SafepointMutexLocker ml(isolate->constant_canonicalization_mutex());
     // Retry lookup.
     {
-      const Bigint& result =
-          Bigint::Handle(zone, cls.LookupCanonicalBigint(zone, value, &index));
-      if (!result.IsNull()) {
-        return result.raw();
+      canonical_value ^= cls.LookupCanonicalBigint(zone, value, &index);
+      if (!canonical_value.IsNull()) {
+        return canonical_value.raw();
       }
     }
     value.SetCanonical();
     // The value needs to be added to the constants list. Grow the list if
     // it is full.
-    cls.InsertCanonicalConstant(index, value);
+    cls.InsertCanonicalNumber(zone, index, value);
     return value.raw();
   }
 }
 
 
 RawTypedData* Bigint::NewDigitsFromHexCString(const char* str, intptr_t* used,
                                               Heap::Space space) {
   const int kBitsPerHexDigit = 4;
   const int kHexDigitsPerDigit = 8;
   const int kBitsPerDigit = kBitsPerHexDigit * kHexDigitsPerDigit;
@@ skipping 2218 matching lines @@
   if (this->raw() == other.raw()) {
     // Both handles point to the same raw instance.
     return true;
   }
 
   // An Array may be compared to an ImmutableArray.
   if (!other.IsArray() || other.IsNull()) {
     return false;
   }
 
-  // Both arrays must have the same type arguments.
-  const TypeArguments& type_args = TypeArguments::Handle(GetTypeArguments());
-  const TypeArguments& other_type_args = TypeArguments::Handle(
-      other.GetTypeArguments());
-  if (!type_args.Equals(other_type_args)) {
-    return false;
-  }
-
+  // First check if both arrays have the same length and elements.
   const Array& other_arr = Array::Cast(other);
 
   intptr_t len = this->Length();
   if (len != other_arr.Length()) {
     return false;
   }
 
   for (intptr_t i = 0; i < len; i++) {

[regis, 2016/04/06 22:02:39]

Depending on len, this loop could be much more expensive than checking the type
arguments and could be run last (possibly only if len is above a threshold, but
that requires more code).
If the average array is small, checking the type arguments last is fine.

[siva, 2016/04/06 22:26:36]

How many times do you think we will have a case where the length is the same and
all the objects are identical but the TypeArguments are different, I am thinking
that is a rarer case. Most of the times the length will not match or if the
length matches then some objects in the array will not match and we will bailout
sooner.

Agreed there could be a degenerate case where a 1000 length array has 999
elements that are identical and the last one is different.

[regis, 2016/04/06 22:42:44]

True, checking the (identical) type first would not help in that case. What I
had in mind is more like 2 identical arrays of 1000 elements, but one is typed
whereas the other one is raw.
But I agree, it is all speculation at this time :-)
Please submit as is.

     if (this->At(i) != other_arr.At(i)) {
       return false;
     }
   }
+
+  // Now check if both arrays have the same type arguments.
+  const TypeArguments& type_args = TypeArguments::Handle(GetTypeArguments());
+  const TypeArguments& other_type_args = TypeArguments::Handle(
+      other.GetTypeArguments());
+  if (!type_args.Equals(other_type_args)) {
+    return false;
+  }
   return true;
 }
 
 
 RawArray* Array::New(intptr_t len, Heap::Space space) {
   ASSERT(Isolate::Current()->object_store()->array_class() != Class::null());
   return New(kClassId, len, space);
 }
 
 
@@ skipping 125 matching lines @@
   array.SetLength(used_len);
 
   // Null the GrowableObjectArray, we are removing its backing array.
   growable_array.SetLength(0);
   growable_array.SetData(Object::empty_array());
 
   return array.raw();
 }
 
 
-bool Array::CheckAndCanonicalizeFields(const char** error_str) const {
-  Object& obj = Object::Handle();
+bool Array::CheckAndCanonicalizeFields(Zone* zone,
+                                       const char** error_str) const {
+  Object& obj = Object::Handle(zone);
   // Iterate over all elements, canonicalize numbers and strings, expect all
   // other instances to be canonical otherwise report error (return false).
   for (intptr_t i = 0; i < Length(); i++) {
     obj = At(i);
     if (obj.IsInstance() && !obj.IsSmi() && !obj.IsCanonical()) {
       if (obj.IsNumber() || obj.IsString()) {
         obj = Instance::Cast(obj).CheckAndCanonicalize(NULL);
         ASSERT(!obj.IsNull());
         this->SetAt(i, obj);
       } else {
@@ skipping 49 matching lines @@
   ASSERT(Length() > 0);
   intptr_t index = Length() - 1;
   const Array& contents = Array::Handle(data());
   const PassiveObject& obj = PassiveObject::Handle(contents.At(index));
   contents.SetAt(index, Object::null_object());
   SetLength(index);
   return obj.raw();
 }
 
 
-bool GrowableObjectArray::CanonicalizeEquals(const Instance& other) const {
-  // If both handles point to the same raw instance they are equal.
-  if (this->raw() == other.raw()) {
-    return true;
-  }
-
-  // Other instance must be non null and a GrowableObjectArray.
-  if (!other.IsGrowableObjectArray() || other.IsNull()) {
-    return false;
-  }
-
-  const GrowableObjectArray& other_arr = GrowableObjectArray::Cast(other);
-
-  // The capacity and length of both objects must be equal.
-  if (Capacity() != other_arr.Capacity() || Length() != other_arr.Length()) {
-    return false;
-  }
-
-  // Both arrays must have the same type arguments.
-  const TypeArguments& type_args = TypeArguments::Handle(GetTypeArguments());
-  const TypeArguments& other_type_args = TypeArguments::Handle(
-      other.GetTypeArguments());
-  if (!type_args.Equals(other_type_args)) {
-    return false;
-  }
-
-  // The data part in both arrays must be identical.
-  const Array& contents = Array::Handle(data());
-  const Array& other_contents = Array::Handle(other_arr.data());
-  for (intptr_t i = 0; i < Length(); i++) {
-    if (contents.At(i) != other_contents.At(i)) {
-      return false;
-    }
-  }
-  return true;
-}
-
-
 RawGrowableObjectArray* GrowableObjectArray::New(intptr_t capacity,
                                                  Heap::Space space) {
   const Array& data = Array::Handle(Array::New(capacity, space));
   return New(data, space);
 }
 
 
 RawGrowableObjectArray* GrowableObjectArray::New(const Array& array,
                                                  Heap::Space space) {
   ASSERT(Isolate::Current()->object_store()->growable_object_array_class()
@@ skipping 1100 matching lines @@
   return UserTag::null();
 }
 
 
 const char* UserTag::ToCString() const {
   const String& tag_label = String::Handle(label());
   return tag_label.ToCString();
 }
 
 }  // namespace dart