Allow dispatch to use a range of Class-ids in tests

runtime/vm/jit_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.
 #ifndef DART_PRECOMPILED_RUNTIME
 #include "vm/jit_optimizer.h"
 
 #include "vm/bit_vector.h"
 #include "vm/branch_optimizer.h"
 #include "vm/cha.h"
 #include "vm/compiler.h"
@@ skipping 1458 matching lines @@
       return;
     }
   }
   AssertAssignableInstr* assert_as = new (Z) AssertAssignableInstr(
       call->token_pos(), new (Z) Value(left), new (Z) Value(type_args), type,
       Symbols::InTypeCast(), call->deopt_id());
   ReplaceCall(call, assert_as);
 }
 
 
+bool JitOptimizer::LookupMethodFor(int class_id,
+                                   const ArgumentsDescriptor& args_desc,
+                                   const String& name,
+                                   Function* fn_return) {
+  Class& clarse = Class::Handle(Z, I->class_table()->At(class_id));

[Vyacheslav Egorov (Google), 2017/03/10 10:31:30]

please use cls

[erikcorry, 2017/03/10 13:30:01]

Done.

+  if (clarse.IsNull()) return false;
+  if (!clarse.is_finalized()) return false;
+  Function& target_function = Function::Handle(
+      Z, Resolver::ResolveDynamicForReceiverClass(clarse, name, args_desc));
+  if (target_function.IsNull()) return false;
+  *fn_return ^= target_function.raw();
+  return true;
+}
+
+
+bool JitOptimizer::TryAddClass(const ICData& ic_data,

[Vyacheslav Egorov (Google), 2017/03/10 10:31:31]

This function is called TryAddClass but it does not actually trying to add
anything anywere, nor it uses ic_data parameter.

[erikcorry, 2017/03/10 13:30:01]

This method was removed.

+                               const Function& match,
+                               int class_id,
+                               const ArgumentsDescriptor& args_desc,
+                               const String& name) {
+  if (class_id < 0) return false;
+  if (class_id >= I->class_table()->NumCids()) return false;
+
+  RawClass* raw_class = I->class_table()->At(class_id);

[Vyacheslav Egorov (Google), 2017/03/10 10:31:30]

This seems to almost duplicate the code in the LookupMethodFor(...) maybe merge
them together and make LookupMethodFor(...) return false if class does not
exist.

[erikcorry, 2017/03/10 13:30:01]

Done.

+  if (raw_class == NULL) return false;
+  Class& try_class = Class::Handle(Z, raw_class);
+
+  if (!try_class.is_finalized()) return false;
+  if (Array::Handle(try_class.functions()).IsNull()) return false;
+  Function& target_function = Function::Handle(
+      Z, Resolver::ResolveDynamicForReceiverClass(try_class, name, args_desc));
+  if (target_function.IsNull()) return false;
+  if (target_function.raw() != match.raw()) return false;
+  return true;
+}
+
+static int OrderById(const intptr_t* a, const intptr_t* b) {
+  // Negative if 'a' should sort before 'b'.
+  return *a - *b;
+}
+
+void JitOptimizer::TryExpandClassesInIC(const ICData& ic_data) {
+  if (ic_data.NumberOfChecks() == 0) return;
+
+  Function& dummy = Function::Handle(Z);
+
+  GrowableArray<intptr_t> ids;
+  for (int i = 0; i < ic_data.NumberOfChecks(); i++) {
+    // The API works for multi dispatch ICs that check more than one argument,
+    // but we know we only check one arg here, so only the 0th element of id
+    // will be used.
+    GrowableArray<intptr_t> id;
+    ic_data.GetCheckAt(i, &id, &dummy);
+    ids.Add(id[0]);
+  }
+  ids.Sort(OrderById);
+
+  Array& args_desc_array = Array::Handle(Z, ic_data.arguments_descriptor());
+  ArgumentsDescriptor args_desc(args_desc_array);
+  String& name = String::Handle(Z, ic_data.target_name());
+
+  Function& fn = Function::Handle(Z);
+  Function& fn_high = Function::Handle(Z);
+
+  for (int cid_index = 0; cid_index < ids.length() - 1; cid_index++) {
+    int low_cid = ids[cid_index];
+    int high_cid = ids[cid_index + 1];
+    if (low_cid + 1 == high_cid) continue;
+    if (LookupMethodFor(low_cid, args_desc, name, &fn) &&
+        LookupMethodFor(high_cid, args_desc, name, &fn_high) &&
+        fn.raw() == fn_high.raw()) {
+      // Try to fill in the IC table by going downwards from a known class-id.
+      bool can_fill_in = true;
+      for (int i = low_cid + 1; i < high_cid; i++) {
+        if (!TryAddClass(ic_data, fn, i, args_desc, name)) {
+          can_fill_in = false;
+          break;
+        }
+      }
+      if (can_fill_in) {
+        for (int i = low_cid + 1; i < high_cid; i++) {
+          ic_data.AddReceiverCheck(i, fn, 0);
+        }
+      }
+    }
+  }
+}
+
 // Tries to optimize instance call by replacing it with a faster instruction
 // (e.g, binary op, field load, ..).
 void JitOptimizer::VisitInstanceCall(InstanceCallInstr* instr) {
   if (!instr->HasICData() || (instr->ic_data()->NumberOfUsedChecks() == 0)) {
     return;
   }
   const Token::Kind op_kind = instr->token_kind();
 
   // Type test is special as it always gets converted into inlined code.
   if (Token::IsTypeTestOperator(op_kind)) {
     ReplaceWithInstanceOf(instr);
     return;
   }
 
   if (Token::IsTypeCastOperator(op_kind)) {
     ReplaceWithTypeCast(instr);
     return;
   }
 
   const ICData& unary_checks =
       ICData::ZoneHandle(Z, instr->ic_data()->AsUnaryClassChecks());
 
-  const bool is_dense = CheckClassInstr::IsDenseCidRange(unary_checks);
-  const intptr_t max_checks = (op_kind == Token::kEQ)
-                                  ? FLAG_max_equality_polymorphic_checks

[Vyacheslav Egorov (Google), 2017/03/10 10:31:30]

If you killed the code, kill the flag FLAG_max_equality_polymorphic_checks.

It might be good to blame the file and see which benchmark did we think this
code helps and remeasure that benchmark. 

Might be some dart2js corner case. (Similar stuff for hashCode).

[erikcorry, 2017/03/10 13:30:01]

Killed the flag.

Original code review has no rationale.  I've kicked off a benchmark run to see. 
dart2js doesn't seem to use strings for hash keys much according to
https://github.com/dart-lang/sdk/issues/26223

[erikcorry, 2017/03/10 13:36:54]

I got confused here between the two flags. I'll check this one as well.

-                                  : FLAG_max_polymorphic_checks;
-  const intptr_t number_of_checks = unary_checks.NumberOfChecks();
-  if ((number_of_checks > max_checks) && !is_dense &&
-      flow_graph()->InstanceCallNeedsClassCheck(
-          instr, RawFunction::kRegularFunction)) {
-    // Too many checks, it will be megamorphic which needs unary checks.
-    instr->set_ic_data(&unary_checks);
-    return;
-  }
-
   if ((op_kind == Token::kASSIGN_INDEX) && TryReplaceWithIndexedOp(instr)) {
     return;
   }
   if ((op_kind == Token::kINDEX) && TryReplaceWithIndexedOp(instr)) {
     return;
   }
 
   if (op_kind == Token::kEQ && TryReplaceWithEqualityOp(instr, op_kind)) {
     return;
   }
@@ skipping 15 matching lines @@
     return;
   }
   if ((op_kind == Token::kSET) &&
       TryInlineInstanceSetter(instr, unary_checks)) {
     return;
   }
   if (TryInlineInstanceMethod(instr)) {
     return;
   }
 
+  // Now we are done trying the inlining options that benefit from only having
+  // 1 entry in the IC table.
+  TryExpandClassesInIC(unary_checks);
+
   bool has_one_target = unary_checks.HasOneTarget();
 
   if (has_one_target) {
     // Check if the single target is a polymorphic target, if it is,
     // we don't have one target.
     const Function& target = Function::Handle(Z, unary_checks.GetTargetAt(0));
     if (target.recognized_kind() == MethodRecognizer::kObjectRuntimeType) {
       has_one_target = PolymorphicInstanceCallInstr::ComputeRuntimeType(
                            unary_checks) != Type::null();
     } else {
       const bool polymorphic_target =
           MethodRecognizer::PolymorphicTarget(target);
       has_one_target = !polymorphic_target;
     }
   }
 
   if (has_one_target) {
     const Function& target = Function::Handle(Z, unary_checks.GetTargetAt(0));
     const RawFunction::Kind function_kind = target.kind();
     if (!flow_graph()->InstanceCallNeedsClassCheck(instr, function_kind)) {
       PolymorphicInstanceCallInstr* call =
           new (Z) PolymorphicInstanceCallInstr(instr, unary_checks,
                                                /* call_with_checks = */ false,
                                                /* complete = */ false);
       instr->ReplaceWith(call, current_iterator());
       return;
     }
   }
 
-  if (number_of_checks <= FLAG_max_polymorphic_checks ||
-      (has_one_target && is_dense)) {
-    bool call_with_checks;
-    if (has_one_target && FLAG_polymorphic_with_deopt) {
-      // Type propagation has not run yet, we cannot eliminate the check.
-      AddReceiverCheck(instr);
-      // Call can still deoptimize, do not detach environment from instr.
-      call_with_checks = false;
-    } else {
-      call_with_checks = true;
-    }
-    PolymorphicInstanceCallInstr* call = new (Z)
-        PolymorphicInstanceCallInstr(instr, unary_checks, call_with_checks,
-                                     /* complete = */ false);
-    instr->ReplaceWith(call, current_iterator());
+  bool call_with_checks;
+  if (has_one_target && FLAG_polymorphic_with_deopt) {
+    // Type propagation has not run yet, we cannot eliminate the check.
+    AddReceiverCheck(instr);
+    // Call can still deoptimize, do not detach environment from instr.
+    call_with_checks = false;
+  } else {
+    call_with_checks = true;
   }
+  PolymorphicInstanceCallInstr* call = new (Z)
+      PolymorphicInstanceCallInstr(instr, unary_checks, call_with_checks,
+                                   /* complete = */ false);
+  instr->ReplaceWith(call, current_iterator());
 }
 
 
 void JitOptimizer::VisitStaticCall(StaticCallInstr* call) {
   MethodRecognizer::Kind recognized_kind =
       MethodRecognizer::RecognizeKind(call->function());
   switch (recognized_kind) {
     case MethodRecognizer::kObjectConstructor:
     case MethodRecognizer::kObjectArrayAllocate:
     case MethodRecognizer::kFloat32x4Zero:
@@ skipping 233 matching lines @@
   // Discard the environment from the original instruction because the store
   // can't deoptimize.
   instr->RemoveEnvironment();
   ReplaceCall(instr, store);
   return true;
 }
 
 
 }  // namespace dart
 #endif  // DART_PRECOMPILED_RUNTIME