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