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.
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-inl.h"
9 #include "src/zone-containers.h"
10 #include "test/unittests/compiler/graph-unittest.h"
16 #define ASSERT_EQUIVALENCE(...) \
18 Node* __n[] = {__VA_ARGS__}; \
19 ASSERT_TRUE(IsEquivalenceClass(arraysize(__n), __n)); \
22 class ControlEquivalenceTest : public GraphTest {
24 ControlEquivalenceTest() : all_nodes_(zone()), classes_(zone()) {
25 Store(graph()->start());
29 void ComputeEquivalence(Node* node) {
30 graph()->SetEnd(graph()->NewNode(common()->End(), node));
31 if (FLAG_trace_turbo) {
33 os << AsDOT(*graph());
35 ControlEquivalence equivalence(zone(), graph());
36 equivalence.Run(node);
37 classes_.resize(graph()->NodeCount());
38 for (Node* node : all_nodes_) {
39 classes_[node->id()] = equivalence.ClassOf(node);
43 bool IsEquivalenceClass(size_t length, Node** nodes) {
44 BitVector in_class(graph()->NodeCount(), zone());
45 size_t expected_class = classes_[nodes[0]->id()];
46 for (size_t i = 0; i < length; ++i) {
47 in_class.Add(nodes[i]->id());
49 for (Node* node : all_nodes_) {
50 if (in_class.Contains(node->id())) {
51 if (classes_[node->id()] != expected_class) return false;
53 if (classes_[node->id()] == expected_class) return false;
59 Node* Value() { return NumberConstant(0.0); }
61 Node* Branch(Node* control) {
62 return Store(graph()->NewNode(common()->Branch(), Value(), control));
65 Node* IfTrue(Node* control) {
66 return Store(graph()->NewNode(common()->IfTrue(), control));
69 Node* IfFalse(Node* control) {
70 return Store(graph()->NewNode(common()->IfFalse(), control));
73 Node* Merge2(Node* control1, Node* control2) {
74 return Store(graph()->NewNode(common()->Merge(2), control1, control2));
77 Node* Loop2(Node* control) {
78 return Store(graph()->NewNode(common()->Loop(2), control, control));
81 Node* End(Node* control) {
82 return Store(graph()->NewNode(common()->End(), control));
86 Node* Store(Node* node) {
87 all_nodes_.push_back(node);
91 ZoneVector<Node*> all_nodes_;
92 ZoneVector<size_t> classes_;
96 // -----------------------------------------------------------------------------
100 TEST_F(ControlEquivalenceTest, Empty1) {
101 Node* start = graph()->start();
102 ComputeEquivalence(start);
104 ASSERT_EQUIVALENCE(start);
108 TEST_F(ControlEquivalenceTest, Empty2) {
109 Node* start = graph()->start();
110 Node* end = End(start);
111 ComputeEquivalence(end);
113 ASSERT_EQUIVALENCE(start, end);
117 TEST_F(ControlEquivalenceTest, Diamond1) {
118 Node* start = graph()->start();
119 Node* b = Branch(start);
121 Node* f = IfFalse(b);
122 Node* m = Merge2(t, f);
123 ComputeEquivalence(m);
125 ASSERT_EQUIVALENCE(b, m, start);
126 ASSERT_EQUIVALENCE(f);
127 ASSERT_EQUIVALENCE(t);
131 TEST_F(ControlEquivalenceTest, Diamond2) {
132 Node* start = graph()->start();
133 Node* b1 = Branch(start);
134 Node* t1 = IfTrue(b1);
135 Node* f1 = IfFalse(b1);
136 Node* b2 = Branch(f1);
137 Node* t2 = IfTrue(b2);
138 Node* f2 = IfFalse(b2);
139 Node* m2 = Merge2(t2, f2);
140 Node* m1 = Merge2(t1, m2);
141 ComputeEquivalence(m1);
143 ASSERT_EQUIVALENCE(b1, m1, start);
144 ASSERT_EQUIVALENCE(t1);
145 ASSERT_EQUIVALENCE(f1, b2, m2);
146 ASSERT_EQUIVALENCE(t2);
147 ASSERT_EQUIVALENCE(f2);
151 TEST_F(ControlEquivalenceTest, Diamond3) {
152 Node* start = graph()->start();
153 Node* b1 = Branch(start);
154 Node* t1 = IfTrue(b1);
155 Node* f1 = IfFalse(b1);
156 Node* m1 = Merge2(t1, f1);
157 Node* b2 = Branch(m1);
158 Node* t2 = IfTrue(b2);
159 Node* f2 = IfFalse(b2);
160 Node* m2 = Merge2(t2, f2);
161 ComputeEquivalence(m2);
163 ASSERT_EQUIVALENCE(b1, m1, b2, m2, start);
164 ASSERT_EQUIVALENCE(t1);
165 ASSERT_EQUIVALENCE(f1);
166 ASSERT_EQUIVALENCE(t2);
167 ASSERT_EQUIVALENCE(f2);
171 TEST_F(ControlEquivalenceTest, Switch1) {
172 Node* start = graph()->start();
173 Node* b1 = Branch(start);
174 Node* t1 = IfTrue(b1);
175 Node* f1 = IfFalse(b1);
176 Node* b2 = Branch(f1);
177 Node* t2 = IfTrue(b2);
178 Node* f2 = IfFalse(b2);
179 Node* b3 = Branch(f2);
180 Node* t3 = IfTrue(b3);
181 Node* f3 = IfFalse(b3);
182 Node* m1 = Merge2(t1, t2);
183 Node* m2 = Merge2(m1, t3);
184 Node* m3 = Merge2(m2, f3);
185 ComputeEquivalence(m3);
187 ASSERT_EQUIVALENCE(b1, m3, start);
188 ASSERT_EQUIVALENCE(t1);
189 ASSERT_EQUIVALENCE(f1, b2);
190 ASSERT_EQUIVALENCE(t2);
191 ASSERT_EQUIVALENCE(f2, b3);
192 ASSERT_EQUIVALENCE(t3);
193 ASSERT_EQUIVALENCE(f3);
194 ASSERT_EQUIVALENCE(m1);
195 ASSERT_EQUIVALENCE(m2);
199 TEST_F(ControlEquivalenceTest, Loop1) {
200 Node* start = graph()->start();
201 Node* l = Loop2(start);
202 l->ReplaceInput(1, l);
203 ComputeEquivalence(l);
205 ASSERT_EQUIVALENCE(start);
206 ASSERT_EQUIVALENCE(l);
210 TEST_F(ControlEquivalenceTest, Loop2) {
211 Node* start = graph()->start();
212 Node* l = Loop2(start);
215 Node* f = IfFalse(b);
216 l->ReplaceInput(1, t);
217 ComputeEquivalence(f);
219 ASSERT_EQUIVALENCE(f, start);
220 ASSERT_EQUIVALENCE(t);
221 ASSERT_EQUIVALENCE(l, b);
225 TEST_F(ControlEquivalenceTest, Irreducible) {
226 Node* start = graph()->start();
227 Node* b1 = Branch(start);
228 Node* t1 = IfTrue(b1);
229 Node* f1 = IfFalse(b1);
230 Node* lp = Loop2(f1);
231 Node* m1 = Merge2(t1, lp);
232 Node* b2 = Branch(m1);
233 Node* t2 = IfTrue(b2);
234 Node* f2 = IfFalse(b2);
235 Node* m2 = Merge2(t2, f2);
236 Node* b3 = Branch(m2);
237 Node* t3 = IfTrue(b3);
238 Node* f3 = IfFalse(b3);
239 lp->ReplaceInput(1, f3);
240 ComputeEquivalence(t3);
242 ASSERT_EQUIVALENCE(b1, t3, start);
243 ASSERT_EQUIVALENCE(t1);
244 ASSERT_EQUIVALENCE(f1);
245 ASSERT_EQUIVALENCE(m1, b2, m2, b3);
246 ASSERT_EQUIVALENCE(t2);
247 ASSERT_EQUIVALENCE(f2);
248 ASSERT_EQUIVALENCE(f3);
249 ASSERT_EQUIVALENCE(lp);
253 } // namespace compiler
254 } // namespace internal