1 files changed, 528 insertions, 0 deletions
diff --git a/deps/v8/tools/turbolizer/src/source-resolver.ts b/deps/v8/tools/turbolizer/src/source-resolver.ts
new file mode 100644
index 0000000000..b2412d3e31
--- /dev/null
+++ b/deps/v8/tools/turbolizer/src/source-resolver.ts
@@ -0,0 +1,528 @@
+// 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 "./util.js"
+
+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): string {
+  if (!sourcePosition) return "undefined";
+  if (sourcePosition.inliningId && sourcePosition.scriptOffset)
+    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;
+}
+
+type Origin = NodeOrigin | BytecodePosition;
+type TurboFanNodeOrigin = NodeOrigin & TurboFanOrigin;
+type TurboFanBytecodeOrigin = BytecodePosition & TurboFanOrigin;
+
+type AnyPosition = SourcePosition | BytecodePosition;
+
+export interface Source {
+  sourcePositions: Array<SourcePosition>;
+  sourceName: string;
+  functionName: string;
+  sourceText: string;
+  sourceId: number;
+  startPosition?: number;
+}
+interface Inlining {
+  inliningPosition: SourcePosition;
+  sourceId: number;
+}
+interface Phase {
+  type: string;
+  name: string;
+  data: any;
+}
+
+export interface Schedule {
+  nodes: 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>>;
+
+
+  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();
+  }
+
+  setSources(sources, mainBackup) {
+    if (sources) {
+      for (let [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;
+      let key = sourcePositionToStringKey(sourcePosition);
+      if (!this.positionToNodes.has(key)) {
+        this.positionToNodes.set(key, []);
+      }
+      this.positionToNodes.get(key).push(nodeId);
+    }
+    for (const [sourceId, source] of Object.entries(this.sources)) {
+      source.sourcePositions = sortUnique(source.sourcePositions,
+        sourcePositionLe, sourcePositionEq);
+    }
+  }
+
+  sourcePositionsToNodeIds(sourcePositions) {
+    const nodeIds = new Set();
+    for (const sp of sourcePositions) {
+      let key = sourcePositionToStringKey(sp);
+      let 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) {
+      let sp = this.nodePositionMap[nodeId];
+      let key = sourcePositionToStringKey(sp);
+      sourcePositions.set(key, sp);
+    }
+    const sourcePositionArray = [];
+    for (const sp of sourcePositions.values()) {
+      sourcePositionArray.push(sp);
+    }
+    return sourcePositionArray;
+  }
+
+  forEachSource(f) {
+    this.sources.forEach(f);
+  }
+
+  translateToSourceId(sourceId, location) {
+    for (const position of this.getInlineStack(location)) {
+      let inlining = this.inlinings[position.inliningId];
+      if (!inlining) continue;
+      if (inlining.sourceId == sourceId) {
+        return position;
+      }
+    }
+    return location;
+  }
+
+  addInliningPositions(sourcePosition, locations) {
+    let inlining = this.inliningsMap.get(sourcePositionToStringKey(sourcePosition));
+    if (!inlining) return;
+    let sourceId = inlining.sourceId
+    const source = this.sources[sourceId];
+    for (const sp of source.sourcePositions) {
+      locations.push(sp);
+      this.addInliningPositions(sp, locations);
+    }
+  }
+
+  getInliningForPosition(sourcePosition) {
+    return this.inliningsMap.get(sourcePositionToStringKey(sourcePosition));
+  }
+
+  getSource(sourceId) {
+    return this.sources[sourceId];
+  }
+
+  getSourceName(sourceId) {
+    const source = this.sources[sourceId];
+    return `${source.sourceName}:${source.functionName}`;
+  }
+
+  sourcePositionFor(sourceId, scriptOffset) {
+    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, start, end) {
+    if (!this.sources[sourceId]) return [];
+    const res = [];
+    const list = this.sources[sourceId].sourcePositions;
+    for (let i = 0; i < list.length; i++) {
+      const sourcePosition = list[i]
+      if (start <= sourcePosition.scriptOffset && sourcePosition.scriptOffset < end) {
+        res.push(sourcePosition);
+      }
+    }
+    return res;
+  }
+
+  getInlineStack(sourcePosition) {
+    if (!sourcePosition) {
+      return [];
+    }
+    let inliningStack = [];
+    let cur = sourcePosition;
+    while (cur && cur.inliningId != -1) {
+      inliningStack.push(cur);
+      let inlining = this.inlinings[cur.inliningId];
+      if (!inlining) {
+        break;
+      }
+      cur = inlining.inliningPosition;
+    }
+    if (cur && cur.inliningId == -1) {
+      inliningStack.push(cur);
+    }
+    return inliningStack;
+  }
+
+  recordOrigins(phase) {
+    if (phase.type != "graph") return;
+    for (const node of phase.data.nodes) {
+      if (node.origin != undefined &&
+        node.origin.bytecodePosition != undefined) {
+        const position = { bytecodePosition: node.origin.bytecodePosition };
+        this.nodePositionMap[node.id] = position;
+        let 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);
+      }
+    }
+  }
+
+  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] {
+    const X = this.nodeIdToInstructionRange[nodeId];
+    if (X === undefined) return [-1, -1];
+    return X;
+  }
+
+  getInstructionRangeForBlock(blockId):[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(instruction);
+    }
+    console.log(this.pcOffsetToInstructions);
+  }
+
+  hasPCOffsets() {
+    return this.pcOffsetToInstructions.size > 0;
+  }
+
+
+  nodesForPCOffset(offset): [Array<String>, Array<String>] {
+    const keys = Array.from(this.pcOffsetToInstructions.keys()).sort((a, b) => b - a);
+    if (keys.length === 0) return [[],[]];
+    for (const key of keys) {
+      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) {
+    for (const [phaseId, phase] of Object.entries<Phase>(phases)) {
+      if (phase.type == 'disassembly') {
+        this.disassemblyPhase = phase;
+      } else if (phase.type == 'schedule') {
+        this.phases.push(this.parseSchedule(phase))
+        this.phaseNames.set(phase.name, this.phases.length);
+      } else if (phase.type == 'instructions') {
+        if (phase.nodeIdToInstructionRange) {
+          this.readNodeIdToInstructionRange(phase.nodeIdToInstructionRange);
+        }
+        if (phase.blockIdtoInstructionRange) {
+          this.readBlockIdToInstructionRange(phase.blockIdtoInstructionRange);
+        }
+        if (phase.instructionOffsetToPCOffset) {
+          this.readInstructionOffsetToPCOffset(phase.instructionOffsetToPCOffset);
+        }
+      } else {
+        this.phases.push(phase);
+        this.recordOrigins(phase);
+        this.phaseNames.set(phase.name, this.phases.length);
+      }
+    }
+  }
+
+  repairPhaseId(anyPhaseId) {
+    return Math.max(0, Math.min(anyPhaseId, this.phases.length - 1))
+  }
+
+  getPhase(phaseId) {
+    return this.phases[phaseId];
+  }
+
+  getPhaseIdByName(phaseName) {
+    return this.phaseNames.get(phaseName);
+  }
+
+  forEachPhase(f) {
+    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, 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;
+  }
+}