register_allocator_test.cc revision 30971d6e2e13c0f2f70fd6d36cf7cba62eddbf04
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 GrowableArray<LiveInterval*> intervals(&allocator, 0); 68 69 // Test with two intervals of the same range. 70 { 71 static constexpr size_t ranges[][2] = {{0, 42}}; 72 intervals.Add(BuildInterval(ranges, arraysize(ranges), &allocator, 0)); 73 intervals.Add(BuildInterval(ranges, arraysize(ranges), &allocator, 1)); 74 ASSERT_TRUE(RegisterAllocator::ValidateIntervals( 75 intervals, 0, 0, codegen, &allocator, true, false)); 76 77 intervals.Get(1)->SetRegister(0); 78 ASSERT_FALSE(RegisterAllocator::ValidateIntervals( 79 intervals, 0, 0, codegen, &allocator, true, false)); 80 intervals.Reset(); 81 } 82 83 // Test with two non-intersecting intervals. 84 { 85 static constexpr size_t ranges1[][2] = {{0, 42}}; 86 intervals.Add(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0)); 87 static constexpr size_t ranges2[][2] = {{42, 43}}; 88 intervals.Add(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1)); 89 ASSERT_TRUE(RegisterAllocator::ValidateIntervals( 90 intervals, 0, 0, codegen, &allocator, true, false)); 91 92 intervals.Get(1)->SetRegister(0); 93 ASSERT_TRUE(RegisterAllocator::ValidateIntervals( 94 intervals, 0, 0, codegen, &allocator, true, false)); 95 intervals.Reset(); 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.Add(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0)); 102 static constexpr size_t ranges2[][2] = {{42, 43}}; 103 intervals.Add(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1)); 104 ASSERT_TRUE(RegisterAllocator::ValidateIntervals( 105 intervals, 0, 0, codegen, &allocator, true, false)); 106 107 intervals.Get(1)->SetRegister(0); 108 ASSERT_TRUE(RegisterAllocator::ValidateIntervals( 109 intervals, 0, 0, codegen, &allocator, true, false)); 110 intervals.Reset(); 111 } 112 113 // Test with intersecting intervals. 114 { 115 static constexpr size_t ranges1[][2] = {{0, 42}, {44, 48}}; 116 intervals.Add(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0)); 117 static constexpr size_t ranges2[][2] = {{42, 47}}; 118 intervals.Add(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1)); 119 ASSERT_TRUE(RegisterAllocator::ValidateIntervals( 120 intervals, 0, 0, codegen, &allocator, true, false)); 121 122 intervals.Get(1)->SetRegister(0); 123 ASSERT_FALSE(RegisterAllocator::ValidateIntervals( 124 intervals, 0, 0, codegen, &allocator, true, false)); 125 intervals.Reset(); 126 } 127 128 // Test with siblings. 129 { 130 static constexpr size_t ranges1[][2] = {{0, 42}, {44, 48}}; 131 intervals.Add(BuildInterval(ranges1, arraysize(ranges1), &allocator, 0)); 132 intervals.Get(0)->SplitAt(43); 133 static constexpr size_t ranges2[][2] = {{42, 47}}; 134 intervals.Add(BuildInterval(ranges2, arraysize(ranges2), &allocator, 1)); 135 ASSERT_TRUE(RegisterAllocator::ValidateIntervals( 136 intervals, 0, 0, codegen, &allocator, true, false)); 137 138 intervals.Get(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.Get(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().Get(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().Get(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().Get(1)->GetFirstInstruction()->AsXor(); 347 HXor* last_xor = graph->GetBlocks().Get(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_.Add( 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_.Add(interval); 446 447 interval = LiveInterval::MakeFixedInterval(&allocator, 0, Primitive::kPrimInt); 448 interval->AddRange(20, 30); 449 register_allocator.inactive_.Add(interval); 450 451 interval = LiveInterval::MakeFixedInterval(&allocator, 0, Primitive::kPrimInt); 452 interval->AddRange(60, 70); 453 register_allocator.inactive_.Add(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_->Get(0)->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 graph->AddBlock(entry); 476 graph->SetEntryBlock(entry); 477 HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimNot); 478 entry->AddInstruction(parameter); 479 480 HBasicBlock* block = new (allocator) HBasicBlock(graph); 481 graph->AddBlock(block); 482 entry->AddSuccessor(block); 483 484 HInstruction* test = new (allocator) HInstanceFieldGet(parameter, 485 Primitive::kPrimBoolean, 486 MemberOffset(22), 487 false, 488 kUnknownFieldIndex, 489 graph->GetDexFile()); 490 block->AddInstruction(test); 491 block->AddInstruction(new (allocator) HIf(test)); 492 HBasicBlock* then = new (allocator) HBasicBlock(graph); 493 HBasicBlock* else_ = new (allocator) HBasicBlock(graph); 494 HBasicBlock* join = new (allocator) HBasicBlock(graph); 495 graph->AddBlock(then); 496 graph->AddBlock(else_); 497 graph->AddBlock(join); 498 499 block->AddSuccessor(then); 500 block->AddSuccessor(else_); 501 then->AddSuccessor(join); 502 else_->AddSuccessor(join); 503 then->AddInstruction(new (allocator) HGoto()); 504 else_->AddInstruction(new (allocator) HGoto()); 505 506 *phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); 507 join->AddPhi(*phi); 508 *input1 = new (allocator) HInstanceFieldGet(parameter, 509 Primitive::kPrimInt, 510 MemberOffset(42), 511 false, 512 kUnknownFieldIndex, 513 graph->GetDexFile()); 514*input2 = new (allocator) HInstanceFieldGet(parameter, 515 Primitive::kPrimInt, 516 MemberOffset(42), 517 false, 518 kUnknownFieldIndex, 519 graph->GetDexFile()); 520 then->AddInstruction(*input1); 521 else_->AddInstruction(*input2); 522 join->AddInstruction(new (allocator) HExit()); 523 (*phi)->AddInput(*input1); 524 (*phi)->AddInput(*input2); 525 526 graph->BuildDominatorTree(); 527 graph->AnalyzeNaturalLoops(); 528 return graph; 529} 530 531TEST(RegisterAllocatorTest, PhiHint) { 532 ArenaPool pool; 533 ArenaAllocator allocator(&pool); 534 HPhi *phi; 535 HInstruction *input1, *input2; 536 537 { 538 HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2); 539 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 540 X86InstructionSetFeatures::FromCppDefines()); 541 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 542 SsaLivenessAnalysis liveness(graph, &codegen); 543 liveness.Analyze(); 544 545 // Check that the register allocator is deterministic. 546 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 547 register_allocator.AllocateRegisters(); 548 549 ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 0); 550 ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 0); 551 ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 0); 552 } 553 554 { 555 HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2); 556 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 557 X86InstructionSetFeatures::FromCppDefines()); 558 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 559 SsaLivenessAnalysis liveness(graph, &codegen); 560 liveness.Analyze(); 561 562 // Set the phi to a specific register, and check that the inputs get allocated 563 // the same register. 564 phi->GetLocations()->UpdateOut(Location::RegisterLocation(2)); 565 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 566 register_allocator.AllocateRegisters(); 567 568 ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2); 569 ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2); 570 ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2); 571 } 572 573 { 574 HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2); 575 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 576 X86InstructionSetFeatures::FromCppDefines()); 577 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 578 SsaLivenessAnalysis liveness(graph, &codegen); 579 liveness.Analyze(); 580 581 // Set input1 to a specific register, and check that the phi and other input get allocated 582 // the same register. 583 input1->GetLocations()->UpdateOut(Location::RegisterLocation(2)); 584 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 585 register_allocator.AllocateRegisters(); 586 587 ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2); 588 ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2); 589 ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2); 590 } 591 592 { 593 HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2); 594 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 595 X86InstructionSetFeatures::FromCppDefines()); 596 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 597 SsaLivenessAnalysis liveness(graph, &codegen); 598 liveness.Analyze(); 599 600 // Set input2 to a specific register, and check that the phi and other input get allocated 601 // the same register. 602 input2->GetLocations()->UpdateOut(Location::RegisterLocation(2)); 603 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 604 register_allocator.AllocateRegisters(); 605 606 ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2); 607 ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2); 608 ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2); 609 } 610} 611 612static HGraph* BuildFieldReturn(ArenaAllocator* allocator, 613 HInstruction** field, 614 HInstruction** ret) { 615 HGraph* graph = CreateGraph(allocator); 616 HBasicBlock* entry = new (allocator) HBasicBlock(graph); 617 graph->AddBlock(entry); 618 graph->SetEntryBlock(entry); 619 HInstruction* parameter = new (allocator) HParameterValue(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 graph->GetDexFile()); 632 block->AddInstruction(*field); 633 *ret = new (allocator) HReturn(*field); 634 block->AddInstruction(*ret); 635 636 HBasicBlock* exit = new (allocator) HBasicBlock(graph); 637 graph->AddBlock(exit); 638 block->AddSuccessor(exit); 639 exit->AddInstruction(new (allocator) HExit()); 640 641 graph->BuildDominatorTree(); 642 return graph; 643} 644 645TEST(RegisterAllocatorTest, ExpectedInRegisterHint) { 646 ArenaPool pool; 647 ArenaAllocator allocator(&pool); 648 HInstruction *field, *ret; 649 650 { 651 HGraph* graph = BuildFieldReturn(&allocator, &field, &ret); 652 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 653 X86InstructionSetFeatures::FromCppDefines()); 654 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 655 SsaLivenessAnalysis liveness(graph, &codegen); 656 liveness.Analyze(); 657 658 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 659 register_allocator.AllocateRegisters(); 660 661 // Sanity check that in normal conditions, the register should be hinted to 0 (EAX). 662 ASSERT_EQ(field->GetLiveInterval()->GetRegister(), 0); 663 } 664 665 { 666 HGraph* graph = BuildFieldReturn(&allocator, &field, &ret); 667 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 668 X86InstructionSetFeatures::FromCppDefines()); 669 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 670 SsaLivenessAnalysis liveness(graph, &codegen); 671 liveness.Analyze(); 672 673 // Check that the field gets put in the register expected by its use. 674 // Don't use SetInAt because we are overriding an already allocated location. 675 ret->GetLocations()->inputs_.Put(0, Location::RegisterLocation(2)); 676 677 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 678 register_allocator.AllocateRegisters(); 679 680 ASSERT_EQ(field->GetLiveInterval()->GetRegister(), 2); 681 } 682} 683 684static HGraph* BuildTwoSubs(ArenaAllocator* allocator, 685 HInstruction** first_sub, 686 HInstruction** second_sub) { 687 HGraph* graph = CreateGraph(allocator); 688 HBasicBlock* entry = new (allocator) HBasicBlock(graph); 689 graph->AddBlock(entry); 690 graph->SetEntryBlock(entry); 691 HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimInt); 692 entry->AddInstruction(parameter); 693 694 HInstruction* constant1 = graph->GetIntConstant(1); 695 HInstruction* constant2 = graph->GetIntConstant(2); 696 697 HBasicBlock* block = new (allocator) HBasicBlock(graph); 698 graph->AddBlock(block); 699 entry->AddSuccessor(block); 700 701 *first_sub = new (allocator) HSub(Primitive::kPrimInt, parameter, constant1); 702 block->AddInstruction(*first_sub); 703 *second_sub = new (allocator) HSub(Primitive::kPrimInt, *first_sub, constant2); 704 block->AddInstruction(*second_sub); 705 706 block->AddInstruction(new (allocator) HExit()); 707 708 graph->BuildDominatorTree(); 709 return graph; 710} 711 712TEST(RegisterAllocatorTest, SameAsFirstInputHint) { 713 ArenaPool pool; 714 ArenaAllocator allocator(&pool); 715 HInstruction *first_sub, *second_sub; 716 717 { 718 HGraph* graph = BuildTwoSubs(&allocator, &first_sub, &second_sub); 719 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 720 X86InstructionSetFeatures::FromCppDefines()); 721 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 722 SsaLivenessAnalysis liveness(graph, &codegen); 723 liveness.Analyze(); 724 725 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 726 register_allocator.AllocateRegisters(); 727 728 // Sanity check that in normal conditions, the registers are the same. 729 ASSERT_EQ(first_sub->GetLiveInterval()->GetRegister(), 1); 730 ASSERT_EQ(second_sub->GetLiveInterval()->GetRegister(), 1); 731 } 732 733 { 734 HGraph* graph = BuildTwoSubs(&allocator, &first_sub, &second_sub); 735 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 736 X86InstructionSetFeatures::FromCppDefines()); 737 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 738 SsaLivenessAnalysis liveness(graph, &codegen); 739 liveness.Analyze(); 740 741 // check that both adds get the same register. 742 // Don't use UpdateOutput because output is already allocated. 743 first_sub->InputAt(0)->GetLocations()->output_ = Location::RegisterLocation(2); 744 ASSERT_EQ(first_sub->GetLocations()->Out().GetPolicy(), Location::kSameAsFirstInput); 745 ASSERT_EQ(second_sub->GetLocations()->Out().GetPolicy(), Location::kSameAsFirstInput); 746 747 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 748 register_allocator.AllocateRegisters(); 749 750 ASSERT_EQ(first_sub->GetLiveInterval()->GetRegister(), 2); 751 ASSERT_EQ(second_sub->GetLiveInterval()->GetRegister(), 2); 752 } 753} 754 755static HGraph* BuildDiv(ArenaAllocator* allocator, 756 HInstruction** div) { 757 HGraph* graph = CreateGraph(allocator); 758 HBasicBlock* entry = new (allocator) HBasicBlock(graph); 759 graph->AddBlock(entry); 760 graph->SetEntryBlock(entry); 761 HInstruction* first = new (allocator) HParameterValue(0, Primitive::kPrimInt); 762 HInstruction* second = new (allocator) HParameterValue(0, Primitive::kPrimInt); 763 entry->AddInstruction(first); 764 entry->AddInstruction(second); 765 766 HBasicBlock* block = new (allocator) HBasicBlock(graph); 767 graph->AddBlock(block); 768 entry->AddSuccessor(block); 769 770 *div = new (allocator) HDiv(Primitive::kPrimInt, first, second, 0); // don't care about dex_pc. 771 block->AddInstruction(*div); 772 773 block->AddInstruction(new (allocator) HExit()); 774 775 graph->BuildDominatorTree(); 776 return graph; 777} 778 779TEST(RegisterAllocatorTest, ExpectedExactInRegisterAndSameOutputHint) { 780 ArenaPool pool; 781 ArenaAllocator allocator(&pool); 782 HInstruction *div; 783 784 { 785 HGraph* graph = BuildDiv(&allocator, &div); 786 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 787 X86InstructionSetFeatures::FromCppDefines()); 788 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 789 SsaLivenessAnalysis liveness(graph, &codegen); 790 liveness.Analyze(); 791 792 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 793 register_allocator.AllocateRegisters(); 794 795 // div on x86 requires its first input in eax and the output be the same as the first input. 796 ASSERT_EQ(div->GetLiveInterval()->GetRegister(), 0); 797 } 798} 799 800// Test a bug in the register allocator, where allocating a blocked 801// register would lead to spilling an inactive interval at the wrong 802// position. 803TEST(RegisterAllocatorTest, SpillInactive) { 804 ArenaPool pool; 805 806 // Create a synthesized graph to please the register_allocator and 807 // ssa_liveness_analysis code. 808 ArenaAllocator allocator(&pool); 809 HGraph* graph = CreateGraph(&allocator); 810 HBasicBlock* entry = new (&allocator) HBasicBlock(graph); 811 graph->AddBlock(entry); 812 graph->SetEntryBlock(entry); 813 HInstruction* one = new (&allocator) HParameterValue(0, Primitive::kPrimInt); 814 HInstruction* two = new (&allocator) HParameterValue(0, Primitive::kPrimInt); 815 HInstruction* three = new (&allocator) HParameterValue(0, Primitive::kPrimInt); 816 HInstruction* four = new (&allocator) HParameterValue(0, Primitive::kPrimInt); 817 entry->AddInstruction(one); 818 entry->AddInstruction(two); 819 entry->AddInstruction(three); 820 entry->AddInstruction(four); 821 822 HBasicBlock* block = new (&allocator) HBasicBlock(graph); 823 graph->AddBlock(block); 824 entry->AddSuccessor(block); 825 block->AddInstruction(new (&allocator) HExit()); 826 827 // We create a synthesized user requesting a register, to avoid just spilling the 828 // intervals. 829 HPhi* user = new (&allocator) HPhi(&allocator, 0, 1, Primitive::kPrimInt); 830 user->AddInput(one); 831 user->SetBlock(block); 832 LocationSummary* locations = new (&allocator) LocationSummary(user, LocationSummary::kNoCall); 833 locations->SetInAt(0, Location::RequiresRegister()); 834 static constexpr size_t phi_ranges[][2] = {{20, 30}}; 835 BuildInterval(phi_ranges, arraysize(phi_ranges), &allocator, -1, user); 836 837 // Create an interval with lifetime holes. 838 static constexpr size_t ranges1[][2] = {{0, 2}, {4, 6}, {8, 10}}; 839 LiveInterval* first = BuildInterval(ranges1, arraysize(ranges1), &allocator, -1, one); 840 first->first_use_ = new(&allocator) UsePosition(user, 0, false, 8, first->first_use_); 841 first->first_use_ = new(&allocator) UsePosition(user, 0, false, 7, first->first_use_); 842 first->first_use_ = new(&allocator) UsePosition(user, 0, false, 6, first->first_use_); 843 844 locations = new (&allocator) LocationSummary(first->GetDefinedBy(), LocationSummary::kNoCall); 845 locations->SetOut(Location::RequiresRegister()); 846 first = first->SplitAt(1); 847 848 // Create an interval that conflicts with the next interval, to force the next 849 // interval to call `AllocateBlockedReg`. 850 static constexpr size_t ranges2[][2] = {{2, 4}}; 851 LiveInterval* second = BuildInterval(ranges2, arraysize(ranges2), &allocator, -1, two); 852 locations = new (&allocator) LocationSummary(second->GetDefinedBy(), LocationSummary::kNoCall); 853 locations->SetOut(Location::RequiresRegister()); 854 855 // Create an interval that will lead to splitting the first interval. The bug occured 856 // by splitting at a wrong position, in this case at the next intersection between 857 // this interval and the first interval. We would have then put the interval with ranges 858 // "[0, 2(, [4, 6(" in the list of handled intervals, even though we haven't processed intervals 859 // before lifetime position 6 yet. 860 static constexpr size_t ranges3[][2] = {{2, 4}, {8, 10}}; 861 LiveInterval* third = BuildInterval(ranges3, arraysize(ranges3), &allocator, -1, three); 862 third->first_use_ = new(&allocator) UsePosition(user, 0, false, 8, third->first_use_); 863 third->first_use_ = new(&allocator) UsePosition(user, 0, false, 4, third->first_use_); 864 third->first_use_ = new(&allocator) UsePosition(user, 0, false, 3, third->first_use_); 865 locations = new (&allocator) LocationSummary(third->GetDefinedBy(), LocationSummary::kNoCall); 866 locations->SetOut(Location::RequiresRegister()); 867 third = third->SplitAt(3); 868 869 // Because the first part of the split interval was considered handled, this interval 870 // was free to allocate the same register, even though it conflicts with it. 871 static constexpr size_t ranges4[][2] = {{4, 6}}; 872 LiveInterval* fourth = BuildInterval(ranges4, arraysize(ranges4), &allocator, -1, four); 873 locations = new (&allocator) LocationSummary(fourth->GetDefinedBy(), LocationSummary::kNoCall); 874 locations->SetOut(Location::RequiresRegister()); 875 876 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 877 X86InstructionSetFeatures::FromCppDefines()); 878 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 879 SsaLivenessAnalysis liveness(graph, &codegen); 880 // Populate the instructions in the liveness object, to please the register allocator. 881 for (size_t i = 0; i < 32; ++i) { 882 liveness.instructions_from_lifetime_position_.Add(user); 883 } 884 885 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 886 register_allocator.unhandled_core_intervals_.Add(fourth); 887 register_allocator.unhandled_core_intervals_.Add(third); 888 register_allocator.unhandled_core_intervals_.Add(second); 889 register_allocator.unhandled_core_intervals_.Add(first); 890 891 // Set just one register available to make all intervals compete for the same. 892 register_allocator.number_of_registers_ = 1; 893 register_allocator.registers_array_ = allocator.AllocArray<size_t>(1); 894 register_allocator.processing_core_registers_ = true; 895 register_allocator.unhandled_ = ®ister_allocator.unhandled_core_intervals_; 896 register_allocator.LinearScan(); 897 898 // Test that there is no conflicts between intervals. 899 GrowableArray<LiveInterval*> intervals(&allocator, 0); 900 intervals.Add(first); 901 intervals.Add(second); 902 intervals.Add(third); 903 intervals.Add(fourth); 904 ASSERT_TRUE(RegisterAllocator::ValidateIntervals( 905 intervals, 0, 0, codegen, &allocator, true, false)); 906} 907 908} // namespace art 909