1 // Copyright 2014 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "src/compiler/gap-resolver.h" 6 7 #include "src/base/utils/random-number-generator.h" 8 #include "test/cctest/cctest.h" 9 10 using namespace v8::internal; 11 using namespace v8::internal::compiler; 12 13 // The state of our move interpreter is the mapping of operands to values. Note 14 // that the actual values don't really matter, all we care about is equality. 15 class InterpreterState { 16 public: 17 typedef std::vector<MoveOperands> Moves; 18 19 void ExecuteInParallel(Moves moves) { 20 InterpreterState copy(*this); 21 for (Moves::iterator it = moves.begin(); it != moves.end(); ++it) { 22 if (!it->IsRedundant()) write(it->destination(), copy.read(it->source())); 23 } 24 } 25 26 bool operator==(const InterpreterState& other) const { 27 return values_ == other.values_; 28 } 29 30 bool operator!=(const InterpreterState& other) const { 31 return values_ != other.values_; 32 } 33 34 private: 35 // Internally, the state is a normalized permutation of (kind,index) pairs. 36 typedef std::pair<InstructionOperand::Kind, int> Key; 37 typedef Key Value; 38 typedef std::map<Key, Value> OperandMap; 39 40 Value read(const InstructionOperand* op) const { 41 OperandMap::const_iterator it = values_.find(KeyFor(op)); 42 return (it == values_.end()) ? ValueFor(op) : it->second; 43 } 44 45 void write(const InstructionOperand* op, Value v) { 46 if (v == ValueFor(op)) { 47 values_.erase(KeyFor(op)); 48 } else { 49 values_[KeyFor(op)] = v; 50 } 51 } 52 53 static Key KeyFor(const InstructionOperand* op) { 54 return Key(op->kind(), op->index()); 55 } 56 57 static Value ValueFor(const InstructionOperand* op) { 58 return Value(op->kind(), op->index()); 59 } 60 61 friend OStream& operator<<(OStream& os, const InterpreterState& is) { 62 for (OperandMap::const_iterator it = is.values_.begin(); 63 it != is.values_.end(); ++it) { 64 if (it != is.values_.begin()) os << " "; 65 InstructionOperand source(it->first.first, it->first.second); 66 InstructionOperand destination(it->second.first, it->second.second); 67 os << MoveOperands(&source, &destination); 68 } 69 return os; 70 } 71 72 OperandMap values_; 73 }; 74 75 76 // An abstract interpreter for moves, swaps and parallel moves. 77 class MoveInterpreter : public GapResolver::Assembler { 78 public: 79 virtual void AssembleMove(InstructionOperand* source, 80 InstructionOperand* destination) OVERRIDE { 81 InterpreterState::Moves moves; 82 moves.push_back(MoveOperands(source, destination)); 83 state_.ExecuteInParallel(moves); 84 } 85 86 virtual void AssembleSwap(InstructionOperand* source, 87 InstructionOperand* destination) OVERRIDE { 88 InterpreterState::Moves moves; 89 moves.push_back(MoveOperands(source, destination)); 90 moves.push_back(MoveOperands(destination, source)); 91 state_.ExecuteInParallel(moves); 92 } 93 94 void AssembleParallelMove(const ParallelMove* pm) { 95 InterpreterState::Moves moves(pm->move_operands()->begin(), 96 pm->move_operands()->end()); 97 state_.ExecuteInParallel(moves); 98 } 99 100 InterpreterState state() const { return state_; } 101 102 private: 103 InterpreterState state_; 104 }; 105 106 107 class ParallelMoveCreator : public HandleAndZoneScope { 108 public: 109 ParallelMoveCreator() : rng_(CcTest::random_number_generator()) {} 110 111 ParallelMove* Create(int size) { 112 ParallelMove* parallel_move = new (main_zone()) ParallelMove(main_zone()); 113 std::set<InstructionOperand*, InstructionOperandComparator> seen; 114 for (int i = 0; i < size; ++i) { 115 MoveOperands mo(CreateRandomOperand(), CreateRandomOperand()); 116 if (!mo.IsRedundant() && seen.find(mo.destination()) == seen.end()) { 117 parallel_move->AddMove(mo.source(), mo.destination(), main_zone()); 118 seen.insert(mo.destination()); 119 } 120 } 121 return parallel_move; 122 } 123 124 private: 125 struct InstructionOperandComparator { 126 bool operator()(const InstructionOperand* x, 127 const InstructionOperand* y) const { 128 return (x->kind() < y->kind()) || 129 (x->kind() == y->kind() && x->index() < y->index()); 130 } 131 }; 132 133 InstructionOperand* CreateRandomOperand() { 134 int index = rng_->NextInt(6); 135 switch (rng_->NextInt(5)) { 136 case 0: 137 return ConstantOperand::Create(index, main_zone()); 138 case 1: 139 return StackSlotOperand::Create(index, main_zone()); 140 case 2: 141 return DoubleStackSlotOperand::Create(index, main_zone()); 142 case 3: 143 return RegisterOperand::Create(index, main_zone()); 144 case 4: 145 return DoubleRegisterOperand::Create(index, main_zone()); 146 } 147 UNREACHABLE(); 148 return NULL; 149 } 150 151 private: 152 v8::base::RandomNumberGenerator* rng_; 153 }; 154 155 156 TEST(FuzzResolver) { 157 ParallelMoveCreator pmc; 158 for (int size = 0; size < 20; ++size) { 159 for (int repeat = 0; repeat < 50; ++repeat) { 160 ParallelMove* pm = pmc.Create(size); 161 162 // Note: The gap resolver modifies the ParallelMove, so interpret first. 163 MoveInterpreter mi1; 164 mi1.AssembleParallelMove(pm); 165 166 MoveInterpreter mi2; 167 GapResolver resolver(&mi2); 168 resolver.Resolve(pm); 169 170 CHECK(mi1.state() == mi2.state()); 171 } 172 } 173 } 174