From ad4450e5c3ffaa9566216cc6fafbf5c11186c467 Mon Sep 17 00:00:00 2001 From: Zheng Xu Date: Fri, 17 Apr 2015 18:48:56 +0800 Subject: 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 --- compiler/optimizing/parallel_move_test.cc | 344 +++++++++++++++++++++++++----- 1 file changed, 286 insertions(+), 58 deletions(-) (limited to 'compiler/optimizing/parallel_move_test.cc') diff --git a/compiler/optimizing/parallel_move_test.cc b/compiler/optimizing/parallel_move_test.cc index 95cca5172b..f8f70105cf 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) {} - - 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; - } +constexpr int kScratchRegisterStartIndexForTest = 100; + +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 @@ class TestParallelMoveResolver : public ParallelMoveResolver { message_ << " "; } message_ << "("; - Dump(move->GetSource()); + DumpLocationForTest(message_, move->GetSource()); message_ << " -> "; - Dump(move->GetDestination()); + DumpLocationForTest(message_, move->GetDestination()); message_ << ")"; } @@ -59,9 +73,9 @@ class TestParallelMoveResolver : public ParallelMoveResolver { message_ << " "; } message_ << "("; - Dump(move->GetSource()); + DumpLocationForTest(message_, move->GetSource()); message_ << " <-> "; - Dump(move->GetDestination()); + DumpLocationForTest(message_, move->GetDestination()); message_ << ")"; } @@ -76,7 +90,64 @@ class TestParallelMoveResolver : public ParallelMoveResolver { 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 @@ static HParallelMove* BuildParallelMove(ArenaAllocator* allocator, return moves; } -TEST(ParallelMoveTest, Dependency) { +template +class ParallelMoveTest : public ::testing::Test { + public: + static const bool has_swap; +}; + +template<> const bool ParallelMoveTest::has_swap = true; +template<> const bool ParallelMoveTest::has_swap = false; + +typedef ::testing::Types + 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()); + } + } + + { + 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()); + } } { - TestParallelMoveResolver resolver(&allocator); + 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 @@ TEST(ParallelMoveTest, ConstantLast) { 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 @@ TEST(ParallelMoveTest, Pairs) { } { - TestParallelMoveResolver resolver(&allocator); + TypeParam resolver(&allocator); HParallelMove* moves = new (&allocator) HParallelMove(&allocator); moves->AddMove( Location::RegisterPairLocation(0, 1), @@ -196,7 +314,7 @@ TEST(ParallelMoveTest, Pairs) { } { - TestParallelMoveResolver resolver(&allocator); + TypeParam resolver(&allocator); HParallelMove* moves = new (&allocator) HParallelMove(&allocator); moves->AddMove( Location::RegisterPairLocation(0, 1), @@ -209,10 +327,14 @@ TEST(ParallelMoveTest, Pairs) { 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 @@ TEST(ParallelMoveTest, Pairs) { 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 @@ TEST(ParallelMoveTest, Pairs) { 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 @@ TEST(ParallelMoveTest, Pairs) { 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 @@ TEST(ParallelMoveTest, Pairs) { 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 @@ TEST(ParallelMoveTest, Pairs) { 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 @@ TEST(ParallelMoveTest, Pairs) { 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 @@ TEST(ParallelMoveTest, CyclesWith64BitsMoves) { 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 @@ TEST(ParallelMoveTest, CyclesWith64BitsMoves) { 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()); + } } } -- cgit v1.2.3-59-g8ed1b