Cache lookups at megamorphic call sites in optimized code.

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/bigint_operations.h"
@@ skipping 79 matching lines @@
 RawClass* Object::pc_descriptors_class_ = reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::stackmap_class_ = reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::var_descriptors_class_ =
     reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::exception_handlers_class_ =
     reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::deopt_info_class_ = reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::context_class_ = reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::context_scope_class_ = reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::icdata_class_ = reinterpret_cast<RawClass*>(RAW_NULL);
+RawClass* Object::megamorphic_cache_class_ =
+    reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::subtypetestcache_class_ =
     reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::api_error_class_ = reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::language_error_class_ = reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::unhandled_exception_class_ =
     reinterpret_cast<RawClass*>(RAW_NULL);
 RawClass* Object::unwind_error_class_ = reinterpret_cast<RawClass*>(RAW_NULL);
 #undef RAW_NULL
 
 
@@ skipping 265 matching lines @@
 
   cls = Class::New<Context>();
   context_class_ = cls.raw();
 
   cls = Class::New<ContextScope>();
   context_scope_class_ = cls.raw();
 
   cls = Class::New<ICData>();
   icdata_class_ = cls.raw();
 
+  cls = Class::New<MegamorphicCache>();
+  megamorphic_cache_class_ = cls.raw();
+
   cls = Class::New<SubtypeTestCache>();
   subtypetestcache_class_ = cls.raw();
 
   cls = Class::New<ApiError>();
   api_error_class_ = cls.raw();
 
   cls = Class::New<LanguageError>();
   language_error_class_ = cls.raw();
 
   cls = Class::New<UnhandledException>();
@@ skipping 55 matching lines @@
   SET_CLASS_NAME(code, Code);
   SET_CLASS_NAME(instructions, Instructions);
   SET_CLASS_NAME(pc_descriptors, PcDescriptors);
   SET_CLASS_NAME(stackmap, Stackmap);
   SET_CLASS_NAME(var_descriptors, LocalVarDescriptors);
   SET_CLASS_NAME(exception_handlers, ExceptionHandlers);
   SET_CLASS_NAME(deopt_info, DeoptInfo);
   SET_CLASS_NAME(context, Context);
   SET_CLASS_NAME(context_scope, ContextScope);
   SET_CLASS_NAME(icdata, ICData);
+  SET_CLASS_NAME(megamorphic_cache, MegamorphicCache);
   SET_CLASS_NAME(subtypetestcache, SubtypeTestCache);
   SET_CLASS_NAME(api_error, ApiError);
   SET_CLASS_NAME(language_error, LanguageError);
   SET_CLASS_NAME(unhandled_exception, UnhandledException);
   SET_CLASS_NAME(unwind_error, UnwindError);
 
   // Set up names for object array and one byte string class which are
   // pre-allocated in the vm isolate also.
   cls = Dart::vm_isolate()->object_store()->array_class();
   str = Symbols::ObjectArray();
@@ skipping 7281 matching lines @@
   // Number of array elements in one test entry.
   intptr_t len = result.TestEntryLength();
   // IC data array must be null terminated (sentinel entry).
   const Array& ic_data = Array::Handle(Array::New(len, Heap::kOld));
   result.set_ic_data(ic_data);
   result.WriteSentinel();
   return result.raw();
 }
 
 
+RawArray* MegamorphicCache::buckets() const {
+  return raw_ptr()->buckets_;
+}
+
+
+void MegamorphicCache::set_buckets(const Array& buckets) const {
+  StorePointer(&raw_ptr()->buckets_, buckets.raw());
+}
+
+
+// Class IDs in the table are smi-tagged, so we use a smi-tagged mask
+// and target class ID to avoid untagging (on each iteration of the
+// test loop) in generated code.
+intptr_t MegamorphicCache::mask() const {
+  return Smi::Value(raw_ptr()->mask_);
+}
+
+
+void MegamorphicCache::set_mask(intptr_t mask) const {
+  raw_ptr()->mask_ = Smi::New(mask);
+}
+
+
+intptr_t MegamorphicCache::filled_entry_count() const {
+  return raw_ptr()->filled_entry_count_;
+}
+
+
+void MegamorphicCache::set_filled_entry_count(intptr_t count) const {
+  raw_ptr()->filled_entry_count_ = count;
+}
+
+
+RawMegamorphicCache* MegamorphicCache::New() {
+  MegamorphicCache& result = MegamorphicCache::Handle();
+  { RawObject* raw = Object::Allocate(MegamorphicCache::kClassId,
+                                      MegamorphicCache::InstanceSize(),
+                                      Heap::kOld);
+    NoGCScope no_gc;
+    result ^= raw;
+  }
+  const intptr_t capacity = kInitialCapacity;
+  const Array& buckets = Array::Handle(Array::New(kEntryLength * capacity));
+  const Smi& illegal = Smi::Handle(Smi::New(kIllegalCid));
+  const Function& handler = Function::Handle(
+      Isolate::Current()->megamorphic_cache_table()->miss_handler());
+  for (intptr_t i = 0; i < capacity; ++i) {
+    SetEntry(buckets, i, illegal, handler);
+  }
+  result.set_buckets(buckets);
+  result.set_mask(capacity - 1);
+  result.set_filled_entry_count(0);
+  return result.raw();
+}
+
+
+void MegamorphicCache::EnsureCapacity() const {
+  intptr_t old_capacity = mask() + 1;
+  double load_limit = kLoadFactor * static_cast<double>(old_capacity);
+  if (static_cast<double>(filled_entry_count() + 1) > load_limit) {
+    const Array& old_buckets = Array::Handle(buckets());
+    intptr_t new_capacity = old_capacity * 2;
+    const Array& new_buckets =
+        Array::Handle(Array::New(kEntryLength * new_capacity));
+
+    Smi& class_id = Smi::Handle(Smi::New(kIllegalCid));
+    Function& target = Function::Handle(
+        Isolate::Current()->megamorphic_cache_table()->miss_handler());
+    for (intptr_t i = 0; i < new_capacity; ++i) {
+      SetEntry(new_buckets, i, class_id, target);
+    }
+    set_buckets(new_buckets);
+    set_mask(new_capacity - 1);
+    set_filled_entry_count(0);
+
+    // Rehash the valid entries.
+    for (intptr_t i = 0; i < old_capacity; ++i) {
+      class_id ^= GetClassId(old_buckets, i);
+      if (class_id.Value() != kIllegalCid) {
+        target ^= GetTargetFunction(old_buckets, i);
+        Insert(class_id, target);
+      }
+    }
+  }
+}
+
+
+void MegamorphicCache::Insert(const Smi& class_id,
+                              const Function& target) const {
+  ASSERT(static_cast<double>(filled_entry_count() + 1) <=
+         (kLoadFactor * static_cast<double>(mask() + 1)));
+  const Array& backing_array = Array::Handle(buckets());
+  intptr_t id_mask = mask();
+  intptr_t index = class_id.Value() & id_mask;
+  Smi& probe = Smi::Handle();
+  intptr_t i = index;
+  do {
+    probe ^= GetClassId(backing_array, i);
+    if (probe.Value() == kIllegalCid) {
+      SetEntry(backing_array, i, class_id, target);
+      set_filled_entry_count(filled_entry_count() + 1);
+      return;
+    }
+    i = (i + 1) & id_mask;
+  } while (i != index);
+  UNREACHABLE();
+}
+
+
+const char* MegamorphicCache::ToCString() const {
+  return "";
+}
+
+
 RawSubtypeTestCache* SubtypeTestCache::New() {
   ASSERT(Object::subtypetestcache_class() != Class::null());
   SubtypeTestCache& result = SubtypeTestCache::Handle();
   {
     // SubtypeTestCache objects are long living objects, allocate them in the
     // old generation.
     RawObject* raw = Object::Allocate(SubtypeTestCache::kClassId,
                                       SubtypeTestCache::InstanceSize(),
                                       Heap::kOld);
     NoGCScope no_gc;
@@ skipping 4344 matching lines @@
   }
   return result.raw();
 }
 
 
 const char* WeakProperty::ToCString() const {
   return "_WeakProperty";
 }
 
 }  // namespace dart