summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--compiler/optimizing/graph_visualizer.cc12
-rw-r--r--compiler/optimizing/nodes.h7
-rw-r--r--compiler/optimizing/register_allocation_resolver.cc67
-rw-r--r--compiler/optimizing/register_allocator_graph_color.cc54
-rw-r--r--compiler/optimizing/register_allocator_test.cc12
-rw-r--r--compiler/optimizing/ssa_liveness_analysis.cc17
-rw-r--r--compiler/optimizing/ssa_liveness_analysis.h242
-rw-r--r--compiler/utils/intrusive_forward_list.h30
-rw-r--r--compiler/utils/intrusive_forward_list_test.cc418
9 files changed, 585 insertions, 274 deletions
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index 02816cf7ce..7dcf2440b2 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 @@ class StringList {
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 @@ class HGraphVisualizerPrinter : public HGraphDelegateVisitor {
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 4d96fbe24c..85e37ca817 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -1485,7 +1485,8 @@ FOR_EACH_INSTRUCTION(FORWARD_DECLARATION)
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 @@ class HUseListNode : public ArenaObject<kArenaAllocUseListNode> {
// 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 c6a0b6a0d2..ce3a4966aa 100644
--- a/compiler/optimizing/register_allocation_resolver.cc
+++ b/compiler/optimizing/register_allocation_resolver.cc
@@ -308,8 +308,10 @@ void RegisterAllocationResolver::ConnectSiblings(LiveInterval* interval) {
}
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 @@ void RegisterAllocationResolver::ConnectSiblings(LiveInterval* interval) {
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();
- }
-
- 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();
+ 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);
}
+ env_use_it = matching_env_use_range.end();
range = range->GetNext();
}
@@ -395,13 +401,8 @@ void RegisterAllocationResolver::ConnectSiblings(LiveInterval* interval) {
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 300f4c6239..090ba3117c 100644
--- a/compiler/optimizing/register_allocator_graph_color.cc
+++ b/compiler/optimizing/register_allocator_graph_color.cc
@@ -178,18 +178,17 @@ static float ComputeSpillWeight(LiveInterval* interval, const SsaLivenessAnalysi
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 @@ void RegisterAllocatorGraphColor::SplitAtRegisterUses(LiveInterval* interval) {
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 @@ void RegisterAllocatorGraphColor::SplitAtRegisterUses(LiveInterval* interval) {
interval = TrySplit(interval, position);
}
}
- use = use->GetNext();
}
}
@@ -1398,18 +1396,20 @@ void ColoringIteration::FindCoalesceOpportunities() {
}
// 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 667afb1ec3..24a2ab24d8 100644
--- a/compiler/optimizing/register_allocator_test.cc
+++ b/compiler/optimizing/register_allocator_test.cc
@@ -912,9 +912,9 @@ TEST_F(RegisterAllocatorTest, SpillInactive) {
// 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 @@ TEST_F(RegisterAllocatorTest, SpillInactive) {
// 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 b538a89a06..7b7495bf3b 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -356,14 +356,16 @@ int LiveInterval::FindFirstRegisterHint(size_t* free_until,
}
}
- 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 @@ int LiveInterval::FindFirstRegisterHint(size_t* free_until,
} 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 @@ int LiveInterval::FindFirstRegisterHint(size_t* free_until,
}
}
}
- use = use->GetNext();
}
return kNoRegister;
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index e9dffc1fac..a6681575a2 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 @@ class LiveRange FINAL : public ArenaObject<kArenaAllocSsaLiveness> {
/**
* 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 @@ class UsePosition : public ArenaObject<kArenaAllocSsaLiveness> {
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 @@ class UsePosition : public ArenaObject<kArenaAllocSsaLiveness> {
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 @@ class EnvUsePosition : public ArenaObject<kArenaAllocSsaLiveness> {
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 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
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 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
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 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
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 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
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 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
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 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
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 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
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 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
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 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
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 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
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 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
}
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 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
// 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 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
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 @@ class LiveInterval : public ArenaObject<kArenaAllocSsaLiveness> {
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 @@ class SsaLivenessAnalysis : public ValueObject {
// 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 {
diff --git a/compiler/utils/intrusive_forward_list.h b/compiler/utils/intrusive_forward_list.h
index b5fc2f2456..5a358ac2c4 100644
--- a/compiler/utils/intrusive_forward_list.h
+++ b/compiler/utils/intrusive_forward_list.h
@@ -23,6 +23,7 @@
#include <memory>
#include <type_traits>
+#include "base/casts.h"
#include "base/logging.h"
#include "base/macros.h"
@@ -42,10 +43,19 @@ struct IntrusiveForwardListHook {
mutable const IntrusiveForwardListHook* next_hook;
};
+template <typename Derived, typename Tag = void>
+struct IntrusiveForwardListNode : public IntrusiveForwardListHook {
+};
+
template <typename T, IntrusiveForwardListHook T::* NextPtr = &T::hook>
-class IntrusiveForwardListMemberHook;
+class IntrusiveForwardListMemberHookTraits;
+
+template <typename T, typename Tag = void>
+class IntrusiveForwardListBaseHookTraits;
-template <typename T, typename HookTraits = IntrusiveForwardListMemberHook<T>>
+template <typename T,
+ typename HookTraits =
+ IntrusiveForwardListBaseHookTraits<typename std::remove_const<T>::type>>
class IntrusiveForwardList;
template <typename T, typename HookTraits>
@@ -435,7 +445,7 @@ bool operator>=(const IntrusiveForwardList<T, HookTraits>& lhs,
}
template <typename T, IntrusiveForwardListHook T::* NextPtr>
-class IntrusiveForwardListMemberHook {
+class IntrusiveForwardListMemberHookTraits {
public:
static const IntrusiveForwardListHook* GetHook(const T* value) {
return &(value->*NextPtr);
@@ -447,6 +457,20 @@ class IntrusiveForwardListMemberHook {
}
};
+template <typename T, typename Tag>
+class IntrusiveForwardListBaseHookTraits {
+ public:
+ static const IntrusiveForwardListHook* GetHook(const T* value) {
+ // Explicit conversion to the "node" followed by implicit conversion to the "hook".
+ return static_cast<const IntrusiveForwardListNode<T, Tag>*>(value);
+ }
+
+ static T* GetValue(const IntrusiveForwardListHook* hook) {
+ return down_cast<T*>(down_cast<IntrusiveForwardListNode<T, Tag>*>(
+ const_cast<IntrusiveForwardListHook*>(hook)));
+ }
+};
+
} // namespace art
#endif // ART_COMPILER_UTILS_INTRUSIVE_FORWARD_LIST_H_
diff --git a/compiler/utils/intrusive_forward_list_test.cc b/compiler/utils/intrusive_forward_list_test.cc
index f2efa4dd15..939676cdc8 100644
--- a/compiler/utils/intrusive_forward_list_test.cc
+++ b/compiler/utils/intrusive_forward_list_test.cc
@@ -23,13 +23,14 @@
namespace art {
-struct IFLTestValue {
+struct IFLTestValue : public IntrusiveForwardListNode<IFLTestValue> {
// Deliberately not explicit.
- IFLTestValue(int v) : hook(), value(v) { } // NOLINT(runtime/explicit)
+ IFLTestValue(int v) : value(v) { } // NOLINT(runtime/explicit)
- IntrusiveForwardListHook hook;
int value;
};
+using IFLTestValueList = IntrusiveForwardList<IFLTestValue>;
+using ConstIFLTestValueList = IntrusiveForwardList<const IFLTestValue>;
bool operator==(const IFLTestValue& lhs, const IFLTestValue& rhs) {
return lhs.value == rhs.value;
@@ -39,6 +40,24 @@ bool operator<(const IFLTestValue& lhs, const IFLTestValue& rhs) {
return lhs.value < rhs.value;
}
+struct IFLTestValue2 {
+ // Deliberately not explicit.
+ IFLTestValue2(int v) : hook(), value(v) { } // NOLINT(runtime/explicit)
+
+ IntrusiveForwardListHook hook;
+ int value;
+};
+using IFLTestValue2List =
+ IntrusiveForwardList<IFLTestValue2, IntrusiveForwardListMemberHookTraits<IFLTestValue2>>;
+
+bool operator==(const IFLTestValue2& lhs, const IFLTestValue2& rhs) {
+ return lhs.value == rhs.value;
+}
+
+bool operator<(const IFLTestValue2& lhs, const IFLTestValue2& rhs) {
+ return lhs.value < rhs.value;
+}
+
#define ASSERT_LISTS_EQUAL(expected, value) \
do { \
ASSERT_EQ((expected).empty(), (value).empty()); \
@@ -47,16 +66,82 @@ bool operator<(const IFLTestValue& lhs, const IFLTestValue& rhs) {
ASSERT_TRUE(std::equal((expected).begin(), (expected).end(), (value).begin())); \
} while (false)
-TEST(IntrusiveForwardList, IteratorToConstIterator) {
- IntrusiveForwardList<IFLTestValue> ifl;
- IntrusiveForwardList<IFLTestValue>::iterator begin = ifl.begin();
- IntrusiveForwardList<IFLTestValue>::const_iterator cbegin = ifl.cbegin();
- IntrusiveForwardList<IFLTestValue>::const_iterator converted_begin = begin;
+class IntrusiveForwardListTest : public testing::Test {
+ public:
+ template <typename ListType>
+ void IteratorToConstIterator();
+
+ template <typename ListType>
+ void IteratorOperators();
+
+ template <typename ListType>
+ void ConstructRange();
+
+ template <typename ListType>
+ void Assign();
+
+ template <typename ListType>
+ void PushPop();
+
+ template <typename ListType>
+ void InsertAfter1();
+
+ template <typename ListType>
+ void InsertAfter2();
+
+ template <typename ListType>
+ void EraseAfter1();
+
+ template <typename ListType>
+ void EraseAfter2();
+
+ template <typename ListType>
+ void SwapClear();
+
+ template <typename ListType>
+ void SpliceAfter();
+
+ template <typename ListType>
+ void Remove();
+
+ template <typename ListType>
+ void Unique();
+
+ template <typename ListType>
+ void Merge();
+
+ template <typename ListType>
+ void Sort1();
+
+ template <typename ListType>
+ void Sort2();
+
+ template <typename ListType>
+ void Reverse();
+
+ template <typename ListType>
+ void ModifyValue();
+};
+
+template <typename ListType>
+void IntrusiveForwardListTest::IteratorToConstIterator() {
+ ListType ifl;
+ typename ListType::iterator begin = ifl.begin();
+ typename ListType::const_iterator cbegin = ifl.cbegin();
+ typename ListType::const_iterator converted_begin = begin;
ASSERT_TRUE(converted_begin == cbegin);
}
-TEST(IntrusiveForwardList, IteratorOperators) {
- IntrusiveForwardList<IFLTestValue> ifl;
+TEST_F(IntrusiveForwardListTest, IteratorToConstIterator) {
+ IteratorToConstIterator<IFLTestValueList>();
+ IteratorToConstIterator<ConstIFLTestValueList>();
+ IteratorToConstIterator<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::IteratorOperators() {
+ using ValueType = typename ListType::value_type;
+ ListType ifl;
ASSERT_TRUE(ifl.begin() == ifl.cbegin());
ASSERT_FALSE(ifl.begin() != ifl.cbegin());
ASSERT_TRUE(ifl.end() == ifl.cend());
@@ -65,37 +150,61 @@ TEST(IntrusiveForwardList, IteratorOperators) {
ASSERT_TRUE(ifl.begin() == ifl.end()); // Empty.
ASSERT_FALSE(ifl.begin() != ifl.end()); // Empty.
- IFLTestValue value(1);
+ ValueType value(1);
ifl.insert_after(ifl.cbefore_begin(), value);
ASSERT_FALSE(ifl.begin() == ifl.end()); // Not empty.
ASSERT_TRUE(ifl.begin() != ifl.end()); // Not empty.
}
-TEST(IntrusiveForwardList, ConstructRange) {
+TEST_F(IntrusiveForwardListTest, IteratorOperators) {
+ IteratorOperators<IFLTestValueList>();
+ IteratorOperators<ConstIFLTestValueList>();
+ IteratorOperators<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::ConstructRange() {
+ using ValueType = typename ListType::value_type;
std::forward_list<int> ref({ 1, 2, 7 });
- std::vector<IFLTestValue> storage(ref.begin(), ref.end());
- IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
+ std::vector<ValueType> storage(ref.begin(), ref.end());
+ ListType ifl(storage.begin(), storage.end());
ASSERT_LISTS_EQUAL(ref, ifl);
}
-TEST(IntrusiveForwardList, Assign) {
+TEST_F(IntrusiveForwardListTest, ConstructRange) {
+ ConstructRange<IFLTestValueList>();
+ ConstructRange<ConstIFLTestValueList>();
+ ConstructRange<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::Assign() {
+ using ValueType = typename ListType::value_type;
std::forward_list<int> ref1({ 2, 8, 5 });
- std::vector<IFLTestValue> storage1(ref1.begin(), ref1.end());
- IntrusiveForwardList<IFLTestValue> ifl;
+ std::vector<ValueType> storage1(ref1.begin(), ref1.end());
+ ListType ifl;
ifl.assign(storage1.begin(), storage1.end());
ASSERT_LISTS_EQUAL(ref1, ifl);
std::forward_list<int> ref2({ 7, 1, 3 });
- std::vector<IFLTestValue> storage2(ref2.begin(), ref2.end());
+ std::vector<ValueType> storage2(ref2.begin(), ref2.end());
ifl.assign(storage2.begin(), storage2.end());
ASSERT_LISTS_EQUAL(ref2, ifl);
}
-TEST(IntrusiveForwardList, PushPop) {
- IFLTestValue value3(3);
- IFLTestValue value7(7);
+TEST_F(IntrusiveForwardListTest, Assign) {
+ Assign<IFLTestValueList>();
+ Assign<ConstIFLTestValueList>();
+ Assign<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::PushPop() {
+ using ValueType = typename ListType::value_type;
+ ValueType value3(3);
+ ValueType value7(7);
std::forward_list<int> ref;
- IntrusiveForwardList<IFLTestValue> ifl;
+ ListType ifl;
ASSERT_LISTS_EQUAL(ref, ifl);
ref.push_front(3);
ifl.push_front(value3);
@@ -114,13 +223,21 @@ TEST(IntrusiveForwardList, PushPop) {
ASSERT_LISTS_EQUAL(ref, ifl);
}
-TEST(IntrusiveForwardList, InsertAfter1) {
- IFLTestValue value4(4);
- IFLTestValue value8(8);
- IFLTestValue value5(5);
- IFLTestValue value3(3);
+TEST_F(IntrusiveForwardListTest, PushPop) {
+ PushPop<IFLTestValueList>();
+ PushPop<ConstIFLTestValueList>();
+ PushPop<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::InsertAfter1() {
+ using ValueType = typename ListType::value_type;
+ ValueType value4(4);
+ ValueType value8(8);
+ ValueType value5(5);
+ ValueType value3(3);
std::forward_list<int> ref;
- IntrusiveForwardList<IFLTestValue> ifl;
+ ListType ifl;
auto ref_it = ref.insert_after(ref.before_begin(), 4);
auto ifl_it = ifl.insert_after(ifl.before_begin(), value4);
@@ -149,23 +266,31 @@ TEST(IntrusiveForwardList, InsertAfter1) {
ASSERT_EQ(*ref_it, *ifl_it);
}
-TEST(IntrusiveForwardList, InsertAfter2) {
+TEST_F(IntrusiveForwardListTest, InsertAfter1) {
+ InsertAfter1<IFLTestValueList>();
+ InsertAfter1<ConstIFLTestValueList>();
+ InsertAfter1<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::InsertAfter2() {
+ using ValueType = typename ListType::value_type;
std::forward_list<int> ref;
- IntrusiveForwardList<IFLTestValue> ifl;
+ ListType ifl;
auto ref_it = ref.insert_after(ref.before_begin(), { 2, 8, 5 });
- std::vector<IFLTestValue> storage1({ { 2 }, { 8 }, { 5 } });
+ std::vector<ValueType> storage1({ { 2 }, { 8 }, { 5 } });
auto ifl_it = ifl.insert_after(ifl.before_begin(), storage1.begin(), storage1.end());
ASSERT_LISTS_EQUAL(ref, ifl);
ASSERT_EQ(*ref_it, *ifl_it);
- std::vector<IFLTestValue> storage2({ { 7 }, { 2 } });
+ std::vector<ValueType> storage2({ { 7 }, { 2 } });
ref_it = ref.insert_after(ref.begin(), { 7, 2 });
ifl_it = ifl.insert_after(ifl.begin(), storage2.begin(), storage2.end());
ASSERT_LISTS_EQUAL(ref, ifl);
ASSERT_EQ(*ref_it, *ifl_it);
- std::vector<IFLTestValue> storage3({ { 1 }, { 3 }, { 4 }, { 9 } });
+ std::vector<ValueType> storage3({ { 1 }, { 3 }, { 4 }, { 9 } });
ref_it = ref.begin();
ifl_it = ifl.begin();
std::advance(ref_it, std::distance(ref.begin(), ref.end()) - 1);
@@ -175,10 +300,18 @@ TEST(IntrusiveForwardList, InsertAfter2) {
ASSERT_LISTS_EQUAL(ref, ifl);
}
-TEST(IntrusiveForwardList, EraseAfter1) {
+TEST_F(IntrusiveForwardListTest, InsertAfter2) {
+ InsertAfter2<IFLTestValueList>();
+ InsertAfter2<ConstIFLTestValueList>();
+ InsertAfter2<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::EraseAfter1() {
+ using ValueType = typename ListType::value_type;
std::forward_list<int> ref({ 1, 2, 7, 4, 5 });
- std::vector<IFLTestValue> storage(ref.begin(), ref.end());
- IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
+ std::vector<ValueType> storage(ref.begin(), ref.end());
+ ListType ifl(storage.begin(), storage.end());
ASSERT_LISTS_EQUAL(ref, ifl);
CHECK_EQ(std::distance(ref.begin(), ref.end()), 5);
@@ -230,10 +363,18 @@ TEST(IntrusiveForwardList, EraseAfter1) {
ASSERT_TRUE(ifl_it == ifl.begin());
}
-TEST(IntrusiveForwardList, EraseAfter2) {
+TEST_F(IntrusiveForwardListTest, EraseAfter1) {
+ EraseAfter1<IFLTestValueList>();
+ EraseAfter1<ConstIFLTestValueList>();
+ EraseAfter1<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::EraseAfter2() {
+ using ValueType = typename ListType::value_type;
std::forward_list<int> ref({ 1, 2, 7, 4, 5, 3, 2, 8, 9 });
- std::vector<IFLTestValue> storage(ref.begin(), ref.end());
- IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
+ std::vector<ValueType> storage(ref.begin(), ref.end());
+ ListType ifl(storage.begin(), storage.end());
ASSERT_LISTS_EQUAL(ref, ifl);
CHECK_EQ(std::distance(ref.begin(), ref.end()), 9);
@@ -262,13 +403,21 @@ TEST(IntrusiveForwardList, EraseAfter2) {
CHECK_EQ(std::distance(ref.begin(), ref.end()), 0);
}
-TEST(IntrusiveForwardList, SwapClear) {
+TEST_F(IntrusiveForwardListTest, EraseAfter2) {
+ EraseAfter2<IFLTestValueList>();
+ EraseAfter2<ConstIFLTestValueList>();
+ EraseAfter2<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::SwapClear() {
+ using ValueType = typename ListType::value_type;
std::forward_list<int> ref1({ 1, 2, 7 });
- std::vector<IFLTestValue> storage1(ref1.begin(), ref1.end());
- IntrusiveForwardList<IFLTestValue> ifl1(storage1.begin(), storage1.end());
+ std::vector<ValueType> storage1(ref1.begin(), ref1.end());
+ ListType ifl1(storage1.begin(), storage1.end());
std::forward_list<int> ref2({ 3, 8, 6 });
- std::vector<IFLTestValue> storage2(ref2.begin(), ref2.end());
- IntrusiveForwardList<IFLTestValue> ifl2(storage2.begin(), storage2.end());
+ std::vector<ValueType> storage2(ref2.begin(), ref2.end());
+ ListType ifl2(storage2.begin(), storage2.end());
ASSERT_LISTS_EQUAL(ref1, ifl1);
ASSERT_LISTS_EQUAL(ref2, ifl2);
ref1.swap(ref2);
@@ -289,12 +438,20 @@ TEST(IntrusiveForwardList, SwapClear) {
ASSERT_LISTS_EQUAL(ref2, ifl2);
}
-TEST(IntrusiveForwardList, SpliceAfter) {
+TEST_F(IntrusiveForwardListTest, SwapClear) {
+ SwapClear<IFLTestValueList>();
+ SwapClear<ConstIFLTestValueList>();
+ SwapClear<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::SpliceAfter() {
+ using ValueType = typename ListType::value_type;
std::forward_list<int> ref1({ 3, 1, 2, 7, 4, 5, 4, 8, 7 });
std::forward_list<int> ref2;
- std::vector<IFLTestValue> storage(ref1.begin(), ref1.end());
- IntrusiveForwardList<IFLTestValue> ifl1(storage.begin(), storage.end());
- IntrusiveForwardList<IFLTestValue> ifl2;
+ std::vector<ValueType> storage(ref1.begin(), ref1.end());
+ ListType ifl1(storage.begin(), storage.end());
+ ListType ifl2;
ASSERT_LISTS_EQUAL(ref1, ifl1);
ASSERT_LISTS_EQUAL(ref2, ifl2);
@@ -398,10 +555,18 @@ TEST(IntrusiveForwardList, SpliceAfter) {
ASSERT_LISTS_EQUAL(check, ifl2);
}
-TEST(IntrusiveForwardList, Remove) {
+TEST_F(IntrusiveForwardListTest, SpliceAfter) {
+ SpliceAfter<IFLTestValueList>();
+ SpliceAfter<ConstIFLTestValueList>();
+ SpliceAfter<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::Remove() {
+ using ValueType = typename ListType::value_type;
std::forward_list<int> ref({ 3, 1, 2, 7, 4, 5, 4, 8, 7 });
- std::vector<IFLTestValue> storage(ref.begin(), ref.end());
- IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
+ std::vector<ValueType> storage(ref.begin(), ref.end());
+ ListType ifl(storage.begin(), storage.end());
ASSERT_LISTS_EQUAL(ref, ifl);
ref.remove(1);
ifl.remove(1);
@@ -409,20 +574,28 @@ TEST(IntrusiveForwardList, Remove) {
ref.remove(4);
ifl.remove(4);
ASSERT_LISTS_EQUAL(ref, ifl);
- auto odd = [](IFLTestValue value) { return (value.value & 1) != 0; }; // NOLINT(readability/braces)
+ auto odd = [](ValueType value) { return (value.value & 1) != 0; }; // NOLINT(readability/braces)
ref.remove_if(odd);
ifl.remove_if(odd);
ASSERT_LISTS_EQUAL(ref, ifl);
- auto all = [](IFLTestValue value ATTRIBUTE_UNUSED) { return true; }; // NOLINT(readability/braces)
+ auto all = [](ValueType value ATTRIBUTE_UNUSED) { return true; }; // NOLINT(readability/braces)
ref.remove_if(all);
ifl.remove_if(all);
ASSERT_LISTS_EQUAL(ref, ifl);
}
-TEST(IntrusiveForwardList, Unique) {
+TEST_F(IntrusiveForwardListTest, Remove) {
+ Remove<IFLTestValueList>();
+ Remove<ConstIFLTestValueList>();
+ Remove<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::Unique() {
+ using ValueType = typename ListType::value_type;
std::forward_list<int> ref({ 3, 1, 1, 2, 3, 3, 7, 7, 4, 4, 5, 7 });
- std::vector<IFLTestValue> storage(ref.begin(), ref.end());
- IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
+ std::vector<ValueType> storage(ref.begin(), ref.end());
+ ListType ifl(storage.begin(), storage.end());
ASSERT_LISTS_EQUAL(ref, ifl);
ref.unique();
ifl.unique();
@@ -430,7 +603,7 @@ TEST(IntrusiveForwardList, Unique) {
std::forward_list<int> check({ 3, 1, 2, 3, 7, 4, 5, 7 });
ASSERT_LISTS_EQUAL(check, ifl);
- auto bin_pred = [](IFLTestValue lhs, IFLTestValue rhs) {
+ auto bin_pred = [](const ValueType& lhs, const ValueType& rhs) {
return (lhs.value & ~1) == (rhs.value & ~1);
};
ref.unique(bin_pred);
@@ -440,13 +613,21 @@ TEST(IntrusiveForwardList, Unique) {
ASSERT_LISTS_EQUAL(check, ifl);
}
-TEST(IntrusiveForwardList, Merge) {
+TEST_F(IntrusiveForwardListTest, Unique) {
+ Unique<IFLTestValueList>();
+ Unique<ConstIFLTestValueList>();
+ Unique<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::Merge() {
+ using ValueType = typename ListType::value_type;
std::forward_list<int> ref1({ 1, 4, 8, 8, 12 });
- std::vector<IFLTestValue> storage1(ref1.begin(), ref1.end());
- IntrusiveForwardList<IFLTestValue> ifl1(storage1.begin(), storage1.end());
+ std::vector<ValueType> storage1(ref1.begin(), ref1.end());
+ ListType ifl1(storage1.begin(), storage1.end());
std::forward_list<int> ref2({ 3, 5, 6, 7, 9 });
- std::vector<IFLTestValue> storage2(ref2.begin(), ref2.end());
- IntrusiveForwardList<IFLTestValue> ifl2(storage2.begin(), storage2.end());
+ std::vector<ValueType> storage2(ref2.begin(), ref2.end());
+ ListType ifl2(storage2.begin(), storage2.end());
ASSERT_LISTS_EQUAL(ref1, ifl1);
ASSERT_LISTS_EQUAL(ref2, ifl2);
CHECK(std::is_sorted(ref1.begin(), ref1.end()));
@@ -460,10 +641,18 @@ TEST(IntrusiveForwardList, Merge) {
ASSERT_LISTS_EQUAL(check, ifl1);
}
-TEST(IntrusiveForwardList, Sort1) {
+TEST_F(IntrusiveForwardListTest, Merge) {
+ Merge<IFLTestValueList>();
+ Merge<ConstIFLTestValueList>();
+ Merge<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::Sort1() {
+ using ValueType = typename ListType::value_type;
std::forward_list<int> ref({ 2, 9, 8, 3, 7, 4, 1, 5, 3, 0 });
- std::vector<IFLTestValue> storage(ref.begin(), ref.end());
- IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
+ std::vector<ValueType> storage(ref.begin(), ref.end());
+ ListType ifl(storage.begin(), storage.end());
ASSERT_LISTS_EQUAL(ref, ifl);
CHECK(!std::is_sorted(ref.begin(), ref.end()));
ref.sort();
@@ -473,12 +662,20 @@ TEST(IntrusiveForwardList, Sort1) {
ASSERT_LISTS_EQUAL(check, ifl);
}
-TEST(IntrusiveForwardList, Sort2) {
+TEST_F(IntrusiveForwardListTest, Sort1) {
+ Sort1<IFLTestValueList>();
+ Sort1<ConstIFLTestValueList>();
+ Sort1<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::Sort2() {
+ using ValueType = typename ListType::value_type;
std::forward_list<int> ref({ 2, 9, 8, 3, 7, 4, 1, 5, 3, 0 });
- std::vector<IFLTestValue> storage(ref.begin(), ref.end());
- IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
+ std::vector<ValueType> storage(ref.begin(), ref.end());
+ ListType ifl(storage.begin(), storage.end());
ASSERT_LISTS_EQUAL(ref, ifl);
- auto cmp = [](IFLTestValue lhs, IFLTestValue rhs) {
+ auto cmp = [](const ValueType& lhs, const ValueType& rhs) {
return (lhs.value & ~1) < (rhs.value & ~1);
};
CHECK(!std::is_sorted(ref.begin(), ref.end(), cmp));
@@ -489,10 +686,18 @@ TEST(IntrusiveForwardList, Sort2) {
ASSERT_LISTS_EQUAL(check, ifl);
}
-TEST(IntrusiveForwardList, Reverse) {
+TEST_F(IntrusiveForwardListTest, Sort2) {
+ Sort2<IFLTestValueList>();
+ Sort2<ConstIFLTestValueList>();
+ Sort2<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::Reverse() {
+ using ValueType = typename ListType::value_type;
std::forward_list<int> ref({ 8, 3, 5, 4, 1, 3 });
- std::vector<IFLTestValue> storage(ref.begin(), ref.end());
- IntrusiveForwardList<IFLTestValue> ifl(storage.begin(), storage.end());
+ std::vector<ValueType> storage(ref.begin(), ref.end());
+ ListType ifl(storage.begin(), storage.end());
ASSERT_LISTS_EQUAL(ref, ifl);
CHECK(!std::is_sorted(ref.begin(), ref.end()));
ref.reverse();
@@ -502,4 +707,73 @@ TEST(IntrusiveForwardList, Reverse) {
ASSERT_LISTS_EQUAL(check, ifl);
}
+TEST_F(IntrusiveForwardListTest, Reverse) {
+ Reverse<IFLTestValueList>();
+ Reverse<ConstIFLTestValueList>();
+ Reverse<IFLTestValue2List>();
+}
+
+template <typename ListType>
+void IntrusiveForwardListTest::ModifyValue() {
+ using ValueType = typename ListType::value_type;
+ std::forward_list<int> ref({ 3, 7, 42 });
+ std::vector<ValueType> storage(ref.begin(), ref.end());
+ ListType ifl(storage.begin(), storage.end());
+ ASSERT_LISTS_EQUAL(ref, ifl);
+
+ auto add1 = [](const ValueType& value) { return value.value + 1; }; // NOLINT [readability/braces]
+ std::transform(ref.begin(), ref.end(), ref.begin(), add1);
+ std::transform(ifl.begin(), ifl.end(), ifl.begin(), add1);
+ ASSERT_LISTS_EQUAL(ref, ifl);
+}
+
+TEST_F(IntrusiveForwardListTest, ModifyValue) {
+ ModifyValue<IFLTestValueList>();
+ // Does not compile with ConstIFLTestValueList because LHS of the assignment is const.
+ // ModifyValue<ConstIFLTestValueList>();
+ static_assert(std::is_const<ConstIFLTestValueList::iterator::value_type>::value, "Const check.");
+ ModifyValue<IFLTestValue2List>();
+}
+
+struct Tag1;
+struct Tag2;
+struct TwoListsValue : public IntrusiveForwardListNode<TwoListsValue, Tag1>,
+ public IntrusiveForwardListNode<TwoListsValue, Tag2> {
+ // Deliberately not explicit.
+ TwoListsValue(int v) : value(v) { } // NOLINT(runtime/explicit)
+
+ int value;
+};
+using FirstList =
+ IntrusiveForwardList<TwoListsValue, IntrusiveForwardListBaseHookTraits<TwoListsValue, Tag1>>;
+using SecondList =
+ IntrusiveForwardList<TwoListsValue, IntrusiveForwardListBaseHookTraits<TwoListsValue, Tag2>>;
+
+bool operator==(const TwoListsValue& lhs, const TwoListsValue& rhs) {
+ return lhs.value == rhs.value;
+}
+
+TEST_F(IntrusiveForwardListTest, TwoLists) {
+ // Test that a value can be in two lists at the same time and the hooks do not interfere.
+ std::vector<TwoListsValue> storage({ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }); // storage[i] = i
+
+ std::vector<int> order1({ 3, 1, 7, 2, 8, 9, 4, 0, 6, 5 });
+ FirstList list1;
+ auto pos1 = list1.before_begin();
+ for (size_t idx : order1) {
+ pos1 = list1.insert_after(pos1, storage[idx]);
+ }
+
+ std::vector<int> order2({ 8, 5, 1, 6, 7, 2, 9, 3, 0, 4 });
+ SecondList list2;
+ auto pos2 = list2.before_begin();
+ for (size_t idx : order2) {
+ pos2 = list2.insert_after(pos2, storage[idx]);
+ }
+
+ // Using `storage[i] = i`, we can easily compare that nodes of each list are in the right order.
+ ASSERT_LISTS_EQUAL(order1, list1);
+ ASSERT_LISTS_EQUAL(order2, list2);
+}
+
} // namespace art
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2025-10-20 09:11:48 +0000