Skip to content

Commit 1c2d378

Browse files
askeksacommit-bot@chromium.org
askeksa
authored and
commit-bot@chromium.org
committed
[vm/aot] Use TFA to eliminate unused selectors in dispatch table.
For each selector, count the number of calls to the selector that are both reachable and polymorphic according to the TFA. Only include selectors in the table with non-zero counts. This reduces the dispatch table size by 30% in dart2js and by 49% in Flutter Gallery (312k memory use reduction on ARM64). Call counts are transferred in a dedicated metadata block with per-selector information. This mechanism also prepares for transferring other per-selector information in the future. Change-Id: Iba15aa4d6c50e67e53c3fd8e542123d3fc98bd07 Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/132603 Reviewed-by: Alexander Markov <alexmarkov@google.com>
1 parent 022b362 commit 1c2d378

10 files changed

Lines changed: 232 additions & 10 deletions

File tree

‎pkg/vm/bin/dump_kernel.dart‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -14,6 +14,8 @@ import 'package:vm/metadata/inferred_type.dart'
1414
show InferredTypeMetadataRepository;
1515
import 'package:vm/metadata/procedure_attributes.dart'
1616
show ProcedureAttributesMetadataRepository;
17+
import 'package:vm/metadata/table_selector.dart'
18+
show TableSelectorMetadataRepository;
1719
import 'package:vm/metadata/unreachable.dart'
1820
show UnreachableNodeMetadataRepository;
1921
import 'package:vm/metadata/call_site_attributes.dart'
@@ -39,6 +41,7 @@ main(List<String> arguments) async {
3941
component.addMetadataRepository(new DirectCallMetadataRepository());
4042
component.addMetadataRepository(new InferredTypeMetadataRepository());
4143
component.addMetadataRepository(new ProcedureAttributesMetadataRepository());
44+
component.addMetadataRepository(new TableSelectorMetadataRepository());
4245
component.addMetadataRepository(new UnreachableNodeMetadataRepository());
4346
component.addMetadataRepository(new BytecodeMetadataRepository());
4447
component.addMetadataRepository(new CallSiteAttributesMetadataRepository());

‎pkg/vm/lib/metadata/table_selector.dart‎

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
// Copyright (c) 2020, the Dart project authors. Please see the AUTHORS file
2+
// for details. All rights reserved. Use of this source code is governed by a
3+
// BSD-style license that can be found in the LICENSE file.
4+
5+
import 'package:kernel/ast.dart';
6+
7+
import 'procedure_attributes.dart';
8+
9+
// Information associated with a selector, used by the dispatch table generator.
10+
class TableSelectorInfo {
11+
int callCount;
12+
13+
TableSelectorInfo() : callCount = 0;
14+
15+
TableSelectorInfo.readFromBinary(BinarySource source)
16+
: callCount = source.readUInt();
17+
18+
void writeToBinary(BinarySink sink) {
19+
sink.writeUInt30(callCount);
20+
}
21+
}
22+
23+
class TableSelectorMetadata {
24+
final List<TableSelectorInfo> selectors;
25+
26+
TableSelectorMetadata()
27+
: selectors = <TableSelectorInfo>[TableSelectorInfo()] {
28+
assert(
29+
selectors.length == ProcedureAttributesMetadata.kInvalidSelectorId + 1);
30+
}
31+
32+
TableSelectorMetadata.fromSelectors(this.selectors);
33+
34+
int addSelector() {
35+
final int selectorId = selectors.length;
36+
selectors.add(TableSelectorInfo());
37+
return selectorId;
38+
}
39+
}
40+
41+
class TableSelectorMetadataRepository
42+
extends MetadataRepository<TableSelectorMetadata> {
43+
static const repositoryTag = 'vm.table-selector.metadata';
44+
45+
@override
46+
final String tag = repositoryTag;
47+
48+
@override
49+
final Map<TreeNode, TableSelectorMetadata> mapping =
50+
<TreeNode, TableSelectorMetadata>{};
51+
52+
@override
53+
void writeToBinary(
54+
TableSelectorMetadata metadata, Node node, BinarySink sink) {
55+
final List<TableSelectorInfo> selectors = metadata.selectors;
56+
sink.writeUInt30(selectors.length);
57+
for (TableSelectorInfo selector in selectors) {
58+
selector.writeToBinary(sink);
59+
}
60+
}
61+
62+
@override
63+
TableSelectorMetadata readFromBinary(Node node, BinarySource source) {
64+
final int length = source.readUInt();
65+
final List<TableSelectorInfo> selectors = List<TableSelectorInfo>.generate(
66+
length, (_) => TableSelectorInfo.readFromBinary(source));
67+
return TableSelectorMetadata.fromSelectors(selectors);
68+
}
69+
}

‎pkg/vm/lib/transformations/type_flow/table_selector.dart‎

Lines changed: 16 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -5,18 +5,20 @@
55
import 'package:kernel/ast.dart';
66

77
import '../../metadata/procedure_attributes.dart';
8+
import '../../metadata/table_selector.dart';
89

910
// Assigns dispatch table selector IDs to interface targets.
1011
// TODO(dartbug.com/40188): Implement a more fine-grained assignment based on
1112
// hierarchy connectedness.
1213
class TableSelectorAssigner {
14+
final TableSelectorMetadata metadata = TableSelectorMetadata();
15+
1316
final Map<Name, int> _methodSelectorId = {};
1417
final Map<Name, int> _getterSelectorId = {};
1518
final Map<Name, int> _setterSelectorId = {};
16-
int _nextSelectorId = ProcedureAttributesMetadata.kInvalidSelectorId + 1;
1719

1820
int _selectorIdForMap(Map<Name, int> map, Member member) {
19-
return map.putIfAbsent(member.name, () => _nextSelectorId++);
21+
return map.putIfAbsent(member.name, () => metadata.addSelector());
2022
}
2123

2224
int methodOrSetterSelectorId(Member member) {
@@ -57,4 +59,16 @@ class TableSelectorAssigner {
5759
}
5860
throw "Unexpected member kind '${member.runtimeType}'";
5961
}
62+
63+
void registerCall(int selectorId) {
64+
metadata.selectors[selectorId].callCount++;
65+
}
66+
67+
void registerMethodOrSetterCall(Member member) {
68+
registerCall(methodOrSetterSelectorId(member));
69+
}
70+
71+
void registerGetterCall(Member member) {
72+
registerCall(getterSelectorId(member));
73+
}
6074
}

‎pkg/vm/lib/transformations/type_flow/transformer.dart‎

Lines changed: 30 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -25,6 +25,7 @@ import '../devirtualization.dart' show Devirtualization;
2525
import '../../metadata/direct_call.dart';
2626
import '../../metadata/inferred_type.dart';
2727
import '../../metadata/procedure_attributes.dart';
28+
import '../../metadata/table_selector.dart';
2829
import '../../metadata/unreachable.dart';
2930

3031
const bool kDumpClassHierarchy =
@@ -116,23 +117,34 @@ class TFADevirtualization extends Devirtualization {
116117
class AnnotateKernel extends RecursiveVisitor<Null> {
117118
final TypeFlowAnalysis _typeFlowAnalysis;
118119
final FieldMorpher fieldMorpher;
120+
final DirectCallMetadataRepository _directCallMetadataRepository;
119121
final InferredTypeMetadataRepository _inferredTypeMetadata;
120122
final UnreachableNodeMetadataRepository _unreachableNodeMetadata;
121123
final ProcedureAttributesMetadataRepository _procedureAttributesMetadata;
124+
final TableSelectorMetadataRepository _tableSelectorMetadata;
122125
final TableSelectorAssigner _tableSelectorAssigner;
123126
final Class _intClass;
124127
Constant _nullConstant;
125128

126129
AnnotateKernel(Component component, this._typeFlowAnalysis, this.fieldMorpher)
127-
: _inferredTypeMetadata = new InferredTypeMetadataRepository(),
130+
: _directCallMetadataRepository =
131+
component.metadata[DirectCallMetadataRepository.repositoryTag],
132+
_inferredTypeMetadata = new InferredTypeMetadataRepository(),
128133
_unreachableNodeMetadata = new UnreachableNodeMetadataRepository(),
129134
_procedureAttributesMetadata =
130135
new ProcedureAttributesMetadataRepository(),
136+
_tableSelectorMetadata = new TableSelectorMetadataRepository(),
131137
_tableSelectorAssigner = new TableSelectorAssigner(),
132138
_intClass = _typeFlowAnalysis.environment.coreTypes.intClass {
133139
component.addMetadataRepository(_inferredTypeMetadata);
134140
component.addMetadataRepository(_unreachableNodeMetadata);
135141
component.addMetadataRepository(_procedureAttributesMetadata);
142+
component.addMetadataRepository(_tableSelectorMetadata);
143+
}
144+
145+
// Query whether a call site was marked as a direct call by the analysis.
146+
bool _callSiteUsesDirectCall(TreeNode node) {
147+
return _directCallMetadataRepository.mapping.containsKey(node);
136148
}
137149

138150
InferredType _convertType(Type type,
@@ -246,6 +258,17 @@ class AnnotateKernel extends RecursiveVisitor<Null> {
246258
_setInferredType(node, resultType,
247259
skipCheck: markSkipCheck, receiverNotInt: markReceiverNotInt);
248260
}
261+
262+
// Tell the table selector assigner about the callsite.
263+
final Selector selector = callSite.selector;
264+
if (selector is InterfaceSelector && !_callSiteUsesDirectCall(node)) {
265+
if (node is PropertyGet) {
266+
_tableSelectorAssigner.registerGetterCall(selector.member);
267+
} else {
268+
assertx(node is MethodInvocation || node is PropertySet);
269+
_tableSelectorAssigner.registerMethodOrSetterCall(selector.member);
270+
}
271+
}
249272
}
250273

251274
void _annotateMember(Member member) {
@@ -399,6 +422,12 @@ class AnnotateKernel extends RecursiveVisitor<Null> {
399422
_annotateCallSite(node, node.target);
400423
super.visitStaticSet(node);
401424
}
425+
426+
@override
427+
visitComponent(Component node) {
428+
super.visitComponent(node);
429+
_tableSelectorMetadata.mapping[node] = _tableSelectorAssigner.metadata;
430+
}
402431
}
403432

404433
/// Tree shaking based on results of type flow analysis (TFA).

‎runtime/vm/compiler/aot/dispatch_table_generator.cc‎

Lines changed: 24 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -400,17 +400,20 @@ const TableSelector* SelectorMap::GetSelector(
400400
const int32_t sid = SelectorId(interface_target);
401401
if (sid == kInvalidSelectorId) return nullptr;
402402
const TableSelector* selector = &selectors_[sid];
403+
if (!selector->IsUsed()) return nullptr;
403404
if (selector->offset == kInvalidSelectorOffset) return nullptr;
404405
return selector;
405406
}
406407

408+
void SelectorMap::AddSelector(int32_t call_count) {
409+
const int32_t added_sid = selectors_.length();
410+
selectors_.Add(TableSelector(added_sid, call_count, kInvalidSelectorOffset));
411+
}
412+
407413
void SelectorMap::SetSelectorProperties(int32_t sid,
408414
bool on_null_interface,
409415
bool requires_args_descriptor) {
410-
while (selectors_.length() <= sid) {
411-
const int32_t added_sid = selectors_.length();
412-
selectors_.Add(TableSelector{added_sid, kInvalidSelectorId, false, false});
413-
}
416+
ASSERT(sid < selectors_.length());
414417
selectors_[sid].on_null_interface |= on_null_interface;
415418
selectors_[sid].requires_args_descriptor |= requires_args_descriptor;
416419
}
@@ -429,11 +432,26 @@ DispatchTableGenerator::DispatchTableGenerator(Zone* zone)
429432
void DispatchTableGenerator::Initialize(ClassTable* table) {
430433
classes_ = table;
431434

435+
ReadTableSelectorInfo();
432436
NumberSelectors();
433437
SetupSelectorRows();
434438
ComputeSelectorOffsets();
435439
}
436440

441+
void DispatchTableGenerator::ReadTableSelectorInfo() {
442+
const auto& object_class = Class::Handle(Z, classes_->At(kInstanceCid));
443+
const auto& script = Script::Handle(Z, object_class.script());
444+
const auto& info = KernelProgramInfo::Handle(Z, script.kernel_program_info());
445+
kernel::TableSelectorMetadata* metadata =
446+
kernel::TableSelectorMetadataForProgram(info, Z);
447+
// This assert will fail if gen_kernel was run in non-AOT mode or without TFA.
448+
RELEASE_ASSERT(metadata != nullptr);
449+
for (intptr_t i = 0; i < metadata->selectors.length(); i++) {
450+
const kernel::TableSelectorInfo* info = &metadata->selectors[i];
451+
selector_map_.AddSelector(info->call_count);
452+
}
453+
}
454+
437455
void DispatchTableGenerator::NumberSelectors() {
438456
num_classes_ = classes_->NumCids();
439457

@@ -583,7 +601,8 @@ void DispatchTableGenerator::SetupSelectorRows() {
583601

584602
// Retain all selectors that contain implementation intervals.
585603
for (intptr_t i = 0; i < num_selectors_; i++) {
586-
if (selector_rows[i].Finalize()) {
604+
const TableSelector& selector = selector_map_.selectors_[i];
605+
if (selector.IsUsed() && selector_rows[i].Finalize()) {
587606
table_rows_.Add(&selector_rows[i]);
588607
}
589608
}

‎runtime/vm/compiler/aot/dispatch_table_generator.h‎

Lines changed: 10 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -19,10 +19,16 @@ namespace compiler {
1919
class SelectorRow;
2020

2121
struct TableSelector {
22+
TableSelector(int32_t id, int32_t call_count, int32_t offset)
23+
: id(id), call_count(call_count), offset(offset) {}
24+
25+
bool IsUsed() const { return call_count > 0; }
26+
2227
int32_t id;
28+
int32_t call_count;
2329
int32_t offset;
24-
bool on_null_interface;
25-
bool requires_args_descriptor;
30+
bool on_null_interface = false;
31+
bool requires_args_descriptor = false;
2632
};
2733

2834
class SelectorMap {
@@ -40,6 +46,7 @@ class SelectorMap {
4046

4147
int32_t SelectorId(const Function& interface_target) const;
4248

49+
void AddSelector(int32_t call_count);
4350
void SetSelectorProperties(int32_t sid,
4451
bool on_null_interface,
4552
bool requires_args_descriptor);
@@ -68,6 +75,7 @@ class DispatchTableGenerator {
6875
DispatchTable* BuildTable();
6976

7077
private:
78+
void ReadTableSelectorInfo();
7179
void NumberSelectors();
7280
void SetupSelectorRows();
7381
void ComputeSelectorOffsets();

‎runtime/vm/compiler/frontend/kernel_translation_helper.cc‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1824,6 +1824,35 @@ CallSiteAttributesMetadataHelper::GetCallSiteAttributes(intptr_t node_offset) {
18241824
return metadata;
18251825
}
18261826

1827+
TableSelectorMetadataHelper::TableSelectorMetadataHelper(
1828+
KernelReaderHelper* helper)
1829+
: MetadataHelper(helper, tag(), /* precompiler_only = */ true) {}
1830+
1831+
TableSelectorMetadata* TableSelectorMetadataHelper::GetTableSelectorMetadata(
1832+
Zone* zone) {
1833+
const intptr_t node_offset = GetComponentMetadataPayloadOffset();
1834+
const intptr_t md_offset = GetNextMetadataPayloadOffset(node_offset);
1835+
if (md_offset < 0) {
1836+
return nullptr;
1837+
}
1838+
1839+
AlternativeReadingScopeWithNewData alt(&helper_->reader_,
1840+
&H.metadata_payloads(), md_offset);
1841+
1842+
const intptr_t num_selectors = helper_->ReadUInt();
1843+
TableSelectorMetadata* metadata =
1844+
new (zone) TableSelectorMetadata(num_selectors);
1845+
for (intptr_t i = 0; i < num_selectors; i++) {
1846+
ReadTableSelectorInfo(&metadata->selectors[i]);
1847+
}
1848+
return metadata;
1849+
}
1850+
1851+
void TableSelectorMetadataHelper::ReadTableSelectorInfo(
1852+
TableSelectorInfo* info) {
1853+
info->call_count = helper_->ReadUInt();
1854+
}
1855+
18271856
intptr_t KernelReaderHelper::ReaderOffset() const {
18281857
return reader_.offset();
18291858
}

‎runtime/vm/compiler/frontend/kernel_translation_helper.h‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1027,6 +1027,39 @@ class CallSiteAttributesMetadataHelper : public MetadataHelper {
10271027
DISALLOW_COPY_AND_ASSIGN(CallSiteAttributesMetadataHelper);
10281028
};
10291029

1030+
// Information about a table selector computed by the TFA.
1031+
struct TableSelectorInfo {
1032+
int call_count = 0;
1033+
};
1034+
1035+
// Collection of table selector information for all selectors in the program.
1036+
class TableSelectorMetadata : public ZoneAllocated {
1037+
public:
1038+
explicit TableSelectorMetadata(intptr_t num_selectors)
1039+
: selectors(num_selectors) {
1040+
selectors.FillWith(TableSelectorInfo(), 0, num_selectors);
1041+
}
1042+
1043+
GrowableArray<TableSelectorInfo> selectors;
1044+
1045+
DISALLOW_COPY_AND_ASSIGN(TableSelectorMetadata);
1046+
};
1047+
1048+
// Helper class which provides access to table selector metadata.
1049+
class TableSelectorMetadataHelper : public MetadataHelper {
1050+
public:
1051+
static const char* tag() { return "vm.table-selector.metadata"; }
1052+
1053+
explicit TableSelectorMetadataHelper(KernelReaderHelper* helper);
1054+
1055+
TableSelectorMetadata* GetTableSelectorMetadata(Zone* zone);
1056+
1057+
private:
1058+
void ReadTableSelectorInfo(TableSelectorInfo* info);
1059+
1060+
DISALLOW_COPY_AND_ASSIGN(TableSelectorMetadataHelper);
1061+
};
1062+
10301063
class KernelReaderHelper {
10311064
public:
10321065
KernelReaderHelper(Zone* zone,
@@ -1162,6 +1195,7 @@ class KernelReaderHelper {
11621195
friend class ProcedureHelper;
11631196
friend class SimpleExpressionConverter;
11641197
friend class ScopeBuilder;
1198+
friend class TableSelectorMetadataHelper;
11651199
friend class TypeParameterHelper;
11661200
friend class TypeTranslator;
11671201
friend class VariableDeclarationHelper;

0 commit comments

Comments
 (0)