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 "register_allocator.h"
28 #include "ssa_liveness_analysis.h"
29 #include "ssa_phi_elimination.h"
30
31 namespace art {
32
33 // Note: the register allocator tests rely on the fact that constants have live
34 // intervals and registers get allocated to them.
35
36 class RegisterAllocatorTest : public CommonCompilerTest {};
37
Check(const uint16_t * data)38 static bool Check(const uint16_t* data) {
39 ArenaPool pool;
40 ArenaAllocator allocator(&pool);
41 HGraph* graph = CreateCFG(&allocator, data);
42 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
43 X86InstructionSetFeatures::FromCppDefines());
44 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
45 SsaLivenessAnalysis liveness(graph, &codegen);
46 liveness.Analyze();
47 RegisterAllocator register_allocator(&allocator, &codegen, liveness);
48 register_allocator.AllocateRegisters();
49 return register_allocator.Validate(false);
50 }
51
52 /**
53 * Unit testing of RegisterAllocator::ValidateIntervals. Register allocator
54 * tests are based on this validation method.
55 */
TEST_F(RegisterAllocatorTest,ValidateIntervals)56 TEST_F(RegisterAllocatorTest, ValidateIntervals) {
57 ArenaPool pool;
58 ArenaAllocator allocator(&pool);
59 HGraph* graph = CreateGraph(&allocator);
60 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
61 X86InstructionSetFeatures::FromCppDefines());
62 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
63 ArenaVector<LiveInterval*> intervals(allocator.Adapter());
64
65 // Test with two intervals of the same range.
66 {
67 static constexpr size_t ranges[][2] = {{0, 42}};
68 intervals.push_back(BuildInterval(ranges, arraysize(ranges), &allocator, 0));
69 intervals.push_back(BuildInterval(ranges, arraysize(ranges), &allocator, 1));
70 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
71 intervals, 0, 0, codegen, &allocator, true, false));
72
73 intervals[1]->SetRegister(0);
74 ASSERT_FALSE(RegisterAllocator::ValidateIntervals(
75 intervals, 0, 0, codegen, &allocator, true, false));
76 intervals.clear();
77 }
78
79 // Test with two non-intersecting intervals.
80 {
81 static constexpr size_t ranges1[][2] = {{0, 42}};
82 intervals.push_back(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0));
83 static constexpr size_t ranges2[][2] = {{42, 43}};
84 intervals.push_back(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1));
85 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
86 intervals, 0, 0, codegen, &allocator, true, false));
87
88 intervals[1]->SetRegister(0);
89 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
90 intervals, 0, 0, codegen, &allocator, true, false));
91 intervals.clear();
92 }
93
94 // Test with two non-intersecting intervals, with one with a lifetime hole.
95 {
96 static constexpr size_t ranges1[][2] = {{0, 42}, {45, 48}};
97 intervals.push_back(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0));
98 static constexpr size_t ranges2[][2] = {{42, 43}};
99 intervals.push_back(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1));
100 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
101 intervals, 0, 0, codegen, &allocator, true, false));
102
103 intervals[1]->SetRegister(0);
104 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
105 intervals, 0, 0, codegen, &allocator, true, false));
106 intervals.clear();
107 }
108
109 // Test with intersecting intervals.
110 {
111 static constexpr size_t ranges1[][2] = {{0, 42}, {44, 48}};
112 intervals.push_back(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0));
113 static constexpr size_t ranges2[][2] = {{42, 47}};
114 intervals.push_back(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1));
115 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
116 intervals, 0, 0, codegen, &allocator, true, false));
117
118 intervals[1]->SetRegister(0);
119 ASSERT_FALSE(RegisterAllocator::ValidateIntervals(
120 intervals, 0, 0, codegen, &allocator, true, false));
121 intervals.clear();
122 }
123
124 // Test with siblings.
125 {
126 static constexpr size_t ranges1[][2] = {{0, 42}, {44, 48}};
127 intervals.push_back(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0));
128 intervals[0]->SplitAt(43);
129 static constexpr size_t ranges2[][2] = {{42, 47}};
130 intervals.push_back(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1));
131 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
132 intervals, 0, 0, codegen, &allocator, true, false));
133
134 intervals[1]->SetRegister(0);
135 // Sibling of the first interval has no register allocated to it.
136 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
137 intervals, 0, 0, codegen, &allocator, true, false));
138
139 intervals[0]->GetNextSibling()->SetRegister(0);
140 ASSERT_FALSE(RegisterAllocator::ValidateIntervals(
141 intervals, 0, 0, codegen, &allocator, true, false));
142 }
143 }
144
TEST_F(RegisterAllocatorTest,CFG1)145 TEST_F(RegisterAllocatorTest, CFG1) {
146 /*
147 * Test the following snippet:
148 * return 0;
149 *
150 * Which becomes the following graph:
151 * constant0
152 * goto
153 * |
154 * return
155 * |
156 * exit
157 */
158 const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
159 Instruction::CONST_4 | 0 | 0,
160 Instruction::RETURN);
161
162 ASSERT_TRUE(Check(data));
163 }
164
TEST_F(RegisterAllocatorTest,Loop1)165 TEST_F(RegisterAllocatorTest, Loop1) {
166 /*
167 * Test the following snippet:
168 * int a = 0;
169 * while (a == a) {
170 * a = 4;
171 * }
172 * return 5;
173 *
174 * Which becomes the following graph:
175 * constant0
176 * constant4
177 * constant5
178 * goto
179 * |
180 * goto
181 * |
182 * phi
183 * equal
184 * if +++++
185 * | \ +
186 * | goto
187 * |
188 * return
189 * |
190 * exit
191 */
192
193 const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
194 Instruction::CONST_4 | 0 | 0,
195 Instruction::IF_EQ, 4,
196 Instruction::CONST_4 | 4 << 12 | 0,
197 Instruction::GOTO | 0xFD00,
198 Instruction::CONST_4 | 5 << 12 | 1 << 8,
199 Instruction::RETURN | 1 << 8);
200
201 ASSERT_TRUE(Check(data));
202 }
203
TEST_F(RegisterAllocatorTest,Loop2)204 TEST_F(RegisterAllocatorTest, Loop2) {
205 /*
206 * Test the following snippet:
207 * int a = 0;
208 * while (a == 8) {
209 * a = 4 + 5;
210 * }
211 * return 6 + 7;
212 *
213 * Which becomes the following graph:
214 * constant0
215 * constant4
216 * constant5
217 * constant6
218 * constant7
219 * constant8
220 * goto
221 * |
222 * goto
223 * |
224 * phi
225 * equal
226 * if +++++
227 * | \ +
228 * | 4 + 5
229 * | goto
230 * |
231 * 6 + 7
232 * return
233 * |
234 * exit
235 */
236
237 const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
238 Instruction::CONST_4 | 0 | 0,
239 Instruction::CONST_4 | 8 << 12 | 1 << 8,
240 Instruction::IF_EQ | 1 << 8, 7,
241 Instruction::CONST_4 | 4 << 12 | 0 << 8,
242 Instruction::CONST_4 | 5 << 12 | 1 << 8,
243 Instruction::ADD_INT, 1 << 8 | 0,
244 Instruction::GOTO | 0xFA00,
245 Instruction::CONST_4 | 6 << 12 | 1 << 8,
246 Instruction::CONST_4 | 7 << 12 | 1 << 8,
247 Instruction::ADD_INT, 1 << 8 | 0,
248 Instruction::RETURN | 1 << 8);
249
250 ASSERT_TRUE(Check(data));
251 }
252
TEST_F(RegisterAllocatorTest,Loop3)253 TEST_F(RegisterAllocatorTest, Loop3) {
254 /*
255 * Test the following snippet:
256 * int a = 0
257 * do {
258 * b = a;
259 * a++;
260 * } while (a != 5)
261 * return b;
262 *
263 * Which becomes the following graph:
264 * constant0
265 * constant1
266 * constant5
267 * goto
268 * |
269 * goto
270 * |++++++++++++
271 * phi +
272 * a++ +
273 * equals +
274 * if +
275 * |++++++++++++
276 * return
277 * |
278 * exit
279 */
280
281 const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
282 Instruction::CONST_4 | 0 | 0,
283 Instruction::ADD_INT_LIT8 | 1 << 8, 1 << 8,
284 Instruction::CONST_4 | 5 << 12 | 2 << 8,
285 Instruction::IF_NE | 1 << 8 | 2 << 12, 3,
286 Instruction::RETURN | 0 << 8,
287 Instruction::MOVE | 1 << 12 | 0 << 8,
288 Instruction::GOTO | 0xF900);
289
290 ArenaPool pool;
291 ArenaAllocator allocator(&pool);
292 HGraph* graph = CreateCFG(&allocator, data);
293 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
294 X86InstructionSetFeatures::FromCppDefines());
295 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
296 SsaLivenessAnalysis liveness(graph, &codegen);
297 liveness.Analyze();
298 RegisterAllocator register_allocator(&allocator, &codegen, liveness);
299 register_allocator.AllocateRegisters();
300 ASSERT_TRUE(register_allocator.Validate(false));
301
302 HBasicBlock* loop_header = graph->GetBlocks()[2];
303 HPhi* phi = loop_header->GetFirstPhi()->AsPhi();
304
305 LiveInterval* phi_interval = phi->GetLiveInterval();
306 LiveInterval* loop_update = phi->InputAt(1)->GetLiveInterval();
307 ASSERT_TRUE(phi_interval->HasRegister());
308 ASSERT_TRUE(loop_update->HasRegister());
309 ASSERT_NE(phi_interval->GetRegister(), loop_update->GetRegister());
310
311 HBasicBlock* return_block = graph->GetBlocks()[3];
312 HReturn* ret = return_block->GetLastInstruction()->AsReturn();
313 ASSERT_EQ(phi_interval->GetRegister(), ret->InputAt(0)->GetLiveInterval()->GetRegister());
314 }
315
TEST_F(RegisterAllocatorTest,FirstRegisterUse)316 TEST_F(RegisterAllocatorTest, FirstRegisterUse) {
317 const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
318 Instruction::CONST_4 | 0 | 0,
319 Instruction::XOR_INT_LIT8 | 1 << 8, 1 << 8,
320 Instruction::XOR_INT_LIT8 | 0 << 8, 1 << 8,
321 Instruction::XOR_INT_LIT8 | 1 << 8, 1 << 8 | 1,
322 Instruction::RETURN_VOID);
323
324 ArenaPool pool;
325 ArenaAllocator allocator(&pool);
326 HGraph* graph = CreateCFG(&allocator, data);
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 HXor* first_xor = graph->GetBlocks()[1]->GetFirstInstruction()->AsXor();
334 HXor* last_xor = graph->GetBlocks()[1]->GetLastInstruction()->GetPrevious()->AsXor();
335 ASSERT_EQ(last_xor->InputAt(0), first_xor);
336 LiveInterval* interval = first_xor->GetLiveInterval();
337 ASSERT_EQ(interval->GetEnd(), last_xor->GetLifetimePosition());
338 ASSERT_TRUE(interval->GetNextSibling() == nullptr);
339
340 // We need a register for the output of the instruction.
341 ASSERT_EQ(interval->FirstRegisterUse(), first_xor->GetLifetimePosition());
342
343 // Split at the next instruction.
344 interval = interval->SplitAt(first_xor->GetLifetimePosition() + 2);
345 // The user of the split is the last add.
346 ASSERT_EQ(interval->FirstRegisterUse(), last_xor->GetLifetimePosition());
347
348 // Split before the last add.
349 LiveInterval* new_interval = interval->SplitAt(last_xor->GetLifetimePosition() - 1);
350 // Ensure the current interval has no register use...
351 ASSERT_EQ(interval->FirstRegisterUse(), kNoLifetime);
352 // And the new interval has it for the last add.
353 ASSERT_EQ(new_interval->FirstRegisterUse(), last_xor->GetLifetimePosition());
354 }
355
TEST_F(RegisterAllocatorTest,DeadPhi)356 TEST_F(RegisterAllocatorTest, DeadPhi) {
357 /* Test for a dead loop phi taking as back-edge input a phi that also has
358 * this loop phi as input. Walking backwards in SsaDeadPhiElimination
359 * does not solve the problem because the loop phi will be visited last.
360 *
361 * Test the following snippet:
362 * int a = 0
363 * do {
364 * if (true) {
365 * a = 2;
366 * }
367 * } while (true);
368 */
369
370 const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
371 Instruction::CONST_4 | 0 | 0,
372 Instruction::CONST_4 | 1 << 8 | 0,
373 Instruction::IF_NE | 1 << 8 | 1 << 12, 3,
374 Instruction::CONST_4 | 2 << 12 | 0 << 8,
375 Instruction::GOTO | 0xFD00,
376 Instruction::RETURN_VOID);
377
378 ArenaPool pool;
379 ArenaAllocator allocator(&pool);
380 HGraph* graph = CreateCFG(&allocator, data);
381 SsaDeadPhiElimination(graph).Run();
382 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
383 X86InstructionSetFeatures::FromCppDefines());
384 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
385 SsaLivenessAnalysis liveness(graph, &codegen);
386 liveness.Analyze();
387 RegisterAllocator register_allocator(&allocator, &codegen, liveness);
388 register_allocator.AllocateRegisters();
389 ASSERT_TRUE(register_allocator.Validate(false));
390 }
391
392 /**
393 * Test that the TryAllocateFreeReg method works in the presence of inactive intervals
394 * that share the same register. It should split the interval it is currently
395 * allocating for at the minimum lifetime position between the two inactive intervals.
396 */
TEST_F(RegisterAllocatorTest,FreeUntil)397 TEST_F(RegisterAllocatorTest, FreeUntil) {
398 const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
399 Instruction::CONST_4 | 0 | 0,
400 Instruction::RETURN);
401
402 ArenaPool pool;
403 ArenaAllocator allocator(&pool);
404 HGraph* graph = CreateCFG(&allocator, data);
405 SsaDeadPhiElimination(graph).Run();
406 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
407 X86InstructionSetFeatures::FromCppDefines());
408 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
409 SsaLivenessAnalysis liveness(graph, &codegen);
410 liveness.Analyze();
411 RegisterAllocator register_allocator(&allocator, &codegen, liveness);
412
413 // Add an artifical range to cover the temps that will be put in the unhandled list.
414 LiveInterval* unhandled = graph->GetEntryBlock()->GetFirstInstruction()->GetLiveInterval();
415 unhandled->AddLoopRange(0, 60);
416
417 // Populate the instructions in the liveness object, to please the register allocator.
418 for (size_t i = 0; i < 60; ++i) {
419 liveness.instructions_from_lifetime_position_.push_back(
420 graph->GetEntryBlock()->GetFirstInstruction());
421 }
422
423 // For SSA value intervals, only an interval resulted from a split may intersect
424 // with inactive intervals.
425 unhandled = register_allocator.Split(unhandled, 5);
426
427 // Add three temps holding the same register, and starting at different positions.
428 // Put the one that should be picked in the middle of the inactive list to ensure
429 // we do not depend on an order.
430 LiveInterval* interval = LiveInterval::MakeFixedInterval(&allocator, 0, Primitive::kPrimInt);
431 interval->AddRange(40, 50);
432 register_allocator.inactive_.push_back(interval);
433
434 interval = LiveInterval::MakeFixedInterval(&allocator, 0, Primitive::kPrimInt);
435 interval->AddRange(20, 30);
436 register_allocator.inactive_.push_back(interval);
437
438 interval = LiveInterval::MakeFixedInterval(&allocator, 0, Primitive::kPrimInt);
439 interval->AddRange(60, 70);
440 register_allocator.inactive_.push_back(interval);
441
442 register_allocator.number_of_registers_ = 1;
443 register_allocator.registers_array_ = allocator.AllocArray<size_t>(1);
444 register_allocator.processing_core_registers_ = true;
445 register_allocator.unhandled_ = ®ister_allocator.unhandled_core_intervals_;
446
447 ASSERT_TRUE(register_allocator.TryAllocateFreeReg(unhandled));
448
449 // Check that we have split the interval.
450 ASSERT_EQ(1u, register_allocator.unhandled_->size());
451 // Check that we know need to find a new register where the next interval
452 // that uses the register starts.
453 ASSERT_EQ(20u, register_allocator.unhandled_->front()->GetStart());
454 }
455
BuildIfElseWithPhi(ArenaAllocator * allocator,HPhi ** phi,HInstruction ** input1,HInstruction ** input2)456 static HGraph* BuildIfElseWithPhi(ArenaAllocator* allocator,
457 HPhi** phi,
458 HInstruction** input1,
459 HInstruction** input2) {
460 HGraph* graph = CreateGraph(allocator);
461 HBasicBlock* entry = new (allocator) HBasicBlock(graph);
462 ScopedNullHandle<mirror::DexCache> dex_cache;
463 graph->AddBlock(entry);
464 graph->SetEntryBlock(entry);
465 HInstruction* parameter = new (allocator) HParameterValue(
466 graph->GetDexFile(), 0, 0, Primitive::kPrimNot);
467 entry->AddInstruction(parameter);
468
469 HBasicBlock* block = new (allocator) HBasicBlock(graph);
470 graph->AddBlock(block);
471 entry->AddSuccessor(block);
472
473 HInstruction* test = new (allocator) HInstanceFieldGet(parameter,
474 Primitive::kPrimBoolean,
475 MemberOffset(22),
476 false,
477 kUnknownFieldIndex,
478 kUnknownClassDefIndex,
479 graph->GetDexFile(),
480 dex_cache,
481 0);
482 block->AddInstruction(test);
483 block->AddInstruction(new (allocator) HIf(test));
484 HBasicBlock* then = new (allocator) HBasicBlock(graph);
485 HBasicBlock* else_ = new (allocator) HBasicBlock(graph);
486 HBasicBlock* join = new (allocator) HBasicBlock(graph);
487 graph->AddBlock(then);
488 graph->AddBlock(else_);
489 graph->AddBlock(join);
490
491 block->AddSuccessor(then);
492 block->AddSuccessor(else_);
493 then->AddSuccessor(join);
494 else_->AddSuccessor(join);
495 then->AddInstruction(new (allocator) HGoto());
496 else_->AddInstruction(new (allocator) HGoto());
497
498 *phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt);
499 join->AddPhi(*phi);
500 *input1 = new (allocator) HInstanceFieldGet(parameter,
501 Primitive::kPrimInt,
502 MemberOffset(42),
503 false,
504 kUnknownFieldIndex,
505 kUnknownClassDefIndex,
506 graph->GetDexFile(),
507 dex_cache,
508 0);
509 *input2 = new (allocator) HInstanceFieldGet(parameter,
510 Primitive::kPrimInt,
511 MemberOffset(42),
512 false,
513 kUnknownFieldIndex,
514 kUnknownClassDefIndex,
515 graph->GetDexFile(),
516 dex_cache,
517 0);
518 then->AddInstruction(*input1);
519 else_->AddInstruction(*input2);
520 join->AddInstruction(new (allocator) HExit());
521 (*phi)->AddInput(*input1);
522 (*phi)->AddInput(*input2);
523
524 graph->BuildDominatorTree();
525 graph->AnalyzeLoops();
526 return graph;
527 }
528
TEST_F(RegisterAllocatorTest,PhiHint)529 TEST_F(RegisterAllocatorTest, PhiHint) {
530 ArenaPool pool;
531 ArenaAllocator allocator(&pool);
532 HPhi *phi;
533 HInstruction *input1, *input2;
534
535 {
536 HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2);
537 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
538 X86InstructionSetFeatures::FromCppDefines());
539 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
540 SsaLivenessAnalysis liveness(graph, &codegen);
541 liveness.Analyze();
542
543 // Check that the register allocator is deterministic.
544 RegisterAllocator register_allocator(&allocator, &codegen, liveness);
545 register_allocator.AllocateRegisters();
546
547 ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 0);
548 ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 0);
549 ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 0);
550 }
551
552 {
553 HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2);
554 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
555 X86InstructionSetFeatures::FromCppDefines());
556 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
557 SsaLivenessAnalysis liveness(graph, &codegen);
558 liveness.Analyze();
559
560 // Set the phi to a specific register, and check that the inputs get allocated
561 // the same register.
562 phi->GetLocations()->UpdateOut(Location::RegisterLocation(2));
563 RegisterAllocator register_allocator(&allocator, &codegen, liveness);
564 register_allocator.AllocateRegisters();
565
566 ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2);
567 ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2);
568 ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2);
569 }
570
571 {
572 HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2);
573 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
574 X86InstructionSetFeatures::FromCppDefines());
575 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
576 SsaLivenessAnalysis liveness(graph, &codegen);
577 liveness.Analyze();
578
579 // Set input1 to a specific register, and check that the phi and other input get allocated
580 // the same register.
581 input1->GetLocations()->UpdateOut(Location::RegisterLocation(2));
582 RegisterAllocator register_allocator(&allocator, &codegen, liveness);
583 register_allocator.AllocateRegisters();
584
585 ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2);
586 ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2);
587 ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2);
588 }
589
590 {
591 HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2);
592 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
593 X86InstructionSetFeatures::FromCppDefines());
594 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
595 SsaLivenessAnalysis liveness(graph, &codegen);
596 liveness.Analyze();
597
598 // Set input2 to a specific register, and check that the phi and other input get allocated
599 // the same register.
600 input2->GetLocations()->UpdateOut(Location::RegisterLocation(2));
601 RegisterAllocator register_allocator(&allocator, &codegen, liveness);
602 register_allocator.AllocateRegisters();
603
604 ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2);
605 ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2);
606 ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2);
607 }
608 }
609
BuildFieldReturn(ArenaAllocator * allocator,HInstruction ** field,HInstruction ** ret)610 static HGraph* BuildFieldReturn(ArenaAllocator* allocator,
611 HInstruction** field,
612 HInstruction** ret) {
613 HGraph* graph = CreateGraph(allocator);
614 ScopedNullHandle<mirror::DexCache> dex_cache;
615 HBasicBlock* entry = new (allocator) HBasicBlock(graph);
616 graph->AddBlock(entry);
617 graph->SetEntryBlock(entry);
618 HInstruction* parameter = new (allocator) HParameterValue(
619 graph->GetDexFile(), 0, 0, Primitive::kPrimNot);
620 entry->AddInstruction(parameter);
621
622 HBasicBlock* block = new (allocator) HBasicBlock(graph);
623 graph->AddBlock(block);
624 entry->AddSuccessor(block);
625
626 *field = new (allocator) HInstanceFieldGet(parameter,
627 Primitive::kPrimInt,
628 MemberOffset(42),
629 false,
630 kUnknownFieldIndex,
631 kUnknownClassDefIndex,
632 graph->GetDexFile(),
633 dex_cache,
634 0);
635 block->AddInstruction(*field);
636 *ret = new (allocator) HReturn(*field);
637 block->AddInstruction(*ret);
638
639 HBasicBlock* exit = new (allocator) HBasicBlock(graph);
640 graph->AddBlock(exit);
641 block->AddSuccessor(exit);
642 exit->AddInstruction(new (allocator) HExit());
643
644 graph->BuildDominatorTree();
645 return graph;
646 }
647
TEST_F(RegisterAllocatorTest,ExpectedInRegisterHint)648 TEST_F(RegisterAllocatorTest, ExpectedInRegisterHint) {
649 ArenaPool pool;
650 ArenaAllocator allocator(&pool);
651 HInstruction *field, *ret;
652
653 {
654 HGraph* graph = BuildFieldReturn(&allocator, &field, &ret);
655 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
656 X86InstructionSetFeatures::FromCppDefines());
657 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
658 SsaLivenessAnalysis liveness(graph, &codegen);
659 liveness.Analyze();
660
661 RegisterAllocator register_allocator(&allocator, &codegen, liveness);
662 register_allocator.AllocateRegisters();
663
664 // Sanity check that in normal conditions, the register should be hinted to 0 (EAX).
665 ASSERT_EQ(field->GetLiveInterval()->GetRegister(), 0);
666 }
667
668 {
669 HGraph* graph = BuildFieldReturn(&allocator, &field, &ret);
670 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
671 X86InstructionSetFeatures::FromCppDefines());
672 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
673 SsaLivenessAnalysis liveness(graph, &codegen);
674 liveness.Analyze();
675
676 // Check that the field gets put in the register expected by its use.
677 // Don't use SetInAt because we are overriding an already allocated location.
678 ret->GetLocations()->inputs_[0] = Location::RegisterLocation(2);
679
680 RegisterAllocator register_allocator(&allocator, &codegen, liveness);
681 register_allocator.AllocateRegisters();
682
683 ASSERT_EQ(field->GetLiveInterval()->GetRegister(), 2);
684 }
685 }
686
BuildTwoSubs(ArenaAllocator * allocator,HInstruction ** first_sub,HInstruction ** second_sub)687 static HGraph* BuildTwoSubs(ArenaAllocator* allocator,
688 HInstruction** first_sub,
689 HInstruction** second_sub) {
690 HGraph* graph = CreateGraph(allocator);
691 HBasicBlock* entry = new (allocator) HBasicBlock(graph);
692 graph->AddBlock(entry);
693 graph->SetEntryBlock(entry);
694 HInstruction* parameter = new (allocator) HParameterValue(
695 graph->GetDexFile(), 0, 0, Primitive::kPrimInt);
696 entry->AddInstruction(parameter);
697
698 HInstruction* constant1 = graph->GetIntConstant(1);
699 HInstruction* constant2 = graph->GetIntConstant(2);
700
701 HBasicBlock* block = new (allocator) HBasicBlock(graph);
702 graph->AddBlock(block);
703 entry->AddSuccessor(block);
704
705 *first_sub = new (allocator) HSub(Primitive::kPrimInt, parameter, constant1);
706 block->AddInstruction(*first_sub);
707 *second_sub = new (allocator) HSub(Primitive::kPrimInt, *first_sub, constant2);
708 block->AddInstruction(*second_sub);
709
710 block->AddInstruction(new (allocator) HExit());
711
712 graph->BuildDominatorTree();
713 return graph;
714 }
715
TEST_F(RegisterAllocatorTest,SameAsFirstInputHint)716 TEST_F(RegisterAllocatorTest, SameAsFirstInputHint) {
717 ArenaPool pool;
718 ArenaAllocator allocator(&pool);
719 HInstruction *first_sub, *second_sub;
720
721 {
722 HGraph* graph = BuildTwoSubs(&allocator, &first_sub, &second_sub);
723 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
724 X86InstructionSetFeatures::FromCppDefines());
725 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
726 SsaLivenessAnalysis liveness(graph, &codegen);
727 liveness.Analyze();
728
729 RegisterAllocator register_allocator(&allocator, &codegen, liveness);
730 register_allocator.AllocateRegisters();
731
732 // Sanity check that in normal conditions, the registers are the same.
733 ASSERT_EQ(first_sub->GetLiveInterval()->GetRegister(), 1);
734 ASSERT_EQ(second_sub->GetLiveInterval()->GetRegister(), 1);
735 }
736
737 {
738 HGraph* graph = BuildTwoSubs(&allocator, &first_sub, &second_sub);
739 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
740 X86InstructionSetFeatures::FromCppDefines());
741 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
742 SsaLivenessAnalysis liveness(graph, &codegen);
743 liveness.Analyze();
744
745 // check that both adds get the same register.
746 // Don't use UpdateOutput because output is already allocated.
747 first_sub->InputAt(0)->GetLocations()->output_ = Location::RegisterLocation(2);
748 ASSERT_EQ(first_sub->GetLocations()->Out().GetPolicy(), Location::kSameAsFirstInput);
749 ASSERT_EQ(second_sub->GetLocations()->Out().GetPolicy(), Location::kSameAsFirstInput);
750
751 RegisterAllocator register_allocator(&allocator, &codegen, liveness);
752 register_allocator.AllocateRegisters();
753
754 ASSERT_EQ(first_sub->GetLiveInterval()->GetRegister(), 2);
755 ASSERT_EQ(second_sub->GetLiveInterval()->GetRegister(), 2);
756 }
757 }
758
BuildDiv(ArenaAllocator * allocator,HInstruction ** div)759 static HGraph* BuildDiv(ArenaAllocator* allocator,
760 HInstruction** div) {
761 HGraph* graph = CreateGraph(allocator);
762 HBasicBlock* entry = new (allocator) HBasicBlock(graph);
763 graph->AddBlock(entry);
764 graph->SetEntryBlock(entry);
765 HInstruction* first = new (allocator) HParameterValue(
766 graph->GetDexFile(), 0, 0, Primitive::kPrimInt);
767 HInstruction* second = new (allocator) HParameterValue(
768 graph->GetDexFile(), 0, 0, Primitive::kPrimInt);
769 entry->AddInstruction(first);
770 entry->AddInstruction(second);
771
772 HBasicBlock* block = new (allocator) HBasicBlock(graph);
773 graph->AddBlock(block);
774 entry->AddSuccessor(block);
775
776 *div = new (allocator) HDiv(Primitive::kPrimInt, first, second, 0); // don't care about dex_pc.
777 block->AddInstruction(*div);
778
779 block->AddInstruction(new (allocator) HExit());
780
781 graph->BuildDominatorTree();
782 return graph;
783 }
784
TEST_F(RegisterAllocatorTest,ExpectedExactInRegisterAndSameOutputHint)785 TEST_F(RegisterAllocatorTest, ExpectedExactInRegisterAndSameOutputHint) {
786 ArenaPool pool;
787 ArenaAllocator allocator(&pool);
788 HInstruction *div;
789
790 {
791 HGraph* graph = BuildDiv(&allocator, &div);
792 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
793 X86InstructionSetFeatures::FromCppDefines());
794 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
795 SsaLivenessAnalysis liveness(graph, &codegen);
796 liveness.Analyze();
797
798 RegisterAllocator register_allocator(&allocator, &codegen, liveness);
799 register_allocator.AllocateRegisters();
800
801 // div on x86 requires its first input in eax and the output be the same as the first input.
802 ASSERT_EQ(div->GetLiveInterval()->GetRegister(), 0);
803 }
804 }
805
806 // Test a bug in the register allocator, where allocating a blocked
807 // register would lead to spilling an inactive interval at the wrong
808 // position.
TEST_F(RegisterAllocatorTest,SpillInactive)809 TEST_F(RegisterAllocatorTest, SpillInactive) {
810 ArenaPool pool;
811
812 // Create a synthesized graph to please the register_allocator and
813 // ssa_liveness_analysis code.
814 ArenaAllocator allocator(&pool);
815 HGraph* graph = CreateGraph(&allocator);
816 HBasicBlock* entry = new (&allocator) HBasicBlock(graph);
817 graph->AddBlock(entry);
818 graph->SetEntryBlock(entry);
819 HInstruction* one = new (&allocator) HParameterValue(
820 graph->GetDexFile(), 0, 0, Primitive::kPrimInt);
821 HInstruction* two = new (&allocator) HParameterValue(
822 graph->GetDexFile(), 0, 0, Primitive::kPrimInt);
823 HInstruction* three = new (&allocator) HParameterValue(
824 graph->GetDexFile(), 0, 0, Primitive::kPrimInt);
825 HInstruction* four = new (&allocator) HParameterValue(
826 graph->GetDexFile(), 0, 0, Primitive::kPrimInt);
827 entry->AddInstruction(one);
828 entry->AddInstruction(two);
829 entry->AddInstruction(three);
830 entry->AddInstruction(four);
831
832 HBasicBlock* block = new (&allocator) HBasicBlock(graph);
833 graph->AddBlock(block);
834 entry->AddSuccessor(block);
835 block->AddInstruction(new (&allocator) HExit());
836
837 // We create a synthesized user requesting a register, to avoid just spilling the
838 // intervals.
839 HPhi* user = new (&allocator) HPhi(&allocator, 0, 1, Primitive::kPrimInt);
840 user->AddInput(one);
841 user->SetBlock(block);
842 LocationSummary* locations = new (&allocator) LocationSummary(user, LocationSummary::kNoCall);
843 locations->SetInAt(0, Location::RequiresRegister());
844 static constexpr size_t phi_ranges[][2] = {{20, 30}};
845 BuildInterval(phi_ranges, arraysize(phi_ranges), &allocator, -1, user);
846
847 // Create an interval with lifetime holes.
848 static constexpr size_t ranges1[][2] = {{0, 2}, {4, 6}, {8, 10}};
849 LiveInterval* first = BuildInterval(ranges1, arraysize(ranges1), &allocator, -1, one);
850 first->first_use_ = new(&allocator) UsePosition(user, 0, false, 8, first->first_use_);
851 first->first_use_ = new(&allocator) UsePosition(user, 0, false, 7, first->first_use_);
852 first->first_use_ = new(&allocator) UsePosition(user, 0, false, 6, first->first_use_);
853
854 locations = new (&allocator) LocationSummary(first->GetDefinedBy(), LocationSummary::kNoCall);
855 locations->SetOut(Location::RequiresRegister());
856 first = first->SplitAt(1);
857
858 // Create an interval that conflicts with the next interval, to force the next
859 // interval to call `AllocateBlockedReg`.
860 static constexpr size_t ranges2[][2] = {{2, 4}};
861 LiveInterval* second = BuildInterval(ranges2, arraysize(ranges2), &allocator, -1, two);
862 locations = new (&allocator) LocationSummary(second->GetDefinedBy(), LocationSummary::kNoCall);
863 locations->SetOut(Location::RequiresRegister());
864
865 // Create an interval that will lead to splitting the first interval. The bug occured
866 // by splitting at a wrong position, in this case at the next intersection between
867 // this interval and the first interval. We would have then put the interval with ranges
868 // "[0, 2(, [4, 6(" in the list of handled intervals, even though we haven't processed intervals
869 // before lifetime position 6 yet.
870 static constexpr size_t ranges3[][2] = {{2, 4}, {8, 10}};
871 LiveInterval* third = BuildInterval(ranges3, arraysize(ranges3), &allocator, -1, three);
872 third->first_use_ = new(&allocator) UsePosition(user, 0, false, 8, third->first_use_);
873 third->first_use_ = new(&allocator) UsePosition(user, 0, false, 4, third->first_use_);
874 third->first_use_ = new(&allocator) UsePosition(user, 0, false, 3, third->first_use_);
875 locations = new (&allocator) LocationSummary(third->GetDefinedBy(), LocationSummary::kNoCall);
876 locations->SetOut(Location::RequiresRegister());
877 third = third->SplitAt(3);
878
879 // Because the first part of the split interval was considered handled, this interval
880 // was free to allocate the same register, even though it conflicts with it.
881 static constexpr size_t ranges4[][2] = {{4, 6}};
882 LiveInterval* fourth = BuildInterval(ranges4, arraysize(ranges4), &allocator, -1, four);
883 locations = new (&allocator) LocationSummary(fourth->GetDefinedBy(), LocationSummary::kNoCall);
884 locations->SetOut(Location::RequiresRegister());
885
886 std::unique_ptr<const X86InstructionSetFeatures> features_x86(
887 X86InstructionSetFeatures::FromCppDefines());
888 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions());
889 SsaLivenessAnalysis liveness(graph, &codegen);
890 // Populate the instructions in the liveness object, to please the register allocator.
891 for (size_t i = 0; i < 32; ++i) {
892 liveness.instructions_from_lifetime_position_.push_back(user);
893 }
894
895 RegisterAllocator register_allocator(&allocator, &codegen, liveness);
896 register_allocator.unhandled_core_intervals_.push_back(fourth);
897 register_allocator.unhandled_core_intervals_.push_back(third);
898 register_allocator.unhandled_core_intervals_.push_back(second);
899 register_allocator.unhandled_core_intervals_.push_back(first);
900
901 // Set just one register available to make all intervals compete for the same.
902 register_allocator.number_of_registers_ = 1;
903 register_allocator.registers_array_ = allocator.AllocArray<size_t>(1);
904 register_allocator.processing_core_registers_ = true;
905 register_allocator.unhandled_ = ®ister_allocator.unhandled_core_intervals_;
906 register_allocator.LinearScan();
907
908 // Test that there is no conflicts between intervals.
909 ArenaVector<LiveInterval*> intervals(allocator.Adapter());
910 intervals.push_back(first);
911 intervals.push_back(second);
912 intervals.push_back(third);
913 intervals.push_back(fourth);
914 ASSERT_TRUE(RegisterAllocator::ValidateIntervals(
915 intervals, 0, 0, codegen, &allocator, true, false));
916 }
917
918 } // namespace art
919