pkg/vm_snapshot_analysis/lib/precompiler_trace.dart - sdk.git - Git at Google

 // 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/src/dominators.dart' as dominators;
 import 'package:vm_snapshot_analysis/name.dart';
 import 'package:vm_snapshot_analysis/program_info.dart';

 /// Build [CallGraph] based on the trace written by `--trace-precompiler-to`
 /// flag.
 CallGraph loadTrace(Object inputJson) => _TraceReader(inputJson).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 data;

   /// Dominator of this node.
   ///
   /// Computed by [CallGraph.computeDominators].
   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<Object> trace;
   final List<Object> strings;
   final List<Object> 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 = Set<ProgramInfoNode>();

   _TraceReader(Map<String, dynamic> data)
       : strings = data['strings'],
         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.
     CallGraphNode currentNode;

     final nodes = <CallGraphNode>[];
     final nodeByEntityId = <CallGraphNode>[];
     final callNodesBySelector = <dynamic, CallGraphNode>{};
     final allocated = Set<ProgramInfoNode>();

     Object next() => trace[pos++];

     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;
       }
       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];
     switch (type) {
       case 'C': // Class: 'C', <library-uri-idx>, <name-idx>, 0
         final libraryUri = strings[entities[index + 1]];
         final className = strings[entities[index + 2]];

         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(entities[index + 1]);
         final functionName = strings[entities[index + 2]];
         final int selectorId = entities[index + 3];

         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(entities[index + 1]);
         final fieldName = strings[entities[index + 2]];

         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;
 }
	// 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/src/dominators.dart' as dominators;
	import 'package:vm_snapshot_analysis/name.dart';
	import 'package:vm_snapshot_analysis/program_info.dart';

	/// Build [CallGraph] based on the trace written by `--trace-precompiler-to`
	/// flag.
	CallGraph loadTrace(Object inputJson) => _TraceReader(inputJson).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 data;

	/// Dominator of this node.
	///
	/// Computed by [CallGraph.computeDominators].
	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<Object> trace;
	final List<Object> strings;
	final List<Object> 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 = Set<ProgramInfoNode>();

	_TraceReader(Map<String, dynamic> data)
	: strings = data['strings'],
	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.
	CallGraphNode currentNode;

	final nodes = <CallGraphNode>[];
	final nodeByEntityId = <CallGraphNode>[];
	final callNodesBySelector = <dynamic, CallGraphNode>{};
	final allocated = Set<ProgramInfoNode>();

	Object next() => trace[pos++];

	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;
	}
	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];
	switch (type) {
	case 'C': // Class: 'C', <library-uri-idx>, <name-idx>, 0
	final libraryUri = strings[entities[index + 1]];
	final className = strings[entities[index + 2]];

	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(entities[index + 1]);
	final functionName = strings[entities[index + 2]];
	final int selectorId = entities[index + 3];

	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(entities[index + 1]);
	final fieldName = strings[entities[index + 2]];

	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;
	}