Clean up and speed up `RegisterAllocationResolver`. Pull some invariants out of a loop in `Resolve()` and use another iterator type (without `PrefetchNext`). Clean up for-loops. Generalize `ZipCount()` to avoid an explicit call to the `MakeIterationRange()` and rename the `MakeIterationRange` parameter to make it clear it applies to any container-like argument that provides `begin()` and `end()`. Remove the `static` qualifier from some inline functions. Remove `SsaLivenessAnalysis::number_of_ssa_values_` as the size of `instructions_from_ssa_index_` provides the same information. This provides context to some of the for-loop rewrites in `RegisterAllocationResolver`. Test: m test-art-host-gtest Test: testrunner.py --host --optimizing Bug: 181943478 Flag: EXEMPT refactor Change-Id: I3e3ddae51a6f41d957c942d487f43a982ff1a6ed
diff --git a/compiler/optimizing/register_allocation_resolver.cc b/compiler/optimizing/register_allocation_resolver.cc index d1697cd..0d54774 100644 --- a/compiler/optimizing/register_allocation_resolver.cc +++ b/compiler/optimizing/register_allocation_resolver.cc
@@ -55,8 +55,7 @@ // Resolve outputs, including stack locations. // TODO: Use pointers of Location inside LiveInterval to avoid doing another iteration. - for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { - HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); + for (HInstruction* instruction : liveness_.GetInstructionsFromSsaIndexes()) { LiveInterval* current = instruction->GetLiveInterval(); LocationSummary* locations = instruction->GetLocations(); Location location = locations->Out(); @@ -143,8 +142,7 @@ } // Connect siblings and resolve inputs. - for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { - HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); + for (HInstruction* instruction : liveness_.GetInstructionsFromSsaIndexes()) { ConnectSiblings(instruction->GetLiveInterval()); } @@ -183,16 +181,14 @@ if (block->IsCatchBlock()) { // Catch phi values are set at runtime by the exception delivery mechanism. } else { - for (HInstructionIteratorPrefetchNext inst_it(block->GetPhis()); !inst_it.Done(); - inst_it.Advance()) { - HInstruction* phi = inst_it.Current(); - for (size_t i = 0, e = block->GetPredecessors().size(); i < e; ++i) { - HBasicBlock* predecessor = block->GetPredecessors()[i]; + for (HInstructionIterator inst_it(block->GetPhis()); !inst_it.Done(); inst_it.Advance()) { + HPhi* phi = inst_it.Current()->AsPhi(); + HInputsRef inputs = phi->GetInputs(); + Location destination = phi->GetLiveInterval()->ToLocation(); + for (auto [predecessor, input_index] : ZipCount(block->GetPredecessors())) { DCHECK_EQ(predecessor->GetNormalSuccessors().size(), 1u); - HInstruction* input = phi->InputAt(i); - Location source = input->GetLiveInterval()->GetLocationAt( + Location source = inputs[input_index]->GetLiveInterval()->GetLocationAt( predecessor->GetLifetimeEnd() - 1); - Location destination = phi->GetLiveInterval()->ToLocation(); InsertParallelMoveAtExitOf(predecessor, phi, source, destination); } } @@ -231,8 +227,7 @@ } void RegisterAllocationResolver::UpdateSafepointLiveRegisters() { - for (size_t i = 0, e = liveness_.GetNumberOfSsaValues(); i < e; ++i) { - HInstruction* instruction = liveness_.GetInstructionFromSsaIndex(i); + for (HInstruction* instruction : liveness_.GetInstructionsFromSsaIndexes()) { for (LiveInterval* current = instruction->GetLiveInterval(); current != nullptr; current = current->GetNextSibling()) {
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc index f129a1d..7fe37ee 100644 --- a/compiler/optimizing/ssa_liveness_analysis.cc +++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -34,7 +34,7 @@ } void SsaLivenessAnalysis::NumberInstructions() { - int ssa_index = 0; + size_t ssa_index = 0; size_t lifetime_position = 0; // Each instruction gets a lifetime position, and a block gets a lifetime // start and end position. Non-phi instructions have a distinct lifetime position than @@ -84,13 +84,14 @@ block->SetLifetimeEnd(lifetime_position); } - number_of_ssa_values_ = ssa_index; + DCHECK_EQ(GetNumberOfSsaValues(), ssa_index); } void SsaLivenessAnalysis::ComputeLiveness() { + size_t number_of_ssa_values = GetNumberOfSsaValues(); for (HBasicBlock* block : graph_->GetLinearOrder()) { block_infos_[block->GetBlockId()] = - new (allocator_) BlockInfo(allocator_, *block, number_of_ssa_values_); + new (allocator_) BlockInfo(allocator_, *block, number_of_ssa_values); } // Compute the live ranges, as well as the initial live_in, live_out, and kill sets.
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h index 4ec9149..de2c030 100644 --- a/compiler/optimizing/ssa_liveness_analysis.h +++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -1174,8 +1174,7 @@ nullptr, allocator_->Adapter(kArenaAllocSsaLiveness)), instructions_from_ssa_index_(allocator_->Adapter(kArenaAllocSsaLiveness)), - instructions_from_lifetime_position_(allocator_->Adapter(kArenaAllocSsaLiveness)), - number_of_ssa_values_(0) { + instructions_from_lifetime_position_(allocator_->Adapter(kArenaAllocSsaLiveness)) { } void Analyze(); @@ -1196,6 +1195,10 @@ return instructions_from_ssa_index_[index]; } + ArrayRef<HInstruction* const> GetInstructionsFromSsaIndexes() const { + return ArrayRef<HInstruction* const>(instructions_from_ssa_index_); + } + HInstruction* GetInstructionFromPosition(size_t index) const { return instructions_from_lifetime_position_[index]; } @@ -1235,7 +1238,7 @@ } size_t GetNumberOfSsaValues() const { - return number_of_ssa_values_; + return instructions_from_ssa_index_.size(); } static constexpr const char* kLivenessPassName = "liveness"; @@ -1314,8 +1317,6 @@ // Indexed by the lifetime position divided by `kLivenessPositionsPerInstruction`. ScopedArenaVector<HInstruction*> instructions_from_lifetime_position_; - size_t number_of_ssa_values_; - friend class RegisterAllocatorTest; DISALLOW_COPY_AND_ASSIGN(SsaLivenessAnalysis);
diff --git a/libartbase/base/iteration_range.h b/libartbase/base/iteration_range.h index 0685d59..91aecf3 100644 --- a/libartbase/base/iteration_range.h +++ b/libartbase/base/iteration_range.h
@@ -50,11 +50,10 @@ return IterationRange<Iter>(begin_it, end_it); } -template <typename List> -inline auto MakeIterationRange(List& list) -> IterationRange<decltype(list.begin())> { - static_assert(std::is_same_v<decltype(list.begin()), decltype(list.end())>, - "Different iterator types"); - return MakeIterationRange(list.begin(), list.end()); +template <typename Container> +inline auto MakeIterationRange(Container&& c) -> IterationRange<decltype(c.begin())> { + static_assert(std::is_same_v<decltype(c.begin()), decltype(c.end())>, "Different iterator types"); + return MakeIterationRange(c.begin(), c.end()); } template <typename Iter>
diff --git a/libartbase/base/stl_util.h b/libartbase/base/stl_util.h index a6ab16c..4af7b0a 100644 --- a/libartbase/base/stl_util.h +++ b/libartbase/base/stl_util.h
@@ -146,7 +146,7 @@ // Returns a copy of the passed vector that doesn't memory-own its entries. template <typename T> -static inline std::vector<T*> MakeNonOwningPointerVector(const std::vector<std::unique_ptr<T>>& src) { +inline std::vector<T*> MakeNonOwningPointerVector(const std::vector<std::unique_ptr<T>>& src) { std::vector<T*> result; result.reserve(src.size()); for (const std::unique_ptr<T>& t : src) { @@ -224,26 +224,26 @@ }; // Make an iteration range that returns a pair of the element and the index of the element. -template <typename Iter> -static inline IterationRange<ZipLeftIter<Iter, CountIter>> ZipCount(IterationRange<Iter> iter) { - return IterationRange(ZipLeftIter(iter.begin(), CountIter(0)), - ZipLeftIter(iter.end(), CountIter(-1))); +template <typename Container> +inline auto ZipCount(Container&& c) -> IterationRange<ZipLeftIter<decltype(c.begin()), CountIter>>{ + static_assert(std::is_same_v<decltype(c.begin()), decltype(c.end())>, "Different iterator types"); + return IterationRange(ZipLeftIter(c.begin(), CountIter(0)), ZipLeftIter(c.end(), CountIter(-1))); } // Make an iteration range that returns a pair of the outputs of two iterators. Stops when the first // (left) one is exhausted. The left iterator must be at least as long as the right one. template <typename IterLeft, typename IterRight> -static inline IterationRange<ZipLeftIter<IterLeft, IterRight>> ZipLeft( +inline IterationRange<ZipLeftIter<IterLeft, IterRight>> ZipLeft( IterationRange<IterLeft> iter_left, IterationRange<IterRight> iter_right) { return IterationRange(ZipLeftIter(iter_left.begin(), iter_right.begin()), ZipLeftIter(iter_left.end(), iter_right.end())); } -static inline IterationRange<CountIter> Range(size_t start, size_t end) { +inline IterationRange<CountIter> Range(size_t start, size_t end) { return IterationRange(CountIter(start), CountIter(end)); } -static inline IterationRange<CountIter> Range(size_t end) { +inline IterationRange<CountIter> Range(size_t end) { return Range(0, end); } @@ -294,7 +294,7 @@ }; template <typename BaseRange, typename FilterT> -static inline auto Filter(BaseRange&& range, FilterT cond) { +inline auto Filter(BaseRange&& range, FilterT cond) { auto end = range.end(); auto start = std::find_if(range.begin(), end, cond); return MakeIterationRange(FilterIterator(start, cond, std::make_optional(end)), @@ -314,7 +314,7 @@ using FilterNull = FilterIterator<InnerIter, NonNullFilter<typename InnerIter::value_type>>; template <typename InnerIter> -static inline IterationRange<FilterNull<InnerIter>> FilterOutNull(IterationRange<InnerIter> inner) { +inline IterationRange<FilterNull<InnerIter>> FilterOutNull(IterationRange<InnerIter> inner) { return Filter(inner, NonNullFilter<typename InnerIter::value_type>()); }