register_allocator.cc revision e27f31a81636ad74bd3376ee39cf215941b85c0e
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 "register_allocator.h" 18 19#include "code_generator.h" 20#include "ssa_liveness_analysis.h" 21 22namespace art { 23 24static constexpr size_t kMaxLifetimePosition = -1; 25static constexpr size_t kDefaultNumberOfSpillSlots = 4; 26 27RegisterAllocator::RegisterAllocator(ArenaAllocator* allocator, 28 CodeGenerator* codegen, 29 const SsaLivenessAnalysis& liveness) 30 : allocator_(allocator), 31 codegen_(codegen), 32 liveness_(liveness), 33 unhandled_(allocator, 0), 34 handled_(allocator, 0), 35 active_(allocator, 0), 36 inactive_(allocator, 0), 37 physical_register_intervals_(allocator, codegen->GetNumberOfRegisters()), 38 spill_slots_(allocator, kDefaultNumberOfSpillSlots), 39 processing_core_registers_(false), 40 number_of_registers_(-1), 41 registers_array_(nullptr), 42 blocked_registers_(allocator->AllocArray<bool>(codegen->GetNumberOfRegisters())) { 43 codegen->SetupBlockedRegisters(blocked_registers_); 44 physical_register_intervals_.SetSize(codegen->GetNumberOfRegisters()); 45} 46 47bool RegisterAllocator::CanAllocateRegistersFor(const HGraph& graph, 48 InstructionSet instruction_set) { 49 if (!Supports(instruction_set)) { 50 return false; 51 } 52 for (size_t i = 0, e = graph.GetBlocks().Size(); i < e; ++i) { 53 for (HInstructionIterator it(graph.GetBlocks().Get(i)->GetInstructions()); 54 !it.Done(); 55 it.Advance()) { 56 HInstruction* current = it.Current(); 57 if (current->NeedsEnvironment()) return false; 58 if (current->GetType() == Primitive::kPrimLong) return false; 59 if (current->GetType() == Primitive::kPrimFloat) return false; 60 if (current->GetType() == Primitive::kPrimDouble) return false; 61 } 62 } 63 return true; 64} 65 66static bool ShouldProcess(bool processing_core_registers, LiveInterval* interval) { 67 bool is_core_register = (interval->GetType() != Primitive::kPrimDouble) 68 && (interval->GetType() != Primitive::kPrimFloat); 69 return processing_core_registers == is_core_register; 70} 71 72void RegisterAllocator::AllocateRegisters() { 73 processing_core_registers_ = true; 74 AllocateRegistersInternal(); 75 processing_core_registers_ = false; 76 AllocateRegistersInternal(); 77 78 Resolve(); 79 80 if (kIsDebugBuild) { 81 processing_core_registers_ = true; 82 ValidateInternal(true); 83 processing_core_registers_ = false; 84 ValidateInternal(true); 85 } 86} 87 88void RegisterAllocator::BlockRegister(Location location, 89 size_t start, 90 size_t end, 91 Primitive::Type type) { 92 int reg = location.reg().RegId(); 93 LiveInterval* interval = physical_register_intervals_.Get(reg); 94 if (interval == nullptr) { 95 interval = LiveInterval::MakeFixedInterval(allocator_, reg, type); 96 physical_register_intervals_.Put(reg, interval); 97 inactive_.Add(interval); 98 } 99 DCHECK(interval->GetRegister() == reg); 100 interval->AddRange(start, end); 101} 102 103void RegisterAllocator::AllocateRegistersInternal() { 104 number_of_registers_ = processing_core_registers_ 105 ? codegen_->GetNumberOfCoreRegisters() 106 : codegen_->GetNumberOfFloatingPointRegisters(); 107 108 registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_); 109 110 // Iterate post-order, to ensure the list is sorted, and the last added interval 111 // is the one with the lowest start position. 112 for (size_t i = liveness_.GetNumberOfSsaValues(); i > 0; --i) { 113 HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i - 1); 114 LiveInterval* current = instruction->GetLiveInterval(); 115 if (ShouldProcess(processing_core_registers_, current)) { 116 DCHECK(unhandled_.IsEmpty() || current->StartsBefore(unhandled_.Peek())); 117 118 LocationSummary* locations = instruction->GetLocations(); 119 if (locations->GetTempCount() != 0) { 120 // Note that we already filtered out instructions requiring temporaries in 121 // RegisterAllocator::CanAllocateRegistersFor. 122 LOG(FATAL) << "Unimplemented"; 123 } 124 125 // Some instructions define their output in fixed register/stack slot. We need 126 // to ensure we know these locations before doing register allocation. For a 127 // given register, we create an interval that covers these locations. The register 128 // will be unavailable at these locations when trying to allocate one for an 129 // interval. 130 // 131 // The backwards walking ensures the ranges are ordered on increasing start positions. 132 Location output = locations->Out(); 133 size_t position = instruction->GetLifetimePosition(); 134 if (output.IsRegister()) { 135 // Shift the interval's start by one to account for the blocked register. 136 current->SetFrom(position + 1); 137 current->SetRegister(output.reg().RegId()); 138 BlockRegister(output, position, position + 1, instruction->GetType()); 139 } else if (output.IsStackSlot()) { 140 current->SetSpillSlot(output.GetStackIndex()); 141 } 142 for (size_t i = 0; i < instruction->InputCount(); ++i) { 143 Location input = locations->InAt(i); 144 if (input.IsRegister()) { 145 BlockRegister(input, position, position + 1, instruction->InputAt(i)->GetType()); 146 } 147 } 148 149 // Add the interval to the correct list. 150 if (current->HasRegister()) { 151 DCHECK(instruction->IsParameterValue()); 152 inactive_.Add(current); 153 } else if (current->HasSpillSlot()) { 154 DCHECK(instruction->IsParameterValue()); 155 // Split before first register use. 156 size_t first_register_use = current->FirstRegisterUse(); 157 if (first_register_use != kNoLifetime) { 158 LiveInterval* split = Split(current, first_register_use - 1); 159 // The new interval may start at a late 160 AddToUnhandled(split); 161 } else { 162 // Nothing to do, we won't allocate a register for this value. 163 } 164 } else { 165 DCHECK(unhandled_.IsEmpty() || current->StartsBefore(unhandled_.Peek())); 166 unhandled_.Add(current); 167 } 168 } 169 } 170 171 LinearScan(); 172} 173 174class AllRangesIterator : public ValueObject { 175 public: 176 explicit AllRangesIterator(LiveInterval* interval) 177 : current_interval_(interval), 178 current_range_(interval->GetFirstRange()) {} 179 180 bool Done() const { return current_interval_ == nullptr; } 181 LiveRange* CurrentRange() const { return current_range_; } 182 LiveInterval* CurrentInterval() const { return current_interval_; } 183 184 void Advance() { 185 current_range_ = current_range_->GetNext(); 186 if (current_range_ == nullptr) { 187 current_interval_ = current_interval_->GetNextSibling(); 188 if (current_interval_ != nullptr) { 189 current_range_ = current_interval_->GetFirstRange(); 190 } 191 } 192 } 193 194 private: 195 LiveInterval* current_interval_; 196 LiveRange* current_range_; 197 198 DISALLOW_COPY_AND_ASSIGN(AllRangesIterator); 199}; 200 201bool RegisterAllocator::ValidateInternal(bool log_fatal_on_failure) const { 202 // To simplify unit testing, we eagerly create the array of intervals, and 203 // call the helper method. 204 GrowableArray<LiveInterval*> intervals(allocator_, 0); 205 for (size_t i = 0; i < liveness_.GetNumberOfSsaValues(); ++i) { 206 HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 207 if (ShouldProcess(processing_core_registers_, instruction->GetLiveInterval())) { 208 intervals.Add(instruction->GetLiveInterval()); 209 } 210 } 211 212 for (size_t i = 0, e = physical_register_intervals_.Size(); i < e; ++i) { 213 LiveInterval* fixed = physical_register_intervals_.Get(i); 214 if (fixed != nullptr && ShouldProcess(processing_core_registers_, fixed)) { 215 intervals.Add(fixed); 216 } 217 } 218 219 return ValidateIntervals(intervals, spill_slots_.Size(), *codegen_, allocator_, 220 processing_core_registers_, log_fatal_on_failure); 221} 222 223bool RegisterAllocator::ValidateIntervals(const GrowableArray<LiveInterval*>& intervals, 224 size_t number_of_spill_slots, 225 const CodeGenerator& codegen, 226 ArenaAllocator* allocator, 227 bool processing_core_registers, 228 bool log_fatal_on_failure) { 229 size_t number_of_registers = processing_core_registers 230 ? codegen.GetNumberOfCoreRegisters() 231 : codegen.GetNumberOfFloatingPointRegisters(); 232 GrowableArray<ArenaBitVector*> liveness_of_values( 233 allocator, number_of_registers + number_of_spill_slots); 234 235 // Allocate a bit vector per register. A live interval that has a register 236 // allocated will populate the associated bit vector based on its live ranges. 237 for (size_t i = 0; i < number_of_registers + number_of_spill_slots; ++i) { 238 liveness_of_values.Add(new (allocator) ArenaBitVector(allocator, 0, true)); 239 } 240 241 for (size_t i = 0, e = intervals.Size(); i < e; ++i) { 242 for (AllRangesIterator it(intervals.Get(i)); !it.Done(); it.Advance()) { 243 LiveInterval* current = it.CurrentInterval(); 244 HInstruction* defined_by = current->GetParent()->GetDefinedBy(); 245 if (current->GetParent()->HasSpillSlot() 246 // Parameters have their own stack slot. 247 && !(defined_by != nullptr && defined_by->IsParameterValue())) { 248 BitVector* liveness_of_spill_slot = liveness_of_values.Get( 249 number_of_registers + current->GetParent()->GetSpillSlot() / kVRegSize); 250 for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 251 if (liveness_of_spill_slot->IsBitSet(j)) { 252 if (log_fatal_on_failure) { 253 std::ostringstream message; 254 message << "Spill slot conflict at " << j; 255 LOG(FATAL) << message.str(); 256 } else { 257 return false; 258 } 259 } else { 260 liveness_of_spill_slot->SetBit(j); 261 } 262 } 263 } 264 265 if (current->HasRegister()) { 266 BitVector* liveness_of_register = liveness_of_values.Get(current->GetRegister()); 267 for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 268 if (liveness_of_register->IsBitSet(j)) { 269 if (log_fatal_on_failure) { 270 std::ostringstream message; 271 message << "Register conflict at " << j << " for "; 272 if (processing_core_registers) { 273 codegen.DumpCoreRegister(message, current->GetRegister()); 274 } else { 275 codegen.DumpFloatingPointRegister(message, current->GetRegister()); 276 } 277 LOG(FATAL) << message.str(); 278 } else { 279 return false; 280 } 281 } else { 282 liveness_of_register->SetBit(j); 283 } 284 } 285 } 286 } 287 } 288 return true; 289} 290 291void RegisterAllocator::DumpInterval(std::ostream& stream, LiveInterval* interval) const { 292 interval->Dump(stream); 293 stream << ": "; 294 if (interval->HasRegister()) { 295 if (processing_core_registers_) { 296 codegen_->DumpCoreRegister(stream, interval->GetRegister()); 297 } else { 298 codegen_->DumpFloatingPointRegister(stream, interval->GetRegister()); 299 } 300 } else { 301 stream << "spilled"; 302 } 303 stream << std::endl; 304} 305 306// By the book implementation of a linear scan register allocator. 307void RegisterAllocator::LinearScan() { 308 while (!unhandled_.IsEmpty()) { 309 // (1) Remove interval with the lowest start position from unhandled. 310 LiveInterval* current = unhandled_.Pop(); 311 DCHECK(!current->IsFixed() && !current->HasRegister() && !current->HasSpillSlot()); 312 size_t position = current->GetStart(); 313 314 // (2) Remove currently active intervals that are dead at this position. 315 // Move active intervals that have a lifetime hole at this position 316 // to inactive. 317 for (size_t i = 0; i < active_.Size(); ++i) { 318 LiveInterval* interval = active_.Get(i); 319 if (interval->IsDeadAt(position)) { 320 active_.Delete(interval); 321 --i; 322 handled_.Add(interval); 323 } else if (!interval->Covers(position)) { 324 active_.Delete(interval); 325 --i; 326 inactive_.Add(interval); 327 } 328 } 329 330 // (3) Remove currently inactive intervals that are dead at this position. 331 // Move inactive intervals that cover this position to active. 332 for (size_t i = 0; i < inactive_.Size(); ++i) { 333 LiveInterval* interval = inactive_.Get(i); 334 if (interval->IsDeadAt(position)) { 335 inactive_.Delete(interval); 336 --i; 337 handled_.Add(interval); 338 } else if (interval->Covers(position)) { 339 inactive_.Delete(interval); 340 --i; 341 active_.Add(interval); 342 } 343 } 344 345 // (4) Try to find an available register. 346 bool success = TryAllocateFreeReg(current); 347 348 // (5) If no register could be found, we need to spill. 349 if (!success) { 350 success = AllocateBlockedReg(current); 351 } 352 353 // (6) If the interval had a register allocated, add it to the list of active 354 // intervals. 355 if (success) { 356 active_.Add(current); 357 } 358 } 359} 360 361// Find a free register. If multiple are found, pick the register that 362// is free the longest. 363bool RegisterAllocator::TryAllocateFreeReg(LiveInterval* current) { 364 size_t* free_until = registers_array_; 365 366 // First set all registers to be free. 367 for (size_t i = 0; i < number_of_registers_; ++i) { 368 free_until[i] = kMaxLifetimePosition; 369 } 370 371 // For each inactive interval, set its register to be free until 372 // the next intersection with `current`. 373 // Thanks to SSA, this should only be needed for intervals 374 // that are the result of a split. 375 for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { 376 LiveInterval* inactive = inactive_.Get(i); 377 DCHECK(inactive->HasRegister()); 378 size_t next_intersection = inactive->FirstIntersectionWith(current); 379 if (next_intersection != kNoLifetime) { 380 free_until[inactive->GetRegister()] = next_intersection; 381 } 382 } 383 384 // For each active interval, set its register to not free. 385 for (size_t i = 0, e = active_.Size(); i < e; ++i) { 386 LiveInterval* interval = active_.Get(i); 387 DCHECK(interval->HasRegister()); 388 free_until[interval->GetRegister()] = 0; 389 } 390 391 // Pick the register that is free the longest. 392 int reg = -1; 393 for (size_t i = 0; i < number_of_registers_; ++i) { 394 if (IsBlocked(i)) continue; 395 if (reg == -1 || free_until[i] > free_until[reg]) { 396 reg = i; 397 if (free_until[i] == kMaxLifetimePosition) break; 398 } 399 } 400 401 // If we could not find a register, we need to spill. 402 if (reg == -1 || free_until[reg] == 0) { 403 return false; 404 } 405 406 current->SetRegister(reg); 407 if (!current->IsDeadAt(free_until[reg])) { 408 // If the register is only available for a subset of live ranges 409 // covered by `current`, split `current` at the position where 410 // the register is not available anymore. 411 LiveInterval* split = Split(current, free_until[reg]); 412 DCHECK(split != nullptr); 413 AddToUnhandled(split); 414 } 415 return true; 416} 417 418bool RegisterAllocator::IsBlocked(int reg) const { 419 // TODO: This only works for core registers and needs to be adjusted for 420 // floating point registers. 421 DCHECK(processing_core_registers_); 422 return blocked_registers_[reg]; 423} 424 425// Find the register that is used the last, and spill the interval 426// that holds it. If the first use of `current` is after that register 427// we spill `current` instead. 428bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) { 429 size_t first_register_use = current->FirstRegisterUse(); 430 if (current->FirstRegisterUse() == kNoLifetime) { 431 AllocateSpillSlotFor(current); 432 return false; 433 } 434 435 // First set all registers as not being used. 436 size_t* next_use = registers_array_; 437 for (size_t i = 0; i < number_of_registers_; ++i) { 438 next_use[i] = kMaxLifetimePosition; 439 } 440 441 // For each active interval, find the next use of its register after the 442 // start of current. 443 for (size_t i = 0, e = active_.Size(); i < e; ++i) { 444 LiveInterval* active = active_.Get(i); 445 DCHECK(active->HasRegister()); 446 if (active->IsFixed()) { 447 next_use[active->GetRegister()] = current->GetStart(); 448 } else { 449 size_t use = active->FirstRegisterUseAfter(current->GetStart()); 450 if (use != kNoLifetime) { 451 next_use[active->GetRegister()] = use; 452 } 453 } 454 } 455 456 // For each inactive interval, find the next use of its register after the 457 // start of current. 458 // Thanks to SSA, this should only be needed for intervals 459 // that are the result of a split. 460 for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { 461 LiveInterval* inactive = inactive_.Get(i); 462 DCHECK(inactive->HasRegister()); 463 size_t next_intersection = inactive->FirstIntersectionWith(current); 464 if (next_intersection != kNoLifetime) { 465 if (inactive->IsFixed()) { 466 next_use[inactive->GetRegister()] = 467 std::min(next_intersection, next_use[inactive->GetRegister()]); 468 } else { 469 size_t use = inactive->FirstRegisterUseAfter(current->GetStart()); 470 if (use != kNoLifetime) { 471 next_use[inactive->GetRegister()] = std::min(use, next_use[inactive->GetRegister()]); 472 } 473 } 474 } 475 } 476 477 // Pick the register that is used the last. 478 int reg = -1; 479 for (size_t i = 0; i < number_of_registers_; ++i) { 480 if (IsBlocked(i)) continue; 481 if (reg == -1 || next_use[i] > next_use[reg]) { 482 reg = i; 483 if (next_use[i] == kMaxLifetimePosition) break; 484 } 485 } 486 487 if (first_register_use >= next_use[reg]) { 488 // If the first use of that instruction is after the last use of the found 489 // register, we split this interval just before its first register use. 490 AllocateSpillSlotFor(current); 491 LiveInterval* split = Split(current, first_register_use - 1); 492 AddToUnhandled(split); 493 return false; 494 } else { 495 // Use this register and spill the active and inactives interval that 496 // have that register. 497 current->SetRegister(reg); 498 499 for (size_t i = 0, e = active_.Size(); i < e; ++i) { 500 LiveInterval* active = active_.Get(i); 501 if (active->GetRegister() == reg) { 502 DCHECK(!active->IsFixed()); 503 LiveInterval* split = Split(active, current->GetStart()); 504 active_.DeleteAt(i); 505 handled_.Add(active); 506 AddToUnhandled(split); 507 break; 508 } 509 } 510 511 for (size_t i = 0; i < inactive_.Size(); ++i) { 512 LiveInterval* inactive = inactive_.Get(i); 513 if (inactive->GetRegister() == reg) { 514 size_t next_intersection = inactive->FirstIntersectionWith(current); 515 if (next_intersection != kNoLifetime) { 516 if (inactive->IsFixed()) { 517 LiveInterval* split = Split(current, next_intersection); 518 AddToUnhandled(split); 519 } else { 520 LiveInterval* split = Split(inactive, current->GetStart()); 521 inactive_.DeleteAt(i); 522 handled_.Add(inactive); 523 AddToUnhandled(split); 524 --i; 525 } 526 } 527 } 528 } 529 530 return true; 531 } 532} 533 534void RegisterAllocator::AddToUnhandled(LiveInterval* interval) { 535 size_t insert_at = 0; 536 for (size_t i = unhandled_.Size(); i > 0; --i) { 537 LiveInterval* current = unhandled_.Get(i - 1); 538 if (current->StartsAfter(interval)) { 539 insert_at = i; 540 break; 541 } 542 } 543 unhandled_.InsertAt(insert_at, interval); 544} 545 546LiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) { 547 DCHECK(position >= interval->GetStart()); 548 DCHECK(!interval->IsDeadAt(position)); 549 if (position == interval->GetStart()) { 550 // Spill slot will be allocated when handling `interval` again. 551 interval->ClearRegister(); 552 return interval; 553 } else { 554 LiveInterval* new_interval = interval->SplitAt(position); 555 return new_interval; 556 } 557} 558 559void RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) { 560 LiveInterval* parent = interval->GetParent(); 561 562 // An instruction gets a spill slot for its entire lifetime. If the parent 563 // of this interval already has a spill slot, there is nothing to do. 564 if (parent->HasSpillSlot()) { 565 return; 566 } 567 568 HInstruction* defined_by = parent->GetDefinedBy(); 569 if (defined_by->IsParameterValue()) { 570 // Parameters have their own stack slot. 571 parent->SetSpillSlot(codegen_->GetStackSlotOfParameter(defined_by->AsParameterValue())); 572 return; 573 } 574 575 LiveInterval* last_sibling = interval; 576 while (last_sibling->GetNextSibling() != nullptr) { 577 last_sibling = last_sibling->GetNextSibling(); 578 } 579 size_t end = last_sibling->GetEnd(); 580 581 // Find an available spill slot. 582 size_t slot = 0; 583 for (size_t e = spill_slots_.Size(); slot < e; ++slot) { 584 if (spill_slots_.Get(slot) <= parent->GetStart()) { 585 break; 586 } 587 } 588 589 if (slot == spill_slots_.Size()) { 590 // We need a new spill slot. 591 spill_slots_.Add(end); 592 } else { 593 spill_slots_.Put(slot, end); 594 } 595 596 parent->SetSpillSlot(slot * kVRegSize); 597} 598 599static Location ConvertToLocation(LiveInterval* interval) { 600 if (interval->HasRegister()) { 601 return Location::RegisterLocation(ManagedRegister(interval->GetRegister())); 602 } else { 603 DCHECK(interval->GetParent()->HasSpillSlot()); 604 return Location::StackSlot(interval->GetParent()->GetSpillSlot()); 605 } 606} 607 608// We create a special marker for inputs moves to differentiate them from 609// moves created during resolution. They must be different instructions 610// because the input moves work on the assumption that the interval moves 611// have been executed. 612static constexpr size_t kInputMoveLifetimePosition = 0; 613static bool IsInputMove(HInstruction* instruction) { 614 return instruction->GetLifetimePosition() == kInputMoveLifetimePosition; 615} 616 617void RegisterAllocator::AddInputMoveFor(HInstruction* instruction, 618 Location source, 619 Location destination) const { 620 if (source.Equals(destination)) return; 621 622 DCHECK(instruction->AsPhi() == nullptr); 623 624 HInstruction* previous = instruction->GetPrevious(); 625 HParallelMove* move = nullptr; 626 if (previous == nullptr 627 || previous->AsParallelMove() == nullptr 628 || !IsInputMove(previous)) { 629 move = new (allocator_) HParallelMove(allocator_); 630 move->SetLifetimePosition(kInputMoveLifetimePosition); 631 instruction->GetBlock()->InsertInstructionBefore(move, instruction); 632 } else { 633 move = previous->AsParallelMove(); 634 } 635 DCHECK(IsInputMove(move)); 636 move->AddMove(new (allocator_) MoveOperands(source, destination)); 637} 638 639void RegisterAllocator::InsertParallelMoveAt(size_t position, 640 Location source, 641 Location destination) const { 642 if (source.Equals(destination)) return; 643 644 HInstruction* at = liveness_.GetInstructionFromPosition(position / 2); 645 if (at == nullptr) { 646 // Block boundary, don't no anything the connection of split siblings will handle it. 647 return; 648 } 649 HParallelMove* move; 650 if ((position & 1) == 1) { 651 // Move must happen after the instruction. 652 DCHECK(!at->IsControlFlow()); 653 move = at->GetNext()->AsParallelMove(); 654 // This is a parallel move for connecting siblings in a same block. We need to 655 // differentiate it with moves for connecting blocks, and input moves. 656 if (move == nullptr || move->GetLifetimePosition() != position) { 657 move = new (allocator_) HParallelMove(allocator_); 658 move->SetLifetimePosition(position); 659 at->GetBlock()->InsertInstructionBefore(move, at->GetNext()); 660 } 661 } else { 662 // Move must happen before the instruction. 663 HInstruction* previous = at->GetPrevious(); 664 if (previous != nullptr && previous->AsParallelMove() != nullptr) { 665 // This is a parallel move for connecting siblings in a same block. We need to 666 // differentiate it with moves for connecting blocks, and input moves. 667 if (previous->GetLifetimePosition() != position) { 668 previous = previous->GetPrevious(); 669 } 670 } 671 if (previous == nullptr || previous->AsParallelMove() == nullptr) { 672 move = new (allocator_) HParallelMove(allocator_); 673 move->SetLifetimePosition(position); 674 at->GetBlock()->InsertInstructionBefore(move, at); 675 } else { 676 move = previous->AsParallelMove(); 677 } 678 } 679 move->AddMove(new (allocator_) MoveOperands(source, destination)); 680} 681 682void RegisterAllocator::InsertParallelMoveAtExitOf(HBasicBlock* block, 683 Location source, 684 Location destination) const { 685 if (source.Equals(destination)) return; 686 687 DCHECK_EQ(block->GetSuccessors().Size(), 1u); 688 HInstruction* last = block->GetLastInstruction(); 689 HInstruction* previous = last->GetPrevious(); 690 HParallelMove* move; 691 // This is a parallel move for connecting blocks. We need to differentiate 692 // it with moves for connecting siblings in a same block, and output moves. 693 if (previous == nullptr || previous->AsParallelMove() == nullptr 694 || previous->AsParallelMove()->GetLifetimePosition() != block->GetLifetimeEnd()) { 695 move = new (allocator_) HParallelMove(allocator_); 696 move->SetLifetimePosition(block->GetLifetimeEnd()); 697 block->InsertInstructionBefore(move, last); 698 } else { 699 move = previous->AsParallelMove(); 700 } 701 move->AddMove(new (allocator_) MoveOperands(source, destination)); 702} 703 704void RegisterAllocator::InsertParallelMoveAtEntryOf(HBasicBlock* block, 705 Location source, 706 Location destination) const { 707 if (source.Equals(destination)) return; 708 709 HInstruction* first = block->GetFirstInstruction(); 710 HParallelMove* move = first->AsParallelMove(); 711 // This is a parallel move for connecting blocks. We need to differentiate 712 // it with moves for connecting siblings in a same block, and input moves. 713 if (move == nullptr || move->GetLifetimePosition() != block->GetLifetimeStart()) { 714 move = new (allocator_) HParallelMove(allocator_); 715 move->SetLifetimePosition(block->GetLifetimeStart()); 716 block->InsertInstructionBefore(move, first); 717 } 718 move->AddMove(new (allocator_) MoveOperands(source, destination)); 719} 720 721void RegisterAllocator::InsertMoveAfter(HInstruction* instruction, 722 Location source, 723 Location destination) const { 724 if (source.Equals(destination)) return; 725 726 if (instruction->AsPhi() != nullptr) { 727 InsertParallelMoveAtEntryOf(instruction->GetBlock(), source, destination); 728 return; 729 } 730 731 size_t position = instruction->GetLifetimePosition() + 1; 732 HParallelMove* move = instruction->GetNext()->AsParallelMove(); 733 // This is a parallel move for moving the output of an instruction. We need 734 // to differentiate with input moves, moves for connecting siblings in a 735 // and moves for connecting blocks. 736 if (move == nullptr || move->GetLifetimePosition() != position) { 737 move = new (allocator_) HParallelMove(allocator_); 738 move->SetLifetimePosition(position); 739 instruction->GetBlock()->InsertInstructionBefore(move, instruction->GetNext()); 740 } 741 move->AddMove(new (allocator_) MoveOperands(source, destination)); 742} 743 744void RegisterAllocator::ConnectSiblings(LiveInterval* interval) { 745 LiveInterval* current = interval; 746 if (current->HasSpillSlot() && current->HasRegister()) { 747 // We spill eagerly, so move must be at definition. 748 InsertMoveAfter(interval->GetDefinedBy(), 749 Location::RegisterLocation(ManagedRegister(interval->GetRegister())), 750 Location::StackSlot(interval->GetParent()->GetSpillSlot())); 751 } 752 UsePosition* use = current->GetFirstUse(); 753 754 // Walk over all siblings, updating locations of use positions, and 755 // connecting them when they are adjacent. 756 do { 757 Location source = ConvertToLocation(current); 758 759 // Walk over all uses covered by this interval, and update the location 760 // information. 761 while (use != nullptr && use->GetPosition() <= current->GetEnd()) { 762 if (!use->GetIsEnvironment()) { 763 LocationSummary* locations = use->GetUser()->GetLocations(); 764 Location expected_location = locations->InAt(use->GetInputIndex()); 765 if (expected_location.IsUnallocated()) { 766 locations->SetInAt(use->GetInputIndex(), source); 767 } else { 768 AddInputMoveFor(use->GetUser(), source, expected_location); 769 } 770 } 771 use = use->GetNext(); 772 } 773 774 // If the next interval starts just after this one, and has a register, 775 // insert a move. 776 LiveInterval* next_sibling = current->GetNextSibling(); 777 if (next_sibling != nullptr 778 && next_sibling->HasRegister() 779 && current->GetEnd() == next_sibling->GetStart()) { 780 Location destination = ConvertToLocation(next_sibling); 781 InsertParallelMoveAt(current->GetEnd(), source, destination); 782 } 783 current = next_sibling; 784 } while (current != nullptr); 785 DCHECK(use == nullptr); 786} 787 788void RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval, 789 HBasicBlock* from, 790 HBasicBlock* to) const { 791 if (interval->GetNextSibling() == nullptr) { 792 // Nothing to connect. The whole range was allocated to the same location. 793 return; 794 } 795 796 size_t from_position = from->GetLifetimeEnd() - 1; 797 size_t to_position = to->GetLifetimeStart(); 798 799 LiveInterval* destination = nullptr; 800 LiveInterval* source = nullptr; 801 802 LiveInterval* current = interval; 803 804 // Check the intervals that cover `from` and `to`. 805 while ((current != nullptr) && (source == nullptr || destination == nullptr)) { 806 if (current->Covers(from_position)) { 807 DCHECK(source == nullptr); 808 source = current; 809 } 810 if (current->Covers(to_position)) { 811 DCHECK(destination == nullptr); 812 destination = current; 813 } 814 815 current = current->GetNextSibling(); 816 } 817 818 if (destination == source) { 819 // Interval was not split. 820 return; 821 } 822 823 if (!destination->HasRegister()) { 824 // Values are eagerly spilled. Spill slot already contains appropriate value. 825 return; 826 } 827 828 // If `from` has only one successor, we can put the moves at the exit of it. Otherwise 829 // we need to put the moves at the entry of `to`. 830 if (from->GetSuccessors().Size() == 1) { 831 InsertParallelMoveAtExitOf(from, ConvertToLocation(source), ConvertToLocation(destination)); 832 } else { 833 DCHECK_EQ(to->GetPredecessors().Size(), 1u); 834 InsertParallelMoveAtEntryOf(to, ConvertToLocation(source), ConvertToLocation(destination)); 835 } 836} 837 838// Returns the location of `interval`, or siblings of `interval`, at `position`. 839static Location FindLocationAt(LiveInterval* interval, size_t position) { 840 LiveInterval* current = interval; 841 while (!current->Covers(position)) { 842 current = current->GetNextSibling(); 843 DCHECK(current != nullptr); 844 } 845 return ConvertToLocation(current); 846} 847 848void RegisterAllocator::Resolve() { 849 codegen_->ComputeFrameSize(spill_slots_.Size()); 850 851 // Adjust the Out Location of instructions. 852 // TODO: Use pointers of Location inside LiveInterval to avoid doing another iteration. 853 for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { 854 HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 855 LiveInterval* current = instruction->GetLiveInterval(); 856 LocationSummary* locations = instruction->GetLocations(); 857 Location location = locations->Out(); 858 if (instruction->AsParameterValue() != nullptr) { 859 // Now that we know the frame size, adjust the parameter's location. 860 if (location.IsStackSlot()) { 861 location = Location::StackSlot(location.GetStackIndex() + codegen_->GetFrameSize()); 862 current->SetSpillSlot(location.GetStackIndex()); 863 locations->SetOut(location); 864 } else if (location.IsDoubleStackSlot()) { 865 location = Location::DoubleStackSlot(location.GetStackIndex() + codegen_->GetFrameSize()); 866 current->SetSpillSlot(location.GetStackIndex()); 867 locations->SetOut(location); 868 } else if (current->HasSpillSlot()) { 869 current->SetSpillSlot(current->GetSpillSlot() + codegen_->GetFrameSize()); 870 } 871 } 872 873 Location source = ConvertToLocation(current); 874 875 if (location.IsUnallocated()) { 876 if (location.GetPolicy() == Location::kSameAsFirstInput) { 877 locations->SetInAt(0, source); 878 } 879 locations->SetOut(source); 880 } else { 881 DCHECK(source.Equals(location)); 882 } 883 } 884 885 // Connect siblings. 886 for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { 887 HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 888 ConnectSiblings(instruction->GetLiveInterval()); 889 } 890 891 // Resolve non-linear control flow across branches. Order does not matter. 892 for (HLinearOrderIterator it(liveness_); !it.Done(); it.Advance()) { 893 HBasicBlock* block = it.Current(); 894 BitVector* live = liveness_.GetLiveInSet(*block); 895 for (uint32_t idx : live->Indexes()) { 896 HInstruction* current = liveness_.GetInstructionFromSsaIndex(idx); 897 LiveInterval* interval = current->GetLiveInterval(); 898 for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { 899 ConnectSplitSiblings(interval, block->GetPredecessors().Get(i), block); 900 } 901 } 902 } 903 904 // Resolve phi inputs. Order does not matter. 905 for (HLinearOrderIterator it(liveness_); !it.Done(); it.Advance()) { 906 HBasicBlock* current = it.Current(); 907 for (HInstructionIterator it(current->GetPhis()); !it.Done(); it.Advance()) { 908 HInstruction* phi = it.Current(); 909 for (size_t i = 0, e = current->GetPredecessors().Size(); i < e; ++i) { 910 HBasicBlock* predecessor = current->GetPredecessors().Get(i); 911 DCHECK_EQ(predecessor->GetSuccessors().Size(), 1u); 912 HInstruction* input = phi->InputAt(i); 913 Location source = FindLocationAt(input->GetLiveInterval(), 914 predecessor->GetLastInstruction()->GetLifetimePosition()); 915 Location destination = ConvertToLocation(phi->GetLiveInterval()); 916 InsertParallelMoveAtExitOf(predecessor, source, destination); 917 } 918 } 919 } 920} 921 922} // namespace art 923