Use IntrusiveForwardList<> for Env-/UsePosition.
Test: m test-art-host-gtest
Test: testrunner.py --host
Change-Id: I2b720e2ed8f96303cf80e9daa6d5278bf0c3da2f
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index e9dffc1..a668157 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -19,7 +19,9 @@
#include <iostream>
+#include "base/iteration_range.h"
#include "nodes.h"
+#include "utils/intrusive_forward_list.h"
namespace art {
@@ -102,28 +104,23 @@
/**
* A use position represents a live interval use at a given position.
*/
-class UsePosition : public ArenaObject<kArenaAllocSsaLiveness> {
+class UsePosition : public ArenaObject<kArenaAllocSsaLiveness>,
+ public IntrusiveForwardListNode<UsePosition> {
public:
- UsePosition(HInstruction* user, size_t input_index, size_t position, UsePosition* next)
+ UsePosition(HInstruction* user, size_t input_index, size_t position)
: user_(user),
input_index_(input_index),
- position_(position),
- next_(next) {
- DCHECK(next_ == nullptr || next->GetPosition() >= GetPosition());
+ position_(position) {
}
explicit UsePosition(size_t position)
: user_(nullptr),
input_index_(kNoInput),
- position_(dchecked_integral_cast<uint32_t>(position)),
- next_(nullptr) {
+ position_(dchecked_integral_cast<uint32_t>(position)) {
}
size_t GetPosition() const { return position_; }
- UsePosition* GetNext() const { return next_; }
- void SetNext(UsePosition* next) { next_ = next; }
-
HInstruction* GetUser() const { return user_; }
bool IsSynthesized() const { return user_ == nullptr; }
@@ -138,10 +135,8 @@
return user_->GetBlock()->GetLoopInformation();
}
- UsePosition* Dup(ArenaAllocator* allocator) const {
- return new (allocator) UsePosition(
- user_, input_index_, position_,
- next_ == nullptr ? nullptr : next_->Dup(allocator));
+ UsePosition* Clone(ArenaAllocator* allocator) const {
+ return new (allocator) UsePosition(user_, input_index_, position_);
}
bool RequiresRegister() const {
@@ -156,33 +151,28 @@
HInstruction* const user_;
const size_t input_index_;
const size_t position_;
- UsePosition* next_;
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> {
+class EnvUsePosition : public ArenaObject<kArenaAllocSsaLiveness>,
+ public IntrusiveForwardListNode<EnvUsePosition> {
public:
EnvUsePosition(HEnvironment* environment,
size_t input_index,
- size_t position,
- EnvUsePosition* next)
+ size_t position)
: environment_(environment),
input_index_(input_index),
- position_(position),
- next_(next) {
+ position_(position) {
DCHECK(environment != nullptr);
- DCHECK(next_ == nullptr || next->GetPosition() >= GetPosition());
}
size_t GetPosition() const { return position_; }
- EnvUsePosition* GetNext() const { return next_; }
- void SetNext(EnvUsePosition* next) { next_ = next; }
-
HEnvironment* GetEnvironment() const { return environment_; }
size_t GetInputIndex() const { return input_index_; }
@@ -190,20 +180,47 @@
stream << position_;
}
- EnvUsePosition* Dup(ArenaAllocator* allocator) const {
- return new (allocator) EnvUsePosition(
- environment_, input_index_, position_,
- next_ == nullptr ? nullptr : next_->Dup(allocator));
+ 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_;
- EnvUsePosition* next_;
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:
@@ -265,11 +282,11 @@
void AddTempUse(HInstruction* instruction, size_t temp_index) {
DCHECK(IsTemp());
- DCHECK(first_use_ == nullptr) << "A temporary can only have one user";
- DCHECK(first_env_use_ == nullptr) << "A temporary cannot have environment user";
+ DCHECK(GetUses().empty()) << "A temporary can only have one user";
+ DCHECK(GetEnvironmentUses().empty()) << "A temporary cannot have environment user";
size_t position = instruction->GetLifetimePosition();
- first_use_ = new (allocator_) UsePosition(
- instruction, temp_index, position, first_use_);
+ UsePosition* new_use = new (allocator_) UsePosition(instruction, temp_index, position);
+ uses_.push_front(*new_use);
AddRange(position, position + 1);
}
@@ -306,32 +323,36 @@
AddBackEdgeUses(*instruction->GetBlock());
}
- if ((first_use_ != nullptr)
- && (first_use_->GetUser() == actual_user)
- && (first_use_->GetPosition() < position)) {
+ 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);
- UsePosition* cursor = first_use_;
- while ((cursor->GetNext() != nullptr) && (cursor->GetNext()->GetPosition() < position)) {
- cursor = cursor->GetNext();
- }
- DCHECK(first_use_->GetPosition() + 1 == position);
- UsePosition* new_use = new (allocator_) UsePosition(
- instruction, input_index, position, cursor->GetNext());
- cursor->SetNext(new_use);
- if (first_range_->GetEnd() == first_use_->GetPosition()) {
+ 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) {
- first_env_use_ = new (allocator_) EnvUsePosition(
- environment, input_index, position, first_env_use_);
+ 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 {
- first_use_ = new (allocator_) UsePosition(
- instruction, input_index, position, first_use_);
+ 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) {
@@ -369,8 +390,9 @@
if (block->IsInLoop()) {
AddBackEdgeUses(*block);
}
- first_use_ = new (allocator_) UsePosition(
- instruction, input_index, block->GetLifetimeEnd(), first_use_);
+ 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) {
@@ -430,7 +452,7 @@
first_range_->start_ = from;
} else {
// Instruction without uses.
- DCHECK(first_use_ == nullptr);
+ DCHECK(uses_.empty());
DCHECK(from == defined_by_->GetLifetimePosition());
first_range_ = last_range_ = range_search_start_ =
new (allocator_) LiveRange(from, from + 2, nullptr);
@@ -528,16 +550,17 @@
return position;
}
- UsePosition* use = first_use_;
size_t end = GetEnd();
- while (use != nullptr && use->GetPosition() <= end) {
- size_t use_position = use->GetPosition();
+ for (const UsePosition& use : GetUses()) {
+ size_t use_position = use.GetPosition();
+ if (use_position > end) {
+ break;
+ }
if (use_position > position) {
- if (use->RequiresRegister()) {
+ if (use.RequiresRegister()) {
return use_position;
}
}
- use = use->GetNext();
}
return kNoLifetime;
}
@@ -564,24 +587,25 @@
return position;
}
- UsePosition* use = first_use_;
size_t end = GetEnd();
- while (use != nullptr && use->GetPosition() <= end) {
- size_t use_position = use->GetPosition();
+ for (const UsePosition& use : GetUses()) {
+ size_t use_position = use.GetPosition();
+ if (use_position > end) {
+ break;
+ }
if (use_position > position) {
return use_position;
}
- use = use->GetNext();
}
return kNoLifetime;
}
- UsePosition* GetFirstUse() const {
- return first_use_;
+ const UsePositionList& GetUses() const {
+ return parent_->uses_;
}
- EnvUsePosition* GetFirstEnvironmentUse() const {
- return first_env_use_;
+ const EnvUsePositionList& GetEnvironmentUses() const {
+ return parent_->env_uses_;
}
Primitive::Type GetType() const {
@@ -645,8 +669,6 @@
next_sibling_ = new_interval;
new_interval->parent_ = parent_;
- new_interval->first_use_ = first_use_;
- new_interval->first_env_use_ = first_env_use_;
LiveRange* current = first_range_;
LiveRange* previous = nullptr;
// Iterate over the ranges, and either find a range that covers this position, or
@@ -718,20 +740,14 @@
current = current->GetNext();
}
stream << "}, uses: { ";
- const UsePosition* use = first_use_;
- if (use != nullptr) {
- do {
- use->Dump(stream);
- stream << " ";
- } while ((use = use->GetNext()) != nullptr);
+ for (const UsePosition& use : GetUses()) {
+ use.Dump(stream);
+ stream << " ";
}
stream << "}, { ";
- const EnvUsePosition* env_use = first_env_use_;
- if (env_use != nullptr) {
- do {
- env_use->Dump(stream);
- stream << " ";
- } while ((env_use = env_use->GetNext()) != nullptr);
+ for (const EnvUsePosition& env_use : GetEnvironmentUses()) {
+ env_use.Dump(stream);
+ stream << " ";
}
stream << "}";
stream << " is_fixed: " << is_fixed_ << ", is_split: " << IsSplit();
@@ -833,12 +849,16 @@
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_;
}
- if (first_use_ != nullptr) {
- high_or_low_interval_->first_use_ = first_use_->Dup(allocator_);
+ 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);
}
- if (first_env_use_ != nullptr) {
- high_or_low_interval_->first_env_use_ = first_env_use_->Dup(allocator_);
+ 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);
}
}
@@ -962,8 +982,8 @@
range_search_start_(nullptr),
first_safepoint_(nullptr),
last_safepoint_(nullptr),
- first_use_(nullptr),
- first_env_use_(nullptr),
+ uses_(),
+ env_uses_(),
type_(type),
next_sibling_(nullptr),
parent_(this),
@@ -1005,14 +1025,12 @@
}
bool HasSynthesizeUseAt(size_t position) const {
- UsePosition* use = first_use_;
- while (use != nullptr) {
- size_t use_position = use->GetPosition();
- if ((use_position == position) && use->IsSynthesized()) {
+ for (const UsePosition& use : GetUses()) {
+ size_t use_position = use.GetPosition();
+ if ((use_position == position) && use.IsSynthesized()) {
return true;
}
if (use_position > position) break;
- use = use->GetNext();
}
return false;
}
@@ -1028,11 +1046,11 @@
// 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 `first_use_` linked list. Because below
+ // 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 take extra care of how the `first_use_` linked list is being updated.
- UsePosition* first_in_new_list = nullptr;
- UsePosition* last_in_new_list = nullptr;
+ // 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()) {
@@ -1042,37 +1060,25 @@
break;
}
- // We're only adding a synthesized use at the last back edge. Adding syntehsized uses on
+ // 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 ((first_use_ != nullptr) && (first_use_->GetPosition() <= back_edge_use_position)) {
+ 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(last_in_new_list == nullptr ||
- back_edge_use_position > last_in_new_list->GetPosition());
+ 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);
-
- if (last_in_new_list != nullptr) {
- // Going outward. The latest created use needs to point to the new use.
- last_in_new_list->SetNext(new_use);
- } else {
- // This is the inner-most loop.
- DCHECK_EQ(current, block_at_use.GetLoopInformation());
- first_in_new_list = new_use;
- }
- last_in_new_list = new_use;
- }
- // Link the newly created linked list with `first_use_`.
- if (last_in_new_list != nullptr) {
- last_in_new_list->SetNext(first_use_);
- first_use_ = first_in_new_list;
+ insert_pos = uses_.insert_after(insert_pos, *new_use);
}
}
@@ -1091,9 +1097,9 @@
SafepointPosition* first_safepoint_;
SafepointPosition* last_safepoint_;
- // Uses of this interval. Note that this linked list is shared amongst siblings.
- UsePosition* first_use_;
- EnvUsePosition* first_env_use_;
+ // 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_;
@@ -1202,14 +1208,14 @@
// 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->GetFirstUse()->GetUser());
+ 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->GetFirstUse()->GetInputIndex();
+ return temp->GetUses().front().GetInputIndex();
}
size_t GetMaxLifetimePosition() const {