register_allocator.cc revision aac0f39a3501a7f7dd04b2342c2a16961969f139
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 19e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers#include "base/bit_vector-inl.h" 20a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray#include "code_generator.h" 21a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray#include "ssa_liveness_analysis.h" 22a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 23a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraynamespace art { 24a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 25a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraystatic constexpr size_t kMaxLifetimePosition = -1; 2631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffraystatic constexpr size_t kDefaultNumberOfSpillSlots = 4; 27a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 2886dbb9a12119273039ce272b41c809fa548b37b6Nicolas GeoffrayRegisterAllocator::RegisterAllocator(ArenaAllocator* allocator, 2986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray CodeGenerator* codegen, 3086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray const SsaLivenessAnalysis& liveness) 31a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray : allocator_(allocator), 32a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen_(codegen), 3386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray liveness_(liveness), 343946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_core_intervals_(allocator, 0), 353946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_fp_intervals_(allocator, 0), 363946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_(nullptr), 37a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_(allocator, 0), 38a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_(allocator, 0), 39a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_(allocator, 0), 4086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray physical_register_intervals_(allocator, codegen->GetNumberOfRegisters()), 413946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray temp_intervals_(allocator, 4), 4231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray spill_slots_(allocator, kDefaultNumberOfSpillSlots), 433946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray safepoints_(allocator, 0), 44a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray processing_core_registers_(false), 45a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray number_of_registers_(-1), 46a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray registers_array_(nullptr), 473946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray blocked_registers_(allocator->AllocArray<bool>(codegen->GetNumberOfRegisters())), 483946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray reserved_out_slots_(0) { 4986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray codegen->SetupBlockedRegisters(blocked_registers_); 5086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray physical_register_intervals_.SetSize(codegen->GetNumberOfRegisters()); 513946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Always reserve for the current method and the graph's max out registers. 523946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // TODO: compute it instead. 533946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray reserved_out_slots_ = 1 + codegen->GetGraph()->GetMaximumNumberOfOutVRegs(); 54a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 55a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 5686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraybool RegisterAllocator::CanAllocateRegistersFor(const HGraph& graph, 5786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InstructionSet instruction_set) { 5886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (!Supports(instruction_set)) { 5986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return false; 6086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 6186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = graph.GetBlocks().Size(); i < e; ++i) { 6286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (HInstructionIterator it(graph.GetBlocks().Get(i)->GetInstructions()); 6386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray !it.Done(); 6486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray it.Advance()) { 6586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* current = it.Current(); 66412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray if (current->GetType() == Primitive::kPrimLong && instruction_set != kX86_64) return false; 6786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->GetType() == Primitive::kPrimFloat) return false; 6886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->GetType() == Primitive::kPrimDouble) return false; 6986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 7086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 7186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return true; 7286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 7386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 7486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraystatic bool ShouldProcess(bool processing_core_registers, LiveInterval* interval) { 753946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (interval == nullptr) return false; 7686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray bool is_core_register = (interval->GetType() != Primitive::kPrimDouble) 7786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && (interval->GetType() != Primitive::kPrimFloat); 78a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return processing_core_registers == is_core_register; 79a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 80a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 8186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::AllocateRegisters() { 8286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray AllocateRegistersInternal(); 8386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Resolve(); 8486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 8586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (kIsDebugBuild) { 8686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray processing_core_registers_ = true; 8786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ValidateInternal(true); 8886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray processing_core_registers_ = false; 8986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ValidateInternal(true); 9086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 9186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 9286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 9386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::BlockRegister(Location location, 9486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t start, 9586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t end, 9686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Primitive::Type type) { 9786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray int reg = location.reg().RegId(); 9886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* interval = physical_register_intervals_.Get(reg); 9986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (interval == nullptr) { 10086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray interval = LiveInterval::MakeFixedInterval(allocator_, reg, type); 10186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray physical_register_intervals_.Put(reg, interval); 10286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray inactive_.Add(interval); 10386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 10486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(interval->GetRegister() == reg); 10586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray interval->AddRange(start, end); 10686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 10786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 10886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::AllocateRegistersInternal() { 1093946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Iterate post-order, to ensure the list is sorted, and the last added interval 1103946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // is the one with the lowest start position. 1113946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (HLinearPostOrderIterator it(liveness_); !it.Done(); it.Advance()) { 1123946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray HBasicBlock* block = it.Current(); 1133946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (HBackwardInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 1143946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray ProcessInstruction(it.Current()); 1153946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 1163946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 1173946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray ProcessInstruction(it.Current()); 1183946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 1193946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 120a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1213946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray number_of_registers_ = codegen_->GetNumberOfCoreRegisters(); 122a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_); 1233946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray processing_core_registers_ = true; 1243946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_ = &unhandled_core_intervals_; 1253946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LinearScan(); 126a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1273946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray inactive_.Reset(); 1283946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray active_.Reset(); 1293946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray handled_.Reset(); 130a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1313946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray number_of_registers_ = codegen_->GetNumberOfFloatingPointRegisters(); 1323946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_); 1333946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray processing_core_registers_ = false; 1343946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_ = &unhandled_fp_intervals_; 1353946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // TODO: Enable FP register allocation. 1363946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray DCHECK(unhandled_->IsEmpty()); 1373946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LinearScan(); 1383946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray} 13986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1403946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffrayvoid RegisterAllocator::ProcessInstruction(HInstruction* instruction) { 1413946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LocationSummary* locations = instruction->GetLocations(); 1423946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t position = instruction->GetLifetimePosition(); 1433946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 1443946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (locations == nullptr) return; 1453946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 1463946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Create synthesized intervals for temporaries. 1473946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < locations->GetTempCount(); ++i) { 1483946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray Location temp = locations->GetTemp(i); 1493946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (temp.IsRegister()) { 1503946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray BlockRegister(temp, position, position + 1, Primitive::kPrimInt); 1513946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 1523946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* interval = 1533946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval::MakeTempInterval(allocator_, instruction, Primitive::kPrimInt); 1543946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray temp_intervals_.Add(interval); 1553946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray interval->AddRange(position, position + 1); 1563946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_core_intervals_.Add(interval); 157a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 158a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 15986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1603946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (locations->CanCall()) { 1613946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray codegen_->MarkNotLeaf(); 1623946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray safepoints_.Add(instruction); 1633946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Block all registers. 1643946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < codegen_->GetNumberOfCoreRegisters(); ++i) { 1653946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray BlockRegister(Location::RegisterLocation(ManagedRegister(i)), 1663946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray position, 1673946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray position + 1, 1683946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray Primitive::kPrimInt); 1693946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 1703946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 1713946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 1723946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < instruction->InputCount(); ++i) { 1733946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray Location input = locations->InAt(i); 1743946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (input.IsRegister()) { 1753946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray BlockRegister(input, position, position + 1, instruction->InputAt(i)->GetType()); 1763946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 1773946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 1783946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 1793946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray bool core_register = (instruction->GetType() != Primitive::kPrimDouble) 1803946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray && (instruction->GetType() != Primitive::kPrimFloat); 1813946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray GrowableArray<LiveInterval*>& unhandled = core_register 1823946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray ? unhandled_core_intervals_ 1833946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray : unhandled_fp_intervals_; 1843946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 1853946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* current = instruction->GetLiveInterval(); 1863946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current == nullptr) return; 1873946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 1883946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray DCHECK(unhandled.IsEmpty() || current->StartsBefore(unhandled.Peek())); 1893946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Some instructions define their output in fixed register/stack slot. We need 1903946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // to ensure we know these locations before doing register allocation. For a 1913946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // given register, we create an interval that covers these locations. The register 1923946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // will be unavailable at these locations when trying to allocate one for an 1933946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // interval. 1943946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // 1953946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // The backwards walking ensures the ranges are ordered on increasing start positions. 1963946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray Location output = locations->Out(); 1973946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (output.IsRegister()) { 1983946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Shift the interval's start by one to account for the blocked register. 1993946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray current->SetFrom(position + 1); 2003946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray current->SetRegister(output.reg().RegId()); 2013946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray BlockRegister(output, position, position + 1, instruction->GetType()); 2023946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else if (output.IsStackSlot() || output.IsDoubleStackSlot()) { 2033946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray current->SetSpillSlot(output.GetStackIndex()); 2043946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 2053946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 2063946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // If needed, add interval to the list of unhandled intervals. 2073946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current->HasSpillSlot() || instruction->IsConstant()) { 2083946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Split before first register use. 2093946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t first_register_use = current->FirstRegisterUse(); 2103946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (first_register_use != kNoLifetime) { 2113946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* split = Split(current, first_register_use - 1); 2123946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Don't add direclty to `unhandled`, it needs to be sorted and the start 2133946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // of this new interval might be after intervals already in the list. 2143946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(&unhandled, split); 2153946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 2163946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Nothing to do, we won't allocate a register for this value. 2173946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 2183946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 2193946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray DCHECK(unhandled.IsEmpty() || current->StartsBefore(unhandled.Peek())); 2203946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled.Add(current); 2213946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 222a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 223a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 22431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffrayclass AllRangesIterator : public ValueObject { 22531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray public: 22631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray explicit AllRangesIterator(LiveInterval* interval) 22731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray : current_interval_(interval), 22831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_(interval->GetFirstRange()) {} 22931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 23031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray bool Done() const { return current_interval_ == nullptr; } 23131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveRange* CurrentRange() const { return current_range_; } 23231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* CurrentInterval() const { return current_interval_; } 23331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 23431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray void Advance() { 23531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_ = current_range_->GetNext(); 23631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current_range_ == nullptr) { 23731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_interval_ = current_interval_->GetNextSibling(); 23831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current_interval_ != nullptr) { 23931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_ = current_interval_->GetFirstRange(); 24031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 24131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 24231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 24331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 24431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray private: 24531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* current_interval_; 24631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveRange* current_range_; 24731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 24831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray DISALLOW_COPY_AND_ASSIGN(AllRangesIterator); 24931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray}; 25031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 25186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraybool RegisterAllocator::ValidateInternal(bool log_fatal_on_failure) const { 25286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // To simplify unit testing, we eagerly create the array of intervals, and 25386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // call the helper method. 25486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray GrowableArray<LiveInterval*> intervals(allocator_, 0); 25586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0; i < liveness_.GetNumberOfSsaValues(); ++i) { 25686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 25786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (ShouldProcess(processing_core_registers_, instruction->GetLiveInterval())) { 25886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray intervals.Add(instruction->GetLiveInterval()); 25986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 26086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 26186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 26286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = physical_register_intervals_.Size(); i < e; ++i) { 26386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* fixed = physical_register_intervals_.Get(i); 26486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (fixed != nullptr && ShouldProcess(processing_core_registers_, fixed)) { 26586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray intervals.Add(fixed); 26686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 26786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 26886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 2693946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0, e = temp_intervals_.Size(); i < e; ++i) { 2703946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* temp = temp_intervals_.Get(i); 2713946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (ShouldProcess(processing_core_registers_, temp)) { 2723946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray intervals.Add(temp); 2733946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 2743946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 2753946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 2763946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray return ValidateIntervals(intervals, spill_slots_.Size(), reserved_out_slots_, *codegen_, 2773946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray allocator_, processing_core_registers_, log_fatal_on_failure); 27886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 27986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 28031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffraybool RegisterAllocator::ValidateIntervals(const GrowableArray<LiveInterval*>& intervals, 28131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray size_t number_of_spill_slots, 2823946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t number_of_out_slots, 283a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray const CodeGenerator& codegen, 284a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray ArenaAllocator* allocator, 285a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool processing_core_registers, 286a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool log_fatal_on_failure) { 287a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t number_of_registers = processing_core_registers 288a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray ? codegen.GetNumberOfCoreRegisters() 289a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray : codegen.GetNumberOfFloatingPointRegisters(); 29031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray GrowableArray<ArenaBitVector*> liveness_of_values( 29131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray allocator, number_of_registers + number_of_spill_slots); 292a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 293a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Allocate a bit vector per register. A live interval that has a register 294a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // allocated will populate the associated bit vector based on its live ranges. 29531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t i = 0; i < number_of_registers + number_of_spill_slots; ++i) { 29631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_values.Add(new (allocator) ArenaBitVector(allocator, 0, true)); 297a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 298a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 29931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t i = 0, e = intervals.Size(); i < e; ++i) { 30031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (AllRangesIterator it(intervals.Get(i)); !it.Done(); it.Advance()) { 30131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* current = it.CurrentInterval(); 30286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* defined_by = current->GetParent()->GetDefinedBy(); 30386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->GetParent()->HasSpillSlot() 30486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Parameters have their own stack slot. 30586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && !(defined_by != nullptr && defined_by->IsParameterValue())) { 3063946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray BitVector* liveness_of_spill_slot = liveness_of_values.Get(number_of_registers 3073946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray + current->GetParent()->GetSpillSlot() / kVRegSize 3083946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray - number_of_out_slots); 30931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 31031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (liveness_of_spill_slot->IsBitSet(j)) { 31131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (log_fatal_on_failure) { 31231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray std::ostringstream message; 31331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray message << "Spill slot conflict at " << j; 31431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LOG(FATAL) << message.str(); 31531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 31631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray return false; 31731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 31831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 31931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_spill_slot->SetBit(j); 32031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 32131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 322a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 32331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 32431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current->HasRegister()) { 32531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray BitVector* liveness_of_register = liveness_of_values.Get(current->GetRegister()); 32631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 32731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (liveness_of_register->IsBitSet(j)) { 328a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (log_fatal_on_failure) { 329a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray std::ostringstream message; 3303946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray message << "Register conflict at " << j << " "; 3313946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (defined_by != nullptr) { 3323946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray message << "(" << defined_by->DebugName() << ")"; 3333946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3343946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray message << "for "; 335a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (processing_core_registers) { 336a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen.DumpCoreRegister(message, current->GetRegister()); 337a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 338a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen.DumpFloatingPointRegister(message, current->GetRegister()); 339a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 340a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LOG(FATAL) << message.str(); 341a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 342a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 343a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 344a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 34531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_register->SetBit(j); 346a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 347a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 34831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 34931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 350a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 351a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 352a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 353a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 35486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::DumpInterval(std::ostream& stream, LiveInterval* interval) const { 355a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray interval->Dump(stream); 356a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << ": "; 357a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->HasRegister()) { 358a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (processing_core_registers_) { 35986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray codegen_->DumpCoreRegister(stream, interval->GetRegister()); 360a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 36186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray codegen_->DumpFloatingPointRegister(stream, interval->GetRegister()); 362a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 363a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 364a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << "spilled"; 365a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 366a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << std::endl; 367a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 368a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 369a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// By the book implementation of a linear scan register allocator. 370a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffrayvoid RegisterAllocator::LinearScan() { 3713946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray while (!unhandled_->IsEmpty()) { 372a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (1) Remove interval with the lowest start position from unhandled. 3733946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* current = unhandled_->Pop(); 3743946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray DCHECK(!current->IsFixed() && !current->HasSpillSlot()); 375a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t position = current->GetStart(); 376a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 377a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (2) Remove currently active intervals that are dead at this position. 378a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Move active intervals that have a lifetime hole at this position 379a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // to inactive. 380a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < active_.Size(); ++i) { 381a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* interval = active_.Get(i); 382a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->IsDeadAt(position)) { 383a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Delete(interval); 384a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 385a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_.Add(interval); 386a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else if (!interval->Covers(position)) { 387a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Delete(interval); 388a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 389a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.Add(interval); 390a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 391a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 392a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 393a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (3) Remove currently inactive intervals that are dead at this position. 394a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Move inactive intervals that cover this position to active. 395a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < inactive_.Size(); ++i) { 396a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* interval = inactive_.Get(i); 397a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->IsDeadAt(position)) { 398a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.Delete(interval); 399a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 400a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_.Add(interval); 401a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else if (interval->Covers(position)) { 402a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.Delete(interval); 403a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 404a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Add(interval); 405a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 406a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 407a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 408a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (4) Try to find an available register. 409a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool success = TryAllocateFreeReg(current); 410a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 411a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (5) If no register could be found, we need to spill. 412a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (!success) { 413a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray success = AllocateBlockedReg(current); 414a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 415a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 416a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (6) If the interval had a register allocated, add it to the list of active 417a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // intervals. 418a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (success) { 419a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Add(current); 420a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 421a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 422a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 423a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 424a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// Find a free register. If multiple are found, pick the register that 425a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// is free the longest. 426a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::TryAllocateFreeReg(LiveInterval* current) { 427a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t* free_until = registers_array_; 428a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 429a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // First set all registers to be free. 430a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 431a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray free_until[i] = kMaxLifetimePosition; 432a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 433a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 434a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each inactive interval, set its register to be free until 435a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // the next intersection with `current`. 436a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Thanks to SSA, this should only be needed for intervals 437a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // that are the result of a split. 438a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { 439a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* inactive = inactive_.Get(i); 440a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(inactive->HasRegister()); 441a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t next_intersection = inactive->FirstIntersectionWith(current); 442a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (next_intersection != kNoLifetime) { 443aac0f39a3501a7f7dd04b2342c2a16961969f139Nicolas Geoffray free_until[inactive->GetRegister()] = 444aac0f39a3501a7f7dd04b2342c2a16961969f139Nicolas Geoffray std::min(free_until[inactive->GetRegister()], next_intersection); 445a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 446a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 447a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 44886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // For each active interval, set its register to not free. 44986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = active_.Size(); i < e; ++i) { 45086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* interval = active_.Get(i); 45186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(interval->HasRegister()); 45286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray free_until[interval->GetRegister()] = 0; 45386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 45486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 455a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray int reg = -1; 4563946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current->HasRegister()) { 4573946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Some instructions have a fixed register output. 4583946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray reg = current->GetRegister(); 4593946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray DCHECK_NE(free_until[reg], 0u); 4603946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 4613946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Pick the register that is free the longest. 4623946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 4633946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (IsBlocked(i)) continue; 4643946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (reg == -1 || free_until[i] > free_until[reg]) { 4653946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray reg = i; 4663946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (free_until[i] == kMaxLifetimePosition) break; 4673946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 468a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 469a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 470a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 471a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // If we could not find a register, we need to spill. 472a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (reg == -1 || free_until[reg] == 0) { 473a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 474a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 475a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 476a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray current->SetRegister(reg); 477a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (!current->IsDeadAt(free_until[reg])) { 478a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // If the register is only available for a subset of live ranges 479a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // covered by `current`, split `current` at the position where 480a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // the register is not available anymore. 481a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* split = Split(current, free_until[reg]); 482a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(split != nullptr); 4833946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 484a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 485a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 486a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 487a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 488a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::IsBlocked(int reg) const { 489a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // TODO: This only works for core registers and needs to be adjusted for 490a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // floating point registers. 491a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(processing_core_registers_); 492a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return blocked_registers_[reg]; 493a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 494a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 495a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// Find the register that is used the last, and spill the interval 496a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// that holds it. If the first use of `current` is after that register 497a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// we spill `current` instead. 498a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) { 499a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t first_register_use = current->FirstRegisterUse(); 500412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray if (first_register_use == kNoLifetime) { 50131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray AllocateSpillSlotFor(current); 502a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 503a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 504a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 505a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // First set all registers as not being used. 506a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t* next_use = registers_array_; 507a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 508a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray next_use[i] = kMaxLifetimePosition; 509a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 510a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 511a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each active interval, find the next use of its register after the 512a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // start of current. 513a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = active_.Size(); i < e; ++i) { 514a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* active = active_.Get(i); 515a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(active->HasRegister()); 51686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (active->IsFixed()) { 51786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[active->GetRegister()] = current->GetStart(); 51886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 51986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t use = active->FirstRegisterUseAfter(current->GetStart()); 52086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (use != kNoLifetime) { 52186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[active->GetRegister()] = use; 52286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 523a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 524a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 525a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 526a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each inactive interval, find the next use of its register after the 527a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // start of current. 528a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Thanks to SSA, this should only be needed for intervals 529a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // that are the result of a split. 530a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { 531a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* inactive = inactive_.Get(i); 532a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(inactive->HasRegister()); 53386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t next_intersection = inactive->FirstIntersectionWith(current); 53486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (next_intersection != kNoLifetime) { 53586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (inactive->IsFixed()) { 53686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[inactive->GetRegister()] = 53786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray std::min(next_intersection, next_use[inactive->GetRegister()]); 53886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 53986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t use = inactive->FirstRegisterUseAfter(current->GetStart()); 54086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (use != kNoLifetime) { 54186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[inactive->GetRegister()] = std::min(use, next_use[inactive->GetRegister()]); 54286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 54386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 544a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 545a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 546a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 547a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Pick the register that is used the last. 548a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray int reg = -1; 549a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 550a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (IsBlocked(i)) continue; 551a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (reg == -1 || next_use[i] > next_use[reg]) { 552a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray reg = i; 553a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (next_use[i] == kMaxLifetimePosition) break; 554a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 555a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 556a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 557a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (first_register_use >= next_use[reg]) { 558a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // If the first use of that instruction is after the last use of the found 559a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // register, we split this interval just before its first register use. 56031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray AllocateSpillSlotFor(current); 561a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* split = Split(current, first_register_use - 1); 5623946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 563a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 564a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 565a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Use this register and spill the active and inactives interval that 566a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // have that register. 567a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray current->SetRegister(reg); 568a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 569a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = active_.Size(); i < e; ++i) { 570a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* active = active_.Get(i); 571a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (active->GetRegister() == reg) { 57286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(!active->IsFixed()); 573a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* split = Split(active, current->GetStart()); 574a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.DeleteAt(i); 575a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_.Add(active); 5763946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 577a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray break; 578a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 579a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 580a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 581a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < inactive_.Size(); ++i) { 582a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* inactive = inactive_.Get(i); 583a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (inactive->GetRegister() == reg) { 58486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t next_intersection = inactive->FirstIntersectionWith(current); 58586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (next_intersection != kNoLifetime) { 58686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (inactive->IsFixed()) { 58786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* split = Split(current, next_intersection); 5883946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 58986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 59086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* split = Split(inactive, current->GetStart()); 59186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray inactive_.DeleteAt(i); 59286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray handled_.Add(inactive); 5933946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 59486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray --i; 59586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 59686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 597a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 598a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 599a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 600a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 601a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 602a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 603a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 6043946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffrayvoid RegisterAllocator::AddSorted(GrowableArray<LiveInterval*>* array, LiveInterval* interval) { 60586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t insert_at = 0; 6063946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = array->Size(); i > 0; --i) { 6073946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* current = array->Get(i - 1); 608a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (current->StartsAfter(interval)) { 60986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray insert_at = i; 610a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray break; 611a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 612a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 6133946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray array->InsertAt(insert_at, interval); 614a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 615a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 616a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas GeoffrayLiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) { 617a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(position >= interval->GetStart()); 618a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(!interval->IsDeadAt(position)); 619a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (position == interval->GetStart()) { 620a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Spill slot will be allocated when handling `interval` again. 621a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray interval->ClearRegister(); 622a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return interval; 623a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 624a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* new_interval = interval->SplitAt(position); 625a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return new_interval; 626a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 627a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 628a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 629412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffraystatic bool NeedTwoSpillSlot(Primitive::Type type) { 630412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray return type == Primitive::kPrimLong || type == Primitive::kPrimDouble; 631412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray} 632412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray 63331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffrayvoid RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) { 63431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* parent = interval->GetParent(); 63531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 63631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // An instruction gets a spill slot for its entire lifetime. If the parent 63731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // of this interval already has a spill slot, there is nothing to do. 63831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (parent->HasSpillSlot()) { 63931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray return; 64031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 64131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 64286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* defined_by = parent->GetDefinedBy(); 64386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (defined_by->IsParameterValue()) { 64486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Parameters have their own stack slot. 64586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray parent->SetSpillSlot(codegen_->GetStackSlotOfParameter(defined_by->AsParameterValue())); 64686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 64786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 64886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 64996f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray if (defined_by->IsConstant()) { 65096f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray // Constants don't need a spill slot. 65196f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray return; 65296f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray } 65396f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray 65431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* last_sibling = interval; 65531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray while (last_sibling->GetNextSibling() != nullptr) { 65631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray last_sibling = last_sibling->GetNextSibling(); 65731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 65831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray size_t end = last_sibling->GetEnd(); 65931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 660412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray if (NeedTwoSpillSlot(parent->GetType())) { 661412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray AllocateTwoSpillSlots(parent, end); 662412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } else { 663412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray AllocateOneSpillSlot(parent, end); 664412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } 665412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray} 666412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray 667412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffrayvoid RegisterAllocator::AllocateTwoSpillSlots(LiveInterval* parent, size_t end) { 668412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // Find an available spill slot. 669412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray size_t slot = 0; 670412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray for (size_t e = spill_slots_.Size(); slot < e; ++slot) { 671412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // We check if it is less rather than less or equal because the parallel move 672412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // resolver does not work when a single spill slot needs to be exchanged with 673412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // a double spill slot. The strict comparison avoids needing to exchange these 674412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // locations at the same lifetime position. 675412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray if (spill_slots_.Get(slot) < parent->GetStart() 676412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray && (slot == (e - 1) || spill_slots_.Get(slot + 1) < parent->GetStart())) { 677412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray break; 678412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } 679412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } 680412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray 681412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray if (slot == spill_slots_.Size()) { 682412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // We need a new spill slot. 683412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray spill_slots_.Add(end); 684412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray spill_slots_.Add(end); 685412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } else if (slot == spill_slots_.Size() - 1) { 686412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray spill_slots_.Put(slot, end); 687412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray spill_slots_.Add(end); 688412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } else { 689412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray spill_slots_.Put(slot, end); 690412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray spill_slots_.Put(slot + 1, end); 691412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } 692412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray 6933946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray parent->SetSpillSlot((slot + reserved_out_slots_) * kVRegSize); 694412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray} 695412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray 696412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffrayvoid RegisterAllocator::AllocateOneSpillSlot(LiveInterval* parent, size_t end) { 69731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // Find an available spill slot. 69831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray size_t slot = 0; 69931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t e = spill_slots_.Size(); slot < e; ++slot) { 70031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (spill_slots_.Get(slot) <= parent->GetStart()) { 70131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray break; 70231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 70331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 70431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 70531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (slot == spill_slots_.Size()) { 70631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // We need a new spill slot. 70731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray spill_slots_.Add(end); 70831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 70931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray spill_slots_.Put(slot, end); 71031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 71131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 7123946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray parent->SetSpillSlot((slot + reserved_out_slots_) * kVRegSize); 71386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 71486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 71586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraystatic Location ConvertToLocation(LiveInterval* interval) { 71686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (interval->HasRegister()) { 71786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return Location::RegisterLocation(ManagedRegister(interval->GetRegister())); 71886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 71996f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray HInstruction* defined_by = interval->GetParent()->GetDefinedBy(); 72096f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray if (defined_by->IsConstant()) { 72196f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray return defined_by->GetLocations()->Out(); 722412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } else { 72396f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray DCHECK(interval->GetParent()->HasSpillSlot()); 72496f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray if (NeedTwoSpillSlot(interval->GetType())) { 72596f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray return Location::DoubleStackSlot(interval->GetParent()->GetSpillSlot()); 72696f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray } else { 72796f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray return Location::StackSlot(interval->GetParent()->GetSpillSlot()); 72896f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray } 729412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } 73086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 73186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 73286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 73386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray// We create a special marker for inputs moves to differentiate them from 73486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray// moves created during resolution. They must be different instructions 73586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray// because the input moves work on the assumption that the interval moves 73686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray// have been executed. 73786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraystatic constexpr size_t kInputMoveLifetimePosition = 0; 73886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraystatic bool IsInputMove(HInstruction* instruction) { 73986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return instruction->GetLifetimePosition() == kInputMoveLifetimePosition; 74086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 74186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 7422a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffraystatic bool IsValidDestination(Location destination) { 7432a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray return destination.IsRegister() || destination.IsStackSlot() || destination.IsDoubleStackSlot(); 7442a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray} 7452a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray 74686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::AddInputMoveFor(HInstruction* instruction, 74786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 74886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 7492a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray DCHECK(IsValidDestination(destination)); 75086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 75186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 75286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(instruction->AsPhi() == nullptr); 75386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 75486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* previous = instruction->GetPrevious(); 75586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move = nullptr; 75686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (previous == nullptr 75786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray || previous->AsParallelMove() == nullptr 75886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray || !IsInputMove(previous)) { 75986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 76086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->SetLifetimePosition(kInputMoveLifetimePosition); 76186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray instruction->GetBlock()->InsertInstructionBefore(move, instruction); 76286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 76386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = previous->AsParallelMove(); 76486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 76586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(IsInputMove(move)); 76686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->AddMove(new (allocator_) MoveOperands(source, destination)); 76786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 76886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 76986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertParallelMoveAt(size_t position, 77086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 77186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 7722a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray DCHECK(IsValidDestination(destination)); 77386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 77486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 77586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* at = liveness_.GetInstructionFromPosition(position / 2); 77686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (at == nullptr) { 77786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Block boundary, don't no anything the connection of split siblings will handle it. 77886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 77986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 78086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move; 78186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if ((position & 1) == 1) { 78286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Move must happen after the instruction. 78386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(!at->IsControlFlow()); 78486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = at->GetNext()->AsParallelMove(); 785e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting siblings in a same block. We need to 786e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // differentiate it with moves for connecting blocks, and input moves. 787e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray if (move == nullptr || move->GetLifetimePosition() != position) { 78886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 78986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->SetLifetimePosition(position); 79086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray at->GetBlock()->InsertInstructionBefore(move, at->GetNext()); 79186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 79286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 79386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Move must happen before the instruction. 79486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* previous = at->GetPrevious(); 79586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (previous != nullptr && previous->AsParallelMove() != nullptr) { 796e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting siblings in a same block. We need to 797e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // differentiate it with moves for connecting blocks, and input moves. 798e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray if (previous->GetLifetimePosition() != position) { 79986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray previous = previous->GetPrevious(); 80086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 80186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 80286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (previous == nullptr || previous->AsParallelMove() == nullptr) { 80386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 80486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->SetLifetimePosition(position); 80586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray at->GetBlock()->InsertInstructionBefore(move, at); 80686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 80786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = previous->AsParallelMove(); 80886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 80986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 81086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->AddMove(new (allocator_) MoveOperands(source, destination)); 81186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 81286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 81386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertParallelMoveAtExitOf(HBasicBlock* block, 81486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 81586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 8162a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray DCHECK(IsValidDestination(destination)); 81786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 81886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 81986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK_EQ(block->GetSuccessors().Size(), 1u); 82086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* last = block->GetLastInstruction(); 82186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* previous = last->GetPrevious(); 82286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move; 823e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting blocks. We need to differentiate 824e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // it with moves for connecting siblings in a same block, and output moves. 825e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray if (previous == nullptr || previous->AsParallelMove() == nullptr 826e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray || previous->AsParallelMove()->GetLifetimePosition() != block->GetLifetimeEnd()) { 82786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 828e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray move->SetLifetimePosition(block->GetLifetimeEnd()); 82986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray block->InsertInstructionBefore(move, last); 83086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 83186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = previous->AsParallelMove(); 83286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 83386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->AddMove(new (allocator_) MoveOperands(source, destination)); 83486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 83586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 83686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertParallelMoveAtEntryOf(HBasicBlock* block, 83786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 83886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 8392a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray DCHECK(IsValidDestination(destination)); 84086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 84186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 84286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* first = block->GetFirstInstruction(); 84386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move = first->AsParallelMove(); 844e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting blocks. We need to differentiate 845e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // it with moves for connecting siblings in a same block, and input moves. 846e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray if (move == nullptr || move->GetLifetimePosition() != block->GetLifetimeStart()) { 84786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 84886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->SetLifetimePosition(block->GetLifetimeStart()); 84986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray block->InsertInstructionBefore(move, first); 85086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 85186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->AddMove(new (allocator_) MoveOperands(source, destination)); 85286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 85386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 85486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertMoveAfter(HInstruction* instruction, 85586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 85686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 8572a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray DCHECK(IsValidDestination(destination)); 85886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 85986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 86086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (instruction->AsPhi() != nullptr) { 86186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InsertParallelMoveAtEntryOf(instruction->GetBlock(), source, destination); 86286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 86386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 86486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 865e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray size_t position = instruction->GetLifetimePosition() + 1; 86686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move = instruction->GetNext()->AsParallelMove(); 867e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for moving the output of an instruction. We need 868e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // to differentiate with input moves, moves for connecting siblings in a 869e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // and moves for connecting blocks. 870e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray if (move == nullptr || move->GetLifetimePosition() != position) { 87186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 872e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray move->SetLifetimePosition(position); 87386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray instruction->GetBlock()->InsertInstructionBefore(move, instruction->GetNext()); 87486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 87586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->AddMove(new (allocator_) MoveOperands(source, destination)); 87686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 87786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 87886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::ConnectSiblings(LiveInterval* interval) { 87986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = interval; 88086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->HasSpillSlot() && current->HasRegister()) { 88186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // We spill eagerly, so move must be at definition. 88286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InsertMoveAfter(interval->GetDefinedBy(), 88386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location::RegisterLocation(ManagedRegister(interval->GetRegister())), 884412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray NeedTwoSpillSlot(interval->GetType()) 885412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray ? Location::DoubleStackSlot(interval->GetParent()->GetSpillSlot()) 886412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray : Location::StackSlot(interval->GetParent()->GetSpillSlot())); 88786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 88886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray UsePosition* use = current->GetFirstUse(); 88986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 89086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Walk over all siblings, updating locations of use positions, and 89186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // connecting them when they are adjacent. 89286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray do { 89386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source = ConvertToLocation(current); 89486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 89586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Walk over all uses covered by this interval, and update the location 89686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // information. 89786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray while (use != nullptr && use->GetPosition() <= current->GetEnd()) { 8983946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LocationSummary* locations = use->GetUser()->GetLocations(); 8993946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (use->GetIsEnvironment()) { 9003946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray locations->SetEnvironmentAt(use->GetInputIndex(), source); 9013946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 90286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location expected_location = locations->InAt(use->GetInputIndex()); 90386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (expected_location.IsUnallocated()) { 90486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray locations->SetInAt(use->GetInputIndex(), source); 9052a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray } else if (!expected_location.IsConstant()) { 90686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray AddInputMoveFor(use->GetUser(), source, expected_location); 90786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 90886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 90986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray use = use->GetNext(); 91086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 91186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 91286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // If the next interval starts just after this one, and has a register, 91386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // insert a move. 91486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* next_sibling = current->GetNextSibling(); 91586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (next_sibling != nullptr 91686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && next_sibling->HasRegister() 91786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && current->GetEnd() == next_sibling->GetStart()) { 91886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination = ConvertToLocation(next_sibling); 91986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InsertParallelMoveAt(current->GetEnd(), source, destination); 92086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 9213946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 9223946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // At each safepoint, we record stack and register information. 9233946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0, e = safepoints_.Size(); i < e; ++i) { 9243946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray HInstruction* safepoint = safepoints_.Get(i); 9253946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t position = safepoint->GetLifetimePosition(); 9263946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LocationSummary* locations = safepoint->GetLocations(); 9273946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (!current->Covers(position)) continue; 9283946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 9293946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current->GetType() == Primitive::kPrimNot) { 9303946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray DCHECK(current->GetParent()->HasSpillSlot()); 9313946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray locations->SetStackBit(current->GetParent()->GetSpillSlot() / kVRegSize); 9323946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 9333946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 9343946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray switch (source.GetKind()) { 9353946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kRegister: { 9363946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray locations->SetLiveRegister(source.reg().RegId()); 9373946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current->GetType() == Primitive::kPrimNot) { 9383946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray locations->SetRegisterBit(source.reg().RegId()); 9393946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 9403946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray break; 9413946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 9423946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kStackSlot: // Fall-through 9433946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kDoubleStackSlot: // Fall-through 9443946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kConstant: { 9453946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Nothing to do. 9463946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray break; 9473946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 9483946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray default: { 9493946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LOG(FATAL) << "Unexpected location for object"; 9503946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 9513946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 9523946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 95386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current = next_sibling; 95486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } while (current != nullptr); 95586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(use == nullptr); 95686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 95786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 95886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval, 95986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* from, 96086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* to) const { 96186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (interval->GetNextSibling() == nullptr) { 96286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Nothing to connect. The whole range was allocated to the same location. 96386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 96486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 96586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 96686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t from_position = from->GetLifetimeEnd() - 1; 96786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t to_position = to->GetLifetimeStart(); 96886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 96986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* destination = nullptr; 97086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* source = nullptr; 97186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 97286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = interval; 97386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 97486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Check the intervals that cover `from` and `to`. 97586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray while ((current != nullptr) && (source == nullptr || destination == nullptr)) { 97686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->Covers(from_position)) { 97786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(source == nullptr); 97886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray source = current; 97986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 98086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->Covers(to_position)) { 98186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(destination == nullptr); 98286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray destination = current; 98386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 98486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 98586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current = current->GetNextSibling(); 98686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 98786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 98886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (destination == source) { 98986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Interval was not split. 99086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 99186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 99286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 99386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (!destination->HasRegister()) { 99486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Values are eagerly spilled. Spill slot already contains appropriate value. 99586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 99686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 99786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 99886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // If `from` has only one successor, we can put the moves at the exit of it. Otherwise 99986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // we need to put the moves at the entry of `to`. 100086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (from->GetSuccessors().Size() == 1) { 100186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InsertParallelMoveAtExitOf(from, ConvertToLocation(source), ConvertToLocation(destination)); 100286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 100386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK_EQ(to->GetPredecessors().Size(), 1u); 100486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InsertParallelMoveAtEntryOf(to, ConvertToLocation(source), ConvertToLocation(destination)); 100586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 100686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 100786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 100886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray// Returns the location of `interval`, or siblings of `interval`, at `position`. 100986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraystatic Location FindLocationAt(LiveInterval* interval, size_t position) { 101086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = interval; 101186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray while (!current->Covers(position)) { 101286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current = current->GetNextSibling(); 101386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(current != nullptr); 101486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 101586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return ConvertToLocation(current); 101686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 101786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 101886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::Resolve() { 10193946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray codegen_->ComputeFrameSize(spill_slots_.Size(), reserved_out_slots_); 102086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 102186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Adjust the Out Location of instructions. 102286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // TODO: Use pointers of Location inside LiveInterval to avoid doing another iteration. 102386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { 102486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 102586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = instruction->GetLiveInterval(); 102686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LocationSummary* locations = instruction->GetLocations(); 102786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location location = locations->Out(); 102886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (instruction->AsParameterValue() != nullptr) { 102986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Now that we know the frame size, adjust the parameter's location. 103086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (location.IsStackSlot()) { 103186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray location = Location::StackSlot(location.GetStackIndex() + codegen_->GetFrameSize()); 103286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(location.GetStackIndex()); 103386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray locations->SetOut(location); 103486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else if (location.IsDoubleStackSlot()) { 103586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray location = Location::DoubleStackSlot(location.GetStackIndex() + codegen_->GetFrameSize()); 103686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(location.GetStackIndex()); 103786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray locations->SetOut(location); 103886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else if (current->HasSpillSlot()) { 103986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(current->GetSpillSlot() + codegen_->GetFrameSize()); 104086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 104186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 104286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 104386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source = ConvertToLocation(current); 104486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 104586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (location.IsUnallocated()) { 104686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (location.GetPolicy() == Location::kSameAsFirstInput) { 104786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray locations->SetInAt(0, source); 104886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 104986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray locations->SetOut(source); 105086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 105186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(source.Equals(location)); 105286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 105386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 105486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 105586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Connect siblings. 105686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { 105786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 105886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ConnectSiblings(instruction->GetLiveInterval()); 105986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 106086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 106186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Resolve non-linear control flow across branches. Order does not matter. 106286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (HLinearOrderIterator it(liveness_); !it.Done(); it.Advance()) { 106386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* block = it.Current(); 106486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray BitVector* live = liveness_.GetLiveInSet(*block); 106586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (uint32_t idx : live->Indexes()) { 106686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* current = liveness_.GetInstructionFromSsaIndex(idx); 106786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* interval = current->GetLiveInterval(); 106886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { 106986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ConnectSplitSiblings(interval, block->GetPredecessors().Get(i), block); 107086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 107186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 107286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 107386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 107486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Resolve phi inputs. Order does not matter. 107586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (HLinearOrderIterator it(liveness_); !it.Done(); it.Advance()) { 107686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* current = it.Current(); 107786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (HInstructionIterator it(current->GetPhis()); !it.Done(); it.Advance()) { 107886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* phi = it.Current(); 107986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = current->GetPredecessors().Size(); i < e; ++i) { 108086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* predecessor = current->GetPredecessors().Get(i); 108186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK_EQ(predecessor->GetSuccessors().Size(), 1u); 108286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* input = phi->InputAt(i); 108386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source = FindLocationAt(input->GetLiveInterval(), 108486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray predecessor->GetLastInstruction()->GetLifetimePosition()); 108586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination = ConvertToLocation(phi->GetLiveInterval()); 108686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InsertParallelMoveAtExitOf(predecessor, source, destination); 108786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 108886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 108986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 10903946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 10913946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Assign temp locations. 10923946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray HInstruction* current = nullptr; 10933946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t temp_index = 0; 10943946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < temp_intervals_.Size(); ++i) { 10953946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* temp = temp_intervals_.Get(i); 10963946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (temp->GetDefinedBy() != current) { 10973946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray temp_index = 0; 10983946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray current = temp->GetDefinedBy(); 10993946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 11003946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LocationSummary* locations = current->GetLocations(); 11013946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray locations->SetTempAt( 11023946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray temp_index++, Location::RegisterLocation(ManagedRegister(temp->GetRegister()))); 11033946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 110431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray} 110531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 1106a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} // namespace art 1107