Cache lookups at megamorphic call sites in optimized code.

runtime/vm/object.h

 // 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.
 
 #ifndef VM_OBJECT_H_
 #define VM_OBJECT_H_
 
 #include "include/dart_api.h"
 #include "platform/assert.h"
 #include "platform/utils.h"
@@ skipping 276 matching lines @@
   static RawClass* deopt_info_class() { return deopt_info_class_; }
   static RawClass* context_class() { return context_class_; }
   static RawClass* context_scope_class() { return context_scope_class_; }
   static RawClass* api_error_class() { return api_error_class_; }
   static RawClass* language_error_class() { return language_error_class_; }
   static RawClass* unhandled_exception_class() {
     return unhandled_exception_class_;
   }
   static RawClass* unwind_error_class() { return unwind_error_class_; }
   static RawClass* icdata_class() { return icdata_class_; }
+  static RawClass* megamorphic_cache_class() {
+    return megamorphic_cache_class_;
+  }
   static RawClass* subtypetestcache_class() { return subtypetestcache_class_; }
 
   static RawError* Init(Isolate* isolate);
   static void InitFromSnapshot(Isolate* isolate);
   static void InitOnce();
   static void RegisterSingletonClassNames();
   static void MakeUnusedSpaceTraversable(const Object& obj,
                                          intptr_t original_size,
                                          intptr_t used_size);
 
@@ skipping 114 matching lines @@
   static RawClass* code_class_;  // Class of the Code vm object.
   static RawClass* instructions_class_;  // Class of the Instructions vm object.
   static RawClass* pc_descriptors_class_;  // Class of PcDescriptors vm object.
   static RawClass* stackmap_class_;  // Class of Stackmap vm object.
   static RawClass* var_descriptors_class_;  // Class of LocalVarDescriptors.
   static RawClass* exception_handlers_class_;  // Class of ExceptionHandlers.
   static RawClass* deopt_info_class_;  // Class of DeoptInfo.
   static RawClass* context_class_;  // Class of the Context vm object.
   static RawClass* context_scope_class_;  // Class of ContextScope vm object.
   static RawClass* icdata_class_;  // Class of ICData.
+  static RawClass* megamorphic_cache_class_;  // Class of MegamorphiCache.
   static RawClass* subtypetestcache_class_;  // Class of SubtypeTestCache.
   static RawClass* api_error_class_;  // Class of ApiError.
   static RawClass* language_error_class_;  // Class of LanguageError.
   static RawClass* unhandled_exception_class_;  // Class of UnhandledException.
   static RawClass* unwind_error_class_;  // Class of UnwindError.
 
   friend void ClassTable::Register(const Class& cls);
   friend void RawObject::Validate(Isolate* isolate) const;
   friend class Closure;
   friend class SnapshotReader;
@@ skipping 2484 matching lines @@
 #endif  // DEBUG
 
   intptr_t TestEntryLength() const;
   void WriteSentinel() const;
 
   HEAP_OBJECT_IMPLEMENTATION(ICData, Object);
   friend class Class;
 };
 
 
+class MegamorphicCache : public Object {
+ public:
+  static const int kInitialCapacity = 16;
+  static const double kLoadFactor = 0.75;
+
+  RawArray* buckets() const;
+  void set_buckets(const Array& buckets) const;
+
+  intptr_t mask() const;
+  void set_mask(intptr_t mask) const;
+
+  intptr_t filled_entry_count() const;
+  void set_filled_entry_count(intptr_t num) const;
+
+  static intptr_t buckets_offset() {
+    return OFFSET_OF(RawMegamorphicCache, buckets_);
+  }
+  static intptr_t mask_offset() {
+    return OFFSET_OF(RawMegamorphicCache, mask_);
+  }
+
+  static RawMegamorphicCache* New();
+
+  void EnsureCapacity() const;
+
+  void Insert(const Smi& class_id, const Function& target) const;
+
+  static intptr_t InstanceSize() {
+    return RoundedAllocationSize(sizeof(RawMegamorphicCache));
+  }
+
+ private:
+  friend class Class;
+
+  enum {
+    kClassIdIndex,
+    kTargetFunctionIndex,
+    kEntryLength,
+  };
+
+  static inline void SetEntry(const Array& array,
+                              intptr_t index,
+                              const Smi& class_id,
+                              const Function& target);
+
+  static inline RawObject* GetClassId(const Array& array, intptr_t index);
+  static inline RawObject* GetTargetFunction(const Array& array,
+                                             intptr_t index);
+
+  HEAP_OBJECT_IMPLEMENTATION(MegamorphicCache, Object);
+};
+
+
 class SubtypeTestCache : public Object {
  public:
   enum Entries {
     kInstanceClassId = 0,
     kInstanceTypeArguments = 1,
     kInstantiatorTypeArguments = 2,
     kTestResult = 3,
     kTestEntryLength  = 4,
   };
 
@@ skipping 3049 matching lines @@
     return false;  // Lengths don't match.
   }
   for (intptr_t i = 0; i < len; i++) {
     if (this->CharAt(i) != str.CharAt(begin_index + i)) {
       return false;
     }
   }
   return true;
 }
 
+
+void MegamorphicCache::SetEntry(const Array& array,
+                                intptr_t index,
+                                const Smi& class_id,
+                                const Function& target) {
+  array.SetAt((index * kEntryLength) + kClassIdIndex, class_id);
+  array.SetAt((index * kEntryLength) + kTargetFunctionIndex, target);
+}
+
+
+RawObject* MegamorphicCache::GetClassId(const Array& array, intptr_t index) {
+  return array.At((index * kEntryLength) + kClassIdIndex);
+}
+
+
+RawObject* MegamorphicCache::GetTargetFunction(const Array& array,
+                                               intptr_t index) {
+  return array.At((index * kEntryLength) + kTargetFunctionIndex);
+}
+
 }  // namespace dart
 
 #endif  // VM_OBJECT_H_