source-position-matcher.cc 7.6 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
// 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,
17
                  const PositionTableEntry& rhs) const {
18 19 20 21 22 23 24 25 26
    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;
    }
  }

27
  int type_score(const PositionTableEntry& entry) const {
28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
    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(
59
      original_bytecode->SourcePositionTable());
60
  SourcePositionTableIterator optimized(
61
      optimized_bytecode->SourcePositionTable());
62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89

  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,
90
                                     original.code_offset());
91 92
    StripUnneededExpressionPositions(optimized_bytecode,
                                     &optimized_expression_entries,
93
                                     optimized.code_offset());
94 95 96 97 98 99 100 101 102 103 104 105

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

106
    if (original.code_offset() < last_original_bytecode_offset) {
107 108
      return false;
    }
109
    last_original_bytecode_offset = original.code_offset();
110

111
    if (optimized.code_offset() < last_optimized_bytecode_offset) {
112 113
      return false;
    }
114
    last_optimized_bytecode_offset = optimized.code_offset();
115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172

    // 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
173
                           : expression_positions->at(i + 1).code_offset;
174
    if (ExpressionPositionIsNeeded(bytecode_array,
175
                                   expression_positions->at(i).code_offset,
176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215
                                   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;
    }
216 217
    positions->push_back({iterator->code_offset(),
                          iterator->source_position().raw(),
218 219 220 221 222 223 224 225
                          iterator->is_statement()});
    iterator->Advance();
  }
}

}  // namespace interpreter
}  // namespace internal
}  // namespace v8