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