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