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::fill_count() const {
+  return raw_ptr()->fill_count_;
+}
+
+
+void MegamorphicCache::set_fill_count(intptr_t fill_count) const {
+  raw_ptr()->fill_count_ = fill_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 size = kInitialCapacity;
+  const Array& buckets = Array::Handle(Array::New(2 * size));
+  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 < size; ++i) {
+    buckets.SetAt(2 * i, illegal);

[Vyacheslav Egorov (Google), 2012/12/03 14:55:22]

I don't like magical constant spread around

[Kevin Millikin (Google), 2012/12/06 14:03:11]

I thought this was already pretty localized, but I named the constants for the
size of the pair and its components anyway.

There is no simple way to use constants in the generated code because it is
encoded in a platform-specific scale factor in a memory operand.

+    buckets.SetAt((2 * i) + 1, handler);
+  }
+  result.set_buckets(buckets);
+  result.set_mask(size - 1);
+  result.set_fill_count(0);
+  return result.raw();
+}
+
+
+void MegamorphicCache::EnsureCapacity() const {
+  intptr_t old_size = mask() + 1;
+  double load_limit = kLoadFactor * static_cast<double>(old_size);
+  if (static_cast<double>(fill_count() + 1) > load_limit) {
+    const Array& old_buckets = Array::Handle(buckets());
+    intptr_t new_size = old_size * 2;
+    const Array& new_buckets = Array::Handle(Array::New(2 * new_size));
+
+    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_size; ++i) {
+      new_buckets.SetAt(2 * i, class_id);
+      new_buckets.SetAt((2 * i) + 1, target);
+    }
+    set_buckets(new_buckets);
+    set_mask(new_size - 1);
+    set_fill_count(0);
+
+    // Rehash the valid entries.
+    for (intptr_t i = 0; i < old_size; ++i) {
+      class_id ^= old_buckets.At(2 * i);
+      if (class_id.Value() != kIllegalCid) {
+        target ^= old_buckets.At((2 * i) + 1);
+        Insert(class_id, target);
+      }
+    }
+  }
+}
+
+
+void MegamorphicCache::Insert(const Smi& class_id,
+                              const Function& target) const {
+  ASSERT(static_cast<double>(fill_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 ^= backing_array.At(2 * i);
+    if (probe.Value() == kIllegalCid) {
+      backing_array.SetAt(2 * i, class_id);
+      backing_array.SetAt((2 * i) + 1, target);
+      set_fill_count(fill_count() + 1);

[Vyacheslav Egorov (Google), 2012/12/03 14:55:22]

consider renaming fill_count to size

[Kevin Millikin (Google), 2012/12/06 14:03:11]

Since variables ending in _size are always in bytes, that seems confusing.  I
was trying for something that couldn't be confused with the capacity (length,
entry_count, etc. seem confusing).

Since fill_count is bad, I went with filled_entry_count.

+      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 4312 matching lines @@
   }
   return result.raw();
 }
 
 
 const char* WeakProperty::ToCString() const {
   return "_WeakProperty";
 }
 
 }  // namespace dart