Optimize instanceof: if all results are true and tests can be done using class only replace instanc…

runtime/vm/flow_graph_optimizer.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_optimizer.h"
 
 #include "vm/bit_vector.h"
 #include "vm/cha.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/flow_graph_compiler.h"
@@ skipping 1231 matching lines @@
     }
     call->ReplaceWith(d2i_instr, current_iterator());
     RemovePushArguments(call);
     return true;
   }
 
   return false;
 }
 
 
+// Returns a Boolean constant if all classes in ic_data yield the same type-test
+// result and the type tests do not depend on type arguments. Otherwise return
+// Bool::null().
+RawBool* FlowGraphOptimizer::InstanceOfAsBool(const ICData& ic_data,
+                                              const AbstractType& type) const {
+  ASSERT(ic_data.num_args_tested() == 1);  // Unary checks only.
+  if (!type.IsInstantiated() || type.IsMalformed()) return Bool::null();
+  const Class& type_class = Class::Handle(type.type_class());
+  if (type_class.HasTypeArguments()) return Bool::null();
+  const ClassTable& class_table = *Isolate::Current()->class_table();
+  Bool& prev = Bool::Handle();
+  Class& cls = Class::Handle();
+  for (int i = 0; i < ic_data.NumberOfChecks(); i++) {
+    cls = class_table.At(ic_data.GetReceiverClassIdAt(i));
+    if (cls.HasTypeArguments()) return Bool::null();
+    // TODO(regis): Fix Class::TypeTest to support NullClass.

[regis, 2013/01/04 01:39:16]

I am pretty sure that Class::TypeTest is supporting NullClass properly. There is
a difference between "is subtype of", which applies to types and "is an instance
of", which applies to instances. Class::TypeTest() implements both "is a subtype
of" or "is more specific than" (according to the flag passed in), but not "is an
instance of".
Please note that null is an instance of Object (and of dynamic), but Null is not
a subtype of Object (or of any type).
This is why Instance::IsInstanceOf handles these special cases before calling
Class::IsSubTypeOf.

[srdjan, 2013/01/04 21:10:25]

Removed TODO. Discussed off-line changes to Class::TypeTest.

+    bool is_subtype = false;
+    if (cls.IsNullClass()) {
+      is_subtype = type_class.IsDynamicClass() || type_class.IsObjectClass();
+    } else {
+      is_subtype = cls.IsSubtypeOf(TypeArguments::Handle(),
+                                   type_class,
+                                   TypeArguments::Handle(),
+                                   NULL);
+    }
+    if (prev.IsNull()) {
+      prev = is_subtype ? Bool::True() : Bool::False();
+    } else {
+      if (is_subtype != prev.value()) return Bool::null();
+    }
+  }
+  return prev.raw();
+}
+
+
 // TODO(srdjan): Use ICData to check if always true or false.
 void FlowGraphOptimizer::ReplaceWithInstanceOf(InstanceCallInstr* call) {
   ASSERT(Token::IsTypeTestOperator(call->token_kind()));
   Value* left_val = call->ArgumentAt(0)->value();
   Value* instantiator_val = call->ArgumentAt(1)->value();
   Value* type_args_val = call->ArgumentAt(2)->value();
   const AbstractType& type =
       AbstractType::Cast(call->ArgumentAt(3)->value()->BoundConstant());
   const Bool& negate =

[Florian Schneider, 2013/01/04 11:35:41]

Maybe just

bool negate =
  Bool::Cast(call->ArgumentAt(4)->value()->BoundConstant()).value()

and substitute negate.value() with just negate below.

[srdjan, 2013/01/04 21:10:25]

Done.

       Bool::Cast(call->ArgumentAt(4)->value()->BoundConstant());
+  const ICData& unary_checks =
+      ICData::ZoneHandle(call->ic_data()->AsUnaryClassChecks());
+  if (unary_checks.NumberOfChecks() <= FLAG_max_polymorphic_checks) {
+    Bool& as_bool = Bool::ZoneHandle(InstanceOfAsBool(unary_checks, type));
+    if (!as_bool.IsNull()) {
+      AddCheckClass(call, left_val->Copy());
+      if (negate.value()) {
+        as_bool = as_bool.value() ? Bool::False() : Bool::True();
+      }
+      ConstantInstr* bool_const = new ConstantInstr(as_bool);
+      call->ReplaceWith(bool_const, current_iterator());
+      RemovePushArguments(call);
+      return;
+    }
+  }
   InstanceOfInstr* instance_of =
       new InstanceOfInstr(call->token_pos(),
                           left_val,
                           instantiator_val,
                           type_args_val,
                           type,
                           negate.value());
   call->ReplaceWith(instance_of, current_iterator());
   RemovePushArguments(call);
 }
@@ skipping 3105 matching lines @@
 
   if (FLAG_trace_constant_propagation) {
     OS::Print("\n==== After constant propagation ====\n");
     FlowGraphPrinter printer(*graph_);
     printer.PrintBlocks();
   }
 }
 
 
 }  // namespace dart