OLD | NEW |
(Empty) | |
| 1 // Copyright 2016 the V8 project authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. |
| 4 |
| 5 #include "test/cctest/interpreter/source-position-matcher.h" |
| 6 |
| 7 #include "src/objects-inl.h" |
| 8 #include "src/objects.h" |
| 9 |
| 10 namespace v8 { |
| 11 namespace internal { |
| 12 namespace interpreter { |
| 13 |
| 14 // Comparer for PositionTableEntry instances. |
| 15 struct PositionTableEntryComparer { |
| 16 bool operator()(const PositionTableEntry& lhs, |
| 17 const PositionTableEntry& rhs) { |
| 18 int lhs_type_score = type_score(lhs); |
| 19 int rhs_type_score = type_score(rhs); |
| 20 if (lhs_type_score == rhs_type_score) { |
| 21 return lhs.source_position < rhs.source_position; |
| 22 } else { |
| 23 return lhs_type_score < rhs_type_score; |
| 24 } |
| 25 } |
| 26 |
| 27 int type_score(const PositionTableEntry& entry) { |
| 28 return entry.is_statement ? 1 : 0; |
| 29 } |
| 30 }; |
| 31 |
| 32 // |
| 33 // The principles for comparing source positions in bytecode arrays |
| 34 // are: |
| 35 // |
| 36 // 1. The number of statement positions must be the same in both. |
| 37 // |
| 38 // 2. Statement positions may be moved provide they do not affect the |
| 39 // debuggers causal view of the v8 heap and local state. This means |
| 40 // statement positions may be moved when their initial position is |
| 41 // on bytecodes that manipulate the accumulator and temporary |
| 42 // registers. |
| 43 // |
| 44 // 3. When duplicate expression positions are present, either may |
| 45 // be dropped. |
| 46 // |
| 47 // 4. Expression positions may be applied to later bytecodes in the |
| 48 // bytecode array if the current bytecode does not throw. |
| 49 // |
| 50 // 5. Expression positions may be dropped when they are applied to |
| 51 // bytecodes that manipulate local frame state and immediately |
| 52 // proceeded by another source position. |
| 53 // |
| 54 // 6. The relative ordering of source positions must be preserved. |
| 55 // |
| 56 bool SourcePositionMatcher::Match(Handle<BytecodeArray> original_bytecode, |
| 57 Handle<BytecodeArray> optimized_bytecode) { |
| 58 SourcePositionTableIterator original( |
| 59 original_bytecode->source_position_table()); |
| 60 SourcePositionTableIterator optimized( |
| 61 optimized_bytecode->source_position_table()); |
| 62 |
| 63 int last_original_bytecode_offset = 0; |
| 64 int last_optimized_bytecode_offset = 0; |
| 65 |
| 66 // Ordered lists of expression positions immediately before the |
| 67 // latest statements in each bytecode array. |
| 68 std::vector<PositionTableEntry> original_expression_entries; |
| 69 std::vector<PositionTableEntry> optimized_expression_entries; |
| 70 |
| 71 while (true) { |
| 72 MoveToNextStatement(&original, &original_expression_entries); |
| 73 MoveToNextStatement(&optimized, &optimized_expression_entries); |
| 74 |
| 75 if (original.done() && optimized.done()) { |
| 76 return true; |
| 77 } else if (original.done()) { |
| 78 return false; |
| 79 } else if (optimized.done()) { |
| 80 return false; |
| 81 } |
| 82 |
| 83 if (HasNewExpressionPositionsInOptimized(&original_expression_entries, |
| 84 &optimized_expression_entries)) { |
| 85 return false; |
| 86 } |
| 87 |
| 88 StripUnneededExpressionPositions(original_bytecode, |
| 89 &original_expression_entries, |
| 90 original.bytecode_offset()); |
| 91 StripUnneededExpressionPositions(optimized_bytecode, |
| 92 &optimized_expression_entries, |
| 93 optimized.bytecode_offset()); |
| 94 |
| 95 if (!CompareExpressionPositions(&original_expression_entries, |
| 96 &optimized_expression_entries)) { |
| 97 // Message logged in CompareExpressionPositions(). |
| 98 return false; |
| 99 } |
| 100 |
| 101 // Check original and optimized have matching source positions. |
| 102 if (original.source_position() != optimized.source_position()) { |
| 103 return false; |
| 104 } |
| 105 |
| 106 if (original.bytecode_offset() < last_original_bytecode_offset) { |
| 107 return false; |
| 108 } |
| 109 last_original_bytecode_offset = original.bytecode_offset(); |
| 110 |
| 111 if (optimized.bytecode_offset() < last_optimized_bytecode_offset) { |
| 112 return false; |
| 113 } |
| 114 last_optimized_bytecode_offset = optimized.bytecode_offset(); |
| 115 |
| 116 // TODO(oth): Can we compare statement positions are semantically |
| 117 // equivalent? e.g. before a bytecode that has debugger observable |
| 118 // effects. This is likely non-trivial. |
| 119 } |
| 120 |
| 121 return true; |
| 122 } |
| 123 |
| 124 bool SourcePositionMatcher::HasNewExpressionPositionsInOptimized( |
| 125 const std::vector<PositionTableEntry>* const original_positions, |
| 126 const std::vector<PositionTableEntry>* const optimized_positions) { |
| 127 std::set<PositionTableEntry, PositionTableEntryComparer> original_set( |
| 128 original_positions->begin(), original_positions->end()); |
| 129 |
| 130 bool retval = false; |
| 131 for (auto optimized_position : *optimized_positions) { |
| 132 if (original_set.find(optimized_position) == original_set.end()) { |
| 133 retval = true; |
| 134 } |
| 135 } |
| 136 return retval; |
| 137 } |
| 138 |
| 139 bool SourcePositionMatcher::CompareExpressionPositions( |
| 140 const std::vector<PositionTableEntry>* const original_positions, |
| 141 const std::vector<PositionTableEntry>* const optimized_positions) { |
| 142 if (original_positions->size() != optimized_positions->size()) { |
| 143 return false; |
| 144 } |
| 145 |
| 146 if (original_positions->size() == 0) { |
| 147 return true; |
| 148 } |
| 149 |
| 150 for (size_t i = 0; i < original_positions->size(); ++i) { |
| 151 PositionTableEntry original = original_positions->at(i); |
| 152 PositionTableEntry optimized = original_positions->at(i); |
| 153 CHECK(original.source_position > 0); |
| 154 if ((original.is_statement || optimized.is_statement) || |
| 155 (original.source_position != optimized.source_position) || |
| 156 (original.source_position < 0)) { |
| 157 return false; |
| 158 } |
| 159 } |
| 160 return true; |
| 161 } |
| 162 |
| 163 void SourcePositionMatcher::StripUnneededExpressionPositions( |
| 164 Handle<BytecodeArray> bytecode_array, |
| 165 std::vector<PositionTableEntry>* expression_positions, |
| 166 int next_statement_bytecode_offset) { |
| 167 size_t j = 0; |
| 168 for (size_t i = 0; i < expression_positions->size(); ++i) { |
| 169 CHECK(expression_positions->at(i).source_position > 0 && |
| 170 !expression_positions->at(i).is_statement); |
| 171 int bytecode_end = (i == expression_positions->size() - 1) |
| 172 ? next_statement_bytecode_offset |
| 173 : expression_positions->at(i + 1).bytecode_offset; |
| 174 if (ExpressionPositionIsNeeded(bytecode_array, |
| 175 expression_positions->at(i).bytecode_offset, |
| 176 bytecode_end)) { |
| 177 expression_positions->at(j++) = expression_positions->at(i); |
| 178 } |
| 179 } |
| 180 expression_positions->resize(j); |
| 181 } |
| 182 |
| 183 void SourcePositionMatcher::AdvanceBytecodeIterator( |
| 184 BytecodeArrayIterator* iterator, int bytecode_offset) { |
| 185 while (iterator->current_offset() != bytecode_offset) { |
| 186 iterator->Advance(); |
| 187 } |
| 188 } |
| 189 |
| 190 bool SourcePositionMatcher::ExpressionPositionIsNeeded( |
| 191 Handle<BytecodeArray> bytecode_array, int start_offset, int end_offset) { |
| 192 CHECK_GT(end_offset, start_offset); |
| 193 BytecodeArrayIterator iterator(bytecode_array); |
| 194 AdvanceBytecodeIterator(&iterator, start_offset); |
| 195 |
| 196 while (iterator.current_offset() != end_offset) { |
| 197 if (Bytecodes::IsWithoutExternalSideEffects(iterator.current_bytecode())) { |
| 198 iterator.Advance(); |
| 199 } else { |
| 200 // Bytecode could throw so need an expression position. |
| 201 return true; |
| 202 } |
| 203 } |
| 204 return false; |
| 205 } |
| 206 |
| 207 void SourcePositionMatcher::MoveToNextStatement( |
| 208 SourcePositionTableIterator* iterator, |
| 209 std::vector<PositionTableEntry>* positions) { |
| 210 iterator->Advance(); |
| 211 positions->clear(); |
| 212 while (!iterator->done()) { |
| 213 if (iterator->is_statement()) { |
| 214 break; |
| 215 } |
| 216 positions->push_back({iterator->bytecode_offset(), |
| 217 iterator->source_position(), |
| 218 iterator->is_statement()}); |
| 219 iterator->Advance(); |
| 220 } |
| 221 } |
| 222 |
| 223 } // namespace interpreter |
| 224 } // namespace internal |
| 225 } // namespace v8 |
OLD | NEW |