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/backend/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 413935 : class InterpreterState {
47 : public:
48 333935 : void ExecuteInParallel(const ParallelMove* moves) {
49 : InterpreterState copy(*this);
50 986320 : for (const auto m : *moves) {
51 652385 : CHECK(!m->IsRedundant());
52 : const InstructionOperand& src = m->source();
53 : 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 652385 : write(dst, copy.read(src));
73 : }
74 333935 : }
75 :
76 : bool operator==(const InterpreterState& other) const {
77 : 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 5119665 : if (this->is_constant != other.is_constant) {
95 : return this->is_constant;
96 : }
97 4814405 : if (this->rep != other.rep) {
98 1024010 : return this->rep < other.rep;
99 : }
100 3790395 : if (this->kind != other.kind) {
101 1137060 : return this->kind < other.kind;
102 : }
103 2653335 : return this->index < other.index;
104 : }
105 :
106 : bool operator==(const Key& other) const {
107 2458160 : return this->is_constant == other.is_constant && this->rep == other.rep &&
108 2170150 : 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 652385 : Value read(const InstructionOperand& op) const {
117 1304770 : OperandMap::const_iterator it = values_.find(KeyFor(op));
118 661675 : return (it == values_.end()) ? ValueFor(op) : it->second;
119 : }
120 :
121 652385 : void write(const InstructionOperand& dst, Value v) {
122 652385 : if (v == ValueFor(dst)) {
123 0 : values_.erase(KeyFor(dst));
124 : } else {
125 652385 : values_[KeyFor(dst)] = v;
126 : }
127 652385 : }
128 :
129 2600250 : 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 2600250 : 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 2314350 : if (IsFloatingPoint(loc_op.representation())) {
140 : rep = kSimpleFPAliasing ? MachineRepresentation::kFloat64
141 : : loc_op.representation();
142 : }
143 2314350 : 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 2600250 : Key key = {is_constant, rep, kind, index};
154 2600250 : return key;
155 : }
156 :
157 1295480 : 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 : const char* space = "";
169 : for (auto& value : is.values_) {
170 : InstructionOperand source = FromKey(value.second);
171 : InstructionOperand destination = FromKey(value.first);
172 : os << space << MoveOperands{source, destination};
173 : space = " ";
174 : }
175 : return os;
176 : }
177 :
178 : OperandMap values_;
179 : };
180 :
181 : // An abstract interpreter for moves, swaps and parallel moves.
182 60000 : class MoveInterpreter : public GapResolver::Assembler {
183 : public:
184 40000 : explicit MoveInterpreter(Zone* zone) : zone_(zone) {}
185 :
186 299570 : void AssembleMove(InstructionOperand* source,
187 : InstructionOperand* destination) override {
188 599140 : ParallelMove* moves = new (zone_) ParallelMove(zone_);
189 : moves->AddMove(*source, *destination);
190 299570 : state_.ExecuteInParallel(moves);
191 299570 : }
192 :
193 14365 : void AssembleSwap(InstructionOperand* source,
194 : InstructionOperand* destination) override {
195 28730 : ParallelMove* moves = new (zone_) ParallelMove(zone_);
196 : moves->AddMove(*source, *destination);
197 : moves->AddMove(*destination, *source);
198 14365 : state_.ExecuteInParallel(moves);
199 14365 : }
200 :
201 : void AssembleParallelMove(const ParallelMove* moves) {
202 20000 : state_.ExecuteInParallel(moves);
203 : }
204 :
205 : InterpreterState state() const { return state_; }
206 :
207 : private:
208 : Zone* const zone_;
209 : InterpreterState state_;
210 : };
211 :
212 :
213 5 : class ParallelMoveCreator : public HandleAndZoneScope {
214 : public:
215 5 : ParallelMoveCreator() : rng_(CcTest::random_number_generator()) {}
216 :
217 : // Creates a ParallelMove with 'size' random MoveOperands. Note that illegal
218 : // moves will be rejected, so the actual number of MoveOperands may be less.
219 20000 : ParallelMove* Create(int size) {
220 : ParallelMove* parallel_move = new (main_zone()) ParallelMove(main_zone());
221 : // Valid ParallelMoves can't have interfering destination ops.
222 : std::set<InstructionOperand, CompareOperandModuloType> destinations;
223 : // Valid ParallelMoves can't have interfering source ops of different reps.
224 : std::map<InstructionOperand, MachineRepresentation,
225 : CompareOperandModuloType>
226 : sources;
227 1600000 : for (int i = 0; i < size; ++i) {
228 790000 : MachineRepresentation rep = RandomRepresentation();
229 1580000 : MoveOperands mo(CreateRandomOperand(true, rep),
230 1580000 : CreateRandomOperand(false, rep));
231 883935 : if (mo.IsRedundant()) continue;
232 :
233 : const InstructionOperand& dst = mo.destination();
234 : bool reject = false;
235 : // On architectures where FP register aliasing is non-simple, update the
236 : // destinations set with the float equivalents of the operand and check
237 : // that all destinations are unique and do not alias each other.
238 : if (!kSimpleFPAliasing && mo.destination().IsFPLocationOperand()) {
239 : std::vector<InstructionOperand> fragments;
240 : GetCanonicalOperands(dst, &fragments);
241 : CHECK(!fragments.empty());
242 : for (size_t i = 0; i < fragments.size(); ++i) {
243 : if (destinations.find(fragments[i]) == destinations.end()) {
244 : destinations.insert(fragments[i]);
245 : } else {
246 : reject = true;
247 : break;
248 : }
249 : }
250 : // Update the sources map, and check that no FP source has multiple
251 : // representations.
252 : const InstructionOperand& src = mo.source();
253 : if (src.IsFPRegister()) {
254 : std::vector<InstructionOperand> fragments;
255 : MachineRepresentation src_rep =
256 : LocationOperand::cast(src).representation();
257 : GetCanonicalOperands(src, &fragments);
258 : CHECK(!fragments.empty());
259 : for (size_t i = 0; i < fragments.size(); ++i) {
260 : auto find_it = sources.find(fragments[i]);
261 : if (find_it != sources.end() && find_it->second != src_rep) {
262 : reject = true;
263 : break;
264 : }
265 : sources.insert(std::make_pair(fragments[i], src_rep));
266 : }
267 : }
268 : } else {
269 696065 : if (destinations.find(dst) == destinations.end()) {
270 : destinations.insert(dst);
271 : } else {
272 : reject = true;
273 : }
274 : }
275 :
276 696065 : if (!reject) {
277 : parallel_move->AddMove(mo.source(), mo.destination());
278 : }
279 : }
280 20000 : return parallel_move;
281 : }
282 :
283 : // Creates a ParallelMove from a list of operand pairs. Even operands are
284 : // destinations, odd ones are sources.
285 : ParallelMove* Create(const std::vector<InstructionOperand>& operand_pairs) {
286 : ParallelMove* parallel_move = new (main_zone()) ParallelMove(main_zone());
287 : for (size_t i = 0; i < operand_pairs.size(); i += 2) {
288 : const InstructionOperand& dst = operand_pairs[i];
289 : const InstructionOperand& src = operand_pairs[i + 1];
290 : parallel_move->AddMove(src, dst);
291 : }
292 : return parallel_move;
293 : }
294 :
295 : private:
296 790000 : MachineRepresentation RandomRepresentation() {
297 790000 : int index = rng_->NextInt(6);
298 790000 : switch (index) {
299 : case 0:
300 : return MachineRepresentation::kWord32;
301 : case 1:
302 : return MachineRepresentation::kWord64;
303 : case 2:
304 : return MachineRepresentation::kFloat32;
305 : case 3:
306 : return MachineRepresentation::kFloat64;
307 : case 4:
308 : return MachineRepresentation::kSimd128;
309 : case 5:
310 : return MachineRepresentation::kTagged;
311 : }
312 0 : UNREACHABLE();
313 : }
314 :
315 : // min(num_alloctable_general_registers for each arch) == 5 from
316 : // assembler-ia32.h
317 : const int kMaxIndex = 5;
318 : const int kMaxIndices = kMaxIndex + 1;
319 :
320 : // Non-FP slots shouldn't overlap FP slots.
321 : // FP slots with different representations shouldn't overlap.
322 712870 : int GetValidSlotIndex(MachineRepresentation rep, int index) {
323 : DCHECK_GE(kMaxIndex, index);
324 : // The first group of slots are for non-FP values.
325 712870 : if (!IsFloatingPoint(rep)) return index;
326 : // The next group are for float values.
327 355915 : int base = kMaxIndices;
328 355915 : if (rep == MachineRepresentation::kFloat32) return base + index;
329 : // Double values.
330 236145 : base += kMaxIndices;
331 236145 : if (rep == MachineRepresentation::kFloat64) return base + index * 2;
332 : // SIMD values
333 117615 : base += kMaxIndices * 2;
334 117615 : CHECK_EQ(MachineRepresentation::kSimd128, rep);
335 117615 : return base + index * 4;
336 : }
337 :
338 1580000 : InstructionOperand CreateRandomOperand(bool is_source,
339 : MachineRepresentation rep) {
340 1580000 : auto conf = RegisterConfiguration::Default();
341 1418320 : auto GetValidRegisterCode = [&conf](MachineRepresentation rep, int index) {
342 709160 : switch (rep) {
343 : case MachineRepresentation::kFloat32:
344 239660 : return conf->RegisterConfiguration::GetAllocatableFloatCode(index);
345 : case MachineRepresentation::kFloat64:
346 235320 : return conf->RegisterConfiguration::GetAllocatableDoubleCode(index);
347 : case MachineRepresentation::kSimd128:
348 235520 : return conf->RegisterConfiguration::GetAllocatableSimd128Code(index);
349 : default:
350 707820 : return conf->RegisterConfiguration::GetAllocatableGeneralCode(index);
351 : }
352 : UNREACHABLE();
353 1580000 : };
354 1580000 : int index = rng_->NextInt(kMaxIndex);
355 : // destination can't be Constant.
356 1580000 : switch (rng_->NextInt(is_source ? 5 : 4)) {
357 : case 0:
358 : return AllocatedOperand(LocationOperand::STACK_SLOT, rep,
359 711580 : GetValidSlotIndex(rep, index));
360 : case 1:
361 : return AllocatedOperand(LocationOperand::REGISTER, rep,
362 714480 : GetValidRegisterCode(rep, index));
363 : case 2:
364 : return ExplicitOperand(LocationOperand::REGISTER, rep,
365 351920 : GetValidRegisterCode(rep, 1));
366 : case 3:
367 : return ExplicitOperand(LocationOperand::STACK_SLOT, rep,
368 357080 : GetValidSlotIndex(rep, index));
369 : case 4:
370 157970 : return ConstantOperand(index);
371 : }
372 0 : UNREACHABLE();
373 : }
374 :
375 : private:
376 : v8::base::RandomNumberGenerator* rng_;
377 : };
378 :
379 20000 : void RunTest(ParallelMove* pm, Zone* zone) {
380 : // Note: The gap resolver modifies the ParallelMove, so interpret first.
381 : MoveInterpreter mi1(zone);
382 : mi1.AssembleParallelMove(pm);
383 :
384 : MoveInterpreter mi2(zone);
385 : GapResolver resolver(&mi2);
386 20000 : resolver.Resolve(pm);
387 :
388 40000 : CHECK_EQ(mi1.state(), mi2.state());
389 20000 : }
390 :
391 26644 : TEST(Aliasing) {
392 : // On platforms with simple aliasing, these parallel moves are ill-formed.
393 : if (kSimpleFPAliasing) return;
394 :
395 : ParallelMoveCreator pmc;
396 : Zone* zone = pmc.main_zone();
397 :
398 : auto s0 = AllocatedOperand(LocationOperand::REGISTER,
399 : MachineRepresentation::kFloat32, 0);
400 : auto s1 = AllocatedOperand(LocationOperand::REGISTER,
401 : MachineRepresentation::kFloat32, 1);
402 : auto s2 = AllocatedOperand(LocationOperand::REGISTER,
403 : MachineRepresentation::kFloat32, 2);
404 : auto s3 = AllocatedOperand(LocationOperand::REGISTER,
405 : MachineRepresentation::kFloat32, 3);
406 : auto s4 = AllocatedOperand(LocationOperand::REGISTER,
407 : MachineRepresentation::kFloat32, 4);
408 :
409 : auto d0 = AllocatedOperand(LocationOperand::REGISTER,
410 : MachineRepresentation::kFloat64, 0);
411 : auto d1 = AllocatedOperand(LocationOperand::REGISTER,
412 : MachineRepresentation::kFloat64, 1);
413 : auto d16 = AllocatedOperand(LocationOperand::REGISTER,
414 : MachineRepresentation::kFloat64, 16);
415 :
416 : // Double slots must be odd to match frame allocation.
417 : auto dSlot = AllocatedOperand(LocationOperand::STACK_SLOT,
418 : MachineRepresentation::kFloat64, 3);
419 :
420 : // Cycles involving s- and d-registers.
421 : {
422 : std::vector<InstructionOperand> moves = {
423 : s2, s0, // s2 <- s0
424 : d0, d1 // d0 <- d1
425 : };
426 : RunTest(pmc.Create(moves), zone);
427 : }
428 : {
429 : std::vector<InstructionOperand> moves = {
430 : d0, d1, // d0 <- d1
431 : s2, s0 // s2 <- s0
432 : };
433 : RunTest(pmc.Create(moves), zone);
434 : }
435 : {
436 : std::vector<InstructionOperand> moves = {
437 : s2, s1, // s2 <- s1
438 : d0, d1 // d0 <- d1
439 : };
440 : RunTest(pmc.Create(moves), zone);
441 : }
442 : {
443 : std::vector<InstructionOperand> moves = {
444 : d0, d1, // d0 <- d1
445 : s2, s1 // s2 <- s1
446 : };
447 : RunTest(pmc.Create(moves), zone);
448 : }
449 : // Two cycles involving a single d-register.
450 : {
451 : std::vector<InstructionOperand> moves = {
452 : d0, d1, // d0 <- d1
453 : s2, s1, // s2 <- s1
454 : s3, s0 // s3 <- s0
455 : };
456 : RunTest(pmc.Create(moves), zone);
457 : }
458 : // Cycle with a float move that must be deferred until after swaps.
459 : {
460 : std::vector<InstructionOperand> moves = {
461 : d0, d1, // d0 <- d1
462 : s2, s0, // s2 <- s0
463 : s3, s4 // s3 <- s4 must be deferred
464 : };
465 : RunTest(pmc.Create(moves), zone);
466 : }
467 : // Cycles involving s-registers and a non-aliased d-register.
468 : {
469 : std::vector<InstructionOperand> moves = {
470 : d16, d0, // d16 <- d0
471 : s1, s2, // s1 <- s2
472 : d1, d16 // d1 <- d16
473 : };
474 : RunTest(pmc.Create(moves), zone);
475 : }
476 : {
477 : std::vector<InstructionOperand> moves = {
478 : s2, s1, // s1 <- s2
479 : d0, d16, // d16 <- d0
480 : d16, d1 // d1 <- d16
481 : };
482 : RunTest(pmc.Create(moves), zone);
483 : }
484 : {
485 : std::vector<InstructionOperand> moves = {
486 : d0, d16, // d0 <- d16
487 : d16, d1, // s2 <- s0
488 : s3, s0 // d0 <- d1
489 : };
490 : RunTest(pmc.Create(moves), zone);
491 : }
492 : // Cycle involving aliasing registers and a slot.
493 : {
494 : std::vector<InstructionOperand> moves = {
495 : dSlot, d0, // dSlot <- d0
496 : d1, dSlot, // d1 <- dSlot
497 : s0, s3 // s0 <- s3
498 : };
499 : RunTest(pmc.Create(moves), zone);
500 : }
501 : }
502 :
503 26644 : TEST(FuzzResolver) {
504 : ParallelMoveCreator pmc;
505 805 : for (int size = 0; size < 80; ++size) {
506 40400 : for (int repeat = 0; repeat < 50; ++repeat) {
507 20000 : RunTest(pmc.Create(size), pmc.main_zone());
508 : }
509 : }
510 5 : }
511 :
512 : } // namespace compiler
513 : } // namespace internal
514 79917 : } // namespace v8
|
