Cache lookups at megamorphic call sites in optimized code.

runtime/vm/object.cc

Index: runtime/vm/object.cc
diff --git a/runtime/vm/object.cc b/runtime/vm/object.cc
index c51a27cc9ab0cd9391c4a7ec7b5f6434ee2f7ae9..dcd503d5489d596b14d434646fd62b5b3b7d266d 100644
--- a/runtime/vm/object.cc
+++ b/runtime/vm/object.cc
@@ -97,6 +97,8 @@ 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);
@@ -382,6 +384,9 @@ void Object::InitOnce() {
   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();
 
@@ -457,6 +462,7 @@ void Object::RegisterSingletonClassNames() {
   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);
@@ -7758,6 +7764,122 @@ RawICData* ICData::New(const Function& function,
 }
 
 
+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();