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