turbolizer/src/source-resolver.ts

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