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