Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(572)

Unified Diff: test/cctest/compiler/test-node-algorithm.cc

Issue 426233002: Land the Fan (disabled) (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: Review feedback, rebase and "git cl format" Created 6 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « test/cctest/compiler/test-node.cc ('k') | test/cctest/compiler/test-node-cache.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: test/cctest/compiler/test-node-algorithm.cc
diff --git a/test/cctest/compiler/test-node-algorithm.cc b/test/cctest/compiler/test-node-algorithm.cc
new file mode 100644
index 0000000000000000000000000000000000000000..ac8fbb9200969b1af32bb5286ebeca8f43a22604
--- /dev/null
+++ b/test/cctest/compiler/test-node-algorithm.cc
@@ -0,0 +1,330 @@
+// Copyright 2013 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <vector>
+
+#include "src/v8.h"
+
+#include "graph-tester.h"
+#include "src/compiler/common-operator.h"
+#include "src/compiler/generic-node.h"
+#include "src/compiler/generic-node-inl.h"
+#include "src/compiler/graph.h"
+#include "src/compiler/graph-inl.h"
+#include "src/compiler/graph-visualizer.h"
+#include "src/compiler/operator.h"
+
+using namespace v8::internal;
+using namespace v8::internal::compiler;
+
+static SimpleOperator dummy_operator(IrOpcode::kParameter, Operator::kNoWrite,
+ 0, 0, "dummy");
+
+class PreNodeVisitor : public NullNodeVisitor {
+ public:
+ GenericGraphVisit::Control Pre(Node* node) {
+ printf("NODE ID: %d\n", node->id());
+ nodes_.push_back(node);
+ return GenericGraphVisit::CONTINUE;
+ }
+ std::vector<Node*> nodes_;
+};
+
+
+class PostNodeVisitor : public NullNodeVisitor {
+ public:
+ GenericGraphVisit::Control Post(Node* node) {
+ printf("NODE ID: %d\n", node->id());
+ nodes_.push_back(node);
+ return GenericGraphVisit::CONTINUE;
+ }
+ std::vector<Node*> nodes_;
+};
+
+
+TEST(TestUseNodeVisitEmpty) {
+ GraphWithStartNodeTester graph;
+
+ PreNodeVisitor node_visitor;
+ graph.VisitNodeUsesFromStart(&node_visitor);
+
+ CHECK_EQ(1, node_visitor.nodes_.size());
+}
+
+
+TEST(TestUseNodePreOrderVisitSimple) {
+ GraphWithStartNodeTester graph;
+ Node* n2 = graph.NewNode(&dummy_operator, graph.start());
+ Node* n3 = graph.NewNode(&dummy_operator, n2);
+ Node* n4 = graph.NewNode(&dummy_operator, n2, n3);
+ Node* n5 = graph.NewNode(&dummy_operator, n4, n2);
+ graph.SetEnd(n5);
+
+ PreNodeVisitor node_visitor;
+ graph.VisitNodeUsesFromStart(&node_visitor);
+
+ CHECK_EQ(5, node_visitor.nodes_.size());
+ CHECK(graph.start()->id() == node_visitor.nodes_[0]->id());
+ CHECK(n2->id() == node_visitor.nodes_[1]->id());
+ CHECK(n3->id() == node_visitor.nodes_[2]->id());
+ CHECK(n4->id() == node_visitor.nodes_[3]->id());
+ CHECK(n5->id() == node_visitor.nodes_[4]->id());
+}
+
+
+TEST(TestInputNodePreOrderVisitSimple) {
+ GraphWithStartNodeTester graph;
+ Node* n2 = graph.NewNode(&dummy_operator, graph.start());
+ Node* n3 = graph.NewNode(&dummy_operator, n2);
+ Node* n4 = graph.NewNode(&dummy_operator, n2, n3);
+ Node* n5 = graph.NewNode(&dummy_operator, n4, n2);
+ graph.SetEnd(n5);
+
+ PreNodeVisitor node_visitor;
+ graph.VisitNodeInputsFromEnd(&node_visitor);
+ CHECK_EQ(5, node_visitor.nodes_.size());
+ CHECK(n5->id() == node_visitor.nodes_[0]->id());
+ CHECK(n4->id() == node_visitor.nodes_[1]->id());
+ CHECK(n2->id() == node_visitor.nodes_[2]->id());
+ CHECK(graph.start()->id() == node_visitor.nodes_[3]->id());
+ CHECK(n3->id() == node_visitor.nodes_[4]->id());
+}
+
+
+TEST(TestUseNodePostOrderVisitSimple) {
+ GraphWithStartNodeTester graph;
+ Node* n2 = graph.NewNode(&dummy_operator, graph.start());
+ Node* n3 = graph.NewNode(&dummy_operator, graph.start());
+ Node* n4 = graph.NewNode(&dummy_operator, n2);
+ Node* n5 = graph.NewNode(&dummy_operator, n2);
+ Node* n6 = graph.NewNode(&dummy_operator, n2);
+ Node* n7 = graph.NewNode(&dummy_operator, n3);
+ Node* end_dependencies[4] = {n4, n5, n6, n7};
+ Node* n8 = graph.NewNode(&dummy_operator, 4, end_dependencies);
+ graph.SetEnd(n8);
+
+ PostNodeVisitor node_visitor;
+ graph.VisitNodeUsesFromStart(&node_visitor);
+
+ CHECK_EQ(8, node_visitor.nodes_.size());
+ CHECK(graph.end()->id() == node_visitor.nodes_[0]->id());
+ CHECK(n4->id() == node_visitor.nodes_[1]->id());
+ CHECK(n5->id() == node_visitor.nodes_[2]->id());
+ CHECK(n6->id() == node_visitor.nodes_[3]->id());
+ CHECK(n2->id() == node_visitor.nodes_[4]->id());
+ CHECK(n7->id() == node_visitor.nodes_[5]->id());
+ CHECK(n3->id() == node_visitor.nodes_[6]->id());
+ CHECK(graph.start()->id() == node_visitor.nodes_[7]->id());
+}
+
+
+TEST(TestUseNodePostOrderVisitLong) {
+ GraphWithStartNodeTester graph;
+ Node* n2 = graph.NewNode(&dummy_operator, graph.start());
+ Node* n3 = graph.NewNode(&dummy_operator, graph.start());
+ Node* n4 = graph.NewNode(&dummy_operator, n2);
+ Node* n5 = graph.NewNode(&dummy_operator, n2);
+ Node* n6 = graph.NewNode(&dummy_operator, n3);
+ Node* n7 = graph.NewNode(&dummy_operator, n3);
+ Node* n8 = graph.NewNode(&dummy_operator, n5);
+ Node* n9 = graph.NewNode(&dummy_operator, n5);
+ Node* n10 = graph.NewNode(&dummy_operator, n9);
+ Node* n11 = graph.NewNode(&dummy_operator, n9);
+ Node* end_dependencies[6] = {n4, n8, n10, n11, n6, n7};
+ Node* n12 = graph.NewNode(&dummy_operator, 6, end_dependencies);
+ graph.SetEnd(n12);
+
+ PostNodeVisitor node_visitor;
+ graph.VisitNodeUsesFromStart(&node_visitor);
+
+ CHECK_EQ(12, node_visitor.nodes_.size());
+ CHECK(graph.end()->id() == node_visitor.nodes_[0]->id());
+ CHECK(n4->id() == node_visitor.nodes_[1]->id());
+ CHECK(n8->id() == node_visitor.nodes_[2]->id());
+ CHECK(n10->id() == node_visitor.nodes_[3]->id());
+ CHECK(n11->id() == node_visitor.nodes_[4]->id());
+ CHECK(n9->id() == node_visitor.nodes_[5]->id());
+ CHECK(n5->id() == node_visitor.nodes_[6]->id());
+ CHECK(n2->id() == node_visitor.nodes_[7]->id());
+ CHECK(n6->id() == node_visitor.nodes_[8]->id());
+ CHECK(n7->id() == node_visitor.nodes_[9]->id());
+ CHECK(n3->id() == node_visitor.nodes_[10]->id());
+ CHECK(graph.start()->id() == node_visitor.nodes_[11]->id());
+}
+
+
+TEST(TestUseNodePreOrderVisitCycle) {
+ GraphWithStartNodeTester graph;
+ Node* n0 = graph.start_node();
+ Node* n1 = graph.NewNode(&dummy_operator, n0);
+ Node* n2 = graph.NewNode(&dummy_operator, n1);
+ n0->AppendInput(graph.main_zone(), n2);
+ graph.SetStart(n0);
+ graph.SetEnd(n2);
+
+ PreNodeVisitor node_visitor;
+ graph.VisitNodeUsesFromStart(&node_visitor);
+
+ CHECK_EQ(3, node_visitor.nodes_.size());
+ CHECK(n0->id() == node_visitor.nodes_[0]->id());
+ CHECK(n1->id() == node_visitor.nodes_[1]->id());
+ CHECK(n2->id() == node_visitor.nodes_[2]->id());
+}
+
+
+struct ReenterNodeVisitor : NullNodeVisitor {
+ GenericGraphVisit::Control Pre(Node* node) {
+ printf("[%d] PRE NODE: %d\n", static_cast<int>(nodes_.size()), node->id());
+ nodes_.push_back(node->id());
+ int size = nodes_.size();
+ switch (node->id()) {
+ case 0:
+ return size < 6 ? GenericGraphVisit::REENTER : GenericGraphVisit::SKIP;
+ case 1:
+ return size < 4 ? GenericGraphVisit::DEFER
+ : GenericGraphVisit::CONTINUE;
+ default:
+ return GenericGraphVisit::REENTER;
+ }
+ }
+
+ GenericGraphVisit::Control Post(Node* node) {
+ printf("[%d] POST NODE: %d\n", static_cast<int>(nodes_.size()), node->id());
+ nodes_.push_back(-node->id());
+ return node->id() == 4 ? GenericGraphVisit::REENTER
+ : GenericGraphVisit::CONTINUE;
+ }
+
+ void PreEdge(Node* from, int index, Node* to) {
+ printf("[%d] PRE EDGE: %d-%d\n", static_cast<int>(edges_.size()),
+ from->id(), to->id());
+ edges_.push_back(std::make_pair(from->id(), to->id()));
+ }
+
+ void PostEdge(Node* from, int index, Node* to) {
+ printf("[%d] POST EDGE: %d-%d\n", static_cast<int>(edges_.size()),
+ from->id(), to->id());
+ edges_.push_back(std::make_pair(-from->id(), -to->id()));
+ }
+
+ std::vector<int> nodes_;
+ std::vector<std::pair<int, int> > edges_;
+};
+
+
+TEST(TestUseNodeReenterVisit) {
+ GraphWithStartNodeTester graph;
+ Node* n0 = graph.start_node();
+ Node* n1 = graph.NewNode(&dummy_operator, n0);
+ Node* n2 = graph.NewNode(&dummy_operator, n0);
+ Node* n3 = graph.NewNode(&dummy_operator, n2);
+ Node* n4 = graph.NewNode(&dummy_operator, n0);
+ Node* n5 = graph.NewNode(&dummy_operator, n4);
+ n0->AppendInput(graph.main_zone(), n3);
+ graph.SetStart(n0);
+ graph.SetEnd(n5);
+
+ ReenterNodeVisitor visitor;
+ graph.VisitNodeUsesFromStart(&visitor);
+
+ CHECK_EQ(22, visitor.nodes_.size());
+ CHECK_EQ(24, visitor.edges_.size());
+
+ CHECK(n0->id() == visitor.nodes_[0]);
+ CHECK(n0->id() == visitor.edges_[0].first);
+ CHECK(n1->id() == visitor.edges_[0].second);
+ CHECK(n1->id() == visitor.nodes_[1]);
+ // N1 is deferred.
+ CHECK(-n1->id() == visitor.edges_[1].second);
+ CHECK(-n0->id() == visitor.edges_[1].first);
+ CHECK(n0->id() == visitor.edges_[2].first);
+ CHECK(n2->id() == visitor.edges_[2].second);
+ CHECK(n2->id() == visitor.nodes_[2]);
+ CHECK(n2->id() == visitor.edges_[3].first);
+ CHECK(n3->id() == visitor.edges_[3].second);
+ CHECK(n3->id() == visitor.nodes_[3]);
+ // Circle back to N0, which we may reenter for now.
+ CHECK(n3->id() == visitor.edges_[4].first);
+ CHECK(n0->id() == visitor.edges_[4].second);
+ CHECK(n0->id() == visitor.nodes_[4]);
+ CHECK(n0->id() == visitor.edges_[5].first);
+ CHECK(n1->id() == visitor.edges_[5].second);
+ CHECK(n1->id() == visitor.nodes_[5]);
+ // This time N1 is no longer deferred.
+ CHECK(-n1->id() == visitor.nodes_[6]);
+ CHECK(-n1->id() == visitor.edges_[6].second);
+ CHECK(-n0->id() == visitor.edges_[6].first);
+ CHECK(n0->id() == visitor.edges_[7].first);
+ CHECK(n2->id() == visitor.edges_[7].second);
+ CHECK(n2->id() == visitor.nodes_[7]);
+ CHECK(n2->id() == visitor.edges_[8].first);
+ CHECK(n3->id() == visitor.edges_[8].second);
+ CHECK(n3->id() == visitor.nodes_[8]);
+ CHECK(n3->id() == visitor.edges_[9].first);
+ CHECK(n0->id() == visitor.edges_[9].second);
+ CHECK(n0->id() == visitor.nodes_[9]);
+ // This time we break at N0 and skip it.
+ CHECK(-n0->id() == visitor.edges_[10].second);
+ CHECK(-n3->id() == visitor.edges_[10].first);
+ CHECK(-n3->id() == visitor.nodes_[10]);
+ CHECK(-n3->id() == visitor.edges_[11].second);
+ CHECK(-n2->id() == visitor.edges_[11].first);
+ CHECK(-n2->id() == visitor.nodes_[11]);
+ CHECK(-n2->id() == visitor.edges_[12].second);
+ CHECK(-n0->id() == visitor.edges_[12].first);
+ CHECK(n0->id() == visitor.edges_[13].first);
+ CHECK(n4->id() == visitor.edges_[13].second);
+ CHECK(n4->id() == visitor.nodes_[12]);
+ CHECK(n4->id() == visitor.edges_[14].first);
+ CHECK(n5->id() == visitor.edges_[14].second);
+ CHECK(n5->id() == visitor.nodes_[13]);
+ CHECK(-n5->id() == visitor.nodes_[14]);
+ CHECK(-n5->id() == visitor.edges_[15].second);
+ CHECK(-n4->id() == visitor.edges_[15].first);
+ CHECK(-n4->id() == visitor.nodes_[15]);
+ CHECK(-n4->id() == visitor.edges_[16].second);
+ CHECK(-n0->id() == visitor.edges_[16].first);
+ CHECK(-n0->id() == visitor.nodes_[16]);
+ CHECK(-n0->id() == visitor.edges_[17].second);
+ CHECK(-n3->id() == visitor.edges_[17].first);
+ CHECK(-n3->id() == visitor.nodes_[17]);
+ CHECK(-n3->id() == visitor.edges_[18].second);
+ CHECK(-n2->id() == visitor.edges_[18].first);
+ CHECK(-n2->id() == visitor.nodes_[18]);
+ CHECK(-n2->id() == visitor.edges_[19].second);
+ CHECK(-n0->id() == visitor.edges_[19].first);
+ // N4 may be reentered.
+ CHECK(n0->id() == visitor.edges_[20].first);
+ CHECK(n4->id() == visitor.edges_[20].second);
+ CHECK(n4->id() == visitor.nodes_[19]);
+ CHECK(n4->id() == visitor.edges_[21].first);
+ CHECK(n5->id() == visitor.edges_[21].second);
+ CHECK(-n5->id() == visitor.edges_[22].second);
+ CHECK(-n4->id() == visitor.edges_[22].first);
+ CHECK(-n4->id() == visitor.nodes_[20]);
+ CHECK(-n4->id() == visitor.edges_[23].second);
+ CHECK(-n0->id() == visitor.edges_[23].first);
+ CHECK(-n0->id() == visitor.nodes_[21]);
+}
+
+
+TEST(TestPrintNodeGraphToNodeGraphviz) {
+ GraphWithStartNodeTester graph;
+ Node* n2 = graph.NewNode(&dummy_operator, graph.start());
+ Node* n3 = graph.NewNode(&dummy_operator, graph.start());
+ Node* n4 = graph.NewNode(&dummy_operator, n2);
+ Node* n5 = graph.NewNode(&dummy_operator, n2);
+ Node* n6 = graph.NewNode(&dummy_operator, n3);
+ Node* n7 = graph.NewNode(&dummy_operator, n3);
+ Node* n8 = graph.NewNode(&dummy_operator, n5);
+ Node* n9 = graph.NewNode(&dummy_operator, n5);
+ Node* n10 = graph.NewNode(&dummy_operator, n9);
+ Node* n11 = graph.NewNode(&dummy_operator, n9);
+ Node* end_dependencies[6] = {n4, n8, n10, n11, n6, n7};
+ Node* n12 = graph.NewNode(&dummy_operator, 6, end_dependencies);
+ graph.SetEnd(n12);
+
+ OFStream os(stdout);
+ os << AsDOT(graph);
+}
« no previous file with comments | « test/cctest/compiler/test-node.cc ('k') | test/cctest/compiler/test-node-cache.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698