Cache lookups at megamorphic call sites in optimized code.

runtime/vm/megamorphic_cache_table.cc

Index: runtime/vm/megamorphic_cache_table.cc
diff --git a/runtime/vm/megamorphic_cache_table.cc b/runtime/vm/megamorphic_cache_table.cc
new file mode 100644
index 0000000000000000000000000000000000000000..12e7ea11368c9d22cd3760043067529f0505c26f
--- /dev/null
+++ b/runtime/vm/megamorphic_cache_table.cc
@@ -0,0 +1,99 @@
+// 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/megamorphic_cache_table.h"
+
+#include "vm/object.h"
+#include "vm/stub_code.h"
+#include "vm/symbols.h"
+
+namespace dart {
+
+MegamorphicCacheTable::MegamorphicCacheTable()
+    : capacity_(kInitialCapacity),

[srdjan, 2012/12/03 19:10:46]

initialize miss_handler to null.

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

Done.

+      length_(0),
+      table_(new Entry[kInitialCapacity]) {

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

I think you can allocate this on the first use of Lookup.

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

Done.

+}
+
+
+MegamorphicCacheTable::~MegamorphicCacheTable() {
+  delete[] table_;
+}
+
+
+RawMegamorphicCache* MegamorphicCacheTable::Lookup(const String& name,
+                                                   const Array& descriptor) {
+  for (intptr_t i = 0; i < length_; ++i) {
+    if ((table_[i].name == name.raw()) &&
+        (table_[i].descriptor == descriptor.raw())) {
+      return table_[i].cache;
+    }
+  }
+
+  if (length_ == capacity_) {
+    Entry* old_table = table_;

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

I suggest using realloc/free instead of new[]/delete[] than this loop goes away.

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

OK, but I originally did it this way to avoid unsightly reinterpret_casts of
void* and sizeof arithmetic.

+    capacity_ += kCapacityIncrement;
+    table_ = new Entry[capacity_];
+    for (intptr_t i = 0; i < length_; ++i) {
+      table_[i] = old_table[i];
+    }
+    delete[] old_table;
+  }
+
+  ASSERT(length_ < capacity_);
+  const MegamorphicCache& cache =
+      MegamorphicCache::Handle(MegamorphicCache::New());
+  Entry entry = { name.raw(), descriptor.raw(), cache.raw() };
+  table_[length_++] = entry;
+  return cache.raw();
+}
+
+
+void MegamorphicCacheTable::InitMissHandler() {
+  const Code& code =

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

I suggest adding a comment why do we need a fake function for this miss handler.

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

OK.

+      Code::Handle(StubCode::Generate("_stub_MegamorphicMiss",
+                                      StubCode::GenerateMegamorphicMissStub));
+  const String& name = String::Handle(Symbols::New("megamorphic_miss"));
+  const Class& cls =
+      Class::Handle(Type::Handle(Type::Function()).type_class());
+  const Function& function =
+      Function::Handle(Function::New(name,
+                                     RawFunction::kRegularFunction,
+                                     false,  // Not static.
+                                     false,  // Not const.
+                                     false,  // Not abstract.
+                                     false,  // Not external.
+                                     cls,
+                                     0));  // No token position.
+  function.SetCode(code);
+  miss_handler_ = function.raw();
+}
+
+
+void MegamorphicCacheTable::VisitObjectPointers(ObjectPointerVisitor* v) {
+  ASSERT(v != NULL);
+  v->VisitPointer(reinterpret_cast<RawObject**>(&miss_handler_));
+  for (intptr_t i = 0; i < length_; ++i) {
+    v->VisitPointer(reinterpret_cast<RawObject**>(&table_[i].name));
+    v->VisitPointer(reinterpret_cast<RawObject**>(&table_[i].descriptor));
+    v->VisitPointer(reinterpret_cast<RawObject**>(&table_[i].cache));
+  }
+}
+
+
+void MegamorphicCacheTable::PrintSizes() {
+  StackZone zone(Isolate::Current());
+  intptr_t size = 0;
+  MegamorphicCache& cache = MegamorphicCache::Handle();
+  Array& buckets = Array::Handle();
+  for (intptr_t i = 0; i < length_; ++i) {
+    cache = table_[i].cache;
+    buckets = cache.buckets();
+    size += MegamorphicCache::InstanceSize();
+    size += Array::InstanceSize(buckets.Length());
+  }
+  OS::Print("%"Pd" megamorphic caches using %"Pd"KB.\n", length_, size / 1024);
+}
+
+}  // namespace dart