| /* |
| * Copyright (C) 2016 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| #include "register_allocator.h" |
| |
| #include <iostream> |
| #include <sstream> |
| |
| #include "base/scoped_arena_allocator.h" |
| #include "base/scoped_arena_containers.h" |
| #include "base/bit_vector-inl.h" |
| #include "code_generator.h" |
| #include "register_allocator_graph_color.h" |
| #include "register_allocator_linear_scan.h" |
| #include "ssa_liveness_analysis.h" |
| |
| namespace art { |
| |
| RegisterAllocator::RegisterAllocator(ScopedArenaAllocator* allocator, |
| CodeGenerator* codegen, |
| const SsaLivenessAnalysis& liveness) |
| : allocator_(allocator), |
| codegen_(codegen), |
| liveness_(liveness) {} |
| |
| std::unique_ptr<RegisterAllocator> RegisterAllocator::Create(ScopedArenaAllocator* allocator, |
| CodeGenerator* codegen, |
| const SsaLivenessAnalysis& analysis, |
| Strategy strategy) { |
| switch (strategy) { |
| case kRegisterAllocatorLinearScan: |
| return std::unique_ptr<RegisterAllocator>( |
| new (allocator) RegisterAllocatorLinearScan(allocator, codegen, analysis)); |
| case kRegisterAllocatorGraphColor: |
| return std::unique_ptr<RegisterAllocator>( |
| new (allocator) RegisterAllocatorGraphColor(allocator, codegen, analysis)); |
| default: |
| LOG(FATAL) << "Invalid register allocation strategy: " << strategy; |
| UNREACHABLE(); |
| } |
| } |
| |
| RegisterAllocator::~RegisterAllocator() { |
| if (kIsDebugBuild) { |
| // Poison live interval pointers with "Error: BAD 71ve1nt3rval." |
| LiveInterval* bad_live_interval = reinterpret_cast<LiveInterval*>(0xebad7113u); |
| for (HBasicBlock* block : codegen_->GetGraph()->GetLinearOrder()) { |
| for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { |
| it.Current()->SetLiveInterval(bad_live_interval); |
| } |
| for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { |
| it.Current()->SetLiveInterval(bad_live_interval); |
| } |
| } |
| } |
| } |
| |
| bool RegisterAllocator::CanAllocateRegistersFor(const HGraph& graph ATTRIBUTE_UNUSED, |
| InstructionSet instruction_set) { |
| return instruction_set == InstructionSet::kArm |
| || instruction_set == InstructionSet::kArm64 |
| || instruction_set == InstructionSet::kMips |
| || instruction_set == InstructionSet::kMips64 |
| || instruction_set == InstructionSet::kThumb2 |
| || instruction_set == InstructionSet::kX86 |
| || instruction_set == InstructionSet::kX86_64; |
| } |
| |
| class AllRangesIterator : public ValueObject { |
| public: |
| explicit AllRangesIterator(LiveInterval* interval) |
| : current_interval_(interval), |
| current_range_(interval->GetFirstRange()) {} |
| |
| bool Done() const { return current_interval_ == nullptr; } |
| LiveRange* CurrentRange() const { return current_range_; } |
| LiveInterval* CurrentInterval() const { return current_interval_; } |
| |
| void Advance() { |
| current_range_ = current_range_->GetNext(); |
| if (current_range_ == nullptr) { |
| current_interval_ = current_interval_->GetNextSibling(); |
| if (current_interval_ != nullptr) { |
| current_range_ = current_interval_->GetFirstRange(); |
| } |
| } |
| } |
| |
| private: |
| LiveInterval* current_interval_; |
| LiveRange* current_range_; |
| |
| DISALLOW_COPY_AND_ASSIGN(AllRangesIterator); |
| }; |
| |
| bool RegisterAllocator::ValidateIntervals(ArrayRef<LiveInterval* const> intervals, |
| size_t number_of_spill_slots, |
| size_t number_of_out_slots, |
| const CodeGenerator& codegen, |
| bool processing_core_registers, |
| bool log_fatal_on_failure) { |
| size_t number_of_registers = processing_core_registers |
| ? codegen.GetNumberOfCoreRegisters() |
| : codegen.GetNumberOfFloatingPointRegisters(); |
| ScopedArenaAllocator allocator(codegen.GetGraph()->GetArenaStack()); |
| ScopedArenaVector<ArenaBitVector*> liveness_of_values( |
| allocator.Adapter(kArenaAllocRegisterAllocatorValidate)); |
| liveness_of_values.reserve(number_of_registers + number_of_spill_slots); |
| |
| size_t max_end = 0u; |
| for (LiveInterval* start_interval : intervals) { |
| for (AllRangesIterator it(start_interval); !it.Done(); it.Advance()) { |
| max_end = std::max(max_end, it.CurrentRange()->GetEnd()); |
| } |
| } |
| |
| // Allocate a bit vector per register. A live interval that has a register |
| // allocated will populate the associated bit vector based on its live ranges. |
| for (size_t i = 0; i < number_of_registers + number_of_spill_slots; ++i) { |
| liveness_of_values.push_back( |
| ArenaBitVector::Create(&allocator, max_end, false, kArenaAllocRegisterAllocatorValidate)); |
| liveness_of_values.back()->ClearAllBits(); |
| } |
| |
| for (LiveInterval* start_interval : intervals) { |
| for (AllRangesIterator it(start_interval); !it.Done(); it.Advance()) { |
| LiveInterval* current = it.CurrentInterval(); |
| HInstruction* defined_by = current->GetParent()->GetDefinedBy(); |
| if (current->GetParent()->HasSpillSlot() |
| // Parameters and current method have their own stack slot. |
| && !(defined_by != nullptr && (defined_by->IsParameterValue() |
| || defined_by->IsCurrentMethod()))) { |
| BitVector* liveness_of_spill_slot = liveness_of_values[number_of_registers |
| + current->GetParent()->GetSpillSlot() / kVRegSize |
| - number_of_out_slots]; |
| for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { |
| if (liveness_of_spill_slot->IsBitSet(j)) { |
| if (log_fatal_on_failure) { |
| std::ostringstream message; |
| message << "Spill slot conflict at " << j; |
| LOG(FATAL) << message.str(); |
| } else { |
| return false; |
| } |
| } else { |
| liveness_of_spill_slot->SetBit(j); |
| } |
| } |
| } |
| |
| if (current->HasRegister()) { |
| if (kIsDebugBuild && log_fatal_on_failure && !current->IsFixed()) { |
| // Only check when an error is fatal. Only tests code ask for non-fatal failures |
| // and test code may not properly fill the right information to the code generator. |
| CHECK(codegen.HasAllocatedRegister(processing_core_registers, current->GetRegister())); |
| } |
| BitVector* liveness_of_register = liveness_of_values[current->GetRegister()]; |
| for (size_t j = it.CurrentRange()->GetStart(); j < it.CurrentRange()->GetEnd(); ++j) { |
| if (liveness_of_register->IsBitSet(j)) { |
| if (current->IsUsingInputRegister() && current->CanUseInputRegister()) { |
| continue; |
| } |
| if (log_fatal_on_failure) { |
| std::ostringstream message; |
| message << "Register conflict at " << j << " "; |
| if (defined_by != nullptr) { |
| message << "(" << defined_by->DebugName() << ")"; |
| } |
| message << "for "; |
| if (processing_core_registers) { |
| codegen.DumpCoreRegister(message, current->GetRegister()); |
| } else { |
| codegen.DumpFloatingPointRegister(message, current->GetRegister()); |
| } |
| for (LiveInterval* interval : intervals) { |
| if (interval->HasRegister() |
| && interval->GetRegister() == current->GetRegister() |
| && interval->CoversSlow(j)) { |
| message << std::endl; |
| if (interval->GetDefinedBy() != nullptr) { |
| message << interval->GetDefinedBy()->GetKind() << " "; |
| } else { |
| message << "physical "; |
| } |
| interval->Dump(message); |
| } |
| } |
| LOG(FATAL) << message.str(); |
| } else { |
| return false; |
| } |
| } else { |
| liveness_of_register->SetBit(j); |
| } |
| } |
| } |
| } |
| } |
| return true; |
| } |
| |
| LiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) { |
| DCHECK_GE(position, interval->GetStart()); |
| DCHECK(!interval->IsDeadAt(position)); |
| if (position == interval->GetStart()) { |
| // Spill slot will be allocated when handling `interval` again. |
| interval->ClearRegister(); |
| if (interval->HasHighInterval()) { |
| interval->GetHighInterval()->ClearRegister(); |
| } else if (interval->HasLowInterval()) { |
| interval->GetLowInterval()->ClearRegister(); |
| } |
| return interval; |
| } else { |
| LiveInterval* new_interval = interval->SplitAt(position); |
| if (interval->HasHighInterval()) { |
| LiveInterval* high = interval->GetHighInterval()->SplitAt(position); |
| new_interval->SetHighInterval(high); |
| high->SetLowInterval(new_interval); |
| } else if (interval->HasLowInterval()) { |
| LiveInterval* low = interval->GetLowInterval()->SplitAt(position); |
| new_interval->SetLowInterval(low); |
| low->SetHighInterval(new_interval); |
| } |
| return new_interval; |
| } |
| } |
| |
| LiveInterval* RegisterAllocator::SplitBetween(LiveInterval* interval, size_t from, size_t to) { |
| HBasicBlock* block_from = liveness_.GetBlockFromPosition(from / 2); |
| HBasicBlock* block_to = liveness_.GetBlockFromPosition(to / 2); |
| DCHECK(block_from != nullptr); |
| DCHECK(block_to != nullptr); |
| |
| // Both locations are in the same block. We split at the given location. |
| if (block_from == block_to) { |
| return Split(interval, to); |
| } |
| |
| /* |
| * Non-linear control flow will force moves at every branch instruction to the new location. |
| * To avoid having all branches doing the moves, we find the next non-linear position and |
| * split the interval at this position. Take the following example (block number is the linear |
| * order position): |
| * |
| * B1 |
| * / \ |
| * B2 B3 |
| * \ / |
| * B4 |
| * |
| * B2 needs to split an interval, whose next use is in B4. If we were to split at the |
| * beginning of B4, B3 would need to do a move between B3 and B4 to ensure the interval |
| * is now in the correct location. It makes performance worst if the interval is spilled |
| * and both B2 and B3 need to reload it before entering B4. |
| * |
| * By splitting at B3, we give a chance to the register allocator to allocate the |
| * interval to the same register as in B1, and therefore avoid doing any |
| * moves in B3. |
| */ |
| if (block_from->GetDominator() != nullptr) { |
| for (HBasicBlock* dominated : block_from->GetDominator()->GetDominatedBlocks()) { |
| size_t position = dominated->GetLifetimeStart(); |
| if ((position > from) && (block_to->GetLifetimeStart() > position)) { |
| // Even if we found a better block, we continue iterating in case |
| // a dominated block is closer. |
| // Note that dominated blocks are not sorted in liveness order. |
| block_to = dominated; |
| DCHECK_NE(block_to, block_from); |
| } |
| } |
| } |
| |
| // If `to` is in a loop, find the outermost loop header which does not contain `from`. |
| for (HLoopInformationOutwardIterator it(*block_to); !it.Done(); it.Advance()) { |
| HBasicBlock* header = it.Current()->GetHeader(); |
| if (block_from->GetLifetimeStart() >= header->GetLifetimeStart()) { |
| break; |
| } |
| block_to = header; |
| } |
| |
| // Split at the start of the found block, to piggy back on existing moves |
| // due to resolution if non-linear control flow (see `ConnectSplitSiblings`). |
| return Split(interval, block_to->GetLifetimeStart()); |
| } |
| |
| } // namespace art |
