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
18using namespace v8::internal;
19using namespace v8::internal::compiler;
20
21static SimpleOperator dummy_operator(IrOpcode::kParameter, Operator::kNoWrite,
22                                     0, 0, "dummy");
23
24class PreNodeVisitor : public NullNodeVisitor {
25 public:
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
35class PostNodeVisitor : public NullNodeVisitor {
36 public:
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
46TEST(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
56TEST(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
76TEST(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
95TEST(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
122TEST(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
157TEST(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
176struct ReenterNodeVisitor : NullNodeVisitor {
177  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
192  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
199  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
205  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
216TEST(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
312TEST(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