register_allocator.cc revision 31d76b42ef5165351499da3f8ee0ac147428c5ed
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 19a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray#include "code_generator.h" 20a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray#include "ssa_liveness_analysis.h" 21a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 22a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraynamespace art { 23a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 24a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraystatic constexpr size_t kMaxLifetimePosition = -1; 2531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffraystatic constexpr size_t kDefaultNumberOfSpillSlots = 4; 26a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 27a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas GeoffrayRegisterAllocator::RegisterAllocator(ArenaAllocator* allocator, const CodeGenerator& codegen) 28a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray : allocator_(allocator), 29a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen_(codegen), 30a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray unhandled_(allocator, 0), 31a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_(allocator, 0), 32a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_(allocator, 0), 33a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_(allocator, 0), 3431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray spill_slots_(allocator, kDefaultNumberOfSpillSlots), 35a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray processing_core_registers_(false), 36a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray number_of_registers_(-1), 37a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray registers_array_(nullptr), 38a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray blocked_registers_(allocator->AllocArray<bool>(codegen.GetNumberOfRegisters())) { 39a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen.SetupBlockedRegisters(blocked_registers_); 40a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 41a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 42a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraystatic bool ShouldProcess(bool processing_core_registers, HInstruction* instruction) { 43a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool is_core_register = (instruction->GetType() != Primitive::kPrimDouble) 44a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray && (instruction->GetType() != Primitive::kPrimFloat); 45a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return processing_core_registers == is_core_register; 46a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 47a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 48a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffrayvoid RegisterAllocator::AllocateRegistersInternal(const SsaLivenessAnalysis& liveness) { 49a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray number_of_registers_ = processing_core_registers_ 50a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray ? codegen_.GetNumberOfCoreRegisters() 51a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray : codegen_.GetNumberOfFloatingPointRegisters(); 52a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 53a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_); 54a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 55a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Iterate post-order, to ensure the list is sorted, and the last added interval 56a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // is the one with the lowest start position. 57a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = liveness.GetNumberOfSsaValues(); i > 0; --i) { 58a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray HInstruction* instruction = liveness.GetInstructionFromSsaIndex(i - 1); 59a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (ShouldProcess(processing_core_registers_, instruction)) { 60a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* current = instruction->GetLiveInterval(); 61a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(unhandled_.IsEmpty() || current->StartsBefore(unhandled_.Peek())); 62a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray unhandled_.Add(current); 63a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 64a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 65a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 66a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LinearScan(); 67a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (kIsDebugBuild) { 68a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray ValidateInternal(liveness, true); 69a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 70a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 71a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 72a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::ValidateInternal(const SsaLivenessAnalysis& liveness, 73a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool log_fatal_on_failure) const { 74a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // To simplify unit testing, we eagerly create the array of intervals, and 75a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // call the helper method. 76a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray GrowableArray<LiveInterval*> intervals(allocator_, 0); 77a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < liveness.GetNumberOfSsaValues(); ++i) { 78a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray HInstruction* instruction = liveness.GetInstructionFromSsaIndex(i); 79a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (ShouldProcess(processing_core_registers_, instruction)) { 80a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray intervals.Add(instruction->GetLiveInterval()); 81a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 82a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 8331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray return ValidateIntervals(intervals, spill_slots_.Size(), codegen_, allocator_, 8431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray processing_core_registers_, log_fatal_on_failure); 85a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 86a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 8731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffrayclass AllRangesIterator : public ValueObject { 8831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray public: 8931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray explicit AllRangesIterator(LiveInterval* interval) 9031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray : current_interval_(interval), 9131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_(interval->GetFirstRange()) {} 9231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 9331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray bool Done() const { return current_interval_ == nullptr; } 9431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveRange* CurrentRange() const { return current_range_; } 9531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* CurrentInterval() const { return current_interval_; } 9631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 9731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray void Advance() { 9831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_ = current_range_->GetNext(); 9931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current_range_ == nullptr) { 10031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_interval_ = current_interval_->GetNextSibling(); 10131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current_interval_ != nullptr) { 10231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray current_range_ = current_interval_->GetFirstRange(); 10331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 10431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 10531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 10631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 10731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray private: 10831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* current_interval_; 10931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveRange* current_range_; 11031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 11131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray DISALLOW_COPY_AND_ASSIGN(AllRangesIterator); 11231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray}; 11331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 11431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffraybool RegisterAllocator::ValidateIntervals(const GrowableArray<LiveInterval*>& intervals, 11531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray size_t number_of_spill_slots, 116a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray const CodeGenerator& codegen, 117a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray ArenaAllocator* allocator, 118a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool processing_core_registers, 119a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool log_fatal_on_failure) { 120a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t number_of_registers = processing_core_registers 121a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray ? codegen.GetNumberOfCoreRegisters() 122a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray : codegen.GetNumberOfFloatingPointRegisters(); 12331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray GrowableArray<ArenaBitVector*> liveness_of_values( 12431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray allocator, number_of_registers + number_of_spill_slots); 125a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 126a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Allocate a bit vector per register. A live interval that has a register 127a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // allocated will populate the associated bit vector based on its live ranges. 12831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t i = 0; i < number_of_registers + number_of_spill_slots; ++i) { 12931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_values.Add(new (allocator) ArenaBitVector(allocator, 0, true)); 130a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 131a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 13231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t i = 0, e = intervals.Size(); i < e; ++i) { 13331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (AllRangesIterator it(intervals.Get(i)); !it.Done(); it.Advance()) { 13431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* current = it.CurrentInterval(); 13531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current->GetParent()->HasSpillSlot()) { 13631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray BitVector* liveness_of_spill_slot = liveness_of_values.Get( 13731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray number_of_registers + current->GetParent()->GetSpillSlot() / kVRegSize); 13831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 13931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (liveness_of_spill_slot->IsBitSet(j)) { 14031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (log_fatal_on_failure) { 14131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray std::ostringstream message; 14231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray message << "Spill slot conflict at " << j; 14331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LOG(FATAL) << message.str(); 14431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 14531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray return false; 14631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 14731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 14831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_spill_slot->SetBit(j); 14931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 15031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 151a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 15231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 15331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (current->HasRegister()) { 15431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray BitVector* liveness_of_register = liveness_of_values.Get(current->GetRegister()); 15531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { 15631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (liveness_of_register->IsBitSet(j)) { 157a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (log_fatal_on_failure) { 158a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray std::ostringstream message; 159a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray message << "Register conflict at " << j << " for "; 160a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (processing_core_registers) { 161a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen.DumpCoreRegister(message, current->GetRegister()); 162a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 163a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen.DumpFloatingPointRegister(message, current->GetRegister()); 164a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 165a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LOG(FATAL) << message.str(); 166a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 167a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 168a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 169a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 17031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray liveness_of_register->SetBit(j); 171a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 172a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 17331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 17431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 175a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 176a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 177a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 178a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 179a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffrayvoid RegisterAllocator::DumpInterval(std::ostream& stream, LiveInterval* interval) { 180a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray interval->Dump(stream); 181a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << ": "; 182a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->HasRegister()) { 183a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (processing_core_registers_) { 184a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen_.DumpCoreRegister(stream, interval->GetRegister()); 185a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 186a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray codegen_.DumpFloatingPointRegister(stream, interval->GetRegister()); 187a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 188a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 189a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << "spilled"; 190a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 191a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray stream << std::endl; 192a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 193a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 194a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// By the book implementation of a linear scan register allocator. 195a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffrayvoid RegisterAllocator::LinearScan() { 196a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray while (!unhandled_.IsEmpty()) { 197a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (1) Remove interval with the lowest start position from unhandled. 198a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* current = unhandled_.Pop(); 199a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t position = current->GetStart(); 200a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 201a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (2) Remove currently active intervals that are dead at this position. 202a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Move active intervals that have a lifetime hole at this position 203a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // to inactive. 204a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < active_.Size(); ++i) { 205a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* interval = active_.Get(i); 206a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->IsDeadAt(position)) { 207a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Delete(interval); 208a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 209a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_.Add(interval); 210a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else if (!interval->Covers(position)) { 211a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Delete(interval); 212a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 213a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.Add(interval); 214a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 215a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 216a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 217a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (3) Remove currently inactive intervals that are dead at this position. 218a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Move inactive intervals that cover this position to active. 219a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < inactive_.Size(); ++i) { 220a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* interval = inactive_.Get(i); 221a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (interval->IsDeadAt(position)) { 222a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.Delete(interval); 223a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 224a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_.Add(interval); 225a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else if (interval->Covers(position)) { 226a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.Delete(interval); 227a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 228a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Add(interval); 229a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 230a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 231a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 232a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (4) Try to find an available register. 233a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray bool success = TryAllocateFreeReg(current); 234a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 235a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (5) If no register could be found, we need to spill. 236a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (!success) { 237a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray success = AllocateBlockedReg(current); 238a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 239a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 240a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // (6) If the interval had a register allocated, add it to the list of active 241a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // intervals. 242a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (success) { 243a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.Add(current); 244a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 245a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 246a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 247a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 248a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// Find a free register. If multiple are found, pick the register that 249a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// is free the longest. 250a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::TryAllocateFreeReg(LiveInterval* current) { 251a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t* free_until = registers_array_; 252a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 253a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // First set all registers to be free. 254a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 255a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray free_until[i] = kMaxLifetimePosition; 256a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 257a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 258a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each active interval, set its register to not free. 259a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = active_.Size(); i < e; ++i) { 260a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* interval = active_.Get(i); 261a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(interval->HasRegister()); 262a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray free_until[interval->GetRegister()] = 0; 263a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 264a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 265a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each inactive interval, set its register to be free until 266a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // the next intersection with `current`. 267a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Thanks to SSA, this should only be needed for intervals 268a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // that are the result of a split. 269a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { 270a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* inactive = inactive_.Get(i); 271a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(inactive->HasRegister()); 272a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t next_intersection = inactive->FirstIntersectionWith(current); 273a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (next_intersection != kNoLifetime) { 274a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray free_until[inactive->GetRegister()] = next_intersection; 275a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 276a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 277a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 278a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Pick the register that is free the longest. 279a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray int reg = -1; 280a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 281a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (IsBlocked(i)) continue; 282a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (reg == -1 || free_until[i] > free_until[reg]) { 283a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray reg = i; 284a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (free_until[i] == kMaxLifetimePosition) break; 285a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 286a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 287a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 288a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // If we could not find a register, we need to spill. 289a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (reg == -1 || free_until[reg] == 0) { 290a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 291a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 292a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 293a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray current->SetRegister(reg); 294a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (!current->IsDeadAt(free_until[reg])) { 295a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // If the register is only available for a subset of live ranges 296a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // covered by `current`, split `current` at the position where 297a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // the register is not available anymore. 298a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* split = Split(current, free_until[reg]); 299a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(split != nullptr); 300a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray AddToUnhandled(split); 301a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 302a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 303a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 304a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 305a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::IsBlocked(int reg) const { 306a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // TODO: This only works for core registers and needs to be adjusted for 307a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // floating point registers. 308a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(processing_core_registers_); 309a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return blocked_registers_[reg]; 310a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 311a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 312a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// Find the register that is used the last, and spill the interval 313a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// that holds it. If the first use of `current` is after that register 314a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray// we spill `current` instead. 315a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffraybool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) { 316a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t first_register_use = current->FirstRegisterUse(); 317a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (current->FirstRegisterUse() == kNoLifetime) { 31831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray AllocateSpillSlotFor(current); 319a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 320a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 321a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 322a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // First set all registers as not being used. 323a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t* next_use = registers_array_; 324a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 325a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray next_use[i] = kMaxLifetimePosition; 326a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 327a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 328a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each active interval, find the next use of its register after the 329a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // start of current. 330a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = active_.Size(); i < e; ++i) { 331a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* active = active_.Get(i); 332a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(active->HasRegister()); 333a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t use = active->FirstRegisterUseAfter(current->GetStart()); 334a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (use != kNoLifetime) { 335a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray next_use[active->GetRegister()] = use; 336a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 337a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 338a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 339a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // For each inactive interval, find the next use of its register after the 340a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // start of current. 341a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Thanks to SSA, this should only be needed for intervals 342a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // that are the result of a split. 343a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { 344a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* inactive = inactive_.Get(i); 345a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(inactive->HasRegister()); 346a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray size_t use = inactive->FirstRegisterUseAfter(current->GetStart()); 347a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (use != kNoLifetime) { 348a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray next_use[inactive->GetRegister()] = use; 349a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 350a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 351a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 352a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Pick the register that is used the last. 353a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray int reg = -1; 354a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < number_of_registers_; ++i) { 355a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (IsBlocked(i)) continue; 356a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (reg == -1 || next_use[i] > next_use[reg]) { 357a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray reg = i; 358a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (next_use[i] == kMaxLifetimePosition) break; 359a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 360a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 361a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 362a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (first_register_use >= next_use[reg]) { 363a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // If the first use of that instruction is after the last use of the found 364a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // register, we split this interval just before its first register use. 36531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray AllocateSpillSlotFor(current); 366a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* split = Split(current, first_register_use - 1); 367a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray AddToUnhandled(split); 368a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return false; 369a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 370a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Use this register and spill the active and inactives interval that 371a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // have that register. 372a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray current->SetRegister(reg); 373a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 374a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0, e = active_.Size(); i < e; ++i) { 375a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* active = active_.Get(i); 376a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (active->GetRegister() == reg) { 377a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* split = Split(active, current->GetStart()); 378a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray active_.DeleteAt(i); 379a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_.Add(active); 380a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray AddToUnhandled(split); 381a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray break; 382a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 383a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 384a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 385a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = 0; i < inactive_.Size(); ++i) { 386a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* inactive = inactive_.Get(i); 387a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (inactive->GetRegister() == reg) { 388a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* split = Split(inactive, current->GetStart()); 389a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray inactive_.DeleteAt(i); 390a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray handled_.Add(inactive); 391a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray AddToUnhandled(split); 392a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray --i; 393a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 394a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 395a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 396a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return true; 397a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 398a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 399a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 400a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffrayvoid RegisterAllocator::AddToUnhandled(LiveInterval* interval) { 401a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray for (size_t i = unhandled_.Size(); i > 0; --i) { 402a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* current = unhandled_.Get(i - 1); 403a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (current->StartsAfter(interval)) { 404a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray unhandled_.InsertAt(i, interval); 405a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray break; 406a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 407a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 408a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 409a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 410a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas GeoffrayLiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) { 411a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(position >= interval->GetStart()); 412a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray DCHECK(!interval->IsDeadAt(position)); 413a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray if (position == interval->GetStart()) { 414a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray // Spill slot will be allocated when handling `interval` again. 415a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray interval->ClearRegister(); 416a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return interval; 417a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } else { 418a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray LiveInterval* new_interval = interval->SplitAt(position); 419a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray return new_interval; 420a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray } 421a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} 422a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray 42331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffrayvoid RegisterAllocator::AllocateSpillSlotFor(LiveInterval* interval) { 42431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* parent = interval->GetParent(); 42531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 42631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // An instruction gets a spill slot for its entire lifetime. If the parent 42731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // of this interval already has a spill slot, there is nothing to do. 42831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (parent->HasSpillSlot()) { 42931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray return; 43031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 43131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 43231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // Find when this instruction dies. 43331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray LiveInterval* last_sibling = interval; 43431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray while (last_sibling->GetNextSibling() != nullptr) { 43531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray last_sibling = last_sibling->GetNextSibling(); 43631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 43731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray size_t end = last_sibling->GetEnd(); 43831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 43931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // Find an available spill slot. 44031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray size_t slot = 0; 44131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray for (size_t e = spill_slots_.Size(); slot < e; ++slot) { 44231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (spill_slots_.Get(slot) <= parent->GetStart()) { 44331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray break; 44431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 44531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 44631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 44731d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray if (slot == spill_slots_.Size()) { 44831d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray // We need a new spill slot. 44931d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray spill_slots_.Add(end); 45031d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } else { 45131d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray spill_slots_.Put(slot, end); 45231d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray } 45331d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 45431d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray interval->GetParent()->SetSpillSlot(slot * kVRegSize); 45531d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray} 45631d76b42ef5165351499da3f8ee0ac147428c5edNicolas Geoffray 457a7062e05e6048c7f817d784a5b94e3122e25b1ecNicolas Geoffray} // namespace art 458