diff options
Diffstat (limited to 'compiler/optimizing/register_allocator.cc')
-rw-r--r-- | compiler/optimizing/register_allocator.cc | 378 |
1 files changed, 378 insertions, 0 deletions
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc new file mode 100644 index 0000000..dd175d2 --- /dev/null +++ b/compiler/optimizing/register_allocator.cc @@ -0,0 +1,378 @@ +/* + * Copyright (C) 2014 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 "code_generator.h" +#include "ssa_liveness_analysis.h" + +namespace art { + +static constexpr size_t kMaxLifetimePosition = -1; + +RegisterAllocator::RegisterAllocator(ArenaAllocator* allocator, const CodeGenerator& codegen) + : allocator_(allocator), + codegen_(codegen), + unhandled_(allocator, 0), + handled_(allocator, 0), + active_(allocator, 0), + inactive_(allocator, 0), + processing_core_registers_(false), + number_of_registers_(-1), + registers_array_(nullptr), + blocked_registers_(allocator->AllocArray<bool>(codegen.GetNumberOfRegisters())) { + codegen.SetupBlockedRegisters(blocked_registers_); +} + +static bool ShouldProcess(bool processing_core_registers, HInstruction* instruction) { + bool is_core_register = (instruction->GetType() != Primitive::kPrimDouble) + && (instruction->GetType() != Primitive::kPrimFloat); + return processing_core_registers == is_core_register; +} + +void RegisterAllocator::AllocateRegistersInternal(const SsaLivenessAnalysis& liveness) { + number_of_registers_ = processing_core_registers_ + ? codegen_.GetNumberOfCoreRegisters() + : codegen_.GetNumberOfFloatingPointRegisters(); + + registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_); + + // Iterate post-order, to ensure the list is sorted, and the last added interval + // is the one with the lowest start position. + for (size_t i = liveness.GetNumberOfSsaValues(); i > 0; --i) { + HInstruction* instruction = liveness.GetInstructionFromSsaIndex(i - 1); + if (ShouldProcess(processing_core_registers_, instruction)) { + LiveInterval* current = instruction->GetLiveInterval(); + DCHECK(unhandled_.IsEmpty() || current->StartsBefore(unhandled_.Peek())); + unhandled_.Add(current); + } + } + + LinearScan(); + if (kIsDebugBuild) { + ValidateInternal(liveness, true); + } +} + +bool RegisterAllocator::ValidateInternal(const SsaLivenessAnalysis& liveness, + bool log_fatal_on_failure) const { + // To simplify unit testing, we eagerly create the array of intervals, and + // call the helper method. + GrowableArray<LiveInterval*> intervals(allocator_, 0); + for (size_t i = 0; i < liveness.GetNumberOfSsaValues(); ++i) { + HInstruction* instruction = liveness.GetInstructionFromSsaIndex(i); + if (ShouldProcess(processing_core_registers_, instruction)) { + intervals.Add(instruction->GetLiveInterval()); + } + } + return ValidateIntervals(intervals, codegen_, allocator_, processing_core_registers_, + log_fatal_on_failure); +} + +bool RegisterAllocator::ValidateIntervals(const GrowableArray<LiveInterval*>& ranges, + const CodeGenerator& codegen, + ArenaAllocator* allocator, + bool processing_core_registers, + bool log_fatal_on_failure) { + size_t number_of_registers = processing_core_registers + ? codegen.GetNumberOfCoreRegisters() + : codegen.GetNumberOfFloatingPointRegisters(); + GrowableArray<ArenaBitVector*> bit_vectors(allocator, number_of_registers); + + // 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; i++) { + bit_vectors.Add(new (allocator) ArenaBitVector(allocator, 0, true)); + } + + for (size_t i = 0, e = ranges.Size(); i < e; ++i) { + LiveInterval* current = ranges.Get(i); + do { + if (!current->HasRegister()) { + continue; + } + BitVector* vector = bit_vectors.Get(current->GetRegister()); + LiveRange* range = current->GetFirstRange(); + do { + for (size_t j = range->GetStart(); j < range->GetEnd(); ++j) { + if (vector->IsBitSet(j)) { + if (log_fatal_on_failure) { + std::ostringstream message; + message << "Register conflict at " << j << " for "; + if (processing_core_registers) { + codegen.DumpCoreRegister(message, current->GetRegister()); + } else { + codegen.DumpFloatingPointRegister(message, current->GetRegister()); + } + LOG(FATAL) << message.str(); + } else { + return false; + } + } else { + vector->SetBit(j); + } + } + } while ((range = range->GetNext()) != nullptr); + } while ((current = current->GetNextSibling()) != nullptr); + } + return true; +} + +void RegisterAllocator::DumpInterval(std::ostream& stream, LiveInterval* interval) { + interval->Dump(stream); + stream << ": "; + if (interval->HasRegister()) { + if (processing_core_registers_) { + codegen_.DumpCoreRegister(stream, interval->GetRegister()); + } else { + codegen_.DumpFloatingPointRegister(stream, interval->GetRegister()); + } + } else { + stream << "spilled"; + } + stream << std::endl; +} + +// By the book implementation of a linear scan register allocator. +void RegisterAllocator::LinearScan() { + while (!unhandled_.IsEmpty()) { + // (1) Remove interval with the lowest start position from unhandled. + LiveInterval* current = unhandled_.Pop(); + size_t position = current->GetStart(); + + // (2) Remove currently active intervals that are dead at this position. + // Move active intervals that have a lifetime hole at this position + // to inactive. + for (size_t i = 0; i < active_.Size(); ++i) { + LiveInterval* interval = active_.Get(i); + if (interval->IsDeadAt(position)) { + active_.Delete(interval); + --i; + handled_.Add(interval); + } else if (!interval->Covers(position)) { + active_.Delete(interval); + --i; + inactive_.Add(interval); + } + } + + // (3) Remove currently inactive intervals that are dead at this position. + // Move inactive intervals that cover this position to active. + for (size_t i = 0; i < inactive_.Size(); ++i) { + LiveInterval* interval = inactive_.Get(i); + if (interval->IsDeadAt(position)) { + inactive_.Delete(interval); + --i; + handled_.Add(interval); + } else if (interval->Covers(position)) { + inactive_.Delete(interval); + --i; + active_.Add(interval); + } + } + + // (4) Try to find an available register. + bool success = TryAllocateFreeReg(current); + + // (5) If no register could be found, we need to spill. + if (!success) { + success = AllocateBlockedReg(current); + } + + // (6) If the interval had a register allocated, add it to the list of active + // intervals. + if (success) { + active_.Add(current); + } + } +} + +// Find a free register. If multiple are found, pick the register that +// is free the longest. +bool RegisterAllocator::TryAllocateFreeReg(LiveInterval* current) { + size_t* free_until = registers_array_; + + // First set all registers to be free. + for (size_t i = 0; i < number_of_registers_; ++i) { + free_until[i] = kMaxLifetimePosition; + } + + // For each active interval, set its register to not free. + for (size_t i = 0, e = active_.Size(); i < e; ++i) { + LiveInterval* interval = active_.Get(i); + DCHECK(interval->HasRegister()); + free_until[interval->GetRegister()] = 0; + } + + // For each inactive interval, set its register to be free until + // the next intersection with `current`. + // Thanks to SSA, this should only be needed for intervals + // that are the result of a split. + for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { + LiveInterval* inactive = inactive_.Get(i); + DCHECK(inactive->HasRegister()); + size_t next_intersection = inactive->FirstIntersectionWith(current); + if (next_intersection != kNoLifetime) { + free_until[inactive->GetRegister()] = next_intersection; + } + } + + // Pick the register that is free the longest. + int reg = -1; + for (size_t i = 0; i < number_of_registers_; ++i) { + if (IsBlocked(i)) continue; + if (reg == -1 || free_until[i] > free_until[reg]) { + reg = i; + if (free_until[i] == kMaxLifetimePosition) break; + } + } + + // If we could not find a register, we need to spill. + if (reg == -1 || free_until[reg] == 0) { + return false; + } + + current->SetRegister(reg); + if (!current->IsDeadAt(free_until[reg])) { + // If the register is only available for a subset of live ranges + // covered by `current`, split `current` at the position where + // the register is not available anymore. + LiveInterval* split = Split(current, free_until[reg]); + DCHECK(split != nullptr); + AddToUnhandled(split); + } + return true; +} + +bool RegisterAllocator::IsBlocked(int reg) const { + // TODO: This only works for core registers and needs to be adjusted for + // floating point registers. + DCHECK(processing_core_registers_); + return blocked_registers_[reg]; +} + +// Find the register that is used the last, and spill the interval +// that holds it. If the first use of `current` is after that register +// we spill `current` instead. +bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) { + size_t first_register_use = current->FirstRegisterUse(); + if (current->FirstRegisterUse() == kNoLifetime) { + // TODO: Allocate spill slot for `current`. + return false; + } + + // First set all registers as not being used. + size_t* next_use = registers_array_; + for (size_t i = 0; i < number_of_registers_; ++i) { + next_use[i] = kMaxLifetimePosition; + } + + // For each active interval, find the next use of its register after the + // start of current. + for (size_t i = 0, e = active_.Size(); i < e; ++i) { + LiveInterval* active = active_.Get(i); + DCHECK(active->HasRegister()); + size_t use = active->FirstRegisterUseAfter(current->GetStart()); + if (use != kNoLifetime) { + next_use[active->GetRegister()] = use; + } + } + + // For each inactive interval, find the next use of its register after the + // start of current. + // Thanks to SSA, this should only be needed for intervals + // that are the result of a split. + for (size_t i = 0, e = inactive_.Size(); i < e; ++i) { + LiveInterval* inactive = inactive_.Get(i); + DCHECK(inactive->HasRegister()); + size_t use = inactive->FirstRegisterUseAfter(current->GetStart()); + if (use != kNoLifetime) { + next_use[inactive->GetRegister()] = use; + } + } + + // Pick the register that is used the last. + int reg = -1; + for (size_t i = 0; i < number_of_registers_; ++i) { + if (IsBlocked(i)) continue; + if (reg == -1 || next_use[i] > next_use[reg]) { + reg = i; + if (next_use[i] == kMaxLifetimePosition) break; + } + } + + if (first_register_use >= next_use[reg]) { + // If the first use of that instruction is after the last use of the found + // register, we split this interval just before its first register use. + LiveInterval* split = Split(current, first_register_use - 1); + AddToUnhandled(split); + return false; + } else { + // Use this register and spill the active and inactives interval that + // have that register. + current->SetRegister(reg); + + for (size_t i = 0, e = active_.Size(); i < e; ++i) { + LiveInterval* active = active_.Get(i); + if (active->GetRegister() == reg) { + LiveInterval* split = Split(active, current->GetStart()); + active_.DeleteAt(i); + handled_.Add(active); + AddToUnhandled(split); + break; + } + } + + for (size_t i = 0; i < inactive_.Size(); ++i) { + LiveInterval* inactive = inactive_.Get(i); + if (inactive->GetRegister() == reg) { + LiveInterval* split = Split(inactive, current->GetStart()); + inactive_.DeleteAt(i); + handled_.Add(inactive); + AddToUnhandled(split); + --i; + } + } + + return true; + } +} + +void RegisterAllocator::AddToUnhandled(LiveInterval* interval) { + for (size_t i = unhandled_.Size(); i > 0; --i) { + LiveInterval* current = unhandled_.Get(i - 1); + if (current->StartsAfter(interval)) { + unhandled_.InsertAt(i, interval); + break; + } + } +} + +LiveInterval* RegisterAllocator::Split(LiveInterval* interval, size_t position) { + DCHECK(position >= interval->GetStart()); + DCHECK(!interval->IsDeadAt(position)); + if (position == interval->GetStart()) { + // Spill slot will be allocated when handling `interval` again. + interval->ClearRegister(); + return interval; + } else { + LiveInterval* new_interval = interval->SplitAt(position); + // TODO: Allocate spill slot for `interval`. + return new_interval; + } +} + +} // namespace art |