register_allocator.cc revision 7c8d009552545e6f1fd6036721e4e42e3fd14697
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 30840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray// For simplicity, we implement register pairs as (reg, reg + 1). 31840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray// Note that this is a requirement for double registers on ARM, since we 32840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray// allocate SRegister. 33840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffraystatic int GetHighForLowRegister(int reg) { return reg + 1; } 34840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffraystatic bool IsLowRegister(int reg) { return (reg & 1) == 0; } 35840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 3686dbb9a12119273039ce272b41c809fa548b37b6Nicolas GeoffrayRegisterAllocator::RegisterAllocator(ArenaAllocator* allocator, 3786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray CodeGenerator* codegen, 3886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray const SsaLivenessAnalysis& liveness) 39a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray : allocator_(allocator), 40a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen_(codegen), 4186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray liveness_(liveness), 423946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_core_intervals_(allocator, 0), 433946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_fp_intervals_(allocator, 0), 443946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_(nullptr), 45a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_(allocator, 0), 46a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_(allocator, 0), 47a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_(allocator, 0), 48102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_core_register_intervals_(allocator, codegen->GetNumberOfCoreRegisters()), 49102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_fp_register_intervals_(allocator, codegen->GetNumberOfFloatingPointRegisters()), 503946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray temp_intervals_(allocator, 4), 5131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray spill_slots_(allocator, kDefaultNumberOfSpillSlots), 523946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray safepoints_(allocator, 0), 53a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray processing_core_registers_(false), 54a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray number_of_registers_(-1), 55a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray registers_array_(nullptr), 56102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray blocked_core_registers_(codegen->GetBlockedCoreRegisters()), 57102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray blocked_fp_registers_(codegen->GetBlockedFloatingPointRegisters()), 583bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray reserved_out_slots_(0), 59f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell maximum_number_of_live_core_registers_(0), 60f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell maximum_number_of_live_fp_registers_(0) { 61988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray static constexpr bool kIsBaseline = false; 62988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray codegen->SetupBlockedRegisters(kIsBaseline); 63102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_core_register_intervals_.SetSize(codegen->GetNumberOfCoreRegisters()); 64102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_fp_register_intervals_.SetSize(codegen->GetNumberOfFloatingPointRegisters()); 653946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Always reserve for the current method and the graph's max out registers. 663946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // TODO: compute it instead. 673946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray reserved_out_slots_ = 1 + codegen->GetGraph()->GetMaximumNumberOfOutVRegs(); 68a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 69a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 7086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraybool RegisterAllocator::CanAllocateRegistersFor(const HGraph& graph, 7186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InstructionSet instruction_set) { 7286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (!Supports(instruction_set)) { 7386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return false; 7486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 756c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (instruction_set == kArm64 766c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray || instruction_set == kX86_64 776c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray || instruction_set == kArm 786c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray || instruction_set == kThumb2) { 793e69f16ae3fddfd24f4f0e29deb106d564ab296cAlexandre Rames return true; 803e69f16ae3fddfd24f4f0e29deb106d564ab296cAlexandre Rames } 8186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = graph.GetBlocks().Size(); i < e; ++i) { 8286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (HInstructionIterator it(graph.GetBlocks().Get(i)->GetInstructions()); 8386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray !it.Done(); 8486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray it.Advance()) { 8586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* current = it.Current(); 867c8d009552545e6f1fd6036721e4e42e3fd14697Mark Mendell if (instruction_set == kX86 && current->GetType() == Primitive::kPrimLong) { 877c8d009552545e6f1fd6036721e4e42e3fd14697Mark Mendell return false; 88102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 8986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 9086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 9186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return true; 9286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 9386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 9486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraystatic bool ShouldProcess(bool processing_core_registers, LiveInterval* interval) { 953946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (interval == nullptr) return false; 9686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray bool is_core_register = (interval->GetType() != Primitive::kPrimDouble) 9786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && (interval->GetType() != Primitive::kPrimFloat); 98a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return processing_core_registers == is_core_register; 99a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 100a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 10186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::AllocateRegisters() { 10286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray AllocateRegistersInternal(); 10386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Resolve(); 10486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 10586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (kIsDebugBuild) { 10686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray processing_core_registers_ = true; 10786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ValidateInternal(true); 10886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray processing_core_registers_ = false; 10986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ValidateInternal(true); 1105976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // Check that the linear order is still correct with regards to lifetime positions. 1115976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // Since only parallel moves have been inserted during the register allocation, 1125976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // these checks are mostly for making sure these moves have been added correctly. 1135976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray size_t current_liveness = 0; 1145976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray for (HLinearOrderIterator it(liveness_); !it.Done(); it.Advance()) { 1155976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray HBasicBlock* block = it.Current(); 1165976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 1175976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray HInstruction* instruction = inst_it.Current(); 1185976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray DCHECK_LE(current_liveness, instruction->GetLifetimePosition()); 1195976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray current_liveness = instruction->GetLifetimePosition(); 1205976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray } 1215976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray for (HInstructionIterator inst_it(block->GetInstructions()); 1225976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray !inst_it.Done(); 1235976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray inst_it.Advance()) { 1245976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray HInstruction* instruction = inst_it.Current(); 1255976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray DCHECK_LE(current_liveness, instruction->GetLifetimePosition()) << instruction->DebugName(); 1265976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray current_liveness = instruction->GetLifetimePosition(); 1275976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray } 1285976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray } 12986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 13086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 13186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 13286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::BlockRegister(Location location, 13386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t start, 134102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray size_t end) { 13556b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray int reg = location.reg(); 136102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray DCHECK(location.IsRegister() || location.IsFpuRegister()); 137102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* interval = location.IsRegister() 138102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ? physical_core_register_intervals_.Get(reg) 139102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray : physical_fp_register_intervals_.Get(reg); 140102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray Primitive::Type type = location.IsRegister() 141102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ? Primitive::kPrimInt 142840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray : Primitive::kPrimFloat; 14386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (interval == nullptr) { 14486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray interval = LiveInterval::MakeFixedInterval(allocator_, reg, type); 145102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (location.IsRegister()) { 146102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_core_register_intervals_.Put(reg, interval); 147102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 148102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_fp_register_intervals_.Put(reg, interval); 149102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 15086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 15186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(interval->GetRegister() == reg); 15286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray interval->AddRange(start, end); 15386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 15486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 15586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::AllocateRegistersInternal() { 1563946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Iterate post-order, to ensure the list is sorted, and the last added interval 1573946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // is the one with the lowest start position. 1583946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (HLinearPostOrderIterator it(liveness_); !it.Done(); it.Advance()) { 1593946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray HBasicBlock* block = it.Current(); 160277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe for (HBackwardInstructionIterator back_it(block->GetInstructions()); !back_it.Done(); 161277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe back_it.Advance()) { 162277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe ProcessInstruction(back_it.Current()); 1633946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 164277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 165277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe ProcessInstruction(inst_it.Current()); 1663946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 1673946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 168a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1693946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray number_of_registers_ = codegen_->GetNumberOfCoreRegisters(); 170a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_); 1713946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray processing_core_registers_ = true; 1723946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_ = &unhandled_core_intervals_; 173102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0, e = physical_core_register_intervals_.Size(); i < e; ++i) { 174102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* fixed = physical_core_register_intervals_.Get(i); 175102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (fixed != nullptr) { 176296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Fixed interval is added to inactive_ instead of unhandled_. 177296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // It's also the only type of inactive interval whose start position 178296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // can be after the current interval during linear scan. 179296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Fixed interval is never split and never moves to unhandled_. 180102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray inactive_.Add(fixed); 181102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 182102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 1833946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LinearScan(); 184a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1853946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray inactive_.Reset(); 1863946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray active_.Reset(); 1873946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray handled_.Reset(); 188a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1893946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray number_of_registers_ = codegen_->GetNumberOfFloatingPointRegisters(); 1903946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_); 1913946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray processing_core_registers_ = false; 1923946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_ = &unhandled_fp_intervals_; 193102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0, e = physical_fp_register_intervals_.Size(); i < e; ++i) { 194102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* fixed = physical_fp_register_intervals_.Get(i); 195102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (fixed != nullptr) { 196296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Fixed interval is added to inactive_ instead of unhandled_. 197296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // It's also the only type of inactive interval whose start position 198296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // can be after the current interval during linear scan. 199296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Fixed interval is never split and never moves to unhandled_. 200102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray inactive_.Add(fixed); 201102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 202102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 2033946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LinearScan(); 2043946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray} 20586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 2063946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffrayvoid RegisterAllocator::ProcessInstruction(HInstruction* instruction) { 2073946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LocationSummary* locations = instruction->GetLocations(); 2083946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t position = instruction->GetLifetimePosition(); 2093946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 2103946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (locations == nullptr) return; 2113946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 2123946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Create synthesized intervals for temporaries. 2133946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < locations->GetTempCount(); ++i) { 2143946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray Location temp = locations->GetTemp(i); 21552839d17c06175e19ca4a093fb878450d1c4310dNicolas Geoffray if (temp.IsRegister() || temp.IsFpuRegister()) { 216102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray BlockRegister(temp, position, position + 1); 2173946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 218102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray DCHECK(temp.IsUnallocated()); 2195368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain switch (temp.GetPolicy()) { 2205368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain case Location::kRequiresRegister: { 2215368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LiveInterval* interval = 2225368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimInt); 2235368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain temp_intervals_.Add(interval); 2245368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain interval->AddRange(position, position + 1); 2255368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain unhandled_core_intervals_.Add(interval); 2265368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain break; 2275368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain } 2285368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain 2295368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain case Location::kRequiresFpuRegister: { 2305368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LiveInterval* interval = 2315368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimDouble); 2325368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain temp_intervals_.Add(interval); 2335368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain interval->AddRange(position, position + 1); 234840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (codegen_->NeedsTwoRegisters(Primitive::kPrimDouble)) { 235840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray interval->AddHighInterval(true); 236840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray LiveInterval* high = interval->GetHighInterval(); 237840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray temp_intervals_.Add(high); 238840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray unhandled_fp_intervals_.Add(high); 239840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 2405368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain unhandled_fp_intervals_.Add(interval); 2415368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain break; 2425368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain } 2435368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain 2445368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain default: 2455368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LOG(FATAL) << "Unexpected policy for temporary location " 2465368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain << temp.GetPolicy(); 2475368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain } 248a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 249a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 25086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 2513bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray bool core_register = (instruction->GetType() != Primitive::kPrimDouble) 2523bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray && (instruction->GetType() != Primitive::kPrimFloat); 2533bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray 2543946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (locations->CanCall()) { 2553bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray if (!instruction->IsSuspendCheck()) { 2563bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray codegen_->MarkNotLeaf(); 2573bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 2583946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray safepoints_.Add(instruction); 2593bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray if (locations->OnlyCallsOnSlowPath()) { 2603bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // We add a synthesized range at this position to record the live registers 2613bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // at this position. Ideally, we could just update the safepoints when locations 2623bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // are updated, but we currently need to know the full stack size before updating 2633bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // locations (because of parameters and the fact that we don't have a frame pointer). 2643bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // And knowing the full stack size requires to know the maximum number of live 2653bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // registers at calls in slow paths. 2663bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // By adding the following interval in the algorithm, we can compute this 2673bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // maximum before updating locations. 2683bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray LiveInterval* interval = LiveInterval::MakeSlowPathInterval(allocator_, instruction); 269acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray interval->AddRange(position, position + 1); 27087d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray AddSorted(&unhandled_core_intervals_, interval); 27187d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray AddSorted(&unhandled_fp_intervals_, interval); 2723bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 2733bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 2743bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray 2753bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray if (locations->WillCall()) { 2763946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Block all registers. 2773946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < codegen_->GetNumberOfCoreRegisters(); ++i) { 278988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray if (!codegen_->IsCoreCalleeSaveRegister(i)) { 279988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray BlockRegister(Location::RegisterLocation(i), 280988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray position, 281988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray position + 1); 282988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray } 283102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 284102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0; i < codegen_->GetNumberOfFloatingPointRegisters(); ++i) { 285988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray if (!codegen_->IsFloatingPointCalleeSaveRegister(i)) { 286988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray BlockRegister(Location::FpuRegisterLocation(i), 287988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray position, 288988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray position + 1); 289988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray } 2903946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 2913946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 2923946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 2933946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < instruction->InputCount(); ++i) { 2943946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray Location input = locations->InAt(i); 295102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (input.IsRegister() || input.IsFpuRegister()) { 296102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray BlockRegister(input, position, position + 1); 297840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (input.IsPair()) { 298840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray BlockRegister(input.ToLow(), position, position + 1); 299840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray BlockRegister(input.ToHigh(), position, position + 1); 3003946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3013946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3023946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 3033946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* current = instruction->GetLiveInterval(); 3043946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current == nullptr) return; 3053946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 306102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray GrowableArray<LiveInterval*>& unhandled = core_register 307102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ? unhandled_core_intervals_ 308102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray : unhandled_fp_intervals_; 309102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray 3107690562d40878f44823d5fb03a2084cfc677ec4aNicolas Geoffray DCHECK(unhandled.IsEmpty() || current->StartsBeforeOrAt(unhandled.Peek())); 31187d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray 312840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (codegen_->NeedsTwoRegisters(current->GetType())) { 313840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray current->AddHighInterval(); 314840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 315840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 3163946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Some instructions define their output in fixed register/stack slot. We need 3173946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // to ensure we know these locations before doing register allocation. For a 3183946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // given register, we create an interval that covers these locations. The register 3193946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // will be unavailable at these locations when trying to allocate one for an 3203946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // interval. 3213946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // 3223946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // The backwards walking ensures the ranges are ordered on increasing start positions. 3233946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray Location output = locations->Out(); 324d0d4852847432368b090c184d6639e573538dccfCalin Juravle if (output.IsUnallocated() && output.GetPolicy() == Location::kSameAsFirstInput) { 325d0d4852847432368b090c184d6639e573538dccfCalin Juravle Location first = locations->InAt(0); 326d0d4852847432368b090c184d6639e573538dccfCalin Juravle if (first.IsRegister() || first.IsFpuRegister()) { 327d0d4852847432368b090c184d6639e573538dccfCalin Juravle current->SetFrom(position + 1); 328d0d4852847432368b090c184d6639e573538dccfCalin Juravle current->SetRegister(first.reg()); 329840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (first.IsPair()) { 330840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray current->SetFrom(position + 1); 331840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray current->SetRegister(first.low()); 332840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray LiveInterval* high = current->GetHighInterval(); 333840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray high->SetRegister(first.high()); 334840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray high->SetFrom(position + 1); 335d0d4852847432368b090c184d6639e573538dccfCalin Juravle } 336d0d4852847432368b090c184d6639e573538dccfCalin Juravle } else if (output.IsRegister() || output.IsFpuRegister()) { 3373946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Shift the interval's start by one to account for the blocked register. 3383946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray current->SetFrom(position + 1); 33956b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray current->SetRegister(output.reg()); 340102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray BlockRegister(output, position, position + 1); 341840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (output.IsPair()) { 342840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray current->SetFrom(position + 1); 343840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray current->SetRegister(output.low()); 344840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray LiveInterval* high = current->GetHighInterval(); 345840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray high->SetRegister(output.high()); 346840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray high->SetFrom(position + 1); 347840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray BlockRegister(output.ToLow(), position, position + 1); 348840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray BlockRegister(output.ToHigh(), position, position + 1); 3493946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else if (output.IsStackSlot() || output.IsDoubleStackSlot()) { 3503946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray current->SetSpillSlot(output.GetStackIndex()); 351840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else { 352840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(output.IsUnallocated() || output.IsConstant()); 3533946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3543946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 3553946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // If needed, add interval to the list of unhandled intervals. 3563946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current->HasSpillSlot() || instruction->IsConstant()) { 357c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray // Split just before first register use. 3583946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t first_register_use = current->FirstRegisterUse(); 3593946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (first_register_use != kNoLifetime) { 360c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray LiveInterval* split = Split(current, first_register_use - 1); 361b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // Don't add directly to `unhandled`, it needs to be sorted and the start 3623946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // of this new interval might be after intervals already in the list. 3633946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(&unhandled, split); 3643946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 3653946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Nothing to do, we won't allocate a register for this value. 3663946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3673946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 368b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // Don't add directly to `unhandled`, temp or safepoint intervals 369b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // for this instruction may have been added, and those can be 370b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // processed first. 371b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray AddSorted(&unhandled, current); 3723946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 373a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 374a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 37531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffrayclass AllRangesIterator : public ValueObject { 37631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray public: 37731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray explicit AllRangesIterator(LiveInterval* interval) 37831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray : current_interval_(interval), 37931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_(interval->GetFirstRange()) {} 38031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 38131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray bool Done() const { return current_interval_ == nullptr; } 38231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveRange* CurrentRange() const { return current_range_; } 38331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* CurrentInterval() const { return current_interval_; } 38431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 38531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray void Advance() { 38631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_ = current_range_->GetNext(); 38731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current_range_ == nullptr) { 38831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_interval_ = current_interval_->GetNextSibling(); 38931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current_interval_ != nullptr) { 39031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_ = current_interval_->GetFirstRange(); 39131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 39231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 39331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 39431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 39531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray private: 39631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* current_interval_; 39731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveRange* current_range_; 39831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 39931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray DISALLOW_COPY_AND_ASSIGN(AllRangesIterator); 40031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray}; 40131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 40286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraybool RegisterAllocator::ValidateInternal(bool log_fatal_on_failure) const { 40386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // To simplify unit testing, we eagerly create the array of intervals, and 40486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // call the helper method. 40586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray GrowableArray<LiveInterval*> intervals(allocator_, 0); 40686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0; i < liveness_.GetNumberOfSsaValues(); ++i) { 40786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 40886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (ShouldProcess(processing_core_registers_, instruction->GetLiveInterval())) { 40986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray intervals.Add(instruction->GetLiveInterval()); 41086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 41186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 41286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 413102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (processing_core_registers_) { 414102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0, e = physical_core_register_intervals_.Size(); i < e; ++i) { 415102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* fixed = physical_core_register_intervals_.Get(i); 416102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (fixed != nullptr) { 417102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray intervals.Add(fixed); 418102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 419102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 420102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 421102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0, e = physical_fp_register_intervals_.Size(); i < e; ++i) { 422102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* fixed = physical_fp_register_intervals_.Get(i); 423102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (fixed != nullptr) { 424102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray intervals.Add(fixed); 425102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 42686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 42786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 42886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 4293946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0, e = temp_intervals_.Size(); i < e; ++i) { 4303946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* temp = temp_intervals_.Get(i); 4313946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (ShouldProcess(processing_core_registers_, temp)) { 4323946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray intervals.Add(temp); 4333946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 4343946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 4353946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 4363946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray return ValidateIntervals(intervals, spill_slots_.Size(), reserved_out_slots_, *codegen_, 4373946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray allocator_, processing_core_registers_, log_fatal_on_failure); 43886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 43986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 44031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffraybool RegisterAllocator::ValidateIntervals(const GrowableArray<LiveInterval*>& intervals, 44131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray size_t number_of_spill_slots, 4423946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t number_of_out_slots, 443a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray const CodeGenerator& codegen, 444a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray ArenaAllocator* allocator, 445a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool processing_core_registers, 446a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool log_fatal_on_failure) { 447a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t number_of_registers = processing_core_registers 448a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray ? codegen.GetNumberOfCoreRegisters() 449a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray : codegen.GetNumberOfFloatingPointRegisters(); 45031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray GrowableArray<ArenaBitVector*> liveness_of_values( 45131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray allocator, number_of_registers + number_of_spill_slots); 452a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 453a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Allocate a bit vector per register. A live interval that has a register 454a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // allocated will populate the associated bit vector based on its live ranges. 45531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t i = 0; i < number_of_registers + number_of_spill_slots; ++i) { 45631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_values.Add(new (allocator) ArenaBitVector(allocator, 0, true)); 457a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 458a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 45931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t i = 0, e = intervals.Size(); i < e; ++i) { 46031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (AllRangesIterator it(intervals.Get(i)); !it.Done(); it.Advance()) { 46131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* current = it.CurrentInterval(); 46286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* defined_by = current->GetParent()->GetDefinedBy(); 46386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->GetParent()->HasSpillSlot() 46486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Parameters have their own stack slot. 46586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && !(defined_by != nullptr && defined_by->IsParameterValue())) { 4663946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray BitVector* liveness_of_spill_slot = liveness_of_values.Get(number_of_registers 4673946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray + current->GetParent()->GetSpillSlot() / kVRegSize 4683946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray - number_of_out_slots); 46931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 47031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (liveness_of_spill_slot->IsBitSet(j)) { 47131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (log_fatal_on_failure) { 47231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray std::ostringstream message; 47331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray message << "Spill slot conflict at " << j; 47431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LOG(FATAL) << message.str(); 47531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 47631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray return false; 47731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 47831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 47931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_spill_slot->SetBit(j); 48031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 48131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 482a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 48331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 48431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current->HasRegister()) { 48531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray BitVector* liveness_of_register = liveness_of_values.Get(current->GetRegister()); 48631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 48731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (liveness_of_register->IsBitSet(j)) { 488a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (log_fatal_on_failure) { 489a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray std::ostringstream message; 4903946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray message << "Register conflict at " << j << " "; 4913946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (defined_by != nullptr) { 4923946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray message << "(" << defined_by->DebugName() << ")"; 4933946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 4943946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray message << "for "; 495a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (processing_core_registers) { 496a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen.DumpCoreRegister(message, current->GetRegister()); 497a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 498a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen.DumpFloatingPointRegister(message, current->GetRegister()); 499a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 500a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LOG(FATAL) << message.str(); 501a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 502a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 503a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 504a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 50531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_register->SetBit(j); 506a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 507a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 50831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 50931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 510a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 511a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 512a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 513a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 51486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::DumpInterval(std::ostream& stream, LiveInterval* interval) const { 515a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray interval->Dump(stream); 516a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << ": "; 517a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->HasRegister()) { 518102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (interval->IsFloatingPoint()) { 51986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray codegen_->DumpFloatingPointRegister(stream, interval->GetRegister()); 520102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 521102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray codegen_->DumpCoreRegister(stream, interval->GetRegister()); 522a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 523a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 524a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << "spilled"; 525a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 526a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << std::endl; 527a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 528a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 529296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yangvoid RegisterAllocator::DumpAllIntervals(std::ostream& stream) const { 530296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang stream << "inactive: " << std::endl; 531296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0; i < inactive_.Size(); i ++) { 532296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DumpInterval(stream, inactive_.Get(i)); 533296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 534296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang stream << "active: " << std::endl; 535296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0; i < active_.Size(); i ++) { 536296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DumpInterval(stream, active_.Get(i)); 537296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 538296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang stream << "unhandled: " << std::endl; 539296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang auto unhandled = (unhandled_ != nullptr) ? 540296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang unhandled_ : &unhandled_core_intervals_; 541296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0; i < unhandled->Size(); i ++) { 542296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DumpInterval(stream, unhandled->Get(i)); 543296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 544296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang stream << "handled: " << std::endl; 545296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0; i < handled_.Size(); i ++) { 546296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DumpInterval(stream, handled_.Get(i)); 547296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 548296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang} 549296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang 550a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// By the book implementation of a linear scan register allocator. 551a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffrayvoid RegisterAllocator::LinearScan() { 5523946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray while (!unhandled_->IsEmpty()) { 553a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (1) Remove interval with the lowest start position from unhandled. 5543946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* current = unhandled_->Pop(); 5553946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray DCHECK(!current->IsFixed() && !current->HasSpillSlot()); 556c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray DCHECK(unhandled_->IsEmpty() || unhandled_->Peek()->GetStart() >= current->GetStart()); 557840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(!current->IsLowInterval() || unhandled_->Peek()->IsHighInterval()); 55887d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray 559a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t position = current->GetStart(); 560a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 561296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Remember the inactive_ size here since the ones moved to inactive_ from 562296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // active_ below shouldn't need to be re-checked. 563296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang size_t inactive_intervals_to_handle = inactive_.Size(); 564296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang 565a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (2) Remove currently active intervals that are dead at this position. 566a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Move active intervals that have a lifetime hole at this position 567a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // to inactive. 568a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < active_.Size(); ++i) { 569a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* interval = active_.Get(i); 570a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->IsDeadAt(position)) { 571a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Delete(interval); 572a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 573a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_.Add(interval); 574a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else if (!interval->Covers(position)) { 575a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Delete(interval); 576a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 577a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.Add(interval); 578a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 579a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 580a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 581a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (3) Remove currently inactive intervals that are dead at this position. 582a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Move inactive intervals that cover this position to active. 583296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0; i < inactive_intervals_to_handle; ++i) { 584a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* interval = inactive_.Get(i); 585296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK(interval->GetStart() < position || interval->IsFixed()); 586a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->IsDeadAt(position)) { 587a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.Delete(interval); 588a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 589296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang --inactive_intervals_to_handle; 590a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_.Add(interval); 591a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else if (interval->Covers(position)) { 592a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.Delete(interval); 593a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 594296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang --inactive_intervals_to_handle; 595a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Add(interval); 596a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 597a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 598a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 599acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray if (current->IsSlowPathSafepoint()) { 600acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray // Synthesized interval to record the maximum number of live registers 601acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray // at safepoints. No need to allocate a register for it. 602f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell if (processing_core_registers_) { 603f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell maximum_number_of_live_core_registers_ = 604f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell std::max(maximum_number_of_live_core_registers_, active_.Size()); 605f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell } else { 606f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell maximum_number_of_live_fp_registers_ = 607f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell std::max(maximum_number_of_live_fp_registers_, active_.Size()); 608f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell } 609acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray DCHECK(unhandled_->IsEmpty() || unhandled_->Peek()->GetStart() > current->GetStart()); 610acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray continue; 611acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray } 612acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray 613840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (current->IsHighInterval() && !current->GetLowInterval()->HasRegister()) { 614840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(!current->HasRegister()); 615840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // Allocating the low part was unsucessful. The splitted interval for the high part 616840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // will be handled next (it is in the `unhandled_` list). 617840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray continue; 618840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 619840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 620a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (4) Try to find an available register. 621a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool success = TryAllocateFreeReg(current); 622a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 623a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (5) If no register could be found, we need to spill. 624a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (!success) { 625a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray success = AllocateBlockedReg(current); 626a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 627a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 628a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (6) If the interval had a register allocated, add it to the list of active 629a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // intervals. 630a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (success) { 631988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray codegen_->AddAllocatedRegister(processing_core_registers_ 632988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray ? Location::RegisterLocation(current->GetRegister()) 633988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray : Location::FpuRegisterLocation(current->GetRegister())); 634a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Add(current); 635840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (current->HasHighInterval() && !current->GetHighInterval()->HasRegister()) { 636840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray current->GetHighInterval()->SetRegister(GetHighForLowRegister(current->GetRegister())); 637840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 638a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 639a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 640a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 641a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 642a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// Find a free register. If multiple are found, pick the register that 643a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// is free the longest. 644a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::TryAllocateFreeReg(LiveInterval* current) { 645a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t* free_until = registers_array_; 646a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 647a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // First set all registers to be free. 648a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 649a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray free_until[i] = kMaxLifetimePosition; 650a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 651a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 652296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // For each active interval, set its register to not free. 653296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0, e = active_.Size(); i < e; ++i) { 654296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang LiveInterval* interval = active_.Get(i); 655296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK(interval->HasRegister()); 656296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang free_until[interval->GetRegister()] = 0; 657296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 658296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang 659a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each inactive interval, set its register to be free until 660a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // the next intersection with `current`. 661a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { 662a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* inactive = inactive_.Get(i); 663296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Temp/Slow-path-safepoint interval has no holes. 664296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK(!inactive->IsTemp() && !inactive->IsSlowPathSafepoint()); 665296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang if (!current->IsSplit() && !inactive->IsFixed()) { 666296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Neither current nor inactive are fixed. 667296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Thanks to SSA, a non-split interval starting in a hole of an 668296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // inactive interval should never intersect with that inactive interval. 669296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Only if it's not fixed though, because fixed intervals don't come from SSA. 670296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime); 671296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang continue; 672296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 673296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang 674a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(inactive->HasRegister()); 675296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang if (free_until[inactive->GetRegister()] == 0) { 676296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Already used by some active interval. No need to intersect. 677296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang continue; 678296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 679a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t next_intersection = inactive->FirstIntersectionWith(current); 680a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (next_intersection != kNoLifetime) { 681aac0f39a3501a7f7dd04b2342c2a16961969f139Nicolas Geoffray free_until[inactive->GetRegister()] = 682aac0f39a3501a7f7dd04b2342c2a16961969f139Nicolas Geoffray std::min(free_until[inactive->GetRegister()], next_intersection); 683a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 684a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 685a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 6866c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray int reg = kNoRegister; 6873946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current->HasRegister()) { 6883946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Some instructions have a fixed register output. 6893946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray reg = current->GetRegister(); 690840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (free_until[reg] == 0) { 691840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(current->IsHighInterval()); 692840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // AllocateBlockedReg will spill the holder of the register. 693840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return false; 694840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 6953946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 696840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(!current->IsHighInterval()); 69701ef345767ea609417fc511e42007705c9667546Nicolas Geoffray int hint = current->FindFirstRegisterHint(free_until); 69801ef345767ea609417fc511e42007705c9667546Nicolas Geoffray if (hint != kNoRegister) { 69901ef345767ea609417fc511e42007705c9667546Nicolas Geoffray DCHECK(!IsBlocked(hint)); 70001ef345767ea609417fc511e42007705c9667546Nicolas Geoffray reg = hint; 701840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (current->IsLowInterval()) { 7026c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray reg = FindAvailableRegisterPair(free_until, current->GetStart()); 70301ef345767ea609417fc511e42007705c9667546Nicolas Geoffray } else { 704840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray reg = FindAvailableRegister(free_until); 705a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 706a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 707a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 7086c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK_NE(reg, kNoRegister); 709a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // If we could not find a register, we need to spill. 710840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (free_until[reg] == 0) { 711840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return false; 712840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 713840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 714840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (current->IsLowInterval() && free_until[GetHighForLowRegister(reg)] == 0) { 715a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 716a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 717a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 718a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray current->SetRegister(reg); 719a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (!current->IsDeadAt(free_until[reg])) { 720a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // If the register is only available for a subset of live ranges 721a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // covered by `current`, split `current` at the position where 722a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // the register is not available anymore. 723a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* split = Split(current, free_until[reg]); 724a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(split != nullptr); 7253946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 726a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 727a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 728a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 729a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 730a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::IsBlocked(int reg) const { 731102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return processing_core_registers_ 732102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ? blocked_core_registers_[reg] 733102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray : blocked_fp_registers_[reg]; 734a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 735a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 7366c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffrayint RegisterAllocator::FindAvailableRegisterPair(size_t* next_use, size_t starting_at) const { 7376c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray int reg = kNoRegister; 738840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // Pick the register pair that is used the last. 739840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 740840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (IsBlocked(i)) continue; 741840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (!IsLowRegister(i)) continue; 742840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray int high_register = GetHighForLowRegister(i); 743840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (IsBlocked(high_register)) continue; 744840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray int existing_high_register = GetHighForLowRegister(reg); 7456c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if ((reg == kNoRegister) || (next_use[i] >= next_use[reg] 746840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray && next_use[high_register] >= next_use[existing_high_register])) { 747840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray reg = i; 748840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (next_use[i] == kMaxLifetimePosition 749840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray && next_use[high_register] == kMaxLifetimePosition) { 750840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray break; 751840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 7526c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } else if (next_use[reg] <= starting_at || next_use[existing_high_register] <= starting_at) { 7536c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // If one of the current register is known to be unavailable, just unconditionally 7546c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // try a new one. 7556c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray reg = i; 756840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 757840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 758840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return reg; 759840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray} 760840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 761840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffrayint RegisterAllocator::FindAvailableRegister(size_t* next_use) const { 7626c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray int reg = kNoRegister; 763840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // Pick the register that is used the last. 764840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 765840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (IsBlocked(i)) continue; 7666c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (reg == kNoRegister || next_use[i] > next_use[reg]) { 767840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray reg = i; 768840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (next_use[i] == kMaxLifetimePosition) break; 769840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 770840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 771840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return reg; 772840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray} 773840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 7746c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffraybool RegisterAllocator::TrySplitNonPairIntervalAt(size_t position, 7756c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray size_t first_register_use, 7766c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray size_t* next_use) { 7776c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray for (size_t i = 0, e = active_.Size(); i < e; ++i) { 7786c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray LiveInterval* active = active_.Get(i); 7796c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(active->HasRegister()); 7806c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // Split the first interval found. 7816c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (first_register_use <= next_use[active->GetRegister()] 7826c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray && !active->IsLowInterval() 7836c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray && !active->IsHighInterval()) { 7846c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray LiveInterval* split = Split(active, position); 7856c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray active_.DeleteAt(i); 7866c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (split != active) { 7876c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray handled_.Add(active); 7886c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 7896c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray AddSorted(unhandled_, split); 7906c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray return true; 7916c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 7926c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 7936c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray return false; 7946c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray} 7956c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray 796a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// Find the register that is used the last, and spill the interval 797a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// that holds it. If the first use of `current` is after that register 798a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// we spill `current` instead. 799a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) { 800a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t first_register_use = current->FirstRegisterUse(); 801412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray if (first_register_use == kNoLifetime) { 80231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray AllocateSpillSlotFor(current); 803a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 804a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 805a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 806a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // First set all registers as not being used. 807a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t* next_use = registers_array_; 808a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 809a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray next_use[i] = kMaxLifetimePosition; 810a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 811a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 812a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each active interval, find the next use of its register after the 813a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // start of current. 814a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = active_.Size(); i < e; ++i) { 815a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* active = active_.Get(i); 816a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(active->HasRegister()); 81786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (active->IsFixed()) { 81886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[active->GetRegister()] = current->GetStart(); 81986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 82086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t use = active->FirstRegisterUseAfter(current->GetStart()); 82186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (use != kNoLifetime) { 82286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[active->GetRegister()] = use; 82386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 824a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 825a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 826a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 827a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each inactive interval, find the next use of its register after the 828a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // start of current. 829a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { 830a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* inactive = inactive_.Get(i); 831296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Temp/Slow-path-safepoint interval has no holes. 832296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK(!inactive->IsTemp() && !inactive->IsSlowPathSafepoint()); 833296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang if (!current->IsSplit() && !inactive->IsFixed()) { 834296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Neither current nor inactive are fixed. 835296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Thanks to SSA, a non-split interval starting in a hole of an 836296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // inactive interval should never intersect with that inactive interval. 837296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Only if it's not fixed though, because fixed intervals don't come from SSA. 838296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime); 839296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang continue; 840296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 841a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(inactive->HasRegister()); 84286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t next_intersection = inactive->FirstIntersectionWith(current); 84386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (next_intersection != kNoLifetime) { 84486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (inactive->IsFixed()) { 84586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[inactive->GetRegister()] = 84686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray std::min(next_intersection, next_use[inactive->GetRegister()]); 84786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 84886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t use = inactive->FirstRegisterUseAfter(current->GetStart()); 84986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (use != kNoLifetime) { 85086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[inactive->GetRegister()] = std::min(use, next_use[inactive->GetRegister()]); 85186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 85286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 853a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 854a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 855a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 8566c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray int reg = kNoRegister; 8576c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray bool should_spill = false; 858840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (current->HasRegister()) { 859840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(current->IsHighInterval()); 860840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray reg = current->GetRegister(); 8616c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // When allocating the low part, we made sure the high register was available. 8626c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK_LT(first_register_use, next_use[reg]); 863840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (current->IsLowInterval()) { 8646c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray reg = FindAvailableRegisterPair(next_use, current->GetStart()); 8656c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // We should spill if both registers are not available. 8666c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray should_spill = (first_register_use >= next_use[reg]) 8676c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray || (first_register_use >= next_use[GetHighForLowRegister(reg)]); 868840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else { 869840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(!current->IsHighInterval()); 870840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray reg = FindAvailableRegister(next_use); 8716c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray should_spill = (first_register_use >= next_use[reg]); 872a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 873a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 8746c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK_NE(reg, kNoRegister); 8756c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (should_spill) { 876840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(!current->IsHighInterval()); 8776c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray bool is_allocation_at_use_site = (current->GetStart() == (first_register_use - 1)); 8786c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (current->IsLowInterval() 8796c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray && is_allocation_at_use_site 8806c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray && TrySplitNonPairIntervalAt(current->GetStart(), first_register_use, next_use)) { 8816c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // If we're allocating a register for `current` because the instruction at 8826c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // that position requires it, but we think we should spill, then there are 8836c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // non-pair intervals blocking the allocation. We split the first 8846c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // interval found, and put ourselves first in the `unhandled_` list. 8856c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray LiveInterval* existing = unhandled_->Peek(); 8866c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(existing->IsHighInterval()); 8876c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK_EQ(existing->GetLowInterval(), current); 8886c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray unhandled_->Add(current); 8896c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } else { 8906c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // If the first use of that instruction is after the last use of the found 8916c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // register, we split this interval just before its first register use. 8926c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray AllocateSpillSlotFor(current); 8936c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray LiveInterval* split = Split(current, first_register_use - 1); 8946c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK_NE(current, split) << "There is not enough registers available for " 8956c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray << split->GetParent()->GetDefinedBy()->DebugName() << " " 8966c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray << split->GetParent()->GetDefinedBy()->GetId() 8976c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray << " at " << first_register_use - 1; 8986c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray AddSorted(unhandled_, split); 8996c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 900a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 901a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 902a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Use this register and spill the active and inactives interval that 903a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // have that register. 904a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray current->SetRegister(reg); 905a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 906a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = active_.Size(); i < e; ++i) { 907a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* active = active_.Get(i); 908a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (active->GetRegister() == reg) { 90986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(!active->IsFixed()); 910a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* split = Split(active, current->GetStart()); 911a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.DeleteAt(i); 912dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray if (split != active) { 913dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray handled_.Add(active); 914dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray } 9153946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 9166c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray 9176c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (active->IsLowInterval() || active->IsHighInterval()) { 9186c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray LiveInterval* other_half = active->IsLowInterval() 9196c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray ? active->GetHighInterval() 9206c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray : active->GetLowInterval(); 9216c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // We also need to remove the other half from the list of actives. 9226c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray bool found = false; 9236c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray for (size_t j = 0; j < active_.Size(); ++j) { 9246c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (active_.Get(j) == other_half) { 9256c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray found = true; 9266c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray active_.DeleteAt(j); 9276c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray handled_.Add(other_half); 9286c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray break; 9296c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 9306c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 9316c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(found); 9326c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 933a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray break; 934a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 935a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 936a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 937296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { 938a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* inactive = inactive_.Get(i); 939a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (inactive->GetRegister() == reg) { 940296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang if (!current->IsSplit() && !inactive->IsFixed()) { 941296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Neither current nor inactive are fixed. 942296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Thanks to SSA, a non-split interval starting in a hole of an 943296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // inactive interval should never intersect with that inactive interval. 944296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Only if it's not fixed though, because fixed intervals don't come from SSA. 945296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime); 946296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang continue; 947296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 94886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t next_intersection = inactive->FirstIntersectionWith(current); 94986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (next_intersection != kNoLifetime) { 95086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (inactive->IsFixed()) { 95186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* split = Split(current, next_intersection); 952dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray DCHECK_NE(split, current); 9533946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 95486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 955dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray // Split at the start of `current`, which will lead to splitting 956dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray // at the end of the lifetime hole of `inactive`. 957dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray LiveInterval* split = Split(inactive, current->GetStart()); 958dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray // If it's inactive, it must start before the current interval. 959dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray DCHECK_NE(split, inactive); 96086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray inactive_.DeleteAt(i); 961296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang --i; 962296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang --e; 96386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray handled_.Add(inactive); 9643946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 9656c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray 9666c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (inactive->IsLowInterval() || inactive->IsHighInterval()) { 9676c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray LiveInterval* other_half = inactive->IsLowInterval() 9686c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray ? inactive->GetHighInterval() 9696c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray : inactive->GetLowInterval(); 9706c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray 9716c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // We also need to remove the other half from the list of inactives. 9726c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray bool found = false; 9736c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray for (size_t j = 0; j < inactive_.Size(); ++j) { 9746c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (inactive_.Get(j) == other_half) { 9756c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray found = true; 9766c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray inactive_.DeleteAt(j); 9776c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray --e; 9786c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray handled_.Add(other_half); 9796c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray break; 9806c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 9816c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 9826c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(found); 9836c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 98486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 98586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 986a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 987a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 988a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 989a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 990a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 991a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 992a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 9933946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffrayvoid RegisterAllocator::AddSorted(GrowableArray<LiveInterval*>* array, LiveInterval* interval) { 994c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray DCHECK(!interval->IsFixed() && !interval->HasSpillSlot()); 99586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t insert_at = 0; 9963946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = array->Size(); i > 0; --i) { 9973946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* current = array->Get(i - 1); 9986c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // High intervals must be processed right after their low equivalent. 9996c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (current->StartsAfter(interval) && !current->IsHighInterval()) { 100086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray insert_at = i; 1001a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray break; 1002acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray } else if ((current->GetStart() == interval->GetStart()) && current->IsSlowPathSafepoint()) { 1003acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray // Ensure the slow path interval is the last to be processed at its location: we want the 1004acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray // interval to know all live registers at this location. 1005acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray DCHECK(i == 1 || array->Get(i - 2)->StartsAfter(current)); 1006acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray insert_at = i; 1007acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray break; 1008a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1009a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1010840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 10113946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray array->InsertAt(insert_at, interval); 1012840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // Insert the high interval before the low, to ensure the low is processed before. 1013840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (interval->HasHighInterval()) { 1014840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray array->InsertAt(insert_at, interval->GetHighInterval()); 1015840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (interval->HasLowInterval()) { 1016840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray array->InsertAt(insert_at + 1, interval->GetLowInterval()); 1017840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 1018a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 1019a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1020a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas GeoffrayLiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) { 1021840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK_GE(position, interval->GetStart()); 1022a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(!interval->IsDeadAt(position)); 1023a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (position == interval->GetStart()) { 1024a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Spill slot will be allocated when handling `interval` again. 1025a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray interval->ClearRegister(); 1026840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (interval->HasHighInterval()) { 1027840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray interval->GetHighInterval()->ClearRegister(); 1028840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (interval->HasLowInterval()) { 1029840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray interval->GetLowInterval()->ClearRegister(); 1030840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 1031a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return interval; 1032a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 1033a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* new_interval = interval->SplitAt(position); 1034840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (interval->HasHighInterval()) { 1035840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray LiveInterval* high = interval->GetHighInterval()->SplitAt(position); 1036840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray new_interval->SetHighInterval(high); 1037840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray high->SetLowInterval(new_interval); 1038840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (interval->HasLowInterval()) { 1039840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray LiveInterval* low = interval->GetLowInterval()->SplitAt(position); 1040840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray new_interval->SetLowInterval(low); 1041840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray low->SetHighInterval(new_interval); 1042840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 1043a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return new_interval; 1044a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1045a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 1046a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 104731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffrayvoid RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) { 1048840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (interval->IsHighInterval()) { 1049840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // The low interval will contain the spill slot. 1050840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return; 1051840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 1052840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 105331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* parent = interval->GetParent(); 105431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 105531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // An instruction gets a spill slot for its entire lifetime. If the parent 105631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // of this interval already has a spill slot, there is nothing to do. 105731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (parent->HasSpillSlot()) { 105831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray return; 105931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 106031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 106186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* defined_by = parent->GetDefinedBy(); 106286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (defined_by->IsParameterValue()) { 106386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Parameters have their own stack slot. 106486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray parent->SetSpillSlot(codegen_->GetStackSlotOfParameter(defined_by->AsParameterValue())); 106586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 106686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 106786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 106896f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray if (defined_by->IsConstant()) { 106996f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray // Constants don't need a spill slot. 107096f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray return; 107196f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray } 107296f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray 107331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* last_sibling = interval; 107431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray while (last_sibling->GetNextSibling() != nullptr) { 107531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray last_sibling = last_sibling->GetNextSibling(); 107631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 107731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray size_t end = last_sibling->GetEnd(); 107831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 1079412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // Find an available spill slot. 1080412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray size_t slot = 0; 1081412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray for (size_t e = spill_slots_.Size(); slot < e; ++slot) { 1082412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // We check if it is less rather than less or equal because the parallel move 1083412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // resolver does not work when a single spill slot needs to be exchanged with 1084412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // a double spill slot. The strict comparison avoids needing to exchange these 1085412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // locations at the same lifetime position. 1086412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray if (spill_slots_.Get(slot) < parent->GetStart() 1087412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray && (slot == (e - 1) || spill_slots_.Get(slot + 1) < parent->GetStart())) { 1088412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray break; 1089412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } 1090412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } 1091412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray 109201ef345767ea609417fc511e42007705c9667546Nicolas Geoffray if (parent->NeedsTwoSpillSlots()) { 10933c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray if (slot == spill_slots_.Size()) { 10943c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray // We need a new spill slot. 10953c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray spill_slots_.Add(end); 10963c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray spill_slots_.Add(end); 10973c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray } else if (slot == spill_slots_.Size() - 1) { 10983c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray spill_slots_.Put(slot, end); 10993c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray spill_slots_.Add(end); 11003c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray } else { 11013c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray spill_slots_.Put(slot, end); 11023c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray spill_slots_.Put(slot + 1, end); 110331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 110431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 11053c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray if (slot == spill_slots_.Size()) { 11063c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray // We need a new spill slot. 11073c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray spill_slots_.Add(end); 11083c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray } else { 11093c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray spill_slots_.Put(slot, end); 11103c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray } 111131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 111231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 11133946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray parent->SetSpillSlot((slot + reserved_out_slots_) * kVRegSize); 111486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 111586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 11162a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffraystatic bool IsValidDestination(Location destination) { 1117102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return destination.IsRegister() 11186c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray || destination.IsRegisterPair() 1119102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray || destination.IsFpuRegister() 1120840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray || destination.IsFpuRegisterPair() 1121102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray || destination.IsStackSlot() 1122102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray || destination.IsDoubleStackSlot(); 11232a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray} 11242a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray 1125740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffrayvoid RegisterAllocator::AddInputMoveFor(HInstruction* user, 112686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 112786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 112886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 112986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1130476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain DCHECK(!user->IsPhi()); 113186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1132740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray HInstruction* previous = user->GetPrevious(); 113386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move = nullptr; 113486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (previous == nullptr 1135476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain || !previous->IsParallelMove() 11368e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray || previous->GetLifetimePosition() < user->GetLifetimePosition()) { 113786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 11388e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray move->SetLifetimePosition(user->GetLifetimePosition()); 1139740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray user->GetBlock()->InsertInstructionBefore(move, user); 114086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 114186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = previous->AsParallelMove(); 114286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 11438e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray DCHECK_EQ(move->GetLifetimePosition(), user->GetLifetimePosition()); 114442d1f5f006c8bdbcbf855c53036cd50f9c69753eNicolas Geoffray move->AddMove(source, destination, nullptr); 114586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 114686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 114746fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffraystatic bool IsInstructionStart(size_t position) { 114846fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray return (position & 1) == 0; 114946fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray} 115046fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray 115146fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffraystatic bool IsInstructionEnd(size_t position) { 115246fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray return (position & 1) == 1; 115346fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray} 115446fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray 115586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertParallelMoveAt(size_t position, 1156740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray HInstruction* instruction, 115786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 115886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 11596c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(IsValidDestination(destination)) << destination; 116086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 116186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 116286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* at = liveness_.GetInstructionFromPosition(position / 2); 116386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move; 116446fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray if (at == nullptr) { 116546fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray if (IsInstructionStart(position)) { 116646fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray // Block boundary, don't do anything the connection of split siblings will handle it. 116746fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray return; 116846fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray } else { 116946fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray // Move must happen before the first instruction of the block. 117046fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray at = liveness_.GetInstructionFromPosition((position + 1) / 2); 11715976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // Note that parallel moves may have already been inserted, so we explicitly 11725976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // ask for the first instruction of the block: `GetInstructionFromPosition` does 11735976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // not contain the moves. 11745976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray at = at->GetBlock()->GetFirstInstruction(); 11755976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray if (at->GetLifetimePosition() != position) { 11765976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray DCHECK_GT(at->GetLifetimePosition(), position); 117746fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 117846fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray move->SetLifetimePosition(position); 117946fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray at->GetBlock()->InsertInstructionBefore(move, at); 11805976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray } else { 11815976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray DCHECK(at->IsParallelMove()); 11825976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray move = at->AsParallelMove(); 118346fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray } 118446fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray } 118546fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray } else if (IsInstructionEnd(position)) { 118686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Move must happen after the instruction. 118786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(!at->IsControlFlow()); 118886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = at->GetNext()->AsParallelMove(); 1189e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting siblings in a same block. We need to 1190e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // differentiate it with moves for connecting blocks, and input moves. 11918e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray if (move == nullptr || move->GetLifetimePosition() > position) { 119286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 119386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->SetLifetimePosition(position); 119486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray at->GetBlock()->InsertInstructionBefore(move, at->GetNext()); 119586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 119686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 119786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Move must happen before the instruction. 119886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* previous = at->GetPrevious(); 1199740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray if (previous == nullptr 1200740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray || !previous->IsParallelMove() 1201740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray || previous->GetLifetimePosition() != position) { 1202740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray // If the previous is a parallel move, then its position must be lower 1203740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray // than the given `position`: it was added just after the non-parallel 1204740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray // move instruction that precedes `instruction`. 1205740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray DCHECK(previous == nullptr 1206740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray || !previous->IsParallelMove() 1207740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray || previous->GetLifetimePosition() < position); 120886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 120986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->SetLifetimePosition(position); 121086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray at->GetBlock()->InsertInstructionBefore(move, at); 121186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 121286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = previous->AsParallelMove(); 121386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 121486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 121501ef345767ea609417fc511e42007705c9667546Nicolas Geoffray DCHECK_EQ(move->GetLifetimePosition(), position); 121642d1f5f006c8bdbcbf855c53036cd50f9c69753eNicolas Geoffray move->AddMove(source, destination, instruction); 121786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 121886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 121986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertParallelMoveAtExitOf(HBasicBlock* block, 1220740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray HInstruction* instruction, 122186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 122286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 12236c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(IsValidDestination(destination)) << destination; 122486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 122586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 122686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK_EQ(block->GetSuccessors().Size(), 1u); 122786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* last = block->GetLastInstruction(); 1228360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray // We insert moves at exit for phi predecessors and connecting blocks. 1229360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray // A block ending with an if cannot branch to a block with phis because 1230360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray // we do not allow critical edges. It can also not connect 1231360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray // a split interval between two blocks: the move has to happen in the successor. 1232360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray DCHECK(!last->IsIf()); 123386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* previous = last->GetPrevious(); 123486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move; 1235e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting blocks. We need to differentiate 1236e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // it with moves for connecting siblings in a same block, and output moves. 12375976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray size_t position = last->GetLifetimePosition(); 1238740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray if (previous == nullptr || !previous->IsParallelMove() 12395976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray || previous->AsParallelMove()->GetLifetimePosition() != position) { 124086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 12415976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray move->SetLifetimePosition(position); 124286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray block->InsertInstructionBefore(move, last); 124386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 124486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = previous->AsParallelMove(); 124586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 124642d1f5f006c8bdbcbf855c53036cd50f9c69753eNicolas Geoffray move->AddMove(source, destination, instruction); 124786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 124886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 124986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertParallelMoveAtEntryOf(HBasicBlock* block, 1250740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray HInstruction* instruction, 125186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 125286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 12536c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(IsValidDestination(destination)) << destination; 125486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 125586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 125686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* first = block->GetFirstInstruction(); 125786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move = first->AsParallelMove(); 1258e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting blocks. We need to differentiate 1259e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // it with moves for connecting siblings in a same block, and input moves. 1260e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray if (move == nullptr || move->GetLifetimePosition() != block->GetLifetimeStart()) { 126186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 126286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->SetLifetimePosition(block->GetLifetimeStart()); 126386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray block->InsertInstructionBefore(move, first); 126486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 126542d1f5f006c8bdbcbf855c53036cd50f9c69753eNicolas Geoffray move->AddMove(source, destination, instruction); 126686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 126786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 126886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertMoveAfter(HInstruction* instruction, 126986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 127086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 12716c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(IsValidDestination(destination)) << destination; 127286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 127386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1274476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain if (instruction->IsPhi()) { 1275740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAtEntryOf(instruction->GetBlock(), instruction, source, destination); 127686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 127786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 127886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1279e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray size_t position = instruction->GetLifetimePosition() + 1; 128086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move = instruction->GetNext()->AsParallelMove(); 1281e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for moving the output of an instruction. We need 1282e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // to differentiate with input moves, moves for connecting siblings in a 1283e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // and moves for connecting blocks. 1284e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray if (move == nullptr || move->GetLifetimePosition() != position) { 128586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 1286e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray move->SetLifetimePosition(position); 128786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray instruction->GetBlock()->InsertInstructionBefore(move, instruction->GetNext()); 128886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 128942d1f5f006c8bdbcbf855c53036cd50f9c69753eNicolas Geoffray move->AddMove(source, destination, instruction); 129086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 129186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 129286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::ConnectSiblings(LiveInterval* interval) { 129386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = interval; 129486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->HasSpillSlot() && current->HasRegister()) { 129586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // We spill eagerly, so move must be at definition. 129686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InsertMoveAfter(interval->GetDefinedBy(), 1297840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray interval->ToLocation(), 129801ef345767ea609417fc511e42007705c9667546Nicolas Geoffray interval->NeedsTwoSpillSlots() 1299412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray ? Location::DoubleStackSlot(interval->GetParent()->GetSpillSlot()) 1300412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray : Location::StackSlot(interval->GetParent()->GetSpillSlot())); 130186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 130286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray UsePosition* use = current->GetFirstUse(); 130386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 130486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Walk over all siblings, updating locations of use positions, and 130586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // connecting them when they are adjacent. 130686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray do { 130701ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location source = current->ToLocation(); 130886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 130986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Walk over all uses covered by this interval, and update the location 131086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // information. 131186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray while (use != nullptr && use->GetPosition() <= current->GetEnd()) { 13123946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LocationSummary* locations = use->GetUser()->GetLocations(); 13133946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (use->GetIsEnvironment()) { 13143946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray locations->SetEnvironmentAt(use->GetInputIndex(), source); 13153946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 131686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location expected_location = locations->InAt(use->GetInputIndex()); 131771fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe // The expected (actual) location may be invalid in case the input is unused. Currently 131871fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe // this only happens for intrinsics. 131971fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe if (expected_location.IsValid()) { 132071fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe if (expected_location.IsUnallocated()) { 132171fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe locations->SetInAt(use->GetInputIndex(), source); 132271fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe } else if (!expected_location.IsConstant()) { 132371fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe AddInputMoveFor(use->GetUser(), source, expected_location); 132471fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe } 132571fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe } else { 132671fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe DCHECK(use->GetUser()->IsInvoke()); 132771fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe DCHECK(use->GetUser()->AsInvoke()->GetIntrinsic() != Intrinsics::kNone); 132886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 132986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 133086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray use = use->GetNext(); 133186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 133286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 133386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // If the next interval starts just after this one, and has a register, 133486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // insert a move. 133586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* next_sibling = current->GetNextSibling(); 133686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (next_sibling != nullptr 133786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && next_sibling->HasRegister() 133886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && current->GetEnd() == next_sibling->GetStart()) { 133901ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location destination = next_sibling->ToLocation(); 1340740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAt(current->GetEnd(), interval->GetDefinedBy(), source, destination); 134186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 13423946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 13433946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // At each safepoint, we record stack and register information. 13443946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0, e = safepoints_.Size(); i < e; ++i) { 13453946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray HInstruction* safepoint = safepoints_.Get(i); 13463946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t position = safepoint->GetLifetimePosition(); 13473946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LocationSummary* locations = safepoint->GetLocations(); 1348b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray if (!current->Covers(position)) { 1349b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray continue; 1350b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray } 1351b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray if (interval->GetStart() == position) { 1352b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // The safepoint is for this instruction, so the location of the instruction 1353b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // does not need to be saved. 1354b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray continue; 1355b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray } 13563946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 13573bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray if ((current->GetType() == Primitive::kPrimNot) && current->GetParent()->HasSpillSlot()) { 13583946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray locations->SetStackBit(current->GetParent()->GetSpillSlot() / kVRegSize); 13593946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 13603946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 13613946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray switch (source.GetKind()) { 13623946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kRegister: { 13633bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray locations->AddLiveRegister(source); 1364988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray if (kIsDebugBuild && locations->OnlyCallsOnSlowPath()) { 1365988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray DCHECK_LE(locations->GetNumberOfLiveRegisters(), 1366988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray maximum_number_of_live_core_registers_ + 1367988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray maximum_number_of_live_fp_registers_); 1368988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray } 13693946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current->GetType() == Primitive::kPrimNot) { 137056b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray locations->SetRegisterBit(source.reg()); 13713946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 13723946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray break; 13733946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 1374102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray case Location::kFpuRegister: { 1375102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray locations->AddLiveRegister(source); 1376102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray break; 1377102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 13786c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray 13796c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray case Location::kRegisterPair: 1380840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray case Location::kFpuRegisterPair: { 1381840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray locations->AddLiveRegister(source.ToLow()); 1382840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray locations->AddLiveRegister(source.ToHigh()); 1383840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray break; 1384840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 13853946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kStackSlot: // Fall-through 13863946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kDoubleStackSlot: // Fall-through 13873946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kConstant: { 13883946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Nothing to do. 13893946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray break; 13903946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 13913946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray default: { 13923946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LOG(FATAL) << "Unexpected location for object"; 13933946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 13943946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 13953946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 139686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current = next_sibling; 139786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } while (current != nullptr); 139886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(use == nullptr); 139986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 140086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 140186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval, 140286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* from, 140386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* to) const { 140486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (interval->GetNextSibling() == nullptr) { 140586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Nothing to connect. The whole range was allocated to the same location. 140686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 140786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 140886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 140946fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray // Intervals end at the lifetime end of a block. The decrement by one 141046fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray // ensures the `Cover` call will return true. 141186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t from_position = from->GetLifetimeEnd() - 1; 141246fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray size_t to_position = to->GetLifetimeStart(); 141386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 141486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* destination = nullptr; 141586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* source = nullptr; 141686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 141786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = interval; 141886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 141986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Check the intervals that cover `from` and `to`. 142086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray while ((current != nullptr) && (source == nullptr || destination == nullptr)) { 142186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->Covers(from_position)) { 142286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(source == nullptr); 142386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray source = current; 142486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 142586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->Covers(to_position)) { 142686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(destination == nullptr); 142786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray destination = current; 142886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 142986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 143086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current = current->GetNextSibling(); 143186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 143286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 143386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (destination == source) { 143486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Interval was not split. 143586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 143686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 143786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 14388ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray DCHECK(destination != nullptr && source != nullptr); 14398ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray 144086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (!destination->HasRegister()) { 144186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Values are eagerly spilled. Spill slot already contains appropriate value. 144286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 144386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 144486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 144586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // If `from` has only one successor, we can put the moves at the exit of it. Otherwise 144686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // we need to put the moves at the entry of `to`. 144786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (from->GetSuccessors().Size() == 1) { 1448740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAtExitOf(from, 1449740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray interval->GetParent()->GetDefinedBy(), 145001ef345767ea609417fc511e42007705c9667546Nicolas Geoffray source->ToLocation(), 145101ef345767ea609417fc511e42007705c9667546Nicolas Geoffray destination->ToLocation()); 145286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 145386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK_EQ(to->GetPredecessors().Size(), 1u); 1454740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAtEntryOf(to, 1455740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray interval->GetParent()->GetDefinedBy(), 145601ef345767ea609417fc511e42007705c9667546Nicolas Geoffray source->ToLocation(), 145701ef345767ea609417fc511e42007705c9667546Nicolas Geoffray destination->ToLocation()); 145886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 145986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 146086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 146186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::Resolve() { 14623bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray codegen_->ComputeFrameSize( 1463f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell spill_slots_.Size(), maximum_number_of_live_core_registers_, 1464f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell maximum_number_of_live_fp_registers_, reserved_out_slots_); 146586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 146686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Adjust the Out Location of instructions. 146786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // TODO: Use pointers of Location inside LiveInterval to avoid doing another iteration. 146886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { 146986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 147086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = instruction->GetLiveInterval(); 147186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LocationSummary* locations = instruction->GetLocations(); 147286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location location = locations->Out(); 1473476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain if (instruction->IsParameterValue()) { 147486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Now that we know the frame size, adjust the parameter's location. 147586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (location.IsStackSlot()) { 147686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray location = Location::StackSlot(location.GetStackIndex() + codegen_->GetFrameSize()); 147786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(location.GetStackIndex()); 1478f43083d560565aea46c602adb86423daeefe589dNicolas Geoffray locations->UpdateOut(location); 147986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else if (location.IsDoubleStackSlot()) { 148086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray location = Location::DoubleStackSlot(location.GetStackIndex() + codegen_->GetFrameSize()); 148186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(location.GetStackIndex()); 1482f43083d560565aea46c602adb86423daeefe589dNicolas Geoffray locations->UpdateOut(location); 148386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else if (current->HasSpillSlot()) { 148486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(current->GetSpillSlot() + codegen_->GetFrameSize()); 148586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 148686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 148786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 148801ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location source = current->ToLocation(); 148986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 149086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (location.IsUnallocated()) { 149186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (location.GetPolicy() == Location::kSameAsFirstInput) { 1492d0d4852847432368b090c184d6639e573538dccfCalin Juravle if (locations->InAt(0).IsUnallocated()) { 1493d0d4852847432368b090c184d6639e573538dccfCalin Juravle locations->SetInAt(0, source); 1494d0d4852847432368b090c184d6639e573538dccfCalin Juravle } else { 1495d0d4852847432368b090c184d6639e573538dccfCalin Juravle DCHECK(locations->InAt(0).Equals(source)); 1496d0d4852847432368b090c184d6639e573538dccfCalin Juravle } 149786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 149886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray locations->SetOut(source); 149986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 150086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(source.Equals(location)); 150186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 150286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 150386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 150486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Connect siblings. 150586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { 150686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 150786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ConnectSiblings(instruction->GetLiveInterval()); 150886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 150986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 151086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Resolve non-linear control flow across branches. Order does not matter. 151186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (HLinearOrderIterator it(liveness_); !it.Done(); it.Advance()) { 151286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* block = it.Current(); 151386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray BitVector* live = liveness_.GetLiveInSet(*block); 151486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (uint32_t idx : live->Indexes()) { 151586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* current = liveness_.GetInstructionFromSsaIndex(idx); 151686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* interval = current->GetLiveInterval(); 151786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { 151886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ConnectSplitSiblings(interval, block->GetPredecessors().Get(i), block); 151986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 152086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 152186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 152286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 152386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Resolve phi inputs. Order does not matter. 152486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (HLinearOrderIterator it(liveness_); !it.Done(); it.Advance()) { 152586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* current = it.Current(); 1526277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe for (HInstructionIterator inst_it(current->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 1527277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe HInstruction* phi = inst_it.Current(); 152886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = current->GetPredecessors().Size(); i < e; ++i) { 152986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* predecessor = current->GetPredecessors().Get(i); 153086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK_EQ(predecessor->GetSuccessors().Size(), 1u); 153186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* input = phi->InputAt(i); 153201ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location source = input->GetLiveInterval()->GetLocationAt( 153301ef345767ea609417fc511e42007705c9667546Nicolas Geoffray predecessor->GetLifetimeEnd() - 1); 153401ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location destination = phi->GetLiveInterval()->ToLocation(); 1535740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAtExitOf(predecessor, nullptr, source, destination); 153686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 153786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 153886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 15393946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 15403946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Assign temp locations. 15413946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray HInstruction* current = nullptr; 15423946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t temp_index = 0; 15433946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < temp_intervals_.Size(); ++i) { 15443946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* temp = temp_intervals_.Get(i); 1545840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (temp->IsHighInterval()) { 1546840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // High intervals can be skipped, they are already handled by the low interval. 1547840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray continue; 1548840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 154901ef345767ea609417fc511e42007705c9667546Nicolas Geoffray HInstruction* at = liveness_.GetTempUser(temp); 155001ef345767ea609417fc511e42007705c9667546Nicolas Geoffray if (at != current) { 15513946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray temp_index = 0; 155201ef345767ea609417fc511e42007705c9667546Nicolas Geoffray current = at; 15533946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 155401ef345767ea609417fc511e42007705c9667546Nicolas Geoffray LocationSummary* locations = at->GetLocations(); 15555368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain switch (temp->GetType()) { 15565368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain case Primitive::kPrimInt: 15575368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain locations->SetTempAt( 15585368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain temp_index++, Location::RegisterLocation(temp->GetRegister())); 15595368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain break; 15605368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain 15615368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain case Primitive::kPrimDouble: 1562840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (codegen_->NeedsTwoRegisters(Primitive::kPrimDouble)) { 1563840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray Location location = Location::FpuRegisterPairLocation( 1564840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray temp->GetRegister(), temp->GetHighInterval()->GetRegister()); 1565840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray locations->SetTempAt(temp_index++, location); 1566840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else { 1567840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray locations->SetTempAt( 1568840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray temp_index++, Location::FpuRegisterLocation(temp->GetRegister())); 1569840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 15705368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain break; 15715368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain 15725368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain default: 15735368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LOG(FATAL) << "Unexpected type for temporary location " 15745368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain << temp->GetType(); 15755368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain } 15763946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 157731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray} 157831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 1579a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} // namespace art 1580