From 7690562d40878f44823d5fb03a2084cfc677ec4a Mon Sep 17 00:00:00 2001 From: Nicolas Geoffray Date: Thu, 25 Sep 2014 14:39:26 +0100 Subject: [PATCH] Register allocator: refine instructions liveness. Add support for instructions that die at the beginning of another instruction. Before, an instruction needed to stay alive during the instruction, so the register allocator was not able not reuse the register. Change-Id: I5f11a80b0a20778227229eb797816edcc6365297 --- compiler/optimizing/locations.h | 10 +++++++ compiler/optimizing/register_allocator.cc | 14 ++++++---- compiler/optimizing/ssa_liveness_analysis.h | 43 ++++++++++++++++++++++------- 3 files changed, 52 insertions(+), 15 deletions(-) diff --git a/compiler/optimizing/locations.h b/compiler/optimizing/locations.h index a2f5bfaac..f358e051a 100644 --- a/compiler/optimizing/locations.h +++ b/compiler/optimizing/locations.h @@ -387,6 +387,16 @@ class LocationSummary : public ArenaObject { return &live_registers_; } + bool InputOverlapsWithOutputOrTemp(uint32_t input, bool is_environment) const { + if (is_environment) return true; + Location location = Out(); + // TODO: Add more policies. + if (input == 0 && location.IsUnallocated() && location.GetPolicy() == Location::kSameAsFirstInput) { + return false; + } + return true; + } + private: GrowableArray inputs_; GrowableArray temps_; diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc index 78f20a155..4b45f4301 100644 --- a/compiler/optimizing/register_allocator.cc +++ b/compiler/optimizing/register_allocator.cc @@ -205,7 +205,7 @@ void RegisterAllocator::ProcessInstruction(HInstruction* instruction) { LiveInterval* current = instruction->GetLiveInterval(); if (current == nullptr) return; - DCHECK(unhandled.IsEmpty() || current->StartsBefore(unhandled.Peek())); + DCHECK(unhandled.IsEmpty() || current->StartsBeforeOrAt(unhandled.Peek())); // Some instructions define their output in fixed register/stack slot. We need // to ensure we know these locations before doing register allocation. For a // given register, we create an interval that covers these locations. The register @@ -228,7 +228,7 @@ void RegisterAllocator::ProcessInstruction(HInstruction* instruction) { // Split before first register use. size_t first_register_use = current->FirstRegisterUse(); if (first_register_use != kNoLifetime) { - LiveInterval* split = Split(current, first_register_use - 1); + LiveInterval* split = Split(current, first_register_use); // Don't add direclty to `unhandled`, it needs to be sorted and the start // of this new interval might be after intervals already in the list. AddSorted(&unhandled, split); @@ -236,7 +236,7 @@ void RegisterAllocator::ProcessInstruction(HInstruction* instruction) { // Nothing to do, we won't allocate a register for this value. } } else { - DCHECK(unhandled.IsEmpty() || current->StartsBefore(unhandled.Peek())); + DCHECK(unhandled.IsEmpty() || current->StartsBeforeOrAt(unhandled.Peek())); unhandled.Add(current); } } @@ -586,7 +586,7 @@ bool RegisterAllocator::AllocateBlockedReg(LiveInterval* current) { // 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. AllocateSpillSlotFor(current); - LiveInterval* split = Split(current, first_register_use - 1); + LiveInterval* split = Split(current, first_register_use); AddSorted(unhandled_, split); return false; } else { @@ -977,7 +977,11 @@ void RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval, } size_t from_position = from->GetLifetimeEnd() - 1; - size_t to_position = to->GetLifetimeStart(); + // When an instructions dies at entry of another, and the latter is the beginning + // of a block, the register allocator ensures the former has a register + // at block->GetLifetimeStart() + 1. Since this is at a block boundary, it must + // must be handled in this method. + size_t to_position = to->GetLifetimeStart() + 1; LiveInterval* destination = nullptr; LiveInterval* source = nullptr; diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h index dea6181cb..3ef24137c 100644 --- a/compiler/optimizing/ssa_liveness_analysis.h +++ b/compiler/optimizing/ssa_liveness_analysis.h @@ -76,7 +76,7 @@ class LiveRange : public ArenaObject { private: size_t start_; - const size_t end_; + size_t end_; LiveRange* next_; friend class LiveInterval; @@ -99,13 +99,16 @@ class UsePosition : public ArenaObject { is_environment_(is_environment), position_(position), next_(next) { - DCHECK(user->AsPhi() != nullptr || GetPosition() == user->GetLifetimePosition() + 1); + DCHECK(user->IsPhi() + || (GetPosition() == user->GetLifetimePosition() + 1) + || (GetPosition() == user->GetLifetimePosition())); DCHECK(next_ == nullptr || next->GetPosition() >= GetPosition()); } size_t GetPosition() const { return position_; } UsePosition* GetNext() const { return next_; } + void SetNext(UsePosition* next) { next_ = next; } HInstruction* GetUser() const { return user_; } @@ -122,7 +125,7 @@ class UsePosition : public ArenaObject { const size_t input_index_; const bool is_environment_; const size_t position_; - UsePosition* const next_; + UsePosition* next_; DISALLOW_COPY_AND_ASSIGN(UsePosition); }; @@ -174,11 +177,29 @@ class LiveInterval : public ArenaObject { void AddUse(HInstruction* instruction, size_t input_index, bool is_environment) { // Set the use within the instruction. - // TODO: Use the instruction's location to know whether the instruction can die - // at entry, or needs to say alive within the user. - size_t position = instruction->GetLifetimePosition() + 1; + size_t position = instruction->GetLifetimePosition(); + if (instruction->GetLocations()->InputOverlapsWithOutputOrTemp(input_index, is_environment)) { + // If it overlaps, we need to make sure the user will not try to allocate a temp + // or its output to the same register. + ++position; + } size_t start_block_position = instruction->GetBlock()->GetLifetimeStart(); size_t end_block_position = instruction->GetBlock()->GetLifetimeEnd(); + if ((first_use_ != nullptr) + && (first_use_->GetUser() == instruction) + && (first_use_->GetPosition() < position)) { + // The user uses the instruction multiple times, and one use dies before the other. + // We update the use list so that the latter is first. + DCHECK(first_use_->GetPosition() + 1 == position); + UsePosition* new_use = new (allocator_) UsePosition( + instruction, input_index, is_environment, position, first_use_->GetNext()); + first_use_->SetNext(new_use); + if (first_range_->GetEnd() == first_use_->GetPosition()) { + first_range_->end_ = position; + } + return; + } + if (first_range_ == nullptr) { // First time we see a use of that interval. first_range_ = last_range_ = new (allocator_) LiveRange(start_block_position, position, nullptr); @@ -198,7 +219,7 @@ class LiveInterval : public ArenaObject { } void AddPhiUse(HInstruction* instruction, size_t input_index, HBasicBlock* block) { - DCHECK(instruction->AsPhi() != nullptr); + DCHECK(instruction->IsPhi()); first_use_ = new (allocator_) UsePosition( instruction, input_index, false, block->GetLifetimeEnd(), first_use_); } @@ -339,7 +360,9 @@ class LiveInterval : public ArenaObject { if (use_position >= position && !use->GetIsEnvironment()) { Location location = use->GetUser()->GetLocations()->InAt(use->GetInputIndex()); if (location.IsUnallocated() && location.GetPolicy() == Location::kRequiresRegister) { - return use_position; + // Return the lifetime just before the user, so that the interval has a register + // when entering the user. + return use->GetUser()->GetLifetimePosition() - 1; } } use = use->GetNext(); @@ -428,12 +451,12 @@ class LiveInterval : public ArenaObject { return nullptr; } - bool StartsBefore(LiveInterval* other) const { + bool StartsBeforeOrAt(LiveInterval* other) const { return GetStart() <= other->GetStart(); } bool StartsAfter(LiveInterval* other) const { - return GetStart() >= other->GetStart(); + return GetStart() > other->GetStart(); } void Dump(std::ostream& stream) const { -- 2.11.0