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: 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: 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 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 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 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 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 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 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 { 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 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 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
