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