register_allocator.cc revision b95fb775cc4c08349d0d905adbc96ad85e50601d
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 <iostream> 20#include <sstream> 21 22#include "base/bit_vector-inl.h" 23#include "code_generator.h" 24#include "ssa_liveness_analysis.h" 25 26namespace art { 27 28static constexpr size_t kMaxLifetimePosition = -1; 29static constexpr size_t kDefaultNumberOfSpillSlots = 4; 30 31// For simplicity, we implement register pairs as (reg, reg + 1). 32// Note that this is a requirement for double registers on ARM, since we 33// allocate SRegister. 34static int GetHighForLowRegister(int reg) { return reg + 1; } 35static bool IsLowRegister(int reg) { return (reg & 1) == 0; } 36static bool IsLowOfUnalignedPairInterval(LiveInterval* low) { 37 return GetHighForLowRegister(low->GetRegister()) != low->GetHighInterval()->GetRegister(); 38} 39 40RegisterAllocator::RegisterAllocator(ArenaAllocator* allocator, 41 CodeGenerator* codegen, 42 const SsaLivenessAnalysis& liveness) 43 : allocator_(allocator), 44 codegen_(codegen), 45 liveness_(liveness), 46 unhandled_core_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), 47 unhandled_fp_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), 48 unhandled_(nullptr), 49 handled_(allocator->Adapter(kArenaAllocRegisterAllocator)), 50 active_(allocator->Adapter(kArenaAllocRegisterAllocator)), 51 inactive_(allocator->Adapter(kArenaAllocRegisterAllocator)), 52 physical_core_register_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), 53 physical_fp_register_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), 54 temp_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), 55 int_spill_slots_(allocator->Adapter(kArenaAllocRegisterAllocator)), 56 long_spill_slots_(allocator->Adapter(kArenaAllocRegisterAllocator)), 57 float_spill_slots_(allocator->Adapter(kArenaAllocRegisterAllocator)), 58 double_spill_slots_(allocator->Adapter(kArenaAllocRegisterAllocator)), 59 catch_phi_spill_slots_(0), 60 safepoints_(allocator->Adapter(kArenaAllocRegisterAllocator)), 61 processing_core_registers_(false), 62 number_of_registers_(-1), 63 registers_array_(nullptr), 64 blocked_core_registers_(codegen->GetBlockedCoreRegisters()), 65 blocked_fp_registers_(codegen->GetBlockedFloatingPointRegisters()), 66 reserved_out_slots_(0), 67 maximum_number_of_live_core_registers_(0), 68 maximum_number_of_live_fp_registers_(0) { 69 temp_intervals_.reserve(4); 70 int_spill_slots_.reserve(kDefaultNumberOfSpillSlots); 71 long_spill_slots_.reserve(kDefaultNumberOfSpillSlots); 72 float_spill_slots_.reserve(kDefaultNumberOfSpillSlots); 73 double_spill_slots_.reserve(kDefaultNumberOfSpillSlots); 74 75 static constexpr bool kIsBaseline = false; 76 codegen->SetupBlockedRegisters(kIsBaseline); 77 physical_core_register_intervals_.resize(codegen->GetNumberOfCoreRegisters(), nullptr); 78 physical_fp_register_intervals_.resize(codegen->GetNumberOfFloatingPointRegisters(), nullptr); 79 // Always reserve for the current method and the graph's max out registers. 80 // TODO: compute it instead. 81 // ArtMethod* takes 2 vregs for 64 bits. 82 reserved_out_slots_ = InstructionSetPointerSize(codegen->GetInstructionSet()) / kVRegSize + 83 codegen->GetGraph()->GetMaximumNumberOfOutVRegs(); 84} 85 86bool RegisterAllocator::CanAllocateRegistersFor(const HGraph& graph ATTRIBUTE_UNUSED, 87 InstructionSet instruction_set) { 88 return instruction_set == kArm64 89 || instruction_set == kX86_64 90 || instruction_set == kMips64 91 || instruction_set == kArm 92 || instruction_set == kX86 93 || instruction_set == kThumb2; 94} 95 96static bool ShouldProcess(bool processing_core_registers, LiveInterval* interval) { 97 if (interval == nullptr) return false; 98 bool is_core_register = (interval->GetType() != Primitive::kPrimDouble) 99 && (interval->GetType() != Primitive::kPrimFloat); 100 return processing_core_registers == is_core_register; 101} 102 103void RegisterAllocator::AllocateRegisters() { 104 AllocateRegistersInternal(); 105 Resolve(); 106 107 if (kIsDebugBuild) { 108 processing_core_registers_ = true; 109 ValidateInternal(true); 110 processing_core_registers_ = false; 111 ValidateInternal(true); 112 // Check that the linear order is still correct with regards to lifetime positions. 113 // Since only parallel moves have been inserted during the register allocation, 114 // these checks are mostly for making sure these moves have been added correctly. 115 size_t current_liveness = 0; 116 for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { 117 HBasicBlock* block = it.Current(); 118 for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 119 HInstruction* instruction = inst_it.Current(); 120 DCHECK_LE(current_liveness, instruction->GetLifetimePosition()); 121 current_liveness = instruction->GetLifetimePosition(); 122 } 123 for (HInstructionIterator inst_it(block->GetInstructions()); 124 !inst_it.Done(); 125 inst_it.Advance()) { 126 HInstruction* instruction = inst_it.Current(); 127 DCHECK_LE(current_liveness, instruction->GetLifetimePosition()) << instruction->DebugName(); 128 current_liveness = instruction->GetLifetimePosition(); 129 } 130 } 131 } 132} 133 134void RegisterAllocator::BlockRegister(Location location, size_t start, size_t end) { 135 int reg = location.reg(); 136 DCHECK(location.IsRegister() || location.IsFpuRegister()); 137 LiveInterval* interval = location.IsRegister() 138 ? physical_core_register_intervals_[reg] 139 : physical_fp_register_intervals_[reg]; 140 Primitive::Type type = location.IsRegister() 141 ? Primitive::kPrimInt 142 : Primitive::kPrimFloat; 143 if (interval == nullptr) { 144 interval = LiveInterval::MakeFixedInterval(allocator_, reg, type); 145 if (location.IsRegister()) { 146 physical_core_register_intervals_[reg] = interval; 147 } else { 148 physical_fp_register_intervals_[reg] = interval; 149 } 150 } 151 DCHECK(interval->GetRegister() == reg); 152 interval->AddRange(start, end); 153} 154 155void RegisterAllocator::BlockRegisters(size_t start, size_t end, bool caller_save_only) { 156 for (size_t i = 0; i < codegen_->GetNumberOfCoreRegisters(); ++i) { 157 if (!caller_save_only || !codegen_->IsCoreCalleeSaveRegister(i)) { 158 BlockRegister(Location::RegisterLocation(i), start, end); 159 } 160 } 161 for (size_t i = 0; i < codegen_->GetNumberOfFloatingPointRegisters(); ++i) { 162 if (!caller_save_only || !codegen_->IsFloatingPointCalleeSaveRegister(i)) { 163 BlockRegister(Location::FpuRegisterLocation(i), start, end); 164 } 165 } 166} 167 168void RegisterAllocator::AllocateRegistersInternal() { 169 // Iterate post-order, to ensure the list is sorted, and the last added interval 170 // is the one with the lowest start position. 171 for (HLinearPostOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { 172 HBasicBlock* block = it.Current(); 173 for (HBackwardInstructionIterator back_it(block->GetInstructions()); !back_it.Done(); 174 back_it.Advance()) { 175 ProcessInstruction(back_it.Current()); 176 } 177 for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 178 ProcessInstruction(inst_it.Current()); 179 } 180 181 if (block->IsCatchBlock()) { 182 // By blocking all registers at the top of each catch block, we force 183 // intervals used after catch to spill. 184 size_t position = block->GetLifetimeStart(); 185 BlockRegisters(position, position + 1); 186 } 187 } 188 189 number_of_registers_ = codegen_->GetNumberOfCoreRegisters(); 190 registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_, 191 kArenaAllocRegisterAllocator); 192 processing_core_registers_ = true; 193 unhandled_ = &unhandled_core_intervals_; 194 for (LiveInterval* fixed : physical_core_register_intervals_) { 195 if (fixed != nullptr) { 196 // Fixed interval is added to inactive_ instead of unhandled_. 197 // It's also the only type of inactive interval whose start position 198 // can be after the current interval during linear scan. 199 // Fixed interval is never split and never moves to unhandled_. 200 inactive_.push_back(fixed); 201 } 202 } 203 LinearScan(); 204 205 inactive_.clear(); 206 active_.clear(); 207 handled_.clear(); 208 209 number_of_registers_ = codegen_->GetNumberOfFloatingPointRegisters(); 210 registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_, 211 kArenaAllocRegisterAllocator); 212 processing_core_registers_ = false; 213 unhandled_ = &unhandled_fp_intervals_; 214 for (LiveInterval* fixed : physical_fp_register_intervals_) { 215 if (fixed != nullptr) { 216 // Fixed interval is added to inactive_ instead of unhandled_. 217 // It's also the only type of inactive interval whose start position 218 // can be after the current interval during linear scan. 219 // Fixed interval is never split and never moves to unhandled_. 220 inactive_.push_back(fixed); 221 } 222 } 223 LinearScan(); 224} 225 226void RegisterAllocator::ProcessInstruction(HInstruction* instruction) { 227 LocationSummary* locations = instruction->GetLocations(); 228 size_t position = instruction->GetLifetimePosition(); 229 230 if (locations == nullptr) return; 231 232 // Create synthesized intervals for temporaries. 233 for (size_t i = 0; i < locations->GetTempCount(); ++i) { 234 Location temp = locations->GetTemp(i); 235 if (temp.IsRegister() || temp.IsFpuRegister()) { 236 BlockRegister(temp, position, position + 1); 237 // Ensure that an explicit temporary register is marked as being allocated. 238 codegen_->AddAllocatedRegister(temp); 239 } else { 240 DCHECK(temp.IsUnallocated()); 241 switch (temp.GetPolicy()) { 242 case Location::kRequiresRegister: { 243 LiveInterval* interval = 244 LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimInt); 245 temp_intervals_.push_back(interval); 246 interval->AddTempUse(instruction, i); 247 unhandled_core_intervals_.push_back(interval); 248 break; 249 } 250 251 case Location::kRequiresFpuRegister: { 252 LiveInterval* interval = 253 LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimDouble); 254 temp_intervals_.push_back(interval); 255 interval->AddTempUse(instruction, i); 256 if (codegen_->NeedsTwoRegisters(Primitive::kPrimDouble)) { 257 interval->AddHighInterval(/* is_temp */ true); 258 LiveInterval* high = interval->GetHighInterval(); 259 temp_intervals_.push_back(high); 260 unhandled_fp_intervals_.push_back(high); 261 } 262 unhandled_fp_intervals_.push_back(interval); 263 break; 264 } 265 266 default: 267 LOG(FATAL) << "Unexpected policy for temporary location " 268 << temp.GetPolicy(); 269 } 270 } 271 } 272 273 bool core_register = (instruction->GetType() != Primitive::kPrimDouble) 274 && (instruction->GetType() != Primitive::kPrimFloat); 275 276 if (locations->NeedsSafepoint()) { 277 if (codegen_->IsLeafMethod()) { 278 // TODO: We do this here because we do not want the suspend check to artificially 279 // create live registers. We should find another place, but this is currently the 280 // simplest. 281 DCHECK(instruction->IsSuspendCheckEntry()); 282 instruction->GetBlock()->RemoveInstruction(instruction); 283 return; 284 } 285 safepoints_.push_back(instruction); 286 if (locations->OnlyCallsOnSlowPath()) { 287 // We add a synthesized range at this position to record the live registers 288 // at this position. Ideally, we could just update the safepoints when locations 289 // are updated, but we currently need to know the full stack size before updating 290 // locations (because of parameters and the fact that we don't have a frame pointer). 291 // And knowing the full stack size requires to know the maximum number of live 292 // registers at calls in slow paths. 293 // By adding the following interval in the algorithm, we can compute this 294 // maximum before updating locations. 295 LiveInterval* interval = LiveInterval::MakeSlowPathInterval(allocator_, instruction); 296 interval->AddRange(position, position + 1); 297 AddSorted(&unhandled_core_intervals_, interval); 298 AddSorted(&unhandled_fp_intervals_, interval); 299 } 300 } 301 302 if (locations->WillCall()) { 303 BlockRegisters(position, position + 1, /* caller_save_only */ true); 304 } 305 306 for (size_t i = 0; i < instruction->InputCount(); ++i) { 307 Location input = locations->InAt(i); 308 if (input.IsRegister() || input.IsFpuRegister()) { 309 BlockRegister(input, position, position + 1); 310 } else if (input.IsPair()) { 311 BlockRegister(input.ToLow(), position, position + 1); 312 BlockRegister(input.ToHigh(), position, position + 1); 313 } 314 } 315 316 LiveInterval* current = instruction->GetLiveInterval(); 317 if (current == nullptr) return; 318 319 ArenaVector<LiveInterval*>& unhandled = core_register 320 ? unhandled_core_intervals_ 321 : unhandled_fp_intervals_; 322 323 DCHECK(unhandled.empty() || current->StartsBeforeOrAt(unhandled.back())); 324 325 if (codegen_->NeedsTwoRegisters(current->GetType())) { 326 current->AddHighInterval(); 327 } 328 329 for (size_t safepoint_index = safepoints_.size(); safepoint_index > 0; --safepoint_index) { 330 HInstruction* safepoint = safepoints_[safepoint_index - 1u]; 331 size_t safepoint_position = safepoint->GetLifetimePosition(); 332 333 // Test that safepoints are ordered in the optimal way. 334 DCHECK(safepoint_index == safepoints_.size() || 335 safepoints_[safepoint_index]->GetLifetimePosition() < safepoint_position); 336 337 if (safepoint_position == current->GetStart()) { 338 // The safepoint is for this instruction, so the location of the instruction 339 // does not need to be saved. 340 DCHECK_EQ(safepoint_index, safepoints_.size()); 341 DCHECK_EQ(safepoint, instruction); 342 continue; 343 } else if (current->IsDeadAt(safepoint_position)) { 344 break; 345 } else if (!current->Covers(safepoint_position)) { 346 // Hole in the interval. 347 continue; 348 } 349 current->AddSafepoint(safepoint); 350 } 351 current->ResetSearchCache(); 352 353 // Some instructions define their output in fixed register/stack slot. We need 354 // to ensure we know these locations before doing register allocation. For a 355 // given register, we create an interval that covers these locations. The register 356 // will be unavailable at these locations when trying to allocate one for an 357 // interval. 358 // 359 // The backwards walking ensures the ranges are ordered on increasing start positions. 360 Location output = locations->Out(); 361 if (output.IsUnallocated() && output.GetPolicy() == Location::kSameAsFirstInput) { 362 Location first = locations->InAt(0); 363 if (first.IsRegister() || first.IsFpuRegister()) { 364 current->SetFrom(position + 1); 365 current->SetRegister(first.reg()); 366 } else if (first.IsPair()) { 367 current->SetFrom(position + 1); 368 current->SetRegister(first.low()); 369 LiveInterval* high = current->GetHighInterval(); 370 high->SetRegister(first.high()); 371 high->SetFrom(position + 1); 372 } 373 } else if (output.IsRegister() || output.IsFpuRegister()) { 374 // Shift the interval's start by one to account for the blocked register. 375 current->SetFrom(position + 1); 376 current->SetRegister(output.reg()); 377 BlockRegister(output, position, position + 1); 378 } else if (output.IsPair()) { 379 current->SetFrom(position + 1); 380 current->SetRegister(output.low()); 381 LiveInterval* high = current->GetHighInterval(); 382 high->SetRegister(output.high()); 383 high->SetFrom(position + 1); 384 BlockRegister(output.ToLow(), position, position + 1); 385 BlockRegister(output.ToHigh(), position, position + 1); 386 } else if (output.IsStackSlot() || output.IsDoubleStackSlot()) { 387 current->SetSpillSlot(output.GetStackIndex()); 388 } else { 389 DCHECK(output.IsUnallocated() || output.IsConstant()); 390 } 391 392 if (instruction->IsPhi() && instruction->AsPhi()->IsCatchPhi()) { 393 AllocateSpillSlotForCatchPhi(instruction->AsPhi()); 394 } 395 396 // If needed, add interval to the list of unhandled intervals. 397 if (current->HasSpillSlot() || instruction->IsConstant()) { 398 // Split just before first register use. 399 size_t first_register_use = current->FirstRegisterUse(); 400 if (first_register_use != kNoLifetime) { 401 LiveInterval* split = SplitBetween(current, current->GetStart(), first_register_use - 1); 402 // Don't add directly to `unhandled`, it needs to be sorted and the start 403 // of this new interval might be after intervals already in the list. 404 AddSorted(&unhandled, split); 405 } else { 406 // Nothing to do, we won't allocate a register for this value. 407 } 408 } else { 409 // Don't add directly to `unhandled`, temp or safepoint intervals 410 // for this instruction may have been added, and those can be 411 // processed first. 412 AddSorted(&unhandled, current); 413 } 414} 415 416class AllRangesIterator : public ValueObject { 417 public: 418 explicit AllRangesIterator(LiveInterval* interval) 419 : current_interval_(interval), 420 current_range_(interval->GetFirstRange()) {} 421 422 bool Done() const { return current_interval_ == nullptr; } 423 LiveRange* CurrentRange() const { return current_range_; } 424 LiveInterval* CurrentInterval() const { return current_interval_; } 425 426 void Advance() { 427 current_range_ = current_range_->GetNext(); 428 if (current_range_ == nullptr) { 429 current_interval_ = current_interval_->GetNextSibling(); 430 if (current_interval_ != nullptr) { 431 current_range_ = current_interval_->GetFirstRange(); 432 } 433 } 434 } 435 436 private: 437 LiveInterval* current_interval_; 438 LiveRange* current_range_; 439 440 DISALLOW_COPY_AND_ASSIGN(AllRangesIterator); 441}; 442 443bool RegisterAllocator::ValidateInternal(bool log_fatal_on_failure) const { 444 // To simplify unit testing, we eagerly create the array of intervals, and 445 // call the helper method. 446 ArenaVector<LiveInterval*> intervals(allocator_->Adapter(kArenaAllocRegisterAllocator)); 447 for (size_t i = 0; i < liveness_.GetNumberOfSsaValues(); ++i) { 448 HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 449 if (ShouldProcess(processing_core_registers_, instruction->GetLiveInterval())) { 450 intervals.push_back(instruction->GetLiveInterval()); 451 } 452 } 453 454 const ArenaVector<LiveInterval*>* physical_register_intervals = processing_core_registers_ 455 ? &physical_core_register_intervals_ 456 : &physical_fp_register_intervals_; 457 for (LiveInterval* fixed : *physical_register_intervals) { 458 if (fixed != nullptr) { 459 intervals.push_back(fixed); 460 } 461 } 462 463 for (LiveInterval* temp : temp_intervals_) { 464 if (ShouldProcess(processing_core_registers_, temp)) { 465 intervals.push_back(temp); 466 } 467 } 468 469 return ValidateIntervals(intervals, GetNumberOfSpillSlots(), reserved_out_slots_, *codegen_, 470 allocator_, processing_core_registers_, log_fatal_on_failure); 471} 472 473bool RegisterAllocator::ValidateIntervals(const ArenaVector<LiveInterval*>& intervals, 474 size_t number_of_spill_slots, 475 size_t number_of_out_slots, 476 const CodeGenerator& codegen, 477 ArenaAllocator* allocator, 478 bool processing_core_registers, 479 bool log_fatal_on_failure) { 480 size_t number_of_registers = processing_core_registers 481 ? codegen.GetNumberOfCoreRegisters() 482 : codegen.GetNumberOfFloatingPointRegisters(); 483 ArenaVector<ArenaBitVector*> liveness_of_values( 484 allocator->Adapter(kArenaAllocRegisterAllocator)); 485 liveness_of_values.reserve(number_of_registers + number_of_spill_slots); 486 487 // Allocate a bit vector per register. A live interval that has a register 488 // allocated will populate the associated bit vector based on its live ranges. 489 for (size_t i = 0; i < number_of_registers + number_of_spill_slots; ++i) { 490 liveness_of_values.push_back(new (allocator) ArenaBitVector(allocator, 0, true)); 491 } 492 493 for (LiveInterval* start_interval : intervals) { 494 for (AllRangesIterator it(start_interval); !it.Done(); it.Advance()) { 495 LiveInterval* current = it.CurrentInterval(); 496 HInstruction* defined_by = current->GetParent()->GetDefinedBy(); 497 if (current->GetParent()->HasSpillSlot() 498 // Parameters and current method have their own stack slot. 499 && !(defined_by != nullptr && (defined_by->IsParameterValue() 500 || defined_by->IsCurrentMethod()))) { 501 BitVector* liveness_of_spill_slot = liveness_of_values[number_of_registers 502 + current->GetParent()->GetSpillSlot() / kVRegSize 503 - number_of_out_slots]; 504 for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 505 if (liveness_of_spill_slot->IsBitSet(j)) { 506 if (log_fatal_on_failure) { 507 std::ostringstream message; 508 message << "Spill slot conflict at " << j; 509 LOG(FATAL) << message.str(); 510 } else { 511 return false; 512 } 513 } else { 514 liveness_of_spill_slot->SetBit(j); 515 } 516 } 517 } 518 519 if (current->HasRegister()) { 520 if (kIsDebugBuild && log_fatal_on_failure && !current->IsFixed()) { 521 // Only check when an error is fatal. Only tests code ask for non-fatal failures 522 // and test code may not properly fill the right information to the code generator. 523 CHECK(codegen.HasAllocatedRegister(processing_core_registers, current->GetRegister())); 524 } 525 BitVector* liveness_of_register = liveness_of_values[current->GetRegister()]; 526 for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 527 if (liveness_of_register->IsBitSet(j)) { 528 if (current->IsUsingInputRegister() && current->CanUseInputRegister()) { 529 continue; 530 } 531 if (log_fatal_on_failure) { 532 std::ostringstream message; 533 message << "Register conflict at " << j << " "; 534 if (defined_by != nullptr) { 535 message << "(" << defined_by->DebugName() << ")"; 536 } 537 message << "for "; 538 if (processing_core_registers) { 539 codegen.DumpCoreRegister(message, current->GetRegister()); 540 } else { 541 codegen.DumpFloatingPointRegister(message, current->GetRegister()); 542 } 543 LOG(FATAL) << message.str(); 544 } else { 545 return false; 546 } 547 } else { 548 liveness_of_register->SetBit(j); 549 } 550 } 551 } 552 } 553 } 554 return true; 555} 556 557void RegisterAllocator::DumpInterval(std::ostream& stream, LiveInterval* interval) const { 558 interval->Dump(stream); 559 stream << ": "; 560 if (interval->HasRegister()) { 561 if (interval->IsFloatingPoint()) { 562 codegen_->DumpFloatingPointRegister(stream, interval->GetRegister()); 563 } else { 564 codegen_->DumpCoreRegister(stream, interval->GetRegister()); 565 } 566 } else { 567 stream << "spilled"; 568 } 569 stream << std::endl; 570} 571 572void RegisterAllocator::DumpAllIntervals(std::ostream& stream) const { 573 stream << "inactive: " << std::endl; 574 for (LiveInterval* inactive_interval : inactive_) { 575 DumpInterval(stream, inactive_interval); 576 } 577 stream << "active: " << std::endl; 578 for (LiveInterval* active_interval : active_) { 579 DumpInterval(stream, active_interval); 580 } 581 stream << "unhandled: " << std::endl; 582 auto unhandled = (unhandled_ != nullptr) ? 583 unhandled_ : &unhandled_core_intervals_; 584 for (LiveInterval* unhandled_interval : *unhandled) { 585 DumpInterval(stream, unhandled_interval); 586 } 587 stream << "handled: " << std::endl; 588 for (LiveInterval* handled_interval : handled_) { 589 DumpInterval(stream, handled_interval); 590 } 591} 592 593// By the book implementation of a linear scan register allocator. 594void RegisterAllocator::LinearScan() { 595 while (!unhandled_->empty()) { 596 // (1) Remove interval with the lowest start position from unhandled. 597 LiveInterval* current = unhandled_->back(); 598 unhandled_->pop_back(); 599 600 // Make sure the interval is an expected state. 601 DCHECK(!current->IsFixed() && !current->HasSpillSlot()); 602 // Make sure we are going in the right order. 603 DCHECK(unhandled_->empty() || unhandled_->back()->GetStart() >= current->GetStart()); 604 // Make sure a low interval is always with a high. 605 DCHECK(!current->IsLowInterval() || unhandled_->back()->IsHighInterval()); 606 // Make sure a high interval is always with a low. 607 DCHECK(current->IsLowInterval() || 608 unhandled_->empty() || 609 !unhandled_->back()->IsHighInterval()); 610 611 size_t position = current->GetStart(); 612 613 // Remember the inactive_ size here since the ones moved to inactive_ from 614 // active_ below shouldn't need to be re-checked. 615 size_t inactive_intervals_to_handle = inactive_.size(); 616 617 // (2) Remove currently active intervals that are dead at this position. 618 // Move active intervals that have a lifetime hole at this position 619 // to inactive. 620 auto active_kept_end = std::remove_if( 621 active_.begin(), 622 active_.end(), 623 [this, position](LiveInterval* interval) { 624 if (interval->IsDeadAt(position)) { 625 handled_.push_back(interval); 626 return true; 627 } else if (!interval->Covers(position)) { 628 inactive_.push_back(interval); 629 return true; 630 } else { 631 return false; // Keep this interval. 632 } 633 }); 634 active_.erase(active_kept_end, active_.end()); 635 636 // (3) Remove currently inactive intervals that are dead at this position. 637 // Move inactive intervals that cover this position to active. 638 auto inactive_to_handle_end = inactive_.begin() + inactive_intervals_to_handle; 639 auto inactive_kept_end = std::remove_if( 640 inactive_.begin(), 641 inactive_to_handle_end, 642 [this, position](LiveInterval* interval) { 643 DCHECK(interval->GetStart() < position || interval->IsFixed()); 644 if (interval->IsDeadAt(position)) { 645 handled_.push_back(interval); 646 return true; 647 } else if (interval->Covers(position)) { 648 active_.push_back(interval); 649 return true; 650 } else { 651 return false; // Keep this interval. 652 } 653 }); 654 inactive_.erase(inactive_kept_end, inactive_to_handle_end); 655 656 if (current->IsSlowPathSafepoint()) { 657 // Synthesized interval to record the maximum number of live registers 658 // at safepoints. No need to allocate a register for it. 659 if (processing_core_registers_) { 660 maximum_number_of_live_core_registers_ = 661 std::max(maximum_number_of_live_core_registers_, active_.size()); 662 } else { 663 maximum_number_of_live_fp_registers_ = 664 std::max(maximum_number_of_live_fp_registers_, active_.size()); 665 } 666 DCHECK(unhandled_->empty() || unhandled_->back()->GetStart() > current->GetStart()); 667 continue; 668 } 669 670 if (current->IsHighInterval() && !current->GetLowInterval()->HasRegister()) { 671 DCHECK(!current->HasRegister()); 672 // Allocating the low part was unsucessful. The splitted interval for the high part 673 // will be handled next (it is in the `unhandled_` list). 674 continue; 675 } 676 677 // (4) Try to find an available register. 678 bool success = TryAllocateFreeReg(current); 679 680 // (5) If no register could be found, we need to spill. 681 if (!success) { 682 success = AllocateBlockedReg(current); 683 } 684 685 // (6) If the interval had a register allocated, add it to the list of active 686 // intervals. 687 if (success) { 688 codegen_->AddAllocatedRegister(processing_core_registers_ 689 ? Location::RegisterLocation(current->GetRegister()) 690 : Location::FpuRegisterLocation(current->GetRegister())); 691 active_.push_back(current); 692 if (current->HasHighInterval() && !current->GetHighInterval()->HasRegister()) { 693 current->GetHighInterval()->SetRegister(GetHighForLowRegister(current->GetRegister())); 694 } 695 } 696 } 697} 698 699static void FreeIfNotCoverAt(LiveInterval* interval, size_t position, size_t* free_until) { 700 DCHECK(!interval->IsHighInterval()); 701 // Note that the same instruction may occur multiple times in the input list, 702 // so `free_until` may have changed already. 703 // Since `position` is not the current scan position, we need to use CoversSlow. 704 if (interval->IsDeadAt(position)) { 705 // Set the register to be free. Note that inactive intervals might later 706 // update this. 707 free_until[interval->GetRegister()] = kMaxLifetimePosition; 708 if (interval->HasHighInterval()) { 709 DCHECK(interval->GetHighInterval()->IsDeadAt(position)); 710 free_until[interval->GetHighInterval()->GetRegister()] = kMaxLifetimePosition; 711 } 712 } else if (!interval->CoversSlow(position)) { 713 // The interval becomes inactive at `defined_by`. We make its register 714 // available only until the next use strictly after `defined_by`. 715 free_until[interval->GetRegister()] = interval->FirstUseAfter(position); 716 if (interval->HasHighInterval()) { 717 DCHECK(!interval->GetHighInterval()->CoversSlow(position)); 718 free_until[interval->GetHighInterval()->GetRegister()] = free_until[interval->GetRegister()]; 719 } 720 } 721} 722 723// Find a free register. If multiple are found, pick the register that 724// is free the longest. 725bool RegisterAllocator::TryAllocateFreeReg(LiveInterval* current) { 726 size_t* free_until = registers_array_; 727 728 // First set all registers to be free. 729 for (size_t i = 0; i < number_of_registers_; ++i) { 730 free_until[i] = kMaxLifetimePosition; 731 } 732 733 // For each active interval, set its register to not free. 734 for (LiveInterval* interval : active_) { 735 DCHECK(interval->HasRegister()); 736 free_until[interval->GetRegister()] = 0; 737 } 738 739 // An interval that starts an instruction (that is, it is not split), may 740 // re-use the registers used by the inputs of that instruciton, based on the 741 // location summary. 742 HInstruction* defined_by = current->GetDefinedBy(); 743 if (defined_by != nullptr && !current->IsSplit()) { 744 LocationSummary* locations = defined_by->GetLocations(); 745 if (!locations->OutputCanOverlapWithInputs() && locations->Out().IsUnallocated()) { 746 for (size_t i = 0, e = defined_by->InputCount(); i < e; ++i) { 747 // Take the last interval of the input. It is the location of that interval 748 // that will be used at `defined_by`. 749 LiveInterval* interval = defined_by->InputAt(i)->GetLiveInterval()->GetLastSibling(); 750 // Note that interval may have not been processed yet. 751 // TODO: Handle non-split intervals last in the work list. 752 if (locations->InAt(i).IsValid() 753 && interval->HasRegister() 754 && interval->SameRegisterKind(*current)) { 755 // The input must be live until the end of `defined_by`, to comply to 756 // the linear scan algorithm. So we use `defined_by`'s end lifetime 757 // position to check whether the input is dead or is inactive after 758 // `defined_by`. 759 DCHECK(interval->CoversSlow(defined_by->GetLifetimePosition())); 760 size_t position = defined_by->GetLifetimePosition() + 1; 761 FreeIfNotCoverAt(interval, position, free_until); 762 } 763 } 764 } 765 } 766 767 // For each inactive interval, set its register to be free until 768 // the next intersection with `current`. 769 for (LiveInterval* inactive : inactive_) { 770 // Temp/Slow-path-safepoint interval has no holes. 771 DCHECK(!inactive->IsTemp() && !inactive->IsSlowPathSafepoint()); 772 if (!current->IsSplit() && !inactive->IsFixed()) { 773 // Neither current nor inactive are fixed. 774 // Thanks to SSA, a non-split interval starting in a hole of an 775 // inactive interval should never intersect with that inactive interval. 776 // Only if it's not fixed though, because fixed intervals don't come from SSA. 777 DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime); 778 continue; 779 } 780 781 DCHECK(inactive->HasRegister()); 782 if (free_until[inactive->GetRegister()] == 0) { 783 // Already used by some active interval. No need to intersect. 784 continue; 785 } 786 size_t next_intersection = inactive->FirstIntersectionWith(current); 787 if (next_intersection != kNoLifetime) { 788 free_until[inactive->GetRegister()] = 789 std::min(free_until[inactive->GetRegister()], next_intersection); 790 } 791 } 792 793 int reg = kNoRegister; 794 if (current->HasRegister()) { 795 // Some instructions have a fixed register output. 796 reg = current->GetRegister(); 797 if (free_until[reg] == 0) { 798 DCHECK(current->IsHighInterval()); 799 // AllocateBlockedReg will spill the holder of the register. 800 return false; 801 } 802 } else { 803 DCHECK(!current->IsHighInterval()); 804 int hint = current->FindFirstRegisterHint(free_until, liveness_); 805 if ((hint != kNoRegister) 806 // For simplicity, if the hint we are getting for a pair cannot be used, 807 // we are just going to allocate a new pair. 808 && !(current->IsLowInterval() && IsBlocked(GetHighForLowRegister(hint)))) { 809 DCHECK(!IsBlocked(hint)); 810 reg = hint; 811 } else if (current->IsLowInterval()) { 812 reg = FindAvailableRegisterPair(free_until, current->GetStart()); 813 } else { 814 reg = FindAvailableRegister(free_until, current); 815 } 816 } 817 818 DCHECK_NE(reg, kNoRegister); 819 // If we could not find a register, we need to spill. 820 if (free_until[reg] == 0) { 821 return false; 822 } 823 824 if (current->IsLowInterval()) { 825 // If the high register of this interval is not available, we need to spill. 826 int high_reg = current->GetHighInterval()->GetRegister(); 827 if (high_reg == kNoRegister) { 828 high_reg = GetHighForLowRegister(reg); 829 } 830 if (free_until[high_reg] == 0) { 831 return false; 832 } 833 } 834 835 current->SetRegister(reg); 836 if (!current->IsDeadAt(free_until[reg])) { 837 // If the register is only available for a subset of live ranges 838 // covered by `current`, split `current` before the position where 839 // the register is not available anymore. 840 LiveInterval* split = SplitBetween(current, current->GetStart(), free_until[reg]); 841 DCHECK(split != nullptr); 842 AddSorted(unhandled_, split); 843 } 844 return true; 845} 846 847bool RegisterAllocator::IsBlocked(int reg) const { 848 return processing_core_registers_ 849 ? blocked_core_registers_[reg] 850 : blocked_fp_registers_[reg]; 851} 852 853int RegisterAllocator::FindAvailableRegisterPair(size_t* next_use, size_t starting_at) const { 854 int reg = kNoRegister; 855 // Pick the register pair that is used the last. 856 for (size_t i = 0; i < number_of_registers_; ++i) { 857 if (IsBlocked(i)) continue; 858 if (!IsLowRegister(i)) continue; 859 int high_register = GetHighForLowRegister(i); 860 if (IsBlocked(high_register)) continue; 861 int existing_high_register = GetHighForLowRegister(reg); 862 if ((reg == kNoRegister) || (next_use[i] >= next_use[reg] 863 && next_use[high_register] >= next_use[existing_high_register])) { 864 reg = i; 865 if (next_use[i] == kMaxLifetimePosition 866 && next_use[high_register] == kMaxLifetimePosition) { 867 break; 868 } 869 } else if (next_use[reg] <= starting_at || next_use[existing_high_register] <= starting_at) { 870 // If one of the current register is known to be unavailable, just unconditionally 871 // try a new one. 872 reg = i; 873 } 874 } 875 return reg; 876} 877 878bool RegisterAllocator::IsCallerSaveRegister(int reg) const { 879 return processing_core_registers_ 880 ? !codegen_->IsCoreCalleeSaveRegister(reg) 881 : !codegen_->IsFloatingPointCalleeSaveRegister(reg); 882} 883 884int RegisterAllocator::FindAvailableRegister(size_t* next_use, LiveInterval* current) const { 885 // We special case intervals that do not span a safepoint to try to find a caller-save 886 // register if one is available. We iterate from 0 to the number of registers, 887 // so if there are caller-save registers available at the end, we continue the iteration. 888 bool prefers_caller_save = !current->HasWillCallSafepoint(); 889 int reg = kNoRegister; 890 for (size_t i = 0; i < number_of_registers_; ++i) { 891 if (IsBlocked(i)) { 892 // Register cannot be used. Continue. 893 continue; 894 } 895 896 // Best case: we found a register fully available. 897 if (next_use[i] == kMaxLifetimePosition) { 898 if (prefers_caller_save && !IsCallerSaveRegister(i)) { 899 // We can get shorter encodings on some platforms by using 900 // small register numbers. So only update the candidate if the previous 901 // one was not available for the whole method. 902 if (reg == kNoRegister || next_use[reg] != kMaxLifetimePosition) { 903 reg = i; 904 } 905 // Continue the iteration in the hope of finding a caller save register. 906 continue; 907 } else { 908 reg = i; 909 // We know the register is good enough. Return it. 910 break; 911 } 912 } 913 914 // If we had no register before, take this one as a reference. 915 if (reg == kNoRegister) { 916 reg = i; 917 continue; 918 } 919 920 // Pick the register that is used the last. 921 if (next_use[i] > next_use[reg]) { 922 reg = i; 923 continue; 924 } 925 } 926 return reg; 927} 928 929// Remove interval and its other half if any. Return iterator to the following element. 930static ArenaVector<LiveInterval*>::iterator RemoveIntervalAndPotentialOtherHalf( 931 ArenaVector<LiveInterval*>* intervals, ArenaVector<LiveInterval*>::iterator pos) { 932 DCHECK(intervals->begin() <= pos && pos < intervals->end()); 933 LiveInterval* interval = *pos; 934 if (interval->IsLowInterval()) { 935 DCHECK(pos + 1 < intervals->end()); 936 DCHECK_EQ(*(pos + 1), interval->GetHighInterval()); 937 return intervals->erase(pos, pos + 2); 938 } else if (interval->IsHighInterval()) { 939 DCHECK(intervals->begin() < pos); 940 DCHECK_EQ(*(pos - 1), interval->GetLowInterval()); 941 return intervals->erase(pos - 1, pos + 1); 942 } else { 943 return intervals->erase(pos); 944 } 945} 946 947bool RegisterAllocator::TrySplitNonPairOrUnalignedPairIntervalAt(size_t position, 948 size_t first_register_use, 949 size_t* next_use) { 950 for (auto it = active_.begin(), end = active_.end(); it != end; ++it) { 951 LiveInterval* active = *it; 952 DCHECK(active->HasRegister()); 953 if (active->IsFixed()) continue; 954 if (active->IsHighInterval()) continue; 955 if (first_register_use > next_use[active->GetRegister()]) continue; 956 957 // Split the first interval found that is either: 958 // 1) A non-pair interval. 959 // 2) A pair interval whose high is not low + 1. 960 // 3) A pair interval whose low is not even. 961 if (!active->IsLowInterval() || 962 IsLowOfUnalignedPairInterval(active) || 963 !IsLowRegister(active->GetRegister())) { 964 LiveInterval* split = Split(active, position); 965 if (split != active) { 966 handled_.push_back(active); 967 } 968 RemoveIntervalAndPotentialOtherHalf(&active_, it); 969 AddSorted(unhandled_, split); 970 return true; 971 } 972 } 973 return false; 974} 975 976// Find the register that is used the last, and spill the interval 977// that holds it. If the first use of `current` is after that register 978// we spill `current` instead. 979bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) { 980 size_t first_register_use = current->FirstRegisterUse(); 981 if (current->HasRegister()) { 982 DCHECK(current->IsHighInterval()); 983 // The low interval has allocated the register for the high interval. In 984 // case the low interval had to split both intervals, we may end up in a 985 // situation where the high interval does not have a register use anymore. 986 // We must still proceed in order to split currently active and inactive 987 // uses of the high interval's register, and put the high interval in the 988 // active set. 989 DCHECK(first_register_use != kNoLifetime || (current->GetNextSibling() != nullptr)); 990 } else if (first_register_use == kNoLifetime) { 991 AllocateSpillSlotFor(current); 992 return false; 993 } 994 995 // We use the first use to compare with other intervals. If this interval 996 // is used after any active intervals, we will spill this interval. 997 size_t first_use = current->FirstUseAfter(current->GetStart()); 998 999 // First set all registers as not being used. 1000 size_t* next_use = registers_array_; 1001 for (size_t i = 0; i < number_of_registers_; ++i) { 1002 next_use[i] = kMaxLifetimePosition; 1003 } 1004 1005 // For each active interval, find the next use of its register after the 1006 // start of current. 1007 for (LiveInterval* active : active_) { 1008 DCHECK(active->HasRegister()); 1009 if (active->IsFixed()) { 1010 next_use[active->GetRegister()] = current->GetStart(); 1011 } else { 1012 size_t use = active->FirstUseAfter(current->GetStart()); 1013 if (use != kNoLifetime) { 1014 next_use[active->GetRegister()] = use; 1015 } 1016 } 1017 } 1018 1019 // For each inactive interval, find the next use of its register after the 1020 // start of current. 1021 for (LiveInterval* inactive : inactive_) { 1022 // Temp/Slow-path-safepoint interval has no holes. 1023 DCHECK(!inactive->IsTemp() && !inactive->IsSlowPathSafepoint()); 1024 if (!current->IsSplit() && !inactive->IsFixed()) { 1025 // Neither current nor inactive are fixed. 1026 // Thanks to SSA, a non-split interval starting in a hole of an 1027 // inactive interval should never intersect with that inactive interval. 1028 // Only if it's not fixed though, because fixed intervals don't come from SSA. 1029 DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime); 1030 continue; 1031 } 1032 DCHECK(inactive->HasRegister()); 1033 size_t next_intersection = inactive->FirstIntersectionWith(current); 1034 if (next_intersection != kNoLifetime) { 1035 if (inactive->IsFixed()) { 1036 next_use[inactive->GetRegister()] = 1037 std::min(next_intersection, next_use[inactive->GetRegister()]); 1038 } else { 1039 size_t use = inactive->FirstUseAfter(current->GetStart()); 1040 if (use != kNoLifetime) { 1041 next_use[inactive->GetRegister()] = std::min(use, next_use[inactive->GetRegister()]); 1042 } 1043 } 1044 } 1045 } 1046 1047 int reg = kNoRegister; 1048 bool should_spill = false; 1049 if (current->HasRegister()) { 1050 DCHECK(current->IsHighInterval()); 1051 reg = current->GetRegister(); 1052 // When allocating the low part, we made sure the high register was available. 1053 DCHECK_LT(first_use, next_use[reg]); 1054 } else if (current->IsLowInterval()) { 1055 reg = FindAvailableRegisterPair(next_use, first_use); 1056 // We should spill if both registers are not available. 1057 should_spill = (first_use >= next_use[reg]) 1058 || (first_use >= next_use[GetHighForLowRegister(reg)]); 1059 } else { 1060 DCHECK(!current->IsHighInterval()); 1061 reg = FindAvailableRegister(next_use, current); 1062 should_spill = (first_use >= next_use[reg]); 1063 } 1064 1065 DCHECK_NE(reg, kNoRegister); 1066 if (should_spill) { 1067 DCHECK(!current->IsHighInterval()); 1068 bool is_allocation_at_use_site = (current->GetStart() >= (first_register_use - 1)); 1069 if (is_allocation_at_use_site) { 1070 if (!current->IsLowInterval()) { 1071 DumpInterval(std::cerr, current); 1072 DumpAllIntervals(std::cerr); 1073 // This situation has the potential to infinite loop, so we make it a non-debug CHECK. 1074 HInstruction* at = liveness_.GetInstructionFromPosition(first_register_use / 2); 1075 CHECK(false) << "There is not enough registers available for " 1076 << current->GetParent()->GetDefinedBy()->DebugName() << " " 1077 << current->GetParent()->GetDefinedBy()->GetId() 1078 << " at " << first_register_use - 1 << " " 1079 << (at == nullptr ? "" : at->DebugName()); 1080 } 1081 1082 // If we're allocating a register for `current` because the instruction at 1083 // that position requires it, but we think we should spill, then there are 1084 // non-pair intervals or unaligned pair intervals blocking the allocation. 1085 // We split the first interval found, and put ourselves first in the 1086 // `unhandled_` list. 1087 bool success = TrySplitNonPairOrUnalignedPairIntervalAt(current->GetStart(), 1088 first_register_use, 1089 next_use); 1090 DCHECK(success); 1091 LiveInterval* existing = unhandled_->back(); 1092 DCHECK(existing->IsHighInterval()); 1093 DCHECK_EQ(existing->GetLowInterval(), current); 1094 unhandled_->push_back(current); 1095 } else { 1096 // If the first use of that instruction is after the last use of the found 1097 // register, we split this interval just before its first register use. 1098 AllocateSpillSlotFor(current); 1099 LiveInterval* split = SplitBetween(current, current->GetStart(), first_register_use - 1); 1100 DCHECK(current != split); 1101 AddSorted(unhandled_, split); 1102 } 1103 return false; 1104 } else { 1105 // Use this register and spill the active and inactives interval that 1106 // have that register. 1107 current->SetRegister(reg); 1108 1109 for (auto it = active_.begin(), end = active_.end(); it != end; ++it) { 1110 LiveInterval* active = *it; 1111 if (active->GetRegister() == reg) { 1112 DCHECK(!active->IsFixed()); 1113 LiveInterval* split = Split(active, current->GetStart()); 1114 if (split != active) { 1115 handled_.push_back(active); 1116 } 1117 RemoveIntervalAndPotentialOtherHalf(&active_, it); 1118 AddSorted(unhandled_, split); 1119 break; 1120 } 1121 } 1122 1123 // NOTE: Retrieve end() on each iteration because we're removing elements in the loop body. 1124 for (auto it = inactive_.begin(); it != inactive_.end(); ) { 1125 LiveInterval* inactive = *it; 1126 bool erased = false; 1127 if (inactive->GetRegister() == reg) { 1128 if (!current->IsSplit() && !inactive->IsFixed()) { 1129 // Neither current nor inactive are fixed. 1130 // Thanks to SSA, a non-split interval starting in a hole of an 1131 // inactive interval should never intersect with that inactive interval. 1132 // Only if it's not fixed though, because fixed intervals don't come from SSA. 1133 DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime); 1134 } else { 1135 size_t next_intersection = inactive->FirstIntersectionWith(current); 1136 if (next_intersection != kNoLifetime) { 1137 if (inactive->IsFixed()) { 1138 LiveInterval* split = Split(current, next_intersection); 1139 DCHECK_NE(split, current); 1140 AddSorted(unhandled_, split); 1141 } else { 1142 // Split at the start of `current`, which will lead to splitting 1143 // at the end of the lifetime hole of `inactive`. 1144 LiveInterval* split = Split(inactive, current->GetStart()); 1145 // If it's inactive, it must start before the current interval. 1146 DCHECK_NE(split, inactive); 1147 it = RemoveIntervalAndPotentialOtherHalf(&inactive_, it); 1148 erased = true; 1149 handled_.push_back(inactive); 1150 AddSorted(unhandled_, split); 1151 } 1152 } 1153 } 1154 } 1155 // If we have erased the element, `it` already points to the next element. 1156 // Otherwise we need to move to the next element. 1157 if (!erased) { 1158 ++it; 1159 } 1160 } 1161 1162 return true; 1163 } 1164} 1165 1166void RegisterAllocator::AddSorted(ArenaVector<LiveInterval*>* array, LiveInterval* interval) { 1167 DCHECK(!interval->IsFixed() && !interval->HasSpillSlot()); 1168 size_t insert_at = 0; 1169 for (size_t i = array->size(); i > 0; --i) { 1170 LiveInterval* current = (*array)[i - 1u]; 1171 // High intervals must be processed right after their low equivalent. 1172 if (current->StartsAfter(interval) && !current->IsHighInterval()) { 1173 insert_at = i; 1174 break; 1175 } else if ((current->GetStart() == interval->GetStart()) && current->IsSlowPathSafepoint()) { 1176 // Ensure the slow path interval is the last to be processed at its location: we want the 1177 // interval to know all live registers at this location. 1178 DCHECK(i == 1 || (*array)[i - 2u]->StartsAfter(current)); 1179 insert_at = i; 1180 break; 1181 } 1182 } 1183 1184 // Insert the high interval before the low, to ensure the low is processed before. 1185 auto insert_pos = array->begin() + insert_at; 1186 if (interval->HasHighInterval()) { 1187 array->insert(insert_pos, { interval->GetHighInterval(), interval }); 1188 } else if (interval->HasLowInterval()) { 1189 array->insert(insert_pos, { interval, interval->GetLowInterval() }); 1190 } else { 1191 array->insert(insert_pos, interval); 1192 } 1193} 1194 1195LiveInterval* RegisterAllocator::SplitBetween(LiveInterval* interval, size_t from, size_t to) { 1196 HBasicBlock* block_from = liveness_.GetBlockFromPosition(from / 2); 1197 HBasicBlock* block_to = liveness_.GetBlockFromPosition(to / 2); 1198 DCHECK(block_from != nullptr); 1199 DCHECK(block_to != nullptr); 1200 1201 // Both locations are in the same block. We split at the given location. 1202 if (block_from == block_to) { 1203 return Split(interval, to); 1204 } 1205 1206 /* 1207 * Non-linear control flow will force moves at every branch instruction to the new location. 1208 * To avoid having all branches doing the moves, we find the next non-linear position and 1209 * split the interval at this position. Take the following example (block number is the linear 1210 * order position): 1211 * 1212 * B1 1213 * / \ 1214 * B2 B3 1215 * \ / 1216 * B4 1217 * 1218 * B2 needs to split an interval, whose next use is in B4. If we were to split at the 1219 * beginning of B4, B3 would need to do a move between B3 and B4 to ensure the interval 1220 * is now in the correct location. It makes performance worst if the interval is spilled 1221 * and both B2 and B3 need to reload it before entering B4. 1222 * 1223 * By splitting at B3, we give a chance to the register allocator to allocate the 1224 * interval to the same register as in B1, and therefore avoid doing any 1225 * moves in B3. 1226 */ 1227 if (block_from->GetDominator() != nullptr) { 1228 for (HBasicBlock* dominated : block_from->GetDominator()->GetDominatedBlocks()) { 1229 size_t position = dominated->GetLifetimeStart(); 1230 if ((position > from) && (block_to->GetLifetimeStart() > position)) { 1231 // Even if we found a better block, we continue iterating in case 1232 // a dominated block is closer. 1233 // Note that dominated blocks are not sorted in liveness order. 1234 block_to = dominated; 1235 DCHECK_NE(block_to, block_from); 1236 } 1237 } 1238 } 1239 1240 // If `to` is in a loop, find the outermost loop header which does not contain `from`. 1241 for (HLoopInformationOutwardIterator it(*block_to); !it.Done(); it.Advance()) { 1242 HBasicBlock* header = it.Current()->GetHeader(); 1243 if (block_from->GetLifetimeStart() >= header->GetLifetimeStart()) { 1244 break; 1245 } 1246 block_to = header; 1247 } 1248 1249 // Split at the start of the found block, to piggy back on existing moves 1250 // due to resolution if non-linear control flow (see `ConnectSplitSiblings`). 1251 return Split(interval, block_to->GetLifetimeStart()); 1252} 1253 1254LiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) { 1255 DCHECK_GE(position, interval->GetStart()); 1256 DCHECK(!interval->IsDeadAt(position)); 1257 if (position == interval->GetStart()) { 1258 // Spill slot will be allocated when handling `interval` again. 1259 interval->ClearRegister(); 1260 if (interval->HasHighInterval()) { 1261 interval->GetHighInterval()->ClearRegister(); 1262 } else if (interval->HasLowInterval()) { 1263 interval->GetLowInterval()->ClearRegister(); 1264 } 1265 return interval; 1266 } else { 1267 LiveInterval* new_interval = interval->SplitAt(position); 1268 if (interval->HasHighInterval()) { 1269 LiveInterval* high = interval->GetHighInterval()->SplitAt(position); 1270 new_interval->SetHighInterval(high); 1271 high->SetLowInterval(new_interval); 1272 } else if (interval->HasLowInterval()) { 1273 LiveInterval* low = interval->GetLowInterval()->SplitAt(position); 1274 new_interval->SetLowInterval(low); 1275 low->SetHighInterval(new_interval); 1276 } 1277 return new_interval; 1278 } 1279} 1280 1281void RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) { 1282 if (interval->IsHighInterval()) { 1283 // The low interval already took care of allocating the spill slot. 1284 DCHECK(!interval->GetLowInterval()->HasRegister()); 1285 DCHECK(interval->GetLowInterval()->GetParent()->HasSpillSlot()); 1286 return; 1287 } 1288 1289 LiveInterval* parent = interval->GetParent(); 1290 1291 // An instruction gets a spill slot for its entire lifetime. If the parent 1292 // of this interval already has a spill slot, there is nothing to do. 1293 if (parent->HasSpillSlot()) { 1294 return; 1295 } 1296 1297 HInstruction* defined_by = parent->GetDefinedBy(); 1298 DCHECK(!defined_by->IsPhi() || !defined_by->AsPhi()->IsCatchPhi()); 1299 1300 if (defined_by->IsParameterValue()) { 1301 // Parameters have their own stack slot. 1302 parent->SetSpillSlot(codegen_->GetStackSlotOfParameter(defined_by->AsParameterValue())); 1303 return; 1304 } 1305 1306 if (defined_by->IsCurrentMethod()) { 1307 parent->SetSpillSlot(0); 1308 return; 1309 } 1310 1311 if (defined_by->IsConstant()) { 1312 // Constants don't need a spill slot. 1313 return; 1314 } 1315 1316 ArenaVector<size_t>* spill_slots = nullptr; 1317 switch (interval->GetType()) { 1318 case Primitive::kPrimDouble: 1319 spill_slots = &double_spill_slots_; 1320 break; 1321 case Primitive::kPrimLong: 1322 spill_slots = &long_spill_slots_; 1323 break; 1324 case Primitive::kPrimFloat: 1325 spill_slots = &float_spill_slots_; 1326 break; 1327 case Primitive::kPrimNot: 1328 case Primitive::kPrimInt: 1329 case Primitive::kPrimChar: 1330 case Primitive::kPrimByte: 1331 case Primitive::kPrimBoolean: 1332 case Primitive::kPrimShort: 1333 spill_slots = &int_spill_slots_; 1334 break; 1335 case Primitive::kPrimVoid: 1336 LOG(FATAL) << "Unexpected type for interval " << interval->GetType(); 1337 } 1338 1339 // Find an available spill slot. 1340 size_t slot = 0; 1341 for (size_t e = spill_slots->size(); slot < e; ++slot) { 1342 if ((*spill_slots)[slot] <= parent->GetStart() 1343 && (slot == (e - 1) || (*spill_slots)[slot + 1] <= parent->GetStart())) { 1344 break; 1345 } 1346 } 1347 1348 size_t end = interval->GetLastSibling()->GetEnd(); 1349 if (parent->NeedsTwoSpillSlots()) { 1350 if (slot + 2u > spill_slots->size()) { 1351 // We need a new spill slot. 1352 spill_slots->resize(slot + 2u, end); 1353 } 1354 (*spill_slots)[slot] = end; 1355 (*spill_slots)[slot + 1] = end; 1356 } else { 1357 if (slot == spill_slots->size()) { 1358 // We need a new spill slot. 1359 spill_slots->push_back(end); 1360 } else { 1361 (*spill_slots)[slot] = end; 1362 } 1363 } 1364 1365 // Note that the exact spill slot location will be computed when we resolve, 1366 // that is when we know the number of spill slots for each type. 1367 parent->SetSpillSlot(slot); 1368} 1369 1370static bool IsValidDestination(Location destination) { 1371 return destination.IsRegister() 1372 || destination.IsRegisterPair() 1373 || destination.IsFpuRegister() 1374 || destination.IsFpuRegisterPair() 1375 || destination.IsStackSlot() 1376 || destination.IsDoubleStackSlot(); 1377} 1378 1379void RegisterAllocator::AllocateSpillSlotForCatchPhi(HPhi* phi) { 1380 LiveInterval* interval = phi->GetLiveInterval(); 1381 1382 HInstruction* previous_phi = phi->GetPrevious(); 1383 DCHECK(previous_phi == nullptr || 1384 previous_phi->AsPhi()->GetRegNumber() <= phi->GetRegNumber()) 1385 << "Phis expected to be sorted by vreg number, so that equivalent phis are adjacent."; 1386 1387 if (phi->IsVRegEquivalentOf(previous_phi)) { 1388 // This is an equivalent of the previous phi. We need to assign the same 1389 // catch phi slot. 1390 DCHECK(previous_phi->GetLiveInterval()->HasSpillSlot()); 1391 interval->SetSpillSlot(previous_phi->GetLiveInterval()->GetSpillSlot()); 1392 } else { 1393 // Allocate a new spill slot for this catch phi. 1394 // TODO: Reuse spill slots when intervals of phis from different catch 1395 // blocks do not overlap. 1396 interval->SetSpillSlot(catch_phi_spill_slots_); 1397 catch_phi_spill_slots_ += interval->NeedsTwoSpillSlots() ? 2 : 1; 1398 } 1399} 1400 1401void RegisterAllocator::AddMove(HParallelMove* move, 1402 Location source, 1403 Location destination, 1404 HInstruction* instruction, 1405 Primitive::Type type) const { 1406 if (type == Primitive::kPrimLong 1407 && codegen_->ShouldSplitLongMoves() 1408 // The parallel move resolver knows how to deal with long constants. 1409 && !source.IsConstant()) { 1410 move->AddMove(source.ToLow(), destination.ToLow(), Primitive::kPrimInt, instruction); 1411 move->AddMove(source.ToHigh(), destination.ToHigh(), Primitive::kPrimInt, nullptr); 1412 } else { 1413 move->AddMove(source, destination, type, instruction); 1414 } 1415} 1416 1417void RegisterAllocator::AddInputMoveFor(HInstruction* input, 1418 HInstruction* user, 1419 Location source, 1420 Location destination) const { 1421 if (source.Equals(destination)) return; 1422 1423 DCHECK(!user->IsPhi()); 1424 1425 HInstruction* previous = user->GetPrevious(); 1426 HParallelMove* move = nullptr; 1427 if (previous == nullptr 1428 || !previous->IsParallelMove() 1429 || previous->GetLifetimePosition() < user->GetLifetimePosition()) { 1430 move = new (allocator_) HParallelMove(allocator_); 1431 move->SetLifetimePosition(user->GetLifetimePosition()); 1432 user->GetBlock()->InsertInstructionBefore(move, user); 1433 } else { 1434 move = previous->AsParallelMove(); 1435 } 1436 DCHECK_EQ(move->GetLifetimePosition(), user->GetLifetimePosition()); 1437 AddMove(move, source, destination, nullptr, input->GetType()); 1438} 1439 1440static bool IsInstructionStart(size_t position) { 1441 return (position & 1) == 0; 1442} 1443 1444static bool IsInstructionEnd(size_t position) { 1445 return (position & 1) == 1; 1446} 1447 1448void RegisterAllocator::InsertParallelMoveAt(size_t position, 1449 HInstruction* instruction, 1450 Location source, 1451 Location destination) const { 1452 DCHECK(IsValidDestination(destination)) << destination; 1453 if (source.Equals(destination)) return; 1454 1455 HInstruction* at = liveness_.GetInstructionFromPosition(position / 2); 1456 HParallelMove* move; 1457 if (at == nullptr) { 1458 if (IsInstructionStart(position)) { 1459 // Block boundary, don't do anything the connection of split siblings will handle it. 1460 return; 1461 } else { 1462 // Move must happen before the first instruction of the block. 1463 at = liveness_.GetInstructionFromPosition((position + 1) / 2); 1464 // Note that parallel moves may have already been inserted, so we explicitly 1465 // ask for the first instruction of the block: `GetInstructionFromPosition` does 1466 // not contain the `HParallelMove` instructions. 1467 at = at->GetBlock()->GetFirstInstruction(); 1468 1469 if (at->GetLifetimePosition() < position) { 1470 // We may insert moves for split siblings and phi spills at the beginning of the block. 1471 // Since this is a different lifetime position, we need to go to the next instruction. 1472 DCHECK(at->IsParallelMove()); 1473 at = at->GetNext(); 1474 } 1475 1476 if (at->GetLifetimePosition() != position) { 1477 DCHECK_GT(at->GetLifetimePosition(), position); 1478 move = new (allocator_) HParallelMove(allocator_); 1479 move->SetLifetimePosition(position); 1480 at->GetBlock()->InsertInstructionBefore(move, at); 1481 } else { 1482 DCHECK(at->IsParallelMove()); 1483 move = at->AsParallelMove(); 1484 } 1485 } 1486 } else if (IsInstructionEnd(position)) { 1487 // Move must happen after the instruction. 1488 DCHECK(!at->IsControlFlow()); 1489 move = at->GetNext()->AsParallelMove(); 1490 // This is a parallel move for connecting siblings in a same block. We need to 1491 // differentiate it with moves for connecting blocks, and input moves. 1492 if (move == nullptr || move->GetLifetimePosition() > position) { 1493 move = new (allocator_) HParallelMove(allocator_); 1494 move->SetLifetimePosition(position); 1495 at->GetBlock()->InsertInstructionBefore(move, at->GetNext()); 1496 } 1497 } else { 1498 // Move must happen before the instruction. 1499 HInstruction* previous = at->GetPrevious(); 1500 if (previous == nullptr 1501 || !previous->IsParallelMove() 1502 || previous->GetLifetimePosition() != position) { 1503 // If the previous is a parallel move, then its position must be lower 1504 // than the given `position`: it was added just after the non-parallel 1505 // move instruction that precedes `instruction`. 1506 DCHECK(previous == nullptr 1507 || !previous->IsParallelMove() 1508 || previous->GetLifetimePosition() < position); 1509 move = new (allocator_) HParallelMove(allocator_); 1510 move->SetLifetimePosition(position); 1511 at->GetBlock()->InsertInstructionBefore(move, at); 1512 } else { 1513 move = previous->AsParallelMove(); 1514 } 1515 } 1516 DCHECK_EQ(move->GetLifetimePosition(), position); 1517 AddMove(move, source, destination, instruction, instruction->GetType()); 1518} 1519 1520void RegisterAllocator::InsertParallelMoveAtExitOf(HBasicBlock* block, 1521 HInstruction* instruction, 1522 Location source, 1523 Location destination) const { 1524 DCHECK(IsValidDestination(destination)) << destination; 1525 if (source.Equals(destination)) return; 1526 1527 DCHECK_EQ(block->NumberOfNormalSuccessors(), 1u); 1528 HInstruction* last = block->GetLastInstruction(); 1529 // We insert moves at exit for phi predecessors and connecting blocks. 1530 // A block ending with an if or a packed switch cannot branch to a block 1531 // with phis because we do not allow critical edges. It can also not connect 1532 // a split interval between two blocks: the move has to happen in the successor. 1533 DCHECK(!last->IsIf() && !last->IsPackedSwitch()); 1534 HInstruction* previous = last->GetPrevious(); 1535 HParallelMove* move; 1536 // This is a parallel move for connecting blocks. We need to differentiate 1537 // it with moves for connecting siblings in a same block, and output moves. 1538 size_t position = last->GetLifetimePosition(); 1539 if (previous == nullptr || !previous->IsParallelMove() 1540 || previous->AsParallelMove()->GetLifetimePosition() != position) { 1541 move = new (allocator_) HParallelMove(allocator_); 1542 move->SetLifetimePosition(position); 1543 block->InsertInstructionBefore(move, last); 1544 } else { 1545 move = previous->AsParallelMove(); 1546 } 1547 AddMove(move, source, destination, instruction, instruction->GetType()); 1548} 1549 1550void RegisterAllocator::InsertParallelMoveAtEntryOf(HBasicBlock* block, 1551 HInstruction* instruction, 1552 Location source, 1553 Location destination) const { 1554 DCHECK(IsValidDestination(destination)) << destination; 1555 if (source.Equals(destination)) return; 1556 1557 HInstruction* first = block->GetFirstInstruction(); 1558 HParallelMove* move = first->AsParallelMove(); 1559 size_t position = block->GetLifetimeStart(); 1560 // This is a parallel move for connecting blocks. We need to differentiate 1561 // it with moves for connecting siblings in a same block, and input moves. 1562 if (move == nullptr || move->GetLifetimePosition() != position) { 1563 move = new (allocator_) HParallelMove(allocator_); 1564 move->SetLifetimePosition(position); 1565 block->InsertInstructionBefore(move, first); 1566 } 1567 AddMove(move, source, destination, instruction, instruction->GetType()); 1568} 1569 1570void RegisterAllocator::InsertMoveAfter(HInstruction* instruction, 1571 Location source, 1572 Location destination) const { 1573 DCHECK(IsValidDestination(destination)) << destination; 1574 if (source.Equals(destination)) return; 1575 1576 if (instruction->IsPhi()) { 1577 InsertParallelMoveAtEntryOf(instruction->GetBlock(), instruction, source, destination); 1578 return; 1579 } 1580 1581 size_t position = instruction->GetLifetimePosition() + 1; 1582 HParallelMove* move = instruction->GetNext()->AsParallelMove(); 1583 // This is a parallel move for moving the output of an instruction. We need 1584 // to differentiate with input moves, moves for connecting siblings in a 1585 // and moves for connecting blocks. 1586 if (move == nullptr || move->GetLifetimePosition() != position) { 1587 move = new (allocator_) HParallelMove(allocator_); 1588 move->SetLifetimePosition(position); 1589 instruction->GetBlock()->InsertInstructionBefore(move, instruction->GetNext()); 1590 } 1591 AddMove(move, source, destination, instruction, instruction->GetType()); 1592} 1593 1594void RegisterAllocator::ConnectSiblings(LiveInterval* interval) { 1595 LiveInterval* current = interval; 1596 if (current->HasSpillSlot() 1597 && current->HasRegister() 1598 // Currently, we spill unconditionnally the current method in the code generators. 1599 && !interval->GetDefinedBy()->IsCurrentMethod()) { 1600 // We spill eagerly, so move must be at definition. 1601 InsertMoveAfter(interval->GetDefinedBy(), 1602 interval->ToLocation(), 1603 interval->NeedsTwoSpillSlots() 1604 ? Location::DoubleStackSlot(interval->GetParent()->GetSpillSlot()) 1605 : Location::StackSlot(interval->GetParent()->GetSpillSlot())); 1606 } 1607 UsePosition* use = current->GetFirstUse(); 1608 UsePosition* env_use = current->GetFirstEnvironmentUse(); 1609 1610 // Walk over all siblings, updating locations of use positions, and 1611 // connecting them when they are adjacent. 1612 do { 1613 Location source = current->ToLocation(); 1614 1615 // Walk over all uses covered by this interval, and update the location 1616 // information. 1617 1618 LiveRange* range = current->GetFirstRange(); 1619 while (range != nullptr) { 1620 while (use != nullptr && use->GetPosition() < range->GetStart()) { 1621 DCHECK(use->IsSynthesized()); 1622 use = use->GetNext(); 1623 } 1624 while (use != nullptr && use->GetPosition() <= range->GetEnd()) { 1625 DCHECK(!use->GetIsEnvironment()); 1626 DCHECK(current->CoversSlow(use->GetPosition()) || (use->GetPosition() == range->GetEnd())); 1627 if (!use->IsSynthesized()) { 1628 LocationSummary* locations = use->GetUser()->GetLocations(); 1629 Location expected_location = locations->InAt(use->GetInputIndex()); 1630 // The expected (actual) location may be invalid in case the input is unused. Currently 1631 // this only happens for intrinsics. 1632 if (expected_location.IsValid()) { 1633 if (expected_location.IsUnallocated()) { 1634 locations->SetInAt(use->GetInputIndex(), source); 1635 } else if (!expected_location.IsConstant()) { 1636 AddInputMoveFor(interval->GetDefinedBy(), use->GetUser(), source, expected_location); 1637 } 1638 } else { 1639 DCHECK(use->GetUser()->IsInvoke()); 1640 DCHECK(use->GetUser()->AsInvoke()->GetIntrinsic() != Intrinsics::kNone); 1641 } 1642 } 1643 use = use->GetNext(); 1644 } 1645 1646 // Walk over the environment uses, and update their locations. 1647 while (env_use != nullptr && env_use->GetPosition() < range->GetStart()) { 1648 env_use = env_use->GetNext(); 1649 } 1650 1651 while (env_use != nullptr && env_use->GetPosition() <= range->GetEnd()) { 1652 DCHECK(current->CoversSlow(env_use->GetPosition()) 1653 || (env_use->GetPosition() == range->GetEnd())); 1654 HEnvironment* environment = env_use->GetEnvironment(); 1655 environment->SetLocationAt(env_use->GetInputIndex(), source); 1656 env_use = env_use->GetNext(); 1657 } 1658 1659 range = range->GetNext(); 1660 } 1661 1662 // If the next interval starts just after this one, and has a register, 1663 // insert a move. 1664 LiveInterval* next_sibling = current->GetNextSibling(); 1665 if (next_sibling != nullptr 1666 && next_sibling->HasRegister() 1667 && current->GetEnd() == next_sibling->GetStart()) { 1668 Location destination = next_sibling->ToLocation(); 1669 InsertParallelMoveAt(current->GetEnd(), interval->GetDefinedBy(), source, destination); 1670 } 1671 1672 for (SafepointPosition* safepoint_position = current->GetFirstSafepoint(); 1673 safepoint_position != nullptr; 1674 safepoint_position = safepoint_position->GetNext()) { 1675 DCHECK(current->CoversSlow(safepoint_position->GetPosition())); 1676 1677 LocationSummary* locations = safepoint_position->GetLocations(); 1678 if ((current->GetType() == Primitive::kPrimNot) && current->GetParent()->HasSpillSlot()) { 1679 locations->SetStackBit(current->GetParent()->GetSpillSlot() / kVRegSize); 1680 } 1681 1682 switch (source.GetKind()) { 1683 case Location::kRegister: { 1684 locations->AddLiveRegister(source); 1685 if (kIsDebugBuild && locations->OnlyCallsOnSlowPath()) { 1686 DCHECK_LE(locations->GetNumberOfLiveRegisters(), 1687 maximum_number_of_live_core_registers_ + 1688 maximum_number_of_live_fp_registers_); 1689 } 1690 if (current->GetType() == Primitive::kPrimNot) { 1691 locations->SetRegisterBit(source.reg()); 1692 } 1693 break; 1694 } 1695 case Location::kFpuRegister: { 1696 locations->AddLiveRegister(source); 1697 break; 1698 } 1699 1700 case Location::kRegisterPair: 1701 case Location::kFpuRegisterPair: { 1702 locations->AddLiveRegister(source.ToLow()); 1703 locations->AddLiveRegister(source.ToHigh()); 1704 break; 1705 } 1706 case Location::kStackSlot: // Fall-through 1707 case Location::kDoubleStackSlot: // Fall-through 1708 case Location::kConstant: { 1709 // Nothing to do. 1710 break; 1711 } 1712 default: { 1713 LOG(FATAL) << "Unexpected location for object"; 1714 } 1715 } 1716 } 1717 current = next_sibling; 1718 } while (current != nullptr); 1719 1720 if (kIsDebugBuild) { 1721 // Following uses can only be synthesized uses. 1722 while (use != nullptr) { 1723 DCHECK(use->IsSynthesized()); 1724 use = use->GetNext(); 1725 } 1726 } 1727} 1728 1729void RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval, 1730 HBasicBlock* from, 1731 HBasicBlock* to) const { 1732 if (interval->GetNextSibling() == nullptr) { 1733 // Nothing to connect. The whole range was allocated to the same location. 1734 return; 1735 } 1736 1737 // Find the intervals that cover `from` and `to`. 1738 LiveInterval* destination = interval->GetSiblingAt(to->GetLifetimeStart()); 1739 LiveInterval* source = interval->GetSiblingAt(from->GetLifetimeEnd() - 1); 1740 1741 if (destination == source) { 1742 // Interval was not split. 1743 return; 1744 } 1745 DCHECK(destination != nullptr && source != nullptr); 1746 1747 if (!destination->HasRegister()) { 1748 // Values are eagerly spilled. Spill slot already contains appropriate value. 1749 return; 1750 } 1751 1752 // If `from` has only one successor, we can put the moves at the exit of it. Otherwise 1753 // we need to put the moves at the entry of `to`. 1754 if (from->NumberOfNormalSuccessors() == 1) { 1755 InsertParallelMoveAtExitOf(from, 1756 interval->GetParent()->GetDefinedBy(), 1757 source->ToLocation(), 1758 destination->ToLocation()); 1759 } else { 1760 DCHECK_EQ(to->GetPredecessors().size(), 1u); 1761 InsertParallelMoveAtEntryOf(to, 1762 interval->GetParent()->GetDefinedBy(), 1763 source->ToLocation(), 1764 destination->ToLocation()); 1765 } 1766} 1767 1768void RegisterAllocator::Resolve() { 1769 codegen_->InitializeCodeGeneration(GetNumberOfSpillSlots(), 1770 maximum_number_of_live_core_registers_, 1771 maximum_number_of_live_fp_registers_, 1772 reserved_out_slots_, 1773 codegen_->GetGraph()->GetLinearOrder()); 1774 1775 // Adjust the Out Location of instructions. 1776 // TODO: Use pointers of Location inside LiveInterval to avoid doing another iteration. 1777 for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { 1778 HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 1779 LiveInterval* current = instruction->GetLiveInterval(); 1780 LocationSummary* locations = instruction->GetLocations(); 1781 Location location = locations->Out(); 1782 if (instruction->IsParameterValue()) { 1783 // Now that we know the frame size, adjust the parameter's location. 1784 if (location.IsStackSlot()) { 1785 location = Location::StackSlot(location.GetStackIndex() + codegen_->GetFrameSize()); 1786 current->SetSpillSlot(location.GetStackIndex()); 1787 locations->UpdateOut(location); 1788 } else if (location.IsDoubleStackSlot()) { 1789 location = Location::DoubleStackSlot(location.GetStackIndex() + codegen_->GetFrameSize()); 1790 current->SetSpillSlot(location.GetStackIndex()); 1791 locations->UpdateOut(location); 1792 } else if (current->HasSpillSlot()) { 1793 current->SetSpillSlot(current->GetSpillSlot() + codegen_->GetFrameSize()); 1794 } 1795 } else if (instruction->IsCurrentMethod()) { 1796 // The current method is always at offset 0. 1797 DCHECK(!current->HasSpillSlot() || (current->GetSpillSlot() == 0)); 1798 } else if (instruction->IsPhi() && instruction->AsPhi()->IsCatchPhi()) { 1799 DCHECK(current->HasSpillSlot()); 1800 size_t slot = current->GetSpillSlot() 1801 + GetNumberOfSpillSlots() 1802 + reserved_out_slots_ 1803 - catch_phi_spill_slots_; 1804 current->SetSpillSlot(slot * kVRegSize); 1805 } else if (current->HasSpillSlot()) { 1806 // Adjust the stack slot, now that we know the number of them for each type. 1807 // The way this implementation lays out the stack is the following: 1808 // [parameter slots ] 1809 // [catch phi spill slots ] 1810 // [double spill slots ] 1811 // [long spill slots ] 1812 // [float spill slots ] 1813 // [int/ref values ] 1814 // [maximum out values ] (number of arguments for calls) 1815 // [art method ]. 1816 size_t slot = current->GetSpillSlot(); 1817 switch (current->GetType()) { 1818 case Primitive::kPrimDouble: 1819 slot += long_spill_slots_.size(); 1820 FALLTHROUGH_INTENDED; 1821 case Primitive::kPrimLong: 1822 slot += float_spill_slots_.size(); 1823 FALLTHROUGH_INTENDED; 1824 case Primitive::kPrimFloat: 1825 slot += int_spill_slots_.size(); 1826 FALLTHROUGH_INTENDED; 1827 case Primitive::kPrimNot: 1828 case Primitive::kPrimInt: 1829 case Primitive::kPrimChar: 1830 case Primitive::kPrimByte: 1831 case Primitive::kPrimBoolean: 1832 case Primitive::kPrimShort: 1833 slot += reserved_out_slots_; 1834 break; 1835 case Primitive::kPrimVoid: 1836 LOG(FATAL) << "Unexpected type for interval " << current->GetType(); 1837 } 1838 current->SetSpillSlot(slot * kVRegSize); 1839 } 1840 1841 Location source = current->ToLocation(); 1842 1843 if (location.IsUnallocated()) { 1844 if (location.GetPolicy() == Location::kSameAsFirstInput) { 1845 if (locations->InAt(0).IsUnallocated()) { 1846 locations->SetInAt(0, source); 1847 } else { 1848 DCHECK(locations->InAt(0).Equals(source)); 1849 } 1850 } 1851 locations->UpdateOut(source); 1852 } else { 1853 DCHECK(source.Equals(location)); 1854 } 1855 } 1856 1857 // Connect siblings. 1858 for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { 1859 HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 1860 ConnectSiblings(instruction->GetLiveInterval()); 1861 } 1862 1863 // Resolve non-linear control flow across branches. Order does not matter. 1864 for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { 1865 HBasicBlock* block = it.Current(); 1866 if (block->IsCatchBlock()) { 1867 // Instructions live at the top of catch blocks were forced to spill. 1868 if (kIsDebugBuild) { 1869 BitVector* live = liveness_.GetLiveInSet(*block); 1870 for (uint32_t idx : live->Indexes()) { 1871 LiveInterval* interval = liveness_.GetInstructionFromSsaIndex(idx)->GetLiveInterval(); 1872 DCHECK(!interval->GetSiblingAt(block->GetLifetimeStart())->HasRegister()); 1873 } 1874 } 1875 } else { 1876 BitVector* live = liveness_.GetLiveInSet(*block); 1877 for (uint32_t idx : live->Indexes()) { 1878 LiveInterval* interval = liveness_.GetInstructionFromSsaIndex(idx)->GetLiveInterval(); 1879 for (HBasicBlock* predecessor : block->GetPredecessors()) { 1880 ConnectSplitSiblings(interval, predecessor, block); 1881 } 1882 } 1883 } 1884 } 1885 1886 // Resolve phi inputs. Order does not matter. 1887 for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { 1888 HBasicBlock* current = it.Current(); 1889 if (current->IsCatchBlock()) { 1890 // Catch phi values are set at runtime by the exception delivery mechanism. 1891 } else { 1892 for (HInstructionIterator inst_it(current->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 1893 HInstruction* phi = inst_it.Current(); 1894 for (size_t i = 0, e = current->GetPredecessors().size(); i < e; ++i) { 1895 HBasicBlock* predecessor = current->GetPredecessor(i); 1896 DCHECK_EQ(predecessor->NumberOfNormalSuccessors(), 1u); 1897 HInstruction* input = phi->InputAt(i); 1898 Location source = input->GetLiveInterval()->GetLocationAt( 1899 predecessor->GetLifetimeEnd() - 1); 1900 Location destination = phi->GetLiveInterval()->ToLocation(); 1901 InsertParallelMoveAtExitOf(predecessor, phi, source, destination); 1902 } 1903 } 1904 } 1905 } 1906 1907 // Assign temp locations. 1908 for (LiveInterval* temp : temp_intervals_) { 1909 if (temp->IsHighInterval()) { 1910 // High intervals can be skipped, they are already handled by the low interval. 1911 continue; 1912 } 1913 HInstruction* at = liveness_.GetTempUser(temp); 1914 size_t temp_index = liveness_.GetTempIndex(temp); 1915 LocationSummary* locations = at->GetLocations(); 1916 switch (temp->GetType()) { 1917 case Primitive::kPrimInt: 1918 locations->SetTempAt(temp_index, Location::RegisterLocation(temp->GetRegister())); 1919 break; 1920 1921 case Primitive::kPrimDouble: 1922 if (codegen_->NeedsTwoRegisters(Primitive::kPrimDouble)) { 1923 Location location = Location::FpuRegisterPairLocation( 1924 temp->GetRegister(), temp->GetHighInterval()->GetRegister()); 1925 locations->SetTempAt(temp_index, location); 1926 } else { 1927 locations->SetTempAt(temp_index, Location::FpuRegisterLocation(temp->GetRegister())); 1928 } 1929 break; 1930 1931 default: 1932 LOG(FATAL) << "Unexpected type for temporary location " 1933 << temp->GetType(); 1934 } 1935 } 1936} 1937 1938} // namespace art 1939