Use off-heap data for type feedback in PolymorphicInstanceCallInstr

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 191 matching lines @@
   if (!call->with_checks()) {
     return;  // Already specialized.
   }
 
   const intptr_t receiver_cid =
       call->PushArgumentAt(0)->value()->Type()->ToCid();
   if (receiver_cid == kDynamicCid) {
     return;  // No information about receiver was infered.
   }
 
-  const ICData& ic_data = FlowGraphCompiler::TrySpecializeICDataByReceiverCid(
-      call->ic_data(), receiver_cid);
-  if (ic_data.raw() == call->ic_data().raw()) {
+  const ICData& ic_data = *call->instance_call()->ic_data();

[Vyacheslav Egorov (Google), 2017/04/10 10:59:28]

disregarding ic_data has an interesting effect on optimizations that use
"ic_data" non-traditionallly: 

e.g. when we compile 

a instanceof T 

we sometimes emit 

a._simpleInstanceOf(T)

where Object has 

_simpleInstanceOf
_simpleInstanceOfTrue(t) => true;
_simpleInstanceOfFalse(t) => false;

and on miss we cache _simpleInstanceOfTrue or _simpleInstanceOfFalse in the
ICData instead of _simpleInstanceOf itself. 

We might want to check that none of these optimizations are broken by this.

[erikcorry, 2017/04/19 15:06:40]

I'm not sure where this is happening.  If it's in ReplaceWithInstanceOf then
it's not touched.

+
+  const PolymorphicTargets* targets =
+      FlowGraphCompiler::TrySpecializeByReceiverCid(
+          Array::Handle(zone(), ic_data.arguments_descriptor()),
+          String::Handle(zone(), ic_data.target_name()), receiver_cid);
+  if (targets == NULL) {
     // No specialization.
     return;
   }
 
   const bool with_checks = false;
   const bool complete = false;
   PolymorphicInstanceCallInstr* specialized =
-      new (Z) PolymorphicInstanceCallInstr(call->instance_call(), ic_data,
+      new (Z) PolymorphicInstanceCallInstr(call->instance_call(), *targets,
                                            with_checks, complete);
   call->ReplaceWith(specialized, current_iterator());
 }
 
 
 static bool ClassIdIsOneOf(intptr_t class_id,
                            const GrowableArray<intptr_t>& class_ids) {
   for (intptr_t i = 0; i < class_ids.length(); i++) {
     ASSERT(class_ids[i] != kIllegalCid);
     if (class_ids[i] == class_id) {
@@ skipping 1204 matching lines @@
     }
   }
   AssertAssignableInstr* assert_as = new (Z) AssertAssignableInstr(
       call->token_pos(), new (Z) Value(left), new (Z) Value(type_args),
       NULL,  // TODO(regis): Pass function type arguments.
       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) {
-  if (class_id < 0) return false;
-  if (class_id >= I->class_table()->NumCids()) return false;
-
-  RawClass* raw_class = I->class_table()->At(class_id);
-  if (raw_class == NULL) return false;
-  Class& cls = Class::Handle(Z, raw_class);
-  if (cls.IsNull()) return false;
-  if (!cls.is_finalized()) return false;
-  if (Array::Handle(cls.functions()).IsNull()) return false;
-
-  Function& target_function = Function::Handle(
-      Z, Resolver::ResolveDynamicForReceiverClass(cls, name, args_desc));
-  if (target_function.IsNull()) return false;
-  *fn_return ^= target_function.raw();
-  return true;
+static int OrderById(const CidRangeTarget* a, const CidRangeTarget* b) {
+  // Negative if 'a' should sort before 'b'.
+  ASSERT(a->cid_start == a->cid_end);
+  ASSERT(b->cid_start == b->cid_end);
+  return a->cid_start - b->cid_start;
 }
 
 
-static int OrderById(const intptr_t* a, const intptr_t* b) {
+static int OrderByFrequency(const CidRangeTarget* a, const CidRangeTarget* b) {
   // Negative if 'a' should sort before 'b'.
-  return *a - *b;
+  return b->count - a->count;
 }
 
 
-void JitOptimizer::TryExpandClassesInICData(const ICData& ic_data) {
-  if (ic_data.NumberOfChecks() == 0) return;
+PolymorphicTargets* JitOptimizer::CreatePolymorphicTargets(

[Vyacheslav Egorov (Google), 2017/04/10 10:59:28]

Given that this method is used by both Aot and Jit compiler can it also go and
live on the FlowGraphCompiler?

[erikcorry, 2017/04/19 15:06:40]

Moved to static CallTargets::Create(...)

+    Zone* zone,
+    const ICData& ic_data) {
+  PolymorphicTargets* targets = new (zone) PolymorphicTargets(zone);
+  if (ic_data.NumberOfChecks() == 0) return targets;
 
-  Function& dummy = Function::Handle(Z);
+  Function& dummy = Function::Handle(zone);
 
-  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]);
+  bool check_one_arg = ic_data.NumArgsTested() == 1;
+
+  int checks = ic_data.NumberOfChecks();
+  for (int i = 0; i < checks; i++) {
+    intptr_t id = 0;
+    if (check_one_arg) {
+      ic_data.GetOneClassCheckAt(i, &id, &dummy);
+    } else {
+      // The API works for multi dispatch ICs that check more than one
+      // argument, but we know we will only check one arg here, so only the 0th
+      // element of id will be used.
+      GrowableArray<intptr_t> arg_ids;
+      ic_data.GetCheckAt(i, &arg_ids, &dummy);
+      id = arg_ids[0];
+    }
+    Function& function = Function::ZoneHandle(zone, ic_data.GetTargetAt(i));
+    targets->Add(CidRangeTarget(id, id, &function, ic_data.GetCountAt(i)));
   }
-  ids.Sort(OrderById);
 
-  Array& args_desc_array = Array::Handle(Z, ic_data.arguments_descriptor());
+  targets->Sort(OrderById);
+
+  Array& args_desc_array = Array::Handle(zone, ic_data.arguments_descriptor());
   ArgumentsDescriptor args_desc(args_desc_array);
-  String& name = String::Handle(Z, ic_data.target_name());
+  String& name = String::Handle(zone, ic_data.target_name());
 
-  Function& fn = Function::Handle(Z);
-  Function& fn_high = Function::Handle(Z);
-  Function& possible_match = Function::Handle(Z);
+  Function& fn = Function::Handle(zone);
 
-  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 (!LookupMethodFor(i, args_desc, name, &possible_match) ||
-            possible_match.raw() != fn.raw()) {
-          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);
-        }
+  intptr_t length = targets->length();
+
+  // Spread class-ids to preceding classes where a lookup yields the same
+  // method.
+  for (int idx = 0; idx < length; idx++) {
+    int lower_limit_cid = (idx == 0) ? -1 : targets->At(idx - 1).cid_end;
+    const Function& target = *targets->At(idx).target;
+    for (int i = targets->At(idx).cid_start - 1; i > lower_limit_cid; i--) {
+      if (FlowGraphCompiler::LookupMethodFor(i, args_desc, name, &fn) &&
+          fn.raw() == target.raw()) {
+        CidRangeTarget t = targets->At(idx);
+        t.cid_start = i;
+        (*targets)[idx] = t;
+      } else {
+        break;
       }
     }
   }
+  // Spread class-ids to following classes where a lookup yields the same
+  // method.
+  for (int idx = 0; idx < length; idx++) {
+    int upper_limit_cid =
+        (idx == length - 1) ? 1000000000 : targets->At(idx + 1).cid_start;
+    const Function& target = *targets->At(idx).target;
+    for (int i = targets->At(idx).cid_end + 1; i < upper_limit_cid; i++) {
+      if (FlowGraphCompiler::LookupMethodFor(i, args_desc, name, &fn) &&
+          fn.raw() == target.raw()) {
+        (*targets)[idx].cid_end = i;
+      } else {
+        break;
+      }
+    }
+  }
+  // Merge adjacent class id ranges.
+  int dest = 0;
+  for (int src = 1; src < length; src++) {
+    if (targets->At(dest).cid_end + 1 == targets->At(src).cid_start &&
+        targets->At(dest).target->raw() == targets->At(src).target->raw()) {
+      (*targets)[dest].cid_end = targets->At(src).cid_end;
+      (*targets)[dest].count += targets->At(src).count;
+    } else {
+      dest++;
+      if (src != dest) (*targets)[dest] = targets->At(src);
+    }
+  }
+  targets->SetLength(dest + 1);
+  targets->Sort(OrderByFrequency);
+  return targets;
 }
 
 // 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();
 
@@ skipping 39 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.
-  TryExpandClassesInICData(unary_checks);
+  PolymorphicTargets* targets = CreatePolymorphicTargets(Z, unary_checks);
 
-  bool has_one_target = unary_checks.HasOneTarget();
+  bool has_one_target = targets->HasSingleTarget();
 
   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();
+                           *targets) != 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,
+          new (Z) PolymorphicInstanceCallInstr(instr, *targets,
                                                /* call_with_checks = */ false,
                                                /* complete = */ false);
       instr->ReplaceWith(call, current_iterator());
       return;
     }
   }
 
   bool call_with_checks;
   if (has_one_target && FLAG_polymorphic_with_deopt) {
     // Type propagation has not run yet, we cannot eliminate the check.
+    // TODO(erikcorry): The receiver check should use the off-heap targets
+    // array, not the IC array.
     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);
+  PolymorphicInstanceCallInstr* call =
+      new (Z) PolymorphicInstanceCallInstr(instr, *targets, 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:
@@ skipping 234 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