More type checking performance improvements and a bug fix in intrinsifier.

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 1418 matching lines @@
 
 // Optimize assignable type check 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.
 // Destroys ECX and EDX.
 // Returns:
 // - object in EAX for successful assignable check (or throws TypeError).
+// Performance notes: positive checks must be quick, negative checks can be slow
+// as they throw an exception.
 void CodeGenerator::GenerateAssertAssignable(intptr_t node_id,
                                              intptr_t token_index,
                                              const AbstractType& dst_type,
                                              const String& dst_name) {
   ASSERT(FLAG_enable_type_checks);
   ASSERT(token_index >= 0);
   ASSERT(!dst_type.IsNull());
   ASSERT(dst_type.IsFinalized());
 
   // Any expression is assignable to the Dynamic type and to the Object type.
@@ skipping 85 matching lines @@
         __ jmp(&done, Assembler::kNearJump);
       } else {
         // Failed assignable type check: call runtime to throw TypeError.
         __ jmp(&runtime_call, Assembler::kNearJump);
       }
       // Compare if the classes are equal.
       __ Bind(&compare_classes);
       // If dst_type is an interface, we can skip the class equality check,
       // because instances cannot be of an interface type.
       if (!dst_type_class.is_interface()) {
+        // Check if classes are equal.
         __ movl(ECX, FieldAddress(EAX, Object::class_offset()));
         TestClassAndJump(dst_type_class, &done);  // Uses ECX.
-        // Check superclass
+        // Check superclasses using a loop (faster than runtime call).
+        Label loop_done, loop;

[sra1, 2012/03/28 01:16:50]

This is a test where Dart can be much faster than JS.
This was a single test in Oberon.
Each class descriptor contains a table of pointers to all the superclasses,
including a self reference at the slot corresponding to the depth of the class
(number of extends from Object).

x is C =>
  x->class_offset->superclasses[C.extends_depth] == C.descriptor

Since C.extends_depth and C.descriptor are constants by this time, the generated
code can be:

  mov r2, [r1 + class_offset]
  cmp [r2 + superclasses + C.extends_depth*4], #C.descriptor
  jz yes

The original paper "Type-extension type test can be performed in constant time",
Norman H. Cohen, has a check on the inheritance depth but that can be avoided in
most cases (depth <= K) by always allocating at least K slots, or storing
something after the table that cannot contain a pointer to a class descriptor. 
If a variable sized descriptor is not possible, some clever hybrid could be
used, e.g. keep the top K slots in-line in the class descriptor, so most 'x is
C' tests can use the fast trick and fall back on the loop (bounded by a depth
check instead of null check) for depth > K.

[srdjan, 2012/03/28 01:46:23]

Thanks. The purpose of this CL is to quickly eliminate runtime calls, which are
still the most expensive part of checked mode. A quick supertype check is on our
TODO list.

+        __ Bind(&loop);
+        // ECX: class.
         __ movl(ECX, FieldAddress(ECX, Class::super_type_offset()));
-        // Note that supertypes can't be NULL as every Dart instance has
-        // as supertype class Object.
+        // The supertype of Object is a null object.
+        __ cmpl(ECX, raw_null);
+        __ j(EQUAL, &loop_done, Assembler::kNearJump);
         __ movl(ECX, FieldAddress(ECX, Type::type_class_offset()));
         TestClassAndJump(dst_type_class, &done);  // Uses ECX.
+        __ jmp(&loop);
+        __ Bind(&loop_done);
       } else {
         // However, for specific core library interfaces, we can check for
         // specific core library classes.
         Error& malformed_error = Error::Handle();
         if (dst_type.IsBoolInterface()) {
           __ movl(ECX, FieldAddress(EAX, Object::class_offset()));
           const Class& bool_class = Class::ZoneHandle(
               Isolate::Current()->object_store()->bool_class());
           TestClassAndJump(bool_class, &done);
         } else if (dst_type.IsSubtypeOf(
@@ skipping 37 matching lines @@
           __ movl(EBX, FieldAddress(EBX, Class::interfaces_offset()));
           __ cmpl(EBX, raw_null);
           __ j(EQUAL, &fall_through, Assembler::kNearJump);
           // Iterate over interfaces array and check if any of interfaces match.
           __ movl(EDI, FieldAddress(EBX, Array::length_offset()));
           // EDI: array index
           // EBX: array
           Label loop;
           __ Bind(&loop);
           __ subl(EDI, Immediate(Smi::RawValue(1)));
           __ cmpl(EDI, Immediate(0));

[sra1, 2012/03/28 01:16:50]

Should be unnecessary since SUB sets CC

[srdjan, 2012/03/28 01:46:23]

Thanks. Next CL.

           __ j(LESS, &runtime_call, Assembler::kNearJump);
           // EDI is Smi therefore TIMES_2 instead of TIMES_4.
           // Get type from array.
           __ movl(ECX, FieldAddress(EBX, EDI, TIMES_2, Array::data_offset()));
           __ movl(ECX, FieldAddress(ECX, Type::type_class_offset()));
           TestClassAndJump(dst_type_class, &done);  // Uses ECX.
           __ jmp(&loop, Assembler::kNearJump);
           // Fall through to runtime code.
           __ Bind(&fall_through);
         }
       }
     }
+  } else {
+    ASSERT(!dst_type.IsInstantiated());
+    // Skip check if destination is a dynamic type.
+    if (dst_type.IsTypeParameter()) {
+      // EAX must be preserved!
+      Label fall_through;
+      GenerateInstantiatorTypeArguments(token_index);
+      // Type arguments are on stack
+      __ popl(EBX);
+      // Check if dynamic.
+      __ cmpl(EBX, raw_null);
+      __ j(EQUAL, &done, Assembler::kNearJump);
+
+      // 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);
+      __ movl(EDX,
+          FieldAddress(EBX, TypeArguments::type_at_offset(dst_type.Index())));
+      __ CompareObject(EDX, Type::ZoneHandle(Type::DynamicType()));
+      __ j(EQUAL,  &done, Assembler::kNearJump);
+      __ Bind(&fall_through);
+    }
   }
   __ Bind(&runtime_call);
   __ PushObject(Object::ZoneHandle());  // Make room for the result.
   const Immediate location =
       Immediate(reinterpret_cast<int32_t>(Smi::New(token_index)));
   __ pushl(location);  // Push the source location.
   __ pushl(EAX);  // Push the source object.
   __ PushObject(dst_type);  // Push the type of the destination.
-  if (!dst_type.IsInstantiated()) {
+  if (dst_type.IsInstantiated()) {
+    __ pushl(raw_null);  // Null instantiator.
+  } else {
     GenerateInstantiatorTypeArguments(token_index);
-  } else {
-    __ pushl(raw_null);  // Null instantiator.
   }
   __ PushObject(dst_name);  // Push the name of the destination.
   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(5 * kWordSize));
   __ popl(EAX);
 
+  // EAX: value.
   __ Bind(&done);
 }
 
 
 void CodeGenerator::GenerateArgumentTypeChecks() {
   const Function& function = parsed_function_.function();
   LocalScope* scope = parsed_function_.node_sequence()->scope();
   const int num_fixed_params = function.num_fixed_parameters();
   const int num_opt_params = function.num_optional_parameters();
   ASSERT(num_fixed_params + num_opt_params <= scope->num_variables());
@@ skipping 571 matching lines @@
   // Restore the context.
   __ 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) {
   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(EAX);  // Pop instantiator.
+      __ popl(EBX);  // Pop 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(EAX, FieldAddress(EAX, type_arguments_instance_field_offset));
-      __ pushl(EAX);
+      __ movl(EBX, FieldAddress(EBX, type_arguments_instance_field_offset));
+      __ pushl(EBX);
     }
   }
 }
 
 
 // Pushes the type arguments on the stack in preparation of a constructor or
 // factory call.
 // For a factory call, instantiates (possibly requiring an additional run time
 // call) and pushes the type argument vector that will be passed as implicit
 // first parameter to the factory.
@@ skipping 456 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