register_allocator.cc revision c7dd295a4e0cc1d15c0c96088e55a85389bade74
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 30RegisterAllocator::RegisterAllocator(ArenaAllocator* allocator, 31 CodeGenerator* codegen, 32 const SsaLivenessAnalysis& liveness) 33 : allocator_(allocator), 34 codegen_(codegen), 35 liveness_(liveness), 36 unhandled_core_intervals_(allocator, 0), 37 unhandled_fp_intervals_(allocator, 0), 38 unhandled_(nullptr), 39 handled_(allocator, 0), 40 active_(allocator, 0), 41 inactive_(allocator, 0), 42 physical_core_register_intervals_(allocator, codegen->GetNumberOfCoreRegisters()), 43 physical_fp_register_intervals_(allocator, codegen->GetNumberOfFloatingPointRegisters()), 44 temp_intervals_(allocator, 4), 45 spill_slots_(allocator, kDefaultNumberOfSpillSlots), 46 safepoints_(allocator, 0), 47 processing_core_registers_(false), 48 number_of_registers_(-1), 49 registers_array_(nullptr), 50 blocked_core_registers_(codegen->GetBlockedCoreRegisters()), 51 blocked_fp_registers_(codegen->GetBlockedFloatingPointRegisters()), 52 reserved_out_slots_(0), 53 maximum_number_of_live_registers_(0) { 54 codegen->SetupBlockedRegisters(); 55 physical_core_register_intervals_.SetSize(codegen->GetNumberOfCoreRegisters()); 56 physical_fp_register_intervals_.SetSize(codegen->GetNumberOfFloatingPointRegisters()); 57 // Always reserve for the current method and the graph's max out registers. 58 // TODO: compute it instead. 59 reserved_out_slots_ = 1 + codegen->GetGraph()->GetMaximumNumberOfOutVRegs(); 60} 61 62bool RegisterAllocator::CanAllocateRegistersFor(const HGraph& graph, 63 InstructionSet instruction_set) { 64 if (!Supports(instruction_set)) { 65 return false; 66 } 67 for (size_t i = 0, e = graph.GetBlocks().Size(); i < e; ++i) { 68 for (HInstructionIterator it(graph.GetBlocks().Get(i)->GetInstructions()); 69 !it.Done(); 70 it.Advance()) { 71 HInstruction* current = it.Current(); 72 if (current->GetType() == Primitive::kPrimLong && instruction_set != kX86_64) return false; 73 if ((current->GetType() == Primitive::kPrimFloat || current->GetType() == Primitive::kPrimDouble) 74 && instruction_set != kX86_64) { 75 return false; 76 } 77 } 78 } 79 return true; 80} 81 82static bool ShouldProcess(bool processing_core_registers, LiveInterval* interval) { 83 if (interval == nullptr) return false; 84 bool is_core_register = (interval->GetType() != Primitive::kPrimDouble) 85 && (interval->GetType() != Primitive::kPrimFloat); 86 return processing_core_registers == is_core_register; 87} 88 89void RegisterAllocator::AllocateRegisters() { 90 AllocateRegistersInternal(); 91 Resolve(); 92 93 if (kIsDebugBuild) { 94 processing_core_registers_ = true; 95 ValidateInternal(true); 96 processing_core_registers_ = false; 97 ValidateInternal(true); 98 } 99} 100 101void RegisterAllocator::BlockRegister(Location location, 102 size_t start, 103 size_t end) { 104 int reg = location.reg(); 105 DCHECK(location.IsRegister() || location.IsFpuRegister()); 106 LiveInterval* interval = location.IsRegister() 107 ? physical_core_register_intervals_.Get(reg) 108 : physical_fp_register_intervals_.Get(reg); 109 Primitive::Type type = location.IsRegister() 110 ? Primitive::kPrimInt 111 : Primitive::kPrimDouble; 112 if (interval == nullptr) { 113 interval = LiveInterval::MakeFixedInterval(allocator_, reg, type); 114 if (location.IsRegister()) { 115 physical_core_register_intervals_.Put(reg, interval); 116 } else { 117 physical_fp_register_intervals_.Put(reg, interval); 118 } 119 } 120 DCHECK(interval->GetRegister() == reg); 121 interval->AddRange(start, end); 122} 123 124void RegisterAllocator::AllocateRegistersInternal() { 125 // Iterate post-order, to ensure the list is sorted, and the last added interval 126 // is the one with the lowest start position. 127 for (HLinearPostOrderIterator it(liveness_); !it.Done(); it.Advance()) { 128 HBasicBlock* block = it.Current(); 129 for (HBackwardInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 130 ProcessInstruction(it.Current()); 131 } 132 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 133 ProcessInstruction(it.Current()); 134 } 135 } 136 137 number_of_registers_ = codegen_->GetNumberOfCoreRegisters(); 138 registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_); 139 processing_core_registers_ = true; 140 unhandled_ = &unhandled_core_intervals_; 141 for (size_t i = 0, e = physical_core_register_intervals_.Size(); i < e; ++i) { 142 LiveInterval* fixed = physical_core_register_intervals_.Get(i); 143 if (fixed != nullptr) { 144 inactive_.Add(fixed); 145 } 146 } 147 LinearScan(); 148 149 size_t saved_maximum_number_of_live_registers = maximum_number_of_live_registers_; 150 maximum_number_of_live_registers_ = 0; 151 152 inactive_.Reset(); 153 active_.Reset(); 154 handled_.Reset(); 155 156 number_of_registers_ = codegen_->GetNumberOfFloatingPointRegisters(); 157 registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_); 158 processing_core_registers_ = false; 159 unhandled_ = &unhandled_fp_intervals_; 160 for (size_t i = 0, e = physical_fp_register_intervals_.Size(); i < e; ++i) { 161 LiveInterval* fixed = physical_fp_register_intervals_.Get(i); 162 if (fixed != nullptr) { 163 inactive_.Add(fixed); 164 } 165 } 166 LinearScan(); 167 maximum_number_of_live_registers_ += saved_maximum_number_of_live_registers; 168} 169 170void RegisterAllocator::ProcessInstruction(HInstruction* instruction) { 171 LocationSummary* locations = instruction->GetLocations(); 172 size_t position = instruction->GetLifetimePosition(); 173 174 if (locations == nullptr) return; 175 176 // Create synthesized intervals for temporaries. 177 for (size_t i = 0; i < locations->GetTempCount(); ++i) { 178 Location temp = locations->GetTemp(i); 179 if (temp.IsRegister()) { 180 BlockRegister(temp, position, position + 1); 181 } else { 182 DCHECK(temp.IsUnallocated()); 183 LiveInterval* interval = LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimInt); 184 temp_intervals_.Add(interval); 185 interval->AddRange(position, position + 1); 186 unhandled_core_intervals_.Add(interval); 187 } 188 } 189 190 bool core_register = (instruction->GetType() != Primitive::kPrimDouble) 191 && (instruction->GetType() != Primitive::kPrimFloat); 192 193 if (locations->CanCall()) { 194 if (!instruction->IsSuspendCheck()) { 195 codegen_->MarkNotLeaf(); 196 } 197 safepoints_.Add(instruction); 198 if (locations->OnlyCallsOnSlowPath()) { 199 // We add a synthesized range at this position to record the live registers 200 // at this position. Ideally, we could just update the safepoints when locations 201 // are updated, but we currently need to know the full stack size before updating 202 // locations (because of parameters and the fact that we don't have a frame pointer). 203 // And knowing the full stack size requires to know the maximum number of live 204 // registers at calls in slow paths. 205 // By adding the following interval in the algorithm, we can compute this 206 // maximum before updating locations. 207 LiveInterval* interval = LiveInterval::MakeSlowPathInterval(allocator_, instruction); 208 interval->AddRange(position, position + 1); 209 unhandled_core_intervals_.Add(interval); 210 unhandled_fp_intervals_.Add(interval); 211 } 212 } 213 214 if (locations->WillCall()) { 215 // Block all registers. 216 for (size_t i = 0; i < codegen_->GetNumberOfCoreRegisters(); ++i) { 217 BlockRegister(Location::RegisterLocation(i), 218 position, 219 position + 1); 220 } 221 for (size_t i = 0; i < codegen_->GetNumberOfFloatingPointRegisters(); ++i) { 222 BlockRegister(Location::FpuRegisterLocation(i), 223 position, 224 position + 1); 225 } 226 } 227 228 for (size_t i = 0; i < instruction->InputCount(); ++i) { 229 Location input = locations->InAt(i); 230 if (input.IsRegister() || input.IsFpuRegister()) { 231 BlockRegister(input, position, position + 1); 232 } 233 } 234 235 LiveInterval* current = instruction->GetLiveInterval(); 236 if (current == nullptr) return; 237 238 GrowableArray<LiveInterval*>& unhandled = core_register 239 ? unhandled_core_intervals_ 240 : unhandled_fp_intervals_; 241 242 DCHECK(unhandled.IsEmpty() || current->StartsBeforeOrAt(unhandled.Peek())); 243 // Some instructions define their output in fixed register/stack slot. We need 244 // to ensure we know these locations before doing register allocation. For a 245 // given register, we create an interval that covers these locations. The register 246 // will be unavailable at these locations when trying to allocate one for an 247 // interval. 248 // 249 // The backwards walking ensures the ranges are ordered on increasing start positions. 250 Location output = locations->Out(); 251 if (output.IsRegister() || output.IsFpuRegister()) { 252 // Shift the interval's start by one to account for the blocked register. 253 current->SetFrom(position + 1); 254 current->SetRegister(output.reg()); 255 BlockRegister(output, position, position + 1); 256 } else if (!locations->OutputOverlapsWithInputs()) { 257 // Shift the interval's start by one to not interfere with the inputs. 258 current->SetFrom(position + 1); 259 } else if (output.IsStackSlot() || output.IsDoubleStackSlot()) { 260 current->SetSpillSlot(output.GetStackIndex()); 261 } 262 263 // If needed, add interval to the list of unhandled intervals. 264 if (current->HasSpillSlot() || instruction->IsConstant()) { 265 // Split just before first register use. 266 size_t first_register_use = current->FirstRegisterUse(); 267 if (first_register_use != kNoLifetime) { 268 LiveInterval* split = Split(current, first_register_use - 1); 269 // Don't add direclty to `unhandled`, it needs to be sorted and the start 270 // of this new interval might be after intervals already in the list. 271 AddSorted(&unhandled, split); 272 } else { 273 // Nothing to do, we won't allocate a register for this value. 274 } 275 } else { 276 DCHECK(unhandled.IsEmpty() || current->StartsBeforeOrAt(unhandled.Peek())); 277 unhandled.Add(current); 278 } 279} 280 281class AllRangesIterator : public ValueObject { 282 public: 283 explicit AllRangesIterator(LiveInterval* interval) 284 : current_interval_(interval), 285 current_range_(interval->GetFirstRange()) {} 286 287 bool Done() const { return current_interval_ == nullptr; } 288 LiveRange* CurrentRange() const { return current_range_; } 289 LiveInterval* CurrentInterval() const { return current_interval_; } 290 291 void Advance() { 292 current_range_ = current_range_->GetNext(); 293 if (current_range_ == nullptr) { 294 current_interval_ = current_interval_->GetNextSibling(); 295 if (current_interval_ != nullptr) { 296 current_range_ = current_interval_->GetFirstRange(); 297 } 298 } 299 } 300 301 private: 302 LiveInterval* current_interval_; 303 LiveRange* current_range_; 304 305 DISALLOW_COPY_AND_ASSIGN(AllRangesIterator); 306}; 307 308bool RegisterAllocator::ValidateInternal(bool log_fatal_on_failure) const { 309 // To simplify unit testing, we eagerly create the array of intervals, and 310 // call the helper method. 311 GrowableArray<LiveInterval*> intervals(allocator_, 0); 312 for (size_t i = 0; i < liveness_.GetNumberOfSsaValues(); ++i) { 313 HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 314 if (ShouldProcess(processing_core_registers_, instruction->GetLiveInterval())) { 315 intervals.Add(instruction->GetLiveInterval()); 316 } 317 } 318 319 if (processing_core_registers_) { 320 for (size_t i = 0, e = physical_core_register_intervals_.Size(); i < e; ++i) { 321 LiveInterval* fixed = physical_core_register_intervals_.Get(i); 322 if (fixed != nullptr) { 323 intervals.Add(fixed); 324 } 325 } 326 } else { 327 for (size_t i = 0, e = physical_fp_register_intervals_.Size(); i < e; ++i) { 328 LiveInterval* fixed = physical_fp_register_intervals_.Get(i); 329 if (fixed != nullptr) { 330 intervals.Add(fixed); 331 } 332 } 333 } 334 335 for (size_t i = 0, e = temp_intervals_.Size(); i < e; ++i) { 336 LiveInterval* temp = temp_intervals_.Get(i); 337 if (ShouldProcess(processing_core_registers_, temp)) { 338 intervals.Add(temp); 339 } 340 } 341 342 return ValidateIntervals(intervals, spill_slots_.Size(), reserved_out_slots_, *codegen_, 343 allocator_, processing_core_registers_, log_fatal_on_failure); 344} 345 346bool RegisterAllocator::ValidateIntervals(const GrowableArray<LiveInterval*>& intervals, 347 size_t number_of_spill_slots, 348 size_t number_of_out_slots, 349 const CodeGenerator& codegen, 350 ArenaAllocator* allocator, 351 bool processing_core_registers, 352 bool log_fatal_on_failure) { 353 size_t number_of_registers = processing_core_registers 354 ? codegen.GetNumberOfCoreRegisters() 355 : codegen.GetNumberOfFloatingPointRegisters(); 356 GrowableArray<ArenaBitVector*> liveness_of_values( 357 allocator, number_of_registers + number_of_spill_slots); 358 359 // Allocate a bit vector per register. A live interval that has a register 360 // allocated will populate the associated bit vector based on its live ranges. 361 for (size_t i = 0; i < number_of_registers + number_of_spill_slots; ++i) { 362 liveness_of_values.Add(new (allocator) ArenaBitVector(allocator, 0, true)); 363 } 364 365 for (size_t i = 0, e = intervals.Size(); i < e; ++i) { 366 for (AllRangesIterator it(intervals.Get(i)); !it.Done(); it.Advance()) { 367 LiveInterval* current = it.CurrentInterval(); 368 HInstruction* defined_by = current->GetParent()->GetDefinedBy(); 369 if (current->GetParent()->HasSpillSlot() 370 // Parameters have their own stack slot. 371 && !(defined_by != nullptr && defined_by->IsParameterValue())) { 372 BitVector* liveness_of_spill_slot = liveness_of_values.Get(number_of_registers 373 + current->GetParent()->GetSpillSlot() / kVRegSize 374 - number_of_out_slots); 375 for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 376 if (liveness_of_spill_slot->IsBitSet(j)) { 377 if (log_fatal_on_failure) { 378 std::ostringstream message; 379 message << "Spill slot conflict at " << j; 380 LOG(FATAL) << message.str(); 381 } else { 382 return false; 383 } 384 } else { 385 liveness_of_spill_slot->SetBit(j); 386 } 387 } 388 } 389 390 if (current->HasRegister()) { 391 BitVector* liveness_of_register = liveness_of_values.Get(current->GetRegister()); 392 for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 393 if (liveness_of_register->IsBitSet(j)) { 394 if (log_fatal_on_failure) { 395 std::ostringstream message; 396 message << "Register conflict at " << j << " "; 397 if (defined_by != nullptr) { 398 message << "(" << defined_by->DebugName() << ")"; 399 } 400 message << "for "; 401 if (processing_core_registers) { 402 codegen.DumpCoreRegister(message, current->GetRegister()); 403 } else { 404 codegen.DumpFloatingPointRegister(message, current->GetRegister()); 405 } 406 LOG(FATAL) << message.str(); 407 } else { 408 return false; 409 } 410 } else { 411 liveness_of_register->SetBit(j); 412 } 413 } 414 } 415 } 416 } 417 return true; 418} 419 420void RegisterAllocator::DumpInterval(std::ostream& stream, LiveInterval* interval) const { 421 interval->Dump(stream); 422 stream << ": "; 423 if (interval->HasRegister()) { 424 if (interval->IsFloatingPoint()) { 425 codegen_->DumpFloatingPointRegister(stream, interval->GetRegister()); 426 } else { 427 codegen_->DumpCoreRegister(stream, interval->GetRegister()); 428 } 429 } else { 430 stream << "spilled"; 431 } 432 stream << std::endl; 433} 434 435// By the book implementation of a linear scan register allocator. 436void RegisterAllocator::LinearScan() { 437 while (!unhandled_->IsEmpty()) { 438 // (1) Remove interval with the lowest start position from unhandled. 439 LiveInterval* current = unhandled_->Pop(); 440 DCHECK(!current->IsFixed() && !current->HasSpillSlot()); 441 DCHECK(unhandled_->IsEmpty() || unhandled_->Peek()->GetStart() >= current->GetStart()); 442 size_t position = current->GetStart(); 443 444 // (2) Remove currently active intervals that are dead at this position. 445 // Move active intervals that have a lifetime hole at this position 446 // to inactive. 447 for (size_t i = 0; i < active_.Size(); ++i) { 448 LiveInterval* interval = active_.Get(i); 449 if (interval->IsDeadAt(position)) { 450 active_.Delete(interval); 451 --i; 452 handled_.Add(interval); 453 } else if (!interval->Covers(position)) { 454 active_.Delete(interval); 455 --i; 456 inactive_.Add(interval); 457 } 458 } 459 460 // (3) Remove currently inactive intervals that are dead at this position. 461 // Move inactive intervals that cover this position to active. 462 for (size_t i = 0; i < inactive_.Size(); ++i) { 463 LiveInterval* interval = inactive_.Get(i); 464 if (interval->IsDeadAt(position)) { 465 inactive_.Delete(interval); 466 --i; 467 handled_.Add(interval); 468 } else if (interval->Covers(position)) { 469 inactive_.Delete(interval); 470 --i; 471 active_.Add(interval); 472 } 473 } 474 475 if (current->IsSlowPathSafepoint()) { 476 // Synthesized interval to record the maximum number of live registers 477 // at safepoints. No need to allocate a register for it. 478 maximum_number_of_live_registers_ = 479 std::max(maximum_number_of_live_registers_, active_.Size()); 480 continue; 481 } 482 483 // (4) Try to find an available register. 484 bool success = TryAllocateFreeReg(current); 485 486 // (5) If no register could be found, we need to spill. 487 if (!success) { 488 success = AllocateBlockedReg(current); 489 } 490 491 // (6) If the interval had a register allocated, add it to the list of active 492 // intervals. 493 if (success) { 494 active_.Add(current); 495 } 496 } 497} 498 499// Find a free register. If multiple are found, pick the register that 500// is free the longest. 501bool RegisterAllocator::TryAllocateFreeReg(LiveInterval* current) { 502 size_t* free_until = registers_array_; 503 504 // First set all registers to be free. 505 for (size_t i = 0; i < number_of_registers_; ++i) { 506 free_until[i] = kMaxLifetimePosition; 507 } 508 509 // For each inactive interval, set its register to be free until 510 // the next intersection with `current`. 511 // Thanks to SSA, this should only be needed for intervals 512 // that are the result of a split. 513 for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { 514 LiveInterval* inactive = inactive_.Get(i); 515 DCHECK(inactive->HasRegister()); 516 size_t next_intersection = inactive->FirstIntersectionWith(current); 517 if (next_intersection != kNoLifetime) { 518 free_until[inactive->GetRegister()] = 519 std::min(free_until[inactive->GetRegister()], next_intersection); 520 } 521 } 522 523 // For each active interval, set its register to not free. 524 for (size_t i = 0, e = active_.Size(); i < e; ++i) { 525 LiveInterval* interval = active_.Get(i); 526 DCHECK(interval->HasRegister()); 527 free_until[interval->GetRegister()] = 0; 528 } 529 530 int reg = -1; 531 if (current->HasRegister()) { 532 // Some instructions have a fixed register output. 533 reg = current->GetRegister(); 534 DCHECK_NE(free_until[reg], 0u); 535 } else { 536 int hint = current->FindFirstRegisterHint(free_until); 537 if (hint != kNoRegister) { 538 DCHECK(!IsBlocked(hint)); 539 reg = hint; 540 } else { 541 // Pick the register that is free the longest. 542 for (size_t i = 0; i < number_of_registers_; ++i) { 543 if (IsBlocked(i)) continue; 544 if (reg == -1 || free_until[i] > free_until[reg]) { 545 reg = i; 546 if (free_until[i] == kMaxLifetimePosition) break; 547 } 548 } 549 } 550 } 551 552 // If we could not find a register, we need to spill. 553 if (reg == -1 || free_until[reg] == 0) { 554 return false; 555 } 556 557 current->SetRegister(reg); 558 if (!current->IsDeadAt(free_until[reg])) { 559 // If the register is only available for a subset of live ranges 560 // covered by `current`, split `current` at the position where 561 // the register is not available anymore. 562 LiveInterval* split = Split(current, free_until[reg]); 563 DCHECK(split != nullptr); 564 AddSorted(unhandled_, split); 565 } 566 return true; 567} 568 569bool RegisterAllocator::IsBlocked(int reg) const { 570 return processing_core_registers_ 571 ? blocked_core_registers_[reg] 572 : blocked_fp_registers_[reg]; 573} 574 575// Find the register that is used the last, and spill the interval 576// that holds it. If the first use of `current` is after that register 577// we spill `current` instead. 578bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) { 579 size_t first_register_use = current->FirstRegisterUse(); 580 if (first_register_use == kNoLifetime) { 581 AllocateSpillSlotFor(current); 582 return false; 583 } 584 585 // First set all registers as not being used. 586 size_t* next_use = registers_array_; 587 for (size_t i = 0; i < number_of_registers_; ++i) { 588 next_use[i] = kMaxLifetimePosition; 589 } 590 591 // For each active interval, find the next use of its register after the 592 // start of current. 593 for (size_t i = 0, e = active_.Size(); i < e; ++i) { 594 LiveInterval* active = active_.Get(i); 595 DCHECK(active->HasRegister()); 596 if (active->IsFixed()) { 597 next_use[active->GetRegister()] = current->GetStart(); 598 } else { 599 size_t use = active->FirstRegisterUseAfter(current->GetStart()); 600 if (use != kNoLifetime) { 601 next_use[active->GetRegister()] = use; 602 } 603 } 604 } 605 606 // For each inactive interval, find the next use of its register after the 607 // start of current. 608 // Thanks to SSA, this should only be needed for intervals 609 // that are the result of a split. 610 for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { 611 LiveInterval* inactive = inactive_.Get(i); 612 DCHECK(inactive->HasRegister()); 613 size_t next_intersection = inactive->FirstIntersectionWith(current); 614 if (next_intersection != kNoLifetime) { 615 if (inactive->IsFixed()) { 616 next_use[inactive->GetRegister()] = 617 std::min(next_intersection, next_use[inactive->GetRegister()]); 618 } else { 619 size_t use = inactive->FirstRegisterUseAfter(current->GetStart()); 620 if (use != kNoLifetime) { 621 next_use[inactive->GetRegister()] = std::min(use, next_use[inactive->GetRegister()]); 622 } 623 } 624 } 625 } 626 627 // Pick the register that is used the last. 628 int reg = -1; 629 for (size_t i = 0; i < number_of_registers_; ++i) { 630 if (IsBlocked(i)) continue; 631 if (reg == -1 || next_use[i] > next_use[reg]) { 632 reg = i; 633 if (next_use[i] == kMaxLifetimePosition) break; 634 } 635 } 636 637 if (first_register_use >= next_use[reg]) { 638 // If the first use of that instruction is after the last use of the found 639 // register, we split this interval just before its first register use. 640 AllocateSpillSlotFor(current); 641 LiveInterval* split = Split(current, first_register_use - 1); 642 DCHECK_NE(current, split) << "There is not enough registers available for " 643 << split->GetParent()->GetDefinedBy()->DebugName(); 644 AddSorted(unhandled_, split); 645 return false; 646 } else { 647 // Use this register and spill the active and inactives interval that 648 // have that register. 649 current->SetRegister(reg); 650 651 for (size_t i = 0, e = active_.Size(); i < e; ++i) { 652 LiveInterval* active = active_.Get(i); 653 if (active->GetRegister() == reg) { 654 DCHECK(!active->IsFixed()); 655 LiveInterval* split = Split(active, current->GetStart()); 656 active_.DeleteAt(i); 657 handled_.Add(active); 658 AddSorted(unhandled_, split); 659 break; 660 } 661 } 662 663 for (size_t i = 0; i < inactive_.Size(); ++i) { 664 LiveInterval* inactive = inactive_.Get(i); 665 if (inactive->GetRegister() == reg) { 666 size_t next_intersection = inactive->FirstIntersectionWith(current); 667 if (next_intersection != kNoLifetime) { 668 if (inactive->IsFixed()) { 669 LiveInterval* split = Split(current, next_intersection); 670 AddSorted(unhandled_, split); 671 } else { 672 LiveInterval* split = Split(inactive, current->GetStart()); 673 inactive_.DeleteAt(i); 674 handled_.Add(inactive); 675 AddSorted(unhandled_, split); 676 --i; 677 } 678 } 679 } 680 } 681 682 return true; 683 } 684} 685 686void RegisterAllocator::AddSorted(GrowableArray<LiveInterval*>* array, LiveInterval* interval) { 687 DCHECK(!interval->IsFixed() && !interval->HasSpillSlot()); 688 size_t insert_at = 0; 689 for (size_t i = array->Size(); i > 0; --i) { 690 LiveInterval* current = array->Get(i - 1); 691 if (current->StartsAfter(interval)) { 692 insert_at = i; 693 break; 694 } 695 } 696 array->InsertAt(insert_at, interval); 697} 698 699LiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) { 700 DCHECK(position >= interval->GetStart()); 701 DCHECK(!interval->IsDeadAt(position)); 702 if (position == interval->GetStart()) { 703 // Spill slot will be allocated when handling `interval` again. 704 interval->ClearRegister(); 705 return interval; 706 } else { 707 LiveInterval* new_interval = interval->SplitAt(position); 708 return new_interval; 709 } 710} 711 712void RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) { 713 LiveInterval* parent = interval->GetParent(); 714 715 // An instruction gets a spill slot for its entire lifetime. If the parent 716 // of this interval already has a spill slot, there is nothing to do. 717 if (parent->HasSpillSlot()) { 718 return; 719 } 720 721 HInstruction* defined_by = parent->GetDefinedBy(); 722 if (defined_by->IsParameterValue()) { 723 // Parameters have their own stack slot. 724 parent->SetSpillSlot(codegen_->GetStackSlotOfParameter(defined_by->AsParameterValue())); 725 return; 726 } 727 728 if (defined_by->IsConstant()) { 729 // Constants don't need a spill slot. 730 return; 731 } 732 733 LiveInterval* last_sibling = interval; 734 while (last_sibling->GetNextSibling() != nullptr) { 735 last_sibling = last_sibling->GetNextSibling(); 736 } 737 size_t end = last_sibling->GetEnd(); 738 739 // Find an available spill slot. 740 size_t slot = 0; 741 for (size_t e = spill_slots_.Size(); slot < e; ++slot) { 742 // We check if it is less rather than less or equal because the parallel move 743 // resolver does not work when a single spill slot needs to be exchanged with 744 // a double spill slot. The strict comparison avoids needing to exchange these 745 // locations at the same lifetime position. 746 if (spill_slots_.Get(slot) < parent->GetStart() 747 && (slot == (e - 1) || spill_slots_.Get(slot + 1) < parent->GetStart())) { 748 break; 749 } 750 } 751 752 if (parent->NeedsTwoSpillSlots()) { 753 if (slot == spill_slots_.Size()) { 754 // We need a new spill slot. 755 spill_slots_.Add(end); 756 spill_slots_.Add(end); 757 } else if (slot == spill_slots_.Size() - 1) { 758 spill_slots_.Put(slot, end); 759 spill_slots_.Add(end); 760 } else { 761 spill_slots_.Put(slot, end); 762 spill_slots_.Put(slot + 1, end); 763 } 764 } else { 765 if (slot == spill_slots_.Size()) { 766 // We need a new spill slot. 767 spill_slots_.Add(end); 768 } else { 769 spill_slots_.Put(slot, end); 770 } 771 } 772 773 parent->SetSpillSlot((slot + reserved_out_slots_) * kVRegSize); 774} 775 776static bool IsValidDestination(Location destination) { 777 return destination.IsRegister() 778 || destination.IsFpuRegister() 779 || destination.IsStackSlot() 780 || destination.IsDoubleStackSlot(); 781} 782 783void RegisterAllocator::AddInputMoveFor(HInstruction* user, 784 Location source, 785 Location destination) const { 786 DCHECK(IsValidDestination(destination)); 787 if (source.Equals(destination)) return; 788 789 DCHECK(!user->IsPhi()); 790 791 HInstruction* previous = user->GetPrevious(); 792 HParallelMove* move = nullptr; 793 if (previous == nullptr 794 || !previous->IsParallelMove() 795 || previous->GetLifetimePosition() < user->GetLifetimePosition()) { 796 move = new (allocator_) HParallelMove(allocator_); 797 move->SetLifetimePosition(user->GetLifetimePosition()); 798 user->GetBlock()->InsertInstructionBefore(move, user); 799 } else { 800 move = previous->AsParallelMove(); 801 } 802 DCHECK_EQ(move->GetLifetimePosition(), user->GetLifetimePosition()); 803 move->AddMove(new (allocator_) MoveOperands(source, destination, nullptr)); 804} 805 806void RegisterAllocator::InsertParallelMoveAt(size_t position, 807 HInstruction* instruction, 808 Location source, 809 Location destination) const { 810 DCHECK(IsValidDestination(destination)); 811 if (source.Equals(destination)) return; 812 813 HInstruction* at = liveness_.GetInstructionFromPosition(position / 2); 814 if (at == nullptr) { 815 // Block boundary, don't no anything the connection of split siblings will handle it. 816 return; 817 } 818 HParallelMove* move; 819 if ((position & 1) == 1) { 820 // Move must happen after the instruction. 821 DCHECK(!at->IsControlFlow()); 822 move = at->GetNext()->AsParallelMove(); 823 // This is a parallel move for connecting siblings in a same block. We need to 824 // differentiate it with moves for connecting blocks, and input moves. 825 if (move == nullptr || move->GetLifetimePosition() > position) { 826 move = new (allocator_) HParallelMove(allocator_); 827 move->SetLifetimePosition(position); 828 at->GetBlock()->InsertInstructionBefore(move, at->GetNext()); 829 } 830 } else { 831 // Move must happen before the instruction. 832 HInstruction* previous = at->GetPrevious(); 833 if (previous == nullptr 834 || !previous->IsParallelMove() 835 || previous->GetLifetimePosition() != position) { 836 // If the previous is a parallel move, then its position must be lower 837 // than the given `position`: it was added just after the non-parallel 838 // move instruction that precedes `instruction`. 839 DCHECK(previous == nullptr 840 || !previous->IsParallelMove() 841 || previous->GetLifetimePosition() < position); 842 move = new (allocator_) HParallelMove(allocator_); 843 move->SetLifetimePosition(position); 844 at->GetBlock()->InsertInstructionBefore(move, at); 845 } else { 846 move = previous->AsParallelMove(); 847 } 848 } 849 DCHECK_EQ(move->GetLifetimePosition(), position); 850 move->AddMove(new (allocator_) MoveOperands(source, destination, instruction)); 851} 852 853void RegisterAllocator::InsertParallelMoveAtExitOf(HBasicBlock* block, 854 HInstruction* instruction, 855 Location source, 856 Location destination) const { 857 DCHECK(IsValidDestination(destination)); 858 if (source.Equals(destination)) return; 859 860 DCHECK_EQ(block->GetSuccessors().Size(), 1u); 861 HInstruction* last = block->GetLastInstruction(); 862 // We insert moves at exit for phi predecessors and connecting blocks. 863 // A block ending with an if cannot branch to a block with phis because 864 // we do not allow critical edges. It can also not connect 865 // a split interval between two blocks: the move has to happen in the successor. 866 DCHECK(!last->IsIf()); 867 HInstruction* previous = last->GetPrevious(); 868 HParallelMove* move; 869 // This is a parallel move for connecting blocks. We need to differentiate 870 // it with moves for connecting siblings in a same block, and output moves. 871 if (previous == nullptr || !previous->IsParallelMove() 872 || previous->AsParallelMove()->GetLifetimePosition() != block->GetLifetimeEnd()) { 873 move = new (allocator_) HParallelMove(allocator_); 874 move->SetLifetimePosition(block->GetLifetimeEnd()); 875 block->InsertInstructionBefore(move, last); 876 } else { 877 move = previous->AsParallelMove(); 878 } 879 move->AddMove(new (allocator_) MoveOperands(source, destination, instruction)); 880} 881 882void RegisterAllocator::InsertParallelMoveAtEntryOf(HBasicBlock* block, 883 HInstruction* instruction, 884 Location source, 885 Location destination) const { 886 DCHECK(IsValidDestination(destination)); 887 if (source.Equals(destination)) return; 888 889 HInstruction* first = block->GetFirstInstruction(); 890 HParallelMove* move = first->AsParallelMove(); 891 // This is a parallel move for connecting blocks. We need to differentiate 892 // it with moves for connecting siblings in a same block, and input moves. 893 if (move == nullptr || move->GetLifetimePosition() != block->GetLifetimeStart()) { 894 move = new (allocator_) HParallelMove(allocator_); 895 move->SetLifetimePosition(block->GetLifetimeStart()); 896 block->InsertInstructionBefore(move, first); 897 } 898 move->AddMove(new (allocator_) MoveOperands(source, destination, instruction)); 899} 900 901void RegisterAllocator::InsertMoveAfter(HInstruction* instruction, 902 Location source, 903 Location destination) const { 904 DCHECK(IsValidDestination(destination)); 905 if (source.Equals(destination)) return; 906 907 if (instruction->IsPhi()) { 908 InsertParallelMoveAtEntryOf(instruction->GetBlock(), instruction, source, destination); 909 return; 910 } 911 912 size_t position = instruction->GetLifetimePosition() + 1; 913 HParallelMove* move = instruction->GetNext()->AsParallelMove(); 914 // This is a parallel move for moving the output of an instruction. We need 915 // to differentiate with input moves, moves for connecting siblings in a 916 // and moves for connecting blocks. 917 if (move == nullptr || move->GetLifetimePosition() != position) { 918 move = new (allocator_) HParallelMove(allocator_); 919 move->SetLifetimePosition(position); 920 instruction->GetBlock()->InsertInstructionBefore(move, instruction->GetNext()); 921 } 922 move->AddMove(new (allocator_) MoveOperands(source, destination, instruction)); 923} 924 925void RegisterAllocator::ConnectSiblings(LiveInterval* interval) { 926 LiveInterval* current = interval; 927 if (current->HasSpillSlot() && current->HasRegister()) { 928 // We spill eagerly, so move must be at definition. 929 InsertMoveAfter(interval->GetDefinedBy(), 930 interval->IsFloatingPoint() 931 ? Location::FpuRegisterLocation(interval->GetRegister()) 932 : Location::RegisterLocation(interval->GetRegister()), 933 interval->NeedsTwoSpillSlots() 934 ? Location::DoubleStackSlot(interval->GetParent()->GetSpillSlot()) 935 : Location::StackSlot(interval->GetParent()->GetSpillSlot())); 936 } 937 UsePosition* use = current->GetFirstUse(); 938 939 // Walk over all siblings, updating locations of use positions, and 940 // connecting them when they are adjacent. 941 do { 942 Location source = current->ToLocation(); 943 944 // Walk over all uses covered by this interval, and update the location 945 // information. 946 while (use != nullptr && use->GetPosition() <= current->GetEnd()) { 947 LocationSummary* locations = use->GetUser()->GetLocations(); 948 if (use->GetIsEnvironment()) { 949 locations->SetEnvironmentAt(use->GetInputIndex(), source); 950 } else { 951 Location expected_location = locations->InAt(use->GetInputIndex()); 952 if (expected_location.IsUnallocated()) { 953 locations->SetInAt(use->GetInputIndex(), source); 954 } else if (!expected_location.IsConstant()) { 955 AddInputMoveFor(use->GetUser(), source, expected_location); 956 } 957 } 958 use = use->GetNext(); 959 } 960 961 // If the next interval starts just after this one, and has a register, 962 // insert a move. 963 LiveInterval* next_sibling = current->GetNextSibling(); 964 if (next_sibling != nullptr 965 && next_sibling->HasRegister() 966 && current->GetEnd() == next_sibling->GetStart()) { 967 Location destination = next_sibling->ToLocation(); 968 InsertParallelMoveAt(current->GetEnd(), interval->GetDefinedBy(), source, destination); 969 } 970 971 // At each safepoint, we record stack and register information. 972 for (size_t i = 0, e = safepoints_.Size(); i < e; ++i) { 973 HInstruction* safepoint = safepoints_.Get(i); 974 size_t position = safepoint->GetLifetimePosition(); 975 LocationSummary* locations = safepoint->GetLocations(); 976 if (!current->Covers(position)) continue; 977 978 if ((current->GetType() == Primitive::kPrimNot) && current->GetParent()->HasSpillSlot()) { 979 locations->SetStackBit(current->GetParent()->GetSpillSlot() / kVRegSize); 980 } 981 982 switch (source.GetKind()) { 983 case Location::kRegister: { 984 locations->AddLiveRegister(source); 985 if (current->GetType() == Primitive::kPrimNot) { 986 locations->SetRegisterBit(source.reg()); 987 } 988 break; 989 } 990 case Location::kFpuRegister: { 991 locations->AddLiveRegister(source); 992 break; 993 } 994 case Location::kStackSlot: // Fall-through 995 case Location::kDoubleStackSlot: // Fall-through 996 case Location::kConstant: { 997 // Nothing to do. 998 break; 999 } 1000 default: { 1001 LOG(FATAL) << "Unexpected location for object"; 1002 } 1003 } 1004 } 1005 current = next_sibling; 1006 } while (current != nullptr); 1007 DCHECK(use == nullptr); 1008} 1009 1010void RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval, 1011 HBasicBlock* from, 1012 HBasicBlock* to) const { 1013 if (interval->GetNextSibling() == nullptr) { 1014 // Nothing to connect. The whole range was allocated to the same location. 1015 return; 1016 } 1017 1018 size_t from_position = from->GetLifetimeEnd() - 1; 1019 // When an instructions dies at entry of another, and the latter is the beginning 1020 // of a block, the register allocator ensures the former has a register 1021 // at block->GetLifetimeStart() + 1. Since this is at a block boundary, it must 1022 // must be handled in this method. 1023 size_t to_position = to->GetLifetimeStart() + 1; 1024 1025 LiveInterval* destination = nullptr; 1026 LiveInterval* source = nullptr; 1027 1028 LiveInterval* current = interval; 1029 1030 // Check the intervals that cover `from` and `to`. 1031 while ((current != nullptr) && (source == nullptr || destination == nullptr)) { 1032 if (current->Covers(from_position)) { 1033 DCHECK(source == nullptr); 1034 source = current; 1035 } 1036 if (current->Covers(to_position)) { 1037 DCHECK(destination == nullptr); 1038 destination = current; 1039 } 1040 1041 current = current->GetNextSibling(); 1042 } 1043 1044 if (destination == source) { 1045 // Interval was not split. 1046 return; 1047 } 1048 1049 DCHECK(destination != nullptr && source != nullptr); 1050 1051 if (!destination->HasRegister()) { 1052 // Values are eagerly spilled. Spill slot already contains appropriate value. 1053 return; 1054 } 1055 1056 // If `from` has only one successor, we can put the moves at the exit of it. Otherwise 1057 // we need to put the moves at the entry of `to`. 1058 if (from->GetSuccessors().Size() == 1) { 1059 InsertParallelMoveAtExitOf(from, 1060 interval->GetParent()->GetDefinedBy(), 1061 source->ToLocation(), 1062 destination->ToLocation()); 1063 } else { 1064 DCHECK_EQ(to->GetPredecessors().Size(), 1u); 1065 InsertParallelMoveAtEntryOf(to, 1066 interval->GetParent()->GetDefinedBy(), 1067 source->ToLocation(), 1068 destination->ToLocation()); 1069 } 1070} 1071 1072void RegisterAllocator::Resolve() { 1073 codegen_->ComputeFrameSize( 1074 spill_slots_.Size(), maximum_number_of_live_registers_, reserved_out_slots_); 1075 1076 // Adjust the Out Location of instructions. 1077 // TODO: Use pointers of Location inside LiveInterval to avoid doing another iteration. 1078 for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { 1079 HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 1080 LiveInterval* current = instruction->GetLiveInterval(); 1081 LocationSummary* locations = instruction->GetLocations(); 1082 Location location = locations->Out(); 1083 if (instruction->IsParameterValue()) { 1084 // Now that we know the frame size, adjust the parameter's location. 1085 if (location.IsStackSlot()) { 1086 location = Location::StackSlot(location.GetStackIndex() + codegen_->GetFrameSize()); 1087 current->SetSpillSlot(location.GetStackIndex()); 1088 locations->SetOut(location); 1089 } else if (location.IsDoubleStackSlot()) { 1090 location = Location::DoubleStackSlot(location.GetStackIndex() + codegen_->GetFrameSize()); 1091 current->SetSpillSlot(location.GetStackIndex()); 1092 locations->SetOut(location); 1093 } else if (current->HasSpillSlot()) { 1094 current->SetSpillSlot(current->GetSpillSlot() + codegen_->GetFrameSize()); 1095 } 1096 } 1097 1098 Location source = current->ToLocation(); 1099 1100 if (location.IsUnallocated()) { 1101 if (location.GetPolicy() == Location::kSameAsFirstInput) { 1102 locations->SetInAt(0, source); 1103 } 1104 locations->SetOut(source); 1105 } else { 1106 DCHECK(source.Equals(location)); 1107 } 1108 } 1109 1110 // Connect siblings. 1111 for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { 1112 HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 1113 ConnectSiblings(instruction->GetLiveInterval()); 1114 } 1115 1116 // Resolve non-linear control flow across branches. Order does not matter. 1117 for (HLinearOrderIterator it(liveness_); !it.Done(); it.Advance()) { 1118 HBasicBlock* block = it.Current(); 1119 BitVector* live = liveness_.GetLiveInSet(*block); 1120 for (uint32_t idx : live->Indexes()) { 1121 HInstruction* current = liveness_.GetInstructionFromSsaIndex(idx); 1122 LiveInterval* interval = current->GetLiveInterval(); 1123 for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { 1124 ConnectSplitSiblings(interval, block->GetPredecessors().Get(i), block); 1125 } 1126 } 1127 } 1128 1129 // Resolve phi inputs. Order does not matter. 1130 for (HLinearOrderIterator it(liveness_); !it.Done(); it.Advance()) { 1131 HBasicBlock* current = it.Current(); 1132 for (HInstructionIterator it(current->GetPhis()); !it.Done(); it.Advance()) { 1133 HInstruction* phi = it.Current(); 1134 for (size_t i = 0, e = current->GetPredecessors().Size(); i < e; ++i) { 1135 HBasicBlock* predecessor = current->GetPredecessors().Get(i); 1136 DCHECK_EQ(predecessor->GetSuccessors().Size(), 1u); 1137 HInstruction* input = phi->InputAt(i); 1138 Location source = input->GetLiveInterval()->GetLocationAt( 1139 predecessor->GetLifetimeEnd() - 1); 1140 Location destination = phi->GetLiveInterval()->ToLocation(); 1141 InsertParallelMoveAtExitOf(predecessor, nullptr, source, destination); 1142 } 1143 } 1144 } 1145 1146 // Assign temp locations. 1147 HInstruction* current = nullptr; 1148 size_t temp_index = 0; 1149 for (size_t i = 0; i < temp_intervals_.Size(); ++i) { 1150 LiveInterval* temp = temp_intervals_.Get(i); 1151 HInstruction* at = liveness_.GetTempUser(temp); 1152 if (at != current) { 1153 temp_index = 0; 1154 current = at; 1155 } 1156 LocationSummary* locations = at->GetLocations(); 1157 DCHECK(temp->GetType() == Primitive::kPrimInt); 1158 locations->SetTempAt( 1159 temp_index++, Location::RegisterLocation(temp->GetRegister())); 1160 } 1161} 1162 1163} // namespace art 1164