src/v8/tools/turbolizer/src/source-resolver.ts - cobalt - Git at Google

 // Copyright 2018 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.

 import { sortUnique, anyToString } from "../src/util";
 import { NodeLabel } from "./node-label";

 function sourcePositionLe(a, b) {
   if (a.inliningId == b.inliningId) {
     return a.scriptOffset - b.scriptOffset;
   }
   return a.inliningId - b.inliningId;
 }

 function sourcePositionEq(a, b) {
   return a.inliningId == b.inliningId &&
     a.scriptOffset == b.scriptOffset;
 }

 export function sourcePositionToStringKey(sourcePosition: AnyPosition): string {
   if (!sourcePosition) return "undefined";
   if ('inliningId' in sourcePosition && 'scriptOffset' in sourcePosition) {
     return "SP:" + sourcePosition.inliningId + ":" + sourcePosition.scriptOffset;
   }
   if (sourcePosition.bytecodePosition) {
     return "BCP:" + sourcePosition.bytecodePosition;
   }
   return "undefined";
 }

 export function sourcePositionValid(l) {
   return (typeof l.scriptOffset !== undefined
     && typeof l.inliningId !== undefined) || typeof l.bytecodePosition != undefined;
 }

 export interface SourcePosition {
   scriptOffset: number;
   inliningId: number;
 }

 interface TurboFanOrigin {
   phase: string;
   reducer: string;
 }

 export interface NodeOrigin {
   nodeId: number;
 }

 interface BytecodePosition {
   bytecodePosition: number;
 }

 export type Origin = NodeOrigin | BytecodePosition;
 export type TurboFanNodeOrigin = NodeOrigin & TurboFanOrigin;
 export type TurboFanBytecodeOrigin = BytecodePosition & TurboFanOrigin;

 type AnyPosition = SourcePosition | BytecodePosition;

 export interface Source {
   sourcePositions: Array<SourcePosition>;
   sourceName: string;
   functionName: string;
   sourceText: string;
   sourceId: number;
   startPosition?: number;
   backwardsCompatibility: boolean;
 }
 interface Inlining {
   inliningPosition: SourcePosition;
   sourceId: number;
 }
 interface OtherPhase {
   type: "disassembly" | "sequence" | "schedule";
   name: string;
   data: any;
 }

 interface InstructionsPhase {
   type: "instructions";
   name: string;
   data: any;
   instructionOffsetToPCOffset?: any;
   blockIdtoInstructionRange?: any;
   nodeIdToInstructionRange?: any;
 }

 interface GraphPhase {
   type: "graph";
   name: string;
   data: any;
   highestNodeId: number;
   nodeLabelMap: Array<NodeLabel>;
 }

 type Phase = GraphPhase | InstructionsPhase | OtherPhase;

 export interface Schedule {
   nodes: Array<any>;
 }

 export interface Sequence {
   blocks: Array<any>;
 }

 export class SourceResolver {
   nodePositionMap: Array<AnyPosition>;
   sources: Array<Source>;
   inlinings: Array<Inlining>;
   inliningsMap: Map<string, Inlining>;
   positionToNodes: Map<string, Array<string>>;
   phases: Array<Phase>;
   phaseNames: Map<string, number>;
   disassemblyPhase: Phase;
   lineToSourcePositions: Map<string, Array<AnyPosition>>;
   nodeIdToInstructionRange: Array<[number, number]>;
   blockIdToInstructionRange: Array<[number, number]>;
   instructionToPCOffset: Array<number>;
   pcOffsetToInstructions: Map<number, Array<number>>;
   pcOffsets: Array<number>;

   constructor() {
     // Maps node ids to source positions.
     this.nodePositionMap = [];
     // Maps source ids to source objects.
     this.sources = [];
     // Maps inlining ids to inlining objects.
     this.inlinings = [];
     // Maps source position keys to inlinings.
     this.inliningsMap = new Map();
     // Maps source position keys to node ids.
     this.positionToNodes = new Map();
     // Maps phase ids to phases.
     this.phases = [];
     // Maps phase names to phaseIds.
     this.phaseNames = new Map();
     // The disassembly phase is stored separately.
     this.disassemblyPhase = undefined;
     // Maps line numbers to source positions
     this.lineToSourcePositions = new Map();
     // Maps node ids to instruction ranges.
     this.nodeIdToInstructionRange = [];
     // Maps block ids to instruction ranges.
     this.blockIdToInstructionRange = [];
     // Maps instruction numbers to PC offsets.
     this.instructionToPCOffset = [];
     // Maps PC offsets to instructions.
     this.pcOffsetToInstructions = new Map();
     this.pcOffsets = [];
   }

   setSources(sources, mainBackup) {
     if (sources) {
       for (const [sourceId, source] of Object.entries(sources)) {
         this.sources[sourceId] = source;
         this.sources[sourceId].sourcePositions = [];
       }
     }
     // This is a fallback if the JSON is incomplete (e.g. due to compiler crash).
     if (!this.sources[-1]) {
       this.sources[-1] = mainBackup;
       this.sources[-1].sourcePositions = [];
     }
   }

   setInlinings(inlinings) {
     if (inlinings) {
       for (const [inliningId, inlining] of Object.entries<Inlining>(inlinings)) {
         this.inlinings[inliningId] = inlining;
         this.inliningsMap.set(sourcePositionToStringKey(inlining.inliningPosition), inlining);
       }
     }
     // This is a default entry for the script itself that helps
     // keep other code more uniform.
     this.inlinings[-1] = { sourceId: -1, inliningPosition: null };
   }

   setNodePositionMap(map) {
     if (!map) return;
     if (typeof map[0] != 'object') {
       const alternativeMap = {};
       for (const [nodeId, scriptOffset] of Object.entries<number>(map)) {
         alternativeMap[nodeId] = { scriptOffset: scriptOffset, inliningId: -1 };
       }
       map = alternativeMap;
     }

     for (const [nodeId, sourcePosition] of Object.entries<SourcePosition>(map)) {
       if (sourcePosition == undefined) {
         console.log("Warning: undefined source position ", sourcePosition, " for nodeId ", nodeId);
       }
       const inliningId = sourcePosition.inliningId;
       const inlining = this.inlinings[inliningId];
       if (inlining) {
         const sourceId = inlining.sourceId;
         this.sources[sourceId].sourcePositions.push(sourcePosition);
       }
       this.nodePositionMap[nodeId] = sourcePosition;
       const key = sourcePositionToStringKey(sourcePosition);
       if (!this.positionToNodes.has(key)) {
         this.positionToNodes.set(key, []);
       }
       this.positionToNodes.get(key).push(nodeId);
     }
     for (const [, source] of Object.entries(this.sources)) {
       source.sourcePositions = sortUnique(source.sourcePositions,
         sourcePositionLe, sourcePositionEq);
     }
   }

   sourcePositionsToNodeIds(sourcePositions) {
     const nodeIds = new Set();
     for (const sp of sourcePositions) {
       const key = sourcePositionToStringKey(sp);
       const nodeIdsForPosition = this.positionToNodes.get(key);
       if (!nodeIdsForPosition) continue;
       for (const nodeId of nodeIdsForPosition) {
         nodeIds.add(nodeId);
       }
     }
     return nodeIds;
   }

   nodeIdsToSourcePositions(nodeIds): Array<AnyPosition> {
     const sourcePositions = new Map();
     for (const nodeId of nodeIds) {
       const sp = this.nodePositionMap[nodeId];
       const key = sourcePositionToStringKey(sp);
       sourcePositions.set(key, sp);
     }
     const sourcePositionArray = [];
     for (const sp of sourcePositions.values()) {
       sourcePositionArray.push(sp);
     }
     return sourcePositionArray;
   }

   forEachSource(f: (value: Source, index: number, array: Array<Source>) => void) {
     this.sources.forEach(f);
   }

   translateToSourceId(sourceId: number, location?: SourcePosition) {
     for (const position of this.getInlineStack(location)) {
       const inlining = this.inlinings[position.inliningId];
       if (!inlining) continue;
       if (inlining.sourceId == sourceId) {
         return position;
       }
     }
     return location;
   }

   addInliningPositions(sourcePosition: AnyPosition, locations: Array<SourcePosition>) {
     const inlining = this.inliningsMap.get(sourcePositionToStringKey(sourcePosition));
     if (!inlining) return;
     const sourceId = inlining.sourceId;
     const source = this.sources[sourceId];
     for (const sp of source.sourcePositions) {
       locations.push(sp);
       this.addInliningPositions(sp, locations);
     }
   }

   getInliningForPosition(sourcePosition: AnyPosition) {
     return this.inliningsMap.get(sourcePositionToStringKey(sourcePosition));
   }

   getSource(sourceId: number) {
     return this.sources[sourceId];
   }

   getSourceName(sourceId: number) {
     const source = this.sources[sourceId];
     return `${source.sourceName}:${source.functionName}`;
   }

   sourcePositionFor(sourceId: number, scriptOffset: number) {
     if (!this.sources[sourceId]) {
       return null;
     }
     const list = this.sources[sourceId].sourcePositions;
     for (let i = 0; i < list.length; i++) {
       const sourcePosition = list[i];
       const position = sourcePosition.scriptOffset;
       const nextPosition = list[Math.min(i + 1, list.length - 1)].scriptOffset;
       if ((position <= scriptOffset && scriptOffset < nextPosition)) {
         return sourcePosition;
       }
     }
     return null;
   }

   sourcePositionsInRange(sourceId: number, start: number, end: number) {
     if (!this.sources[sourceId]) return [];
     const res = [];
     const list = this.sources[sourceId].sourcePositions;
     for (const sourcePosition of list) {
       if (start <= sourcePosition.scriptOffset && sourcePosition.scriptOffset < end) {
         res.push(sourcePosition);
       }
     }
     return res;
   }

   getInlineStack(sourcePosition?: SourcePosition) {
     if (!sourcePosition) return [];

     const inliningStack = [];
     let cur = sourcePosition;
     while (cur && cur.inliningId != -1) {
       inliningStack.push(cur);
       const inlining = this.inlinings[cur.inliningId];
       if (!inlining) {
         break;
       }
       cur = inlining.inliningPosition;
     }
     if (cur && cur.inliningId == -1) {
       inliningStack.push(cur);
     }
     return inliningStack;
   }

   recordOrigins(phase: GraphPhase) {
     if (phase.type != "graph") return;
     for (const node of phase.data.nodes) {
       phase.highestNodeId = Math.max(phase.highestNodeId, node.id);
       if (node.origin != undefined &&
         node.origin.bytecodePosition != undefined) {
         const position = { bytecodePosition: node.origin.bytecodePosition };
         this.nodePositionMap[node.id] = position;
         const key = sourcePositionToStringKey(position);
         if (!this.positionToNodes.has(key)) {
           this.positionToNodes.set(key, []);
         }
         const A = this.positionToNodes.get(key);
         if (!A.includes(node.id)) A.push(`${node.id}`);
       }

       // Backwards compatibility.
       if (typeof node.pos === "number") {
         node.sourcePosition = { scriptOffset: node.pos, inliningId: -1 };
       }
     }
   }

   readNodeIdToInstructionRange(nodeIdToInstructionRange) {
     for (const [nodeId, range] of Object.entries<[number, number]>(nodeIdToInstructionRange)) {
       this.nodeIdToInstructionRange[nodeId] = range;
     }
   }

   readBlockIdToInstructionRange(blockIdToInstructionRange) {
     for (const [blockId, range] of Object.entries<[number, number]>(blockIdToInstructionRange)) {
       this.blockIdToInstructionRange[blockId] = range;
     }
   }

   getInstruction(nodeId: number): [number, number] {
     const X = this.nodeIdToInstructionRange[nodeId];
     if (X === undefined) return [-1, -1];
     return X;
   }

   getInstructionRangeForBlock(blockId: number): [number, number] {
     const X = this.blockIdToInstructionRange[blockId];
     if (X === undefined) return [-1, -1];
     return X;
   }

   readInstructionOffsetToPCOffset(instructionToPCOffset) {
     for (const [instruction, offset] of Object.entries<number>(instructionToPCOffset)) {
       this.instructionToPCOffset[instruction] = offset;
       if (!this.pcOffsetToInstructions.has(offset)) {
         this.pcOffsetToInstructions.set(offset, []);
       }
       this.pcOffsetToInstructions.get(offset).push(Number(instruction));
     }
     this.pcOffsets = Array.from(this.pcOffsetToInstructions.keys()).sort((a, b) => b - a);
   }

   hasPCOffsets() {
     return this.pcOffsetToInstructions.size > 0;
   }

   getKeyPcOffset(offset: number): number {
     if (this.pcOffsets.length === 0) return -1;
     for (const key of this.pcOffsets) {
       if (key <= offset) {
         return key;
       }
     }
     return -1;
   }

   instructionRangeToKeyPcOffsets([start, end]: [number, number]) {
     if (start == end) return [this.instructionToPCOffset[start]];
     return this.instructionToPCOffset.slice(start, end);
   }

   instructionsToKeyPcOffsets(instructionIds: Iterable<number>) {
     const keyPcOffsets = [];
     for (const instructionId of instructionIds) {
       keyPcOffsets.push(this.instructionToPCOffset[instructionId]);
     }
     return keyPcOffsets;
   }

   nodesToKeyPcOffsets(nodes) {
     let offsets = [];
     for (const node of nodes) {
       const range = this.nodeIdToInstructionRange[node];
       if (!range) continue;
       offsets = offsets.concat(this.instructionRangeToKeyPcOffsets(range));
     }
     return offsets;
   }

   nodesForPCOffset(offset: number): [Array<string>, Array<string>] {
     if (this.pcOffsets.length === 0) return [[], []];
     for (const key of this.pcOffsets) {
       if (key <= offset) {
         const instrs = this.pcOffsetToInstructions.get(key);
         const nodes = [];
         const blocks = [];
         for (const instr of instrs) {
           for (const [nodeId, range] of this.nodeIdToInstructionRange.entries()) {
             if (!range) continue;
             const [start, end] = range;
             if (start == end && instr == start) {
               nodes.push("" + nodeId);
             }
             if (start <= instr && instr < end) {
               nodes.push("" + nodeId);
             }
           }
         }
         return [nodes, blocks];
       }
     }
     return [[], []];
   }

   parsePhases(phases) {
     const nodeLabelMap = [];
     for (const [, phase] of Object.entries<Phase>(phases)) {
       switch (phase.type) {
         case 'disassembly':
           this.disassemblyPhase = phase;
           break;
         case 'schedule':
           this.phaseNames.set(phase.name, this.phases.length);
           this.phases.push(this.parseSchedule(phase));
           break;
         case 'sequence':
           this.phaseNames.set(phase.name, this.phases.length);
           this.phases.push(this.parseSequence(phase));
           break;
         case 'instructions':
           if (phase.nodeIdToInstructionRange) {
             this.readNodeIdToInstructionRange(phase.nodeIdToInstructionRange);
           }
           if (phase.blockIdtoInstructionRange) {
             this.readBlockIdToInstructionRange(phase.blockIdtoInstructionRange);
           }
           if (phase.instructionOffsetToPCOffset) {
             this.readInstructionOffsetToPCOffset(phase.instructionOffsetToPCOffset);
           }
           break;
         case 'graph':
           const graphPhase: GraphPhase = Object.assign(phase, { highestNodeId: 0 });
           this.phaseNames.set(graphPhase.name, this.phases.length);
           this.phases.push(graphPhase);
           this.recordOrigins(graphPhase);
           this.internNodeLabels(graphPhase, nodeLabelMap);
           graphPhase.nodeLabelMap = nodeLabelMap.slice();
           break;
         default:
           throw "Unsupported phase type";
       }
     }
   }

   internNodeLabels(phase: GraphPhase, nodeLabelMap: Array<NodeLabel>) {
     for (const n of phase.data.nodes) {
       const label = new NodeLabel(n.id, n.label, n.title, n.live,
         n.properties, n.sourcePosition, n.origin, n.opcode, n.control,
         n.opinfo, n.type);
       const previous = nodeLabelMap[label.id];
       if (!label.equals(previous)) {
         if (previous != undefined) {
           label.setInplaceUpdatePhase(phase.name);
         }
         nodeLabelMap[label.id] = label;
       }
       n.nodeLabel = nodeLabelMap[label.id];
     }
   }

   repairPhaseId(anyPhaseId) {
     return Math.max(0, Math.min(anyPhaseId | 0, this.phases.length - 1));
   }

   getPhase(phaseId: number) {
     return this.phases[phaseId];
   }

   getPhaseIdByName(phaseName: string) {
     return this.phaseNames.get(phaseName);
   }

   forEachPhase(f: (value: Phase, index: number, array: Array<Phase>) => void) {
     this.phases.forEach(f);
   }

   addAnyPositionToLine(lineNumber: number | string, sourcePosition: AnyPosition) {
     const lineNumberString = anyToString(lineNumber);
     if (!this.lineToSourcePositions.has(lineNumberString)) {
       this.lineToSourcePositions.set(lineNumberString, []);
     }
     const A = this.lineToSourcePositions.get(lineNumberString);
     if (!A.includes(sourcePosition)) A.push(sourcePosition);
   }

   setSourceLineToBytecodePosition(sourceLineToBytecodePosition: Array<number> | undefined) {
     if (!sourceLineToBytecodePosition) return;
     sourceLineToBytecodePosition.forEach((pos, i) => {
       this.addAnyPositionToLine(i, { bytecodePosition: pos });
     });
   }

   linetoSourcePositions(lineNumber: number | string) {
     const positions = this.lineToSourcePositions.get(anyToString(lineNumber));
     if (positions === undefined) return [];
     return positions;
   }

   parseSchedule(phase) {
     function createNode(state: any, match) {
       let inputs = [];
       if (match.groups.args) {
         const nodeIdsString = match.groups.args.replace(/\s/g, '');
         const nodeIdStrings = nodeIdsString.split(',');
         inputs = nodeIdStrings.map(n => Number.parseInt(n, 10));
       }
       const node = {
         id: Number.parseInt(match.groups.id, 10),
         label: match.groups.label,
         inputs: inputs
       };
       if (match.groups.blocks) {
         const nodeIdsString = match.groups.blocks.replace(/\s/g, '').replace(/B/g, '');
         const nodeIdStrings = nodeIdsString.split(',');
         const successors = nodeIdStrings.map(n => Number.parseInt(n, 10));
         state.currentBlock.succ = successors;
       }
       state.nodes[node.id] = node;
       state.currentBlock.nodes.push(node);
     }
     function createBlock(state, match) {
       let predecessors = [];
       if (match.groups.in) {
         const blockIdsString = match.groups.in.replace(/\s/g, '').replace(/B/g, '');
         const blockIdStrings = blockIdsString.split(',');
         predecessors = blockIdStrings.map(n => Number.parseInt(n, 10));
       }
       const block = {
         id: Number.parseInt(match.groups.id, 10),
         isDeferred: match.groups.deferred != undefined,
         pred: predecessors.sort(),
         succ: [],
         nodes: []
       };
       state.blocks[block.id] = block;
       state.currentBlock = block;
     }
     function setGotoSuccessor(state, match) {
       state.currentBlock.succ = [Number.parseInt(match.groups.successor.replace(/\s/g, ''), 10)];
     }
     const rules = [
       {
         lineRegexps:
           [/^\s*(?<id>\d+):\ (?<label>.*)\((?<args>.*)\)$/,
             /^\s*(?<id>\d+):\ (?<label>.*)\((?<args>.*)\)\ ->\ (?<blocks>.*)$/,
             /^\s*(?<id>\d+):\ (?<label>.*)$/
           ],
         process: createNode
       },
       {
         lineRegexps:
           [/^\s*---\s*BLOCK\ B(?<id>\d+)\s*(?<deferred>\(deferred\))?(\ <-\ )?(?<in>[^-]*)?\ ---$/
           ],
         process: createBlock
       },
       {
         lineRegexps:
           [/^\s*Goto\s*->\s*B(?<successor>\d+)\s*$/
           ],
         process: setGotoSuccessor
       }
     ];

     const lines = phase.data.split(/[\n]/);
     const state = { currentBlock: undefined, blocks: [], nodes: [] };

     nextLine:
     for (const line of lines) {
       for (const rule of rules) {
         for (const lineRegexp of rule.lineRegexps) {
           const match = line.match(lineRegexp);
           if (match) {
             rule.process(state, match);
             continue nextLine;
           }
         }
       }
       console.log("Warning: unmatched schedule line \"" + line + "\"");
     }
     phase.schedule = state;
     return phase;
   }
   parseSequence(phase) {
     phase.sequence = { blocks: phase.blocks };
     return phase;
   }
 }
	// Copyright 2018 the V8 project authors. All rights reserved.
	// Use of this source code is governed by a BSD-style license that can be
	// found in the LICENSE file.

	import { sortUnique, anyToString } from "../src/util";
	import { NodeLabel } from "./node-label";

	function sourcePositionLe(a, b) {
	if (a.inliningId == b.inliningId) {
	return a.scriptOffset - b.scriptOffset;
	}
	return a.inliningId - b.inliningId;
	}

	function sourcePositionEq(a, b) {
	return a.inliningId == b.inliningId &&
	a.scriptOffset == b.scriptOffset;
	}

	export function sourcePositionToStringKey(sourcePosition: AnyPosition): string {
	if (!sourcePosition) return "undefined";
	if ('inliningId' in sourcePosition && 'scriptOffset' in sourcePosition) {
	return "SP:" + sourcePosition.inliningId + ":" + sourcePosition.scriptOffset;
	}
	if (sourcePosition.bytecodePosition) {
	return "BCP:" + sourcePosition.bytecodePosition;
	}
	return "undefined";
	}

	export function sourcePositionValid(l) {
	return (typeof l.scriptOffset !== undefined
	&& typeof l.inliningId !== undefined) \|\| typeof l.bytecodePosition != undefined;
	}

	export interface SourcePosition {
	scriptOffset: number;
	inliningId: number;
	}

	interface TurboFanOrigin {
	phase: string;
	reducer: string;
	}

	export interface NodeOrigin {
	nodeId: number;
	}

	interface BytecodePosition {
	bytecodePosition: number;
	}

	export type Origin = NodeOrigin \| BytecodePosition;
	export type TurboFanNodeOrigin = NodeOrigin & TurboFanOrigin;
	export type TurboFanBytecodeOrigin = BytecodePosition & TurboFanOrigin;

	type AnyPosition = SourcePosition \| BytecodePosition;

	export interface Source {
	sourcePositions: Array<SourcePosition>;
	sourceName: string;
	functionName: string;
	sourceText: string;
	sourceId: number;
	startPosition?: number;
	backwardsCompatibility: boolean;
	}
	interface Inlining {
	inliningPosition: SourcePosition;
	sourceId: number;
	}
	interface OtherPhase {
	type: "disassembly" \| "sequence" \| "schedule";
	name: string;
	data: any;
	}

	interface InstructionsPhase {
	type: "instructions";
	name: string;
	data: any;
	instructionOffsetToPCOffset?: any;
	blockIdtoInstructionRange?: any;
	nodeIdToInstructionRange?: any;
	}

	interface GraphPhase {
	type: "graph";
	name: string;
	data: any;
	highestNodeId: number;
	nodeLabelMap: Array<NodeLabel>;
	}

	type Phase = GraphPhase \| InstructionsPhase \| OtherPhase;

	export interface Schedule {
	nodes: Array<any>;
	}

	export interface Sequence {
	blocks: Array<any>;
	}

	export class SourceResolver {
	nodePositionMap: Array<AnyPosition>;
	sources: Array<Source>;
	inlinings: Array<Inlining>;
	inliningsMap: Map<string, Inlining>;
	positionToNodes: Map<string, Array<string>>;
	phases: Array<Phase>;
	phaseNames: Map<string, number>;
	disassemblyPhase: Phase;
	lineToSourcePositions: Map<string, Array<AnyPosition>>;
	nodeIdToInstructionRange: Array<[number, number]>;
	blockIdToInstructionRange: Array<[number, number]>;
	instructionToPCOffset: Array<number>;
	pcOffsetToInstructions: Map<number, Array<number>>;
	pcOffsets: Array<number>;

	constructor() {
	// Maps node ids to source positions.
	this.nodePositionMap = [];
	// Maps source ids to source objects.
	this.sources = [];
	// Maps inlining ids to inlining objects.
	this.inlinings = [];
	// Maps source position keys to inlinings.
	this.inliningsMap = new Map();
	// Maps source position keys to node ids.
	this.positionToNodes = new Map();
	// Maps phase ids to phases.
	this.phases = [];
	// Maps phase names to phaseIds.
	this.phaseNames = new Map();
	// The disassembly phase is stored separately.
	this.disassemblyPhase = undefined;
	// Maps line numbers to source positions
	this.lineToSourcePositions = new Map();
	// Maps node ids to instruction ranges.
	this.nodeIdToInstructionRange = [];
	// Maps block ids to instruction ranges.
	this.blockIdToInstructionRange = [];
	// Maps instruction numbers to PC offsets.
	this.instructionToPCOffset = [];
	// Maps PC offsets to instructions.
	this.pcOffsetToInstructions = new Map();
	this.pcOffsets = [];
	}

	setSources(sources, mainBackup) {
	if (sources) {
	for (const [sourceId, source] of Object.entries(sources)) {
	this.sources[sourceId] = source;
	this.sources[sourceId].sourcePositions = [];
	}
	}
	// This is a fallback if the JSON is incomplete (e.g. due to compiler crash).
	if (!this.sources[-1]) {
	this.sources[-1] = mainBackup;
	this.sources[-1].sourcePositions = [];
	}
	}

	setInlinings(inlinings) {
	if (inlinings) {
	for (const [inliningId, inlining] of Object.entries<Inlining>(inlinings)) {
	this.inlinings[inliningId] = inlining;
	this.inliningsMap.set(sourcePositionToStringKey(inlining.inliningPosition), inlining);
	}
	}
	// This is a default entry for the script itself that helps
	// keep other code more uniform.
	this.inlinings[-1] = { sourceId: -1, inliningPosition: null };
	}

	setNodePositionMap(map) {
	if (!map) return;
	if (typeof map[0] != 'object') {
	const alternativeMap = {};
	for (const [nodeId, scriptOffset] of Object.entries<number>(map)) {
	alternativeMap[nodeId] = { scriptOffset: scriptOffset, inliningId: -1 };
	}
	map = alternativeMap;
	}

	for (const [nodeId, sourcePosition] of Object.entries<SourcePosition>(map)) {
	if (sourcePosition == undefined) {
	console.log("Warning: undefined source position ", sourcePosition, " for nodeId ", nodeId);
	}
	const inliningId = sourcePosition.inliningId;
	const inlining = this.inlinings[inliningId];
	if (inlining) {
	const sourceId = inlining.sourceId;
	this.sources[sourceId].sourcePositions.push(sourcePosition);
	}
	this.nodePositionMap[nodeId] = sourcePosition;
	const key = sourcePositionToStringKey(sourcePosition);
	if (!this.positionToNodes.has(key)) {
	this.positionToNodes.set(key, []);
	}
	this.positionToNodes.get(key).push(nodeId);
	}
	for (const [, source] of Object.entries(this.sources)) {
	source.sourcePositions = sortUnique(source.sourcePositions,
	sourcePositionLe, sourcePositionEq);
	}
	}

	sourcePositionsToNodeIds(sourcePositions) {
	const nodeIds = new Set();
	for (const sp of sourcePositions) {
	const key = sourcePositionToStringKey(sp);
	const nodeIdsForPosition = this.positionToNodes.get(key);
	if (!nodeIdsForPosition) continue;
	for (const nodeId of nodeIdsForPosition) {
	nodeIds.add(nodeId);
	}
	}
	return nodeIds;
	}

	nodeIdsToSourcePositions(nodeIds): Array<AnyPosition> {
	const sourcePositions = new Map();
	for (const nodeId of nodeIds) {
	const sp = this.nodePositionMap[nodeId];
	const key = sourcePositionToStringKey(sp);
	sourcePositions.set(key, sp);
	}
	const sourcePositionArray = [];
	for (const sp of sourcePositions.values()) {
	sourcePositionArray.push(sp);
	}
	return sourcePositionArray;
	}

	forEachSource(f: (value: Source, index: number, array: Array<Source>) => void) {
	this.sources.forEach(f);
	}

	translateToSourceId(sourceId: number, location?: SourcePosition) {
	for (const position of this.getInlineStack(location)) {
	const inlining = this.inlinings[position.inliningId];
	if (!inlining) continue;
	if (inlining.sourceId == sourceId) {
	return position;
	}
	}
	return location;
	}

	addInliningPositions(sourcePosition: AnyPosition, locations: Array<SourcePosition>) {
	const inlining = this.inliningsMap.get(sourcePositionToStringKey(sourcePosition));
	if (!inlining) return;
	const sourceId = inlining.sourceId;
	const source = this.sources[sourceId];
	for (const sp of source.sourcePositions) {
	locations.push(sp);
	this.addInliningPositions(sp, locations);
	}
	}

	getInliningForPosition(sourcePosition: AnyPosition) {
	return this.inliningsMap.get(sourcePositionToStringKey(sourcePosition));
	}

	getSource(sourceId: number) {
	return this.sources[sourceId];
	}

	getSourceName(sourceId: number) {
	const source = this.sources[sourceId];
	return `${source.sourceName}:${source.functionName}`;
	}

	sourcePositionFor(sourceId: number, scriptOffset: number) {
	if (!this.sources[sourceId]) {
	return null;
	}
	const list = this.sources[sourceId].sourcePositions;
	for (let i = 0; i < list.length; i++) {
	const sourcePosition = list[i];
	const position = sourcePosition.scriptOffset;
	const nextPosition = list[Math.min(i + 1, list.length - 1)].scriptOffset;
	if ((position <= scriptOffset && scriptOffset < nextPosition)) {
	return sourcePosition;
	}
	}
	return null;
	}

	sourcePositionsInRange(sourceId: number, start: number, end: number) {
	if (!this.sources[sourceId]) return [];
	const res = [];
	const list = this.sources[sourceId].sourcePositions;
	for (const sourcePosition of list) {
	if (start <= sourcePosition.scriptOffset && sourcePosition.scriptOffset < end) {
	res.push(sourcePosition);
	}
	}
	return res;
	}

	getInlineStack(sourcePosition?: SourcePosition) {
	if (!sourcePosition) return [];

	const inliningStack = [];
	let cur = sourcePosition;
	while (cur && cur.inliningId != -1) {
	inliningStack.push(cur);
	const inlining = this.inlinings[cur.inliningId];
	if (!inlining) {
	break;
	}
	cur = inlining.inliningPosition;
	}
	if (cur && cur.inliningId == -1) {
	inliningStack.push(cur);
	}
	return inliningStack;
	}

	recordOrigins(phase: GraphPhase) {
	if (phase.type != "graph") return;
	for (const node of phase.data.nodes) {
	phase.highestNodeId = Math.max(phase.highestNodeId, node.id);
	if (node.origin != undefined &&
	node.origin.bytecodePosition != undefined) {
	const position = { bytecodePosition: node.origin.bytecodePosition };
	this.nodePositionMap[node.id] = position;
	const key = sourcePositionToStringKey(position);
	if (!this.positionToNodes.has(key)) {
	this.positionToNodes.set(key, []);
	}
	const A = this.positionToNodes.get(key);
	if (!A.includes(node.id)) A.push(`${node.id}`);
	}

	// Backwards compatibility.
	if (typeof node.pos === "number") {
	node.sourcePosition = { scriptOffset: node.pos, inliningId: -1 };
	}
	}
	}

	readNodeIdToInstructionRange(nodeIdToInstructionRange) {
	for (const [nodeId, range] of Object.entries<[number, number]>(nodeIdToInstructionRange)) {
	this.nodeIdToInstructionRange[nodeId] = range;
	}
	}

	readBlockIdToInstructionRange(blockIdToInstructionRange) {
	for (const [blockId, range] of Object.entries<[number, number]>(blockIdToInstructionRange)) {
	this.blockIdToInstructionRange[blockId] = range;
	}
	}

	getInstruction(nodeId: number): [number, number] {
	const X = this.nodeIdToInstructionRange[nodeId];
	if (X === undefined) return [-1, -1];
	return X;
	}

	getInstructionRangeForBlock(blockId: number): [number, number] {
	const X = this.blockIdToInstructionRange[blockId];
	if (X === undefined) return [-1, -1];
	return X;
	}

	readInstructionOffsetToPCOffset(instructionToPCOffset) {
	for (const [instruction, offset] of Object.entries<number>(instructionToPCOffset)) {
	this.instructionToPCOffset[instruction] = offset;
	if (!this.pcOffsetToInstructions.has(offset)) {
	this.pcOffsetToInstructions.set(offset, []);
	}
	this.pcOffsetToInstructions.get(offset).push(Number(instruction));
	}
	this.pcOffsets = Array.from(this.pcOffsetToInstructions.keys()).sort((a, b) => b - a);
	}

	hasPCOffsets() {
	return this.pcOffsetToInstructions.size > 0;
	}

	getKeyPcOffset(offset: number): number {
	if (this.pcOffsets.length === 0) return -1;
	for (const key of this.pcOffsets) {
	if (key <= offset) {
	return key;
	}
	}
	return -1;
	}

	instructionRangeToKeyPcOffsets([start, end]: [number, number]) {
	if (start == end) return [this.instructionToPCOffset[start]];
	return this.instructionToPCOffset.slice(start, end);
	}

	instructionsToKeyPcOffsets(instructionIds: Iterable<number>) {
	const keyPcOffsets = [];
	for (const instructionId of instructionIds) {
	keyPcOffsets.push(this.instructionToPCOffset[instructionId]);
	}
	return keyPcOffsets;
	}

	nodesToKeyPcOffsets(nodes) {
	let offsets = [];
	for (const node of nodes) {
	const range = this.nodeIdToInstructionRange[node];
	if (!range) continue;
	offsets = offsets.concat(this.instructionRangeToKeyPcOffsets(range));
	}
	return offsets;
	}

	nodesForPCOffset(offset: number): [Array<string>, Array<string>] {
	if (this.pcOffsets.length === 0) return [[], []];
	for (const key of this.pcOffsets) {
	if (key <= offset) {
	const instrs = this.pcOffsetToInstructions.get(key);
	const nodes = [];
	const blocks = [];
	for (const instr of instrs) {
	for (const [nodeId, range] of this.nodeIdToInstructionRange.entries()) {
	if (!range) continue;
	const [start, end] = range;
	if (start == end && instr == start) {
	nodes.push("" + nodeId);
	}
	if (start <= instr && instr < end) {
	nodes.push("" + nodeId);
	}
	}
	}
	return [nodes, blocks];
	}
	}
	return [[], []];
	}

	parsePhases(phases) {
	const nodeLabelMap = [];
	for (const [, phase] of Object.entries<Phase>(phases)) {
	switch (phase.type) {
	case 'disassembly':
	this.disassemblyPhase = phase;
	break;
	case 'schedule':
	this.phaseNames.set(phase.name, this.phases.length);
	this.phases.push(this.parseSchedule(phase));
	break;
	case 'sequence':
	this.phaseNames.set(phase.name, this.phases.length);
	this.phases.push(this.parseSequence(phase));
	break;
	case 'instructions':
	if (phase.nodeIdToInstructionRange) {
	this.readNodeIdToInstructionRange(phase.nodeIdToInstructionRange);
	}
	if (phase.blockIdtoInstructionRange) {
	this.readBlockIdToInstructionRange(phase.blockIdtoInstructionRange);
	}
	if (phase.instructionOffsetToPCOffset) {
	this.readInstructionOffsetToPCOffset(phase.instructionOffsetToPCOffset);
	}
	break;
	case 'graph':
	const graphPhase: GraphPhase = Object.assign(phase, { highestNodeId: 0 });
	this.phaseNames.set(graphPhase.name, this.phases.length);
	this.phases.push(graphPhase);
	this.recordOrigins(graphPhase);
	this.internNodeLabels(graphPhase, nodeLabelMap);
	graphPhase.nodeLabelMap = nodeLabelMap.slice();
	break;
	default:
	throw "Unsupported phase type";
	}
	}
	}

	internNodeLabels(phase: GraphPhase, nodeLabelMap: Array<NodeLabel>) {
	for (const n of phase.data.nodes) {
	const label = new NodeLabel(n.id, n.label, n.title, n.live,
	n.properties, n.sourcePosition, n.origin, n.opcode, n.control,
	n.opinfo, n.type);
	const previous = nodeLabelMap[label.id];
	if (!label.equals(previous)) {
	if (previous != undefined) {
	label.setInplaceUpdatePhase(phase.name);
	}
	nodeLabelMap[label.id] = label;
	}
	n.nodeLabel = nodeLabelMap[label.id];
	}
	}

	repairPhaseId(anyPhaseId) {
	return Math.max(0, Math.min(anyPhaseId \| 0, this.phases.length - 1));
	}

	getPhase(phaseId: number) {
	return this.phases[phaseId];
	}

	getPhaseIdByName(phaseName: string) {
	return this.phaseNames.get(phaseName);
	}

	forEachPhase(f: (value: Phase, index: number, array: Array<Phase>) => void) {
	this.phases.forEach(f);
	}

	addAnyPositionToLine(lineNumber: number \| string, sourcePosition: AnyPosition) {
	const lineNumberString = anyToString(lineNumber);
	if (!this.lineToSourcePositions.has(lineNumberString)) {
	this.lineToSourcePositions.set(lineNumberString, []);
	}
	const A = this.lineToSourcePositions.get(lineNumberString);
	if (!A.includes(sourcePosition)) A.push(sourcePosition);
	}

	setSourceLineToBytecodePosition(sourceLineToBytecodePosition: Array<number> \| undefined) {
	if (!sourceLineToBytecodePosition) return;
	sourceLineToBytecodePosition.forEach((pos, i) => {
	this.addAnyPositionToLine(i, { bytecodePosition: pos });
	});
	}

	linetoSourcePositions(lineNumber: number \| string) {
	const positions = this.lineToSourcePositions.get(anyToString(lineNumber));
	if (positions === undefined) return [];
	return positions;
	}

	parseSchedule(phase) {
	function createNode(state: any, match) {
	let inputs = [];
	if (match.groups.args) {
	const nodeIdsString = match.groups.args.replace(/\s/g, '');
	const nodeIdStrings = nodeIdsString.split(',');
	inputs = nodeIdStrings.map(n => Number.parseInt(n, 10));
	}
	const node = {
	id: Number.parseInt(match.groups.id, 10),
	label: match.groups.label,
	inputs: inputs
	};
	if (match.groups.blocks) {
	const nodeIdsString = match.groups.blocks.replace(/\s/g, '').replace(/B/g, '');
	const nodeIdStrings = nodeIdsString.split(',');
	const successors = nodeIdStrings.map(n => Number.parseInt(n, 10));
	state.currentBlock.succ = successors;
	}
	state.nodes[node.id] = node;
	state.currentBlock.nodes.push(node);
	}
	function createBlock(state, match) {
	let predecessors = [];
	if (match.groups.in) {
	const blockIdsString = match.groups.in.replace(/\s/g, '').replace(/B/g, '');
	const blockIdStrings = blockIdsString.split(',');
	predecessors = blockIdStrings.map(n => Number.parseInt(n, 10));
	}
	const block = {
	id: Number.parseInt(match.groups.id, 10),
	isDeferred: match.groups.deferred != undefined,
	pred: predecessors.sort(),
	succ: [],
	nodes: []
	};
	state.blocks[block.id] = block;
	state.currentBlock = block;
	}
	function setGotoSuccessor(state, match) {
	state.currentBlock.succ = [Number.parseInt(match.groups.successor.replace(/\s/g, ''), 10)];
	}
	const rules = [
	{
	lineRegexps:
	[/^\s(?<id>\d+):\ (?<label>.)\((?<args>.*)\)$/,
	/^\s(?<id>\d+):\ (?<label>.)\((?<args>.)\)\ ->\ (?<blocks>.)$/,
	/^\s(?<id>\d+):\ (?<label>.)$/
	],
	process: createNode
	},
	{
	lineRegexps:
	[/^\s---\sBLOCK\ B(?<id>\d+)\s(?<deferred>\(deferred\))?(\ <-\ )?(?<in>[^-])?\ ---$/
	],
	process: createBlock
	},
	{
	lineRegexps:
	[/^\sGoto\s->\sB(?<successor>\d+)\s$/
	],
	process: setGotoSuccessor
	}
	];

	const lines = phase.data.split(/[\n]/);
	const state = { currentBlock: undefined, blocks: [], nodes: [] };

	nextLine:
	for (const line of lines) {
	for (const rule of rules) {
	for (const lineRegexp of rule.lineRegexps) {
	const match = line.match(lineRegexp);
	if (match) {
	rule.process(state, match);
	continue nextLine;
	}
	}
	}
	console.log("Warning: unmatched schedule line \"" + line + "\"");
	}
	phase.schedule = state;
	return phase;
	}
	parseSequence(phase) {
	phase.sequence = { blocks: phase.blocks };
	return phase;
	}
	}