blob: 06e80763d99b6ec6fee330de26ad05ad733fad3c [file] [log] [blame]
// Copyright (c) 2020, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
/// Helpers for working with the output of `--trace-precompiler-to` VM flag.
library vm_snapshot_analysis.precompiler_trace;
import 'package:vm_snapshot_analysis/name.dart';
import 'package:vm_snapshot_analysis/program_info.dart';
import 'package:vm_snapshot_analysis/src/dominators.dart' as dominators;
/// Build [CallGraph] based on the trace written by `--trace-precompiler-to`
/// flag.
CallGraph loadTrace(Object inputJson) =>
_TraceReader(inputJson as Map<String, dynamic>).readTrace();
/// [CallGraphNode] represents a node of the call-graph. It can either be:
///
/// - a function, in which case [data] will be [ProgramInfoNode] of type
/// [NodeType.functionNode];
/// - a dynamic call node, in which case [data] will be a [String] selector;
/// - a dispatch table call node, in which case [data] will be an [int]
/// selector id.
///
class CallGraphNode {
/// An index of this node in [CallGraph.nodes].
final int id;
/// Successors of this node.
final List<CallGraphNode> succ = [];
/// Predecessors of this node.
final List<CallGraphNode> pred = [];
/// Datum associated with this node: a [ProgramInfoNode] (function), a
/// [String] (dynamic call selector) or an [int] (dispatch table selector id).
final dynamic data;
/// Dominator of this node.
///
/// Computed by [CallGraph.computeDominators].
late CallGraphNode dominator;
/// Nodes dominated by this node.
///
/// Computed by [CallGraph.computeDominators].
List<CallGraphNode> dominated = _emptyNodeList;
CallGraphNode(this.id, {this.data});
bool get isFunctionNode =>
data is ProgramInfoNode && data.type == NodeType.functionNode;
bool get isClassNode =>
data is ProgramInfoNode && data.type == NodeType.classNode;
bool get isDynamicCallNode => data is String;
/// Create outgoing edge from this node to the given node [n].
void connectTo(CallGraphNode n) {
if (n == this) {
return;
}
if (!succ.contains(n)) {
n.pred.add(this);
succ.add(n);
}
}
void _addDominatedBlock(CallGraphNode n) {
if (identical(dominated, _emptyNodeList)) {
dominated = [];
}
dominated.add(n);
n.dominator = this;
}
void visitDominatorTree(bool Function(CallGraphNode n, int depth) callback,
[int depth = 0]) {
if (callback(this, depth)) {
for (var n in dominated) {
n.visitDominatorTree(callback, depth + 1);
}
}
}
@override
String toString() {
return 'CallGraphNode(${data is ProgramInfoNode ? data.qualifiedName : data})';
}
}
const _emptyNodeList = <CallGraphNode>[];
class CallGraph {
final ProgramInfo program;
final List<CallGraphNode> nodes;
// Mapping from [ProgramInfoNode] to a corresponding [CallGraphNode] (if any)
// via [ProgramInfoNode.id].
final List<CallGraphNode?> _graphNodeByEntityId;
CallGraph._(this.program, this.nodes, this._graphNodeByEntityId);
CallGraphNode get root => nodes.first;
CallGraphNode lookup(ProgramInfoNode node) => _graphNodeByEntityId[node.id]!;
Iterable<CallGraphNode> get dynamicCalls =>
nodes.where((n) => n.isDynamicCallNode);
/// Compute a collapsed version of the call-graph, where
CallGraph collapse(NodeType type, {bool dropCallNodes = false}) {
final graphNodesByData = <Object, CallGraphNode>{};
final graphNodeByEntityId = <CallGraphNode?>[];
ProgramInfoNode collapsed(ProgramInfoNode nn) {
// Root always collapses onto itself.
if (nn == program.root) {
return nn;
}
// Even though all code is grouped into libraries, not all libraries
// are grouped into packages (e.g. dart:* libraries). Meaning
// that if we are collapsing by package we need to stop right before
// hitting the root node.
var n = nn;
while (n.parent != program.root && n.type != type) {
n = n.parent!;
}
return n;
}
CallGraphNode callGraphNodeFor(Object data) {
return graphNodesByData.putIfAbsent(data, () {
final n = CallGraphNode(graphNodesByData.length, data: data);
if (data is ProgramInfoNode) {
if (graphNodeByEntityId.length <= data.id) {
graphNodeByEntityId.length = data.id * 2 + 1;
}
graphNodeByEntityId[data.id] = n;
}
return n;
});
}
final newNodes = nodes.map((n) {
if (n.data is ProgramInfoNode) {
return callGraphNodeFor(collapsed(n.data));
} else if (!dropCallNodes) {
return callGraphNodeFor(n.data);
}
}).toList(growable: false);
for (var n in nodes) {
for (var succ in n.succ) {
final from = newNodes[n.id];
final to = newNodes[succ.id];
if (from != null && to != null) {
from.connectTo(to);
}
}
}
return CallGraph._(program, graphNodesByData.values.toList(growable: false),
graphNodeByEntityId);
}
/// Compute dominator tree of the call-graph.
void computeDominators() {
final dom = dominators.computeDominators(
size: nodes.length,
root: nodes.first.id,
succ: (i) => nodes[i].succ.map((n) => n.id),
predOf: (i) => nodes[i].pred.map((n) => n.id),
handleEdge: (from, to) {});
for (var i = 1; i < nodes.length; i++) {
nodes[dom[i]]._addDominatedBlock(nodes[i]);
}
}
}
/// Helper class for reading `--trace-precompiler-to` output.
///
/// See README.md for description of the format.
class _TraceReader {
final List<dynamic> trace;
final List<String> strings;
final List<dynamic> entities;
final program = ProgramInfo();
/// Mapping between entity ids and corresponding [ProgramInfoNode] nodes.
final entityById = List<ProgramInfoNode?>.filled(1024, null, growable: true);
/// Mapping between functions (represented as [ProgramInfoNode]s) and
/// their selector ids.
final selectorIdMap = <ProgramInfoNode, int>{};
/// Set of functions which can be reached through dynamic dispatch.
final dynamicFunctions = <ProgramInfoNode>{};
_TraceReader(Map<String, dynamic> data)
: strings = (data['strings'] as List<dynamic>).cast<String>(),
entities = data['entities'],
trace = data['trace'];
/// Read all trace events and construct the call graph based on them.
CallGraph readTrace() {
var pos = 0; // Position in the [trace] array.
late CallGraphNode currentNode;
int maxId = 0;
final nodes = <CallGraphNode>[];
final nodeByEntityId = <CallGraphNode?>[];
final callNodesBySelector = <dynamic, CallGraphNode>{};
final allocated = <ProgramInfoNode>{};
T next<T>() => trace[pos++] as T;
CallGraphNode makeNode({dynamic data}) {
final n = CallGraphNode(nodes.length, data: data);
nodes.add(n);
return n;
}
CallGraphNode makeCallNode(dynamic selector) => callNodesBySelector
.putIfAbsent(selector, () => makeNode(data: selector));
CallGraphNode nodeFor(ProgramInfoNode n) {
if (nodeByEntityId.length <= n.id) {
nodeByEntityId.length = n.id * 2 + 1;
}
if (n.id > maxId) {
maxId = n.id;
}
return nodeByEntityId[n.id] ??= makeNode(data: n);
}
void recordDynamicCall(String selector) {
currentNode.connectTo(makeCallNode(selector));
}
void recordInterfaceCall(int selector) {
currentNode.connectTo(makeCallNode(selector));
}
void recordStaticCall(ProgramInfoNode to) {
currentNode.connectTo(nodeFor(to));
}
void recordFieldRef(ProgramInfoNode field) {
currentNode.connectTo(nodeFor(field));
}
void recordAllocation(ProgramInfoNode cls) {
currentNode.connectTo(nodeFor(cls));
allocated.add(cls);
}
bool readRef() {
final ref = next();
if (ref is int) {
final entity = getEntityAt(ref);
if (entity.type == NodeType.classNode) {
recordAllocation(entity);
} else if (entity.type == NodeType.functionNode) {
recordStaticCall(entity);
} else if (entity.type == NodeType.other) {
recordFieldRef(entity);
}
} else if (ref == 'S') {
final String selector = strings[next()];
recordDynamicCall(selector);
} else if (ref == 'T') {
recordInterfaceCall(next());
} else if (ref == 'C' || ref == 'E') {
pos--;
return false;
} else {
throw FormatException('unexpected ref: $ref');
}
return true;
}
void readRefs() {
while (readRef()) {}
}
void readEvents() {
while (true) {
final op = next();
switch (op) {
case 'E': // End.
return;
case 'R': // Roots.
currentNode = nodeFor(program.root);
readRefs();
break;
case 'C': // Function compilation.
currentNode = nodeFor(getEntityAt(next()));
readRefs();
break;
default:
throw FormatException('Unknown event: $op at ${pos - 1}');
}
}
}
readEvents();
// Finally connect nodes representing dynamic and dispatch table calls
// to their potential targets.
for (var cls in allocated) {
for (var fun in cls.children.values.where(dynamicFunctions.contains)) {
final funNode = nodeFor(fun);
callNodesBySelector[selectorIdMap[fun]]?.connectTo(funNode);
final name = fun.name;
callNodesBySelector[name]?.connectTo(funNode);
const dynPrefix = 'dyn:';
const getterPrefix = 'get:';
const extractorPrefix = '[tear-off-extractor] ';
if (!name.startsWith(dynPrefix)) {
// Normal methods can be hit by dyn: selectors if the class
// does not contain a dedicated dyn: forwarder for this name.
if (!cls.children.containsKey('$dynPrefix$name')) {
callNodesBySelector['$dynPrefix$name']?.connectTo(funNode);
}
if (name.startsWith(getterPrefix)) {
// Handle potential calls through getters: getter get:foo can be
// hit by dyn:foo and foo selectors.
final targetName = name.substring(getterPrefix.length);
callNodesBySelector[targetName]?.connectTo(funNode);
callNodesBySelector['$dynPrefix$targetName']?.connectTo(funNode);
} else if (name.startsWith(extractorPrefix)) {
// Handle method tear-off: [tear-off-extractor] get:foo can be hit
// by dyn:get:foo and get:foo.
final targetName = name.substring(extractorPrefix.length);
callNodesBySelector[targetName]?.connectTo(funNode);
callNodesBySelector['$dynPrefix$targetName']?.connectTo(funNode);
}
}
}
}
return CallGraph._(program, nodes, nodeByEntityId);
}
/// Return [ProgramInfoNode] representing the entity with the given [id].
ProgramInfoNode getEntityAt(int id) {
if (entityById.length <= id) {
entityById.length = id * 2;
}
// Entity records have fixed size which allows us to perform random access.
const elementsPerEntity = 4;
return entityById[id] ??= readEntityAt(id * elementsPerEntity);
}
/// Read the entity at the given [index] in [entities].
ProgramInfoNode readEntityAt(int index) {
final type = entities[index];
final idx0 = entities[index + 1] as int;
final idx1 = entities[index + 2] as int;
final idx2 = entities[index + 3] as int;
switch (type) {
case 'C': // Class: 'C', <library-uri-idx>, <name-idx>, 0
final libraryUri = strings[idx0];
final className = strings[idx1];
return program.makeNode(
name: className,
parent: getLibraryNode(libraryUri),
type: NodeType.classNode);
case 'S':
case 'F': // Function: 'F'|'S', <class-idx>, <name-idx>, <selector-id>
final classNode = getEntityAt(idx0);
final functionName = strings[idx1];
final int selectorId = idx2;
final path = Name(functionName).rawComponents;
if (path.last == 'FfiTrampoline') {
path[path.length - 1] = '${path.last}@$index';
}
var node = program.makeNode(
name: path.first, parent: classNode, type: NodeType.functionNode);
for (var name in path.skip(1)) {
node = program.makeNode(
name: name, parent: node, type: NodeType.functionNode);
}
if (selectorId >= 0) {
selectorIdMap[node] = selectorId;
}
if (type == 'F') {
dynamicFunctions.add(node);
}
return node;
case 'V': // Field: 'V', <class-idx>, <name-idx>, 0
final classNode = getEntityAt(idx0);
final fieldName = strings[idx1];
return program.makeNode(
name: fieldName, parent: classNode, type: NodeType.other);
default:
throw FormatException('unrecognized entity type $type');
}
}
ProgramInfoNode getLibraryNode(String libraryUri) {
final package = packageOf(libraryUri);
var node = program.root;
if (package != libraryUri) {
node = program.makeNode(
name: package, parent: node, type: NodeType.packageNode);
}
return program.makeNode(
name: libraryUri, parent: node, type: NodeType.libraryNode);
}
}
/// Generates a [CallGraph] from the given [precompilerTrace], which is produced
/// by `--trace-precompiler-to`, then collapses it down to the granularity
/// specified by [nodeType], and computes dominators of the resulting graph.
CallGraph generateCallGraphWithDominators(
Object precompilerTrace,
NodeType nodeType,
) {
var callGraph = loadTrace(precompilerTrace);
// Convert call graph into the approximate dependency graph, dropping any
// dynamic and dispatch table based dependencies from the graph and only
// following the static call, field access and allocation edges.
callGraph = callGraph.collapse(nodeType, dropCallNodes: true)
..computeDominators();
return callGraph;
}