1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
|
// 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) const {
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());
}
}
}
|
