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