1 // Copyright 2013 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 <vector>
6
7 #include "src/v8.h"
8
9 #include "graph-tester.h"
10 #include "src/compiler/common-operator.h"
11 #include "src/compiler/generic-node.h"
12 #include "src/compiler/generic-node-inl.h"
13 #include "src/compiler/graph.h"
14 #include "src/compiler/graph-inl.h"
15 #include "src/compiler/graph-visualizer.h"
16 #include "src/compiler/operator.h"
17
18 using namespace v8::internal;
19 using namespace v8::internal::compiler;
20
21 static SimpleOperator dummy_operator(IrOpcode::kParameter, Operator::kNoWrite,
22 0, 0, "dummy");
23
24 class PreNodeVisitor : public NullNodeVisitor {
25 public:
Pre(Node * node)26 GenericGraphVisit::Control Pre(Node* node) {
27 printf("NODE ID: %d\n", node->id());
28 nodes_.push_back(node);
29 return GenericGraphVisit::CONTINUE;
30 }
31 std::vector<Node*> nodes_;
32 };
33
34
35 class PostNodeVisitor : public NullNodeVisitor {
36 public:
Post(Node * node)37 GenericGraphVisit::Control Post(Node* node) {
38 printf("NODE ID: %d\n", node->id());
39 nodes_.push_back(node);
40 return GenericGraphVisit::CONTINUE;
41 }
42 std::vector<Node*> nodes_;
43 };
44
45
TEST(TestUseNodeVisitEmpty)46 TEST(TestUseNodeVisitEmpty) {
47 GraphWithStartNodeTester graph;
48
49 PreNodeVisitor node_visitor;
50 graph.VisitNodeUsesFromStart(&node_visitor);
51
52 CHECK_EQ(1, static_cast<int>(node_visitor.nodes_.size()));
53 }
54
55
TEST(TestUseNodePreOrderVisitSimple)56 TEST(TestUseNodePreOrderVisitSimple) {
57 GraphWithStartNodeTester graph;
58 Node* n2 = graph.NewNode(&dummy_operator, graph.start());
59 Node* n3 = graph.NewNode(&dummy_operator, n2);
60 Node* n4 = graph.NewNode(&dummy_operator, n2, n3);
61 Node* n5 = graph.NewNode(&dummy_operator, n4, n2);
62 graph.SetEnd(n5);
63
64 PreNodeVisitor node_visitor;
65 graph.VisitNodeUsesFromStart(&node_visitor);
66
67 CHECK_EQ(5, static_cast<int>(node_visitor.nodes_.size()));
68 CHECK(graph.start()->id() == node_visitor.nodes_[0]->id());
69 CHECK(n2->id() == node_visitor.nodes_[1]->id());
70 CHECK(n3->id() == node_visitor.nodes_[2]->id());
71 CHECK(n4->id() == node_visitor.nodes_[3]->id());
72 CHECK(n5->id() == node_visitor.nodes_[4]->id());
73 }
74
75
TEST(TestInputNodePreOrderVisitSimple)76 TEST(TestInputNodePreOrderVisitSimple) {
77 GraphWithStartNodeTester graph;
78 Node* n2 = graph.NewNode(&dummy_operator, graph.start());
79 Node* n3 = graph.NewNode(&dummy_operator, n2);
80 Node* n4 = graph.NewNode(&dummy_operator, n2, n3);
81 Node* n5 = graph.NewNode(&dummy_operator, n4, n2);
82 graph.SetEnd(n5);
83
84 PreNodeVisitor node_visitor;
85 graph.VisitNodeInputsFromEnd(&node_visitor);
86 CHECK_EQ(5, static_cast<int>(node_visitor.nodes_.size()));
87 CHECK(n5->id() == node_visitor.nodes_[0]->id());
88 CHECK(n4->id() == node_visitor.nodes_[1]->id());
89 CHECK(n2->id() == node_visitor.nodes_[2]->id());
90 CHECK(graph.start()->id() == node_visitor.nodes_[3]->id());
91 CHECK(n3->id() == node_visitor.nodes_[4]->id());
92 }
93
94
TEST(TestUseNodePostOrderVisitSimple)95 TEST(TestUseNodePostOrderVisitSimple) {
96 GraphWithStartNodeTester graph;
97 Node* n2 = graph.NewNode(&dummy_operator, graph.start());
98 Node* n3 = graph.NewNode(&dummy_operator, graph.start());
99 Node* n4 = graph.NewNode(&dummy_operator, n2);
100 Node* n5 = graph.NewNode(&dummy_operator, n2);
101 Node* n6 = graph.NewNode(&dummy_operator, n2);
102 Node* n7 = graph.NewNode(&dummy_operator, n3);
103 Node* end_dependencies[4] = {n4, n5, n6, n7};
104 Node* n8 = graph.NewNode(&dummy_operator, 4, end_dependencies);
105 graph.SetEnd(n8);
106
107 PostNodeVisitor node_visitor;
108 graph.VisitNodeUsesFromStart(&node_visitor);
109
110 CHECK_EQ(8, static_cast<int>(node_visitor.nodes_.size()));
111 CHECK(graph.end()->id() == node_visitor.nodes_[0]->id());
112 CHECK(n4->id() == node_visitor.nodes_[1]->id());
113 CHECK(n5->id() == node_visitor.nodes_[2]->id());
114 CHECK(n6->id() == node_visitor.nodes_[3]->id());
115 CHECK(n2->id() == node_visitor.nodes_[4]->id());
116 CHECK(n7->id() == node_visitor.nodes_[5]->id());
117 CHECK(n3->id() == node_visitor.nodes_[6]->id());
118 CHECK(graph.start()->id() == node_visitor.nodes_[7]->id());
119 }
120
121
TEST(TestUseNodePostOrderVisitLong)122 TEST(TestUseNodePostOrderVisitLong) {
123 GraphWithStartNodeTester graph;
124 Node* n2 = graph.NewNode(&dummy_operator, graph.start());
125 Node* n3 = graph.NewNode(&dummy_operator, graph.start());
126 Node* n4 = graph.NewNode(&dummy_operator, n2);
127 Node* n5 = graph.NewNode(&dummy_operator, n2);
128 Node* n6 = graph.NewNode(&dummy_operator, n3);
129 Node* n7 = graph.NewNode(&dummy_operator, n3);
130 Node* n8 = graph.NewNode(&dummy_operator, n5);
131 Node* n9 = graph.NewNode(&dummy_operator, n5);
132 Node* n10 = graph.NewNode(&dummy_operator, n9);
133 Node* n11 = graph.NewNode(&dummy_operator, n9);
134 Node* end_dependencies[6] = {n4, n8, n10, n11, n6, n7};
135 Node* n12 = graph.NewNode(&dummy_operator, 6, end_dependencies);
136 graph.SetEnd(n12);
137
138 PostNodeVisitor node_visitor;
139 graph.VisitNodeUsesFromStart(&node_visitor);
140
141 CHECK_EQ(12, static_cast<int>(node_visitor.nodes_.size()));
142 CHECK(graph.end()->id() == node_visitor.nodes_[0]->id());
143 CHECK(n4->id() == node_visitor.nodes_[1]->id());
144 CHECK(n8->id() == node_visitor.nodes_[2]->id());
145 CHECK(n10->id() == node_visitor.nodes_[3]->id());
146 CHECK(n11->id() == node_visitor.nodes_[4]->id());
147 CHECK(n9->id() == node_visitor.nodes_[5]->id());
148 CHECK(n5->id() == node_visitor.nodes_[6]->id());
149 CHECK(n2->id() == node_visitor.nodes_[7]->id());
150 CHECK(n6->id() == node_visitor.nodes_[8]->id());
151 CHECK(n7->id() == node_visitor.nodes_[9]->id());
152 CHECK(n3->id() == node_visitor.nodes_[10]->id());
153 CHECK(graph.start()->id() == node_visitor.nodes_[11]->id());
154 }
155
156
TEST(TestUseNodePreOrderVisitCycle)157 TEST(TestUseNodePreOrderVisitCycle) {
158 GraphWithStartNodeTester graph;
159 Node* n0 = graph.start_node();
160 Node* n1 = graph.NewNode(&dummy_operator, n0);
161 Node* n2 = graph.NewNode(&dummy_operator, n1);
162 n0->AppendInput(graph.main_zone(), n2);
163 graph.SetStart(n0);
164 graph.SetEnd(n2);
165
166 PreNodeVisitor node_visitor;
167 graph.VisitNodeUsesFromStart(&node_visitor);
168
169 CHECK_EQ(3, static_cast<int>(node_visitor.nodes_.size()));
170 CHECK(n0->id() == node_visitor.nodes_[0]->id());
171 CHECK(n1->id() == node_visitor.nodes_[1]->id());
172 CHECK(n2->id() == node_visitor.nodes_[2]->id());
173 }
174
175
176 struct ReenterNodeVisitor : NullNodeVisitor {
PreReenterNodeVisitor177 GenericGraphVisit::Control Pre(Node* node) {
178 printf("[%d] PRE NODE: %d\n", static_cast<int>(nodes_.size()), node->id());
179 nodes_.push_back(node->id());
180 int size = static_cast<int>(nodes_.size());
181 switch (node->id()) {
182 case 0:
183 return size < 6 ? GenericGraphVisit::REENTER : GenericGraphVisit::SKIP;
184 case 1:
185 return size < 4 ? GenericGraphVisit::DEFER
186 : GenericGraphVisit::CONTINUE;
187 default:
188 return GenericGraphVisit::REENTER;
189 }
190 }
191
PostReenterNodeVisitor192 GenericGraphVisit::Control Post(Node* node) {
193 printf("[%d] POST NODE: %d\n", static_cast<int>(nodes_.size()), node->id());
194 nodes_.push_back(-node->id());
195 return node->id() == 4 ? GenericGraphVisit::REENTER
196 : GenericGraphVisit::CONTINUE;
197 }
198
PreEdgeReenterNodeVisitor199 void PreEdge(Node* from, int index, Node* to) {
200 printf("[%d] PRE EDGE: %d-%d\n", static_cast<int>(edges_.size()),
201 from->id(), to->id());
202 edges_.push_back(std::make_pair(from->id(), to->id()));
203 }
204
PostEdgeReenterNodeVisitor205 void PostEdge(Node* from, int index, Node* to) {
206 printf("[%d] POST EDGE: %d-%d\n", static_cast<int>(edges_.size()),
207 from->id(), to->id());
208 edges_.push_back(std::make_pair(-from->id(), -to->id()));
209 }
210
211 std::vector<int> nodes_;
212 std::vector<std::pair<int, int> > edges_;
213 };
214
215
TEST(TestUseNodeReenterVisit)216 TEST(TestUseNodeReenterVisit) {
217 GraphWithStartNodeTester graph;
218 Node* n0 = graph.start_node();
219 Node* n1 = graph.NewNode(&dummy_operator, n0);
220 Node* n2 = graph.NewNode(&dummy_operator, n0);
221 Node* n3 = graph.NewNode(&dummy_operator, n2);
222 Node* n4 = graph.NewNode(&dummy_operator, n0);
223 Node* n5 = graph.NewNode(&dummy_operator, n4);
224 n0->AppendInput(graph.main_zone(), n3);
225 graph.SetStart(n0);
226 graph.SetEnd(n5);
227
228 ReenterNodeVisitor visitor;
229 graph.VisitNodeUsesFromStart(&visitor);
230
231 CHECK_EQ(22, static_cast<int>(visitor.nodes_.size()));
232 CHECK_EQ(24, static_cast<int>(visitor.edges_.size()));
233
234 CHECK(n0->id() == visitor.nodes_[0]);
235 CHECK(n0->id() == visitor.edges_[0].first);
236 CHECK(n1->id() == visitor.edges_[0].second);
237 CHECK(n1->id() == visitor.nodes_[1]);
238 // N1 is deferred.
239 CHECK(-n1->id() == visitor.edges_[1].second);
240 CHECK(-n0->id() == visitor.edges_[1].first);
241 CHECK(n0->id() == visitor.edges_[2].first);
242 CHECK(n2->id() == visitor.edges_[2].second);
243 CHECK(n2->id() == visitor.nodes_[2]);
244 CHECK(n2->id() == visitor.edges_[3].first);
245 CHECK(n3->id() == visitor.edges_[3].second);
246 CHECK(n3->id() == visitor.nodes_[3]);
247 // Circle back to N0, which we may reenter for now.
248 CHECK(n3->id() == visitor.edges_[4].first);
249 CHECK(n0->id() == visitor.edges_[4].second);
250 CHECK(n0->id() == visitor.nodes_[4]);
251 CHECK(n0->id() == visitor.edges_[5].first);
252 CHECK(n1->id() == visitor.edges_[5].second);
253 CHECK(n1->id() == visitor.nodes_[5]);
254 // This time N1 is no longer deferred.
255 CHECK(-n1->id() == visitor.nodes_[6]);
256 CHECK(-n1->id() == visitor.edges_[6].second);
257 CHECK(-n0->id() == visitor.edges_[6].first);
258 CHECK(n0->id() == visitor.edges_[7].first);
259 CHECK(n2->id() == visitor.edges_[7].second);
260 CHECK(n2->id() == visitor.nodes_[7]);
261 CHECK(n2->id() == visitor.edges_[8].first);
262 CHECK(n3->id() == visitor.edges_[8].second);
263 CHECK(n3->id() == visitor.nodes_[8]);
264 CHECK(n3->id() == visitor.edges_[9].first);
265 CHECK(n0->id() == visitor.edges_[9].second);
266 CHECK(n0->id() == visitor.nodes_[9]);
267 // This time we break at N0 and skip it.
268 CHECK(-n0->id() == visitor.edges_[10].second);
269 CHECK(-n3->id() == visitor.edges_[10].first);
270 CHECK(-n3->id() == visitor.nodes_[10]);
271 CHECK(-n3->id() == visitor.edges_[11].second);
272 CHECK(-n2->id() == visitor.edges_[11].first);
273 CHECK(-n2->id() == visitor.nodes_[11]);
274 CHECK(-n2->id() == visitor.edges_[12].second);
275 CHECK(-n0->id() == visitor.edges_[12].first);
276 CHECK(n0->id() == visitor.edges_[13].first);
277 CHECK(n4->id() == visitor.edges_[13].second);
278 CHECK(n4->id() == visitor.nodes_[12]);
279 CHECK(n4->id() == visitor.edges_[14].first);
280 CHECK(n5->id() == visitor.edges_[14].second);
281 CHECK(n5->id() == visitor.nodes_[13]);
282 CHECK(-n5->id() == visitor.nodes_[14]);
283 CHECK(-n5->id() == visitor.edges_[15].second);
284 CHECK(-n4->id() == visitor.edges_[15].first);
285 CHECK(-n4->id() == visitor.nodes_[15]);
286 CHECK(-n4->id() == visitor.edges_[16].second);
287 CHECK(-n0->id() == visitor.edges_[16].first);
288 CHECK(-n0->id() == visitor.nodes_[16]);
289 CHECK(-n0->id() == visitor.edges_[17].second);
290 CHECK(-n3->id() == visitor.edges_[17].first);
291 CHECK(-n3->id() == visitor.nodes_[17]);
292 CHECK(-n3->id() == visitor.edges_[18].second);
293 CHECK(-n2->id() == visitor.edges_[18].first);
294 CHECK(-n2->id() == visitor.nodes_[18]);
295 CHECK(-n2->id() == visitor.edges_[19].second);
296 CHECK(-n0->id() == visitor.edges_[19].first);
297 // N4 may be reentered.
298 CHECK(n0->id() == visitor.edges_[20].first);
299 CHECK(n4->id() == visitor.edges_[20].second);
300 CHECK(n4->id() == visitor.nodes_[19]);
301 CHECK(n4->id() == visitor.edges_[21].first);
302 CHECK(n5->id() == visitor.edges_[21].second);
303 CHECK(-n5->id() == visitor.edges_[22].second);
304 CHECK(-n4->id() == visitor.edges_[22].first);
305 CHECK(-n4->id() == visitor.nodes_[20]);
306 CHECK(-n4->id() == visitor.edges_[23].second);
307 CHECK(-n0->id() == visitor.edges_[23].first);
308 CHECK(-n0->id() == visitor.nodes_[21]);
309 }
310
311
TEST(TestPrintNodeGraphToNodeGraphviz)312 TEST(TestPrintNodeGraphToNodeGraphviz) {
313 GraphWithStartNodeTester graph;
314 Node* n2 = graph.NewNode(&dummy_operator, graph.start());
315 Node* n3 = graph.NewNode(&dummy_operator, graph.start());
316 Node* n4 = graph.NewNode(&dummy_operator, n2);
317 Node* n5 = graph.NewNode(&dummy_operator, n2);
318 Node* n6 = graph.NewNode(&dummy_operator, n3);
319 Node* n7 = graph.NewNode(&dummy_operator, n3);
320 Node* n8 = graph.NewNode(&dummy_operator, n5);
321 Node* n9 = graph.NewNode(&dummy_operator, n5);
322 Node* n10 = graph.NewNode(&dummy_operator, n9);
323 Node* n11 = graph.NewNode(&dummy_operator, n9);
324 Node* end_dependencies[6] = {n4, n8, n10, n11, n6, n7};
325 Node* n12 = graph.NewNode(&dummy_operator, 6, end_dependencies);
326 graph.SetEnd(n12);
327
328 OFStream os(stdout);
329 os << AsDOT(graph);
330 }
331