| /* |
| * 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. |
| */ |
| |
| #ifndef ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_ |
| #define ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_ |
| |
| #include <iostream> |
| |
| #include "base/iteration_range.h" |
| #include "nodes.h" |
| #include "utils/intrusive_forward_list.h" |
| |
| namespace art { |
| |
| class CodeGenerator; |
| class SsaLivenessAnalysis; |
| |
| static constexpr int kNoRegister = -1; |
| |
| class BlockInfo : public ArenaObject<kArenaAllocSsaLiveness> { |
| public: |
| BlockInfo(ArenaAllocator* allocator, const HBasicBlock& block, size_t number_of_ssa_values) |
| : block_(block), |
| live_in_(allocator, number_of_ssa_values, false, kArenaAllocSsaLiveness), |
| live_out_(allocator, number_of_ssa_values, false, kArenaAllocSsaLiveness), |
| kill_(allocator, number_of_ssa_values, false, kArenaAllocSsaLiveness) { |
| UNUSED(block_); |
| live_in_.ClearAllBits(); |
| live_out_.ClearAllBits(); |
| kill_.ClearAllBits(); |
| } |
| |
| private: |
| const HBasicBlock& block_; |
| ArenaBitVector live_in_; |
| ArenaBitVector live_out_; |
| ArenaBitVector kill_; |
| |
| friend class SsaLivenessAnalysis; |
| |
| DISALLOW_COPY_AND_ASSIGN(BlockInfo); |
| }; |
| |
| /** |
| * A live range contains the start and end of a range where an instruction or a temporary |
| * is live. |
| */ |
| class LiveRange FINAL : public ArenaObject<kArenaAllocSsaLiveness> { |
| public: |
| LiveRange(size_t start, size_t end, LiveRange* next) : start_(start), end_(end), next_(next) { |
| DCHECK_LT(start, end); |
| DCHECK(next_ == nullptr || next_->GetStart() > GetEnd()); |
| } |
| |
| size_t GetStart() const { return start_; } |
| size_t GetEnd() const { return end_; } |
| LiveRange* GetNext() const { return next_; } |
| |
| bool IntersectsWith(const LiveRange& other) const { |
| return (start_ >= other.start_ && start_ < other.end_) |
| || (other.start_ >= start_ && other.start_ < end_); |
| } |
| |
| bool IsBefore(const LiveRange& other) const { |
| return end_ <= other.start_; |
| } |
| |
| void Dump(std::ostream& stream) const { |
| stream << "[" << start_ << "," << end_ << ")"; |
| } |
| |
| LiveRange* Dup(ArenaAllocator* allocator) const { |
| return new (allocator) LiveRange( |
| start_, end_, next_ == nullptr ? nullptr : next_->Dup(allocator)); |
| } |
| |
| LiveRange* GetLastRange() { |
| return next_ == nullptr ? this : next_->GetLastRange(); |
| } |
| |
| private: |
| size_t start_; |
| size_t end_; |
| LiveRange* next_; |
| |
| friend class LiveInterval; |
| |
| DISALLOW_COPY_AND_ASSIGN(LiveRange); |
| }; |
| |
| /** |
| * A use position represents a live interval use at a given position. |
| */ |
| class UsePosition : public ArenaObject<kArenaAllocSsaLiveness>, |
| public IntrusiveForwardListNode<UsePosition> { |
| public: |
| UsePosition(HInstruction* user, size_t input_index, size_t position) |
| : user_(user), |
| input_index_(input_index), |
| position_(position) { |
| } |
| |
| explicit UsePosition(size_t position) |
| : user_(nullptr), |
| input_index_(kNoInput), |
| position_(dchecked_integral_cast<uint32_t>(position)) { |
| } |
| |
| size_t GetPosition() const { return position_; } |
| |
| HInstruction* GetUser() const { return user_; } |
| |
| bool IsSynthesized() const { return user_ == nullptr; } |
| |
| size_t GetInputIndex() const { return input_index_; } |
| |
| void Dump(std::ostream& stream) const { |
| stream << position_; |
| } |
| |
| HLoopInformation* GetLoopInformation() const { |
| return user_->GetBlock()->GetLoopInformation(); |
| } |
| |
| UsePosition* Clone(ArenaAllocator* allocator) const { |
| return new (allocator) UsePosition(user_, input_index_, position_); |
| } |
| |
| bool RequiresRegister() const { |
| if (IsSynthesized()) return false; |
| Location location = GetUser()->GetLocations()->InAt(GetInputIndex()); |
| return location.IsUnallocated() && location.RequiresRegisterKind(); |
| } |
| |
| private: |
| static constexpr uint32_t kNoInput = static_cast<uint32_t>(-1); |
| |
| HInstruction* const user_; |
| const size_t input_index_; |
| const size_t position_; |
| |
| DISALLOW_COPY_AND_ASSIGN(UsePosition); |
| }; |
| using UsePositionList = IntrusiveForwardList<UsePosition>; |
| |
| /** |
| * An environment use position represents a live interval for environment use at a given position. |
| */ |
| class EnvUsePosition : public ArenaObject<kArenaAllocSsaLiveness>, |
| public IntrusiveForwardListNode<EnvUsePosition> { |
| public: |
| EnvUsePosition(HEnvironment* environment, |
| size_t input_index, |
| size_t position) |
| : environment_(environment), |
| input_index_(input_index), |
| position_(position) { |
| DCHECK(environment != nullptr); |
| } |
| |
| size_t GetPosition() const { return position_; } |
| |
| HEnvironment* GetEnvironment() const { return environment_; } |
| size_t GetInputIndex() const { return input_index_; } |
| |
| void Dump(std::ostream& stream) const { |
| stream << position_; |
| } |
| |
| EnvUsePosition* Clone(ArenaAllocator* allocator) const { |
| return new (allocator) EnvUsePosition(environment_, input_index_, position_); |
| } |
| |
| private: |
| HEnvironment* const environment_; |
| const size_t input_index_; |
| const size_t position_; |
| |
| DISALLOW_COPY_AND_ASSIGN(EnvUsePosition); |
| }; |
| using EnvUsePositionList = IntrusiveForwardList<EnvUsePosition>; |
| |
| template <typename Iterator> |
| inline Iterator FindUseAtOrAfterPosition(Iterator first, Iterator last, size_t position) { |
| using value_type = const typename Iterator::value_type; |
| static_assert(std::is_same<value_type, const UsePosition>::value || |
| std::is_same<value_type, const EnvUsePosition>::value, |
| "Expecting value type UsePosition or EnvUsePosition."); |
| Iterator ret = std::find_if( |
| first, last, [position](const value_type& use) { return use.GetPosition() >= position; }); |
| // Check that the processed range is sorted. Do not check the rest of the range to avoid |
| // increasing the complexity of callers from O(n) to O(n^2). |
| DCHECK(std::is_sorted( |
| first, |
| ret, |
| [](const value_type& lhs, const value_type& rhs) { |
| return lhs.GetPosition() < rhs.GetPosition(); |
| })); |
| return ret; |
| } |
| |
| template <typename Iterator> |
| inline IterationRange<Iterator> FindMatchingUseRange(Iterator first, |
| Iterator last, |
| size_t position_begin, |
| size_t position_end) { |
| Iterator begin = FindUseAtOrAfterPosition(first, last, position_begin); |
| Iterator end = FindUseAtOrAfterPosition(begin, last, position_end); |
| return MakeIterationRange(begin, end); |
| } |
| |
| class SafepointPosition : public ArenaObject<kArenaAllocSsaLiveness> { |
| public: |
| explicit SafepointPosition(HInstruction* instruction) |
| : instruction_(instruction), |
| next_(nullptr) {} |
| |
| void SetNext(SafepointPosition* next) { |
| next_ = next; |
| } |
| |
| size_t GetPosition() const { |
| return instruction_->GetLifetimePosition(); |
| } |
| |
| SafepointPosition* GetNext() const { |
| return next_; |
| } |
| |
| LocationSummary* GetLocations() const { |
| return instruction_->GetLocations(); |
| } |
| |
| HInstruction* GetInstruction() const { |
| return instruction_; |
| } |
| |
| private: |
| HInstruction* const instruction_; |
| SafepointPosition* next_; |
| |
| DISALLOW_COPY_AND_ASSIGN(SafepointPosition); |
| }; |
| |
| /** |
| * An interval is a list of disjoint live ranges where an instruction is live. |
| * Each instruction that has uses gets an interval. |
| */ |
| class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> { |
| public: |
| static LiveInterval* MakeInterval(ArenaAllocator* allocator, |
| Primitive::Type type, |
| HInstruction* instruction = nullptr) { |
| return new (allocator) LiveInterval(allocator, type, instruction); |
| } |
| |
| static LiveInterval* MakeFixedInterval(ArenaAllocator* allocator, int reg, Primitive::Type type) { |
| return new (allocator) LiveInterval(allocator, type, nullptr, true, reg, false); |
| } |
| |
| static LiveInterval* MakeTempInterval(ArenaAllocator* allocator, Primitive::Type type) { |
| return new (allocator) LiveInterval(allocator, type, nullptr, false, kNoRegister, true); |
| } |
| |
| bool IsFixed() const { return is_fixed_; } |
| bool IsTemp() const { return is_temp_; } |
| // This interval is the result of a split. |
| bool IsSplit() const { return parent_ != this; } |
| |
| void AddTempUse(HInstruction* instruction, size_t temp_index) { |
| DCHECK(IsTemp()); |
| DCHECK(GetUses().empty()) << "A temporary can only have one user"; |
| DCHECK(GetEnvironmentUses().empty()) << "A temporary cannot have environment user"; |
| size_t position = instruction->GetLifetimePosition(); |
| UsePosition* new_use = new (allocator_) UsePosition(instruction, temp_index, position); |
| uses_.push_front(*new_use); |
| AddRange(position, position + 1); |
| } |
| |
| // Record use of an input. The use will be recorded as an environment use if |
| // `environment` is not null and as register use otherwise. If `actual_user` |
| // is specified, the use will be recorded at `actual_user`'s lifetime position. |
| void AddUse(HInstruction* instruction, |
| HEnvironment* environment, |
| size_t input_index, |
| HInstruction* actual_user = nullptr, |
| bool keep_alive = false) { |
| bool is_environment = (environment != nullptr); |
| LocationSummary* locations = instruction->GetLocations(); |
| if (actual_user == nullptr) { |
| actual_user = instruction; |
| } |
| |
| // Set the use within the instruction. |
| size_t position = actual_user->GetLifetimePosition() + 1; |
| if (!is_environment) { |
| if (locations->IsFixedInput(input_index) || locations->OutputUsesSameAs(input_index)) { |
| // For fixed inputs and output same as input, the register allocator |
| // requires to have inputs die at the instruction, so that input moves use the |
| // location of the input just before that instruction (and not potential moves due |
| // to splitting). |
| DCHECK_EQ(instruction, actual_user); |
| position = actual_user->GetLifetimePosition(); |
| } else if (!locations->InAt(input_index).IsValid()) { |
| return; |
| } |
| } |
| |
| if (!is_environment && instruction->IsInLoop()) { |
| AddBackEdgeUses(*instruction->GetBlock()); |
| } |
| |
| if ((!uses_.empty()) && |
| (uses_.front().GetUser() == actual_user) && |
| (uses_.front().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(!is_environment); |
| DCHECK(uses_.front().GetPosition() + 1 == position); |
| UsePositionList::iterator next_pos = uses_.begin(); |
| UsePositionList::iterator insert_pos; |
| do { |
| insert_pos = next_pos; |
| ++next_pos; |
| } while (next_pos != uses_.end() && next_pos->GetPosition() < position); |
| UsePosition* new_use = new (allocator_) UsePosition(instruction, input_index, position); |
| uses_.insert_after(insert_pos, *new_use); |
| if (first_range_->GetEnd() == uses_.front().GetPosition()) { |
| first_range_->end_ = position; |
| } |
| return; |
| } |
| |
| if (is_environment) { |
| DCHECK(env_uses_.empty() || position <= env_uses_.front().GetPosition()); |
| EnvUsePosition* new_env_use = |
| new (allocator_) EnvUsePosition(environment, input_index, position); |
| env_uses_.push_front(*new_env_use); |
| } else { |
| DCHECK(uses_.empty() || position <= uses_.front().GetPosition()); |
| UsePosition* new_use = new (allocator_) UsePosition(instruction, input_index, position); |
| uses_.push_front(*new_use); |
| } |
| |
| if (is_environment && !keep_alive) { |
| // If this environment use does not keep the instruction live, it does not |
| // affect the live range of that instruction. |
| return; |
| } |
| |
| size_t start_block_position = instruction->GetBlock()->GetLifetimeStart(); |
| if (first_range_ == nullptr) { |
| // First time we see a use of that interval. |
| first_range_ = last_range_ = range_search_start_ = |
| new (allocator_) LiveRange(start_block_position, position, nullptr); |
| } else if (first_range_->GetStart() == start_block_position) { |
| // There is a use later in the same block or in a following block. |
| // Note that in such a case, `AddRange` for the whole blocks has been called |
| // before arriving in this method, and this is the reason the start of |
| // `first_range_` is before the given `position`. |
| DCHECK_LE(position, first_range_->GetEnd()); |
| } else { |
| DCHECK(first_range_->GetStart() > position); |
| // There is a hole in the interval. Create a new range. |
| // Note that the start of `first_range_` can be equal to `end`: two blocks |
| // having adjacent lifetime positions are not necessarily |
| // predecessor/successor. When two blocks are predecessor/successor, the |
| // liveness algorithm has called `AddRange` before arriving in this method, |
| // and the check line 205 would succeed. |
| first_range_ = range_search_start_ = |
| new (allocator_) LiveRange(start_block_position, position, first_range_); |
| } |
| } |
| |
| void AddPhiUse(HInstruction* instruction, size_t input_index, HBasicBlock* block) { |
| DCHECK(instruction->IsPhi()); |
| if (block->IsInLoop()) { |
| AddBackEdgeUses(*block); |
| } |
| UsePosition* new_use = |
| new (allocator_) UsePosition(instruction, input_index, block->GetLifetimeEnd()); |
| uses_.push_front(*new_use); |
| } |
| |
| ALWAYS_INLINE void AddRange(size_t start, size_t end) { |
| if (first_range_ == nullptr) { |
| first_range_ = last_range_ = range_search_start_ = |
| new (allocator_) LiveRange(start, end, first_range_); |
| } else if (first_range_->GetStart() == end) { |
| // There is a use in the following block. |
| first_range_->start_ = start; |
| } else if (first_range_->GetStart() == start && first_range_->GetEnd() == end) { |
| DCHECK(is_fixed_); |
| } else { |
| DCHECK_GT(first_range_->GetStart(), end); |
| // There is a hole in the interval. Create a new range. |
| first_range_ = range_search_start_ = new (allocator_) LiveRange(start, end, first_range_); |
| } |
| } |
| |
| void AddLoopRange(size_t start, size_t end) { |
| DCHECK(first_range_ != nullptr); |
| DCHECK_LE(start, first_range_->GetStart()); |
| // Find the range that covers the positions after the loop. |
| LiveRange* after_loop = first_range_; |
| LiveRange* last_in_loop = nullptr; |
| while (after_loop != nullptr && after_loop->GetEnd() < end) { |
| DCHECK_LE(start, after_loop->GetStart()); |
| last_in_loop = after_loop; |
| after_loop = after_loop->GetNext(); |
| } |
| if (after_loop == nullptr) { |
| // Uses are only in the loop. |
| first_range_ = last_range_ = range_search_start_ = |
| new (allocator_) LiveRange(start, end, nullptr); |
| } else if (after_loop->GetStart() <= end) { |
| first_range_ = range_search_start_ = after_loop; |
| // There are uses after the loop. |
| first_range_->start_ = start; |
| } else { |
| // The use after the loop is after a lifetime hole. |
| DCHECK(last_in_loop != nullptr); |
| first_range_ = range_search_start_ = last_in_loop; |
| first_range_->start_ = start; |
| first_range_->end_ = end; |
| } |
| } |
| |
| bool HasSpillSlot() const { return spill_slot_ != kNoSpillSlot; } |
| void SetSpillSlot(int slot) { |
| DCHECK(!is_fixed_); |
| DCHECK(!is_temp_); |
| spill_slot_ = slot; |
| } |
| int GetSpillSlot() const { return spill_slot_; } |
| |
| void SetFrom(size_t from) { |
| if (first_range_ != nullptr) { |
| first_range_->start_ = from; |
| } else { |
| // Instruction without uses. |
| DCHECK(uses_.empty()); |
| DCHECK(from == defined_by_->GetLifetimePosition()); |
| first_range_ = last_range_ = range_search_start_ = |
| new (allocator_) LiveRange(from, from + 2, nullptr); |
| } |
| } |
| |
| LiveInterval* GetParent() const { return parent_; } |
| |
| // Returns whether this interval is the parent interval, that is, the interval |
| // that starts where the HInstruction is defined. |
| bool IsParent() const { return parent_ == this; } |
| |
| LiveRange* GetFirstRange() const { return first_range_; } |
| LiveRange* GetLastRange() const { return last_range_; } |
| |
| int GetRegister() const { return register_; } |
| void SetRegister(int reg) { register_ = reg; } |
| void ClearRegister() { register_ = kNoRegister; } |
| bool HasRegister() const { return register_ != kNoRegister; } |
| |
| bool IsDeadAt(size_t position) const { |
| return GetEnd() <= position; |
| } |
| |
| bool IsDefinedAt(size_t position) const { |
| return GetStart() <= position && !IsDeadAt(position); |
| } |
| |
| // Returns true if the interval contains a LiveRange covering `position`. |
| // The range at or immediately after the current position of linear scan |
| // is cached for better performance. If `position` can be smaller than |
| // that, CoversSlow should be used instead. |
| bool Covers(size_t position) { |
| LiveRange* candidate = FindRangeAtOrAfter(position, range_search_start_); |
| range_search_start_ = candidate; |
| return (candidate != nullptr && candidate->GetStart() <= position); |
| } |
| |
| // Same as Covers but always tests all ranges. |
| bool CoversSlow(size_t position) const { |
| LiveRange* candidate = FindRangeAtOrAfter(position, first_range_); |
| return candidate != nullptr && candidate->GetStart() <= position; |
| } |
| |
| // Returns the first intersection of this interval with `current`, which |
| // must be the interval currently being allocated by linear scan. |
| size_t FirstIntersectionWith(LiveInterval* current) const { |
| // Find the first range after the start of `current`. We use the search |
| // cache to improve performance. |
| DCHECK(GetStart() <= current->GetStart() || IsFixed()); |
| LiveRange* other_range = current->first_range_; |
| LiveRange* my_range = FindRangeAtOrAfter(other_range->GetStart(), range_search_start_); |
| if (my_range == nullptr) { |
| return kNoLifetime; |
| } |
| |
| // Advance both intervals and find the first matching range start in |
| // this interval. |
| do { |
| if (my_range->IsBefore(*other_range)) { |
| my_range = my_range->GetNext(); |
| if (my_range == nullptr) { |
| return kNoLifetime; |
| } |
| } else if (other_range->IsBefore(*my_range)) { |
| other_range = other_range->GetNext(); |
| if (other_range == nullptr) { |
| return kNoLifetime; |
| } |
| } else { |
| DCHECK(my_range->IntersectsWith(*other_range)); |
| return std::max(my_range->GetStart(), other_range->GetStart()); |
| } |
| } while (true); |
| } |
| |
| size_t GetStart() const { |
| return first_range_->GetStart(); |
| } |
| |
| size_t GetEnd() const { |
| return last_range_->GetEnd(); |
| } |
| |
| size_t GetLength() const { |
| return GetEnd() - GetStart(); |
| } |
| |
| size_t FirstRegisterUseAfter(size_t position) const { |
| if (is_temp_) { |
| return position == GetStart() ? position : kNoLifetime; |
| } |
| |
| if (IsDefiningPosition(position) && DefinitionRequiresRegister()) { |
| return position; |
| } |
| |
| size_t end = GetEnd(); |
| for (const UsePosition& use : GetUses()) { |
| size_t use_position = use.GetPosition(); |
| if (use_position > end) { |
| break; |
| } |
| if (use_position > position) { |
| if (use.RequiresRegister()) { |
| return use_position; |
| } |
| } |
| } |
| return kNoLifetime; |
| } |
| |
| // Returns the location of the first register use for this live interval, |
| // including a register definition if applicable. |
| size_t FirstRegisterUse() const { |
| return FirstRegisterUseAfter(GetStart()); |
| } |
| |
| // Whether the interval requires a register rather than a stack location. |
| // If needed for performance, this could be cached. |
| bool RequiresRegister() const { |
| return !HasRegister() && FirstRegisterUse() != kNoLifetime; |
| } |
| |
| size_t FirstUseAfter(size_t position) const { |
| if (is_temp_) { |
| return position == GetStart() ? position : kNoLifetime; |
| } |
| |
| if (IsDefiningPosition(position)) { |
| DCHECK(defined_by_->GetLocations()->Out().IsValid()); |
| return position; |
| } |
| |
| size_t end = GetEnd(); |
| for (const UsePosition& use : GetUses()) { |
| size_t use_position = use.GetPosition(); |
| if (use_position > end) { |
| break; |
| } |
| if (use_position > position) { |
| return use_position; |
| } |
| } |
| return kNoLifetime; |
| } |
| |
| const UsePositionList& GetUses() const { |
| return parent_->uses_; |
| } |
| |
| const EnvUsePositionList& GetEnvironmentUses() const { |
| return parent_->env_uses_; |
| } |
| |
| Primitive::Type GetType() const { |
| return type_; |
| } |
| |
| HInstruction* GetDefinedBy() const { |
| return defined_by_; |
| } |
| |
| bool HasWillCallSafepoint() const { |
| for (SafepointPosition* safepoint = first_safepoint_; |
| safepoint != nullptr; |
| safepoint = safepoint->GetNext()) { |
| if (safepoint->GetLocations()->WillCall()) return true; |
| } |
| return false; |
| } |
| |
| SafepointPosition* FindSafepointJustBefore(size_t position) const { |
| for (SafepointPosition* safepoint = first_safepoint_, *previous = nullptr; |
| safepoint != nullptr; |
| previous = safepoint, safepoint = safepoint->GetNext()) { |
| if (safepoint->GetPosition() >= position) return previous; |
| } |
| return last_safepoint_; |
| } |
| |
| /** |
| * Split this interval at `position`. This interval is changed to: |
| * [start ... position). |
| * |
| * The new interval covers: |
| * [position ... end) |
| */ |
| LiveInterval* SplitAt(size_t position) { |
| DCHECK(!is_temp_); |
| DCHECK(!is_fixed_); |
| DCHECK_GT(position, GetStart()); |
| |
| if (GetEnd() <= position) { |
| // This range dies before `position`, no need to split. |
| return nullptr; |
| } |
| |
| LiveInterval* new_interval = new (allocator_) LiveInterval(allocator_, type_); |
| SafepointPosition* new_last_safepoint = FindSafepointJustBefore(position); |
| if (new_last_safepoint == nullptr) { |
| new_interval->first_safepoint_ = first_safepoint_; |
| new_interval->last_safepoint_ = last_safepoint_; |
| first_safepoint_ = last_safepoint_ = nullptr; |
| } else if (last_safepoint_ != new_last_safepoint) { |
| new_interval->last_safepoint_ = last_safepoint_; |
| new_interval->first_safepoint_ = new_last_safepoint->GetNext(); |
| DCHECK(new_interval->first_safepoint_ != nullptr); |
| last_safepoint_ = new_last_safepoint; |
| last_safepoint_->SetNext(nullptr); |
| } |
| |
| new_interval->next_sibling_ = next_sibling_; |
| next_sibling_ = new_interval; |
| new_interval->parent_ = parent_; |
| |
| LiveRange* current = first_range_; |
| LiveRange* previous = nullptr; |
| // Iterate over the ranges, and either find a range that covers this position, or |
| // two ranges in between this position (that is, the position is in a lifetime hole). |
| do { |
| if (position >= current->GetEnd()) { |
| // Move to next range. |
| previous = current; |
| current = current->next_; |
| } else if (position <= current->GetStart()) { |
| // If the previous range did not cover this position, we know position is in |
| // a lifetime hole. We can just break the first_range_ and last_range_ links |
| // and return the new interval. |
| DCHECK(previous != nullptr); |
| DCHECK(current != first_range_); |
| new_interval->last_range_ = last_range_; |
| last_range_ = previous; |
| previous->next_ = nullptr; |
| new_interval->first_range_ = current; |
| if (range_search_start_ != nullptr && range_search_start_->GetEnd() >= current->GetEnd()) { |
| // Search start point is inside `new_interval`. Change it to null |
| // (i.e. the end of the interval) in the original interval. |
| range_search_start_ = nullptr; |
| } |
| new_interval->range_search_start_ = new_interval->first_range_; |
| return new_interval; |
| } else { |
| // This range covers position. We create a new last_range_ for this interval |
| // that covers last_range_->Start() and position. We also shorten the current |
| // range and make it the first range of the new interval. |
| DCHECK(position < current->GetEnd() && position > current->GetStart()); |
| new_interval->last_range_ = last_range_; |
| last_range_ = new (allocator_) LiveRange(current->start_, position, nullptr); |
| if (previous != nullptr) { |
| previous->next_ = last_range_; |
| } else { |
| first_range_ = last_range_; |
| } |
| new_interval->first_range_ = current; |
| current->start_ = position; |
| if (range_search_start_ != nullptr && range_search_start_->GetEnd() >= current->GetEnd()) { |
| // Search start point is inside `new_interval`. Change it to `last_range` |
| // in the original interval. This is conservative but always correct. |
| range_search_start_ = last_range_; |
| } |
| new_interval->range_search_start_ = new_interval->first_range_; |
| return new_interval; |
| } |
| } while (current != nullptr); |
| |
| LOG(FATAL) << "Unreachable"; |
| return nullptr; |
| } |
| |
| bool StartsBeforeOrAt(LiveInterval* other) const { |
| return GetStart() <= other->GetStart(); |
| } |
| |
| bool StartsAfter(LiveInterval* other) const { |
| return GetStart() > other->GetStart(); |
| } |
| |
| void Dump(std::ostream& stream) const { |
| stream << "ranges: { "; |
| LiveRange* current = first_range_; |
| while (current != nullptr) { |
| current->Dump(stream); |
| stream << " "; |
| current = current->GetNext(); |
| } |
| stream << "}, uses: { "; |
| for (const UsePosition& use : GetUses()) { |
| use.Dump(stream); |
| stream << " "; |
| } |
| stream << "}, { "; |
| for (const EnvUsePosition& env_use : GetEnvironmentUses()) { |
| env_use.Dump(stream); |
| stream << " "; |
| } |
| stream << "}"; |
| stream << " is_fixed: " << is_fixed_ << ", is_split: " << IsSplit(); |
| stream << " is_low: " << IsLowInterval(); |
| stream << " is_high: " << IsHighInterval(); |
| } |
| |
| // Same as Dump, but adds context such as the instruction defining this interval, and |
| // the register currently assigned to this interval. |
| void DumpWithContext(std::ostream& stream, const CodeGenerator& codegen) const; |
| |
| LiveInterval* GetNextSibling() const { return next_sibling_; } |
| LiveInterval* GetLastSibling() { |
| LiveInterval* result = this; |
| while (result->next_sibling_ != nullptr) { |
| result = result->next_sibling_; |
| } |
| return result; |
| } |
| |
| // Returns the first register hint that is at least free before |
| // the value contained in `free_until`. If none is found, returns |
| // `kNoRegister`. |
| int FindFirstRegisterHint(size_t* free_until, const SsaLivenessAnalysis& liveness) const; |
| |
| // If there is enough at the definition site to find a register (for example |
| // it uses the same input as the first input), returns the register as a hint. |
| // Returns kNoRegister otherwise. |
| int FindHintAtDefinition() const; |
| |
| // Returns the number of required spilling slots (measured as a multiple of the |
| // Dex virtual register size `kVRegSize`). |
| size_t NumberOfSpillSlotsNeeded() const; |
| |
| bool IsFloatingPoint() const { |
| return type_ == Primitive::kPrimFloat || type_ == Primitive::kPrimDouble; |
| } |
| |
| // Converts the location of the interval to a `Location` object. |
| Location ToLocation() const; |
| |
| // Returns the location of the interval following its siblings at `position`. |
| Location GetLocationAt(size_t position); |
| |
| // Finds the sibling that is defined at `position`. |
| LiveInterval* GetSiblingAt(size_t position); |
| |
| // Returns whether `other` and `this` share the same kind of register. |
| bool SameRegisterKind(Location other) const; |
| bool SameRegisterKind(const LiveInterval& other) const { |
| return IsFloatingPoint() == other.IsFloatingPoint(); |
| } |
| |
| bool HasHighInterval() const { |
| return IsLowInterval(); |
| } |
| |
| bool HasLowInterval() const { |
| return IsHighInterval(); |
| } |
| |
| LiveInterval* GetLowInterval() const { |
| DCHECK(HasLowInterval()); |
| return high_or_low_interval_; |
| } |
| |
| LiveInterval* GetHighInterval() const { |
| DCHECK(HasHighInterval()); |
| return high_or_low_interval_; |
| } |
| |
| bool IsHighInterval() const { |
| return GetParent()->is_high_interval_; |
| } |
| |
| bool IsLowInterval() const { |
| return !IsHighInterval() && (GetParent()->high_or_low_interval_ != nullptr); |
| } |
| |
| void SetLowInterval(LiveInterval* low) { |
| DCHECK(IsHighInterval()); |
| high_or_low_interval_ = low; |
| } |
| |
| void SetHighInterval(LiveInterval* high) { |
| DCHECK(IsLowInterval()); |
| high_or_low_interval_ = high; |
| } |
| |
| void AddHighInterval(bool is_temp = false) { |
| DCHECK(IsParent()); |
| DCHECK(!HasHighInterval()); |
| DCHECK(!HasLowInterval()); |
| high_or_low_interval_ = new (allocator_) LiveInterval( |
| allocator_, type_, defined_by_, false, kNoRegister, is_temp, true); |
| high_or_low_interval_->high_or_low_interval_ = this; |
| if (first_range_ != nullptr) { |
| high_or_low_interval_->first_range_ = first_range_->Dup(allocator_); |
| high_or_low_interval_->last_range_ = high_or_low_interval_->first_range_->GetLastRange(); |
| high_or_low_interval_->range_search_start_ = high_or_low_interval_->first_range_; |
| } |
| auto pos = high_or_low_interval_->uses_.before_begin(); |
| for (const UsePosition& use : uses_) { |
| UsePosition* new_use = use.Clone(allocator_); |
| pos = high_or_low_interval_->uses_.insert_after(pos, *new_use); |
| } |
| |
| auto env_pos = high_or_low_interval_->env_uses_.before_begin(); |
| for (const EnvUsePosition& env_use : env_uses_) { |
| EnvUsePosition* new_env_use = env_use.Clone(allocator_); |
| env_pos = high_or_low_interval_->env_uses_.insert_after(env_pos, *new_env_use); |
| } |
| } |
| |
| // Returns whether an interval, when it is non-split, is using |
| // the same register of one of its input. |
| bool IsUsingInputRegister() const { |
| CHECK(kIsDebugBuild) << "Function should be used only for DCHECKs"; |
| if (defined_by_ != nullptr && !IsSplit()) { |
| for (const HInstruction* input : defined_by_->GetInputs()) { |
| LiveInterval* interval = input->GetLiveInterval(); |
| |
| // Find the interval that covers `defined_by`_. Calls to this function |
| // are made outside the linear scan, hence we need to use CoversSlow. |
| while (interval != nullptr && !interval->CoversSlow(defined_by_->GetLifetimePosition())) { |
| interval = interval->GetNextSibling(); |
| } |
| |
| // Check if both intervals have the same register of the same kind. |
| if (interval != nullptr |
| && interval->SameRegisterKind(*this) |
| && interval->GetRegister() == GetRegister()) { |
| return true; |
| } |
| } |
| } |
| return false; |
| } |
| |
| // Returns whether an interval, when it is non-split, can safely use |
| // the same register of one of its input. Note that this method requires |
| // IsUsingInputRegister() to be true. |
| bool CanUseInputRegister() const { |
| CHECK(kIsDebugBuild) << "Function should be used only for DCHECKs"; |
| DCHECK(IsUsingInputRegister()); |
| if (defined_by_ != nullptr && !IsSplit()) { |
| LocationSummary* locations = defined_by_->GetLocations(); |
| if (locations->OutputCanOverlapWithInputs()) { |
| return false; |
| } |
| for (const HInstruction* input : defined_by_->GetInputs()) { |
| LiveInterval* interval = input->GetLiveInterval(); |
| |
| // Find the interval that covers `defined_by`_. Calls to this function |
| // are made outside the linear scan, hence we need to use CoversSlow. |
| while (interval != nullptr && !interval->CoversSlow(defined_by_->GetLifetimePosition())) { |
| interval = interval->GetNextSibling(); |
| } |
| |
| if (interval != nullptr |
| && interval->SameRegisterKind(*this) |
| && interval->GetRegister() == GetRegister()) { |
| // We found the input that has the same register. Check if it is live after |
| // `defined_by`_. |
| return !interval->CoversSlow(defined_by_->GetLifetimePosition() + 1); |
| } |
| } |
| } |
| LOG(FATAL) << "Unreachable"; |
| UNREACHABLE(); |
| } |
| |
| void AddSafepoint(HInstruction* instruction) { |
| SafepointPosition* safepoint = new (allocator_) SafepointPosition(instruction); |
| if (first_safepoint_ == nullptr) { |
| first_safepoint_ = last_safepoint_ = safepoint; |
| } else { |
| DCHECK_LT(last_safepoint_->GetPosition(), safepoint->GetPosition()); |
| last_safepoint_->SetNext(safepoint); |
| last_safepoint_ = safepoint; |
| } |
| } |
| |
| SafepointPosition* GetFirstSafepoint() const { |
| return first_safepoint_; |
| } |
| |
| // Resets the starting point for range-searching queries to the first range. |
| // Intervals must be reset prior to starting a new linear scan over them. |
| void ResetSearchCache() { |
| range_search_start_ = first_range_; |
| } |
| |
| bool DefinitionRequiresRegister() const { |
| DCHECK(IsParent()); |
| LocationSummary* locations = defined_by_->GetLocations(); |
| Location location = locations->Out(); |
| // This interval is the first interval of the instruction. If the output |
| // of the instruction requires a register, we return the position of that instruction |
| // as the first register use. |
| if (location.IsUnallocated()) { |
| if ((location.GetPolicy() == Location::kRequiresRegister) |
| || (location.GetPolicy() == Location::kSameAsFirstInput |
| && (locations->InAt(0).IsRegister() |
| || locations->InAt(0).IsRegisterPair() |
| || locations->InAt(0).GetPolicy() == Location::kRequiresRegister))) { |
| return true; |
| } else if ((location.GetPolicy() == Location::kRequiresFpuRegister) |
| || (location.GetPolicy() == Location::kSameAsFirstInput |
| && (locations->InAt(0).IsFpuRegister() |
| || locations->InAt(0).IsFpuRegisterPair() |
| || locations->InAt(0).GetPolicy() == Location::kRequiresFpuRegister))) { |
| return true; |
| } |
| } else if (location.IsRegister() || location.IsRegisterPair()) { |
| return true; |
| } |
| return false; |
| } |
| |
| private: |
| LiveInterval(ArenaAllocator* allocator, |
| Primitive::Type type, |
| HInstruction* defined_by = nullptr, |
| bool is_fixed = false, |
| int reg = kNoRegister, |
| bool is_temp = false, |
| bool is_high_interval = false) |
| : allocator_(allocator), |
| first_range_(nullptr), |
| last_range_(nullptr), |
| range_search_start_(nullptr), |
| first_safepoint_(nullptr), |
| last_safepoint_(nullptr), |
| uses_(), |
| env_uses_(), |
| type_(type), |
| next_sibling_(nullptr), |
| parent_(this), |
| register_(reg), |
| spill_slot_(kNoSpillSlot), |
| is_fixed_(is_fixed), |
| is_temp_(is_temp), |
| is_high_interval_(is_high_interval), |
| high_or_low_interval_(nullptr), |
| defined_by_(defined_by) {} |
| |
| // Searches for a LiveRange that either covers the given position or is the |
| // first next LiveRange. Returns null if no such LiveRange exists. Ranges |
| // known to end before `position` can be skipped with `search_start`. |
| LiveRange* FindRangeAtOrAfter(size_t position, LiveRange* search_start) const { |
| if (kIsDebugBuild) { |
| if (search_start != first_range_) { |
| // If we are not searching the entire list of ranges, make sure we do |
| // not skip the range we are searching for. |
| if (search_start == nullptr) { |
| DCHECK(IsDeadAt(position)); |
| } else if (search_start->GetStart() > position) { |
| DCHECK_EQ(search_start, FindRangeAtOrAfter(position, first_range_)); |
| } |
| } |
| } |
| |
| LiveRange* range; |
| for (range = search_start; |
| range != nullptr && range->GetEnd() <= position; |
| range = range->GetNext()) { |
| continue; |
| } |
| return range; |
| } |
| |
| bool IsDefiningPosition(size_t position) const { |
| return IsParent() && (position == GetStart()); |
| } |
| |
| bool HasSynthesizeUseAt(size_t position) const { |
| for (const UsePosition& use : GetUses()) { |
| size_t use_position = use.GetPosition(); |
| if ((use_position == position) && use.IsSynthesized()) { |
| return true; |
| } |
| if (use_position > position) break; |
| } |
| return false; |
| } |
| |
| void AddBackEdgeUses(const HBasicBlock& block_at_use) { |
| DCHECK(block_at_use.IsInLoop()); |
| if (block_at_use.GetGraph()->HasIrreducibleLoops()) { |
| // Linear order may not be well formed when irreducible loops are present, |
| // i.e. loop blocks may not be adjacent and a back edge may not be last, |
| // which violates assumptions made in this method. |
| return; |
| } |
| |
| // Add synthesized uses at the back edge of loops to help the register allocator. |
| // Note that this method is called in decreasing liveness order, to faciliate adding |
| // uses at the head of the `uses_` list. Because below |
| // we iterate from inner-most to outer-most, which is in increasing liveness order, |
| // we need to add subsequent entries after the last inserted entry. |
| const UsePositionList::iterator old_begin = uses_.begin(); |
| UsePositionList::iterator insert_pos = uses_.before_begin(); |
| for (HLoopInformationOutwardIterator it(block_at_use); |
| !it.Done(); |
| it.Advance()) { |
| HLoopInformation* current = it.Current(); |
| if (GetDefinedBy()->GetLifetimePosition() >= current->GetHeader()->GetLifetimeStart()) { |
| // This interval is defined in the loop. We can stop going outward. |
| break; |
| } |
| |
| // We're only adding a synthesized use at the last back edge. Adding synthesized uses on |
| // all back edges is not necessary: anything used in the loop will have its use at the |
| // last back edge. If we want branches in a loop to have better register allocation than |
| // another branch, then it is the linear order we should change. |
| size_t back_edge_use_position = current->GetLifetimeEnd(); |
| if ((old_begin != uses_.end()) && (old_begin->GetPosition() <= back_edge_use_position)) { |
| // There was a use already seen in this loop. Therefore the previous call to `AddUse` |
| // already inserted the backedge use. We can stop going outward. |
| DCHECK(HasSynthesizeUseAt(back_edge_use_position)); |
| break; |
| } |
| |
| DCHECK(insert_pos != uses_.before_begin() |
| ? back_edge_use_position > insert_pos->GetPosition() |
| : current == block_at_use.GetLoopInformation()) |
| << std::distance(uses_.before_begin(), insert_pos); |
| |
| UsePosition* new_use = new (allocator_) UsePosition(back_edge_use_position); |
| insert_pos = uses_.insert_after(insert_pos, *new_use); |
| } |
| } |
| |
| ArenaAllocator* const allocator_; |
| |
| // Ranges of this interval. We need a quick access to the last range to test |
| // for liveness (see `IsDeadAt`). |
| LiveRange* first_range_; |
| LiveRange* last_range_; |
| |
| // The first range at or after the current position of a linear scan. It is |
| // used to optimize range-searching queries. |
| LiveRange* range_search_start_; |
| |
| // Safepoints where this interval is live. |
| SafepointPosition* first_safepoint_; |
| SafepointPosition* last_safepoint_; |
| |
| // Uses of this interval. Only the parent interval keeps these lists. |
| UsePositionList uses_; |
| EnvUsePositionList env_uses_; |
| |
| // The instruction type this interval corresponds to. |
| const Primitive::Type type_; |
| |
| // Live interval that is the result of a split. |
| LiveInterval* next_sibling_; |
| |
| // The first interval from which split intervals come from. |
| LiveInterval* parent_; |
| |
| // The register allocated to this interval. |
| int register_; |
| |
| // The spill slot allocated to this interval. |
| int spill_slot_; |
| |
| // Whether the interval is for a fixed register. |
| const bool is_fixed_; |
| |
| // Whether the interval is for a temporary. |
| const bool is_temp_; |
| |
| // Whether this interval is a synthesized interval for register pair. |
| const bool is_high_interval_; |
| |
| // If this interval needs a register pair, the high or low equivalent. |
| // `is_high_interval_` tells whether this holds the low or the high. |
| LiveInterval* high_or_low_interval_; |
| |
| // The instruction represented by this interval. |
| HInstruction* const defined_by_; |
| |
| static constexpr int kNoRegister = -1; |
| static constexpr int kNoSpillSlot = -1; |
| |
| ART_FRIEND_TEST(RegisterAllocatorTest, SpillInactive); |
| |
| DISALLOW_COPY_AND_ASSIGN(LiveInterval); |
| }; |
| |
| /** |
| * Analysis that computes the liveness of instructions: |
| * |
| * (a) Non-environment uses of an instruction always make |
| * the instruction live. |
| * (b) Environment uses of an instruction whose type is |
| * object (that is, non-primitive), make the instruction live. |
| * This is due to having to keep alive objects that have |
| * finalizers deleting native objects. |
| * (c) When the graph has the debuggable property, environment uses |
| * of an instruction that has a primitive type make the instruction live. |
| * If the graph does not have the debuggable property, the environment |
| * use has no effect, and may get a 'none' value after register allocation. |
| * |
| * (b) and (c) are implemented through SsaLivenessAnalysis::ShouldBeLiveForEnvironment. |
| */ |
| class SsaLivenessAnalysis : public ValueObject { |
| public: |
| SsaLivenessAnalysis(HGraph* graph, CodeGenerator* codegen) |
| : graph_(graph), |
| codegen_(codegen), |
| block_infos_(graph->GetBlocks().size(), |
| nullptr, |
| graph->GetArena()->Adapter(kArenaAllocSsaLiveness)), |
| instructions_from_ssa_index_(graph->GetArena()->Adapter(kArenaAllocSsaLiveness)), |
| instructions_from_lifetime_position_(graph->GetArena()->Adapter(kArenaAllocSsaLiveness)), |
| number_of_ssa_values_(0) { |
| } |
| |
| void Analyze(); |
| |
| BitVector* GetLiveInSet(const HBasicBlock& block) const { |
| return &block_infos_[block.GetBlockId()]->live_in_; |
| } |
| |
| BitVector* GetLiveOutSet(const HBasicBlock& block) const { |
| return &block_infos_[block.GetBlockId()]->live_out_; |
| } |
| |
| BitVector* GetKillSet(const HBasicBlock& block) const { |
| return &block_infos_[block.GetBlockId()]->kill_; |
| } |
| |
| HInstruction* GetInstructionFromSsaIndex(size_t index) const { |
| return instructions_from_ssa_index_[index]; |
| } |
| |
| HInstruction* GetInstructionFromPosition(size_t index) const { |
| return instructions_from_lifetime_position_[index]; |
| } |
| |
| HBasicBlock* GetBlockFromPosition(size_t index) const { |
| HInstruction* instruction = GetInstructionFromPosition(index); |
| if (instruction == nullptr) { |
| // If we are at a block boundary, get the block following. |
| instruction = GetInstructionFromPosition(index + 1); |
| } |
| return instruction->GetBlock(); |
| } |
| |
| bool IsAtBlockBoundary(size_t index) const { |
| return GetInstructionFromPosition(index) == nullptr; |
| } |
| |
| HInstruction* GetTempUser(LiveInterval* temp) const { |
| // A temporary shares the same lifetime start as the instruction that requires it. |
| DCHECK(temp->IsTemp()); |
| HInstruction* user = GetInstructionFromPosition(temp->GetStart() / 2); |
| DCHECK_EQ(user, temp->GetUses().front().GetUser()); |
| return user; |
| } |
| |
| size_t GetTempIndex(LiveInterval* temp) const { |
| // We use the input index to store the index of the temporary in the user's temporary list. |
| DCHECK(temp->IsTemp()); |
| return temp->GetUses().front().GetInputIndex(); |
| } |
| |
| size_t GetMaxLifetimePosition() const { |
| return instructions_from_lifetime_position_.size() * 2 - 1; |
| } |
| |
| size_t GetNumberOfSsaValues() const { |
| return number_of_ssa_values_; |
| } |
| |
| static constexpr const char* kLivenessPassName = "liveness"; |
| |
| private: |
| // Give an SSA number to each instruction that defines a value used by another instruction, |
| // and setup the lifetime information of each instruction and block. |
| void NumberInstructions(); |
| |
| // Compute live ranges of instructions, as well as live_in, live_out and kill sets. |
| void ComputeLiveness(); |
| |
| // Compute the live ranges of instructions, as well as the initial live_in, live_out and |
| // kill sets, that do not take into account backward branches. |
| void ComputeLiveRanges(); |
| |
| // After computing the initial sets, this method does a fixed point |
| // calculation over the live_in and live_out set to take into account |
| // backwards branches. |
| void ComputeLiveInAndLiveOutSets(); |
| |
| // Update the live_in set of the block and returns whether it has changed. |
| bool UpdateLiveIn(const HBasicBlock& block); |
| |
| // Update the live_out set of the block and returns whether it has changed. |
| bool UpdateLiveOut(const HBasicBlock& block); |
| |
| // Returns whether `instruction` in an HEnvironment held by `env_holder` |
| // should be kept live by the HEnvironment. |
| static bool ShouldBeLiveForEnvironment(HInstruction* env_holder, HInstruction* instruction) { |
| if (instruction == nullptr) return false; |
| // A value that's not live in compiled code may still be needed in interpreter, |
| // due to code motion, etc. |
| if (env_holder->IsDeoptimize()) return true; |
| // A value live at a throwing instruction in a try block may be copied by |
| // the exception handler to its location at the top of the catch block. |
| if (env_holder->CanThrowIntoCatchBlock()) return true; |
| if (instruction->GetBlock()->GetGraph()->IsDebuggable()) return true; |
| return instruction->GetType() == Primitive::kPrimNot; |
| } |
| |
| void CheckNoLiveInIrreducibleLoop(const HBasicBlock& block) const { |
| if (!block.IsLoopHeader() || !block.GetLoopInformation()->IsIrreducible()) { |
| return; |
| } |
| BitVector* live_in = GetLiveInSet(block); |
| // To satisfy our liveness algorithm, we need to ensure loop headers of |
| // irreducible loops do not have any live-in instructions, except constants |
| // and the current method, which can be trivially re-materialized. |
| for (uint32_t idx : live_in->Indexes()) { |
| HInstruction* instruction = GetInstructionFromSsaIndex(idx); |
| DCHECK(instruction->GetBlock()->IsEntryBlock()) << instruction->DebugName(); |
| DCHECK(!instruction->IsParameterValue()); |
| DCHECK(instruction->IsCurrentMethod() || instruction->IsConstant()) |
| << instruction->DebugName(); |
| } |
| } |
| |
| HGraph* const graph_; |
| CodeGenerator* const codegen_; |
| ArenaVector<BlockInfo*> block_infos_; |
| |
| // Temporary array used when computing live_in, live_out, and kill sets. |
| ArenaVector<HInstruction*> instructions_from_ssa_index_; |
| |
| // Temporary array used when inserting moves in the graph. |
| ArenaVector<HInstruction*> instructions_from_lifetime_position_; |
| size_t number_of_ssa_values_; |
| |
| ART_FRIEND_TEST(RegisterAllocatorTest, SpillInactive); |
| ART_FRIEND_TEST(RegisterAllocatorTest, FreeUntil); |
| |
| DISALLOW_COPY_AND_ASSIGN(SsaLivenessAnalysis); |
| }; |
| |
| } // namespace art |
| |
| #endif // ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_ |