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 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 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 */ 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 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 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 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 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 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 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 */ 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 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 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. 648 TEST_F(RegisterAllocatorTest, PhiHint_LinearScan) { 649 PhiHint(Strategy::kRegisterAllocatorLinearScan); 650 } 651 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 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. 728 TEST_F(RegisterAllocatorTest, ExpectedInRegisterHint_LinearScan) { 729 ExpectedInRegisterHint(Strategy::kRegisterAllocatorLinearScan); 730 } 731 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 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. 804 TEST_F(RegisterAllocatorTest, SameAsFirstInputHint_LinearScan) { 805 SameAsFirstInputHint(Strategy::kRegisterAllocatorLinearScan); 806 } 807 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 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. 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. 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
