Index: test/cctest/compiler/compiler/test-gap-resolver.cc |
diff --git a/test/cctest/compiler/compiler/test-gap-resolver.cc b/test/cctest/compiler/compiler/test-gap-resolver.cc |
new file mode 100644 |
index 0000000000000000000000000000000000000000..60a476286157ce4be31d58a6be155feb2495c7cd |
--- /dev/null |
+++ b/test/cctest/compiler/compiler/test-gap-resolver.cc |
@@ -0,0 +1,172 @@ |
+// Copyright 2014 the V8 project authors. All rights reserved. |
+// Use of this source code is governed by a BSD-style license that can be |
+// found in the LICENSE file. |
+ |
+#include "src/compiler/gap-resolver.h" |
+ |
+#include "src/base/utils/random-number-generator.h" |
+#include "test/cctest/cctest.h" |
+ |
+using namespace v8::internal; |
+using namespace v8::internal::compiler; |
+ |
+// The state of our move interpreter is the mapping of operands to values. Note |
+// that the actual values don't really matter, all we care about is equality. |
+class InterpreterState { |
+ public: |
+ typedef std::vector<MoveOperands> Moves; |
+ |
+ void ExecuteInParallel(Moves moves) { |
+ InterpreterState copy(*this); |
+ for (Moves::iterator it = moves.begin(); it != moves.end(); ++it) { |
+ if (!it->IsRedundant()) write(it->destination(), copy.read(it->source())); |
+ } |
+ } |
+ |
+ bool operator==(const InterpreterState& other) const { |
+ return values_ == other.values_; |
+ } |
+ |
+ bool operator!=(const InterpreterState& other) const { |
+ return values_ != other.values_; |
+ } |
+ |
+ private: |
+ // Internally, the state is a normalized permutation of (kind,index) pairs. |
+ typedef std::pair<InstructionOperand::Kind, int> Key; |
+ typedef Key Value; |
+ typedef std::map<Key, Value> OperandMap; |
+ |
+ Value read(const InstructionOperand* op) const { |
+ OperandMap::const_iterator it = values_.find(KeyFor(op)); |
+ return (it == values_.end()) ? ValueFor(op) : it->second; |
+ } |
+ |
+ void write(const InstructionOperand* op, Value v) { |
+ if (v == ValueFor(op)) { |
+ values_.erase(KeyFor(op)); |
+ } else { |
+ values_[KeyFor(op)] = v; |
+ } |
+ } |
+ |
+ static Key KeyFor(const InstructionOperand* op) { |
+ return Key(op->kind(), op->index()); |
+ } |
+ |
+ static Value ValueFor(const InstructionOperand* op) { |
+ return Value(op->kind(), op->index()); |
+ } |
+ |
+ friend OStream& operator<<(OStream& os, const InterpreterState& is) { |
+ for (OperandMap::const_iterator it = is.values_.begin(); |
+ it != is.values_.end(); ++it) { |
+ if (it != is.values_.begin()) os << " "; |
+ InstructionOperand source(it->first.first, it->first.second); |
+ InstructionOperand destination(it->second.first, it->second.second); |
+ os << MoveOperands(&source, &destination); |
+ } |
+ return os; |
+ } |
+ |
+ OperandMap values_; |
+}; |
+ |
+ |
+// An abstract interpreter for moves, swaps and parallel moves. |
+class MoveInterpreter : public GapResolver::Assembler { |
+ public: |
+ virtual void AssembleMove(InstructionOperand* source, |
+ InstructionOperand* destination) V8_OVERRIDE { |
+ InterpreterState::Moves moves; |
+ moves.push_back(MoveOperands(source, destination)); |
+ state_.ExecuteInParallel(moves); |
+ } |
+ |
+ virtual void AssembleSwap(InstructionOperand* source, |
+ InstructionOperand* destination) V8_OVERRIDE { |
+ InterpreterState::Moves moves; |
+ moves.push_back(MoveOperands(source, destination)); |
+ moves.push_back(MoveOperands(destination, source)); |
+ state_.ExecuteInParallel(moves); |
+ } |
+ |
+ void AssembleParallelMove(const ParallelMove* pm) { |
+ InterpreterState::Moves moves(pm->move_operands()->begin(), |
+ pm->move_operands()->end()); |
+ state_.ExecuteInParallel(moves); |
+ } |
+ |
+ InterpreterState state() const { return state_; } |
+ |
+ private: |
+ InterpreterState state_; |
+}; |
+ |
+ |
+class ParallelMoveCreator : public HandleAndZoneScope { |
+ public: |
+ ParallelMoveCreator() : rng_(CcTest::random_number_generator()) {} |
+ |
+ ParallelMove* Create(int size) { |
+ ParallelMove* parallel_move = new (main_zone()) ParallelMove(main_zone()); |
+ std::set<InstructionOperand*, InstructionOperandComparator> seen; |
+ for (int i = 0; i < size; ++i) { |
+ MoveOperands mo(CreateRandomOperand(), CreateRandomOperand()); |
+ if (!mo.IsRedundant() && seen.find(mo.destination()) == seen.end()) { |
+ parallel_move->AddMove(mo.source(), mo.destination(), main_zone()); |
+ seen.insert(mo.destination()); |
+ } |
+ } |
+ return parallel_move; |
+ } |
+ |
+ private: |
+ struct InstructionOperandComparator { |
+ bool operator()(const InstructionOperand* x, const InstructionOperand* y) { |
+ return (x->kind() < y->kind()) || |
+ (x->kind() == y->kind() && x->index() < y->index()); |
+ } |
+ }; |
+ |
+ InstructionOperand* CreateRandomOperand() { |
+ int index = rng_->NextInt(6); |
+ switch (rng_->NextInt(5)) { |
+ case 0: |
+ return ConstantOperand::Create(index, main_zone()); |
+ case 1: |
+ return StackSlotOperand::Create(index, main_zone()); |
+ case 2: |
+ return DoubleStackSlotOperand::Create(index, main_zone()); |
+ case 3: |
+ return RegisterOperand::Create(index, main_zone()); |
+ case 4: |
+ return DoubleRegisterOperand::Create(index, main_zone()); |
+ } |
+ UNREACHABLE(); |
+ return NULL; |
+ } |
+ |
+ private: |
+ v8::base::RandomNumberGenerator* rng_; |
+}; |
+ |
+ |
+TEST(FuzzResolver) { |
+ ParallelMoveCreator pmc; |
+ for (int size = 0; size < 20; ++size) { |
+ for (int repeat = 0; repeat < 50; ++repeat) { |
+ ParallelMove* pm = pmc.Create(size); |
+ |
+ // Note: The gap resolver modifies the ParallelMove, so interpret first. |
+ MoveInterpreter mi1; |
+ mi1.AssembleParallelMove(pm); |
+ |
+ MoveInterpreter mi2; |
+ GapResolver resolver(&mi2); |
+ resolver.Resolve(pm); |
+ |
+ CHECK(mi1.state() == mi2.state()); |
+ } |
+ } |
+} |