Line data Source code
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 5850 : if (lhs_type_score == rhs_type_score) {
21 5850 : return lhs.source_position < rhs.source_position;
22 : } else {
23 0 : return lhs_type_score < rhs_type_score;
24 : }
25 : }
26 :
27 : int type_score(const PositionTableEntry& entry) const {
28 5850 : 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 240 : bool SourcePositionMatcher::Match(Handle<BytecodeArray> original_bytecode,
57 : Handle<BytecodeArray> optimized_bytecode) {
58 : SourcePositionTableIterator original(
59 240 : original_bytecode->SourcePositionTable());
60 : SourcePositionTableIterator optimized(
61 240 : optimized_bytecode->SourcePositionTable());
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 1440 : MoveToNextStatement(&original, &original_expression_entries);
73 1440 : MoveToNextStatement(&optimized, &optimized_expression_entries);
74 :
75 1440 : if (original.done() && optimized.done()) {
76 : return true;
77 1200 : } else if (original.done()) {
78 : return false;
79 1200 : } else if (optimized.done()) {
80 : return false;
81 : }
82 :
83 1200 : if (HasNewExpressionPositionsInOptimized(&original_expression_entries,
84 : &optimized_expression_entries)) {
85 : return false;
86 : }
87 :
88 : StripUnneededExpressionPositions(original_bytecode,
89 : &original_expression_entries,
90 1200 : original.code_offset());
91 : StripUnneededExpressionPositions(optimized_bytecode,
92 : &optimized_expression_entries,
93 1200 : optimized.code_offset());
94 :
95 1200 : 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 1200 : if (original.source_position() != optimized.source_position()) {
103 : return false;
104 : }
105 :
106 1200 : if (original.code_offset() < last_original_bytecode_offset) {
107 : return false;
108 : }
109 : last_original_bytecode_offset = original.code_offset();
110 :
111 1200 : if (optimized.code_offset() < last_optimized_bytecode_offset) {
112 : return false;
113 : }
114 : last_optimized_bytecode_offset = optimized.code_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 1200 : 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 1200 : original_positions->begin(), original_positions->end());
129 :
130 : bool retval = false;
131 2520 : for (auto optimized_position : *optimized_positions) {
132 1320 : if (original_set.find(optimized_position) == original_set.end()) {
133 : retval = true;
134 : }
135 : }
136 1200 : return retval;
137 : }
138 :
139 1200 : bool SourcePositionMatcher::CompareExpressionPositions(
140 : const std::vector<PositionTableEntry>* const original_positions,
141 : const std::vector<PositionTableEntry>* const optimized_positions) {
142 1200 : if (original_positions->size() != optimized_positions->size()) {
143 : return false;
144 : }
145 :
146 1200 : if (original_positions->size() == 0) {
147 : return true;
148 : }
149 :
150 1950 : for (size_t i = 0; i < original_positions->size(); ++i) {
151 765 : PositionTableEntry original = original_positions->at(i);
152 : PositionTableEntry optimized = original_positions->at(i);
153 765 : CHECK_GT(original.source_position, 0);
154 765 : if ((original.is_statement || optimized.is_statement) ||
155 765 : (original.source_position != optimized.source_position) ||
156 : (original.source_position < 0)) {
157 : return false;
158 : }
159 : }
160 : return true;
161 : }
162 :
163 2400 : 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 7680 : for (size_t i = 0; i < expression_positions->size(); ++i) {
169 5280 : CHECK(expression_positions->at(i).source_position > 0 &&
170 : !expression_positions->at(i).is_statement);
171 2640 : int bytecode_end = (i == expression_positions->size() - 1)
172 : ? next_statement_bytecode_offset
173 3900 : : expression_positions->at(i + 1).code_offset;
174 2640 : if (ExpressionPositionIsNeeded(bytecode_array,
175 : expression_positions->at(i).code_offset,
176 : bytecode_end)) {
177 3060 : expression_positions->at(j++) = expression_positions->at(i);
178 : }
179 : }
180 2400 : expression_positions->resize(j);
181 2400 : }
182 :
183 0 : void SourcePositionMatcher::AdvanceBytecodeIterator(
184 : BytecodeArrayIterator* iterator, int bytecode_offset) {
185 43860 : while (iterator->current_offset() != bytecode_offset) {
186 41220 : iterator->Advance();
187 : }
188 0 : }
189 :
190 2640 : bool SourcePositionMatcher::ExpressionPositionIsNeeded(
191 : Handle<BytecodeArray> bytecode_array, int start_offset, int end_offset) {
192 2640 : CHECK_GT(end_offset, start_offset);
193 2640 : BytecodeArrayIterator iterator(bytecode_array);
194 : AdvanceBytecodeIterator(&iterator, start_offset);
195 :
196 1710 : while (iterator.current_offset() != end_offset) {
197 3240 : if (Bytecodes::IsWithoutExternalSideEffects(iterator.current_bytecode())) {
198 1710 : iterator.Advance();
199 : } else {
200 : // Bytecode could throw so need an expression position.
201 : return true;
202 : }
203 : }
204 : return false;
205 : }
206 :
207 2880 : void SourcePositionMatcher::MoveToNextStatement(
208 : SourcePositionTableIterator* iterator,
209 : std::vector<PositionTableEntry>* positions) {
210 2880 : iterator->Advance();
211 : positions->clear();
212 8160 : while (!iterator->done()) {
213 5040 : if (iterator->is_statement()) {
214 : break;
215 : }
216 2640 : positions->push_back({iterator->code_offset(),
217 : iterator->source_position().raw(),
218 : iterator->is_statement()});
219 2640 : iterator->Advance();
220 : }
221 2880 : }
222 :
223 : } // namespace interpreter
224 : } // namespace internal
225 53312 : } // namespace v8
|
