[vm/kernel/aot] Approximate numerous invocations per selector in TFA
This change adds tracking of number of invocations with the same
selector but different arguments. If this number reaches certain limit,
all subsequent invocations with such selector are approximated.
On Flutter gallery, 1 selector is approximated:
dart.core::Object::==
On Analyzer, 2 selectors are approximated:
analyzer.dart.ast.ast::AstNode::visitChildren
dart.core::List::[]=
Flutter gallery Total(CodeSize): +11 K.
Fixes https://github.com/dart-lang/sdk/issues/33199
Change-Id: I3598555194262a4f08fe1bc207d10880a25eb432
Reviewed-on: https://dart-review.googlesource.com/56420
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 deb2464..40a3e79 100644
--- a/pkg/vm/lib/transformations/type_flow/analysis.dart
+++ b/pkg/vm/lib/transformations/type_flow/analysis.dart
@@ -611,20 +611,65 @@
}
}
+/// Keeps track of number of cached [_Invocation] objects with
+/// a particular selector and provides approximation if needed.
+class _SelectorApproximation {
+ /// Approximation [_Invocation] with raw arguments is created and used
+ /// after number of [_Invocation] objects with same selector but
+ /// different arguments reaches this limit.
+ static const int maxInvocationsPerSelector = 5000;
+
+ int count = 0;
+ _Invocation approximation;
+}
+
+/// Maintains ([Selector], [Args]) => [_Invocation] cache.
+/// Invocations are cached in order to reuse previously calculated result.
class _InvocationsCache {
+ final TypeFlowAnalysis _typeFlowAnalysis;
final Set<_Invocation> _invocations = new Set<_Invocation>();
+ final Map<Selector, _SelectorApproximation> _approximations =
+ <Selector, _SelectorApproximation>{};
+
+ _InvocationsCache(this._typeFlowAnalysis);
_Invocation getInvocation(Selector selector, Args<Type> args) {
+ ++Statistics.invocationsQueriedInCache;
_Invocation invocation = (selector is DirectSelector)
? new _DirectInvocation(selector, args)
: new _DispatchableInvocation(selector, args);
_Invocation result = _invocations.lookup(invocation);
- if (result == null) {
- bool added = _invocations.add(invocation);
- assertx(added);
- result = invocation;
+ if (result != null) {
+ return result;
}
- return result;
+
+ if (selector is InterfaceSelector) {
+ // Detect if there are too many invocations per selector. In such case,
+ // approximate extra invocations with a single invocation with raw
+ // arguments.
+
+ final sa = (_approximations[selector] ??= new _SelectorApproximation());
+
+ if (sa.count >= _SelectorApproximation.maxInvocationsPerSelector) {
+ if (sa.approximation == null) {
+ final rawArgs =
+ _typeFlowAnalysis.summaryCollector.rawArguments(selector);
+ sa.approximation = new _DispatchableInvocation(selector, rawArgs);
+ Statistics.approximateInvocationsCreated++;
+ }
+ Statistics.approximateInvocationsUsed++;
+ return sa.approximation;
+ }
+
+ ++sa.count;
+ Statistics.maxInvocationsCachedPerSelector =
+ max(Statistics.maxInvocationsCachedPerSelector, sa.count);
+ }
+
+ bool added = _invocations.add(invocation);
+ assertx(added);
+ ++Statistics.invocationsAddedToCache;
+ return invocation;
}
}
@@ -1010,6 +1055,7 @@
void process() {
while (pending.isNotEmpty) {
assertx(callStack.isEmpty && processing.isEmpty);
+ Statistics.iterationsOverInvocationsWorkList++;
processInvocation(pending.first);
}
}
@@ -1060,6 +1106,7 @@
// Invocation is still pending - it was invalidated while being processed.
// Move result to invalidatedResult.
if (_isPending(invocation)) {
+ Statistics.invocationsInvalidatedDuringProcessing++;
invocation.invalidatedResult = result;
invocation.result = null;
}
@@ -1095,7 +1142,7 @@
final NativeCodeOracle nativeCodeOracle;
_ClassHierarchyCache hierarchyCache;
SummaryCollector summaryCollector;
- _InvocationsCache _invocationsCache = new _InvocationsCache();
+ _InvocationsCache _invocationsCache;
_WorkList workList;
final Map<Member, Summary> _summaries = <Member, Summary>{};
@@ -1108,6 +1155,7 @@
hierarchyCache = new _ClassHierarchyCache(this, hierarchy);
summaryCollector =
new SummaryCollector(environment, this, nativeCodeOracle);
+ _invocationsCache = new _InvocationsCache(this);
workList = new _WorkList(this);
if (entryPointsJSONFiles != null) {
diff --git a/pkg/vm/lib/transformations/type_flow/utils.dart b/pkg/vm/lib/transformations/type_flow/utils.dart
index de0d7a0..3ce56e8 100644
--- a/pkg/vm/lib/transformations/type_flow/utils.dart
+++ b/pkg/vm/lib/transformations/type_flow/utils.dart
@@ -78,6 +78,13 @@
static int maxInvalidationsPerInvocation = 0;
static int recursiveInvocationsApproximated = 0;
static int typeConeSpecializations = 0;
+ static int iterationsOverInvocationsWorkList = 0;
+ static int invocationsInvalidatedDuringProcessing = 0;
+ static int invocationsQueriedInCache = 0;
+ static int invocationsAddedToCache = 0;
+ static int maxInvocationsCachedPerSelector = 0;
+ static int approximateInvocationsCreated = 0;
+ static int approximateInvocationsUsed = 0;
static int classesDropped = 0;
static int membersDropped = 0;
static int methodBodiesDropped = 0;
@@ -97,6 +104,13 @@
maxInvalidationsPerInvocation = 0;
recursiveInvocationsApproximated = 0;
typeConeSpecializations = 0;
+ iterationsOverInvocationsWorkList = 0;
+ invocationsInvalidatedDuringProcessing = 0;
+ invocationsQueriedInCache = 0;
+ invocationsAddedToCache = 0;
+ maxInvocationsCachedPerSelector = 0;
+ approximateInvocationsCreated = 0;
+ approximateInvocationsUsed = 0;
classesDropped = 0;
membersDropped = 0;
methodBodiesDropped = 0;
@@ -117,6 +131,13 @@
${maxInvalidationsPerInvocation} maximum invalidations per invocation
${recursiveInvocationsApproximated} recursive invocations approximated
${typeConeSpecializations} type cones specialized
+ ${iterationsOverInvocationsWorkList} iterations over invocations work list
+ ${invocationsInvalidatedDuringProcessing} invocations invalidated during processing
+ ${invocationsQueriedInCache} invocations queried in cache
+ ${invocationsAddedToCache} invocations added to cache
+ ${maxInvocationsCachedPerSelector} maximum invocations cached per selector
+ ${approximateInvocationsCreated} approximate invocations created
+ ${approximateInvocationsUsed} times approximate invocation is used
${classesDropped} classes dropped
${membersDropped} members dropped
${methodBodiesDropped} method bodies dropped
