[interpreter] Ensure optimizations preserve source positions.

test/cctest/interpreter/source-position-matcher.cc

+// Copyright 2016 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.
+
+#include "test/cctest/interpreter/source-position-matcher.h"
+
+#include "src/objects-inl.h"
+#include "src/objects.h"
+
+namespace v8 {
+namespace internal {
+namespace interpreter {
+
+// Comparer for PositionTableEntry instances.
+struct PositionTableEntryComparer {
+  bool operator()(const PositionTableEntry& lhs,
+                  const PositionTableEntry& rhs) {
+    int lhs_type_score = type_score(lhs);
+    int rhs_type_score = type_score(rhs);
+    if (lhs_type_score == rhs_type_score) {
+      return lhs.source_position < rhs.source_position;
+    } else {
+      return lhs_type_score < rhs_type_score;
+    }
+  }
+
+  int type_score(const PositionTableEntry& entry) {
+    return entry.is_statement ? 1 : 0;
+  }
+};
+
+//
+// The principles for comparing source positions in bytecode arrays
+// are:
+//
+// 1. The number of statement positions must be the same in both.
+//
+// 2. Statement positions may be moved provide they do not affect the
+//    debuggers causal view of the v8 heap and local state. This means
+//    statement positions may be moved when their initial position is
+//    on bytecodes that manipulate the accumulator and temporary
+//    registers.
+//
+// 3. When duplicate expression positions are present, either may
+//    be dropped.
+//
+// 4. Expression positions may be applied to later bytecodes in the
+//    bytecode array if the current bytecode does not throw.
+//
+// 5. Expression positions may be dropped when they are applied to
+//    bytecodes that manipulate local frame state and immediately
+//    proceeded by another source position.
+//
+// 6. The relative ordering of source positions must be preserved.
+//
+bool SourcePositionMatcher::Match(Handle<BytecodeArray> original_bytecode,
+                                  Handle<BytecodeArray> optimized_bytecode) {
+  SourcePositionTableIterator original(
+      original_bytecode->source_position_table());
+  SourcePositionTableIterator optimized(
+      optimized_bytecode->source_position_table());
+
+  int last_original_bytecode_offset = 0;
+  int last_optimized_bytecode_offset = 0;
+
+  // Ordered lists of expression positions immediately before the
+  // latest statements in each bytecode array.
+  std::vector<PositionTableEntry> original_expression_entries;
+  std::vector<PositionTableEntry> optimized_expression_entries;
+
+  while (true) {
+    MoveToNextStatement(&original, &original_expression_entries);
+    MoveToNextStatement(&optimized, &optimized_expression_entries);
+
+    if (original.done() && optimized.done()) {
+      return true;
+    } else if (original.done()) {
+      return false;
+    } else if (optimized.done()) {
+      return false;
+    }
+
+    if (HasNewExpressionPositionsInOptimized(&original_expression_entries,
+                                             &optimized_expression_entries)) {
+      return false;
+    }
+
+    StripUnneededExpressionPositions(original_bytecode,
+                                     &original_expression_entries,
+                                     original.bytecode_offset());
+    StripUnneededExpressionPositions(optimized_bytecode,
+                                     &optimized_expression_entries,
+                                     optimized.bytecode_offset());
+
+    if (!CompareExpressionPositions(&original_expression_entries,
+                                    &optimized_expression_entries)) {
+      // Message logged in CompareExpressionPositions().
+      return false;
+    }
+
+    // Check original and optimized have matching source positions.
+    if (original.source_position() != optimized.source_position()) {
+      return false;
+    }
+
+    if (original.bytecode_offset() < last_original_bytecode_offset) {
+      return false;
+    }
+    last_original_bytecode_offset = original.bytecode_offset();
+
+    if (optimized.bytecode_offset() < last_optimized_bytecode_offset) {
+      return false;
+    }
+    last_optimized_bytecode_offset = optimized.bytecode_offset();
+
+    // TODO(oth): Can we compare statement positions are semantically
+    // equivalent? e.g. before a bytecode that has debugger observable
+    // effects. This is likely non-trivial.
+  }
+
+  return true;
+}
+
+bool SourcePositionMatcher::HasNewExpressionPositionsInOptimized(
+    const std::vector<PositionTableEntry>* const original_positions,
+    const std::vector<PositionTableEntry>* const optimized_positions) {
+  std::set<PositionTableEntry, PositionTableEntryComparer> original_set(
+      original_positions->begin(), original_positions->end());
+
+  bool retval = false;
+  for (auto optimized_position : *optimized_positions) {
+    if (original_set.find(optimized_position) == original_set.end()) {
+      retval = true;
+    }
+  }
+  return retval;
+}
+
+bool SourcePositionMatcher::CompareExpressionPositions(
+    const std::vector<PositionTableEntry>* const original_positions,
+    const std::vector<PositionTableEntry>* const optimized_positions) {
+  if (original_positions->size() != optimized_positions->size()) {
+    return false;
+  }
+
+  if (original_positions->size() == 0) {
+    return true;
+  }
+
+  for (size_t i = 0; i < original_positions->size(); ++i) {
+    PositionTableEntry original = original_positions->at(i);
+    PositionTableEntry optimized = original_positions->at(i);
+    CHECK(original.source_position > 0);
+    if ((original.is_statement || optimized.is_statement) ||
+        (original.source_position != optimized.source_position) ||
+        (original.source_position < 0)) {
+      return false;
+    }
+  }
+  return true;
+}
+
+void SourcePositionMatcher::StripUnneededExpressionPositions(
+    Handle<BytecodeArray> bytecode_array,
+    std::vector<PositionTableEntry>* expression_positions,
+    int next_statement_bytecode_offset) {
+  size_t j = 0;
+  for (size_t i = 0; i < expression_positions->size(); ++i) {
+    CHECK(expression_positions->at(i).source_position > 0 &&
+          !expression_positions->at(i).is_statement);
+    int bytecode_end = (i == expression_positions->size() - 1)
+                           ? next_statement_bytecode_offset
+                           : expression_positions->at(i + 1).bytecode_offset;
+    if (ExpressionPositionIsNeeded(bytecode_array,
+                                   expression_positions->at(i).bytecode_offset,
+                                   bytecode_end)) {
+      expression_positions->at(j++) = expression_positions->at(i);
+    }
+  }
+  expression_positions->resize(j);
+}
+
+void SourcePositionMatcher::AdvanceBytecodeIterator(
+    BytecodeArrayIterator* iterator, int bytecode_offset) {
+  while (iterator->current_offset() != bytecode_offset) {
+    iterator->Advance();
+  }
+}
+
+bool SourcePositionMatcher::ExpressionPositionIsNeeded(
+    Handle<BytecodeArray> bytecode_array, int start_offset, int end_offset) {
+  CHECK_GT(end_offset, start_offset);
+  BytecodeArrayIterator iterator(bytecode_array);
+  AdvanceBytecodeIterator(&iterator, start_offset);
+
+  while (iterator.current_offset() != end_offset) {
+    if (Bytecodes::IsWithoutExternalSideEffects(iterator.current_bytecode())) {
+      iterator.Advance();
+    } else {
+      // Bytecode could throw so need an expression position.
+      return true;
+    }
+  }
+  return false;
+}
+
+void SourcePositionMatcher::MoveToNextStatement(
+    SourcePositionTableIterator* iterator,
+    std::vector<PositionTableEntry>* positions) {
+  iterator->Advance();
+  positions->clear();
+  while (!iterator->done()) {
+    if (iterator->is_statement()) {
+      break;
+    }
+    positions->push_back({iterator->bytecode_offset(),
+                          iterator->source_position(),
+                          iterator->is_statement()});
+    iterator->Advance();
+  }
+}
+
+}  // namespace interpreter
+}  // namespace internal
+}  // namespace v8