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