Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 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) const { |
| 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) const { |
| 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 |