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