[vm/aot/tfa] Improve AOT compilation time (step 2 / TFA)
This change improves TFA speed by adding
* Cache of dispatch targets.
* Identical types fast path to union and intersection of set and cone
types.
* Subset fast path in the union of set types.
* More efficient ConcreteType.raw.
AOT step 2 (TFA):
app #1: 200s -> 140s (-30%)
app #2: 208s -> 150s (-27%)
Issue: https://github.com/dart-lang/sdk/issues/42442
Issue: https://github.com/dart-lang/sdk/issues/43299
b/154155290
Change-Id: Ie9039a6448a7655d2aed5f5260473c28b1d917d9
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/164480
Reviewed-by: Martin Kustermann <kustermann@google.com>
Reviewed-by: Vyacheslav Egorov <vegorov@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 48932cd..bad218c 100644
--- a/pkg/vm/lib/transformations/type_flow/analysis.dart
+++ b/pkg/vm/lib/transformations/type_flow/analysis.dart
@@ -548,9 +548,8 @@
TypeFlowAnalysis typeFlowAnalysis) {
final TFClass cls = receiver.cls;
- Member target = typeFlowAnalysis.hierarchyCache.hierarchy.getDispatchTarget(
- cls.classNode, selector.name,
- setter: selector.isSetter);
+ Member target =
+ (cls as _TFClassImpl).getDispatchTarget(selector, typeFlowAnalysis);
if (target != null) {
if (kPrintTrace) {
@@ -934,6 +933,7 @@
class _TFClassImpl extends TFClass {
final Set<_TFClassImpl> supertypes; // List of super-types including this.
final Set<_TFClassImpl> _allocatedSubtypes = new Set<_TFClassImpl>();
+ final Map<Selector, Member> _dispatchTargets = <Selector, Member>{};
final _DependencyTracker dependencyTracker = new _DependencyTracker();
/// Flag indicating if this class has a noSuchMethod() method not inherited
@@ -977,6 +977,18 @@
_specializedConeType = null; // Reset cached specialization.
}
+ Member getDispatchTarget(
+ Selector selector, TypeFlowAnalysis typeFlowAnalysis) {
+ Member target = _dispatchTargets[selector];
+ if (target == null) {
+ target = typeFlowAnalysis.hierarchyCache.hierarchy.getDispatchTarget(
+ classNode, selector.name,
+ setter: selector.isSetter);
+ _dispatchTargets[selector] = target;
+ }
+ return target;
+ }
+
String dump() => "$this {supers: $supertypes}";
}
diff --git a/pkg/vm/lib/transformations/type_flow/types.dart b/pkg/vm/lib/transformations/type_flow/types.dart
index 01c219a..e7e0c1d 100644
--- a/pkg/vm/lib/transformations/type_flow/types.dart
+++ b/pkg/vm/lib/transformations/type_flow/types.dart
@@ -25,6 +25,10 @@
/// instances specific to given [TypeHierarchy].
TFClass(this.id, this.classNode);
+ /// Returns ConcreteType corresponding to this class without
+ /// any extra attributes.
+ ConcreteType get concreteType => ConcreteType(this);
+
@override
int get hashCode => id;
@@ -457,12 +461,40 @@
return types;
}
+ bool _isSubList(List<ConcreteType> sublist, List<ConcreteType> list) {
+ int i1 = 0;
+ int i2 = 0;
+ while ((i1 < sublist.length) && (i2 < list.length)) {
+ final t1 = sublist[i1];
+ final t2 = list[i2];
+ if (identical(t1, t2)) {
+ ++i1;
+ ++i2;
+ } else if (t1.cls.id > t2.cls.id) {
+ ++i2;
+ } else {
+ return false;
+ }
+ }
+ return i1 == sublist.length;
+ }
+
@override
Type union(Type other, TypeHierarchy typeHierarchy) {
+ if (identical(this, other)) return this;
if (other.order < this.order) {
return other.union(this, typeHierarchy);
}
if (other is SetType) {
+ if (types.length >= other.types.length) {
+ if (_isSubList(other.types, types)) {
+ return this;
+ }
+ } else {
+ if (_isSubList(types, other.types)) {
+ return other;
+ }
+ }
return new SetType(_unionLists(types, other.types));
} else if (other is ConcreteType) {
return types.contains(other)
@@ -479,6 +511,7 @@
@override
Type intersection(Type other, TypeHierarchy typeHierarchy) {
+ if (identical(this, other)) return this;
if (other.order < this.order) {
return other.intersection(this, typeHierarchy);
}
@@ -559,6 +592,7 @@
@override
Type union(Type other, TypeHierarchy typeHierarchy) {
+ if (identical(this, other)) return this;
if (other.order < this.order) {
return other.union(this, typeHierarchy);
}
@@ -582,6 +616,7 @@
@override
Type intersection(Type other, TypeHierarchy typeHierarchy) {
+ if (identical(this, other)) return this;
if (other.order < this.order) {
return other.intersection(this, typeHierarchy);
}
@@ -640,7 +675,8 @@
assert(typeArgs == null || typeArgs.any((t) => t is RuntimeType));
}
- ConcreteType get raw => new ConcreteType(cls, null);
+ ConcreteType get raw => cls.concreteType;
+ bool get isRaw => typeArgs == null && constant == null;
@override
Class getConcreteClass(TypeHierarchy typeHierarchy) => cls.classNode;