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 'dart:math' as math;

 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;

   /// Preorder number of this node.
   ///
   /// Computed by [CallGraph.computeDominators].
   int _preorderNumber;

   /// 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> _nodeByEntityId;

   CallGraph._(this.program, this.nodes, this._nodeByEntityId);

   CallGraphNode get root => nodes.first;

   CallGraphNode lookup(ProgramInfoNode node) => _nodeByEntityId[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 nodesByData = <Object, CallGraphNode>{};
     final nodeByEntityId = <CallGraphNode>[];

     ProgramInfoNode collapsed(ProgramInfoNode nn) {
       var n = nn;
       while (n.parent != null && n.type != type) {
         n = n.parent;
       }
       return n;
     }

     CallGraphNode nodeFor(Object data) {
       return nodesByData.putIfAbsent(data, () {
         final n = CallGraphNode(nodesByData.length, data: data);
         if (data is ProgramInfoNode) {
           if (nodeByEntityId.length <= data.id) {
             nodeByEntityId.length = data.id * 2 + 1;
           }
           nodeByEntityId[data.id] = n;
         }
         return n;
       });
     }

     final newNodes = nodes.map((n) {
       if (n.data is ProgramInfoNode) {
         return nodeFor(collapsed(n.data));
       } else if (!dropCallNodes) {
         return nodeFor(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, nodesByData.values.toList(growable: false), nodeByEntityId);
   }

   /// Compute dominator tree of the call-graph.
   ///
   /// The code for dominator tree computation is taken verbatim from the
   /// native compiler (see runtime/vm/compiler/backend/flow_graph.cc).
   void computeDominators() {
     final size = nodes.length;

     // Compute preorder numbering for the graph using DFS.
     final parent = List<int>.filled(size, -1);
     final preorder = List<CallGraphNode>.filled(size, null);

     var N = 0;
     void dfs() {
       final stack = [_DfsState(p: -1, n: nodes.first)];
       while (stack.isNotEmpty) {
         final s = stack.removeLast();
         final p = s.p;
         final n = s.n;
         if (n._preorderNumber == null) {
           n._preorderNumber = N;
           preorder[n._preorderNumber] = n;
           parent[n._preorderNumber] = p;

           for (var w in n.succ) {
             stack.add(_DfsState(p: n._preorderNumber, n: w));
           }

           N++;
         }
       }
     }

     dfs();

     for (var node in nodes) {
       if (node._preorderNumber == null) {
         print('${node} is unreachable');
       }
     }

     // Use the SEMI-NCA algorithm to compute dominators.  This is a two-pass
     // version of the Lengauer-Tarjan algorithm (LT is normally three passes)
     // that eliminates a pass by using nearest-common ancestor (NCA) to
     // compute immediate dominators from semidominators.  It also removes a
     // level of indirection in the link-eval forest data structure.
     //
     // The algorithm is described in Georgiadis, Tarjan, and Werneck's
     // "Finding Dominators in Practice".
     // See http://www.cs.princeton.edu/~rwerneck/dominators/ .

     // All arrays are maps between preorder basic-block numbers.
     final idom = parent.toList(); // Immediate dominator.
     final semi = List<int>.generate(size, (i) => i); // Semidominator.
     final label =
         List<int>.generate(size, (i) => i); // Label for link-eval forest.

     void compressPath(int start, int current) {
       final next = parent[current];
       if (next > start) {
         compressPath(start, next);
         label[current] = math.min(label[current], label[next]);
         parent[current] = parent[next];
       }
     }

     // 1. First pass: compute semidominators as in Lengauer-Tarjan.
     // Semidominators are computed from a depth-first spanning tree and are an
     // approximation of immediate dominators.

     // Use a link-eval data structure with path compression.  Implement path
     // compression in place by mutating the parent array.  Each block has a
     // label, which is the minimum block number on the compressed path.

     // Loop over the blocks in reverse preorder (not including the graph
     // entry).
     for (var block_index = size - 1; block_index >= 1; --block_index) {
       // Loop over the predecessors.
       final block = preorder[block_index];
       // Clear the immediately dominated blocks in case ComputeDominators is
       // used to recompute them.
       for (final pred in block.pred) {
         // Look for the semidominator by ascending the semidominator path
         // starting from pred.
         final pred_index = pred._preorderNumber;
         var best = pred_index;
         if (pred_index > block_index) {
           compressPath(block_index, pred_index);
           best = label[pred_index];
         }

         // Update the semidominator if we've found a better one.
         semi[block_index] = math.min(semi[block_index], semi[best]);
       }

       // Now use label for the semidominator.
       label[block_index] = semi[block_index];
     }

     // 2. Compute the immediate dominators as the nearest common ancestor of
     // spanning tree parent and semidominator, for all blocks except the entry.
     for (var block_index = 1; block_index < size; ++block_index) {
       var dom_index = idom[block_index];
       while (dom_index > semi[block_index]) {
         dom_index = idom[dom_index];
       }
       idom[block_index] = dom_index;
       preorder[dom_index]._addDominatedBlock(preorder[block_index]);
     }
   }
 }

 class _DfsState {
   final int p;
   final CallGraphNode n;
   _DfsState({this.p, this.n});
 }

 /// 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);
   }
 }
	// 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 'dart:math' as math;

	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;

	/// Preorder number of this node.
	///
	/// Computed by [CallGraph.computeDominators].
	int _preorderNumber;

	/// 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> _nodeByEntityId;

	CallGraph._(this.program, this.nodes, this._nodeByEntityId);

	CallGraphNode get root => nodes.first;

	CallGraphNode lookup(ProgramInfoNode node) => _nodeByEntityId[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 nodesByData = <Object, CallGraphNode>{};
	final nodeByEntityId = <CallGraphNode>[];

	ProgramInfoNode collapsed(ProgramInfoNode nn) {
	var n = nn;
	while (n.parent != null && n.type != type) {
	n = n.parent;
	}
	return n;
	}

	CallGraphNode nodeFor(Object data) {
	return nodesByData.putIfAbsent(data, () {
	final n = CallGraphNode(nodesByData.length, data: data);
	if (data is ProgramInfoNode) {
	if (nodeByEntityId.length <= data.id) {
	nodeByEntityId.length = data.id * 2 + 1;
	}
	nodeByEntityId[data.id] = n;
	}
	return n;
	});
	}

	final newNodes = nodes.map((n) {
	if (n.data is ProgramInfoNode) {
	return nodeFor(collapsed(n.data));
	} else if (!dropCallNodes) {
	return nodeFor(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, nodesByData.values.toList(growable: false), nodeByEntityId);
	}

	/// Compute dominator tree of the call-graph.
	///
	/// The code for dominator tree computation is taken verbatim from the
	/// native compiler (see runtime/vm/compiler/backend/flow_graph.cc).
	void computeDominators() {
	final size = nodes.length;

	// Compute preorder numbering for the graph using DFS.
	final parent = List<int>.filled(size, -1);
	final preorder = List<CallGraphNode>.filled(size, null);

	var N = 0;
	void dfs() {
	final stack = [_DfsState(p: -1, n: nodes.first)];
	while (stack.isNotEmpty) {
	final s = stack.removeLast();
	final p = s.p;
	final n = s.n;
	if (n._preorderNumber == null) {
	n._preorderNumber = N;
	preorder[n._preorderNumber] = n;
	parent[n._preorderNumber] = p;

	for (var w in n.succ) {
	stack.add(_DfsState(p: n._preorderNumber, n: w));
	}

	N++;
	}
	}
	}

	dfs();

	for (var node in nodes) {
	if (node._preorderNumber == null) {
	print('${node} is unreachable');
	}
	}

	// Use the SEMI-NCA algorithm to compute dominators. This is a two-pass
	// version of the Lengauer-Tarjan algorithm (LT is normally three passes)
	// that eliminates a pass by using nearest-common ancestor (NCA) to
	// compute immediate dominators from semidominators. It also removes a
	// level of indirection in the link-eval forest data structure.
	//
	// The algorithm is described in Georgiadis, Tarjan, and Werneck's
	// "Finding Dominators in Practice".
	// See http://www.cs.princeton.edu/~rwerneck/dominators/ .

	// All arrays are maps between preorder basic-block numbers.
	final idom = parent.toList(); // Immediate dominator.
	final semi = List<int>.generate(size, (i) => i); // Semidominator.
	final label =
	List<int>.generate(size, (i) => i); // Label for link-eval forest.

	void compressPath(int start, int current) {
	final next = parent[current];
	if (next > start) {
	compressPath(start, next);
	label[current] = math.min(label[current], label[next]);
	parent[current] = parent[next];
	}
	}

	// 1. First pass: compute semidominators as in Lengauer-Tarjan.
	// Semidominators are computed from a depth-first spanning tree and are an
	// approximation of immediate dominators.

	// Use a link-eval data structure with path compression. Implement path
	// compression in place by mutating the parent array. Each block has a
	// label, which is the minimum block number on the compressed path.

	// Loop over the blocks in reverse preorder (not including the graph
	// entry).
	for (var block_index = size - 1; block_index >= 1; --block_index) {
	// Loop over the predecessors.
	final block = preorder[block_index];
	// Clear the immediately dominated blocks in case ComputeDominators is
	// used to recompute them.
	for (final pred in block.pred) {
	// Look for the semidominator by ascending the semidominator path
	// starting from pred.
	final pred_index = pred._preorderNumber;
	var best = pred_index;
	if (pred_index > block_index) {
	compressPath(block_index, pred_index);
	best = label[pred_index];
	}

	// Update the semidominator if we've found a better one.
	semi[block_index] = math.min(semi[block_index], semi[best]);
	}

	// Now use label for the semidominator.
	label[block_index] = semi[block_index];
	}

	// 2. Compute the immediate dominators as the nearest common ancestor of
	// spanning tree parent and semidominator, for all blocks except the entry.
	for (var block_index = 1; block_index < size; ++block_index) {
	var dom_index = idom[block_index];
	while (dom_index > semi[block_index]) {
	dom_index = idom[dom_index];
	}
	idom[block_index] = dom_index;
	preorder[dom_index]._addDominatedBlock(preorder[block_index]);
	}
	}
	}

	class _DfsState {
	final int p;
	final CallGraphNode n;
	_DfsState({this.p, this.n});
	}

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