Use IntrusiveForwardList<> for Env-/UsePosition.
Test: m test-art-host-gtest
Test: testrunner.py --host
Change-Id: I2b720e2ed8f96303cf80e9daa6d5278bf0c3da2f
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 02816cf..7dcf244 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -34,6 +34,7 @@
#include "register_allocator_linear_scan.h"
#include "ssa_liveness_analysis.h"
#include "utils/assembler.h"
+#include "utils/intrusive_forward_list.h"
namespace art {
@@ -66,6 +67,13 @@
current->Dump(NewEntryStream());
}
}
+ // Construct StringList from a list of elements. The value type must provide method `Dump`.
+ template <typename Container>
+ explicit StringList(const Container& list, Format format = kArrayBrackets) : StringList(format) {
+ for (const typename Container::value_type& current : list) {
+ current.Dump(NewEntryStream());
+ }
+ }
std::ostream& NewEntryStream() {
if (is_empty_) {
@@ -584,8 +592,8 @@
LiveInterval* interval = instruction->GetLiveInterval();
StartAttributeStream("ranges")
<< StringList(interval->GetFirstRange(), StringList::kSetBrackets);
- StartAttributeStream("uses") << StringList(interval->GetFirstUse());
- StartAttributeStream("env_uses") << StringList(interval->GetFirstEnvironmentUse());
+ StartAttributeStream("uses") << StringList(interval->GetUses());
+ StartAttributeStream("env_uses") << StringList(interval->GetEnvironmentUses());
StartAttributeStream("is_fixed") << interval->IsFixed();
StartAttributeStream("is_split") << interval->IsSplit();
StartAttributeStream("is_low") << interval->IsLowInterval();
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 4d96fbe..85e37ca 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -1485,7 +1485,8 @@
H##type* As##type() { return this; }
template <typename T>
-class HUseListNode : public ArenaObject<kArenaAllocUseListNode> {
+class HUseListNode : public ArenaObject<kArenaAllocUseListNode>,
+ public IntrusiveForwardListNode<HUseListNode<T>> {
public:
// Get the instruction which has this use as one of the inputs.
T GetUser() const { return user_; }
@@ -1494,10 +1495,6 @@
// Set the position of the input record that this use corresponds to.
void SetIndex(size_t index) { index_ = index; }
- // Hook for the IntrusiveForwardList<>.
- // TODO: Hide this better.
- IntrusiveForwardListHook hook;
-
private:
HUseListNode(T user, size_t index)
: user_(user), index_(index) {}
diff --git a/compiler/optimizing/register_allocation_resolver.cc b/compiler/optimizing/register_allocation_resolver.cc
index c6a0b6a..ce3a496 100644
--- a/compiler/optimizing/register_allocation_resolver.cc
+++ b/compiler/optimizing/register_allocation_resolver.cc
@@ -308,8 +308,10 @@
}
InsertMoveAfter(interval->GetDefinedBy(), interval->ToLocation(), loc);
}
- UsePosition* use = current->GetFirstUse();
- EnvUsePosition* env_use = current->GetFirstEnvironmentUse();
+ UsePositionList::const_iterator use_it = current->GetUses().begin();
+ const UsePositionList::const_iterator use_end = current->GetUses().end();
+ EnvUsePositionList::const_iterator env_use_it = current->GetEnvironmentUses().begin();
+ const EnvUsePositionList::const_iterator env_use_end = current->GetEnvironmentUses().end();
// Walk over all siblings, updating locations of use positions, and
// connecting them when they are adjacent.
@@ -321,43 +323,47 @@
LiveRange* range = current->GetFirstRange();
while (range != nullptr) {
- while (use != nullptr && use->GetPosition() < range->GetStart()) {
- DCHECK(use->IsSynthesized());
- use = use->GetNext();
- }
- while (use != nullptr && use->GetPosition() <= range->GetEnd()) {
- DCHECK(current->CoversSlow(use->GetPosition()) || (use->GetPosition() == range->GetEnd()));
- if (!use->IsSynthesized()) {
- LocationSummary* locations = use->GetUser()->GetLocations();
- Location expected_location = locations->InAt(use->GetInputIndex());
+ // Process uses in the closed interval [range->GetStart(), range->GetEnd()].
+ // FindMatchingUseRange() expects a half-open interval, so pass `range->GetEnd() + 1u`.
+ size_t range_begin = range->GetStart();
+ size_t range_end = range->GetEnd() + 1u;
+ auto matching_use_range =
+ FindMatchingUseRange(use_it, use_end, range_begin, range_end);
+ DCHECK(std::all_of(use_it,
+ matching_use_range.begin(),
+ [](const UsePosition& pos) { return pos.IsSynthesized(); }));
+ for (const UsePosition& use : matching_use_range) {
+ DCHECK(current->CoversSlow(use.GetPosition()) || (use.GetPosition() == range->GetEnd()));
+ if (!use.IsSynthesized()) {
+ LocationSummary* locations = use.GetUser()->GetLocations();
+ Location expected_location = locations->InAt(use.GetInputIndex());
// The expected (actual) location may be invalid in case the input is unused. Currently
// this only happens for intrinsics.
if (expected_location.IsValid()) {
if (expected_location.IsUnallocated()) {
- locations->SetInAt(use->GetInputIndex(), source);
+ locations->SetInAt(use.GetInputIndex(), source);
} else if (!expected_location.IsConstant()) {
- AddInputMoveFor(interval->GetDefinedBy(), use->GetUser(), source, expected_location);
+ AddInputMoveFor(
+ interval->GetDefinedBy(), use.GetUser(), source, expected_location);
}
} else {
- DCHECK(use->GetUser()->IsInvoke());
- DCHECK(use->GetUser()->AsInvoke()->GetIntrinsic() != Intrinsics::kNone);
+ DCHECK(use.GetUser()->IsInvoke());
+ DCHECK(use.GetUser()->AsInvoke()->GetIntrinsic() != Intrinsics::kNone);
}
}
- use = use->GetNext();
}
+ use_it = matching_use_range.end();
// Walk over the environment uses, and update their locations.
- while (env_use != nullptr && env_use->GetPosition() < range->GetStart()) {
- env_use = env_use->GetNext();
+ auto matching_env_use_range =
+ FindMatchingUseRange(env_use_it, env_use_end, range_begin, range_end);
+ for (const EnvUsePosition& env_use : matching_env_use_range) {
+ DCHECK(current->CoversSlow(env_use.GetPosition())
+ || (env_use.GetPosition() == range->GetEnd()));
+ HEnvironment* environment = env_use.GetEnvironment();
+ environment->SetLocationAt(env_use.GetInputIndex(), source);
}
-
- while (env_use != nullptr && env_use->GetPosition() <= range->GetEnd()) {
- DCHECK(current->CoversSlow(env_use->GetPosition())
- || (env_use->GetPosition() == range->GetEnd()));
- HEnvironment* environment = env_use->GetEnvironment();
- environment->SetLocationAt(env_use->GetInputIndex(), source);
- env_use = env_use->GetNext();
- }
+ env_use_it = matching_env_use_range.end();
range = range->GetNext();
}
@@ -395,13 +401,8 @@
current = next_sibling;
} while (current != nullptr);
- if (kIsDebugBuild) {
- // Following uses can only be synthesized uses.
- while (use != nullptr) {
- DCHECK(use->IsSynthesized());
- use = use->GetNext();
- }
- }
+ // Following uses can only be synthesized uses.
+ DCHECK(std::all_of(use_it, use_end, [](const UsePosition& pos) { return pos.IsSynthesized(); }));
}
static bool IsMaterializableEntryBlockInstructionOfGraphWithIrreducibleLoop(
diff --git a/compiler/optimizing/register_allocator_graph_color.cc b/compiler/optimizing/register_allocator_graph_color.cc
index 300f4c6..090ba31 100644
--- a/compiler/optimizing/register_allocator_graph_color.cc
+++ b/compiler/optimizing/register_allocator_graph_color.cc
@@ -178,18 +178,17 @@
use_weight += CostForMoveAt(interval->GetStart() + 1, liveness);
}
- UsePosition* use = interval->GetFirstUse();
- while (use != nullptr && use->GetPosition() <= interval->GetStart()) {
- // Skip uses before the start of this live interval.
- use = use->GetNext();
- }
-
- while (use != nullptr && use->GetPosition() <= interval->GetEnd()) {
- if (use->GetUser() != nullptr && use->RequiresRegister()) {
+ // Process uses in the range (interval->GetStart(), interval->GetEnd()], i.e.
+ // [interval->GetStart() + 1, interval->GetEnd() + 1)
+ auto matching_use_range = FindMatchingUseRange(interval->GetUses().begin(),
+ interval->GetUses().end(),
+ interval->GetStart() + 1u,
+ interval->GetEnd() + 1u);
+ for (const UsePosition& use : matching_use_range) {
+ if (use.GetUser() != nullptr && use.RequiresRegister()) {
// Cost for spilling at a register use point.
- use_weight += CostForMoveAt(use->GetUser()->GetLifetimePosition() - 1, liveness);
+ use_weight += CostForMoveAt(use.GetUser()->GetLifetimePosition() - 1, liveness);
}
- use = use->GetNext();
}
// We divide by the length of the interval because we want to prioritize
@@ -989,16 +988,16 @@
interval = TrySplit(interval, interval->GetStart() + 1);
}
- UsePosition* use = interval->GetFirstUse();
- while (use != nullptr && use->GetPosition() < interval->GetStart()) {
- use = use->GetNext();
- }
-
+ // Process uses in the range [interval->GetStart(), interval->GetEnd()], i.e.
+ // [interval->GetStart(), interval->GetEnd() + 1)
+ auto matching_use_range = FindMatchingUseRange(interval->GetUses().begin(),
+ interval->GetUses().end(),
+ interval->GetStart(),
+ interval->GetEnd() + 1u);
// Split around register uses.
- size_t end = interval->GetEnd();
- while (use != nullptr && use->GetPosition() <= end) {
- if (use->RequiresRegister()) {
- size_t position = use->GetPosition();
+ for (const UsePosition& use : matching_use_range) {
+ if (use.RequiresRegister()) {
+ size_t position = use.GetPosition();
interval = TrySplit(interval, position - 1);
if (liveness_.GetInstructionFromPosition(position / 2)->IsControlFlow()) {
// If we are at the very end of a basic block, we cannot split right
@@ -1008,7 +1007,6 @@
interval = TrySplit(interval, position);
}
}
- use = use->GetNext();
}
}
@@ -1398,18 +1396,20 @@
}
// Try to prevent moves into fixed input locations.
- UsePosition* use = interval->GetFirstUse();
- for (; use != nullptr && use->GetPosition() <= interval->GetStart(); use = use->GetNext()) {
- // Skip past uses before the start of this interval.
- }
- for (; use != nullptr && use->GetPosition() <= interval->GetEnd(); use = use->GetNext()) {
- HInstruction* user = use->GetUser();
+ // Process uses in the range (interval->GetStart(), interval->GetEnd()], i.e.
+ // [interval->GetStart() + 1, interval->GetEnd() + 1)
+ auto matching_use_range = FindMatchingUseRange(interval->GetUses().begin(),
+ interval->GetUses().end(),
+ interval->GetStart() + 1u,
+ interval->GetEnd() + 1u);
+ for (const UsePosition& use : matching_use_range) {
+ HInstruction* user = use.GetUser();
if (user == nullptr) {
// User may be null for certain intervals, such as temp intervals.
continue;
}
LocationSummary* locations = user->GetLocations();
- Location input = locations->InAt(use->GetInputIndex());
+ Location input = locations->InAt(use.GetInputIndex());
if (input.IsRegister() || input.IsFpuRegister()) {
// TODO: Could try to handle pair interval too, but coalescing with fixed pair nodes
// is currently not supported.
diff --git a/compiler/optimizing/register_allocator_test.cc b/compiler/optimizing/register_allocator_test.cc
index 667afb1..24a2ab2 100644
--- a/compiler/optimizing/register_allocator_test.cc
+++ b/compiler/optimizing/register_allocator_test.cc
@@ -912,9 +912,9 @@
// Create an interval with lifetime holes.
static constexpr size_t ranges1[][2] = {{0, 2}, {4, 6}, {8, 10}};
LiveInterval* first = BuildInterval(ranges1, arraysize(ranges1), &allocator, -1, one);
- first->first_use_ = new(&allocator) UsePosition(user, false, 8, first->first_use_);
- first->first_use_ = new(&allocator) UsePosition(user, false, 7, first->first_use_);
- first->first_use_ = new(&allocator) UsePosition(user, false, 6, first->first_use_);
+ first->uses_.push_front(*new(&allocator) UsePosition(user, false, 8));
+ first->uses_.push_front(*new(&allocator) UsePosition(user, false, 7));
+ first->uses_.push_front(*new(&allocator) UsePosition(user, false, 6));
locations = new (&allocator) LocationSummary(first->GetDefinedBy(), LocationSummary::kNoCall);
locations->SetOut(Location::RequiresRegister());
@@ -934,9 +934,9 @@
// before lifetime position 6 yet.
static constexpr size_t ranges3[][2] = {{2, 4}, {8, 10}};
LiveInterval* third = BuildInterval(ranges3, arraysize(ranges3), &allocator, -1, three);
- third->first_use_ = new(&allocator) UsePosition(user, false, 8, third->first_use_);
- third->first_use_ = new(&allocator) UsePosition(user, false, 4, third->first_use_);
- third->first_use_ = new(&allocator) UsePosition(user, false, 3, third->first_use_);
+ third->uses_.push_front(*new(&allocator) UsePosition(user, false, 8));
+ third->uses_.push_front(*new(&allocator) UsePosition(user, false, 4));
+ third->uses_.push_front(*new(&allocator) UsePosition(user, false, 3));
locations = new (&allocator) LocationSummary(third->GetDefinedBy(), LocationSummary::kNoCall);
locations->SetOut(Location::RequiresRegister());
third = third->SplitAt(3);
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index b538a89..7b7495b 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -356,14 +356,16 @@
}
}
- UsePosition* use = first_use_;
size_t start = GetStart();
size_t end = GetEnd();
- while (use != nullptr && use->GetPosition() <= end) {
- size_t use_position = use->GetPosition();
- if (use_position >= start && !use->IsSynthesized()) {
- HInstruction* user = use->GetUser();
- size_t input_index = use->GetInputIndex();
+ for (const UsePosition& use : GetUses()) {
+ size_t use_position = use.GetPosition();
+ if (use_position > end) {
+ break;
+ }
+ if (use_position >= start && !use.IsSynthesized()) {
+ HInstruction* user = use.GetUser();
+ size_t input_index = use.GetInputIndex();
if (user->IsPhi()) {
// If the phi has a register, try to use the same.
Location phi_location = user->GetLiveInterval()->ToLocation();
@@ -395,7 +397,7 @@
} else {
// If the instruction is expected in a register, try to use it.
LocationSummary* locations = user->GetLocations();
- Location expected = locations->InAt(use->GetInputIndex());
+ Location expected = locations->InAt(use.GetInputIndex());
// We use the user's lifetime position - 1 (and not `use_position`) because the
// register is blocked at the beginning of the user.
size_t position = user->GetLifetimePosition() - 1;
@@ -408,7 +410,6 @@
}
}
}
- use = use->GetNext();
}
return kNoRegister;
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 {