Add --trace_type_check_elimination flag for debugging purposes.

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"
 #include "vm/flags.h"
 #include "vm/il_printer.h"
 #include "vm/intermediate_language.h"
 #include "vm/longjump.h"
 #include "vm/object_store.h"
 #include "vm/os.h"
 #include "vm/parser.h"
 #include "vm/resolver.h"
 #include "vm/stub_code.h"
 
 namespace dart {
 
 DEFINE_FLAG(bool, eliminate_type_checks, true,
-            "Eliminate type checks when allowed by static type analysis");
+            "Eliminate type checks when allowed by static type analysis.");
 DEFINE_FLAG(bool, print_ast, false, "Print abstract syntax tree.");
 DEFINE_FLAG(bool, print_flow_graph, false, "Print the IR flow graph.");
+DEFINE_FLAG(bool, trace_type_check_elimination, false,
+            "Trace type check elimination at compile time.");
 #if defined(TARGET_ARCH_X64)
 DEFINE_FLAG(bool, use_ssa, true, "Use SSA form");
 #else
 DEFINE_FLAG(bool, use_ssa, false, "Use SSA form");
 #endif
 DECLARE_FLAG(bool, enable_type_checks);
 
 
 FlowGraphBuilder::FlowGraphBuilder(const ParsedFunction& parsed_function)
   : parsed_function_(parsed_function),
@@ skipping 271 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
-// 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(!dst_type.IsNull());
-  ASSERT(dst_type.IsFinalized());
-  if (!FLAG_eliminate_type_checks) {
-    return false;
-  }
+// Helper routine returning true if the static type of the given value is more
+// specific than the given dst_type.
+static bool IsStaticTypeMoreSpecific(Value* value,
+                                     const AbstractType& dst_type) {
+  ASSERT(!dst_type.IsMalformed());
 
-  // 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())) {
+  // Any type is more specific than the Dynamic type and than the Object type.
+  if (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()) {
+    // TODO(regis): Should we perform this null test at run-time?
     return true;
   }
 
+  // Do not perform type check elimination if this optimization is turned off.
+  if (!FLAG_eliminate_type_checks) {
+    return false;
+  }
+
   // If nothing is known about the value, as is the case for passed-in
-  // parameters, the test cannot be eliminated.
+  // parameters, the type test cannot be eliminated.

[srdjan, 2012/07/07 23:06:04]

The comment is confusing as it implies how the method "IsStaticTypeMoreSpecific"
is called.  Maybe move that test to the caller instead?

[regis, 2012/07/09 16:58:53]

Moving this test to the caller would skip the tests above returning true, even
when the value is NULL. I improved the comment.

   if (value == NULL) {
     return false;
   }
 
   // Consider the static type of the value.
   const AbstractType& static_type = AbstractType::Handle(value->StaticType());
   ASSERT(!static_type.IsMalformed());
 
   // If the static type of the value is void, the only allowed value is null,
   // which must be verified by the type test.
+  // TODO(regis): Eliminate the test if the value is constant null.

[srdjan, 2012/07/07 23:06:04]

ditto

[regis, 2012/07/09 16:58:53]

ditto

   if (static_type.IsVoidType()) {
-    // TODO(regis): Eliminate the test if the value is constant null.
     return false;
   }
 
   // If the static type of the value is NullType, the type test is eliminated.
+  // 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.
   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;
   }
 
-  // The run time type of the value is guaranteed to be a subtype of the compile
-  // time static type of the value. However, establishing here that the static
-  // type is a subtype of the destination type does not guarantee that the run
-  // time type will also be a subtype of the destination type, because the
-  // subtype relation is not transitive.
-  // However, the 'more specific than' relation is transitive and is used here.
-  // In other words, if the static type of the value is more specific than the
-  // destination type, the run time type of the value, which is guaranteed to
-  // be a subtype of the static type, is also guaranteed to be a subtype of the
-  // destination type and the type check can therefore be eliminated.
+  // The run time type of the value is guaranteed to be a subtype of the
+  // compile time static type of the value. However, establishing here that
+  // the static type is a subtype of the destination type does not guarantee
+  // that the run time type will also be a subtype of the destination type,
+  // because the subtype relation is not transitive.
+  // However, the 'more specific than' relation is transitive and is used
+  // here. In other words, if the static type of the value is more specific
+  // than the destination type, the run time type of the value, which is
+  // guaranteed to be a subtype of the static type, is also guaranteed to be
+  // a subtype of the destination type and the type check can therefore be
+  // eliminated.
   Error& malformed_error = Error::Handle();
-  if (static_type.IsMoreSpecificThan(dst_type, &malformed_error)) {
-    return true;
-  }
-
-  return false;
+  return static_type.IsMoreSpecificThan(dst_type, &malformed_error);
 }
 
 
+// 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.
+bool EffectGraphVisitor::CanSkipTypeCheck(intptr_t token_pos,
+                                          Value* value,
+                                          const AbstractType& dst_type,
+                                          const String& dst_name) {
+  ASSERT(!dst_type.IsNull());
+  ASSERT(dst_type.IsFinalized());
+
+  // If the destination type is malformed, a dynamic type error must be thrown
+  // at run time.
+  if (dst_type.IsMalformed()) {
+    return false;
+  }
+
+  const bool eliminated = IsStaticTypeMoreSpecific(value, dst_type);
+  if (FLAG_eliminate_type_checks && FLAG_trace_type_check_elimination) {
+    const Class& cls = Class::Handle(
+        owner()->parsed_function().function().owner());
+    const Script& script = Script::Handle(cls.script());
+    const char* static_type_name = "unknown";
+    if (value != NULL) {
+      const AbstractType& type = AbstractType::Handle(value->StaticType());
+      static_type_name = String::Handle(type.Name()).ToCString();
+    }
+    Parser::PrintMessage(script, token_pos, "",
+                         "%s type check: static type '%s' is %s specific than "
+                         "type '%s' of '%s'.",
+                         eliminated ? "Eliminated" : "Generated",
+                         static_type_name,
+                         eliminated ? "more" : "not more",
+                         String::Handle(dst_type.Name()).ToCString(),
+                         dst_name.ToCString());
+  }
+  return eliminated;
+}
+
+
 // <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());
@@ skipping 260 matching lines @@
                                   dst_type,
                                   dst_name);
 }
 
 
 // Used for type casts and to test assignments.
 Value* EffectGraphVisitor::BuildAssignableValue(intptr_t token_pos,
                                                 Value* value,
                                                 const AbstractType& dst_type,
                                                 const String& dst_name) {
-  if (CanSkipTypeCheck(value, dst_type)) {
+  if (CanSkipTypeCheck(token_pos, value, dst_type, dst_name)) {
     return value;
   }
   AssertAssignableComp* comp = BuildAssertAssignable(token_pos,
                                                      value,
                                                      dst_type,
                                                      dst_name);
   BindInstr* assert_assignable = new BindInstr(comp);
   AddInstruction(assert_assignable);
   return new UseVal(assert_assignable);
 }
 
 
 void EffectGraphVisitor::BuildTypeTest(ComparisonNode* node) {
   ASSERT(Token::IsTypeTestOperator(node->kind()));
   EffectGraphVisitor for_left_value(owner(), temp_index());
   node->left()->Visit(&for_left_value);
   Append(for_left_value);
 }
 
 
 void EffectGraphVisitor::BuildTypeCast(ComparisonNode* node) {
   ASSERT(Token::IsTypeCastOperator(node->kind()));
   const AbstractType& type = node->right()->AsTypeNode()->type();
   ASSERT(type.IsFinalized());  // The type in a type cast may be malformed.
   ValueGraphVisitor for_value(owner(), temp_index());
   node->left()->Visit(&for_value);
   Append(for_value);
   const String& dst_name = String::ZoneHandle(
       String::NewSymbol(Exceptions::kCastExceptionDstName));
-  if (!CanSkipTypeCheck(for_value.value(), type)) {
+  if (!CanSkipTypeCheck(node->token_pos(), for_value.value(), type, dst_name)) {
     AssertAssignableComp* assert_assignable =
         BuildAssertAssignable(node->token_pos(),
                               for_value.value(),
                               type,
                               dst_name);
     AddInstruction(new DoInstr(assert_assignable));
   }
 }
 
 
@@ skipping 1470 matching lines @@
       // 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())) {
+      if (!CanSkipTypeCheck(parameter.token_pos(),
+                            NULL,
+                            parameter.type(),
+                            parameter.name())) {
         BindInstr* load = new BindInstr(BuildLoadLocal(parameter));
         AddInstruction(load);
         AssertAssignableComp* assert_assignable =
             BuildAssertAssignable(parameter.token_pos(),
                                   new UseVal(load),
                                   parameter.type(),
                                   parameter.name());
         AddInstruction(new DoInstr(assert_assignable));
       }
       pos++;
@@ skipping 595 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