Inline type checks for complex uninstantiated types, e.g., List<T>.

runtime/vm/code_generator_ia32.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/globals.h"  // Needed here to get TARGET_ARCH_IA32.
 #if defined(TARGET_ARCH_IA32)
 
 #include "vm/code_generator.h"
 
 #include "lib/error.h"
@@ skipping 776 matching lines @@
   }
   ASSERT(function.context_scope() != ContextScope::null());
 
   // The function type of a closure may have type arguments. In that case, pass
   // the type arguments of the instantiator.
   const Class& cls = Class::Handle(function.signature_class());
   ASSERT(!cls.IsNull());
   const bool requires_type_arguments = cls.HasTypeArguments();
   if (requires_type_arguments) {
     ASSERT(!function.IsImplicitStaticClosureFunction());
-    GenerateInstantiatorTypeArguments(node->token_index());
+    const bool kPushInstantiator = false;
+    GenerateInstantiatorTypeArguments(node->token_index(), kPushInstantiator);
   }
   const Code& stub = Code::Handle(
       StubCode::GetAllocationStubForClosure(function));
   const ExternalLabel label(function.ToCString(), stub.EntryPoint());
   GenerateCall(node->token_index(), &label, PcDescriptors::kOther);
   if (requires_type_arguments) {
     __ popl(ECX);  // Pop type arguments.
   }
   if (function.IsImplicitInstanceClosureFunction()) {
     __ popl(ECX);  // Pop receiver.
@@ skipping 463 matching lines @@
                                               type,
                                               is_instance_lbl,
                                               is_not_instance_lbl);
       // If test non-conclusive so far, try the inlined type-test cache.
       // 'type' is known at compile time.
       return GenerateSubtype1TestCacheLookup(
           node_id, token_index, type_class,
           is_instance_lbl, is_not_instance_lbl);
     }
   } else {
-    GenerateUninstantiatedTypeTest(type,
-                                   token_index,
-                                   is_instance_lbl);
+    return GenerateUninstantiatedTypeTest(type,
+                                          node_id,
+                                          token_index,
+                                          is_instance_lbl,
+                                          is_not_instance_lbl);
   }
   return SubtypeTestCache::null();
 }
 
 
 // If instanceof type test cannot be performed successfully at compile time and
 // therefore eliminated, optimize it by adding inlined tests for:
 // - NULL -> return false.
 // - Smi -> compile time subtype check (only if dst class is not parameterized).
 // - Class equality (only if class is not parameterized).
@@ skipping 73 matching lines @@
   test_cache = GenerateInlineInstanceof(node_id, token_index, type,
                                         &is_instance_of, &is_not_instance_of);
 
   __ PushObject(Object::ZoneHandle());  // Make room for the result.
   const Immediate location = Immediate(Smi::RawValue(token_index));
   const Immediate node_id_as_smi = Immediate(Smi::RawValue(node_id));
   __ pushl(location);  // Push the source location.
   __ pushl(node_id_as_smi);  // node-id.
   __ pushl(EAX);  // Push the instance.
   __ PushObject(type);  // Push the type.
-  if (!type.IsInstantiated()) {
-    GenerateInstantiatorTypeArguments(token_index);
+  if (type.IsInstantiated()) {
+    __ pushl(raw_null);  // Null instantiator.
+    __ pushl(raw_null);  // Null instantiator.
   } else {
-    __ pushl(raw_null);  // Null instantiator.
+    const bool kPushInstantiator = true;
+    GenerateInstantiatorTypeArguments(token_index, kPushInstantiator);
   }
   __ LoadObject(EAX, test_cache);
   __ pushl(EAX);
   GenerateCallRuntime(node_id, token_index, kInstanceofRuntimeEntry);
   // Pop the two parameters supplied to the runtime entry. The result of the
   // instanceof runtime call will be left as the result of the operation.
-  __ addl(ESP, Immediate(6 * kWordSize));
+  __ addl(ESP, Immediate(7 * kWordSize));
   if (negate_result) {
     __ popl(EDX);
     __ CompareObject(EDX, bool_false);
     __ j(EQUAL, &is_not_instance_of, Assembler::kNearJump);
     // Fall through to is_instance_of.
   } else {
     __ jmp(&done);
   }
 
   __ Bind(&is_instance_of);
@@ skipping 64 matching lines @@
     // Instance class test only necessary.
     return GenerateSubtype1TestCacheLookup(
         node_id, token_index, type_class, is_instance_lbl, is_not_instance_lbl);
   }
   const SubtypeTestCache& type_test_cache =
       SubtypeTestCache::ZoneHandle(SubtypeTestCache::New());
   Label inlined_check, fall_through;
   const Immediate raw_null =
       Immediate(reinterpret_cast<intptr_t>(Object::null()));
   __ LoadObject(EDX, type_test_cache);
-  __ pushl(EDX);  // Cache array.
+  __ pushl(EDX);  // Subtype test cache.
   __ pushl(EAX);  // Instance.
   __ pushl(raw_null);  // Unused.
   __ call(&StubCode::Subtype2TestCacheLabel());
   __ popl(EAX);  // Discard.
   __ popl(EAX);  // Restore receiver.
   __ popl(EDX);  // Discard.
   // Result is in ECX: null -> not found, otherwise Bool::True or Bool::False.
 
   __ cmpl(ECX, raw_null);
   __ j(EQUAL, &fall_through, Assembler::kNearJump);
@@ skipping 97 matching lines @@
     __ movl(ECX, FieldAddress(ECX, Class::signature_function_offset()));
     __ cmpl(ECX, raw_null);
     __ j(NOT_EQUAL, is_instance_lbl);
   }
   // Otherwise fallthrough.
 }
 
 
 // EAX: instance to test.
 // Clobbers: EBX, EDX, ECX.
-void CodeGenerator::GenerateUninstantiatedTypeTest(
+RawSubtypeTestCache* CodeGenerator::GenerateUninstantiatedTypeTest(
     const AbstractType& type,
+    intptr_t node_id,
     intptr_t token_index,
-    Label* is_instance_lbl) {
+    Label* is_instance_lbl,
+    Label* is_not_instance_lbl) {
   ASSERT(!type.IsInstantiated());
   // Skip check if destination is a dynamic type.
+  const Immediate raw_null =
+      Immediate(reinterpret_cast<intptr_t>(Object::null()));
   if (type.IsTypeParameter()) {
-    const Immediate raw_null =
-        Immediate(reinterpret_cast<intptr_t>(Object::null()));
     // EAX must be preserved!
     Label fall_through;
-    GenerateInstantiatorTypeArguments(token_index);
+    const bool kPushInstantiator = false;
+    GenerateInstantiatorTypeArguments(token_index, kPushInstantiator);
     // Type arguments are on stack.
     __ popl(EBX);
     // Check if type argument is dynamic.
     __ cmpl(EBX, raw_null);
     __ j(EQUAL, is_instance_lbl);
 
     // For now handle only TypeArguments and bail out if InstantiatedTypeArgs.
     __ movl(EDX, FieldAddress(EBX, Object::class_offset()));
     __ CompareObject(EDX, Object::ZoneHandle(Object::type_arguments_class()));
     __ j(NOT_EQUAL, &fall_through, Assembler::kNearJump);
@@ skipping 39 matching lines @@
     // We have a non-parameterized class in EDX, compare with class of
     // value in EAX. EAX, EDX are preserved in stub.
     __ movl(ECX, FieldAddress(EAX, Object::class_offset()));
     __ call(&StubCode::IsRawSubTypeLabel());
     // Result in EBX: 1 is raw subtype.
     __ cmpl(EBX, Immediate(1));
     __ j(EQUAL, is_instance_lbl);
 
     // Test not conclusive.
     __ Bind(&fall_through);
+    return SubtypeTestCache::null();
   }
+  if (type.IsType()) {
+    Label fall_through;
+    __ testl(EAX, Immediate(kSmiTagMask));  // Is instance Smi?
+    __ j(ZERO, is_not_instance_lbl, Assembler::kNearJump);
+    // Uninstantiated type class is known at compile time, but the type
+    // arguments are determined at runtime by the instantiator.
+    const SubtypeTestCache& type_test_cache =
+        SubtypeTestCache::ZoneHandle(SubtypeTestCache::New());
+    __ LoadObject(EDX, type_test_cache);
+    __ pushl(EDX);  // Subtype test cache.
+    __ pushl(EAX);  // Instance.
+    const bool kPushInstantiator = false;
+    GenerateInstantiatorTypeArguments(token_index, kPushInstantiator);
+    __ call(&StubCode::Subtype3TestCacheLabel());
+    __ popl(EDX);  // Discard type arguments.
+    __ popl(EAX);  // Restore receiver.
+    __ popl(EDX);  // Discard subtype test cache.
+    // Result is in ECX: null -> not found, otherwise Bool::True or Bool::False.
+    __ cmpl(ECX, raw_null);
+    __ j(EQUAL, &fall_through, Assembler::kNearJump);
+    const Bool& bool_true = Bool::ZoneHandle(Bool::True());
+    __ CompareObject(ECX, bool_true);
+    __ j(EQUAL, is_instance_lbl);
+    __ jmp(is_not_instance_lbl);
+    __ Bind(&fall_through);
+    return type_test_cache.raw();
+  }
+  return SubtypeTestCache::null();
 }
 
 
 // If type check cannot be performed successfully at compile time and therefore
 // eliminated, optimize it by adding inlined tests for:
 // - NULL -> return NULL.
 // - Smi -> compile time subtype check (only if dst class is not parameterized).
 // - Class equality (only if class is not parameterized).
 // Inputs:
 // - EAX: object.
@@ skipping 78 matching lines @@
                                         &done, &runtime_call);
 
   __ Bind(&runtime_call);
   __ PushObject(Object::ZoneHandle());  // Make room for the result.
   __ pushl(Immediate(Smi::RawValue(token_index)));  // Source location.
   __ pushl(Immediate(Smi::RawValue(node_id)));  // node-id.
   __ pushl(EAX);  // Push the source object.
   __ PushObject(dst_type);  // Push the type of the destination.
   if (dst_type.IsInstantiated()) {
     __ pushl(raw_null);  // Null instantiator.
+    __ pushl(raw_null);  // Null instantiator type argument.
   } else {
-    GenerateInstantiatorTypeArguments(token_index);
+    const bool kPushInstantiator = true;
+    GenerateInstantiatorTypeArguments(token_index, kPushInstantiator);
   }
   __ PushObject(dst_name);  // Push the name of the destination.
   __ LoadObject(EAX, test_cache);
   __ pushl(EAX);
   GenerateCallRuntime(node_id, token_index, kTypeCheckRuntimeEntry);
   // Pop the parameters supplied to the runtime entry. The result of the
   // type check runtime call is the checked value.
-  __ addl(ESP, Immediate(7 * kWordSize));
+  __ addl(ESP, Immediate(8 * kWordSize));
   __ popl(EAX);
 
   // EAX: value.
   __ Bind(&done);
 }
 
 
 void CodeGenerator::GenerateArgumentTypeChecks() {
   const Function& function = parsed_function_.function();
   const SequenceNode& sequence_node = *parsed_function_.node_sequence();
@@ skipping 576 matching lines @@
   __ popl(CTX);
   // Result is in EAX.
   if (IsResultNeeded(node)) {
     __ pushl(EAX);
   }
 }
 
 
 // Pushes the type arguments of the instantiator on the stack.
 // Destroys EBX.
-void CodeGenerator::GenerateInstantiatorTypeArguments(intptr_t token_index) {
+void CodeGenerator::GenerateInstantiatorTypeArguments(intptr_t token_index,
+                                                      bool push_instantiator) {
+  if (push_instantiator) {
+    const Immediate raw_null =
+        Immediate(reinterpret_cast<intptr_t>(Object::null()));
+    __ pushl(raw_null);  // Initial instantiator.
+  }
   const Class& instantiator_class = Class::Handle(
       parsed_function().function().owner());
   if (instantiator_class.NumTypeParameters() == 0) {
     // The type arguments are compile time constants.
     AbstractTypeArguments& type_arguments = AbstractTypeArguments::ZoneHandle();
     // TODO(regis): Temporary type should be allocated in new gen heap.
     Type& type = Type::Handle(
         Type::New(instantiator_class, type_arguments, token_index));
     type ^= ClassFinalizer::FinalizeType(
         instantiator_class, type, ClassFinalizer::kFinalizeWellFormed);
     type_arguments = type.arguments();
     __ PushObject(type_arguments);
   } else {
     ASSERT(parsed_function().instantiator() != NULL);
     parsed_function().instantiator()->Visit(this);
     Function& outer_function =
         Function::Handle(parsed_function().function().raw());
     while (outer_function.IsLocalFunction()) {
       outer_function = outer_function.parent_function();
     }
     if (!outer_function.IsFactory()) {
-      __ popl(EBX);  // Pop instantiator.
+      if (push_instantiator) {
+        __ popl(EBX);   // Pop instantiator.
+        __ popl(ECX);   // Discard null instantiator.
+        __ pushl(EBX);  // Replace it with the real one.
+      } else {
+        __ popl(EBX);  // Pop instantiator.
+      }
+      // EBX: instantiator.
       // The instantiator is the receiver of the caller, which is not a factory.
       // The receiver cannot be null; extract its AbstractTypeArguments object.
       // Note that in the factory case, the instantiator is the first parameter
       // of the factory, i.e. already an AbstractTypeArguments object.
       intptr_t type_arguments_instance_field_offset =
           instantiator_class.type_arguments_instance_field_offset();
       ASSERT(type_arguments_instance_field_offset != Class::kNoTypeArguments);
       __ movl(EBX, FieldAddress(EBX, type_arguments_instance_field_offset));
       __ pushl(EBX);
     }
@@ skipping 18 matching lines @@
   if (type_arguments.IsNull() || type_arguments.IsInstantiated()) {
     // The type arguments are instantiated.
     __ PushObject(type_arguments);
     if (!instantiate_type_arguments) {
       // The type arguments of the instantiator are not needed, since the
       // type arguments are instantiated.
       __ pushl(Immediate(Smi::RawValue(StubCode::kNoInstantiator)));
     }
   } else {
     // The type arguments are uninstantiated.
-    GenerateInstantiatorTypeArguments(token_index);
+    const bool kPushInstantiator = false;
+    GenerateInstantiatorTypeArguments(token_index, kPushInstantiator);
     __ popl(EAX);  // Pop instantiator.
     // EAX is the instantiator AbstractTypeArguments object (or null).
     // If the instantiator is null and if the type argument vector
     // instantiated from null becomes a vector of Dynamic, then use null as
     // the type arguments.
     Label type_arguments_instantiated;
     const intptr_t len = type_arguments.Length();
     if (type_arguments.IsRawInstantiatedRaw(len)) {
       __ cmpl(EAX, raw_null);
       __ j(EQUAL, &type_arguments_instantiated, Assembler::kNearJump);
@@ skipping 467 matching lines @@
   const Error& error = Error::Handle(
       Parser::FormatError(script, token_index, "Error", format, args));
   va_end(args);
   Isolate::Current()->long_jump_base()->Jump(1, error);
   UNREACHABLE();
 }
 
 }  // namespace dart
 
 #endif  // defined TARGET_ARCH_IA32