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