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 "builder.h"
18 #include "code_generator.h"
19 #include "dex_file.h"
20 #include "dex_instruction.h"
21 #include "nodes.h"
22 #include "optimizing_unit_test.h"
23 #include "ssa_liveness_analysis.h"
24 #include "utils/arena_allocator.h"
25
26 #include "gtest/gtest.h"
27
28 namespace art {
29
BuildGraph(const uint16_t * data,ArenaAllocator * allocator)30 static HGraph* BuildGraph(const uint16_t* data, ArenaAllocator* allocator) {
31 HGraphBuilder builder(allocator);
32 const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
33 HGraph* graph = builder.BuildGraph(*item);
34 graph->BuildDominatorTree();
35 graph->TransformToSSA();
36 graph->FindNaturalLoops();
37 return graph;
38 }
39
TEST(LiveRangesTest,CFG1)40 TEST(LiveRangesTest, CFG1) {
41 /*
42 * Test the following snippet:
43 * return 0;
44 *
45 * Which becomes the following graph (numbered by lifetime position):
46 * 2: constant0
47 * 4: goto
48 * |
49 * 8: return
50 * |
51 * 12: exit
52 */
53 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
54 Instruction::CONST_4 | 0 | 0,
55 Instruction::RETURN);
56
57 ArenaPool pool;
58 ArenaAllocator allocator(&pool);
59 HGraph* graph = BuildGraph(data, &allocator);
60
61 CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, InstructionSet::kX86);
62 SsaLivenessAnalysis liveness(*graph, codegen);
63 liveness.Analyze();
64
65 LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
66 LiveRange* range = interval->GetFirstRange();
67 ASSERT_EQ(2u, range->GetStart());
68 // Last use is the return instruction.
69 ASSERT_EQ(9u, range->GetEnd());
70 HBasicBlock* block = graph->GetBlocks().Get(1);
71 ASSERT_TRUE(block->GetLastInstruction()->AsReturn() != nullptr);
72 ASSERT_EQ(8u, block->GetLastInstruction()->GetLifetimePosition());
73 ASSERT_TRUE(range->GetNext() == nullptr);
74 }
75
TEST(LiveRangesTest,CFG2)76 TEST(LiveRangesTest, CFG2) {
77 /*
78 * Test the following snippet:
79 * var a = 0;
80 * if (0 == 0) {
81 * } else {
82 * }
83 * return a;
84 *
85 * Which becomes the following graph (numbered by lifetime position):
86 * 2: constant0
87 * 4: goto
88 * |
89 * 8: equal
90 * 10: if
91 * / \
92 * 14: goto 18: goto
93 * \ /
94 * 22: return
95 * |
96 * 26: exit
97 */
98 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
99 Instruction::CONST_4 | 0 | 0,
100 Instruction::IF_EQ, 3,
101 Instruction::GOTO | 0x100,
102 Instruction::RETURN | 0 << 8);
103
104 ArenaPool pool;
105 ArenaAllocator allocator(&pool);
106 HGraph* graph = BuildGraph(data, &allocator);
107 CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, InstructionSet::kX86);
108 SsaLivenessAnalysis liveness(*graph, codegen);
109 liveness.Analyze();
110
111 LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
112 LiveRange* range = interval->GetFirstRange();
113 ASSERT_EQ(2u, range->GetStart());
114 // Last use is the return instruction.
115 ASSERT_EQ(23u, range->GetEnd());
116 HBasicBlock* block = graph->GetBlocks().Get(3);
117 ASSERT_TRUE(block->GetLastInstruction()->AsReturn() != nullptr);
118 ASSERT_EQ(22u, block->GetLastInstruction()->GetLifetimePosition());
119 ASSERT_TRUE(range->GetNext() == nullptr);
120 }
121
TEST(LiveRangesTest,CFG3)122 TEST(LiveRangesTest, CFG3) {
123 /*
124 * Test the following snippet:
125 * var a = 0;
126 * if (0 == 0) {
127 * } else {
128 * a = 4;
129 * }
130 * return a;
131 *
132 * Which becomes the following graph (numbered by lifetime position):
133 * 2: constant0
134 * 4: constant4
135 * 6: goto
136 * |
137 * 10: equal
138 * 12: if
139 * / \
140 * 16: goto 20: goto
141 * \ /
142 * 22: phi
143 * 24: return
144 * |
145 * 38: exit
146 */
147 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
148 Instruction::CONST_4 | 0 | 0,
149 Instruction::IF_EQ, 3,
150 Instruction::CONST_4 | 4 << 12 | 0,
151 Instruction::RETURN | 0 << 8);
152
153 ArenaPool pool;
154 ArenaAllocator allocator(&pool);
155 HGraph* graph = BuildGraph(data, &allocator);
156 CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, InstructionSet::kX86);
157 SsaLivenessAnalysis liveness(*graph, codegen);
158 liveness.Analyze();
159
160 // Test for the 4 constant.
161 LiveInterval* interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval();
162 LiveRange* range = interval->GetFirstRange();
163 ASSERT_EQ(4u, range->GetStart());
164 // Last use is the phi at the return block so instruction is live until
165 // the end of the then block.
166 ASSERT_EQ(18u, range->GetEnd());
167 ASSERT_TRUE(range->GetNext() == nullptr);
168
169 // Test for the 0 constant.
170 interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
171 // The then branch is a hole for this constant, therefore its interval has 2 ranges.
172 // First range starts from the definition and ends at the if block.
173 range = interval->GetFirstRange();
174 ASSERT_EQ(2u, range->GetStart());
175 // 14 is the end of the if block.
176 ASSERT_EQ(14u, range->GetEnd());
177 // Second range is the else block.
178 range = range->GetNext();
179 ASSERT_EQ(18u, range->GetStart());
180 // Last use is the phi at the return block.
181 ASSERT_EQ(22u, range->GetEnd());
182 ASSERT_TRUE(range->GetNext() == nullptr);
183
184 // Test for the phi.
185 interval = liveness.GetInstructionFromSsaIndex(2)->GetLiveInterval();
186 range = interval->GetFirstRange();
187 ASSERT_EQ(22u, liveness.GetInstructionFromSsaIndex(2)->GetLifetimePosition());
188 ASSERT_EQ(22u, range->GetStart());
189 ASSERT_EQ(25u, range->GetEnd());
190 ASSERT_TRUE(range->GetNext() == nullptr);
191 }
192
TEST(LiveRangesTest,Loop)193 TEST(LiveRangesTest, Loop) {
194 /*
195 * Test the following snippet:
196 * var a = 0;
197 * while (a == a) {
198 * a = 4;
199 * }
200 * return 5;
201 *
202 * Which becomes the following graph (numbered by lifetime position):
203 * 2: constant0
204 * 4: constant4
205 * 6: constant5
206 * 8: goto
207 * |
208 * 12: goto
209 * |
210 * 14: phi
211 * 16: equal
212 * 18: if +++++
213 * | \ +
214 * | 22: goto
215 * |
216 * 26: return
217 * |
218 * 30: exit
219 */
220
221 const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
222 Instruction::CONST_4 | 0 | 0,
223 Instruction::IF_EQ, 4,
224 Instruction::CONST_4 | 4 << 12 | 0,
225 Instruction::GOTO | 0xFD00,
226 Instruction::CONST_4 | 5 << 12 | 1 << 8,
227 Instruction::RETURN | 1 << 8);
228
229 ArenaPool pool;
230 ArenaAllocator allocator(&pool);
231 HGraph* graph = BuildGraph(data, &allocator);
232 CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, InstructionSet::kX86);
233 SsaLivenessAnalysis liveness(*graph, codegen);
234 liveness.Analyze();
235
236 // Test for the 0 constant.
237 LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
238 LiveRange* range = interval->GetFirstRange();
239 ASSERT_EQ(2u, range->GetStart());
240 // Last use is the loop phi so instruction is live until
241 // the end of the pre loop header.
242 ASSERT_EQ(14u, range->GetEnd());
243 ASSERT_TRUE(range->GetNext() == nullptr);
244
245 // Test for the 4 constant.
246 interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval();
247 range = interval->GetFirstRange();
248 // The instruction is live until the end of the loop.
249 ASSERT_EQ(4u, range->GetStart());
250 ASSERT_EQ(24u, range->GetEnd());
251 ASSERT_TRUE(range->GetNext() == nullptr);
252
253 // Test for the 5 constant.
254 interval = liveness.GetInstructionFromSsaIndex(2)->GetLiveInterval();
255 range = interval->GetFirstRange();
256 // The instruction is live until the return instruction after the loop.
257 ASSERT_EQ(6u, range->GetStart());
258 ASSERT_EQ(27u, range->GetEnd());
259 ASSERT_TRUE(range->GetNext() == nullptr);
260
261 // Test for the phi.
262 interval = liveness.GetInstructionFromSsaIndex(3)->GetLiveInterval();
263 range = interval->GetFirstRange();
264 // Instruction is consumed by the if.
265 ASSERT_EQ(14u, range->GetStart());
266 ASSERT_EQ(17u, range->GetEnd());
267 ASSERT_TRUE(range->GetNext() == nullptr);
268 }
269
270 } // namespace art
271