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