1 /*
2 * Copyright (C) 2014 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "android-base/stringprintf.h"
18
19 #include "base/arena_allocator.h"
20 #include "base/macros.h"
21 #include "builder.h"
22 #include "dex/dex_file.h"
23 #include "dex/dex_instruction.h"
24 #include "nodes.h"
25 #include "optimizing_unit_test.h"
26 #include "pretty_printer.h"
27 #include "ssa_builder.h"
28
29 #include "gtest/gtest.h"
30
31 namespace art HIDDEN {
32
33 class SsaTest : public CommonCompilerTest, public OptimizingUnitTestHelper {
34 protected:
35 void TestCode(const std::vector<uint16_t>& data, const char* expected);
36 };
37
38 class SsaPrettyPrinter : public HPrettyPrinter {
39 public:
SsaPrettyPrinter(HGraph * graph)40 explicit SsaPrettyPrinter(HGraph* graph) : HPrettyPrinter(graph), str_("") {}
41
PrintInt(int value)42 void PrintInt(int value) override {
43 str_ += android::base::StringPrintf("%d", value);
44 }
45
PrintString(const char * value)46 void PrintString(const char* value) override {
47 str_ += value;
48 }
49
PrintNewLine()50 void PrintNewLine() override {
51 str_ += '\n';
52 }
53
Clear()54 void Clear() { str_.clear(); }
55
str() const56 std::string str() const { return str_; }
57
VisitIntConstant(HIntConstant * constant)58 void VisitIntConstant(HIntConstant* constant) override {
59 PrintPreInstruction(constant);
60 str_ += constant->DebugName();
61 str_ += " ";
62 PrintInt(constant->GetValue());
63 PrintPostInstruction(constant);
64 }
65
66 private:
67 std::string str_;
68
69 DISALLOW_COPY_AND_ASSIGN(SsaPrettyPrinter);
70 };
71
ReNumberInstructions(HGraph * graph)72 static void ReNumberInstructions(HGraph* graph) {
73 int id = 0;
74 for (HBasicBlock* block : graph->GetBlocks()) {
75 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
76 it.Current()->SetId(id++);
77 }
78 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
79 it.Current()->SetId(id++);
80 }
81 }
82 }
83
TestCode(const std::vector<uint16_t> & data,const char * expected)84 void SsaTest::TestCode(const std::vector<uint16_t>& data, const char* expected) {
85 HGraph* graph = CreateCFG(data);
86 // Suspend checks implementation may change in the future, and this test relies
87 // on how instructions are ordered.
88 RemoveSuspendChecks(graph);
89 ReNumberInstructions(graph);
90
91 // Test that phis had their type set.
92 for (HBasicBlock* block : graph->GetBlocks()) {
93 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
94 ASSERT_NE(it.Current()->GetType(), DataType::Type::kVoid);
95 }
96 }
97
98 SsaPrettyPrinter printer(graph);
99 printer.VisitInsertionOrder();
100
101 ASSERT_STREQ(expected, printer.str().c_str());
102 }
103
TEST_F(SsaTest,CFG1)104 TEST_F(SsaTest, CFG1) {
105 // Test that we get rid of loads and stores.
106 const char* expected =
107 "BasicBlock 0, succ: 1\n"
108 " 0: IntConstant 0 [2, 2]\n"
109 " 1: Goto\n"
110 "BasicBlock 1, pred: 0, succ: 5, 2\n"
111 " 2: Equal(0, 0) [3]\n"
112 " 3: If(2)\n"
113 "BasicBlock 2, pred: 1, succ: 3\n"
114 " 4: Goto\n"
115 "BasicBlock 3, pred: 5, 2, succ: 4\n"
116 " 5: ReturnVoid\n"
117 "BasicBlock 4, pred: 3\n"
118 " 6: Exit\n"
119 // Synthesized block to avoid critical edge.
120 "BasicBlock 5, pred: 1, succ: 3\n"
121 " 7: Goto\n";
122
123 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
124 Instruction::CONST_4 | 0 | 0,
125 Instruction::IF_EQ, 3,
126 Instruction::GOTO | 0x100,
127 Instruction::RETURN_VOID);
128
129 TestCode(data, expected);
130 }
131
TEST_F(SsaTest,CFG2)132 TEST_F(SsaTest, CFG2) {
133 // Test that we create a phi for the join block of an if control flow instruction
134 // when there is only code in the else branch.
135 const char* expected =
136 "BasicBlock 0, succ: 1\n"
137 " 0: IntConstant 0 [6, 3, 3]\n"
138 " 1: IntConstant 4 [6]\n"
139 " 2: Goto\n"
140 "BasicBlock 1, pred: 0, succ: 5, 2\n"
141 " 3: Equal(0, 0) [4]\n"
142 " 4: If(3)\n"
143 "BasicBlock 2, pred: 1, succ: 3\n"
144 " 5: Goto\n"
145 "BasicBlock 3, pred: 5, 2, succ: 4\n"
146 " 6: Phi(0, 1) [7]\n"
147 " 7: Return(6)\n"
148 "BasicBlock 4, pred: 3\n"
149 " 8: Exit\n"
150 // Synthesized block to avoid critical edge.
151 "BasicBlock 5, pred: 1, succ: 3\n"
152 " 9: Goto\n";
153
154 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
155 Instruction::CONST_4 | 0 | 0,
156 Instruction::IF_EQ, 3,
157 Instruction::CONST_4 | 4 << 12 | 0,
158 Instruction::RETURN | 0 << 8);
159
160 TestCode(data, expected);
161 }
162
TEST_F(SsaTest,CFG3)163 TEST_F(SsaTest, CFG3) {
164 // Test that we create a phi for the join block of an if control flow instruction
165 // when both branches update a local.
166 const char* expected =
167 "BasicBlock 0, succ: 1\n"
168 " 0: IntConstant 0 [4, 4]\n"
169 " 1: IntConstant 5 [8]\n"
170 " 2: IntConstant 4 [8]\n"
171 " 3: Goto\n"
172 "BasicBlock 1, pred: 0, succ: 3, 2\n"
173 " 4: Equal(0, 0) [5]\n"
174 " 5: If(4)\n"
175 "BasicBlock 2, pred: 1, succ: 4\n"
176 " 6: Goto\n"
177 "BasicBlock 3, pred: 1, succ: 4\n"
178 " 7: Goto\n"
179 "BasicBlock 4, pred: 2, 3, succ: 5\n"
180 " 8: Phi(2, 1) [9]\n"
181 " 9: Return(8)\n"
182 "BasicBlock 5, pred: 4\n"
183 " 10: Exit\n";
184
185 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
186 Instruction::CONST_4 | 0 | 0,
187 Instruction::IF_EQ, 4,
188 Instruction::CONST_4 | 4 << 12 | 0,
189 Instruction::GOTO | 0x200,
190 Instruction::CONST_4 | 5 << 12 | 0,
191 Instruction::RETURN | 0 << 8);
192
193 TestCode(data, expected);
194 }
195
TEST_F(SsaTest,Loop1)196 TEST_F(SsaTest, Loop1) {
197 // Test that we create a phi for an initialized local at entry of a loop.
198 const char* expected =
199 "BasicBlock 0, succ: 1\n"
200 " 0: IntConstant 0 [6, 3, 3]\n"
201 " 1: IntConstant 4 [6]\n"
202 " 2: Goto\n"
203 "BasicBlock 1, pred: 0, succ: 4, 2\n"
204 " 3: Equal(0, 0) [4]\n"
205 " 4: If(3)\n"
206 "BasicBlock 2, pred: 1, succ: 3\n"
207 " 5: Goto\n"
208 "BasicBlock 3, pred: 2, 4, succ: 5\n"
209 " 6: Phi(1, 0) [9]\n"
210 " 7: Goto\n"
211 "BasicBlock 4, pred: 1, succ: 3\n"
212 " 8: Goto\n"
213 "BasicBlock 5, pred: 3, succ: 6\n"
214 " 9: Return(6)\n"
215 "BasicBlock 6, pred: 5\n"
216 " 10: Exit\n";
217
218 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
219 Instruction::CONST_4 | 0 | 0,
220 Instruction::IF_EQ, 4,
221 Instruction::CONST_4 | 4 << 12 | 0,
222 Instruction::GOTO | 0x200,
223 Instruction::GOTO | 0xFF00,
224 Instruction::RETURN | 0 << 8);
225
226 TestCode(data, expected);
227 }
228
TEST_F(SsaTest,Loop2)229 TEST_F(SsaTest, Loop2) {
230 // Simple loop with one preheader and one back edge.
231 const char* expected =
232 "BasicBlock 0, succ: 1\n"
233 " 0: IntConstant 0 [4]\n"
234 " 1: IntConstant 4 [4]\n"
235 " 2: Goto\n"
236 "BasicBlock 1, pred: 0, succ: 2\n"
237 " 3: Goto\n"
238 "BasicBlock 2, pred: 1, 3, succ: 4, 3\n"
239 " 4: Phi(0, 1) [5, 5]\n"
240 " 5: Equal(4, 4) [6]\n"
241 " 6: If(5)\n"
242 "BasicBlock 3, pred: 2, succ: 2\n"
243 " 7: Goto\n"
244 "BasicBlock 4, pred: 2, succ: 5\n"
245 " 8: ReturnVoid\n"
246 "BasicBlock 5, pred: 4\n"
247 " 9: Exit\n";
248
249 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
250 Instruction::CONST_4 | 0 | 0,
251 Instruction::IF_EQ, 4,
252 Instruction::CONST_4 | 4 << 12 | 0,
253 Instruction::GOTO | 0xFD00,
254 Instruction::RETURN_VOID);
255
256 TestCode(data, expected);
257 }
258
TEST_F(SsaTest,Loop3)259 TEST_F(SsaTest, Loop3) {
260 // Test that a local not yet defined at the entry of a loop is handled properly.
261 const char* expected =
262 "BasicBlock 0, succ: 1\n"
263 " 0: IntConstant 0 [5]\n"
264 " 1: IntConstant 5 [9]\n"
265 " 2: IntConstant 4 [5]\n"
266 " 3: Goto\n"
267 "BasicBlock 1, pred: 0, succ: 2\n"
268 " 4: Goto\n"
269 "BasicBlock 2, pred: 1, 3, succ: 4, 3\n"
270 " 5: Phi(0, 2) [6, 6]\n"
271 " 6: Equal(5, 5) [7]\n"
272 " 7: If(6)\n"
273 "BasicBlock 3, pred: 2, succ: 2\n"
274 " 8: Goto\n"
275 "BasicBlock 4, pred: 2, succ: 5\n"
276 " 9: Return(1)\n"
277 "BasicBlock 5, pred: 4\n"
278 " 10: Exit\n";
279
280 const std::vector<uint16_t> data = TWO_REGISTERS_CODE_ITEM(
281 Instruction::CONST_4 | 0 | 0,
282 Instruction::IF_EQ, 4,
283 Instruction::CONST_4 | 4 << 12 | 0,
284 Instruction::GOTO | 0xFD00,
285 Instruction::CONST_4 | 5 << 12 | 1 << 8,
286 Instruction::RETURN | 1 << 8);
287
288 TestCode(data, expected);
289 }
290
TEST_F(SsaTest,Loop4)291 TEST_F(SsaTest, Loop4) {
292 // Make sure we support a preheader of a loop not being the first predecessor
293 // in the predecessor list of the header.
294 const char* expected =
295 "BasicBlock 0, succ: 1\n"
296 " 0: IntConstant 0 [4]\n"
297 " 1: IntConstant 4 [4]\n"
298 " 2: Goto\n"
299 "BasicBlock 1, pred: 0, succ: 4\n"
300 " 3: Goto\n"
301 "BasicBlock 2, pred: 4, 3, succ: 5, 3\n"
302 " 4: Phi(0, 1) [9, 5, 5]\n"
303 " 5: Equal(4, 4) [6]\n"
304 " 6: If(5)\n"
305 "BasicBlock 3, pred: 2, succ: 2\n"
306 " 7: Goto\n"
307 "BasicBlock 4, pred: 1, succ: 2\n"
308 " 8: Goto\n"
309 "BasicBlock 5, pred: 2, succ: 6\n"
310 " 9: Return(4)\n"
311 "BasicBlock 6, pred: 5\n"
312 " 10: Exit\n";
313
314 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
315 Instruction::CONST_4 | 0 | 0,
316 Instruction::GOTO | 0x500,
317 Instruction::IF_EQ, 5,
318 Instruction::CONST_4 | 4 << 12 | 0,
319 Instruction::GOTO | 0xFD00,
320 Instruction::GOTO | 0xFC00,
321 Instruction::RETURN | 0 << 8);
322
323 TestCode(data, expected);
324 }
325
TEST_F(SsaTest,Loop5)326 TEST_F(SsaTest, Loop5) {
327 // Make sure we create a preheader of a loop when a header originally has two
328 // incoming blocks and one back edge.
329 const char* expected =
330 "BasicBlock 0, succ: 1\n"
331 " 0: IntConstant 0 [4, 4]\n"
332 " 1: IntConstant 5 [13]\n"
333 " 2: IntConstant 4 [13]\n"
334 " 3: Goto\n"
335 "BasicBlock 1, pred: 0, succ: 3, 2\n"
336 " 4: Equal(0, 0) [5]\n"
337 " 5: If(4)\n"
338 "BasicBlock 2, pred: 1, succ: 8\n"
339 " 6: Goto\n"
340 "BasicBlock 3, pred: 1, succ: 8\n"
341 " 7: Goto\n"
342 "BasicBlock 4, pred: 8, 5, succ: 6, 5\n"
343 " 8: Equal(13, 13) [9]\n"
344 " 9: If(8)\n"
345 "BasicBlock 5, pred: 4, succ: 4\n"
346 " 10: Goto\n"
347 "BasicBlock 6, pred: 4, succ: 7\n"
348 " 11: Return(13)\n"
349 "BasicBlock 7, pred: 6\n"
350 " 12: Exit\n"
351 "BasicBlock 8, pred: 2, 3, succ: 4\n"
352 " 13: Phi(2, 1) [11, 8, 8]\n"
353 " 14: Goto\n";
354
355 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
356 Instruction::CONST_4 | 0 | 0,
357 Instruction::IF_EQ, 4,
358 Instruction::CONST_4 | 4 << 12 | 0,
359 Instruction::GOTO | 0x200,
360 Instruction::CONST_4 | 5 << 12 | 0,
361 Instruction::IF_EQ, 3,
362 Instruction::GOTO | 0xFE00,
363 Instruction::RETURN | 0 << 8);
364
365 TestCode(data, expected);
366 }
367
TEST_F(SsaTest,Loop6)368 TEST_F(SsaTest, Loop6) {
369 // Test a loop with one preheader and two back edges (e.g. continue).
370 const char* expected =
371 "BasicBlock 0, succ: 1\n"
372 " 0: IntConstant 0 [5]\n"
373 " 1: IntConstant 4 [5, 8, 8]\n"
374 " 2: IntConstant 5 [5]\n"
375 " 3: Goto\n"
376 "BasicBlock 1, pred: 0, succ: 2\n"
377 " 4: Goto\n"
378 "BasicBlock 2, pred: 1, 4, 5, succ: 6, 3\n"
379 " 5: Phi(0, 2, 1) [12, 6, 6]\n"
380 " 6: Equal(5, 5) [7]\n"
381 " 7: If(6)\n"
382 "BasicBlock 3, pred: 2, succ: 5, 4\n"
383 " 8: Equal(1, 1) [9]\n"
384 " 9: If(8)\n"
385 "BasicBlock 4, pred: 3, succ: 2\n"
386 " 10: Goto\n"
387 "BasicBlock 5, pred: 3, succ: 2\n"
388 " 11: Goto\n"
389 "BasicBlock 6, pred: 2, succ: 7\n"
390 " 12: Return(5)\n"
391 "BasicBlock 7, pred: 6\n"
392 " 13: Exit\n";
393
394 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
395 Instruction::CONST_4 | 0 | 0,
396 Instruction::IF_EQ, 8,
397 Instruction::CONST_4 | 4 << 12 | 0,
398 Instruction::IF_EQ, 4,
399 Instruction::CONST_4 | 5 << 12 | 0,
400 Instruction::GOTO | 0xFA00,
401 Instruction::GOTO | 0xF900,
402 Instruction::RETURN | 0 << 8);
403
404 TestCode(data, expected);
405 }
406
TEST_F(SsaTest,Loop7)407 TEST_F(SsaTest, Loop7) {
408 // Test a loop with one preheader, one back edge, and two exit edges (e.g. break).
409 const char* expected =
410 "BasicBlock 0, succ: 1\n"
411 " 0: IntConstant 0 [5]\n"
412 " 1: IntConstant 4 [5, 8, 8]\n"
413 " 2: IntConstant 5 [12]\n"
414 " 3: Goto\n"
415 "BasicBlock 1, pred: 0, succ: 2\n"
416 " 4: Goto\n"
417 "BasicBlock 2, pred: 1, 5, succ: 8, 3\n"
418 " 5: Phi(0, 1) [12, 6, 6]\n"
419 " 6: Equal(5, 5) [7]\n"
420 " 7: If(6)\n"
421 "BasicBlock 3, pred: 2, succ: 5, 4\n"
422 " 8: Equal(1, 1) [9]\n"
423 " 9: If(8)\n"
424 "BasicBlock 4, pred: 3, succ: 6\n"
425 " 10: Goto\n"
426 "BasicBlock 5, pred: 3, succ: 2\n"
427 " 11: Goto\n"
428 "BasicBlock 6, pred: 8, 4, succ: 7\n"
429 " 12: Phi(5, 2) [13]\n"
430 " 13: Return(12)\n"
431 "BasicBlock 7, pred: 6\n"
432 " 14: Exit\n"
433 "BasicBlock 8, pred: 2, succ: 6\n"
434 " 15: Goto\n";
435
436 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
437 Instruction::CONST_4 | 0 | 0,
438 Instruction::IF_EQ, 8,
439 Instruction::CONST_4 | 4 << 12 | 0,
440 Instruction::IF_EQ, 4,
441 Instruction::CONST_4 | 5 << 12 | 0,
442 Instruction::GOTO | 0x0200,
443 Instruction::GOTO | 0xF900,
444 Instruction::RETURN | 0 << 8);
445
446 TestCode(data, expected);
447 }
448
TEST_F(SsaTest,DeadLocal)449 TEST_F(SsaTest, DeadLocal) {
450 // Test that we correctly handle a local not being used.
451 const char* expected =
452 "BasicBlock 0, succ: 1\n"
453 " 0: IntConstant 0\n"
454 " 1: Goto\n"
455 "BasicBlock 1, pred: 0, succ: 2\n"
456 " 2: ReturnVoid\n"
457 "BasicBlock 2, pred: 1\n"
458 " 3: Exit\n";
459
460 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
461 Instruction::CONST_4 | 0 | 0,
462 Instruction::RETURN_VOID);
463
464 TestCode(data, expected);
465 }
466
TEST_F(SsaTest,LocalInIf)467 TEST_F(SsaTest, LocalInIf) {
468 // Test that we do not create a phi in the join block when one predecessor
469 // does not update the local.
470 const char* expected =
471 "BasicBlock 0, succ: 1\n"
472 " 0: IntConstant 0 [3, 3]\n"
473 " 1: IntConstant 4\n"
474 " 2: Goto\n"
475 "BasicBlock 1, pred: 0, succ: 5, 2\n"
476 " 3: Equal(0, 0) [4]\n"
477 " 4: If(3)\n"
478 "BasicBlock 2, pred: 1, succ: 3\n"
479 " 5: Goto\n"
480 "BasicBlock 3, pred: 5, 2, succ: 4\n"
481 " 6: ReturnVoid\n"
482 "BasicBlock 4, pred: 3\n"
483 " 7: Exit\n"
484 // Synthesized block to avoid critical edge.
485 "BasicBlock 5, pred: 1, succ: 3\n"
486 " 8: Goto\n";
487
488 const std::vector<uint16_t> data = TWO_REGISTERS_CODE_ITEM(
489 Instruction::CONST_4 | 0 | 0,
490 Instruction::IF_EQ, 3,
491 Instruction::CONST_4 | 4 << 12 | 1 << 8,
492 Instruction::RETURN_VOID);
493
494 TestCode(data, expected);
495 }
496
TEST_F(SsaTest,MultiplePredecessors)497 TEST_F(SsaTest, MultiplePredecessors) {
498 // Test that we do not create a phi when one predecessor
499 // does not update the local.
500 const char* expected =
501 "BasicBlock 0, succ: 1\n"
502 " 0: IntConstant 0 [4, 4, 8, 8, 6, 6, 2, 2]\n"
503 " 1: Goto\n"
504 "BasicBlock 1, pred: 0, succ: 3, 2\n"
505 " 2: Equal(0, 0) [3]\n"
506 " 3: If(2)\n"
507 "BasicBlock 2, pred: 1, succ: 5\n"
508 " 4: Add(0, 0)\n"
509 " 5: Goto\n"
510 "BasicBlock 3, pred: 1, succ: 7, 4\n"
511 " 6: Equal(0, 0) [7]\n"
512 " 7: If(6)\n"
513 "BasicBlock 4, pred: 3, succ: 5\n"
514 " 8: Add(0, 0)\n"
515 " 9: Goto\n"
516 // This block should not get a phi for local 1.
517 "BasicBlock 5, pred: 2, 7, 4, succ: 6\n"
518 " 10: ReturnVoid\n"
519 "BasicBlock 6, pred: 5\n"
520 " 11: Exit\n"
521 "BasicBlock 7, pred: 3, succ: 5\n"
522 " 12: Goto\n";
523
524 const std::vector<uint16_t> data = TWO_REGISTERS_CODE_ITEM(
525 Instruction::CONST_4 | 0 | 0,
526 Instruction::IF_EQ, 5,
527 Instruction::ADD_INT_LIT8 | 1 << 8, 0 << 8,
528 Instruction::GOTO | 0x0500,
529 Instruction::IF_EQ, 4,
530 Instruction::ADD_INT_LIT8 | 1 << 8, 0 << 8,
531 Instruction::RETURN_VOID);
532
533 TestCode(data, expected);
534 }
535
536 } // namespace art
537