Use off-heap data for class check instructions

runtime/vm/intermediate_language.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/intermediate_language.h"
 
 #include "vm/bit_vector.h"
 #include "vm/bootstrap.h"
 #include "vm/compiler.h"
 #include "vm/constant_propagator.h"
@@ skipping 124 matching lines @@
   compiler->Bailout(ToCString());
   UNREACHABLE();
 }
 
 
 bool Value::Equals(Value* other) const {
   return definition() == other->definition();
 }
 
 
-static int LowestFirst(const intptr_t* a, const intptr_t* b) {
-  return *a - *b;
-}
-
-
 CheckClassInstr::CheckClassInstr(Value* value,
                                  intptr_t deopt_id,
-                                 const ICData& unary_checks,
+                                 const CallTargets& targets,
                                  TokenPosition token_pos)
     : TemplateInstruction(deopt_id),
-      unary_checks_(unary_checks),
-      cids_(unary_checks.NumberOfChecks()),
+      targets_(targets),
       licm_hoisted_(false),
-      is_dense_switch_(IsDenseCidRange(unary_checks)),
+      is_dense_switch_(IsDenseCidRange(targets)),
       token_pos_(token_pos) {
-  ASSERT(unary_checks.IsZoneHandle());
   // Expected useful check data.
-  ASSERT(!unary_checks_.IsNull());
-  const intptr_t number_of_checks = unary_checks_.NumberOfChecks();
+  const intptr_t number_of_checks = targets.length();
   ASSERT(number_of_checks > 0);
-  ASSERT(unary_checks_.NumArgsTested() == 1);
   SetInputAt(0, value);
   // Otherwise use CheckSmiInstr.
-  ASSERT(number_of_checks != 1 ||
-         (unary_checks_.GetReceiverClassIdAt(0) != kSmiCid));
-  for (intptr_t i = 0; i < number_of_checks; ++i) {
-    cids_.Add(unary_checks.GetReceiverClassIdAt(i));
-  }
-  cids_.Sort(LowestFirst);
+  ASSERT(number_of_checks != 1 || targets[0].cid_start != targets[0].cid_end ||
+         targets[0].cid_start != kSmiCid);
 }
 
 
 bool CheckClassInstr::AttributesEqual(Instruction* other) const {
   CheckClassInstr* other_check = other->AsCheckClass();
   ASSERT(other_check != NULL);
-  const intptr_t number_of_checks = unary_checks_.NumberOfChecks();
-  if (number_of_checks != other_check->unary_checks().NumberOfChecks()) {
-    return false;
-  }
-  for (intptr_t i = 0; i < number_of_checks; ++i) {
-    // TODO(fschneider): Make sure ic_data are sorted to hit more cases.
-    if (unary_checks().GetReceiverClassIdAt(i) !=
-        other_check->unary_checks().GetReceiverClassIdAt(i)) {
-      return false;
+  return targets().Equals(other_check->targets());
+}
+
+
+bool CallTargets::AreAllChecksImmutable() const {

[Vyacheslav Egorov (Google), 2017/05/01 12:21:25]

this name is very confusing. maybe rename it to ContainsExternalizableCids(...)

[erikcorry, 2017/05/05 15:15:51]

Done.

+  for (intptr_t i = 0; i < length(); i++) {
+    for (intptr_t cid = cid_ranges_[i].cid_start; cid <= cid_ranges_[i].cid_end;
+         cid++) {
+      if (Field::IsExternalizableCid(cid)) {
+        return false;
+      }
     }
   }
   return true;
 }
 
 
-static bool AreAllChecksImmutable(const ICData& checks) {
-  const intptr_t len = checks.NumberOfChecks();
-  for (intptr_t i = 0; i < len; i++) {
-    if (checks.IsUsedAt(i)) {
-      if (Field::IsExternalizableCid(checks.GetReceiverClassIdAt(i))) {
+bool CallTargets::HasReceiverClassId(intptr_t cid) const {

[Vyacheslav Egorov (Google), 2017/05/01 12:21:25]

I think this is the same as HasClassId()?

[erikcorry, 2017/05/05 15:15:51]

Merged

+  for (int i = 0; i < length(); i++) {
+    if (cid_ranges_[i].cid_start <= cid && cid <= cid_ranges_[i].cid_end) {
+      return true;
+    }
+  }
+  return false;
+}
+
+
+bool CallTargets::Equals(const CallTargets& other) const {
+  if (length() != other.length()) return false;
+  for (int i = 0; i < length(); i++) {
+    if (cid_ranges_[i].cid_start != other.cid_ranges_[i].cid_start ||
+        cid_ranges_[i].cid_end != other.cid_ranges_[i].cid_end) {
+      return false;
+    }
+    const Function* target = cid_ranges_[i].target;
+    const Function* other_target = other.cid_ranges_[i].target;
+    if (target == NULL) {
+      if (other_target != NULL) {
+        return false;
+      }
+    } else {
+      if (other_target == NULL || target->raw() != other_target->raw()) {
         return false;
       }
     }
   }
   return true;
 }
 
 
 EffectSet CheckClassInstr::Dependencies() const {
   // Externalization of strings via the API can change the class-id.
-  return !AreAllChecksImmutable(unary_checks()) ? EffectSet::Externalization()
-                                                : EffectSet::None();
+  return targets_.AreAllChecksImmutable() ? EffectSet::None()
+                                          : EffectSet::Externalization();
 }
 
 
 EffectSet CheckClassIdInstr::Dependencies() const {
   // Externalization of strings via the API can change the class-id.
   return Field::IsExternalizableCid(cid_) ? EffectSet::Externalization()
                                           : EffectSet::None();
 }
 
 
-bool CheckClassInstr::DeoptIfNull() const {
-  if (!unary_checks().NumberOfChecksIs(1)) {
+bool CheckClassInstr::IsDeoptIfNull() const {
+  if (!targets().IsMonomorphic()) {
     return false;
   }
   CompileType* in_type = value()->Type();
-  const intptr_t cid = unary_checks().GetCidAt(0);
+  const intptr_t cid = targets().MonomorphicReceiverCid();
   // Performance check: use CheckSmiInstr instead.
   ASSERT(cid != kSmiCid);
   return in_type->is_nullable() && (in_type->ToNullableCid() == cid);
 }
 
 
 // Null object is a singleton of null-class (except for some sentinel,
 // transitional temporaries). Instead of checking against the null class only
 // we can check against null instance instead.
-bool CheckClassInstr::DeoptIfNotNull() const {
-  if (!unary_checks().NumberOfChecksIs(1)) {
+bool CheckClassInstr::IsDeoptIfNotNull() const {
+  if (!targets().IsMonomorphic()) {
     return false;
   }
-  const intptr_t cid = unary_checks().GetCidAt(0);
+  const intptr_t cid = targets().MonomorphicReceiverCid();
   return cid == kNullCid;
 }
 
 
-bool CheckClassInstr::IsDenseCidRange(const ICData& unary_checks) {
-  ASSERT(unary_checks.NumArgsTested() == 1);
+bool CheckClassInstr::IsDenseCidRange(const CallTargets& targets) {
+  const intptr_t number_of_checks = targets.length();
+  if (number_of_checks <= 2) return false;
+  intptr_t min = targets.ComputeLowestCid();
+  intptr_t max = targets.ComputeHighestCid();
+
   // TODO(fschneider): Support smis in dense cid checks.
-  if (unary_checks.GetReceiverClassIdAt(0) == kSmiCid) return false;
-  const intptr_t number_of_checks = unary_checks.NumberOfChecks();
-  if (number_of_checks <= 2) return false;
-  intptr_t max = 0;
-  intptr_t min = kIntptrMax;
-  for (intptr_t i = 0; i < number_of_checks; ++i) {
-    intptr_t cid = unary_checks.GetCidAt(i);
-    if (cid < min) min = cid;
-    if (cid > max) max = cid;
-  }
+  if (min <= kSmiCid && kSmiCid <= max) return false;

[Vyacheslav Egorov (Google), 2017/05/01 12:21:25]

this is not equivalent: it is fine to have kSmiCid between min and max as long
as it is not actually *contained* in the targets (i.e. not all cids between min
and max are contained in the targets).

[erikcorry, 2017/05/05 15:15:51]

Done.

   return (max - min) < kBitsPerWord;
 }
 
 
 bool CheckClassInstr::IsDenseSwitch() const {
   return is_dense_switch_;
 }
 
 
+intptr_t CallTargets::ComputeLowestCid() const {
+  intptr_t min = kIntptrMax;
+  for (intptr_t i = 0; i < cid_ranges_.length(); ++i) {
+    min = Utils::Minimum(min, cid_ranges_[i].cid_start);
+  }
+  return min;
+}
+
+
+intptr_t CallTargets::ComputeHighestCid() const {
+  intptr_t max = -1;
+  for (intptr_t i = 0; i < cid_ranges_.length(); ++i) {
+    max = Utils::Maximum(max, cid_ranges_[i].cid_end);
+  }
+  return max;
+}
+
+
 intptr_t CheckClassInstr::ComputeCidMask() const {
   ASSERT(IsDenseSwitch());
+  intptr_t min = targets_.ComputeLowestCid();
   intptr_t mask = 0;
-  for (intptr_t i = 0; i < cids_.length(); ++i) {
-    mask |= static_cast<intptr_t>(1) << (cids_[i] - cids_[0]);
+  for (intptr_t i = 0; i < targets_.length(); ++i) {
+    intptr_t cid_start = targets_[i].cid_start;
+    intptr_t cid_end = targets_[i].cid_start;
+    intptr_t run = (1 << (1 + cid_end - cid_start)) - 1;

[Vyacheslav Egorov (Google), 2017/05/01 12:21:24]

I don't think this works if (cid_end - cid_start + 1) = kBitsPerWord

[erikcorry, 2017/05/05 15:15:51]

Done.

+    mask |= run << (cid_start - min);
   }
   return mask;
 }
 
 
-bool CheckClassInstr::IsDenseMask(intptr_t mask) {
-  // Returns true if the mask is a continuous sequence of ones in its binary
-  // representation (i.e. no holes)
-  return mask == -1 || Utils::IsPowerOfTwo(mask + 1);
-}
-
-
 bool LoadFieldInstr::IsUnboxedLoad() const {
   return FLAG_unbox_numeric_fields && (field() != NULL) &&
          FlowGraphCompiler::IsUnboxedField(*field());
 }
 
 
 bool LoadFieldInstr::IsPotentialUnboxedLoad() const {
   return FLAG_unbox_numeric_fields && (field() != NULL) &&
          FlowGraphCompiler::IsPotentialUnboxedField(*field());
 }
@@ skipping 2264 matching lines @@
   Definition* replacement = CanonicalizeStrictCompare(this, &negated,
                                                       /* is_branch = */ false);
   if (negated && replacement->IsComparison()) {
     ASSERT(replacement != this);
     replacement->AsComparison()->NegateComparison();
   }
   return replacement;
 }
 
 
+bool CallTargets::HasClassId(intptr_t cid) const {
+  for (int i = 0; i < length(); i++) {
+    if (cid_ranges_[i].cid_start <= cid && cid <= cid_ranges_[i].cid_end) {
+      return true;
+    }
+  }
+  return false;
+}
+
+
 Instruction* CheckClassInstr::Canonicalize(FlowGraph* flow_graph) {
   const intptr_t value_cid = value()->Type()->ToCid();
   if (value_cid == kDynamicCid) {
     return this;
   }
 
-  return unary_checks().HasReceiverClassId(value_cid) ? NULL : this;
+  return targets().HasReceiverClassId(value_cid) ? NULL : this;
 }
 
 
 Instruction* CheckClassIdInstr::Canonicalize(FlowGraph* flow_graph) {
   if (value()->BindsToConstant()) {
     const Object& constant_value = value()->BoundConstant();
     if (constant_value.IsSmi() && Smi::Cast(constant_value).Value() == cid_) {
       return NULL;
     }
   }
@@ skipping 162 matching lines @@
   return a->cid_start - b->cid_start;
 }
 
 
 static int OrderByFrequency(const CidRangeTarget* a, const CidRangeTarget* b) {
   // Negative if 'a' should sort before 'b'.
   return b->count - a->count;
 }
 
 
-CallTargets* CallTargets::Create(Zone* zone, const ICData& ic_data) {
+CallTargets* CallTargets::Create(Zone* zone,
+                                 const ICData& ic_data,
+                                 int argument_number) {
+  CallTargets* targets = CreateHelper(zone, ic_data, argument_number);
+  targets->Sort(OrderById);
+  targets->MergeIntoRanges();
+  return targets;
+}
+
+
+CallTargets* CallTargets::CreateHelper(Zone* zone,
+                                       const ICData& ic_data,
+                                       int argument_number) {
+  ASSERT(argument_number < ic_data.NumArgsTested());
+
   CallTargets* targets = new (zone) CallTargets();
   if (ic_data.NumberOfChecks() == 0) return targets;
 
   Function& dummy = Function::Handle(zone);
 
   bool check_one_arg = ic_data.NumArgsTested() == 1;
 
   int checks = ic_data.NumberOfChecks();
   for (int i = 0; i < checks; i++) {
+    if (ic_data.GetCountAt(i) == 0) continue;
     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];
+      id = arg_ids[argument_number];
     }
-    Function& function = Function::ZoneHandle(zone, ic_data.GetTargetAt(i));
-    targets->Add(CidRangeTarget(id, id, &function, ic_data.GetCountAt(i)));
+    if (argument_number == 0) {
+      Function& function = Function::ZoneHandle(zone, ic_data.GetTargetAt(i));
+      targets->Add(CidRangeTarget(id, id, &function, ic_data.GetCountAt(i)));
+    } else {
+      targets->Add(CidRangeTarget(id, id, NULL, ic_data.GetCountAt(i)));
+    }
   }
+  return targets;
+}
 
+
+CallTargets* CallTargets::CreateAndExpand(Zone* zone, const ICData& ic_data) {
+  CallTargets* targets = CreateHelper(zone, ic_data, 0);
   targets->Sort(OrderById);
 
   Array& args_desc_array = Array::Handle(zone, ic_data.arguments_descriptor());
   ArgumentsDescriptor args_desc(args_desc_array);
   String& name = String::Handle(zone, ic_data.target_name());
 
   Function& fn = Function::Handle(zone);
 
   intptr_t length = targets->length();
 
@@ skipping 11 matching lines @@
       } 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;
+    ASSERT(targets->At(idx).target != NULL);
     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, name, args_desc, &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);
+  targets->MergeIntoRanges();
   return targets;
 }
 
 
+void CallTargets::MergeIntoRanges() {
+  // Merge adjacent class id ranges.
+  int dest = 0;
+  for (int src = 1; src < length(); src++) {
+    if (cid_ranges_[dest].cid_end + 1 >= cid_ranges_[src].cid_start &&
+        (cid_ranges_[dest].target == NULL ||
+         cid_ranges_[dest].target->raw() == cid_ranges_[src].target->raw())) {
+      cid_ranges_[dest].cid_end = cid_ranges_[src].cid_end;
+      cid_ranges_[dest].count += cid_ranges_[src].count;
+    } else {
+      dest++;
+      if (src != dest) cid_ranges_[dest] = cid_ranges_[src];
+    }
+  }
+  SetLength(dest + 1);
+  Sort(OrderByFrequency);
+}
+
+
 // Shared code generation methods (EmitNativeCode and
 // MakeLocationSummary). Only assembly code that can be shared across all
 // architectures can be used. Machine specific register allocation and code
 // generation is located in intermediate_language_<arch>.cc
 
 #define __ compiler->assembler()->
 
 LocationSummary* GraphEntryInstr::MakeLocationSummary(Zone* zone,
                                                       bool optimizing) const {
   UNREACHABLE();
@@ skipping 437 matching lines @@
   return cid_ranges_[0].cid_start == cid_ranges_[0].cid_end;
 }
 
 
 intptr_t CallTargets::MonomorphicReceiverCid() const {
   ASSERT(IsMonomorphic());
   return cid_ranges_[0].cid_start;
 }
 
 
-Function& CallTargets::FirstTarget() const {
+const Function& CallTargets::FirstTarget() const {
   ASSERT(length() != 0);
   ASSERT(cid_ranges_[0].target->IsZoneHandle());
   return *cid_ranges_[0].target;
 }
 
 
-Function& CallTargets::MostPopularTarget() const {
+const Function& CallTargets::MostPopularTarget() const {
   ASSERT(length() != 0);
   ASSERT(cid_ranges_[0].target->IsZoneHandle());
   for (int i = 1; i < length(); i++) {
     ASSERT(cid_ranges_[i].count <= cid_ranges_[0].count);
   }
   return *cid_ranges_[0].target;
 }
 
 
 intptr_t CallTargets::AggregateCallCount() const {
@@ skipping 229 matching lines @@
 
 void DeoptimizeInstr::EmitNativeCode(FlowGraphCompiler* compiler) {
 #if !defined(TARGET_ARCH_DBC)
   __ Jump(compiler->AddDeoptStub(deopt_id(), deopt_reason_));
 #else
   compiler->EmitDeopt(deopt_id(), deopt_reason_);
 #endif
 }
 
 
+#if !defined(TARGET_ARCH_DBC)
+void CheckClassInstr::EmitNativeCode(FlowGraphCompiler* compiler) {
+  Label* deopt = compiler->AddDeoptStub(deopt_id(), ICData::kDeoptCheckClass,
+                                        licm_hoisted_ ? ICData::kHoisted : 0);
+  if (IsNullCheck()) {
+    EmitNullCheck(compiler, deopt);
+    return;
+  }
+
+  ASSERT(!targets_.IsMonomorphic() || !targets_.HasReceiverClassId(kSmiCid));
+  Register value = locs()->in(0).reg();
+  Register temp = locs()->temp(0).reg();
+  Label is_ok;
+
+  __ BranchIfSmi(value, targets_.HasReceiverClassId(kSmiCid) ? &is_ok : deopt);
+
+  __ LoadClassId(temp, value);
+
+  if (IsDenseSwitch()) {
+    intptr_t min = targets_.ComputeLowestCid();
+    intptr_t max = targets_.ComputeHighestCid();
+    EmitDenseSwitch(compiler, min, max, ComputeCidMask(), deopt);
+  } else {
+    const intptr_t num_checks = targets_.length();
+    const bool use_near_jump = num_checks < 5;
+    int bias = 0;
+    for (intptr_t i = 0; i < num_checks; i++) {
+      intptr_t cid_start = targets_[i].cid_start;
+      intptr_t cid_end = targets_[i].cid_end;
+      if (cid_start == kSmiCid && cid_end == kSmiCid) {
+        continue;  // We already handled Smi above.
+      }
+      if (cid_start == kSmiCid) cid_start++;
+      if (cid_end == kSmiCid) cid_end--;
+      const bool is_last =
+          (i == num_checks - 1) ||
+          (i == num_checks - 2 && targets_[i + 1].cid_start == kSmiCid &&
+           targets_[i + 1].cid_end == kSmiCid);
+      bias = EmitCheckCid(compiler, bias, cid_start, cid_end, is_last, &is_ok,
+                          deopt, use_near_jump);
+    }
+  }
+  __ Bind(&is_ok);
+}
+#endif
+
+
 Environment* Environment::From(Zone* zone,
                                const GrowableArray<Definition*>& definitions,
                                intptr_t fixed_parameter_count,
                                const ParsedFunction& parsed_function) {
   Environment* env =
       new (zone) Environment(definitions.length(), fixed_parameter_count,
                              Thread::kNoDeoptId, parsed_function, NULL);
   for (intptr_t i = 0; i < definitions.length(); ++i) {
     env->values_.Add(new (zone) Value(definitions[i]));
   }
@@ skipping 617 matching lines @@
                      "native function '%s' (%" Pd " arguments) cannot be found",
                      native_name().ToCString(), function().NumParameters());
   }
   set_is_auto_scope(auto_setup_scope);
   set_native_c_function(native_function);
 }
 
 #undef __
 
 }  // namespace dart