[vm/compiler] Improved type analysis for check class.
Rationale:
Improves the analysis if instance calls need checks
(check class or check null) combined with CHA.
Bug: https://github.com/dart-lang/sdk/issues/33664
Change-Id: I0a4761f8816bf5a5aaf5d17ca56d8bf4e3b79fc3
Reviewed-on: https://dart-review.googlesource.com/64440
Commit-Queue: Aart Bik <ajcbik@google.com>
Reviewed-by: Vyacheslav Egorov <vegorov@google.com>
Reviewed-by: Alexander Markov <alexmarkov@google.com>
diff --git a/runtime/vm/compiler/aot/aot_call_specializer.cc b/runtime/vm/compiler/aot/aot_call_specializer.cc
index 93bcf21bf..b41ad00 100644
--- a/runtime/vm/compiler/aot/aot_call_specializer.cc
+++ b/runtime/vm/compiler/aot/aot_call_specializer.cc
@@ -800,7 +800,8 @@
if (has_one_target) {
RawFunction::Kind function_kind =
Function::Handle(Z, unary_checks.GetTargetAt(0)).kind();
- if (!flow_graph()->InstanceCallNeedsClassCheck(instr, function_kind)) {
+ if (flow_graph()->CheckForInstanceCall(instr, function_kind) ==
+ FlowGraph::ToCheck::kNoCheck) {
CallTargets* targets = CallTargets::Create(Z, unary_checks);
ASSERT(targets->HasSingleTarget());
const Function& target = targets->FirstTarget();
diff --git a/runtime/vm/compiler/backend/flow_graph.cc b/runtime/vm/compiler/backend/flow_graph.cc
index 1f079f6..02d00b3 100644
--- a/runtime/vm/compiler/backend/flow_graph.cc
+++ b/runtime/vm/compiler/backend/flow_graph.cc
@@ -15,6 +15,7 @@
#include "vm/compiler/frontend/flow_graph_builder.h"
#include "vm/growable_array.h"
#include "vm/object_store.h"
+#include "vm/resolver.h"
namespace dart {
@@ -416,38 +417,91 @@
return (phi->is_receiver() == PhiInstr::kReceiver);
}
-// Use CHA to determine if the call needs a class check: if the callee's
-// receiver is the same as the caller's receiver and there are no overridden
-// callee functions, then no class check is needed.
-bool FlowGraph::InstanceCallNeedsClassCheck(InstanceCallInstr* call,
- RawFunction::Kind kind) const {
+FlowGraph::ToCheck FlowGraph::CheckForInstanceCall(
+ InstanceCallInstr* call,
+ RawFunction::Kind kind) const {
if (!FLAG_use_cha_deopt && !isolate()->all_classes_finalized()) {
// Even if class or function are private, lazy class finalization
// may later add overriding methods.
- return true;
+ return ToCheck::kCheckCid;
}
- Definition* callee_receiver = call->Receiver()->definition();
- ASSERT(callee_receiver != NULL);
- if (function().IsDynamicFunction() && IsReceiver(callee_receiver)) {
- const String& name =
- (kind == RawFunction::kMethodExtractor)
- ? String::Handle(zone(),
- Field::NameFromGetter(call->function_name()))
- : call->function_name();
- const Class& cls = Class::Handle(zone(), function().Owner());
- intptr_t subclass_count = 0;
- if (!thread()->cha()->HasOverride(cls, name, &subclass_count)) {
- if (FLAG_trace_cha) {
- THR_Print(
- " **(CHA) Instance call needs no check, "
- "no overrides of '%s' '%s'\n",
- name.ToCString(), cls.ToCString());
+
+ // Best effort to get the receiver class.
+ Value* receiver = call->Receiver();
+ Class& receiver_class = Class::Handle(zone());
+ bool receiver_maybe_null = false;
+ if (function().IsDynamicFunction() && IsReceiver(receiver->definition())) {
+ // Call receiver is callee receiver: calling "this.g()" in f().
+ receiver_class = function().Owner();
+ } else if (FLAG_use_strong_mode_types && isolate()->strong()) {
+ // In strong mode, get the receiver's compile type. Note that
+ // we allow nullable types, which may result in just generating
+ // a null check rather than the more elaborate class check
+ CompileType* type = receiver->Type();
+ const AbstractType* atype = type->ToAbstractType();
+ if (atype->HasResolvedTypeClass() && !atype->IsDynamicType()) {
+ if (type->is_nullable()) {
+ receiver_maybe_null = true;
}
- thread()->cha()->AddToGuardedClasses(cls, subclass_count);
- return false;
+ receiver_class = atype->type_class();
+ if (receiver_class.is_implemented()) {
+ receiver_class = Class::null();
+ }
}
}
- return true;
+
+ // Useful receiver class information?
+ if (receiver_class.IsNull()) {
+ return ToCheck::kCheckCid;
+ } else if (FLAG_precompiled_mode && call->HasICData() &&
+ !call->ic_data()->HasReceiverClassId(receiver_class.id())) {
+ // In AOT, if the static class type does not match information
+ // found in ICData (which may be "guessed"), then bail, since
+ // subsequent code generation for inlining uses the latter.
+ // TODO(ajcbik): improve this by using the static class in AOT.
+ return ToCheck::kCheckCid;
+ }
+
+ const String& method_name =
+ (kind == RawFunction::kMethodExtractor)
+ ? String::Handle(zone(), Field::NameFromGetter(call->function_name()))
+ : call->function_name();
+
+ // If the receiver can have the null value, exclude any method
+ // that is actually valid on a null receiver.
+ if (receiver_maybe_null) {
+#ifdef TARGET_ARCH_DBC
+ // TODO(ajcbik): DBC does not support null check at all yet.
+ return ToCheck::kCheckCid;
+#else
+ const Class& null_class =
+ Class::Handle(zone(), isolate()->object_store()->null_class());
+ const Function& target = Function::Handle(
+ zone(),
+ Resolver::ResolveDynamicAnyArgs(zone(), null_class, method_name));
+ if (!target.IsNull()) {
+ return ToCheck::kCheckCid;
+ }
+#endif
+ }
+
+ // Use CHA to determine if the method is not overridden by any subclass
+ // of the receiver class. Any methods that are valid when the receiver
+ // has a null value are excluded above (to avoid throwing an exception
+ // on something valid, like null.hashCode).
+ intptr_t subclass_count = 0;
+ if (!thread()->cha()->HasOverride(receiver_class, method_name,
+ &subclass_count)) {
+ if (FLAG_trace_cha) {
+ THR_Print(
+ " **(CHA) Instance call needs no class check since there "
+ "are no overrides of method '%s' on '%s'\n",
+ method_name.ToCString(), receiver_class.ToCString());
+ }
+ thread()->cha()->AddToGuardedClasses(receiver_class, subclass_count);
+ return receiver_maybe_null ? ToCheck::kCheckNull : ToCheck::kNoCheck;
+ }
+ return ToCheck::kCheckCid;
}
Instruction* FlowGraph::CreateCheckClass(Definition* to_check,
diff --git a/runtime/vm/compiler/backend/flow_graph.h b/runtime/vm/compiler/backend/flow_graph.h
index a583585..4a8e86c 100644
--- a/runtime/vm/compiler/backend/flow_graph.h
+++ b/runtime/vm/compiler/backend/flow_graph.h
@@ -183,8 +183,13 @@
return current_ssa_temp_index();
}
- bool InstanceCallNeedsClassCheck(InstanceCallInstr* call,
- RawFunction::Kind kind) const;
+ enum class ToCheck { kNoCheck, kCheckNull, kCheckCid };
+
+ // Uses CHA to determine if the called method can be overridden.
+ // Return value indicates that the call needs no check at all,
+ // just a null check, or a full class check.
+ ToCheck CheckForInstanceCall(InstanceCallInstr* call,
+ RawFunction::Kind kind) const;
Thread* thread() const { return thread_; }
Zone* zone() const { return thread()->zone(); }
diff --git a/runtime/vm/compiler/backend/inliner.cc b/runtime/vm/compiler/backend/inliner.cc
index f041b41..07c8847 100644
--- a/runtime/vm/compiler/backend/inliner.cc
+++ b/runtime/vm/compiler/backend/inliner.cc
@@ -3117,13 +3117,35 @@
flow_graph, receiver_cid, target, call,
call->Receiver()->definition(), call->token_pos(), call->ic_data(),
&entry, &last, policy)) {
- // Insert receiver class check if needed.
- if (MethodRecognizer::PolymorphicTarget(target) ||
- flow_graph->InstanceCallNeedsClassCheck(call, target.kind())) {
- Instruction* check = flow_graph->CreateCheckClass(
- call->Receiver()->definition(), *Cids::Create(Z, *call->ic_data(), 0),
- call->deopt_id(), call->token_pos());
- flow_graph->InsertBefore(call, check, call->env(), FlowGraph::kEffect);
+ // Determine if inlining instance methods needs a check.
+ FlowGraph::ToCheck check = FlowGraph::ToCheck::kNoCheck;
+ if (MethodRecognizer::PolymorphicTarget(target)) {
+ check = FlowGraph::ToCheck::kCheckCid;
+ } else {
+ check = flow_graph->CheckForInstanceCall(call, target.kind());
+ }
+
+ // Insert receiver class or null check if needed.
+ switch (check) {
+ case FlowGraph::ToCheck::kCheckCid: {
+ Instruction* check_class =
+ flow_graph->CreateCheckClass(call->Receiver()->definition(),
+ *Cids::Create(Z, *call->ic_data(), 0),
+ call->deopt_id(), call->token_pos());
+ flow_graph->InsertBefore(call, check_class, call->env(),
+ FlowGraph::kEffect);
+ break;
+ }
+ case FlowGraph::ToCheck::kCheckNull: {
+ Instruction* check_null = new (Z) CheckNullInstr(
+ call->Receiver()->CopyWithType(Z), call->function_name(),
+ call->deopt_id(), call->token_pos());
+ flow_graph->InsertBefore(call, check_null, call->env(),
+ FlowGraph::kEffect);
+ break;
+ }
+ case FlowGraph::ToCheck::kNoCheck:
+ break;
}
// Remove the original push arguments.
diff --git a/runtime/vm/compiler/call_specializer.cc b/runtime/vm/compiler/call_specializer.cc
index e6b1481..38c4791 100644
--- a/runtime/vm/compiler/call_specializer.cc
+++ b/runtime/vm/compiler/call_specializer.cc
@@ -879,13 +879,20 @@
const Field& field = Field::ZoneHandle(Z, GetField(class_ids[0], field_name));
ASSERT(!field.IsNull());
- if (flow_graph()->InstanceCallNeedsClassCheck(call,
- RawFunction::kImplicitGetter)) {
- if (FLAG_precompiled_mode) {
- return false;
- }
-
- AddReceiverCheck(call);
+ switch (
+ flow_graph()->CheckForInstanceCall(call, RawFunction::kImplicitGetter)) {
+ case FlowGraph::ToCheck::kCheckNull:
+ AddCheckNull(call->Receiver(), call->function_name(), call->deopt_id(),
+ call->env(), call);
+ break;
+ case FlowGraph::ToCheck::kCheckCid:
+ if (FLAG_precompiled_mode) {
+ return false; // AOT cannot class check
+ }
+ AddReceiverCheck(call);
+ break;
+ case FlowGraph::ToCheck::kNoCheck:
+ break;
}
InlineImplicitInstanceGetter(call, field);
return true;
@@ -942,13 +949,20 @@
const Field& field = Field::ZoneHandle(Z, GetField(class_id, field_name));
ASSERT(!field.IsNull());
- if (flow_graph()->InstanceCallNeedsClassCheck(instr,
- RawFunction::kImplicitSetter)) {
- if (FLAG_precompiled_mode) {
- return false;
- }
-
- AddReceiverCheck(instr);
+ switch (
+ flow_graph()->CheckForInstanceCall(instr, RawFunction::kImplicitSetter)) {
+ case FlowGraph::ToCheck::kCheckNull:
+ AddCheckNull(instr->Receiver(), instr->function_name(), instr->deopt_id(),
+ instr->env(), instr);
+ break;
+ case FlowGraph::ToCheck::kCheckCid:
+ if (FLAG_precompiled_mode) {
+ return false; // AOT cannot class check
+ }
+ AddReceiverCheck(instr);
+ break;
+ case FlowGraph::ToCheck::kNoCheck:
+ break;
}
if (I->use_field_guards()) {
diff --git a/runtime/vm/compiler/jit/jit_call_specializer.cc b/runtime/vm/compiler/jit/jit_call_specializer.cc
index fa0ae29..aabe9ac 100644
--- a/runtime/vm/compiler/jit/jit_call_specializer.cc
+++ b/runtime/vm/compiler/jit/jit_call_specializer.cc
@@ -132,8 +132,8 @@
if (has_one_target) {
const Function& target =
Function::ZoneHandle(Z, unary_checks.GetTargetAt(0));
- const RawFunction::Kind function_kind = target.kind();
- if (!flow_graph()->InstanceCallNeedsClassCheck(instr, function_kind)) {
+ if (flow_graph()->CheckForInstanceCall(instr, target.kind()) ==
+ FlowGraph::ToCheck::kNoCheck) {
StaticCallInstr* call = StaticCallInstr::FromCall(Z, instr, target);
instr->ReplaceWith(call, current_iterator());
return;
diff --git a/tests/standalone_2/check_class_cha_test.dart b/tests/standalone_2/check_class_cha_test.dart
new file mode 100644
index 0000000..19ed029
--- /dev/null
+++ b/tests/standalone_2/check_class_cha_test.dart
@@ -0,0 +1,66 @@
+// Copyright (c) 2018, 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.
+
+import "package:expect/expect.dart";
+
+// Class hierarchy on an abstract class
+// that defines a "next" structure.
+
+abstract class A {
+ A next;
+}
+
+class B extends A {
+ B(A n) {
+ this.next = n;
+ }
+}
+
+// Method that counts length of list.
+// With only Bs, the getter can be
+// inlined without check class.
+int countMe(A i) {
+ int x = 0;
+ while (i != null) {
+ A next = i.next;
+ x++;
+ i = next;
+ }
+ return x;
+}
+
+int doitHot(A a) {
+ // Warm up the JIT.
+ int d = 0;
+ for (int i = 0; i < 1000; i++) {
+ d += countMe(a);
+ }
+ return d;
+}
+
+// Nasty class that overrides the getter.
+class C extends A {
+ C(A n) {
+ this.next = n;
+ }
+ // New override.
+ A get next => null;
+}
+
+int bringInC(A a) {
+ // Introduce C to compiler.
+ a = new C(a);
+ return doitHot(a);
+}
+
+main() {
+ // Make a list with just Bs.
+ A a = null;
+ for (int i = 0; i < 1000; i++) {
+ a = new B(a);
+ }
+
+ Expect.equals(1000 * 1000, doitHot(a));
+ Expect.equals(1000, bringInC(a));
+}
diff --git a/tests/standalone_2/check_null_cha_test.dart b/tests/standalone_2/check_null_cha_test.dart
new file mode 100644
index 0000000..fc9c17d
--- /dev/null
+++ b/tests/standalone_2/check_null_cha_test.dart
@@ -0,0 +1,58 @@
+// Copyright (c) 2018, 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.
+
+import "package:expect/expect.dart";
+
+// A class the has a getter also provided by Object
+// (higher in the class hierarchy) and thus also the
+// Null class (besides X in the class hierarchy).
+class X {
+ int hashCode;
+ X() {
+ hashCode = 1;
+ }
+}
+
+// Use this getter on X receiver.
+int hashMe(X x) {
+ int d = 0;
+ for (int i = 0; i < 10; i++) {
+ d += x.hashCode;
+ }
+ return d;
+}
+
+// Use this getter on Null class receiver.
+// Only possible value is null.
+int hashNull(Null x) {
+ int d = 0;
+ for (int i = 0; i < 10; i++) {
+ d += x.hashCode;
+ }
+ return d;
+}
+
+main() {
+ // Warm up the JIT with just an X object. Having a single receiver
+ // of type X with nothing below in the hierarchy that overrides
+ // hashCode could tempt the JIT to inline the getter with CHA
+ // that deopts when X is subclassed in the future.
+ X x = new X();
+ for (int i = 0; i < 1000; i++) {
+ Expect.equals(10, hashMe(x));
+ }
+
+ // However, this is a special case that also works on null
+ // (calling Object's hashCode). So this should not throw an
+ // exception. Had we inlined, this would have hit the null
+ // check and thrown an exception.
+ Expect.notEquals(0, hashMe(null));
+
+ // Also warm up the JIT on a direct Null receiver.
+ int d = 0;
+ for (int i = 0; i < 1000; i++) {
+ d += hashNull(null);
+ }
+ Expect.notEquals(0, d);
+}
