First shot at static type propagation and type test elimination.

runtime/vm/flow_graph_builder.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/flow_graph_builder.h"
 
 #include "vm/ast_printer.h"
 #include "vm/bit_vector.h"
 #include "vm/code_descriptors.h"
 #include "vm/dart_entry.h"
@@ skipping 138 matching lines @@
     const LocalVariable& local, Value* value) {
   if (local.is_captured()) {
     intptr_t delta = owner()->context_level() -
                      local.owner()->context_level();
     ASSERT(delta >= 0);
     BindInstr* context = new BindInstr(new CurrentContextComp());
     AddInstruction(context);
     Value* context_value = new UseVal(context);
     while (delta-- > 0) {
       BindInstr* load = new BindInstr(new NativeLoadFieldComp(
-          context_value, Context::parent_offset()));
+          context_value, Context::parent_offset(), Type::ZoneHandle()));

[srdjan, 2012/05/16 20:16:15]

Why not pass dynamic type (meaning unknown) instead of null?

[regis, 2012/05/16 23:20:37]

I want to catch cases where the static type is requested by mistake (similar to
UNREACHABLE()). Using Dynamic would hide these cases.  

       AddInstruction(load);
       context_value = new UseVal(load);
     }
     Computation* store = new NativeStoreFieldComp(
         context_value, Context::variable_offset(local.index()), value);

[srdjan, 2012/05/16 20:16:15]

Needs a type as well, I think.

[regis, 2012/05/16 23:20:37]

No, the type of interest is the type of the assigned value, which may be more
specific than the type of the field.

     return store;
   } else {
     return new StoreLocalComp(local, value, owner()->context_level());
   }
 }
 
 
 Computation* EffectGraphVisitor::BuildLoadLocal(const LocalVariable& local) {
   if (local.is_captured()) {
     intptr_t delta = owner()->context_level() -
                      local.owner()->context_level();
     ASSERT(delta >= 0);
     BindInstr* context = new BindInstr(new CurrentContextComp());
     AddInstruction(context);
     Value* context_value = new UseVal(context);
     while (delta-- > 0) {
       BindInstr* load = new BindInstr(new NativeLoadFieldComp(
-          context_value, Context::parent_offset()));
+          context_value, Context::parent_offset(), Type::ZoneHandle()));

[srdjan, 2012/05/16 20:16:15]

dynamic type instead of null?

[regis, 2012/05/16 23:20:37]

Same as above.

       AddInstruction(load);
       context_value = new UseVal(load);
     }
     Computation* store = new NativeLoadFieldComp(
-        context_value, Context::variable_offset(local.index()));
+        context_value, Context::variable_offset(local.index()), local.type());
     return store;
   } else {
     return new LoadLocalComp(local, owner()->context_level());
   }
 }
 
 
 // Stores current context into the 'variable'
 void EffectGraphVisitor::BuildStoreContext(const LocalVariable& variable) {
   BindInstr* context = new BindInstr(new CurrentContextComp());
@@ skipping 96 matching lines @@
 
 void ValueGraphVisitor::VisitLiteralNode(LiteralNode* node) {
   ReturnComputation(new ConstantVal(node->literal()));
 }
 
 // Type nodes only occur as the right-hand side of instanceof comparisons,
 // and they are handled specially in that context.
 void EffectGraphVisitor::VisitTypeNode(TypeNode* node) { UNREACHABLE(); }
 
 
-// Returns true if the type check can be skipped, for example, if the type is
-// Dynamic or if the value is a compile time constant and an instance of type.
-static bool CanSkipTypeCheck(AstNode* value, const AbstractType& dst_type) {
+// Returns true if the type check can be skipped, for example, if the
+// destination type is Dynamic or if the static type of the value is a subtype
+// of the destination type.
+static bool CanSkipTypeCheck(Value* value, const AbstractType& dst_type) {
   ASSERT(FLAG_enable_type_checks);
   ASSERT(!dst_type.IsNull());
   ASSERT(dst_type.IsFinalized());
 
   // Any expression is assignable to the Dynamic type and to the Object type.
   // Skip the test.
   if (!dst_type.IsMalformed() &&
       (dst_type.IsDynamicType() || dst_type.IsObjectType())) {
     return true;
   }
 
   // It is a compile-time error to explicitly return a value (including null)
   // from a void function. However, functions that do not explicitly return a
   // value, implicitly return null. This includes void functions. Therefore, we
   // skip the type test here and trust the parser to only return null in void
   // function.
   if (dst_type.IsVoidType()) {
     return true;
   }
 
+  // If nothing is known about the value, as is the case for passed-in
+  // parameters, the test cannot be eliminated.
+  if (value == NULL) {
+    return false;
+  }
+
+  // If nothing is known about the static type of the value, the test cannot be
+  // eliminated.
+  const AbstractType& static_type = AbstractType::Handle(value->StaticType());
+  ASSERT(!static_type.IsMalformed());
+  if (static_type.IsDynamicType()) {
+    return false;
+  }
+
+  // If the static type of the value is void, the only allowed value is null,
+  // which must be verified by the type test.
+  if (static_type.IsVoidType()) {
+    // TODO(regis): Eliminate the test if the value is constant null.
+    return false;
+  }
+
   // Eliminate the test if it can be performed successfully at compile time.
-  if ((value != NULL) && value->IsLiteralNode()) {
-    const Instance& literal_value = value->AsLiteralNode()->literal();
-    const Class& cls = Class::Handle(literal_value.clazz());
-    if (cls.IsNullClass()) {
-      // There are only three instances that can be of Class Null:
-      // Object::null(), Object::sentinel(), and Object::transition_sentinel().
-      // The inline code and run time code performing the type check will never
-      // encounter the 2 sentinel values. The type check of a sentinel value
-      // will always be eliminated here, because these sentinel values can only
-      // be encountered as constants, never as actual value of an heap object
-      // being type checked.
-      ASSERT(literal_value.IsNull() ||
-             (literal_value.raw() == Object::sentinel()) ||
-             (literal_value.raw() == Object::transition_sentinel()));
-      return true;
-    }
-    Error& malformed_error = Error::Handle();
-    if (!dst_type.IsMalformed() &&
-        dst_type.IsInstantiated() &&
-        literal_value.IsInstanceOf(dst_type,
-                                   TypeArguments::Handle(),
-                                   &malformed_error)) {
-      return true;
-    }
+  if (static_type.IsNullType()) {
+    // There are only three instances that can be of Class Null:
+    // Object::null(), Object::sentinel(), and Object::transition_sentinel().
+    // The inline code and run time code performing the type check will never
+    // encounter the 2 sentinel values. The type check of a sentinel value
+    // will always be eliminated here, because these sentinel values can only
+    // be encountered as constants, never as actual value of a heap object
+    // being type checked.
+    return true;
+  }
+  Error& malformed_error = Error::Handle();
+  if (!dst_type.IsMalformed() &&
+      static_type.IsSubtypeOf(dst_type, &malformed_error)) {
+    return true;
   }
 
   return false;
 }
 
 
 // <Expression> :: Assignable { expr:     <Expression>
 //                              type:     AbstractType
 //                              dst_name: String }
 void EffectGraphVisitor::VisitAssignableNode(AssignableNode* node) {
@@ skipping 217 matching lines @@
                                dst_type,
                                dst_name);
   AddInstruction(new DoInstr(assert_assignable));
 }
 
 
 Value* EffectGraphVisitor::BuildAssignableValue(AstNode* value_node,
                                                 Value* value,
                                                 const AbstractType& dst_type,
                                                 const String& dst_name) {
-  if (CanSkipTypeCheck(value_node, dst_type)) {
+  if (CanSkipTypeCheck(value, dst_type)) {
     return value;
   }
 
   // Build the type check computation.
   Value* instantiator_type_arguments = NULL;
   if (!dst_type.IsInstantiated()) {
     instantiator_type_arguments =
         BuildInstantiatorTypeArguments(value_node->token_index());
   }
   BindInstr* assert_assignable =
@@ skipping 887 matching lines @@
   // 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);
 
   BindInstr* load =
       new BindInstr(new NativeLoadFieldComp(
                         for_instantiator.value(),
-                        type_arguments_instance_field_offset));
+                        type_arguments_instance_field_offset,
+                        Type::ZoneHandle()));  // Not an instance, no type.
   AddInstruction(load);
   return new UseVal(load);
 }
 
 
 Definition* EffectGraphVisitor::BuildInstantiatedTypeArguments(
     intptr_t token_index,
     const AbstractTypeArguments& type_arguments) {
   if (type_arguments.IsNull() || type_arguments.IsInstantiated()) {
     BindInstr* type_args =
@@ skipping 329 matching lines @@
 bool EffectGraphVisitor::MustSaveRestoreContext(SequenceNode* node) const {
   return (node == owner()->parsed_function().node_sequence()) &&
          (owner()->parsed_function().saved_context_var() != NULL);
 }
 
 
 void EffectGraphVisitor::UnchainContext() {
   BindInstr* context = new BindInstr(new CurrentContextComp());
   AddInstruction(context);
   BindInstr* parent =
-      new BindInstr(new NativeLoadFieldComp(
-                        new UseVal(context), Context::parent_offset()));
+      new BindInstr(
+          new NativeLoadFieldComp(
+              new UseVal(context),
+              Context::parent_offset(),
+              Type::ZoneHandle()));  // Not an instance, no type.
   AddInstruction(parent);
   AddInstruction(new DoInstr(new StoreContextComp(new UseVal(parent))));
 }
 
 
 // <Statement> ::= Sequence { scope: LocalScope
 //                            nodes: <Statement>*
 //                            label: SourceLabel }
 void EffectGraphVisitor::VisitSequenceNode(SequenceNode* node) {
   LocalScope* scope = node->scope();
@@ skipping 70 matching lines @@
           Computation* clear_local =
               BuildStoreLocal(*temp_local, new UseVal(null_constant));
           AddInstruction(new DoInstr(clear_local));
         }
       }
     }
   }
 
   if (FLAG_enable_type_checks &&
       (node == owner()->parsed_function().node_sequence())) {
-    const int num_params =
-        owner()->parsed_function().function().NumberOfParameters();
-    for (int pos = 0; pos < num_params; pos++) {
+    const Function& function = owner()->parsed_function().function();
+    const int num_params = function.NumberOfParameters();
+    int pos = 0;
+    if (function.IsConstructor()) {
+      // Skip type checking of receiver and phase for constructor functions.
+      pos = 2;
+    } else if (function.IsFactory() || function.IsDynamicFunction()) {
+      // Skip type checking of type arguments for factory functions.
+      // Skip type checking of receiver for instance functions.
+      pos = 1;
+    }
+    while (pos < num_params) {
       const LocalVariable& parameter = *scope->VariableAt(pos);
       ASSERT(parameter.owner() == scope);
       if (!CanSkipTypeCheck(NULL, parameter.type())) {
         BindInstr* load = new BindInstr(BuildLoadLocal(parameter));
         AddInstruction(load);
         BuildAssertAssignable(parameter.token_index(),
                               new UseVal(load),
                               parameter.type(),
                               parameter.name());
       }
+      pos++;
     }
   }
 
   intptr_t i = 0;
   while (is_open() && (i < node->length())) {
     EffectGraphVisitor for_effect(owner(), temp_index());
     node->NodeAt(i++)->Visit(&for_effect);
     Append(for_effect);
     if (!is_open()) {
       // E.g., because of a JumpNode.
@@ skipping 324 matching lines @@
   char* chars = reinterpret_cast<char*>(
       Isolate::Current()->current_zone()->Allocate(len));
   OS::SNPrint(chars, len, kFormat, function_name, reason);
   const Error& error = Error::Handle(
       LanguageError::New(String::Handle(String::New(chars))));
   Isolate::Current()->long_jump_base()->Jump(1, error);
 }
 
 
 }  // namespace dart