register_allocator.cc revision 776b3184ee04092b11edc781cdb81e8ed60601e3
1a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray/* 2a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * Copyright (C) 2014 The Android Open Source Project 3a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * 4a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * Licensed under the Apache License, Version 2.0 (the "License"); 5a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * you may not use this file except in compliance with the License. 6a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * You may obtain a copy of the License at 7a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * 8a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * http://www.apache.org/licenses/LICENSE-2.0 9a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * 10a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * Unless required by applicable law or agreed to in writing, software 11a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * distributed under the License is distributed on an "AS IS" BASIS, 12a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * See the License for the specific language governing permissions and 14a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray * limitations under the License. 15a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray */ 16a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 17a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray#include "register_allocator.h" 18a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 19c7dd295a4e0cc1d15c0c96088e55a85389bade74Ian Rogers#include <sstream> 20c7dd295a4e0cc1d15c0c96088e55a85389bade74Ian Rogers 21e77493c7217efdd1a0ecef521a6845a13da0305bIan Rogers#include "base/bit_vector-inl.h" 22a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray#include "code_generator.h" 23a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray#include "ssa_liveness_analysis.h" 24a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 25a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraynamespace art { 26a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 27a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraystatic constexpr size_t kMaxLifetimePosition = -1; 2831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffraystatic constexpr size_t kDefaultNumberOfSpillSlots = 4; 29a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 30840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray// For simplicity, we implement register pairs as (reg, reg + 1). 31840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray// Note that this is a requirement for double registers on ARM, since we 32840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray// allocate SRegister. 33840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffraystatic int GetHighForLowRegister(int reg) { return reg + 1; } 34840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffraystatic bool IsLowRegister(int reg) { return (reg & 1) == 0; } 35840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 3686dbb9a12119273039ce272b41c809fa548b37b6Nicolas GeoffrayRegisterAllocator::RegisterAllocator(ArenaAllocator* allocator, 3786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray CodeGenerator* codegen, 3886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray const SsaLivenessAnalysis& liveness) 39a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray : allocator_(allocator), 40a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen_(codegen), 4186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray liveness_(liveness), 423946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_core_intervals_(allocator, 0), 433946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_fp_intervals_(allocator, 0), 443946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_(nullptr), 45a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_(allocator, 0), 46a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_(allocator, 0), 47a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_(allocator, 0), 48102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_core_register_intervals_(allocator, codegen->GetNumberOfCoreRegisters()), 49102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_fp_register_intervals_(allocator, codegen->GetNumberOfFloatingPointRegisters()), 503946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray temp_intervals_(allocator, 4), 51776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray int_spill_slots_(allocator, kDefaultNumberOfSpillSlots), 52776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray long_spill_slots_(allocator, kDefaultNumberOfSpillSlots), 53776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray float_spill_slots_(allocator, kDefaultNumberOfSpillSlots), 54776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray double_spill_slots_(allocator, kDefaultNumberOfSpillSlots), 553946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray safepoints_(allocator, 0), 56a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray processing_core_registers_(false), 57a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray number_of_registers_(-1), 58a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray registers_array_(nullptr), 59102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray blocked_core_registers_(codegen->GetBlockedCoreRegisters()), 60102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray blocked_fp_registers_(codegen->GetBlockedFloatingPointRegisters()), 613bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray reserved_out_slots_(0), 62f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell maximum_number_of_live_core_registers_(0), 63f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell maximum_number_of_live_fp_registers_(0) { 64988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray static constexpr bool kIsBaseline = false; 65988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray codegen->SetupBlockedRegisters(kIsBaseline); 66102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_core_register_intervals_.SetSize(codegen->GetNumberOfCoreRegisters()); 67102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_fp_register_intervals_.SetSize(codegen->GetNumberOfFloatingPointRegisters()); 683946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Always reserve for the current method and the graph's max out registers. 693946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // TODO: compute it instead. 703946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray reserved_out_slots_ = 1 + codegen->GetGraph()->GetMaximumNumberOfOutVRegs(); 71a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 72a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 7386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraybool RegisterAllocator::CanAllocateRegistersFor(const HGraph& graph, 7486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InstructionSet instruction_set) { 7586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (!Supports(instruction_set)) { 7686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return false; 7786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 786c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (instruction_set == kArm64 796c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray || instruction_set == kX86_64 806c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray || instruction_set == kArm 816c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray || instruction_set == kThumb2) { 823e69f16ae3fddfd24f4f0e29deb106d564ab296cAlexandre Rames return true; 833e69f16ae3fddfd24f4f0e29deb106d564ab296cAlexandre Rames } 8486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = graph.GetBlocks().Size(); i < e; ++i) { 8586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (HInstructionIterator it(graph.GetBlocks().Get(i)->GetInstructions()); 8686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray !it.Done(); 8786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray it.Advance()) { 8886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* current = it.Current(); 897c8d009552545e6f1fd6036721e4e42e3fd14697Mark Mendell if (instruction_set == kX86 && current->GetType() == Primitive::kPrimLong) { 907c8d009552545e6f1fd6036721e4e42e3fd14697Mark Mendell return false; 91102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 9286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 9386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 9486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return true; 9586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 9686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 9786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraystatic bool ShouldProcess(bool processing_core_registers, LiveInterval* interval) { 983946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (interval == nullptr) return false; 9986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray bool is_core_register = (interval->GetType() != Primitive::kPrimDouble) 10086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && (interval->GetType() != Primitive::kPrimFloat); 101a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return processing_core_registers == is_core_register; 102a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 103a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 10486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::AllocateRegisters() { 10586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray AllocateRegistersInternal(); 10686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Resolve(); 10786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 10886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (kIsDebugBuild) { 10986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray processing_core_registers_ = true; 11086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ValidateInternal(true); 11186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray processing_core_registers_ = false; 11286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ValidateInternal(true); 1135976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // Check that the linear order is still correct with regards to lifetime positions. 1145976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // Since only parallel moves have been inserted during the register allocation, 1155976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // these checks are mostly for making sure these moves have been added correctly. 1165976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray size_t current_liveness = 0; 1175976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray for (HLinearOrderIterator it(liveness_); !it.Done(); it.Advance()) { 1185976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray HBasicBlock* block = it.Current(); 1195976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 1205976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray HInstruction* instruction = inst_it.Current(); 1215976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray DCHECK_LE(current_liveness, instruction->GetLifetimePosition()); 1225976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray current_liveness = instruction->GetLifetimePosition(); 1235976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray } 1245976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray for (HInstructionIterator inst_it(block->GetInstructions()); 1255976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray !inst_it.Done(); 1265976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray inst_it.Advance()) { 1275976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray HInstruction* instruction = inst_it.Current(); 1285976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray DCHECK_LE(current_liveness, instruction->GetLifetimePosition()) << instruction->DebugName(); 1295976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray current_liveness = instruction->GetLifetimePosition(); 1305976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray } 1315976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray } 13286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 13386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 13486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 13586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::BlockRegister(Location location, 13686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t start, 137102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray size_t end) { 13856b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray int reg = location.reg(); 139102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray DCHECK(location.IsRegister() || location.IsFpuRegister()); 140102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* interval = location.IsRegister() 141102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ? physical_core_register_intervals_.Get(reg) 142102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray : physical_fp_register_intervals_.Get(reg); 143102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray Primitive::Type type = location.IsRegister() 144102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ? Primitive::kPrimInt 145840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray : Primitive::kPrimFloat; 14686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (interval == nullptr) { 14786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray interval = LiveInterval::MakeFixedInterval(allocator_, reg, type); 148102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (location.IsRegister()) { 149102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_core_register_intervals_.Put(reg, interval); 150102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 151102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray physical_fp_register_intervals_.Put(reg, interval); 152102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 15386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 15486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(interval->GetRegister() == reg); 15586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray interval->AddRange(start, end); 15686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 15786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 15886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::AllocateRegistersInternal() { 1593946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Iterate post-order, to ensure the list is sorted, and the last added interval 1603946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // is the one with the lowest start position. 1613946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (HLinearPostOrderIterator it(liveness_); !it.Done(); it.Advance()) { 1623946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray HBasicBlock* block = it.Current(); 163277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe for (HBackwardInstructionIterator back_it(block->GetInstructions()); !back_it.Done(); 164277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe back_it.Advance()) { 165277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe ProcessInstruction(back_it.Current()); 1663946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 167277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 168277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe ProcessInstruction(inst_it.Current()); 1693946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 1703946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 171a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1723946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray number_of_registers_ = codegen_->GetNumberOfCoreRegisters(); 173a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_); 1743946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray processing_core_registers_ = true; 1753946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_ = &unhandled_core_intervals_; 176102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0, e = physical_core_register_intervals_.Size(); i < e; ++i) { 177102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* fixed = physical_core_register_intervals_.Get(i); 178102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (fixed != nullptr) { 179296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Fixed interval is added to inactive_ instead of unhandled_. 180296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // It's also the only type of inactive interval whose start position 181296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // can be after the current interval during linear scan. 182296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Fixed interval is never split and never moves to unhandled_. 183102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray inactive_.Add(fixed); 184102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 185102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 1863946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LinearScan(); 187a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1883946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray inactive_.Reset(); 1893946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray active_.Reset(); 1903946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray handled_.Reset(); 191a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1923946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray number_of_registers_ = codegen_->GetNumberOfFloatingPointRegisters(); 1933946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_); 1943946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray processing_core_registers_ = false; 1953946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray unhandled_ = &unhandled_fp_intervals_; 196102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0, e = physical_fp_register_intervals_.Size(); i < e; ++i) { 197102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* fixed = physical_fp_register_intervals_.Get(i); 198102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (fixed != nullptr) { 199296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Fixed interval is added to inactive_ instead of unhandled_. 200296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // It's also the only type of inactive interval whose start position 201296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // can be after the current interval during linear scan. 202296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Fixed interval is never split and never moves to unhandled_. 203102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray inactive_.Add(fixed); 204102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 205102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 2063946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LinearScan(); 2073946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray} 20886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 2093946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffrayvoid RegisterAllocator::ProcessInstruction(HInstruction* instruction) { 2103946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LocationSummary* locations = instruction->GetLocations(); 2113946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t position = instruction->GetLifetimePosition(); 2123946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 2133946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (locations == nullptr) return; 2143946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 2153946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Create synthesized intervals for temporaries. 2163946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < locations->GetTempCount(); ++i) { 2173946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray Location temp = locations->GetTemp(i); 21852839d17c06175e19ca4a093fb878450d1c4310dNicolas Geoffray if (temp.IsRegister() || temp.IsFpuRegister()) { 219102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray BlockRegister(temp, position, position + 1); 2203946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 221102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray DCHECK(temp.IsUnallocated()); 2225368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain switch (temp.GetPolicy()) { 2235368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain case Location::kRequiresRegister: { 2245368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LiveInterval* interval = 2255368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimInt); 2265368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain temp_intervals_.Add(interval); 2275368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain interval->AddRange(position, position + 1); 2285368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain unhandled_core_intervals_.Add(interval); 2295368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain break; 2305368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain } 2315368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain 2325368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain case Location::kRequiresFpuRegister: { 2335368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LiveInterval* interval = 2345368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LiveInterval::MakeTempInterval(allocator_, Primitive::kPrimDouble); 2355368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain temp_intervals_.Add(interval); 2365368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain interval->AddRange(position, position + 1); 237840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (codegen_->NeedsTwoRegisters(Primitive::kPrimDouble)) { 238840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray interval->AddHighInterval(true); 239840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray LiveInterval* high = interval->GetHighInterval(); 240840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray temp_intervals_.Add(high); 241840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray unhandled_fp_intervals_.Add(high); 242840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 2435368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain unhandled_fp_intervals_.Add(interval); 2445368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain break; 2455368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain } 2465368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain 2475368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain default: 2485368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LOG(FATAL) << "Unexpected policy for temporary location " 2495368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain << temp.GetPolicy(); 2505368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain } 251a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 252a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 25386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 2543bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray bool core_register = (instruction->GetType() != Primitive::kPrimDouble) 2553bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray && (instruction->GetType() != Primitive::kPrimFloat); 2563bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray 2573946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (locations->CanCall()) { 258c0572a451944f78397619dec34a38c36c11e9d2aNicolas Geoffray if (codegen_->IsLeafMethod()) { 259c0572a451944f78397619dec34a38c36c11e9d2aNicolas Geoffray // TODO: We do this here because we do not want the suspend check to artificially 260c0572a451944f78397619dec34a38c36c11e9d2aNicolas Geoffray // create live registers. We should find another place, but this is currently the 261c0572a451944f78397619dec34a38c36c11e9d2aNicolas Geoffray // simplest. 262c0572a451944f78397619dec34a38c36c11e9d2aNicolas Geoffray DCHECK(instruction->IsSuspendCheckEntry()); 263c0572a451944f78397619dec34a38c36c11e9d2aNicolas Geoffray instruction->GetBlock()->RemoveInstruction(instruction); 264c0572a451944f78397619dec34a38c36c11e9d2aNicolas Geoffray return; 2653bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 2663946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray safepoints_.Add(instruction); 2673bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray if (locations->OnlyCallsOnSlowPath()) { 2683bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // We add a synthesized range at this position to record the live registers 2693bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // at this position. Ideally, we could just update the safepoints when locations 2703bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // are updated, but we currently need to know the full stack size before updating 2713bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // locations (because of parameters and the fact that we don't have a frame pointer). 2723bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // And knowing the full stack size requires to know the maximum number of live 2733bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // registers at calls in slow paths. 2743bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // By adding the following interval in the algorithm, we can compute this 2753bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray // maximum before updating locations. 2763bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray LiveInterval* interval = LiveInterval::MakeSlowPathInterval(allocator_, instruction); 277acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray interval->AddRange(position, position + 1); 27887d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray AddSorted(&unhandled_core_intervals_, interval); 27987d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray AddSorted(&unhandled_fp_intervals_, interval); 2803bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 2813bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray } 2823bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray 2833bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray if (locations->WillCall()) { 2843946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Block all registers. 2853946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < codegen_->GetNumberOfCoreRegisters(); ++i) { 286988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray if (!codegen_->IsCoreCalleeSaveRegister(i)) { 287988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray BlockRegister(Location::RegisterLocation(i), 288988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray position, 289988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray position + 1); 290988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray } 291102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 292102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0; i < codegen_->GetNumberOfFloatingPointRegisters(); ++i) { 293988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray if (!codegen_->IsFloatingPointCalleeSaveRegister(i)) { 294988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray BlockRegister(Location::FpuRegisterLocation(i), 295988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray position, 296988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray position + 1); 297988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray } 2983946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 2993946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3003946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 3013946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < instruction->InputCount(); ++i) { 3023946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray Location input = locations->InAt(i); 303102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (input.IsRegister() || input.IsFpuRegister()) { 304102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray BlockRegister(input, position, position + 1); 305840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (input.IsPair()) { 306840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray BlockRegister(input.ToLow(), position, position + 1); 307840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray BlockRegister(input.ToHigh(), position, position + 1); 3083946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3093946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3103946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 3113946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* current = instruction->GetLiveInterval(); 3123946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current == nullptr) return; 3133946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 314102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray GrowableArray<LiveInterval*>& unhandled = core_register 315102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ? unhandled_core_intervals_ 316102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray : unhandled_fp_intervals_; 317102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray 3187690562d40878f44823d5fb03a2084cfc677ec4aNicolas Geoffray DCHECK(unhandled.IsEmpty() || current->StartsBeforeOrAt(unhandled.Peek())); 31987d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray 320840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (codegen_->NeedsTwoRegisters(current->GetType())) { 321840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray current->AddHighInterval(); 322840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 323840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 3243946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Some instructions define their output in fixed register/stack slot. We need 3253946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // to ensure we know these locations before doing register allocation. For a 3263946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // given register, we create an interval that covers these locations. The register 3273946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // will be unavailable at these locations when trying to allocate one for an 3283946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // interval. 3293946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // 3303946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // The backwards walking ensures the ranges are ordered on increasing start positions. 3313946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray Location output = locations->Out(); 332d0d4852847432368b090c184d6639e573538dccfCalin Juravle if (output.IsUnallocated() && output.GetPolicy() == Location::kSameAsFirstInput) { 333d0d4852847432368b090c184d6639e573538dccfCalin Juravle Location first = locations->InAt(0); 334d0d4852847432368b090c184d6639e573538dccfCalin Juravle if (first.IsRegister() || first.IsFpuRegister()) { 335d0d4852847432368b090c184d6639e573538dccfCalin Juravle current->SetFrom(position + 1); 336d0d4852847432368b090c184d6639e573538dccfCalin Juravle current->SetRegister(first.reg()); 337840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (first.IsPair()) { 338840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray current->SetFrom(position + 1); 339840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray current->SetRegister(first.low()); 340840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray LiveInterval* high = current->GetHighInterval(); 341840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray high->SetRegister(first.high()); 342840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray high->SetFrom(position + 1); 343d0d4852847432368b090c184d6639e573538dccfCalin Juravle } 344d0d4852847432368b090c184d6639e573538dccfCalin Juravle } else if (output.IsRegister() || output.IsFpuRegister()) { 3453946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Shift the interval's start by one to account for the blocked register. 3463946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray current->SetFrom(position + 1); 34756b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray current->SetRegister(output.reg()); 348102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray BlockRegister(output, position, position + 1); 349840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (output.IsPair()) { 350840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray current->SetFrom(position + 1); 351840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray current->SetRegister(output.low()); 352840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray LiveInterval* high = current->GetHighInterval(); 353840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray high->SetRegister(output.high()); 354840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray high->SetFrom(position + 1); 355840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray BlockRegister(output.ToLow(), position, position + 1); 356840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray BlockRegister(output.ToHigh(), position, position + 1); 3573946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else if (output.IsStackSlot() || output.IsDoubleStackSlot()) { 3583946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray current->SetSpillSlot(output.GetStackIndex()); 359840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else { 360840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(output.IsUnallocated() || output.IsConstant()); 3613946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3623946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 3633946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // If needed, add interval to the list of unhandled intervals. 3643946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current->HasSpillSlot() || instruction->IsConstant()) { 365c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray // Split just before first register use. 3663946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t first_register_use = current->FirstRegisterUse(); 3673946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (first_register_use != kNoLifetime) { 368c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray LiveInterval* split = Split(current, first_register_use - 1); 369b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // Don't add directly to `unhandled`, it needs to be sorted and the start 3703946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // of this new interval might be after intervals already in the list. 3713946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(&unhandled, split); 3723946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 3733946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Nothing to do, we won't allocate a register for this value. 3743946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 3753946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 376b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // Don't add directly to `unhandled`, temp or safepoint intervals 377b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // for this instruction may have been added, and those can be 378b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // processed first. 379b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray AddSorted(&unhandled, current); 3803946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 381a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 382a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 38331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffrayclass AllRangesIterator : public ValueObject { 38431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray public: 38531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray explicit AllRangesIterator(LiveInterval* interval) 38631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray : current_interval_(interval), 38731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_(interval->GetFirstRange()) {} 38831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 38931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray bool Done() const { return current_interval_ == nullptr; } 39031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveRange* CurrentRange() const { return current_range_; } 39131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* CurrentInterval() const { return current_interval_; } 39231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 39331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray void Advance() { 39431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_ = current_range_->GetNext(); 39531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current_range_ == nullptr) { 39631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_interval_ = current_interval_->GetNextSibling(); 39731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current_interval_ != nullptr) { 39831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_ = current_interval_->GetFirstRange(); 39931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 40031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 40131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 40231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 40331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray private: 40431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* current_interval_; 40531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveRange* current_range_; 40631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 40731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray DISALLOW_COPY_AND_ASSIGN(AllRangesIterator); 40831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray}; 40931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 41086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffraybool RegisterAllocator::ValidateInternal(bool log_fatal_on_failure) const { 41186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // To simplify unit testing, we eagerly create the array of intervals, and 41286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // call the helper method. 41386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray GrowableArray<LiveInterval*> intervals(allocator_, 0); 41486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0; i < liveness_.GetNumberOfSsaValues(); ++i) { 41586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 41686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (ShouldProcess(processing_core_registers_, instruction->GetLiveInterval())) { 41786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray intervals.Add(instruction->GetLiveInterval()); 41886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 41986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 42086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 421102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (processing_core_registers_) { 422102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0, e = physical_core_register_intervals_.Size(); i < e; ++i) { 423102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* fixed = physical_core_register_intervals_.Get(i); 424102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (fixed != nullptr) { 425102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray intervals.Add(fixed); 426102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 427102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 428102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 429102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray for (size_t i = 0, e = physical_fp_register_intervals_.Size(); i < e; ++i) { 430102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray LiveInterval* fixed = physical_fp_register_intervals_.Get(i); 431102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (fixed != nullptr) { 432102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray intervals.Add(fixed); 433102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 43486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 43586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 43686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 4373946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0, e = temp_intervals_.Size(); i < e; ++i) { 4383946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* temp = temp_intervals_.Get(i); 4393946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (ShouldProcess(processing_core_registers_, temp)) { 4403946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray intervals.Add(temp); 4413946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 4423946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 4433946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 444776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray return ValidateIntervals(intervals, GetNumberOfSpillSlots(), reserved_out_slots_, *codegen_, 4453946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray allocator_, processing_core_registers_, log_fatal_on_failure); 44686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 44786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 44831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffraybool RegisterAllocator::ValidateIntervals(const GrowableArray<LiveInterval*>& intervals, 44931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray size_t number_of_spill_slots, 4503946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t number_of_out_slots, 451a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray const CodeGenerator& codegen, 452a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray ArenaAllocator* allocator, 453a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool processing_core_registers, 454a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool log_fatal_on_failure) { 455a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t number_of_registers = processing_core_registers 456a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray ? codegen.GetNumberOfCoreRegisters() 457a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray : codegen.GetNumberOfFloatingPointRegisters(); 45831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray GrowableArray<ArenaBitVector*> liveness_of_values( 45931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray allocator, number_of_registers + number_of_spill_slots); 460a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 461a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Allocate a bit vector per register. A live interval that has a register 462a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // allocated will populate the associated bit vector based on its live ranges. 46331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t i = 0; i < number_of_registers + number_of_spill_slots; ++i) { 46431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_values.Add(new (allocator) ArenaBitVector(allocator, 0, true)); 465a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 466a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 46731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t i = 0, e = intervals.Size(); i < e; ++i) { 46831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (AllRangesIterator it(intervals.Get(i)); !it.Done(); it.Advance()) { 46931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* current = it.CurrentInterval(); 47086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* defined_by = current->GetParent()->GetDefinedBy(); 47186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->GetParent()->HasSpillSlot() 47286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Parameters have their own stack slot. 47386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && !(defined_by != nullptr && defined_by->IsParameterValue())) { 4743946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray BitVector* liveness_of_spill_slot = liveness_of_values.Get(number_of_registers 4753946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray + current->GetParent()->GetSpillSlot() / kVRegSize 4763946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray - number_of_out_slots); 47731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 47831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (liveness_of_spill_slot->IsBitSet(j)) { 47931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (log_fatal_on_failure) { 48031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray std::ostringstream message; 48131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray message << "Spill slot conflict at " << j; 48231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LOG(FATAL) << message.str(); 48331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 48431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray return false; 48531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 48631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 48731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_spill_slot->SetBit(j); 48831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 48931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 490a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 49131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 49231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current->HasRegister()) { 49331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray BitVector* liveness_of_register = liveness_of_values.Get(current->GetRegister()); 49431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 49531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (liveness_of_register->IsBitSet(j)) { 496829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray if (current->IsUsingInputRegister() && current->CanUseInputRegister()) { 497829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray continue; 498829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 499a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (log_fatal_on_failure) { 500a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray std::ostringstream message; 5013946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray message << "Register conflict at " << j << " "; 5023946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (defined_by != nullptr) { 5033946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray message << "(" << defined_by->DebugName() << ")"; 5043946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 5053946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray message << "for "; 506a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (processing_core_registers) { 507a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen.DumpCoreRegister(message, current->GetRegister()); 508a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 509a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen.DumpFloatingPointRegister(message, current->GetRegister()); 510a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 511a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LOG(FATAL) << message.str(); 512a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 513a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 514a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 515a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 51631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_register->SetBit(j); 517a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 518a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 51931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 52031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 521a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 522a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 523a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 524a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 52586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::DumpInterval(std::ostream& stream, LiveInterval* interval) const { 526a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray interval->Dump(stream); 527a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << ": "; 528a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->HasRegister()) { 529102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray if (interval->IsFloatingPoint()) { 53086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray codegen_->DumpFloatingPointRegister(stream, interval->GetRegister()); 531102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } else { 532102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray codegen_->DumpCoreRegister(stream, interval->GetRegister()); 533a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 534a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 535a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << "spilled"; 536a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 537a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << std::endl; 538a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 539a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 540296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yangvoid RegisterAllocator::DumpAllIntervals(std::ostream& stream) const { 541296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang stream << "inactive: " << std::endl; 542296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0; i < inactive_.Size(); i ++) { 543296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DumpInterval(stream, inactive_.Get(i)); 544296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 545296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang stream << "active: " << std::endl; 546296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0; i < active_.Size(); i ++) { 547296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DumpInterval(stream, active_.Get(i)); 548296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 549296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang stream << "unhandled: " << std::endl; 550296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang auto unhandled = (unhandled_ != nullptr) ? 551296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang unhandled_ : &unhandled_core_intervals_; 552296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0; i < unhandled->Size(); i ++) { 553296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DumpInterval(stream, unhandled->Get(i)); 554296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 555296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang stream << "handled: " << std::endl; 556296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0; i < handled_.Size(); i ++) { 557296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DumpInterval(stream, handled_.Get(i)); 558296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 559296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang} 560296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang 561a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// By the book implementation of a linear scan register allocator. 562a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffrayvoid RegisterAllocator::LinearScan() { 5633946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray while (!unhandled_->IsEmpty()) { 564a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (1) Remove interval with the lowest start position from unhandled. 5653946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* current = unhandled_->Pop(); 5663946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray DCHECK(!current->IsFixed() && !current->HasSpillSlot()); 567c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray DCHECK(unhandled_->IsEmpty() || unhandled_->Peek()->GetStart() >= current->GetStart()); 568840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(!current->IsLowInterval() || unhandled_->Peek()->IsHighInterval()); 56987d03761f35ad6cbe0bffbf1ec739875a471da6dNicolas Geoffray 570a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t position = current->GetStart(); 571a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 572296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Remember the inactive_ size here since the ones moved to inactive_ from 573296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // active_ below shouldn't need to be re-checked. 574296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang size_t inactive_intervals_to_handle = inactive_.Size(); 575296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang 576a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (2) Remove currently active intervals that are dead at this position. 577a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Move active intervals that have a lifetime hole at this position 578a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // to inactive. 579a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < active_.Size(); ++i) { 580a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* interval = active_.Get(i); 581a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->IsDeadAt(position)) { 582a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Delete(interval); 583a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 584a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_.Add(interval); 585a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else if (!interval->Covers(position)) { 586a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Delete(interval); 587a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 588a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.Add(interval); 589a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 590a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 591a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 592a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (3) Remove currently inactive intervals that are dead at this position. 593a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Move inactive intervals that cover this position to active. 594296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0; i < inactive_intervals_to_handle; ++i) { 595a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* interval = inactive_.Get(i); 596296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK(interval->GetStart() < position || interval->IsFixed()); 597a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->IsDeadAt(position)) { 598a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.Delete(interval); 599a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 600296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang --inactive_intervals_to_handle; 601a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_.Add(interval); 602a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else if (interval->Covers(position)) { 603a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.Delete(interval); 604a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 605296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang --inactive_intervals_to_handle; 606a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Add(interval); 607a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 608a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 609a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 610acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray if (current->IsSlowPathSafepoint()) { 611acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray // Synthesized interval to record the maximum number of live registers 612acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray // at safepoints. No need to allocate a register for it. 613f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell if (processing_core_registers_) { 614f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell maximum_number_of_live_core_registers_ = 615f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell std::max(maximum_number_of_live_core_registers_, active_.Size()); 616f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell } else { 617f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell maximum_number_of_live_fp_registers_ = 618f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell std::max(maximum_number_of_live_fp_registers_, active_.Size()); 619f85a9ca9859ad843dc03d3a2b600afbaf2e9bbddMark Mendell } 620acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray DCHECK(unhandled_->IsEmpty() || unhandled_->Peek()->GetStart() > current->GetStart()); 621acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray continue; 622acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray } 623acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray 624840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (current->IsHighInterval() && !current->GetLowInterval()->HasRegister()) { 625840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(!current->HasRegister()); 626840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // Allocating the low part was unsucessful. The splitted interval for the high part 627840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // will be handled next (it is in the `unhandled_` list). 628840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray continue; 629840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 630840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 631a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (4) Try to find an available register. 632a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool success = TryAllocateFreeReg(current); 633a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 634a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (5) If no register could be found, we need to spill. 635a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (!success) { 636a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray success = AllocateBlockedReg(current); 637a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 638a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 639a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (6) If the interval had a register allocated, add it to the list of active 640a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // intervals. 641a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (success) { 642988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray codegen_->AddAllocatedRegister(processing_core_registers_ 643988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray ? Location::RegisterLocation(current->GetRegister()) 644988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray : Location::FpuRegisterLocation(current->GetRegister())); 645a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Add(current); 646840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (current->HasHighInterval() && !current->GetHighInterval()->HasRegister()) { 647840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray current->GetHighInterval()->SetRegister(GetHighForLowRegister(current->GetRegister())); 648840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 649a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 650a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 651a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 652a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 653829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffraystatic void FreeIfNotCoverAt(LiveInterval* interval, size_t position, size_t* free_until) { 654829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray DCHECK(!interval->IsHighInterval()); 655829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // Note that the same instruction may occur multiple times in the input list, 656829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // so `free_until` may have changed already. 657829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray if (interval->IsDeadAt(position)) { 658829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // Set the register to be free. Note that inactive intervals might later 659829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // update this. 660829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray free_until[interval->GetRegister()] = kMaxLifetimePosition; 661829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray if (interval->HasHighInterval()) { 662829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray DCHECK(interval->GetHighInterval()->IsDeadAt(position)); 663829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray free_until[interval->GetHighInterval()->GetRegister()] = kMaxLifetimePosition; 664829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 665829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } else if (!interval->Covers(position)) { 666829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // The interval becomes inactive at `defined_by`. We make its register 667829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // available only until the next use strictly after `defined_by`. 668829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray free_until[interval->GetRegister()] = interval->FirstUseAfter(position); 669829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray if (interval->HasHighInterval()) { 670829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray DCHECK(!interval->GetHighInterval()->Covers(position)); 671829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray free_until[interval->GetHighInterval()->GetRegister()] = free_until[interval->GetRegister()]; 672829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 673829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 674829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray} 675829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray 676a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// Find a free register. If multiple are found, pick the register that 677a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// is free the longest. 678a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::TryAllocateFreeReg(LiveInterval* current) { 679a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t* free_until = registers_array_; 680a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 681a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // First set all registers to be free. 682a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 683a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray free_until[i] = kMaxLifetimePosition; 684a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 685a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 686296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // For each active interval, set its register to not free. 687296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0, e = active_.Size(); i < e; ++i) { 688296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang LiveInterval* interval = active_.Get(i); 689296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK(interval->HasRegister()); 690296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang free_until[interval->GetRegister()] = 0; 691296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 692296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang 693829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // An interval that starts an instruction (that is, it is not split), may 694829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // re-use the registers used by the inputs of that instruciton, based on the 695829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // location summary. 696829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray HInstruction* defined_by = current->GetDefinedBy(); 697829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray if (defined_by != nullptr && !current->IsSplit()) { 698829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray LocationSummary* locations = defined_by->GetLocations(); 699829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray if (!locations->OutputCanOverlapWithInputs() && locations->Out().IsUnallocated()) { 700829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray for (HInputIterator it(defined_by); !it.Done(); it.Advance()) { 701829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // Take the last interval of the input. It is the location of that interval 702829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // that will be used at `defined_by`. 703829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray LiveInterval* interval = it.Current()->GetLiveInterval()->GetLastSibling(); 704829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // Note that interval may have not been processed yet. 705829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // TODO: Handle non-split intervals last in the work list. 706829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray if (interval->HasRegister() && interval->SameRegisterKind(*current)) { 707829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // The input must be live until the end of `defined_by`, to comply to 708829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // the linear scan algorithm. So we use `defined_by`'s end lifetime 709829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // position to check whether the input is dead or is inactive after 710829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray // `defined_by`. 711829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray DCHECK(interval->Covers(defined_by->GetLifetimePosition())); 712829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray size_t position = defined_by->GetLifetimePosition() + 1; 713829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray FreeIfNotCoverAt(interval, position, free_until); 714829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 715829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 716829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 717829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray } 718829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray 719a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each inactive interval, set its register to be free until 720a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // the next intersection with `current`. 721a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { 722a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* inactive = inactive_.Get(i); 723296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Temp/Slow-path-safepoint interval has no holes. 724296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK(!inactive->IsTemp() && !inactive->IsSlowPathSafepoint()); 725296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang if (!current->IsSplit() && !inactive->IsFixed()) { 726296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Neither current nor inactive are fixed. 727296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Thanks to SSA, a non-split interval starting in a hole of an 728296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // inactive interval should never intersect with that inactive interval. 729296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Only if it's not fixed though, because fixed intervals don't come from SSA. 730296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime); 731296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang continue; 732296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 733296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang 734a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(inactive->HasRegister()); 735296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang if (free_until[inactive->GetRegister()] == 0) { 736296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Already used by some active interval. No need to intersect. 737296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang continue; 738296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 739a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t next_intersection = inactive->FirstIntersectionWith(current); 740a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (next_intersection != kNoLifetime) { 741aac0f39a3501a7f7dd04b2342c2a16961969f139Nicolas Geoffray free_until[inactive->GetRegister()] = 742aac0f39a3501a7f7dd04b2342c2a16961969f139Nicolas Geoffray std::min(free_until[inactive->GetRegister()], next_intersection); 743a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 744a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 745a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 7466c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray int reg = kNoRegister; 7473946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current->HasRegister()) { 7483946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Some instructions have a fixed register output. 7493946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray reg = current->GetRegister(); 750840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (free_until[reg] == 0) { 751840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(current->IsHighInterval()); 752840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // AllocateBlockedReg will spill the holder of the register. 753840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return false; 754840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 7553946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 756840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(!current->IsHighInterval()); 75701ef345767ea609417fc511e42007705c9667546Nicolas Geoffray int hint = current->FindFirstRegisterHint(free_until); 75801ef345767ea609417fc511e42007705c9667546Nicolas Geoffray if (hint != kNoRegister) { 75901ef345767ea609417fc511e42007705c9667546Nicolas Geoffray DCHECK(!IsBlocked(hint)); 76001ef345767ea609417fc511e42007705c9667546Nicolas Geoffray reg = hint; 761840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (current->IsLowInterval()) { 7626c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray reg = FindAvailableRegisterPair(free_until, current->GetStart()); 76301ef345767ea609417fc511e42007705c9667546Nicolas Geoffray } else { 764840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray reg = FindAvailableRegister(free_until); 765a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 766a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 767a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 7686c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK_NE(reg, kNoRegister); 769a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // If we could not find a register, we need to spill. 770840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (free_until[reg] == 0) { 771840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return false; 772840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 773840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 774840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (current->IsLowInterval() && free_until[GetHighForLowRegister(reg)] == 0) { 775a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 776a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 777a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 778a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray current->SetRegister(reg); 779a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (!current->IsDeadAt(free_until[reg])) { 780a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // If the register is only available for a subset of live ranges 781a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // covered by `current`, split `current` at the position where 782a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // the register is not available anymore. 783a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* split = Split(current, free_until[reg]); 784a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(split != nullptr); 7853946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 786a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 787a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 788a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 789a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 790a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::IsBlocked(int reg) const { 791102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return processing_core_registers_ 792102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray ? blocked_core_registers_[reg] 793102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray : blocked_fp_registers_[reg]; 794a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 795a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 7966c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffrayint RegisterAllocator::FindAvailableRegisterPair(size_t* next_use, size_t starting_at) const { 7976c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray int reg = kNoRegister; 798840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // Pick the register pair that is used the last. 799840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 800840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (IsBlocked(i)) continue; 801840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (!IsLowRegister(i)) continue; 802840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray int high_register = GetHighForLowRegister(i); 803840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (IsBlocked(high_register)) continue; 804840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray int existing_high_register = GetHighForLowRegister(reg); 8056c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if ((reg == kNoRegister) || (next_use[i] >= next_use[reg] 806840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray && next_use[high_register] >= next_use[existing_high_register])) { 807840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray reg = i; 808840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (next_use[i] == kMaxLifetimePosition 809840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray && next_use[high_register] == kMaxLifetimePosition) { 810840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray break; 811840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 8126c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } else if (next_use[reg] <= starting_at || next_use[existing_high_register] <= starting_at) { 8136c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // If one of the current register is known to be unavailable, just unconditionally 8146c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // try a new one. 8156c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray reg = i; 816840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 817840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 818840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return reg; 819840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray} 820840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 821840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffrayint RegisterAllocator::FindAvailableRegister(size_t* next_use) const { 8226c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray int reg = kNoRegister; 823840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // Pick the register that is used the last. 824840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 825840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (IsBlocked(i)) continue; 8266c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (reg == kNoRegister || next_use[i] > next_use[reg]) { 827840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray reg = i; 828840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (next_use[i] == kMaxLifetimePosition) break; 829840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 830840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 831840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return reg; 832840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray} 833840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 8346c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffraybool RegisterAllocator::TrySplitNonPairIntervalAt(size_t position, 8356c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray size_t first_register_use, 8366c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray size_t* next_use) { 8376c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray for (size_t i = 0, e = active_.Size(); i < e; ++i) { 8386c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray LiveInterval* active = active_.Get(i); 8396c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(active->HasRegister()); 8406c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // Split the first interval found. 8416c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (first_register_use <= next_use[active->GetRegister()] 8426c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray && !active->IsLowInterval() 8436c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray && !active->IsHighInterval()) { 8446c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray LiveInterval* split = Split(active, position); 8456c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray active_.DeleteAt(i); 8466c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (split != active) { 8476c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray handled_.Add(active); 8486c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 8496c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray AddSorted(unhandled_, split); 8506c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray return true; 8516c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 8526c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 8536c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray return false; 8546c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray} 8556c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray 856a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// Find the register that is used the last, and spill the interval 857a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// that holds it. If the first use of `current` is after that register 858a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// we spill `current` instead. 859a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) { 860a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t first_register_use = current->FirstRegisterUse(); 861412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray if (first_register_use == kNoLifetime) { 86231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray AllocateSpillSlotFor(current); 863a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 864a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 865a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 866a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // First set all registers as not being used. 867a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t* next_use = registers_array_; 868a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 869a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray next_use[i] = kMaxLifetimePosition; 870a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 871a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 872a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each active interval, find the next use of its register after the 873a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // start of current. 874a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = active_.Size(); i < e; ++i) { 875a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* active = active_.Get(i); 876a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(active->HasRegister()); 87786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (active->IsFixed()) { 87886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[active->GetRegister()] = current->GetStart(); 87986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 88086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t use = active->FirstRegisterUseAfter(current->GetStart()); 88186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (use != kNoLifetime) { 88286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[active->GetRegister()] = use; 88386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 884a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 885a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 886a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 887a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each inactive interval, find the next use of its register after the 888a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // start of current. 889a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { 890a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* inactive = inactive_.Get(i); 891296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Temp/Slow-path-safepoint interval has no holes. 892296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK(!inactive->IsTemp() && !inactive->IsSlowPathSafepoint()); 893296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang if (!current->IsSplit() && !inactive->IsFixed()) { 894296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Neither current nor inactive are fixed. 895296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Thanks to SSA, a non-split interval starting in a hole of an 896296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // inactive interval should never intersect with that inactive interval. 897296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Only if it's not fixed though, because fixed intervals don't come from SSA. 898296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime); 899296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang continue; 900296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 901a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(inactive->HasRegister()); 90286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t next_intersection = inactive->FirstIntersectionWith(current); 90386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (next_intersection != kNoLifetime) { 90486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (inactive->IsFixed()) { 90586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[inactive->GetRegister()] = 90686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray std::min(next_intersection, next_use[inactive->GetRegister()]); 90786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 90886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t use = inactive->FirstRegisterUseAfter(current->GetStart()); 90986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (use != kNoLifetime) { 91086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray next_use[inactive->GetRegister()] = std::min(use, next_use[inactive->GetRegister()]); 91186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 91286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 913a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 914a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 915a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 9166c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray int reg = kNoRegister; 9176c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray bool should_spill = false; 918840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (current->HasRegister()) { 919840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(current->IsHighInterval()); 920840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray reg = current->GetRegister(); 9216c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // When allocating the low part, we made sure the high register was available. 9226c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK_LT(first_register_use, next_use[reg]); 923840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (current->IsLowInterval()) { 9246c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray reg = FindAvailableRegisterPair(next_use, current->GetStart()); 9256c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // We should spill if both registers are not available. 9266c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray should_spill = (first_register_use >= next_use[reg]) 9276c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray || (first_register_use >= next_use[GetHighForLowRegister(reg)]); 928840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else { 929840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(!current->IsHighInterval()); 930840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray reg = FindAvailableRegister(next_use); 9316c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray should_spill = (first_register_use >= next_use[reg]); 932a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 933a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 9346c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK_NE(reg, kNoRegister); 9356c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (should_spill) { 936840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK(!current->IsHighInterval()); 9376c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray bool is_allocation_at_use_site = (current->GetStart() == (first_register_use - 1)); 9386c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (current->IsLowInterval() 9396c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray && is_allocation_at_use_site 9406c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray && TrySplitNonPairIntervalAt(current->GetStart(), first_register_use, next_use)) { 9416c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // If we're allocating a register for `current` because the instruction at 9426c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // that position requires it, but we think we should spill, then there are 9436c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // non-pair intervals blocking the allocation. We split the first 9446c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // interval found, and put ourselves first in the `unhandled_` list. 9456c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray LiveInterval* existing = unhandled_->Peek(); 9466c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(existing->IsHighInterval()); 9476c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK_EQ(existing->GetLowInterval(), current); 9486c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray unhandled_->Add(current); 9496c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } else { 9506c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // If the first use of that instruction is after the last use of the found 9516c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // register, we split this interval just before its first register use. 9526c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray AllocateSpillSlotFor(current); 9536c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray LiveInterval* split = Split(current, first_register_use - 1); 9546c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK_NE(current, split) << "There is not enough registers available for " 9556c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray << split->GetParent()->GetDefinedBy()->DebugName() << " " 9566c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray << split->GetParent()->GetDefinedBy()->GetId() 9576c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray << " at " << first_register_use - 1; 9586c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray AddSorted(unhandled_, split); 9596c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 960a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 961a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 962a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Use this register and spill the active and inactives interval that 963a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // have that register. 964a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray current->SetRegister(reg); 965a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 966a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = active_.Size(); i < e; ++i) { 967a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* active = active_.Get(i); 968a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (active->GetRegister() == reg) { 96986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(!active->IsFixed()); 970a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* split = Split(active, current->GetStart()); 971a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.DeleteAt(i); 972dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray if (split != active) { 973dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray handled_.Add(active); 974dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray } 9753946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 9766c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray 9776c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (active->IsLowInterval() || active->IsHighInterval()) { 9786c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray LiveInterval* other_half = active->IsLowInterval() 9796c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray ? active->GetHighInterval() 9806c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray : active->GetLowInterval(); 9816c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // We also need to remove the other half from the list of actives. 9826c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray bool found = false; 9836c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray for (size_t j = 0; j < active_.Size(); ++j) { 9846c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (active_.Get(j) == other_half) { 9856c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray found = true; 9866c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray active_.DeleteAt(j); 9876c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray handled_.Add(other_half); 9886c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray break; 9896c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 9906c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 9916c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(found); 9926c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 993a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray break; 994a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 995a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 996a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 997296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { 998a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* inactive = inactive_.Get(i); 999a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (inactive->GetRegister() == reg) { 1000296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang if (!current->IsSplit() && !inactive->IsFixed()) { 1001296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Neither current nor inactive are fixed. 1002296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Thanks to SSA, a non-split interval starting in a hole of an 1003296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // inactive interval should never intersect with that inactive interval. 1004296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang // Only if it's not fixed though, because fixed intervals don't come from SSA. 1005296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang DCHECK_EQ(inactive->FirstIntersectionWith(current), kNoLifetime); 1006296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang continue; 1007296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang } 100886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t next_intersection = inactive->FirstIntersectionWith(current); 100986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (next_intersection != kNoLifetime) { 101086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (inactive->IsFixed()) { 101186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* split = Split(current, next_intersection); 1012dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray DCHECK_NE(split, current); 10133946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 101486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 1015dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray // Split at the start of `current`, which will lead to splitting 1016dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray // at the end of the lifetime hole of `inactive`. 1017dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray LiveInterval* split = Split(inactive, current->GetStart()); 1018dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray // If it's inactive, it must start before the current interval. 1019dd8f887e81b894bc8075d8bacdb223747b6a8018Nicolas Geoffray DCHECK_NE(split, inactive); 102086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray inactive_.DeleteAt(i); 1021296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang --i; 1022296bd60423e0630d8152b99fb7afb20fbff5a18aMingyao Yang --e; 102386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray handled_.Add(inactive); 10243946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray AddSorted(unhandled_, split); 10256c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray 10266c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (inactive->IsLowInterval() || inactive->IsHighInterval()) { 10276c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray LiveInterval* other_half = inactive->IsLowInterval() 10286c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray ? inactive->GetHighInterval() 10296c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray : inactive->GetLowInterval(); 10306c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray 10316c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // We also need to remove the other half from the list of inactives. 10326c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray bool found = false; 10336c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray for (size_t j = 0; j < inactive_.Size(); ++j) { 10346c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (inactive_.Get(j) == other_half) { 10356c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray found = true; 10366c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray inactive_.DeleteAt(j); 10376c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray --e; 10386c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray handled_.Add(other_half); 10396c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray break; 10406c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 10416c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 10426c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(found); 10436c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray } 104486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 104586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 1046a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1047a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1048a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1049a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 1050a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1051a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 1052a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 10533946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffrayvoid RegisterAllocator::AddSorted(GrowableArray<LiveInterval*>* array, LiveInterval* interval) { 1054c8147a76ed2f440f38329dc08ff889d393b5c535Nicolas Geoffray DCHECK(!interval->IsFixed() && !interval->HasSpillSlot()); 105586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t insert_at = 0; 10563946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = array->Size(); i > 0; --i) { 10573946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* current = array->Get(i - 1); 10586c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray // High intervals must be processed right after their low equivalent. 10596c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray if (current->StartsAfter(interval) && !current->IsHighInterval()) { 106086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray insert_at = i; 1061a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray break; 1062acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray } else if ((current->GetStart() == interval->GetStart()) && current->IsSlowPathSafepoint()) { 1063acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray // Ensure the slow path interval is the last to be processed at its location: we want the 1064acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray // interval to know all live registers at this location. 1065acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray DCHECK(i == 1 || array->Get(i - 2)->StartsAfter(current)); 1066acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray insert_at = i; 1067acd033994aced8246c2fd8e931340dbf82d06d1aNicolas Geoffray break; 1068a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1069a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1070840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 10713946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray array->InsertAt(insert_at, interval); 1072840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // Insert the high interval before the low, to ensure the low is processed before. 1073840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (interval->HasHighInterval()) { 1074840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray array->InsertAt(insert_at, interval->GetHighInterval()); 1075840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (interval->HasLowInterval()) { 1076840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray array->InsertAt(insert_at + 1, interval->GetLowInterval()); 1077840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 1078a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 1079a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 1080a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas GeoffrayLiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) { 1081840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray DCHECK_GE(position, interval->GetStart()); 1082a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(!interval->IsDeadAt(position)); 1083a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (position == interval->GetStart()) { 1084a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Spill slot will be allocated when handling `interval` again. 1085a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray interval->ClearRegister(); 1086840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (interval->HasHighInterval()) { 1087840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray interval->GetHighInterval()->ClearRegister(); 1088840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (interval->HasLowInterval()) { 1089840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray interval->GetLowInterval()->ClearRegister(); 1090840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 1091a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return interval; 1092a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 1093a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* new_interval = interval->SplitAt(position); 1094840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (interval->HasHighInterval()) { 1095840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray LiveInterval* high = interval->GetHighInterval()->SplitAt(position); 1096840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray new_interval->SetHighInterval(high); 1097840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray high->SetLowInterval(new_interval); 1098840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else if (interval->HasLowInterval()) { 1099840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray LiveInterval* low = interval->GetLowInterval()->SplitAt(position); 1100840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray new_interval->SetLowInterval(low); 1101840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray low->SetHighInterval(new_interval); 1102840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 1103a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return new_interval; 1104a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 1105a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 1106a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 110731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffrayvoid RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) { 1108840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (interval->IsHighInterval()) { 1109840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // The low interval will contain the spill slot. 1110840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray return; 1111840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 1112840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray 111331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* parent = interval->GetParent(); 111431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 111531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // An instruction gets a spill slot for its entire lifetime. If the parent 111631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // of this interval already has a spill slot, there is nothing to do. 111731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (parent->HasSpillSlot()) { 111831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray return; 111931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 112031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 112186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* defined_by = parent->GetDefinedBy(); 112286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (defined_by->IsParameterValue()) { 112386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Parameters have their own stack slot. 112486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray parent->SetSpillSlot(codegen_->GetStackSlotOfParameter(defined_by->AsParameterValue())); 112586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 112686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 112786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 112896f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray if (defined_by->IsConstant()) { 112996f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray // Constants don't need a spill slot. 113096f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray return; 113196f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray } 113296f89a290eb67d7bf4b1636798fa28df14309cc7Nicolas Geoffray 113331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* last_sibling = interval; 113431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray while (last_sibling->GetNextSibling() != nullptr) { 113531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray last_sibling = last_sibling->GetNextSibling(); 113631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 113731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray size_t end = last_sibling->GetEnd(); 113831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 1139776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray GrowableArray<size_t>* spill_slots = nullptr; 1140776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray switch (interval->GetType()) { 1141776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimDouble: 1142776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots = &double_spill_slots_; 1143776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray break; 1144776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimLong: 1145776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots = &long_spill_slots_; 1146776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray break; 1147776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimFloat: 1148776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots = &float_spill_slots_; 1149776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray break; 1150776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimNot: 1151776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimInt: 1152776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimChar: 1153776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimByte: 1154776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimBoolean: 1155776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimShort: 1156776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots = &int_spill_slots_; 1157776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray break; 1158776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimVoid: 1159776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray LOG(FATAL) << "Unexpected type for interval " << interval->GetType(); 1160776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray } 1161776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray 1162412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray // Find an available spill slot. 1163412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray size_t slot = 0; 1164776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray for (size_t e = spill_slots->Size(); slot < e; ++slot) { 1165776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray if (spill_slots->Get(slot) <= parent->GetStart() 1166776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray && (slot == (e - 1) || spill_slots->Get(slot + 1) <= parent->GetStart())) { 1167412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray break; 1168412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } 1169412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray } 1170412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray 117101ef345767ea609417fc511e42007705c9667546Nicolas Geoffray if (parent->NeedsTwoSpillSlots()) { 1172776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray if (slot == spill_slots->Size()) { 11733c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray // We need a new spill slot. 1174776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots->Add(end); 1175776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots->Add(end); 1176776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray } else if (slot == spill_slots->Size() - 1) { 1177776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots->Put(slot, end); 1178776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots->Add(end); 11793c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray } else { 1180776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots->Put(slot, end); 1181776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots->Put(slot + 1, end); 118231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 118331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 1184776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray if (slot == spill_slots->Size()) { 11853c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray // We need a new spill slot. 1186776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots->Add(end); 11873c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray } else { 1188776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray spill_slots->Put(slot, end); 11893c04974a90b0e03f4b509010bff49f0b2a3da57fNicolas Geoffray } 119031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 119131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 1192776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // Note that the exact spill slot location will be computed when we resolve, 1193776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // that is when we know the number of spill slots for each type. 1194776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray parent->SetSpillSlot(slot); 119586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 119686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 11972a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffraystatic bool IsValidDestination(Location destination) { 1198102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray return destination.IsRegister() 11996c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray || destination.IsRegisterPair() 1200102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray || destination.IsFpuRegister() 1201840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray || destination.IsFpuRegisterPair() 1202102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray || destination.IsStackSlot() 1203102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray || destination.IsDoubleStackSlot(); 12042a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray} 12052a877f32fe145ad50250389df958a559e7d4ad92Nicolas Geoffray 1206740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffrayvoid RegisterAllocator::AddInputMoveFor(HInstruction* user, 120786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 120886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 120986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 121086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1211476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain DCHECK(!user->IsPhi()); 121286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1213740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray HInstruction* previous = user->GetPrevious(); 121486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move = nullptr; 121586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (previous == nullptr 1216476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain || !previous->IsParallelMove() 12178e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray || previous->GetLifetimePosition() < user->GetLifetimePosition()) { 121886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 12198e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray move->SetLifetimePosition(user->GetLifetimePosition()); 1220740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray user->GetBlock()->InsertInstructionBefore(move, user); 122186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 122286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = previous->AsParallelMove(); 122386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 12248e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray DCHECK_EQ(move->GetLifetimePosition(), user->GetLifetimePosition()); 122542d1f5f006c8bdbcbf855c53036cd50f9c69753eNicolas Geoffray move->AddMove(source, destination, nullptr); 122686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 122786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 122846fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffraystatic bool IsInstructionStart(size_t position) { 122946fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray return (position & 1) == 0; 123046fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray} 123146fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray 123246fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffraystatic bool IsInstructionEnd(size_t position) { 123346fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray return (position & 1) == 1; 123446fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray} 123546fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray 123686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertParallelMoveAt(size_t position, 1237740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray HInstruction* instruction, 123886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 123986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 12406c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(IsValidDestination(destination)) << destination; 124186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 124286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 124386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* at = liveness_.GetInstructionFromPosition(position / 2); 124486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move; 124546fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray if (at == nullptr) { 124646fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray if (IsInstructionStart(position)) { 124746fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray // Block boundary, don't do anything the connection of split siblings will handle it. 124846fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray return; 124946fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray } else { 125046fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray // Move must happen before the first instruction of the block. 125146fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray at = liveness_.GetInstructionFromPosition((position + 1) / 2); 12525976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // Note that parallel moves may have already been inserted, so we explicitly 12535976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // ask for the first instruction of the block: `GetInstructionFromPosition` does 12545976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray // not contain the moves. 12555976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray at = at->GetBlock()->GetFirstInstruction(); 12565976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray if (at->GetLifetimePosition() != position) { 12575976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray DCHECK_GT(at->GetLifetimePosition(), position); 125846fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 125946fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray move->SetLifetimePosition(position); 126046fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray at->GetBlock()->InsertInstructionBefore(move, at); 12615976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray } else { 12625976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray DCHECK(at->IsParallelMove()); 12635976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray move = at->AsParallelMove(); 126446fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray } 126546fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray } 126646fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray } else if (IsInstructionEnd(position)) { 126786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Move must happen after the instruction. 126886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(!at->IsControlFlow()); 126986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = at->GetNext()->AsParallelMove(); 1270e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting siblings in a same block. We need to 1271e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // differentiate it with moves for connecting blocks, and input moves. 12728e3964b766652a0478e8e0e303e8556c997675f1Nicolas Geoffray if (move == nullptr || move->GetLifetimePosition() > position) { 127386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 127486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->SetLifetimePosition(position); 127586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray at->GetBlock()->InsertInstructionBefore(move, at->GetNext()); 127686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 127786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 127886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Move must happen before the instruction. 127986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* previous = at->GetPrevious(); 1280740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray if (previous == nullptr 1281740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray || !previous->IsParallelMove() 1282740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray || previous->GetLifetimePosition() != position) { 1283740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray // If the previous is a parallel move, then its position must be lower 1284740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray // than the given `position`: it was added just after the non-parallel 1285740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray // move instruction that precedes `instruction`. 1286740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray DCHECK(previous == nullptr 1287740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray || !previous->IsParallelMove() 1288740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray || previous->GetLifetimePosition() < position); 128986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 129086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->SetLifetimePosition(position); 129186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray at->GetBlock()->InsertInstructionBefore(move, at); 129286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 129386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = previous->AsParallelMove(); 129486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 129586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 129601ef345767ea609417fc511e42007705c9667546Nicolas Geoffray DCHECK_EQ(move->GetLifetimePosition(), position); 129742d1f5f006c8bdbcbf855c53036cd50f9c69753eNicolas Geoffray move->AddMove(source, destination, instruction); 129886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 129986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 130086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertParallelMoveAtExitOf(HBasicBlock* block, 1301740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray HInstruction* instruction, 130286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 130386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 13046c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(IsValidDestination(destination)) << destination; 130586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 130686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 130786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK_EQ(block->GetSuccessors().Size(), 1u); 130886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* last = block->GetLastInstruction(); 1309360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray // We insert moves at exit for phi predecessors and connecting blocks. 1310360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray // A block ending with an if cannot branch to a block with phis because 1311360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray // we do not allow critical edges. It can also not connect 1312360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray // a split interval between two blocks: the move has to happen in the successor. 1313360231a056e796c36ffe62348507e904dc9efb9bNicolas Geoffray DCHECK(!last->IsIf()); 131486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* previous = last->GetPrevious(); 131586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move; 1316e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting blocks. We need to differentiate 1317e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // it with moves for connecting siblings in a same block, and output moves. 13185976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray size_t position = last->GetLifetimePosition(); 1319740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray if (previous == nullptr || !previous->IsParallelMove() 13205976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray || previous->AsParallelMove()->GetLifetimePosition() != position) { 132186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 13225976857e65d3d0e7be0c4e3183e9483c85a76bb8Nicolas Geoffray move->SetLifetimePosition(position); 132386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray block->InsertInstructionBefore(move, last); 132486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 132586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = previous->AsParallelMove(); 132686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 132742d1f5f006c8bdbcbf855c53036cd50f9c69753eNicolas Geoffray move->AddMove(source, destination, instruction); 132886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 132986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 133086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertParallelMoveAtEntryOf(HBasicBlock* block, 1331740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray HInstruction* instruction, 133286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 133386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 13346c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(IsValidDestination(destination)) << destination; 133586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 133686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 133786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* first = block->GetFirstInstruction(); 133886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move = first->AsParallelMove(); 1339e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for connecting blocks. We need to differentiate 1340e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // it with moves for connecting siblings in a same block, and input moves. 1341e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray if (move == nullptr || move->GetLifetimePosition() != block->GetLifetimeStart()) { 134286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 134386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move->SetLifetimePosition(block->GetLifetimeStart()); 134486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray block->InsertInstructionBefore(move, first); 134586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 134642d1f5f006c8bdbcbf855c53036cd50f9c69753eNicolas Geoffray move->AddMove(source, destination, instruction); 134786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 134886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 134986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::InsertMoveAfter(HInstruction* instruction, 135086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location source, 135186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location destination) const { 13526c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray DCHECK(IsValidDestination(destination)) << destination; 135386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (source.Equals(destination)) return; 135486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1355476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain if (instruction->IsPhi()) { 1356740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAtEntryOf(instruction->GetBlock(), instruction, source, destination); 135786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 135886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 135986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 1360e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray size_t position = instruction->GetLifetimePosition() + 1; 136186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HParallelMove* move = instruction->GetNext()->AsParallelMove(); 1362e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // This is a parallel move for moving the output of an instruction. We need 1363e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // to differentiate with input moves, moves for connecting siblings in a 1364e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray // and moves for connecting blocks. 1365e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray if (move == nullptr || move->GetLifetimePosition() != position) { 136686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray move = new (allocator_) HParallelMove(allocator_); 1367e27f31a81636ad74bd3376ee39cf215941b85c0eNicolas Geoffray move->SetLifetimePosition(position); 136886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray instruction->GetBlock()->InsertInstructionBefore(move, instruction->GetNext()); 136986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 137042d1f5f006c8bdbcbf855c53036cd50f9c69753eNicolas Geoffray move->AddMove(source, destination, instruction); 137186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 137286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 137386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::ConnectSiblings(LiveInterval* interval) { 137486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = interval; 137586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->HasSpillSlot() && current->HasRegister()) { 137686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // We spill eagerly, so move must be at definition. 137786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray InsertMoveAfter(interval->GetDefinedBy(), 1378840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray interval->ToLocation(), 137901ef345767ea609417fc511e42007705c9667546Nicolas Geoffray interval->NeedsTwoSpillSlots() 1380412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray ? Location::DoubleStackSlot(interval->GetParent()->GetSpillSlot()) 1381412f10cfed002ab617c78f2621d68446ca4dd8bdNicolas Geoffray : Location::StackSlot(interval->GetParent()->GetSpillSlot())); 138286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 138386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray UsePosition* use = current->GetFirstUse(); 138486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 138586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Walk over all siblings, updating locations of use positions, and 138686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // connecting them when they are adjacent. 138786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray do { 138801ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location source = current->ToLocation(); 138986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 139086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Walk over all uses covered by this interval, and update the location 139186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // information. 139286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray while (use != nullptr && use->GetPosition() <= current->GetEnd()) { 13933946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LocationSummary* locations = use->GetUser()->GetLocations(); 13943946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (use->GetIsEnvironment()) { 13953946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray locations->SetEnvironmentAt(use->GetInputIndex(), source); 13963946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } else { 139786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location expected_location = locations->InAt(use->GetInputIndex()); 139871fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe // The expected (actual) location may be invalid in case the input is unused. Currently 139971fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe // this only happens for intrinsics. 140071fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe if (expected_location.IsValid()) { 140171fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe if (expected_location.IsUnallocated()) { 140271fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe locations->SetInAt(use->GetInputIndex(), source); 140371fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe } else if (!expected_location.IsConstant()) { 140471fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe AddInputMoveFor(use->GetUser(), source, expected_location); 140571fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe } 140671fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe } else { 140771fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe DCHECK(use->GetUser()->IsInvoke()); 140871fb52fee246b7d511f520febbd73dc7a9bbca79Andreas Gampe DCHECK(use->GetUser()->AsInvoke()->GetIntrinsic() != Intrinsics::kNone); 140986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 141086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 141186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray use = use->GetNext(); 141286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 141386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 141486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // If the next interval starts just after this one, and has a register, 141586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // insert a move. 141686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* next_sibling = current->GetNextSibling(); 141786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (next_sibling != nullptr 141886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && next_sibling->HasRegister() 141986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray && current->GetEnd() == next_sibling->GetStart()) { 142001ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location destination = next_sibling->ToLocation(); 1421740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAt(current->GetEnd(), interval->GetDefinedBy(), source, destination); 142286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 14233946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 14243946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // At each safepoint, we record stack and register information. 14253946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0, e = safepoints_.Size(); i < e; ++i) { 14263946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray HInstruction* safepoint = safepoints_.Get(i); 14273946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t position = safepoint->GetLifetimePosition(); 14283946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LocationSummary* locations = safepoint->GetLocations(); 1429b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray if (!current->Covers(position)) { 1430b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray continue; 1431b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray } 1432b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray if (interval->GetStart() == position) { 1433b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // The safepoint is for this instruction, so the location of the instruction 1434b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray // does not need to be saved. 1435b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray continue; 1436b5f62b3dc5ac2731ba8ad53cdf3d9bdb14fbf86bNicolas Geoffray } 14373946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 14383bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray if ((current->GetType() == Primitive::kPrimNot) && current->GetParent()->HasSpillSlot()) { 14393946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray locations->SetStackBit(current->GetParent()->GetSpillSlot() / kVRegSize); 14403946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 14413946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 14423946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray switch (source.GetKind()) { 14433946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kRegister: { 14443bca0df855f0e575c6ee020ed016999fc8f14122Nicolas Geoffray locations->AddLiveRegister(source); 1445988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray if (kIsDebugBuild && locations->OnlyCallsOnSlowPath()) { 1446988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray DCHECK_LE(locations->GetNumberOfLiveRegisters(), 1447988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray maximum_number_of_live_core_registers_ + 1448988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray maximum_number_of_live_fp_registers_); 1449988939683c26c0b1c8808fc206add6337319509aNicolas Geoffray } 14503946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray if (current->GetType() == Primitive::kPrimNot) { 145156b9ee6fe1d6880c5fca0e7feb28b25a1ded2e2fNicolas Geoffray locations->SetRegisterBit(source.reg()); 14523946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 14533946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray break; 14543946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 1455102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray case Location::kFpuRegister: { 1456102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray locations->AddLiveRegister(source); 1457102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray break; 1458102cbed1e52b7c5f09458b44903fe97bb3e14d5fNicolas Geoffray } 14596c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray 14606c2dff8ff8e1440fa4d9e1b2ba2a44d036882801Nicolas Geoffray case Location::kRegisterPair: 1461840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray case Location::kFpuRegisterPair: { 1462840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray locations->AddLiveRegister(source.ToLow()); 1463840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray locations->AddLiveRegister(source.ToHigh()); 1464840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray break; 1465840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 14663946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kStackSlot: // Fall-through 14673946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kDoubleStackSlot: // Fall-through 14683946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray case Location::kConstant: { 14693946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Nothing to do. 14703946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray break; 14713946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 14723946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray default: { 14733946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LOG(FATAL) << "Unexpected location for object"; 14743946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 14753946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 14763946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 147786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current = next_sibling; 147886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } while (current != nullptr); 147986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(use == nullptr); 148086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 148186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 148286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval, 148386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* from, 148486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* to) const { 148586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (interval->GetNextSibling() == nullptr) { 148686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Nothing to connect. The whole range was allocated to the same location. 148786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 148886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 148986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 149046fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray // Intervals end at the lifetime end of a block. The decrement by one 149146fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray // ensures the `Cover` call will return true. 149286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray size_t from_position = from->GetLifetimeEnd() - 1; 149346fbaab1bf2981f2768b046abf43e368663daacdNicolas Geoffray size_t to_position = to->GetLifetimeStart(); 149486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 149586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* destination = nullptr; 149686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* source = nullptr; 149786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 149886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = interval; 149986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 150086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Check the intervals that cover `from` and `to`. 150186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray while ((current != nullptr) && (source == nullptr || destination == nullptr)) { 150286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->Covers(from_position)) { 150386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(source == nullptr); 150486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray source = current; 150586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 150686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (current->Covers(to_position)) { 150786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(destination == nullptr); 150886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray destination = current; 150986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 151086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 151186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current = current->GetNextSibling(); 151286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 151386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 151486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (destination == source) { 151586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Interval was not split. 151686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 151786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 151886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 15198ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray DCHECK(destination != nullptr && source != nullptr); 15208ddb00ca935733f5d3b07816e5bb33d6cabe6ec4Nicolas Geoffray 152186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (!destination->HasRegister()) { 152286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Values are eagerly spilled. Spill slot already contains appropriate value. 152386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray return; 152486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 152586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 152686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // If `from` has only one successor, we can put the moves at the exit of it. Otherwise 152786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // we need to put the moves at the entry of `to`. 152886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (from->GetSuccessors().Size() == 1) { 1529740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAtExitOf(from, 1530740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray interval->GetParent()->GetDefinedBy(), 153101ef345767ea609417fc511e42007705c9667546Nicolas Geoffray source->ToLocation(), 153201ef345767ea609417fc511e42007705c9667546Nicolas Geoffray destination->ToLocation()); 153386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 153486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK_EQ(to->GetPredecessors().Size(), 1u); 1535740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAtEntryOf(to, 1536740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray interval->GetParent()->GetDefinedBy(), 153701ef345767ea609417fc511e42007705c9667546Nicolas Geoffray source->ToLocation(), 153801ef345767ea609417fc511e42007705c9667546Nicolas Geoffray destination->ToLocation()); 153986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 154086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray} 154186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 154286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffrayvoid RegisterAllocator::Resolve() { 1543776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray codegen_->InitializeCodeGeneration(GetNumberOfSpillSlots(), 15444c204bafbc8d596894f8cb8ec696f5be1c6f12d8Nicolas Geoffray maximum_number_of_live_core_registers_, 15454c204bafbc8d596894f8cb8ec696f5be1c6f12d8Nicolas Geoffray maximum_number_of_live_fp_registers_, 15464c204bafbc8d596894f8cb8ec696f5be1c6f12d8Nicolas Geoffray reserved_out_slots_, 15474c204bafbc8d596894f8cb8ec696f5be1c6f12d8Nicolas Geoffray liveness_.GetLinearOrder()); 154886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 154986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Adjust the Out Location of instructions. 155086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // TODO: Use pointers of Location inside LiveInterval to avoid doing another iteration. 155186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { 155286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 155386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* current = instruction->GetLiveInterval(); 155486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LocationSummary* locations = instruction->GetLocations(); 155586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray Location location = locations->Out(); 1556476df557fed5f0b3f32f8d11a654674bb403a8f8Roland Levillain if (instruction->IsParameterValue()) { 155786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Now that we know the frame size, adjust the parameter's location. 155886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (location.IsStackSlot()) { 155986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray location = Location::StackSlot(location.GetStackIndex() + codegen_->GetFrameSize()); 156086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(location.GetStackIndex()); 1561f43083d560565aea46c602adb86423daeefe589dNicolas Geoffray locations->UpdateOut(location); 156286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else if (location.IsDoubleStackSlot()) { 156386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray location = Location::DoubleStackSlot(location.GetStackIndex() + codegen_->GetFrameSize()); 156486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(location.GetStackIndex()); 1565f43083d560565aea46c602adb86423daeefe589dNicolas Geoffray locations->UpdateOut(location); 156686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else if (current->HasSpillSlot()) { 156786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray current->SetSpillSlot(current->GetSpillSlot() + codegen_->GetFrameSize()); 156886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 1569776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray } else if (current->HasSpillSlot()) { 1570776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // Adjust the stack slot, now that we know the number of them for each type. 1571776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // The way this implementation lays out the stack is the following: 1572776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // [parameter slots ] 1573776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // [double spill slots ] 1574776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // [long spill slots ] 1575776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // [float spill slots ] 1576776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // [int/ref values ] 1577776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // [maximum out values ] (number of arguments for calls) 1578776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray // [art method ]. 1579776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray uint32_t slot = current->GetSpillSlot(); 1580776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray switch (current->GetType()) { 1581776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimDouble: 1582776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray slot += long_spill_slots_.Size(); 1583776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray FALLTHROUGH_INTENDED; 1584776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimLong: 1585776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray slot += float_spill_slots_.Size(); 1586776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray FALLTHROUGH_INTENDED; 1587776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimFloat: 1588776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray slot += int_spill_slots_.Size(); 1589776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray FALLTHROUGH_INTENDED; 1590776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimNot: 1591776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimInt: 1592776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimChar: 1593776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimByte: 1594776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimBoolean: 1595776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimShort: 1596776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray slot += reserved_out_slots_; 1597776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray break; 1598776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray case Primitive::kPrimVoid: 1599776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray LOG(FATAL) << "Unexpected type for interval " << current->GetType(); 1600776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray } 1601776b3184ee04092b11edc781cdb81e8ed60601e3Nicolas Geoffray current->SetSpillSlot(slot * kVRegSize); 160286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 160386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 160401ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location source = current->ToLocation(); 160586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 160686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (location.IsUnallocated()) { 160786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray if (location.GetPolicy() == Location::kSameAsFirstInput) { 1608d0d4852847432368b090c184d6639e573538dccfCalin Juravle if (locations->InAt(0).IsUnallocated()) { 1609d0d4852847432368b090c184d6639e573538dccfCalin Juravle locations->SetInAt(0, source); 1610d0d4852847432368b090c184d6639e573538dccfCalin Juravle } else { 1611d0d4852847432368b090c184d6639e573538dccfCalin Juravle DCHECK(locations->InAt(0).Equals(source)); 1612d0d4852847432368b090c184d6639e573538dccfCalin Juravle } 161386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 1614829280cc90b7a84db42864589b4bafb4c94a79d9Nicolas Geoffray locations->UpdateOut(source); 161586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } else { 161686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK(source.Equals(location)); 161786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 161886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 161986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 162086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Connect siblings. 162186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { 162286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); 162386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ConnectSiblings(instruction->GetLiveInterval()); 162486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 162586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 162686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Resolve non-linear control flow across branches. Order does not matter. 162786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (HLinearOrderIterator it(liveness_); !it.Done(); it.Advance()) { 162886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* block = it.Current(); 162986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray BitVector* live = liveness_.GetLiveInSet(*block); 163086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (uint32_t idx : live->Indexes()) { 163186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* current = liveness_.GetInstructionFromSsaIndex(idx); 163286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray LiveInterval* interval = current->GetLiveInterval(); 163386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) { 163486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray ConnectSplitSiblings(interval, block->GetPredecessors().Get(i), block); 163586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 163686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 163786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 163886dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray 163986dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray // Resolve phi inputs. Order does not matter. 164086dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (HLinearOrderIterator it(liveness_); !it.Done(); it.Advance()) { 164186dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* current = it.Current(); 1642277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe for (HInstructionIterator inst_it(current->GetPhis()); !inst_it.Done(); inst_it.Advance()) { 1643277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe HInstruction* phi = inst_it.Current(); 164486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray for (size_t i = 0, e = current->GetPredecessors().Size(); i < e; ++i) { 164586dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HBasicBlock* predecessor = current->GetPredecessors().Get(i); 164686dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray DCHECK_EQ(predecessor->GetSuccessors().Size(), 1u); 164786dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray HInstruction* input = phi->InputAt(i); 164801ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location source = input->GetLiveInterval()->GetLocationAt( 164901ef345767ea609417fc511e42007705c9667546Nicolas Geoffray predecessor->GetLifetimeEnd() - 1); 165001ef345767ea609417fc511e42007705c9667546Nicolas Geoffray Location destination = phi->GetLiveInterval()->ToLocation(); 1651740475d5f45b8caa2c3c6fc51e657ecf4f3547e5Nicolas Geoffray InsertParallelMoveAtExitOf(predecessor, nullptr, source, destination); 165286dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 165386dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 165486dbb9a12119273039ce272b41c809fa548b37b6Nicolas Geoffray } 16553946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray 16563946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray // Assign temp locations. 16573946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray HInstruction* current = nullptr; 16583946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray size_t temp_index = 0; 16593946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray for (size_t i = 0; i < temp_intervals_.Size(); ++i) { 16603946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray LiveInterval* temp = temp_intervals_.Get(i); 1661840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (temp->IsHighInterval()) { 1662840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray // High intervals can be skipped, they are already handled by the low interval. 1663840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray continue; 1664840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 166501ef345767ea609417fc511e42007705c9667546Nicolas Geoffray HInstruction* at = liveness_.GetTempUser(temp); 166601ef345767ea609417fc511e42007705c9667546Nicolas Geoffray if (at != current) { 16673946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray temp_index = 0; 166801ef345767ea609417fc511e42007705c9667546Nicolas Geoffray current = at; 16693946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 167001ef345767ea609417fc511e42007705c9667546Nicolas Geoffray LocationSummary* locations = at->GetLocations(); 16715368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain switch (temp->GetType()) { 16725368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain case Primitive::kPrimInt: 16735368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain locations->SetTempAt( 16745368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain temp_index++, Location::RegisterLocation(temp->GetRegister())); 16755368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain break; 16765368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain 16775368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain case Primitive::kPrimDouble: 1678840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray if (codegen_->NeedsTwoRegisters(Primitive::kPrimDouble)) { 1679840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray Location location = Location::FpuRegisterPairLocation( 1680840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray temp->GetRegister(), temp->GetHighInterval()->GetRegister()); 1681840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray locations->SetTempAt(temp_index++, location); 1682840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } else { 1683840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray locations->SetTempAt( 1684840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray temp_index++, Location::FpuRegisterLocation(temp->GetRegister())); 1685840e5461a85f8908f51e7f6cd562a9129ff0e7ceNicolas Geoffray } 16865368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain break; 16875368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain 16885368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain default: 16895368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain LOG(FATAL) << "Unexpected type for temporary location " 16905368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain << temp->GetType(); 16915368c219a462defc90c4b896b34eb7506ba5c142Roland Levillain } 16923946844c34ad965515f677084b07d663d70ad1b8Nicolas Geoffray } 169331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray} 169431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 1695a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} // namespace art 1696