[vm/kernel/aot] Fix infinite looping in TFA (ensure convergence of analysis)
Change-Id: If4fe0d6522271880b4bf8d0957ca07ef1f038a90
Reviewed-on: https://dart-review.googlesource.com/53525
Reviewed-by: Zach Anderson <zra@google.com>
Reviewed-by: Vyacheslav Egorov <vegorov@google.com>
Reviewed-by: Martin Kustermann <kustermann@google.com>
Commit-Queue: Alexander Markov <alexmarkov@google.com>
diff --git a/pkg/vm/lib/transformations/type_flow/analysis.dart b/pkg/vm/lib/transformations/type_flow/analysis.dart
index 99a885c..71ee83e 100644
--- a/pkg/vm/lib/transformations/type_flow/analysis.dart
+++ b/pkg/vm/lib/transformations/type_flow/analysis.dart
@@ -7,6 +7,7 @@
import 'dart:collection';
import 'dart:core' hide Type;
+import 'dart:math' show max;
import 'package:kernel/ast.dart' hide Statement, StatementVisitor;
import 'package:kernel/class_hierarchy.dart' show ClosedWorldClassHierarchy;
@@ -55,6 +56,12 @@
void invalidateDependentInvocations(_WorkList workList) {
if (_dependentInvocations != null) {
+ if (kPrintTrace) {
+ tracePrint(' - CHANGED: $this');
+ for (var di in _dependentInvocations) {
+ tracePrint(' - invalidating $di');
+ }
+ }
_dependentInvocations.forEach(workList.invalidateInvocation);
}
}
@@ -77,6 +84,13 @@
/// result or not (to avoid invalidation of callers if result hasn't changed).
Type invalidatedResult;
+ /// Number of times result of this invocation was invalidated.
+ int invalidationCounter = 0;
+
+ /// If an invocation is invalidated more than [invalidationLimit] times,
+ /// its result is saturated in order to guarantee convergence.
+ static const int invalidationLimit = 1000;
+
Type process(TypeFlowAnalysis typeFlowAnalysis);
_Invocation(this.selector, this.args);
@@ -320,6 +334,9 @@
.getInvocation(directSelector, directArgs);
type = typeFlowAnalysis.workList.processInvocation(directInvocation);
+ if (kPrintTrace) {
+ tracePrint('Dispatch: $directInvocation, result: $type');
+ }
// Result of this invocation depends on the results of direct
// invocations corresponding to each target.
@@ -672,7 +689,9 @@
newValue.intersection(staticType, typeFlowAnalysis.hierarchyCache),
typeFlowAnalysis.hierarchyCache);
if (newType != value) {
- tracePrint("Set field $field value $newType");
+ if (kPrintTrace) {
+ tracePrint("Set field $field value $newType");
+ }
invalidateDependentInvocations(typeFlowAnalysis.workList);
value = newType;
}
@@ -866,7 +885,9 @@
@override
Type specializeTypeCone(DartType base) {
- tracePrint("specializeTypeCone for $base");
+ if (kPrintTrace) {
+ tracePrint("specializeTypeCone for $base");
+ }
Statistics.typeConeSpecializations++;
// TODO(alexmarkov): handle function types properly
@@ -1009,7 +1030,7 @@
callStack.add(invocation);
pending.remove(invocation);
- final Type result = invocation.process(_typeFlowAnalysis);
+ Type result = invocation.process(_typeFlowAnalysis);
assertx(result != null);
invocation.result = result;
@@ -1017,6 +1038,21 @@
if (invocation.invalidatedResult != null) {
if (invocation.invalidatedResult != result) {
invocation.invalidateDependentInvocations(this);
+
+ invocation.invalidationCounter++;
+ Statistics.maxInvalidationsPerInvocation = max(
+ Statistics.maxInvalidationsPerInvocation,
+ invocation.invalidationCounter);
+ // In rare cases, loops in dependencies and approximation of
+ // recursive invocations may cause infinite bouncing of result
+ // types. To prevent infinite looping and guarantee convergence of
+ // the analysis, result is saturated after invocation is invalidated
+ // at least [_Invocation.invalidationLimit] times.
+ if (invocation.invalidationCounter > _Invocation.invalidationLimit) {
+ result = result.union(
+ invocation.invalidatedResult, _typeFlowAnalysis.hierarchyCache);
+ invocation.result = result;
+ }
}
invocation.invalidatedResult = null;
}
@@ -1034,14 +1070,20 @@
processing.remove(invocation);
Statistics.invocationsProcessed++;
+ if (kPrintTrace) {
+ tracePrint('END PROCESSING $invocation, RESULT $result');
+ }
return result;
} else {
// Recursive invocation, approximate with static type.
Statistics.recursiveInvocationsApproximated++;
final staticType =
new Type.fromStatic(invocation.selector.staticReturnType);
- tracePrint(
- "Approximated recursive invocation with static type $staticType");
+ if (kPrintTrace) {
+ tracePrint(
+ "Approximated recursive invocation with static type $staticType");
+ tracePrint('END PROCESSING $invocation, RESULT $staticType');
+ }
return staticType;
}
}
@@ -1145,7 +1187,9 @@
@override
void addRawCall(Selector selector) {
- debugPrint("ADD RAW CALL: $selector");
+ if (kPrintDebug) {
+ debugPrint("ADD RAW CALL: $selector");
+ }
assertx(selector is! DynamicSelector); // TODO(alexmarkov)
applyCall(null, selector, summaryCollector.rawArguments(selector),
@@ -1154,7 +1198,9 @@
@override
ConcreteType addAllocatedClass(Class c) {
- debugPrint("ADD ALLOCATED CLASS: $c");
+ if (kPrintDebug) {
+ debugPrint("ADD ALLOCATED CLASS: $c");
+ }
return hierarchyCache.addAllocatedClass(c);
}
}
diff --git a/pkg/vm/lib/transformations/type_flow/utils.dart b/pkg/vm/lib/transformations/type_flow/utils.dart
index 95e4467..de0d7a0 100644
--- a/pkg/vm/lib/transformations/type_flow/utils.dart
+++ b/pkg/vm/lib/transformations/type_flow/utils.dart
@@ -75,6 +75,7 @@
static int invocationsProcessed = 0;
static int usedCachedResultsOfInvocations = 0;
static int invocationsInvalidated = 0;
+ static int maxInvalidationsPerInvocation = 0;
static int recursiveInvocationsApproximated = 0;
static int typeConeSpecializations = 0;
static int classesDropped = 0;
@@ -93,6 +94,7 @@
invocationsProcessed = 0;
usedCachedResultsOfInvocations = 0;
invocationsInvalidated = 0;
+ maxInvalidationsPerInvocation = 0;
recursiveInvocationsApproximated = 0;
typeConeSpecializations = 0;
classesDropped = 0;
@@ -112,6 +114,7 @@
${invocationsProcessed} invocations processed
${usedCachedResultsOfInvocations} times cached result of invocation is used
${invocationsInvalidated} invocations invalidated
+ ${maxInvalidationsPerInvocation} maximum invalidations per invocation
${recursiveInvocationsApproximated} recursive invocations approximated
${typeConeSpecializations} type cones specialized
${classesDropped} classes dropped
diff --git a/pkg/vm/testcases/transformations/type_flow/transformer/invalidation_cycle.dart b/pkg/vm/testcases/transformations/type_flow/transformer/invalidation_cycle.dart
new file mode 100644
index 0000000..da1f458
--- /dev/null
+++ b/pkg/vm/testcases/transformations/type_flow/transformer/invalidation_cycle.dart
@@ -0,0 +1,122 @@
+// 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.
+
+// This test carefully reproduces subtle situation when TFA fails to converge
+// unless result types are saturated.
+// * There is a loop in dependencies (or even multiple loops).
+// * There is a recursive invocation which may result in a type approximation.
+// * Invalidation of results of certain invocations cause types to bounce
+// between approximated and non-approximated results, causing more
+// self-induced invalidations.
+//
+
+class StreamSubscription {}
+
+class _BufferingStreamSubscription extends StreamSubscription {}
+
+class _BroadcastSubscription extends StreamSubscription {}
+
+abstract class Stream {
+ StreamSubscription foobar(void onData(event), {Function onError});
+}
+
+abstract class _StreamImpl extends Stream {
+ StreamSubscription foobar(void onData(data), {Function onError}) {
+ return _createSubscription();
+ }
+
+ StreamSubscription _createSubscription() {
+ return new _BufferingStreamSubscription();
+ }
+}
+
+class _ControllerStream extends _StreamImpl {
+ StreamSubscription _createSubscription() {
+ return new _BroadcastSubscription();
+ }
+}
+
+class _GeneratedStreamImpl extends _StreamImpl {}
+
+class StreamView extends Stream {
+ final Stream _stream;
+
+ StreamView(Stream stream) : _stream = stream;
+
+ StreamSubscription foobar(void onData(value), {Function onError}) {
+ return _stream.foobar(onData, onError: onError);
+ }
+}
+
+class ByteStream extends StreamView {
+ ByteStream(Stream stream) : super(stream);
+
+ super_foobar1(void onData(value)) {
+ super.foobar(onData);
+ }
+
+ super_foobar2(void onData(value)) {
+ super.foobar(onData);
+ }
+
+ super_foobar3({void onData(value), Function onError}) {
+ super.foobar(onData, onError: onError);
+ }
+
+ Stream get super_stream => super._stream;
+}
+
+class _HandleErrorStream extends Stream {
+ StreamSubscription foobar(void onData(event), {Function onError}) {
+ return new _BufferingStreamSubscription();
+ }
+}
+
+void round0() {
+ new ByteStream(new ByteStream(new _GeneratedStreamImpl()));
+}
+
+void round1({void onData(value)}) {
+ var x = new ByteStream(new ByteStream(new _GeneratedStreamImpl()));
+ x.super_foobar1(onData);
+}
+
+void round2({void onData(value), Function onError}) {
+ new _ControllerStream();
+ Stream x = new _GeneratedStreamImpl();
+ x = new ByteStream(x);
+ x.foobar(onData, onError: onError);
+}
+
+void round3({void onData(value), Function onError}) {
+ Stream x = new _GeneratedStreamImpl();
+ x = new ByteStream(x);
+ x = new _ControllerStream();
+ x.foobar(onData, onError: onError);
+}
+
+void round4({void onData(value)}) {
+ var x = new ByteStream(new _ControllerStream());
+ var y = x.super_stream;
+ var z = x._stream;
+ if (y == z) {
+ x.super_foobar2(onData);
+ }
+}
+
+void round5() {
+ var x = new ByteStream(new _GeneratedStreamImpl());
+ new _HandleErrorStream();
+ x.super_foobar3();
+}
+
+main(List<String> args) {
+ new _GeneratedStreamImpl();
+ round0();
+ round1();
+ round2();
+ round3();
+ round4();
+ round5();
+}
diff --git a/pkg/vm/testcases/transformations/type_flow/transformer/invalidation_cycle.dart.expect b/pkg/vm/testcases/transformations/type_flow/transformer/invalidation_cycle.dart.expect
new file mode 100644
index 0000000..fd8c263
--- /dev/null
+++ b/pkg/vm/testcases/transformations/type_flow/transformer/invalidation_cycle.dart.expect
@@ -0,0 +1,120 @@
+library #lib;
+import self as self;
+import "dart:core" as core;
+
+abstract class StreamSubscription extends core::Object {
+ synthetic constructor •() → void
+ : super core::Object::•()
+ ;
+}
+class _BufferingStreamSubscription extends self::StreamSubscription {
+ synthetic constructor •() → void
+ : super self::StreamSubscription::•()
+ ;
+}
+class _BroadcastSubscription extends self::StreamSubscription {
+ synthetic constructor •() → void
+ : super self::StreamSubscription::•()
+ ;
+}
+abstract class Stream extends core::Object {
+ synthetic constructor •() → void
+ : super core::Object::•()
+ ;
+ abstract method foobar((dynamic) → void onData, {core::Function onError = null}) → self::StreamSubscription;
+}
+abstract class _StreamImpl extends self::Stream {
+ synthetic constructor •() → void
+ : super self::Stream::•()
+ ;
+ method foobar([@vm.inferred-type.metadata=dart.core::Null?] (dynamic) → void onData, {[@vm.inferred-type.metadata=dart.core::Null?] core::Function onError = null}) → self::StreamSubscription {
+ return [@vm.inferred-type.metadata=!] this.{self::_StreamImpl::_createSubscription}();
+ }
+ method _createSubscription() → self::StreamSubscription {
+ return new self::_BufferingStreamSubscription::•();
+ }
+}
+class _ControllerStream extends self::_StreamImpl {
+ synthetic constructor •() → void
+ : super self::_StreamImpl::•()
+ ;
+ method _createSubscription() → self::StreamSubscription {
+ return new self::_BroadcastSubscription::•();
+ }
+}
+class _GeneratedStreamImpl extends self::_StreamImpl {
+ synthetic constructor •() → void
+ : super self::_StreamImpl::•()
+ ;
+}
+abstract class StreamView extends self::Stream {
+[@vm.inferred-type.metadata=!] final field self::Stream _stream;
+ constructor •([@vm.inferred-type.metadata=!] self::Stream stream) → void
+ : self::StreamView::_stream = stream, super self::Stream::•()
+ ;
+ method foobar([@vm.inferred-type.metadata=dart.core::Null?] (dynamic) → void onData, {[@vm.inferred-type.metadata=dart.core::Null?] core::Function onError = null}) → self::StreamSubscription {
+ return [@vm.direct-call.metadata=#lib::StreamView::_stream] [@vm.inferred-type.metadata=!] this.{self::StreamView::_stream}.{self::Stream::foobar}(onData, onError: onError);
+ }
+}
+class ByteStream extends self::StreamView {
+ constructor •([@vm.inferred-type.metadata=!] self::Stream stream) → void
+ : super self::StreamView::•(stream)
+ ;
+ method super_foobar1([@vm.inferred-type.metadata=dart.core::Null?] (dynamic) → void onData) → dynamic {
+ super.{self::StreamView::foobar}(onData);
+ }
+ method super_foobar2([@vm.inferred-type.metadata=dart.core::Null?] (dynamic) → void onData) → dynamic {
+ super.{self::StreamView::foobar}(onData);
+ }
+ method super_foobar3({[@vm.inferred-type.metadata=dart.core::Null?] (dynamic) → void onData = null, [@vm.inferred-type.metadata=dart.core::Null?] core::Function onError = null}) → dynamic {
+ super.{self::StreamView::foobar}(onData, onError: onError);
+ }
+ get super_stream() → self::Stream
+ return [@vm.inferred-type.metadata=!] super.{self::StreamView::_stream};
+}
+class _HandleErrorStream extends self::Stream {
+ synthetic constructor •() → void
+ : super self::Stream::•()
+ ;
+}
+static method round0() → void {
+ new self::ByteStream::•(new self::ByteStream::•(new self::_GeneratedStreamImpl::•()));
+}
+static method round1({[@vm.inferred-type.metadata=dart.core::Null?] (dynamic) → void onData = null}) → void {
+ self::ByteStream x = new self::ByteStream::•(new self::ByteStream::•(new self::_GeneratedStreamImpl::•()));
+ [@vm.direct-call.metadata=#lib::ByteStream::super_foobar1] x.{self::ByteStream::super_foobar1}(onData);
+}
+static method round2({[@vm.inferred-type.metadata=dart.core::Null?] (dynamic) → void onData = null, [@vm.inferred-type.metadata=dart.core::Null?] core::Function onError = null}) → void {
+ new self::_ControllerStream::•();
+ self::Stream x = new self::_GeneratedStreamImpl::•();
+ x = new self::ByteStream::•(x);
+ x.{self::Stream::foobar}(onData, onError: onError);
+}
+static method round3({[@vm.inferred-type.metadata=dart.core::Null?] (dynamic) → void onData = null, [@vm.inferred-type.metadata=dart.core::Null?] core::Function onError = null}) → void {
+ self::Stream x = new self::_GeneratedStreamImpl::•();
+ x = new self::ByteStream::•(x);
+ x = new self::_ControllerStream::•();
+ x.{self::Stream::foobar}(onData, onError: onError);
+}
+static method round4({[@vm.inferred-type.metadata=dart.core::Null?] (dynamic) → void onData = null}) → void {
+ self::ByteStream x = new self::ByteStream::•(new self::_ControllerStream::•());
+ self::Stream y = [@vm.direct-call.metadata=#lib::ByteStream::super_stream] [@vm.inferred-type.metadata=!] x.{self::ByteStream::super_stream};
+ self::Stream z = [@vm.direct-call.metadata=#lib::StreamView::_stream] [@vm.inferred-type.metadata=!] x.{self::StreamView::_stream};
+ if([@vm.direct-call.metadata=dart.core::Object::==] [@vm.inferred-type.metadata=dart.core::bool] y.{core::Object::==}(z)) {
+ [@vm.direct-call.metadata=#lib::ByteStream::super_foobar2] x.{self::ByteStream::super_foobar2}(onData);
+ }
+}
+static method round5() → void {
+ self::ByteStream x = new self::ByteStream::•(new self::_GeneratedStreamImpl::•());
+ new self::_HandleErrorStream::•();
+ [@vm.direct-call.metadata=#lib::ByteStream::super_foobar3] x.{self::ByteStream::super_foobar3}();
+}
+static method main(core::List<core::String> args) → dynamic {
+ new self::_GeneratedStreamImpl::•();
+ self::round0();
+ self::round1();
+ self::round2();
+ self::round3();
+ self::round4();
+ self::round5();
+}
