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

runtime/vm/jit_optimizer.cc

Index: runtime/vm/jit_optimizer.cc
diff --git a/runtime/vm/jit_optimizer.cc b/runtime/vm/jit_optimizer.cc
index cfd3fd4c2286d533b505fc74f4afa52509566bf9..2597fb61896c94b65de3fe45c47455b0b771d8ba 100644
--- a/runtime/vm/jit_optimizer.cc
+++ b/runtime/vm/jit_optimizer.cc
@@ -1476,6 +1476,94 @@ void JitOptimizer::ReplaceWithTypeCast(InstanceCallInstr* call) {
 }
 
 
+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) {
@@ -1498,19 +1586,6 @@ void JitOptimizer::VisitInstanceCall(InstanceCallInstr* instr) {
   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;
   }
@@ -1546,6 +1621,10 @@ void JitOptimizer::VisitInstanceCall(InstanceCallInstr* 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) {
@@ -1575,22 +1654,19 @@ void JitOptimizer::VisitInstanceCall(InstanceCallInstr* instr) {
     }
   }
 
-  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());
 }