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