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