| OLD | NEW |
| 1 // Copyright 2013 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #include <vector> | 5 #include <vector> |
| 6 | 6 |
| 7 #include "src/v8.h" | 7 #include "src/v8.h" |
| 8 | 8 |
| 9 #include "graph-tester.h" | 9 #include "graph-tester.h" |
| 10 #include "src/compiler/common-operator.h" | 10 #include "src/compiler/common-operator.h" |
| (...skipping 31 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 42 std::vector<Node*> nodes_; | 42 std::vector<Node*> nodes_; |
| 43 }; | 43 }; |
| 44 | 44 |
| 45 | 45 |
| 46 TEST(TestUseNodeVisitEmpty) { | 46 TEST(TestUseNodeVisitEmpty) { |
| 47 GraphWithStartNodeTester graph; | 47 GraphWithStartNodeTester graph; |
| 48 | 48 |
| 49 PreNodeVisitor node_visitor; | 49 PreNodeVisitor node_visitor; |
| 50 graph.VisitNodeUsesFromStart(&node_visitor); | 50 graph.VisitNodeUsesFromStart(&node_visitor); |
| 51 | 51 |
| 52 CHECK_EQ(1, node_visitor.nodes_.size()); | 52 CHECK_EQ(1, static_cast<int>(node_visitor.nodes_.size())); |
| 53 } | 53 } |
| 54 | 54 |
| 55 | 55 |
| 56 TEST(TestUseNodePreOrderVisitSimple) { | 56 TEST(TestUseNodePreOrderVisitSimple) { |
| 57 GraphWithStartNodeTester graph; | 57 GraphWithStartNodeTester graph; |
| 58 Node* n2 = graph.NewNode(&dummy_operator, graph.start()); | 58 Node* n2 = graph.NewNode(&dummy_operator, graph.start()); |
| 59 Node* n3 = graph.NewNode(&dummy_operator, n2); | 59 Node* n3 = graph.NewNode(&dummy_operator, n2); |
| 60 Node* n4 = graph.NewNode(&dummy_operator, n2, n3); | 60 Node* n4 = graph.NewNode(&dummy_operator, n2, n3); |
| 61 Node* n5 = graph.NewNode(&dummy_operator, n4, n2); | 61 Node* n5 = graph.NewNode(&dummy_operator, n4, n2); |
| 62 graph.SetEnd(n5); | 62 graph.SetEnd(n5); |
| 63 | 63 |
| 64 PreNodeVisitor node_visitor; | 64 PreNodeVisitor node_visitor; |
| 65 graph.VisitNodeUsesFromStart(&node_visitor); | 65 graph.VisitNodeUsesFromStart(&node_visitor); |
| 66 | 66 |
| 67 CHECK_EQ(5, node_visitor.nodes_.size()); | 67 CHECK_EQ(5, static_cast<int>(node_visitor.nodes_.size())); |
| 68 CHECK(graph.start()->id() == node_visitor.nodes_[0]->id()); | 68 CHECK(graph.start()->id() == node_visitor.nodes_[0]->id()); |
| 69 CHECK(n2->id() == node_visitor.nodes_[1]->id()); | 69 CHECK(n2->id() == node_visitor.nodes_[1]->id()); |
| 70 CHECK(n3->id() == node_visitor.nodes_[2]->id()); | 70 CHECK(n3->id() == node_visitor.nodes_[2]->id()); |
| 71 CHECK(n4->id() == node_visitor.nodes_[3]->id()); | 71 CHECK(n4->id() == node_visitor.nodes_[3]->id()); |
| 72 CHECK(n5->id() == node_visitor.nodes_[4]->id()); | 72 CHECK(n5->id() == node_visitor.nodes_[4]->id()); |
| 73 } | 73 } |
| 74 | 74 |
| 75 | 75 |
| 76 TEST(TestInputNodePreOrderVisitSimple) { | 76 TEST(TestInputNodePreOrderVisitSimple) { |
| 77 GraphWithStartNodeTester graph; | 77 GraphWithStartNodeTester graph; |
| 78 Node* n2 = graph.NewNode(&dummy_operator, graph.start()); | 78 Node* n2 = graph.NewNode(&dummy_operator, graph.start()); |
| 79 Node* n3 = graph.NewNode(&dummy_operator, n2); | 79 Node* n3 = graph.NewNode(&dummy_operator, n2); |
| 80 Node* n4 = graph.NewNode(&dummy_operator, n2, n3); | 80 Node* n4 = graph.NewNode(&dummy_operator, n2, n3); |
| 81 Node* n5 = graph.NewNode(&dummy_operator, n4, n2); | 81 Node* n5 = graph.NewNode(&dummy_operator, n4, n2); |
| 82 graph.SetEnd(n5); | 82 graph.SetEnd(n5); |
| 83 | 83 |
| 84 PreNodeVisitor node_visitor; | 84 PreNodeVisitor node_visitor; |
| 85 graph.VisitNodeInputsFromEnd(&node_visitor); | 85 graph.VisitNodeInputsFromEnd(&node_visitor); |
| 86 CHECK_EQ(5, node_visitor.nodes_.size()); | 86 CHECK_EQ(5, static_cast<int>(node_visitor.nodes_.size())); |
| 87 CHECK(n5->id() == node_visitor.nodes_[0]->id()); | 87 CHECK(n5->id() == node_visitor.nodes_[0]->id()); |
| 88 CHECK(n4->id() == node_visitor.nodes_[1]->id()); | 88 CHECK(n4->id() == node_visitor.nodes_[1]->id()); |
| 89 CHECK(n2->id() == node_visitor.nodes_[2]->id()); | 89 CHECK(n2->id() == node_visitor.nodes_[2]->id()); |
| 90 CHECK(graph.start()->id() == node_visitor.nodes_[3]->id()); | 90 CHECK(graph.start()->id() == node_visitor.nodes_[3]->id()); |
| 91 CHECK(n3->id() == node_visitor.nodes_[4]->id()); | 91 CHECK(n3->id() == node_visitor.nodes_[4]->id()); |
| 92 } | 92 } |
| 93 | 93 |
| 94 | 94 |
| 95 TEST(TestUseNodePostOrderVisitSimple) { | 95 TEST(TestUseNodePostOrderVisitSimple) { |
| 96 GraphWithStartNodeTester graph; | 96 GraphWithStartNodeTester graph; |
| 97 Node* n2 = graph.NewNode(&dummy_operator, graph.start()); | 97 Node* n2 = graph.NewNode(&dummy_operator, graph.start()); |
| 98 Node* n3 = graph.NewNode(&dummy_operator, graph.start()); | 98 Node* n3 = graph.NewNode(&dummy_operator, graph.start()); |
| 99 Node* n4 = graph.NewNode(&dummy_operator, n2); | 99 Node* n4 = graph.NewNode(&dummy_operator, n2); |
| 100 Node* n5 = graph.NewNode(&dummy_operator, n2); | 100 Node* n5 = graph.NewNode(&dummy_operator, n2); |
| 101 Node* n6 = graph.NewNode(&dummy_operator, n2); | 101 Node* n6 = graph.NewNode(&dummy_operator, n2); |
| 102 Node* n7 = graph.NewNode(&dummy_operator, n3); | 102 Node* n7 = graph.NewNode(&dummy_operator, n3); |
| 103 Node* end_dependencies[4] = {n4, n5, n6, n7}; | 103 Node* end_dependencies[4] = {n4, n5, n6, n7}; |
| 104 Node* n8 = graph.NewNode(&dummy_operator, 4, end_dependencies); | 104 Node* n8 = graph.NewNode(&dummy_operator, 4, end_dependencies); |
| 105 graph.SetEnd(n8); | 105 graph.SetEnd(n8); |
| 106 | 106 |
| 107 PostNodeVisitor node_visitor; | 107 PostNodeVisitor node_visitor; |
| 108 graph.VisitNodeUsesFromStart(&node_visitor); | 108 graph.VisitNodeUsesFromStart(&node_visitor); |
| 109 | 109 |
| 110 CHECK_EQ(8, node_visitor.nodes_.size()); | 110 CHECK_EQ(8, static_cast<int>(node_visitor.nodes_.size())); |
| 111 CHECK(graph.end()->id() == node_visitor.nodes_[0]->id()); | 111 CHECK(graph.end()->id() == node_visitor.nodes_[0]->id()); |
| 112 CHECK(n4->id() == node_visitor.nodes_[1]->id()); | 112 CHECK(n4->id() == node_visitor.nodes_[1]->id()); |
| 113 CHECK(n5->id() == node_visitor.nodes_[2]->id()); | 113 CHECK(n5->id() == node_visitor.nodes_[2]->id()); |
| 114 CHECK(n6->id() == node_visitor.nodes_[3]->id()); | 114 CHECK(n6->id() == node_visitor.nodes_[3]->id()); |
| 115 CHECK(n2->id() == node_visitor.nodes_[4]->id()); | 115 CHECK(n2->id() == node_visitor.nodes_[4]->id()); |
| 116 CHECK(n7->id() == node_visitor.nodes_[5]->id()); | 116 CHECK(n7->id() == node_visitor.nodes_[5]->id()); |
| 117 CHECK(n3->id() == node_visitor.nodes_[6]->id()); | 117 CHECK(n3->id() == node_visitor.nodes_[6]->id()); |
| 118 CHECK(graph.start()->id() == node_visitor.nodes_[7]->id()); | 118 CHECK(graph.start()->id() == node_visitor.nodes_[7]->id()); |
| 119 } | 119 } |
| 120 | 120 |
| (...skipping 10 matching lines...) Expand all Loading... |
| 131 Node* n9 = graph.NewNode(&dummy_operator, n5); | 131 Node* n9 = graph.NewNode(&dummy_operator, n5); |
| 132 Node* n10 = graph.NewNode(&dummy_operator, n9); | 132 Node* n10 = graph.NewNode(&dummy_operator, n9); |
| 133 Node* n11 = graph.NewNode(&dummy_operator, n9); | 133 Node* n11 = graph.NewNode(&dummy_operator, n9); |
| 134 Node* end_dependencies[6] = {n4, n8, n10, n11, n6, n7}; | 134 Node* end_dependencies[6] = {n4, n8, n10, n11, n6, n7}; |
| 135 Node* n12 = graph.NewNode(&dummy_operator, 6, end_dependencies); | 135 Node* n12 = graph.NewNode(&dummy_operator, 6, end_dependencies); |
| 136 graph.SetEnd(n12); | 136 graph.SetEnd(n12); |
| 137 | 137 |
| 138 PostNodeVisitor node_visitor; | 138 PostNodeVisitor node_visitor; |
| 139 graph.VisitNodeUsesFromStart(&node_visitor); | 139 graph.VisitNodeUsesFromStart(&node_visitor); |
| 140 | 140 |
| 141 CHECK_EQ(12, node_visitor.nodes_.size()); | 141 CHECK_EQ(12, static_cast<int>(node_visitor.nodes_.size())); |
| 142 CHECK(graph.end()->id() == node_visitor.nodes_[0]->id()); | 142 CHECK(graph.end()->id() == node_visitor.nodes_[0]->id()); |
| 143 CHECK(n4->id() == node_visitor.nodes_[1]->id()); | 143 CHECK(n4->id() == node_visitor.nodes_[1]->id()); |
| 144 CHECK(n8->id() == node_visitor.nodes_[2]->id()); | 144 CHECK(n8->id() == node_visitor.nodes_[2]->id()); |
| 145 CHECK(n10->id() == node_visitor.nodes_[3]->id()); | 145 CHECK(n10->id() == node_visitor.nodes_[3]->id()); |
| 146 CHECK(n11->id() == node_visitor.nodes_[4]->id()); | 146 CHECK(n11->id() == node_visitor.nodes_[4]->id()); |
| 147 CHECK(n9->id() == node_visitor.nodes_[5]->id()); | 147 CHECK(n9->id() == node_visitor.nodes_[5]->id()); |
| 148 CHECK(n5->id() == node_visitor.nodes_[6]->id()); | 148 CHECK(n5->id() == node_visitor.nodes_[6]->id()); |
| 149 CHECK(n2->id() == node_visitor.nodes_[7]->id()); | 149 CHECK(n2->id() == node_visitor.nodes_[7]->id()); |
| 150 CHECK(n6->id() == node_visitor.nodes_[8]->id()); | 150 CHECK(n6->id() == node_visitor.nodes_[8]->id()); |
| 151 CHECK(n7->id() == node_visitor.nodes_[9]->id()); | 151 CHECK(n7->id() == node_visitor.nodes_[9]->id()); |
| 152 CHECK(n3->id() == node_visitor.nodes_[10]->id()); | 152 CHECK(n3->id() == node_visitor.nodes_[10]->id()); |
| 153 CHECK(graph.start()->id() == node_visitor.nodes_[11]->id()); | 153 CHECK(graph.start()->id() == node_visitor.nodes_[11]->id()); |
| 154 } | 154 } |
| 155 | 155 |
| 156 | 156 |
| 157 TEST(TestUseNodePreOrderVisitCycle) { | 157 TEST(TestUseNodePreOrderVisitCycle) { |
| 158 GraphWithStartNodeTester graph; | 158 GraphWithStartNodeTester graph; |
| 159 Node* n0 = graph.start_node(); | 159 Node* n0 = graph.start_node(); |
| 160 Node* n1 = graph.NewNode(&dummy_operator, n0); | 160 Node* n1 = graph.NewNode(&dummy_operator, n0); |
| 161 Node* n2 = graph.NewNode(&dummy_operator, n1); | 161 Node* n2 = graph.NewNode(&dummy_operator, n1); |
| 162 n0->AppendInput(graph.main_zone(), n2); | 162 n0->AppendInput(graph.main_zone(), n2); |
| 163 graph.SetStart(n0); | 163 graph.SetStart(n0); |
| 164 graph.SetEnd(n2); | 164 graph.SetEnd(n2); |
| 165 | 165 |
| 166 PreNodeVisitor node_visitor; | 166 PreNodeVisitor node_visitor; |
| 167 graph.VisitNodeUsesFromStart(&node_visitor); | 167 graph.VisitNodeUsesFromStart(&node_visitor); |
| 168 | 168 |
| 169 CHECK_EQ(3, node_visitor.nodes_.size()); | 169 CHECK_EQ(3, static_cast<int>(node_visitor.nodes_.size())); |
| 170 CHECK(n0->id() == node_visitor.nodes_[0]->id()); | 170 CHECK(n0->id() == node_visitor.nodes_[0]->id()); |
| 171 CHECK(n1->id() == node_visitor.nodes_[1]->id()); | 171 CHECK(n1->id() == node_visitor.nodes_[1]->id()); |
| 172 CHECK(n2->id() == node_visitor.nodes_[2]->id()); | 172 CHECK(n2->id() == node_visitor.nodes_[2]->id()); |
| 173 } | 173 } |
| 174 | 174 |
| 175 | 175 |
| 176 struct ReenterNodeVisitor : NullNodeVisitor { | 176 struct ReenterNodeVisitor : NullNodeVisitor { |
| 177 GenericGraphVisit::Control Pre(Node* node) { | 177 GenericGraphVisit::Control Pre(Node* node) { |
| 178 printf("[%d] PRE NODE: %d\n", static_cast<int>(nodes_.size()), node->id()); | 178 printf("[%d] PRE NODE: %d\n", static_cast<int>(nodes_.size()), node->id()); |
| 179 nodes_.push_back(node->id()); | 179 nodes_.push_back(node->id()); |
| 180 int size = nodes_.size(); | 180 int size = static_cast<int>(nodes_.size()); |
| 181 switch (node->id()) { | 181 switch (node->id()) { |
| 182 case 0: | 182 case 0: |
| 183 return size < 6 ? GenericGraphVisit::REENTER : GenericGraphVisit::SKIP; | 183 return size < 6 ? GenericGraphVisit::REENTER : GenericGraphVisit::SKIP; |
| 184 case 1: | 184 case 1: |
| 185 return size < 4 ? GenericGraphVisit::DEFER | 185 return size < 4 ? GenericGraphVisit::DEFER |
| 186 : GenericGraphVisit::CONTINUE; | 186 : GenericGraphVisit::CONTINUE; |
| 187 default: | 187 default: |
| 188 return GenericGraphVisit::REENTER; | 188 return GenericGraphVisit::REENTER; |
| 189 } | 189 } |
| 190 } | 190 } |
| (...skipping 30 matching lines...) Expand all Loading... |
| 221 Node* n3 = graph.NewNode(&dummy_operator, n2); | 221 Node* n3 = graph.NewNode(&dummy_operator, n2); |
| 222 Node* n4 = graph.NewNode(&dummy_operator, n0); | 222 Node* n4 = graph.NewNode(&dummy_operator, n0); |
| 223 Node* n5 = graph.NewNode(&dummy_operator, n4); | 223 Node* n5 = graph.NewNode(&dummy_operator, n4); |
| 224 n0->AppendInput(graph.main_zone(), n3); | 224 n0->AppendInput(graph.main_zone(), n3); |
| 225 graph.SetStart(n0); | 225 graph.SetStart(n0); |
| 226 graph.SetEnd(n5); | 226 graph.SetEnd(n5); |
| 227 | 227 |
| 228 ReenterNodeVisitor visitor; | 228 ReenterNodeVisitor visitor; |
| 229 graph.VisitNodeUsesFromStart(&visitor); | 229 graph.VisitNodeUsesFromStart(&visitor); |
| 230 | 230 |
| 231 CHECK_EQ(22, visitor.nodes_.size()); | 231 CHECK_EQ(22, static_cast<int>(visitor.nodes_.size())); |
| 232 CHECK_EQ(24, visitor.edges_.size()); | 232 CHECK_EQ(24, static_cast<int>(visitor.edges_.size())); |
| 233 | 233 |
| 234 CHECK(n0->id() == visitor.nodes_[0]); | 234 CHECK(n0->id() == visitor.nodes_[0]); |
| 235 CHECK(n0->id() == visitor.edges_[0].first); | 235 CHECK(n0->id() == visitor.edges_[0].first); |
| 236 CHECK(n1->id() == visitor.edges_[0].second); | 236 CHECK(n1->id() == visitor.edges_[0].second); |
| 237 CHECK(n1->id() == visitor.nodes_[1]); | 237 CHECK(n1->id() == visitor.nodes_[1]); |
| 238 // N1 is deferred. | 238 // N1 is deferred. |
| 239 CHECK(-n1->id() == visitor.edges_[1].second); | 239 CHECK(-n1->id() == visitor.edges_[1].second); |
| 240 CHECK(-n0->id() == visitor.edges_[1].first); | 240 CHECK(-n0->id() == visitor.edges_[1].first); |
| 241 CHECK(n0->id() == visitor.edges_[2].first); | 241 CHECK(n0->id() == visitor.edges_[2].first); |
| 242 CHECK(n2->id() == visitor.edges_[2].second); | 242 CHECK(n2->id() == visitor.edges_[2].second); |
| (...skipping 78 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 321 Node* n9 = graph.NewNode(&dummy_operator, n5); | 321 Node* n9 = graph.NewNode(&dummy_operator, n5); |
| 322 Node* n10 = graph.NewNode(&dummy_operator, n9); | 322 Node* n10 = graph.NewNode(&dummy_operator, n9); |
| 323 Node* n11 = graph.NewNode(&dummy_operator, n9); | 323 Node* n11 = graph.NewNode(&dummy_operator, n9); |
| 324 Node* end_dependencies[6] = {n4, n8, n10, n11, n6, n7}; | 324 Node* end_dependencies[6] = {n4, n8, n10, n11, n6, n7}; |
| 325 Node* n12 = graph.NewNode(&dummy_operator, 6, end_dependencies); | 325 Node* n12 = graph.NewNode(&dummy_operator, 6, end_dependencies); |
| 326 graph.SetEnd(n12); | 326 graph.SetEnd(n12); |
| 327 | 327 |
| 328 OFStream os(stdout); | 328 OFStream os(stdout); |
| 329 os << AsDOT(graph); | 329 os << AsDOT(graph); |
| 330 } | 330 } |
| OLD | NEW |