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 // For SSA value intervals, only an interval resulted from a split may intersect 430 // with inactive intervals. 431 unhandled = register_allocator.Split(unhandled, 5); 432 433 // Add three temps holding the same register, and starting at different positions. 434 // Put the one that should be picked in the middle of the inactive list to ensure 435 // we do not depend on an order. 436 LiveInterval* interval = LiveInterval::MakeFixedInterval(&allocator, 0, Primitive::kPrimInt); 437 interval->AddRange(40, 50); 438 register_allocator.inactive_.Add(interval); 439 440 interval = LiveInterval::MakeFixedInterval(&allocator, 0, Primitive::kPrimInt); 441 interval->AddRange(20, 30); 442 register_allocator.inactive_.Add(interval); 443 444 interval = LiveInterval::MakeFixedInterval(&allocator, 0, Primitive::kPrimInt); 445 interval->AddRange(60, 70); 446 register_allocator.inactive_.Add(interval); 447 448 register_allocator.number_of_registers_ = 1; 449 register_allocator.registers_array_ = allocator.AllocArray<size_t>(1); 450 register_allocator.processing_core_registers_ = true; 451 register_allocator.unhandled_ = ®ister_allocator.unhandled_core_intervals_; 452 453 ASSERT_TRUE(register_allocator.TryAllocateFreeReg(unhandled)); 454 455 // Check that we have split the interval. 456 ASSERT_EQ(1u, register_allocator.unhandled_->Size()); 457 // Check that we know need to find a new register where the next interval 458 // that uses the register starts. 459 ASSERT_EQ(20u, register_allocator.unhandled_->Get(0)->GetStart()); 460} 461 462static HGraph* BuildIfElseWithPhi(ArenaAllocator* allocator, 463 HPhi** phi, 464 HInstruction** input1, 465 HInstruction** input2) { 466 HGraph* graph = CreateGraph(allocator); 467 HBasicBlock* entry = new (allocator) HBasicBlock(graph); 468 graph->AddBlock(entry); 469 graph->SetEntryBlock(entry); 470 HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimNot); 471 entry->AddInstruction(parameter); 472 473 HBasicBlock* block = new (allocator) HBasicBlock(graph); 474 graph->AddBlock(block); 475 entry->AddSuccessor(block); 476 477 HInstruction* test = new (allocator) HInstanceFieldGet( 478 parameter, Primitive::kPrimBoolean, MemberOffset(22), false); 479 block->AddInstruction(test); 480 block->AddInstruction(new (allocator) HIf(test)); 481 HBasicBlock* then = new (allocator) HBasicBlock(graph); 482 HBasicBlock* else_ = new (allocator) HBasicBlock(graph); 483 HBasicBlock* join = new (allocator) HBasicBlock(graph); 484 graph->AddBlock(then); 485 graph->AddBlock(else_); 486 graph->AddBlock(join); 487 488 block->AddSuccessor(then); 489 block->AddSuccessor(else_); 490 then->AddSuccessor(join); 491 else_->AddSuccessor(join); 492 then->AddInstruction(new (allocator) HGoto()); 493 else_->AddInstruction(new (allocator) HGoto()); 494 495 *phi = new (allocator) HPhi(allocator, 0, 0, Primitive::kPrimInt); 496 join->AddPhi(*phi); 497 *input1 = new (allocator) HInstanceFieldGet(parameter, Primitive::kPrimInt, 498 MemberOffset(42), false); 499 *input2 = new (allocator) HInstanceFieldGet(parameter, Primitive::kPrimInt, 500 MemberOffset(42), false); 501 then->AddInstruction(*input1); 502 else_->AddInstruction(*input2); 503 join->AddInstruction(new (allocator) HExit()); 504 (*phi)->AddInput(*input1); 505 (*phi)->AddInput(*input2); 506 507 graph->BuildDominatorTree(); 508 graph->AnalyzeNaturalLoops(); 509 return graph; 510} 511 512TEST(RegisterAllocatorTest, PhiHint) { 513 ArenaPool pool; 514 ArenaAllocator allocator(&pool); 515 HPhi *phi; 516 HInstruction *input1, *input2; 517 518 { 519 HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2); 520 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 521 X86InstructionSetFeatures::FromCppDefines()); 522 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 523 SsaLivenessAnalysis liveness(graph, &codegen); 524 liveness.Analyze(); 525 526 // Check that the register allocator is deterministic. 527 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 528 register_allocator.AllocateRegisters(); 529 530 ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 0); 531 ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 0); 532 ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 0); 533 } 534 535 { 536 HGraph* graph = BuildIfElseWithPhi(&allocator, &phi, &input1, &input2); 537 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 538 X86InstructionSetFeatures::FromCppDefines()); 539 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 540 SsaLivenessAnalysis liveness(graph, &codegen); 541 liveness.Analyze(); 542 543 // Set the phi to a specific register, and check that the inputs get allocated 544 // the same register. 545 phi->GetLocations()->UpdateOut(Location::RegisterLocation(2)); 546 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 547 register_allocator.AllocateRegisters(); 548 549 ASSERT_EQ(input1->GetLiveInterval()->GetRegister(), 2); 550 ASSERT_EQ(input2->GetLiveInterval()->GetRegister(), 2); 551 ASSERT_EQ(phi->GetLiveInterval()->GetRegister(), 2); 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 input1 to a specific register, and check that the phi and other input get allocated 563 // the same register. 564 input1->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 input2 to a specific register, and check that the phi and other input get allocated 582 // the same register. 583 input2->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 593static HGraph* BuildFieldReturn(ArenaAllocator* allocator, 594 HInstruction** field, 595 HInstruction** ret) { 596 HGraph* graph = CreateGraph(allocator); 597 HBasicBlock* entry = new (allocator) HBasicBlock(graph); 598 graph->AddBlock(entry); 599 graph->SetEntryBlock(entry); 600 HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimNot); 601 entry->AddInstruction(parameter); 602 603 HBasicBlock* block = new (allocator) HBasicBlock(graph); 604 graph->AddBlock(block); 605 entry->AddSuccessor(block); 606 607 *field = new (allocator) HInstanceFieldGet(parameter, Primitive::kPrimInt, 608 MemberOffset(42), false); 609 block->AddInstruction(*field); 610 *ret = new (allocator) HReturn(*field); 611 block->AddInstruction(*ret); 612 613 HBasicBlock* exit = new (allocator) HBasicBlock(graph); 614 graph->AddBlock(exit); 615 block->AddSuccessor(exit); 616 exit->AddInstruction(new (allocator) HExit()); 617 618 graph->BuildDominatorTree(); 619 return graph; 620} 621 622TEST(RegisterAllocatorTest, ExpectedInRegisterHint) { 623 ArenaPool pool; 624 ArenaAllocator allocator(&pool); 625 HInstruction *field, *ret; 626 627 { 628 HGraph* graph = BuildFieldReturn(&allocator, &field, &ret); 629 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 630 X86InstructionSetFeatures::FromCppDefines()); 631 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 632 SsaLivenessAnalysis liveness(graph, &codegen); 633 liveness.Analyze(); 634 635 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 636 register_allocator.AllocateRegisters(); 637 638 // Sanity check that in normal conditions, the register should be hinted to 0 (EAX). 639 ASSERT_EQ(field->GetLiveInterval()->GetRegister(), 0); 640 } 641 642 { 643 HGraph* graph = BuildFieldReturn(&allocator, &field, &ret); 644 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 645 X86InstructionSetFeatures::FromCppDefines()); 646 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 647 SsaLivenessAnalysis liveness(graph, &codegen); 648 liveness.Analyze(); 649 650 // Check that the field gets put in the register expected by its use. 651 // Don't use SetInAt because we are overriding an already allocated location. 652 ret->GetLocations()->inputs_.Put(0, Location::RegisterLocation(2)); 653 654 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 655 register_allocator.AllocateRegisters(); 656 657 ASSERT_EQ(field->GetLiveInterval()->GetRegister(), 2); 658 } 659} 660 661static HGraph* BuildTwoSubs(ArenaAllocator* allocator, 662 HInstruction** first_sub, 663 HInstruction** second_sub) { 664 HGraph* graph = CreateGraph(allocator); 665 HBasicBlock* entry = new (allocator) HBasicBlock(graph); 666 graph->AddBlock(entry); 667 graph->SetEntryBlock(entry); 668 HInstruction* parameter = new (allocator) HParameterValue(0, Primitive::kPrimInt); 669 entry->AddInstruction(parameter); 670 671 HInstruction* constant1 = graph->GetIntConstant(1); 672 HInstruction* constant2 = graph->GetIntConstant(2); 673 674 HBasicBlock* block = new (allocator) HBasicBlock(graph); 675 graph->AddBlock(block); 676 entry->AddSuccessor(block); 677 678 *first_sub = new (allocator) HSub(Primitive::kPrimInt, parameter, constant1); 679 block->AddInstruction(*first_sub); 680 *second_sub = new (allocator) HSub(Primitive::kPrimInt, *first_sub, constant2); 681 block->AddInstruction(*second_sub); 682 683 block->AddInstruction(new (allocator) HExit()); 684 685 graph->BuildDominatorTree(); 686 return graph; 687} 688 689TEST(RegisterAllocatorTest, SameAsFirstInputHint) { 690 ArenaPool pool; 691 ArenaAllocator allocator(&pool); 692 HInstruction *first_sub, *second_sub; 693 694 { 695 HGraph* graph = BuildTwoSubs(&allocator, &first_sub, &second_sub); 696 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 697 X86InstructionSetFeatures::FromCppDefines()); 698 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 699 SsaLivenessAnalysis liveness(graph, &codegen); 700 liveness.Analyze(); 701 702 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 703 register_allocator.AllocateRegisters(); 704 705 // Sanity check that in normal conditions, the registers are the same. 706 ASSERT_EQ(first_sub->GetLiveInterval()->GetRegister(), 1); 707 ASSERT_EQ(second_sub->GetLiveInterval()->GetRegister(), 1); 708 } 709 710 { 711 HGraph* graph = BuildTwoSubs(&allocator, &first_sub, &second_sub); 712 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 713 X86InstructionSetFeatures::FromCppDefines()); 714 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 715 SsaLivenessAnalysis liveness(graph, &codegen); 716 liveness.Analyze(); 717 718 // check that both adds get the same register. 719 // Don't use UpdateOutput because output is already allocated. 720 first_sub->InputAt(0)->GetLocations()->output_ = Location::RegisterLocation(2); 721 ASSERT_EQ(first_sub->GetLocations()->Out().GetPolicy(), Location::kSameAsFirstInput); 722 ASSERT_EQ(second_sub->GetLocations()->Out().GetPolicy(), Location::kSameAsFirstInput); 723 724 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 725 register_allocator.AllocateRegisters(); 726 727 ASSERT_EQ(first_sub->GetLiveInterval()->GetRegister(), 2); 728 ASSERT_EQ(second_sub->GetLiveInterval()->GetRegister(), 2); 729 } 730} 731 732static HGraph* BuildDiv(ArenaAllocator* allocator, 733 HInstruction** div) { 734 HGraph* graph = CreateGraph(allocator); 735 HBasicBlock* entry = new (allocator) HBasicBlock(graph); 736 graph->AddBlock(entry); 737 graph->SetEntryBlock(entry); 738 HInstruction* first = new (allocator) HParameterValue(0, Primitive::kPrimInt); 739 HInstruction* second = new (allocator) HParameterValue(0, Primitive::kPrimInt); 740 entry->AddInstruction(first); 741 entry->AddInstruction(second); 742 743 HBasicBlock* block = new (allocator) HBasicBlock(graph); 744 graph->AddBlock(block); 745 entry->AddSuccessor(block); 746 747 *div = new (allocator) HDiv(Primitive::kPrimInt, first, second, 0); // don't care about dex_pc. 748 block->AddInstruction(*div); 749 750 block->AddInstruction(new (allocator) HExit()); 751 752 graph->BuildDominatorTree(); 753 return graph; 754} 755 756TEST(RegisterAllocatorTest, ExpectedExactInRegisterAndSameOutputHint) { 757 ArenaPool pool; 758 ArenaAllocator allocator(&pool); 759 HInstruction *div; 760 761 { 762 HGraph* graph = BuildDiv(&allocator, &div); 763 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 764 X86InstructionSetFeatures::FromCppDefines()); 765 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 766 SsaLivenessAnalysis liveness(graph, &codegen); 767 liveness.Analyze(); 768 769 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 770 register_allocator.AllocateRegisters(); 771 772 // div on x86 requires its first input in eax and the output be the same as the first input. 773 ASSERT_EQ(div->GetLiveInterval()->GetRegister(), 0); 774 } 775} 776 777// Test a bug in the register allocator, where allocating a blocked 778// register would lead to spilling an inactive interval at the wrong 779// position. 780TEST(RegisterAllocatorTest, SpillInactive) { 781 ArenaPool pool; 782 783 // Create a synthesized graph to please the register_allocator and 784 // ssa_liveness_analysis code. 785 ArenaAllocator allocator(&pool); 786 HGraph* graph = CreateGraph(&allocator); 787 HBasicBlock* entry = new (&allocator) HBasicBlock(graph); 788 graph->AddBlock(entry); 789 graph->SetEntryBlock(entry); 790 HInstruction* one = new (&allocator) HParameterValue(0, Primitive::kPrimInt); 791 HInstruction* two = new (&allocator) HParameterValue(0, Primitive::kPrimInt); 792 HInstruction* three = new (&allocator) HParameterValue(0, Primitive::kPrimInt); 793 HInstruction* four = new (&allocator) HParameterValue(0, Primitive::kPrimInt); 794 entry->AddInstruction(one); 795 entry->AddInstruction(two); 796 entry->AddInstruction(three); 797 entry->AddInstruction(four); 798 799 HBasicBlock* block = new (&allocator) HBasicBlock(graph); 800 graph->AddBlock(block); 801 entry->AddSuccessor(block); 802 block->AddInstruction(new (&allocator) HExit()); 803 804 // We create a synthesized user requesting a register, to avoid just spilling the 805 // intervals. 806 HPhi* user = new (&allocator) HPhi(&allocator, 0, 1, Primitive::kPrimInt); 807 user->AddInput(one); 808 user->SetBlock(block); 809 LocationSummary* locations = new (&allocator) LocationSummary(user, LocationSummary::kNoCall); 810 locations->SetInAt(0, Location::RequiresRegister()); 811 static constexpr size_t phi_ranges[][2] = {{20, 30}}; 812 BuildInterval(phi_ranges, arraysize(phi_ranges), &allocator, -1, user); 813 814 // Create an interval with lifetime holes. 815 static constexpr size_t ranges1[][2] = {{0, 2}, {4, 6}, {8, 10}}; 816 LiveInterval* first = BuildInterval(ranges1, arraysize(ranges1), &allocator, -1, one); 817 first->first_use_ = new(&allocator) UsePosition(user, 0, false, 8, first->first_use_); 818 first->first_use_ = new(&allocator) UsePosition(user, 0, false, 7, first->first_use_); 819 first->first_use_ = new(&allocator) UsePosition(user, 0, false, 6, first->first_use_); 820 821 locations = new (&allocator) LocationSummary(first->GetDefinedBy(), LocationSummary::kNoCall); 822 locations->SetOut(Location::RequiresRegister()); 823 first = first->SplitAt(1); 824 825 // Create an interval that conflicts with the next interval, to force the next 826 // interval to call `AllocateBlockedReg`. 827 static constexpr size_t ranges2[][2] = {{2, 4}}; 828 LiveInterval* second = BuildInterval(ranges2, arraysize(ranges2), &allocator, -1, two); 829 locations = new (&allocator) LocationSummary(second->GetDefinedBy(), LocationSummary::kNoCall); 830 locations->SetOut(Location::RequiresRegister()); 831 832 // Create an interval that will lead to splitting the first interval. The bug occured 833 // by splitting at a wrong position, in this case at the next intersection between 834 // this interval and the first interval. We would have then put the interval with ranges 835 // "[0, 2(, [4, 6(" in the list of handled intervals, even though we haven't processed intervals 836 // before lifetime position 6 yet. 837 static constexpr size_t ranges3[][2] = {{2, 4}, {8, 10}}; 838 LiveInterval* third = BuildInterval(ranges3, arraysize(ranges3), &allocator, -1, three); 839 third->first_use_ = new(&allocator) UsePosition(user, 0, false, 8, third->first_use_); 840 third->first_use_ = new(&allocator) UsePosition(user, 0, false, 4, third->first_use_); 841 third->first_use_ = new(&allocator) UsePosition(user, 0, false, 3, third->first_use_); 842 locations = new (&allocator) LocationSummary(third->GetDefinedBy(), LocationSummary::kNoCall); 843 locations->SetOut(Location::RequiresRegister()); 844 third = third->SplitAt(3); 845 846 // Because the first part of the split interval was considered handled, this interval 847 // was free to allocate the same register, even though it conflicts with it. 848 static constexpr size_t ranges4[][2] = {{4, 6}}; 849 LiveInterval* fourth = BuildInterval(ranges4, arraysize(ranges4), &allocator, -1, four); 850 locations = new (&allocator) LocationSummary(fourth->GetDefinedBy(), LocationSummary::kNoCall); 851 locations->SetOut(Location::RequiresRegister()); 852 853 std::unique_ptr<const X86InstructionSetFeatures> features_x86( 854 X86InstructionSetFeatures::FromCppDefines()); 855 x86::CodeGeneratorX86 codegen(graph, *features_x86.get(), CompilerOptions()); 856 SsaLivenessAnalysis liveness(graph, &codegen); 857 // Populate the instructions in the liveness object, to please the register allocator. 858 for (size_t i = 0; i < 32; ++i) { 859 liveness.instructions_from_lifetime_position_.Add(user); 860 } 861 862 RegisterAllocator register_allocator(&allocator, &codegen, liveness); 863 register_allocator.unhandled_core_intervals_.Add(fourth); 864 register_allocator.unhandled_core_intervals_.Add(third); 865 register_allocator.unhandled_core_intervals_.Add(second); 866 register_allocator.unhandled_core_intervals_.Add(first); 867 868 // Set just one register available to make all intervals compete for the same. 869 register_allocator.number_of_registers_ = 1; 870 register_allocator.registers_array_ = allocator.AllocArray<size_t>(1); 871 register_allocator.processing_core_registers_ = true; 872 register_allocator.unhandled_ = ®ister_allocator.unhandled_core_intervals_; 873 register_allocator.LinearScan(); 874 875 // Test that there is no conflicts between intervals. 876 GrowableArray<LiveInterval*> intervals(&allocator, 0); 877 intervals.Add(first); 878 intervals.Add(second); 879 intervals.Add(third); 880 intervals.Add(fourth); 881 ASSERT_TRUE(RegisterAllocator::ValidateIntervals( 882 intervals, 0, 0, codegen, &allocator, true, false)); 883} 884 885} // namespace art 886