Fix type test elimination using static type propagation in new compiler.

runtime/vm/object.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/object.h"
 
 #include "platform/assert.h"
 #include "vm/assembler.h"
 #include "vm/bigint_operations.h"
 #include "vm/bootstrap.h"
@@ skipping 1721 matching lines @@
   return raw() == Type::Handle(Type::ObjectType()).type_class();
 }
 
 
 bool Class::IsCanonicalSignatureClass() const {
   const Function& function = Function::Handle(signature_function());
   return (!function.IsNull() && (function.signature_class() == raw()));
 }
 
 
-// Checks if the type S is a subtype of type T.
+// If test == kIsSubtypeOf, checks if type S is a subtype of type T.
+// If test == kIsMoreSpecificThan, checks if type S is more specific than T.
 // Type S is specified by this class parameterized with 'type_arguments', and
 // type T by class 'other' parameterized with 'other_type_arguments'.
 // This class and class 'other' do not need to be finalized, however, they must
 // be resolved as well as their interfaces.
-bool Class::IsSubtypeOf(
+bool Class::TypeTest(
+    TypeTestKind test,

[srdjan, 2012/06/19 20:08:21]

MO, it would be more readable if you call this argument test_kind.

[regis, 2012/06/19 20:31:47]

Done.

     const AbstractTypeArguments& type_arguments,
     const Class& other,
     const AbstractTypeArguments& other_type_arguments,
     Error* malformed_error) const {
   // Check for DynamicType.
-  // The DynamicType on the lefthand side is replaced by the bottom type, which
-  // is more specific than any type.
-  // Any type is more specific than the DynamicType on the righthand side.
-  if (IsDynamicClass() || other.IsDynamicClass()) {
+  // Each occurrence of DynamicType in type T is interpreted as the Dynamic
+  // type, a supertype of all types.
+  if (other.IsDynamicClass()) {
     return true;
   }
+  // In the case of a subtype test, each occurrence of DynamicType in type S is
+  // interpreted as the bottom type, a subtype of all types.
+  if (IsDynamicClass()) {
+    return test == kIsSubtypeOf;
+  }
   // Check for reflexivity.
   if (raw() == other.raw()) {
     const intptr_t len = NumTypeArguments();
     if (len == 0) {
       return true;
     }
     // Since we do not truncate the type argument vector of a subclass (see
     // below), we only check a prefix of the proper length.
     // Check for covariance.
-    if (type_arguments.IsNull() ||
-        other_type_arguments.IsNull() ||
-        type_arguments.IsRawInstantiatedRaw(len) ||
+    if (other_type_arguments.IsNull() ||
         other_type_arguments.IsRawInstantiatedRaw(len)) {
       return true;
     }
-    return type_arguments.IsSubtypeOf(other_type_arguments,
-                                      len,
-                                      malformed_error);
+    if (type_arguments.IsNull() ||
+        type_arguments.IsRawInstantiatedRaw(len)) {
+      return test == kIsSubtypeOf;
+    }
+    return type_arguments.TypeTest(test,
+                                   other_type_arguments,
+                                   len,
+                                   malformed_error);
   }
   // Check for two function types.
   if (IsSignatureClass() && other.IsSignatureClass()) {
     const Function& fun = Function::Handle(signature_function());
     const Function& other_fun = Function::Handle(other.signature_function());
     return fun.IsSubtypeOf(type_arguments,
                            other_fun,
                            other_type_arguments,
                            malformed_error);
   }
@@ skipping 26 matching lines @@
       // check from true in production mode to false in checked mode.
       if (FLAG_enable_type_checks && !interface_args.IsNull()) {
         // Pass type_arguments as bounds instantiator.
         if (!interface_args.IsWithinBoundsOf(interface_class,
                                              type_arguments,
                                              malformed_error)) {
           continue;
         }
       }
     }
-    if (interface_class.IsSubtypeOf(interface_args,
-                                    other,
-                                    other_type_arguments,
-                                    malformed_error)) {
+    if (interface_class.TypeTest(test,
+                                 interface_args,
+                                 other,
+                                 other_type_arguments,
+                                 malformed_error)) {
       return true;
     }
   }
   // Check the interface case.
   if (is_interface()) {
     // We already checked the case where 'other' is an interface. Now, 'this',
     // an interface, cannot be more specific than a class, except class Object,
     // because although Object is not considered an interface by the vm, it is
     // one. In other words, all classes implementing this interface also extend
     // class Object. An interface is also more specific than the DynamicType.
     return (other.IsDynamicClass() || other.IsObjectClass());
   }
   const Class& super_class = Class::Handle(SuperClass());
   if (super_class.IsNull()) {
     return false;
   }
   // Instead of truncating the type argument vector to the length of the super
   // type argument vector, we make sure that the code works with a vector that
   // is longer than necessary.
-  return super_class.IsSubtypeOf(type_arguments,
-                                 other,
-                                 other_type_arguments,
-                                 malformed_error);
+  return super_class.TypeTest(test,
+                              type_arguments,
+                              other,
+                              other_type_arguments,
+                              malformed_error);
 }
 
 
 bool Class::IsTopLevel() const {
   return String::Handle(Name()).Equals("::");
 }
 
 
 RawFunction* Class::LookupDynamicFunction(const String& name) const {
   Function& function = Function::Handle(LookupFunction(name));
@@ skipping 536 matching lines @@
       (type_class() == Type::Handle(Type::FunctionInterface()).type_class());
 }
 
 
 bool AbstractType::IsListInterface() const {
   return HasResolvedTypeClass() &&
       (type_class() == Type::Handle(Type::ListInterface()).type_class());
 }
 
 
-bool AbstractType::IsSubtypeOf(const AbstractType& other,
-                               Error* malformed_error) const {
+bool AbstractType::TypeTest(TypeTestKind test,
+                            const AbstractType& other,
+                            Error* malformed_error) const {
   ASSERT(IsFinalized());
   ASSERT(other.IsFinalized());
   // In case the type checked in a type test is malformed, the code generator
   // may compile a throw instead of a run time call performing the type check.
   // However, in checked mode, a function type may include malformed result type
   // and/or malformed parameter types, which will then be encountered here at
   // run time.
   if (IsMalformed()) {
     ASSERT(FLAG_enable_type_checks);
     if (malformed_error->IsNull()) {
       *malformed_error = this->malformed_error();
     }
     return false;
   }
   if (other.IsMalformed()) {
     ASSERT(FLAG_enable_type_checks);
     if (malformed_error->IsNull()) {
       *malformed_error = other.malformed_error();
     }
     return false;
   }
-  // AbstractType parameters cannot be handled by Class::IsSubtypeOf().
+  // AbstractType parameters cannot be handled by Class::TypeTest().
   // When comparing two uninstantiated function types, one returning type
   // parameter K, the other returning type parameter V, we cannot assume that K
   // is a subtype of V, or vice versa. We only return true if K == V, i.e. if
   // they have the same index (both are finalized, so their indices are
   // comparable).
   // The same rule applies When checking the upper bound of a still
   // uninstantiated type at compile time. Returning false will defer the test
   // to run time. But there are cases where it can be decided at compile time.
   // For example, with class A<K, V extends K>, new A<T, T> called from within
   // a class B<T> will never require a run time bounds check, even it T is
   // uninstantiated at compile time.
-  if (IsTypeParameter() || other.IsTypeParameter()) {
-    return IsTypeParameter() && other.IsTypeParameter() &&
-        (Index() == other.Index());
+  if (IsTypeParameter()) {
+    if (other.IsTypeParameter()) {
+      return Index() == other.Index();
+    } else {
+      // TODO(regis): In checked mode, if the other type is the upper bound of
+      // this type parameter, then return true.
+      // We would need to keep the upper bound associated to the type parameter.
+    }
+    return false;
+  }
+  if (other.IsTypeParameter()) {
+    return false;
   }
   const Class& cls = Class::Handle(type_class());
-  return cls.IsSubtypeOf(AbstractTypeArguments::Handle(arguments()),
-                         Class::Handle(other.type_class()),
-                         AbstractTypeArguments::Handle(other.arguments()),
-                         malformed_error);
+  return cls.TypeTest(test,
+                      AbstractTypeArguments::Handle(arguments()),
+                      Class::Handle(other.type_class()),
+                      AbstractTypeArguments::Handle(other.arguments()),
+                      malformed_error);
 }
 
 
 const char* AbstractType::ToCString() const {
   // AbstractType is an abstract class.
   UNREACHABLE();
   return "AbstractType";
 }
 
 
@@ skipping 714 matching lines @@
   }
   const Class& super_class = Class::Handle(cls.SuperClass());
   if (!super_class.IsNull() &&
       !IsWithinBoundsOf(super_class, bounds_instantiator, malformed_error)) {
     return false;
   }
   return true;
 }
 
 
-bool AbstractTypeArguments::IsSubtypeOf(
-    const AbstractTypeArguments& other,
-    intptr_t len,
-    Error* malformed_error) const {
+bool AbstractTypeArguments::TypeTest(TypeTestKind test,

[srdjan, 2012/06/19 20:08:21]

ditto

[regis, 2012/06/19 20:31:47]

Done.

+                                     const AbstractTypeArguments& other,
+                                     intptr_t len,
+                                     Error* malformed_error) const {
   ASSERT(Length() >= len);
   ASSERT(!other.IsNull());
   ASSERT(other.Length() >= len);
   AbstractType& type = AbstractType::Handle();
   AbstractType& other_type = AbstractType::Handle();
   for (intptr_t i = 0; i < len; i++) {
     type = TypeAt(i);
     ASSERT(!type.IsNull());
     other_type = other.TypeAt(i);
     ASSERT(!other_type.IsNull());
-    if (!type.IsSubtypeOf(other_type, malformed_error)) {
+    if (!type.TypeTest(test, other_type, malformed_error)) {
       return false;
     }
   }
   return true;
 }
 
 
 const char* AbstractTypeArguments::ToCString() const {
   // AbstractTypeArguments is an abstract class, valid only for representing
   // null.
@@ skipping 6893 matching lines @@
   const String& str = String::Handle(pattern());
   const char* format = "JSRegExp: pattern=%s flags=%s";
   intptr_t len = OS::SNPrint(NULL, 0, format, str.ToCString(), Flags());
   char* chars = reinterpret_cast<char*>(
       Isolate::Current()->current_zone()->Allocate(len + 1));
   OS::SNPrint(chars, (len + 1), format, str.ToCString(), Flags());
   return chars;
 }
 
 }  // namespace dart