Skip to content

Commit 2cb2ac4

Browse files
johnniwinthercommit-bot@chromium.org
johnniwinther
authored and
[email protected]
committed
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 <[email protected]> Reviewed-by: Stephen Adams <[email protected]>
1 parent e8880fd commit 2cb2ac4

File tree

7 files changed

+115
-30
lines changed

7 files changed

+115
-30
lines changed

‎pkg/compiler/lib/src/compiler.dart‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -290,6 +290,15 @@ abstract class Compiler {
290290

291291
JClosedWorld computeClosedWorld(LoadedLibraries loadedLibraries) {
292292
ResolutionEnqueuer resolutionEnqueuer = startResolution();
293+
for (LibraryEntity library
294+
in frontendStrategy.elementEnvironment.libraries) {
295+
frontendStrategy.elementEnvironment.forEachClass(library,
296+
(ClassEntity cls) {
297+
// Register all classes eagerly to optimize closed world computation in
298+
// `ClassWorldBuilder.isInheritedInSubtypeOf`.
299+
resolutionEnqueuer.worldBuilder.registerClass(cls);
300+
});
301+
}
293302
WorldImpactBuilderImpl mainImpact = new WorldImpactBuilderImpl();
294303
FunctionEntity mainFunction = frontendStrategy.computeMain(mainImpact);
295304

‎pkg/compiler/lib/src/js_emitter/program_builder/program_builder.dart‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -690,7 +690,7 @@ class ProgramBuilder {
690690
callStubs.add(_buildStubMethod(name, function));
691691
}
692692

693-
if (_commonElements.isInstantiationClass(cls)) {
693+
if (_commonElements.isInstantiationClass(cls) && !onlyForRti) {
694694
callStubs.addAll(_generateInstantiationStubs(cls));
695695
}
696696

‎pkg/compiler/lib/src/library_loader.dart‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -41,6 +41,8 @@ class LibraryLoaderTask extends CompilerTask {
4141
: initializedCompilerState = _options.kernelInitializedCompilerState,
4242
super(measurer);
4343

44+
String get name => 'Library loader';
45+
4446
/// Loads an entire Kernel [Component] from a file on disk.
4547
Future<LoadedLibraries> loadLibraries(Uri resolvedUri) {
4648
return measure(() async {

‎pkg/compiler/lib/src/universe/class_hierarchy.dart‎

Lines changed: 96 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -625,32 +625,112 @@ class ClassHierarchyBuilder {
625625
return classSet.hasSubtype(classHierarchyNode);
626626
}
627627

628+
Map<ClassEntity, _InheritedCache> _inheritedCacheMap = {};
629+
628630
bool isInheritedInSubtypeOf(ClassEntity x, ClassEntity y) {
629-
ClassSet classSet = classSets[x];
630-
assert(classSet != null,
631-
failedAt(x, "No ClassSet for $x (${x.runtimeType}): ${classSets}"));
631+
_InheritedCache cache = _inheritedCacheMap[x] ??= new _InheritedCache();
632+
return cache.isInheritedInSubtypeOf(this, x, y);
633+
}
634+
}
632635

633-
if (_isSubtypeOf(x, y)) {
634-
// [x] implements [y] itself, possible through supertypes.
635-
return true;
636+
/// A cache object used for [ClassHierarchyBuilder.isInheritedInSubtypeOf].
637+
class _InheritedCache {
638+
Map<ClassEntity, _InheritingSet> _map;
639+
640+
/// Returns whether a live class currently known to inherit from [x] and
641+
/// implement [y].
642+
bool isInheritedInSubtypeOf(
643+
ClassHierarchyBuilder builder, ClassEntity x, ClassEntity y) {
644+
_InheritingSet set;
645+
if (_map == null) {
646+
_map = {};
647+
} else {
648+
set = _map[y];
636649
}
650+
if (set == null) {
651+
set = _map[y] = _computeInheritingSet(builder, x, y);
652+
}
653+
return set.hasLiveClass(builder);
654+
}
655+
656+
/// Creates an [_InheritingSet] of classes that inherit members of a class [x]
657+
/// while implementing class [y].
658+
_InheritingSet _computeInheritingSet(
659+
ClassHierarchyBuilder builder, ClassEntity x, ClassEntity y) {
660+
ClassSet classSet = builder.classSets[x];
661+
662+
assert(
663+
classSet != null,
664+
failedAt(
665+
x, "No ClassSet for $x (${x.runtimeType}): ${builder.classSets}"));
666+
667+
Set<ClassEntity> classes = new Set<ClassEntity>();
637668

638-
/// Returns `true` if any live subclass of [node] implements [y].
639-
bool subclassImplements(ClassHierarchyNode node, {bool strict}) {
640-
return node.anySubclass((ClassEntity z) => _isSubtypeOf(z, y),
641-
ClassHierarchyNode.INSTANTIATED,
642-
strict: strict);
669+
if (builder._isSubtypeOf(x, y)) {
670+
// [x] implements [y] itself, possible through supertypes.
671+
classes.add(x);
643672
}
644673

645-
if (subclassImplements(classSet.node, strict: true)) {
646-
// A subclass of [x] implements [y].
647-
return true;
674+
/// Add subclasses of [node] that implement [y].
675+
void subclassImplements(ClassHierarchyNode node, {bool strict}) {
676+
node.forEachSubclass((ClassEntity z) {
677+
if (builder._isSubtypeOf(z, y)) {
678+
classes.add(z);
679+
}
680+
}, ClassHierarchyNode.ALL, strict: strict);
648681
}
649682

683+
// A subclasses of [x] that implement [y].
684+
subclassImplements(classSet.node, strict: true);
685+
650686
for (ClassHierarchyNode mixinApplication
651687
in classSet.mixinApplicationNodes) {
652-
if (subclassImplements(mixinApplication, strict: false)) {
653-
// A subclass of [mixinApplication] implements [y].
688+
// A subclass of [mixinApplication] implements [y].
689+
subclassImplements(mixinApplication, strict: false);
690+
}
691+
692+
return new _InheritingSet(classes);
693+
}
694+
}
695+
696+
/// A set of classes that inherit members of a class 'x' while implementing
697+
/// class 'y'.
698+
///
699+
/// The set is used [ClassHierarchyBuilder.isInheritedInSubtypeOf] to determine
700+
/// when members of a class is live.
701+
class _InheritingSet {
702+
/// If `true` the set of classes is known to contain a live class. In this
703+
/// case [_classes] is `null`. If `false` the set of classes is empty and
704+
/// therefore known never to contain live classes. In this case [_classes]
705+
/// is `null`. If `null` [_classes] is a non-empty set containing classes
706+
/// that are not yet known to be live.
707+
bool _result;
708+
Set<ClassEntity> _classes;
709+
710+
_InheritingSet(Set<ClassEntity> classes)
711+
: _result = classes.isEmpty ? false : null,
712+
_classes = classes.isNotEmpty ? classes : null;
713+
714+
/// Returns whether the set of classes is currently known to contain a live
715+
/// classes.
716+
///
717+
/// The result of this method changes during the closed world computation.
718+
/// Initially, we haven't seen any live classes so we will return `false` even
719+
/// for a non-empty set of classes. As more classes are marked as
720+
/// instantiated, during tree-shaking, the result might change to `true` if
721+
/// one of the [_classes] has been marked as live.
722+
///
723+
/// The result of this method _is_ monotone, though; when we have returned
724+
/// `true` (because at least one class is known to be live) we will continue
725+
/// to return `true`.
726+
bool hasLiveClass(ClassHierarchyBuilder builder) {
727+
if (_result != null) return _result;
728+
for (ClassEntity cls in _classes) {
729+
if (builder.classHierarchyNodes[cls].isInstantiated) {
730+
// We now know this set contains a live class and done need to remember
731+
// that set of classes anymore.
732+
_result = true;
733+
_classes = null;
654734
return true;
655735
}
656736
}

‎pkg/compiler/lib/src/universe/resolution_world_builder.dart‎

Lines changed: 3 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -851,7 +851,7 @@ class ResolutionWorldBuilderImpl extends WorldBuilderBase
851851
memberUsed(usage.entity, useSet);
852852
return usage;
853853
});
854-
if (!newUsage) {
854+
if (!usage.fullyUsed && !newUsage) {
855855
EnumSet<MemberUse> useSet = new EnumSet<MemberUse>();
856856
if (!usage.hasRead && _hasInvokedGetter(member)) {
857857
useSet.addAll(usage.read());
@@ -945,8 +945,6 @@ class ResolutionWorldBuilderImpl extends WorldBuilderBase
945945
bool isInheritedInSubtypeOf(MemberEntity member, ClassEntity type) {
946946
// TODO(johnniwinther): Use the [member] itself to avoid enqueueing members
947947
// that are overridden.
948-
_classHierarchyBuilder.registerClass(member.enclosingClass);
949-
_classHierarchyBuilder.registerClass(type);
950948
return _classHierarchyBuilder.isInheritedInSubtypeOf(
951949
member.enclosingClass, type);
952950
}
@@ -972,12 +970,7 @@ class ResolutionWorldBuilderImpl extends WorldBuilderBase
972970
Map<ClassEntity, Set<ClassEntity>> typesImplementedBySubclasses =
973971
populateHierarchyNodes();
974972

975-
var backendUsage = _backendUsageBuilder.close();
976-
backendUsage.helperClassesUsed
977-
.forEach(_classHierarchyBuilder.registerClass);
978-
_nativeResolutionEnqueuer.liveNativeClasses
979-
.forEach(_classHierarchyBuilder.registerClass);
980-
973+
BackendUsage backendUsage = _backendUsageBuilder.close();
981974
_closed = true;
982975
assert(
983976
_classHierarchyBuilder.classHierarchyNodes.length ==
@@ -996,7 +989,7 @@ class ResolutionWorldBuilderImpl extends WorldBuilderBase
996989
commonElements: _commonElements,
997990
nativeData: _nativeDataBuilder.close(),
998991
interceptorData: _interceptorDataBuilder.close(),
999-
backendUsage: _backendUsageBuilder.close(),
992+
backendUsage: backendUsage,
1000993
noSuchMethodData: _noSuchMethodRegistry.close(),
1001994
resolutionWorldBuilder: this,
1002995
rtiNeedBuilder: _rtiNeedBuilder,

‎pkg/compiler/lib/src/universe/world_builder.dart‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,8 @@ import '../elements/entities.dart';
1414
import '../elements/types.dart';
1515
import '../js_backend/annotations.dart';
1616
import '../js_backend/allocator_analysis.dart' show KAllocatorAnalysis;
17-
import '../js_backend/backend_usage.dart' show BackendUsageBuilder;
17+
import '../js_backend/backend_usage.dart'
18+
show BackendUsage, BackendUsageBuilder;
1819
import '../js_backend/interceptor_data.dart' show InterceptorDataBuilder;
1920
import '../js_backend/native_data.dart' show NativeBasicData, NativeDataBuilder;
2021
import '../js_backend/no_such_method_registry.dart';

‎tests/compiler/dart2js/model/class_set_test.dart‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -36,8 +36,8 @@ testIterators() async {
3636
/// D E F G
3737
///
3838
class A {}
39-
class B extends A {}
4039
class C extends A {}
40+
class B extends A {}
4141
class D extends B {}
4242
class E extends C {}
4343
class F extends C {}
@@ -361,8 +361,8 @@ testForEach() async {
361361
/// H I
362362
///
363363
class A implements X {}
364-
class B extends A {}
365364
class C extends A {}
365+
class B extends A {}
366366
class D extends B {}
367367
class E extends C {}
368368
class F extends C implements B {}

0 commit comments

Comments
 (0)