Copy of Issue 231383002 after hard disk crash: First step in improving instance of test for a fixed…

runtime/vm/flow_graph_optimizer.cc

 // Copyright (c) 2013, 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/cpu.h"
 #include "vm/dart_entry.h"
@@ skipping 3655 matching lines @@
                                                  intptr_t view_cid) {
   bool simd_view = (view_cid == kTypedDataFloat32x4ArrayCid) ||
                    (view_cid == kTypedDataInt32x4ArrayCid);
   if (simd_view && !ShouldInlineSimd()) {
     return false;
   }
   return TryReplaceInstanceCallWithInline(call);
 }
 
 
-// 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 {
+// If type tests specified by 'ic_data' do not depend on type arguments,
+// return mapping cid->result in 'results' (i : cid; i + 1: result).
+// If all tests yield the same result, return it otherwise return Bool::null.
+// If no mapping is possible, 'results' is empty.
+// An instance-of test returning all same results can be converted to a class
+// check.
+RawBool* FlowGraphOptimizer::InstanceOfAsBool(
+    const ICData& ic_data,
+    const AbstractType& type,
+    ZoneGrowableArray<intptr_t>* results) const {
+  results->Clear();

[Florian Schneider, 2014/04/28 15:41:01]

Is results reused somewhere? 
Maybe just ASSERT(result->is_empty());

[srdjan, 2014/04/28 15:44:58]

Done.

   ASSERT(ic_data.num_args_tested() == 1);  // Unary checks only.
   if (!type.IsInstantiated() || type.IsMalformedOrMalbounded()) {
     return Bool::null();
   }
   const Class& type_class = Class::Handle(type.type_class());
   const intptr_t num_type_args = type_class.NumTypeArguments();
   if (num_type_args > 0) {
     // Only raw types can be directly compared, thus disregarding type
     // arguments.
     const intptr_t num_type_params = type_class.NumTypeParameters();
     const intptr_t from_index = num_type_args - num_type_params;
     const TypeArguments& type_arguments =
         TypeArguments::Handle(type.arguments());
     const bool is_raw_type = type_arguments.IsNull() ||
         type_arguments.IsRaw(from_index, num_type_params);
     if (!is_raw_type) {
       // Unknown result.
       return Bool::null();
     }
   }
+
   const ClassTable& class_table = *Isolate::Current()->class_table();
   Bool& prev = Bool::Handle();
   Class& cls = Class::Handle();
+
+  bool results_differ = false;
   for (int i = 0; i < ic_data.NumberOfChecks(); i++) {
     cls = class_table.At(ic_data.GetReceiverClassIdAt(i));
-    if (cls.NumTypeArguments() > 0) return Bool::null();
+    if (cls.NumTypeArguments() > 0) {
+      return Bool::null();
+    }
     const bool is_subtype = cls.IsSubtypeOf(TypeArguments::Handle(),
                                             type_class,
                                             TypeArguments::Handle(),
                                             NULL);
+    results->Add(cls.id());
+    results->Add(is_subtype);
     if (prev.IsNull()) {
       prev = Bool::Get(is_subtype).raw();
     } else {
-      if (is_subtype != prev.value()) return Bool::null();
+      if (is_subtype != prev.value()) {
+        results_differ = true;
+      }
     }
   }
-  return prev.raw();
+  return results_differ ?  Bool::null() : prev.raw();
 }
 
 
 static Definition* OriginalDefinition(Definition* defn) {
   while (defn->IsRedefinition() || defn->IsAssertAssignable()) {
     if (defn->IsRedefinition()) {
       defn = defn->AsRedefinition()->value()->definition();
     } else {
       defn = defn->AsAssertAssignable()->value()->definition();
     }
@@ skipping 24 matching lines @@
     const TypeArguments& type_arguments =
         TypeArguments::Handle(type.arguments());
     const bool is_raw_type = type_arguments.IsNull() ||
         type_arguments.IsRaw(from_index, num_type_params);
     return is_raw_type;
   }
   return true;
 }
 
 
+static bool CidTestResultsContains(const ZoneGrowableArray<intptr_t>& results,
+                                   intptr_t test_cid) {
+  for (intptr_t i = 0; i < results.length(); i += 2) {
+    if (results[i] == test_cid) return true;
+  }
+  return false;
+}
+
+
+static void TryAddTest(ZoneGrowableArray<intptr_t>* results,
+                       intptr_t test_cid,
+                       bool result) {
+  if (!CidTestResultsContains(*results, test_cid)) {
+    results->Add(test_cid);
+    results->Add(result);
+  }
+}
+
+
+// Tries to add cid tests to 'results' so that no deoptimization is
+// necessary.
+// TODO(srdjan): Do also for other than 'int' type.
+static bool TryExpandTestCidsResult(ZoneGrowableArray<intptr_t>* results,
+                                    const AbstractType& type) {
+  ASSERT(results->length() >= 2);  // At least on eentry.
+  const ClassTable& class_table = *Isolate::Current()->class_table();
+  if ((*results)[0] != kSmiCid) {
+    const Class& cls = Class::Handle(class_table.At(kSmiCid));
+    const Class& type_class = Class::Handle(type.type_class());
+    const bool smi_is_subtype = cls.IsSubtypeOf(TypeArguments::Handle(),
+                                                type_class,
+                                                TypeArguments::Handle(),
+                                                NULL);
+    results->Add((*results)[results->length() - 2]);
+    results->Add((*results)[results->length() - 2]);
+    for (intptr_t i = results->length() - 3; i > 1; --i) {
+      (*results)[i] = (*results)[i - 2];
+    }
+    (*results)[0] = kSmiCid;
+    (*results)[1] = smi_is_subtype;
+  }
+
+  ASSERT(type.IsInstantiated() && !type.IsMalformedOrMalbounded());
+  ASSERT(results->length() >= 2);
+  // const Class& type_class = Class::Handle(type.type_class())

[Florian Schneider, 2014/04/28 15:41:01]

Remove commented-out code.

[srdjan, 2014/04/28 15:44:58]

Done.

+  if (type.IsIntType()) {
+    ASSERT((*results)[0] == kSmiCid);
+    TryAddTest(results, kMintCid, true);
+    TryAddTest(results, kBigintCid, true);
+    // Cannot deoptimize since all tests returning true have been added.
+    return false;
+  }
+
+  return true;  // May deoptimize since we have not identified all 'true' tests.
+}
+
+
 // TODO(srdjan): Use ICData to check if always true or false.
 void FlowGraphOptimizer::ReplaceWithInstanceOf(InstanceCallInstr* call) {
   ASSERT(Token::IsTypeTestOperator(call->token_kind()));
   Definition* left = call->ArgumentAt(0);
   Definition* instantiator = call->ArgumentAt(1);
   Definition* type_args = call->ArgumentAt(2);
   const AbstractType& type =
       AbstractType::Cast(call->ArgumentAt(3)->AsConstant()->value());
   const bool negate = Bool::Cast(
       OriginalDefinition(call->ArgumentAt(4))->AsConstant()->value()).value();
   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()) {
+    ZoneGrowableArray<intptr_t>* results =
+        new ZoneGrowableArray<intptr_t>(unary_checks.NumberOfChecks() * 2);
+    Bool& as_bool =
+        Bool::ZoneHandle(InstanceOfAsBool(unary_checks, type, results));
+    if (as_bool.IsNull()) {
+      if (results->length() == unary_checks.NumberOfChecks() * 2) {
+        const bool can_deopt = TryExpandTestCidsResult(results, type);
+        TestCidsInstr* test_cids = new TestCidsInstr(
+            call->token_pos(),
+            negate ? Token::kISNOT : Token::kIS,
+            new Value(left),
+            *results,
+            can_deopt ? call->deopt_id() : Isolate::kNoDeoptId);
+        // Remove type.
+        ReplaceCall(call, test_cids);
+        return;
+      }
+    } else {
+      // TODO(srdjan): Use TestCidsInstr also for this case.
+      // One result only.
       AddReceiverCheck(call);
       if (negate) {
         as_bool = Bool::Get(!as_bool.value()).raw();
       }
       ConstantInstr* bool_const = flow_graph()->GetConstant(as_bool);
       for (intptr_t i = 0; i < call->ArgumentCount(); ++i) {
         PushArgumentInstr* push = call->PushArgumentAt(i);
         push->ReplaceUsesWith(push->value()->definition());
         push->RemoveFromGraph();
       }
@@ skipping 29 matching lines @@
                           new Value(left),
                           new Value(instantiator),
                           new Value(type_args),
                           type,
                           negate,
                           call->deopt_id());
   ReplaceCall(call, instance_of);
 }
 
 
+// TODO(srdjan): Apply optimizations as in ReplaceWithInstanceOf (TestCids).
 void FlowGraphOptimizer::ReplaceWithTypeCast(InstanceCallInstr* call) {
   ASSERT(Token::IsTypeCastOperator(call->token_kind()));
   Definition* left = call->ArgumentAt(0);
   Definition* instantiator = call->ArgumentAt(1);
   Definition* type_args = call->ArgumentAt(2);
   const AbstractType& type =
       AbstractType::Cast(call->ArgumentAt(3)->AsConstant()->value());
   ASSERT(!type.IsMalformedOrMalbounded());
   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));
+    ZoneGrowableArray<intptr_t>* results =
+        new ZoneGrowableArray<intptr_t>(unary_checks.NumberOfChecks() * 2);
+    const Bool& as_bool =
+        Bool::ZoneHandle(InstanceOfAsBool(unary_checks, type, results));
     if (as_bool.raw() == Bool::True().raw()) {
       AddReceiverCheck(call);
       // Remove the original push arguments.
       for (intptr_t i = 0; i < call->ArgumentCount(); ++i) {
         PushArgumentInstr* push = call->PushArgumentAt(i);
         push->ReplaceUsesWith(push->value()->definition());
         push->RemoveFromGraph();
       }
       // Remove call, replace it with 'left'.
       call->ReplaceUsesWith(left);
@@ skipping 3568 matching lines @@
                                                     Integer::Cast(right))),
           Smi::Handle(Smi::New(0)));
       SetValue(instr, result ? Bool::True() : Bool::False());
     } else {
       SetValue(instr, non_constant_);
     }
   }
 }
 
 
+void ConstantPropagator::VisitTestCids(TestCidsInstr* instr) {
+  SetValue(instr, non_constant_);
+}
+
+
 void ConstantPropagator::VisitEqualityCompare(EqualityCompareInstr* instr) {
   const Object& left = instr->left()->definition()->constant_value();
   const Object& right = instr->right()->definition()->constant_value();
 
   if (instr->left()->definition() == instr->right()->definition()) {
     // Fold x == x, and x != x to true/false for numbers comparisons.
     if (RawObject::IsIntegerClassId(instr->operation_cid())) {
       return SetValue(instr, Bool::Get(instr->kind() == Token::kEQ));
     }
   }
@@ skipping 1063 matching lines @@
   // These are the branches produced by inlining in a test context.  Also,
   // the phi has no other uses so they can simply be eliminated.  The block
   // has no other phis and no instructions intervening between the phi and
   // branch so the block can simply be eliminated.
   BranchInstr* branch = block->last_instruction()->AsBranch();
   ASSERT(branch != NULL);
   ComparisonInstr* comparison = branch->comparison();
   Value* left = comparison->left();
   PhiInstr* phi = left->definition()->AsPhi();
   Value* right = comparison->right();
-  ConstantInstr* constant = right->definition()->AsConstant();
+  ConstantInstr* constant =
+      (right == NULL) ? NULL : right->definition()->AsConstant();
   return (phi != NULL) &&
       (constant != NULL) &&
       (phi->GetBlock() == block) &&
       PhiHasSingleUse(phi, left) &&
       (block->next() == branch) &&
       (block->phis()->length() == 1);
 }
 
 
 JoinEntryInstr* BranchSimplifier::ToJoinEntry(TargetEntryInstr* target) {
@@ skipping 533 matching lines @@
   }
 
   // Insert materializations at environment uses.
   for (intptr_t i = 0; i < exits.length(); i++) {
     CreateMaterializationAt(exits[i], alloc, alloc->cls(), *slots);
   }
 }
 
 
 }  // namespace dart