register_allocator_linear_scan.cc revision 5d6e27d136756216c945d3fc5eb2ecc1537bfe7a
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_linear_scan.h" 18 19#include <iostream> 20#include <sstream> 21 22#include "base/bit_vector-inl.h" 23#include "code_generator.h" 24#include "register_allocation_resolver.h" 25#include "ssa_liveness_analysis.h" 26 27namespace art { 28 29static constexpr size_t kMaxLifetimePosition = -1; 30static constexpr size_t kDefaultNumberOfSpillSlots = 4; 31 32// For simplicity, we implement register pairs as (reg, reg + 1). 33// Note that this is a requirement for double registers on ARM, since we 34// allocate SRegister. 35static int GetHighForLowRegister(int reg) { return reg + 1; } 36static bool IsLowRegister(int reg) { return (reg & 1) == 0; } 37static bool IsLowOfUnalignedPairInterval(LiveInterval* low) { 38 return GetHighForLowRegister(low->GetRegister()) != low->GetHighInterval()->GetRegister(); 39} 40 41RegisterAllocator::RegisterAllocator(ArenaAllocator* allocator, 42 CodeGenerator* codegen, 43 const SsaLivenessAnalysis& liveness) 44 : allocator_(allocator), 45 codegen_(codegen), 46 liveness_(liveness), 47 unhandled_core_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), 48 unhandled_fp_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), 49 unhandled_(nullptr), 50 handled_(allocator->Adapter(kArenaAllocRegisterAllocator)), 51 active_(allocator->Adapter(kArenaAllocRegisterAllocator)), 52 inactive_(allocator->Adapter(kArenaAllocRegisterAllocator)), 53 physical_core_register_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), 54 physical_fp_register_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), 55 temp_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), 56 int_spill_slots_(allocator->Adapter(kArenaAllocRegisterAllocator)), 57 long_spill_slots_(allocator->Adapter(kArenaAllocRegisterAllocator)), 58 float_spill_slots_(allocator->Adapter(kArenaAllocRegisterAllocator)), 59 double_spill_slots_(allocator->Adapter(kArenaAllocRegisterAllocator)), 60 catch_phi_spill_slots_(0), 61 safepoints_(allocator->Adapter(kArenaAllocRegisterAllocator)), 62 processing_core_registers_(false), 63 number_of_registers_(-1), 64 registers_array_(nullptr), 65 blocked_core_registers_(codegen->GetBlockedCoreRegisters()), 66 blocked_fp_registers_(codegen->GetBlockedFloatingPointRegisters()), 67 reserved_out_slots_(0), 68 maximum_number_of_live_core_registers_(0), 69 maximum_number_of_live_fp_registers_(0) { 70 temp_intervals_.reserve(4); 71 int_spill_slots_.reserve(kDefaultNumberOfSpillSlots); 72 long_spill_slots_.reserve(kDefaultNumberOfSpillSlots); 73 float_spill_slots_.reserve(kDefaultNumberOfSpillSlots); 74 double_spill_slots_.reserve(kDefaultNumberOfSpillSlots); 75 76 codegen->SetupBlockedRegisters(); 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 == kArm 89 || instruction_set == kArm64 90 || instruction_set == kMips 91 || instruction_set == kMips64 92 || instruction_set == kThumb2 93 || instruction_set == kX86 94 || instruction_set == kX86_64; 95} 96 97static bool ShouldProcess(bool processing_core_registers, LiveInterval* interval) { 98 if (interval == nullptr) return false; 99 bool is_core_register = (interval->GetType() != Primitive::kPrimDouble) 100 && (interval->GetType() != Primitive::kPrimFloat); 101 return processing_core_registers == is_core_register; 102} 103 104void RegisterAllocator::AllocateRegisters() { 105 AllocateRegistersInternal(); 106 RegisterAllocationResolver(allocator_, codegen_, liveness_) 107 .Resolve(maximum_number_of_live_core_registers_, 108 maximum_number_of_live_fp_registers_, 109 reserved_out_slots_, 110 int_spill_slots_.size(), 111 long_spill_slots_.size(), 112 float_spill_slots_.size(), 113 double_spill_slots_.size(), 114 catch_phi_spill_slots_, 115 temp_intervals_); 116 117 if (kIsDebugBuild) { 118 processing_core_registers_ = true; 119 ValidateInternal(true); 120 processing_core_registers_ = false; 121 ValidateInternal(true); 122 // Check that the linear order is still correct with regards to lifetime positions. 123 // Since only parallel moves have been inserted during the register allocation, 124 // these checks are mostly for making sure these moves have been added correctly. 125 size_t current_liveness = 0; 126 for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { 127 HBasicBlock* block = it.Current(); 128 for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 129 HInstruction* instruction = inst_it.Current(); 130 DCHECK_LE(current_liveness, instruction->GetLifetimePosition()); 131 current_liveness = instruction->GetLifetimePosition(); 132 } 133 for (HInstructionIterator inst_it(block->GetInstructions()); 134 !inst_it.Done(); 135 inst_it.Advance()) { 136 HInstruction* instruction = inst_it.Current(); 137 DCHECK_LE(current_liveness, instruction->GetLifetimePosition()) << instruction->DebugName(); 138 current_liveness = instruction->GetLifetimePosition(); 139 } 140 } 141 } 142} 143 144void RegisterAllocator::BlockRegister(Location location, size_t start, size_t end) { 145 int reg = location.reg(); 146 DCHECK(location.IsRegister() || location.IsFpuRegister()); 147 LiveInterval* interval = location.IsRegister() 148 ? physical_core_register_intervals_[reg] 149 : physical_fp_register_intervals_[reg]; 150 Primitive::Type type = location.IsRegister() 151 ? Primitive::kPrimInt 152 : Primitive::kPrimFloat; 153 if (interval == nullptr) { 154 interval = LiveInterval::MakeFixedInterval(allocator_, reg, type); 155 if (location.IsRegister()) { 156 physical_core_register_intervals_[reg] = interval; 157 } else { 158 physical_fp_register_intervals_[reg] = interval; 159 } 160 } 161 DCHECK(interval->GetRegister() == reg); 162 interval->AddRange(start, end); 163} 164 165void RegisterAllocator::BlockRegisters(size_t start, size_t end, bool caller_save_only) { 166 for (size_t i = 0; i < codegen_->GetNumberOfCoreRegisters(); ++i) { 167 if (!caller_save_only || !codegen_->IsCoreCalleeSaveRegister(i)) { 168 BlockRegister(Location::RegisterLocation(i), start, end); 169 } 170 } 171 for (size_t i = 0; i < codegen_->GetNumberOfFloatingPointRegisters(); ++i) { 172 if (!caller_save_only || !codegen_->IsFloatingPointCalleeSaveRegister(i)) { 173 BlockRegister(Location::FpuRegisterLocation(i), start, end); 174 } 175 } 176} 177 178void RegisterAllocator::AllocateRegistersInternal() { 179 // Iterate post-order, to ensure the list is sorted, and the last added interval 180 // is the one with the lowest start position. 181 for (HLinearPostOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { 182 HBasicBlock* block = it.Current(); 183 for (HBackwardInstructionIterator back_it(block->GetInstructions()); !back_it.Done(); 184 back_it.Advance()) { 185 ProcessInstruction(back_it.Current()); 186 } 187 for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 188 ProcessInstruction(inst_it.Current()); 189 } 190 191 if (block->IsCatchBlock() || 192 (block->IsLoopHeader() && block->GetLoopInformation()->IsIrreducible())) { 193 // By blocking all registers at the top of each catch block or irreducible loop, we force 194 // intervals belonging to the live-in set of the catch/header block to be spilled. 195 // TODO(ngeoffray): Phis in this block could be allocated in register. 196 size_t position = block->GetLifetimeStart(); 197 BlockRegisters(position, position + 1); 198 } 199 } 200 201 number_of_registers_ = codegen_->GetNumberOfCoreRegisters(); 202 registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_, 203 kArenaAllocRegisterAllocator); 204 processing_core_registers_ = true; 205 unhandled_ = &unhandled_core_intervals_; 206 for (LiveInterval* fixed : physical_core_register_intervals_) { 207 if (fixed != nullptr) { 208 // Fixed interval is added to inactive_ instead of unhandled_. 209 // It's also the only type of inactive interval whose start position 210 // can be after the current interval during linear scan. 211 // Fixed interval is never split and never moves to unhandled_. 212 inactive_.push_back(fixed); 213 } 214 } 215 LinearScan(); 216 217 inactive_.clear(); 218 active_.clear(); 219 handled_.clear(); 220 221 number_of_registers_ = codegen_->GetNumberOfFloatingPointRegisters(); 222 registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_, 223 kArenaAllocRegisterAllocator); 224 processing_core_registers_ = false; 225 unhandled_ = &unhandled_fp_intervals_; 226 for (LiveInterval* fixed : physical_fp_register_intervals_) { 227 if (fixed != nullptr) { 228 // Fixed interval is added to inactive_ instead of unhandled_. 229 // It's also the only type of inactive interval whose start position 230 // can be after the current interval during linear scan. 231 // Fixed interval is never split and never moves to unhandled_. 232 inactive_.push_back(fixed); 233 } 234 } 235 LinearScan(); 236} 237 238void RegisterAllocator::ProcessInstruction(HInstruction* instruction) { 239 LocationSummary* locations = instruction->GetLocations(); 240 size_t position = instruction->GetLifetimePosition(); 241 242 if (locations == nullptr) return; 243 244 // Create synthesized intervals for temporaries. 245 for (size_t i = 0; i < locations->GetTempCount(); ++i) { 246 Location temp = locations->GetTemp(i); 247 if (temp.IsRegister() || temp.IsFpuRegister()) { 248 BlockRegister(temp, position, position + 1); 249 // Ensure that an explicit temporary register is marked as being allocated. 250 codegen_->AddAllocatedRegister(temp); 251 } else { 252 DCHECK(temp.IsUnallocated()); 253 switch (temp.GetPolicy()) { 254 case Location::kRequiresRegister: { 255 LiveInterval* interval = 256 LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimInt); 257 temp_intervals_.push_back(interval); 258 interval->AddTempUse(instruction, i); 259 unhandled_core_intervals_.push_back(interval); 260 break; 261 } 262 263 case Location::kRequiresFpuRegister: { 264 LiveInterval* interval = 265 LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimDouble); 266 temp_intervals_.push_back(interval); 267 interval->AddTempUse(instruction, i); 268 if (codegen_->NeedsTwoRegisters(Primitive::kPrimDouble)) { 269 interval->AddHighInterval(/* is_temp */ true); 270 LiveInterval* high = interval->GetHighInterval(); 271 temp_intervals_.push_back(high); 272 unhandled_fp_intervals_.push_back(high); 273 } 274 unhandled_fp_intervals_.push_back(interval); 275 break; 276 } 277 278 default: 279 LOG(FATAL) << "Unexpected policy for temporary location " 280 << temp.GetPolicy(); 281 } 282 } 283 } 284 285 bool core_register = (instruction->GetType() != Primitive::kPrimDouble) 286 && (instruction->GetType() != Primitive::kPrimFloat); 287 288 if (locations->NeedsSafepoint()) { 289 if (codegen_->IsLeafMethod()) { 290 // TODO: We do this here because we do not want the suspend check to artificially 291 // create live registers. We should find another place, but this is currently the 292 // simplest. 293 DCHECK(instruction->IsSuspendCheckEntry()); 294 instruction->GetBlock()->RemoveInstruction(instruction); 295 return; 296 } 297 safepoints_.push_back(instruction); 298 if (locations->OnlyCallsOnSlowPath()) { 299 // We add a synthesized range at this position to record the live registers 300 // at this position. Ideally, we could just update the safepoints when locations 301 // are updated, but we currently need to know the full stack size before updating 302 // locations (because of parameters and the fact that we don't have a frame pointer). 303 // And knowing the full stack size requires to know the maximum number of live 304 // registers at calls in slow paths. 305 // By adding the following interval in the algorithm, we can compute this 306 // maximum before updating locations. 307 LiveInterval* interval = LiveInterval::MakeSlowPathInterval(allocator_, instruction); 308 interval->AddRange(position, position + 1); 309 AddSorted(&unhandled_core_intervals_, interval); 310 AddSorted(&unhandled_fp_intervals_, interval); 311 } 312 } 313 314 if (locations->WillCall()) { 315 BlockRegisters(position, position + 1, /* caller_save_only */ true); 316 } 317 318 for (size_t i = 0; i < locations->GetInputCount(); ++i) { 319 Location input = locations->InAt(i); 320 if (input.IsRegister() || input.IsFpuRegister()) { 321 BlockRegister(input, position, position + 1); 322 } else if (input.IsPair()) { 323 BlockRegister(input.ToLow(), position, position + 1); 324 BlockRegister(input.ToHigh(), position, position + 1); 325 } 326 } 327 328 LiveInterval* current = instruction->GetLiveInterval(); 329 if (current == nullptr) return; 330 331 ArenaVector<LiveInterval*>& unhandled = core_register 332 ? unhandled_core_intervals_ 333 : unhandled_fp_intervals_; 334 335 DCHECK(unhandled.empty() || current->StartsBeforeOrAt(unhandled.back())); 336 337 if (codegen_->NeedsTwoRegisters(current->GetType())) { 338 current->AddHighInterval(); 339 } 340 341 for (size_t safepoint_index = safepoints_.size(); safepoint_index > 0; --safepoint_index) { 342 HInstruction* safepoint = safepoints_[safepoint_index - 1u]; 343 size_t safepoint_position = safepoint->GetLifetimePosition(); 344 345 // Test that safepoints are ordered in the optimal way. 346 DCHECK(safepoint_index == safepoints_.size() || 347 safepoints_[safepoint_index]->GetLifetimePosition() < safepoint_position); 348 349 if (safepoint_position == current->GetStart()) { 350 // The safepoint is for this instruction, so the location of the instruction 351 // does not need to be saved. 352 DCHECK_EQ(safepoint_index, safepoints_.size()); 353 DCHECK_EQ(safepoint, instruction); 354 continue; 355 } else if (current->IsDeadAt(safepoint_position)) { 356 break; 357 } else if (!current->Covers(safepoint_position)) { 358 // Hole in the interval. 359 continue; 360 } 361 current->AddSafepoint(safepoint); 362 } 363 current->ResetSearchCache(); 364 365 // Some instructions define their output in fixed register/stack slot. We need 366 // to ensure we know these locations before doing register allocation. For a 367 // given register, we create an interval that covers these locations. The register 368 // will be unavailable at these locations when trying to allocate one for an 369 // interval. 370 // 371 // The backwards walking ensures the ranges are ordered on increasing start positions. 372 Location output = locations->Out(); 373 if (output.IsUnallocated() && output.GetPolicy() == Location::kSameAsFirstInput) { 374 Location first = locations->InAt(0); 375 if (first.IsRegister() || first.IsFpuRegister()) { 376 current->SetFrom(position + 1); 377 current->SetRegister(first.reg()); 378 } else if (first.IsPair()) { 379 current->SetFrom(position + 1); 380 current->SetRegister(first.low()); 381 LiveInterval* high = current->GetHighInterval(); 382 high->SetRegister(first.high()); 383 high->SetFrom(position + 1); 384 } 385 } else if (output.IsRegister() || output.IsFpuRegister()) { 386 // Shift the interval's start by one to account for the blocked register. 387 current->SetFrom(position + 1); 388 current->SetRegister(output.reg()); 389 BlockRegister(output, position, position + 1); 390 } else if (output.IsPair()) { 391 current->SetFrom(position + 1); 392 current->SetRegister(output.low()); 393 LiveInterval* high = current->GetHighInterval(); 394 high->SetRegister(output.high()); 395 high->SetFrom(position + 1); 396 BlockRegister(output.ToLow(), position, position + 1); 397 BlockRegister(output.ToHigh(), position, position + 1); 398 } else if (output.IsStackSlot() || output.IsDoubleStackSlot()) { 399 current->SetSpillSlot(output.GetStackIndex()); 400 } else { 401 DCHECK(output.IsUnallocated() || output.IsConstant()); 402 } 403 404 if (instruction->IsPhi() && instruction->AsPhi()->IsCatchPhi()) { 405 AllocateSpillSlotForCatchPhi(instruction->AsPhi()); 406 } 407 408 // If needed, add interval to the list of unhandled intervals. 409 if (current->HasSpillSlot() || instruction->IsConstant()) { 410 // Split just before first register use. 411 size_t first_register_use = current->FirstRegisterUse(); 412 if (first_register_use != kNoLifetime) { 413 LiveInterval* split = SplitBetween(current, current->GetStart(), first_register_use - 1); 414 // Don't add directly to `unhandled`, it needs to be sorted and the start 415 // of this new interval might be after intervals already in the list. 416 AddSorted(&unhandled, split); 417 } else { 418 // Nothing to do, we won't allocate a register for this value. 419 } 420 } else { 421 // Don't add directly to `unhandled`, temp or safepoint intervals 422 // for this instruction may have been added, and those can be 423 // processed first. 424 AddSorted(&unhandled, current); 425 } 426} 427 428class AllRangesIterator : public ValueObject { 429 public: 430 explicit AllRangesIterator(LiveInterval* interval) 431 : current_interval_(interval), 432 current_range_(interval->GetFirstRange()) {} 433 434 bool Done() const { return current_interval_ == nullptr; } 435 LiveRange* CurrentRange() const { return current_range_; } 436 LiveInterval* CurrentInterval() const { return current_interval_; } 437 438 void Advance() { 439 current_range_ = current_range_->GetNext(); 440 if (current_range_ == nullptr) { 441 current_interval_ = current_interval_->GetNextSibling(); 442 if (current_interval_ != nullptr) { 443 current_range_ = current_interval_->GetFirstRange(); 444 } 445 } 446 } 447 448 private: 449 LiveInterval* current_interval_; 450 LiveRange* current_range_; 451 452 DISALLOW_COPY_AND_ASSIGN(AllRangesIterator); 453}; 454 455bool RegisterAllocator::ValidateInternal(bool log_fatal_on_failure) const { 456 // To simplify unit testing, we eagerly create the array of intervals, and 457 // call the helper method. 458 ArenaVector<LiveInterval*> intervals(allocator_->Adapter(kArenaAllocRegisterAllocatorValidate)); 459 for (size_t i = 0; i < liveness_.GetNumberOfSsaValues(); ++i) { 460 HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 461 if (ShouldProcess(processing_core_registers_, instruction->GetLiveInterval())) { 462 intervals.push_back(instruction->GetLiveInterval()); 463 } 464 } 465 466 const ArenaVector<LiveInterval*>* physical_register_intervals = processing_core_registers_ 467 ? &physical_core_register_intervals_ 468 : &physical_fp_register_intervals_; 469 for (LiveInterval* fixed : *physical_register_intervals) { 470 if (fixed != nullptr) { 471 intervals.push_back(fixed); 472 } 473 } 474 475 for (LiveInterval* temp : temp_intervals_) { 476 if (ShouldProcess(processing_core_registers_, temp)) { 477 intervals.push_back(temp); 478 } 479 } 480 481 return ValidateIntervals(intervals, GetNumberOfSpillSlots(), reserved_out_slots_, *codegen_, 482 allocator_, processing_core_registers_, log_fatal_on_failure); 483} 484 485bool RegisterAllocator::ValidateIntervals(const ArenaVector<LiveInterval*>& intervals, 486 size_t number_of_spill_slots, 487 size_t number_of_out_slots, 488 const CodeGenerator& codegen, 489 ArenaAllocator* allocator, 490 bool processing_core_registers, 491 bool log_fatal_on_failure) { 492 size_t number_of_registers = processing_core_registers 493 ? codegen.GetNumberOfCoreRegisters() 494 : codegen.GetNumberOfFloatingPointRegisters(); 495 ArenaVector<ArenaBitVector*> liveness_of_values( 496 allocator->Adapter(kArenaAllocRegisterAllocatorValidate)); 497 liveness_of_values.reserve(number_of_registers + number_of_spill_slots); 498 499 size_t max_end = 0u; 500 for (LiveInterval* start_interval : intervals) { 501 for (AllRangesIterator it(start_interval); !it.Done(); it.Advance()) { 502 max_end = std::max(max_end, it.CurrentRange()->GetEnd()); 503 } 504 } 505 506 // Allocate a bit vector per register. A live interval that has a register 507 // allocated will populate the associated bit vector based on its live ranges. 508 for (size_t i = 0; i < number_of_registers + number_of_spill_slots; ++i) { 509 liveness_of_values.push_back( 510 ArenaBitVector::Create(allocator, max_end, false, kArenaAllocRegisterAllocatorValidate)); 511 } 512 513 for (LiveInterval* start_interval : intervals) { 514 for (AllRangesIterator it(start_interval); !it.Done(); it.Advance()) { 515 LiveInterval* current = it.CurrentInterval(); 516 HInstruction* defined_by = current->GetParent()->GetDefinedBy(); 517 if (current->GetParent()->HasSpillSlot() 518 // Parameters and current method have their own stack slot. 519 && !(defined_by != nullptr && (defined_by->IsParameterValue() 520 || defined_by->IsCurrentMethod()))) { 521 BitVector* liveness_of_spill_slot = liveness_of_values[number_of_registers 522 + current->GetParent()->GetSpillSlot() / kVRegSize 523 - number_of_out_slots]; 524 for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 525 if (liveness_of_spill_slot->IsBitSet(j)) { 526 if (log_fatal_on_failure) { 527 std::ostringstream message; 528 message << "Spill slot conflict at " << j; 529 LOG(FATAL) << message.str(); 530 } else { 531 return false; 532 } 533 } else { 534 liveness_of_spill_slot->SetBit(j); 535 } 536 } 537 } 538 539 if (current->HasRegister()) { 540 if (kIsDebugBuild && log_fatal_on_failure && !current->IsFixed()) { 541 // Only check when an error is fatal. Only tests code ask for non-fatal failures 542 // and test code may not properly fill the right information to the code generator. 543 CHECK(codegen.HasAllocatedRegister(processing_core_registers, current->GetRegister())); 544 } 545 BitVector* liveness_of_register = liveness_of_values[current->GetRegister()]; 546 for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 547 if (liveness_of_register->IsBitSet(j)) { 548 if (current->IsUsingInputRegister() && current->CanUseInputRegister()) { 549 continue; 550 } 551 if (log_fatal_on_failure) { 552 std::ostringstream message; 553 message << "Register conflict at " << j << " "; 554 if (defined_by != nullptr) { 555 message << "(" << defined_by->DebugName() << ")"; 556 } 557 message << "for "; 558 if (processing_core_registers) { 559 codegen.DumpCoreRegister(message, current->GetRegister()); 560 } else { 561 codegen.DumpFloatingPointRegister(message, current->GetRegister()); 562 } 563 LOG(FATAL) << message.str(); 564 } else { 565 return false; 566 } 567 } else { 568 liveness_of_register->SetBit(j); 569 } 570 } 571 } 572 } 573 } 574 return true; 575} 576 577void RegisterAllocator::DumpInterval(std::ostream& stream, LiveInterval* interval) const { 578 interval->Dump(stream); 579 stream << ": "; 580 if (interval->HasRegister()) { 581 if (interval->IsFloatingPoint()) { 582 codegen_->DumpFloatingPointRegister(stream, interval->GetRegister()); 583 } else { 584 codegen_->DumpCoreRegister(stream, interval->GetRegister()); 585 } 586 } else { 587 stream << "spilled"; 588 } 589 stream << std::endl; 590} 591 592void RegisterAllocator::DumpAllIntervals(std::ostream& stream) const { 593 stream << "inactive: " << std::endl; 594 for (LiveInterval* inactive_interval : inactive_) { 595 DumpInterval(stream, inactive_interval); 596 } 597 stream << "active: " << std::endl; 598 for (LiveInterval* active_interval : active_) { 599 DumpInterval(stream, active_interval); 600 } 601 stream << "unhandled: " << std::endl; 602 auto unhandled = (unhandled_ != nullptr) ? 603 unhandled_ : &unhandled_core_intervals_; 604 for (LiveInterval* unhandled_interval : *unhandled) { 605 DumpInterval(stream, unhandled_interval); 606 } 607 stream << "handled: " << std::endl; 608 for (LiveInterval* handled_interval : handled_) { 609 DumpInterval(stream, handled_interval); 610 } 611} 612 613// By the book implementation of a linear scan register allocator. 614void RegisterAllocator::LinearScan() { 615 while (!unhandled_->empty()) { 616 // (1) Remove interval with the lowest start position from unhandled. 617 LiveInterval* current = unhandled_->back(); 618 unhandled_->pop_back(); 619 620 // Make sure the interval is an expected state. 621 DCHECK(!current->IsFixed() && !current->HasSpillSlot()); 622 // Make sure we are going in the right order. 623 DCHECK(unhandled_->empty() || unhandled_->back()->GetStart() >= current->GetStart()); 624 // Make sure a low interval is always with a high. 625 DCHECK(!current->IsLowInterval() || unhandled_->back()->IsHighInterval()); 626 // Make sure a high interval is always with a low. 627 DCHECK(current->IsLowInterval() || 628 unhandled_->empty() || 629 !unhandled_->back()->IsHighInterval()); 630 631 size_t position = current->GetStart(); 632 633 // Remember the inactive_ size here since the ones moved to inactive_ from 634 // active_ below shouldn't need to be re-checked. 635 size_t inactive_intervals_to_handle = inactive_.size(); 636 637 // (2) Remove currently active intervals that are dead at this position. 638 // Move active intervals that have a lifetime hole at this position 639 // to inactive. 640 auto active_kept_end = std::remove_if( 641 active_.begin(), 642 active_.end(), 643 [this, position](LiveInterval* interval) { 644 if (interval->IsDeadAt(position)) { 645 handled_.push_back(interval); 646 return true; 647 } else if (!interval->Covers(position)) { 648 inactive_.push_back(interval); 649 return true; 650 } else { 651 return false; // Keep this interval. 652 } 653 }); 654 active_.erase(active_kept_end, active_.end()); 655 656 // (3) Remove currently inactive intervals that are dead at this position. 657 // Move inactive intervals that cover this position to active. 658 auto inactive_to_handle_end = inactive_.begin() + inactive_intervals_to_handle; 659 auto inactive_kept_end = std::remove_if( 660 inactive_.begin(), 661 inactive_to_handle_end, 662 [this, position](LiveInterval* interval) { 663 DCHECK(interval->GetStart() < position || interval->IsFixed()); 664 if (interval->IsDeadAt(position)) { 665 handled_.push_back(interval); 666 return true; 667 } else if (interval->Covers(position)) { 668 active_.push_back(interval); 669 return true; 670 } else { 671 return false; // Keep this interval. 672 } 673 }); 674 inactive_.erase(inactive_kept_end, inactive_to_handle_end); 675 676 if (current->IsSlowPathSafepoint()) { 677 // Synthesized interval to record the maximum number of live registers 678 // at safepoints. No need to allocate a register for it. 679 if (processing_core_registers_) { 680 maximum_number_of_live_core_registers_ = 681 std::max(maximum_number_of_live_core_registers_, active_.size()); 682 } else { 683 maximum_number_of_live_fp_registers_ = 684 std::max(maximum_number_of_live_fp_registers_, active_.size()); 685 } 686 DCHECK(unhandled_->empty() || unhandled_->back()->GetStart() > current->GetStart()); 687 continue; 688 } 689 690 if (current->IsHighInterval() && !current->GetLowInterval()->HasRegister()) { 691 DCHECK(!current->HasRegister()); 692 // Allocating the low part was unsucessful. The splitted interval for the high part 693 // will be handled next (it is in the `unhandled_` list). 694 continue; 695 } 696 697 // (4) Try to find an available register. 698 bool success = TryAllocateFreeReg(current); 699 700 // (5) If no register could be found, we need to spill. 701 if (!success) { 702 success = AllocateBlockedReg(current); 703 } 704 705 // (6) If the interval had a register allocated, add it to the list of active 706 // intervals. 707 if (success) { 708 codegen_->AddAllocatedRegister(processing_core_registers_ 709 ? Location::RegisterLocation(current->GetRegister()) 710 : Location::FpuRegisterLocation(current->GetRegister())); 711 active_.push_back(current); 712 if (current->HasHighInterval() && !current->GetHighInterval()->HasRegister()) { 713 current->GetHighInterval()->SetRegister(GetHighForLowRegister(current->GetRegister())); 714 } 715 } 716 } 717} 718 719static void FreeIfNotCoverAt(LiveInterval* interval, size_t position, size_t* free_until) { 720 DCHECK(!interval->IsHighInterval()); 721 // Note that the same instruction may occur multiple times in the input list, 722 // so `free_until` may have changed already. 723 // Since `position` is not the current scan position, we need to use CoversSlow. 724 if (interval->IsDeadAt(position)) { 725 // Set the register to be free. Note that inactive intervals might later 726 // update this. 727 free_until[interval->GetRegister()] = kMaxLifetimePosition; 728 if (interval->HasHighInterval()) { 729 DCHECK(interval->GetHighInterval()->IsDeadAt(position)); 730 free_until[interval->GetHighInterval()->GetRegister()] = kMaxLifetimePosition; 731 } 732 } else if (!interval->CoversSlow(position)) { 733 // The interval becomes inactive at `defined_by`. We make its register 734 // available only until the next use strictly after `defined_by`. 735 free_until[interval->GetRegister()] = interval->FirstUseAfter(position); 736 if (interval->HasHighInterval()) { 737 DCHECK(!interval->GetHighInterval()->CoversSlow(position)); 738 free_until[interval->GetHighInterval()->GetRegister()] = free_until[interval->GetRegister()]; 739 } 740 } 741} 742 743// Find a free register. If multiple are found, pick the register that 744// is free the longest. 745bool RegisterAllocator::TryAllocateFreeReg(LiveInterval* current) { 746 size_t* free_until = registers_array_; 747 748 // First set all registers to be free. 749 for (size_t i = 0; i < number_of_registers_; ++i) { 750 free_until[i] = kMaxLifetimePosition; 751 } 752 753 // For each active interval, set its register to not free. 754 for (LiveInterval* interval : active_) { 755 DCHECK(interval->HasRegister()); 756 free_until[interval->GetRegister()] = 0; 757 } 758 759 // An interval that starts an instruction (that is, it is not split), may 760 // re-use the registers used by the inputs of that instruciton, based on the 761 // location summary. 762 HInstruction* defined_by = current->GetDefinedBy(); 763 if (defined_by != nullptr && !current->IsSplit()) { 764 LocationSummary* locations = defined_by->GetLocations(); 765 if (!locations->OutputCanOverlapWithInputs() && locations->Out().IsUnallocated()) { 766 HInputsRef inputs = defined_by->GetInputs(); 767 for (size_t i = 0; i < inputs.size(); ++i) { 768 // Take the last interval of the input. It is the location of that interval 769 // that will be used at `defined_by`. 770 LiveInterval* interval = inputs[i]->GetLiveInterval()->GetLastSibling(); 771 // Note that interval may have not been processed yet. 772 // TODO: Handle non-split intervals last in the work list. 773 if (locations->InAt(i).IsValid() 774 && interval->HasRegister() 775 && interval->SameRegisterKind(*current)) { 776 // The input must be live until the end of `defined_by`, to comply to 777 // the linear scan algorithm. So we use `defined_by`'s end lifetime 778 // position to check whether the input is dead or is inactive after 779 // `defined_by`. 780 DCHECK(interval->CoversSlow(defined_by->GetLifetimePosition())); 781 size_t position = defined_by->GetLifetimePosition() + 1; 782 FreeIfNotCoverAt(interval, position, free_until); 783 } 784 } 785 } 786 } 787 788 // For each inactive interval, set its register to be free until 789 // the next intersection with `current`. 790 for (LiveInterval* inactive : inactive_) { 791 // Temp/Slow-path-safepoint interval has no holes. 792 DCHECK(!inactive->IsTemp() && !inactive->IsSlowPathSafepoint()); 793 if (!current->IsSplit() && !inactive->IsFixed()) { 794 // Neither current nor inactive are fixed. 795 // Thanks to SSA, a non-split interval starting in a hole of an 796 // inactive interval should never intersect with that inactive interval. 797 // Only if it's not fixed though, because fixed intervals don't come from SSA. 798 DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime); 799 continue; 800 } 801 802 DCHECK(inactive->HasRegister()); 803 if (free_until[inactive->GetRegister()] == 0) { 804 // Already used by some active interval. No need to intersect. 805 continue; 806 } 807 size_t next_intersection = inactive->FirstIntersectionWith(current); 808 if (next_intersection != kNoLifetime) { 809 free_until[inactive->GetRegister()] = 810 std::min(free_until[inactive->GetRegister()], next_intersection); 811 } 812 } 813 814 int reg = kNoRegister; 815 if (current->HasRegister()) { 816 // Some instructions have a fixed register output. 817 reg = current->GetRegister(); 818 if (free_until[reg] == 0) { 819 DCHECK(current->IsHighInterval()); 820 // AllocateBlockedReg will spill the holder of the register. 821 return false; 822 } 823 } else { 824 DCHECK(!current->IsHighInterval()); 825 int hint = current->FindFirstRegisterHint(free_until, liveness_); 826 if ((hint != kNoRegister) 827 // For simplicity, if the hint we are getting for a pair cannot be used, 828 // we are just going to allocate a new pair. 829 && !(current->IsLowInterval() && IsBlocked(GetHighForLowRegister(hint)))) { 830 DCHECK(!IsBlocked(hint)); 831 reg = hint; 832 } else if (current->IsLowInterval()) { 833 reg = FindAvailableRegisterPair(free_until, current->GetStart()); 834 } else { 835 reg = FindAvailableRegister(free_until, current); 836 } 837 } 838 839 DCHECK_NE(reg, kNoRegister); 840 // If we could not find a register, we need to spill. 841 if (free_until[reg] == 0) { 842 return false; 843 } 844 845 if (current->IsLowInterval()) { 846 // If the high register of this interval is not available, we need to spill. 847 int high_reg = current->GetHighInterval()->GetRegister(); 848 if (high_reg == kNoRegister) { 849 high_reg = GetHighForLowRegister(reg); 850 } 851 if (free_until[high_reg] == 0) { 852 return false; 853 } 854 } 855 856 current->SetRegister(reg); 857 if (!current->IsDeadAt(free_until[reg])) { 858 // If the register is only available for a subset of live ranges 859 // covered by `current`, split `current` before the position where 860 // the register is not available anymore. 861 LiveInterval* split = SplitBetween(current, current->GetStart(), free_until[reg]); 862 DCHECK(split != nullptr); 863 AddSorted(unhandled_, split); 864 } 865 return true; 866} 867 868bool RegisterAllocator::IsBlocked(int reg) const { 869 return processing_core_registers_ 870 ? blocked_core_registers_[reg] 871 : blocked_fp_registers_[reg]; 872} 873 874int RegisterAllocator::FindAvailableRegisterPair(size_t* next_use, size_t starting_at) const { 875 int reg = kNoRegister; 876 // Pick the register pair that is used the last. 877 for (size_t i = 0; i < number_of_registers_; ++i) { 878 if (IsBlocked(i)) continue; 879 if (!IsLowRegister(i)) continue; 880 int high_register = GetHighForLowRegister(i); 881 if (IsBlocked(high_register)) continue; 882 int existing_high_register = GetHighForLowRegister(reg); 883 if ((reg == kNoRegister) || (next_use[i] >= next_use[reg] 884 && next_use[high_register] >= next_use[existing_high_register])) { 885 reg = i; 886 if (next_use[i] == kMaxLifetimePosition 887 && next_use[high_register] == kMaxLifetimePosition) { 888 break; 889 } 890 } else if (next_use[reg] <= starting_at || next_use[existing_high_register] <= starting_at) { 891 // If one of the current register is known to be unavailable, just unconditionally 892 // try a new one. 893 reg = i; 894 } 895 } 896 return reg; 897} 898 899bool RegisterAllocator::IsCallerSaveRegister(int reg) const { 900 return processing_core_registers_ 901 ? !codegen_->IsCoreCalleeSaveRegister(reg) 902 : !codegen_->IsFloatingPointCalleeSaveRegister(reg); 903} 904 905int RegisterAllocator::FindAvailableRegister(size_t* next_use, LiveInterval* current) const { 906 // We special case intervals that do not span a safepoint to try to find a caller-save 907 // register if one is available. We iterate from 0 to the number of registers, 908 // so if there are caller-save registers available at the end, we continue the iteration. 909 bool prefers_caller_save = !current->HasWillCallSafepoint(); 910 int reg = kNoRegister; 911 for (size_t i = 0; i < number_of_registers_; ++i) { 912 if (IsBlocked(i)) { 913 // Register cannot be used. Continue. 914 continue; 915 } 916 917 // Best case: we found a register fully available. 918 if (next_use[i] == kMaxLifetimePosition) { 919 if (prefers_caller_save && !IsCallerSaveRegister(i)) { 920 // We can get shorter encodings on some platforms by using 921 // small register numbers. So only update the candidate if the previous 922 // one was not available for the whole method. 923 if (reg == kNoRegister || next_use[reg] != kMaxLifetimePosition) { 924 reg = i; 925 } 926 // Continue the iteration in the hope of finding a caller save register. 927 continue; 928 } else { 929 reg = i; 930 // We know the register is good enough. Return it. 931 break; 932 } 933 } 934 935 // If we had no register before, take this one as a reference. 936 if (reg == kNoRegister) { 937 reg = i; 938 continue; 939 } 940 941 // Pick the register that is used the last. 942 if (next_use[i] > next_use[reg]) { 943 reg = i; 944 continue; 945 } 946 } 947 return reg; 948} 949 950// Remove interval and its other half if any. Return iterator to the following element. 951static ArenaVector<LiveInterval*>::iterator RemoveIntervalAndPotentialOtherHalf( 952 ArenaVector<LiveInterval*>* intervals, ArenaVector<LiveInterval*>::iterator pos) { 953 DCHECK(intervals->begin() <= pos && pos < intervals->end()); 954 LiveInterval* interval = *pos; 955 if (interval->IsLowInterval()) { 956 DCHECK(pos + 1 < intervals->end()); 957 DCHECK_EQ(*(pos + 1), interval->GetHighInterval()); 958 return intervals->erase(pos, pos + 2); 959 } else if (interval->IsHighInterval()) { 960 DCHECK(intervals->begin() < pos); 961 DCHECK_EQ(*(pos - 1), interval->GetLowInterval()); 962 return intervals->erase(pos - 1, pos + 1); 963 } else { 964 return intervals->erase(pos); 965 } 966} 967 968bool RegisterAllocator::TrySplitNonPairOrUnalignedPairIntervalAt(size_t position, 969 size_t first_register_use, 970 size_t* next_use) { 971 for (auto it = active_.begin(), end = active_.end(); it != end; ++it) { 972 LiveInterval* active = *it; 973 DCHECK(active->HasRegister()); 974 if (active->IsFixed()) continue; 975 if (active->IsHighInterval()) continue; 976 if (first_register_use > next_use[active->GetRegister()]) continue; 977 978 // Split the first interval found that is either: 979 // 1) A non-pair interval. 980 // 2) A pair interval whose high is not low + 1. 981 // 3) A pair interval whose low is not even. 982 if (!active->IsLowInterval() || 983 IsLowOfUnalignedPairInterval(active) || 984 !IsLowRegister(active->GetRegister())) { 985 LiveInterval* split = Split(active, position); 986 if (split != active) { 987 handled_.push_back(active); 988 } 989 RemoveIntervalAndPotentialOtherHalf(&active_, it); 990 AddSorted(unhandled_, split); 991 return true; 992 } 993 } 994 return false; 995} 996 997// Find the register that is used the last, and spill the interval 998// that holds it. If the first use of `current` is after that register 999// we spill `current` instead. 1000bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) { 1001 size_t first_register_use = current->FirstRegisterUse(); 1002 if (current->HasRegister()) { 1003 DCHECK(current->IsHighInterval()); 1004 // The low interval has allocated the register for the high interval. In 1005 // case the low interval had to split both intervals, we may end up in a 1006 // situation where the high interval does not have a register use anymore. 1007 // We must still proceed in order to split currently active and inactive 1008 // uses of the high interval's register, and put the high interval in the 1009 // active set. 1010 DCHECK(first_register_use != kNoLifetime || (current->GetNextSibling() != nullptr)); 1011 } else if (first_register_use == kNoLifetime) { 1012 AllocateSpillSlotFor(current); 1013 return false; 1014 } 1015 1016 // First set all registers as not being used. 1017 size_t* next_use = registers_array_; 1018 for (size_t i = 0; i < number_of_registers_; ++i) { 1019 next_use[i] = kMaxLifetimePosition; 1020 } 1021 1022 // For each active interval, find the next use of its register after the 1023 // start of current. 1024 for (LiveInterval* active : active_) { 1025 DCHECK(active->HasRegister()); 1026 if (active->IsFixed()) { 1027 next_use[active->GetRegister()] = current->GetStart(); 1028 } else { 1029 size_t use = active->FirstRegisterUseAfter(current->GetStart()); 1030 if (use != kNoLifetime) { 1031 next_use[active->GetRegister()] = use; 1032 } 1033 } 1034 } 1035 1036 // For each inactive interval, find the next use of its register after the 1037 // start of current. 1038 for (LiveInterval* inactive : inactive_) { 1039 // Temp/Slow-path-safepoint interval has no holes. 1040 DCHECK(!inactive->IsTemp() && !inactive->IsSlowPathSafepoint()); 1041 if (!current->IsSplit() && !inactive->IsFixed()) { 1042 // Neither current nor inactive are fixed. 1043 // Thanks to SSA, a non-split interval starting in a hole of an 1044 // inactive interval should never intersect with that inactive interval. 1045 // Only if it's not fixed though, because fixed intervals don't come from SSA. 1046 DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime); 1047 continue; 1048 } 1049 DCHECK(inactive->HasRegister()); 1050 size_t next_intersection = inactive->FirstIntersectionWith(current); 1051 if (next_intersection != kNoLifetime) { 1052 if (inactive->IsFixed()) { 1053 next_use[inactive->GetRegister()] = 1054 std::min(next_intersection, next_use[inactive->GetRegister()]); 1055 } else { 1056 size_t use = inactive->FirstUseAfter(current->GetStart()); 1057 if (use != kNoLifetime) { 1058 next_use[inactive->GetRegister()] = std::min(use, next_use[inactive->GetRegister()]); 1059 } 1060 } 1061 } 1062 } 1063 1064 int reg = kNoRegister; 1065 bool should_spill = false; 1066 if (current->HasRegister()) { 1067 DCHECK(current->IsHighInterval()); 1068 reg = current->GetRegister(); 1069 // When allocating the low part, we made sure the high register was available. 1070 DCHECK_LT(first_register_use, next_use[reg]); 1071 } else if (current->IsLowInterval()) { 1072 reg = FindAvailableRegisterPair(next_use, first_register_use); 1073 // We should spill if both registers are not available. 1074 should_spill = (first_register_use >= next_use[reg]) 1075 || (first_register_use >= next_use[GetHighForLowRegister(reg)]); 1076 } else { 1077 DCHECK(!current->IsHighInterval()); 1078 reg = FindAvailableRegister(next_use, current); 1079 should_spill = (first_register_use >= next_use[reg]); 1080 } 1081 1082 DCHECK_NE(reg, kNoRegister); 1083 if (should_spill) { 1084 DCHECK(!current->IsHighInterval()); 1085 bool is_allocation_at_use_site = (current->GetStart() >= (first_register_use - 1)); 1086 if (is_allocation_at_use_site) { 1087 if (!current->IsLowInterval()) { 1088 DumpInterval(std::cerr, current); 1089 DumpAllIntervals(std::cerr); 1090 // This situation has the potential to infinite loop, so we make it a non-debug CHECK. 1091 HInstruction* at = liveness_.GetInstructionFromPosition(first_register_use / 2); 1092 CHECK(false) << "There is not enough registers available for " 1093 << current->GetParent()->GetDefinedBy()->DebugName() << " " 1094 << current->GetParent()->GetDefinedBy()->GetId() 1095 << " at " << first_register_use - 1 << " " 1096 << (at == nullptr ? "" : at->DebugName()); 1097 } 1098 1099 // If we're allocating a register for `current` because the instruction at 1100 // that position requires it, but we think we should spill, then there are 1101 // non-pair intervals or unaligned pair intervals blocking the allocation. 1102 // We split the first interval found, and put ourselves first in the 1103 // `unhandled_` list. 1104 bool success = TrySplitNonPairOrUnalignedPairIntervalAt(current->GetStart(), 1105 first_register_use, 1106 next_use); 1107 DCHECK(success); 1108 LiveInterval* existing = unhandled_->back(); 1109 DCHECK(existing->IsHighInterval()); 1110 DCHECK_EQ(existing->GetLowInterval(), current); 1111 unhandled_->push_back(current); 1112 } else { 1113 // If the first use of that instruction is after the last use of the found 1114 // register, we split this interval just before its first register use. 1115 AllocateSpillSlotFor(current); 1116 LiveInterval* split = SplitBetween(current, current->GetStart(), first_register_use - 1); 1117 DCHECK(current != split); 1118 AddSorted(unhandled_, split); 1119 } 1120 return false; 1121 } else { 1122 // Use this register and spill the active and inactives interval that 1123 // have that register. 1124 current->SetRegister(reg); 1125 1126 for (auto it = active_.begin(), end = active_.end(); it != end; ++it) { 1127 LiveInterval* active = *it; 1128 if (active->GetRegister() == reg) { 1129 DCHECK(!active->IsFixed()); 1130 LiveInterval* split = Split(active, current->GetStart()); 1131 if (split != active) { 1132 handled_.push_back(active); 1133 } 1134 RemoveIntervalAndPotentialOtherHalf(&active_, it); 1135 AddSorted(unhandled_, split); 1136 break; 1137 } 1138 } 1139 1140 // NOTE: Retrieve end() on each iteration because we're removing elements in the loop body. 1141 for (auto it = inactive_.begin(); it != inactive_.end(); ) { 1142 LiveInterval* inactive = *it; 1143 bool erased = false; 1144 if (inactive->GetRegister() == reg) { 1145 if (!current->IsSplit() && !inactive->IsFixed()) { 1146 // Neither current nor inactive are fixed. 1147 // Thanks to SSA, a non-split interval starting in a hole of an 1148 // inactive interval should never intersect with that inactive interval. 1149 // Only if it's not fixed though, because fixed intervals don't come from SSA. 1150 DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime); 1151 } else { 1152 size_t next_intersection = inactive->FirstIntersectionWith(current); 1153 if (next_intersection != kNoLifetime) { 1154 if (inactive->IsFixed()) { 1155 LiveInterval* split = Split(current, next_intersection); 1156 DCHECK_NE(split, current); 1157 AddSorted(unhandled_, split); 1158 } else { 1159 // Split at the start of `current`, which will lead to splitting 1160 // at the end of the lifetime hole of `inactive`. 1161 LiveInterval* split = Split(inactive, current->GetStart()); 1162 // If it's inactive, it must start before the current interval. 1163 DCHECK_NE(split, inactive); 1164 it = RemoveIntervalAndPotentialOtherHalf(&inactive_, it); 1165 erased = true; 1166 handled_.push_back(inactive); 1167 AddSorted(unhandled_, split); 1168 } 1169 } 1170 } 1171 } 1172 // If we have erased the element, `it` already points to the next element. 1173 // Otherwise we need to move to the next element. 1174 if (!erased) { 1175 ++it; 1176 } 1177 } 1178 1179 return true; 1180 } 1181} 1182 1183void RegisterAllocator::AddSorted(ArenaVector<LiveInterval*>* array, LiveInterval* interval) { 1184 DCHECK(!interval->IsFixed() && !interval->HasSpillSlot()); 1185 size_t insert_at = 0; 1186 for (size_t i = array->size(); i > 0; --i) { 1187 LiveInterval* current = (*array)[i - 1u]; 1188 // High intervals must be processed right after their low equivalent. 1189 if (current->StartsAfter(interval) && !current->IsHighInterval()) { 1190 insert_at = i; 1191 break; 1192 } else if ((current->GetStart() == interval->GetStart()) && current->IsSlowPathSafepoint()) { 1193 // Ensure the slow path interval is the last to be processed at its location: we want the 1194 // interval to know all live registers at this location. 1195 DCHECK(i == 1 || (*array)[i - 2u]->StartsAfter(current)); 1196 insert_at = i; 1197 break; 1198 } 1199 } 1200 1201 // Insert the high interval before the low, to ensure the low is processed before. 1202 auto insert_pos = array->begin() + insert_at; 1203 if (interval->HasHighInterval()) { 1204 array->insert(insert_pos, { interval->GetHighInterval(), interval }); 1205 } else if (interval->HasLowInterval()) { 1206 array->insert(insert_pos, { interval, interval->GetLowInterval() }); 1207 } else { 1208 array->insert(insert_pos, interval); 1209 } 1210} 1211 1212LiveInterval* RegisterAllocator::SplitBetween(LiveInterval* interval, size_t from, size_t to) { 1213 HBasicBlock* block_from = liveness_.GetBlockFromPosition(from / 2); 1214 HBasicBlock* block_to = liveness_.GetBlockFromPosition(to / 2); 1215 DCHECK(block_from != nullptr); 1216 DCHECK(block_to != nullptr); 1217 1218 // Both locations are in the same block. We split at the given location. 1219 if (block_from == block_to) { 1220 return Split(interval, to); 1221 } 1222 1223 /* 1224 * Non-linear control flow will force moves at every branch instruction to the new location. 1225 * To avoid having all branches doing the moves, we find the next non-linear position and 1226 * split the interval at this position. Take the following example (block number is the linear 1227 * order position): 1228 * 1229 * B1 1230 * / \ 1231 * B2 B3 1232 * \ / 1233 * B4 1234 * 1235 * B2 needs to split an interval, whose next use is in B4. If we were to split at the 1236 * beginning of B4, B3 would need to do a move between B3 and B4 to ensure the interval 1237 * is now in the correct location. It makes performance worst if the interval is spilled 1238 * and both B2 and B3 need to reload it before entering B4. 1239 * 1240 * By splitting at B3, we give a chance to the register allocator to allocate the 1241 * interval to the same register as in B1, and therefore avoid doing any 1242 * moves in B3. 1243 */ 1244 if (block_from->GetDominator() != nullptr) { 1245 for (HBasicBlock* dominated : block_from->GetDominator()->GetDominatedBlocks()) { 1246 size_t position = dominated->GetLifetimeStart(); 1247 if ((position > from) && (block_to->GetLifetimeStart() > position)) { 1248 // Even if we found a better block, we continue iterating in case 1249 // a dominated block is closer. 1250 // Note that dominated blocks are not sorted in liveness order. 1251 block_to = dominated; 1252 DCHECK_NE(block_to, block_from); 1253 } 1254 } 1255 } 1256 1257 // If `to` is in a loop, find the outermost loop header which does not contain `from`. 1258 for (HLoopInformationOutwardIterator it(*block_to); !it.Done(); it.Advance()) { 1259 HBasicBlock* header = it.Current()->GetHeader(); 1260 if (block_from->GetLifetimeStart() >= header->GetLifetimeStart()) { 1261 break; 1262 } 1263 block_to = header; 1264 } 1265 1266 // Split at the start of the found block, to piggy back on existing moves 1267 // due to resolution if non-linear control flow (see `ConnectSplitSiblings`). 1268 return Split(interval, block_to->GetLifetimeStart()); 1269} 1270 1271LiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) { 1272 DCHECK_GE(position, interval->GetStart()); 1273 DCHECK(!interval->IsDeadAt(position)); 1274 if (position == interval->GetStart()) { 1275 // Spill slot will be allocated when handling `interval` again. 1276 interval->ClearRegister(); 1277 if (interval->HasHighInterval()) { 1278 interval->GetHighInterval()->ClearRegister(); 1279 } else if (interval->HasLowInterval()) { 1280 interval->GetLowInterval()->ClearRegister(); 1281 } 1282 return interval; 1283 } else { 1284 LiveInterval* new_interval = interval->SplitAt(position); 1285 if (interval->HasHighInterval()) { 1286 LiveInterval* high = interval->GetHighInterval()->SplitAt(position); 1287 new_interval->SetHighInterval(high); 1288 high->SetLowInterval(new_interval); 1289 } else if (interval->HasLowInterval()) { 1290 LiveInterval* low = interval->GetLowInterval()->SplitAt(position); 1291 new_interval->SetLowInterval(low); 1292 low->SetHighInterval(new_interval); 1293 } 1294 return new_interval; 1295 } 1296} 1297 1298void RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) { 1299 if (interval->IsHighInterval()) { 1300 // The low interval already took care of allocating the spill slot. 1301 DCHECK(!interval->GetLowInterval()->HasRegister()); 1302 DCHECK(interval->GetLowInterval()->GetParent()->HasSpillSlot()); 1303 return; 1304 } 1305 1306 LiveInterval* parent = interval->GetParent(); 1307 1308 // An instruction gets a spill slot for its entire lifetime. If the parent 1309 // of this interval already has a spill slot, there is nothing to do. 1310 if (parent->HasSpillSlot()) { 1311 return; 1312 } 1313 1314 HInstruction* defined_by = parent->GetDefinedBy(); 1315 DCHECK(!defined_by->IsPhi() || !defined_by->AsPhi()->IsCatchPhi()); 1316 1317 if (defined_by->IsParameterValue()) { 1318 // Parameters have their own stack slot. 1319 parent->SetSpillSlot(codegen_->GetStackSlotOfParameter(defined_by->AsParameterValue())); 1320 return; 1321 } 1322 1323 if (defined_by->IsCurrentMethod()) { 1324 parent->SetSpillSlot(0); 1325 return; 1326 } 1327 1328 if (defined_by->IsConstant()) { 1329 // Constants don't need a spill slot. 1330 return; 1331 } 1332 1333 ArenaVector<size_t>* spill_slots = nullptr; 1334 switch (interval->GetType()) { 1335 case Primitive::kPrimDouble: 1336 spill_slots = &double_spill_slots_; 1337 break; 1338 case Primitive::kPrimLong: 1339 spill_slots = &long_spill_slots_; 1340 break; 1341 case Primitive::kPrimFloat: 1342 spill_slots = &float_spill_slots_; 1343 break; 1344 case Primitive::kPrimNot: 1345 case Primitive::kPrimInt: 1346 case Primitive::kPrimChar: 1347 case Primitive::kPrimByte: 1348 case Primitive::kPrimBoolean: 1349 case Primitive::kPrimShort: 1350 spill_slots = &int_spill_slots_; 1351 break; 1352 case Primitive::kPrimVoid: 1353 LOG(FATAL) << "Unexpected type for interval " << interval->GetType(); 1354 } 1355 1356 // Find an available spill slot. 1357 size_t slot = 0; 1358 for (size_t e = spill_slots->size(); slot < e; ++slot) { 1359 if ((*spill_slots)[slot] <= parent->GetStart()) { 1360 if (!parent->NeedsTwoSpillSlots()) { 1361 // One spill slot is sufficient. 1362 break; 1363 } 1364 if (slot == e - 1 || (*spill_slots)[slot + 1] <= parent->GetStart()) { 1365 // Two spill slots are available. 1366 break; 1367 } 1368 } 1369 } 1370 1371 size_t end = interval->GetLastSibling()->GetEnd(); 1372 if (parent->NeedsTwoSpillSlots()) { 1373 if (slot + 2u > spill_slots->size()) { 1374 // We need a new spill slot. 1375 spill_slots->resize(slot + 2u, end); 1376 } 1377 (*spill_slots)[slot] = end; 1378 (*spill_slots)[slot + 1] = end; 1379 } else { 1380 if (slot == spill_slots->size()) { 1381 // We need a new spill slot. 1382 spill_slots->push_back(end); 1383 } else { 1384 (*spill_slots)[slot] = end; 1385 } 1386 } 1387 1388 // Note that the exact spill slot location will be computed when we resolve, 1389 // that is when we know the number of spill slots for each type. 1390 parent->SetSpillSlot(slot); 1391} 1392 1393void RegisterAllocator::AllocateSpillSlotForCatchPhi(HPhi* phi) { 1394 LiveInterval* interval = phi->GetLiveInterval(); 1395 1396 HInstruction* previous_phi = phi->GetPrevious(); 1397 DCHECK(previous_phi == nullptr || 1398 previous_phi->AsPhi()->GetRegNumber() <= phi->GetRegNumber()) 1399 << "Phis expected to be sorted by vreg number, so that equivalent phis are adjacent."; 1400 1401 if (phi->IsVRegEquivalentOf(previous_phi)) { 1402 // This is an equivalent of the previous phi. We need to assign the same 1403 // catch phi slot. 1404 DCHECK(previous_phi->GetLiveInterval()->HasSpillSlot()); 1405 interval->SetSpillSlot(previous_phi->GetLiveInterval()->GetSpillSlot()); 1406 } else { 1407 // Allocate a new spill slot for this catch phi. 1408 // TODO: Reuse spill slots when intervals of phis from different catch 1409 // blocks do not overlap. 1410 interval->SetSpillSlot(catch_phi_spill_slots_); 1411 catch_phi_spill_slots_ += interval->NeedsTwoSpillSlots() ? 2 : 1; 1412 } 1413} 1414 1415} // namespace art 1416