register_allocator_test.cc revision 8030c4100d2586fac39ed4007c61ee91d4ea4f25
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#include "gtest/gtest.h" 32 33namespace art { 34 35// Note: the register allocator tests rely on the fact that constants have live 36// intervals and registers get allocated to them. 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 graph->TryBuildingSsa(); 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(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(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(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(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 graph->TryBuildingSsa(); 263 return graph; 264} 265 266TEST(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(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(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(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 NullHandle<mirror::DexCache> dex_cache; 476 graph->AddBlock(entry); 477 graph->SetEntryBlock(entry); 478 HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimNot); 479 entry->AddInstruction(parameter); 480 481 HBasicBlock* block = new (allocator) HBasicBlock(graph); 482 graph->AddBlock(block); 483 entry->AddSuccessor(block); 484 485 HInstruction* test = new (allocator) HInstanceFieldGet(parameter, 486 Primitive::kPrimBoolean, 487 MemberOffset(22), 488 false, 489 kUnknownFieldIndex, 490 graph->GetDexFile(), 491 dex_cache, 492 0); 493 block->AddInstruction(test); 494 block->AddInstruction(new (allocator) HIf(test)); 495 HBasicBlock* then = new (allocator) HBasicBlock(graph); 496 HBasicBlock* else_ = new (allocator) HBasicBlock(graph); 497 HBasicBlock* join = new (allocator) HBasicBlock(graph); 498 graph->AddBlock(then); 499 graph->AddBlock(else_); 500 graph->AddBlock(join); 501 502 block->AddSuccessor(then); 503 block->AddSuccessor(else_); 504 then->AddSuccessor(join); 505 else_->AddSuccessor(join); 506 then->AddInstruction(new (allocator) HGoto()); 507 else_->AddInstruction(new (allocator) HGoto()); 508 509 *phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); 510 join->AddPhi(*phi); 511 *input1 = new (allocator) HInstanceFieldGet(parameter, 512 Primitive::kPrimInt, 513 MemberOffset(42), 514 false, 515 kUnknownFieldIndex, 516 graph->GetDexFile(), 517 dex_cache, 518 0); 519*input2 = new (allocator) HInstanceFieldGet(parameter, 520 Primitive::kPrimInt, 521 MemberOffset(42), 522 false, 523 kUnknownFieldIndex, 524 graph->GetDexFile(), 525 dex_cache, 526 0); 527 then->AddInstruction(*input1); 528 else_->AddInstruction(*input2); 529 join->AddInstruction(new (allocator) HExit()); 530 (*phi)->AddInput(*input1); 531 (*phi)->AddInput(*input2); 532 533 graph->BuildDominatorTree(); 534 graph->AnalyzeNaturalLoops(); 535 return graph; 536} 537 538TEST(RegisterAllocatorTest, PhiHint) { 539 ArenaPool pool; 540 ArenaAllocator allocator(&pool); 541 HPhi *phi; 542 HInstruction *input1, *input2; 543 544 { 545 HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2); 546 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 547 X86InstructionSetFeatures::FromCppDefines()); 548 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 549 SsaLivenessAnalysis liveness(graph, &codegen); 550 liveness.Analyze(); 551 552 // Check that the register allocator is deterministic. 553 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 554 register_allocator.AllocateRegisters(); 555 556 ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 0); 557 ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 0); 558 ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 0); 559 } 560 561 { 562 HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2); 563 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 564 X86InstructionSetFeatures::FromCppDefines()); 565 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 566 SsaLivenessAnalysis liveness(graph, &codegen); 567 liveness.Analyze(); 568 569 // Set the phi to a specific register, and check that the inputs get allocated 570 // the same register. 571 phi->GetLocations()->UpdateOut(Location::RegisterLocation(2)); 572 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 573 register_allocator.AllocateRegisters(); 574 575 ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2); 576 ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2); 577 ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2); 578 } 579 580 { 581 HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2); 582 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 583 X86InstructionSetFeatures::FromCppDefines()); 584 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 585 SsaLivenessAnalysis liveness(graph, &codegen); 586 liveness.Analyze(); 587 588 // Set input1 to a specific register, and check that the phi and other input get allocated 589 // the same register. 590 input1->GetLocations()->UpdateOut(Location::RegisterLocation(2)); 591 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 592 register_allocator.AllocateRegisters(); 593 594 ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2); 595 ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2); 596 ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2); 597 } 598 599 { 600 HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2); 601 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 602 X86InstructionSetFeatures::FromCppDefines()); 603 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 604 SsaLivenessAnalysis liveness(graph, &codegen); 605 liveness.Analyze(); 606 607 // Set input2 to a specific register, and check that the phi and other input get allocated 608 // the same register. 609 input2->GetLocations()->UpdateOut(Location::RegisterLocation(2)); 610 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 611 register_allocator.AllocateRegisters(); 612 613 ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2); 614 ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2); 615 ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2); 616 } 617} 618 619static HGraph* BuildFieldReturn(ArenaAllocator* allocator, 620 HInstruction** field, 621 HInstruction** ret) { 622 HGraph* graph = CreateGraph(allocator); 623 NullHandle<mirror::DexCache> dex_cache; 624 HBasicBlock* entry = new (allocator) HBasicBlock(graph); 625 graph->AddBlock(entry); 626 graph->SetEntryBlock(entry); 627 HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimNot); 628 entry->AddInstruction(parameter); 629 630 HBasicBlock* block = new (allocator) HBasicBlock(graph); 631 graph->AddBlock(block); 632 entry->AddSuccessor(block); 633 634 *field = new (allocator) HInstanceFieldGet(parameter, 635 Primitive::kPrimInt, 636 MemberOffset(42), 637 false, 638 kUnknownFieldIndex, 639 graph->GetDexFile(), 640 dex_cache, 641 0); 642 block->AddInstruction(*field); 643 *ret = new (allocator) HReturn(*field); 644 block->AddInstruction(*ret); 645 646 HBasicBlock* exit = new (allocator) HBasicBlock(graph); 647 graph->AddBlock(exit); 648 block->AddSuccessor(exit); 649 exit->AddInstruction(new (allocator) HExit()); 650 651 graph->BuildDominatorTree(); 652 return graph; 653} 654 655TEST(RegisterAllocatorTest, ExpectedInRegisterHint) { 656 ArenaPool pool; 657 ArenaAllocator allocator(&pool); 658 HInstruction *field, *ret; 659 660 { 661 HGraph* graph = BuildFieldReturn(&allocator, &field, &ret); 662 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 663 X86InstructionSetFeatures::FromCppDefines()); 664 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 665 SsaLivenessAnalysis liveness(graph, &codegen); 666 liveness.Analyze(); 667 668 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 669 register_allocator.AllocateRegisters(); 670 671 // Sanity check that in normal conditions, the register should be hinted to 0 (EAX). 672 ASSERT_EQ(field->GetLiveInterval()->GetRegister(), 0); 673 } 674 675 { 676 HGraph* graph = BuildFieldReturn(&allocator, &field, &ret); 677 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 678 X86InstructionSetFeatures::FromCppDefines()); 679 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 680 SsaLivenessAnalysis liveness(graph, &codegen); 681 liveness.Analyze(); 682 683 // Check that the field gets put in the register expected by its use. 684 // Don't use SetInAt because we are overriding an already allocated location. 685 ret->GetLocations()->inputs_[0] = Location::RegisterLocation(2); 686 687 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 688 register_allocator.AllocateRegisters(); 689 690 ASSERT_EQ(field->GetLiveInterval()->GetRegister(), 2); 691 } 692} 693 694static HGraph* BuildTwoSubs(ArenaAllocator* allocator, 695 HInstruction** first_sub, 696 HInstruction** second_sub) { 697 HGraph* graph = CreateGraph(allocator); 698 HBasicBlock* entry = new (allocator) HBasicBlock(graph); 699 graph->AddBlock(entry); 700 graph->SetEntryBlock(entry); 701 HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimInt); 702 entry->AddInstruction(parameter); 703 704 HInstruction* constant1 = graph->GetIntConstant(1); 705 HInstruction* constant2 = graph->GetIntConstant(2); 706 707 HBasicBlock* block = new (allocator) HBasicBlock(graph); 708 graph->AddBlock(block); 709 entry->AddSuccessor(block); 710 711 *first_sub = new (allocator) HSub(Primitive::kPrimInt, parameter, constant1); 712 block->AddInstruction(*first_sub); 713 *second_sub = new (allocator) HSub(Primitive::kPrimInt, *first_sub, constant2); 714 block->AddInstruction(*second_sub); 715 716 block->AddInstruction(new (allocator) HExit()); 717 718 graph->BuildDominatorTree(); 719 return graph; 720} 721 722TEST(RegisterAllocatorTest, SameAsFirstInputHint) { 723 ArenaPool pool; 724 ArenaAllocator allocator(&pool); 725 HInstruction *first_sub, *second_sub; 726 727 { 728 HGraph* graph = BuildTwoSubs(&allocator, &first_sub, &second_sub); 729 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 730 X86InstructionSetFeatures::FromCppDefines()); 731 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 732 SsaLivenessAnalysis liveness(graph, &codegen); 733 liveness.Analyze(); 734 735 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 736 register_allocator.AllocateRegisters(); 737 738 // Sanity check that in normal conditions, the registers are the same. 739 ASSERT_EQ(first_sub->GetLiveInterval()->GetRegister(), 1); 740 ASSERT_EQ(second_sub->GetLiveInterval()->GetRegister(), 1); 741 } 742 743 { 744 HGraph* graph = BuildTwoSubs(&allocator, &first_sub, &second_sub); 745 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 746 X86InstructionSetFeatures::FromCppDefines()); 747 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 748 SsaLivenessAnalysis liveness(graph, &codegen); 749 liveness.Analyze(); 750 751 // check that both adds get the same register. 752 // Don't use UpdateOutput because output is already allocated. 753 first_sub->InputAt(0)->GetLocations()->output_ = Location::RegisterLocation(2); 754 ASSERT_EQ(first_sub->GetLocations()->Out().GetPolicy(), Location::kSameAsFirstInput); 755 ASSERT_EQ(second_sub->GetLocations()->Out().GetPolicy(), Location::kSameAsFirstInput); 756 757 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 758 register_allocator.AllocateRegisters(); 759 760 ASSERT_EQ(first_sub->GetLiveInterval()->GetRegister(), 2); 761 ASSERT_EQ(second_sub->GetLiveInterval()->GetRegister(), 2); 762 } 763} 764 765static HGraph* BuildDiv(ArenaAllocator* allocator, 766 HInstruction** div) { 767 HGraph* graph = CreateGraph(allocator); 768 HBasicBlock* entry = new (allocator) HBasicBlock(graph); 769 graph->AddBlock(entry); 770 graph->SetEntryBlock(entry); 771 HInstruction* first = new (allocator) HParameterValue(0, Primitive::kPrimInt); 772 HInstruction* second = new (allocator) HParameterValue(0, Primitive::kPrimInt); 773 entry->AddInstruction(first); 774 entry->AddInstruction(second); 775 776 HBasicBlock* block = new (allocator) HBasicBlock(graph); 777 graph->AddBlock(block); 778 entry->AddSuccessor(block); 779 780 *div = new (allocator) HDiv(Primitive::kPrimInt, first, second, 0); // don't care about dex_pc. 781 block->AddInstruction(*div); 782 783 block->AddInstruction(new (allocator) HExit()); 784 785 graph->BuildDominatorTree(); 786 return graph; 787} 788 789TEST(RegisterAllocatorTest, ExpectedExactInRegisterAndSameOutputHint) { 790 ArenaPool pool; 791 ArenaAllocator allocator(&pool); 792 HInstruction *div; 793 794 { 795 HGraph* graph = BuildDiv(&allocator, &div); 796 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 797 X86InstructionSetFeatures::FromCppDefines()); 798 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 799 SsaLivenessAnalysis liveness(graph, &codegen); 800 liveness.Analyze(); 801 802 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 803 register_allocator.AllocateRegisters(); 804 805 // div on x86 requires its first input in eax and the output be the same as the first input. 806 ASSERT_EQ(div->GetLiveInterval()->GetRegister(), 0); 807 } 808} 809 810// Test a bug in the register allocator, where allocating a blocked 811// register would lead to spilling an inactive interval at the wrong 812// position. 813TEST(RegisterAllocatorTest, SpillInactive) { 814 ArenaPool pool; 815 816 // Create a synthesized graph to please the register_allocator and 817 // ssa_liveness_analysis code. 818 ArenaAllocator allocator(&pool); 819 HGraph* graph = CreateGraph(&allocator); 820 HBasicBlock* entry = new (&allocator) HBasicBlock(graph); 821 graph->AddBlock(entry); 822 graph->SetEntryBlock(entry); 823 HInstruction* one = new (&allocator) HParameterValue(0, Primitive::kPrimInt); 824 HInstruction* two = new (&allocator) HParameterValue(0, Primitive::kPrimInt); 825 HInstruction* three = new (&allocator) HParameterValue(0, Primitive::kPrimInt); 826 HInstruction* four = new (&allocator) HParameterValue(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