Using SubtypeTestCache object instead of an array, that way we do not need to patch and can communi…

runtime/vm/code_generator.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/code_generator.h"
 
 #include "vm/code_patcher.h"
 #include "vm/compiler.h"
 #include "vm/dart_api_impl.h"
 #include "vm/dart_entry.h"
@@ skipping 433 matching lines @@
 // This updates the type test cache, an array containing 4-value elements
 // (instance class, instance type arguments, instantiator type arguments and
 // test_result). It can be applied to classes with type arguments in which
 // case it contains just the result of the class subtype test, not including
 // the evaluation of type arguments.
 // This operation is currently very slow (lookup of code is not efficient yet).
 static void UpdateTypeTestCache(intptr_t node_id,
                                 const Instance& instance,
                                 const AbstractType& type,
                                 const AbstractTypeArguments& type_instantiator,
-                                const Bool& result) {
+                                const Bool& result,
+                                const SubtypeTestCache& new_cache) {
   // Since the test is expensive, don't do it unless necessary.
   // The list of disallowed cases will decrease as they are implemented in
   // inlined assembly.
-  if (!type.IsInstantiated()) return;
-  if (Class::Handle(type.type_class()).HasTypeArguments()) {
-    const AbstractTypeArguments& type_arguments =
-        AbstractTypeArguments::Handle(type.arguments());
-    const bool is_raw_type = type_arguments.IsNull() ||
-        type_arguments.IsRaw(type_arguments.Length());
-    if (!is_raw_type) {
-      // We cannot inline tests for instances with more than one type argument
-      // or if its class has not been resolved (malformed type).
-      if (type_arguments.Length() != 1) {
-        // We can handle only one argument so far.
-        return;
-      }
-      const AbstractType& tp_argument =
-          AbstractType::ZoneHandle(type_arguments.TypeAt(0));
-      if (!tp_argument.IsType()) {
-        // E.g, it is TypeParameter.
-        return;
-      }
-      ASSERT(tp_argument.HasResolvedTypeClass());
-    }
-  }
+  if (new_cache.IsNull()) return;
   AbstractTypeArguments& instance_type_arguments =
       AbstractTypeArguments::Handle();
   const Class& instance_class = Class::Handle(instance.clazz());
   AbstractTypeArguments& original_instance_type_arguments =
       AbstractTypeArguments::Handle();
   if (instance_class.HasTypeArguments()) {
+    // Canonicalize type arguments.
     original_instance_type_arguments = instance.GetTypeArguments();
     OptimizeTypeArguments(instance);
     instance_type_arguments = instance.GetTypeArguments();
   }
 
-  DartFrameIterator iterator;
-  StackFrame* caller_frame = iterator.NextFrame();
-  ASSERT(caller_frame != NULL);
-  const Code& code = Code::Handle(caller_frame->LookupDartCode());
-  ASSERT(!code.IsNull());
-  uword loc = code.GetTypeTestAtNodeId(node_id);
-  if (loc != 0) {
-    // Found type test cache.
-    Array& cache = Array::Handle(CodePatcher::GetTypeTestArray(loc));
-    // TODO(srdjan): Prevent type test cache from growing too much, it has been
-    // observed to grow to 100 elements.
-    // Don't enter duplicate entries.
-    // TODO(srdjan): Check instantiator type arguments as well.
-    Object& last_instance_class = Object::Handle();
-    Object& last_instance_type_arguments = Object::Handle();
-    // Check for duplicate entries (can happen if we optimized type arguments
-    // above).
-    for (intptr_t i = 0; i < cache.Length();
-         i += SubTypeTestCache::kNumEntries) {
-      last_instance_class = cache.At(i + SubTypeTestCache::kInstanceClass);
-      last_instance_type_arguments =
-          cache.At(i + SubTypeTestCache::kInstanceTypeArguments);
-      if ((last_instance_class.raw() == instance_class.raw()) &&
-          (last_instance_type_arguments.raw() ==
-              instance_type_arguments.raw())) {
-        if (FLAG_trace_type_checks &&
-            (original_instance_type_arguments.raw() ==
-             instance_type_arguments.raw())) {
+  Class& last_instance_class = Class::Handle();
+  AbstractTypeArguments& last_instance_type_arguments =
+      AbstractTypeArguments::Handle();
+  AbstractTypeArguments& last_instantiator_type_arguments =
+      AbstractTypeArguments::Handle();
+  Bool& last_result = Bool::Handle();
+  intptr_t len = new_cache.NumberOfChecks();
+  for (intptr_t i = 0; i < len; ++i) {
+    new_cache.GetCheck(i, &last_instance_class,
+                          &last_instance_type_arguments,

[regis, 2012/05/03 20:59:11]

Interesting indentation

[srdjan, 2012/05/03 21:51:08]

Made it conventional.

+                          &last_instantiator_type_arguments,
+                          &last_result);
+    if ((last_instance_class.raw() == instance_class.raw()) &&
+        (last_instance_type_arguments.raw() ==
+            instance_type_arguments.raw())) {
+      if (FLAG_trace_type_checks) {
+        if (original_instance_type_arguments.raw() ==
+            instance_type_arguments.raw()) {
           PrintTypeCheck("WARNING duplicate cache entry", instance, type,
               type_instantiator, result);
         }
-        return;
       }
+      // A duplicate entry found, likely because the instance type arguments
+      // were not cacnonicalized before.
+      return;
     }
-
-    // Array must be null terminated.
-    ASSERT(last_instance_class.IsNull());
-    ASSERT(!cache.IsNull());
-    // Cache is null terminate, i.e., the last entry contains all null elements.
-    intptr_t old_len = cache.Length();
-    cache = cache.Grow(cache, old_len + SubTypeTestCache::kNumEntries);
-    intptr_t last_start = old_len - SubTypeTestCache::kNumEntries;
-    cache.SetAt(last_start + SubTypeTestCache::kInstanceClass, instance_class);
-    cache.SetAt(last_start + SubTypeTestCache::kInstanceTypeArguments,
-        instance_type_arguments);
-    // TODO(srdjan): Store instantiator arguments instead of null.
-    cache.SetAt(last_start + SubTypeTestCache::kInstantiatorTypeArguments,
-        AbstractTypeArguments::Handle());
-    cache.SetAt(last_start + SubTypeTestCache::kTestResult , result);
-    if (FLAG_trace_type_checks) {
-      OS::Print("  Updated test cache: [0x%x %s, 0x%x %s]\n"
-                "                      [0x%x %s] %s\n",
-           instance_class.raw(),
-           instance_class.ToCString(),
-           instance_type_arguments.raw(),
-           instance_type_arguments.ToCString(),
-           type.type_class(),
-           Class::Handle(type.type_class()).ToCString(),
-           result.ToCString());
-    }
-    CodePatcher::SetTypeTestArray(loc, cache);
+  }
+  new_cache.AddCheck(instance_class,
+                     instance_type_arguments,
+                     AbstractTypeArguments::Handle(),
+                     result);
+  if (FLAG_trace_type_checks) {
+    OS::Print("  Updated test cache 0x%x ix:%d:\n"
+              "    [0x%x %s, 0x%x %s]\n"
+              "    [0x%x %s] %s\n",
+         new_cache.raw(),

[regis, 2012/05/03 20:59:11]

indentation

[regis, 2012/05/03 20:59:11]

indentation

[srdjan, 2012/05/03 21:51:08]

Done.

[srdjan, 2012/05/03 21:51:08]

Done.

+         len,
+         instance_class.raw(),
+         instance_class.ToCString(),
+         instance_type_arguments.raw(),
+         instance_type_arguments.ToCString(),
+         type.type_class(),
+         Class::Handle(type.type_class()).ToCString(),
+         result.ToCString());
   }
 }
 
 
 // Check that the given instance is an instance of the given type.
 // Tested instance may not be null, because the null test is inlined.
 // Arg0: index of the token of the instanceof test (source location).
 // Arg1: node id of the instanceof node.
 // Arg2: instance being checked.
 // Arg3: type.
 // Arg4: type arguments of the instantiator of the type.
+// Arg5: SubtypeTestCache.
 // Return value: true or false, or may throw a type error in checked mode.
-DEFINE_RUNTIME_ENTRY(Instanceof, 5) {
+DEFINE_RUNTIME_ENTRY(Instanceof, 6) {
   ASSERT(arguments.Count() == kInstanceofRuntimeEntry.argument_count());
   // TODO(regis): Get the token index from the PcDesc (via DartFrame).
   intptr_t location = Smi::CheckedHandle(arguments.At(0)).Value();
   intptr_t node_id = Smi::CheckedHandle(arguments.At(1)).Value();
   const Instance& instance = Instance::CheckedHandle(arguments.At(2));
   const AbstractType& type = AbstractType::CheckedHandle(arguments.At(3));
   const AbstractTypeArguments& type_instantiator =
       AbstractTypeArguments::CheckedHandle(arguments.At(4));
+  const SubtypeTestCache& cache =
+      SubtypeTestCache::CheckedHandle(arguments.At(5));
   ASSERT(type.IsFinalized());
   Error& malformed_error = Error::Handle();
   const Bool& result = Bool::Handle(
       instance.IsInstanceOf(type, type_instantiator, &malformed_error) ?
       Bool::True() : Bool::False());
   if (FLAG_trace_type_checks) {
     PrintTypeCheck("InstanceOf", instance, type, type_instantiator, result);
   }
   if (!result.value() && !malformed_error.IsNull()) {
     // Throw a dynamic type error only if the instanceof test fails.
     String& malformed_error_message =  String::Handle(
         String::New(malformed_error.ToErrorCString()));
     const String& no_name = String::Handle(String::NewSymbol(""));
     Exceptions::CreateAndThrowTypeError(
         location, no_name, no_name, no_name, malformed_error_message);
     UNREACHABLE();
   }
-  UpdateTypeTestCache(node_id, instance, type, type_instantiator, result);
+  UpdateTypeTestCache(
+      node_id, instance, type, type_instantiator, result, cache);
   arguments.SetReturn(result);
 }
 
 
 // For error reporting simplify type name, e.g, all integer types (Smi, Mint,
 // Bigint) a re reported as 'int'.
 static RawString* GetSimpleTypeName(const Instance& value) {
   if (value.IsInteger()) {
     return String::NewSymbol("int");
   } else {
     return Type::Handle(value.GetType()).Name();
   }
 }
 
 
 // Check that the type of the given instance is a subtype of the given type and
 // can therefore be assigned.
 // Arg0: index of the token of the assignment (source location).
 // Arg1: node-id of the assignemnt.
-// Arg1: instance being assigned.
-// Arg2: type being assigned to.
-// Arg3: type arguments of the instantiator of the type being assigned to.
-// Arg4: name of variable being assigned to.
+// Arg2: instance being assigned.
+// Arg3: type being assigned to.
+// Arg4: type arguments of the instantiator of the type being assigned to.
+// Arg5: name of variable being assigned to.
+// Arg6: SubtypeTestCache.
 // Return value: instance if a subtype, otherwise throw a TypeError.
-DEFINE_RUNTIME_ENTRY(TypeCheck, 6) {
+DEFINE_RUNTIME_ENTRY(TypeCheck, 7) {
   ASSERT(arguments.Count() == kTypeCheckRuntimeEntry.argument_count());
   // TODO(regis): Get the token index from the PcDesc (via DartFrame).
   intptr_t location = Smi::CheckedHandle(arguments.At(0)).Value();
   intptr_t node_id = Smi::CheckedHandle(arguments.At(1)).Value();
   const Instance& src_instance = Instance::CheckedHandle(arguments.At(2));
   const AbstractType& dst_type = AbstractType::CheckedHandle(arguments.At(3));
   const AbstractTypeArguments& dst_type_instantiator =
       AbstractTypeArguments::CheckedHandle(arguments.At(4));
   const String& dst_name = String::CheckedHandle(arguments.At(5));
+  const SubtypeTestCache& cache =
+      SubtypeTestCache::CheckedHandle(arguments.At(6));
   ASSERT(!dst_type.IsDynamicType());  // No need to check assignment.
   ASSERT(!dst_type.IsMalformed());  // Already checked in code generator.
   ASSERT(!src_instance.IsNull());  // Already checked in inlined code.
 
   Error& malformed_error = Error::Handle();
   const bool is_instance_of = src_instance.IsInstanceOf(
       dst_type, dst_type_instantiator, &malformed_error);
 
   if (FLAG_trace_type_checks) {
     PrintTypeCheck("TypeCheck", src_instance, dst_type, dst_type_instantiator,
@@ skipping 13 matching lines @@
     String& malformed_error_message =  String::Handle();
     if (!malformed_error.IsNull()) {
       ASSERT(FLAG_enable_type_checks);
       malformed_error_message = String::New(malformed_error.ToErrorCString());
     }
     Exceptions::CreateAndThrowTypeError(location, src_type_name, dst_type_name,
                                         dst_name, malformed_error_message);
     UNREACHABLE();
   }
   UpdateTypeTestCache(node_id, src_instance, dst_type, dst_type_instantiator,
-      Bool::ZoneHandle(Bool::True()));
+      Bool::ZoneHandle(Bool::True()), cache);
   arguments.SetReturn(src_instance);
 }
 
 
 // Report that the type of the given object is not bool in conditional context.
 // Arg0: index of the token of the assignment (source location).
 // Arg1: bad object.
 // Return value: none, throws a TypeError.
 DEFINE_RUNTIME_ENTRY(ConditionTypeError, 2) {
   ASSERT(arguments.Count() ==
@@ skipping 902 matching lines @@
       }
     }
   }
   // The cache is null terminated, therefore the loop above should never
   // terminate by itself.
   UNREACHABLE();
   return Code::null();
 }
 
 }  // namespace dart