Move type check elimination from backend to graph builder in new compiler.

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/code_descriptors.h"
 #include "vm/dart_entry.h"
 #include "vm/flags.h"
@@ skipping 202 matching lines @@
         (kind == RawFunction::kConstImplicitGetter);
     const bool is_static = owner()->parsed_function().function().is_static();
     // Implicit getters do not need a type check at return, unless they compute
     // the initial value of a static field.
     if (is_static || !is_implicit_getter) {
       const AbstractType& dst_type =
           AbstractType::ZoneHandle(
               owner()->parsed_function().function().result_type());
       const String& dst_name =
           String::ZoneHandle(String::NewSymbol("function result"));
-      Value* type_arguments = NULL;
-      if (!dst_type.IsInstantiated()) {
-        type_arguments = BuildInstantiatorTypeArguments(
-            node->token_index(), for_value.temp_index());
-      }
-      AssertAssignableComp* assert =
-          new AssertAssignableComp(node->id(),
-                                   node->value()->token_index(),
-                                   owner()->try_index(),
-                                   return_value,
-                                   type_arguments,
-                                   dst_type,
-                                   dst_name);
-      AddInstruction(new BindInstr(temp_index(), assert));
-      return_value = new TempVal(temp_index());
+      return_value = BuildAssignableValue(node->id(),
+                                          node->value()->token_index(),
+                                          return_value,
+                                          dst_type,
+                                          dst_name,
+                                          temp_index());
     }
   }
 
   intptr_t current_context_level = owner()->context_level();
   ASSERT(current_context_level >= 0);
   if (owner()->parsed_function().saved_context_var() != NULL) {
     // CTX on entry was saved, but not linked as context parent.
     BuildLoadContext(*owner()->parsed_function().saved_context_var(), 0);
   } else {
     while (current_context_level-- > 0) {
@@ skipping 20 matching lines @@
 void TestGraphVisitor::VisitLiteralNode(LiteralNode* node) {
   ReturnValue(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(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;
+  }
+
+  // Eliminate the test if it can be performed successfully at compile time.
+  if ((value != NULL) && value->IsConstant()) {
+    Instance& literal_value = Instance::Handle();
+    literal_value ^= value->AsConstant()->value().raw();
+    const Class& cls = Class::Handle(literal_value.clazz());
+    if (cls.IsNullClass()) {
+      ASSERT(literal_value.IsNull() ||
+             (literal_value.raw() == Object::sentinel()) ||
+             (literal_value.raw() == Object::transition_sentinel()));

[srdjan, 2012/04/18 21:33:16]

Why is this assert needed?

[regis, 2012/04/18 21:58:31]

The assert is only to document the fact that we eliminate type checks with
sentinels as well, not just null. I have added this comment:

      // 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.

+      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;
+    }
+  }
+  return false;
+}
+
+
 // <Expression> :: Assignable { expr:     <Expression>
 //                              type:     AbstractType
 //                              dst_name: String }
 void EffectGraphVisitor::VisitAssignableNode(AssignableNode* node) {
+  UNREACHABLE();
+}
+
+
+void ValueGraphVisitor::VisitAssignableNode(AssignableNode* node) {
   ValueGraphVisitor for_value(owner(), temp_index());
   node->expr()->Visit(&for_value);
   Append(for_value);
-  Value* type_arguments = NULL;
-  if (!node->type().IsInstantiated()) {
-    type_arguments = BuildInstantiatorTypeArguments(
-        node->token_index(), for_value.temp_index());
-  }
-  AssertAssignableComp* assert_assignable =
-      new AssertAssignableComp(node->id(),
-                               node->token_index(),
-                               owner()->try_index(),
-                               for_value.value(),
-                               type_arguments,
-                               node->type(),
-                               node->dst_name());
-  ReturnComputation(assert_assignable);
+  ReturnValue(BuildAssignableValue(node->id(),
+                                   node->token_index(),
+                                   for_value.value(),
+                                   node->type(),
+                                   node->dst_name(),
+                                   temp_index()));
 }
 
 
 // <Expression> :: BinaryOp { kind:  Token::Kind
 //                            left:  <Expression>
 //                            right: <Expression> }
 void EffectGraphVisitor::VisitBinaryOpNode(BinaryOpNode* node) {
   // Operators "&&" and "||" cannot be overloaded therefore do not call
   // operator.
   if ((node->kind() == Token::kAND) || (node->kind() == Token::kOR)) {
@@ skipping 157 matching lines @@
   StaticCallComp* call =
       new StaticCallComp(node->token_index(),
                          owner()->try_index(),
                          interpol_func,
                          interpol_arg->names(),
                          values);
   ReturnComputation(call);
 }
 
 
+void EffectGraphVisitor::BuildAssertAssignable(intptr_t node_id,
+                                               intptr_t token_index,
+                                               Value* value,
+                                               const AbstractType& dst_type,
+                                               const String& dst_name,
+                                               intptr_t start_index) {
+  // We should not call this function if the type check can be skipped.
+  ASSERT(!CanSkipTypeCheck(value, dst_type));
+
+  // Build the type check computation.
+  Value* instantiator_type_arguments = NULL;
+  if (!dst_type.IsInstantiated()) {
+    instantiator_type_arguments =
+        BuildInstantiatorTypeArguments(token_index, start_index + 1);
+  }
+  AssertAssignableComp* assert_assignable =
+      new AssertAssignableComp(node_id,
+                               token_index,
+                               owner()->try_index(),
+                               value,
+                               instantiator_type_arguments,
+                               dst_type,
+                               dst_name);
+  AddInstruction(new DoInstr(assert_assignable));
+}
+
+
+Value* EffectGraphVisitor::BuildAssignableValue(intptr_t node_id,
+                                                intptr_t token_index,
+                                                Value* value,
+                                                const AbstractType& dst_type,
+                                                const String& dst_name,
+                                                intptr_t start_index) {
+  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(token_index, start_index + 1);
+  }
+  AssertAssignableComp* assert_assignable =
+      new AssertAssignableComp(node_id,
+                               token_index,
+                               owner()->try_index(),
+                               value,
+                               instantiator_type_arguments,
+                               dst_type,
+                               dst_name);
+  AddInstruction(new BindInstr(start_index, assert_assignable));
+  return new TempVal(start_index);
+}
+
+
 void EffectGraphVisitor::BuildInstanceOf(ComparisonNode* node) {
   ASSERT(Token::IsInstanceofOperator(node->kind()));
   EffectGraphVisitor for_left_value(owner(), temp_index());
   node->left()->Visit(&for_left_value);
   Append(for_left_value);
 }
 
 
 void ValueGraphVisitor::BuildInstanceOf(ComparisonNode* node) {
   ASSERT(Token::IsInstanceofOperator(node->kind()));
@@ skipping 1304 matching lines @@
   ReturnComputation(load);
 }
 
 
 // <Expression> ::= StoreLocal { local: LocalVariable
 //                               value: <Expression> }
 void EffectGraphVisitor::VisitStoreLocalNode(StoreLocalNode* node) {
   ValueGraphVisitor for_value(owner(), temp_index());
   node->value()->Visit(&for_value);
   Append(for_value);
-
-  Value* value = for_value.value();
+  Value* store_value = for_value.value();
   if (FLAG_enable_type_checks) {
-    Value* type_arguments = NULL;
-    if (!node->local().type().IsInstantiated()) {
-      type_arguments = BuildInstantiatorTypeArguments(
-          node->token_index(), for_value.temp_index());
-    }
-    AssertAssignableComp* assert_assignable =
-        new AssertAssignableComp(node->id(),
-                                 node->value()->token_index(),
-                                 owner()->try_index(),
-                                 value,
-                                 type_arguments,
-                                 node->local().type(),
-                                 node->local().name());
-    AddInstruction(new BindInstr(temp_index(), assert_assignable));
-    value = new TempVal(temp_index());
+    store_value = BuildAssignableValue(node->id(),
+                                       node->value()->token_index(),
+                                       store_value,
+                                       node->local().type(),
+                                       node->local().name(),
+                                       temp_index());
   }
-
   StoreLocalComp* store =
-      new StoreLocalComp(node->local(), value, owner()->context_level());
+      new StoreLocalComp(node->local(), store_value, owner()->context_level());
   ReturnComputation(store);
 }
 
 
 void EffectGraphVisitor::VisitLoadInstanceFieldNode(
     LoadInstanceFieldNode* node) {
   ValueGraphVisitor for_instance(owner(), temp_index());
   node->instance()->Visit(&for_instance);
   Append(for_instance);
   LoadInstanceFieldComp* load =
       new LoadInstanceFieldComp(node, for_instance.value());
   ReturnComputation(load);
 }
 
 
 void EffectGraphVisitor::VisitStoreInstanceFieldNode(
     StoreInstanceFieldNode* node) {
   ValueGraphVisitor for_instance(owner(), temp_index());
   node->instance()->Visit(&for_instance);
   Append(for_instance);
   ValueGraphVisitor for_value(owner(), for_instance.temp_index());
   node->value()->Visit(&for_value);
   Append(for_value);
   Value* store_value = for_value.value();
   if (FLAG_enable_type_checks) {
     const AbstractType& type = AbstractType::ZoneHandle(node->field().type());
-    Value* type_arguments = NULL;
-    if (!type.IsInstantiated()) {
-      type_arguments = BuildInstantiatorTypeArguments(
-          node->token_index(), for_value.temp_index());
-    }
-    AssertAssignableComp* assert_assignable =
-        new AssertAssignableComp(node->id(),
-                                 node->value()->token_index(),
-                                 owner()->try_index(),
-                                 store_value,
-                                 type_arguments,
-                                 type,
-                                 String::ZoneHandle(node->field().name()));
-    AddInstruction(new BindInstr(temp_index() + 1, assert_assignable));
-    store_value = new TempVal(temp_index() + 1);
+    const String& dst_name = String::ZoneHandle(node->field().name());
+    store_value = BuildAssignableValue(node->id(),
+                                       node->value()->token_index(),
+                                       store_value,
+                                       type,
+                                       dst_name,
+                                       for_instance.temp_index());
   }
   StoreInstanceFieldComp* store =
       new StoreInstanceFieldComp(node, for_instance.value(), store_value);
   ReturnComputation(store);
 }
 
 
 void EffectGraphVisitor::VisitLoadStaticFieldNode(LoadStaticFieldNode* node) {
   LoadStaticFieldComp* load = new LoadStaticFieldComp(node->field());
   ReturnComputation(load);
 }
 
 
 void EffectGraphVisitor::VisitStoreStaticFieldNode(StoreStaticFieldNode* node) {
   ValueGraphVisitor for_value(owner(), temp_index());
   node->value()->Visit(&for_value);
   Append(for_value);
   Value* store_value = for_value.value();
   if (FLAG_enable_type_checks) {
     const AbstractType& type = AbstractType::ZoneHandle(node->field().type());
-    Value* type_arguments = NULL;
-    if (!type.IsInstantiated()) {
-      type_arguments = BuildInstantiatorTypeArguments(
-          node->token_index(), for_value.temp_index());
-    }
-    AssertAssignableComp* assert_assignable =
-        new AssertAssignableComp(node->id(),
-                                 node->value()->token_index(),
-                                 owner()->try_index(),
-                                 store_value,
-                                 type_arguments,
-                                 type,
-                                 String::ZoneHandle(node->field().name()));
-    AddInstruction(new BindInstr(temp_index(), assert_assignable));
-    store_value = new TempVal(temp_index());
+    const String& dst_name = String::ZoneHandle(node->field().name());
+    store_value = BuildAssignableValue(node->id(),
+                                       node->value()->token_index(),
+                                       store_value,
+                                       type,
+                                       dst_name,
+                                       temp_index());
   }
   StoreStaticFieldComp* store =
       new StoreStaticFieldComp(node->field(), store_value);
   ReturnComputation(store);
 }
 
 
 void EffectGraphVisitor::VisitLoadIndexedNode(LoadIndexedNode* node) {
   ArgumentGraphVisitor for_array(owner(), temp_index());
   node->array()->Visit(&for_array);
@@ skipping 133 matching lines @@
     }
   }
 
   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 LocalVariable& parameter = *scope->VariableAt(pos);
       ASSERT(parameter.owner() == scope);
-      LoadLocalComp* load = new LoadLocalComp(parameter,
-                                              owner()->context_level());
-      AddInstruction(new BindInstr(temp_index(), load));
-      TempVal* argument_value = new TempVal(temp_index());
-      Value* type_arguments = NULL;
-      if (!parameter.type().IsInstantiated()) {
-        type_arguments = BuildInstantiatorTypeArguments(
-            node->token_index(), temp_index() + 1);
+      if (!CanSkipTypeCheck(NULL, parameter.type())) {
+        LoadLocalComp* load = new LoadLocalComp(parameter,
+                                                owner()->context_level());
+        AddInstruction(new BindInstr(temp_index(), load));
+        TempVal* argument_value = new TempVal(temp_index());
+        BuildAssertAssignable(node->id(),
+                              parameter.token_index(),
+                              argument_value,
+                              parameter.type(),
+                              parameter.name(),
+                              temp_index());
       }
-      AssertAssignableComp* assert_assignable =
-          new AssertAssignableComp(node->id(),
-                                   parameter.token_index(),
-                                   owner()->try_index(),
-                                   argument_value,
-                                   type_arguments,
-                                   parameter.type(),
-                                   parameter.name());
-      AddInstruction(new DoInstr(assert_assignable));
     }
   }
 
   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 218 matching lines @@
   OS::Print("#%s", val->value().ToCString());
 }
 
 
 void FlowGraphPrinter::VisitAssertAssignable(AssertAssignableComp* comp) {
   OS::Print("AssertAssignable(");
   comp->value()->Accept(this);
   OS::Print(", %s, '%s'",
             String::Handle(comp->dst_type().Name()).ToCString(),
             comp->dst_name().ToCString());
-  if (comp->type_arguments() != NULL) {
-    OS::Print(" (type-arg:");
-    comp->type_arguments()->Accept(this);
+  if (comp->instantiator_type_arguments() != NULL) {
+    OS::Print(" (instantiator:");
+    comp->instantiator_type_arguments()->Accept(this);
   }
   OS::Print(")");
 }
 
 
 void FlowGraphPrinter::VisitAssertBoolean(AssertBooleanComp* comp) {
   OS::Print("AssertBoolean(");
   comp->value()->Accept(this);
   OS::Print(")");
 }
@@ skipping 449 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