[interpreter] Ensure optimizations preserve source positions.

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

Index: test/cctest/interpreter/source-position-matcher.cc
diff --git a/test/cctest/interpreter/source-position-matcher.cc b/test/cctest/interpreter/source-position-matcher.cc
new file mode 100644
index 0000000000000000000000000000000000000000..9a001737078711d69dd209dbb193a725da032d4d
--- /dev/null
+++ b/test/cctest/interpreter/source-position-matcher.cc
@@ -0,0 +1,252 @@
+// 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/interpreter/bytecode-array-iterator.h"
+#include "src/objects-inl.h"
+#include "src/objects.h"
+
+namespace v8 {
+namespace internal {
+namespace interpreter {
+
+// Comparer for PositionTableEntry instances.
+struct PTECompare {

[rmcilroy, 2016/06/07 09:46:11]

I don't think it's worth abbreviating this given you only use the name once ->
PositionTableEntryComparer ?

[oth, 2016/06/07 13:46:17]

Done.

+  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 posiiton is

[rmcilroy, 2016/06/07 09:46:11]

/s/posiiton/position

[oth, 2016/06/07 13:46:17]

Done.

+//    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;
+
+  // Order list of expression positions (terminated by a statement
+  // position to ease validation).

[rmcilroy, 2016/06/07 09:46:11]

I think it's a bit confusing to terminate with the statement position. does that
really help with validation? I think it is clearer to use original/optimized as
the statement positions (which you do below) and only have expression in the
vector - you seem to skip the statements when checking properties of the source
positions in the vector anyway AFAIKT.

[oth, 2016/06/07 13:46:17]

Okay, done. The statement position is used as a back marker, but now passed as
an argument.

+  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()) {
+      printf("Source positions ended early on original bytecode.");
+      return false;
+    } else if (optimized.done()) {
+      printf("Source positions ended early on optimized bytecode.");
+      return false;
+    }
+
+    if (NewExpressionPositionsInOptimized(&original_expression_entries,

[rmcilroy, 2016/06/07 09:46:11]

nit - HasNewExpressionPositionsInOptimized

[oth, 2016/06/07 13:46:17]

Done.

+                                          &optimized_expression_entries)) {
+      printf("Optimized set has new expression positions.\n");
+      return false;
+    }
+
+    StripUnneededExpressionPositions(original_bytecode,
+                                     &original_expression_entries);
+    StripUnneededExpressionPositions(optimized_bytecode,
+                                     &optimized_expression_entries);
+    if (!CompareExpressionPositions(&original_expression_entries,
+                                    &optimized_expression_entries)) {
+      return false;

[rmcilroy, 2016/06/07 09:46:11]

nit - comment that message is printed in CompareExpressionPositions

[oth, 2016/06/07 13:46:17]

Done.

+    }
+
+    // Check original and optimized have matching source positions.
+    if (original.source_position() != optimized.source_position()) {
+      printf("Statement source position mismatch %d != %d\n",
+             original.source_position(), optimized.source_position());
+      return false;
+    }
+
+    if (original.bytecode_offset() < last_original_bytecode_offset) {
+      printf("Original has bytecode offset running backwards %d < %d.\n",
+             original.bytecode_offset(), last_original_bytecode_offset);
+      return false;
+    }
+    last_original_bytecode_offset = original.bytecode_offset();
+
+    if (optimized.bytecode_offset() < last_optimized_bytecode_offset) {
+      printf("Optimized has bytecode offset running backwards %d < %d.\n",
+             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::NewExpressionPositionsInOptimized(
+    const std::vector<PositionTableEntry>* const original_positions,
+    const std::vector<PositionTableEntry>* const optimized_positions) {
+  std::set<PositionTableEntry, PTECompare> 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()) {
+      printf("Optimized bytecode has new expression source position %d\n",
+             optimized_position.source_position);
+      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() < 1 ||
+      !original_positions->back().is_statement) {
+    printf(
+        "Original expression positions are not terminated by a statement.\n");
+    return false;
+  }
+
+  if (optimized_positions->size() < 1 ||
+      !optimized_positions->back().is_statement) {
+    printf(
+        "Optimized expression positions are not terminated by a statement.\n");
+    return false;
+  }
+
+  if (original_positions->size() != optimized_positions->size()) {
+    printf(
+        "Optimized bytecode has different number of expression positions "
+        "%zu != %zu\n",
+        optimized_positions->size() - 1, original_positions->size() - 1);
+    printf("Original expression source positions");

[rmcilroy, 2016/06/07 09:46:11]

Is some of this logging printfs? Maybe you should add a log_error function to
make it clear when you are logging an error message.

[oth, 2016/06/07 13:46:17]

I can't see anything in v8 tests that attempts to be this helpful. Removed
these.

+    for (size_t i = 0; i < original_positions->size() - 1; ++i) {
+      printf(" %d", original_positions->at(i).source_position);
+    }
+    printf("\nOptimized expression source positions");
+    for (size_t i = 0; i < optimized_positions->size() - 1; ++i) {
+      printf(" %d", optimized_positions->at(i).source_position);
+    }
+    printf("\n");
+    return false;
+  }
+
+  for (size_t i = 0; i < original_positions->size() - 1; ++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)) {
+      printf("Expression positions differ %d != %d\n", original.source_position,
+             optimized.source_position);
+      return false;
+    }
+  }
+  return true;
+}
+
+void SourcePositionMatcher::StripUnneededExpressionPositions(
+    Handle<BytecodeArray> bytecode_array,
+    std::vector<PositionTableEntry>* positions) {
+  size_t j = 0;
+  for (size_t i = 0; i < positions->size() - 1; ++i) {
+    CHECK(positions->at(i).source_position > 0 &&
+          !positions->at(i).is_statement);
+    if (ExpressionPositionIsNeeded(bytecode_array,
+                                   positions->at(i).bytecode_offset,
+                                   positions->at(i + 1).bytecode_offset)) {
+      positions->at(j++) = positions->at(i);
+    }
+  }
+  positions->at(j++) = positions->back();
+  positions->resize(j);
+  CHECK(positions->back().is_statement);
+}
+
+bool SourcePositionMatcher::ExpressionPositionIsNeeded(
+    Handle<BytecodeArray> bytecode_array, int start_offset, int end_offset) {
+  CHECK_GT(end_offset, start_offset);
+  BytecodeArrayIterator iterator(bytecode_array);
+  while (iterator.current_offset() != start_offset) {
+    iterator.Advance();
+  }
+
+  while (iterator.current_offset() != end_offset) {
+    if (Bytecodes::IsWithoutExternalSideEffects(iterator.current_bytecode())) {
+      iterator.Advance();
+    } else {
+      // Bytecode could throw so need an expression position.
+      CHECK(iterator.current_bytecode() != Bytecode::kStar);

[rmcilroy, 2016/06/07 09:46:11]

Not sure why this CHECK is here. It couldn't be Star if
IsWithoutExternalSideEffects could it?

[oth, 2016/06/07 13:46:17]

It's just left over cruft from an earlier revision. Removed.

+      return true;
+    }
+  }
+  return false;
+}
+
+void SourcePositionMatcher::MoveToNextStatement(
+    SourcePositionTableIterator* iterator,
+    std::vector<PositionTableEntry>* positions) {
+  iterator->Advance();
+  positions->clear();
+  while (!iterator->done()) {
+    positions->push_back({iterator->bytecode_offset(),
+                          iterator->source_position(),
+                          iterator->is_statement()});
+    if (iterator->is_statement()) {
+      break;
+    }
+    iterator->Advance();
+  }
+}
+
+}  // namespace interpreter
+}  // namespace internal
+}  // namespace v8