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