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