register_allocator.cc revision 96f89a290eb67d7bf4b1636798fa28df14309cc7
1a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray/* 2a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * Copyright (C) 2014 The Android Open Source Project 3a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * 4a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * Licensed under the Apache License, Version 2.0 (the "License"); 5a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * you may not use this file except in compliance with the License. 6a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * You may obtain a copy of the License at 7a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * 8a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * http://www.apache.org/licenses/LICENSE-2.0 9a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * 10a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * Unless required by applicable law or agreed to in writing, software 11a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * distributed under the License is distributed on an "AS IS" BASIS, 12a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * See the License for the specific language governing permissions and 14a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * limitations under the License. 15a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray */ 16a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 17a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray#include "register_allocator.h" 18a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 19a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray#include "code_generator.h" 20a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray#include "ssa_liveness_analysis.h" 21a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 22a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraynamespace art { 23a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 24a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraystatic constexpr size_t kMaxLifetimePosition = -1; 2531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffraystatic constexpr size_t kDefaultNumberOfSpillSlots = 4; 26a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 2786dbb9a12119273039ce272b41c809fa548b37b6Nicolas GeoffrayRegisterAllocator::RegisterAllocator(ArenaAllocator* allocator, 2886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray CodeGenerator* codegen, 2986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray const SsaLivenessAnalysis& liveness) 30a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray : allocator_(allocator), 31a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen_(codegen), 3286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray liveness_(liveness), 33a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray unhandled_(allocator, 0), 34a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_(allocator, 0), 35a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_(allocator, 0), 36a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_(allocator, 0), 3786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray physical_register_intervals_(allocator, codegen->GetNumberOfRegisters()), 3831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray spill_slots_(allocator, kDefaultNumberOfSpillSlots), 39a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray processing_core_registers_(false), 40a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray number_of_registers_(-1), 41a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray registers_array_(nullptr), 4286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray blocked_registers_(allocator->AllocArray<bool>(codegen->GetNumberOfRegisters())) { 4386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray codegen->SetupBlockedRegisters(blocked_registers_); 4486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray physical_register_intervals_.SetSize(codegen->GetNumberOfRegisters()); 45a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 46a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 4786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraybool RegisterAllocator::CanAllocateRegistersFor(const HGraph& graph, 4886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InstructionSet instruction_set) { 4986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (!Supports(instruction_set)) { 5086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return false; 5186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 5286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = graph.GetBlocks().Size(); i < e; ++i) { 5386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (HInstructionIterator it(graph.GetBlocks().Get(i)->GetInstructions()); 5486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray !it.Done(); 5586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray it.Advance()) { 5686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* current = it.Current(); 5786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->NeedsEnvironment()) return false; 58412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray if (current->GetType() == Primitive::kPrimLong && instruction_set != kX86_64) return false; 5986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->GetType() == Primitive::kPrimFloat) return false; 6086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->GetType() == Primitive::kPrimDouble) return false; 6186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 6286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 6386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return true; 6486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 6586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 6686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraystatic bool ShouldProcess(bool processing_core_registers, LiveInterval* interval) { 6786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray bool is_core_register = (interval->GetType() != Primitive::kPrimDouble) 6886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && (interval->GetType() != Primitive::kPrimFloat); 69a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return processing_core_registers == is_core_register; 70a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 71a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 7286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::AllocateRegisters() { 7386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray processing_core_registers_ = true; 7486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray AllocateRegistersInternal(); 7586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray processing_core_registers_ = false; 7686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray AllocateRegistersInternal(); 7786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 7886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Resolve(); 7986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 8086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (kIsDebugBuild) { 8186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray processing_core_registers_ = true; 8286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ValidateInternal(true); 8386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray processing_core_registers_ = false; 8486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ValidateInternal(true); 8586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 8686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 8786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 8886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::BlockRegister(Location location, 8986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t start, 9086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t end, 9186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Primitive::Type type) { 9286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray int reg = location.reg().RegId(); 9386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* interval = physical_register_intervals_.Get(reg); 9486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (interval == nullptr) { 9586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray interval = LiveInterval::MakeFixedInterval(allocator_, reg, type); 9686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray physical_register_intervals_.Put(reg, interval); 9786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray inactive_.Add(interval); 9886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 9986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(interval->GetRegister() == reg); 10086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray interval->AddRange(start, end); 10186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 10286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 10320dfc797dc631bf8d655dcf123f46f13332d3074Dave Allison// TODO: make the register allocator understand instructions like HCondition 10420dfc797dc631bf8d655dcf123f46f13332d3074Dave Allison// that may not need to be materialized. It doesn't need to allocate any 10520dfc797dc631bf8d655dcf123f46f13332d3074Dave Allison// registers for it. 10686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::AllocateRegistersInternal() { 107a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray number_of_registers_ = processing_core_registers_ 10886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ? codegen_->GetNumberOfCoreRegisters() 10986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray : codegen_->GetNumberOfFloatingPointRegisters(); 110a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 111a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_); 112a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 113a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Iterate post-order, to ensure the list is sorted, and the last added interval 114a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // is the one with the lowest start position. 11586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = liveness_.GetNumberOfSsaValues(); i > 0; --i) { 11686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i - 1); 11786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = instruction->GetLiveInterval(); 11886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (ShouldProcess(processing_core_registers_, current)) { 119a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(unhandled_.IsEmpty() || current->StartsBefore(unhandled_.Peek())); 120a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 12186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LocationSummary* locations = instruction->GetLocations(); 12286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (locations->GetTempCount() != 0) { 12386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Note that we already filtered out instructions requiring temporaries in 12486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // RegisterAllocator::CanAllocateRegistersFor. 12586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LOG(FATAL) << "Unimplemented"; 12686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 127a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 12886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Some instructions define their output in fixed register/stack slot. We need 12986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // to ensure we know these locations before doing register allocation. For a 13086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // given register, we create an interval that covers these locations. The register 13186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // will be unavailable at these locations when trying to allocate one for an 13286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // interval. 13386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // 13486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // The backwards walking ensures the ranges are ordered on increasing start positions. 13586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location output = locations->Out(); 13686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t position = instruction->GetLifetimePosition(); 13786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (output.IsRegister()) { 13886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Shift the interval's start by one to account for the blocked register. 13986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetFrom(position + 1); 14086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetRegister(output.reg().RegId()); 14186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray BlockRegister(output, position, position + 1, instruction->GetType()); 142412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } else if (output.IsStackSlot() || output.IsDoubleStackSlot()) { 14386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(output.GetStackIndex()); 14486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 14586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0; i < instruction->InputCount(); ++i) { 14686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location input = locations->InAt(i); 14786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (input.IsRegister()) { 14886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray BlockRegister(input, position, position + 1, instruction->InputAt(i)->GetType()); 14986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 15086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 15186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 15286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Add the interval to the correct list. 15386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->HasRegister()) { 15486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(instruction->IsParameterValue()); 15586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray inactive_.Add(current); 15696f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray } else if (current->HasSpillSlot() || instruction->IsConstant()) { 15786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Split before first register use. 15886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t first_register_use = current->FirstRegisterUse(); 15986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (first_register_use != kNoLifetime) { 16086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* split = Split(current, first_register_use - 1); 16196f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray // Don't add direclty to `unhandled_`, it needs to be sorted and the start 16296f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray // of this new interval might be after intervals already in the list. 16386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray AddToUnhandled(split); 16486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 16586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Nothing to do, we won't allocate a register for this value. 16686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 16786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 16886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(unhandled_.IsEmpty() || current->StartsBefore(unhandled_.Peek())); 16986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray unhandled_.Add(current); 17086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 171a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 172a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 17386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 17486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LinearScan(); 175a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 176a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 17731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffrayclass AllRangesIterator : public ValueObject { 17831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray public: 17931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray explicit AllRangesIterator(LiveInterval* interval) 18031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray : current_interval_(interval), 18131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_(interval->GetFirstRange()) {} 18231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 18331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray bool Done() const { return current_interval_ == nullptr; } 18431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveRange* CurrentRange() const { return current_range_; } 18531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* CurrentInterval() const { return current_interval_; } 18631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 18731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray void Advance() { 18831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_ = current_range_->GetNext(); 18931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current_range_ == nullptr) { 19031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_interval_ = current_interval_->GetNextSibling(); 19131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current_interval_ != nullptr) { 19231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_ = current_interval_->GetFirstRange(); 19331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 19431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 19531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 19631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 19731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray private: 19831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* current_interval_; 19931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveRange* current_range_; 20031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 20131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray DISALLOW_COPY_AND_ASSIGN(AllRangesIterator); 20231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray}; 20331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 20486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraybool RegisterAllocator::ValidateInternal(bool log_fatal_on_failure) const { 20586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // To simplify unit testing, we eagerly create the array of intervals, and 20686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // call the helper method. 20786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray GrowableArray<LiveInterval*> intervals(allocator_, 0); 20886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0; i < liveness_.GetNumberOfSsaValues(); ++i) { 20986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 21086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (ShouldProcess(processing_core_registers_, instruction->GetLiveInterval())) { 21186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray intervals.Add(instruction->GetLiveInterval()); 21286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 21386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 21486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 21586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = physical_register_intervals_.Size(); i < e; ++i) { 21686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* fixed = physical_register_intervals_.Get(i); 21786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (fixed != nullptr && ShouldProcess(processing_core_registers_, fixed)) { 21886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray intervals.Add(fixed); 21986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 22086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 22186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 22286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return ValidateIntervals(intervals, spill_slots_.Size(), *codegen_, allocator_, 22386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray processing_core_registers_, log_fatal_on_failure); 22486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 22586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 22631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffraybool RegisterAllocator::ValidateIntervals(const GrowableArray<LiveInterval*>& intervals, 22731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray size_t number_of_spill_slots, 228a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray const CodeGenerator& codegen, 229a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray ArenaAllocator* allocator, 230a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool processing_core_registers, 231a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool log_fatal_on_failure) { 232a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t number_of_registers = processing_core_registers 233a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray ? codegen.GetNumberOfCoreRegisters() 234a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray : codegen.GetNumberOfFloatingPointRegisters(); 23531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray GrowableArray<ArenaBitVector*> liveness_of_values( 23631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray allocator, number_of_registers + number_of_spill_slots); 237a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 238a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Allocate a bit vector per register. A live interval that has a register 239a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // allocated will populate the associated bit vector based on its live ranges. 24031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t i = 0; i < number_of_registers + number_of_spill_slots; ++i) { 24131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_values.Add(new (allocator) ArenaBitVector(allocator, 0, true)); 242a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 243a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 24431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t i = 0, e = intervals.Size(); i < e; ++i) { 24531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (AllRangesIterator it(intervals.Get(i)); !it.Done(); it.Advance()) { 24631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* current = it.CurrentInterval(); 24786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* defined_by = current->GetParent()->GetDefinedBy(); 24886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->GetParent()->HasSpillSlot() 24986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Parameters have their own stack slot. 25086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && !(defined_by != nullptr && defined_by->IsParameterValue())) { 25131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray BitVector* liveness_of_spill_slot = liveness_of_values.Get( 25231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray number_of_registers + current->GetParent()->GetSpillSlot() / kVRegSize); 25331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 25431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (liveness_of_spill_slot->IsBitSet(j)) { 25531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (log_fatal_on_failure) { 25631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray std::ostringstream message; 25731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray message << "Spill slot conflict at " << j; 25831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LOG(FATAL) << message.str(); 25931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 26031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray return false; 26131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 26231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 26331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_spill_slot->SetBit(j); 26431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 26531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 266a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 26731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 26831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current->HasRegister()) { 26931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray BitVector* liveness_of_register = liveness_of_values.Get(current->GetRegister()); 27031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 27131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (liveness_of_register->IsBitSet(j)) { 272a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (log_fatal_on_failure) { 273a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray std::ostringstream message; 274a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray message << "Register conflict at " << j << " for "; 275a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (processing_core_registers) { 276a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen.DumpCoreRegister(message, current->GetRegister()); 277a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 278a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen.DumpFloatingPointRegister(message, current->GetRegister()); 279a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 280a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LOG(FATAL) << message.str(); 281a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 282a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 283a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 284a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 28531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_register->SetBit(j); 286a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 287a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 28831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 28931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 290a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 291a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 292a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 293a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 29486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::DumpInterval(std::ostream& stream, LiveInterval* interval) const { 295a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray interval->Dump(stream); 296a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << ": "; 297a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->HasRegister()) { 298a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (processing_core_registers_) { 29986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray codegen_->DumpCoreRegister(stream, interval->GetRegister()); 300a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 30186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray codegen_->DumpFloatingPointRegister(stream, interval->GetRegister()); 302a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 303a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 304a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << "spilled"; 305a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 306a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << std::endl; 307a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 308a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 309a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// By the book implementation of a linear scan register allocator. 310a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffrayvoid RegisterAllocator::LinearScan() { 311a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray while (!unhandled_.IsEmpty()) { 312a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (1) Remove interval with the lowest start position from unhandled. 313a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* current = unhandled_.Pop(); 31486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(!current->IsFixed() && !current->HasRegister() && !current->HasSpillSlot()); 315a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t position = current->GetStart(); 316a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 317a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (2) Remove currently active intervals that are dead at this position. 318a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Move active intervals that have a lifetime hole at this position 319a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // to inactive. 320a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < active_.Size(); ++i) { 321a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* interval = active_.Get(i); 322a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->IsDeadAt(position)) { 323a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Delete(interval); 324a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 325a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_.Add(interval); 326a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else if (!interval->Covers(position)) { 327a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Delete(interval); 328a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 329a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.Add(interval); 330a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 331a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 332a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 333a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (3) Remove currently inactive intervals that are dead at this position. 334a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Move inactive intervals that cover this position to active. 335a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < inactive_.Size(); ++i) { 336a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* interval = inactive_.Get(i); 337a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->IsDeadAt(position)) { 338a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.Delete(interval); 339a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 340a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_.Add(interval); 341a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else if (interval->Covers(position)) { 342a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.Delete(interval); 343a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 344a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Add(interval); 345a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 346a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 347a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 348a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (4) Try to find an available register. 349a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool success = TryAllocateFreeReg(current); 350a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 351a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (5) If no register could be found, we need to spill. 352a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (!success) { 353a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray success = AllocateBlockedReg(current); 354a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 355a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 356a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (6) If the interval had a register allocated, add it to the list of active 357a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // intervals. 358a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (success) { 359a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Add(current); 360a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 361a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 362a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 363a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 364a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// Find a free register. If multiple are found, pick the register that 365a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// is free the longest. 366a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::TryAllocateFreeReg(LiveInterval* current) { 367a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t* free_until = registers_array_; 368a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 369a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // First set all registers to be free. 370a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 371a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray free_until[i] = kMaxLifetimePosition; 372a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 373a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 374a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each inactive interval, set its register to be free until 375a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // the next intersection with `current`. 376a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Thanks to SSA, this should only be needed for intervals 377a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // that are the result of a split. 378a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { 379a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* inactive = inactive_.Get(i); 380a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(inactive->HasRegister()); 381a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t next_intersection = inactive->FirstIntersectionWith(current); 382a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (next_intersection != kNoLifetime) { 383a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray free_until[inactive->GetRegister()] = next_intersection; 384a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 385a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 386a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 38786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // For each active interval, set its register to not free. 38886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = active_.Size(); i < e; ++i) { 38986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* interval = active_.Get(i); 39086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(interval->HasRegister()); 39186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray free_until[interval->GetRegister()] = 0; 39286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 39386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 394a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Pick the register that is free the longest. 395a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray int reg = -1; 396a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 397a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (IsBlocked(i)) continue; 398a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (reg == -1 || free_until[i] > free_until[reg]) { 399a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray reg = i; 400a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (free_until[i] == kMaxLifetimePosition) break; 401a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 402a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 403a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 404a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // If we could not find a register, we need to spill. 405a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (reg == -1 || free_until[reg] == 0) { 406a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 407a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 408a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 409a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray current->SetRegister(reg); 410a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (!current->IsDeadAt(free_until[reg])) { 411a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // If the register is only available for a subset of live ranges 412a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // covered by `current`, split `current` at the position where 413a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // the register is not available anymore. 414a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* split = Split(current, free_until[reg]); 415a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(split != nullptr); 416a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray AddToUnhandled(split); 417a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 418a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 419a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 420a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 421a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::IsBlocked(int reg) const { 422a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // TODO: This only works for core registers and needs to be adjusted for 423a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // floating point registers. 424a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(processing_core_registers_); 425a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return blocked_registers_[reg]; 426a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 427a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 428a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// Find the register that is used the last, and spill the interval 429a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// that holds it. If the first use of `current` is after that register 430a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// we spill `current` instead. 431a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) { 432a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t first_register_use = current->FirstRegisterUse(); 433412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray if (first_register_use == kNoLifetime) { 43431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray AllocateSpillSlotFor(current); 435a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 436a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 437a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 438a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // First set all registers as not being used. 439a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t* next_use = registers_array_; 440a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 441a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray next_use[i] = kMaxLifetimePosition; 442a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 443a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 444a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each active interval, find the next use of its register after the 445a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // start of current. 446a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = active_.Size(); i < e; ++i) { 447a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* active = active_.Get(i); 448a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(active->HasRegister()); 44986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (active->IsFixed()) { 45086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[active->GetRegister()] = current->GetStart(); 45186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 45286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t use = active->FirstRegisterUseAfter(current->GetStart()); 45386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (use != kNoLifetime) { 45486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[active->GetRegister()] = use; 45586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 456a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 457a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 458a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 459a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each inactive interval, find the next use of its register after the 460a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // start of current. 461a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Thanks to SSA, this should only be needed for intervals 462a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // that are the result of a split. 463a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { 464a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* inactive = inactive_.Get(i); 465a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(inactive->HasRegister()); 46686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t next_intersection = inactive->FirstIntersectionWith(current); 46786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (next_intersection != kNoLifetime) { 46886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (inactive->IsFixed()) { 46986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[inactive->GetRegister()] = 47086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray std::min(next_intersection, next_use[inactive->GetRegister()]); 47186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 47286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t use = inactive->FirstRegisterUseAfter(current->GetStart()); 47386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (use != kNoLifetime) { 47486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[inactive->GetRegister()] = std::min(use, next_use[inactive->GetRegister()]); 47586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 47686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 477a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 478a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 479a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 480a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Pick the register that is used the last. 481a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray int reg = -1; 482a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 483a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (IsBlocked(i)) continue; 484a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (reg == -1 || next_use[i] > next_use[reg]) { 485a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray reg = i; 486a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (next_use[i] == kMaxLifetimePosition) break; 487a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 488a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 489a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 490a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (first_register_use >= next_use[reg]) { 491a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // If the first use of that instruction is after the last use of the found 492a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // register, we split this interval just before its first register use. 49331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray AllocateSpillSlotFor(current); 494a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* split = Split(current, first_register_use - 1); 495a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray AddToUnhandled(split); 496a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 497a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 498a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Use this register and spill the active and inactives interval that 499a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // have that register. 500a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray current->SetRegister(reg); 501a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 502a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = active_.Size(); i < e; ++i) { 503a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* active = active_.Get(i); 504a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (active->GetRegister() == reg) { 50586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(!active->IsFixed()); 506a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* split = Split(active, current->GetStart()); 507a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.DeleteAt(i); 508a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_.Add(active); 509a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray AddToUnhandled(split); 510a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray break; 511a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 512a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 513a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 514a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < inactive_.Size(); ++i) { 515a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* inactive = inactive_.Get(i); 516a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (inactive->GetRegister() == reg) { 51786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t next_intersection = inactive->FirstIntersectionWith(current); 51886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (next_intersection != kNoLifetime) { 51986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (inactive->IsFixed()) { 52086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* split = Split(current, next_intersection); 52186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray AddToUnhandled(split); 52286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 52386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* split = Split(inactive, current->GetStart()); 52486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray inactive_.DeleteAt(i); 52586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray handled_.Add(inactive); 52686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray AddToUnhandled(split); 52786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray --i; 52886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 52986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 530a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 531a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 532a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 533a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 534a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 535a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 536a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 537a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffrayvoid RegisterAllocator::AddToUnhandled(LiveInterval* interval) { 53886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t insert_at = 0; 539a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = unhandled_.Size(); i > 0; --i) { 540a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* current = unhandled_.Get(i - 1); 541a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (current->StartsAfter(interval)) { 54286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray insert_at = i; 543a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray break; 544a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 545a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 54686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray unhandled_.InsertAt(insert_at, interval); 547a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 548a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 549a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas GeoffrayLiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) { 550a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(position >= interval->GetStart()); 551a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(!interval->IsDeadAt(position)); 552a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (position == interval->GetStart()) { 553a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Spill slot will be allocated when handling `interval` again. 554a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray interval->ClearRegister(); 555a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return interval; 556a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 557a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* new_interval = interval->SplitAt(position); 558a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return new_interval; 559a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 560a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 561a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 562412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffraystatic bool NeedTwoSpillSlot(Primitive::Type type) { 563412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray return type == Primitive::kPrimLong || type == Primitive::kPrimDouble; 564412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray} 565412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray 56631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffrayvoid RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) { 56731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* parent = interval->GetParent(); 56831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 56931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // An instruction gets a spill slot for its entire lifetime. If the parent 57031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // of this interval already has a spill slot, there is nothing to do. 57131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (parent->HasSpillSlot()) { 57231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray return; 57331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 57431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 57586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* defined_by = parent->GetDefinedBy(); 57686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (defined_by->IsParameterValue()) { 57786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Parameters have their own stack slot. 57886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray parent->SetSpillSlot(codegen_->GetStackSlotOfParameter(defined_by->AsParameterValue())); 57986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 58086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 58186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 58296f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray if (defined_by->IsConstant()) { 58396f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray // Constants don't need a spill slot. 58496f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray return; 58596f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray } 58696f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray 58731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* last_sibling = interval; 58831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray while (last_sibling->GetNextSibling() != nullptr) { 58931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray last_sibling = last_sibling->GetNextSibling(); 59031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 59131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray size_t end = last_sibling->GetEnd(); 59231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 593412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray if (NeedTwoSpillSlot(parent->GetType())) { 594412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray AllocateTwoSpillSlots(parent, end); 595412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } else { 596412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray AllocateOneSpillSlot(parent, end); 597412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } 598412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray} 599412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray 600412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffrayvoid RegisterAllocator::AllocateTwoSpillSlots(LiveInterval* parent, size_t end) { 601412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // Find an available spill slot. 602412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray size_t slot = 0; 603412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray for (size_t e = spill_slots_.Size(); slot < e; ++slot) { 604412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // We check if it is less rather than less or equal because the parallel move 605412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // resolver does not work when a single spill slot needs to be exchanged with 606412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // a double spill slot. The strict comparison avoids needing to exchange these 607412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // locations at the same lifetime position. 608412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray if (spill_slots_.Get(slot) < parent->GetStart() 609412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray && (slot == (e - 1) || spill_slots_.Get(slot + 1) < parent->GetStart())) { 610412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray break; 611412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } 612412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } 613412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray 614412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray if (slot == spill_slots_.Size()) { 615412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // We need a new spill slot. 616412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray spill_slots_.Add(end); 617412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray spill_slots_.Add(end); 618412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } else if (slot == spill_slots_.Size() - 1) { 619412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray spill_slots_.Put(slot, end); 620412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray spill_slots_.Add(end); 621412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } else { 622412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray spill_slots_.Put(slot, end); 623412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray spill_slots_.Put(slot + 1, end); 624412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } 625412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray 626412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray parent->SetSpillSlot(slot * kVRegSize); 627412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray} 628412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray 629412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffrayvoid RegisterAllocator::AllocateOneSpillSlot(LiveInterval* parent, size_t end) { 63031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // Find an available spill slot. 63131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray size_t slot = 0; 63231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t e = spill_slots_.Size(); slot < e; ++slot) { 63331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (spill_slots_.Get(slot) <= parent->GetStart()) { 63431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray break; 63531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 63631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 63731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 63831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (slot == spill_slots_.Size()) { 63931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // We need a new spill slot. 64031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray spill_slots_.Add(end); 64131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 64231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray spill_slots_.Put(slot, end); 64331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 64431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 64586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray parent->SetSpillSlot(slot * kVRegSize); 64686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 64786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 64886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraystatic Location ConvertToLocation(LiveInterval* interval) { 64986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (interval->HasRegister()) { 65086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return Location::RegisterLocation(ManagedRegister(interval->GetRegister())); 65186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 65296f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray HInstruction* defined_by = interval->GetParent()->GetDefinedBy(); 65396f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray if (defined_by->IsConstant()) { 65496f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray return defined_by->GetLocations()->Out(); 655412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } else { 65696f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray DCHECK(interval->GetParent()->HasSpillSlot()); 65796f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray if (NeedTwoSpillSlot(interval->GetType())) { 65896f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray return Location::DoubleStackSlot(interval->GetParent()->GetSpillSlot()); 65996f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray } else { 66096f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray return Location::StackSlot(interval->GetParent()->GetSpillSlot()); 66196f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray } 662412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } 66386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 66486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 66586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 66686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray// We create a special marker for inputs moves to differentiate them from 66786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray// moves created during resolution. They must be different instructions 66886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray// because the input moves work on the assumption that the interval moves 66986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray// have been executed. 67086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraystatic constexpr size_t kInputMoveLifetimePosition = 0; 67186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraystatic bool IsInputMove(HInstruction* instruction) { 67286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return instruction->GetLifetimePosition() == kInputMoveLifetimePosition; 67386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 67486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 67586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::AddInputMoveFor(HInstruction* instruction, 67686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 67786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 67886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 67986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 68086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(instruction->AsPhi() == nullptr); 68186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 68286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* previous = instruction->GetPrevious(); 68386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move = nullptr; 68486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (previous == nullptr 68586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray || previous->AsParallelMove() == nullptr 68686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray || !IsInputMove(previous)) { 68786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 68886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->SetLifetimePosition(kInputMoveLifetimePosition); 68986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray instruction->GetBlock()->InsertInstructionBefore(move, instruction); 69086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 69186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = previous->AsParallelMove(); 69286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 69386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(IsInputMove(move)); 69486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->AddMove(new (allocator_) MoveOperands(source, destination)); 69586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 69686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 69786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertParallelMoveAt(size_t position, 69886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 69986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 70086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 70186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 70286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* at = liveness_.GetInstructionFromPosition(position / 2); 70386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (at == nullptr) { 70486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Block boundary, don't no anything the connection of split siblings will handle it. 70586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 70686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 70786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move; 70886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if ((position & 1) == 1) { 70986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Move must happen after the instruction. 71086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(!at->IsControlFlow()); 71186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = at->GetNext()->AsParallelMove(); 712e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting siblings in a same block. We need to 713e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // differentiate it with moves for connecting blocks, and input moves. 714e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray if (move == nullptr || move->GetLifetimePosition() != position) { 71586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 71686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->SetLifetimePosition(position); 71786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray at->GetBlock()->InsertInstructionBefore(move, at->GetNext()); 71886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 71986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 72086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Move must happen before the instruction. 72186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* previous = at->GetPrevious(); 72286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (previous != nullptr && previous->AsParallelMove() != nullptr) { 723e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting siblings in a same block. We need to 724e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // differentiate it with moves for connecting blocks, and input moves. 725e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray if (previous->GetLifetimePosition() != position) { 72686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray previous = previous->GetPrevious(); 72786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 72886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 72986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (previous == nullptr || previous->AsParallelMove() == nullptr) { 73086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 73186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->SetLifetimePosition(position); 73286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray at->GetBlock()->InsertInstructionBefore(move, at); 73386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 73486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = previous->AsParallelMove(); 73586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 73686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 73786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->AddMove(new (allocator_) MoveOperands(source, destination)); 73886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 73986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 74086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertParallelMoveAtExitOf(HBasicBlock* block, 74186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 74286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 74386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 74486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 74586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK_EQ(block->GetSuccessors().Size(), 1u); 74686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* last = block->GetLastInstruction(); 74786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* previous = last->GetPrevious(); 74886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move; 749e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting blocks. We need to differentiate 750e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // it with moves for connecting siblings in a same block, and output moves. 751e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray if (previous == nullptr || previous->AsParallelMove() == nullptr 752e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray || previous->AsParallelMove()->GetLifetimePosition() != block->GetLifetimeEnd()) { 75386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 754e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray move->SetLifetimePosition(block->GetLifetimeEnd()); 75586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray block->InsertInstructionBefore(move, last); 75686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 75786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = previous->AsParallelMove(); 75886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 75986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->AddMove(new (allocator_) MoveOperands(source, destination)); 76086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 76186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 76286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertParallelMoveAtEntryOf(HBasicBlock* block, 76386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 76486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 76586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 76686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 76786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* first = block->GetFirstInstruction(); 76886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move = first->AsParallelMove(); 769e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting blocks. We need to differentiate 770e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // it with moves for connecting siblings in a same block, and input moves. 771e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray if (move == nullptr || move->GetLifetimePosition() != block->GetLifetimeStart()) { 77286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 77386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->SetLifetimePosition(block->GetLifetimeStart()); 77486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray block->InsertInstructionBefore(move, first); 77586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 77686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->AddMove(new (allocator_) MoveOperands(source, destination)); 77786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 77886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 77986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertMoveAfter(HInstruction* instruction, 78086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 78186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 78286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 78386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 78486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (instruction->AsPhi() != nullptr) { 78586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InsertParallelMoveAtEntryOf(instruction->GetBlock(), source, destination); 78686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 78786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 78886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 789e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray size_t position = instruction->GetLifetimePosition() + 1; 79086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move = instruction->GetNext()->AsParallelMove(); 791e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for moving the output of an instruction. We need 792e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // to differentiate with input moves, moves for connecting siblings in a 793e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // and moves for connecting blocks. 794e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray if (move == nullptr || move->GetLifetimePosition() != position) { 79586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 796e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray move->SetLifetimePosition(position); 79786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray instruction->GetBlock()->InsertInstructionBefore(move, instruction->GetNext()); 79886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 79986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->AddMove(new (allocator_) MoveOperands(source, destination)); 80086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 80186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 80286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::ConnectSiblings(LiveInterval* interval) { 80386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = interval; 80486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->HasSpillSlot() && current->HasRegister()) { 80586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // We spill eagerly, so move must be at definition. 80686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InsertMoveAfter(interval->GetDefinedBy(), 80786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location::RegisterLocation(ManagedRegister(interval->GetRegister())), 808412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray NeedTwoSpillSlot(interval->GetType()) 809412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray ? Location::DoubleStackSlot(interval->GetParent()->GetSpillSlot()) 810412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray : Location::StackSlot(interval->GetParent()->GetSpillSlot())); 81186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 81286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray UsePosition* use = current->GetFirstUse(); 81386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 81486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Walk over all siblings, updating locations of use positions, and 81586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // connecting them when they are adjacent. 81686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray do { 81786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source = ConvertToLocation(current); 81886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 81986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Walk over all uses covered by this interval, and update the location 82086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // information. 82186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray while (use != nullptr && use->GetPosition() <= current->GetEnd()) { 82286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (!use->GetIsEnvironment()) { 82386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LocationSummary* locations = use->GetUser()->GetLocations(); 82486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location expected_location = locations->InAt(use->GetInputIndex()); 82586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (expected_location.IsUnallocated()) { 82686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray locations->SetInAt(use->GetInputIndex(), source); 82786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 82886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray AddInputMoveFor(use->GetUser(), source, expected_location); 82986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 83086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 83186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray use = use->GetNext(); 83286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 83386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 83486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // If the next interval starts just after this one, and has a register, 83586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // insert a move. 83686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* next_sibling = current->GetNextSibling(); 83786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (next_sibling != nullptr 83886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && next_sibling->HasRegister() 83986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && current->GetEnd() == next_sibling->GetStart()) { 84086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination = ConvertToLocation(next_sibling); 84186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InsertParallelMoveAt(current->GetEnd(), source, destination); 84286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 84386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current = next_sibling; 84486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } while (current != nullptr); 84586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(use == nullptr); 84686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 84786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 84886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval, 84986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* from, 85086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* to) const { 85186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (interval->GetNextSibling() == nullptr) { 85286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Nothing to connect. The whole range was allocated to the same location. 85386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 85486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 85586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 85686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t from_position = from->GetLifetimeEnd() - 1; 85786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t to_position = to->GetLifetimeStart(); 85886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 85986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* destination = nullptr; 86086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* source = nullptr; 86186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 86286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = interval; 86386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 86486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Check the intervals that cover `from` and `to`. 86586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray while ((current != nullptr) && (source == nullptr || destination == nullptr)) { 86686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->Covers(from_position)) { 86786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(source == nullptr); 86886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray source = current; 86986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 87086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->Covers(to_position)) { 87186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(destination == nullptr); 87286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray destination = current; 87386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 87486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 87586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current = current->GetNextSibling(); 87686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 87786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 87886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (destination == source) { 87986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Interval was not split. 88086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 88186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 88286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 88386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (!destination->HasRegister()) { 88486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Values are eagerly spilled. Spill slot already contains appropriate value. 88586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 88686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 88786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 88886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // If `from` has only one successor, we can put the moves at the exit of it. Otherwise 88986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // we need to put the moves at the entry of `to`. 89086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (from->GetSuccessors().Size() == 1) { 89186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InsertParallelMoveAtExitOf(from, ConvertToLocation(source), ConvertToLocation(destination)); 89286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 89386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK_EQ(to->GetPredecessors().Size(), 1u); 89486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InsertParallelMoveAtEntryOf(to, ConvertToLocation(source), ConvertToLocation(destination)); 89586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 89686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 89786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 89886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray// Returns the location of `interval`, or siblings of `interval`, at `position`. 89986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraystatic Location FindLocationAt(LiveInterval* interval, size_t position) { 90086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = interval; 90186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray while (!current->Covers(position)) { 90286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current = current->GetNextSibling(); 90386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(current != nullptr); 90486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 90586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return ConvertToLocation(current); 90686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 90786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 90886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::Resolve() { 90986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray codegen_->ComputeFrameSize(spill_slots_.Size()); 91086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 91186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Adjust the Out Location of instructions. 91286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // TODO: Use pointers of Location inside LiveInterval to avoid doing another iteration. 91386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { 91486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 91586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = instruction->GetLiveInterval(); 91686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LocationSummary* locations = instruction->GetLocations(); 91786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location location = locations->Out(); 91886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (instruction->AsParameterValue() != nullptr) { 91986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Now that we know the frame size, adjust the parameter's location. 92086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (location.IsStackSlot()) { 92186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray location = Location::StackSlot(location.GetStackIndex() + codegen_->GetFrameSize()); 92286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(location.GetStackIndex()); 92386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray locations->SetOut(location); 92486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else if (location.IsDoubleStackSlot()) { 92586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray location = Location::DoubleStackSlot(location.GetStackIndex() + codegen_->GetFrameSize()); 92686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(location.GetStackIndex()); 92786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray locations->SetOut(location); 92886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else if (current->HasSpillSlot()) { 92986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(current->GetSpillSlot() + codegen_->GetFrameSize()); 93086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 93186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 93286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 93386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source = ConvertToLocation(current); 93486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 93586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (location.IsUnallocated()) { 93686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (location.GetPolicy() == Location::kSameAsFirstInput) { 93786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray locations->SetInAt(0, source); 93886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 93986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray locations->SetOut(source); 94086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 94186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(source.Equals(location)); 94286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 94386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 94486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 94586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Connect siblings. 94686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { 94786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 94886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ConnectSiblings(instruction->GetLiveInterval()); 94986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 95086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 95186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Resolve non-linear control flow across branches. Order does not matter. 95286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (HLinearOrderIterator it(liveness_); !it.Done(); it.Advance()) { 95386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* block = it.Current(); 95486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray BitVector* live = liveness_.GetLiveInSet(*block); 95586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (uint32_t idx : live->Indexes()) { 95686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* current = liveness_.GetInstructionFromSsaIndex(idx); 95786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* interval = current->GetLiveInterval(); 95886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { 95986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ConnectSplitSiblings(interval, block->GetPredecessors().Get(i), block); 96086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 96186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 96286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 96386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 96486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Resolve phi inputs. Order does not matter. 96586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (HLinearOrderIterator it(liveness_); !it.Done(); it.Advance()) { 96686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* current = it.Current(); 96786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (HInstructionIterator it(current->GetPhis()); !it.Done(); it.Advance()) { 96886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* phi = it.Current(); 96986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = current->GetPredecessors().Size(); i < e; ++i) { 97086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* predecessor = current->GetPredecessors().Get(i); 97186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK_EQ(predecessor->GetSuccessors().Size(), 1u); 97286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* input = phi->InputAt(i); 97386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source = FindLocationAt(input->GetLiveInterval(), 97486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray predecessor->GetLastInstruction()->GetLifetimePosition()); 97586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination = ConvertToLocation(phi->GetLiveInterval()); 97686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InsertParallelMoveAtExitOf(predecessor, source, destination); 97786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 97886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 97986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 98031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray} 98131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 982a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} // namespace art 983