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