Line data Source code
1 : // Copyright 2015 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 "src/v8.h"
6 :
7 : #include "src/compiler/bytecode-analysis.h"
8 : #include "src/interpreter/bytecode-array-builder.h"
9 : #include "src/interpreter/bytecode-array-iterator.h"
10 : #include "src/interpreter/bytecode-decoder.h"
11 : #include "src/interpreter/bytecode-label.h"
12 : #include "src/interpreter/control-flow-builders.h"
13 : #include "src/objects-inl.h"
14 : #include "test/unittests/test-utils.h"
15 :
16 : namespace v8 {
17 : namespace internal {
18 : namespace compiler {
19 :
20 : using ToBooleanMode = interpreter::BytecodeArrayBuilder::ToBooleanMode;
21 :
22 : class BytecodeAnalysisTest : public TestWithIsolateAndZone {
23 : public:
24 9 : BytecodeAnalysisTest() {}
25 9 : ~BytecodeAnalysisTest() override {}
26 :
27 9 : static void SetUpTestCase() {
28 9 : CHECK_NULL(save_flags_);
29 9 : save_flags_ = new SaveFlags();
30 9 : i::FLAG_ignition_elide_noneffectful_bytecodes = false;
31 9 : i::FLAG_ignition_reo = false;
32 :
33 9 : TestWithIsolateAndZone::SetUpTestCase();
34 9 : }
35 :
36 9 : static void TearDownTestCase() {
37 9 : TestWithIsolateAndZone::TearDownTestCase();
38 9 : delete save_flags_;
39 9 : save_flags_ = nullptr;
40 9 : }
41 :
42 108 : std::string ToLivenessString(const BytecodeLivenessState* liveness) const {
43 648 : const BitVector& bit_vector = liveness->bit_vector();
44 :
45 : std::string out;
46 108 : out.resize(bit_vector.length());
47 1080 : for (int i = 0; i < bit_vector.length(); ++i) {
48 432 : if (bit_vector.Contains(i)) {
49 316 : out[i] = 'L';
50 : } else {
51 548 : out[i] = '.';
52 : }
53 : }
54 108 : return out;
55 : }
56 :
57 9 : void EnsureLivenessMatches(
58 : Handle<BytecodeArray> bytecode,
59 : const std::vector<std::pair<std::string, std::string>>&
60 : expected_liveness) {
61 9 : BytecodeAnalysis analysis(bytecode, zone(), true);
62 9 : analysis.Analyze(BailoutId::None());
63 :
64 9 : interpreter::BytecodeArrayIterator iterator(bytecode);
65 72 : for (auto liveness : expected_liveness) {
66 108 : std::stringstream ss;
67 108 : ss << std::setw(4) << iterator.current_offset() << " : ";
68 54 : iterator.PrintTo(ss);
69 :
70 108 : EXPECT_EQ(liveness.first, ToLivenessString(analysis.GetInLivenessFor(
71 : iterator.current_offset())))
72 0 : << " at bytecode " << ss.str();
73 :
74 108 : EXPECT_EQ(liveness.second, ToLivenessString(analysis.GetOutLivenessFor(
75 : iterator.current_offset())))
76 0 : << " at bytecode " << ss.str();
77 :
78 54 : iterator.Advance();
79 54 : }
80 :
81 27 : EXPECT_TRUE(iterator.done());
82 9 : }
83 :
84 : private:
85 : static SaveFlags* save_flags_;
86 :
87 : DISALLOW_COPY_AND_ASSIGN(BytecodeAnalysisTest);
88 : };
89 :
90 : SaveFlags* BytecodeAnalysisTest::save_flags_ = nullptr;
91 :
92 13160 : TEST_F(BytecodeAnalysisTest, EmptyBlock) {
93 2 : interpreter::BytecodeArrayBuilder builder(isolate(), zone(), 3, 3);
94 1 : std::vector<std::pair<std::string, std::string>> expected_liveness;
95 :
96 : interpreter::Register reg_0(0);
97 :
98 1 : builder.Return();
99 1 : expected_liveness.emplace_back("...L", "....");
100 :
101 1 : Handle<BytecodeArray> bytecode = builder.ToBytecodeArray(isolate());
102 :
103 1 : EnsureLivenessMatches(bytecode, expected_liveness);
104 1 : }
105 :
106 13160 : TEST_F(BytecodeAnalysisTest, SimpleLoad) {
107 2 : interpreter::BytecodeArrayBuilder builder(isolate(), zone(), 3, 3);
108 1 : std::vector<std::pair<std::string, std::string>> expected_liveness;
109 :
110 : interpreter::Register reg_0(0);
111 :
112 1 : builder.LoadAccumulatorWithRegister(reg_0);
113 1 : expected_liveness.emplace_back("L...", "...L");
114 :
115 1 : builder.Return();
116 1 : expected_liveness.emplace_back("...L", "....");
117 :
118 1 : Handle<BytecodeArray> bytecode = builder.ToBytecodeArray(isolate());
119 :
120 1 : EnsureLivenessMatches(bytecode, expected_liveness);
121 1 : }
122 :
123 13160 : TEST_F(BytecodeAnalysisTest, StoreThenLoad) {
124 2 : interpreter::BytecodeArrayBuilder builder(isolate(), zone(), 3, 3);
125 1 : std::vector<std::pair<std::string, std::string>> expected_liveness;
126 :
127 : interpreter::Register reg_0(0);
128 :
129 1 : builder.StoreAccumulatorInRegister(reg_0);
130 1 : expected_liveness.emplace_back("...L", "L...");
131 :
132 1 : builder.LoadAccumulatorWithRegister(reg_0);
133 1 : expected_liveness.emplace_back("L...", "...L");
134 :
135 1 : builder.Return();
136 1 : expected_liveness.emplace_back("...L", "....");
137 :
138 1 : Handle<BytecodeArray> bytecode = builder.ToBytecodeArray(isolate());
139 :
140 1 : EnsureLivenessMatches(bytecode, expected_liveness);
141 1 : }
142 :
143 13160 : TEST_F(BytecodeAnalysisTest, DiamondLoad) {
144 2 : interpreter::BytecodeArrayBuilder builder(isolate(), zone(), 3, 3);
145 1 : std::vector<std::pair<std::string, std::string>> expected_liveness;
146 :
147 : interpreter::Register reg_0(0);
148 : interpreter::Register reg_1(1);
149 : interpreter::Register reg_2(2);
150 :
151 : interpreter::BytecodeLabel ld1_label;
152 : interpreter::BytecodeLabel end_label;
153 :
154 1 : builder.JumpIfTrue(ToBooleanMode::kConvertToBoolean, &ld1_label);
155 1 : expected_liveness.emplace_back("LLLL", "LLL.");
156 :
157 1 : builder.LoadAccumulatorWithRegister(reg_0);
158 1 : expected_liveness.emplace_back("L.L.", "..L.");
159 :
160 1 : builder.Jump(&end_label);
161 1 : expected_liveness.emplace_back("..L.", "..L.");
162 :
163 1 : builder.Bind(&ld1_label);
164 1 : builder.LoadAccumulatorWithRegister(reg_1);
165 1 : expected_liveness.emplace_back(".LL.", "..L.");
166 :
167 1 : builder.Bind(&end_label);
168 :
169 1 : builder.LoadAccumulatorWithRegister(reg_2);
170 1 : expected_liveness.emplace_back("..L.", "...L");
171 :
172 1 : builder.Return();
173 1 : expected_liveness.emplace_back("...L", "....");
174 :
175 1 : Handle<BytecodeArray> bytecode = builder.ToBytecodeArray(isolate());
176 :
177 1 : EnsureLivenessMatches(bytecode, expected_liveness);
178 1 : }
179 :
180 13160 : TEST_F(BytecodeAnalysisTest, DiamondLookupsAndBinds) {
181 2 : interpreter::BytecodeArrayBuilder builder(isolate(), zone(), 3, 3);
182 1 : std::vector<std::pair<std::string, std::string>> expected_liveness;
183 :
184 : interpreter::Register reg_0(0);
185 : interpreter::Register reg_1(1);
186 : interpreter::Register reg_2(2);
187 :
188 : interpreter::BytecodeLabel ld1_label;
189 : interpreter::BytecodeLabel end_label;
190 :
191 1 : builder.StoreAccumulatorInRegister(reg_0);
192 1 : expected_liveness.emplace_back(".LLL", "LLLL");
193 :
194 1 : builder.JumpIfTrue(ToBooleanMode::kConvertToBoolean, &ld1_label);
195 1 : expected_liveness.emplace_back("LLLL", "LLL.");
196 :
197 : {
198 1 : builder.LoadAccumulatorWithRegister(reg_0);
199 1 : expected_liveness.emplace_back("L...", "...L");
200 :
201 1 : builder.StoreAccumulatorInRegister(reg_2);
202 1 : expected_liveness.emplace_back("...L", "..L.");
203 :
204 1 : builder.Jump(&end_label);
205 1 : expected_liveness.emplace_back("..L.", "..L.");
206 : }
207 :
208 1 : builder.Bind(&ld1_label);
209 : {
210 1 : builder.LoadAccumulatorWithRegister(reg_1);
211 1 : expected_liveness.emplace_back(".LL.", "..L.");
212 : }
213 :
214 1 : builder.Bind(&end_label);
215 :
216 1 : builder.LoadAccumulatorWithRegister(reg_2);
217 1 : expected_liveness.emplace_back("..L.", "...L");
218 :
219 1 : builder.Return();
220 1 : expected_liveness.emplace_back("...L", "....");
221 :
222 1 : Handle<BytecodeArray> bytecode = builder.ToBytecodeArray(isolate());
223 :
224 1 : EnsureLivenessMatches(bytecode, expected_liveness);
225 1 : }
226 :
227 13160 : TEST_F(BytecodeAnalysisTest, SimpleLoop) {
228 2 : interpreter::BytecodeArrayBuilder builder(isolate(), zone(), 3, 3);
229 1 : std::vector<std::pair<std::string, std::string>> expected_liveness;
230 :
231 : interpreter::Register reg_0(0);
232 : interpreter::Register reg_1(1);
233 : interpreter::Register reg_2(2);
234 :
235 : // Kill r0.
236 1 : builder.StoreAccumulatorInRegister(reg_0);
237 1 : expected_liveness.emplace_back("..LL", "L.L.");
238 :
239 : {
240 1 : interpreter::LoopBuilder loop_builder(&builder, nullptr, nullptr);
241 1 : loop_builder.LoopHeader();
242 :
243 1 : builder.LoadUndefined();
244 1 : expected_liveness.emplace_back("L.L.", "L.LL");
245 :
246 : builder.JumpIfTrue(ToBooleanMode::kConvertToBoolean,
247 1 : loop_builder.break_labels()->New());
248 1 : expected_liveness.emplace_back("L.LL", "L.L.");
249 :
250 : // Gen r0.
251 1 : builder.LoadAccumulatorWithRegister(reg_0);
252 1 : expected_liveness.emplace_back("L...", "L..L");
253 :
254 : // Kill r2.
255 1 : builder.StoreAccumulatorInRegister(reg_2);
256 1 : expected_liveness.emplace_back("L..L", "L.L.");
257 :
258 1 : loop_builder.BindContinueTarget();
259 1 : loop_builder.JumpToHeader(0);
260 1 : expected_liveness.emplace_back("L.L.", "L.L.");
261 : }
262 :
263 : // Gen r2.
264 1 : builder.LoadAccumulatorWithRegister(reg_2);
265 1 : expected_liveness.emplace_back("..L.", "...L");
266 :
267 1 : builder.Return();
268 1 : expected_liveness.emplace_back("...L", "....");
269 :
270 1 : Handle<BytecodeArray> bytecode = builder.ToBytecodeArray(isolate());
271 :
272 1 : EnsureLivenessMatches(bytecode, expected_liveness);
273 1 : }
274 :
275 13160 : TEST_F(BytecodeAnalysisTest, TryCatch) {
276 2 : interpreter::BytecodeArrayBuilder builder(isolate(), zone(), 3, 3);
277 1 : std::vector<std::pair<std::string, std::string>> expected_liveness;
278 :
279 : interpreter::Register reg_0(0);
280 : interpreter::Register reg_1(1);
281 : interpreter::Register reg_context(2);
282 :
283 : // Kill r0.
284 1 : builder.StoreAccumulatorInRegister(reg_0);
285 1 : expected_liveness.emplace_back(".LLL", "LLL.");
286 :
287 : interpreter::TryCatchBuilder try_builder(&builder, HandlerTable::CAUGHT);
288 1 : try_builder.BeginTry(reg_context);
289 : {
290 : // Gen r0.
291 1 : builder.LoadAccumulatorWithRegister(reg_0);
292 1 : expected_liveness.emplace_back("LLL.", ".LLL");
293 :
294 : // Kill r0.
295 1 : builder.StoreAccumulatorInRegister(reg_0);
296 1 : expected_liveness.emplace_back(".LLL", ".LL.");
297 :
298 1 : builder.CallRuntime(Runtime::kThrow);
299 1 : expected_liveness.emplace_back(".LL.", ".LLL");
300 :
301 1 : builder.StoreAccumulatorInRegister(reg_0);
302 : // Star can't throw, so doesn't take handler liveness
303 1 : expected_liveness.emplace_back("...L", "...L");
304 : }
305 1 : try_builder.EndTry();
306 1 : expected_liveness.emplace_back("...L", "...L");
307 :
308 : // Catch
309 : {
310 1 : builder.LoadAccumulatorWithRegister(reg_1);
311 1 : expected_liveness.emplace_back(".L..", "...L");
312 : }
313 1 : try_builder.EndCatch();
314 :
315 1 : builder.Return();
316 1 : expected_liveness.emplace_back("...L", "....");
317 :
318 1 : Handle<BytecodeArray> bytecode = builder.ToBytecodeArray(isolate());
319 :
320 1 : EnsureLivenessMatches(bytecode, expected_liveness);
321 1 : }
322 :
323 13160 : TEST_F(BytecodeAnalysisTest, DiamondInLoop) {
324 : // For a logic diamond inside a loop, the liveness down one path of the
325 : // diamond should eventually propagate up the other path when the loop is
326 : // reprocessed.
327 :
328 2 : interpreter::BytecodeArrayBuilder builder(isolate(), zone(), 3, 3);
329 1 : std::vector<std::pair<std::string, std::string>> expected_liveness;
330 :
331 : interpreter::Register reg_0(0);
332 :
333 : {
334 1 : interpreter::LoopBuilder loop_builder(&builder, nullptr, nullptr);
335 1 : loop_builder.LoopHeader();
336 :
337 1 : builder.LoadUndefined();
338 1 : expected_liveness.emplace_back("L...", "L..L");
339 : builder.JumpIfTrue(ToBooleanMode::kConvertToBoolean,
340 1 : loop_builder.break_labels()->New());
341 1 : expected_liveness.emplace_back("L..L", "L..L");
342 :
343 : interpreter::BytecodeLabel ld1_label;
344 : interpreter::BytecodeLabel end_label;
345 1 : builder.JumpIfTrue(ToBooleanMode::kConvertToBoolean, &ld1_label);
346 1 : expected_liveness.emplace_back("L..L", "L...");
347 :
348 : {
349 1 : builder.Jump(&end_label);
350 1 : expected_liveness.emplace_back("L...", "L...");
351 : }
352 :
353 1 : builder.Bind(&ld1_label);
354 : {
355 : // Gen r0.
356 1 : builder.LoadAccumulatorWithRegister(reg_0);
357 1 : expected_liveness.emplace_back("L...", "L...");
358 : }
359 :
360 1 : builder.Bind(&end_label);
361 :
362 1 : loop_builder.BindContinueTarget();
363 1 : loop_builder.JumpToHeader(0);
364 1 : expected_liveness.emplace_back("L...", "L...");
365 : }
366 :
367 1 : builder.LoadUndefined();
368 1 : expected_liveness.emplace_back("....", "...L");
369 1 : builder.Return();
370 1 : expected_liveness.emplace_back("...L", "....");
371 :
372 1 : Handle<BytecodeArray> bytecode = builder.ToBytecodeArray(isolate());
373 :
374 1 : EnsureLivenessMatches(bytecode, expected_liveness);
375 1 : }
376 :
377 13160 : TEST_F(BytecodeAnalysisTest, KillingLoopInsideLoop) {
378 : // For a loop inside a loop, the inner loop has to be processed after the
379 : // outer loop has been processed, to ensure that it can propagate the
380 : // information in its header. Consider
381 : //
382 : // 0: do {
383 : // 1: acc = r0;
384 : // 2: acc = r1;
385 : // 3: do {
386 : // 4: r0 = acc;
387 : // 5: break;
388 : // 6: } while(true);
389 : // 7: } while(true);
390 : //
391 : // r0 should should be dead at 3 and 6, while r1 is live throughout. On the
392 : // initial pass, r1 is dead from 3-7. On the outer loop pass, it becomes live
393 : // in 3 and 7 (but not 4-6 because 6 only reads liveness from 3). Only after
394 : // the inner loop pass does it become live in 4-6. It's necessary, however, to
395 : // still process the inner loop when processing the outer loop, to ensure that
396 : // r1 becomes live in 3 (via 5), but r0 stays dead (because of 4).
397 :
398 2 : interpreter::BytecodeArrayBuilder builder(isolate(), zone(), 3, 3);
399 1 : std::vector<std::pair<std::string, std::string>> expected_liveness;
400 :
401 : interpreter::Register reg_0(0);
402 : interpreter::Register reg_1(1);
403 :
404 : {
405 1 : interpreter::LoopBuilder loop_builder(&builder, nullptr, nullptr);
406 1 : loop_builder.LoopHeader();
407 :
408 : // Gen r0.
409 1 : builder.LoadAccumulatorWithRegister(reg_0);
410 1 : expected_liveness.emplace_back("LL..", ".L..");
411 :
412 : // Gen r1.
413 1 : builder.LoadAccumulatorWithRegister(reg_1);
414 1 : expected_liveness.emplace_back(".L..", ".L.L");
415 :
416 : builder.JumpIfTrue(ToBooleanMode::kConvertToBoolean,
417 1 : loop_builder.break_labels()->New());
418 1 : expected_liveness.emplace_back(".L.L", ".L..");
419 :
420 : {
421 1 : interpreter::LoopBuilder inner_loop_builder(&builder, nullptr, nullptr);
422 1 : inner_loop_builder.LoopHeader();
423 :
424 : // Kill r0.
425 1 : builder.LoadUndefined();
426 1 : expected_liveness.emplace_back(".L..", ".L.L");
427 1 : builder.StoreAccumulatorInRegister(reg_0);
428 1 : expected_liveness.emplace_back(".L.L", "LL.L");
429 :
430 : builder.JumpIfTrue(ToBooleanMode::kConvertToBoolean,
431 1 : inner_loop_builder.break_labels()->New());
432 1 : expected_liveness.emplace_back("LL.L", "LL..");
433 :
434 1 : inner_loop_builder.BindContinueTarget();
435 1 : inner_loop_builder.JumpToHeader(1);
436 1 : expected_liveness.emplace_back(".L..", ".L..");
437 : }
438 :
439 1 : loop_builder.BindContinueTarget();
440 1 : loop_builder.JumpToHeader(0);
441 1 : expected_liveness.emplace_back("LL..", "LL..");
442 : }
443 :
444 1 : builder.LoadUndefined();
445 1 : expected_liveness.emplace_back("....", "...L");
446 1 : builder.Return();
447 1 : expected_liveness.emplace_back("...L", "....");
448 :
449 1 : Handle<BytecodeArray> bytecode = builder.ToBytecodeArray(isolate());
450 :
451 1 : EnsureLivenessMatches(bytecode, expected_liveness);
452 1 : }
453 :
454 : } // namespace compiler
455 : } // namespace internal
456 7893 : } // namespace v8
|
