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