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