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