Optimize `ClassHierarchyBuilder.isInheritedInSubtypeOf`.
This fixes the compile-time regression introduced by
https://dart-review.googlesource.com/c/sdk/+/72643
Change-Id: I55d441592cd710daeca980a3eb902284751575dc
Reviewed-on: https://dart-review.googlesource.com/75001
Commit-Queue: Johnni Winther <johnniwinther@google.com>
Reviewed-by: Stephen Adams <sra@google.com>
diff --git a/pkg/compiler/lib/src/compiler.dart b/pkg/compiler/lib/src/compiler.dart
index 1e2a298..be24ef3 100644
--- a/pkg/compiler/lib/src/compiler.dart
+++ b/pkg/compiler/lib/src/compiler.dart
@@ -290,6 +290,15 @@
JClosedWorld computeClosedWorld(LoadedLibraries loadedLibraries) {
ResolutionEnqueuer resolutionEnqueuer = startResolution();
+ for (LibraryEntity library
+ in frontendStrategy.elementEnvironment.libraries) {
+ frontendStrategy.elementEnvironment.forEachClass(library,
+ (ClassEntity cls) {
+ // Register all classes eagerly to optimize closed world computation in
+ // `ClassWorldBuilder.isInheritedInSubtypeOf`.
+ resolutionEnqueuer.worldBuilder.registerClass(cls);
+ });
+ }
WorldImpactBuilderImpl mainImpact = new WorldImpactBuilderImpl();
FunctionEntity mainFunction = frontendStrategy.computeMain(mainImpact);
diff --git a/pkg/compiler/lib/src/js_emitter/program_builder/program_builder.dart b/pkg/compiler/lib/src/js_emitter/program_builder/program_builder.dart
index 00cdf32..de9d367 100644
--- a/pkg/compiler/lib/src/js_emitter/program_builder/program_builder.dart
+++ b/pkg/compiler/lib/src/js_emitter/program_builder/program_builder.dart
@@ -690,7 +690,7 @@
callStubs.add(_buildStubMethod(name, function));
}
- if (_commonElements.isInstantiationClass(cls)) {
+ if (_commonElements.isInstantiationClass(cls) && !onlyForRti) {
callStubs.addAll(_generateInstantiationStubs(cls));
}
diff --git a/pkg/compiler/lib/src/library_loader.dart b/pkg/compiler/lib/src/library_loader.dart
index a941245..b4832ee 100644
--- a/pkg/compiler/lib/src/library_loader.dart
+++ b/pkg/compiler/lib/src/library_loader.dart
@@ -41,6 +41,8 @@
: initializedCompilerState = _options.kernelInitializedCompilerState,
super(measurer);
+ String get name => 'Library loader';
+
/// Loads an entire Kernel [Component] from a file on disk.
Future<LoadedLibraries> loadLibraries(Uri resolvedUri) {
return measure(() async {
diff --git a/pkg/compiler/lib/src/universe/class_hierarchy.dart b/pkg/compiler/lib/src/universe/class_hierarchy.dart
index cc91490..c351f1e 100644
--- a/pkg/compiler/lib/src/universe/class_hierarchy.dart
+++ b/pkg/compiler/lib/src/universe/class_hierarchy.dart
@@ -625,32 +625,112 @@
return classSet.hasSubtype(classHierarchyNode);
}
+ Map<ClassEntity, _InheritedCache> _inheritedCacheMap = {};
+
bool isInheritedInSubtypeOf(ClassEntity x, ClassEntity y) {
- ClassSet classSet = classSets[x];
- assert(classSet != null,
- failedAt(x, "No ClassSet for $x (${x.runtimeType}): ${classSets}"));
+ _InheritedCache cache = _inheritedCacheMap[x] ??= new _InheritedCache();
+ return cache.isInheritedInSubtypeOf(this, x, y);
+ }
+}
- if (_isSubtypeOf(x, y)) {
+/// A cache object used for [ClassHierarchyBuilder.isInheritedInSubtypeOf].
+class _InheritedCache {
+ Map<ClassEntity, _InheritingSet> _map;
+
+ /// Returns whether a live class currently known to inherit from [x] and
+ /// implement [y].
+ bool isInheritedInSubtypeOf(
+ ClassHierarchyBuilder builder, ClassEntity x, ClassEntity y) {
+ _InheritingSet set;
+ if (_map == null) {
+ _map = {};
+ } else {
+ set = _map[y];
+ }
+ if (set == null) {
+ set = _map[y] = _computeInheritingSet(builder, x, y);
+ }
+ return set.hasLiveClass(builder);
+ }
+
+ /// Creates an [_InheritingSet] of classes that inherit members of a class [x]
+ /// while implementing class [y].
+ _InheritingSet _computeInheritingSet(
+ ClassHierarchyBuilder builder, ClassEntity x, ClassEntity y) {
+ ClassSet classSet = builder.classSets[x];
+
+ assert(
+ classSet != null,
+ failedAt(
+ x, "No ClassSet for $x (${x.runtimeType}): ${builder.classSets}"));
+
+ Set<ClassEntity> classes = new Set<ClassEntity>();
+
+ if (builder._isSubtypeOf(x, y)) {
// [x] implements [y] itself, possible through supertypes.
- return true;
+ classes.add(x);
}
- /// Returns `true` if any live subclass of [node] implements [y].
- bool subclassImplements(ClassHierarchyNode node, {bool strict}) {
- return node.anySubclass((ClassEntity z) => _isSubtypeOf(z, y),
- ClassHierarchyNode.INSTANTIATED,
- strict: strict);
+ /// Add subclasses of [node] that implement [y].
+ void subclassImplements(ClassHierarchyNode node, {bool strict}) {
+ node.forEachSubclass((ClassEntity z) {
+ if (builder._isSubtypeOf(z, y)) {
+ classes.add(z);
+ }
+ }, ClassHierarchyNode.ALL, strict: strict);
}
- if (subclassImplements(classSet.node, strict: true)) {
- // A subclass of [x] implements [y].
- return true;
- }
+ // A subclasses of [x] that implement [y].
+ subclassImplements(classSet.node, strict: true);
for (ClassHierarchyNode mixinApplication
in classSet.mixinApplicationNodes) {
- if (subclassImplements(mixinApplication, strict: false)) {
- // A subclass of [mixinApplication] implements [y].
+ // A subclass of [mixinApplication] implements [y].
+ subclassImplements(mixinApplication, strict: false);
+ }
+
+ return new _InheritingSet(classes);
+ }
+}
+
+/// A set of classes that inherit members of a class 'x' while implementing
+/// class 'y'.
+///
+/// The set is used [ClassHierarchyBuilder.isInheritedInSubtypeOf] to determine
+/// when members of a class is live.
+class _InheritingSet {
+ /// If `true` the set of classes is known to contain a live class. In this
+ /// case [_classes] is `null`. If `false` the set of classes is empty and
+ /// therefore known never to contain live classes. In this case [_classes]
+ /// is `null`. If `null` [_classes] is a non-empty set containing classes
+ /// that are not yet known to be live.
+ bool _result;
+ Set<ClassEntity> _classes;
+
+ _InheritingSet(Set<ClassEntity> classes)
+ : _result = classes.isEmpty ? false : null,
+ _classes = classes.isNotEmpty ? classes : null;
+
+ /// Returns whether the set of classes is currently known to contain a live
+ /// classes.
+ ///
+ /// The result of this method changes during the closed world computation.
+ /// Initially, we haven't seen any live classes so we will return `false` even
+ /// for a non-empty set of classes. As more classes are marked as
+ /// instantiated, during tree-shaking, the result might change to `true` if
+ /// one of the [_classes] has been marked as live.
+ ///
+ /// The result of this method _is_ monotone, though; when we have returned
+ /// `true` (because at least one class is known to be live) we will continue
+ /// to return `true`.
+ bool hasLiveClass(ClassHierarchyBuilder builder) {
+ if (_result != null) return _result;
+ for (ClassEntity cls in _classes) {
+ if (builder.classHierarchyNodes[cls].isInstantiated) {
+ // We now know this set contains a live class and done need to remember
+ // that set of classes anymore.
+ _result = true;
+ _classes = null;
return true;
}
}
diff --git a/pkg/compiler/lib/src/universe/resolution_world_builder.dart b/pkg/compiler/lib/src/universe/resolution_world_builder.dart
index 6f7d4bd..b203dc9 100644
--- a/pkg/compiler/lib/src/universe/resolution_world_builder.dart
+++ b/pkg/compiler/lib/src/universe/resolution_world_builder.dart
@@ -851,7 +851,7 @@
memberUsed(usage.entity, useSet);
return usage;
});
- if (!newUsage) {
+ if (!usage.fullyUsed && !newUsage) {
EnumSet<MemberUse> useSet = new EnumSet<MemberUse>();
if (!usage.hasRead && _hasInvokedGetter(member)) {
useSet.addAll(usage.read());
@@ -945,8 +945,6 @@
bool isInheritedInSubtypeOf(MemberEntity member, ClassEntity type) {
// TODO(johnniwinther): Use the [member] itself to avoid enqueueing members
// that are overridden.
- _classHierarchyBuilder.registerClass(member.enclosingClass);
- _classHierarchyBuilder.registerClass(type);
return _classHierarchyBuilder.isInheritedInSubtypeOf(
member.enclosingClass, type);
}
@@ -972,12 +970,7 @@
Map<ClassEntity, Set<ClassEntity>> typesImplementedBySubclasses =
populateHierarchyNodes();
- var backendUsage = _backendUsageBuilder.close();
- backendUsage.helperClassesUsed
- .forEach(_classHierarchyBuilder.registerClass);
- _nativeResolutionEnqueuer.liveNativeClasses
- .forEach(_classHierarchyBuilder.registerClass);
-
+ BackendUsage backendUsage = _backendUsageBuilder.close();
_closed = true;
assert(
_classHierarchyBuilder.classHierarchyNodes.length ==
@@ -996,7 +989,7 @@
commonElements: _commonElements,
nativeData: _nativeDataBuilder.close(),
interceptorData: _interceptorDataBuilder.close(),
- backendUsage: _backendUsageBuilder.close(),
+ backendUsage: backendUsage,
noSuchMethodData: _noSuchMethodRegistry.close(),
resolutionWorldBuilder: this,
rtiNeedBuilder: _rtiNeedBuilder,
diff --git a/pkg/compiler/lib/src/universe/world_builder.dart b/pkg/compiler/lib/src/universe/world_builder.dart
index 5107b28..84aa6d3 100644
--- a/pkg/compiler/lib/src/universe/world_builder.dart
+++ b/pkg/compiler/lib/src/universe/world_builder.dart
@@ -14,7 +14,8 @@
import '../elements/types.dart';
import '../js_backend/annotations.dart';
import '../js_backend/allocator_analysis.dart' show KAllocatorAnalysis;
-import '../js_backend/backend_usage.dart' show BackendUsageBuilder;
+import '../js_backend/backend_usage.dart'
+ show BackendUsage, BackendUsageBuilder;
import '../js_backend/interceptor_data.dart' show InterceptorDataBuilder;
import '../js_backend/native_data.dart' show NativeBasicData, NativeDataBuilder;
import '../js_backend/no_such_method_registry.dart';
diff --git a/tests/compiler/dart2js/model/class_set_test.dart b/tests/compiler/dart2js/model/class_set_test.dart
index ada6c0c..790a8a5 100644
--- a/tests/compiler/dart2js/model/class_set_test.dart
+++ b/tests/compiler/dart2js/model/class_set_test.dart
@@ -36,8 +36,8 @@
/// D E F G
///
class A {}
- class B extends A {}
class C extends A {}
+ class B extends A {}
class D extends B {}
class E extends C {}
class F extends C {}
@@ -361,8 +361,8 @@
/// H I
///
class A implements X {}
- class B extends A {}
class C extends A {}
+ class B extends A {}
class D extends B {}
class E extends C {}
class F extends C implements B {}
