src/v8/test/cctest/compiler/test-node-algorithm.cc

   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 Operator dummy_operator(IrOpcode::kParameter, Operator::kNoWrite,
  22                                "dummy", 0, 0, 0, 1, 0, 0);
  23
  24 class PreNodeVisitor : public NullNodeVisitor {
  25  public:
  26   void Pre(Node* node) {
  27     printf("NODE ID: %d\n", node->id());
  28     nodes_.push_back(node);
  29   }
  30   std::vector<Node*> nodes_;
  31 };
  32
  33
  34 class PostNodeVisitor : public NullNodeVisitor {
  35  public:
  36   void Post(Node* node) {
  37     printf("NODE ID: %d\n", node->id());
  38     nodes_.push_back(node);
  39   }
  40   std::vector<Node*> nodes_;
  41 };
  42
  43
  44 TEST(TestUseNodeVisitEmpty) {
  45   GraphWithStartNodeTester graph;
  46
  47   PreNodeVisitor node_visitor;
  48   graph.VisitNodeUsesFromStart(&node_visitor);
  49
  50   CHECK_EQ(1, static_cast<int>(node_visitor.nodes_.size()));
  51 }
  52
  53
  54 TEST(TestUseNodePreOrderVisitSimple) {
  55   GraphWithStartNodeTester graph;
  56   Node* n2 = graph.NewNode(&dummy_operator, graph.start());
  57   Node* n3 = graph.NewNode(&dummy_operator, n2);
  58   Node* n4 = graph.NewNode(&dummy_operator, n2, n3);
  59   Node* n5 = graph.NewNode(&dummy_operator, n4, n2);
  60   graph.SetEnd(n5);
  61
  62   PreNodeVisitor node_visitor;
  63   graph.VisitNodeUsesFromStart(&node_visitor);
  64
  65   CHECK_EQ(5, static_cast<int>(node_visitor.nodes_.size()));
  66   CHECK(graph.start()->id() == node_visitor.nodes_[0]->id());
  67   CHECK(n2->id() == node_visitor.nodes_[1]->id());
  68   CHECK(n3->id() == node_visitor.nodes_[2]->id());
  69   CHECK(n4->id() == node_visitor.nodes_[3]->id());
  70   CHECK(n5->id() == node_visitor.nodes_[4]->id());
  71 }
  72
  73
  74 TEST(TestInputNodePreOrderVisitSimple) {
  75   GraphWithStartNodeTester graph;
  76   Node* n2 = graph.NewNode(&dummy_operator, graph.start());
  77   Node* n3 = graph.NewNode(&dummy_operator, n2);
  78   Node* n4 = graph.NewNode(&dummy_operator, n2, n3);
  79   Node* n5 = graph.NewNode(&dummy_operator, n4, n2);
  80   graph.SetEnd(n5);
  81
  82   PreNodeVisitor node_visitor;
  83   graph.VisitNodeInputsFromEnd(&node_visitor);
  84   CHECK_EQ(5, static_cast<int>(node_visitor.nodes_.size()));
  85   CHECK(n5->id() == node_visitor.nodes_[0]->id());
  86   CHECK(n4->id() == node_visitor.nodes_[1]->id());
  87   CHECK(n2->id() == node_visitor.nodes_[2]->id());
  88   CHECK(graph.start()->id() == node_visitor.nodes_[3]->id());
  89   CHECK(n3->id() == node_visitor.nodes_[4]->id());
  90 }
  91
  92
  93 TEST(TestUseNodePostOrderVisitSimple) {
  94   GraphWithStartNodeTester graph;
  95   Node* n2 = graph.NewNode(&dummy_operator, graph.start());
  96   Node* n3 = graph.NewNode(&dummy_operator, graph.start());
  97   Node* n4 = graph.NewNode(&dummy_operator, n2);
  98   Node* n5 = graph.NewNode(&dummy_operator, n2);
  99   Node* n6 = graph.NewNode(&dummy_operator, n2);
 100   Node* n7 = graph.NewNode(&dummy_operator, n3);
 101   Node* end_dependencies[4] = {n4, n5, n6, n7};
 102   Node* n8 = graph.NewNode(&dummy_operator, 4, end_dependencies);
 103   graph.SetEnd(n8);
 104
 105   PostNodeVisitor node_visitor;
 106   graph.VisitNodeUsesFromStart(&node_visitor);
 107
 108   CHECK_EQ(8, static_cast<int>(node_visitor.nodes_.size()));
 109   CHECK(graph.end()->id() == node_visitor.nodes_[0]->id());
 110   CHECK(n4->id() == node_visitor.nodes_[1]->id());
 111   CHECK(n5->id() == node_visitor.nodes_[2]->id());
 112   CHECK(n6->id() == node_visitor.nodes_[3]->id());
 113   CHECK(n2->id() == node_visitor.nodes_[4]->id());
 114   CHECK(n7->id() == node_visitor.nodes_[5]->id());
 115   CHECK(n3->id() == node_visitor.nodes_[6]->id());
 116   CHECK(graph.start()->id() == node_visitor.nodes_[7]->id());
 117 }
 118
 119
 120 TEST(TestUseNodePostOrderVisitLong) {
 121   GraphWithStartNodeTester graph;
 122   Node* n2 = graph.NewNode(&dummy_operator, graph.start());
 123   Node* n3 = graph.NewNode(&dummy_operator, graph.start());
 124   Node* n4 = graph.NewNode(&dummy_operator, n2);
 125   Node* n5 = graph.NewNode(&dummy_operator, n2);
 126   Node* n6 = graph.NewNode(&dummy_operator, n3);
 127   Node* n7 = graph.NewNode(&dummy_operator, n3);
 128   Node* n8 = graph.NewNode(&dummy_operator, n5);
 129   Node* n9 = graph.NewNode(&dummy_operator, n5);
 130   Node* n10 = graph.NewNode(&dummy_operator, n9);
 131   Node* n11 = graph.NewNode(&dummy_operator, n9);
 132   Node* end_dependencies[6] = {n4, n8, n10, n11, n6, n7};
 133   Node* n12 = graph.NewNode(&dummy_operator, 6, end_dependencies);
 134   graph.SetEnd(n12);
 135
 136   PostNodeVisitor node_visitor;
 137   graph.VisitNodeUsesFromStart(&node_visitor);
 138
 139   CHECK_EQ(12, static_cast<int>(node_visitor.nodes_.size()));
 140   CHECK(graph.end()->id() == node_visitor.nodes_[0]->id());
 141   CHECK(n4->id() == node_visitor.nodes_[1]->id());
 142   CHECK(n8->id() == node_visitor.nodes_[2]->id());
 143   CHECK(n10->id() == node_visitor.nodes_[3]->id());
 144   CHECK(n11->id() == node_visitor.nodes_[4]->id());
 145   CHECK(n9->id() == node_visitor.nodes_[5]->id());
 146   CHECK(n5->id() == node_visitor.nodes_[6]->id());
 147   CHECK(n2->id() == node_visitor.nodes_[7]->id());
 148   CHECK(n6->id() == node_visitor.nodes_[8]->id());
 149   CHECK(n7->id() == node_visitor.nodes_[9]->id());
 150   CHECK(n3->id() == node_visitor.nodes_[10]->id());
 151   CHECK(graph.start()->id() == node_visitor.nodes_[11]->id());
 152 }
 153
 154
 155 TEST(TestUseNodePreOrderVisitCycle) {
 156   GraphWithStartNodeTester graph;
 157   Node* n0 = graph.start_node();
 158   Node* n1 = graph.NewNode(&dummy_operator, n0);
 159   Node* n2 = graph.NewNode(&dummy_operator, n1);
 160   n0->AppendInput(graph.main_zone(), n2);
 161   graph.SetStart(n0);
 162   graph.SetEnd(n2);
 163
 164   PreNodeVisitor node_visitor;
 165   graph.VisitNodeUsesFromStart(&node_visitor);
 166
 167   CHECK_EQ(3, static_cast<int>(node_visitor.nodes_.size()));
 168   CHECK(n0->id() == node_visitor.nodes_[0]->id());
 169   CHECK(n1->id() == node_visitor.nodes_[1]->id());
 170   CHECK(n2->id() == node_visitor.nodes_[2]->id());
 171 }
 172
 173
 174 TEST(TestPrintNodeGraphToNodeGraphviz) {
 175   GraphWithStartNodeTester graph;
 176   Node* n2 = graph.NewNode(&dummy_operator, graph.start());
 177   Node* n3 = graph.NewNode(&dummy_operator, graph.start());
 178   Node* n4 = graph.NewNode(&dummy_operator, n2);
 179   Node* n5 = graph.NewNode(&dummy_operator, n2);
 180   Node* n6 = graph.NewNode(&dummy_operator, n3);
 181   Node* n7 = graph.NewNode(&dummy_operator, n3);
 182   Node* n8 = graph.NewNode(&dummy_operator, n5);
 183   Node* n9 = graph.NewNode(&dummy_operator, n5);
 184   Node* n10 = graph.NewNode(&dummy_operator, n9);
 185   Node* n11 = graph.NewNode(&dummy_operator, n9);
 186   Node* end_dependencies[6] = {n4, n8, n10, n11, n6, n7};
 187   Node* n12 = graph.NewNode(&dummy_operator, 6, end_dependencies);
 188   graph.SetEnd(n12);
 189
 190   OFStream os(stdout);
 191   os << AsDOT(graph);
 192 }