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 19234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray#include <iostream> 20c7dd295a4e0cc1d15c0c96088e55a85389bade74Ian Rogers#include <sstream> 21c7dd295a4e0cc1d15c0c96088e55a85389bade74Ian Rogers 22e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers#include "base/bit_vector-inl.h" 23a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray#include "code_generator.h" 24a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray#include "ssa_liveness_analysis.h" 25a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 26a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraynamespace art { 27a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 28a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraystatic constexpr size_t kMaxLifetimePosition = -1; 2931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffraystatic constexpr size_t kDefaultNumberOfSpillSlots = 4; 30a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 31840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray// For simplicity, we implement register pairs as (reg, reg + 1). 32840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray// Note that this is a requirement for double registers on ARM, since we 33840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray// allocate SRegister. 34840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffraystatic int GetHighForLowRegister(int reg) { return reg + 1; } 35840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffraystatic bool IsLowRegister(int reg) { return (reg & 1) == 0; } 36234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffraystatic bool IsLowOfUnalignedPairInterval(LiveInterval* low) { 37234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray return GetHighForLowRegister(low->GetRegister()) != low->GetHighInterval()->GetRegister(); 38234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray} 39840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 4086dbb9a12119273039ce272b41c809fa548b37b6Nicolas GeoffrayRegisterAllocator::RegisterAllocator(ArenaAllocator* allocator, 4186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray CodeGenerator* codegen, 4286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray const SsaLivenessAnalysis& liveness) 43a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray : allocator_(allocator), 44a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen_(codegen), 4586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray liveness_(liveness), 462aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko unhandled_core_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), 472aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko unhandled_fp_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), 483946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_(nullptr), 492aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko handled_(allocator->Adapter(kArenaAllocRegisterAllocator)), 502aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko active_(allocator->Adapter(kArenaAllocRegisterAllocator)), 512aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko inactive_(allocator->Adapter(kArenaAllocRegisterAllocator)), 522aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko physical_core_register_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), 532aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko physical_fp_register_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), 542aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko temp_intervals_(allocator->Adapter(kArenaAllocRegisterAllocator)), 552aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko int_spill_slots_(allocator->Adapter(kArenaAllocRegisterAllocator)), 562aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko long_spill_slots_(allocator->Adapter(kArenaAllocRegisterAllocator)), 572aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko float_spill_slots_(allocator->Adapter(kArenaAllocRegisterAllocator)), 582aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko double_spill_slots_(allocator->Adapter(kArenaAllocRegisterAllocator)), 5977a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil catch_phi_spill_slots_(0), 602aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko safepoints_(allocator->Adapter(kArenaAllocRegisterAllocator)), 61a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray processing_core_registers_(false), 62a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray number_of_registers_(-1), 63a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray registers_array_(nullptr), 64102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray blocked_core_registers_(codegen->GetBlockedCoreRegisters()), 65102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray blocked_fp_registers_(codegen->GetBlockedFloatingPointRegisters()), 663bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray reserved_out_slots_(0), 67f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell maximum_number_of_live_core_registers_(0), 68f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell maximum_number_of_live_fp_registers_(0) { 692aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko temp_intervals_.reserve(4); 702aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko int_spill_slots_.reserve(kDefaultNumberOfSpillSlots); 712aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko long_spill_slots_.reserve(kDefaultNumberOfSpillSlots); 722aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko float_spill_slots_.reserve(kDefaultNumberOfSpillSlots); 732aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko double_spill_slots_.reserve(kDefaultNumberOfSpillSlots); 742aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko 7558282f4510961317b8d5a364a6f740a78926716fDavid Brazdil codegen->SetupBlockedRegisters(); 762aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko physical_core_register_intervals_.resize(codegen->GetNumberOfCoreRegisters(), nullptr); 772aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko physical_fp_register_intervals_.resize(codegen->GetNumberOfFloatingPointRegisters(), nullptr); 783946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Always reserve for the current method and the graph's max out registers. 793946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // TODO: compute it instead. 80e401d146407d61eeb99f8d6176b2ac13c4df1e33Mathieu Chartier // ArtMethod* takes 2 vregs for 64 bits. 81e401d146407d61eeb99f8d6176b2ac13c4df1e33Mathieu Chartier reserved_out_slots_ = InstructionSetPointerSize(codegen->GetInstructionSet()) / kVRegSize + 82e401d146407d61eeb99f8d6176b2ac13c4df1e33Mathieu Chartier codegen->GetGraph()->GetMaximumNumberOfOutVRegs(); 83a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 84a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 85234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffraybool RegisterAllocator::CanAllocateRegistersFor(const HGraph& graph ATTRIBUTE_UNUSED, 8686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InstructionSet instruction_set) { 87f652cecb984c104d44a0223c3c98400ef8ed8ce2Goran Jakovljevic return instruction_set == kArm 88f652cecb984c104d44a0223c3c98400ef8ed8ce2Goran Jakovljevic || instruction_set == kArm64 89f652cecb984c104d44a0223c3c98400ef8ed8ce2Goran Jakovljevic || instruction_set == kMips 904dda3376b71209fae07f5c3c8ac3eb4b54207aa8Alexey Frunze || instruction_set == kMips64 91f652cecb984c104d44a0223c3c98400ef8ed8ce2Goran Jakovljevic || instruction_set == kThumb2 92234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray || instruction_set == kX86 93f652cecb984c104d44a0223c3c98400ef8ed8ce2Goran Jakovljevic || instruction_set == kX86_64; 9486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 9586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 9686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraystatic bool ShouldProcess(bool processing_core_registers, LiveInterval* interval) { 973946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (interval == nullptr) return false; 9886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray bool is_core_register = (interval->GetType() != Primitive::kPrimDouble) 9986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && (interval->GetType() != Primitive::kPrimFloat); 100a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return processing_core_registers == is_core_register; 101a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 102a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 10386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::AllocateRegisters() { 10486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray AllocateRegistersInternal(); 10586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Resolve(); 10686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 10786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (kIsDebugBuild) { 10886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray processing_core_registers_ = true; 10986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ValidateInternal(true); 11086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray processing_core_registers_ = false; 11186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ValidateInternal(true); 1125976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // Check that the linear order is still correct with regards to lifetime positions. 1135976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // Since only parallel moves have been inserted during the register allocation, 1145976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // these checks are mostly for making sure these moves have been added correctly. 1155976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray size_t current_liveness = 0; 1160d9f17de8f21a10702de1510b73e89d07b3b9bbfNicolas Geoffray for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { 1175976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray HBasicBlock* block = it.Current(); 1185976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 1195976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray HInstruction* instruction = inst_it.Current(); 1205976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray DCHECK_LE(current_liveness, instruction->GetLifetimePosition()); 1215976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray current_liveness = instruction->GetLifetimePosition(); 1225976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray } 1235976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray for (HInstructionIterator inst_it(block->GetInstructions()); 1245976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray !inst_it.Done(); 1255976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray inst_it.Advance()) { 1265976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray HInstruction* instruction = inst_it.Current(); 1275976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray DCHECK_LE(current_liveness, instruction->GetLifetimePosition()) << instruction->DebugName(); 1285976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray current_liveness = instruction->GetLifetimePosition(); 1295976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray } 1305976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray } 13186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 13286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 13386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 13477a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdilvoid RegisterAllocator::BlockRegister(Location location, size_t start, size_t end) { 13556b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray int reg = location.reg(); 136102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray DCHECK(location.IsRegister() || location.IsFpuRegister()); 137102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* interval = location.IsRegister() 1382aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko ? physical_core_register_intervals_[reg] 1392aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko : physical_fp_register_intervals_[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()) { 1462aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko physical_core_register_intervals_[reg] = interval; 147102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 1482aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko physical_fp_register_intervals_[reg] = interval; 149102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 15086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 15186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(interval->GetRegister() == reg); 15286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray interval->AddRange(start, end); 15386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 15486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 15577a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdilvoid RegisterAllocator::BlockRegisters(size_t start, size_t end, bool caller_save_only) { 15677a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil for (size_t i = 0; i < codegen_->GetNumberOfCoreRegisters(); ++i) { 15777a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil if (!caller_save_only || !codegen_->IsCoreCalleeSaveRegister(i)) { 15877a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil BlockRegister(Location::RegisterLocation(i), start, end); 15977a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil } 16077a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil } 16177a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil for (size_t i = 0; i < codegen_->GetNumberOfFloatingPointRegisters(); ++i) { 16277a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil if (!caller_save_only || !codegen_->IsFloatingPointCalleeSaveRegister(i)) { 16377a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil BlockRegister(Location::FpuRegisterLocation(i), start, end); 16477a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil } 16577a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil } 16677a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil} 16777a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil 16886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::AllocateRegistersInternal() { 1693946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Iterate post-order, to ensure the list is sorted, and the last added interval 1703946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // is the one with the lowest start position. 1710d9f17de8f21a10702de1510b73e89d07b3b9bbfNicolas Geoffray for (HLinearPostOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { 1723946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray HBasicBlock* block = it.Current(); 173277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe for (HBackwardInstructionIterator back_it(block->GetInstructions()); !back_it.Done(); 174277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe back_it.Advance()) { 175277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe ProcessInstruction(back_it.Current()); 1763946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 177277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 178277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe ProcessInstruction(inst_it.Current()); 1793946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 18077a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil 18115bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray if (block->IsCatchBlock() || 182ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray (block->IsLoopHeader() && block->GetLoopInformation()->IsIrreducible())) { 18315bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray // By blocking all registers at the top of each catch block or irreducible loop, we force 18415bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray // intervals belonging to the live-in set of the catch/header block to be spilled. 18515bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray // TODO(ngeoffray): Phis in this block could be allocated in register. 18677a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil size_t position = block->GetLifetimeStart(); 18777a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil BlockRegisters(position, position + 1); 18877a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil } 1893946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 190a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1913946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray number_of_registers_ = codegen_->GetNumberOfCoreRegisters(); 1925233f93ee336b3581ccdb993ff6342c52fec34b0Vladimir Marko registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_, 1935233f93ee336b3581ccdb993ff6342c52fec34b0Vladimir Marko kArenaAllocRegisterAllocator); 1943946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray processing_core_registers_ = true; 1953946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_ = &unhandled_core_intervals_; 1962aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko for (LiveInterval* fixed : physical_core_register_intervals_) { 197102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (fixed != nullptr) { 198296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Fixed interval is added to inactive_ instead of unhandled_. 199296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // It's also the only type of inactive interval whose start position 200296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // can be after the current interval during linear scan. 201296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Fixed interval is never split and never moves to unhandled_. 2022aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko inactive_.push_back(fixed); 203102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 204102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 2053946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LinearScan(); 206a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 2072aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko inactive_.clear(); 2082aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko active_.clear(); 2092aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko handled_.clear(); 210a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 2113946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray number_of_registers_ = codegen_->GetNumberOfFloatingPointRegisters(); 2125233f93ee336b3581ccdb993ff6342c52fec34b0Vladimir Marko registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_, 2135233f93ee336b3581ccdb993ff6342c52fec34b0Vladimir Marko kArenaAllocRegisterAllocator); 2143946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray processing_core_registers_ = false; 2153946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_ = &unhandled_fp_intervals_; 2162aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko for (LiveInterval* fixed : physical_fp_register_intervals_) { 217102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (fixed != nullptr) { 218296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Fixed interval is added to inactive_ instead of unhandled_. 219296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // It's also the only type of inactive interval whose start position 220296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // can be after the current interval during linear scan. 221296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Fixed interval is never split and never moves to unhandled_. 2222aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko inactive_.push_back(fixed); 223102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 224102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 2253946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LinearScan(); 2263946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray} 22786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 2283946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffrayvoid RegisterAllocator::ProcessInstruction(HInstruction* instruction) { 2293946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LocationSummary* locations = instruction->GetLocations(); 2303946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t position = instruction->GetLifetimePosition(); 2313946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 2323946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (locations == nullptr) return; 2333946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 2343946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Create synthesized intervals for temporaries. 2353946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < locations->GetTempCount(); ++i) { 2363946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray Location temp = locations->GetTemp(i); 23752839d17c06175e19ca4a093fb878450d1c4310dNicolas Geoffray if (temp.IsRegister() || temp.IsFpuRegister()) { 238102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray BlockRegister(temp, position, position + 1); 23945b83aff85a8a8dfcae0da90d010fa2d7eb299a7Nicolas Geoffray // Ensure that an explicit temporary register is marked as being allocated. 24045b83aff85a8a8dfcae0da90d010fa2d7eb299a7Nicolas Geoffray codegen_->AddAllocatedRegister(temp); 2413946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 242102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray DCHECK(temp.IsUnallocated()); 2435368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain switch (temp.GetPolicy()) { 2445368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain case Location::kRequiresRegister: { 2455368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LiveInterval* interval = 2465368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimInt); 2472aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko temp_intervals_.push_back(interval); 248f01d34445953e6b9c9b13de1dd32a5c0ee5abab5Nicolas Geoffray interval->AddTempUse(instruction, i); 2492aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko unhandled_core_intervals_.push_back(interval); 2505368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain break; 2515368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain } 2525368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain 2535368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain case Location::kRequiresFpuRegister: { 2545368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LiveInterval* interval = 2555368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimDouble); 2562aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko temp_intervals_.push_back(interval); 257f01d34445953e6b9c9b13de1dd32a5c0ee5abab5Nicolas Geoffray interval->AddTempUse(instruction, i); 258840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (codegen_->NeedsTwoRegisters(Primitive::kPrimDouble)) { 2595588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray interval->AddHighInterval(/* is_temp */ true); 260840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray LiveInterval* high = interval->GetHighInterval(); 2612aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko temp_intervals_.push_back(high); 2622aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko unhandled_fp_intervals_.push_back(high); 263840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 2642aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko unhandled_fp_intervals_.push_back(interval); 2655368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain break; 2665368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain } 2675368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain 2685368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain default: 2695368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LOG(FATAL) << "Unexpected policy for temporary location " 2705368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain << temp.GetPolicy(); 2715368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain } 272a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 273a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 27486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 2753bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray bool core_register = (instruction->GetType() != Primitive::kPrimDouble) 2763bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray && (instruction->GetType() != Primitive::kPrimFloat); 2773bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray 2788158f28b6689314213eb4dbbe14166073be71f7eAlexandre Rames if (locations->NeedsSafepoint()) { 279c0572a451944f78397619dec34a38c36c11e9d2aNicolas Geoffray if (codegen_->IsLeafMethod()) { 280c0572a451944f78397619dec34a38c36c11e9d2aNicolas Geoffray // TODO: We do this here because we do not want the suspend check to artificially 281c0572a451944f78397619dec34a38c36c11e9d2aNicolas Geoffray // create live registers. We should find another place, but this is currently the 282c0572a451944f78397619dec34a38c36c11e9d2aNicolas Geoffray // simplest. 283c0572a451944f78397619dec34a38c36c11e9d2aNicolas Geoffray DCHECK(instruction->IsSuspendCheckEntry()); 284c0572a451944f78397619dec34a38c36c11e9d2aNicolas Geoffray instruction->GetBlock()->RemoveInstruction(instruction); 285c0572a451944f78397619dec34a38c36c11e9d2aNicolas Geoffray return; 2863bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 2872aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko safepoints_.push_back(instruction); 2883bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray if (locations->OnlyCallsOnSlowPath()) { 2893bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // We add a synthesized range at this position to record the live registers 2903bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // at this position. Ideally, we could just update the safepoints when locations 2913bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // are updated, but we currently need to know the full stack size before updating 2923bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // locations (because of parameters and the fact that we don't have a frame pointer). 2933bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // And knowing the full stack size requires to know the maximum number of live 2943bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // registers at calls in slow paths. 2953bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // By adding the following interval in the algorithm, we can compute this 2963bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // maximum before updating locations. 2973bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray LiveInterval* interval = LiveInterval::MakeSlowPathInterval(allocator_, instruction); 298acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray interval->AddRange(position, position + 1); 29987d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray AddSorted(&unhandled_core_intervals_, interval); 30087d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray AddSorted(&unhandled_fp_intervals_, interval); 3013bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 3023bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 3033bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray 3043bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray if (locations->WillCall()) { 30577a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil BlockRegisters(position, position + 1, /* caller_save_only */ true); 3063946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3073946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 3083946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < instruction->InputCount(); ++i) { 3093946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray Location input = locations->InAt(i); 310102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (input.IsRegister() || input.IsFpuRegister()) { 311102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray BlockRegister(input, position, position + 1); 312840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (input.IsPair()) { 313840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray BlockRegister(input.ToLow(), position, position + 1); 314840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray BlockRegister(input.ToHigh(), position, position + 1); 3153946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3163946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3173946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 3183946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* current = instruction->GetLiveInterval(); 3193946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current == nullptr) return; 3203946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 3212aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko ArenaVector<LiveInterval*>& unhandled = core_register 322102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ? unhandled_core_intervals_ 323102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray : unhandled_fp_intervals_; 324102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray 3252aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko DCHECK(unhandled.empty() || current->StartsBeforeOrAt(unhandled.back())); 32687d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray 327840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (codegen_->NeedsTwoRegisters(current->GetType())) { 328840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray current->AddHighInterval(); 329840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 330840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 3312aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko for (size_t safepoint_index = safepoints_.size(); safepoint_index > 0; --safepoint_index) { 3322aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko HInstruction* safepoint = safepoints_[safepoint_index - 1u]; 3335588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray size_t safepoint_position = safepoint->GetLifetimePosition(); 3345588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray 3355588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray // Test that safepoints are ordered in the optimal way. 3362aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko DCHECK(safepoint_index == safepoints_.size() || 3372aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko safepoints_[safepoint_index]->GetLifetimePosition() < safepoint_position); 3385588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray 3395588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray if (safepoint_position == current->GetStart()) { 3405588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray // The safepoint is for this instruction, so the location of the instruction 3415588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray // does not need to be saved. 3422aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko DCHECK_EQ(safepoint_index, safepoints_.size()); 3435588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray DCHECK_EQ(safepoint, instruction); 3445588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray continue; 3455588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray } else if (current->IsDeadAt(safepoint_position)) { 3465588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray break; 3475588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray } else if (!current->Covers(safepoint_position)) { 3485588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray // Hole in the interval. 3495588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray continue; 3505588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray } 3515588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray current->AddSafepoint(safepoint); 3525588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray } 3533fc992f9dfe8f49ff350132323cc635f102b7b62David Brazdil current->ResetSearchCache(); 3545588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray 3553946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Some instructions define their output in fixed register/stack slot. We need 3563946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // to ensure we know these locations before doing register allocation. For a 3573946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // given register, we create an interval that covers these locations. The register 3583946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // will be unavailable at these locations when trying to allocate one for an 3593946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // interval. 3603946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // 3613946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // The backwards walking ensures the ranges are ordered on increasing start positions. 3623946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray Location output = locations->Out(); 363d0d4852847432368b090c184d6639e573538dccfCalin Juravle if (output.IsUnallocated() && output.GetPolicy() == Location::kSameAsFirstInput) { 364d0d4852847432368b090c184d6639e573538dccfCalin Juravle Location first = locations->InAt(0); 365d0d4852847432368b090c184d6639e573538dccfCalin Juravle if (first.IsRegister() || first.IsFpuRegister()) { 366d0d4852847432368b090c184d6639e573538dccfCalin Juravle current->SetFrom(position + 1); 367d0d4852847432368b090c184d6639e573538dccfCalin Juravle current->SetRegister(first.reg()); 368840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (first.IsPair()) { 369840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray current->SetFrom(position + 1); 370840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray current->SetRegister(first.low()); 371840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray LiveInterval* high = current->GetHighInterval(); 372840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray high->SetRegister(first.high()); 373840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray high->SetFrom(position + 1); 374d0d4852847432368b090c184d6639e573538dccfCalin Juravle } 375d0d4852847432368b090c184d6639e573538dccfCalin Juravle } else if (output.IsRegister() || output.IsFpuRegister()) { 3763946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Shift the interval's start by one to account for the blocked register. 3773946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray current->SetFrom(position + 1); 37856b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray current->SetRegister(output.reg()); 379102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray BlockRegister(output, position, position + 1); 380840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (output.IsPair()) { 381840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray current->SetFrom(position + 1); 382840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray current->SetRegister(output.low()); 383840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray LiveInterval* high = current->GetHighInterval(); 384840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray high->SetRegister(output.high()); 385840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray high->SetFrom(position + 1); 386840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray BlockRegister(output.ToLow(), position, position + 1); 387840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray BlockRegister(output.ToHigh(), position, position + 1); 3883946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else if (output.IsStackSlot() || output.IsDoubleStackSlot()) { 3893946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray current->SetSpillSlot(output.GetStackIndex()); 390840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else { 391840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(output.IsUnallocated() || output.IsConstant()); 3923946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3933946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 39477a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil if (instruction->IsPhi() && instruction->AsPhi()->IsCatchPhi()) { 39577a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil AllocateSpillSlotForCatchPhi(instruction->AsPhi()); 39677a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil } 39777a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil 3983946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // If needed, add interval to the list of unhandled intervals. 3993946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current->HasSpillSlot() || instruction->IsConstant()) { 400c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray // Split just before first register use. 4013946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t first_register_use = current->FirstRegisterUse(); 4023946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (first_register_use != kNoLifetime) { 4038cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray LiveInterval* split = SplitBetween(current, current->GetStart(), first_register_use - 1); 404b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // Don't add directly to `unhandled`, it needs to be sorted and the start 4053946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // of this new interval might be after intervals already in the list. 4063946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(&unhandled, split); 4073946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 4083946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Nothing to do, we won't allocate a register for this value. 4093946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 4103946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 411b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // Don't add directly to `unhandled`, temp or safepoint intervals 412b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // for this instruction may have been added, and those can be 413b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // processed first. 414b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray AddSorted(&unhandled, current); 4153946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 416a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 417a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 41831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffrayclass AllRangesIterator : public ValueObject { 41931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray public: 42031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray explicit AllRangesIterator(LiveInterval* interval) 42131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray : current_interval_(interval), 42231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_(interval->GetFirstRange()) {} 42331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 42431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray bool Done() const { return current_interval_ == nullptr; } 42531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveRange* CurrentRange() const { return current_range_; } 42631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* CurrentInterval() const { return current_interval_; } 42731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 42831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray void Advance() { 42931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_ = current_range_->GetNext(); 43031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current_range_ == nullptr) { 43131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_interval_ = current_interval_->GetNextSibling(); 43231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current_interval_ != nullptr) { 43331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_ = current_interval_->GetFirstRange(); 43431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 43531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 43631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 43731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 43831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray private: 43931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* current_interval_; 44031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveRange* current_range_; 44131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 44231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray DISALLOW_COPY_AND_ASSIGN(AllRangesIterator); 44331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray}; 44431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 44586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraybool RegisterAllocator::ValidateInternal(bool log_fatal_on_failure) const { 44686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // To simplify unit testing, we eagerly create the array of intervals, and 44786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // call the helper method. 448f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko ArenaVector<LiveInterval*> intervals(allocator_->Adapter(kArenaAllocRegisterAllocatorValidate)); 44986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0; i < liveness_.GetNumberOfSsaValues(); ++i) { 45086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 45186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (ShouldProcess(processing_core_registers_, instruction->GetLiveInterval())) { 4522aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko intervals.push_back(instruction->GetLiveInterval()); 45386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 45486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 45586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 4562aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko const ArenaVector<LiveInterval*>* physical_register_intervals = processing_core_registers_ 4572aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko ? &physical_core_register_intervals_ 4582aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko : &physical_fp_register_intervals_; 4592aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko for (LiveInterval* fixed : *physical_register_intervals) { 4602aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko if (fixed != nullptr) { 4612aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko intervals.push_back(fixed); 46286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 46386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 46486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 4652aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko for (LiveInterval* temp : temp_intervals_) { 4663946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (ShouldProcess(processing_core_registers_, temp)) { 4672aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko intervals.push_back(temp); 4683946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 4693946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 4703946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 471776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray return ValidateIntervals(intervals, GetNumberOfSpillSlots(), reserved_out_slots_, *codegen_, 4723946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray allocator_, processing_core_registers_, log_fatal_on_failure); 47386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 47486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 4752aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Markobool RegisterAllocator::ValidateIntervals(const ArenaVector<LiveInterval*>& intervals, 47631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray size_t number_of_spill_slots, 4773946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t number_of_out_slots, 478a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray const CodeGenerator& codegen, 479a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray ArenaAllocator* allocator, 480a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool processing_core_registers, 481a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool log_fatal_on_failure) { 482a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t number_of_registers = processing_core_registers 483a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray ? codegen.GetNumberOfCoreRegisters() 484a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray : codegen.GetNumberOfFloatingPointRegisters(); 4852aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko ArenaVector<ArenaBitVector*> liveness_of_values( 486f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko allocator->Adapter(kArenaAllocRegisterAllocatorValidate)); 4872aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko liveness_of_values.reserve(number_of_registers + number_of_spill_slots); 488a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 489f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko size_t max_end = 0u; 490f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko for (LiveInterval* start_interval : intervals) { 491f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko for (AllRangesIterator it(start_interval); !it.Done(); it.Advance()) { 492f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko max_end = std::max(max_end, it.CurrentRange()->GetEnd()); 493f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko } 494f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko } 495f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko 496a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Allocate a bit vector per register. A live interval that has a register 497a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // allocated will populate the associated bit vector based on its live ranges. 49831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t i = 0; i < number_of_registers + number_of_spill_slots; ++i) { 499f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko liveness_of_values.push_back( 500f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko ArenaBitVector::Create(allocator, max_end, false, kArenaAllocRegisterAllocatorValidate)); 501a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 502a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 5032aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko for (LiveInterval* start_interval : intervals) { 5042aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko for (AllRangesIterator it(start_interval); !it.Done(); it.Advance()) { 50531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* current = it.CurrentInterval(); 50686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* defined_by = current->GetParent()->GetDefinedBy(); 50786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->GetParent()->HasSpillSlot() 50876b1e1799a713a19218de26b171b0aef48a59e98Nicolas Geoffray // Parameters and current method have their own stack slot. 50976b1e1799a713a19218de26b171b0aef48a59e98Nicolas Geoffray && !(defined_by != nullptr && (defined_by->IsParameterValue() 51076b1e1799a713a19218de26b171b0aef48a59e98Nicolas Geoffray || defined_by->IsCurrentMethod()))) { 5112aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko BitVector* liveness_of_spill_slot = liveness_of_values[number_of_registers 5123946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray + current->GetParent()->GetSpillSlot() / kVRegSize 5132aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko - number_of_out_slots]; 51431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 51531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (liveness_of_spill_slot->IsBitSet(j)) { 51631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (log_fatal_on_failure) { 51731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray std::ostringstream message; 51831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray message << "Spill slot conflict at " << j; 51931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LOG(FATAL) << message.str(); 52031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 52131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray return false; 52231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 52331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 52431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_spill_slot->SetBit(j); 52531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 52631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 527a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 52831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 52931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current->HasRegister()) { 53045b83aff85a8a8dfcae0da90d010fa2d7eb299a7Nicolas Geoffray if (kIsDebugBuild && log_fatal_on_failure && !current->IsFixed()) { 53145b83aff85a8a8dfcae0da90d010fa2d7eb299a7Nicolas Geoffray // Only check when an error is fatal. Only tests code ask for non-fatal failures 53245b83aff85a8a8dfcae0da90d010fa2d7eb299a7Nicolas Geoffray // and test code may not properly fill the right information to the code generator. 53345b83aff85a8a8dfcae0da90d010fa2d7eb299a7Nicolas Geoffray CHECK(codegen.HasAllocatedRegister(processing_core_registers, current->GetRegister())); 53445b83aff85a8a8dfcae0da90d010fa2d7eb299a7Nicolas Geoffray } 5352aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko BitVector* liveness_of_register = liveness_of_values[current->GetRegister()]; 53631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 53731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (liveness_of_register->IsBitSet(j)) { 538829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray if (current->IsUsingInputRegister() && current->CanUseInputRegister()) { 539829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray continue; 540829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 541a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (log_fatal_on_failure) { 542a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray std::ostringstream message; 5433946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray message << "Register conflict at " << j << " "; 5443946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (defined_by != nullptr) { 5453946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray message << "(" << defined_by->DebugName() << ")"; 5463946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 5473946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray message << "for "; 548a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (processing_core_registers) { 549a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen.DumpCoreRegister(message, current->GetRegister()); 550a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 551a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen.DumpFloatingPointRegister(message, current->GetRegister()); 552a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 553a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LOG(FATAL) << message.str(); 554a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 555a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 556a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 557a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 55831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_register->SetBit(j); 559a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 560a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 56131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 56231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 563a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 564a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 565a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 566a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 56786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::DumpInterval(std::ostream& stream, LiveInterval* interval) const { 568a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray interval->Dump(stream); 569a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << ": "; 570a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->HasRegister()) { 571102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (interval->IsFloatingPoint()) { 57286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray codegen_->DumpFloatingPointRegister(stream, interval->GetRegister()); 573102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 574102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray codegen_->DumpCoreRegister(stream, interval->GetRegister()); 575a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 576a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 577a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << "spilled"; 578a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 579a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << std::endl; 580a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 581a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 582296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yangvoid RegisterAllocator::DumpAllIntervals(std::ostream& stream) const { 583296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang stream << "inactive: " << std::endl; 5842aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko for (LiveInterval* inactive_interval : inactive_) { 5852aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko DumpInterval(stream, inactive_interval); 586296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 587296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang stream << "active: " << std::endl; 5882aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko for (LiveInterval* active_interval : active_) { 5892aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko DumpInterval(stream, active_interval); 590296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 591296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang stream << "unhandled: " << std::endl; 592296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang auto unhandled = (unhandled_ != nullptr) ? 593296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang unhandled_ : &unhandled_core_intervals_; 5942aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko for (LiveInterval* unhandled_interval : *unhandled) { 5952aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko DumpInterval(stream, unhandled_interval); 596296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 597296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang stream << "handled: " << std::endl; 5982aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko for (LiveInterval* handled_interval : handled_) { 5992aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko DumpInterval(stream, handled_interval); 600296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 601296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang} 602296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang 603a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// By the book implementation of a linear scan register allocator. 604a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffrayvoid RegisterAllocator::LinearScan() { 6052aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko while (!unhandled_->empty()) { 606a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (1) Remove interval with the lowest start position from unhandled. 6072aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko LiveInterval* current = unhandled_->back(); 6082aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko unhandled_->pop_back(); 6092e92bc2ba2446525a07f5172d1cd30ab49d26cd6Nicolas Geoffray 6102e92bc2ba2446525a07f5172d1cd30ab49d26cd6Nicolas Geoffray // Make sure the interval is an expected state. 6113946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray DCHECK(!current->IsFixed() && !current->HasSpillSlot()); 6122e92bc2ba2446525a07f5172d1cd30ab49d26cd6Nicolas Geoffray // Make sure we are going in the right order. 6132aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko DCHECK(unhandled_->empty() || unhandled_->back()->GetStart() >= current->GetStart()); 6142e92bc2ba2446525a07f5172d1cd30ab49d26cd6Nicolas Geoffray // Make sure a low interval is always with a high. 6152aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko DCHECK(!current->IsLowInterval() || unhandled_->back()->IsHighInterval()); 6162e92bc2ba2446525a07f5172d1cd30ab49d26cd6Nicolas Geoffray // Make sure a high interval is always with a low. 6172e92bc2ba2446525a07f5172d1cd30ab49d26cd6Nicolas Geoffray DCHECK(current->IsLowInterval() || 6182aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko unhandled_->empty() || 6192aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko !unhandled_->back()->IsHighInterval()); 62087d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray 621a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t position = current->GetStart(); 622a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 623296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Remember the inactive_ size here since the ones moved to inactive_ from 624296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // active_ below shouldn't need to be re-checked. 6252aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko size_t inactive_intervals_to_handle = inactive_.size(); 626296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang 627a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (2) Remove currently active intervals that are dead at this position. 628a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Move active intervals that have a lifetime hole at this position 629a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // to inactive. 630b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko auto active_kept_end = std::remove_if( 631b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko active_.begin(), 632b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko active_.end(), 633b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko [this, position](LiveInterval* interval) { 634b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko if (interval->IsDeadAt(position)) { 635b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko handled_.push_back(interval); 636b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko return true; 637b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko } else if (!interval->Covers(position)) { 638b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko inactive_.push_back(interval); 639b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko return true; 640b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko } else { 641b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko return false; // Keep this interval. 642b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko } 643b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko }); 6442aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko active_.erase(active_kept_end, active_.end()); 645a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 646a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (3) Remove currently inactive intervals that are dead at this position. 647a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Move inactive intervals that cover this position to active. 6482aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko auto inactive_to_handle_end = inactive_.begin() + inactive_intervals_to_handle; 649b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko auto inactive_kept_end = std::remove_if( 650b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko inactive_.begin(), 651b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko inactive_to_handle_end, 652b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko [this, position](LiveInterval* interval) { 653b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko DCHECK(interval->GetStart() < position || interval->IsFixed()); 654b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko if (interval->IsDeadAt(position)) { 655b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko handled_.push_back(interval); 656b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko return true; 657b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko } else if (interval->Covers(position)) { 658b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko active_.push_back(interval); 659b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko return true; 660b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko } else { 661b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko return false; // Keep this interval. 662b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko } 663b95fb775cc4c08349d0d905adbc96ad85e50601dVladimir Marko }); 6642aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko inactive_.erase(inactive_kept_end, inactive_to_handle_end); 665a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 666acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray if (current->IsSlowPathSafepoint()) { 667acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray // Synthesized interval to record the maximum number of live registers 668acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray // at safepoints. No need to allocate a register for it. 669f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell if (processing_core_registers_) { 670f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell maximum_number_of_live_core_registers_ = 6712aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko std::max(maximum_number_of_live_core_registers_, active_.size()); 672f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell } else { 673f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell maximum_number_of_live_fp_registers_ = 6742aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko std::max(maximum_number_of_live_fp_registers_, active_.size()); 675f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell } 6762aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko DCHECK(unhandled_->empty() || unhandled_->back()->GetStart() > current->GetStart()); 677acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray continue; 678acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray } 679acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray 680840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (current->IsHighInterval() && !current->GetLowInterval()->HasRegister()) { 681840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(!current->HasRegister()); 682840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // Allocating the low part was unsucessful. The splitted interval for the high part 683840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // will be handled next (it is in the `unhandled_` list). 684840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray continue; 685840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 686840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 687a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (4) Try to find an available register. 688a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool success = TryAllocateFreeReg(current); 689a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 690a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (5) If no register could be found, we need to spill. 691a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (!success) { 692a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray success = AllocateBlockedReg(current); 693a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 694a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 695a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (6) If the interval had a register allocated, add it to the list of active 696a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // intervals. 697a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (success) { 698988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray codegen_->AddAllocatedRegister(processing_core_registers_ 699988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray ? Location::RegisterLocation(current->GetRegister()) 700988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray : Location::FpuRegisterLocation(current->GetRegister())); 7012aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko active_.push_back(current); 702840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (current->HasHighInterval() && !current->GetHighInterval()->HasRegister()) { 703840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray current->GetHighInterval()->SetRegister(GetHighForLowRegister(current->GetRegister())); 704840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 705a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 706a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 707a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 708a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 709829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffraystatic void FreeIfNotCoverAt(LiveInterval* interval, size_t position, size_t* free_until) { 710829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray DCHECK(!interval->IsHighInterval()); 711829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // Note that the same instruction may occur multiple times in the input list, 712829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // so `free_until` may have changed already. 7133fc992f9dfe8f49ff350132323cc635f102b7b62David Brazdil // Since `position` is not the current scan position, we need to use CoversSlow. 714829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray if (interval->IsDeadAt(position)) { 715829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // Set the register to be free. Note that inactive intervals might later 716829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // update this. 717829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray free_until[interval->GetRegister()] = kMaxLifetimePosition; 718829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray if (interval->HasHighInterval()) { 719829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray DCHECK(interval->GetHighInterval()->IsDeadAt(position)); 720829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray free_until[interval->GetHighInterval()->GetRegister()] = kMaxLifetimePosition; 721829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 7223fc992f9dfe8f49ff350132323cc635f102b7b62David Brazdil } else if (!interval->CoversSlow(position)) { 723829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // The interval becomes inactive at `defined_by`. We make its register 724829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // available only until the next use strictly after `defined_by`. 725829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray free_until[interval->GetRegister()] = interval->FirstUseAfter(position); 726829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray if (interval->HasHighInterval()) { 7273fc992f9dfe8f49ff350132323cc635f102b7b62David Brazdil DCHECK(!interval->GetHighInterval()->CoversSlow(position)); 728829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray free_until[interval->GetHighInterval()->GetRegister()] = free_until[interval->GetRegister()]; 729829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 730829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 731829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray} 732829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray 733a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// Find a free register. If multiple are found, pick the register that 734a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// is free the longest. 735a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::TryAllocateFreeReg(LiveInterval* current) { 736a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t* free_until = registers_array_; 737a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 738a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // First set all registers to be free. 739a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 740a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray free_until[i] = kMaxLifetimePosition; 741a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 742a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 743296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // For each active interval, set its register to not free. 7442aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko for (LiveInterval* interval : active_) { 745296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK(interval->HasRegister()); 746296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang free_until[interval->GetRegister()] = 0; 747296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 748296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang 749829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // An interval that starts an instruction (that is, it is not split), may 750829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // re-use the registers used by the inputs of that instruciton, based on the 751829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // location summary. 752829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray HInstruction* defined_by = current->GetDefinedBy(); 753829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray if (defined_by != nullptr && !current->IsSplit()) { 754829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray LocationSummary* locations = defined_by->GetLocations(); 755829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray if (!locations->OutputCanOverlapWithInputs() && locations->Out().IsUnallocated()) { 75694015b939060f5041d408d48717f22443e55b6adNicolas Geoffray for (size_t i = 0, e = defined_by->InputCount(); i < e; ++i) { 757829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // Take the last interval of the input. It is the location of that interval 758829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // that will be used at `defined_by`. 75994015b939060f5041d408d48717f22443e55b6adNicolas Geoffray LiveInterval* interval = defined_by->InputAt(i)->GetLiveInterval()->GetLastSibling(); 760829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // Note that interval may have not been processed yet. 761829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // TODO: Handle non-split intervals last in the work list. 76294015b939060f5041d408d48717f22443e55b6adNicolas Geoffray if (locations->InAt(i).IsValid() 76394015b939060f5041d408d48717f22443e55b6adNicolas Geoffray && interval->HasRegister() 76494015b939060f5041d408d48717f22443e55b6adNicolas Geoffray && interval->SameRegisterKind(*current)) { 765829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // The input must be live until the end of `defined_by`, to comply to 766829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // the linear scan algorithm. So we use `defined_by`'s end lifetime 767829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // position to check whether the input is dead or is inactive after 768829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // `defined_by`. 7693fc992f9dfe8f49ff350132323cc635f102b7b62David Brazdil DCHECK(interval->CoversSlow(defined_by->GetLifetimePosition())); 770829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray size_t position = defined_by->GetLifetimePosition() + 1; 771829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray FreeIfNotCoverAt(interval, position, free_until); 772829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 773829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 774829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 775829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 776829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray 777a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each inactive interval, set its register to be free until 778a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // the next intersection with `current`. 7792aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko for (LiveInterval* inactive : inactive_) { 780296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Temp/Slow-path-safepoint interval has no holes. 781296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK(!inactive->IsTemp() && !inactive->IsSlowPathSafepoint()); 782296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang if (!current->IsSplit() && !inactive->IsFixed()) { 783296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Neither current nor inactive are fixed. 784296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Thanks to SSA, a non-split interval starting in a hole of an 785296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // inactive interval should never intersect with that inactive interval. 786296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Only if it's not fixed though, because fixed intervals don't come from SSA. 787296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime); 788296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang continue; 789296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 790296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang 791a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(inactive->HasRegister()); 792296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang if (free_until[inactive->GetRegister()] == 0) { 793296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Already used by some active interval. No need to intersect. 794296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang continue; 795296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 796a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t next_intersection = inactive->FirstIntersectionWith(current); 797a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (next_intersection != kNoLifetime) { 798aac0f39a3501a7f7dd04b2342c2a16961969f139Nicolas Geoffray free_until[inactive->GetRegister()] = 799aac0f39a3501a7f7dd04b2342c2a16961969f139Nicolas Geoffray std::min(free_until[inactive->GetRegister()], next_intersection); 800a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 801a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 802a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 8036c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray int reg = kNoRegister; 8043946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current->HasRegister()) { 8053946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Some instructions have a fixed register output. 8063946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray reg = current->GetRegister(); 807840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (free_until[reg] == 0) { 808840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(current->IsHighInterval()); 809840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // AllocateBlockedReg will spill the holder of the register. 810840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return false; 811840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 8123946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 813840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(!current->IsHighInterval()); 814fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray int hint = current->FindFirstRegisterHint(free_until, liveness_); 815f29758111e71a7d14f3e52d78773561a5d59961fNicolas Geoffray if ((hint != kNoRegister) 816f29758111e71a7d14f3e52d78773561a5d59961fNicolas Geoffray // For simplicity, if the hint we are getting for a pair cannot be used, 817f29758111e71a7d14f3e52d78773561a5d59961fNicolas Geoffray // we are just going to allocate a new pair. 818f29758111e71a7d14f3e52d78773561a5d59961fNicolas Geoffray && !(current->IsLowInterval() && IsBlocked(GetHighForLowRegister(hint)))) { 81901ef345767ea609417fc511e42007705c9667546Nicolas Geoffray DCHECK(!IsBlocked(hint)); 82001ef345767ea609417fc511e42007705c9667546Nicolas Geoffray reg = hint; 821840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (current->IsLowInterval()) { 8226c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray reg = FindAvailableRegisterPair(free_until, current->GetStart()); 82301ef345767ea609417fc511e42007705c9667546Nicolas Geoffray } else { 8248826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray reg = FindAvailableRegister(free_until, current); 825a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 826a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 827a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 8286c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK_NE(reg, kNoRegister); 829a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // If we could not find a register, we need to spill. 830840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (free_until[reg] == 0) { 831840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return false; 832840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 833840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 834234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray if (current->IsLowInterval()) { 835234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray // If the high register of this interval is not available, we need to spill. 836234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray int high_reg = current->GetHighInterval()->GetRegister(); 837234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray if (high_reg == kNoRegister) { 838234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray high_reg = GetHighForLowRegister(reg); 839234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray } 840234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray if (free_until[high_reg] == 0) { 841234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray return false; 842234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray } 843a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 844a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 845a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray current->SetRegister(reg); 846a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (!current->IsDeadAt(free_until[reg])) { 847a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // If the register is only available for a subset of live ranges 8488272688499c2232355db34d94057983fd436173dNicolas Geoffray // covered by `current`, split `current` before the position where 849a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // the register is not available anymore. 8508272688499c2232355db34d94057983fd436173dNicolas Geoffray LiveInterval* split = SplitBetween(current, current->GetStart(), free_until[reg]); 851a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(split != nullptr); 8523946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 853a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 854a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 855a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 856a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 857a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::IsBlocked(int reg) const { 858102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return processing_core_registers_ 859102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ? blocked_core_registers_[reg] 860102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray : blocked_fp_registers_[reg]; 861a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 862a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 8636c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffrayint RegisterAllocator::FindAvailableRegisterPair(size_t* next_use, size_t starting_at) const { 8646c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray int reg = kNoRegister; 865840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // Pick the register pair that is used the last. 866840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 867840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (IsBlocked(i)) continue; 868840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (!IsLowRegister(i)) continue; 869840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray int high_register = GetHighForLowRegister(i); 870840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (IsBlocked(high_register)) continue; 871840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray int existing_high_register = GetHighForLowRegister(reg); 8726c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if ((reg == kNoRegister) || (next_use[i] >= next_use[reg] 873840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray && next_use[high_register] >= next_use[existing_high_register])) { 874840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray reg = i; 875840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (next_use[i] == kMaxLifetimePosition 876840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray && next_use[high_register] == kMaxLifetimePosition) { 877840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray break; 878840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 8796c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } else if (next_use[reg] <= starting_at || next_use[existing_high_register] <= starting_at) { 8806c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // If one of the current register is known to be unavailable, just unconditionally 8816c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // try a new one. 8826c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray reg = i; 883840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 884840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 885840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return reg; 886840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray} 887840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 8888826f67ad53099021f6442364348fa66729288d7Nicolas Geoffraybool RegisterAllocator::IsCallerSaveRegister(int reg) const { 8898826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray return processing_core_registers_ 8908826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray ? !codegen_->IsCoreCalleeSaveRegister(reg) 8918826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray : !codegen_->IsFloatingPointCalleeSaveRegister(reg); 8928826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray} 8938826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray 8948826f67ad53099021f6442364348fa66729288d7Nicolas Geoffrayint RegisterAllocator::FindAvailableRegister(size_t* next_use, LiveInterval* current) const { 8958826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray // We special case intervals that do not span a safepoint to try to find a caller-save 8968826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray // register if one is available. We iterate from 0 to the number of registers, 8978826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray // so if there are caller-save registers available at the end, we continue the iteration. 8988826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray bool prefers_caller_save = !current->HasWillCallSafepoint(); 8996c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray int reg = kNoRegister; 900840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 9018826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray if (IsBlocked(i)) { 9028826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray // Register cannot be used. Continue. 9038826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray continue; 9048826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray } 9058826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray 9068826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray // Best case: we found a register fully available. 9078826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray if (next_use[i] == kMaxLifetimePosition) { 9088826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray if (prefers_caller_save && !IsCallerSaveRegister(i)) { 9098826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray // We can get shorter encodings on some platforms by using 9108826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray // small register numbers. So only update the candidate if the previous 9118826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray // one was not available for the whole method. 9128826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray if (reg == kNoRegister || next_use[reg] != kMaxLifetimePosition) { 9138826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray reg = i; 9148826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray } 9158826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray // Continue the iteration in the hope of finding a caller save register. 9168826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray continue; 9178826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray } else { 9188826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray reg = i; 9198826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray // We know the register is good enough. Return it. 9208826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray break; 9218826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray } 9228826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray } 9238826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray 9248826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray // If we had no register before, take this one as a reference. 9258826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray if (reg == kNoRegister) { 926840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray reg = i; 9278826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray continue; 9288826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray } 9298826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray 9308826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray // Pick the register that is used the last. 9318826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray if (next_use[i] > next_use[reg]) { 9328826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray reg = i; 9338826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray continue; 934840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 935840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 936840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return reg; 937840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray} 938840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 9392aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko// Remove interval and its other half if any. Return iterator to the following element. 9402aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Markostatic ArenaVector<LiveInterval*>::iterator RemoveIntervalAndPotentialOtherHalf( 9412aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko ArenaVector<LiveInterval*>* intervals, ArenaVector<LiveInterval*>::iterator pos) { 9422aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko DCHECK(intervals->begin() <= pos && pos < intervals->end()); 9432aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko LiveInterval* interval = *pos; 9442aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko if (interval->IsLowInterval()) { 9452aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko DCHECK(pos + 1 < intervals->end()); 9462aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko DCHECK_EQ(*(pos + 1), interval->GetHighInterval()); 9472aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko return intervals->erase(pos, pos + 2); 9482aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko } else if (interval->IsHighInterval()) { 9492aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko DCHECK(intervals->begin() < pos); 9502aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko DCHECK_EQ(*(pos - 1), interval->GetLowInterval()); 9512aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko return intervals->erase(pos - 1, pos + 1); 9522aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko } else { 9532aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko return intervals->erase(pos); 9542aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko } 9552aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko} 9562aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko 957234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffraybool RegisterAllocator::TrySplitNonPairOrUnalignedPairIntervalAt(size_t position, 958234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray size_t first_register_use, 959234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray size_t* next_use) { 9602aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko for (auto it = active_.begin(), end = active_.end(); it != end; ++it) { 9612aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko LiveInterval* active = *it; 9626c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(active->HasRegister()); 963234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray if (active->IsFixed()) continue; 964234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray if (active->IsHighInterval()) continue; 965234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray if (first_register_use > next_use[active->GetRegister()]) continue; 966234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray 9672e92bc2ba2446525a07f5172d1cd30ab49d26cd6Nicolas Geoffray // Split the first interval found that is either: 9682e92bc2ba2446525a07f5172d1cd30ab49d26cd6Nicolas Geoffray // 1) A non-pair interval. 9692e92bc2ba2446525a07f5172d1cd30ab49d26cd6Nicolas Geoffray // 2) A pair interval whose high is not low + 1. 9702e92bc2ba2446525a07f5172d1cd30ab49d26cd6Nicolas Geoffray // 3) A pair interval whose low is not even. 9712e92bc2ba2446525a07f5172d1cd30ab49d26cd6Nicolas Geoffray if (!active->IsLowInterval() || 9722e92bc2ba2446525a07f5172d1cd30ab49d26cd6Nicolas Geoffray IsLowOfUnalignedPairInterval(active) || 9732e92bc2ba2446525a07f5172d1cd30ab49d26cd6Nicolas Geoffray !IsLowRegister(active->GetRegister())) { 9746c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray LiveInterval* split = Split(active, position); 9756c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (split != active) { 9762aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko handled_.push_back(active); 9776c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 9782aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko RemoveIntervalAndPotentialOtherHalf(&active_, it); 9796c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray AddSorted(unhandled_, split); 9806c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray return true; 9816c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 9826c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 9836c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray return false; 9846c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray} 9856c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray 986a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// Find the register that is used the last, and spill the interval 987a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// that holds it. If the first use of `current` is after that register 988a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// we spill `current` instead. 989a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) { 990a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t first_register_use = current->FirstRegisterUse(); 991da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray if (current->HasRegister()) { 992da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray DCHECK(current->IsHighInterval()); 993da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray // The low interval has allocated the register for the high interval. In 994da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray // case the low interval had to split both intervals, we may end up in a 995da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray // situation where the high interval does not have a register use anymore. 996da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray // We must still proceed in order to split currently active and inactive 997da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray // uses of the high interval's register, and put the high interval in the 998da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray // active set. 999da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray DCHECK(first_register_use != kNoLifetime || (current->GetNextSibling() != nullptr)); 1000da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray } else if (first_register_use == kNoLifetime) { 100131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray AllocateSpillSlotFor(current); 1002a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 1003a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1004a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1005a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // First set all registers as not being used. 1006a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t* next_use = registers_array_; 1007a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 1008a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray next_use[i] = kMaxLifetimePosition; 1009a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1010a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1011a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each active interval, find the next use of its register after the 1012a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // start of current. 10132aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko for (LiveInterval* active : active_) { 1014a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(active->HasRegister()); 101586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (active->IsFixed()) { 101686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[active->GetRegister()] = current->GetStart(); 101786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 1018119a885ff58f158a4e3cd783c5604ae4252a08ebNicolas Geoffray size_t use = active->FirstRegisterUseAfter(current->GetStart()); 101986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (use != kNoLifetime) { 102086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[active->GetRegister()] = use; 102186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 1022a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1023a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1024a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1025a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each inactive interval, find the next use of its register after the 1026a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // start of current. 10272aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko for (LiveInterval* inactive : inactive_) { 1028296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Temp/Slow-path-safepoint interval has no holes. 1029296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK(!inactive->IsTemp() && !inactive->IsSlowPathSafepoint()); 1030296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang if (!current->IsSplit() && !inactive->IsFixed()) { 1031296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Neither current nor inactive are fixed. 1032296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Thanks to SSA, a non-split interval starting in a hole of an 1033296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // inactive interval should never intersect with that inactive interval. 1034296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Only if it's not fixed though, because fixed intervals don't come from SSA. 1035296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime); 1036296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang continue; 1037296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 1038a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(inactive->HasRegister()); 103986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t next_intersection = inactive->FirstIntersectionWith(current); 104086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (next_intersection != kNoLifetime) { 104186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (inactive->IsFixed()) { 104286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[inactive->GetRegister()] = 104386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray std::min(next_intersection, next_use[inactive->GetRegister()]); 104486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 10451ba1981ee9d28f87f594b157566d09e973fa5bceNicolas Geoffray size_t use = inactive->FirstUseAfter(current->GetStart()); 104686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (use != kNoLifetime) { 104786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[inactive->GetRegister()] = std::min(use, next_use[inactive->GetRegister()]); 104886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 104986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 1050a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1051a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1052a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 10536c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray int reg = kNoRegister; 10546c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray bool should_spill = false; 1055840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (current->HasRegister()) { 1056840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(current->IsHighInterval()); 1057840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray reg = current->GetRegister(); 10586c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // When allocating the low part, we made sure the high register was available. 1059119a885ff58f158a4e3cd783c5604ae4252a08ebNicolas Geoffray DCHECK_LT(first_register_use, next_use[reg]); 1060840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (current->IsLowInterval()) { 1061119a885ff58f158a4e3cd783c5604ae4252a08ebNicolas Geoffray reg = FindAvailableRegisterPair(next_use, first_register_use); 10626c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // We should spill if both registers are not available. 1063119a885ff58f158a4e3cd783c5604ae4252a08ebNicolas Geoffray should_spill = (first_register_use >= next_use[reg]) 1064119a885ff58f158a4e3cd783c5604ae4252a08ebNicolas Geoffray || (first_register_use >= next_use[GetHighForLowRegister(reg)]); 1065840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else { 1066840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(!current->IsHighInterval()); 10678826f67ad53099021f6442364348fa66729288d7Nicolas Geoffray reg = FindAvailableRegister(next_use, current); 1068119a885ff58f158a4e3cd783c5604ae4252a08ebNicolas Geoffray should_spill = (first_register_use >= next_use[reg]); 1069a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1070a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 10716c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK_NE(reg, kNoRegister); 10726c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (should_spill) { 1073840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(!current->IsHighInterval()); 1074234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray bool is_allocation_at_use_site = (current->GetStart() >= (first_register_use - 1)); 1075da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray if (is_allocation_at_use_site) { 1076da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray if (!current->IsLowInterval()) { 1077da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray DumpInterval(std::cerr, current); 1078da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray DumpAllIntervals(std::cerr); 1079da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray // This situation has the potential to infinite loop, so we make it a non-debug CHECK. 1080da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray HInstruction* at = liveness_.GetInstructionFromPosition(first_register_use / 2); 1081da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray CHECK(false) << "There is not enough registers available for " 1082da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray << current->GetParent()->GetDefinedBy()->DebugName() << " " 1083da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray << current->GetParent()->GetDefinedBy()->GetId() 1084da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray << " at " << first_register_use - 1 << " " 1085da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray << (at == nullptr ? "" : at->DebugName()); 1086da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray } 1087da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray 10886c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // If we're allocating a register for `current` because the instruction at 10896c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // that position requires it, but we think we should spill, then there are 1090234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray // non-pair intervals or unaligned pair intervals blocking the allocation. 1091234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray // We split the first interval found, and put ourselves first in the 1092234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray // `unhandled_` list. 1093da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray bool success = TrySplitNonPairOrUnalignedPairIntervalAt(current->GetStart(), 1094da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray first_register_use, 1095da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray next_use); 1096da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray DCHECK(success); 10972aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko LiveInterval* existing = unhandled_->back(); 10986c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(existing->IsHighInterval()); 10996c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK_EQ(existing->GetLowInterval(), current); 11002aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko unhandled_->push_back(current); 11016c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } else { 11026c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // If the first use of that instruction is after the last use of the found 11036c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // register, we split this interval just before its first register use. 11046c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray AllocateSpillSlotFor(current); 11058cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray LiveInterval* split = SplitBetween(current, current->GetStart(), first_register_use - 1); 1106da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray DCHECK(current != split); 11076c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray AddSorted(unhandled_, split); 11086c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 1109a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 1110a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 1111a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Use this register and spill the active and inactives interval that 1112a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // have that register. 1113a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray current->SetRegister(reg); 1114a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 11152aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko for (auto it = active_.begin(), end = active_.end(); it != end; ++it) { 11162aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko LiveInterval* active = *it; 1117a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (active->GetRegister() == reg) { 111886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(!active->IsFixed()); 1119a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* split = Split(active, current->GetStart()); 1120dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray if (split != active) { 11212aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko handled_.push_back(active); 1122dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray } 11232aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko RemoveIntervalAndPotentialOtherHalf(&active_, it); 11243946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 1125a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray break; 1126a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1127a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1128a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 11292aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko // NOTE: Retrieve end() on each iteration because we're removing elements in the loop body. 11302aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko for (auto it = inactive_.begin(); it != inactive_.end(); ) { 11312aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko LiveInterval* inactive = *it; 11322aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko bool erased = false; 1133a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (inactive->GetRegister() == reg) { 1134296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang if (!current->IsSplit() && !inactive->IsFixed()) { 1135296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Neither current nor inactive are fixed. 1136296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Thanks to SSA, a non-split interval starting in a hole of an 1137296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // inactive interval should never intersect with that inactive interval. 1138296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Only if it's not fixed though, because fixed intervals don't come from SSA. 1139296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime); 11402aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko } else { 11412aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko size_t next_intersection = inactive->FirstIntersectionWith(current); 11422aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko if (next_intersection != kNoLifetime) { 11432aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko if (inactive->IsFixed()) { 11442aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko LiveInterval* split = Split(current, next_intersection); 11452aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko DCHECK_NE(split, current); 11462aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko AddSorted(unhandled_, split); 11472aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko } else { 11482aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko // Split at the start of `current`, which will lead to splitting 11492aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko // at the end of the lifetime hole of `inactive`. 11502aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko LiveInterval* split = Split(inactive, current->GetStart()); 11512aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko // If it's inactive, it must start before the current interval. 11522aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko DCHECK_NE(split, inactive); 11532aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko it = RemoveIntervalAndPotentialOtherHalf(&inactive_, it); 11542aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko erased = true; 11552aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko handled_.push_back(inactive); 11562aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko AddSorted(unhandled_, split); 11575b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray } 115886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 115986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 1160a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 11612aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko // If we have erased the element, `it` already points to the next element. 11622aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko // Otherwise we need to move to the next element. 11632aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko if (!erased) { 11642aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko ++it; 11652aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko } 1166a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1167a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1168a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 1169a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1170a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 1171a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 11722aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Markovoid RegisterAllocator::AddSorted(ArenaVector<LiveInterval*>* array, LiveInterval* interval) { 1173c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray DCHECK(!interval->IsFixed() && !interval->HasSpillSlot()); 117486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t insert_at = 0; 11752aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko for (size_t i = array->size(); i > 0; --i) { 11762aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko LiveInterval* current = (*array)[i - 1u]; 11776c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // High intervals must be processed right after their low equivalent. 11786c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (current->StartsAfter(interval) && !current->IsHighInterval()) { 117986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray insert_at = i; 1180a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray break; 1181acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray } else if ((current->GetStart() == interval->GetStart()) && current->IsSlowPathSafepoint()) { 1182acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray // Ensure the slow path interval is the last to be processed at its location: we want the 1183acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray // interval to know all live registers at this location. 11842aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko DCHECK(i == 1 || (*array)[i - 2u]->StartsAfter(current)); 1185acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray insert_at = i; 1186acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray break; 1187a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1188a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1189840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 1190840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // Insert the high interval before the low, to ensure the low is processed before. 11912aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko auto insert_pos = array->begin() + insert_at; 1192840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (interval->HasHighInterval()) { 11932aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko array->insert(insert_pos, { interval->GetHighInterval(), interval }); 1194840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (interval->HasLowInterval()) { 11952aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko array->insert(insert_pos, { interval, interval->GetLowInterval() }); 11962aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko } else { 11972aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko array->insert(insert_pos, interval); 1198840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 1199a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 1200a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 12018cbab3c4de3328b576454ce702d7748f56c44346Nicolas GeoffrayLiveInterval* RegisterAllocator::SplitBetween(LiveInterval* interval, size_t from, size_t to) { 1202fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray HBasicBlock* block_from = liveness_.GetBlockFromPosition(from / 2); 1203fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray HBasicBlock* block_to = liveness_.GetBlockFromPosition(to / 2); 12048cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray DCHECK(block_from != nullptr); 12058cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray DCHECK(block_to != nullptr); 12068cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray 12078cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray // Both locations are in the same block. We split at the given location. 12088cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray if (block_from == block_to) { 12098cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray return Split(interval, to); 12108cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray } 12118cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray 1212fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray /* 1213fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * Non-linear control flow will force moves at every branch instruction to the new location. 1214fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * To avoid having all branches doing the moves, we find the next non-linear position and 1215fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * split the interval at this position. Take the following example (block number is the linear 1216fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * order position): 1217fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * 1218fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * B1 1219fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * / \ 1220fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * B2 B3 1221fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * \ / 1222fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * B4 1223fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * 1224fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * B2 needs to split an interval, whose next use is in B4. If we were to split at the 1225fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * beginning of B4, B3 would need to do a move between B3 and B4 to ensure the interval 1226fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * is now in the correct location. It makes performance worst if the interval is spilled 1227fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * and both B2 and B3 need to reload it before entering B4. 1228fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * 1229fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * By splitting at B3, we give a chance to the register allocator to allocate the 1230fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * interval to the same register as in B1, and therefore avoid doing any 1231fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * moves in B3. 1232fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray */ 1233fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray if (block_from->GetDominator() != nullptr) { 12346058455d486219994921b63a2d774dc9908415a2Vladimir Marko for (HBasicBlock* dominated : block_from->GetDominator()->GetDominatedBlocks()) { 12356058455d486219994921b63a2d774dc9908415a2Vladimir Marko size_t position = dominated->GetLifetimeStart(); 1236fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray if ((position > from) && (block_to->GetLifetimeStart() > position)) { 1237fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray // Even if we found a better block, we continue iterating in case 1238fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray // a dominated block is closer. 1239fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray // Note that dominated blocks are not sorted in liveness order. 12406058455d486219994921b63a2d774dc9908415a2Vladimir Marko block_to = dominated; 1241fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray DCHECK_NE(block_to, block_from); 1242fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray } 1243fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray } 1244fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray } 1245fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray 12468cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray // If `to` is in a loop, find the outermost loop header which does not contain `from`. 12478cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray for (HLoopInformationOutwardIterator it(*block_to); !it.Done(); it.Advance()) { 12488cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray HBasicBlock* header = it.Current()->GetHeader(); 12498cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray if (block_from->GetLifetimeStart() >= header->GetLifetimeStart()) { 12508cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray break; 12518cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray } 12528cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray block_to = header; 12538cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray } 12548cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray 12558cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray // Split at the start of the found block, to piggy back on existing moves 12568cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray // due to resolution if non-linear control flow (see `ConnectSplitSiblings`). 12578cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray return Split(interval, block_to->GetLifetimeStart()); 12588cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray} 12598cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray 1260a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas GeoffrayLiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) { 1261840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK_GE(position, interval->GetStart()); 1262a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(!interval->IsDeadAt(position)); 1263a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (position == interval->GetStart()) { 1264a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Spill slot will be allocated when handling `interval` again. 1265a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray interval->ClearRegister(); 1266840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (interval->HasHighInterval()) { 1267840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray interval->GetHighInterval()->ClearRegister(); 1268840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (interval->HasLowInterval()) { 1269840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray interval->GetLowInterval()->ClearRegister(); 1270840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 1271a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return interval; 1272a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 1273a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* new_interval = interval->SplitAt(position); 1274840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (interval->HasHighInterval()) { 1275840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray LiveInterval* high = interval->GetHighInterval()->SplitAt(position); 1276840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray new_interval->SetHighInterval(high); 1277840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray high->SetLowInterval(new_interval); 1278840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (interval->HasLowInterval()) { 1279840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray LiveInterval* low = interval->GetLowInterval()->SplitAt(position); 1280840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray new_interval->SetLowInterval(low); 1281840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray low->SetHighInterval(new_interval); 1282840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 1283a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return new_interval; 1284a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1285a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 1286a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 128731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffrayvoid RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) { 1288840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (interval->IsHighInterval()) { 1289da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray // The low interval already took care of allocating the spill slot. 1290da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray DCHECK(!interval->GetLowInterval()->HasRegister()); 1291da2b254fe4c35986d85876c5819b1114e25140cbNicolas Geoffray DCHECK(interval->GetLowInterval()->GetParent()->HasSpillSlot()); 1292840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return; 1293840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 1294840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 129531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* parent = interval->GetParent(); 129631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 129731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // An instruction gets a spill slot for its entire lifetime. If the parent 129831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // of this interval already has a spill slot, there is nothing to do. 129931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (parent->HasSpillSlot()) { 130031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray return; 130131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 130231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 130386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* defined_by = parent->GetDefinedBy(); 130477a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil DCHECK(!defined_by->IsPhi() || !defined_by->AsPhi()->IsCatchPhi()); 130577a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil 130686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (defined_by->IsParameterValue()) { 130786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Parameters have their own stack slot. 130886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray parent->SetSpillSlot(codegen_->GetStackSlotOfParameter(defined_by->AsParameterValue())); 130986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 131086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 131186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 131276b1e1799a713a19218de26b171b0aef48a59e98Nicolas Geoffray if (defined_by->IsCurrentMethod()) { 131376b1e1799a713a19218de26b171b0aef48a59e98Nicolas Geoffray parent->SetSpillSlot(0); 131476b1e1799a713a19218de26b171b0aef48a59e98Nicolas Geoffray return; 131576b1e1799a713a19218de26b171b0aef48a59e98Nicolas Geoffray } 131676b1e1799a713a19218de26b171b0aef48a59e98Nicolas Geoffray 131796f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray if (defined_by->IsConstant()) { 131896f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray // Constants don't need a spill slot. 131996f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray return; 132096f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray } 132196f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray 13222aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko ArenaVector<size_t>* spill_slots = nullptr; 1323776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray switch (interval->GetType()) { 1324776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimDouble: 1325776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots = &double_spill_slots_; 1326776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray break; 1327776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimLong: 1328776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots = &long_spill_slots_; 1329776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray break; 1330776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimFloat: 1331776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots = &float_spill_slots_; 1332776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray break; 1333776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimNot: 1334776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimInt: 1335776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimChar: 1336776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimByte: 1337776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimBoolean: 1338776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimShort: 1339776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots = &int_spill_slots_; 1340776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray break; 1341776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimVoid: 1342776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray LOG(FATAL) << "Unexpected type for interval " << interval->GetType(); 1343776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray } 1344776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray 1345412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // Find an available spill slot. 1346412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray size_t slot = 0; 13472aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko for (size_t e = spill_slots->size(); slot < e; ++slot) { 13482aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko if ((*spill_slots)[slot] <= parent->GetStart() 13492aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko && (slot == (e - 1) || (*spill_slots)[slot + 1] <= parent->GetStart())) { 1350412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray break; 1351412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } 1352412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } 1353412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray 135477a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil size_t end = interval->GetLastSibling()->GetEnd(); 135501ef345767ea609417fc511e42007705c9667546Nicolas Geoffray if (parent->NeedsTwoSpillSlots()) { 13562aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko if (slot + 2u > spill_slots->size()) { 13573c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray // We need a new spill slot. 13582aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko spill_slots->resize(slot + 2u, end); 135931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 13602aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko (*spill_slots)[slot] = end; 13612aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko (*spill_slots)[slot + 1] = end; 136231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 13632aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko if (slot == spill_slots->size()) { 13643c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray // We need a new spill slot. 13652aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko spill_slots->push_back(end); 13663c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray } else { 13672aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko (*spill_slots)[slot] = end; 13683c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray } 136931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 137031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 1371776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // Note that the exact spill slot location will be computed when we resolve, 1372776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // that is when we know the number of spill slots for each type. 1373776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray parent->SetSpillSlot(slot); 137486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 137586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 13762a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffraystatic bool IsValidDestination(Location destination) { 1377102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return destination.IsRegister() 13786c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray || destination.IsRegisterPair() 1379102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray || destination.IsFpuRegister() 1380840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray || destination.IsFpuRegisterPair() 1381102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray || destination.IsStackSlot() 1382102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray || destination.IsDoubleStackSlot(); 13832a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray} 13842a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray 138577a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdilvoid RegisterAllocator::AllocateSpillSlotForCatchPhi(HPhi* phi) { 138677a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil LiveInterval* interval = phi->GetLiveInterval(); 138777a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil 138877a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil HInstruction* previous_phi = phi->GetPrevious(); 138977a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil DCHECK(previous_phi == nullptr || 139077a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil previous_phi->AsPhi()->GetRegNumber() <= phi->GetRegNumber()) 139177a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil << "Phis expected to be sorted by vreg number, so that equivalent phis are adjacent."; 139277a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil 139377a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil if (phi->IsVRegEquivalentOf(previous_phi)) { 139477a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil // This is an equivalent of the previous phi. We need to assign the same 139577a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil // catch phi slot. 139677a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil DCHECK(previous_phi->GetLiveInterval()->HasSpillSlot()); 139777a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil interval->SetSpillSlot(previous_phi->GetLiveInterval()->GetSpillSlot()); 139877a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil } else { 139977a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil // Allocate a new spill slot for this catch phi. 140077a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil // TODO: Reuse spill slots when intervals of phis from different catch 140177a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil // blocks do not overlap. 140277a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil interval->SetSpillSlot(catch_phi_spill_slots_); 140377a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil catch_phi_spill_slots_ += interval->NeedsTwoSpillSlots() ? 2 : 1; 140477a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil } 140577a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil} 140677a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil 1407234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffrayvoid RegisterAllocator::AddMove(HParallelMove* move, 1408234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray Location source, 1409234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray Location destination, 1410234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray HInstruction* instruction, 1411234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray Primitive::Type type) const { 1412234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray if (type == Primitive::kPrimLong 1413234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray && codegen_->ShouldSplitLongMoves() 1414234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray // The parallel move resolver knows how to deal with long constants. 1415234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray && !source.IsConstant()) { 14169021825d1e73998b99c81e89c73796f6f2845471Nicolas Geoffray move->AddMove(source.ToLow(), destination.ToLow(), Primitive::kPrimInt, instruction); 14179021825d1e73998b99c81e89c73796f6f2845471Nicolas Geoffray move->AddMove(source.ToHigh(), destination.ToHigh(), Primitive::kPrimInt, nullptr); 1418234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray } else { 14199021825d1e73998b99c81e89c73796f6f2845471Nicolas Geoffray move->AddMove(source, destination, type, instruction); 1420234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray } 1421234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray} 1422234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray 1423234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffrayvoid RegisterAllocator::AddInputMoveFor(HInstruction* input, 1424234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray HInstruction* user, 142586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 142686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 142786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 142886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1429476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain DCHECK(!user->IsPhi()); 143086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1431740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray HInstruction* previous = user->GetPrevious(); 143286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move = nullptr; 143386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (previous == nullptr 1434476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain || !previous->IsParallelMove() 14358e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray || previous->GetLifetimePosition() < user->GetLifetimePosition()) { 143686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 14378e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray move->SetLifetimePosition(user->GetLifetimePosition()); 1438740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray user->GetBlock()->InsertInstructionBefore(move, user); 143986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 144086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = previous->AsParallelMove(); 144186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 14428e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray DCHECK_EQ(move->GetLifetimePosition(), user->GetLifetimePosition()); 1443234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray AddMove(move, source, destination, nullptr, input->GetType()); 144486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 144586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 144646fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffraystatic bool IsInstructionStart(size_t position) { 144746fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray return (position & 1) == 0; 144846fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray} 144946fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray 145046fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffraystatic bool IsInstructionEnd(size_t position) { 145146fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray return (position & 1) == 1; 145246fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray} 145346fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray 145486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertParallelMoveAt(size_t position, 1455740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray HInstruction* instruction, 145686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 145786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 14586c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(IsValidDestination(destination)) << destination; 145986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 146086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 146186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* at = liveness_.GetInstructionFromPosition(position / 2); 146286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move; 146346fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray if (at == nullptr) { 146446fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray if (IsInstructionStart(position)) { 146546fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray // Block boundary, don't do anything the connection of split siblings will handle it. 146646fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray return; 146746fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray } else { 146846fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray // Move must happen before the first instruction of the block. 146946fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray at = liveness_.GetInstructionFromPosition((position + 1) / 2); 14705976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // Note that parallel moves may have already been inserted, so we explicitly 14715976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // ask for the first instruction of the block: `GetInstructionFromPosition` does 1472234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray // not contain the `HParallelMove` instructions. 14735976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray at = at->GetBlock()->GetFirstInstruction(); 1474234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray 1475234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray if (at->GetLifetimePosition() < position) { 1476234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray // We may insert moves for split siblings and phi spills at the beginning of the block. 1477234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray // Since this is a different lifetime position, we need to go to the next instruction. 1478234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray DCHECK(at->IsParallelMove()); 1479234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray at = at->GetNext(); 1480234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray } 1481234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray 14825976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray if (at->GetLifetimePosition() != position) { 14835976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray DCHECK_GT(at->GetLifetimePosition(), position); 148446fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 148546fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray move->SetLifetimePosition(position); 148646fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray at->GetBlock()->InsertInstructionBefore(move, at); 14875976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray } else { 14885976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray DCHECK(at->IsParallelMove()); 14895976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray move = at->AsParallelMove(); 149046fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray } 149146fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray } 149246fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray } else if (IsInstructionEnd(position)) { 149386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Move must happen after the instruction. 149486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(!at->IsControlFlow()); 149586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = at->GetNext()->AsParallelMove(); 1496e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting siblings in a same block. We need to 1497e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // differentiate it with moves for connecting blocks, and input moves. 14988e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray if (move == nullptr || move->GetLifetimePosition() > position) { 149986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 150086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->SetLifetimePosition(position); 150186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray at->GetBlock()->InsertInstructionBefore(move, at->GetNext()); 150286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 150386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 150486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Move must happen before the instruction. 150586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* previous = at->GetPrevious(); 1506740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray if (previous == nullptr 1507740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray || !previous->IsParallelMove() 1508740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray || previous->GetLifetimePosition() != position) { 1509740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray // If the previous is a parallel move, then its position must be lower 1510740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray // than the given `position`: it was added just after the non-parallel 1511740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray // move instruction that precedes `instruction`. 1512740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray DCHECK(previous == nullptr 1513740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray || !previous->IsParallelMove() 1514740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray || previous->GetLifetimePosition() < position); 151586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 151686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->SetLifetimePosition(position); 151786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray at->GetBlock()->InsertInstructionBefore(move, at); 151886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 151986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = previous->AsParallelMove(); 152086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 152186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 152201ef345767ea609417fc511e42007705c9667546Nicolas Geoffray DCHECK_EQ(move->GetLifetimePosition(), position); 1523234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray AddMove(move, source, destination, instruction, instruction->GetType()); 152486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 152586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 152686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertParallelMoveAtExitOf(HBasicBlock* block, 1527740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray HInstruction* instruction, 152886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 152986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 15306c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(IsValidDestination(destination)) << destination; 153186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 153286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1533d26a411adee1e71b3f09dd604ab9b23018037138David Brazdil DCHECK_EQ(block->GetNormalSuccessors().size(), 1u); 153486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* last = block->GetLastInstruction(); 1535360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray // We insert moves at exit for phi predecessors and connecting blocks. 1536fe57faa2e0349418dda38e77ef1c0ac29db75f4dMark Mendell // A block ending with an if or a packed switch cannot branch to a block 1537fe57faa2e0349418dda38e77ef1c0ac29db75f4dMark Mendell // with phis because we do not allow critical edges. It can also not connect 1538360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray // a split interval between two blocks: the move has to happen in the successor. 1539fe57faa2e0349418dda38e77ef1c0ac29db75f4dMark Mendell DCHECK(!last->IsIf() && !last->IsPackedSwitch()); 154086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* previous = last->GetPrevious(); 154186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move; 1542e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting blocks. We need to differentiate 1543e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // it with moves for connecting siblings in a same block, and output moves. 15445976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray size_t position = last->GetLifetimePosition(); 1545740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray if (previous == nullptr || !previous->IsParallelMove() 15465976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray || previous->AsParallelMove()->GetLifetimePosition() != position) { 154786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 15485976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray move->SetLifetimePosition(position); 154986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray block->InsertInstructionBefore(move, last); 155086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 155186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = previous->AsParallelMove(); 155286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 1553234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray AddMove(move, source, destination, instruction, instruction->GetType()); 155486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 155586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 155686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertParallelMoveAtEntryOf(HBasicBlock* block, 1557740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray HInstruction* instruction, 155886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 155986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 15606c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(IsValidDestination(destination)) << destination; 156186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 156286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 156386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* first = block->GetFirstInstruction(); 156486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move = first->AsParallelMove(); 1565234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray size_t position = block->GetLifetimeStart(); 1566e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting blocks. We need to differentiate 1567e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // it with moves for connecting siblings in a same block, and input moves. 1568234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray if (move == nullptr || move->GetLifetimePosition() != position) { 156986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 1570234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray move->SetLifetimePosition(position); 157186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray block->InsertInstructionBefore(move, first); 157286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 1573234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray AddMove(move, source, destination, instruction, instruction->GetType()); 157486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 157586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 157686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertMoveAfter(HInstruction* instruction, 157786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 157886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 15796c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(IsValidDestination(destination)) << destination; 158086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 158186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1582476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain if (instruction->IsPhi()) { 1583740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAtEntryOf(instruction->GetBlock(), instruction, source, destination); 158486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 158586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 158686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1587e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray size_t position = instruction->GetLifetimePosition() + 1; 158886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move = instruction->GetNext()->AsParallelMove(); 1589e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for moving the output of an instruction. We need 1590e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // to differentiate with input moves, moves for connecting siblings in a 1591e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // and moves for connecting blocks. 1592e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray if (move == nullptr || move->GetLifetimePosition() != position) { 159386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 1594e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray move->SetLifetimePosition(position); 159586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray instruction->GetBlock()->InsertInstructionBefore(move, instruction->GetNext()); 159686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 1597234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray AddMove(move, source, destination, instruction, instruction->GetType()); 159886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 159986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 160086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::ConnectSiblings(LiveInterval* interval) { 160186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = interval; 160276b1e1799a713a19218de26b171b0aef48a59e98Nicolas Geoffray if (current->HasSpillSlot() 160376b1e1799a713a19218de26b171b0aef48a59e98Nicolas Geoffray && current->HasRegister() 160476b1e1799a713a19218de26b171b0aef48a59e98Nicolas Geoffray // Currently, we spill unconditionnally the current method in the code generators. 160576b1e1799a713a19218de26b171b0aef48a59e98Nicolas Geoffray && !interval->GetDefinedBy()->IsCurrentMethod()) { 160686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // We spill eagerly, so move must be at definition. 160786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InsertMoveAfter(interval->GetDefinedBy(), 1608840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray interval->ToLocation(), 160901ef345767ea609417fc511e42007705c9667546Nicolas Geoffray interval->NeedsTwoSpillSlots() 1610412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray ? Location::DoubleStackSlot(interval->GetParent()->GetSpillSlot()) 1611412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray : Location::StackSlot(interval->GetParent()->GetSpillSlot())); 161286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 161386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray UsePosition* use = current->GetFirstUse(); 16144ed947a58de87d19d0609be773207c905ccb0f7fNicolas Geoffray UsePosition* env_use = current->GetFirstEnvironmentUse(); 161586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 161686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Walk over all siblings, updating locations of use positions, and 161786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // connecting them when they are adjacent. 161886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray do { 161901ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location source = current->ToLocation(); 162086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 162186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Walk over all uses covered by this interval, and update the location 162286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // information. 1623d8126bef62df7f40f2e6abc74004f52e664daf45Nicolas Geoffray 1624d8126bef62df7f40f2e6abc74004f52e664daf45Nicolas Geoffray LiveRange* range = current->GetFirstRange(); 1625d8126bef62df7f40f2e6abc74004f52e664daf45Nicolas Geoffray while (range != nullptr) { 1626579026039080252878106118645ed70706f4838eNicolas Geoffray while (use != nullptr && use->GetPosition() < range->GetStart()) { 1627579026039080252878106118645ed70706f4838eNicolas Geoffray DCHECK(use->IsSynthesized()); 1628579026039080252878106118645ed70706f4838eNicolas Geoffray use = use->GetNext(); 1629579026039080252878106118645ed70706f4838eNicolas Geoffray } 1630d8126bef62df7f40f2e6abc74004f52e664daf45Nicolas Geoffray while (use != nullptr && use->GetPosition() <= range->GetEnd()) { 16314ed947a58de87d19d0609be773207c905ccb0f7fNicolas Geoffray DCHECK(!use->GetIsEnvironment()); 16323fc992f9dfe8f49ff350132323cc635f102b7b62David Brazdil DCHECK(current->CoversSlow(use->GetPosition()) || (use->GetPosition() == range->GetEnd())); 1633579026039080252878106118645ed70706f4838eNicolas Geoffray if (!use->IsSynthesized()) { 1634579026039080252878106118645ed70706f4838eNicolas Geoffray LocationSummary* locations = use->GetUser()->GetLocations(); 1635579026039080252878106118645ed70706f4838eNicolas Geoffray Location expected_location = locations->InAt(use->GetInputIndex()); 1636579026039080252878106118645ed70706f4838eNicolas Geoffray // The expected (actual) location may be invalid in case the input is unused. Currently 1637579026039080252878106118645ed70706f4838eNicolas Geoffray // this only happens for intrinsics. 1638579026039080252878106118645ed70706f4838eNicolas Geoffray if (expected_location.IsValid()) { 1639579026039080252878106118645ed70706f4838eNicolas Geoffray if (expected_location.IsUnallocated()) { 1640579026039080252878106118645ed70706f4838eNicolas Geoffray locations->SetInAt(use->GetInputIndex(), source); 1641579026039080252878106118645ed70706f4838eNicolas Geoffray } else if (!expected_location.IsConstant()) { 1642579026039080252878106118645ed70706f4838eNicolas Geoffray AddInputMoveFor(interval->GetDefinedBy(), use->GetUser(), source, expected_location); 1643579026039080252878106118645ed70706f4838eNicolas Geoffray } 1644579026039080252878106118645ed70706f4838eNicolas Geoffray } else { 1645579026039080252878106118645ed70706f4838eNicolas Geoffray DCHECK(use->GetUser()->IsInvoke()); 1646579026039080252878106118645ed70706f4838eNicolas Geoffray DCHECK(use->GetUser()->AsInvoke()->GetIntrinsic() != Intrinsics::kNone); 1647d8126bef62df7f40f2e6abc74004f52e664daf45Nicolas Geoffray } 164886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 1649d8126bef62df7f40f2e6abc74004f52e664daf45Nicolas Geoffray use = use->GetNext(); 165086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 16514ed947a58de87d19d0609be773207c905ccb0f7fNicolas Geoffray 16524ed947a58de87d19d0609be773207c905ccb0f7fNicolas Geoffray // Walk over the environment uses, and update their locations. 16534ed947a58de87d19d0609be773207c905ccb0f7fNicolas Geoffray while (env_use != nullptr && env_use->GetPosition() < range->GetStart()) { 16544ed947a58de87d19d0609be773207c905ccb0f7fNicolas Geoffray env_use = env_use->GetNext(); 16554ed947a58de87d19d0609be773207c905ccb0f7fNicolas Geoffray } 16564ed947a58de87d19d0609be773207c905ccb0f7fNicolas Geoffray 16574ed947a58de87d19d0609be773207c905ccb0f7fNicolas Geoffray while (env_use != nullptr && env_use->GetPosition() <= range->GetEnd()) { 16580a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray DCHECK(current->CoversSlow(env_use->GetPosition()) 16590a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray || (env_use->GetPosition() == range->GetEnd())); 1660d23eeef3492b53102eb8093524cf37e2b4c296dbNicolas Geoffray HEnvironment* environment = env_use->GetEnvironment(); 16610a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray environment->SetLocationAt(env_use->GetInputIndex(), source); 16624ed947a58de87d19d0609be773207c905ccb0f7fNicolas Geoffray env_use = env_use->GetNext(); 16634ed947a58de87d19d0609be773207c905ccb0f7fNicolas Geoffray } 16644ed947a58de87d19d0609be773207c905ccb0f7fNicolas Geoffray 1665d8126bef62df7f40f2e6abc74004f52e664daf45Nicolas Geoffray range = range->GetNext(); 166686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 166786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 166886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // If the next interval starts just after this one, and has a register, 166986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // insert a move. 167086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* next_sibling = current->GetNextSibling(); 167186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (next_sibling != nullptr 167286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && next_sibling->HasRegister() 167386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && current->GetEnd() == next_sibling->GetStart()) { 167401ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location destination = next_sibling->ToLocation(); 1675740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAt(current->GetEnd(), interval->GetDefinedBy(), source, destination); 167686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 16773946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 167843af728a3ccecb5f0eacef85f44d70df3d4c40f9Nicolas Geoffray for (SafepointPosition* safepoint_position = current->GetFirstSafepoint(); 167943af728a3ccecb5f0eacef85f44d70df3d4c40f9Nicolas Geoffray safepoint_position != nullptr; 168043af728a3ccecb5f0eacef85f44d70df3d4c40f9Nicolas Geoffray safepoint_position = safepoint_position->GetNext()) { 16813fc992f9dfe8f49ff350132323cc635f102b7b62David Brazdil DCHECK(current->CoversSlow(safepoint_position->GetPosition())); 16823946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 16835588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray LocationSummary* locations = safepoint_position->GetLocations(); 16843bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray if ((current->GetType() == Primitive::kPrimNot) && current->GetParent()->HasSpillSlot()) { 16851af564e2d3b560fb9a076eb35ea20471aed0dc92Nicolas Geoffray DCHECK(interval->GetDefinedBy()->IsActualObject()) 16861af564e2d3b560fb9a076eb35ea20471aed0dc92Nicolas Geoffray << interval->GetDefinedBy()->DebugName() 16871af564e2d3b560fb9a076eb35ea20471aed0dc92Nicolas Geoffray << "@" << safepoint_position->GetInstruction()->DebugName(); 16883946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray locations->SetStackBit(current->GetParent()->GetSpillSlot() / kVRegSize); 16893946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 16903946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 16913946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray switch (source.GetKind()) { 16923946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kRegister: { 16933bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray locations->AddLiveRegister(source); 1694988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray if (kIsDebugBuild && locations->OnlyCallsOnSlowPath()) { 1695988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray DCHECK_LE(locations->GetNumberOfLiveRegisters(), 1696988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray maximum_number_of_live_core_registers_ + 1697988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray maximum_number_of_live_fp_registers_); 1698988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray } 16993946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current->GetType() == Primitive::kPrimNot) { 1700a3eca2d7300f35c66cf4b696d788a8b7ba74eb99Nicolas Geoffray DCHECK(interval->GetDefinedBy()->IsActualObject()) 17011af564e2d3b560fb9a076eb35ea20471aed0dc92Nicolas Geoffray << interval->GetDefinedBy()->DebugName() 17021af564e2d3b560fb9a076eb35ea20471aed0dc92Nicolas Geoffray << "@" << safepoint_position->GetInstruction()->DebugName(); 170356b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray locations->SetRegisterBit(source.reg()); 17043946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 17053946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray break; 17063946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 1707102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray case Location::kFpuRegister: { 1708102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray locations->AddLiveRegister(source); 1709102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray break; 1710102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 17116c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray 17126c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray case Location::kRegisterPair: 1713840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray case Location::kFpuRegisterPair: { 1714840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray locations->AddLiveRegister(source.ToLow()); 1715840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray locations->AddLiveRegister(source.ToHigh()); 1716840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray break; 1717840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 17183946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kStackSlot: // Fall-through 17193946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kDoubleStackSlot: // Fall-through 17203946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kConstant: { 17213946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Nothing to do. 17223946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray break; 17233946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 17243946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray default: { 17253946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LOG(FATAL) << "Unexpected location for object"; 17263946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 17273946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 17283946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 172986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current = next_sibling; 173086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } while (current != nullptr); 1731d8126bef62df7f40f2e6abc74004f52e664daf45Nicolas Geoffray 1732579026039080252878106118645ed70706f4838eNicolas Geoffray if (kIsDebugBuild) { 1733579026039080252878106118645ed70706f4838eNicolas Geoffray // Following uses can only be synthesized uses. 1734579026039080252878106118645ed70706f4838eNicolas Geoffray while (use != nullptr) { 1735579026039080252878106118645ed70706f4838eNicolas Geoffray DCHECK(use->IsSynthesized()); 1736579026039080252878106118645ed70706f4838eNicolas Geoffray use = use->GetNext(); 1737579026039080252878106118645ed70706f4838eNicolas Geoffray } 1738579026039080252878106118645ed70706f4838eNicolas Geoffray } 173986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 174086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 174104eb70f0282703a150e3e2c7e5b3f678fec25397Nicolas Geoffraystatic bool IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop( 174204eb70f0282703a150e3e2c7e5b3f678fec25397Nicolas Geoffray HInstruction* instruction) { 174304eb70f0282703a150e3e2c7e5b3f678fec25397Nicolas Geoffray return instruction->GetBlock()->GetGraph()->HasIrreducibleLoops() && 174404eb70f0282703a150e3e2c7e5b3f678fec25397Nicolas Geoffray (instruction->IsConstant() || instruction->IsCurrentMethod()); 174504eb70f0282703a150e3e2c7e5b3f678fec25397Nicolas Geoffray} 174604eb70f0282703a150e3e2c7e5b3f678fec25397Nicolas Geoffray 174786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval, 174886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* from, 174986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* to) const { 175086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (interval->GetNextSibling() == nullptr) { 175186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Nothing to connect. The whole range was allocated to the same location. 175286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 175386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 175486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1755241a486267bdb59b32fe4c8db370eb936068fb39David Brazdil // Find the intervals that cover `from` and `to`. 1756ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray size_t destination_position = to->GetLifetimeStart(); 1757ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray size_t source_position = from->GetLifetimeEnd() - 1; 1758ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray LiveInterval* destination = interval->GetSiblingAt(destination_position); 1759ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray LiveInterval* source = interval->GetSiblingAt(source_position); 176086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 176186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (destination == source) { 176286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Interval was not split. 176386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 176486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 176504eb70f0282703a150e3e2c7e5b3f678fec25397Nicolas Geoffray 176604eb70f0282703a150e3e2c7e5b3f678fec25397Nicolas Geoffray LiveInterval* parent = interval->GetParent(); 176704eb70f0282703a150e3e2c7e5b3f678fec25397Nicolas Geoffray HInstruction* defined_by = parent->GetDefinedBy(); 1768ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray if (codegen_->GetGraph()->HasIrreducibleLoops() && 1769ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray (destination == nullptr || !destination->CoversSlow(destination_position))) { 177004eb70f0282703a150e3e2c7e5b3f678fec25397Nicolas Geoffray // Our live_in fixed point calculation has found that the instruction is live 177104eb70f0282703a150e3e2c7e5b3f678fec25397Nicolas Geoffray // in the `to` block because it will eventually enter an irreducible loop. Our 177204eb70f0282703a150e3e2c7e5b3f678fec25397Nicolas Geoffray // live interval computation however does not compute a fixed point, and 177304eb70f0282703a150e3e2c7e5b3f678fec25397Nicolas Geoffray // therefore will not have a location for that instruction for `to`. 177404eb70f0282703a150e3e2c7e5b3f678fec25397Nicolas Geoffray // Because the instruction is a constant or the ArtMethod, we don't need to 177504eb70f0282703a150e3e2c7e5b3f678fec25397Nicolas Geoffray // do anything: it will be materialized in the irreducible loop. 177677ce6430af2709432b22344ed656edd8ec80581bNicolas Geoffray DCHECK(IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop(defined_by)) 177777ce6430af2709432b22344ed656edd8ec80581bNicolas Geoffray << defined_by->DebugName() << ":" << defined_by->GetId() 177877ce6430af2709432b22344ed656edd8ec80581bNicolas Geoffray << " " << from->GetBlockId() << " -> " << to->GetBlockId(); 177904eb70f0282703a150e3e2c7e5b3f678fec25397Nicolas Geoffray return; 178004eb70f0282703a150e3e2c7e5b3f678fec25397Nicolas Geoffray } 17818ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray 178286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (!destination->HasRegister()) { 178386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Values are eagerly spilled. Spill slot already contains appropriate value. 178486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 178586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 178686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1787ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray Location location_source; 1788ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray // `GetSiblingAt` returns the interval whose start and end cover `position`, 1789ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray // but does not check whether the interval is inactive at that position. 1790ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray // The only situation where the interval is inactive at that position is in the 1791ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray // presence of irreducible loops for constants and ArtMethod. 1792ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray if (codegen_->GetGraph()->HasIrreducibleLoops() && 1793ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray (source == nullptr || !source->CoversSlow(source_position))) { 1794ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray DCHECK(IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop(defined_by)); 1795ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray if (defined_by->IsConstant()) { 1796ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray location_source = defined_by->GetLocations()->Out(); 1797ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray } else { 1798ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray DCHECK(defined_by->IsCurrentMethod()); 1799ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray location_source = parent->NeedsTwoSpillSlots() 1800ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray ? Location::DoubleStackSlot(parent->GetSpillSlot()) 1801ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray : Location::StackSlot(parent->GetSpillSlot()); 1802ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray } 1803ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray } else { 1804ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray DCHECK(source != nullptr); 1805ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray DCHECK(source->CoversSlow(source_position)); 1806ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray DCHECK(destination->CoversSlow(destination_position)); 1807ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray location_source = source->ToLocation(); 1808ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray } 1809ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray 181086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // If `from` has only one successor, we can put the moves at the exit of it. Otherwise 181186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // we need to put the moves at the entry of `to`. 1812d26a411adee1e71b3f09dd604ab9b23018037138David Brazdil if (from->GetNormalSuccessors().size() == 1) { 1813740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAtExitOf(from, 181404eb70f0282703a150e3e2c7e5b3f678fec25397Nicolas Geoffray defined_by, 1815ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray location_source, 181601ef345767ea609417fc511e42007705c9667546Nicolas Geoffray destination->ToLocation()); 181786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 18186058455d486219994921b63a2d774dc9908415a2Vladimir Marko DCHECK_EQ(to->GetPredecessors().size(), 1u); 1819740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAtEntryOf(to, 182004eb70f0282703a150e3e2c7e5b3f678fec25397Nicolas Geoffray defined_by, 1821ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray location_source, 182201ef345767ea609417fc511e42007705c9667546Nicolas Geoffray destination->ToLocation()); 182386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 182486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 182586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 182686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::Resolve() { 1827776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray codegen_->InitializeCodeGeneration(GetNumberOfSpillSlots(), 18284c204bafbc8d596894f8cb8ec696f5be1c6f12d8Nicolas Geoffray maximum_number_of_live_core_registers_, 18294c204bafbc8d596894f8cb8ec696f5be1c6f12d8Nicolas Geoffray maximum_number_of_live_fp_registers_, 18304c204bafbc8d596894f8cb8ec696f5be1c6f12d8Nicolas Geoffray reserved_out_slots_, 18310d9f17de8f21a10702de1510b73e89d07b3b9bbfNicolas Geoffray codegen_->GetGraph()->GetLinearOrder()); 183286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 183386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Adjust the Out Location of instructions. 183486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // TODO: Use pointers of Location inside LiveInterval to avoid doing another iteration. 183586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { 183686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 183786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = instruction->GetLiveInterval(); 183886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LocationSummary* locations = instruction->GetLocations(); 183986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location location = locations->Out(); 1840476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain if (instruction->IsParameterValue()) { 184186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Now that we know the frame size, adjust the parameter's location. 184286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (location.IsStackSlot()) { 184386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray location = Location::StackSlot(location.GetStackIndex() + codegen_->GetFrameSize()); 184486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(location.GetStackIndex()); 1845f43083d560565aea46c602adb86423daeefe589dNicolas Geoffray locations->UpdateOut(location); 184686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else if (location.IsDoubleStackSlot()) { 184786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray location = Location::DoubleStackSlot(location.GetStackIndex() + codegen_->GetFrameSize()); 184886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(location.GetStackIndex()); 1849f43083d560565aea46c602adb86423daeefe589dNicolas Geoffray locations->UpdateOut(location); 185086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else if (current->HasSpillSlot()) { 185186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(current->GetSpillSlot() + codegen_->GetFrameSize()); 185286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 185376b1e1799a713a19218de26b171b0aef48a59e98Nicolas Geoffray } else if (instruction->IsCurrentMethod()) { 185476b1e1799a713a19218de26b171b0aef48a59e98Nicolas Geoffray // The current method is always at offset 0. 185576b1e1799a713a19218de26b171b0aef48a59e98Nicolas Geoffray DCHECK(!current->HasSpillSlot() || (current->GetSpillSlot() == 0)); 185677a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil } else if (instruction->IsPhi() && instruction->AsPhi()->IsCatchPhi()) { 185777a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil DCHECK(current->HasSpillSlot()); 185877a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil size_t slot = current->GetSpillSlot() 185977a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil + GetNumberOfSpillSlots() 186077a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil + reserved_out_slots_ 186177a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil - catch_phi_spill_slots_; 186277a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil current->SetSpillSlot(slot * kVRegSize); 1863776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray } else if (current->HasSpillSlot()) { 1864776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // Adjust the stack slot, now that we know the number of them for each type. 1865776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // The way this implementation lays out the stack is the following: 186677a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil // [parameter slots ] 186777a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil // [catch phi spill slots ] 186877a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil // [double spill slots ] 186977a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil // [long spill slots ] 187077a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil // [float spill slots ] 187177a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil // [int/ref values ] 187277a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil // [maximum out values ] (number of arguments for calls) 187377a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil // [art method ]. 187477a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil size_t slot = current->GetSpillSlot(); 1875776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray switch (current->GetType()) { 1876776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimDouble: 18772aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko slot += long_spill_slots_.size(); 1878776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray FALLTHROUGH_INTENDED; 1879776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimLong: 18802aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko slot += float_spill_slots_.size(); 1881776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray FALLTHROUGH_INTENDED; 1882776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimFloat: 18832aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko slot += int_spill_slots_.size(); 1884776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray FALLTHROUGH_INTENDED; 1885776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimNot: 1886776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimInt: 1887776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimChar: 1888776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimByte: 1889776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimBoolean: 1890776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimShort: 1891776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray slot += reserved_out_slots_; 1892776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray break; 1893776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimVoid: 1894776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray LOG(FATAL) << "Unexpected type for interval " << current->GetType(); 1895776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray } 1896776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray current->SetSpillSlot(slot * kVRegSize); 189786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 189886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 189901ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location source = current->ToLocation(); 190086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 190186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (location.IsUnallocated()) { 190286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (location.GetPolicy() == Location::kSameAsFirstInput) { 1903d0d4852847432368b090c184d6639e573538dccfCalin Juravle if (locations->InAt(0).IsUnallocated()) { 1904d0d4852847432368b090c184d6639e573538dccfCalin Juravle locations->SetInAt(0, source); 1905d0d4852847432368b090c184d6639e573538dccfCalin Juravle } else { 1906d0d4852847432368b090c184d6639e573538dccfCalin Juravle DCHECK(locations->InAt(0).Equals(source)); 1907d0d4852847432368b090c184d6639e573538dccfCalin Juravle } 190886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 1909829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray locations->UpdateOut(source); 191086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 191186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(source.Equals(location)); 191286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 191386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 191486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 191586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Connect siblings. 191686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { 191786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 191886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ConnectSiblings(instruction->GetLiveInterval()); 191986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 192086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 192186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Resolve non-linear control flow across branches. Order does not matter. 19220d9f17de8f21a10702de1510b73e89d07b3b9bbfNicolas Geoffray for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { 192386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* block = it.Current(); 192415bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray if (block->IsCatchBlock() || 1925ad4ed08d557ff24bd7c66d3f36687d2035367ad0Nicolas Geoffray (block->IsLoopHeader() && block->GetLoopInformation()->IsIrreducible())) { 192615bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray // Instructions live at the top of catch blocks or irreducible loop header 192715bd22849ee6a1ffb3fb3630f686c2870bdf1bbcNicolas Geoffray // were forced to spill. 192877a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil if (kIsDebugBuild) { 192977a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil BitVector* live = liveness_.GetLiveInSet(*block); 193077a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil for (uint32_t idx : live->Indexes()) { 193177a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil LiveInterval* interval = liveness_.GetInstructionFromSsaIndex(idx)->GetLiveInterval(); 1932974bbdd24404830538f6ab1efe3062e4a411e3aeNicolas Geoffray LiveInterval* sibling = interval->GetSiblingAt(block->GetLifetimeStart()); 1933974bbdd24404830538f6ab1efe3062e4a411e3aeNicolas Geoffray // `GetSiblingAt` returns the sibling that contains a position, but there could be 1934974bbdd24404830538f6ab1efe3062e4a411e3aeNicolas Geoffray // a lifetime hole in it. `CoversSlow` returns whether the interval is live at that 1935974bbdd24404830538f6ab1efe3062e4a411e3aeNicolas Geoffray // position. 193632cc778aff36c5d99026d9bdef5f75a5b17cfe23Nicolas Geoffray if ((sibling != nullptr) && sibling->CoversSlow(block->GetLifetimeStart())) { 1937974bbdd24404830538f6ab1efe3062e4a411e3aeNicolas Geoffray DCHECK(!sibling->HasRegister()); 1938974bbdd24404830538f6ab1efe3062e4a411e3aeNicolas Geoffray } 193977a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil } 194077a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil } 194177a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil } else { 194277a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil BitVector* live = liveness_.GetLiveInSet(*block); 194377a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil for (uint32_t idx : live->Indexes()) { 194477a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil LiveInterval* interval = liveness_.GetInstructionFromSsaIndex(idx)->GetLiveInterval(); 194577a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil for (HBasicBlock* predecessor : block->GetPredecessors()) { 194677a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil ConnectSplitSiblings(interval, predecessor, block); 194777a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil } 194886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 194986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 195086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 195186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 195286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Resolve phi inputs. Order does not matter. 19530d9f17de8f21a10702de1510b73e89d07b3b9bbfNicolas Geoffray for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { 195486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* current = it.Current(); 195577a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil if (current->IsCatchBlock()) { 195677a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil // Catch phi values are set at runtime by the exception delivery mechanism. 195777a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil } else { 195877a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil for (HInstructionIterator inst_it(current->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 195977a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil HInstruction* phi = inst_it.Current(); 196077a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil for (size_t i = 0, e = current->GetPredecessors().size(); i < e; ++i) { 1961ec7802a102d49ab5c17495118d4fe0bcc7287bebVladimir Marko HBasicBlock* predecessor = current->GetPredecessors()[i]; 1962d26a411adee1e71b3f09dd604ab9b23018037138David Brazdil DCHECK_EQ(predecessor->GetNormalSuccessors().size(), 1u); 196377a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil HInstruction* input = phi->InputAt(i); 196477a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil Location source = input->GetLiveInterval()->GetLocationAt( 196577a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil predecessor->GetLifetimeEnd() - 1); 196677a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil Location destination = phi->GetLiveInterval()->ToLocation(); 196777a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil InsertParallelMoveAtExitOf(predecessor, phi, source, destination); 196877a48ae01bbc5b05ca009cf09e2fcb53e4c8ff23David Brazdil } 196986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 197086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 197186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 19723946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 19733946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Assign temp locations. 19742aaa4b5532d30c4e65d8892b556400bb61f9dc8cVladimir Marko for (LiveInterval* temp : temp_intervals_) { 1975840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (temp->IsHighInterval()) { 1976840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // High intervals can be skipped, they are already handled by the low interval. 1977840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray continue; 1978840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 197901ef345767ea609417fc511e42007705c9667546Nicolas Geoffray HInstruction* at = liveness_.GetTempUser(temp); 1980f01d34445953e6b9c9b13de1dd32a5c0ee5abab5Nicolas Geoffray size_t temp_index = liveness_.GetTempIndex(temp); 198101ef345767ea609417fc511e42007705c9667546Nicolas Geoffray LocationSummary* locations = at->GetLocations(); 19825368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain switch (temp->GetType()) { 19835368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain case Primitive::kPrimInt: 1984f01d34445953e6b9c9b13de1dd32a5c0ee5abab5Nicolas Geoffray locations->SetTempAt(temp_index, Location::RegisterLocation(temp->GetRegister())); 19855368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain break; 19865368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain 19875368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain case Primitive::kPrimDouble: 1988840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (codegen_->NeedsTwoRegisters(Primitive::kPrimDouble)) { 1989840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray Location location = Location::FpuRegisterPairLocation( 1990840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray temp->GetRegister(), temp->GetHighInterval()->GetRegister()); 1991f01d34445953e6b9c9b13de1dd32a5c0ee5abab5Nicolas Geoffray locations->SetTempAt(temp_index, location); 1992840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else { 1993f01d34445953e6b9c9b13de1dd32a5c0ee5abab5Nicolas Geoffray locations->SetTempAt(temp_index, Location::FpuRegisterLocation(temp->GetRegister())); 1994840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 19955368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain break; 19965368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain 19975368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain default: 19985368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LOG(FATAL) << "Unexpected type for temporary location " 19995368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain << temp->GetType(); 20005368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain } 20013946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 200231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray} 200331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 2004a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} // namespace art 2005