[dart2js] Add inferrer engine changes for type graph call linearization.
Change-Id: I23c1f12f4b619be9f4409b23f83cf54cd0fcc301
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/267062
Reviewed-by: Mayank Patke <fishythefish@google.com>
diff --git a/pkg/compiler/lib/src/closure.dart b/pkg/compiler/lib/src/closure.dart
index 5871f23..bae68f9 100644
--- a/pkg/compiler/lib/src/closure.dart
+++ b/pkg/compiler/lib/src/closure.dart
@@ -23,7 +23,8 @@
void writeToDataSink(DataSinkWriter sink);
/// Look up information about the variables that have been mutated and are
- /// used inside the scope of [node].
+ /// used inside the scope of [node]. Assumes member is not abstract and
+ /// therefore scope info exists.
ScopeInfo getScopeInfo(MemberEntity member);
ClosureRepresentationInfo getClosureInfo(ir.LocalFunction localFunction);
diff --git a/pkg/compiler/lib/src/inferrer_experimental/builder.dart b/pkg/compiler/lib/src/inferrer_experimental/builder.dart
index 7e49e67..02a512f 100644
--- a/pkg/compiler/lib/src/inferrer_experimental/builder.dart
+++ b/pkg/compiler/lib/src/inferrer_experimental/builder.dart
@@ -225,10 +225,12 @@
// be handled specially, in that we are computing their LUB at
// each update, and reading them yields the type that was found in a
// previous analysis of [outermostElement].
- ScopeInfo scopeInfo = _closureDataLookup.getScopeInfo(_analyzedMember);
- scopeInfo.forEachBoxedVariable(_localsMap, (variable, field) {
- _capturedAndBoxed[variable] = field;
- });
+ if (!_analyzedMember.isAbstract) {
+ ScopeInfo scopeInfo = _closureDataLookup.getScopeInfo(_analyzedMember);
+ scopeInfo.forEachBoxedVariable(_localsMap, (variable, field) {
+ _capturedAndBoxed[variable] = field;
+ });
+ }
return visit(_analyzedNode)!;
}
diff --git a/pkg/compiler/lib/src/inferrer_experimental/engine.dart b/pkg/compiler/lib/src/inferrer_experimental/engine.dart
index 34d7e38..cb9e1a0 100644
--- a/pkg/compiler/lib/src/inferrer_experimental/engine.dart
+++ b/pkg/compiler/lib/src/inferrer_experimental/engine.dart
@@ -25,6 +25,7 @@
import '../options.dart';
import '../serialization/serialization.dart';
import '../universe/call_structure.dart';
+import '../universe/member_hierarchy.dart';
import '../universe/selector.dart';
import '../universe/side_effects.dart';
import '../inferrer/abstract_value_domain.dart';
@@ -80,7 +81,9 @@
/// The maximum number of times we allow a node in the graph to
/// change types. If a node reaches that limit, we give up
/// inferencing on it and give it the dynamic type.
- final int _MAX_CHANGE_COUNT = 6;
+ /// TODO(natebiggs): This value is needed right now because some types
+ /// do not converge. See https://github.com/dart-lang/sdk/issues/50626
+ final int _MAX_CHANGE_COUNT = 12;
int _overallRefineCount = 0;
int _addedInGraph = 0;
@@ -108,6 +111,8 @@
// [ClosureWorldRefiner].
NoSuchMethodData get noSuchMethodData => closedWorld.noSuchMethodData;
+ final MemberHierarchyBuilder memberHierarchyBuilder;
+
InferrerEngine(
this._options,
this._progress,
@@ -118,7 +123,8 @@
this.globalLocalsMap,
this.inferredDataBuilder)
: this.types = TypeSystem(closedWorld,
- KernelTypeSystemStrategy(closedWorld, globalLocalsMap));
+ KernelTypeSystemStrategy(closedWorld, globalLocalsMap)),
+ memberHierarchyBuilder = MemberHierarchyBuilder(closedWorld);
/// Applies [f] to all elements in the universe that match [selector] and
/// [mask]. If [f] returns false, aborts the iteration.
@@ -309,6 +315,8 @@
}
void _runOverAllElements() {
+ metrics.memberHierarchy
+ .measure(() => memberHierarchyBuilder.init(_joinOverriddenMember));
metrics.analyze.measure(_analyzeAllElements);
final dump =
debug.PRINT_GRAPH ? TypeGraphDump(_compilerOutput, this) : null;
@@ -317,6 +325,10 @@
_buildWorkQueue();
metrics.refine1.measure(_refine);
+ // Update overrides that need to be considered for closurization before
+ // tracing.
+ _updateOverrideClosurizations();
+
metrics.trace.measure(() {
// Try to infer element types of lists and compute their escape information.
types.allocatedLists.values.forEach((ListTypeInformation info) {
@@ -397,7 +409,7 @@
// of this closure call are not a root to trace but an intermediate
// for some other function.
Iterable<FunctionEntity> elements = List<FunctionEntity>.from(
- info.callees.where((e) => e.isFunction));
+ info.callees.where((e) => e.isFunction && !e.isAbstract));
trace(elements, ClosureTracerVisitor(elements, info, this));
}
} else if (info is MemberTypeInformation) {
@@ -429,6 +441,10 @@
_workQueue.addAll(seenTypes);
metrics.refine2.measure(_refine);
+ // Update overrides that need to be considered for closurization after
+ // the final round of refines.
+ _updateOverrideClosurizations();
+
if (debug.PRINT_SUMMARY) {
types.allocatedLists.values.forEach((_info) {
ListTypeInformation info = _info;
@@ -494,11 +510,11 @@
/// Call [analyze] for all live members.
void _analyzeAllElements() {
- Iterable<MemberEntity> processedMembers = closedWorld.processedMembers
- .where((MemberEntity member) => !member.isAbstract);
-
_progress.startPhase();
- processedMembers.forEach((MemberEntity member) {
+ final toProcess = closedWorld.processedMembers
+ .followedBy(closedWorld.liveAbstractInstanceMembers)
+ .toSet();
+ toProcess.forEach((MemberEntity member) {
_progress.showProgress(
'Added ', _addedInGraph, ' elements in inferencing graph.');
// This also forces the creation of the [ElementTypeInformation] to ensure
@@ -616,12 +632,13 @@
}
} else {
final method = element as FunctionEntity;
- recordReturnType(method, type!);
+ // Abstract methods don't have a body so they won't have a return type.
+ if (!method.isAbstract) recordReturnType(method, type!);
}
}
/// Visits [body] to compute the [TypeInformation] node for [member].
- TypeInformation? _computeMemberTypeInformation(
+ TypeInformation _computeMemberTypeInformation(
MemberEntity member, ir.Node? body) {
KernelTypeGraphBuilder visitor = KernelTypeGraphBuilder(
_options,
@@ -742,12 +759,13 @@
}
/// Update the inputs to parameters in the graph. [remove] tells whether
- /// inputs must be added or removed. If [init] is false, parameters are
- /// added to the work queue.
- void updateParameterInputs(TypeInformation caller, MemberEntity callee,
+ /// inputs must be added or removed. If [addToQueue] is `true`, parameters are
+ /// added to the work queue. Returns `true` if the call requires [callee] to
+ /// be closurized.
+ bool updateParameterInputs(TypeInformation callSiteType, MemberEntity callee,
ArgumentsTypes? arguments, Selector? selector,
{required bool remove, required bool addToQueue}) {
- if (callee.name == Identifiers.noSuchMethod_) return;
+ if (callee.name == Identifiers.noSuchMethod_) return false;
if (callee is FieldEntity) {
if (selector!.isSetter) {
ElementTypeInformation info = types.getInferredTypeOfMember(callee);
@@ -759,30 +777,14 @@
if (addToQueue) _workQueue.add(info);
}
} else if (callee.isGetter) {
- return;
+ return false;
} else if (selector != null && selector.isGetter) {
// We are tearing a function off and thus create a closure.
assert(callee.isFunction);
- MemberTypeInformation info = types.getInferredTypeOfMember(callee);
- if (remove) {
- info.closurizedCount--;
- } else {
- info.closurizedCount++;
- if (callee.isStatic || callee.isTopLevel) {
- types.allocatedClosures.add(info);
- } else {
- // We add the call-site type information here so that we
- // can benefit from further refinement of the selector.
- types.allocatedClosures.add(caller);
- }
- types.strategy.forEachParameter(callee as FunctionEntity,
- (Local parameter) {
- ParameterTypeInformation info =
- types.getInferredTypeOfParameter(parameter);
- info.tagAsTearOffClosureParameter(this);
- if (addToQueue) _workQueue.add(info);
- });
- }
+ final memberInfo = types.getInferredTypeOfMember(callee);
+ _markForClosurization(memberInfo, callSiteType,
+ remove: remove, addToQueue: addToQueue);
+ return true;
} else {
final method = callee as FunctionEntity;
ParameterStructure parameterStructure = method.parameterStructure;
@@ -808,6 +810,160 @@
if (addToQueue) _workQueue.add(info);
});
}
+ return false;
+ }
+
+ void _joinOverrideParameters(MemberEntity parent, MemberEntity override) {
+ final method = parent as FunctionEntity;
+ ParameterStructure parameterStructure = method.parameterStructure;
+ int parameterIndex = 0;
+ // Collect the parent parameter type infos.
+ final List<TypeInformation> positional = [];
+ final Map<String, TypeInformation> named = {};
+ types.strategy.forEachParameter(parent, (Local parameter) {
+ TypeInformation type = types.getInferredTypeOfParameter(parameter);
+ if (parameterIndex < parameterStructure.requiredPositionalParameters) {
+ positional.add(type);
+ } else if (parameterStructure.namedParameters.isNotEmpty) {
+ named[parameter.name!] = type;
+ } else if (parameterIndex < parameterStructure.positionalParameters) {
+ positional.add(type);
+ }
+ parameterIndex++;
+ });
+ parameterIndex = 0;
+
+ // Add the parent parameter type infos as inputs to the override's
+ // parameters.
+ types.strategy.forEachParameter(override as FunctionEntity,
+ (Local parameter) {
+ TypeInformation? parentParamInfo;
+ if (parameterIndex < parameterStructure.requiredPositionalParameters) {
+ parentParamInfo = positional[parameterIndex];
+ } else if (parameterStructure.namedParameters.isNotEmpty) {
+ parentParamInfo = named[parameter.name];
+ } else if (parameterIndex < positional.length) {
+ parentParamInfo = positional[parameterIndex];
+ }
+ // If the override includes parameters that the parent doesn't
+ // (optional parameters) then use the override's default type as any
+ // default value will be used within the body of the override.
+ parentParamInfo ??= getDefaultTypeOfParameter(parameter);
+ TypeInformation overrideParamInfo =
+ types.getInferredTypeOfParameter(parameter);
+ overrideParamInfo.addInput(parentParamInfo);
+ parameterIndex++;
+ });
+ }
+
+ /// Adds edges between [parent] and [override] based on the type of member
+ /// each is.
+ ///
+ /// Possible override configurations (parent/override):
+ /// - field/getter
+ /// - field/setter
+ /// - field/field
+ /// - getter/getter
+ /// - getter/field
+ /// - setter/setter
+ /// - setter/field
+ /// - method/method
+ void _joinOverriddenMember(MemberEntity parent, MemberEntity override) {
+ if (parent.name == Identifiers.noSuchMethod_) return;
+ final parentType = types.getInferredTypeOfMember(parent);
+ final overrideType = types.getInferredTypeOfMember(override);
+ if (parent is FieldEntity) {
+ if (override.isGetter) {
+ parentType.addInput(overrideType);
+ } else if (override.isSetter) {
+ types.strategy.forEachParameter(override as FunctionEntity,
+ (Local parameter) {
+ final paramInfo = types.getInferredTypeOfParameter(parameter);
+ paramInfo.addInput(parentType);
+ });
+ } else {
+ assert(override is FieldEntity);
+ parentType.addInput(overrideType);
+ if (parent.isAssignable) {
+ // Parent has an implicit setter so the types of set values need to
+ // flow into the override.
+ overrideType.addInput(parentType);
+ }
+ }
+ } else if (parent.isGetter) {
+ assert(override.isGetter || override is FieldEntity);
+ parentType.addInput(overrideType);
+ } else if (parent.isSetter) {
+ if (override.isSetter) {
+ _joinOverrideParameters(parent, override);
+ } else {
+ assert(override is FieldEntity);
+ types.strategy.forEachParameter(parent as FunctionEntity,
+ (Local parameter) {
+ final paramInfo = types.getInferredTypeOfParameter(parameter);
+ overrideType.addInput(paramInfo);
+ });
+ }
+ } else {
+ assert(parent.isFunction && override.isFunction);
+ parentType.addInput(overrideType);
+ _joinOverrideParameters(parent, override);
+ }
+ }
+
+ void _markForClosurization(
+ MemberTypeInformation memberInfo, TypeInformation callSiteType,
+ {required bool remove, required bool addToQueue}) {
+ final member = memberInfo.member;
+ if (remove) {
+ memberInfo.closurizedCount--;
+ } else {
+ memberInfo.closurizedCount++;
+ if (member.isStatic || member.isTopLevel) {
+ types.allocatedClosures.add(memberInfo);
+ } else {
+ // We add the call-site type information here so that we
+ // can benefit from further refinement of the selector.
+ types.allocatedClosures.add(callSiteType);
+ }
+ types.strategy.forEachParameter(member as FunctionEntity,
+ (Local parameter) {
+ ParameterTypeInformation info =
+ types.getInferredTypeOfParameter(parameter);
+ info.tagAsTearOffClosureParameter(this);
+ if (addToQueue) _workQueue.add(info);
+ });
+ }
+ }
+
+ void _registerOverridesCalled(
+ MemberEntity callee,
+ DynamicCallSiteTypeInformation callSiteType,
+ ir.Node? callSite,
+ Set<MemberEntity> visited,
+ {required bool isClosurized}) {
+ memberHierarchyBuilder.forEachOverride(callee, (override) {
+ if (override.isAbstract || !visited.add(override)) return;
+ MemberTypeInformation info = types.getInferredTypeOfMember(override);
+ info.addCall(callSiteType.caller, callSite);
+
+ if (isClosurized) {
+ _markForClosurization(info, callSiteType,
+ remove: false, addToQueue: false);
+ }
+ });
+ }
+
+ void _updateOverrideClosurizations() {
+ final Set<MemberEntity> visited = {};
+ for (final call in types.allocatedCalls) {
+ if (call is! DynamicCallSiteTypeInformation) continue;
+ for (final target in call.callees) {
+ if (!visited.add(target)) continue;
+ _registerOverridesCalled(target, call, null, visited,
+ isClosurized: call.closurizedTargets.contains(target));
+ }
+ }
}
/// Sets the type of a parameter's default value to [type]. If the global
@@ -871,8 +1027,7 @@
// Even if x.== doesn't return a bool, 'x == null' evaluates to 'false'.
info.addInput(types.boolType);
}
-
- if (info.inputs.isEmpty) info.addInput(type);
+ info.addInput(type);
}
/// Notifies to the inferrer that [analyzedElement] can have return type
@@ -1140,6 +1295,7 @@
class _InferrerEngineMetrics extends MetricsBase {
final time = DurationMetric('time');
final analyze = DurationMetric('time.analyze');
+ final memberHierarchy = DurationMetric('time.memberHierarchy');
final refine1 = DurationMetric('time.refine1');
final trace = DurationMetric('time.trace');
final refine2 = DurationMetric('time.refine2');
@@ -1152,6 +1308,7 @@
primary = [time, ...subMetrics.primary];
secondary = [
analyze,
+ memberHierarchy,
refine1,
trace,
refine2,
diff --git a/pkg/compiler/lib/src/inferrer_experimental/node_tracer.dart b/pkg/compiler/lib/src/inferrer_experimental/node_tracer.dart
index 69c1b89..1555457 100644
--- a/pkg/compiler/lib/src/inferrer_experimental/node_tracer.dart
+++ b/pkg/compiler/lib/src/inferrer_experimental/node_tracer.dart
@@ -104,7 +104,7 @@
int.fromEnvironment('dart2js.tracing.limit', defaultValue: 32);
// TODO(natebiggs): We allow null here to maintain current functionality
// but we should verify we actually need to allow it.
- final Setlet<MemberEntity> analyzedElements = Setlet<MemberEntity>();
+ final Setlet<MemberEntity?> analyzedElements = Setlet<MemberEntity?>();
TracerVisitor(this.tracedType, this.inferrer);
@@ -163,7 +163,7 @@
break;
}
for (final info in user.users) {
- analyzedElements.add(info.owner!);
+ analyzedElements.add(info.owner);
info.accept(this);
}
while (!listsToAnalyze.isEmpty) {
diff --git a/pkg/compiler/lib/src/inferrer_experimental/type_graph_nodes.dart b/pkg/compiler/lib/src/inferrer_experimental/type_graph_nodes.dart
index d9cdf1f..01d3fc4 100644
--- a/pkg/compiler/lib/src/inferrer_experimental/type_graph_nodes.dart
+++ b/pkg/compiler/lib/src/inferrer_experimental/type_graph_nodes.dart
@@ -1095,6 +1095,9 @@
callee.removeCall(caller, _call!);
}
+ // TODO(natebiggs): Populate this below.
+ late final Set<MemberEntity> closurizedTargets = {};
+
@override
void addToGraph(InferrerEngine inferrer) {
assert((receiver as dynamic) != null); // TODO(48820): Remove when sound.
diff --git a/pkg/compiler/lib/src/inferrer_experimental/type_system.dart b/pkg/compiler/lib/src/inferrer_experimental/type_system.dart
index e7aec78..68d1039 100644
--- a/pkg/compiler/lib/src/inferrer_experimental/type_system.dart
+++ b/pkg/compiler/lib/src/inferrer_experimental/type_system.dart
@@ -331,8 +331,6 @@
}
MemberTypeInformation getInferredTypeOfMember(MemberEntity member) {
- assert(!member.isAbstract,
- failedAt(member, "Unexpected abstract member $member."));
return memberTypeInformations[member] ??= _getInferredTypeOfMember(member);
}
diff --git a/pkg/compiler/lib/src/inferrer_experimental/types.dart b/pkg/compiler/lib/src/inferrer_experimental/types.dart
index 9ae851a..f7197f9 100644
--- a/pkg/compiler/lib/src/inferrer_experimental/types.dart
+++ b/pkg/compiler/lib/src/inferrer_experimental/types.dart
@@ -323,7 +323,7 @@
(MemberEntity member, GlobalTypeInferenceMemberResult result) =>
result.writeToDataSink(
sink,
- elementMap.getMemberContextNode(member)!,
+ elementMap.getMemberContextNode(member),
closedWorld.abstractValueDomain)));
sink.writeDeferrable(() => sink.writeLocalMap(
_parameterResults.loaded(),
