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 "builder.h"
19 #include "code_generator.h"
20 #include "dex/dex_file.h"
21 #include "dex/dex_instruction.h"
22 #include "driver/compiler_options.h"
23 #include "nodes.h"
24 #include "optimizing_unit_test.h"
25 #include "prepare_for_register_allocation.h"
26 #include "ssa_liveness_analysis.h"
27
28 namespace art {
29
30 class LiveRangesTest : public OptimizingUnitTest {
31 public:
32 HGraph* BuildGraph(const std::vector<uint16_t>& data);
33 };
34
BuildGraph(const std::vector<uint16_t> & data)35 HGraph* LiveRangesTest::BuildGraph(const std::vector<uint16_t>& data) {
36 HGraph* graph = CreateCFG(data);
37 // Suspend checks implementation may change in the future, and this test relies
38 // on how instructions are ordered.
39 RemoveSuspendChecks(graph);
40 // `Inline` conditions into ifs.
41 PrepareForRegisterAllocation(graph, *compiler_options_).Run();
42 return graph;
43 }
44
TEST_F(LiveRangesTest,CFG1)45 TEST_F(LiveRangesTest, CFG1) {
46 /*
47 * Test the following snippet:
48 * return 0;
49 *
50 * Which becomes the following graph (numbered by lifetime position):
51 * 2: constant0
52 * 4: goto
53 * |
54 * 8: return
55 * |
56 * 12: exit
57 */
58 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
59 Instruction::CONST_4 | 0 | 0,
60 Instruction::RETURN);
61
62 HGraph* graph = BuildGraph(data);
63
64 std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options_);
65 SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator());
66 liveness.Analyze();
67
68 LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
69 LiveRange* range = interval->GetFirstRange();
70 ASSERT_EQ(2u, range->GetStart());
71 // Last use is the return instruction.
72 ASSERT_EQ(8u, range->GetEnd());
73 HBasicBlock* block = graph->GetBlocks()[1];
74 ASSERT_TRUE(block->GetLastInstruction()->IsReturn());
75 ASSERT_EQ(8u, block->GetLastInstruction()->GetLifetimePosition());
76 ASSERT_TRUE(range->GetNext() == nullptr);
77 }
78
TEST_F(LiveRangesTest,CFG2)79 TEST_F(LiveRangesTest, CFG2) {
80 /*
81 * Test the following snippet:
82 * var a = 0;
83 * if (0 == 0) {
84 * } else {
85 * }
86 * return a;
87 *
88 * Which becomes the following graph (numbered by lifetime position):
89 * 2: constant0
90 * 4: goto
91 * |
92 * 8: equal
93 * 10: if
94 * / \
95 * 14: goto 18: goto
96 * \ /
97 * 22: return
98 * |
99 * 26: exit
100 */
101 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
102 Instruction::CONST_4 | 0 | 0,
103 Instruction::IF_EQ, 3,
104 Instruction::GOTO | 0x100,
105 Instruction::RETURN | 0 << 8);
106
107 HGraph* graph = BuildGraph(data);
108 std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options_);
109 SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator());
110 liveness.Analyze();
111
112 LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
113 LiveRange* range = interval->GetFirstRange();
114 ASSERT_EQ(2u, range->GetStart());
115 // Last use is the return instruction.
116 ASSERT_EQ(22u, range->GetEnd());
117 HBasicBlock* block = graph->GetBlocks()[3];
118 ASSERT_TRUE(block->GetLastInstruction()->IsReturn());
119 ASSERT_EQ(22u, block->GetLastInstruction()->GetLifetimePosition());
120 ASSERT_TRUE(range->GetNext() == nullptr);
121 }
122
TEST_F(LiveRangesTest,CFG3)123 TEST_F(LiveRangesTest, CFG3) {
124 /*
125 * Test the following snippet:
126 * var a = 0;
127 * if (0 == 0) {
128 * } else {
129 * a = 4;
130 * }
131 * return a;
132 *
133 * Which becomes the following graph (numbered by lifetime position):
134 * 2: constant0
135 * 4: constant4
136 * 6: goto
137 * |
138 * 10: equal
139 * 12: if
140 * / \
141 * 16: goto 20: goto
142 * \ /
143 * 22: phi
144 * 24: return
145 * |
146 * 28: exit
147 */
148 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
149 Instruction::CONST_4 | 0 | 0,
150 Instruction::IF_EQ, 3,
151 Instruction::CONST_4 | 4 << 12 | 0,
152 Instruction::RETURN | 0 << 8);
153
154 HGraph* graph = BuildGraph(data);
155 std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options_);
156 SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator());
157 liveness.Analyze();
158
159 // Test for the 4 constant.
160 LiveInterval* interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval();
161 LiveRange* range = interval->GetFirstRange();
162 ASSERT_EQ(4u, range->GetStart());
163 // Last use is the phi at the return block so instruction is live until
164 // the end of the then block.
165 ASSERT_EQ(18u, range->GetEnd());
166 ASSERT_TRUE(range->GetNext() == nullptr);
167
168 // Test for the 0 constant.
169 interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
170 // The then branch is a hole for this constant, therefore its interval has 2 ranges.
171 // First range starts from the definition and ends at the if block.
172 range = interval->GetFirstRange();
173 ASSERT_EQ(2u, range->GetStart());
174 // 14 is the end of the if block.
175 ASSERT_EQ(14u, range->GetEnd());
176 // Second range is the else block.
177 range = range->GetNext();
178 ASSERT_EQ(18u, range->GetStart());
179 // Last use is the phi at the return block.
180 ASSERT_EQ(22u, range->GetEnd());
181 ASSERT_TRUE(range->GetNext() == nullptr);
182
183 // Test for the phi.
184 interval = liveness.GetInstructionFromSsaIndex(2)->GetLiveInterval();
185 range = interval->GetFirstRange();
186 ASSERT_EQ(22u, liveness.GetInstructionFromSsaIndex(2)->GetLifetimePosition());
187 ASSERT_EQ(22u, range->GetStart());
188 ASSERT_EQ(24u, range->GetEnd());
189 ASSERT_TRUE(range->GetNext() == nullptr);
190 }
191
TEST_F(LiveRangesTest,Loop1)192 TEST_F(LiveRangesTest, Loop1) {
193 /*
194 * Test the following snippet:
195 * var a = 0;
196 * while (a == a) {
197 * a = 4;
198 * }
199 * return 5;
200 *
201 * Which becomes the following graph (numbered by lifetime position):
202 * 2: constant0
203 * 4: constant5
204 * 6: constant4
205 * 8: goto
206 * |
207 * 12: goto
208 * |
209 * 14: phi
210 * 16: equal
211 * 18: if +++++
212 * | \ +
213 * | 22: goto
214 * |
215 * 26: return
216 * |
217 * 30: exit
218 */
219
220 const std::vector<uint16_t> data = TWO_REGISTERS_CODE_ITEM(
221 Instruction::CONST_4 | 0 | 0,
222 Instruction::IF_EQ, 4,
223 Instruction::CONST_4 | 4 << 12 | 0,
224 Instruction::GOTO | 0xFD00,
225 Instruction::CONST_4 | 5 << 12 | 1 << 8,
226 Instruction::RETURN | 1 << 8);
227
228 HGraph* graph = BuildGraph(data);
229 RemoveSuspendChecks(graph);
230 std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options_);
231 SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator());
232 liveness.Analyze();
233
234 // Test for the 0 constant.
235 LiveInterval* interval = graph->GetIntConstant(0)->GetLiveInterval();
236 LiveRange* range = interval->GetFirstRange();
237 ASSERT_EQ(2u, range->GetStart());
238 // Last use is the loop phi so instruction is live until
239 // the end of the pre loop header.
240 ASSERT_EQ(14u, range->GetEnd());
241 ASSERT_TRUE(range->GetNext() == nullptr);
242
243 // Test for the 4 constant.
244 interval = graph->GetIntConstant(4)->GetLiveInterval();
245 range = interval->GetFirstRange();
246 // The instruction is live until the end of the loop.
247 ASSERT_EQ(6u, range->GetStart());
248 ASSERT_EQ(24u, range->GetEnd());
249 ASSERT_TRUE(range->GetNext() == nullptr);
250
251 // Test for the 5 constant.
252 interval = graph->GetIntConstant(5)->GetLiveInterval();
253 range = interval->GetFirstRange();
254 // The instruction is live until the return instruction after the loop.
255 ASSERT_EQ(4u, range->GetStart());
256 ASSERT_EQ(26u, range->GetEnd());
257 ASSERT_TRUE(range->GetNext() == nullptr);
258
259 // Test for the phi.
260 interval = liveness.GetInstructionFromSsaIndex(3)->GetLiveInterval();
261 range = interval->GetFirstRange();
262 // Instruction is input of non-materialized Equal and hence live until If.
263 ASSERT_EQ(14u, range->GetStart());
264 ASSERT_EQ(19u, range->GetEnd());
265 ASSERT_TRUE(range->GetNext() == nullptr);
266 }
267
TEST_F(LiveRangesTest,Loop2)268 TEST_F(LiveRangesTest, Loop2) {
269 /*
270 * Test the following snippet:
271 * var a = 0;
272 * while (a == a) {
273 * a = a + a;
274 * }
275 * return a;
276 *
277 * Which becomes the following graph (numbered by lifetime position):
278 * 2: constant0
279 * 4: goto
280 * |
281 * 8: goto
282 * |
283 * 10: phi
284 * 12: equal
285 * 14: if +++++
286 * | \ +
287 * | 18: add
288 * | 20: goto
289 * |
290 * 24: return
291 * |
292 * 28: exit
293 *
294 * We want to make sure the phi at 10 has a lifetime hole after the add at 20.
295 */
296
297 const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
298 Instruction::CONST_4 | 0 | 0,
299 Instruction::IF_EQ, 6,
300 Instruction::ADD_INT, 0, 0,
301 Instruction::GOTO | 0xFB00,
302 Instruction::RETURN | 0 << 8);
303
304 HGraph* graph = BuildGraph(data);
305 std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options_);
306 SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator());
307 liveness.Analyze();
308
309 // Test for the 0 constant.
310 HIntConstant* constant = liveness.GetInstructionFromSsaIndex(0)->AsIntConstant();
311 LiveInterval* interval = constant->GetLiveInterval();
312 LiveRange* range = interval->GetFirstRange();
313 ASSERT_EQ(2u, range->GetStart());
314 // Last use is the loop phi so instruction is live until
315 // the end of the pre loop header.
316 ASSERT_EQ(10u, range->GetEnd());
317 ASSERT_TRUE(range->GetNext() == nullptr);
318
319 // Test for the loop phi.
320 HPhi* phi = liveness.GetInstructionFromSsaIndex(1)->AsPhi();
321 interval = phi->GetLiveInterval();
322 range = interval->GetFirstRange();
323 ASSERT_EQ(10u, range->GetStart());
324 ASSERT_EQ(19u, range->GetEnd());
325 range = range->GetNext();
326 ASSERT_TRUE(range != nullptr);
327 ASSERT_EQ(22u, range->GetStart());
328 ASSERT_EQ(24u, range->GetEnd());
329
330 // Test for the add instruction.
331 HAdd* add = liveness.GetInstructionFromSsaIndex(2)->AsAdd();
332 interval = add->GetLiveInterval();
333 range = interval->GetFirstRange();
334 ASSERT_EQ(18u, range->GetStart());
335 ASSERT_EQ(22u, range->GetEnd());
336 ASSERT_TRUE(range->GetNext() == nullptr);
337 }
338
TEST_F(LiveRangesTest,CFG4)339 TEST_F(LiveRangesTest, CFG4) {
340 /*
341 * Test the following snippet:
342 * var a = 0;
343 * var b = 4;
344 * if (a == a) {
345 * a = b + a;
346 * } else {
347 * a = b + a
348 * }
349 * return b;
350 *
351 * Which becomes the following graph (numbered by lifetime position):
352 * 2: constant0
353 * 4: constant4
354 * 6: goto
355 * |
356 * 10: equal
357 * 12: if
358 * / \
359 * 16: add 22: add
360 * 18: goto 24: goto
361 * \ /
362 * 26: phi
363 * 28: return
364 * |
365 * 32: exit
366 *
367 * We want to make sure the constant0 has a lifetime hole after the 16: add.
368 */
369 const std::vector<uint16_t> data = TWO_REGISTERS_CODE_ITEM(
370 Instruction::CONST_4 | 0 | 0,
371 Instruction::CONST_4 | 4 << 12 | 1 << 8,
372 Instruction::IF_EQ, 5,
373 Instruction::ADD_INT, 1 << 8,
374 Instruction::GOTO | 0x300,
375 Instruction::ADD_INT, 1 << 8,
376 Instruction::RETURN);
377
378 HGraph* graph = BuildGraph(data);
379 std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options_);
380 SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator());
381 liveness.Analyze();
382
383 // Test for the 0 constant.
384 LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
385 LiveRange* range = interval->GetFirstRange();
386 ASSERT_EQ(2u, range->GetStart());
387 ASSERT_EQ(17u, range->GetEnd());
388 range = range->GetNext();
389 ASSERT_TRUE(range != nullptr);
390 ASSERT_EQ(20u, range->GetStart());
391 ASSERT_EQ(23u, range->GetEnd());
392 ASSERT_TRUE(range->GetNext() == nullptr);
393
394 // Test for the 4 constant.
395 interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval();
396 range = interval->GetFirstRange();
397 ASSERT_EQ(4u, range->GetStart());
398 ASSERT_EQ(17u, range->GetEnd());
399 range = range->GetNext();
400 ASSERT_EQ(20u, range->GetStart());
401 ASSERT_EQ(23u, range->GetEnd());
402 ASSERT_TRUE(range->GetNext() == nullptr);
403
404 // Test for the first add.
405 HAdd* add = liveness.GetInstructionFromSsaIndex(2)->AsAdd();
406 interval = add->GetLiveInterval();
407 range = interval->GetFirstRange();
408 ASSERT_EQ(16u, range->GetStart());
409 ASSERT_EQ(20u, range->GetEnd());
410 ASSERT_TRUE(range->GetNext() == nullptr);
411
412 // Test for the second add.
413 add = liveness.GetInstructionFromSsaIndex(3)->AsAdd();
414 interval = add->GetLiveInterval();
415 range = interval->GetFirstRange();
416 ASSERT_EQ(22u, range->GetStart());
417 ASSERT_EQ(26u, range->GetEnd());
418 ASSERT_TRUE(range->GetNext() == nullptr);
419
420 HPhi* phi = liveness.GetInstructionFromSsaIndex(4)->AsPhi();
421 ASSERT_TRUE(phi->GetUses().HasExactlyOneElement());
422 interval = phi->GetLiveInterval();
423 range = interval->GetFirstRange();
424 ASSERT_EQ(26u, range->GetStart());
425 ASSERT_EQ(28u, range->GetEnd());
426 ASSERT_TRUE(range->GetNext() == nullptr);
427 }
428
429 } // namespace art
430