Simplify type argument instantiation cache lookup by introducing an array

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 75 matching lines @@
 #if defined(RAW_NULL)
 #error RAW_NULL should not be defined.
 #endif
 #define RAW_NULL kHeapObjectTag
 Object* Object::null_object_ = NULL;
 Array* Object::null_array_ = NULL;
 String* Object::null_string_ = NULL;
 Instance* Object::null_instance_ = NULL;
 TypeArguments* Object::null_type_arguments_ = NULL;
 Array* Object::empty_array_ = NULL;
+Array* Object::zero_array_ = NULL;
 PcDescriptors* Object::empty_descriptors_ = NULL;
 Instance* Object::sentinel_ = NULL;
 Instance* Object::transition_sentinel_ = NULL;
 Instance* Object::unknown_constant_ = NULL;
 Instance* Object::non_constant_ = NULL;
 Bool* Object::bool_true_ = NULL;
 Bool* Object::bool_false_ = NULL;
 Smi* Object::smi_illegal_cid_ = NULL;
 LanguageError* Object::snapshot_writer_error_ = NULL;
 LanguageError* Object::branch_offset_error_ = NULL;
@@ skipping 336 matching lines @@
   Isolate* isolate = Isolate::Current();
   Heap* heap = isolate->heap();
 
   // Allocate the read only object handles here.
   null_object_ = Object::ReadOnlyHandle();
   null_array_ = Array::ReadOnlyHandle();
   null_string_ = String::ReadOnlyHandle();
   null_instance_ = Instance::ReadOnlyHandle();
   null_type_arguments_ = TypeArguments::ReadOnlyHandle();
   empty_array_ = Array::ReadOnlyHandle();
+  zero_array_ = Array::ReadOnlyHandle();
   empty_descriptors_ = PcDescriptors::ReadOnlyHandle();
   sentinel_ = Instance::ReadOnlyHandle();
   transition_sentinel_ = Instance::ReadOnlyHandle();
   unknown_constant_ =  Instance::ReadOnlyHandle();
   non_constant_ =  Instance::ReadOnlyHandle();
   bool_true_ = Bool::ReadOnlyHandle();
   bool_false_ = Bool::ReadOnlyHandle();
   smi_illegal_cid_ = Smi::ReadOnlyHandle();
   snapshot_writer_error_ = LanguageError::ReadOnlyHandle();
   branch_offset_error_ = LanguageError::ReadOnlyHandle();
 
 
   // Allocate and initialize the null instance.
   // 'null_' must be the first object allocated as it is used in allocation to
   // clear the object.
   {
     uword address = heap->Allocate(Instance::InstanceSize(), Heap::kOld);
     null_ = reinterpret_cast<RawInstance*>(address + kHeapObjectTag);
     // The call below is using 'null_' to initialize itself.
     InitializeObject(address, kNullCid, Instance::InstanceSize());
   }
 
   *null_object_ = Object::null();
   *null_array_ = Array::null();
   *null_string_ = String::null();
   *null_instance_ = Instance::null();
   *null_type_arguments_ = TypeArguments::null();
 
-  // Initialize the empty array handle to null_ in order to be able to check
-  // if the empty array was allocated (RAW_NULL is not available).
+  // Initialize the empty and zero array handles to null_ in order to be able to
+  // check if the empty and zero arrays were allocated (RAW_NULL is not
+  // available).
   *empty_array_ = Array::null();
+  *zero_array_ = Array::null();
 
   Class& cls = Class::Handle();
 
   // Allocate and initialize the class class.
   {
     intptr_t size = Class::InstanceSize();
     uword address = heap->Allocate(size, Heap::kOld);
     class_class_ = reinterpret_cast<RawClass*>(address + kHeapObjectTag);
     InitializeObject(address, Class::kClassId, size);
 
@@ skipping 157 matching lines @@
   // Allocate and initialize the empty_array instance.
   {
     uword address = heap->Allocate(Array::InstanceSize(0), Heap::kOld);
     InitializeObject(address, kArrayCid, Array::InstanceSize(0));
     Array::initializeHandle(
         empty_array_,
         reinterpret_cast<RawArray*>(address + kHeapObjectTag));
     empty_array_->raw_ptr()->length_ = Smi::New(0);
   }
 
+  // Allocate and initialize the zero_array instance.
+  {
+    uword address = heap->Allocate(Array::InstanceSize(1), Heap::kOld);
+    InitializeObject(address, kArrayCid, Array::InstanceSize(1));
+    Array::initializeHandle(
+        zero_array_,
+        reinterpret_cast<RawArray*>(address + kHeapObjectTag));
+    zero_array_->raw_ptr()->length_ = Smi::New(1);
+    zero_array_->raw_ptr()->data()[0] = Smi::New(0);
+  }
+
   // Allocate and initialize the empty_descriptors instance.
   {
     uword address = heap->Allocate(PcDescriptors::InstanceSize(0), Heap::kOld);
     InitializeObject(address, kPcDescriptorsCid,
                      PcDescriptors::InstanceSize(0));
     PcDescriptors::initializeHandle(
         empty_descriptors_,
         reinterpret_cast<RawPcDescriptors*>(address + kHeapObjectTag));
     empty_descriptors_->raw_ptr()->length_ = Smi::New(0);
   }
@@ skipping 43 matching lines @@
   ASSERT(!null_array_->IsSmi());
   ASSERT(null_array_->IsArray());
   ASSERT(!null_string_->IsSmi());
   ASSERT(null_string_->IsString());
   ASSERT(!null_instance_->IsSmi());
   ASSERT(null_instance_->IsInstance());
   ASSERT(!null_type_arguments_->IsSmi());
   ASSERT(null_type_arguments_->IsTypeArguments());
   ASSERT(!empty_array_->IsSmi());
   ASSERT(empty_array_->IsArray());
+  ASSERT(!zero_array_->IsSmi());
+  ASSERT(zero_array_->IsArray());
   ASSERT(!sentinel_->IsSmi());
   ASSERT(sentinel_->IsInstance());
   ASSERT(!transition_sentinel_->IsSmi());
   ASSERT(transition_sentinel_->IsInstance());
   ASSERT(!unknown_constant_->IsSmi());
   ASSERT(unknown_constant_->IsInstance());
   ASSERT(!non_constant_->IsSmi());
   ASSERT(non_constant_->IsInstance());
   ASSERT(!bool_true_->IsSmi());
   ASSERT(bool_true_->IsBool());
@@ skipping 3480 matching lines @@
 
 RawTypeArguments* TypeArguments::InstantiateAndCanonicalizeFrom(
     const TypeArguments& instantiator_type_arguments,
     Error* bound_error) const {
   ASSERT(!IsInstantiated());
   ASSERT(instantiator_type_arguments.IsNull() ||
          instantiator_type_arguments.IsCanonical());
   // Lookup instantiator and, if found, return paired instantiated result.
   Array& prior_instantiations = Array::Handle(instantiations());
   ASSERT(!prior_instantiations.IsNull() && prior_instantiations.IsArray());
-  intptr_t length = prior_instantiations.Length();
+  // The instantiations cache is initialized with Object::zero_array() and is
+  // therefore guaranteed to contain kNoInstantiator. No length check needed.
+  ASSERT(prior_instantiations.Length() > 0);
   intptr_t index = 0;
-  while (index < length) {
+  while (true) {
     if (prior_instantiations.At(index) == instantiator_type_arguments.raw()) {
       return TypeArguments::RawCast(prior_instantiations.At(index + 1));
     }
     if (prior_instantiations.At(index) == Smi::New(StubCode::kNoInstantiator)) {
       break;
     }
     index += 2;
   }
   // Cache lookup failed. Instantiate the type arguments.
   TypeArguments& result = TypeArguments::Handle();
   result = InstantiateFrom(instantiator_type_arguments, bound_error);
   if ((bound_error != NULL) && !bound_error->IsNull()) {
     return result.raw();
   }
   // Instantiation did not result in bound error. Canonicalize type arguments.
   result = result.Canonicalize();
   // Add instantiator and result to instantiations array.
-  if ((index + 2) > length) {
+  intptr_t length = prior_instantiations.Length();
+  if ((index + 2) >= length) {
     // Grow the instantiations array.
-    length = (length == 0) ? 2 : length + 4;
+    // The initial array is Object::zero_array() of length 1.
+    length = (length == 1) ? 3 : length + 4;
     prior_instantiations =
         Array::Grow(prior_instantiations, length, Heap::kOld);
     set_instantiations(prior_instantiations);
+    ASSERT((index + 2) < length);
   }
   prior_instantiations.SetAt(index, instantiator_type_arguments);
   prior_instantiations.SetAt(index + 1, result);
-  if ((index + 2) < length) {
-    prior_instantiations.SetAt(index + 2,
-        Smi::Handle(Smi::New(StubCode::kNoInstantiator)));
-  }
+  prior_instantiations.SetAt(index + 2,
+                             Smi::Handle(Smi::New(StubCode::kNoInstantiator)));
   return result.raw();
 }
 
 
 RawTypeArguments* TypeArguments::New(intptr_t len, Heap::Space space) {
   if (len < 0 || len > kMaxElements) {
     // This should be caught before we reach here.
     FATAL1("Fatal error in TypeArguments::New: invalid len %" Pd "\n", len);
   }
   TypeArguments& result = TypeArguments::Handle();
   {
     RawObject* raw = Object::Allocate(TypeArguments::kClassId,
                                       TypeArguments::InstanceSize(len),
                                       space);
     NoGCScope no_gc;
     result ^= raw;
     // Length must be set before we start storing into the array.
     result.SetLength(len);
   }
-  result.set_instantiations(Object::empty_array());
+  // The zero array should have been initialized.
+  ASSERT(Object::zero_array().raw() != Array::null());
+  ASSERT(StubCode::kNoInstantiator == 0);

[Florian Schneider, 2014/02/17 10:09:59]

That can be make a COMPILE_ASSERT.

[regis, 2014/02/18 19:29:29]

I had never noticed this assert flavor before. Done.

+  result.set_instantiations(Object::zero_array());
   return result.raw();
 }
 
 
 
 RawAbstractType** TypeArguments::TypeAddr(intptr_t index) const {
   // TODO(iposva): Determine if we should throw an exception here.
   ASSERT((index >= 0) && (index < Length()));
   return &raw_ptr()->types_[index];
 }
@@ skipping 13113 matching lines @@
   return "_MirrorReference";
 }
 
 
 void MirrorReference::PrintToJSONStream(JSONStream* stream, bool ref) const {
   Instance::PrintToJSONStream(stream, ref);
 }
 
 
 }  // namespace dart