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