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