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