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