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), 463946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_core_intervals_(allocator, 0), 473946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_fp_intervals_(allocator, 0), 483946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_(nullptr), 49a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_(allocator, 0), 50a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_(allocator, 0), 51a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_(allocator, 0), 52102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_core_register_intervals_(allocator, codegen->GetNumberOfCoreRegisters()), 53102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_fp_register_intervals_(allocator, codegen->GetNumberOfFloatingPointRegisters()), 543946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray temp_intervals_(allocator, 4), 55776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray int_spill_slots_(allocator, kDefaultNumberOfSpillSlots), 56776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray long_spill_slots_(allocator, kDefaultNumberOfSpillSlots), 57776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray float_spill_slots_(allocator, kDefaultNumberOfSpillSlots), 58776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray double_spill_slots_(allocator, kDefaultNumberOfSpillSlots), 593946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray safepoints_(allocator, 0), 60a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray processing_core_registers_(false), 61a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray number_of_registers_(-1), 62a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray registers_array_(nullptr), 63102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray blocked_core_registers_(codegen->GetBlockedCoreRegisters()), 64102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray blocked_fp_registers_(codegen->GetBlockedFloatingPointRegisters()), 653bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray reserved_out_slots_(0), 66f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell maximum_number_of_live_core_registers_(0), 67f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell maximum_number_of_live_fp_registers_(0) { 68988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray static constexpr bool kIsBaseline = false; 69988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray codegen->SetupBlockedRegisters(kIsBaseline); 70102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_core_register_intervals_.SetSize(codegen->GetNumberOfCoreRegisters()); 71102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_fp_register_intervals_.SetSize(codegen->GetNumberOfFloatingPointRegisters()); 723946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Always reserve for the current method and the graph's max out registers. 733946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // TODO: compute it instead. 743d21bdf8894e780d349c481e5c9e29fe1556051cMathieu Chartier // ArtMethod* takes 2 vregs for 64 bits. 753d21bdf8894e780d349c481e5c9e29fe1556051cMathieu Chartier reserved_out_slots_ = InstructionSetPointerSize(codegen->GetInstructionSet()) / kVRegSize + 763d21bdf8894e780d349c481e5c9e29fe1556051cMathieu Chartier codegen->GetGraph()->GetMaximumNumberOfOutVRegs(); 77a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 78a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 79234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffraybool RegisterAllocator::CanAllocateRegistersFor(const HGraph& graph ATTRIBUTE_UNUSED, 8086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InstructionSet instruction_set) { 81234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray return instruction_set == kArm64 826c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray || instruction_set == kX86_64 83a1935c4fa255b5c20f5e9b2abce6be2d0f7cb0a8Roland Levillain || instruction_set == kMips64 846c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray || instruction_set == kArm 85234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray || instruction_set == kX86 86234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray || instruction_set == kThumb2; 8786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 8886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 8986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraystatic bool ShouldProcess(bool processing_core_registers, LiveInterval* interval) { 903946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (interval == nullptr) return false; 9186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray bool is_core_register = (interval->GetType() != Primitive::kPrimDouble) 9286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && (interval->GetType() != Primitive::kPrimFloat); 93a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return processing_core_registers == is_core_register; 94a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 95a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 9686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::AllocateRegisters() { 9786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray AllocateRegistersInternal(); 9886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Resolve(); 9986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 10086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (kIsDebugBuild) { 10186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray processing_core_registers_ = true; 10286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ValidateInternal(true); 10386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray processing_core_registers_ = false; 10486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ValidateInternal(true); 1055976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // Check that the linear order is still correct with regards to lifetime positions. 1065976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // Since only parallel moves have been inserted during the register allocation, 1075976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // these checks are mostly for making sure these moves have been added correctly. 1085976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray size_t current_liveness = 0; 1090d9f17de8f21a10702de1510b73e89d07b3b9bbfNicolas Geoffray for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { 1105976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray HBasicBlock* block = it.Current(); 1115976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 1125976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray HInstruction* instruction = inst_it.Current(); 1135976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray DCHECK_LE(current_liveness, instruction->GetLifetimePosition()); 1145976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray current_liveness = instruction->GetLifetimePosition(); 1155976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray } 1165976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray for (HInstructionIterator inst_it(block->GetInstructions()); 1175976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray !inst_it.Done(); 1185976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray inst_it.Advance()) { 1195976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray HInstruction* instruction = inst_it.Current(); 1205976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray DCHECK_LE(current_liveness, instruction->GetLifetimePosition()) << instruction->DebugName(); 1215976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray current_liveness = instruction->GetLifetimePosition(); 1225976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray } 1235976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray } 12486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 12586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 12686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 12786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::BlockRegister(Location location, 12886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t start, 129102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray size_t end) { 13056b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray int reg = location.reg(); 131102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray DCHECK(location.IsRegister() || location.IsFpuRegister()); 132102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* interval = location.IsRegister() 133102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ? physical_core_register_intervals_.Get(reg) 134102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray : physical_fp_register_intervals_.Get(reg); 135102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray Primitive::Type type = location.IsRegister() 136102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ? Primitive::kPrimInt 137840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray : Primitive::kPrimFloat; 13886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (interval == nullptr) { 13986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray interval = LiveInterval::MakeFixedInterval(allocator_, reg, type); 140102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (location.IsRegister()) { 141102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_core_register_intervals_.Put(reg, interval); 142102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 143102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_fp_register_intervals_.Put(reg, interval); 144102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 14586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 14686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(interval->GetRegister() == reg); 14786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray interval->AddRange(start, end); 14886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 14986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 15086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::AllocateRegistersInternal() { 1513946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Iterate post-order, to ensure the list is sorted, and the last added interval 1523946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // is the one with the lowest start position. 1530d9f17de8f21a10702de1510b73e89d07b3b9bbfNicolas Geoffray for (HLinearPostOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { 1543946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray HBasicBlock* block = it.Current(); 155277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe for (HBackwardInstructionIterator back_it(block->GetInstructions()); !back_it.Done(); 156277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe back_it.Advance()) { 157277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe ProcessInstruction(back_it.Current()); 1583946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 159277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 160277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe ProcessInstruction(inst_it.Current()); 1613946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 1623946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 163a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1643946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray number_of_registers_ = codegen_->GetNumberOfCoreRegisters(); 165a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_); 1663946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray processing_core_registers_ = true; 1673946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_ = &unhandled_core_intervals_; 168102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0, e = physical_core_register_intervals_.Size(); i < e; ++i) { 169102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* fixed = physical_core_register_intervals_.Get(i); 170102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (fixed != nullptr) { 171296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Fixed interval is added to inactive_ instead of unhandled_. 172296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // It's also the only type of inactive interval whose start position 173296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // can be after the current interval during linear scan. 174296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Fixed interval is never split and never moves to unhandled_. 175102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray inactive_.Add(fixed); 176102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 177102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 1783946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LinearScan(); 179a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1803946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray inactive_.Reset(); 1813946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray active_.Reset(); 1823946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray handled_.Reset(); 183a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1843946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray number_of_registers_ = codegen_->GetNumberOfFloatingPointRegisters(); 1853946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_); 1863946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray processing_core_registers_ = false; 1873946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_ = &unhandled_fp_intervals_; 188102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0, e = physical_fp_register_intervals_.Size(); i < e; ++i) { 189102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* fixed = physical_fp_register_intervals_.Get(i); 190102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (fixed != nullptr) { 191296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Fixed interval is added to inactive_ instead of unhandled_. 192296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // It's also the only type of inactive interval whose start position 193296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // can be after the current interval during linear scan. 194296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Fixed interval is never split and never moves to unhandled_. 195102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray inactive_.Add(fixed); 196102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 197102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 1983946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LinearScan(); 1993946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray} 20086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 2013946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffrayvoid RegisterAllocator::ProcessInstruction(HInstruction* instruction) { 2023946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LocationSummary* locations = instruction->GetLocations(); 2033946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t position = instruction->GetLifetimePosition(); 2043946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 2053946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (locations == nullptr) return; 2063946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 2073946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Create synthesized intervals for temporaries. 2083946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < locations->GetTempCount(); ++i) { 2093946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray Location temp = locations->GetTemp(i); 21052839d17c06175e19ca4a093fb878450d1c4310dNicolas Geoffray if (temp.IsRegister() || temp.IsFpuRegister()) { 211102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray BlockRegister(temp, position, position + 1); 2123946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 213102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray DCHECK(temp.IsUnallocated()); 2145368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain switch (temp.GetPolicy()) { 2155368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain case Location::kRequiresRegister: { 2165368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LiveInterval* interval = 2175368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimInt); 2185368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain temp_intervals_.Add(interval); 219f01d34445953e6b9c9b13de1dd32a5c0ee5abab5Nicolas Geoffray interval->AddTempUse(instruction, i); 2205368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain unhandled_core_intervals_.Add(interval); 2215368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain break; 2225368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain } 2235368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain 2245368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain case Location::kRequiresFpuRegister: { 2255368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LiveInterval* interval = 2265368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimDouble); 2275368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain temp_intervals_.Add(interval); 228f01d34445953e6b9c9b13de1dd32a5c0ee5abab5Nicolas Geoffray interval->AddTempUse(instruction, i); 229840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (codegen_->NeedsTwoRegisters(Primitive::kPrimDouble)) { 2305588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray interval->AddHighInterval(/* is_temp */ true); 231840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray LiveInterval* high = interval->GetHighInterval(); 232840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray temp_intervals_.Add(high); 233840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray unhandled_fp_intervals_.Add(high); 234840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 2355368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain unhandled_fp_intervals_.Add(interval); 2365368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain break; 2375368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain } 2385368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain 2395368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain default: 2405368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LOG(FATAL) << "Unexpected policy for temporary location " 2415368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain << temp.GetPolicy(); 2425368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain } 243a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 244a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 24586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 2463bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray bool core_register = (instruction->GetType() != Primitive::kPrimDouble) 2473bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray && (instruction->GetType() != Primitive::kPrimFloat); 2483bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray 2493946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (locations->CanCall()) { 250c0572a451944f78397619dec34a38c36c11e9d2aNicolas Geoffray if (codegen_->IsLeafMethod()) { 251c0572a451944f78397619dec34a38c36c11e9d2aNicolas Geoffray // TODO: We do this here because we do not want the suspend check to artificially 252c0572a451944f78397619dec34a38c36c11e9d2aNicolas Geoffray // create live registers. We should find another place, but this is currently the 253c0572a451944f78397619dec34a38c36c11e9d2aNicolas Geoffray // simplest. 254c0572a451944f78397619dec34a38c36c11e9d2aNicolas Geoffray DCHECK(instruction->IsSuspendCheckEntry()); 255c0572a451944f78397619dec34a38c36c11e9d2aNicolas Geoffray instruction->GetBlock()->RemoveInstruction(instruction); 256c0572a451944f78397619dec34a38c36c11e9d2aNicolas Geoffray return; 2573bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 2583946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray safepoints_.Add(instruction); 2593bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray if (locations->OnlyCallsOnSlowPath()) { 2603bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // We add a synthesized range at this position to record the live registers 2613bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // at this position. Ideally, we could just update the safepoints when locations 2623bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // are updated, but we currently need to know the full stack size before updating 2633bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // locations (because of parameters and the fact that we don't have a frame pointer). 2643bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // And knowing the full stack size requires to know the maximum number of live 2653bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // registers at calls in slow paths. 2663bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // By adding the following interval in the algorithm, we can compute this 2673bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // maximum before updating locations. 2683bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray LiveInterval* interval = LiveInterval::MakeSlowPathInterval(allocator_, instruction); 269acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray interval->AddRange(position, position + 1); 27087d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray AddSorted(&unhandled_core_intervals_, interval); 27187d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray AddSorted(&unhandled_fp_intervals_, interval); 2723bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 2733bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 2743bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray 2753bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray if (locations->WillCall()) { 2763946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Block all registers. 2773946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < codegen_->GetNumberOfCoreRegisters(); ++i) { 278988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray if (!codegen_->IsCoreCalleeSaveRegister(i)) { 279988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray BlockRegister(Location::RegisterLocation(i), 280988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray position, 281988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray position + 1); 282988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray } 283102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 284102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0; i < codegen_->GetNumberOfFloatingPointRegisters(); ++i) { 285988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray if (!codegen_->IsFloatingPointCalleeSaveRegister(i)) { 286988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray BlockRegister(Location::FpuRegisterLocation(i), 287988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray position, 288988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray position + 1); 289988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray } 2903946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 2913946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 2923946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 2933946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < instruction->InputCount(); ++i) { 2943946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray Location input = locations->InAt(i); 295102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (input.IsRegister() || input.IsFpuRegister()) { 296102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray BlockRegister(input, position, position + 1); 297840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (input.IsPair()) { 298840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray BlockRegister(input.ToLow(), position, position + 1); 299840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray BlockRegister(input.ToHigh(), position, position + 1); 3003946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3013946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3023946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 3033946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* current = instruction->GetLiveInterval(); 3043946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current == nullptr) return; 3053946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 306102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray GrowableArray<LiveInterval*>& unhandled = core_register 307102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ? unhandled_core_intervals_ 308102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray : unhandled_fp_intervals_; 309102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray 3107690562d40878f44823d5fb03a2084cfc677ec4aNicolas Geoffray DCHECK(unhandled.IsEmpty() || current->StartsBeforeOrAt(unhandled.Peek())); 31187d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray 312840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (codegen_->NeedsTwoRegisters(current->GetType())) { 313840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray current->AddHighInterval(); 314840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 315840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 3165588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray for (size_t safepoint_index = safepoints_.Size(); safepoint_index > 0; --safepoint_index) { 3175588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray HInstruction* safepoint = safepoints_.Get(safepoint_index - 1); 3185588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray size_t safepoint_position = safepoint->GetLifetimePosition(); 3195588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray 3205588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray // Test that safepoints are ordered in the optimal way. 3215588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray DCHECK(safepoint_index == safepoints_.Size() 3225588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray || safepoints_.Get(safepoint_index)->GetLifetimePosition() < safepoint_position); 3235588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray 3245588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray if (safepoint_position == current->GetStart()) { 3255588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray // The safepoint is for this instruction, so the location of the instruction 3265588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray // does not need to be saved. 3275588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray DCHECK_EQ(safepoint_index, safepoints_.Size()); 3285588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray DCHECK_EQ(safepoint, instruction); 3295588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray continue; 3305588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray } else if (current->IsDeadAt(safepoint_position)) { 3315588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray break; 3325588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray } else if (!current->Covers(safepoint_position)) { 3335588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray // Hole in the interval. 3345588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray continue; 3355588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray } 3365588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray current->AddSafepoint(safepoint); 3375588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray } 3383fc992f9dfe8f49ff350132323cc635f102b7b62David Brazdil current->ResetSearchCache(); 3395588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray 3403946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Some instructions define their output in fixed register/stack slot. We need 3413946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // to ensure we know these locations before doing register allocation. For a 3423946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // given register, we create an interval that covers these locations. The register 3433946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // will be unavailable at these locations when trying to allocate one for an 3443946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // interval. 3453946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // 3463946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // The backwards walking ensures the ranges are ordered on increasing start positions. 3473946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray Location output = locations->Out(); 348d0d4852847432368b090c184d6639e573538dccfCalin Juravle if (output.IsUnallocated() && output.GetPolicy() == Location::kSameAsFirstInput) { 349d0d4852847432368b090c184d6639e573538dccfCalin Juravle Location first = locations->InAt(0); 350d0d4852847432368b090c184d6639e573538dccfCalin Juravle if (first.IsRegister() || first.IsFpuRegister()) { 351d0d4852847432368b090c184d6639e573538dccfCalin Juravle current->SetFrom(position + 1); 352d0d4852847432368b090c184d6639e573538dccfCalin Juravle current->SetRegister(first.reg()); 353840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (first.IsPair()) { 354840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray current->SetFrom(position + 1); 355840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray current->SetRegister(first.low()); 356840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray LiveInterval* high = current->GetHighInterval(); 357840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray high->SetRegister(first.high()); 358840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray high->SetFrom(position + 1); 359d0d4852847432368b090c184d6639e573538dccfCalin Juravle } 360d0d4852847432368b090c184d6639e573538dccfCalin Juravle } else if (output.IsRegister() || output.IsFpuRegister()) { 3613946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Shift the interval's start by one to account for the blocked register. 3623946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray current->SetFrom(position + 1); 36356b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray current->SetRegister(output.reg()); 364102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray BlockRegister(output, position, position + 1); 365840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (output.IsPair()) { 366840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray current->SetFrom(position + 1); 367840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray current->SetRegister(output.low()); 368840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray LiveInterval* high = current->GetHighInterval(); 369840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray high->SetRegister(output.high()); 370840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray high->SetFrom(position + 1); 371840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray BlockRegister(output.ToLow(), position, position + 1); 372840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray BlockRegister(output.ToHigh(), position, position + 1); 3733946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else if (output.IsStackSlot() || output.IsDoubleStackSlot()) { 3743946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray current->SetSpillSlot(output.GetStackIndex()); 375840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else { 376840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(output.IsUnallocated() || output.IsConstant()); 3773946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3783946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 3793946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // If needed, add interval to the list of unhandled intervals. 3803946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current->HasSpillSlot() || instruction->IsConstant()) { 381c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray // Split just before first register use. 3823946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t first_register_use = current->FirstRegisterUse(); 3833946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (first_register_use != kNoLifetime) { 3848cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray LiveInterval* split = SplitBetween(current, current->GetStart(), first_register_use - 1); 385b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // Don't add directly to `unhandled`, it needs to be sorted and the start 3863946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // of this new interval might be after intervals already in the list. 3873946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(&unhandled, split); 3883946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 3893946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Nothing to do, we won't allocate a register for this value. 3903946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3913946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 392b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // Don't add directly to `unhandled`, temp or safepoint intervals 393b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // for this instruction may have been added, and those can be 394b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // processed first. 395b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray AddSorted(&unhandled, current); 3963946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 397a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 398a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 39931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffrayclass AllRangesIterator : public ValueObject { 40031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray public: 40131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray explicit AllRangesIterator(LiveInterval* interval) 40231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray : current_interval_(interval), 40331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_(interval->GetFirstRange()) {} 40431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 40531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray bool Done() const { return current_interval_ == nullptr; } 40631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveRange* CurrentRange() const { return current_range_; } 40731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* CurrentInterval() const { return current_interval_; } 40831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 40931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray void Advance() { 41031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_ = current_range_->GetNext(); 41131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current_range_ == nullptr) { 41231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_interval_ = current_interval_->GetNextSibling(); 41331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current_interval_ != nullptr) { 41431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_ = current_interval_->GetFirstRange(); 41531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 41631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 41731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 41831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 41931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray private: 42031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* current_interval_; 42131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveRange* current_range_; 42231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 42331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray DISALLOW_COPY_AND_ASSIGN(AllRangesIterator); 42431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray}; 42531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 42686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraybool RegisterAllocator::ValidateInternal(bool log_fatal_on_failure) const { 42786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // To simplify unit testing, we eagerly create the array of intervals, and 42886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // call the helper method. 42986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray GrowableArray<LiveInterval*> intervals(allocator_, 0); 43086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0; i < liveness_.GetNumberOfSsaValues(); ++i) { 43186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 43286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (ShouldProcess(processing_core_registers_, instruction->GetLiveInterval())) { 43386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray intervals.Add(instruction->GetLiveInterval()); 43486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 43586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 43686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 437102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (processing_core_registers_) { 438102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0, e = physical_core_register_intervals_.Size(); i < e; ++i) { 439102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* fixed = physical_core_register_intervals_.Get(i); 440102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (fixed != nullptr) { 441102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray intervals.Add(fixed); 442102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 443102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 444102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 445102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0, e = physical_fp_register_intervals_.Size(); i < e; ++i) { 446102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* fixed = physical_fp_register_intervals_.Get(i); 447102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (fixed != nullptr) { 448102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray intervals.Add(fixed); 449102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 45086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 45186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 45286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 4533946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0, e = temp_intervals_.Size(); i < e; ++i) { 4543946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* temp = temp_intervals_.Get(i); 4553946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (ShouldProcess(processing_core_registers_, temp)) { 4563946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray intervals.Add(temp); 4573946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 4583946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 4593946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 460776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray return ValidateIntervals(intervals, GetNumberOfSpillSlots(), reserved_out_slots_, *codegen_, 4613946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray allocator_, processing_core_registers_, log_fatal_on_failure); 46286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 46386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 46431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffraybool RegisterAllocator::ValidateIntervals(const GrowableArray<LiveInterval*>& intervals, 46531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray size_t number_of_spill_slots, 4663946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t number_of_out_slots, 467a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray const CodeGenerator& codegen, 468a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray ArenaAllocator* allocator, 469a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool processing_core_registers, 470a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool log_fatal_on_failure) { 471a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t number_of_registers = processing_core_registers 472a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray ? codegen.GetNumberOfCoreRegisters() 473a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray : codegen.GetNumberOfFloatingPointRegisters(); 47431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray GrowableArray<ArenaBitVector*> liveness_of_values( 47531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray allocator, number_of_registers + number_of_spill_slots); 476a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 477a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Allocate a bit vector per register. A live interval that has a register 478a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // allocated will populate the associated bit vector based on its live ranges. 47931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t i = 0; i < number_of_registers + number_of_spill_slots; ++i) { 48031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_values.Add(new (allocator) ArenaBitVector(allocator, 0, true)); 481a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 482a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 48331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t i = 0, e = intervals.Size(); i < e; ++i) { 48431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (AllRangesIterator it(intervals.Get(i)); !it.Done(); it.Advance()) { 48531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* current = it.CurrentInterval(); 48686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* defined_by = current->GetParent()->GetDefinedBy(); 48786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->GetParent()->HasSpillSlot() 48886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Parameters have their own stack slot. 48986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && !(defined_by != nullptr && defined_by->IsParameterValue())) { 4903946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray BitVector* liveness_of_spill_slot = liveness_of_values.Get(number_of_registers 4913946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray + current->GetParent()->GetSpillSlot() / kVRegSize 4923946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray - number_of_out_slots); 49331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 49431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (liveness_of_spill_slot->IsBitSet(j)) { 49531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (log_fatal_on_failure) { 49631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray std::ostringstream message; 49731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray message << "Spill slot conflict at " << j; 49831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LOG(FATAL) << message.str(); 49931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 50031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray return false; 50131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 50231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 50331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_spill_slot->SetBit(j); 50431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 50531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 506a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 50731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 50831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current->HasRegister()) { 50931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray BitVector* liveness_of_register = liveness_of_values.Get(current->GetRegister()); 51031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 51131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (liveness_of_register->IsBitSet(j)) { 512829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray if (current->IsUsingInputRegister() && current->CanUseInputRegister()) { 513829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray continue; 514829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 515a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (log_fatal_on_failure) { 516a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray std::ostringstream message; 5173946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray message << "Register conflict at " << j << " "; 5183946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (defined_by != nullptr) { 5193946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray message << "(" << defined_by->DebugName() << ")"; 5203946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 5213946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray message << "for "; 522a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (processing_core_registers) { 523a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen.DumpCoreRegister(message, current->GetRegister()); 524a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 525a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen.DumpFloatingPointRegister(message, current->GetRegister()); 526a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 527a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LOG(FATAL) << message.str(); 528a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 529a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 530a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 531a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 53231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_register->SetBit(j); 533a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 534a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 53531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 53631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 537a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 538a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 539a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 540a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 54186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::DumpInterval(std::ostream& stream, LiveInterval* interval) const { 542a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray interval->Dump(stream); 543a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << ": "; 544a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->HasRegister()) { 545102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (interval->IsFloatingPoint()) { 54686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray codegen_->DumpFloatingPointRegister(stream, interval->GetRegister()); 547102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 548102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray codegen_->DumpCoreRegister(stream, interval->GetRegister()); 549a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 550a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 551a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << "spilled"; 552a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 553a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << std::endl; 554a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 555a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 556296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yangvoid RegisterAllocator::DumpAllIntervals(std::ostream& stream) const { 557296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang stream << "inactive: " << std::endl; 558296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0; i < inactive_.Size(); i ++) { 559296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DumpInterval(stream, inactive_.Get(i)); 560296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 561296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang stream << "active: " << std::endl; 562296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0; i < active_.Size(); i ++) { 563296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DumpInterval(stream, active_.Get(i)); 564296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 565296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang stream << "unhandled: " << std::endl; 566296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang auto unhandled = (unhandled_ != nullptr) ? 567296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang unhandled_ : &unhandled_core_intervals_; 568296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0; i < unhandled->Size(); i ++) { 569296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DumpInterval(stream, unhandled->Get(i)); 570296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 571296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang stream << "handled: " << std::endl; 572296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0; i < handled_.Size(); i ++) { 573296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DumpInterval(stream, handled_.Get(i)); 574296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 575296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang} 576296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang 577a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// By the book implementation of a linear scan register allocator. 578a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffrayvoid RegisterAllocator::LinearScan() { 5793946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray while (!unhandled_->IsEmpty()) { 580a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (1) Remove interval with the lowest start position from unhandled. 5813946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* current = unhandled_->Pop(); 5823946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray DCHECK(!current->IsFixed() && !current->HasSpillSlot()); 583c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray DCHECK(unhandled_->IsEmpty() || unhandled_->Peek()->GetStart() >= current->GetStart()); 584840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(!current->IsLowInterval() || unhandled_->Peek()->IsHighInterval()); 58587d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray 586a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t position = current->GetStart(); 587a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 588296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Remember the inactive_ size here since the ones moved to inactive_ from 589296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // active_ below shouldn't need to be re-checked. 590296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang size_t inactive_intervals_to_handle = inactive_.Size(); 591296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang 592a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (2) Remove currently active intervals that are dead at this position. 593a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Move active intervals that have a lifetime hole at this position 594a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // to inactive. 595a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < active_.Size(); ++i) { 596a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* interval = active_.Get(i); 597a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->IsDeadAt(position)) { 598a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Delete(interval); 599a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 600a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_.Add(interval); 601a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else if (!interval->Covers(position)) { 602a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Delete(interval); 603a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 604a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.Add(interval); 605a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 606a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 607a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 608a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (3) Remove currently inactive intervals that are dead at this position. 609a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Move inactive intervals that cover this position to active. 610296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0; i < inactive_intervals_to_handle; ++i) { 611a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* interval = inactive_.Get(i); 612296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK(interval->GetStart() < position || interval->IsFixed()); 613a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->IsDeadAt(position)) { 614a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.Delete(interval); 615a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 616296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang --inactive_intervals_to_handle; 617a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_.Add(interval); 618a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else if (interval->Covers(position)) { 619a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.Delete(interval); 620a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 621296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang --inactive_intervals_to_handle; 622a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Add(interval); 623a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 624a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 625a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 626acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray if (current->IsSlowPathSafepoint()) { 627acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray // Synthesized interval to record the maximum number of live registers 628acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray // at safepoints. No need to allocate a register for it. 629f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell if (processing_core_registers_) { 630f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell maximum_number_of_live_core_registers_ = 631f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell std::max(maximum_number_of_live_core_registers_, active_.Size()); 632f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell } else { 633f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell maximum_number_of_live_fp_registers_ = 634f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell std::max(maximum_number_of_live_fp_registers_, active_.Size()); 635f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell } 636acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray DCHECK(unhandled_->IsEmpty() || unhandled_->Peek()->GetStart() > current->GetStart()); 637acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray continue; 638acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray } 639acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray 640840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (current->IsHighInterval() && !current->GetLowInterval()->HasRegister()) { 641840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(!current->HasRegister()); 642840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // Allocating the low part was unsucessful. The splitted interval for the high part 643840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // will be handled next (it is in the `unhandled_` list). 644840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray continue; 645840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 646840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 647a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (4) Try to find an available register. 648a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool success = TryAllocateFreeReg(current); 649a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 650a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (5) If no register could be found, we need to spill. 651a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (!success) { 652a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray success = AllocateBlockedReg(current); 653a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 654a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 655a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (6) If the interval had a register allocated, add it to the list of active 656a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // intervals. 657a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (success) { 658988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray codegen_->AddAllocatedRegister(processing_core_registers_ 659988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray ? Location::RegisterLocation(current->GetRegister()) 660988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray : Location::FpuRegisterLocation(current->GetRegister())); 661a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Add(current); 662840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (current->HasHighInterval() && !current->GetHighInterval()->HasRegister()) { 663840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray current->GetHighInterval()->SetRegister(GetHighForLowRegister(current->GetRegister())); 664840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 665a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 666a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 667a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 668a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 669829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffraystatic void FreeIfNotCoverAt(LiveInterval* interval, size_t position, size_t* free_until) { 670829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray DCHECK(!interval->IsHighInterval()); 671829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // Note that the same instruction may occur multiple times in the input list, 672829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // so `free_until` may have changed already. 6733fc992f9dfe8f49ff350132323cc635f102b7b62David Brazdil // Since `position` is not the current scan position, we need to use CoversSlow. 674829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray if (interval->IsDeadAt(position)) { 675829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // Set the register to be free. Note that inactive intervals might later 676829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // update this. 677829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray free_until[interval->GetRegister()] = kMaxLifetimePosition; 678829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray if (interval->HasHighInterval()) { 679829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray DCHECK(interval->GetHighInterval()->IsDeadAt(position)); 680829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray free_until[interval->GetHighInterval()->GetRegister()] = kMaxLifetimePosition; 681829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 6823fc992f9dfe8f49ff350132323cc635f102b7b62David Brazdil } else if (!interval->CoversSlow(position)) { 683829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // The interval becomes inactive at `defined_by`. We make its register 684829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // available only until the next use strictly after `defined_by`. 685829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray free_until[interval->GetRegister()] = interval->FirstUseAfter(position); 686829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray if (interval->HasHighInterval()) { 6873fc992f9dfe8f49ff350132323cc635f102b7b62David Brazdil DCHECK(!interval->GetHighInterval()->CoversSlow(position)); 688829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray free_until[interval->GetHighInterval()->GetRegister()] = free_until[interval->GetRegister()]; 689829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 690829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 691829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray} 692829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray 693a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// Find a free register. If multiple are found, pick the register that 694a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// is free the longest. 695a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::TryAllocateFreeReg(LiveInterval* current) { 696a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t* free_until = registers_array_; 697a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 698a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // First set all registers to be free. 699a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 700a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray free_until[i] = kMaxLifetimePosition; 701a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 702a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 703296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // For each active interval, set its register to not free. 704296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0, e = active_.Size(); i < e; ++i) { 705296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang LiveInterval* interval = active_.Get(i); 706296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK(interval->HasRegister()); 707296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang free_until[interval->GetRegister()] = 0; 708296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 709296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang 710829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // An interval that starts an instruction (that is, it is not split), may 711829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // re-use the registers used by the inputs of that instruciton, based on the 712829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // location summary. 713829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray HInstruction* defined_by = current->GetDefinedBy(); 714829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray if (defined_by != nullptr && !current->IsSplit()) { 715829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray LocationSummary* locations = defined_by->GetLocations(); 716829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray if (!locations->OutputCanOverlapWithInputs() && locations->Out().IsUnallocated()) { 717829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray for (HInputIterator it(defined_by); !it.Done(); it.Advance()) { 718829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // Take the last interval of the input. It is the location of that interval 719829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // that will be used at `defined_by`. 720829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray LiveInterval* interval = it.Current()->GetLiveInterval()->GetLastSibling(); 721829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // Note that interval may have not been processed yet. 722829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // TODO: Handle non-split intervals last in the work list. 723829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray if (interval->HasRegister() && interval->SameRegisterKind(*current)) { 724829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // The input must be live until the end of `defined_by`, to comply to 725829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // the linear scan algorithm. So we use `defined_by`'s end lifetime 726829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // position to check whether the input is dead or is inactive after 727829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // `defined_by`. 7283fc992f9dfe8f49ff350132323cc635f102b7b62David Brazdil DCHECK(interval->CoversSlow(defined_by->GetLifetimePosition())); 729829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray size_t position = defined_by->GetLifetimePosition() + 1; 730829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray FreeIfNotCoverAt(interval, position, free_until); 731829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 732829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 733829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 734829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 735829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray 736a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each inactive interval, set its register to be free until 737a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // the next intersection with `current`. 738a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { 739a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* inactive = inactive_.Get(i); 740296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Temp/Slow-path-safepoint interval has no holes. 741296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK(!inactive->IsTemp() && !inactive->IsSlowPathSafepoint()); 742296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang if (!current->IsSplit() && !inactive->IsFixed()) { 743296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Neither current nor inactive are fixed. 744296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Thanks to SSA, a non-split interval starting in a hole of an 745296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // inactive interval should never intersect with that inactive interval. 746296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Only if it's not fixed though, because fixed intervals don't come from SSA. 747296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime); 748296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang continue; 749296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 750296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang 751a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(inactive->HasRegister()); 752296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang if (free_until[inactive->GetRegister()] == 0) { 753296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Already used by some active interval. No need to intersect. 754296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang continue; 755296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 756a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t next_intersection = inactive->FirstIntersectionWith(current); 757a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (next_intersection != kNoLifetime) { 758aac0f39a3501a7f7dd04b2342c2a16961969f139Nicolas Geoffray free_until[inactive->GetRegister()] = 759aac0f39a3501a7f7dd04b2342c2a16961969f139Nicolas Geoffray std::min(free_until[inactive->GetRegister()], next_intersection); 760a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 761a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 762a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 7636c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray int reg = kNoRegister; 7643946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current->HasRegister()) { 7653946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Some instructions have a fixed register output. 7663946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray reg = current->GetRegister(); 767840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (free_until[reg] == 0) { 768840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(current->IsHighInterval()); 769840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // AllocateBlockedReg will spill the holder of the register. 770840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return false; 771840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 7723946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 773840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(!current->IsHighInterval()); 774fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray int hint = current->FindFirstRegisterHint(free_until, liveness_); 7756e9c66e099654b63ed3648bda2daeaf0a862f047Nicolas Geoffray if ((hint != kNoRegister) 7766e9c66e099654b63ed3648bda2daeaf0a862f047Nicolas Geoffray // For simplicity, if the hint we are getting for a pair cannot be used, 7776e9c66e099654b63ed3648bda2daeaf0a862f047Nicolas Geoffray // we are just going to allocate a new pair. 7786e9c66e099654b63ed3648bda2daeaf0a862f047Nicolas Geoffray && !(current->IsLowInterval() && IsBlocked(GetHighForLowRegister(hint)))) { 77901ef345767ea609417fc511e42007705c9667546Nicolas Geoffray DCHECK(!IsBlocked(hint)); 78001ef345767ea609417fc511e42007705c9667546Nicolas Geoffray reg = hint; 781840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (current->IsLowInterval()) { 7826c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray reg = FindAvailableRegisterPair(free_until, current->GetStart()); 78301ef345767ea609417fc511e42007705c9667546Nicolas Geoffray } else { 784840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray reg = FindAvailableRegister(free_until); 785a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 786a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 787a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 7886c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK_NE(reg, kNoRegister); 789a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // If we could not find a register, we need to spill. 790840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (free_until[reg] == 0) { 791840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return false; 792840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 793840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 794234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray if (current->IsLowInterval()) { 795234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray // If the high register of this interval is not available, we need to spill. 796234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray int high_reg = current->GetHighInterval()->GetRegister(); 797234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray if (high_reg == kNoRegister) { 798234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray high_reg = GetHighForLowRegister(reg); 799234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray } 800234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray if (free_until[high_reg] == 0) { 801234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray return false; 802234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray } 803a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 804a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 805a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray current->SetRegister(reg); 806a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (!current->IsDeadAt(free_until[reg])) { 807a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // If the register is only available for a subset of live ranges 808a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // covered by `current`, split `current` at the position where 809a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // the register is not available anymore. 810a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* split = Split(current, free_until[reg]); 811a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(split != nullptr); 8123946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 813a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 814a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 815a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 816a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 817a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::IsBlocked(int reg) const { 818102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return processing_core_registers_ 819102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ? blocked_core_registers_[reg] 820102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray : blocked_fp_registers_[reg]; 821a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 822a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 8236c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffrayint RegisterAllocator::FindAvailableRegisterPair(size_t* next_use, size_t starting_at) const { 8246c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray int reg = kNoRegister; 825840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // Pick the register pair that is used the last. 826840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 827840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (IsBlocked(i)) continue; 828840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (!IsLowRegister(i)) continue; 829840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray int high_register = GetHighForLowRegister(i); 830840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (IsBlocked(high_register)) continue; 831840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray int existing_high_register = GetHighForLowRegister(reg); 8326c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if ((reg == kNoRegister) || (next_use[i] >= next_use[reg] 833840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray && next_use[high_register] >= next_use[existing_high_register])) { 834840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray reg = i; 835840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (next_use[i] == kMaxLifetimePosition 836840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray && next_use[high_register] == kMaxLifetimePosition) { 837840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray break; 838840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 8396c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } else if (next_use[reg] <= starting_at || next_use[existing_high_register] <= starting_at) { 8406c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // If one of the current register is known to be unavailable, just unconditionally 8416c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // try a new one. 8426c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray reg = i; 843840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 844840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 845840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return reg; 846840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray} 847840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 848840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffrayint RegisterAllocator::FindAvailableRegister(size_t* next_use) const { 8496c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray int reg = kNoRegister; 850840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // Pick the register that is used the last. 851840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 852840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (IsBlocked(i)) continue; 8536c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (reg == kNoRegister || next_use[i] > next_use[reg]) { 854840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray reg = i; 855840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (next_use[i] == kMaxLifetimePosition) break; 856840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 857840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 858840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return reg; 859840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray} 860840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 861234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffraybool RegisterAllocator::TrySplitNonPairOrUnalignedPairIntervalAt(size_t position, 862234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray size_t first_register_use, 863234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray size_t* next_use) { 8646c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray for (size_t i = 0, e = active_.Size(); i < e; ++i) { 8656c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray LiveInterval* active = active_.Get(i); 8666c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(active->HasRegister()); 867234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray if (active->IsFixed()) continue; 868234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray if (active->IsHighInterval()) continue; 869234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray if (first_register_use > next_use[active->GetRegister()]) continue; 870234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray 8716c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // Split the first interval found. 872234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray if (!active->IsLowInterval() || IsLowOfUnalignedPairInterval(active)) { 8736c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray LiveInterval* split = Split(active, position); 8746c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray active_.DeleteAt(i); 8756c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (split != active) { 8766c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray handled_.Add(active); 8776c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 8786c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray AddSorted(unhandled_, split); 8796c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray return true; 8806c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 8816c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 8826c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray return false; 8836c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray} 8846c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray 8855b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffraybool RegisterAllocator::PotentiallyRemoveOtherHalf(LiveInterval* interval, 8865b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray GrowableArray<LiveInterval*>* intervals, 8875b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray size_t index) { 8885b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray if (interval->IsLowInterval()) { 8895b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray DCHECK_EQ(intervals->Get(index), interval->GetHighInterval()); 8905b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray intervals->DeleteAt(index); 8915b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray return true; 8925b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray } else if (interval->IsHighInterval()) { 8935b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray DCHECK_GT(index, 0u); 8945b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray DCHECK_EQ(intervals->Get(index - 1), interval->GetLowInterval()); 8955b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray intervals->DeleteAt(index - 1); 8965b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray return true; 8975b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray } else { 8985b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray return false; 8995b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray } 9005b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray} 9015b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray 902a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// Find the register that is used the last, and spill the interval 903a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// that holds it. If the first use of `current` is after that register 904a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// we spill `current` instead. 905a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) { 906a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t first_register_use = current->FirstRegisterUse(); 907412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray if (first_register_use == kNoLifetime) { 90831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray AllocateSpillSlotFor(current); 909a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 910a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 911a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 9121ba1981ee9d28f87f594b157566d09e973fa5bceNicolas Geoffray // We use the first use to compare with other intervals. If this interval 9131ba1981ee9d28f87f594b157566d09e973fa5bceNicolas Geoffray // is used after any active intervals, we will spill this interval. 9141ba1981ee9d28f87f594b157566d09e973fa5bceNicolas Geoffray size_t first_use = current->FirstUseAfter(current->GetStart()); 9151ba1981ee9d28f87f594b157566d09e973fa5bceNicolas Geoffray 916a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // First set all registers as not being used. 917a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t* next_use = registers_array_; 918a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 919a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray next_use[i] = kMaxLifetimePosition; 920a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 921a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 922a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each active interval, find the next use of its register after the 923a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // start of current. 924a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = active_.Size(); i < e; ++i) { 925a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* active = active_.Get(i); 926a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(active->HasRegister()); 92786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (active->IsFixed()) { 92886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[active->GetRegister()] = current->GetStart(); 92986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 9301ba1981ee9d28f87f594b157566d09e973fa5bceNicolas Geoffray size_t use = active->FirstUseAfter(current->GetStart()); 93186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (use != kNoLifetime) { 93286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[active->GetRegister()] = use; 93386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 934a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 935a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 936a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 937a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each inactive interval, find the next use of its register after the 938a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // start of current. 939a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { 940a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* inactive = inactive_.Get(i); 941296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Temp/Slow-path-safepoint interval has no holes. 942296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK(!inactive->IsTemp() && !inactive->IsSlowPathSafepoint()); 943296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang if (!current->IsSplit() && !inactive->IsFixed()) { 944296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Neither current nor inactive are fixed. 945296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Thanks to SSA, a non-split interval starting in a hole of an 946296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // inactive interval should never intersect with that inactive interval. 947296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Only if it's not fixed though, because fixed intervals don't come from SSA. 948296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime); 949296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang continue; 950296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 951a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(inactive->HasRegister()); 95286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t next_intersection = inactive->FirstIntersectionWith(current); 95386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (next_intersection != kNoLifetime) { 95486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (inactive->IsFixed()) { 95586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[inactive->GetRegister()] = 95686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray std::min(next_intersection, next_use[inactive->GetRegister()]); 95786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 9581ba1981ee9d28f87f594b157566d09e973fa5bceNicolas Geoffray size_t use = inactive->FirstUseAfter(current->GetStart()); 95986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (use != kNoLifetime) { 96086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[inactive->GetRegister()] = std::min(use, next_use[inactive->GetRegister()]); 96186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 96286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 963a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 964a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 965a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 9666c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray int reg = kNoRegister; 9676c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray bool should_spill = false; 968840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (current->HasRegister()) { 969840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(current->IsHighInterval()); 970840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray reg = current->GetRegister(); 9716c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // When allocating the low part, we made sure the high register was available. 9721ba1981ee9d28f87f594b157566d09e973fa5bceNicolas Geoffray DCHECK_LT(first_use, next_use[reg]); 973840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (current->IsLowInterval()) { 974234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray reg = FindAvailableRegisterPair(next_use, first_register_use); 9756c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // We should spill if both registers are not available. 9761ba1981ee9d28f87f594b157566d09e973fa5bceNicolas Geoffray should_spill = (first_use >= next_use[reg]) 9771ba1981ee9d28f87f594b157566d09e973fa5bceNicolas Geoffray || (first_use >= next_use[GetHighForLowRegister(reg)]); 978840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else { 979840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(!current->IsHighInterval()); 980840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray reg = FindAvailableRegister(next_use); 9811ba1981ee9d28f87f594b157566d09e973fa5bceNicolas Geoffray should_spill = (first_use >= next_use[reg]); 982a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 983a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 9846c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK_NE(reg, kNoRegister); 9856c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (should_spill) { 986840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(!current->IsHighInterval()); 987234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray bool is_allocation_at_use_site = (current->GetStart() >= (first_register_use - 1)); 9886c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (current->IsLowInterval() 9896c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray && is_allocation_at_use_site 990234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray && TrySplitNonPairOrUnalignedPairIntervalAt(current->GetStart(), 991234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray first_register_use, 992234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray next_use)) { 9936c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // If we're allocating a register for `current` because the instruction at 9946c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // that position requires it, but we think we should spill, then there are 995234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray // non-pair intervals or unaligned pair intervals blocking the allocation. 996234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray // We split the first interval found, and put ourselves first in the 997234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray // `unhandled_` list. 9986c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray LiveInterval* existing = unhandled_->Peek(); 9996c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(existing->IsHighInterval()); 10006c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK_EQ(existing->GetLowInterval(), current); 10016c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray unhandled_->Add(current); 10026c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } else { 10036c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // If the first use of that instruction is after the last use of the found 10046c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // register, we split this interval just before its first register use. 10056c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray AllocateSpillSlotFor(current); 10068cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray LiveInterval* split = SplitBetween(current, current->GetStart(), first_register_use - 1); 1007234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray if (current == split) { 1008234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray DumpInterval(std::cerr, current); 1009234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray DumpAllIntervals(std::cerr); 1010234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray // This situation has the potential to infinite loop, so we make it a non-debug CHECK. 10111ba1981ee9d28f87f594b157566d09e973fa5bceNicolas Geoffray HInstruction* at = liveness_.GetInstructionFromPosition(first_register_use / 2); 1012234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray CHECK(false) << "There is not enough registers available for " 1013234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray << split->GetParent()->GetDefinedBy()->DebugName() << " " 1014234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray << split->GetParent()->GetDefinedBy()->GetId() 10151ba1981ee9d28f87f594b157566d09e973fa5bceNicolas Geoffray << " at " << first_register_use - 1 << " " 10161ba1981ee9d28f87f594b157566d09e973fa5bceNicolas Geoffray << (at == nullptr ? "" : at->DebugName()); 1017234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray } 10186c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray AddSorted(unhandled_, split); 10196c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 1020a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 1021a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 1022a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Use this register and spill the active and inactives interval that 1023a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // have that register. 1024a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray current->SetRegister(reg); 1025a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1026a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = active_.Size(); i < e; ++i) { 1027a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* active = active_.Get(i); 1028a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (active->GetRegister() == reg) { 102986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(!active->IsFixed()); 1030a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* split = Split(active, current->GetStart()); 1031dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray if (split != active) { 1032dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray handled_.Add(active); 1033dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray } 10345b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray active_.DeleteAt(i); 10355b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray PotentiallyRemoveOtherHalf(active, &active_, i); 10363946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 1037a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray break; 1038a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1039a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1040a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 10415b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray for (size_t i = 0; i < inactive_.Size(); ++i) { 1042a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* inactive = inactive_.Get(i); 1043a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (inactive->GetRegister() == reg) { 1044296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang if (!current->IsSplit() && !inactive->IsFixed()) { 1045296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Neither current nor inactive are fixed. 1046296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Thanks to SSA, a non-split interval starting in a hole of an 1047296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // inactive interval should never intersect with that inactive interval. 1048296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Only if it's not fixed though, because fixed intervals don't come from SSA. 1049296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime); 1050296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang continue; 1051296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 105286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t next_intersection = inactive->FirstIntersectionWith(current); 105386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (next_intersection != kNoLifetime) { 105486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (inactive->IsFixed()) { 105586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* split = Split(current, next_intersection); 1056dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray DCHECK_NE(split, current); 10573946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 105886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 1059dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray // Split at the start of `current`, which will lead to splitting 1060dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray // at the end of the lifetime hole of `inactive`. 1061dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray LiveInterval* split = Split(inactive, current->GetStart()); 1062dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray // If it's inactive, it must start before the current interval. 1063dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray DCHECK_NE(split, inactive); 106486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray inactive_.DeleteAt(i); 10655b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray if (PotentiallyRemoveOtherHalf(inactive, &inactive_, i) && inactive->IsHighInterval()) { 10665b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray // We have removed an entry prior to `inactive`. So we need to decrement. 10675b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray --i; 10685b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray } 10695b168deeae2c5a8a566ce5c140741f0e2227af21Nicolas Geoffray // Decrement because we have removed `inactive` from the list. 1070296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang --i; 107186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray handled_.Add(inactive); 10723946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 107386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 107486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 1075a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1076a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1077a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1078a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 1079a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1080a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 1081a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 10823946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffrayvoid RegisterAllocator::AddSorted(GrowableArray<LiveInterval*>* array, LiveInterval* interval) { 1083c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray DCHECK(!interval->IsFixed() && !interval->HasSpillSlot()); 108486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t insert_at = 0; 10853946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = array->Size(); i > 0; --i) { 10863946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* current = array->Get(i - 1); 10876c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // High intervals must be processed right after their low equivalent. 10886c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (current->StartsAfter(interval) && !current->IsHighInterval()) { 108986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray insert_at = i; 1090a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray break; 1091acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray } else if ((current->GetStart() == interval->GetStart()) && current->IsSlowPathSafepoint()) { 1092acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray // Ensure the slow path interval is the last to be processed at its location: we want the 1093acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray // interval to know all live registers at this location. 1094acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray DCHECK(i == 1 || array->Get(i - 2)->StartsAfter(current)); 1095acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray insert_at = i; 1096acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray break; 1097a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1098a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1099840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 11003946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray array->InsertAt(insert_at, interval); 1101840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // Insert the high interval before the low, to ensure the low is processed before. 1102840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (interval->HasHighInterval()) { 1103840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray array->InsertAt(insert_at, interval->GetHighInterval()); 1104840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (interval->HasLowInterval()) { 1105840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray array->InsertAt(insert_at + 1, interval->GetLowInterval()); 1106840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 1107a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 1108a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 11098cbab3c4de3328b576454ce702d7748f56c44346Nicolas GeoffrayLiveInterval* RegisterAllocator::SplitBetween(LiveInterval* interval, size_t from, size_t to) { 1110fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray HBasicBlock* block_from = liveness_.GetBlockFromPosition(from / 2); 1111fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray HBasicBlock* block_to = liveness_.GetBlockFromPosition(to / 2); 11128cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray DCHECK(block_from != nullptr); 11138cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray DCHECK(block_to != nullptr); 11148cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray 11158cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray // Both locations are in the same block. We split at the given location. 11168cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray if (block_from == block_to) { 11178cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray return Split(interval, to); 11188cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray } 11198cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray 1120fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray /* 1121fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * Non-linear control flow will force moves at every branch instruction to the new location. 1122fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * To avoid having all branches doing the moves, we find the next non-linear position and 1123fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * split the interval at this position. Take the following example (block number is the linear 1124fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * order position): 1125fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * 1126fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * B1 1127fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * / \ 1128fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * B2 B3 1129fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * \ / 1130fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * B4 1131fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * 1132fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * B2 needs to split an interval, whose next use is in B4. If we were to split at the 1133fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * beginning of B4, B3 would need to do a move between B3 and B4 to ensure the interval 1134fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * is now in the correct location. It makes performance worst if the interval is spilled 1135fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * and both B2 and B3 need to reload it before entering B4. 1136fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * 1137fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * By splitting at B3, we give a chance to the register allocator to allocate the 1138fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * interval to the same register as in B1, and therefore avoid doing any 1139fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray * moves in B3. 1140fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray */ 1141fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray if (block_from->GetDominator() != nullptr) { 1142fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray const GrowableArray<HBasicBlock*>& dominated = block_from->GetDominator()->GetDominatedBlocks(); 1143fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray for (size_t i = 0; i < dominated.Size(); ++i) { 1144fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray size_t position = dominated.Get(i)->GetLifetimeStart(); 1145fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray if ((position > from) && (block_to->GetLifetimeStart() > position)) { 1146fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray // Even if we found a better block, we continue iterating in case 1147fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray // a dominated block is closer. 1148fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray // Note that dominated blocks are not sorted in liveness order. 1149fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray block_to = dominated.Get(i); 1150fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray DCHECK_NE(block_to, block_from); 1151fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray } 1152fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray } 1153fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray } 1154fbda5f3e1378f07ae202f62da625ee43a063a052Nicolas Geoffray 11558cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray // If `to` is in a loop, find the outermost loop header which does not contain `from`. 11568cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray for (HLoopInformationOutwardIterator it(*block_to); !it.Done(); it.Advance()) { 11578cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray HBasicBlock* header = it.Current()->GetHeader(); 11588cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray if (block_from->GetLifetimeStart() >= header->GetLifetimeStart()) { 11598cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray break; 11608cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray } 11618cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray block_to = header; 11628cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray } 11638cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray 11648cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray // Split at the start of the found block, to piggy back on existing moves 11658cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray // due to resolution if non-linear control flow (see `ConnectSplitSiblings`). 11668cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray return Split(interval, block_to->GetLifetimeStart()); 11678cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray} 11688cbab3c4de3328b576454ce702d7748f56c44346Nicolas Geoffray 1169a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas GeoffrayLiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) { 1170840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK_GE(position, interval->GetStart()); 1171a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(!interval->IsDeadAt(position)); 1172a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (position == interval->GetStart()) { 1173a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Spill slot will be allocated when handling `interval` again. 1174a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray interval->ClearRegister(); 1175840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (interval->HasHighInterval()) { 1176840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray interval->GetHighInterval()->ClearRegister(); 1177840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (interval->HasLowInterval()) { 1178840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray interval->GetLowInterval()->ClearRegister(); 1179840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 1180a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return interval; 1181a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 1182a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* new_interval = interval->SplitAt(position); 1183840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (interval->HasHighInterval()) { 1184840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray LiveInterval* high = interval->GetHighInterval()->SplitAt(position); 1185840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray new_interval->SetHighInterval(high); 1186840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray high->SetLowInterval(new_interval); 1187840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (interval->HasLowInterval()) { 1188840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray LiveInterval* low = interval->GetLowInterval()->SplitAt(position); 1189840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray new_interval->SetLowInterval(low); 1190840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray low->SetHighInterval(new_interval); 1191840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 1192a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return new_interval; 1193a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1194a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 1195a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 119631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffrayvoid RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) { 1197840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (interval->IsHighInterval()) { 1198840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // The low interval will contain the spill slot. 1199840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return; 1200840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 1201840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 120231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* parent = interval->GetParent(); 120331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 120431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // An instruction gets a spill slot for its entire lifetime. If the parent 120531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // of this interval already has a spill slot, there is nothing to do. 120631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (parent->HasSpillSlot()) { 120731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray return; 120831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 120931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 121086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* defined_by = parent->GetDefinedBy(); 121186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (defined_by->IsParameterValue()) { 121286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Parameters have their own stack slot. 121386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray parent->SetSpillSlot(codegen_->GetStackSlotOfParameter(defined_by->AsParameterValue())); 121486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 121586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 121686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 121796f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray if (defined_by->IsConstant()) { 121896f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray // Constants don't need a spill slot. 121996f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray return; 122096f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray } 122196f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray 122231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* last_sibling = interval; 122331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray while (last_sibling->GetNextSibling() != nullptr) { 122431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray last_sibling = last_sibling->GetNextSibling(); 122531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 122631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray size_t end = last_sibling->GetEnd(); 122731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 1228776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray GrowableArray<size_t>* spill_slots = nullptr; 1229776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray switch (interval->GetType()) { 1230776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimDouble: 1231776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots = &double_spill_slots_; 1232776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray break; 1233776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimLong: 1234776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots = &long_spill_slots_; 1235776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray break; 1236776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimFloat: 1237776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots = &float_spill_slots_; 1238776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray break; 1239776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimNot: 1240776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimInt: 1241776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimChar: 1242776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimByte: 1243776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimBoolean: 1244776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimShort: 1245776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots = &int_spill_slots_; 1246776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray break; 1247776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimVoid: 1248776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray LOG(FATAL) << "Unexpected type for interval " << interval->GetType(); 1249776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray } 1250776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray 1251412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // Find an available spill slot. 1252412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray size_t slot = 0; 1253776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray for (size_t e = spill_slots->Size(); slot < e; ++slot) { 1254776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray if (spill_slots->Get(slot) <= parent->GetStart() 1255776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray && (slot == (e - 1) || spill_slots->Get(slot + 1) <= parent->GetStart())) { 1256412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray break; 1257412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } 1258412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } 1259412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray 126001ef345767ea609417fc511e42007705c9667546Nicolas Geoffray if (parent->NeedsTwoSpillSlots()) { 1261776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray if (slot == spill_slots->Size()) { 12623c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray // We need a new spill slot. 1263776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots->Add(end); 1264776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots->Add(end); 1265776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray } else if (slot == spill_slots->Size() - 1) { 1266776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots->Put(slot, end); 1267776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots->Add(end); 12683c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray } else { 1269776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots->Put(slot, end); 1270776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots->Put(slot + 1, end); 127131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 127231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 1273776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray if (slot == spill_slots->Size()) { 12743c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray // We need a new spill slot. 1275776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots->Add(end); 12763c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray } else { 1277776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots->Put(slot, end); 12783c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray } 127931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 128031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 1281776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // Note that the exact spill slot location will be computed when we resolve, 1282776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // that is when we know the number of spill slots for each type. 1283776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray parent->SetSpillSlot(slot); 128486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 128586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 12862a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffraystatic bool IsValidDestination(Location destination) { 1287102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return destination.IsRegister() 12886c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray || destination.IsRegisterPair() 1289102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray || destination.IsFpuRegister() 1290840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray || destination.IsFpuRegisterPair() 1291102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray || destination.IsStackSlot() 1292102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray || destination.IsDoubleStackSlot(); 12932a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray} 12942a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray 1295234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffrayvoid RegisterAllocator::AddMove(HParallelMove* move, 1296234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray Location source, 1297234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray Location destination, 1298234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray HInstruction* instruction, 1299234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray Primitive::Type type) const { 1300234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray if (type == Primitive::kPrimLong 1301234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray && codegen_->ShouldSplitLongMoves() 1302234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray // The parallel move resolver knows how to deal with long constants. 1303234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray && !source.IsConstant()) { 13049021825d1e73998b99c81e89c73796f6f2845471Nicolas Geoffray move->AddMove(source.ToLow(), destination.ToLow(), Primitive::kPrimInt, instruction); 13059021825d1e73998b99c81e89c73796f6f2845471Nicolas Geoffray move->AddMove(source.ToHigh(), destination.ToHigh(), Primitive::kPrimInt, nullptr); 1306234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray } else { 13079021825d1e73998b99c81e89c73796f6f2845471Nicolas Geoffray move->AddMove(source, destination, type, instruction); 1308234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray } 1309234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray} 1310234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray 1311234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffrayvoid RegisterAllocator::AddInputMoveFor(HInstruction* input, 1312234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray HInstruction* user, 131386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 131486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 131586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 131686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1317476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain DCHECK(!user->IsPhi()); 131886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1319740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray HInstruction* previous = user->GetPrevious(); 132086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move = nullptr; 132186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (previous == nullptr 1322476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain || !previous->IsParallelMove() 13238e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray || previous->GetLifetimePosition() < user->GetLifetimePosition()) { 132486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 13258e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray move->SetLifetimePosition(user->GetLifetimePosition()); 1326740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray user->GetBlock()->InsertInstructionBefore(move, user); 132786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 132886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = previous->AsParallelMove(); 132986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 13308e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray DCHECK_EQ(move->GetLifetimePosition(), user->GetLifetimePosition()); 1331234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray AddMove(move, source, destination, nullptr, input->GetType()); 133286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 133386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 133446fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffraystatic bool IsInstructionStart(size_t position) { 133546fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray return (position & 1) == 0; 133646fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray} 133746fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray 133846fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffraystatic bool IsInstructionEnd(size_t position) { 133946fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray return (position & 1) == 1; 134046fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray} 134146fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray 134286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertParallelMoveAt(size_t position, 1343740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray HInstruction* instruction, 134486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 134586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 13466c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(IsValidDestination(destination)) << destination; 134786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 134886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 134986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* at = liveness_.GetInstructionFromPosition(position / 2); 135086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move; 135146fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray if (at == nullptr) { 135246fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray if (IsInstructionStart(position)) { 135346fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray // Block boundary, don't do anything the connection of split siblings will handle it. 135446fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray return; 135546fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray } else { 135646fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray // Move must happen before the first instruction of the block. 135746fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray at = liveness_.GetInstructionFromPosition((position + 1) / 2); 13585976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // Note that parallel moves may have already been inserted, so we explicitly 13595976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // ask for the first instruction of the block: `GetInstructionFromPosition` does 1360234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray // not contain the `HParallelMove` instructions. 13615976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray at = at->GetBlock()->GetFirstInstruction(); 1362234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray 1363234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray if (at->GetLifetimePosition() < position) { 1364234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray // We may insert moves for split siblings and phi spills at the beginning of the block. 1365234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray // Since this is a different lifetime position, we need to go to the next instruction. 1366234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray DCHECK(at->IsParallelMove()); 1367234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray at = at->GetNext(); 1368234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray } 1369234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray 13705976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray if (at->GetLifetimePosition() != position) { 13715976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray DCHECK_GT(at->GetLifetimePosition(), position); 137246fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 137346fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray move->SetLifetimePosition(position); 137446fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray at->GetBlock()->InsertInstructionBefore(move, at); 13755976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray } else { 13765976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray DCHECK(at->IsParallelMove()); 13775976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray move = at->AsParallelMove(); 137846fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray } 137946fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray } 138046fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray } else if (IsInstructionEnd(position)) { 138186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Move must happen after the instruction. 138286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(!at->IsControlFlow()); 138386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = at->GetNext()->AsParallelMove(); 1384e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting siblings in a same block. We need to 1385e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // differentiate it with moves for connecting blocks, and input moves. 13868e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray if (move == nullptr || move->GetLifetimePosition() > position) { 138786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 138886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->SetLifetimePosition(position); 138986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray at->GetBlock()->InsertInstructionBefore(move, at->GetNext()); 139086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 139186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 139286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Move must happen before the instruction. 139386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* previous = at->GetPrevious(); 1394740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray if (previous == nullptr 1395740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray || !previous->IsParallelMove() 1396740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray || previous->GetLifetimePosition() != position) { 1397740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray // If the previous is a parallel move, then its position must be lower 1398740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray // than the given `position`: it was added just after the non-parallel 1399740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray // move instruction that precedes `instruction`. 1400740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray DCHECK(previous == nullptr 1401740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray || !previous->IsParallelMove() 1402740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray || previous->GetLifetimePosition() < position); 140386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 140486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->SetLifetimePosition(position); 140586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray at->GetBlock()->InsertInstructionBefore(move, at); 140686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 140786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = previous->AsParallelMove(); 140886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 140986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 141001ef345767ea609417fc511e42007705c9667546Nicolas Geoffray DCHECK_EQ(move->GetLifetimePosition(), position); 1411234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray AddMove(move, source, destination, instruction, instruction->GetType()); 141286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 141386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 141486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertParallelMoveAtExitOf(HBasicBlock* block, 1415740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray HInstruction* instruction, 141686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 141786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 14186c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(IsValidDestination(destination)) << destination; 141986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 142086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 142186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK_EQ(block->GetSuccessors().Size(), 1u); 142286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* last = block->GetLastInstruction(); 1423360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray // We insert moves at exit for phi predecessors and connecting blocks. 1424360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray // A block ending with an if cannot branch to a block with phis because 1425360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray // we do not allow critical edges. It can also not connect 1426360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray // a split interval between two blocks: the move has to happen in the successor. 1427360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray DCHECK(!last->IsIf()); 142886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* previous = last->GetPrevious(); 142986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move; 1430e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting blocks. We need to differentiate 1431e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // it with moves for connecting siblings in a same block, and output moves. 14325976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray size_t position = last->GetLifetimePosition(); 1433740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray if (previous == nullptr || !previous->IsParallelMove() 14345976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray || previous->AsParallelMove()->GetLifetimePosition() != position) { 143586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 14365976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray move->SetLifetimePosition(position); 143786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray block->InsertInstructionBefore(move, last); 143886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 143986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = previous->AsParallelMove(); 144086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 1441234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray AddMove(move, source, destination, instruction, instruction->GetType()); 144286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 144386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 144486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertParallelMoveAtEntryOf(HBasicBlock* block, 1445740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray HInstruction* instruction, 144686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 144786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 14486c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(IsValidDestination(destination)) << destination; 144986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 145086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 145186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* first = block->GetFirstInstruction(); 145286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move = first->AsParallelMove(); 1453234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray size_t position = block->GetLifetimeStart(); 1454e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting blocks. We need to differentiate 1455e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // it with moves for connecting siblings in a same block, and input moves. 1456234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray if (move == nullptr || move->GetLifetimePosition() != position) { 145786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 1458234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray move->SetLifetimePosition(position); 145986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray block->InsertInstructionBefore(move, first); 146086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 1461234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray AddMove(move, source, destination, instruction, instruction->GetType()); 146286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 146386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 146486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertMoveAfter(HInstruction* instruction, 146586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 146686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 14676c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(IsValidDestination(destination)) << destination; 146886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 146986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1470476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain if (instruction->IsPhi()) { 1471740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAtEntryOf(instruction->GetBlock(), instruction, source, destination); 147286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 147386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 147486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1475e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray size_t position = instruction->GetLifetimePosition() + 1; 147686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move = instruction->GetNext()->AsParallelMove(); 1477e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for moving the output of an instruction. We need 1478e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // to differentiate with input moves, moves for connecting siblings in a 1479e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // and moves for connecting blocks. 1480e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray if (move == nullptr || move->GetLifetimePosition() != position) { 148186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 1482e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray move->SetLifetimePosition(position); 148386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray instruction->GetBlock()->InsertInstructionBefore(move, instruction->GetNext()); 148486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 1485234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray AddMove(move, source, destination, instruction, instruction->GetType()); 148686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 148786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 148886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::ConnectSiblings(LiveInterval* interval) { 148986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = interval; 149086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->HasSpillSlot() && current->HasRegister()) { 149186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // We spill eagerly, so move must be at definition. 149286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InsertMoveAfter(interval->GetDefinedBy(), 1493840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray interval->ToLocation(), 149401ef345767ea609417fc511e42007705c9667546Nicolas Geoffray interval->NeedsTwoSpillSlots() 1495412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray ? Location::DoubleStackSlot(interval->GetParent()->GetSpillSlot()) 1496412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray : Location::StackSlot(interval->GetParent()->GetSpillSlot())); 149786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 149886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray UsePosition* use = current->GetFirstUse(); 14994ed947a58de87d19d0609be773207c905ccb0f7fNicolas Geoffray UsePosition* env_use = current->GetFirstEnvironmentUse(); 150086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 150186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Walk over all siblings, updating locations of use positions, and 150286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // connecting them when they are adjacent. 150386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray do { 150401ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location source = current->ToLocation(); 150586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 150686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Walk over all uses covered by this interval, and update the location 150786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // information. 1508d8126bef62df7f40f2e6abc74004f52e664daf45Nicolas Geoffray 1509d8126bef62df7f40f2e6abc74004f52e664daf45Nicolas Geoffray LiveRange* range = current->GetFirstRange(); 1510d8126bef62df7f40f2e6abc74004f52e664daf45Nicolas Geoffray while (range != nullptr) { 1511579026039080252878106118645ed70706f4838eNicolas Geoffray while (use != nullptr && use->GetPosition() < range->GetStart()) { 1512579026039080252878106118645ed70706f4838eNicolas Geoffray DCHECK(use->IsSynthesized()); 1513579026039080252878106118645ed70706f4838eNicolas Geoffray use = use->GetNext(); 1514579026039080252878106118645ed70706f4838eNicolas Geoffray } 1515d8126bef62df7f40f2e6abc74004f52e664daf45Nicolas Geoffray while (use != nullptr && use->GetPosition() <= range->GetEnd()) { 15164ed947a58de87d19d0609be773207c905ccb0f7fNicolas Geoffray DCHECK(!use->GetIsEnvironment()); 15173fc992f9dfe8f49ff350132323cc635f102b7b62David Brazdil DCHECK(current->CoversSlow(use->GetPosition()) || (use->GetPosition() == range->GetEnd())); 1518579026039080252878106118645ed70706f4838eNicolas Geoffray if (!use->IsSynthesized()) { 1519579026039080252878106118645ed70706f4838eNicolas Geoffray LocationSummary* locations = use->GetUser()->GetLocations(); 1520579026039080252878106118645ed70706f4838eNicolas Geoffray Location expected_location = locations->InAt(use->GetInputIndex()); 1521579026039080252878106118645ed70706f4838eNicolas Geoffray // The expected (actual) location may be invalid in case the input is unused. Currently 1522579026039080252878106118645ed70706f4838eNicolas Geoffray // this only happens for intrinsics. 1523579026039080252878106118645ed70706f4838eNicolas Geoffray if (expected_location.IsValid()) { 1524579026039080252878106118645ed70706f4838eNicolas Geoffray if (expected_location.IsUnallocated()) { 1525579026039080252878106118645ed70706f4838eNicolas Geoffray locations->SetInAt(use->GetInputIndex(), source); 1526579026039080252878106118645ed70706f4838eNicolas Geoffray } else if (!expected_location.IsConstant()) { 1527579026039080252878106118645ed70706f4838eNicolas Geoffray AddInputMoveFor(interval->GetDefinedBy(), use->GetUser(), source, expected_location); 1528579026039080252878106118645ed70706f4838eNicolas Geoffray } 1529579026039080252878106118645ed70706f4838eNicolas Geoffray } else { 1530579026039080252878106118645ed70706f4838eNicolas Geoffray DCHECK(use->GetUser()->IsInvoke()); 1531579026039080252878106118645ed70706f4838eNicolas Geoffray DCHECK(use->GetUser()->AsInvoke()->GetIntrinsic() != Intrinsics::kNone); 1532d8126bef62df7f40f2e6abc74004f52e664daf45Nicolas Geoffray } 153386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 1534d8126bef62df7f40f2e6abc74004f52e664daf45Nicolas Geoffray use = use->GetNext(); 153586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 15364ed947a58de87d19d0609be773207c905ccb0f7fNicolas Geoffray 15374ed947a58de87d19d0609be773207c905ccb0f7fNicolas Geoffray // Walk over the environment uses, and update their locations. 15384ed947a58de87d19d0609be773207c905ccb0f7fNicolas Geoffray while (env_use != nullptr && env_use->GetPosition() < range->GetStart()) { 15394ed947a58de87d19d0609be773207c905ccb0f7fNicolas Geoffray env_use = env_use->GetNext(); 15404ed947a58de87d19d0609be773207c905ccb0f7fNicolas Geoffray } 15414ed947a58de87d19d0609be773207c905ccb0f7fNicolas Geoffray 15424ed947a58de87d19d0609be773207c905ccb0f7fNicolas Geoffray while (env_use != nullptr && env_use->GetPosition() <= range->GetEnd()) { 15430a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray DCHECK(current->CoversSlow(env_use->GetPosition()) 15440a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray || (env_use->GetPosition() == range->GetEnd())); 15450a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray HEnvironment* environment = env_use->GetUser()->GetEnvironment(); 15460a23d74dc2751440822960eab218be4cb8843647Nicolas Geoffray environment->SetLocationAt(env_use->GetInputIndex(), source); 15474ed947a58de87d19d0609be773207c905ccb0f7fNicolas Geoffray env_use = env_use->GetNext(); 15484ed947a58de87d19d0609be773207c905ccb0f7fNicolas Geoffray } 15494ed947a58de87d19d0609be773207c905ccb0f7fNicolas Geoffray 1550d8126bef62df7f40f2e6abc74004f52e664daf45Nicolas Geoffray range = range->GetNext(); 155186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 155286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 155386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // If the next interval starts just after this one, and has a register, 155486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // insert a move. 155586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* next_sibling = current->GetNextSibling(); 155686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (next_sibling != nullptr 155786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && next_sibling->HasRegister() 155886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && current->GetEnd() == next_sibling->GetStart()) { 155901ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location destination = next_sibling->ToLocation(); 1560740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAt(current->GetEnd(), interval->GetDefinedBy(), source, destination); 156186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 15623946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 156343af728a3ccecb5f0eacef85f44d70df3d4c40f9Nicolas Geoffray for (SafepointPosition* safepoint_position = current->GetFirstSafepoint(); 156443af728a3ccecb5f0eacef85f44d70df3d4c40f9Nicolas Geoffray safepoint_position != nullptr; 156543af728a3ccecb5f0eacef85f44d70df3d4c40f9Nicolas Geoffray safepoint_position = safepoint_position->GetNext()) { 15663fc992f9dfe8f49ff350132323cc635f102b7b62David Brazdil DCHECK(current->CoversSlow(safepoint_position->GetPosition())); 15673946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 15685588e588144fffc978845a2c9c915a0044565a03Nicolas Geoffray LocationSummary* locations = safepoint_position->GetLocations(); 15693bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray if ((current->GetType() == Primitive::kPrimNot) && current->GetParent()->HasSpillSlot()) { 15703946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray locations->SetStackBit(current->GetParent()->GetSpillSlot() / kVRegSize); 15713946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 15723946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 15733946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray switch (source.GetKind()) { 15743946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kRegister: { 15753bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray locations->AddLiveRegister(source); 1576988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray if (kIsDebugBuild && locations->OnlyCallsOnSlowPath()) { 1577988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray DCHECK_LE(locations->GetNumberOfLiveRegisters(), 1578988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray maximum_number_of_live_core_registers_ + 1579988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray maximum_number_of_live_fp_registers_); 1580988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray } 15813946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current->GetType() == Primitive::kPrimNot) { 158256b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray locations->SetRegisterBit(source.reg()); 15833946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 15843946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray break; 15853946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 1586102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray case Location::kFpuRegister: { 1587102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray locations->AddLiveRegister(source); 1588102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray break; 1589102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 15906c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray 15916c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray case Location::kRegisterPair: 1592840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray case Location::kFpuRegisterPair: { 1593840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray locations->AddLiveRegister(source.ToLow()); 1594840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray locations->AddLiveRegister(source.ToHigh()); 1595840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray break; 1596840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 15973946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kStackSlot: // Fall-through 15983946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kDoubleStackSlot: // Fall-through 15993946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kConstant: { 16003946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Nothing to do. 16013946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray break; 16023946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 16033946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray default: { 16043946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LOG(FATAL) << "Unexpected location for object"; 16053946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 16063946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 16073946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 160886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current = next_sibling; 160986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } while (current != nullptr); 1610d8126bef62df7f40f2e6abc74004f52e664daf45Nicolas Geoffray 1611579026039080252878106118645ed70706f4838eNicolas Geoffray if (kIsDebugBuild) { 1612579026039080252878106118645ed70706f4838eNicolas Geoffray // Following uses can only be synthesized uses. 1613579026039080252878106118645ed70706f4838eNicolas Geoffray while (use != nullptr) { 1614579026039080252878106118645ed70706f4838eNicolas Geoffray DCHECK(use->IsSynthesized()); 1615579026039080252878106118645ed70706f4838eNicolas Geoffray use = use->GetNext(); 1616579026039080252878106118645ed70706f4838eNicolas Geoffray } 1617579026039080252878106118645ed70706f4838eNicolas Geoffray } 161886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 161986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 162086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval, 162186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* from, 162286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* to) const { 162386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (interval->GetNextSibling() == nullptr) { 162486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Nothing to connect. The whole range was allocated to the same location. 162586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 162686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 162786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1628241a486267bdb59b32fe4c8db370eb936068fb39David Brazdil // Find the intervals that cover `from` and `to`. 1629241a486267bdb59b32fe4c8db370eb936068fb39David Brazdil LiveInterval* destination = interval->GetSiblingAt(to->GetLifetimeStart()); 1630241a486267bdb59b32fe4c8db370eb936068fb39David Brazdil LiveInterval* source = interval->GetSiblingAt(from->GetLifetimeEnd() - 1); 163186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 163286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (destination == source) { 163386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Interval was not split. 163486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 163586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 16368ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray DCHECK(destination != nullptr && source != nullptr); 16378ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray 163886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (!destination->HasRegister()) { 163986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Values are eagerly spilled. Spill slot already contains appropriate value. 164086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 164186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 164286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 164386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // If `from` has only one successor, we can put the moves at the exit of it. Otherwise 164486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // we need to put the moves at the entry of `to`. 164586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (from->GetSuccessors().Size() == 1) { 1646740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAtExitOf(from, 1647740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray interval->GetParent()->GetDefinedBy(), 164801ef345767ea609417fc511e42007705c9667546Nicolas Geoffray source->ToLocation(), 164901ef345767ea609417fc511e42007705c9667546Nicolas Geoffray destination->ToLocation()); 165086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 165186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK_EQ(to->GetPredecessors().Size(), 1u); 1652740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAtEntryOf(to, 1653740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray interval->GetParent()->GetDefinedBy(), 165401ef345767ea609417fc511e42007705c9667546Nicolas Geoffray source->ToLocation(), 165501ef345767ea609417fc511e42007705c9667546Nicolas Geoffray destination->ToLocation()); 165686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 165786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 165886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 165986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::Resolve() { 1660776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray codegen_->InitializeCodeGeneration(GetNumberOfSpillSlots(), 16614c204bafbc8d596894f8cb8ec696f5be1c6f12d8Nicolas Geoffray maximum_number_of_live_core_registers_, 16624c204bafbc8d596894f8cb8ec696f5be1c6f12d8Nicolas Geoffray maximum_number_of_live_fp_registers_, 16634c204bafbc8d596894f8cb8ec696f5be1c6f12d8Nicolas Geoffray reserved_out_slots_, 16640d9f17de8f21a10702de1510b73e89d07b3b9bbfNicolas Geoffray codegen_->GetGraph()->GetLinearOrder()); 166586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 166686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Adjust the Out Location of instructions. 166786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // TODO: Use pointers of Location inside LiveInterval to avoid doing another iteration. 166886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { 166986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 167086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = instruction->GetLiveInterval(); 167186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LocationSummary* locations = instruction->GetLocations(); 167286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location location = locations->Out(); 1673476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain if (instruction->IsParameterValue()) { 167486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Now that we know the frame size, adjust the parameter's location. 167586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (location.IsStackSlot()) { 167686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray location = Location::StackSlot(location.GetStackIndex() + codegen_->GetFrameSize()); 167786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(location.GetStackIndex()); 1678f43083d560565aea46c602adb86423daeefe589dNicolas Geoffray locations->UpdateOut(location); 167986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else if (location.IsDoubleStackSlot()) { 168086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray location = Location::DoubleStackSlot(location.GetStackIndex() + codegen_->GetFrameSize()); 168186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(location.GetStackIndex()); 1682f43083d560565aea46c602adb86423daeefe589dNicolas Geoffray locations->UpdateOut(location); 168386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else if (current->HasSpillSlot()) { 168486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(current->GetSpillSlot() + codegen_->GetFrameSize()); 168586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 1686776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray } else if (current->HasSpillSlot()) { 1687776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // Adjust the stack slot, now that we know the number of them for each type. 1688776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // The way this implementation lays out the stack is the following: 1689776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // [parameter slots ] 1690776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // [double spill slots ] 1691776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // [long spill slots ] 1692776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // [float spill slots ] 1693776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // [int/ref values ] 1694776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // [maximum out values ] (number of arguments for calls) 1695776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // [art method ]. 1696776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray uint32_t slot = current->GetSpillSlot(); 1697776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray switch (current->GetType()) { 1698776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimDouble: 1699776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray slot += long_spill_slots_.Size(); 1700776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray FALLTHROUGH_INTENDED; 1701776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimLong: 1702776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray slot += float_spill_slots_.Size(); 1703776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray FALLTHROUGH_INTENDED; 1704776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimFloat: 1705776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray slot += int_spill_slots_.Size(); 1706776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray FALLTHROUGH_INTENDED; 1707776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimNot: 1708776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimInt: 1709776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimChar: 1710776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimByte: 1711776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimBoolean: 1712776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimShort: 1713776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray slot += reserved_out_slots_; 1714776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray break; 1715776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimVoid: 1716776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray LOG(FATAL) << "Unexpected type for interval " << current->GetType(); 1717776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray } 1718776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray current->SetSpillSlot(slot * kVRegSize); 171986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 172086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 172101ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location source = current->ToLocation(); 172286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 172386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (location.IsUnallocated()) { 172486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (location.GetPolicy() == Location::kSameAsFirstInput) { 1725d0d4852847432368b090c184d6639e573538dccfCalin Juravle if (locations->InAt(0).IsUnallocated()) { 1726d0d4852847432368b090c184d6639e573538dccfCalin Juravle locations->SetInAt(0, source); 1727d0d4852847432368b090c184d6639e573538dccfCalin Juravle } else { 1728d0d4852847432368b090c184d6639e573538dccfCalin Juravle DCHECK(locations->InAt(0).Equals(source)); 1729d0d4852847432368b090c184d6639e573538dccfCalin Juravle } 173086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 1731829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray locations->UpdateOut(source); 173286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 173386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(source.Equals(location)); 173486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 173586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 173686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 173786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Connect siblings. 173886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { 173986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 174086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ConnectSiblings(instruction->GetLiveInterval()); 174186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 174286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 174386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Resolve non-linear control flow across branches. Order does not matter. 17440d9f17de8f21a10702de1510b73e89d07b3b9bbfNicolas Geoffray for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { 174586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* block = it.Current(); 174686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray BitVector* live = liveness_.GetLiveInSet(*block); 174786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (uint32_t idx : live->Indexes()) { 174886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* current = liveness_.GetInstructionFromSsaIndex(idx); 174986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* interval = current->GetLiveInterval(); 175086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { 175186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ConnectSplitSiblings(interval, block->GetPredecessors().Get(i), block); 175286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 175386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 175486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 175586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 175686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Resolve phi inputs. Order does not matter. 17570d9f17de8f21a10702de1510b73e89d07b3b9bbfNicolas Geoffray for (HLinearOrderIterator it(*codegen_->GetGraph()); !it.Done(); it.Advance()) { 175886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* current = it.Current(); 1759277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe for (HInstructionIterator inst_it(current->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 1760277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe HInstruction* phi = inst_it.Current(); 176186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = current->GetPredecessors().Size(); i < e; ++i) { 176286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* predecessor = current->GetPredecessors().Get(i); 176386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK_EQ(predecessor->GetSuccessors().Size(), 1u); 176486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* input = phi->InputAt(i); 176501ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location source = input->GetLiveInterval()->GetLocationAt( 176601ef345767ea609417fc511e42007705c9667546Nicolas Geoffray predecessor->GetLifetimeEnd() - 1); 176701ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location destination = phi->GetLiveInterval()->ToLocation(); 1768234d69d075d1608f80adb647f7935077b62b6376Nicolas Geoffray InsertParallelMoveAtExitOf(predecessor, phi, source, destination); 176986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 177086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 177186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 17723946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 17733946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Assign temp locations. 17743946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < temp_intervals_.Size(); ++i) { 17753946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* temp = temp_intervals_.Get(i); 1776840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (temp->IsHighInterval()) { 1777840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // High intervals can be skipped, they are already handled by the low interval. 1778840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray continue; 1779840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 178001ef345767ea609417fc511e42007705c9667546Nicolas Geoffray HInstruction* at = liveness_.GetTempUser(temp); 1781f01d34445953e6b9c9b13de1dd32a5c0ee5abab5Nicolas Geoffray size_t temp_index = liveness_.GetTempIndex(temp); 178201ef345767ea609417fc511e42007705c9667546Nicolas Geoffray LocationSummary* locations = at->GetLocations(); 17835368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain switch (temp->GetType()) { 17845368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain case Primitive::kPrimInt: 1785f01d34445953e6b9c9b13de1dd32a5c0ee5abab5Nicolas Geoffray locations->SetTempAt(temp_index, Location::RegisterLocation(temp->GetRegister())); 17865368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain break; 17875368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain 17885368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain case Primitive::kPrimDouble: 1789840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (codegen_->NeedsTwoRegisters(Primitive::kPrimDouble)) { 1790840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray Location location = Location::FpuRegisterPairLocation( 1791840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray temp->GetRegister(), temp->GetHighInterval()->GetRegister()); 1792f01d34445953e6b9c9b13de1dd32a5c0ee5abab5Nicolas Geoffray locations->SetTempAt(temp_index, location); 1793840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else { 1794f01d34445953e6b9c9b13de1dd32a5c0ee5abab5Nicolas Geoffray locations->SetTempAt(temp_index, Location::FpuRegisterLocation(temp->GetRegister())); 1795840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 17965368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain break; 17975368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain 17985368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain default: 17995368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LOG(FATAL) << "Unexpected type for temporary location " 18005368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain << temp->GetType(); 18015368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain } 18023946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 180331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray} 180431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 1805a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} // namespace art 1806