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 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 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 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 */ 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 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 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 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 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 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 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 */ 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 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 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. 634 TEST_F(RegisterAllocatorTest, PhiHint_LinearScan) { 635 PhiHint(Strategy::kRegisterAllocatorLinearScan); 636 } 637 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 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. 710 TEST_F(RegisterAllocatorTest, ExpectedInRegisterHint_LinearScan) { 711 ExpectedInRegisterHint(Strategy::kRegisterAllocatorLinearScan); 712 } 713 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 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. 782 TEST_F(RegisterAllocatorTest, SameAsFirstInputHint_LinearScan) { 783 SameAsFirstInputHint(Strategy::kRegisterAllocatorLinearScan); 784 } 785 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 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. 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. 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
