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