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 = MakeParam(DataType::Type::kReference);
465
466 HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph);
467 graph->AddBlock(block);
468 entry->AddSuccessor(block);
469
470 HInstruction* test = MakeIFieldGet(block, parameter, DataType::Type::kBool, MemberOffset(22));
471 MakeIf(block, test);
472
473 HBasicBlock* then = new (GetAllocator()) HBasicBlock(graph);
474 HBasicBlock* else_ = new (GetAllocator()) HBasicBlock(graph);
475 HBasicBlock* join = new (GetAllocator()) HBasicBlock(graph);
476 graph->AddBlock(then);
477 graph->AddBlock(else_);
478 graph->AddBlock(join);
479
480 block->AddSuccessor(then);
481 block->AddSuccessor(else_);
482 then->AddSuccessor(join);
483 else_->AddSuccessor(join);
484 MakeGoto(then);
485 MakeGoto(else_);
486
487 *input1 = MakeIFieldGet(then, parameter, DataType::Type::kInt32, MemberOffset(42));
488 *input2 = MakeIFieldGet(else_, parameter, DataType::Type::kInt32, MemberOffset(42));
489
490 *phi = MakePhi(join, {*input1, *input2});
491 MakeExit(join);
492
493 graph->BuildDominatorTree();
494 graph->AnalyzeLoops();
495 return graph;
496 }
497
TEST_F(RegisterAllocatorTest,PhiHint)498 TEST_F(RegisterAllocatorTest, PhiHint) {
499 HPhi *phi;
500 HInstruction *input1, *input2;
501
502 {
503 HGraph* graph = BuildIfElseWithPhi(&phi, &input1, &input2);
504 x86::CodeGeneratorX86 codegen(graph, *compiler_options_);
505 SsaLivenessAnalysis liveness(graph, &codegen, GetScopedAllocator());
506 liveness.Analyze();
507
508 // Check that the register allocator is deterministic.
509 std::unique_ptr<RegisterAllocator> register_allocator =
510 RegisterAllocator::Create(GetScopedAllocator(), &codegen, liveness);
511 register_allocator->AllocateRegisters();
512
513 ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 0);
514 ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 0);
515 ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 0);
516 }
517
518 {
519 HGraph* graph = BuildIfElseWithPhi(&phi, &input1, &input2);
520 x86::CodeGeneratorX86 codegen(graph, *compiler_options_);
521 SsaLivenessAnalysis liveness(graph, &codegen, GetScopedAllocator());
522 liveness.Analyze();
523
524 // Set the phi to a specific register, and check that the inputs get allocated
525 // the same register.
526 phi->GetLocations()->UpdateOut(Location::RegisterLocation(2));
527 std::unique_ptr<RegisterAllocator> register_allocator =
528 RegisterAllocator::Create(GetScopedAllocator(), &codegen, liveness);
529 register_allocator->AllocateRegisters();
530
531 ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2);
532 ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2);
533 ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2);
534 }
535
536 {
537 HGraph* graph = BuildIfElseWithPhi(&phi, &input1, &input2);
538 x86::CodeGeneratorX86 codegen(graph, *compiler_options_);
539 SsaLivenessAnalysis liveness(graph, &codegen, GetScopedAllocator());
540 liveness.Analyze();
541
542 // Set input1 to a specific register, and check that the phi and other input get allocated
543 // the same register.
544 input1->GetLocations()->UpdateOut(Location::RegisterLocation(2));
545 std::unique_ptr<RegisterAllocator> register_allocator =
546 RegisterAllocator::Create(GetScopedAllocator(), &codegen, liveness);
547 register_allocator->AllocateRegisters();
548
549 ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2);
550 ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2);
551 ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2);
552 }
553
554 {
555 HGraph* graph = BuildIfElseWithPhi(&phi, &input1, &input2);
556 x86::CodeGeneratorX86 codegen(graph, *compiler_options_);
557 SsaLivenessAnalysis liveness(graph, &codegen, GetScopedAllocator());
558 liveness.Analyze();
559
560 // Set input2 to a specific register, and check that the phi and other input get allocated
561 // the same register.
562 input2->GetLocations()->UpdateOut(Location::RegisterLocation(2));
563 std::unique_ptr<RegisterAllocator> register_allocator =
564 RegisterAllocator::Create(GetScopedAllocator(), &codegen, liveness);
565 register_allocator->AllocateRegisters();
566
567 ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2);
568 ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2);
569 ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2);
570 }
571 }
572
BuildFieldReturn(HInstruction ** field,HInstruction ** ret)573 HGraph* RegisterAllocatorTest::BuildFieldReturn(HInstruction** field, HInstruction** ret) {
574 HGraph* graph = CreateGraph();
575 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph);
576 graph->AddBlock(entry);
577 graph->SetEntryBlock(entry);
578 HInstruction* parameter = MakeParam(DataType::Type::kReference);
579
580 HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph);
581 graph->AddBlock(block);
582 entry->AddSuccessor(block);
583
584 *field = MakeIFieldGet(block, parameter, DataType::Type::kInt32, MemberOffset(42));
585 *ret = MakeReturn(block, *field);
586
587 HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph);
588 graph->AddBlock(exit);
589 block->AddSuccessor(exit);
590 MakeExit(exit);
591
592 graph->BuildDominatorTree();
593 return graph;
594 }
595
TEST_F(RegisterAllocatorTest,ExpectedInRegisterHint)596 TEST_F(RegisterAllocatorTest, ExpectedInRegisterHint) {
597 HInstruction *field, *ret;
598
599 {
600 HGraph* graph = BuildFieldReturn(&field, &ret);
601 x86::CodeGeneratorX86 codegen(graph, *compiler_options_);
602 SsaLivenessAnalysis liveness(graph, &codegen, GetScopedAllocator());
603 liveness.Analyze();
604
605 std::unique_ptr<RegisterAllocator> register_allocator =
606 RegisterAllocator::Create(GetScopedAllocator(), &codegen, liveness);
607 register_allocator->AllocateRegisters();
608
609 // Check the validity that in normal conditions, the register should be hinted to 0 (EAX).
610 ASSERT_EQ(field->GetLiveInterval()->GetRegister(), 0);
611 }
612
613 {
614 HGraph* graph = BuildFieldReturn(&field, &ret);
615 x86::CodeGeneratorX86 codegen(graph, *compiler_options_);
616 SsaLivenessAnalysis liveness(graph, &codegen, GetScopedAllocator());
617 liveness.Analyze();
618
619 // Check that the field gets put in the register expected by its use.
620 // Don't use SetInAt because we are overriding an already allocated location.
621 ret->GetLocations()->inputs_[0] = Location::RegisterLocation(2);
622
623 std::unique_ptr<RegisterAllocator> register_allocator =
624 RegisterAllocator::Create(GetScopedAllocator(), &codegen, liveness);
625 register_allocator->AllocateRegisters();
626
627 ASSERT_EQ(field->GetLiveInterval()->GetRegister(), 2);
628 }
629 }
630
BuildTwoSubs(HInstruction ** first_sub,HInstruction ** second_sub)631 HGraph* RegisterAllocatorTest::BuildTwoSubs(HInstruction** first_sub, HInstruction** second_sub) {
632 HGraph* graph = CreateGraph();
633 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph);
634 graph->AddBlock(entry);
635 graph->SetEntryBlock(entry);
636 HInstruction* parameter = MakeParam(DataType::Type::kInt32);
637
638 HInstruction* constant1 = graph->GetIntConstant(1);
639 HInstruction* constant2 = graph->GetIntConstant(2);
640
641 HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph);
642 graph->AddBlock(block);
643 entry->AddSuccessor(block);
644
645 *first_sub = new (GetAllocator()) HSub(DataType::Type::kInt32, parameter, constant1);
646 block->AddInstruction(*first_sub);
647 *second_sub = new (GetAllocator()) HSub(DataType::Type::kInt32, *first_sub, constant2);
648 block->AddInstruction(*second_sub);
649
650 MakeExit(block);
651
652 graph->BuildDominatorTree();
653 return graph;
654 }
655
TEST_F(RegisterAllocatorTest,SameAsFirstInputHint)656 TEST_F(RegisterAllocatorTest, SameAsFirstInputHint) {
657 HInstruction *first_sub, *second_sub;
658
659 {
660 HGraph* graph = BuildTwoSubs(&first_sub, &second_sub);
661 x86::CodeGeneratorX86 codegen(graph, *compiler_options_);
662 SsaLivenessAnalysis liveness(graph, &codegen, GetScopedAllocator());
663 liveness.Analyze();
664
665 std::unique_ptr<RegisterAllocator> register_allocator =
666 RegisterAllocator::Create(GetScopedAllocator(), &codegen, liveness);
667 register_allocator->AllocateRegisters();
668
669 // Check the validity that in normal conditions, the registers are the same.
670 ASSERT_EQ(first_sub->GetLiveInterval()->GetRegister(), 1);
671 ASSERT_EQ(second_sub->GetLiveInterval()->GetRegister(), 1);
672 }
673
674 {
675 HGraph* graph = BuildTwoSubs(&first_sub, &second_sub);
676 x86::CodeGeneratorX86 codegen(graph, *compiler_options_);
677 SsaLivenessAnalysis liveness(graph, &codegen, GetScopedAllocator());
678 liveness.Analyze();
679
680 // check that both adds get the same register.
681 // Don't use UpdateOutput because output is already allocated.
682 first_sub->InputAt(0)->GetLocations()->output_ = Location::RegisterLocation(2);
683 ASSERT_EQ(first_sub->GetLocations()->Out().GetPolicy(), Location::kSameAsFirstInput);
684 ASSERT_EQ(second_sub->GetLocations()->Out().GetPolicy(), Location::kSameAsFirstInput);
685
686 std::unique_ptr<RegisterAllocator> register_allocator =
687 RegisterAllocator::Create(GetScopedAllocator(), &codegen, liveness);
688 register_allocator->AllocateRegisters();
689
690 ASSERT_EQ(first_sub->GetLiveInterval()->GetRegister(), 2);
691 ASSERT_EQ(second_sub->GetLiveInterval()->GetRegister(), 2);
692 }
693 }
694
BuildDiv(HInstruction ** div)695 HGraph* RegisterAllocatorTest::BuildDiv(HInstruction** div) {
696 HGraph* graph = CreateGraph();
697 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph);
698 graph->AddBlock(entry);
699 graph->SetEntryBlock(entry);
700 HInstruction* first = MakeParam(DataType::Type::kInt32);
701 HInstruction* second = MakeParam(DataType::Type::kInt32);
702
703 HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph);
704 graph->AddBlock(block);
705 entry->AddSuccessor(block);
706
707 *div = new (GetAllocator()) HDiv(
708 DataType::Type::kInt32, first, second, 0); // don't care about dex_pc.
709 block->AddInstruction(*div);
710
711 MakeExit(block);
712
713 graph->BuildDominatorTree();
714 return graph;
715 }
716
TEST_F(RegisterAllocatorTest,ExpectedExactInRegisterAndSameOutputHint)717 TEST_F(RegisterAllocatorTest, ExpectedExactInRegisterAndSameOutputHint) {
718 HInstruction *div;
719 HGraph* graph = BuildDiv(&div);
720 x86::CodeGeneratorX86 codegen(graph, *compiler_options_);
721 SsaLivenessAnalysis liveness(graph, &codegen, GetScopedAllocator());
722 liveness.Analyze();
723
724 std::unique_ptr<RegisterAllocator> register_allocator =
725 RegisterAllocator::Create(GetScopedAllocator(), &codegen, liveness);
726 register_allocator->AllocateRegisters();
727
728 // div on x86 requires its first input in eax and the output be the same as the first input.
729 ASSERT_EQ(div->GetLiveInterval()->GetRegister(), 0);
730 }
731
732 // Test a bug in the register allocator, where allocating a blocked
733 // register would lead to spilling an inactive interval at the wrong
734 // position.
735 // This test only applies to the linear scan allocator.
TEST_F(RegisterAllocatorTest,SpillInactive)736 TEST_F(RegisterAllocatorTest, SpillInactive) {
737 // Create a synthesized graph to please the register_allocator and
738 // ssa_liveness_analysis code.
739 HGraph* graph = CreateGraph();
740 HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph);
741 graph->AddBlock(entry);
742 graph->SetEntryBlock(entry);
743 HInstruction* one = MakeParam(DataType::Type::kInt32);
744 HInstruction* two = MakeParam(DataType::Type::kInt32);
745 HInstruction* three = MakeParam(DataType::Type::kInt32);
746 HInstruction* four = MakeParam(DataType::Type::kInt32);
747
748 HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph);
749 graph->AddBlock(block);
750 entry->AddSuccessor(block);
751 MakeExit(block);
752
753 // We create a synthesized user requesting a register, to avoid just spilling the
754 // intervals.
755 HPhi* user = new (GetAllocator()) HPhi(GetAllocator(), 0, 1, DataType::Type::kInt32);
756 user->SetBlock(block);
757 user->AddInput(one);
758 LocationSummary* locations = new (GetAllocator()) LocationSummary(user, LocationSummary::kNoCall);
759 locations->SetInAt(0, Location::RequiresRegister());
760 static constexpr size_t phi_ranges[][2] = {{20, 30}};
761 BuildInterval(phi_ranges, arraysize(phi_ranges), GetScopedAllocator(), -1, user);
762
763 // Create an interval with lifetime holes.
764 static constexpr size_t ranges1[][2] = {{0, 2}, {4, 6}, {8, 10}};
765 LiveInterval* first = BuildInterval(ranges1, arraysize(ranges1), GetScopedAllocator(), -1, one);
766 first->uses_.push_front(*new (GetScopedAllocator()) UsePosition(user, 0u, 8));
767 first->uses_.push_front(*new (GetScopedAllocator()) UsePosition(user, 0u, 7));
768 first->uses_.push_front(*new (GetScopedAllocator()) UsePosition(user, 0u, 6));
769
770 locations = new (GetAllocator()) LocationSummary(first->GetDefinedBy(), LocationSummary::kNoCall);
771 locations->SetOut(Location::RequiresRegister());
772 first = first->SplitAt(1);
773
774 // Create an interval that conflicts with the next interval, to force the next
775 // interval to call `AllocateBlockedReg`.
776 static constexpr size_t ranges2[][2] = {{2, 4}};
777 LiveInterval* second = BuildInterval(ranges2, arraysize(ranges2), GetScopedAllocator(), -1, two);
778 locations =
779 new (GetAllocator()) LocationSummary(second->GetDefinedBy(), LocationSummary::kNoCall);
780 locations->SetOut(Location::RequiresRegister());
781
782 // Create an interval that will lead to splitting the first interval. The bug occured
783 // by splitting at a wrong position, in this case at the next intersection between
784 // this interval and the first interval. We would have then put the interval with ranges
785 // "[0, 2(, [4, 6(" in the list of handled intervals, even though we haven't processed intervals
786 // before lifetime position 6 yet.
787 static constexpr size_t ranges3[][2] = {{2, 4}, {8, 10}};
788 LiveInterval* third = BuildInterval(ranges3, arraysize(ranges3), GetScopedAllocator(), -1, three);
789 third->uses_.push_front(*new (GetScopedAllocator()) UsePosition(user, 0u, 8));
790 third->uses_.push_front(*new (GetScopedAllocator()) UsePosition(user, 0u, 4));
791 third->uses_.push_front(*new (GetScopedAllocator()) UsePosition(user, 0u, 3));
792 locations = new (GetAllocator()) LocationSummary(third->GetDefinedBy(), LocationSummary::kNoCall);
793 locations->SetOut(Location::RequiresRegister());
794 third = third->SplitAt(3);
795
796 // Because the first part of the split interval was considered handled, this interval
797 // was free to allocate the same register, even though it conflicts with it.
798 static constexpr size_t ranges4[][2] = {{4, 6}};
799 LiveInterval* fourth = BuildInterval(ranges4, arraysize(ranges4), GetScopedAllocator(), -1, four);
800 locations =
801 new (GetAllocator()) LocationSummary(fourth->GetDefinedBy(), LocationSummary::kNoCall);
802 locations->SetOut(Location::RequiresRegister());
803
804 x86::CodeGeneratorX86 codegen(graph, *compiler_options_);
805 SsaLivenessAnalysis liveness(graph, &codegen, GetScopedAllocator());
806 // Populate the instructions in the liveness object, to please the register allocator.
807 for (size_t i = 0; i < 32; ++i) {
808 liveness.instructions_from_lifetime_position_.push_back(user);
809 }
810
811 RegisterAllocatorLinearScan register_allocator(GetScopedAllocator(), &codegen, liveness);
812 register_allocator.unhandled_core_intervals_.push_back(fourth);
813 register_allocator.unhandled_core_intervals_.push_back(third);
814 register_allocator.unhandled_core_intervals_.push_back(second);
815 register_allocator.unhandled_core_intervals_.push_back(first);
816
817 // Set just one register available to make all intervals compete for the same.
818 register_allocator.number_of_registers_ = 1;
819 register_allocator.registers_array_ = GetAllocator()->AllocArray<size_t>(1);
820 register_allocator.current_register_type_ = RegisterAllocator::RegisterType::kCoreRegister;
821 register_allocator.unhandled_ = ®ister_allocator.unhandled_core_intervals_;
822 register_allocator.LinearScan();
823
824 // Test that there is no conflicts between intervals.
825 ScopedArenaVector<LiveInterval*> intervals(GetScopedAllocator()->Adapter());
826 intervals.push_back(first);
827 intervals.push_back(second);
828 intervals.push_back(third);
829 intervals.push_back(fourth);
830 ASSERT_TRUE(ValidateIntervals(intervals, codegen));
831 }
832
833 } // namespace art
834