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/stringprintf.h"
18 #include "builder.h"
19 #include "dex_file.h"
20 #include "dex_instruction.h"
21 #include "nodes.h"
22 #include "optimizing_unit_test.h"
23 #include "pretty_printer.h"
24 #include "ssa_builder.h"
25 #include "utils/arena_allocator.h"
26
27 #include "gtest/gtest.h"
28
29 namespace art {
30
31 class SsaPrettyPrinter : public HPrettyPrinter {
32 public:
SsaPrettyPrinter(HGraph * graph)33 explicit SsaPrettyPrinter(HGraph* graph) : HPrettyPrinter(graph), str_("") {}
34
PrintInt(int value)35 virtual void PrintInt(int value) {
36 str_ += StringPrintf("%d", value);
37 }
38
PrintString(const char * value)39 virtual void PrintString(const char* value) {
40 str_ += value;
41 }
42
PrintNewLine()43 virtual void PrintNewLine() {
44 str_ += '\n';
45 }
46
Clear()47 void Clear() { str_.clear(); }
48
str() const49 std::string str() const { return str_; }
50
VisitIntConstant(HIntConstant * constant)51 virtual void VisitIntConstant(HIntConstant* constant) {
52 PrintPreInstruction(constant);
53 str_ += constant->DebugName();
54 str_ += " ";
55 PrintInt(constant->GetValue());
56 PrintPostInstruction(constant);
57 }
58
59 private:
60 std::string str_;
61
62 DISALLOW_COPY_AND_ASSIGN(SsaPrettyPrinter);
63 };
64
ReNumberInstructions(HGraph * graph)65 static void ReNumberInstructions(HGraph* graph) {
66 int id = 0;
67 for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
68 HBasicBlock* block = graph->GetBlocks().Get(i);
69 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
70 it.Current()->SetId(id++);
71 }
72 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
73 it.Current()->SetId(id++);
74 }
75 }
76 }
77
TestCode(const uint16_t * data,const char * expected)78 static void TestCode(const uint16_t* data, const char* expected) {
79 ArenaPool pool;
80 ArenaAllocator allocator(&pool);
81 HGraphBuilder builder(&allocator);
82 const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
83 HGraph* graph = builder.BuildGraph(*item);
84 ASSERT_NE(graph, nullptr);
85
86 graph->BuildDominatorTree();
87 graph->TransformToSSA();
88 ReNumberInstructions(graph);
89
90 // Test that phis had their type set.
91 for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) {
92 for (HInstructionIterator it(graph->GetBlocks().Get(i)->GetPhis()); !it.Done(); it.Advance()) {
93 ASSERT_NE(it.Current()->GetType(), Primitive::kPrimVoid);
94 }
95 }
96
97 SsaPrettyPrinter printer(graph);
98 printer.VisitInsertionOrder();
99
100 ASSERT_STREQ(expected, printer.str().c_str());
101 }
102
TEST(SsaTest,CFG1)103 TEST(SsaTest, CFG1) {
104 // Test that we get rid of loads and stores.
105 const char* expected =
106 "BasicBlock 0, succ: 1\n"
107 " 0: IntConstant 0 [2, 2]\n"
108 " 1: Goto\n"
109 "BasicBlock 1, pred: 0, succ: 5, 2\n"
110 " 2: Equal(0, 0) [3]\n"
111 " 3: If(2)\n"
112 "BasicBlock 2, pred: 1, succ: 3\n"
113 " 4: Goto\n"
114 "BasicBlock 3, pred: 2, 5, succ: 4\n"
115 " 5: ReturnVoid\n"
116 "BasicBlock 4, pred: 3\n"
117 " 6: Exit\n"
118 // Synthesized block to avoid critical edge.
119 "BasicBlock 5, pred: 1, succ: 3\n"
120 " 7: Goto\n";
121
122 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
123 Instruction::CONST_4 | 0 | 0,
124 Instruction::IF_EQ, 3,
125 Instruction::GOTO | 0x100,
126 Instruction::RETURN_VOID);
127
128 TestCode(data, expected);
129 }
130
TEST(SsaTest,CFG2)131 TEST(SsaTest, CFG2) {
132 // Test that we create a phi for the join block of an if control flow instruction
133 // when there is only code in the else branch.
134 const char* expected =
135 "BasicBlock 0, succ: 1\n"
136 " 0: IntConstant 0 [6, 3, 3]\n"
137 " 1: IntConstant 4 [6]\n"
138 " 2: Goto\n"
139 "BasicBlock 1, pred: 0, succ: 5, 2\n"
140 " 3: Equal(0, 0) [4]\n"
141 " 4: If(3)\n"
142 "BasicBlock 2, pred: 1, succ: 3\n"
143 " 5: Goto\n"
144 "BasicBlock 3, pred: 2, 5, succ: 4\n"
145 " 6: Phi(1, 0) [7]\n"
146 " 7: Return(6)\n"
147 "BasicBlock 4, pred: 3\n"
148 " 8: Exit\n"
149 // Synthesized block to avoid critical edge.
150 "BasicBlock 5, pred: 1, succ: 3\n"
151 " 9: Goto\n";
152
153 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
154 Instruction::CONST_4 | 0 | 0,
155 Instruction::IF_EQ, 3,
156 Instruction::CONST_4 | 4 << 12 | 0,
157 Instruction::RETURN | 0 << 8);
158
159 TestCode(data, expected);
160 }
161
TEST(SsaTest,CFG3)162 TEST(SsaTest, CFG3) {
163 // Test that we create a phi for the join block of an if control flow instruction
164 // when both branches update a local.
165 const char* expected =
166 "BasicBlock 0, succ: 1\n"
167 " 0: IntConstant 0 [4, 4]\n"
168 " 1: IntConstant 4 [8]\n"
169 " 2: IntConstant 5 [8]\n"
170 " 3: Goto\n"
171 "BasicBlock 1, pred: 0, succ: 3, 2\n"
172 " 4: Equal(0, 0) [5]\n"
173 " 5: If(4)\n"
174 "BasicBlock 2, pred: 1, succ: 4\n"
175 " 6: Goto\n"
176 "BasicBlock 3, pred: 1, succ: 4\n"
177 " 7: Goto\n"
178 "BasicBlock 4, pred: 2, 3, succ: 5\n"
179 " 8: Phi(1, 2) [9]\n"
180 " 9: Return(8)\n"
181 "BasicBlock 5, pred: 4\n"
182 " 10: Exit\n";
183
184 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
185 Instruction::CONST_4 | 0 | 0,
186 Instruction::IF_EQ, 4,
187 Instruction::CONST_4 | 4 << 12 | 0,
188 Instruction::GOTO | 0x200,
189 Instruction::CONST_4 | 5 << 12 | 0,
190 Instruction::RETURN | 0 << 8);
191
192 TestCode(data, expected);
193 }
194
TEST(SsaTest,Loop1)195 TEST(SsaTest, Loop1) {
196 // Test that we create a phi for an initialized local at entry of a loop.
197 const char* expected =
198 "BasicBlock 0, succ: 1\n"
199 " 0: IntConstant 0 [6, 4, 2, 2]\n"
200 " 1: Goto\n"
201 "BasicBlock 1, pred: 0, succ: 5, 6\n"
202 " 2: Equal(0, 0) [3]\n"
203 " 3: If(2)\n"
204 "BasicBlock 2, pred: 3, 6, succ: 3\n"
205 " 4: Phi(6, 0) [6]\n"
206 " 5: Goto\n"
207 "BasicBlock 3, pred: 2, 5, succ: 2\n"
208 " 6: Phi(4, 0) [4]\n"
209 " 7: Goto\n"
210 "BasicBlock 4\n"
211 // Synthesized blocks to avoid critical edge.
212 "BasicBlock 5, pred: 1, succ: 3\n"
213 " 8: Goto\n"
214 "BasicBlock 6, pred: 1, succ: 2\n"
215 " 9: Goto\n";
216
217 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
218 Instruction::CONST_4 | 0 | 0,
219 Instruction::IF_EQ, 3,
220 Instruction::GOTO | 0x100,
221 Instruction::GOTO | 0xFF00);
222
223 TestCode(data, expected);
224 }
225
TEST(SsaTest,Loop2)226 TEST(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(SsaTest,Loop3)256 TEST(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 4 [5]\n"
262 " 2: IntConstant 5 [9]\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, 1) [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(2)\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(SsaTest,Loop4)288 TEST(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: 3, 4, succ: 5, 3\n"
299 " 4: Phi(1, 0) [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(SsaTest,Loop5)323 TEST(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 4 [14]\n"
330 " 2: IntConstant 5 [14]\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: 5, 8, succ: 6, 5\n"
340 " 8: Phi(8, 14) [8, 12, 9, 9]\n"
341 " 9: Equal(8, 8) [10]\n"
342 " 10: If(9)\n"
343 "BasicBlock 5, pred: 4, succ: 4\n"
344 " 11: Goto\n"
345 "BasicBlock 6, pred: 4, succ: 7\n"
346 " 12: Return(8)\n"
347 "BasicBlock 7, pred: 6\n"
348 " 13: Exit\n"
349 "BasicBlock 8, pred: 2, 3, succ: 4\n"
350 " 14: Phi(1, 2) [8]\n"
351 " 15: 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(SsaTest,Loop6)366 TEST(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 [14, 8, 8]\n"
372 " 2: IntConstant 5 [14]\n"
373 " 3: Goto\n"
374 "BasicBlock 1, pred: 0, succ: 2\n"
375 " 4: Goto\n"
376 "BasicBlock 2, pred: 1, 8, succ: 6, 3\n"
377 " 5: Phi(0, 14) [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: 8\n"
384 " 10: Goto\n"
385 "BasicBlock 5, pred: 3, succ: 8\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 // Synthesized single back edge of loop.
392 "BasicBlock 8, pred: 5, 4, succ: 2\n"
393 " 14: Phi(1, 2) [5]\n"
394 " 15: Goto\n";
395
396 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
397 Instruction::CONST_4 | 0 | 0,
398 Instruction::IF_EQ, 8,
399 Instruction::CONST_4 | 4 << 12 | 0,
400 Instruction::IF_EQ, 4,
401 Instruction::CONST_4 | 5 << 12 | 0,
402 Instruction::GOTO | 0xFA00,
403 Instruction::GOTO | 0xF900,
404 Instruction::RETURN | 0 << 8);
405
406 TestCode(data, expected);
407 }
408
TEST(SsaTest,Loop7)409 TEST(SsaTest, Loop7) {
410 // Test a loop with one preheader, one back edge, and two exit edges (e.g. break).
411 const char* expected =
412 "BasicBlock 0, succ: 1\n"
413 " 0: IntConstant 0 [5]\n"
414 " 1: IntConstant 4 [5, 8, 8]\n"
415 " 2: IntConstant 5 [12]\n"
416 " 3: Goto\n"
417 "BasicBlock 1, pred: 0, succ: 2\n"
418 " 4: Goto\n"
419 "BasicBlock 2, pred: 1, 5, succ: 8, 3\n"
420 " 5: Phi(0, 1) [12, 6, 6]\n"
421 " 6: Equal(5, 5) [7]\n"
422 " 7: If(6)\n"
423 "BasicBlock 3, pred: 2, succ: 5, 4\n"
424 " 8: Equal(1, 1) [9]\n"
425 " 9: If(8)\n"
426 "BasicBlock 4, pred: 3, succ: 6\n"
427 " 10: Goto\n"
428 "BasicBlock 5, pred: 3, succ: 2\n"
429 " 11: Goto\n"
430 "BasicBlock 6, pred: 4, 8, succ: 7\n"
431 " 12: Phi(2, 5) [13]\n"
432 " 13: Return(12)\n"
433 "BasicBlock 7, pred: 6\n"
434 " 14: Exit\n"
435 "BasicBlock 8, pred: 2, succ: 6\n"
436 " 15: Goto\n";
437
438 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
439 Instruction::CONST_4 | 0 | 0,
440 Instruction::IF_EQ, 8,
441 Instruction::CONST_4 | 4 << 12 | 0,
442 Instruction::IF_EQ, 4,
443 Instruction::CONST_4 | 5 << 12 | 0,
444 Instruction::GOTO | 0x0200,
445 Instruction::GOTO | 0xF900,
446 Instruction::RETURN | 0 << 8);
447
448 TestCode(data, expected);
449 }
450
TEST(SsaTest,DeadLocal)451 TEST(SsaTest, DeadLocal) {
452 // Test that we correctly handle a local not being used.
453 const char* expected =
454 "BasicBlock 0, succ: 1\n"
455 " 0: IntConstant 0\n"
456 " 1: Goto\n"
457 "BasicBlock 1, pred: 0, succ: 2\n"
458 " 2: ReturnVoid\n"
459 "BasicBlock 2, pred: 1\n"
460 " 3: Exit\n";
461
462 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
463 Instruction::CONST_4 | 0 | 0,
464 Instruction::RETURN_VOID);
465
466 TestCode(data, expected);
467 }
468
TEST(SsaTest,LocalInIf)469 TEST(SsaTest, LocalInIf) {
470 // Test that we do not create a phi in the join block when one predecessor
471 // does not update the local.
472 const char* expected =
473 "BasicBlock 0, succ: 1\n"
474 " 0: IntConstant 0 [3, 3]\n"
475 " 1: IntConstant 4\n"
476 " 2: Goto\n"
477 "BasicBlock 1, pred: 0, succ: 5, 2\n"
478 " 3: Equal(0, 0) [4]\n"
479 " 4: If(3)\n"
480 "BasicBlock 2, pred: 1, succ: 3\n"
481 " 5: Goto\n"
482 "BasicBlock 3, pred: 2, 5, succ: 4\n"
483 " 6: ReturnVoid\n"
484 "BasicBlock 4, pred: 3\n"
485 " 7: Exit\n"
486 // Synthesized block to avoid critical edge.
487 "BasicBlock 5, pred: 1, succ: 3\n"
488 " 8: Goto\n";
489
490 const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
491 Instruction::CONST_4 | 0 | 0,
492 Instruction::IF_EQ, 3,
493 Instruction::CONST_4 | 4 << 12 | 1 << 8,
494 Instruction::RETURN_VOID);
495
496 TestCode(data, expected);
497 }
498
TEST(SsaTest,MultiplePredecessors)499 TEST(SsaTest, MultiplePredecessors) {
500 // Test that we do not create a phi when one predecessor
501 // does not update the local.
502 const char* expected =
503 "BasicBlock 0, succ: 1\n"
504 " 0: IntConstant 0 [4, 8, 6, 6, 2, 2, 8, 4]\n"
505 " 1: Goto\n"
506 "BasicBlock 1, pred: 0, succ: 3, 2\n"
507 " 2: Equal(0, 0) [3]\n"
508 " 3: If(2)\n"
509 "BasicBlock 2, pred: 1, succ: 5\n"
510 " 4: Add(0, 0)\n"
511 " 5: Goto\n"
512 "BasicBlock 3, pred: 1, succ: 7, 4\n"
513 " 6: Equal(0, 0) [7]\n"
514 " 7: If(6)\n"
515 "BasicBlock 4, pred: 3, succ: 5\n"
516 " 8: Add(0, 0)\n"
517 " 9: Goto\n"
518 // This block should not get a phi for local 1.
519 "BasicBlock 5, pred: 2, 4, 7, succ: 6\n"
520 " 10: ReturnVoid\n"
521 "BasicBlock 6, pred: 5\n"
522 " 11: Exit\n"
523 "BasicBlock 7, pred: 3, succ: 5\n"
524 " 12: Goto\n";
525
526 const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
527 Instruction::CONST_4 | 0 | 0,
528 Instruction::IF_EQ, 5,
529 Instruction::ADD_INT_LIT8 | 1 << 8, 0 << 8,
530 Instruction::GOTO | 0x0500,
531 Instruction::IF_EQ, 4,
532 Instruction::ADD_INT_LIT8 | 1 << 8, 0 << 8,
533 Instruction::RETURN_VOID);
534
535 TestCode(data, expected);
536 }
537
538 } // namespace art
539