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 <fstream>
18
19#include "arch/x86/instruction_set_features_x86.h"
20#include "base/arena_allocator.h"
21#include "base/stringprintf.h"
22#include "builder.h"
23#include "code_generator.h"
24#include "code_generator_x86.h"
25#include "dex_file.h"
26#include "dex_instruction.h"
27#include "driver/compiler_options.h"
28#include "graph_visualizer.h"
29#include "nodes.h"
30#include "optimizing_unit_test.h"
31#include "pretty_printer.h"
32#include "ssa_liveness_analysis.h"
33
34namespace art {
35
36class LinearizeTest : public CommonCompilerTest {};
37
38template <size_t number_of_blocks>
39static void TestCode(const uint16_t* data, const uint32_t (&expected_order)[number_of_blocks]) {
40  ArenaPool pool;
41  ArenaAllocator allocator(&pool);
42  HGraph* graph = CreateCFG(&allocator, data);
43  std::unique_ptr<const X86InstructionSetFeatures> features_x86(
44      X86InstructionSetFeatures::FromCppDefines());
45  x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
46  SsaLivenessAnalysis liveness(graph, &codegen);
47  liveness.Analyze();
48
49  ASSERT_EQ(graph->GetLinearOrder().size(), number_of_blocks);
50  for (size_t i = 0; i < number_of_blocks; ++i) {
51    ASSERT_EQ(graph->GetLinearOrder()[i]->GetBlockId(), expected_order[i]);
52  }
53}
54
55TEST_F(LinearizeTest, CFG1) {
56  // Structure of this graph (+ are back edges)
57  //            Block0
58  //              |
59  //            Block1
60  //              |
61  //            Block2 ++++++
62  //            /   \       +
63  //       Block5   Block7  +
64  //         |        |     +
65  //       Block6   Block3  +
66  //               + /   \  +
67  //           Block4   Block8
68
69  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
70    Instruction::CONST_4 | 0 | 0,
71    Instruction::IF_EQ, 5,
72    Instruction::IF_EQ, 0xFFFE,
73    Instruction::GOTO | 0xFE00,
74    Instruction::RETURN_VOID);
75
76  const uint32_t blocks[] = {0, 1, 2, 7, 3, 4, 8, 5, 6};
77  TestCode(data, blocks);
78}
79
80TEST_F(LinearizeTest, CFG2) {
81  // Structure of this graph (+ are back edges)
82  //            Block0
83  //              |
84  //            Block1
85  //              |
86  //            Block2 ++++++
87  //            /   \       +
88  //       Block3   Block7  +
89  //         |        |     +
90  //       Block6   Block4  +
91  //               + /   \  +
92  //           Block5   Block8
93
94  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
95    Instruction::CONST_4 | 0 | 0,
96    Instruction::IF_EQ, 3,
97    Instruction::RETURN_VOID,
98    Instruction::IF_EQ, 0xFFFD,
99    Instruction::GOTO | 0xFE00);
100
101  const uint32_t blocks[] = {0, 1, 2, 7, 4, 5, 8, 3, 6};
102  TestCode(data, blocks);
103}
104
105TEST_F(LinearizeTest, CFG3) {
106  // Structure of this graph (+ are back edges)
107  //            Block0
108  //              |
109  //            Block1
110  //              |
111  //            Block2 ++++++
112  //            /   \       +
113  //       Block3   Block8  +
114  //         |        |     +
115  //       Block7   Block5  +
116  //                 / +  \ +
117  //           Block6  + Block9
118  //             |     +
119  //           Block4 ++
120  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
121    Instruction::CONST_4 | 0 | 0,
122    Instruction::IF_EQ, 4,
123    Instruction::RETURN_VOID,
124    Instruction::GOTO | 0x0100,
125    Instruction::IF_EQ, 0xFFFC,
126    Instruction::GOTO | 0xFD00);
127
128  const uint32_t blocks[] = {0, 1, 2, 8, 5, 6, 4, 9, 3, 7};
129  TestCode(data, blocks);
130}
131
132TEST_F(LinearizeTest, CFG4) {
133  /* Structure of this graph (+ are back edges)
134  //            Block0
135  //              |
136  //            Block1
137  //              |
138  //            Block2
139  //            / +  \
140  //       Block6 + Block8
141  //         |    +   |
142  //       Block7 + Block3 +++++++
143  //              +  /  \        +
144  //           Block9   Block10  +
145  //                      |      +
146  //                    Block4   +
147  //                  + /    \   +
148  //                Block5  Block11
149  */
150  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
151    Instruction::CONST_4 | 0 | 0,
152    Instruction::IF_EQ, 7,
153    Instruction::IF_EQ, 0xFFFE,
154    Instruction::IF_EQ, 0xFFFE,
155    Instruction::GOTO | 0xFE00,
156    Instruction::RETURN_VOID);
157
158  const uint32_t blocks[] = {0, 1, 2, 8, 3, 10, 4, 5, 11, 9, 6, 7};
159  TestCode(data, blocks);
160}
161
162TEST_F(LinearizeTest, CFG5) {
163  /* Structure of this graph (+ are back edges)
164  //            Block0
165  //              |
166  //            Block1
167  //              |
168  //            Block2
169  //            / +  \
170  //       Block3 + Block8
171  //         |    +   |
172  //       Block7 + Block4 +++++++
173  //              +  /  \        +
174  //           Block9   Block10  +
175  //                      |      +
176  //                    Block5   +
177  //                   +/    \   +
178  //                Block6  Block11
179  */
180  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
181    Instruction::CONST_4 | 0 | 0,
182    Instruction::IF_EQ, 3,
183    Instruction::RETURN_VOID,
184    Instruction::IF_EQ, 0xFFFD,
185    Instruction::IF_EQ, 0xFFFE,
186    Instruction::GOTO | 0xFE00);
187
188  const uint32_t blocks[] = {0, 1, 2, 8, 4, 10, 5, 6, 11, 9, 3, 7};
189  TestCode(data, blocks);
190}
191
192TEST_F(LinearizeTest, CFG6) {
193  //            Block0
194  //              |
195  //            Block1
196  //              |
197  //            Block2 ++++++++++++++
198  //              |                 +
199  //            Block3              +
200  //            /     \             +
201  //       Block8     Block4        +
202  //         |         /   \        +
203  //       Block5 <- Block9 Block6  +
204  //         |
205  //       Block7
206  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
207    Instruction::CONST_4 | 0 | 0,
208    Instruction::GOTO | 0x0100,
209    Instruction::IF_EQ, 0x0004,
210    Instruction::IF_EQ, 0x0003,
211    Instruction::RETURN_VOID,
212    Instruction::GOTO | 0xFA00);
213
214  const uint32_t blocks[] = {0, 1, 2, 3, 4, 6, 9, 8, 5, 7};
215  TestCode(data, blocks);
216}
217
218TEST_F(LinearizeTest, CFG7) {
219  // Structure of this graph (+ are back edges)
220  //            Block0
221  //              |
222  //            Block1
223  //              |
224  //            Block2 ++++++++
225  //              |           +
226  //            Block3        +
227  //            /    \        +
228  //        Block4  Block8    +
229  //        /  \        |     +
230  //   Block5 Block9 - Block6 +
231  //     |
232  //   Block7
233  //
234  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
235    Instruction::CONST_4 | 0 | 0,
236    Instruction::GOTO | 0x0100,
237    Instruction::IF_EQ, 0x0005,
238    Instruction::IF_EQ, 0x0003,
239    Instruction::RETURN_VOID,
240    Instruction::GOTO | 0xFA00);
241
242  const uint32_t blocks[] = {0, 1, 2, 3, 4, 9, 8, 6, 5, 7};
243  TestCode(data, blocks);
244}
245
246}  // namespace art
247