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 namespace v8 {
11 namespace internal {
12 namespace compiler {
13
14 // The state of our move interpreter is the mapping of operands to values. Note
15 // that the actual values don't really matter, all we care about is equality.
16 class InterpreterState {
17 public:
ExecuteInParallel(const ParallelMove * moves)18 void ExecuteInParallel(const ParallelMove* moves) {
19 InterpreterState copy(*this);
20 for (const auto m : *moves) {
21 if (!m->IsRedundant()) write(m->destination(), copy.read(m->source()));
22 }
23 }
24
operator ==(const InterpreterState & other) const25 bool operator==(const InterpreterState& other) const {
26 return values_ == other.values_;
27 }
28
operator !=(const InterpreterState & other) const29 bool operator!=(const InterpreterState& other) const {
30 return values_ != other.values_;
31 }
32
33 private:
34 struct Key {
35 bool is_constant;
36 bool is_float;
37 LocationOperand::LocationKind kind;
38 int index;
39
operator <v8::internal::compiler::InterpreterState::Key40 bool operator<(const Key& other) const {
41 if (this->is_constant != other.is_constant) {
42 return this->is_constant;
43 }
44 if (this->is_float != other.is_float) {
45 return this->is_float;
46 }
47 if (this->kind != other.kind) {
48 return this->kind < other.kind;
49 }
50 return this->index < other.index;
51 }
52
operator ==v8::internal::compiler::InterpreterState::Key53 bool operator==(const Key& other) const {
54 return this->is_constant == other.is_constant &&
55 this->kind == other.kind && this->index == other.index;
56 }
57 };
58
59 // Internally, the state is a normalized permutation of (kind,index) pairs.
60 typedef Key Value;
61 typedef std::map<Key, Value> OperandMap;
62
read(const InstructionOperand & op) const63 Value read(const InstructionOperand& op) const {
64 OperandMap::const_iterator it = values_.find(KeyFor(op));
65 return (it == values_.end()) ? ValueFor(op) : it->second;
66 }
67
write(const InstructionOperand & op,Value v)68 void write(const InstructionOperand& op, Value v) {
69 if (v == ValueFor(op)) {
70 values_.erase(KeyFor(op));
71 } else {
72 values_[KeyFor(op)] = v;
73 }
74 }
75
KeyFor(const InstructionOperand & op)76 static Key KeyFor(const InstructionOperand& op) {
77 bool is_constant = op.IsConstant();
78 bool is_float = false;
79 LocationOperand::LocationKind kind;
80 int index;
81 if (!is_constant) {
82 if (op.IsRegister()) {
83 index = LocationOperand::cast(op).GetRegister().code();
84 } else if (op.IsDoubleRegister()) {
85 index = LocationOperand::cast(op).GetDoubleRegister().code();
86 } else {
87 index = LocationOperand::cast(op).index();
88 }
89 is_float = IsFloatingPoint(LocationOperand::cast(op).representation());
90 kind = LocationOperand::cast(op).location_kind();
91 } else {
92 index = ConstantOperand::cast(op).virtual_register();
93 kind = LocationOperand::REGISTER;
94 }
95 Key key = {is_constant, is_float, kind, index};
96 return key;
97 }
98
ValueFor(const InstructionOperand & op)99 static Value ValueFor(const InstructionOperand& op) { return KeyFor(op); }
100
FromKey(Key key)101 static InstructionOperand FromKey(Key key) {
102 if (key.is_constant) {
103 return ConstantOperand(key.index);
104 }
105 return AllocatedOperand(
106 key.kind,
107 v8::internal::compiler::InstructionSequence::DefaultRepresentation(),
108 key.index);
109 }
110
operator <<(std::ostream & os,const InterpreterState & is)111 friend std::ostream& operator<<(std::ostream& os,
112 const InterpreterState& is) {
113 for (OperandMap::const_iterator it = is.values_.begin();
114 it != is.values_.end(); ++it) {
115 if (it != is.values_.begin()) os << " ";
116 InstructionOperand source = FromKey(it->first);
117 InstructionOperand destination = FromKey(it->second);
118 MoveOperands mo(source, destination);
119 PrintableMoveOperands pmo = {
120 RegisterConfiguration::ArchDefault(RegisterConfiguration::TURBOFAN),
121 &mo};
122 os << pmo;
123 }
124 return os;
125 }
126
127 OperandMap values_;
128 };
129
130
131 // An abstract interpreter for moves, swaps and parallel moves.
132 class MoveInterpreter : public GapResolver::Assembler {
133 public:
MoveInterpreter(Zone * zone)134 explicit MoveInterpreter(Zone* zone) : zone_(zone) {}
135
AssembleMove(InstructionOperand * source,InstructionOperand * destination)136 void AssembleMove(InstructionOperand* source,
137 InstructionOperand* destination) override {
138 ParallelMove* moves = new (zone_) ParallelMove(zone_);
139 moves->AddMove(*source, *destination);
140 state_.ExecuteInParallel(moves);
141 }
142
AssembleSwap(InstructionOperand * source,InstructionOperand * destination)143 void AssembleSwap(InstructionOperand* source,
144 InstructionOperand* destination) override {
145 ParallelMove* moves = new (zone_) ParallelMove(zone_);
146 moves->AddMove(*source, *destination);
147 moves->AddMove(*destination, *source);
148 state_.ExecuteInParallel(moves);
149 }
150
AssembleParallelMove(const ParallelMove * moves)151 void AssembleParallelMove(const ParallelMove* moves) {
152 state_.ExecuteInParallel(moves);
153 }
154
state() const155 InterpreterState state() const { return state_; }
156
157 private:
158 Zone* const zone_;
159 InterpreterState state_;
160 };
161
162
163 class ParallelMoveCreator : public HandleAndZoneScope {
164 public:
ParallelMoveCreator()165 ParallelMoveCreator() : rng_(CcTest::random_number_generator()) {}
166
Create(int size)167 ParallelMove* Create(int size) {
168 ParallelMove* parallel_move = new (main_zone()) ParallelMove(main_zone());
169 std::set<InstructionOperand, CompareOperandModuloType> seen;
170 for (int i = 0; i < size; ++i) {
171 MoveOperands mo(CreateRandomOperand(true), CreateRandomOperand(false));
172 if (!mo.IsRedundant() && seen.find(mo.destination()) == seen.end()) {
173 parallel_move->AddMove(mo.source(), mo.destination());
174 seen.insert(mo.destination());
175 }
176 }
177 return parallel_move;
178 }
179
180 private:
RandomRepresentation()181 MachineRepresentation RandomRepresentation() {
182 int index = rng_->NextInt(3);
183 switch (index) {
184 case 0:
185 return MachineRepresentation::kWord32;
186 case 1:
187 return MachineRepresentation::kWord64;
188 case 2:
189 return MachineRepresentation::kTagged;
190 }
191 UNREACHABLE();
192 return MachineRepresentation::kNone;
193 }
194
RandomDoubleRepresentation()195 MachineRepresentation RandomDoubleRepresentation() {
196 int index = rng_->NextInt(2);
197 if (index == 0) return MachineRepresentation::kFloat64;
198 return MachineRepresentation::kFloat32;
199 }
200
CreateRandomOperand(bool is_source)201 InstructionOperand CreateRandomOperand(bool is_source) {
202 int index = rng_->NextInt(7);
203 // destination can't be Constant.
204 switch (rng_->NextInt(is_source ? 7 : 6)) {
205 case 0:
206 return AllocatedOperand(LocationOperand::STACK_SLOT,
207 RandomRepresentation(), index);
208 case 1:
209 return AllocatedOperand(LocationOperand::STACK_SLOT,
210 RandomDoubleRepresentation(), index);
211 case 2:
212 return AllocatedOperand(LocationOperand::REGISTER,
213 RandomRepresentation(), index);
214 case 3:
215 return AllocatedOperand(LocationOperand::REGISTER,
216 RandomDoubleRepresentation(), index);
217 case 4:
218 return ExplicitOperand(
219 LocationOperand::REGISTER, RandomRepresentation(),
220 RegisterConfiguration::ArchDefault(RegisterConfiguration::TURBOFAN)
221 ->GetAllocatableGeneralCode(1));
222 case 5:
223 return ExplicitOperand(
224 LocationOperand::STACK_SLOT, RandomRepresentation(),
225 RegisterConfiguration::ArchDefault(RegisterConfiguration::TURBOFAN)
226 ->GetAllocatableGeneralCode(index));
227 case 6:
228 return ConstantOperand(index);
229 }
230 UNREACHABLE();
231 return InstructionOperand();
232 }
233
234 private:
235 v8::base::RandomNumberGenerator* rng_;
236 };
237
238
TEST(FuzzResolver)239 TEST(FuzzResolver) {
240 ParallelMoveCreator pmc;
241 for (int size = 0; size < 20; ++size) {
242 for (int repeat = 0; repeat < 50; ++repeat) {
243 ParallelMove* pm = pmc.Create(size);
244
245 // Note: The gap resolver modifies the ParallelMove, so interpret first.
246 MoveInterpreter mi1(pmc.main_zone());
247 mi1.AssembleParallelMove(pm);
248
249 MoveInterpreter mi2(pmc.main_zone());
250 GapResolver resolver(&mi2);
251 resolver.Resolve(pm);
252
253 CHECK(mi1.state() == mi2.state());
254 }
255 }
256 }
257
258 } // namespace compiler
259 } // namespace internal
260 } // namespace v8
261