Opt compiler: Implement parallel move resolver without using swap.
The algorithm of ParallelMoveResolverNoSwap() is almost the same with
ParallelMoveResolverWithSwap(), except the way we resolve the circular
dependency. NoSwap() uses additional scratch register to resolve the
circular dependency. For example, (0->1) (1->2) (2->0) will be performed
as (2->scratch) (1->2) (0->1) (scratch->0).
On architectures without swap register support, NoSwap() can reduce the
number of moves from 3x(N-1) to (N+1) when there is circular dependency
with N moves.
And also, NoSwap() algorithm does not depend on architecture register
layout information, which means it can support register pairs on arm32
and X/W, D/S registers on arm64 without additional modification.
Change-Id: Idf56bd5469bb78c0e339e43ab16387428a082318
diff --git a/compiler/optimizing/parallel_move_test.cc b/compiler/optimizing/parallel_move_test.cc
index 95cca51..f8f7010 100644
--- a/compiler/optimizing/parallel_move_test.cc
+++ b/compiler/optimizing/parallel_move_test.cc
@@ -19,27 +19,41 @@
#include "parallel_move_resolver.h"
#include "gtest/gtest.h"
+#include "gtest/gtest-typed-test.h"
namespace art {
-class TestParallelMoveResolver : public ParallelMoveResolver {
- public:
- explicit TestParallelMoveResolver(ArenaAllocator* allocator) : ParallelMoveResolver(allocator) {}
+constexpr int kScratchRegisterStartIndexForTest = 100;
- void Dump(Location location) {
- if (location.IsConstant()) {
- message_ << "C";
- } else if (location.IsPair()) {
- message_ << location.low() << "," << location.high();
- } else if (location.IsRegister()) {
- message_ << location.reg();
- } else if (location.IsStackSlot()) {
- message_ << location.GetStackIndex() << "(sp)";
- } else {
- message_ << "2x" << location.GetStackIndex() << "(sp)";
- DCHECK(location.IsDoubleStackSlot()) << location;
- }
+static void DumpRegisterForTest(std::ostream& os, int reg) {
+ if (reg >= kScratchRegisterStartIndexForTest) {
+ os << "T" << reg - kScratchRegisterStartIndexForTest;
+ } else {
+ os << reg;
}
+}
+
+static void DumpLocationForTest(std::ostream& os, Location location) {
+ if (location.IsConstant()) {
+ os << "C";
+ } else if (location.IsPair()) {
+ DumpRegisterForTest(os, location.low());
+ os << ",";
+ DumpRegisterForTest(os, location.high());
+ } else if (location.IsRegister()) {
+ DumpRegisterForTest(os, location.reg());
+ } else if (location.IsStackSlot()) {
+ os << location.GetStackIndex() << "(sp)";
+ } else {
+ DCHECK(location.IsDoubleStackSlot())<< location;
+ os << "2x" << location.GetStackIndex() << "(sp)";
+ }
+}
+
+class TestParallelMoveResolverWithSwap : public ParallelMoveResolverWithSwap {
+ public:
+ explicit TestParallelMoveResolverWithSwap(ArenaAllocator* allocator)
+ : ParallelMoveResolverWithSwap(allocator) {}
void EmitMove(size_t index) OVERRIDE {
MoveOperands* move = moves_.Get(index);
@@ -47,9 +61,9 @@
message_ << " ";
}
message_ << "(";
- Dump(move->GetSource());
+ DumpLocationForTest(message_, move->GetSource());
message_ << " -> ";
- Dump(move->GetDestination());
+ DumpLocationForTest(message_, move->GetDestination());
message_ << ")";
}
@@ -59,9 +73,9 @@
message_ << " ";
}
message_ << "(";
- Dump(move->GetSource());
+ DumpLocationForTest(message_, move->GetSource());
message_ << " <-> ";
- Dump(move->GetDestination());
+ DumpLocationForTest(message_, move->GetDestination());
message_ << ")";
}
@@ -76,7 +90,64 @@
std::ostringstream message_;
- DISALLOW_COPY_AND_ASSIGN(TestParallelMoveResolver);
+ DISALLOW_COPY_AND_ASSIGN(TestParallelMoveResolverWithSwap);
+};
+
+class TestParallelMoveResolverNoSwap : public ParallelMoveResolverNoSwap {
+ public:
+ explicit TestParallelMoveResolverNoSwap(ArenaAllocator* allocator)
+ : ParallelMoveResolverNoSwap(allocator), scratch_index_(kScratchRegisterStartIndexForTest) {}
+
+ void PrepareForEmitNativeCode() OVERRIDE {
+ scratch_index_ = kScratchRegisterStartIndexForTest;
+ }
+
+ void FinishEmitNativeCode() OVERRIDE {}
+
+ Location AllocateScratchLocationFor(Location::Kind kind) OVERRIDE {
+ if (kind == Location::kStackSlot || kind == Location::kFpuRegister ||
+ kind == Location::kRegister) {
+ kind = Location::kRegister;
+ } else {
+ // Allocate register pair for double stack slot which simulates 32-bit backend's behavior.
+ kind = Location::kRegisterPair;
+ }
+ Location scratch = GetScratchLocation(kind);
+ if (scratch.Equals(Location::NoLocation())) {
+ AddScratchLocation(Location::RegisterLocation(scratch_index_));
+ AddScratchLocation(Location::RegisterLocation(scratch_index_ + 1));
+ AddScratchLocation(Location::RegisterPairLocation(scratch_index_, scratch_index_ + 1));
+ scratch = (kind == Location::kRegister) ? Location::RegisterLocation(scratch_index_)
+ : Location::RegisterPairLocation(scratch_index_, scratch_index_ + 1);
+ scratch_index_ += 2;
+ }
+ return scratch;
+ }
+
+ void FreeScratchLocation(Location loc ATTRIBUTE_UNUSED) OVERRIDE {}
+
+ void EmitMove(size_t index) OVERRIDE {
+ MoveOperands* move = moves_.Get(index);
+ if (!message_.str().empty()) {
+ message_ << " ";
+ }
+ message_ << "(";
+ DumpLocationForTest(message_, move->GetSource());
+ message_ << " -> ";
+ DumpLocationForTest(message_, move->GetDestination());
+ message_ << ")";
+ }
+
+ std::string GetMessage() const {
+ return message_.str();
+ }
+
+ private:
+ std::ostringstream message_;
+
+ int scratch_index_;
+
+ DISALLOW_COPY_AND_ASSIGN(TestParallelMoveResolverNoSwap);
};
static HParallelMove* BuildParallelMove(ArenaAllocator* allocator,
@@ -93,55 +164,102 @@
return moves;
}
-TEST(ParallelMoveTest, Dependency) {
+template <typename T>
+class ParallelMoveTest : public ::testing::Test {
+ public:
+ static const bool has_swap;
+};
+
+template<> const bool ParallelMoveTest<TestParallelMoveResolverWithSwap>::has_swap = true;
+template<> const bool ParallelMoveTest<TestParallelMoveResolverNoSwap>::has_swap = false;
+
+typedef ::testing::Types<TestParallelMoveResolverWithSwap, TestParallelMoveResolverNoSwap>
+ ParallelMoveResolverTestTypes;
+
+TYPED_TEST_CASE(ParallelMoveTest, ParallelMoveResolverTestTypes);
+
+
+TYPED_TEST(ParallelMoveTest, Dependency) {
ArenaPool pool;
ArenaAllocator allocator(&pool);
{
- TestParallelMoveResolver resolver(&allocator);
+ TypeParam resolver(&allocator);
static constexpr size_t moves[][2] = {{0, 1}, {1, 2}};
resolver.EmitNativeCode(BuildParallelMove(&allocator, moves, arraysize(moves)));
- ASSERT_STREQ("(1 -> 2) (0 -> 1)", resolver.GetMessage().c_str());
+ if (TestFixture::has_swap) {
+ ASSERT_STREQ("(1 -> 2) (0 -> 1)", resolver.GetMessage().c_str());
+ } else {
+ ASSERT_STREQ("(1 -> 2) (0 -> 1)", resolver.GetMessage().c_str());
+ }
}
{
- TestParallelMoveResolver resolver(&allocator);
+ TypeParam resolver(&allocator);
static constexpr size_t moves[][2] = {{0, 1}, {1, 2}, {2, 3}, {1, 4}};
resolver.EmitNativeCode(BuildParallelMove(&allocator, moves, arraysize(moves)));
- ASSERT_STREQ("(2 -> 3) (1 -> 2) (1 -> 4) (0 -> 1)", resolver.GetMessage().c_str());
+ if (TestFixture::has_swap) {
+ ASSERT_STREQ("(2 -> 3) (1 -> 2) (1 -> 4) (0 -> 1)", resolver.GetMessage().c_str());
+ } else {
+ ASSERT_STREQ("(2 -> 3) (1 -> 2) (0 -> 1) (2 -> 4)", resolver.GetMessage().c_str());
+ }
}
}
-TEST(ParallelMoveTest, Swap) {
+TYPED_TEST(ParallelMoveTest, Cycle) {
ArenaPool pool;
ArenaAllocator allocator(&pool);
{
- TestParallelMoveResolver resolver(&allocator);
+ TypeParam resolver(&allocator);
static constexpr size_t moves[][2] = {{0, 1}, {1, 0}};
resolver.EmitNativeCode(BuildParallelMove(&allocator, moves, arraysize(moves)));
- ASSERT_STREQ("(1 <-> 0)", resolver.GetMessage().c_str());
+ if (TestFixture::has_swap) {
+ ASSERT_STREQ("(1 <-> 0)", resolver.GetMessage().c_str());
+ } else {
+ ASSERT_STREQ("(1 -> T0) (0 -> 1) (T0 -> 0)", resolver.GetMessage().c_str());
+ }
}
{
- TestParallelMoveResolver resolver(&allocator);
+ TypeParam resolver(&allocator);
static constexpr size_t moves[][2] = {{0, 1}, {1, 2}, {1, 0}};
resolver.EmitNativeCode(BuildParallelMove(&allocator, moves, arraysize(moves)));
- ASSERT_STREQ("(1 -> 2) (1 <-> 0)", resolver.GetMessage().c_str());
+ if (TestFixture::has_swap) {
+ ASSERT_STREQ("(1 -> 2) (1 <-> 0)", resolver.GetMessage().c_str());
+ } else {
+ ASSERT_STREQ("(1 -> 2) (0 -> 1) (2 -> 0)", resolver.GetMessage().c_str());
+ }
}
{
- TestParallelMoveResolver resolver(&allocator);
+ TypeParam resolver(&allocator);
+ static constexpr size_t moves[][2] = {{0, 1}, {1, 0}, {0, 2}};
+ resolver.EmitNativeCode(BuildParallelMove(&allocator, moves, arraysize(moves)));
+ if (TestFixture::has_swap) {
+ ASSERT_STREQ("(0 -> 2) (1 <-> 0)", resolver.GetMessage().c_str());
+ } else {
+ ASSERT_STREQ("(0 -> 2) (1 -> 0) (2 -> 1)", resolver.GetMessage().c_str());
+ }
+ }
+
+ {
+ TypeParam resolver(&allocator);
static constexpr size_t moves[][2] = {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 0}};
resolver.EmitNativeCode(BuildParallelMove(&allocator, moves, arraysize(moves)));
- ASSERT_STREQ("(4 <-> 0) (3 <-> 4) (2 <-> 3) (1 <-> 2)", resolver.GetMessage().c_str());
+ if (TestFixture::has_swap) {
+ ASSERT_STREQ("(4 <-> 0) (3 <-> 4) (2 <-> 3) (1 <-> 2)", resolver.GetMessage().c_str());
+ } else {
+ ASSERT_STREQ("(4 -> T0) (3 -> 4) (2 -> 3) (1 -> 2) (0 -> 1) (T0 -> 0)",
+ resolver.GetMessage().c_str());
+ }
}
}
-TEST(ParallelMoveTest, ConstantLast) {
+TYPED_TEST(ParallelMoveTest, ConstantLast) {
ArenaPool pool;
ArenaAllocator allocator(&pool);
- TestParallelMoveResolver resolver(&allocator);
+ TypeParam resolver(&allocator);
HParallelMove* moves = new (&allocator) HParallelMove(&allocator);
moves->AddMove(
Location::ConstantLocation(new (&allocator) HIntConstant(0)),
@@ -157,12 +275,12 @@
ASSERT_STREQ("(1 -> 2) (C -> 0)", resolver.GetMessage().c_str());
}
-TEST(ParallelMoveTest, Pairs) {
+TYPED_TEST(ParallelMoveTest, Pairs) {
ArenaPool pool;
ArenaAllocator allocator(&pool);
{
- TestParallelMoveResolver resolver(&allocator);
+ TypeParam resolver(&allocator);
HParallelMove* moves = new (&allocator) HParallelMove(&allocator);
moves->AddMove(
Location::RegisterLocation(2),
@@ -179,7 +297,7 @@
}
{
- TestParallelMoveResolver resolver(&allocator);
+ TypeParam resolver(&allocator);
HParallelMove* moves = new (&allocator) HParallelMove(&allocator);
moves->AddMove(
Location::RegisterPairLocation(0, 1),
@@ -196,7 +314,7 @@
}
{
- TestParallelMoveResolver resolver(&allocator);
+ TypeParam resolver(&allocator);
HParallelMove* moves = new (&allocator) HParallelMove(&allocator);
moves->AddMove(
Location::RegisterPairLocation(0, 1),
@@ -209,10 +327,14 @@
Primitive::kPrimInt,
nullptr);
resolver.EmitNativeCode(moves);
- ASSERT_STREQ("(0,1 <-> 2,3)", resolver.GetMessage().c_str());
+ if (TestFixture::has_swap) {
+ ASSERT_STREQ("(0,1 <-> 2,3)", resolver.GetMessage().c_str());
+ } else {
+ ASSERT_STREQ("(2 -> T0) (0,1 -> 2,3) (T0 -> 0)", resolver.GetMessage().c_str());
+ }
}
{
- TestParallelMoveResolver resolver(&allocator);
+ TypeParam resolver(&allocator);
HParallelMove* moves = new (&allocator) HParallelMove(&allocator);
moves->AddMove(
Location::RegisterLocation(2),
@@ -230,10 +352,15 @@
Primitive::kPrimLong,
nullptr);
resolver.EmitNativeCode(moves);
- ASSERT_STREQ("(0,1 <-> 2,3) (7 -> 1) (0 -> 7)", resolver.GetMessage().c_str());
+ if (TestFixture::has_swap) {
+ ASSERT_STREQ("(0,1 <-> 2,3) (7 -> 1) (0 -> 7)", resolver.GetMessage().c_str());
+ } else {
+ ASSERT_STREQ("(0,1 -> T0,T1) (7 -> 1) (2 -> 7) (T0,T1 -> 2,3)",
+ resolver.GetMessage().c_str());
+ }
}
{
- TestParallelMoveResolver resolver(&allocator);
+ TypeParam resolver(&allocator);
HParallelMove* moves = new (&allocator) HParallelMove(&allocator);
moves->AddMove(
Location::RegisterLocation(2),
@@ -251,10 +378,15 @@
Primitive::kPrimInt,
nullptr);
resolver.EmitNativeCode(moves);
- ASSERT_STREQ("(0,1 <-> 2,3) (7 -> 1) (0 -> 7)", resolver.GetMessage().c_str());
+ if (TestFixture::has_swap) {
+ ASSERT_STREQ("(0,1 <-> 2,3) (7 -> 1) (0 -> 7)", resolver.GetMessage().c_str());
+ } else {
+ ASSERT_STREQ("(0,1 -> T0,T1) (7 -> 1) (2 -> 7) (T0,T1 -> 2,3)",
+ resolver.GetMessage().c_str());
+ }
}
{
- TestParallelMoveResolver resolver(&allocator);
+ TypeParam resolver(&allocator);
HParallelMove* moves = new (&allocator) HParallelMove(&allocator);
moves->AddMove(
Location::RegisterPairLocation(0, 1),
@@ -272,10 +404,14 @@
Primitive::kPrimInt,
nullptr);
resolver.EmitNativeCode(moves);
- ASSERT_STREQ("(0,1 <-> 2,3) (7 -> 1) (0 -> 7)", resolver.GetMessage().c_str());
+ if (TestFixture::has_swap) {
+ ASSERT_STREQ("(0,1 <-> 2,3) (7 -> 1) (0 -> 7)", resolver.GetMessage().c_str());
+ } else {
+ ASSERT_STREQ("(7 -> T0) (2 -> 7) (0,1 -> 2,3) (T0 -> 1)", resolver.GetMessage().c_str());
+ }
}
{
- TestParallelMoveResolver resolver(&allocator);
+ TypeParam resolver(&allocator);
HParallelMove* moves = new (&allocator) HParallelMove(&allocator);
moves->AddMove(
Location::RegisterPairLocation(0, 1),
@@ -288,10 +424,14 @@
Primitive::kPrimLong,
nullptr);
resolver.EmitNativeCode(moves);
- ASSERT_STREQ("(2,3 <-> 0,1)", resolver.GetMessage().c_str());
+ if (TestFixture::has_swap) {
+ ASSERT_STREQ("(2,3 <-> 0,1)", resolver.GetMessage().c_str());
+ } else {
+ ASSERT_STREQ("(2,3 -> T0,T1) (0,1 -> 2,3) (T0,T1 -> 0,1)", resolver.GetMessage().c_str());
+ }
}
{
- TestParallelMoveResolver resolver(&allocator);
+ TypeParam resolver(&allocator);
HParallelMove* moves = new (&allocator) HParallelMove(&allocator);
moves->AddMove(
Location::RegisterPairLocation(2, 3),
@@ -304,12 +444,85 @@
Primitive::kPrimLong,
nullptr);
resolver.EmitNativeCode(moves);
- ASSERT_STREQ("(0,1 <-> 2,3)", resolver.GetMessage().c_str());
+ if (TestFixture::has_swap) {
+ ASSERT_STREQ("(0,1 <-> 2,3)", resolver.GetMessage().c_str());
+ } else {
+ ASSERT_STREQ("(0,1 -> T0,T1) (2,3 -> 0,1) (T0,T1 -> 2,3)", resolver.GetMessage().c_str());
+ }
+ }
+}
+
+TYPED_TEST(ParallelMoveTest, MultiCycles) {
+ ArenaPool pool;
+ ArenaAllocator allocator(&pool);
+
+ {
+ TypeParam resolver(&allocator);
+ static constexpr size_t moves[][2] = {{0, 1}, {1, 0}, {2, 3}, {3, 2}};
+ resolver.EmitNativeCode(BuildParallelMove(&allocator, moves, arraysize(moves)));
+ if (TestFixture::has_swap) {
+ ASSERT_STREQ("(1 <-> 0) (3 <-> 2)", resolver.GetMessage().c_str());
+ } else {
+ ASSERT_STREQ("(1 -> T0) (0 -> 1) (T0 -> 0) (3 -> T0) (2 -> 3) (T0 -> 2)",
+ resolver.GetMessage().c_str());
+ }
+ }
+ {
+ TypeParam resolver(&allocator);
+ HParallelMove* moves = new (&allocator) HParallelMove(&allocator);
+ moves->AddMove(
+ Location::RegisterPairLocation(0, 1),
+ Location::RegisterPairLocation(2, 3),
+ Primitive::kPrimLong,
+ nullptr);
+ moves->AddMove(
+ Location::RegisterLocation(2),
+ Location::RegisterLocation(0),
+ Primitive::kPrimInt,
+ nullptr);
+ moves->AddMove(
+ Location::RegisterLocation(3),
+ Location::RegisterLocation(1),
+ Primitive::kPrimInt,
+ nullptr);
+ resolver.EmitNativeCode(moves);
+ if (TestFixture::has_swap) {
+ ASSERT_STREQ("(0,1 <-> 2,3)", resolver.GetMessage().c_str());
+ } else {
+ ASSERT_STREQ("(2 -> T0) (3 -> T1) (0,1 -> 2,3) (T0 -> 0) (T1 -> 1)",
+ resolver.GetMessage().c_str());
+ }
+ }
+ {
+ TypeParam resolver(&allocator);
+ HParallelMove* moves = new (&allocator) HParallelMove(&allocator);
+ moves->AddMove(
+ Location::RegisterLocation(2),
+ Location::RegisterLocation(0),
+ Primitive::kPrimInt,
+ nullptr);
+ moves->AddMove(
+ Location::RegisterLocation(3),
+ Location::RegisterLocation(1),
+ Primitive::kPrimInt,
+ nullptr);
+ moves->AddMove(
+ Location::RegisterPairLocation(0, 1),
+ Location::RegisterPairLocation(2, 3),
+ Primitive::kPrimLong,
+ nullptr);
+ resolver.EmitNativeCode(moves);
+ if (TestFixture::has_swap) {
+ ASSERT_STREQ("(0,1 <-> 2,3)", resolver.GetMessage().c_str());
+ } else {
+ ASSERT_STREQ("(3 -> T0) (0,1 -> T2,T3) (T0 -> 1) (2 -> 0) (T2,T3 -> 2,3)",
+ resolver.GetMessage().c_str());
+ }
}
{
// Test involving registers used in single context and pair context.
- TestParallelMoveResolver resolver(&allocator);
+ TypeParam resolver(&allocator);
HParallelMove* moves = new (&allocator) HParallelMove(&allocator);
moves->AddMove(
Location::RegisterLocation(10),
@@ -327,17 +540,22 @@
Primitive::kPrimLong,
nullptr);
resolver.EmitNativeCode(moves);
- ASSERT_STREQ("(2x32(sp) <-> 10,11) (4,5 <-> 2x32(sp)) (4 -> 5)", resolver.GetMessage().c_str());
+ if (TestFixture::has_swap) {
+ ASSERT_STREQ("(2x32(sp) <-> 10,11) (4,5 <-> 2x32(sp)) (4 -> 5)", resolver.GetMessage().c_str());
+ } else {
+ ASSERT_STREQ("(2x32(sp) -> T0,T1) (4,5 -> 2x32(sp)) (10 -> 5) (T0,T1 -> 10,11)",
+ resolver.GetMessage().c_str());
+ }
}
}
// Test that we do 64bits moves before 32bits moves.
-TEST(ParallelMoveTest, CyclesWith64BitsMoves) {
+TYPED_TEST(ParallelMoveTest, CyclesWith64BitsMoves) {
ArenaPool pool;
ArenaAllocator allocator(&pool);
{
- TestParallelMoveResolver resolver(&allocator);
+ TypeParam resolver(&allocator);
HParallelMove* moves = new (&allocator) HParallelMove(&allocator);
moves->AddMove(
Location::RegisterLocation(0),
@@ -355,11 +573,16 @@
Primitive::kPrimInt,
nullptr);
resolver.EmitNativeCode(moves);
- ASSERT_STREQ("(0 <-> 1) (48(sp) <-> 0)", resolver.GetMessage().c_str());
+ if (TestFixture::has_swap) {
+ ASSERT_STREQ("(0 <-> 1) (48(sp) <-> 0)", resolver.GetMessage().c_str());
+ } else {
+ ASSERT_STREQ("(48(sp) -> T0) (1 -> 48(sp)) (0 -> 1) (T0 -> 0)",
+ resolver.GetMessage().c_str());
+ }
}
{
- TestParallelMoveResolver resolver(&allocator);
+ TypeParam resolver(&allocator);
HParallelMove* moves = new (&allocator) HParallelMove(&allocator);
moves->AddMove(
Location::RegisterPairLocation(0, 1),
@@ -377,7 +600,12 @@
Primitive::kPrimLong,
nullptr);
resolver.EmitNativeCode(moves);
- ASSERT_STREQ("(2x32(sp) <-> 0,1) (2,3 <-> 2x32(sp))", resolver.GetMessage().c_str());
+ if (TestFixture::has_swap) {
+ ASSERT_STREQ("(2x32(sp) <-> 0,1) (2,3 <-> 2x32(sp))", resolver.GetMessage().c_str());
+ } else {
+ ASSERT_STREQ("(2x32(sp) -> T0,T1) (2,3 -> 2x32(sp)) (0,1 -> 2,3) (T0,T1 -> 0,1)",
+ resolver.GetMessage().c_str());
+ }
}
}