register_allocator.cc revision 3e69f16ae3fddfd24f4f0e29deb106d564ab296c
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 19c7dd295a4e0cc1d15c0c96088e55a85389bade74Ian Rogers#include <sstream> 20c7dd295a4e0cc1d15c0c96088e55a85389bade74Ian Rogers 21e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers#include "base/bit_vector-inl.h" 22a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray#include "code_generator.h" 23a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray#include "ssa_liveness_analysis.h" 24a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 25a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraynamespace art { 26a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 27a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraystatic constexpr size_t kMaxLifetimePosition = -1; 2831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffraystatic constexpr size_t kDefaultNumberOfSpillSlots = 4; 29a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 3086dbb9a12119273039ce272b41c809fa548b37b6Nicolas GeoffrayRegisterAllocator::RegisterAllocator(ArenaAllocator* allocator, 3186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray CodeGenerator* codegen, 3286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray const SsaLivenessAnalysis& liveness) 33a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray : allocator_(allocator), 34a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen_(codegen), 3586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray liveness_(liveness), 363946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_core_intervals_(allocator, 0), 373946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_fp_intervals_(allocator, 0), 383946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_(nullptr), 39a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_(allocator, 0), 40a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_(allocator, 0), 41a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_(allocator, 0), 42102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_core_register_intervals_(allocator, codegen->GetNumberOfCoreRegisters()), 43102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_fp_register_intervals_(allocator, codegen->GetNumberOfFloatingPointRegisters()), 443946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray temp_intervals_(allocator, 4), 4531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray spill_slots_(allocator, kDefaultNumberOfSpillSlots), 463946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray safepoints_(allocator, 0), 47a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray processing_core_registers_(false), 48a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray number_of_registers_(-1), 49a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray registers_array_(nullptr), 50102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray blocked_core_registers_(codegen->GetBlockedCoreRegisters()), 51102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray blocked_fp_registers_(codegen->GetBlockedFloatingPointRegisters()), 523bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray reserved_out_slots_(0), 533bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray maximum_number_of_live_registers_(0) { 5471175b7f19a4f6cf9cc264feafd820dbafa371fbNicolas Geoffray codegen->SetupBlockedRegisters(); 55102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_core_register_intervals_.SetSize(codegen->GetNumberOfCoreRegisters()); 56102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_fp_register_intervals_.SetSize(codegen->GetNumberOfFloatingPointRegisters()); 573946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Always reserve for the current method and the graph's max out registers. 583946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // TODO: compute it instead. 593946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray reserved_out_slots_ = 1 + codegen->GetGraph()->GetMaximumNumberOfOutVRegs(); 60a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 61a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 6286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraybool RegisterAllocator::CanAllocateRegistersFor(const HGraph& graph, 6386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InstructionSet instruction_set) { 6486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (!Supports(instruction_set)) { 6586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return false; 6686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 673e69f16ae3fddfd24f4f0e29deb106d564ab296cAlexandre Rames if (instruction_set == kArm64 || instruction_set == kX86_64) { 683e69f16ae3fddfd24f4f0e29deb106d564ab296cAlexandre Rames return true; 693e69f16ae3fddfd24f4f0e29deb106d564ab296cAlexandre Rames } 7086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = graph.GetBlocks().Size(); i < e; ++i) { 7186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (HInstructionIterator it(graph.GetBlocks().Get(i)->GetInstructions()); 7286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray !it.Done(); 7386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray it.Advance()) { 7486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* current = it.Current(); 753e69f16ae3fddfd24f4f0e29deb106d564ab296cAlexandre Rames if (current->GetType() == Primitive::kPrimLong || 763e69f16ae3fddfd24f4f0e29deb106d564ab296cAlexandre Rames current->GetType() == Primitive::kPrimFloat || 773e69f16ae3fddfd24f4f0e29deb106d564ab296cAlexandre Rames current->GetType() == Primitive::kPrimDouble) { 78102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return false; 79102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 8086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 8186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 8286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return true; 8386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 8486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 8586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraystatic bool ShouldProcess(bool processing_core_registers, LiveInterval* interval) { 863946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (interval == nullptr) return false; 8786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray bool is_core_register = (interval->GetType() != Primitive::kPrimDouble) 8886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && (interval->GetType() != Primitive::kPrimFloat); 89a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return processing_core_registers == is_core_register; 90a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 91a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 9286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::AllocateRegisters() { 9386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray AllocateRegistersInternal(); 9486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Resolve(); 9586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 9686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (kIsDebugBuild) { 9786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray processing_core_registers_ = true; 9886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ValidateInternal(true); 9986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray processing_core_registers_ = false; 10086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ValidateInternal(true); 1015976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // Check that the linear order is still correct with regards to lifetime positions. 1025976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // Since only parallel moves have been inserted during the register allocation, 1035976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // these checks are mostly for making sure these moves have been added correctly. 1045976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray size_t current_liveness = 0; 1055976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray for (HLinearOrderIterator it(liveness_); !it.Done(); it.Advance()) { 1065976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray HBasicBlock* block = it.Current(); 1075976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 1085976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray HInstruction* instruction = inst_it.Current(); 1095976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray DCHECK_LE(current_liveness, instruction->GetLifetimePosition()); 1105976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray current_liveness = instruction->GetLifetimePosition(); 1115976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray } 1125976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray for (HInstructionIterator inst_it(block->GetInstructions()); 1135976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray !inst_it.Done(); 1145976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray inst_it.Advance()) { 1155976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray HInstruction* instruction = inst_it.Current(); 1165976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray DCHECK_LE(current_liveness, instruction->GetLifetimePosition()) << instruction->DebugName(); 1175976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray current_liveness = instruction->GetLifetimePosition(); 1185976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray } 1195976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray } 12086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 12186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 12286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 12386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::BlockRegister(Location location, 12486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t start, 125102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray size_t end) { 12656b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray int reg = location.reg(); 127102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray DCHECK(location.IsRegister() || location.IsFpuRegister()); 128102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* interval = location.IsRegister() 129102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ? physical_core_register_intervals_.Get(reg) 130102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray : physical_fp_register_intervals_.Get(reg); 131102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray Primitive::Type type = location.IsRegister() 132102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ? Primitive::kPrimInt 133102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray : Primitive::kPrimDouble; 13486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (interval == nullptr) { 13586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray interval = LiveInterval::MakeFixedInterval(allocator_, reg, type); 136102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (location.IsRegister()) { 137102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_core_register_intervals_.Put(reg, interval); 138102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 139102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_fp_register_intervals_.Put(reg, interval); 140102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 14186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 14286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(interval->GetRegister() == reg); 14386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray interval->AddRange(start, end); 14486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 14586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 14686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::AllocateRegistersInternal() { 1473946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Iterate post-order, to ensure the list is sorted, and the last added interval 1483946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // is the one with the lowest start position. 1493946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (HLinearPostOrderIterator it(liveness_); !it.Done(); it.Advance()) { 1503946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray HBasicBlock* block = it.Current(); 151277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe for (HBackwardInstructionIterator back_it(block->GetInstructions()); !back_it.Done(); 152277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe back_it.Advance()) { 153277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe ProcessInstruction(back_it.Current()); 1543946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 155277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 156277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe ProcessInstruction(inst_it.Current()); 1573946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 1583946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 159a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1603946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray number_of_registers_ = codegen_->GetNumberOfCoreRegisters(); 161a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_); 1623946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray processing_core_registers_ = true; 1633946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_ = &unhandled_core_intervals_; 164102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0, e = physical_core_register_intervals_.Size(); i < e; ++i) { 165102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* fixed = physical_core_register_intervals_.Get(i); 166102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (fixed != nullptr) { 167296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Fixed interval is added to inactive_ instead of unhandled_. 168296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // It's also the only type of inactive interval whose start position 169296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // can be after the current interval during linear scan. 170296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Fixed interval is never split and never moves to unhandled_. 171102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray inactive_.Add(fixed); 172102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 173102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 1743946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LinearScan(); 175a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 176102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray size_t saved_maximum_number_of_live_registers = maximum_number_of_live_registers_; 177102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray maximum_number_of_live_registers_ = 0; 178102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray 1793946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray inactive_.Reset(); 1803946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray active_.Reset(); 1813946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray handled_.Reset(); 182a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1833946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray number_of_registers_ = codegen_->GetNumberOfFloatingPointRegisters(); 1843946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_); 1853946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray processing_core_registers_ = false; 1863946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_ = &unhandled_fp_intervals_; 187102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0, e = physical_fp_register_intervals_.Size(); i < e; ++i) { 188102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* fixed = physical_fp_register_intervals_.Get(i); 189102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (fixed != nullptr) { 190296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Fixed interval is added to inactive_ instead of unhandled_. 191296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // It's also the only type of inactive interval whose start position 192296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // can be after the current interval during linear scan. 193296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Fixed interval is never split and never moves to unhandled_. 194102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray inactive_.Add(fixed); 195102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 196102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 1973946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LinearScan(); 198102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray maximum_number_of_live_registers_ += saved_maximum_number_of_live_registers; 1993946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray} 20086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 2013946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffrayvoid RegisterAllocator::ProcessInstruction(HInstruction* instruction) { 2023946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LocationSummary* locations = instruction->GetLocations(); 2033946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t position = instruction->GetLifetimePosition(); 2043946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 2053946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (locations == nullptr) return; 2063946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 2073946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Create synthesized intervals for temporaries. 2083946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < locations->GetTempCount(); ++i) { 2093946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray Location temp = locations->GetTemp(i); 21052839d17c06175e19ca4a093fb878450d1c4310dNicolas Geoffray if (temp.IsRegister() || temp.IsFpuRegister()) { 211102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray BlockRegister(temp, position, position + 1); 2123946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 213102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray DCHECK(temp.IsUnallocated()); 2145368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain switch (temp.GetPolicy()) { 2155368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain case Location::kRequiresRegister: { 2165368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LiveInterval* interval = 2175368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimInt); 2185368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain temp_intervals_.Add(interval); 2195368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain interval->AddRange(position, position + 1); 2205368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain unhandled_core_intervals_.Add(interval); 2215368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain break; 2225368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain } 2235368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain 2245368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain case Location::kRequiresFpuRegister: { 2255368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LiveInterval* interval = 2265368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimDouble); 2275368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain temp_intervals_.Add(interval); 2285368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain interval->AddRange(position, position + 1); 2295368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain unhandled_fp_intervals_.Add(interval); 2305368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain break; 2315368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain } 2325368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain 2335368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain default: 2345368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LOG(FATAL) << "Unexpected policy for temporary location " 2355368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain << temp.GetPolicy(); 2365368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain } 237a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 238a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 23986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 2403bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray bool core_register = (instruction->GetType() != Primitive::kPrimDouble) 2413bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray && (instruction->GetType() != Primitive::kPrimFloat); 2423bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray 2433946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (locations->CanCall()) { 2443bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray if (!instruction->IsSuspendCheck()) { 2453bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray codegen_->MarkNotLeaf(); 2463bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 2473946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray safepoints_.Add(instruction); 2483bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray if (locations->OnlyCallsOnSlowPath()) { 2493bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // We add a synthesized range at this position to record the live registers 2503bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // at this position. Ideally, we could just update the safepoints when locations 2513bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // are updated, but we currently need to know the full stack size before updating 2523bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // locations (because of parameters and the fact that we don't have a frame pointer). 2533bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // And knowing the full stack size requires to know the maximum number of live 2543bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // registers at calls in slow paths. 2553bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // By adding the following interval in the algorithm, we can compute this 2563bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // maximum before updating locations. 2573bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray LiveInterval* interval = LiveInterval::MakeSlowPathInterval(allocator_, instruction); 258acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray interval->AddRange(position, position + 1); 25987d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray AddSorted(&unhandled_core_intervals_, interval); 26087d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray AddSorted(&unhandled_fp_intervals_, interval); 2613bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 2623bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 2633bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray 2643bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray if (locations->WillCall()) { 2653946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Block all registers. 2663946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < codegen_->GetNumberOfCoreRegisters(); ++i) { 26756b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray BlockRegister(Location::RegisterLocation(i), 2683946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray position, 269102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray position + 1); 270102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 271102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0; i < codegen_->GetNumberOfFloatingPointRegisters(); ++i) { 272102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray BlockRegister(Location::FpuRegisterLocation(i), 273102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray position, 274102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray position + 1); 2753946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 2763946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 2773946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 2783946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < instruction->InputCount(); ++i) { 2793946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray Location input = locations->InAt(i); 280102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (input.IsRegister() || input.IsFpuRegister()) { 281102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray BlockRegister(input, position, position + 1); 2823946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 2833946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 2843946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 2853946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* current = instruction->GetLiveInterval(); 2863946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current == nullptr) return; 2873946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 288102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray GrowableArray<LiveInterval*>& unhandled = core_register 289102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ? unhandled_core_intervals_ 290102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray : unhandled_fp_intervals_; 291102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray 2927690562d40878f44823d5fb03a2084cfc677ec4aNicolas Geoffray DCHECK(unhandled.IsEmpty() || current->StartsBeforeOrAt(unhandled.Peek())); 29387d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray 2943946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Some instructions define their output in fixed register/stack slot. We need 2953946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // to ensure we know these locations before doing register allocation. For a 2963946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // given register, we create an interval that covers these locations. The register 2973946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // will be unavailable at these locations when trying to allocate one for an 2983946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // interval. 2993946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // 3003946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // The backwards walking ensures the ranges are ordered on increasing start positions. 3013946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray Location output = locations->Out(); 302d0d4852847432368b090c184d6639e573538dccfCalin Juravle if (output.IsUnallocated() && output.GetPolicy() == Location::kSameAsFirstInput) { 303d0d4852847432368b090c184d6639e573538dccfCalin Juravle Location first = locations->InAt(0); 304d0d4852847432368b090c184d6639e573538dccfCalin Juravle if (first.IsRegister() || first.IsFpuRegister()) { 305d0d4852847432368b090c184d6639e573538dccfCalin Juravle current->SetFrom(position + 1); 306d0d4852847432368b090c184d6639e573538dccfCalin Juravle current->SetRegister(first.reg()); 307d0d4852847432368b090c184d6639e573538dccfCalin Juravle } 308d0d4852847432368b090c184d6639e573538dccfCalin Juravle } else if (output.IsRegister() || output.IsFpuRegister()) { 3093946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Shift the interval's start by one to account for the blocked register. 3103946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray current->SetFrom(position + 1); 31156b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray current->SetRegister(output.reg()); 312102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray BlockRegister(output, position, position + 1); 3133946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else if (output.IsStackSlot() || output.IsDoubleStackSlot()) { 3143946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray current->SetSpillSlot(output.GetStackIndex()); 3153946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3163946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 3173946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // If needed, add interval to the list of unhandled intervals. 3183946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current->HasSpillSlot() || instruction->IsConstant()) { 319c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray // Split just before first register use. 3203946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t first_register_use = current->FirstRegisterUse(); 3213946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (first_register_use != kNoLifetime) { 322c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray LiveInterval* split = Split(current, first_register_use - 1); 323b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // Don't add directly to `unhandled`, it needs to be sorted and the start 3243946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // of this new interval might be after intervals already in the list. 3253946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(&unhandled, split); 3263946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 3273946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Nothing to do, we won't allocate a register for this value. 3283946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3293946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 330b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // Don't add directly to `unhandled`, temp or safepoint intervals 331b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // for this instruction may have been added, and those can be 332b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // processed first. 333b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray AddSorted(&unhandled, current); 3343946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 335a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 336a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 33731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffrayclass AllRangesIterator : public ValueObject { 33831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray public: 33931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray explicit AllRangesIterator(LiveInterval* interval) 34031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray : current_interval_(interval), 34131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_(interval->GetFirstRange()) {} 34231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 34331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray bool Done() const { return current_interval_ == nullptr; } 34431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveRange* CurrentRange() const { return current_range_; } 34531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* CurrentInterval() const { return current_interval_; } 34631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 34731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray void Advance() { 34831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_ = current_range_->GetNext(); 34931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current_range_ == nullptr) { 35031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_interval_ = current_interval_->GetNextSibling(); 35131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current_interval_ != nullptr) { 35231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_ = current_interval_->GetFirstRange(); 35331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 35431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 35531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 35631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 35731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray private: 35831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* current_interval_; 35931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveRange* current_range_; 36031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 36131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray DISALLOW_COPY_AND_ASSIGN(AllRangesIterator); 36231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray}; 36331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 36486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraybool RegisterAllocator::ValidateInternal(bool log_fatal_on_failure) const { 36586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // To simplify unit testing, we eagerly create the array of intervals, and 36686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // call the helper method. 36786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray GrowableArray<LiveInterval*> intervals(allocator_, 0); 36886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0; i < liveness_.GetNumberOfSsaValues(); ++i) { 36986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 37086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (ShouldProcess(processing_core_registers_, instruction->GetLiveInterval())) { 37186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray intervals.Add(instruction->GetLiveInterval()); 37286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 37386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 37486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 375102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (processing_core_registers_) { 376102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0, e = physical_core_register_intervals_.Size(); i < e; ++i) { 377102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* fixed = physical_core_register_intervals_.Get(i); 378102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (fixed != nullptr) { 379102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray intervals.Add(fixed); 380102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 381102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 382102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 383102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0, e = physical_fp_register_intervals_.Size(); i < e; ++i) { 384102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* fixed = physical_fp_register_intervals_.Get(i); 385102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (fixed != nullptr) { 386102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray intervals.Add(fixed); 387102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 38886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 38986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 39086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 3913946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0, e = temp_intervals_.Size(); i < e; ++i) { 3923946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* temp = temp_intervals_.Get(i); 3933946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (ShouldProcess(processing_core_registers_, temp)) { 3943946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray intervals.Add(temp); 3953946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3963946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3973946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 3983946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray return ValidateIntervals(intervals, spill_slots_.Size(), reserved_out_slots_, *codegen_, 3993946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray allocator_, processing_core_registers_, log_fatal_on_failure); 40086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 40186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 40231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffraybool RegisterAllocator::ValidateIntervals(const GrowableArray<LiveInterval*>& intervals, 40331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray size_t number_of_spill_slots, 4043946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t number_of_out_slots, 405a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray const CodeGenerator& codegen, 406a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray ArenaAllocator* allocator, 407a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool processing_core_registers, 408a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool log_fatal_on_failure) { 409a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t number_of_registers = processing_core_registers 410a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray ? codegen.GetNumberOfCoreRegisters() 411a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray : codegen.GetNumberOfFloatingPointRegisters(); 41231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray GrowableArray<ArenaBitVector*> liveness_of_values( 41331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray allocator, number_of_registers + number_of_spill_slots); 414a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 415a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Allocate a bit vector per register. A live interval that has a register 416a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // allocated will populate the associated bit vector based on its live ranges. 41731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t i = 0; i < number_of_registers + number_of_spill_slots; ++i) { 41831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_values.Add(new (allocator) ArenaBitVector(allocator, 0, true)); 419a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 420a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 42131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t i = 0, e = intervals.Size(); i < e; ++i) { 42231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (AllRangesIterator it(intervals.Get(i)); !it.Done(); it.Advance()) { 42331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* current = it.CurrentInterval(); 42486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* defined_by = current->GetParent()->GetDefinedBy(); 42586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->GetParent()->HasSpillSlot() 42686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Parameters have their own stack slot. 42786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && !(defined_by != nullptr && defined_by->IsParameterValue())) { 4283946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray BitVector* liveness_of_spill_slot = liveness_of_values.Get(number_of_registers 4293946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray + current->GetParent()->GetSpillSlot() / kVRegSize 4303946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray - number_of_out_slots); 43131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 43231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (liveness_of_spill_slot->IsBitSet(j)) { 43331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (log_fatal_on_failure) { 43431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray std::ostringstream message; 43531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray message << "Spill slot conflict at " << j; 43631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LOG(FATAL) << message.str(); 43731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 43831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray return false; 43931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 44031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 44131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_spill_slot->SetBit(j); 44231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 44331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 444a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 44531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 44631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current->HasRegister()) { 44731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray BitVector* liveness_of_register = liveness_of_values.Get(current->GetRegister()); 44831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 44931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (liveness_of_register->IsBitSet(j)) { 450a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (log_fatal_on_failure) { 451a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray std::ostringstream message; 4523946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray message << "Register conflict at " << j << " "; 4533946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (defined_by != nullptr) { 4543946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray message << "(" << defined_by->DebugName() << ")"; 4553946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 4563946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray message << "for "; 457a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (processing_core_registers) { 458a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen.DumpCoreRegister(message, current->GetRegister()); 459a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 460a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen.DumpFloatingPointRegister(message, current->GetRegister()); 461a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 462a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LOG(FATAL) << message.str(); 463a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 464a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 465a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 466a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 46731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_register->SetBit(j); 468a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 469a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 47031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 47131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 472a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 473a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 474a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 475a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 47686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::DumpInterval(std::ostream& stream, LiveInterval* interval) const { 477a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray interval->Dump(stream); 478a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << ": "; 479a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->HasRegister()) { 480102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (interval->IsFloatingPoint()) { 48186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray codegen_->DumpFloatingPointRegister(stream, interval->GetRegister()); 482102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 483102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray codegen_->DumpCoreRegister(stream, interval->GetRegister()); 484a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 485a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 486a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << "spilled"; 487a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 488a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << std::endl; 489a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 490a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 491296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yangvoid RegisterAllocator::DumpAllIntervals(std::ostream& stream) const { 492296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang stream << "inactive: " << std::endl; 493296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0; i < inactive_.Size(); i ++) { 494296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DumpInterval(stream, inactive_.Get(i)); 495296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 496296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang stream << "active: " << std::endl; 497296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0; i < active_.Size(); i ++) { 498296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DumpInterval(stream, active_.Get(i)); 499296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 500296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang stream << "unhandled: " << std::endl; 501296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang auto unhandled = (unhandled_ != nullptr) ? 502296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang unhandled_ : &unhandled_core_intervals_; 503296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0; i < unhandled->Size(); i ++) { 504296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DumpInterval(stream, unhandled->Get(i)); 505296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 506296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang stream << "handled: " << std::endl; 507296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0; i < handled_.Size(); i ++) { 508296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DumpInterval(stream, handled_.Get(i)); 509296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 510296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang} 511296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang 512a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// By the book implementation of a linear scan register allocator. 513a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffrayvoid RegisterAllocator::LinearScan() { 5143946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray while (!unhandled_->IsEmpty()) { 515a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (1) Remove interval with the lowest start position from unhandled. 5163946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* current = unhandled_->Pop(); 5173946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray DCHECK(!current->IsFixed() && !current->HasSpillSlot()); 518c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray DCHECK(unhandled_->IsEmpty() || unhandled_->Peek()->GetStart() >= current->GetStart()); 51987d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray 520a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t position = current->GetStart(); 521a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 522296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Remember the inactive_ size here since the ones moved to inactive_ from 523296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // active_ below shouldn't need to be re-checked. 524296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang size_t inactive_intervals_to_handle = inactive_.Size(); 525296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang 526a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (2) Remove currently active intervals that are dead at this position. 527a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Move active intervals that have a lifetime hole at this position 528a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // to inactive. 529a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < active_.Size(); ++i) { 530a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* interval = active_.Get(i); 531a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->IsDeadAt(position)) { 532a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Delete(interval); 533a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 534a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_.Add(interval); 535a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else if (!interval->Covers(position)) { 536a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Delete(interval); 537a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 538a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.Add(interval); 539a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 540a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 541a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 542a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (3) Remove currently inactive intervals that are dead at this position. 543a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Move inactive intervals that cover this position to active. 544296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0; i < inactive_intervals_to_handle; ++i) { 545a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* interval = inactive_.Get(i); 546296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK(interval->GetStart() < position || interval->IsFixed()); 547a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->IsDeadAt(position)) { 548a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.Delete(interval); 549a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 550296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang --inactive_intervals_to_handle; 551a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_.Add(interval); 552a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else if (interval->Covers(position)) { 553a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.Delete(interval); 554a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 555296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang --inactive_intervals_to_handle; 556a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Add(interval); 557a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 558a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 559a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 560acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray if (current->IsSlowPathSafepoint()) { 561acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray // Synthesized interval to record the maximum number of live registers 562acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray // at safepoints. No need to allocate a register for it. 563acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray maximum_number_of_live_registers_ = 564acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray std::max(maximum_number_of_live_registers_, active_.Size()); 565acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray DCHECK(unhandled_->IsEmpty() || unhandled_->Peek()->GetStart() > current->GetStart()); 566acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray continue; 567acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray } 568acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray 569a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (4) Try to find an available register. 570a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool success = TryAllocateFreeReg(current); 571a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 572a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (5) If no register could be found, we need to spill. 573a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (!success) { 574a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray success = AllocateBlockedReg(current); 575a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 576a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 577a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (6) If the interval had a register allocated, add it to the list of active 578a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // intervals. 579a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (success) { 580a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Add(current); 581a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 582a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 583a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 584a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 585a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// Find a free register. If multiple are found, pick the register that 586a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// is free the longest. 587a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::TryAllocateFreeReg(LiveInterval* current) { 588a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t* free_until = registers_array_; 589a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 590a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // First set all registers to be free. 591a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 592a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray free_until[i] = kMaxLifetimePosition; 593a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 594a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 595296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // For each active interval, set its register to not free. 596296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0, e = active_.Size(); i < e; ++i) { 597296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang LiveInterval* interval = active_.Get(i); 598296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK(interval->HasRegister()); 599296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang free_until[interval->GetRegister()] = 0; 600296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 601296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang 602a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each inactive interval, set its register to be free until 603a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // the next intersection with `current`. 604a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { 605a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* inactive = inactive_.Get(i); 606296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Temp/Slow-path-safepoint interval has no holes. 607296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK(!inactive->IsTemp() && !inactive->IsSlowPathSafepoint()); 608296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang if (!current->IsSplit() && !inactive->IsFixed()) { 609296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Neither current nor inactive are fixed. 610296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Thanks to SSA, a non-split interval starting in a hole of an 611296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // inactive interval should never intersect with that inactive interval. 612296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Only if it's not fixed though, because fixed intervals don't come from SSA. 613296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime); 614296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang continue; 615296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 616296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang 617a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(inactive->HasRegister()); 618296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang if (free_until[inactive->GetRegister()] == 0) { 619296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Already used by some active interval. No need to intersect. 620296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang continue; 621296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 622a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t next_intersection = inactive->FirstIntersectionWith(current); 623a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (next_intersection != kNoLifetime) { 624aac0f39a3501a7f7dd04b2342c2a16961969f139Nicolas Geoffray free_until[inactive->GetRegister()] = 625aac0f39a3501a7f7dd04b2342c2a16961969f139Nicolas Geoffray std::min(free_until[inactive->GetRegister()], next_intersection); 626a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 627a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 628a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 629a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray int reg = -1; 6303946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current->HasRegister()) { 6313946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Some instructions have a fixed register output. 6323946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray reg = current->GetRegister(); 6333946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray DCHECK_NE(free_until[reg], 0u); 6343946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 63501ef345767ea609417fc511e42007705c9667546Nicolas Geoffray int hint = current->FindFirstRegisterHint(free_until); 63601ef345767ea609417fc511e42007705c9667546Nicolas Geoffray if (hint != kNoRegister) { 63701ef345767ea609417fc511e42007705c9667546Nicolas Geoffray DCHECK(!IsBlocked(hint)); 63801ef345767ea609417fc511e42007705c9667546Nicolas Geoffray reg = hint; 63901ef345767ea609417fc511e42007705c9667546Nicolas Geoffray } else { 64001ef345767ea609417fc511e42007705c9667546Nicolas Geoffray // Pick the register that is free the longest. 64101ef345767ea609417fc511e42007705c9667546Nicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 64201ef345767ea609417fc511e42007705c9667546Nicolas Geoffray if (IsBlocked(i)) continue; 64301ef345767ea609417fc511e42007705c9667546Nicolas Geoffray if (reg == -1 || free_until[i] > free_until[reg]) { 64401ef345767ea609417fc511e42007705c9667546Nicolas Geoffray reg = i; 64501ef345767ea609417fc511e42007705c9667546Nicolas Geoffray if (free_until[i] == kMaxLifetimePosition) break; 64601ef345767ea609417fc511e42007705c9667546Nicolas Geoffray } 6473946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 648a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 649a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 650a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 651a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // If we could not find a register, we need to spill. 652a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (reg == -1 || free_until[reg] == 0) { 653a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 654a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 655a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 656a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray current->SetRegister(reg); 657a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (!current->IsDeadAt(free_until[reg])) { 658a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // If the register is only available for a subset of live ranges 659a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // covered by `current`, split `current` at the position where 660a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // the register is not available anymore. 661a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* split = Split(current, free_until[reg]); 662a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(split != nullptr); 6633946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 664a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 665a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 666a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 667a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 668a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::IsBlocked(int reg) const { 669102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return processing_core_registers_ 670102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ? blocked_core_registers_[reg] 671102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray : blocked_fp_registers_[reg]; 672a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 673a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 674a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// Find the register that is used the last, and spill the interval 675a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// that holds it. If the first use of `current` is after that register 676a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// we spill `current` instead. 677a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) { 678a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t first_register_use = current->FirstRegisterUse(); 679412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray if (first_register_use == kNoLifetime) { 68031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray AllocateSpillSlotFor(current); 681a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 682a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 683a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 684a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // First set all registers as not being used. 685a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t* next_use = registers_array_; 686a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 687a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray next_use[i] = kMaxLifetimePosition; 688a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 689a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 690a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each active interval, find the next use of its register after the 691a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // start of current. 692a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = active_.Size(); i < e; ++i) { 693a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* active = active_.Get(i); 694a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(active->HasRegister()); 69586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (active->IsFixed()) { 69686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[active->GetRegister()] = current->GetStart(); 69786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 69886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t use = active->FirstRegisterUseAfter(current->GetStart()); 69986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (use != kNoLifetime) { 70086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[active->GetRegister()] = use; 70186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 702a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 703a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 704a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 705a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each inactive interval, find the next use of its register after the 706a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // start of current. 707a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { 708a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* inactive = inactive_.Get(i); 709296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Temp/Slow-path-safepoint interval has no holes. 710296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK(!inactive->IsTemp() && !inactive->IsSlowPathSafepoint()); 711296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang if (!current->IsSplit() && !inactive->IsFixed()) { 712296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Neither current nor inactive are fixed. 713296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Thanks to SSA, a non-split interval starting in a hole of an 714296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // inactive interval should never intersect with that inactive interval. 715296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Only if it's not fixed though, because fixed intervals don't come from SSA. 716296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime); 717296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang continue; 718296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 719a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(inactive->HasRegister()); 72086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t next_intersection = inactive->FirstIntersectionWith(current); 72186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (next_intersection != kNoLifetime) { 72286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (inactive->IsFixed()) { 72386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[inactive->GetRegister()] = 72486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray std::min(next_intersection, next_use[inactive->GetRegister()]); 72586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 72686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t use = inactive->FirstRegisterUseAfter(current->GetStart()); 72786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (use != kNoLifetime) { 72886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[inactive->GetRegister()] = std::min(use, next_use[inactive->GetRegister()]); 72986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 73086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 731a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 732a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 733a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 734a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Pick the register that is used the last. 735a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray int reg = -1; 736a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 737a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (IsBlocked(i)) continue; 738a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (reg == -1 || next_use[i] > next_use[reg]) { 739a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray reg = i; 740a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (next_use[i] == kMaxLifetimePosition) break; 741a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 742a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 743a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 744a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (first_register_use >= next_use[reg]) { 745a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // If the first use of that instruction is after the last use of the found 746a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // register, we split this interval just before its first register use. 74731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray AllocateSpillSlotFor(current); 748c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray LiveInterval* split = Split(current, first_register_use - 1); 749c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray DCHECK_NE(current, split) << "There is not enough registers available for " 750c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray << split->GetParent()->GetDefinedBy()->DebugName(); 7513946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 752a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 753a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 754a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Use this register and spill the active and inactives interval that 755a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // have that register. 756a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray current->SetRegister(reg); 757a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 758a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = active_.Size(); i < e; ++i) { 759a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* active = active_.Get(i); 760a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (active->GetRegister() == reg) { 76186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(!active->IsFixed()); 762a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* split = Split(active, current->GetStart()); 763a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.DeleteAt(i); 764a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_.Add(active); 7653946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 766a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray break; 767a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 768a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 769a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 770296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { 771a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* inactive = inactive_.Get(i); 772a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (inactive->GetRegister() == reg) { 773296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang if (!current->IsSplit() && !inactive->IsFixed()) { 774296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Neither current nor inactive are fixed. 775296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Thanks to SSA, a non-split interval starting in a hole of an 776296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // inactive interval should never intersect with that inactive interval. 777296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Only if it's not fixed though, because fixed intervals don't come from SSA. 778296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime); 779296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang continue; 780296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 78186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t next_intersection = inactive->FirstIntersectionWith(current); 78286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (next_intersection != kNoLifetime) { 78386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (inactive->IsFixed()) { 78486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* split = Split(current, next_intersection); 7853946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 78686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 787296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang LiveInterval* split = Split(inactive, next_intersection); 78886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray inactive_.DeleteAt(i); 789296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang --i; 790296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang --e; 79186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray handled_.Add(inactive); 7923946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 79386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 79486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 795a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 796a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 797a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 798a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 799a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 800a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 801a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 8023946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffrayvoid RegisterAllocator::AddSorted(GrowableArray<LiveInterval*>* array, LiveInterval* interval) { 803c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray DCHECK(!interval->IsFixed() && !interval->HasSpillSlot()); 80486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t insert_at = 0; 8053946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = array->Size(); i > 0; --i) { 8063946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* current = array->Get(i - 1); 807a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (current->StartsAfter(interval)) { 80886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray insert_at = i; 809a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray break; 810acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray } else if ((current->GetStart() == interval->GetStart()) && current->IsSlowPathSafepoint()) { 811acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray // Ensure the slow path interval is the last to be processed at its location: we want the 812acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray // interval to know all live registers at this location. 813acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray DCHECK(i == 1 || array->Get(i - 2)->StartsAfter(current)); 814acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray insert_at = i; 815acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray break; 816a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 817a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 8183946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray array->InsertAt(insert_at, interval); 819a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 820a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 821a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas GeoffrayLiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) { 822a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(position >= interval->GetStart()); 823a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(!interval->IsDeadAt(position)); 824a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (position == interval->GetStart()) { 825a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Spill slot will be allocated when handling `interval` again. 826a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray interval->ClearRegister(); 827a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return interval; 828a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 829a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* new_interval = interval->SplitAt(position); 830a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return new_interval; 831a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 832a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 833a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 83431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffrayvoid RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) { 83531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* parent = interval->GetParent(); 83631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 83731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // An instruction gets a spill slot for its entire lifetime. If the parent 83831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // of this interval already has a spill slot, there is nothing to do. 83931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (parent->HasSpillSlot()) { 84031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray return; 84131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 84231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 84386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* defined_by = parent->GetDefinedBy(); 84486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (defined_by->IsParameterValue()) { 84586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Parameters have their own stack slot. 84686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray parent->SetSpillSlot(codegen_->GetStackSlotOfParameter(defined_by->AsParameterValue())); 84786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 84886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 84986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 85096f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray if (defined_by->IsConstant()) { 85196f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray // Constants don't need a spill slot. 85296f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray return; 85396f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray } 85496f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray 85531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* last_sibling = interval; 85631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray while (last_sibling->GetNextSibling() != nullptr) { 85731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray last_sibling = last_sibling->GetNextSibling(); 85831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 85931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray size_t end = last_sibling->GetEnd(); 86031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 861412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // Find an available spill slot. 862412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray size_t slot = 0; 863412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray for (size_t e = spill_slots_.Size(); slot < e; ++slot) { 864412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // We check if it is less rather than less or equal because the parallel move 865412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // resolver does not work when a single spill slot needs to be exchanged with 866412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // a double spill slot. The strict comparison avoids needing to exchange these 867412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // locations at the same lifetime position. 868412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray if (spill_slots_.Get(slot) < parent->GetStart() 869412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray && (slot == (e - 1) || spill_slots_.Get(slot + 1) < parent->GetStart())) { 870412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray break; 871412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } 872412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } 873412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray 87401ef345767ea609417fc511e42007705c9667546Nicolas Geoffray if (parent->NeedsTwoSpillSlots()) { 8753c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray if (slot == spill_slots_.Size()) { 8763c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray // We need a new spill slot. 8773c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray spill_slots_.Add(end); 8783c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray spill_slots_.Add(end); 8793c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray } else if (slot == spill_slots_.Size() - 1) { 8803c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray spill_slots_.Put(slot, end); 8813c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray spill_slots_.Add(end); 8823c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray } else { 8833c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray spill_slots_.Put(slot, end); 8843c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray spill_slots_.Put(slot + 1, end); 88531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 88631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 8873c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray if (slot == spill_slots_.Size()) { 8883c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray // We need a new spill slot. 8893c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray spill_slots_.Add(end); 8903c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray } else { 8913c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray spill_slots_.Put(slot, end); 8923c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray } 89331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 89431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 8953946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray parent->SetSpillSlot((slot + reserved_out_slots_) * kVRegSize); 89686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 89786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 8982a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffraystatic bool IsValidDestination(Location destination) { 899102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return destination.IsRegister() 900102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray || destination.IsFpuRegister() 901102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray || destination.IsStackSlot() 902102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray || destination.IsDoubleStackSlot(); 9032a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray} 9042a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray 905740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffrayvoid RegisterAllocator::AddInputMoveFor(HInstruction* user, 90686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 90786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 9082a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray DCHECK(IsValidDestination(destination)); 90986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 91086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 911476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain DCHECK(!user->IsPhi()); 91286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 913740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray HInstruction* previous = user->GetPrevious(); 91486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move = nullptr; 91586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (previous == nullptr 916476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain || !previous->IsParallelMove() 9178e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray || previous->GetLifetimePosition() < user->GetLifetimePosition()) { 91886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 9198e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray move->SetLifetimePosition(user->GetLifetimePosition()); 920740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray user->GetBlock()->InsertInstructionBefore(move, user); 92186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 92286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = previous->AsParallelMove(); 92386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 9248e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray DCHECK_EQ(move->GetLifetimePosition(), user->GetLifetimePosition()); 925740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray move->AddMove(new (allocator_) MoveOperands(source, destination, nullptr)); 92686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 92786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 92846fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffraystatic bool IsInstructionStart(size_t position) { 92946fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray return (position & 1) == 0; 93046fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray} 93146fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray 93246fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffraystatic bool IsInstructionEnd(size_t position) { 93346fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray return (position & 1) == 1; 93446fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray} 93546fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray 93686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertParallelMoveAt(size_t position, 937740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray HInstruction* instruction, 93886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 93986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 9402a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray DCHECK(IsValidDestination(destination)); 94186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 94286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 94386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* at = liveness_.GetInstructionFromPosition(position / 2); 94486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move; 94546fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray if (at == nullptr) { 94646fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray if (IsInstructionStart(position)) { 94746fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray // Block boundary, don't do anything the connection of split siblings will handle it. 94846fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray return; 94946fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray } else { 95046fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray // Move must happen before the first instruction of the block. 95146fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray at = liveness_.GetInstructionFromPosition((position + 1) / 2); 9525976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // Note that parallel moves may have already been inserted, so we explicitly 9535976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // ask for the first instruction of the block: `GetInstructionFromPosition` does 9545976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // not contain the moves. 9555976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray at = at->GetBlock()->GetFirstInstruction(); 9565976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray if (at->GetLifetimePosition() != position) { 9575976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray DCHECK_GT(at->GetLifetimePosition(), position); 95846fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 95946fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray move->SetLifetimePosition(position); 96046fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray at->GetBlock()->InsertInstructionBefore(move, at); 9615976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray } else { 9625976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray DCHECK(at->IsParallelMove()); 9635976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray move = at->AsParallelMove(); 96446fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray } 96546fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray } 96646fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray } else if (IsInstructionEnd(position)) { 96786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Move must happen after the instruction. 96886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(!at->IsControlFlow()); 96986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = at->GetNext()->AsParallelMove(); 970e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting siblings in a same block. We need to 971e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // differentiate it with moves for connecting blocks, and input moves. 9728e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray if (move == nullptr || move->GetLifetimePosition() > position) { 97386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 97486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->SetLifetimePosition(position); 97586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray at->GetBlock()->InsertInstructionBefore(move, at->GetNext()); 97686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 97786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 97886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Move must happen before the instruction. 97986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* previous = at->GetPrevious(); 980740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray if (previous == nullptr 981740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray || !previous->IsParallelMove() 982740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray || previous->GetLifetimePosition() != position) { 983740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray // If the previous is a parallel move, then its position must be lower 984740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray // than the given `position`: it was added just after the non-parallel 985740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray // move instruction that precedes `instruction`. 986740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray DCHECK(previous == nullptr 987740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray || !previous->IsParallelMove() 988740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray || previous->GetLifetimePosition() < position); 98986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 99086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->SetLifetimePosition(position); 99186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray at->GetBlock()->InsertInstructionBefore(move, at); 99286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 99386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = previous->AsParallelMove(); 99486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 99586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 99601ef345767ea609417fc511e42007705c9667546Nicolas Geoffray DCHECK_EQ(move->GetLifetimePosition(), position); 997740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray move->AddMove(new (allocator_) MoveOperands(source, destination, instruction)); 99886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 99986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 100086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertParallelMoveAtExitOf(HBasicBlock* block, 1001740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray HInstruction* instruction, 100286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 100386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 10042a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray DCHECK(IsValidDestination(destination)); 100586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 100686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 100786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK_EQ(block->GetSuccessors().Size(), 1u); 100886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* last = block->GetLastInstruction(); 1009360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray // We insert moves at exit for phi predecessors and connecting blocks. 1010360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray // A block ending with an if cannot branch to a block with phis because 1011360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray // we do not allow critical edges. It can also not connect 1012360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray // a split interval between two blocks: the move has to happen in the successor. 1013360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray DCHECK(!last->IsIf()); 101486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* previous = last->GetPrevious(); 101586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move; 1016e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting blocks. We need to differentiate 1017e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // it with moves for connecting siblings in a same block, and output moves. 10185976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray size_t position = last->GetLifetimePosition(); 1019740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray if (previous == nullptr || !previous->IsParallelMove() 10205976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray || previous->AsParallelMove()->GetLifetimePosition() != position) { 102186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 10225976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray move->SetLifetimePosition(position); 102386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray block->InsertInstructionBefore(move, last); 102486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 102586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = previous->AsParallelMove(); 102686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 1027740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray move->AddMove(new (allocator_) MoveOperands(source, destination, instruction)); 102886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 102986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 103086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertParallelMoveAtEntryOf(HBasicBlock* block, 1031740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray HInstruction* instruction, 103286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 103386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 10342a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray DCHECK(IsValidDestination(destination)); 103586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 103686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 103786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* first = block->GetFirstInstruction(); 103886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move = first->AsParallelMove(); 1039e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting blocks. We need to differentiate 1040e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // it with moves for connecting siblings in a same block, and input moves. 1041e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray if (move == nullptr || move->GetLifetimePosition() != block->GetLifetimeStart()) { 104286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 104386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->SetLifetimePosition(block->GetLifetimeStart()); 104486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray block->InsertInstructionBefore(move, first); 104586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 1046740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray move->AddMove(new (allocator_) MoveOperands(source, destination, instruction)); 104786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 104886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 104986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertMoveAfter(HInstruction* instruction, 105086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 105186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 10522a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray DCHECK(IsValidDestination(destination)); 105386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 105486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1055476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain if (instruction->IsPhi()) { 1056740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAtEntryOf(instruction->GetBlock(), instruction, source, destination); 105786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 105886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 105986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1060e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray size_t position = instruction->GetLifetimePosition() + 1; 106186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move = instruction->GetNext()->AsParallelMove(); 1062e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for moving the output of an instruction. We need 1063e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // to differentiate with input moves, moves for connecting siblings in a 1064e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // and moves for connecting blocks. 1065e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray if (move == nullptr || move->GetLifetimePosition() != position) { 106686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 1067e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray move->SetLifetimePosition(position); 106886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray instruction->GetBlock()->InsertInstructionBefore(move, instruction->GetNext()); 106986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 1070740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray move->AddMove(new (allocator_) MoveOperands(source, destination, instruction)); 107186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 107286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 107386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::ConnectSiblings(LiveInterval* interval) { 107486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = interval; 107586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->HasSpillSlot() && current->HasRegister()) { 107686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // We spill eagerly, so move must be at definition. 107786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InsertMoveAfter(interval->GetDefinedBy(), 1078102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray interval->IsFloatingPoint() 1079102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ? Location::FpuRegisterLocation(interval->GetRegister()) 1080102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray : Location::RegisterLocation(interval->GetRegister()), 108101ef345767ea609417fc511e42007705c9667546Nicolas Geoffray interval->NeedsTwoSpillSlots() 1082412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray ? Location::DoubleStackSlot(interval->GetParent()->GetSpillSlot()) 1083412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray : Location::StackSlot(interval->GetParent()->GetSpillSlot())); 108486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 108586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray UsePosition* use = current->GetFirstUse(); 108686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 108786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Walk over all siblings, updating locations of use positions, and 108886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // connecting them when they are adjacent. 108986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray do { 109001ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location source = current->ToLocation(); 109186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 109286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Walk over all uses covered by this interval, and update the location 109386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // information. 109486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray while (use != nullptr && use->GetPosition() <= current->GetEnd()) { 10953946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LocationSummary* locations = use->GetUser()->GetLocations(); 10963946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (use->GetIsEnvironment()) { 10973946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray locations->SetEnvironmentAt(use->GetInputIndex(), source); 10983946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 109986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location expected_location = locations->InAt(use->GetInputIndex()); 110086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (expected_location.IsUnallocated()) { 110186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray locations->SetInAt(use->GetInputIndex(), source); 11022a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray } else if (!expected_location.IsConstant()) { 110386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray AddInputMoveFor(use->GetUser(), source, expected_location); 110486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 110586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 110686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray use = use->GetNext(); 110786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 110886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 110986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // If the next interval starts just after this one, and has a register, 111086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // insert a move. 111186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* next_sibling = current->GetNextSibling(); 111286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (next_sibling != nullptr 111386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && next_sibling->HasRegister() 111486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && current->GetEnd() == next_sibling->GetStart()) { 111501ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location destination = next_sibling->ToLocation(); 1116740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAt(current->GetEnd(), interval->GetDefinedBy(), source, destination); 111786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 11183946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 11193946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // At each safepoint, we record stack and register information. 11203946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0, e = safepoints_.Size(); i < e; ++i) { 11213946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray HInstruction* safepoint = safepoints_.Get(i); 11223946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t position = safepoint->GetLifetimePosition(); 11233946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LocationSummary* locations = safepoint->GetLocations(); 1124b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray if (!current->Covers(position)) { 1125b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray continue; 1126b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray } 1127b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray if (interval->GetStart() == position) { 1128b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // The safepoint is for this instruction, so the location of the instruction 1129b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // does not need to be saved. 1130b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray continue; 1131b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray } 11323946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 11333bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray if ((current->GetType() == Primitive::kPrimNot) && current->GetParent()->HasSpillSlot()) { 11343946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray locations->SetStackBit(current->GetParent()->GetSpillSlot() / kVRegSize); 11353946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 11363946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 11373946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray switch (source.GetKind()) { 11383946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kRegister: { 11393bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray locations->AddLiveRegister(source); 114087d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray DCHECK_LE(locations->GetNumberOfLiveRegisters(), maximum_number_of_live_registers_); 1141acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray 11423946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current->GetType() == Primitive::kPrimNot) { 114356b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray locations->SetRegisterBit(source.reg()); 11443946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 11453946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray break; 11463946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 1147102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray case Location::kFpuRegister: { 1148102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray locations->AddLiveRegister(source); 1149102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray break; 1150102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 11513946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kStackSlot: // Fall-through 11523946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kDoubleStackSlot: // Fall-through 11533946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kConstant: { 11543946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Nothing to do. 11553946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray break; 11563946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 11573946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray default: { 11583946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LOG(FATAL) << "Unexpected location for object"; 11593946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 11603946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 11613946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 116286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current = next_sibling; 116386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } while (current != nullptr); 116486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(use == nullptr); 116586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 116686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 116786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval, 116886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* from, 116986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* to) const { 117086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (interval->GetNextSibling() == nullptr) { 117186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Nothing to connect. The whole range was allocated to the same location. 117286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 117386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 117486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 117546fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray // Intervals end at the lifetime end of a block. The decrement by one 117646fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray // ensures the `Cover` call will return true. 117786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t from_position = from->GetLifetimeEnd() - 1; 117846fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray size_t to_position = to->GetLifetimeStart(); 117986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 118086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* destination = nullptr; 118186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* source = nullptr; 118286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 118386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = interval; 118486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 118586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Check the intervals that cover `from` and `to`. 118686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray while ((current != nullptr) && (source == nullptr || destination == nullptr)) { 118786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->Covers(from_position)) { 118886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(source == nullptr); 118986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray source = current; 119086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 119186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->Covers(to_position)) { 119286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(destination == nullptr); 119386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray destination = current; 119486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 119586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 119686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current = current->GetNextSibling(); 119786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 119886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 119986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (destination == source) { 120086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Interval was not split. 120186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 120286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 120386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 12048ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray DCHECK(destination != nullptr && source != nullptr); 12058ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray 120686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (!destination->HasRegister()) { 120786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Values are eagerly spilled. Spill slot already contains appropriate value. 120886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 120986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 121086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 121186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // If `from` has only one successor, we can put the moves at the exit of it. Otherwise 121286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // we need to put the moves at the entry of `to`. 121386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (from->GetSuccessors().Size() == 1) { 1214740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAtExitOf(from, 1215740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray interval->GetParent()->GetDefinedBy(), 121601ef345767ea609417fc511e42007705c9667546Nicolas Geoffray source->ToLocation(), 121701ef345767ea609417fc511e42007705c9667546Nicolas Geoffray destination->ToLocation()); 121886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 121986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK_EQ(to->GetPredecessors().Size(), 1u); 1220740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAtEntryOf(to, 1221740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray interval->GetParent()->GetDefinedBy(), 122201ef345767ea609417fc511e42007705c9667546Nicolas Geoffray source->ToLocation(), 122301ef345767ea609417fc511e42007705c9667546Nicolas Geoffray destination->ToLocation()); 122486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 122586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 122686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 122786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::Resolve() { 12283bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray codegen_->ComputeFrameSize( 12293bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray spill_slots_.Size(), maximum_number_of_live_registers_, reserved_out_slots_); 123086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 123186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Adjust the Out Location of instructions. 123286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // TODO: Use pointers of Location inside LiveInterval to avoid doing another iteration. 123386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { 123486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 123586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = instruction->GetLiveInterval(); 123686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LocationSummary* locations = instruction->GetLocations(); 123786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location location = locations->Out(); 1238476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain if (instruction->IsParameterValue()) { 123986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Now that we know the frame size, adjust the parameter's location. 124086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (location.IsStackSlot()) { 124186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray location = Location::StackSlot(location.GetStackIndex() + codegen_->GetFrameSize()); 124286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(location.GetStackIndex()); 1243f43083d560565aea46c602adb86423daeefe589dNicolas Geoffray locations->UpdateOut(location); 124486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else if (location.IsDoubleStackSlot()) { 124586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray location = Location::DoubleStackSlot(location.GetStackIndex() + codegen_->GetFrameSize()); 124686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(location.GetStackIndex()); 1247f43083d560565aea46c602adb86423daeefe589dNicolas Geoffray locations->UpdateOut(location); 124886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else if (current->HasSpillSlot()) { 124986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(current->GetSpillSlot() + codegen_->GetFrameSize()); 125086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 125186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 125286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 125301ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location source = current->ToLocation(); 125486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 125586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (location.IsUnallocated()) { 125686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (location.GetPolicy() == Location::kSameAsFirstInput) { 1257d0d4852847432368b090c184d6639e573538dccfCalin Juravle if (locations->InAt(0).IsUnallocated()) { 1258d0d4852847432368b090c184d6639e573538dccfCalin Juravle locations->SetInAt(0, source); 1259d0d4852847432368b090c184d6639e573538dccfCalin Juravle } else { 1260d0d4852847432368b090c184d6639e573538dccfCalin Juravle DCHECK(locations->InAt(0).Equals(source)); 1261d0d4852847432368b090c184d6639e573538dccfCalin Juravle } 126286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 126386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray locations->SetOut(source); 126486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 126586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(source.Equals(location)); 126686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 126786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 126886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 126986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Connect siblings. 127086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { 127186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 127286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ConnectSiblings(instruction->GetLiveInterval()); 127386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 127486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 127586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Resolve non-linear control flow across branches. Order does not matter. 127686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (HLinearOrderIterator it(liveness_); !it.Done(); it.Advance()) { 127786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* block = it.Current(); 127886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray BitVector* live = liveness_.GetLiveInSet(*block); 127986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (uint32_t idx : live->Indexes()) { 128086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* current = liveness_.GetInstructionFromSsaIndex(idx); 128186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* interval = current->GetLiveInterval(); 128286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { 128386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ConnectSplitSiblings(interval, block->GetPredecessors().Get(i), block); 128486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 128586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 128686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 128786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 128886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Resolve phi inputs. Order does not matter. 128986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (HLinearOrderIterator it(liveness_); !it.Done(); it.Advance()) { 129086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* current = it.Current(); 1291277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe for (HInstructionIterator inst_it(current->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 1292277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe HInstruction* phi = inst_it.Current(); 129386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = current->GetPredecessors().Size(); i < e; ++i) { 129486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* predecessor = current->GetPredecessors().Get(i); 129586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK_EQ(predecessor->GetSuccessors().Size(), 1u); 129686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* input = phi->InputAt(i); 129701ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location source = input->GetLiveInterval()->GetLocationAt( 129801ef345767ea609417fc511e42007705c9667546Nicolas Geoffray predecessor->GetLifetimeEnd() - 1); 129901ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location destination = phi->GetLiveInterval()->ToLocation(); 1300740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAtExitOf(predecessor, nullptr, source, destination); 130186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 130286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 130386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 13043946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 13053946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Assign temp locations. 13063946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray HInstruction* current = nullptr; 13073946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t temp_index = 0; 13083946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < temp_intervals_.Size(); ++i) { 13093946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* temp = temp_intervals_.Get(i); 131001ef345767ea609417fc511e42007705c9667546Nicolas Geoffray HInstruction* at = liveness_.GetTempUser(temp); 131101ef345767ea609417fc511e42007705c9667546Nicolas Geoffray if (at != current) { 13123946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray temp_index = 0; 131301ef345767ea609417fc511e42007705c9667546Nicolas Geoffray current = at; 13143946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 131501ef345767ea609417fc511e42007705c9667546Nicolas Geoffray LocationSummary* locations = at->GetLocations(); 13165368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain switch (temp->GetType()) { 13175368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain case Primitive::kPrimInt: 13185368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain locations->SetTempAt( 13195368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain temp_index++, Location::RegisterLocation(temp->GetRegister())); 13205368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain break; 13215368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain 13225368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain case Primitive::kPrimDouble: 13235368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain // TODO: Support the case of ARM, where a double value 13245368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain // requires an FPU register pair (note that the ARM back end 13255368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain // does not yet use this register allocator when a method uses 13265368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain // floats or doubles). 13275368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain DCHECK(codegen_->GetInstructionSet() != kArm 13285368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain && codegen_->GetInstructionSet() != kThumb2); 13295368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain locations->SetTempAt( 13305368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain temp_index++, Location::FpuRegisterLocation(temp->GetRegister())); 13315368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain break; 13325368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain 13335368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain default: 13345368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LOG(FATAL) << "Unexpected type for temporary location " 13355368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain << temp->GetType(); 13365368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain } 13373946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 133831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray} 133931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 1340a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} // namespace art 1341