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

runtime/vm/flow_graph_compiler_arm.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/globals.h"  // Needed here to get TARGET_ARCH_ARM.
 #if defined(TARGET_ARCH_ARM)
 
 #include "vm/flow_graph_compiler.h"
 
 #include "vm/ast_printer.h"
@@ skipping 1229 matching lines @@
   const Array& arguments_descriptor =
       Array::ZoneHandle(zone(), ic_data.arguments_descriptor());
   ASSERT(!arguments_descriptor.IsNull() && (arguments_descriptor.Length() > 0));
   const MegamorphicCache& cache = MegamorphicCache::ZoneHandle(
       zone(),
       MegamorphicCacheTable::Lookup(isolate(), name, arguments_descriptor));
 
   __ Comment("MegamorphicCall");
   // Load receiver into R0.
   __ LoadFromOffset(kWord, R0, SP, (argument_count - 1) * kWordSize);
-  Label done;
-  if (ShouldInlineSmiStringHashCode(ic_data)) {
-    Label megamorphic_call;
-    __ Comment("Inlined get:hashCode for Smi and OneByteString");
-    __ tst(R0, Operand(kSmiTagMask));
-    __ b(&done, EQ);  // Is Smi (result is receiver).
-
-    // Use R9 (cache for megamorphic call) as scratch.
-    __ CompareClassId(R0, kOneByteStringCid, R9);
-    __ b(&megamorphic_call, NE);
-
-    __ mov(R9, Operand(R0));  // Preserve receiver in R9.
-    __ ldr(R0, FieldAddress(R0, String::hash_offset()));
-    ASSERT(Smi::New(0) == 0);
-    __ cmp(R0, Operand(0));
-
-    __ b(&done, NE);          // Return if already computed.
-    __ mov(R0, Operand(R9));  // Restore receiver in R0.
-
-    __ Bind(&megamorphic_call);
-    __ Comment("Slow case: megamorphic call");
-  }
   __ LoadObject(R9, cache);
   __ ldr(LR, Address(THR, Thread::megamorphic_call_checked_entry_offset()));
   __ blx(LR);
 
-  __ Bind(&done);
   RecordSafepoint(locs, slow_path_argument_count);
   const intptr_t deopt_id_after = Thread::ToDeoptAfter(deopt_id);
   if (FLAG_precompiled_mode) {
     // Megamorphic calls may occur in slow path stubs.
     // If valid use try_index argument.
     if (try_index == CatchClauseNode::kInvalidTryIndex) {
       try_index = CurrentTryIndex();
     }
     AddDescriptor(RawPcDescriptors::kOther, assembler()->CodeSize(),
                   Thread::kNoDeoptId, token_pos, try_index);
@@ skipping 232 matching lines @@
 
 
 void FlowGraphCompiler::EmitTestAndCall(const ICData& ic_data,
                                         intptr_t argument_count,
                                         const Array& argument_names,
                                         Label* failed,
                                         Label* match_found,
                                         intptr_t deopt_id,
                                         TokenPosition token_index,
                                         LocationSummary* locs,
-                                        bool complete) {
+                                        bool complete,
+                                        intptr_t total_ic_calls) {
   ASSERT(is_optimizing());
   __ Comment("EmitTestAndCall");
   const Array& arguments_descriptor = Array::ZoneHandle(
       zone(), ArgumentsDescriptor::New(argument_count, argument_names));
 
   // Load receiver into R0.
   __ LoadFromOffset(kWord, R0, SP, (argument_count - 1) * kWordSize);
   __ LoadObject(R4, arguments_descriptor);
 
   const bool kFirstCheckIsSmi = ic_data.GetReceiverClassIdAt(0) == kSmiCid;
@@ skipping 25 matching lines @@
     // Receiver is Smi, but Smi is not a valid class therefore fail.
     // (Smi class must be first in the list).
     if (!complete) {
       __ tst(R0, Operand(kSmiTagMask));
       __ b(failed, EQ);
     }
   }
   __ Bind(&after_smi_test);
 
   ASSERT(!ic_data.IsNull() && (num_checks > 0));
-  GrowableArray<CidTarget> sorted(num_checks);
+  GrowableArray<CidRangeTarget> sorted(num_checks);
   SortICDataByCount(ic_data, &sorted, /* drop_smi = */ true);
 
+  const intptr_t sorted_len = sorted.length();
+  // If sorted_len is 0 then only a Smi check was needed; the Smi check above
+  // will fail if there was only one check and receiver is not Smi.
+  if (sorted_len == 0) return;
+
   // Value is not Smi,
-  const intptr_t kSortedLen = sorted.length();
-  // If kSortedLen is 0 then only a Smi check was needed; the Smi check above
-  // will fail if there was only one check and receiver is not Smi.
-  if (kSortedLen == 0) return;
+  __ LoadClassId(R2, R0);
 
-  __ LoadClassId(R2, R0);
-  for (intptr_t i = 0; i < kSortedLen; i++) {
-    const bool kIsLastCheck = (i == (kSortedLen - 1));
-    ASSERT(sorted[i].cid != kSmiCid);
+  bool add_megamorphic_call = false;
+  int bias = GetGoodBias(sorted, 256);
+  if (bias != 0) __ AddImmediate(R2, R2, -bias);
+
+  for (intptr_t i = 0; i < sorted_len; i++) {
+    const bool is_last_check = (i == (sorted_len - 1));
+    int cid_start = sorted[i].cid_start;
+    int cid_end = sorted[i].cid_end;
+    int count = sorted[i].count;
+    if (!is_last_check && !complete && count < (total_ic_calls >> 5)) {

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

Magic constants!

This is a suspect optimization because we are ignoring `fail` label - which in
JIT case would be a deopt. 

Going to megamorphic stub violates assumption that PolymorphicInstanceCall would
deoptimize if a mismatched cid is found. So if we propagate types from
PolymorphicInstanceCalls (treating them as ClassCheck-s) then we will break.

(We actually already do that in AOT just not in JIT).

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

Previous behaviour:

* If there are only a few cids we make a PolymorphicInstanceCall and we will
deopt if new cids appear
* If there are too many cids we leave it as an InstanceCall, which generates a
megamorphic call and never deopt

New behaviour:

* Either way we end up here.
* If there are a lot of different cids then we add a fallback megamorphic stub
call and never deopt.

So I think it's pretty much the same.

+      // This case is hit too rarely to be worth writing class-id checks inline
+      // for.
+      add_megamorphic_call = true;
+      break;
+    }
+    ASSERT(cid_start > kSmiCid || cid_end < kSmiCid);
     Label next_test;
-    if (!complete) {
-      __ CompareImmediate(R2, sorted[i].cid);
-      if (kIsLastCheck) {
-        __ b(failed, NE);
+    if (!complete || !is_last_check) {
+      Label* next_label = is_last_check ? failed : &next_test;
+      if (cid_start == cid_end) {
+        __ CompareImmediate(R2, cid_start - bias);
+        __ b(next_label, NE);
       } else {
-        __ b(&next_test, NE);
-      }
-    } else {
-      if (!kIsLastCheck) {
-        __ CompareImmediate(R2, sorted[i].cid);
-        __ b(&next_test, NE);
+        __ AddImmediate(R2, R2, bias - cid_start);
+        bias = cid_start;
+        __ CompareImmediate(R2, cid_end - cid_start);
+        __ b(next_label, HI);  // Unsigned higher.
       }
     }
     // Do not use the code from the function, but let the code be patched so
     // that we can record the outgoing edges to other code.
     const Function& function = *sorted[i].target;
     GenerateStaticDartCall(deopt_id, token_index,
                            *StubCode::CallStaticFunction_entry(),
                            RawPcDescriptors::kOther, locs, function);
     __ Drop(argument_count);
-    if (!kIsLastCheck) {
+    if (!is_last_check) {
       __ b(match_found);
     }
     __ Bind(&next_test);
   }
+  if (add_megamorphic_call) {
+    int try_index = CatchClauseNode::kInvalidTryIndex;
+    EmitMegamorphicInstanceCall(ic_data, argument_count, deopt_id, token_index,
+                                locs, try_index, argument_count);
+  }
 }
 
 
 #undef __
 #define __ compiler_->assembler()->
 
 
 void ParallelMoveResolver::EmitMove(int index) {
   MoveOperands* move = moves_[index];
   const Location source = move->src();
@@ skipping 282 matching lines @@
   DRegister dreg = EvenDRegisterOf(reg);
   __ vldrd(dreg, Address(SP, kDoubleSize, Address::PostIndex));
 }
 
 
 #undef __
 
 }  // namespace dart
 
 #endif  // defined TARGET_ARCH_ARM