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