register_allocator.cc revision c8147a76ed2f440f38329dc08ff889d393b5c535
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), 40102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_core_register_intervals_(allocator, codegen->GetNumberOfCoreRegisters()), 41102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_fp_register_intervals_(allocator, codegen->GetNumberOfFloatingPointRegisters()), 423946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray temp_intervals_(allocator, 4), 4331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray spill_slots_(allocator, kDefaultNumberOfSpillSlots), 443946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray safepoints_(allocator, 0), 45a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray processing_core_registers_(false), 46a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray number_of_registers_(-1), 47a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray registers_array_(nullptr), 48102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray blocked_core_registers_(codegen->GetBlockedCoreRegisters()), 49102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray blocked_fp_registers_(codegen->GetBlockedFloatingPointRegisters()), 503bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray reserved_out_slots_(0), 513bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray maximum_number_of_live_registers_(0) { 5271175b7f19a4f6cf9cc264feafd820dbafa371fbNicolas Geoffray codegen->SetupBlockedRegisters(); 53102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_core_register_intervals_.SetSize(codegen->GetNumberOfCoreRegisters()); 54102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_fp_register_intervals_.SetSize(codegen->GetNumberOfFloatingPointRegisters()); 553946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Always reserve for the current method and the graph's max out registers. 563946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // TODO: compute it instead. 573946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray reserved_out_slots_ = 1 + codegen->GetGraph()->GetMaximumNumberOfOutVRegs(); 58a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 59a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 6086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraybool RegisterAllocator::CanAllocateRegistersFor(const HGraph& graph, 6186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InstructionSet instruction_set) { 6286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (!Supports(instruction_set)) { 6386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return false; 6486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 6586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = graph.GetBlocks().Size(); i < e; ++i) { 6686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (HInstructionIterator it(graph.GetBlocks().Get(i)->GetInstructions()); 6786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray !it.Done(); 6886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray it.Advance()) { 6986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* current = it.Current(); 70412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray if (current->GetType() == Primitive::kPrimLong && instruction_set != kX86_64) return false; 71102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if ((current->GetType() == Primitive::kPrimFloat || current->GetType() == Primitive::kPrimDouble) 72102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray && instruction_set != kX86_64) { 73102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return false; 74102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 7586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 7686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 7786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return true; 7886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 7986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 8086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraystatic bool ShouldProcess(bool processing_core_registers, LiveInterval* interval) { 813946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (interval == nullptr) return false; 8286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray bool is_core_register = (interval->GetType() != Primitive::kPrimDouble) 8386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && (interval->GetType() != Primitive::kPrimFloat); 84a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return processing_core_registers == is_core_register; 85a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 86a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 8786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::AllocateRegisters() { 8886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray AllocateRegistersInternal(); 8986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Resolve(); 9086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 9186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (kIsDebugBuild) { 9286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray processing_core_registers_ = true; 9386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ValidateInternal(true); 9486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray processing_core_registers_ = false; 9586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ValidateInternal(true); 9686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 9786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 9886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 9986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::BlockRegister(Location location, 10086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t start, 101102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray size_t end) { 10256b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray int reg = location.reg(); 103102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray DCHECK(location.IsRegister() || location.IsFpuRegister()); 104102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* interval = location.IsRegister() 105102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ? physical_core_register_intervals_.Get(reg) 106102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray : physical_fp_register_intervals_.Get(reg); 107102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray Primitive::Type type = location.IsRegister() 108102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ? Primitive::kPrimInt 109102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray : Primitive::kPrimDouble; 11086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (interval == nullptr) { 11186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray interval = LiveInterval::MakeFixedInterval(allocator_, reg, type); 112102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (location.IsRegister()) { 113102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_core_register_intervals_.Put(reg, interval); 114102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 115102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_fp_register_intervals_.Put(reg, interval); 116102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 11786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 11886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(interval->GetRegister() == reg); 11986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray interval->AddRange(start, end); 12086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 12186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 12286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::AllocateRegistersInternal() { 1233946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Iterate post-order, to ensure the list is sorted, and the last added interval 1243946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // is the one with the lowest start position. 1253946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (HLinearPostOrderIterator it(liveness_); !it.Done(); it.Advance()) { 1263946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray HBasicBlock* block = it.Current(); 1273946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (HBackwardInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 1283946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray ProcessInstruction(it.Current()); 1293946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 1303946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { 1313946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray ProcessInstruction(it.Current()); 1323946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 1333946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 134a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1353946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray number_of_registers_ = codegen_->GetNumberOfCoreRegisters(); 136a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_); 1373946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray processing_core_registers_ = true; 1383946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_ = &unhandled_core_intervals_; 139102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0, e = physical_core_register_intervals_.Size(); i < e; ++i) { 140102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* fixed = physical_core_register_intervals_.Get(i); 141102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (fixed != nullptr) { 142102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray inactive_.Add(fixed); 143102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 144102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 1453946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LinearScan(); 146a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 147102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray size_t saved_maximum_number_of_live_registers = maximum_number_of_live_registers_; 148102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray maximum_number_of_live_registers_ = 0; 149102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray 1503946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray inactive_.Reset(); 1513946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray active_.Reset(); 1523946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray handled_.Reset(); 153a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1543946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray number_of_registers_ = codegen_->GetNumberOfFloatingPointRegisters(); 1553946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_); 1563946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray processing_core_registers_ = false; 1573946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_ = &unhandled_fp_intervals_; 158102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0, e = physical_fp_register_intervals_.Size(); i < e; ++i) { 159102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* fixed = physical_fp_register_intervals_.Get(i); 160102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (fixed != nullptr) { 161102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray inactive_.Add(fixed); 162102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 163102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 1643946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LinearScan(); 165102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray maximum_number_of_live_registers_ += saved_maximum_number_of_live_registers; 1663946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray} 16786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1683946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffrayvoid RegisterAllocator::ProcessInstruction(HInstruction* instruction) { 1693946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LocationSummary* locations = instruction->GetLocations(); 1703946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t position = instruction->GetLifetimePosition(); 1713946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 1723946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (locations == nullptr) return; 1733946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 1743946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Create synthesized intervals for temporaries. 1753946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < locations->GetTempCount(); ++i) { 1763946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray Location temp = locations->GetTemp(i); 1773946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (temp.IsRegister()) { 178102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray BlockRegister(temp, position, position + 1); 1793946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 180102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray DCHECK(temp.IsUnallocated()); 18101ef345767ea609417fc511e42007705c9667546Nicolas Geoffray LiveInterval* interval = LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimInt); 1823946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray temp_intervals_.Add(interval); 1833946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray interval->AddRange(position, position + 1); 1843946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_core_intervals_.Add(interval); 185a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 186a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 18786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1883bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray bool core_register = (instruction->GetType() != Primitive::kPrimDouble) 1893bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray && (instruction->GetType() != Primitive::kPrimFloat); 1903bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray 1913946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (locations->CanCall()) { 1923bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray if (!instruction->IsSuspendCheck()) { 1933bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray codegen_->MarkNotLeaf(); 1943bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 1953946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray safepoints_.Add(instruction); 1963bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray if (locations->OnlyCallsOnSlowPath()) { 1973bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // We add a synthesized range at this position to record the live registers 1983bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // at this position. Ideally, we could just update the safepoints when locations 1993bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // are updated, but we currently need to know the full stack size before updating 2003bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // locations (because of parameters and the fact that we don't have a frame pointer). 2013bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // And knowing the full stack size requires to know the maximum number of live 2023bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // registers at calls in slow paths. 2033bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // By adding the following interval in the algorithm, we can compute this 2043bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // maximum before updating locations. 2053bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray LiveInterval* interval = LiveInterval::MakeSlowPathInterval(allocator_, instruction); 2063bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray interval->AddRange(position, position + 1); 207102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray unhandled_core_intervals_.Add(interval); 208102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray unhandled_fp_intervals_.Add(interval); 2093bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 2103bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 2113bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray 2123bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray if (locations->WillCall()) { 2133946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Block all registers. 2143946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < codegen_->GetNumberOfCoreRegisters(); ++i) { 21556b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray BlockRegister(Location::RegisterLocation(i), 2163946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray position, 217102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray position + 1); 218102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 219102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0; i < codegen_->GetNumberOfFloatingPointRegisters(); ++i) { 220102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray BlockRegister(Location::FpuRegisterLocation(i), 221102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray position, 222102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray position + 1); 2233946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 2243946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 2253946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 2263946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < instruction->InputCount(); ++i) { 2273946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray Location input = locations->InAt(i); 228102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (input.IsRegister() || input.IsFpuRegister()) { 229102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray BlockRegister(input, position, position + 1); 2303946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 2313946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 2323946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 2333946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* current = instruction->GetLiveInterval(); 2343946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current == nullptr) return; 2353946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 236102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray GrowableArray<LiveInterval*>& unhandled = core_register 237102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ? unhandled_core_intervals_ 238102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray : unhandled_fp_intervals_; 239102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray 2407690562d40878f44823d5fb03a2084cfc677ec4aNicolas Geoffray DCHECK(unhandled.IsEmpty() || current->StartsBeforeOrAt(unhandled.Peek())); 2413946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Some instructions define their output in fixed register/stack slot. We need 2423946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // to ensure we know these locations before doing register allocation. For a 2433946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // given register, we create an interval that covers these locations. The register 2443946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // will be unavailable at these locations when trying to allocate one for an 2453946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // interval. 2463946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // 2473946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // The backwards walking ensures the ranges are ordered on increasing start positions. 2483946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray Location output = locations->Out(); 249102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (output.IsRegister() || output.IsFpuRegister()) { 2503946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Shift the interval's start by one to account for the blocked register. 2513946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray current->SetFrom(position + 1); 25256b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray current->SetRegister(output.reg()); 253102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray BlockRegister(output, position, position + 1); 2548e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray } else if (!locations->OutputOverlapsWithInputs()) { 2558e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray // Shift the interval's start by one to not interfere with the inputs. 2568e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray current->SetFrom(position + 1); 2573946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else if (output.IsStackSlot() || output.IsDoubleStackSlot()) { 2583946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray current->SetSpillSlot(output.GetStackIndex()); 2593946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 2603946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 2613946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // If needed, add interval to the list of unhandled intervals. 2623946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current->HasSpillSlot() || instruction->IsConstant()) { 263c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray // Split just before first register use. 2643946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t first_register_use = current->FirstRegisterUse(); 2653946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (first_register_use != kNoLifetime) { 266c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray LiveInterval* split = Split(current, first_register_use - 1); 2673946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Don't add direclty to `unhandled`, it needs to be sorted and the start 2683946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // of this new interval might be after intervals already in the list. 2693946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(&unhandled, split); 2703946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 2713946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Nothing to do, we won't allocate a register for this value. 2723946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 2733946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 2747690562d40878f44823d5fb03a2084cfc677ec4aNicolas Geoffray DCHECK(unhandled.IsEmpty() || current->StartsBeforeOrAt(unhandled.Peek())); 2753946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled.Add(current); 2763946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 277a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 278a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 27931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffrayclass AllRangesIterator : public ValueObject { 28031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray public: 28131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray explicit AllRangesIterator(LiveInterval* interval) 28231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray : current_interval_(interval), 28331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_(interval->GetFirstRange()) {} 28431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 28531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray bool Done() const { return current_interval_ == nullptr; } 28631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveRange* CurrentRange() const { return current_range_; } 28731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* CurrentInterval() const { return current_interval_; } 28831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 28931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray void Advance() { 29031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_ = current_range_->GetNext(); 29131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current_range_ == nullptr) { 29231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_interval_ = current_interval_->GetNextSibling(); 29331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current_interval_ != nullptr) { 29431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_ = current_interval_->GetFirstRange(); 29531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 29631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 29731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 29831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 29931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray private: 30031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* current_interval_; 30131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveRange* current_range_; 30231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 30331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray DISALLOW_COPY_AND_ASSIGN(AllRangesIterator); 30431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray}; 30531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 30686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraybool RegisterAllocator::ValidateInternal(bool log_fatal_on_failure) const { 30786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // To simplify unit testing, we eagerly create the array of intervals, and 30886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // call the helper method. 30986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray GrowableArray<LiveInterval*> intervals(allocator_, 0); 31086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0; i < liveness_.GetNumberOfSsaValues(); ++i) { 31186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 31286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (ShouldProcess(processing_core_registers_, instruction->GetLiveInterval())) { 31386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray intervals.Add(instruction->GetLiveInterval()); 31486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 31586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 31686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 317102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (processing_core_registers_) { 318102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0, e = physical_core_register_intervals_.Size(); i < e; ++i) { 319102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* fixed = physical_core_register_intervals_.Get(i); 320102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (fixed != nullptr) { 321102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray intervals.Add(fixed); 322102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 323102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 324102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 325102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0, e = physical_fp_register_intervals_.Size(); i < e; ++i) { 326102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* fixed = physical_fp_register_intervals_.Get(i); 327102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (fixed != nullptr) { 328102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray intervals.Add(fixed); 329102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 33086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 33186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 33286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 3333946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0, e = temp_intervals_.Size(); i < e; ++i) { 3343946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* temp = temp_intervals_.Get(i); 3353946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (ShouldProcess(processing_core_registers_, temp)) { 3363946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray intervals.Add(temp); 3373946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3383946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3393946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 3403946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray return ValidateIntervals(intervals, spill_slots_.Size(), reserved_out_slots_, *codegen_, 3413946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray allocator_, processing_core_registers_, log_fatal_on_failure); 34286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 34386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 34431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffraybool RegisterAllocator::ValidateIntervals(const GrowableArray<LiveInterval*>& intervals, 34531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray size_t number_of_spill_slots, 3463946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t number_of_out_slots, 347a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray const CodeGenerator& codegen, 348a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray ArenaAllocator* allocator, 349a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool processing_core_registers, 350a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool log_fatal_on_failure) { 351a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t number_of_registers = processing_core_registers 352a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray ? codegen.GetNumberOfCoreRegisters() 353a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray : codegen.GetNumberOfFloatingPointRegisters(); 35431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray GrowableArray<ArenaBitVector*> liveness_of_values( 35531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray allocator, number_of_registers + number_of_spill_slots); 356a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 357a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Allocate a bit vector per register. A live interval that has a register 358a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // allocated will populate the associated bit vector based on its live ranges. 35931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t i = 0; i < number_of_registers + number_of_spill_slots; ++i) { 36031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_values.Add(new (allocator) ArenaBitVector(allocator, 0, true)); 361a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 362a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 36331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t i = 0, e = intervals.Size(); i < e; ++i) { 36431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (AllRangesIterator it(intervals.Get(i)); !it.Done(); it.Advance()) { 36531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* current = it.CurrentInterval(); 36686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* defined_by = current->GetParent()->GetDefinedBy(); 36786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->GetParent()->HasSpillSlot() 36886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Parameters have their own stack slot. 36986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && !(defined_by != nullptr && defined_by->IsParameterValue())) { 3703946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray BitVector* liveness_of_spill_slot = liveness_of_values.Get(number_of_registers 3713946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray + current->GetParent()->GetSpillSlot() / kVRegSize 3723946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray - number_of_out_slots); 37331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 37431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (liveness_of_spill_slot->IsBitSet(j)) { 37531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (log_fatal_on_failure) { 37631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray std::ostringstream message; 37731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray message << "Spill slot conflict at " << j; 37831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LOG(FATAL) << message.str(); 37931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 38031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray return false; 38131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 38231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 38331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_spill_slot->SetBit(j); 38431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 38531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 386a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 38731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 38831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current->HasRegister()) { 38931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray BitVector* liveness_of_register = liveness_of_values.Get(current->GetRegister()); 39031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 39131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (liveness_of_register->IsBitSet(j)) { 392a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (log_fatal_on_failure) { 393a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray std::ostringstream message; 3943946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray message << "Register conflict at " << j << " "; 3953946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (defined_by != nullptr) { 3963946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray message << "(" << defined_by->DebugName() << ")"; 3973946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3983946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray message << "for "; 399a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (processing_core_registers) { 400a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen.DumpCoreRegister(message, current->GetRegister()); 401a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 402a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen.DumpFloatingPointRegister(message, current->GetRegister()); 403a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 404a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LOG(FATAL) << message.str(); 405a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 406a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 407a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 408a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 40931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_register->SetBit(j); 410a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 411a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 41231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 41331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 414a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 415a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 416a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 417a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 41886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::DumpInterval(std::ostream& stream, LiveInterval* interval) const { 419a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray interval->Dump(stream); 420a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << ": "; 421a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->HasRegister()) { 422102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (interval->IsFloatingPoint()) { 42386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray codegen_->DumpFloatingPointRegister(stream, interval->GetRegister()); 424102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 425102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray codegen_->DumpCoreRegister(stream, interval->GetRegister()); 426a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 427a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 428a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << "spilled"; 429a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 430a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << std::endl; 431a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 432a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 433a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// By the book implementation of a linear scan register allocator. 434a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffrayvoid RegisterAllocator::LinearScan() { 4353946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray while (!unhandled_->IsEmpty()) { 436a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (1) Remove interval with the lowest start position from unhandled. 4373946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* current = unhandled_->Pop(); 4383946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray DCHECK(!current->IsFixed() && !current->HasSpillSlot()); 439c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray DCHECK(unhandled_->IsEmpty() || unhandled_->Peek()->GetStart() >= current->GetStart()); 440a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t position = current->GetStart(); 441a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 442a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (2) Remove currently active intervals that are dead at this position. 443a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Move active intervals that have a lifetime hole at this position 444a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // to inactive. 445a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < active_.Size(); ++i) { 446a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* interval = active_.Get(i); 447a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->IsDeadAt(position)) { 448a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Delete(interval); 449a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 450a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_.Add(interval); 451a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else if (!interval->Covers(position)) { 452a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Delete(interval); 453a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 454a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.Add(interval); 455a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 456a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 457a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 458a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (3) Remove currently inactive intervals that are dead at this position. 459a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Move inactive intervals that cover this position to active. 460a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < inactive_.Size(); ++i) { 461a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* interval = inactive_.Get(i); 462a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->IsDeadAt(position)) { 463a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.Delete(interval); 464a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 465a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_.Add(interval); 466a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else if (interval->Covers(position)) { 467a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.Delete(interval); 468a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 469a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Add(interval); 470a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 471a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 472a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 4733bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray if (current->IsSlowPathSafepoint()) { 4743bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // Synthesized interval to record the maximum number of live registers 4753bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // at safepoints. No need to allocate a register for it. 4763bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray maximum_number_of_live_registers_ = 4773bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray std::max(maximum_number_of_live_registers_, active_.Size()); 4783bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray continue; 4793bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 4803bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray 481a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (4) Try to find an available register. 482a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool success = TryAllocateFreeReg(current); 483a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 484a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (5) If no register could be found, we need to spill. 485a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (!success) { 486a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray success = AllocateBlockedReg(current); 487a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 488a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 489a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (6) If the interval had a register allocated, add it to the list of active 490a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // intervals. 491a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (success) { 492a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Add(current); 493a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 494a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 495a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 496a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 497a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// Find a free register. If multiple are found, pick the register that 498a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// is free the longest. 499a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::TryAllocateFreeReg(LiveInterval* current) { 500a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t* free_until = registers_array_; 501a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 502a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // First set all registers to be free. 503a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 504a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray free_until[i] = kMaxLifetimePosition; 505a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 506a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 507a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each inactive interval, set its register to be free until 508a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // the next intersection with `current`. 509a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Thanks to SSA, this should only be needed for intervals 510a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // that are the result of a split. 511a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { 512a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* inactive = inactive_.Get(i); 513a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(inactive->HasRegister()); 514a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t next_intersection = inactive->FirstIntersectionWith(current); 515a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (next_intersection != kNoLifetime) { 516aac0f39a3501a7f7dd04b2342c2a16961969f139Nicolas Geoffray free_until[inactive->GetRegister()] = 517aac0f39a3501a7f7dd04b2342c2a16961969f139Nicolas Geoffray std::min(free_until[inactive->GetRegister()], next_intersection); 518a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 519a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 520a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 52186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // For each active interval, set its register to not free. 52286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = active_.Size(); i < e; ++i) { 52386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* interval = active_.Get(i); 52486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(interval->HasRegister()); 52586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray free_until[interval->GetRegister()] = 0; 52686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 52786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 528a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray int reg = -1; 5293946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current->HasRegister()) { 5303946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Some instructions have a fixed register output. 5313946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray reg = current->GetRegister(); 5323946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray DCHECK_NE(free_until[reg], 0u); 5333946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 53401ef345767ea609417fc511e42007705c9667546Nicolas Geoffray int hint = current->FindFirstRegisterHint(free_until); 53501ef345767ea609417fc511e42007705c9667546Nicolas Geoffray if (hint != kNoRegister) { 53601ef345767ea609417fc511e42007705c9667546Nicolas Geoffray DCHECK(!IsBlocked(hint)); 53701ef345767ea609417fc511e42007705c9667546Nicolas Geoffray reg = hint; 53801ef345767ea609417fc511e42007705c9667546Nicolas Geoffray } else { 53901ef345767ea609417fc511e42007705c9667546Nicolas Geoffray // Pick the register that is free the longest. 54001ef345767ea609417fc511e42007705c9667546Nicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 54101ef345767ea609417fc511e42007705c9667546Nicolas Geoffray if (IsBlocked(i)) continue; 54201ef345767ea609417fc511e42007705c9667546Nicolas Geoffray if (reg == -1 || free_until[i] > free_until[reg]) { 54301ef345767ea609417fc511e42007705c9667546Nicolas Geoffray reg = i; 54401ef345767ea609417fc511e42007705c9667546Nicolas Geoffray if (free_until[i] == kMaxLifetimePosition) break; 54501ef345767ea609417fc511e42007705c9667546Nicolas Geoffray } 5463946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 547a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 548a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 549a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 550a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // If we could not find a register, we need to spill. 551a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (reg == -1 || free_until[reg] == 0) { 552a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 553a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 554a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 555a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray current->SetRegister(reg); 556a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (!current->IsDeadAt(free_until[reg])) { 557a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // If the register is only available for a subset of live ranges 558a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // covered by `current`, split `current` at the position where 559a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // the register is not available anymore. 560a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* split = Split(current, free_until[reg]); 561a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(split != nullptr); 5623946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 563a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 564a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 565a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 566a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 567a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::IsBlocked(int reg) const { 568102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return processing_core_registers_ 569102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ? blocked_core_registers_[reg] 570102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray : blocked_fp_registers_[reg]; 571a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 572a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 573a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// Find the register that is used the last, and spill the interval 574a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// that holds it. If the first use of `current` is after that register 575a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// we spill `current` instead. 576a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) { 577a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t first_register_use = current->FirstRegisterUse(); 578412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray if (first_register_use == kNoLifetime) { 57931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray AllocateSpillSlotFor(current); 580a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 581a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 582a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 583a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // First set all registers as not being used. 584a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t* next_use = registers_array_; 585a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 586a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray next_use[i] = kMaxLifetimePosition; 587a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 588a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 589a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each active interval, find the next use of its register after the 590a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // start of current. 591a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = active_.Size(); i < e; ++i) { 592a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* active = active_.Get(i); 593a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(active->HasRegister()); 59486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (active->IsFixed()) { 59586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[active->GetRegister()] = current->GetStart(); 59686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 59786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t use = active->FirstRegisterUseAfter(current->GetStart()); 59886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (use != kNoLifetime) { 59986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[active->GetRegister()] = use; 60086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 601a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 602a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 603a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 604a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each inactive interval, find the next use of its register after the 605a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // start of current. 606a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Thanks to SSA, this should only be needed for intervals 607a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // that are the result of a split. 608a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { 609a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* inactive = inactive_.Get(i); 610a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(inactive->HasRegister()); 61186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t next_intersection = inactive->FirstIntersectionWith(current); 61286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (next_intersection != kNoLifetime) { 61386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (inactive->IsFixed()) { 61486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[inactive->GetRegister()] = 61586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray std::min(next_intersection, next_use[inactive->GetRegister()]); 61686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 61786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t use = inactive->FirstRegisterUseAfter(current->GetStart()); 61886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (use != kNoLifetime) { 61986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[inactive->GetRegister()] = std::min(use, next_use[inactive->GetRegister()]); 62086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 62186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 622a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 623a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 624a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 625a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Pick the register that is used the last. 626a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray int reg = -1; 627a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 628a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (IsBlocked(i)) continue; 629a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (reg == -1 || next_use[i] > next_use[reg]) { 630a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray reg = i; 631a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (next_use[i] == kMaxLifetimePosition) break; 632a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 633a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 634a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 635a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (first_register_use >= next_use[reg]) { 636a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // If the first use of that instruction is after the last use of the found 637a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // register, we split this interval just before its first register use. 63831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray AllocateSpillSlotFor(current); 639c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray LiveInterval* split = Split(current, first_register_use - 1); 640c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray DCHECK_NE(current, split) << "There is not enough registers available for " 641c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray << split->GetParent()->GetDefinedBy()->DebugName(); 6423946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 643a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 644a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 645a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Use this register and spill the active and inactives interval that 646a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // have that register. 647a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray current->SetRegister(reg); 648a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 649a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = active_.Size(); i < e; ++i) { 650a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* active = active_.Get(i); 651a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (active->GetRegister() == reg) { 65286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(!active->IsFixed()); 653a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* split = Split(active, current->GetStart()); 654a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.DeleteAt(i); 655a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_.Add(active); 6563946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 657a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray break; 658a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 659a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 660a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 661a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < inactive_.Size(); ++i) { 662a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* inactive = inactive_.Get(i); 663a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (inactive->GetRegister() == reg) { 66486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t next_intersection = inactive->FirstIntersectionWith(current); 66586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (next_intersection != kNoLifetime) { 66686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (inactive->IsFixed()) { 66786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* split = Split(current, next_intersection); 6683946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 66986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 67086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* split = Split(inactive, current->GetStart()); 67186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray inactive_.DeleteAt(i); 67286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray handled_.Add(inactive); 6733946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 67486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray --i; 67586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 67686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 677a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 678a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 679a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 680a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 681a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 682a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 683a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 6843946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffrayvoid RegisterAllocator::AddSorted(GrowableArray<LiveInterval*>* array, LiveInterval* interval) { 685c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray DCHECK(!interval->IsFixed() && !interval->HasSpillSlot()); 68686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t insert_at = 0; 6873946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = array->Size(); i > 0; --i) { 6883946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* current = array->Get(i - 1); 689a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (current->StartsAfter(interval)) { 69086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray insert_at = i; 691a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray break; 692a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 693a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 6943946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray array->InsertAt(insert_at, interval); 695a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 696a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 697a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas GeoffrayLiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) { 698a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(position >= interval->GetStart()); 699a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(!interval->IsDeadAt(position)); 700a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (position == interval->GetStart()) { 701a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Spill slot will be allocated when handling `interval` again. 702a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray interval->ClearRegister(); 703a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return interval; 704a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 705a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* new_interval = interval->SplitAt(position); 706a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return new_interval; 707a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 708a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 709a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 71031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffrayvoid RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) { 71131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* parent = interval->GetParent(); 71231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 71331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // An instruction gets a spill slot for its entire lifetime. If the parent 71431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // of this interval already has a spill slot, there is nothing to do. 71531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (parent->HasSpillSlot()) { 71631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray return; 71731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 71831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 71986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* defined_by = parent->GetDefinedBy(); 72086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (defined_by->IsParameterValue()) { 72186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Parameters have their own stack slot. 72286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray parent->SetSpillSlot(codegen_->GetStackSlotOfParameter(defined_by->AsParameterValue())); 72386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 72486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 72586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 72696f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray if (defined_by->IsConstant()) { 72796f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray // Constants don't need a spill slot. 72896f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray return; 72996f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray } 73096f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray 73131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* last_sibling = interval; 73231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray while (last_sibling->GetNextSibling() != nullptr) { 73331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray last_sibling = last_sibling->GetNextSibling(); 73431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 73531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray size_t end = last_sibling->GetEnd(); 73631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 737412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // Find an available spill slot. 738412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray size_t slot = 0; 739412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray for (size_t e = spill_slots_.Size(); slot < e; ++slot) { 740412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // We check if it is less rather than less or equal because the parallel move 741412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // resolver does not work when a single spill slot needs to be exchanged with 742412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // a double spill slot. The strict comparison avoids needing to exchange these 743412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // locations at the same lifetime position. 744412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray if (spill_slots_.Get(slot) < parent->GetStart() 745412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray && (slot == (e - 1) || spill_slots_.Get(slot + 1) < parent->GetStart())) { 746412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray break; 747412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } 748412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } 749412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray 75001ef345767ea609417fc511e42007705c9667546Nicolas Geoffray if (parent->NeedsTwoSpillSlots()) { 7513c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray if (slot == spill_slots_.Size()) { 7523c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray // We need a new spill slot. 7533c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray spill_slots_.Add(end); 7543c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray spill_slots_.Add(end); 7553c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray } else if (slot == spill_slots_.Size() - 1) { 7563c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray spill_slots_.Put(slot, end); 7573c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray spill_slots_.Add(end); 7583c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray } else { 7593c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray spill_slots_.Put(slot, end); 7603c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray spill_slots_.Put(slot + 1, end); 76131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 76231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 7633c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray if (slot == spill_slots_.Size()) { 7643c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray // We need a new spill slot. 7653c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray spill_slots_.Add(end); 7663c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray } else { 7673c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray spill_slots_.Put(slot, end); 7683c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray } 76931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 77031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 7713946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray parent->SetSpillSlot((slot + reserved_out_slots_) * kVRegSize); 77286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 77386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 7742a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffraystatic bool IsValidDestination(Location destination) { 775102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return destination.IsRegister() 776102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray || destination.IsFpuRegister() 777102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray || destination.IsStackSlot() 778102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray || destination.IsDoubleStackSlot(); 7792a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray} 7802a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray 781740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffrayvoid RegisterAllocator::AddInputMoveFor(HInstruction* user, 78286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 78386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 7842a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray DCHECK(IsValidDestination(destination)); 78586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 78686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 787476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain DCHECK(!user->IsPhi()); 78886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 789740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray HInstruction* previous = user->GetPrevious(); 79086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move = nullptr; 79186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (previous == nullptr 792476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain || !previous->IsParallelMove() 7938e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray || previous->GetLifetimePosition() < user->GetLifetimePosition()) { 79486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 7958e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray move->SetLifetimePosition(user->GetLifetimePosition()); 796740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray user->GetBlock()->InsertInstructionBefore(move, user); 79786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 79886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = previous->AsParallelMove(); 79986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 8008e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray DCHECK_EQ(move->GetLifetimePosition(), user->GetLifetimePosition()); 801740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray move->AddMove(new (allocator_) MoveOperands(source, destination, nullptr)); 80286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 80386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 80486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertParallelMoveAt(size_t position, 805740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray HInstruction* instruction, 80686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 80786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 8082a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray DCHECK(IsValidDestination(destination)); 80986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 81086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 81186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* at = liveness_.GetInstructionFromPosition(position / 2); 81286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (at == nullptr) { 81386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Block boundary, don't no anything the connection of split siblings will handle it. 81486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 81586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 81686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move; 81786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if ((position & 1) == 1) { 81886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Move must happen after the instruction. 81986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(!at->IsControlFlow()); 82086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = at->GetNext()->AsParallelMove(); 821e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting siblings in a same block. We need to 822e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // differentiate it with moves for connecting blocks, and input moves. 8238e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray if (move == nullptr || move->GetLifetimePosition() > position) { 82486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 82586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->SetLifetimePosition(position); 82686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray at->GetBlock()->InsertInstructionBefore(move, at->GetNext()); 82786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 82886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 82986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Move must happen before the instruction. 83086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* previous = at->GetPrevious(); 831740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray if (previous == nullptr 832740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray || !previous->IsParallelMove() 833740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray || previous->GetLifetimePosition() != position) { 834740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray // If the previous is a parallel move, then its position must be lower 835740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray // than the given `position`: it was added just after the non-parallel 836740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray // move instruction that precedes `instruction`. 837740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray DCHECK(previous == nullptr 838740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray || !previous->IsParallelMove() 839740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray || previous->GetLifetimePosition() < position); 84086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 84186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->SetLifetimePosition(position); 84286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray at->GetBlock()->InsertInstructionBefore(move, at); 84386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 84486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = previous->AsParallelMove(); 84586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 84686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 84701ef345767ea609417fc511e42007705c9667546Nicolas Geoffray DCHECK_EQ(move->GetLifetimePosition(), position); 848740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray move->AddMove(new (allocator_) MoveOperands(source, destination, instruction)); 84986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 85086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 85186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertParallelMoveAtExitOf(HBasicBlock* block, 852740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray HInstruction* instruction, 85386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 85486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 8552a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray DCHECK(IsValidDestination(destination)); 85686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 85786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 85886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK_EQ(block->GetSuccessors().Size(), 1u); 85986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* last = block->GetLastInstruction(); 860360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray // We insert moves at exit for phi predecessors and connecting blocks. 861360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray // A block ending with an if cannot branch to a block with phis because 862360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray // we do not allow critical edges. It can also not connect 863360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray // a split interval between two blocks: the move has to happen in the successor. 864360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray DCHECK(!last->IsIf()); 86586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* previous = last->GetPrevious(); 86686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move; 867e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting blocks. We need to differentiate 868e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // it with moves for connecting siblings in a same block, and output moves. 869740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray if (previous == nullptr || !previous->IsParallelMove() 870e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray || previous->AsParallelMove()->GetLifetimePosition() != block->GetLifetimeEnd()) { 87186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 872e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray move->SetLifetimePosition(block->GetLifetimeEnd()); 87386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray block->InsertInstructionBefore(move, last); 87486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 87586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = previous->AsParallelMove(); 87686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 877740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray move->AddMove(new (allocator_) MoveOperands(source, destination, instruction)); 87886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 87986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 88086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertParallelMoveAtEntryOf(HBasicBlock* block, 881740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray HInstruction* instruction, 88286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 88386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 8842a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray DCHECK(IsValidDestination(destination)); 88586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 88686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 88786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* first = block->GetFirstInstruction(); 88886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move = first->AsParallelMove(); 889e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting blocks. We need to differentiate 890e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // it with moves for connecting siblings in a same block, and input moves. 891e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray if (move == nullptr || move->GetLifetimePosition() != block->GetLifetimeStart()) { 89286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 89386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->SetLifetimePosition(block->GetLifetimeStart()); 89486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray block->InsertInstructionBefore(move, first); 89586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 896740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray move->AddMove(new (allocator_) MoveOperands(source, destination, instruction)); 89786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 89886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 89986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertMoveAfter(HInstruction* instruction, 90086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 90186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 9022a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray DCHECK(IsValidDestination(destination)); 90386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 90486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 905476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain if (instruction->IsPhi()) { 906740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAtEntryOf(instruction->GetBlock(), instruction, source, destination); 90786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 90886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 90986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 910e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray size_t position = instruction->GetLifetimePosition() + 1; 91186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move = instruction->GetNext()->AsParallelMove(); 912e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for moving the output of an instruction. We need 913e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // to differentiate with input moves, moves for connecting siblings in a 914e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // and moves for connecting blocks. 915e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray if (move == nullptr || move->GetLifetimePosition() != position) { 91686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 917e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray move->SetLifetimePosition(position); 91886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray instruction->GetBlock()->InsertInstructionBefore(move, instruction->GetNext()); 91986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 920740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray move->AddMove(new (allocator_) MoveOperands(source, destination, instruction)); 92186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 92286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 92386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::ConnectSiblings(LiveInterval* interval) { 92486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = interval; 92586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->HasSpillSlot() && current->HasRegister()) { 92686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // We spill eagerly, so move must be at definition. 92786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InsertMoveAfter(interval->GetDefinedBy(), 928102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray interval->IsFloatingPoint() 929102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ? Location::FpuRegisterLocation(interval->GetRegister()) 930102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray : Location::RegisterLocation(interval->GetRegister()), 93101ef345767ea609417fc511e42007705c9667546Nicolas Geoffray interval->NeedsTwoSpillSlots() 932412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray ? Location::DoubleStackSlot(interval->GetParent()->GetSpillSlot()) 933412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray : Location::StackSlot(interval->GetParent()->GetSpillSlot())); 93486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 93586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray UsePosition* use = current->GetFirstUse(); 93686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 93786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Walk over all siblings, updating locations of use positions, and 93886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // connecting them when they are adjacent. 93986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray do { 94001ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location source = current->ToLocation(); 94186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 94286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Walk over all uses covered by this interval, and update the location 94386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // information. 94486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray while (use != nullptr && use->GetPosition() <= current->GetEnd()) { 9453946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LocationSummary* locations = use->GetUser()->GetLocations(); 9463946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (use->GetIsEnvironment()) { 9473946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray locations->SetEnvironmentAt(use->GetInputIndex(), source); 9483946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 94986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location expected_location = locations->InAt(use->GetInputIndex()); 95086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (expected_location.IsUnallocated()) { 95186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray locations->SetInAt(use->GetInputIndex(), source); 9522a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray } else if (!expected_location.IsConstant()) { 95386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray AddInputMoveFor(use->GetUser(), source, expected_location); 95486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 95586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 95686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray use = use->GetNext(); 95786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 95886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 95986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // If the next interval starts just after this one, and has a register, 96086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // insert a move. 96186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* next_sibling = current->GetNextSibling(); 96286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (next_sibling != nullptr 96386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && next_sibling->HasRegister() 96486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && current->GetEnd() == next_sibling->GetStart()) { 96501ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location destination = next_sibling->ToLocation(); 966740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAt(current->GetEnd(), interval->GetDefinedBy(), source, destination); 96786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 9683946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 9693946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // At each safepoint, we record stack and register information. 9703946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0, e = safepoints_.Size(); i < e; ++i) { 9713946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray HInstruction* safepoint = safepoints_.Get(i); 9723946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t position = safepoint->GetLifetimePosition(); 9733946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LocationSummary* locations = safepoint->GetLocations(); 9743946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (!current->Covers(position)) continue; 9753946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 9763bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray if ((current->GetType() == Primitive::kPrimNot) && current->GetParent()->HasSpillSlot()) { 9773946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray locations->SetStackBit(current->GetParent()->GetSpillSlot() / kVRegSize); 9783946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 9793946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 9803946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray switch (source.GetKind()) { 9813946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kRegister: { 9823bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray locations->AddLiveRegister(source); 9833946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current->GetType() == Primitive::kPrimNot) { 98456b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray locations->SetRegisterBit(source.reg()); 9853946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 9863946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray break; 9873946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 988102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray case Location::kFpuRegister: { 989102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray locations->AddLiveRegister(source); 990102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray break; 991102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 9923946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kStackSlot: // Fall-through 9933946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kDoubleStackSlot: // Fall-through 9943946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kConstant: { 9953946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Nothing to do. 9963946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray break; 9973946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 9983946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray default: { 9993946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LOG(FATAL) << "Unexpected location for object"; 10003946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 10013946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 10023946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 100386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current = next_sibling; 100486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } while (current != nullptr); 100586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(use == nullptr); 100686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 100786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 100886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval, 100986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* from, 101086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* to) const { 101186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (interval->GetNextSibling() == nullptr) { 101286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Nothing to connect. The whole range was allocated to the same location. 101386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 101486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 101586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 101686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t from_position = from->GetLifetimeEnd() - 1; 10177690562d40878f44823d5fb03a2084cfc677ec4aNicolas Geoffray // When an instructions dies at entry of another, and the latter is the beginning 10187690562d40878f44823d5fb03a2084cfc677ec4aNicolas Geoffray // of a block, the register allocator ensures the former has a register 10197690562d40878f44823d5fb03a2084cfc677ec4aNicolas Geoffray // at block->GetLifetimeStart() + 1. Since this is at a block boundary, it must 10207690562d40878f44823d5fb03a2084cfc677ec4aNicolas Geoffray // must be handled in this method. 10217690562d40878f44823d5fb03a2084cfc677ec4aNicolas Geoffray size_t to_position = to->GetLifetimeStart() + 1; 102286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 102386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* destination = nullptr; 102486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* source = nullptr; 102586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 102686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = interval; 102786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 102886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Check the intervals that cover `from` and `to`. 102986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray while ((current != nullptr) && (source == nullptr || destination == nullptr)) { 103086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->Covers(from_position)) { 103186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(source == nullptr); 103286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray source = current; 103386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 103486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->Covers(to_position)) { 103586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(destination == nullptr); 103686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray destination = current; 103786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 103886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 103986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current = current->GetNextSibling(); 104086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 104186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 104286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (destination == source) { 104386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Interval was not split. 104486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 104586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 104686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 10478ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray DCHECK(destination != nullptr && source != nullptr); 10488ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray 104986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (!destination->HasRegister()) { 105086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Values are eagerly spilled. Spill slot already contains appropriate value. 105186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 105286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 105386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 105486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // If `from` has only one successor, we can put the moves at the exit of it. Otherwise 105586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // we need to put the moves at the entry of `to`. 105686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (from->GetSuccessors().Size() == 1) { 1057740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAtExitOf(from, 1058740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray interval->GetParent()->GetDefinedBy(), 105901ef345767ea609417fc511e42007705c9667546Nicolas Geoffray source->ToLocation(), 106001ef345767ea609417fc511e42007705c9667546Nicolas Geoffray destination->ToLocation()); 106186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 106286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK_EQ(to->GetPredecessors().Size(), 1u); 1063740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAtEntryOf(to, 1064740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray interval->GetParent()->GetDefinedBy(), 106501ef345767ea609417fc511e42007705c9667546Nicolas Geoffray source->ToLocation(), 106601ef345767ea609417fc511e42007705c9667546Nicolas Geoffray destination->ToLocation()); 106786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 106886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 106986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 107086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::Resolve() { 10713bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray codegen_->ComputeFrameSize( 10723bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray spill_slots_.Size(), maximum_number_of_live_registers_, reserved_out_slots_); 107386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 107486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Adjust the Out Location of instructions. 107586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // TODO: Use pointers of Location inside LiveInterval to avoid doing another iteration. 107686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { 107786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 107886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = instruction->GetLiveInterval(); 107986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LocationSummary* locations = instruction->GetLocations(); 108086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location location = locations->Out(); 1081476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain if (instruction->IsParameterValue()) { 108286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Now that we know the frame size, adjust the parameter's location. 108386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (location.IsStackSlot()) { 108486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray location = Location::StackSlot(location.GetStackIndex() + codegen_->GetFrameSize()); 108586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(location.GetStackIndex()); 108686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray locations->SetOut(location); 108786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else if (location.IsDoubleStackSlot()) { 108886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray location = Location::DoubleStackSlot(location.GetStackIndex() + codegen_->GetFrameSize()); 108986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(location.GetStackIndex()); 109086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray locations->SetOut(location); 109186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else if (current->HasSpillSlot()) { 109286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(current->GetSpillSlot() + codegen_->GetFrameSize()); 109386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 109486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 109586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 109601ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location source = current->ToLocation(); 109786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 109886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (location.IsUnallocated()) { 109986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (location.GetPolicy() == Location::kSameAsFirstInput) { 110086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray locations->SetInAt(0, source); 110186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 110286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray locations->SetOut(source); 110386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 110486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(source.Equals(location)); 110586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 110686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 110786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 110886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Connect siblings. 110986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { 111086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 111186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ConnectSiblings(instruction->GetLiveInterval()); 111286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 111386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 111486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Resolve non-linear control flow across branches. Order does not matter. 111586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (HLinearOrderIterator it(liveness_); !it.Done(); it.Advance()) { 111686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* block = it.Current(); 111786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray BitVector* live = liveness_.GetLiveInSet(*block); 111886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (uint32_t idx : live->Indexes()) { 111986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* current = liveness_.GetInstructionFromSsaIndex(idx); 112086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* interval = current->GetLiveInterval(); 112186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { 112286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ConnectSplitSiblings(interval, block->GetPredecessors().Get(i), block); 112386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 112486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 112586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 112686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 112786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Resolve phi inputs. Order does not matter. 112886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (HLinearOrderIterator it(liveness_); !it.Done(); it.Advance()) { 112986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* current = it.Current(); 113086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (HInstructionIterator it(current->GetPhis()); !it.Done(); it.Advance()) { 113186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* phi = it.Current(); 113286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = current->GetPredecessors().Size(); i < e; ++i) { 113386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* predecessor = current->GetPredecessors().Get(i); 113486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK_EQ(predecessor->GetSuccessors().Size(), 1u); 113586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* input = phi->InputAt(i); 113601ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location source = input->GetLiveInterval()->GetLocationAt( 113701ef345767ea609417fc511e42007705c9667546Nicolas Geoffray predecessor->GetLifetimeEnd() - 1); 113801ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location destination = phi->GetLiveInterval()->ToLocation(); 1139740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAtExitOf(predecessor, nullptr, source, destination); 114086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 114186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 114286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 11433946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 11443946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Assign temp locations. 11453946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray HInstruction* current = nullptr; 11463946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t temp_index = 0; 11473946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < temp_intervals_.Size(); ++i) { 11483946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* temp = temp_intervals_.Get(i); 114901ef345767ea609417fc511e42007705c9667546Nicolas Geoffray HInstruction* at = liveness_.GetTempUser(temp); 115001ef345767ea609417fc511e42007705c9667546Nicolas Geoffray if (at != current) { 11513946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray temp_index = 0; 115201ef345767ea609417fc511e42007705c9667546Nicolas Geoffray current = at; 11533946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 115401ef345767ea609417fc511e42007705c9667546Nicolas Geoffray LocationSummary* locations = at->GetLocations(); 1155102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray DCHECK(temp->GetType() == Primitive::kPrimInt); 11563946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray locations->SetTempAt( 115756b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray temp_index++, Location::RegisterLocation(temp->GetRegister())); 11583946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 115931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray} 116031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 1161a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} // namespace art 1162