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/bit-vector.h"
6 #include "src/compiler/control-equivalence.h"
7 #include "src/compiler/graph-visualizer.h"
8 #include "src/compiler/node-properties.h"
9 #include "src/compiler/source-position.h"
10 #include "src/zone-containers.h"
11 #include "test/unittests/compiler/graph-unittest.h"
12
13 namespace v8 {
14 namespace internal {
15 namespace compiler {
16
17 #define ASSERT_EQUIVALENCE(...) \
18 do { \
19 Node* __n[] = {__VA_ARGS__}; \
20 ASSERT_TRUE(IsEquivalenceClass(arraysize(__n), __n)); \
21 } while (false)
22
23 class ControlEquivalenceTest : public GraphTest {
24 public:
ControlEquivalenceTest()25 ControlEquivalenceTest() : all_nodes_(zone()), classes_(zone()) {
26 Store(graph()->start());
27 }
28
29 protected:
ComputeEquivalence(Node * node)30 void ComputeEquivalence(Node* node) {
31 graph()->SetEnd(graph()->NewNode(common()->End(1), node));
32 if (FLAG_trace_turbo) {
33 OFStream os(stdout);
34 SourcePositionTable table(graph());
35 os << AsJSON(*graph(), &table);
36 }
37 ControlEquivalence equivalence(zone(), graph());
38 equivalence.Run(node);
39 classes_.resize(graph()->NodeCount());
40 for (Node* node : all_nodes_) {
41 classes_[node->id()] = equivalence.ClassOf(node);
42 }
43 }
44
IsEquivalenceClass(size_t length,Node ** nodes)45 bool IsEquivalenceClass(size_t length, Node** nodes) {
46 BitVector in_class(static_cast<int>(graph()->NodeCount()), zone());
47 size_t expected_class = classes_[nodes[0]->id()];
48 for (size_t i = 0; i < length; ++i) {
49 in_class.Add(nodes[i]->id());
50 }
51 for (Node* node : all_nodes_) {
52 if (in_class.Contains(node->id())) {
53 if (classes_[node->id()] != expected_class) return false;
54 } else {
55 if (classes_[node->id()] == expected_class) return false;
56 }
57 }
58 return true;
59 }
60
Value()61 Node* Value() { return NumberConstant(0.0); }
62
Branch(Node * control)63 Node* Branch(Node* control) {
64 return Store(graph()->NewNode(common()->Branch(), Value(), control));
65 }
66
IfTrue(Node * control)67 Node* IfTrue(Node* control) {
68 return Store(graph()->NewNode(common()->IfTrue(), control));
69 }
70
IfFalse(Node * control)71 Node* IfFalse(Node* control) {
72 return Store(graph()->NewNode(common()->IfFalse(), control));
73 }
74
Merge1(Node * control)75 Node* Merge1(Node* control) {
76 return Store(graph()->NewNode(common()->Merge(1), control));
77 }
78
Merge2(Node * control1,Node * control2)79 Node* Merge2(Node* control1, Node* control2) {
80 return Store(graph()->NewNode(common()->Merge(2), control1, control2));
81 }
82
Loop2(Node * control)83 Node* Loop2(Node* control) {
84 return Store(graph()->NewNode(common()->Loop(2), control, control));
85 }
86
End(Node * control)87 Node* End(Node* control) {
88 return Store(graph()->NewNode(common()->End(1), control));
89 }
90
91 private:
Store(Node * node)92 Node* Store(Node* node) {
93 all_nodes_.push_back(node);
94 return node;
95 }
96
97 ZoneVector<Node*> all_nodes_;
98 ZoneVector<size_t> classes_;
99 };
100
101
102 // -----------------------------------------------------------------------------
103 // Test cases.
104
105
TEST_F(ControlEquivalenceTest,Empty1)106 TEST_F(ControlEquivalenceTest, Empty1) {
107 Node* start = graph()->start();
108 ComputeEquivalence(start);
109
110 ASSERT_EQUIVALENCE(start);
111 }
112
113
TEST_F(ControlEquivalenceTest,Empty2)114 TEST_F(ControlEquivalenceTest, Empty2) {
115 Node* start = graph()->start();
116 Node* merge1 = Merge1(start);
117 ComputeEquivalence(merge1);
118
119 ASSERT_EQUIVALENCE(start, merge1);
120 }
121
122
TEST_F(ControlEquivalenceTest,Diamond1)123 TEST_F(ControlEquivalenceTest, Diamond1) {
124 Node* start = graph()->start();
125 Node* b = Branch(start);
126 Node* t = IfTrue(b);
127 Node* f = IfFalse(b);
128 Node* m = Merge2(t, f);
129 ComputeEquivalence(m);
130
131 ASSERT_EQUIVALENCE(b, m, start);
132 ASSERT_EQUIVALENCE(f);
133 ASSERT_EQUIVALENCE(t);
134 }
135
136
TEST_F(ControlEquivalenceTest,Diamond2)137 TEST_F(ControlEquivalenceTest, Diamond2) {
138 Node* start = graph()->start();
139 Node* b1 = Branch(start);
140 Node* t1 = IfTrue(b1);
141 Node* f1 = IfFalse(b1);
142 Node* b2 = Branch(f1);
143 Node* t2 = IfTrue(b2);
144 Node* f2 = IfFalse(b2);
145 Node* m2 = Merge2(t2, f2);
146 Node* m1 = Merge2(t1, m2);
147 ComputeEquivalence(m1);
148
149 ASSERT_EQUIVALENCE(b1, m1, start);
150 ASSERT_EQUIVALENCE(t1);
151 ASSERT_EQUIVALENCE(f1, b2, m2);
152 ASSERT_EQUIVALENCE(t2);
153 ASSERT_EQUIVALENCE(f2);
154 }
155
156
TEST_F(ControlEquivalenceTest,Diamond3)157 TEST_F(ControlEquivalenceTest, Diamond3) {
158 Node* start = graph()->start();
159 Node* b1 = Branch(start);
160 Node* t1 = IfTrue(b1);
161 Node* f1 = IfFalse(b1);
162 Node* m1 = Merge2(t1, f1);
163 Node* b2 = Branch(m1);
164 Node* t2 = IfTrue(b2);
165 Node* f2 = IfFalse(b2);
166 Node* m2 = Merge2(t2, f2);
167 ComputeEquivalence(m2);
168
169 ASSERT_EQUIVALENCE(b1, m1, b2, m2, start);
170 ASSERT_EQUIVALENCE(t1);
171 ASSERT_EQUIVALENCE(f1);
172 ASSERT_EQUIVALENCE(t2);
173 ASSERT_EQUIVALENCE(f2);
174 }
175
176
TEST_F(ControlEquivalenceTest,Switch1)177 TEST_F(ControlEquivalenceTest, Switch1) {
178 Node* start = graph()->start();
179 Node* b1 = Branch(start);
180 Node* t1 = IfTrue(b1);
181 Node* f1 = IfFalse(b1);
182 Node* b2 = Branch(f1);
183 Node* t2 = IfTrue(b2);
184 Node* f2 = IfFalse(b2);
185 Node* b3 = Branch(f2);
186 Node* t3 = IfTrue(b3);
187 Node* f3 = IfFalse(b3);
188 Node* m1 = Merge2(t1, t2);
189 Node* m2 = Merge2(m1, t3);
190 Node* m3 = Merge2(m2, f3);
191 ComputeEquivalence(m3);
192
193 ASSERT_EQUIVALENCE(b1, m3, start);
194 ASSERT_EQUIVALENCE(t1);
195 ASSERT_EQUIVALENCE(f1, b2);
196 ASSERT_EQUIVALENCE(t2);
197 ASSERT_EQUIVALENCE(f2, b3);
198 ASSERT_EQUIVALENCE(t3);
199 ASSERT_EQUIVALENCE(f3);
200 ASSERT_EQUIVALENCE(m1);
201 ASSERT_EQUIVALENCE(m2);
202 }
203
204
TEST_F(ControlEquivalenceTest,Loop1)205 TEST_F(ControlEquivalenceTest, Loop1) {
206 Node* start = graph()->start();
207 Node* l = Loop2(start);
208 l->ReplaceInput(1, l);
209 ComputeEquivalence(l);
210
211 ASSERT_EQUIVALENCE(start);
212 ASSERT_EQUIVALENCE(l);
213 }
214
215
TEST_F(ControlEquivalenceTest,Loop2)216 TEST_F(ControlEquivalenceTest, Loop2) {
217 Node* start = graph()->start();
218 Node* l = Loop2(start);
219 Node* b = Branch(l);
220 Node* t = IfTrue(b);
221 Node* f = IfFalse(b);
222 l->ReplaceInput(1, t);
223 ComputeEquivalence(f);
224
225 ASSERT_EQUIVALENCE(f, start);
226 ASSERT_EQUIVALENCE(t);
227 ASSERT_EQUIVALENCE(l, b);
228 }
229
230
TEST_F(ControlEquivalenceTest,Irreducible)231 TEST_F(ControlEquivalenceTest, Irreducible) {
232 Node* start = graph()->start();
233 Node* b1 = Branch(start);
234 Node* t1 = IfTrue(b1);
235 Node* f1 = IfFalse(b1);
236 Node* lp = Loop2(f1);
237 Node* m1 = Merge2(t1, lp);
238 Node* b2 = Branch(m1);
239 Node* t2 = IfTrue(b2);
240 Node* f2 = IfFalse(b2);
241 Node* m2 = Merge2(t2, f2);
242 Node* b3 = Branch(m2);
243 Node* t3 = IfTrue(b3);
244 Node* f3 = IfFalse(b3);
245 lp->ReplaceInput(1, f3);
246 ComputeEquivalence(t3);
247
248 ASSERT_EQUIVALENCE(b1, t3, start);
249 ASSERT_EQUIVALENCE(t1);
250 ASSERT_EQUIVALENCE(f1);
251 ASSERT_EQUIVALENCE(m1, b2, m2, b3);
252 ASSERT_EQUIVALENCE(t2);
253 ASSERT_EQUIVALENCE(f2);
254 ASSERT_EQUIVALENCE(f3);
255 ASSERT_EQUIVALENCE(lp);
256 }
257
258
259 } // namespace compiler
260 } // namespace internal
261 } // namespace v8
262