pkg/vm/lib/bytecode/ngrams.dart

// Copyright (c) 2018, 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.

library vm.bytecode.ngrams;

import 'dart:io';
import 'dart:typed_data';

import 'package:kernel/ast.dart' show listEquals, listHashCode;

import 'dbc.dart';
import 'disassembler.dart' show Instruction, BytecodeDisassembler;

bool isControlFlowInstr(Instruction instr) => isControlFlow(instr.opcode);

class NGram {
  List<Instruction> instrs;
  BytecodeDisassembler _disassembler;

  NGram(this.instrs, {bool mergePushes = false}) {
    if (mergePushes) {
      _mergePushes(instrs);
    }
    _canonicalize(instrs);
  }

  /// Tests if any instructions that are not the last instruction in the window
  /// are a jump, throw, or call.
  bool get controlFlowIsNotLast =>
      instrs.sublist(0, instrs.length - 1).any(isControlFlowInstr);

  @override
  int get hashCode => listHashCode(instrs);

  @override
  bool operator ==(other) =>
      (other is NGram) && listEquals(instrs, other.instrs);

  @override
  String toString() {
    StringBuffer out = new StringBuffer();
    for (var instr in instrs) {
      _disassembler.writeInstruction(out, instr);
    }
    return out.toString();
  }

  /// Rewrites all Push-like instructions as 'Push r0'.
  static void _mergePushes(List<Instruction> instrs) {
    for (int i = 0; i < instrs.length; i++) {
      if (isPush(instrs[i].opcode)) {
        instrs[i] = new Instruction(Opcode.kPush, false, <int>[0], 0);
      }
    }
  }

  /// Rewrites the operands of instructions so that ngrams that differ only in
  /// operands can be considered the same.
  ///
  /// Each type of operand is considered to come from a different space, and
  /// each operand is re-indexed in that space starting from 0 such that each
  /// distinct operand before canonicalization remains distinct afterwords. E.g.
  ///
  /// Push r3
  /// Push r3
  /// Push r4
  ///
  /// Becomes
  ///
  /// Push r0
  /// Push r0
  /// Push r1
  static void _canonicalize(List<Instruction> instrs) {
    Map<Operand, Map<int, int>> operandMaps = <Operand, Map<int, int>>{
      // No mapping for Operand.none.
      Operand.imm: <int, int>{},
      Operand.lit: <int, int>{},
      Operand.reg: <int, int>{},
      Operand.xeg: <int, int>{},
      Operand.tgt: <int, int>{},
      // No mapping for Operand.spe.
    };
    for (Instruction instr in instrs) {
      Format fmt = BytecodeFormats[instr.opcode];
      for (int i = 0; i < instr.operands.length; i++) {
        Operand op = fmt.operands[i];
        if (!operandMaps.containsKey(op)) {
          continue;
        }
        int newOperand = operandMaps[op]
            .putIfAbsent(instr.operands[i], () => operandMaps[op].length);
        instr.operands[i] = newOperand;
      }
    }
  }
}

class NGramReader {
  List<Instruction> _instructions;

  Map<NGram, int> _ngramCounts = <NGram, int>{};

  NGramReader(String traceFilename) {
    File traceFile = File(traceFilename);
    Uint8List bytecode = traceFile.readAsBytesSync();
    final disassembler = new BytecodeDisassembler();
    _instructions = disassembler.decode(bytecode);
  }

  Map<NGram, int> get ngramCounts => _ngramCounts;

  void readAllNGrams(int windowSize,
      {bool basicBlocks: true, bool mergePushes: false}) {
    int offset = 0;
    while (offset + windowSize < _instructions.length) {
      List<Instruction> window =
          _instructions.sublist(offset, offset + windowSize);
      offset += 1;
      NGram ngram = new NGram(window, mergePushes: mergePushes);
      if (basicBlocks && ngram.controlFlowIsNotLast) {
        continue;
      }
      _ngramCounts.update(ngram, (count) => count + 1, ifAbsent: () => 1);
    }
  }

  void writeNGramStats(String outputFilename,
      {bool sort = true, int minCount = 1000}) {
    File outputFile = new File(outputFilename);
    IOSink file = outputFile.openWrite();
    List<MapEntry<NGram, int>> entries =
        _ngramCounts.entries.where((e) => e.value > minCount).toList();
    if (sort) {
      entries.sort((e1, e2) => e2.value - e1.value);
    }
    entries.forEach((e) {
      file.write("count: ${e.value}\n${e.key}\n");
    });
    file.close();
  }
}