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 SsaTest : public CommonCompilerTest {};
32
33class SsaPrettyPrinter : public HPrettyPrinter {
34 public:
35  explicit SsaPrettyPrinter(HGraph* graph) : HPrettyPrinter(graph), str_("") {}
36
37  void PrintInt(int value) OVERRIDE {
38    str_ += StringPrintf("%d", value);
39  }
40
41  void PrintString(const char* value) OVERRIDE {
42    str_ += value;
43  }
44
45  void PrintNewLine() OVERRIDE {
46    str_ += '\n';
47  }
48
49  void Clear() { str_.clear(); }
50
51  std::string str() const { return str_; }
52
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
67static 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
79static 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
101TEST_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
129TEST_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
160TEST_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
193TEST_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
226TEST_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
256TEST_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
288TEST_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
323TEST_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
365TEST_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
404TEST_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
446TEST_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
464TEST_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
494TEST_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