diff options
| -rw-r--r-- | build/Android.gtest.mk | 1 | ||||
| -rw-r--r-- | compiler/Android.mk | 2 | ||||
| -rw-r--r-- | compiler/optimizing/code_generator.h | 262 | ||||
| -rw-r--r-- | compiler/optimizing/code_generator_arm.cc | 8 | ||||
| -rw-r--r-- | compiler/optimizing/code_generator_x86.cc | 8 | ||||
| -rw-r--r-- | compiler/optimizing/nodes.cc | 11 | ||||
| -rw-r--r-- | compiler/optimizing/nodes.h | 85 | ||||
| -rw-r--r-- | compiler/optimizing/parallel_move_resolver.cc | 150 | ||||
| -rw-r--r-- | compiler/optimizing/parallel_move_resolver.h | 63 | ||||
| -rw-r--r-- | compiler/optimizing/parallel_move_test.cc | 128 |
10 files changed, 457 insertions, 261 deletions
diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk index 952f79a489..c5457c25b0 100644 --- a/build/Android.gtest.mk +++ b/build/Android.gtest.mk @@ -82,6 +82,7 @@ COMPILER_GTEST_COMMON_SRC_FILES := \ compiler/optimizing/linearize_test.cc \ compiler/optimizing/liveness_test.cc \ compiler/optimizing/live_ranges_test.cc \ + compiler/optimizing/parallel_move_test.cc \ compiler/optimizing/pretty_printer_test.cc \ compiler/optimizing/ssa_test.cc \ compiler/output_stream_test.cc \ diff --git a/compiler/Android.mk b/compiler/Android.mk index cb900eac61..d9417fc825 100644 --- a/compiler/Android.mk +++ b/compiler/Android.mk @@ -83,8 +83,10 @@ LIBART_COMPILER_SRC_FILES := \ optimizing/code_generator_arm.cc \ optimizing/code_generator_x86.cc \ optimizing/graph_visualizer.cc \ + optimizing/locations.cc \ optimizing/nodes.cc \ optimizing/optimizing_compiler.cc \ + optimizing/parallel_move_resolver.cc \ optimizing/ssa_builder.cc \ optimizing/ssa_liveness_analysis.cc \ trampolines/trampoline_compiler.cc \ diff --git a/compiler/optimizing/code_generator.h b/compiler/optimizing/code_generator.h index aafd801eab..e18902ffb2 100644 --- a/compiler/optimizing/code_generator.h +++ b/compiler/optimizing/code_generator.h @@ -20,6 +20,7 @@ #include "base/bit_field.h" #include "globals.h" #include "instruction_set.h" +#include "locations.h" #include "memory_region.h" #include "nodes.h" #include "utils/assembler.h" @@ -46,267 +47,6 @@ struct PcInfo { uintptr_t native_pc; }; -/** - * A Location is an abstraction over the potential location - * of an instruction. It could be in register or stack. - */ -class Location : public ValueObject { - public: - enum Kind { - kInvalid = 0, - kStackSlot = 1, // Word size slot. - kDoubleStackSlot = 2, // 64bit stack slot. - kRegister = 3, - // On 32bits architectures, quick can pass a long where the - // low bits are in the last parameter register, and the high - // bits are in a stack slot. The kQuickParameter kind is for - // handling this special case. - kQuickParameter = 4, - - // Unallocated location represents a location that is not fixed and can be - // allocated by a register allocator. Each unallocated location has - // a policy that specifies what kind of location is suitable. Payload - // contains register allocation policy. - kUnallocated = 5, - }; - - Location() : value_(kInvalid) { - DCHECK(!IsValid()); - } - - Location(const Location& other) : ValueObject(), value_(other.value_) {} - - Location& operator=(const Location& other) { - value_ = other.value_; - return *this; - } - - bool IsValid() const { - return value_ != kInvalid; - } - - // Register locations. - static Location RegisterLocation(ManagedRegister reg) { - return Location(kRegister, reg.RegId()); - } - - bool IsRegister() const { - return GetKind() == kRegister; - } - - ManagedRegister reg() const { - DCHECK(IsRegister()); - return static_cast<ManagedRegister>(GetPayload()); - } - - static uword EncodeStackIndex(intptr_t stack_index) { - DCHECK(-kStackIndexBias <= stack_index); - DCHECK(stack_index < kStackIndexBias); - return static_cast<uword>(kStackIndexBias + stack_index); - } - - static Location StackSlot(intptr_t stack_index) { - uword payload = EncodeStackIndex(stack_index); - Location loc(kStackSlot, payload); - // Ensure that sign is preserved. - DCHECK_EQ(loc.GetStackIndex(), stack_index); - return loc; - } - - bool IsStackSlot() const { - return GetKind() == kStackSlot; - } - - static Location DoubleStackSlot(intptr_t stack_index) { - uword payload = EncodeStackIndex(stack_index); - Location loc(kDoubleStackSlot, payload); - // Ensure that sign is preserved. - DCHECK_EQ(loc.GetStackIndex(), stack_index); - return loc; - } - - bool IsDoubleStackSlot() const { - return GetKind() == kDoubleStackSlot; - } - - intptr_t GetStackIndex() const { - DCHECK(IsStackSlot() || IsDoubleStackSlot()); - // Decode stack index manually to preserve sign. - return GetPayload() - kStackIndexBias; - } - - intptr_t GetHighStackIndex(uintptr_t word_size) const { - DCHECK(IsDoubleStackSlot()); - // Decode stack index manually to preserve sign. - return GetPayload() - kStackIndexBias + word_size; - } - - static Location QuickParameter(uint32_t parameter_index) { - return Location(kQuickParameter, parameter_index); - } - - uint32_t GetQuickParameterIndex() const { - DCHECK(IsQuickParameter()); - return GetPayload(); - } - - bool IsQuickParameter() const { - return GetKind() == kQuickParameter; - } - - arm::ArmManagedRegister AsArm() const; - x86::X86ManagedRegister AsX86() const; - - Kind GetKind() const { - return KindField::Decode(value_); - } - - bool Equals(Location other) const { - return value_ == other.value_; - } - - const char* DebugString() const { - switch (GetKind()) { - case kInvalid: return "?"; - case kRegister: return "R"; - case kStackSlot: return "S"; - case kDoubleStackSlot: return "DS"; - case kQuickParameter: return "Q"; - case kUnallocated: return "U"; - } - return "?"; - } - - // Unallocated locations. - enum Policy { - kAny, - kRequiresRegister, - kSameAsFirstInput, - }; - - bool IsUnallocated() const { - return GetKind() == kUnallocated; - } - - static Location UnallocatedLocation(Policy policy) { - return Location(kUnallocated, PolicyField::Encode(policy)); - } - - // Any free register is suitable to replace this unallocated location. - static Location Any() { - return UnallocatedLocation(kAny); - } - - static Location RequiresRegister() { - return UnallocatedLocation(kRequiresRegister); - } - - // The location of the first input to the instruction will be - // used to replace this unallocated location. - static Location SameAsFirstInput() { - return UnallocatedLocation(kSameAsFirstInput); - } - - Policy GetPolicy() const { - DCHECK(IsUnallocated()); - return PolicyField::Decode(GetPayload()); - } - - uword GetEncoding() const { - return GetPayload(); - } - - private: - // Number of bits required to encode Kind value. - static constexpr uint32_t kBitsForKind = 4; - static constexpr uint32_t kBitsForPayload = kWordSize * kBitsPerByte - kBitsForKind; - - explicit Location(uword value) : value_(value) {} - - Location(Kind kind, uword payload) - : value_(KindField::Encode(kind) | PayloadField::Encode(payload)) {} - - uword GetPayload() const { - return PayloadField::Decode(value_); - } - - typedef BitField<Kind, 0, kBitsForKind> KindField; - typedef BitField<uword, kBitsForKind, kBitsForPayload> PayloadField; - - // Layout for kUnallocated locations payload. - typedef BitField<Policy, 0, 3> PolicyField; - - // Layout for stack slots. - static const intptr_t kStackIndexBias = - static_cast<intptr_t>(1) << (kBitsForPayload - 1); - - // Location either contains kind and payload fields or a tagged handle for - // a constant locations. Values of enumeration Kind are selected in such a - // way that none of them can be interpreted as a kConstant tag. - uword value_; -}; - -/** - * The code generator computes LocationSummary for each instruction so that - * the instruction itself knows what code to generate: where to find the inputs - * and where to place the result. - * - * The intent is to have the code for generating the instruction independent of - * register allocation. A register allocator just has to provide a LocationSummary. - */ -class LocationSummary : public ArenaObject { - public: - explicit LocationSummary(HInstruction* instruction) - : inputs_(instruction->GetBlock()->GetGraph()->GetArena(), instruction->InputCount()), - temps_(instruction->GetBlock()->GetGraph()->GetArena(), 0) { - inputs_.SetSize(instruction->InputCount()); - for (size_t i = 0; i < instruction->InputCount(); i++) { - inputs_.Put(i, Location()); - } - } - - void SetInAt(uint32_t at, Location location) { - inputs_.Put(at, location); - } - - Location InAt(uint32_t at) const { - return inputs_.Get(at); - } - - size_t GetInputCount() const { - return inputs_.Size(); - } - - void SetOut(Location location) { - output_ = Location(location); - } - - void AddTemp(Location location) { - temps_.Add(location); - } - - Location GetTemp(uint32_t at) const { - return temps_.Get(at); - } - - void SetTempAt(uint32_t at, Location location) { - temps_.Put(at, location); - } - - size_t GetTempCount() const { - return temps_.Size(); - } - - Location Out() const { return output_; } - - private: - GrowableArray<Location> inputs_; - GrowableArray<Location> temps_; - Location output_; - - DISALLOW_COPY_AND_ASSIGN(LocationSummary); -}; - class CodeGenerator : public ArenaObject { public: // Compiles the graph to executable instructions. Returns whether the compilation diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc index be512323c0..f1b16a1d4a 100644 --- a/compiler/optimizing/code_generator_arm.cc +++ b/compiler/optimizing/code_generator_arm.cc @@ -793,5 +793,13 @@ void InstructionCodeGeneratorARM::VisitPhi(HPhi* instruction) { LOG(FATAL) << "Unimplemented"; } +void LocationsBuilderARM::VisitParallelMove(HParallelMove* instruction) { + LOG(FATAL) << "Unimplemented"; +} + +void InstructionCodeGeneratorARM::VisitParallelMove(HParallelMove* instruction) { + LOG(FATAL) << "Unimplemented"; +} + } // namespace arm } // namespace art diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc index e4f95c795f..b8b25f9886 100644 --- a/compiler/optimizing/code_generator_x86.cc +++ b/compiler/optimizing/code_generator_x86.cc @@ -813,5 +813,13 @@ void InstructionCodeGeneratorX86::VisitPhi(HPhi* instruction) { LOG(FATAL) << "Unimplemented"; } +void LocationsBuilderX86::VisitParallelMove(HParallelMove* instruction) { + LOG(FATAL) << "Unimplemented"; +} + +void InstructionCodeGeneratorX86::VisitParallelMove(HParallelMove* instruction) { + LOG(FATAL) << "Unimplemented"; +} + } // namespace x86 } // namespace art diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index afaedd7f18..74ba5208c4 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -291,6 +291,17 @@ bool HBasicBlock::Dominates(HBasicBlock* other) const { return false; } +void HBasicBlock::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) { + DCHECK(cursor->AsPhi() == nullptr); + DCHECK(instruction->AsPhi() == nullptr); + instruction->next_ = cursor; + instruction->previous_ = cursor->previous_; + cursor->previous_ = instruction; + if (GetFirstInstruction() == cursor) { + instructions_.first_instruction_ = instruction; + } +} + static void Add(HInstructionList* instruction_list, HBasicBlock* block, HInstruction* instruction) { diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index a2cb1c47ae..476f24e491 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -17,6 +17,7 @@ #ifndef ART_COMPILER_OPTIMIZING_NODES_H_ #define ART_COMPILER_OPTIMIZING_NODES_H_ +#include "locations.h" #include "utils/allocation.h" #include "utils/arena_bit_vector.h" #include "utils/growable_array.h" @@ -315,6 +316,7 @@ class HBasicBlock : public ArenaObject { void AddInstruction(HInstruction* instruction); void RemoveInstruction(HInstruction* instruction); + void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor); void AddPhi(HPhi* phi); void RemovePhi(HPhi* phi); @@ -383,6 +385,7 @@ class HBasicBlock : public ArenaObject { M(NewInstance) \ M(Not) \ M(ParameterValue) \ + M(ParallelMove) \ M(Phi) \ M(Return) \ M(ReturnVoid) \ @@ -1102,6 +1105,88 @@ class HPhi : public HInstruction { DISALLOW_COPY_AND_ASSIGN(HPhi); }; +class MoveOperands : public ArenaObject { + public: + MoveOperands(Location source, Location destination) + : source_(source), destination_(destination) {} + + Location GetSource() const { return source_; } + Location GetDestination() const { return destination_; } + + void SetSource(Location value) { source_ = value; } + void SetDestination(Location value) { destination_ = value; } + + // The parallel move resolver marks moves as "in-progress" by clearing the + // destination (but not the source). + Location MarkPending() { + DCHECK(!IsPending()); + Location dest = destination_; + destination_ = Location::NoLocation(); + return dest; + } + + void ClearPending(Location dest) { + DCHECK(IsPending()); + destination_ = dest; + } + + bool IsPending() const { + DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); + return destination_.IsInvalid() && !source_.IsInvalid(); + } + + // True if this blocks a move from the given location. + bool Blocks(Location loc) const { + return !IsEliminated() && source_.Equals(loc); + } + + // A move is redundant if it's been eliminated, if its source and + // destination are the same, or if its destination is unneeded. + bool IsRedundant() const { + return IsEliminated() || destination_.IsInvalid() || source_.Equals(destination_); + } + + // We clear both operands to indicate move that's been eliminated. + void Eliminate() { + source_ = destination_ = Location::NoLocation(); + } + + bool IsEliminated() const { + DCHECK(!source_.IsInvalid() || destination_.IsInvalid()); + return source_.IsInvalid(); + } + + private: + Location source_; + Location destination_; + + DISALLOW_COPY_AND_ASSIGN(MoveOperands); +}; + +static constexpr size_t kDefaultNumberOfMoves = 4; + +class HParallelMove : public HTemplateInstruction<0> { + public: + explicit HParallelMove(ArenaAllocator* arena) : moves_(arena, kDefaultNumberOfMoves) {} + + void AddMove(MoveOperands* move) { + moves_.Add(move); + } + + MoveOperands* MoveOperandsAt(size_t index) const { + return moves_.Get(index); + } + + size_t NumMoves() const { return moves_.Size(); } + + DECLARE_INSTRUCTION(ParallelMove) + + private: + GrowableArray<MoveOperands*> moves_; + + DISALLOW_COPY_AND_ASSIGN(HParallelMove); +}; + class HGraphVisitor : public ValueObject { public: explicit HGraphVisitor(HGraph* graph) : graph_(graph) { } diff --git a/compiler/optimizing/parallel_move_resolver.cc b/compiler/optimizing/parallel_move_resolver.cc new file mode 100644 index 0000000000..3d2d136ec3 --- /dev/null +++ b/compiler/optimizing/parallel_move_resolver.cc @@ -0,0 +1,150 @@ +/* + * Copyright (C) 2014 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "parallel_move_resolver.h" +#include "nodes.h" +#include "locations.h" + +namespace art { + +void ParallelMoveResolver::EmitNativeCode(HParallelMove* parallel_move) { + DCHECK(moves_.IsEmpty()); + // Build up a worklist of moves. + BuildInitialMoveList(parallel_move); + + for (size_t i = 0; i < moves_.Size(); ++i) { + const MoveOperands& move = *moves_.Get(i); + // Skip constants to perform them last. They don't block other moves + // and skipping such moves with register destinations keeps those + // registers free for the whole algorithm. + if (!move.IsEliminated() && !move.GetSource().IsConstant()) { + PerformMove(i); + } + } + + // Perform the moves with constant sources. + for (size_t i = 0; i < moves_.Size(); ++i) { + const MoveOperands& move = *moves_.Get(i); + if (!move.IsEliminated()) { + DCHECK(move.GetSource().IsConstant()); + EmitMove(i); + } + } + + moves_.Reset(); +} + + +void ParallelMoveResolver::BuildInitialMoveList(HParallelMove* parallel_move) { + // Perform a linear sweep of the moves to add them to the initial list of + // moves to perform, ignoring any move that is redundant (the source is + // the same as the destination, the destination is ignored and + // unallocated, or the move was already eliminated). + for (size_t i = 0; i < parallel_move->NumMoves(); ++i) { + MoveOperands* move = parallel_move->MoveOperandsAt(i); + if (!move->IsRedundant()) { + moves_.Add(move); + } + } +} + + +void ParallelMoveResolver::PerformMove(size_t index) { + // Each call to this function performs a move and deletes it from the move + // graph. We first recursively perform any move blocking this one. We + // mark a move as "pending" on entry to PerformMove in order to detect + // cycles in the move graph. We use operand swaps to resolve cycles, + // which means that a call to PerformMove could change any source operand + // in the move graph. + + DCHECK(!moves_.Get(index)->IsPending()); + DCHECK(!moves_.Get(index)->IsRedundant()); + + // Clear this move's destination to indicate a pending move. The actual + // destination is saved in a stack-allocated local. Recursion may allow + // multiple moves to be pending. + DCHECK(!moves_.Get(index)->GetSource().IsInvalid()); + Location destination = moves_.Get(index)->MarkPending(); + + // Perform a depth-first traversal of the move graph to resolve + // dependencies. Any unperformed, unpending move with a source the same + // as this one's destination blocks this one so recursively perform all + // such moves. + for (size_t i = 0; i < moves_.Size(); ++i) { + const MoveOperands& other_move = *moves_.Get(i); + if (other_move.Blocks(destination) && !other_move.IsPending()) { + // Though PerformMove can change any source operand in the move graph, + // this call cannot create a blocking move via a swap (this loop does + // not miss any). Assume there is a non-blocking move with source A + // and this move is blocked on source B and there is a swap of A and + // B. Then A and B must be involved in the same cycle (or they would + // not be swapped). Since this move's destination is B and there is + // only a single incoming edge to an operand, this move must also be + // involved in the same cycle. In that case, the blocking move will + // be created but will be "pending" when we return from PerformMove. + PerformMove(i); + } + } + MoveOperands* move = moves_.Get(index); + + // We are about to resolve this move and don't need it marked as + // pending, so restore its destination. + move->ClearPending(destination); + + // This move's source may have changed due to swaps to resolve cycles and + // so it may now be the last move in the cycle. If so remove it. + if (move->GetSource().Equals(destination)) { + move->Eliminate(); + return; + } + + // The move may be blocked on a (at most one) pending move, in which case + // we have a cycle. Search for such a blocking move and perform a swap to + // resolve it. + bool do_swap = false; + for (size_t i = 0; i < moves_.Size(); ++i) { + const MoveOperands& other_move = *moves_.Get(i); + if (other_move.Blocks(destination)) { + DCHECK(other_move.IsPending()); + do_swap = true; + break; + } + } + + if (do_swap) { + EmitSwap(index); + // Any unperformed (including pending) move with a source of either + // this move's source or destination needs to have their source + // changed to reflect the state of affairs after the swap. + Location source = move->GetSource(); + Location destination = move->GetDestination(); + move->Eliminate(); + for (size_t i = 0; i < moves_.Size(); ++i) { + const MoveOperands& other_move = *moves_.Get(i); + if (other_move.Blocks(source)) { + moves_.Get(i)->SetSource(destination); + } else if (other_move.Blocks(destination)) { + moves_.Get(i)->SetSource(source); + } + } + } else { + // This move is not blocked. + EmitMove(index); + move->Eliminate(); + } +} + +} // namespace art diff --git a/compiler/optimizing/parallel_move_resolver.h b/compiler/optimizing/parallel_move_resolver.h new file mode 100644 index 0000000000..f652db1095 --- /dev/null +++ b/compiler/optimizing/parallel_move_resolver.h @@ -0,0 +1,63 @@ +/* + * Copyright (C) 2014 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef ART_COMPILER_OPTIMIZING_PARALLEL_MOVE_RESOLVER_H_ +#define ART_COMPILER_OPTIMIZING_PARALLEL_MOVE_RESOLVER_H_ + +#include "utils/allocation.h" +#include "utils/growable_array.h" + +namespace art { + +class HParallelMove; +class MoveOperands; + +/** + * Helper class to resolve a set of parallel moves. Architecture dependent code + * generator must have their own subclass that implements the `EmitMove` and `EmitSwap` + * operations. + */ +class ParallelMoveResolver : public ValueObject { + public: + explicit ParallelMoveResolver(ArenaAllocator* allocator) : moves_(allocator, 32) {} + + // Resolve a set of parallel moves, emitting assembler instructions. + void EmitNativeCode(HParallelMove* parallel_move); + + protected: + // Emit a move. + virtual void EmitMove(size_t index) = 0; + + // Execute a move by emitting a swap of two operands. + virtual void EmitSwap(size_t index) = 0; + + // List of moves not yet resolved. + GrowableArray<MoveOperands*> moves_; + + private: + // Build the initial list of moves. + void BuildInitialMoveList(HParallelMove* parallel_move); + + // Perform the move at the moves_ index in question (possibly requiring + // other moves to satisfy dependencies). + void PerformMove(size_t index); + + DISALLOW_COPY_AND_ASSIGN(ParallelMoveResolver); +}; + +} // namespace art + +#endif // ART_COMPILER_OPTIMIZING_PARALLEL_MOVE_RESOLVER_H_ diff --git a/compiler/optimizing/parallel_move_test.cc b/compiler/optimizing/parallel_move_test.cc new file mode 100644 index 0000000000..88df24d9ac --- /dev/null +++ b/compiler/optimizing/parallel_move_test.cc @@ -0,0 +1,128 @@ +/* + * Copyright (C) 2014 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "nodes.h" +#include "parallel_move_resolver.h" +#include "utils/arena_allocator.h" + +#include "gtest/gtest.h" + +namespace art { + +class TestParallelMoveResolver : public ParallelMoveResolver { + public: + explicit TestParallelMoveResolver(ArenaAllocator* allocator) : ParallelMoveResolver(allocator) {} + + virtual void EmitMove(size_t index) { + MoveOperands* move = moves_.Get(index); + if (!message_.str().empty()) { + message_ << " "; + } + message_ << "(" + << move->GetSource().reg().RegId() + << " -> " + << move->GetDestination().reg().RegId() + << ")"; + } + + virtual void EmitSwap(size_t index) { + MoveOperands* move = moves_.Get(index); + if (!message_.str().empty()) { + message_ << " "; + } + message_ << "(" + << move->GetSource().reg().RegId() + << " <-> " + << move->GetDestination().reg().RegId() + << ")"; + } + + std::string GetMessage() const { + return message_.str(); + } + + private: + std::ostringstream message_; + + + DISALLOW_COPY_AND_ASSIGN(TestParallelMoveResolver); +}; + +static HParallelMove* BuildParallelMove(ArenaAllocator* allocator, + const size_t operands[][2], + size_t number_of_moves) { + HParallelMove* moves = new (allocator) HParallelMove(allocator); + for (size_t i = 0; i < number_of_moves; ++i) { + moves->AddMove(new (allocator) MoveOperands( + Location::RegisterLocation(ManagedRegister(operands[i][0])), + Location::RegisterLocation(ManagedRegister(operands[i][1])))); + } + return moves; +} + +TEST(ParallelMoveTest, Dependency) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + { + TestParallelMoveResolver 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()); + } + + { + TestParallelMoveResolver 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()); + } +} + +TEST(ParallelMoveTest, Swap) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + + { + TestParallelMoveResolver 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()); + } + + { + TestParallelMoveResolver 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()); + } + + { + TestParallelMoveResolver resolver(&allocator); + static constexpr size_t moves[][2] = {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 1}}; + resolver.EmitNativeCode(BuildParallelMove(&allocator, moves, arraysize(moves))); + ASSERT_STREQ("(4 <-> 1) (3 <-> 4) (2 <-> 3) (0 -> 1)", resolver.GetMessage().c_str()); + } + + { + TestParallelMoveResolver resolver(&allocator); + static constexpr size_t moves[][2] = {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 1}, {5, 4}}; + resolver.EmitNativeCode(BuildParallelMove(&allocator, moves, arraysize(moves))); + ASSERT_STREQ("(4 <-> 1) (3 <-> 4) (2 <-> 3) (0 -> 1) (5 -> 4)", resolver.GetMessage().c_str()); + } +} + +} // namespace art |