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 226