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