Line data Source code
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 : const auto GetRegConfig = RegisterConfiguration::Default;
15 :
16 : // Fragments the given FP operand into an equivalent set of FP operands to
17 : // simplify ParallelMove equivalence testing.
18 0 : void GetCanonicalOperands(const InstructionOperand& op,
19 : std::vector<InstructionOperand>* fragments) {
20 0 : CHECK(!kSimpleFPAliasing);
21 : CHECK(op.IsFPLocationOperand());
22 : const LocationOperand& loc = LocationOperand::cast(op);
23 : MachineRepresentation rep = loc.representation();
24 : int base = -1;
25 : int aliases = GetRegConfig()->GetAliases(
26 : rep, 0, MachineRepresentation::kFloat32, &base);
27 : CHECK_LT(0, aliases);
28 : CHECK_GE(4, aliases);
29 : int index = -1;
30 : int step = 1;
31 : if (op.IsFPRegister()) {
32 : index = loc.register_code() * aliases;
33 : } else {
34 : index = loc.index();
35 : step = -1;
36 : }
37 : for (int i = 0; i < aliases; i++) {
38 : fragments->push_back(AllocatedOperand(loc.location_kind(),
39 : MachineRepresentation::kFloat32,
40 : index + i * step));
41 : }
42 : }
43 :
44 : // The state of our move interpreter is the mapping of operands to values. Note
45 : // that the actual values don't really matter, all we care about is equality.
46 : class InterpreterState {
47 : public:
48 365710 : void ExecuteInParallel(const ParallelMove* moves) {
49 : InterpreterState copy(*this);
50 1444390 : for (const auto m : *moves) {
51 712970 : CHECK(!m->IsRedundant());
52 712970 : const InstructionOperand& src = m->source();
53 712970 : const InstructionOperand& dst = m->destination();
54 : if (!kSimpleFPAliasing && src.IsFPLocationOperand() &&
55 : dst.IsFPLocationOperand()) {
56 : // Canonicalize FP location-location moves by fragmenting them into
57 : // an equivalent sequence of float32 moves, to simplify state
58 : // equivalence testing.
59 : std::vector<InstructionOperand> src_fragments;
60 : GetCanonicalOperands(src, &src_fragments);
61 : CHECK(!src_fragments.empty());
62 : std::vector<InstructionOperand> dst_fragments;
63 : GetCanonicalOperands(dst, &dst_fragments);
64 : CHECK_EQ(src_fragments.size(), dst_fragments.size());
65 :
66 : for (size_t i = 0; i < src_fragments.size(); ++i) {
67 : write(dst_fragments[i], copy.read(src_fragments[i]));
68 : }
69 : continue;
70 : }
71 : // All other moves.
72 712970 : write(dst, copy.read(src));
73 : }
74 365710 : }
75 :
76 20000 : bool operator==(const InterpreterState& other) const {
77 20000 : return values_ == other.values_;
78 : }
79 :
80 : private:
81 : // struct for mapping operands to a unique value, that makes it easier to
82 : // detect illegal parallel moves, and to evaluate moves for equivalence. This
83 : // is a one way transformation. All general register and slot operands are
84 : // mapped to the default representation. FP registers and slots are mapped to
85 : // float64 except on architectures with non-simple FP register aliasing, where
86 : // the actual representation is used.
87 : struct Key {
88 : bool is_constant;
89 : MachineRepresentation rep;
90 : LocationOperand::LocationKind kind;
91 : int index;
92 :
93 : bool operator<(const Key& other) const {
94 5771210 : if (this->is_constant != other.is_constant) {
95 : return this->is_constant;
96 : }
97 5437250 : if (this->rep != other.rep) {
98 1112205 : return this->rep < other.rep;
99 : }
100 4325045 : if (this->kind != other.kind) {
101 1239630 : return this->kind < other.kind;
102 : }
103 3085415 : return this->index < other.index;
104 : }
105 :
106 : bool operator==(const Key& other) const {
107 3961190 : return this->is_constant == other.is_constant && this->rep == other.rep &&
108 3650450 : this->kind == other.kind && this->index == other.index;
109 : }
110 : };
111 :
112 : // Internally, the state is a normalized permutation of Value pairs.
113 : typedef Key Value;
114 : typedef std::map<Key, Value> OperandMap;
115 :
116 712970 : Value read(const InstructionOperand& op) const {
117 1425940 : OperandMap::const_iterator it = values_.find(KeyFor(op));
118 721805 : return (it == values_.end()) ? ValueFor(op) : it->second;
119 : }
120 :
121 712970 : void write(const InstructionOperand& dst, Value v) {
122 712970 : if (v == ValueFor(dst)) {
123 0 : values_.erase(KeyFor(dst));
124 : } else {
125 712970 : values_[KeyFor(dst)] = v;
126 : }
127 712970 : }
128 :
129 2843045 : static Key KeyFor(const InstructionOperand& op) {
130 : bool is_constant = op.IsConstant();
131 : MachineRepresentation rep =
132 : v8::internal::compiler::InstructionSequence::DefaultRepresentation();
133 : LocationOperand::LocationKind kind;
134 : int index;
135 2843045 : if (!is_constant) {
136 : const LocationOperand& loc_op = LocationOperand::cast(op);
137 : // Preserve FP representation when FP register aliasing is complex.
138 : // Otherwise, canonicalize to kFloat64.
139 2537545 : if (IsFloatingPoint(loc_op.representation())) {
140 : rep = kSimpleFPAliasing ? MachineRepresentation::kFloat64
141 : : loc_op.representation();
142 : }
143 2537545 : if (loc_op.IsAnyRegister()) {
144 : index = loc_op.register_code();
145 : } else {
146 : index = loc_op.index();
147 : }
148 : kind = loc_op.location_kind();
149 : } else {
150 : index = ConstantOperand::cast(op).virtual_register();
151 : kind = LocationOperand::REGISTER;
152 : }
153 2843045 : Key key = {is_constant, rep, kind, index};
154 2843045 : return key;
155 : }
156 :
157 1417105 : static Value ValueFor(const InstructionOperand& op) { return KeyFor(op); }
158 :
159 : static InstructionOperand FromKey(Key key) {
160 : if (key.is_constant) {
161 : return ConstantOperand(key.index);
162 : }
163 : return AllocatedOperand(key.kind, key.rep, key.index);
164 : }
165 :
166 : friend std::ostream& operator<<(std::ostream& os,
167 : const InterpreterState& is) {
168 : for (OperandMap::const_iterator it = is.values_.begin();
169 : it != is.values_.end(); ++it) {
170 : if (it != is.values_.begin()) os << " ";
171 : InstructionOperand source = FromKey(it->second);
172 : InstructionOperand destination = FromKey(it->first);
173 : MoveOperands mo(source, destination);
174 : PrintableMoveOperands pmo = {GetRegConfig(), &mo};
175 : os << pmo;
176 : }
177 : return os;
178 : }
179 :
180 : OperandMap values_;
181 : };
182 :
183 : // An abstract interpreter for moves, swaps and parallel moves.
184 40000 : class MoveInterpreter : public GapResolver::Assembler {
185 : public:
186 40000 : explicit MoveInterpreter(Zone* zone) : zone_(zone) {}
187 :
188 333080 : void AssembleMove(InstructionOperand* source,
189 : InstructionOperand* destination) override {
190 666160 : ParallelMove* moves = new (zone_) ParallelMove(zone_);
191 : moves->AddMove(*source, *destination);
192 333080 : state_.ExecuteInParallel(moves);
193 333080 : }
194 :
195 12630 : void AssembleSwap(InstructionOperand* source,
196 : InstructionOperand* destination) override {
197 25260 : ParallelMove* moves = new (zone_) ParallelMove(zone_);
198 : moves->AddMove(*source, *destination);
199 : moves->AddMove(*destination, *source);
200 12630 : state_.ExecuteInParallel(moves);
201 12630 : }
202 :
203 : void AssembleParallelMove(const ParallelMove* moves) {
204 20000 : state_.ExecuteInParallel(moves);
205 : }
206 :
207 : InterpreterState state() const { return state_; }
208 :
209 : private:
210 : Zone* const zone_;
211 : InterpreterState state_;
212 : };
213 :
214 :
215 5 : class ParallelMoveCreator : public HandleAndZoneScope {
216 : public:
217 5 : ParallelMoveCreator() : rng_(CcTest::random_number_generator()) {}
218 :
219 : // Creates a ParallelMove with 'size' random MoveOperands. Note that illegal
220 : // moves will be rejected, so the actual number of MoveOperands may be less.
221 810000 : ParallelMove* Create(int size) {
222 : ParallelMove* parallel_move = new (main_zone()) ParallelMove(main_zone());
223 : // Valid ParallelMoves can't have interfering destination ops.
224 : std::set<InstructionOperand, CompareOperandModuloType> destinations;
225 : // Valid ParallelMoves can't have interfering source ops of different reps.
226 : std::map<InstructionOperand, MachineRepresentation,
227 : CompareOperandModuloType>
228 : sources;
229 810000 : for (int i = 0; i < size; ++i) {
230 790000 : MachineRepresentation rep = RandomRepresentation();
231 : MoveOperands mo(CreateRandomOperand(true, rep),
232 1580000 : CreateRandomOperand(false, rep));
233 876210 : if (mo.IsRedundant()) continue;
234 :
235 : const InstructionOperand& dst = mo.destination();
236 : bool reject = false;
237 : // On architectures where FP register aliasing is non-simple, update the
238 : // destinations set with the float equivalents of the operand and check
239 : // that all destinations are unique and do not alias each other.
240 : if (!kSimpleFPAliasing && mo.destination().IsFPLocationOperand()) {
241 : std::vector<InstructionOperand> fragments;
242 : GetCanonicalOperands(dst, &fragments);
243 : CHECK(!fragments.empty());
244 : for (size_t i = 0; i < fragments.size(); ++i) {
245 : if (destinations.find(fragments[i]) == destinations.end()) {
246 : destinations.insert(fragments[i]);
247 : } else {
248 : reject = true;
249 : break;
250 : }
251 : }
252 : // Update the sources map, and check that no FP source has multiple
253 : // representations.
254 : const InstructionOperand& src = mo.source();
255 : if (src.IsFPRegister()) {
256 : std::vector<InstructionOperand> fragments;
257 : MachineRepresentation src_rep =
258 : LocationOperand::cast(src).representation();
259 : GetCanonicalOperands(src, &fragments);
260 : CHECK(!fragments.empty());
261 : for (size_t i = 0; i < fragments.size(); ++i) {
262 : auto find_it = sources.find(fragments[i]);
263 : if (find_it != sources.end() && find_it->second != src_rep) {
264 : reject = true;
265 : break;
266 : }
267 : sources.insert(std::make_pair(fragments[i], src_rep));
268 : }
269 : }
270 : } else {
271 703790 : if (destinations.find(dst) == destinations.end()) {
272 : destinations.insert(dst);
273 : } else {
274 : reject = true;
275 : }
276 : }
277 :
278 703790 : if (!reject) {
279 : parallel_move->AddMove(mo.source(), mo.destination());
280 : }
281 : }
282 20000 : return parallel_move;
283 : }
284 :
285 : // Creates a ParallelMove from a list of operand pairs. Even operands are
286 : // destinations, odd ones are sources.
287 : ParallelMove* Create(const std::vector<InstructionOperand>& operand_pairs) {
288 : ParallelMove* parallel_move = new (main_zone()) ParallelMove(main_zone());
289 : for (size_t i = 0; i < operand_pairs.size(); i += 2) {
290 : const InstructionOperand& dst = operand_pairs[i];
291 : const InstructionOperand& src = operand_pairs[i + 1];
292 : parallel_move->AddMove(src, dst);
293 : }
294 : return parallel_move;
295 : }
296 :
297 : private:
298 790000 : MachineRepresentation RandomRepresentation() {
299 790000 : int index = rng_->NextInt(6);
300 790000 : switch (index) {
301 : case 0:
302 : return MachineRepresentation::kWord32;
303 : case 1:
304 : return MachineRepresentation::kWord64;
305 : case 2:
306 : return MachineRepresentation::kFloat32;
307 : case 3:
308 : return MachineRepresentation::kFloat64;
309 : case 4:
310 : return MachineRepresentation::kSimd128;
311 : case 5:
312 : return MachineRepresentation::kTagged;
313 : }
314 0 : UNREACHABLE();
315 : }
316 :
317 : // min(num_alloctable_general_registers for each arch) == 6 from
318 : // assembler-ia32.h
319 : const int kMaxIndex = 6;
320 : const int kMaxIndices = kMaxIndex + 1;
321 :
322 : // Non-FP slots shouldn't overlap FP slots.
323 : // FP slots with different representations shouldn't overlap.
324 711080 : int GetValidSlotIndex(MachineRepresentation rep, int index) {
325 : DCHECK_GE(kMaxIndex, index);
326 : // The first group of slots are for non-FP values.
327 711080 : if (!IsFloatingPoint(rep)) return index;
328 : // The next group are for float values.
329 354420 : int base = kMaxIndices;
330 354420 : if (rep == MachineRepresentation::kFloat32) return base + index;
331 : // Double values.
332 237580 : base += kMaxIndices;
333 237580 : if (rep == MachineRepresentation::kFloat64) return base + index * 2;
334 : // SIMD values
335 117675 : base += kMaxIndices * 2;
336 117675 : CHECK_EQ(MachineRepresentation::kSimd128, rep);
337 117675 : return base + index * 4;
338 : }
339 :
340 1580000 : InstructionOperand CreateRandomOperand(bool is_source,
341 : MachineRepresentation rep) {
342 1580000 : auto conf = RegisterConfiguration::Default();
343 710915 : auto GetValidRegisterCode = [&conf](MachineRepresentation rep, int index) {
344 710915 : switch (rep) {
345 : case MachineRepresentation::kFloat32:
346 711160 : return conf->RegisterConfiguration::GetAllocatableFloatCode(index);
347 : case MachineRepresentation::kFloat64:
348 236740 : return conf->RegisterConfiguration::GetAllocatableDoubleCode(index);
349 : case MachineRepresentation::kSimd128:
350 236940 : return conf->RegisterConfiguration::GetAllocatableSimd128Code(index);
351 : default:
352 710720 : return conf->RegisterConfiguration::GetAllocatableGeneralCode(index);
353 : }
354 : UNREACHABLE();
355 1580000 : };
356 1580000 : int index = rng_->NextInt(kMaxIndex);
357 : // destination can't be Constant.
358 1580000 : switch (rng_->NextInt(is_source ? 5 : 4)) {
359 : case 0:
360 : return AllocatedOperand(LocationOperand::STACK_SLOT, rep,
361 712350 : GetValidSlotIndex(rep, index));
362 : case 1:
363 : return AllocatedOperand(LocationOperand::REGISTER, rep,
364 712380 : GetValidRegisterCode(rep, index));
365 : case 2:
366 : return ExplicitOperand(LocationOperand::REGISTER, rep,
367 354725 : GetValidRegisterCode(rep, 1));
368 : case 3:
369 : return ExplicitOperand(LocationOperand::STACK_SLOT, rep,
370 354905 : GetValidSlotIndex(rep, index));
371 : case 4:
372 158005 : return ConstantOperand(index);
373 : }
374 0 : UNREACHABLE();
375 : }
376 :
377 : private:
378 : v8::base::RandomNumberGenerator* rng_;
379 : };
380 :
381 20000 : void RunTest(ParallelMove* pm, Zone* zone) {
382 : // Note: The gap resolver modifies the ParallelMove, so interpret first.
383 : MoveInterpreter mi1(zone);
384 : mi1.AssembleParallelMove(pm);
385 :
386 : MoveInterpreter mi2(zone);
387 : GapResolver resolver(&mi2);
388 20000 : resolver.Resolve(pm);
389 :
390 40000 : CHECK_EQ(mi1.state(), mi2.state());
391 20000 : }
392 :
393 23723 : TEST(Aliasing) {
394 : // On platforms with simple aliasing, these parallel moves are ill-formed.
395 5 : if (kSimpleFPAliasing) return;
396 :
397 : ParallelMoveCreator pmc;
398 : Zone* zone = pmc.main_zone();
399 :
400 : auto s0 = AllocatedOperand(LocationOperand::REGISTER,
401 : MachineRepresentation::kFloat32, 0);
402 : auto s1 = AllocatedOperand(LocationOperand::REGISTER,
403 : MachineRepresentation::kFloat32, 1);
404 : auto s2 = AllocatedOperand(LocationOperand::REGISTER,
405 : MachineRepresentation::kFloat32, 2);
406 : auto s3 = AllocatedOperand(LocationOperand::REGISTER,
407 : MachineRepresentation::kFloat32, 3);
408 : auto s4 = AllocatedOperand(LocationOperand::REGISTER,
409 : MachineRepresentation::kFloat32, 4);
410 :
411 : auto d0 = AllocatedOperand(LocationOperand::REGISTER,
412 : MachineRepresentation::kFloat64, 0);
413 : auto d1 = AllocatedOperand(LocationOperand::REGISTER,
414 : MachineRepresentation::kFloat64, 1);
415 : auto d16 = AllocatedOperand(LocationOperand::REGISTER,
416 : MachineRepresentation::kFloat64, 16);
417 :
418 : // Double slots must be odd to match frame allocation.
419 : auto dSlot = AllocatedOperand(LocationOperand::STACK_SLOT,
420 : MachineRepresentation::kFloat64, 3);
421 :
422 : // Cycles involving s- and d-registers.
423 : {
424 : std::vector<InstructionOperand> moves = {
425 : s2, s0, // s2 <- s0
426 : d0, d1 // d0 <- d1
427 : };
428 : RunTest(pmc.Create(moves), zone);
429 : }
430 : {
431 : std::vector<InstructionOperand> moves = {
432 : d0, d1, // d0 <- d1
433 : s2, s0 // s2 <- s0
434 : };
435 : RunTest(pmc.Create(moves), zone);
436 : }
437 : {
438 : std::vector<InstructionOperand> moves = {
439 : s2, s1, // s2 <- s1
440 : d0, d1 // d0 <- d1
441 : };
442 : RunTest(pmc.Create(moves), zone);
443 : }
444 : {
445 : std::vector<InstructionOperand> moves = {
446 : d0, d1, // d0 <- d1
447 : s2, s1 // s2 <- s1
448 : };
449 : RunTest(pmc.Create(moves), zone);
450 : }
451 : // Two cycles involving a single d-register.
452 : {
453 : std::vector<InstructionOperand> moves = {
454 : d0, d1, // d0 <- d1
455 : s2, s1, // s2 <- s1
456 : s3, s0 // s3 <- s0
457 : };
458 : RunTest(pmc.Create(moves), zone);
459 : }
460 : // Cycle with a float move that must be deferred until after swaps.
461 : {
462 : std::vector<InstructionOperand> moves = {
463 : d0, d1, // d0 <- d1
464 : s2, s0, // s2 <- s0
465 : s3, s4 // s3 <- s4 must be deferred
466 : };
467 : RunTest(pmc.Create(moves), zone);
468 : }
469 : // Cycles involving s-registers and a non-aliased d-register.
470 : {
471 : std::vector<InstructionOperand> moves = {
472 : d16, d0, // d16 <- d0
473 : s1, s2, // s1 <- s2
474 : d1, d16 // d1 <- d16
475 : };
476 : RunTest(pmc.Create(moves), zone);
477 : }
478 : {
479 : std::vector<InstructionOperand> moves = {
480 : s2, s1, // s1 <- s2
481 : d0, d16, // d16 <- d0
482 : d16, d1 // d1 <- d16
483 : };
484 : RunTest(pmc.Create(moves), zone);
485 : }
486 : {
487 : std::vector<InstructionOperand> moves = {
488 : d0, d16, // d0 <- d16
489 : d16, d1, // s2 <- s0
490 : s3, s0 // d0 <- d1
491 : };
492 : RunTest(pmc.Create(moves), zone);
493 : }
494 : // Cycle involving aliasing registers and a slot.
495 : {
496 : std::vector<InstructionOperand> moves = {
497 : dSlot, d0, // dSlot <- d0
498 : d1, dSlot, // d1 <- dSlot
499 : s0, s3 // s0 <- s3
500 : };
501 : RunTest(pmc.Create(moves), zone);
502 : }
503 : }
504 :
505 23723 : TEST(FuzzResolver) {
506 5 : ParallelMoveCreator pmc;
507 405 : for (int size = 0; size < 80; ++size) {
508 20000 : for (int repeat = 0; repeat < 50; ++repeat) {
509 20000 : RunTest(pmc.Create(size), pmc.main_zone());
510 : }
511 : }
512 5 : }
513 :
514 : } // namespace compiler
515 : } // namespace internal
516 71154 : } // namespace v8
|
